1 //! Module which contains the snapshot/rollback functionality of the `ena` data structures. 2 //! 3 //! For most usecases this is just an internal implementation detail. However if many `ena` 4 //! data structures are used snapshotted simultaneously it is possible to use 5 //! `UnificationTableStorage`/`SnapshotVecStorage` instead and use a custom `UndoLogs<T>` 6 //! type capable of recording the actions of all used data structures. 7 //! 8 //! Since the `*Storage` variants do not have an undo log `with_log` must be called with the 9 //! unified log before any mutating actions. 10 11 /// A trait which allows undo actions (`T`) to be pushed which can be used to rollback actio at a 12 /// later time if needed. 13 /// 14 /// The undo actions themselves are opaque to `UndoLogs`, only specified `Rollback` implementations 15 /// need to know what an action is and how to reverse it. 16 pub trait UndoLogs<T> { 17 /// True if a snapshot has started, false otherwise in_snapshot(&self) -> bool18 fn in_snapshot(&self) -> bool { 19 self.num_open_snapshots() > 0 20 } 21 22 /// How many open snapshots this undo log currently has num_open_snapshots(&self) -> usize23 fn num_open_snapshots(&self) -> usize; 24 25 /// Pushes a new "undo item" onto the undo log. This method is invoked when some action is taken 26 /// (e.g., a variable is unified). It records the info needed to reverse that action should an 27 /// enclosing snapshot be rolleod back. push(&mut self, undo: T)28 fn push(&mut self, undo: T); 29 30 /// Removes all items from the undo log. clear(&mut self)31 fn clear(&mut self); 32 33 /// Extends the undo log with many undos. extend<I>(&mut self, undos: I) where Self: Sized, I: IntoIterator<Item = T>,34 fn extend<I>(&mut self, undos: I) 35 where 36 Self: Sized, 37 I: IntoIterator<Item = T>, 38 { 39 undos.into_iter().for_each(|undo| self.push(undo)); 40 } 41 } 42 43 impl<'a, T, U> UndoLogs<T> for &'a mut U 44 where 45 U: UndoLogs<T>, 46 { in_snapshot(&self) -> bool47 fn in_snapshot(&self) -> bool { 48 U::in_snapshot(self) 49 } num_open_snapshots(&self) -> usize50 fn num_open_snapshots(&self) -> usize { 51 U::num_open_snapshots(self) 52 } push(&mut self, undo: T)53 fn push(&mut self, undo: T) { 54 U::push(self, undo) 55 } clear(&mut self)56 fn clear(&mut self) { 57 U::clear(self); 58 } extend<I>(&mut self, undos: I) where Self: Sized, I: IntoIterator<Item = T>,59 fn extend<I>(&mut self, undos: I) 60 where 61 Self: Sized, 62 I: IntoIterator<Item = T>, 63 { 64 U::extend(self, undos) 65 } 66 } 67 68 /// A trait which extends `UndoLogs` to allow snapshots to be done at specific points. Each snapshot can then be used to 69 /// rollback any changes to an underlying data structures if they were not desirable. 70 /// 71 /// Each snapshot must be consumed linearly with either `rollback_to` or `commit`. 72 pub trait Snapshots<T>: UndoLogs<T> { 73 type Snapshot; 74 75 /// Returns true if `self` has made any changes since snapshot started. has_changes(&self, snapshot: &Self::Snapshot) -> bool76 fn has_changes(&self, snapshot: &Self::Snapshot) -> bool { 77 !self.actions_since_snapshot(snapshot).is_empty() 78 } 79 80 /// Returns the slice of actions that were taken since the snapshot began. actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T]81 fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T]; 82 83 /// Starts a new snapshot. That snapshot must eventually either be committed via a call to 84 /// commit or rollback via rollback_to. Snapshots can be nested (i.e., you can start a snapshot 85 /// whilst another snapshot is in progress) but you must then commit or rollback the inner 86 /// snapshot before attempting to commit or rollback the outer snapshot. start_snapshot(&mut self) -> Self::Snapshot87 fn start_snapshot(&mut self) -> Self::Snapshot; 88 89 /// Rollback (undo) the changes made to `storage` since the snapshot. rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot) where R: Rollback<T>90 fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot) 91 where 92 R: Rollback<T>; 93 94 /// Commit: keep the changes that have been made since the snapshot began commit(&mut self, snapshot: Self::Snapshot)95 fn commit(&mut self, snapshot: Self::Snapshot); 96 } 97 98 impl<T, U> Snapshots<T> for &'_ mut U 99 where 100 U: Snapshots<T>, 101 { 102 type Snapshot = U::Snapshot; has_changes(&self, snapshot: &Self::Snapshot) -> bool103 fn has_changes(&self, snapshot: &Self::Snapshot) -> bool { 104 U::has_changes(self, snapshot) 105 } actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T]106 fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T] { 107 U::actions_since_snapshot(self, snapshot) 108 } 109 start_snapshot(&mut self) -> Self::Snapshot110 fn start_snapshot(&mut self) -> Self::Snapshot { 111 U::start_snapshot(self) 112 } rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot) where R: Rollback<T>,113 fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot) 114 where 115 R: Rollback<T>, 116 { 117 U::rollback_to(self, storage, snapshot) 118 } 119 commit(&mut self, snapshot: Self::Snapshot)120 fn commit(&mut self, snapshot: Self::Snapshot) { 121 U::commit(self, snapshot) 122 } 123 } 124 125 pub struct NoUndo; 126 impl<T> UndoLogs<T> for NoUndo { num_open_snapshots(&self) -> usize127 fn num_open_snapshots(&self) -> usize { 128 0 129 } push(&mut self, _undo: T)130 fn push(&mut self, _undo: T) {} clear(&mut self)131 fn clear(&mut self) {} 132 } 133 134 /// A basic undo log. 135 #[derive(Clone, Debug)] 136 pub struct VecLog<T> { 137 log: Vec<T>, 138 num_open_snapshots: usize, 139 } 140 141 impl<T> Default for VecLog<T> { default() -> Self142 fn default() -> Self { 143 VecLog { 144 log: Vec::new(), 145 num_open_snapshots: 0, 146 } 147 } 148 } 149 150 impl<T> UndoLogs<T> for VecLog<T> { num_open_snapshots(&self) -> usize151 fn num_open_snapshots(&self) -> usize { 152 self.num_open_snapshots 153 } push(&mut self, undo: T)154 fn push(&mut self, undo: T) { 155 self.log.push(undo); 156 } clear(&mut self)157 fn clear(&mut self) { 158 self.log.clear(); 159 self.num_open_snapshots = 0; 160 } 161 } 162 163 impl<T> Snapshots<T> for VecLog<T> { 164 type Snapshot = Snapshot; 165 has_changes(&self, snapshot: &Self::Snapshot) -> bool166 fn has_changes(&self, snapshot: &Self::Snapshot) -> bool { 167 self.log.len() > snapshot.undo_len 168 } actions_since_snapshot(&self, snapshot: &Snapshot) -> &[T]169 fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[T] { 170 &self.log[snapshot.undo_len..] 171 } 172 start_snapshot(&mut self) -> Snapshot173 fn start_snapshot(&mut self) -> Snapshot { 174 self.num_open_snapshots += 1; 175 Snapshot { 176 undo_len: self.log.len(), 177 } 178 } 179 rollback_to<R>(&mut self, values: impl FnOnce() -> R, snapshot: Snapshot) where R: Rollback<T>,180 fn rollback_to<R>(&mut self, values: impl FnOnce() -> R, snapshot: Snapshot) 181 where 182 R: Rollback<T>, 183 { 184 debug!("rollback_to({})", snapshot.undo_len); 185 186 self.assert_open_snapshot(&snapshot); 187 188 if self.log.len() > snapshot.undo_len { 189 let mut values = values(); 190 while self.log.len() > snapshot.undo_len { 191 values.reverse(self.log.pop().unwrap()); 192 } 193 } 194 195 self.num_open_snapshots -= 1; 196 } 197 commit(&mut self, snapshot: Snapshot)198 fn commit(&mut self, snapshot: Snapshot) { 199 debug!("commit({})", snapshot.undo_len); 200 201 self.assert_open_snapshot(&snapshot); 202 203 if self.num_open_snapshots == 1 { 204 // The root snapshot. It's safe to clear the undo log because 205 // there's no snapshot further out that we might need to roll back 206 // to. 207 assert!(snapshot.undo_len == 0); 208 self.log.clear(); 209 } 210 211 self.num_open_snapshots -= 1; 212 } 213 } 214 215 impl<T> VecLog<T> { assert_open_snapshot(&self, snapshot: &Snapshot)216 fn assert_open_snapshot(&self, snapshot: &Snapshot) { 217 // Failures here may indicate a failure to follow a stack discipline. 218 assert!(self.log.len() >= snapshot.undo_len); 219 assert!(self.num_open_snapshots > 0); 220 } 221 } 222 223 impl<T> std::ops::Index<usize> for VecLog<T> { 224 type Output = T; index(&self, key: usize) -> &T225 fn index(&self, key: usize) -> &T { 226 &self.log[key] 227 } 228 } 229 230 /// A trait implemented for storage types (like `SnapshotVecStorage`) which can be rolled back using actions of type `U`. 231 pub trait Rollback<U> { reverse(&mut self, undo: U)232 fn reverse(&mut self, undo: U); 233 } 234 235 impl<T, U> Rollback<U> for &'_ mut T 236 where 237 T: Rollback<U>, 238 { reverse(&mut self, undo: U)239 fn reverse(&mut self, undo: U) { 240 T::reverse(self, undo) 241 } 242 } 243 244 /// Snapshots are tokens that should be created/consumed linearly. 245 pub struct Snapshot { 246 // Length of the undo log at the time the snapshot was taken. 247 undo_len: usize, 248 } 249