use crate::semantics::{value_eq, EvalErr, Fail, Value};
use rustc_hash::FxHashMap;
use std::cell::{Cell, RefCell};
pub type Key = String;
pub enum DbErr {
Cycle(Vec<Key>),
Fail(Fail),
}
pub type DResult = Result<Value, DbErr>;
pub type Compute = Box<dyn Fn(&Db) -> DResult>;
pub type Resolve = Box<dyn Fn(&str) -> Option<Compute>>;
struct Entry {
value: Value,
deps: Vec<Key>,
changed_rev: u64, verified_rev: u64, }
struct Frame {
key: Key,
deps: RefCell<Vec<Key>>,
}
pub struct Db {
rev: Cell<u64>,
memo: RefCell<FxHashMap<Key, Entry>>,
inputs: RefCell<FxHashMap<Key, Value>>,
input_rev: RefCell<FxHashMap<Key, u64>>,
resolve: Resolve,
stack: RefCell<Vec<Frame>>,
}
impl Db {
pub fn new(resolve: Resolve) -> Db {
Db {
rev: Cell::new(0),
memo: RefCell::new(FxHashMap::default()),
inputs: RefCell::new(FxHashMap::default()),
input_rev: RefCell::new(FxHashMap::default()),
resolve,
stack: RefCell::new(Vec::new()),
}
}
pub fn clear(&self) {
self.memo.borrow_mut().clear();
self.rev.set(self.rev.get() + 1);
}
pub fn revision(&self) -> u64 {
self.rev.get()
}
pub fn set_input(&self, key: &str, value: Value) {
if let Some(old) = self.inputs.borrow().get(key) {
if value_eq(old, &value) {
return;
}
}
self.rev.set(self.rev.get() + 1);
self.inputs.borrow_mut().insert(key.to_string(), value);
self.input_rev
.borrow_mut()
.insert(key.to_string(), self.rev.get());
}
pub fn query(&self, key: &str) -> DResult {
if let Some(top) = self.stack.borrow().last() {
top.deps.borrow_mut().push(key.to_string());
}
self.evaluate(key)
}
fn evaluate(&self, key: &str) -> DResult {
if let Some(v) = self.inputs.borrow().get(key) {
return Ok(v.clone());
}
let cur = self.rev.get();
let (has_memo, verified, deps) = {
let memo = self.memo.borrow();
match memo.get(key) {
Some(m) if m.verified_rev == cur => return Ok(m.value.clone()),
Some(m) => (true, m.verified_rev, m.deps.clone()),
None => (false, 0, Vec::new()),
}
};
if has_memo && self.deps_unchanged(&deps, verified)? {
if let Some(m) = self.memo.borrow_mut().get_mut(key) {
m.verified_rev = cur;
}
return Ok(self.memo.borrow().get(key).unwrap().value.clone());
}
self.recompute(key, has_memo)
}
fn deps_unchanged(&self, deps: &[Key], verified: u64) -> Result<bool, DbErr> {
for d in deps {
self.evaluate(d)?; if self.changed_rev_of(d) > verified {
return Ok(false);
}
}
Ok(true)
}
fn recompute(&self, key: &str, has_prev: bool) -> DResult {
if self.stack.borrow().iter().any(|f| f.key == key) {
let mut cyc: Vec<Key> = self.stack.borrow().iter().map(|f| f.key.clone()).collect();
cyc.push(key.to_string());
return Err(DbErr::Cycle(cyc));
}
let compute = (self.resolve)(key).ok_or_else(|| {
DbErr::Fail(Fail::Eval(EvalErr {
msg: format!("no such query: {key}"),
code: None,
}))
})?;
self.stack.borrow_mut().push(Frame {
key: key.to_string(),
deps: RefCell::new(Vec::new()),
});
let result = compute(self);
let frame = self.stack.borrow_mut().pop().unwrap();
let value = result?; let deps = frame.deps.into_inner();
let cur = self.rev.get();
let prev_changed = if has_prev {
self.memo
.borrow()
.get(key)
.filter(|m| value_eq(&value, &m.value))
.map(|m| m.changed_rev)
} else {
None
};
let changed_rev = prev_changed.unwrap_or(cur);
self.memo.borrow_mut().insert(
key.to_string(),
Entry {
value: value.clone(),
deps,
changed_rev,
verified_rev: cur,
},
);
Ok(value)
}
fn changed_rev_of(&self, key: &str) -> u64 {
if let Some(r) = self.input_rev.borrow().get(key) {
return *r;
}
self.memo
.borrow()
.get(key)
.map(|m| m.changed_rev)
.unwrap_or(0)
}
}