rustc_borrowck/
member_constraints.rs

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

rustc_borrowck/
member_constraints.rs
