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 abitrary 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 #[deriving(PartialEq)]
  26 pub enum UndoLog<T,U> {
  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(uint),
  35
  36     /// Variable with given index was changed *from* the given value.
  37     SetElem(uint, T),
  38
  39     /// Extensible set of actions
  40     Other(U)
  41 }
  42
  43 pub struct SnapshotVec<T,U,D> {
  44     values: Vec<T>,
  45     undo_log: Vec<UndoLog<T,U>>,
  46     delegate: D
  47 }
  48
  49 // Snapshots are tokens that should be created/consumed linearly.
  50 #[allow(missing_copy_implementations)]
  51 pub struct Snapshot {
  52     // Length of the undo log at the time the snapshot was taken.
  53     length: uint,
  54 }
  55
  56 pub trait SnapshotVecDelegate<T,U> {
  57     fn reverse(&mut self, values: &mut Vec<T>, action: U);
  58 }
  59
  60 impl<T,U,D:SnapshotVecDelegate<T,U>> SnapshotVec<T,U,D> {
  61     pub fn new(delegate: D) -> SnapshotVec<T,U,D> {
  62         SnapshotVec {
  63             values: Vec::new(),
  64             undo_log: Vec::new(),
  65             delegate: delegate
  66         }
  67     }
  68
  69     fn in_snapshot(&self) -> bool {
  70         !self.undo_log.is_empty()
  71     }
  72
  73     pub fn record(&mut self, action: U) {
  74         if self.in_snapshot() {
  75             self.undo_log.push(Other(action));
  76         }
  77     }
  78
  79     pub fn push(&mut self, elem: T) -> uint {
  80         let len = self.values.len();
  81         self.values.push(elem);
  82
  83         if self.in_snapshot() {
  84             self.undo_log.push(NewElem(len));
  85         }
  86
  87         len
  88     }
  89
  90     pub fn get<'a>(&'a self, index: uint) -> &'a T {
  91         &self.values[index]
  92     }
  93
  94     /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone
  95     /// automatically, so you should be sure call `record()` with some sort of suitable undo
  96     /// action.
  97     pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
  98         &mut self.values[index]
  99     }
 100
 101     /// Updates the element at the given index. The old value will saved (and perhaps restored) if
 102     /// a snapshot is active.
 103     pub fn set(&mut self, index: uint, new_elem: T) {
 104         let old_elem = mem::replace(&mut self.values[index], new_elem);
 105         if self.in_snapshot() {
 106             self.undo_log.push(SetElem(index, old_elem));
 107         }
 108     }
 109
 110     pub fn start_snapshot(&mut self) -> Snapshot {
 111         let length = self.undo_log.len();
 112         self.undo_log.push(OpenSnapshot);
 113         Snapshot { length: length }
 114     }
 115
 116     pub fn actions_since_snapshot(&self,
 117                                   snapshot: &Snapshot)
 118                                   -> &[UndoLog<T,U>] {
 119         self.undo_log[snapshot.length..]
 120     }
 121
 122     fn assert_open_snapshot(&self, snapshot: &Snapshot) {
 123         // Or else there was a failure to follow a stack discipline:
 124         assert!(self.undo_log.len() > snapshot.length);
 125
 126         // Invariant established by start_snapshot():
 127         assert!(
 128             match self.undo_log[snapshot.length] {
 129                 OpenSnapshot => true,
 130                 _ => false
 131             });
 132     }
 133
 134     pub fn rollback_to(&mut self, snapshot: Snapshot) {
 135         debug!("rollback_to({})", snapshot.length);
 136
 137         self.assert_open_snapshot(&snapshot);
 138
 139         while self.undo_log.len() > snapshot.length + 1 {
 140             match self.undo_log.pop().unwrap() {
 141                 OpenSnapshot => {
 142                     // This indicates a failure to obey the stack discipline.
 143                     panic!("Cannot rollback an uncommitted snapshot");
 144                 }
 145
 146                 CommittedSnapshot => {
 147                     // This occurs when there are nested snapshots and
 148                     // the inner is committed but outer is rolled back.
 149                 }
 150
 151                 NewElem(i) => {
 152                     self.values.pop();
 153                     assert!(self.values.len() == i);
 154                 }
 155
 156                 SetElem(i, v) => {
 157                     self.values[i] = v;
 158                 }
 159
 160                 Other(u) => {
 161                     self.delegate.reverse(&mut self.values, u);
 162                 }
 163             }
 164         }
 165
 166         let v = self.undo_log.pop().unwrap();
 167         assert!(match v { OpenSnapshot => true, _ => false });
 168         assert!(self.undo_log.len() == snapshot.length);
 169     }
 170
 171     /// Commits all changes since the last snapshot. Of course, they
 172     /// can still be undone if there is a snapshot further out.
 173     pub fn commit(&mut self, snapshot: Snapshot) {
 174         debug!("commit({})", snapshot.length);
 175
 176         self.assert_open_snapshot(&snapshot);
 177
 178         if snapshot.length == 0 {
 179             // The root snapshot.
 180             self.undo_log.truncate(0);
 181         } else {
 182             self.undo_log[snapshot.length] = CommittedSnapshot;
 183         }
 184     }
 185 }