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