compiler/rustc_data_structures/src/snapshot_map/mod.rs

   1 use crate::fx::FxHashMap;
   2 use crate::undo_log::{Rollback, Snapshots, UndoLogs, VecLog};
   3 use std::borrow::{Borrow, BorrowMut};
   4 use std::hash::Hash;
   5 use std::marker::PhantomData;
   6 use std::ops;
   7
   8 pub use crate::undo_log::Snapshot;
   9
  10 #[cfg(test)]
  11 mod tests;
  12
  13 pub type SnapshotMapStorage<K, V> = SnapshotMap<K, V, FxHashMap<K, V>, ()>;
  14 pub type SnapshotMapRef<'a, K, V, L> = SnapshotMap<K, V, &'a mut FxHashMap<K, V>, &'a mut L>;
  15
  16 pub struct SnapshotMap<K, V, M = FxHashMap<K, V>, L = VecLog<UndoLog<K, V>>> {
  17     map: M,
  18     undo_log: L,
  19     _marker: PhantomData<(K, V)>,
  20 }
  21
  22 // HACK(eddyb) manual impl avoids `Default` bounds on `K` and `V`.
  23 impl<K, V, M, L> Default for SnapshotMap<K, V, M, L>
  24 where
  25     M: Default,
  26     L: Default,
  27 {
  28     fn default() -> Self {
  29         SnapshotMap { map: Default::default(), undo_log: Default::default(), _marker: PhantomData }
  30     }
  31 }
  32
  33 pub enum UndoLog<K, V> {
  34     Inserted(K),
  35     Overwrite(K, V),
  36     Purged,
  37 }
  38
  39 impl<K, V, M, L> SnapshotMap<K, V, M, L> {
  40     #[inline]
  41     pub fn with_log<L2>(&mut self, undo_log: L2) -> SnapshotMap<K, V, &mut M, L2> {
  42         SnapshotMap { map: &mut self.map, undo_log, _marker: PhantomData }
  43     }
  44 }
  45
  46 impl<K, V, M, L> SnapshotMap<K, V, M, L>
  47 where
  48     K: Hash + Clone + Eq,
  49     M: BorrowMut<FxHashMap<K, V>> + Borrow<FxHashMap<K, V>>,
  50     L: UndoLogs<UndoLog<K, V>>,
  51 {
  52     pub fn clear(&mut self) {
  53         self.map.borrow_mut().clear();
  54         self.undo_log.clear();
  55     }
  56
  57     pub fn insert(&mut self, key: K, value: V) -> bool {
  58         match self.map.borrow_mut().insert(key.clone(), value) {
  59             None => {
  60                 self.undo_log.push(UndoLog::Inserted(key));
  61                 true
  62             }
  63             Some(old_value) => {
  64                 self.undo_log.push(UndoLog::Overwrite(key, old_value));
  65                 false
  66             }
  67         }
  68     }
  69
  70     pub fn remove(&mut self, key: K) -> bool {
  71         match self.map.borrow_mut().remove(&key) {
  72             Some(old_value) => {
  73                 self.undo_log.push(UndoLog::Overwrite(key, old_value));
  74                 true
  75             }
  76             None => false,
  77         }
  78     }
  79
  80     pub fn get(&self, key: &K) -> Option<&V> {
  81         self.map.borrow().get(key)
  82     }
  83 }
  84
  85 impl<K, V> SnapshotMap<K, V>
  86 where
  87     K: Hash + Clone + Eq,
  88 {
  89     pub fn snapshot(&mut self) -> Snapshot {
  90         self.undo_log.start_snapshot()
  91     }
  92
  93     pub fn commit(&mut self, snapshot: Snapshot) {
  94         self.undo_log.commit(snapshot)
  95     }
  96
  97     pub fn rollback_to(&mut self, snapshot: Snapshot) {
  98         let map = &mut self.map;
  99         self.undo_log.rollback_to(|| map, snapshot)
 100     }
 101 }
 102
 103 impl<'k, K, V, M, L> ops::Index<&'k K> for SnapshotMap<K, V, M, L>
 104 where
 105     K: Hash + Clone + Eq,
 106     M: Borrow<FxHashMap<K, V>>,
 107 {
 108     type Output = V;
 109     fn index(&self, key: &'k K) -> &V {
 110         &self.map.borrow()[key]
 111     }
 112 }
 113
 114 impl<K, V, M, L> Rollback<UndoLog<K, V>> for SnapshotMap<K, V, M, L>
 115 where
 116     K: Eq + Hash,
 117     M: Rollback<UndoLog<K, V>>,
 118 {
 119     fn reverse(&mut self, undo: UndoLog<K, V>) {
 120         self.map.reverse(undo)
 121     }
 122 }
 123
 124 impl<K, V> Rollback<UndoLog<K, V>> for FxHashMap<K, V>
 125 where
 126     K: Eq + Hash,
 127 {
 128     fn reverse(&mut self, undo: UndoLog<K, V>) {
 129         match undo {
 130             UndoLog::Inserted(key) => {
 131                 self.remove(&key);
 132             }
 133
 134             UndoLog::Overwrite(key, old_value) => {
 135                 self.insert(key, old_value);
 136             }
 137
 138             UndoLog::Purged => {}
 139         }
 140     }
 141 }