Skip to main content

yse_model/
graph.rs

1//! Internal reactive graph: nodes, transactions, and glitch-free propagation.
2
3use std::any::Any;
4use std::cell::{Cell, Ref, RefCell};
5use std::collections::HashSet;
6use std::panic::{AssertUnwindSafe, catch_unwind, resume_unwind};
7use std::rc::{Rc, Weak};
8use std::sync::atomic::{AtomicU64, Ordering};
9
10use crate::diagnostics::DiagnosticEvent;
11
12#[derive(Clone, Copy, PartialEq, Eq, Debug)]
13pub(crate) enum NodeKind {
14    Signal,
15    Stream,
16}
17
18/// Shared per-node state used by the propagation machinery.
19pub(crate) struct NodeCommon {
20    kind: NodeKind,
21    id: u64,
22    rank: Cell<usize>,
23    parents: RefCell<Vec<Weak<dyn Node>>>,
24    dependents: RefCell<Vec<Rc<dyn Node>>>,
25    scheduled: Cell<bool>,
26    incoming: RefCell<Vec<Rc<dyn Any>>>,
27    ever_observed: Cell<bool>,
28}
29
30impl NodeCommon {
31    pub fn new(kind: NodeKind) -> Self {
32        static NEXT_NODE_ID: AtomicU64 = AtomicU64::new(1);
33        Self {
34            kind,
35            id: NEXT_NODE_ID.fetch_add(1, Ordering::Relaxed),
36            rank: Cell::new(0),
37            parents: RefCell::new(Vec::new()),
38            dependents: RefCell::new(Vec::new()),
39            scheduled: Cell::new(false),
40            incoming: RefCell::new(Vec::new()),
41            ever_observed: Cell::new(false),
42        }
43    }
44}
45
46/// A node in the reactive graph.
47pub(crate) trait Node {
48    fn common(&self) -> &NodeCommon;
49
50    fn kind(&self) -> NodeKind {
51        self.common().kind
52    }
53
54    fn id(&self) -> u64 {
55        self.common().id
56    }
57
58    fn rank(&self) -> usize {
59        self.common().rank.get()
60    }
61
62    fn set_rank(&self, rank: usize) {
63        self.common().rank.set(rank);
64    }
65
66    fn parents(&self) -> Ref<'_, Vec<Weak<dyn Node>>> {
67        self.common().parents.borrow()
68    }
69
70    fn dependents(&self) -> Ref<'_, Vec<Rc<dyn Node>>> {
71        self.common().dependents.borrow()
72    }
73
74    fn is_scheduled(&self) -> bool {
75        self.common().scheduled.get()
76    }
77
78    fn set_scheduled(&self, scheduled: bool) {
79        self.common().scheduled.set(scheduled);
80    }
81
82    fn push_incoming(&self, value: Rc<dyn Any>) {
83        self.common().incoming.borrow_mut().push(value);
84    }
85
86    fn take_incoming(&self) -> Vec<Rc<dyn Any>> {
87        std::mem::take(&mut *self.common().incoming.borrow_mut())
88    }
89
90    /// Current value for signal nodes, `None` for stream nodes.
91    fn current_any(&self) -> Option<Rc<dyn Any>> {
92        None
93    }
94
95    /// Whether this node is a terminal observer (always scheduled, never pruned).
96    fn is_observer(&self) -> bool {
97        false
98    }
99
100    /// Whether this stream derives exclusively from signal state (used for
101    /// restart re-synchronisation).
102    fn is_signal_backed(&self) -> bool {
103        false
104    }
105
106    fn ever_observed(&self) -> bool {
107        self.common().ever_observed.get()
108    }
109
110    fn mark_observed(&self) {
111        self.common().ever_observed.set(true);
112    }
113
114    /// Recompute the current output of a signal-backed stream chain from the
115    /// current signal state, without emitting through the graph.
116    fn pull_output(&self) -> Option<Rc<dyn Any>> {
117        None
118    }
119
120    fn apply_write(&self, _value: Rc<dyn Any>) {
121        panic!("this observable is not writable");
122    }
123
124    fn deactivate(&self) {}
125
126    /// Invoke the observer callback (observer nodes only).
127    fn fire(&self, _value: Rc<dyn Any>) {}
128
129    /// Recompute a signal node's value from its parents (signal nodes only).
130    fn recompute(&self) -> bool {
131        false
132    }
133
134    /// Process pending events / parent changes during a transaction and
135    /// return the outputs that should be delivered to dependents.
136    fn process(&self, tx: &TxState) -> Vec<Rc<dyn Any>>;
137
138    fn add_parent(&self, parent: &Rc<dyn Node>) {
139        self.common()
140            .parents
141            .borrow_mut()
142            .push(Rc::downgrade(parent));
143    }
144
145    fn remove_dependent(&self, child: &Rc<dyn Node>) {
146        self.common()
147            .dependents
148            .borrow_mut()
149            .retain(|dep| !Rc::ptr_eq(dep, child));
150    }
151
152    /// Receive an event forwarded from a `flat_map_switch` inner stream.
153    fn forward_incoming(&self, _value: Rc<dyn Any>) {
154        panic!("node does not accept forwarded events");
155    }
156}
157
158/// A write performed during propagation, applied after the current pass.
159pub(crate) struct DeferredWrite {
160    pub node: Rc<dyn Node>,
161    pub value: Rc<dyn Any>,
162}
163
164/// Per-thread transaction state.
165pub(crate) struct TxState {
166    pub id: u64,
167    pub seq: Cell<u64>,
168    pub work: RefCell<Vec<(u64, Rc<dyn Node>)>>,
169    pub deferred: RefCell<Vec<DeferredWrite>>,
170    pub fires: RefCell<Vec<(Weak<dyn Node>, Rc<dyn Any>)>>,
171    pub panic: RefCell<Option<Box<dyn Any + Send>>>,
172    pub propagating: Cell<bool>,
173    pub processed: Cell<usize>,
174    pub fired: Cell<usize>,
175    pub deferred_count: Cell<usize>,
176}
177
178impl TxState {
179    pub fn new() -> Self {
180        static NEXT_TX_ID: AtomicU64 = AtomicU64::new(1);
181        Self {
182            id: NEXT_TX_ID.fetch_add(1, Ordering::Relaxed),
183            seq: Cell::new(0),
184            work: RefCell::new(Vec::new()),
185            deferred: RefCell::new(Vec::new()),
186            fires: RefCell::new(Vec::new()),
187            panic: RefCell::new(None),
188            propagating: Cell::new(false),
189            processed: Cell::new(0),
190            fired: Cell::new(0),
191            deferred_count: Cell::new(0),
192        }
193    }
194}
195
196thread_local! {
197    static TX: RefCell<Option<Rc<TxState>>> = const { RefCell::new(None) };
198}
199
200fn tx() -> Option<Rc<TxState>> {
201    TX.with(|t| t.borrow().clone())
202}
203
204/// Queue a node for processing in the current transaction, if any.
205pub(crate) fn schedule_node(node: Rc<dyn Node>) {
206    if let Some(tx) = tx() {
207        schedule_into(&tx, node);
208    }
209}
210
211fn schedule_into(tx: &TxState, node: Rc<dyn Node>) {
212    if node.is_scheduled() {
213        return;
214    }
215    node.set_scheduled(true);
216    let seq = tx.seq.get();
217    tx.seq.set(seq + 1);
218    tx.work.borrow_mut().push((seq, node));
219}
220
221/// Run `f` inside a single transaction. Nested calls join the outer transaction.
222///
223/// Writes applied inside the block become visible immediately to readers, and
224/// are propagated once when the block ends, including when `f` panics. Writes performed during
225/// propagation (from inside observers) are queued and applied in FIFO order
226/// after the current pass.
227pub fn transaction<R>(f: impl FnOnce() -> R) -> R {
228    if tx().is_some() {
229        return f();
230    }
231
232    let tx_rc = Rc::new(TxState::new());
233    TX.with(|t| *t.borrow_mut() = Some(tx_rc.clone()));
234    crate::diagnostics::Diagnostics::emit(DiagnosticEvent::TransactionStarted { id: tx_rc.id });
235
236    let result = catch_unwind(AssertUnwindSafe(f));
237    let propagation = catch_unwind(AssertUnwindSafe(|| {
238        tx_rc.propagating.set(true);
239        loop {
240            process_work(&tx_rc);
241            apply_deferred(&tx_rc);
242            if tx_rc.work.borrow().is_empty() && tx_rc.deferred.borrow().is_empty() {
243                deliver_fires(&tx_rc);
244                if tx_rc.deferred.borrow().is_empty() {
245                    break;
246                }
247            }
248        }
249    }));
250    tx_rc.propagating.set(false);
251    if propagation.is_err() {
252        abort_transaction(&tx_rc);
253    }
254
255    TX.with(|t| *t.borrow_mut() = None);
256    crate::diagnostics::Diagnostics::emit(DiagnosticEvent::TransactionEnded {
257        id: tx_rc.id,
258        processed: tx_rc.processed.get(),
259        fired: tx_rc.fired.get(),
260        deferred: tx_rc.deferred_count.get(),
261    });
262    crate::diagnostics::Diagnostics::flush_global();
263
264    match result {
265        Ok(value) => {
266            if let Err(payload) = propagation {
267                resume_unwind(payload);
268            }
269            if let Some(panic) = tx_rc.panic.borrow_mut().take() {
270                resume_unwind(panic);
271            }
272            value
273        }
274        // State writes are deliberately committed before this point. This is
275        // the only useful general rule for arbitrary `T`: rolling them back
276        // would require cloning or compensating every writable node.
277        Err(payload) => resume_unwind(payload),
278    }
279}
280
281/// Write a value into a writable node (a `Var` or `Sink`).
282pub(crate) fn write_node(node: Rc<dyn Node>, value: Rc<dyn Any>) {
283    match tx() {
284        Some(tx) if tx.propagating.get() => {
285            crate::diagnostics::Diagnostics::emit(DiagnosticEvent::DeferredWriteQueued {
286                transaction: tx.id,
287            });
288            tx.deferred_count.set(tx.deferred_count.get() + 1);
289            tx.deferred.borrow_mut().push(DeferredWrite { node, value });
290        }
291        Some(tx) => {
292            node.apply_write(value);
293            schedule_into(&tx, node);
294        }
295        None => transaction(|| write_node(node, value)),
296    }
297}
298
299/// Connect `child` as a dependent of `parent`, rejecting cycles.
300pub(crate) fn connect(parent: Rc<dyn Node>, child: Rc<dyn Node>) {
301    assert_no_cycle(&parent, &child);
302    child.add_parent(&parent);
303    parent.common().dependents.borrow_mut().push(child.clone());
304    bubble_ranks(&child);
305}
306
307/// Panic if `target` is already an ancestor of `parent` (i.e. the edge would
308/// create a cycle).
309pub(crate) fn assert_no_cycle(parent: &Rc<dyn Node>, target: &Rc<dyn Node>) {
310    let mut stack = vec![parent.clone()];
311    let mut seen = HashSet::new();
312    while let Some(node) = stack.pop() {
313        if Rc::ptr_eq(&node, target) {
314            crate::diagnostics::Diagnostics::emit(DiagnosticEvent::CycleRejected);
315            panic!("reactive cycle detected: an observable cannot depend on itself");
316        }
317        let addr = Rc::as_ptr(&node) as *const () as usize;
318        if !seen.insert(addr) {
319            continue;
320        }
321        for ancestor in node.parents().iter().filter_map(|w| w.upgrade()) {
322            stack.push(ancestor);
323        }
324    }
325}
326
327fn bubble_ranks(node: &Rc<dyn Node>) {
328    let new_rank = node
329        .parents()
330        .iter()
331        .filter_map(|w| w.upgrade())
332        .map(|p| p.rank())
333        .max()
334        .map_or(0, |rank| rank + 1);
335    if new_rank != node.rank() {
336        node.set_rank(new_rank);
337        let dependents: Vec<Rc<dyn Node>> = node.dependents().iter().cloned().collect();
338        for dependent in dependents {
339            bubble_ranks(&dependent);
340        }
341    }
342}
343
344fn process_work(tx: &TxState) {
345    loop {
346        let next = {
347            let mut work = tx.work.borrow_mut();
348            let index = work
349                .iter()
350                .enumerate()
351                .min_by_key(|(_, (seq, node))| (node.rank(), *seq))
352                .map(|(index, _)| index);
353            index.map(|index| work.swap_remove(index))
354        };
355        let Some((_, node)) = next else { break };
356        node.set_scheduled(false);
357        tx.processed.set(tx.processed.get() + 1);
358        crate::diagnostics::Diagnostics::emit(DiagnosticEvent::NodeProcessed {
359            node: node.id(),
360            rank: node.rank(),
361            signal: node.kind() == NodeKind::Signal,
362        });
363        let outputs = node.process(tx);
364        deliver(tx, &node, outputs);
365    }
366}
367
368fn deliver(tx: &TxState, parent: &Rc<dyn Node>, outputs: Vec<Rc<dyn Any>>) {
369    if outputs.is_empty() {
370        return;
371    }
372    let dependents: Vec<Rc<dyn Node>> = parent.dependents().iter().cloned().collect();
373    for child in dependents {
374        // Prune streams that have no observers downstream: they are stopped.
375        if !child.is_observer() && child.kind() == NodeKind::Stream && child.dependents().is_empty()
376        {
377            continue;
378        }
379        match parent.kind() {
380            NodeKind::Signal => schedule_into(tx, child),
381            NodeKind::Stream => {
382                for output in &outputs {
383                    child.push_incoming(output.clone());
384                }
385                schedule_into(tx, child);
386            }
387        }
388    }
389}
390
391fn apply_deferred(tx: &TxState) {
392    let writes: Vec<DeferredWrite> = std::mem::take(&mut *tx.deferred.borrow_mut());
393    for write in writes {
394        write.node.apply_write(write.value);
395        schedule_into(tx, write.node.clone());
396    }
397}
398
399fn deliver_fires(tx: &TxState) {
400    let fires: Vec<(Weak<dyn Node>, Rc<dyn Any>)> = std::mem::take(&mut *tx.fires.borrow_mut());
401    for (weak, value) in fires {
402        let Some(node) = weak.upgrade() else { continue };
403        tx.fired.set(tx.fired.get() + 1);
404        crate::diagnostics::Diagnostics::emit(DiagnosticEvent::ObserverFired {
405            observer: node.id(),
406        });
407        let result = catch_unwind(AssertUnwindSafe(|| node.fire(value)));
408        if let Err(payload) = result
409            && tx.panic.borrow().is_none()
410        {
411            *tx.panic.borrow_mut() = Some(payload);
412        }
413    }
414}
415
416/// Clear the bookkeeping left by a panicking propagation pass. In particular,
417/// every queued node must lose its scheduled bit or a later transaction would
418/// silently skip it forever. Stream inputs belong to the aborted pass and are
419/// discarded with that pass.
420fn abort_transaction(tx: &TxState) {
421    let mut seen = HashSet::new();
422    let mut discard = |node: Rc<dyn Node>| {
423        let address = Rc::as_ptr(&node) as *const () as usize;
424        if seen.insert(address) {
425            node.set_scheduled(false);
426            node.take_incoming();
427        }
428    };
429
430    let work = std::mem::take(&mut *tx.work.borrow_mut());
431    for (_, node) in work {
432        discard(node);
433    }
434    let deferred = std::mem::take(&mut *tx.deferred.borrow_mut());
435    for write in deferred {
436        discard(write.node);
437    }
438    tx.fires.borrow_mut().clear();
439}
440
441/// Recompute every signal ancestor of `node` in topological order, so that a
442/// restarted observation sees fully current state.
443pub(crate) fn resync_signal_ancestors(node: &Rc<dyn Node>) {
444    let mut signals = Vec::new();
445    let mut stack = vec![node.clone()];
446    let mut seen = HashSet::new();
447    while let Some(current) = stack.pop() {
448        let addr = Rc::as_ptr(&current) as *const () as usize;
449        if !seen.insert(addr) {
450            continue;
451        }
452        if current.kind() == NodeKind::Signal {
453            signals.push(current.clone());
454        }
455        for parent in current.parents().iter().filter_map(|w| w.upgrade()) {
456            stack.push(parent);
457        }
458    }
459    signals.sort_by_key(|node| node.rank());
460    for signal in signals {
461        signal.recompute();
462    }
463}
464
465/// Handle to an active observation. Dropping it unsubscribes.
466pub struct Subscription {
467    pub(crate) node: Rc<dyn Node>,
468}
469
470impl Drop for Subscription {
471    fn drop(&mut self) {
472        self.node.deactivate();
473        let parents: Vec<Rc<dyn Node>> = self
474            .node
475            .parents()
476            .iter()
477            .filter_map(|w| w.upgrade())
478            .collect();
479        for parent in parents {
480            parent.remove_dependent(&self.node);
481        }
482    }
483}
484
485#[cfg(test)]
486mod tests {
487    use super::*;
488    use crate::nodes::{MapSignalNode, SignalSourceNode};
489
490    #[test]
491    fn cycles_are_rejected() {
492        let diagnostics = crate::diagnostics::Diagnostics::install();
493        let seen = std::rc::Rc::new(std::cell::RefCell::new(Vec::new()));
494        let seen_rc = seen.clone();
495        let _sub = diagnostics
496            .events()
497            .observe(move |event| seen_rc.borrow_mut().push(event.clone()));
498
499        let a: Rc<dyn Node> = Rc::new(SignalSourceNode::new(1i32));
500        let b: Rc<dyn Node> = Rc::new(MapSignalNode::new(
501            a.clone(),
502            Box::new(|value: &i32| value + 1),
503        ));
504        connect(a.clone(), b.clone());
505        let c: Rc<dyn Node> = Rc::new(MapSignalNode::new(
506            b.clone(),
507            Box::new(|value: &i32| value + 1),
508        ));
509        connect(b.clone(), c.clone());
510
511        let result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
512            connect(c.clone(), a.clone())
513        }));
514        assert!(result.is_err(), "connecting a cycle must panic");
515        diagnostics.flush();
516        assert!(
517            seen.borrow()
518                .iter()
519                .any(|e| matches!(e, crate::diagnostics::DiagnosticEvent::CycleRejected)),
520            "cycle rejection must be reported by diagnostics"
521        );
522        diagnostics.uninstall();
523    }
524}