1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

//! This module handles the relationships between "free regions", i.e., lifetime parameters.
//! Ordinarily, free regions are unrelated to one another, but they can be related via implied
//! or explicit bounds. In that case, we track the bounds using the `TransitiveRelation` type,
//! and use that to decide when one free region outlives another, and so forth.

use rustc_data_structures::transitive_relation::TransitiveRelation;
use rustc_middle::ty::{Lift, Region, TyCtxt};

/// Combines a `FreeRegionMap` and a `TyCtxt`.
///
/// This stuff is a bit convoluted and should be refactored, but as we
/// transition to NLL, it'll all go away anyhow.
pub(crate) struct RegionRelations<'a, 'tcx> {
    pub tcx: TyCtxt<'tcx>,

    /// Free-region relationships.
    pub free_regions: &'a FreeRegionMap<'tcx>,
}

impl<'a, 'tcx> RegionRelations<'a, 'tcx> {
    pub fn new(tcx: TyCtxt<'tcx>, free_regions: &'a FreeRegionMap<'tcx>) -> Self {
        Self { tcx, free_regions }
    }

    pub fn lub_free_regions(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> Region<'tcx> {
        self.free_regions.lub_free_regions(self.tcx, r_a, r_b)
    }
}

#[derive(Clone, Debug)]
pub struct FreeRegionMap<'tcx> {
    /// Stores the relation `a < b`, where `a` and `b` are regions.
    ///
    /// Invariant: only free regions like `'x` or `'static` are stored
    /// in this relation, not scopes.
    pub(crate) relation: TransitiveRelation<Region<'tcx>>,
}

impl<'tcx> FreeRegionMap<'tcx> {
    pub fn elements(&self) -> impl Iterator<Item = Region<'tcx>> + '_ {
        self.relation.elements().copied()
    }

    pub fn is_empty(&self) -> bool {
        self.relation.is_empty()
    }

    /// Tests whether `r_a <= r_b`.
    ///
    /// Both regions must meet `is_free_or_static`.
    ///
    /// Subtle: one tricky case that this code gets correct is as
    /// follows. If we know that `r_b: 'static`, then this function
    /// will return true, even though we don't know anything that
    /// directly relates `r_a` and `r_b`.
    pub fn sub_free_regions(
        &self,
        tcx: TyCtxt<'tcx>,
        r_a: Region<'tcx>,
        r_b: Region<'tcx>,
    ) -> bool {
        assert!(r_a.is_free_or_static() && r_b.is_free_or_static());
        let re_static = tcx.lifetimes.re_static;
        if self.check_relation(re_static, r_b) {
            // `'a <= 'static` is always true, and not stored in the
            // relation explicitly, so check if `'b` is `'static` (or
            // equivalent to it)
            true
        } else {
            self.check_relation(r_a, r_b)
        }
    }

    /// Check whether `r_a <= r_b` is found in the relation.
    fn check_relation(&self, r_a: Region<'tcx>, r_b: Region<'tcx>) -> bool {
        r_a == r_b || self.relation.contains(r_a, r_b)
    }

    /// Computes the least-upper-bound of two free regions. In some
    /// cases, this is more conservative than necessary, in order to
    /// avoid making arbitrary choices. See
    /// `TransitiveRelation::postdom_upper_bound` for more details.
    pub fn lub_free_regions(
        &self,
        tcx: TyCtxt<'tcx>,
        r_a: Region<'tcx>,
        r_b: Region<'tcx>,
    ) -> Region<'tcx> {
        debug!("lub_free_regions(r_a={:?}, r_b={:?})", r_a, r_b);
        assert!(r_a.is_free());
        assert!(r_b.is_free());
        let result = if r_a == r_b {
            r_a
        } else {
            match self.relation.postdom_upper_bound(r_a, r_b) {
                None => tcx.lifetimes.re_static,
                Some(r) => r,
            }
        };
        debug!("lub_free_regions(r_a={:?}, r_b={:?}) = {:?}", r_a, r_b, result);
        result
    }
}

impl<'a, 'tcx> Lift<'tcx> for FreeRegionMap<'a> {
    type Lifted = FreeRegionMap<'tcx>;
    fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<FreeRegionMap<'tcx>> {
        self.relation.maybe_map(|fr| tcx.lift(fr)).map(|relation| FreeRegionMap { relation })
    }
}