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>;
235 struct InferredIndex(uint);
237 enum VarianceTerm<'a> {
238 ConstantTerm(ty::Variance),
239 TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
240 InferredTerm(InferredIndex),
243 impl<'a> fmt::Show for VarianceTerm<'a> {
244 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
246 ConstantTerm(c1) => write!(f, "{}", c1),
247 TransformTerm(v1, v2) => write!(f, "({} \u00D7 {})", v1, v2),
248 InferredTerm(id) => write!(f, "[{}]", { let InferredIndex(i) = id; i })
253 /**************************************************************************
254 * The first pass over the crate simply builds up the set of inferreds.
257 struct TermsContext<'a, 'tcx: 'a> {
258 tcx: &'a ty::ctxt<'tcx>,
261 empty_variances: Rc<ty::ItemVariances>,
263 // Maps from the node id of a type/generic parameter to the
264 // corresponding inferred index.
265 inferred_map: HashMap<ast::NodeId, InferredIndex>,
267 // Maps from an InferredIndex to the info for that variable.
268 inferred_infos: Vec<InferredInfo<'a>> ,
271 #[deriving(Show, PartialEq)]
277 struct InferredInfo<'a> {
278 item_id: ast::NodeId,
282 param_id: ast::NodeId,
283 term: VarianceTermPtr<'a>,
286 fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
287 arena: &'a mut Arena,
289 -> TermsContext<'a, 'tcx> {
290 let mut terms_cx = TermsContext {
293 inferred_map: HashMap::new(),
294 inferred_infos: Vec::new(),
296 // cache and share the variance struct used for items with
297 // no type/region parameters
298 empty_variances: Rc::new(ty::ItemVariances {
299 types: VecPerParamSpace::empty(),
300 regions: VecPerParamSpace::empty()
304 visit::walk_crate(&mut terms_cx, krate);
309 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
310 fn add_inferred(&mut self,
311 item_id: ast::NodeId,
315 param_id: ast::NodeId) {
316 let inf_index = InferredIndex(self.inferred_infos.len());
317 let term = self.arena.alloc(|| InferredTerm(inf_index));
318 self.inferred_infos.push(InferredInfo { item_id: item_id,
324 let newly_added = self.inferred_map.insert(param_id, inf_index);
325 assert!(newly_added);
327 debug!("add_inferred(item_id={}, \
332 item_id, kind, index, param_id, inf_index);
335 fn num_inferred(&self) -> uint {
336 self.inferred_infos.len()
340 impl<'a, 'tcx, 'v> Visitor<'v> for TermsContext<'a, 'tcx> {
341 fn visit_item(&mut self, item: &ast::Item) {
342 debug!("add_inferreds for item {}", item.repr(self.tcx));
344 let inferreds_on_entry = self.num_inferred();
346 // NB: In the code below for writing the results back into the
347 // tcx, we rely on the fact that all inferreds for a particular
348 // item are assigned continuous indices.
350 ast::ItemTrait(..) => {
351 self.add_inferred(item.id, TypeParam, SelfSpace, 0, item.id);
357 ast::ItemEnum(_, ref generics) |
358 ast::ItemStruct(_, ref generics) |
359 ast::ItemTrait(ref generics, _, _, _) => {
360 for (i, p) in generics.lifetimes.iter().enumerate() {
361 let id = p.lifetime.id;
362 self.add_inferred(item.id, RegionParam, TypeSpace, i, id);
364 for (i, p) in generics.ty_params.iter().enumerate() {
365 self.add_inferred(item.id, TypeParam, TypeSpace, i, p.id);
368 // If this item has no type or lifetime parameters,
369 // then there are no variances to infer, so just
370 // insert an empty entry into the variance map.
371 // Arguably we could just leave the map empty in this
372 // case but it seems cleaner to be able to distinguish
373 // "invalid item id" from "item id with no
375 if self.num_inferred() == inferreds_on_entry {
376 let newly_added = self.tcx.item_variance_map.borrow_mut().insert(
377 ast_util::local_def(item.id),
378 self.empty_variances.clone());
379 assert!(newly_added);
382 visit::walk_item(self, item);
386 ast::ItemStatic(..) |
390 ast::ItemForeignMod(..) |
392 ast::ItemMac(..) => {
393 visit::walk_item(self, item);
399 /**************************************************************************
400 * Constraint construction and representation
402 * The second pass over the AST determines the set of constraints.
403 * We walk the set of items and, for each member, generate new constraints.
406 struct ConstraintContext<'a, 'tcx: 'a> {
407 terms_cx: TermsContext<'a, 'tcx>,
409 // These are the def-id of the std::kinds::marker::InvariantType,
410 // std::kinds::marker::InvariantLifetime, and so on. The arrays
411 // are indexed by the `ParamKind` (type, lifetime, self). Note
412 // that there are no marker types for self, so the entries for
413 // self are always None.
414 invariant_lang_items: [Option<ast::DefId>, ..2],
415 covariant_lang_items: [Option<ast::DefId>, ..2],
416 contravariant_lang_items: [Option<ast::DefId>, ..2],
417 unsafe_lang_item: Option<ast::DefId>,
419 // These are pointers to common `ConstantTerm` instances
420 covariant: VarianceTermPtr<'a>,
421 contravariant: VarianceTermPtr<'a>,
422 invariant: VarianceTermPtr<'a>,
423 bivariant: VarianceTermPtr<'a>,
425 constraints: Vec<Constraint<'a>> ,
428 /// Declares that the variable `decl_id` appears in a location with
429 /// variance `variance`.
430 struct Constraint<'a> {
431 inferred: InferredIndex,
432 variance: &'a VarianceTerm<'a>,
435 fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>,
437 -> ConstraintContext<'a, 'tcx> {
438 let mut invariant_lang_items = [None, ..2];
439 let mut covariant_lang_items = [None, ..2];
440 let mut contravariant_lang_items = [None, ..2];
442 covariant_lang_items[TypeParam as uint] =
443 terms_cx.tcx.lang_items.covariant_type();
444 covariant_lang_items[RegionParam as uint] =
445 terms_cx.tcx.lang_items.covariant_lifetime();
447 contravariant_lang_items[TypeParam as uint] =
448 terms_cx.tcx.lang_items.contravariant_type();
449 contravariant_lang_items[RegionParam as uint] =
450 terms_cx.tcx.lang_items.contravariant_lifetime();
452 invariant_lang_items[TypeParam as uint] =
453 terms_cx.tcx.lang_items.invariant_type();
454 invariant_lang_items[RegionParam as uint] =
455 terms_cx.tcx.lang_items.invariant_lifetime();
457 let unsafe_lang_item = terms_cx.tcx.lang_items.unsafe_type();
459 let covariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Covariant));
460 let contravariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Contravariant));
461 let invariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Invariant));
462 let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
463 let mut constraint_cx = ConstraintContext {
466 invariant_lang_items: invariant_lang_items,
467 covariant_lang_items: covariant_lang_items,
468 contravariant_lang_items: contravariant_lang_items,
469 unsafe_lang_item: unsafe_lang_item,
471 covariant: covariant,
472 contravariant: contravariant,
473 invariant: invariant,
474 bivariant: bivariant,
475 constraints: Vec::new(),
477 visit::walk_crate(&mut constraint_cx, krate);
481 impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> {
482 fn visit_item(&mut self, item: &ast::Item) {
483 let did = ast_util::local_def(item.id);
484 let tcx = self.terms_cx.tcx;
487 ast::ItemEnum(ref enum_definition, _) => {
488 // Hack: If we directly call `ty::enum_variants`, it
489 // annoyingly takes it upon itself to run off and
490 // evaluate the discriminants eagerly (*grumpy* that's
491 // not the typical pattern). This results in double
492 // error messages because typeck goes off and does
493 // this at a later time. All we really care about is
494 // the types of the variant arguments, so we just call
495 // `ty::VariantInfo::from_ast_variant()` ourselves
496 // here, mainly so as to mask the differences between
497 // struct-like enums and so forth.
498 for ast_variant in enum_definition.variants.iter() {
500 ty::VariantInfo::from_ast_variant(tcx,
503 for arg_ty in variant.args.iter() {
504 self.add_constraints_from_ty(*arg_ty, self.covariant);
509 ast::ItemStruct(..) => {
510 let struct_fields = ty::lookup_struct_fields(tcx, did);
511 for field_info in struct_fields.iter() {
512 assert_eq!(field_info.id.krate, ast::LOCAL_CRATE);
513 let field_ty = ty::node_id_to_type(tcx, field_info.id.node);
514 self.add_constraints_from_ty(field_ty, self.covariant);
518 ast::ItemTrait(..) => {
519 let trait_items = ty::trait_items(tcx, did);
520 for trait_item in trait_items.iter() {
522 ty::MethodTraitItem(ref method) => {
523 self.add_constraints_from_sig(&method.fty.sig,
526 ty::TypeTraitItem(_) => {}
531 ast::ItemStatic(..) |
535 ast::ItemForeignMod(..) |
538 ast::ItemMac(..) => {
539 visit::walk_item(self, item);
545 /// Is `param_id` a lifetime according to `map`?
546 fn is_lifetime(map: &ast_map::Map, param_id: ast::NodeId) -> bool {
547 match map.find(param_id) {
548 Some(ast_map::NodeLifetime(..)) => true, _ => false
552 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
553 fn tcx(&self) -> &'a ty::ctxt<'tcx> {
557 fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
558 match self.terms_cx.inferred_map.find(¶m_id) {
559 Some(&index) => index,
561 self.tcx().sess.bug(format!(
562 "no inferred index entry for {}",
563 self.tcx().map.node_to_string(param_id)).as_slice());
568 fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
569 let tcx = self.terms_cx.tcx;
570 assert!(is_lifetime(&tcx.map, param_id));
571 match tcx.named_region_map.find(¶m_id) {
572 Some(&rl::DefEarlyBoundRegion(_, _, lifetime_decl_id))
574 Some(_) => fail!("should not encounter non early-bound cases"),
576 // The lookup should only fail when `param_id` is
577 // itself a lifetime binding: use it as the decl_id.
583 /// Is `param_id` a type parameter for which we infer variance?
584 fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
585 let result = self.terms_cx.inferred_map.contains_key(¶m_id);
587 // To safe-guard against invalid inferred_map constructions,
588 // double-check if variance is inferred at some use of a type
589 // parameter (by inspecting parent of its binding declaration
590 // to see if it is introduced by a type or by a fn/impl).
592 let check_result = |this:&ConstraintContext| -> bool {
593 let tcx = this.terms_cx.tcx;
594 let decl_id = this.find_binding_for_lifetime(param_id);
595 // Currently only called on lifetimes; double-checking that.
596 assert!(is_lifetime(&tcx.map, param_id));
597 let parent_id = tcx.map.get_parent(decl_id);
598 let parent = tcx.map.find(parent_id).unwrap_or_else(
599 || fail!("tcx.map missing entry for id: {}", parent_id));
602 macro_rules! cannot_happen { () => { {
603 fail!("invalid parent: {:s} for {:s}",
604 tcx.map.node_to_string(parent_id),
605 tcx.map.node_to_string(param_id));
609 ast_map::NodeItem(p) => {
613 ast::ItemStruct(..) |
614 ast::ItemTrait(..) => is_inferred = true,
615 ast::ItemFn(..) => is_inferred = false,
616 _ => cannot_happen!(),
619 ast_map::NodeTraitItem(..) => is_inferred = false,
620 ast_map::NodeImplItem(..) => is_inferred = false,
621 _ => cannot_happen!(),
627 assert_eq!(result, check_result(self));
632 fn declared_variance(&self,
633 param_def_id: ast::DefId,
634 item_def_id: ast::DefId,
638 -> VarianceTermPtr<'a> {
640 * Returns a variance term representing the declared variance of
641 * the type/region parameter with the given id.
644 assert_eq!(param_def_id.krate, item_def_id.krate);
646 if self.invariant_lang_items[kind as uint] == Some(item_def_id) {
648 } else if self.covariant_lang_items[kind as uint] == Some(item_def_id) {
650 } else if self.contravariant_lang_items[kind as uint] == Some(item_def_id) {
652 } else if kind == TypeParam && Some(item_def_id) == self.unsafe_lang_item {
654 } else if param_def_id.krate == ast::LOCAL_CRATE {
655 // Parameter on an item defined within current crate:
656 // variance not yet inferred, so return a symbolic
658 let InferredIndex(index) = self.inferred_index(param_def_id.node);
659 self.terms_cx.inferred_infos.get(index).term
661 // Parameter on an item defined within another crate:
662 // variance already inferred, just look it up.
663 let variances = ty::item_variances(self.tcx(), item_def_id);
664 let variance = match kind {
665 TypeParam => *variances.types.get(space, index),
666 RegionParam => *variances.regions.get(space, index),
668 self.constant_term(variance)
672 fn add_constraint(&mut self,
673 InferredIndex(index): InferredIndex,
674 variance: VarianceTermPtr<'a>) {
675 debug!("add_constraint(index={}, variance={})",
676 index, variance.to_string());
677 self.constraints.push(Constraint { inferred: InferredIndex(index),
678 variance: variance });
681 fn contravariant(&mut self,
682 variance: VarianceTermPtr<'a>)
683 -> VarianceTermPtr<'a> {
684 self.xform(variance, self.contravariant)
687 fn invariant(&mut self,
688 variance: VarianceTermPtr<'a>)
689 -> VarianceTermPtr<'a> {
690 self.xform(variance, self.invariant)
693 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
695 ty::Covariant => self.covariant,
696 ty::Invariant => self.invariant,
697 ty::Contravariant => self.contravariant,
698 ty::Bivariant => self.bivariant,
703 v1: VarianceTermPtr<'a>,
704 v2: VarianceTermPtr<'a>)
705 -> VarianceTermPtr<'a> {
707 (_, ConstantTerm(ty::Covariant)) => {
708 // Applying a "covariant" transform is always a no-op
712 (ConstantTerm(c1), ConstantTerm(c2)) => {
713 self.constant_term(c1.xform(c2))
717 self.terms_cx.arena.alloc(|| TransformTerm(v1, v2))
722 /// Adds constraints appropriate for an instance of `ty` appearing
723 /// in a context with ambient variance `variance`
724 fn add_constraints_from_ty(&mut self,
726 variance: VarianceTermPtr<'a>) {
727 debug!("add_constraints_from_ty(ty={})", ty.repr(self.tcx()));
729 match ty::get(ty).sty {
730 ty::ty_nil | ty::ty_bot | ty::ty_bool |
731 ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) |
732 ty::ty_float(_) | ty::ty_str => {
733 /* leaf type -- noop */
736 ty::ty_unboxed_closure(_, region) => {
737 let contra = self.contravariant(variance);
738 self.add_constraints_from_region(region, contra);
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 { def_id: 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 self.add_constraints_from_ty(sig.output, variance);
888 /// Adds constraints appropriate for a region appearing in a
889 /// context with ambient variance `variance`
890 fn add_constraints_from_region(&mut self,
892 variance: VarianceTermPtr<'a>) {
894 ty::ReEarlyBound(param_id, _, _, _) => {
895 if self.is_to_be_inferred(param_id) {
896 let index = self.inferred_index(param_id);
897 self.add_constraint(index, variance);
903 ty::ReLateBound(..) => {
904 // We do not infer variance for region parameters on
905 // methods or in fn types.
908 ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) |
910 // We don't expect to see anything but 'static or bound
911 // regions when visiting member types or method types.
914 .bug(format!("unexpected region encountered in variance \
916 region.repr(self.tcx())).as_slice());
921 /// Adds constraints appropriate for a mutability-type pair
922 /// appearing in a context with ambient variance `variance`
923 fn add_constraints_from_mt(&mut self,
925 variance: VarianceTermPtr<'a>) {
928 let invar = self.invariant(variance);
929 self.add_constraints_from_ty(mt.ty, invar);
932 ast::MutImmutable => {
933 self.add_constraints_from_ty(mt.ty, variance);
939 /**************************************************************************
942 * The final phase iterates over the constraints, refining the variance
943 * for each inferred until a fixed point is reached. This will be the
944 * optimal solution to the constraints. The final variance for each
945 * inferred is then written into the `variance_map` in the tcx.
948 struct SolveContext<'a, 'tcx: 'a> {
949 terms_cx: TermsContext<'a, 'tcx>,
950 constraints: Vec<Constraint<'a>> ,
952 // Maps from an InferredIndex to the inferred value for that variable.
953 solutions: Vec<ty::Variance> }
955 fn solve_constraints(constraints_cx: ConstraintContext) {
956 let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
957 let solutions = Vec::from_elem(terms_cx.num_inferred(), ty::Bivariant);
958 let mut solutions_cx = SolveContext {
960 constraints: constraints,
963 solutions_cx.solve();
964 solutions_cx.write();
967 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
968 fn solve(&mut self) {
969 // Propagate constraints until a fixed point is reached. Note
970 // that the maximum number of iterations is 2C where C is the
971 // number of constraints (each variable can change values at most
972 // twice). Since number of constraints is linear in size of the
973 // input, so is the inference process.
974 let mut changed = true;
978 for constraint in self.constraints.iter() {
979 let Constraint { inferred, variance: term } = *constraint;
980 let InferredIndex(inferred) = inferred;
981 let variance = self.evaluate(term);
982 let old_value = *self.solutions.get(inferred);
983 let new_value = glb(variance, old_value);
984 if old_value != new_value {
985 debug!("Updating inferred {} (node {}) \
986 from {} to {} due to {}",
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.get(index).item_id;
1020 let mut types = VecPerParamSpace::empty();
1021 let mut regions = VecPerParamSpace::empty();
1023 while index < num_inferred &&
1024 inferred_infos.get(index).item_id == item_id {
1025 let info = inferred_infos.get(index);
1026 let variance = *solutions.get(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.get(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,