use crate::debug::TableEntry;
use crate::dependency::DatabaseSlot;
use crate::durability::Durability;
use crate::intern_id::InternId;
use crate::plumbing::HasQueryGroup;
use crate::plumbing::QueryStorageMassOps;
use crate::plumbing::QueryStorageOps;
use crate::revision::Revision;
use crate::Query;
use crate::{CycleError, Database, DiscardIf, SweepStrategy};
use crossbeam::atomic::AtomicCell;
use parking_lot::RwLock;
use rustc_hash::FxHashMap;
use std::collections::hash_map::Entry;
use std::convert::From;
use std::fmt::Debug;
use std::hash::Hash;
use std::sync::Arc;
const INTERN_DURABILITY: Durability = Durability::HIGH;
pub struct InternedStorage<DB, Q>
where
Q: Query<DB>,
Q::Value: InternKey,
DB: Database,
{
tables: RwLock<InternTables<Q::Key>>,
}
pub struct LookupInternedStorage<DB, Q, IQ>
where
Q: Query<DB>,
Q::Key: InternKey,
Q::Value: Eq + Hash,
IQ: Query<
DB,
Key = Q::Value,
Value = Q::Key,
Group = Q::Group,
GroupStorage = Q::GroupStorage,
GroupKey = Q::GroupKey,
>,
DB: Database,
{
phantom: std::marker::PhantomData<(Q::Key, IQ)>,
}
struct InternTables<K> {
map: FxHashMap<K, InternId>,
values: Vec<InternValue<K>>,
first_free: Option<InternId>,
}
pub trait InternKey {
fn from_intern_id(v: InternId) -> Self;
fn as_intern_id(&self) -> InternId;
}
impl InternKey for InternId {
fn from_intern_id(v: InternId) -> InternId {
v
}
fn as_intern_id(&self) -> InternId {
*self
}
}
enum InternValue<K> {
Present { slot: Arc<Slot<K>> },
Free { next: Option<InternId> },
}
#[derive(Debug)]
struct Slot<K> {
index: InternId,
value: K,
interned_at: Revision,
accessed_at: AtomicCell<Option<Revision>>,
}
impl<DB, Q> std::panic::RefUnwindSafe for InternedStorage<DB, Q>
where
Q: Query<DB>,
DB: Database,
Q::Key: std::panic::RefUnwindSafe,
Q::Value: InternKey,
Q::Value: std::panic::RefUnwindSafe,
{
}
impl<DB, Q> Default for InternedStorage<DB, Q>
where
Q: Query<DB>,
Q::Key: Eq + Hash,
Q::Value: InternKey,
DB: Database,
{
fn default() -> Self {
InternedStorage {
tables: RwLock::new(InternTables::default()),
}
}
}
impl<DB, Q, IQ> Default for LookupInternedStorage<DB, Q, IQ>
where
Q: Query<DB>,
Q::Key: InternKey,
Q::Value: Eq + Hash,
IQ: Query<
DB,
Key = Q::Value,
Value = Q::Key,
Group = Q::Group,
GroupStorage = Q::GroupStorage,
GroupKey = Q::GroupKey,
>,
DB: Database,
{
fn default() -> Self {
LookupInternedStorage {
phantom: std::marker::PhantomData,
}
}
}
impl<K: Debug + Hash + Eq> InternTables<K> {
fn slot_for_key(&self, key: &K, revision_now: Revision) -> Option<Arc<Slot<K>>> {
let index = self.map.get(key)?;
Some(self.slot_for_index(*index, revision_now))
}
fn slot_for_index(&self, index: InternId, revision_now: Revision) -> Arc<Slot<K>> {
match &self.values[index.as_usize()] {
InternValue::Present { slot } => {
let updated = slot.try_update_accessed_at(revision_now);
assert!(
updated,
"failed to update slot {:?} while holding read lock",
slot
);
slot.clone()
}
InternValue::Free { .. } => {
panic!("index {:?} is free but should not be", index);
}
}
}
}
impl<K> Default for InternTables<K>
where
K: Eq + Hash,
{
fn default() -> Self {
Self {
map: Default::default(),
values: Default::default(),
first_free: Default::default(),
}
}
}
impl<DB, Q> InternedStorage<DB, Q>
where
Q: Query<DB>,
Q::Key: Eq + Hash + Clone,
Q::Value: InternKey,
DB: Database,
{
fn intern_index(&self, db: &DB, key: &Q::Key) -> Arc<Slot<Q::Key>> {
if let Some(i) = self.intern_check(db, key) {
return i;
}
let owned_key1 = key.to_owned();
let owned_key2 = owned_key1.clone();
let revision_now = db.salsa_runtime().current_revision();
let mut tables = self.tables.write();
let tables = &mut *tables;
let entry = match tables.map.entry(owned_key1) {
Entry::Vacant(entry) => entry,
Entry::Occupied(entry) => {
let index = *entry.get();
match &tables.values[index.as_usize()] {
InternValue::Present { slot } => {
debug_assert_eq!(owned_key2, slot.value);
debug_assert_eq!(slot.accessed_at.load(), Some(revision_now));
return slot.clone();
}
InternValue::Free { .. } => {
panic!("key {:?} should be present but is not", key,);
}
}
}
};
let create_slot = |index: InternId| {
Arc::new(Slot {
index,
value: owned_key2,
interned_at: revision_now,
accessed_at: AtomicCell::new(Some(revision_now)),
})
};
let (slot, index);
match tables.first_free {
None => {
index = InternId::from(tables.values.len());
slot = create_slot(index);
tables
.values
.push(InternValue::Present { slot: slot.clone() });
}
Some(i) => {
index = i;
slot = create_slot(index);
let next_free = match &tables.values[i.as_usize()] {
InternValue::Free { next } => *next,
InternValue::Present { slot } => {
panic!(
"index {:?} was supposed to be free but contains {:?}",
i, slot.value
);
}
};
tables.values[index.as_usize()] = InternValue::Present { slot: slot.clone() };
tables.first_free = next_free;
}
}
entry.insert(index);
slot
}
fn intern_check(&self, db: &DB, key: &Q::Key) -> Option<Arc<Slot<Q::Key>>> {
let revision_now = db.salsa_runtime().current_revision();
let slot = self.tables.read().slot_for_key(key, revision_now)?;
Some(slot)
}
fn lookup_value(&self, db: &DB, index: InternId) -> Arc<Slot<Q::Key>> {
let revision_now = db.salsa_runtime().current_revision();
self.tables.read().slot_for_index(index, revision_now)
}
}
impl<DB, Q> QueryStorageOps<DB, Q> for InternedStorage<DB, Q>
where
Q: Query<DB>,
Q::Value: InternKey,
DB: Database,
{
fn try_fetch(&self, db: &DB, key: &Q::Key) -> Result<Q::Value, CycleError<DB::DatabaseKey>> {
let slot = self.intern_index(db, key);
let changed_at = slot.interned_at;
let index = slot.index;
db.salsa_runtime()
.report_query_read(slot, INTERN_DURABILITY, changed_at);
Ok(<Q::Value>::from_intern_id(index))
}
fn durability(&self, _db: &DB, _key: &Q::Key) -> Durability {
INTERN_DURABILITY
}
fn entries<C>(&self, _db: &DB) -> C
where
C: std::iter::FromIterator<TableEntry<Q::Key, Q::Value>>,
{
let tables = self.tables.read();
tables
.map
.iter()
.map(|(key, index)| {
TableEntry::new(key.clone(), Some(<Q::Value>::from_intern_id(*index)))
})
.collect()
}
}
impl<DB, Q> QueryStorageMassOps<DB> for InternedStorage<DB, Q>
where
Q: Query<DB>,
Q::Value: InternKey,
DB: Database,
{
fn sweep(&self, db: &DB, strategy: SweepStrategy) {
let mut tables = self.tables.write();
let last_changed = db.salsa_runtime().last_changed_revision(INTERN_DURABILITY);
let revision_now = db.salsa_runtime().current_revision();
let InternTables {
map,
values,
first_free,
} = &mut *tables;
map.retain(|key, intern_index| {
match strategy.discard_if {
DiscardIf::Never => true,
DiscardIf::Always | DiscardIf::Outdated => match &values[intern_index.as_usize()] {
InternValue::Present { slot, .. } => {
if slot.try_collect(last_changed, revision_now) {
values[intern_index.as_usize()] =
InternValue::Free { next: *first_free };
*first_free = Some(*intern_index);
false
} else {
true
}
}
InternValue::Free { .. } => {
panic!(
"key {:?} maps to index {:?} which is free",
key, intern_index
);
}
},
}
});
}
}
impl<DB, Q, IQ> QueryStorageOps<DB, Q> for LookupInternedStorage<DB, Q, IQ>
where
Q: Query<DB>,
Q::Key: InternKey,
Q::Value: Eq + Hash,
IQ: Query<
DB,
Key = Q::Value,
Value = Q::Key,
Storage = InternedStorage<DB, IQ>,
Group = Q::Group,
GroupStorage = Q::GroupStorage,
GroupKey = Q::GroupKey,
>,
DB: Database + HasQueryGroup<Q::Group>,
{
fn try_fetch(&self, db: &DB, key: &Q::Key) -> Result<Q::Value, CycleError<DB::DatabaseKey>> {
let index = key.as_intern_id();
let group_storage = <DB as HasQueryGroup<Q::Group>>::group_storage(db);
let interned_storage = IQ::query_storage(group_storage);
let slot = interned_storage.lookup_value(db, index);
let value = slot.value.clone();
let interned_at = slot.interned_at;
db.salsa_runtime()
.report_query_read(slot, INTERN_DURABILITY, interned_at);
Ok(value)
}
fn durability(&self, _db: &DB, _key: &Q::Key) -> Durability {
INTERN_DURABILITY
}
fn entries<C>(&self, db: &DB) -> C
where
C: std::iter::FromIterator<TableEntry<Q::Key, Q::Value>>,
{
let group_storage = <DB as HasQueryGroup<Q::Group>>::group_storage(db);
let interned_storage = IQ::query_storage(group_storage);
let tables = interned_storage.tables.read();
tables
.map
.iter()
.map(|(key, index)| {
TableEntry::new(<Q::Key>::from_intern_id(*index), Some(key.clone()))
})
.collect()
}
}
impl<DB, Q, IQ> QueryStorageMassOps<DB> for LookupInternedStorage<DB, Q, IQ>
where
Q: Query<DB>,
Q::Key: InternKey,
Q::Value: Eq + Hash,
IQ: Query<
DB,
Key = Q::Value,
Value = Q::Key,
Group = Q::Group,
GroupStorage = Q::GroupStorage,
GroupKey = Q::GroupKey,
>,
DB: Database,
{
fn sweep(&self, _db: &DB, _strategy: SweepStrategy) {}
}
impl<K> Slot<K> {
fn try_update_accessed_at(&self, revision_now: Revision) -> bool {
if let Some(accessed_at) = self.accessed_at.load() {
match self
.accessed_at
.compare_exchange(Some(accessed_at), Some(revision_now))
{
Ok(_) => true,
Err(Some(r)) => {
debug_assert_eq!(r, revision_now);
true
}
Err(None) => {
false
}
}
} else {
false
}
}
fn try_collect(&self, last_changed: Revision, revision_now: Revision) -> bool {
let accessed_at = self.accessed_at.load().unwrap();
if accessed_at < last_changed {
match self.accessed_at.compare_exchange(Some(accessed_at), None) {
Ok(_) => true,
Err(r) => {
debug_assert_eq!(r, Some(revision_now));
false
}
}
} else {
false
}
}
}
unsafe impl<DB, K> DatabaseSlot<DB> for Slot<K>
where
DB: Database,
K: Debug,
{
fn maybe_changed_since(&self, db: &DB, revision: Revision) -> bool {
let revision_now = db.salsa_runtime().current_revision();
if !self.try_update_accessed_at(revision_now) {
true
} else {
self.interned_at > revision
}
}
}
#[allow(dead_code)]
fn check_send_sync<K>()
where
K: Send + Sync,
{
fn is_send_sync<T: Send + Sync>() {}
is_send_sync::<Slot<K>>();
}
#[allow(dead_code)]
fn check_static<K>()
where
K: 'static,
{
fn is_static<T: 'static>() {}
is_static::<Slot<K>>();
}