src/librustc_typeck/variance.rs

   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.
   4 //
   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.
  10
  11 //! This file infers the variance of type and lifetime parameters. The
  12 //! algorithm is taken from Section 4 of the paper "Taming the Wildcards:
  13 //! Combining Definition- and Use-Site Variance" published in PLDI'11 and
  14 //! written by Altidor et al., and hereafter referred to as The Paper.
  15 //!
  16 //! This inference is explicitly designed *not* to consider the uses of
  17 //! types within code. To determine the variance of type parameters
  18 //! defined on type `X`, we only consider the definition of the type `X`
  19 //! and the definitions of any types it references.
  20 //!
  21 //! We only infer variance for type parameters found on *types*: structs,
  22 //! enums, and traits. We do not infer variance for type parameters found
  23 //! on fns or impls. This is because those things are not type definitions
  24 //! and variance doesn't really make sense in that context.
  25 //!
  26 //! It is worth covering what variance means in each case. For structs and
  27 //! enums, I think it is fairly straightforward. The variance of the type
  28 //! or lifetime parameters defines whether `T<A>` is a subtype of `T<B>`
  29 //! (resp. `T<'a>` and `T<'b>`) based on the relationship of `A` and `B`
  30 //! (resp. `'a` and `'b`). (FIXME #3598 -- we do not currently make use of
  31 //! the variances we compute for type parameters.)
  32 //!
  33 //! ### Variance on traits
  34 //!
  35 //! The meaning of variance for trait parameters is more subtle and worth
  36 //! expanding upon. There are in fact two uses of the variance values we
  37 //! compute.
  38 //!
  39 //! #### Trait variance and object types
  40 //!
  41 //! The first is for object types. Just as with structs and enums, we can
  42 //! decide the subtyping relationship between two object types `&Trait<A>`
  43 //! and `&Trait<B>` based on the relationship of `A` and `B`. Note that
  44 //! for object types we ignore the `Self` type parameter -- it is unknown,
  45 //! and the nature of dynamic dispatch ensures that we will always call a
  46 //! function that is expected the appropriate `Self` type. However, we
  47 //! must be careful with the other type parameters, or else we could end
  48 //! up calling a function that is expecting one type but provided another.
  49 //!
  50 //! To see what I mean, consider a trait like so:
  51 //!
  52 //!     trait ConvertTo<A> {
  53 //!         fn convertTo(&self) -> A;
  54 //!     }
  55 //!
  56 //! Intuitively, If we had one object `O=&ConvertTo<Object>` and another
  57 //! `S=&ConvertTo<String>`, then `S <: O` because `String <: Object`
  58 //! (presuming Java-like "string" and "object" types, my go to examples
  59 //! for subtyping). The actual algorithm would be to compare the
  60 //! (explicit) type parameters pairwise respecting their variance: here,
  61 //! the type parameter A is covariant (it appears only in a return
  62 //! position), and hence we require that `String <: Object`.
  63 //!
  64 //! You'll note though that we did not consider the binding for the
  65 //! (implicit) `Self` type parameter: in fact, it is unknown, so that's
  66 //! good. The reason we can ignore that parameter is precisely because we
  67 //! don't need to know its value until a call occurs, and at that time (as
  68 //! you said) the dynamic nature of virtual dispatch means the code we run
  69 //! will be correct for whatever value `Self` happens to be bound to for
  70 //! the particular object whose method we called. `Self` is thus different
  71 //! from `A`, because the caller requires that `A` be known in order to
  72 //! know the return type of the method `convertTo()`. (As an aside, we
  73 //! have rules preventing methods where `Self` appears outside of the
  74 //! receiver position from being called via an object.)
  75 //!
  76 //! #### Trait variance and vtable resolution
  77 //!
  78 //! But traits aren't only used with objects. They're also used when
  79 //! deciding whether a given impl satisfies a given trait bound. To set the
  80 //! scene here, imagine I had a function:
  81 //!
  82 //!     fn convertAll<A,T:ConvertTo<A>>(v: &[T]) {
  83 //!         ...
  84 //!     }
  85 //!
  86 //! Now imagine that I have an implementation of `ConvertTo` for `Object`:
  87 //!
  88 //!     impl ConvertTo<int> for Object { ... }
  89 //!
  90 //! And I want to call `convertAll` on an array of strings. Suppose
  91 //! further that for whatever reason I specifically supply the value of
  92 //! `String` for the type parameter `T`:
  93 //!
  94 //!     let mut vector = ~["string", ...];
  95 //!     convertAll::<int, String>(v);
  96 //!
  97 //! Is this legal? To put another way, can we apply the `impl` for
  98 //! `Object` to the type `String`? The answer is yes, but to see why
  99 //! we have to expand out what will happen:
 100 //!
 101 //! - `convertAll` will create a pointer to one of the entries in the
 102 //!   vector, which will have type `&String`
 103 //! - It will then call the impl of `convertTo()` that is intended
 104 //!   for use with objects. This has the type:
 105 //!
 106 //!       fn(self: &Object) -> int
 107 //!
 108 //!   It is ok to provide a value for `self` of type `&String` because
 109 //!   `&String <: &Object`.
 110 //!
 111 //! OK, so intuitively we want this to be legal, so let's bring this back
 112 //! to variance and see whether we are computing the correct result. We
 113 //! must first figure out how to phrase the question "is an impl for
 114 //! `Object,int` usable where an impl for `String,int` is expected?"
 115 //!
 116 //! Maybe it's helpful to think of a dictionary-passing implementation of
 117 //! type classes. In that case, `convertAll()` takes an implicit parameter
 118 //! representing the impl. In short, we *have* an impl of type:
 119 //!
 120 //!     V_O = ConvertTo<int> for Object
 121 //!
 122 //! and the function prototype expects an impl of type:
 123 //!
 124 //!     V_S = ConvertTo<int> for String
 125 //!
 126 //! As with any argument, this is legal if the type of the value given
 127 //! (`V_O`) is a subtype of the type expected (`V_S`). So is `V_O <: V_S`?
 128 //! The answer will depend on the variance of the various parameters. In
 129 //! this case, because the `Self` parameter is contravariant and `A` is
 130 //! covariant, it means that:
 131 //!
 132 //!     V_O <: V_S iff
 133 //!         int <: int
 134 //!         String <: Object
 135 //!
 136 //! These conditions are satisfied and so we are happy.
 137 //!
 138 //! ### The algorithm
 139 //!
 140 //! The basic idea is quite straightforward. We iterate over the types
 141 //! defined and, for each use of a type parameter X, accumulate a
 142 //! constraint indicating that the variance of X must be valid for the
 143 //! variance of that use site. We then iteratively refine the variance of
 144 //! X until all constraints are met. There is *always* a sol'n, because at
 145 //! the limit we can declare all type parameters to be invariant and all
 146 //! constraints will be satisfied.
 147 //!
 148 //! As a simple example, consider:
 149 //!
 150 //!     enum Option<A> { Some(A), None }
 151 //!     enum OptionalFn<B> { Some(|B|), None }
 152 //!     enum OptionalMap<C> { Some(|C| -> C), None }
 153 //!
 154 //! Here, we will generate the constraints:
 155 //!
 156 //!     1. V(A) <= +
 157 //!     2. V(B) <= -
 158 //!     3. V(C) <= +
 159 //!     4. V(C) <= -
 160 //!
 161 //! These indicate that (1) the variance of A must be at most covariant;
 162 //! (2) the variance of B must be at most contravariant; and (3, 4) the
 163 //! variance of C must be at most covariant *and* contravariant. All of these
 164 //! results are based on a variance lattice defined as follows:
 165 //!
 166 //!       *      Top (bivariant)
 167 //!    -     +
 168 //!       o      Bottom (invariant)
 169 //!
 170 //! Based on this lattice, the solution V(A)=+, V(B)=-, V(C)=o is the
 171 //! optimal solution. Note that there is always a naive solution which
 172 //! just declares all variables to be invariant.
 173 //!
 174 //! You may be wondering why fixed-point iteration is required. The reason
 175 //! is that the variance of a use site may itself be a function of the
 176 //! variance of other type parameters. In full generality, our constraints
 177 //! take the form:
 178 //!
 179 //!     V(X) <= Term
 180 //!     Term := + | - | * | o | V(X) | Term x Term
 181 //!
 182 //! Here the notation V(X) indicates the variance of a type/region
 183 //! parameter `X` with respect to its defining class. `Term x Term`
 184 //! represents the "variance transform" as defined in the paper:
 185 //!
 186 //!   If the variance of a type variable `X` in type expression `E` is `V2`
 187 //!   and the definition-site variance of the [corresponding] type parameter
 188 //!   of a class `C` is `V1`, then the variance of `X` in the type expression
 189 //!   `C<E>` is `V3 = V1.xform(V2)`.
 190
 191 use self::VarianceTerm::*;
 192 use self::ParamKind::*;
 193
 194 use arena;
 195 use arena::Arena;
 196 use middle::resolve_lifetime as rl;
 197 use middle::subst;
 198 use middle::subst::{ParamSpace, FnSpace, TypeSpace, SelfSpace, VecPerParamSpace};
 199 use middle::ty::{self, Ty};
 200 use std::fmt;
 201 use std::rc::Rc;
 202 use std::iter::repeat;
 203 use syntax::ast;
 204 use syntax::ast_map;
 205 use syntax::ast_util;
 206 use syntax::visit;
 207 use syntax::visit::Visitor;
 208 use util::nodemap::NodeMap;
 209 use util::ppaux::Repr;
 210
 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);
 218 }
 219
 220 // Representing terms
 221 //
 222 // Terms are structured as a straightforward tree. Rather than rely on
 223 // GC, we allocate terms out of a bounded arena (the lifetime of this
 224 // arena is the lifetime 'a that is threaded around).
 225 //
 226 // We assign a unique index to each type/region parameter whose variance
 227 // is to be inferred. We refer to such variables as "inferreds". An
 228 // `InferredIndex` is a newtype'd int representing the index of such
 229 // a variable.
 230
 231 type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
 232
 233 #[derive(Copy, Show)]
 234 struct InferredIndex(uint);
 235
 236 #[derive(Copy)]
 237 enum VarianceTerm<'a> {
 238     ConstantTerm(ty::Variance),
 239     TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
 240     InferredTerm(InferredIndex),
 241 }
 242
 243 impl<'a> fmt::Debug for VarianceTerm<'a> {
 244     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 245         match *self {
 246             ConstantTerm(c1) => write!(f, "{:?}", c1),
 247             TransformTerm(v1, v2) => write!(f, "({:?} \u{00D7} {:?})", v1, v2),
 248             InferredTerm(id) => write!(f, "[{}]", { let InferredIndex(i) = id; i })
 249         }
 250     }
 251 }
 252
 253 // The first pass over the crate simply builds up the set of inferreds.
 254
 255 struct TermsContext<'a, 'tcx: 'a> {
 256     tcx: &'a ty::ctxt<'tcx>,
 257     arena: &'a Arena,
 258
 259     empty_variances: Rc<ty::ItemVariances>,
 260
 261     // Maps from the node id of a type/generic parameter to the
 262     // corresponding inferred index.
 263     inferred_map: NodeMap<InferredIndex>,
 264
 265     // Maps from an InferredIndex to the info for that variable.
 266     inferred_infos: Vec<InferredInfo<'a>> ,
 267 }
 268
 269 #[derive(Copy, Show, PartialEq)]
 270 enum ParamKind {
 271     TypeParam,
 272     RegionParam
 273 }
 274
 275 struct InferredInfo<'a> {
 276     item_id: ast::NodeId,
 277     kind: ParamKind,
 278     space: ParamSpace,
 279     index: uint,
 280     param_id: ast::NodeId,
 281     term: VarianceTermPtr<'a>,
 282 }
 283
 284 fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
 285                                                  arena: &'a mut Arena,
 286                                                  krate: &ast::Crate)
 287                                                  -> TermsContext<'a, 'tcx> {
 288     let mut terms_cx = TermsContext {
 289         tcx: tcx,
 290         arena: arena,
 291         inferred_map: NodeMap(),
 292         inferred_infos: Vec::new(),
 293
 294         // cache and share the variance struct used for items with
 295         // no type/region parameters
 296         empty_variances: Rc::new(ty::ItemVariances {
 297             types: VecPerParamSpace::empty(),
 298             regions: VecPerParamSpace::empty()
 299         })
 300     };
 301
 302     visit::walk_crate(&mut terms_cx, krate);
 303
 304     terms_cx
 305 }
 306
 307 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 308     fn add_inferred(&mut self,
 309                     item_id: ast::NodeId,
 310                     kind: ParamKind,
 311                     space: ParamSpace,
 312                     index: uint,
 313                     param_id: ast::NodeId) {
 314         let inf_index = InferredIndex(self.inferred_infos.len());
 315         let term = self.arena.alloc(|| InferredTerm(inf_index));
 316         self.inferred_infos.push(InferredInfo { item_id: item_id,
 317                                                 kind: kind,
 318                                                 space: space,
 319                                                 index: index,
 320                                                 param_id: param_id,
 321                                                 term: term });
 322         let newly_added = self.inferred_map.insert(param_id, inf_index).is_none();
 323         assert!(newly_added);
 324
 325         debug!("add_inferred(item_id={}, \
 326                 kind={:?}, \
 327                 index={}, \
 328                 param_id={},
 329                 inf_index={:?})",
 330                 item_id, kind, index, param_id, inf_index);
 331     }
 332
 333     fn num_inferred(&self) -> uint {
 334         self.inferred_infos.len()
 335     }
 336 }
 337
 338 impl<'a, 'tcx, 'v> Visitor<'v> for TermsContext<'a, 'tcx> {
 339     fn visit_item(&mut self, item: &ast::Item) {
 340         debug!("add_inferreds for item {}", item.repr(self.tcx));
 341
 342         let inferreds_on_entry = self.num_inferred();
 343
 344         // NB: In the code below for writing the results back into the
 345         // tcx, we rely on the fact that all inferreds for a particular
 346         // item are assigned continuous indices.
 347         match item.node {
 348             ast::ItemTrait(..) => {
 349                 self.add_inferred(item.id, TypeParam, SelfSpace, 0, item.id);
 350             }
 351             _ => { }
 352         }
 353
 354         match item.node {
 355             ast::ItemEnum(_, ref generics) |
 356             ast::ItemStruct(_, ref generics) |
 357             ast::ItemTrait(_, ref generics, _, _) => {
 358                 for (i, p) in generics.lifetimes.iter().enumerate() {
 359                     let id = p.lifetime.id;
 360                     self.add_inferred(item.id, RegionParam, TypeSpace, i, id);
 361                 }
 362                 for (i, p) in generics.ty_params.iter().enumerate() {
 363                     self.add_inferred(item.id, TypeParam, TypeSpace, i, p.id);
 364                 }
 365
 366                 // If this item has no type or lifetime parameters,
 367                 // then there are no variances to infer, so just
 368                 // insert an empty entry into the variance map.
 369                 // Arguably we could just leave the map empty in this
 370                 // case but it seems cleaner to be able to distinguish
 371                 // "invalid item id" from "item id with no
 372                 // parameters".
 373                 if self.num_inferred() == inferreds_on_entry {
 374                     let newly_added = self.tcx.item_variance_map.borrow_mut().insert(
 375                         ast_util::local_def(item.id),
 376                         self.empty_variances.clone()).is_none();
 377                     assert!(newly_added);
 378                 }
 379
 380                 visit::walk_item(self, item);
 381             }
 382
 383             ast::ItemImpl(..) |
 384             ast::ItemStatic(..) |
 385             ast::ItemConst(..) |
 386             ast::ItemFn(..) |
 387             ast::ItemMod(..) |
 388             ast::ItemForeignMod(..) |
 389             ast::ItemTy(..) |
 390             ast::ItemMac(..) => {
 391                 visit::walk_item(self, item);
 392             }
 393         }
 394     }
 395 }
 396
 397 // Constraint construction and representation
 398 //
 399 // The second pass over the AST determines the set of constraints.
 400 // We walk the set of items and, for each member, generate new constraints.
 401
 402 struct ConstraintContext<'a, 'tcx: 'a> {
 403     terms_cx: TermsContext<'a, 'tcx>,
 404
 405     // These are the def-id of the std::marker::InvariantType,
 406     // std::marker::InvariantLifetime, and so on. The arrays
 407     // are indexed by the `ParamKind` (type, lifetime, self). Note
 408     // that there are no marker types for self, so the entries for
 409     // self are always None.
 410     invariant_lang_items: [Option<ast::DefId>; 2],
 411     covariant_lang_items: [Option<ast::DefId>; 2],
 412     contravariant_lang_items: [Option<ast::DefId>; 2],
 413     unsafe_lang_item: Option<ast::DefId>,
 414
 415     // These are pointers to common `ConstantTerm` instances
 416     covariant: VarianceTermPtr<'a>,
 417     contravariant: VarianceTermPtr<'a>,
 418     invariant: VarianceTermPtr<'a>,
 419     bivariant: VarianceTermPtr<'a>,
 420
 421     constraints: Vec<Constraint<'a>> ,
 422 }
 423
 424 /// Declares that the variable `decl_id` appears in a location with
 425 /// variance `variance`.
 426 #[derive(Copy)]
 427 struct Constraint<'a> {
 428     inferred: InferredIndex,
 429     variance: &'a VarianceTerm<'a>,
 430 }
 431
 432 fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>,
 433                                         krate: &ast::Crate)
 434                                         -> ConstraintContext<'a, 'tcx> {
 435     let mut invariant_lang_items = [None; 2];
 436     let mut covariant_lang_items = [None; 2];
 437     let mut contravariant_lang_items = [None; 2];
 438
 439     covariant_lang_items[TypeParam as uint] =
 440         terms_cx.tcx.lang_items.covariant_type();
 441     covariant_lang_items[RegionParam as uint] =
 442         terms_cx.tcx.lang_items.covariant_lifetime();
 443
 444     contravariant_lang_items[TypeParam as uint] =
 445         terms_cx.tcx.lang_items.contravariant_type();
 446     contravariant_lang_items[RegionParam as uint] =
 447         terms_cx.tcx.lang_items.contravariant_lifetime();
 448
 449     invariant_lang_items[TypeParam as uint] =
 450         terms_cx.tcx.lang_items.invariant_type();
 451     invariant_lang_items[RegionParam as uint] =
 452         terms_cx.tcx.lang_items.invariant_lifetime();
 453
 454     let unsafe_lang_item = terms_cx.tcx.lang_items.unsafe_type();
 455
 456     let covariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Covariant));
 457     let contravariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Contravariant));
 458     let invariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Invariant));
 459     let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
 460     let mut constraint_cx = ConstraintContext {
 461         terms_cx: terms_cx,
 462
 463         invariant_lang_items: invariant_lang_items,
 464         covariant_lang_items: covariant_lang_items,
 465         contravariant_lang_items: contravariant_lang_items,
 466         unsafe_lang_item: unsafe_lang_item,
 467
 468         covariant: covariant,
 469         contravariant: contravariant,
 470         invariant: invariant,
 471         bivariant: bivariant,
 472         constraints: Vec::new(),
 473     };
 474     visit::walk_crate(&mut constraint_cx, krate);
 475     constraint_cx
 476 }
 477
 478 impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> {
 479     fn visit_item(&mut self, item: &ast::Item) {
 480         let did = ast_util::local_def(item.id);
 481         let tcx = self.terms_cx.tcx;
 482
 483         debug!("visit_item item={}",
 484                item.repr(tcx));
 485
 486         match item.node {
 487             ast::ItemEnum(ref enum_definition, _) => {
 488                 let generics = &ty::lookup_item_type(tcx, did).generics;
 489
 490                 // Hack: If we directly call `ty::enum_variants`, it
 491                 // annoyingly takes it upon itself to run off and
 492                 // evaluate the discriminants eagerly (*grumpy* that's
 493                 // not the typical pattern). This results in double
 494                 // error messages because typeck goes off and does
 495                 // this at a later time. All we really care about is
 496                 // the types of the variant arguments, so we just call
 497                 // `ty::VariantInfo::from_ast_variant()` ourselves
 498                 // here, mainly so as to mask the differences between
 499                 // struct-like enums and so forth.
 500                 for ast_variant in enum_definition.variants.iter() {
 501                     let variant =
 502                         ty::VariantInfo::from_ast_variant(tcx,
 503                                                           &**ast_variant,
 504                                                           /*discriminant*/ 0);
 505                     for arg_ty in variant.args.iter() {
 506                         self.add_constraints_from_ty(generics, *arg_ty, self.covariant);
 507                     }
 508                 }
 509             }
 510
 511             ast::ItemStruct(..) => {
 512                 let generics = &ty::lookup_item_type(tcx, did).generics;
 513                 let struct_fields = ty::lookup_struct_fields(tcx, did);
 514                 for field_info in struct_fields.iter() {
 515                     assert_eq!(field_info.id.krate, ast::LOCAL_CRATE);
 516                     let field_ty = ty::node_id_to_type(tcx, field_info.id.node);
 517                     self.add_constraints_from_ty(generics, field_ty, self.covariant);
 518                 }
 519             }
 520
 521             ast::ItemTrait(..) => {
 522                 let trait_items = ty::trait_items(tcx, did);
 523                 for trait_item in trait_items.iter() {
 524                     match *trait_item {
 525                         ty::MethodTraitItem(ref method) => {
 526                             self.add_constraints_from_sig(&method.generics,
 527                                                           &method.fty.sig,
 528                                                           self.covariant);
 529                         }
 530                         ty::TypeTraitItem(_) => {}
 531                     }
 532                 }
 533             }
 534
 535             ast::ItemStatic(..) |
 536             ast::ItemConst(..) |
 537             ast::ItemFn(..) |
 538             ast::ItemMod(..) |
 539             ast::ItemForeignMod(..) |
 540             ast::ItemTy(..) |
 541             ast::ItemImpl(..) |
 542             ast::ItemMac(..) => {
 543                 visit::walk_item(self, item);
 544             }
 545         }
 546     }
 547 }
 548
 549 /// Is `param_id` a lifetime according to `map`?
 550 fn is_lifetime(map: &ast_map::Map, param_id: ast::NodeId) -> bool {
 551     match map.find(param_id) {
 552         Some(ast_map::NodeLifetime(..)) => true, _ => false
 553     }
 554 }
 555
 556 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 557     fn tcx(&self) -> &'a ty::ctxt<'tcx> {
 558         self.terms_cx.tcx
 559     }
 560
 561     fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
 562         match self.terms_cx.inferred_map.get(&param_id) {
 563             Some(&index) => index,
 564             None => {
 565                 self.tcx().sess.bug(&format!(
 566                         "no inferred index entry for {}",
 567                         self.tcx().map.node_to_string(param_id))[]);
 568             }
 569         }
 570     }
 571
 572     fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
 573         let tcx = self.terms_cx.tcx;
 574         assert!(is_lifetime(&tcx.map, param_id));
 575         match tcx.named_region_map.get(&param_id) {
 576             Some(&rl::DefEarlyBoundRegion(_, _, lifetime_decl_id))
 577                 => lifetime_decl_id,
 578             Some(_) => panic!("should not encounter non early-bound cases"),
 579
 580             // The lookup should only fail when `param_id` is
 581             // itself a lifetime binding: use it as the decl_id.
 582             None    => param_id,
 583         }
 584
 585     }
 586
 587     /// Is `param_id` a type parameter for which we infer variance?
 588     fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
 589         let result = self.terms_cx.inferred_map.contains_key(&param_id);
 590
 591         // To safe-guard against invalid inferred_map constructions,
 592         // double-check if variance is inferred at some use of a type
 593         // parameter (by inspecting parent of its binding declaration
 594         // to see if it is introduced by a type or by a fn/impl).
 595
 596         let check_result = |&: this:&ConstraintContext| -> bool {
 597             let tcx = this.terms_cx.tcx;
 598             let decl_id = this.find_binding_for_lifetime(param_id);
 599             // Currently only called on lifetimes; double-checking that.
 600             assert!(is_lifetime(&tcx.map, param_id));
 601             let parent_id = tcx.map.get_parent(decl_id);
 602             let parent = tcx.map.find(parent_id).unwrap_or_else(
 603                 || panic!("tcx.map missing entry for id: {}", parent_id));
 604
 605             let is_inferred;
 606             macro_rules! cannot_happen { () => { {
 607                 panic!("invalid parent: {} for {}",
 608                       tcx.map.node_to_string(parent_id),
 609                       tcx.map.node_to_string(param_id));
 610             } } }
 611
 612             match parent {
 613                 ast_map::NodeItem(p) => {
 614                     match p.node {
 615                         ast::ItemTy(..) |
 616                         ast::ItemEnum(..) |
 617                         ast::ItemStruct(..) |
 618                         ast::ItemTrait(..)   => is_inferred = true,
 619                         ast::ItemFn(..)      => is_inferred = false,
 620                         _                    => cannot_happen!(),
 621                     }
 622                 }
 623                 ast_map::NodeTraitItem(..)   => is_inferred = false,
 624                 ast_map::NodeImplItem(..)    => is_inferred = false,
 625                 _                            => cannot_happen!(),
 626             }
 627
 628             return is_inferred;
 629         };
 630
 631         assert_eq!(result, check_result(self));
 632
 633         return result;
 634     }
 635
 636     /// Returns a variance term representing the declared variance of the type/region parameter
 637     /// with the given id.
 638     fn declared_variance(&self,
 639                          param_def_id: ast::DefId,
 640                          item_def_id: ast::DefId,
 641                          kind: ParamKind,
 642                          space: ParamSpace,
 643                          index: uint)
 644                          -> VarianceTermPtr<'a> {
 645         assert_eq!(param_def_id.krate, item_def_id.krate);
 646
 647         if self.invariant_lang_items[kind as uint] == Some(item_def_id) {
 648             self.invariant
 649         } else if self.covariant_lang_items[kind as uint] == Some(item_def_id) {
 650             self.covariant
 651         } else if self.contravariant_lang_items[kind as uint] == Some(item_def_id) {
 652             self.contravariant
 653         } else if kind == TypeParam && Some(item_def_id) == self.unsafe_lang_item {
 654             self.invariant
 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
 658             // variance.
 659             let InferredIndex(index) = self.inferred_index(param_def_id.node);
 660             self.terms_cx.inferred_infos[index].term
 661         } else {
 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),
 668             };
 669             self.constant_term(variance)
 670         }
 671     }
 672
 673     fn add_constraint(&mut self,
 674                       InferredIndex(index): InferredIndex,
 675                       variance: VarianceTermPtr<'a>) {
 676         debug!("add_constraint(index={}, variance={:?})",
 677                 index, variance);
 678         self.constraints.push(Constraint { inferred: InferredIndex(index),
 679                                            variance: variance });
 680     }
 681
 682     fn contravariant(&mut self,
 683                      variance: VarianceTermPtr<'a>)
 684                      -> VarianceTermPtr<'a> {
 685         self.xform(variance, self.contravariant)
 686     }
 687
 688     fn invariant(&mut self,
 689                  variance: VarianceTermPtr<'a>)
 690                  -> VarianceTermPtr<'a> {
 691         self.xform(variance, self.invariant)
 692     }
 693
 694     fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
 695         match v {
 696             ty::Covariant => self.covariant,
 697             ty::Invariant => self.invariant,
 698             ty::Contravariant => self.contravariant,
 699             ty::Bivariant => self.bivariant,
 700         }
 701     }
 702
 703     fn xform(&mut self,
 704              v1: VarianceTermPtr<'a>,
 705              v2: VarianceTermPtr<'a>)
 706              -> VarianceTermPtr<'a> {
 707         match (*v1, *v2) {
 708             (_, ConstantTerm(ty::Covariant)) => {
 709                 // Applying a "covariant" transform is always a no-op
 710                 v1
 711             }
 712
 713             (ConstantTerm(c1), ConstantTerm(c2)) => {
 714                 self.constant_term(c1.xform(c2))
 715             }
 716
 717             _ => {
 718                 &*self.terms_cx.arena.alloc(|| TransformTerm(v1, v2))
 719             }
 720         }
 721     }
 722
 723     /// Adds constraints appropriate for an instance of `ty` appearing
 724     /// in a context with the generics defined in `generics` and
 725     /// ambient variance `variance`
 726     fn add_constraints_from_ty(&mut self,
 727                                generics: &ty::Generics<'tcx>,
 728                                ty: Ty<'tcx>,
 729                                variance: VarianceTermPtr<'a>) {
 730         debug!("add_constraints_from_ty(ty={})", ty.repr(self.tcx()));
 731
 732         match ty.sty {
 733             ty::ty_bool |
 734             ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) |
 735             ty::ty_float(_) | ty::ty_str => {
 736                 /* leaf type -- noop */
 737             }
 738
 739             ty::ty_unboxed_closure(..) => {
 740                 self.tcx().sess.bug("Unexpected unboxed closure type in variance computation");
 741             }
 742
 743             ty::ty_rptr(region, ref mt) => {
 744                 let contra = self.contravariant(variance);
 745                 self.add_constraints_from_region(generics, *region, contra);
 746                 self.add_constraints_from_mt(generics, mt, variance);
 747             }
 748
 749             ty::ty_uniq(typ) | ty::ty_vec(typ, _) | ty::ty_open(typ) => {
 750                 self.add_constraints_from_ty(generics, typ, variance);
 751             }
 752
 753             ty::ty_ptr(ref mt) => {
 754                 self.add_constraints_from_mt(generics, mt, variance);
 755             }
 756
 757             ty::ty_tup(ref subtys) => {
 758                 for &subty in subtys.iter() {
 759                     self.add_constraints_from_ty(generics, subty, variance);
 760                 }
 761             }
 762
 763             ty::ty_enum(def_id, substs) |
 764             ty::ty_struct(def_id, substs) => {
 765                 let item_type = ty::lookup_item_type(self.tcx(), def_id);
 766
 767                 // All type parameters on enums and structs should be
 768                 // in the TypeSpace.
 769                 assert!(item_type.generics.types.is_empty_in(subst::SelfSpace));
 770                 assert!(item_type.generics.types.is_empty_in(subst::FnSpace));
 771                 assert!(item_type.generics.regions.is_empty_in(subst::SelfSpace));
 772                 assert!(item_type.generics.regions.is_empty_in(subst::FnSpace));
 773
 774                 self.add_constraints_from_substs(
 775                     generics,
 776                     def_id,
 777                     item_type.generics.types.get_slice(subst::TypeSpace),
 778                     item_type.generics.regions.get_slice(subst::TypeSpace),
 779                     substs,
 780                     variance);
 781             }
 782
 783             ty::ty_projection(ref data) => {
 784                 let trait_ref = &data.trait_ref;
 785                 let trait_def = ty::lookup_trait_def(self.tcx(), trait_ref.def_id);
 786                 self.add_constraints_from_substs(
 787                     generics,
 788                     trait_ref.def_id,
 789                     trait_def.generics.types.as_slice(),
 790                     trait_def.generics.regions.as_slice(),
 791                     trait_ref.substs,
 792                     variance);
 793             }
 794
 795             ty::ty_trait(ref data) => {
 796                 let trait_ref = data.principal_trait_ref_with_self_ty(self.tcx(),
 797                                                                       self.tcx().types.err);
 798                 let trait_def = ty::lookup_trait_def(self.tcx(), trait_ref.def_id());
 799
 800                 // Traits never declare region parameters in the self
 801                 // space nor anything in the fn space.
 802                 assert!(trait_def.generics.regions.is_empty_in(subst::SelfSpace));
 803                 assert!(trait_def.generics.types.is_empty_in(subst::FnSpace));
 804                 assert!(trait_def.generics.regions.is_empty_in(subst::FnSpace));
 805
 806                 // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
 807                 let contra = self.contravariant(variance);
 808                 self.add_constraints_from_region(generics, data.bounds.region_bound, contra);
 809
 810                 self.add_constraints_from_substs(
 811                     generics,
 812                     trait_ref.def_id(),
 813                     trait_def.generics.types.get_slice(subst::TypeSpace),
 814                     trait_def.generics.regions.get_slice(subst::TypeSpace),
 815                     trait_ref.substs(),
 816                     variance);
 817             }
 818
 819             ty::ty_param(ref data) => {
 820                 let def_id = generics.types.get(data.space, data.idx as uint).def_id;
 821                 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
 822                 match self.terms_cx.inferred_map.get(&def_id.node) {
 823                     Some(&index) => {
 824                         self.add_constraint(index, variance);
 825                     }
 826                     None => {
 827                         // We do not infer variance for type parameters
 828                         // declared on methods. They will not be present
 829                         // in the inferred_map.
 830                     }
 831                 }
 832             }
 833
 834             ty::ty_bare_fn(_, &ty::BareFnTy { ref sig, .. }) => {
 835                 self.add_constraints_from_sig(generics, sig, variance);
 836             }
 837
 838             ty::ty_infer(..) | ty::ty_err => {
 839                 self.tcx().sess.bug(
 840                     &format!("unexpected type encountered in \
 841                             variance inference: {}",
 842                             ty.repr(self.tcx()))[]);
 843             }
 844         }
 845     }
 846
 847
 848     /// Adds constraints appropriate for a nominal type (enum, struct,
 849     /// object, etc) appearing in a context with ambient variance `variance`
 850     fn add_constraints_from_substs(&mut self,
 851                                    generics: &ty::Generics<'tcx>,
 852                                    def_id: ast::DefId,
 853                                    type_param_defs: &[ty::TypeParameterDef<'tcx>],
 854                                    region_param_defs: &[ty::RegionParameterDef],
 855                                    substs: &subst::Substs<'tcx>,
 856                                    variance: VarianceTermPtr<'a>) {
 857         debug!("add_constraints_from_substs(def_id={:?})", def_id);
 858
 859         for p in type_param_defs.iter() {
 860             let variance_decl =
 861                 self.declared_variance(p.def_id, def_id, TypeParam,
 862                                        p.space, p.index as uint);
 863             let variance_i = self.xform(variance, variance_decl);
 864             let substs_ty = *substs.types.get(p.space, p.index as uint);
 865             self.add_constraints_from_ty(generics, substs_ty, variance_i);
 866         }
 867
 868         for p in region_param_defs.iter() {
 869             let variance_decl =
 870                 self.declared_variance(p.def_id, def_id,
 871                                        RegionParam, p.space, p.index as uint);
 872             let variance_i = self.xform(variance, variance_decl);
 873             let substs_r = *substs.regions().get(p.space, p.index as uint);
 874             self.add_constraints_from_region(generics, substs_r, variance_i);
 875         }
 876     }
 877
 878     /// Adds constraints appropriate for a function with signature
 879     /// `sig` appearing in a context with ambient variance `variance`
 880     fn add_constraints_from_sig(&mut self,
 881                                 generics: &ty::Generics<'tcx>,
 882                                 sig: &ty::PolyFnSig<'tcx>,
 883                                 variance: VarianceTermPtr<'a>) {
 884         let contra = self.contravariant(variance);
 885         for &input in sig.0.inputs.iter() {
 886             self.add_constraints_from_ty(generics, input, contra);
 887         }
 888         if let ty::FnConverging(result_type) = sig.0.output {
 889             self.add_constraints_from_ty(generics, result_type, variance);
 890         }
 891     }
 892
 893     /// Adds constraints appropriate for a region appearing in a
 894     /// context with ambient variance `variance`
 895     fn add_constraints_from_region(&mut self,
 896                                    _generics: &ty::Generics<'tcx>,
 897                                    region: ty::Region,
 898                                    variance: VarianceTermPtr<'a>) {
 899         match region {
 900             ty::ReEarlyBound(param_id, _, _, _) => {
 901                 if self.is_to_be_inferred(param_id) {
 902                     let index = self.inferred_index(param_id);
 903                     self.add_constraint(index, variance);
 904                 }
 905             }
 906
 907             ty::ReStatic => { }
 908
 909             ty::ReLateBound(..) => {
 910                 // We do not infer variance for region parameters on
 911                 // methods or in fn types.
 912             }
 913
 914             ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) |
 915             ty::ReEmpty => {
 916                 // We don't expect to see anything but 'static or bound
 917                 // regions when visiting member types or method types.
 918                 self.tcx()
 919                     .sess
 920                     .bug(&format!("unexpected region encountered in variance \
 921                                   inference: {}",
 922                                  region.repr(self.tcx()))[]);
 923             }
 924         }
 925     }
 926
 927     /// Adds constraints appropriate for a mutability-type pair
 928     /// appearing in a context with ambient variance `variance`
 929     fn add_constraints_from_mt(&mut self,
 930                                generics: &ty::Generics<'tcx>,
 931                                mt: &ty::mt<'tcx>,
 932                                variance: VarianceTermPtr<'a>) {
 933         match mt.mutbl {
 934             ast::MutMutable => {
 935                 let invar = self.invariant(variance);
 936                 self.add_constraints_from_ty(generics, mt.ty, invar);
 937             }
 938
 939             ast::MutImmutable => {
 940                 self.add_constraints_from_ty(generics, mt.ty, variance);
 941             }
 942         }
 943     }
 944 }
 945
 946 // Constraint solving
 947 //
 948 // The final phase iterates over the constraints, refining the variance
 949 // for each inferred until a fixed point is reached. This will be the
 950 // optimal solution to the constraints. The final variance for each
 951 // inferred is then written into the `variance_map` in the tcx.
 952
 953 struct SolveContext<'a, 'tcx: 'a> {
 954     terms_cx: TermsContext<'a, 'tcx>,
 955     constraints: Vec<Constraint<'a>> ,
 956
 957     // Maps from an InferredIndex to the inferred value for that variable.
 958     solutions: Vec<ty::Variance> }
 959
 960 fn solve_constraints(constraints_cx: ConstraintContext) {
 961     let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
 962     let solutions: Vec<_> = repeat(ty::Bivariant).take(terms_cx.num_inferred()).collect();
 963     let mut solutions_cx = SolveContext {
 964         terms_cx: terms_cx,
 965         constraints: constraints,
 966         solutions: solutions
 967     };
 968     solutions_cx.solve();
 969     solutions_cx.write();
 970 }
 971
 972 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
 973     fn solve(&mut self) {
 974         // Propagate constraints until a fixed point is reached.  Note
 975         // that the maximum number of iterations is 2C where C is the
 976         // number of constraints (each variable can change values at most
 977         // twice). Since number of constraints is linear in size of the
 978         // input, so is the inference process.
 979         let mut changed = true;
 980         while changed {
 981             changed = false;
 982
 983             for constraint in self.constraints.iter() {
 984                 let Constraint { inferred, variance: term } = *constraint;
 985                 let InferredIndex(inferred) = inferred;
 986                 let variance = self.evaluate(term);
 987                 let old_value = self.solutions[inferred];
 988                 let new_value = glb(variance, old_value);
 989                 if old_value != new_value {
 990                     debug!("Updating inferred {} (node {}) \
 991                             from {:?} to {:?} due to {:?}",
 992                             inferred,
 993                             self.terms_cx
 994                                 .inferred_infos[inferred]
 995                                 .param_id,
 996                             old_value,
 997                             new_value,
 998                             term);
 999
1000                     self.solutions[inferred] = new_value;
1001                     changed = true;
1002                 }
1003             }
1004         }
1005     }
1006
1007     fn write(&self) {
1008         // Collect all the variances for a particular item and stick
1009         // them into the variance map. We rely on the fact that we
1010         // generate all the inferreds for a particular item
1011         // consecutively (that is, we collect solutions for an item
1012         // until we see a new item id, and we assume (1) the solutions
1013         // are in the same order as the type parameters were declared
1014         // and (2) all solutions or a given item appear before a new
1015         // item id).
1016
1017         let tcx = self.terms_cx.tcx;
1018         let solutions = &self.solutions;
1019         let inferred_infos = &self.terms_cx.inferred_infos;
1020         let mut index = 0;
1021         let num_inferred = self.terms_cx.num_inferred();
1022         while index < num_inferred {
1023             let item_id = inferred_infos[index].item_id;
1024             let mut types = VecPerParamSpace::empty();
1025             let mut regions = VecPerParamSpace::empty();
1026
1027             while index < num_inferred &&
1028                   inferred_infos[index].item_id == item_id {
1029                 let info = &inferred_infos[index];
1030                 let variance = solutions[index];
1031                 debug!("Index {} Info {} / {:?} / {:?} Variance {:?}",
1032                        index, info.index, info.kind, info.space, variance);
1033                 match info.kind {
1034                     TypeParam => {
1035                         types.push(info.space, variance);
1036                     }
1037                     RegionParam => {
1038                         regions.push(info.space, variance);
1039                     }
1040                 }
1041                 index += 1;
1042             }
1043
1044             let item_variances = ty::ItemVariances {
1045                 types: types,
1046                 regions: regions
1047             };
1048             debug!("item_id={} item_variances={}",
1049                     item_id,
1050                     item_variances.repr(tcx));
1051
1052             let item_def_id = ast_util::local_def(item_id);
1053
1054             // For unit testing: check for a special "rustc_variance"
1055             // attribute and report an error with various results if found.
1056             if ty::has_attr(tcx, item_def_id, "rustc_variance") {
1057                 let found = item_variances.repr(tcx);
1058                 span_err!(tcx.sess, tcx.map.span(item_id), E0208, "{}", &found[]);
1059             }
1060
1061             let newly_added = tcx.item_variance_map.borrow_mut()
1062                                  .insert(item_def_id, Rc::new(item_variances)).is_none();
1063             assert!(newly_added);
1064         }
1065     }
1066
1067     fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
1068         match *term {
1069             ConstantTerm(v) => {
1070                 v
1071             }
1072
1073             TransformTerm(t1, t2) => {
1074                 let v1 = self.evaluate(t1);
1075                 let v2 = self.evaluate(t2);
1076                 v1.xform(v2)
1077             }
1078
1079             InferredTerm(InferredIndex(index)) => {
1080                 self.solutions[index]
1081             }
1082         }
1083     }
1084 }
1085
1086 // Miscellany transformations on variance
1087
1088 trait Xform {
1089     fn xform(self, v: Self) -> Self;
1090 }
1091
1092 impl Xform for ty::Variance {
1093     fn xform(self, v: ty::Variance) -> ty::Variance {
1094         // "Variance transformation", Figure 1 of The Paper
1095         match (self, v) {
1096             // Figure 1, column 1.
1097             (ty::Covariant, ty::Covariant) => ty::Covariant,
1098             (ty::Covariant, ty::Contravariant) => ty::Contravariant,
1099             (ty::Covariant, ty::Invariant) => ty::Invariant,
1100             (ty::Covariant, ty::Bivariant) => ty::Bivariant,
1101
1102             // Figure 1, column 2.
1103             (ty::Contravariant, ty::Covariant) => ty::Contravariant,
1104             (ty::Contravariant, ty::Contravariant) => ty::Covariant,
1105             (ty::Contravariant, ty::Invariant) => ty::Invariant,
1106             (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
1107
1108             // Figure 1, column 3.
1109             (ty::Invariant, _) => ty::Invariant,
1110
1111             // Figure 1, column 4.
1112             (ty::Bivariant, _) => ty::Bivariant,
1113         }
1114     }
1115 }
1116
1117 fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance {
1118     // Greatest lower bound of the variance lattice as
1119     // defined in The Paper:
1120     //
1121     //       *
1122     //    -     +
1123     //       o
1124     match (v1, v2) {
1125         (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
1126
1127         (ty::Covariant, ty::Contravariant) => ty::Invariant,
1128         (ty::Contravariant, ty::Covariant) => ty::Invariant,
1129
1130         (ty::Covariant, ty::Covariant) => ty::Covariant,
1131
1132         (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
1133
1134         (x, ty::Bivariant) | (ty::Bivariant, x) => x,
1135     }
1136 }