1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
//! A library for computing, composing, and applying **deltas** between states.
//!
//! # 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 produce a delta `D` relative to an initial state (requires [`Patch<D>`]).
//! - [`Delta`] — implemented by the delta type itself; the key operation is
//! `aggregate`, which composes two consecutive deltas into one. An aggregated `A → C` delta
//! lets you reproduce the final state without ever materialising the intermediate `B`.
//!
//! # Built-in Implementations
//!
//! | Type | Delta | Notes |
//! |---|---|---|
//! | `Vec<T>`, `[T]`, `[T; N]` | [`SliceDelta<T>`][delta::SliceDelta] | LCS-based splice diff |
//! | `u8`, `i8`, … `u64`, `i64` | [`ArithmeticDelta<T>`][delta::ArithmeticDelta] | Wrapping addition; any type implementing [`WrappingArithmetic`][delta::WrappingArithmetic] gets this for free |
//!
//! # Macros
//!
//! When the `macros` feature is enabled, procedural macros auto-generate delta types and trait implementations for your custom structs and enums:
//!
//! - [`#[derive(Diff)]`][Diff] — derives both `Diff` and `Patch` for full bidirectional diffing and patching.
//! - [`#[derive(Patch)]`][Patch] — derives only `Patch` (skipping diff generation), ideal for client-side state receivers or read-only replicas.
//!
//! # Timelines
//!
//! [`Timeline<D, M>`][timeline::Timeline] stores an ordered sequence of
//! [`Commit<D, M>`][timeline::Commit] values and supports aggregate queries, range merging, and
//! state replay.
//!
//! [`StateCachedTimeline<T, D, M>`][timeline::StateCachedTimeline] adds periodic state
//! snapshots at a configurable interval, reducing arbitrary state-retrieval and delta-query
//! cost from `O(N)` to `O(interval)`. It also supports efficient **bidirectional** seeking via
//! [`delta_between`][timeline::StateCachedTimeline::delta_between] — the same call handles both
//! forward and inverse (backward) deltas.
//!
//! # Utilities
//!
//! [`ChangeBucket<T>`][util::ChangeBucket] holds "old" and "new" copies of a value.
//! Mutate `new` freely through `DerefMut`, then call `pop()` to extract the accumulated delta and reset the
//! baseline — handy for pipelines that only want to emit a commit when something actually
//! changed.
//!
//! # Feature Flags
//!
//! | Feature | Description |
//! |---|---|
//! | `std` | Enabled by default, adding a dependency on the standard library. Remove this feature for `no_std` environments. |
//! | `alloc` | Enabled by default, linking the `alloc` crate. This is required for timelines and allocating deltas such as `SliceDelta`.
//! | `macros` | Enables proc-macros to auto-generate many of the trait implementations from this crate. |
//! | `serde` | Derives `serde::Serialize`/`Deserialize` on all delta and timeline types |
pub use deltapatcher_macros as macros;
pub use ;
extern crate alloc;
/// Trait for types that can compute the difference (delta)
/// relative to another state of the same type.
///
/// `Diff` represents the generator side of diff patching.
/// Calling `b.diff(&a)` calculates the delta needed to transform `a` into `b`.
///
/// The delta type `D` is **not** required to implement [`Delta`]. `Diff` and
/// [`Patch`] are general-purpose, auxiliary traits: a delta type that only
/// needs to be produced and applied (for example, a single-use-case delta used
/// internally) can implement them without also supporting aggregation. Delta
/// types that implement [`Delta`] are the "complete" deltas that can be used by
/// downstream utilities which need to compose changes.
///
/// # Contract
///
/// **Round-Trip Invariant**: If a type `T` implements both [`Diff<D>`] and [`Patch<D>`], the following identity
/// should hold for any states `a` and `b`:
///
/// ```rust,ignore
/// let mut state = a.clone();
/// let delta = b.diff(&a);
/// state.patch(&delta);
/// assert_eq!(state, b);
/// ```
///
/// In order to help enforce this invariant, it is required that all types capable
/// of producing a delta (i.e. types implementing [`Diff`]) must also be capable of
/// consuming the same type of delta (via [`Patch`]).
///
/// # Examples
///
/// ```rust
/// use deltapatcher::{Diff, Patch, delta::ArithmeticDelta};
///
/// let start = 10i32;
/// let target = 25i32;
/// let delta = target.diff(&start);
/// assert_eq!(delta, ArithmeticDelta(15));
/// ```
/// Trait for types that can be updated in-place by applying a delta.
///
/// `Patch` represents the consumption side of differential patching. A type
/// implementing [`Patch<D>`] can mutate its state using a delta `D`, without
/// requiring the capability to compute diffs itself.
///
/// The delta type `D` is **not** required to implement [`Delta`]; see the
/// [`Diff`] docs for the rationale.
///
/// # Examples
///
/// ```rust
/// use deltapatcher::{Patch, delta::ArithmeticDelta};
///
/// let mut value = 10i32;
/// value.patch(&ArithmeticDelta(5));
/// assert_eq!(value, 15);
/// ```
/// A value that encodes the change between two states and can be composed
/// with other deltas of the same type.
///
/// A delta is always expressed relative to the state *immediately before* it
/// is applied. Composing two deltas with [`aggregate`][Delta::aggregate]
/// produces a single delta that skips the intermediate state entirely —
/// useful for compressing a sequence of changes before sending them over the
/// network or storing them in a timeline.
///
/// `Delta` is deliberately independent of [`Diff`] and [`Patch`]: those traits
/// work with any delta type, whether or not it supports aggregation. Implement
/// `Delta` only for delta types that should be fully composable and usable by
/// downstream utilities (such as timelines) that need to aggregate changes.
///
/// # Contract
///
/// Aggregation must be **associative**: aggregating `(A→B)` with `(B→C)` and
/// then with `(C→D)` must produce the same result as aggregating `(A→B)` with
/// the pre-aggregated `(B→D)`.
///
/// # Implementing `Delta`
///
/// You typically pair `Delta` with [`Diff`] and [`Patch`] impls on the state
/// type, but this is not required. The only required method is
/// [`aggregate`][Delta::aggregate]; [`aggregate_owned`][Delta::aggregate_owned]
/// has a default implementation that simply borrows its argument, but you
/// should override it whenever moving the data is cheaper than cloning.
///
/// ```rust
/// use deltapatcher::Delta;
///
/// /// A delta for a simple counter: just the signed difference.
/// #[derive(Clone, Copy)]
/// struct CounterDelta(i64);
///
/// impl Delta for CounterDelta {
/// fn aggregate(&mut self, next: &Self) {
/// self.0 += next.0;
/// }
/// }
/// ```
///
/// # Example: composing deltas to skip an intermediate state
///
/// ```rust
/// use deltapatcher::{Delta, Patch, Diff};
///
/// let a = vec![1i32, 2, 3];
/// let b = vec![1i32, 9, 3]; // A → B
/// let c = vec![1i32, 9, 3, 4]; // B → C
///
/// let mut a_to_b = b.diff(&a);
/// let b_to_c = c.diff(&b);
///
/// // Compose into a single A → C delta — `b` is never needed again.
/// a_to_b.aggregate_owned(b_to_c);
///
/// let mut result = a.clone();
/// result.patch(&a_to_b);
/// assert_eq!(result, c);
/// ```
///
/// # See also
///
/// - [`Diff`] — the trait for types that *produce* deltas.
/// - [`Patch`] — the trait for types that *consume* deltas.
/// - [`delta`] — module containing builtin delta types.