vendor/salsa/src/derived.rs

   1 use crate::debug::TableEntry;
   2 use crate::durability::Durability;
   3 use crate::lru::Lru;
   4 use crate::plumbing::DerivedQueryStorageOps;
   5 use crate::plumbing::LruQueryStorageOps;
   6 use crate::plumbing::QueryFunction;
   7 use crate::plumbing::QueryStorageMassOps;
   8 use crate::plumbing::QueryStorageOps;
   9 use crate::runtime::{FxIndexMap, StampedValue};
  10 use crate::{CycleError, Database, DatabaseKeyIndex, Revision, Runtime, SweepStrategy};
  11 use parking_lot::RwLock;
  12 use std::convert::TryFrom;
  13 use std::marker::PhantomData;
  14 use std::sync::Arc;
  15
  16 mod slot;
  17 use slot::Slot;
  18
  19 /// Memoized queries store the result plus a list of the other queries
  20 /// that they invoked. This means we can avoid recomputing them when
  21 /// none of those inputs have changed.
  22 pub type MemoizedStorage<Q> = DerivedStorage<Q, AlwaysMemoizeValue>;
  23
  24 /// "Dependency" queries just track their dependencies and not the
  25 /// actual value (which they produce on demand). This lessens the
  26 /// storage requirements.
  27 pub type DependencyStorage<Q> = DerivedStorage<Q, NeverMemoizeValue>;
  28
  29 /// Handles storage where the value is 'derived' by executing a
  30 /// function (in contrast to "inputs").
  31 pub struct DerivedStorage<Q, MP>
  32 where
  33     Q: QueryFunction,
  34     MP: MemoizationPolicy<Q>,
  35 {
  36     group_index: u16,
  37     lru_list: Lru<Slot<Q, MP>>,
  38     slot_map: RwLock<FxIndexMap<Q::Key, Arc<Slot<Q, MP>>>>,
  39     policy: PhantomData<MP>,
  40 }
  41
  42 impl<Q, MP> std::panic::RefUnwindSafe for DerivedStorage<Q, MP>
  43 where
  44     Q: QueryFunction,
  45     MP: MemoizationPolicy<Q>,
  46     Q::Key: std::panic::RefUnwindSafe,
  47     Q::Value: std::panic::RefUnwindSafe,
  48 {
  49 }
  50
  51 pub trait MemoizationPolicy<Q>: Send + Sync + 'static
  52 where
  53     Q: QueryFunction,
  54 {
  55     fn should_memoize_value(key: &Q::Key) -> bool;
  56
  57     fn memoized_value_eq(old_value: &Q::Value, new_value: &Q::Value) -> bool;
  58 }
  59
  60 pub enum AlwaysMemoizeValue {}
  61 impl<Q> MemoizationPolicy<Q> for AlwaysMemoizeValue
  62 where
  63     Q: QueryFunction,
  64     Q::Value: Eq,
  65 {
  66     fn should_memoize_value(_key: &Q::Key) -> bool {
  67         true
  68     }
  69
  70     fn memoized_value_eq(old_value: &Q::Value, new_value: &Q::Value) -> bool {
  71         old_value == new_value
  72     }
  73 }
  74
  75 pub enum NeverMemoizeValue {}
  76 impl<Q> MemoizationPolicy<Q> for NeverMemoizeValue
  77 where
  78     Q: QueryFunction,
  79 {
  80     fn should_memoize_value(_key: &Q::Key) -> bool {
  81         false
  82     }
  83
  84     fn memoized_value_eq(_old_value: &Q::Value, _new_value: &Q::Value) -> bool {
  85         panic!("cannot reach since we never memoize")
  86     }
  87 }
  88
  89 impl<Q, MP> DerivedStorage<Q, MP>
  90 where
  91     Q: QueryFunction,
  92     MP: MemoizationPolicy<Q>,
  93 {
  94     fn slot(&self, key: &Q::Key) -> Arc<Slot<Q, MP>> {
  95         if let Some(v) = self.slot_map.read().get(key) {
  96             return v.clone();
  97         }
  98
  99         let mut write = self.slot_map.write();
 100         let entry = write.entry(key.clone());
 101         let key_index = u32::try_from(entry.index()).unwrap();
 102         let database_key_index = DatabaseKeyIndex {
 103             group_index: self.group_index,
 104             query_index: Q::QUERY_INDEX,
 105             key_index: key_index,
 106         };
 107         entry
 108             .or_insert_with(|| Arc::new(Slot::new(key.clone(), database_key_index)))
 109             .clone()
 110     }
 111 }
 112
 113 impl<Q, MP> QueryStorageOps<Q> for DerivedStorage<Q, MP>
 114 where
 115     Q: QueryFunction,
 116     MP: MemoizationPolicy<Q>,
 117 {
 118     fn new(group_index: u16) -> Self {
 119         DerivedStorage {
 120             group_index,
 121             slot_map: RwLock::new(FxIndexMap::default()),
 122             lru_list: Default::default(),
 123             policy: PhantomData,
 124         }
 125     }
 126
 127     fn fmt_index(
 128         &self,
 129         _db: &Q::DynDb,
 130         index: DatabaseKeyIndex,
 131         fmt: &mut std::fmt::Formatter<'_>,
 132     ) -> std::fmt::Result {
 133         assert_eq!(index.group_index, self.group_index);
 134         assert_eq!(index.query_index, Q::QUERY_INDEX);
 135         let slot_map = self.slot_map.read();
 136         let key = slot_map.get_index(index.key_index as usize).unwrap().0;
 137         write!(fmt, "{}({:?})", Q::QUERY_NAME, key)
 138     }
 139
 140     fn maybe_changed_since(
 141         &self,
 142         db: &Q::DynDb,
 143         input: DatabaseKeyIndex,
 144         revision: Revision,
 145     ) -> bool {
 146         assert_eq!(input.group_index, self.group_index);
 147         assert_eq!(input.query_index, Q::QUERY_INDEX);
 148         let slot = self
 149             .slot_map
 150             .read()
 151             .get_index(input.key_index as usize)
 152             .unwrap()
 153             .1
 154             .clone();
 155         slot.maybe_changed_since(db, revision)
 156     }
 157
 158     fn try_fetch(
 159         &self,
 160         db: &Q::DynDb,
 161         key: &Q::Key,
 162     ) -> Result<Q::Value, CycleError<DatabaseKeyIndex>> {
 163         let slot = self.slot(key);
 164         let StampedValue {
 165             value,
 166             durability,
 167             changed_at,
 168         } = slot.read(db)?;
 169
 170         if let Some(evicted) = self.lru_list.record_use(&slot) {
 171             evicted.evict();
 172         }
 173
 174         db.salsa_runtime()
 175             .report_query_read(slot.database_key_index(), durability, changed_at);
 176
 177         Ok(value)
 178     }
 179
 180     fn durability(&self, db: &Q::DynDb, key: &Q::Key) -> Durability {
 181         self.slot(key).durability(db)
 182     }
 183
 184     fn entries<C>(&self, _db: &Q::DynDb) -> C
 185     where
 186         C: std::iter::FromIterator<TableEntry<Q::Key, Q::Value>>,
 187     {
 188         let slot_map = self.slot_map.read();
 189         slot_map
 190             .values()
 191             .filter_map(|slot| slot.as_table_entry())
 192             .collect()
 193     }
 194 }
 195
 196 impl<Q, MP> QueryStorageMassOps for DerivedStorage<Q, MP>
 197 where
 198     Q: QueryFunction,
 199     MP: MemoizationPolicy<Q>,
 200 {
 201     fn sweep(&self, runtime: &Runtime, strategy: SweepStrategy) {
 202         let map_read = self.slot_map.read();
 203         let revision_now = runtime.current_revision();
 204         for slot in map_read.values() {
 205             slot.sweep(revision_now, strategy);
 206         }
 207     }
 208     fn purge(&self) {
 209         self.lru_list.purge();
 210         *self.slot_map.write() = Default::default();
 211     }
 212 }
 213
 214 impl<Q, MP> LruQueryStorageOps for DerivedStorage<Q, MP>
 215 where
 216     Q: QueryFunction,
 217     MP: MemoizationPolicy<Q>,
 218 {
 219     fn set_lru_capacity(&self, new_capacity: usize) {
 220         self.lru_list.set_lru_capacity(new_capacity);
 221     }
 222 }
 223
 224 impl<Q, MP> DerivedQueryStorageOps<Q> for DerivedStorage<Q, MP>
 225 where
 226     Q: QueryFunction,
 227     MP: MemoizationPolicy<Q>,
 228 {
 229     fn invalidate(&self, db: &mut Q::DynDb, key: &Q::Key) {
 230         db.salsa_runtime_mut()
 231             .with_incremented_revision(&mut |_new_revision| {
 232                 let map_read = self.slot_map.read();
 233
 234                 if let Some(slot) = map_read.get(key) {
 235                     if let Some(durability) = slot.invalidate() {
 236                         return Some(durability);
 237                     }
 238                 }
 239
 240                 None
 241             })
 242     }
 243 }