Skip to main content

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}