jsonx_lib/parser.rs
1//! The configured parser and the tree builder.
2
3use alloc::{borrow::Cow, vec::Vec};
4use core::mem::size_of;
5
6use crate::{
7 Array, Limits, Object, Reader, Value, dupes,
8 error::{Error, ErrorKind},
9 reader::Event,
10 small::SmallStack,
11 tree::Member,
12};
13
14/// What to do when an object names the same key twice.
15///
16/// RFC 8259 says names within an object SHOULD be unique and leaves the
17/// behaviour for duplicates to the implementation; implementations disagree,
18/// which makes duplicates a classic way to smuggle a different value past one
19/// reader than another sees. The default is therefore to refuse them.
20/// Keys are compared after unescaping, so `"a"` and `"\u0061"` are the same
21/// key.
22///
23/// The policy applies to every way of reading: [`Parser::parse`], and the
24/// [`Reader`]s it makes, whose events and raw slices refuse a duplicate
25/// under `Error`. Under `First`, `Last`, and `KeepAll` a reader's events
26/// carry every member as written; the values a parse or
27/// [`Reader::read_value`] builds apply the policy.
28///
29/// The enum is `#[non_exhaustive]`: a later version may add a policy.
30///
31/// # Examples
32///
33/// ```
34/// use jsonx_lib::{DuplicateKeys, ErrorKind, Parser};
35///
36/// let text = r#"{"a": 1, "b": 2, "a": 3}"#;
37///
38/// let err = Parser::new().parse(text).unwrap_err();
39/// assert_eq!((err.kind(), err.offset()), (ErrorKind::DuplicateKey, 17));
40///
41/// let first = Parser::new().duplicate_keys(DuplicateKeys::First).parse(text)?;
42/// assert_eq!(first.to_string(), r#"{"a":1,"b":2}"#);
43///
44/// let last = Parser::new().duplicate_keys(DuplicateKeys::Last).parse(text)?;
45/// assert_eq!(last.to_string(), r#"{"a":3,"b":2}"#);
46///
47/// let all = Parser::new().duplicate_keys(DuplicateKeys::KeepAll).parse(text)?;
48/// assert_eq!(all.to_string(), r#"{"a":1,"b":2,"a":3}"#);
49/// # Ok::<(), jsonx_lib::Error>(())
50/// ```
51#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
52#[non_exhaustive]
53pub enum DuplicateKeys {
54 /// Refuse the document with [`ErrorKind::DuplicateKey`] at the second
55 /// occurrence's opening quote. The default.
56 #[default]
57 Error,
58 /// Keep the first occurrence and its value; drop the later ones.
59 First,
60 /// Keep the last occurrence's value, at the first occurrence's position,
61 /// as inserting each member into an ordered map would.
62 Last,
63 /// Keep every member as written. The writer reproduces the duplicates.
64 /// [`Object::get`](crate::Object::get) then finds the *first* member with
65 /// a key (`serde_json`'s map keeps the last), and typed reads of a struct
66 /// field or a map keep the last value.
67 KeepAll,
68}
69
70/// How typed reads ([`FromJson`](crate::FromJson)) of integers treat a
71/// number written as a fraction or with an exponent.
72///
73/// JSON has one number type, and writers differ on how they spell a whole
74/// number: some write `100`, some `100.0` or `1e2`. The default reads an
75/// integer type only from integer text, as [`Number::as_i64`](crate::Number::as_i64)
76/// does, so a value that was meant as a float is never silently taken as an
77/// integer. `WholeValues` also accepts any spelling of a whole number, read
78/// exactly ([`Number::whole_value`](crate::Number::whole_value)); a
79/// fractional value is still refused.
80///
81/// The enum is `#[non_exhaustive]`.
82///
83/// # Examples
84///
85/// ```
86/// use jsonx_lib::{Numbers, Parser};
87///
88/// assert!(Parser::new().decode::<u32>("1e2").is_err());
89/// let lenient = Parser::new().numbers(Numbers::WholeValues);
90/// assert_eq!(lenient.decode::<u32>("1e2")?, 100);
91/// assert_eq!(lenient.decode::<u32>("7.0")?, 7);
92/// assert!(lenient.decode::<u32>("7.5").is_err());
93/// # Ok::<(), jsonx_lib::DecodeError>(())
94/// ```
95#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
96#[non_exhaustive]
97pub enum Numbers {
98 /// Integers from integer text only (`100`); `1e2` and `100.0` are
99 /// refused for an integer type. The default.
100 #[default]
101 IntegerText,
102 /// Integers from any spelling of a whole number (`100`, `1e2`,
103 /// `100.0`), within `i128`'s range for exponent or fraction forms.
104 WholeValues,
105}
106
107/// A configured parser: [`Limits`] and a [`DuplicateKeys`] policy.
108///
109/// [`parse`](crate::parse) is `Parser::new().parse`. Build a `Parser` to
110/// change a budget or the duplicate-key policy; it is a small `Copy` value
111/// that can be kept in a `const` or a struct and reused for any number of
112/// documents.
113///
114/// # Examples
115///
116/// ```
117/// use jsonx_lib::{DuplicateKeys, ErrorKind, Limits, Parser};
118///
119/// // Messages from the network: small and shallow.
120/// const WIRE: Parser = Parser::new()
121/// .limits(Limits::new().with_max_input_bytes(1 << 20).with_max_depth(32))
122/// .duplicate_keys(DuplicateKeys::Error);
123///
124/// assert!(WIRE.parse(r#"{"ok": true}"#).is_ok());
125/// let deep = "[".repeat(33);
126/// assert_eq!(WIRE.parse(&deep).unwrap_err().kind(), ErrorKind::DepthLimitExceeded);
127/// ```
128#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
129#[must_use]
130pub struct Parser {
131 limits: Limits,
132 duplicates: DuplicateKeys,
133 numbers: Numbers,
134}
135
136impl Parser {
137 /// A parser with the default [`Limits`] and [`DuplicateKeys::Error`].
138 ///
139 /// # Examples
140 ///
141 /// ```
142 /// assert_eq!(jsonx_lib::Parser::new().parse("[]")?.to_string(), "[]");
143 /// # Ok::<(), jsonx_lib::Error>(())
144 /// ```
145 pub const fn new() -> Self {
146 Self {
147 limits: Limits::new(),
148 duplicates: DuplicateKeys::Error,
149 numbers: Numbers::IntegerText,
150 }
151 }
152
153 /// Replaces the budgets.
154 ///
155 /// # Examples
156 ///
157 /// ```
158 /// use jsonx_lib::{ErrorKind, Limits, Parser};
159 ///
160 /// let p = Parser::new().limits(Limits::new().with_max_string_bytes(3));
161 /// assert_eq!(p.parse(r#""four""#).unwrap_err().kind(), ErrorKind::StringTooLong);
162 /// ```
163 pub const fn limits(mut self, limits: Limits) -> Self {
164 self.limits = limits;
165 self
166 }
167
168 /// Sets the duplicate-key policy.
169 ///
170 /// # Examples
171 ///
172 /// ```
173 /// use jsonx_lib::{DuplicateKeys, Parser};
174 ///
175 /// let p = Parser::new().duplicate_keys(DuplicateKeys::Last);
176 /// assert_eq!(p.parse(r#"{"k": 1, "k": 2}"#)?["k"], 2);
177 /// # Ok::<(), jsonx_lib::Error>(())
178 /// ```
179 pub const fn duplicate_keys(mut self, policy: DuplicateKeys) -> Self {
180 self.duplicates = policy;
181 self
182 }
183
184 /// Sets how typed reads take integers; see [`Numbers`].
185 ///
186 /// # Examples
187 ///
188 /// ```
189 /// use jsonx_lib::{Numbers, Parser};
190 ///
191 /// let p = Parser::new().numbers(Numbers::WholeValues);
192 /// assert_eq!(p.get_numbers(), Numbers::WholeValues);
193 /// ```
194 pub const fn numbers(mut self, numbers: Numbers) -> Self {
195 self.numbers = numbers;
196 self
197 }
198
199 /// The parser's [`Numbers`] setting.
200 ///
201 /// # Examples
202 ///
203 /// ```
204 /// assert_eq!(jsonx_lib::Parser::new().get_numbers(), jsonx_lib::Numbers::IntegerText);
205 /// ```
206 #[must_use]
207 pub const fn get_numbers(&self) -> Numbers {
208 self.numbers
209 }
210
211 /// The parser's budgets.
212 ///
213 /// # Examples
214 ///
215 /// ```
216 /// assert_eq!(jsonx_lib::Parser::new().get_limits().max_depth, 128);
217 /// ```
218 #[must_use]
219 pub const fn get_limits(&self) -> Limits {
220 self.limits
221 }
222
223 /// The parser's duplicate-key policy.
224 ///
225 /// # Examples
226 ///
227 /// ```
228 /// use jsonx_lib::{DuplicateKeys, Parser};
229 ///
230 /// assert_eq!(Parser::new().get_duplicate_keys(), DuplicateKeys::Error);
231 /// ```
232 #[must_use]
233 pub const fn get_duplicate_keys(&self) -> DuplicateKeys {
234 self.duplicates
235 }
236
237 /// Parses one JSON document.
238 ///
239 /// The whole input must be exactly one value, with optional whitespace
240 /// around it (space, tab, line feed, carriage return; nothing else, not
241 /// even a byte-order mark). Strings without escapes and all numbers borrow
242 /// from `text`.
243 ///
244 /// # Errors
245 ///
246 /// The first syntax error or exceeded budget, at its byte offset; see
247 /// [`ErrorKind`] for every case.
248 ///
249 /// # Examples
250 ///
251 /// ```
252 /// use jsonx_lib::{ErrorKind, Parser};
253 ///
254 /// let v = Parser::new().parse(" [1, \"two\"] ")?;
255 /// assert_eq!(v[1], "two");
256 ///
257 /// let err = Parser::new().parse("[1] [2]").unwrap_err();
258 /// assert_eq!((err.kind(), err.offset()), (ErrorKind::TrailingCharacters, 4));
259 /// # Ok::<(), jsonx_lib::Error>(())
260 /// ```
261 pub fn parse<'a>(&self, text: &'a str) -> Result<Value<'a>, Error> {
262 let mut reader = self.reader(text);
263 let value = reader
264 .read_value()?
265 .ok_or(Error::new(ErrorKind::UnexpectedEnd, text.len()))?;
266 reader.read_to_end()?;
267 Ok(value)
268 }
269
270 /// Parses one JSON document from bytes, which must be UTF-8 (RFC 8259
271 /// ยง8.1). The size budget is checked first, then the encoding, then the
272 /// syntax.
273 ///
274 /// # Errors
275 ///
276 /// [`ErrorKind::InputTooLarge`], then [`ErrorKind::InvalidUtf8`] at the
277 /// first byte of the first invalid sequence, then as
278 /// [`parse`](Self::parse).
279 ///
280 /// # Examples
281 ///
282 /// ```
283 /// use jsonx_lib::{ErrorKind, Parser};
284 ///
285 /// assert_eq!(Parser::new().parse_bytes(b"[\"\xC3\xA9\"]")?[0], "\u{e9}");
286 /// let err = Parser::new().parse_bytes(b"[\"\xC3\"]").unwrap_err();
287 /// assert_eq!((err.kind(), err.offset()), (ErrorKind::InvalidUtf8, 2));
288 /// # Ok::<(), jsonx_lib::Error>(())
289 /// ```
290 pub fn parse_bytes<'a>(&self, bytes: &'a [u8]) -> Result<Value<'a>, Error> {
291 self.parse(self.check_bytes(bytes)?)
292 }
293
294 /// A [`Reader`] over `text` with this parser's budgets and duplicate-key
295 /// policy (which [`Reader::read_value`] applies).
296 ///
297 /// # Examples
298 ///
299 /// ```
300 /// use jsonx_lib::{ErrorKind, Limits, Parser};
301 ///
302 /// let mut r = Parser::new().limits(Limits::new().with_max_depth(1)).reader("[[]]");
303 /// assert!(r.next_event().is_ok());
304 /// assert_eq!(r.next_event().unwrap_err().kind(), ErrorKind::DepthLimitExceeded);
305 /// ```
306 #[must_use]
307 pub fn reader<'a>(&self, text: &'a str) -> Reader<'a> {
308 Reader::with_config(text, self.limits, self.duplicates).with_numbers(self.numbers)
309 }
310
311 /// A [`Reader`] over bytes, which must be UTF-8. The size budget and the
312 /// encoding are checked here, before any event is read.
313 ///
314 /// # Errors
315 ///
316 /// [`ErrorKind::InputTooLarge`] or [`ErrorKind::InvalidUtf8`].
317 ///
318 /// # Examples
319 ///
320 /// ```
321 /// use jsonx_lib::{Event, Parser};
322 ///
323 /// let mut r = Parser::new().reader_bytes(b"null")?;
324 /// assert_eq!(r.next_event()?, Some(Event::Null));
325 /// # Ok::<(), jsonx_lib::Error>(())
326 /// ```
327 pub fn reader_bytes<'a>(&self, bytes: &'a [u8]) -> Result<Reader<'a>, Error> {
328 Ok(self.reader(self.check_bytes(bytes)?))
329 }
330
331 fn check_bytes<'a>(&self, bytes: &'a [u8]) -> Result<&'a str, Error> {
332 if bytes.len() > self.limits.max_input_bytes {
333 return Err(Error::new(
334 ErrorKind::InputTooLarge,
335 self.limits.max_input_bytes,
336 ));
337 }
338 core::str::from_utf8(bytes).map_err(|e| Error::new(ErrorKind::InvalidUtf8, e.valid_up_to()))
339 }
340}
341
342/// An open container in the builder: where its children start on the shared
343/// value and key stacks, and where it starts in the input.
344#[derive(Clone, Copy)]
345struct Frame {
346 values: usize,
347 keys: usize,
348 start: usize,
349}
350
351/// The heap a build holds, against [`Limits::max_memory`].
352struct Budget {
353 max: usize,
354 /// The finished arrays and objects, and decoded strings.
355 held: usize,
356}
357
358impl Budget {
359 /// Refuses the value at `at` if `extra` more bytes, on top of what is
360 /// held and the stacks' `stacks` bytes, would pass the budget.
361 #[inline]
362 fn allow(&self, stacks: usize, extra: usize, at: usize) -> Result<(), Error> {
363 if self.held.saturating_add(stacks).saturating_add(extra) > self.max {
364 Err(Error::new(ErrorKind::MemoryLimitExceeded, at))
365 } else {
366 Ok(())
367 }
368 }
369}
370
371/// The bytes the builder's stacks hold, at their capacity.
372#[inline]
373fn stacks(values: &Vec<Value<'_>>, keys: &Vec<Cow<'_, str>>) -> usize {
374 values.capacity() * size_of::<Value<'_>>() + keys.capacity() * size_of::<Cow<'_, str>>()
375}
376
377/// The bytes one more push onto `v` would allocate: none while it has room,
378/// otherwise its whole new buffer (vectors double, from four). The old
379/// buffer is still counted in [`stacks`] until the move, so the check covers
380/// the moment both exist.
381#[inline]
382fn growth<T>(v: &Vec<T>) -> usize {
383 if v.len() < v.capacity() {
384 0
385 } else {
386 (v.capacity() * 2).max(4) * size_of::<T>()
387 }
388}
389
390/// Buffers reused by every object's duplicate check in one build.
391#[derive(Default)]
392struct Scratch {
393 order: Vec<usize>,
394 keep: Vec<bool>,
395}
396
397/// Builds the value whose first event comes next from `reader`.
398///
399/// Children of every open container sit on one shared value stack; when a
400/// container closes, its children are moved off the top into a vector of
401/// exactly their size, except the outermost array, which takes the stack
402/// itself. Nothing recurses, and no container's vector other than that
403/// outermost one (the value stack, which grows by doubling) ever grows by
404/// reallocation. What the build holds is charged against `max_memory`
405/// before it is allocated (see [`Limits`]).
406pub(crate) fn build<'a>(
407 reader: &mut Reader<'a>,
408 policy: DuplicateKeys,
409) -> Result<Value<'a>, Error> {
410 let mut values: Vec<Value<'a>> = Vec::new();
411 let mut keys: Vec<Cow<'a, str>> = Vec::new();
412 // The open containers: a message's few levels live inline.
413 let mut frames: SmallStack<Frame, 16> = SmallStack::new(Frame {
414 values: 0,
415 keys: 0,
416 start: 0,
417 });
418 let mut scratch = Scratch::default();
419 // The document's count so far: a tree built inside a typed read adds
420 // to what that read already holds.
421 let mut budget = Budget {
422 max: reader.max_memory(),
423 held: reader.held(),
424 };
425 loop {
426 let Some(event) = reader.next_event()? else {
427 // The reader ends a document only after a complete value.
428 return Err(Error::new(ErrorKind::UnexpectedEnd, reader.offset()));
429 };
430 let at = reader.event_offset();
431 let value = match event {
432 Event::StartArray | Event::StartObject => {
433 frames.push(Frame {
434 values: values.len(),
435 keys: keys.len(),
436 start: at,
437 });
438 continue;
439 }
440 Event::Key(key) => {
441 budget.allow(stacks(&values, &keys), growth(&keys), at)?;
442 if let Cow::Owned(decoded) = &key {
443 budget.held += decoded.capacity();
444 }
445 keys.push(key);
446 continue;
447 }
448 Event::EndArray => {
449 let Some(frame) = frames.pop() else {
450 return Err(Error::new(ErrorKind::ExpectedValue, at));
451 };
452 if frames.len() == 0 && frame.values == 0 {
453 // The outermost array: its items are the whole stack,
454 // which becomes the array in place, already counted.
455 let mut items = core::mem::take(&mut values);
456 items.shrink_to_fit();
457 reader.set_held(budget.held + items.capacity() * size_of::<Value<'a>>());
458 return Ok(Value::Array(Array::from(items)));
459 }
460 let bytes = (values.len() - frame.values) * size_of::<Value<'a>>();
461 budget.allow(stacks(&values, &keys), bytes, frame.start)?;
462 budget.held += bytes;
463 Value::Array(Array::from(values.split_off(frame.values)))
464 }
465 Event::EndObject => {
466 let Some(frame) = frames.pop() else {
467 return Err(Error::new(ErrorKind::ExpectedValue, at));
468 };
469 let bytes = (keys.len() - frame.keys) * size_of::<Member<'a>>();
470 budget.allow(stacks(&values, &keys), bytes, frame.start)?;
471 budget.held += bytes;
472 Value::Object(close_object(
473 &mut values,
474 &mut keys,
475 frame,
476 policy,
477 &mut scratch,
478 ))
479 }
480 Event::String(s) => {
481 if let Cow::Owned(decoded) = &s {
482 budget.held += decoded.capacity();
483 budget.allow(stacks(&values, &keys), 0, at)?;
484 }
485 Value::String(s)
486 }
487 Event::Number(n) => Value::Number(n),
488 Event::Bool(b) => Value::Bool(b),
489 Event::Null => Value::Null,
490 };
491 if frames.len() == 0 {
492 reader.set_held(budget.held);
493 return Ok(value);
494 }
495 let start = match &value {
496 Value::Array(_) | Value::Object(_) => reader.event_offset(),
497 _ => at,
498 };
499 budget.allow(stacks(&values, &keys), growth(&values), start)?;
500 values.push(value);
501 }
502}
503
504#[inline]
505fn key_at<'k>(keys: &'k [Cow<'_, str>], i: usize) -> &'k str {
506 keys.get(i).map_or("", |k| k)
507}
508
509/// Moves the closing object's members off the stacks, applying `policy`.
510/// Under [`DuplicateKeys::Error`] the reader has already refused any
511/// duplicate (when the object closed), so only `First` and `Last` have
512/// anything to do here.
513fn close_object<'a>(
514 values: &mut Vec<Value<'a>>,
515 keys: &mut Vec<Cow<'a, str>>,
516 frame: Frame,
517 policy: DuplicateKeys,
518 scratch: &mut Scratch,
519) -> Object<'a> {
520 let member_keys = keys.get(frame.keys..).unwrap_or(&[]);
521 let key = |i| key_at(member_keys, i);
522 let dedupe = matches!(policy, DuplicateKeys::First | DuplicateKeys::Last)
523 && dupes::has_duplicates(member_keys.len(), &key, &mut scratch.order);
524 if dedupe {
525 mark_duplicates(member_keys, policy, scratch, values, frame.values);
526 }
527 let pairs = keys.drain(frame.keys..).zip(values.drain(frame.values..));
528 let members: Vec<Member<'a>> = if dedupe {
529 // Sized exactly up front: a filtered iterator's size is unknown, and
530 // collecting it would grow the vector by reallocation.
531 let kept = scratch.keep.iter().filter(|&&keep| keep).count();
532 let mut members = Vec::with_capacity(kept);
533 members.extend(
534 pairs
535 .zip(scratch.keep.iter())
536 .filter_map(|(member, &keep)| keep.then_some(member)),
537 );
538 members
539 } else {
540 pairs.collect()
541 };
542 Object::from(members)
543}
544
545/// Fills `scratch.keep` with which members survive the policy, and for
546/// [`DuplicateKeys::Last`] moves each repeated key's last value to its first
547/// position. `scratch.order` holds the keys' sorted order.
548fn mark_duplicates(
549 keys: &[Cow<'_, str>],
550 policy: DuplicateKeys,
551 scratch: &mut Scratch,
552 values: &mut [Value<'_>],
553 base: usize,
554) {
555 let keep = &mut scratch.keep;
556 keep.clear();
557 keep.resize(keys.len(), true);
558 let key = |i| key_at(keys, i);
559 dupes::for_each_run(&key, &scratch.order, |run| {
560 let (Some(&first), Some(&last)) = (run.first(), run.last()) else {
561 return;
562 };
563 if policy == DuplicateKeys::Last {
564 values.swap(base + first, base + last);
565 }
566 for &i in run.get(1..).unwrap_or(&[]) {
567 if let Some(slot) = keep.get_mut(i) {
568 *slot = false;
569 }
570 }
571 });
572}
573
574#[cfg(test)]
575mod tests {
576 use super::*;
577
578 #[test]
579 fn test_duplicate_detection_small_and_large() {
580 let small = r#"{"a":1,"b":2,"c":3}"#;
581 assert!(Parser::new().parse(small).is_ok());
582 let mut large = alloc::string::String::from("{");
583 for i in 0..100 {
584 large.push_str(&alloc::format!("\"k{i}\":{i},"));
585 }
586 large.push_str("\"k50\":0,\"k7\":0}");
587 let err = Parser::new().parse(&large).unwrap_err();
588 assert_eq!(err.kind(), ErrorKind::DuplicateKey);
589 assert_eq!(large.get(err.offset()..err.offset() + 6), Some("\"k50\":"));
590 let last = Parser::new()
591 .duplicate_keys(DuplicateKeys::Last)
592 .parse(&large);
593 let last = last.unwrap_or_default();
594 assert_eq!(last.as_object().map(Object::len), Some(100));
595 assert_eq!(last["k50"], 0);
596 assert_eq!(last["k7"], 0);
597 assert_eq!(last.as_object().and_then(|o| o.keys().nth(50)), Some("k50"));
598 let first = Parser::new()
599 .duplicate_keys(DuplicateKeys::First)
600 .parse(&large);
601 assert_eq!(first.unwrap_or_default()["k50"], 50);
602 }
603
604 #[test]
605 fn test_duplicates_compare_decoded_keys() {
606 let err = Parser::new().parse(r#"{"a":1,"\u0061":2}"#).unwrap_err();
607 assert_eq!((err.kind(), err.offset()), (ErrorKind::DuplicateKey, 7));
608 }
609
610 proptest::proptest! {
611 /// Every policy matches a naive quadratic reference, across the
612 /// pairwise and sorting paths, with keys that share long prefixes
613 /// (equal fingerprints, different strings).
614 #[test]
615 fn prop_duplicate_policies_match_naive(picks in proptest::collection::vec(0usize..12, 0..40)) {
616 use alloc::{format, string::String, vec::Vec};
617 const KEYS: [&str; 12] = [
618 "a", "b", "abcdefgh1", "abcdefgh2", "abcdefgh12", "abcdefghX", "", "k",
619 "abcdefgh", "abcdefgi", "zz", "abcdefgh1\\u0000",
620 ];
621 let decoded = |k: &str| k.replace("\\u0000", "\u{0}");
622 let mut text = String::from("{");
623 let mut offsets = Vec::new();
624 for (i, &p) in picks.iter().enumerate() {
625 if i > 0 { text.push(','); }
626 offsets.push(text.len());
627 text.push_str(&format!("\"{}\":{i}", KEYS[p]));
628 }
629 text.push('}');
630 let names: Vec<String> = picks.iter().map(|&p| decoded(KEYS[p])).collect();
631
632 // Error: the earliest member whose key appeared before.
633 let repeat = (0..names.len()).find(|&i| names[..i].contains(&names[i]));
634 let got = Parser::new().parse(&text).err().map(|e| (e.kind(), e.offset()));
635 proptest::prop_assert_eq!(got, repeat.map(|i| (ErrorKind::DuplicateKey, offsets[i])));
636
637 // First and Last: one member per key, at its first position.
638 let mut order: Vec<&String> = Vec::new();
639 for n in &names { if !order.contains(&n) { order.push(n); } }
640 let first = Parser::new().duplicate_keys(DuplicateKeys::First).parse(&text).unwrap_or_default();
641 let last = Parser::new().duplicate_keys(DuplicateKeys::Last).parse(&text).unwrap_or_default();
642 let (fo, lo) = (first.as_object().cloned().unwrap_or_default(), last.as_object().cloned().unwrap_or_default());
643 proptest::prop_assert_eq!(fo.keys().collect::<Vec<_>>(), order.iter().map(|s| s.as_str()).collect::<Vec<_>>());
644 proptest::prop_assert_eq!(lo.keys().collect::<Vec<_>>(), order.iter().map(|s| s.as_str()).collect::<Vec<_>>());
645 for key in &order {
646 let want_first = names.iter().position(|n| n == *key);
647 let want_last = names.iter().rposition(|n| n == *key);
648 proptest::prop_assert_eq!(fo.get(key).and_then(Value::as_u64), want_first.map(|i| i as u64));
649 proptest::prop_assert_eq!(lo.get(key).and_then(Value::as_u64), want_last.map(|i| i as u64));
650 }
651 }
652 }
653
654 #[test]
655 fn test_duplicate_reported_at_earliest_repeat() {
656 // `b` repeats before `a` does.
657 let err = Parser::new()
658 .parse(r#"{"a":1,"b":2,"b":3,"a":4}"#)
659 .unwrap_err();
660 assert_eq!(err.offset(), 13);
661 }
662}