1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
13 This file infers the variance of type and lifetime parameters. The
14 algorithm is taken from Section 4 of the paper "Taming the Wildcards:
15 Combining Definition- and Use-Site Variance" published in PLDI'11 and
16 written by Altidor et al., and hereafter referred to as The Paper.
18 This inference is explicitly designed *not* to consider the uses of
19 types within code. To determine the variance of type parameters
20 defined on type `X`, we only consider the definition of the type `X`
21 and the definitions of any types it references.
23 We only infer variance for type parameters found on *types*: structs,
24 enums, and traits. We do not infer variance for type parameters found
25 on fns or impls. This is because those things are not type definitions
26 and variance doesn't really make sense in that context.
28 It is worth covering what variance means in each case. For structs and
29 enums, I think it is fairly straightforward. The variance of the type
30 or lifetime parameters defines whether `T<A>` is a subtype of `T<B>`
31 (resp. `T<'a>` and `T<'b>`) based on the relationship of `A` and `B`
32 (resp. `'a` and `'b`). (FIXME #3598 -- we do not currently make use of
33 the variances we compute for type parameters.)
35 ### Variance on traits
37 The meaning of variance for trait parameters is more subtle and worth
38 expanding upon. There are in fact two uses of the variance values we
41 #### Trait variance and object types
43 The first is for object types. Just as with structs and enums, we can
44 decide the subtyping relationship between two object types `&Trait<A>`
45 and `&Trait<B>` based on the relationship of `A` and `B`. Note that
46 for object types we ignore the `Self` type parameter -- it is unknown,
47 and the nature of dynamic dispatch ensures that we will always call a
48 function that is expected the appropriate `Self` type. However, we
49 must be careful with the other type parameters, or else we could end
50 up calling a function that is expecting one type but provided another.
52 To see what I mean, consider a trait like so:
55 fn convertTo(&self) -> A;
58 Intuitively, If we had one object `O=&ConvertTo<Object>` and another
59 `S=&ConvertTo<String>`, then `S <: O` because `String <: Object`
60 (presuming Java-like "string" and "object" types, my go to examples
61 for subtyping). The actual algorithm would be to compare the
62 (explicit) type parameters pairwise respecting their variance: here,
63 the type parameter A is covariant (it appears only in a return
64 position), and hence we require that `String <: Object`.
66 You'll note though that we did not consider the binding for the
67 (implicit) `Self` type parameter: in fact, it is unknown, so that's
68 good. The reason we can ignore that parameter is precisely because we
69 don't need to know its value until a call occurs, and at that time (as
70 you said) the dynamic nature of virtual dispatch means the code we run
71 will be correct for whatever value `Self` happens to be bound to for
72 the particular object whose method we called. `Self` is thus different
73 from `A`, because the caller requires that `A` be known in order to
74 know the return type of the method `convertTo()`. (As an aside, we
75 have rules preventing methods where `Self` appears outside of the
76 receiver position from being called via an object.)
78 #### Trait variance and vtable resolution
80 But traits aren't only used with objects. They're also used when
81 deciding whether a given impl satisfies a given trait bound. To set the
82 scene here, imagine I had a function:
84 fn convertAll<A,T:ConvertTo<A>>(v: &[T]) {
88 Now imagine that I have an implementation of `ConvertTo` for `Object`:
90 impl ConvertTo<int> for Object { ... }
92 And I want to call `convertAll` on an array of strings. Suppose
93 further that for whatever reason I specifically supply the value of
94 `String` for the type parameter `T`:
96 let mut vector = ~["string", ...];
97 convertAll::<int, String>(v);
99 Is this legal? To put another way, can we apply the `impl` for
100 `Object` to the type `String`? The answer is yes, but to see why
101 we have to expand out what will happen:
103 - `convertAll` will create a pointer to one of the entries in the
104 vector, which will have type `&String`
105 - It will then call the impl of `convertTo()` that is intended
106 for use with objects. This has the type:
108 fn(self: &Object) -> int
110 It is ok to provide a value for `self` of type `&String` because
111 `&String <: &Object`.
113 OK, so intuitively we want this to be legal, so let's bring this back
114 to variance and see whether we are computing the correct result. We
115 must first figure out how to phrase the question "is an impl for
116 `Object,int` usable where an impl for `String,int` is expected?"
118 Maybe it's helpful to think of a dictionary-passing implementation of
119 type classes. In that case, `convertAll()` takes an implicit parameter
120 representing the impl. In short, we *have* an impl of type:
122 V_O = ConvertTo<int> for Object
124 and the function prototype expects an impl of type:
126 V_S = ConvertTo<int> for String
128 As with any argument, this is legal if the type of the value given
129 (`V_O`) is a subtype of the type expected (`V_S`). So is `V_O <: V_S`?
130 The answer will depend on the variance of the various parameters. In
131 this case, because the `Self` parameter is contravariant and `A` is
132 covariant, it means that:
138 These conditions are satisfied and so we are happy.
142 The basic idea is quite straightforward. We iterate over the types
143 defined and, for each use of a type parameter X, accumulate a
144 constraint indicating that the variance of X must be valid for the
145 variance of that use site. We then iteratively refine the variance of
146 X until all constraints are met. There is *always* a sol'n, because at
147 the limit we can declare all type parameters to be invariant and all
148 constraints will be satisfied.
150 As a simple example, consider:
152 enum Option<A> { Some(A), None }
153 enum OptionalFn<B> { Some(|B|), None }
154 enum OptionalMap<C> { Some(|C| -> C), None }
156 Here, we will generate the constraints:
163 These indicate that (1) the variance of A must be at most covariant;
164 (2) the variance of B must be at most contravariant; and (3, 4) the
165 variance of C must be at most covariant *and* contravariant. All of these
166 results are based on a variance lattice defined as follows:
172 Based on this lattice, the solution V(A)=+, V(B)=-, V(C)=o is the
173 optimal solution. Note that there is always a naive solution which
174 just declares all variables to be invariant.
176 You may be wondering why fixed-point iteration is required. The reason
177 is that the variance of a use site may itself be a function of the
178 variance of other type parameters. In full generality, our constraints
182 Term := + | - | * | o | V(X) | Term x Term
184 Here the notation V(X) indicates the variance of a type/region
185 parameter `X` with respect to its defining class. `Term x Term`
186 represents the "variance transform" as defined in the paper:
188 If the variance of a type variable `X` in type expression `E` is `V2`
189 and the definition-site variance of the [corresponding] type parameter
190 of a class `C` is `V1`, then the variance of `X` in the type expression
191 `C<E>` is `V3 = V1.xform(V2)`.
194 use self::VarianceTerm::*;
195 use self::ParamKind::*;
199 use middle::resolve_lifetime as rl;
201 use middle::subst::{ParamSpace, FnSpace, TypeSpace, SelfSpace, VecPerParamSpace};
202 use middle::ty::{mod, Ty};
207 use syntax::ast_util;
209 use syntax::visit::Visitor;
210 use util::nodemap::NodeMap;
211 use util::ppaux::Repr;
213 pub fn infer_variance(tcx: &ty::ctxt) {
214 let krate = tcx.map.krate();
215 let mut arena = arena::Arena::new();
216 let terms_cx = determine_parameters_to_be_inferred(tcx, &mut arena, krate);
217 let constraints_cx = add_constraints_from_crate(terms_cx, krate);
218 solve_constraints(constraints_cx);
219 tcx.variance_computed.set(true);
222 /**************************************************************************
225 * Terms are structured as a straightforward tree. Rather than rely on
226 * GC, we allocate terms out of a bounded arena (the lifetime of this
227 * arena is the lifetime 'a that is threaded around).
229 * We assign a unique index to each type/region parameter whose variance
230 * is to be inferred. We refer to such variables as "inferreds". An
231 * `InferredIndex` is a newtype'd int representing the index of such
235 type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
238 struct InferredIndex(uint);
240 enum VarianceTerm<'a> {
241 ConstantTerm(ty::Variance),
242 TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
243 InferredTerm(InferredIndex),
246 impl<'a> fmt::Show for VarianceTerm<'a> {
247 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
249 ConstantTerm(c1) => write!(f, "{}", c1),
250 TransformTerm(v1, v2) => write!(f, "({} \u00D7 {})", v1, v2),
251 InferredTerm(id) => write!(f, "[{}]", { let InferredIndex(i) = id; i })
256 /**************************************************************************
257 * The first pass over the crate simply builds up the set of inferreds.
260 struct TermsContext<'a, 'tcx: 'a> {
261 tcx: &'a ty::ctxt<'tcx>,
264 empty_variances: Rc<ty::ItemVariances>,
266 // Maps from the node id of a type/generic parameter to the
267 // corresponding inferred index.
268 inferred_map: NodeMap<InferredIndex>,
270 // Maps from an InferredIndex to the info for that variable.
271 inferred_infos: Vec<InferredInfo<'a>> ,
274 #[deriving(Show, PartialEq)]
280 struct InferredInfo<'a> {
281 item_id: ast::NodeId,
285 param_id: ast::NodeId,
286 term: VarianceTermPtr<'a>,
289 fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
290 arena: &'a mut Arena,
292 -> TermsContext<'a, 'tcx> {
293 let mut terms_cx = TermsContext {
296 inferred_map: NodeMap::new(),
297 inferred_infos: Vec::new(),
299 // cache and share the variance struct used for items with
300 // no type/region parameters
301 empty_variances: Rc::new(ty::ItemVariances {
302 types: VecPerParamSpace::empty(),
303 regions: VecPerParamSpace::empty()
307 visit::walk_crate(&mut terms_cx, krate);
312 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
313 fn add_inferred(&mut self,
314 item_id: ast::NodeId,
318 param_id: ast::NodeId) {
319 let inf_index = InferredIndex(self.inferred_infos.len());
320 let term = self.arena.alloc(|| InferredTerm(inf_index));
321 self.inferred_infos.push(InferredInfo { item_id: item_id,
327 let newly_added = self.inferred_map.insert(param_id, inf_index).is_none();
328 assert!(newly_added);
330 debug!("add_inferred(item_id={}, \
335 item_id, kind, index, param_id, inf_index);
338 fn num_inferred(&self) -> uint {
339 self.inferred_infos.len()
343 impl<'a, 'tcx, 'v> Visitor<'v> for TermsContext<'a, 'tcx> {
344 fn visit_item(&mut self, item: &ast::Item) {
345 debug!("add_inferreds for item {}", item.repr(self.tcx));
347 let inferreds_on_entry = self.num_inferred();
349 // NB: In the code below for writing the results back into the
350 // tcx, we rely on the fact that all inferreds for a particular
351 // item are assigned continuous indices.
353 ast::ItemTrait(..) => {
354 self.add_inferred(item.id, TypeParam, SelfSpace, 0, item.id);
360 ast::ItemEnum(_, ref generics) |
361 ast::ItemStruct(_, ref generics) |
362 ast::ItemTrait(ref generics, _, _, _) => {
363 for (i, p) in generics.lifetimes.iter().enumerate() {
364 let id = p.lifetime.id;
365 self.add_inferred(item.id, RegionParam, TypeSpace, i, id);
367 for (i, p) in generics.ty_params.iter().enumerate() {
368 self.add_inferred(item.id, TypeParam, TypeSpace, i, p.id);
371 // If this item has no type or lifetime parameters,
372 // then there are no variances to infer, so just
373 // insert an empty entry into the variance map.
374 // Arguably we could just leave the map empty in this
375 // case but it seems cleaner to be able to distinguish
376 // "invalid item id" from "item id with no
378 if self.num_inferred() == inferreds_on_entry {
379 let newly_added = self.tcx.item_variance_map.borrow_mut().insert(
380 ast_util::local_def(item.id),
381 self.empty_variances.clone()).is_none();
382 assert!(newly_added);
385 visit::walk_item(self, item);
389 ast::ItemStatic(..) |
393 ast::ItemForeignMod(..) |
395 ast::ItemMac(..) => {
396 visit::walk_item(self, item);
402 /**************************************************************************
403 * Constraint construction and representation
405 * The second pass over the AST determines the set of constraints.
406 * We walk the set of items and, for each member, generate new constraints.
409 struct ConstraintContext<'a, 'tcx: 'a> {
410 terms_cx: TermsContext<'a, 'tcx>,
412 // These are the def-id of the std::kinds::marker::InvariantType,
413 // std::kinds::marker::InvariantLifetime, and so on. The arrays
414 // are indexed by the `ParamKind` (type, lifetime, self). Note
415 // that there are no marker types for self, so the entries for
416 // self are always None.
417 invariant_lang_items: [Option<ast::DefId>, ..2],
418 covariant_lang_items: [Option<ast::DefId>, ..2],
419 contravariant_lang_items: [Option<ast::DefId>, ..2],
420 unsafe_lang_item: Option<ast::DefId>,
422 // These are pointers to common `ConstantTerm` instances
423 covariant: VarianceTermPtr<'a>,
424 contravariant: VarianceTermPtr<'a>,
425 invariant: VarianceTermPtr<'a>,
426 bivariant: VarianceTermPtr<'a>,
428 constraints: Vec<Constraint<'a>> ,
431 /// Declares that the variable `decl_id` appears in a location with
432 /// variance `variance`.
433 struct Constraint<'a> {
434 inferred: InferredIndex,
435 variance: &'a VarianceTerm<'a>,
438 fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>,
440 -> ConstraintContext<'a, 'tcx> {
441 let mut invariant_lang_items = [None, ..2];
442 let mut covariant_lang_items = [None, ..2];
443 let mut contravariant_lang_items = [None, ..2];
445 covariant_lang_items[TypeParam as uint] =
446 terms_cx.tcx.lang_items.covariant_type();
447 covariant_lang_items[RegionParam as uint] =
448 terms_cx.tcx.lang_items.covariant_lifetime();
450 contravariant_lang_items[TypeParam as uint] =
451 terms_cx.tcx.lang_items.contravariant_type();
452 contravariant_lang_items[RegionParam as uint] =
453 terms_cx.tcx.lang_items.contravariant_lifetime();
455 invariant_lang_items[TypeParam as uint] =
456 terms_cx.tcx.lang_items.invariant_type();
457 invariant_lang_items[RegionParam as uint] =
458 terms_cx.tcx.lang_items.invariant_lifetime();
460 let unsafe_lang_item = terms_cx.tcx.lang_items.unsafe_type();
462 let covariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Covariant));
463 let contravariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Contravariant));
464 let invariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Invariant));
465 let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
466 let mut constraint_cx = ConstraintContext {
469 invariant_lang_items: invariant_lang_items,
470 covariant_lang_items: covariant_lang_items,
471 contravariant_lang_items: contravariant_lang_items,
472 unsafe_lang_item: unsafe_lang_item,
474 covariant: covariant,
475 contravariant: contravariant,
476 invariant: invariant,
477 bivariant: bivariant,
478 constraints: Vec::new(),
480 visit::walk_crate(&mut constraint_cx, krate);
484 impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> {
485 fn visit_item(&mut self, item: &ast::Item) {
486 let did = ast_util::local_def(item.id);
487 let tcx = self.terms_cx.tcx;
490 ast::ItemEnum(ref enum_definition, _) => {
491 // Hack: If we directly call `ty::enum_variants`, it
492 // annoyingly takes it upon itself to run off and
493 // evaluate the discriminants eagerly (*grumpy* that's
494 // not the typical pattern). This results in double
495 // error messages because typeck goes off and does
496 // this at a later time. All we really care about is
497 // the types of the variant arguments, so we just call
498 // `ty::VariantInfo::from_ast_variant()` ourselves
499 // here, mainly so as to mask the differences between
500 // struct-like enums and so forth.
501 for ast_variant in enum_definition.variants.iter() {
503 ty::VariantInfo::from_ast_variant(tcx,
506 for arg_ty in variant.args.iter() {
507 self.add_constraints_from_ty(*arg_ty, self.covariant);
512 ast::ItemStruct(..) => {
513 let struct_fields = ty::lookup_struct_fields(tcx, did);
514 for field_info in struct_fields.iter() {
515 assert_eq!(field_info.id.krate, ast::LOCAL_CRATE);
516 let field_ty = ty::node_id_to_type(tcx, field_info.id.node);
517 self.add_constraints_from_ty(field_ty, self.covariant);
521 ast::ItemTrait(..) => {
522 let trait_items = ty::trait_items(tcx, did);
523 for trait_item in trait_items.iter() {
525 ty::MethodTraitItem(ref method) => {
526 self.add_constraints_from_sig(&method.fty.sig,
529 ty::TypeTraitItem(_) => {}
534 ast::ItemStatic(..) |
538 ast::ItemForeignMod(..) |
541 ast::ItemMac(..) => {
542 visit::walk_item(self, item);
548 /// Is `param_id` a lifetime according to `map`?
549 fn is_lifetime(map: &ast_map::Map, param_id: ast::NodeId) -> bool {
550 match map.find(param_id) {
551 Some(ast_map::NodeLifetime(..)) => true, _ => false
555 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
556 fn tcx(&self) -> &'a ty::ctxt<'tcx> {
560 fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
561 match self.terms_cx.inferred_map.get(¶m_id) {
562 Some(&index) => index,
564 self.tcx().sess.bug(format!(
565 "no inferred index entry for {}",
566 self.tcx().map.node_to_string(param_id)).as_slice());
571 fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
572 let tcx = self.terms_cx.tcx;
573 assert!(is_lifetime(&tcx.map, param_id));
574 match tcx.named_region_map.get(¶m_id) {
575 Some(&rl::DefEarlyBoundRegion(_, _, lifetime_decl_id))
577 Some(_) => panic!("should not encounter non early-bound cases"),
579 // The lookup should only fail when `param_id` is
580 // itself a lifetime binding: use it as the decl_id.
586 /// Is `param_id` a type parameter for which we infer variance?
587 fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
588 let result = self.terms_cx.inferred_map.contains_key(¶m_id);
590 // To safe-guard against invalid inferred_map constructions,
591 // double-check if variance is inferred at some use of a type
592 // parameter (by inspecting parent of its binding declaration
593 // to see if it is introduced by a type or by a fn/impl).
595 let check_result = |this:&ConstraintContext| -> bool {
596 let tcx = this.terms_cx.tcx;
597 let decl_id = this.find_binding_for_lifetime(param_id);
598 // Currently only called on lifetimes; double-checking that.
599 assert!(is_lifetime(&tcx.map, param_id));
600 let parent_id = tcx.map.get_parent(decl_id);
601 let parent = tcx.map.find(parent_id).unwrap_or_else(
602 || panic!("tcx.map missing entry for id: {}", parent_id));
605 macro_rules! cannot_happen { () => { {
606 panic!("invalid parent: {} for {}",
607 tcx.map.node_to_string(parent_id),
608 tcx.map.node_to_string(param_id));
612 ast_map::NodeItem(p) => {
616 ast::ItemStruct(..) |
617 ast::ItemTrait(..) => is_inferred = true,
618 ast::ItemFn(..) => is_inferred = false,
619 _ => cannot_happen!(),
622 ast_map::NodeTraitItem(..) => is_inferred = false,
623 ast_map::NodeImplItem(..) => is_inferred = false,
624 _ => cannot_happen!(),
630 assert_eq!(result, check_result(self));
635 fn declared_variance(&self,
636 param_def_id: ast::DefId,
637 item_def_id: ast::DefId,
641 -> VarianceTermPtr<'a> {
643 * Returns a variance term representing the declared variance of
644 * the type/region parameter with the given id.
647 assert_eq!(param_def_id.krate, item_def_id.krate);
649 if self.invariant_lang_items[kind as uint] == Some(item_def_id) {
651 } else if self.covariant_lang_items[kind as uint] == Some(item_def_id) {
653 } else if self.contravariant_lang_items[kind as uint] == Some(item_def_id) {
655 } else if kind == TypeParam && Some(item_def_id) == self.unsafe_lang_item {
657 } else if param_def_id.krate == ast::LOCAL_CRATE {
658 // Parameter on an item defined within current crate:
659 // variance not yet inferred, so return a symbolic
661 let InferredIndex(index) = self.inferred_index(param_def_id.node);
662 self.terms_cx.inferred_infos[index].term
664 // Parameter on an item defined within another crate:
665 // variance already inferred, just look it up.
666 let variances = ty::item_variances(self.tcx(), item_def_id);
667 let variance = match kind {
668 TypeParam => *variances.types.get(space, index),
669 RegionParam => *variances.regions.get(space, index),
671 self.constant_term(variance)
675 fn add_constraint(&mut self,
676 InferredIndex(index): InferredIndex,
677 variance: VarianceTermPtr<'a>) {
678 debug!("add_constraint(index={}, variance={})",
679 index, variance.to_string());
680 self.constraints.push(Constraint { inferred: InferredIndex(index),
681 variance: variance });
684 fn contravariant(&mut self,
685 variance: VarianceTermPtr<'a>)
686 -> VarianceTermPtr<'a> {
687 self.xform(variance, self.contravariant)
690 fn invariant(&mut self,
691 variance: VarianceTermPtr<'a>)
692 -> VarianceTermPtr<'a> {
693 self.xform(variance, self.invariant)
696 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
698 ty::Covariant => self.covariant,
699 ty::Invariant => self.invariant,
700 ty::Contravariant => self.contravariant,
701 ty::Bivariant => self.bivariant,
706 v1: VarianceTermPtr<'a>,
707 v2: VarianceTermPtr<'a>)
708 -> VarianceTermPtr<'a> {
710 (_, ConstantTerm(ty::Covariant)) => {
711 // Applying a "covariant" transform is always a no-op
715 (ConstantTerm(c1), ConstantTerm(c2)) => {
716 self.constant_term(c1.xform(c2))
720 &*self.terms_cx.arena.alloc(|| TransformTerm(v1, v2))
725 /// Adds constraints appropriate for an instance of `ty` appearing
726 /// in a context with ambient variance `variance`
727 fn add_constraints_from_ty(&mut self,
729 variance: VarianceTermPtr<'a>) {
730 debug!("add_constraints_from_ty(ty={})", ty.repr(self.tcx()));
734 ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) |
735 ty::ty_float(_) | ty::ty_str => {
736 /* leaf type -- noop */
739 ty::ty_unboxed_closure(..) => {
740 self.tcx().sess.bug("Unexpected unboxed closure type in variance computation");
743 ty::ty_rptr(region, ref mt) => {
744 let contra = self.contravariant(variance);
745 self.add_constraints_from_region(region, contra);
746 self.add_constraints_from_mt(mt, variance);
749 ty::ty_uniq(typ) | ty::ty_vec(typ, _) | ty::ty_open(typ) => {
750 self.add_constraints_from_ty(typ, variance);
753 ty::ty_ptr(ref mt) => {
754 self.add_constraints_from_mt(mt, variance);
757 ty::ty_tup(ref subtys) => {
758 for &subty in subtys.iter() {
759 self.add_constraints_from_ty(subty, variance);
763 ty::ty_enum(def_id, ref substs) |
764 ty::ty_struct(def_id, ref substs) => {
765 let item_type = ty::lookup_item_type(self.tcx(), def_id);
766 let generics = &item_type.generics;
768 // All type parameters on enums and structs should be
770 assert!(generics.types.is_empty_in(subst::SelfSpace));
771 assert!(generics.types.is_empty_in(subst::FnSpace));
772 assert!(generics.regions.is_empty_in(subst::SelfSpace));
773 assert!(generics.regions.is_empty_in(subst::FnSpace));
775 self.add_constraints_from_substs(
777 generics.types.get_slice(subst::TypeSpace),
778 generics.regions.get_slice(subst::TypeSpace),
783 ty::ty_trait(box ty::TyTrait { ref principal, bounds }) => {
784 let trait_def = ty::lookup_trait_def(self.tcx(), principal.def_id);
785 let generics = &trait_def.generics;
787 // Traits DO have a Self type parameter, but it is
788 // erased from object types.
789 assert!(!generics.types.is_empty_in(subst::SelfSpace) &&
790 principal.substs.types.is_empty_in(subst::SelfSpace));
792 // Traits never declare region parameters in the self
794 assert!(generics.regions.is_empty_in(subst::SelfSpace));
796 // Traits never declare type/region parameters in the
798 assert!(generics.types.is_empty_in(subst::FnSpace));
799 assert!(generics.regions.is_empty_in(subst::FnSpace));
801 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
802 let contra = self.contravariant(variance);
803 self.add_constraints_from_region(bounds.region_bound, contra);
805 self.add_constraints_from_substs(
807 generics.types.get_slice(subst::TypeSpace),
808 generics.regions.get_slice(subst::TypeSpace),
813 ty::ty_param(ty::ParamTy { ref def_id, .. }) => {
814 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
815 match self.terms_cx.inferred_map.get(&def_id.node) {
817 self.add_constraint(index, variance);
820 // We do not infer variance for type parameters
821 // declared on methods. They will not be present
822 // in the inferred_map.
827 ty::ty_bare_fn(ty::BareFnTy { ref sig, .. }) |
828 ty::ty_closure(box ty::ClosureTy {
830 store: ty::UniqTraitStore,
833 self.add_constraints_from_sig(sig, variance);
836 ty::ty_closure(box ty::ClosureTy { ref sig,
837 store: ty::RegionTraitStore(region, _), .. }) => {
838 let contra = self.contravariant(variance);
839 self.add_constraints_from_region(region, contra);
840 self.add_constraints_from_sig(sig, variance);
843 ty::ty_infer(..) | ty::ty_err => {
845 format!("unexpected type encountered in \
846 variance inference: {}",
847 ty.repr(self.tcx())).as_slice());
853 /// Adds constraints appropriate for a nominal type (enum, struct,
854 /// object, etc) appearing in a context with ambient variance `variance`
855 fn add_constraints_from_substs(&mut self,
857 type_param_defs: &[ty::TypeParameterDef<'tcx>],
858 region_param_defs: &[ty::RegionParameterDef],
859 substs: &subst::Substs<'tcx>,
860 variance: VarianceTermPtr<'a>) {
861 debug!("add_constraints_from_substs(def_id={})", def_id);
863 for p in type_param_defs.iter() {
865 self.declared_variance(p.def_id, def_id, TypeParam,
867 let variance_i = self.xform(variance, variance_decl);
868 let substs_ty = *substs.types.get(p.space, p.index);
869 self.add_constraints_from_ty(substs_ty, variance_i);
872 for p in region_param_defs.iter() {
874 self.declared_variance(p.def_id, def_id,
875 RegionParam, p.space, p.index);
876 let variance_i = self.xform(variance, variance_decl);
877 let substs_r = *substs.regions().get(p.space, p.index);
878 self.add_constraints_from_region(substs_r, variance_i);
882 /// Adds constraints appropriate for a function with signature
883 /// `sig` appearing in a context with ambient variance `variance`
884 fn add_constraints_from_sig(&mut self,
885 sig: &ty::FnSig<'tcx>,
886 variance: VarianceTermPtr<'a>) {
887 let contra = self.contravariant(variance);
888 for &input in sig.inputs.iter() {
889 self.add_constraints_from_ty(input, contra);
891 if let ty::FnConverging(result_type) = sig.output {
892 self.add_constraints_from_ty(result_type, variance);
896 /// Adds constraints appropriate for a region appearing in a
897 /// context with ambient variance `variance`
898 fn add_constraints_from_region(&mut self,
900 variance: VarianceTermPtr<'a>) {
902 ty::ReEarlyBound(param_id, _, _, _) => {
903 if self.is_to_be_inferred(param_id) {
904 let index = self.inferred_index(param_id);
905 self.add_constraint(index, variance);
911 ty::ReLateBound(..) => {
912 // We do not infer variance for region parameters on
913 // methods or in fn types.
916 ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) |
918 // We don't expect to see anything but 'static or bound
919 // regions when visiting member types or method types.
922 .bug(format!("unexpected region encountered in variance \
924 region.repr(self.tcx())).as_slice());
929 /// Adds constraints appropriate for a mutability-type pair
930 /// appearing in a context with ambient variance `variance`
931 fn add_constraints_from_mt(&mut self,
933 variance: VarianceTermPtr<'a>) {
936 let invar = self.invariant(variance);
937 self.add_constraints_from_ty(mt.ty, invar);
940 ast::MutImmutable => {
941 self.add_constraints_from_ty(mt.ty, variance);
947 /**************************************************************************
950 * The final phase iterates over the constraints, refining the variance
951 * for each inferred until a fixed point is reached. This will be the
952 * optimal solution to the constraints. The final variance for each
953 * inferred is then written into the `variance_map` in the tcx.
956 struct SolveContext<'a, 'tcx: 'a> {
957 terms_cx: TermsContext<'a, 'tcx>,
958 constraints: Vec<Constraint<'a>> ,
960 // Maps from an InferredIndex to the inferred value for that variable.
961 solutions: Vec<ty::Variance> }
963 fn solve_constraints(constraints_cx: ConstraintContext) {
964 let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
965 let solutions = Vec::from_elem(terms_cx.num_inferred(), ty::Bivariant);
966 let mut solutions_cx = SolveContext {
968 constraints: constraints,
971 solutions_cx.solve();
972 solutions_cx.write();
975 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
976 fn solve(&mut self) {
977 // Propagate constraints until a fixed point is reached. Note
978 // that the maximum number of iterations is 2C where C is the
979 // number of constraints (each variable can change values at most
980 // twice). Since number of constraints is linear in size of the
981 // input, so is the inference process.
982 let mut changed = true;
986 for constraint in self.constraints.iter() {
987 let Constraint { inferred, variance: term } = *constraint;
988 let InferredIndex(inferred) = inferred;
989 let variance = self.evaluate(term);
990 let old_value = self.solutions[inferred];
991 let new_value = glb(variance, old_value);
992 if old_value != new_value {
993 debug!("Updating inferred {} (node {}) \
994 from {} to {} due to {}",
997 .inferred_infos[inferred]
1003 self.solutions[inferred] = new_value;
1011 // Collect all the variances for a particular item and stick
1012 // them into the variance map. We rely on the fact that we
1013 // generate all the inferreds for a particular item
1014 // consecutively (that is, we collect solutions for an item
1015 // until we see a new item id, and we assume (1) the solutions
1016 // are in the same order as the type parameters were declared
1017 // and (2) all solutions or a given item appear before a new
1020 let tcx = self.terms_cx.tcx;
1021 let solutions = &self.solutions;
1022 let inferred_infos = &self.terms_cx.inferred_infos;
1024 let num_inferred = self.terms_cx.num_inferred();
1025 while index < num_inferred {
1026 let item_id = inferred_infos[index].item_id;
1027 let mut types = VecPerParamSpace::empty();
1028 let mut regions = VecPerParamSpace::empty();
1030 while index < num_inferred &&
1031 inferred_infos[index].item_id == item_id {
1032 let info = inferred_infos[index];
1033 let variance = solutions[index];
1034 debug!("Index {} Info {} / {} / {} Variance {}",
1035 index, info.index, info.kind, info.space, variance);
1038 types.push(info.space, variance);
1041 regions.push(info.space, variance);
1047 let item_variances = ty::ItemVariances {
1051 debug!("item_id={} item_variances={}",
1053 item_variances.repr(tcx));
1055 let item_def_id = ast_util::local_def(item_id);
1057 // For unit testing: check for a special "rustc_variance"
1058 // attribute and report an error with various results if found.
1059 if ty::has_attr(tcx, item_def_id, "rustc_variance") {
1060 let found = item_variances.repr(tcx);
1061 tcx.sess.span_err(tcx.map.span(item_id), found.as_slice());
1064 let newly_added = tcx.item_variance_map.borrow_mut()
1065 .insert(item_def_id, Rc::new(item_variances)).is_none();
1066 assert!(newly_added);
1070 fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
1072 ConstantTerm(v) => {
1076 TransformTerm(t1, t2) => {
1077 let v1 = self.evaluate(t1);
1078 let v2 = self.evaluate(t2);
1082 InferredTerm(InferredIndex(index)) => {
1083 self.solutions[index]
1089 /**************************************************************************
1090 * Miscellany transformations on variance
1094 fn xform(self, v: Self) -> Self;
1097 impl Xform for ty::Variance {
1098 fn xform(self, v: ty::Variance) -> ty::Variance {
1099 // "Variance transformation", Figure 1 of The Paper
1101 // Figure 1, column 1.
1102 (ty::Covariant, ty::Covariant) => ty::Covariant,
1103 (ty::Covariant, ty::Contravariant) => ty::Contravariant,
1104 (ty::Covariant, ty::Invariant) => ty::Invariant,
1105 (ty::Covariant, ty::Bivariant) => ty::Bivariant,
1107 // Figure 1, column 2.
1108 (ty::Contravariant, ty::Covariant) => ty::Contravariant,
1109 (ty::Contravariant, ty::Contravariant) => ty::Covariant,
1110 (ty::Contravariant, ty::Invariant) => ty::Invariant,
1111 (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
1113 // Figure 1, column 3.
1114 (ty::Invariant, _) => ty::Invariant,
1116 // Figure 1, column 4.
1117 (ty::Bivariant, _) => ty::Bivariant,
1122 fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance {
1123 // Greatest lower bound of the variance lattice as
1124 // defined in The Paper:
1130 (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
1132 (ty::Covariant, ty::Contravariant) => ty::Invariant,
1133 (ty::Contravariant, ty::Covariant) => ty::Invariant,
1135 (ty::Covariant, ty::Covariant) => ty::Covariant,
1137 (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
1139 (x, ty::Bivariant) | (ty::Bivariant, x) => x,