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