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_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(..) => {
738 self.tcx().sess.bug("Unexpected unboxed closure type in variance computation");
741 ty::ty_rptr(region, ref mt) => {
742 let contra = self.contravariant(variance);
743 self.add_constraints_from_region(region, contra);
744 self.add_constraints_from_mt(mt, variance);
747 ty::ty_uniq(typ) | ty::ty_vec(typ, _) | ty::ty_open(typ) => {
748 self.add_constraints_from_ty(typ, variance);
751 ty::ty_ptr(ref mt) => {
752 self.add_constraints_from_mt(mt, variance);
755 ty::ty_tup(ref subtys) => {
756 for &subty in subtys.iter() {
757 self.add_constraints_from_ty(subty, variance);
761 ty::ty_enum(def_id, ref substs) |
762 ty::ty_struct(def_id, ref substs) => {
763 let item_type = ty::lookup_item_type(self.tcx(), def_id);
764 let generics = &item_type.generics;
766 // All type parameters on enums and structs should be
768 assert!(generics.types.is_empty_in(subst::SelfSpace));
769 assert!(generics.types.is_empty_in(subst::FnSpace));
770 assert!(generics.regions.is_empty_in(subst::SelfSpace));
771 assert!(generics.regions.is_empty_in(subst::FnSpace));
773 self.add_constraints_from_substs(
775 generics.types.get_slice(subst::TypeSpace),
776 generics.regions.get_slice(subst::TypeSpace),
781 ty::ty_trait(box ty::TyTrait { def_id, ref substs, .. }) => {
782 let trait_def = ty::lookup_trait_def(self.tcx(), def_id);
783 let generics = &trait_def.generics;
785 // Traits DO have a Self type parameter, but it is
786 // erased from object types.
787 assert!(!generics.types.is_empty_in(subst::SelfSpace) &&
788 substs.types.is_empty_in(subst::SelfSpace));
790 // Traits never declare region parameters in the self
792 assert!(generics.regions.is_empty_in(subst::SelfSpace));
794 // Traits never declare type/region parameters in the
796 assert!(generics.types.is_empty_in(subst::FnSpace));
797 assert!(generics.regions.is_empty_in(subst::FnSpace));
799 self.add_constraints_from_substs(
801 generics.types.get_slice(subst::TypeSpace),
802 generics.regions.get_slice(subst::TypeSpace),
807 ty::ty_param(ty::ParamTy { ref def_id, .. }) => {
808 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
809 match self.terms_cx.inferred_map.find(&def_id.node) {
811 self.add_constraint(index, variance);
814 // We do not infer variance for type parameters
815 // declared on methods. They will not be present
816 // in the inferred_map.
821 ty::ty_bare_fn(ty::BareFnTy { ref sig, .. }) |
822 ty::ty_closure(box ty::ClosureTy {
824 store: ty::UniqTraitStore,
827 self.add_constraints_from_sig(sig, variance);
830 ty::ty_closure(box ty::ClosureTy { ref sig,
831 store: ty::RegionTraitStore(region, _), .. }) => {
832 let contra = self.contravariant(variance);
833 self.add_constraints_from_region(region, contra);
834 self.add_constraints_from_sig(sig, variance);
837 ty::ty_infer(..) | ty::ty_err => {
839 format!("unexpected type encountered in \
840 variance inference: {}",
841 ty.repr(self.tcx())).as_slice());
847 /// Adds constraints appropriate for a nominal type (enum, struct,
848 /// object, etc) appearing in a context with ambient variance `variance`
849 fn add_constraints_from_substs(&mut self,
851 type_param_defs: &[ty::TypeParameterDef],
852 region_param_defs: &[ty::RegionParameterDef],
853 substs: &subst::Substs,
854 variance: VarianceTermPtr<'a>) {
855 debug!("add_constraints_from_substs(def_id={})", def_id);
857 for p in type_param_defs.iter() {
859 self.declared_variance(p.def_id, def_id, TypeParam,
861 let variance_i = self.xform(variance, variance_decl);
862 let substs_ty = *substs.types.get(p.space, p.index);
863 self.add_constraints_from_ty(substs_ty, variance_i);
866 for p in region_param_defs.iter() {
868 self.declared_variance(p.def_id, def_id,
869 RegionParam, p.space, p.index);
870 let variance_i = self.xform(variance, variance_decl);
871 let substs_r = *substs.regions().get(p.space, p.index);
872 self.add_constraints_from_region(substs_r, variance_i);
876 /// Adds constraints appropriate for a function with signature
877 /// `sig` appearing in a context with ambient variance `variance`
878 fn add_constraints_from_sig(&mut self,
880 variance: VarianceTermPtr<'a>) {
881 let contra = self.contravariant(variance);
882 for &input in sig.inputs.iter() {
883 self.add_constraints_from_ty(input, contra);
885 if let ty::FnConverging(result_type) = sig.output {
886 self.add_constraints_from_ty(result_type, variance);
890 /// Adds constraints appropriate for a region appearing in a
891 /// context with ambient variance `variance`
892 fn add_constraints_from_region(&mut self,
894 variance: VarianceTermPtr<'a>) {
896 ty::ReEarlyBound(param_id, _, _, _) => {
897 if self.is_to_be_inferred(param_id) {
898 let index = self.inferred_index(param_id);
899 self.add_constraint(index, variance);
905 ty::ReLateBound(..) => {
906 // We do not infer variance for region parameters on
907 // methods or in fn types.
910 ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) |
912 // We don't expect to see anything but 'static or bound
913 // regions when visiting member types or method types.
916 .bug(format!("unexpected region encountered in variance \
918 region.repr(self.tcx())).as_slice());
923 /// Adds constraints appropriate for a mutability-type pair
924 /// appearing in a context with ambient variance `variance`
925 fn add_constraints_from_mt(&mut self,
927 variance: VarianceTermPtr<'a>) {
930 let invar = self.invariant(variance);
931 self.add_constraints_from_ty(mt.ty, invar);
934 ast::MutImmutable => {
935 self.add_constraints_from_ty(mt.ty, variance);
941 /**************************************************************************
944 * The final phase iterates over the constraints, refining the variance
945 * for each inferred until a fixed point is reached. This will be the
946 * optimal solution to the constraints. The final variance for each
947 * inferred is then written into the `variance_map` in the tcx.
950 struct SolveContext<'a, 'tcx: 'a> {
951 terms_cx: TermsContext<'a, 'tcx>,
952 constraints: Vec<Constraint<'a>> ,
954 // Maps from an InferredIndex to the inferred value for that variable.
955 solutions: Vec<ty::Variance> }
957 fn solve_constraints(constraints_cx: ConstraintContext) {
958 let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
959 let solutions = Vec::from_elem(terms_cx.num_inferred(), ty::Bivariant);
960 let mut solutions_cx = SolveContext {
962 constraints: constraints,
965 solutions_cx.solve();
966 solutions_cx.write();
969 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
970 fn solve(&mut self) {
971 // Propagate constraints until a fixed point is reached. Note
972 // that the maximum number of iterations is 2C where C is the
973 // number of constraints (each variable can change values at most
974 // twice). Since number of constraints is linear in size of the
975 // input, so is the inference process.
976 let mut changed = true;
980 for constraint in self.constraints.iter() {
981 let Constraint { inferred, variance: term } = *constraint;
982 let InferredIndex(inferred) = inferred;
983 let variance = self.evaluate(term);
984 let old_value = self.solutions[inferred];
985 let new_value = glb(variance, old_value);
986 if old_value != new_value {
987 debug!("Updating inferred {} (node {}) \
988 from {} to {} due to {}",
991 .inferred_infos[inferred]
997 *self.solutions.get_mut(inferred) = new_value;
1005 // Collect all the variances for a particular item and stick
1006 // them into the variance map. We rely on the fact that we
1007 // generate all the inferreds for a particular item
1008 // consecutively (that is, we collect solutions for an item
1009 // until we see a new item id, and we assume (1) the solutions
1010 // are in the same order as the type parameters were declared
1011 // and (2) all solutions or a given item appear before a new
1014 let tcx = self.terms_cx.tcx;
1015 let solutions = &self.solutions;
1016 let inferred_infos = &self.terms_cx.inferred_infos;
1018 let num_inferred = self.terms_cx.num_inferred();
1019 while index < num_inferred {
1020 let item_id = inferred_infos[index].item_id;
1021 let mut types = VecPerParamSpace::empty();
1022 let mut regions = VecPerParamSpace::empty();
1024 while index < num_inferred &&
1025 inferred_infos[index].item_id == item_id {
1026 let info = inferred_infos[index];
1027 let variance = solutions[index];
1028 debug!("Index {} Info {} / {} / {} Variance {}",
1029 index, info.index, info.kind, info.space, variance);
1032 types.push(info.space, variance);
1035 regions.push(info.space, variance);
1041 let item_variances = ty::ItemVariances {
1045 debug!("item_id={} item_variances={}",
1047 item_variances.repr(tcx));
1049 let item_def_id = ast_util::local_def(item_id);
1051 // For unit testing: check for a special "rustc_variance"
1052 // attribute and report an error with various results if found.
1053 if ty::has_attr(tcx, item_def_id, "rustc_variance") {
1054 let found = item_variances.repr(tcx);
1055 tcx.sess.span_err(tcx.map.span(item_id), found.as_slice());
1058 let newly_added = tcx.item_variance_map.borrow_mut()
1059 .insert(item_def_id, Rc::new(item_variances));
1060 assert!(newly_added);
1064 fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
1066 ConstantTerm(v) => {
1070 TransformTerm(t1, t2) => {
1071 let v1 = self.evaluate(t1);
1072 let v2 = self.evaluate(t2);
1076 InferredTerm(InferredIndex(index)) => {
1077 self.solutions[index]
1083 /**************************************************************************
1084 * Miscellany transformations on variance
1088 fn xform(self, v: Self) -> Self;
1091 impl Xform for ty::Variance {
1092 fn xform(self, v: ty::Variance) -> ty::Variance {
1093 // "Variance transformation", Figure 1 of The Paper
1095 // Figure 1, column 1.
1096 (ty::Covariant, ty::Covariant) => ty::Covariant,
1097 (ty::Covariant, ty::Contravariant) => ty::Contravariant,
1098 (ty::Covariant, ty::Invariant) => ty::Invariant,
1099 (ty::Covariant, ty::Bivariant) => ty::Bivariant,
1101 // Figure 1, column 2.
1102 (ty::Contravariant, ty::Covariant) => ty::Contravariant,
1103 (ty::Contravariant, ty::Contravariant) => ty::Covariant,
1104 (ty::Contravariant, ty::Invariant) => ty::Invariant,
1105 (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
1107 // Figure 1, column 3.
1108 (ty::Invariant, _) => ty::Invariant,
1110 // Figure 1, column 4.
1111 (ty::Bivariant, _) => ty::Bivariant,
1116 fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance {
1117 // Greatest lower bound of the variance lattice as
1118 // defined in The Paper:
1124 (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
1126 (ty::Covariant, ty::Contravariant) => ty::Invariant,
1127 (ty::Contravariant, ty::Covariant) => ty::Invariant,
1129 (ty::Covariant, ty::Covariant) => ty::Covariant,
1131 (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
1133 (x, ty::Bivariant) | (ty::Bivariant, x) => x,