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