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