src/librustc/middle/typeck/infer/higher_ranked/mod.rs

   1 // Copyright 2014 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  * Helper routines for higher-ranked things. See the `doc` module at
  13  * the end of the file for details.
  14  */
  15
  16 use middle::ty::{mod, Ty, replace_late_bound_regions};
  17 use middle::typeck::infer::{mod, combine, cres, InferCtxt};
  18 use middle::typeck::infer::combine::Combine;
  19 use middle::typeck::infer::region_inference::{RegionMark};
  20 use middle::ty_fold::{mod, HigherRankedFoldable, TypeFoldable};
  21 use syntax::codemap::Span;
  22 use util::nodemap::FnvHashMap;
  23 use util::ppaux::{bound_region_to_string, Repr};
  24
  25 pub trait HigherRankedCombineable<'tcx>: HigherRankedFoldable<'tcx> +
  26                                          TypeFoldable<'tcx> + Repr<'tcx> {
  27     fn super_combine<C:Combine<'tcx>>(combiner: &C, a: &Self, b: &Self) -> cres<'tcx, Self>;
  28 }
  29
  30 pub trait HigherRankedRelations<'tcx> {
  31     fn higher_ranked_sub<T>(&self, a: &T, b: &T) -> cres<'tcx, T>
  32         where T : HigherRankedCombineable<'tcx>;
  33
  34     fn higher_ranked_lub<T>(&self, a: &T, b: &T) -> cres<'tcx, T>
  35         where T : HigherRankedCombineable<'tcx>;
  36
  37     fn higher_ranked_glb<T>(&self, a: &T, b: &T) -> cres<'tcx, T>
  38         where T : HigherRankedCombineable<'tcx>;
  39 }
  40
  41 impl<'tcx,C> HigherRankedRelations<'tcx> for C
  42     where C : Combine<'tcx>
  43 {
  44     fn higher_ranked_sub<T>(&self, a: &T, b: &T) -> cres<'tcx, T>
  45         where T : HigherRankedCombineable<'tcx>
  46     {
  47         debug!("higher_ranked_sub(a={}, b={})",
  48                a.repr(self.tcx()), b.repr(self.tcx()));
  49
  50         // Rather than checking the subtype relationship between `a` and `b`
  51         // as-is, we need to do some extra work here in order to make sure
  52         // that function subtyping works correctly with respect to regions
  53         //
  54         // Note: this is a subtle algorithm.  For a full explanation,
  55         // please see the large comment at the end of the file in the (inlined) module
  56         // `doc`.
  57
  58         // Make a mark so we can examine "all bindings that were
  59         // created as part of this type comparison".
  60         let mark = self.infcx().region_vars.mark();
  61
  62         // First, we instantiate each bound region in the subtype with a fresh
  63         // region variable.
  64         let (a_prime, _) =
  65             self.infcx().replace_late_bound_regions_with_fresh_var(
  66                 self.trace().origin.span(),
  67                 infer::HigherRankedType,
  68                 a);
  69
  70         // Second, we instantiate each bound region in the supertype with a
  71         // fresh concrete region.
  72         let (b_prime, skol_map) = {
  73             replace_late_bound_regions(self.tcx(), b, |br, _| {
  74                 let skol = self.infcx().region_vars.new_skolemized(br);
  75                 debug!("Bound region {} skolemized to {}",
  76                        bound_region_to_string(self.tcx(), "", false, br),
  77                        skol);
  78                 skol
  79             })
  80         };
  81
  82         debug!("a_prime={}", a_prime.repr(self.tcx()));
  83         debug!("b_prime={}", b_prime.repr(self.tcx()));
  84
  85         // Compare types now that bound regions have been replaced.
  86         let result = try!(HigherRankedCombineable::super_combine(self, &a_prime, &b_prime));
  87
  88         // Presuming type comparison succeeds, we need to check
  89         // that the skolemized regions do not "leak".
  90         let new_vars =
  91             self.infcx().region_vars.vars_created_since_mark(mark);
  92         for (&skol_br, &skol) in skol_map.iter() {
  93             let tainted = self.infcx().region_vars.tainted(mark, skol);
  94             for tainted_region in tainted.iter() {
  95                 // Each skolemized should only be relatable to itself
  96                 // or new variables:
  97                 match *tainted_region {
  98                     ty::ReInfer(ty::ReVar(ref vid)) => {
  99                         if new_vars.iter().any(|x| x == vid) { continue; }
 100                     }
 101                     _ => {
 102                         if *tainted_region == skol { continue; }
 103                     }
 104                 };
 105
 106                 // A is not as polymorphic as B:
 107                 if self.a_is_expected() {
 108                     debug!("Not as polymorphic!");
 109                     return Err(ty::terr_regions_insufficiently_polymorphic(
 110                         skol_br, *tainted_region));
 111                 } else {
 112                     debug!("Overly polymorphic!");
 113                     return Err(ty::terr_regions_overly_polymorphic(
 114                         skol_br, *tainted_region));
 115                 }
 116             }
 117         }
 118
 119         debug!("higher_ranked_sub: OK result={}",
 120                result.repr(self.tcx()));
 121
 122         return Ok(result);
 123     }
 124
 125     fn higher_ranked_lub<T>(&self, a: &T, b: &T) -> cres<'tcx, T>
 126         where T : HigherRankedCombineable<'tcx>
 127     {
 128         // Make a mark so we can examine "all bindings that were
 129         // created as part of this type comparison".
 130         let mark = self.infcx().region_vars.mark();
 131
 132         // Instantiate each bound region with a fresh region variable.
 133         let span = self.trace().origin.span();
 134         let (a_with_fresh, a_map) =
 135             self.infcx().replace_late_bound_regions_with_fresh_var(
 136                 span, infer::HigherRankedType, a);
 137         let (b_with_fresh, _) =
 138             self.infcx().replace_late_bound_regions_with_fresh_var(
 139                 span, infer::HigherRankedType, b);
 140
 141         // Collect constraints.
 142         let result0 =
 143             try!(HigherRankedCombineable::super_combine(self, &a_with_fresh, &b_with_fresh));
 144         debug!("lub result0 = {}", result0.repr(self.tcx()));
 145
 146         // Generalize the regions appearing in result0 if possible
 147         let new_vars = self.infcx().region_vars.vars_created_since_mark(mark);
 148         let span = self.trace().origin.span();
 149         let result1 =
 150             fold_regions_in(
 151                 self.tcx(),
 152                 &result0,
 153                 |r, debruijn| generalize_region(self.infcx(), span, mark, debruijn,
 154                                                 new_vars.as_slice(), &a_map, r));
 155
 156         debug!("lub({},{}) = {}",
 157                a.repr(self.tcx()),
 158                b.repr(self.tcx()),
 159                result1.repr(self.tcx()));
 160
 161         return Ok(result1);
 162
 163         fn generalize_region(infcx: &InferCtxt,
 164                              span: Span,
 165                              mark: RegionMark,
 166                              debruijn: ty::DebruijnIndex,
 167                              new_vars: &[ty::RegionVid],
 168                              a_map: &FnvHashMap<ty::BoundRegion, ty::Region>,
 169                              r0: ty::Region)
 170                              -> ty::Region {
 171             // Regions that pre-dated the LUB computation stay as they are.
 172             if !is_var_in_set(new_vars, r0) {
 173                 assert!(!r0.is_bound());
 174                 debug!("generalize_region(r0={}): not new variable", r0);
 175                 return r0;
 176             }
 177
 178             let tainted = infcx.region_vars.tainted(mark, r0);
 179
 180             // Variables created during LUB computation which are
 181             // *related* to regions that pre-date the LUB computation
 182             // stay as they are.
 183             if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) {
 184                 debug!("generalize_region(r0={}): \
 185                         non-new-variables found in {}",
 186                        r0, tainted);
 187                 assert!(!r0.is_bound());
 188                 return r0;
 189             }
 190
 191             // Otherwise, the variable must be associated with at
 192             // least one of the variables representing bound regions
 193             // in both A and B.  Replace the variable with the "first"
 194             // bound region from A that we find it to be associated
 195             // with.
 196             for (a_br, a_r) in a_map.iter() {
 197                 if tainted.iter().any(|x| x == a_r) {
 198                     debug!("generalize_region(r0={}): \
 199                             replacing with {}, tainted={}",
 200                            r0, *a_br, tainted);
 201                     return ty::ReLateBound(debruijn, *a_br);
 202                 }
 203             }
 204
 205             infcx.tcx.sess.span_bug(
 206                 span,
 207                 format!("region {} is not associated with \
 208                          any bound region from A!",
 209                         r0).as_slice())
 210         }
 211     }
 212
 213     fn higher_ranked_glb<T>(&self, a: &T, b: &T) -> cres<'tcx, T>
 214         where T : HigherRankedCombineable<'tcx>
 215     {
 216         debug!("{}.higher_ranked_glb({}, {})",
 217                self.tag(), a.repr(self.tcx()), b.repr(self.tcx()));
 218
 219         // Make a mark so we can examine "all bindings that were
 220         // created as part of this type comparison".
 221         let mark = self.infcx().region_vars.mark();
 222
 223         // Instantiate each bound region with a fresh region variable.
 224         let (a_with_fresh, a_map) =
 225             self.infcx().replace_late_bound_regions_with_fresh_var(
 226                 self.trace().origin.span(), infer::HigherRankedType, a);
 227         let (b_with_fresh, b_map) =
 228             self.infcx().replace_late_bound_regions_with_fresh_var(
 229                 self.trace().origin.span(), infer::HigherRankedType, b);
 230         let a_vars = var_ids(self, &a_map);
 231         let b_vars = var_ids(self, &b_map);
 232
 233         // Collect constraints.
 234         let result0 =
 235             try!(HigherRankedCombineable::super_combine(self, &a_with_fresh, &b_with_fresh));
 236         debug!("glb result0 = {}", result0.repr(self.tcx()));
 237
 238         // Generalize the regions appearing in fn_ty0 if possible
 239         let new_vars = self.infcx().region_vars.vars_created_since_mark(mark);
 240         let span = self.trace().origin.span();
 241         let result1 =
 242             fold_regions_in(
 243                 self.tcx(),
 244                 &result0,
 245                 |r, debruijn| generalize_region(self.infcx(), span, mark, debruijn,
 246                                                 new_vars.as_slice(),
 247                                                 &a_map, a_vars.as_slice(), b_vars.as_slice(),
 248                                                 r));
 249
 250         debug!("glb({},{}) = {}",
 251                a.repr(self.tcx()),
 252                b.repr(self.tcx()),
 253                result1.repr(self.tcx()));
 254
 255         return Ok(result1);
 256
 257         fn generalize_region(infcx: &InferCtxt,
 258                              span: Span,
 259                              mark: RegionMark,
 260                              debruijn: ty::DebruijnIndex,
 261                              new_vars: &[ty::RegionVid],
 262                              a_map: &FnvHashMap<ty::BoundRegion, ty::Region>,
 263                              a_vars: &[ty::RegionVid],
 264                              b_vars: &[ty::RegionVid],
 265                              r0: ty::Region) -> ty::Region {
 266             if !is_var_in_set(new_vars, r0) {
 267                 assert!(!r0.is_bound());
 268                 return r0;
 269             }
 270
 271             let tainted = infcx.region_vars.tainted(mark, r0);
 272
 273             let mut a_r = None;
 274             let mut b_r = None;
 275             let mut only_new_vars = true;
 276             for r in tainted.iter() {
 277                 if is_var_in_set(a_vars, *r) {
 278                     if a_r.is_some() {
 279                         return fresh_bound_variable(infcx, debruijn);
 280                     } else {
 281                         a_r = Some(*r);
 282                     }
 283                 } else if is_var_in_set(b_vars, *r) {
 284                     if b_r.is_some() {
 285                         return fresh_bound_variable(infcx, debruijn);
 286                     } else {
 287                         b_r = Some(*r);
 288                     }
 289                 } else if !is_var_in_set(new_vars, *r) {
 290                     only_new_vars = false;
 291                 }
 292             }
 293
 294             // NB---I do not believe this algorithm computes
 295             // (necessarily) the GLB.  As written it can
 296             // spuriously fail. In particular, if there is a case
 297             // like: |fn(&a)| and fn(fn(&b)), where a and b are
 298             // free, it will return fn(&c) where c = GLB(a,b).  If
 299             // however this GLB is not defined, then the result is
 300             // an error, even though something like
 301             // "fn<X>(fn(&X))" where X is bound would be a
 302             // subtype of both of those.
 303             //
 304             // The problem is that if we were to return a bound
 305             // variable, we'd be computing a lower-bound, but not
 306             // necessarily the *greatest* lower-bound.
 307             //
 308             // Unfortunately, this problem is non-trivial to solve,
 309             // because we do not know at the time of computing the GLB
 310             // whether a GLB(a,b) exists or not, because we haven't
 311             // run region inference (or indeed, even fully computed
 312             // the region hierarchy!). The current algorithm seems to
 313             // works ok in practice.
 314
 315             if a_r.is_some() && b_r.is_some() && only_new_vars {
 316                 // Related to exactly one bound variable from each fn:
 317                 return rev_lookup(infcx, span, a_map, a_r.unwrap());
 318             } else if a_r.is_none() && b_r.is_none() {
 319                 // Not related to bound variables from either fn:
 320                 assert!(!r0.is_bound());
 321                 return r0;
 322             } else {
 323                 // Other:
 324                 return fresh_bound_variable(infcx, debruijn);
 325             }
 326         }
 327
 328         fn rev_lookup(infcx: &InferCtxt,
 329                       span: Span,
 330                       a_map: &FnvHashMap<ty::BoundRegion, ty::Region>,
 331                       r: ty::Region) -> ty::Region
 332         {
 333             for (a_br, a_r) in a_map.iter() {
 334                 if *a_r == r {
 335                     return ty::ReLateBound(ty::DebruijnIndex::new(1), *a_br);
 336                 }
 337             }
 338             infcx.tcx.sess.span_bug(
 339                 span,
 340                 format!("could not find original bound region for {}", r)[]);
 341         }
 342
 343         fn fresh_bound_variable(infcx: &InferCtxt, debruijn: ty::DebruijnIndex) -> ty::Region {
 344             infcx.region_vars.new_bound(debruijn)
 345         }
 346     }
 347 }
 348
 349 impl<'tcx> HigherRankedCombineable<'tcx> for ty::FnSig<'tcx> {
 350     fn super_combine<C:Combine<'tcx>>(combiner: &C, a: &ty::FnSig<'tcx>, b: &ty::FnSig<'tcx>)
 351                                       -> cres<'tcx, ty::FnSig<'tcx>>
 352     {
 353         if a.variadic != b.variadic {
 354             return Err(ty::terr_variadic_mismatch(
 355                 combine::expected_found(combiner, a.variadic, b.variadic)));
 356         }
 357
 358         let inputs = try!(argvecs(combiner,
 359                                   a.inputs.as_slice(),
 360                                   b.inputs.as_slice()));
 361
 362         let output = try!(match (a.output, b.output) {
 363             (ty::FnConverging(a_ty), ty::FnConverging(b_ty)) =>
 364                 Ok(ty::FnConverging(try!(combiner.tys(a_ty, b_ty)))),
 365             (ty::FnDiverging, ty::FnDiverging) =>
 366                 Ok(ty::FnDiverging),
 367             (a, b) =>
 368                 Err(ty::terr_convergence_mismatch(
 369                     combine::expected_found(combiner, a != ty::FnDiverging, b != ty::FnDiverging))),
 370         });
 371
 372         return Ok(ty::FnSig {inputs: inputs,
 373                              output: output,
 374                              variadic: a.variadic});
 375
 376
 377         fn argvecs<'tcx, C: Combine<'tcx>>(combiner: &C,
 378                                            a_args: &[Ty<'tcx>],
 379                                            b_args: &[Ty<'tcx>])
 380                                            -> cres<'tcx, Vec<Ty<'tcx>>>
 381         {
 382             if a_args.len() == b_args.len() {
 383                 a_args.iter().zip(b_args.iter())
 384                     .map(|(a, b)| combiner.args(*a, *b)).collect()
 385             } else {
 386                 Err(ty::terr_arg_count)
 387             }
 388         }
 389     }
 390 }
 391
 392 impl<'tcx> HigherRankedCombineable<'tcx> for ty::TraitRef<'tcx> {
 393     fn super_combine<C:Combine<'tcx>>(combiner: &C,
 394                                       a: &ty::TraitRef<'tcx>,
 395                                       b: &ty::TraitRef<'tcx>)
 396                                       -> cres<'tcx, ty::TraitRef<'tcx>>
 397     {
 398         // Different traits cannot be related
 399         if a.def_id != b.def_id {
 400             Err(ty::terr_traits(
 401                 combine::expected_found(combiner, a.def_id, b.def_id)))
 402         } else {
 403             let substs = try!(combiner.substs(a.def_id, &a.substs, &b.substs));
 404             Ok(ty::TraitRef { def_id: a.def_id,
 405                               substs: substs })
 406         }
 407     }
 408 }
 409
 410 fn var_ids<'tcx, T: Combine<'tcx>>(combiner: &T,
 411                                    map: &FnvHashMap<ty::BoundRegion, ty::Region>)
 412                                    -> Vec<ty::RegionVid> {
 413     map.iter().map(|(_, r)| match *r {
 414             ty::ReInfer(ty::ReVar(r)) => { r }
 415             r => {
 416                 combiner.infcx().tcx.sess.span_bug(
 417                     combiner.trace().origin.span(),
 418                     format!("found non-region-vid: {}", r).as_slice());
 419             }
 420         }).collect()
 421 }
 422
 423 fn is_var_in_set(new_vars: &[ty::RegionVid], r: ty::Region) -> bool {
 424     match r {
 425         ty::ReInfer(ty::ReVar(ref v)) => new_vars.iter().any(|x| x == v),
 426         _ => false
 427     }
 428 }
 429
 430 fn fold_regions_in<'tcx, T>(tcx: &ty::ctxt<'tcx>,
 431                             value: &T,
 432                             fldr: |ty::Region, ty::DebruijnIndex| -> ty::Region)
 433                             -> T
 434     where T: HigherRankedFoldable<'tcx>
 435 {
 436     value.fold_contents(&mut ty_fold::RegionFolder::new(tcx, |region, current_depth| {
 437         // we should only be encountering "escaping" late-bound regions here,
 438         // because the ones at the current level should have been replaced
 439         // with fresh variables
 440         assert!(match region {
 441             ty::ReLateBound(..) => false,
 442             _ => true
 443         });
 444
 445         fldr(region, ty::DebruijnIndex::new(current_depth))
 446     }))
 447 }
 448