src/vendor/ena/src/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
  22 use self::UndoLog::*;
  23
  24 use std::fmt;
  25 use std::mem;
  26 use std::ops;
  27
  28 #[derive(Debug)]
  29 pub enum UndoLog<D: SnapshotVecDelegate> {
  30     /// Indicates where a snapshot started.
  31     OpenSnapshot,
  32
  33     /// Indicates a snapshot that has been committed.
  34     CommittedSnapshot,
  35
  36     /// New variable with given index was created.
  37     NewElem(usize),
  38
  39     /// Variable with given index was changed *from* the given value.
  40     SetElem(usize, D::Value),
  41
  42     /// Extensible set of actions
  43     Other(D::Undo),
  44 }
  45
  46 pub struct SnapshotVec<D: SnapshotVecDelegate> {
  47     values: Vec<D::Value>,
  48     undo_log: Vec<UndoLog<D>>,
  49 }
  50
  51 impl<D> fmt::Debug for SnapshotVec<D>
  52     where D: SnapshotVecDelegate,
  53           D: fmt::Debug,
  54           D::Undo: fmt::Debug,
  55           D::Value: fmt::Debug
  56 {
  57     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
  58         fmt.debug_struct("SnapshotVec")
  59             .field("values", &self.values)
  60             .field("undo_log", &self.undo_log)
  61             .finish()
  62     }
  63 }
  64
  65 // Snapshots are tokens that should be created/consumed linearly.
  66 pub struct Snapshot {
  67     // Length of the undo log at the time the snapshot was taken.
  68     length: usize,
  69 }
  70
  71 pub trait SnapshotVecDelegate {
  72     type Value;
  73     type Undo;
  74
  75     fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
  76 }
  77
  78 impl<D: SnapshotVecDelegate> SnapshotVec<D> {
  79     pub fn new() -> SnapshotVec<D> {
  80         SnapshotVec {
  81             values: Vec::new(),
  82             undo_log: Vec::new(),
  83         }
  84     }
  85
  86     pub fn with_capacity(c: usize) -> SnapshotVec<D> {
  87         SnapshotVec {
  88             values: Vec::with_capacity(c),
  89             undo_log: Vec::new(),
  90         }
  91     }
  92
  93     fn in_snapshot(&self) -> bool {
  94         !self.undo_log.is_empty()
  95     }
  96
  97     pub fn record(&mut self, action: D::Undo) {
  98         if self.in_snapshot() {
  99             self.undo_log.push(Other(action));
 100         }
 101     }
 102
 103     pub fn len(&self) -> usize {
 104         self.values.len()
 105     }
 106
 107     pub fn push(&mut self, elem: D::Value) -> usize {
 108         let len = self.values.len();
 109         self.values.push(elem);
 110
 111         if self.in_snapshot() {
 112             self.undo_log.push(NewElem(len));
 113         }
 114
 115         len
 116     }
 117
 118     pub fn get(&self, index: usize) -> &D::Value {
 119         &self.values[index]
 120     }
 121
 122     /// Reserve space for new values, just like an ordinary vec.
 123     pub fn reserve(&mut self, additional: usize) {
 124         // This is not affected by snapshots or anything.
 125         self.values.reserve(additional);
 126     }
 127
 128     /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone
 129     /// automatically, so you should be sure call `record()` with some sort of suitable undo
 130     /// action.
 131     pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
 132         &mut self.values[index]
 133     }
 134
 135     /// Updates the element at the given index. The old value will saved (and perhaps restored) if
 136     /// a snapshot is active.
 137     pub fn set(&mut self, index: usize, new_elem: D::Value) {
 138         let old_elem = mem::replace(&mut self.values[index], new_elem);
 139         if self.in_snapshot() {
 140             self.undo_log.push(SetElem(index, old_elem));
 141         }
 142     }
 143
 144     /// Updates all elements. Potentially more efficient -- but
 145     /// otherwise equivalent to -- invoking `set` for each element.
 146     pub fn set_all(&mut self, mut new_elems: impl FnMut(usize) -> D::Value) {
 147         if !self.in_snapshot() {
 148             for (slot, index) in self.values.iter_mut().zip(0..) {
 149                 *slot = new_elems(index);
 150             }
 151         } else {
 152             for i in 0..self.values.len() {
 153                 self.set(i, new_elems(i));
 154             }
 155         }
 156     }
 157
 158     pub fn update<OP>(&mut self, index: usize, op: OP)
 159     where
 160         OP: FnOnce(&mut D::Value),
 161         D::Value: Clone,
 162     {
 163         if self.in_snapshot() {
 164             let old_elem = self.values[index].clone();
 165             self.undo_log.push(SetElem(index, old_elem));
 166         }
 167         op(&mut self.values[index]);
 168     }
 169
 170     pub fn start_snapshot(&mut self) -> Snapshot {
 171         let length = self.undo_log.len();
 172         self.undo_log.push(OpenSnapshot);
 173         Snapshot { length: length }
 174     }
 175
 176     pub fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[UndoLog<D>] {
 177         &self.undo_log[snapshot.length..]
 178     }
 179
 180     fn assert_open_snapshot(&self, snapshot: &Snapshot) {
 181         // Or else there was a failure to follow a stack discipline:
 182         assert!(self.undo_log.len() > snapshot.length);
 183
 184         // Invariant established by start_snapshot():
 185         assert!(match self.undo_log[snapshot.length] {
 186             OpenSnapshot => true,
 187             _ => false,
 188         });
 189     }
 190
 191     pub fn rollback_to(&mut self, snapshot: Snapshot) {
 192         debug!("rollback_to({})", snapshot.length);
 193
 194         self.assert_open_snapshot(&snapshot);
 195
 196         while self.undo_log.len() > snapshot.length + 1 {
 197             match self.undo_log.pop().unwrap() {
 198                 OpenSnapshot => {
 199                     // This indicates a failure to obey the stack discipline.
 200                     panic!("Cannot rollback an uncommitted snapshot");
 201                 }
 202
 203                 CommittedSnapshot => {
 204                     // This occurs when there are nested snapshots and
 205                     // the inner is committed but outer is rolled back.
 206                 }
 207
 208                 NewElem(i) => {
 209                     self.values.pop();
 210                     assert!(self.values.len() == i);
 211                 }
 212
 213                 SetElem(i, v) => {
 214                     self.values[i] = v;
 215                 }
 216
 217                 Other(u) => {
 218                     D::reverse(&mut self.values, u);
 219                 }
 220             }
 221         }
 222
 223         let v = self.undo_log.pop().unwrap();
 224         assert!(match v {
 225             OpenSnapshot => true,
 226             _ => false,
 227         });
 228         assert!(self.undo_log.len() == snapshot.length);
 229     }
 230
 231     /// Commits all changes since the last snapshot. Of course, they
 232     /// can still be undone if there is a snapshot further out.
 233     pub fn commit(&mut self, snapshot: Snapshot) {
 234         debug!("commit({})", snapshot.length);
 235
 236         self.assert_open_snapshot(&snapshot);
 237
 238         if snapshot.length == 0 {
 239             // The root snapshot.
 240             self.undo_log.truncate(0);
 241         } else {
 242             self.undo_log[snapshot.length] = CommittedSnapshot;
 243         }
 244     }
 245 }
 246
 247 impl<D: SnapshotVecDelegate> ops::Deref for SnapshotVec<D> {
 248     type Target = [D::Value];
 249     fn deref(&self) -> &[D::Value] {
 250         &*self.values
 251     }
 252 }
 253
 254 impl<D: SnapshotVecDelegate> ops::DerefMut for SnapshotVec<D> {
 255     fn deref_mut(&mut self) -> &mut [D::Value] {
 256         &mut *self.values
 257     }
 258 }
 259
 260 impl<D: SnapshotVecDelegate> ops::Index<usize> for SnapshotVec<D> {
 261     type Output = D::Value;
 262     fn index(&self, index: usize) -> &D::Value {
 263         self.get(index)
 264     }
 265 }
 266
 267 impl<D: SnapshotVecDelegate> ops::IndexMut<usize> for SnapshotVec<D> {
 268     fn index_mut(&mut self, index: usize) -> &mut D::Value {
 269         self.get_mut(index)
 270     }
 271 }
 272
 273 impl<D: SnapshotVecDelegate> Extend<D::Value> for SnapshotVec<D> {
 274     fn extend<T>(&mut self, iterable: T)
 275     where
 276         T: IntoIterator<Item = D::Value>,
 277     {
 278         for item in iterable {
 279             self.push(item);
 280         }
 281     }
 282 }
 283
 284 impl<D: SnapshotVecDelegate> Clone for SnapshotVec<D>
 285 where
 286     D::Value: Clone,
 287     D::Undo: Clone,
 288 {
 289     fn clone(&self) -> Self {
 290         SnapshotVec {
 291             values: self.values.clone(),
 292             undo_log: self.undo_log.clone(),
 293         }
 294     }
 295 }
 296
 297 impl<D: SnapshotVecDelegate> Clone for UndoLog<D>
 298 where
 299     D::Value: Clone,
 300     D::Undo: Clone,
 301 {
 302     fn clone(&self) -> Self {
 303         match *self {
 304             OpenSnapshot => OpenSnapshot,
 305             CommittedSnapshot => CommittedSnapshot,
 306             NewElem(i) => NewElem(i),
 307             SetElem(i, ref v) => SetElem(i, v.clone()),
 308             Other(ref u) => Other(u.clone()),
 309         }
 310     }
 311 }