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.
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.
11 use ty::{self, Lift, TyCtxt, Region};
12 use rustc_data_structures::transitive_relation::TransitiveRelation;
14 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
15 pub struct FreeRegionMap<'tcx> {
16 // Stores the relation `a < b`, where `a` and `b` are regions.
18 // Invariant: only free regions like `'x` or `'static` are stored
19 // in this relation, not scopes.
20 relation: TransitiveRelation<Region<'tcx>>
23 impl<'tcx> FreeRegionMap<'tcx> {
24 pub fn new() -> Self {
25 FreeRegionMap { relation: TransitiveRelation::new() }
28 pub fn is_empty(&self) -> bool {
29 self.relation.is_empty()
32 // Record that `'sup:'sub`. Or, put another way, `'sub <= 'sup`.
33 // (with the exception that `'static: 'x` is not notable)
34 pub fn relate_regions(&mut self, sub: Region<'tcx>, sup: Region<'tcx>) {
35 debug!("relate_regions(sub={:?}, sup={:?})", sub, sup);
36 if is_free_or_static(sub) && is_free(sup) {
37 self.relation.add(sub, sup)
41 /// Compute the least-upper-bound of two free regions. In some
42 /// cases, this is more conservative than necessary, in order to
43 /// avoid making arbitrary choices. See
44 /// `TransitiveRelation::postdom_upper_bound` for more details.
45 pub fn lub_free_regions<'a, 'gcx>(&self,
46 tcx: TyCtxt<'a, 'gcx, 'tcx>,
50 debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b);
51 assert!(is_free(r_a));
52 assert!(is_free(r_b));
53 let result = if r_a == r_b { r_a } else {
54 match self.relation.postdom_upper_bound(&r_a, &r_b) {
55 None => tcx.mk_region(ty::ReStatic),
59 debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
64 /// The NLL region handling code represents free region relations in a
65 /// slightly different way; this trait allows functions to be abstract
66 /// over which version is in use.
67 pub trait FreeRegionRelations<'tcx> {
68 /// Tests whether `r_a <= r_b`. Both must be free regions or
70 fn sub_free_regions(&self, shorter: ty::Region<'tcx>, longer: ty::Region<'tcx>) -> bool;
73 impl<'tcx> FreeRegionRelations<'tcx> for FreeRegionMap<'tcx> {
74 fn sub_free_regions(&self,
78 assert!(is_free_or_static(r_a) && is_free_or_static(r_b));
79 if let ty::ReStatic = r_b {
80 true // `'a <= 'static` is just always true, and not stored in the relation explicitly
82 r_a == r_b || self.relation.contains(&r_a, &r_b)
87 fn is_free(r: Region) -> bool {
89 ty::ReEarlyBound(_) | ty::ReFree(_) => true,
94 fn is_free_or_static(r: Region) -> bool {
101 impl_stable_hash_for!(struct FreeRegionMap<'tcx> {
105 impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> {
106 type Lifted = FreeRegionMap<'tcx>;
107 fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<FreeRegionMap<'tcx>> {
108 self.relation.maybe_map(|&fr| fr.lift_to_tcx(tcx))
109 .map(|relation| FreeRegionMap { relation })