]>
Commit | Line | Data |
---|---|---|
7453a54e SL |
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. | |
4 | // | |
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. | |
10 | ||
11 | // Representing terms | |
12 | // | |
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). | |
16 | // | |
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 | |
20 | // a variable. | |
21 | ||
22 | use arena::TypedArena; | |
23 | use dep_graph::DepTrackingMapConfig; | |
54a0048b SL |
24 | use rustc::ty::{self, TyCtxt}; |
25 | use rustc::ty::maps::ItemVariances; | |
7453a54e SL |
26 | use std::fmt; |
27 | use std::rc::Rc; | |
28 | use syntax::ast; | |
54a0048b SL |
29 | use rustc::hir; |
30 | use rustc::hir::intravisit::Visitor; | |
7453a54e SL |
31 | use util::nodemap::NodeMap; |
32 | ||
33 | use self::VarianceTerm::*; | |
7453a54e SL |
34 | |
35 | pub type VarianceTermPtr<'a> = &'a VarianceTerm<'a>; | |
36 | ||
37 | #[derive(Copy, Clone, Debug)] | |
38 | pub struct InferredIndex(pub usize); | |
39 | ||
40 | #[derive(Copy, Clone)] | |
41 | pub enum VarianceTerm<'a> { | |
42 | ConstantTerm(ty::Variance), | |
43 | TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>), | |
44 | InferredTerm(InferredIndex), | |
45 | } | |
46 | ||
47 | impl<'a> fmt::Debug for VarianceTerm<'a> { | |
48 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
49 | match *self { | |
50 | ConstantTerm(c1) => write!(f, "{:?}", c1), | |
51 | TransformTerm(v1, v2) => write!(f, "({:?} \u{00D7} {:?})", v1, v2), | |
9e0c209e SL |
52 | InferredTerm(id) => { |
53 | write!(f, "[{}]", { | |
54 | let InferredIndex(i) = id; | |
55 | i | |
56 | }) | |
57 | } | |
7453a54e SL |
58 | } |
59 | } | |
60 | } | |
61 | ||
62 | // The first pass over the crate simply builds up the set of inferreds. | |
63 | ||
64 | pub struct TermsContext<'a, 'tcx: 'a> { | |
a7813a04 | 65 | pub tcx: TyCtxt<'a, 'tcx, 'tcx>, |
7453a54e SL |
66 | pub arena: &'a TypedArena<VarianceTerm<'a>>, |
67 | ||
9e0c209e | 68 | pub empty_variances: Rc<Vec<ty::Variance>>, |
7453a54e SL |
69 | |
70 | // For marker types, UnsafeCell, and other lang items where | |
71 | // variance is hardcoded, records the item-id and the hardcoded | |
72 | // variance. | |
73 | pub lang_items: Vec<(ast::NodeId, Vec<ty::Variance>)>, | |
74 | ||
75 | // Maps from the node id of a type/generic parameter to the | |
76 | // corresponding inferred index. | |
77 | pub inferred_map: NodeMap<InferredIndex>, | |
78 | ||
79 | // Maps from an InferredIndex to the info for that variable. | |
9e0c209e | 80 | pub inferred_infos: Vec<InferredInfo<'a>>, |
7453a54e SL |
81 | } |
82 | ||
83 | pub struct InferredInfo<'a> { | |
84 | pub item_id: ast::NodeId, | |
7453a54e SL |
85 | pub index: usize, |
86 | pub param_id: ast::NodeId, | |
87 | pub term: VarianceTermPtr<'a>, | |
88 | ||
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, | |
93 | } | |
94 | ||
9e0c209e SL |
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> { | |
7453a54e SL |
98 | let mut terms_cx = TermsContext { |
99 | tcx: tcx, | |
100 | arena: arena, | |
101 | inferred_map: NodeMap(), | |
102 | inferred_infos: Vec::new(), | |
103 | ||
104 | lang_items: lang_items(tcx), | |
105 | ||
106 | // cache and share the variance struct used for items with | |
107 | // no type/region parameters | |
9e0c209e | 108 | empty_variances: Rc::new(vec![]), |
7453a54e SL |
109 | }; |
110 | ||
111 | // See README.md for a discussion on dep-graph management. | |
9e0c209e | 112 | tcx.visit_all_items_in_krate(|def_id| ItemVariances::to_dep_node(&def_id), &mut terms_cx); |
7453a54e SL |
113 | |
114 | terms_cx | |
115 | } | |
116 | ||
9e0c209e | 117 | fn lang_items(tcx: TyCtxt) -> Vec<(ast::NodeId, Vec<ty::Variance>)> { |
7453a54e SL |
118 | let all = vec![ |
119 | (tcx.lang_items.phantom_data(), vec![ty::Covariant]), | |
120 | (tcx.lang_items.unsafe_cell_type(), vec![ty::Invariant]), | |
121 | ||
122 | // Deprecated: | |
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]), | |
129 | ||
130 | ]; | |
131 | ||
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.map.as_local_node_id(d).map(|n| (n, v))) // (NodeId, Variance) | |
136 | .collect() | |
137 | } | |
138 | ||
139 | impl<'a, 'tcx> TermsContext<'a, 'tcx> { | |
140 | fn add_inferreds_for_item(&mut self, | |
141 | item_id: ast::NodeId, | |
142 | has_self: bool, | |
9e0c209e SL |
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. | |
149 | //! | |
7453a54e SL |
150 | |
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. | |
154 | ||
155 | let inferreds_on_entry = self.num_inferred(); | |
156 | ||
157 | if has_self { | |
9e0c209e | 158 | self.add_inferred(item_id, 0, item_id); |
7453a54e SL |
159 | } |
160 | ||
161 | for (i, p) in generics.lifetimes.iter().enumerate() { | |
162 | let id = p.lifetime.id; | |
9e0c209e SL |
163 | let i = has_self as usize + i; |
164 | self.add_inferred(item_id, i, id); | |
7453a54e SL |
165 | } |
166 | ||
167 | for (i, p) in generics.ty_params.iter().enumerate() { | |
9e0c209e SL |
168 | let i = has_self as usize + generics.lifetimes.len() + i; |
169 | self.add_inferred(item_id, i, p.id); | |
7453a54e SL |
170 | } |
171 | ||
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 | |
178 | // parameters". | |
179 | if self.num_inferred() == inferreds_on_entry { | |
180 | let item_def_id = self.tcx.map.local_def_id(item_id); | |
9e0c209e SL |
181 | let newly_added = self.tcx |
182 | .item_variance_map | |
183 | .borrow_mut() | |
184 | .insert(item_def_id, self.empty_variances.clone()) | |
185 | .is_none(); | |
7453a54e SL |
186 | assert!(newly_added); |
187 | } | |
188 | } | |
189 | ||
9e0c209e | 190 | fn add_inferred(&mut self, item_id: ast::NodeId, index: usize, param_id: ast::NodeId) { |
7453a54e SL |
191 | let inf_index = InferredIndex(self.inferred_infos.len()); |
192 | let term = self.arena.alloc(InferredTerm(inf_index)); | |
9e0c209e SL |
193 | let initial_variance = self.pick_initial_variance(item_id, index); |
194 | self.inferred_infos.push(InferredInfo { | |
195 | item_id: item_id, | |
196 | index: index, | |
197 | param_id: param_id, | |
198 | term: term, | |
199 | initial_variance: initial_variance, | |
200 | }); | |
7453a54e SL |
201 | let newly_added = self.inferred_map.insert(param_id, inf_index).is_none(); |
202 | assert!(newly_added); | |
203 | ||
204 | debug!("add_inferred(item_path={}, \ | |
205 | item_id={}, \ | |
7453a54e SL |
206 | index={}, \ |
207 | param_id={}, \ | |
208 | inf_index={:?}, \ | |
209 | initial_variance={:?})", | |
210 | self.tcx.item_path_str(self.tcx.map.local_def_id(item_id)), | |
9e0c209e SL |
211 | item_id, |
212 | index, | |
213 | param_id, | |
214 | inf_index, | |
7453a54e SL |
215 | initial_variance); |
216 | } | |
217 | ||
9e0c209e SL |
218 | fn pick_initial_variance(&self, item_id: ast::NodeId, index: usize) -> ty::Variance { |
219 | match self.lang_items.iter().find(|&&(n, _)| n == item_id) { | |
220 | Some(&(_, ref variances)) => variances[index], | |
221 | None => ty::Bivariant, | |
7453a54e SL |
222 | } |
223 | } | |
224 | ||
225 | pub fn num_inferred(&self) -> usize { | |
226 | self.inferred_infos.len() | |
227 | } | |
228 | } | |
229 | ||
230 | impl<'a, 'tcx, 'v> Visitor<'v> for TermsContext<'a, 'tcx> { | |
231 | fn visit_item(&mut self, item: &hir::Item) { | |
9e0c209e SL |
232 | debug!("add_inferreds for item {}", |
233 | self.tcx.map.node_to_string(item.id)); | |
7453a54e SL |
234 | |
235 | match item.node { | |
236 | hir::ItemEnum(_, ref generics) | | |
9e0c209e SL |
237 | hir::ItemStruct(_, ref generics) | |
238 | hir::ItemUnion(_, ref generics) => { | |
7453a54e SL |
239 | self.add_inferreds_for_item(item.id, false, generics); |
240 | } | |
9e0c209e | 241 | hir::ItemTrait(_, ref generics, ..) => { |
7453a54e SL |
242 | // Note: all inputs for traits are ultimately |
243 | // constrained to be invariant. See `visit_item` in | |
244 | // the impl for `ConstraintContext` in `constraints.rs`. | |
245 | self.add_inferreds_for_item(item.id, true, generics); | |
246 | } | |
247 | ||
248 | hir::ItemExternCrate(_) | | |
249 | hir::ItemUse(_) | | |
250 | hir::ItemDefaultImpl(..) | | |
251 | hir::ItemImpl(..) | | |
252 | hir::ItemStatic(..) | | |
253 | hir::ItemConst(..) | | |
254 | hir::ItemFn(..) | | |
255 | hir::ItemMod(..) | | |
256 | hir::ItemForeignMod(..) | | |
9e0c209e | 257 | hir::ItemTy(..) => {} |
7453a54e SL |
258 | } |
259 | } | |
260 | } |