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.
16pub trait UndoLogs<T> {
17 /// True if a snapshot has started, false otherwise
18 fn in_snapshot(&self) -> bool {
19 self.num_open_snapshots() > 0
20 }
21
22 /// How many open snapshots this undo log currently has
23 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.
28 fn push(&mut self, undo: T);
29
30 /// Removes all items from the undo log.
31 fn clear(&mut self);
32
33 /// Extends the undo log with many undos.
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
43impl<'a, T, U> UndoLogs<T> for &'a mut U
44where
45 U: UndoLogs<T>,
46{
47 fn in_snapshot(&self) -> bool {
48 U::in_snapshot(self)
49 }
50 fn num_open_snapshots(&self) -> usize {
51 U::num_open_snapshots(self)
52 }
53 fn push(&mut self, undo: T) {
54 U::push(self, undo)
55 }
56 fn clear(&mut self) {
57 U::clear(self);
58 }
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`.
72pub trait Snapshots<T>: UndoLogs<T> {
73 type Snapshot;
74
75 /// Returns true if `self` has made any changes since snapshot started.
76 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.
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.
87 fn start_snapshot(&mut self) -> Self::Snapshot;
88
89 /// Rollback (undo) the changes made to `storage` since the snapshot.
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
95 fn commit(&mut self, snapshot: Self::Snapshot);
96}
97
98impl<T, U> Snapshots<T> for &'_ mut U
99where
100 U: Snapshots<T>,
101{
102 type Snapshot = U::Snapshot;
103 fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
104 U::has_changes(self, snapshot)
105 }
106 fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T] {
107 U::actions_since_snapshot(self, snapshot)
108 }
109
110 fn start_snapshot(&mut self) -> Self::Snapshot {
111 U::start_snapshot(self)
112 }
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
120 fn commit(&mut self, snapshot: Self::Snapshot) {
121 U::commit(self, snapshot)
122 }
123}
124
125pub struct NoUndo;
126impl<T> UndoLogs<T> for NoUndo {
127 fn num_open_snapshots(&self) -> usize {
128 0
129 }
130 fn push(&mut self, _undo: T) {}
131 fn clear(&mut self) {}
132}
133
134/// A basic undo log.
135#[derive(Clone, Debug)]
136pub struct VecLog<T> {
137 log: Vec<T>,
138 num_open_snapshots: usize,
139}
140
141impl<T> Default for VecLog<T> {
142 fn default() -> Self {
143 VecLog {
144 log: Vec::new(),
145 num_open_snapshots: 0,
146 }
147 }
148}
149
150impl<T> UndoLogs<T> for VecLog<T> {
151 fn num_open_snapshots(&self) -> usize {
152 self.num_open_snapshots
153 }
154 fn push(&mut self, undo: T) {
155 self.log.push(undo);
156 }
157 fn clear(&mut self) {
158 self.log.clear();
159 self.num_open_snapshots = 0;
160 }
161}
162
163impl<T> Snapshots<T> for VecLog<T> {
164 type Snapshot = Snapshot;
165
166 fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
167 self.log.len() > snapshot.undo_len
168 }
169 fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[T] {
170 &self.log[snapshot.undo_len..]
171 }
172
173 fn start_snapshot(&mut self) -> Snapshot {
174 self.num_open_snapshots += 1;
175 Snapshot {
176 undo_len: self.log.len(),
177 }
178 }
179
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
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
215impl<T> VecLog<T> {
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
223impl<T> std::ops::Index<usize> for VecLog<T> {
224 type Output = T;
225 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`.
231pub trait Rollback<U> {
232 fn reverse(&mut self, undo: U);
233}
234
235impl<T, U> Rollback<U> for &'_ mut T
236where
237 T: Rollback<U>,
238{
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.
245pub struct Snapshot {
246 // Length of the undo log at the time the snapshot was taken.
247 undo_len: usize,
248}
249