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