dialcache/protocol/
mismatch.rs

1//! The built-in confirmed-mismatch difference: a walk over two JSON values
2//! that reports RFC 6901 pointers with the sides found there.
3
4use std::fmt::Write;
5
6use serde_json::Value;
7
8use crate::identity::compare_utf16;
9use crate::operation::MismatchEntry;
10use crate::preview::{
11    clamp_utf8, SHADOW_MISMATCH_MAX_DEPTH, SHADOW_MISMATCH_MAX_ENTRIES,
12    SHADOW_MISMATCH_PATH_MAX_BYTES, SHADOW_MISMATCH_SIDE_MAX_BYTES,
13};
14
15/// The capped built-in difference list and its uncut length.
16#[derive(Debug, Clone, PartialEq)]
17pub struct MismatchJsonDiff {
18    /// Bounded entries in walk order, at most
19    /// [`SHADOW_MISMATCH_MAX_ENTRIES`](crate::preview::SHADOW_MISMATCH_MAX_ENTRIES).
20    pub entries: Vec<MismatchEntry>,
21    /// Every difference the walk found, before the cut.
22    pub count: u64,
23}
24
25/// The built-in difference computation over two JSON values.
26///
27/// Objects recurse over the union of their member names in UTF-16 code-unit
28/// order, and a member present on one side only is reported at its pointer
29/// with that side. Arrays of equal length recurse by index; arrays of
30/// different length are reported once at their own pointer. Any other
31/// differing pair, roots of different kinds included, is reported at its
32/// pointer with both sides, and a differing pair of containers at
33/// [`SHADOW_MISMATCH_MAX_DEPTH`](crate::preview::SHADOW_MISMATCH_MAX_DEPTH)
34/// reference tokens is reported whole without descending. Numbers compare by
35/// value as doubles, so `1` and `1.0` are equal. Entries keep walk order and
36/// are cut at
37/// [`SHADOW_MISMATCH_MAX_ENTRIES`](crate::preview::SHADOW_MISMATCH_MAX_ENTRIES);
38/// `count` is the uncut total. Each pointer is clamped to
39/// [`SHADOW_MISMATCH_PATH_MAX_BYTES`](crate::preview::SHADOW_MISMATCH_PATH_MAX_BYTES),
40/// and a side whose JSON exceeds
41/// [`SHADOW_MISMATCH_SIDE_MAX_BYTES`](crate::preview::SHADOW_MISMATCH_SIDE_MAX_BYTES)
42/// becomes its clamped JSON text as a string.
43pub fn diff_shadow_mismatch_json(cached: &Value, source: &Value) -> MismatchJsonDiff {
44    let walk = walk_json(cached, source);
45    MismatchJsonDiff {
46        entries: walk
47            .entries
48            .iter()
49            .map(|entry| bound_entry(&entry.path, entry.cached, entry.source, true))
50            .collect(),
51        count: walk.count,
52    }
53}
54
55/// The difference between two renderings, `None` for an absent side. Equal
56/// texts have no entries; one absent side is reported whole at the root.
57/// `with_values` keeps the bounded sides; without it entries carry paths only.
58pub(crate) fn diff_rendered(
59    cached: Option<&str>,
60    source: Option<&str>,
61    with_values: bool,
62) -> Result<MismatchJsonDiff, serde_json::Error> {
63    if cached == source {
64        return Ok(MismatchJsonDiff {
65            entries: Vec::new(),
66            count: 0,
67        });
68    }
69    let cached: Option<Value> = cached.map(serde_json::from_str).transpose()?;
70    let source: Option<Value> = source.map(serde_json::from_str).transpose()?;
71    let (cached, source) = match (&cached, &source) {
72        (Some(cached), Some(source)) => (cached, source),
73        _ => {
74            return Ok(MismatchJsonDiff {
75                entries: vec![bound_entry(
76                    "",
77                    cached.as_ref(),
78                    source.as_ref(),
79                    with_values,
80                )],
81                count: 1,
82            })
83        }
84    };
85    let walk = walk_json(cached, source);
86    Ok(MismatchJsonDiff {
87        entries: walk
88            .entries
89            .iter()
90            .map(|entry| bound_entry(&entry.path, entry.cached, entry.source, with_values))
91            .collect(),
92        count: walk.count,
93    })
94}
95
96/// The one clamp rule for built-in and hook entries: the pointer is clamped,
97/// and with `with_values` each present side is kept as JSON, or as its
98/// clamped text when its rendering exceeds the side cap.
99pub(crate) fn bound_entry(
100    path: &str,
101    cached: Option<&Value>,
102    source: Option<&Value>,
103    with_values: bool,
104) -> MismatchEntry {
105    let side = |value: Option<&Value>| value.filter(|_| with_values).map(bound_side);
106    MismatchEntry {
107        path: clamp_utf8(path, SHADOW_MISMATCH_PATH_MAX_BYTES),
108        cached: side(cached),
109        source: side(source),
110    }
111}
112
113fn bound_side(value: &Value) -> Value {
114    match serde_json::to_string(value) {
115        Ok(json) if json.len() > SHADOW_MISMATCH_SIDE_MAX_BYTES => {
116            Value::String(clamp_utf8(&json, SHADOW_MISMATCH_SIDE_MAX_BYTES))
117        }
118        _ => value.clone(),
119    }
120}
121
122/// One difference as the walk holds it, before the clamps.
123struct RawEntry<'a> {
124    path: String,
125    cached: Option<&'a Value>,
126    source: Option<&'a Value>,
127}
128
129/// One unescaped reference token of the pointer to the walk's position.
130#[derive(Clone, Copy)]
131enum Token<'a> {
132    Index(usize),
133    Name(&'a str),
134}
135
136struct Walk<'a> {
137    entries: Vec<RawEntry<'a>>,
138    count: u64,
139    /// The pointer to the current position, as tokens, so descending costs
140    /// no copy of the prefix.
141    tokens: Vec<Token<'a>>,
142}
143
144impl<'a> Walk<'a> {
145    fn report(&mut self, cached: Option<&'a Value>, source: Option<&'a Value>) {
146        self.count += 1;
147        if self.entries.len() < SHADOW_MISMATCH_MAX_ENTRIES {
148            self.entries.push(RawEntry {
149                path: self.pointer(),
150                cached,
151                source,
152            });
153        }
154    }
155
156    /// The escaped pointer to the current position, built only as far as
157    /// [`SHADOW_MISMATCH_PATH_MAX_BYTES`] reads: past the cap it stops at a
158    /// character boundary, and that prefix clamps as the whole pointer would.
159    /// So a retained entry costs at most the cap, however long and deep the
160    /// member names above it.
161    fn pointer(&self) -> String {
162        let mut pointer = String::new();
163        for token in &self.tokens {
164            if pointer.len() > SHADOW_MISMATCH_PATH_MAX_BYTES {
165                break;
166            }
167            pointer.push('/');
168            match *token {
169                Token::Index(index) => {
170                    let _ = write!(pointer, "{index}");
171                }
172                Token::Name(name) => {
173                    for c in name.chars() {
174                        if pointer.len() > SHADOW_MISMATCH_PATH_MAX_BYTES {
175                            break;
176                        }
177                        match c {
178                            '~' => pointer.push_str("~0"),
179                            '/' => pointer.push_str("~1"),
180                            c => pointer.push(c),
181                        }
182                    }
183                }
184            }
185        }
186        pointer
187    }
188
189    fn walk(&mut self, left: &'a Value, right: &'a Value) {
190        let kind = Kind::of(left);
191        if kind != Kind::of(right) || kind == Kind::Primitive {
192            if !primitives_equal(left, right) {
193                self.report(Some(left), Some(right));
194            }
195            return;
196        }
197        if self.tokens.len() >= SHADOW_MISMATCH_MAX_DEPTH {
198            if !json_values_equal(left, right) {
199                self.report(Some(left), Some(right));
200            }
201            return;
202        }
203        match (left, right) {
204            (Value::Array(left_items), Value::Array(right_items)) => {
205                if left_items.len() != right_items.len() {
206                    self.report(Some(left), Some(right));
207                    return;
208                }
209                for (index, (l, r)) in left_items.iter().zip(right_items).enumerate() {
210                    self.tokens.push(Token::Index(index));
211                    self.walk(l, r);
212                    self.tokens.pop();
213                }
214            }
215            (Value::Object(left_members), Value::Object(right_members)) => {
216                let mut names: Vec<&String> = left_members.keys().collect();
217                names.extend(
218                    right_members
219                        .keys()
220                        .filter(|name| !left_members.contains_key(*name)),
221                );
222                names.sort_by(|a, b| compare_utf16(a, b));
223                for name in names {
224                    self.tokens.push(Token::Name(name));
225                    match (left_members.get(name), right_members.get(name)) {
226                        (Some(l), Some(r)) => self.walk(l, r),
227                        (l, r) => self.report(l, r),
228                    }
229                    self.tokens.pop();
230                }
231            }
232            _ => unreachable!("both values share a container kind"),
233        }
234    }
235}
236
237fn walk_json<'a>(cached: &'a Value, source: &'a Value) -> Walk<'a> {
238    let mut walk = Walk {
239        entries: Vec::new(),
240        count: 0,
241        tokens: Vec::new(),
242    };
243    walk.walk(cached, source);
244    walk
245}
246
247#[derive(Clone, Copy, PartialEq, Eq)]
248enum Kind {
249    Array,
250    Object,
251    Primitive,
252}
253
254impl Kind {
255    fn of(value: &Value) -> Kind {
256        match value {
257            Value::Array(_) => Kind::Array,
258            Value::Object(_) => Kind::Object,
259            _ => Kind::Primitive,
260        }
261    }
262}
263
264/// JSON primitive equality as JavaScript's `===` sees parsed JSON: numbers by
265/// their double value, everything else exactly.
266fn primitives_equal(left: &Value, right: &Value) -> bool {
267    match (left, right) {
268        (Value::Number(l), Value::Number(r)) => l.as_f64() == r.as_f64(),
269        _ => left == right,
270    }
271}
272
273// Structural equality for a depth-capped pair, iterative so that a subtree as
274// deep as the parser allows cannot exhaust the stack.
275fn json_values_equal(cached: &Value, source: &Value) -> bool {
276    let mut pending = vec![(cached, source)];
277    while let Some((left, right)) = pending.pop() {
278        match (left, right) {
279            (Value::Array(l), Value::Array(r)) => {
280                if l.len() != r.len() {
281                    return false;
282                }
283                pending.extend(l.iter().zip(r));
284            }
285            (Value::Object(l), Value::Object(r)) => {
286                if l.len() != r.len() {
287                    return false;
288                }
289                for (name, value) in l {
290                    let Some(other) = r.get(name) else {
291                        return false;
292                    };
293                    pending.push((value, other));
294                }
295            }
296            _ => {
297                if Kind::of(left) != Kind::of(right) || !primitives_equal(left, right) {
298                    return false;
299                }
300            }
301        }
302    }
303    true
304}
dialcache/protocol/mismatch.rs

dialcache/protocol/
mismatch.rs
