From 52c34625866f6e23fd0de484282f326da6a100e3 Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Tue, 7 Apr 2015 06:11:49 -0400 Subject: Use the newer snapshot_vec, which has a simplified delegate interface since in practice no delegates had any state. --- src/librustc/lib.rs | 1 - src/librustc/middle/infer/type_variable.rs | 8 +- src/librustc/middle/infer/unify.rs | 6 +- src/librustc/util/snapshot_vec.rs | 186 ------------------------ src/librustc_data_structures/lib.rs | 2 + src/librustc_data_structures/snapshot_vec.rs | 207 +++++++++++++++++++++++++++ 6 files changed, 215 insertions(+), 195 deletions(-) delete mode 100644 src/librustc/util/snapshot_vec.rs create mode 100644 src/librustc_data_structures/snapshot_vec.rs (limited to 'src') diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs index 4f7bb3d528a..6837483a422 100644 --- a/src/librustc/lib.rs +++ b/src/librustc/lib.rs @@ -142,7 +142,6 @@ pub mod util { pub mod common; pub mod ppaux; pub mod nodemap; - pub mod snapshot_vec; pub mod lev_distance; } diff --git a/src/librustc/middle/infer/type_variable.rs b/src/librustc/middle/infer/type_variable.rs index 03612a6c1ae..b3e3e016d85 100644 --- a/src/librustc/middle/infer/type_variable.rs +++ b/src/librustc/middle/infer/type_variable.rs @@ -17,7 +17,7 @@ use std::cmp::min; use std::marker::PhantomData; use std::mem; use std::u32; -use util::snapshot_vec as sv; +use rustc_data_structures::snapshot_vec as sv; pub struct TypeVariableTable<'tcx> { values: sv::SnapshotVec>, @@ -65,7 +65,7 @@ impl RelationDir { impl<'tcx> TypeVariableTable<'tcx> { pub fn new() -> TypeVariableTable<'tcx> { - TypeVariableTable { values: sv::SnapshotVec::new(Delegate(PhantomData)) } + TypeVariableTable { values: sv::SnapshotVec::new() } } fn relations<'a>(&'a mut self, a: ty::TyVid) -> &'a mut Vec { @@ -201,9 +201,7 @@ impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> { type Value = TypeVariableData<'tcx>; type Undo = UndoEntry; - fn reverse(&mut self, - values: &mut Vec>, - action: UndoEntry) { + fn reverse(values: &mut Vec>, action: UndoEntry) { match action { SpecifyVar(vid, relations) => { values[vid.index as usize].value = Bounded(relations); diff --git a/src/librustc/middle/infer/unify.rs b/src/librustc/middle/infer/unify.rs index 4bbced1d75c..5aec4227136 100644 --- a/src/librustc/middle/infer/unify.rs +++ b/src/librustc/middle/infer/unify.rs @@ -17,7 +17,7 @@ use middle::ty::{self, Ty}; use std::fmt::Debug; use std::marker::PhantomData; use syntax::ast; -use util::snapshot_vec as sv; +use rustc_data_structures::snapshot_vec as sv; /// This trait is implemented by any type that can serve as a type /// variable. We call such variables *unification keys*. For example, @@ -95,7 +95,7 @@ pub struct Delegate(PhantomData); impl UnificationTable { pub fn new() -> UnificationTable { UnificationTable { - values: sv::SnapshotVec::new(Delegate(PhantomData)), + values: sv::SnapshotVec::new(), } } @@ -213,7 +213,7 @@ impl sv::SnapshotVecDelegate for Delegate { type Value = VarValue; type Undo = (); - fn reverse(&mut self, _: &mut Vec>, _: ()) { + fn reverse(_: &mut Vec>, _: ()) { panic!("Nothing to reverse"); } } diff --git a/src/librustc/util/snapshot_vec.rs b/src/librustc/util/snapshot_vec.rs deleted file mode 100644 index d2e0b3aec2f..00000000000 --- a/src/librustc/util/snapshot_vec.rs +++ /dev/null @@ -1,186 +0,0 @@ -// Copyright 2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! A utility class for implementing "snapshottable" things; a snapshottable data structure permits -//! you to take a snapshot (via `start_snapshot`) and then, after making some changes, elect either -//! to rollback to the start of the snapshot or commit those changes. -//! -//! This vector is intended to be used as part of an abstraction, not serve as a complete -//! abstraction on its own. As such, while it will roll back most changes on its own, it also -//! supports a `get_mut` operation that gives you an arbitrary mutable pointer into the vector. To -//! ensure that any changes you make this with this pointer are rolled back, you must invoke -//! `record` to record any changes you make and also supplying a delegate capable of reversing -//! those changes. -use self::UndoLog::*; - -use std::mem; - -pub enum UndoLog { - /// Indicates where a snapshot started. - OpenSnapshot, - - /// Indicates a snapshot that has been committed. - CommittedSnapshot, - - /// New variable with given index was created. - NewElem(usize), - - /// Variable with given index was changed *from* the given value. - SetElem(usize, D::Value), - - /// Extensible set of actions - Other(D::Undo) -} - -pub struct SnapshotVec { - values: Vec, - undo_log: Vec>, - delegate: D -} - -// Snapshots are tokens that should be created/consumed linearly. -pub struct Snapshot { - // Length of the undo log at the time the snapshot was taken. - length: usize, -} - -pub trait SnapshotVecDelegate { - type Value; - type Undo; - - fn reverse(&mut self, values: &mut Vec, action: Self::Undo); -} - -impl SnapshotVec { - pub fn new(delegate: D) -> SnapshotVec { - SnapshotVec { - values: Vec::new(), - undo_log: Vec::new(), - delegate: delegate - } - } - - fn in_snapshot(&self) -> bool { - !self.undo_log.is_empty() - } - - pub fn record(&mut self, action: D::Undo) { - if self.in_snapshot() { - self.undo_log.push(Other(action)); - } - } - - pub fn push(&mut self, elem: D::Value) -> usize { - let len = self.values.len(); - self.values.push(elem); - - if self.in_snapshot() { - self.undo_log.push(NewElem(len)); - } - - len - } - - pub fn get<'a>(&'a self, index: usize) -> &'a D::Value { - &self.values[index] - } - - /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone - /// automatically, so you should be sure call `record()` with some sort of suitable undo - /// action. - pub fn get_mut<'a>(&'a mut self, index: usize) -> &'a mut D::Value { - &mut self.values[index] - } - - /// Updates the element at the given index. The old value will saved (and perhaps restored) if - /// a snapshot is active. - pub fn set(&mut self, index: usize, new_elem: D::Value) { - let old_elem = mem::replace(&mut self.values[index], new_elem); - if self.in_snapshot() { - self.undo_log.push(SetElem(index, old_elem)); - } - } - - pub fn start_snapshot(&mut self) -> Snapshot { - let length = self.undo_log.len(); - self.undo_log.push(OpenSnapshot); - Snapshot { length: length } - } - - pub fn actions_since_snapshot(&self, - snapshot: &Snapshot) - -> &[UndoLog] { - &self.undo_log[snapshot.length..] - } - - fn assert_open_snapshot(&self, snapshot: &Snapshot) { - // Or else there was a failure to follow a stack discipline: - assert!(self.undo_log.len() > snapshot.length); - - // Invariant established by start_snapshot(): - assert!( - match self.undo_log[snapshot.length] { - OpenSnapshot => true, - _ => false - }); - } - - pub fn rollback_to(&mut self, snapshot: Snapshot) { - debug!("rollback_to({})", snapshot.length); - - self.assert_open_snapshot(&snapshot); - - while self.undo_log.len() > snapshot.length + 1 { - match self.undo_log.pop().unwrap() { - OpenSnapshot => { - // This indicates a failure to obey the stack discipline. - panic!("Cannot rollback an uncommitted snapshot"); - } - - CommittedSnapshot => { - // This occurs when there are nested snapshots and - // the inner is committed but outer is rolled back. - } - - NewElem(i) => { - self.values.pop(); - assert!(self.values.len() == i); - } - - SetElem(i, v) => { - self.values[i] = v; - } - - Other(u) => { - self.delegate.reverse(&mut self.values, u); - } - } - } - - let v = self.undo_log.pop().unwrap(); - assert!(match v { OpenSnapshot => true, _ => false }); - assert!(self.undo_log.len() == snapshot.length); - } - - /// Commits all changes since the last snapshot. Of course, they - /// can still be undone if there is a snapshot further out. - pub fn commit(&mut self, snapshot: Snapshot) { - debug!("commit({})", snapshot.length); - - self.assert_open_snapshot(&snapshot); - - if snapshot.length == 0 { - // The root snapshot. - self.undo_log.truncate(0); - } else { - self.undo_log[snapshot.length] = CommittedSnapshot; - } - } -} diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs index abac991e5ce..5f2f430df50 100644 --- a/src/librustc_data_structures/lib.rs +++ b/src/librustc_data_structures/lib.rs @@ -31,3 +31,5 @@ #[macro_use] extern crate log; extern crate serialize as rustc_serialize; // used by deriving + +pub mod snapshot_vec; diff --git a/src/librustc_data_structures/snapshot_vec.rs b/src/librustc_data_structures/snapshot_vec.rs new file mode 100644 index 00000000000..5ab740f3629 --- /dev/null +++ b/src/librustc_data_structures/snapshot_vec.rs @@ -0,0 +1,207 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! A utility class for implementing "snapshottable" things; a snapshottable data structure permits +//! you to take a snapshot (via `start_snapshot`) and then, after making some changes, elect either +//! to rollback to the start of the snapshot or commit those changes. +//! +//! This vector is intended to be used as part of an abstraction, not serve as a complete +//! abstraction on its own. As such, while it will roll back most changes on its own, it also +//! supports a `get_mut` operation that gives you an arbitrary mutable pointer into the vector. To +//! ensure that any changes you make this with this pointer are rolled back, you must invoke +//! `record` to record any changes you make and also supplying a delegate capable of reversing +//! those changes. +use self::UndoLog::*; + +use std::mem; +use std::ops; + +pub enum UndoLog { + /// Indicates where a snapshot started. + OpenSnapshot, + + /// Indicates a snapshot that has been committed. + CommittedSnapshot, + + /// New variable with given index was created. + NewElem(usize), + + /// Variable with given index was changed *from* the given value. + SetElem(usize, D::Value), + + /// Extensible set of actions + Other(D::Undo) +} + +pub struct SnapshotVec { + values: Vec, + undo_log: Vec>, +} + +// Snapshots are tokens that should be created/consumed linearly. +pub struct Snapshot { + // Length of the undo log at the time the snapshot was taken. + length: usize, +} + +pub trait SnapshotVecDelegate { + type Value; + type Undo; + + fn reverse(values: &mut Vec, action: Self::Undo); +} + +impl SnapshotVec { + pub fn new() -> SnapshotVec { + SnapshotVec { + values: Vec::new(), + undo_log: Vec::new(), + } + } + + fn in_snapshot(&self) -> bool { + !self.undo_log.is_empty() + } + + pub fn record(&mut self, action: D::Undo) { + if self.in_snapshot() { + self.undo_log.push(Other(action)); + } + } + + pub fn len(&self) -> usize { + self.values.len() + } + + pub fn push(&mut self, elem: D::Value) -> usize { + let len = self.values.len(); + self.values.push(elem); + + if self.in_snapshot() { + self.undo_log.push(NewElem(len)); + } + + len + } + + pub fn get<'a>(&'a self, index: usize) -> &'a D::Value { + &self.values[index] + } + + /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone + /// automatically, so you should be sure call `record()` with some sort of suitable undo + /// action. + pub fn get_mut<'a>(&'a mut self, index: usize) -> &'a mut D::Value { + &mut self.values[index] + } + + /// Updates the element at the given index. The old value will saved (and perhaps restored) if + /// a snapshot is active. + pub fn set(&mut self, index: usize, new_elem: D::Value) { + let old_elem = mem::replace(&mut self.values[index], new_elem); + if self.in_snapshot() { + self.undo_log.push(SetElem(index, old_elem)); + } + } + + pub fn start_snapshot(&mut self) -> Snapshot { + let length = self.undo_log.len(); + self.undo_log.push(OpenSnapshot); + Snapshot { length: length } + } + + pub fn actions_since_snapshot(&self, + snapshot: &Snapshot) + -> &[UndoLog] { + &self.undo_log[snapshot.length..] + } + + fn assert_open_snapshot(&self, snapshot: &Snapshot) { + // Or else there was a failure to follow a stack discipline: + assert!(self.undo_log.len() > snapshot.length); + + // Invariant established by start_snapshot(): + assert!( + match self.undo_log[snapshot.length] { + OpenSnapshot => true, + _ => false + }); + } + + pub fn rollback_to(&mut self, snapshot: Snapshot) { + debug!("rollback_to({})", snapshot.length); + + self.assert_open_snapshot(&snapshot); + + while self.undo_log.len() > snapshot.length + 1 { + match self.undo_log.pop().unwrap() { + OpenSnapshot => { + // This indicates a failure to obey the stack discipline. + panic!("Cannot rollback an uncommitted snapshot"); + } + + CommittedSnapshot => { + // This occurs when there are nested snapshots and + // the inner is committed but outer is rolled back. + } + + NewElem(i) => { + self.values.pop(); + assert!(self.values.len() == i); + } + + SetElem(i, v) => { + self.values[i] = v; + } + + Other(u) => { + D::reverse(&mut self.values, u); + } + } + } + + let v = self.undo_log.pop().unwrap(); + assert!(match v { OpenSnapshot => true, _ => false }); + assert!(self.undo_log.len() == snapshot.length); + } + + /// Commits all changes since the last snapshot. Of course, they + /// can still be undone if there is a snapshot further out. + pub fn commit(&mut self, snapshot: Snapshot) { + debug!("commit({})", snapshot.length); + + self.assert_open_snapshot(&snapshot); + + if snapshot.length == 0 { + // The root snapshot. + self.undo_log.truncate(0); + } else { + self.undo_log[snapshot.length] = CommittedSnapshot; + } + } +} + +impl ops::Deref for SnapshotVec { + type Target = [D::Value]; + fn deref(&self) -> &[D::Value] { &*self.values } +} + +impl ops::DerefMut for SnapshotVec { + fn deref_mut(&mut self) -> &mut [D::Value] { &mut *self.values } +} + +impl ops::Index for SnapshotVec { + type Output = D::Value; + fn index(&self, index: usize) -> &D::Value { self.get(index) } +} + +impl ops::IndexMut for SnapshotVec { + fn index_mut(&mut self, index: usize) -> &mut D::Value { self.get_mut(index) } +} -- cgit 1.4.1-3-g733a5