1use crate::semantics::{value_eq, EvalErr, Fail, Value};
17use rustc_hash::FxHashMap;
18use std::cell::{Cell, RefCell};
19
20pub type Key = String;
22
23pub enum DbErr {
26 Cycle(Vec<Key>),
28 Fail(Fail),
30}
31pub type DResult = Result<Value, DbErr>;
33
34pub type Compute = Box<dyn Fn(&Db) -> DResult>;
36pub type Resolve = Box<dyn Fn(&str) -> Option<Compute>>;
38
39struct Entry {
40 value: Value,
41 deps: Vec<Key>,
42 changed_rev: u64, verified_rev: u64, }
45
46struct Frame {
48 key: Key,
49 deps: RefCell<Vec<Key>>,
50}
51
52pub struct Db {
54 rev: Cell<u64>,
55 memo: RefCell<FxHashMap<Key, Entry>>,
56 inputs: RefCell<FxHashMap<Key, Value>>,
57 input_rev: RefCell<FxHashMap<Key, u64>>,
58 resolve: Resolve,
59 stack: RefCell<Vec<Frame>>,
62}
63
64impl Db {
65 pub fn new(resolve: Resolve) -> Db {
67 Db {
68 rev: Cell::new(0),
69 memo: RefCell::new(FxHashMap::default()),
70 inputs: RefCell::new(FxHashMap::default()),
71 input_rev: RefCell::new(FxHashMap::default()),
72 resolve,
73 stack: RefCell::new(Vec::new()),
74 }
75 }
76
77 pub fn clear(&self) {
79 self.memo.borrow_mut().clear();
80 self.rev.set(self.rev.get() + 1);
81 }
82
83 pub fn revision(&self) -> u64 {
85 self.rev.get()
86 }
87
88 pub fn set_input(&self, key: &str, value: Value) {
91 if let Some(old) = self.inputs.borrow().get(key) {
92 if value_eq(old, &value) {
93 return;
94 }
95 }
96 self.rev.set(self.rev.get() + 1);
97 self.inputs.borrow_mut().insert(key.to_string(), value);
98 self.input_rev
99 .borrow_mut()
100 .insert(key.to_string(), self.rev.get());
101 }
102
103 pub fn query(&self, key: &str) -> DResult {
105 if let Some(top) = self.stack.borrow().last() {
106 top.deps.borrow_mut().push(key.to_string());
107 }
108 self.evaluate(key)
109 }
110
111 fn evaluate(&self, key: &str) -> DResult {
113 if let Some(v) = self.inputs.borrow().get(key) {
114 return Ok(v.clone());
115 }
116 let cur = self.rev.get();
117 let (has_memo, verified, deps) = {
119 let memo = self.memo.borrow();
120 match memo.get(key) {
121 Some(m) if m.verified_rev == cur => return Ok(m.value.clone()),
122 Some(m) => (true, m.verified_rev, m.deps.clone()),
123 None => (false, 0, Vec::new()),
124 }
125 };
126 if has_memo && self.deps_unchanged(&deps, verified)? {
127 if let Some(m) = self.memo.borrow_mut().get_mut(key) {
129 m.verified_rev = cur;
130 }
131 return Ok(self.memo.borrow().get(key).unwrap().value.clone());
132 }
133 self.recompute(key, has_memo)
134 }
135
136 fn deps_unchanged(&self, deps: &[Key], verified: u64) -> Result<bool, DbErr> {
137 for d in deps {
138 self.evaluate(d)?; if self.changed_rev_of(d) > verified {
140 return Ok(false);
141 }
142 }
143 Ok(true)
144 }
145
146 fn recompute(&self, key: &str, has_prev: bool) -> DResult {
147 if self.stack.borrow().iter().any(|f| f.key == key) {
148 let mut cyc: Vec<Key> = self.stack.borrow().iter().map(|f| f.key.clone()).collect();
149 cyc.push(key.to_string());
150 return Err(DbErr::Cycle(cyc));
151 }
152 let compute = (self.resolve)(key).ok_or_else(|| {
153 DbErr::Fail(Fail::Eval(EvalErr {
154 msg: format!("no such query: {key}"),
155 code: None,
156 }))
157 })?;
158 self.stack.borrow_mut().push(Frame {
159 key: key.to_string(),
160 deps: RefCell::new(Vec::new()),
161 });
162 let result = compute(self);
163 let frame = self.stack.borrow_mut().pop().unwrap();
164 let value = result?; let deps = frame.deps.into_inner();
166 let cur = self.rev.get();
169 let prev_changed = if has_prev {
170 self.memo
171 .borrow()
172 .get(key)
173 .filter(|m| value_eq(&value, &m.value))
174 .map(|m| m.changed_rev)
175 } else {
176 None
177 };
178 let changed_rev = prev_changed.unwrap_or(cur);
179 self.memo.borrow_mut().insert(
180 key.to_string(),
181 Entry {
182 value: value.clone(),
183 deps,
184 changed_rev,
185 verified_rev: cur,
186 },
187 );
188 Ok(value)
189 }
190
191 fn changed_rev_of(&self, key: &str) -> u64 {
192 if let Some(r) = self.input_rev.borrow().get(key) {
193 return *r;
194 }
195 self.memo
196 .borrow()
197 .get(key)
198 .map(|m| m.changed_rev)
199 .unwrap_or(0)
200 }
201}