use alloc::{borrow::Cow, vec::Vec};
use crate::{
Array, Limits, Object, Reader, Value,
error::{Error, ErrorKind},
reader::Event,
tree::Member,
};
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum DuplicateKeys {
#[default]
Error,
First,
Last,
KeepAll,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[must_use]
pub struct Parser {
limits: Limits,
duplicates: DuplicateKeys,
}
impl Parser {
pub const fn new() -> Self {
Self {
limits: Limits::new(),
duplicates: DuplicateKeys::Error,
}
}
pub const fn limits(mut self, limits: Limits) -> Self {
self.limits = limits;
self
}
pub const fn duplicate_keys(mut self, policy: DuplicateKeys) -> Self {
self.duplicates = policy;
self
}
#[must_use]
pub const fn get_limits(&self) -> Limits {
self.limits
}
#[must_use]
pub const fn get_duplicate_keys(&self) -> DuplicateKeys {
self.duplicates
}
pub fn parse<'a>(&self, text: &'a str) -> Result<Value<'a>, Error> {
let mut reader = self.reader(text);
let value = reader
.read_value()?
.ok_or(Error::new(ErrorKind::UnexpectedEnd, text.len()))?;
reader.finish()?;
Ok(value)
}
pub fn parse_bytes<'a>(&self, bytes: &'a [u8]) -> Result<Value<'a>, Error> {
self.parse(self.check_bytes(bytes)?)
}
#[must_use]
pub fn reader<'a>(&self, text: &'a str) -> Reader<'a> {
Reader::with_config(text, self.limits, self.duplicates)
}
pub fn reader_bytes<'a>(&self, bytes: &'a [u8]) -> Result<Reader<'a>, Error> {
Ok(self.reader(self.check_bytes(bytes)?))
}
fn check_bytes<'a>(&self, bytes: &'a [u8]) -> Result<&'a str, Error> {
if bytes.len() > self.limits.max_input_bytes {
return Err(Error::new(
ErrorKind::InputTooLarge,
self.limits.max_input_bytes,
));
}
core::str::from_utf8(bytes).map_err(|e| Error::new(ErrorKind::InvalidUtf8, e.valid_up_to()))
}
}
#[derive(Clone, Copy)]
struct Frame {
values: usize,
keys: usize,
}
#[derive(Default)]
struct Scratch {
order: Vec<usize>,
keep: Vec<bool>,
}
pub(crate) fn build<'a>(
reader: &mut Reader<'a>,
policy: DuplicateKeys,
) -> Result<Value<'a>, Error> {
let mut values: Vec<Value<'a>> = Vec::new();
let mut keys: Vec<(Cow<'a, str>, usize)> = Vec::new();
let mut frames: Vec<Frame> = Vec::new();
let mut scratch = Scratch::default();
loop {
let Some(event) = reader.next_event()? else {
return Err(Error::new(ErrorKind::UnexpectedEnd, reader.offset()));
};
let value = match event {
Event::StartArray | Event::StartObject => {
frames.push(Frame {
values: values.len(),
keys: keys.len(),
});
continue;
}
Event::Key(key) => {
keys.push((key, reader.event_offset()));
continue;
}
Event::EndArray => {
let Some(frame) = frames.pop() else {
return Err(Error::new(ErrorKind::ExpectedValue, reader.event_offset()));
};
Value::Array(Array::from(values.split_off(frame.values)))
}
Event::EndObject => {
let Some(frame) = frames.pop() else {
return Err(Error::new(ErrorKind::ExpectedValue, reader.event_offset()));
};
Value::Object(close_object(
&mut values,
&mut keys,
frame,
policy,
&mut scratch,
)?)
}
Event::String(s) => Value::String(s),
Event::Number(n) => Value::Number(n),
Event::Bool(b) => Value::Bool(b),
Event::Null => Value::Null,
};
if frames.is_empty() {
return Ok(value);
}
values.push(value);
}
}
#[inline]
fn key_at<'k>(keys: &'k [(Cow<'_, str>, usize)], i: usize) -> &'k str {
keys.get(i).map_or("", |(k, _)| k)
}
fn close_object<'a>(
values: &mut Vec<Value<'a>>,
keys: &mut Vec<(Cow<'a, str>, usize)>,
frame: Frame,
policy: DuplicateKeys,
scratch: &mut Scratch,
) -> Result<Object<'a>, Error> {
let member_keys = keys.get(frame.keys..).unwrap_or(&[]);
let mut dedupe = false;
if policy != DuplicateKeys::KeepAll && has_duplicates(member_keys, &mut scratch.order) {
match policy {
DuplicateKeys::First | DuplicateKeys::Last => {
mark_duplicates(member_keys, policy, scratch, values, frame.values);
dedupe = true;
}
_ => {
let at = first_repeat(member_keys, &scratch.order);
let offset = member_keys.get(at).map_or(0, |(_, o)| *o);
return Err(Error::new(ErrorKind::DuplicateKey, offset));
}
}
}
let pairs = keys
.drain(frame.keys..)
.map(|(k, _)| k)
.zip(values.drain(frame.values..));
let members: Vec<Member<'a>> = if dedupe {
pairs
.zip(scratch.keep.iter())
.filter_map(|(member, &keep)| keep.then_some(member))
.collect()
} else {
pairs.collect()
};
Ok(Object::from(members))
}
fn has_duplicates(keys: &[(Cow<'_, str>, usize)], order: &mut Vec<usize>) -> bool {
const PAIRWISE: usize = 16;
let n = keys.len();
if n < 2 {
return false;
}
if n <= PAIRWISE {
let mut prints = [0u64; PAIRWISE];
for (slot, (key, _)) in prints.iter_mut().zip(keys) {
*slot = fingerprint(key);
}
let prints = prints.get(..n).unwrap_or(&[]);
let any = prints.iter().enumerate().skip(1).any(|(i, a)| {
prints
.iter()
.take(i)
.enumerate()
.any(|(j, b)| a == b && key_at(keys, i) == key_at(keys, j))
});
if !any {
return false;
}
}
order.clear();
order.extend(0..n);
order.sort_unstable_by(|&a, &b| key_at(keys, a).cmp(key_at(keys, b)).then(a.cmp(&b)));
order.windows(2).any(|w| match w {
[a, b] => key_at(keys, *a) == key_at(keys, *b),
_ => false,
})
}
#[inline]
fn fingerprint(key: &str) -> u64 {
let bytes = key.as_bytes();
let mut head = [0u8; 8];
for (slot, &b) in head.iter_mut().zip(bytes) {
*slot = b;
}
u64::from_le_bytes(head) ^ (bytes.len() as u64).rotate_left(56)
}
fn for_each_run(keys: &[(Cow<'_, str>, usize)], order: &[usize], mut f: impl FnMut(&[usize])) {
let mut start = 0;
while start < order.len() {
let first = key_at(keys, order.get(start).copied().unwrap_or(0));
let mut end = start + 1;
while order.get(end).is_some_and(|&i| key_at(keys, i) == first) {
end += 1;
}
if end - start > 1 {
f(order.get(start..end).unwrap_or(&[]));
}
start = end;
}
}
fn first_repeat(keys: &[(Cow<'_, str>, usize)], order: &[usize]) -> usize {
let mut earliest = usize::MAX;
for_each_run(keys, order, |run| {
if let Some(&second) = run.get(1) {
earliest = earliest.min(second);
}
});
earliest
}
fn mark_duplicates(
keys: &[(Cow<'_, str>, usize)],
policy: DuplicateKeys,
scratch: &mut Scratch,
values: &mut [Value<'_>],
base: usize,
) {
let keep = &mut scratch.keep;
keep.clear();
keep.resize(keys.len(), true);
for_each_run(keys, &scratch.order, |run| {
let (Some(&first), Some(&last)) = (run.first(), run.last()) else {
return;
};
if policy == DuplicateKeys::Last {
values.swap(base + first, base + last);
}
for &i in run.get(1..).unwrap_or(&[]) {
if let Some(slot) = keep.get_mut(i) {
*slot = false;
}
}
});
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_duplicate_detection_small_and_large() {
let small = r#"{"a":1,"b":2,"c":3}"#;
assert!(Parser::new().parse(small).is_ok());
let mut large = alloc::string::String::from("{");
for i in 0..100 {
large.push_str(&alloc::format!("\"k{i}\":{i},"));
}
large.push_str("\"k50\":0,\"k7\":0}");
let err = Parser::new().parse(&large).unwrap_err();
assert_eq!(err.kind(), ErrorKind::DuplicateKey);
assert_eq!(large.get(err.offset()..err.offset() + 6), Some("\"k50\":"));
let last = Parser::new()
.duplicate_keys(DuplicateKeys::Last)
.parse(&large);
let last = last.unwrap_or_default();
assert_eq!(last.as_object().map(Object::len), Some(100));
assert_eq!(last["k50"], 0);
assert_eq!(last["k7"], 0);
assert_eq!(last.as_object().and_then(|o| o.keys().nth(50)), Some("k50"));
let first = Parser::new()
.duplicate_keys(DuplicateKeys::First)
.parse(&large);
assert_eq!(first.unwrap_or_default()["k50"], 50);
}
#[test]
fn test_duplicates_compare_decoded_keys() {
let err = Parser::new().parse(r#"{"a":1,"\u0061":2}"#).unwrap_err();
assert_eq!((err.kind(), err.offset()), (ErrorKind::DuplicateKey, 7));
}
proptest::proptest! {
#[test]
fn prop_duplicate_policies_match_naive(picks in proptest::collection::vec(0usize..12, 0..40)) {
use alloc::{format, string::String, vec::Vec};
const KEYS: [&str; 12] = [
"a", "b", "abcdefgh1", "abcdefgh2", "abcdefgh12", "abcdefghX", "", "k",
"abcdefgh", "abcdefgi", "zz", "abcdefgh1\\u0000",
];
let decoded = |k: &str| k.replace("\\u0000", "\u{0}");
let mut text = String::from("{");
let mut offsets = Vec::new();
for (i, &p) in picks.iter().enumerate() {
if i > 0 { text.push(','); }
offsets.push(text.len());
text.push_str(&format!("\"{}\":{i}", KEYS[p]));
}
text.push('}');
let names: Vec<String> = picks.iter().map(|&p| decoded(KEYS[p])).collect();
let repeat = (0..names.len()).find(|&i| names[..i].contains(&names[i]));
let got = Parser::new().parse(&text).err().map(|e| (e.kind(), e.offset()));
proptest::prop_assert_eq!(got, repeat.map(|i| (ErrorKind::DuplicateKey, offsets[i])));
let mut order: Vec<&String> = Vec::new();
for n in &names { if !order.contains(&n) { order.push(n); } }
let first = Parser::new().duplicate_keys(DuplicateKeys::First).parse(&text).unwrap_or_default();
let last = Parser::new().duplicate_keys(DuplicateKeys::Last).parse(&text).unwrap_or_default();
let (fo, lo) = (first.as_object().cloned().unwrap_or_default(), last.as_object().cloned().unwrap_or_default());
proptest::prop_assert_eq!(fo.keys().collect::<Vec<_>>(), order.iter().map(|s| s.as_str()).collect::<Vec<_>>());
proptest::prop_assert_eq!(lo.keys().collect::<Vec<_>>(), order.iter().map(|s| s.as_str()).collect::<Vec<_>>());
for key in &order {
let want_first = names.iter().position(|n| n == *key);
let want_last = names.iter().rposition(|n| n == *key);
proptest::prop_assert_eq!(fo.get(key).and_then(Value::as_u64), want_first.map(|i| i as u64));
proptest::prop_assert_eq!(lo.get(key).and_then(Value::as_u64), want_last.map(|i| i as u64));
}
}
}
#[test]
fn test_duplicate_reported_at_earliest_repeat() {
let err = Parser::new()
.parse(r#"{"a":1,"b":2,"b":3,"a":4}"#)
.unwrap_err();
assert_eq!(err.offset(), 13);
}
}