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