use std::collections::{BTreeMap, HashMap, HashSet};
use std::sync::{Arc, Mutex, MutexGuard};
use datumesh_core::{Receipt, Slice};
use crate::engine::MemoStats;
use crate::eval::{Ans, FaultAns, Use};
#[derive(Clone, Debug)]
pub(crate) enum Entry {
Value(Arc<Ans>),
Fault(Arc<FaultAns>),
}
impl Entry {
fn id(&self) -> &str {
match self {
Entry::Value(a) => &a.id,
Entry::Fault(f) => &f.id,
}
}
fn memo(&self) -> bool {
match self {
Entry::Value(a) => a.memo,
Entry::Fault(f) => f.memo,
}
}
fn deps(&self) -> Vec<&String> {
match self {
Entry::Value(a) => a.deps().collect(),
Entry::Fault(f) => f.deps().collect(),
}
}
fn patterns(&self) -> Vec<&Arc<Slice>> {
match self {
Entry::Value(a) => a.patterns().collect(),
Entry::Fault(f) => f.patterns().collect(),
}
}
}
pub(crate) struct Memo {
capacity: usize,
state: Mutex<State>,
}
type Readers = (Arc<Slice>, HashSet<String>);
#[derive(Default)]
struct State {
rev: u64,
entries: HashMap<String, Vec<Arc<Ans>>>,
faults: HashMap<String, Vec<Arc<FaultAns>>>,
count: usize,
stale: HashMap<String, Vec<Arc<Ans>>>,
stale_count: usize,
readers: HashMap<String, HashSet<String>>,
edges: usize,
dirty: HashMap<String, u64>,
active: BTreeMap<u64, usize>,
patterns: HashMap<String, HashMap<String, Readers>>,
pattern_count: usize,
added: Vec<(u64, Option<Arc<Receipt>>)>,
}
impl Memo {
pub(crate) fn new(capacity: usize) -> Memo {
Memo { capacity, state: Mutex::new(State::default()) }
}
pub(crate) fn enabled(&self) -> bool {
self.capacity > 0
}
fn lock(&self) -> MutexGuard<'_, State> {
self.state.lock().unwrap_or_else(|p| p.into_inner())
}
pub(crate) fn get(&self, cell_id: &str, asof: &str) -> Option<Arc<Ans>> {
if !self.enabled() {
return None;
}
let s = self.lock();
s.entries
.get(cell_id)?
.iter()
.find(|a| a.lo.as_str() <= asof && a.hi.as_deref().is_none_or(|h| asof < h))
.cloned()
}
pub(crate) fn get_fault(&self, cell_id: &str, asof: &str) -> Option<Arc<FaultAns>> {
if !self.enabled() {
return None;
}
let s = self.lock();
s.faults
.get(cell_id)?
.iter()
.find(|f| f.lo.as_str() <= asof && f.hi.as_deref().is_none_or(|h| asof < h))
.cloned()
}
pub(crate) fn stale(&self, cell_id: &str, asof: &str) -> Option<Arc<Ans>> {
if !self.enabled() {
return None;
}
let s = self.lock();
s.stale
.get(cell_id)?
.iter()
.find(|a| a.lo.as_str() <= asof && a.hi.as_deref().is_none_or(|h| asof < h))
.cloned()
}
pub(crate) fn begin(&self) -> u64 {
let mut s = self.lock();
let rev = s.rev;
*s.active.entry(rev).or_default() += 1;
rev
}
pub(crate) fn end(&self, start: u64, learned: &[Entry]) {
let mut s = self.lock();
if self.enabled() {
for e in learned {
if !e.memo() {
continue;
}
let deps = e.deps();
let patterns = e.patterns();
let mut mark = std::iter::once(e.id())
.chain(deps.iter().map(|d| d.as_str()))
.filter_map(|c| s.dirty.get(c))
.max()
.copied();
for (rev, r) in s.added.iter().filter(|(rev, _)| *rev > start) {
let hit = patterns.iter().any(|p| match r {
Some(r) => p.fn_hash() == r.cell().fn_hash && p.contains(r),
None => true,
});
if hit {
mark = Some(mark.map_or(*rev, |m| m.max(*rev)));
}
}
if let Some(m) = mark.filter(|m| *m > start) {
let d = s.dirty.entry(e.id().to_string()).or_default();
*d = (*d).max(m);
continue;
}
s.insert(e.clone(), self.capacity);
}
}
s.finish(start);
}
pub(crate) fn abort(&self, start: u64) {
self.lock().finish(start);
}
pub(crate) fn wants_receipts(&self) -> bool {
let s = self.lock();
s.pattern_count > 0 || !s.active.is_empty()
}
pub(crate) fn invalidate(&self, cell_id: &str, receipt: Option<Arc<Receipt>>) {
let mut s = self.lock();
s.rev += 1;
let rev = s.rev;
let track = !s.active.is_empty();
let mut queue = vec![cell_id.to_string()];
let mut matched = Vec::new();
match &receipt {
Some(r) => {
if let Some(by_id) = s.patterns.get_mut(&r.cell().fn_hash) {
by_id.retain(|_, (slice, readers)| {
if slice.contains(r) {
matched.extend(readers.drain());
false
} else {
true
}
});
}
}
None => {
for (_, by_id) in s.patterns.drain() {
for (_, (_, readers)) in by_id {
matched.extend(readers);
}
}
}
}
s.pattern_count = s.patterns.values().map(HashMap::len).sum();
queue.extend(matched);
if track {
s.added.push((rev, receipt));
}
let mut seen = HashSet::new();
while let Some(c) = queue.pop() {
if !seen.insert(c.clone()) {
continue;
}
if track {
s.dirty.insert(c.clone(), rev);
}
if let Some(list) = s.entries.remove(&c) {
s.count -= list.len();
s.stale_count += list.len();
s.stale.entry(c.clone()).or_default().extend(list);
}
if let Some(list) = s.faults.remove(&c) {
s.count -= list.len();
}
if let Some(readers) = s.readers.remove(&c) {
s.edges -= readers.len();
queue.extend(readers);
}
}
}
pub(crate) fn clear(&self) {
let mut s = self.lock();
s.rev += 1;
s.entries.clear();
s.faults.clear();
s.readers.clear();
s.stale.clear();
s.patterns.clear();
s.pattern_count = 0;
s.count = 0;
s.stale_count = 0;
s.edges = 0;
}
pub(crate) fn stats(&self) -> MemoStats {
let s = self.lock();
let mut bytes = 0usize;
for (id, list) in &s.faults {
bytes += id.len() + 48;
for f in list {
bytes += std::mem::size_of::<FaultAns>()
+ f.id.len()
+ f.known.len()
+ f.lo.len()
+ f.hi.as_ref().map_or(0, String::len)
+ f.faulted.iter().map(|c| c.len() + 32).sum::<usize>()
+ f.names.len() * 64;
}
}
for (id, list) in &s.entries {
bytes += id.len() + 48;
for a in list {
bytes += std::mem::size_of::<Ans>()
+ a.bytes.len()
+ a.id.len()
+ a.hash.len()
+ a.tx.len()
+ a.asof.len()
+ a.lo.len()
+ a.hi.as_ref().map_or(0, String::len)
+ a.inputs
.iter()
.map(|u| match u {
Use::Cell { id, hash, .. } => id.len() + hash.len() + std::mem::size_of_val(u) + 160,
Use::Slice(r) => {
(r.entry.len() + r.manifest.len() + r.members.len() * 400 + 200)
/ Arc::strong_count(r).max(1)
}
})
.sum::<usize>()
+ a.names
.iter()
.map(|((k, t), v)| k.len() + t.as_ref().map_or(0, String::len) + v.len() + 64)
.sum::<usize>()
/ Arc::strong_count(&a.names).max(1);
}
}
for (k, set) in &s.readers {
bytes += k.len() + 48 + set.iter().map(|c| c.len() + 32).sum::<usize>();
}
bytes += s.dirty.keys().map(|k| k.len() + 40).sum::<usize>();
bytes += s.stale.values().flatten().map(|a| a.bytes.len() + 400).sum::<usize>();
bytes += s
.patterns
.values()
.flat_map(HashMap::values)
.map(|(p, r)| p.canonical().len() + r.len() * 80 + 120)
.sum::<usize>();
let fault_cells = s.faults.keys().filter(|k| !s.entries.contains_key(*k)).count();
MemoStats {
slice_patterns: s.pattern_count,
stale: s.stale_count,
entries: s.count,
cells: s.entries.len() + fault_cells,
dependent_edges: s.edges,
dirty: s.dirty.len(),
approx_bytes: bytes,
}
}
}
impl State {
fn insert(&mut self, e: Entry, capacity: usize) {
let held = match &e {
Entry::Value(a) => self
.entries
.get(&a.id)
.is_some_and(|list| list.iter().any(|x| x.hash == a.hash && x.lo == a.lo && x.hi == a.hi)),
Entry::Fault(f) => self
.faults
.get(&f.id)
.is_some_and(|list| list.iter().any(|x| x.fault == f.fault && x.lo == f.lo && x.hi == f.hi)),
};
if held {
return;
}
if let Entry::Value(a) = &e {
if let Some(old) = self.stale.remove(&a.id) {
self.stale_count -= old.len();
}
}
if self.count + self.stale_count >= capacity {
self.entries.clear();
self.faults.clear();
self.readers.clear();
self.stale.clear();
self.patterns.clear();
self.pattern_count = 0;
self.count = 0;
self.stale_count = 0;
self.edges = 0;
}
let id = e.id().to_string();
for d in e.deps() {
if self.readers.entry(d.clone()).or_default().insert(id.clone()) {
self.edges += 1;
}
}
for p in e.patterns() {
let by_id = self.patterns.entry(p.fn_hash().to_string()).or_default();
if !by_id.contains_key(p.id()) {
self.pattern_count += 1;
}
by_id.entry(p.id().to_string()).or_insert_with(|| (p.clone(), HashSet::new())).1.insert(id.clone());
}
match e {
Entry::Value(a) => self.entries.entry(a.id.clone()).or_default().push(a),
Entry::Fault(f) => self.faults.entry(f.id.clone()).or_default().push(f),
}
self.count += 1;
}
fn finish(&mut self, start: u64) {
if let Some(n) = self.active.get_mut(&start) {
*n -= 1;
if *n == 0 {
self.active.remove(&start);
}
}
match self.active.keys().next().copied() {
None => {
self.dirty.clear();
self.added.clear();
}
Some(oldest) => {
self.dirty.retain(|_, m| *m > oldest);
self.added.retain(|(m, _)| *m > oldest);
}
}
}
}