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