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