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.
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.
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.
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
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`
26 //! (resp. `'a` and `'b`).
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
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.
47 //! As a simple example, consider:
49 //! enum Option<A> { Some(A), None }
50 //! enum OptionalFn<B> { Some(|B|), None }
51 //! enum OptionalMap<C> { Some(|C| -> C), None }
53 //! Here, we will generate the constraints:
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:
67 //! o Bottom (invariant)
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.
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
79 //! Term := + | - | * | o | V(X) | Term x Term
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:
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)`.
92 //! If I have a struct or enum with where clauses:
94 //! struct Foo<T:Bar> { ... }
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.
106 //! ### Addendum: Variance on traits
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.
122 //! Just for historical reference,I am going to preserve some text indicating
123 //! how one could interpret variance and trait matching.
125 //! #### Variance and object types
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
132 //! function that is expected the appropriate `Self` type. However, we
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
137 //! To see what I mean, consider a trait like so:
139 //! trait ConvertTo<A> {
140 //! fn convertTo(&self) -> A;
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`.
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.)
163 //! #### Trait variance and vtable resolution
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:
169 //! fn convertAll<A,T:ConvertTo<A>>(v: &[T]) {
173 //! Now imagine that I have an implementation of `ConvertTo` for `Object`:
175 //! impl ConvertTo<int> for Object { ... }
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`:
181 //! let mut vector = vec!["string", ...];
182 //! convertAll::<int, String>(vector);
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:
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:
193 //! fn(self: &Object) -> int
195 //! It is ok to provide a value for `self` of type `&String` because
196 //! `&String <: &Object`.
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?"
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:
207 //! V_O = ConvertTo<int> for Object
209 //! and the function prototype expects an impl of type:
211 //! V_S = ConvertTo<int> for String
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:
223 //! These conditions are satisfied and so we are happy.
225 //! #### Variance and associated types
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:
232 //! <T as Trait> <: <U as Trait>
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.
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.
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:
249 //! trait Identity { type Out; fn foo(&self); }
250 //! impl<T> Identity for T { type Out = T; ... }
253 //! Now if I have `<&'static () as Identity>::Out`, this can be
254 //! validly derived as `&'a ()` for any `'a`:
256 //! <&'a () as Identity> <: <&'static () as Identity>
257 //! if &'static () < : &'a () -- Identity is contravariant in Self
258 //! if 'static : 'a -- Subtyping rules for relations
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.
264 use self::VarianceTerm::*;
265 use self::ParamKind::*;
268 use arena::TypedArena;
269 use middle::def_id::DefId;
270 use middle::resolve_lifetime as rl;
272 use middle::subst::{ParamSpace, FnSpace, TypeSpace, SelfSpace, VecPerParamSpace};
273 use middle::ty::{self, Ty};
274 use rustc::front::map as hir_map;
278 use rustc_front::hir;
279 use rustc_front::visit;
280 use rustc_front::visit::Visitor;
281 use util::nodemap::NodeMap;
283 pub fn infer_variance(tcx: &ty::ctxt) {
284 let krate = tcx.map.krate();
285 let mut arena = arena::TypedArena::new();
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);
292 // Representing terms
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).
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
303 type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
305 #[derive(Copy, Clone, Debug)]
306 struct InferredIndex(usize);
308 #[derive(Copy, Clone)]
309 enum VarianceTerm<'a> {
310 ConstantTerm(ty::Variance),
311 TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
312 InferredTerm(InferredIndex),
315 impl<'a> fmt::Debug for VarianceTerm<'a> {
316 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
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 })
325 // The first pass over the crate simply builds up the set of inferreds.
327 struct TermsContext<'a, 'tcx: 'a> {
328 tcx: &'a ty::ctxt<'tcx>,
329 arena: &'a TypedArena<VarianceTerm<'a>>,
331 empty_variances: Rc<ty::ItemVariances>,
333 // For marker types, UnsafeCell, and other lang items where
334 // variance is hardcoded, records the item-id and the hardcoded
336 lang_items: Vec<(ast::NodeId, Vec<ty::Variance>)>,
338 // Maps from the node id of a type/generic parameter to the
339 // corresponding inferred index.
340 inferred_map: NodeMap<InferredIndex>,
342 // Maps from an InferredIndex to the info for that variable.
343 inferred_infos: Vec<InferredInfo<'a>> ,
346 #[derive(Copy, Clone, Debug, PartialEq)]
352 struct InferredInfo<'a> {
353 item_id: ast::NodeId,
357 param_id: ast::NodeId,
358 term: VarianceTermPtr<'a>,
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,
366 fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
367 arena: &'a mut TypedArena<VarianceTerm<'a>>,
369 -> TermsContext<'a, 'tcx> {
370 let mut terms_cx = TermsContext {
373 inferred_map: NodeMap(),
374 inferred_infos: Vec::new(),
376 lang_items: lang_items(tcx),
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()
386 visit::walk_crate(&mut terms_cx, krate);
391 fn lang_items(tcx: &ty::ctxt) -> Vec<(ast::NodeId,Vec<ty::Variance>)> {
393 (tcx.lang_items.phantom_data(), vec![ty::Covariant]),
394 (tcx.lang_items.unsafe_cell_type(), vec![ty::Invariant]),
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]),
406 all.into_iter() // iterating over (Option<DefId>, Variance)
407 .filter(|&(ref d,_)| d.is_some())
408 .map(|(d, v)| (d.unwrap(), v)) // (DefId, Variance)
409 .filter_map(|(d, v)| tcx.map.as_local_node_id(d).map(|n| (n, v))) // (NodeId, Variance)
413 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
414 fn add_inferreds_for_item(&mut self,
415 item_id: ast::NodeId,
417 generics: &hir::Generics)
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.
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.
431 let inferreds_on_entry = self.num_inferred();
434 self.add_inferred(item_id, TypeParam, SelfSpace, 0, item_id);
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);
442 for (i, p) in generics.ty_params.iter().enumerate() {
443 self.add_inferred(item_id, TypeParam, TypeSpace, i, p.id);
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
453 if self.num_inferred() == inferreds_on_entry {
454 let item_def_id = self.tcx.map.local_def_id(item_id);
456 self.tcx.item_variance_map.borrow_mut().insert(
458 self.empty_variances.clone()).is_none();
459 assert!(newly_added);
463 fn add_inferred(&mut self,
464 item_id: ast::NodeId,
468 param_id: ast::NodeId) {
469 let inf_index = InferredIndex(self.inferred_infos.len());
470 let term = self.arena.alloc(InferredTerm(inf_index));
471 let initial_variance = self.pick_initial_variance(item_id, space, index);
472 self.inferred_infos.push(InferredInfo { item_id: item_id,
478 initial_variance: initial_variance });
479 let newly_added = self.inferred_map.insert(param_id, inf_index).is_none();
480 assert!(newly_added);
482 debug!("add_inferred(item_path={}, \
489 initial_variance={:?})",
490 self.tcx.item_path_str(self.tcx.map.local_def_id(item_id)),
491 item_id, kind, space, index, param_id, inf_index,
495 fn pick_initial_variance(&self,
496 item_id: ast::NodeId,
502 SelfSpace | FnSpace => {
507 match self.lang_items.iter().find(|&&(n, _)| n == item_id) {
508 Some(&(_, ref variances)) => variances[index],
509 None => ty::Bivariant
515 fn num_inferred(&self) -> usize {
516 self.inferred_infos.len()
520 impl<'a, 'tcx, 'v> Visitor<'v> for TermsContext<'a, 'tcx> {
521 fn visit_item(&mut self, item: &hir::Item) {
522 debug!("add_inferreds for item {}", self.tcx.map.node_to_string(item.id));
525 hir::ItemEnum(_, ref generics) |
526 hir::ItemStruct(_, ref generics) => {
527 self.add_inferreds_for_item(item.id, false, generics);
529 hir::ItemTrait(_, ref generics, _, _) => {
530 // Note: all inputs for traits are ultimately
531 // constrained to be invariant. See `visit_item` in
532 // the impl for `ConstraintContext` below.
533 self.add_inferreds_for_item(item.id, true, generics);
534 visit::walk_item(self, item);
537 hir::ItemExternCrate(_) |
539 hir::ItemDefaultImpl(..) |
541 hir::ItemStatic(..) |
545 hir::ItemForeignMod(..) |
547 visit::walk_item(self, item);
553 // Constraint construction and representation
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.
558 struct ConstraintContext<'a, 'tcx: 'a> {
559 terms_cx: TermsContext<'a, 'tcx>,
561 // These are pointers to common `ConstantTerm` instances
562 covariant: VarianceTermPtr<'a>,
563 contravariant: VarianceTermPtr<'a>,
564 invariant: VarianceTermPtr<'a>,
565 bivariant: VarianceTermPtr<'a>,
567 constraints: Vec<Constraint<'a>> ,
570 /// Declares that the variable `decl_id` appears in a location with
571 /// variance `variance`.
572 #[derive(Copy, Clone)]
573 struct Constraint<'a> {
574 inferred: InferredIndex,
575 variance: &'a VarianceTerm<'a>,
578 fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>,
580 -> ConstraintContext<'a, 'tcx>
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));
586 let mut constraint_cx = ConstraintContext {
588 covariant: covariant,
589 contravariant: contravariant,
590 invariant: invariant,
591 bivariant: bivariant,
592 constraints: Vec::new(),
594 visit::walk_crate(&mut constraint_cx, krate);
598 impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> {
599 fn visit_item(&mut self, item: &hir::Item) {
600 let tcx = self.terms_cx.tcx;
601 let did = tcx.map.local_def_id(item.id);
603 debug!("visit_item item={}", tcx.map.node_to_string(item.id));
606 hir::ItemEnum(..) | hir::ItemStruct(..) => {
607 let scheme = tcx.lookup_item_type(did);
609 // Not entirely obvious: constraints on structs/enums do not
610 // affect the variance of their type parameters. See discussion
611 // in comment at top of module.
613 // self.add_constraints_from_generics(&scheme.generics);
615 for field in tcx.lookup_adt_def(did).all_fields() {
616 self.add_constraints_from_ty(&scheme.generics,
621 hir::ItemTrait(..) => {
622 let trait_def = tcx.lookup_trait_def(did);
623 self.add_constraints_from_trait_ref(&trait_def.generics,
628 hir::ItemExternCrate(_) |
630 hir::ItemStatic(..) |
634 hir::ItemForeignMod(..) |
637 hir::ItemDefaultImpl(..) => {
641 visit::walk_item(self, item);
645 /// Is `param_id` a lifetime according to `map`?
646 fn is_lifetime(map: &hir_map::Map, param_id: ast::NodeId) -> bool {
647 match map.find(param_id) {
648 Some(hir_map::NodeLifetime(..)) => true, _ => false
652 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
653 fn tcx(&self) -> &'a ty::ctxt<'tcx> {
657 fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
658 match self.terms_cx.inferred_map.get(¶m_id) {
659 Some(&index) => index,
661 self.tcx().sess.bug(&format!(
662 "no inferred index entry for {}",
663 self.tcx().map.node_to_string(param_id)));
668 fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
669 let tcx = self.terms_cx.tcx;
670 assert!(is_lifetime(&tcx.map, param_id));
671 match tcx.named_region_map.get(¶m_id) {
672 Some(&rl::DefEarlyBoundRegion(_, _, lifetime_decl_id))
674 Some(_) => panic!("should not encounter non early-bound cases"),
676 // The lookup should only fail when `param_id` is
677 // itself a lifetime binding: use it as the decl_id.
683 /// Is `param_id` a type parameter for which we infer variance?
684 fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
685 let result = self.terms_cx.inferred_map.contains_key(¶m_id);
687 // To safe-guard against invalid inferred_map constructions,
688 // double-check if variance is inferred at some use of a type
689 // parameter (by inspecting parent of its binding declaration
690 // to see if it is introduced by a type or by a fn/impl).
692 let check_result = |this:&ConstraintContext| -> bool {
693 let tcx = this.terms_cx.tcx;
694 let decl_id = this.find_binding_for_lifetime(param_id);
695 // Currently only called on lifetimes; double-checking that.
696 assert!(is_lifetime(&tcx.map, param_id));
697 let parent_id = tcx.map.get_parent(decl_id);
698 let parent = tcx.map.find(parent_id).unwrap_or_else(
699 || panic!("tcx.map missing entry for id: {}", parent_id));
702 macro_rules! cannot_happen { () => { {
703 panic!("invalid parent: {} for {}",
704 tcx.map.node_to_string(parent_id),
705 tcx.map.node_to_string(param_id));
709 hir_map::NodeItem(p) => {
713 hir::ItemStruct(..) |
714 hir::ItemTrait(..) => is_inferred = true,
715 hir::ItemFn(..) => is_inferred = false,
716 _ => cannot_happen!(),
719 hir_map::NodeTraitItem(..) => is_inferred = false,
720 hir_map::NodeImplItem(..) => is_inferred = false,
721 _ => cannot_happen!(),
727 assert_eq!(result, check_result(self));
732 /// Returns a variance term representing the declared variance of the type/region parameter
733 /// with the given id.
734 fn declared_variance(&self,
740 -> VarianceTermPtr<'a> {
741 assert_eq!(param_def_id.krate, item_def_id.krate);
743 if let Some(param_node_id) = self.tcx().map.as_local_node_id(param_def_id) {
744 // Parameter on an item defined within current crate:
745 // variance not yet inferred, so return a symbolic
747 let InferredIndex(index) = self.inferred_index(param_node_id);
748 self.terms_cx.inferred_infos[index].term
750 // Parameter on an item defined within another crate:
751 // variance already inferred, just look it up.
752 let variances = self.tcx().item_variances(item_def_id);
753 let variance = match kind {
754 TypeParam => *variances.types.get(space, index),
755 RegionParam => *variances.regions.get(space, index),
757 self.constant_term(variance)
761 fn add_constraint(&mut self,
762 InferredIndex(index): InferredIndex,
763 variance: VarianceTermPtr<'a>) {
764 debug!("add_constraint(index={}, variance={:?})",
766 self.constraints.push(Constraint { inferred: InferredIndex(index),
767 variance: variance });
770 fn contravariant(&mut self,
771 variance: VarianceTermPtr<'a>)
772 -> VarianceTermPtr<'a> {
773 self.xform(variance, self.contravariant)
776 fn invariant(&mut self,
777 variance: VarianceTermPtr<'a>)
778 -> VarianceTermPtr<'a> {
779 self.xform(variance, self.invariant)
782 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
784 ty::Covariant => self.covariant,
785 ty::Invariant => self.invariant,
786 ty::Contravariant => self.contravariant,
787 ty::Bivariant => self.bivariant,
792 v1: VarianceTermPtr<'a>,
793 v2: VarianceTermPtr<'a>)
794 -> VarianceTermPtr<'a> {
796 (_, ConstantTerm(ty::Covariant)) => {
797 // Applying a "covariant" transform is always a no-op
801 (ConstantTerm(c1), ConstantTerm(c2)) => {
802 self.constant_term(c1.xform(c2))
806 &*self.terms_cx.arena.alloc(TransformTerm(v1, v2))
811 fn add_constraints_from_trait_ref(&mut self,
812 generics: &ty::Generics<'tcx>,
813 trait_ref: ty::TraitRef<'tcx>,
814 variance: VarianceTermPtr<'a>) {
815 debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}",
819 let trait_def = self.tcx().lookup_trait_def(trait_ref.def_id);
821 self.add_constraints_from_substs(
824 trait_def.generics.types.as_slice(),
825 trait_def.generics.regions.as_slice(),
830 /// Adds constraints appropriate for an instance of `ty` appearing
831 /// in a context with the generics defined in `generics` and
832 /// ambient variance `variance`
833 fn add_constraints_from_ty(&mut self,
834 generics: &ty::Generics<'tcx>,
836 variance: VarianceTermPtr<'a>) {
837 debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
843 ty::TyChar | ty::TyInt(_) | ty::TyUint(_) |
844 ty::TyFloat(_) | ty::TyStr => {
845 /* leaf type -- noop */
848 ty::TyClosure(..) => {
849 self.tcx().sess.bug("Unexpected closure type in variance computation");
852 ty::TyRef(region, ref mt) => {
853 let contra = self.contravariant(variance);
854 self.add_constraints_from_region(generics, *region, contra);
855 self.add_constraints_from_mt(generics, mt, variance);
858 ty::TyBox(typ) | ty::TyArray(typ, _) | ty::TySlice(typ) => {
859 self.add_constraints_from_ty(generics, typ, variance);
863 ty::TyRawPtr(ref mt) => {
864 self.add_constraints_from_mt(generics, mt, variance);
867 ty::TyTuple(ref subtys) => {
868 for &subty in subtys {
869 self.add_constraints_from_ty(generics, subty, variance);
873 ty::TyEnum(def, substs) |
874 ty::TyStruct(def, substs) => {
875 let item_type = self.tcx().lookup_item_type(def.did);
877 // All type parameters on enums and structs should be
879 assert!(item_type.generics.types.is_empty_in(subst::SelfSpace));
880 assert!(item_type.generics.types.is_empty_in(subst::FnSpace));
881 assert!(item_type.generics.regions.is_empty_in(subst::SelfSpace));
882 assert!(item_type.generics.regions.is_empty_in(subst::FnSpace));
884 self.add_constraints_from_substs(
887 item_type.generics.types.get_slice(subst::TypeSpace),
888 item_type.generics.regions.get_slice(subst::TypeSpace),
893 ty::TyProjection(ref data) => {
894 let trait_ref = &data.trait_ref;
895 let trait_def = self.tcx().lookup_trait_def(trait_ref.def_id);
896 self.add_constraints_from_substs(
899 trait_def.generics.types.as_slice(),
900 trait_def.generics.regions.as_slice(),
905 ty::TyTrait(ref data) => {
907 data.principal_trait_ref_with_self_ty(self.tcx(),
908 self.tcx().types.err);
910 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
911 let contra = self.contravariant(variance);
912 self.add_constraints_from_region(generics, data.bounds.region_bound, contra);
914 // Ignore the SelfSpace, it is erased.
915 self.add_constraints_from_trait_ref(generics, poly_trait_ref.0, variance);
917 let projections = data.projection_bounds_with_self_ty(self.tcx(),
918 self.tcx().types.err);
919 for projection in &projections {
920 self.add_constraints_from_ty(generics, projection.0.ty, self.invariant);
924 ty::TyParam(ref data) => {
925 let def_id = generics.types.get(data.space, data.idx as usize).def_id;
926 let node_id = self.tcx().map.as_local_node_id(def_id).unwrap();
927 match self.terms_cx.inferred_map.get(&node_id) {
929 self.add_constraint(index, variance);
932 // We do not infer variance for type parameters
933 // declared on methods. They will not be present
934 // in the inferred_map.
939 ty::TyBareFn(_, &ty::BareFnTy { ref sig, .. }) => {
940 self.add_constraints_from_sig(generics, sig, variance);
944 // we encounter this when walking the trait references for object
945 // types, where we use TyError as the Self type
950 &format!("unexpected type encountered in \
951 variance inference: {}", ty));
957 /// Adds constraints appropriate for a nominal type (enum, struct,
958 /// object, etc) appearing in a context with ambient variance `variance`
959 fn add_constraints_from_substs(&mut self,
960 generics: &ty::Generics<'tcx>,
962 type_param_defs: &[ty::TypeParameterDef<'tcx>],
963 region_param_defs: &[ty::RegionParameterDef],
964 substs: &subst::Substs<'tcx>,
965 variance: VarianceTermPtr<'a>) {
966 debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
971 for p in type_param_defs {
973 self.declared_variance(p.def_id, def_id, TypeParam,
974 p.space, p.index as usize);
975 let variance_i = self.xform(variance, variance_decl);
976 let substs_ty = *substs.types.get(p.space, p.index as usize);
977 debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
978 variance_decl, variance_i);
979 self.add_constraints_from_ty(generics, substs_ty, variance_i);
982 for p in region_param_defs {
984 self.declared_variance(p.def_id, def_id,
985 RegionParam, p.space, p.index as usize);
986 let variance_i = self.xform(variance, variance_decl);
987 let substs_r = *substs.regions().get(p.space, p.index as usize);
988 self.add_constraints_from_region(generics, substs_r, variance_i);
992 /// Adds constraints appropriate for a function with signature
993 /// `sig` appearing in a context with ambient variance `variance`
994 fn add_constraints_from_sig(&mut self,
995 generics: &ty::Generics<'tcx>,
996 sig: &ty::PolyFnSig<'tcx>,
997 variance: VarianceTermPtr<'a>) {
998 let contra = self.contravariant(variance);
999 for &input in &sig.0.inputs {
1000 self.add_constraints_from_ty(generics, input, contra);
1002 if let ty::FnConverging(result_type) = sig.0.output {
1003 self.add_constraints_from_ty(generics, result_type, variance);
1007 /// Adds constraints appropriate for a region appearing in a
1008 /// context with ambient variance `variance`
1009 fn add_constraints_from_region(&mut self,
1010 _generics: &ty::Generics<'tcx>,
1012 variance: VarianceTermPtr<'a>) {
1014 ty::ReEarlyBound(ref data) => {
1015 let node_id = self.tcx().map.as_local_node_id(data.def_id).unwrap();
1016 if self.is_to_be_inferred(node_id) {
1017 let index = self.inferred_index(node_id);
1018 self.add_constraint(index, variance);
1024 ty::ReLateBound(..) => {
1025 // We do not infer variance for region parameters on
1026 // methods or in fn types.
1029 ty::ReFree(..) | ty::ReScope(..) | ty::ReVar(..) |
1030 ty::ReSkolemized(..) | ty::ReEmpty => {
1031 // We don't expect to see anything but 'static or bound
1032 // regions when visiting member types or method types.
1035 .bug(&format!("unexpected region encountered in variance \
1042 /// Adds constraints appropriate for a mutability-type pair
1043 /// appearing in a context with ambient variance `variance`
1044 fn add_constraints_from_mt(&mut self,
1045 generics: &ty::Generics<'tcx>,
1046 mt: &ty::TypeAndMut<'tcx>,
1047 variance: VarianceTermPtr<'a>) {
1049 hir::MutMutable => {
1050 let invar = self.invariant(variance);
1051 self.add_constraints_from_ty(generics, mt.ty, invar);
1054 hir::MutImmutable => {
1055 self.add_constraints_from_ty(generics, mt.ty, variance);
1061 // Constraint solving
1063 // The final phase iterates over the constraints, refining the variance
1064 // for each inferred until a fixed point is reached. This will be the
1065 // optimal solution to the constraints. The final variance for each
1066 // inferred is then written into the `variance_map` in the tcx.
1068 struct SolveContext<'a, 'tcx: 'a> {
1069 terms_cx: TermsContext<'a, 'tcx>,
1070 constraints: Vec<Constraint<'a>> ,
1072 // Maps from an InferredIndex to the inferred value for that variable.
1073 solutions: Vec<ty::Variance> }
1075 fn solve_constraints(constraints_cx: ConstraintContext) {
1076 let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
1079 terms_cx.inferred_infos.iter()
1080 .map(|ii| ii.initial_variance)
1083 let mut solutions_cx = SolveContext {
1085 constraints: constraints,
1086 solutions: solutions
1088 solutions_cx.solve();
1089 solutions_cx.write();
1092 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
1093 fn solve(&mut self) {
1094 // Propagate constraints until a fixed point is reached. Note
1095 // that the maximum number of iterations is 2C where C is the
1096 // number of constraints (each variable can change values at most
1097 // twice). Since number of constraints is linear in size of the
1098 // input, so is the inference process.
1099 let mut changed = true;
1103 for constraint in &self.constraints {
1104 let Constraint { inferred, variance: term } = *constraint;
1105 let InferredIndex(inferred) = inferred;
1106 let variance = self.evaluate(term);
1107 let old_value = self.solutions[inferred];
1108 let new_value = glb(variance, old_value);
1109 if old_value != new_value {
1110 debug!("Updating inferred {} (node {}) \
1111 from {:?} to {:?} due to {:?}",
1114 .inferred_infos[inferred]
1120 self.solutions[inferred] = new_value;
1128 // Collect all the variances for a particular item and stick
1129 // them into the variance map. We rely on the fact that we
1130 // generate all the inferreds for a particular item
1131 // consecutively (that is, we collect solutions for an item
1132 // until we see a new item id, and we assume (1) the solutions
1133 // are in the same order as the type parameters were declared
1134 // and (2) all solutions or a given item appear before a new
1137 let tcx = self.terms_cx.tcx;
1138 let solutions = &self.solutions;
1139 let inferred_infos = &self.terms_cx.inferred_infos;
1141 let num_inferred = self.terms_cx.num_inferred();
1142 while index < num_inferred {
1143 let item_id = inferred_infos[index].item_id;
1144 let mut types = VecPerParamSpace::empty();
1145 let mut regions = VecPerParamSpace::empty();
1147 while index < num_inferred && inferred_infos[index].item_id == item_id {
1148 let info = &inferred_infos[index];
1149 let variance = solutions[index];
1150 debug!("Index {} Info {} / {:?} / {:?} Variance {:?}",
1151 index, info.index, info.kind, info.space, variance);
1153 TypeParam => { types.push(info.space, variance); }
1154 RegionParam => { regions.push(info.space, variance); }
1160 let item_variances = ty::ItemVariances {
1164 debug!("item_id={} item_variances={:?}",
1168 let item_def_id = tcx.map.local_def_id(item_id);
1170 // For unit testing: check for a special "rustc_variance"
1171 // attribute and report an error with various results if found.
1172 if tcx.has_attr(item_def_id, "rustc_variance") {
1173 span_err!(tcx.sess, tcx.map.span(item_id), E0208, "{:?}", item_variances);
1176 let newly_added = tcx.item_variance_map.borrow_mut()
1177 .insert(item_def_id, Rc::new(item_variances)).is_none();
1178 assert!(newly_added);
1182 fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
1184 ConstantTerm(v) => {
1188 TransformTerm(t1, t2) => {
1189 let v1 = self.evaluate(t1);
1190 let v2 = self.evaluate(t2);
1194 InferredTerm(InferredIndex(index)) => {
1195 self.solutions[index]
1201 // Miscellany transformations on variance
1204 fn xform(self, v: Self) -> Self;
1207 impl Xform for ty::Variance {
1208 fn xform(self, v: ty::Variance) -> ty::Variance {
1209 // "Variance transformation", Figure 1 of The Paper
1211 // Figure 1, column 1.
1212 (ty::Covariant, ty::Covariant) => ty::Covariant,
1213 (ty::Covariant, ty::Contravariant) => ty::Contravariant,
1214 (ty::Covariant, ty::Invariant) => ty::Invariant,
1215 (ty::Covariant, ty::Bivariant) => ty::Bivariant,
1217 // Figure 1, column 2.
1218 (ty::Contravariant, ty::Covariant) => ty::Contravariant,
1219 (ty::Contravariant, ty::Contravariant) => ty::Covariant,
1220 (ty::Contravariant, ty::Invariant) => ty::Invariant,
1221 (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
1223 // Figure 1, column 3.
1224 (ty::Invariant, _) => ty::Invariant,
1226 // Figure 1, column 4.
1227 (ty::Bivariant, _) => ty::Bivariant,
1232 fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance {
1233 // Greatest lower bound of the variance lattice as
1234 // defined in The Paper:
1240 (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
1242 (ty::Covariant, ty::Contravariant) => ty::Invariant,
1243 (ty::Contravariant, ty::Covariant) => ty::Invariant,
1245 (ty::Covariant, ty::Covariant) => ty::Covariant,
1247 (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
1249 (x, ty::Bivariant) | (ty::Bivariant, x) => x,