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)`.
195 use std::collections::HashMap;
198 use middle::resolve_lifetime as rl;
200 use middle::subst::{ParamSpace, FnSpace, TypeSpace, SelfSpace, VecPerParamSpace};
206 use syntax::ast_util;
208 use syntax::visit::Visitor;
209 use util::ppaux::Repr;
211 pub fn infer_variance(tcx: &ty::ctxt) {
212 let krate = tcx.map.krate();
213 let mut arena = arena::Arena::new();
214 let terms_cx = determine_parameters_to_be_inferred(tcx, &mut arena, krate);
215 let constraints_cx = add_constraints_from_crate(terms_cx, krate);
216 solve_constraints(constraints_cx);
217 tcx.variance_computed.set(true);
220 /**************************************************************************
223 * Terms are structured as a straightforward tree. Rather than rely on
224 * GC, we allocate terms out of a bounded arena (the lifetime of this
225 * arena is the lifetime 'a that is threaded around).
227 * We assign a unique index to each type/region parameter whose variance
228 * is to be inferred. We refer to such variables as "inferreds". An
229 * `InferredIndex` is a newtype'd int representing the index of such
233 type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
236 struct InferredIndex(uint);
238 enum VarianceTerm<'a> {
239 ConstantTerm(ty::Variance),
240 TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
241 InferredTerm(InferredIndex),
244 impl<'a> fmt::Show for VarianceTerm<'a> {
245 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
247 ConstantTerm(c1) => write!(f, "{}", c1),
248 TransformTerm(v1, v2) => write!(f, "({} \u00D7 {})", v1, v2),
249 InferredTerm(id) => write!(f, "[{}]", { let InferredIndex(i) = id; i })
254 /**************************************************************************
255 * The first pass over the crate simply builds up the set of inferreds.
258 struct TermsContext<'a, 'tcx: 'a> {
259 tcx: &'a ty::ctxt<'tcx>,
262 empty_variances: Rc<ty::ItemVariances>,
264 // Maps from the node id of a type/generic parameter to the
265 // corresponding inferred index.
266 inferred_map: HashMap<ast::NodeId, InferredIndex>,
268 // Maps from an InferredIndex to the info for that variable.
269 inferred_infos: Vec<InferredInfo<'a>> ,
272 #[deriving(Show, PartialEq)]
278 struct InferredInfo<'a> {
279 item_id: ast::NodeId,
283 param_id: ast::NodeId,
284 term: VarianceTermPtr<'a>,
287 fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
288 arena: &'a mut Arena,
290 -> TermsContext<'a, 'tcx> {
291 let mut terms_cx = TermsContext {
294 inferred_map: HashMap::new(),
295 inferred_infos: Vec::new(),
297 // cache and share the variance struct used for items with
298 // no type/region parameters
299 empty_variances: Rc::new(ty::ItemVariances {
300 types: VecPerParamSpace::empty(),
301 regions: VecPerParamSpace::empty()
305 visit::walk_crate(&mut terms_cx, krate);
310 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
311 fn add_inferred(&mut self,
312 item_id: ast::NodeId,
316 param_id: ast::NodeId) {
317 let inf_index = InferredIndex(self.inferred_infos.len());
318 let term = self.arena.alloc(|| InferredTerm(inf_index));
319 self.inferred_infos.push(InferredInfo { item_id: item_id,
325 let newly_added = self.inferred_map.insert(param_id, inf_index);
326 assert!(newly_added);
328 debug!("add_inferred(item_id={}, \
333 item_id, kind, index, param_id, inf_index);
336 fn num_inferred(&self) -> uint {
337 self.inferred_infos.len()
341 impl<'a, 'tcx, 'v> Visitor<'v> for TermsContext<'a, 'tcx> {
342 fn visit_item(&mut self, item: &ast::Item) {
343 debug!("add_inferreds for item {}", item.repr(self.tcx));
345 let inferreds_on_entry = self.num_inferred();
347 // NB: In the code below for writing the results back into the
348 // tcx, we rely on the fact that all inferreds for a particular
349 // item are assigned continuous indices.
351 ast::ItemTrait(..) => {
352 self.add_inferred(item.id, TypeParam, SelfSpace, 0, item.id);
358 ast::ItemEnum(_, ref generics) |
359 ast::ItemStruct(_, ref generics) |
360 ast::ItemTrait(ref generics, _, _, _) => {
361 for (i, p) in generics.lifetimes.iter().enumerate() {
362 let id = p.lifetime.id;
363 self.add_inferred(item.id, RegionParam, TypeSpace, i, id);
365 for (i, p) in generics.ty_params.iter().enumerate() {
366 self.add_inferred(item.id, TypeParam, TypeSpace, i, p.id);
369 // If this item has no type or lifetime parameters,
370 // then there are no variances to infer, so just
371 // insert an empty entry into the variance map.
372 // Arguably we could just leave the map empty in this
373 // case but it seems cleaner to be able to distinguish
374 // "invalid item id" from "item id with no
376 if self.num_inferred() == inferreds_on_entry {
377 let newly_added = self.tcx.item_variance_map.borrow_mut().insert(
378 ast_util::local_def(item.id),
379 self.empty_variances.clone());
380 assert!(newly_added);
383 visit::walk_item(self, item);
387 ast::ItemStatic(..) |
391 ast::ItemForeignMod(..) |
393 ast::ItemMac(..) => {
394 visit::walk_item(self, item);
400 /**************************************************************************
401 * Constraint construction and representation
403 * The second pass over the AST determines the set of constraints.
404 * We walk the set of items and, for each member, generate new constraints.
407 struct ConstraintContext<'a, 'tcx: 'a> {
408 terms_cx: TermsContext<'a, 'tcx>,
410 // These are the def-id of the std::kinds::marker::InvariantType,
411 // std::kinds::marker::InvariantLifetime, and so on. The arrays
412 // are indexed by the `ParamKind` (type, lifetime, self). Note
413 // that there are no marker types for self, so the entries for
414 // self are always None.
415 invariant_lang_items: [Option<ast::DefId>, ..2],
416 covariant_lang_items: [Option<ast::DefId>, ..2],
417 contravariant_lang_items: [Option<ast::DefId>, ..2],
418 unsafe_lang_item: Option<ast::DefId>,
420 // These are pointers to common `ConstantTerm` instances
421 covariant: VarianceTermPtr<'a>,
422 contravariant: VarianceTermPtr<'a>,
423 invariant: VarianceTermPtr<'a>,
424 bivariant: VarianceTermPtr<'a>,
426 constraints: Vec<Constraint<'a>> ,
429 /// Declares that the variable `decl_id` appears in a location with
430 /// variance `variance`.
431 struct Constraint<'a> {
432 inferred: InferredIndex,
433 variance: &'a VarianceTerm<'a>,
436 fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>,
438 -> ConstraintContext<'a, 'tcx> {
439 let mut invariant_lang_items = [None, ..2];
440 let mut covariant_lang_items = [None, ..2];
441 let mut contravariant_lang_items = [None, ..2];
443 covariant_lang_items[TypeParam as uint] =
444 terms_cx.tcx.lang_items.covariant_type();
445 covariant_lang_items[RegionParam as uint] =
446 terms_cx.tcx.lang_items.covariant_lifetime();
448 contravariant_lang_items[TypeParam as uint] =
449 terms_cx.tcx.lang_items.contravariant_type();
450 contravariant_lang_items[RegionParam as uint] =
451 terms_cx.tcx.lang_items.contravariant_lifetime();
453 invariant_lang_items[TypeParam as uint] =
454 terms_cx.tcx.lang_items.invariant_type();
455 invariant_lang_items[RegionParam as uint] =
456 terms_cx.tcx.lang_items.invariant_lifetime();
458 let unsafe_lang_item = terms_cx.tcx.lang_items.unsafe_type();
460 let covariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Covariant));
461 let contravariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Contravariant));
462 let invariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Invariant));
463 let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
464 let mut constraint_cx = ConstraintContext {
467 invariant_lang_items: invariant_lang_items,
468 covariant_lang_items: covariant_lang_items,
469 contravariant_lang_items: contravariant_lang_items,
470 unsafe_lang_item: unsafe_lang_item,
472 covariant: covariant,
473 contravariant: contravariant,
474 invariant: invariant,
475 bivariant: bivariant,
476 constraints: Vec::new(),
478 visit::walk_crate(&mut constraint_cx, krate);
482 impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> {
483 fn visit_item(&mut self, item: &ast::Item) {
484 let did = ast_util::local_def(item.id);
485 let tcx = self.terms_cx.tcx;
488 ast::ItemEnum(ref enum_definition, _) => {
489 // Hack: If we directly call `ty::enum_variants`, it
490 // annoyingly takes it upon itself to run off and
491 // evaluate the discriminants eagerly (*grumpy* that's
492 // not the typical pattern). This results in double
493 // error messages because typeck goes off and does
494 // this at a later time. All we really care about is
495 // the types of the variant arguments, so we just call
496 // `ty::VariantInfo::from_ast_variant()` ourselves
497 // here, mainly so as to mask the differences between
498 // struct-like enums and so forth.
499 for ast_variant in enum_definition.variants.iter() {
501 ty::VariantInfo::from_ast_variant(tcx,
504 for arg_ty in variant.args.iter() {
505 self.add_constraints_from_ty(*arg_ty, self.covariant);
510 ast::ItemStruct(..) => {
511 let struct_fields = ty::lookup_struct_fields(tcx, did);
512 for field_info in struct_fields.iter() {
513 assert_eq!(field_info.id.krate, ast::LOCAL_CRATE);
514 let field_ty = ty::node_id_to_type(tcx, field_info.id.node);
515 self.add_constraints_from_ty(field_ty, self.covariant);
519 ast::ItemTrait(..) => {
520 let trait_items = ty::trait_items(tcx, did);
521 for trait_item in trait_items.iter() {
523 ty::MethodTraitItem(ref method) => {
524 self.add_constraints_from_sig(&method.fty.sig,
527 ty::TypeTraitItem(_) => {}
532 ast::ItemStatic(..) |
536 ast::ItemForeignMod(..) |
539 ast::ItemMac(..) => {
540 visit::walk_item(self, item);
546 /// Is `param_id` a lifetime according to `map`?
547 fn is_lifetime(map: &ast_map::Map, param_id: ast::NodeId) -> bool {
548 match map.find(param_id) {
549 Some(ast_map::NodeLifetime(..)) => true, _ => false
553 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
554 fn tcx(&self) -> &'a ty::ctxt<'tcx> {
558 fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
559 match self.terms_cx.inferred_map.find(¶m_id) {
560 Some(&index) => index,
562 self.tcx().sess.bug(format!(
563 "no inferred index entry for {}",
564 self.tcx().map.node_to_string(param_id)).as_slice());
569 fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
570 let tcx = self.terms_cx.tcx;
571 assert!(is_lifetime(&tcx.map, param_id));
572 match tcx.named_region_map.find(¶m_id) {
573 Some(&rl::DefEarlyBoundRegion(_, _, lifetime_decl_id))
575 Some(_) => fail!("should not encounter non early-bound cases"),
577 // The lookup should only fail when `param_id` is
578 // itself a lifetime binding: use it as the decl_id.
584 /// Is `param_id` a type parameter for which we infer variance?
585 fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
586 let result = self.terms_cx.inferred_map.contains_key(¶m_id);
588 // To safe-guard against invalid inferred_map constructions,
589 // double-check if variance is inferred at some use of a type
590 // parameter (by inspecting parent of its binding declaration
591 // to see if it is introduced by a type or by a fn/impl).
593 let check_result = |this:&ConstraintContext| -> bool {
594 let tcx = this.terms_cx.tcx;
595 let decl_id = this.find_binding_for_lifetime(param_id);
596 // Currently only called on lifetimes; double-checking that.
597 assert!(is_lifetime(&tcx.map, param_id));
598 let parent_id = tcx.map.get_parent(decl_id);
599 let parent = tcx.map.find(parent_id).unwrap_or_else(
600 || fail!("tcx.map missing entry for id: {}", parent_id));
603 macro_rules! cannot_happen { () => { {
604 fail!("invalid parent: {:s} for {:s}",
605 tcx.map.node_to_string(parent_id),
606 tcx.map.node_to_string(param_id));
610 ast_map::NodeItem(p) => {
614 ast::ItemStruct(..) |
615 ast::ItemTrait(..) => is_inferred = true,
616 ast::ItemFn(..) => is_inferred = false,
617 _ => cannot_happen!(),
620 ast_map::NodeTraitItem(..) => is_inferred = false,
621 ast_map::NodeImplItem(..) => is_inferred = false,
622 _ => cannot_happen!(),
628 assert_eq!(result, check_result(self));
633 fn declared_variance(&self,
634 param_def_id: ast::DefId,
635 item_def_id: ast::DefId,
639 -> VarianceTermPtr<'a> {
641 * Returns a variance term representing the declared variance of
642 * the type/region parameter with the given id.
645 assert_eq!(param_def_id.krate, item_def_id.krate);
647 if self.invariant_lang_items[kind as uint] == Some(item_def_id) {
649 } else if self.covariant_lang_items[kind as uint] == Some(item_def_id) {
651 } else if self.contravariant_lang_items[kind as uint] == Some(item_def_id) {
653 } else if kind == TypeParam && Some(item_def_id) == self.unsafe_lang_item {
655 } else if param_def_id.krate == ast::LOCAL_CRATE {
656 // Parameter on an item defined within current crate:
657 // variance not yet inferred, so return a symbolic
659 let InferredIndex(index) = self.inferred_index(param_def_id.node);
660 self.terms_cx.inferred_infos[index].term
662 // Parameter on an item defined within another crate:
663 // variance already inferred, just look it up.
664 let variances = ty::item_variances(self.tcx(), item_def_id);
665 let variance = match kind {
666 TypeParam => *variances.types.get(space, index),
667 RegionParam => *variances.regions.get(space, index),
669 self.constant_term(variance)
673 fn add_constraint(&mut self,
674 InferredIndex(index): InferredIndex,
675 variance: VarianceTermPtr<'a>) {
676 debug!("add_constraint(index={}, variance={})",
677 index, variance.to_string());
678 self.constraints.push(Constraint { inferred: InferredIndex(index),
679 variance: variance });
682 fn contravariant(&mut self,
683 variance: VarianceTermPtr<'a>)
684 -> VarianceTermPtr<'a> {
685 self.xform(variance, self.contravariant)
688 fn invariant(&mut self,
689 variance: VarianceTermPtr<'a>)
690 -> VarianceTermPtr<'a> {
691 self.xform(variance, self.invariant)
694 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
696 ty::Covariant => self.covariant,
697 ty::Invariant => self.invariant,
698 ty::Contravariant => self.contravariant,
699 ty::Bivariant => self.bivariant,
704 v1: VarianceTermPtr<'a>,
705 v2: VarianceTermPtr<'a>)
706 -> VarianceTermPtr<'a> {
708 (_, ConstantTerm(ty::Covariant)) => {
709 // Applying a "covariant" transform is always a no-op
713 (ConstantTerm(c1), ConstantTerm(c2)) => {
714 self.constant_term(c1.xform(c2))
718 &*self.terms_cx.arena.alloc(|| TransformTerm(v1, v2))
723 /// Adds constraints appropriate for an instance of `ty` appearing
724 /// in a context with ambient variance `variance`
725 fn add_constraints_from_ty(&mut self,
727 variance: VarianceTermPtr<'a>) {
728 debug!("add_constraints_from_ty(ty={})", ty.repr(self.tcx()));
730 match ty::get(ty).sty {
731 ty::ty_nil | ty::ty_bot | ty::ty_bool |
732 ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) |
733 ty::ty_float(_) | ty::ty_str => {
734 /* leaf type -- noop */
737 ty::ty_unboxed_closure(_, region) => {
738 let contra = self.contravariant(variance);
739 self.add_constraints_from_region(region, contra);
742 ty::ty_rptr(region, ref mt) => {
743 let contra = self.contravariant(variance);
744 self.add_constraints_from_region(region, contra);
745 self.add_constraints_from_mt(mt, variance);
748 ty::ty_uniq(typ) | ty::ty_vec(typ, _) | ty::ty_open(typ) => {
749 self.add_constraints_from_ty(typ, variance);
752 ty::ty_ptr(ref mt) => {
753 self.add_constraints_from_mt(mt, variance);
756 ty::ty_tup(ref subtys) => {
757 for &subty in subtys.iter() {
758 self.add_constraints_from_ty(subty, variance);
762 ty::ty_enum(def_id, ref substs) |
763 ty::ty_struct(def_id, ref substs) => {
764 let item_type = ty::lookup_item_type(self.tcx(), def_id);
765 let generics = &item_type.generics;
767 // All type parameters on enums and structs should be
769 assert!(generics.types.is_empty_in(subst::SelfSpace));
770 assert!(generics.types.is_empty_in(subst::FnSpace));
771 assert!(generics.regions.is_empty_in(subst::SelfSpace));
772 assert!(generics.regions.is_empty_in(subst::FnSpace));
774 self.add_constraints_from_substs(
776 generics.types.get_slice(subst::TypeSpace),
777 generics.regions.get_slice(subst::TypeSpace),
782 ty::ty_trait(box ty::TyTrait { def_id, ref substs, .. }) => {
783 let trait_def = ty::lookup_trait_def(self.tcx(), def_id);
784 let generics = &trait_def.generics;
786 // Traits DO have a Self type parameter, but it is
787 // erased from object types.
788 assert!(!generics.types.is_empty_in(subst::SelfSpace) &&
789 substs.types.is_empty_in(subst::SelfSpace));
791 // Traits never declare region parameters in the self
793 assert!(generics.regions.is_empty_in(subst::SelfSpace));
795 // Traits never declare type/region parameters in the
797 assert!(generics.types.is_empty_in(subst::FnSpace));
798 assert!(generics.regions.is_empty_in(subst::FnSpace));
800 self.add_constraints_from_substs(
802 generics.types.get_slice(subst::TypeSpace),
803 generics.regions.get_slice(subst::TypeSpace),
808 ty::ty_param(ty::ParamTy { ref def_id, .. }) => {
809 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
810 match self.terms_cx.inferred_map.find(&def_id.node) {
812 self.add_constraint(index, variance);
815 // We do not infer variance for type parameters
816 // declared on methods. They will not be present
817 // in the inferred_map.
822 ty::ty_bare_fn(ty::BareFnTy { ref sig, .. }) |
823 ty::ty_closure(box ty::ClosureTy {
825 store: ty::UniqTraitStore,
828 self.add_constraints_from_sig(sig, variance);
831 ty::ty_closure(box ty::ClosureTy { ref sig,
832 store: ty::RegionTraitStore(region, _), .. }) => {
833 let contra = self.contravariant(variance);
834 self.add_constraints_from_region(region, contra);
835 self.add_constraints_from_sig(sig, variance);
838 ty::ty_infer(..) | ty::ty_err => {
840 format!("unexpected type encountered in \
841 variance inference: {}",
842 ty.repr(self.tcx())).as_slice());
848 /// Adds constraints appropriate for a nominal type (enum, struct,
849 /// object, etc) appearing in a context with ambient variance `variance`
850 fn add_constraints_from_substs(&mut self,
852 type_param_defs: &[ty::TypeParameterDef],
853 region_param_defs: &[ty::RegionParameterDef],
854 substs: &subst::Substs,
855 variance: VarianceTermPtr<'a>) {
856 debug!("add_constraints_from_substs(def_id={})", def_id);
858 for p in type_param_defs.iter() {
860 self.declared_variance(p.def_id, def_id, TypeParam,
862 let variance_i = self.xform(variance, variance_decl);
863 let substs_ty = *substs.types.get(p.space, p.index);
864 self.add_constraints_from_ty(substs_ty, variance_i);
867 for p in region_param_defs.iter() {
869 self.declared_variance(p.def_id, def_id,
870 RegionParam, p.space, p.index);
871 let variance_i = self.xform(variance, variance_decl);
872 let substs_r = *substs.regions().get(p.space, p.index);
873 self.add_constraints_from_region(substs_r, variance_i);
877 /// Adds constraints appropriate for a function with signature
878 /// `sig` appearing in a context with ambient variance `variance`
879 fn add_constraints_from_sig(&mut self,
881 variance: VarianceTermPtr<'a>) {
882 let contra = self.contravariant(variance);
883 for &input in sig.inputs.iter() {
884 self.add_constraints_from_ty(input, contra);
886 self.add_constraints_from_ty(sig.output, variance);
889 /// Adds constraints appropriate for a region appearing in a
890 /// context with ambient variance `variance`
891 fn add_constraints_from_region(&mut self,
893 variance: VarianceTermPtr<'a>) {
895 ty::ReEarlyBound(param_id, _, _, _) => {
896 if self.is_to_be_inferred(param_id) {
897 let index = self.inferred_index(param_id);
898 self.add_constraint(index, variance);
904 ty::ReLateBound(..) => {
905 // We do not infer variance for region parameters on
906 // methods or in fn types.
909 ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) |
911 // We don't expect to see anything but 'static or bound
912 // regions when visiting member types or method types.
915 .bug(format!("unexpected region encountered in variance \
917 region.repr(self.tcx())).as_slice());
922 /// Adds constraints appropriate for a mutability-type pair
923 /// appearing in a context with ambient variance `variance`
924 fn add_constraints_from_mt(&mut self,
926 variance: VarianceTermPtr<'a>) {
929 let invar = self.invariant(variance);
930 self.add_constraints_from_ty(mt.ty, invar);
933 ast::MutImmutable => {
934 self.add_constraints_from_ty(mt.ty, variance);
940 /**************************************************************************
943 * The final phase iterates over the constraints, refining the variance
944 * for each inferred until a fixed point is reached. This will be the
945 * optimal solution to the constraints. The final variance for each
946 * inferred is then written into the `variance_map` in the tcx.
949 struct SolveContext<'a, 'tcx: 'a> {
950 terms_cx: TermsContext<'a, 'tcx>,
951 constraints: Vec<Constraint<'a>> ,
953 // Maps from an InferredIndex to the inferred value for that variable.
954 solutions: Vec<ty::Variance> }
956 fn solve_constraints(constraints_cx: ConstraintContext) {
957 let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
958 let solutions = Vec::from_elem(terms_cx.num_inferred(), ty::Bivariant);
959 let mut solutions_cx = SolveContext {
961 constraints: constraints,
964 solutions_cx.solve();
965 solutions_cx.write();
968 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
969 fn solve(&mut self) {
970 // Propagate constraints until a fixed point is reached. Note
971 // that the maximum number of iterations is 2C where C is the
972 // number of constraints (each variable can change values at most
973 // twice). Since number of constraints is linear in size of the
974 // input, so is the inference process.
975 let mut changed = true;
979 for constraint in self.constraints.iter() {
980 let Constraint { inferred, variance: term } = *constraint;
981 let InferredIndex(inferred) = inferred;
982 let variance = self.evaluate(term);
983 let old_value = self.solutions[inferred];
984 let new_value = glb(variance, old_value);
985 if old_value != new_value {
986 debug!("Updating inferred {} (node {}) \
987 from {} to {} due to {}",
990 .inferred_infos[inferred]
996 *self.solutions.get_mut(inferred) = new_value;
1004 // Collect all the variances for a particular item and stick
1005 // them into the variance map. We rely on the fact that we
1006 // generate all the inferreds for a particular item
1007 // consecutively (that is, we collect solutions for an item
1008 // until we see a new item id, and we assume (1) the solutions
1009 // are in the same order as the type parameters were declared
1010 // and (2) all solutions or a given item appear before a new
1013 let tcx = self.terms_cx.tcx;
1014 let solutions = &self.solutions;
1015 let inferred_infos = &self.terms_cx.inferred_infos;
1017 let num_inferred = self.terms_cx.num_inferred();
1018 while index < num_inferred {
1019 let item_id = inferred_infos[index].item_id;
1020 let mut types = VecPerParamSpace::empty();
1021 let mut regions = VecPerParamSpace::empty();
1023 while index < num_inferred &&
1024 inferred_infos[index].item_id == item_id {
1025 let info = inferred_infos[index];
1026 let variance = solutions[index];
1027 debug!("Index {} Info {} / {} / {} Variance {}",
1028 index, info.index, info.kind, info.space, variance);
1031 types.push(info.space, variance);
1034 regions.push(info.space, variance);
1040 let item_variances = ty::ItemVariances {
1044 debug!("item_id={} item_variances={}",
1046 item_variances.repr(tcx));
1048 let item_def_id = ast_util::local_def(item_id);
1050 // For unit testing: check for a special "rustc_variance"
1051 // attribute and report an error with various results if found.
1052 if ty::has_attr(tcx, item_def_id, "rustc_variance") {
1053 let found = item_variances.repr(tcx);
1054 tcx.sess.span_err(tcx.map.span(item_id), found.as_slice());
1057 let newly_added = tcx.item_variance_map.borrow_mut()
1058 .insert(item_def_id, Rc::new(item_variances));
1059 assert!(newly_added);
1063 fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
1065 ConstantTerm(v) => {
1069 TransformTerm(t1, t2) => {
1070 let v1 = self.evaluate(t1);
1071 let v2 = self.evaluate(t2);
1075 InferredTerm(InferredIndex(index)) => {
1076 self.solutions[index]
1082 /**************************************************************************
1083 * Miscellany transformations on variance
1087 fn xform(self, v: Self) -> Self;
1090 impl Xform for ty::Variance {
1091 fn xform(self, v: ty::Variance) -> ty::Variance {
1092 // "Variance transformation", Figure 1 of The Paper
1094 // Figure 1, column 1.
1095 (ty::Covariant, ty::Covariant) => ty::Covariant,
1096 (ty::Covariant, ty::Contravariant) => ty::Contravariant,
1097 (ty::Covariant, ty::Invariant) => ty::Invariant,
1098 (ty::Covariant, ty::Bivariant) => ty::Bivariant,
1100 // Figure 1, column 2.
1101 (ty::Contravariant, ty::Covariant) => ty::Contravariant,
1102 (ty::Contravariant, ty::Contravariant) => ty::Covariant,
1103 (ty::Contravariant, ty::Invariant) => ty::Invariant,
1104 (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
1106 // Figure 1, column 3.
1107 (ty::Invariant, _) => ty::Invariant,
1109 // Figure 1, column 4.
1110 (ty::Bivariant, _) => ty::Bivariant,
1115 fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance {
1116 // Greatest lower bound of the variance lattice as
1117 // defined in The Paper:
1123 (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
1125 (ty::Covariant, ty::Contravariant) => ty::Invariant,
1126 (ty::Contravariant, ty::Covariant) => ty::Invariant,
1128 (ty::Covariant, ty::Covariant) => ty::Covariant,
1130 (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
1132 (x, ty::Bivariant) | (ty::Bivariant, x) => x,