fionn_core/
diffable.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//! Format-agnostic diff and patch traits
3//!
4//! This module provides traits for computing diffs and applying patches
5//! across different data formats. The [`DiffableValue`] trait enables
6//! structural comparison, while [`GenericPatch`] represents format-agnostic
7//! patch operations.
8//!
9//! # Key Types
10//!
11//! - [`DiffableValue`] - Trait for values that can be compared for diffing
12//! - [`DiffValueKind`] - Classification of value types for diff operations
13//! - [`GenericPatchOperation`] - A single patch operation
14//! - [`GenericPatch`] - A collection of patch operations
15//!
16//! # Example
17//!
18//! ```ignore
19//! use fionn_core::diffable::{DiffableValue, compute_diff};
20//!
21//! let source: serde_json::Value = serde_json::json!({"name": "Alice"});
22//! let target: serde_json::Value = serde_json::json!({"name": "Bob"});
23//!
24//! let patch = compute_diff(&source, &target);
25//! ```
26
27use std::fmt;
28
29// ============================================================================
30// DiffValueKind - Value type classification
31// ============================================================================
32
33/// Classification of value types for diff operations
34///
35/// This enum provides a uniform way to identify value types across
36/// different data formats, enabling type-aware diff algorithms.
37#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
38pub enum DiffValueKind {
39    /// Null/nil/none value
40    Null,
41    /// Boolean value
42    Bool,
43    /// Numeric value (integer or float)
44    Number,
45    /// String value
46    String,
47    /// Array/sequence container
48    Array,
49    /// Object/map container
50    Object,
51}
52
53impl DiffValueKind {
54    /// Check if this is a scalar type
55    #[must_use]
56    pub const fn is_scalar(self) -> bool {
57        matches!(self, Self::Null | Self::Bool | Self::Number | Self::String)
58    }
59
60    /// Check if this is a container type
61    #[must_use]
62    pub const fn is_container(self) -> bool {
63        matches!(self, Self::Array | Self::Object)
64    }
65}
66
67impl fmt::Display for DiffValueKind {
68    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
69        match self {
70            Self::Null => write!(f, "null"),
71            Self::Bool => write!(f, "boolean"),
72            Self::Number => write!(f, "number"),
73            Self::String => write!(f, "string"),
74            Self::Array => write!(f, "array"),
75            Self::Object => write!(f, "object"),
76        }
77    }
78}
79
80// ============================================================================
81// DiffableValue Trait
82// ============================================================================
83
84/// Trait for values that can be compared for diffing
85///
86/// This trait provides the interface needed by diff algorithms to:
87/// - Compare values for equality
88/// - Determine value types
89/// - Navigate container contents
90///
91/// # Implementation Notes
92///
93/// - `equals()` should perform deep equality comparison
94/// - `as_object()` returns an iterator over (key, value) pairs
95/// - `as_array()` returns a slice of elements
96pub trait DiffableValue: Clone + PartialEq {
97    /// Check deep equality with another value
98    fn equals(&self, other: &Self) -> bool;
99
100    /// Get the value type classification
101    fn value_kind(&self) -> DiffValueKind;
102
103    /// Get object entries as an iterator if this is an object
104    ///
105    /// Returns `None` if this is not an object.
106    fn as_object(&self) -> Option<Box<dyn Iterator<Item = (&str, &Self)> + '_>>;
107
108    /// Get object keys as a vector if this is an object
109    fn object_keys(&self) -> Option<Vec<&str>> {
110        self.as_object().map(|iter| iter.map(|(k, _)| k).collect())
111    }
112
113    /// Get a field value from an object
114    fn get_field(&self, key: &str) -> Option<&Self>;
115
116    /// Get array elements as a slice if this is an array
117    fn as_array(&self) -> Option<&[Self]>
118    where
119        Self: Sized;
120
121    /// Get array length if this is an array
122    fn array_len(&self) -> Option<usize> {
123        self.as_array().map(<[Self]>::len)
124    }
125
126    /// Get an array element by index
127    fn get_element(&self, index: usize) -> Option<&Self>
128    where
129        Self: Sized,
130    {
131        self.as_array().and_then(|arr| arr.get(index))
132    }
133
134    /// Get as string reference if this is a string
135    fn as_str(&self) -> Option<&str>;
136
137    /// Get as boolean if this is a boolean
138    fn as_bool(&self) -> Option<bool>;
139
140    /// Get as i64 if this is a number
141    fn as_i64(&self) -> Option<i64>;
142
143    /// Get as f64 if this is a number
144    fn as_f64(&self) -> Option<f64>;
145
146    /// Create a deep clone of this value
147    #[must_use]
148    fn deep_clone(&self) -> Self
149    where
150        Self: Sized,
151    {
152        self.clone()
153    }
154
155    /// Check if this is a null value
156    fn is_null(&self) -> bool {
157        matches!(self.value_kind(), DiffValueKind::Null)
158    }
159
160    /// Check if this is an object
161    fn is_object(&self) -> bool {
162        matches!(self.value_kind(), DiffValueKind::Object)
163    }
164
165    /// Check if this is an array
166    fn is_array(&self) -> bool {
167        matches!(self.value_kind(), DiffValueKind::Array)
168    }
169}
170
171// ============================================================================
172// GenericPatchOperation
173// ============================================================================
174
175/// A single patch operation (format-agnostic)
176///
177/// Modeled after RFC 6902 (JSON Patch) but generic over value types.
178#[derive(Debug, Clone, PartialEq, Eq)]
179pub enum GenericPatchOperation<V: DiffableValue> {
180    /// Add a value at a path
181    Add {
182        /// The target path
183        path: String,
184        /// The value to add
185        value: V,
186    },
187    /// Remove the value at a path
188    Remove {
189        /// The path to remove
190        path: String,
191    },
192    /// Replace the value at a path
193    Replace {
194        /// The target path
195        path: String,
196        /// The new value
197        value: V,
198    },
199    /// Move a value from one path to another
200    Move {
201        /// The source path
202        from: String,
203        /// The destination path
204        path: String,
205    },
206    /// Copy a value from one path to another
207    Copy {
208        /// The source path
209        from: String,
210        /// The destination path
211        path: String,
212    },
213    /// Test that a value at a path equals the expected value
214    Test {
215        /// The path to test
216        path: String,
217        /// The expected value
218        value: V,
219    },
220}
221
222impl<V: DiffableValue> GenericPatchOperation<V> {
223    /// Get the target path of this operation
224    #[must_use]
225    pub fn path(&self) -> &str {
226        match self {
227            Self::Add { path, .. }
228            | Self::Remove { path }
229            | Self::Replace { path, .. }
230            | Self::Move { path, .. }
231            | Self::Copy { path, .. }
232            | Self::Test { path, .. } => path,
233        }
234    }
235
236    /// Get the source path for move/copy operations
237    #[must_use]
238    pub fn from_path(&self) -> Option<&str> {
239        match self {
240            Self::Move { from, .. } | Self::Copy { from, .. } => Some(from),
241            _ => None,
242        }
243    }
244
245    /// Check if this is an add operation
246    #[must_use]
247    pub const fn is_add(&self) -> bool {
248        matches!(self, Self::Add { .. })
249    }
250
251    /// Check if this is a remove operation
252    #[must_use]
253    pub const fn is_remove(&self) -> bool {
254        matches!(self, Self::Remove { .. })
255    }
256
257    /// Check if this is a replace operation
258    #[must_use]
259    pub const fn is_replace(&self) -> bool {
260        matches!(self, Self::Replace { .. })
261    }
262}
263
264impl<V: DiffableValue + fmt::Debug> fmt::Display for GenericPatchOperation<V> {
265    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
266        match self {
267            Self::Add { path, value } => write!(f, "add({path}, {value:?})"),
268            Self::Remove { path } => write!(f, "remove({path})"),
269            Self::Replace { path, value } => write!(f, "replace({path}, {value:?})"),
270            Self::Move { from, path } => write!(f, "move({from} -> {path})"),
271            Self::Copy { from, path } => write!(f, "copy({from} -> {path})"),
272            Self::Test { path, value } => write!(f, "test({path}, {value:?})"),
273        }
274    }
275}
276
277// ============================================================================
278// GenericPatch
279// ============================================================================
280
281/// A collection of patch operations (format-agnostic)
282///
283/// Represents a complete diff between two values as a sequence of operations.
284#[derive(Debug, Clone, Default)]
285pub struct GenericPatch<V: DiffableValue> {
286    /// The operations in this patch
287    pub operations: Vec<GenericPatchOperation<V>>,
288}
289
290impl<V: DiffableValue> GenericPatch<V> {
291    /// Create a new empty patch
292    #[must_use]
293    pub const fn new() -> Self {
294        Self {
295            operations: Vec::new(),
296        }
297    }
298
299    /// Create a patch with the given operations
300    #[must_use]
301    pub const fn with_operations(operations: Vec<GenericPatchOperation<V>>) -> Self {
302        Self { operations }
303    }
304
305    /// Add an operation to this patch
306    pub fn push(&mut self, op: GenericPatchOperation<V>) {
307        self.operations.push(op);
308    }
309
310    /// Check if this patch is empty
311    #[must_use]
312    pub const fn is_empty(&self) -> bool {
313        self.operations.is_empty()
314    }
315
316    /// Get the number of operations
317    #[must_use]
318    pub const fn len(&self) -> usize {
319        self.operations.len()
320    }
321
322    /// Iterate over operations
323    pub fn iter(&self) -> impl Iterator<Item = &GenericPatchOperation<V>> {
324        self.operations.iter()
325    }
326
327    /// Get operations that affect a specific path prefix
328    #[must_use]
329    pub fn operations_at_prefix(&self, prefix: &str) -> Vec<&GenericPatchOperation<V>> {
330        self.operations
331            .iter()
332            .filter(|op| op.path().starts_with(prefix))
333            .collect()
334    }
335}
336
337impl<V: DiffableValue> FromIterator<GenericPatchOperation<V>> for GenericPatch<V> {
338    fn from_iter<I: IntoIterator<Item = GenericPatchOperation<V>>>(iter: I) -> Self {
339        Self {
340            operations: iter.into_iter().collect(),
341        }
342    }
343}
344
345impl<V: DiffableValue> IntoIterator for GenericPatch<V> {
346    type Item = GenericPatchOperation<V>;
347    type IntoIter = std::vec::IntoIter<GenericPatchOperation<V>>;
348
349    fn into_iter(self) -> Self::IntoIter {
350        self.operations.into_iter()
351    }
352}
353
354// ============================================================================
355// DiffableValue for serde_json::Value
356// ============================================================================
357
358impl DiffableValue for serde_json::Value {
359    fn equals(&self, other: &Self) -> bool {
360        self == other
361    }
362
363    fn value_kind(&self) -> DiffValueKind {
364        match self {
365            Self::Null => DiffValueKind::Null,
366            Self::Bool(_) => DiffValueKind::Bool,
367            Self::Number(_) => DiffValueKind::Number,
368            Self::String(_) => DiffValueKind::String,
369            Self::Array(_) => DiffValueKind::Array,
370            Self::Object(_) => DiffValueKind::Object,
371        }
372    }
373
374    fn as_object(&self) -> Option<Box<dyn Iterator<Item = (&str, &Self)> + '_>> {
375        match self {
376            Self::Object(map) => Some(Box::new(map.iter().map(|(k, v)| (k.as_str(), v)))),
377            _ => None,
378        }
379    }
380
381    fn get_field(&self, key: &str) -> Option<&Self> {
382        match self {
383            Self::Object(map) => map.get(key),
384            _ => None,
385        }
386    }
387
388    fn as_array(&self) -> Option<&[Self]> {
389        match self {
390            Self::Array(arr) => Some(arr.as_slice()),
391            _ => None,
392        }
393    }
394
395    fn as_str(&self) -> Option<&str> {
396        self.as_str()
397    }
398
399    fn as_bool(&self) -> Option<bool> {
400        self.as_bool()
401    }
402
403    fn as_i64(&self) -> Option<i64> {
404        self.as_i64()
405    }
406
407    fn as_f64(&self) -> Option<f64> {
408        self.as_f64()
409    }
410}
411
412// ============================================================================
413// Diff Algorithm Helpers
414// ============================================================================
415
416/// Options for diff computation
417#[derive(Debug, Clone, Default)]
418pub struct DiffOptions {
419    /// Include paths to arrays that were reordered
420    pub detect_reorder: bool,
421    /// Use move operations for object field renames
422    pub detect_moves: bool,
423    /// Maximum depth to diff (0 = unlimited)
424    pub max_depth: usize,
425}
426
427impl DiffOptions {
428    /// Create default diff options
429    #[must_use]
430    pub fn new() -> Self {
431        Self::default()
432    }
433
434    /// Enable move detection
435    #[must_use]
436    pub const fn with_move_detection(mut self) -> Self {
437        self.detect_moves = true;
438        self
439    }
440
441    /// Enable reorder detection
442    #[must_use]
443    pub const fn with_reorder_detection(mut self) -> Self {
444        self.detect_reorder = true;
445        self
446    }
447
448    /// Set maximum diff depth
449    #[must_use]
450    pub const fn with_max_depth(mut self, depth: usize) -> Self {
451        self.max_depth = depth;
452        self
453    }
454}
455
456/// Compute a diff between two values
457///
458/// This is a generic diff algorithm that works with any [`DiffableValue`].
459#[must_use]
460pub fn compute_diff<V: DiffableValue>(source: &V, target: &V) -> GenericPatch<V> {
461    compute_diff_with_options(source, target, &DiffOptions::default())
462}
463
464/// Compute a diff with custom options
465#[must_use]
466pub fn compute_diff_with_options<V: DiffableValue>(
467    source: &V,
468    target: &V,
469    options: &DiffOptions,
470) -> GenericPatch<V> {
471    let mut patch = GenericPatch::new();
472    diff_values(source, target, "", &mut patch, options, 0);
473    patch
474}
475
476fn diff_values<V: DiffableValue>(
477    source: &V,
478    target: &V,
479    current_path: &str,
480    result: &mut GenericPatch<V>,
481    options: &DiffOptions,
482    depth: usize,
483) {
484    // Check depth limit
485    if options.max_depth > 0 && depth >= options.max_depth {
486        if !source.equals(target) {
487            result.push(GenericPatchOperation::Replace {
488                path: current_path.to_string(),
489                value: target.deep_clone(),
490            });
491        }
492        return;
493    }
494
495    // Fast path: equal values
496    if source.equals(target) {
497        return;
498    }
499
500    // Different types: replace
501    if source.value_kind() != target.value_kind() {
502        result.push(GenericPatchOperation::Replace {
503            path: current_path.to_string(),
504            value: target.deep_clone(),
505        });
506        return;
507    }
508
509    // Same type, different values
510    match (source.value_kind(), target.value_kind()) {
511        (DiffValueKind::Object, DiffValueKind::Object) => {
512            diff_objects(source, target, current_path, result, options, depth);
513        }
514        (DiffValueKind::Array, DiffValueKind::Array) => {
515            diff_arrays(source, target, current_path, result, options, depth);
516        }
517        _ => {
518            // Scalar types: just replace
519            result.push(GenericPatchOperation::Replace {
520                path: current_path.to_string(),
521                value: target.deep_clone(),
522            });
523        }
524    }
525}
526
527fn diff_objects<V: DiffableValue>(
528    source: &V,
529    target: &V,
530    current_path: &str,
531    result: &mut GenericPatch<V>,
532    options: &DiffOptions,
533    depth: usize,
534) {
535    let src_keys: std::collections::HashSet<_> = source
536        .object_keys()
537        .map(|keys| keys.into_iter().collect())
538        .unwrap_or_default();
539    let tgt_keys: std::collections::HashSet<_> = target
540        .object_keys()
541        .map(|keys| keys.into_iter().collect())
542        .unwrap_or_default();
543
544    // Removed keys
545    for key in &src_keys {
546        if !tgt_keys.contains(key) {
547            let field_path = format_path(current_path, key);
548            result.push(GenericPatchOperation::Remove { path: field_path });
549        }
550    }
551
552    // Added and modified keys
553    for key in &tgt_keys {
554        let field_path = format_path(current_path, key);
555
556        if src_keys.contains(key) {
557            // Modified (recursively diff)
558            if let (Some(src_val), Some(tgt_val)) = (source.get_field(key), target.get_field(key)) {
559                diff_values(src_val, tgt_val, &field_path, result, options, depth + 1);
560            }
561        } else {
562            // Added
563            if let Some(val) = target.get_field(key) {
564                result.push(GenericPatchOperation::Add {
565                    path: field_path,
566                    value: val.deep_clone(),
567                });
568            }
569        }
570    }
571}
572
573fn diff_arrays<V: DiffableValue>(
574    source: &V,
575    target: &V,
576    current_path: &str,
577    result: &mut GenericPatch<V>,
578    options: &DiffOptions,
579    depth: usize,
580) {
581    let src_arr = source.as_array().unwrap_or(&[]);
582    let tgt_arr = target.as_array().unwrap_or(&[]);
583
584    let src_len = src_arr.len();
585    let tgt_len = tgt_arr.len();
586
587    // Simple element-by-element diff
588    let min_len = src_len.min(tgt_len);
589
590    // Diff common elements
591    for (idx, (src_elem, tgt_elem)) in src_arr.iter().zip(tgt_arr.iter()).take(min_len).enumerate()
592    {
593        let elem_path = format!("{current_path}/{idx}");
594        diff_values(src_elem, tgt_elem, &elem_path, result, options, depth + 1);
595    }
596
597    // Handle length differences
598    if tgt_len > src_len {
599        // Elements added
600        for (idx, elem) in tgt_arr.iter().enumerate().skip(src_len) {
601            let elem_path = format!("{current_path}/{idx}");
602            result.push(GenericPatchOperation::Add {
603                path: elem_path,
604                value: elem.deep_clone(),
605            });
606        }
607    } else if src_len > tgt_len {
608        // Elements removed (remove from end first)
609        for idx in (tgt_len..src_len).rev() {
610            let elem_path = format!("{current_path}/{idx}");
611            result.push(GenericPatchOperation::Remove { path: elem_path });
612        }
613    }
614}
615
616fn format_path(base: &str, key: &str) -> String {
617    if base.is_empty() {
618        format!("/{}", escape_json_pointer(key))
619    } else {
620        format!("{base}/{}", escape_json_pointer(key))
621    }
622}
623
624fn escape_json_pointer(s: &str) -> String {
625    s.replace('~', "~0").replace('/', "~1")
626}
627
628// ============================================================================
629// Tests
630// ============================================================================
631
632#[cfg(test)]
633mod tests {
634    use super::*;
635    use serde_json::json;
636
637    #[test]
638    fn test_diff_value_kind() {
639        assert!(DiffValueKind::Null.is_scalar());
640        assert!(DiffValueKind::Bool.is_scalar());
641        assert!(DiffValueKind::Number.is_scalar());
642        assert!(DiffValueKind::String.is_scalar());
643        assert!(!DiffValueKind::Array.is_scalar());
644        assert!(!DiffValueKind::Object.is_scalar());
645
646        assert!(DiffValueKind::Array.is_container());
647        assert!(DiffValueKind::Object.is_container());
648    }
649
650    #[test]
651    fn test_diffable_value_json() {
652        let val = json!({"name": "Alice", "age": 30});
653
654        assert_eq!(val.value_kind(), DiffValueKind::Object);
655        assert!(val.is_object());
656
657        let keys = val.object_keys().unwrap();
658        assert!(keys.contains(&"name"));
659        assert!(keys.contains(&"age"));
660
661        assert_eq!(val.get_field("name"), Some(&json!("Alice")));
662    }
663
664    #[test]
665    fn test_diffable_value_array() {
666        let val = json!([1, 2, 3]);
667
668        assert_eq!(val.value_kind(), DiffValueKind::Array);
669        assert!(val.is_array());
670        assert_eq!(val.array_len(), Some(3));
671        assert_eq!(val.get_element(0), Some(&json!(1)));
672    }
673
674    #[test]
675    fn test_compute_diff_equal() {
676        let source = json!({"name": "Alice"});
677        let target = json!({"name": "Alice"});
678
679        let patch = compute_diff(&source, &target);
680        assert!(patch.is_empty());
681    }
682
683    #[test]
684    fn test_compute_diff_replace_scalar() {
685        let source = json!({"name": "Alice"});
686        let target = json!({"name": "Bob"});
687
688        let patch = compute_diff(&source, &target);
689        assert_eq!(patch.len(), 1);
690        assert!(
691            matches!(&patch.operations[0], GenericPatchOperation::Replace { path, .. } if path == "/name")
692        );
693    }
694
695    #[test]
696    fn test_compute_diff_add_field() {
697        let source = json!({"name": "Alice"});
698        let target = json!({"name": "Alice", "age": 30});
699
700        let patch = compute_diff(&source, &target);
701        assert_eq!(patch.len(), 1);
702        assert!(
703            matches!(&patch.operations[0], GenericPatchOperation::Add { path, .. } if path == "/age")
704        );
705    }
706
707    #[test]
708    fn test_compute_diff_remove_field() {
709        let source = json!({"name": "Alice", "age": 30});
710        let target = json!({"name": "Alice"});
711
712        let patch = compute_diff(&source, &target);
713        assert_eq!(patch.len(), 1);
714        assert!(
715            matches!(&patch.operations[0], GenericPatchOperation::Remove { path } if path == "/age")
716        );
717    }
718
719    #[test]
720    fn test_compute_diff_array_add() {
721        let source = json!([1, 2]);
722        let target = json!([1, 2, 3]);
723
724        let patch = compute_diff(&source, &target);
725        assert_eq!(patch.len(), 1);
726        assert!(
727            matches!(&patch.operations[0], GenericPatchOperation::Add { path, .. } if path == "/2")
728        );
729    }
730
731    #[test]
732    fn test_compute_diff_array_remove() {
733        let source = json!([1, 2, 3]);
734        let target = json!([1, 2]);
735
736        let patch = compute_diff(&source, &target);
737        assert_eq!(patch.len(), 1);
738        assert!(
739            matches!(&patch.operations[0], GenericPatchOperation::Remove { path } if path == "/2")
740        );
741    }
742
743    #[test]
744    fn test_compute_diff_type_change() {
745        let source = json!({"value": "string"});
746        let target = json!({"value": 42});
747
748        let patch = compute_diff(&source, &target);
749        assert_eq!(patch.len(), 1);
750        assert!(patch.operations[0].is_replace());
751    }
752
753    #[test]
754    fn test_compute_diff_nested() {
755        let source = json!({"user": {"name": "Alice"}});
756        let target = json!({"user": {"name": "Bob"}});
757
758        let patch = compute_diff(&source, &target);
759        assert_eq!(patch.len(), 1);
760        assert!(
761            matches!(&patch.operations[0], GenericPatchOperation::Replace { path, .. } if path == "/user/name")
762        );
763    }
764
765    #[test]
766    fn test_generic_patch_operations() {
767        let op: GenericPatchOperation<serde_json::Value> = GenericPatchOperation::Add {
768            path: "/test".to_string(),
769            value: json!(42),
770        };
771
772        assert_eq!(op.path(), "/test");
773        assert!(op.is_add());
774        assert!(!op.is_remove());
775    }
776
777    #[test]
778    fn test_generic_patch_iter() {
779        let patch = GenericPatch::with_operations(vec![
780            GenericPatchOperation::Add {
781                path: "/a".to_string(),
782                value: json!(1),
783            },
784            GenericPatchOperation::Add {
785                path: "/b".to_string(),
786                value: json!(2),
787            },
788        ]);
789
790        assert_eq!(patch.len(), 2);
791        assert!(!patch.is_empty());
792
793        let paths: Vec<_> = patch.iter().map(GenericPatchOperation::path).collect();
794        assert_eq!(paths, vec!["/a", "/b"]);
795    }
796
797    #[test]
798    fn test_diff_options() {
799        let options = DiffOptions::new().with_move_detection().with_max_depth(5);
800
801        assert!(options.detect_moves);
802        assert_eq!(options.max_depth, 5);
803    }
804
805    #[test]
806    fn test_escape_json_pointer() {
807        assert_eq!(escape_json_pointer("simple"), "simple");
808        assert_eq!(escape_json_pointer("with/slash"), "with~1slash");
809        assert_eq!(escape_json_pointer("with~tilde"), "with~0tilde");
810    }
811}
fionn_core/diffable.rs

fionn_core/
diffable.rs
