compiler/rustc_borrowck/src/member_constraints.rs

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