1use std::any::{Any, type_name};
20use std::cell::RefCell;
21use std::collections::HashMap;
22use std::marker::PhantomData;
23use std::mem;
24use std::ops::Deref;
25use std::panic::{self, AssertUnwindSafe, Location};
26use std::rc::Rc;
27
28use slotmap::{SlotMap, new_key_type};
29
30use crate::Owner;
31
32pub const MAX_RUNS_PER_FLUSH: u32 = 100;
36
37new_key_type! {
38 pub(crate) struct NodeId;
42}
43
44pub(crate) struct Computed {
46 pub(crate) changed: bool,
48 pub(crate) leftover: Option<Box<dyn Any>>,
51}
52
53pub(crate) type Compute = Box<dyn FnMut() -> Computed>;
55
56pub(crate) enum Missing {
59 Disposed,
61 NoValue,
63 Gone,
65}
66
67impl Missing {
68 #[track_caller]
69 pub(crate) fn panic<T>(self, handle: &str) -> ! {
70 let ty = type_name::<T>();
71 match self {
72 Missing::Disposed => panic!(
73 "{handle}<{ty}> was used after its owner was disposed (try_get() returns None instead)"
74 ),
75 Missing::NoValue => panic!(
76 "{handle}<{ty}> has no value: its closure panicked before producing one and was disabled"
77 ),
78 Missing::Gone => panic!(
79 "{handle}<{ty}> was used after this thread's runtime was torn down (try_get() returns None instead)"
80 ),
81 }
82 }
83}
84
85struct BorrowConflict(String);
90
91struct Node {
92 kind: Kind,
93 owner: Option<NodeId>,
96 seq: u64,
98 name: Option<String>,
100 state: State,
101 disabled: bool,
104 compute: Option<Compute>,
107 children: Vec<NodeId>,
110 sources: Vec<NodeId>,
112 subscribers: Vec<NodeId>,
114}
115
116enum Kind {
117 Owner,
118 Signal {
120 value: Rc<dyn Any>,
121 },
122 Memo {
125 value: Rc<dyn Any>,
126 },
127 Effect {
130 queued: bool,
131 },
132}
133
134impl Kind {
135 fn name(&self) -> &'static str {
136 match self {
137 Kind::Owner => "owner",
138 Kind::Signal { .. } => "signal",
139 Kind::Memo { .. } => "memo",
140 Kind::Effect { .. } => "effect",
141 }
142 }
143}
144
145#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
147enum State {
148 Clean,
149 Check,
151 Dirty,
153}
154
155#[derive(Clone, Copy)]
157struct Running {
158 id: NodeId,
159 is_memo: bool,
160}
161
162#[derive(Default)]
163struct Graph {
164 nodes: SlotMap<NodeId, Node>,
165 queue: Vec<NodeId>,
167 observer: Option<NodeId>,
171 running: Option<Running>,
174 next_seq: u64,
175 flushing: bool,
176}
177
178impl Graph {
179 fn memo_running(&self) -> bool {
182 self.running.is_some_and(|running| running.is_memo)
183 }
184}
185
186impl Drop for Graph {
187 fn drop(&mut self) {
188 for (_, node) in self.nodes.drain() {
191 drop_isolated(node);
192 }
193 }
194}
195
196thread_local! {
197 static GRAPH: RefCell<Graph> = RefCell::new(Graph::default());
198}
199
200fn try_graph<R>(f: impl FnOnce(&mut Graph) -> R) -> Option<R> {
204 GRAPH
205 .try_with(|graph| {
206 let mut graph = graph
207 .try_borrow_mut()
208 .expect("invariant: the runtime is never borrowed while user code runs");
209 f(&mut graph)
210 })
211 .ok()
212}
213
214fn with_graph<R>(f: impl FnOnce(&mut Graph) -> R) -> R {
216 try_graph(f).expect("invariant: the runtime outlives every call that found it alive")
217}
218
219pub(crate) fn drop_isolated<T>(value: T) {
225 let caught = untrack(|| panic::catch_unwind(AssertUnwindSafe(move || drop(value))));
226 if let Err(payload) = caught {
227 tracing::error!(
228 "a Drop impl panicked while the runtime was dropping a value or closure: {}",
229 panic_message(payload.as_ref())
230 );
231 }
232}
233
234struct DropIsolated<T>(Option<T>);
237
238impl<T> Deref for DropIsolated<T> {
239 type Target = T;
240
241 fn deref(&self) -> &T {
242 self
243 .0
244 .as_ref()
245 .expect("invariant: a DropIsolated holds its value until it is dropped")
246 }
247}
248
249impl<T> Drop for DropIsolated<T> {
250 fn drop(&mut self) {
251 drop_isolated(self.0.take());
252 }
253}
254
255#[cfg(test)]
257pub(crate) fn is_unborrowed() -> bool {
258 GRAPH.with(|graph| graph.try_borrow_mut().is_ok())
259}
260
261#[cfg(test)]
263pub(crate) fn subscriber_count(id: NodeId) -> usize {
264 with_graph(|g| g.nodes.get(id).map_or(0, |node| node.subscribers.len()))
265}
266
267#[cfg(test)]
269pub(crate) fn slot_of(id: NodeId) -> (u32, u32) {
270 use slotmap::Key;
271 let ffi = id.data().as_ffi();
272 (ffi as u32, (ffi >> 32) as u32)
273}
274
275#[derive(Clone, Copy)]
281pub struct Runtime {
282 _not_send: PhantomData<*const ()>,
284}
285
286impl Runtime {
287 pub fn current() -> Runtime {
289 Runtime {
290 _not_send: PhantomData,
291 }
292 }
293
294 #[track_caller]
297 pub fn new_owner(&self) -> Owner {
298 Owner::new(None)
299 }
300
301 #[track_caller]
320 pub fn flush(&self) {
321 flush();
322 }
323
324 pub fn node_count(&self) -> usize {
328 try_graph(|g| g.nodes.len()).unwrap_or(0)
329 }
330}
331
332pub fn untrack<R>(f: impl FnOnce() -> R) -> R {
339 struct Restore(Option<NodeId>);
342
343 impl Drop for Restore {
344 fn drop(&mut self) {
345 let observer = self.0;
346 try_graph(|g| g.observer = observer);
347 }
348 }
349
350 let _restore = try_graph(|g| g.observer.take()).map(Restore);
351 f()
352}
353
354#[track_caller]
355pub(crate) fn create_owner(parent: Option<NodeId>) -> NodeId {
356 create(parent, Kind::Owner, None)
357}
358
359#[track_caller]
360pub(crate) fn create_signal(owner: NodeId, value: Rc<dyn Any>) -> NodeId {
361 create(Some(owner), Kind::Signal { value }, None)
362}
363
364#[track_caller]
365pub(crate) fn create_memo(owner: NodeId, value: Rc<dyn Any>, compute: Compute) -> NodeId {
366 create(Some(owner), Kind::Memo { value }, Some(compute))
367}
368
369#[track_caller]
372pub(crate) fn create_effect(owner: NodeId, compute: Compute) -> NodeId {
373 create(Some(owner), Kind::Effect { queued: true }, Some(compute))
374}
375
376#[track_caller]
381pub(crate) fn new_scope() -> NodeId {
382 let (effect, previous) = with_graph(|g| {
383 let effect = g
384 .running
385 .expect("invariant: new_scope() runs inside an effect")
386 .id;
387 let previous = g
388 .nodes
389 .get_mut(effect)
390 .map(|node| mem::take(&mut node.children))
391 .unwrap_or_default();
392 (effect, previous)
393 });
394 for scope in previous {
395 dispose(scope);
396 }
397 create_owner(Some(effect))
398}
399
400#[track_caller]
401fn create(owner: Option<NodeId>, kind: Kind, compute: Option<Compute>) -> NodeId {
402 let owner_alive = try_graph(|g| owner.is_none_or(|owner| g.nodes.contains_key(owner)));
403 if owner_alive != Some(true) {
404 let what = kind.name();
405 drop_isolated((kind, compute));
408 if owner_alive.is_none() {
409 panic!("tried to create a new {what} after this thread's runtime was torn down");
410 }
411 panic!("tried to create a new {what} under an owner that was already disposed");
412 }
413 with_graph(|g| {
414 let seq = g.next_seq;
415 g.next_seq += 1;
416 let is_effect = matches!(kind, Kind::Effect { .. });
417 let state = if compute.is_some() {
419 State::Dirty
420 } else {
421 State::Clean
422 };
423 let id = g.nodes.insert(Node {
424 kind,
425 owner,
426 seq,
427 name: None,
428 state,
429 disabled: false,
430 compute,
431 children: Vec::new(),
432 sources: Vec::new(),
433 subscribers: Vec::new(),
434 });
435 if let Some(owner) = owner
436 && let Some(parent) = g.nodes.get_mut(owner)
437 {
438 parent.children.push(id);
439 }
440 if is_effect {
441 g.queue.push(id);
442 }
443 id
444 })
445}
446
447pub(crate) fn set_name(id: NodeId, name: String) {
448 try_graph(|g| {
449 if let Some(node) = g.nodes.get_mut(id) {
450 node.name = Some(name);
451 }
452 });
453}
454
455pub(crate) fn is_disposed(id: NodeId) -> bool {
457 try_graph(|g| !g.nodes.contains_key(id)).unwrap_or(true)
458}
459
460#[track_caller]
464pub(crate) fn read<T: 'static, R>(
465 id: NodeId,
466 track: bool,
467 handle: &str,
468 f: impl FnOnce(&T) -> R,
469) -> Result<R, Missing> {
470 let found = try_graph(|g| {
471 let node = g.nodes.get(id)?;
472 match &node.kind {
473 Kind::Signal { value } => Some((Rc::clone(value), false, false)),
474 Kind::Memo { value } => Some((
477 Rc::clone(value),
478 true,
479 node.compute.is_none() && !node.disabled,
480 )),
481 Kind::Owner | Kind::Effect { .. } => None,
482 }
483 });
484 let Some(found) = found else {
485 return Err(Missing::Gone);
486 };
487 let Some((value, is_memo, computing)) = found else {
488 return Err(Missing::Disposed);
489 };
490 if computing {
491 drop_isolated(f);
492 panic!(
493 "{handle}<{}> was read while computing its own value (a dependency cycle)",
494 type_name::<T>()
495 );
496 }
497 if is_memo {
498 refresh(id);
499 }
500 if track {
504 with_graph(|g| subscribe(g, id));
505 }
506 let value = DropIsolated(Some(downcast::<T>(value)));
508 let Ok(slot) = value.try_borrow() else {
509 drop_isolated(f);
510 borrow_conflict(format!(
511 "{handle}<{}> was read inside its own update() (at {})",
512 type_name::<T>(),
513 Location::caller()
514 ));
515 };
516 match slot.as_ref() {
517 Some(current) => Ok(f(current)),
518 None => Err(Missing::NoValue),
519 }
520}
521
522#[track_caller]
523pub(crate) fn read_or_panic<T: 'static, R>(
524 id: NodeId,
525 track: bool,
526 handle: &str,
527 f: impl FnOnce(&T) -> R,
528) -> R {
529 match read(id, track, handle, f) {
530 Ok(result) => result,
531 Err(missing) => missing.panic::<T>(handle),
532 }
533}
534
535#[track_caller]
540pub(crate) fn borrow_conflict(message: String) -> ! {
541 if with_graph(|g| g.memo_running()) {
542 panic::resume_unwind(Box::new(BorrowConflict(message)));
543 }
544 panic!("{message}");
545}
546
547#[track_caller]
557pub(crate) fn write<T: 'static, R>(
558 id: NodeId,
559 f: impl FnOnce(&mut Option<T>) -> R,
560) -> Result<R, Missing> {
561 let found = try_graph(|g| {
562 let value = match g.nodes.get(id).map(|node| &node.kind) {
563 Some(Kind::Signal { value }) => Some(Rc::clone(value)),
564 _ => None,
565 };
566 (value, g.memo_running())
567 });
568 let (value, memo_running) = match found {
570 Some((Some(value), memo_running)) => (value, memo_running),
571 Some((None, _)) => {
572 drop_isolated(f);
573 return Err(Missing::Disposed);
574 }
575 None => {
576 drop_isolated(f);
577 return Err(Missing::Gone);
578 }
579 };
580 if memo_running {
581 drop_isolated(f);
582 panic!(
583 "Signal<{}> was written inside a memo: memos must not write signals; use an effect",
584 type_name::<T>()
585 );
586 }
587 let value = DropIsolated(Some(downcast::<T>(value)));
589 let outcome = {
590 let Ok(mut slot) = value.try_borrow_mut() else {
591 drop_isolated(f);
592 panic!(
593 "Signal<{}> was written while a with() call on it was still running",
594 type_name::<T>()
595 );
596 };
597 panic::catch_unwind(AssertUnwindSafe(|| f(&mut slot)))
598 };
599 with_graph(|g| mark_subscribers(g, id, State::Dirty));
601 match outcome {
602 Ok(result) => Ok(result),
603 Err(payload) => panic::resume_unwind(payload),
604 }
605}
606
607#[track_caller]
610pub(crate) fn write_or_panic<T: 'static, R>(
611 id: NodeId,
612 f: impl FnOnce(&mut Option<T>) -> R,
613) -> Option<R> {
614 match write(id, f) {
615 Ok(result) => Some(result),
616 Err(Missing::Gone) => None,
617 Err(missing) => missing.panic::<T>("Signal"),
618 }
619}
620
621fn downcast<T: 'static>(value: Rc<dyn Any>) -> Rc<RefCell<Option<T>>> {
622 value
623 .downcast()
624 .expect("invariant: a handle's type matches its node's value type")
625}
626
627pub(crate) fn dispose(owner: NodeId) {
631 let Some(removed) = try_graph(|g| {
633 if let Some(parent) = g.nodes.get(owner).and_then(|node| node.owner)
634 && let Some(parent) = g.nodes.get_mut(parent)
635 {
636 parent.children.retain(|&child| child != owner);
637 }
638 let mut removed = Vec::new();
639 let mut stack = vec![owner];
640 while let Some(id) = stack.pop() {
641 let Some(node) = g.nodes.remove(id) else {
642 continue;
643 };
644 stack.extend_from_slice(&node.children);
645 unsubscribe_all(g, id, &node.sources);
646 removed.push(node);
647 }
648 removed
649 }) else {
650 return;
651 };
652 for node in removed {
653 drop_isolated(node);
654 }
655}
656
657#[track_caller]
658fn flush() {
659 let started = try_graph(|g| (!g.memo_running()).then(|| !mem::replace(&mut g.flushing, true)));
661 match started {
662 Some(Some(true)) => {}
663 Some(None) => {
664 panic!("Runtime::flush() was called inside a memo: memos must not run effects")
665 }
666 None | Some(Some(false)) => return,
669 }
670 let mut runs: HashMap<NodeId, u32> = HashMap::new();
671 loop {
672 let round = with_graph(|g| {
673 let mut round = mem::take(&mut g.queue);
674 round.sort_by_key(|&id| g.nodes.get(id).map_or(0, |node| node.seq));
675 round
676 });
677 if round.is_empty() {
678 break;
679 }
680 let mut round = round.into_iter();
681 while let Some(id) = round.next() {
682 let runnable = with_graph(|g| match g.nodes.get_mut(id) {
684 Some(Node {
685 kind: Kind::Effect { queued },
686 disabled,
687 ..
688 }) => {
689 *queued = false;
690 !*disabled
691 }
692 _ => false,
693 });
694 if !runnable {
695 continue;
696 }
697 let count = runs.entry(id).or_insert(0);
698 if *count >= MAX_RUNS_PER_FLUSH {
699 let what = with_graph(|g| describe(g, id));
700 tracing::error!(
701 "{what} is in a dependency cycle: it ran {MAX_RUNS_PER_FLUSH} times in one \
702 flush and was queued again, so it is disabled"
703 );
704 disable(id);
705 continue;
706 }
707 match panic::catch_unwind(AssertUnwindSafe(|| refresh(id))) {
708 Ok(ran) => *count += u32::from(ran),
709 Err(payload) => {
710 with_graph(|g| {
715 if let Some(Node {
716 kind: Kind::Effect { queued },
717 ..
718 }) = g.nodes.get_mut(id)
719 && !*queued
720 {
721 *queued = true;
722 g.queue.push(id);
723 }
724 g.queue.extend(round);
726 g.flushing = false;
727 });
728 panic::resume_unwind(payload);
729 }
730 }
731 }
732 }
733 with_graph(|g| g.flushing = false);
734}
735
736fn refresh(id: NodeId) -> bool {
740 let sources = with_graph(|g| match g.nodes.get(id) {
741 Some(node) if !node.disabled && node.state == State::Check => node.sources.clone(),
742 _ => Vec::new(),
743 });
744 for source in sources {
748 refresh(source);
749 if with_graph(|g| g.nodes.get(id).map(|node| node.state)) != Some(State::Check) {
750 break;
751 }
752 }
753 let dirty = with_graph(|g| match g.nodes.get_mut(id) {
754 Some(node) if !node.disabled => {
755 if node.state == State::Check {
756 node.state = State::Clean;
757 }
758 node.state == State::Dirty
759 }
760 _ => false,
761 });
762 dirty && run(id)
763}
764
765fn run(id: NodeId) -> bool {
770 let taken = with_graph(|g| {
771 let node = g.nodes.get_mut(id)?;
772 let compute = node.compute.take()?;
773 let is_memo = matches!(node.kind, Kind::Memo { .. });
774 node.state = State::Clean;
777 let sources = mem::take(&mut node.sources);
779 unsubscribe_all(g, id, &sources);
780 Some((compute, is_memo))
781 });
782 let Some((mut compute, is_memo)) = taken else {
783 return false;
784 };
785
786 let outer = with_graph(|g| {
787 (
788 g.observer.replace(id),
789 g.running.replace(Running { id, is_memo }),
790 )
791 });
792 let result = panic::catch_unwind(AssertUnwindSafe(&mut compute));
796 with_graph(|g| (g.observer, g.running) = outer);
797
798 let payload = match result {
799 Ok(Computed { changed, leftover }) => {
800 let orphan = put_back(id, compute, |g| {
801 if changed {
802 mark_subscribers(g, id, State::Dirty);
803 }
804 });
805 drop_isolated(leftover);
808 drop_isolated(orphan);
809 return changed;
810 }
811 Err(payload) => payload,
812 };
813 match payload.downcast::<BorrowConflict>() {
814 Ok(conflict) => {
815 let orphan = put_back(id, compute, |g| {
820 if let Some(node) = g.nodes.get_mut(id) {
821 node.state = State::Dirty;
822 }
823 });
824 drop_isolated(orphan);
825 if with_graph(|g| g.memo_running()) {
826 panic::resume_unwind(conflict);
827 }
828 panic!("{}", conflict.0);
829 }
830 Err(payload) => {
831 let what = with_graph(|g| describe(g, id));
832 tracing::error!(
833 "{what} panicked and is disabled: {}",
834 panic_message(payload.as_ref())
835 );
836 disable(id);
839 drop_isolated(compute);
840 drop_isolated(payload);
841 false
842 }
843 }
844}
845
846fn put_back(id: NodeId, compute: Compute, then: impl FnOnce(&mut Graph)) -> Option<Compute> {
850 with_graph(|g| {
851 let Some(node) = g.nodes.get_mut(id) else {
852 return Some(compute);
853 };
854 node.compute = Some(compute);
855 then(g);
856 None
857 })
858}
859
860fn disable(id: NodeId) {
863 let Some((compute, scopes)) = with_graph(|g| {
864 let node = g.nodes.get_mut(id)?;
865 node.disabled = true;
866 let sources = mem::take(&mut node.sources);
867 let compute = node.compute.take();
868 let scopes = mem::take(&mut node.children);
869 unsubscribe_all(g, id, &sources);
870 Some((compute, scopes))
871 }) else {
872 return;
873 };
874 drop_isolated(compute);
875 for scope in scopes {
876 dispose(scope);
877 }
878}
879
880fn mark_subscribers(g: &mut Graph, id: NodeId, state: State) {
883 let Some(node) = g.nodes.get(id) else {
884 return;
885 };
886 let mut stack: Vec<(NodeId, State)> = node.subscribers.iter().map(|&s| (s, state)).collect();
887 while let Some((id, state)) = stack.pop() {
888 let Some(node) = g.nodes.get_mut(id) else {
889 continue;
890 };
891 if node.disabled || node.state >= state {
892 continue;
893 }
894 let was_clean = node.state == State::Clean;
896 node.state = state;
897 match &mut node.kind {
898 Kind::Effect { queued } if !*queued => {
899 *queued = true;
900 g.queue.push(id);
901 }
902 Kind::Memo { .. } if was_clean => {
903 stack.extend(node.subscribers.iter().map(|&s| (s, State::Check)));
904 }
905 _ => {}
906 }
907 }
908}
909
910fn subscribe(g: &mut Graph, source: NodeId) {
912 let Some(observer) = g.observer else {
913 return;
914 };
915 if observer == source || !g.nodes.contains_key(source) {
916 return;
917 }
918 let Some(node) = g.nodes.get_mut(observer) else {
920 return;
921 };
922 if node.sources.contains(&source) {
923 return;
924 }
925 node.sources.push(source);
926 if let Some(source) = g.nodes.get_mut(source) {
927 source.subscribers.push(observer);
928 }
929}
930
931fn unsubscribe_all(g: &mut Graph, id: NodeId, sources: &[NodeId]) {
933 for &source in sources {
934 if let Some(source) = g.nodes.get_mut(source) {
935 source.subscribers.retain(|&s| s != id);
936 }
937 }
938}
939
940fn describe(g: &Graph, id: NodeId) -> String {
944 let Some(node) = g.nodes.get(id) else {
945 return String::from("a disposed node");
946 };
947 let kind = node.kind.name();
948 if let Some(name) = &node.name {
949 return format!("{kind} {name}");
950 }
951 let mut parent = node.owner;
952 while let Some(ancestor) = parent.and_then(|parent| g.nodes.get(parent)) {
953 if let Some(name) = &ancestor.name {
954 return format!("unnamed {kind} #{} in {name}", node.seq);
955 }
956 parent = ancestor.owner;
957 }
958 format!("unnamed {kind} #{}", node.seq)
959}
960
961fn panic_message(payload: &(dyn Any + Send)) -> &str {
962 if let Some(message) = payload.downcast_ref::<&str>() {
963 message
964 } else if let Some(message) = payload.downcast_ref::<String>() {
965 message
966 } else if let Some(conflict) = payload.downcast_ref::<BorrowConflict>() {
967 &conflict.0
968 } else {
969 "(panic payload is not a string)"
970 }
971}