use hashbrown::{hash_table::Entry, HashTable};
use rustc_hash::{FxHashSet, FxHasher};
use std::cell::{Cell, RefCell};
use std::cmp::Ordering;
use std::fmt;
use std::hash::{Hash, Hasher};
use std::iter::FusedIterator;
use std::mem::size_of;
use std::ops::Deref;
use std::rc::{Rc, Weak};
struct QueryKey {
text: Rc<str>,
hash: u64,
}
#[derive(Clone)]
pub(crate) struct QueryId(Rc<QueryKey>);
impl QueryId {
pub(crate) fn as_str(&self) -> &str {
&self.0.text
}
pub(crate) fn text_hash(&self) -> u64 {
self.0.hash
}
}
impl Deref for QueryId {
type Target = str;
fn deref(&self) -> &Self::Target {
self.as_str()
}
}
impl AsRef<str> for QueryId {
fn as_ref(&self) -> &str {
self.as_str()
}
}
impl fmt::Display for QueryId {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Display::fmt(self.as_str(), f)
}
}
impl fmt::Debug for QueryId {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Debug::fmt(self.as_str(), f)
}
}
impl PartialEq for QueryId {
fn eq(&self, other: &Self) -> bool {
Rc::ptr_eq(&self.0, &other.0)
|| self.0.hash == other.0.hash && self.as_str() == other.as_str()
}
}
impl Eq for QueryId {}
impl Hash for QueryId {
fn hash<H: Hasher>(&self, state: &mut H) {
state.write_u64(self.0.hash);
}
}
impl Ord for QueryId {
fn cmp(&self, other: &Self) -> Ordering {
self.as_str().cmp(other.as_str())
}
}
impl PartialOrd for QueryId {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
#[derive(Clone, Copy, Debug, Default)]
pub(crate) struct QueryPoolStats {
pub(crate) entries: usize,
pub(crate) live: usize,
pub(crate) dead: usize,
pub(crate) text_bytes: usize,
pub(crate) live_text_bytes: usize,
pub(crate) dead_text_bytes: usize,
pub(crate) capacity: usize,
pub(crate) query_id_bytes: usize,
pub(crate) query_key_bytes: usize,
pub(crate) text_handle_bytes: usize,
pub(crate) weak_key_bytes: usize,
pub(crate) interner_entry_bytes: usize,
pub(crate) read_set_bytes: usize,
pub(crate) dependency_set_bytes: usize,
pub(crate) rc_header_bytes: usize,
pub(crate) scratch_index_entries: usize,
pub(crate) scratch_index_capacity: usize,
pub(crate) scratch_index_entry_bytes: usize,
}
pub(crate) struct QueryPool {
by_text: RefCell<HashTable<QueryId>>,
next_sweep: Cell<usize>,
creations_since_sweep: Cell<usize>,
swept_during_intern: Cell<bool>,
scratch: RefCell<Vec<Weak<QueryKey>>>,
}
impl Default for QueryPool {
fn default() -> Self {
Self {
by_text: RefCell::new(HashTable::new()),
next_sweep: Cell::new(1024),
creations_since_sweep: Cell::new(0),
swept_during_intern: Cell::new(false),
scratch: RefCell::new(Vec::new()),
}
}
}
impl QueryPool {
pub(crate) fn intern(&self, text: &str) -> QueryId {
let mut by_text = self.by_text.borrow_mut();
let hash = Self::text_hash(text);
let matches = |key: &QueryId| key.0.hash == hash && key.as_str() == text;
let id = if by_text.len() >= self.next_sweep.get() {
if let Some(key) = by_text.find(hash, matches) {
if Rc::strong_count(&key.0) > 1 {
return key.clone();
}
}
let recycled = by_text
.find_entry(hash, matches)
.ok()
.map(|entry| entry.remove().0);
self.sweep_entries(&mut by_text);
self.swept_during_intern.set(true);
let id = recycled.unwrap_or_else(|| self.new_id(text, hash));
by_text.insert_unique(hash, id.clone(), |key| key.0.hash);
id
} else {
match by_text.entry(hash, matches, |key| key.0.hash) {
Entry::Occupied(entry) => {
let key = entry.get();
if Rc::strong_count(&key.0) > 1 {
return key.clone();
}
key.clone() }
Entry::Vacant(entry) => {
let id = self.new_id(text, hash);
entry.insert(id.clone());
id
}
}
};
self.creations_since_sweep
.set(self.creations_since_sweep.get().saturating_add(1));
id
}
pub(crate) fn text_hash(text: &str) -> u64 {
let mut hasher = FxHasher::default();
text.hash(&mut hasher);
hasher.finish()
}
fn new_id(&self, text: &str, hash: u64) -> QueryId {
let id = QueryId(Rc::new(QueryKey {
text: Rc::from(text),
hash,
}));
let path = text.strip_prefix("assert:").unwrap_or(text);
if path.strip_prefix('_').is_some_and(|suffix| {
suffix.is_empty() || suffix.starts_with('.') || suffix.starts_with('[')
}) {
self.scratch.borrow_mut().push(Rc::downgrade(&id.0));
}
id
}
fn prune_scratch(&self) {
let mut scratch = self.scratch.borrow_mut();
scratch.retain(|key| key.strong_count() > 0);
if scratch.capacity() > scratch.len().saturating_mul(2).max(64) {
scratch.shrink_to_fit();
}
}
pub(crate) fn scratch_ids(&self) -> Vec<QueryId> {
self.prune_scratch();
self.scratch
.borrow()
.iter()
.filter_map(|key| key.upgrade().map(QueryId))
.collect()
}
pub(crate) fn lookup(&self, text: &str) -> Option<QueryId> {
let hash = Self::text_hash(text);
self.by_text
.borrow()
.find(hash, |key| key.0.hash == hash && key.as_str() == text)
.filter(|key| Rc::strong_count(&key.0) > 1)
.cloned()
}
pub(crate) fn sweep(&self) {
let mut by_text = self.by_text.borrow_mut();
self.sweep_entries(&mut by_text);
self.swept_during_intern.set(false);
}
pub(crate) fn maintain_transient(&self) {
if self.swept_during_intern.get() || self.creations_since_sweep.get() >= 1024 {
self.sweep();
}
}
fn sweep_entries(&self, by_text: &mut HashTable<QueryId>) {
by_text.retain(|key| Rc::strong_count(&key.0) > 1);
if by_text.capacity() > by_text.len().saturating_mul(2).max(64) {
by_text.shrink_to_fit(|key| key.0.hash);
}
self.next_sweep
.set(by_text.len().saturating_mul(2).max(1024));
self.creations_since_sweep.set(0);
self.prune_scratch();
}
pub(crate) fn census(&self) -> QueryPoolStats {
let by_text = self.by_text.borrow();
let scratch = self.scratch.borrow();
let mut stats = QueryPoolStats {
entries: by_text.len(),
capacity: by_text.capacity(),
scratch_index_entries: scratch.len(),
scratch_index_capacity: scratch.capacity(),
scratch_index_entry_bytes: size_of::<Weak<QueryKey>>(),
query_id_bytes: size_of::<QueryId>(),
query_key_bytes: size_of::<QueryKey>(),
text_handle_bytes: size_of::<Rc<str>>(),
weak_key_bytes: 0,
interner_entry_bytes: size_of::<QueryId>(),
read_set_bytes: size_of::<ReadSet>(),
dependency_set_bytes: size_of::<FxHashSet<QueryId>>(),
rc_header_bytes: 2 * size_of::<usize>(),
..QueryPoolStats::default()
};
for key in by_text.iter() {
let text = key.as_str();
stats.text_bytes += text.len();
if Rc::strong_count(&key.0) > 1 {
stats.live += 1;
stats.live_text_bytes += text.len();
} else {
stats.dead += 1;
stats.dead_text_bytes += text.len();
}
}
stats
}
}
#[derive(Clone, Debug, Default)]
pub(crate) struct ReadSet(Option<Rc<FxHashSet<QueryId>>>);
#[derive(Clone, Copy, Debug)]
pub(crate) struct ReadSetStorage {
pub(crate) identity: usize,
pub(crate) len: usize,
pub(crate) capacity: usize,
pub(crate) strong_count: usize,
}
impl ReadSet {
pub(crate) fn iter(&self) -> ReadSetIter<'_> {
ReadSetIter(self.0.as_ref().map(|deps| deps.iter()))
}
pub(crate) fn insert(&mut self, key: QueryId) -> bool {
let deps = self.0.get_or_insert_with(|| Rc::new(FxHashSet::default()));
Rc::make_mut(deps).insert(key)
}
pub(crate) fn len(&self) -> usize {
self.0.as_ref().map_or(0, |deps| deps.len())
}
pub(crate) fn is_empty(&self) -> bool {
self.len() == 0
}
pub(crate) fn storage(&self) -> Option<ReadSetStorage> {
self.0.as_ref().map(|deps| ReadSetStorage {
identity: Rc::as_ptr(deps) as usize,
len: deps.len(),
capacity: deps.capacity(),
strong_count: Rc::strong_count(deps),
})
}
}
impl FromIterator<QueryId> for ReadSet {
fn from_iter<T: IntoIterator<Item = QueryId>>(iter: T) -> Self {
let deps: FxHashSet<_> = iter.into_iter().collect();
Self((!deps.is_empty()).then(|| Rc::new(deps)))
}
}
pub(crate) struct ReadSetIter<'a>(Option<std::collections::hash_set::Iter<'a, QueryId>>);
impl<'a> Iterator for ReadSetIter<'a> {
type Item = &'a QueryId;
fn next(&mut self) -> Option<Self::Item> {
self.0.as_mut().and_then(Iterator::next)
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
}
impl ExactSizeIterator for ReadSetIter<'_> {
fn len(&self) -> usize {
self.0.as_ref().map_or(0, ExactSizeIterator::len)
}
}
impl FusedIterator for ReadSetIter<'_> {}
impl<'a> IntoIterator for &'a ReadSet {
type Item = &'a QueryId;
type IntoIter = ReadSetIter<'a>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
#[cfg(test)]
#[path = "../../tests/private/query_graph_test.rs"]
mod tests;