platform_value/patch/
diff.rs

1use crate::Value;
2use std::fmt;
3use std::fmt::Display;
4
5struct PatchDiffer {
6    path: String,
7    patch: super::Patch,
8    shift: usize,
9}
10
11impl PatchDiffer {
12    fn new() -> Self {
13        Self {
14            path: "/".to_string(),
15            patch: super::Patch(Vec::new()),
16            shift: 0,
17        }
18    }
19}
20
21impl<'a> treediff::Delegate<'a, PlatformItemKey, Value> for PatchDiffer {
22    fn push(&mut self, key: &PlatformItemKey) {
23        use std::fmt::Write;
24        if self.path.len() != 1 {
25            self.path.push('/');
26        }
27        match key {
28            PlatformItemKey::Index(idx) => write!(self.path, "{}", *idx).unwrap(),
29            PlatformItemKey::String(ref key) => append_path(&mut self.path, key),
30            PlatformItemKey::BigSignedIndex(idx) => write!(self.path, "{}", *idx).unwrap(),
31            PlatformItemKey::BigIndex(idx) => write!(self.path, "{}", *idx).unwrap(),
32            PlatformItemKey::SignedIndex(idx) => write!(self.path, "{}", *idx).unwrap(),
33            PlatformItemKey::Bytes(bytes) => write!(self.path, "{}", hex::encode(bytes)).unwrap(),
34            PlatformItemKey::ArrayIndex(idx) => write!(self.path, "{}", *idx - self.shift).unwrap(),
35        }
36    }
37
38    fn pop(&mut self) {
39        let mut pos = self.path.rfind('/').unwrap_or(0);
40        if pos == 0 {
41            pos = 1;
42        }
43        self.path.truncate(pos);
44        self.shift = 0;
45    }
46
47    fn removed<'b>(&mut self, k: &'b PlatformItemKey, _v: &'a Value) {
48        let len = self.path.len();
49        self.push(k);
50        self.patch
51            .0
52            .push(super::PatchOperation::Remove(super::RemoveOperation {
53                path: self.path.clone(),
54            }));
55        // Shift indices, we are deleting array elements
56        if let PlatformItemKey::ArrayIndex(_) = k {
57            self.shift += 1;
58        }
59        self.path.truncate(len);
60    }
61
62    fn added(&mut self, k: &PlatformItemKey, v: &Value) {
63        let len = self.path.len();
64        self.push(k);
65        self.patch
66            .0
67            .push(super::PatchOperation::Add(super::AddOperation {
68                path: self.path.clone(),
69                value: v.clone(),
70            }));
71        self.path.truncate(len);
72    }
73
74    fn modified(&mut self, _old: &'a Value, new: &'a Value) {
75        self.patch
76            .0
77            .push(super::PatchOperation::Replace(super::ReplaceOperation {
78                path: self.path.clone(),
79                value: new.clone(),
80            }));
81    }
82}
83
84fn append_path(path: &mut String, key: &str) {
85    path.reserve(key.len());
86    for ch in key.chars() {
87        if ch == '~' {
88            *path += "~0";
89        } else if ch == '/' {
90            *path += "~1";
91        } else {
92            path.push(ch);
93        }
94    }
95}
96
97/// Diff two Platform Value documents and generate a Platform Value Patch (RFC 6902).
98///
99/// # Example
100/// Diff two JSONs:
101///
102/// ```rust
103/// #[macro_use]
104///
105/// use platform_value::{from_value, patch, platform_value};
106///
107/// # pub fn main() {
108/// use platform_value::patch::diff;
109/// let left = platform_value!({
110///   "title": "Goodbye!",
111///   "author" : {
112///     "givenName" : "John",
113///     "familyName" : "Doe"
114///   },
115///   "tags":[ "example", "sample" ],
116///   "content": "This will be unchanged"
117/// });
118///
119/// let right = platform_value!({
120///   "title": "Hello!",
121///   "author" : {
122///     "givenName" : "John"
123///   },
124///   "tags": [ "example" ],
125///   "content": "This will be unchanged",
126///   "phoneNumber": "+01-123-456-7890"
127/// });
128///
129/// let p = diff(&left, &right);
130/// assert_eq!(p, from_value(platform_value!([
131///   { "op": "remove", "path": "/author/familyName" },
132///   { "op": "remove", "path": "/tags/1" },
133///   { "op": "replace", "path": "/title", "value": "Hello!" },
134///   { "op": "add", "path": "/phoneNumber", "value": "+01-123-456-7890" },
135/// ])).unwrap());
136///
137/// let mut doc = left.clone();
138/// patch(&mut doc, &p).unwrap();
139/// assert_eq!(doc, right);
140///
141/// # }
142/// ```
143pub fn diff(left: &Value, right: &Value) -> super::Patch {
144    let mut differ = PatchDiffer::new();
145    treediff::diff(left, right, &mut differ);
146    differ.patch
147}
148
149/// A representation of all key types typical Value types will assume.
150#[derive(Debug, Clone, PartialEq, Eq, Ord, PartialOrd)]
151pub enum PlatformItemKey {
152    /// A big index
153    BigSignedIndex(i128),
154    /// A big index
155    BigIndex(u128),
156    /// An array index
157    SignedIndex(i64),
158    /// An array index
159    Index(u64),
160    /// An array index
161    ArrayIndex(usize),
162    /// Bytes
163    Bytes(Vec<u8>),
164    /// A string index for mappings
165    String(String),
166}
167
168impl Display for PlatformItemKey {
169    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
170        match *self {
171            PlatformItemKey::String(ref v) => v.fmt(f),
172            PlatformItemKey::Index(ref v) => v.fmt(f),
173            PlatformItemKey::BigSignedIndex(ref v) => v.fmt(f),
174            PlatformItemKey::BigIndex(ref v) => v.fmt(f),
175            PlatformItemKey::SignedIndex(ref v) => v.fmt(f),
176            PlatformItemKey::Bytes(ref v) => hex::encode(v).fmt(f),
177            PlatformItemKey::ArrayIndex(ref v) => v.fmt(f),
178        }
179    }
180}
181
182impl From<Value> for Option<PlatformItemKey> {
183    fn from(value: Value) -> Self {
184        match value {
185            Value::U128(i) => Some(PlatformItemKey::BigIndex(i)),
186            Value::I128(i) => Some(PlatformItemKey::BigSignedIndex(i)),
187            Value::U64(i) => Some(PlatformItemKey::Index(i)),
188            Value::I64(i) => Some(PlatformItemKey::SignedIndex(i)),
189            Value::U32(i) => Some(PlatformItemKey::Index(i as u64)),
190            Value::I32(i) => Some(PlatformItemKey::SignedIndex(i as i64)),
191            Value::U16(i) => Some(PlatformItemKey::Index(i as u64)),
192            Value::I16(i) => Some(PlatformItemKey::SignedIndex(i as i64)),
193            Value::U8(i) => Some(PlatformItemKey::Index(i as u64)),
194            Value::I8(i) => Some(PlatformItemKey::SignedIndex(i as i64)),
195            Value::Bytes(bytes) => Some(PlatformItemKey::Bytes(bytes)),
196            Value::Bytes20(bytes) => Some(PlatformItemKey::Bytes(bytes.into())),
197            Value::Bytes32(bytes) => Some(PlatformItemKey::Bytes(bytes.into())),
198            Value::Bytes36(bytes) => Some(PlatformItemKey::Bytes(bytes.into())),
199            Value::EnumU8(_) => None,
200            Value::EnumString(_) => None,
201            Value::Identifier(bytes) => Some(PlatformItemKey::Bytes(bytes.into())),
202            Value::Float(_) => None,
203            Value::Text(str) => Some(PlatformItemKey::String(str)),
204            Value::Bool(_) => None,
205            Value::Null => None,
206            Value::Array(_) => None,
207            Value::Map(_) => None,
208        }
209    }
210}
211
212impl treediff::Value for Value {
213    type Key = PlatformItemKey;
214    /// The Value type itself.
215    type Item = Value;
216    /// Returns `None` if this is a scalar value, and an iterator yielding (Key, Value) pairs
217    /// otherwise. It is entirely possible for it to yield no values though.
218    #[allow(clippy::type_complexity)]
219    fn items<'a>(&'a self) -> Option<Box<dyn Iterator<Item = (Self::Key, &'a Self::Item)> + 'a>> {
220        match *self {
221            Value::Array(ref inner) => Some(Box::new(
222                inner
223                    .iter()
224                    .enumerate()
225                    .map(|(i, v)| (PlatformItemKey::ArrayIndex(i), v)),
226            )),
227            Value::Map(ref inner) => Some(Box::new(inner.iter().filter_map(|(s, v)| {
228                let key: Option<PlatformItemKey> = s.clone().into();
229                key.map(|k| (k, v))
230            }))),
231            _ => None,
232        }
233    }
234}
235
236#[cfg(test)]
237mod tests {
238    use crate::{from_value, platform_value, Value};
239
240    #[test]
241    pub fn replace_all() {
242        let left = platform_value!({"title": "Hello!"});
243        let p = super::diff(&left, &Value::Null);
244        assert_eq!(
245            p,
246            from_value(platform_value!([
247                { "op": "replace", "path": "/", "value": null },
248            ]))
249            .unwrap()
250        );
251    }
252
253    #[test]
254    pub fn add_all() {
255        let right = platform_value!({"title": "Hello!"});
256        let p = super::diff(&Value::Null, &right);
257        assert_eq!(
258            p,
259            from_value(platform_value!([
260                { "op": "replace", "path": "/", "value": { "title": "Hello!" } },
261            ]))
262            .unwrap()
263        );
264    }
265
266    #[test]
267    pub fn remove_all() {
268        let left = platform_value!(["hello", "bye"]);
269        let right = platform_value!([]);
270        let p = super::diff(&left, &right);
271        assert_eq!(
272            p,
273            from_value(platform_value!([
274                { "op": "remove", "path": "/0" },
275                { "op": "remove", "path": "/0" },
276            ]))
277            .unwrap()
278        );
279    }
280
281    #[test]
282    pub fn remove_tail() {
283        let left = platform_value!(["hello", "bye", "hi"]);
284        let right = platform_value!(["hello"]);
285        let p = super::diff(&left, &right);
286        assert_eq!(
287            p,
288            from_value(platform_value!([
289                { "op": "remove", "path": "/1" },
290                { "op": "remove", "path": "/1" },
291            ]))
292            .unwrap()
293        );
294    }
295    #[test]
296    pub fn replace_object() {
297        let left = platform_value!(["hello", "bye"]);
298        let right = platform_value!({"hello": "bye"});
299        let p = super::diff(&left, &right);
300        assert_eq!(
301            p,
302            from_value(platform_value!([
303                { "op": "add", "path": "/hello", "value": "bye" },
304                { "op": "remove", "path": "/0" },
305                { "op": "remove", "path": "/0" },
306            ]))
307            .unwrap()
308        );
309    }
310
311    #[test]
312    fn escape_json_keys() {
313        let mut left = platform_value!({
314            "/slashed/path": 1
315        });
316        let right = platform_value!({
317            "/slashed/path": 2,
318        });
319        let patch = super::diff(&left, &right);
320
321        eprintln!("{:?}", patch);
322
323        crate::patch(&mut left, &patch).unwrap();
324        assert_eq!(left, right);
325    }
326
327    // ---------------------------------------------------------------
328    // append_path: tilde and slash escaping
329    // ---------------------------------------------------------------
330
331    #[test]
332    fn append_path_escapes_tilde() {
333        let mut path = String::from("/");
334        super::append_path(&mut path, "a~b");
335        assert_eq!(path, "/a~0b");
336    }
337
338    #[test]
339    fn append_path_escapes_slash() {
340        let mut path = String::from("/");
341        super::append_path(&mut path, "a/b");
342        assert_eq!(path, "/a~1b");
343    }
344
345    #[test]
346    fn append_path_escapes_both() {
347        let mut path = String::from("/");
348        super::append_path(&mut path, "~/");
349        assert_eq!(path, "/~0~1");
350    }
351
352    #[test]
353    fn append_path_no_escaping_needed() {
354        let mut path = String::from("/");
355        super::append_path(&mut path, "plain");
356        assert_eq!(path, "/plain");
357    }
358
359    #[test]
360    fn append_path_empty_key() {
361        let mut path = String::from("/");
362        super::append_path(&mut path, "");
363        assert_eq!(path, "/");
364    }
365
366    // ---------------------------------------------------------------
367    // diff: identical values returns empty patch
368    // ---------------------------------------------------------------
369
370    #[test]
371    fn diff_identical_scalars_returns_empty() {
372        let v = platform_value!("hello");
373        let p = super::diff(&v, &v);
374        assert!(p.0.is_empty());
375    }
376
377    #[test]
378    fn diff_identical_maps_returns_empty() {
379        let v = platform_value!({"a": 1, "b": 2});
380        let p = super::diff(&v, &v);
381        assert!(p.0.is_empty());
382    }
383
384    #[test]
385    fn diff_identical_arrays_returns_empty() {
386        let v = platform_value!([1, 2, 3]);
387        let p = super::diff(&v, &v);
388        assert!(p.0.is_empty());
389    }
390
391    #[test]
392    fn diff_identical_nested_returns_empty() {
393        let v = platform_value!({"a": {"b": [1, 2]}});
394        let p = super::diff(&v, &v);
395        assert!(p.0.is_empty());
396    }
397
398    // ---------------------------------------------------------------
399    // diff: maps with added/removed/modified keys
400    // ---------------------------------------------------------------
401
402    #[test]
403    fn diff_map_added_key() {
404        let left = platform_value!({"a": 1});
405        let right = platform_value!({"a": 1, "b": 2});
406        let p = super::diff(&left, &right);
407        assert_eq!(
408            p,
409            from_value(platform_value!([
410                { "op": "add", "path": "/b", "value": 2 },
411            ]))
412            .unwrap()
413        );
414    }
415
416    #[test]
417    fn diff_map_removed_key() {
418        let left = platform_value!({"a": 1, "b": 2});
419        let right = platform_value!({"a": 1});
420        let p = super::diff(&left, &right);
421        assert_eq!(
422            p,
423            from_value(platform_value!([
424                { "op": "remove", "path": "/b" },
425            ]))
426            .unwrap()
427        );
428    }
429
430    #[test]
431    fn diff_map_modified_key() {
432        let left = platform_value!({"a": 1});
433        let right = platform_value!({"a": 2});
434        let p = super::diff(&left, &right);
435        assert_eq!(
436            p,
437            from_value(platform_value!([
438                { "op": "replace", "path": "/a", "value": 2 },
439            ]))
440            .unwrap()
441        );
442    }
443
444    #[test]
445    fn diff_map_added_removed_modified() {
446        let left = platform_value!({"a": 1, "b": 2});
447        let right = platform_value!({"a": 10, "c": 3});
448        let mut p_left = left.clone();
449        let patch = super::diff(&left, &right);
450        crate::patch(&mut p_left, &patch).unwrap();
451        assert_eq!(p_left, right);
452    }
453
454    // ---------------------------------------------------------------
455    // diff: arrays with insertions/deletions
456    // ---------------------------------------------------------------
457
458    #[test]
459    fn diff_array_append() {
460        let left = platform_value!([1, 2]);
461        let right = platform_value!([1, 2, 3]);
462        let patch = super::diff(&left, &right);
463        let mut doc = left.clone();
464        crate::patch(&mut doc, &patch).unwrap();
465        assert_eq!(doc, right);
466    }
467
468    #[test]
469    fn diff_array_removal_from_middle() {
470        let left = platform_value!([1, 2, 3]);
471        let right = platform_value!([1, 3]);
472        let patch = super::diff(&left, &right);
473        let mut doc = left.clone();
474        crate::patch(&mut doc, &patch).unwrap();
475        assert_eq!(doc, right);
476    }
477
478    #[test]
479    fn diff_array_complete_replacement() {
480        let left = platform_value!([1, 2, 3]);
481        let right = platform_value!([4, 5]);
482        let patch = super::diff(&left, &right);
483        let mut doc = left.clone();
484        crate::patch(&mut doc, &patch).unwrap();
485        assert_eq!(doc, right);
486    }
487
488    // ---------------------------------------------------------------
489    // diff: nested maps
490    // ---------------------------------------------------------------
491
492    #[test]
493    fn diff_nested_map_modification() {
494        let left = platform_value!({
495            "outer": {
496                "inner": 1,
497                "keep": "same"
498            }
499        });
500        let right = platform_value!({
501            "outer": {
502                "inner": 99,
503                "keep": "same"
504            }
505        });
506        let p = super::diff(&left, &right);
507        assert_eq!(
508            p,
509            from_value(platform_value!([
510                { "op": "replace", "path": "/outer/inner", "value": 99 },
511            ]))
512            .unwrap()
513        );
514    }
515
516    #[test]
517    fn diff_nested_map_add_and_remove() {
518        let left = platform_value!({
519            "a": {
520                "b": 1,
521                "c": 2
522            }
523        });
524        let right = platform_value!({
525            "a": {
526                "c": 2,
527                "d": 3
528            }
529        });
530        let patch = super::diff(&left, &right);
531        let mut doc = left.clone();
532        crate::patch(&mut doc, &patch).unwrap();
533        assert_eq!(doc, right);
534    }
535
536    #[test]
537    fn diff_deeply_nested() {
538        let left = platform_value!({
539            "l1": {
540                "l2": {
541                    "l3": "old"
542                }
543            }
544        });
545        let right = platform_value!({
546            "l1": {
547                "l2": {
548                    "l3": "new"
549                }
550            }
551        });
552        let p = super::diff(&left, &right);
553        assert_eq!(
554            p,
555            from_value(platform_value!([
556                { "op": "replace", "path": "/l1/l2/l3", "value": "new" },
557            ]))
558            .unwrap()
559        );
560    }
561
562    // ---------------------------------------------------------------
563    // diff: tilde-escaped keys round-trip through patch
564    // ---------------------------------------------------------------
565
566    #[test]
567    fn diff_tilde_key_round_trip() {
568        let left = platform_value!({
569            "a~b": 1
570        });
571        let right = platform_value!({
572            "a~b": 2
573        });
574        let mut doc = left.clone();
575        let patch = super::diff(&left, &right);
576        crate::patch(&mut doc, &patch).unwrap();
577        assert_eq!(doc, right);
578    }
579
580    #[test]
581    fn diff_slash_key_round_trip() {
582        let left = platform_value!({
583            "x/y": 10
584        });
585        let right = platform_value!({
586            "x/y": 20
587        });
588        let mut doc = left.clone();
589        let patch = super::diff(&left, &right);
590        crate::patch(&mut doc, &patch).unwrap();
591        assert_eq!(doc, right);
592    }
593
594    // ---------------------------------------------------------------
595    // diff: null values
596    // ---------------------------------------------------------------
597
598    #[test]
599    fn diff_both_null_returns_empty() {
600        let p = super::diff(&Value::Null, &Value::Null);
601        assert!(p.0.is_empty());
602    }
603
604    #[test]
605    fn diff_null_to_value() {
606        let left = Value::Null;
607        let right = platform_value!(42);
608        let p = super::diff(&left, &right);
609        assert_eq!(
610            p,
611            from_value(platform_value!([
612                { "op": "replace", "path": "/", "value": 42 },
613            ]))
614            .unwrap()
615        );
616    }
617
618    #[test]
619    fn diff_value_to_null() {
620        let left = platform_value!(42);
621        let right = Value::Null;
622        let p = super::diff(&left, &right);
623        assert_eq!(
624            p,
625            from_value(platform_value!([
626                { "op": "replace", "path": "/", "value": null },
627            ]))
628            .unwrap()
629        );
630    }
631
632    // ---------------------------------------------------------------
633    // diff: mixed types
634    // ---------------------------------------------------------------
635
636    #[test]
637    fn diff_scalar_to_map() {
638        let left = platform_value!(42);
639        let right = platform_value!({"a": 1});
640        let p = super::diff(&left, &right);
641        assert_eq!(
642            p,
643            from_value(platform_value!([
644                { "op": "replace", "path": "/", "value": {"a": 1} },
645            ]))
646            .unwrap()
647        );
648    }
649
650    #[test]
651    fn diff_array_with_nested_maps() {
652        let left = platform_value!([{"name": "alice"}, {"name": "bob"}]);
653        let right = platform_value!([{"name": "alice"}, {"name": "charlie"}]);
654        let patch = super::diff(&left, &right);
655        let mut doc = left.clone();
656        crate::patch(&mut doc, &patch).unwrap();
657        assert_eq!(doc, right);
658    }
659}
platform_value/patch/diff.rs

platform_value/patch/
diff.rs
