rustc_borrowck/
member_constraints.rs

Help
1use std::hash::Hash;
2use std::ops::Index;
3
4use rustc_data_structures::captures::Captures;
5use rustc_data_structures::fx::FxIndexMap;
6use rustc_index::{IndexSlice, IndexVec};
7use rustc_middle::ty::{self, Ty};
8use rustc_span::Span;
9use tracing::instrument;
10
11/// Compactly stores a set of `R0 member of [R1...Rn]` constraints,
12/// indexed by the region `R0`.
13#[derive(Debug)]
14pub(crate) struct MemberConstraintSet<'tcx, R>
15where
16    R: Copy + Eq,
17{
18    /// Stores the first "member" constraint for a given `R0`. This is an
19    /// index into the `constraints` vector below.
20    first_constraints: FxIndexMap<R, NllMemberConstraintIndex>,
21
22    /// Stores the data about each `R0 member of [R1..Rn]` constraint.
23    /// These are organized into a linked list, so each constraint
24    /// contains the index of the next constraint with the same `R0`.
25    constraints: IndexVec<NllMemberConstraintIndex, MemberConstraint<'tcx>>,
26
27    /// Stores the `R1..Rn` regions for *all* sets. For any given
28    /// constraint, we keep two indices so that we can pull out a
29    /// slice.
30    choice_regions: Vec<ty::RegionVid>,
31}
32
33/// Represents a `R0 member of [R1..Rn]` constraint
34#[derive(Debug)]
35pub(crate) struct MemberConstraint<'tcx> {
36    next_constraint: Option<NllMemberConstraintIndex>,
37
38    /// The span where the hidden type was instantiated.
39    pub(crate) definition_span: Span,
40
41    /// The hidden type in which `R0` appears. (Used in error reporting.)
42    pub(crate) hidden_ty: Ty<'tcx>,
43
44    pub(crate) key: ty::OpaqueTypeKey<'tcx>,
45
46    /// The region `R0`.
47    pub(crate) member_region_vid: ty::RegionVid,
48
49    /// Index of `R1` in `choice_regions` vector from `MemberConstraintSet`.
50    start_index: usize,
51
52    /// Index of `Rn` in `choice_regions` vector from `MemberConstraintSet`.
53    end_index: usize,
54}
55
56rustc_index::newtype_index! {
57    #[debug_format = "MemberConstraintIndex({})"]
58    pub(crate) struct NllMemberConstraintIndex {}
59}
60
61impl Default for MemberConstraintSet<'_, ty::RegionVid> {
62    fn default() -> Self {
63        Self {
64            first_constraints: Default::default(),
65            constraints: Default::default(),
66            choice_regions: Default::default(),
67        }
68    }
69}
70
71impl<'tcx> MemberConstraintSet<'tcx, ty::RegionVid> {
72    pub(crate) fn is_empty(&self) -> bool {
73        self.constraints.is_empty()
74    }
75
76    /// Pushes a member constraint into the set.
77    #[instrument(level = "debug", skip(self))]
78    pub(crate) fn add_member_constraint(
79        &mut self,
80        key: ty::OpaqueTypeKey<'tcx>,
81        hidden_ty: Ty<'tcx>,
82        definition_span: Span,
83        member_region_vid: ty::RegionVid,
84        choice_regions: &[ty::RegionVid],
85    ) {
86        let next_constraint = self.first_constraints.get(&member_region_vid).cloned();
87        let start_index = self.choice_regions.len();
88        self.choice_regions.extend(choice_regions);
89        let end_index = self.choice_regions.len();
90        let constraint_index = self.constraints.push(MemberConstraint {
91            next_constraint,
92            member_region_vid,
93            definition_span,
94            hidden_ty,
95            key,
96            start_index,
97            end_index,
98        });
99        self.first_constraints.insert(member_region_vid, constraint_index);
100    }
101}
102
103impl<'tcx, R1> MemberConstraintSet<'tcx, R1>
104where
105    R1: Copy + Hash + Eq,
106{
107    /// Remap the "member region" key using `map_fn`, producing a new
108    /// member constraint set. This is used in the NLL code to map from
109    /// the original `RegionVid` to an scc index. In some cases, we
110    /// may have multiple `R1` values mapping to the same `R2` key -- that
111    /// is ok, the two sets will be merged.
112    pub(crate) fn into_mapped<R2>(
113        self,
114        mut map_fn: impl FnMut(R1) -> R2,
115    ) -> MemberConstraintSet<'tcx, R2>
116    where
117        R2: Copy + Hash + Eq,
118    {
119        // We can re-use most of the original data, just tweaking the
120        // linked list links a bit.
121        //
122        // For example if we had two keys `Ra` and `Rb` that both now
123        // wind up mapped to the same key `S`, we would append the
124        // linked list for `Ra` onto the end of the linked list for
125        // `Rb` (or vice versa) -- this basically just requires
126        // rewriting the final link from one list to point at the other
127        // other (see `append_list`).
128
129        let MemberConstraintSet { first_constraints, mut constraints, choice_regions } = self;
130
131        let mut first_constraints2 = FxIndexMap::default();
132        first_constraints2.reserve(first_constraints.len());
133
134        for (r1, start1) in first_constraints {
135            let r2 = map_fn(r1);
136            if let Some(&start2) = first_constraints2.get(&r2) {
137                append_list(&mut constraints, start1, start2);
138            }
139            first_constraints2.insert(r2, start1);
140        }
141
142        MemberConstraintSet { first_constraints: first_constraints2, constraints, choice_regions }
143    }
144}
145
146impl<'tcx, R> MemberConstraintSet<'tcx, R>
147where
148    R: Copy + Hash + Eq,
149{
150    pub(crate) fn all_indices(
151        &self,
152    ) -> impl Iterator<Item = NllMemberConstraintIndex> + Captures<'tcx> + '_ {
153        self.constraints.indices()
154    }
155
156    /// Iterate down the constraint indices associated with a given
157    /// peek-region. You can then use `choice_regions` and other
158    /// methods to access data.
159    pub(crate) fn indices(
160        &self,
161        member_region_vid: R,
162    ) -> impl Iterator<Item = NllMemberConstraintIndex> + Captures<'tcx> + '_ {
163        let mut next = self.first_constraints.get(&member_region_vid).cloned();
164        std::iter::from_fn(move || -> Option<NllMemberConstraintIndex> {
165            if let Some(current) = next {
166                next = self.constraints[current].next_constraint;
167                Some(current)
168            } else {
169                None
170            }
171        })
172    }
173
174    /// Returns the "choice regions" for a given member
175    /// constraint. This is the `R1..Rn` from a constraint like:
176    ///
177    /// ```text
178    /// R0 member of [R1..Rn]
179    /// ```
180    pub(crate) fn choice_regions(&self, pci: NllMemberConstraintIndex) -> &[ty::RegionVid] {
181        let MemberConstraint { start_index, end_index, .. } = &self.constraints[pci];
182        &self.choice_regions[*start_index..*end_index]
183    }
184}
185
186impl<'tcx, R> Index<NllMemberConstraintIndex> for MemberConstraintSet<'tcx, R>
187where
188    R: Copy + Eq,
189{
190    type Output = MemberConstraint<'tcx>;
191
192    fn index(&self, i: NllMemberConstraintIndex) -> &MemberConstraint<'tcx> {
193        &self.constraints[i]
194    }
195}
196
197/// Given a linked list starting at `source_list` and another linked
198/// list starting at `target_list`, modify `target_list` so that it is
199/// followed by `source_list`.
200///
201/// Before:
202///
203/// ```text
204/// target_list: A -> B -> C -> (None)
205/// source_list: D -> E -> F -> (None)
206/// ```
207///
208/// After:
209///
210/// ```text
211/// target_list: A -> B -> C -> D -> E -> F -> (None)
212/// ```
213fn append_list(
214    constraints: &mut IndexSlice<NllMemberConstraintIndex, MemberConstraint<'_>>,
215    target_list: NllMemberConstraintIndex,
216    source_list: NllMemberConstraintIndex,
217) {
218    let mut p = target_list;
219    loop {
220        let r = &mut constraints[p];
221        match r.next_constraint {
222            Some(q) => p = q,
223            None => {
224                r.next_constraint = Some(source_list);
225                return;
226            }
227        }
228    }
229}
rustc_borrowck/member_constraints.rs

rustc_borrowck/
member_constraints.rs
