src/librustc_mir/borrow_check/nll/member_constraints.rs

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