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}