Crate invalidation

Expand description

Invalidation: generic primitives for dependency-aware invalidation.

This crate provides building blocks for incremental computation systems where changes to upstream data must propagate to downstream consumers. It models invalidation as a combination of:

Channels (Channel, ChannelSet): Named domains for invalidation tracking (for example, layout, paint, accessibility).
Dependency graphs (InvalidationGraph): DAG of “A depends on B” edges, with cycle detection and bidirectional traversal.
Invalidation sets (InvalidationSet): Accumulated invalidated keys per channel with generation tracking for stale-computation detection.
Propagation policies (PropagationPolicy, EagerPolicy, LazyPolicy): Pluggable strategies for how invalidation spreads through the graph.
Topological drain (DrainSorted): Kahn’s algorithm to yield invalidated keys in dependency order.
Channel cascades (ChannelCascade): DAG of “invalidation on channel A also marks channel B” rules, with precomputed transitive closure.
Cross-channel edges (CrossChannelEdges): Sparse (key, channel) → (key, channel) edges for cross-key cross-channel dependencies.
Scratch buffers (TraversalScratch): Reusable traversal state for tight loops to avoid repeated allocations.

This crate owns invalidation primitives. It explicitly does not own recomputation, caching, or scheduling policy.

§Quick Start

use invalidation::{Channel, InvalidationTracker, EagerPolicy};

const LAYOUT: Channel = Channel::new(0);
const PAINT: Channel = Channel::new(1);

let mut tracker = InvalidationTracker::<u32>::new();
// `u32` is fine for compact 0-based IDs. Sparse/external IDs should be
// interned first so dense storage grows with node count, not key magnitude.

// Build dependency graph: 3 depends on 2, 2 depends on 1
tracker.add_dependency(2, 1, LAYOUT).unwrap();
tracker.add_dependency(3, 2, LAYOUT).unwrap();

// Mark with eager propagation (marks 1, 2, 3)
tracker.mark_with(1, LAYOUT, &EagerPolicy);

// Or mark manually without propagation
tracker.mark(1, PAINT);

// Drain in topological order: 1, 2, 3
for key in tracker.drain_sorted(LAYOUT) {
    let _ = key;
}

§Choosing An API

Use InvalidationTracker for the common “graph + set together” workflow.
Use InvalidationGraph plus InvalidationSet separately if your embedder already owns invalidation state and just wants the primitives.
Use DrainBuilder when you need deterministic drains, targeted drains, scratch reuse, or tracing.
Use intern::Interner when your natural keys are not already compact Copy identifiers.

§Using Components Separately

While InvalidationTracker provides a convenient combined API, you can also use the underlying types directly for more control:

use invalidation::{
    Channel, CycleHandling, InvalidationGraph, InvalidationSet, EagerPolicy, PropagationPolicy,
};

const LAYOUT: Channel = Channel::new(0);

// Build the dependency graph
let mut graph = InvalidationGraph::<u32>::new();
// Dense storage expects compact key spaces; sparse/owned keys should be
// interned first.
graph.add_dependency(2, 1, LAYOUT, CycleHandling::Error).unwrap();
graph.add_dependency(3, 2, LAYOUT, CycleHandling::Error).unwrap();

// Maintain invalidation state separately
let mut invalidated = InvalidationSet::new();
let eager = EagerPolicy;

// Propagate invalidation marks
eager.propagate(1, LAYOUT, &graph, &mut invalidated);

assert!(invalidated.is_invalidated(1, LAYOUT));
assert!(invalidated.is_invalidated(2, LAYOUT));
assert!(invalidated.is_invalidated(3, LAYOUT));

§Propagation Policies

The crate provides two built-in policies:

EagerPolicy: Immediately marks all transitive dependents when a key is marked invalidated. Use this when you need to know the full invalidation set immediately after marking. Use with InvalidationTracker::drain_sorted.
LazyPolicy: Only marks the key itself at mark time; no propagation occurs. Use InvalidationTracker::drain_affected_sorted to expand and process all affected keys at drain time.

You can implement PropagationPolicy for custom strategies.

§Choosing a Drain Function

drain_sorted / InvalidationTracker::drain_sorted: Drain exactly the keys that are currently marked invalidated, in topological order.
drain_affected_sorted / InvalidationTracker::drain_affected_sorted: Expand the invalidation set to include all transitive dependents before draining.
DrainBuilder: Configure ordering, scope, scratch reuse, and tracing in one place.

§Cycle Detection

InvalidationGraph::add_dependency supports configurable cycle handling via CycleHandling:

DebugAssert (default): Panic in debug builds, ignore in release.
Error: Return Err(CycleError) if a cycle would be created.
Ignore: Silently ignore the dependency.
Allow: Skip cycle detection entirely.

§`no_std` Support

This crate is no_std and uses alloc. It does not depend on std.

§Common Mistakes

add_dependency(a, b, ...) means a depends on b.
LazyPolicy is usually paired with affected drains, not plain drain_sorted.
Deterministic dense drains assume a compact key space; intern sparse or structured keys first.
If cycles are allowed, topological drains can stall.

Re-exports§

pub use intern::InternId;
pub use trace::InvalidationCause;
pub use trace::InvalidationTrace;
pub use trace::OneParentRecorder;

Modules§

intern: Interning helper for non-Copy keys.
trace: Explainability helpers for invalidation propagation.

Structs§

AnyOrder: Type-level marker for “any” drain ordering (ties are not specified).
CascadeCycleError: Error returned when adding a cascade would create a cycle.
Channel: Identifies an invalidation domain (layout, paint, accessibility, etc.).
ChannelCascade: Channel-to-channel cascade rules (same key, different channels).
ChannelSet: A compact bitfield representing a set of up to 64 channels.
ChannelSetIter: An iterator over the channels in a ChannelSet.
CrossChannelEdges: Sparse cross-channel dependency edges.
CycleError: Error returned when a cycle would be created by adding a dependency.
DeterministicOrder: Type-level marker for deterministic drain ordering (ties broken by Ord).
DrainBuilder: A builder that configures and performs a drain.
DrainSorted: Iterator that yields invalidated keys in topological order.
DrainSortedDeterministic: Deterministic variant of DrainSorted.
EagerPolicy: Eager propagation policy: immediately mark all transitive dependents.
InvalidationGraph: Dependency graph: “A depends on B” edges per channel.
InvalidationSet: Accumulated invalidated keys per channel with generation tracking.
InvalidationTracker: Combined invalidation tracker with dependency graph and invalidation set.
LazyPolicy: Lazy propagation policy: only marks the key itself, no propagation.
TraversalScratch: Reusable scratch storage for graph traversals.

Enums§

CycleHandling: How to handle cycle detection when adding dependencies.
DrainCompletion: Indicates whether a drain finished normally or stalled due to a cycle.

Traits§

DenseKey: Trait for keys that can be used as dense Vec indices.
PropagationPolicy: Trait for invalidation propagation policies.

Functions§

drain_affected_sorted: Creates a topologically sorted drain that includes all affected keys.
drain_affected_sorted_deterministic: Creates a deterministic, topologically sorted drain that includes all affected keys.
drain_affected_sorted_with_trace: Creates a topologically sorted drain of all affected keys, while recording a trace.
drain_sorted: Creates a topologically sorted drain from a invalidation set.
drain_sorted_deterministic: Creates a deterministic, topologically sorted drain from a invalidation set.