src/librustc/middle/infer/combine.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 ///////////////////////////////////////////////////////////////////////////
  12 // # Type combining
  13 //
  14 // There are four type combiners: equate, sub, lub, and glb.  Each
  15 // implements the trait `Combine` and contains methods for combining
  16 // two instances of various things and yielding a new instance.  These
  17 // combiner methods always yield a `Result<T>`.  There is a lot of
  18 // common code for these operations, implemented as default methods on
  19 // the `Combine` trait.
  20 //
  21 // Each operation may have side-effects on the inference context,
  22 // though these can be unrolled using snapshots. On success, the
  23 // LUB/GLB operations return the appropriate bound. The Eq and Sub
  24 // operations generally return the first operand.
  25 //
  26 // ## Contravariance
  27 //
  28 // When you are relating two things which have a contravariant
  29 // relationship, you should use `contratys()` or `contraregions()`,
  30 // rather than inversing the order of arguments!  This is necessary
  31 // because the order of arguments is not relevant for LUB and GLB.  It
  32 // is also useful to track which value is the "expected" value in
  33 // terms of error reporting.
  34
  35 use super::equate::Equate;
  36 use super::glb::Glb;
  37 use super::lub::Lub;
  38 use super::sub::Sub;
  39 use super::unify::InferCtxtMethodsForSimplyUnifiableTypes;
  40 use super::{InferCtxt, cres};
  41 use super::{MiscVariable, TypeTrace};
  42 use super::type_variable::{RelationDir, EqTo, SubtypeOf, SupertypeOf};
  43
  44 use middle::subst;
  45 use middle::subst::{ErasedRegions, NonerasedRegions, Substs};
  46 use middle::ty::{FloatVar, FnSig, IntVar, TyVar};
  47 use middle::ty::{IntType, UintType};
  48 use middle::ty::{BuiltinBounds};
  49 use middle::ty::{self, Ty};
  50 use middle::ty_fold;
  51 use middle::ty_fold::{TypeFoldable};
  52 use util::ppaux::Repr;
  53
  54 use std::rc::Rc;
  55 use syntax::ast::{Onceness, Unsafety};
  56 use syntax::ast;
  57 use syntax::abi;
  58 use syntax::codemap::Span;
  59
  60 pub trait Combine<'tcx> : Sized {
  61     fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx>;
  62     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.infcx().tcx }
  63     fn tag(&self) -> String;
  64     fn a_is_expected(&self) -> bool;
  65     fn trace(&self) -> TypeTrace<'tcx>;
  66
  67     fn equate<'a>(&'a self) -> Equate<'a, 'tcx>;
  68     fn sub<'a>(&'a self) -> Sub<'a, 'tcx>;
  69     fn lub<'a>(&'a self) -> Lub<'a, 'tcx>;
  70     fn glb<'a>(&'a self) -> Glb<'a, 'tcx>;
  71
  72     fn mts(&self, a: &ty::mt<'tcx>, b: &ty::mt<'tcx>) -> cres<'tcx, ty::mt<'tcx>>;
  73     fn contratys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> cres<'tcx, Ty<'tcx>>;
  74     fn tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> cres<'tcx, Ty<'tcx>>;
  75
  76     fn tps(&self,
  77            _: subst::ParamSpace,
  78            as_: &[Ty<'tcx>],
  79            bs: &[Ty<'tcx>])
  80            -> cres<'tcx, Vec<Ty<'tcx>>> {
  81         // FIXME -- In general, we treat variance a bit wrong
  82         // here. For historical reasons, we treat tps and Self
  83         // as invariant. This is overly conservative.
  84
  85         if as_.len() != bs.len() {
  86             return Err(ty::terr_ty_param_size(expected_found(self,
  87                                                              as_.len(),
  88                                                              bs.len())));
  89         }
  90
  91         try!(as_.iter().zip(bs.iter())
  92                 .map(|(a, b)| self.equate().tys(*a, *b))
  93                 .collect::<cres<Vec<Ty>>>());
  94         Ok(as_.to_vec())
  95     }
  96
  97     fn substs(&self,
  98               item_def_id: ast::DefId,
  99               a_subst: &subst::Substs<'tcx>,
 100               b_subst: &subst::Substs<'tcx>)
 101               -> cres<'tcx, subst::Substs<'tcx>>
 102     {
 103         let variances = if self.infcx().tcx.variance_computed.get() {
 104             Some(ty::item_variances(self.infcx().tcx, item_def_id))
 105         } else {
 106             None
 107         };
 108         self.substs_variances(variances.as_ref().map(|v| &**v), a_subst, b_subst)
 109     }
 110
 111     fn substs_variances(&self,
 112                         variances: Option<&ty::ItemVariances>,
 113                         a_subst: &subst::Substs<'tcx>,
 114                         b_subst: &subst::Substs<'tcx>)
 115                         -> cres<'tcx, subst::Substs<'tcx>>
 116     {
 117         let mut substs = subst::Substs::empty();
 118
 119         for &space in subst::ParamSpace::all().iter() {
 120             let a_tps = a_subst.types.get_slice(space);
 121             let b_tps = b_subst.types.get_slice(space);
 122             let tps = try!(self.tps(space, a_tps, b_tps));
 123             substs.types.replace(space, tps);
 124         }
 125
 126         match (&a_subst.regions, &b_subst.regions) {
 127             (&ErasedRegions, _) | (_, &ErasedRegions) => {
 128                 substs.regions = ErasedRegions;
 129             }
 130
 131             (&NonerasedRegions(ref a), &NonerasedRegions(ref b)) => {
 132                 for &space in subst::ParamSpace::all().iter() {
 133                     let a_regions = a.get_slice(space);
 134                     let b_regions = b.get_slice(space);
 135
 136                     let mut invariance = Vec::new();
 137                     let r_variances = match variances {
 138                         Some(variances) => {
 139                             variances.regions.get_slice(space)
 140                         }
 141                         None => {
 142                             for _ in a_regions.iter() {
 143                                 invariance.push(ty::Invariant);
 144                             }
 145                             &invariance[]
 146                         }
 147                     };
 148
 149                     let regions = try!(relate_region_params(self,
 150                                                             r_variances,
 151                                                             a_regions,
 152                                                             b_regions));
 153                     substs.mut_regions().replace(space, regions);
 154                 }
 155             }
 156         }
 157
 158         return Ok(substs);
 159
 160         fn relate_region_params<'tcx, C: Combine<'tcx>>(this: &C,
 161                                                         variances: &[ty::Variance],
 162                                                         a_rs: &[ty::Region],
 163                                                         b_rs: &[ty::Region])
 164                                                         -> cres<'tcx, Vec<ty::Region>> {
 165             let tcx = this.infcx().tcx;
 166             let num_region_params = variances.len();
 167
 168             debug!("relate_region_params(\
 169                    a_rs={}, \
 170                    b_rs={},
 171                    variances={})",
 172                    a_rs.repr(tcx),
 173                    b_rs.repr(tcx),
 174                    variances.repr(tcx));
 175
 176             assert_eq!(num_region_params, a_rs.len());
 177             assert_eq!(num_region_params, b_rs.len());
 178             let mut rs = vec!();
 179             for i in range(0, num_region_params) {
 180                 let a_r = a_rs[i];
 181                 let b_r = b_rs[i];
 182                 let variance = variances[i];
 183                 let r = match variance {
 184                     ty::Invariant => this.equate().regions(a_r, b_r),
 185                     ty::Covariant => this.regions(a_r, b_r),
 186                     ty::Contravariant => this.contraregions(a_r, b_r),
 187                     ty::Bivariant => Ok(a_r),
 188                 };
 189                 rs.push(try!(r));
 190             }
 191             Ok(rs)
 192         }
 193     }
 194
 195     fn bare_fn_tys(&self, a: &ty::BareFnTy<'tcx>,
 196                    b: &ty::BareFnTy<'tcx>) -> cres<'tcx, ty::BareFnTy<'tcx>> {
 197         let unsafety = try!(self.unsafeties(a.unsafety, b.unsafety));
 198         let abi = try!(self.abi(a.abi, b.abi));
 199         let sig = try!(self.binders(&a.sig, &b.sig));
 200         Ok(ty::BareFnTy {unsafety: unsafety,
 201                          abi: abi,
 202                          sig: sig})
 203     }
 204
 205     fn closure_tys(&self, a: &ty::ClosureTy<'tcx>,
 206                    b: &ty::ClosureTy<'tcx>) -> cres<'tcx, ty::ClosureTy<'tcx>> {
 207
 208         let store = match (a.store, b.store) {
 209             (ty::RegionTraitStore(a_r, a_m),
 210              ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => {
 211                 let r = try!(self.contraregions(a_r, b_r));
 212                 ty::RegionTraitStore(r, a_m)
 213             }
 214
 215             _ if a.store == b.store => {
 216                 a.store
 217             }
 218
 219             _ => {
 220                 return Err(ty::terr_sigil_mismatch(expected_found(self, a.store, b.store)))
 221             }
 222         };
 223         let unsafety = try!(self.unsafeties(a.unsafety, b.unsafety));
 224         let onceness = try!(self.oncenesses(a.onceness, b.onceness));
 225         let bounds = try!(self.existential_bounds(&a.bounds, &b.bounds));
 226         let sig = try!(self.binders(&a.sig, &b.sig));
 227         let abi = try!(self.abi(a.abi, b.abi));
 228         Ok(ty::ClosureTy {
 229             unsafety: unsafety,
 230             onceness: onceness,
 231             store: store,
 232             bounds: bounds,
 233             sig: sig,
 234             abi: abi,
 235         })
 236     }
 237
 238     fn fn_sigs(&self, a: &ty::FnSig<'tcx>, b: &ty::FnSig<'tcx>) -> cres<'tcx, ty::FnSig<'tcx>> {
 239         if a.variadic != b.variadic {
 240             return Err(ty::terr_variadic_mismatch(expected_found(self, a.variadic, b.variadic)));
 241         }
 242
 243         let inputs = try!(argvecs(self,
 244                                   a.inputs.as_slice(),
 245                                   b.inputs.as_slice()));
 246
 247         let output = try!(match (a.output, b.output) {
 248             (ty::FnConverging(a_ty), ty::FnConverging(b_ty)) =>
 249                 Ok(ty::FnConverging(try!(self.tys(a_ty, b_ty)))),
 250             (ty::FnDiverging, ty::FnDiverging) =>
 251                 Ok(ty::FnDiverging),
 252             (a, b) =>
 253                 Err(ty::terr_convergence_mismatch(
 254                     expected_found(self, a != ty::FnDiverging, b != ty::FnDiverging))),
 255         });
 256
 257         return Ok(ty::FnSig {inputs: inputs,
 258                              output: output,
 259                              variadic: a.variadic});
 260
 261
 262         fn argvecs<'tcx, C: Combine<'tcx>>(combiner: &C,
 263                                            a_args: &[Ty<'tcx>],
 264                                            b_args: &[Ty<'tcx>])
 265                                            -> cres<'tcx, Vec<Ty<'tcx>>>
 266         {
 267             if a_args.len() == b_args.len() {
 268                 a_args.iter().zip(b_args.iter())
 269                     .map(|(a, b)| combiner.args(*a, *b)).collect()
 270             } else {
 271                 Err(ty::terr_arg_count)
 272             }
 273         }
 274     }
 275
 276     fn args(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> cres<'tcx, Ty<'tcx>> {
 277         self.contratys(a, b).and_then(|t| Ok(t))
 278     }
 279
 280     fn unsafeties(&self, a: Unsafety, b: Unsafety) -> cres<'tcx, Unsafety>;
 281
 282     fn abi(&self, a: abi::Abi, b: abi::Abi) -> cres<'tcx, abi::Abi> {
 283         if a == b {
 284             Ok(a)
 285         } else {
 286             Err(ty::terr_abi_mismatch(expected_found(self, a, b)))
 287         }
 288     }
 289
 290     fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<'tcx, Onceness>;
 291
 292     fn projection_tys(&self,
 293                       a: &ty::ProjectionTy<'tcx>,
 294                       b: &ty::ProjectionTy<'tcx>)
 295                       -> cres<'tcx, ty::ProjectionTy<'tcx>>
 296     {
 297         if a.item_name != b.item_name {
 298             Err(ty::terr_projection_name_mismatched(
 299                 expected_found(self, a.item_name, b.item_name)))
 300         } else {
 301             let trait_ref = try!(self.trait_refs(&*a.trait_ref, &*b.trait_ref));
 302             Ok(ty::ProjectionTy { trait_ref: Rc::new(trait_ref), item_name: a.item_name })
 303         }
 304     }
 305
 306     fn projection_predicates(&self,
 307                              a: &ty::ProjectionPredicate<'tcx>,
 308                              b: &ty::ProjectionPredicate<'tcx>)
 309                              -> cres<'tcx, ty::ProjectionPredicate<'tcx>>
 310     {
 311         let projection_ty = try!(self.projection_tys(&a.projection_ty, &b.projection_ty));
 312         let ty = try!(self.tys(a.ty, b.ty));
 313         Ok(ty::ProjectionPredicate { projection_ty: projection_ty, ty: ty })
 314     }
 315
 316     fn projection_bounds(&self,
 317                          a: &Vec<ty::PolyProjectionPredicate<'tcx>>,
 318                          b: &Vec<ty::PolyProjectionPredicate<'tcx>>)
 319                          -> cres<'tcx, Vec<ty::PolyProjectionPredicate<'tcx>>>
 320     {
 321         // To be compatible, `a` and `b` must be for precisely the
 322         // same set of traits and item names. We always require that
 323         // projection bounds lists are sorted by trait-def-id and item-name,
 324         // so we can just iterate through the lists pairwise, so long as they are the
 325         // same length.
 326         if a.len() != b.len() {
 327             Err(ty::terr_projection_bounds_length(expected_found(self, a.len(), b.len())))
 328         } else {
 329             a.iter()
 330                 .zip(b.iter())
 331                 .map(|(a, b)| self.binders(a, b))
 332                 .collect()
 333         }
 334     }
 335
 336     fn existential_bounds(&self,
 337                           a: &ty::ExistentialBounds<'tcx>,
 338                           b: &ty::ExistentialBounds<'tcx>)
 339                           -> cres<'tcx, ty::ExistentialBounds<'tcx>>
 340     {
 341         let r = try!(self.contraregions(a.region_bound, b.region_bound));
 342         let nb = try!(self.builtin_bounds(a.builtin_bounds, b.builtin_bounds));
 343         let pb = try!(self.projection_bounds(&a.projection_bounds, &b.projection_bounds));
 344         Ok(ty::ExistentialBounds { region_bound: r,
 345                                    builtin_bounds: nb,
 346                                    projection_bounds: pb })
 347     }
 348
 349     fn builtin_bounds(&self,
 350                       a: ty::BuiltinBounds,
 351                       b: ty::BuiltinBounds)
 352                       -> cres<'tcx, ty::BuiltinBounds>;
 353
 354     fn contraregions(&self, a: ty::Region, b: ty::Region)
 355                   -> cres<'tcx, ty::Region>;
 356
 357     fn regions(&self, a: ty::Region, b: ty::Region) -> cres<'tcx, ty::Region>;
 358
 359     fn trait_stores(&self,
 360                     vk: ty::terr_vstore_kind,
 361                     a: ty::TraitStore,
 362                     b: ty::TraitStore)
 363                     -> cres<'tcx, ty::TraitStore> {
 364         debug!("{}.trait_stores(a={:?}, b={:?})", self.tag(), a, b);
 365
 366         match (a, b) {
 367             (ty::RegionTraitStore(a_r, a_m),
 368              ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => {
 369                 self.contraregions(a_r, b_r).and_then(|r| {
 370                     Ok(ty::RegionTraitStore(r, a_m))
 371                 })
 372             }
 373
 374             _ if a == b => {
 375                 Ok(a)
 376             }
 377
 378             _ => {
 379                 Err(ty::terr_trait_stores_differ(vk, expected_found(self, a, b)))
 380             }
 381         }
 382     }
 383
 384     fn trait_refs(&self,
 385                   a: &ty::TraitRef<'tcx>,
 386                   b: &ty::TraitRef<'tcx>)
 387                   -> cres<'tcx, ty::TraitRef<'tcx>>
 388     {
 389         // Different traits cannot be related
 390         if a.def_id != b.def_id {
 391             Err(ty::terr_traits(expected_found(self, a.def_id, b.def_id)))
 392         } else {
 393             let substs = try!(self.substs(a.def_id, a.substs, b.substs));
 394             Ok(ty::TraitRef { def_id: a.def_id, substs: self.tcx().mk_substs(substs) })
 395         }
 396     }
 397
 398     fn binders<T>(&self, a: &ty::Binder<T>, b: &ty::Binder<T>) -> cres<'tcx, ty::Binder<T>>
 399         where T : Combineable<'tcx>;
 400     // this must be overridden to do correctly, so as to account for higher-ranked
 401     // behavior
 402 }
 403
 404 pub trait Combineable<'tcx> : Repr<'tcx> + TypeFoldable<'tcx> {
 405     fn combine<C:Combine<'tcx>>(combiner: &C, a: &Self, b: &Self) -> cres<'tcx, Self>;
 406 }
 407
 408 impl<'tcx,T> Combineable<'tcx> for Rc<T>
 409     where T : Combineable<'tcx>
 410 {
 411     fn combine<C:Combine<'tcx>>(combiner: &C,
 412                                 a: &Rc<T>,
 413                                 b: &Rc<T>)
 414                                 -> cres<'tcx, Rc<T>>
 415     {
 416         Ok(Rc::new(try!(Combineable::combine(combiner, &**a, &**b))))
 417     }
 418 }
 419
 420 impl<'tcx> Combineable<'tcx> for ty::TraitRef<'tcx> {
 421     fn combine<C:Combine<'tcx>>(combiner: &C,
 422                                 a: &ty::TraitRef<'tcx>,
 423                                 b: &ty::TraitRef<'tcx>)
 424                                 -> cres<'tcx, ty::TraitRef<'tcx>>
 425     {
 426         combiner.trait_refs(a, b)
 427     }
 428 }
 429
 430 impl<'tcx> Combineable<'tcx> for Ty<'tcx> {
 431     fn combine<C:Combine<'tcx>>(combiner: &C,
 432                                 a: &Ty<'tcx>,
 433                                 b: &Ty<'tcx>)
 434                                 -> cres<'tcx, Ty<'tcx>>
 435     {
 436         combiner.tys(*a, *b)
 437     }
 438 }
 439
 440 impl<'tcx> Combineable<'tcx> for ty::ProjectionPredicate<'tcx> {
 441     fn combine<C:Combine<'tcx>>(combiner: &C,
 442                                 a: &ty::ProjectionPredicate<'tcx>,
 443                                 b: &ty::ProjectionPredicate<'tcx>)
 444                                 -> cres<'tcx, ty::ProjectionPredicate<'tcx>>
 445     {
 446         combiner.projection_predicates(a, b)
 447     }
 448 }
 449
 450 impl<'tcx> Combineable<'tcx> for ty::FnSig<'tcx> {
 451     fn combine<C:Combine<'tcx>>(combiner: &C,
 452                                 a: &ty::FnSig<'tcx>,
 453                                 b: &ty::FnSig<'tcx>)
 454                                 -> cres<'tcx, ty::FnSig<'tcx>>
 455     {
 456         combiner.fn_sigs(a, b)
 457     }
 458 }
 459
 460 #[derive(Clone)]
 461 pub struct CombineFields<'a, 'tcx: 'a> {
 462     pub infcx: &'a InferCtxt<'a, 'tcx>,
 463     pub a_is_expected: bool,
 464     pub trace: TypeTrace<'tcx>,
 465 }
 466
 467 pub fn expected_found<'tcx, C: Combine<'tcx>, T>(
 468         this: &C, a: T, b: T) -> ty::expected_found<T> {
 469     if this.a_is_expected() {
 470         ty::expected_found {expected: a, found: b}
 471     } else {
 472         ty::expected_found {expected: b, found: a}
 473     }
 474 }
 475
 476 pub fn super_tys<'tcx, C: Combine<'tcx>>(this: &C,
 477                                          a: Ty<'tcx>,
 478                                          b: Ty<'tcx>)
 479                                          -> cres<'tcx, Ty<'tcx>>
 480 {
 481     let tcx = this.infcx().tcx;
 482     let a_sty = &a.sty;
 483     let b_sty = &b.sty;
 484     debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
 485     return match (a_sty, b_sty) {
 486       // The "subtype" ought to be handling cases involving var:
 487       (&ty::ty_infer(TyVar(_)), _) |
 488       (_, &ty::ty_infer(TyVar(_))) => {
 489         tcx.sess.bug(
 490             &format!("{}: bot and var types should have been handled ({},{})",
 491                     this.tag(),
 492                     a.repr(this.infcx().tcx),
 493                     b.repr(this.infcx().tcx))[]);
 494       }
 495
 496       (&ty::ty_err, _) | (_, &ty::ty_err) => {
 497           Ok(tcx.types.err)
 498       }
 499
 500         // Relate integral variables to other types
 501         (&ty::ty_infer(IntVar(a_id)), &ty::ty_infer(IntVar(b_id))) => {
 502             try!(this.infcx().simple_vars(this.a_is_expected(),
 503                                             a_id, b_id));
 504             Ok(a)
 505         }
 506         (&ty::ty_infer(IntVar(v_id)), &ty::ty_int(v)) => {
 507             unify_integral_variable(this, this.a_is_expected(),
 508                                     v_id, IntType(v))
 509         }
 510         (&ty::ty_int(v), &ty::ty_infer(IntVar(v_id))) => {
 511             unify_integral_variable(this, !this.a_is_expected(),
 512                                     v_id, IntType(v))
 513         }
 514         (&ty::ty_infer(IntVar(v_id)), &ty::ty_uint(v)) => {
 515             unify_integral_variable(this, this.a_is_expected(),
 516                                     v_id, UintType(v))
 517         }
 518         (&ty::ty_uint(v), &ty::ty_infer(IntVar(v_id))) => {
 519             unify_integral_variable(this, !this.a_is_expected(),
 520                                     v_id, UintType(v))
 521         }
 522
 523         // Relate floating-point variables to other types
 524         (&ty::ty_infer(FloatVar(a_id)), &ty::ty_infer(FloatVar(b_id))) => {
 525             try!(this.infcx().simple_vars(this.a_is_expected(), a_id, b_id));
 526             Ok(a)
 527         }
 528         (&ty::ty_infer(FloatVar(v_id)), &ty::ty_float(v)) => {
 529             unify_float_variable(this, this.a_is_expected(), v_id, v)
 530         }
 531         (&ty::ty_float(v), &ty::ty_infer(FloatVar(v_id))) => {
 532             unify_float_variable(this, !this.a_is_expected(), v_id, v)
 533         }
 534
 535       (&ty::ty_char, _) |
 536       (&ty::ty_bool, _) |
 537       (&ty::ty_int(_), _) |
 538       (&ty::ty_uint(_), _) |
 539       (&ty::ty_float(_), _) => {
 540         if a == b {
 541             Ok(a)
 542         } else {
 543             Err(ty::terr_sorts(expected_found(this, a, b)))
 544         }
 545       }
 546
 547       (&ty::ty_param(ref a_p), &ty::ty_param(ref b_p)) if
 548           a_p.idx == b_p.idx && a_p.space == b_p.space => {
 549         Ok(a)
 550       }
 551
 552       (&ty::ty_enum(a_id, a_substs),
 553        &ty::ty_enum(b_id, b_substs))
 554       if a_id == b_id => {
 555           let substs = try!(this.substs(a_id,
 556                                           a_substs,
 557                                           b_substs));
 558           Ok(ty::mk_enum(tcx, a_id, tcx.mk_substs(substs)))
 559       }
 560
 561       (&ty::ty_trait(ref a_),
 562        &ty::ty_trait(ref b_)) => {
 563           debug!("Trying to match traits {:?} and {:?}", a, b);
 564           let principal = try!(this.binders(&a_.principal, &b_.principal));
 565           let bounds = try!(this.existential_bounds(&a_.bounds, &b_.bounds));
 566           Ok(ty::mk_trait(tcx, principal, bounds))
 567       }
 568
 569       (&ty::ty_struct(a_id, a_substs), &ty::ty_struct(b_id, b_substs))
 570       if a_id == b_id => {
 571             let substs = try!(this.substs(a_id, a_substs, b_substs));
 572             Ok(ty::mk_struct(tcx, a_id, tcx.mk_substs(substs)))
 573       }
 574
 575       (&ty::ty_unboxed_closure(a_id, a_region, a_substs),
 576        &ty::ty_unboxed_closure(b_id, b_region, b_substs))
 577       if a_id == b_id => {
 578           // All ty_unboxed_closure types with the same id represent
 579           // the (anonymous) type of the same closure expression. So
 580           // all of their regions should be equated.
 581           let region = try!(this.equate().regions(*a_region, *b_region));
 582           let substs = try!(this.substs_variances(None, a_substs, b_substs));
 583           Ok(ty::mk_unboxed_closure(tcx, a_id, tcx.mk_region(region), tcx.mk_substs(substs)))
 584       }
 585
 586       (&ty::ty_uniq(a_inner), &ty::ty_uniq(b_inner)) => {
 587           let typ = try!(this.tys(a_inner, b_inner));
 588           Ok(ty::mk_uniq(tcx, typ))
 589       }
 590
 591       (&ty::ty_ptr(ref a_mt), &ty::ty_ptr(ref b_mt)) => {
 592           let mt = try!(this.mts(a_mt, b_mt));
 593           Ok(ty::mk_ptr(tcx, mt))
 594       }
 595
 596       (&ty::ty_rptr(a_r, ref a_mt), &ty::ty_rptr(b_r, ref b_mt)) => {
 597             let r = try!(this.contraregions(*a_r, *b_r));
 598             // FIXME(14985)  If we have mutable references to trait objects, we
 599             // used to use covariant subtyping. I have preserved this behaviour,
 600             // even though it is probably incorrect. So don't go down the usual
 601             // path which would require invariance.
 602             let mt = match (&a_mt.ty.sty, &b_mt.ty.sty) {
 603                 (&ty::ty_trait(..), &ty::ty_trait(..)) if a_mt.mutbl == b_mt.mutbl => {
 604                     let ty = try!(this.tys(a_mt.ty, b_mt.ty));
 605                     ty::mt { ty: ty, mutbl: a_mt.mutbl }
 606                 }
 607                 _ => try!(this.mts(a_mt, b_mt))
 608             };
 609             Ok(ty::mk_rptr(tcx, tcx.mk_region(r), mt))
 610       }
 611
 612       (&ty::ty_vec(a_t, Some(sz_a)), &ty::ty_vec(b_t, Some(sz_b))) => {
 613         this.tys(a_t, b_t).and_then(|t| {
 614             if sz_a == sz_b {
 615                 Ok(ty::mk_vec(tcx, t, Some(sz_a)))
 616             } else {
 617                 Err(ty::terr_fixed_array_size(expected_found(this, sz_a, sz_b)))
 618             }
 619         })
 620       }
 621
 622       (&ty::ty_vec(a_t, sz_a), &ty::ty_vec(b_t, sz_b)) => {
 623         this.tys(a_t, b_t).and_then(|t| {
 624             if sz_a == sz_b {
 625                 Ok(ty::mk_vec(tcx, t, sz_a))
 626             } else {
 627                 Err(ty::terr_sorts(expected_found(this, a, b)))
 628             }
 629         })
 630       }
 631
 632       (&ty::ty_str, &ty::ty_str) => {
 633             Ok(ty::mk_str(tcx))
 634       }
 635
 636       (&ty::ty_tup(ref as_), &ty::ty_tup(ref bs)) => {
 637         if as_.len() == bs.len() {
 638             as_.iter().zip(bs.iter())
 639                .map(|(a, b)| this.tys(*a, *b))
 640                .collect::<Result<_, _>>()
 641                .map(|ts| ty::mk_tup(tcx, ts))
 642         } else if as_.len() != 0 && bs.len() != 0 {
 643             Err(ty::terr_tuple_size(
 644                 expected_found(this, as_.len(), bs.len())))
 645         } else {
 646             Err(ty::terr_sorts(expected_found(this, a, b)))
 647         }
 648       }
 649
 650         (&ty::ty_bare_fn(a_opt_def_id, a_fty), &ty::ty_bare_fn(b_opt_def_id, b_fty))
 651             if a_opt_def_id == b_opt_def_id =>
 652         {
 653             let fty = try!(this.bare_fn_tys(a_fty, b_fty));
 654             Ok(ty::mk_bare_fn(tcx, a_opt_def_id, tcx.mk_bare_fn(fty)))
 655         }
 656
 657       (&ty::ty_projection(ref a_data), &ty::ty_projection(ref b_data)) => {
 658           let projection_ty = try!(this.projection_tys(a_data, b_data));
 659           Ok(ty::mk_projection(tcx, projection_ty.trait_ref, projection_ty.item_name))
 660       }
 661
 662       _ => Err(ty::terr_sorts(expected_found(this, a, b)))
 663     };
 664
 665     fn unify_integral_variable<'tcx, C: Combine<'tcx>>(
 666         this: &C,
 667         vid_is_expected: bool,
 668         vid: ty::IntVid,
 669         val: ty::IntVarValue) -> cres<'tcx, Ty<'tcx>>
 670     {
 671         try!(this.infcx().simple_var_t(vid_is_expected, vid, val));
 672         match val {
 673             IntType(v) => Ok(ty::mk_mach_int(this.tcx(), v)),
 674             UintType(v) => Ok(ty::mk_mach_uint(this.tcx(), v))
 675         }
 676     }
 677
 678     fn unify_float_variable<'tcx, C: Combine<'tcx>>(
 679         this: &C,
 680         vid_is_expected: bool,
 681         vid: ty::FloatVid,
 682         val: ast::FloatTy) -> cres<'tcx, Ty<'tcx>>
 683     {
 684         try!(this.infcx().simple_var_t(vid_is_expected, vid, val));
 685         Ok(ty::mk_mach_float(this.tcx(), val))
 686     }
 687 }
 688
 689 impl<'f, 'tcx> CombineFields<'f, 'tcx> {
 690     pub fn switch_expected(&self) -> CombineFields<'f, 'tcx> {
 691         CombineFields {
 692             a_is_expected: !self.a_is_expected,
 693             ..(*self).clone()
 694         }
 695     }
 696
 697     fn equate(&self) -> Equate<'f, 'tcx> {
 698         Equate((*self).clone())
 699     }
 700
 701     fn sub(&self) -> Sub<'f, 'tcx> {
 702         Sub((*self).clone())
 703     }
 704
 705     pub fn instantiate(&self,
 706                        a_ty: Ty<'tcx>,
 707                        dir: RelationDir,
 708                        b_vid: ty::TyVid)
 709                        -> cres<'tcx, ()>
 710     {
 711         let tcx = self.infcx.tcx;
 712         let mut stack = Vec::new();
 713         stack.push((a_ty, dir, b_vid));
 714         loop {
 715             // For each turn of the loop, we extract a tuple
 716             //
 717             //     (a_ty, dir, b_vid)
 718             //
 719             // to relate. Here dir is either SubtypeOf or
 720             // SupertypeOf. The idea is that we should ensure that
 721             // the type `a_ty` is a subtype or supertype (respectively) of the
 722             // type to which `b_vid` is bound.
 723             //
 724             // If `b_vid` has not yet been instantiated with a type
 725             // (which is always true on the first iteration, but not
 726             // necessarily true on later iterations), we will first
 727             // instantiate `b_vid` with a *generalized* version of
 728             // `a_ty`. Generalization introduces other inference
 729             // variables wherever subtyping could occur (at time of
 730             // this writing, this means replacing free regions with
 731             // region variables).
 732             let (a_ty, dir, b_vid) = match stack.pop() {
 733                 None => break,
 734                 Some(e) => e,
 735             };
 736
 737             debug!("instantiate(a_ty={} dir={:?} b_vid={})",
 738                    a_ty.repr(tcx),
 739                    dir,
 740                    b_vid.repr(tcx));
 741
 742             // Check whether `vid` has been instantiated yet.  If not,
 743             // make a generalized form of `ty` and instantiate with
 744             // that.
 745             let b_ty = self.infcx.type_variables.borrow().probe(b_vid);
 746             let b_ty = match b_ty {
 747                 Some(t) => t, // ...already instantiated.
 748                 None => {     // ...not yet instantiated:
 749                     // Generalize type if necessary.
 750                     let generalized_ty = try!(match dir {
 751                         EqTo => {
 752                             self.generalize(a_ty, b_vid, false)
 753                         }
 754                         SupertypeOf | SubtypeOf => {
 755                             self.generalize(a_ty, b_vid, true)
 756                         }
 757                     });
 758                     debug!("instantiate(a_ty={}, dir={:?}, \
 759                                         b_vid={}, generalized_ty={})",
 760                            a_ty.repr(tcx), dir, b_vid.repr(tcx),
 761                            generalized_ty.repr(tcx));
 762                     self.infcx.type_variables
 763                         .borrow_mut()
 764                         .instantiate_and_push(
 765                             b_vid, generalized_ty, &mut stack);
 766                     generalized_ty
 767                 }
 768             };
 769
 770             // The original triple was `(a_ty, dir, b_vid)` -- now we have
 771             // resolved `b_vid` to `b_ty`, so apply `(a_ty, dir, b_ty)`:
 772             //
 773             // FIXME(#16847): This code is non-ideal because all these subtype
 774             // relations wind up attributed to the same spans. We need
 775             // to associate causes/spans with each of the relations in
 776             // the stack to get this right.
 777             match dir {
 778                 EqTo => {
 779                     try!(self.equate().tys(a_ty, b_ty));
 780                 }
 781
 782                 SubtypeOf => {
 783                     try!(self.sub().tys(a_ty, b_ty));
 784                 }
 785
 786                 SupertypeOf => {
 787                     try!(self.sub().contratys(a_ty, b_ty));
 788                 }
 789             }
 790         }
 791
 792         Ok(())
 793     }
 794
 795     /// Attempts to generalize `ty` for the type variable `for_vid`.  This checks for cycle -- that
 796     /// is, whether the type `ty` references `for_vid`. If `make_region_vars` is true, it will also
 797     /// replace all regions with fresh variables. Returns `ty_err` in the case of a cycle, `Ok`
 798     /// otherwise.
 799     fn generalize(&self,
 800                   ty: Ty<'tcx>,
 801                   for_vid: ty::TyVid,
 802                   make_region_vars: bool)
 803                   -> cres<'tcx, Ty<'tcx>>
 804     {
 805         let mut generalize = Generalizer { infcx: self.infcx,
 806                                            span: self.trace.origin.span(),
 807                                            for_vid: for_vid,
 808                                            make_region_vars: make_region_vars,
 809                                            cycle_detected: false };
 810         let u = ty.fold_with(&mut generalize);
 811         if generalize.cycle_detected {
 812             Err(ty::terr_cyclic_ty)
 813         } else {
 814             Ok(u)
 815         }
 816     }
 817 }
 818
 819 struct Generalizer<'cx, 'tcx:'cx> {
 820     infcx: &'cx InferCtxt<'cx, 'tcx>,
 821     span: Span,
 822     for_vid: ty::TyVid,
 823     make_region_vars: bool,
 824     cycle_detected: bool,
 825 }
 826
 827 impl<'cx, 'tcx> ty_fold::TypeFolder<'tcx> for Generalizer<'cx, 'tcx> {
 828     fn tcx(&self) -> &ty::ctxt<'tcx> {
 829         self.infcx.tcx
 830     }
 831
 832     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 833         // Check to see whether the type we are genealizing references
 834         // `vid`. At the same time, also update any type variables to
 835         // the values that they are bound to. This is needed to truly
 836         // check for cycles, but also just makes things readable.
 837         //
 838         // (In particular, you could have something like `$0 = Box<$1>`
 839         //  where `$1` has already been instantiated with `Box<$0>`)
 840         match t.sty {
 841             ty::ty_infer(ty::TyVar(vid)) => {
 842                 if vid == self.for_vid {
 843                     self.cycle_detected = true;
 844                     self.tcx().types.err
 845                 } else {
 846                     match self.infcx.type_variables.borrow().probe(vid) {
 847                         Some(u) => self.fold_ty(u),
 848                         None => t,
 849                     }
 850                 }
 851             }
 852             _ => {
 853                 ty_fold::super_fold_ty(self, t)
 854             }
 855         }
 856     }
 857
 858     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 859         match r {
 860             // Never make variables for regions bound within the type itself.
 861             ty::ReLateBound(..) => { return r; }
 862
 863             // Early-bound regions should really have been substituted away before
 864             // we get to this point.
 865             ty::ReEarlyBound(..) => {
 866                 self.tcx().sess.span_bug(
 867                     self.span,
 868                     &format!("Encountered early bound region when generalizing: {}",
 869                             r.repr(self.tcx()))[]);
 870             }
 871
 872             // Always make a fresh region variable for skolemized regions;
 873             // the higher-ranked decision procedures rely on this.
 874             ty::ReInfer(ty::ReSkolemized(..)) => { }
 875
 876             // For anything else, we make a region variable, unless we
 877             // are *equating*, in which case it's just wasteful.
 878             ty::ReEmpty |
 879             ty::ReStatic |
 880             ty::ReScope(..) |
 881             ty::ReInfer(ty::ReVar(..)) |
 882             ty::ReFree(..) => {
 883                 if !self.make_region_vars {
 884                     return r;
 885                 }
 886             }
 887         }
 888
 889         // FIXME: This is non-ideal because we don't give a
 890         // very descriptive origin for this region variable.
 891         self.infcx.next_region_var(MiscVariable(self.span))
 892     }
 893 }