src/librustc/middle/typeck/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
  36 use middle::subst;
  37 use middle::subst::Substs;
  38 use middle::ty::{FloatVar, FnSig, IntVar, TyVar};
  39 use middle::ty::{IntType, UintType};
  40 use middle::ty::{BuiltinBounds};
  41 use middle::ty;
  42 use middle::ty_fold;
  43 use middle::typeck::infer::equate::Equate;
  44 use middle::typeck::infer::glb::Glb;
  45 use middle::typeck::infer::lub::Lub;
  46 use middle::typeck::infer::sub::Sub;
  47 use middle::typeck::infer::unify::InferCtxtMethodsForSimplyUnifiableTypes;
  48 use middle::typeck::infer::{InferCtxt, cres};
  49 use middle::typeck::infer::{MiscVariable, TypeTrace};
  50 use middle::typeck::infer::type_variable::{RelationDir, EqTo,
  51                                            SubtypeOf, SupertypeOf};
  52 use middle::ty_fold::{TypeFoldable};
  53 use util::ppaux::Repr;
  54
  55 use std::result;
  56
  57 use syntax::ast::{Onceness, FnStyle};
  58 use syntax::ast;
  59 use syntax::abi;
  60 use syntax::codemap::Span;
  61
  62 pub trait Combine<'tcx> {
  63     fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx>;
  64     fn tag(&self) -> String;
  65     fn a_is_expected(&self) -> bool;
  66     fn trace(&self) -> TypeTrace;
  67
  68     fn equate<'a>(&'a self) -> Equate<'a, 'tcx>;
  69     fn sub<'a>(&'a self) -> Sub<'a, 'tcx>;
  70     fn lub<'a>(&'a self) -> Lub<'a, 'tcx>;
  71     fn glb<'a>(&'a self) -> Glb<'a, 'tcx>;
  72
  73     fn mts(&self, a: &ty::mt, b: &ty::mt) -> cres<ty::mt>;
  74     fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t>;
  75     fn tys(&self, a: ty::t, b: ty::t) -> cres<ty::t>;
  76
  77     fn tps(&self,
  78            _: subst::ParamSpace,
  79            as_: &[ty::t],
  80            bs: &[ty::t])
  81            -> cres<Vec<ty::t>> {
  82         // FIXME -- In general, we treat variance a bit wrong
  83         // here. For historical reasons, we treat tps and Self
  84         // as invariant. This is overly conservative.
  85
  86         if as_.len() != bs.len() {
  87             return Err(ty::terr_ty_param_size(expected_found(self,
  88                                                              as_.len(),
  89                                                              bs.len())));
  90         }
  91
  92         try!(result::fold_(as_
  93                           .iter()
  94                           .zip(bs.iter())
  95                           .map(|(a, b)| self.equate().tys(*a, *b))));
  96         Ok(Vec::from_slice(as_))
  97     }
  98
  99     fn substs(&self,
 100               item_def_id: ast::DefId,
 101               a_subst: &subst::Substs,
 102               b_subst: &subst::Substs)
 103               -> cres<subst::Substs>
 104     {
 105         let variances = if self.infcx().tcx.variance_computed.get() {
 106             Some(ty::item_variances(self.infcx().tcx, item_def_id))
 107         } else {
 108             None
 109         };
 110         let mut substs = subst::Substs::empty();
 111
 112         for &space in subst::ParamSpace::all().iter() {
 113             let a_tps = a_subst.types.get_slice(space);
 114             let b_tps = b_subst.types.get_slice(space);
 115             let tps = try!(self.tps(space, a_tps, b_tps));
 116
 117             let a_regions = a_subst.regions().get_slice(space);
 118             let b_regions = b_subst.regions().get_slice(space);
 119
 120             let mut invariance = Vec::new();
 121             let r_variances = match variances {
 122                 Some(ref variances) => variances.regions.get_slice(space),
 123                 None => {
 124                     for _ in a_regions.iter() {
 125                         invariance.push(ty::Invariant);
 126                     }
 127                     invariance.as_slice()
 128                 }
 129             };
 130
 131             let regions = try!(relate_region_params(self,
 132                                                     item_def_id,
 133                                                     r_variances,
 134                                                     a_regions,
 135                                                     b_regions));
 136
 137             substs.types.replace(space, tps);
 138             substs.mut_regions().replace(space, regions);
 139         }
 140
 141         return Ok(substs);
 142
 143         fn relate_region_params<'tcx, C: Combine<'tcx>>(this: &C,
 144                                                         item_def_id: ast::DefId,
 145                                                         variances: &[ty::Variance],
 146                                                         a_rs: &[ty::Region],
 147                                                         b_rs: &[ty::Region])
 148                                                         -> cres<Vec<ty::Region>> {
 149             let tcx = this.infcx().tcx;
 150             let num_region_params = variances.len();
 151
 152             debug!("relate_region_params(\
 153                    item_def_id={}, \
 154                    a_rs={}, \
 155                    b_rs={},
 156                    variances={})",
 157                    item_def_id.repr(tcx),
 158                    a_rs.repr(tcx),
 159                    b_rs.repr(tcx),
 160                    variances.repr(tcx));
 161
 162             assert_eq!(num_region_params, a_rs.len());
 163             assert_eq!(num_region_params, b_rs.len());
 164             let mut rs = vec!();
 165             for i in range(0, num_region_params) {
 166                 let a_r = a_rs[i];
 167                 let b_r = b_rs[i];
 168                 let variance = variances[i];
 169                 let r = match variance {
 170                     ty::Invariant => this.equate().regions(a_r, b_r),
 171                     ty::Covariant => this.regions(a_r, b_r),
 172                     ty::Contravariant => this.contraregions(a_r, b_r),
 173                     ty::Bivariant => Ok(a_r),
 174                 };
 175                 rs.push(try!(r));
 176             }
 177             Ok(rs)
 178         }
 179     }
 180
 181     fn bare_fn_tys(&self, a: &ty::BareFnTy,
 182                    b: &ty::BareFnTy) -> cres<ty::BareFnTy> {
 183         let fn_style = try!(self.fn_styles(a.fn_style, b.fn_style));
 184         let abi = try!(self.abi(a.abi, b.abi));
 185         let sig = try!(self.fn_sigs(&a.sig, &b.sig));
 186         Ok(ty::BareFnTy {fn_style: fn_style,
 187                 abi: abi,
 188                 sig: sig})
 189     }
 190
 191     fn closure_tys(&self, a: &ty::ClosureTy,
 192                    b: &ty::ClosureTy) -> cres<ty::ClosureTy> {
 193
 194         let store = match (a.store, b.store) {
 195             (ty::RegionTraitStore(a_r, a_m),
 196              ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => {
 197                 let r = try!(self.contraregions(a_r, b_r));
 198                 ty::RegionTraitStore(r, a_m)
 199             }
 200
 201             _ if a.store == b.store => {
 202                 a.store
 203             }
 204
 205             _ => {
 206                 return Err(ty::terr_sigil_mismatch(expected_found(self, a.store, b.store)))
 207             }
 208         };
 209         let fn_style = try!(self.fn_styles(a.fn_style, b.fn_style));
 210         let onceness = try!(self.oncenesses(a.onceness, b.onceness));
 211         let bounds = try!(self.existential_bounds(a.bounds, b.bounds));
 212         let sig = try!(self.fn_sigs(&a.sig, &b.sig));
 213         let abi = try!(self.abi(a.abi, b.abi));
 214         Ok(ty::ClosureTy {
 215             fn_style: fn_style,
 216             onceness: onceness,
 217             store: store,
 218             bounds: bounds,
 219             sig: sig,
 220             abi: abi,
 221         })
 222     }
 223
 224     fn fn_sigs(&self, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig>;
 225
 226     fn args(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
 227         self.contratys(a, b).and_then(|t| Ok(t))
 228     }
 229
 230     fn fn_styles(&self, a: FnStyle, b: FnStyle) -> cres<FnStyle>;
 231
 232     fn abi(&self, a: abi::Abi, b: abi::Abi) -> cres<abi::Abi> {
 233         if a == b {
 234             Ok(a)
 235         } else {
 236             Err(ty::terr_abi_mismatch(expected_found(self, a, b)))
 237         }
 238     }
 239
 240     fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<Onceness>;
 241
 242     fn existential_bounds(&self,
 243                           a: ty::ExistentialBounds,
 244                           b: ty::ExistentialBounds)
 245                           -> cres<ty::ExistentialBounds>
 246     {
 247         let r = try!(self.contraregions(a.region_bound, b.region_bound));
 248         let nb = try!(self.builtin_bounds(a.builtin_bounds, b.builtin_bounds));
 249         Ok(ty::ExistentialBounds { region_bound: r,
 250                                    builtin_bounds: nb })
 251     }
 252
 253     fn builtin_bounds(&self,
 254                       a: ty::BuiltinBounds,
 255                       b: ty::BuiltinBounds)
 256                       -> cres<ty::BuiltinBounds>;
 257
 258     fn contraregions(&self, a: ty::Region, b: ty::Region)
 259                   -> cres<ty::Region>;
 260
 261     fn regions(&self, a: ty::Region, b: ty::Region) -> cres<ty::Region>;
 262
 263     fn trait_stores(&self,
 264                     vk: ty::terr_vstore_kind,
 265                     a: ty::TraitStore,
 266                     b: ty::TraitStore)
 267                     -> cres<ty::TraitStore> {
 268         debug!("{}.trait_stores(a={}, b={})", self.tag(), a, b);
 269
 270         match (a, b) {
 271             (ty::RegionTraitStore(a_r, a_m),
 272              ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => {
 273                 self.contraregions(a_r, b_r).and_then(|r| {
 274                     Ok(ty::RegionTraitStore(r, a_m))
 275                 })
 276             }
 277
 278             _ if a == b => {
 279                 Ok(a)
 280             }
 281
 282             _ => {
 283                 Err(ty::terr_trait_stores_differ(vk, expected_found(self, a, b)))
 284             }
 285         }
 286
 287     }
 288
 289     fn trait_refs(&self,
 290                   a: &ty::TraitRef,
 291                   b: &ty::TraitRef)
 292                   -> cres<ty::TraitRef> {
 293         // Different traits cannot be related
 294
 295         // - NOTE in the future, expand out subtraits!
 296
 297         if a.def_id != b.def_id {
 298             Err(ty::terr_traits(
 299                                 expected_found(self, a.def_id, b.def_id)))
 300         } else {
 301             let substs = try!(self.substs(a.def_id, &a.substs, &b.substs));
 302             Ok(ty::TraitRef { def_id: a.def_id,
 303                               substs: substs })
 304         }
 305     }
 306 }
 307
 308 #[deriving(Clone)]
 309 pub struct CombineFields<'a, 'tcx: 'a> {
 310     pub infcx: &'a InferCtxt<'a, 'tcx>,
 311     pub a_is_expected: bool,
 312     pub trace: TypeTrace,
 313 }
 314
 315 pub fn expected_found<'tcx, C: Combine<'tcx>, T>(
 316         this: &C, a: T, b: T) -> ty::expected_found<T> {
 317     if this.a_is_expected() {
 318         ty::expected_found {expected: a, found: b}
 319     } else {
 320         ty::expected_found {expected: b, found: a}
 321     }
 322 }
 323
 324 pub fn super_fn_sigs<'tcx, C: Combine<'tcx>>(this: &C,
 325                                              a: &ty::FnSig,
 326                                              b: &ty::FnSig)
 327                                              -> cres<ty::FnSig> {
 328
 329     fn argvecs<'tcx, C: Combine<'tcx>>(this: &C,
 330                                        a_args: &[ty::t],
 331                                        b_args: &[ty::t])
 332                                        -> cres<Vec<ty::t>> {
 333         if a_args.len() == b_args.len() {
 334             result::collect(a_args.iter().zip(b_args.iter())
 335                             .map(|(a, b)| this.args(*a, *b)))
 336         } else {
 337             Err(ty::terr_arg_count)
 338         }
 339     }
 340
 341     if a.variadic != b.variadic {
 342         return Err(ty::terr_variadic_mismatch(expected_found(this, a.variadic, b.variadic)));
 343     }
 344
 345     let inputs = try!(argvecs(this,
 346                                 a.inputs.as_slice(),
 347                                 b.inputs.as_slice()));
 348     let output = try!(this.tys(a.output, b.output));
 349     Ok(FnSig {binder_id: a.binder_id,
 350               inputs: inputs,
 351               output: output,
 352               variadic: a.variadic})
 353 }
 354
 355 pub fn super_tys<'tcx, C: Combine<'tcx>>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
 356
 357     // This is a horrible hack - historically, [T] was not treated as a type,
 358     // so, for example, &T and &[U] should not unify. In fact the only thing
 359     // &[U] should unify with is &[T]. We preserve that behaviour with this
 360     // check.
 361     fn check_ptr_to_unsized<'tcx, C: Combine<'tcx>>(this: &C,
 362                                                     a: ty::t,
 363                                                     b: ty::t,
 364                                                     a_inner: ty::t,
 365                                                     b_inner: ty::t,
 366                                                     result: ty::t) -> cres<ty::t> {
 367         match (&ty::get(a_inner).sty, &ty::get(b_inner).sty) {
 368             (&ty::ty_vec(_, None), &ty::ty_vec(_, None)) |
 369             (&ty::ty_str, &ty::ty_str) |
 370             (&ty::ty_trait(..), &ty::ty_trait(..)) => Ok(result),
 371             (&ty::ty_vec(_, None), _) | (_, &ty::ty_vec(_, None)) |
 372             (&ty::ty_str, _) | (_, &ty::ty_str) |
 373             (&ty::ty_trait(..), _) | (_, &ty::ty_trait(..))
 374                 => Err(ty::terr_sorts(expected_found(this, a, b))),
 375             _ => Ok(result),
 376         }
 377     }
 378
 379     let tcx = this.infcx().tcx;
 380     let a_sty = &ty::get(a).sty;
 381     let b_sty = &ty::get(b).sty;
 382     debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
 383     return match (a_sty, b_sty) {
 384       // The "subtype" ought to be handling cases involving bot or var:
 385       (&ty::ty_bot, _) |
 386       (_, &ty::ty_bot) |
 387       (&ty::ty_infer(TyVar(_)), _) |
 388       (_, &ty::ty_infer(TyVar(_))) => {
 389         tcx.sess.bug(
 390             format!("{}: bot and var types should have been handled ({},{})",
 391                     this.tag(),
 392                     a.repr(this.infcx().tcx),
 393                     b.repr(this.infcx().tcx)).as_slice());
 394       }
 395
 396         // Relate integral variables to other types
 397         (&ty::ty_infer(IntVar(a_id)), &ty::ty_infer(IntVar(b_id))) => {
 398             try!(this.infcx().simple_vars(this.a_is_expected(),
 399                                             a_id, b_id));
 400             Ok(a)
 401         }
 402         (&ty::ty_infer(IntVar(v_id)), &ty::ty_int(v)) => {
 403             unify_integral_variable(this, this.a_is_expected(),
 404                                     v_id, IntType(v))
 405         }
 406         (&ty::ty_int(v), &ty::ty_infer(IntVar(v_id))) => {
 407             unify_integral_variable(this, !this.a_is_expected(),
 408                                     v_id, IntType(v))
 409         }
 410         (&ty::ty_infer(IntVar(v_id)), &ty::ty_uint(v)) => {
 411             unify_integral_variable(this, this.a_is_expected(),
 412                                     v_id, UintType(v))
 413         }
 414         (&ty::ty_uint(v), &ty::ty_infer(IntVar(v_id))) => {
 415             unify_integral_variable(this, !this.a_is_expected(),
 416                                     v_id, UintType(v))
 417         }
 418
 419         // Relate floating-point variables to other types
 420         (&ty::ty_infer(FloatVar(a_id)), &ty::ty_infer(FloatVar(b_id))) => {
 421             try!(this.infcx().simple_vars(this.a_is_expected(), a_id, b_id));
 422             Ok(a)
 423         }
 424         (&ty::ty_infer(FloatVar(v_id)), &ty::ty_float(v)) => {
 425             unify_float_variable(this, this.a_is_expected(), v_id, v)
 426         }
 427         (&ty::ty_float(v), &ty::ty_infer(FloatVar(v_id))) => {
 428             unify_float_variable(this, !this.a_is_expected(), v_id, v)
 429         }
 430
 431       (&ty::ty_char, _) |
 432       (&ty::ty_nil, _) |
 433       (&ty::ty_bool, _) |
 434       (&ty::ty_int(_), _) |
 435       (&ty::ty_uint(_), _) |
 436       (&ty::ty_float(_), _) |
 437       (&ty::ty_err, _) => {
 438         if ty::get(a).sty == ty::get(b).sty {
 439             Ok(a)
 440         } else {
 441             Err(ty::terr_sorts(expected_found(this, a, b)))
 442         }
 443       }
 444
 445       (&ty::ty_param(ref a_p), &ty::ty_param(ref b_p)) if
 446           a_p.idx == b_p.idx && a_p.space == b_p.space => {
 447         Ok(a)
 448       }
 449
 450       (&ty::ty_enum(a_id, ref a_substs),
 451        &ty::ty_enum(b_id, ref b_substs))
 452       if a_id == b_id => {
 453           let substs = try!(this.substs(a_id,
 454                                           a_substs,
 455                                           b_substs));
 456           Ok(ty::mk_enum(tcx, a_id, substs))
 457       }
 458
 459       (&ty::ty_trait(ref a_),
 460        &ty::ty_trait(ref b_))
 461       if a_.def_id == b_.def_id => {
 462           debug!("Trying to match traits {:?} and {:?}", a, b);
 463           let substs = try!(this.substs(a_.def_id, &a_.substs, &b_.substs));
 464           let bounds = try!(this.existential_bounds(a_.bounds, b_.bounds));
 465           Ok(ty::mk_trait(tcx,
 466                           a_.def_id,
 467                           substs.clone(),
 468                           bounds))
 469       }
 470
 471       (&ty::ty_struct(a_id, ref a_substs), &ty::ty_struct(b_id, ref b_substs))
 472       if a_id == b_id => {
 473             let substs = try!(this.substs(a_id, a_substs, b_substs));
 474             Ok(ty::mk_struct(tcx, a_id, substs))
 475       }
 476
 477       (&ty::ty_unboxed_closure(a_id, a_region),
 478        &ty::ty_unboxed_closure(b_id, b_region))
 479       if a_id == b_id => {
 480           // All ty_unboxed_closure types with the same id represent
 481           // the (anonymous) type of the same closure expression. So
 482           // all of their regions should be equated.
 483           let region = try!(this.equate().regions(a_region, b_region));
 484           Ok(ty::mk_unboxed_closure(tcx, a_id, region))
 485       }
 486
 487       (&ty::ty_box(a_inner), &ty::ty_box(b_inner)) => {
 488         this.tys(a_inner, b_inner).and_then(|typ| Ok(ty::mk_box(tcx, typ)))
 489       }
 490
 491       (&ty::ty_uniq(a_inner), &ty::ty_uniq(b_inner)) => {
 492             let typ = try!(this.tys(a_inner, b_inner));
 493             check_ptr_to_unsized(this, a, b, a_inner, b_inner, ty::mk_uniq(tcx, typ))
 494       }
 495
 496       (&ty::ty_ptr(ref a_mt), &ty::ty_ptr(ref b_mt)) => {
 497             let mt = try!(this.mts(a_mt, b_mt));
 498             check_ptr_to_unsized(this, a, b, a_mt.ty, b_mt.ty, ty::mk_ptr(tcx, mt))
 499       }
 500
 501       (&ty::ty_rptr(a_r, ref a_mt), &ty::ty_rptr(b_r, ref b_mt)) => {
 502             let r = try!(this.contraregions(a_r, b_r));
 503             // FIXME(14985)  If we have mutable references to trait objects, we
 504             // used to use covariant subtyping. I have preserved this behaviour,
 505             // even though it is probably incorrect. So don't go down the usual
 506             // path which would require invariance.
 507             let mt = match (&ty::get(a_mt.ty).sty, &ty::get(b_mt.ty).sty) {
 508                 (&ty::ty_trait(..), &ty::ty_trait(..)) if a_mt.mutbl == b_mt.mutbl => {
 509                     let ty = try!(this.tys(a_mt.ty, b_mt.ty));
 510                     ty::mt { ty: ty, mutbl: a_mt.mutbl }
 511                 }
 512                 _ => try!(this.mts(a_mt, b_mt))
 513             };
 514             check_ptr_to_unsized(this, a, b, a_mt.ty, b_mt.ty, ty::mk_rptr(tcx, r, mt))
 515       }
 516
 517       (&ty::ty_vec(a_t, sz_a), &ty::ty_vec(b_t, sz_b)) => {
 518         this.tys(a_t, b_t).and_then(|t| {
 519             if sz_a == sz_b {
 520                 Ok(ty::mk_vec(tcx, t, sz_a))
 521             } else {
 522                 Err(ty::terr_sorts(expected_found(this, a, b)))
 523             }
 524         })
 525       }
 526
 527       (&ty::ty_str, &ty::ty_str) => {
 528             Ok(ty::mk_str(tcx))
 529       }
 530
 531       (&ty::ty_tup(ref as_), &ty::ty_tup(ref bs)) => {
 532         if as_.len() == bs.len() {
 533             result::collect(as_.iter().zip(bs.iter())
 534                             .map(|(a, b)| this.tys(*a, *b)))
 535                     .and_then(|ts| Ok(ty::mk_tup(tcx, ts)) )
 536         } else {
 537             Err(ty::terr_tuple_size(
 538                 expected_found(this, as_.len(), bs.len())))
 539         }
 540       }
 541
 542       (&ty::ty_bare_fn(ref a_fty), &ty::ty_bare_fn(ref b_fty)) => {
 543         this.bare_fn_tys(a_fty, b_fty).and_then(|fty| {
 544             Ok(ty::mk_bare_fn(tcx, fty))
 545         })
 546       }
 547
 548       (&ty::ty_closure(ref a_fty), &ty::ty_closure(ref b_fty)) => {
 549         this.closure_tys(&**a_fty, &**b_fty).and_then(|fty| {
 550             Ok(ty::mk_closure(tcx, fty))
 551         })
 552       }
 553
 554       _ => Err(ty::terr_sorts(expected_found(this, a, b)))
 555     };
 556
 557     fn unify_integral_variable<'tcx, C: Combine<'tcx>>(
 558         this: &C,
 559         vid_is_expected: bool,
 560         vid: ty::IntVid,
 561         val: ty::IntVarValue) -> cres<ty::t>
 562     {
 563         try!(this.infcx().simple_var_t(vid_is_expected, vid, val));
 564         match val {
 565             IntType(v) => Ok(ty::mk_mach_int(v)),
 566             UintType(v) => Ok(ty::mk_mach_uint(v))
 567         }
 568     }
 569
 570     fn unify_float_variable<'tcx, C: Combine<'tcx>>(
 571         this: &C,
 572         vid_is_expected: bool,
 573         vid: ty::FloatVid,
 574         val: ast::FloatTy) -> cres<ty::t>
 575     {
 576         try!(this.infcx().simple_var_t(vid_is_expected, vid, val));
 577         Ok(ty::mk_mach_float(val))
 578     }
 579 }
 580
 581 impl<'f, 'tcx> CombineFields<'f, 'tcx> {
 582     pub fn switch_expected(&self) -> CombineFields<'f, 'tcx> {
 583         CombineFields {
 584             a_is_expected: !self.a_is_expected,
 585             ..(*self).clone()
 586         }
 587     }
 588
 589     fn equate(&self) -> Equate<'f, 'tcx> {
 590         Equate((*self).clone())
 591     }
 592
 593     fn sub(&self) -> Sub<'f, 'tcx> {
 594         Sub((*self).clone())
 595     }
 596
 597     pub fn instantiate(&self,
 598                        a_ty: ty::t,
 599                        dir: RelationDir,
 600                        b_vid: ty::TyVid)
 601                        -> cres<()>
 602     {
 603         let tcx = self.infcx.tcx;
 604         let mut stack = Vec::new();
 605         stack.push((a_ty, dir, b_vid));
 606         loop {
 607             // For each turn of the loop, we extract a tuple
 608             //
 609             //     (a_ty, dir, b_vid)
 610             //
 611             // to relate. Here dir is either SubtypeOf or
 612             // SupertypeOf. The idea is that we should ensure that
 613             // the type `a_ty` is a subtype or supertype (respectively) of the
 614             // type to which `b_vid` is bound.
 615             //
 616             // If `b_vid` has not yet been instantiated with a type
 617             // (which is always true on the first iteration, but not
 618             // necessarily true on later iterations), we will first
 619             // instantiate `b_vid` with a *generalized* version of
 620             // `a_ty`. Generalization introduces other inference
 621             // variables wherever subtyping could occur (at time of
 622             // this writing, this means replacing free regions with
 623             // region variables).
 624             let (a_ty, dir, b_vid) = match stack.pop() {
 625                 None => break,
 626                 Some(e) => e,
 627             };
 628
 629             debug!("instantiate(a_ty={} dir={} b_vid={})",
 630                    a_ty.repr(tcx),
 631                    dir,
 632                    b_vid.repr(tcx));
 633
 634             // Check whether `vid` has been instantiated yet.  If not,
 635             // make a generalized form of `ty` and instantiate with
 636             // that.
 637             let b_ty = self.infcx.type_variables.borrow().probe(b_vid);
 638             let b_ty = match b_ty {
 639                 Some(t) => t, // ...already instantiated.
 640                 None => {     // ...not yet instantiated:
 641                     // Generalize type if necessary.
 642                     let generalized_ty = try!(match dir {
 643                         EqTo => {
 644                             self.generalize(a_ty, b_vid, false)
 645                         }
 646                         SupertypeOf | SubtypeOf => {
 647                             self.generalize(a_ty, b_vid, true)
 648                         }
 649                     });
 650                     debug!("instantiate(a_ty={}, dir={}, \
 651                                         b_vid={}, generalized_ty={})",
 652                            a_ty.repr(tcx), dir, b_vid.repr(tcx),
 653                            generalized_ty.repr(tcx));
 654                     self.infcx.type_variables
 655                         .borrow_mut()
 656                         .instantiate_and_push(
 657                             b_vid, generalized_ty, &mut stack);
 658                     generalized_ty
 659                 }
 660             };
 661
 662             // The original triple was `(a_ty, dir, b_vid)` -- now we have
 663             // resolved `b_vid` to `b_ty`, so apply `(a_ty, dir, b_ty)`:
 664             //
 665             // FIXME(#16847): This code is non-ideal because all these subtype
 666             // relations wind up attributed to the same spans. We need
 667             // to associate causes/spans with each of the relations in
 668             // the stack to get this right.
 669             match dir {
 670                 EqTo => {
 671                     try!(self.equate().tys(a_ty, b_ty));
 672                 }
 673
 674                 SubtypeOf => {
 675                     try!(self.sub().tys(a_ty, b_ty));
 676                 }
 677
 678                 SupertypeOf => {
 679                     try!(self.sub().contratys(a_ty, b_ty));
 680                 }
 681             }
 682         }
 683
 684         Ok(())
 685     }
 686
 687     fn generalize(&self,
 688                   ty: ty::t,
 689                   for_vid: ty::TyVid,
 690                   make_region_vars: bool)
 691                   -> cres<ty::t>
 692     {
 693         /*!
 694          * Attempts to generalize `ty` for the type variable
 695          * `for_vid`.  This checks for cycle -- that is, whether the
 696          * type `ty` references `for_vid`. If `make_region_vars` is
 697          * true, it will also replace all regions with fresh
 698          * variables. Returns `ty_err` in the case of a cycle, `Ok`
 699          * otherwise.
 700          */
 701
 702         let mut generalize = Generalizer { infcx: self.infcx,
 703                                            span: self.trace.origin.span(),
 704                                            for_vid: for_vid,
 705                                            make_region_vars: make_region_vars,
 706                                            cycle_detected: false };
 707         let u = ty.fold_with(&mut generalize);
 708         if generalize.cycle_detected {
 709             Err(ty::terr_cyclic_ty)
 710         } else {
 711             Ok(u)
 712         }
 713     }
 714 }
 715
 716 struct Generalizer<'cx, 'tcx:'cx> {
 717     infcx: &'cx InferCtxt<'cx, 'tcx>,
 718     span: Span,
 719     for_vid: ty::TyVid,
 720     make_region_vars: bool,
 721     cycle_detected: bool,
 722 }
 723
 724 impl<'cx, 'tcx> ty_fold::TypeFolder<'tcx> for Generalizer<'cx, 'tcx> {
 725     fn tcx(&self) -> &ty::ctxt<'tcx> {
 726         self.infcx.tcx
 727     }
 728
 729     fn fold_ty(&mut self, t: ty::t) -> ty::t {
 730         // Check to see whether the type we are genealizing references
 731         // `vid`. At the same time, also update any type variables to
 732         // the values that they are bound to. This is needed to truly
 733         // check for cycles, but also just makes things readable.
 734         //
 735         // (In particular, you could have something like `$0 = Box<$1>`
 736         //  where `$1` has already been instantiated with `Box<$0>`)
 737         match ty::get(t).sty {
 738             ty::ty_infer(ty::TyVar(vid)) => {
 739                 if vid == self.for_vid {
 740                     self.cycle_detected = true;
 741                     ty::mk_err()
 742                 } else {
 743                     match self.infcx.type_variables.borrow().probe(vid) {
 744                         Some(u) => self.fold_ty(u),
 745                         None => t,
 746                     }
 747                 }
 748             }
 749             _ => {
 750                 ty_fold::super_fold_ty(self, t)
 751             }
 752         }
 753     }
 754
 755     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 756         match r {
 757             ty::ReLateBound(..) | ty::ReEarlyBound(..) => r,
 758             _ if self.make_region_vars => {
 759                 // FIXME: This is non-ideal because we don't give a
 760                 // very descriptive origin for this region variable.
 761                 self.infcx.next_region_var(MiscVariable(self.span))
 762             }
 763             _ => r,
 764         }
 765     }
 766 }
 767
 768