src/librustc_data_structures/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 use self::UndoLog::*;
  22
  23 use std::mem;
  24 use std::ops;
  25
  26 pub enum UndoLog<D: SnapshotVecDelegate> {
  27     /// Indicates where a snapshot started.
  28     OpenSnapshot,
  29
  30     /// Indicates a snapshot that has been committed.
  31     CommittedSnapshot,
  32
  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
  43 pub struct SnapshotVec<D: SnapshotVecDelegate> {
  44     values: Vec<D::Value>,
  45     undo_log: Vec<UndoLog<D>>,
  46 }
  47
  48 // Snapshots are tokens that should be created/consumed linearly.
  49 pub struct Snapshot {
  50     // Length of the undo log at the time the snapshot was taken.
  51     length: usize,
  52 }
  53
  54 pub trait SnapshotVecDelegate {
  55     type Value;
  56     type Undo;
  57
  58     fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
  59 }
  60
  61 impl<D: SnapshotVecDelegate> SnapshotVec<D> {
  62     pub fn new() -> SnapshotVec<D> {
  63         SnapshotVec {
  64             values: Vec::new(),
  65             undo_log: Vec::new(),
  66         }
  67     }
  68
  69     fn in_snapshot(&self) -> bool {
  70         !self.undo_log.is_empty()
  71     }
  72
  73     pub fn record(&mut self, action: D::Undo) {
  74         if self.in_snapshot() {
  75             self.undo_log.push(Other(action));
  76         }
  77     }
  78
  79     pub fn len(&self) -> usize {
  80         self.values.len()
  81     }
  82
  83     pub fn push(&mut self, elem: D::Value) -> usize {
  84         let len = self.values.len();
  85         self.values.push(elem);
  86
  87         if self.in_snapshot() {
  88             self.undo_log.push(NewElem(len));
  89         }
  90
  91         len
  92     }
  93
  94     pub fn get(&self, index: usize) -> &D::Value {
  95         &self.values[index]
  96     }
  97
  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
 100     /// action.
 101     pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
 102         &mut self.values[index]
 103     }
 104
 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));
 111         }
 112     }
 113
 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 }
 118     }
 119
 120     pub fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[UndoLog<D>] {
 121         &self.undo_log[snapshot.length..]
 122     }
 123
 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);
 127
 128         // Invariant established by start_snapshot():
 129         assert!(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                     D::reverse(&mut self.values, u);
 163                 }
 164             }
 165         }
 166
 167         let v = self.undo_log.pop().unwrap();
 168         assert!(match v {
 169             OpenSnapshot => true,
 170             _ => false,
 171         });
 172         assert!(self.undo_log.len() == snapshot.length);
 173     }
 174
 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);
 179
 180         self.assert_open_snapshot(&snapshot);
 181
 182         if snapshot.length == 0 {
 183             // The root snapshot.
 184             self.undo_log.truncate(0);
 185         } else {
 186             self.undo_log[snapshot.length] = CommittedSnapshot;
 187         }
 188     }
 189 }
 190
 191 impl<D: SnapshotVecDelegate> ops::Deref for SnapshotVec<D> {
 192     type Target = [D::Value];
 193     fn deref(&self) -> &[D::Value] {
 194         &*self.values
 195     }
 196 }
 197
 198 impl<D: SnapshotVecDelegate> ops::DerefMut for SnapshotVec<D> {
 199     fn deref_mut(&mut self) -> &mut [D::Value] {
 200         &mut *self.values
 201     }
 202 }
 203
 204 impl<D: SnapshotVecDelegate> ops::Index<usize> for SnapshotVec<D> {
 205     type Output = D::Value;
 206     fn index(&self, index: usize) -> &D::Value {
 207         self.get(index)
 208     }
 209 }
 210
 211 impl<D: SnapshotVecDelegate> ops::IndexMut<usize> for SnapshotVec<D> {
 212     fn index_mut(&mut self, index: usize) -> &mut D::Value {
 213         self.get_mut(index)
 214     }
 215 }