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/// The debug name of `id` or of its nearest named ancestor.
456pub(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
470/// Whether `id` is gone, or the runtime with it.
471pub(crate) fn is_disposed(id: NodeId) -> bool {
472  try_graph(|g| !g.nodes.contains_key(id)).unwrap_or(true)
473}
474
475/// Reads a signal's or memo's value. A stale memo is recomputed first. If
476/// `track` is true and a memo or effect is running, it starts depending on
477/// this node.
478#[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      // A memo whose closure is out of its node (and not because it was
490      // disabled) is computing right now.
491      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  // Subscribe only after the refresh. If the memo changed, it marked its
516  // subscribers dirty, and the reader, which is about to see the new
517  // value, shouldn't be one of them yet.
518  if track {
519    with_graph(|g| subscribe(g, id));
520  }
521  // If `f` disposes this node's owner, this is the value's last reference.
522  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/// Raises a borrow-conflict panic. Inside a memo it is a [`BorrowConflict`]
551/// for [`run`] to recognize, raised without the panic hook; `run` raises a
552/// readable panic once the conflict has left the memos. Anywhere else it is
553/// a plain panic.
554#[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/// Changes a signal's value through `f`, then marks its dependents stale and
563/// queues effects, even if `f` panics. Whatever `f` returns (such as the old
564/// value) is handed back for the caller to drop, outside every borrow.
565///
566/// # Panics
567///
568/// Inside a memo, because a memo that writes a signal it read would leave
569/// itself stale and its readers would miss every later change. Also passes
570/// on a panic from `f`, after marking.
571#[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  // `f` can hold the new value; it is dropped unused on every early exit.
584  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  // If `f` disposes this signal's owner, this is the value's last reference.
603  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  // Even if `f` panicked, it may have changed the value first.
615  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/// [`write`] for `set()` and `update()`: panics on a disposed signal, and
623/// returns `None` without writing once the runtime is gone.
624#[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
642/// Disposes an owner and everything created under it, child owners and
643/// effect scopes included. Their values and closures are dropped after the
644/// borrow ends.
645pub(crate) fn dispose(owner: NodeId) {
646  // If the runtime is gone, its nodes are already being dropped.
647  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  // `None` inside: a memo is running.
675  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    // The runtime is gone, or a flush further up the stack is already
682    // running and will pick up whatever gets queued.
683    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      // From here on, a new write queues the effect for the next round.
698      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          // Only a borrow conflict from a memo this effect reads
726          // gets here, when flush() runs inside with() or update().
727          // Leave this effect and the rest of the round queued, end
728          // the flush, and pass the panic on to flush()'s caller.
729          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            // These still have `queued` set.
740            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
751/// Brings a memo or effect up to date, running it if needed. Returns whether
752/// it ran (for a memo, whether its value changed). Signals and owners are
753/// always up to date.
754fn 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  // A memo this node read may have changed. Refresh those memos in order.
760  // One whose value changes marks this node dirty, and then there's no
761  // need to look further.
762  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
780/// Runs a memo's or effect's closure with no borrow held, recording what it
781/// reads. Returns whether it ran (for a memo, whether its value changed). A
782/// panic is caught, logged, and disables the node, except a memo's borrow
783/// conflict, which goes on to its reader.
784fn 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    // Clean before the run, so a write during the run that affects this
790    // node marks it dirty again.
791    node.state = State::Clean;
792    // Dependencies are recorded afresh on every run.
793    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  // `AssertUnwindSafe`: after a panic the closure is either dropped without
808  // being called again, or, after a borrow conflict, called again from the
809  // start with its value untouched.
810  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      // After the readers were told, so a panic in the old value's
821      // `Drop` can't hide the change.
822      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      // Not this memo's fault: leave it dirty, so the next read
831      // recomputes it, and pass the panic on to its reader. A memo
832      // reading this one handles it the same way; past the memos it
833      // becomes a readable panic.
834      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 first, so nothing the closure's values do while they
852      // drop can queue or run it again.
853      disable(id);
854      drop_isolated(compute);
855      drop_isolated(payload);
856      false
857    }
858  }
859}
860
861/// Puts a closure back into its node and then runs `then`. If the closure
862/// disposed its own owner, the node is gone: the closure is handed back to
863/// be dropped outside the borrow.
864fn 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
875/// Stops a memo or effect for good. A disabled memo keeps its last value. A
876/// scoped effect's last scope is disposed, everything in it included.
877fn 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
895/// Marks what read `id` as `state`, everything further downstream as
896/// `Check`, and queues the effects among them.
897fn 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    // A node that was already stale has marked its own subscribers.
910    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
925/// Makes the running memo or effect, if any, depend on `source`.
926fn 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  // The observer can be gone if its closure disposed its own owner.
934  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
946/// Removes `id` from the subscriber lists of everything in `sources`.
947fn 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
955/// How log lines name a node: its debug name if it has one, otherwise its
956/// creation number and the name of its nearest named ancestor. Scopes and
957/// rows are rarely named; the widget above them usually is.
958fn 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}