src/librustc_infer/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, Snapshots, UndoLogs};
   5 use rustc_data_structures::unify as ut;
   6 use rustc_hir as hir;
   7 use rustc_middle::ty;
   8
   9 use crate::{
  10     infer::{
  11         region_constraints::{self, RegionConstraintStorage},
  12         type_variable, RegionObligation,
  13     },
  14     traits,
  15 };
  16
  17 pub struct Snapshot<'tcx> {
  18     pub(crate) undo_len: usize,
  19     _marker: PhantomData<&'tcx ()>,
  20 }
  21
  22 pub(crate) enum UndoLog<'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<ty::RegionVid>>),
  29     ProjectionCache(traits::UndoLog<'tcx>),
  30     PushRegionObligation,
  31 }
  32
  33 impl<'tcx> From<region_constraints::UndoLog<'tcx>> for UndoLog<'tcx> {
  34     fn from(l: region_constraints::UndoLog<'tcx>) -> Self {
  35         UndoLog::RegionConstraintCollector(l)
  36     }
  37 }
  38
  39 impl<'tcx> From<sv::UndoLog<ut::Delegate<type_variable::TyVidEqKey<'tcx>>>> for UndoLog<'tcx> {
  40     fn from(l: sv::UndoLog<ut::Delegate<type_variable::TyVidEqKey<'tcx>>>) -> Self {
  41         UndoLog::TypeVariables(type_variable::UndoLog::EqRelation(l))
  42     }
  43 }
  44
  45 impl<'tcx> From<sv::UndoLog<ut::Delegate<ty::TyVid>>> for UndoLog<'tcx> {
  46     fn from(l: sv::UndoLog<ut::Delegate<ty::TyVid>>) -> Self {
  47         UndoLog::TypeVariables(type_variable::UndoLog::SubRelation(l))
  48     }
  49 }
  50
  51 impl<'tcx> From<sv::UndoLog<type_variable::Delegate>> for UndoLog<'tcx> {
  52     fn from(l: sv::UndoLog<type_variable::Delegate>) -> Self {
  53         UndoLog::TypeVariables(type_variable::UndoLog::Values(l))
  54     }
  55 }
  56
  57 impl<'tcx> From<type_variable::Instantiate> for UndoLog<'tcx> {
  58     fn from(l: type_variable::Instantiate) -> Self {
  59         UndoLog::TypeVariables(type_variable::UndoLog::from(l))
  60     }
  61 }
  62
  63 impl From<type_variable::UndoLog<'tcx>> for UndoLog<'tcx> {
  64     fn from(t: type_variable::UndoLog<'tcx>) -> Self {
  65         Self::TypeVariables(t)
  66     }
  67 }
  68
  69 impl<'tcx> From<sv::UndoLog<ut::Delegate<ty::ConstVid<'tcx>>>> for UndoLog<'tcx> {
  70     fn from(l: sv::UndoLog<ut::Delegate<ty::ConstVid<'tcx>>>) -> Self {
  71         Self::ConstUnificationTable(l)
  72     }
  73 }
  74
  75 impl<'tcx> From<sv::UndoLog<ut::Delegate<ty::IntVid>>> for UndoLog<'tcx> {
  76     fn from(l: sv::UndoLog<ut::Delegate<ty::IntVid>>) -> Self {
  77         Self::IntUnificationTable(l)
  78     }
  79 }
  80
  81 impl<'tcx> From<sv::UndoLog<ut::Delegate<ty::FloatVid>>> for UndoLog<'tcx> {
  82     fn from(l: sv::UndoLog<ut::Delegate<ty::FloatVid>>) -> Self {
  83         Self::FloatUnificationTable(l)
  84     }
  85 }
  86
  87 impl<'tcx> From<sv::UndoLog<ut::Delegate<ty::RegionVid>>> for UndoLog<'tcx> {
  88     fn from(l: sv::UndoLog<ut::Delegate<ty::RegionVid>>) -> Self {
  89         Self::RegionUnificationTable(l)
  90     }
  91 }
  92
  93 impl<'tcx> From<traits::UndoLog<'tcx>> for UndoLog<'tcx> {
  94     fn from(l: traits::UndoLog<'tcx>) -> Self {
  95         Self::ProjectionCache(l)
  96     }
  97 }
  98
  99 pub(super) struct RollbackView<'tcx, 'a> {
 100     pub(super) type_variables: &'a mut type_variable::TypeVariableStorage<'tcx>,
 101     pub(super) const_unification_table: &'a mut ut::UnificationTableStorage<ty::ConstVid<'tcx>>,
 102     pub(super) int_unification_table: &'a mut ut::UnificationTableStorage<ty::IntVid>,
 103     pub(super) float_unification_table: &'a mut ut::UnificationTableStorage<ty::FloatVid>,
 104     pub(super) region_constraints: &'a mut RegionConstraintStorage<'tcx>,
 105     pub(super) projection_cache: &'a mut traits::ProjectionCacheStorage<'tcx>,
 106     pub(super) region_obligations: &'a mut Vec<(hir::HirId, RegionObligation<'tcx>)>,
 107 }
 108
 109 impl<'tcx> Rollback<UndoLog<'tcx>> for RollbackView<'tcx, '_> {
 110     fn reverse(&mut self, undo: UndoLog<'tcx>) {
 111         match undo {
 112             UndoLog::TypeVariables(undo) => self.type_variables.reverse(undo),
 113             UndoLog::ConstUnificationTable(undo) => self.const_unification_table.reverse(undo),
 114             UndoLog::IntUnificationTable(undo) => self.int_unification_table.reverse(undo),
 115             UndoLog::FloatUnificationTable(undo) => self.float_unification_table.reverse(undo),
 116             UndoLog::RegionConstraintCollector(undo) => self.region_constraints.reverse(undo),
 117             UndoLog::RegionUnificationTable(undo) => {
 118                 self.region_constraints.unification_table.reverse(undo)
 119             }
 120             UndoLog::ProjectionCache(undo) => self.projection_cache.reverse(undo),
 121             UndoLog::PushRegionObligation => {
 122                 self.region_obligations.pop();
 123             }
 124         }
 125     }
 126 }
 127
 128 pub(crate) struct InferCtxtUndoLogs<'tcx> {
 129     logs: Vec<UndoLog<'tcx>>,
 130     num_open_snapshots: usize,
 131 }
 132
 133 impl Default for InferCtxtUndoLogs<'_> {
 134     fn default() -> Self {
 135         Self { logs: Default::default(), num_open_snapshots: Default::default() }
 136     }
 137 }
 138
 139 impl<'tcx, T> UndoLogs<T> for InferCtxtUndoLogs<'tcx>
 140 where
 141     UndoLog<'tcx>: From<T>,
 142 {
 143     fn num_open_snapshots(&self) -> usize {
 144         self.num_open_snapshots
 145     }
 146     fn push(&mut self, undo: T) {
 147         if self.in_snapshot() {
 148             self.logs.push(undo.into())
 149         }
 150     }
 151     fn clear(&mut self) {
 152         self.logs.clear();
 153         self.num_open_snapshots = 0;
 154     }
 155     fn extend<J>(&mut self, undos: J)
 156     where
 157         Self: Sized,
 158         J: IntoIterator<Item = T>,
 159     {
 160         if self.in_snapshot() {
 161             self.logs.extend(undos.into_iter().map(UndoLog::from))
 162         }
 163     }
 164 }
 165
 166 impl<'tcx> Snapshots<UndoLog<'tcx>> for InferCtxtUndoLogs<'tcx> {
 167     type Snapshot = Snapshot<'tcx>;
 168     fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[UndoLog<'tcx>] {
 169         &self.logs[snapshot.undo_len..]
 170     }
 171
 172     fn start_snapshot(&mut self) -> Self::Snapshot {
 173         self.num_open_snapshots += 1;
 174         Snapshot { undo_len: self.logs.len(), _marker: PhantomData }
 175     }
 176
 177     fn rollback_to<R>(&mut self, values: impl FnOnce() -> R, snapshot: Self::Snapshot)
 178     where
 179         R: Rollback<UndoLog<'tcx>>,
 180     {
 181         debug!("rollback_to({})", snapshot.undo_len);
 182         self.assert_open_snapshot(&snapshot);
 183
 184         if self.logs.len() > snapshot.undo_len {
 185             let mut values = values();
 186             while self.logs.len() > snapshot.undo_len {
 187                 values.reverse(self.logs.pop().unwrap());
 188             }
 189         }
 190
 191         if self.num_open_snapshots == 1 {
 192             // The root snapshot. It's safe to clear the undo log because
 193             // there's no snapshot further out that we might need to roll back
 194             // to.
 195             assert!(snapshot.undo_len == 0);
 196             self.logs.clear();
 197         }
 198
 199         self.num_open_snapshots -= 1;
 200     }
 201
 202     fn commit(&mut self, snapshot: Self::Snapshot) {
 203         debug!("commit({})", snapshot.undo_len);
 204
 205         if self.num_open_snapshots == 1 {
 206             // The root snapshot. It's safe to clear the undo log because
 207             // there's no snapshot further out that we might need to roll back
 208             // to.
 209             assert!(snapshot.undo_len == 0);
 210             self.logs.clear();
 211         }
 212
 213         self.num_open_snapshots -= 1;
 214     }
 215 }
 216
 217 impl<'tcx> InferCtxtUndoLogs<'tcx> {
 218     pub(crate) fn region_constraints_in_snapshot(
 219         &self,
 220         s: &Snapshot<'tcx>,
 221     ) -> impl Iterator<Item = &'_ region_constraints::UndoLog<'tcx>> + Clone {
 222         self.logs[s.undo_len..].iter().filter_map(|log| match log {
 223             UndoLog::RegionConstraintCollector(log) => Some(log),
 224             _ => None,
 225         })
 226     }
 227
 228     pub(crate) fn region_constraints(
 229         &self,
 230     ) -> impl Iterator<Item = &'_ region_constraints::UndoLog<'tcx>> + Clone {
 231         self.logs.iter().filter_map(|log| match log {
 232             UndoLog::RegionConstraintCollector(log) => Some(log),
 233             _ => None,
 234         })
 235     }
 236
 237     fn assert_open_snapshot(&self, snapshot: &Snapshot<'tcx>) {
 238         // Failures here may indicate a failure to follow a stack discipline.
 239         assert!(self.logs.len() >= snapshot.undo_len);
 240         assert!(self.num_open_snapshots > 0);
 241     }
 242
 243     pub(crate) fn iter(&self) -> std::slice::Iter<'_, UndoLog<'tcx>> {
 244         self.logs.iter()
 245     }
 246 }
 247
 248 impl<'tcx> std::ops::Index<usize> for InferCtxtUndoLogs<'tcx> {
 249     type Output = UndoLog<'tcx>;
 250     fn index(&self, key: usize) -> &Self::Output {
 251         &self.logs[key]
 252     }
 253 }
 254
 255 impl<'tcx> std::ops::IndexMut<usize> for InferCtxtUndoLogs<'tcx> {
 256     fn index_mut(&mut self, key: usize) -> &mut Self::Output {
 257         &mut self.logs[key]
 258     }
 259 }