1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
13 // Terms are structured as a straightforward tree. Rather than rely on
14 // GC, we allocate terms out of a bounded arena (the lifetime of this
15 // arena is the lifetime 'a that is threaded around).
17 // We assign a unique index to each type/region parameter whose variance
18 // is to be inferred. We refer to such variables as "inferreds". An
19 // `InferredIndex` is a newtype'd int representing the index of such
22 use arena::TypedArena;
23 use rustc::ty::{self, TyCtxt};
28 use rustc::hir::itemlikevisit::ItemLikeVisitor;
29 use util::nodemap::NodeMap;
31 use self::VarianceTerm::*;
33 pub type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
35 use dep_graph::DepNode::ItemSignature as VarianceDepNode;
37 #[derive(Copy, Clone, Debug)]
38 pub struct InferredIndex(pub usize);
40 #[derive(Copy, Clone)]
41 pub enum VarianceTerm<'a> {
42 ConstantTerm(ty::Variance),
43 TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
44 InferredTerm(InferredIndex),
47 impl<'a> fmt::Debug for VarianceTerm<'a> {
48 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
50 ConstantTerm(c1) => write!(f, "{:?}", c1),
51 TransformTerm(v1, v2) => write!(f, "({:?} \u{00D7} {:?})", v1, v2),
54 let InferredIndex(i) = id;
62 // The first pass over the crate simply builds up the set of inferreds.
64 pub struct TermsContext<'a, 'tcx: 'a> {
65 pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
66 pub arena: &'a TypedArena<VarianceTerm<'a>>,
68 pub empty_variances: Rc<Vec<ty::Variance>>,
70 // For marker types, UnsafeCell, and other lang items where
71 // variance is hardcoded, records the item-id and the hardcoded
73 pub lang_items: Vec<(ast::NodeId, Vec<ty::Variance>)>,
75 // Maps from the node id of a type/generic parameter to the
76 // corresponding inferred index.
77 pub inferred_map: NodeMap<InferredIndex>,
79 // Maps from an InferredIndex to the info for that variable.
80 pub inferred_infos: Vec<InferredInfo<'a>>,
83 pub struct InferredInfo<'a> {
84 pub item_id: ast::NodeId,
86 pub param_id: ast::NodeId,
87 pub term: VarianceTermPtr<'a>,
89 // Initial value to use for this parameter when inferring
90 // variance. For most parameters, this is Bivariant. But for lang
91 // items and input type parameters on traits, it is different.
92 pub initial_variance: ty::Variance,
95 pub fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
96 arena: &'a mut TypedArena<VarianceTerm<'a>>)
97 -> TermsContext<'a, 'tcx> {
98 let mut terms_cx = TermsContext {
101 inferred_map: NodeMap(),
102 inferred_infos: Vec::new(),
104 lang_items: lang_items(tcx),
106 // cache and share the variance struct used for items with
107 // no type/region parameters
108 empty_variances: Rc::new(vec![]),
111 // See README.md for a discussion on dep-graph management.
112 tcx.visit_all_item_likes_in_krate(|def_id| VarianceDepNode(def_id), &mut terms_cx);
117 fn lang_items(tcx: TyCtxt) -> Vec<(ast::NodeId, Vec<ty::Variance>)> {
119 (tcx.lang_items.phantom_data(), vec![ty::Covariant]),
120 (tcx.lang_items.unsafe_cell_type(), vec![ty::Invariant]),
123 (tcx.lang_items.covariant_type(), vec![ty::Covariant]),
124 (tcx.lang_items.contravariant_type(), vec![ty::Contravariant]),
125 (tcx.lang_items.invariant_type(), vec![ty::Invariant]),
126 (tcx.lang_items.covariant_lifetime(), vec![ty::Covariant]),
127 (tcx.lang_items.contravariant_lifetime(), vec![ty::Contravariant]),
128 (tcx.lang_items.invariant_lifetime(), vec![ty::Invariant]),
132 all.into_iter() // iterating over (Option<DefId>, Variance)
133 .filter(|&(ref d,_)| d.is_some())
134 .map(|(d, v)| (d.unwrap(), v)) // (DefId, Variance)
135 .filter_map(|(d, v)| tcx.hir.as_local_node_id(d).map(|n| (n, v))) // (NodeId, Variance)
139 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
140 fn add_inferreds_for_item(&mut self,
141 item_id: ast::NodeId,
143 generics: &hir::Generics) {
144 //! Add "inferreds" for the generic parameters declared on this
145 //! item. This has a lot of annoying parameters because we are
146 //! trying to drive this from the AST, rather than the
147 //! ty::Generics, so that we can get span info -- but this
148 //! means we must accommodate syntactic distinctions.
151 // NB: In the code below for writing the results back into the
152 // tcx, we rely on the fact that all inferreds for a particular
153 // item are assigned continuous indices.
155 let inferreds_on_entry = self.num_inferred();
158 self.add_inferred(item_id, 0, item_id);
161 for (i, p) in generics.lifetimes.iter().enumerate() {
162 let id = p.lifetime.id;
163 let i = has_self as usize + i;
164 self.add_inferred(item_id, i, id);
167 for (i, p) in generics.ty_params.iter().enumerate() {
168 let i = has_self as usize + generics.lifetimes.len() + i;
169 self.add_inferred(item_id, i, p.id);
172 // If this item has no type or lifetime parameters,
173 // then there are no variances to infer, so just
174 // insert an empty entry into the variance map.
175 // Arguably we could just leave the map empty in this
176 // case but it seems cleaner to be able to distinguish
177 // "invalid item id" from "item id with no
179 if self.num_inferred() == inferreds_on_entry {
180 let item_def_id = self.tcx.hir.local_def_id(item_id);
181 self.tcx.maps.variances
183 .insert(item_def_id, self.empty_variances.clone());
187 fn add_inferred(&mut self, item_id: ast::NodeId, index: usize, param_id: ast::NodeId) {
188 let inf_index = InferredIndex(self.inferred_infos.len());
189 let term = self.arena.alloc(InferredTerm(inf_index));
190 let initial_variance = self.pick_initial_variance(item_id, index);
191 self.inferred_infos.push(InferredInfo {
196 initial_variance: initial_variance,
198 let newly_added = self.inferred_map.insert(param_id, inf_index).is_none();
199 assert!(newly_added);
201 debug!("add_inferred(item_path={}, \
206 initial_variance={:?})",
207 self.tcx.item_path_str(self.tcx.hir.local_def_id(item_id)),
215 fn pick_initial_variance(&self, item_id: ast::NodeId, index: usize) -> ty::Variance {
216 match self.lang_items.iter().find(|&&(n, _)| n == item_id) {
217 Some(&(_, ref variances)) => variances[index],
218 None => ty::Bivariant,
222 pub fn num_inferred(&self) -> usize {
223 self.inferred_infos.len()
227 impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for TermsContext<'a, 'tcx> {
228 fn visit_item(&mut self, item: &hir::Item) {
229 debug!("add_inferreds for item {}",
230 self.tcx.hir.node_to_string(item.id));
233 hir::ItemEnum(_, ref generics) |
234 hir::ItemStruct(_, ref generics) |
235 hir::ItemUnion(_, ref generics) => {
236 self.add_inferreds_for_item(item.id, false, generics);
238 hir::ItemTrait(_, ref generics, ..) => {
239 // Note: all inputs for traits are ultimately
240 // constrained to be invariant. See `visit_item` in
241 // the impl for `ConstraintContext` in `constraints.rs`.
242 self.add_inferreds_for_item(item.id, true, generics);
245 hir::ItemExternCrate(_) |
247 hir::ItemDefaultImpl(..) |
249 hir::ItemStatic(..) |
253 hir::ItemForeignMod(..) |
254 hir::ItemTy(..) => {}
258 fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem) {
261 fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) {