diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
commit | 698f8c2f01ea549d77d7dc3338a12e04c11057b9 (patch) | |
tree | 173a775858bd501c378080a10dca74132f05bc50 /compiler/rustc_data_structures/src/snapshot_map | |
parent | Initial commit. (diff) | |
download | rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.tar.xz rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.zip |
Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'compiler/rustc_data_structures/src/snapshot_map')
-rw-r--r-- | compiler/rustc_data_structures/src/snapshot_map/mod.rs | 143 | ||||
-rw-r--r-- | compiler/rustc_data_structures/src/snapshot_map/tests.rs | 43 |
2 files changed, 186 insertions, 0 deletions
diff --git a/compiler/rustc_data_structures/src/snapshot_map/mod.rs b/compiler/rustc_data_structures/src/snapshot_map/mod.rs new file mode 100644 index 000000000..8a50179cd --- /dev/null +++ b/compiler/rustc_data_structures/src/snapshot_map/mod.rs @@ -0,0 +1,143 @@ +use crate::fx::FxHashMap; +use crate::undo_log::{Rollback, Snapshots, UndoLogs, VecLog}; +use std::borrow::{Borrow, BorrowMut}; +use std::hash::Hash; +use std::marker::PhantomData; +use std::ops; + +pub use crate::undo_log::Snapshot; + +#[cfg(test)] +mod tests; + +pub type SnapshotMapStorage<K, V> = SnapshotMap<K, V, FxHashMap<K, V>, ()>; +pub type SnapshotMapRef<'a, K, V, L> = SnapshotMap<K, V, &'a mut FxHashMap<K, V>, &'a mut L>; + +#[derive(Clone)] +pub struct SnapshotMap<K, V, M = FxHashMap<K, V>, L = VecLog<UndoLog<K, V>>> { + map: M, + undo_log: L, + _marker: PhantomData<(K, V)>, +} + +// HACK(eddyb) manual impl avoids `Default` bounds on `K` and `V`. +impl<K, V, M, L> Default for SnapshotMap<K, V, M, L> +where + M: Default, + L: Default, +{ + fn default() -> Self { + SnapshotMap { map: Default::default(), undo_log: Default::default(), _marker: PhantomData } + } +} + +#[derive(Clone)] +pub enum UndoLog<K, V> { + Inserted(K), + Overwrite(K, V), + Purged, +} + +impl<K, V, M, L> SnapshotMap<K, V, M, L> { + #[inline] + pub fn with_log<L2>(&mut self, undo_log: L2) -> SnapshotMap<K, V, &mut M, L2> { + SnapshotMap { map: &mut self.map, undo_log, _marker: PhantomData } + } +} + +impl<K, V, M, L> SnapshotMap<K, V, M, L> +where + K: Hash + Clone + Eq, + M: BorrowMut<FxHashMap<K, V>> + Borrow<FxHashMap<K, V>>, + L: UndoLogs<UndoLog<K, V>>, +{ + pub fn clear(&mut self) { + self.map.borrow_mut().clear(); + self.undo_log.clear(); + } + + pub fn insert(&mut self, key: K, value: V) -> bool { + match self.map.borrow_mut().insert(key.clone(), value) { + None => { + self.undo_log.push(UndoLog::Inserted(key)); + true + } + Some(old_value) => { + self.undo_log.push(UndoLog::Overwrite(key, old_value)); + false + } + } + } + + pub fn remove(&mut self, key: K) -> bool { + match self.map.borrow_mut().remove(&key) { + Some(old_value) => { + self.undo_log.push(UndoLog::Overwrite(key, old_value)); + true + } + None => false, + } + } + + pub fn get(&self, key: &K) -> Option<&V> { + self.map.borrow().get(key) + } +} + +impl<K, V> SnapshotMap<K, V> +where + K: Hash + Clone + Eq, +{ + pub fn snapshot(&mut self) -> Snapshot { + self.undo_log.start_snapshot() + } + + pub fn commit(&mut self, snapshot: Snapshot) { + self.undo_log.commit(snapshot) + } + + pub fn rollback_to(&mut self, snapshot: Snapshot) { + let map = &mut self.map; + self.undo_log.rollback_to(|| map, snapshot) + } +} + +impl<'k, K, V, M, L> ops::Index<&'k K> for SnapshotMap<K, V, M, L> +where + K: Hash + Clone + Eq, + M: Borrow<FxHashMap<K, V>>, +{ + type Output = V; + fn index(&self, key: &'k K) -> &V { + &self.map.borrow()[key] + } +} + +impl<K, V, M, L> Rollback<UndoLog<K, V>> for SnapshotMap<K, V, M, L> +where + K: Eq + Hash, + M: Rollback<UndoLog<K, V>>, +{ + fn reverse(&mut self, undo: UndoLog<K, V>) { + self.map.reverse(undo) + } +} + +impl<K, V> Rollback<UndoLog<K, V>> for FxHashMap<K, V> +where + K: Eq + Hash, +{ + fn reverse(&mut self, undo: UndoLog<K, V>) { + match undo { + UndoLog::Inserted(key) => { + self.remove(&key); + } + + UndoLog::Overwrite(key, old_value) => { + self.insert(key, old_value); + } + + UndoLog::Purged => {} + } + } +} diff --git a/compiler/rustc_data_structures/src/snapshot_map/tests.rs b/compiler/rustc_data_structures/src/snapshot_map/tests.rs new file mode 100644 index 000000000..72ca53c2b --- /dev/null +++ b/compiler/rustc_data_structures/src/snapshot_map/tests.rs @@ -0,0 +1,43 @@ +use super::SnapshotMap; + +#[test] +fn basic() { + let mut map = SnapshotMap::default(); + map.insert(22, "twenty-two"); + let snapshot = map.snapshot(); + map.insert(22, "thirty-three"); + assert_eq!(map[&22], "thirty-three"); + map.insert(44, "forty-four"); + assert_eq!(map[&44], "forty-four"); + assert_eq!(map.get(&33), None); + map.rollback_to(snapshot); + assert_eq!(map[&22], "twenty-two"); + assert_eq!(map.get(&33), None); + assert_eq!(map.get(&44), None); +} + +#[test] +#[should_panic] +fn out_of_order() { + let mut map = SnapshotMap::default(); + map.insert(22, "twenty-two"); + let snapshot1 = map.snapshot(); + map.insert(33, "thirty-three"); + let snapshot2 = map.snapshot(); + map.insert(44, "forty-four"); + map.rollback_to(snapshot1); // bogus, but accepted + map.rollback_to(snapshot2); // asserts +} + +#[test] +fn nested_commit_then_rollback() { + let mut map = SnapshotMap::default(); + map.insert(22, "twenty-two"); + let snapshot1 = map.snapshot(); + let snapshot2 = map.snapshot(); + map.insert(22, "thirty-three"); + map.commit(snapshot2); + assert_eq!(map[&22], "thirty-three"); + map.rollback_to(snapshot1); + assert_eq!(map[&22], "twenty-two"); +} |