1 use rustc_data_structures
::fx
::FxHashMap
;
2 use rustc_index
::vec
::IndexVec
;
3 use rustc_middle
::infer
::MemberConstraint
;
4 use rustc_middle
::ty
::{self, Ty}
;
9 /// Compactly stores a set of `R0 member of [R1...Rn]` constraints,
10 /// indexed by the region `R0`.
11 crate struct MemberConstraintSet
<'tcx
, R
>
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
>,
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
>>,
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
27 choice_regions
: Vec
<ty
::RegionVid
>,
30 /// Represents a `R0 member of [R1..Rn]` constraint
31 crate struct NllMemberConstraint
<'tcx
> {
32 next_constraint
: Option
<NllMemberConstraintIndex
>,
34 /// The span where the hidden type was instantiated.
35 crate definition_span
: Span
,
37 /// The hidden type in which `R0` appears. (Used in error reporting.)
38 crate hidden_ty
: Ty
<'tcx
>,
41 crate member_region_vid
: ty
::RegionVid
,
43 /// Index of `R1` in `choice_regions` vector from `MemberConstraintSet`.
46 /// Index of `Rn` in `choice_regions` vector from `MemberConstraintSet`.
50 rustc_index
::newtype_index
! {
51 crate struct NllMemberConstraintIndex
{
52 DEBUG_FORMAT
= "MemberConstraintIndex({})"
56 impl Default
for MemberConstraintSet
<'_
, ty
::RegionVid
> {
57 fn default() -> Self {
59 first_constraints
: Default
::default(),
60 constraints
: Default
::default(),
61 choice_regions
: Default
::default(),
66 impl<'tcx
> MemberConstraintSet
<'tcx
, ty
::RegionVid
> {
67 /// Pushes a member constraint into the set.
69 /// The input member constraint `m_c` is in the form produced by
70 /// the `rustc_middle::infer` code.
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(
78 m_c
: &MemberConstraint
<'tcx
>,
79 mut to_region_vid
: impl FnMut(ty
::Region
<'tcx
>) -> ty
::RegionVid
,
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
{
90 definition_span
: m_c
.definition_span
,
91 hidden_ty
: m_c
.hidden_ty
,
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
)));
100 impl<'tcx
, R1
> MemberConstraintSet
<'tcx
, R1
>
102 R1
: Copy
+ Hash
+ Eq
,
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
>(
111 mut map_fn
: impl FnMut(R1
) -> R2
,
112 ) -> MemberConstraintSet
<'tcx
, R2
>
114 R2
: Copy
+ Hash
+ Eq
,
116 // We can re-use most of the original data, just tweaking the
117 // linked list links a bit.
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
123 // rewriting the final link from one list to point at the other
124 // other (see `append_list`).
126 let MemberConstraintSet { first_constraints, mut constraints, choice_regions }
= self;
128 let mut first_constraints2
= FxHashMap
::default();
129 first_constraints2
.reserve(first_constraints
.len());
131 for (r1
, start1
) in first_constraints
{
133 if let Some(&start2
) = first_constraints2
.get(&r2
) {
134 append_list(&mut constraints
, start1
, start2
);
136 first_constraints2
.insert(r2
, start1
);
139 MemberConstraintSet { first_constraints: first_constraints2, constraints, choice_regions }
143 impl<R
> MemberConstraintSet
<'_
, R
>
147 crate fn all_indices(&self) -> impl Iterator
<Item
= NllMemberConstraintIndex
> + '_
{
148 self.constraints
.indices()
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.
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
;
169 /// Returns the "choice regions" for a given member
170 /// constraint. This is the `R1..Rn` from a constraint like:
173 /// R0 member of [R1..Rn]
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
]
181 impl<'tcx
, R
> Index
<NllMemberConstraintIndex
> for MemberConstraintSet
<'tcx
, R
>
185 type Output
= NllMemberConstraint
<'tcx
>;
187 fn index(&self, i
: NllMemberConstraintIndex
) -> &NllMemberConstraint
<'tcx
> {
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`.
199 /// target_list: A -> B -> C -> (None)
200 /// source_list: D -> E -> F -> (None)
206 /// target_list: A -> B -> C -> D -> E -> F -> (None)
209 constraints
: &mut IndexVec
<NllMemberConstraintIndex
, NllMemberConstraint
<'_
>>,
210 target_list
: NllMemberConstraintIndex
,
211 source_list
: NllMemberConstraintIndex
,
213 let mut p
= target_list
;
215 let mut r
= &mut constraints
[p
];
216 match r
.next_constraint
{
219 r
.next_constraint
= Some(source_list
);