Skip to main content

crabshell_reactive/
runtime.rs

1//! The runtime: this thread's arena of nodes, the dependency edges between
2//! them, and `flush`.
3//!
4//! Every handle (`Signal`, `Memo`, `Effect`, `Owner`) is a [`NodeId`] into one
5//! arena that lives in a thread-local `RefCell`. Functions here borrow it for a
6//! few lines at a time and never while user code runs. A memo's or effect's
7//! closure is taken out of its node before it is called and put back after.
8//! User values and closures are dropped only after the borrow has ended, and
9//! through [`drop_isolated`], so a panicking `Drop` can't escape either, and
10//! nothing a `Drop` reads becomes a dependency. So user code can call back
11//! into the runtime freely, and a panic in user code can't leave the runtime
12//! borrowed or half-updated.
13//!
14//! When the thread exits, the arena is dropped with everything in it. User
15//! `Drop` code that calls back in then finds the runtime gone and is treated
16//! as touching a disposed handle: writes and disposes do nothing, and reads
17//! find no value.
18
19use 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
32/// How many times one effect may run in a single flush. An effect that is
33/// queued again after that is in a dependency cycle, so it is logged and
34/// disabled.
35pub const MAX_RUNS_PER_FLUSH: u32 = 100;
36
37new_key_type! {
38    /// The key of one node in the arena. A key also records the slot's
39    /// version, so once its node is removed it never matches a newer node
40    /// that reuses the slot.
41    pub(crate) struct NodeId;
42}
43
44/// What one run of a memo's or effect's closure produced.
45pub(crate) struct Computed {
46  /// Whether the value changed. Always true for an effect.
47  pub(crate) changed: bool,
48  /// A value the run replaced or didn't keep. The runtime drops it after
49  /// telling the readers, so a panic in its `Drop` can't stop that.
50  pub(crate) leftover: Option<Box<dyn Any>>,
51}
52
53/// A memo's or effect's closure with its types erased.
54pub(crate) type Compute = Box<dyn FnMut() -> Computed>;
55
56/// Why a read or write found no value. These can happen in correct code, so
57/// `try_get()` and `try_set()` report them instead of panicking.
58pub(crate) enum Missing {
59  /// The node's owner was disposed.
60  Disposed,
61  /// A memo whose closure panicked before producing its first value.
62  NoValue,
63  /// The thread is exiting and its runtime has been dropped.
64  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
85/// The panic payload of a borrow conflict inside a memo: the memo read a
86/// signal that is being updated further up the stack, or its own value is
87/// still borrowed by a `with()` further up. The memo is not at fault, so
88/// [`run`] puts it back unchanged and passes the panic on to its reader.
89struct BorrowConflict(String);
90
91struct Node {
92  kind: Kind,
93  /// The owner or effect this node was created under. `None` for a root
94  /// owner.
95  owner: Option<NodeId>,
96  /// Creation order. Effects in one flush round run in this order.
97  seq: u64,
98  /// Debug name, such as a widget path, used in log lines.
99  name: Option<String>,
100  state: State,
101  /// Set once the closure panicked or was caught in a cycle. A disabled
102  /// node never runs again.
103  disabled: bool,
104  /// The memo's or effect's closure. `None` for signals and owners, while
105  /// the closure is running, and once the node is disabled.
106  compute: Option<Compute>,
107  /// What was created under this node: everything an owner made, or the
108  /// scope an effect made with [`new_scope`] on its last run.
109  children: Vec<NodeId>,
110  /// The signals and memos this memo or effect read on its last run.
111  sources: Vec<NodeId>,
112  /// The memos and effects that read this signal or memo on their last run.
113  subscribers: Vec<NodeId>,
114}
115
116enum Kind {
117  Owner,
118  /// `value` is an `Rc<RefCell<Option<T>>>` that always holds `Some`.
119  Signal {
120    value: Rc<dyn Any>,
121  },
122  /// `value` is an `Rc<RefCell<Option<T>>>`, `None` until the first
123  /// computation succeeds.
124  Memo {
125    value: Rc<dyn Any>,
126  },
127  /// `queued` is true while the effect waits in the flush queue, so it is
128  /// never queued twice.
129  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/// How up to date a memo or effect is. Signals and owners stay `Clean`.
146#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
147enum State {
148  Clean,
149  /// A memo it read may have changed. Refreshing those memos tells.
150  Check,
151  /// Something it read has changed, so it must run again.
152  Dirty,
153}
154
155/// The memo or effect whose closure is running.
156#[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  /// Effects waiting for the next flush round.
166  queue: Vec<NodeId>,
167  /// The memo or effect that what is read now becomes a dependency of: the
168  /// one whose closure is running. `None` outside any run and inside
169  /// [`untrack`].
170  observer: Option<NodeId>,
171  /// The innermost memo or effect whose closure is running. Unlike
172  /// `observer`, [`untrack`] leaves it alone.
173  running: Option<Running>,
174  next_seq: u64,
175  flushing: bool,
176}
177
178impl Graph {
179  /// True while the innermost running closure is a memo's. Writing a
180  /// signal or flushing then panics.
181  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    // This runs when the thread exits. The runtime already counts as
189    // gone, so user `Drop` code that calls back in finds nothing to do.
190    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
200/// Runs `f` on this thread's runtime. Returns `None` if the runtime is gone
201/// because the thread is exiting. Every call from outside the runtime starts
202/// here.
203fn 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
214/// Like [`try_graph`], for the steps after a call has found the runtime alive.
215fn 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
219/// Drops a user value or closure that the runtime owned, with no borrow
220/// held. A panic in its `Drop` is caught and logged, so it can't escape
221/// halfway through a flush or a dispose and leave the runtime inconsistent.
222/// The drop is untracked, so what the `Drop` reads doesn't become a
223/// dependency of whichever memo or effect happens to be running.
224pub(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
234/// Holds a value and drops it through [`drop_isolated`] when it goes, even
235/// while a panic unwinds.
236struct 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/// True if nothing holds a borrow of this thread's runtime.
256#[cfg(test)]
257pub(crate) fn is_unborrowed() -> bool {
258  GRAPH.with(|graph| graph.try_borrow_mut().is_ok())
259}
260
261/// How many memos and effects read this node on their last run.
262#[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/// A key's slot index and version.
268#[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/// This thread's reactive runtime.
276///
277/// There is one per thread, created on first use. In the shell that is the
278/// main thread. A `Runtime` value is only a handle to it, so
279/// [`Runtime::current`] is cheap and every copy refers to the same runtime.
280#[derive(Clone, Copy)]
281pub struct Runtime {
282  /// Keeps the handle on its thread: `*const ()` is neither `Send` nor `Sync`.
283  _not_send: PhantomData<*const ()>,
284}
285
286impl Runtime {
287  /// Returns a handle to this thread's runtime.
288  pub fn current() -> Runtime {
289    Runtime {
290      _not_send: PhantomData,
291    }
292  }
293
294  /// Creates a root owner: one with no parent, freed only by its own
295  /// [`Owner::dispose`].
296  #[track_caller]
297  pub fn new_owner(&self) -> Owner {
298    Owner::new(None)
299  }
300
301  /// Runs every queued effect. The event loop calls this once per
302  /// iteration, before layout and painting.
303  ///
304  /// Each round runs the queued effects once each, in creation order, so an
305  /// effect reached through several paths (a diamond) still runs once.
306  /// Effects queued during a round, because an effect wrote a signal they
307  /// read or was just created, run in the next round of the same flush. An
308  /// effect that has run [`MAX_RUNS_PER_FLUSH`] times in this flush and is
309  /// queued again is in a cycle: it is logged with its debug name and
310  /// disabled, and the flush carries on with the other effects.
311  ///
312  /// Calling `flush` from inside an effect does nothing: the flush that is
313  /// already running picks up whatever got queued.
314  ///
315  /// # Panics
316  ///
317  /// Inside a memo, which must not run effects in the middle of its
318  /// computation.
319  #[track_caller]
320  pub fn flush(&self) {
321    flush();
322  }
323
324  /// The number of live nodes (owners, signals, memos and effects) on this
325  /// thread. Tests use it to check that disposing an owner frees
326  /// everything created under it.
327  pub fn node_count(&self) -> usize {
328    try_graph(|g| g.nodes.len()).unwrap_or(0)
329  }
330}
331
332/// Runs `f` without recording what it reads as dependencies of the running
333/// memo or effect, and returns `f`'s result. Recording resumes afterward,
334/// even if `f` panics.
335///
336/// Use it to read a value once without rerunning when it changes, such as
337/// the initial value a child widget is built with inside a parent's effect.
338pub fn untrack<R>(f: impl FnOnce() -> R) -> R {
339  /// Puts the observer back when dropped, which also happens while a panic
340  /// unwinds out of `f`.
341  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/// The new effect is queued straight away. It runs in the next flush round:
370/// later in the current flush if one is running, otherwise at the next flush.
371#[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/// Starts a fresh scope for the running effect, for
377/// [`Owner::effect_scoped`]: disposes the scope of its previous run and
378/// creates a new owner under the effect itself. So disposing or disabling
379/// the effect frees its last scope too.
380#[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    // `kind` and `compute` can hold user values. Drop them now, so a
406    // panicking `Drop` can't turn the panic below into an abort.
407    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    // Memos and effects start dirty: they haven't run yet.
418    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/// Reads a signal's or memo's value. A stale memo is recomputed first. If
456/// `track` is true and a memo or effect is running, it starts depending on
457/// this node.
458#[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      // A memo whose closure is out of its node (and not because it was
470      // disabled) is computing right now.
471      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  // Subscribe only after the refresh. If the memo changed, it marked its
496  // subscribers dirty, and the reader, which is about to see the new
497  // value, shouldn't be one of them yet.
498  if track {
499    with_graph(|g| subscribe(g, id));
500  }
501  // If `f` disposes this node's owner, this is the value's last reference.
502  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/// Raises a borrow-conflict panic. Inside a memo it is a [`BorrowConflict`]
531/// for [`run`] to recognize, raised without the panic hook; `run` raises a
532/// readable panic once the conflict has left the memos. Anywhere else it is
533/// a plain panic.
534#[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/// Changes a signal's value through `f`, then marks its dependents stale and
543/// queues effects, even if `f` panics. Whatever `f` returns (such as the old
544/// value) is handed back for the caller to drop, outside every borrow.
545///
546/// # Panics
547///
548/// Inside a memo, because a memo that writes a signal it read would leave
549/// itself stale and its readers would miss every later change. Also passes
550/// on a panic from `f`, after marking.
551#[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  // `f` can hold the new value; it is dropped unused on every early exit.
564  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  // If `f` disposes this signal's owner, this is the value's last reference.
583  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  // Even if `f` panicked, it may have changed the value first.
595  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/// [`write`] for `set()` and `update()`: panics on a disposed signal, and
603/// returns `None` without writing once the runtime is gone.
604#[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
622/// Disposes an owner and everything created under it, child owners and
623/// effect scopes included. Their values and closures are dropped after the
624/// borrow ends.
625pub(crate) fn dispose(owner: NodeId) {
626  // If the runtime is gone, its nodes are already being dropped.
627  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  // `None` inside: a memo is running.
655  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    // The runtime is gone, or a flush further up the stack is already
662    // running and will pick up whatever gets queued.
663    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      // From here on, a new write queues the effect for the next round.
678      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          // Only a borrow conflict from a memo this effect reads
706          // gets here, when flush() runs inside with() or update().
707          // Leave this effect and the rest of the round queued, end
708          // the flush, and pass the panic on to flush()'s caller.
709          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            // These still have `queued` set.
720            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
731/// Brings a memo or effect up to date, running it if needed. Returns whether
732/// it ran (for a memo, whether its value changed). Signals and owners are
733/// always up to date.
734fn 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  // A memo this node read may have changed. Refresh those memos in order.
740  // One whose value changes marks this node dirty, and then there's no
741  // need to look further.
742  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
760/// Runs a memo's or effect's closure with no borrow held, recording what it
761/// reads. Returns whether it ran (for a memo, whether its value changed). A
762/// panic is caught, logged, and disables the node, except a memo's borrow
763/// conflict, which goes on to its reader.
764fn 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    // Clean before the run, so a write during the run that affects this
770    // node marks it dirty again.
771    node.state = State::Clean;
772    // Dependencies are recorded afresh on every run.
773    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  // `AssertUnwindSafe`: after a panic the closure is either dropped without
788  // being called again, or, after a borrow conflict, called again from the
789  // start with its value untouched.
790  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      // After the readers were told, so a panic in the old value's
801      // `Drop` can't hide the change.
802      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      // Not this memo's fault: leave it dirty, so the next read
811      // recomputes it, and pass the panic on to its reader. A memo
812      // reading this one handles it the same way; past the memos it
813      // becomes a readable panic.
814      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 first, so nothing the closure's values do while they
832      // drop can queue or run it again.
833      disable(id);
834      drop_isolated(compute);
835      drop_isolated(payload);
836      false
837    }
838  }
839}
840
841/// Puts a closure back into its node and then runs `then`. If the closure
842/// disposed its own owner, the node is gone: the closure is handed back to
843/// be dropped outside the borrow.
844fn 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
855/// Stops a memo or effect for good. A disabled memo keeps its last value. A
856/// scoped effect's last scope is disposed, everything in it included.
857fn 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
875/// Marks what read `id` as `state`, everything further downstream as
876/// `Check`, and queues the effects among them.
877fn 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    // A node that was already stale has marked its own subscribers.
890    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
905/// Makes the running memo or effect, if any, depend on `source`.
906fn 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  // The observer can be gone if its closure disposed its own owner.
914  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
926/// Removes `id` from the subscriber lists of everything in `sources`.
927fn 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
935/// How log lines name a node: its debug name if it has one, otherwise its
936/// creation number and the name of its nearest named ancestor. Scopes and
937/// rows are rarely named; the widget above them usually is.
938fn 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}