use std::any::{Any, type_name};
use std::cell::RefCell;
use std::collections::HashMap;
use std::marker::PhantomData;
use std::mem;
use std::ops::Deref;
use std::panic::{self, AssertUnwindSafe, Location};
use std::rc::Rc;
use slotmap::{SlotMap, new_key_type};
use crate::Owner;
pub const MAX_RUNS_PER_FLUSH: u32 = 100;
new_key_type! {
pub(crate) struct NodeId;
}
pub(crate) struct Computed {
pub(crate) changed: bool,
pub(crate) leftover: Option<Box<dyn Any>>,
}
pub(crate) type Compute = Box<dyn FnMut() -> Computed>;
pub(crate) enum Missing {
Disposed,
NoValue,
Gone,
}
impl Missing {
#[track_caller]
pub(crate) fn panic<T>(self, handle: &str) -> ! {
let ty = type_name::<T>();
match self {
Missing::Disposed => panic!(
"{handle}<{ty}> was used after its owner was disposed (try_get() returns None instead)"
),
Missing::NoValue => panic!(
"{handle}<{ty}> has no value: its closure panicked before producing one and was disabled"
),
Missing::Gone => panic!(
"{handle}<{ty}> was used after this thread's runtime was torn down (try_get() returns None instead)"
),
}
}
}
struct BorrowConflict(String);
struct Node {
kind: Kind,
owner: Option<NodeId>,
seq: u64,
name: Option<String>,
state: State,
disabled: bool,
compute: Option<Compute>,
children: Vec<NodeId>,
sources: Vec<NodeId>,
subscribers: Vec<NodeId>,
}
enum Kind {
Owner,
Signal {
value: Rc<dyn Any>,
},
Memo {
value: Rc<dyn Any>,
},
Effect {
queued: bool,
},
}
impl Kind {
fn name(&self) -> &'static str {
match self {
Kind::Owner => "owner",
Kind::Signal { .. } => "signal",
Kind::Memo { .. } => "memo",
Kind::Effect { .. } => "effect",
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum State {
Clean,
Check,
Dirty,
}
#[derive(Clone, Copy)]
struct Running {
id: NodeId,
is_memo: bool,
}
#[derive(Default)]
struct Graph {
nodes: SlotMap<NodeId, Node>,
queue: Vec<NodeId>,
observer: Option<NodeId>,
running: Option<Running>,
next_seq: u64,
flushing: bool,
}
impl Graph {
fn memo_running(&self) -> bool {
self.running.is_some_and(|running| running.is_memo)
}
}
impl Drop for Graph {
fn drop(&mut self) {
for (_, node) in self.nodes.drain() {
drop_isolated(node);
}
}
}
thread_local! {
static GRAPH: RefCell<Graph> = RefCell::new(Graph::default());
}
fn try_graph<R>(f: impl FnOnce(&mut Graph) -> R) -> Option<R> {
GRAPH
.try_with(|graph| {
let mut graph = graph
.try_borrow_mut()
.expect("invariant: the runtime is never borrowed while user code runs");
f(&mut graph)
})
.ok()
}
fn with_graph<R>(f: impl FnOnce(&mut Graph) -> R) -> R {
try_graph(f).expect("invariant: the runtime outlives every call that found it alive")
}
pub(crate) fn drop_isolated<T>(value: T) {
let caught = untrack(|| panic::catch_unwind(AssertUnwindSafe(move || drop(value))));
if let Err(payload) = caught {
tracing::error!(
"a Drop impl panicked while the runtime was dropping a value or closure: {}",
panic_message(payload.as_ref())
);
}
}
struct DropIsolated<T>(Option<T>);
impl<T> Deref for DropIsolated<T> {
type Target = T;
fn deref(&self) -> &T {
self
.0
.as_ref()
.expect("invariant: a DropIsolated holds its value until it is dropped")
}
}
impl<T> Drop for DropIsolated<T> {
fn drop(&mut self) {
drop_isolated(self.0.take());
}
}
#[cfg(test)]
pub(crate) fn is_unborrowed() -> bool {
GRAPH.with(|graph| graph.try_borrow_mut().is_ok())
}
#[cfg(test)]
pub(crate) fn subscriber_count(id: NodeId) -> usize {
with_graph(|g| g.nodes.get(id).map_or(0, |node| node.subscribers.len()))
}
#[cfg(test)]
pub(crate) fn slot_of(id: NodeId) -> (u32, u32) {
use slotmap::Key;
let ffi = id.data().as_ffi();
(ffi as u32, (ffi >> 32) as u32)
}
#[derive(Clone, Copy)]
pub struct Runtime {
_not_send: PhantomData<*const ()>,
}
impl Runtime {
pub fn current() -> Runtime {
Runtime {
_not_send: PhantomData,
}
}
#[track_caller]
pub fn new_owner(&self) -> Owner {
Owner::new(None)
}
#[track_caller]
pub fn flush(&self) {
flush();
}
pub fn node_count(&self) -> usize {
try_graph(|g| g.nodes.len()).unwrap_or(0)
}
}
pub fn untrack<R>(f: impl FnOnce() -> R) -> R {
struct Restore(Option<NodeId>);
impl Drop for Restore {
fn drop(&mut self) {
let observer = self.0;
try_graph(|g| g.observer = observer);
}
}
let _restore = try_graph(|g| g.observer.take()).map(Restore);
f()
}
#[track_caller]
pub(crate) fn create_owner(parent: Option<NodeId>) -> NodeId {
create(parent, Kind::Owner, None)
}
#[track_caller]
pub(crate) fn create_signal(owner: NodeId, value: Rc<dyn Any>) -> NodeId {
create(Some(owner), Kind::Signal { value }, None)
}
#[track_caller]
pub(crate) fn create_memo(owner: NodeId, value: Rc<dyn Any>, compute: Compute) -> NodeId {
create(Some(owner), Kind::Memo { value }, Some(compute))
}
#[track_caller]
pub(crate) fn create_effect(owner: NodeId, compute: Compute) -> NodeId {
create(Some(owner), Kind::Effect { queued: true }, Some(compute))
}
#[track_caller]
pub(crate) fn new_scope() -> NodeId {
let (effect, previous) = with_graph(|g| {
let effect = g
.running
.expect("invariant: new_scope() runs inside an effect")
.id;
let previous = g
.nodes
.get_mut(effect)
.map(|node| mem::take(&mut node.children))
.unwrap_or_default();
(effect, previous)
});
for scope in previous {
dispose(scope);
}
create_owner(Some(effect))
}
#[track_caller]
fn create(owner: Option<NodeId>, kind: Kind, compute: Option<Compute>) -> NodeId {
let owner_alive = try_graph(|g| owner.is_none_or(|owner| g.nodes.contains_key(owner)));
if owner_alive != Some(true) {
let what = kind.name();
drop_isolated((kind, compute));
if owner_alive.is_none() {
panic!("tried to create a new {what} after this thread's runtime was torn down");
}
panic!("tried to create a new {what} under an owner that was already disposed");
}
with_graph(|g| {
let seq = g.next_seq;
g.next_seq += 1;
let is_effect = matches!(kind, Kind::Effect { .. });
let state = if compute.is_some() {
State::Dirty
} else {
State::Clean
};
let id = g.nodes.insert(Node {
kind,
owner,
seq,
name: None,
state,
disabled: false,
compute,
children: Vec::new(),
sources: Vec::new(),
subscribers: Vec::new(),
});
if let Some(owner) = owner
&& let Some(parent) = g.nodes.get_mut(owner)
{
parent.children.push(id);
}
if is_effect {
g.queue.push(id);
}
id
})
}
pub(crate) fn set_name(id: NodeId, name: String) {
try_graph(|g| {
if let Some(node) = g.nodes.get_mut(id) {
node.name = Some(name);
}
});
}
pub(crate) fn is_disposed(id: NodeId) -> bool {
try_graph(|g| !g.nodes.contains_key(id)).unwrap_or(true)
}
#[track_caller]
pub(crate) fn read<T: 'static, R>(
id: NodeId,
track: bool,
handle: &str,
f: impl FnOnce(&T) -> R,
) -> Result<R, Missing> {
let found = try_graph(|g| {
let node = g.nodes.get(id)?;
match &node.kind {
Kind::Signal { value } => Some((Rc::clone(value), false, false)),
Kind::Memo { value } => Some((
Rc::clone(value),
true,
node.compute.is_none() && !node.disabled,
)),
Kind::Owner | Kind::Effect { .. } => None,
}
});
let Some(found) = found else {
return Err(Missing::Gone);
};
let Some((value, is_memo, computing)) = found else {
return Err(Missing::Disposed);
};
if computing {
drop_isolated(f);
panic!(
"{handle}<{}> was read while computing its own value (a dependency cycle)",
type_name::<T>()
);
}
if is_memo {
refresh(id);
}
if track {
with_graph(|g| subscribe(g, id));
}
let value = DropIsolated(Some(downcast::<T>(value)));
let Ok(slot) = value.try_borrow() else {
drop_isolated(f);
borrow_conflict(format!(
"{handle}<{}> was read inside its own update() (at {})",
type_name::<T>(),
Location::caller()
));
};
match slot.as_ref() {
Some(current) => Ok(f(current)),
None => Err(Missing::NoValue),
}
}
#[track_caller]
pub(crate) fn read_or_panic<T: 'static, R>(
id: NodeId,
track: bool,
handle: &str,
f: impl FnOnce(&T) -> R,
) -> R {
match read(id, track, handle, f) {
Ok(result) => result,
Err(missing) => missing.panic::<T>(handle),
}
}
#[track_caller]
pub(crate) fn borrow_conflict(message: String) -> ! {
if with_graph(|g| g.memo_running()) {
panic::resume_unwind(Box::new(BorrowConflict(message)));
}
panic!("{message}");
}
#[track_caller]
pub(crate) fn write<T: 'static, R>(
id: NodeId,
f: impl FnOnce(&mut Option<T>) -> R,
) -> Result<R, Missing> {
let found = try_graph(|g| {
let value = match g.nodes.get(id).map(|node| &node.kind) {
Some(Kind::Signal { value }) => Some(Rc::clone(value)),
_ => None,
};
(value, g.memo_running())
});
let (value, memo_running) = match found {
Some((Some(value), memo_running)) => (value, memo_running),
Some((None, _)) => {
drop_isolated(f);
return Err(Missing::Disposed);
}
None => {
drop_isolated(f);
return Err(Missing::Gone);
}
};
if memo_running {
drop_isolated(f);
panic!(
"Signal<{}> was written inside a memo: memos must not write signals; use an effect",
type_name::<T>()
);
}
let value = DropIsolated(Some(downcast::<T>(value)));
let outcome = {
let Ok(mut slot) = value.try_borrow_mut() else {
drop_isolated(f);
panic!(
"Signal<{}> was written while a with() call on it was still running",
type_name::<T>()
);
};
panic::catch_unwind(AssertUnwindSafe(|| f(&mut slot)))
};
with_graph(|g| mark_subscribers(g, id, State::Dirty));
match outcome {
Ok(result) => Ok(result),
Err(payload) => panic::resume_unwind(payload),
}
}
#[track_caller]
pub(crate) fn write_or_panic<T: 'static, R>(
id: NodeId,
f: impl FnOnce(&mut Option<T>) -> R,
) -> Option<R> {
match write(id, f) {
Ok(result) => Some(result),
Err(Missing::Gone) => None,
Err(missing) => missing.panic::<T>("Signal"),
}
}
fn downcast<T: 'static>(value: Rc<dyn Any>) -> Rc<RefCell<Option<T>>> {
value
.downcast()
.expect("invariant: a handle's type matches its node's value type")
}
pub(crate) fn dispose(owner: NodeId) {
let Some(removed) = try_graph(|g| {
if let Some(parent) = g.nodes.get(owner).and_then(|node| node.owner)
&& let Some(parent) = g.nodes.get_mut(parent)
{
parent.children.retain(|&child| child != owner);
}
let mut removed = Vec::new();
let mut stack = vec![owner];
while let Some(id) = stack.pop() {
let Some(node) = g.nodes.remove(id) else {
continue;
};
stack.extend_from_slice(&node.children);
unsubscribe_all(g, id, &node.sources);
removed.push(node);
}
removed
}) else {
return;
};
for node in removed {
drop_isolated(node);
}
}
#[track_caller]
fn flush() {
let started = try_graph(|g| (!g.memo_running()).then(|| !mem::replace(&mut g.flushing, true)));
match started {
Some(Some(true)) => {}
Some(None) => {
panic!("Runtime::flush() was called inside a memo: memos must not run effects")
}
None | Some(Some(false)) => return,
}
let mut runs: HashMap<NodeId, u32> = HashMap::new();
loop {
let round = with_graph(|g| {
let mut round = mem::take(&mut g.queue);
round.sort_by_key(|&id| g.nodes.get(id).map_or(0, |node| node.seq));
round
});
if round.is_empty() {
break;
}
let mut round = round.into_iter();
while let Some(id) = round.next() {
let runnable = with_graph(|g| match g.nodes.get_mut(id) {
Some(Node {
kind: Kind::Effect { queued },
disabled,
..
}) => {
*queued = false;
!*disabled
}
_ => false,
});
if !runnable {
continue;
}
let count = runs.entry(id).or_insert(0);
if *count >= MAX_RUNS_PER_FLUSH {
let what = with_graph(|g| describe(g, id));
tracing::error!(
"{what} is in a dependency cycle: it ran {MAX_RUNS_PER_FLUSH} times in one \
flush and was queued again, so it is disabled"
);
disable(id);
continue;
}
match panic::catch_unwind(AssertUnwindSafe(|| refresh(id))) {
Ok(ran) => *count += u32::from(ran),
Err(payload) => {
with_graph(|g| {
if let Some(Node {
kind: Kind::Effect { queued },
..
}) = g.nodes.get_mut(id)
&& !*queued
{
*queued = true;
g.queue.push(id);
}
g.queue.extend(round);
g.flushing = false;
});
panic::resume_unwind(payload);
}
}
}
}
with_graph(|g| g.flushing = false);
}
fn refresh(id: NodeId) -> bool {
let sources = with_graph(|g| match g.nodes.get(id) {
Some(node) if !node.disabled && node.state == State::Check => node.sources.clone(),
_ => Vec::new(),
});
for source in sources {
refresh(source);
if with_graph(|g| g.nodes.get(id).map(|node| node.state)) != Some(State::Check) {
break;
}
}
let dirty = with_graph(|g| match g.nodes.get_mut(id) {
Some(node) if !node.disabled => {
if node.state == State::Check {
node.state = State::Clean;
}
node.state == State::Dirty
}
_ => false,
});
dirty && run(id)
}
fn run(id: NodeId) -> bool {
let taken = with_graph(|g| {
let node = g.nodes.get_mut(id)?;
let compute = node.compute.take()?;
let is_memo = matches!(node.kind, Kind::Memo { .. });
node.state = State::Clean;
let sources = mem::take(&mut node.sources);
unsubscribe_all(g, id, &sources);
Some((compute, is_memo))
});
let Some((mut compute, is_memo)) = taken else {
return false;
};
let outer = with_graph(|g| {
(
g.observer.replace(id),
g.running.replace(Running { id, is_memo }),
)
});
let result = panic::catch_unwind(AssertUnwindSafe(&mut compute));
with_graph(|g| (g.observer, g.running) = outer);
let payload = match result {
Ok(Computed { changed, leftover }) => {
let orphan = put_back(id, compute, |g| {
if changed {
mark_subscribers(g, id, State::Dirty);
}
});
drop_isolated(leftover);
drop_isolated(orphan);
return changed;
}
Err(payload) => payload,
};
match payload.downcast::<BorrowConflict>() {
Ok(conflict) => {
let orphan = put_back(id, compute, |g| {
if let Some(node) = g.nodes.get_mut(id) {
node.state = State::Dirty;
}
});
drop_isolated(orphan);
if with_graph(|g| g.memo_running()) {
panic::resume_unwind(conflict);
}
panic!("{}", conflict.0);
}
Err(payload) => {
let what = with_graph(|g| describe(g, id));
tracing::error!(
"{what} panicked and is disabled: {}",
panic_message(payload.as_ref())
);
disable(id);
drop_isolated(compute);
drop_isolated(payload);
false
}
}
}
fn put_back(id: NodeId, compute: Compute, then: impl FnOnce(&mut Graph)) -> Option<Compute> {
with_graph(|g| {
let Some(node) = g.nodes.get_mut(id) else {
return Some(compute);
};
node.compute = Some(compute);
then(g);
None
})
}
fn disable(id: NodeId) {
let Some((compute, scopes)) = with_graph(|g| {
let node = g.nodes.get_mut(id)?;
node.disabled = true;
let sources = mem::take(&mut node.sources);
let compute = node.compute.take();
let scopes = mem::take(&mut node.children);
unsubscribe_all(g, id, &sources);
Some((compute, scopes))
}) else {
return;
};
drop_isolated(compute);
for scope in scopes {
dispose(scope);
}
}
fn mark_subscribers(g: &mut Graph, id: NodeId, state: State) {
let Some(node) = g.nodes.get(id) else {
return;
};
let mut stack: Vec<(NodeId, State)> = node.subscribers.iter().map(|&s| (s, state)).collect();
while let Some((id, state)) = stack.pop() {
let Some(node) = g.nodes.get_mut(id) else {
continue;
};
if node.disabled || node.state >= state {
continue;
}
let was_clean = node.state == State::Clean;
node.state = state;
match &mut node.kind {
Kind::Effect { queued } if !*queued => {
*queued = true;
g.queue.push(id);
}
Kind::Memo { .. } if was_clean => {
stack.extend(node.subscribers.iter().map(|&s| (s, State::Check)));
}
_ => {}
}
}
}
fn subscribe(g: &mut Graph, source: NodeId) {
let Some(observer) = g.observer else {
return;
};
if observer == source || !g.nodes.contains_key(source) {
return;
}
let Some(node) = g.nodes.get_mut(observer) else {
return;
};
if node.sources.contains(&source) {
return;
}
node.sources.push(source);
if let Some(source) = g.nodes.get_mut(source) {
source.subscribers.push(observer);
}
}
fn unsubscribe_all(g: &mut Graph, id: NodeId, sources: &[NodeId]) {
for &source in sources {
if let Some(source) = g.nodes.get_mut(source) {
source.subscribers.retain(|&s| s != id);
}
}
}
fn describe(g: &Graph, id: NodeId) -> String {
let Some(node) = g.nodes.get(id) else {
return String::from("a disposed node");
};
let kind = node.kind.name();
if let Some(name) = &node.name {
return format!("{kind} {name}");
}
let mut parent = node.owner;
while let Some(ancestor) = parent.and_then(|parent| g.nodes.get(parent)) {
if let Some(name) = &ancestor.name {
return format!("unnamed {kind} #{} in {name}", node.seq);
}
parent = ancestor.owner;
}
format!("unnamed {kind} #{}", node.seq)
}
fn panic_message(payload: &(dyn Any + Send)) -> &str {
if let Some(message) = payload.downcast_ref::<&str>() {
message
} else if let Some(message) = payload.downcast_ref::<String>() {
message
} else if let Some(conflict) = payload.downcast_ref::<BorrowConflict>() {
&conflict.0
} else {
"(panic payload is not a string)"
}
}