src/librustc/middle/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 /*!
  12
  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.
  17
  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.
  22
  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.
  27
  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.)
  34
  35 ### Variance on traits
  36
  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
  39 compute.
  40
  41 #### Trait variance and object types
  42
  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.
  51
  52 To see what I mean, consider a trait like so:
  53
  54     trait ConvertTo<A> {
  55         fn convertTo(&self) -> A;
  56     }
  57
  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`.
  65
  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.)
  77
  78 #### Trait variance and vtable resolution
  79
  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:
  83
  84     fn convertAll<A,T:ConvertTo<A>>(v: &[T]) {
  85         ...
  86     }
  87
  88 Now imagine that I have an implementation of `ConvertTo` for `Object`:
  89
  90     impl ConvertTo<int> for Object { ... }
  91
  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`:
  95
  96     let mut vector = ~["string", ...];
  97     convertAll::<int, String>(v);
  98
  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:
 102
 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:
 107
 108       fn(self: &Object) -> int
 109
 110   It is ok to provide a value for `self` of type `&String` because
 111   `&String <: &Object`.
 112
 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?"
 117
 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:
 121
 122     V_O = ConvertTo<int> for Object
 123
 124 and the function prototype expects an impl of type:
 125
 126     V_S = ConvertTo<int> for String
 127
 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:
 133
 134     V_O <: V_S iff
 135         int <: int
 136         String <: Object
 137
 138 These conditions are satisfied and so we are happy.
 139
 140 ### The algorithm
 141
 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.
 149
 150 As a simple example, consider:
 151
 152     enum Option<A> { Some(A), None }
 153     enum OptionalFn<B> { Some(|B|), None }
 154     enum OptionalMap<C> { Some(|C| -> C), None }
 155
 156 Here, we will generate the constraints:
 157
 158     1. V(A) <= +
 159     2. V(B) <= -
 160     3. V(C) <= +
 161     4. V(C) <= -
 162
 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:
 167
 168       *      Top (bivariant)
 169    -     +
 170       o      Bottom (invariant)
 171
 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.
 175
 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
 179 take the form:
 180
 181     V(X) <= Term
 182     Term := + | - | * | o | V(X) | Term x Term
 183
 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:
 187
 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)`.
 192
 193 */
 194
 195 use std::collections::HashMap;
 196 use arena;
 197 use arena::Arena;
 198 use middle::resolve_lifetime as rl;
 199 use middle::subst;
 200 use middle::subst::{ParamSpace, FnSpace, TypeSpace, SelfSpace, VecPerParamSpace};
 201 use middle::ty;
 202 use std::fmt;
 203 use std::rc::Rc;
 204 use syntax::ast;
 205 use syntax::ast_map;
 206 use syntax::ast_util;
 207 use syntax::visit;
 208 use syntax::visit::Visitor;
 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 /**************************************************************************
 221  * Representing terms
 222  *
 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).
 226  *
 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
 230  * a variable.
 231  */
 232
 233 type VarianceTermPtr<'a> = &'a VarianceTerm<'a>;
 234
 235 struct InferredIndex(uint);
 236
 237 enum VarianceTerm<'a> {
 238     ConstantTerm(ty::Variance),
 239     TransformTerm(VarianceTermPtr<'a>, VarianceTermPtr<'a>),
 240     InferredTerm(InferredIndex),
 241 }
 242
 243 impl<'a> fmt::Show 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, "({} \u00D7 {})", v1, v2),
 248             InferredTerm(id) => write!(f, "[{}]", { let InferredIndex(i) = id; i })
 249         }
 250     }
 251 }
 252
 253 /**************************************************************************
 254  * The first pass over the crate simply builds up the set of inferreds.
 255  */
 256
 257 struct TermsContext<'a, 'tcx: 'a> {
 258     tcx: &'a ty::ctxt<'tcx>,
 259     arena: &'a Arena,
 260
 261     empty_variances: Rc<ty::ItemVariances>,
 262
 263     // Maps from the node id of a type/generic parameter to the
 264     // corresponding inferred index.
 265     inferred_map: HashMap<ast::NodeId, InferredIndex>,
 266
 267     // Maps from an InferredIndex to the info for that variable.
 268     inferred_infos: Vec<InferredInfo<'a>> ,
 269 }
 270
 271 #[deriving(Show, PartialEq)]
 272 enum ParamKind {
 273     TypeParam,
 274     RegionParam
 275 }
 276
 277 struct InferredInfo<'a> {
 278     item_id: ast::NodeId,
 279     kind: ParamKind,
 280     space: ParamSpace,
 281     index: uint,
 282     param_id: ast::NodeId,
 283     term: VarianceTermPtr<'a>,
 284 }
 285
 286 fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
 287                                                  arena: &'a mut Arena,
 288                                                  krate: &ast::Crate)
 289                                                  -> TermsContext<'a, 'tcx> {
 290     let mut terms_cx = TermsContext {
 291         tcx: tcx,
 292         arena: arena,
 293         inferred_map: HashMap::new(),
 294         inferred_infos: Vec::new(),
 295
 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()
 301         })
 302     };
 303
 304     visit::walk_crate(&mut terms_cx, krate);
 305
 306     terms_cx
 307 }
 308
 309 impl<'a, 'tcx> TermsContext<'a, 'tcx> {
 310     fn add_inferred(&mut self,
 311                     item_id: ast::NodeId,
 312                     kind: ParamKind,
 313                     space: ParamSpace,
 314                     index: uint,
 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,
 319                                                 kind: kind,
 320                                                 space: space,
 321                                                 index: index,
 322                                                 param_id: param_id,
 323                                                 term: term });
 324         let newly_added = self.inferred_map.insert(param_id, inf_index);
 325         assert!(newly_added);
 326
 327         debug!("add_inferred(item_id={}, \
 328                 kind={:?}, \
 329                 index={}, \
 330                 param_id={},
 331                 inf_index={:?})",
 332                 item_id, kind, index, param_id, inf_index);
 333     }
 334
 335     fn num_inferred(&self) -> uint {
 336         self.inferred_infos.len()
 337     }
 338 }
 339
 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));
 343
 344         let inferreds_on_entry = self.num_inferred();
 345
 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.
 349         match item.node {
 350             ast::ItemTrait(..) => {
 351                 self.add_inferred(item.id, TypeParam, SelfSpace, 0, item.id);
 352             }
 353             _ => { }
 354         }
 355
 356         match item.node {
 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);
 363                 }
 364                 for (i, p) in generics.ty_params.iter().enumerate() {
 365                     self.add_inferred(item.id, TypeParam, TypeSpace, i, p.id);
 366                 }
 367
 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
 374                 // parameters".
 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);
 380                 }
 381
 382                 visit::walk_item(self, item);
 383             }
 384
 385             ast::ItemImpl(..) |
 386             ast::ItemStatic(..) |
 387             ast::ItemConst(..) |
 388             ast::ItemFn(..) |
 389             ast::ItemMod(..) |
 390             ast::ItemForeignMod(..) |
 391             ast::ItemTy(..) |
 392             ast::ItemMac(..) => {
 393                 visit::walk_item(self, item);
 394             }
 395         }
 396     }
 397 }
 398
 399 /**************************************************************************
 400  * Constraint construction and representation
 401  *
 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.
 404  */
 405
 406 struct ConstraintContext<'a, 'tcx: 'a> {
 407     terms_cx: TermsContext<'a, 'tcx>,
 408
 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>,
 418
 419     // These are pointers to common `ConstantTerm` instances
 420     covariant: VarianceTermPtr<'a>,
 421     contravariant: VarianceTermPtr<'a>,
 422     invariant: VarianceTermPtr<'a>,
 423     bivariant: VarianceTermPtr<'a>,
 424
 425     constraints: Vec<Constraint<'a>> ,
 426 }
 427
 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>,
 433 }
 434
 435 fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>,
 436                                         krate: &ast::Crate)
 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];
 441
 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();
 446
 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();
 451
 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();
 456
 457     let unsafe_lang_item = terms_cx.tcx.lang_items.unsafe_type();
 458
 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 {
 464         terms_cx: terms_cx,
 465
 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,
 470
 471         covariant: covariant,
 472         contravariant: contravariant,
 473         invariant: invariant,
 474         bivariant: bivariant,
 475         constraints: Vec::new(),
 476     };
 477     visit::walk_crate(&mut constraint_cx, krate);
 478     constraint_cx
 479 }
 480
 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;
 485
 486         match item.node {
 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() {
 499                     let variant =
 500                         ty::VariantInfo::from_ast_variant(tcx,
 501                                                           &**ast_variant,
 502                                                           /*discriminant*/ 0);
 503                     for arg_ty in variant.args.iter() {
 504                         self.add_constraints_from_ty(*arg_ty, self.covariant);
 505                     }
 506                 }
 507             }
 508
 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);
 515                 }
 516             }
 517
 518             ast::ItemTrait(..) => {
 519                 let trait_items = ty::trait_items(tcx, did);
 520                 for trait_item in trait_items.iter() {
 521                     match *trait_item {
 522                         ty::MethodTraitItem(ref method) => {
 523                             self.add_constraints_from_sig(&method.fty.sig,
 524                                                           self.covariant);
 525                         }
 526                         ty::TypeTraitItem(_) => {}
 527                     }
 528                 }
 529             }
 530
 531             ast::ItemStatic(..) |
 532             ast::ItemConst(..) |
 533             ast::ItemFn(..) |
 534             ast::ItemMod(..) |
 535             ast::ItemForeignMod(..) |
 536             ast::ItemTy(..) |
 537             ast::ItemImpl(..) |
 538             ast::ItemMac(..) => {
 539                 visit::walk_item(self, item);
 540             }
 541         }
 542     }
 543 }
 544
 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
 549     }
 550 }
 551
 552 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 553     fn tcx(&self) -> &'a ty::ctxt<'tcx> {
 554         self.terms_cx.tcx
 555     }
 556
 557     fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
 558         match self.terms_cx.inferred_map.find(&param_id) {
 559             Some(&index) => index,
 560             None => {
 561                 self.tcx().sess.bug(format!(
 562                         "no inferred index entry for {}",
 563                         self.tcx().map.node_to_string(param_id)).as_slice());
 564             }
 565         }
 566     }
 567
 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(&param_id) {
 572             Some(&rl::DefEarlyBoundRegion(_, _, lifetime_decl_id))
 573                 => lifetime_decl_id,
 574             Some(_) => fail!("should not encounter non early-bound cases"),
 575
 576             // The lookup should only fail when `param_id` is
 577             // itself a lifetime binding: use it as the decl_id.
 578             None    => param_id,
 579         }
 580
 581     }
 582
 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(&param_id);
 586
 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).
 591
 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));
 600
 601             let is_inferred;
 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));
 606             } } }
 607
 608             match parent {
 609                 ast_map::NodeItem(p) => {
 610                     match p.node {
 611                         ast::ItemTy(..) |
 612                         ast::ItemEnum(..) |
 613                         ast::ItemStruct(..) |
 614                         ast::ItemTrait(..)   => is_inferred = true,
 615                         ast::ItemFn(..)      => is_inferred = false,
 616                         _                    => cannot_happen!(),
 617                     }
 618                 }
 619                 ast_map::NodeTraitItem(..)   => is_inferred = false,
 620                 ast_map::NodeImplItem(..)    => is_inferred = false,
 621                 _                            => cannot_happen!(),
 622             }
 623
 624             return is_inferred;
 625         };
 626
 627         assert_eq!(result, check_result(self));
 628
 629         return result;
 630     }
 631
 632     fn declared_variance(&self,
 633                          param_def_id: ast::DefId,
 634                          item_def_id: ast::DefId,
 635                          kind: ParamKind,
 636                          space: ParamSpace,
 637                          index: uint)
 638                          -> VarianceTermPtr<'a> {
 639         /*!
 640          * Returns a variance term representing the declared variance of
 641          * the type/region parameter with the given id.
 642          */
 643
 644         assert_eq!(param_def_id.krate, item_def_id.krate);
 645
 646         if self.invariant_lang_items[kind as uint] == Some(item_def_id) {
 647             self.invariant
 648         } else if self.covariant_lang_items[kind as uint] == Some(item_def_id) {
 649             self.covariant
 650         } else if self.contravariant_lang_items[kind as uint] == Some(item_def_id) {
 651             self.contravariant
 652         } else if kind == TypeParam && Some(item_def_id) == self.unsafe_lang_item {
 653             self.invariant
 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
 657             // variance.
 658             let InferredIndex(index) = self.inferred_index(param_def_id.node);
 659             self.terms_cx.inferred_infos.get(index).term
 660         } else {
 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),
 667             };
 668             self.constant_term(variance)
 669         }
 670     }
 671
 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 });
 679     }
 680
 681     fn contravariant(&mut self,
 682                      variance: VarianceTermPtr<'a>)
 683                      -> VarianceTermPtr<'a> {
 684         self.xform(variance, self.contravariant)
 685     }
 686
 687     fn invariant(&mut self,
 688                  variance: VarianceTermPtr<'a>)
 689                  -> VarianceTermPtr<'a> {
 690         self.xform(variance, self.invariant)
 691     }
 692
 693     fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
 694         match v {
 695             ty::Covariant => self.covariant,
 696             ty::Invariant => self.invariant,
 697             ty::Contravariant => self.contravariant,
 698             ty::Bivariant => self.bivariant,
 699         }
 700     }
 701
 702     fn xform(&mut self,
 703              v1: VarianceTermPtr<'a>,
 704              v2: VarianceTermPtr<'a>)
 705              -> VarianceTermPtr<'a> {
 706         match (*v1, *v2) {
 707             (_, ConstantTerm(ty::Covariant)) => {
 708                 // Applying a "covariant" transform is always a no-op
 709                 v1
 710             }
 711
 712             (ConstantTerm(c1), ConstantTerm(c2)) => {
 713                 self.constant_term(c1.xform(c2))
 714             }
 715
 716             _ => {
 717                 self.terms_cx.arena.alloc(|| TransformTerm(v1, v2))
 718             }
 719         }
 720     }
 721
 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,
 725                                ty: ty::t,
 726                                variance: VarianceTermPtr<'a>) {
 727         debug!("add_constraints_from_ty(ty={})", ty.repr(self.tcx()));
 728
 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 */
 734             }
 735
 736             ty::ty_unboxed_closure(_, region) => {
 737                 let contra = self.contravariant(variance);
 738                 self.add_constraints_from_region(region, contra);
 739             }
 740
 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);
 745             }
 746
 747             ty::ty_uniq(typ) | ty::ty_vec(typ, _) | ty::ty_open(typ) => {
 748                 self.add_constraints_from_ty(typ, variance);
 749             }
 750
 751             ty::ty_ptr(ref mt) => {
 752                 self.add_constraints_from_mt(mt, variance);
 753             }
 754
 755             ty::ty_tup(ref subtys) => {
 756                 for &subty in subtys.iter() {
 757                     self.add_constraints_from_ty(subty, variance);
 758                 }
 759             }
 760
 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;
 765
 766                 // All type parameters on enums and structs should be
 767                 // in the TypeSpace.
 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));
 772
 773                 self.add_constraints_from_substs(
 774                     def_id,
 775                     generics.types.get_slice(subst::TypeSpace),
 776                     generics.regions.get_slice(subst::TypeSpace),
 777                     substs,
 778                     variance);
 779             }
 780
 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;
 784
 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));
 789
 790                 // Traits never declare region parameters in the self
 791                 // space.
 792                 assert!(generics.regions.is_empty_in(subst::SelfSpace));
 793
 794                 // Traits never declare type/region parameters in the
 795                 // fn space.
 796                 assert!(generics.types.is_empty_in(subst::FnSpace));
 797                 assert!(generics.regions.is_empty_in(subst::FnSpace));
 798
 799                 self.add_constraints_from_substs(
 800                     def_id,
 801                     generics.types.get_slice(subst::TypeSpace),
 802                     generics.regions.get_slice(subst::TypeSpace),
 803                     substs,
 804                     variance);
 805             }
 806
 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) {
 810                     Some(&index) => {
 811                         self.add_constraint(index, variance);
 812                     }
 813                     None => {
 814                         // We do not infer variance for type parameters
 815                         // declared on methods. They will not be present
 816                         // in the inferred_map.
 817                     }
 818                 }
 819             }
 820
 821             ty::ty_bare_fn(ty::BareFnTy { ref sig, .. }) |
 822             ty::ty_closure(box ty::ClosureTy {
 823                     ref sig,
 824                     store: ty::UniqTraitStore,
 825                     ..
 826                 }) => {
 827                 self.add_constraints_from_sig(sig, variance);
 828             }
 829
 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);
 835             }
 836
 837             ty::ty_infer(..) | ty::ty_err => {
 838                 self.tcx().sess.bug(
 839                     format!("unexpected type encountered in \
 840                             variance inference: {}",
 841                             ty.repr(self.tcx())).as_slice());
 842             }
 843         }
 844     }
 845
 846
 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,
 850                                    def_id: ast::DefId,
 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);
 856
 857         for p in type_param_defs.iter() {
 858             let variance_decl =
 859                 self.declared_variance(p.def_id, def_id, TypeParam,
 860                                        p.space, p.index);
 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);
 864         }
 865
 866         for p in region_param_defs.iter() {
 867             let variance_decl =
 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);
 873         }
 874     }
 875
 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,
 879                                 sig: &ty::FnSig,
 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);
 884         }
 885         self.add_constraints_from_ty(sig.output, variance);
 886     }
 887
 888     /// Adds constraints appropriate for a region appearing in a
 889     /// context with ambient variance `variance`
 890     fn add_constraints_from_region(&mut self,
 891                                    region: ty::Region,
 892                                    variance: VarianceTermPtr<'a>) {
 893         match region {
 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);
 898                 }
 899             }
 900
 901             ty::ReStatic => { }
 902
 903             ty::ReLateBound(..) => {
 904                 // We do not infer variance for region parameters on
 905                 // methods or in fn types.
 906             }
 907
 908             ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) |
 909             ty::ReEmpty => {
 910                 // We don't expect to see anything but 'static or bound
 911                 // regions when visiting member types or method types.
 912                 self.tcx()
 913                     .sess
 914                     .bug(format!("unexpected region encountered in variance \
 915                                   inference: {}",
 916                                  region.repr(self.tcx())).as_slice());
 917             }
 918         }
 919     }
 920
 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,
 924                                mt: &ty::mt,
 925                                variance: VarianceTermPtr<'a>) {
 926         match mt.mutbl {
 927             ast::MutMutable => {
 928                 let invar = self.invariant(variance);
 929                 self.add_constraints_from_ty(mt.ty, invar);
 930             }
 931
 932             ast::MutImmutable => {
 933                 self.add_constraints_from_ty(mt.ty, variance);
 934             }
 935         }
 936     }
 937 }
 938
 939 /**************************************************************************
 940  * Constraint solving
 941  *
 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.
 946  */
 947
 948 struct SolveContext<'a, 'tcx: 'a> {
 949     terms_cx: TermsContext<'a, 'tcx>,
 950     constraints: Vec<Constraint<'a>> ,
 951
 952     // Maps from an InferredIndex to the inferred value for that variable.
 953     solutions: Vec<ty::Variance> }
 954
 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 {
 959         terms_cx: terms_cx,
 960         constraints: constraints,
 961         solutions: solutions
 962     };
 963     solutions_cx.solve();
 964     solutions_cx.write();
 965 }
 966
 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;
 975         while changed {
 976             changed = false;
 977
 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 {}",
 987                             inferred,
 988                             self.terms_cx
 989                                 .inferred_infos
 990                                 .get(inferred)
 991                                 .param_id,
 992                             old_value,
 993                             new_value,
 994                             term.to_string());
 995
 996                     *self.solutions.get_mut(inferred) = new_value;
 997                     changed = true;
 998                 }
 999             }
1000         }
1001     }
1002
1003     fn write(&self) {
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
1011         // item id).
1012
1013         let tcx = self.terms_cx.tcx;
1014         let solutions = &self.solutions;
1015         let inferred_infos = &self.terms_cx.inferred_infos;
1016         let mut index = 0;
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();
1022
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);
1029                 match info.kind {
1030                     TypeParam => {
1031                         types.push(info.space, variance);
1032                     }
1033                     RegionParam => {
1034                         regions.push(info.space, variance);
1035                     }
1036                 }
1037                 index += 1;
1038             }
1039
1040             let item_variances = ty::ItemVariances {
1041                 types: types,
1042                 regions: regions
1043             };
1044             debug!("item_id={} item_variances={}",
1045                     item_id,
1046                     item_variances.repr(tcx));
1047
1048             let item_def_id = ast_util::local_def(item_id);
1049
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());
1055             }
1056
1057             let newly_added = tcx.item_variance_map.borrow_mut()
1058                                  .insert(item_def_id, Rc::new(item_variances));
1059             assert!(newly_added);
1060         }
1061     }
1062
1063     fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
1064         match *term {
1065             ConstantTerm(v) => {
1066                 v
1067             }
1068
1069             TransformTerm(t1, t2) => {
1070                 let v1 = self.evaluate(t1);
1071                 let v2 = self.evaluate(t2);
1072                 v1.xform(v2)
1073             }
1074
1075             InferredTerm(InferredIndex(index)) => {
1076                 *self.solutions.get(index)
1077             }
1078         }
1079     }
1080 }
1081
1082 /**************************************************************************
1083  * Miscellany transformations on variance
1084  */
1085
1086 trait Xform {
1087     fn xform(self, v: Self) -> Self;
1088 }
1089
1090 impl Xform for ty::Variance {
1091     fn xform(self, v: ty::Variance) -> ty::Variance {
1092         // "Variance transformation", Figure 1 of The Paper
1093         match (self, v) {
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,
1099
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,
1105
1106             // Figure 1, column 3.
1107             (ty::Invariant, _) => ty::Invariant,
1108
1109             // Figure 1, column 4.
1110             (ty::Bivariant, _) => ty::Bivariant,
1111         }
1112     }
1113 }
1114
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:
1118     //
1119     //       *
1120     //    -     +
1121     //       o
1122     match (v1, v2) {
1123         (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
1124
1125         (ty::Covariant, ty::Contravariant) => ty::Invariant,
1126         (ty::Contravariant, ty::Covariant) => ty::Invariant,
1127
1128         (ty::Covariant, ty::Covariant) => ty::Covariant,
1129
1130         (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
1131
1132         (x, ty::Bivariant) | (ty::Bivariant, x) => x,
1133     }
1134 }