Introduce new variance inference pass that replaces (and generalizes) old

region-parameterization/variance inference. We now compute variance for
type parameters but do not make use of it (most of the way towards #3598).

23 files changed, 1278 insertions, 807 deletions

diff --git a/src/librustc/metadata/common.rs b/src/librustc/metadata/common.rs
index 05d40bbb6ae..5e6d0f27615 100644
--- a/src/librustc/metadata/common.rs
+++ b/src/librustc/metadata/common.rs
@@ -89,7 +89,7 @@ pub static tag_path_elt_name: uint = 0x43u;
 pub static tag_item_field: uint = 0x44u;
 pub static tag_struct_mut: uint = 0x45u;
 
-pub static tag_region_param: uint = 0x46u;
+pub static tag_item_variances: uint = 0x46;
 pub static tag_mod_impl_trait: uint = 0x47u;
 /*
   trait items contain tag_item_trait_method elements,
diff --git a/src/librustc/metadata/csearch.rs b/src/librustc/metadata/csearch.rs
index 436b4c3df6b..fdda6b38462 100644
--- a/src/librustc/metadata/csearch.rs
+++ b/src/librustc/metadata/csearch.rs
@@ -14,7 +14,6 @@
 use metadata::common::*;
 use metadata::cstore;
 use metadata::decoder;
-use metadata;
 use middle::ty;
 use middle::typeck;
 
@@ -144,6 +143,12 @@ pub fn get_trait_method_def_ids(cstore: @mut cstore::CStore,
     decoder::get_trait_method_def_ids(cdata, def.node)
 }
 
+pub fn get_item_variances(cstore: @mut cstore::CStore,
+                          def: ast::DefId) -> ty::ItemVariances {
+    let cdata = cstore::get_crate_data(cstore, def.crate);
+    decoder::get_item_variances(cdata, def.node)
+}
+
 pub fn get_provided_trait_methods(tcx: ty::ctxt,
                                   def: ast::DefId)
                                -> ~[@ty::Method] {
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 3b4e29c97c0..b63d9320bd6 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -1088,6 +1088,14 @@ pub fn get_trait_method_def_ids(cdata: Cmd,
     result
 }
 
+pub fn get_item_variances(cdata: Cmd, id: ast::NodeId) -> ty::ItemVariances {
+    let data = cdata.data;
+    let item_doc = lookup_item(id, data);
+    let variance_doc = reader::get_doc(item_doc, tag_item_variances);
+    let mut decoder = reader::Decoder(variance_doc);
+    Decodable::decode(&mut decoder)
+}
+
 pub fn get_provided_trait_methods(intr: @ident_interner, cdata: Cmd,
                                   id: ast::NodeId, tcx: ty::ctxt) ->
         ~[@ty::Method] {
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index 76c49da5861..9ce0b676e7e 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -211,6 +211,15 @@ fn encode_region_param_defs(ebml_w: &mut writer::Encoder,
     }
 }
 
+fn encode_item_variances(ebml_w: &mut writer::Encoder,
+                         ecx: &EncodeContext,
+                         id: ast::NodeId) {
+    let v = ty::item_variances(ecx.tcx, ast_util::local_def(id));
+    ebml_w.start_tag(tag_item_variances);
+    v.encode(ebml_w);
+    ebml_w.end_tag();
+}
+
 fn encode_bounds_and_type(ebml_w: &mut writer::Encoder,
                           ecx: &EncodeContext,
                           tpt: &ty::ty_param_bounds_and_ty) {
@@ -992,6 +1001,7 @@ fn encode_info_for_item(ecx: &EncodeContext,
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, def_id);
         encode_family(ebml_w, 't');
+        encode_item_variances(ebml_w, ecx, item.id);
         encode_bounds_and_type(ebml_w, ecx, &lookup_item_type(tcx, def_id));
         encode_name(ecx, ebml_w, item.ident);
         encode_attributes(ebml_w, item.attrs);
@@ -1032,6 +1042,7 @@ fn encode_info_for_item(ecx: &EncodeContext,
         encode_family(ebml_w, 'S');
         encode_bounds_and_type(ebml_w, ecx, &lookup_item_type(tcx, def_id));
 
+        encode_item_variances(ebml_w, ecx, item.id);
         encode_name(ecx, ebml_w, item.ident);
         encode_attributes(ebml_w, item.attrs);
         encode_path(ecx, ebml_w, path, ast_map::path_name(item.ident));
@@ -1138,6 +1149,7 @@ fn encode_info_for_item(ecx: &EncodeContext,
         ebml_w.start_tag(tag_items_data_item);
         encode_def_id(ebml_w, def_id);
         encode_family(ebml_w, 'I');
+        encode_item_variances(ebml_w, ecx, item.id);
         let trait_def = ty::lookup_trait_def(tcx, def_id);
         encode_ty_type_param_defs(ebml_w, ecx,
                                   trait_def.generics.type_param_defs,
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 29acfe14381..80103aa4106 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -22,22 +22,14 @@ Most of the documentation on regions can be found in
 
 
 use driver::session::Session;
-use metadata::csearch;
-use middle::resolve;
-use middle::ty::{region_variance, rv_covariant, rv_invariant};
-use middle::ty::{rv_contravariant, FreeRegion};
+use middle::ty::{FreeRegion};
 use middle::ty;
 
 use std::hashmap::{HashMap, HashSet};
-use syntax::ast_map;
 use syntax::codemap::Span;
-use syntax::print::pprust;
-use syntax::parse::token;
-use syntax::parse::token::special_idents;
 use syntax::{ast, visit};
 use syntax::visit::{Visitor,fn_kind};
 use syntax::ast::{Block,item,fn_decl,NodeId,Arm,Pat,Stmt,Expr,Local};
-use syntax::ast::{Ty,TypeMethod,struct_field};
 
 /**
 The region maps encode information about region relationships.
@@ -74,7 +66,6 @@ pub struct Context {
 
 struct RegionResolutionVisitor {
     sess: Session,
-    def_map: resolve::DefMap,
 
     // Generated maps:
     region_maps: @mut RegionMaps,
@@ -504,7 +495,6 @@ impl Visitor<Context> for RegionResolutionVisitor {
 }
 
 pub fn resolve_crate(sess: Session,
-                     def_map: resolve::DefMap,
                      crate: &ast::Crate) -> @mut RegionMaps
 {
     let region_maps = @mut RegionMaps {
@@ -516,483 +506,9 @@ pub fn resolve_crate(sess: Session,
                       var_parent: None};
     let mut visitor = RegionResolutionVisitor {
         sess: sess,
-        def_map: def_map,
         region_maps: region_maps,
     };
     visit::walk_crate(&mut visitor, crate, cx);
     return region_maps;
 }
 
-// ___________________________________________________________________________
-// Determining region parameterization
-//
-// Infers which type defns must be region parameterized---this is done
-// by scanning their contents to see whether they reference a region
-// type, directly or indirectly.  This is a fixed-point computation.
-//
-// We do it in two passes.  First we walk the AST and construct a map
-// from each type defn T1 to other defns which make use of it.  For example,
-// if we have a type like:
-//
-//    type S = *int;
-//    type T = S;
-//
-// Then there would be a map entry from S to T.  During the same walk,
-// we also construct add any types that reference regions to a set and
-// a worklist.  We can then process the worklist, propagating indirect
-// dependencies until a fixed point is reached.
-
-pub type region_paramd_items = @mut HashMap<ast::NodeId, region_variance>;
-
-#[deriving(Eq)]
-pub struct region_dep {
-    ambient_variance: region_variance,
-    id: ast::NodeId
-}
-
-pub struct DetermineRpCtxt {
-    sess: Session,
-    ast_map: ast_map::map,
-    def_map: resolve::DefMap,
-    region_paramd_items: region_paramd_items,
-    dep_map: @mut HashMap<ast::NodeId, @mut ~[region_dep]>,
-    worklist: ~[ast::NodeId],
-
-    // the innermost enclosing item id
-    item_id: ast::NodeId,
-
-    // true when we are within an item but not within a method.
-    // see long discussion on region_is_relevant().
-    anon_implies_rp: bool,
-
-    // encodes the context of the current type; invariant if
-    // mutable, covariant otherwise
-    ambient_variance: region_variance,
-}
-
-pub fn join_variance(variance1: region_variance,
-                     variance2: region_variance)
-                  -> region_variance {
-    match (variance1, variance2) {
-      (rv_invariant, _) => {rv_invariant}
-      (_, rv_invariant) => {rv_invariant}
-      (rv_covariant, rv_contravariant) => {rv_invariant}
-      (rv_contravariant, rv_covariant) => {rv_invariant}
-      (rv_covariant, rv_covariant) => {rv_covariant}
-      (rv_contravariant, rv_contravariant) => {rv_contravariant}
-    }
-}
-
-/// Combines the ambient variance with the variance of a
-/// particular site to yield the final variance of the reference.
-///
-/// Example: if we are checking function arguments then the ambient
-/// variance is contravariant.  If we then find a `&'r T` pointer, `r`
-/// appears in a co-variant position.  This implies that this
-/// occurrence of `r` is contra-variant with respect to the current
-/// item, and hence the function returns `rv_contravariant`.
-pub fn add_variance(ambient_variance: region_variance,
-                    variance: region_variance)
-                 -> region_variance {
-    match (ambient_variance, variance) {
-      (rv_invariant, _) => rv_invariant,
-      (_, rv_invariant) => rv_invariant,
-      (rv_covariant, c) => c,
-      (c, rv_covariant) => c,
-      (rv_contravariant, rv_contravariant) => rv_covariant
-    }
-}
-
-impl DetermineRpCtxt {
-    pub fn add_variance(&self, variance: region_variance) -> region_variance {
-        add_variance(self.ambient_variance, variance)
-    }
-
-    /// Records that item `id` is region-parameterized with the
-    /// variance `variance`.  If `id` was already parameterized, then
-    /// the new variance is joined with the old variance.
-    pub fn add_rp(&mut self, id: ast::NodeId, variance: region_variance) {
-        assert!(id != 0);
-        let old_variance = self.region_paramd_items.find(&id).map(|x| *x);
-        let joined_variance = match old_variance {
-          None => variance,
-          Some(v) => join_variance(v, variance)
-        };
-
-        debug!("add_rp() variance for {}: {:?} == {:?} ^ {:?}",
-               ast_map::node_id_to_str(self.ast_map, id,
-                                       token::get_ident_interner()),
-               joined_variance, old_variance, variance);
-
-        if Some(joined_variance) != old_variance {
-            let region_paramd_items = self.region_paramd_items;
-            region_paramd_items.insert(id, joined_variance);
-            self.worklist.push(id);
-        }
-    }
-
-    /// Indicates that the region-parameterization of the current item
-    /// is dependent on the region-parameterization of the item
-    /// `from`.  Put another way, it indicates that the current item
-    /// contains a value of type `from`, so if `from` is
-    /// region-parameterized, so is the current item.
-    pub fn add_dep(&mut self, from: ast::NodeId) {
-        debug!("add dependency from {} -> {} ({} -> {}) with variance {:?}",
-               from, self.item_id,
-               ast_map::node_id_to_str(self.ast_map, from,
-                                       token::get_ident_interner()),
-               ast_map::node_id_to_str(self.ast_map, self.item_id,
-                                       token::get_ident_interner()),
-               self.ambient_variance);
-        let vec = do self.dep_map.find_or_insert_with(from) |_| {
-            @mut ~[]
-        };
-        let dep = region_dep {
-            ambient_variance: self.ambient_variance,
-            id: self.item_id
-        };
-        if !vec.iter().any(|x| x == &dep) { vec.push(dep); }
-    }
-
-    // Determines whether a reference to a region that appears in the
-    // AST implies that the enclosing type is region-parameterized (RP).
-    // This point is subtle.  Here are some examples to make it more
-    // concrete.
-    //
-    // 1. impl foo for &int { ... }
-    // 2. impl foo for &'self int { ... }
-    // 3. impl foo for bar { fn m(@self) -> &'self int { ... } }
-    // 4. impl foo for bar { fn m(&self) -> &'self int { ... } }
-    // 5. impl foo for bar { fn m(&self) -> &int { ... } }
-    //
-    // In case 1, the anonymous region is being referenced,
-    // but it appears in a context where the anonymous region
-    // resolves to self, so the impl foo is RP.
-    //
-    // In case 2, the self parameter is written explicitly.
-    //
-    // In case 3, the method refers to the region `self`, so that
-    // implies that the impl must be region parameterized.  (If the
-    // type bar is not region parameterized, that is an error, because
-    // the self region is effectively unconstrained, but that is
-    // detected elsewhere).
-    //
-    // In case 4, the method refers to the region `self`, but the
-    // `self` region is bound by the `&self` receiver, and so this
-    // does not require that `bar` be RP.
-    //
-    // In case 5, the anonymous region is referenced, but it
-    // bound by the method, so it does not refer to self.  This impl
-    // need not be region parameterized.
-    //
-    // Normally, & or &self implies that the enclosing item is RP.
-    // However, within a function, & is always bound.  Within a method
-    // with &self type, &self is also bound.  We detect those last two
-    // cases via flags (anon_implies_rp and self_implies_rp) that are
-    // true when the anon or self region implies RP.
-    pub fn region_is_relevant(&self, r: &Option<ast::Lifetime>) -> bool {
-        match r {
-            &None => {
-                self.anon_implies_rp
-            }
-            &Some(ref l) if l.ident == special_idents::statik => {
-                false
-            }
-            &Some(ref l) if l.ident == special_idents::self_ => {
-                true
-            }
-            &Some(_) => {
-                false
-            }
-        }
-    }
-
-    pub fn with(@mut self,
-                item_id: ast::NodeId,
-                anon_implies_rp: bool,
-                f: &fn()) {
-        let old_item_id = self.item_id;
-        let old_anon_implies_rp = self.anon_implies_rp;
-        self.item_id = item_id;
-        self.anon_implies_rp = anon_implies_rp;
-        debug!("with_item_id({}, {})",
-               item_id,
-               anon_implies_rp);
-        let _i = ::util::common::indenter();
-        f();
-        self.item_id = old_item_id;
-        self.anon_implies_rp = old_anon_implies_rp;
-    }
-
-    pub fn with_ambient_variance(@mut self,
-                                 variance: region_variance,
-                                 f: &fn()) {
-        let old_ambient_variance = self.ambient_variance;
-        self.ambient_variance = self.add_variance(variance);
-        f();
-        self.ambient_variance = old_ambient_variance;
-    }
-}
-
-fn determine_rp_in_item(visitor: &mut DetermineRpVisitor,
-                        item: @ast::item) {
-    do visitor.cx.with(item.id, true) {
-        visit::walk_item(visitor, item, ());
-    }
-}
-
-fn determine_rp_in_fn(visitor: &mut DetermineRpVisitor,
-                      fk: &visit::fn_kind,
-                      decl: &ast::fn_decl,
-                      body: &ast::Block,
-                      _: Span,
-                      _: ast::NodeId) {
-    let cx = visitor.cx;
-    do cx.with(cx.item_id, false) {
-        do cx.with_ambient_variance(rv_contravariant) {
-            for a in decl.inputs.iter() {
-                visitor.visit_ty(&a.ty, ());
-            }
-        }
-        visitor.visit_ty(&decl.output, ());
-        let generics = visit::generics_of_fn(fk);
-        visitor.visit_generics(&generics, ());
-        visitor.visit_block(body, ());
-    }
-}
-
-fn determine_rp_in_ty_method(visitor: &mut DetermineRpVisitor,
-                             ty_m: &ast::TypeMethod) {
-    let cx = visitor.cx;
-    do cx.with(cx.item_id, false) {
-        visit::walk_ty_method(visitor, ty_m, ());
-    }
-}
-
-fn determine_rp_in_ty(visitor: &mut DetermineRpVisitor,
-                      ty: &ast::Ty) {
-    let cx = visitor.cx;
-
-    // we are only interested in types that will require an item to
-    // be region-parameterized.  if cx.item_id is zero, then this type
-    // is not a member of a type defn nor is it a constitutent of an
-    // impl etc.  So we can ignore it and its components.
-    if cx.item_id == 0 { return; }
-
-    // if this type directly references a region pointer like &'r ty,
-    // add to the worklist/set.  Note that &'r ty is contravariant with
-    // respect to &r, because &'r ty can be used whereever a *smaller*
-    // region is expected (and hence is a supertype of those
-    // locations)
-    let sess = cx.sess;
-    match ty.node {
-        ast::ty_rptr(ref r, _) => {
-            debug!("referenced rptr type {}",
-                   pprust::ty_to_str(ty, sess.intr()));
-
-            if cx.region_is_relevant(r) {
-                let rv = cx.add_variance(rv_contravariant);
-                cx.add_rp(cx.item_id, rv)
-            }
-        }
-
-        ast::ty_closure(ref f) => {
-            debug!("referenced fn type: {}",
-                   pprust::ty_to_str(ty, sess.intr()));
-            match f.region {
-                Some(_) => {
-                    if cx.region_is_relevant(&f.region) {
-                        let rv = cx.add_variance(rv_contravariant);
-                        cx.add_rp(cx.item_id, rv)
-                    }
-                }
-                None => {
-                    if f.sigil == ast::BorrowedSigil && cx.anon_implies_rp {
-                        let rv = cx.add_variance(rv_contravariant);
-                        cx.add_rp(cx.item_id, rv)
-                    }
-                }
-            }
-        }
-
-        _ => {}
-    }
-
-    // if this references another named type, add the dependency
-    // to the dep_map.  If the type is not defined in this crate,
-    // then check whether it is region-parameterized and consider
-    // that as a direct dependency.
-    match ty.node {
-      ast::ty_path(ref path, _, id) => {
-        match cx.def_map.find(&id) {
-          Some(&ast::DefTy(did)) |
-          Some(&ast::DefTrait(did)) |
-          Some(&ast::DefStruct(did)) => {
-            if did.crate == ast::LOCAL_CRATE {
-                if cx.region_is_relevant(&path.segments.last().lifetime) {
-                    cx.add_dep(did.node);
-                }
-            } else {
-                let cstore = sess.cstore;
-                match csearch::get_region_param(cstore, did) {
-                  None => {}
-                  Some(variance) => {
-                    debug!("reference to external, rp'd type {}",
-                           pprust::ty_to_str(ty, sess.intr()));
-                    if cx.region_is_relevant(&path.segments.last().lifetime) {
-                        let rv = cx.add_variance(variance);
-                        cx.add_rp(cx.item_id, rv)
-                    }
-                  }
-                }
-            }
-          }
-          _ => {}
-        }
-      }
-      _ => {}
-    }
-
-    match ty.node {
-      ast::ty_box(ref mt) | ast::ty_uniq(ref mt) | ast::ty_vec(ref mt) |
-      ast::ty_rptr(_, ref mt) | ast::ty_ptr(ref mt) => {
-        visit_mt(visitor, mt);
-      }
-
-      ast::ty_path(ref path, _, _) => {
-        // type parameters are---for now, anyway---always invariant
-        do cx.with_ambient_variance(rv_invariant) {
-            for tp in path.segments.iter().flat_map(|s| s.types.iter()) {
-                visitor.visit_ty(tp, ());
-            }
-        }
-      }
-
-      ast::ty_closure(@ast::TyClosure {decl: ref decl, _}) |
-      ast::ty_bare_fn(@ast::TyBareFn {decl: ref decl, _}) => {
-        // fn() binds the & region, so do not consider &T types that
-        // appear *inside* a fn() type to affect the enclosing item:
-        do cx.with(cx.item_id, false) {
-            // parameters are contravariant
-            do cx.with_ambient_variance(rv_contravariant) {
-                for a in decl.inputs.iter() {
-                    visitor.visit_ty(&a.ty, ());
-                }
-            }
-            visitor.visit_ty(&decl.output, ());
-        }
-      }
-
-      _ => {
-        visit::walk_ty(visitor, ty, ());
-      }
-    }
-
-    fn visit_mt(visitor: &mut DetermineRpVisitor,
-                mt: &ast::mt) {
-        let cx = visitor.cx;
-        // mutability is invariant
-        if mt.mutbl == ast::MutMutable {
-            do cx.with_ambient_variance(rv_invariant) {
-                visitor.visit_ty(mt.ty, ());
-            }
-        } else {
-            visitor.visit_ty(mt.ty, ());
-        }
-    }
-}
-
-fn determine_rp_in_struct_field(visitor: &mut DetermineRpVisitor,
-                                cm: @ast::struct_field) {
-    visit::walk_struct_field(visitor, cm, ());
-}
-
-struct DetermineRpVisitor {
-    cx: @mut DetermineRpCtxt
-}
-
-impl Visitor<()> for DetermineRpVisitor {
-
-    fn visit_fn(&mut self, fk:&fn_kind, fd:&fn_decl,
-                b:&Block, s:Span, n:NodeId, _:()) {
-        determine_rp_in_fn(self, fk, fd, b, s, n);
-    }
-    fn visit_item(&mut self, i:@item, _:()) {
-        determine_rp_in_item(self, i);
-    }
-    fn visit_ty(&mut self, t:&Ty, _:()) {
-        determine_rp_in_ty(self, t);
-    }
-    fn visit_ty_method(&mut self, t:&TypeMethod, _:()) {
-        determine_rp_in_ty_method(self, t);
-    }
-    fn visit_struct_field(&mut self, s:@struct_field, _:()) {
-        determine_rp_in_struct_field(self, s);
-    }
-
-}
-
-pub fn determine_rp_in_crate(sess: Session,
-                             ast_map: ast_map::map,
-                             def_map: resolve::DefMap,
-                             crate: &ast::Crate)
-                          -> region_paramd_items {
-    let cx = @mut DetermineRpCtxt {
-        sess: sess,
-        ast_map: ast_map,
-        def_map: def_map,
-        region_paramd_items: @mut HashMap::new(),
-        dep_map: @mut HashMap::new(),
-        worklist: ~[],
-        item_id: 0,
-        anon_implies_rp: false,
-        ambient_variance: rv_covariant
-    };
-
-    // Gather up the base set, worklist and dep_map
-    let mut visitor = DetermineRpVisitor { cx: cx };
-    visit::walk_crate(&mut visitor, crate, ());
-
-    // Propagate indirect dependencies
-    //
-    // Each entry in the worklist is the id of an item C whose region
-    // parameterization has been updated.  So we pull ids off of the
-    // worklist, find the current variance, and then iterate through
-    // all of the dependent items (that is, those items that reference
-    // C).  For each dependent item D, we combine the variance of C
-    // with the ambient variance where the reference occurred and then
-    // update the region-parameterization of D to reflect the result.
-    {
-        let cx = &mut *cx;
-        while cx.worklist.len() != 0 {
-            let c_id = cx.worklist.pop();
-            let c_variance = cx.region_paramd_items.get_copy(&c_id);
-            debug!("popped {} from worklist", c_id);
-            match cx.dep_map.find(&c_id) {
-              None => {}
-              Some(deps) => {
-                for dep in deps.iter() {
-                    let v = add_variance(dep.ambient_variance, c_variance);
-                    cx.add_rp(dep.id, v);
-                }
-              }
-            }
-        }
-    }
-
-    debug!("{}", {
-        debug!("Region variance results:");
-        let region_paramd_items = cx.region_paramd_items;
-        for (&key, &value) in region_paramd_items.iter() {
-            debug!("item {:?} ({}) is parameterized with variance {:?}",
-                   key,
-                   ast_map::node_id_to_str(ast_map, key,
-                                           token::get_ident_interner()),
-                   value);
-        }
-        "----"
-    });
-
-    // return final set
-    return cx.region_paramd_items;
-}
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 66fba347acc..a2959170584 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -209,13 +209,19 @@ pub enum ast_ty_to_ty_cache_entry {
     atttce_resolved(t)  /* resolved to a type, irrespective of region */
 }
 
-pub type opt_region_variance = Option<region_variance>;
+#[deriving(Clone, Eq, Decodable, Encodable)]
+pub struct ItemVariances {
+    self_param: Option<Variance>,
+    type_params: OptVec<Variance>,
+    region_params: OptVec<Variance>
+}
 
 #[deriving(Clone, Eq, Decodable, Encodable)]
-pub enum region_variance {
-    rv_covariant,
-    rv_invariant,
-    rv_contravariant,
+pub enum Variance {
+    Covariant,
+    Invariant,
+    Contravariant,
+    Bivariant,
 }
 
 #[deriving(Decodable, Encodable)]
@@ -264,7 +270,6 @@ struct ctxt_ {
     named_region_map: @mut resolve_lifetime::NamedRegionMap,
 
     region_maps: @mut middle::region::RegionMaps,
-    region_paramd_items: middle::region::region_paramd_items,
 
     // Stores the types for various nodes in the AST.  Note that this table
     // is not guaranteed to be populated until after typeck.  See
@@ -309,6 +314,10 @@ struct ctxt_ {
     provided_method_sources: @mut HashMap<ast::DefId, ast::DefId>,
     supertraits: @mut HashMap<ast::DefId, @~[@TraitRef]>,
 
+    // Maps from def-id of a type or region parameter to its
+    // (inferred) variance.
+    item_variance_map: @mut HashMap<ast::DefId, @ItemVariances>,
+
     // A mapping from the def ID of an enum or struct type to the def ID
     // of the method that implements its destructor. If the type is not
     // present in this map, it does not have a destructor. This map is
@@ -954,11 +963,11 @@ pub fn mk_ctxt(s: session::Session,
                amap: ast_map::map,
                freevars: freevars::freevar_map,
                region_maps: @mut middle::region::RegionMaps,
-               region_paramd_items: middle::region::region_paramd_items,
                lang_items: middle::lang_items::LanguageItems)
             -> ctxt {
     @ctxt_ {
         named_region_map: named_region_map,
+        item_variance_map: @mut HashMap::new(),
         diag: s.diagnostic(),
         interner: @mut HashMap::new(),
         next_id: @mut primitives::LAST_PRIMITIVE_ID,
@@ -966,7 +975,6 @@ pub fn mk_ctxt(s: session::Session,
         sess: s,
         def_map: dm,
         region_maps: region_maps,
-        region_paramd_items: region_paramd_items,
         node_types: @mut HashMap::new(),
         node_type_substs: @mut HashMap::new(),
         trait_refs: @mut HashMap::new(),
@@ -4410,6 +4418,12 @@ pub fn visitor_object_ty(tcx: ctxt,
                  EmptyBuiltinBounds())))
 }
 
+pub fn item_variances(tcx: ctxt, item_id: ast::DefId) -> @ItemVariances {
+    lookup_locally_or_in_crate_store(
+        "item_variance_map", item_id, tcx.item_variance_map,
+        || @csearch::get_item_variances(tcx.cstore, item_id))
+}
+
 /// Records a trait-to-implementation mapping.
 fn record_trait_implementation(tcx: ctxt,
                                trait_def_id: DefId,
@@ -4692,6 +4706,17 @@ pub fn hash_crate_independent(tcx: ctxt, t: t, local_hash: @str) -> u64 {
     hash.result_u64()
 }
 
+impl Variance {
+    pub fn to_str(self) -> &'static str {
+        match self {
+            Covariant => "+",
+            Contravariant => "-",
+            Invariant => "o",
+            Bivariant => "*",
+        }
+    }
+}
+
 pub fn construct_parameter_environment(
     tcx: ctxt,
     self_bound: Option<@TraitRef>,
diff --git a/src/librustc/middle/typeck/infer/combine.rs b/src/librustc/middle/typeck/infer/combine.rs
index d6d1618de71..c42f74864d2 100644
--- a/src/librustc/middle/typeck/infer/combine.rs
+++ b/src/librustc/middle/typeck/infer/combine.rs
@@ -123,76 +123,70 @@ pub trait Combine {
         }
     }
 
-    fn substs(&self, generics: &ty::Generics, as_: &ty::substs,
+    fn substs(&self,
+              item_def_id: ast::DefId,
+              as_: &ty::substs,
               bs: &ty::substs) -> cres<ty::substs> {
 
-        fn relate_region_params<C:Combine>(
-                                           this: &C,
-                                           generics: &ty::Generics,
+        fn relate_region_params<C:Combine>(this: &C,
+                                           item_def_id: ast::DefId,
                                            a: &ty::RegionSubsts,
                                            b: &ty::RegionSubsts)
-            -> cres<ty::RegionSubsts>
-            {
+                                           -> cres<ty::RegionSubsts> {
+            let tcx = this.infcx().tcx;
             match (a, b) {
-                (&ty::ErasedRegions, _) |
-                    (_, &ty::ErasedRegions) => {
+                (&ty::ErasedRegions, _) | (_, &ty::ErasedRegions) => {
                     Ok(ty::ErasedRegions)
                 }
 
                 (&ty::NonerasedRegions(ref a_rs),
                  &ty::NonerasedRegions(ref b_rs)) => {
-                    match generics.region_param {
-                        None => {
-                            assert!(a_rs.is_empty());
-                            assert!(b_rs.is_empty());
-                            Ok(ty::NonerasedRegions(opt_vec::Empty))
-                        }
-
-                        Some(variance) => {
-                            assert_eq!(a_rs.len(), 1);
-                            assert_eq!(b_rs.len(), 1);
-                            let a_r = *a_rs.get(0);
-                            let b_r = *b_rs.get(0);
-
-                            match variance {
-                                ty::rv_invariant => {
-                                    do eq_regions(this, a_r, b_r).then {
-                                        Ok(ty::NonerasedRegions(opt_vec::with(a_r)))
-                                    }
-                                }
-
-                                ty::rv_covariant => {
-                                    do this.regions(a_r, b_r).and_then |r| {
-                                        Ok(ty::NonerasedRegions(opt_vec::with(r)))
-                                    }
-                                }
-
-                                ty::rv_contravariant => {
-                                    do this.contraregions(a_r, b_r).and_then |r| {
-                                        Ok(ty::NonerasedRegions(opt_vec::with(r)))
-                                    }
-                                }
+                    let variances = ty::item_variances(tcx, item_def_id);
+                    let region_params = &variances.region_params;
+                    let num_region_params = region_params.len();
+
+                    debug!("relate_region_params(\
+                            item_def_id={}, \
+                            a_rs={}, \
+                            b_rs={},
+                            region_params={})",
+                            item_def_id.repr(tcx),
+                            a_rs.repr(tcx),
+                            b_rs.repr(tcx),
+                            region_params.repr(tcx));
+
+                    assert_eq!(num_region_params, a_rs.len());
+                    assert_eq!(num_region_params, b_rs.len());
+                    let mut rs = opt_vec::Empty;
+                    for i in range(0, num_region_params) {
+                        let a_r = *a_rs.get(i);
+                        let b_r = *b_rs.get(i);
+                        let variance = *region_params.get(i);
+                        let r = match variance {
+                            ty::Invariant => {
+                                eq_regions(this, a_r, b_r)
+                                    .and_then(|()| Ok(a_r))
                             }
-                        }
+                            ty::Covariant => this.regions(a_r, b_r),
+                            ty::Contravariant => this.contraregions(a_r, b_r),
+                            ty::Bivariant => Ok(a_r),
+                        };
+                        rs.push(if_ok!(r));
                     }
+                    Ok(ty::NonerasedRegions(rs))
                 }
             }
         }
 
-        do self.tps(as_.tps, bs.tps).and_then |tps| {
-            do self.self_tys(as_.self_ty, bs.self_ty).and_then |self_ty| {
-                do relate_region_params(self,
-                                        generics,
-                                        &as_.regions,
-                                        &bs.regions).and_then |regions| {
-                    Ok(substs {
-                            regions: regions,
-                            self_ty: self_ty,
-                            tps: tps.clone()
-                        })
-                }
-            }
-        }
+        let tps = if_ok!(self.tps(as_.tps, bs.tps));
+        let self_ty = if_ok!(self.self_tys(as_.self_ty, bs.self_ty));
+        let regions = if_ok!(relate_region_params(self,
+                                                  item_def_id,
+                                                  &as_.regions,
+                                                  &bs.regions));
+        Ok(substs { regions: regions,
+                    self_ty: self_ty,
+                    tps: tps.clone() })
     }
 
     fn bare_fn_tys(&self, a: &ty::BareFnTy,
@@ -267,9 +261,11 @@ pub trait Combine {
                   -> cres<ty::Region>;
     fn regions(&self, a: ty::Region, b: ty::Region) -> cres<ty::Region>;
 
-    fn vstores(&self, vk: ty::terr_vstore_kind,
-               a: ty::vstore, b: ty::vstore) -> cres<ty::vstore> {
-
+    fn vstores(&self,
+               vk: ty::terr_vstore_kind,
+               a: ty::vstore,
+               b: ty::vstore)
+               -> cres<ty::vstore> {
         debug!("{}.vstores(a={:?}, b={:?})", self.tag(), a, b);
 
         match (a, b) {
@@ -293,8 +289,7 @@ pub trait Combine {
                     vk: ty::terr_vstore_kind,
                     a: ty::TraitStore,
                     b: ty::TraitStore)
-                 -> cres<ty::TraitStore> {
-
+                    -> cres<ty::TraitStore> {
         debug!("{}.trait_stores(a={:?}, b={:?})", self.tag(), a, b);
 
         match (a, b) {
@@ -317,7 +312,8 @@ pub trait Combine {
 
     fn trait_refs(&self,
                   a: &ty::TraitRef,
-                  b: &ty::TraitRef) -> cres<ty::TraitRef> {
+                  b: &ty::TraitRef)
+                  -> cres<ty::TraitRef> {
         // Different traits cannot be related
 
         // - NOTE in the future, expand out subtraits!
@@ -326,15 +322,9 @@ pub trait Combine {
             Err(ty::terr_traits(
                                 expected_found(self, a.def_id, b.def_id)))
         } else {
-            let tcx = self.infcx().tcx;
-            let trait_def = ty::lookup_trait_def(tcx, a.def_id);
-            let substs = if_ok!(self.substs(&trait_def.generics,
-                                            &a.substs,
-                                            &b.substs));
-            Ok(ty::TraitRef {
-                    def_id: a.def_id,
-                    substs: substs
-                })
+            let substs = if_ok!(self.substs(a.def_id, &a.substs, &b.substs));
+            Ok(ty::TraitRef { def_id: a.def_id,
+                              substs: substs })
         }
     }
 }
@@ -366,8 +356,8 @@ pub fn eq_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> ures {
 pub fn eq_regions<C:Combine>(this: &C, a: ty::Region, b: ty::Region)
                           -> ures {
     debug!("eq_regions({}, {})",
-           a.inf_str(this.infcx()),
-           b.inf_str(this.infcx()));
+            a.repr(this.infcx().tcx),
+            b.repr(this.infcx().tcx));
     let sub = this.sub();
     do indent {
         this.infcx().try(|| {
@@ -511,36 +501,30 @@ pub fn super_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
       (&ty::ty_enum(a_id, ref a_substs),
        &ty::ty_enum(b_id, ref b_substs))
       if a_id == b_id => {
-          let type_def = ty::lookup_item_type(tcx, a_id);
-          do this.substs(&type_def.generics, a_substs, b_substs).and_then |substs| {
-              Ok(ty::mk_enum(tcx, a_id, substs))
-          }
+          let substs = if_ok!(this.substs(a_id,
+                                          a_substs,
+                                          b_substs));
+          Ok(ty::mk_enum(tcx, a_id, substs))
       }
 
       (&ty::ty_trait(a_id, ref a_substs, a_store, a_mutbl, a_bounds),
        &ty::ty_trait(b_id, ref b_substs, b_store, b_mutbl, b_bounds))
       if a_id == b_id && a_mutbl == b_mutbl => {
-          let trait_def = ty::lookup_trait_def(tcx, a_id);
-          do this.substs(&trait_def.generics, a_substs, b_substs).and_then |substs| {
-              do this.trait_stores(ty::terr_trait, a_store, b_store).and_then |s| {
-                  do this.bounds(a_bounds, b_bounds).and_then |bounds| {
-                    Ok(ty::mk_trait(tcx,
-                                    a_id,
-                                    substs.clone(),
-                                    s,
-                                    a_mutbl,
-                                    bounds))
-                  }
-              }
-          }
+          let substs = if_ok!(this.substs(a_id, a_substs, b_substs));
+          let s = if_ok!(this.trait_stores(ty::terr_trait, a_store, b_store));
+          let bounds = if_ok!(this.bounds(a_bounds, b_bounds));
+          Ok(ty::mk_trait(tcx,
+                          a_id,
+                          substs.clone(),
+                          s,
+                          a_mutbl,
+                          bounds))
       }
 
       (&ty::ty_struct(a_id, ref a_substs), &ty::ty_struct(b_id, ref b_substs))
       if a_id == b_id => {
-          let type_def = ty::lookup_item_type(tcx, a_id);
-          do this.substs(&type_def.generics, a_substs, b_substs).and_then |substs| {
-              Ok(ty::mk_struct(tcx, a_id, substs))
-          }
+            let substs = if_ok!(this.substs(a_id, a_substs, b_substs));
+            Ok(ty::mk_struct(tcx, a_id, substs))
       }
 
       (&ty::ty_box(ref a_mt), &ty::ty_box(ref b_mt)) => {
@@ -576,9 +560,8 @@ pub fn super_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
       }
 
       (&ty::ty_estr(vs_a), &ty::ty_estr(vs_b)) => {
-        do this.vstores(ty::terr_str, vs_a, vs_b).and_then |vs| {
-            Ok(ty::mk_estr(tcx,vs))
-        }
+        let vs = if_ok!(this.vstores(ty::terr_str, vs_a, vs_b));
+        Ok(ty::mk_estr(tcx,vs))
       }
 
       (&ty::ty_tup(ref as_), &ty::ty_tup(ref bs)) => {
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index 022c0ffb432..ed6c810e52c 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -19,16 +19,23 @@ The type checker is responsible for:
 3. Guaranteeing that most type rules are met ("most?", you say, "why most?"
    Well, dear reader, read on)
 
-The main entry point is `check_crate()`.  Type checking operates in two major
-phases: collect and check.  The collect phase passes over all items and
-determines their type, without examining their "innards".  The check phase
-then checks function bodies and so forth.
+The main entry point is `check_crate()`.  Type checking operates in
+several major phases:
 
-Within the check phase, we check each function body one at a time (bodies of
-function expressions are checked as part of the containing function).
-Inference is used to supply types wherever they are unknown. The actual
-checking of a function itself has several phases (check, regionck, writeback),
-as discussed in the documentation for the `check` module.
+1. The collect phase first passes over all items and determines their
+   type, without examining their "innards".
+
+2. Variance inference then runs to compute the variance of each parameter
+
+3. Coherence checks for overlapping or orphaned impls
+
+4. Finally, the check phase then checks function bodies and so forth.
+   Within the check phase, we check each function body one at a time
+   (bodies of function expressions are checked as part of the
+   containing function).  Inference is used to supply types wherever
+   they are unknown. The actual checking of a function itself has
+   several phases (check, regionck, writeback), as discussed in the
+   documentation for the `check` module.
 
 The type checker is defined into various submodules which are documented
 independently:
@@ -39,6 +46,10 @@ independently:
 - collect: computes the types of each top-level item and enters them into
   the `cx.tcache` table for later use
 
+- coherence: enforces coherence rules, builds some tables
+
+- variance: variance inference
+
 - check: walks over function bodies and type checks them, inferring types for
   local variables, type parameters, etc as necessary.
 
@@ -71,6 +82,7 @@ pub mod astconv;
 pub mod infer;
 pub mod collect;
 pub mod coherence;
+pub mod variance;
 
 #[deriving(Clone, Encodable, Decodable, Eq, Ord)]
 pub enum param_index {
@@ -455,6 +467,9 @@ pub fn check_crate(tcx: ty::ctxt,
     // have valid types and not error
     tcx.sess.abort_if_errors();
 
+    time(time_passes, "variance inference", (), |_|
+         variance::infer_variance(tcx, crate));
+
     time(time_passes, "coherence checking", (), |_|
         coherence::check_coherence(ccx, crate));
 
diff --git a/src/librustc/middle/typeck/variance.rs b/src/librustc/middle/typeck/variance.rs
new file mode 100644
index 00000000000..adb05d252e6
--- /dev/null
+++ b/src/librustc/middle/typeck/variance.rs
@@ -0,0 +1,841 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*!
+
+This file infers the variance of type and lifetime parameters. The
+algorithm is taken from Section 4 of the paper "Taming the Wildcards:
+Combining Definition- and Use-Site Variance" published in PLDI'11 and
+written by Altidor et al., and hereafter referred to as The Paper.
+
+The basic idea is quite straightforward. We iterate over the types
+defined and, for each use of a type parameter X, accumulate a
+constraint indicating that the variance of X must be valid for the
+variance of that use site. We then iteratively refine the variance of
+X until all constraints are met. There is *always* a sol'n, because at
+the limit we can declare all type parameters to be invariant and all
+constriants will be satisfied.
+
+As a simple example, consider:
+
+    enum Option<A> { Some(A), None }
+    enum OptionalFn<B> { Some(&fn(B)), None }
+    enum OptionalMap<C> { Some(&fn(C) -> C), None }
+
+Here, we will generate the constraints:
+
+    1. V(A) <= +
+    2. V(B) <= -
+    3. V(C) <= +
+    4. V(C) <= -
+
+These indicate that (1) the variance of A must be at most covariant;
+(2) the variance of B must be at most contravariant; and (3, 4) the
+variance of C must be at most covariant *and* contravariant. All of these
+results are based on a variance lattice defined as follows:
+
+      *      Top (bivariant)
+   -     +
+      o      Bottom (invariant)
+
+Based on this lattice, the solution V(A)=+, V(B)=-, V(C)=o is the
+minimal solution (which is what we are looking for; the maximal
+solution is just that all variables are invariant. Not so exciting.).
+
+You may be wondering why fixed-point iteration is required. The reason
+is that the variance of a use site may itself be a function of the
+variance of other type parameters. In full generality, our constraints
+take the form:
+
+    V(X) <= Term
+    Term := + | - | * | o | V(X) | Term x Term
+
+Here the notation V(X) indicates the variance of a type/region
+parameter `X` with respect to its defining class. `Term x Term`
+represents the "variance transform" as defined in the paper -- `V1 x
+V2` is the resulting variance when a use site with variance V2 appears
+inside a use site with variance V1.
+
+*/
+
+use std::hashmap::HashMap;
+use extra::arena;
+use extra::arena::Arena;
+use middle::ty;
+use std::vec;
+use syntax::ast;
+use syntax::ast_map;
+use syntax::ast_util;
+use syntax::parse::token;
+use syntax::opt_vec;
+use syntax::visit;
+use syntax::visit::Visitor;
+
+pub fn infer_variance(tcx: ty::ctxt,
+                      crate: &ast::Crate) {
+    let mut arena = arena::Arena::new();
+    let terms_cx = determine_parameters_to_be_inferred(tcx, &mut arena, crate);
+    let constraints_cx = add_constraints_from_crate(terms_cx, crate);
+    solve_constraints(constraints_cx);
+}
+
+/**************************************************************************
+ * Representing terms
+ *
+ * Terms are structured as a straightforward tree. Rather than rely on
+ * GC, we allocate terms out of a bounded arena (the lifetime of this
+ * arena is the lifetime 'self that is threaded around).
+ *
+ * We assign a unique index to each type/region parameter whose variance
+ * is to be inferred. We refer to such variables as "inferreds". An
+ * `InferredIndex` is a newtype'd int representing the index of such
+ * a variable.
+ */
+
+type VarianceTermPtr<'self> = &'self VarianceTerm<'self>;
+
+struct InferredIndex(uint);
+
+enum VarianceTerm<'self> {
+    ConstantTerm(ty::Variance),
+    TransformTerm(VarianceTermPtr<'self>, VarianceTermPtr<'self>),
+    InferredTerm(InferredIndex),
+}
+
+impl<'self> ToStr for VarianceTerm<'self> {
+    fn to_str(&self) -> ~str {
+        match *self {
+            ConstantTerm(c1) => format!("{}", c1.to_str()),
+            TransformTerm(v1, v2) => format!("({} \u00D7 {})",
+                                          v1.to_str(), v2.to_str()),
+            InferredTerm(id) => format!("[{}]", *id)
+        }
+    }
+}
+
+/**************************************************************************
+ * The first pass over the crate simply builds up the set of inferreds.
+ */
+
+struct TermsContext<'self> {
+    tcx: ty::ctxt,
+    arena: &'self Arena,
+
+    // Maps from the node id of a type/generic parameter to the
+    // corresponding inferred index.
+    inferred_map: HashMap<ast::NodeId, InferredIndex>,
+    inferred_infos: ~[InferredInfo<'self>],
+}
+
+enum ParamKind { TypeParam, RegionParam, SelfParam }
+
+struct InferredInfo<'self> {
+    item_id: ast::NodeId,
+    kind: ParamKind,
+    index: uint,
+    param_id: ast::NodeId,
+    term: VarianceTermPtr<'self>,
+}
+
+fn determine_parameters_to_be_inferred<'a>(tcx: ty::ctxt,
+                                           arena: &'a mut Arena,
+                                           crate: &ast::Crate)
+                                           -> TermsContext<'a> {
+    let mut terms_cx = TermsContext {
+        tcx: tcx,
+        arena: arena,
+        inferred_map: HashMap::new(),
+        inferred_infos: ~[],
+    };
+
+    visit::walk_crate(&mut terms_cx, crate, ());
+
+    terms_cx
+}
+
+impl<'self> TermsContext<'self> {
+    fn add_inferred(&mut self,
+                    item_id: ast::NodeId,
+                    kind: ParamKind,
+                    index: uint,
+                    param_id: ast::NodeId) {
+        let inf_index = InferredIndex(self.inferred_infos.len());
+        let term = self.arena.alloc(|| InferredTerm(inf_index));
+        self.inferred_infos.push(InferredInfo { item_id: item_id,
+                                                kind: kind,
+                                                index: index,
+                                                param_id: param_id,
+                                                term: term });
+        let newly_added = self.inferred_map.insert(param_id, inf_index);
+        assert!(newly_added);
+
+        debug!("add_inferred(item_id={}, \
+                kind={:?}, \
+                index={}, \
+                param_id={},
+                inf_index={:?})",
+                item_id, kind, index, param_id, inf_index);
+    }
+
+    fn num_inferred(&self) -> uint {
+        self.inferred_infos.len()
+    }
+}
+
+impl<'self> Visitor<()> for TermsContext<'self> {
+    fn visit_item(&mut self,
+                  item: @ast::item,
+                  (): ()) {
+        debug!("add_inferreds for item {}", item.repr(self.tcx));
+
+        let inferreds_on_entry = self.num_inferred();
+
+        // NB: In the code below for writing the results back into the
+        // tcx, we rely on the fact that all inferreds for a particular
+        // item are assigned continuous indices.
+        match item.node {
+            ast::item_trait(*) => {
+                self.add_inferred(item.id, SelfParam, 0, item.id);
+            }
+            _ => { }
+        }
+
+        match item.node {
+            ast::item_enum(_, ref generics) |
+            ast::item_struct(_, ref generics) |
+            ast::item_trait(ref generics, _, _) => {
+                for (i, p) in generics.lifetimes.iter().enumerate() {
+                    self.add_inferred(item.id, RegionParam, i, p.id);
+                }
+                for (i, p) in generics.ty_params.iter().enumerate() {
+                    self.add_inferred(item.id, TypeParam, i, p.id);
+                }
+
+                // If this item has no type or lifetime parameters,
+                // then there are no variances to infer, so just
+                // insert an empty entry into the variance map.
+                // Arguably we could just leave the map empty in this
+                // case but it seems cleaner to be able to distinguish
+                // "invalid item id" from "item id with no
+                // parameters".
+                if self.num_inferred() == inferreds_on_entry {
+                    let newly_added = self.tcx.item_variance_map.insert(
+                        ast_util::local_def(item.id),
+                        @ty::ItemVariances {
+                            self_param: None,
+                            type_params: opt_vec::Empty,
+                            region_params: opt_vec::Empty
+                        });
+                    assert!(newly_added);
+                }
+
+                visit::walk_item(self, item, ());
+            }
+
+            ast::item_impl(*) |
+            ast::item_static(*) |
+            ast::item_fn(*) |
+            ast::item_mod(*) |
+            ast::item_foreign_mod(*) |
+            ast::item_ty(*) |
+            ast::item_mac(*) => {
+                visit::walk_item(self, item, ());
+            }
+        }
+    }
+}
+
+/**************************************************************************
+ * Constraint construction and representation
+ *
+ * The second pass over the AST determines the set of constraints.
+ * We walk the set of items and, for each member, generate new constraints.
+ */
+
+struct ConstraintContext<'self> {
+    terms_cx: TermsContext<'self>,
+
+    covariant: VarianceTermPtr<'self>,
+    contravariant: VarianceTermPtr<'self>,
+    invariant: VarianceTermPtr<'self>,
+    bivariant: VarianceTermPtr<'self>,
+
+    constraints: ~[Constraint<'self>],
+}
+
+/// Declares that the variable `decl_id` appears in a location with
+/// variance `variance`.
+struct Constraint<'self> {
+    inferred: InferredIndex,
+    variance: &'self VarianceTerm<'self>,
+}
+
+fn add_constraints_from_crate<'a>(terms_cx: TermsContext<'a>,
+                                  crate: &ast::Crate)
+                                  -> ConstraintContext<'a> {
+    let covariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Covariant));
+    let contravariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Contravariant));
+    let invariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Invariant));
+    let bivariant = terms_cx.arena.alloc(|| ConstantTerm(ty::Bivariant));
+    let mut constraint_cx = ConstraintContext {
+        terms_cx: terms_cx,
+        covariant: covariant,
+        contravariant: contravariant,
+        invariant: invariant,
+        bivariant: bivariant,
+        constraints: ~[],
+    };
+    visit::walk_crate(&mut constraint_cx, crate, ());
+    constraint_cx
+}
+
+impl<'self> Visitor<()> for ConstraintContext<'self> {
+    fn visit_item(&mut self,
+                  item: @ast::item,
+                  (): ()) {
+        let did = ast_util::local_def(item.id);
+        let tcx = self.terms_cx.tcx;
+
+        match item.node {
+            ast::item_enum(ref enum_definition, _) => {
+                // Hack: If we directly call `ty::enum_variants`, it
+                // annoyingly takes it upon itself to run off and
+                // evaluate the discriminants eagerly (*grumpy* that's
+                // not the typical pattern). This results in double
+                // error messagees because typeck goes off and does
+                // this at a later time. All we really care about is
+                // the types of the variant arguments, so we just call
+                // `ty::VariantInfo::from_ast_variant()` ourselves
+                // here, mainly so as to mask the differences between
+                // struct-like enums and so forth.
+                for ast_variant in enum_definition.variants.iter() {
+                    let variant =
+                        ty::VariantInfo::from_ast_variant(tcx,
+                                                          ast_variant,
+                                                          /*discrimant*/ 0);
+                    for &arg_ty in variant.args.iter() {
+                        self.add_constraints_from_ty(arg_ty, self.covariant);
+                    }
+                }
+            }
+
+            ast::item_struct(*) => {
+                let struct_fields = ty::lookup_struct_fields(tcx, did);
+                for field_info in struct_fields.iter() {
+                    assert_eq!(field_info.id.crate, ast::LOCAL_CRATE);
+                    let field_ty = ty::node_id_to_type(tcx, field_info.id.node);
+                    self.add_constraints_from_ty(field_ty, self.covariant);
+                }
+            }
+
+            ast::item_trait(*) => {
+                let methods = ty::trait_methods(tcx, did);
+                for method in methods.iter() {
+                    match method.transformed_self_ty {
+                        Some(self_ty) => {
+                            // The self type is a parameter, so its type
+                            // should be considered contravariant:
+                            self.add_constraints_from_ty(
+                                self_ty, self.contravariant);
+                        }
+                        None => {}
+                    }
+
+                    self.add_constraints_from_sig(
+                        &method.fty.sig, self.covariant);
+                }
+            }
+
+            ast::item_static(*) |
+            ast::item_fn(*) |
+            ast::item_mod(*) |
+            ast::item_foreign_mod(*) |
+            ast::item_ty(*) |
+            ast::item_impl(*) |
+            ast::item_mac(*) => {
+                visit::walk_item(self, item, ());
+            }
+        }
+    }
+}
+
+impl<'self> ConstraintContext<'self> {
+    fn tcx(&self) -> ty::ctxt {
+        self.terms_cx.tcx
+    }
+
+    fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
+        match self.terms_cx.inferred_map.find(&param_id) {
+            Some(&index) => index,
+            None => {
+                self.tcx().sess.bug(format!(
+                        "No inferred index entry for {}",
+                        ast_map::node_id_to_str(self.tcx().items,
+                                                param_id,
+                                                token::get_ident_interner())));
+            }
+        }
+    }
+
+    fn declared_variance(&self,
+                         param_def_id: ast::DefId,
+                         item_def_id: ast::DefId,
+                         kind: ParamKind,
+                         index: uint)
+                         -> VarianceTermPtr<'self> {
+        /*!
+         * Returns a variance term representing the declared variance of
+         * the type/region parameter with the given id.
+         */
+
+        assert_eq!(param_def_id.crate, item_def_id.crate);
+        if param_def_id.crate == ast::LOCAL_CRATE {
+            // Parameter on an item defined within current crate:
+            // variance not yet inferred, so return a symbolic
+            // variance.
+            let index = self.inferred_index(param_def_id.node);
+            self.terms_cx.inferred_infos[*index].term
+        } else {
+            // Parameter on an item defined within another crate:
+            // variance already inferred, just look it up.
+            let variances = ty::item_variances(self.tcx(), item_def_id);
+            let variance = match kind {
+                SelfParam => variances.self_param.unwrap(),
+                TypeParam => *variances.type_params.get(index),
+                RegionParam => *variances.region_params.get(index),
+            };
+            self.constant_term(variance)
+        }
+    }
+
+    fn add_constraint(&mut self,
+                      index: InferredIndex,
+                      variance: VarianceTermPtr<'self>) {
+        debug!("add_constraint(index={}, variance={})",
+                *index, variance.to_str());
+        self.constraints.push(Constraint { inferred: index,
+                                           variance: variance });
+    }
+
+    fn contravariant(&mut self,
+                     variance: VarianceTermPtr<'self>)
+                     -> VarianceTermPtr<'self> {
+        self.xform(variance, self.contravariant)
+    }
+
+    fn invariant(&mut self,
+                 variance: VarianceTermPtr<'self>)
+                 -> VarianceTermPtr<'self> {
+        self.xform(variance, self.invariant)
+    }
+
+    fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'self> {
+        match v {
+            ty::Covariant => self.covariant,
+            ty::Invariant => self.invariant,
+            ty::Contravariant => self.contravariant,
+            ty::Bivariant => self.bivariant,
+        }
+    }
+
+    fn xform(&mut self,
+             v1: VarianceTermPtr<'self>,
+             v2: VarianceTermPtr<'self>)
+             -> VarianceTermPtr<'self> {
+        match (*v1, *v2) {
+            (_, ConstantTerm(ty::Covariant)) => {
+                // Applying a "covariant" transform is always a no-op
+                v1
+            }
+
+            (ConstantTerm(c1), ConstantTerm(c2)) => {
+                self.constant_term(c1.xform(c2))
+            }
+
+            _ => {
+                self.terms_cx.arena.alloc(|| TransformTerm(v1, v2))
+            }
+        }
+    }
+
+    fn add_constraints_from_ty(&mut self,
+                               ty: ty::t,
+                               variance: VarianceTermPtr<'self>) {
+        debug!("add_constraints_from_ty(ty={})", ty.repr(self.tcx()));
+
+        match ty::get(ty).sty {
+            ty::ty_nil | ty::ty_bot | ty::ty_bool |
+            ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) |
+            ty::ty_float(_) => {
+                /* leaf type -- noop */
+            }
+
+            ty::ty_rptr(region, ref mt) => {
+                let contra = self.contravariant(variance);
+                self.add_constraints_from_region(region, contra);
+                self.add_constraints_from_mt(mt, variance);
+            }
+
+            ty::ty_estr(vstore) => {
+                self.add_constraints_from_vstore(vstore, variance);
+            }
+
+            ty::ty_evec(ref mt, vstore) => {
+                self.add_constraints_from_vstore(vstore, variance);
+                self.add_constraints_from_mt(mt, variance);
+            }
+
+            ty::ty_box(ref mt) |
+            ty::ty_uniq(ref mt) |
+            ty::ty_ptr(ref mt) => {
+                self.add_constraints_from_mt(mt, variance);
+            }
+
+            ty::ty_tup(ref subtys) => {
+                for &subty in subtys.iter() {
+                    self.add_constraints_from_ty(subty, variance);
+                }
+            }
+
+            ty::ty_enum(def_id, ref substs) |
+            ty::ty_struct(def_id, ref substs) => {
+                let item_type = ty::lookup_item_type(self.tcx(), def_id);
+                self.add_constraints_from_substs(def_id, &item_type.generics,
+                                                 substs, variance);
+            }
+
+            ty::ty_trait(def_id, ref substs, _, _, _) => {
+                let trait_def = ty::lookup_trait_def(self.tcx(), def_id);
+                self.add_constraints_from_substs(def_id, &trait_def.generics,
+                                                 substs, variance);
+            }
+
+            ty::ty_param(ty::param_ty { def_id: ref def_id, _ }) => {
+                assert_eq!(def_id.crate, ast::LOCAL_CRATE);
+                match self.terms_cx.inferred_map.find(&def_id.node) {
+                    Some(&index) => {
+                        self.add_constraint(index, variance);
+                    }
+                    None => {
+                        // We do not infer variance for type parameters
+                        // declared on methods. They will not be present
+                        // in the inferred_map.
+                    }
+                }
+            }
+
+            ty::ty_self(ref def_id) => {
+                assert_eq!(def_id.crate, ast::LOCAL_CRATE);
+                let index = self.inferred_index(def_id.node);
+                self.add_constraint(index, variance);
+            }
+
+            ty::ty_bare_fn(ty::BareFnTy { sig: ref sig, _ }) => {
+                self.add_constraints_from_sig(sig, variance);
+            }
+
+            ty::ty_closure(ty::ClosureTy { sig: ref sig, region, _ }) => {
+                let contra = self.contravariant(variance);
+                self.add_constraints_from_region(region, contra);
+                self.add_constraints_from_sig(sig, variance);
+            }
+
+            ty::ty_infer(*) | ty::ty_err | ty::ty_type |
+            ty::ty_opaque_box | ty::ty_opaque_closure_ptr(*) |
+            ty::ty_unboxed_vec(*) => {
+                self.tcx().sess.bug(
+                    format!("Unexpected type encountered in \
+                            variance inference: {}",
+                            ty.repr(self.tcx())));
+            }
+        }
+    }
+
+    fn add_constraints_from_vstore(&mut self,
+                                   vstore: ty::vstore,
+                                   variance: VarianceTermPtr<'self>) {
+        match vstore {
+            ty::vstore_slice(r) => {
+                let contra = self.contravariant(variance);
+                self.add_constraints_from_region(r, contra);
+            }
+
+            ty::vstore_fixed(_) | ty::vstore_uniq | ty::vstore_box => {
+            }
+        }
+    }
+
+    fn add_constraints_from_substs(&mut self,
+                                   def_id: ast::DefId,
+                                   generics: &ty::Generics,
+                                   substs: &ty::substs,
+                                   variance: VarianceTermPtr<'self>) {
+        debug!("add_constraints_from_substs(def_id={:?})", def_id);
+
+        for (i, p) in generics.type_param_defs.iter().enumerate() {
+            let variance_decl =
+                self.declared_variance(p.def_id, def_id, TypeParam, i);
+            let variance_i = self.xform(variance, variance_decl);
+            self.add_constraints_from_ty(substs.tps[i], variance_i);
+        }
+
+        match substs.regions {
+            ty::ErasedRegions => {}
+            ty::NonerasedRegions(ref rps) => {
+                for (i, p) in generics.region_param_defs.iter().enumerate() {
+                    let variance_decl =
+                        self.declared_variance(p.def_id, def_id, RegionParam, i);
+                    let variance_i = self.xform(variance, variance_decl);
+                    self.add_constraints_from_region(*rps.get(i), variance_i);
+                }
+            }
+        }
+    }
+
+    fn add_constraints_from_sig(&mut self,
+                                sig: &ty::FnSig,
+                                variance: VarianceTermPtr<'self>) {
+        let contra = self.contravariant(variance);
+        for &input in sig.inputs.iter() {
+            self.add_constraints_from_ty(input, contra);
+        }
+        self.add_constraints_from_ty(sig.output, variance);
+    }
+
+    fn add_constraints_from_region(&mut self,
+                                   region: ty::Region,
+                                   variance: VarianceTermPtr<'self>) {
+        match region {
+            ty::re_type_bound(param_id, _, _) => {
+                let index = self.inferred_index(param_id);
+                self.add_constraint(index, variance);
+            }
+
+            ty::re_static => { }
+
+            ty::re_fn_bound(*) => {
+                // We do not infer variance for region parameters on
+                // methods or in fn types.
+            }
+
+            ty::re_free(*) | ty::re_scope(*) | ty::re_infer(*) |
+            ty::re_empty => {
+                // We don't expect to see anything but 'static or bound
+                // regions when visiting member types or method types.
+                self.tcx().sess.bug(format!("Unexpected region encountered in \
+                                            variance inference: {}",
+                                            region.repr(self.tcx())));
+            }
+        }
+    }
+
+    fn add_constraints_from_mt(&mut self,
+                               mt: &ty::mt,
+                               variance: VarianceTermPtr<'self>) {
+        match mt.mutbl {
+            ast::MutMutable => {
+                let invar = self.invariant(variance);
+                self.add_constraints_from_ty(mt.ty, invar);
+            }
+
+            ast::MutImmutable => {
+                self.add_constraints_from_ty(mt.ty, variance);
+            }
+        }
+    }
+}
+
+/**************************************************************************
+ * Constraint solving
+ *
+ * The final phase iterates over the constraints, refining the variance
+ * for each inferred until a fixed point is reached. This will be the
+ * maximal solution to the constraints. The final variance for each
+ * inferred is then written into the `variance_map` in the tcx.
+ */
+
+struct SolveContext<'self> {
+    terms_cx: TermsContext<'self>,
+    constraints: ~[Constraint<'self>],
+    solutions: ~[ty::Variance]
+}
+
+fn solve_constraints(constraints_cx: ConstraintContext) {
+    let ConstraintContext { terms_cx, constraints, _ } = constraints_cx;
+    let solutions = vec::from_elem(terms_cx.num_inferred(), ty::Bivariant);
+    let mut solutions_cx = SolveContext {
+        terms_cx: terms_cx,
+        constraints: constraints,
+        solutions: solutions
+    };
+    solutions_cx.solve();
+    solutions_cx.write();
+}
+
+impl<'self> SolveContext<'self> {
+    fn solve(&mut self) {
+        // Propagate constraints until a fixed point is reached.  Note
+        // that the maximum number of iterations is 2C where C is the
+        // number of constraints (each variable can change values at most
+        // twice). Since number of constraints is linear in size of the
+        // input, so is the inference process.
+        let mut changed = true;
+        while changed {
+            changed = false;
+
+            for constraint in self.constraints.iter() {
+                let Constraint { inferred, variance: term } = *constraint;
+                let variance = self.evaluate(term);
+                let old_value = self.solutions[*inferred];
+                let new_value = glb(variance, old_value);
+                if old_value != new_value {
+                    debug!("Updating inferred {} (node {}) \
+                            from {:?} to {:?} due to {}",
+                            *inferred,
+                            self.terms_cx.inferred_infos[*inferred].param_id,
+                            old_value,
+                            new_value,
+                            term.to_str());
+
+                    self.solutions[*inferred] = new_value;
+                    changed = true;
+                }
+            }
+        }
+    }
+
+    fn write(&self) {
+        // Collect all the variances for a particular item and stick
+        // them into the variance map. We rely on the fact that we
+        // generate all the inferreds for a particular item
+        // consecutively.
+        let tcx = self.terms_cx.tcx;
+        let item_variance_map = tcx.item_variance_map;
+        let solutions = &self.solutions;
+        let inferred_infos = &self.terms_cx.inferred_infos;
+        let mut index = 0;
+        let num_inferred = self.terms_cx.num_inferred();
+        while index < num_inferred {
+            let item_id = inferred_infos[index].item_id;
+            let mut item_variances = ty::ItemVariances {
+                self_param: None,
+                type_params: opt_vec::Empty,
+                region_params: opt_vec::Empty
+            };
+            while (index < num_inferred &&
+                   inferred_infos[index].item_id == item_id) {
+                let info = &inferred_infos[index];
+                match info.kind {
+                    SelfParam => {
+                        assert!(item_variances.self_param.is_none());
+                        item_variances.self_param = Some(solutions[index]);
+                    }
+                    TypeParam => {
+                        item_variances.type_params.push(solutions[index]);
+                    }
+                    RegionParam => {
+                        item_variances.region_params.push(solutions[index]);
+                    }
+                }
+                index += 1;
+            }
+
+            debug!("item_id={} item_variances={}",
+                    item_id,
+                    item_variances.repr(tcx));
+
+            let item_def_id = ast_util::local_def(item_id);
+
+            // For unit testing: check for a special "rustc_variance"
+            // attribute and report an error with various results if found.
+            if ty::has_attr(tcx, item_def_id, "rustc_variance") {
+                let found = item_variances.repr(tcx);
+                tcx.sess.span_err(ast_map::item_span(tcx.items, item_id), found);
+            }
+
+            let newly_added = item_variance_map.insert(item_def_id,
+                                                       @item_variances);
+            assert!(newly_added);
+        }
+    }
+
+    fn evaluate(&self, term: VarianceTermPtr<'self>) -> ty::Variance {
+        match *term {
+            ConstantTerm(v) => {
+                v
+            }
+
+            TransformTerm(t1, t2) => {
+                let v1 = self.evaluate(t1);
+                let v2 = self.evaluate(t2);
+                v1.xform(v2)
+            }
+
+            InferredTerm(index) => {
+                self.solutions[*index]
+            }
+        }
+    }
+}
+
+/**************************************************************************
+ * Miscellany transformations on variance
+ */
+
+trait Xform {
+    fn xform(self, v: Self) -> Self;
+}
+
+impl Xform for ty::Variance {
+    fn xform(self, v: ty::Variance) -> ty::Variance {
+        // "Variance transformation", Figure 1 of The Paper
+        match (self, v) {
+            // Figure 1, column 1.
+            (ty::Covariant, ty::Covariant) => ty::Covariant,
+            (ty::Covariant, ty::Contravariant) => ty::Contravariant,
+            (ty::Covariant, ty::Invariant) => ty::Invariant,
+            (ty::Covariant, ty::Bivariant) => ty::Bivariant,
+
+            // Figure 1, column 2.
+            (ty::Contravariant, ty::Covariant) => ty::Contravariant,
+            (ty::Contravariant, ty::Contravariant) => ty::Covariant,
+            (ty::Contravariant, ty::Invariant) => ty::Invariant,
+            (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
+
+            // Figure 1, column 3.
+            (ty::Invariant, _) => ty::Invariant,
+
+            // Figure 1, column 4.
+            (ty::Bivariant, _) => ty::Bivariant,
+        }
+    }
+}
+
+fn glb(v1: ty::Variance, v2: ty::Variance) -> ty::Variance {
+    // Greatest lower bound of the variance lattice as
+    // defined in The Paper:
+    //
+    //       *
+    //    -     +
+    //       o
+    match (v1, v2) {
+        (ty::Invariant, _) | (_, ty::Invariant) => ty::Invariant,
+
+        (ty::Covariant, ty::Contravariant) => ty::Invariant,
+        (ty::Contravariant, ty::Covariant) => ty::Invariant,
+
+        (ty::Covariant, ty::Covariant) => ty::Covariant,
+
+        (ty::Contravariant, ty::Contravariant) => ty::Contravariant,
+
+        (x, ty::Bivariant) | (ty::Bivariant, x) => x,
+    }
+}
+
diff --git a/src/test/compile-fail/regions-infer-contravariance-due-to-immutability.rs b/src/test/compile-fail/regions-infer-contravariance-due-to-immutability.rs
deleted file mode 100644
index 83e39ebd9f4..00000000000
--- a/src/test/compile-fail/regions-infer-contravariance-due-to-immutability.rs
+++ /dev/null
@@ -1,28 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-struct contravariant<'self> {
-    f: &'self int
-}
-
-fn to_same_lifetime<'r>(bi: contravariant<'r>) {
-    let bj: contravariant<'r> = bi;
-}
-
-fn to_shorter_lifetime<'r>(bi: contravariant<'r>) {
-    let bj: contravariant<'blk> = bi;
-}
-
-fn to_longer_lifetime<'r>(bi: contravariant<'r>) -> contravariant<'static> {
-    bi //~ ERROR mismatched types
-}
-
-fn main() {
-}
diff --git a/src/test/compile-fail/regions-infer-contravariance-due-to-ret.rs b/src/test/compile-fail/regions-infer-contravariance-due-to-ret.rs
deleted file mode 100644
index 3fcc5184b4a..00000000000
--- a/src/test/compile-fail/regions-infer-contravariance-due-to-ret.rs
+++ /dev/null
@@ -1,33 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-// Contravariant with respect to a region:
-//
-// You can upcast to a *smaller region* but not a larger one.  This is
-// the normal case.
-
-struct contravariant<'self> {
-    f: &'static fn() -> &'self int
-}
-
-fn to_same_lifetime<'r>(bi: contravariant<'r>) {
-    let bj: contravariant<'r> = bi;
-}
-
-fn to_shorter_lifetime<'r>(bi: contravariant<'r>) {
-    let bj: contravariant<'blk> = bi;
-}
-
-fn to_longer_lifetime<'r>(bi: contravariant<'r>) -> contravariant<'static> {
-    bi //~ ERROR mismatched types
-}
-
-fn main() {
-}
diff --git a/src/test/compile-fail/regions-infer-covariance-due-to-arg.rs b/src/test/compile-fail/regions-infer-covariance-due-to-arg.rs
deleted file mode 100644
index 4b26e6b6021..00000000000
--- a/src/test/compile-fail/regions-infer-covariance-due-to-arg.rs
+++ /dev/null
@@ -1,33 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-// Covariant with respect to a region:
-//
-// You can upcast to a *larger region* but not a smaller one.
-
-struct covariant<'self> {
-    f: &'static fn(x: &'self int) -> int
-}
-
-fn to_same_lifetime<'r>(bi: covariant<'r>) {
-    let bj: covariant<'r> = bi;
-}
-
-fn to_shorter_lifetime<'r>(bi: covariant<'r>) {
-    let bj: covariant<'blk> = bi; //~ ERROR mismatched types
-    //~^ ERROR cannot infer an appropriate lifetime
-}
-
-fn to_longer_lifetime<'r>(bi: covariant<'r>) -> covariant<'static> {
-    bi
-}
-
-fn main() {
-}
diff --git a/src/test/compile-fail/regions-infer-invariance-due-to-arg-and-ret.rs b/src/test/compile-fail/regions-infer-invariance-due-to-arg-and-ret.rs
deleted file mode 100644
index 0d4d4056a44..00000000000
--- a/src/test/compile-fail/regions-infer-invariance-due-to-arg-and-ret.rs
+++ /dev/null
@@ -1,32 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-// Invariance with respect to a region:
-//
-// You cannot convert between regions.
-
-struct invariant<'self> {
-    f: &'self fn(x: &'self int) -> &'self int
-}
-
-fn to_same_lifetime<'r>(bi: invariant<'r>) {
-    let bj: invariant<'r> = bi;
-}
-
-fn to_shorter_lifetime<'r>(bi: invariant<'r>) {
-    let bj: invariant<'blk> = bi; //~ ERROR mismatched types
-}
-
-fn to_longer_lifetime<'r>(bi: invariant<'r>) -> invariant<'static> {
-    bi //~ ERROR mismatched types
-}
-
-fn main() {
-}
diff --git a/src/test/compile-fail/regions-infer-invariance-due-to-mutability-1.rs b/src/test/compile-fail/regions-infer-invariance-due-to-mutability-1.rs
deleted file mode 100644
index f7c9e5bda3b..00000000000
--- a/src/test/compile-fail/regions-infer-invariance-due-to-mutability-1.rs
+++ /dev/null
@@ -1,26 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-#[feature(managed_boxes)];
-
-struct invariant<'self> {
-    f: @mut &'self int
-}
-
-fn to_same_lifetime<'r>(bi: invariant<'r>) {
-    let bj: invariant<'r> = bi;
-}
-
-fn to_longer_lifetime<'r>(bi: invariant<'r>) -> invariant<'static> {
-    bi //~ ERROR mismatched types
-}
-
-fn main() {
-}
diff --git a/src/test/compile-fail/regions-infer-invariance-due-to-mutability-2.rs b/src/test/compile-fail/regions-infer-invariance-due-to-mutability-2.rs
deleted file mode 100644
index 522e5675bfe..00000000000
--- a/src/test/compile-fail/regions-infer-invariance-due-to-mutability-2.rs
+++ /dev/null
@@ -1,26 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-#[feature(managed_boxes)];
-
-struct invariant<'self> {
-    f: @mut [&'self int]
-}
-
-fn to_same_lifetime<'r>(bi: invariant<'r>) {
-    let bj: invariant<'r> = bi;
-}
-
-fn to_longer_lifetime<'r>(bi: invariant<'r>) -> invariant<'static> {
-    bi //~ ERROR mismatched types
-}
-
-fn main() {
-}
diff --git a/src/test/compile-fail/regions-infer-invariance-due-to-mutability.rs b/src/test/compile-fail/regions-infer-invariance-due-to-mutability.rs
deleted file mode 100644
index 9853741d77a..00000000000
--- a/src/test/compile-fail/regions-infer-invariance-due-to-mutability.rs
+++ /dev/null
@@ -1,30 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-#[feature(managed_boxes)];
-
-struct invariant<'self> {
-    f: @mut &'self int
-}
-
-fn to_same_lifetime<'r>(bi: invariant<'r>) {
-    let bj: invariant<'r> = bi;
-}
-
-fn to_shorter_lifetime<'r>(bi: invariant<'r>) {
-    let bj: invariant<'blk> = bi; //~ ERROR mismatched types
-}
-
-fn to_longer_lifetime<'r>(bi: invariant<'r>) -> invariant<'static> {
-    bi //~ ERROR mismatched types
-}
-
-fn main() {
-}
diff --git a/src/test/compile-fail/regions-variance-covariant-use-contravariant.rs b/src/test/compile-fail/regions-variance-covariant-use-contravariant.rs
new file mode 100644
index 00000000000..b004bc471a5
--- /dev/null
+++ b/src/test/compile-fail/regions-variance-covariant-use-contravariant.rs
@@ -0,0 +1,38 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that a type which is contravariant with respect to its region
+// parameter yields an error when used in a covariant way.
+//
+// Note: see variance-regions-*.rs for the tests that check that the
+// variance inference works in the first place.
+
+// This is covariant with respect to 'a, meaning that
+// Covariant<'foo> <: Covariant<'static> because
+// 'foo <= 'static
+struct Covariant<'a> {
+    f: extern "Rust" fn(&'a int)
+}
+
+fn use_<'a>(c: Covariant<'a>) {
+    let x = 3;
+
+    // 'b winds up being inferred to 'a because
+    // Covariant<'a> <: Covariant<'b> => 'a <= 'b
+    //
+    // Borrow checker then reports an error because `x` does not
+    // have the lifetime 'a.
+    collapse(&x, c); //~ ERROR borrowed value does not live long enough
+
+
+    fn collapse<'b>(x: &'b int, c: Covariant<'b>) { }
+}
+
+fn main() {}
diff --git a/src/test/compile-fail/regions-variance-invariant-use-contravariant.rs b/src/test/compile-fail/regions-variance-invariant-use-contravariant.rs
new file mode 100644
index 00000000000..b105fc72692
--- /dev/null
+++ b/src/test/compile-fail/regions-variance-invariant-use-contravariant.rs
@@ -0,0 +1,33 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that a covariant region parameter used in a covariant position
+// yields an error.
+//
+// Note: see variance-regions-*.rs for the tests that check that the
+// variance inference works in the first place.
+
+struct Invariant<'a> {
+    f: &'static mut &'a int
+}
+
+fn use_<'a>(c: Invariant<'a>) {
+    let x = 3;
+
+    // 'b winds up being inferred to 'a, because that is the
+    // only way that Invariant<'a> <: Invariant<'b>, and hence
+    // we get an error in the borrow checker because &x cannot
+    // live that long
+    collapse(&x, c); //~ ERROR borrowed value does not live long enough
+
+    fn collapse<'b>(x: &'b int, c: Invariant<'b>) { }
+}
+
+fn main() { }
diff --git a/src/test/compile-fail/regions-variance-invariant-use-covariant.rs b/src/test/compile-fail/regions-variance-invariant-use-covariant.rs
new file mode 100644
index 00000000000..9aae0f87f5b
--- /dev/null
+++ b/src/test/compile-fail/regions-variance-invariant-use-covariant.rs
@@ -0,0 +1,27 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that a type which is invariant with respect to its region
+// parameter used in a covariant way yields an error.
+//
+// Note: see variance-regions-*.rs for the tests that check that the
+// variance inference works in the first place.
+
+struct Invariant<'a> {
+    f: &'static mut &'a int
+}
+
+fn use_<'a>(c: Invariant<'a>) {
+    // For this assignment to be legal, Invariant<'a> <: Invariant<'static>,
+    // which (if Invariant were covariant) would require 'a <= 'static.
+    let _: Invariant<'static> = c; //~ ERROR mismatched types
+}
+
+fn main() { }
diff --git a/src/test/compile-fail/variance-regions-direct.rs b/src/test/compile-fail/variance-regions-direct.rs
new file mode 100644
index 00000000000..ae8444f015e
--- /dev/null
+++ b/src/test/compile-fail/variance-regions-direct.rs
@@ -0,0 +1,73 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that we correctly infer variance for region parameters in
+// various self-contained types.
+
+// Regions that just appear in normal spots are contravariant:
+
+#[rustc_variance]
+struct Test2<'a, 'b, 'c> { //~ ERROR region_params=[-, -, -]
+    x: &'a int,
+    y: &'b [int],
+    c: &'c str
+}
+
+// Those same annotations in function arguments become covariant:
+
+#[rustc_variance]
+struct Test3<'a, 'b, 'c> { //~ ERROR region_params=[+, +, +]
+    x: extern "Rust" fn(&'a int),
+    y: extern "Rust" fn(&'b [int]),
+    c: extern "Rust" fn(&'c str),
+}
+
+// Mutability induces invariance:
+
+#[rustc_variance]
+struct Test4<'a, 'b> { //~ ERROR region_params=[-, o]
+    x: &'a mut &'b int,
+}
+
+// Mutability induces invariance, even when in a
+// contravariant context:
+
+#[rustc_variance]
+struct Test5<'a, 'b> { //~ ERROR region_params=[+, o]
+    x: extern "Rust" fn(&'a mut &'b int),
+}
+
+// Invariance is a trap from which NO ONE CAN ESCAPE.
+// In other words, even though the `&'b int` occurs in
+// a argument list (which is contravariant), that
+// argument list occurs in an invariant context.
+
+#[rustc_variance]
+struct Test6<'a, 'b> { //~ ERROR region_params=[-, o]
+    x: &'a mut extern "Rust" fn(&'b int),
+}
+
+// No uses at all is bivariant:
+
+#[rustc_variance]
+struct Test7<'a> { //~ ERROR region_params=[*]
+    x: int
+}
+
+// Try enums too.
+
+#[rustc_variance]
+enum Test8<'a, 'b, 'c> { //~ ERROR region_params=[+, -, o]
+    Test8A(extern "Rust" fn(&'a int)),
+    Test8B(&'b [int]),
+    Test8C(&'b mut &'c str),
+}
+
+fn main() {}
diff --git a/src/test/compile-fail/variance-regions-indirect.rs b/src/test/compile-fail/variance-regions-indirect.rs
new file mode 100644
index 00000000000..fa22bb41aa3
--- /dev/null
+++ b/src/test/compile-fail/variance-regions-indirect.rs
@@ -0,0 +1,42 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that we correctly infer variance for region parameters in
+// case that involve multiple intracrate types.
+// Try enums too.
+
+#[rustc_variance]
+enum Base<'a, 'b, 'c, 'd> { //~ ERROR region_params=[+, -, o, *]
+    Test8A(extern "Rust" fn(&'a int)),
+    Test8B(&'b [int]),
+    Test8C(&'b mut &'c str),
+}
+
+#[rustc_variance]
+struct Derived1<'w, 'x, 'y, 'z> { //~ ERROR region_params=[*, o, -, +]
+    f: Base<'z, 'y, 'x, 'w>
+}
+
+#[rustc_variance] // Combine - and + to yield o
+struct Derived2<'a, 'b, 'c> { //~ ERROR region_params=[o, o, *]
+    f: Base<'a, 'a, 'b, 'c>
+}
+
+#[rustc_variance] // Combine + and o to yield o (just pay attention to 'a here)
+struct Derived3<'a, 'b, 'c> { //~ ERROR region_params=[o, -, *]
+    f: Base<'a, 'b, 'a, 'c>
+}
+
+#[rustc_variance] // Combine + and * to yield + (just pay attention to 'a here)
+struct Derived4<'a, 'b, 'c> { //~ ERROR region_params=[+, -, o]
+    f: Base<'a, 'b, 'c, 'a>
+}
+
+fn main() {}
diff --git a/src/test/run-pass/regions-variance-contravariant-use-contravariant.rs b/src/test/run-pass/regions-variance-contravariant-use-contravariant.rs
new file mode 100644
index 00000000000..1cc9a501ab6
--- /dev/null
+++ b/src/test/run-pass/regions-variance-contravariant-use-contravariant.rs
@@ -0,0 +1,32 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that a type which is contravariant with respect to its region
+// parameter compiles successfully when used in a contravariant way.
+//
+// Note: see compile-fail/variance-regions-*.rs for the tests that check that the
+// variance inference works in the first place.
+
+struct Contravariant<'a> {
+    f: &'a int
+}
+
+fn use_<'a>(c: Contravariant<'a>) {
+    let x = 3;
+
+    // 'b winds up being inferred to this call.
+    // Contravariant<'a> <: Contravariant<'call> is true
+    // if 'call <= 'a, which is true, so no error.
+    collapse(&x, c);
+
+    fn collapse<'b>(x: &'b int, c: Contravariant<'b>) { }
+}
+
+fn main() {}
diff --git a/src/test/run-pass/regions-variance-covariant-use-covariant.rs b/src/test/run-pass/regions-variance-covariant-use-covariant.rs
new file mode 100644
index 00000000000..ca32f7a5258
--- /dev/null
+++ b/src/test/run-pass/regions-variance-covariant-use-covariant.rs
@@ -0,0 +1,29 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that a type which is covariant with respect to its region
+// parameter is successful when used in a covariant way.
+//
+// Note: see compile-fail/variance-regions-*.rs for the tests that
+// check that the variance inference works in the first place.
+
+// This is covariant with respect to 'a, meaning that
+// Covariant<'foo> <: Covariant<'static> because
+// 'foo <= 'static
+struct Covariant<'a> {
+    f: extern "Rust" fn(&'a int)
+}
+
+fn use_<'a>(c: Covariant<'a>) {
+    // OK Because Covariant<'a> <: Covariant<'static> iff 'a <= 'static
+    let _: Covariant<'static> = c;
+}
+
+fn main() {}