src/librustc_typeck/variance.rs

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