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