1use 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 NewElem(usize),
35
36 SetElem(usize, D::Value),
38
39 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
134pub 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
147impl<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 pub fn new() -> Self {
162 Self::default()
163 }
164}
165
166impl<D: SnapshotVecDelegate> SnapshotVecStorage<D> {
167 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 pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
206 &mut self.values.as_mut()[index]
207 }
208
209 pub fn reserve(&mut self, additional: usize) {
211 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 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 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 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); vec.rollback_to(snapshot2); }
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}