]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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 | //! This file infers the variance of type and lifetime parameters. The | |
12 | //! algorithm is taken from Section 4 of the paper "Taming the Wildcards: | |
13 | //! Combining Definition- and Use-Site Variance" published in PLDI'11 and | |
14 | //! written by Altidor et al., and hereafter referred to as The Paper. | |
15 | //! | |
16 | //! This inference is explicitly designed *not* to consider the uses of | |
17 | //! types within code. To determine the variance of type parameters | |
18 | //! defined on type `X`, we only consider the definition of the type `X` | |
19 | //! and the definitions of any types it references. | |
20 | //! | |
9346a6ac AL |
21 | //! We only infer variance for type parameters found on *data types* |
22 | //! like structs and enums. In these cases, there is fairly straightforward | |
23 | //! explanation for what variance means. The variance of the type | |
1a4d82fc JJ |
24 | //! or lifetime parameters defines whether `T<A>` is a subtype of `T<B>` |
25 | //! (resp. `T<'a>` and `T<'b>`) based on the relationship of `A` and `B` | |
9346a6ac AL |
26 | //! (resp. `'a` and `'b`). |
27 | //! | |
28 | //! We do not infer variance for type parameters found on traits, fns, | |
29 | //! or impls. Variance on trait parameters can make indeed make sense | |
30 | //! (and we used to compute it) but it is actually rather subtle in | |
31 | //! meaning and not that useful in practice, so we removed it. See the | |
32 | //! addendum for some details. Variances on fn/impl parameters, otoh, | |
33 | //! doesn't make sense because these parameters are instantiated and | |
34 | //! then forgotten, they don't persist in types or compiled | |
35 | //! byproducts. | |
36 | //! | |
37 | //! ### The algorithm | |
38 | //! | |
39 | //! The basic idea is quite straightforward. We iterate over the types | |
40 | //! defined and, for each use of a type parameter X, accumulate a | |
41 | //! constraint indicating that the variance of X must be valid for the | |
42 | //! variance of that use site. We then iteratively refine the variance of | |
43 | //! X until all constraints are met. There is *always* a sol'n, because at | |
44 | //! the limit we can declare all type parameters to be invariant and all | |
45 | //! constraints will be satisfied. | |
46 | //! | |
47 | //! As a simple example, consider: | |
48 | //! | |
49 | //! enum Option<A> { Some(A), None } | |
50 | //! enum OptionalFn<B> { Some(|B|), None } | |
51 | //! enum OptionalMap<C> { Some(|C| -> C), None } | |
52 | //! | |
53 | //! Here, we will generate the constraints: | |
54 | //! | |
55 | //! 1. V(A) <= + | |
56 | //! 2. V(B) <= - | |
57 | //! 3. V(C) <= + | |
58 | //! 4. V(C) <= - | |
59 | //! | |
60 | //! These indicate that (1) the variance of A must be at most covariant; | |
61 | //! (2) the variance of B must be at most contravariant; and (3, 4) the | |
62 | //! variance of C must be at most covariant *and* contravariant. All of these | |
63 | //! results are based on a variance lattice defined as follows: | |
64 | //! | |
65 | //! * Top (bivariant) | |
66 | //! - + | |
67 | //! o Bottom (invariant) | |
68 | //! | |
69 | //! Based on this lattice, the solution V(A)=+, V(B)=-, V(C)=o is the | |
70 | //! optimal solution. Note that there is always a naive solution which | |
71 | //! just declares all variables to be invariant. | |
72 | //! | |
73 | //! You may be wondering why fixed-point iteration is required. The reason | |
74 | //! is that the variance of a use site may itself be a function of the | |
75 | //! variance of other type parameters. In full generality, our constraints | |
76 | //! take the form: | |
77 | //! | |
78 | //! V(X) <= Term | |
79 | //! Term := + | - | * | o | V(X) | Term x Term | |
80 | //! | |
81 | //! Here the notation V(X) indicates the variance of a type/region | |
82 | //! parameter `X` with respect to its defining class. `Term x Term` | |
83 | //! represents the "variance transform" as defined in the paper: | |
84 | //! | |
85 | //! If the variance of a type variable `X` in type expression `E` is `V2` | |
86 | //! and the definition-site variance of the [corresponding] type parameter | |
87 | //! of a class `C` is `V1`, then the variance of `X` in the type expression | |
88 | //! `C<E>` is `V3 = V1.xform(V2)`. | |
89 | //! | |
90 | //! ### Constraints | |
91 | //! | |
92 | //! If I have a struct or enum with where clauses: | |
93 | //! | |
94 | //! struct Foo<T:Bar> { ... } | |
95 | //! | |
96 | //! you might wonder whether the variance of `T` with respect to `Bar` | |
97 | //! affects the variance `T` with respect to `Foo`. I claim no. The | |
98 | //! reason: assume that `T` is invariant w/r/t `Bar` but covariant w/r/t | |
99 | //! `Foo`. And then we have a `Foo<X>` that is upcast to `Foo<Y>`, where | |
100 | //! `X <: Y`. However, while `X : Bar`, `Y : Bar` does not hold. In that | |
101 | //! case, the upcast will be illegal, but not because of a variance | |
102 | //! failure, but rather because the target type `Foo<Y>` is itself just | |
103 | //! not well-formed. Basically we get to assume well-formedness of all | |
104 | //! types involved before considering variance. | |
105 | //! | |
106 | //! ### Addendum: Variance on traits | |
1a4d82fc | 107 | //! |
9346a6ac AL |
108 | //! As mentioned above, we used to permit variance on traits. This was |
109 | //! computed based on the appearance of trait type parameters in | |
110 | //! method signatures and was used to represent the compatibility of | |
111 | //! vtables in trait objects (and also "virtual" vtables or dictionary | |
112 | //! in trait bounds). One complication was that variance for | |
113 | //! associated types is less obvious, since they can be projected out | |
114 | //! and put to myriad uses, so it's not clear when it is safe to allow | |
115 | //! `X<A>::Bar` to vary (or indeed just what that means). Moreover (as | |
116 | //! covered below) all inputs on any trait with an associated type had | |
117 | //! to be invariant, limiting the applicability. Finally, the | |
118 | //! annotations (`MarkerTrait`, `PhantomFn`) needed to ensure that all | |
119 | //! trait type parameters had a variance were confusing and annoying | |
120 | //! for little benefit. | |
1a4d82fc | 121 | //! |
9346a6ac AL |
122 | //! Just for historical reference,I am going to preserve some text indicating |
123 | //! how one could interpret variance and trait matching. | |
1a4d82fc | 124 | //! |
9346a6ac | 125 | //! #### Variance and object types |
1a4d82fc | 126 | //! |
9346a6ac AL |
127 | //! Just as with structs and enums, we can decide the subtyping |
128 | //! relationship between two object types `&Trait<A>` and `&Trait<B>` | |
129 | //! based on the relationship of `A` and `B`. Note that for object | |
130 | //! types we ignore the `Self` type parameter -- it is unknown, and | |
131 | //! the nature of dynamic dispatch ensures that we will always call a | |
1a4d82fc | 132 | //! function that is expected the appropriate `Self` type. However, we |
9346a6ac AL |
133 | //! must be careful with the other type parameters, or else we could |
134 | //! end up calling a function that is expecting one type but provided | |
135 | //! another. | |
1a4d82fc JJ |
136 | //! |
137 | //! To see what I mean, consider a trait like so: | |
138 | //! | |
139 | //! trait ConvertTo<A> { | |
140 | //! fn convertTo(&self) -> A; | |
141 | //! } | |
142 | //! | |
143 | //! Intuitively, If we had one object `O=&ConvertTo<Object>` and another | |
144 | //! `S=&ConvertTo<String>`, then `S <: O` because `String <: Object` | |
145 | //! (presuming Java-like "string" and "object" types, my go to examples | |
146 | //! for subtyping). The actual algorithm would be to compare the | |
147 | //! (explicit) type parameters pairwise respecting their variance: here, | |
148 | //! the type parameter A is covariant (it appears only in a return | |
149 | //! position), and hence we require that `String <: Object`. | |
150 | //! | |
151 | //! You'll note though that we did not consider the binding for the | |
152 | //! (implicit) `Self` type parameter: in fact, it is unknown, so that's | |
153 | //! good. The reason we can ignore that parameter is precisely because we | |
154 | //! don't need to know its value until a call occurs, and at that time (as | |
155 | //! you said) the dynamic nature of virtual dispatch means the code we run | |
156 | //! will be correct for whatever value `Self` happens to be bound to for | |
157 | //! the particular object whose method we called. `Self` is thus different | |
158 | //! from `A`, because the caller requires that `A` be known in order to | |
159 | //! know the return type of the method `convertTo()`. (As an aside, we | |
160 | //! have rules preventing methods where `Self` appears outside of the | |
161 | //! receiver position from being called via an object.) | |
162 | //! | |
163 | //! #### Trait variance and vtable resolution | |
164 | //! | |
165 | //! But traits aren't only used with objects. They're also used when | |
166 | //! deciding whether a given impl satisfies a given trait bound. To set the | |
167 | //! scene here, imagine I had a function: | |
168 | //! | |
169 | //! fn convertAll<A,T:ConvertTo<A>>(v: &[T]) { | |
170 | //! ... | |
171 | //! } | |
172 | //! | |
173 | //! Now imagine that I have an implementation of `ConvertTo` for `Object`: | |
174 | //! | |
175 | //! impl ConvertTo<int> for Object { ... } | |
176 | //! | |
177 | //! And I want to call `convertAll` on an array of strings. Suppose | |
178 | //! further that for whatever reason I specifically supply the value of | |
179 | //! `String` for the type parameter `T`: | |
180 | //! | |
d9579d0f AL |
181 | //! let mut vector = vec!["string", ...]; |
182 | //! convertAll::<int, String>(vector); | |
1a4d82fc JJ |
183 | //! |
184 | //! Is this legal? To put another way, can we apply the `impl` for | |
185 | //! `Object` to the type `String`? The answer is yes, but to see why | |
186 | //! we have to expand out what will happen: | |
187 | //! | |
188 | //! - `convertAll` will create a pointer to one of the entries in the | |
189 | //! vector, which will have type `&String` | |
190 | //! - It will then call the impl of `convertTo()` that is intended | |
191 | //! for use with objects. This has the type: | |
192 | //! | |
193 | //! fn(self: &Object) -> int | |
194 | //! | |
195 | //! It is ok to provide a value for `self` of type `&String` because | |
196 | //! `&String <: &Object`. | |
197 | //! | |
198 | //! OK, so intuitively we want this to be legal, so let's bring this back | |
199 | //! to variance and see whether we are computing the correct result. We | |
200 | //! must first figure out how to phrase the question "is an impl for | |
201 | //! `Object,int` usable where an impl for `String,int` is expected?" | |
202 | //! | |
203 | //! Maybe it's helpful to think of a dictionary-passing implementation of | |
204 | //! type classes. In that case, `convertAll()` takes an implicit parameter | |
205 | //! representing the impl. In short, we *have* an impl of type: | |
206 | //! | |
207 | //! V_O = ConvertTo<int> for Object | |
208 | //! | |
209 | //! and the function prototype expects an impl of type: | |
210 | //! | |
211 | //! V_S = ConvertTo<int> for String | |
212 | //! | |
213 | //! As with any argument, this is legal if the type of the value given | |
214 | //! (`V_O`) is a subtype of the type expected (`V_S`). So is `V_O <: V_S`? | |
215 | //! The answer will depend on the variance of the various parameters. In | |
216 | //! this case, because the `Self` parameter is contravariant and `A` is | |
217 | //! covariant, it means that: | |
218 | //! | |
219 | //! V_O <: V_S iff | |
220 | //! int <: int | |
221 | //! String <: Object | |
222 | //! | |
223 | //! These conditions are satisfied and so we are happy. | |
224 | //! | |
9346a6ac | 225 | //! #### Variance and associated types |
1a4d82fc | 226 | //! |
9346a6ac AL |
227 | //! Traits with associated types -- or at minimum projection |
228 | //! expressions -- must be invariant with respect to all of their | |
229 | //! inputs. To see why this makes sense, consider what subtyping for a | |
230 | //! trait reference means: | |
c34b1796 AL |
231 | //! |
232 | //! <T as Trait> <: <U as Trait> | |
233 | //! | |
9346a6ac AL |
234 | //! means that if I know that `T as Trait`, I also know that `U as |
235 | //! Trait`. Moreover, if you think of it as dictionary passing style, | |
236 | //! it means that a dictionary for `<T as Trait>` is safe to use where | |
237 | //! a dictionary for `<U as Trait>` is expected. | |
c34b1796 | 238 | //! |
9346a6ac AL |
239 | //! The problem is that when you can project types out from `<T as |
240 | //! Trait>`, the relationship to types projected out of `<U as Trait>` | |
241 | //! is completely unknown unless `T==U` (see #21726 for more | |
242 | //! details). Making `Trait` invariant ensures that this is true. | |
c34b1796 AL |
243 | //! |
244 | //! Another related reason is that if we didn't make traits with | |
245 | //! associated types invariant, then projection is no longer a | |
246 | //! function with a single result. Consider: | |
247 | //! | |
248 | //! ``` | |
249 | //! trait Identity { type Out; fn foo(&self); } | |
250 | //! impl<T> Identity for T { type Out = T; ... } | |
251 | //! ``` | |
252 | //! | |
253 | //! Now if I have `<&'static () as Identity>::Out`, this can be | |
254 | //! validly derived as `&'a ()` for any `'a`: | |
255 | //! | |
256 | //! <&'a () as Identity> <: <&'static () as Identity> | |
257 | //! if &'static () < : &'a () -- Identity is contravariant in Self | |
258 | //! if 'static : 'a -- Subtyping rules for relations | |
259 | //! | |
260 | //! This change otoh means that `<'static () as Identity>::Out` is | |
261 | //! always `&'static ()` (which might then be upcast to `'a ()`, | |
262 | //! separately). This was helpful in solving #21750. | |
1a4d82fc JJ |
263 | |
264 | use self::VarianceTerm::*; | |
265 | use self::ParamKind::*; | |
266 | ||
267 | use arena; | |
85aaf69f | 268 | use arena::TypedArena; |
1a4d82fc JJ |
269 | use middle::resolve_lifetime as rl; |
270 | use middle::subst; | |
271 | use middle::subst::{ParamSpace, FnSpace, TypeSpace, SelfSpace, VecPerParamSpace}; | |
272 | use middle::ty::{self, Ty}; | |
273 | use std::fmt; | |
274 | use std::rc::Rc; | |
1a4d82fc JJ |
275 | use syntax::ast; |
276 | use syntax::ast_map; | |
277 | use syntax::ast_util; | |
278 | use syntax::visit; | |
279 | use syntax::visit::Visitor; | |
280 | use util::nodemap::NodeMap; | |
281 | use util::ppaux::Repr; | |
282 | ||
283 | pub fn infer_variance(tcx: &ty::ctxt) { | |
284 | let krate = tcx.map.krate(); | |
85aaf69f | 285 | let mut arena = arena::TypedArena::new(); |
1a4d82fc JJ |
286 | let terms_cx = determine_parameters_to_be_inferred(tcx, &mut arena, krate); |
287 | let constraints_cx = add_constraints_from_crate(terms_cx, krate); | |
288 | solve_constraints(constraints_cx); | |
289 | tcx.variance_computed.set(true); | |
290 | } | |
291 | ||
292 | // Representing terms | |
293 | // | |
294 | // Terms are structured as a straightforward tree. Rather than rely on | |
295 | // GC, we allocate terms out of a bounded arena (the lifetime of this | |
296 | // arena is the lifetime 'a that is threaded around). | |
297 | // | |
298 | // We assign a unique index to each type/region parameter whose variance | |
299 | // is to be inferred. We refer to such variables as "inferreds". An | |
300 | // `InferredIndex` is a newtype'd int representing the index of such | |
301 | // a variable. | |
302 | ||
303 | type VarianceTermPtr<'a> = &'a VarianceTerm<'a>; | |
304 | ||
c34b1796 AL |
305 | #[derive(Copy, Clone, Debug)] |
306 | struct InferredIndex(usize); | |
1a4d82fc | 307 | |
c34b1796 | 308 | #[derive(Copy, Clone)] |
1a4d82fc JJ |
309 | enum VarianceTerm<'a> { |
310 | ConstantTerm(ty::Variance), | |
311 | TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>), | |
312 | InferredTerm(InferredIndex), | |
313 | } | |
314 | ||
85aaf69f | 315 | impl<'a> fmt::Debug for VarianceTerm<'a> { |
1a4d82fc JJ |
316 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
317 | match *self { | |
318 | ConstantTerm(c1) => write!(f, "{:?}", c1), | |
319 | TransformTerm(v1, v2) => write!(f, "({:?} \u{00D7} {:?})", v1, v2), | |
320 | InferredTerm(id) => write!(f, "[{}]", { let InferredIndex(i) = id; i }) | |
321 | } | |
322 | } | |
323 | } | |
324 | ||
325 | // The first pass over the crate simply builds up the set of inferreds. | |
326 | ||
327 | struct TermsContext<'a, 'tcx: 'a> { | |
328 | tcx: &'a ty::ctxt<'tcx>, | |
85aaf69f | 329 | arena: &'a TypedArena<VarianceTerm<'a>>, |
1a4d82fc JJ |
330 | |
331 | empty_variances: Rc<ty::ItemVariances>, | |
332 | ||
85aaf69f SL |
333 | // For marker types, UnsafeCell, and other lang items where |
334 | // variance is hardcoded, records the item-id and the hardcoded | |
335 | // variance. | |
336 | lang_items: Vec<(ast::NodeId, Vec<ty::Variance>)>, | |
337 | ||
1a4d82fc JJ |
338 | // Maps from the node id of a type/generic parameter to the |
339 | // corresponding inferred index. | |
340 | inferred_map: NodeMap<InferredIndex>, | |
341 | ||
342 | // Maps from an InferredIndex to the info for that variable. | |
343 | inferred_infos: Vec<InferredInfo<'a>> , | |
344 | } | |
345 | ||
c34b1796 | 346 | #[derive(Copy, Clone, Debug, PartialEq)] |
1a4d82fc JJ |
347 | enum ParamKind { |
348 | TypeParam, | |
85aaf69f | 349 | RegionParam, |
1a4d82fc JJ |
350 | } |
351 | ||
352 | struct InferredInfo<'a> { | |
353 | item_id: ast::NodeId, | |
354 | kind: ParamKind, | |
355 | space: ParamSpace, | |
c34b1796 | 356 | index: usize, |
1a4d82fc JJ |
357 | param_id: ast::NodeId, |
358 | term: VarianceTermPtr<'a>, | |
85aaf69f SL |
359 | |
360 | // Initial value to use for this parameter when inferring | |
361 | // variance. For most parameters, this is Bivariant. But for lang | |
362 | // items and input type parameters on traits, it is different. | |
363 | initial_variance: ty::Variance, | |
1a4d82fc JJ |
364 | } |
365 | ||
366 | fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>, | |
85aaf69f | 367 | arena: &'a mut TypedArena<VarianceTerm<'a>>, |
1a4d82fc JJ |
368 | krate: &ast::Crate) |
369 | -> TermsContext<'a, 'tcx> { | |
370 | let mut terms_cx = TermsContext { | |
371 | tcx: tcx, | |
372 | arena: arena, | |
85aaf69f | 373 | inferred_map: NodeMap(), |
1a4d82fc JJ |
374 | inferred_infos: Vec::new(), |
375 | ||
85aaf69f SL |
376 | lang_items: lang_items(tcx), |
377 | ||
1a4d82fc JJ |
378 | // cache and share the variance struct used for items with |
379 | // no type/region parameters | |
380 | empty_variances: Rc::new(ty::ItemVariances { | |
381 | types: VecPerParamSpace::empty(), | |
382 | regions: VecPerParamSpace::empty() | |
383 | }) | |
384 | }; | |
385 | ||
386 | visit::walk_crate(&mut terms_cx, krate); | |
387 | ||
388 | terms_cx | |
389 | } | |
390 | ||
85aaf69f SL |
391 | fn lang_items(tcx: &ty::ctxt) -> Vec<(ast::NodeId,Vec<ty::Variance>)> { |
392 | let all = vec![ | |
85aaf69f SL |
393 | (tcx.lang_items.phantom_data(), vec![ty::Covariant]), |
394 | (tcx.lang_items.unsafe_cell_type(), vec![ty::Invariant]), | |
395 | ||
396 | // Deprecated: | |
397 | (tcx.lang_items.covariant_type(), vec![ty::Covariant]), | |
398 | (tcx.lang_items.contravariant_type(), vec![ty::Contravariant]), | |
399 | (tcx.lang_items.invariant_type(), vec![ty::Invariant]), | |
400 | (tcx.lang_items.covariant_lifetime(), vec![ty::Covariant]), | |
401 | (tcx.lang_items.contravariant_lifetime(), vec![ty::Contravariant]), | |
402 | (tcx.lang_items.invariant_lifetime(), vec![ty::Invariant]), | |
403 | ||
404 | ]; | |
405 | ||
406 | all.into_iter() | |
407 | .filter(|&(ref d,_)| d.is_some()) | |
408 | .filter(|&(ref d,_)| d.as_ref().unwrap().krate == ast::LOCAL_CRATE) | |
409 | .map(|(d, v)| (d.unwrap().node, v)) | |
410 | .collect() | |
411 | } | |
412 | ||
1a4d82fc | 413 | impl<'a, 'tcx> TermsContext<'a, 'tcx> { |
85aaf69f SL |
414 | fn add_inferreds_for_item(&mut self, |
415 | item_id: ast::NodeId, | |
416 | has_self: bool, | |
417 | generics: &ast::Generics) | |
418 | { | |
419 | /*! | |
420 | * Add "inferreds" for the generic parameters declared on this | |
421 | * item. This has a lot of annoying parameters because we are | |
422 | * trying to drive this from the AST, rather than the | |
423 | * ty::Generics, so that we can get span info -- but this | |
424 | * means we must accommodate syntactic distinctions. | |
425 | */ | |
426 | ||
427 | // NB: In the code below for writing the results back into the | |
428 | // tcx, we rely on the fact that all inferreds for a particular | |
429 | // item are assigned continuous indices. | |
430 | ||
431 | let inferreds_on_entry = self.num_inferred(); | |
432 | ||
433 | if has_self { | |
434 | self.add_inferred(item_id, TypeParam, SelfSpace, 0, item_id); | |
435 | } | |
436 | ||
437 | for (i, p) in generics.lifetimes.iter().enumerate() { | |
438 | let id = p.lifetime.id; | |
439 | self.add_inferred(item_id, RegionParam, TypeSpace, i, id); | |
440 | } | |
441 | ||
442 | for (i, p) in generics.ty_params.iter().enumerate() { | |
443 | self.add_inferred(item_id, TypeParam, TypeSpace, i, p.id); | |
444 | } | |
445 | ||
446 | // If this item has no type or lifetime parameters, | |
447 | // then there are no variances to infer, so just | |
448 | // insert an empty entry into the variance map. | |
449 | // Arguably we could just leave the map empty in this | |
450 | // case but it seems cleaner to be able to distinguish | |
451 | // "invalid item id" from "item id with no | |
452 | // parameters". | |
453 | if self.num_inferred() == inferreds_on_entry { | |
454 | let newly_added = | |
455 | self.tcx.item_variance_map.borrow_mut().insert( | |
456 | ast_util::local_def(item_id), | |
457 | self.empty_variances.clone()).is_none(); | |
458 | assert!(newly_added); | |
459 | } | |
460 | } | |
461 | ||
1a4d82fc JJ |
462 | fn add_inferred(&mut self, |
463 | item_id: ast::NodeId, | |
464 | kind: ParamKind, | |
465 | space: ParamSpace, | |
c34b1796 | 466 | index: usize, |
1a4d82fc JJ |
467 | param_id: ast::NodeId) { |
468 | let inf_index = InferredIndex(self.inferred_infos.len()); | |
85aaf69f SL |
469 | let term = self.arena.alloc(InferredTerm(inf_index)); |
470 | let initial_variance = self.pick_initial_variance(item_id, space, index); | |
1a4d82fc JJ |
471 | self.inferred_infos.push(InferredInfo { item_id: item_id, |
472 | kind: kind, | |
473 | space: space, | |
474 | index: index, | |
475 | param_id: param_id, | |
85aaf69f SL |
476 | term: term, |
477 | initial_variance: initial_variance }); | |
1a4d82fc JJ |
478 | let newly_added = self.inferred_map.insert(param_id, inf_index).is_none(); |
479 | assert!(newly_added); | |
480 | ||
85aaf69f SL |
481 | debug!("add_inferred(item_path={}, \ |
482 | item_id={}, \ | |
1a4d82fc | 483 | kind={:?}, \ |
85aaf69f | 484 | space={:?}, \ |
1a4d82fc | 485 | index={}, \ |
85aaf69f SL |
486 | param_id={}, \ |
487 | inf_index={:?}, \ | |
488 | initial_variance={:?})", | |
489 | ty::item_path_str(self.tcx, ast_util::local_def(item_id)), | |
490 | item_id, kind, space, index, param_id, inf_index, | |
491 | initial_variance); | |
492 | } | |
493 | ||
494 | fn pick_initial_variance(&self, | |
495 | item_id: ast::NodeId, | |
496 | space: ParamSpace, | |
c34b1796 | 497 | index: usize) |
85aaf69f SL |
498 | -> ty::Variance |
499 | { | |
500 | match space { | |
501 | SelfSpace | FnSpace => { | |
502 | ty::Bivariant | |
503 | } | |
504 | ||
505 | TypeSpace => { | |
506 | match self.lang_items.iter().find(|&&(n, _)| n == item_id) { | |
507 | Some(&(_, ref variances)) => variances[index], | |
508 | None => ty::Bivariant | |
509 | } | |
510 | } | |
511 | } | |
1a4d82fc JJ |
512 | } |
513 | ||
c34b1796 | 514 | fn num_inferred(&self) -> usize { |
1a4d82fc JJ |
515 | self.inferred_infos.len() |
516 | } | |
517 | } | |
518 | ||
519 | impl<'a, 'tcx, 'v> Visitor<'v> for TermsContext<'a, 'tcx> { | |
520 | fn visit_item(&mut self, item: &ast::Item) { | |
521 | debug!("add_inferreds for item {}", item.repr(self.tcx)); | |
522 | ||
1a4d82fc JJ |
523 | match item.node { |
524 | ast::ItemEnum(_, ref generics) | | |
85aaf69f SL |
525 | ast::ItemStruct(_, ref generics) => { |
526 | self.add_inferreds_for_item(item.id, false, generics); | |
527 | } | |
1a4d82fc | 528 | ast::ItemTrait(_, ref generics, _, _) => { |
9346a6ac AL |
529 | // Note: all inputs for traits are ultimately |
530 | // constrained to be invariant. See `visit_item` in | |
531 | // the impl for `ConstraintContext` below. | |
85aaf69f | 532 | self.add_inferreds_for_item(item.id, true, generics); |
1a4d82fc JJ |
533 | visit::walk_item(self, item); |
534 | } | |
535 | ||
85aaf69f SL |
536 | ast::ItemExternCrate(_) | |
537 | ast::ItemUse(_) | | |
c34b1796 | 538 | ast::ItemDefaultImpl(..) | |
1a4d82fc JJ |
539 | ast::ItemImpl(..) | |
540 | ast::ItemStatic(..) | | |
541 | ast::ItemConst(..) | | |
542 | ast::ItemFn(..) | | |
543 | ast::ItemMod(..) | | |
544 | ast::ItemForeignMod(..) | | |
545 | ast::ItemTy(..) | | |
546 | ast::ItemMac(..) => { | |
547 | visit::walk_item(self, item); | |
548 | } | |
549 | } | |
550 | } | |
551 | } | |
552 | ||
553 | // Constraint construction and representation | |
554 | // | |
555 | // The second pass over the AST determines the set of constraints. | |
556 | // We walk the set of items and, for each member, generate new constraints. | |
557 | ||
558 | struct ConstraintContext<'a, 'tcx: 'a> { | |
559 | terms_cx: TermsContext<'a, 'tcx>, | |
560 | ||
1a4d82fc JJ |
561 | // These are pointers to common `ConstantTerm` instances |
562 | covariant: VarianceTermPtr<'a>, | |
563 | contravariant: VarianceTermPtr<'a>, | |
564 | invariant: VarianceTermPtr<'a>, | |
565 | bivariant: VarianceTermPtr<'a>, | |
566 | ||
567 | constraints: Vec<Constraint<'a>> , | |
568 | } | |
569 | ||
570 | /// Declares that the variable `decl_id` appears in a location with | |
571 | /// variance `variance`. | |
c34b1796 | 572 | #[derive(Copy, Clone)] |
1a4d82fc JJ |
573 | struct Constraint<'a> { |
574 | inferred: InferredIndex, | |
575 | variance: &'a VarianceTerm<'a>, | |
576 | } | |
577 | ||
578 | fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>, | |
579 | krate: &ast::Crate) | |
85aaf69f SL |
580 | -> ConstraintContext<'a, 'tcx> |
581 | { | |
582 | let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant)); | |
583 | let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant)); | |
584 | let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant)); | |
585 | let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant)); | |
1a4d82fc JJ |
586 | let mut constraint_cx = ConstraintContext { |
587 | terms_cx: terms_cx, | |
1a4d82fc JJ |
588 | covariant: covariant, |
589 | contravariant: contravariant, | |
590 | invariant: invariant, | |
591 | bivariant: bivariant, | |
592 | constraints: Vec::new(), | |
593 | }; | |
594 | visit::walk_crate(&mut constraint_cx, krate); | |
595 | constraint_cx | |
596 | } | |
597 | ||
598 | impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> { | |
599 | fn visit_item(&mut self, item: &ast::Item) { | |
600 | let did = ast_util::local_def(item.id); | |
601 | let tcx = self.terms_cx.tcx; | |
602 | ||
603 | debug!("visit_item item={}", | |
604 | item.repr(tcx)); | |
605 | ||
606 | match item.node { | |
607 | ast::ItemEnum(ref enum_definition, _) => { | |
85aaf69f SL |
608 | let scheme = ty::lookup_item_type(tcx, did); |
609 | ||
610 | // Not entirely obvious: constraints on structs/enums do not | |
611 | // affect the variance of their type parameters. See discussion | |
612 | // in comment at top of module. | |
613 | // | |
614 | // self.add_constraints_from_generics(&scheme.generics); | |
1a4d82fc JJ |
615 | |
616 | // Hack: If we directly call `ty::enum_variants`, it | |
617 | // annoyingly takes it upon itself to run off and | |
618 | // evaluate the discriminants eagerly (*grumpy* that's | |
619 | // not the typical pattern). This results in double | |
620 | // error messages because typeck goes off and does | |
621 | // this at a later time. All we really care about is | |
622 | // the types of the variant arguments, so we just call | |
623 | // `ty::VariantInfo::from_ast_variant()` ourselves | |
624 | // here, mainly so as to mask the differences between | |
625 | // struct-like enums and so forth. | |
85aaf69f | 626 | for ast_variant in &enum_definition.variants { |
1a4d82fc JJ |
627 | let variant = |
628 | ty::VariantInfo::from_ast_variant(tcx, | |
629 | &**ast_variant, | |
630 | /*discriminant*/ 0); | |
85aaf69f SL |
631 | for arg_ty in &variant.args { |
632 | self.add_constraints_from_ty(&scheme.generics, *arg_ty, self.covariant); | |
1a4d82fc JJ |
633 | } |
634 | } | |
635 | } | |
636 | ||
637 | ast::ItemStruct(..) => { | |
85aaf69f SL |
638 | let scheme = ty::lookup_item_type(tcx, did); |
639 | ||
640 | // Not entirely obvious: constraints on structs/enums do not | |
641 | // affect the variance of their type parameters. See discussion | |
642 | // in comment at top of module. | |
643 | // | |
644 | // self.add_constraints_from_generics(&scheme.generics); | |
645 | ||
1a4d82fc | 646 | let struct_fields = ty::lookup_struct_fields(tcx, did); |
85aaf69f | 647 | for field_info in &struct_fields { |
1a4d82fc JJ |
648 | assert_eq!(field_info.id.krate, ast::LOCAL_CRATE); |
649 | let field_ty = ty::node_id_to_type(tcx, field_info.id.node); | |
85aaf69f | 650 | self.add_constraints_from_ty(&scheme.generics, field_ty, self.covariant); |
1a4d82fc JJ |
651 | } |
652 | } | |
653 | ||
654 | ast::ItemTrait(..) => { | |
85aaf69f | 655 | let trait_def = ty::lookup_trait_def(tcx, did); |
9346a6ac | 656 | self.add_constraints_from_trait_ref(&trait_def.generics, |
d9579d0f | 657 | trait_def.trait_ref, |
9346a6ac | 658 | self.invariant); |
1a4d82fc JJ |
659 | } |
660 | ||
85aaf69f SL |
661 | ast::ItemExternCrate(_) | |
662 | ast::ItemUse(_) | | |
1a4d82fc JJ |
663 | ast::ItemStatic(..) | |
664 | ast::ItemConst(..) | | |
665 | ast::ItemFn(..) | | |
666 | ast::ItemMod(..) | | |
667 | ast::ItemForeignMod(..) | | |
668 | ast::ItemTy(..) | | |
669 | ast::ItemImpl(..) | | |
c34b1796 | 670 | ast::ItemDefaultImpl(..) | |
1a4d82fc | 671 | ast::ItemMac(..) => { |
1a4d82fc JJ |
672 | } |
673 | } | |
85aaf69f SL |
674 | |
675 | visit::walk_item(self, item); | |
1a4d82fc JJ |
676 | } |
677 | } | |
678 | ||
679 | /// Is `param_id` a lifetime according to `map`? | |
680 | fn is_lifetime(map: &ast_map::Map, param_id: ast::NodeId) -> bool { | |
681 | match map.find(param_id) { | |
682 | Some(ast_map::NodeLifetime(..)) => true, _ => false | |
683 | } | |
684 | } | |
685 | ||
686 | impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { | |
687 | fn tcx(&self) -> &'a ty::ctxt<'tcx> { | |
688 | self.terms_cx.tcx | |
689 | } | |
690 | ||
691 | fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex { | |
692 | match self.terms_cx.inferred_map.get(¶m_id) { | |
693 | Some(&index) => index, | |
694 | None => { | |
695 | self.tcx().sess.bug(&format!( | |
696 | "no inferred index entry for {}", | |
c34b1796 | 697 | self.tcx().map.node_to_string(param_id))); |
1a4d82fc JJ |
698 | } |
699 | } | |
700 | } | |
701 | ||
702 | fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId { | |
703 | let tcx = self.terms_cx.tcx; | |
704 | assert!(is_lifetime(&tcx.map, param_id)); | |
705 | match tcx.named_region_map.get(¶m_id) { | |
706 | Some(&rl::DefEarlyBoundRegion(_, _, lifetime_decl_id)) | |
707 | => lifetime_decl_id, | |
708 | Some(_) => panic!("should not encounter non early-bound cases"), | |
709 | ||
710 | // The lookup should only fail when `param_id` is | |
711 | // itself a lifetime binding: use it as the decl_id. | |
712 | None => param_id, | |
713 | } | |
714 | ||
715 | } | |
716 | ||
717 | /// Is `param_id` a type parameter for which we infer variance? | |
718 | fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool { | |
719 | let result = self.terms_cx.inferred_map.contains_key(¶m_id); | |
720 | ||
721 | // To safe-guard against invalid inferred_map constructions, | |
722 | // double-check if variance is inferred at some use of a type | |
723 | // parameter (by inspecting parent of its binding declaration | |
724 | // to see if it is introduced by a type or by a fn/impl). | |
725 | ||
85aaf69f | 726 | let check_result = |this:&ConstraintContext| -> bool { |
1a4d82fc JJ |
727 | let tcx = this.terms_cx.tcx; |
728 | let decl_id = this.find_binding_for_lifetime(param_id); | |
729 | // Currently only called on lifetimes; double-checking that. | |
730 | assert!(is_lifetime(&tcx.map, param_id)); | |
731 | let parent_id = tcx.map.get_parent(decl_id); | |
732 | let parent = tcx.map.find(parent_id).unwrap_or_else( | |
733 | || panic!("tcx.map missing entry for id: {}", parent_id)); | |
734 | ||
735 | let is_inferred; | |
736 | macro_rules! cannot_happen { () => { { | |
737 | panic!("invalid parent: {} for {}", | |
738 | tcx.map.node_to_string(parent_id), | |
739 | tcx.map.node_to_string(param_id)); | |
740 | } } } | |
741 | ||
742 | match parent { | |
743 | ast_map::NodeItem(p) => { | |
744 | match p.node { | |
745 | ast::ItemTy(..) | | |
746 | ast::ItemEnum(..) | | |
747 | ast::ItemStruct(..) | | |
748 | ast::ItemTrait(..) => is_inferred = true, | |
749 | ast::ItemFn(..) => is_inferred = false, | |
750 | _ => cannot_happen!(), | |
751 | } | |
752 | } | |
753 | ast_map::NodeTraitItem(..) => is_inferred = false, | |
754 | ast_map::NodeImplItem(..) => is_inferred = false, | |
755 | _ => cannot_happen!(), | |
756 | } | |
757 | ||
758 | return is_inferred; | |
759 | }; | |
760 | ||
761 | assert_eq!(result, check_result(self)); | |
762 | ||
763 | return result; | |
764 | } | |
765 | ||
766 | /// Returns a variance term representing the declared variance of the type/region parameter | |
767 | /// with the given id. | |
768 | fn declared_variance(&self, | |
769 | param_def_id: ast::DefId, | |
770 | item_def_id: ast::DefId, | |
771 | kind: ParamKind, | |
772 | space: ParamSpace, | |
c34b1796 | 773 | index: usize) |
1a4d82fc JJ |
774 | -> VarianceTermPtr<'a> { |
775 | assert_eq!(param_def_id.krate, item_def_id.krate); | |
776 | ||
85aaf69f | 777 | if param_def_id.krate == ast::LOCAL_CRATE { |
1a4d82fc JJ |
778 | // Parameter on an item defined within current crate: |
779 | // variance not yet inferred, so return a symbolic | |
780 | // variance. | |
781 | let InferredIndex(index) = self.inferred_index(param_def_id.node); | |
782 | self.terms_cx.inferred_infos[index].term | |
783 | } else { | |
784 | // Parameter on an item defined within another crate: | |
785 | // variance already inferred, just look it up. | |
786 | let variances = ty::item_variances(self.tcx(), item_def_id); | |
787 | let variance = match kind { | |
788 | TypeParam => *variances.types.get(space, index), | |
789 | RegionParam => *variances.regions.get(space, index), | |
790 | }; | |
791 | self.constant_term(variance) | |
792 | } | |
793 | } | |
794 | ||
795 | fn add_constraint(&mut self, | |
796 | InferredIndex(index): InferredIndex, | |
797 | variance: VarianceTermPtr<'a>) { | |
798 | debug!("add_constraint(index={}, variance={:?})", | |
799 | index, variance); | |
800 | self.constraints.push(Constraint { inferred: InferredIndex(index), | |
801 | variance: variance }); | |
802 | } | |
803 | ||
804 | fn contravariant(&mut self, | |
805 | variance: VarianceTermPtr<'a>) | |
806 | -> VarianceTermPtr<'a> { | |
807 | self.xform(variance, self.contravariant) | |
808 | } | |
809 | ||
810 | fn invariant(&mut self, | |
811 | variance: VarianceTermPtr<'a>) | |
812 | -> VarianceTermPtr<'a> { | |
813 | self.xform(variance, self.invariant) | |
814 | } | |
815 | ||
816 | fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> { | |
817 | match v { | |
818 | ty::Covariant => self.covariant, | |
819 | ty::Invariant => self.invariant, | |
820 | ty::Contravariant => self.contravariant, | |
821 | ty::Bivariant => self.bivariant, | |
822 | } | |
823 | } | |
824 | ||
825 | fn xform(&mut self, | |
826 | v1: VarianceTermPtr<'a>, | |
827 | v2: VarianceTermPtr<'a>) | |
828 | -> VarianceTermPtr<'a> { | |
829 | match (*v1, *v2) { | |
830 | (_, ConstantTerm(ty::Covariant)) => { | |
831 | // Applying a "covariant" transform is always a no-op | |
832 | v1 | |
833 | } | |
834 | ||
835 | (ConstantTerm(c1), ConstantTerm(c2)) => { | |
836 | self.constant_term(c1.xform(c2)) | |
837 | } | |
838 | ||
839 | _ => { | |
85aaf69f | 840 | &*self.terms_cx.arena.alloc(TransformTerm(v1, v2)) |
1a4d82fc JJ |
841 | } |
842 | } | |
843 | } | |
844 | ||
85aaf69f SL |
845 | fn add_constraints_from_trait_ref(&mut self, |
846 | generics: &ty::Generics<'tcx>, | |
d9579d0f | 847 | trait_ref: ty::TraitRef<'tcx>, |
85aaf69f SL |
848 | variance: VarianceTermPtr<'a>) { |
849 | debug!("add_constraints_from_trait_ref: trait_ref={} variance={:?}", | |
850 | trait_ref.repr(self.tcx()), | |
851 | variance); | |
852 | ||
853 | let trait_def = ty::lookup_trait_def(self.tcx(), trait_ref.def_id); | |
854 | ||
855 | self.add_constraints_from_substs( | |
856 | generics, | |
857 | trait_ref.def_id, | |
858 | trait_def.generics.types.as_slice(), | |
859 | trait_def.generics.regions.as_slice(), | |
860 | trait_ref.substs, | |
861 | variance); | |
862 | } | |
863 | ||
1a4d82fc JJ |
864 | /// Adds constraints appropriate for an instance of `ty` appearing |
865 | /// in a context with the generics defined in `generics` and | |
866 | /// ambient variance `variance` | |
867 | fn add_constraints_from_ty(&mut self, | |
868 | generics: &ty::Generics<'tcx>, | |
869 | ty: Ty<'tcx>, | |
870 | variance: VarianceTermPtr<'a>) { | |
85aaf69f SL |
871 | debug!("add_constraints_from_ty(ty={}, variance={:?})", |
872 | ty.repr(self.tcx()), | |
873 | variance); | |
1a4d82fc JJ |
874 | |
875 | match ty.sty { | |
876 | ty::ty_bool | | |
877 | ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) | | |
878 | ty::ty_float(_) | ty::ty_str => { | |
879 | /* leaf type -- noop */ | |
880 | } | |
881 | ||
85aaf69f SL |
882 | ty::ty_closure(..) => { |
883 | self.tcx().sess.bug("Unexpected closure type in variance computation"); | |
1a4d82fc JJ |
884 | } |
885 | ||
886 | ty::ty_rptr(region, ref mt) => { | |
887 | let contra = self.contravariant(variance); | |
888 | self.add_constraints_from_region(generics, *region, contra); | |
889 | self.add_constraints_from_mt(generics, mt, variance); | |
890 | } | |
891 | ||
c34b1796 | 892 | ty::ty_uniq(typ) | ty::ty_vec(typ, _) => { |
1a4d82fc JJ |
893 | self.add_constraints_from_ty(generics, typ, variance); |
894 | } | |
895 | ||
85aaf69f | 896 | |
1a4d82fc JJ |
897 | ty::ty_ptr(ref mt) => { |
898 | self.add_constraints_from_mt(generics, mt, variance); | |
899 | } | |
900 | ||
901 | ty::ty_tup(ref subtys) => { | |
85aaf69f | 902 | for &subty in subtys { |
1a4d82fc JJ |
903 | self.add_constraints_from_ty(generics, subty, variance); |
904 | } | |
905 | } | |
906 | ||
907 | ty::ty_enum(def_id, substs) | | |
908 | ty::ty_struct(def_id, substs) => { | |
909 | let item_type = ty::lookup_item_type(self.tcx(), def_id); | |
910 | ||
911 | // All type parameters on enums and structs should be | |
912 | // in the TypeSpace. | |
913 | assert!(item_type.generics.types.is_empty_in(subst::SelfSpace)); | |
914 | assert!(item_type.generics.types.is_empty_in(subst::FnSpace)); | |
915 | assert!(item_type.generics.regions.is_empty_in(subst::SelfSpace)); | |
916 | assert!(item_type.generics.regions.is_empty_in(subst::FnSpace)); | |
917 | ||
918 | self.add_constraints_from_substs( | |
919 | generics, | |
920 | def_id, | |
921 | item_type.generics.types.get_slice(subst::TypeSpace), | |
922 | item_type.generics.regions.get_slice(subst::TypeSpace), | |
923 | substs, | |
924 | variance); | |
925 | } | |
926 | ||
927 | ty::ty_projection(ref data) => { | |
928 | let trait_ref = &data.trait_ref; | |
929 | let trait_def = ty::lookup_trait_def(self.tcx(), trait_ref.def_id); | |
930 | self.add_constraints_from_substs( | |
931 | generics, | |
932 | trait_ref.def_id, | |
933 | trait_def.generics.types.as_slice(), | |
934 | trait_def.generics.regions.as_slice(), | |
935 | trait_ref.substs, | |
c34b1796 | 936 | variance); |
1a4d82fc JJ |
937 | } |
938 | ||
939 | ty::ty_trait(ref data) => { | |
85aaf69f SL |
940 | let poly_trait_ref = |
941 | data.principal_trait_ref_with_self_ty(self.tcx(), | |
942 | self.tcx().types.err); | |
1a4d82fc JJ |
943 | |
944 | // The type `Foo<T+'a>` is contravariant w/r/t `'a`: | |
945 | let contra = self.contravariant(variance); | |
946 | self.add_constraints_from_region(generics, data.bounds.region_bound, contra); | |
947 | ||
85aaf69f | 948 | // Ignore the SelfSpace, it is erased. |
d9579d0f | 949 | self.add_constraints_from_trait_ref(generics, poly_trait_ref.0, variance); |
85aaf69f SL |
950 | |
951 | let projections = data.projection_bounds_with_self_ty(self.tcx(), | |
952 | self.tcx().types.err); | |
953 | for projection in &projections { | |
954 | self.add_constraints_from_ty(generics, projection.0.ty, self.invariant); | |
955 | } | |
1a4d82fc JJ |
956 | } |
957 | ||
958 | ty::ty_param(ref data) => { | |
c34b1796 | 959 | let def_id = generics.types.get(data.space, data.idx as usize).def_id; |
1a4d82fc JJ |
960 | assert_eq!(def_id.krate, ast::LOCAL_CRATE); |
961 | match self.terms_cx.inferred_map.get(&def_id.node) { | |
962 | Some(&index) => { | |
963 | self.add_constraint(index, variance); | |
964 | } | |
965 | None => { | |
966 | // We do not infer variance for type parameters | |
967 | // declared on methods. They will not be present | |
968 | // in the inferred_map. | |
969 | } | |
970 | } | |
971 | } | |
972 | ||
973 | ty::ty_bare_fn(_, &ty::BareFnTy { ref sig, .. }) => { | |
974 | self.add_constraints_from_sig(generics, sig, variance); | |
975 | } | |
976 | ||
85aaf69f SL |
977 | ty::ty_err => { |
978 | // we encounter this when walking the trait references for object | |
979 | // types, where we use ty_err as the Self type | |
980 | } | |
981 | ||
982 | ty::ty_infer(..) => { | |
1a4d82fc JJ |
983 | self.tcx().sess.bug( |
984 | &format!("unexpected type encountered in \ | |
985 | variance inference: {}", | |
c34b1796 | 986 | ty.repr(self.tcx()))); |
1a4d82fc JJ |
987 | } |
988 | } | |
989 | } | |
990 | ||
991 | ||
992 | /// Adds constraints appropriate for a nominal type (enum, struct, | |
993 | /// object, etc) appearing in a context with ambient variance `variance` | |
994 | fn add_constraints_from_substs(&mut self, | |
995 | generics: &ty::Generics<'tcx>, | |
996 | def_id: ast::DefId, | |
997 | type_param_defs: &[ty::TypeParameterDef<'tcx>], | |
998 | region_param_defs: &[ty::RegionParameterDef], | |
999 | substs: &subst::Substs<'tcx>, | |
1000 | variance: VarianceTermPtr<'a>) { | |
85aaf69f SL |
1001 | debug!("add_constraints_from_substs(def_id={}, substs={}, variance={:?})", |
1002 | def_id.repr(self.tcx()), | |
1003 | substs.repr(self.tcx()), | |
1004 | variance); | |
1a4d82fc | 1005 | |
85aaf69f | 1006 | for p in type_param_defs { |
1a4d82fc JJ |
1007 | let variance_decl = |
1008 | self.declared_variance(p.def_id, def_id, TypeParam, | |
c34b1796 | 1009 | p.space, p.index as usize); |
1a4d82fc | 1010 | let variance_i = self.xform(variance, variance_decl); |
c34b1796 | 1011 | let substs_ty = *substs.types.get(p.space, p.index as usize); |
85aaf69f SL |
1012 | debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}", |
1013 | variance_decl, variance_i); | |
1a4d82fc JJ |
1014 | self.add_constraints_from_ty(generics, substs_ty, variance_i); |
1015 | } | |
1016 | ||
85aaf69f | 1017 | for p in region_param_defs { |
1a4d82fc JJ |
1018 | let variance_decl = |
1019 | self.declared_variance(p.def_id, def_id, | |
c34b1796 | 1020 | RegionParam, p.space, p.index as usize); |
1a4d82fc | 1021 | let variance_i = self.xform(variance, variance_decl); |
c34b1796 | 1022 | let substs_r = *substs.regions().get(p.space, p.index as usize); |
1a4d82fc JJ |
1023 | self.add_constraints_from_region(generics, substs_r, variance_i); |
1024 | } | |
1025 | } | |
1026 | ||
1027 | /// Adds constraints appropriate for a function with signature | |
1028 | /// `sig` appearing in a context with ambient variance `variance` | |
1029 | fn add_constraints_from_sig(&mut self, | |
1030 | generics: &ty::Generics<'tcx>, | |
1031 | sig: &ty::PolyFnSig<'tcx>, | |
1032 | variance: VarianceTermPtr<'a>) { | |
1033 | let contra = self.contravariant(variance); | |
85aaf69f | 1034 | for &input in &sig.0.inputs { |
1a4d82fc JJ |
1035 | self.add_constraints_from_ty(generics, input, contra); |
1036 | } | |
1037 | if let ty::FnConverging(result_type) = sig.0.output { | |
1038 | self.add_constraints_from_ty(generics, result_type, variance); | |
1039 | } | |
1040 | } | |
1041 | ||
1042 | /// Adds constraints appropriate for a region appearing in a | |
1043 | /// context with ambient variance `variance` | |
1044 | fn add_constraints_from_region(&mut self, | |
1045 | _generics: &ty::Generics<'tcx>, | |
1046 | region: ty::Region, | |
1047 | variance: VarianceTermPtr<'a>) { | |
1048 | match region { | |
9346a6ac AL |
1049 | ty::ReEarlyBound(ref data) => { |
1050 | if self.is_to_be_inferred(data.param_id) { | |
1051 | let index = self.inferred_index(data.param_id); | |
1a4d82fc JJ |
1052 | self.add_constraint(index, variance); |
1053 | } | |
1054 | } | |
1055 | ||
1056 | ty::ReStatic => { } | |
1057 | ||
1058 | ty::ReLateBound(..) => { | |
1059 | // We do not infer variance for region parameters on | |
1060 | // methods or in fn types. | |
1061 | } | |
1062 | ||
1063 | ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) | | |
1064 | ty::ReEmpty => { | |
1065 | // We don't expect to see anything but 'static or bound | |
1066 | // regions when visiting member types or method types. | |
1067 | self.tcx() | |
1068 | .sess | |
1069 | .bug(&format!("unexpected region encountered in variance \ | |
1070 | inference: {}", | |
c34b1796 | 1071 | region.repr(self.tcx()))); |
1a4d82fc JJ |
1072 | } |
1073 | } | |
1074 | } | |
1075 | ||
1076 | /// Adds constraints appropriate for a mutability-type pair | |
1077 | /// appearing in a context with ambient variance `variance` | |
1078 | fn add_constraints_from_mt(&mut self, | |
1079 | generics: &ty::Generics<'tcx>, | |
1080 | mt: &ty::mt<'tcx>, | |
1081 | variance: VarianceTermPtr<'a>) { | |
1082 | match mt.mutbl { | |
1083 | ast::MutMutable => { | |
1084 | let invar = self.invariant(variance); | |
1085 | self.add_constraints_from_ty(generics, mt.ty, invar); | |
1086 | } | |
1087 | ||
1088 | ast::MutImmutable => { | |
1089 | self.add_constraints_from_ty(generics, mt.ty, variance); | |
1090 | } | |
1091 | } | |
1092 | } | |
1093 | } | |
1094 | ||
1095 | // Constraint solving | |
1096 | // | |
1097 | // The final phase iterates over the constraints, refining the variance | |
1098 | // for each inferred until a fixed point is reached. This will be the | |
1099 | // optimal solution to the constraints. The final variance for each | |
1100 | // inferred is then written into the `variance_map` in the tcx. | |
1101 | ||
1102 | struct SolveContext<'a, 'tcx: 'a> { | |
1103 | terms_cx: TermsContext<'a, 'tcx>, | |
1104 | constraints: Vec<Constraint<'a>> , | |
1105 | ||
1106 | // Maps from an InferredIndex to the inferred value for that variable. | |
1107 | solutions: Vec<ty::Variance> } | |
1108 | ||
1109 | fn solve_constraints(constraints_cx: ConstraintContext) { | |
1110 | let ConstraintContext { terms_cx, constraints, .. } = constraints_cx; | |
85aaf69f SL |
1111 | |
1112 | let solutions = | |
1113 | terms_cx.inferred_infos.iter() | |
1114 | .map(|ii| ii.initial_variance) | |
1115 | .collect(); | |
1116 | ||
1a4d82fc JJ |
1117 | let mut solutions_cx = SolveContext { |
1118 | terms_cx: terms_cx, | |
1119 | constraints: constraints, | |
1120 | solutions: solutions | |
1121 | }; | |
1122 | solutions_cx.solve(); | |
1123 | solutions_cx.write(); | |
1124 | } | |
1125 | ||
1126 | impl<'a, 'tcx> SolveContext<'a, 'tcx> { | |
1127 | fn solve(&mut self) { | |
1128 | // Propagate constraints until a fixed point is reached. Note | |
1129 | // that the maximum number of iterations is 2C where C is the | |
1130 | // number of constraints (each variable can change values at most | |
1131 | // twice). Since number of constraints is linear in size of the | |
1132 | // input, so is the inference process. | |
1133 | let mut changed = true; | |
1134 | while changed { | |
1135 | changed = false; | |
1136 | ||
85aaf69f | 1137 | for constraint in &self.constraints { |
1a4d82fc JJ |
1138 | let Constraint { inferred, variance: term } = *constraint; |
1139 | let InferredIndex(inferred) = inferred; | |
1140 | let variance = self.evaluate(term); | |
1141 | let old_value = self.solutions[inferred]; | |
1142 | let new_value = glb(variance, old_value); | |
1143 | if old_value != new_value { | |
1144 | debug!("Updating inferred {} (node {}) \ | |
1145 | from {:?} to {:?} due to {:?}", | |
1146 | inferred, | |
1147 | self.terms_cx | |
1148 | .inferred_infos[inferred] | |
1149 | .param_id, | |
1150 | old_value, | |
1151 | new_value, | |
1152 | term); | |
1153 | ||
1154 | self.solutions[inferred] = new_value; | |
1155 | changed = true; | |
1156 | } | |
1157 | } | |
1158 | } | |
1159 | } | |
1160 | ||
1161 | fn write(&self) { | |
1162 | // Collect all the variances for a particular item and stick | |
1163 | // them into the variance map. We rely on the fact that we | |
1164 | // generate all the inferreds for a particular item | |
1165 | // consecutively (that is, we collect solutions for an item | |
1166 | // until we see a new item id, and we assume (1) the solutions | |
1167 | // are in the same order as the type parameters were declared | |
1168 | // and (2) all solutions or a given item appear before a new | |
1169 | // item id). | |
1170 | ||
1171 | let tcx = self.terms_cx.tcx; | |
1172 | let solutions = &self.solutions; | |
1173 | let inferred_infos = &self.terms_cx.inferred_infos; | |
1174 | let mut index = 0; | |
1175 | let num_inferred = self.terms_cx.num_inferred(); | |
1176 | while index < num_inferred { | |
1177 | let item_id = inferred_infos[index].item_id; | |
1178 | let mut types = VecPerParamSpace::empty(); | |
1179 | let mut regions = VecPerParamSpace::empty(); | |
1180 | ||
85aaf69f | 1181 | while index < num_inferred && inferred_infos[index].item_id == item_id { |
1a4d82fc JJ |
1182 | let info = &inferred_infos[index]; |
1183 | let variance = solutions[index]; | |
1184 | debug!("Index {} Info {} / {:?} / {:?} Variance {:?}", | |
1185 | index, info.index, info.kind, info.space, variance); | |
1186 | match info.kind { | |
85aaf69f SL |
1187 | TypeParam => { types.push(info.space, variance); } |
1188 | RegionParam => { regions.push(info.space, variance); } | |
1a4d82fc | 1189 | } |
85aaf69f | 1190 | |
1a4d82fc JJ |
1191 | index += 1; |
1192 | } | |
1193 | ||
1194 | let item_variances = ty::ItemVariances { | |
1195 | types: types, | |
1196 | regions: regions | |
1197 | }; | |
1198 | debug!("item_id={} item_variances={}", | |
1199 | item_id, | |
1200 | item_variances.repr(tcx)); | |
1201 | ||
1202 | let item_def_id = ast_util::local_def(item_id); | |
1203 | ||
1204 | // For unit testing: check for a special "rustc_variance" | |
1205 | // attribute and report an error with various results if found. | |
1206 | if ty::has_attr(tcx, item_def_id, "rustc_variance") { | |
1207 | let found = item_variances.repr(tcx); | |
85aaf69f | 1208 | span_err!(tcx.sess, tcx.map.span(item_id), E0208, "{}", &found[..]); |
1a4d82fc JJ |
1209 | } |
1210 | ||
1211 | let newly_added = tcx.item_variance_map.borrow_mut() | |
1212 | .insert(item_def_id, Rc::new(item_variances)).is_none(); | |
1213 | assert!(newly_added); | |
1214 | } | |
1215 | } | |
1216 | ||
1217 | fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance { | |
1218 | match *term { | |
1219 | ConstantTerm(v) => { | |
1220 | v | |
1221 | } | |
1222 | ||
1223 | TransformTerm(t1, t2) => { | |
1224 | let v1 = self.evaluate(t1); | |
1225 | let v2 = self.evaluate(t2); | |
1226 | v1.xform(v2) | |
1227 | } | |
1228 | ||
1229 | InferredTerm(InferredIndex(index)) => { | |
1230 | self.solutions[index] | |
1231 | } | |
1232 | } | |
1233 | } | |
1234 | } | |
1235 | ||
1236 | // Miscellany transformations on variance | |
1237 | ||
1238 | trait Xform { | |
1239 | fn xform(self, v: Self) -> Self; | |
1240 | } | |
1241 | ||
1242 | impl Xform for ty::Variance { | |
1243 | fn xform(self, v: ty::Variance) -> ty::Variance { | |
1244 | // "Variance transformation", Figure 1 of The Paper | |
1245 | match (self, v) { | |
1246 | // Figure 1, column 1. | |
1247 | (ty::Covariant, ty::Covariant) => ty::Covariant, | |
1248 | (ty::Covariant, ty::Contravariant) => ty::Contravariant, | |
1249 | (ty::Covariant, ty::Invariant) => ty::Invariant, | |
1250 | (ty::Covariant, ty::Bivariant) => ty::Bivariant, | |
1251 | ||
1252 | // Figure 1, column 2. | |
1253 | (ty::Contravariant, ty::Covariant) => ty::Contravariant, | |
1254 | (ty::Contravariant, ty::Contravariant) => ty::Covariant, | |
1255 | (ty::Contravariant, ty::Invariant) => ty::Invariant, | |
1256 | (ty::Contravariant, ty::Bivariant) => ty::Bivariant, | |
1257 | ||
1258 | // Figure 1, column 3. | |
1259 | (ty::Invariant, _) => ty::Invariant, | |
1260 | ||
1261 | // Figure 1, column 4. | |
1262 | (ty::Bivariant, _) => ty::Bivariant, | |
1263 | } | |
1264 | } | |
1265 | } | |
1266 | ||
1267 | fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance { | |
1268 | // Greatest lower bound of the variance lattice as | |
1269 | // defined in The Paper: | |
1270 | // | |
1271 | // * | |
1272 | // - + | |
1273 | // o | |
1274 | match (v1, v2) { | |
1275 | (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant, | |
1276 | ||
1277 | (ty::Covariant, ty::Contravariant) => ty::Invariant, | |
1278 | (ty::Contravariant, ty::Covariant) => ty::Invariant, | |
1279 | ||
1280 | (ty::Covariant, ty::Covariant) => ty::Covariant, | |
1281 | ||
1282 | (ty::Contravariant, ty::Contravariant) => ty::Contravariant, | |
1283 | ||
1284 | (x, ty::Bivariant) | (ty::Bivariant, x) => x, | |
1285 | } | |
1286 | } |