Skip to main content

jsonx_lib/
parser.rs

1//! The configured parser and the tree builder.
2
3use alloc::{borrow::Cow, vec::Vec};
4
5use crate::{
6    Array, Limits, Object, Reader, Value,
7    error::{Error, ErrorKind},
8    reader::Event,
9    tree::Member,
10};
11
12/// What to do when an object names the same key twice.
13///
14/// RFC 8259 says names within an object SHOULD be unique and leaves the
15/// behaviour for duplicates to the implementation; implementations disagree,
16/// which makes duplicates a classic way to smuggle a different value past one
17/// reader than another sees. The default is therefore to refuse them.
18/// Keys are compared after unescaping, so `"a"` and `"\u0061"` are the same
19/// key.
20///
21/// The enum is `#[non_exhaustive]`: a later version may add a policy.
22///
23/// # Examples
24///
25/// ```
26/// use jsonx_lib::{DuplicateKeys, ErrorKind, Parser};
27///
28/// let text = r#"{"a": 1, "b": 2, "a": 3}"#;
29///
30/// let err = Parser::new().parse(text).unwrap_err();
31/// assert_eq!((err.kind(), err.offset()), (ErrorKind::DuplicateKey, 17));
32///
33/// let first = Parser::new().duplicate_keys(DuplicateKeys::First).parse(text)?;
34/// assert_eq!(first.to_string(), r#"{"a":1,"b":2}"#);
35///
36/// let last = Parser::new().duplicate_keys(DuplicateKeys::Last).parse(text)?;
37/// assert_eq!(last.to_string(), r#"{"a":3,"b":2}"#);
38///
39/// let all = Parser::new().duplicate_keys(DuplicateKeys::KeepAll).parse(text)?;
40/// assert_eq!(all.to_string(), r#"{"a":1,"b":2,"a":3}"#);
41/// # Ok::<(), jsonx_lib::Error>(())
42/// ```
43#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
44#[non_exhaustive]
45pub enum DuplicateKeys {
46    /// Refuse the document with [`ErrorKind::DuplicateKey`] at the second
47    /// occurrence's opening quote. The default.
48    #[default]
49    Error,
50    /// Keep the first occurrence and its value; drop the later ones.
51    First,
52    /// Keep the last occurrence's value, at the first occurrence's position,
53    /// as inserting each member into an ordered map would.
54    Last,
55    /// Keep every member as written. The writer reproduces the duplicates.
56    KeepAll,
57}
58
59/// A configured parser: [`Limits`] and a [`DuplicateKeys`] policy.
60///
61/// [`parse`](crate::parse) is `Parser::new().parse`. Build a `Parser` to
62/// change a budget or the duplicate-key policy; it is a small `Copy` value
63/// that can be kept in a `const` or a struct and reused for any number of
64/// documents.
65///
66/// # Examples
67///
68/// ```
69/// use jsonx_lib::{DuplicateKeys, ErrorKind, Limits, Parser};
70///
71/// // Messages from the network: small and shallow.
72/// const WIRE: Parser = Parser::new()
73///     .limits(Limits::new().with_max_input_bytes(1 << 20).with_max_depth(32))
74///     .duplicate_keys(DuplicateKeys::Error);
75///
76/// assert!(WIRE.parse(r#"{"ok": true}"#).is_ok());
77/// let deep = "[".repeat(33);
78/// assert_eq!(WIRE.parse(&deep).unwrap_err().kind(), ErrorKind::DepthLimitExceeded);
79/// ```
80#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
81#[must_use]
82pub struct Parser {
83    limits: Limits,
84    duplicates: DuplicateKeys,
85}
86
87impl Parser {
88    /// A parser with the default [`Limits`] and [`DuplicateKeys::Error`].
89    ///
90    /// # Examples
91    ///
92    /// ```
93    /// assert_eq!(jsonx_lib::Parser::new().parse("[]")?.to_string(), "[]");
94    /// # Ok::<(), jsonx_lib::Error>(())
95    /// ```
96    pub const fn new() -> Self {
97        Self {
98            limits: Limits::new(),
99            duplicates: DuplicateKeys::Error,
100        }
101    }
102
103    /// Replaces the budgets.
104    ///
105    /// # Examples
106    ///
107    /// ```
108    /// use jsonx_lib::{ErrorKind, Limits, Parser};
109    ///
110    /// let p = Parser::new().limits(Limits::new().with_max_string_bytes(3));
111    /// assert_eq!(p.parse(r#""four""#).unwrap_err().kind(), ErrorKind::StringTooLong);
112    /// ```
113    pub const fn limits(mut self, limits: Limits) -> Self {
114        self.limits = limits;
115        self
116    }
117
118    /// Sets the duplicate-key policy.
119    ///
120    /// # Examples
121    ///
122    /// ```
123    /// use jsonx_lib::{DuplicateKeys, Parser};
124    ///
125    /// let p = Parser::new().duplicate_keys(DuplicateKeys::Last);
126    /// assert_eq!(p.parse(r#"{"k": 1, "k": 2}"#)?["k"], 2);
127    /// # Ok::<(), jsonx_lib::Error>(())
128    /// ```
129    pub const fn duplicate_keys(mut self, policy: DuplicateKeys) -> Self {
130        self.duplicates = policy;
131        self
132    }
133
134    /// The parser's budgets.
135    ///
136    /// # Examples
137    ///
138    /// ```
139    /// assert_eq!(jsonx_lib::Parser::new().get_limits().max_depth, 128);
140    /// ```
141    #[must_use]
142    pub const fn get_limits(&self) -> Limits {
143        self.limits
144    }
145
146    /// The parser's duplicate-key policy.
147    ///
148    /// # Examples
149    ///
150    /// ```
151    /// use jsonx_lib::{DuplicateKeys, Parser};
152    ///
153    /// assert_eq!(Parser::new().get_duplicate_keys(), DuplicateKeys::Error);
154    /// ```
155    #[must_use]
156    pub const fn get_duplicate_keys(&self) -> DuplicateKeys {
157        self.duplicates
158    }
159
160    /// Parses one JSON document.
161    ///
162    /// The whole input must be exactly one value, with optional whitespace
163    /// around it (space, tab, line feed, carriage return; nothing else, not
164    /// even a byte-order mark). Strings without escapes and all numbers borrow
165    /// from `text`.
166    ///
167    /// # Errors
168    ///
169    /// The first syntax error or exceeded budget, at its byte offset; see
170    /// [`ErrorKind`] for every case.
171    ///
172    /// # Examples
173    ///
174    /// ```
175    /// use jsonx_lib::{ErrorKind, Parser};
176    ///
177    /// let v = Parser::new().parse(" [1, \"two\"] ")?;
178    /// assert_eq!(v[1], "two");
179    ///
180    /// let err = Parser::new().parse("[1] [2]").unwrap_err();
181    /// assert_eq!((err.kind(), err.offset()), (ErrorKind::TrailingCharacters, 4));
182    /// # Ok::<(), jsonx_lib::Error>(())
183    /// ```
184    pub fn parse<'a>(&self, text: &'a str) -> Result<Value<'a>, Error> {
185        let mut reader = self.reader(text);
186        let value = reader
187            .read_value()?
188            .ok_or(Error::new(ErrorKind::UnexpectedEnd, text.len()))?;
189        reader.finish()?;
190        Ok(value)
191    }
192
193    /// Parses one JSON document from bytes, which must be UTF-8 (RFC 8259
194    /// ยง8.1). The size budget is checked first, then the encoding, then the
195    /// syntax.
196    ///
197    /// # Errors
198    ///
199    /// [`ErrorKind::InputTooLarge`], then [`ErrorKind::InvalidUtf8`] at the
200    /// first byte of the first invalid sequence, then as
201    /// [`parse`](Self::parse).
202    ///
203    /// # Examples
204    ///
205    /// ```
206    /// use jsonx_lib::{ErrorKind, Parser};
207    ///
208    /// assert_eq!(Parser::new().parse_bytes(b"[\"\xC3\xA9\"]")?[0], "\u{e9}");
209    /// let err = Parser::new().parse_bytes(b"[\"\xC3\"]").unwrap_err();
210    /// assert_eq!((err.kind(), err.offset()), (ErrorKind::InvalidUtf8, 2));
211    /// # Ok::<(), jsonx_lib::Error>(())
212    /// ```
213    pub fn parse_bytes<'a>(&self, bytes: &'a [u8]) -> Result<Value<'a>, Error> {
214        self.parse(self.check_bytes(bytes)?)
215    }
216
217    /// A [`Reader`] over `text` with this parser's budgets and duplicate-key
218    /// policy (which [`Reader::read_value`] applies).
219    ///
220    /// # Examples
221    ///
222    /// ```
223    /// use jsonx_lib::{ErrorKind, Limits, Parser};
224    ///
225    /// let mut r = Parser::new().limits(Limits::new().with_max_depth(1)).reader("[[]]");
226    /// assert!(r.next_event().is_ok());
227    /// assert_eq!(r.next_event().unwrap_err().kind(), ErrorKind::DepthLimitExceeded);
228    /// ```
229    #[must_use]
230    pub fn reader<'a>(&self, text: &'a str) -> Reader<'a> {
231        Reader::with_config(text, self.limits, self.duplicates)
232    }
233
234    /// A [`Reader`] over bytes, which must be UTF-8. The size budget and the
235    /// encoding are checked here, before any event is read.
236    ///
237    /// # Errors
238    ///
239    /// [`ErrorKind::InputTooLarge`] or [`ErrorKind::InvalidUtf8`].
240    ///
241    /// # Examples
242    ///
243    /// ```
244    /// use jsonx_lib::{Event, Parser};
245    ///
246    /// let mut r = Parser::new().reader_bytes(b"null")?;
247    /// assert_eq!(r.next_event()?, Some(Event::Null));
248    /// # Ok::<(), jsonx_lib::Error>(())
249    /// ```
250    pub fn reader_bytes<'a>(&self, bytes: &'a [u8]) -> Result<Reader<'a>, Error> {
251        Ok(self.reader(self.check_bytes(bytes)?))
252    }
253
254    fn check_bytes<'a>(&self, bytes: &'a [u8]) -> Result<&'a str, Error> {
255        if bytes.len() > self.limits.max_input_bytes {
256            return Err(Error::new(
257                ErrorKind::InputTooLarge,
258                self.limits.max_input_bytes,
259            ));
260        }
261        core::str::from_utf8(bytes).map_err(|e| Error::new(ErrorKind::InvalidUtf8, e.valid_up_to()))
262    }
263}
264
265/// An open container in the builder: where its children start on the shared
266/// value and key stacks.
267#[derive(Clone, Copy)]
268struct Frame {
269    values: usize,
270    keys: usize,
271}
272
273/// Buffers reused by every object's duplicate check in one build.
274#[derive(Default)]
275struct Scratch {
276    order: Vec<usize>,
277    keep: Vec<bool>,
278}
279
280/// Builds the value whose first event comes next from `reader`.
281///
282/// Children of every open container sit on one shared value stack; when a
283/// container closes, its children are moved off the top into a vector of
284/// exactly their size. Nothing recurses, and no container's vector ever grows
285/// by reallocation.
286pub(crate) fn build<'a>(
287    reader: &mut Reader<'a>,
288    policy: DuplicateKeys,
289) -> Result<Value<'a>, Error> {
290    let mut values: Vec<Value<'a>> = Vec::new();
291    let mut keys: Vec<(Cow<'a, str>, usize)> = Vec::new();
292    let mut frames: Vec<Frame> = Vec::new();
293    let mut scratch = Scratch::default();
294    loop {
295        let Some(event) = reader.next_event()? else {
296            // The reader ends a document only after a complete value.
297            return Err(Error::new(ErrorKind::UnexpectedEnd, reader.offset()));
298        };
299        let value = match event {
300            Event::StartArray | Event::StartObject => {
301                frames.push(Frame {
302                    values: values.len(),
303                    keys: keys.len(),
304                });
305                continue;
306            }
307            Event::Key(key) => {
308                keys.push((key, reader.event_offset()));
309                continue;
310            }
311            Event::EndArray => {
312                let Some(frame) = frames.pop() else {
313                    return Err(Error::new(ErrorKind::ExpectedValue, reader.event_offset()));
314                };
315                Value::Array(Array::from(values.split_off(frame.values)))
316            }
317            Event::EndObject => {
318                let Some(frame) = frames.pop() else {
319                    return Err(Error::new(ErrorKind::ExpectedValue, reader.event_offset()));
320                };
321                Value::Object(close_object(
322                    &mut values,
323                    &mut keys,
324                    frame,
325                    policy,
326                    &mut scratch,
327                )?)
328            }
329            Event::String(s) => Value::String(s),
330            Event::Number(n) => Value::Number(n),
331            Event::Bool(b) => Value::Bool(b),
332            Event::Null => Value::Null,
333        };
334        if frames.is_empty() {
335            return Ok(value);
336        }
337        values.push(value);
338    }
339}
340
341#[inline]
342fn key_at<'k>(keys: &'k [(Cow<'_, str>, usize)], i: usize) -> &'k str {
343    keys.get(i).map_or("", |(k, _)| k)
344}
345
346/// Moves the closing object's members off the stacks, applying `policy`.
347fn close_object<'a>(
348    values: &mut Vec<Value<'a>>,
349    keys: &mut Vec<(Cow<'a, str>, usize)>,
350    frame: Frame,
351    policy: DuplicateKeys,
352    scratch: &mut Scratch,
353) -> Result<Object<'a>, Error> {
354    let member_keys = keys.get(frame.keys..).unwrap_or(&[]);
355    let mut dedupe = false;
356    if policy != DuplicateKeys::KeepAll && has_duplicates(member_keys, &mut scratch.order) {
357        match policy {
358            DuplicateKeys::First | DuplicateKeys::Last => {
359                mark_duplicates(member_keys, policy, scratch, values, frame.values);
360                dedupe = true;
361            }
362            _ => {
363                let at = first_repeat(member_keys, &scratch.order);
364                let offset = member_keys.get(at).map_or(0, |(_, o)| *o);
365                return Err(Error::new(ErrorKind::DuplicateKey, offset));
366            }
367        }
368    }
369    let pairs = keys
370        .drain(frame.keys..)
371        .map(|(k, _)| k)
372        .zip(values.drain(frame.values..));
373    let members: Vec<Member<'a>> = if dedupe {
374        pairs
375            .zip(scratch.keep.iter())
376            .filter_map(|(member, &keep)| keep.then_some(member))
377            .collect()
378    } else {
379        pairs.collect()
380    };
381    Ok(Object::from(members))
382}
383
384/// Whether any key repeats. Small objects are checked pairwise; larger ones
385/// by sorting indices (`O(n log n)`), which also leaves `order` sorted by
386/// (key, position) for [`first_repeat`] and [`mark_duplicates`].
387fn has_duplicates(keys: &[(Cow<'_, str>, usize)], order: &mut Vec<usize>) -> bool {
388    const PAIRWISE: usize = 16;
389    let n = keys.len();
390    if n < 2 {
391        return false;
392    }
393    if n <= PAIRWISE {
394        // At most 120 one-word comparisons; the strings themselves are
395        // compared only when their fingerprints match.
396        let mut prints = [0u64; PAIRWISE];
397        for (slot, (key, _)) in prints.iter_mut().zip(keys) {
398            *slot = fingerprint(key);
399        }
400        let prints = prints.get(..n).unwrap_or(&[]);
401        let any = prints.iter().enumerate().skip(1).any(|(i, a)| {
402            prints
403                .iter()
404                .take(i)
405                .enumerate()
406                .any(|(j, b)| a == b && key_at(keys, i) == key_at(keys, j))
407        });
408        if !any {
409            return false;
410        }
411    }
412    order.clear();
413    order.extend(0..n);
414    order.sort_unstable_by(|&a, &b| key_at(keys, a).cmp(key_at(keys, b)).then(a.cmp(&b)));
415    order.windows(2).any(|w| match w {
416        [a, b] => key_at(keys, *a) == key_at(keys, *b),
417        _ => false,
418    })
419}
420
421/// A cheap summary of a key: equal keys have equal fingerprints. The length
422/// and the first eight bytes, which tell most distinct keys apart.
423#[inline]
424fn fingerprint(key: &str) -> u64 {
425    let bytes = key.as_bytes();
426    let mut head = [0u8; 8];
427    for (slot, &b) in head.iter_mut().zip(bytes) {
428        *slot = b;
429    }
430    u64::from_le_bytes(head) ^ (bytes.len() as u64).rotate_left(56)
431}
432
433/// Calls `f(run)` for each run of equal keys in `order` (each run sorted by
434/// position, the first being the first occurrence).
435fn for_each_run(keys: &[(Cow<'_, str>, usize)], order: &[usize], mut f: impl FnMut(&[usize])) {
436    let mut start = 0;
437    while start < order.len() {
438        let first = key_at(keys, order.get(start).copied().unwrap_or(0));
439        let mut end = start + 1;
440        while order.get(end).is_some_and(|&i| key_at(keys, i) == first) {
441            end += 1;
442        }
443        if end - start > 1 {
444            f(order.get(start..end).unwrap_or(&[]));
445        }
446        start = end;
447    }
448}
449
450/// The position of the earliest member whose key repeats an earlier one.
451fn first_repeat(keys: &[(Cow<'_, str>, usize)], order: &[usize]) -> usize {
452    let mut earliest = usize::MAX;
453    for_each_run(keys, order, |run| {
454        if let Some(&second) = run.get(1) {
455            earliest = earliest.min(second);
456        }
457    });
458    earliest
459}
460
461/// Fills `scratch.keep` with which members survive the policy, and for
462/// [`DuplicateKeys::Last`] moves each repeated key's last value to its first
463/// position.
464fn mark_duplicates(
465    keys: &[(Cow<'_, str>, usize)],
466    policy: DuplicateKeys,
467    scratch: &mut Scratch,
468    values: &mut [Value<'_>],
469    base: usize,
470) {
471    let keep = &mut scratch.keep;
472    keep.clear();
473    keep.resize(keys.len(), true);
474    for_each_run(keys, &scratch.order, |run| {
475        let (Some(&first), Some(&last)) = (run.first(), run.last()) else {
476            return;
477        };
478        if policy == DuplicateKeys::Last {
479            values.swap(base + first, base + last);
480        }
481        for &i in run.get(1..).unwrap_or(&[]) {
482            if let Some(slot) = keep.get_mut(i) {
483                *slot = false;
484            }
485        }
486    });
487}
488
489#[cfg(test)]
490mod tests {
491    use super::*;
492
493    #[test]
494    fn test_duplicate_detection_small_and_large() {
495        let small = r#"{"a":1,"b":2,"c":3}"#;
496        assert!(Parser::new().parse(small).is_ok());
497        let mut large = alloc::string::String::from("{");
498        for i in 0..100 {
499            large.push_str(&alloc::format!("\"k{i}\":{i},"));
500        }
501        large.push_str("\"k50\":0,\"k7\":0}");
502        let err = Parser::new().parse(&large).unwrap_err();
503        assert_eq!(err.kind(), ErrorKind::DuplicateKey);
504        assert_eq!(large.get(err.offset()..err.offset() + 6), Some("\"k50\":"));
505        let last = Parser::new()
506            .duplicate_keys(DuplicateKeys::Last)
507            .parse(&large);
508        let last = last.unwrap_or_default();
509        assert_eq!(last.as_object().map(Object::len), Some(100));
510        assert_eq!(last["k50"], 0);
511        assert_eq!(last["k7"], 0);
512        assert_eq!(last.as_object().and_then(|o| o.keys().nth(50)), Some("k50"));
513        let first = Parser::new()
514            .duplicate_keys(DuplicateKeys::First)
515            .parse(&large);
516        assert_eq!(first.unwrap_or_default()["k50"], 50);
517    }
518
519    #[test]
520    fn test_duplicates_compare_decoded_keys() {
521        let err = Parser::new().parse(r#"{"a":1,"\u0061":2}"#).unwrap_err();
522        assert_eq!((err.kind(), err.offset()), (ErrorKind::DuplicateKey, 7));
523    }
524
525    proptest::proptest! {
526        /// Every policy matches a naive quadratic reference, across the
527        /// pairwise and sorting paths, with keys that share long prefixes
528        /// (equal fingerprints, different strings).
529        #[test]
530        fn prop_duplicate_policies_match_naive(picks in proptest::collection::vec(0usize..12, 0..40)) {
531            use alloc::{format, string::String, vec::Vec};
532            const KEYS: [&str; 12] = [
533                "a", "b", "abcdefgh1", "abcdefgh2", "abcdefgh12", "abcdefghX", "", "k",
534                "abcdefgh", "abcdefgi", "zz", "abcdefgh1\\u0000",
535            ];
536            let decoded = |k: &str| k.replace("\\u0000", "\u{0}");
537            let mut text = String::from("{");
538            let mut offsets = Vec::new();
539            for (i, &p) in picks.iter().enumerate() {
540                if i > 0 { text.push(','); }
541                offsets.push(text.len());
542                text.push_str(&format!("\"{}\":{i}", KEYS[p]));
543            }
544            text.push('}');
545            let names: Vec<String> = picks.iter().map(|&p| decoded(KEYS[p])).collect();
546
547            // Error: the earliest member whose key appeared before.
548            let repeat = (0..names.len()).find(|&i| names[..i].contains(&names[i]));
549            let got = Parser::new().parse(&text).err().map(|e| (e.kind(), e.offset()));
550            proptest::prop_assert_eq!(got, repeat.map(|i| (ErrorKind::DuplicateKey, offsets[i])));
551
552            // First and Last: one member per key, at its first position.
553            let mut order: Vec<&String> = Vec::new();
554            for n in &names { if !order.contains(&n) { order.push(n); } }
555            let first = Parser::new().duplicate_keys(DuplicateKeys::First).parse(&text).unwrap_or_default();
556            let last = Parser::new().duplicate_keys(DuplicateKeys::Last).parse(&text).unwrap_or_default();
557            let (fo, lo) = (first.as_object().cloned().unwrap_or_default(), last.as_object().cloned().unwrap_or_default());
558            proptest::prop_assert_eq!(fo.keys().collect::<Vec<_>>(), order.iter().map(|s| s.as_str()).collect::<Vec<_>>());
559            proptest::prop_assert_eq!(lo.keys().collect::<Vec<_>>(), order.iter().map(|s| s.as_str()).collect::<Vec<_>>());
560            for key in &order {
561                let want_first = names.iter().position(|n| n == *key);
562                let want_last = names.iter().rposition(|n| n == *key);
563                proptest::prop_assert_eq!(fo.get(key).and_then(Value::as_u64), want_first.map(|i| i as u64));
564                proptest::prop_assert_eq!(lo.get(key).and_then(Value::as_u64), want_last.map(|i| i as u64));
565            }
566        }
567    }
568
569    #[test]
570    fn test_duplicate_reported_at_earliest_repeat() {
571        // `b` repeats before `a` does.
572        let err = Parser::new()
573            .parse(r#"{"a":1,"b":2,"b":3,"a":4}"#)
574            .unwrap_err();
575        assert_eq!(err.offset(), 13);
576    }
577}