1 #![deny(rustc::untranslatable_diagnostic)]
2 #![deny(rustc::diagnostic_outside_of_impl)]
3 use rustc_data_structures::captures::Captures;
4 use rustc_data_structures::fx::FxHashMap;
5 use rustc_index::vec::IndexVec;
6 use rustc_middle::infer::MemberConstraint;
7 use rustc_middle::ty::{self, Ty};
12 /// Compactly stores a set of `R0 member of [R1...Rn]` constraints,
13 /// indexed by the region `R0`.
15 pub(crate) struct MemberConstraintSet<'tcx, R>
19 /// Stores the first "member" constraint for a given `R0`. This is an
20 /// index into the `constraints` vector below.
21 first_constraints: FxHashMap<R, NllMemberConstraintIndex>,
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>>,
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
31 choice_regions: Vec<ty::RegionVid>,
34 /// Represents a `R0 member of [R1..Rn]` constraint
36 pub(crate) struct NllMemberConstraint<'tcx> {
37 next_constraint: Option<NllMemberConstraintIndex>,
39 /// The span where the hidden type was instantiated.
40 pub(crate) definition_span: Span,
42 /// The hidden type in which `R0` appears. (Used in error reporting.)
43 pub(crate) hidden_ty: Ty<'tcx>,
45 pub(crate) key: ty::OpaqueTypeKey<'tcx>,
48 pub(crate) member_region_vid: ty::RegionVid,
50 /// Index of `R1` in `choice_regions` vector from `MemberConstraintSet`.
53 /// Index of `Rn` in `choice_regions` vector from `MemberConstraintSet`.
57 rustc_index::newtype_index! {
58 #[debug_format = "MemberConstraintIndex({})"]
59 pub(crate) struct NllMemberConstraintIndex {}
62 impl Default for MemberConstraintSet<'_, ty::RegionVid> {
63 fn default() -> Self {
65 first_constraints: Default::default(),
66 constraints: Default::default(),
67 choice_regions: Default::default(),
72 impl<'tcx> MemberConstraintSet<'tcx, ty::RegionVid> {
73 /// Pushes a member constraint into the set.
75 /// The input member constraint `m_c` is in the form produced by
76 /// the `rustc_middle::infer` code.
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).
82 pub(crate) fn push_constraint(
84 m_c: &MemberConstraint<'tcx>,
85 mut to_region_vid: impl FnMut(ty::Region<'tcx>) -> ty::RegionVid,
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 {
96 definition_span: m_c.definition_span,
97 hidden_ty: m_c.hidden_ty,
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)));
107 impl<'tcx, R1> MemberConstraintSet<'tcx, R1>
109 R1: Copy + Hash + Eq,
111 /// Remap the "member region" key using `map_fn`, producing a new
112 /// member constraint set. This is used in the NLL code to map from
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.
116 pub(crate) fn into_mapped<R2>(
118 mut map_fn: impl FnMut(R1) -> R2,
119 ) -> MemberConstraintSet<'tcx, R2>
121 R2: Copy + Hash + Eq,
123 // We can re-use most of the original data, just tweaking the
124 // linked list links a bit.
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
130 // rewriting the final link from one list to point at the other
131 // other (see `append_list`).
133 let MemberConstraintSet { first_constraints, mut constraints, choice_regions } = self;
135 let mut first_constraints2 = FxHashMap::default();
136 first_constraints2.reserve(first_constraints.len());
138 for (r1, start1) in first_constraints {
140 if let Some(&start2) = first_constraints2.get(&r2) {
141 append_list(&mut constraints, start1, start2);
143 first_constraints2.insert(r2, start1);
146 MemberConstraintSet { first_constraints: first_constraints2, constraints, choice_regions }
150 impl<'tcx, R> MemberConstraintSet<'tcx, R>
154 pub(crate) fn all_indices(
156 ) -> impl Iterator<Item = NllMemberConstraintIndex> + Captures<'tcx> + '_ {
157 self.constraints.indices()
160 /// Iterate down the constraint indices associated with a given
161 /// peek-region. You can then use `choice_regions` and other
162 /// methods to access data.
163 pub(crate) fn indices(
165 member_region_vid: R,
166 ) -> impl Iterator<Item = NllMemberConstraintIndex> + Captures<'tcx> + '_ {
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;
178 /// Returns the "choice regions" for a given member
179 /// constraint. This is the `R1..Rn` from a constraint like:
182 /// R0 member of [R1..Rn]
184 pub(crate) fn choice_regions(&self, pci: NllMemberConstraintIndex) -> &[ty::RegionVid] {
185 let NllMemberConstraint { start_index, end_index, .. } = &self.constraints[pci];
186 &self.choice_regions[*start_index..*end_index]
190 impl<'tcx, R> Index<NllMemberConstraintIndex> for MemberConstraintSet<'tcx, R>
194 type Output = NllMemberConstraint<'tcx>;
196 fn index(&self, i: NllMemberConstraintIndex) -> &NllMemberConstraint<'tcx> {
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`.
208 /// target_list: A -> B -> C -> (None)
209 /// source_list: D -> E -> F -> (None)
215 /// target_list: A -> B -> C -> D -> E -> F -> (None)
218 constraints: &mut IndexVec<NllMemberConstraintIndex, NllMemberConstraint<'_>>,
219 target_list: NllMemberConstraintIndex,
220 source_list: NllMemberConstraintIndex,
222 let mut p = target_list;
224 let mut r = &mut constraints[p];
225 match r.next_constraint {
228 r.next_constraint = Some(source_list);