tirea_state/
patch.rs

1//! Patch containers for grouping operations.
2//!
3//! A `Patch` is a collection of operations that can be applied atomically
4//! to a JSON document. `TrackedPatch` adds metadata for debugging and auditing.
5
6use crate::Op;
7use serde::{Deserialize, Serialize};
8
9/// A collection of operations to apply atomically.
10///
11/// Patches are the primary way to describe changes to a document.
12/// Operations are applied in order.
13///
14/// # Examples
15///
16/// ```
17/// use tirea_state::{Patch, Op, path};
18/// use serde_json::json;
19///
20/// let patch = Patch::new()
21///     .with_op(Op::set(path!("name"), json!("Alice")))
22///     .with_op(Op::set(path!("age"), json!(30)));
23///
24/// assert_eq!(patch.len(), 2);
25/// ```
26#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
27pub struct Patch {
28    /// The operations in this patch.
29    ops: Vec<Op>,
30}
31
32impl Patch {
33    /// Create an empty patch.
34    #[inline]
35    pub fn new() -> Self {
36        Self::default()
37    }
38
39    /// Create a patch with the given operations.
40    #[inline]
41    pub fn with_ops(ops: Vec<Op>) -> Self {
42        Self { ops }
43    }
44
45    /// Add an operation to this patch (builder pattern).
46    #[inline]
47    pub fn with_op(mut self, op: Op) -> Self {
48        self.ops.push(op);
49        self
50    }
51
52    /// Push an operation onto this patch.
53    #[inline]
54    pub fn push(&mut self, op: Op) {
55        self.ops.push(op);
56    }
57
58    /// Get the operations in this patch.
59    #[inline]
60    pub fn ops(&self) -> &[Op] {
61        &self.ops
62    }
63
64    /// Get mutable access to the operations.
65    #[inline]
66    pub fn ops_mut(&mut self) -> &mut Vec<Op> {
67        &mut self.ops
68    }
69
70    /// Consume this patch and return the operations.
71    #[inline]
72    pub fn into_ops(self) -> Vec<Op> {
73        self.ops
74    }
75
76    /// Check if this patch is empty.
77    #[inline]
78    pub fn is_empty(&self) -> bool {
79        self.ops.is_empty()
80    }
81
82    /// Get the number of operations in this patch.
83    #[inline]
84    pub fn len(&self) -> usize {
85        self.ops.len()
86    }
87
88    /// Extend this patch with operations from another patch.
89    #[inline]
90    pub fn extend(&mut self, other: Patch) {
91        self.ops.extend(other.ops);
92    }
93
94    /// Merge another patch into this one (alias for extend).
95    #[inline]
96    pub fn merge(&mut self, other: Patch) {
97        self.extend(other);
98    }
99
100    /// Clear all operations from this patch.
101    #[inline]
102    pub fn clear(&mut self) {
103        self.ops.clear();
104    }
105
106    /// Iterate over the operations.
107    #[inline]
108    pub fn iter(&self) -> impl Iterator<Item = &Op> {
109        self.ops.iter()
110    }
111
112    /// Canonicalize the patch by removing redundant operations.
113    ///
114    /// This is a **safe, semantics-preserving** optimization that:
115    /// - Removes earlier `Set` operations when a later `Set` targets the same path
116    /// - Removes earlier `Set` operations when a later `Delete` targets the same path
117    /// - Removes earlier `Delete` operations when a later `Set` or `Delete` targets the same path
118    ///
119    /// **Important**: This function only *removes* redundant operations. It never reorders
120    /// the remaining operations. The output is always a subsequence of the input in the
121    /// same relative order.
122    ///
123    /// Operations that are **not** optimized (kept as-is):
124    /// - `Increment`, `Decrement`, `MergeObject`: These have cumulative effects and
125    ///   cannot be safely deduplicated without semantic analysis
126    /// - `Append`, `Insert`, `Remove`: Array operations are order-sensitive
127    ///
128    /// # Examples
129    ///
130    /// ```
131    /// use tirea_state::{Patch, Op, path};
132    /// use serde_json::json;
133    ///
134    /// let patch = Patch::new()
135    ///     .with_op(Op::set(path!("name"), json!("Alice")))
136    ///     .with_op(Op::set(path!("name"), json!("Bob")));  // overwrites Alice
137    ///
138    /// let canonical = patch.canonicalize();
139    /// assert_eq!(canonical.len(), 1);
140    /// assert_eq!(canonical.ops()[0], Op::set(path!("name"), json!("Bob")));
141    /// ```
142    pub fn canonicalize(&self) -> Patch {
143        use crate::Path;
144        use std::collections::HashSet;
145
146        if self.ops.is_empty() {
147            return Patch::new();
148        }
149
150        // Backward scan algorithm for semantic-preserving canonicalization
151        //
152        // Key insight: A later Set/Delete at path P makes earlier operations at P
153        // or any child of P irrelevant, because Set/Delete overwrites everything.
154        //
155        // Algorithm:
156        // 1. Scan operations backward (from end to start)
157        // 2. Maintain a set of "covered" paths
158        // 3. For each operation:
159        //    - If its path is covered by any later Set/Delete → skip (redundant)
160        //    - Otherwise → keep it
161        //    - If it's a Set/Delete → mark its path as covered
162        // 4. Reverse the result to restore original order
163
164        let mut covered_paths: HashSet<Path> = HashSet::new();
165        let mut kept_ops: Vec<Op> = Vec::new();
166
167        // Scan backward
168        for op in self.ops.iter().rev() {
169            let op_path = op.path();
170
171            // Check if this operation is covered by a later Set/Delete
172            let is_covered = covered_paths.iter().any(|covered| {
173                // Case 1: Exact match - later op at same path覆盖s this one
174                if covered == op_path {
175                    return true;
176                }
177                // Case 2: covered is prefix of op_path - parent Set覆盖s child op
178                // e.g., Set(user)覆盖s Increment(user.age)
179                if covered.is_prefix_of(op_path) {
180                    return true;
181                }
182                false
183            });
184
185            if is_covered {
186                // This operation is redundant, skip it
187                continue;
188            }
189
190            // Keep this operation
191            kept_ops.push(op.clone());
192
193            // If this is a Set/Delete, mark its path (and implicitly all children) as covered
194            match op {
195                Op::Set { path, .. } | Op::Delete { path } => {
196                    // Also remove any covered paths that are children of this path
197                    // because Set(user) makes Set(user.name) coverage redundant
198                    covered_paths.retain(|p| !path.is_prefix_of(p));
199                    covered_paths.insert(path.clone());
200                }
201                _ => {
202                    // Non-Set/Delete operations don't create coverage
203                    // They can still be覆盖d by later Sets, but don't覆盖 others
204                }
205            }
206        }
207
208        // Reverse to restore original order
209        kept_ops.reverse();
210
211        Patch::with_ops(kept_ops)
212    }
213}
214
215impl FromIterator<Op> for Patch {
216    fn from_iter<I: IntoIterator<Item = Op>>(iter: I) -> Self {
217        Self {
218            ops: iter.into_iter().collect(),
219        }
220    }
221}
222
223impl IntoIterator for Patch {
224    type Item = Op;
225    type IntoIter = std::vec::IntoIter<Op>;
226
227    fn into_iter(self) -> Self::IntoIter {
228        self.ops.into_iter()
229    }
230}
231
232impl<'a> IntoIterator for &'a Patch {
233    type Item = &'a Op;
234    type IntoIter = std::slice::Iter<'a, Op>;
235
236    fn into_iter(self) -> Self::IntoIter {
237        self.ops.iter()
238    }
239}
240
241impl Extend<Op> for Patch {
242    fn extend<I: IntoIterator<Item = Op>>(&mut self, iter: I) {
243        self.ops.extend(iter);
244    }
245}
246
247/// A patch with tracking metadata.
248///
249/// `TrackedPatch` wraps a `Patch` with additional information useful for
250/// debugging, auditing, and conflict detection.
251///
252/// # Examples
253///
254/// ```
255/// use tirea_state::{Patch, TrackedPatch, Op, path};
256/// use serde_json::json;
257///
258/// let patch = Patch::new()
259///     .with_op(Op::set(path!("counter"), json!(1)));
260///
261/// let tracked = TrackedPatch::new(patch)
262///     .with_id("patch-001")
263///     .with_source("user-service");
264/// ```
265#[derive(Clone, Debug, Serialize, Deserialize)]
266pub struct TrackedPatch {
267    /// The underlying patch.
268    pub patch: Patch,
269
270    /// Unique identifier for this patch.
271    #[serde(skip_serializing_if = "Option::is_none")]
272    pub id: Option<String>,
273
274    /// Timestamp when this patch was created (Unix epoch millis).
275    #[serde(skip_serializing_if = "Option::is_none")]
276    pub timestamp: Option<u64>,
277
278    /// Source/origin of this patch (e.g., service name, user ID).
279    #[serde(skip_serializing_if = "Option::is_none")]
280    pub source: Option<String>,
281
282    /// Optional description of what this patch does.
283    #[serde(skip_serializing_if = "Option::is_none")]
284    pub description: Option<String>,
285}
286
287impl TrackedPatch {
288    /// Create a new tracked patch.
289    #[inline]
290    pub fn new(patch: Patch) -> Self {
291        Self {
292            patch,
293            id: None,
294            timestamp: None,
295            source: None,
296            description: None,
297        }
298    }
299
300    /// Set the patch ID (builder pattern).
301    #[inline]
302    pub fn with_id(mut self, id: impl Into<String>) -> Self {
303        self.id = Some(id.into());
304        self
305    }
306
307    /// Set the timestamp (builder pattern).
308    #[inline]
309    pub fn with_timestamp(mut self, ts: u64) -> Self {
310        self.timestamp = Some(ts);
311        self
312    }
313
314    /// Set the source (builder pattern).
315    #[inline]
316    pub fn with_source(mut self, source: impl Into<String>) -> Self {
317        self.source = Some(source.into());
318        self
319    }
320
321    /// Set the description (builder pattern).
322    #[inline]
323    pub fn with_description(mut self, desc: impl Into<String>) -> Self {
324        self.description = Some(desc.into());
325        self
326    }
327
328    /// Get the underlying patch.
329    #[inline]
330    pub fn patch(&self) -> &Patch {
331        &self.patch
332    }
333
334    /// Consume and return the underlying patch.
335    #[inline]
336    pub fn into_patch(self) -> Patch {
337        self.patch
338    }
339}
340
341impl From<Patch> for TrackedPatch {
342    fn from(patch: Patch) -> Self {
343        TrackedPatch::new(patch)
344    }
345}
346
347#[cfg(test)]
348mod tests {
349    use super::*;
350    use crate::path;
351    use serde_json::json;
352
353    #[test]
354    fn test_patch_builder() {
355        let patch = Patch::new()
356            .with_op(Op::set(path!("a"), json!(1)))
357            .with_op(Op::set(path!("b"), json!(2)));
358
359        assert_eq!(patch.len(), 2);
360    }
361
362    #[test]
363    fn test_patch_extend() {
364        let mut p1 = Patch::new().with_op(Op::set(path!("a"), json!(1)));
365        let p2 = Patch::new().with_op(Op::set(path!("b"), json!(2)));
366
367        p1.extend(p2);
368        assert_eq!(p1.len(), 2);
369    }
370
371    #[test]
372    fn test_patch_serde() {
373        let patch = Patch::new()
374            .with_op(Op::set(path!("name"), json!("test")))
375            .with_op(Op::increment(path!("count"), 1i64));
376
377        let json = serde_json::to_string(&patch).unwrap();
378        let parsed: Patch = serde_json::from_str(&json).unwrap();
379        assert_eq!(patch, parsed);
380    }
381
382    #[test]
383    fn test_tracked_patch() {
384        let patch = Patch::new().with_op(Op::set(path!("x"), json!(42)));
385
386        let tracked = TrackedPatch::new(patch)
387            .with_id("test-001")
388            .with_source("test")
389            .with_timestamp(1234567890);
390
391        assert_eq!(tracked.id, Some("test-001".into()));
392        assert_eq!(tracked.source, Some("test".into()));
393        assert_eq!(tracked.timestamp, Some(1234567890));
394    }
395
396    #[test]
397    fn test_canonicalize_multiple_sets() {
398        let patch = Patch::new()
399            .with_op(Op::set(path!("name"), json!("Alice")))
400            .with_op(Op::set(path!("name"), json!("Bob")))
401            .with_op(Op::set(path!("name"), json!("Charlie")));
402
403        let canonical = patch.canonicalize();
404        assert_eq!(canonical.len(), 1);
405        assert_eq!(canonical.ops()[0], Op::set(path!("name"), json!("Charlie")));
406    }
407
408    #[test]
409    fn test_canonicalize_set_then_delete() {
410        let patch = Patch::new()
411            .with_op(Op::set(path!("x"), json!(42)))
412            .with_op(Op::delete(path!("x")));
413
414        let canonical = patch.canonicalize();
415        assert_eq!(canonical.len(), 1);
416        assert_eq!(canonical.ops()[0], Op::delete(path!("x")));
417    }
418
419    #[test]
420    fn test_canonicalize_increments_not_combined() {
421        // Safe canonicalize does NOT combine increments (they have cumulative effects)
422        let patch = Patch::new()
423            .with_op(Op::increment(path!("count"), 1i64))
424            .with_op(Op::increment(path!("count"), 2i64))
425            .with_op(Op::increment(path!("count"), 3i64));
426
427        let canonical = patch.canonicalize();
428        // All increments are kept
429        assert_eq!(canonical.len(), 3);
430
431        // Verify semantics are preserved
432        let doc = json!({"count": 0});
433        let result_original = crate::apply_patch(&doc, &patch).unwrap();
434        let result_canonical = crate::apply_patch(&doc, &canonical).unwrap();
435        assert_eq!(result_original, result_canonical);
436    }
437
438    #[test]
439    fn test_canonicalize_increment_decrement_not_combined() {
440        // Safe canonicalize does NOT combine increment/decrement
441        let patch = Patch::new()
442            .with_op(Op::increment(path!("count"), 10i64))
443            .with_op(Op::decrement(path!("count"), 3i64));
444
445        let canonical = patch.canonicalize();
446        assert_eq!(canonical.len(), 2);
447
448        // Verify semantics
449        let doc = json!({"count": 0});
450        let result_original = crate::apply_patch(&doc, &patch).unwrap();
451        let result_canonical = crate::apply_patch(&doc, &canonical).unwrap();
452        assert_eq!(result_original, result_canonical);
453    }
454
455    #[test]
456    fn test_canonicalize_merge_objects_not_combined() {
457        // Safe canonicalize does NOT combine merge objects
458        let patch = Patch::new()
459            .with_op(Op::merge_object(path!("user"), json!({"name": "Alice"})))
460            .with_op(Op::merge_object(path!("user"), json!({"age": 30})));
461
462        let canonical = patch.canonicalize();
463        assert_eq!(canonical.len(), 2);
464
465        // Verify semantics
466        let doc = json!({"user": {}});
467        let result_original = crate::apply_patch(&doc, &patch).unwrap();
468        let result_canonical = crate::apply_patch(&doc, &canonical).unwrap();
469        assert_eq!(result_original, result_canonical);
470    }
471
472    #[test]
473    fn test_canonicalize_preserves_different_paths() {
474        // Input: set(a,1), set(b,2), set(a,10)
475        // Canonicalize removes set(a,1) because set(a,10) is the last for path "a"
476        // Result is a subsequence: set(b,2), set(a,10)
477        //
478        // IMPORTANT: This is NOT reordering. The output preserves the relative
479        // order of the remaining operations. b was at index 1, a's last occurrence
480        // was at index 2, so the output order is b -> a.
481        let patch = Patch::new()
482            .with_op(Op::set(path!("a"), json!(1))) // index 0 - REMOVED (not last for "a")
483            .with_op(Op::set(path!("b"), json!(2))) // index 1 - KEPT (last for "b")
484            .with_op(Op::set(path!("a"), json!(10))); // index 2 - KEPT (last for "a")
485
486        let canonical = patch.canonicalize();
487        assert_eq!(canonical.len(), 2);
488        // Output is a subsequence in original order: ops at index 1, then index 2
489        assert_eq!(canonical.ops()[0], Op::set(path!("b"), json!(2)));
490        assert_eq!(canonical.ops()[1], Op::set(path!("a"), json!(10)));
491    }
492
493    #[test]
494    fn test_canonicalize_array_ops_preserve_order() {
495        let patch = Patch::new()
496            .with_op(Op::append(path!("items"), json!(1)))
497            .with_op(Op::set(path!("name"), json!("test")))
498            .with_op(Op::append(path!("items"), json!(2)));
499
500        let canonical = patch.canonicalize();
501        // Array ops stay in their original positions
502        assert_eq!(canonical.len(), 3);
503        assert_eq!(canonical.ops()[0], Op::append(path!("items"), json!(1)));
504        assert_eq!(canonical.ops()[1], Op::set(path!("name"), json!("test")));
505        assert_eq!(canonical.ops()[2], Op::append(path!("items"), json!(2)));
506    }
507
508    #[test]
509    fn test_canonicalize_preserves_operation_order() {
510        // This test verifies that canonicalize doesn't reorder operations
511        let patch = Patch::new()
512            .with_op(Op::set(path!("user"), json!({})))
513            .with_op(Op::append(path!("items"), json!(1)))
514            .with_op(Op::set(path!("user", "name"), json!("Alice")));
515
516        let canonical = patch.canonicalize();
517        // Order must be preserved: Set(user) -> Append(items) -> Set(user.name)
518        assert_eq!(canonical.len(), 3);
519        assert_eq!(canonical.ops()[0], Op::set(path!("user"), json!({})));
520        assert_eq!(canonical.ops()[1], Op::append(path!("items"), json!(1)));
521        assert_eq!(
522            canonical.ops()[2],
523            Op::set(path!("user", "name"), json!("Alice"))
524        );
525    }
526
527    #[test]
528    fn test_canonicalize_interleaved_increment_set() {
529        // Increment, Set, Increment 交错序列
530        // 正确行为：Set 会重置值，后续的 Increment 应该保留
531        let patch = Patch::new()
532            .with_op(Op::increment(path!("x"), 1i64))
533            .with_op(Op::set(path!("x"), json!(0)))
534            .with_op(Op::increment(path!("x"), 2i64));
535
536        let canonical = patch.canonicalize();
537
538        // 验证语义一致性
539        let doc = json!({"x": 100});
540        let result_original = crate::apply_patch(&doc, &patch).unwrap();
541        let result_canonical = crate::apply_patch(&doc, &canonical).unwrap();
542
543        assert_eq!(
544            result_original, result_canonical,
545            "canonicalize changed semantics! original={}, canonical={}",
546            result_original["x"], result_canonical["x"]
547        );
548    }
549
550    #[test]
551    fn test_canonicalize_interleaved_merge_set() {
552        // MergeObject, Set, MergeObject 交错序列
553        let patch = Patch::new()
554            .with_op(Op::merge_object(path!("user"), json!({"a": 1})))
555            .with_op(Op::set(path!("user"), json!({})))
556            .with_op(Op::merge_object(path!("user"), json!({"b": 2})));
557
558        let canonical = patch.canonicalize();
559
560        let doc = json!({"user": {"existing": true}});
561        let result_original = crate::apply_patch(&doc, &patch).unwrap();
562        let result_canonical = crate::apply_patch(&doc, &canonical).unwrap();
563
564        assert_eq!(
565            result_original, result_canonical,
566            "canonicalize changed semantics!"
567        );
568    }
569
570    #[test]
571    fn test_canonicalize_empty_patch() {
572        let patch = Patch::new();
573        let canonical = patch.canonicalize();
574        assert!(canonical.is_empty());
575    }
576
577    #[test]
578    fn test_canonicalize_semantics_preserved() {
579        // Comprehensive test: canonicalize must never change semantics
580        let patch = Patch::new()
581            .with_op(Op::increment(path!("value"), 1.5f64))
582            .with_op(Op::increment(path!("value"), 2.5f64));
583
584        let canonical = patch.canonicalize();
585        // Increments are not combined in safe mode
586        assert_eq!(canonical.len(), 2);
587
588        // But semantics must be identical
589        let doc = json!({"value": 0.0});
590        let result_original = crate::apply_patch(&doc, &patch).unwrap();
591        let result_canonical = crate::apply_patch(&doc, &canonical).unwrap();
592        assert_eq!(result_original, result_canonical);
593    }
594
595    #[test]
596    fn test_canonicalize_set_increment_set_correct_behavior() {
597        // Problem 1 from code review: Set -> Increment -> Set should remove BOTH
598        // Set(1) and Increment because the final Set(2) overwrites everything.
599        //
600        // Original: set(x, 1) -> increment(x, +1) -> set(x, 2)
601        // Correct semantic: x = 2 (final set wins, intermediate ops irrelevant)
602        //
603        // Correct canonicalize should produce: set(x, 2)
604        // Only the final Set matters
605
606        let patch = Patch::new()
607            .with_op(Op::set(path!("x"), json!(1)))
608            .with_op(Op::increment(path!("x"), 1i64))
609            .with_op(Op::set(path!("x"), json!(2)));
610
611        let canonical = patch.canonicalize();
612
613        // Test with various initial docs
614        let docs = vec![
615            json!({}),          // x doesn't exist
616            json!({"x": 100}),  // x has different value
617            json!({"x": null}), // x is null
618        ];
619
620        for doc in docs {
621            let result_original = crate::apply_patch(&doc, &patch).unwrap();
622            let result_canonical = crate::apply_patch(&doc, &canonical).unwrap();
623
624            assert_eq!(
625                result_original, result_canonical,
626                "canonicalize changed semantics for doc: {}",
627                doc
628            );
629
630            // Both should result in x = 2
631            assert_eq!(result_original["x"], json!(2));
632        }
633
634        // Canonical should be just: set(x, 2)
635        // The final Set should have covered both previous Set and Increment
636        assert_eq!(
637            canonical.len(),
638            1,
639            "Expected 1 op after canonicalization, got: {:?}",
640            canonical.ops()
641        );
642
643        // Verify it's a Set operation for path "x" with value 2
644        match &canonical.ops()[0] {
645            Op::Set { path, value } => {
646                assert_eq!(path, &path!("x"));
647                assert_eq!(value, &json!(2));
648            }
649            _ => panic!("Expected Set operation, got: {:?}", canonical.ops()[0]),
650        }
651    }
652}
tirea_state/patch.rs

tirea_state/
patch.rs
