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<'a>(&'a self, index: usize) -> &'a 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<'a>(&'a mut self, index: usize) -> &'a 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,
 121                                   snapshot: &Snapshot)
 122                                   -> &[UndoLog<D>] {
 123         &self.undo_log[snapshot.length..]
 124     }
 125
 126     fn assert_open_snapshot(&self, snapshot: &Snapshot) {
 127         // Or else there was a failure to follow a stack discipline:
 128         assert!(self.undo_log.len() > snapshot.length);
 129
 130         // Invariant established by start_snapshot():
 131         assert!(
 132             match self.undo_log[snapshot.length] {
 133                 OpenSnapshot => true,
 134                 _ => false
 135             });
 136     }
 137
 138     pub fn rollback_to(&mut self, snapshot: Snapshot) {
 139         debug!("rollback_to({})", snapshot.length);
 140
 141         self.assert_open_snapshot(&snapshot);
 142
 143         while self.undo_log.len() > snapshot.length + 1 {
 144             match self.undo_log.pop().unwrap() {
 145                 OpenSnapshot => {
 146                     // This indicates a failure to obey the stack discipline.
 147                     panic!("Cannot rollback an uncommitted snapshot");
 148                 }
 149
 150                 CommittedSnapshot => {
 151                     // This occurs when there are nested snapshots and
 152                     // the inner is committed but outer is rolled back.
 153                 }
 154
 155                 NewElem(i) => {
 156                     self.values.pop();
 157                     assert!(self.values.len() == i);
 158                 }
 159
 160                 SetElem(i, v) => {
 161                     self.values[i] = v;
 162                 }
 163
 164                 Other(u) => {
 165                     D::reverse(&mut self.values, u);
 166                 }
 167             }
 168         }
 169
 170         let v = self.undo_log.pop().unwrap();
 171         assert!(match v { OpenSnapshot => true, _ => false });
 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] { &*self.values }
 194 }
 195
 196 impl<D:SnapshotVecDelegate> ops::DerefMut for SnapshotVec<D> {
 197     fn deref_mut(&mut self) -> &mut [D::Value] { &mut *self.values }
 198 }
 199
 200 impl<D:SnapshotVecDelegate> ops::Index<usize> for SnapshotVec<D> {
 201     type Output = D::Value;
 202     fn index(&self, index: usize) -> &D::Value { self.get(index) }
 203 }
 204
 205 impl<D:SnapshotVecDelegate> ops::IndexMut<usize> for SnapshotVec<D> {
 206     fn index_mut(&mut self, index: usize) -> &mut D::Value { self.get_mut(index) }
 207 }