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 nearest_name(id: NodeId) -> Option<String> {
457 try_graph(|g| {
458 let mut at = Some(id);
459 while let Some(node) = at.and_then(|id| g.nodes.get(id)) {
460 if let Some(name) = &node.name {
461 return Some(name.clone());
462 }
463 at = node.owner;
464 }
465 None
466 })
467 .flatten()
468}
469
470pub(crate) fn is_disposed(id: NodeId) -> bool {
472 try_graph(|g| !g.nodes.contains_key(id)).unwrap_or(true)
473}
474
475#[track_caller]
479pub(crate) fn read<T: 'static, R>(
480 id: NodeId,
481 track: bool,
482 handle: &str,
483 f: impl FnOnce(&T) -> R,
484) -> Result<R, Missing> {
485 let found = try_graph(|g| {
486 let node = g.nodes.get(id)?;
487 match &node.kind {
488 Kind::Signal { value } => Some((Rc::clone(value), false, false)),
489 Kind::Memo { value } => Some((
492 Rc::clone(value),
493 true,
494 node.compute.is_none() && !node.disabled,
495 )),
496 Kind::Owner | Kind::Effect { .. } => None,
497 }
498 });
499 let Some(found) = found else {
500 return Err(Missing::Gone);
501 };
502 let Some((value, is_memo, computing)) = found else {
503 return Err(Missing::Disposed);
504 };
505 if computing {
506 drop_isolated(f);
507 panic!(
508 "{handle}<{}> was read while computing its own value (a dependency cycle)",
509 type_name::<T>()
510 );
511 }
512 if is_memo {
513 refresh(id);
514 }
515 if track {
519 with_graph(|g| subscribe(g, id));
520 }
521 let value = DropIsolated(Some(downcast::<T>(value)));
523 let Ok(slot) = value.try_borrow() else {
524 drop_isolated(f);
525 borrow_conflict(format!(
526 "{handle}<{}> was read inside its own update() (at {})",
527 type_name::<T>(),
528 Location::caller()
529 ));
530 };
531 match slot.as_ref() {
532 Some(current) => Ok(f(current)),
533 None => Err(Missing::NoValue),
534 }
535}
536
537#[track_caller]
538pub(crate) fn read_or_panic<T: 'static, R>(
539 id: NodeId,
540 track: bool,
541 handle: &str,
542 f: impl FnOnce(&T) -> R,
543) -> R {
544 match read(id, track, handle, f) {
545 Ok(result) => result,
546 Err(missing) => missing.panic::<T>(handle),
547 }
548}
549
550#[track_caller]
555pub(crate) fn borrow_conflict(message: String) -> ! {
556 if with_graph(|g| g.memo_running()) {
557 panic::resume_unwind(Box::new(BorrowConflict(message)));
558 }
559 panic!("{message}");
560}
561
562#[track_caller]
572pub(crate) fn write<T: 'static, R>(
573 id: NodeId,
574 f: impl FnOnce(&mut Option<T>) -> R,
575) -> Result<R, Missing> {
576 let found = try_graph(|g| {
577 let value = match g.nodes.get(id).map(|node| &node.kind) {
578 Some(Kind::Signal { value }) => Some(Rc::clone(value)),
579 _ => None,
580 };
581 (value, g.memo_running())
582 });
583 let (value, memo_running) = match found {
585 Some((Some(value), memo_running)) => (value, memo_running),
586 Some((None, _)) => {
587 drop_isolated(f);
588 return Err(Missing::Disposed);
589 }
590 None => {
591 drop_isolated(f);
592 return Err(Missing::Gone);
593 }
594 };
595 if memo_running {
596 drop_isolated(f);
597 panic!(
598 "Signal<{}> was written inside a memo: memos must not write signals; use an effect",
599 type_name::<T>()
600 );
601 }
602 let value = DropIsolated(Some(downcast::<T>(value)));
604 let outcome = {
605 let Ok(mut slot) = value.try_borrow_mut() else {
606 drop_isolated(f);
607 panic!(
608 "Signal<{}> was written while a with() call on it was still running",
609 type_name::<T>()
610 );
611 };
612 panic::catch_unwind(AssertUnwindSafe(|| f(&mut slot)))
613 };
614 with_graph(|g| mark_subscribers(g, id, State::Dirty));
616 match outcome {
617 Ok(result) => Ok(result),
618 Err(payload) => panic::resume_unwind(payload),
619 }
620}
621
622#[track_caller]
625pub(crate) fn write_or_panic<T: 'static, R>(
626 id: NodeId,
627 f: impl FnOnce(&mut Option<T>) -> R,
628) -> Option<R> {
629 match write(id, f) {
630 Ok(result) => Some(result),
631 Err(Missing::Gone) => None,
632 Err(missing) => missing.panic::<T>("Signal"),
633 }
634}
635
636fn downcast<T: 'static>(value: Rc<dyn Any>) -> Rc<RefCell<Option<T>>> {
637 value
638 .downcast()
639 .expect("invariant: a handle's type matches its node's value type")
640}
641
642pub(crate) fn dispose(owner: NodeId) {
646 let Some(removed) = try_graph(|g| {
648 if let Some(parent) = g.nodes.get(owner).and_then(|node| node.owner)
649 && let Some(parent) = g.nodes.get_mut(parent)
650 {
651 parent.children.retain(|&child| child != owner);
652 }
653 let mut removed = Vec::new();
654 let mut stack = vec![owner];
655 while let Some(id) = stack.pop() {
656 let Some(node) = g.nodes.remove(id) else {
657 continue;
658 };
659 stack.extend_from_slice(&node.children);
660 unsubscribe_all(g, id, &node.sources);
661 removed.push(node);
662 }
663 removed
664 }) else {
665 return;
666 };
667 for node in removed {
668 drop_isolated(node);
669 }
670}
671
672#[track_caller]
673fn flush() {
674 let started = try_graph(|g| (!g.memo_running()).then(|| !mem::replace(&mut g.flushing, true)));
676 match started {
677 Some(Some(true)) => {}
678 Some(None) => {
679 panic!("Runtime::flush() was called inside a memo: memos must not run effects")
680 }
681 None | Some(Some(false)) => return,
684 }
685 let mut runs: HashMap<NodeId, u32> = HashMap::new();
686 loop {
687 let round = with_graph(|g| {
688 let mut round = mem::take(&mut g.queue);
689 round.sort_by_key(|&id| g.nodes.get(id).map_or(0, |node| node.seq));
690 round
691 });
692 if round.is_empty() {
693 break;
694 }
695 let mut round = round.into_iter();
696 while let Some(id) = round.next() {
697 let runnable = with_graph(|g| match g.nodes.get_mut(id) {
699 Some(Node {
700 kind: Kind::Effect { queued },
701 disabled,
702 ..
703 }) => {
704 *queued = false;
705 !*disabled
706 }
707 _ => false,
708 });
709 if !runnable {
710 continue;
711 }
712 let count = runs.entry(id).or_insert(0);
713 if *count >= MAX_RUNS_PER_FLUSH {
714 let what = with_graph(|g| describe(g, id));
715 tracing::error!(
716 "{what} is in a dependency cycle: it ran {MAX_RUNS_PER_FLUSH} times in one \
717 flush and was queued again, so it is disabled"
718 );
719 disable(id);
720 continue;
721 }
722 match panic::catch_unwind(AssertUnwindSafe(|| refresh(id))) {
723 Ok(ran) => *count += u32::from(ran),
724 Err(payload) => {
725 with_graph(|g| {
730 if let Some(Node {
731 kind: Kind::Effect { queued },
732 ..
733 }) = g.nodes.get_mut(id)
734 && !*queued
735 {
736 *queued = true;
737 g.queue.push(id);
738 }
739 g.queue.extend(round);
741 g.flushing = false;
742 });
743 panic::resume_unwind(payload);
744 }
745 }
746 }
747 }
748 with_graph(|g| g.flushing = false);
749}
750
751fn refresh(id: NodeId) -> bool {
755 let sources = with_graph(|g| match g.nodes.get(id) {
756 Some(node) if !node.disabled && node.state == State::Check => node.sources.clone(),
757 _ => Vec::new(),
758 });
759 for source in sources {
763 refresh(source);
764 if with_graph(|g| g.nodes.get(id).map(|node| node.state)) != Some(State::Check) {
765 break;
766 }
767 }
768 let dirty = with_graph(|g| match g.nodes.get_mut(id) {
769 Some(node) if !node.disabled => {
770 if node.state == State::Check {
771 node.state = State::Clean;
772 }
773 node.state == State::Dirty
774 }
775 _ => false,
776 });
777 dirty && run(id)
778}
779
780fn run(id: NodeId) -> bool {
785 let taken = with_graph(|g| {
786 let node = g.nodes.get_mut(id)?;
787 let compute = node.compute.take()?;
788 let is_memo = matches!(node.kind, Kind::Memo { .. });
789 node.state = State::Clean;
792 let sources = mem::take(&mut node.sources);
794 unsubscribe_all(g, id, &sources);
795 Some((compute, is_memo))
796 });
797 let Some((mut compute, is_memo)) = taken else {
798 return false;
799 };
800
801 let outer = with_graph(|g| {
802 (
803 g.observer.replace(id),
804 g.running.replace(Running { id, is_memo }),
805 )
806 });
807 let result = panic::catch_unwind(AssertUnwindSafe(&mut compute));
811 with_graph(|g| (g.observer, g.running) = outer);
812
813 let payload = match result {
814 Ok(Computed { changed, leftover }) => {
815 let orphan = put_back(id, compute, |g| {
816 if changed {
817 mark_subscribers(g, id, State::Dirty);
818 }
819 });
820 drop_isolated(leftover);
823 drop_isolated(orphan);
824 return changed;
825 }
826 Err(payload) => payload,
827 };
828 match payload.downcast::<BorrowConflict>() {
829 Ok(conflict) => {
830 let orphan = put_back(id, compute, |g| {
835 if let Some(node) = g.nodes.get_mut(id) {
836 node.state = State::Dirty;
837 }
838 });
839 drop_isolated(orphan);
840 if with_graph(|g| g.memo_running()) {
841 panic::resume_unwind(conflict);
842 }
843 panic!("{}", conflict.0);
844 }
845 Err(payload) => {
846 let what = with_graph(|g| describe(g, id));
847 tracing::error!(
848 "{what} panicked and is disabled: {}",
849 panic_message(payload.as_ref())
850 );
851 disable(id);
854 drop_isolated(compute);
855 drop_isolated(payload);
856 false
857 }
858 }
859}
860
861fn put_back(id: NodeId, compute: Compute, then: impl FnOnce(&mut Graph)) -> Option<Compute> {
865 with_graph(|g| {
866 let Some(node) = g.nodes.get_mut(id) else {
867 return Some(compute);
868 };
869 node.compute = Some(compute);
870 then(g);
871 None
872 })
873}
874
875fn disable(id: NodeId) {
878 let Some((compute, scopes)) = with_graph(|g| {
879 let node = g.nodes.get_mut(id)?;
880 node.disabled = true;
881 let sources = mem::take(&mut node.sources);
882 let compute = node.compute.take();
883 let scopes = mem::take(&mut node.children);
884 unsubscribe_all(g, id, &sources);
885 Some((compute, scopes))
886 }) else {
887 return;
888 };
889 drop_isolated(compute);
890 for scope in scopes {
891 dispose(scope);
892 }
893}
894
895fn mark_subscribers(g: &mut Graph, id: NodeId, state: State) {
898 let Some(node) = g.nodes.get(id) else {
899 return;
900 };
901 let mut stack: Vec<(NodeId, State)> = node.subscribers.iter().map(|&s| (s, state)).collect();
902 while let Some((id, state)) = stack.pop() {
903 let Some(node) = g.nodes.get_mut(id) else {
904 continue;
905 };
906 if node.disabled || node.state >= state {
907 continue;
908 }
909 let was_clean = node.state == State::Clean;
911 node.state = state;
912 match &mut node.kind {
913 Kind::Effect { queued } if !*queued => {
914 *queued = true;
915 g.queue.push(id);
916 }
917 Kind::Memo { .. } if was_clean => {
918 stack.extend(node.subscribers.iter().map(|&s| (s, State::Check)));
919 }
920 _ => {}
921 }
922 }
923}
924
925fn subscribe(g: &mut Graph, source: NodeId) {
927 let Some(observer) = g.observer else {
928 return;
929 };
930 if observer == source || !g.nodes.contains_key(source) {
931 return;
932 }
933 let Some(node) = g.nodes.get_mut(observer) else {
935 return;
936 };
937 if node.sources.contains(&source) {
938 return;
939 }
940 node.sources.push(source);
941 if let Some(source) = g.nodes.get_mut(source) {
942 source.subscribers.push(observer);
943 }
944}
945
946fn unsubscribe_all(g: &mut Graph, id: NodeId, sources: &[NodeId]) {
948 for &source in sources {
949 if let Some(source) = g.nodes.get_mut(source) {
950 source.subscribers.retain(|&s| s != id);
951 }
952 }
953}
954
955fn describe(g: &Graph, id: NodeId) -> String {
959 let Some(node) = g.nodes.get(id) else {
960 return String::from("a disposed node");
961 };
962 let kind = node.kind.name();
963 if let Some(name) = &node.name {
964 return format!("{kind} {name}");
965 }
966 let mut parent = node.owner;
967 while let Some(ancestor) = parent.and_then(|parent| g.nodes.get(parent)) {
968 if let Some(name) = &ancestor.name {
969 return format!("unnamed {kind} #{} in {name}", node.seq);
970 }
971 parent = ancestor.owner;
972 }
973 format!("unnamed {kind} #{}", node.seq)
974}
975
976fn panic_message(payload: &(dyn Any + Send)) -> &str {
977 if let Some(message) = payload.downcast_ref::<&str>() {
978 message
979 } else if let Some(message) = payload.downcast_ref::<String>() {
980 message
981 } else if let Some(conflict) = payload.downcast_ref::<BorrowConflict>() {
982 &conflict.0
983 } else {
984 "(panic payload is not a string)"
985 }
986}