]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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 | use self::UndoLog::*; | |
22 | ||
23 | use std::mem; | |
24 | ||
85aaf69f | 25 | pub enum UndoLog<D:SnapshotVecDelegate> { |
1a4d82fc JJ |
26 | /// Indicates where a snapshot started. |
27 | OpenSnapshot, | |
28 | ||
29 | /// Indicates a snapshot that has been committed. | |
30 | CommittedSnapshot, | |
31 | ||
32 | /// New variable with given index was created. | |
c34b1796 | 33 | NewElem(usize), |
1a4d82fc JJ |
34 | |
35 | /// Variable with given index was changed *from* the given value. | |
c34b1796 | 36 | SetElem(usize, D::Value), |
1a4d82fc JJ |
37 | |
38 | /// Extensible set of actions | |
85aaf69f | 39 | Other(D::Undo) |
1a4d82fc JJ |
40 | } |
41 | ||
85aaf69f SL |
42 | pub struct SnapshotVec<D:SnapshotVecDelegate> { |
43 | values: Vec<D::Value>, | |
44 | undo_log: Vec<UndoLog<D>>, | |
1a4d82fc JJ |
45 | delegate: D |
46 | } | |
47 | ||
48 | // Snapshots are tokens that should be created/consumed linearly. | |
1a4d82fc JJ |
49 | pub struct Snapshot { |
50 | // Length of the undo log at the time the snapshot was taken. | |
c34b1796 | 51 | length: usize, |
1a4d82fc JJ |
52 | } |
53 | ||
85aaf69f SL |
54 | pub trait SnapshotVecDelegate { |
55 | type Value; | |
56 | type Undo; | |
57 | ||
58 | fn reverse(&mut self, values: &mut Vec<Self::Value>, action: Self::Undo); | |
1a4d82fc JJ |
59 | } |
60 | ||
85aaf69f SL |
61 | impl<D:SnapshotVecDelegate> SnapshotVec<D> { |
62 | pub fn new(delegate: D) -> SnapshotVec<D> { | |
1a4d82fc JJ |
63 | SnapshotVec { |
64 | values: Vec::new(), | |
65 | undo_log: Vec::new(), | |
66 | delegate: delegate | |
67 | } | |
68 | } | |
69 | ||
70 | fn in_snapshot(&self) -> bool { | |
71 | !self.undo_log.is_empty() | |
72 | } | |
73 | ||
85aaf69f | 74 | pub fn record(&mut self, action: D::Undo) { |
1a4d82fc JJ |
75 | if self.in_snapshot() { |
76 | self.undo_log.push(Other(action)); | |
77 | } | |
78 | } | |
79 | ||
c34b1796 | 80 | pub fn push(&mut self, elem: D::Value) -> usize { |
1a4d82fc JJ |
81 | let len = self.values.len(); |
82 | self.values.push(elem); | |
83 | ||
84 | if self.in_snapshot() { | |
85 | self.undo_log.push(NewElem(len)); | |
86 | } | |
87 | ||
88 | len | |
89 | } | |
90 | ||
c34b1796 | 91 | pub fn get<'a>(&'a self, index: usize) -> &'a D::Value { |
1a4d82fc JJ |
92 | &self.values[index] |
93 | } | |
94 | ||
95 | /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone | |
96 | /// automatically, so you should be sure call `record()` with some sort of suitable undo | |
97 | /// action. | |
c34b1796 | 98 | pub fn get_mut<'a>(&'a mut self, index: usize) -> &'a mut D::Value { |
1a4d82fc JJ |
99 | &mut self.values[index] |
100 | } | |
101 | ||
102 | /// Updates the element at the given index. The old value will saved (and perhaps restored) if | |
103 | /// a snapshot is active. | |
c34b1796 | 104 | pub fn set(&mut self, index: usize, new_elem: D::Value) { |
1a4d82fc JJ |
105 | let old_elem = mem::replace(&mut self.values[index], new_elem); |
106 | if self.in_snapshot() { | |
107 | self.undo_log.push(SetElem(index, old_elem)); | |
108 | } | |
109 | } | |
110 | ||
111 | pub fn start_snapshot(&mut self) -> Snapshot { | |
112 | let length = self.undo_log.len(); | |
113 | self.undo_log.push(OpenSnapshot); | |
114 | Snapshot { length: length } | |
115 | } | |
116 | ||
117 | pub fn actions_since_snapshot(&self, | |
118 | snapshot: &Snapshot) | |
85aaf69f | 119 | -> &[UndoLog<D>] { |
1a4d82fc JJ |
120 | &self.undo_log[snapshot.length..] |
121 | } | |
122 | ||
123 | fn assert_open_snapshot(&self, snapshot: &Snapshot) { | |
124 | // Or else there was a failure to follow a stack discipline: | |
125 | assert!(self.undo_log.len() > snapshot.length); | |
126 | ||
127 | // Invariant established by start_snapshot(): | |
128 | assert!( | |
129 | match self.undo_log[snapshot.length] { | |
130 | OpenSnapshot => true, | |
131 | _ => false | |
132 | }); | |
133 | } | |
134 | ||
135 | pub fn rollback_to(&mut self, snapshot: Snapshot) { | |
136 | debug!("rollback_to({})", snapshot.length); | |
137 | ||
138 | self.assert_open_snapshot(&snapshot); | |
139 | ||
140 | while self.undo_log.len() > snapshot.length + 1 { | |
141 | match self.undo_log.pop().unwrap() { | |
142 | OpenSnapshot => { | |
143 | // This indicates a failure to obey the stack discipline. | |
144 | panic!("Cannot rollback an uncommitted snapshot"); | |
145 | } | |
146 | ||
147 | CommittedSnapshot => { | |
148 | // This occurs when there are nested snapshots and | |
149 | // the inner is committed but outer is rolled back. | |
150 | } | |
151 | ||
152 | NewElem(i) => { | |
153 | self.values.pop(); | |
154 | assert!(self.values.len() == i); | |
155 | } | |
156 | ||
157 | SetElem(i, v) => { | |
158 | self.values[i] = v; | |
159 | } | |
160 | ||
161 | Other(u) => { | |
162 | self.delegate.reverse(&mut self.values, u); | |
163 | } | |
164 | } | |
165 | } | |
166 | ||
167 | let v = self.undo_log.pop().unwrap(); | |
168 | assert!(match v { OpenSnapshot => true, _ => false }); | |
169 | assert!(self.undo_log.len() == snapshot.length); | |
170 | } | |
171 | ||
172 | /// Commits all changes since the last snapshot. Of course, they | |
173 | /// can still be undone if there is a snapshot further out. | |
174 | pub fn commit(&mut self, snapshot: Snapshot) { | |
175 | debug!("commit({})", snapshot.length); | |
176 | ||
177 | self.assert_open_snapshot(&snapshot); | |
178 | ||
179 | if snapshot.length == 0 { | |
180 | // The root snapshot. | |
181 | self.undo_log.truncate(0); | |
182 | } else { | |
183 | self.undo_log[snapshot.length] = CommittedSnapshot; | |
184 | } | |
185 | } | |
186 | } |