compiler/rustc_infer/src/infer/undo_log.rs

   1 use std::marker::PhantomData;
   2
   3 use rustc_data_structures::snapshot_vec as sv;
   4 use rustc_data_structures::undo_log::{Rollback, UndoLogs};
   5 use rustc_data_structures::unify as ut;
   6 use rustc_middle::infer::unify_key::RegionVidKey;
   7 use rustc_middle::ty::{self, OpaqueHiddenType, OpaqueTypeKey};
   8
   9 use crate::{
  10     infer::{region_constraints, type_variable, InferCtxtInner},
  11     traits,
  12 };
  13
  14 pub struct Snapshot<'tcx> {
  15     pub(crate) undo_len: usize,
  16     _marker: PhantomData<&'tcx ()>,
  17 }
  18
  19 /// Records the "undo" data for a single operation that affects some form of inference variable.
  20 #[derive(Clone)]
  21 pub(crate) enum UndoLog<'tcx> {
  22     OpaqueTypes(OpaqueTypeKey<'tcx>, Option<OpaqueHiddenType<'tcx>>),
  23     TypeVariables(type_variable::UndoLog<'tcx>),
  24     ConstUnificationTable(sv::UndoLog<ut::Delegate<ty::ConstVid<'tcx>>>),
  25     IntUnificationTable(sv::UndoLog<ut::Delegate<ty::IntVid>>),
  26     FloatUnificationTable(sv::UndoLog<ut::Delegate<ty::FloatVid>>),
  27     RegionConstraintCollector(region_constraints::UndoLog<'tcx>),
  28     RegionUnificationTable(sv::UndoLog<ut::Delegate<RegionVidKey<'tcx>>>),
  29     ProjectionCache(traits::UndoLog<'tcx>),
  30     PushRegionObligation,
  31 }
  32
  33 macro_rules! impl_from {
  34     ($($ctor: ident ($ty: ty),)*) => {
  35         $(
  36         impl<'tcx> From<$ty> for UndoLog<'tcx> {
  37             fn from(x: $ty) -> Self {
  38                 UndoLog::$ctor(x.into())
  39             }
  40         }
  41         )*
  42     }
  43 }
  44
  45 // Upcast from a single kind of "undoable action" to the general enum
  46 impl_from! {
  47     RegionConstraintCollector(region_constraints::UndoLog<'tcx>),
  48     TypeVariables(type_variable::UndoLog<'tcx>),
  49
  50     TypeVariables(sv::UndoLog<ut::Delegate<type_variable::TyVidEqKey<'tcx>>>),
  51     TypeVariables(sv::UndoLog<ut::Delegate<ty::TyVid>>),
  52     TypeVariables(sv::UndoLog<type_variable::Delegate>),
  53     TypeVariables(type_variable::Instantiate),
  54
  55     IntUnificationTable(sv::UndoLog<ut::Delegate<ty::IntVid>>),
  56
  57     FloatUnificationTable(sv::UndoLog<ut::Delegate<ty::FloatVid>>),
  58
  59     ConstUnificationTable(sv::UndoLog<ut::Delegate<ty::ConstVid<'tcx>>>),
  60
  61     RegionUnificationTable(sv::UndoLog<ut::Delegate<RegionVidKey<'tcx>>>),
  62     ProjectionCache(traits::UndoLog<'tcx>),
  63 }
  64
  65 /// The Rollback trait defines how to rollback a particular action.
  66 impl<'tcx> Rollback<UndoLog<'tcx>> for InferCtxtInner<'tcx> {
  67     fn reverse(&mut self, undo: UndoLog<'tcx>) {
  68         match undo {
  69             UndoLog::OpaqueTypes(key, idx) => self.opaque_type_storage.remove(key, idx),
  70             UndoLog::TypeVariables(undo) => self.type_variable_storage.reverse(undo),
  71             UndoLog::ConstUnificationTable(undo) => self.const_unification_storage.reverse(undo),
  72             UndoLog::IntUnificationTable(undo) => self.int_unification_storage.reverse(undo),
  73             UndoLog::FloatUnificationTable(undo) => self.float_unification_storage.reverse(undo),
  74             UndoLog::RegionConstraintCollector(undo) => {
  75                 self.region_constraint_storage.as_mut().unwrap().reverse(undo)
  76             }
  77             UndoLog::RegionUnificationTable(undo) => {
  78                 self.region_constraint_storage.as_mut().unwrap().unification_table.reverse(undo)
  79             }
  80             UndoLog::ProjectionCache(undo) => self.projection_cache.reverse(undo),
  81             UndoLog::PushRegionObligation => {
  82                 self.region_obligations.pop();
  83             }
  84         }
  85     }
  86 }
  87
  88 /// The combined undo log for all the various unification tables. For each change to the storage
  89 /// for any kind of inference variable, we record an UndoLog entry in the vector here.
  90 #[derive(Clone)]
  91 pub(crate) struct InferCtxtUndoLogs<'tcx> {
  92     logs: Vec<UndoLog<'tcx>>,
  93     num_open_snapshots: usize,
  94 }
  95
  96 impl Default for InferCtxtUndoLogs<'_> {
  97     fn default() -> Self {
  98         Self { logs: Default::default(), num_open_snapshots: Default::default() }
  99     }
 100 }
 101
 102 /// The UndoLogs trait defines how we undo a particular kind of action (of type T). We can undo any
 103 /// action that is convertible into an UndoLog (per the From impls above).
 104 impl<'tcx, T> UndoLogs<T> for InferCtxtUndoLogs<'tcx>
 105 where
 106     UndoLog<'tcx>: From<T>,
 107 {
 108     #[inline]
 109     fn num_open_snapshots(&self) -> usize {
 110         self.num_open_snapshots
 111     }
 112
 113     #[inline]
 114     fn push(&mut self, undo: T) {
 115         if self.in_snapshot() {
 116             self.logs.push(undo.into())
 117         }
 118     }
 119
 120     fn clear(&mut self) {
 121         self.logs.clear();
 122         self.num_open_snapshots = 0;
 123     }
 124
 125     fn extend<J>(&mut self, undos: J)
 126     where
 127         Self: Sized,
 128         J: IntoIterator<Item = T>,
 129     {
 130         if self.in_snapshot() {
 131             self.logs.extend(undos.into_iter().map(UndoLog::from))
 132         }
 133     }
 134 }
 135
 136 impl<'tcx> InferCtxtInner<'tcx> {
 137     pub fn rollback_to(&mut self, snapshot: Snapshot<'tcx>) {
 138         debug!("rollback_to({})", snapshot.undo_len);
 139         self.undo_log.assert_open_snapshot(&snapshot);
 140
 141         while self.undo_log.logs.len() > snapshot.undo_len {
 142             let undo = self.undo_log.logs.pop().unwrap();
 143             self.reverse(undo);
 144         }
 145
 146         if self.undo_log.num_open_snapshots == 1 {
 147             // The root snapshot. It's safe to clear the undo log because
 148             // there's no snapshot further out that we might need to roll back
 149             // to.
 150             assert!(snapshot.undo_len == 0);
 151             self.undo_log.logs.clear();
 152         }
 153
 154         self.undo_log.num_open_snapshots -= 1;
 155     }
 156
 157     pub fn commit(&mut self, snapshot: Snapshot<'tcx>) {
 158         debug!("commit({})", snapshot.undo_len);
 159
 160         if self.undo_log.num_open_snapshots == 1 {
 161             // The root snapshot. It's safe to clear the undo log because
 162             // there's no snapshot further out that we might need to roll back
 163             // to.
 164             assert!(snapshot.undo_len == 0);
 165             self.undo_log.logs.clear();
 166         }
 167
 168         self.undo_log.num_open_snapshots -= 1;
 169     }
 170 }
 171
 172 impl<'tcx> InferCtxtUndoLogs<'tcx> {
 173     pub fn start_snapshot(&mut self) -> Snapshot<'tcx> {
 174         self.num_open_snapshots += 1;
 175         Snapshot { undo_len: self.logs.len(), _marker: PhantomData }
 176     }
 177
 178     pub(crate) fn region_constraints_in_snapshot(
 179         &self,
 180         s: &Snapshot<'tcx>,
 181     ) -> impl Iterator<Item = &'_ region_constraints::UndoLog<'tcx>> + Clone {
 182         self.logs[s.undo_len..].iter().filter_map(|log| match log {
 183             UndoLog::RegionConstraintCollector(log) => Some(log),
 184             _ => None,
 185         })
 186     }
 187
 188     pub(crate) fn opaque_types_in_snapshot(&self, s: &Snapshot<'tcx>) -> bool {
 189         self.logs[s.undo_len..].iter().any(|log| matches!(log, UndoLog::OpaqueTypes(..)))
 190     }
 191
 192     pub(crate) fn region_constraints(
 193         &self,
 194     ) -> impl Iterator<Item = &'_ region_constraints::UndoLog<'tcx>> + Clone {
 195         self.logs.iter().filter_map(|log| match log {
 196             UndoLog::RegionConstraintCollector(log) => Some(log),
 197             _ => None,
 198         })
 199     }
 200
 201     fn assert_open_snapshot(&self, snapshot: &Snapshot<'tcx>) {
 202         // Failures here may indicate a failure to follow a stack discipline.
 203         assert!(self.logs.len() >= snapshot.undo_len);
 204         assert!(self.num_open_snapshots > 0);
 205     }
 206 }
 207
 208 impl<'tcx> std::ops::Index<usize> for InferCtxtUndoLogs<'tcx> {
 209     type Output = UndoLog<'tcx>;
 210
 211     fn index(&self, key: usize) -> &Self::Output {
 212         &self.logs[key]
 213     }
 214 }
 215
 216 impl<'tcx> std::ops::IndexMut<usize> for InferCtxtUndoLogs<'tcx> {
 217     fn index_mut(&mut self, key: usize) -> &mut Self::Output {
 218         &mut self.logs[key]
 219     }
 220 }