Skip to main content

vibe/
reactive_cell.rs

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/// Sorted contiguous name-to-index lookup table (zero per-node BTree allocations).
8#[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/// An error that can occur in the reactive cell graph engine.
44#[derive(Debug, Clone, PartialEq)]
45pub enum ReactiveCellError {
46    /// A cyclic dependency was detected among reactive cells.
47    CycleDetected { cycle: Vec<String> },
48    /// A cell with the given name was not found.
49    CellNotFound(String),
50    /// Evaluation error during cell computation.
51    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/// A compiled reactive cell node.
79#[derive(Debug, Clone)]
80pub struct ReactiveCell {
81    /// Unique identifier / index in graph.
82    pub id: usize,
83    /// Cell identifier name.
84    pub name: String,
85    /// The original declaration AST.
86    pub decl: CellDecl,
87    /// Names of variables and cells this cell depends on.
88    pub dependencies: Vec<String>,
89    /// Indices of cells that depend on this cell (downstream).
90    pub dependents: Vec<usize>,
91    /// Current evaluated cached value.
92    pub value: Value,
93    /// True if the cell needs re-evaluation.
94    pub is_dirty: bool,
95    /// True if this cell takes time/clock input parameters (e.g. `t: Instant`).
96    pub is_temporal: bool,
97}
98
99/// Compiled reactive cell dependency graph.
100#[derive(Debug, Clone)]
101pub struct ReactiveCellGraph {
102    /// List of cell nodes.
103    pub cells: Vec<ReactiveCell>,
104    /// Sorted flat lookup table from cell name to its index in `cells`.
105    pub name_to_index: FlatNameIndex,
106    /// Topologically sorted order of cell indices (dependencies before dependents).
107    pub topo_order: Vec<usize>,
108    /// Dirty bitset words (64 cells per word; grows past 64 cells).
109    pub dirty_words: Vec<u64>,
110    /// Current logical time clock (in seconds since epoch / start).
111    pub clock_seconds: f64,
112}
113
114impl ReactiveCellGraph {
115    /// Construct a new empty reactive cell graph.
116    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    /// Build a reactive cell graph from an AST Program.
127    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    /// Add a cell declaration to the graph.
139    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    /// True if cell `idx` is marked dirty. Works past 64 cells.
188    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    /// First 64 dirty bits (debug / HUD). Prefer [`Self::is_dirty_bit`].
197    pub fn dirty_mask(&self) -> u64 {
198        self.dirty_words.first().copied().unwrap_or(0)
199    }
200
201    /// Compile dependencies, wire dependents, check cycles, and compute topological order.
202    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        // Build adjacency: dependency -> dependent
209        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        // Kahn's algorithm for topological sorting and cycle detection
221        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            // Cycle detected — collect remaining nodes with in_degree > 0
243            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    /// Mark a single cell and all its transitive downstream dependents as dirty.
256    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    /// Mark all cells in the graph as dirty.
271    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    /// Set an external input signal / variable and mark downstream cells dirty.
287    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    /// Advance time and evaluate dirty cells on a **local** in-process host.
302    ///
303    /// Prefer [`Self::step_with`] when a live `Host` (Poet, tests with
304    /// query rows, GPU) must dispatch capability.invoke.
305    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    /// Homogeneous ready-cluster size for P16.2. Scalar path still
316    /// evaluates one cell at a time; the batch is the set of dirty cells
317    /// whose dependencies are already clean, capped at 512.
318    pub const CELL_BATCH_512: usize = 512;
319
320    /// One ready cluster of up to 512 dirty cells, then stop.
321    /// Callers loop until the dirty set is empty.
322    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    /// Advance time and evaluate dirty cells through the caller's engine/host.
396    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    /// Retrieve the current cached value of a cell by name.
458    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
471/// Recursively collect all identifier variable names referenced in an expression in deterministic sorted order.
472fn 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        // c depends on a and b; first ready cluster is a and b.
613        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}