use std::borrow::Cow;
use std::hash::{BuildHasher, RandomState};
use hashbrown::HashTable;
use hashbrown::hash_table::Entry;
use crate::event::{Event, EventKind};
use crate::messages::{
COMMENTS_NOT_ALLOWED, Message, NAN_AND_INFINITY_NOT_ALLOWED, NUMBER_FORM_NOT_ALLOWED,
SINGLE_QUOTES_NOT_ALLOWED, UNQUOTED_KEYS_NOT_ALLOWED,
};
use crate::path::{self, PathStep};
use crate::problem::{Detail, SyntaxError, SyntaxKind};
use crate::unicode::{
is_high_surrogate, is_identifier_part, is_identifier_start, is_json5_space, is_low_surrogate,
is_noncharacter, is_surrogate, line_separator_at,
};
use crate::{Config, Dialect, Problem, Rule, Severity};
const LINEAR_KEYS: usize = 16;
const MAX_SAFE_INTEGER: u64 = (1 << 53) - 1;
const SAFE_DECIMAL_DIGITS: usize = 16;
const SAFE_HEX_DIGITS: usize = 14;
const DOUBLE_HEX_DIGITS: usize = 256;
pub(crate) fn check<'a>(
text: &'a str,
config: &Config,
events: bool,
) -> (Vec<Problem>, Vec<Event<'a>>) {
let mut list = Vec::new();
let mut push = |event| list.push(event);
let problems = walk(text, 0..text.len(), config, events.then_some(&mut push));
(problems, list)
}
pub(crate) fn walk<'a>(
text: &'a str,
lines: std::ops::Range<usize>,
config: &Config,
sink: Option<&mut dyn FnMut(Event<'a>)>,
) -> Vec<Problem> {
walk_scan::<false>(text, lines, config, sink, None).0
}
#[derive(Default)]
pub(crate) struct Scan {
pub(crate) commas: Vec<usize>,
pub(crate) members: Vec<Member>,
last_comma: usize,
starts: Vec<usize>,
pub(crate) endings: Vec<(usize, usize)>,
pub(crate) target: Option<Eol>,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum Eol {
Lf,
CrLf,
Cr,
}
impl Eol {
pub(crate) fn len(self) -> usize {
self.text().len()
}
pub(crate) fn text(self) -> &'static str {
match self {
Eol::Lf => "\n",
Eol::CrLf => "\r\n",
Eol::Cr => "\r",
}
}
}
struct Endings {
severity: Severity,
first: Option<Eol>,
reported: bool,
}
pub(crate) struct Member {
pub(crate) start: usize,
pub(crate) end: usize,
pub(crate) comma: usize,
}
pub(crate) fn scan(text: &str, config: &Config) -> (Vec<Problem>, Scan) {
let mut scan = Scan::default();
let problems = walk_scan::<true>(text, 0..text.len(), config, None, Some(&mut scan)).0;
(problems, scan)
}
fn walk_scan<'a, 's, const SCAN: bool>(
text: &'a str,
lines: std::ops::Range<usize>,
config: &Config,
sink: Option<&'s mut dyn FnMut(Event<'a>)>,
scan: Option<&'s mut Scan>,
) -> (Vec<Problem>, Option<Eol>) {
let dialect = config.dialect();
let text = &text[..lines.end];
let mut parser = Parser::<SCAN> {
text,
bytes: text.as_bytes(),
pos: lines.start,
dialect,
json5: dialect.json5(),
json_lines: dialect == Dialect::JsonLines,
duplicate_key: config.severity(Rule::DuplicateKey),
invalid_number: config.severity(Rule::InvalidNumber),
invalid_code_point: config.severity(Rule::InvalidCodePoint),
max_depth: config.max_depth,
problems: Vec::new(),
stack: Vec::new(),
depth: 0,
events: sink,
scan,
endings: Endings {
severity: config.severity(Rule::MixedLineEndings),
first: None,
reported: false,
},
cr_mask: 0,
lf_fast: dialect != Dialect::JsonLines,
};
if parser.endings.severity.is_on() {
if parser.json_lines {
parser.endings.first = text.find('\n').map(|i| {
if text[..i].ends_with('\r') {
Eol::CrLf
} else {
Eol::Lf
}
});
} else if lines.start == 0 {
parser.cr_mask = CR_BIT;
}
}
if lines.start == 0 {
parser.byte_order_mark(config.severity(Rule::ByteOrderMark));
}
let outcome = if parser.json_lines {
parser.json_lines(config.severity(Rule::MissingFinalNewline))
} else {
parser.document()
};
if let Err(mut fail) = outcome {
parser.unclosed(&mut fail);
let end = parser.syntax_end(&fail);
parser.problems.push(Problem {
offset: fail.offset,
end,
severity: Severity::Error,
detail: Detail::Syntax(SyntaxError {
kind: fail.kind,
started: fail.started,
}),
});
}
if let (Some(scan), Some(first)) = (parser.scan.as_deref_mut(), parser.endings.first) {
scan.target = Some(target_ending(first, dialect));
}
(parser.problems, parser.endings.first)
}
pub(crate) fn check_ending(text: &str, config: &Config) -> (Vec<Problem>, &'static str) {
let severity = config.severity(Rule::MixedLineEndings);
let on;
let config = if severity.is_on() {
config
} else {
on = config
.clone()
.rule(Rule::MixedLineEndings, Severity::Warning);
&on
};
let (mut problems, first) = walk_scan::<false>(text, 0..text.len(), config, None, None);
if !severity.is_on() {
problems.retain(|p| p.rule() != Rule::MixedLineEndings);
}
let eol = first.map_or(Eol::Lf, |first| target_ending(first, config.dialect()));
(problems, eol.text())
}
const CR_BIT: u8 = 4;
fn target_ending(first: Eol, dialect: Dialect) -> Eol {
if first == Eol::Cr && dialect == Dialect::Jwcc {
Eol::Lf
} else {
first
}
}
pub(crate) type Key<'a> = Cow<'a, [u8]>;
struct Fail {
offset: usize,
kind: SyntaxKind,
started: Option<usize>,
}
impl Fail {
fn at(offset: usize, kind: SyntaxKind) -> Fail {
Fail {
offset,
kind,
started: None,
}
}
fn inside(offset: usize, kind: SyntaxKind, started: usize) -> Fail {
Fail {
offset,
kind,
started: Some(started),
}
}
}
struct Parser<'a, 's, const SCAN: bool> {
text: &'a str,
bytes: &'a [u8],
pos: usize,
dialect: Dialect,
json5: bool,
json_lines: bool,
duplicate_key: Severity,
invalid_number: Severity,
invalid_code_point: Severity,
max_depth: usize,
problems: Vec<Problem>,
stack: Vec<Frame<'a>>,
depth: usize,
events: Option<&'s mut dyn FnMut(Event<'a>)>,
scan: Option<&'s mut Scan>,
endings: Endings,
cr_mask: u8,
lf_fast: bool,
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum Container {
Object,
Array,
}
struct Frame<'a> {
container: Container,
opened: usize,
keys: Keys<'a>,
current_key: Key<'a>,
element_index: usize,
}
#[inline]
fn key_eq(a: &[u8], b: &[u8]) -> bool {
a.len() == b.len() && a.first() == b.first() && a == b
}
#[derive(Default)]
struct Keys<'a> {
list: Vec<(Key<'a>, usize)>,
index: HashTable<(u32, u32)>,
state: RandomState,
}
impl<'a> Keys<'a> {
fn first_or_insert(&mut self, key: &Key<'a>, at: usize) -> Option<usize> {
let list = &mut self.list;
let position = u32::try_from(list.len())
.ok()
.filter(|_| list.len() > LINEAR_KEYS);
let Some(position) = position else {
if let Some((_, first)) = list.iter().find(|(k, _)| key_eq(k, key)) {
return Some(*first);
}
list.push((key.clone(), at));
if list.len() == LINEAR_KEYS + 1 {
for (i, (k, _)) in (0..).zip(list.iter()) {
let hash = short_hash(&self.state, k);
self.index
.insert_unique(spread(hash), (hash, i), |&(h, _)| spread(h));
}
}
return None;
};
let hash = short_hash(&self.state, key);
let entry = self.index.entry(
spread(hash),
|&(h, i)| h == hash && key_eq(&list[i as usize].0, key),
|&(h, _)| spread(h),
);
match entry {
Entry::Occupied(found) => Some(list[found.get().1 as usize].1),
Entry::Vacant(vacant) => {
vacant.insert((hash, position));
list.push((key.clone(), at));
None
}
}
}
fn clear(&mut self) {
self.list.clear();
if self.index.capacity() > 4 * self.index.len() {
self.index = HashTable::new();
} else {
self.index.clear();
}
}
}
#[expect(
clippy::cast_possible_truncation,
reason = "the low 32 bits are the point"
)]
fn short_hash(state: &RandomState, key: &[u8]) -> u32 {
state.hash_one(key) as u32
}
fn spread(hash: u32) -> u64 {
u64::from(hash) * 0x1_0000_0001
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum State {
Value,
ArrayFirst,
ArrayNext,
ObjectFirst,
ObjectNext,
Colon,
AfterValue,
Done,
}
impl<'a, const SCAN: bool> Parser<'a, '_, SCAN> {
fn peek(&self) -> Option<u8> {
self.bytes.get(self.pos).copied()
}
fn line_end(&self) -> Option<usize> {
self.line_end_at(self.pos)
}
fn line_end_at(&self, at: usize) -> Option<usize> {
if !self.json_lines {
return None;
}
match self.bytes.get(at..)? {
[b'\n', ..] => Some(1),
[b'\r', b'\n', ..] => Some(2),
_ => None,
}
}
fn char_at(&self, at: usize) -> char {
self.text
.get(at..)
.and_then(|s| s.chars().next())
.unwrap_or('\u{FFFD}')
}
fn fail(&self, kind: SyntaxKind) -> Fail {
Fail::at(self.pos, kind)
}
fn unexpected(&self, expected: &'static str) -> Fail {
self.unexpected_at(self.pos, expected)
}
fn unexpected_at(&self, at: usize, expected: &'static str) -> Fail {
if let Some(word) = self.word_at(at) {
let word = word.to_owned();
Fail::at(at, SyntaxKind::UnexpectedWord { word, expected })
} else if at >= self.bytes.len() {
Fail::at(at, SyntaxKind::UnexpectedEnd { expected })
} else if self.line_end_at(at).is_some() {
Fail::at(at, SyntaxKind::UnexpectedLineEnd { expected })
} else {
Fail::at(
at,
SyntaxKind::Unexpected {
found: self.char_at(at),
expected,
},
)
}
}
fn word_at(&self, at: usize) -> Option<&'a str> {
let part = |b: &u8| b.is_ascii_alphanumeric() || *b == b'_';
let rest = self.bytes.get(at..)?;
if !rest.first()?.is_ascii_alphabetic()
|| at.checked_sub(1).is_some_and(|i| part(&self.bytes[i]))
{
return None;
}
let len = rest.iter().take(33).take_while(|b| part(b)).count();
(len <= 32 && rest.get(len).is_none_or(u8::is_ascii)).then(|| &self.text[at..at + len])
}
fn unclosed(&self, fail: &mut Fail) {
let SyntaxKind::UnexpectedEnd { expected } = fail.kind else {
return;
};
let structural = ["a value", "a key", "`:`", "`,` or `}`", "`,` or `]`"];
let Some(frame) = self.top() else {
return;
};
if fail.started.is_none() && structural.contains(&expected) {
let open = match frame.container {
Container::Object => '{',
Container::Array => '[',
};
fail.kind = SyntaxKind::Unclosed { open, expected };
fail.started = Some(frame.opened);
}
}
#[cold]
fn not_allowed(&self, at: usize, what: Message, hint: bool) -> Fail {
Fail::at(
at,
SyntaxKind::NotAllowed {
what,
dialect: self.dialect,
hint: hint && !self.json_lines,
},
)
}
#[cold]
fn single_quoted(&mut self, at: usize) -> Fail {
let hint = self.json5_reads(at, |p| p.string(b'\'', false).map(|_| true));
self.not_allowed(at, SINGLE_QUOTES_NOT_ALLOWED, hint)
}
#[cold]
fn json5_reads(
&mut self,
at: usize,
scan: impl FnOnce(&mut Self) -> Result<bool, Fail>,
) -> bool {
if self.json_lines {
return false;
}
let (pos, json5, problems) = (self.pos, self.json5, self.problems.len());
self.pos = at;
self.json5 = true;
let reads = scan(self).unwrap_or(false);
self.problems.truncate(problems);
(self.pos, self.json5) = (pos, json5);
reads
}
#[cold]
fn json5_number(&mut self, start: usize, what: Message) -> Fail {
let hint = self.json5_reads(start, |p| {
p.number()?;
let c = p.char_at(p.pos);
Ok(p.pos == p.bytes.len() || !(c == '\\' || is_identifier_part(c)))
});
self.not_allowed(start, what, hint)
}
#[cold]
fn comment_not_allowed(&self) -> Fail {
let hint = !self.json_lines
&& (self.bytes[self.pos + 1] == b'/'
|| memchr::memmem::find(&self.bytes[self.pos + 2..], b"*/").is_some());
self.not_allowed(self.pos, COMMENTS_NOT_ALLOWED, hint)
}
fn emit(&mut self, offset: usize, kind: EventKind<'a>) {
if let Some(sink) = &mut self.events {
sink(Event { offset, kind });
}
}
#[cold]
fn syntax_end(&self, fail: &Fail) -> usize {
let at = fail.offset;
match &fail.kind {
SyntaxKind::UnexpectedWord { word, .. } => at + word.len(),
SyntaxKind::UnexpectedEnd { .. }
| SyntaxKind::UnexpectedLineEnd { .. }
| SyntaxKind::Unclosed { .. }
| SyntaxKind::MissingComma
| SyntaxKind::UnterminatedString
| SyntaxKind::UnterminatedComment => at,
_ => match self.text.get(at..).and_then(|rest| rest.chars().next()) {
Some('\n' | '\r' | '\u{2028}' | '\u{2029}') | None => at,
Some(c) => at + c.len_utf8(),
},
}
}
fn report(&mut self, offset: usize, end: usize, severity: Severity, detail: Detail) {
if severity.is_on() {
self.problems.push(Problem {
offset,
end,
severity,
detail,
});
}
}
#[inline]
fn ending(&mut self, at: usize, eol: Eol) {
let known = self.endings.first == Some(eol);
if !known || target_ending(eol, self.dialect) != eol {
self.ending_differs(at, eol);
}
}
#[inline(never)]
fn ending_differs(&mut self, at: usize, eol: Eol) {
let first = if let Some(first) = self.endings.first {
first
} else {
let lf_before = eol != Eol::Lf && memchr::memchr(b'\n', &self.bytes[..at]).is_some();
let first = if lf_before { Eol::Lf } else { eol };
self.endings.first = Some(first);
if first != Eol::Lf {
self.cr_mask = u8::MAX;
self.lf_fast = false;
}
first
};
if eol != first && !self.endings.reported {
self.endings.reported = true;
let end = at + eol.len();
self.report(at, end, self.endings.severity, Detail::MixedLineEndings);
if !SCAN {
self.endings.severity = Severity::Off;
self.cr_mask = 0;
self.lf_fast = !self.json_lines;
}
}
let target = target_ending(first, self.dialect);
if SCAN
&& eol != target
&& let Some(scan) = self.scan.as_deref_mut()
{
let (mut at, mut len) = (at, eol.len());
if eol == Eol::CrLf && target == Eol::Lf {
let stop = scan.endings.last().map_or(0, |&(a, l)| a + l);
while at > stop && self.bytes[at - 1] == b'\r' {
(at, len) = (at - 1, len + 1);
}
}
scan.endings.push((at, len));
}
}
#[inline(never)]
fn endings_in(&mut self, from: usize, to: usize) {
let mut i = from;
while let Some(rest) = self.bytes.get(i..to)
&& let Some(found) = memchr::memchr2(b'\n', b'\r', rest)
{
let at = i + found;
i = at + 1;
let (at, eol) = match self.bytes[at] {
b'\r' if self.bytes.get(i) == Some(&b'\n') => continue,
b'\r' => (at, Eol::Cr),
_ if at > 0 && self.bytes[at - 1] == b'\r' => (at - 1, Eol::CrLf),
_ => (at, Eol::Lf),
};
self.ending(at, eol);
}
}
fn byte_order_mark(&mut self, severity: Severity) {
if self.text.starts_with('\u{FEFF}') {
self.report(0, '\u{FEFF}'.len_utf8(), severity, Detail::ByteOrderMark);
self.pos = '\u{FEFF}'.len_utf8();
}
}
fn document(&mut self) -> Result<(), Fail> {
let mut state = State::Value;
loop {
let value_end = self.pos;
self.trivia()?;
state = match state {
State::ArrayFirst | State::ArrayNext if self.peek() == Some(b']') => {
self.close(']', state == State::ArrayNext)?
}
State::Value | State::ArrayFirst | State::ArrayNext => self.value()?,
State::ObjectFirst | State::ObjectNext if self.peek() == Some(b'}') => {
self.close('}', state == State::ObjectNext)?
}
State::ObjectFirst | State::ObjectNext => {
self.key()?;
State::Colon
}
State::Colon if self.peek() == Some(b':') => {
self.pos += 1;
State::Value
}
State::Colon => return Err(self.unexpected("`:`")),
State::AfterValue => self.after_value(value_end)?,
State::Done => {
return match self.peek() {
None => Ok(()),
Some(_) if self.line_end().is_some() => Ok(()),
Some(_) if self.json_lines => Err(self.unexpected("the end of the line")),
Some(_) => Err(self.unexpected("the end of the file")),
};
}
};
}
}
fn top(&self) -> Option<&Frame<'a>> {
self.stack[..self.depth].last()
}
fn top_mut(&mut self) -> Option<&mut Frame<'a>> {
self.stack[..self.depth].last_mut()
}
fn state_after_value(&self) -> State {
if self.depth == 0 {
State::Done
} else {
State::AfterValue
}
}
fn after_value(&mut self, value_end: usize) -> Result<State, Fail> {
let object = self.top().is_some_and(|f| f.container == Container::Object);
match self.peek() {
Some(b',') => {
if SCAN && let Some(scan) = self.scan.as_deref_mut() {
scan.last_comma = self.pos;
if object {
let start = self.depth.checked_sub(1).and_then(|d| scan.starts.get(d));
scan.members.push(Member {
start: start.copied().unwrap_or(0),
end: value_end,
comma: self.pos,
});
}
}
self.pos += 1;
if let Some(frame) = self.top_mut() {
frame.element_index += 1;
}
Ok(if object {
State::ObjectNext
} else {
State::ArrayNext
})
}
Some(b'}') if object => self.close('}', false),
Some(b']') if !object => self.close(']', false),
Some(b) if self.starts_item(b, object) => {
Err(Fail::at(value_end, SyntaxKind::MissingComma))
}
_ => Err(self.unexpected(if object { "`,` or `}`" } else { "`,` or `]`" })),
}
}
fn starts_item(&self, b: u8, object: bool) -> bool {
if object {
matches!(b, b'"' | b'\'') || self.identifier_start(self.pos)
} else {
matches!(
b,
b'{' | b'[' | b'"' | b'\'' | b'-' | b'+' | b'.' | b'0'
..=b'9' | b't' | b'f' | b'n' | b'I' | b'N'
)
}
}
fn close(&mut self, close: char, after_comma: bool) -> Result<State, Fail> {
if after_comma && !self.dialect.trailing_commas() {
if SCAN && let Some(scan) = self.scan.as_deref_mut() {
scan.commas.push(scan.last_comma);
} else {
return Err(self.fail(SyntaxKind::TrailingComma {
close,
dialect: self.dialect,
}));
}
}
self.emit(self.pos, EventKind::End);
self.pos += 1;
if let Some(depth) = self.depth.checked_sub(1) {
self.depth = depth;
self.stack[depth].keys.clear();
}
Ok(self.state_after_value())
}
fn open(&mut self, container: Container) -> Result<State, Fail> {
if self.depth >= self.max_depth {
let limit = self.max_depth;
return Err(Fail::at(self.pos, SyntaxKind::TooDeep { limit }));
}
if let Some(frame) = self.stack.get_mut(self.depth) {
frame.container = container;
frame.opened = self.pos;
frame.current_key = Key::Borrowed(&[]);
frame.element_index = 0;
} else {
self.stack.push(Frame {
container,
opened: self.pos,
keys: Keys::default(),
current_key: Key::Borrowed(&[]),
element_index: 0,
});
}
self.depth += 1;
let kind = match container {
Container::Object => EventKind::ObjectStart,
Container::Array => EventKind::ArrayStart,
};
self.emit(self.pos, kind);
self.pos += 1;
Ok(match container {
Container::Object => State::ObjectFirst,
Container::Array => State::ArrayFirst,
})
}
fn value(&mut self) -> Result<State, Fail> {
let start = self.pos;
let Some(b) = self.peek() else {
return Err(self.unexpected("a value"));
};
let kind = match b {
b'{' => return self.open(Container::Object),
b'[' => return self.open(Container::Array),
b'"' | b'\'' if b == b'"' || self.json5 => {
let value = self.string(b, self.events.is_some())?;
match value {
Some(value) => EventKind::String(path::text(value)),
None => return Ok(self.state_after_value()),
}
}
b'\'' => return Err(self.single_quoted(self.pos)),
b'-' | b'+' | b'.' | b'0'..=b'9' | b'I' | b'N' => {
self.number()?;
EventKind::Number(&self.text[start..self.pos])
}
b't' => {
self.literal("`true`", "a value")?;
EventKind::Bool(true)
}
b'f' => {
self.literal("`false`", "a value")?;
EventKind::Bool(false)
}
b'n' => {
self.literal("`null`", "a value")?;
EventKind::Null
}
_ => return Err(self.unexpected("a value")),
};
self.emit(start, kind);
Ok(self.state_after_value())
}
fn json_lines(&mut self, final_newline: Severity) -> Result<(), Fail> {
let len = self.bytes.len();
while self.pos < len {
let line_start = self.pos;
self.trivia()?;
match self.peek() {
None => return Err(Fail::at(line_start, SyntaxKind::BlankLine)),
Some(_) if self.line_end().is_some() => {
return Err(Fail::at(line_start, SyntaxKind::BlankLine));
}
Some(_) => self.document()?,
}
if let Some(len) = self.line_end() {
if self.endings.severity.is_on() {
self.ending(self.pos, if len == 1 { Eol::Lf } else { Eol::CrLf });
}
self.pos += len;
} else {
self.report(len, len, final_newline, Detail::MissingFinalNewline);
}
}
Ok(())
}
fn key(&mut self) -> Result<(), Fail> {
let start = self.pos;
let track_keys = self.duplicate_key.is_on();
let key = self
.read_key(track_keys || self.events.is_some())?
.unwrap_or(Key::Borrowed(&[]));
if !track_keys {
if self.events.is_some() {
self.emit(start, EventKind::Key(key));
}
return Ok(());
}
if self.events.is_some() {
self.emit(start, EventKind::Key(key.clone()));
}
self.check_duplicate(start, &key);
if SCAN
&& let Some(scan) = self.scan.as_deref_mut()
&& let Some(top) = self.depth.checked_sub(1)
{
if scan.starts.len() <= top {
scan.starts.resize(top + 1, 0);
}
if let Some(slot) = scan.starts.get_mut(top) {
*slot = start;
}
}
if let Some(frame) = self.top_mut() {
frame.current_key = key;
}
Ok(())
}
fn read_key(&mut self, decode: bool) -> Result<Option<Key<'a>>, Fail> {
let start = self.pos;
match self.peek() {
Some(b'"') => self.string(b'"', decode),
Some(b'\'') if self.json5 => self.string(b'\'', decode),
Some(b'\'') => Err(self.single_quoted(start)),
Some(_) if self.identifier_start(start) => {
if !self.json5 {
let hint = self.json5_reads(start, |p| p.identifier().map(|_| true));
return Err(self.not_allowed(start, UNQUOTED_KEYS_NOT_ALLOWED, hint));
}
self.identifier().map(Some)
}
_ => Err(self.unexpected("a key")),
}
}
fn check_duplicate(&mut self, start: usize, key: &Key<'a>) {
let Some(frame) = self.top_mut() else {
return;
};
match frame.keys.first_or_insert(key, start) {
None => {}
Some(first) => {
let stack = &self.stack[..self.depth];
let path = path::path_of(stack.len(), |i| match stack.get(i + 1) {
None => PathStep::Key(key),
Some(_) => match stack[i].container {
Container::Object => PathStep::Key(&stack[i].current_key),
Container::Array => PathStep::Index(stack[i].element_index),
},
});
self.report(
start,
self.pos,
self.duplicate_key,
Detail::DuplicateKey { first, path },
);
}
}
}
fn identifier_start(&self, at: usize) -> bool {
let c = self.char_at(at);
c == '\\' || is_identifier_start(c)
}
fn identifier(&mut self) -> Result<Key<'a>, Fail> {
let start = self.pos;
let mut decoded: Option<String> = None;
while self.pos < self.bytes.len() {
let escaped = self.bytes[self.pos] == b'\\';
let (c, len) = if escaped {
if self.bytes.get(self.pos + 1) != Some(&b'u') {
return Err(self.fail(SyntaxKind::InvalidEscape {
found: self.char_at(self.pos + 1),
}));
}
let Some(unit) = self.hex(self.pos + 2, 4) else {
return Err(self.fail(SyntaxKind::InvalidUnicodeEscape));
};
if is_high_surrogate(unit)
&& self.bytes.get(self.pos + 6..self.pos + 8) == Some(b"\\u")
&& let Some(low) = self.hex(self.pos + 8, 4)
&& is_low_surrogate(low)
{
let code_point = 0x10000 + ((unit - 0xD800) << 10) + (low - 0xDC00);
(char::from_u32(code_point).unwrap_or('\u{FFFD}'), 12)
} else {
(char::from_u32(unit).unwrap_or('\u{FFFD}'), 6)
}
} else {
let c = self.char_at(self.pos);
(c, c.len_utf8())
};
let fits = if self.pos == start {
is_identifier_start(c)
} else {
is_identifier_part(c)
};
if !fits {
if self.pos == start {
return Err(self.unexpected("a key"));
}
break;
}
if let Some(buffer) = &mut decoded {
buffer.push(c);
} else if escaped {
let mut buffer = self.text[start..self.pos].to_owned();
buffer.push(c);
decoded = Some(buffer);
}
self.pos += len;
}
Ok(match decoded {
Some(buffer) => Cow::Owned(buffer.into_bytes()),
None => Cow::Borrowed(&self.bytes[start..self.pos]),
})
}
fn string(&mut self, quote: u8, decode: bool) -> Result<Option<Key<'a>>, Fail> {
let start = self.pos;
self.pos += 1;
let mut decoded: Option<Vec<u8>> = None;
let mut run_start = self.pos;
let ascii_only = self.invalid_code_point.is_on();
let stops = string_stops(quote, self.json5, ascii_only);
loop {
self.pos += plain_bytes(&self.bytes[self.pos..], stops, quote, ascii_only);
let Some(b) = self.peek() else {
return Err(Fail::inside(
self.pos,
SyntaxKind::UnterminatedString,
start,
));
};
match b {
_ if b == quote => {
let value = match decoded {
Some(mut buffer) => {
buffer.extend_from_slice(&self.bytes[run_start..self.pos]);
Some(Cow::Owned(buffer))
}
None if decode => Some(Cow::Borrowed(&self.bytes[start + 1..self.pos])),
None => None,
};
self.pos += 1;
return Ok(value);
}
b'\\' => {
let buffer = decode.then(|| {
let buffer = decoded.get_or_insert_with(Vec::new);
buffer.extend_from_slice(&self.bytes[run_start..self.pos]);
buffer
});
let code_point = self.escape(start)?;
if let (Some(buffer), Some(code_point)) = (buffer, code_point) {
push_wtf8(buffer, code_point);
}
run_start = self.pos;
}
b'\n' | b'\r' => {
return Err(Fail::inside(self.pos, SyntaxKind::LineBreakInString, start));
}
0..0x20 => {
debug_assert!(!self.json5);
return Err(self.fail(SyntaxKind::ControlCharacter {
found: char::from(b),
}));
}
_ => {
debug_assert!(b >= 0x80 && self.invalid_code_point.is_on());
let c = self.char_at(self.pos);
if is_noncharacter(u32::from(c)) {
self.report(
self.pos,
self.pos + c.len_utf8(),
self.invalid_code_point,
Detail::InvalidCodePoint {
code_point: u32::from(c),
},
);
}
self.pos += c.len_utf8();
}
}
}
}
fn escape(&mut self, string_start: usize) -> Result<Option<u32>, Fail> {
let at = self.pos;
let Some(b) = self.bytes.get(at + 1).copied() else {
return Err(Fail::inside(
self.bytes.len(),
SyntaxKind::UnterminatedString,
string_start,
));
};
self.pos += 2;
let simple = match b {
b'"' => Some('"'),
b'\\' => Some('\\'),
b'/' => Some('/'),
b'b' => Some('\u{8}'),
b'f' => Some('\u{c}'),
b'n' => Some('\n'),
b'r' => Some('\r'),
b't' => Some('\t'),
_ => None,
};
if let Some(c) = simple {
return Ok(Some(u32::from(c)));
}
if b == b'u' {
return self.unicode_escape(at).map(Some);
}
if !self.json5 {
return Err(Fail::at(
at,
SyntaxKind::InvalidEscape {
found: self.char_at(at + 1),
},
));
}
match b {
b'v' => Ok(Some(0xB)),
b'0' if self.peek().is_some_and(|d| d.is_ascii_digit()) => {
Err(Fail::at(at, SyntaxKind::InvalidEscape { found: '0' }))
}
b'0' => Ok(Some(0)),
b'1'..=b'9' => Err(Fail::at(
at,
SyntaxKind::InvalidEscape {
found: char::from(b),
},
)),
b'x' => {
let Some(value) = self.hex(self.pos, 2) else {
return Err(Fail::at(at, SyntaxKind::InvalidHexEscape));
};
self.pos += 2;
Ok(Some(value))
}
b'\n' => {
if self.cr_mask != 0 {
self.ending(at + 1, Eol::Lf);
}
Ok(None)
}
b'\r' => {
let crlf = self.peek() == Some(b'\n');
if crlf {
self.pos += 1;
}
if self.cr_mask != 0 {
self.ending(at + 1, if crlf { Eol::CrLf } else { Eol::Cr });
}
Ok(None)
}
_ => {
let c = self.char_at(at + 1);
self.pos = at + 1 + c.len_utf8();
Ok(if c == '\u{2028}' || c == '\u{2029}' {
None
} else {
Some(u32::from(c))
})
}
}
}
fn unicode_escape(&mut self, at: usize) -> Result<u32, Fail> {
let Some(unit) = self.hex(self.pos, 4) else {
return Err(Fail::at(at, SyntaxKind::InvalidUnicodeEscape));
};
self.pos += 4;
let code_point = if is_high_surrogate(unit)
&& self.bytes.get(self.pos..self.pos + 2) == Some(b"\\u")
&& let Some(low) = self.hex(self.pos + 2, 4)
&& is_low_surrogate(low)
{
self.pos += 6;
0x10000 + ((unit - 0xD800) << 10) + (low - 0xDC00)
} else {
unit
};
if is_surrogate(code_point) || is_noncharacter(code_point) {
self.report(
at,
self.pos,
self.invalid_code_point,
Detail::InvalidCodePoint { code_point },
);
}
Ok(code_point)
}
fn hex(&self, at: usize, digits: usize) -> Option<u32> {
let text = self.text.get(at..at + digits)?;
if !text.bytes().all(|b| b.is_ascii_hexdigit()) {
return None;
}
u32::from_str_radix(text, 16).ok()
}
fn number(&mut self) -> Result<(), Fail> {
let start = self.pos;
match self.peek() {
Some(b'+') if !self.json5 => {
return Err(self.json5_number(start, NUMBER_FORM_NOT_ALLOWED));
}
Some(b'+' | b'-') => self.pos += 1,
_ => {}
}
match self.peek() {
Some(b'I') => self.nan_or_infinity(start, "`Infinity`"),
Some(b'N') => self.nan_or_infinity(start, "`NaN`"),
Some(b'0') if matches!(self.bytes.get(self.pos + 1), Some(b'x' | b'X')) => {
self.hex_number(start)
}
_ => self.decimal_number(start),
}
}
fn hex_number(&mut self, start: usize) -> Result<(), Fail> {
if !self.json5 {
return Err(self.json5_number(start, NUMBER_FORM_NOT_ALLOWED));
}
self.pos += 2;
let hex_start = self.pos;
while self.peek().is_some_and(|b| b.is_ascii_hexdigit()) {
self.pos += 1;
}
if self.pos == hex_start {
return Err(self.unexpected("a hex digit"));
}
self.check_hex(start, hex_start);
Ok(())
}
fn decimal_number(&mut self, start: usize) -> Result<(), Fail> {
let int_start = self.pos;
let int_digits = if self.peek() == Some(b'0') {
self.pos += 1;
if self.peek().is_some_and(|b| b.is_ascii_digit()) {
return Err(Fail::at(int_start, SyntaxKind::LeadingZero));
}
true
} else {
self.skip_digits()
};
let mut has_dot = false;
if self.peek() == Some(b'.') {
let fraction_digits = self.bytes.get(self.pos + 1).is_some_and(u8::is_ascii_digit);
if !int_digits && !fraction_digits {
return Err(self.unexpected_at(int_start, "a value"));
}
if !self.json5 && int_digits != fraction_digits {
return Err(self.json5_number(start, NUMBER_FORM_NOT_ALLOWED));
}
self.pos += 1;
self.skip_digits();
has_dot = true;
} else if !int_digits {
return Err(self.unexpected("a digit"));
}
let mut has_exp = false;
if matches!(self.peek(), Some(b'e' | b'E')) {
self.pos += 1;
if matches!(self.peek(), Some(b'+' | b'-')) {
self.pos += 1;
}
if !self.skip_digits() {
return Err(self.unexpected("a digit"));
}
has_exp = true;
}
self.check_decimal(start, has_dot, has_exp);
Ok(())
}
fn skip_digits(&mut self) -> bool {
let rest = &self.bytes[self.pos..];
let mut len = 0;
while len < rest.len() && rest[len].is_ascii_digit() {
len += 1;
}
self.pos += len;
len > 0
}
fn nan_or_infinity(&mut self, start: usize, word: &'static str) -> Result<(), Fail> {
if !self.json5 {
return Err(
if self.text[self.pos..].starts_with(word.trim_matches('`')) {
self.json5_number(start, NAN_AND_INFINITY_NOT_ALLOWED)
} else {
self.unexpected(self.after_sign(start))
},
);
}
self.literal(word, self.after_sign(start))
}
fn after_sign(&self, start: usize) -> &'static str {
if self.pos > start {
"a digit"
} else {
"a value"
}
}
fn literal(&mut self, word: &'static str, instead: &'static str) -> Result<(), Fail> {
let start = self.pos;
let bare = &word.as_bytes()[1..word.len() - 1];
if self.bytes[start..].starts_with(bare) {
self.pos += bare.len();
return Ok(());
}
for &expected in bare {
if self.peek() != Some(expected) {
let other = self
.word_at(start)
.is_some_and(|w| start + w.len() > self.pos);
return Err(if other {
self.unexpected_at(start, instead)
} else {
self.unexpected(word)
});
}
self.pos += 1;
}
Ok(())
}
fn check_decimal(&mut self, start: usize, has_dot: bool, has_exp: bool) {
if !self.invalid_number.is_on() {
return;
}
let text = &self.text[start..self.pos];
if has_dot || has_exp {
if (has_exp || text.len() > 308) && text.parse::<f64>().is_ok_and(f64::is_infinite) {
self.report(
start,
self.pos,
self.invalid_number,
Detail::InvalidNumber { overflows: true },
);
}
return;
}
let digits = text.trim_start_matches(['+', '-']).trim_start_matches('0');
if digits.len() < SAFE_DECIMAL_DIGITS {
return;
}
let overflows = digits.len() > 308 && text.parse::<f64>().is_ok_and(f64::is_infinite);
let unsafe_integer = digits.len() > SAFE_DECIMAL_DIGITS
|| digits.parse::<u64>().is_ok_and(|n| n > MAX_SAFE_INTEGER);
if overflows || unsafe_integer {
self.report(
start,
self.pos,
self.invalid_number,
Detail::InvalidNumber { overflows },
);
}
}
fn check_hex(&mut self, start: usize, hex_start: usize) {
if !self.invalid_number.is_on() {
return;
}
let significant = self.text[hex_start..self.pos].trim_start_matches('0');
let top = significant
.as_bytes()
.get(..14)
.map(<[u8]>::to_ascii_lowercase);
let overflows = significant.len() > DOUBLE_HEX_DIGITS
|| (significant.len() == DOUBLE_HEX_DIGITS
&& top.is_some_and(|top| top[..13].iter().all(|&b| b == b'f') && top[13] >= b'c'));
let unsafe_integer = significant.len() > SAFE_HEX_DIGITS
|| u64::from_str_radix(significant, 16).is_ok_and(|n| n > MAX_SAFE_INTEGER);
if overflows || unsafe_integer {
self.report(
start,
self.pos,
self.invalid_number,
Detail::InvalidNumber { overflows },
);
}
}
#[inline]
fn trivia(&mut self) -> Result<(), Fail> {
if self.peek().is_none_or(ends_trivia) {
return Ok(());
}
if self.peek() == Some(b' ')
&& self.bytes[self.pos..]
.get(1)
.is_some_and(|&b| ends_trivia(b))
{
self.pos += 1;
return Ok(());
}
if self.peek() == Some(b'\n') && self.lf_fast {
let rest = &self.bytes[self.pos..][1..];
if let Some(run) = rest.iter().position(|&b| b != b' ')
&& ends_trivia(rest[run])
{
self.pos += 1 + run;
return Ok(());
}
}
self.skip_trivia()
}
#[inline(never)]
fn skip_trivia(&mut self) -> Result<(), Fail> {
loop {
let Some(b) = self.peek() else { return Ok(()) };
match b {
b'\n' | b'\r' if self.line_end().is_some() => return Ok(()),
b' ' | b'\t' | b'\r' | b'\n' => {
let from = self.pos;
let rest = &self.bytes[from + 1..];
let mut seen = b;
let run = if self.json_lines {
rest.iter().position(|&b| !matches!(b, b' ' | b'\t'))
} else {
rest.iter().position(|&b| {
let white = matches!(b, b' ' | b'\t' | b'\r' | b'\n');
seen |= if white { b } else { 0 };
!white
})
};
let Some(run) = run else {
self.pos = self.bytes.len();
if seen & self.cr_mask != 0 {
self.endings_in(from, self.pos);
}
return Ok(());
};
self.pos += 1 + run;
if seen & self.cr_mask != 0 {
self.endings_in(from, self.pos);
}
if ends_trivia(rest[run]) {
return Ok(());
}
}
b'/' => match self.bytes.get(self.pos + 1) {
Some(b'/' | b'*') if !self.dialect.comments() => {
return Err(self.comment_not_allowed());
}
Some(b'/') => self.line_comment(),
Some(b'*') => self.block_comment()?,
_ => return Ok(()),
},
0x0B | 0x0C if self.json5 => self.pos += 1,
0x80.. if self.json5 => {
let c = self.char_at(self.pos);
if !is_json5_space(c) {
return Ok(());
}
self.pos += c.len_utf8();
}
_ => return Ok(()),
}
}
}
fn line_comment(&mut self) {
let mut from = self.pos + 2;
if self.dialect.line_comment_ends_only_at_lf() {
self.pos =
memchr::memchr(b'\n', &self.bytes[from..]).map_or(self.bytes.len(), |n| from + n);
if self.cr_mask != 0 && self.pos < self.bytes.len() && self.bytes[self.pos - 1] == b'\r'
{
self.ending(self.pos - 1, Eol::CrLf);
}
return;
}
while let Some(found) = memchr::memchr3(b'\n', b'\r', 0xE2, &self.bytes[from..]) {
let at = from + found;
let separator =
self.bytes[at] != 0xE2 || (self.json5 && line_separator_at(self.bytes, at));
if separator {
self.pos = at;
return;
}
from = at + 1;
}
self.pos = self.bytes.len();
}
fn block_comment(&mut self) -> Result<(), Fail> {
let start = self.pos;
let mut from = self.pos + 2;
while let Some(found) = memchr::memchr(b'*', &self.bytes[from..]) {
let at = from + found;
if self.bytes.get(at + 1) == Some(&b'/') {
self.pos = at + 2;
if self.cr_mask != 0 {
self.endings_in(start + 2, at);
}
return Ok(());
}
from = at + 1;
}
Err(Fail::inside(
self.bytes.len(),
SyntaxKind::UnterminatedComment,
start,
))
}
}
fn ends_trivia(b: u8) -> bool {
b > b' ' && b != b'/' && b < 0x80
}
const DOUBLE_QUOTE: u8 = 1;
const SINGLE_QUOTE: u8 = 2;
const BACKSLASH: u8 = 4;
const LINE_BREAK: u8 = 8;
const CONTROL: u8 = 16;
const NON_ASCII: u8 = 32;
#[expect(clippy::cast_possible_truncation, reason = "b stays below 256")]
static STRING_CLASS: [u8; 256] = {
let mut table = [0; 256];
let mut b = 0;
while b < 256 {
table[b] = match b as u8 {
b'"' => DOUBLE_QUOTE,
b'\'' => SINGLE_QUOTE,
b'\\' => BACKSLASH,
b'\n' | b'\r' => LINE_BREAK,
0..0x20 => CONTROL,
0x80.. => NON_ASCII,
_ => 0,
};
b += 1;
}
table
};
fn string_stops(quote: u8, json5: bool, ascii_only: bool) -> u8 {
let quote = if quote == b'"' {
DOUBLE_QUOTE
} else {
SINGLE_QUOTE
};
let control = if json5 { 0 } else { CONTROL };
let high = if ascii_only { NON_ASCII } else { 0 };
quote | BACKSLASH | LINE_BREAK | control | high
}
fn plain_bytes(bytes: &[u8], stops: u8, quote: u8, ascii_only: bool) -> usize {
let stop = |&b: &u8| STRING_CLASS[usize::from(b)] & stops != 0;
let head = bytes.len().min(16);
if let Some(i) = bytes[..head].iter().position(stop) {
return i;
}
let run = head + plain_run(&bytes[head..], quote, ascii_only);
run + bytes[run..]
.iter()
.position(stop)
.unwrap_or(bytes.len() - run)
}
#[expect(
clippy::needless_bitwise_bool,
reason = "no branch per byte, so the block compiles to vector compares"
)]
fn plain_run(bytes: &[u8], quote: u8, ascii_only: bool) -> usize {
let high = if ascii_only { 0x80 } else { 0 };
bytes
.as_chunks::<16>()
.0
.iter()
.take_while(|block| {
!block.iter().fold(false, |stop, &b| {
stop | (b == quote) | (b == b'\\') | (b < 0x20) | (b & high != 0)
})
})
.count()
* 16
}
fn push_wtf8(buffer: &mut Vec<u8>, code_point: u32) {
match char::from_u32(code_point) {
Some(c) => buffer.extend_from_slice(c.encode_utf8(&mut [0; 4]).as_bytes()),
None => buffer.extend_from_slice(&[
0xED,
0x80 | ((code_point >> 6) & 0x3F) as u8,
0x80 | (code_point & 0x3F) as u8,
]),
}
}
#[cfg(test)]
mod tests {
use std::hash::RandomState;
use super::{Key, Keys, LINEAR_KEYS, plain_bytes, plain_run, short_hash, spread, string_stops};
#[test]
fn spread_puts_the_hash_in_both_halves() {
assert_eq!(spread(0x1234_5678), 0x1234_5678_1234_5678);
}
#[test]
fn short_hash_tells_keys_apart() {
let state = RandomState::new();
let hashes: std::collections::HashSet<u32> = (0..1000)
.map(|i| short_hash(&state, format!("k{i}").as_bytes()))
.collect();
assert!(hashes.len() >= 998, "{}", hashes.len());
}
#[test]
fn keys_index_only_an_object_past_the_linear_limit() {
let mut keys = Keys::default();
let key = |i: usize| Key::from(format!("k{i}").into_bytes());
for i in 0..LINEAR_KEYS {
assert_eq!(keys.first_or_insert(&key(i), i), None);
}
assert_eq!(keys.index.len(), 0);
for i in LINEAR_KEYS..2 * LINEAR_KEYS {
assert_eq!(keys.first_or_insert(&key(i), i), None);
}
assert_eq!(keys.index.len(), 2 * LINEAR_KEYS);
assert_eq!(keys.first_or_insert(&key(3), 99), Some(3));
assert_eq!(
keys.first_or_insert(&key(LINEAR_KEYS + 3), 99),
Some(LINEAR_KEYS + 3)
);
}
#[test]
fn a_plain_run_stops_at_the_block_holding_any_byte_that_needs_a_decision() {
let plain = "a".repeat(40);
assert_eq!(plain_run(plain.as_bytes(), b'"', true), 32);
assert_eq!(plain_run(&plain.as_bytes()[..15], b'"', true), 0);
for stop in ["\"", "\\", "\u{1f}", "\u{0}", "é"] {
for stops in [stop.to_owned(), stop.repeat(2)] {
let text = format!("{}{stops}{}", "a".repeat(20), "a".repeat(20));
assert_eq!(plain_run(text.as_bytes(), b'"', true), 16, "{stops:?}");
}
}
let text = format!("{}'é{}", "a".repeat(20), "a".repeat(20));
assert_eq!(plain_run(text.as_bytes(), b'"', false), 32);
assert_eq!(plain_run(text.as_bytes(), b'\'', false), 16);
assert_eq!(plain_run(" ".repeat(16).as_bytes(), b'"', true), 16);
}
#[test]
fn plain_bytes_stop_at_the_first_byte_that_needs_a_decision_in_the_dialect() {
for "e in b"\"'" {
for json5 in [false, true] {
for ascii_only in [false, true] {
let stops = string_stops(quote, json5, ascii_only);
let other = if quote == b'"' { "'" } else { "\"" };
let cases = [
(char::from(quote).to_string(), true),
(other.to_owned(), false),
("\\".to_owned(), true),
("\n".to_owned(), true),
("\r".to_owned(), true),
("\x01".to_owned(), !json5),
("\t".to_owned(), !json5),
("é".to_owned(), ascii_only),
];
for at in [0, 5, 15, 16, 20, 40] {
for (probe, stop) in &cases {
let text = format!("{}{probe}{}", "a".repeat(at), "a".repeat(40));
let want = if *stop { at } else { text.len() };
assert_eq!(
plain_bytes(text.as_bytes(), stops, quote, ascii_only),
want,
"{probe:?} at {at}, quote {quote}, json5 {json5}, ascii_only {ascii_only}"
);
}
}
let plain = "a".repeat(40);
assert_eq!(plain_bytes(plain.as_bytes(), stops, quote, ascii_only), 40);
}
}
}
let json5 = string_stops(b'\'', true, false);
for text in [
format!("a\t{}'", "a".repeat(40)),
format!("{}\t{}\r", "a".repeat(20), "a".repeat(20)),
] {
assert_eq!(
plain_bytes(text.as_bytes(), json5, b'\'', false),
text.len() - 1,
"{text:?}"
);
}
}
#[test]
fn escaped_surrogate_pair_identifier_decodes_to_exact_character() {
use crate::{Config, Dialect, parse};
let (report, events) = parse("{\\uD801\\uDC00: 1}", &Config::new(Dialect::Json5));
assert!(report.passed());
let events = events.expect("events");
assert_eq!(
events[1].kind,
crate::EventKind::Key(Key::from("\u{10400}".as_bytes()))
);
}
}