src/librustc/util/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
  25 pub enum UndoLog<D:SnapshotVecDelegate> {
  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.
  33     NewElem(usize),
  34
  35     /// Variable with given index was changed *from* the given value.
  36     SetElem(usize, D::Value),
  37
  38     /// Extensible set of actions
  39     Other(D::Undo)
  40 }
  41
  42 pub struct SnapshotVec<D:SnapshotVecDelegate> {
  43     values: Vec<D::Value>,
  44     undo_log: Vec<UndoLog<D>>,
  45     delegate: 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(&mut self, values: &mut Vec<Self::Value>, action: Self::Undo);
  59 }
  60
  61 impl<D:SnapshotVecDelegate> SnapshotVec<D> {
  62     pub fn new(delegate: D) -> SnapshotVec<D> {
  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
  74     pub fn record(&mut self, action: D::Undo) {
  75         if self.in_snapshot() {
  76             self.undo_log.push(Other(action));
  77         }
  78     }
  79
  80     pub fn push(&mut self, elem: D::Value) -> usize {
  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
  91     pub fn get<'a>(&'a self, index: usize) -> &'a D::Value {
  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.
  98     pub fn get_mut<'a>(&'a mut self, index: usize) -> &'a mut D::Value {
  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.
 104     pub fn set(&mut self, index: usize, new_elem: D::Value) {
 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)
 119                                   -> &[UndoLog<D>] {
 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 }