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 handles the relationships between free regions --
  12 //! meaning lifetime parameters. Ordinarily, free regions are
  13 //! unrelated to one another, but they can be related via implied or
  14 //! explicit bounds.  In that case, we track the bounds using the
  15 //! `TransitiveRelation` type and use that to decide when one free
  16 //! region outlives another and so forth.
  17
  18 use ty::{self, Lift, TyCtxt, Region};
  19 use ty::wf::ImpliedBound;
  20 use rustc_data_structures::transitive_relation::TransitiveRelation;
  21
  22 #[derive(Clone, RustcEncodable, RustcDecodable)]
  23 pub struct FreeRegionMap<'tcx> {
  24     // Stores the relation `a < b`, where `a` and `b` are regions.
  25     //
  26     // Invariant: only free regions like `'x` or `'static` are stored
  27     // in this relation, not scopes.
  28     relation: TransitiveRelation<Region<'tcx>>
  29 }
  30
  31 impl<'tcx> FreeRegionMap<'tcx> {
  32     pub fn new() -> Self {
  33         FreeRegionMap { relation: TransitiveRelation::new() }
  34     }
  35
  36     pub fn is_empty(&self) -> bool {
  37         self.relation.is_empty()
  38     }
  39
  40     pub fn relate_free_regions_from_implied_bounds(&mut self,
  41                                                    implied_bounds: &[ImpliedBound<'tcx>])
  42     {
  43         debug!("relate_free_regions_from_implied_bounds()");
  44         for implied_bound in implied_bounds {
  45             debug!("implied bound: {:?}", implied_bound);
  46             match *implied_bound {
  47                 ImpliedBound::RegionSubRegion(a @ &ty::ReFree(_), b @ &ty::ReFree(_)) |
  48                 ImpliedBound::RegionSubRegion(a @ &ty::ReStatic, b @ &ty::ReFree(_)) => {
  49                     self.relate_regions(a, b);
  50                 }
  51                 ImpliedBound::RegionSubRegion(..) |
  52                 ImpliedBound::RegionSubParam(..) |
  53                 ImpliedBound::RegionSubProjection(..) => {
  54                 }
  55             }
  56         }
  57     }
  58
  59     pub fn relate_free_regions_from_predicates(&mut self,
  60                                                predicates: &[ty::Predicate<'tcx>]) {
  61         debug!("relate_free_regions_from_predicates(predicates={:?})", predicates);
  62         for predicate in predicates {
  63             match *predicate {
  64                 ty::Predicate::Projection(..) |
  65                 ty::Predicate::Trait(..) |
  66                 ty::Predicate::Equate(..) |
  67                 ty::Predicate::Subtype(..) |
  68                 ty::Predicate::WellFormed(..) |
  69                 ty::Predicate::ObjectSafe(..) |
  70                 ty::Predicate::ClosureKind(..) |
  71                 ty::Predicate::TypeOutlives(..) => {
  72                     // No region bounds here
  73                 }
  74                 ty::Predicate::RegionOutlives(ty::Binder(ty::OutlivesPredicate(r_a, r_b))) => {
  75                     match (r_a, r_b) {
  76                         // `'static: 'x` is not notable
  77                         (&ty::ReStatic, &ty::ReFree(_)) => {},
  78
  79                         (&ty::ReFree(_), &ty::ReStatic) |
  80                         (&ty::ReFree(_), &ty::ReFree(_)) => {
  81                             // Record that `'a:'b`. Or, put another way, `'b <= 'a`.
  82                             self.relate_regions(r_b, r_a);
  83                         }
  84
  85                         _ => {
  86                             // All named regions are instantiated with free regions.
  87                             bug!("record_region_bounds: non free region: {:?} / {:?}",
  88                                  r_a,
  89                                  r_b);
  90                         }
  91                     }
  92                 }
  93             }
  94         }
  95     }
  96
  97     fn relate_regions(&mut self, sub: Region<'tcx>, sup: Region<'tcx>) {
  98         assert!(match *sub { ty::ReFree(_) | ty::ReStatic => true, _ => false });
  99         assert!(match *sup { ty::ReFree(_) | ty::ReStatic => true, _ => false });
 100         self.relation.add(sub, sup)
 101     }
 102
 103     pub fn lub_free_regions<'a, 'gcx>(&self,
 104                                       tcx: TyCtxt<'a, 'gcx, 'tcx>,
 105                                       r_a: Region<'tcx>,
 106                                       r_b: Region<'tcx>)
 107                                       -> Region<'tcx> {
 108         assert!(match *r_a { ty::ReFree(_) => true, _ => false });
 109         assert!(match *r_b { ty::ReFree(_) => true, _ => false });
 110         let result = if r_a == r_b { r_a } else {
 111             match self.relation.postdom_upper_bound(&r_a, &r_b) {
 112                 None => tcx.mk_region(ty::ReStatic),
 113                 Some(r) => *r,
 114             }
 115         };
 116         debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
 117         result
 118     }
 119
 120     /// Determines whether one region is a subregion of another.  This is intended to run *after
 121     /// inference* and sadly the logic is somewhat duplicated with the code in infer.rs.
 122     pub fn is_subregion_of<'a, 'gcx>(&self,
 123                                      tcx: TyCtxt<'a, 'gcx, 'tcx>,
 124                                      sub_region: ty::Region<'tcx>,
 125                                      super_region: ty::Region<'tcx>)
 126                                      -> bool {
 127         let result = sub_region == super_region || {
 128             match (sub_region, super_region) {
 129                 (&ty::ReEmpty, _) |
 130                 (_, &ty::ReStatic) =>
 131                     true,
 132
 133                 (&ty::ReScope(sub_scope), &ty::ReScope(super_scope)) =>
 134                     tcx.region_maps().is_subscope_of(sub_scope, super_scope),
 135
 136                 (&ty::ReScope(sub_scope), &ty::ReFree(fr)) => {
 137                     // 1. It is safe to unwrap `fr.scope` because we
 138                     // should only ever wind up comparing against
 139                     // `ReScope` in the context of a method or
 140                     // body, where `fr.scope` should be `Some`.
 141                     tcx.region_maps().is_subscope_of(sub_scope, fr.scope.unwrap() /*1*/) ||
 142                         self.is_static(tcx, super_region)
 143                 }
 144
 145                 (&ty::ReFree(_), &ty::ReFree(_)) =>
 146                     self.relation.contains(&sub_region, &super_region) ||
 147                         self.is_static(tcx, super_region),
 148
 149                 (&ty::ReStatic, &ty::ReFree(_)) =>
 150                     self.is_static(tcx, super_region),
 151
 152                 _ =>
 153                     false,
 154             }
 155         };
 156         debug!("is_subregion_of(sub_region={:?}, super_region={:?}) = {:?}",
 157                sub_region, super_region, result);
 158         result
 159     }
 160
 161     /// Determines whether this free-region is required to be 'static
 162     fn is_static<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, super_region: ty::Region<'tcx>)
 163                            -> bool {
 164         debug!("is_static(super_region={:?})", super_region);
 165         match *super_region {
 166             ty::ReStatic => true,
 167             ty::ReFree(_) => {
 168                 let re_static = tcx.mk_region(ty::ReStatic);
 169                 self.relation.contains(&re_static, &super_region)
 170             }
 171             _ => bug!("only free regions should be given to `is_static`")
 172         }
 173     }
 174 }
 175
 176 impl_stable_hash_for!(struct FreeRegionMap<'tcx> {
 177     relation
 178 });
 179
 180 impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> {
 181     type Lifted = FreeRegionMap<'tcx>;
 182     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<FreeRegionMap<'tcx>> {
 183         self.relation.maybe_map(|&fr| fr.lift_to_tcx(tcx))
 184                      .map(|relation| FreeRegionMap { relation })
 185     }
 186 }