use alloc::{borrow::Cow, vec::Vec};
use core::mem::size_of;
use crate::{
Array, Limits, Object, Reader, Value, dupes,
error::{Error, ErrorKind},
reader::Event,
small::SmallStack,
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)]
#[non_exhaustive]
pub enum Numbers {
#[default]
IntegerText,
WholeValues,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[must_use]
pub struct Parser {
limits: Limits,
duplicates: DuplicateKeys,
numbers: Numbers,
}
impl Parser {
pub const fn new() -> Self {
Self {
limits: Limits::new(),
duplicates: DuplicateKeys::Error,
numbers: Numbers::IntegerText,
}
}
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
}
pub const fn numbers(mut self, numbers: Numbers) -> Self {
self.numbers = numbers;
self
}
#[must_use]
pub const fn get_numbers(&self) -> Numbers {
self.numbers
}
#[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.read_to_end()?;
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).with_numbers(self.numbers)
}
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,
start: usize,
}
struct Budget {
max: usize,
held: usize,
}
impl Budget {
#[inline]
fn allow(&self, stacks: usize, extra: usize, at: usize) -> Result<(), Error> {
if self.held.saturating_add(stacks).saturating_add(extra) > self.max {
Err(Error::new(ErrorKind::MemoryLimitExceeded, at))
} else {
Ok(())
}
}
}
#[inline]
fn stacks(values: &Vec<Value<'_>>, keys: &Vec<Cow<'_, str>>) -> usize {
values.capacity() * size_of::<Value<'_>>() + keys.capacity() * size_of::<Cow<'_, str>>()
}
#[inline]
fn growth<T>(v: &Vec<T>) -> usize {
if v.len() < v.capacity() {
0
} else {
(v.capacity() * 2).max(4) * size_of::<T>()
}
}
#[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>> = Vec::new();
let mut frames: SmallStack<Frame, 16> = SmallStack::new(Frame {
values: 0,
keys: 0,
start: 0,
});
let mut scratch = Scratch::default();
let mut budget = Budget {
max: reader.max_memory(),
held: reader.held(),
};
loop {
let Some(event) = reader.next_event()? else {
return Err(Error::new(ErrorKind::UnexpectedEnd, reader.offset()));
};
let at = reader.event_offset();
let value = match event {
Event::StartArray | Event::StartObject => {
frames.push(Frame {
values: values.len(),
keys: keys.len(),
start: at,
});
continue;
}
Event::Key(key) => {
budget.allow(stacks(&values, &keys), growth(&keys), at)?;
if let Cow::Owned(decoded) = &key {
budget.held += decoded.capacity();
}
keys.push(key);
continue;
}
Event::EndArray => {
let Some(frame) = frames.pop() else {
return Err(Error::new(ErrorKind::ExpectedValue, at));
};
if frames.len() == 0 && frame.values == 0 {
let mut items = core::mem::take(&mut values);
items.shrink_to_fit();
reader.set_held(budget.held + items.capacity() * size_of::<Value<'a>>());
return Ok(Value::Array(Array::from(items)));
}
let bytes = (values.len() - frame.values) * size_of::<Value<'a>>();
budget.allow(stacks(&values, &keys), bytes, frame.start)?;
budget.held += bytes;
Value::Array(Array::from(values.split_off(frame.values)))
}
Event::EndObject => {
let Some(frame) = frames.pop() else {
return Err(Error::new(ErrorKind::ExpectedValue, at));
};
let bytes = (keys.len() - frame.keys) * size_of::<Member<'a>>();
budget.allow(stacks(&values, &keys), bytes, frame.start)?;
budget.held += bytes;
Value::Object(close_object(
&mut values,
&mut keys,
frame,
policy,
&mut scratch,
))
}
Event::String(s) => {
if let Cow::Owned(decoded) = &s {
budget.held += decoded.capacity();
budget.allow(stacks(&values, &keys), 0, at)?;
}
Value::String(s)
}
Event::Number(n) => Value::Number(n),
Event::Bool(b) => Value::Bool(b),
Event::Null => Value::Null,
};
if frames.len() == 0 {
reader.set_held(budget.held);
return Ok(value);
}
let start = match &value {
Value::Array(_) | Value::Object(_) => reader.event_offset(),
_ => at,
};
budget.allow(stacks(&values, &keys), growth(&values), start)?;
values.push(value);
}
}
#[inline]
fn key_at<'k>(keys: &'k [Cow<'_, str>], 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>>,
frame: Frame,
policy: DuplicateKeys,
scratch: &mut Scratch,
) -> Object<'a> {
let member_keys = keys.get(frame.keys..).unwrap_or(&[]);
let key = |i| key_at(member_keys, i);
let dedupe = matches!(policy, DuplicateKeys::First | DuplicateKeys::Last)
&& dupes::has_duplicates(member_keys.len(), &key, &mut scratch.order);
if dedupe {
mark_duplicates(member_keys, policy, scratch, values, frame.values);
}
let pairs = keys.drain(frame.keys..).zip(values.drain(frame.values..));
let members: Vec<Member<'a>> = if dedupe {
let kept = scratch.keep.iter().filter(|&&keep| keep).count();
let mut members = Vec::with_capacity(kept);
members.extend(
pairs
.zip(scratch.keep.iter())
.filter_map(|(member, &keep)| keep.then_some(member)),
);
members
} else {
pairs.collect()
};
Object::from(members)
}
fn mark_duplicates(
keys: &[Cow<'_, str>],
policy: DuplicateKeys,
scratch: &mut Scratch,
values: &mut [Value<'_>],
base: usize,
) {
let keep = &mut scratch.keep;
keep.clear();
keep.resize(keys.len(), true);
let key = |i| key_at(keys, i);
dupes::for_each_run(&key, &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);
}
}