Port over type inference to using the new type relation stuff

19 files changed, 1140 insertions, 955 deletions

diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index f31f8e8d4ce..8a4790c17a4 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -122,6 +122,7 @@ pub mod middle {
     pub mod traits;
     pub mod ty;
     pub mod ty_fold;
+    pub mod ty_relate;
     pub mod ty_walk;
     pub mod weak_lang_items;
 }
diff --git a/src/librustc/middle/infer/bivariate.rs b/src/librustc/middle/infer/bivariate.rs
index 91e1fea7ca5..940dc75271c 100644
--- a/src/librustc/middle/infer/bivariate.rs
+++ b/src/librustc/middle/infer/bivariate.rs
@@ -25,66 +25,54 @@
 //! In particular, it might be enough to say (A,B) are bivariant for
 //! all (A,B).
 
-use middle::ty::BuiltinBounds;
+use super::combine::{self, CombineFields};
+use super::type_variable::{BiTo};
+
 use middle::ty::{self, Ty};
 use middle::ty::TyVar;
-use middle::infer::combine::*;
-use middle::infer::CombineResult;
-use middle::infer::type_variable::BiTo;
-use util::ppaux::Repr;
+use middle::ty_relate::{Relate, RelateResult, TypeRelation};
+use util::ppaux::{Repr};
 
-pub struct Bivariate<'f, 'tcx: 'f> {
-    fields: CombineFields<'f, 'tcx>
+pub struct Bivariate<'a, 'tcx: 'a> {
+    fields: CombineFields<'a, 'tcx>
 }
 
-#[allow(non_snake_case)]
-pub fn Bivariate<'f, 'tcx>(cf: CombineFields<'f, 'tcx>) -> Bivariate<'f, 'tcx> {
-    Bivariate { fields: cf }
+impl<'a, 'tcx> Bivariate<'a, 'tcx> {
+    pub fn new(fields: CombineFields<'a, 'tcx>) -> Bivariate<'a, 'tcx> {
+        Bivariate { fields: fields }
+    }
 }
 
-impl<'f, 'tcx> Combine<'tcx> for Bivariate<'f, 'tcx> {
-    fn tag(&self) -> String { "Bivariate".to_string() }
-    fn fields<'a>(&'a self) -> &'a CombineFields<'a, 'tcx> { &self.fields }
+impl<'a, 'tcx> TypeRelation<'a, 'tcx> for Bivariate<'a, 'tcx> {
+    fn tag(&self) -> &'static str { "Bivariate" }
 
-    fn tys_with_variance(&self, v: ty::Variance, a: Ty<'tcx>, b: Ty<'tcx>)
-                         -> CombineResult<'tcx, Ty<'tcx>>
-    {
-        match v {
-            ty::Invariant => self.equate().tys(a, b),
-            ty::Covariant => self.tys(a, b),
-            ty::Contravariant => self.tys(a, b),
-            ty::Bivariant => self.tys(a, b),
-        }
-    }
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> { self.fields.tcx() }
 
-    fn regions_with_variance(&self, v: ty::Variance, a: ty::Region, b: ty::Region)
-                             -> CombineResult<'tcx, ty::Region>
-    {
-        match v {
-            ty::Invariant => self.equate().regions(a, b),
-            ty::Covariant => self.regions(a, b),
-            ty::Contravariant => self.regions(a, b),
-            ty::Bivariant => self.regions(a, b),
-        }
-    }
+    fn a_is_expected(&self) -> bool { self.fields.a_is_expected }
 
-    fn regions(&self, a: ty::Region, _: ty::Region) -> CombineResult<'tcx, ty::Region> {
-        Ok(a)
-    }
-
-    fn builtin_bounds(&self,
-                      a: BuiltinBounds,
-                      b: BuiltinBounds)
-                      -> CombineResult<'tcx, BuiltinBounds>
+    fn relate_with_variance<T:Relate<'a,'tcx>>(&mut self,
+                                               variance: ty::Variance,
+                                               a: &T,
+                                               b: &T)
+                                               -> RelateResult<'tcx, T>
     {
-        if a != b {
-            Err(ty::terr_builtin_bounds(expected_found(self, a, b)))
-        } else {
-            Ok(a)
+        match variance {
+            // If we have Foo<A> and Foo is invariant w/r/t A,
+            // and we want to assert that
+            //
+            //     Foo<A> <: Foo<B> ||
+            //     Foo<B> <: Foo<A>
+            //
+            // then still A must equal B.
+            ty::Invariant => self.relate(a, b),
+
+            ty::Covariant => self.relate(a, b),
+            ty::Bivariant => self.relate(a, b),
+            ty::Contravariant => self.relate(a, b),
         }
     }
 
-    fn tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, Ty<'tcx>> {
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
         debug!("{}.tys({}, {})", self.tag(),
                a.repr(self.fields.infcx.tcx), b.repr(self.fields.infcx.tcx));
         if a == b { return Ok(a); }
@@ -109,17 +97,22 @@ impl<'f, 'tcx> Combine<'tcx> for Bivariate<'f, 'tcx> {
             }
 
             _ => {
-                super_tys(self, a, b)
+                combine::super_combine_tys(self.fields.infcx, self, a, b)
             }
         }
     }
 
-    fn binders<T>(&self, a: &ty::Binder<T>, b: &ty::Binder<T>) -> CombineResult<'tcx, ty::Binder<T>>
-        where T : Combineable<'tcx>
+    fn regions(&mut self, a: ty::Region, _: ty::Region) -> RelateResult<'tcx, ty::Region> {
+        Ok(a)
+    }
+
+    fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
+                  -> RelateResult<'tcx, ty::Binder<T>>
+        where T: Relate<'a,'tcx>
     {
         let a1 = ty::erase_late_bound_regions(self.tcx(), a);
         let b1 = ty::erase_late_bound_regions(self.tcx(), b);
-        let c = try!(Combineable::combine(self, &a1, &b1));
+        let c = try!(self.relate(&a1, &b1));
         Ok(ty::Binder(c))
     }
 }
diff --git a/src/librustc/middle/infer/combine.rs b/src/librustc/middle/infer/combine.rs
index fdff750bf46..86f12b669b3 100644
--- a/src/librustc/middle/infer/combine.rs
+++ b/src/librustc/middle/infer/combine.rs
@@ -37,394 +37,21 @@ use super::equate::Equate;
 use super::glb::Glb;
 use super::lub::Lub;
 use super::sub::Sub;
-use super::{InferCtxt, CombineResult};
+use super::{InferCtxt};
 use super::{MiscVariable, TypeTrace};
 use super::type_variable::{RelationDir, BiTo, EqTo, SubtypeOf, SupertypeOf};
 
-use middle::subst;
-use middle::subst::{ErasedRegions, NonerasedRegions, Substs};
-use middle::ty::{FloatVar, FnSig, IntVar, TyVar};
+use middle::ty::{TyVar};
 use middle::ty::{IntType, UintType};
-use middle::ty::BuiltinBounds;
 use middle::ty::{self, Ty};
 use middle::ty_fold;
 use middle::ty_fold::{TypeFolder, TypeFoldable};
+use middle::ty_relate::{self, Relate, RelateResult, TypeRelation};
 use util::ppaux::Repr;
 
-use std::rc::Rc;
-use syntax::ast::Unsafety;
 use syntax::ast;
-use syntax::abi;
 use syntax::codemap::Span;
 
-pub trait Combine<'tcx> : Sized {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.infcx().tcx }
-    fn tag(&self) -> String;
-
-    fn fields<'a>(&'a self) -> &'a CombineFields<'a, 'tcx>;
-
-    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx> { self.fields().infcx }
-    fn a_is_expected(&self) -> bool { self.fields().a_is_expected }
-    fn trace(&self) -> TypeTrace<'tcx> { self.fields().trace.clone() }
-    fn equate<'a>(&'a self) -> Equate<'a, 'tcx> { self.fields().equate() }
-    fn bivariate<'a>(&'a self) -> Bivariate<'a, 'tcx> { self.fields().bivariate() }
-
-    fn sub<'a>(&'a self) -> Sub<'a, 'tcx> { self.fields().sub() }
-    fn lub<'a>(&'a self) -> Lub<'a, 'tcx> { Lub(self.fields().clone()) }
-    fn glb<'a>(&'a self) -> Glb<'a, 'tcx> { Glb(self.fields().clone()) }
-
-    fn mts(&self, a: &ty::mt<'tcx>, b: &ty::mt<'tcx>) -> CombineResult<'tcx, ty::mt<'tcx>> {
-        debug!("{}.mts({}, {})",
-               self.tag(),
-               a.repr(self.tcx()),
-               b.repr(self.tcx()));
-
-        if a.mutbl != b.mutbl {
-            Err(ty::terr_mutability)
-        } else {
-            let mutbl = a.mutbl;
-            let variance = match mutbl {
-                ast::MutImmutable => ty::Covariant,
-                ast::MutMutable => ty::Invariant,
-            };
-            let ty = try!(self.tys_with_variance(variance, a.ty, b.ty));
-            Ok(ty::mt {ty: ty, mutbl: mutbl})
-        }
-    }
-
-    fn tys_with_variance(&self, variance: ty::Variance, a: Ty<'tcx>, b: Ty<'tcx>)
-                         -> CombineResult<'tcx, Ty<'tcx>>;
-
-    fn tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, Ty<'tcx>>;
-
-    fn regions_with_variance(&self, variance: ty::Variance, a: ty::Region, b: ty::Region)
-                             -> CombineResult<'tcx, ty::Region>;
-
-    fn regions(&self, a: ty::Region, b: ty::Region) -> CombineResult<'tcx, ty::Region>;
-
-    fn substs(&self,
-              item_def_id: ast::DefId,
-              a_subst: &subst::Substs<'tcx>,
-              b_subst: &subst::Substs<'tcx>)
-              -> CombineResult<'tcx, subst::Substs<'tcx>>
-    {
-        debug!("substs: item_def_id={} a_subst={} b_subst={}",
-               item_def_id.repr(self.infcx().tcx),
-               a_subst.repr(self.infcx().tcx),
-               b_subst.repr(self.infcx().tcx));
-
-        let variances = if self.infcx().tcx.variance_computed.get() {
-            Some(ty::item_variances(self.infcx().tcx, item_def_id))
-        } else {
-            None
-        };
-        self.substs_variances(variances.as_ref().map(|v| &**v), a_subst, b_subst)
-    }
-
-    fn substs_variances(&self,
-                        variances: Option<&ty::ItemVariances>,
-                        a_subst: &subst::Substs<'tcx>,
-                        b_subst: &subst::Substs<'tcx>)
-                        -> CombineResult<'tcx, subst::Substs<'tcx>>
-    {
-        let mut substs = subst::Substs::empty();
-
-        for &space in &subst::ParamSpace::all() {
-            let a_tps = a_subst.types.get_slice(space);
-            let b_tps = b_subst.types.get_slice(space);
-            let t_variances = variances.map(|v| v.types.get_slice(space));
-            let tps = try!(relate_type_params(self, t_variances, a_tps, b_tps));
-            substs.types.replace(space, tps);
-        }
-
-        match (&a_subst.regions, &b_subst.regions) {
-            (&ErasedRegions, _) | (_, &ErasedRegions) => {
-                substs.regions = ErasedRegions;
-            }
-
-            (&NonerasedRegions(ref a), &NonerasedRegions(ref b)) => {
-                for &space in &subst::ParamSpace::all() {
-                    let a_regions = a.get_slice(space);
-                    let b_regions = b.get_slice(space);
-                    let r_variances = variances.map(|v| v.regions.get_slice(space));
-                    let regions = try!(relate_region_params(self,
-                                                            r_variances,
-                                                            a_regions,
-                                                            b_regions));
-                    substs.mut_regions().replace(space, regions);
-                }
-            }
-        }
-
-        return Ok(substs);
-
-        fn relate_type_params<'tcx, C: Combine<'tcx>>(this: &C,
-                                                      variances: Option<&[ty::Variance]>,
-                                                      a_tys: &[Ty<'tcx>],
-                                                      b_tys: &[Ty<'tcx>])
-                                                      -> CombineResult<'tcx, Vec<Ty<'tcx>>>
-        {
-            if a_tys.len() != b_tys.len() {
-                return Err(ty::terr_ty_param_size(expected_found(this,
-                                                                 a_tys.len(),
-                                                                 b_tys.len())));
-            }
-
-            (0.. a_tys.len()).map(|i| {
-                let a_ty = a_tys[i];
-                let b_ty = b_tys[i];
-                let v = variances.map_or(ty::Invariant, |v| v[i]);
-                this.tys_with_variance(v, a_ty, b_ty)
-            }).collect()
-        }
-
-        fn relate_region_params<'tcx, C: Combine<'tcx>>(this: &C,
-                                                        variances: Option<&[ty::Variance]>,
-                                                        a_rs: &[ty::Region],
-                                                        b_rs: &[ty::Region])
-                                                        -> CombineResult<'tcx, Vec<ty::Region>>
-        {
-            let tcx = this.infcx().tcx;
-            let num_region_params = a_rs.len();
-
-            debug!("relate_region_params(\
-                   a_rs={}, \
-                   b_rs={},
-                   variances={})",
-                   a_rs.repr(tcx),
-                   b_rs.repr(tcx),
-                   variances.repr(tcx));
-
-            assert_eq!(num_region_params,
-                       variances.map_or(num_region_params,
-                                        |v| v.len()));
-
-            assert_eq!(num_region_params, b_rs.len());
-
-            (0..a_rs.len()).map(|i| {
-                let a_r = a_rs[i];
-                let b_r = b_rs[i];
-                let variance = variances.map_or(ty::Invariant, |v| v[i]);
-                this.regions_with_variance(variance, a_r, b_r)
-            }).collect()
-        }
-    }
-
-    fn bare_fn_tys(&self, a: &ty::BareFnTy<'tcx>,
-                   b: &ty::BareFnTy<'tcx>) -> CombineResult<'tcx, ty::BareFnTy<'tcx>> {
-        let unsafety = try!(self.unsafeties(a.unsafety, b.unsafety));
-        let abi = try!(self.abi(a.abi, b.abi));
-        let sig = try!(self.binders(&a.sig, &b.sig));
-        Ok(ty::BareFnTy {unsafety: unsafety,
-                         abi: abi,
-                         sig: sig})
-    }
-
-    fn fn_sigs(&self, a: &ty::FnSig<'tcx>, b: &ty::FnSig<'tcx>) -> CombineResult<'tcx, ty::FnSig<'tcx>> {
-        if a.variadic != b.variadic {
-            return Err(ty::terr_variadic_mismatch(expected_found(self, a.variadic, b.variadic)));
-        }
-
-        let inputs = try!(argvecs(self,
-                                  &a.inputs,
-                                  &b.inputs));
-
-        let output = try!(match (a.output, b.output) {
-            (ty::FnConverging(a_ty), ty::FnConverging(b_ty)) =>
-                Ok(ty::FnConverging(try!(self.tys(a_ty, b_ty)))),
-            (ty::FnDiverging, ty::FnDiverging) =>
-                Ok(ty::FnDiverging),
-            (a, b) =>
-                Err(ty::terr_convergence_mismatch(
-                    expected_found(self, a != ty::FnDiverging, b != ty::FnDiverging))),
-        });
-
-        return Ok(ty::FnSig {inputs: inputs,
-                             output: output,
-                             variadic: a.variadic});
-
-
-        fn argvecs<'tcx, C>(combiner: &C,
-                            a_args: &[Ty<'tcx>],
-                            b_args: &[Ty<'tcx>])
-                            -> CombineResult<'tcx, Vec<Ty<'tcx>>>
-                            where C: Combine<'tcx> {
-            if a_args.len() == b_args.len() {
-                a_args.iter().zip(b_args.iter())
-                    .map(|(a, b)| combiner.args(*a, *b)).collect()
-            } else {
-                Err(ty::terr_arg_count)
-            }
-        }
-    }
-
-    fn args(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, Ty<'tcx>> {
-        self.tys_with_variance(ty::Contravariant, a, b).and_then(|t| Ok(t))
-    }
-
-    fn unsafeties(&self, a: Unsafety, b: Unsafety) -> CombineResult<'tcx, Unsafety> {
-        if a != b {
-            Err(ty::terr_unsafety_mismatch(expected_found(self, a, b)))
-        } else {
-            Ok(a)
-        }
-    }
-
-    fn abi(&self, a: abi::Abi, b: abi::Abi) -> CombineResult<'tcx, abi::Abi> {
-        if a == b {
-            Ok(a)
-        } else {
-            Err(ty::terr_abi_mismatch(expected_found(self, a, b)))
-        }
-    }
-
-    fn projection_tys(&self,
-                      a: &ty::ProjectionTy<'tcx>,
-                      b: &ty::ProjectionTy<'tcx>)
-                      -> CombineResult<'tcx, ty::ProjectionTy<'tcx>>
-    {
-        if a.item_name != b.item_name {
-            Err(ty::terr_projection_name_mismatched(
-                expected_found(self, a.item_name, b.item_name)))
-        } else {
-            let trait_ref = try!(self.trait_refs(&*a.trait_ref, &*b.trait_ref));
-            Ok(ty::ProjectionTy { trait_ref: Rc::new(trait_ref), item_name: a.item_name })
-        }
-    }
-
-    fn projection_predicates(&self,
-                             a: &ty::ProjectionPredicate<'tcx>,
-                             b: &ty::ProjectionPredicate<'tcx>)
-                             -> CombineResult<'tcx, ty::ProjectionPredicate<'tcx>>
-    {
-        let projection_ty = try!(self.projection_tys(&a.projection_ty, &b.projection_ty));
-        let ty = try!(self.tys(a.ty, b.ty));
-        Ok(ty::ProjectionPredicate { projection_ty: projection_ty, ty: ty })
-    }
-
-    fn projection_bounds(&self,
-                         a: &Vec<ty::PolyProjectionPredicate<'tcx>>,
-                         b: &Vec<ty::PolyProjectionPredicate<'tcx>>)
-                         -> CombineResult<'tcx, Vec<ty::PolyProjectionPredicate<'tcx>>>
-    {
-        // To be compatible, `a` and `b` must be for precisely the
-        // same set of traits and item names. We always require that
-        // projection bounds lists are sorted by trait-def-id and item-name,
-        // so we can just iterate through the lists pairwise, so long as they are the
-        // same length.
-        if a.len() != b.len() {
-            Err(ty::terr_projection_bounds_length(expected_found(self, a.len(), b.len())))
-        } else {
-            a.iter()
-                .zip(b.iter())
-                .map(|(a, b)| self.binders(a, b))
-                .collect()
-        }
-    }
-
-    fn existential_bounds(&self,
-                          a: &ty::ExistentialBounds<'tcx>,
-                          b: &ty::ExistentialBounds<'tcx>)
-                          -> CombineResult<'tcx, ty::ExistentialBounds<'tcx>>
-    {
-        let r = try!(self.regions_with_variance(ty::Contravariant, a.region_bound, b.region_bound));
-        let nb = try!(self.builtin_bounds(a.builtin_bounds, b.builtin_bounds));
-        let pb = try!(self.projection_bounds(&a.projection_bounds, &b.projection_bounds));
-        Ok(ty::ExistentialBounds { region_bound: r,
-                                   builtin_bounds: nb,
-                                   projection_bounds: pb })
-    }
-
-    fn builtin_bounds(&self,
-                      a: BuiltinBounds,
-                      b: BuiltinBounds)
-                      -> CombineResult<'tcx, BuiltinBounds>
-    {
-        // Two sets of builtin bounds are only relatable if they are
-        // precisely the same (but see the coercion code).
-        if a != b {
-            Err(ty::terr_builtin_bounds(expected_found(self, a, b)))
-        } else {
-            Ok(a)
-        }
-    }
-
-    fn trait_refs(&self,
-                  a: &ty::TraitRef<'tcx>,
-                  b: &ty::TraitRef<'tcx>)
-                  -> CombineResult<'tcx, ty::TraitRef<'tcx>>
-    {
-        // Different traits cannot be related
-        if a.def_id != b.def_id {
-            Err(ty::terr_traits(expected_found(self, a.def_id, b.def_id)))
-        } else {
-            let substs = try!(self.substs(a.def_id, a.substs, b.substs));
-            Ok(ty::TraitRef { def_id: a.def_id, substs: self.tcx().mk_substs(substs) })
-        }
-    }
-
-    fn binders<T>(&self, a: &ty::Binder<T>, b: &ty::Binder<T>) -> CombineResult<'tcx, ty::Binder<T>>
-        where T : Combineable<'tcx>;
-    // this must be overridden to do correctly, so as to account for higher-ranked
-    // behavior
-}
-
-pub trait Combineable<'tcx> : Repr<'tcx> + TypeFoldable<'tcx> {
-    fn combine<C:Combine<'tcx>>(combiner: &C, a: &Self, b: &Self) -> CombineResult<'tcx, Self>;
-}
-
-impl<'tcx,T> Combineable<'tcx> for Rc<T>
-    where T : Combineable<'tcx>
-{
-    fn combine<C>(combiner: &C,
-                  a: &Rc<T>,
-                  b: &Rc<T>)
-                  -> CombineResult<'tcx, Rc<T>>
-                  where C: Combine<'tcx> {
-        Ok(Rc::new(try!(Combineable::combine(combiner, &**a, &**b))))
-    }
-}
-
-impl<'tcx> Combineable<'tcx> for ty::TraitRef<'tcx> {
-    fn combine<C>(combiner: &C,
-                  a: &ty::TraitRef<'tcx>,
-                  b: &ty::TraitRef<'tcx>)
-                  -> CombineResult<'tcx, ty::TraitRef<'tcx>>
-                  where C: Combine<'tcx> {
-        combiner.trait_refs(a, b)
-    }
-}
-
-impl<'tcx> Combineable<'tcx> for Ty<'tcx> {
-    fn combine<C>(combiner: &C,
-                  a: &Ty<'tcx>,
-                  b: &Ty<'tcx>)
-                  -> CombineResult<'tcx, Ty<'tcx>>
-                  where C: Combine<'tcx> {
-        combiner.tys(*a, *b)
-    }
-}
-
-impl<'tcx> Combineable<'tcx> for ty::ProjectionPredicate<'tcx> {
-    fn combine<C>(combiner: &C,
-                  a: &ty::ProjectionPredicate<'tcx>,
-                  b: &ty::ProjectionPredicate<'tcx>)
-                  -> CombineResult<'tcx, ty::ProjectionPredicate<'tcx>>
-                  where C: Combine<'tcx> {
-        combiner.projection_predicates(a, b)
-    }
-}
-
-impl<'tcx> Combineable<'tcx> for ty::FnSig<'tcx> {
-    fn combine<C>(combiner: &C,
-                  a: &ty::FnSig<'tcx>,
-                  b: &ty::FnSig<'tcx>)
-                  -> CombineResult<'tcx, ty::FnSig<'tcx>>
-                  where C: Combine<'tcx> {
-        combiner.fn_sigs(a, b)
-    }
-}
-
 #[derive(Clone)]
 pub struct CombineFields<'a, 'tcx: 'a> {
     pub infcx: &'a InferCtxt<'a, 'tcx>,
@@ -432,253 +59,133 @@ pub struct CombineFields<'a, 'tcx: 'a> {
     pub trace: TypeTrace<'tcx>,
 }
 
-pub fn expected_found<'tcx, C, T>(this: &C,
-                                  a: T,
-                                  b: T)
-                                  -> ty::expected_found<T>
-                                  where C: Combine<'tcx>
-{
-    expected_found_bool(this.a_is_expected(), a, b)
-}
-
-fn expected_found_bool<T>(a_is_expected: bool,
-                          a: T,
-                          b: T)
-                          -> ty::expected_found<T>
+pub fn super_combine_tys<'a,'tcx:'a,R>(infcx: &InferCtxt<'a, 'tcx>,
+                                       relation: &mut R,
+                                       a: Ty<'tcx>,
+                                       b: Ty<'tcx>)
+                                       -> RelateResult<'tcx, Ty<'tcx>>
+    where R: TypeRelation<'a,'tcx>
 {
-    if a_is_expected {
-        ty::expected_found {expected: a, found: b}
-    } else {
-        ty::expected_found {expected: b, found: a}
-    }
-}
-
-pub fn super_tys<'tcx, C>(this: &C,
-                          a: Ty<'tcx>,
-                          b: Ty<'tcx>)
-                          -> CombineResult<'tcx, Ty<'tcx>>
-                          where C: Combine<'tcx> {
-    let tcx = this.infcx().tcx;
-    let a_sty = &a.sty;
-    let b_sty = &b.sty;
-    debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
-    return match (a_sty, b_sty) {
-        // The "subtype" ought to be handling cases involving var:
-        (&ty::ty_infer(TyVar(_)), _)
-        | (_, &ty::ty_infer(TyVar(_))) =>
-            tcx.sess.bug(
-                &format!("{}: bot and var types should have been handled ({},{})",
-                this.tag(),
-                a.repr(this.infcx().tcx),
-                b.repr(this.infcx().tcx))),
-
-        (&ty::ty_err, _) | (_, &ty::ty_err) => Ok(tcx.types.err),
+    let a_is_expected = relation.a_is_expected();
 
+    match (&a.sty, &b.sty) {
         // Relate integral variables to other types
-        (&ty::ty_infer(IntVar(a_id)), &ty::ty_infer(IntVar(b_id))) => {
-            try!(this.infcx().int_unification_table
-                             .borrow_mut()
-                             .unify_var_var(a_id, b_id)
-                             .map_err(|e| int_unification_error(this.a_is_expected(), e)));
+        (&ty::ty_infer(ty::IntVar(a_id)), &ty::ty_infer(ty::IntVar(b_id))) => {
+            try!(infcx.int_unification_table
+                      .borrow_mut()
+                      .unify_var_var(a_id, b_id)
+                      .map_err(|e| int_unification_error(a_is_expected, e)));
             Ok(a)
         }
-        (&ty::ty_infer(IntVar(v_id)), &ty::ty_int(v)) => {
-            unify_integral_variable(this, this.a_is_expected(), v_id, IntType(v))
+        (&ty::ty_infer(ty::IntVar(v_id)), &ty::ty_int(v)) => {
+            unify_integral_variable(infcx, a_is_expected, v_id, IntType(v))
         }
-        (&ty::ty_int(v), &ty::ty_infer(IntVar(v_id))) => {
-            unify_integral_variable(this, !this.a_is_expected(), v_id, IntType(v))
+        (&ty::ty_int(v), &ty::ty_infer(ty::IntVar(v_id))) => {
+            unify_integral_variable(infcx, !a_is_expected, v_id, IntType(v))
         }
-        (&ty::ty_infer(IntVar(v_id)), &ty::ty_uint(v)) => {
-            unify_integral_variable(this, this.a_is_expected(), v_id, UintType(v))
+        (&ty::ty_infer(ty::IntVar(v_id)), &ty::ty_uint(v)) => {
+            unify_integral_variable(infcx, a_is_expected, v_id, UintType(v))
         }
-        (&ty::ty_uint(v), &ty::ty_infer(IntVar(v_id))) => {
-            unify_integral_variable(this, !this.a_is_expected(), v_id, UintType(v))
+        (&ty::ty_uint(v), &ty::ty_infer(ty::IntVar(v_id))) => {
+            unify_integral_variable(infcx, !a_is_expected, v_id, UintType(v))
         }
 
         // Relate floating-point variables to other types
-        (&ty::ty_infer(FloatVar(a_id)), &ty::ty_infer(FloatVar(b_id))) => {
-            try!(this.infcx().float_unification_table
-                             .borrow_mut()
-                             .unify_var_var(a_id, b_id)
-                             .map_err(|e| float_unification_error(this.a_is_expected(), e)));
+        (&ty::ty_infer(ty::FloatVar(a_id)), &ty::ty_infer(ty::FloatVar(b_id))) => {
+            try!(infcx.float_unification_table
+                      .borrow_mut()
+                      .unify_var_var(a_id, b_id)
+                      .map_err(|e| float_unification_error(relation.a_is_expected(), e)));
             Ok(a)
         }
-        (&ty::ty_infer(FloatVar(v_id)), &ty::ty_float(v)) => {
-            unify_float_variable(this, this.a_is_expected(), v_id, v)
-        }
-        (&ty::ty_float(v), &ty::ty_infer(FloatVar(v_id))) => {
-            unify_float_variable(this, !this.a_is_expected(), v_id, v)
-        }
-
-        (&ty::ty_char, _)
-        | (&ty::ty_bool, _)
-        | (&ty::ty_int(_), _)
-        | (&ty::ty_uint(_), _)
-        | (&ty::ty_float(_), _) => {
-            if a == b {
-                Ok(a)
-            } else {
-                Err(ty::terr_sorts(expected_found(this, a, b)))
-            }
-        }
-
-        (&ty::ty_param(ref a_p), &ty::ty_param(ref b_p)) if
-          a_p.idx == b_p.idx && a_p.space == b_p.space => Ok(a),
-
-        (&ty::ty_enum(a_id, a_substs), &ty::ty_enum(b_id, b_substs))
-          if a_id == b_id => {
-            let substs = try!(this.substs(a_id, a_substs, b_substs));
-            Ok(ty::mk_enum(tcx, a_id, tcx.mk_substs(substs)))
-        }
-
-        (&ty::ty_trait(ref a_), &ty::ty_trait(ref b_)) => {
-            debug!("Trying to match traits {:?} and {:?}", a, b);
-            let principal = try!(this.binders(&a_.principal, &b_.principal));
-            let bounds = try!(this.existential_bounds(&a_.bounds, &b_.bounds));
-            Ok(ty::mk_trait(tcx, principal, bounds))
-        }
-
-        (&ty::ty_struct(a_id, a_substs), &ty::ty_struct(b_id, b_substs))
-          if a_id == b_id => {
-            let substs = try!(this.substs(a_id, a_substs, b_substs));
-            Ok(ty::mk_struct(tcx, a_id, tcx.mk_substs(substs)))
-        }
-
-        (&ty::ty_closure(a_id, a_substs),
-         &ty::ty_closure(b_id, b_substs))
-          if a_id == b_id => {
-            // All ty_closure types with the same id represent
-            // the (anonymous) type of the same closure expression. So
-            // all of their regions should be equated.
-            let substs = try!(this.substs_variances(None, a_substs, b_substs));
-            Ok(ty::mk_closure(tcx, a_id, tcx.mk_substs(substs)))
-        }
-
-        (&ty::ty_uniq(a_inner), &ty::ty_uniq(b_inner)) => {
-            let typ = try!(this.tys(a_inner, b_inner));
-            Ok(ty::mk_uniq(tcx, typ))
-        }
-
-        (&ty::ty_ptr(ref a_mt), &ty::ty_ptr(ref b_mt)) => {
-            let mt = try!(this.mts(a_mt, b_mt));
-            Ok(ty::mk_ptr(tcx, mt))
-        }
-
-        (&ty::ty_rptr(a_r, ref a_mt), &ty::ty_rptr(b_r, ref b_mt)) => {
-            let r = try!(this.regions_with_variance(ty::Contravariant, *a_r, *b_r));
-            let mt = try!(this.mts(a_mt, b_mt));
-            Ok(ty::mk_rptr(tcx, tcx.mk_region(r), mt))
-        }
-
-        (&ty::ty_vec(a_t, Some(sz_a)), &ty::ty_vec(b_t, Some(sz_b))) => {
-            this.tys(a_t, b_t).and_then(|t| {
-                if sz_a == sz_b {
-                    Ok(ty::mk_vec(tcx, t, Some(sz_a)))
-                } else {
-                    Err(ty::terr_fixed_array_size(expected_found(this, sz_a, sz_b)))
-                }
-            })
-        }
-
-        (&ty::ty_vec(a_t, sz_a), &ty::ty_vec(b_t, sz_b)) => {
-            this.tys(a_t, b_t).and_then(|t| {
-                if sz_a == sz_b {
-                    Ok(ty::mk_vec(tcx, t, sz_a))
-                } else {
-                    Err(ty::terr_sorts(expected_found(this, a, b)))
-                }
-            })
-        }
-
-        (&ty::ty_str, &ty::ty_str) => Ok(ty::mk_str(tcx)),
-
-        (&ty::ty_tup(ref as_), &ty::ty_tup(ref bs)) => {
-            if as_.len() == bs.len() {
-                as_.iter().zip(bs.iter())
-                   .map(|(a, b)| this.tys(*a, *b))
-                   .collect::<Result<_, _>>()
-                   .map(|ts| ty::mk_tup(tcx, ts))
-            } else if as_.len() != 0 && bs.len() != 0 {
-                Err(ty::terr_tuple_size(
-                    expected_found(this, as_.len(), bs.len())))
-            } else {
-                Err(ty::terr_sorts(expected_found(this, a, b)))
-            }
+        (&ty::ty_infer(ty::FloatVar(v_id)), &ty::ty_float(v)) => {
+            unify_float_variable(infcx, a_is_expected, v_id, v)
         }
-
-        (&ty::ty_bare_fn(a_opt_def_id, a_fty), &ty::ty_bare_fn(b_opt_def_id, b_fty))
-            if a_opt_def_id == b_opt_def_id =>
-        {
-            let fty = try!(this.bare_fn_tys(a_fty, b_fty));
-            Ok(ty::mk_bare_fn(tcx, a_opt_def_id, tcx.mk_bare_fn(fty)))
+        (&ty::ty_float(v), &ty::ty_infer(ty::FloatVar(v_id))) => {
+            unify_float_variable(infcx, !a_is_expected, v_id, v)
         }
 
-        (&ty::ty_projection(ref a_data), &ty::ty_projection(ref b_data)) => {
-            let projection_ty = try!(this.projection_tys(a_data, b_data));
-            Ok(ty::mk_projection(tcx, projection_ty.trait_ref, projection_ty.item_name))
+        // All other cases of inference are errors
+        (&ty::ty_infer(_), _) |
+        (_, &ty::ty_infer(_)) => {
+            Err(ty::terr_sorts(ty_relate::expected_found(relation, &a, &b)))
         }
 
-        _ => Err(ty::terr_sorts(expected_found(this, a, b))),
-    };
 
-    fn unify_integral_variable<'tcx, C>(this: &C,
-                                        vid_is_expected: bool,
-                                        vid: ty::IntVid,
-                                        val: ty::IntVarValue)
-                                        -> CombineResult<'tcx, Ty<'tcx>>
-        where C: Combine<'tcx>
-    {
-        try!(this.infcx()
-                 .int_unification_table
-                 .borrow_mut()
-                 .unify_var_value(vid, val)
-                 .map_err(|e| int_unification_error(vid_is_expected, e)));
-        match val {
-            IntType(v) => Ok(ty::mk_mach_int(this.tcx(), v)),
-            UintType(v) => Ok(ty::mk_mach_uint(this.tcx(), v)),
+        _ => {
+            ty_relate::super_relate_tys(relation, a, b)
         }
     }
+}
 
-    fn unify_float_variable<'tcx, C>(this: &C,
-                                     vid_is_expected: bool,
-                                     vid: ty::FloatVid,
-                                     val: ast::FloatTy)
-                                     -> CombineResult<'tcx, Ty<'tcx>>
-        where C: Combine<'tcx>
-    {
-        try!(this.infcx().float_unification_table
-                         .borrow_mut()
-                         .unify_var_value(vid, val)
-                         .map_err(|e| float_unification_error(vid_is_expected, e)));
-        Ok(ty::mk_mach_float(this.tcx(), val))
+fn unify_integral_variable<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
+                                    vid_is_expected: bool,
+                                    vid: ty::IntVid,
+                                    val: ty::IntVarValue)
+                                    -> RelateResult<'tcx, Ty<'tcx>>
+{
+    try!(infcx
+         .int_unification_table
+         .borrow_mut()
+         .unify_var_value(vid, val)
+         .map_err(|e| int_unification_error(vid_is_expected, e)));
+    match val {
+        IntType(v) => Ok(ty::mk_mach_int(infcx.tcx, v)),
+        UintType(v) => Ok(ty::mk_mach_uint(infcx.tcx, v)),
     }
 }
 
-impl<'f, 'tcx> CombineFields<'f, 'tcx> {
-    pub fn switch_expected(&self) -> CombineFields<'f, 'tcx> {
+fn unify_float_variable<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
+                                 vid_is_expected: bool,
+                                 vid: ty::FloatVid,
+                                 val: ast::FloatTy)
+                                 -> RelateResult<'tcx, Ty<'tcx>>
+{
+    try!(infcx
+         .float_unification_table
+         .borrow_mut()
+         .unify_var_value(vid, val)
+         .map_err(|e| float_unification_error(vid_is_expected, e)));
+    Ok(ty::mk_mach_float(infcx.tcx, val))
+}
+
+impl<'a, 'tcx> CombineFields<'a, 'tcx> {
+    pub fn tcx(&self) -> &'a ty::ctxt<'tcx> {
+        self.infcx.tcx
+    }
+
+    pub fn switch_expected(&self) -> CombineFields<'a, 'tcx> {
         CombineFields {
             a_is_expected: !self.a_is_expected,
             ..(*self).clone()
         }
     }
 
-    fn equate(&self) -> Equate<'f, 'tcx> {
-        Equate((*self).clone())
+    pub fn equate(&self) -> Equate<'a, 'tcx> {
+        Equate::new(self.clone())
+    }
+
+    pub fn bivariate(&self) -> Bivariate<'a, 'tcx> {
+        Bivariate::new(self.clone())
+    }
+
+    pub fn sub(&self) -> Sub<'a, 'tcx> {
+        Sub::new(self.clone())
     }
 
-    fn bivariate(&self) -> Bivariate<'f, 'tcx> {
-        Bivariate((*self).clone())
+    pub fn lub(&self) -> Lub<'a, 'tcx> {
+        Lub::new(self.clone())
     }
 
-    fn sub(&self) -> Sub<'f, 'tcx> {
-        Sub((*self).clone())
+    pub fn glb(&self) -> Glb<'a, 'tcx> {
+        Glb::new(self.clone())
     }
 
     pub fn instantiate(&self,
                        a_ty: Ty<'tcx>,
                        dir: RelationDir,
                        b_vid: ty::TyVid)
-                       -> CombineResult<'tcx, ()>
+                       -> RelateResult<'tcx, ()>
     {
         let tcx = self.infcx.tcx;
         let mut stack = Vec::new();
@@ -742,15 +249,12 @@ impl<'f, 'tcx> CombineFields<'f, 'tcx> {
             // relations wind up attributed to the same spans. We need
             // to associate causes/spans with each of the relations in
             // the stack to get this right.
-            match dir {
-                BiTo => try!(self.bivariate().tys(a_ty, b_ty)),
-
-                EqTo => try!(self.equate().tys(a_ty, b_ty)),
-
-                SubtypeOf => try!(self.sub().tys(a_ty, b_ty)),
-
-                SupertypeOf => try!(self.sub().tys_with_variance(ty::Contravariant, a_ty, b_ty)),
-            };
+            try!(match dir {
+                BiTo => self.bivariate().relate(&a_ty, &b_ty),
+                EqTo => self.equate().relate(&a_ty, &b_ty),
+                SubtypeOf => self.sub().relate(&a_ty, &b_ty),
+                SupertypeOf => self.sub().relate_with_variance(ty::Contravariant, &a_ty, &b_ty),
+            });
         }
 
         Ok(())
@@ -764,7 +268,7 @@ impl<'f, 'tcx> CombineFields<'f, 'tcx> {
                   ty: Ty<'tcx>,
                   for_vid: ty::TyVid,
                   make_region_vars: bool)
-                  -> CombineResult<'tcx, Ty<'tcx>>
+                  -> RelateResult<'tcx, Ty<'tcx>>
     {
         let mut generalize = Generalizer {
             infcx: self.infcx,
@@ -858,18 +362,18 @@ impl<'cx, 'tcx> ty_fold::TypeFolder<'tcx> for Generalizer<'cx, 'tcx> {
     }
 }
 
-pub trait CombineResultCompare<'tcx, T> {
-    fn compare<F>(&self, t: T, f: F) -> CombineResult<'tcx, T> where
+pub trait RelateResultCompare<'tcx, T> {
+    fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T> where
         F: FnOnce() -> ty::type_err<'tcx>;
 }
 
-impl<'tcx, T:Clone + PartialEq> CombineResultCompare<'tcx, T> for CombineResult<'tcx, T> {
-    fn compare<F>(&self, t: T, f: F) -> CombineResult<'tcx, T> where
+impl<'tcx, T:Clone + PartialEq> RelateResultCompare<'tcx, T> for RelateResult<'tcx, T> {
+    fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T> where
         F: FnOnce() -> ty::type_err<'tcx>,
     {
-        (*self).clone().and_then(|s| {
+        self.clone().and_then(|s| {
             if s == t {
-                (*self).clone()
+                self.clone()
             } else {
                 Err(f())
             }
@@ -881,7 +385,7 @@ fn int_unification_error<'tcx>(a_is_expected: bool, v: (ty::IntVarValue, ty::Int
                                -> ty::type_err<'tcx>
 {
     let (a, b) = v;
-    ty::terr_int_mismatch(expected_found_bool(a_is_expected, a, b))
+    ty::terr_int_mismatch(ty_relate::expected_found_bool(a_is_expected, &a, &b))
 }
 
 fn float_unification_error<'tcx>(a_is_expected: bool,
@@ -889,5 +393,5 @@ fn float_unification_error<'tcx>(a_is_expected: bool,
                                  -> ty::type_err<'tcx>
 {
     let (a, b) = v;
-    ty::terr_float_mismatch(expected_found_bool(a_is_expected, a, b))
+    ty::terr_float_mismatch(ty_relate::expected_found_bool(a_is_expected, &a, &b))
 }
diff --git a/src/librustc/middle/infer/equate.rs b/src/librustc/middle/infer/equate.rs
index 59394d1dd37..2003f459d89 100644
--- a/src/librustc/middle/infer/equate.rs
+++ b/src/librustc/middle/infer/equate.rs
@@ -8,51 +8,43 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use super::combine::{self, CombineFields};
+use super::higher_ranked::HigherRankedRelations;
+use super::{Subtype};
+use super::type_variable::{EqTo};
+
 use middle::ty::{self, Ty};
 use middle::ty::TyVar;
-use middle::infer::combine::*;
-use middle::infer::CombineResult;
-use middle::infer::Subtype;
-use middle::infer::type_variable::EqTo;
-use util::ppaux::Repr;
+use middle::ty_relate::{Relate, RelateResult, TypeRelation};
+use util::ppaux::{Repr};
 
-pub struct Equate<'f, 'tcx: 'f> {
-    fields: CombineFields<'f, 'tcx>
+pub struct Equate<'a, 'tcx: 'a> {
+    fields: CombineFields<'a, 'tcx>
 }
 
-#[allow(non_snake_case)]
-pub fn Equate<'f, 'tcx>(cf: CombineFields<'f, 'tcx>) -> Equate<'f, 'tcx> {
-    Equate { fields: cf }
+impl<'a, 'tcx> Equate<'a, 'tcx> {
+    pub fn new(fields: CombineFields<'a, 'tcx>) -> Equate<'a, 'tcx> {
+        Equate { fields: fields }
+    }
 }
 
-impl<'f, 'tcx> Combine<'tcx> for Equate<'f, 'tcx> {
-    fn tag(&self) -> String { "Equate".to_string() }
-    fn fields<'a>(&'a self) -> &'a CombineFields<'a, 'tcx> { &self.fields }
+impl<'a, 'tcx> TypeRelation<'a,'tcx> for Equate<'a, 'tcx> {
+    fn tag(&self) -> &'static str { "Equate" }
 
-    fn tys_with_variance(&self, _: ty::Variance, a: Ty<'tcx>, b: Ty<'tcx>)
-                         -> CombineResult<'tcx, Ty<'tcx>>
-    {
-        // Once we're equating, it doesn't matter what the variance is.
-        self.tys(a, b)
-    }
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> { self.fields.tcx() }
 
-    fn regions_with_variance(&self, _: ty::Variance, a: ty::Region, b: ty::Region)
-                             -> CombineResult<'tcx, ty::Region>
-    {
-        // Once we're equating, it doesn't matter what the variance is.
-        self.regions(a, b)
-    }
+    fn a_is_expected(&self) -> bool { self.fields.a_is_expected }
 
-    fn regions(&self, a: ty::Region, b: ty::Region) -> CombineResult<'tcx, ty::Region> {
-        debug!("{}.regions({}, {})",
-               self.tag(),
-               a.repr(self.fields.infcx.tcx),
-               b.repr(self.fields.infcx.tcx));
-        self.infcx().region_vars.make_eqregion(Subtype(self.trace()), a, b);
-        Ok(a)
+    fn relate_with_variance<T:Relate<'a,'tcx>>(&mut self,
+                                               _: ty::Variance,
+                                               a: &T,
+                                               b: &T)
+                                               -> RelateResult<'tcx, T>
+    {
+        self.relate(a, b)
     }
 
-    fn tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, Ty<'tcx>> {
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
         debug!("{}.tys({}, {})", self.tag(),
                a.repr(self.fields.infcx.tcx), b.repr(self.fields.infcx.tcx));
         if a == b { return Ok(a); }
@@ -77,15 +69,26 @@ impl<'f, 'tcx> Combine<'tcx> for Equate<'f, 'tcx> {
             }
 
             _ => {
-                super_tys(self, a, b)
+                combine::super_combine_tys(self.fields.infcx, self, a, b)
             }
         }
     }
 
-    fn binders<T>(&self, a: &ty::Binder<T>, b: &ty::Binder<T>) -> CombineResult<'tcx, ty::Binder<T>>
-        where T : Combineable<'tcx>
+    fn regions(&mut self, a: ty::Region, b: ty::Region) -> RelateResult<'tcx, ty::Region> {
+        debug!("{}.regions({}, {})",
+               self.tag(),
+               a.repr(self.fields.infcx.tcx),
+               b.repr(self.fields.infcx.tcx));
+        let origin = Subtype(self.fields.trace.clone());
+        self.fields.infcx.region_vars.make_eqregion(origin, a, b);
+        Ok(a)
+    }
+
+    fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
+                  -> RelateResult<'tcx, ty::Binder<T>>
+        where T: Relate<'a, 'tcx>
     {
-        try!(self.sub().binders(a, b));
-        self.sub().binders(b, a)
+        try!(self.fields.higher_ranked_sub(a, b));
+        self.fields.higher_ranked_sub(b, a)
     }
 }
diff --git a/src/librustc/middle/infer/glb.rs b/src/librustc/middle/infer/glb.rs
index 28c0b4df7f4..5822fb0f2d4 100644
--- a/src/librustc/middle/infer/glb.rs
+++ b/src/librustc/middle/infer/glb.rs
@@ -8,67 +8,79 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use super::combine::*;
-use super::lattice::*;
+use super::combine::CombineFields;
 use super::higher_ranked::HigherRankedRelations;
-use super::CombineResult;
+use super::InferCtxt;
+use super::lattice::{self, LatticeDir};
 use super::Subtype;
 
 use middle::ty::{self, Ty};
+use middle::ty_relate::{Relate, RelateResult, TypeRelation};
 use util::ppaux::Repr;
 
 /// "Greatest lower bound" (common subtype)
-pub struct Glb<'f, 'tcx: 'f> {
-    fields: CombineFields<'f, 'tcx>
+pub struct Glb<'a, 'tcx: 'a> {
+    fields: CombineFields<'a, 'tcx>
 }
 
-#[allow(non_snake_case)]
-pub fn Glb<'f, 'tcx>(cf: CombineFields<'f, 'tcx>) -> Glb<'f, 'tcx> {
-    Glb { fields: cf }
+impl<'a, 'tcx> Glb<'a, 'tcx> {
+    pub fn new(fields: CombineFields<'a, 'tcx>) -> Glb<'a, 'tcx> {
+        Glb { fields: fields }
+    }
 }
 
-impl<'f, 'tcx> Combine<'tcx> for Glb<'f, 'tcx> {
-    fn tag(&self) -> String { "Glb".to_string() }
-    fn fields<'a>(&'a self) -> &'a CombineFields<'a, 'tcx> { &self.fields }
+impl<'a, 'tcx> TypeRelation<'a, 'tcx> for Glb<'a, 'tcx> {
+    fn tag(&self) -> &'static str { "Glb" }
+
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> { self.fields.tcx() }
+
+    fn a_is_expected(&self) -> bool { self.fields.a_is_expected }
 
-    fn tys_with_variance(&self, v: ty::Variance, a: Ty<'tcx>, b: Ty<'tcx>)
-                         -> CombineResult<'tcx, Ty<'tcx>>
+    fn relate_with_variance<T:Relate<'a,'tcx>>(&mut self,
+                                               variance: ty::Variance,
+                                               a: &T,
+                                               b: &T)
+                                               -> RelateResult<'tcx, T>
     {
-        match v {
-            ty::Invariant => self.equate().tys(a, b),
-            ty::Covariant => self.tys(a, b),
-            ty::Bivariant => self.bivariate().tys(a, b),
-            ty::Contravariant => self.lub().tys(a, b),
+        match variance {
+            ty::Invariant => self.fields.equate().relate(a, b),
+            ty::Covariant => self.relate(a, b),
+            ty::Bivariant => self.fields.bivariate().relate(a, b),
+            ty::Contravariant => self.fields.lub().relate(a, b),
         }
     }
 
-    fn regions_with_variance(&self, v: ty::Variance, a: ty::Region, b: ty::Region)
-                             -> CombineResult<'tcx, ty::Region>
-    {
-        match v {
-            ty::Invariant => self.equate().regions(a, b),
-            ty::Covariant => self.regions(a, b),
-            ty::Bivariant => self.bivariate().regions(a, b),
-            ty::Contravariant => self.lub().regions(a, b),
-        }
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        lattice::super_lattice_tys(self, a, b)
     }
 
-    fn regions(&self, a: ty::Region, b: ty::Region) -> CombineResult<'tcx, ty::Region> {
+    fn regions(&mut self, a: ty::Region, b: ty::Region) -> RelateResult<'tcx, ty::Region> {
         debug!("{}.regions({}, {})",
                self.tag(),
                a.repr(self.fields.infcx.tcx),
                b.repr(self.fields.infcx.tcx));
 
-        Ok(self.fields.infcx.region_vars.glb_regions(Subtype(self.trace()), a, b))
+        let origin = Subtype(self.fields.trace.clone());
+        Ok(self.fields.infcx.region_vars.glb_regions(origin, a, b))
     }
 
-    fn tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, Ty<'tcx>> {
-        super_lattice_tys(self, a, b)
+    fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
+                  -> RelateResult<'tcx, ty::Binder<T>>
+        where T: Relate<'a, 'tcx>
+    {
+        self.fields.higher_ranked_glb(a, b)
     }
+}
 
-    fn binders<T>(&self, a: &ty::Binder<T>, b: &ty::Binder<T>) -> CombineResult<'tcx, ty::Binder<T>>
-        where T : Combineable<'tcx>
-    {
-        self.higher_ranked_glb(a, b)
+impl<'a, 'tcx> LatticeDir<'a,'tcx> for Glb<'a, 'tcx> {
+    fn infcx(&self) -> &'a InferCtxt<'a,'tcx> {
+        self.fields.infcx
+    }
+
+    fn relate_bound(&self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()> {
+        let mut sub = self.fields.sub();
+        try!(sub.relate(&v, &a));
+        try!(sub.relate(&v, &b));
+        Ok(())
     }
 }
diff --git a/src/librustc/middle/infer/higher_ranked/mod.rs b/src/librustc/middle/infer/higher_ranked/mod.rs
index 9280ffd0654..f347d28b93c 100644
--- a/src/librustc/middle/infer/higher_ranked/mod.rs
+++ b/src/librustc/middle/infer/higher_ranked/mod.rs
@@ -11,25 +11,26 @@
 //! Helper routines for higher-ranked things. See the `doc` module at
 //! the end of the file for details.
 
-use super::{CombinedSnapshot, CombineResult, InferCtxt, HigherRankedType, SkolemizationMap};
-use super::combine::{Combine, Combineable};
+use super::{CombinedSnapshot, InferCtxt, HigherRankedType, SkolemizationMap};
+use super::combine::CombineFields;
 
 use middle::subst;
 use middle::ty::{self, Binder};
 use middle::ty_fold::{self, TypeFoldable};
+use middle::ty_relate::{Relate, RelateResult, TypeRelation};
 use syntax::codemap::Span;
 use util::nodemap::{FnvHashMap, FnvHashSet};
 use util::ppaux::Repr;
 
-pub trait HigherRankedRelations<'tcx> {
-    fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> CombineResult<'tcx, Binder<T>>
-        where T : Combineable<'tcx>;
+pub trait HigherRankedRelations<'a,'tcx> {
+    fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
+        where T: Relate<'a,'tcx>;
 
-    fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> CombineResult<'tcx, Binder<T>>
-        where T : Combineable<'tcx>;
+    fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
+        where T: Relate<'a,'tcx>;
 
-    fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> CombineResult<'tcx, Binder<T>>
-        where T : Combineable<'tcx>;
+    fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
+        where T: Relate<'a,'tcx>;
 }
 
 trait InferCtxtExt {
@@ -40,15 +41,15 @@ trait InferCtxtExt {
                                         -> Vec<ty::RegionVid>;
 }
 
-impl<'tcx,C> HigherRankedRelations<'tcx> for C
-    where C : Combine<'tcx>
-{
+impl<'a,'tcx> HigherRankedRelations<'a,'tcx> for CombineFields<'a,'tcx> {
     fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>)
-                            -> CombineResult<'tcx, Binder<T>>
-        where T : Combineable<'tcx>
+                            -> RelateResult<'tcx, Binder<T>>
+        where T: Relate<'a,'tcx>
     {
+        let tcx = self.infcx.tcx;
+
         debug!("higher_ranked_sub(a={}, b={})",
-               a.repr(self.tcx()), b.repr(self.tcx()));
+               a.repr(tcx), b.repr(tcx));
 
         // Rather than checking the subtype relationship between `a` and `b`
         // as-is, we need to do some extra work here in order to make sure
@@ -60,32 +61,32 @@ impl<'tcx,C> HigherRankedRelations<'tcx> for C
 
         // Start a snapshot so we can examine "all bindings that were
         // created as part of this type comparison".
-        return self.infcx().commit_if_ok(|snapshot| {
+        return self.infcx.commit_if_ok(|snapshot| {
             // First, we instantiate each bound region in the subtype with a fresh
             // region variable.
             let (a_prime, _) =
-                self.infcx().replace_late_bound_regions_with_fresh_var(
-                    self.trace().origin.span(),
+                self.infcx.replace_late_bound_regions_with_fresh_var(
+                    self.trace.origin.span(),
                     HigherRankedType,
                     a);
 
             // Second, we instantiate each bound region in the supertype with a
             // fresh concrete region.
             let (b_prime, skol_map) =
-                self.infcx().skolemize_late_bound_regions(b, snapshot);
+                self.infcx.skolemize_late_bound_regions(b, snapshot);
 
-            debug!("a_prime={}", a_prime.repr(self.tcx()));
-            debug!("b_prime={}", b_prime.repr(self.tcx()));
+            debug!("a_prime={}", a_prime.repr(tcx));
+            debug!("b_prime={}", b_prime.repr(tcx));
 
             // Compare types now that bound regions have been replaced.
-            let result = try!(Combineable::combine(self, &a_prime, &b_prime));
+            let result = try!(self.sub().relate(&a_prime, &b_prime));
 
             // Presuming type comparison succeeds, we need to check
             // that the skolemized regions do not "leak".
-            match leak_check(self.infcx(), &skol_map, snapshot) {
+            match leak_check(self.infcx, &skol_map, snapshot) {
                 Ok(()) => { }
                 Err((skol_br, tainted_region)) => {
-                    if self.a_is_expected() {
+                    if self.a_is_expected {
                         debug!("Not as polymorphic!");
                         return Err(ty::terr_regions_insufficiently_polymorphic(skol_br,
                                                                                tainted_region));
@@ -98,42 +99,42 @@ impl<'tcx,C> HigherRankedRelations<'tcx> for C
             }
 
             debug!("higher_ranked_sub: OK result={}",
-                   result.repr(self.tcx()));
+                   result.repr(tcx));
 
             Ok(ty::Binder(result))
         });
     }
 
-    fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> CombineResult<'tcx, Binder<T>>
-        where T : Combineable<'tcx>
+    fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
+        where T: Relate<'a,'tcx>
     {
         // Start a snapshot so we can examine "all bindings that were
         // created as part of this type comparison".
-        return self.infcx().commit_if_ok(|snapshot| {
+        return self.infcx.commit_if_ok(|snapshot| {
             // Instantiate each bound region with a fresh region variable.
-            let span = self.trace().origin.span();
+            let span = self.trace.origin.span();
             let (a_with_fresh, a_map) =
-                self.infcx().replace_late_bound_regions_with_fresh_var(
+                self.infcx.replace_late_bound_regions_with_fresh_var(
                     span, HigherRankedType, a);
             let (b_with_fresh, _) =
-                self.infcx().replace_late_bound_regions_with_fresh_var(
+                self.infcx.replace_late_bound_regions_with_fresh_var(
                     span, HigherRankedType, b);
 
             // Collect constraints.
             let result0 =
-                try!(Combineable::combine(self, &a_with_fresh, &b_with_fresh));
+                try!(self.lub().relate(&a_with_fresh, &b_with_fresh));
             let result0 =
-                self.infcx().resolve_type_vars_if_possible(&result0);
+                self.infcx.resolve_type_vars_if_possible(&result0);
             debug!("lub result0 = {}", result0.repr(self.tcx()));
 
             // Generalize the regions appearing in result0 if possible
-            let new_vars = self.infcx().region_vars_confined_to_snapshot(snapshot);
-            let span = self.trace().origin.span();
+            let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot);
+            let span = self.trace.origin.span();
             let result1 =
                 fold_regions_in(
                     self.tcx(),
                     &result0,
-                    |r, debruijn| generalize_region(self.infcx(), span, snapshot, debruijn,
+                    |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn,
                                                     &new_vars, &a_map, r));
 
             debug!("lub({},{}) = {}",
@@ -194,40 +195,40 @@ impl<'tcx,C> HigherRankedRelations<'tcx> for C
         }
     }
 
-    fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> CombineResult<'tcx, Binder<T>>
-        where T : Combineable<'tcx>
+    fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
+        where T: Relate<'a,'tcx>
     {
-        debug!("{}.higher_ranked_glb({}, {})",
-               self.tag(), a.repr(self.tcx()), b.repr(self.tcx()));
+        debug!("higher_ranked_glb({}, {})",
+               a.repr(self.tcx()), b.repr(self.tcx()));
 
         // Make a snapshot so we can examine "all bindings that were
         // created as part of this type comparison".
-        return self.infcx().commit_if_ok(|snapshot| {
+        return self.infcx.commit_if_ok(|snapshot| {
             // Instantiate each bound region with a fresh region variable.
             let (a_with_fresh, a_map) =
-                self.infcx().replace_late_bound_regions_with_fresh_var(
-                    self.trace().origin.span(), HigherRankedType, a);
+                self.infcx.replace_late_bound_regions_with_fresh_var(
+                    self.trace.origin.span(), HigherRankedType, a);
             let (b_with_fresh, b_map) =
-                self.infcx().replace_late_bound_regions_with_fresh_var(
-                    self.trace().origin.span(), HigherRankedType, b);
+                self.infcx.replace_late_bound_regions_with_fresh_var(
+                    self.trace.origin.span(), HigherRankedType, b);
             let a_vars = var_ids(self, &a_map);
             let b_vars = var_ids(self, &b_map);
 
             // Collect constraints.
             let result0 =
-                try!(Combineable::combine(self, &a_with_fresh, &b_with_fresh));
+                try!(self.glb().relate(&a_with_fresh, &b_with_fresh));
             let result0 =
-                self.infcx().resolve_type_vars_if_possible(&result0);
+                self.infcx.resolve_type_vars_if_possible(&result0);
             debug!("glb result0 = {}", result0.repr(self.tcx()));
 
             // Generalize the regions appearing in result0 if possible
-            let new_vars = self.infcx().region_vars_confined_to_snapshot(snapshot);
-            let span = self.trace().origin.span();
+            let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot);
+            let span = self.trace.origin.span();
             let result1 =
                 fold_regions_in(
                     self.tcx(),
                     &result0,
-                    |r, debruijn| generalize_region(self.infcx(), span, snapshot, debruijn,
+                    |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn,
                                                     &new_vars,
                                                     &a_map, &a_vars, &b_vars,
                                                     r));
@@ -332,17 +333,19 @@ impl<'tcx,C> HigherRankedRelations<'tcx> for C
     }
 }
 
-fn var_ids<'tcx, T: Combine<'tcx>>(combiner: &T,
-                                   map: &FnvHashMap<ty::BoundRegion, ty::Region>)
-                                   -> Vec<ty::RegionVid> {
-    map.iter().map(|(_, r)| match *r {
-            ty::ReInfer(ty::ReVar(r)) => { r }
-            r => {
-                combiner.infcx().tcx.sess.span_bug(
-                    combiner.trace().origin.span(),
-                    &format!("found non-region-vid: {:?}", r));
-            }
-        }).collect()
+fn var_ids<'a, 'tcx>(fields: &CombineFields<'a, 'tcx>,
+                      map: &FnvHashMap<ty::BoundRegion, ty::Region>)
+                     -> Vec<ty::RegionVid> {
+    map.iter()
+       .map(|(_, r)| match *r {
+           ty::ReInfer(ty::ReVar(r)) => { r }
+           r => {
+               fields.tcx().sess.span_bug(
+                   fields.trace.origin.span(),
+                   &format!("found non-region-vid: {:?}", r));
+           }
+       })
+       .collect()
 }
 
 fn is_var_in_set(new_vars: &[ty::RegionVid], r: ty::Region) -> bool {
@@ -356,8 +359,8 @@ fn fold_regions_in<'tcx, T, F>(tcx: &ty::ctxt<'tcx>,
                                unbound_value: &T,
                                mut fldr: F)
                                -> T
-    where T : Combineable<'tcx>,
-          F : FnMut(ty::Region, ty::DebruijnIndex) -> ty::Region,
+    where T: TypeFoldable<'tcx>,
+          F: FnMut(ty::Region, ty::DebruijnIndex) -> ty::Region,
 {
     unbound_value.fold_with(&mut ty_fold::RegionFolder::new(tcx, &mut |region, current_depth| {
         // we should only be encountering "escaping" late-bound regions here,
diff --git a/src/librustc/middle/infer/lattice.rs b/src/librustc/middle/infer/lattice.rs
index 6cbf20f26ae..57001083b03 100644
--- a/src/librustc/middle/infer/lattice.rs
+++ b/src/librustc/middle/infer/lattice.rs
@@ -29,48 +29,32 @@
 //! over a `LatticeValue`, which is a value defined with respect to
 //! a lattice.
 
-use super::*;
-use super::combine::*;
-use super::glb::Glb;
-use super::lub::Lub;
+use super::combine;
+use super::InferCtxt;
 
 use middle::ty::TyVar;
 use middle::ty::{self, Ty};
+use middle::ty_relate::{RelateResult, TypeRelation};
 use util::ppaux::Repr;
 
-pub trait LatticeDir<'tcx> {
+pub trait LatticeDir<'f,'tcx> : TypeRelation<'f,'tcx> {
+    fn infcx(&self) -> &'f InferCtxt<'f, 'tcx>;
+
     // Relates the type `v` to `a` and `b` such that `v` represents
     // the LUB/GLB of `a` and `b` as appropriate.
-    fn relate_bound(&self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, ()>;
-}
-
-impl<'a, 'tcx> LatticeDir<'tcx> for Lub<'a, 'tcx> {
-    fn relate_bound(&self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, ()> {
-        let sub = self.sub();
-        try!(sub.tys(a, v));
-        try!(sub.tys(b, v));
-        Ok(())
-    }
-}
-
-impl<'a, 'tcx> LatticeDir<'tcx> for Glb<'a, 'tcx> {
-    fn relate_bound(&self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, ()> {
-        let sub = self.sub();
-        try!(sub.tys(v, a));
-        try!(sub.tys(v, b));
-        Ok(())
-    }
+    fn relate_bound(&self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()>;
 }
 
-pub fn super_lattice_tys<'tcx, L:LatticeDir<'tcx>+Combine<'tcx>>(this: &L,
-                                                                 a: Ty<'tcx>,
-                                                                 b: Ty<'tcx>)
-                                                                 -> CombineResult<'tcx, Ty<'tcx>>
+pub fn super_lattice_tys<'a,'tcx,L:LatticeDir<'a,'tcx>>(this: &mut L,
+                                                        a: Ty<'tcx>,
+                                                        b: Ty<'tcx>)
+                                                        -> RelateResult<'tcx, Ty<'tcx>>
+    where 'tcx: 'a
 {
     debug!("{}.lattice_tys({}, {})",
            this.tag(),
-           a.repr(this.infcx().tcx),
-           b.repr(this.infcx().tcx));
+           a.repr(this.tcx()),
+           b.repr(this.tcx()));
 
     if a == b {
         return Ok(a);
@@ -95,7 +79,7 @@ pub fn super_lattice_tys<'tcx, L:LatticeDir<'tcx>+Combine<'tcx>>(this: &L,
         }
 
         _ => {
-            super_tys(this, a, b)
+            combine::super_combine_tys(this.infcx(), this, a, b)
         }
     }
 }
diff --git a/src/librustc/middle/infer/lub.rs b/src/librustc/middle/infer/lub.rs
index 123b6cbcc0a..f456687be13 100644
--- a/src/librustc/middle/infer/lub.rs
+++ b/src/librustc/middle/infer/lub.rs
@@ -8,67 +8,80 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use super::combine::*;
+use super::combine::CombineFields;
 use super::higher_ranked::HigherRankedRelations;
-use super::lattice::*;
-use super::CombineResult;
+use super::InferCtxt;
+use super::lattice::{self, LatticeDir};
 use super::Subtype;
 
 use middle::ty::{self, Ty};
+use middle::ty_relate::{Relate, RelateResult, TypeRelation};
 use util::ppaux::Repr;
 
 /// "Least upper bound" (common supertype)
-pub struct Lub<'f, 'tcx: 'f> {
-    fields: CombineFields<'f, 'tcx>
+pub struct Lub<'a, 'tcx: 'a> {
+    fields: CombineFields<'a, 'tcx>
 }
 
-#[allow(non_snake_case)]
-pub fn Lub<'f, 'tcx>(cf: CombineFields<'f, 'tcx>) -> Lub<'f, 'tcx> {
-    Lub { fields: cf }
+impl<'a, 'tcx> Lub<'a, 'tcx> {
+    pub fn new(fields: CombineFields<'a, 'tcx>) -> Lub<'a, 'tcx> {
+        Lub { fields: fields }
+    }
 }
 
-impl<'f, 'tcx> Combine<'tcx> for Lub<'f, 'tcx> {
-    fn tag(&self) -> String { "Lub".to_string() }
-    fn fields<'a>(&'a self) -> &'a CombineFields<'a, 'tcx> { &self.fields }
+impl<'a, 'tcx> TypeRelation<'a, 'tcx> for Lub<'a, 'tcx> {
+    fn tag(&self) -> &'static str { "Lub" }
+
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> { self.fields.tcx() }
+
+    fn a_is_expected(&self) -> bool { self.fields.a_is_expected }
 
-    fn tys_with_variance(&self, v: ty::Variance, a: Ty<'tcx>, b: Ty<'tcx>)
-                         -> CombineResult<'tcx, Ty<'tcx>>
+    fn relate_with_variance<T:Relate<'a,'tcx>>(&mut self,
+                                               variance: ty::Variance,
+                                               a: &T,
+                                               b: &T)
+                                               -> RelateResult<'tcx, T>
     {
-        match v {
-            ty::Invariant => self.equate().tys(a, b),
-            ty::Covariant => self.tys(a, b),
-            ty::Bivariant => self.bivariate().tys(a, b),
-            ty::Contravariant => self.glb().tys(a, b),
+        match variance {
+            ty::Invariant => self.fields.equate().relate(a, b),
+            ty::Covariant => self.relate(a, b),
+            ty::Bivariant => self.fields.bivariate().relate(a, b),
+            ty::Contravariant => self.fields.glb().relate(a, b),
         }
     }
 
-    fn regions_with_variance(&self, v: ty::Variance, a: ty::Region, b: ty::Region)
-                             -> CombineResult<'tcx, ty::Region>
-    {
-        match v {
-            ty::Invariant => self.equate().regions(a, b),
-            ty::Covariant => self.regions(a, b),
-            ty::Bivariant => self.bivariate().regions(a, b),
-            ty::Contravariant => self.glb().regions(a, b),
-        }
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        lattice::super_lattice_tys(self, a, b)
     }
 
-    fn regions(&self, a: ty::Region, b: ty::Region) -> CombineResult<'tcx, ty::Region> {
+    fn regions(&mut self, a: ty::Region, b: ty::Region) -> RelateResult<'tcx, ty::Region> {
         debug!("{}.regions({}, {})",
                self.tag(),
                a.repr(self.tcx()),
                b.repr(self.tcx()));
 
-        Ok(self.infcx().region_vars.lub_regions(Subtype(self.trace()), a, b))
+        let origin = Subtype(self.fields.trace.clone());
+        Ok(self.fields.infcx.region_vars.lub_regions(origin, a, b))
     }
 
-    fn tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, Ty<'tcx>> {
-        super_lattice_tys(self, a, b)
+    fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
+                  -> RelateResult<'tcx, ty::Binder<T>>
+        where T: Relate<'a, 'tcx>
+    {
+        self.fields.higher_ranked_lub(a, b)
     }
+}
 
-    fn binders<T>(&self, a: &ty::Binder<T>, b: &ty::Binder<T>) -> CombineResult<'tcx, ty::Binder<T>>
-        where T : Combineable<'tcx>
-    {
-        self.higher_ranked_lub(a, b)
+impl<'a, 'tcx> LatticeDir<'a,'tcx> for Lub<'a, 'tcx> {
+    fn infcx(&self) -> &'a InferCtxt<'a,'tcx> {
+        self.fields.infcx
+    }
+
+    fn relate_bound(&self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()> {
+        let mut sub = self.fields.sub();
+        try!(sub.relate(&a, &v));
+        try!(sub.relate(&b, &v));
+        Ok(())
     }
 }
+
diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index 7e9c4d8e076..da811c35457 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -28,7 +28,8 @@ use middle::ty::{TyVid, IntVid, FloatVid, RegionVid, UnconstrainedNumeric};
 use middle::ty::replace_late_bound_regions;
 use middle::ty::{self, Ty};
 use middle::ty_fold::{TypeFolder, TypeFoldable};
-use std::cell::RefCell;
+use middle::ty_relate::{Relate, RelateResult, TypeRelation};
+use std::cell::{RefCell};
 use std::fmt;
 use std::rc::Rc;
 use syntax::ast;
@@ -38,11 +39,8 @@ use util::nodemap::FnvHashMap;
 use util::ppaux::ty_to_string;
 use util::ppaux::{Repr, UserString};
 
-use self::combine::{Combine, Combineable, CombineFields};
+use self::combine::CombineFields;
 use self::region_inference::{RegionVarBindings, RegionSnapshot};
-use self::equate::Equate;
-use self::sub::Sub;
-use self::lub::Lub;
 use self::unify::{ToType, UnificationTable};
 use self::error_reporting::ErrorReporting;
 
@@ -62,9 +60,7 @@ pub mod type_variable;
 pub mod unify;
 
 pub type Bound<T> = Option<T>;
-
-pub type CombineResult<'tcx, T> = Result<T,ty::type_err<'tcx>>; // "combine result"
-pub type UnitResult<'tcx> = CombineResult<'tcx, ()>; // "unify result"
+pub type UnitResult<'tcx> = RelateResult<'tcx, ()>; // "unify result"
 pub type fres<T> = Result<T, fixup_err>; // "fixup result"
 
 pub struct InferCtxt<'a, 'tcx: 'a> {
@@ -343,7 +339,7 @@ pub fn common_supertype<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>,
         values: Types(expected_found(a_is_expected, a, b))
     };
 
-    let result = cx.commit_if_ok(|_| cx.lub(a_is_expected, trace.clone()).tys(a, b));
+    let result = cx.commit_if_ok(|_| cx.lub(a_is_expected, trace.clone()).relate(&a, &b));
     match result {
         Ok(t) => t,
         Err(ref err) => {
@@ -374,11 +370,12 @@ pub fn can_mk_subty<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>,
             origin: Misc(codemap::DUMMY_SP),
             values: Types(expected_found(true, a, b))
         };
-        cx.sub(true, trace).tys(a, b).map(|_| ())
+        cx.sub(true, trace).relate(&a, &b).map(|_| ())
     })
 }
 
-pub fn can_mk_eqty<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> UnitResult<'tcx>
+pub fn can_mk_eqty<'a, 'tcx>(cx: &InferCtxt<'a, 'tcx>, a: Ty<'tcx>, b: Ty<'tcx>)
+                             -> UnitResult<'tcx>
 {
     cx.can_equate(&a, &b)
 }
@@ -473,26 +470,39 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         }
     }
 
-    fn combine_fields<'b>(&'b self, a_is_expected: bool, trace: TypeTrace<'tcx>)
-                          -> CombineFields<'b, 'tcx> {
+    fn combine_fields(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
+                      -> CombineFields<'a, 'tcx> {
         CombineFields {infcx: self,
                        a_is_expected: a_is_expected,
                        trace: trace}
     }
 
-    fn equate<'b>(&'b self, a_is_expected: bool, trace: TypeTrace<'tcx>)
-                  -> Equate<'b, 'tcx> {
-        Equate(self.combine_fields(a_is_expected, trace))
+    // public so that it can be used from the rustc_driver unit tests
+    pub fn equate(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
+              -> equate::Equate<'a, 'tcx>
+    {
+        self.combine_fields(a_is_expected, trace).equate()
     }
 
-    fn sub<'b>(&'b self, a_is_expected: bool, trace: TypeTrace<'tcx>)
-               -> Sub<'b, 'tcx> {
-        Sub(self.combine_fields(a_is_expected, trace))
+    // public so that it can be used from the rustc_driver unit tests
+    pub fn sub(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
+               -> sub::Sub<'a, 'tcx>
+    {
+        self.combine_fields(a_is_expected, trace).sub()
     }
 
-    fn lub<'b>(&'b self, a_is_expected: bool, trace: TypeTrace<'tcx>)
-               -> Lub<'b, 'tcx> {
-        Lub(self.combine_fields(a_is_expected, trace))
+    // public so that it can be used from the rustc_driver unit tests
+    pub fn lub(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
+               -> lub::Lub<'a, 'tcx>
+    {
+        self.combine_fields(a_is_expected, trace).lub()
+    }
+
+    // public so that it can be used from the rustc_driver unit tests
+    pub fn glb(&'a self, a_is_expected: bool, trace: TypeTrace<'tcx>)
+               -> glb::Glb<'a, 'tcx>
+    {
+        self.combine_fields(a_is_expected, trace).glb()
     }
 
     fn start_snapshot(&self) -> CombinedSnapshot {
@@ -631,7 +641,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         debug!("sub_types({} <: {})", a.repr(self.tcx), b.repr(self.tcx));
         self.commit_if_ok(|_| {
             let trace = TypeTrace::types(origin, a_is_expected, a, b);
-            self.sub(a_is_expected, trace).tys(a, b).map(|_| ())
+            self.sub(a_is_expected, trace).relate(&a, &b).map(|_| ())
         })
     }
 
@@ -644,7 +654,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
     {
         self.commit_if_ok(|_| {
             let trace = TypeTrace::types(origin, a_is_expected, a, b);
-            self.equate(a_is_expected, trace).tys(a, b).map(|_| ())
+            self.equate(a_is_expected, trace).relate(&a, &b).map(|_| ())
         })
     }
 
@@ -663,7 +673,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                 origin: origin,
                 values: TraitRefs(expected_found(a_is_expected, a.clone(), b.clone()))
             };
-            self.sub(a_is_expected, trace).trait_refs(&*a, &*b).map(|_| ())
+            self.sub(a_is_expected, trace).relate(&*a, &*b).map(|_| ())
         })
     }
 
@@ -682,7 +692,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                 origin: origin,
                 values: PolyTraitRefs(expected_found(a_is_expected, a.clone(), b.clone()))
             };
-            self.sub(a_is_expected, trace).binders(&a, &b).map(|_| ())
+            self.sub(a_is_expected, trace).relate(&a, &b).map(|_| ())
         })
     }
 
@@ -1045,8 +1055,8 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         self.region_vars.verify_generic_bound(origin, kind, a, bs);
     }
 
-    pub fn can_equate<T>(&self, a: &T, b: &T) -> UnitResult<'tcx>
-        where T : Combineable<'tcx> + Repr<'tcx>
+    pub fn can_equate<'b,T>(&'b self, a: &T, b: &T) -> UnitResult<'tcx>
+        where T: Relate<'b,'tcx> + Repr<'tcx>
     {
         debug!("can_equate({}, {})", a.repr(self.tcx), b.repr(self.tcx));
         self.probe(|_| {
@@ -1057,8 +1067,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
             let e = self.tcx.types.err;
             let trace = TypeTrace { origin: Misc(codemap::DUMMY_SP),
                                     values: Types(expected_found(true, e, e)) };
-            let eq = self.equate(true, trace);
-            Combineable::combine(&eq, a, b)
+            self.equate(true, trace).relate(a, b)
         }).map(|_| ())
     }
 }
diff --git a/src/librustc/middle/infer/region_inference/mod.rs b/src/librustc/middle/infer/region_inference/mod.rs
index 1d15656fea2..45d4a8c5d9f 100644
--- a/src/librustc/middle/infer/region_inference/mod.rs
+++ b/src/librustc/middle/infer/region_inference/mod.rs
@@ -18,7 +18,6 @@ pub use self::RegionResolutionError::*;
 pub use self::VarValue::*;
 use self::Classification::*;
 
-use super::CombineResult;
 use super::{RegionVariableOrigin, SubregionOrigin, TypeTrace, MiscVariable};
 
 use middle::region;
@@ -26,6 +25,7 @@ use middle::ty::{self, Ty};
 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid};
 use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound};
 use middle::ty::{ReLateBound, ReScope, ReVar, ReSkolemized, BrFresh};
+use middle::ty_relate::RelateResult;
 use middle::graph;
 use middle::graph::{Direction, NodeIndex};
 use util::common::indenter;
@@ -825,7 +825,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     fn glb_concrete_regions(&self,
                             a: Region,
                             b: Region)
-                            -> CombineResult<'tcx, Region>
+                            -> RelateResult<'tcx, Region>
     {
         debug!("glb_concrete_regions({:?}, {:?})", a, b);
         match (a, b) {
@@ -901,7 +901,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     fn glb_free_regions(&self,
                         a: &FreeRegion,
                         b: &FreeRegion)
-                        -> CombineResult<'tcx, ty::Region>
+                        -> RelateResult<'tcx, ty::Region>
     {
         return match a.cmp(b) {
             Less => helper(self, a, b),
@@ -911,7 +911,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
 
         fn helper<'a, 'tcx>(this: &RegionVarBindings<'a, 'tcx>,
                             a: &FreeRegion,
-                            b: &FreeRegion) -> CombineResult<'tcx, ty::Region>
+                            b: &FreeRegion) -> RelateResult<'tcx, ty::Region>
         {
             if this.tcx.region_maps.sub_free_region(*a, *b) {
                 Ok(ty::ReFree(*a))
@@ -930,7 +930,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
                         region_b: ty::Region,
                         scope_a: region::CodeExtent,
                         scope_b: region::CodeExtent)
-                        -> CombineResult<'tcx, Region>
+                        -> RelateResult<'tcx, Region>
     {
         // We want to generate the intersection of two
         // scopes or two free regions.  So, if one of
diff --git a/src/librustc/middle/infer/sub.rs b/src/librustc/middle/infer/sub.rs
index d58a911e860..31b654a5b3f 100644
--- a/src/librustc/middle/infer/sub.rs
+++ b/src/librustc/middle/infer/sub.rs
@@ -8,64 +8,49 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use super::combine::*;
-use super::CombineResult;
+use super::combine::{self, CombineFields};
 use super::higher_ranked::HigherRankedRelations;
 use super::Subtype;
 use super::type_variable::{SubtypeOf, SupertypeOf};
 
 use middle::ty::{self, Ty};
 use middle::ty::TyVar;
-use util::ppaux::Repr;
+use middle::ty_relate::{Relate, RelateResult, TypeRelation};
+use util::ppaux::{Repr};
 
 /// "Greatest lower bound" (common subtype)
-pub struct Sub<'f, 'tcx: 'f> {
-    fields: CombineFields<'f, 'tcx>
+pub struct Sub<'a, 'tcx: 'a> {
+    fields: CombineFields<'a, 'tcx>
 }
 
-#[allow(non_snake_case)]
-pub fn Sub<'f, 'tcx>(cf: CombineFields<'f, 'tcx>) -> Sub<'f, 'tcx> {
-    Sub { fields: cf }
+impl<'a, 'tcx> Sub<'a, 'tcx> {
+    pub fn new(f: CombineFields<'a, 'tcx>) -> Sub<'a, 'tcx> {
+        Sub { fields: f }
+    }
 }
 
-impl<'f, 'tcx> Combine<'tcx> for Sub<'f, 'tcx> {
-    fn tag(&self) -> String { "Sub".to_string() }
-    fn fields<'a>(&'a self) -> &'a CombineFields<'a, 'tcx> { &self.fields }
-
-    fn tys_with_variance(&self, v: ty::Variance, a: Ty<'tcx>, b: Ty<'tcx>)
-                         -> CombineResult<'tcx, Ty<'tcx>>
-    {
-        match v {
-            ty::Invariant => self.equate().tys(a, b),
-            ty::Covariant => self.tys(a, b),
-            ty::Bivariant => self.bivariate().tys(a, b),
-            ty::Contravariant => Sub(self.fields.switch_expected()).tys(b, a),
-        }
-    }
+impl<'a, 'tcx> TypeRelation<'a, 'tcx> for Sub<'a, 'tcx> {
+    fn tag(&self) -> &'static str { "Sub" }
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> { self.fields.infcx.tcx }
+    fn a_is_expected(&self) -> bool { self.fields.a_is_expected }
 
-    fn regions_with_variance(&self, v: ty::Variance, a: ty::Region, b: ty::Region)
-                             -> CombineResult<'tcx, ty::Region>
+    fn relate_with_variance<T:Relate<'a,'tcx>>(&mut self,
+                                               variance: ty::Variance,
+                                               a: &T,
+                                               b: &T)
+                                               -> RelateResult<'tcx, T>
     {
-        match v {
-            ty::Invariant => self.equate().regions(a, b),
-            ty::Covariant => self.regions(a, b),
-            ty::Bivariant => self.bivariate().regions(a, b),
-            ty::Contravariant => Sub(self.fields.switch_expected()).regions(b, a),
+        match variance {
+            ty::Invariant => self.fields.equate().relate(a, b),
+            ty::Covariant => self.relate(a, b),
+            ty::Bivariant => self.fields.bivariate().relate(a, b),
+            ty::Contravariant => self.fields.switch_expected().sub().relate(b, a),
         }
     }
 
-    fn regions(&self, a: ty::Region, b: ty::Region) -> CombineResult<'tcx, ty::Region> {
-        debug!("{}.regions({}, {})",
-               self.tag(),
-               a.repr(self.tcx()),
-               b.repr(self.tcx()));
-        self.infcx().region_vars.make_subregion(Subtype(self.trace()), a, b);
-        Ok(a)
-    }
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        debug!("{}.tys({}, {})", self.tag(), a.repr(self.tcx()), b.repr(self.tcx()));
 
-    fn tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> CombineResult<'tcx, Ty<'tcx>> {
-        debug!("{}.tys({}, {})", self.tag(),
-               a.repr(self.tcx()), b.repr(self.tcx()));
         if a == b { return Ok(a); }
 
         let infcx = self.fields.infcx;
@@ -80,8 +65,8 @@ impl<'f, 'tcx> Combine<'tcx> for Sub<'f, 'tcx> {
             }
             (&ty::ty_infer(TyVar(a_id)), _) => {
                 try!(self.fields
-                       .switch_expected()
-                       .instantiate(b, SupertypeOf, a_id));
+                         .switch_expected()
+                         .instantiate(b, SupertypeOf, a_id));
                 Ok(a)
             }
             (_, &ty::ty_infer(TyVar(b_id))) => {
@@ -94,14 +79,25 @@ impl<'f, 'tcx> Combine<'tcx> for Sub<'f, 'tcx> {
             }
 
             _ => {
-                super_tys(self, a, b)
+                combine::super_combine_tys(self.fields.infcx, self, a, b)
             }
         }
     }
 
-    fn binders<T>(&self, a: &ty::Binder<T>, b: &ty::Binder<T>) -> CombineResult<'tcx, ty::Binder<T>>
-        where T : Combineable<'tcx>
+    fn regions(&mut self, a: ty::Region, b: ty::Region) -> RelateResult<'tcx, ty::Region> {
+        debug!("{}.regions({}, {})",
+               self.tag(),
+               a.repr(self.tcx()),
+               b.repr(self.tcx()));
+        let origin = Subtype(self.fields.trace.clone());
+        self.fields.infcx.region_vars.make_subregion(origin, a, b);
+        Ok(a)
+    }
+
+    fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
+                  -> RelateResult<'tcx, ty::Binder<T>>
+        where T: Relate<'a,'tcx>
     {
-        self.higher_ranked_sub(a, b)
+        self.fields.higher_ranked_sub(a, b)
     }
 }
diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs
index e27b910f6c2..7488b8f046e 100644
--- a/src/librustc/middle/traits/project.rs
+++ b/src/librustc/middle/traits/project.rs
@@ -291,6 +291,7 @@ impl<'a,'b,'tcx> TypeFolder<'tcx> for AssociatedTypeNormalizer<'a,'b,'tcx> {
     }
 }
 
+#[derive(Clone)]
 pub struct Normalized<'tcx,T> {
     pub value: T,
     pub obligations: Vec<PredicateObligation<'tcx>>,
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index f17ba78007b..5f77574f65e 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -39,6 +39,8 @@ use middle::subst::VecPerParamSpace;
 use middle::ty::{self, Ty};
 use middle::traits;
 use std::rc::Rc;
+use syntax::abi;
+use syntax::ast;
 use syntax::owned_slice::OwnedSlice;
 use util::ppaux::Repr;
 
@@ -47,7 +49,7 @@ use util::ppaux::Repr;
 
 /// The TypeFoldable trait is implemented for every type that can be folded.
 /// Basically, every type that has a corresponding method in TypeFolder.
-pub trait TypeFoldable<'tcx> {
+pub trait TypeFoldable<'tcx>: Repr<'tcx> + Clone {
     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self;
 }
 
@@ -149,12 +151,20 @@ pub trait TypeFolder<'tcx> : Sized {
 // can easily refactor the folding into the TypeFolder trait as
 // needed.
 
-impl<'tcx> TypeFoldable<'tcx> for () {
-    fn fold_with<F:TypeFolder<'tcx>>(&self, _: &mut F) -> () {
-        ()
+macro_rules! CopyImpls {
+    ($($ty:ty),+) => {
+        $(
+            impl<'tcx> TypeFoldable<'tcx> for $ty {
+                fn fold_with<F:TypeFolder<'tcx>>(&self, _: &mut F) -> $ty {
+                    *self
+                }
+            }
+        )+
     }
 }
 
+CopyImpls! { (), ast::Unsafety, abi::Abi }
+
 impl<'tcx, T:TypeFoldable<'tcx>, U:TypeFoldable<'tcx>> TypeFoldable<'tcx> for (T, U) {
     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> (T, U) {
         (self.0.fold_with(folder), self.1.fold_with(folder))
diff --git a/src/librustc/middle/ty_relate/mod.rs b/src/librustc/middle/ty_relate/mod.rs
new file mode 100644
index 00000000000..1205b7d9579
--- /dev/null
+++ b/src/librustc/middle/ty_relate/mod.rs
@@ -0,0 +1,655 @@
+// Copyright 2012-2013 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.
+
+//! Generalized type relating mechanism. A type relation R relates a
+//! pair of values (A, B). A and B are usually types or regions but
+//! can be other things. Examples of type relations are subtyping,
+//! type equality, etc.
+
+use middle::subst::{ErasedRegions, NonerasedRegions, ParamSpace, Substs};
+use middle::ty::{self, Ty};
+use middle::ty_fold::TypeFoldable;
+use std::rc::Rc;
+use syntax::abi;
+use syntax::ast;
+use util::ppaux::Repr;
+
+pub type RelateResult<'tcx, T> = Result<T, ty::type_err<'tcx>>;
+
+pub trait TypeRelation<'a,'tcx> : Sized {
+    fn tcx(&self) -> &'a ty::ctxt<'tcx>;
+
+    /// Returns a static string we can use for printouts.
+    fn tag(&self) -> &'static str;
+
+    /// Returns true if the value `a` is the "expected" type in the
+    /// relation. Just affects error messages.
+    fn a_is_expected(&self) -> bool;
+
+    /// Generic relation routine suitable for most anything.
+    fn relate<T:Relate<'a,'tcx>>(&mut self, a: &T, b: &T) -> RelateResult<'tcx, T> {
+        Relate::relate(self, a, b)
+    }
+
+    /// Switch variance for the purpose of relating `a` and `b`.
+    fn relate_with_variance<T:Relate<'a,'tcx>>(&mut self,
+                                               variance: ty::Variance,
+                                               a: &T,
+                                               b: &T)
+                                               -> RelateResult<'tcx, T>;
+
+    // Overrideable relations. You shouldn't typically call these
+    // directly, instead call `relate()`, which in turn calls
+    // these. This is both more uniform but also allows us to add
+    // additional hooks for other types in the future if needed
+    // without making older code, which called `relate`, obsolete.
+
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>)
+           -> RelateResult<'tcx, Ty<'tcx>>;
+
+    fn regions(&mut self, a: ty::Region, b: ty::Region)
+               -> RelateResult<'tcx, ty::Region>;
+
+    fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
+                  -> RelateResult<'tcx, ty::Binder<T>>
+        where T: Relate<'a,'tcx>;
+}
+
+pub trait Relate<'a,'tcx>: TypeFoldable<'tcx> {
+    fn relate<R:TypeRelation<'a,'tcx>>(relation: &mut R,
+                                       a: &Self,
+                                       b: &Self)
+                                       -> RelateResult<'tcx, Self>;
+}
+
+///////////////////////////////////////////////////////////////////////////
+// Relate impls
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::mt<'tcx> {
+    fn relate<R>(relation: &mut R,
+                 a: &ty::mt<'tcx>,
+                 b: &ty::mt<'tcx>)
+                 -> RelateResult<'tcx, ty::mt<'tcx>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        debug!("{}.mts({}, {})",
+               relation.tag(),
+               a.repr(relation.tcx()),
+               b.repr(relation.tcx()));
+        if a.mutbl != b.mutbl {
+            Err(ty::terr_mutability)
+        } else {
+            let mutbl = a.mutbl;
+            let variance = match mutbl {
+                ast::MutImmutable => ty::Covariant,
+                ast::MutMutable => ty::Invariant,
+            };
+            let ty = try!(relation.relate_with_variance(variance, &a.ty, &b.ty));
+            Ok(ty::mt {ty: ty, mutbl: mutbl})
+        }
+    }
+}
+
+// substitutions are not themselves relatable without more context,
+// but they is an important subroutine for things that ARE relatable,
+// like traits etc.
+fn relate_item_substs<'a,'tcx:'a,R>(relation: &mut R,
+                                    item_def_id: ast::DefId,
+                                    a_subst: &Substs<'tcx>,
+                                    b_subst: &Substs<'tcx>)
+                                    -> RelateResult<'tcx, Substs<'tcx>>
+    where R: TypeRelation<'a,'tcx>
+{
+    debug!("substs: item_def_id={} a_subst={} b_subst={}",
+           item_def_id.repr(relation.tcx()),
+           a_subst.repr(relation.tcx()),
+           b_subst.repr(relation.tcx()));
+
+    let variances;
+    let opt_variances = if relation.tcx().variance_computed.get() {
+        variances = ty::item_variances(relation.tcx(), item_def_id);
+        Some(&*variances)
+    } else {
+        None
+    };
+    relate_substs(relation, opt_variances, a_subst, b_subst)
+}
+
+fn relate_substs<'a,'tcx,R>(relation: &mut R,
+                            variances: Option<&ty::ItemVariances>,
+                            a_subst: &Substs<'tcx>,
+                            b_subst: &Substs<'tcx>)
+                            -> RelateResult<'tcx, Substs<'tcx>>
+    where R: TypeRelation<'a,'tcx>
+{
+    let mut substs = Substs::empty();
+
+    for &space in &ParamSpace::all() {
+        let a_tps = a_subst.types.get_slice(space);
+        let b_tps = b_subst.types.get_slice(space);
+        let t_variances = variances.map(|v| v.types.get_slice(space));
+        let tps = try!(relate_type_params(relation, t_variances, a_tps, b_tps));
+        substs.types.replace(space, tps);
+    }
+
+    match (&a_subst.regions, &b_subst.regions) {
+        (&ErasedRegions, _) | (_, &ErasedRegions) => {
+            substs.regions = ErasedRegions;
+        }
+
+        (&NonerasedRegions(ref a), &NonerasedRegions(ref b)) => {
+            for &space in &ParamSpace::all() {
+                let a_regions = a.get_slice(space);
+                let b_regions = b.get_slice(space);
+                let r_variances = variances.map(|v| v.regions.get_slice(space));
+                let regions = try!(relate_region_params(relation,
+                                                        r_variances,
+                                                        a_regions,
+                                                        b_regions));
+                substs.mut_regions().replace(space, regions);
+            }
+        }
+    }
+
+    Ok(substs)
+}
+
+fn relate_type_params<'a,'tcx,R>(relation: &mut R,
+                                 variances: Option<&[ty::Variance]>,
+                                 a_tys: &[Ty<'tcx>],
+                                 b_tys: &[Ty<'tcx>])
+                                 -> RelateResult<'tcx, Vec<Ty<'tcx>>>
+    where R: TypeRelation<'a,'tcx>
+{
+    if a_tys.len() != b_tys.len() {
+        return Err(ty::terr_ty_param_size(expected_found(relation,
+                                                         &a_tys.len(),
+                                                         &b_tys.len())));
+    }
+
+    (0 .. a_tys.len())
+        .map(|i| {
+            let a_ty = a_tys[i];
+            let b_ty = b_tys[i];
+            let v = variances.map_or(ty::Invariant, |v| v[i]);
+            relation.relate_with_variance(v, &a_ty, &b_ty)
+        })
+        .collect()
+}
+
+fn relate_region_params<'a,'tcx:'a,R>(relation: &mut R,
+                                      variances: Option<&[ty::Variance]>,
+                                      a_rs: &[ty::Region],
+                                      b_rs: &[ty::Region])
+                                      -> RelateResult<'tcx, Vec<ty::Region>>
+    where R: TypeRelation<'a,'tcx>
+{
+    let tcx = relation.tcx();
+    let num_region_params = a_rs.len();
+
+    debug!("relate_region_params(a_rs={}, \
+            b_rs={}, variances={})",
+           a_rs.repr(tcx),
+           b_rs.repr(tcx),
+           variances.repr(tcx));
+
+    assert_eq!(num_region_params,
+               variances.map_or(num_region_params,
+                                |v| v.len()));
+
+    assert_eq!(num_region_params, b_rs.len());
+
+    (0..a_rs.len())
+        .map(|i| {
+            let a_r = a_rs[i];
+            let b_r = b_rs[i];
+            let variance = variances.map_or(ty::Invariant, |v| v[i]);
+            relation.relate_with_variance(variance, &a_r, &b_r)
+        })
+        .collect()
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::BareFnTy<'tcx> {
+    fn relate<R>(relation: &mut R,
+                 a: &ty::BareFnTy<'tcx>,
+                 b: &ty::BareFnTy<'tcx>)
+                 -> RelateResult<'tcx, ty::BareFnTy<'tcx>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        let unsafety = try!(relation.relate(&a.unsafety, &b.unsafety));
+        let abi = try!(relation.relate(&a.abi, &b.abi));
+        let sig = try!(relation.relate(&a.sig, &b.sig));
+        Ok(ty::BareFnTy {unsafety: unsafety,
+                         abi: abi,
+                         sig: sig})
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::FnSig<'tcx> {
+    fn relate<R>(relation: &mut R,
+                 a: &ty::FnSig<'tcx>,
+                 b: &ty::FnSig<'tcx>)
+                 -> RelateResult<'tcx, ty::FnSig<'tcx>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        if a.variadic != b.variadic {
+            return Err(ty::terr_variadic_mismatch(
+                expected_found(relation, &a.variadic, &b.variadic)));
+        }
+
+        let inputs = try!(relate_arg_vecs(relation,
+                                          &a.inputs,
+                                          &b.inputs));
+
+        let output = try!(match (a.output, b.output) {
+            (ty::FnConverging(a_ty), ty::FnConverging(b_ty)) =>
+                Ok(ty::FnConverging(try!(relation.relate(&a_ty, &b_ty)))),
+            (ty::FnDiverging, ty::FnDiverging) =>
+                Ok(ty::FnDiverging),
+            (a, b) =>
+                Err(ty::terr_convergence_mismatch(
+                    expected_found(relation, &(a != ty::FnDiverging), &(b != ty::FnDiverging)))),
+        });
+
+        return Ok(ty::FnSig {inputs: inputs,
+                             output: output,
+                             variadic: a.variadic});
+    }
+}
+
+fn relate_arg_vecs<'a,'tcx,R>(relation: &mut R,
+                              a_args: &[Ty<'tcx>],
+                              b_args: &[Ty<'tcx>])
+                              -> RelateResult<'tcx, Vec<Ty<'tcx>>>
+    where R: TypeRelation<'a,'tcx>
+{
+    if a_args.len() != b_args.len() {
+        return Err(ty::terr_arg_count);
+    }
+
+    a_args.iter()
+          .zip(b_args.iter())
+          .map(|(a, b)| relation.relate_with_variance(ty::Contravariant, a, b))
+          .collect()
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ast::Unsafety {
+    fn relate<R>(relation: &mut R,
+                 a: &ast::Unsafety,
+                 b: &ast::Unsafety)
+                 -> RelateResult<'tcx, ast::Unsafety>
+        where R: TypeRelation<'a,'tcx>
+    {
+        if a != b {
+            Err(ty::terr_unsafety_mismatch(expected_found(relation, a, b)))
+        } else {
+            Ok(*a)
+        }
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for abi::Abi {
+    fn relate<R>(relation: &mut R,
+                 a: &abi::Abi,
+                 b: &abi::Abi)
+                 -> RelateResult<'tcx, abi::Abi>
+        where R: TypeRelation<'a,'tcx>
+    {
+        if a == b {
+            Ok(*a)
+        } else {
+            Err(ty::terr_abi_mismatch(expected_found(relation, a, b)))
+        }
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ProjectionTy<'tcx> {
+    fn relate<R>(relation: &mut R,
+                 a: &ty::ProjectionTy<'tcx>,
+                 b: &ty::ProjectionTy<'tcx>)
+                 -> RelateResult<'tcx, ty::ProjectionTy<'tcx>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        if a.item_name != b.item_name {
+            Err(ty::terr_projection_name_mismatched(
+                expected_found(relation, &a.item_name, &b.item_name)))
+        } else {
+            let trait_ref = try!(relation.relate(&*a.trait_ref, &*b.trait_ref));
+            Ok(ty::ProjectionTy { trait_ref: Rc::new(trait_ref), item_name: a.item_name })
+        }
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ProjectionPredicate<'tcx> {
+    fn relate<R>(relation: &mut R,
+                 a: &ty::ProjectionPredicate<'tcx>,
+                 b: &ty::ProjectionPredicate<'tcx>)
+                 -> RelateResult<'tcx, ty::ProjectionPredicate<'tcx>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        let projection_ty = try!(relation.relate(&a.projection_ty, &b.projection_ty));
+        let ty = try!(relation.relate(&a.ty, &b.ty));
+        Ok(ty::ProjectionPredicate { projection_ty: projection_ty, ty: ty })
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for Vec<ty::PolyProjectionPredicate<'tcx>> {
+    fn relate<R>(relation: &mut R,
+                 a: &Vec<ty::PolyProjectionPredicate<'tcx>>,
+                 b: &Vec<ty::PolyProjectionPredicate<'tcx>>)
+                 -> RelateResult<'tcx, Vec<ty::PolyProjectionPredicate<'tcx>>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        // To be compatible, `a` and `b` must be for precisely the
+        // same set of traits and item names. We always require that
+        // projection bounds lists are sorted by trait-def-id and item-name,
+        // so we can just iterate through the lists pairwise, so long as they are the
+        // same length.
+        if a.len() != b.len() {
+            Err(ty::terr_projection_bounds_length(expected_found(relation, &a.len(), &b.len())))
+        } else {
+            a.iter()
+                .zip(b.iter())
+                .map(|(a, b)| relation.relate(a, b))
+                .collect()
+        }
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ExistentialBounds<'tcx> {
+    fn relate<R>(relation: &mut R,
+                 a: &ty::ExistentialBounds<'tcx>,
+                 b: &ty::ExistentialBounds<'tcx>)
+                 -> RelateResult<'tcx, ty::ExistentialBounds<'tcx>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        let r = try!(relation.relate_with_variance(ty::Contravariant,
+                                                   &a.region_bound,
+                                                   &b.region_bound));
+        let nb = try!(relation.relate(&a.builtin_bounds, &b.builtin_bounds));
+        let pb = try!(relation.relate(&a.projection_bounds, &b.projection_bounds));
+        Ok(ty::ExistentialBounds { region_bound: r,
+                                   builtin_bounds: nb,
+                                   projection_bounds: pb })
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::BuiltinBounds {
+    fn relate<R>(relation: &mut R,
+                 a: &ty::BuiltinBounds,
+                 b: &ty::BuiltinBounds)
+                 -> RelateResult<'tcx, ty::BuiltinBounds>
+        where R: TypeRelation<'a,'tcx>
+    {
+        // Two sets of builtin bounds are only relatable if they are
+        // precisely the same (but see the coercion code).
+        if a != b {
+            Err(ty::terr_builtin_bounds(expected_found(relation, a, b)))
+        } else {
+            Ok(*a)
+        }
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::TraitRef<'tcx> {
+    fn relate<R>(relation: &mut R,
+                 a: &ty::TraitRef<'tcx>,
+                 b: &ty::TraitRef<'tcx>)
+                 -> RelateResult<'tcx, ty::TraitRef<'tcx>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        // Different traits cannot be related
+        if a.def_id != b.def_id {
+            Err(ty::terr_traits(expected_found(relation, &a.def_id, &b.def_id)))
+        } else {
+            let substs = try!(relate_item_substs(relation, a.def_id, a.substs, b.substs));
+            Ok(ty::TraitRef { def_id: a.def_id, substs: relation.tcx().mk_substs(substs) })
+        }
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for Ty<'tcx> {
+    fn relate<R>(relation: &mut R,
+                 a: &Ty<'tcx>,
+                 b: &Ty<'tcx>)
+                 -> RelateResult<'tcx, Ty<'tcx>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        relation.tys(a, b)
+    }
+}
+
+/// The main "type relation" routine. Note that this does not handle
+/// inference artifacts, so you should filter those out before calling
+/// it.
+pub fn super_relate_tys<'a,'tcx:'a,R>(relation: &mut R,
+                                      a: Ty<'tcx>,
+                                      b: Ty<'tcx>)
+                                      -> RelateResult<'tcx, Ty<'tcx>>
+    where R: TypeRelation<'a,'tcx>
+{
+    let tcx = relation.tcx();
+    let a_sty = &a.sty;
+    let b_sty = &b.sty;
+    debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
+    match (a_sty, b_sty) {
+        (&ty::ty_infer(_), _) |
+        (_, &ty::ty_infer(_)) =>
+        {
+            // The caller should handle these cases!
+            tcx.sess.bug("var types encountered in super_relate_tys")
+        }
+
+        (&ty::ty_err, _) | (_, &ty::ty_err) =>
+        {
+            Ok(tcx.types.err)
+        }
+
+        (&ty::ty_char, _) |
+        (&ty::ty_bool, _) |
+        (&ty::ty_int(_), _) |
+        (&ty::ty_uint(_), _) |
+        (&ty::ty_float(_), _) |
+        (&ty::ty_str, _)
+            if a == b =>
+        {
+            Ok(a)
+        }
+
+        (&ty::ty_param(ref a_p), &ty::ty_param(ref b_p))
+            if a_p.idx == b_p.idx && a_p.space == b_p.space =>
+        {
+            Ok(a)
+        }
+
+        (&ty::ty_enum(a_id, a_substs), &ty::ty_enum(b_id, b_substs))
+            if a_id == b_id =>
+        {
+            let substs = try!(relate_item_substs(relation, a_id, a_substs, b_substs));
+            Ok(ty::mk_enum(tcx, a_id, tcx.mk_substs(substs)))
+        }
+
+        (&ty::ty_trait(ref a_), &ty::ty_trait(ref b_)) =>
+        {
+            let principal = try!(relation.relate(&a_.principal, &b_.principal));
+            let bounds = try!(relation.relate(&a_.bounds, &b_.bounds));
+            Ok(ty::mk_trait(tcx, principal, bounds))
+        }
+
+        (&ty::ty_struct(a_id, a_substs), &ty::ty_struct(b_id, b_substs))
+            if a_id == b_id =>
+        {
+            let substs = try!(relate_item_substs(relation, a_id, a_substs, b_substs));
+            Ok(ty::mk_struct(tcx, a_id, tcx.mk_substs(substs)))
+        }
+
+        (&ty::ty_closure(a_id, a_substs),
+         &ty::ty_closure(b_id, b_substs))
+            if a_id == b_id =>
+        {
+            // All ty_closure types with the same id represent
+            // the (anonymous) type of the same closure expression. So
+            // all of their regions should be equated.
+            let substs = try!(relate_substs(relation, None, a_substs, b_substs));
+            Ok(ty::mk_closure(tcx, a_id, tcx.mk_substs(substs)))
+        }
+
+        (&ty::ty_uniq(a_inner), &ty::ty_uniq(b_inner)) =>
+        {
+            let typ = try!(relation.relate(&a_inner, &b_inner));
+            Ok(ty::mk_uniq(tcx, typ))
+        }
+
+        (&ty::ty_ptr(ref a_mt), &ty::ty_ptr(ref b_mt)) =>
+        {
+            let mt = try!(relation.relate(a_mt, b_mt));
+            Ok(ty::mk_ptr(tcx, mt))
+        }
+
+        (&ty::ty_rptr(a_r, ref a_mt), &ty::ty_rptr(b_r, ref b_mt)) =>
+        {
+            let r = try!(relation.relate_with_variance(ty::Contravariant, a_r, b_r));
+            let mt = try!(relation.relate(a_mt, b_mt));
+            Ok(ty::mk_rptr(tcx, tcx.mk_region(r), mt))
+        }
+
+        (&ty::ty_vec(a_t, Some(sz_a)), &ty::ty_vec(b_t, Some(sz_b))) =>
+        {
+            let t = try!(relation.relate(&a_t, &b_t));
+            if sz_a == sz_b {
+                Ok(ty::mk_vec(tcx, t, Some(sz_a)))
+            } else {
+                Err(ty::terr_fixed_array_size(expected_found(relation, &sz_a, &sz_b)))
+            }
+        }
+
+        (&ty::ty_vec(a_t, None), &ty::ty_vec(b_t, None)) =>
+        {
+            let t = try!(relation.relate(&a_t, &b_t));
+            Ok(ty::mk_vec(tcx, t, None))
+        }
+
+        (&ty::ty_tup(ref as_), &ty::ty_tup(ref bs)) =>
+        {
+            if as_.len() == bs.len() {
+                let ts = try!(as_.iter()
+                                 .zip(bs.iter())
+                                 .map(|(a, b)| relation.relate(a, b))
+                                 .collect::<Result<_, _>>());
+                Ok(ty::mk_tup(tcx, ts))
+            } else if as_.len() != 0 && bs.len() != 0 {
+                Err(ty::terr_tuple_size(
+                    expected_found(relation, &as_.len(), &bs.len())))
+            } else {
+                Err(ty::terr_sorts(expected_found(relation, &a, &b)))
+            }
+        }
+
+        (&ty::ty_bare_fn(a_opt_def_id, a_fty), &ty::ty_bare_fn(b_opt_def_id, b_fty))
+            if a_opt_def_id == b_opt_def_id =>
+        {
+            let fty = try!(relation.relate(a_fty, b_fty));
+            Ok(ty::mk_bare_fn(tcx, a_opt_def_id, tcx.mk_bare_fn(fty)))
+        }
+
+        (&ty::ty_projection(ref a_data), &ty::ty_projection(ref b_data)) =>
+        {
+            let projection_ty = try!(relation.relate(a_data, b_data));
+            Ok(ty::mk_projection(tcx, projection_ty.trait_ref, projection_ty.item_name))
+        }
+
+        _ =>
+        {
+            Err(ty::terr_sorts(expected_found(relation, &a, &b)))
+        }
+    }
+}
+
+impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::Region {
+    fn relate<R>(relation: &mut R,
+                 a: &ty::Region,
+                 b: &ty::Region)
+                 -> RelateResult<'tcx, ty::Region>
+        where R: TypeRelation<'a,'tcx>
+    {
+        relation.regions(*a, *b)
+    }
+}
+
+impl<'a,'tcx:'a,T> Relate<'a,'tcx> for ty::Binder<T>
+    where T: Relate<'a,'tcx>
+{
+    fn relate<R>(relation: &mut R,
+                 a: &ty::Binder<T>,
+                 b: &ty::Binder<T>)
+                 -> RelateResult<'tcx, ty::Binder<T>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        relation.binders(a, b)
+    }
+}
+
+impl<'a,'tcx:'a,T> Relate<'a,'tcx> for Rc<T>
+    where T: Relate<'a,'tcx>
+{
+    fn relate<R>(relation: &mut R,
+                 a: &Rc<T>,
+                 b: &Rc<T>)
+                 -> RelateResult<'tcx, Rc<T>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        let a: &T = a;
+        let b: &T = b;
+        Ok(Rc::new(try!(relation.relate(a, b))))
+    }
+}
+
+impl<'a,'tcx:'a,T> Relate<'a,'tcx> for Box<T>
+    where T: Relate<'a,'tcx>
+{
+    fn relate<R>(relation: &mut R,
+                 a: &Box<T>,
+                 b: &Box<T>)
+                 -> RelateResult<'tcx, Box<T>>
+        where R: TypeRelation<'a,'tcx>
+    {
+        let a: &T = a;
+        let b: &T = b;
+        Ok(Box::new(try!(relation.relate(a, b))))
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
+// Error handling
+
+pub fn expected_found<'a,'tcx,R,T>(relation: &mut R,
+                                   a: &T,
+                                   b: &T)
+                                   -> ty::expected_found<T>
+    where R: TypeRelation<'a,'tcx>, T: Clone
+{
+    expected_found_bool(relation.a_is_expected(), a, b)
+}
+
+pub fn expected_found_bool<T>(a_is_expected: bool,
+                              a: &T,
+                              b: &T)
+                              -> ty::expected_found<T>
+    where T: Clone
+{
+    let a = a.clone();
+    let b = b.clone();
+    if a_is_expected {
+        ty::expected_found {expected: a, found: b}
+    } else {
+        ty::expected_found {expected: b, found: a}
+    }
+}
+
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 452589a2407..91c320237d5 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -1532,3 +1532,9 @@ impl<'tcx> UserString<'tcx> for ty::Predicate<'tcx> {
         }
     }
 }
+
+impl<'tcx> Repr<'tcx> for ast::Unsafety {
+    fn repr(&self, _: &ctxt<'tcx>) -> String {
+        format!("{:?}", *self)
+    }
+}
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index fcb0b9bdd3c..ac444478fcf 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -22,7 +22,7 @@ use rustc_typeck::middle::stability;
 use rustc_typeck::middle::subst;
 use rustc_typeck::middle::subst::Subst;
 use rustc_typeck::middle::ty::{self, Ty};
-use rustc_typeck::middle::infer::combine::Combine;
+use rustc_typeck::middle::ty_relate::TypeRelation;
 use rustc_typeck::middle::infer;
 use rustc_typeck::middle::infer::lub::Lub;
 use rustc_typeck::middle::infer::glb::Glb;
@@ -350,21 +350,21 @@ impl<'a, 'tcx> Env<'a, 'tcx> {
 
     pub fn sub(&self) -> Sub<'a, 'tcx> {
         let trace = self.dummy_type_trace();
-        Sub(self.infcx.combine_fields(true, trace))
+        self.infcx.sub(true, trace)
     }
 
     pub fn lub(&self) -> Lub<'a, 'tcx> {
         let trace = self.dummy_type_trace();
-        Lub(self.infcx.combine_fields(true, trace))
+        self.infcx.lub(true, trace)
     }
 
     pub fn glb(&self) -> Glb<'a, 'tcx> {
         let trace = self.dummy_type_trace();
-        Glb(self.infcx.combine_fields(true, trace))
+        self.infcx.glb(true, trace)
     }
 
     pub fn make_lub_ty(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) -> Ty<'tcx> {
-        match self.lub().tys(t1, t2) {
+        match self.lub().relate(&t1, &t2) {
             Ok(t) => t,
             Err(ref e) => panic!("unexpected error computing LUB: {}",
                                 ty::type_err_to_str(self.infcx.tcx, e))
@@ -374,7 +374,7 @@ impl<'a, 'tcx> Env<'a, 'tcx> {
     /// Checks that `t1 <: t2` is true (this may register additional
     /// region checks).
     pub fn check_sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) {
-        match self.sub().tys(t1, t2) {
+        match self.sub().relate(&t1, &t2) {
             Ok(_) => { }
             Err(ref e) => {
                 panic!("unexpected error computing sub({},{}): {}",
@@ -388,7 +388,7 @@ impl<'a, 'tcx> Env<'a, 'tcx> {
     /// Checks that `t1 <: t2` is false (this may register additional
     /// region checks).
     pub fn check_not_sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) {
-        match self.sub().tys(t1, t2) {
+        match self.sub().relate(&t1, &t2) {
             Err(_) => { }
             Ok(_) => {
                 panic!("unexpected success computing sub({},{})",
@@ -400,7 +400,7 @@ impl<'a, 'tcx> Env<'a, 'tcx> {
 
     /// Checks that `LUB(t1,t2) == t_lub`
     pub fn check_lub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>, t_lub: Ty<'tcx>) {
-        match self.lub().tys(t1, t2) {
+        match self.lub().relate(&t1, &t2) {
             Ok(t) => {
                 self.assert_eq(t, t_lub);
             }
@@ -417,7 +417,7 @@ impl<'a, 'tcx> Env<'a, 'tcx> {
                self.ty_to_string(t1),
                self.ty_to_string(t2),
                self.ty_to_string(t_glb));
-        match self.glb().tys(t1, t2) {
+        match self.glb().relate(&t1, &t2) {
             Err(e) => {
                 panic!("unexpected error computing LUB: {:?}", e)
             }
diff --git a/src/librustc_typeck/check/coercion.rs b/src/librustc_typeck/check/coercion.rs
index 1ba0194f84e..ced6cec3ef0 100644
--- a/src/librustc_typeck/check/coercion.rs
+++ b/src/librustc_typeck/check/coercion.rs
@@ -62,11 +62,11 @@
 
 use check::{autoderef, FnCtxt, NoPreference, PreferMutLvalue, UnresolvedTypeAction};
 
-use middle::infer::{self, CombineResult, Coercion};
-use middle::infer::combine::Combine;
+use middle::infer::{self, Coercion};
 use middle::subst;
 use middle::ty::{AutoPtr, AutoDerefRef, AdjustDerefRef, AutoUnsize, AutoUnsafe};
 use middle::ty::{self, mt, Ty};
+use middle::ty_relate::RelateResult;
 use util::common::indent;
 use util::ppaux;
 use util::ppaux::Repr;
@@ -78,7 +78,7 @@ struct Coerce<'a, 'tcx: 'a> {
     origin: infer::TypeOrigin,
 }
 
-type CoerceResult<'tcx> = CombineResult<'tcx, Option<ty::AutoAdjustment<'tcx>>>;
+type CoerceResult<'tcx> = RelateResult<'tcx, Option<ty::AutoAdjustment<'tcx>>>;
 
 impl<'f, 'tcx> Coerce<'f, 'tcx> {
     fn tcx(&self) -> &ty::ctxt<'tcx> {
@@ -536,7 +536,7 @@ pub fn mk_assignty<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
                              expr: &ast::Expr,
                              a: Ty<'tcx>,
                              b: Ty<'tcx>)
-                             -> CombineResult<'tcx, ()> {
+                             -> RelateResult<'tcx, ()> {
     debug!("mk_assignty({} -> {})", a.repr(fcx.tcx()), b.repr(fcx.tcx()));
     let adjustment = try!(indent(|| {
         fcx.infcx().commit_if_ok(|_| {
diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs
index eaf07a3ef13..51d0c18872d 100644
--- a/src/librustc_typeck/coherence/mod.rs
+++ b/src/librustc_typeck/coherence/mod.rs
@@ -30,7 +30,6 @@ use middle::ty::{ty_uint, ty_closure, ty_uniq, ty_bare_fn};
 use middle::ty::ty_projection;
 use middle::ty;
 use CrateCtxt;
-use middle::infer::combine::Combine;
 use middle::infer::InferCtxt;
 use middle::infer::new_infer_ctxt;
 use std::collections::HashSet;
diff --git a/src/test/compile-fail/dst-bad-coerce1.rs b/src/test/compile-fail/dst-bad-coerce1.rs
index ddc92901771..2d87345db22 100644
--- a/src/test/compile-fail/dst-bad-coerce1.rs
+++ b/src/test/compile-fail/dst-bad-coerce1.rs
@@ -23,10 +23,6 @@ pub fn main() {
     let f2: &Fat<[isize; 3]> = &f1;
     let f3: &Fat<[usize]> = f2;
     //~^ ERROR mismatched types
-    //~| expected `&Fat<[usize]>`
-    //~| found `&Fat<[isize; 3]>`
-    //~| expected usize
-    //~| found isize
 
     // With a trait.
     let f1 = Fat { ptr: Foo };