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