Expand description
§Cranpose Core
The core runtime engine for Cranpose. This crate implements the fundamental algorithms for managing the composition tree, state snapshots, and change detection.
§When to Use
Use cranpose-core directly if you are:
- Building a custom tree management system unrelated to UI (e.g., a reactive scene graph).
- Implementing low-level state primitives.
- Developing a renderer for a strictly non-standard environment where the higher-level
cranpose-uimight be too opinionated.
§Key Concepts
- Slot Table: The active slot-table runtime. It is a preorder group table backed by separate group, payload, and node storage. Active structure stays in the table; inactive retained branches are detached into explicit
DetachedSubtreeobjects instead of being encoded as gaps. - Composer: The primary interface for building and updating the slot table. It coordinates scopes, retention/disposal policy, remembered values, and node lifecycle on top of the semantic slot-storage API.
- Snapshot System: A multi-version concurrency control (MVCC) system for state. It allows
MutableStateto be read and written transactions, enabling atomic updates and ensuring UI consistency during concurrent operations. - Recomposition: The process of re-executing composable functions when their dependencies change. The runtime tracks dependencies at a fine-grained level (scopes) to minimize re-execution.
For the short invariant checklist the slot table must uphold, see docs/slot_table_invariants.md. For the design history behind the current architecture, see docs/cranpose_slot_table_v2_design.md (historical). Gap-table material is historical rationale only.
§Example: Manual State Transaction
The following example shows how to perform atomic state updates using the snapshot system explicitly.
use cranpose_core::{mutableStateOf, run_in_mutable_snapshot};
fn main() {
let count = mutableStateOf(0);
// Any modification to state must happen within a snapshot.
// This ensures that observers (like the UI recomposer) see a consistent view of data.
run_in_mutable_snapshot(|| {
let current = count.value();
count.set(current + 1);
});
assert_eq!(count.value(), 1);
}§Internals: Snapshots and Slot Table System
This section documents the internals of the Snapshot and Slot Table systems, which form the foundation of the composition runtime.
§Table of Contents
§Overview
The cranpose runtime is built on two fundamental subsystems:
- Snapshot System: Provides Multi-Version Concurrency Control (MVCC) for state isolation, conflict detection, and optimistic merging
- Slot Table System: Manages the composition tree structure, enabling efficient recomposition and structural preservation
These systems work together but serve distinct purposes:
- Snapshots manage state values (what data is visible)
- Slot tables manage composition structure (where data is stored in the UI tree)
§Snapshot System
§Architecture Overview
The snapshot system implements a sophisticated MVCC mechanism that allows:
- Isolated views of mutable state
- Concurrent modifications without locks
- Optimistic conflict detection and merging
- Efficient garbage collection of obsolete records
§Core Files
crates/cranpose-core/src/snapshot_v2/
├── mod.rs - Main types and coordination
├── runtime.rs - Global runtime state
├── mutable.rs - Mutable snapshot implementation
├── readonly.rs - Read-only snapshot implementation
├── nested.rs - Nested snapshot support
├── global.rs - Global snapshot
└── transparent.rs - Transparent observer snapshots
Supporting files:
├── state.rs - State objects and records
├── snapshot_id_set.rs - Optimized bit-set for IDs
├── snapshot_pinning.rs - Snapshot GC pinning
├── snapshot_weak_set.rs - Weak references to state
├── snapshot_double_index_heap.rs - Heap for pinning
└── snapshot_state_observer.rs - State observation§Data Structures
§SnapshotIdSet
An optimized immutable bit-set for tracking snapshot IDs with O(1) access for recent snapshots:
pub struct SnapshotIdSet {
upper_set: u64, // IDs [lower_bound+64..lower_bound+127]
lower_set: u64, // IDs [lower_bound..lower_bound+63]
lower_bound: usize, // Base offset
below_bound: Box<[SnapshotId]>, // Sorted array for older IDs
}Key Properties:
- Recent snapshots (128 most recent): O(1) bit operations
- Older snapshots: O(log N) binary search
- Immutable: All modifications create new instances (copy-on-write)
- Memory efficient: Two 64-bit integers cover 128 IDs
Operations:
get(id) // O(1) for recent, O(log N) for old
set(id) // O(1) for recent, O(N) for old (copy-on-write)
or(other) // Combine two sets
and_not(other) // Set difference
lowest() // Find minimum ID§StateRecord
The fundamental unit of state versioning - a linked list node containing one version of a state value:
pub struct StateRecord {
snapshot_id: Cell<SnapshotId>, // Which snapshot owns this
tombstone: Cell<bool>, // Marked for deletion
next: Cell<Option<Arc<StateRecord>>>, // Chain to older records
value: RwLock<Option<Box<dyn Any>>>, // Type-erased value
}Record Chain Example:
SnapshotMutableState<i32>
head → [id=10, value=100, next] → [id=8, value=50, next] → [id=5, value=0, next] → None
↑ ↑ ↑
Latest Older OldestSpecial IDs:
INVALID_SNAPSHOT(SnapshotId::MAX): Marks records available for reuse- Valid IDs: Used to determine visibility to each snapshot
§SnapshotMutableState<T>
The primary state object that applications interact with:
pub struct SnapshotMutableState<T> {
head: RwLock<Arc<StateRecord>>, // Head of record chain
policy: Arc<dyn MutationPolicy<T>>, // Equality/merge policy
id: ObjectId, // Unique object ID
weak_self: Weak<Self>, // Self-reference for callbacks
apply_observers: Vec<Box<dyn Fn()>>, // Applied change observers
}Usage:
let state = SnapshotMutableState::new(42, StructuralEqualityPolicy::new());
let value = state.read(&snapshot); // Read with snapshot isolation
state.write(&snapshot, 100); // Write creates new recordMutationPolicy: Defines how values are compared and merged:
StructuralEqualityPolicy: UsesPartialEqReferentialEqualityPolicy: UsesArcpointer equality- Custom policies can implement three-way merging
§MutableSnapshot
A snapshot that can track writes and be applied to its parent:
pub struct MutableSnapshot {
state: SnapshotState,
base_parent_id: SnapshotId, // Parent ID when created
nested_count: Cell<usize>, // Active nested snapshots
applied: Cell<bool>, // Applied flag
}SnapshotState (shared between snapshot types):
pub struct SnapshotState {
id: Cell<SnapshotId>,
invalid: RefCell<SnapshotIdSet>, // Invalid snapshot IDs
pin_handle: Cell<PinHandle>, // Keep alive for GC
disposed: Cell<bool>,
read_observer: Option<ReadObserver>, // Track reads
write_observer: Option<WriteObserver>, // Track writes
modified: RefCell<HashMap<StateObjectId, (Arc<dyn StateObject>, SnapshotId)>>,
pending_children: RefCell<HashSet<SnapshotId>>,
}The modified map tracks all state objects written to in this snapshot:
- Key:
StateObjectId(unique object identifier) - Value:
(Arc<StateObject>, SnapshotId)- the object and writer snapshot ID
§Snapshot Lifecycle
§1. Creation
// In runtime.rs
pub fn allocate_snapshot() -> (SnapshotId, SnapshotIdSet) {
let id = next_snapshot_id.fetch_add(1);
let invalid = open_snapshots.clone();
open_snapshots.set(id);
(id, invalid)
}Steps:
- Allocate new monotonically increasing ID
- Capture current
open_snapshotsas theinvalidset - Add new ID to
open_snapshots - Pin the snapshot ID to prevent GC
Why capture open_snapshots? Any snapshot currently open might write to state objects, so their writes should be invisible to this new snapshot until they’re applied.
§2. Reading State
pub fn read(&self, snapshot: &dyn Snapshot) -> T {
snapshot.record_read(self); // Observer notification
let head = self.head.read();
let record = readable_record_for(
&head,
snapshot.id(),
&snapshot.invalid()
);
// Read value from record
}Finding the readable record:
fn readable_record_for(
head: &Arc<StateRecord>,
snapshot_id: SnapshotId,
invalid: &SnapshotIdSet
) -> Arc<StateRecord> {
let mut current = head.clone();
let mut best: Option<Arc<StateRecord>> = None;
loop {
let id = current.snapshot_id.get();
// Skip tombstones and invalid records
if !current.tombstone.get()
&& id <= snapshot_id
&& !invalid.get(id) {
// Keep highest valid ID ≤ snapshot_id
if best.is_none() || id > best.as_ref().unwrap().snapshot_id.get() {
best = Some(current.clone());
}
}
match current.next.get() {
Some(next) => current = next,
None => break,
}
}
best.expect("No readable record found")
}Key insight: Walk the chain, skip invalid/tombstone records, return the record with the highest valid ID ≤ snapshot_id.
§3. Writing State
pub fn write(&self, snapshot: &dyn Snapshot, value: T) {
snapshot.record_write(self); // Observer + track in modified map
let writable = self.writable_record(
snapshot.id(),
snapshot.reuse_limit()
);
*writable.value.write() = Some(Box::new(value));
}Creating/reusing writable records:
fn writable_record(&self, snapshot_id: SnapshotId, reuse_limit: SnapshotId)
-> Arc<StateRecord> {
let head = self.head.read();
// Fast path: reuse existing record with this snapshot's ID
if head.snapshot_id.get() == snapshot_id {
return head.clone();
}
// Try to reuse INVALID records below reuse_limit
if let Some(reusable) = find_reusable_record(&head, reuse_limit) {
reusable.snapshot_id.set(snapshot_id);
reusable.tombstone.set(false);
return reusable;
}
// Create new record and prepend to chain
let new_record = Arc::new(StateRecord {
snapshot_id: Cell::new(snapshot_id),
tombstone: Cell::new(false),
next: Cell::new(Some(head.clone())),
value: RwLock::new(None),
});
*self.head.write() = new_record.clone();
new_record
}Record reuse is critical for performance - instead of creating infinite records, we reuse ones that are no longer visible to any snapshot.
§4. Applying (Merging)
The most complex operation - merging a child snapshot’s changes into its parent:
pub fn apply(self) -> SnapshotApplyResult {
// Collect all modified objects
let modified = self.state.modified.borrow();
for (obj_id, (state_obj, writer_id)) in modified.iter() {
// 1. Find three records for three-way merge
let applied = find_applied_record(state_obj, writer_id);
let current = find_current_record(state_obj, parent_snapshot);
let previous = find_previous_record(state_obj, base_parent_id);
// 2. Detect conflicts
let last_write_id = RUNTIME.last_writes.get(obj_id);
if last_write_id != self.base_parent_id {
// Another snapshot modified this object!
// 3. Attempt merge
match merge_records(previous, current, applied) {
Some(merged) => {
// Merge succeeded
commit_merged_record(state_obj, merged);
}
None => {
// Merge failed - conflict!
return SnapshotApplyResult::Failure;
}
}
} else {
// No conflict - promote child's record
promote_child_record(state_obj, applied);
}
}
// 4. Update runtime state
advance_global_snapshot();
notify_observers();
SnapshotApplyResult::Success
}Three-way merge visualization:
Timeline:
t0: Create snapshot S1 (base_parent_id = G0)
previous = state.read(G0) = "A"
t1: Snapshot S1 writes "B"
applied = "B"
t2: Snapshot S2 writes "C" and applies
current = state.read(G1) = "C"
t3: Snapshot S1 tries to apply
previous = "A"
current = "C" (≠ previous, conflict detected!)
applied = "B"
Merge attempt: Can we merge "A" → "C" and "A" → "B"?Merge strategies (from MutationPolicy):
- PromoteChild: No conflict (current == previous), use applied
- PromoteExisting: Merged value equals current, use current
- CommitMerged: Create new merged record
§5. Disposal
impl Drop for MutableSnapshot {
fn drop(&mut self) {
if !self.applied.get() {
self.state.dispose();
}
}
}
fn dispose(&self) {
self.disposed.set(true);
// Release pin (allow GC)
let pin = self.pin_handle.take();
RUNTIME.release_pin(pin);
// Close snapshot ID
RUNTIME.close_snapshot(self.id.get());
// Decrement parent nested count
if let Some(parent) = self.parent {
parent.decrement_nested();
}
// Trigger on_dispose callbacks
for callback in &self.on_dispose {
callback();
}
}§Garbage Collection (Record Reuse System)
IMPORTANT: This is NOT traditional garbage collection. Rust’s Arc already provides automatic memory management. This system is about record chain cleanup and reuse optimization.
§Why Needed in Rust (Not Just Copy-Paste from Kotlin)
The Problem:
let state = SnapshotMutableState::new(0);
// Without record reuse:
for i in 0..1000 {
state.set(i); // Creates new record each time
}
// Result: 1000 records in chain, even though only latest matters!
// Memory: ~64KB for records that will never be readWhy Rust’s Arc Doesn’t Help:
- Arc keeps records alive: Each record has
next: Cell<Option<Arc<StateRecord>>> - Chain references prevent collection: Head → Record1 → Record2 → Record3…
- Arc only frees when refcount = 0, but head always holds reference to entire chain
- Without cleanup: Infinite record chain growth = memory leak
What This System Actually Does:
- Identifies obsolete records: Records older than
lowest_pinned_snapshotcan’t be read - Marks for reuse: Set
snapshot_id = INVALID_SNAPSHOTinstead of dropping - Reuses on next write:
writable_record()checks for INVALID records first - Prevents chain growth: Bounded memory regardless of write count
§Real-World Impact
Without record reuse (hypothetical):
// UI counter that updates every frame (60 FPS)
let counter = SnapshotMutableState::new(0);
for frame in 0..3600 { // 1 minute at 60 FPS
counter.set(frame);
}
// Memory: 3600 records × 64 bytes = ~230 KB
// After 1 hour: ~13 MB just for one counter!With record reuse:
// Same scenario, but records are reused
// Memory: ~3-10 records (bounded by concurrent snapshot count)
// Memory: ~200-640 bytes regardless of time§Actual Usage in Code
The cleanup runs automatically on every global write:
// state.rs:647
state.set(new_value);
↓
advance_global_snapshot(new_id); // state.rs:647
↓
check_and_overwrite_unused_records_locked(); // global.rs:190
↓
EXTRA_STATE_OBJECTS.remove_if(|state| {
state.overwrite_unused_records() // Cleanup happens here
});Frequency: Every write to global snapshot (most common case).
§The Algorithm Explained
§Kotlin vs Rust: Why Both Need This
Kotlin (Original Compose):
- JVM GC collects unreferenced objects automatically
- Still needs record reuse because record chains hold strong references
- JVM GC won’t collect records still referenced by chain
- Same problem: unbounded chain growth without manual cleanup
Rust (This Implementation):
Arcprovides automatic reference counting- Same problem as Kotlin: chain references prevent automatic cleanup
Arconly drops when refcount = 0, but chain maintains references- Not a copy-paste bug: Genuinely required for memory bounds
Key Insight: This isn’t about memory safety (Rust guarantees that). It’s about memory efficiency. Without this system, memory usage grows O(n) with write count instead of O(1).
§Visual Example: Why Arc Alone Fails
// Initial state
state.head -> [id=1, value=0, next=None]
Arc::strong_count = 1
// After state.set(10)
state.head -> [id=2, value=10, next] -> [id=1, value=0, next=None]
Arc::strong_count = 1 Arc::strong_count = 1 ← Still alive!
// After state.set(20)
state.head -> [id=3, value=20, next] -> [id=2, value=10, next] -> [id=1, value=0, next=None]
↑ Can't drop: still referenced by id=3
// After 1000 writes: Chain of 1000 records, all kept alive by next pointers
// Arc can't help because references form a chain
// WITH record reuse:
state.head -> [id=1003, value=1000, next] -> [id=INVALID, reusable] -> [id=1, value=0, next=None]
↑ Latest ↑ Marked for reuse ↑ PREEXISTING (kept)
// Next write reuses INVALID record instead of allocating§Pinning System
Problem: Records can only be reused if no snapshot can read them.
Solution: Track the lowest snapshot ID that might read each record:
pub struct SnapshotPinning {
pins: DoubleIndexHeap<SnapshotId>, // Min-heap of pinned IDs
}
pub fn pin_snapshot(id: SnapshotId) -> PinHandle {
PINNING.pins.insert(id)
}
pub fn lowest_pinned_snapshot() -> SnapshotId {
PINNING.pins.min().unwrap_or(SnapshotId::MAX)
}Reuse limit: Records with id < lowest_pinned_snapshot() are safe to reuse.
§Record Cleanup
fn overwrite_unused_records_locked(&self, reuse_limit: SnapshotId) {
let head = self.head.read();
let mut records_below: Vec<Arc<StateRecord>> = Vec::new();
// 1. Find records below reuse limit
let mut current = head.clone();
loop {
let id = current.snapshot_id.get();
if id < reuse_limit && id != INVALID_SNAPSHOT {
records_below.push(current.clone());
}
match current.next.get() {
Some(next) => current = next,
None => break,
}
}
if records_below.len() <= 1 {
return; // Keep at least one historical record
}
// 2. Keep highest record below limit (most recent history)
records_below.sort_by_key(|r| std::cmp::Reverse(r.snapshot_id.get()));
let keep = records_below[0].clone();
// 3. Mark others as INVALID, copy data to reuse
for record in &records_below[1..] {
let keep_value = keep.value.read().clone();
*record.value.write() = keep_value;
record.snapshot_id.set(INVALID_SNAPSHOT);
record.tombstone.set(false);
}
}Key insight: Keep one historical record for potential rollback, mark older ones as INVALID for reuse.
§Nested Snapshots
Snapshots can be nested to create isolation boundaries:
let outer = take_mutable_snapshot();
{
let inner = outer.take_nested_mutable_snapshot();
// Modifications in inner are isolated from outer
inner.apply()?; // Merge into outer
}
outer.apply()?; // Merge into globalNested tracking:
- Parent tracks
nested_countof active children - Parent cannot apply while children are alive
- Children’s
base_parent_idpoints to parent’s ID at creation time
§Slot Table System
§Architecture Overview
The active slot-table implementation separates active structure, payload storage, node identity, and retention into distinct layers, replacing the historical gap-buffer design.
It separates the runtime into distinct storage layers:
- Active structure lives in a preorder
Vec<GroupRecord>. - Remembered payloads live in a separate payload table.
- Node identities live in a separate node table.
- Inactive preserved branches live outside the active table as explicit
DetachedSubtreevalues.
That gives the runtime much simpler semantics:
- There is no semantic
Gapinside the active table. - Retention is explicit detach/restore, not preserved free space.
- Scopes are resolved through an index, not by scanning all groups.
- All structural mutation goes through the writer session state.
The invariants it must uphold are tracked in docs/slot_table_invariants.md; the design history behind this architecture is docs/cranpose_slot_table_v2_design.md (historical).
§Core Files
crates/cranpose-core/src/
├── retention.rs - Detached-subtree retention bookkeeping
└── slot/
├── types.rs - Semantic handles, cursors, and operation result types
├── table.rs - SlotTable and write-session entry points
├── writer.rs - begin/finish/end/skip group traversal
├── table/ - SlotTable metadata, mutation, and value helpers
├── writer/ - Writer state-machine helper modules
├── groups.rs - GroupRecord helpers and child traversal
├── payload.rs - Payload storage and value-slot records
├── payload_anchors.rs - Stable value-slot identity registry
├── nodes.rs - Node record storage and subtree extraction
├── anchors.rs - AnchorRegistry and anchor state tracking
├── scope_index.rs - ScopeId -> active group lookup
├── detach.rs - DetachedSubtree extraction and restore
├── validate/ - Structural invariant checking
├── debug.rs / reader.rs - Debug snapshots and textual dumps
└── lifecycle.rs - Deferred payload disposal§Data Structures
§SlotTable
The active table stores groups, payloads, nodes, stable identity registries, and scope lookup separately:
pub struct SlotTable {
storage_id: usize,
groups: Vec<GroupRecord>,
payloads: Vec<PayloadRecord>,
nodes: Vec<NodeRecord>,
anchors: AnchorRegistry,
payload_anchors: PayloadAnchorRegistry,
scope_index: ScopeIndex,
mutation_debug_stats: SlotTableMutationDebugStats,
next_group_generation: u32,
}Key properties:
- Exact active structure:
subtree_lenalways means the active preorder span. - Stable addressing: groups use stable
AnchorIdidentities plus transientActiveGroupIdhandles; values use anchor-basedValueSlotId. - Indexed scopes: active scopes map directly to group anchors.
- Explicit retention: removed branches are detached from the table before any retain/dispose decision happens.
§GroupRecord
Each group describes one active composable call:
pub struct GroupRecord {
key: GroupKey,
parent_anchor: AnchorId,
depth: u32,
subtree_len: u32,
payload_start: u32,
payload_len: u32,
node_start: u32,
node_len: u32,
subtree_node_count: u32,
generation: u32,
anchor: AnchorId,
scope_id: Option<ScopeId>,
}parent_anchor stays stable even when active indexes shift. subtree_len and
subtree_node_count are validated against the actual preorder tree.
§PayloadRecord and NodeRecord
Remembered values and emitted nodes are stored outside the structural group table:
pub struct PayloadRecord {
owner: AnchorId,
anchor: PayloadAnchor,
type_id: TypeId,
type_name: &'static str,
kind: PayloadKind,
value: Box<dyn Any>,
}
pub struct NodeRecord {
owner: AnchorId,
id: NodeId,
parent_id: Option<NodeId>,
generation: u32,
lifecycle: NodeLifecycle,
}Payload anchors back ValueSlotId, and ValueSlotId also stores the owning
slot-table storage id. Remembered values remain addressable when sibling
reordering moves the owning group in the active table, while stale cross-table
handles fail instead of aliasing another table.
§DetachedSubtree
When a branch leaves the active table, storage returns an owned subtree:
pub struct DetachedSubtree {
root_key: GroupKey,
root_scope_id: Option<ScopeId>,
groups: Vec<GroupRecord>,
payloads: Vec<PayloadRecord>,
nodes: Vec<NodeRecord>,
}Detached subtrees carry remembered payloads, anchors, scope IDs, and node identities together. The slot table itself does not decide whether they are retained or disposed.
§Core Operations
§begin_group() - Begin Group
Writers match groups only among siblings of the current parent:
pub fn begin_group(&mut self, input: BeginGroupInput<DetachedSubtree>) -> GroupStart<ActiveGroupId> {
if let Some(restored) = input.restored {
return restore_started_group(input.key, restored);
}
if expected_sibling_matches(parent, input.key) {
return GroupStartKind::Reused;
}
if let Some(found) = find_later_sibling(parent, input.key) {
move_subtree(found, insert_index);
return GroupStartKind::Moved;
}
insert_new_group(insert_index, parent, input.key);
GroupStartKind::Inserted
}There is no fixed global search budget and no recursive rescue scan into grandchildren. Large sibling ranges build a temporary sibling index inside the active writer frame.
§finish_group_body() / end_group()
At the end of a group body, the writer trims payloads and direct nodes that were not visited, detaches unvisited child subtrees, and returns them for retain-or-dispose handling:
let finish = slots.finish_group_body();
composer.handle_detached_children(parent_scope, finish.detached_children);
slots.end_group();This is where inactive branches become DetachedSubtree values. They are no longer present in
the active table after finish_group_body.
§value_slot() / remember()
Remembered state is stored in the payload table and addressed by ValueSlotId:
let slot = slots.value_slot(|| SnapshotMutableState::new(0, policy));
let state = slots.read_value::<SnapshotMutableState<i32>>(slot);If a payload slot is revisited with a different type, the old boxed value is dropped through the slot lifecycle coordinator and the new typed payload replaces it in place. Public composer-held value access uses typed value-slot handles; the old untyped composer write surface is not part of the active API.
§begin_recompose_at_scope()
Targeted recomposition starts from the indexed scope mapping:
if let Some(group) = slots.begin_recompose_at_scope(scope_id) {
// group handle resolves through scope_anchor_to_group -> anchors -> groups
}Detached scopes are intentionally absent from that index. They stay inactive until their retained subtree is explicitly restored.
§Active-Table Invariants
The slot table validates a small set of invariants after mutations in debug/test builds:
- active groups form one valid preorder forest;
- every
subtree_lenandsubtree_node_countmatches the actual active subtree; - payload and node ranges are contiguous and owner-correct;
- every active scope index entry resolves to the correct group anchor;
- retained subtree anchors are detached or invalidated, never active.
- debug stats report occupied invalidated anchor slots separately from reusable free anchor IDs for both group and payload anchor registries.
The active debug helpers are SlotTable::validate(), SlotTable::debug_snapshot(),
SlotTable::debug_dump_groups(), and SlotTable::debug_dump_slot_entries().
§Integration Points
The snapshot and slot table systems integrate at several key points:
§1. State Storage in Slots
State objects are stored in slot-table payload records and accessed through composer helpers:
composer.with_group(key, |composer| {
let state = composer.remember(|| {
SnapshotMutableState::new(0, policy)
});
let value = state.value();
});Key insight: Slot table manages where state is stored, snapshots manage what values are visible.
§2. Scope-Based Recomposition
Scopes are attached to groups during composition and later resolved through the active scope index:
let started = slots.begin_group(BeginGroupInput::new(group_key, restored));
slots.set_group_scope(started.group, scope_id);
// Later:
slots.begin_recompose_at_scope(scope_id);Snapshot integration:
// Snapshot observer tracks which scopes read which state
let observer = SnapshotStateObserver::new(|scope_id| {
invalidate_scope(scope_id);
});
snapshot.set_read_observer(Box::new(move |state_obj| {
observer.observe_read(current_scope, state_obj);
}));Flow:
- Composition reads state → observer records
(scope, state_obj)mapping - State changes → observer invalidates affected scopes
- Active scope index resolves the group anchor → recompose at that group
Detached scopes are intentionally absent from the active scope index. When a retained subtree is restored, its scope is reactivated and can re-enter normal recomposition.
§3. Invalidation Tracking
pub struct SnapshotStateObserver {
observations: HashMap<ScopeId, HashSet<StateObjectId>>,
reverse: HashMap<StateObjectId, HashSet<ScopeId>>,
}
impl SnapshotStateObserver {
pub fn observe_read(&mut self, scope: ScopeId, obj: StateObjectId) {
self.observations.entry(scope).or_default().insert(obj);
self.reverse.entry(obj).or_default().insert(scope);
}
pub fn notify_changed(&mut self, obj: StateObjectId) -> Vec<ScopeId> {
self.reverse.get(&obj).cloned().unwrap_or_default().collect()
}
}Recomposition flow:
// 1. Apply snapshot changes
snapshot.apply()?;
// 2. Get invalidated scopes
let invalid_scopes = observer.notify_changed_objects(&changed_objects);
// 3. Recompose each scope
for scope in invalid_scopes {
composer.recompose_group(scope);
}§4. Composition Context
The composition runtime coordinates slot passes, command application, and retention policy:
composition.render(root_key, || ui());
// inside:
// - SlotsHost begins a compose/recompose pass
// - SlotWriteSession mutates the active SlotTable
// - detached children become DetachedSubtree values
// - composer/host decide retain vs dispose
// - command queue applies node attach/move/remove work to the applier§Key Algorithms
§Three-Way Merge Algorithm
Used when applying snapshots with concurrent modifications:
pub fn three_way_merge<T>(
previous: &T,
current: &T,
applied: &T,
policy: &dyn MutationPolicy<T>
) -> MergeResult<T> {
// 1. No conflict case
if policy.equivalent(current, previous) {
return MergeResult::PromoteChild;
}
// 2. Identical modification case
if policy.equivalent(applied, current) {
return MergeResult::PromoteExisting;
}
// 3. Attempt custom merge
if let Some(merged) = policy.merge(previous, current, applied) {
// Check if merge equals current (no-op)
if policy.equivalent(&merged, current) {
return MergeResult::PromoteExisting;
}
return MergeResult::CommitMerged(merged);
}
// 4. Conflict
MergeResult::Conflict
}Example merges:
Structural equality (integers):
previous: 10
current: 15 (another snapshot wrote this)
applied: 20 (our snapshot wrote this)
merge: Cannot merge conflicting integers → ConflictSet merge (additive):
previous: {A, B}
current: {A, B, C} (another snapshot added C)
applied: {A, B, D} (our snapshot added D)
merge: {A, B, C, D} (union) → CommitMergedList merge (operational transform):
previous: ["a", "b", "c"]
current: ["a", "x", "b", "c"] (inserted "x" at 1)
applied: ["a", "b", "c", "y"] (appended "y")
merge: ["a", "x", "b", "c", "y"] (apply both ops) → CommitMerged§Sibling Matching and Movement
The writer only matches direct siblings under the current parent:
pub fn begin_group(&mut self, input: BeginGroupInput<DetachedSubtree>) -> GroupStart<ActiveGroupId> {
if let Some(restored) = input.restored {
return restore_started_group(input.key, restored);
}
if expected_sibling_matches(parent, input.key) {
return GroupStartKind::Reused;
}
if let Some(found) = find_later_sibling(parent, input.key) {
move_subtree(found, insert_index);
return GroupStartKind::Moved;
}
insert_new_group(insert_index, parent, input.key);
GroupStartKind::Inserted
}Why it matters:
- the search is parent-bounded;
- grandchildren are never treated as sibling matches;
- retention is not mixed into sibling search;
- the semantics depend on exact keys, not rescue budgets.
§Detach and Restore
Conditional structure changes become explicit subtree extraction and reinsertion:
pub fn detach_subtree(&mut self, anchor: AnchorId) -> DetachedSubtree {
let groups = drain_group_range(root_index, subtree_len);
let payloads = detach_payloads_for_groups(root_index, &mut groups);
let nodes = detach_nodes_for_groups(root_index, &mut groups);
clear_group_indexes(&groups);
clear_scope_index_for_groups(&groups);
DetachedSubtree { groups, payloads, nodes, .. }
}
pub fn restore_subtree(&mut self, insert_index: usize, subtree: DetachedSubtree) -> AnchorId {
restore_payloads_for_groups(insert_index, &mut groups, subtree.payloads);
restore_nodes_for_groups(insert_index, &mut groups, subtree.nodes);
groups.splice(insert_index..insert_index, subtree.groups);
recompute_all_metadata();
}Why it matters:
- removed structure is no longer present in the active table;
- retained state is explicit and owner-controlled;
- restoring a retained subtree preserves remembered payloads, scopes, and node identities.
§Design Patterns
§Persistent/Immutable Data Structures (NOT True CoW)
Used in: SnapshotIdSet
IMPORTANT CLARIFICATION: The documentation claims “CoW” but this is NOT true copy-on-write. It’s actually a persistent/immutable data structure with partial optimization.
Actual Implementation:
pub struct SnapshotIdSet {
upper_set: u64, // Bit set (cheap to copy)
lower_set: u64, // Bit set (cheap to copy)
lower_bound: usize, // Cheap to copy
below_bound: Option<Box<[SnapshotId]>>, // FULL COPY on clone!
}
impl SnapshotIdSet {
pub fn set(&self, id: SnapshotId) -> Self {
// Returns NEW instance
Self {
upper_set: self.upper_set,
lower_set: self.lower_set | mask,
below_bound: self.below_bound.clone(), // ⚠️ Box::clone() = full array copy!
}
}
}Usage Pattern (3 clones per snapshot!):
// global.rs:141-143
let mut parent_invalid = self.state.invalid.borrow().clone(); // Clone 1
parent_invalid = parent_invalid.set(new_id); // Clone 2
self.state.invalid.replace(parent_invalid.clone()); // Clone 3What’s Actually Happening:
- ✅ Immutable: Can’t modify in place (functional correctness)
- ✅ Fast for recent IDs: Only bit operations, no allocation
- ❌ NOT true CoW:
Box::clone()does full array copy - ❌ Suboptimal: Could use
Arc<[SnapshotId]>for O(1) sharing
True CoW Would Be:
below_bound: Option<Arc<[SnapshotId]>>, // Share via Arc
// .clone() would just bump refcount, no array copyReal-World Impact:
- Best case (all recent IDs): 24 bytes copied, very fast ✅
- Worst case (100 old IDs): ~2.4 KB copied per snapshot creation ⚠️
- Not dead code: Works correctly, just not optimally
Why It Works Despite Not Being True CoW:
- Most snapshot IDs are recent (fit in bit sets)
below_boundarray is typically small or empty- Correctness > performance (for now)
§Object Pool
Used in: StateRecord reuse
Pattern:
// Mark object as reusable
record.snapshot_id.set(INVALID_SNAPSHOT);
// Reuse later
if record.snapshot_id.get() == INVALID_SNAPSHOT {
record.snapshot_id.set(new_id);
record.value.write() = new_value;
return record;
}Benefits:
- Reduces allocation pressure
- Maintains stable Arc pointers
- Amortizes allocation cost
§Observer Pattern
Used in: Snapshot read/write tracking, invalidation
Pattern:
pub trait Snapshot {
fn set_read_observer(&self, observer: Box<dyn Fn(&dyn StateObject)>);
fn set_write_observer(&self, observer: Box<dyn Fn(&dyn StateObject)>);
}
// Usage
snapshot.set_read_observer(Box::new(|obj| {
println!("Read: {:?}", obj.id());
invalidation_tracker.record_read(current_scope, obj);
}));Benefits:
- Decouple observation from core logic
- Enable multiple observation strategies
- Support transparent snapshots
§Strategy Pattern
Used in: MutationPolicy, slot write sessions
Pattern:
pub trait MutationPolicy<T> {
fn equivalent(&self, a: &T, b: &T) -> bool;
fn merge(&self, previous: &T, current: &T, applied: &T) -> Option<T>;
}
// Implementations
pub struct StructuralEqualityPolicy<T>(PhantomData<T>);
pub struct ReferentialEqualityPolicy<T>(PhantomData<T>);
pub struct NeverEqualPolicy<T>(PhantomData<T>);Benefits:
- Customize state comparison logic
- Different merge strategies per type
- Extensible without modifying core
§Writer Frame Pattern
Used in: Slot table composition and recomposition sessions
Pattern:
pub(crate) struct SlotWriteSessionState {
root: RootFrame,
group_stack: Vec<GroupFrame>,
}
pub(in crate::slot) struct GroupFrame {
group_anchor: AnchorId,
old_children: Vec<AnchorId>,
old_cursor: usize,
next_child_index: usize,
payload_cursor: usize,
node_cursor: usize,
}Benefits:
- Traversal state is scoped to the active writer session instead of living inside table storage
- Group reuse, movement, and restoration operate against sibling lists and anchors
- Composition code works through semantic
begin_group/finish_group_body/end_groupoperations
§Performance Characteristics
§Snapshot System
| Operation | Time Complexity | Notes |
|---|---|---|
| Create snapshot | O(1) amortized | Allocate ID, copy open set |
| Read state | O(R) | R = record chain length, typically small |
| Write state | O(1) amortized | Reuse or prepend record |
| Apply snapshot | O(M × R) | M = modified objects, R = record chain |
| GC record cleanup | O(R) | Per state object |
| SnapshotIdSet get | O(1) recent, O(log N) old | Recent = last 128 IDs |
| SnapshotIdSet set | O(1) recent, O(N) old | Copy-on-write |
Optimization opportunities:
- Keep record chains short via aggressive GC
- Use read-only snapshots when possible (no tracking overhead)
- Batch apply operations
- Use ReferentialEqualityPolicy for cheap equality checks
§Slot Table System
| Operation | Time Complexity | Notes |
|---|---|---|
begin_group() reuse | O(1) | Expected sibling already matches |
begin_group() sibling search | O(D) | D = number of direct siblings examined |
move_subtree() | O(G + P + N + T) | moved groups, payloads, nodes, and suffix metadata shifts |
finish_group_body() | O(R + C) | trims direct payload/node tails and detaches remaining child subtrees |
detach_subtree() | O(G + P + N + T) | extracts subtree records and repairs active indexes |
restore_subtree() | O(G + P + N + T) | reinserts subtree records and recomputes metadata |
value_slot() / read_value() | O(1) | payload anchor lookup plus owner-relative offset |
begin_recompose_at_scope() | O(1) | scope index -> anchor -> active group |
validate() | O(G + P + N + A + S) | full structural check in debug/test builds |
Optimization opportunities:
- Reduce temporary
Veccloning in detach/retention hot paths - Profile subtree
Vec::drain/Vec::splicecosts before changing storage layout - Add retained-memory instrumentation before pursuing more complex backends
- Keep validation strong while optimizing
§Memory Usage
Snapshot system:
- Each StateRecord: ~64 bytes (Arc, Cell, RwLock overhead)
- SnapshotIdSet: 24 bytes + 8 bytes per old ID
- MutableSnapshot: ~200 bytes + modified map
Slot table:
- Group storage, payload storage, and node storage scale independently
- Anchor and scope indexes add hash-map overhead on top of active records
- Retained branches consume separate detached subtree allocations while inactive
Scaling:
- 10,000 UI elements no longer imply one flat slot array
- 1,000 state objects with 10 records each: ~640 KB
- Typical app: 1-10 MB for composition runtime
§Common Scenarios
§Scenario 1: Simple State Update
// 1. Create state
let state = SnapshotMutableState::new(0, StructuralEqualityPolicy::new());
// 2. Read in current snapshot
let value = state.read(¤t_snapshot); // Returns 0
// 3. Create mutable snapshot
let snapshot = take_mutable_snapshot();
// 4. Write in snapshot
state.write(&snapshot, 42);
// 5. Apply snapshot
snapshot.apply()?; // Merge into global
// 6. Read new value
let new_value = state.read(¤t_snapshot); // Returns 42Internals:
- State has single record:
[id=1, value=0] - Write creates new record:
[id=2, value=42] → [id=1, value=0] - Apply promotes child record to global visibility
- Global snapshot now sees
id=2as valid
§Scenario 2: Conditional Rendering (Tabs)
// Initial composition - Tab 1 active
composer.with_group(TAB_GROUP, |composer| {
composer.cranpose_with_reuse(TAB_1, RecomposeOptions::default(), |composer| {
// ... tab 1 content ...
});
});
// Hide Tab 1
composer.with_group(TAB_GROUP, |_composer| {
// tab 1 branch omitted
});
// Result:
// - finish_group_body() detaches Tab 1 as DetachedSubtree
// - retain policy keeps it outside the active SlotTable
// - its remembered payloads, scopes, and node IDs stay owned by the detached subtree
// Show Tab 1 again
composer.with_group(TAB_GROUP, |composer| {
composer.cranpose_with_reuse(TAB_1, RecomposeOptions::default(), |composer| {
// ... tab 1 content restored from DetachedSubtree ...
});
});Key benefit: Tab 1’s state is preserved by an explicit retained subtree, not by hidden gap metadata in the active table.
§Scenario 3: Concurrent Snapshot Conflict
// t0: Initial state
let state = SnapshotMutableState::new(10);
// t1: Create two snapshots
let snapshot1 = take_mutable_snapshot(); // base_parent_id = 1
let snapshot2 = take_mutable_snapshot(); // base_parent_id = 1
// t2: Snapshot1 writes
state.write(&snapshot1, 20);
// t3: Snapshot2 writes (concurrent)
state.write(&snapshot2, 30);
// t4: Snapshot1 applies first
snapshot1.apply()?; // Success, now global = 20
// t5: Snapshot2 tries to apply
let result = snapshot2.apply();
// Conflict detected: last_write (snapshot1) != base_parent_id (global before)
// Merge attempt: previous=10, current=20, applied=30
// StructuralEqualityPolicy cannot merge integers
// Result: SnapshotApplyResult::FailureHandling conflicts:
loop {
let snapshot = take_mutable_snapshot();
// Perform modifications
state.write(&snapshot, new_value);
// Try to apply
match snapshot.apply() {
SnapshotApplyResult::Success => break,
SnapshotApplyResult::Failure => {
// Retry with fresh snapshot
continue;
}
}
}§Scenario 4: Nested Snapshots (Transaction-like)
let outer = take_mutable_snapshot();
// Modify state
state1.write(&outer, 10);
{
let inner = outer.take_nested_mutable_snapshot();
// Inner can see outer's changes
assert_eq!(state1.read(&inner), 10);
// Inner modifications
state2.write(&inner, 20);
// Apply inner to outer (not global yet)
inner.apply()?;
}
// Outer can now see inner's changes
assert_eq!(state2.read(&outer), 20);
// Apply outer to global
outer.apply()?;
// Both changes now visible globally
assert_eq!(state1.read(&global_snapshot), 10);
assert_eq!(state2.read(&global_snapshot), 20);Use case: Atomic multi-state updates, rollback on failure.
§Future Optimizations
§Snapshot System
- Persistent Data Structures: Replace record chains with persistent trees for O(log N) all operations
- Lock-Free Records: Use atomic operations instead of RwLock for high-contention scenarios
- Compressed ID Sets: Use roaring bitmaps for very large snapshot ID sets
- Lazy GC: Defer record cleanup to background thread
§Slot Table System
- Chunked subtree storage: Replace hot
Vec::drain/Vec::splicepaths only if profiling proves they dominate. - Denser group storage: Pack
GroupRecordfields or split arrays only if cache pressure matters in real traces. - Retained-memory diagnostics: Add stronger retained-subtree and anchor-capacity telemetry for leak hunting.
- Parallel recomposition: Only after current invariants, retention semantics, and applier-side node ownership stay deterministic.
§Debugging Tips
§Snapshot Debugging
View record chain:
fn debug_record_chain(state: &SnapshotMutableState<T>) {
let head = state.head.read();
let mut current = head.clone();
loop {
println!("Record {{ id: {}, tombstone: {}, value: {:?} }}",
current.snapshot_id.get(),
current.tombstone.get(),
current.value.read().as_ref().map(|v| format!("{:?}", v))
);
match current.next.get() {
Some(next) => current = next,
None => break,
}
}
}Check snapshot visibility:
fn is_visible_to_snapshot(
record_id: SnapshotId,
snapshot_id: SnapshotId,
invalid: &SnapshotIdSet
) -> bool {
record_id <= snapshot_id && !invalid.get(record_id)
}§Slot Table Debugging
Dump the active slot table:
fn debug_print_slots(composition: &Composition) {
for entry in composition.debug_dump_slot_entries() {
println!("{}: {}", entry.path, entry.line);
}
}Inspect structured debug state:
fn debug_snapshot(composition: &Composition) {
let snapshot = composition.debug_slot_snapshot();
println!("{snapshot:#?}");
}Force validation in debug/test paths:
assert_eq!(slot_table.validate(), Ok(()));Enable automatic pass dumps:
COMPOSE_DEBUG_SLOT_TABLE=1 cargo test -p cranpose-core slot::tests§Summary
The Snapshots and Slot Table system provides a sophisticated foundation for cranpose:
Snapshots deliver:
- Isolated state views via MVCC
- Optimistic concurrency with conflict detection
- Flexible merge strategies
- Efficient garbage collection
Slot Tables deliver:
- Exact active-tree storage with separate payload and node tables
- Stable anchors and indexed scopes for targeted recomposition
- Explicit detached-subtree retention instead of semantic gaps
- Strong validation and debug snapshots for structural correctness
Together they enable:
- Predictable recomposition
- State preservation across structural changes
- Concurrent snapshot modifications
- High-performance UI updates
This design mirrors Jetpack Compose’s battle-tested architecture while leveraging Rust’s ownership model for memory safety and performance.
Re-exports§
pub extern crate self as cranpose_core;
Re-exports§
pub use concurrency::CollectEvents;pub use concurrency::CoroutineScope;pub use concurrency::Delay;pub use concurrency::EventChannel;pub use concurrency::EventSender;pub use concurrency::EventStream;pub use concurrency::EventStreamNext;pub use concurrency::ProduceScope;pub use concurrency::collectAsState;pub use concurrency::delay;pub use concurrency::interval;pub use concurrency::launchBlocking;pub use concurrency::produceState;pub use concurrency::rememberCoroutineScope;pub use concurrency::rememberEventStream;pub use concurrency::spawn_ui_task;pub use concurrency::withBlocking;pub use owned::Owned;pub use platform::Clock;pub use platform::RuntimeScheduler;pub use platform::SchedulerRef;pub use platform::scheduler_ref;pub use subcompose::ContentTypeReusePolicy;pub use subcompose::DefaultSlotReusePolicy;pub use subcompose::SlotId;pub use subcompose::SlotReusePolicy;pub use subcompose::SubcomposeState;pub use composer_context::note_nested_slots_host;pub use composer_context::with_composer as with_current_composer;pub use test_scratch::test_scratch_dir;
Modules§
- collections
- composer_
context - concurrency
- Composition-scoped structured concurrency.
- env_
flags - Cached reads of the
CRANPOSE_*diagnostic environment variables. - hash
- owned
- platform
- Platform abstraction traits for Compose runtime services.
- runtime
- snapshot_
double_ index_ heap - snapshot_
id_ set - snapshot_
pinning - snapshot_
state_ observer - snapshot_
v2 - Snapshot system for managing isolated state changes.
- subcompose
- State tracking for measure-time subcomposition.
- test_
scratch - Where a test writes real files. Behind
test-helpersso only a test build of the workspace carries it. Where a test writes real files.
Macros§
- Disposable
Effect - Launched
Effect - Launched
Effect Async - clone_
captures - env_
flag - Reads a presence-style environment switch once and caches the answer.
- env_
threshold_ ms - Reads a millisecond-threshold environment variable once and caches it.
Structs§
- Anchor
Id - Stable identifier for a slot in the slot table.
- Applier
Guard - Branch
Group Guard - Callback
Holder - Callback
Holder1 - CallbackHolder1 keeps the latest single-argument callback closure alive across recompositions.
It mirrors
CallbackHolderbut supports callbacks that receive one argument. - Cancel
Token - Cooperative cancellation token passed into background
LaunchedEffectwork. - Captured
Composition Context - The composition context inherited by work that is composed in another slot host. Besides composition locals, this carries the source owner scope so a secondary tree cannot outlive the composition that supplied its callbacks.
- Composer
- Composition
- Composition
Local - Composition
Pass Debug Stats - Concrete
Applier Host - Disposable
Effect Result - Disposable
Effect Scope - Event
Handler Scope Guard - Launched
Effect Scope - Memory
Applier - Memory
Applier Debug Stats - Mutable
State - Cheap copyable mutable view of a state cell.
- Owned
Mutable State - Owning state handle for reclaimable state cells.
- Param
Slot - ParamSlot holds function/closure parameters by ownership (no PartialEq/Clone required).
Used by the
#[composable]macro to store Fn-like parameters in the slot table. - Param
State - Provided
Value - Recompose
Options - Recompose
Scope - Recompose
Scope Registry Debug Stats - Recycled
Node - Recycled
Node Insertion - Retention
Budget - Retention
Policy - Return
Slot - Slot
Debug Anchor - Slot
Debug Entry - Slot
Debug Group - Slot
Debug Scope - Slot
Debug Snapshot - Slot
Retention Debug Stats - Slot
Table - Slot
Table Debug Stats - Slot
Table Local Debug Stats - Slot
Table Mutation Debug Stats - Slots
Host - Snapshot
State List - Snapshot
State Map - State
- Cheap copyable read-only view of a state cell.
- Static
Composition Local - A
StaticCompositionLocalis a CompositionLocal that is optimized for values that are unlikely to change. UnlikeCompositionLocal, reads of aStaticCompositionLocalare not tracked by the recomposition system, which means: - Task
Site - Where an effect was written, carried onto the task it spawns.
- Value
Slot Handle
Enums§
Constants§
- ROOT_
RENDER_ REPLAY_ LIMIT - Upper bound on chained root-render replays and scope-recomposition rounds.
Traits§
Functions§
- Composition
Local Provider - Side
Effect - __
disposable_ effect_ impl - __
launched_ effect_ async_ impl siteis where the effect was written. It travels onto the task the effect spawns, so a task the runtime is still holding says which effect started it.- __
launched_ effect_ impl - bubble_
layout_ dirty - Unified API for bubbling layout dirty flags from a node to the root (Applier context).
- bubble_
layout_ dirty_ in_ composer - Unified API for bubbling layout dirty flags from a node to the root (Composer context).
- bubble_
measure_ dirty - Unified API for bubbling measure dirty flags from a node to the root (Applier context).
- bubble_
measure_ dirty_ in_ composer - Unified API for bubbling measure dirty flags from a node to the root during composition.
- bubble_
semantics_ dirty - Unified API for bubbling semantics dirty flags from a node to the root (Applier context).
- bubble_
semantics_ dirty_ in_ composer - Unified API for bubbling semantics dirty flags from a node to the root (Composer context).
- composition
Local Of - composition
Local OfWith Policy - derived
State Of - dispatch_
ui_ event - Dispatches a UI event in a proper snapshot context.
- enter_
event_ handler_ scope - in_
applied_ snapshot - Returns true if currently in an applied snapshot context.
- in_
event_ handler - Returns true if currently in an event handler context.
- location_
key - mutable
State List - mutable
State List Of - mutable
State Map - mutable
State MapOf - mutable
State Of - Creates a new
MutableStateinitialized with the given value. - owned
Mutable State Of - pop_
parent - push_
parent - queue_
semantics_ invalidation - Schedules semantics bubbling for a node using the active composer if present.
- remember
- remember
Keyed - Like
remember, but recomputes wheneverkeychanges. - remember
Mutable State Of - A composable hook that creates and remembers a
MutableState. - remember
Mutable State OfNever Equal - remember
Updated State - Returns a
MutableStatethat always holds the latest value. - run_
in_ mutable_ snapshot - Runs the provided closure inside a mutable snapshot and applies the result.
- static
Composition Local Of - try_
mutable State Of - Like
mutableStateOfbut returnsNoneif no runtime is available. - with
Current Composer - with_
key - with_
node_ mut