ena/
undo_log.rs

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 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 actions 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 rolled 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        I: IntoIterator<Item = T>,
62    {
63        U::extend(self, undos)
64    }
65}
66
67/// A trait which extends `UndoLogs` to allow snapshots to be done at specific points. Each snapshot can then be used to
68/// rollback any changes to an underlying data structures if they were not desirable.
69///
70/// Each snapshot must be consumed linearly with either `rollback_to` or `commit`.
71pub trait Snapshots<T>: UndoLogs<T> {
72    type Snapshot;
73
74    /// Returns true if `self` has made any changes since snapshot started.
75    fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
76        !self.actions_since_snapshot(snapshot).is_empty()
77    }
78
79    /// Returns the slice of actions that were taken since the snapshot began.
80    fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T];
81
82    /// Starts a new snapshot. That snapshot must eventually either be committed via a call to
83    /// commit or rollback via rollback_to. Snapshots can be nested (i.e., you can start a snapshot
84    /// whilst another snapshot is in progress) but you must then commit or rollback the inner
85    /// snapshot before attempting to commit or rollback the outer snapshot.
86    fn start_snapshot(&mut self) -> Self::Snapshot;
87
88    /// Rollback (undo) the changes made to `storage` since the snapshot.
89    fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot)
90    where
91        R: Rollback<T>;
92
93    /// Commit: keep the changes that have been made since the snapshot began
94    fn commit(&mut self, snapshot: Self::Snapshot);
95}
96
97impl<T, U> Snapshots<T> for &'_ mut U
98where
99    U: Snapshots<T>,
100{
101    type Snapshot = U::Snapshot;
102    fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
103        U::has_changes(self, snapshot)
104    }
105    fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T] {
106        U::actions_since_snapshot(self, snapshot)
107    }
108
109    fn start_snapshot(&mut self) -> Self::Snapshot {
110        U::start_snapshot(self)
111    }
112    fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot)
113    where
114        R: Rollback<T>,
115    {
116        U::rollback_to(self, storage, snapshot)
117    }
118
119    fn commit(&mut self, snapshot: Self::Snapshot) {
120        U::commit(self, snapshot)
121    }
122}
123
124pub struct NoUndo;
125impl<T> UndoLogs<T> for NoUndo {
126    fn num_open_snapshots(&self) -> usize {
127        0
128    }
129    fn push(&mut self, _undo: T) {}
130    fn clear(&mut self) {}
131}
132
133/// A basic undo log.
134#[derive(Clone, Debug)]
135pub struct VecLog<T> {
136    log: Vec<T>,
137    num_open_snapshots: usize,
138}
139
140impl<T> Default for VecLog<T> {
141    fn default() -> Self {
142        VecLog {
143            log: Vec::new(),
144            num_open_snapshots: 0,
145        }
146    }
147}
148
149impl<T> UndoLogs<T> for VecLog<T> {
150    fn num_open_snapshots(&self) -> usize {
151        self.num_open_snapshots
152    }
153    fn push(&mut self, undo: T) {
154        self.log.push(undo);
155    }
156    fn clear(&mut self) {
157        self.log.clear();
158        self.num_open_snapshots = 0;
159    }
160}
161
162impl<T> Snapshots<T> for VecLog<T> {
163    type Snapshot = Snapshot;
164
165    fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
166        self.log.len() > snapshot.undo_len
167    }
168    fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[T] {
169        &self.log[snapshot.undo_len..]
170    }
171
172    fn start_snapshot(&mut self) -> Snapshot {
173        self.num_open_snapshots += 1;
174        Snapshot {
175            undo_len: self.log.len(),
176        }
177    }
178
179    fn rollback_to<R>(&mut self, values: impl FnOnce() -> R, snapshot: Snapshot)
180    where
181        R: Rollback<T>,
182    {
183        debug!("rollback_to({})", snapshot.undo_len);
184
185        self.assert_open_snapshot(&snapshot);
186
187        if self.log.len() > snapshot.undo_len {
188            let mut values = values();
189            while self.log.len() > snapshot.undo_len {
190                values.reverse(self.log.pop().unwrap());
191            }
192        }
193
194        self.num_open_snapshots -= 1;
195    }
196
197    fn commit(&mut self, snapshot: Snapshot) {
198        debug!("commit({})", snapshot.undo_len);
199
200        self.assert_open_snapshot(&snapshot);
201
202        if self.num_open_snapshots == 1 {
203            // The root snapshot. It's safe to clear the undo log because
204            // there's no snapshot further out that we might need to roll back
205            // to.
206            assert!(snapshot.undo_len == 0);
207            self.log.clear();
208        }
209
210        self.num_open_snapshots -= 1;
211    }
212}
213
214impl<T> VecLog<T> {
215    fn assert_open_snapshot(&self, snapshot: &Snapshot) {
216        // Failures here may indicate a failure to follow a stack discipline.
217        assert!(self.log.len() >= snapshot.undo_len);
218        assert!(self.num_open_snapshots > 0);
219    }
220}
221
222impl<T> std::ops::Index<usize> for VecLog<T> {
223    type Output = T;
224    fn index(&self, key: usize) -> &T {
225        &self.log[key]
226    }
227}
228
229/// A trait implemented for storage types (like `SnapshotVecStorage`) which can be rolled back using actions of type `U`.
230pub trait Rollback<U> {
231    fn reverse(&mut self, undo: U);
232}
233
234impl<T, U> Rollback<U> for &'_ mut T
235where
236    T: Rollback<U>,
237{
238    fn reverse(&mut self, undo: U) {
239        T::reverse(self, undo)
240    }
241}
242
243/// Snapshots are tokens that should be created/consumed linearly.
244pub struct Snapshot {
245    // Length of the undo log at the time the snapshot was taken.
246    undo_len: usize,
247}
ena/undo_log.rs

ena/
undo_log.rs
