1use 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
18pub(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
46pub(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 fn current_any(&self) -> Option<Rc<dyn Any>> {
92 None
93 }
94
95 fn is_observer(&self) -> bool {
97 false
98 }
99
100 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 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 fn fire(&self, _value: Rc<dyn Any>) {}
128
129 fn recompute(&self) -> bool {
131 false
132 }
133
134 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 fn forward_incoming(&self, _value: Rc<dyn Any>) {
154 panic!("node does not accept forwarded events");
155 }
156}
157
158pub(crate) struct DeferredWrite {
160 pub node: Rc<dyn Node>,
161 pub value: Rc<dyn Any>,
162}
163
164pub(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
204pub(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
221pub 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 Err(payload) => resume_unwind(payload),
278 }
279}
280
281pub(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
299pub(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
307pub(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 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
416fn 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
441pub(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(¤t) 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
465pub 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}