state-tree

A state tree utility library that provides functionality for preserving and managing internal DSP (Digital Signal Processing) state between two different compiled source codes.

Overview

In mimium, to implement hot-reload functionality, it's necessary to transfer the state of compiled code (delay line buffers, memory values, feedback values, etc.) to newly compiled code. This crate provides a mechanism for efficiently migrating data from an old state tree to a new state tree.

Key Features

1. State Tree Representation (`tree` module)

StateTree - A data structure for hierarchically representing DSP internal state

Delay: Represents delay lines (read index, write index, buffer data)
Mem: Memory nodes (list of values)
Feed: Feedback values (control signals, etc.)
FnCall: Function call nodes with multiple child nodes

StateTreeSkeleton - Type-safe representation of state tree "structure"

Holds only size information for each node, not actual values
Used to define what the new code structure will look like
Generic type T: SizedType specifies how to calculate size for each node

2. Diff Detection (`tree_diff` module)

take_diff - Detects differences between old and new trees

Diff detection algorithm:

Uses Longest Common Subsequence (LCS) algorithm to detect correspondence between nodes
Matches nodes by verifying they are the "same type" and "same size"
Identifies inserted, deleted, and shared nodes

Detection results are returned as a list of CopyFromPatch

3. Patch Application (`patch` module)

CopyFromPatch - Instructions for copying data from old tree to new tree

old_path: Path (array of indices) indicating node position in the old tree
new_path: Path (array of indices) indicating node position in the new tree

apply_patches - Applies patches to transfer old data to the new tree

Copies data from corresponding nodes in the old tree to the new tree
Appropriately copies Delay's readidx/writeidx and Mem/Feed data

4. State Storage Update (`lib.rs`)

update_state_storage - Integrated update function

pub fn update_state_storage<T: SizedType + PartialEq>(
    old: &[u64],                              // Flattened binary representation of old state
    old_state_skeleton: StateTreeSkeleton<T>, // Old structure
    new_state_skeleton: StateTreeSkeleton<T>, // New structure
) -> Result<Option<Vec<u64>>, Box<dyn std::error::Error>>

Processing flow:

Deserialize old binary data with old structure
Create an empty tree with new structure
Detect differences (take_diff)
Apply patches (apply_patches)
Serialize the new tree to binary and return

Returns None if the structure hasn't changed (optimization)

Usage Examples

Basic Usage

use state_tree::{update_state_storage, tree::*};

// Hold old state in binary
let old_state_bytes: Vec<u64> = vec![/* ... */];

// Structure obtained from old compilation result
let old_skeleton = StateTreeSkeleton::FnCall(vec![
    Box::new(StateTreeSkeleton::Delay { len: 2 }),
    Box::new(StateTreeSkeleton::Mem(SizeInfo { size: 100 })),
]);

// Structure of newly compiled code
let new_skeleton = StateTreeSkeleton::FnCall(vec![
    Box::new(StateTreeSkeleton::Mem(SizeInfo { size: 100 })),  // Order changed
    Box::new(StateTreeSkeleton::Delay { len: 2 }),
    Box::new(StateTreeSkeleton::Feed(SizeInfo { size: 1 })),   // Newly added
]);

// Adapt state to new structure
match update_state_storage(&old_state_bytes, &old_skeleton, &new_skeleton) {
    Ok(Some(new_state_bytes)) => {
        // Use state adapted to new structure
    }
    Ok(None) => {
        // Structure hasn't changed
    }
    Err(e) => {
        // Error handling
    }
}

Implementation Details

Serialization/Deserialization

serialize_tree_untagged: Flattens StateTree to Vec<u64>
- Does not include tag information (structure information managed separately by skeleton)
- Efficient memory usage
deserialize_tree_untagged: Restores Vec<u64> to StateTree using skeleton

Node Matching Strategy

By using the LCS algorithm:

Handles node reordering
Automatically detects node insertion/deletion
Minimizes data transfer between corresponding nodes

Path Specification

Access to each node is specified by path (array of indices):

old_path: [2, 1, 0]  // Child [2] → its child [1] → its child [0]

Testing

Unit Tests (`tests/diff.rs`)

Simple diff detection
Node insertion/deletion
LCS algorithm correctness

Integration Tests (`tests/end2end.rs`)

Node reordering
Complex structure changes
Integration of serialization/deserialization and diff application

Design Considerations

Performance

LCS algorithm has $O(mn)$ time complexity (m, n are node counts)
Practical for actual DSP structures which typically have few nodes

Type Safety

SizedType trait generalizes size calculation for each node
Representing skeleton as types reduces runtime type mismatch errors

Error Handling

Returns Result on deserialization failure
Panics on invalid path specification during patch application (validated with debug_assert)

Related Modules

crates/lib/mimium-lang: Main lang crate. Uses state-tree as part of language processing
plugins/mimium-scheduler: Requires state management for scheduling functionality

License

Follows the common license of the workspace Ï

state-tree 3.1.2