use alloc::{borrow::Cow, string::String, vec::Vec};
use crate::{
DuplicateKeys, Kind, Limits, Number, dupes,
error::{Error, ErrorKind},
lexer::{self, NumScan, StrScan},
reader::Event,
scan,
small::{BitStack, SmallStack},
};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum State {
Value,
Element,
ArrayFirst,
ArrayNext,
ObjectFirst,
Key,
ObjectNext,
End,
Done,
}
#[derive(Clone, Copy, Debug)]
enum Pending {
None,
Str { quote: usize, scan: StrScan },
Key { quote: usize, scan: StrScan },
Colon {
quote: usize,
end: usize,
escaped: bool,
from: usize,
},
Num { start: usize, scan: NumScan },
Literal { start: usize },
}
#[derive(Clone, Copy, Debug)]
struct OpenObject {
keys: usize,
seen: u64,
suspect: bool,
}
#[derive(Clone, Copy, Debug)]
struct KeyMark {
print: u64,
quote: usize,
}
const COMPARE_AS_READ: usize = 16;
const INLINE_OBJECTS: usize = 8;
const INLINE_KEYS: usize = 16;
const KEY_STATE_BYTES: usize = size_of::<KeyMark>() + 5 * size_of::<usize>();
#[derive(Clone, Debug)]
pub(crate) struct Machine {
pub(crate) pos: usize,
pub(crate) last: usize,
state: State,
stack: BitStack,
elements: usize,
pub(crate) limits: Limits,
pub(crate) duplicates: DuplicateKeys,
pub(crate) skipping: bool,
pub(crate) complete: bool,
pending: Pending,
pub(crate) copy_keys: bool,
pub(crate) documents: bool,
doc_start: usize,
pub(crate) numbers: crate::Numbers,
objects: SmallStack<OpenObject, INLINE_OBJECTS>,
keys: SmallStack<KeyMark, INLINE_KEYS>,
dropped: usize,
copies: Vec<(usize, usize)>,
arena: String,
order: Vec<usize>,
}
impl Machine {
pub(crate) const fn new(limits: Limits, duplicates: DuplicateKeys, complete: bool) -> Self {
Self {
pos: 0,
last: 0,
state: State::Value,
stack: BitStack::new(),
elements: 0,
limits,
duplicates,
skipping: false,
complete,
pending: Pending::None,
copy_keys: false,
documents: false,
doc_start: 0,
numbers: crate::Numbers::IntegerText,
objects: SmallStack::new(OpenObject {
keys: 0,
seen: 0,
suspect: false,
}),
keys: SmallStack::new(KeyMark { print: 0, quote: 0 }),
dropped: 0,
copies: Vec::new(),
arena: String::new(),
order: Vec::new(),
}
}
#[inline]
fn checks_keys(&self) -> bool {
self.duplicates == DuplicateKeys::Error
}
#[inline]
pub(crate) fn depth(&self) -> usize {
self.stack.len()
}
#[inline]
pub(crate) fn is_done(&self) -> bool {
self.state == State::Done
}
#[inline]
pub(crate) fn finish_iteration(&mut self) {
self.state = State::Done;
}
pub(crate) fn document_start(&self) -> usize {
if self.documents && self.state == State::End && matches!(self.pending, Pending::None) {
self.dropped + self.pos
} else {
self.doc_start
}
}
pub(crate) fn check_trailing(&self, src: &str) -> Result<(), Error> {
if self.state == State::End && !self.documents {
if self.pos < src.len() {
return Err(Error::new(ErrorKind::TrailingCharacters, self.pos));
}
if !self.complete {
return Err(Self::end_error(src));
}
}
Ok(())
}
pub(crate) fn needed_from(&self) -> usize {
match self.pending {
Pending::None => self.pos,
Pending::Str { quote, .. }
| Pending::Key { quote, .. }
| Pending::Colon { quote, .. } => quote,
Pending::Num { start, .. } | Pending::Literal { start } => start,
}
}
pub(crate) fn rebase(&mut self, by: usize) {
self.dropped += by;
self.pos -= by;
self.last = self.last.saturating_sub(by);
self.pending = match self.pending {
Pending::None => Pending::None,
Pending::Str { quote, scan } => Pending::Str {
quote: quote - by,
scan: StrScan {
next: scan.next - by,
escaped: scan.escaped,
},
},
Pending::Key { quote, scan } => Pending::Key {
quote: quote - by,
scan: StrScan {
next: scan.next - by,
escaped: scan.escaped,
},
},
Pending::Colon {
quote,
end,
escaped,
from,
} => Pending::Colon {
quote: quote - by,
end: end - by,
escaped,
from: from - by,
},
Pending::Num { start, mut scan } => {
scan.rebase(by);
Pending::Num {
start: start - by,
scan,
}
}
Pending::Literal { start } => Pending::Literal { start: start - by },
};
}
#[inline]
fn end_error(src: &str) -> Error {
Error::new(ErrorKind::UnexpectedEnd, src.len())
}
#[inline]
fn cut_short(&self, e: &Error, src: &str) -> bool {
!self.complete && e.kind() == ErrorKind::UnexpectedEnd && e.offset() == src.len()
}
#[inline]
fn suspend<T>(&mut self, e: Error, src: &str, pending: Pending) -> Result<T, Error> {
if self.cut_short(&e, src) {
self.pending = pending;
}
Err(e)
}
pub(crate) fn at_value(&mut self, src: &str) -> Result<bool, Error> {
match self.pending {
Pending::None => {}
Pending::Key { .. } | Pending::Colon { .. } => return Ok(false),
_ => return Ok(true),
}
let bytes = src.as_bytes();
self.pos = scan::skip_whitespace(bytes, self.pos);
let next = bytes.get(self.pos).copied();
Ok(match self.state {
State::Value | State::Element => true,
State::End if self.documents => match next {
Some(_) => {
self.next_document();
true
}
None if !self.complete => return Err(Self::end_error(src)),
None => false,
},
State::ArrayFirst => match next {
None if !self.complete => return Err(Self::end_error(src)),
next => next != Some(b']'),
},
State::ArrayNext => match next {
Some(b',') => {
self.pos = scan::skip_whitespace(bytes, self.pos + 1);
self.state = State::Element;
true
}
None if !self.complete => return Err(Self::end_error(src)),
_ => false,
},
_ => false,
})
}
#[inline]
pub(crate) fn at_item(&mut self, src: &str) -> Option<bool> {
if !matches!(self.pending, Pending::None) {
return None;
}
let bytes = src.as_bytes();
let at = scan::skip_whitespace(bytes, self.pos);
match (self.state, bytes.get(at)) {
(State::ArrayNext, Some(b',')) => {
let next = scan::skip_whitespace(bytes, at + 1);
match bytes.get(next) {
Some(&b) if b != b']' => {
self.pos = next;
self.state = State::Element;
Some(true)
}
_ => None,
}
}
(State::ArrayFirst, Some(&b)) if b != b']' => {
self.pos = at;
Some(true)
}
_ => None,
}
}
pub(crate) fn peek_kind(&self, src: &str) -> Option<Kind> {
let at = match self.pending {
Pending::Str { .. } => return Some(Kind::String),
Pending::Num { .. } => return Some(Kind::Number),
Pending::Literal { start } => start,
Pending::Key { .. } | Pending::Colon { .. } => return None,
Pending::None => self.pos,
};
Some(match src.as_bytes().get(at)? {
b'{' => Kind::Object,
b'[' => Kind::Array,
b'"' => Kind::String,
b'-' | b'0'..=b'9' => Kind::Number,
b't' | b'f' => Kind::Bool,
b'n' => Kind::Null,
_ => return None,
})
}
pub(crate) fn step<'s>(&mut self, src: &'s str) -> Result<Option<Event<'s>>, Error> {
if !matches!(self.pending, Pending::None) {
return self.resume(src).map(Some);
}
let bytes = src.as_bytes();
loop {
self.pos = scan::skip_whitespace(bytes, self.pos);
let at = self.pos;
let next = bytes.get(at).copied();
let err = |kind| Err(Error::new(kind, at));
match self.state {
State::Value | State::Element | State::ArrayFirst => match next {
None => return Err(Self::end_error(src)),
Some(b']') if self.state == State::ArrayFirst => {
return Ok(Some(self.close(at, Event::EndArray)));
}
Some(b']') if self.state == State::Element => {
return err(ErrorKind::TrailingComma);
}
Some(b) => return self.value(src, b, at).map(Some),
},
State::ArrayNext => match next {
None => return Err(Self::end_error(src)),
Some(b',') => {
self.pos += 1;
self.state = State::Element;
}
Some(b']') => return Ok(Some(self.close(at, Event::EndArray))),
Some(_) => return err(ErrorKind::ExpectedCommaOrBracket),
},
State::ObjectFirst | State::Key => match next {
None => return Err(Self::end_error(src)),
Some(b'"') => return self.key(src, at, StrScan::start(at)).map(Some),
Some(b'}') if self.state == State::ObjectFirst => {
return self.close_object(src, at).map(Some);
}
Some(b'}') => return err(ErrorKind::TrailingComma),
Some(_) => return err(ErrorKind::ExpectedKey),
},
State::ObjectNext => match next {
None => return Err(Self::end_error(src)),
Some(b',') => {
self.pos += 1;
self.state = State::Key;
}
Some(b'}') => return self.close_object(src, at).map(Some),
Some(_) => return err(ErrorKind::ExpectedCommaOrBrace),
},
State::End => {
return match next {
None if !self.complete => Err(Self::end_error(src)),
None => {
self.state = State::Done;
Ok(None)
}
Some(_) if self.documents => {
self.next_document();
continue;
}
Some(_) => err(ErrorKind::TrailingCharacters),
};
}
State::Done => return Ok(None),
}
}
}
#[inline]
pub(crate) fn enter(&mut self, src: &str, object: bool) -> Result<bool, Error> {
if !matches!(self.pending, Pending::None)
|| !matches!(
self.state,
State::Value | State::Element | State::ArrayFirst
)
{
return Ok(false);
}
let bytes = src.as_bytes();
let at = scan::skip_whitespace(bytes, self.pos);
let want = if object { b'{' } else { b'[' };
if bytes.get(at) != Some(&want) {
return Ok(false);
}
self.step(src).map(|_| true)
}
fn resume<'s>(&mut self, src: &'s str) -> Result<Event<'s>, Error> {
match core::mem::replace(&mut self.pending, Pending::None) {
Pending::None => Err(Self::end_error(src)),
Pending::Str { quote, scan } => self.string(src, quote, scan),
Pending::Key { quote, scan } => self.key(src, quote, scan),
Pending::Colon {
quote,
end,
escaped,
from,
} => self.colon(src, quote, end, escaped, from),
Pending::Num { start, scan } => self.number(src, start, scan),
Pending::Literal { start } => self.literal(src, start),
}
}
fn next_document(&mut self) {
self.state = State::Value;
self.elements = 0;
self.doc_start = self.dropped + self.pos;
}
#[inline]
fn after_value(&mut self) {
self.state = match self.stack.last() {
None => State::End,
Some(false) => State::ArrayNext,
Some(true) => State::ObjectNext,
};
}
#[inline]
fn close<'s>(&mut self, at: usize, event: Event<'s>) -> Event<'s> {
self.pos = at + 1;
self.last = at;
self.stack.pop();
self.after_value();
event
}
fn close_object<'s>(&mut self, src: &'s str, at: usize) -> Result<Event<'s>, Error> {
if self.checks_keys() {
if let Some(open) = self.objects.pop() {
if open.suspect {
self.check_object(src, open)?;
}
self.keys.truncate(open.keys);
if self.copy_keys {
if let Some(&(from, _)) = self.copies.get(open.keys) {
self.arena.truncate(from);
}
self.copies.truncate(open.keys);
}
}
}
Ok(self.close(at, Event::EndObject))
}
#[cold]
fn check_object(&mut self, src: &str, open: OpenObject) -> Result<(), Error> {
let quotes: Vec<usize> = self
.keys
.iter_from(open.keys)
.map(|k| k.quote.wrapping_sub(self.dropped))
.collect();
let repeat = if self.copy_keys {
let copies = self.copies.get(open.keys..).unwrap_or(&[]);
let arena = self.arena.as_str();
let text = |i: usize| {
copies
.get(i)
.and_then(|&(from, to)| arena.get(from..to))
.unwrap_or("")
};
dupes::has_duplicates(quotes.len(), &text, &mut self.order)
.then(|| dupes::first_repeat(&text, &self.order))
} else {
let texts: Vec<Cow<'_, str>> = quotes.iter().map(|&q| key_text(src, q)).collect();
let text = |i: usize| texts.get(i).map_or("", |t| t);
dupes::has_duplicates(texts.len(), &text, &mut self.order)
.then(|| dupes::first_repeat(&text, &self.order))
};
match repeat.and_then(|i| quotes.get(i)) {
Some("e) => Err(Error::new(ErrorKind::DuplicateKey, quote)),
None => Ok(()),
}
}
#[inline]
fn keep_key(
&mut self,
src: &str,
quote: usize,
end: usize,
escaped: bool,
) -> Result<(), Error> {
if self.keys.len() >= INLINE_KEYS {
self.key_state_fits(quote)?;
}
let print = if self.copy_keys || escaped {
self.decoded_print(src, quote, end, escaped)
} else {
dupes::fingerprint_at(src.as_bytes(), quote + 1, end - 1)
};
let count = self.keys.len();
if let Some(open) = self.objects.last_mut() {
let bit = 1u64 << (print.wrapping_mul(0x9e37_79b9_7f4a_7c15) >> 58);
if !open.suspect && open.seen & bit != 0 {
let (inline, spill) = self.keys.from(open.keys);
open.suspect = inline.iter().chain(spill).any(|k| k.print == print);
}
open.seen |= bit;
if count - open.keys >= COMPARE_AS_READ {
open.suspect = true;
}
}
self.keys.push(KeyMark {
print,
quote: quote + self.dropped,
});
Ok(())
}
#[cold]
fn key_state_fits(&self, quote: usize) -> Result<(), Error> {
let held = (self.keys.len() + 1)
.saturating_mul(KEY_STATE_BYTES)
.saturating_add(self.arena.len());
if held > self.limits.max_memory {
return Err(Error::new(ErrorKind::MemoryLimitExceeded, quote));
}
Ok(())
}
#[cold]
#[inline(never)]
fn decoded_print(&mut self, src: &str, quote: usize, end: usize, escaped: bool) -> u64 {
let body = src.get(quote + 1..end - 1).unwrap_or("");
if self.copy_keys {
let from = self.arena.len();
if escaped {
self.arena.push_str(&lexer::decode(body));
} else {
self.arena.push_str(body);
}
let to = self.arena.len();
self.copies.push((from, to));
dupes::fingerprint(self.arena.as_bytes().get(from..to).unwrap_or_default())
} else {
dupes::fingerprint(lexer::decode(body).as_bytes())
}
}
#[inline]
fn count_value(&mut self, at: usize) -> Result<(), Error> {
if self.elements >= self.limits.max_elements {
return Err(Error::new(ErrorKind::TooManyElements, at));
}
self.elements += 1;
Ok(())
}
#[inline]
fn value<'s>(&mut self, src: &'s str, b: u8, at: usize) -> Result<Event<'s>, Error> {
match b {
b'{' => self.open(at, true),
b'[' => self.open(at, false),
b'"' => {
self.count_value(at)?;
self.string(src, at, StrScan::start(at))
}
b'-' | b'0'..=b'9' => {
self.count_value(at)?;
match lexer::quick_integer(src.as_bytes(), at) {
Some(end) if end - at <= self.limits.max_number_bytes => {
self.pos = end;
self.last = at;
self.after_value();
let text = src.get(at..end).unwrap_or("0");
Ok(Event::Number(Number::from_valid(text)))
}
_ => self.number(src, at, NumScan::start(at)),
}
}
b't' | b'f' | b'n' => {
self.count_value(at)?;
self.literal(src, at)
}
_ => Err(Error::new(ErrorKind::ExpectedValue, at)),
}
}
#[inline]
fn open<'s>(&mut self, at: usize, object: bool) -> Result<Event<'s>, Error> {
self.count_value(at)?;
if self.stack.len() >= self.limits.max_depth {
return Err(Error::new(ErrorKind::DepthLimitExceeded, at));
}
self.pos = at + 1;
self.last = at;
self.stack.push(object);
Ok(if object {
self.state = State::ObjectFirst;
if self.checks_keys() {
self.objects.push(OpenObject {
keys: self.keys.len(),
seen: 0,
suspect: false,
});
}
Event::StartObject
} else {
self.state = State::ArrayFirst;
Event::StartArray
})
}
#[inline(always)]
fn string<'s>(
&mut self,
src: &'s str,
quote: usize,
scan: StrScan,
) -> Result<Event<'s>, Error> {
let mut scan = scan;
match lexer::resume_string(
src.as_bytes(),
quote,
&mut scan,
self.limits.max_string_bytes,
) {
Ok(token) => {
self.pos = token.end;
self.last = quote;
let text = self.body(src, quote, token.end, token.escaped);
self.after_value();
Ok(Event::String(text))
}
Err(e) => self.suspend(e, src, Pending::Str { quote, scan }),
}
}
fn key<'s>(&mut self, src: &'s str, quote: usize, scan: StrScan) -> Result<Event<'s>, Error> {
let mut scan = scan;
match lexer::resume_string(
src.as_bytes(),
quote,
&mut scan,
self.limits.max_string_bytes,
) {
Ok(token) => self.colon(src, quote, token.end, token.escaped, token.end),
Err(e) => self.suspend(e, src, Pending::Key { quote, scan }),
}
}
fn colon<'s>(
&mut self,
src: &'s str,
quote: usize,
end: usize,
escaped: bool,
from: usize,
) -> Result<Event<'s>, Error> {
let at = scan::skip_whitespace(src.as_bytes(), from);
match src.as_bytes().get(at) {
Some(b':') => {
self.pos = at + 1;
self.last = quote;
self.state = State::Value;
if self.checks_keys() {
self.keep_key(src, quote, end, escaped)?;
}
Ok(Event::Key(self.body(src, quote, end, escaped)))
}
Some(_) => Err(Error::new(ErrorKind::ExpectedColon, at)),
None => {
let pending = Pending::Colon {
quote,
end,
escaped,
from: at,
};
self.suspend(Self::end_error(src), src, pending)
}
}
}
#[inline]
fn number<'s>(
&mut self,
src: &'s str,
start: usize,
scan: NumScan,
) -> Result<Event<'s>, Error> {
let mut scan = scan;
let max = self.limits.max_number_bytes;
match lexer::resume_number(src.as_bytes(), start, &mut scan, self.complete, max) {
Ok(end) => {
self.pos = end;
self.last = start;
self.after_value();
let text = src.get(start..end).unwrap_or("0");
Ok(Event::Number(Number::from_valid(text)))
}
Err(e) => self.suspend(e, src, Pending::Num { start, scan }),
}
}
#[inline]
fn literal<'s>(&mut self, src: &'s str, start: usize) -> Result<Event<'s>, Error> {
let (word, event): (&[u8], _) = match src.as_bytes().get(start) {
Some(b't') => (b"true", Event::Bool(true)),
Some(b'f') => (b"false", Event::Bool(false)),
_ => (b"null", Event::Null),
};
match lexer::scan_literal(src.as_bytes(), start, word) {
Ok(end) => {
self.pos = end;
self.last = start;
self.after_value();
Ok(event)
}
Err(e) => self.suspend(e, src, Pending::Literal { start }),
}
}
#[inline]
fn body<'s>(&self, src: &'s str, quote: usize, end: usize, escaped: bool) -> Cow<'s, str> {
let body = src.get(quote + 1..end - 1).unwrap_or("");
if escaped && !self.skipping {
Cow::Owned(lexer::decode(body))
} else {
Cow::Borrowed(body)
}
}
}
pub(crate) fn key_text(src: &str, quote: usize) -> Cow<'_, str> {
match lexer::scan_string(src.as_bytes(), quote, usize::MAX) {
Ok(token) => {
let body = src.get(quote + 1..token.end - 1).unwrap_or("");
if token.escaped {
Cow::Owned(lexer::decode(body))
} else {
Cow::Borrowed(body)
}
}
Err(_) => Cow::Borrowed(""),
}
}
#[cfg(test)]
mod tests {
use alloc::vec::Vec;
use super::*;
fn chunked(text: &str, chunk: usize) -> Result<Vec<Event<'static>>, Error> {
let mut m = Machine::new(Limits::unlimited(), DuplicateKeys::KeepAll, false);
let mut out = Vec::new();
let mut have = 0;
loop {
let src = text.get(..have).unwrap_or(text);
match m.step(src) {
Ok(Some(e)) => out.push(owned(e)),
Ok(None) => return Ok(out),
Err(e) if m.cut_short(&e, src) => {
if have == text.len() {
m.complete = true;
}
have = (have + chunk).min(text.len());
while !text.is_char_boundary(have) {
have += 1;
}
}
Err(e) => return Err(e),
}
}
}
fn owned(e: Event<'_>) -> Event<'static> {
match e {
Event::Key(k) => Event::Key(Cow::Owned(k.into_owned())),
Event::String(s) => Event::String(Cow::Owned(s.into_owned())),
Event::Number(n) => Event::Number(n.into_owned()),
Event::StartObject => Event::StartObject,
Event::EndObject => Event::EndObject,
Event::StartArray => Event::StartArray,
Event::EndArray => Event::EndArray,
Event::Bool(b) => Event::Bool(b),
Event::Null => Event::Null,
}
}
fn whole(text: &str) -> Result<Vec<Event<'static>>, Error> {
let mut m = Machine::new(Limits::unlimited(), DuplicateKeys::KeepAll, true);
let mut out = Vec::new();
while let Some(e) = m.step(text)? {
out.push(owned(e));
}
Ok(out)
}
#[test]
fn test_partial_text_gives_the_same_events_at_every_chunk_size() {
let docs = [
r#"{"a" : [1, -2.5e3, true, false, null, "x\ny\u00e9\ud83d\ude00"], "b": {}}"#,
" 12345 ",
"[[], {}, [[]], \"\"]",
r#"{"key with spaces" : "v"}"#,
"[1,]",
"{\"a\" 1}",
"[tru]",
"[1 2]",
"-",
"\"abc",
"[0e]",
"nul",
];
for doc in docs {
let want = whole(doc);
for chunk in 1..=doc.len() {
assert_eq!(chunked(doc, chunk), want, "{doc:?} in chunks of {chunk}");
}
}
}
fn checked(text: &str) -> Result<usize, Error> {
let mut m = Machine::new(Limits::new(), DuplicateKeys::Error, true);
let mut n = 0;
while m.step(text)?.is_some() {
n += 1;
}
Ok(n)
}
#[test]
fn test_repeats_are_found_past_the_inline_state_and_collisions_are_not_repeats() {
let nest = |depth: usize, repeat_at: Option<usize>| {
let mut text = alloc::string::String::new();
for level in 0..depth {
text.push_str(r#"{"a": 1, "b": 2, "c": 3, "#);
if repeat_at == Some(level) {
text.push_str(r#""b": 4, "#);
}
text.push_str(r#""child": "#);
}
text.push_str("null");
text.push_str(&"}".repeat(depth));
text
};
assert!(checked(&nest(20, None)).is_ok());
for level in [0, 5, 7, 8, 12, 19] {
let text = nest(20, Some(level));
let quote = text.match_indices(r#""b": 4"#).next().map(|(at, _)| at);
let err = checked(&text).err();
assert_eq!(
err.map(|e| (e.kind(), Some(e.offset()))),
Some((ErrorKind::DuplicateKey, quote)),
"{level}"
);
}
let same_print = r#"{"abcdefgh_1_abcdefgh": 1, "abcdefgh_2_abcdefgh": 2}"#;
assert_eq!(
dupes::fingerprint(b"abcdefgh_1_abcdefgh"),
dupes::fingerprint(b"abcdefgh_2_abcdefgh")
);
assert!(checked(same_print).is_ok());
assert!(
checked(
r#"{"abcdefgh_1_abcdefgh": 1, "abcdefgh_2_abcdefgh": 2, "abcdefgh_1_abcdefgh": 3}"#
)
.is_err()
);
assert!(checked(r#"{"id": 1, "\u0069d": 2}"#).is_err());
assert!(checked(r#"{"textDocument": 1, "textDocumen\u0074": 2}"#).is_err());
let mut wide = alloc::string::String::new();
for i in 0..40 {
wide.push_str(&alloc::format!(r#""k{i}": {i}, "#));
}
assert!(checked(&alloc::format!("{{{wide}\"end\": 0}}")).is_ok());
assert!(checked(&alloc::format!("{{{wide}\"k3\": 0}}")).is_err());
}
#[test]
fn test_duplicate_check_state_is_bounded_by_the_memory_budget() {
let mut wide = alloc::string::String::from("{");
for i in 0..100 {
wide.push_str(&alloc::format!(r#""k{i}": 0, "#));
}
wide.push_str(r#""end": 0}"#);
let run = |max_memory: usize, duplicates: DuplicateKeys| {
let limits = Limits::new().with_max_memory(max_memory);
let mut m = Machine::new(limits, duplicates, true);
loop {
match m.step(&wide) {
Ok(Some(_)) => {}
Ok(None) => return Ok(()),
Err(e) => return Err(e.kind()),
}
}
};
assert_eq!(
run(1000, DuplicateKeys::Error),
Err(ErrorKind::MemoryLimitExceeded)
);
assert_eq!(run(KEY_STATE_BYTES * 101, DuplicateKeys::Error), Ok(()));
assert_eq!(run(1000, DuplicateKeys::KeepAll), Ok(()));
}
#[test]
fn test_documents_follow_one_another() {
let text = " 1 [2]{\"a\":3}\"s\"
null ";
let mut m = Machine::new(Limits::new(), DuplicateKeys::Error, true);
m.documents = true;
let mut events = Vec::new();
while let Ok(Some(e)) = m.step(text) {
events.push(owned(e));
}
assert_eq!(events.len(), 10);
assert!(m.is_done());
let mut m = Machine::new(Limits::new(), DuplicateKeys::Error, true);
m.documents = true;
assert!(m.step("1 2").is_ok());
assert_eq!(m.at_value("1 2"), Ok(true));
assert_eq!(m.peek_kind("1 2"), Some(Kind::Number));
let mut m = Machine::new(Limits::new(), DuplicateKeys::Error, false);
m.documents = true;
assert!(m.step("[] ").is_ok() && m.step("[] ").is_ok());
assert!(m.at_value("[] ").is_err());
m.complete = true;
assert_eq!(m.at_value("[] "), Ok(false));
assert_eq!(m.step("[] "), Ok(None));
}
#[test]
fn test_peek_kind_and_at_value() {
let src = r#"[{"a": 1}, "s", 2, true, null, []]"#;
let mut m = Machine::new(Limits::new(), DuplicateKeys::Error, true);
assert_eq!(m.at_value(src), Ok(true));
assert_eq!(m.peek_kind(src), Some(Kind::Array));
assert!(m.step(src).is_ok());
let mut kinds = Vec::new();
while m.at_value(src) == Ok(true) {
kinds.push(m.peek_kind(src));
let depth = m.depth();
let _first = m.step(src);
while m.depth() > depth {
let _inner = m.step(src);
}
}
assert_eq!(
kinds,
[
Some(Kind::Object),
Some(Kind::String),
Some(Kind::Number),
Some(Kind::Bool),
Some(Kind::Null),
Some(Kind::Array)
]
);
assert_eq!(m.peek_kind("x"), None);
}
#[test]
fn test_pending_tokens_report_their_kind_and_rebase() {
let mut m = Machine::new(Limits::new(), DuplicateKeys::Error, false);
let src = " [\"abc";
assert!(m.step(src).is_ok()); assert!(m.step(src).is_err()); assert_eq!(m.needed_from(), 4);
assert_eq!(m.peek_kind(src), Some(Kind::String));
assert_eq!(m.at_value(src), Ok(true));
m.rebase(3);
assert_eq!(m.needed_from(), 1);
let rest = "[\"abcdef\"]";
assert_eq!(
m.step(rest).ok().flatten(),
Some(Event::String("abcdef".into()))
);
assert_eq!(m.last, 1);
let mut m = Machine::new(Limits::new(), DuplicateKeys::Error, false);
assert!(m.step("{\"k\" ").is_ok()); assert!(m.step("{\"k\" ").is_err()); assert_eq!(m.at_value("{\"k\" "), Ok(false));
assert_eq!(m.peek_kind("{\"k\" "), None);
m.rebase(1);
assert_eq!(
m.step("\"k\" :1}").ok().flatten(),
Some(Event::Key("k".into()))
);
let mut m = Machine::new(Limits::new(), DuplicateKeys::Error, false);
assert!(m.step("[12").is_ok());
assert!(m.step("[12").is_err());
assert_eq!(m.peek_kind("[12"), Some(Kind::Number));
m.rebase(1);
assert_eq!(m.needed_from(), 0);
assert!(
m.step("12]")
.is_ok_and(|e| e == Some(Event::Number(12.into())))
);
let mut m = Machine::new(Limits::new(), DuplicateKeys::Error, false);
assert!(m.step("[tr").is_ok());
assert!(m.step("[tr").is_err());
assert_eq!(m.peek_kind("[tr"), Some(Kind::Bool));
m.rebase(1);
assert_eq!(m.step("true]").ok().flatten(), Some(Event::Bool(true)));
}
}