# 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 delta `D` to mutate their state in-place.
* **`Diff<D>`** — implemented by types that can compute a delta `D` relative to an initial state (requires `Patch<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
| `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`
```rust
use deltapatcher::{Diff, Patch};
let start = vec![1, 2, 3, 4, 5];
let end = vec![1, 9, 3, 4, 10, 5];
// Compute the delta from `start` to `end`
let delta = end.diff(&start);
// Apply it to a different starting state
let mut other = start.clone();
other.patch(&delta);
assert_eq!(other, end);
```
### 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`:
```rust
let a_to_b = b.diff(&a);
let b_to_c = c.diff(&b);
let mut a_to_c = a_to_b;
a_to_c.aggregate_owned(b_to_c);
let mut result = a.clone();
result.patch(&a_to_c);
assert_eq!(result, c);
```
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 for `Vec<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 the `WrappingArithmetic` trait gets `Patch<ArithmeticDelta<Self>>` and `Diff<ArithmeticDelta<Self>>` impls for free.
Full API details on [docs.rs](https://docs.rs/deltapatcher).
## 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.
```toml
# Cargo.toml
[dependencies]
deltapatcher = { version = "*", features = ["macros"] }
```
### Full `Diff` + `Patch` Derive
Deriving `Diff` auto-generates the delta type along with `Delta`, `Patch`, and `Diff` implementations:
```rust
use deltapatcher::{Diff, delta::ArithmeticDelta, delta::SliceDelta};
#[derive(Diff, Debug, Clone, Copy)]
#[deltapatcher(
delta_name = PosDelta, // optional: override the generated type name
delta_derive(Debug, Clone), // optional: derives to add to the generated type
)]
struct Position {
#[deltapatcher(delta_ty = ArithmeticDelta<i32>)]
x: i32,
#[deltapatcher(delta_ty = ArithmeticDelta<i32>)]
y: i32,
}
#[derive(Diff, Debug, Clone)]
enum State {
A {
#[deltapatcher(delta_ty = ArithmeticDelta<u32>)]
foo: u32,
#[deltapatcher(delta_ty = ArithmeticDelta<i32>)]
bar: i32,
},
B(
#[deltapatcher(delta_ty = SliceDelta<u8>)]
Vec<u8>
),
C,
}
```
### `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:
```rust
use deltapatcher::{Patch, delta::ArithmeticDelta};
#[derive(Patch, Debug, Clone)]
#[deltapatcher(delta_name = ClientStateDelta, delta_derive(Debug, Clone))]
struct ClientState {
#[deltapatcher(delta_ty = ArithmeticDelta<i32>)]
score: i32,
#[deltapatcher(delta_ty = ArithmeticDelta<u32>)]
level: u32,
}
```
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](https://docs.rs/deltapatcher).
### 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:
```rust
// Server: build a cached timeline from raw frames
let server_timeline = StateCachedTimeline::from_commits(
/*interval=*/ 4,
initial_frame,
raw_frames.windows(2).map(|w| Commit::new_with_default(w[1].diff(&w[0]))),
);
// Client: seek forward
let delta = server_timeline.diff_between(current_frame, target_frame).unwrap();
current_frame_data.patch(&delta);
// Client: seek backward — inverse delta calculated directly in O(interval)
let inv_delta = server_timeline.diff_between(current_frame, earlier_frame).unwrap();
current_frame_data.patch(&inv_delta);
```
See [`example/src/bin/video_stream.rs`](https://github.com/HyperCodec/deltapatcher/blob/master/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.
```rust
let mut bucket = ChangeBucket::new(IVec2 { x: 0, y: 0 });
bucket.x += 10;
if bucket.is_dirty() {
let delta: VecDelta = bucket.pop();
// process or send delta...
}
```
Additional helpers include `peek::<D>()`, `discard()`, and `checkpoint()`.
Full API details on [docs.rs](https://docs.rs/deltapatcher).
## Running the Examples
This repo uses a dedicated `example` crate with multiple binaries. Run any example with:
```shell
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 for `HashSet` / `BTreeSet`
* `BitmapDelta` — XOR-based delta for `u8`/`u32`/`u64` bitfields, useful for flag sets and masks
* `StringDelta` — character- or byte-level diff for `String` / `&str`, wrapping `SliceDelta` with 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 in `SliceDelta` entries and using varint encoding for arithmetic deltas, with the whole thing potentially exposed as a `deku`-backed implementation.
* **Reversible delta trait** — a `ReversibleDelta` trait (or an `invert()` method) so types can cheaply produce their own inverse without needing a `StateCachedTimeline` to reconstruct two states and call `diff`.
* **`#[derive(WrappingArithmetic)]`** — remove the boilerplate of implementing the trait by hand for newtype wrappers and simple structs.
* **Async / streaming timeline** — a `StreamingTimeline` adapter that yields commits as a `Stream`, targeting networked applications that push state changes in real time.
## License
Licensed under either of [MIT](https://opensource.org/license/MIT) or [Apache-2.0](https://www.apache.org/licenses/LICENSE-2.0.html) at your option.