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/// Whether `id` is gone, or the runtime with it.
456pub(crate) fn is_disposed(id: NodeId) -> bool {
457  try_graph(|g| !g.nodes.contains_key(id)).unwrap_or(true)
458}
459
460/// Reads a signal's or memo's value. A stale memo is recomputed first. If
461/// `track` is true and a memo or effect is running, it starts depending on
462/// this node.
463#[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      // A memo whose closure is out of its node (and not because it was
475      // disabled) is computing right now.
476      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  // Subscribe only after the refresh. If the memo changed, it marked its
501  // subscribers dirty, and the reader, which is about to see the new
502  // value, shouldn't be one of them yet.
503  if track {
504    with_graph(|g| subscribe(g, id));
505  }
506  // If `f` disposes this node's owner, this is the value's last reference.
507  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/// Raises a borrow-conflict panic. Inside a memo it is a [`BorrowConflict`]
536/// for [`run`] to recognize, raised without the panic hook; `run` raises a
537/// readable panic once the conflict has left the memos. Anywhere else it is
538/// a plain panic.
539#[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/// Changes a signal's value through `f`, then marks its dependents stale and
548/// queues effects, even if `f` panics. Whatever `f` returns (such as the old
549/// value) is handed back for the caller to drop, outside every borrow.
550///
551/// # Panics
552///
553/// Inside a memo, because a memo that writes a signal it read would leave
554/// itself stale and its readers would miss every later change. Also passes
555/// on a panic from `f`, after marking.
556#[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  // `f` can hold the new value; it is dropped unused on every early exit.
569  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  // If `f` disposes this signal's owner, this is the value's last reference.
588  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  // Even if `f` panicked, it may have changed the value first.
600  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/// [`write`] for `set()` and `update()`: panics on a disposed signal, and
608/// returns `None` without writing once the runtime is gone.
609#[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
627/// Disposes an owner and everything created under it, child owners and
628/// effect scopes included. Their values and closures are dropped after the
629/// borrow ends.
630pub(crate) fn dispose(owner: NodeId) {
631  // If the runtime is gone, its nodes are already being dropped.
632  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  // `None` inside: a memo is running.
660  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    // The runtime is gone, or a flush further up the stack is already
667    // running and will pick up whatever gets queued.
668    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      // From here on, a new write queues the effect for the next round.
683      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          // Only a borrow conflict from a memo this effect reads
711          // gets here, when flush() runs inside with() or update().
712          // Leave this effect and the rest of the round queued, end
713          // the flush, and pass the panic on to flush()'s caller.
714          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            // These still have `queued` set.
725            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
736/// Brings a memo or effect up to date, running it if needed. Returns whether
737/// it ran (for a memo, whether its value changed). Signals and owners are
738/// always up to date.
739fn 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  // A memo this node read may have changed. Refresh those memos in order.
745  // One whose value changes marks this node dirty, and then there's no
746  // need to look further.
747  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
765/// Runs a memo's or effect's closure with no borrow held, recording what it
766/// reads. Returns whether it ran (for a memo, whether its value changed). A
767/// panic is caught, logged, and disables the node, except a memo's borrow
768/// conflict, which goes on to its reader.
769fn 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    // Clean before the run, so a write during the run that affects this
775    // node marks it dirty again.
776    node.state = State::Clean;
777    // Dependencies are recorded afresh on every run.
778    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  // `AssertUnwindSafe`: after a panic the closure is either dropped without
793  // being called again, or, after a borrow conflict, called again from the
794  // start with its value untouched.
795  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      // After the readers were told, so a panic in the old value's
806      // `Drop` can't hide the change.
807      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      // Not this memo's fault: leave it dirty, so the next read
816      // recomputes it, and pass the panic on to its reader. A memo
817      // reading this one handles it the same way; past the memos it
818      // becomes a readable panic.
819      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 first, so nothing the closure's values do while they
837      // drop can queue or run it again.
838      disable(id);
839      drop_isolated(compute);
840      drop_isolated(payload);
841      false
842    }
843  }
844}
845
846/// Puts a closure back into its node and then runs `then`. If the closure
847/// disposed its own owner, the node is gone: the closure is handed back to
848/// be dropped outside the borrow.
849fn 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
860/// Stops a memo or effect for good. A disabled memo keeps its last value. A
861/// scoped effect's last scope is disposed, everything in it included.
862fn 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
880/// Marks what read `id` as `state`, everything further downstream as
881/// `Check`, and queues the effects among them.
882fn 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    // A node that was already stale has marked its own subscribers.
895    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
910/// Makes the running memo or effect, if any, depend on `source`.
911fn 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  // The observer can be gone if its closure disposed its own owner.
919  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
931/// Removes `id` from the subscriber lists of everything in `sources`.
932fn 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
940/// How log lines name a node: its debug name if it has one, otherwise its
941/// creation number and the name of its nearest named ancestor. Scopes and
942/// rows are rarely named; the widget above them usually is.
943fn 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}