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::ItemFn(..) |
 388             ast::ItemMod(..) |
 389             ast::ItemForeignMod(..) |
 390             ast::ItemTy(..) |
 391             ast::ItemMac(..) => {
 392                 visit::walk_item(self, item);
 393             }
 394         }
 395     }
 396 }
 397
 398 /**************************************************************************
 399  * Constraint construction and representation
 400  *
 401  * The second pass over the AST determines the set of constraints.
 402  * We walk the set of items and, for each member, generate new constraints.
 403  */
 404
 405 struct ConstraintContext<'a, 'tcx: 'a> {
 406     terms_cx: TermsContext<'a, 'tcx>,
 407
 408     // These are the def-id of the std::kinds::marker::InvariantType,
 409     // std::kinds::marker::InvariantLifetime, and so on. The arrays
 410     // are indexed by the `ParamKind` (type, lifetime, self). Note
 411     // that there are no marker types for self, so the entries for
 412     // self are always None.
 413     invariant_lang_items: [Option<ast::DefId>, ..2],
 414     covariant_lang_items: [Option<ast::DefId>, ..2],
 415     contravariant_lang_items: [Option<ast::DefId>, ..2],
 416     unsafe_lang_item: Option<ast::DefId>,
 417
 418     // These are pointers to common `ConstantTerm` instances
 419     covariant: VarianceTermPtr<'a>,
 420     contravariant: VarianceTermPtr<'a>,
 421     invariant: VarianceTermPtr<'a>,
 422     bivariant: VarianceTermPtr<'a>,
 423
 424     constraints: Vec<Constraint<'a>> ,
 425 }
 426
 427 /// Declares that the variable `decl_id` appears in a location with
 428 /// variance `variance`.
 429 struct Constraint<'a> {
 430     inferred: InferredIndex,
 431     variance: &'a VarianceTerm<'a>,
 432 }
 433
 434 fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>,
 435                                         krate: &ast::Crate)
 436                                         -> ConstraintContext<'a, 'tcx> {
 437     let mut invariant_lang_items = [None, ..2];
 438     let mut covariant_lang_items = [None, ..2];
 439     let mut contravariant_lang_items = [None, ..2];
 440
 441     covariant_lang_items[TypeParam as uint] =
 442         terms_cx.tcx.lang_items.covariant_type();
 443     covariant_lang_items[RegionParam as uint] =
 444         terms_cx.tcx.lang_items.covariant_lifetime();
 445
 446     contravariant_lang_items[TypeParam as uint] =
 447         terms_cx.tcx.lang_items.contravariant_type();
 448     contravariant_lang_items[RegionParam as uint] =
 449         terms_cx.tcx.lang_items.contravariant_lifetime();
 450
 451     invariant_lang_items[TypeParam as uint] =
 452         terms_cx.tcx.lang_items.invariant_type();
 453     invariant_lang_items[RegionParam as uint] =
 454         terms_cx.tcx.lang_items.invariant_lifetime();
 455
 456     let unsafe_lang_item = terms_cx.tcx.lang_items.unsafe_type();
 457
 458     let covariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Covariant));
 459     let contravariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Contravariant));
 460     let invariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Invariant));
 461     let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
 462     let mut constraint_cx = ConstraintContext {
 463         terms_cx: terms_cx,
 464
 465         invariant_lang_items: invariant_lang_items,
 466         covariant_lang_items: covariant_lang_items,
 467         contravariant_lang_items: contravariant_lang_items,
 468         unsafe_lang_item: unsafe_lang_item,
 469
 470         covariant: covariant,
 471         contravariant: contravariant,
 472         invariant: invariant,
 473         bivariant: bivariant,
 474         constraints: Vec::new(),
 475     };
 476     visit::walk_crate(&mut constraint_cx, krate);
 477     constraint_cx
 478 }
 479
 480 impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> {
 481     fn visit_item(&mut self, item: &ast::Item) {
 482         let did = ast_util::local_def(item.id);
 483         let tcx = self.terms_cx.tcx;
 484
 485         match item.node {
 486             ast::ItemEnum(ref enum_definition, _) => {
 487                 // Hack: If we directly call `ty::enum_variants`, it
 488                 // annoyingly takes it upon itself to run off and
 489                 // evaluate the discriminants eagerly (*grumpy* that's
 490                 // not the typical pattern). This results in double
 491                 // error messages because typeck goes off and does
 492                 // this at a later time. All we really care about is
 493                 // the types of the variant arguments, so we just call
 494                 // `ty::VariantInfo::from_ast_variant()` ourselves
 495                 // here, mainly so as to mask the differences between
 496                 // struct-like enums and so forth.
 497                 for ast_variant in enum_definition.variants.iter() {
 498                     let variant =
 499                         ty::VariantInfo::from_ast_variant(tcx,
 500                                                           &**ast_variant,
 501                                                           /*discriminant*/ 0);
 502                     for arg_ty in variant.args.iter() {
 503                         self.add_constraints_from_ty(*arg_ty, self.covariant);
 504                     }
 505                 }
 506             }
 507
 508             ast::ItemStruct(..) => {
 509                 let struct_fields = ty::lookup_struct_fields(tcx, did);
 510                 for field_info in struct_fields.iter() {
 511                     assert_eq!(field_info.id.krate, ast::LOCAL_CRATE);
 512                     let field_ty = ty::node_id_to_type(tcx, field_info.id.node);
 513                     self.add_constraints_from_ty(field_ty, self.covariant);
 514                 }
 515             }
 516
 517             ast::ItemTrait(..) => {
 518                 let trait_items = ty::trait_items(tcx, did);
 519                 for trait_item in trait_items.iter() {
 520                     match *trait_item {
 521                         ty::MethodTraitItem(ref method) => {
 522                             self.add_constraints_from_sig(&method.fty.sig,
 523                                                           self.covariant);
 524                         }
 525                         ty::TypeTraitItem(_) => {}
 526                     }
 527                 }
 528             }
 529
 530             ast::ItemStatic(..) |
 531             ast::ItemFn(..) |
 532             ast::ItemMod(..) |
 533             ast::ItemForeignMod(..) |
 534             ast::ItemTy(..) |
 535             ast::ItemImpl(..) |
 536             ast::ItemMac(..) => {
 537                 visit::walk_item(self, item);
 538             }
 539         }
 540     }
 541 }
 542
 543 /// Is `param_id` a lifetime according to `map`?
 544 fn is_lifetime(map: &ast_map::Map, param_id: ast::NodeId) -> bool {
 545     match map.find(param_id) {
 546         Some(ast_map::NodeLifetime(..)) => true, _ => false
 547     }
 548 }
 549
 550 impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
 551     fn tcx(&self) -> &'a ty::ctxt<'tcx> {
 552         self.terms_cx.tcx
 553     }
 554
 555     fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
 556         match self.terms_cx.inferred_map.find(&param_id) {
 557             Some(&index) => index,
 558             None => {
 559                 self.tcx().sess.bug(format!(
 560                         "no inferred index entry for {}",
 561                         self.tcx().map.node_to_string(param_id)).as_slice());
 562             }
 563         }
 564     }
 565
 566     fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
 567         let tcx = self.terms_cx.tcx;
 568         assert!(is_lifetime(&tcx.map, param_id));
 569         match tcx.named_region_map.find(&param_id) {
 570             Some(&rl::DefEarlyBoundRegion(_, _, lifetime_decl_id))
 571                 => lifetime_decl_id,
 572             Some(_) => fail!("should not encounter non early-bound cases"),
 573
 574             // The lookup should only fail when `param_id` is
 575             // itself a lifetime binding: use it as the decl_id.
 576             None    => param_id,
 577         }
 578
 579     }
 580
 581     /// Is `param_id` a type parameter for which we infer variance?
 582     fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
 583         let result = self.terms_cx.inferred_map.contains_key(&param_id);
 584
 585         // To safe-guard against invalid inferred_map constructions,
 586         // double-check if variance is inferred at some use of a type
 587         // parameter (by inspecting parent of its binding declaration
 588         // to see if it is introduced by a type or by a fn/impl).
 589
 590         let check_result = |this:&ConstraintContext| -> bool {
 591             let tcx = this.terms_cx.tcx;
 592             let decl_id = this.find_binding_for_lifetime(param_id);
 593             // Currently only called on lifetimes; double-checking that.
 594             assert!(is_lifetime(&tcx.map, param_id));
 595             let parent_id = tcx.map.get_parent(decl_id);
 596             let parent = tcx.map.find(parent_id).unwrap_or_else(
 597                 || fail!("tcx.map missing entry for id: {}", parent_id));
 598
 599             let is_inferred;
 600             macro_rules! cannot_happen { () => { {
 601                 fail!("invalid parent: {:s} for {:s}",
 602                       tcx.map.node_to_string(parent_id),
 603                       tcx.map.node_to_string(param_id));
 604             } } }
 605
 606             match parent {
 607                 ast_map::NodeItem(p) => {
 608                     match p.node {
 609                         ast::ItemTy(..) |
 610                         ast::ItemEnum(..) |
 611                         ast::ItemStruct(..) |
 612                         ast::ItemTrait(..)   => is_inferred = true,
 613                         ast::ItemFn(..)      => is_inferred = false,
 614                         _                    => cannot_happen!(),
 615                     }
 616                 }
 617                 ast_map::NodeTraitItem(..)   => is_inferred = false,
 618                 ast_map::NodeImplItem(..)    => is_inferred = false,
 619                 _                            => cannot_happen!(),
 620             }
 621
 622             return is_inferred;
 623         };
 624
 625         assert_eq!(result, check_result(self));
 626
 627         return result;
 628     }
 629
 630     fn declared_variance(&self,
 631                          param_def_id: ast::DefId,
 632                          item_def_id: ast::DefId,
 633                          kind: ParamKind,
 634                          space: ParamSpace,
 635                          index: uint)
 636                          -> VarianceTermPtr<'a> {
 637         /*!
 638          * Returns a variance term representing the declared variance of
 639          * the type/region parameter with the given id.
 640          */
 641
 642         assert_eq!(param_def_id.krate, item_def_id.krate);
 643
 644         if self.invariant_lang_items[kind as uint] == Some(item_def_id) {
 645             self.invariant
 646         } else if self.covariant_lang_items[kind as uint] == Some(item_def_id) {
 647             self.covariant
 648         } else if self.contravariant_lang_items[kind as uint] == Some(item_def_id) {
 649             self.contravariant
 650         } else if kind == TypeParam && Some(item_def_id) == self.unsafe_lang_item {
 651             self.invariant
 652         } else if param_def_id.krate == ast::LOCAL_CRATE {
 653             // Parameter on an item defined within current crate:
 654             // variance not yet inferred, so return a symbolic
 655             // variance.
 656             let InferredIndex(index) = self.inferred_index(param_def_id.node);
 657             self.terms_cx.inferred_infos.get(index).term
 658         } else {
 659             // Parameter on an item defined within another crate:
 660             // variance already inferred, just look it up.
 661             let variances = ty::item_variances(self.tcx(), item_def_id);
 662             let variance = match kind {
 663                 TypeParam => *variances.types.get(space, index),
 664                 RegionParam => *variances.regions.get(space, index),
 665             };
 666             self.constant_term(variance)
 667         }
 668     }
 669
 670     fn add_constraint(&mut self,
 671                       InferredIndex(index): InferredIndex,
 672                       variance: VarianceTermPtr<'a>) {
 673         debug!("add_constraint(index={}, variance={})",
 674                 index, variance.to_string());
 675         self.constraints.push(Constraint { inferred: InferredIndex(index),
 676                                            variance: variance });
 677     }
 678
 679     fn contravariant(&mut self,
 680                      variance: VarianceTermPtr<'a>)
 681                      -> VarianceTermPtr<'a> {
 682         self.xform(variance, self.contravariant)
 683     }
 684
 685     fn invariant(&mut self,
 686                  variance: VarianceTermPtr<'a>)
 687                  -> VarianceTermPtr<'a> {
 688         self.xform(variance, self.invariant)
 689     }
 690
 691     fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
 692         match v {
 693             ty::Covariant => self.covariant,
 694             ty::Invariant => self.invariant,
 695             ty::Contravariant => self.contravariant,
 696             ty::Bivariant => self.bivariant,
 697         }
 698     }
 699
 700     fn xform(&mut self,
 701              v1: VarianceTermPtr<'a>,
 702              v2: VarianceTermPtr<'a>)
 703              -> VarianceTermPtr<'a> {
 704         match (*v1, *v2) {
 705             (_, ConstantTerm(ty::Covariant)) => {
 706                 // Applying a "covariant" transform is always a no-op
 707                 v1
 708             }
 709
 710             (ConstantTerm(c1), ConstantTerm(c2)) => {
 711                 self.constant_term(c1.xform(c2))
 712             }
 713
 714             _ => {
 715                 self.terms_cx.arena.alloc(|| TransformTerm(v1, v2))
 716             }
 717         }
 718     }
 719
 720     /// Adds constraints appropriate for an instance of `ty` appearing
 721     /// in a context with ambient variance `variance`
 722     fn add_constraints_from_ty(&mut self,
 723                                ty: ty::t,
 724                                variance: VarianceTermPtr<'a>) {
 725         debug!("add_constraints_from_ty(ty={})", ty.repr(self.tcx()));
 726
 727         match ty::get(ty).sty {
 728             ty::ty_nil | ty::ty_bot | ty::ty_bool |
 729             ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) |
 730             ty::ty_float(_) | ty::ty_str => {
 731                 /* leaf type -- noop */
 732             }
 733
 734             ty::ty_unboxed_closure(_, region) => {
 735                 let contra = self.contravariant(variance);
 736                 self.add_constraints_from_region(region, contra);
 737             }
 738
 739             ty::ty_rptr(region, ref mt) => {
 740                 let contra = self.contravariant(variance);
 741                 self.add_constraints_from_region(region, contra);
 742                 self.add_constraints_from_mt(mt, variance);
 743             }
 744
 745             ty::ty_uniq(typ) | ty::ty_box(typ) | ty::ty_vec(typ, _) | ty::ty_open(typ) => {
 746                 self.add_constraints_from_ty(typ, variance);
 747             }
 748
 749             ty::ty_ptr(ref mt) => {
 750                 self.add_constraints_from_mt(mt, variance);
 751             }
 752
 753             ty::ty_tup(ref subtys) => {
 754                 for &subty in subtys.iter() {
 755                     self.add_constraints_from_ty(subty, variance);
 756                 }
 757             }
 758
 759             ty::ty_enum(def_id, ref substs) |
 760             ty::ty_struct(def_id, ref substs) => {
 761                 let item_type = ty::lookup_item_type(self.tcx(), def_id);
 762                 let generics = &item_type.generics;
 763
 764                 // All type parameters on enums and structs should be
 765                 // in the TypeSpace.
 766                 assert!(generics.types.is_empty_in(subst::SelfSpace));
 767                 assert!(generics.types.is_empty_in(subst::FnSpace));
 768                 assert!(generics.regions.is_empty_in(subst::SelfSpace));
 769                 assert!(generics.regions.is_empty_in(subst::FnSpace));
 770
 771                 self.add_constraints_from_substs(
 772                     def_id,
 773                     generics.types.get_slice(subst::TypeSpace),
 774                     generics.regions.get_slice(subst::TypeSpace),
 775                     substs,
 776                     variance);
 777             }
 778
 779             ty::ty_trait(box ty::TyTrait { def_id, ref substs, .. }) => {
 780                 let trait_def = ty::lookup_trait_def(self.tcx(), def_id);
 781                 let generics = &trait_def.generics;
 782
 783                 // Traits DO have a Self type parameter, but it is
 784                 // erased from object types.
 785                 assert!(!generics.types.is_empty_in(subst::SelfSpace) &&
 786                         substs.types.is_empty_in(subst::SelfSpace));
 787
 788                 // Traits never declare region parameters in the self
 789                 // space.
 790                 assert!(generics.regions.is_empty_in(subst::SelfSpace));
 791
 792                 // Traits never declare type/region parameters in the
 793                 // fn space.
 794                 assert!(generics.types.is_empty_in(subst::FnSpace));
 795                 assert!(generics.regions.is_empty_in(subst::FnSpace));
 796
 797                 self.add_constraints_from_substs(
 798                     def_id,
 799                     generics.types.get_slice(subst::TypeSpace),
 800                     generics.regions.get_slice(subst::TypeSpace),
 801                     substs,
 802                     variance);
 803             }
 804
 805             ty::ty_param(ty::ParamTy { def_id: ref def_id, .. }) => {
 806                 assert_eq!(def_id.krate, ast::LOCAL_CRATE);
 807                 match self.terms_cx.inferred_map.find(&def_id.node) {
 808                     Some(&index) => {
 809                         self.add_constraint(index, variance);
 810                     }
 811                     None => {
 812                         // We do not infer variance for type parameters
 813                         // declared on methods. They will not be present
 814                         // in the inferred_map.
 815                     }
 816                 }
 817             }
 818
 819             ty::ty_bare_fn(ty::BareFnTy { ref sig, .. }) |
 820             ty::ty_closure(box ty::ClosureTy {
 821                     ref sig,
 822                     store: ty::UniqTraitStore,
 823                     ..
 824                 }) => {
 825                 self.add_constraints_from_sig(sig, variance);
 826             }
 827
 828             ty::ty_closure(box ty::ClosureTy { ref sig,
 829                     store: ty::RegionTraitStore(region, _), .. }) => {
 830                 let contra = self.contravariant(variance);
 831                 self.add_constraints_from_region(region, contra);
 832                 self.add_constraints_from_sig(sig, variance);
 833             }
 834
 835             ty::ty_infer(..) | ty::ty_err => {
 836                 self.tcx().sess.bug(
 837                     format!("unexpected type encountered in \
 838                             variance inference: {}",
 839                             ty.repr(self.tcx())).as_slice());
 840             }
 841         }
 842     }
 843
 844
 845     /// Adds constraints appropriate for a nominal type (enum, struct,
 846     /// object, etc) appearing in a context with ambient variance `variance`
 847     fn add_constraints_from_substs(&mut self,
 848                                    def_id: ast::DefId,
 849                                    type_param_defs: &[ty::TypeParameterDef],
 850                                    region_param_defs: &[ty::RegionParameterDef],
 851                                    substs: &subst::Substs,
 852                                    variance: VarianceTermPtr<'a>) {
 853         debug!("add_constraints_from_substs(def_id={:?})", def_id);
 854
 855         for p in type_param_defs.iter() {
 856             let variance_decl =
 857                 self.declared_variance(p.def_id, def_id, TypeParam,
 858                                        p.space, p.index);
 859             let variance_i = self.xform(variance, variance_decl);
 860             let substs_ty = *substs.types.get(p.space, p.index);
 861             self.add_constraints_from_ty(substs_ty, variance_i);
 862         }
 863
 864         for p in region_param_defs.iter() {
 865             let variance_decl =
 866                 self.declared_variance(p.def_id, def_id,
 867                                        RegionParam, p.space, p.index);
 868             let variance_i = self.xform(variance, variance_decl);
 869             let substs_r = *substs.regions().get(p.space, p.index);
 870             self.add_constraints_from_region(substs_r, variance_i);
 871         }
 872     }
 873
 874     /// Adds constraints appropriate for a function with signature
 875     /// `sig` appearing in a context with ambient variance `variance`
 876     fn add_constraints_from_sig(&mut self,
 877                                 sig: &ty::FnSig,
 878                                 variance: VarianceTermPtr<'a>) {
 879         let contra = self.contravariant(variance);
 880         for &input in sig.inputs.iter() {
 881             self.add_constraints_from_ty(input, contra);
 882         }
 883         self.add_constraints_from_ty(sig.output, variance);
 884     }
 885
 886     /// Adds constraints appropriate for a region appearing in a
 887     /// context with ambient variance `variance`
 888     fn add_constraints_from_region(&mut self,
 889                                    region: ty::Region,
 890                                    variance: VarianceTermPtr<'a>) {
 891         match region {
 892             ty::ReEarlyBound(param_id, _, _, _) => {
 893                 if self.is_to_be_inferred(param_id) {
 894                     let index = self.inferred_index(param_id);
 895                     self.add_constraint(index, variance);
 896                 }
 897             }
 898
 899             ty::ReStatic => { }
 900
 901             ty::ReLateBound(..) => {
 902                 // We do not infer variance for region parameters on
 903                 // methods or in fn types.
 904             }
 905
 906             ty::ReFree(..) | ty::ReScope(..) | ty::ReInfer(..) |
 907             ty::ReEmpty => {
 908                 // We don't expect to see anything but 'static or bound
 909                 // regions when visiting member types or method types.
 910                 self.tcx()
 911                     .sess
 912                     .bug(format!("unexpected region encountered in variance \
 913                                   inference: {}",
 914                                  region.repr(self.tcx())).as_slice());
 915             }
 916         }
 917     }
 918
 919     /// Adds constraints appropriate for a mutability-type pair
 920     /// appearing in a context with ambient variance `variance`
 921     fn add_constraints_from_mt(&mut self,
 922                                mt: &ty::mt,
 923                                variance: VarianceTermPtr<'a>) {
 924         match mt.mutbl {
 925             ast::MutMutable => {
 926                 let invar = self.invariant(variance);
 927                 self.add_constraints_from_ty(mt.ty, invar);
 928             }
 929
 930             ast::MutImmutable => {
 931                 self.add_constraints_from_ty(mt.ty, variance);
 932             }
 933         }
 934     }
 935 }
 936
 937 /**************************************************************************
 938  * Constraint solving
 939  *
 940  * The final phase iterates over the constraints, refining the variance
 941  * for each inferred until a fixed point is reached. This will be the
 942  * optimal solution to the constraints. The final variance for each
 943  * inferred is then written into the `variance_map` in the tcx.
 944  */
 945
 946 struct SolveContext<'a, 'tcx: 'a> {
 947     terms_cx: TermsContext<'a, 'tcx>,
 948     constraints: Vec<Constraint<'a>> ,
 949
 950     // Maps from an InferredIndex to the inferred value for that variable.
 951     solutions: Vec<ty::Variance> }
 952
 953 fn solve_constraints(constraints_cx: ConstraintContext) {
 954     let ConstraintContext { terms_cx, constraints, .. } = constraints_cx;
 955     let solutions = Vec::from_elem(terms_cx.num_inferred(), ty::Bivariant);
 956     let mut solutions_cx = SolveContext {
 957         terms_cx: terms_cx,
 958         constraints: constraints,
 959         solutions: solutions
 960     };
 961     solutions_cx.solve();
 962     solutions_cx.write();
 963 }
 964
 965 impl<'a, 'tcx> SolveContext<'a, 'tcx> {
 966     fn solve(&mut self) {
 967         // Propagate constraints until a fixed point is reached.  Note
 968         // that the maximum number of iterations is 2C where C is the
 969         // number of constraints (each variable can change values at most
 970         // twice). Since number of constraints is linear in size of the
 971         // input, so is the inference process.
 972         let mut changed = true;
 973         while changed {
 974             changed = false;
 975
 976             for constraint in self.constraints.iter() {
 977                 let Constraint { inferred, variance: term } = *constraint;
 978                 let InferredIndex(inferred) = inferred;
 979                 let variance = self.evaluate(term);
 980                 let old_value = *self.solutions.get(inferred);
 981                 let new_value = glb(variance, old_value);
 982                 if old_value != new_value {
 983                     debug!("Updating inferred {} (node {}) \
 984                             from {} to {} due to {}",
 985                             inferred,
 986                             self.terms_cx
 987                                 .inferred_infos
 988                                 .get(inferred)
 989                                 .param_id,
 990                             old_value,
 991                             new_value,
 992                             term.to_string());
 993
 994                     *self.solutions.get_mut(inferred) = new_value;
 995                     changed = true;
 996                 }
 997             }
 998         }
 999     }
1000
1001     fn write(&self) {
1002         // Collect all the variances for a particular item and stick
1003         // them into the variance map. We rely on the fact that we
1004         // generate all the inferreds for a particular item
1005         // consecutively (that is, we collect solutions for an item
1006         // until we see a new item id, and we assume (1) the solutions
1007         // are in the same order as the type parameters were declared
1008         // and (2) all solutions or a given item appear before a new
1009         // item id).
1010
1011         let tcx = self.terms_cx.tcx;
1012         let solutions = &self.solutions;
1013         let inferred_infos = &self.terms_cx.inferred_infos;
1014         let mut index = 0;
1015         let num_inferred = self.terms_cx.num_inferred();
1016         while index < num_inferred {
1017             let item_id = inferred_infos.get(index).item_id;
1018             let mut types = VecPerParamSpace::empty();
1019             let mut regions = VecPerParamSpace::empty();
1020
1021             while index < num_inferred &&
1022                   inferred_infos.get(index).item_id == item_id {
1023                 let info = inferred_infos.get(index);
1024                 let variance = *solutions.get(index);
1025                 debug!("Index {} Info {} / {} / {} Variance {}",
1026                        index, info.index, info.kind, info.space, variance);
1027                 match info.kind {
1028                     TypeParam => {
1029                         types.push(info.space, variance);
1030                     }
1031                     RegionParam => {
1032                         regions.push(info.space, variance);
1033                     }
1034                 }
1035                 index += 1;
1036             }
1037
1038             let item_variances = ty::ItemVariances {
1039                 types: types,
1040                 regions: regions
1041             };
1042             debug!("item_id={} item_variances={}",
1043                     item_id,
1044                     item_variances.repr(tcx));
1045
1046             let item_def_id = ast_util::local_def(item_id);
1047
1048             // For unit testing: check for a special "rustc_variance"
1049             // attribute and report an error with various results if found.
1050             if ty::has_attr(tcx, item_def_id, "rustc_variance") {
1051                 let found = item_variances.repr(tcx);
1052                 tcx.sess.span_err(tcx.map.span(item_id), found.as_slice());
1053             }
1054
1055             let newly_added = tcx.item_variance_map.borrow_mut()
1056                                  .insert(item_def_id, Rc::new(item_variances));
1057             assert!(newly_added);
1058         }
1059     }
1060
1061     fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance {
1062         match *term {
1063             ConstantTerm(v) => {
1064                 v
1065             }
1066
1067             TransformTerm(t1, t2) => {
1068                 let v1 = self.evaluate(t1);
1069                 let v2 = self.evaluate(t2);
1070                 v1.xform(v2)
1071             }
1072
1073             InferredTerm(InferredIndex(index)) => {
1074                 *self.solutions.get(index)
1075             }
1076         }
1077     }
1078 }
1079
1080 /**************************************************************************
1081  * Miscellany transformations on variance
1082  */
1083
1084 trait Xform {
1085     fn xform(self, v: Self) -> Self;
1086 }
1087
1088 impl Xform for ty::Variance {
1089     fn xform(self, v: ty::Variance) -> ty::Variance {
1090         // "Variance transformation", Figure 1 of The Paper
1091         match (self, v) {
1092             // Figure 1, column 1.
1093             (ty::Covariant, ty::Covariant) => ty::Covariant,
1094             (ty::Covariant, ty::Contravariant) => ty::Contravariant,
1095             (ty::Covariant, ty::Invariant) => ty::Invariant,
1096             (ty::Covariant, ty::Bivariant) => ty::Bivariant,
1097
1098             // Figure 1, column 2.
1099             (ty::Contravariant, ty::Covariant) => ty::Contravariant,
1100             (ty::Contravariant, ty::Contravariant) => ty::Covariant,
1101             (ty::Contravariant, ty::Invariant) => ty::Invariant,
1102             (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
1103
1104             // Figure 1, column 3.
1105             (ty::Invariant, _) => ty::Invariant,
1106
1107             // Figure 1, column 4.
1108             (ty::Bivariant, _) => ty::Bivariant,
1109         }
1110     }
1111 }
1112
1113 fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance {
1114     // Greatest lower bound of the variance lattice as
1115     // defined in The Paper:
1116     //
1117     //       *
1118     //    -     +
1119     //       o
1120     match (v1, v2) {
1121         (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
1122
1123         (ty::Covariant, ty::Contravariant) => ty::Invariant,
1124         (ty::Contravariant, ty::Covariant) => ty::Invariant,
1125
1126         (ty::Covariant, ty::Covariant) => ty::Covariant,
1127
1128         (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
1129
1130         (x, ty::Bivariant) | (ty::Bivariant, x) => x,
1131     }
1132 }