ena/
snapshot_vec.rs

1// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! A utility class for implementing "snapshottable" things; a snapshottable data structure permits
12//! you to take a snapshot (via `start_snapshot`) and then, after making some changes, elect either
13//! to rollback to the start of the snapshot or commit those changes.
14//!
15//! This vector is intended to be used as part of an abstraction, not serve as a complete
16//! abstraction on its own. As such, while it will roll back most changes on its own, it also
17//! supports a `get_mut` operation that gives you an arbitrary mutable pointer into the vector. To
18//! ensure that any changes you make this with this pointer are rolled back, you must invoke
19//! `record` to record any changes you make and also supplying a delegate capable of reversing
20//! those changes.
21
22use self::UndoLog::*;
23
24use std::fmt;
25use std::marker::PhantomData;
26use std::mem;
27use std::ops;
28
29use undo_log::{Rollback, Snapshots, UndoLogs, VecLog};
30
31#[derive(Debug)]
32pub enum UndoLog<D: SnapshotVecDelegate> {
33    /// New variable with given index was created.
34    NewElem(usize),
35
36    /// Variable with given index was changed *from* the given value.
37    SetElem(usize, D::Value),
38
39    /// Extensible set of actions
40    Other(D::Undo),
41}
42
43impl<D: SnapshotVecDelegate> Rollback<UndoLog<D>> for SnapshotVecStorage<D> {
44    fn reverse(&mut self, undo: UndoLog<D>) {
45        self.values.reverse(undo)
46    }
47}
48impl<D: SnapshotVecDelegate> Rollback<UndoLog<D>> for Vec<D::Value> {
49    fn reverse(&mut self, undo: UndoLog<D>) {
50        match undo {
51            NewElem(i) => {
52                self.pop();
53                assert!(Vec::len(self) == i);
54            }
55
56            SetElem(i, v) => {
57                self[i] = v;
58            }
59
60            Other(u) => {
61                D::reverse(self, u);
62            }
63        }
64    }
65}
66
67pub trait VecLike<D>: AsRef<[D::Value]> + AsMut<[D::Value]> + Rollback<UndoLog<D>>
68where
69    D: SnapshotVecDelegate,
70{
71    fn push(&mut self, item: D::Value);
72    fn len(&self) -> usize;
73    fn reserve(&mut self, size: usize);
74}
75
76impl<D> VecLike<D> for Vec<D::Value>
77where
78    D: SnapshotVecDelegate,
79{
80    fn push(&mut self, item: D::Value) {
81        Vec::push(self, item)
82    }
83    fn len(&self) -> usize {
84        Vec::len(self)
85    }
86    fn reserve(&mut self, size: usize) {
87        Vec::reserve(self, size)
88    }
89}
90
91impl<D> VecLike<D> for &'_ mut Vec<D::Value>
92where
93    D: SnapshotVecDelegate,
94{
95    fn push(&mut self, item: D::Value) {
96        Vec::push(self, item)
97    }
98    fn len(&self) -> usize {
99        Vec::len(self)
100    }
101    fn reserve(&mut self, size: usize) {
102        Vec::reserve(self, size)
103    }
104}
105
106#[allow(type_alias_bounds)]
107pub type SnapshotVecStorage<D: SnapshotVecDelegate> =
108    SnapshotVec<D, Vec<<D as SnapshotVecDelegate>::Value>, ()>;
109
110pub struct SnapshotVec<
111    D: SnapshotVecDelegate,
112    V: VecLike<D> = Vec<<D as SnapshotVecDelegate>::Value>,
113    L = VecLog<UndoLog<D>>,
114> {
115    values: V,
116    undo_log: L,
117    _marker: PhantomData<D>,
118}
119
120impl<D, V, L> fmt::Debug for SnapshotVec<D, V, L>
121where
122    D: SnapshotVecDelegate,
123    V: VecLike<D> + fmt::Debug,
124    L: fmt::Debug,
125{
126    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
127        fmt.debug_struct("SnapshotVec")
128            .field("values", &self.values)
129            .field("undo_log", &self.undo_log)
130            .finish()
131    }
132}
133
134// Snapshots are tokens that should be created/consumed linearly.
135pub struct Snapshot<S = ::undo_log::Snapshot> {
136    pub(crate) value_count: usize,
137    snapshot: S,
138}
139
140pub trait SnapshotVecDelegate {
141    type Value;
142    type Undo;
143
144    fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
145}
146
147// HACK(eddyb) manual impl avoids `Default` bound on `D`.
148impl<D: SnapshotVecDelegate, V: VecLike<D> + Default, L: Default> Default for SnapshotVec<D, V, L> {
149    fn default() -> Self {
150        SnapshotVec {
151            values: V::default(),
152            undo_log: Default::default(),
153            _marker: PhantomData,
154        }
155    }
156}
157
158impl<D: SnapshotVecDelegate, V: VecLike<D> + Default, L: Default> SnapshotVec<D, V, L> {
159    /// Creates a new `SnapshotVec`. If `L` is set to `()` then most mutating functions will not
160    /// be accessible without calling `with_log` and supplying a compatibly `UndoLogs` instance.
161    pub fn new() -> Self {
162        Self::default()
163    }
164}
165
166impl<D: SnapshotVecDelegate> SnapshotVecStorage<D> {
167    /// Creates a `SnapshotVec` using the `undo_log`, allowing mutating methods to be called
168    pub fn with_log<'a, L>(
169        &'a mut self,
170        undo_log: L,
171    ) -> SnapshotVec<D, &'a mut Vec<<D as SnapshotVecDelegate>::Value>, L>
172    where
173        L: UndoLogs<UndoLog<D>>,
174    {
175        SnapshotVec {
176            values: &mut self.values,
177            undo_log,
178            _marker: PhantomData,
179        }
180    }
181}
182
183impl<D: SnapshotVecDelegate, L: Default> SnapshotVec<D, Vec<D::Value>, L> {
184    pub fn with_capacity(c: usize) -> Self {
185        SnapshotVec {
186            values: Vec::with_capacity(c),
187            undo_log: Default::default(),
188            _marker: PhantomData,
189        }
190    }
191}
192
193impl<V: VecLike<D>, D: SnapshotVecDelegate, U> SnapshotVec<D, V, U> {
194    pub fn len(&self) -> usize {
195        self.values.len()
196    }
197
198    pub fn get(&self, index: usize) -> &D::Value {
199        &self.values.as_ref()[index]
200    }
201
202    /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone
203    /// automatically, so you should be sure call `record()` with some sort of suitable undo
204    /// action.
205    pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
206        &mut self.values.as_mut()[index]
207    }
208
209    /// Reserve space for new values, just like an ordinary vec.
210    pub fn reserve(&mut self, additional: usize) {
211        // This is not affected by snapshots or anything.
212        self.values.reserve(additional);
213    }
214}
215
216impl<V: VecLike<D>, D: SnapshotVecDelegate, L: UndoLogs<UndoLog<D>>> SnapshotVec<D, V, L> {
217    fn in_snapshot(&self) -> bool {
218        self.undo_log.in_snapshot()
219    }
220
221    pub fn record(&mut self, action: D::Undo) {
222        if self.in_snapshot() {
223            self.undo_log.push(Other(action));
224        }
225    }
226
227    pub fn push(&mut self, elem: D::Value) -> usize {
228        let len = self.values.len();
229        self.values.push(elem);
230
231        if self.in_snapshot() {
232            self.undo_log.push(NewElem(len));
233        }
234
235        len
236    }
237
238    /// Updates the element at the given index. The old value will saved (and perhaps restored) if
239    /// a snapshot is active.
240    pub fn set(&mut self, index: usize, new_elem: D::Value) {
241        let old_elem = mem::replace(&mut self.values.as_mut()[index], new_elem);
242        if self.undo_log.in_snapshot() {
243            self.undo_log.push(SetElem(index, old_elem));
244        }
245    }
246
247    /// Updates all elements. Potentially more efficient -- but
248    /// otherwise equivalent to -- invoking `set` for each element.
249    pub fn set_all(&mut self, mut new_elems: impl FnMut(usize) -> D::Value) {
250        if !self.undo_log.in_snapshot() {
251            for (index, slot) in self.values.as_mut().iter_mut().enumerate() {
252                *slot = new_elems(index);
253            }
254        } else {
255            for i in 0..self.values.len() {
256                self.set(i, new_elems(i));
257            }
258        }
259    }
260
261    pub fn update<OP>(&mut self, index: usize, op: OP)
262    where
263        OP: FnOnce(&mut D::Value),
264        D::Value: Clone,
265    {
266        if self.undo_log.in_snapshot() {
267            let old_elem = self.values.as_mut()[index].clone();
268            self.undo_log.push(SetElem(index, old_elem));
269        }
270        op(&mut self.values.as_mut()[index]);
271    }
272}
273
274impl<D, V, L> SnapshotVec<D, V, L>
275where
276    D: SnapshotVecDelegate,
277    V: VecLike<D> + Rollback<UndoLog<D>>,
278    L: Snapshots<UndoLog<D>>,
279{
280    pub fn start_snapshot(&mut self) -> Snapshot<L::Snapshot> {
281        Snapshot {
282            value_count: self.values.len(),
283            snapshot: self.undo_log.start_snapshot(),
284        }
285    }
286
287    pub fn actions_since_snapshot(&self, snapshot: &Snapshot<L::Snapshot>) -> &[UndoLog<D>] {
288        self.undo_log.actions_since_snapshot(&snapshot.snapshot)
289    }
290
291    pub fn rollback_to(&mut self, snapshot: Snapshot<L::Snapshot>) {
292        let values = &mut self.values;
293        self.undo_log.rollback_to(|| values, snapshot.snapshot);
294    }
295
296    /// Commits all changes since the last snapshot. Of course, they
297    /// can still be undone if there is a snapshot further out.
298    pub fn commit(&mut self, snapshot: Snapshot<L::Snapshot>) {
299        self.undo_log.commit(snapshot.snapshot);
300    }
301}
302
303impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::Deref for SnapshotVec<D, V, L> {
304    type Target = [D::Value];
305    fn deref(&self) -> &[D::Value] {
306        self.values.as_ref()
307    }
308}
309
310impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::DerefMut for SnapshotVec<D, V, L> {
311    fn deref_mut(&mut self) -> &mut [D::Value] {
312        self.values.as_mut()
313    }
314}
315
316impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::Index<usize> for SnapshotVec<D, V, L> {
317    type Output = D::Value;
318    fn index(&self, index: usize) -> &D::Value {
319        self.get(index)
320    }
321}
322
323impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::IndexMut<usize> for SnapshotVec<D, V, L> {
324    fn index_mut(&mut self, index: usize) -> &mut D::Value {
325        self.get_mut(index)
326    }
327}
328
329impl<D: SnapshotVecDelegate, V: VecLike<D> + Extend<D::Value>> Extend<D::Value>
330    for SnapshotVec<D, V>
331{
332    fn extend<T>(&mut self, iterable: T)
333    where
334        T: IntoIterator<Item = D::Value>,
335    {
336        let initial_len = self.values.len();
337        self.values.extend(iterable);
338        let final_len = self.values.len();
339
340        if self.in_snapshot() {
341            self.undo_log
342                .extend((initial_len..final_len).map(|len| NewElem(len)));
343        }
344    }
345}
346
347impl<D: SnapshotVecDelegate, V, L> Clone for SnapshotVec<D, V, L>
348where
349    V: VecLike<D> + Clone,
350    L: Clone,
351{
352    fn clone(&self) -> Self {
353        SnapshotVec {
354            values: self.values.clone(),
355            undo_log: self.undo_log.clone(),
356            _marker: PhantomData,
357        }
358    }
359}
360
361impl<D: SnapshotVecDelegate> Clone for UndoLog<D>
362where
363    D::Value: Clone,
364    D::Undo: Clone,
365{
366    fn clone(&self) -> Self {
367        match *self {
368            NewElem(i) => NewElem(i),
369            SetElem(i, ref v) => SetElem(i, v.clone()),
370            Other(ref u) => Other(u.clone()),
371        }
372    }
373}
374
375impl SnapshotVecDelegate for i32 {
376    type Value = i32;
377    type Undo = ();
378
379    fn reverse(_: &mut Vec<i32>, _: ()) {}
380}
381
382#[test]
383fn basic() {
384    let mut vec: SnapshotVec<i32> = SnapshotVec::default();
385    assert!(!vec.in_snapshot());
386    assert_eq!(vec.len(), 0);
387    vec.push(22);
388    vec.push(33);
389    assert_eq!(vec.len(), 2);
390    assert_eq!(*vec.get(0), 22);
391    assert_eq!(*vec.get(1), 33);
392    vec.set(1, 34);
393    assert_eq!(vec.len(), 2);
394    assert_eq!(*vec.get(0), 22);
395    assert_eq!(*vec.get(1), 34);
396
397    let snapshot = vec.start_snapshot();
398    assert!(vec.in_snapshot());
399
400    vec.push(44);
401    vec.push(55);
402    vec.set(1, 35);
403    assert_eq!(vec.len(), 4);
404    assert_eq!(*vec.get(0), 22);
405    assert_eq!(*vec.get(1), 35);
406    assert_eq!(*vec.get(2), 44);
407    assert_eq!(*vec.get(3), 55);
408
409    vec.rollback_to(snapshot);
410    assert!(!vec.in_snapshot());
411
412    assert_eq!(vec.len(), 2);
413    assert_eq!(*vec.get(0), 22);
414    assert_eq!(*vec.get(1), 34);
415}
416
417#[test]
418#[should_panic]
419fn out_of_order() {
420    let mut vec: SnapshotVec<i32> = SnapshotVec::default();
421    vec.push(22);
422    let snapshot1 = vec.start_snapshot();
423    vec.push(33);
424    let snapshot2 = vec.start_snapshot();
425    vec.push(44);
426    vec.rollback_to(snapshot1); // bogus, but accepted
427    vec.rollback_to(snapshot2); // asserts
428}
429
430#[test]
431fn nested_commit_then_rollback() {
432    let mut vec: SnapshotVec<i32> = SnapshotVec::default();
433    vec.push(22);
434    let snapshot1 = vec.start_snapshot();
435    let snapshot2 = vec.start_snapshot();
436    vec.set(0, 23);
437    vec.commit(snapshot2);
438    assert_eq!(*vec.get(0), 23);
439    vec.rollback_to(snapshot1);
440    assert_eq!(*vec.get(0), 22);
441}