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.
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.
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.
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
26 pub enum UndoLog<D: SnapshotVecDelegate> {
27 /// Indicates where a snapshot started.
30 /// Indicates a snapshot that has been committed.
33 /// New variable with given index was created.
36 /// Variable with given index was changed *from* the given value.
37 SetElem(usize, D::Value),
39 /// Extensible set of actions
43 pub struct SnapshotVec<D: SnapshotVecDelegate> {
44 values: Vec<D::Value>,
45 undo_log: Vec<UndoLog<D>>,
48 // Snapshots are tokens that should be created/consumed linearly.
50 // Length of the undo log at the time the snapshot was taken.
54 pub trait SnapshotVecDelegate {
58 fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
61 impl<D: SnapshotVecDelegate> SnapshotVec<D> {
62 pub fn new() -> SnapshotVec<D> {
69 fn in_snapshot(&self) -> bool {
70 !self.undo_log.is_empty()
73 pub fn record(&mut self, action: D::Undo) {
74 if self.in_snapshot() {
75 self.undo_log.push(Other(action));
79 pub fn len(&self) -> usize {
83 pub fn push(&mut self, elem: D::Value) -> usize {
84 let len = self.values.len();
85 self.values.push(elem);
87 if self.in_snapshot() {
88 self.undo_log.push(NewElem(len));
94 pub fn get(&self, index: usize) -> &D::Value {
98 /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone
99 /// automatically, so you should be sure call `record()` with some sort of suitable undo
101 pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
102 &mut self.values[index]
105 /// Updates the element at the given index. The old value will saved (and perhaps restored) if
106 /// a snapshot is active.
107 pub fn set(&mut self, index: usize, new_elem: D::Value) {
108 let old_elem = mem::replace(&mut self.values[index], new_elem);
109 if self.in_snapshot() {
110 self.undo_log.push(SetElem(index, old_elem));
114 pub fn start_snapshot(&mut self) -> Snapshot {
115 let length = self.undo_log.len();
116 self.undo_log.push(OpenSnapshot);
117 Snapshot { length: length }
120 pub fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[UndoLog<D>] {
121 &self.undo_log[snapshot.length..]
124 fn assert_open_snapshot(&self, snapshot: &Snapshot) {
125 // Or else there was a failure to follow a stack discipline:
126 assert!(self.undo_log.len() > snapshot.length);
128 // Invariant established by start_snapshot():
129 assert!(match self.undo_log[snapshot.length] {
130 OpenSnapshot => true,
135 pub fn rollback_to(&mut self, snapshot: Snapshot) {
136 debug!("rollback_to({})", snapshot.length);
138 self.assert_open_snapshot(&snapshot);
140 while self.undo_log.len() > snapshot.length + 1 {
141 match self.undo_log.pop().unwrap() {
143 // This indicates a failure to obey the stack discipline.
144 panic!("Cannot rollback an uncommitted snapshot");
147 CommittedSnapshot => {
148 // This occurs when there are nested snapshots and
149 // the inner is committed but outer is rolled back.
154 assert!(self.values.len() == i);
162 D::reverse(&mut self.values, u);
167 let v = self.undo_log.pop().unwrap();
169 OpenSnapshot => true,
172 assert!(self.undo_log.len() == snapshot.length);
175 /// Commits all changes since the last snapshot. Of course, they
176 /// can still be undone if there is a snapshot further out.
177 pub fn commit(&mut self, snapshot: Snapshot) {
178 debug!("commit({})", snapshot.length);
180 self.assert_open_snapshot(&snapshot);
182 if snapshot.length == 0 {
183 // The root snapshot.
184 self.undo_log.truncate(0);
186 self.undo_log[snapshot.length] = CommittedSnapshot;
191 impl<D: SnapshotVecDelegate> ops::Deref for SnapshotVec<D> {
192 type Target = [D::Value];
193 fn deref(&self) -> &[D::Value] {
198 impl<D: SnapshotVecDelegate> ops::DerefMut for SnapshotVec<D> {
199 fn deref_mut(&mut self) -> &mut [D::Value] {
204 impl<D: SnapshotVecDelegate> ops::Index<usize> for SnapshotVec<D> {
205 type Output = D::Value;
206 fn index(&self, index: usize) -> &D::Value {
211 impl<D: SnapshotVecDelegate> ops::IndexMut<usize> for SnapshotVec<D> {
212 fn index_mut(&mut self, index: usize) -> &mut D::Value {
217 impl<D: SnapshotVecDelegate> Extend<D::Value> for SnapshotVec<D> {
218 fn extend<T>(&mut self, iterable: T) where T: IntoIterator<Item=D::Value> {
219 for item in iterable {