compiler/rustc_borrowck/src/member_constraints.rs

   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};
   5 use rustc_span::Span;
   6 use std::hash::Hash;
   7 use std::ops::Index;
   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
  13     R: Copy + Eq,
  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
  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
  50 rustc_index::newtype_index! {
  51     crate struct NllMemberConstraintIndex {
  52         DEBUG_FORMAT = "MemberConstraintIndex({})"
  53     }
  54 }
  55
  56 impl Default for MemberConstraintSet<'_, 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
  70     /// the `rustc_middle::infer` code.
  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,
  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<'tcx, 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
 123         // rewriting the final link from one list to point at the other
 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
 139         MemberConstraintSet { first_constraints: first_constraints2, constraints, choice_regions }
 140     }
 141 }
 142
 143 impl<R> MemberConstraintSet<'_, R>
 144 where
 145     R: Copy + Hash + Eq,
 146 {
 147     crate fn all_indices(&self) -> impl Iterator<Item = NllMemberConstraintIndex> + '_ {
 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
 183     R: Copy + Eq,
 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 }