1use crate::ast::{CellDecl, Expr, ExprKind, Item, Program};
2use crate::bind::{Host, LocalHost};
3use crate::error::Diagnostic;
4use crate::eval::{Engine, Env};
5use crate::value::{Instant, Value};
6
7#[derive(Debug, Clone, Default)]
9pub struct FlatNameIndex {
10 entries: Vec<(String, usize)>,
11}
12
13impl FlatNameIndex {
14 pub fn new() -> Self {
15 Self {
16 entries: Vec::new(),
17 }
18 }
19
20 pub fn insert(&mut self, name: String, idx: usize) {
21 match self.entries.binary_search_by(|(k, _)| k.as_str().cmp(name.as_str())) {
22 Ok(pos) => self.entries[pos].1 = idx,
23 Err(pos) => self.entries.insert(pos, (name, idx)),
24 }
25 }
26
27 pub fn get(&self, name: &str) -> Option<&usize> {
28 self.entries
29 .binary_search_by(|(k, _)| k.as_str().cmp(name))
30 .ok()
31 .map(|pos| &self.entries[pos].1)
32 }
33}
34
35impl std::ops::Index<&str> for FlatNameIndex {
36 type Output = usize;
37
38 fn index(&self, name: &str) -> &Self::Output {
39 self.get(name).expect("reactive cell name not found")
40 }
41}
42
43#[derive(Debug, Clone, PartialEq)]
45pub enum ReactiveCellError {
46 CycleDetected { cycle: Vec<String> },
48 CellNotFound(String),
50 EvaluationError(String),
52}
53
54impl std::fmt::Display for ReactiveCellError {
55 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
56 match self {
57 Self::CycleDetected { cycle } => {
58 write!(
59 f,
60 "cycle detected in reactive cell graph: {}",
61 cycle.join(" -> ")
62 )
63 }
64 Self::CellNotFound(name) => write!(f, "reactive cell '{name}' not found"),
65 Self::EvaluationError(msg) => write!(f, "evaluation error in cell: {msg}"),
66 }
67 }
68}
69
70impl std::error::Error for ReactiveCellError {}
71
72impl From<Diagnostic> for ReactiveCellError {
73 fn from(diag: Diagnostic) -> Self {
74 Self::EvaluationError(diag.message)
75 }
76}
77
78#[derive(Debug, Clone)]
80pub struct ReactiveCell {
81 pub id: usize,
83 pub name: String,
85 pub decl: CellDecl,
87 pub dependencies: Vec<String>,
89 pub dependents: Vec<usize>,
91 pub value: Value,
93 pub is_dirty: bool,
95 pub is_temporal: bool,
97}
98
99#[derive(Debug, Clone)]
101pub struct ReactiveCellGraph {
102 pub cells: Vec<ReactiveCell>,
104 pub name_to_index: FlatNameIndex,
106 pub topo_order: Vec<usize>,
108 pub dirty_words: Vec<u64>,
110 pub clock_seconds: f64,
112}
113
114impl ReactiveCellGraph {
115 pub fn new() -> Self {
117 Self {
118 cells: Vec::new(),
119 name_to_index: FlatNameIndex::new(),
120 topo_order: Vec::new(),
121 dirty_words: Vec::new(),
122 clock_seconds: 0.0,
123 }
124 }
125
126 pub fn from_program(program: &Program) -> Result<Self, ReactiveCellError> {
128 let mut graph = Self::new();
129 for item in &program.items {
130 if let Item::Cell(cd) = item {
131 graph.add_cell(cd.clone());
132 }
133 }
134 graph.compile()?;
135 Ok(graph)
136 }
137
138 pub fn add_cell(&mut self, decl: CellDecl) -> usize {
140 let id = self.cells.len();
141 let name = decl.name.clone();
142 let is_temporal = !decl.params.is_empty();
143 let mut dependencies = extract_expr_dependencies(&decl.expr);
144 if let Some(ref when_expr) = decl.when {
145 dependencies.extend(extract_expr_dependencies(when_expr));
146 }
147
148 let cell = ReactiveCell {
149 id,
150 name: name.clone(),
151 decl,
152 dependencies,
153 dependents: Vec::new(),
154 value: Value::Null,
155 is_dirty: true,
156 is_temporal,
157 };
158
159 self.name_to_index.insert(name, id);
160 self.cells.push(cell);
161 self.set_dirty_bit(id);
162 id
163 }
164
165 fn dirty_word_bit(idx: usize) -> (usize, u64) {
166 (idx / 64, 1u64 << (idx % 64))
167 }
168
169 fn ensure_dirty_word(&mut self, word: usize) {
170 if self.dirty_words.len() <= word {
171 self.dirty_words.resize(word + 1, 0);
172 }
173 }
174
175 fn set_dirty_bit(&mut self, idx: usize) {
176 let (word, bit) = Self::dirty_word_bit(idx);
177 self.ensure_dirty_word(word);
178 self.dirty_words[word] |= bit;
179 }
180
181 fn clear_dirty_bit(&mut self, idx: usize) {
182 let (word, bit) = Self::dirty_word_bit(idx);
183 self.ensure_dirty_word(word);
184 self.dirty_words[word] &= !bit;
185 }
186
187 pub fn is_dirty_bit(&self, idx: usize) -> bool {
189 let (word, bit) = Self::dirty_word_bit(idx);
190 self.dirty_words
191 .get(word)
192 .map(|w| w & bit != 0)
193 .unwrap_or(false)
194 }
195
196 pub fn dirty_mask(&self) -> u64 {
198 self.dirty_words.first().copied().unwrap_or(0)
199 }
200
201 pub fn compile(&mut self) -> Result<(), ReactiveCellError> {
203 let n = self.cells.len();
204 for i in 0..n {
205 self.cells[i].dependents.clear();
206 }
207
208 for i in 0..n {
210 let deps = self.cells[i].dependencies.clone();
211 for dep in deps {
212 if let Some(&dep_idx) = self.name_to_index.get(&dep) {
213 if !self.cells[dep_idx].dependents.contains(&i) {
214 self.cells[dep_idx].dependents.push(i);
215 }
216 }
217 }
218 }
219
220 let mut in_degree = vec![0usize; n];
222 for i in 0..n {
223 for &dep in &self.cells[i].dependents {
224 in_degree[dep] += 1;
225 }
226 }
227
228 let mut queue: Vec<usize> = (0..n).filter(|&i| in_degree[i] == 0).collect();
229 let mut order = Vec::with_capacity(n);
230
231 while let Some(u) = queue.pop() {
232 order.push(u);
233 for &v in &self.cells[u].dependents {
234 in_degree[v] -= 1;
235 if in_degree[v] == 0 {
236 queue.push(v);
237 }
238 }
239 }
240
241 if order.len() < n {
242 let cycle_nodes: Vec<String> = (0..n)
244 .filter(|&i| in_degree[i] > 0)
245 .map(|i| self.cells[i].name.clone())
246 .collect();
247 return Err(ReactiveCellError::CycleDetected { cycle: cycle_nodes });
248 }
249
250 self.topo_order = order;
251 self.mark_all_dirty();
252 Ok(())
253 }
254
255 pub fn mark_dirty(&mut self, name: &str) {
257 if let Some(&idx) = self.name_to_index.get(name) {
258 self.mark_dirty_index(idx);
259 }
260 }
261
262 fn mark_dirty_index(&mut self, idx: usize) {
263 self.cells[idx].is_dirty = true;
264 self.set_dirty_bit(idx);
265 for &dep in &self.cells[idx].dependents.clone() {
266 self.mark_dirty_index(dep);
267 }
268 }
269
270 pub fn mark_all_dirty(&mut self) {
272 for cell in &mut self.cells {
273 cell.is_dirty = true;
274 }
275 let words = if self.cells.is_empty() {
276 0
277 } else {
278 (self.cells.len() + 63) / 64
279 };
280 self.dirty_words = vec![0; words];
281 for i in 0..self.cells.len() {
282 self.set_dirty_bit(i);
283 }
284 }
285
286 pub fn set_input(&mut self, name: &str, value: Value, env: &mut Env) {
288 env.vars.insert(name.to_string(), value.clone());
289 if let Some(&idx) = self.name_to_index.get(name) {
290 self.cells[idx].value = value;
291 self.cells[idx].is_dirty = false;
292 self.clear_dirty_bit(idx);
293 for &dep in &self.cells[idx].dependents.clone() {
294 self.mark_dirty_index(dep);
295 }
296 } else {
297 self.mark_dirty(name);
298 }
299 }
300
301 pub fn step(
306 &mut self,
307 env: &mut Env,
308 dt_seconds: f64,
309 ) -> Result<Vec<(String, Value)>, ReactiveCellError> {
310 let mut local_host = LocalHost::default();
311 let mut engine = Engine::new(&mut local_host, crate::budget::Budget::default());
312 self.step_with(&mut engine, env, dt_seconds)
313 }
314
315 pub const CELL_BATCH_512: usize = 512;
319
320 pub fn evaluate_cell_batch_512<H: Host>(
323 &mut self,
324 engine: &mut Engine<'_, H>,
325 env: &mut Env,
326 dt_seconds: f64,
327 ) -> Result<Vec<(String, Value)>, ReactiveCellError> {
328 self.clock_seconds += dt_seconds;
329 let secs = self.clock_seconds.floor() as i64;
330 let nanos = ((self.clock_seconds - self.clock_seconds.floor()) * 1e9) as u32;
331 let clock_instant = Instant::unix(secs, nanos);
332
333 for i in 0..self.cells.len() {
334 if self.cells[i].is_temporal {
335 self.mark_dirty_index(i);
336 }
337 }
338
339 let mut ready = Vec::new();
340 for &idx in &self.topo_order {
341 if ready.len() >= crate::accel::cell_batch_cap() {
342 break;
343 }
344 if !self.cells[idx].is_dirty {
345 continue;
346 }
347 let deps_ready = self.cells[idx].dependencies.iter().all(|name| {
348 match self.name_to_index.get(name) {
349 Some(&dep) => !self.cells[dep].is_dirty,
350 None => true,
351 }
352 });
353 if deps_ready {
354 ready.push(idx);
355 }
356 }
357
358 let mut updated = Vec::new();
359 for idx in ready {
360 if self.cells[idx].is_temporal {
361 if let Some(first_param) = self.cells[idx].decl.params.first() {
362 env.vars.insert(
363 first_param.name.clone(),
364 Value::Instant(clock_instant.clone()),
365 );
366 }
367 }
368 let should_run = if let Some(ref cond) = self.cells[idx].decl.when {
369 match engine.eval_expr(cond, env) {
370 Ok(v) => v.is_truthy(),
371 Err(e) => return Err(ReactiveCellError::EvaluationError(e.message)),
372 }
373 } else {
374 true
375 };
376 if should_run {
377 match engine.eval_expr(&self.cells[idx].decl.expr, env) {
378 Ok(val) => {
379 self.cells[idx].value = val.clone();
380 self.cells[idx].is_dirty = false;
381 self.clear_dirty_bit(idx);
382 env.vars.insert(self.cells[idx].name.clone(), val.clone());
383 updated.push((self.cells[idx].name.clone(), val));
384 }
385 Err(e) => return Err(ReactiveCellError::EvaluationError(e.message)),
386 }
387 } else {
388 self.cells[idx].is_dirty = false;
389 self.clear_dirty_bit(idx);
390 }
391 }
392 Ok(updated)
393 }
394
395 pub fn step_with<H: Host>(
397 &mut self,
398 engine: &mut Engine<'_, H>,
399 env: &mut Env,
400 dt_seconds: f64,
401 ) -> Result<Vec<(String, Value)>, ReactiveCellError> {
402 self.clock_seconds += dt_seconds;
403 let secs = self.clock_seconds.floor() as i64;
404 let nanos = ((self.clock_seconds - self.clock_seconds.floor()) * 1e9) as u32;
405 let clock_instant = Instant::unix(secs, nanos);
406
407 for i in 0..self.cells.len() {
408 if self.cells[i].is_temporal {
409 self.mark_dirty_index(i);
410 }
411 }
412
413 let mut updated = Vec::new();
414 let topo = self.topo_order.clone();
415
416 for &idx in &topo {
417 if self.cells[idx].is_dirty {
418 if self.cells[idx].is_temporal {
419 if let Some(first_param) = self.cells[idx].decl.params.first() {
420 env.vars.insert(
421 first_param.name.clone(),
422 Value::Instant(clock_instant.clone()),
423 );
424 }
425 }
426
427 let should_run = if let Some(ref cond) = self.cells[idx].decl.when {
428 match engine.eval_expr(cond, env) {
429 Ok(v) => v.is_truthy(),
430 Err(e) => return Err(ReactiveCellError::EvaluationError(e.message)),
431 }
432 } else {
433 true
434 };
435
436 if should_run {
437 match engine.eval_expr(&self.cells[idx].decl.expr, env) {
438 Ok(val) => {
439 self.cells[idx].value = val.clone();
440 self.cells[idx].is_dirty = false;
441 self.clear_dirty_bit(idx);
442 env.vars.insert(self.cells[idx].name.clone(), val.clone());
443 updated.push((self.cells[idx].name.clone(), val));
444 }
445 Err(e) => return Err(ReactiveCellError::EvaluationError(e.message)),
446 }
447 } else {
448 self.cells[idx].is_dirty = false;
449 self.clear_dirty_bit(idx);
450 }
451 }
452 }
453
454 Ok(updated)
455 }
456
457 pub fn get_value(&self, name: &str) -> Option<&Value> {
459 self.name_to_index
460 .get(name)
461 .map(|&idx| &self.cells[idx].value)
462 }
463}
464
465impl Default for ReactiveCellGraph {
466 fn default() -> Self {
467 Self::new()
468 }
469}
470
471fn extract_expr_dependencies(expr: &Expr) -> Vec<String> {
473 let mut deps = Vec::new();
474 walk_expr_deps(expr, &mut deps);
475 deps.sort();
476 deps.dedup();
477 deps
478}
479
480fn walk_expr_deps(expr: &Expr, deps: &mut Vec<String>) {
481 match &expr.kind {
482 ExprKind::Ident(name) => {
483 deps.push(name.clone());
484 }
485 ExprKind::Binary { left, right, .. } => {
486 walk_expr_deps(left, deps);
487 walk_expr_deps(right, deps);
488 }
489 ExprKind::Unary { expr, .. } | ExprKind::Await(expr) | ExprKind::Try(expr) => {
490 walk_expr_deps(expr, deps);
491 }
492 ExprKind::Member { recv, .. } => {
493 walk_expr_deps(recv, deps);
494 }
495 ExprKind::Index { recv, index } => {
496 walk_expr_deps(recv, deps);
497 walk_expr_deps(index, deps);
498 }
499 ExprKind::Call { callee, args } => {
500 walk_expr_deps(callee, deps);
501 for arg in args {
502 match arg {
503 crate::ast::Arg::Pos(e) => walk_expr_deps(e, deps),
504 crate::ast::Arg::Named(na) => walk_expr_deps(&na.value, deps),
505 }
506 }
507 }
508 ExprKind::List(items) => {
509 for item in items {
510 walk_expr_deps(item, deps);
511 }
512 }
513 ExprKind::Record(fields) => {
514 for f in fields {
515 walk_expr_deps(&f.value, deps);
516 }
517 }
518 ExprKind::Interpolate(parts) => {
519 for p in parts {
520 walk_expr_deps(p, deps);
521 }
522 }
523 ExprKind::Pipe { left, right } => {
524 walk_expr_deps(left, deps);
525 walk_expr_deps(right, deps);
526 }
527 ExprKind::Triple {
528 subject,
529 predicate,
530 object,
531 } => {
532 walk_expr_deps(subject, deps);
533 walk_expr_deps(predicate, deps);
534 walk_expr_deps(object, deps);
535 }
536 ExprKind::Reified {
537 subject,
538 predicate,
539 object,
540 reifier,
541 } => {
542 walk_expr_deps(subject, deps);
543 walk_expr_deps(predicate, deps);
544 walk_expr_deps(object, deps);
545 walk_expr_deps(reifier, deps);
546 }
547 ExprKind::Lambda { body, .. } => walk_expr_deps(body, deps),
548 ExprKind::Tween { from, to, over, .. } => {
549 walk_expr_deps(from, deps);
550 walk_expr_deps(to, deps);
551 walk_expr_deps(over, deps);
552 }
553 ExprKind::IfElse {
554 cond,
555 then_value,
556 else_value,
557 } => {
558 walk_expr_deps(cond, deps);
559 walk_expr_deps(then_value, deps);
560 walk_expr_deps(else_value, deps);
561 }
562 _ => {}
563 }
564}
565
566#[cfg(test)]
567mod tests {
568 use super::*;
569 use crate::eval::Env;
570 use crate::parse::parse_program;
571
572 #[test]
573 fn dirty_bits_cover_more_than_64_cells() {
574 let mut src = String::from("cell c0 := 0;\n");
575 for i in 1..70 {
576 src.push_str(&format!("cell c{i} := c{} + 1;\n", i - 1));
577 }
578 let prog = parse_program(&src).expect("parse");
579 let mut graph = ReactiveCellGraph::from_program(&prog).expect("graph");
580 assert!(graph.cells.len() >= 70);
581 assert!(graph.is_dirty_bit(0));
582 assert!(graph.is_dirty_bit(69));
583 let mut env = Env::default();
584 graph.step(&mut env, 0.0).expect("step");
585 assert!(
586 !graph.is_dirty_bit(69),
587 "step should clear dirty bits past 64"
588 );
589 graph.mark_dirty("c0");
590 assert!(graph.is_dirty_bit(0));
591 assert!(
592 graph.is_dirty_bit(69),
593 "downstream cell 69 must dirty when c0 changes"
594 );
595 }
596
597 #[test]
598 fn cell_batch_512_evaluates_ready_cluster() {
599 let src = "cell a := 1;\ncell b := 2;\ncell c := a + b;\n";
600 let prog = parse_program(src).expect("parse");
601 let mut graph = ReactiveCellGraph::from_program(&prog).expect("graph");
602 let mut env = Env::default();
603 let mut host = crate::bind::LocalHost::default();
604 let mut engine = Engine::new(&mut host, crate::budget::Budget::default());
605 let updated = graph
606 .evaluate_cell_batch_512(&mut engine, &mut env, 0.0)
607 .expect("batch");
608 assert!(!updated.is_empty());
609 assert!(updated.len() <= ReactiveCellGraph::CELL_BATCH_512);
610 assert_eq!(graph.get_value("a"), Some(&Value::I64(1)));
611 assert_eq!(graph.get_value("b"), Some(&Value::I64(2)));
612 if graph.is_dirty_bit(graph.name_to_index["c"]) {
614 graph
615 .evaluate_cell_batch_512(&mut engine, &mut env, 0.0)
616 .expect("second batch");
617 }
618 assert_eq!(graph.get_value("c"), Some(&Value::I64(3)));
619 }
620}