rustc_infer/infer/
free_regions.rs

Help
1//! This module handles the relationships between "free regions", i.e., lifetime parameters.
2//! Ordinarily, free regions are unrelated to one another, but they can be related via implied
3//! or explicit bounds. In that case, we track the bounds using the `TransitiveRelation` type,
4//! and use that to decide when one free region outlives another, and so forth.
5
6use rustc_data_structures::transitive_relation::TransitiveRelation;
7use rustc_middle::ty::{Region, TyCtxt};
8use tracing::debug;
9
10/// Combines a `FreeRegionMap` and a `TyCtxt`.
11///
12/// This stuff is a bit convoluted and should be refactored, but as we
13/// transition to NLL, it'll all go away anyhow.
14pub(crate) struct RegionRelations<'a, 'tcx> {
15    pub tcx: TyCtxt<'tcx>,
16
17    /// Free-region relationships.
18    pub free_regions: &'a FreeRegionMap<'tcx>,
19}
20
21impl<'a, 'tcx> RegionRelations<'a, 'tcx> {
22    pub(crate) fn new(tcx: TyCtxt<'tcx>, free_regions: &'a FreeRegionMap<'tcx>) -> Self {
23        Self { tcx, free_regions }
24    }
25
26    pub(crate) fn lub_param_regions(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> Region<'tcx> {
27        self.free_regions.lub_param_regions(self.tcx, r_a, r_b)
28    }
29}
30
31#[derive(Clone, Debug)]
32pub struct FreeRegionMap<'tcx> {
33    /// Stores the relation `a < b`, where `a` and `b` are regions.
34    ///
35    /// Invariant: only free regions like `'x` or `'static` are stored
36    /// in this relation, not scopes.
37    pub(crate) relation: TransitiveRelation<Region<'tcx>>,
38}
39
40impl<'tcx> FreeRegionMap<'tcx> {
41    pub fn elements(&self) -> impl Iterator<Item = Region<'tcx>> + '_ {
42        self.relation.elements().copied()
43    }
44
45    pub fn is_empty(&self) -> bool {
46        self.relation.is_empty()
47    }
48
49    /// Tests whether `r_a <= r_b`.
50    ///
51    /// Both regions must meet `is_free_or_static`.
52    ///
53    /// Subtle: one tricky case that this code gets correct is as
54    /// follows. If we know that `r_b: 'static`, then this function
55    /// will return true, even though we don't know anything that
56    /// directly relates `r_a` and `r_b`.
57    pub fn sub_free_regions(
58        &self,
59        tcx: TyCtxt<'tcx>,
60        r_a: Region<'tcx>,
61        r_b: Region<'tcx>,
62    ) -> bool {
63        assert!(r_a.is_free() && r_b.is_free());
64        let re_static = tcx.lifetimes.re_static;
65        if self.check_relation(re_static, r_b) {
66            // `'a <= 'static` is always true, and not stored in the
67            // relation explicitly, so check if `'b` is `'static` (or
68            // equivalent to it)
69            true
70        } else {
71            self.check_relation(r_a, r_b)
72        }
73    }
74
75    /// Check whether `r_a <= r_b` is found in the relation.
76    fn check_relation(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool {
77        r_a == r_b || self.relation.contains(r_a, r_b)
78    }
79
80    /// Computes the least-upper-bound of two free regions. In some
81    /// cases, this is more conservative than necessary, in order to
82    /// avoid making arbitrary choices. See
83    /// `TransitiveRelation::postdom_upper_bound` for more details.
84    pub(crate) fn lub_param_regions(
85        &self,
86        tcx: TyCtxt<'tcx>,
87        r_a: Region<'tcx>,
88        r_b: Region<'tcx>,
89    ) -> Region<'tcx> {
90        debug!("lub_param_regions(r_a={:?}, r_b={:?})", r_a, r_b);
91        assert!(r_a.is_param());
92        assert!(r_b.is_param());
93        let result = if r_a == r_b {
94            r_a
95        } else {
96            match self.relation.postdom_upper_bound(r_a, r_b) {
97                None => tcx.lifetimes.re_static,
98                Some(r) => r,
99            }
100        };
101        debug!("lub_param_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
102        result
103    }
104}
rustc_infer/infer/free_regions.rs

rustc_infer/infer/
free_regions.rs
