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