src/librustc/middle/free_region.rs

   1 // Copyright 2012-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 //! This file defines
  12
  13 use middle::implicator::Implication;
  14 use middle::ty::{self, FreeRegion};
  15 use util::common::can_reach;
  16 use util::nodemap::FnvHashMap;
  17 use util::ppaux::Repr;
  18
  19 #[derive(Clone)]
  20 pub struct FreeRegionMap {
  21     /// `free_region_map` maps from a free region `a` to a list of
  22     /// free regions `bs` such that `a <= b for all b in bs`
  23     map: FnvHashMap<FreeRegion, Vec<FreeRegion>>,
  24 }
  25
  26 impl FreeRegionMap {
  27     pub fn new() -> FreeRegionMap {
  28         FreeRegionMap { map: FnvHashMap() }
  29     }
  30
  31     pub fn relate_free_regions_from_implications<'tcx>(&mut self,
  32                                                        tcx: &ty::ctxt<'tcx>,
  33                                                        implications: &[Implication<'tcx>])
  34     {
  35         for implication in implications {
  36             debug!("implication: {}", implication.repr(tcx));
  37             match *implication {
  38                 Implication::RegionSubRegion(_, ty::ReFree(free_a), ty::ReFree(free_b)) => {
  39                     self.relate_free_regions(free_a, free_b);
  40                 }
  41                 Implication::RegionSubRegion(..) |
  42                 Implication::RegionSubClosure(..) |
  43                 Implication::RegionSubGeneric(..) |
  44                 Implication::Predicate(..) => {
  45                 }
  46             }
  47         }
  48     }
  49
  50     pub fn relate_free_regions_from_predicates<'tcx>(&mut self,
  51                                                      tcx: &ty::ctxt<'tcx>,
  52                                                      predicates: &[ty::Predicate<'tcx>]) {
  53         debug!("relate_free_regions_from_predicates(predicates={})", predicates.repr(tcx));
  54         for predicate in predicates {
  55             match *predicate {
  56                 ty::Predicate::Projection(..) |
  57                 ty::Predicate::Trait(..) |
  58                 ty::Predicate::Equate(..) |
  59                 ty::Predicate::TypeOutlives(..) => {
  60                     // No region bounds here
  61                 }
  62                 ty::Predicate::RegionOutlives(ty::Binder(ty::OutlivesPredicate(r_a, r_b))) => {
  63                     match (r_a, r_b) {
  64                         (ty::ReFree(fr_a), ty::ReFree(fr_b)) => {
  65                             // Record that `'a:'b`. Or, put another way, `'b <= 'a`.
  66                             self.relate_free_regions(fr_b, fr_a);
  67                         }
  68                         _ => {
  69                             // All named regions are instantiated with free regions.
  70                             tcx.sess.bug(
  71                                 &format!("record_region_bounds: non free region: {} / {}",
  72                                          r_a.repr(tcx),
  73                                          r_b.repr(tcx)));
  74                         }
  75                     }
  76                 }
  77             }
  78         }
  79     }
  80
  81     pub fn relate_free_regions(&mut self, sub: FreeRegion, sup: FreeRegion) {
  82         let mut sups = self.map.entry(sub).or_insert(Vec::new());
  83         if !sups.contains(&sup) {
  84             sups.push(sup);
  85         }
  86     }
  87
  88     /// Determines whether two free regions have a subregion relationship
  89     /// by walking the graph encoded in `map`.  Note that
  90     /// it is possible that `sub != sup` and `sub <= sup` and `sup <= sub`
  91     /// (that is, the user can give two different names to the same lifetime).
  92     pub fn sub_free_region(&self, sub: FreeRegion, sup: FreeRegion) -> bool {
  93         can_reach(&self.map, sub, sup)
  94     }
  95
  96     /// Determines whether one region is a subregion of another.  This is intended to run *after
  97     /// inference* and sadly the logic is somewhat duplicated with the code in infer.rs.
  98     pub fn is_subregion_of(&self,
  99                            tcx: &ty::ctxt,
 100                            sub_region: ty::Region,
 101                            super_region: ty::Region)
 102                            -> bool {
 103         debug!("is_subregion_of(sub_region={:?}, super_region={:?})",
 104                sub_region, super_region);
 105
 106         sub_region == super_region || {
 107             match (sub_region, super_region) {
 108                 (ty::ReEmpty, _) |
 109                 (_, ty::ReStatic) =>
 110                     true,
 111
 112                 (ty::ReScope(sub_scope), ty::ReScope(super_scope)) =>
 113                     tcx.region_maps.is_subscope_of(sub_scope, super_scope),
 114
 115                 (ty::ReScope(sub_scope), ty::ReFree(ref fr)) =>
 116                     tcx.region_maps.is_subscope_of(sub_scope, fr.scope.to_code_extent()),
 117
 118                 (ty::ReFree(sub_fr), ty::ReFree(super_fr)) =>
 119                     self.sub_free_region(sub_fr, super_fr),
 120
 121                 _ =>
 122                     false,
 123             }
 124         }
 125     }
 126 }
 127