src/librustc/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::InferCtxt;
  41 use super::{MiscVariable, TypeTrace};
  42 use super::type_variable::{RelationDir, BiTo, EqTo, SubtypeOf, SupertypeOf};
  43
  44 use ty::{IntType, UintType};
  45 use ty::{self, Ty, TyCtxt};
  46 use ty::error::TypeError;
  47 use ty::fold::TypeFoldable;
  48 use ty::relate::{RelateResult, TypeRelation};
  49 use traits::PredicateObligations;
  50
  51 use syntax::ast;
  52 use syntax::util::small_vector::SmallVector;
  53 use syntax_pos::Span;
  54
  55 #[derive(Clone)]
  56 pub struct CombineFields<'infcx, 'gcx: 'infcx+'tcx, 'tcx: 'infcx> {
  57     pub infcx: &'infcx InferCtxt<'infcx, 'gcx, 'tcx>,
  58     pub trace: TypeTrace<'tcx>,
  59     pub cause: Option<ty::relate::Cause>,
  60     pub obligations: PredicateObligations<'tcx>,
  61 }
  62
  63 impl<'infcx, 'gcx, 'tcx> InferCtxt<'infcx, 'gcx, 'tcx> {
  64     pub fn super_combine_tys<R>(&self,
  65                                 relation: &mut R,
  66                                 a: Ty<'tcx>,
  67                                 b: Ty<'tcx>)
  68                                 -> RelateResult<'tcx, Ty<'tcx>>
  69         where R: TypeRelation<'infcx, 'gcx, 'tcx>
  70     {
  71         let a_is_expected = relation.a_is_expected();
  72
  73         match (&a.sty, &b.sty) {
  74             // Relate integral variables to other types
  75             (&ty::TyInfer(ty::IntVar(a_id)), &ty::TyInfer(ty::IntVar(b_id))) => {
  76                 self.int_unification_table
  77                     .borrow_mut()
  78                     .unify_var_var(a_id, b_id)
  79                     .map_err(|e| int_unification_error(a_is_expected, e))?;
  80                 Ok(a)
  81             }
  82             (&ty::TyInfer(ty::IntVar(v_id)), &ty::TyInt(v)) => {
  83                 self.unify_integral_variable(a_is_expected, v_id, IntType(v))
  84             }
  85             (&ty::TyInt(v), &ty::TyInfer(ty::IntVar(v_id))) => {
  86                 self.unify_integral_variable(!a_is_expected, v_id, IntType(v))
  87             }
  88             (&ty::TyInfer(ty::IntVar(v_id)), &ty::TyUint(v)) => {
  89                 self.unify_integral_variable(a_is_expected, v_id, UintType(v))
  90             }
  91             (&ty::TyUint(v), &ty::TyInfer(ty::IntVar(v_id))) => {
  92                 self.unify_integral_variable(!a_is_expected, v_id, UintType(v))
  93             }
  94
  95             // Relate floating-point variables to other types
  96             (&ty::TyInfer(ty::FloatVar(a_id)), &ty::TyInfer(ty::FloatVar(b_id))) => {
  97                 self.float_unification_table
  98                     .borrow_mut()
  99                     .unify_var_var(a_id, b_id)
 100                     .map_err(|e| float_unification_error(relation.a_is_expected(), e))?;
 101                 Ok(a)
 102             }
 103             (&ty::TyInfer(ty::FloatVar(v_id)), &ty::TyFloat(v)) => {
 104                 self.unify_float_variable(a_is_expected, v_id, v)
 105             }
 106             (&ty::TyFloat(v), &ty::TyInfer(ty::FloatVar(v_id))) => {
 107                 self.unify_float_variable(!a_is_expected, v_id, v)
 108             }
 109
 110             // All other cases of inference are errors
 111             (&ty::TyInfer(_), _) |
 112             (_, &ty::TyInfer(_)) => {
 113                 Err(TypeError::Sorts(ty::relate::expected_found(relation, &a, &b)))
 114             }
 115
 116
 117             _ => {
 118                 ty::relate::super_relate_tys(relation, a, b)
 119             }
 120         }
 121     }
 122
 123     fn unify_integral_variable(&self,
 124                                vid_is_expected: bool,
 125                                vid: ty::IntVid,
 126                                val: ty::IntVarValue)
 127                                -> RelateResult<'tcx, Ty<'tcx>>
 128     {
 129         self.int_unification_table
 130             .borrow_mut()
 131             .unify_var_value(vid, val)
 132             .map_err(|e| int_unification_error(vid_is_expected, e))?;
 133         match val {
 134             IntType(v) => Ok(self.tcx.mk_mach_int(v)),
 135             UintType(v) => Ok(self.tcx.mk_mach_uint(v)),
 136         }
 137     }
 138
 139     fn unify_float_variable(&self,
 140                             vid_is_expected: bool,
 141                             vid: ty::FloatVid,
 142                             val: ast::FloatTy)
 143                             -> RelateResult<'tcx, Ty<'tcx>>
 144     {
 145         self.float_unification_table
 146             .borrow_mut()
 147             .unify_var_value(vid, val)
 148             .map_err(|e| float_unification_error(vid_is_expected, e))?;
 149         Ok(self.tcx.mk_mach_float(val))
 150     }
 151 }
 152
 153 impl<'infcx, 'gcx, 'tcx> CombineFields<'infcx, 'gcx, 'tcx> {
 154     pub fn tcx(&self) -> TyCtxt<'infcx, 'gcx, 'tcx> {
 155         self.infcx.tcx
 156     }
 157
 158     pub fn equate<'a>(&'a mut self, a_is_expected: bool) -> Equate<'a, 'infcx, 'gcx, 'tcx> {
 159         Equate::new(self, a_is_expected)
 160     }
 161
 162     pub fn bivariate<'a>(&'a mut self, a_is_expected: bool) -> Bivariate<'a, 'infcx, 'gcx, 'tcx> {
 163         Bivariate::new(self, a_is_expected)
 164     }
 165
 166     pub fn sub<'a>(&'a mut self, a_is_expected: bool) -> Sub<'a, 'infcx, 'gcx, 'tcx> {
 167         Sub::new(self, a_is_expected)
 168     }
 169
 170     pub fn lub<'a>(&'a mut self, a_is_expected: bool) -> Lub<'a, 'infcx, 'gcx, 'tcx> {
 171         Lub::new(self, a_is_expected)
 172     }
 173
 174     pub fn glb<'a>(&'a mut self, a_is_expected: bool) -> Glb<'a, 'infcx, 'gcx, 'tcx> {
 175         Glb::new(self, a_is_expected)
 176     }
 177
 178     pub fn instantiate(&mut self,
 179                        a_ty: Ty<'tcx>,
 180                        dir: RelationDir,
 181                        b_vid: ty::TyVid,
 182                        a_is_expected: bool)
 183                        -> RelateResult<'tcx, ()>
 184     {
 185         // We use SmallVector here instead of Vec because this code is hot and
 186         // it's rare that the stack length exceeds 1.
 187         let mut stack = SmallVector::new();
 188         stack.push((a_ty, dir, b_vid));
 189         loop {
 190             // For each turn of the loop, we extract a tuple
 191             //
 192             //     (a_ty, dir, b_vid)
 193             //
 194             // to relate. Here dir is either SubtypeOf or
 195             // SupertypeOf. The idea is that we should ensure that
 196             // the type `a_ty` is a subtype or supertype (respectively) of the
 197             // type to which `b_vid` is bound.
 198             //
 199             // If `b_vid` has not yet been instantiated with a type
 200             // (which is always true on the first iteration, but not
 201             // necessarily true on later iterations), we will first
 202             // instantiate `b_vid` with a *generalized* version of
 203             // `a_ty`. Generalization introduces other inference
 204             // variables wherever subtyping could occur (at time of
 205             // this writing, this means replacing free regions with
 206             // region variables).
 207             let (a_ty, dir, b_vid) = match stack.pop() {
 208                 None => break,
 209                 Some(e) => e,
 210             };
 211             // Get the actual variable that b_vid has been inferred to
 212             let (b_vid, b_ty) = {
 213                 let mut variables = self.infcx.type_variables.borrow_mut();
 214                 let b_vid = variables.root_var(b_vid);
 215                 (b_vid, variables.probe_root(b_vid))
 216             };
 217
 218             debug!("instantiate(a_ty={:?} dir={:?} b_vid={:?})",
 219                    a_ty,
 220                    dir,
 221                    b_vid);
 222
 223             // Check whether `vid` has been instantiated yet.  If not,
 224             // make a generalized form of `ty` and instantiate with
 225             // that.
 226             let b_ty = match b_ty {
 227                 Some(t) => t, // ...already instantiated.
 228                 None => {     // ...not yet instantiated:
 229                     // Generalize type if necessary.
 230                     let generalized_ty = match dir {
 231                         EqTo => self.generalize(a_ty, b_vid, false),
 232                         BiTo | SupertypeOf | SubtypeOf => self.generalize(a_ty, b_vid, true),
 233                     }?;
 234                     debug!("instantiate(a_ty={:?}, dir={:?}, \
 235                                         b_vid={:?}, generalized_ty={:?})",
 236                            a_ty, dir, b_vid,
 237                            generalized_ty);
 238                     self.infcx.type_variables
 239                         .borrow_mut()
 240                         .instantiate_and_push(
 241                             b_vid, generalized_ty, &mut stack);
 242                     generalized_ty
 243                 }
 244             };
 245
 246             // The original triple was `(a_ty, dir, b_vid)` -- now we have
 247             // resolved `b_vid` to `b_ty`, so apply `(a_ty, dir, b_ty)`:
 248             //
 249             // FIXME(#16847): This code is non-ideal because all these subtype
 250             // relations wind up attributed to the same spans. We need
 251             // to associate causes/spans with each of the relations in
 252             // the stack to get this right.
 253             match dir {
 254                 BiTo => self.bivariate(a_is_expected).relate(&a_ty, &b_ty),
 255                 EqTo => self.equate(a_is_expected).relate(&a_ty, &b_ty),
 256                 SubtypeOf => self.sub(a_is_expected).relate(&a_ty, &b_ty),
 257                 SupertypeOf => self.sub(a_is_expected).relate_with_variance(
 258                     ty::Contravariant, &a_ty, &b_ty),
 259             }?;
 260         }
 261
 262         Ok(())
 263     }
 264
 265     /// Attempts to generalize `ty` for the type variable `for_vid`.  This checks for cycle -- that
 266     /// is, whether the type `ty` references `for_vid`. If `make_region_vars` is true, it will also
 267     /// replace all regions with fresh variables. Returns `TyError` in the case of a cycle, `Ok`
 268     /// otherwise.
 269     fn generalize(&self,
 270                   ty: Ty<'tcx>,
 271                   for_vid: ty::TyVid,
 272                   make_region_vars: bool)
 273                   -> RelateResult<'tcx, Ty<'tcx>>
 274     {
 275         let mut generalize = Generalizer {
 276             infcx: self.infcx,
 277             span: self.trace.cause.span,
 278             for_vid: for_vid,
 279             make_region_vars: make_region_vars,
 280             cycle_detected: false
 281         };
 282         let u = ty.fold_with(&mut generalize);
 283         if generalize.cycle_detected {
 284             Err(TypeError::CyclicTy)
 285         } else {
 286             Ok(u)
 287         }
 288     }
 289 }
 290
 291 struct Generalizer<'cx, 'gcx: 'cx+'tcx, 'tcx: 'cx> {
 292     infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
 293     span: Span,
 294     for_vid: ty::TyVid,
 295     make_region_vars: bool,
 296     cycle_detected: bool,
 297 }
 298
 299 impl<'cx, 'gcx, 'tcx> ty::fold::TypeFolder<'gcx, 'tcx> for Generalizer<'cx, 'gcx, 'tcx> {
 300     fn tcx<'a>(&'a self) -> TyCtxt<'a, 'gcx, 'tcx> {
 301         self.infcx.tcx
 302     }
 303
 304     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 305         // Check to see whether the type we are genealizing references
 306         // `vid`. At the same time, also update any type variables to
 307         // the values that they are bound to. This is needed to truly
 308         // check for cycles, but also just makes things readable.
 309         //
 310         // (In particular, you could have something like `$0 = Box<$1>`
 311         //  where `$1` has already been instantiated with `Box<$0>`)
 312         match t.sty {
 313             ty::TyInfer(ty::TyVar(vid)) => {
 314                 let mut variables = self.infcx.type_variables.borrow_mut();
 315                 let vid = variables.root_var(vid);
 316                 if vid == self.for_vid {
 317                     self.cycle_detected = true;
 318                     self.tcx().types.err
 319                 } else {
 320                     match variables.probe_root(vid) {
 321                         Some(u) => {
 322                             drop(variables);
 323                             self.fold_ty(u)
 324                         }
 325                         None => t,
 326                     }
 327                 }
 328             }
 329             _ => {
 330                 t.super_fold_with(self)
 331             }
 332         }
 333     }
 334
 335     fn fold_region(&mut self, r: &'tcx ty::Region) -> &'tcx ty::Region {
 336         match *r {
 337             // Never make variables for regions bound within the type itself,
 338             // nor for erased regions.
 339             ty::ReLateBound(..) |
 340             ty::ReErased => { return r; }
 341
 342             // Early-bound regions should really have been substituted away before
 343             // we get to this point.
 344             ty::ReEarlyBound(..) => {
 345                 span_bug!(
 346                     self.span,
 347                     "Encountered early bound region when generalizing: {:?}",
 348                     r);
 349             }
 350
 351             // Always make a fresh region variable for skolemized regions;
 352             // the higher-ranked decision procedures rely on this.
 353             ty::ReSkolemized(..) => { }
 354
 355             // For anything else, we make a region variable, unless we
 356             // are *equating*, in which case it's just wasteful.
 357             ty::ReEmpty |
 358             ty::ReStatic |
 359             ty::ReScope(..) |
 360             ty::ReVar(..) |
 361             ty::ReFree(..) => {
 362                 if !self.make_region_vars {
 363                     return r;
 364                 }
 365             }
 366         }
 367
 368         // FIXME: This is non-ideal because we don't give a
 369         // very descriptive origin for this region variable.
 370         self.infcx.next_region_var(MiscVariable(self.span))
 371     }
 372 }
 373
 374 pub trait RelateResultCompare<'tcx, T> {
 375     fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T> where
 376         F: FnOnce() -> TypeError<'tcx>;
 377 }
 378
 379 impl<'tcx, T:Clone + PartialEq> RelateResultCompare<'tcx, T> for RelateResult<'tcx, T> {
 380     fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T> where
 381         F: FnOnce() -> TypeError<'tcx>,
 382     {
 383         self.clone().and_then(|s| {
 384             if s == t {
 385                 self.clone()
 386             } else {
 387                 Err(f())
 388             }
 389         })
 390     }
 391 }
 392
 393 fn int_unification_error<'tcx>(a_is_expected: bool, v: (ty::IntVarValue, ty::IntVarValue))
 394                                -> TypeError<'tcx>
 395 {
 396     let (a, b) = v;
 397     TypeError::IntMismatch(ty::relate::expected_found_bool(a_is_expected, &a, &b))
 398 }
 399
 400 fn float_unification_error<'tcx>(a_is_expected: bool,
 401                                  v: (ast::FloatTy, ast::FloatTy))
 402                                  -> TypeError<'tcx>
 403 {
 404     let (a, b) = v;
 405     TypeError::FloatMismatch(ty::relate::expected_found_bool(a_is_expected, &a, &b))
 406 }