deltapatcher
A Rust library for computing, composing, and applying deltas (diffs) between states, with built-in support for timelines, state caching, and efficient bidirectional seeking.
Overview
deltapatcher provides three core traits:
Patch<D>— implemented by types that can apply a deltaDto mutate their state in-place.Diff<D>— implemented by types that can compute a deltaDrelative to an initial state (requiresPatch<D>).Delta— implemented by delta types, allowing sequential deltas to be composed (aggregated) together.
Built-in implementations are provided for Vec<T>, slices [T], fixed-size arrays [T; N], and all primitive integer types (with more planned soon).
Features
| Feature | Description |
|---|---|
std |
Enabled by default, adding a dependency on the standard library. Remove this feature for no_std environments. |
macros |
Enables proc-macros to auto-generate many of the trait implementations from this crate. |
serde |
Enables serde::Serialize/Deserialize on all delta and timeline types |
Core Concepts
Diff and Patch
use ;
let start = vec!;
let end = vec!;
// Compute the delta from `start` to `end`
let delta = end.diff;
// Apply it to a different starting state
let mut other = start.clone;
other.patch;
assert_eq!;
Delta Aggregation
Deltas can be composed together with aggregate / aggregate_owned. An aggregated delta A → C can reproduce the final state without ever materializing the intermediate state B:
let a_to_b = b.diff;
let b_to_c = c.diff;
let mut a_to_c = a_to_b;
a_to_c.aggregate_owned;
let mut result = a.clone;
result.patch;
assert_eq!;
This is especially useful in networking scenarios (e.g. game state sync, media streaming) where you want to send a single compact delta instead of multiple incremental ones or a full snapshot.
Built-in Delta Types
SliceDelta<T>— LCS-based diff forVec<T>,[T], and[T; N]. Stores changes as a compact set of non-overlapping splice entries that can be correctly aggregated without knowing the intermediate state.ArithmeticDelta<T>— wrapping-arithmetic delta for all primitive integer types. Any type implementing theWrappingArithmetictrait getsPatch<ArithmeticDelta<Self>>andDiff<ArithmeticDelta<Self>>impls for free.
Full API details on docs.rs.
Deriving Diff and Patch
Enable the macros feature to derive Diff and Patch for your own structs and enums. Each field is annotated with the delta type it should use, and the macros generate the corresponding delta struct/enum along with its Delta, Patch, and (optionally) Diff implementations.
# Cargo.toml
[]
= { = "*", = ["macros"] }
Full Diff + Patch Derive
Deriving Diff auto-generates the delta type along with Delta, Patch, and Diff implementations:
use ;
Patch-Only Derive
Use #[derive(Patch)] when you only need to apply incoming deltas (e.g., client-side networking or read-only replicas) without compiling diffing logic:
use ;
Run cargo expand to inspect the generated code.
Timelines
Timeline<D, M> is an ordered sequence of Commit<D, M> values (delta + optional metadata). It supports aggregate queries, range merging, and state replay. StateCachedTimeline<T, D, M> wraps it with periodic state snapshots, dropping arbitrary state-retrieval and delta-query cost from O(N) to O(interval).
Full API details on docs.rs.
Real-World Example: Video Scrubbing
StateCachedTimeline maps naturally onto a video player's seek model. Each frame is a commit; the server stores periodic keyframe-equivalent cached states and can answer any seek request with a lightweight delta rather than a full snapshot:
// Server: build a cached timeline from raw frames
let server_timeline = from_commits;
// Client: seek forward
let delta = server_timeline.diff_between.unwrap;
current_frame_data.patch;
// Client: seek backward — inverse delta calculated directly in O(interval)
let inv_delta = server_timeline.diff_between.unwrap;
current_frame_data.patch;
See example/src/bin/video_stream.rs for the full runnable version.
Utilities
ChangeBucket<T> holds "old" and "new" copies of a value. Mutate new freely through DerefMut, then call pop::<D>() to extract the accumulated delta as any supported delta type and reset the baseline — useful for building pipelines that only emit commits when something actually changes.
let mut bucket = new;
bucket.x += 10;
if bucket.is_dirty
Additional helpers include peek::<D>(), discard(), and checkpoint().
Full API details on docs.rs.
Running the Examples
This repo uses a dedicated example crate with multiple binaries. Run any example with:
just run-example basic
just run-example macros
just run-example video_stream
Roadmap
-
More built-in delta types
-
MapDelta— key-level insert/remove/update entries -
SetDelta— insertion and removal sets forHashSet/BTreeSet -
BitmapDelta— XOR-based delta foru8/u32/u64bitfields, useful for flag sets and masks -
StringDelta— character- or byte-level diff forString/&str, wrappingSliceDeltawith UTF-8 awareness -
MyersSliceDelta— Myers algorithm for huge slice diffing. -
Compact / bitpacked serialization — an opt-in binary format (behind a feature flag) that encodes deltas far more densely than
serde+ any text format can. Candidates include bitpacking index and length fields inSliceDeltaentries and using varint encoding for arithmetic deltas, with the whole thing potentially exposed as adeku-backed implementation. -
Reversible delta trait — a
ReversibleDeltatrait (or aninvert()method) so types can cheaply produce their own inverse without needing aStateCachedTimelineto reconstruct two states and calldiff. -
#[derive(WrappingArithmetic)]— remove the boilerplate of implementing the trait by hand for newtype wrappers and simple structs. -
Async / streaming timeline — a
StreamingTimelineadapter that yields commits as aStream, targeting networked applications that push state changes in real time.
License
Licensed under either of MIT or Apache-2.0 at your option.