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 (or should
82 be -- FIXME #5781). To set the 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 collections::HashMap;
202 use syntax::ast_util;
205 use syntax::visit::Visitor;
206 use util::ppaux::Repr;
208 pub fn infer_variance(tcx: ty::ctxt,
209 krate: &ast::Crate) {
210 let mut arena = arena::Arena::new();
211 let terms_cx = determine_parameters_to_be_inferred(tcx, &mut arena, krate);
212 let constraints_cx = add_constraints_from_crate(terms_cx, krate);
213 solve_constraints(constraints_cx);
216 /**************************************************************************
219 * Terms are structured as a straightforward tree. Rather than rely on
220 * GC, we allocate terms out of a bounded arena (the lifetime of this
221 * arena is the lifetime 'a that is threaded around).
223 * We assign a unique index to each type/region parameter whose variance
224 * is to be inferred. We refer to such variables as "inferreds". An
225 * `InferredIndex` is a newtype'd int representing the index of such
229 type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
231 struct InferredIndex(uint);
233 enum VarianceTerm<'a> {
234 ConstantTerm(ty::Variance),
235 TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
236 InferredTerm(InferredIndex),
239 impl<'a> fmt::Show for VarianceTerm<'a> {
240 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
242 ConstantTerm(c1) => write!(f.buf, "{}", c1),
243 TransformTerm(v1, v2) => write!(f.buf, "({} \u00D7 {})", v1, v2),
244 InferredTerm(id) => write!(f.buf, "[{}]", { let InferredIndex(i) = id; i })
249 /**************************************************************************
250 * The first pass over the crate simply builds up the set of inferreds.
253 struct TermsContext<'a> {
257 empty_variances: @ty::ItemVariances,
259 // Maps from the node id of a type/generic parameter to the
260 // corresponding inferred index.
261 inferred_map: HashMap<ast::NodeId, InferredIndex>,
263 // Maps from an InferredIndex to the info for that variable.
264 inferred_infos: ~[InferredInfo<'a>],
267 enum ParamKind { TypeParam, RegionParam, SelfParam }
269 struct InferredInfo<'a> {
270 item_id: ast::NodeId,
273 param_id: ast::NodeId,
274 term: VarianceTermPtr<'a>,
277 fn determine_parameters_to_be_inferred<'a>(tcx: ty::ctxt,
278 arena: &'a mut Arena,
280 -> TermsContext<'a> {
281 let mut terms_cx = TermsContext {
284 inferred_map: HashMap::new(),
287 // cache and share the variance struct used for items with
288 // no type/region parameters
289 empty_variances: @ty::ItemVariances { self_param: None,
290 type_params: opt_vec::Empty,
291 region_params: opt_vec::Empty }
294 visit::walk_crate(&mut terms_cx, krate, ());
299 impl<'a> TermsContext<'a> {
300 fn add_inferred(&mut self,
301 item_id: ast::NodeId,
304 param_id: ast::NodeId) {
305 let inf_index = InferredIndex(self.inferred_infos.len());
306 let term = self.arena.alloc(|| InferredTerm(inf_index));
307 self.inferred_infos.push(InferredInfo { item_id: item_id,
312 let newly_added = self.inferred_map.insert(param_id, inf_index);
313 assert!(newly_added);
315 debug!("add_inferred(item_id={}, \
320 item_id, kind, index, param_id, inf_index);
323 fn num_inferred(&self) -> uint {
324 self.inferred_infos.len()
328 impl<'a> Visitor<()> for TermsContext<'a> {
329 fn visit_item(&mut self, item: &ast::Item, _: ()) {
330 debug!("add_inferreds for item {}", item.repr(self.tcx));
332 let inferreds_on_entry = self.num_inferred();
334 // NB: In the code below for writing the results back into the
335 // tcx, we rely on the fact that all inferreds for a particular
336 // item are assigned continuous indices.
338 ast::ItemTrait(..) => {
339 self.add_inferred(item.id, SelfParam, 0, item.id);
345 ast::ItemEnum(_, ref generics) |
346 ast::ItemStruct(_, ref generics) |
347 ast::ItemTrait(ref generics, _, _) => {
348 for (i, p) in generics.lifetimes.iter().enumerate() {
349 self.add_inferred(item.id, RegionParam, i, p.id);
351 for (i, p) in generics.ty_params.iter().enumerate() {
352 self.add_inferred(item.id, TypeParam, i, p.id);
355 // If this item has no type or lifetime parameters,
356 // then there are no variances to infer, so just
357 // insert an empty entry into the variance map.
358 // Arguably we could just leave the map empty in this
359 // case but it seems cleaner to be able to distinguish
360 // "invalid item id" from "item id with no
362 if self.num_inferred() == inferreds_on_entry {
363 let mut item_variance_map = self.tcx
366 let newly_added = item_variance_map.get().insert(
367 ast_util::local_def(item.id),
368 self.empty_variances);
369 assert!(newly_added);
372 visit::walk_item(self, item, ());
376 ast::ItemStatic(..) |
379 ast::ItemForeignMod(..) |
381 ast::ItemMac(..) => {
382 visit::walk_item(self, item, ());
388 /**************************************************************************
389 * Constraint construction and representation
391 * The second pass over the AST determines the set of constraints.
392 * We walk the set of items and, for each member, generate new constraints.
395 struct ConstraintContext<'a> {
396 terms_cx: TermsContext<'a>,
398 // These are the def-id of the std::kinds::marker::InvariantType,
399 // std::kinds::marker::InvariantLifetime, and so on. The arrays
400 // are indexed by the `ParamKind` (type, lifetime, self). Note
401 // that there are no marker types for self, so the entries for
402 // self are always None.
403 invariant_lang_items: [Option<ast::DefId>, ..3],
404 covariant_lang_items: [Option<ast::DefId>, ..3],
405 contravariant_lang_items: [Option<ast::DefId>, ..3],
407 // These are pointers to common `ConstantTerm` instances
408 covariant: VarianceTermPtr<'a>,
409 contravariant: VarianceTermPtr<'a>,
410 invariant: VarianceTermPtr<'a>,
411 bivariant: VarianceTermPtr<'a>,
413 constraints: ~[Constraint<'a>],
416 /// Declares that the variable `decl_id` appears in a location with
417 /// variance `variance`.
418 struct Constraint<'a> {
419 inferred: InferredIndex,
420 variance: &'a VarianceTerm<'a>,
423 fn add_constraints_from_crate<'a>(terms_cx: TermsContext<'a>,
425 -> ConstraintContext<'a> {
426 let mut invariant_lang_items = [None, ..3];
427 let mut covariant_lang_items = [None, ..3];
428 let mut contravariant_lang_items = [None, ..3];
430 covariant_lang_items[TypeParam as uint] =
431 terms_cx.tcx.lang_items.covariant_type();
432 covariant_lang_items[RegionParam as uint] =
433 terms_cx.tcx.lang_items.covariant_lifetime();
435 contravariant_lang_items[TypeParam as uint] =
436 terms_cx.tcx.lang_items.contravariant_type();
437 contravariant_lang_items[RegionParam as uint] =
438 terms_cx.tcx.lang_items.contravariant_lifetime();
440 invariant_lang_items[TypeParam as uint] =
441 terms_cx.tcx.lang_items.invariant_type();
442 invariant_lang_items[RegionParam as uint] =
443 terms_cx.tcx.lang_items.invariant_lifetime();
445 let covariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Covariant));
446 let contravariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Contravariant));
447 let invariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Invariant));
448 let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
449 let mut constraint_cx = ConstraintContext {
452 invariant_lang_items: invariant_lang_items,
453 covariant_lang_items: covariant_lang_items,
454 contravariant_lang_items: contravariant_lang_items,
456 covariant: covariant,
457 contravariant: contravariant,
458 invariant: invariant,
459 bivariant: bivariant,
462 visit::walk_crate(&mut constraint_cx, krate, ());
466 impl<'a> Visitor<()> for ConstraintContext<'a> {
467 fn visit_item(&mut self, item: &ast::Item, _: ()) {
468 let did = ast_util::local_def(item.id);
469 let tcx = self.terms_cx.tcx;
472 ast::ItemEnum(ref enum_definition, _) => {
473 // Hack: If we directly call `ty::enum_variants`, it
474 // annoyingly takes it upon itself to run off and
475 // evaluate the discriminants eagerly (*grumpy* that's
476 // not the typical pattern). This results in double
477 // error messages because typeck goes off and does
478 // this at a later time. All we really care about is
479 // the types of the variant arguments, so we just call
480 // `ty::VariantInfo::from_ast_variant()` ourselves
481 // here, mainly so as to mask the differences between
482 // struct-like enums and so forth.
483 for &ast_variant in enum_definition.variants.iter() {
485 ty::VariantInfo::from_ast_variant(tcx,
488 for &arg_ty in variant.args.iter() {
489 self.add_constraints_from_ty(arg_ty, self.covariant);
494 ast::ItemStruct(..) => {
495 let struct_fields = ty::lookup_struct_fields(tcx, did);
496 for field_info in struct_fields.iter() {
497 assert_eq!(field_info.id.krate, ast::LOCAL_CRATE);
498 let field_ty = ty::node_id_to_type(tcx, field_info.id.node);
499 self.add_constraints_from_ty(field_ty, self.covariant);
503 ast::ItemTrait(..) => {
504 let methods = ty::trait_methods(tcx, did);
505 for method in methods.iter() {
506 self.add_constraints_from_sig(
507 &method.fty.sig, self.covariant);
511 ast::ItemStatic(..) |
514 ast::ItemForeignMod(..) |
517 ast::ItemMac(..) => {
518 visit::walk_item(self, item, ());
524 impl<'a> ConstraintContext<'a> {
525 fn tcx(&self) -> ty::ctxt {
529 fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
530 match self.terms_cx.inferred_map.find(¶m_id) {
531 Some(&index) => index,
533 self.tcx().sess.bug(format!(
534 "No inferred index entry for {}",
535 self.tcx().map.node_to_str(param_id)));
540 fn declared_variance(&self,
541 param_def_id: ast::DefId,
542 item_def_id: ast::DefId,
545 -> VarianceTermPtr<'a> {
547 * Returns a variance term representing the declared variance of
548 * the type/region parameter with the given id.
551 assert_eq!(param_def_id.krate, item_def_id.krate);
553 if self.invariant_lang_items[kind as uint] == Some(item_def_id) {
555 } else if self.covariant_lang_items[kind as uint] == Some(item_def_id) {
557 } else if self.contravariant_lang_items[kind as uint] == Some(item_def_id) {
559 } else if param_def_id.krate == ast::LOCAL_CRATE {
560 // Parameter on an item defined within current crate:
561 // variance not yet inferred, so return a symbolic
563 let InferredIndex(index) = self.inferred_index(param_def_id.node);
564 self.terms_cx.inferred_infos[index].term
566 // Parameter on an item defined within another crate:
567 // variance already inferred, just look it up.
568 let variances = ty::item_variances(self.tcx(), item_def_id);
569 let variance = match kind {
570 SelfParam => variances.self_param.unwrap(),
571 TypeParam => *variances.type_params.get(index),
572 RegionParam => *variances.region_params.get(index),
574 self.constant_term(variance)
578 fn add_constraint(&mut self,
579 InferredIndex(index): InferredIndex,
580 variance: VarianceTermPtr<'a>) {
581 debug!("add_constraint(index={}, variance={})",
582 index, variance.to_str());
583 self.constraints.push(Constraint { inferred: InferredIndex(index),
584 variance: variance });
587 fn contravariant(&mut self,
588 variance: VarianceTermPtr<'a>)
589 -> VarianceTermPtr<'a> {
590 self.xform(variance, self.contravariant)
593 fn invariant(&mut self,
594 variance: VarianceTermPtr<'a>)
595 -> VarianceTermPtr<'a> {
596 self.xform(variance, self.invariant)
599 fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
601 ty::Covariant => self.covariant,
602 ty::Invariant => self.invariant,
603 ty::Contravariant => self.contravariant,
604 ty::Bivariant => self.bivariant,
609 v1: VarianceTermPtr<'a>,
610 v2: VarianceTermPtr<'a>)
611 -> VarianceTermPtr<'a> {
613 (_, ConstantTerm(ty::Covariant)) => {
614 // Applying a "covariant" transform is always a no-op
618 (ConstantTerm(c1), ConstantTerm(c2)) => {
619 self.constant_term(c1.xform(c2))
623 self.terms_cx.arena.alloc(|| TransformTerm(v1, v2))
628 /// Adds constraints appropriate for an instance of `ty` appearing
629 /// in a context with ambient variance `variance`
630 fn add_constraints_from_ty(&mut self,
632 variance: VarianceTermPtr<'a>) {
633 debug!("add_constraints_from_ty(ty={})", ty.repr(self.tcx()));
635 match ty::get(ty).sty {
636 ty::ty_nil | ty::ty_bot | ty::ty_bool |
637 ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) |
639 /* leaf type -- noop */
642 ty::ty_rptr(region, ref mt) => {
643 let contra = self.contravariant(variance);
644 self.add_constraints_from_region(region, contra);
645 self.add_constraints_from_mt(mt, variance);
648 ty::ty_str(vstore) => {
649 self.add_constraints_from_vstore(vstore, variance);
652 ty::ty_vec(ref mt, vstore) => {
653 self.add_constraints_from_vstore(vstore, variance);
654 self.add_constraints_from_mt(mt, variance);
657 ty::ty_uniq(typ) | ty::ty_box(typ) => {
658 self.add_constraints_from_ty(typ, variance);
661 ty::ty_ptr(ref mt) => {
662 self.add_constraints_from_mt(mt, variance);
665 ty::ty_tup(ref subtys) => {
666 for &subty in subtys.iter() {
667 self.add_constraints_from_ty(subty, variance);
671 ty::ty_enum(def_id, ref substs) |
672 ty::ty_struct(def_id, ref substs) => {
673 let item_type = ty::lookup_item_type(self.tcx(), def_id);
674 self.add_constraints_from_substs(def_id, &item_type.generics,
678 ty::ty_trait(def_id, ref substs, _, _, _) => {
679 let trait_def = ty::lookup_trait_def(self.tcx(), def_id);
680 self.add_constraints_from_substs(def_id, &trait_def.generics,
684 ty::ty_param(ty::param_ty { def_id: ref def_id, .. }) => {
685 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
686 match self.terms_cx.inferred_map.find(&def_id.node) {
688 self.add_constraint(index, variance);
691 // We do not infer variance for type parameters
692 // declared on methods. They will not be present
693 // in the inferred_map.
698 ty::ty_self(ref def_id) => {
699 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
700 let index = self.inferred_index(def_id.node);
701 self.add_constraint(index, variance);
704 ty::ty_bare_fn(ty::BareFnTy { sig: ref sig, .. }) => {
705 self.add_constraints_from_sig(sig, variance);
708 ty::ty_closure(ty::ClosureTy { sig: ref sig, region, .. }) => {
709 let contra = self.contravariant(variance);
710 self.add_constraints_from_region(region, contra);
711 self.add_constraints_from_sig(sig, variance);
714 ty::ty_infer(..) | ty::ty_err | ty::ty_unboxed_vec(..) => {
716 format!("unexpected type encountered in \
717 variance inference: {}",
718 ty.repr(self.tcx())));
723 /// Adds constraints appropriate for a vector with vstore `vstore`
724 /// appearing in a context with ambient variance `variance`
725 fn add_constraints_from_vstore(&mut self,
727 variance: VarianceTermPtr<'a>) {
729 ty::vstore_slice(r) => {
730 let contra = self.contravariant(variance);
731 self.add_constraints_from_region(r, contra);
734 ty::vstore_fixed(_) | ty::vstore_uniq => {
739 /// Adds constraints appropriate for a nominal type (enum, struct,
740 /// object, etc) appearing in a context with ambient variance `variance`
741 fn add_constraints_from_substs(&mut self,
743 generics: &ty::Generics,
745 variance: VarianceTermPtr<'a>) {
746 debug!("add_constraints_from_substs(def_id={:?})", def_id);
748 for (i, p) in generics.type_param_defs().iter().enumerate() {
750 self.declared_variance(p.def_id, def_id, TypeParam, i);
751 let variance_i = self.xform(variance, variance_decl);
752 self.add_constraints_from_ty(substs.tps[i], variance_i);
755 match substs.regions {
756 ty::ErasedRegions => {}
757 ty::NonerasedRegions(ref rps) => {
758 for (i, p) in generics.region_param_defs().iter().enumerate() {
760 self.declared_variance(p.def_id, def_id, RegionParam, i);
761 let variance_i = self.xform(variance, variance_decl);
762 self.add_constraints_from_region(*rps.get(i), variance_i);
768 /// Adds constraints appropriate for a function with signature
769 /// `sig` appearing in a context with ambient variance `variance`
770 fn add_constraints_from_sig(&mut self,
772 variance: VarianceTermPtr<'a>) {
773 let contra = self.contravariant(variance);
774 for &input in sig.inputs.iter() {
775 self.add_constraints_from_ty(input, contra);
777 self.add_constraints_from_ty(sig.output, variance);
780 /// Adds constraints appropriate for a region appearing in a
781 /// context with ambient variance `variance`
782 fn add_constraints_from_region(&mut self,
784 variance: VarianceTermPtr<'a>) {
786 ty::ReEarlyBound(param_id, _, _) => {
787 let index = self.inferred_index(param_id);
788 self.add_constraint(index, variance);
793 ty::ReLateBound(..) => {
794 // We do not infer variance for region parameters on
795 // methods or in fn types.
798 ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) |
800 // We don't expect to see anything but 'static or bound
801 // regions when visiting member types or method types.
802 self.tcx().sess.bug(format!("unexpected region encountered in \
803 variance inference: {}",
804 region.repr(self.tcx())));
809 /// Adds constraints appropriate for a mutability-type pair
810 /// appearing in a context with ambient variance `variance`
811 fn add_constraints_from_mt(&mut self,
813 variance: VarianceTermPtr<'a>) {
816 let invar = self.invariant(variance);
817 self.add_constraints_from_ty(mt.ty, invar);
820 ast::MutImmutable => {
821 self.add_constraints_from_ty(mt.ty, variance);
827 /**************************************************************************
830 * The final phase iterates over the constraints, refining the variance
831 * for each inferred until a fixed point is reached. This will be the
832 * optimal solution to the constraints. The final variance for each
833 * inferred is then written into the `variance_map` in the tcx.
836 struct SolveContext<'a> {
837 terms_cx: TermsContext<'a>,
838 constraints: ~[Constraint<'a>],
840 // Maps from an InferredIndex to the inferred value for that variable.
841 solutions: ~[ty::Variance]
844 fn solve_constraints(constraints_cx: ConstraintContext) {
845 let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
846 let solutions = vec::from_elem(terms_cx.num_inferred(), ty::Bivariant);
847 let mut solutions_cx = SolveContext {
849 constraints: constraints,
852 solutions_cx.solve();
853 solutions_cx.write();
856 impl<'a> SolveContext<'a> {
857 fn solve(&mut self) {
858 // Propagate constraints until a fixed point is reached. Note
859 // that the maximum number of iterations is 2C where C is the
860 // number of constraints (each variable can change values at most
861 // twice). Since number of constraints is linear in size of the
862 // input, so is the inference process.
863 let mut changed = true;
867 for constraint in self.constraints.iter() {
868 let Constraint { inferred, variance: term } = *constraint;
869 let InferredIndex(inferred) = inferred;
870 let variance = self.evaluate(term);
871 let old_value = self.solutions[inferred];
872 let new_value = glb(variance, old_value);
873 if old_value != new_value {
874 debug!("Updating inferred {} (node {}) \
875 from {:?} to {:?} due to {}",
877 self.terms_cx.inferred_infos[inferred].param_id,
882 self.solutions[inferred] = new_value;
890 // Collect all the variances for a particular item and stick
891 // them into the variance map. We rely on the fact that we
892 // generate all the inferreds for a particular item
893 // consecutively (that is, we collect solutions for an item
894 // until we see a new item id, and we assume (1) the solutions
895 // are in the same order as the type parameters were declared
896 // and (2) all solutions or a given item appear before a new
899 let tcx = self.terms_cx.tcx;
900 let solutions = &self.solutions;
901 let inferred_infos = &self.terms_cx.inferred_infos;
903 let num_inferred = self.terms_cx.num_inferred();
904 while index < num_inferred {
905 let item_id = inferred_infos[index].item_id;
906 let mut item_variances = ty::ItemVariances {
908 type_params: opt_vec::Empty,
909 region_params: opt_vec::Empty
911 while index < num_inferred &&
912 inferred_infos[index].item_id == item_id {
913 let info = &inferred_infos[index];
916 assert!(item_variances.self_param.is_none());
917 item_variances.self_param = Some(solutions[index]);
920 item_variances.type_params.push(solutions[index]);
923 item_variances.region_params.push(solutions[index]);
929 debug!("item_id={} item_variances={}",
931 item_variances.repr(tcx));
933 let item_def_id = ast_util::local_def(item_id);
935 // For unit testing: check for a special "rustc_variance"
936 // attribute and report an error with various results if found.
937 if ty::has_attr(tcx, item_def_id, "rustc_variance") {
938 let found = item_variances.repr(tcx);
939 tcx.sess.span_err(tcx.map.span(item_id), found);
942 let mut item_variance_map = tcx.item_variance_map.borrow_mut();
943 let newly_added = item_variance_map.get().insert(item_def_id,
945 assert!(newly_added);
949 fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
955 TransformTerm(t1, t2) => {
956 let v1 = self.evaluate(t1);
957 let v2 = self.evaluate(t2);
961 InferredTerm(InferredIndex(index)) => {
962 self.solutions[index]
968 /**************************************************************************
969 * Miscellany transformations on variance
973 fn xform(self, v: Self) -> Self;
976 impl Xform for ty::Variance {
977 fn xform(self, v: ty::Variance) -> ty::Variance {
978 // "Variance transformation", Figure 1 of The Paper
980 // Figure 1, column 1.
981 (ty::Covariant, ty::Covariant) => ty::Covariant,
982 (ty::Covariant, ty::Contravariant) => ty::Contravariant,
983 (ty::Covariant, ty::Invariant) => ty::Invariant,
984 (ty::Covariant, ty::Bivariant) => ty::Bivariant,
986 // Figure 1, column 2.
987 (ty::Contravariant, ty::Covariant) => ty::Contravariant,
988 (ty::Contravariant, ty::Contravariant) => ty::Covariant,
989 (ty::Contravariant, ty::Invariant) => ty::Invariant,
990 (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
992 // Figure 1, column 3.
993 (ty::Invariant, _) => ty::Invariant,
995 // Figure 1, column 4.
996 (ty::Bivariant, _) => ty::Bivariant,
1001 fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance {
1002 // Greatest lower bound of the variance lattice as
1003 // defined in The Paper:
1009 (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
1011 (ty::Covariant, ty::Contravariant) => ty::Invariant,
1012 (ty::Contravariant, ty::Covariant) => ty::Invariant,
1014 (ty::Covariant, ty::Covariant) => ty::Covariant,
1016 (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
1018 (x, ty::Bivariant) | (ty::Bivariant, x) => x,