use crate::instant::describe_malformed_instant;
use crate::scalar::{
self, MAX_DIAGNOSED_LENGTH, ScalarError, bare_key_end, describe_bad_number, describe_character,
describe_unknown_word, has_date_prefix, is_bare_key, is_bare_key_byte,
is_quotable_key_character, line_start, quoting_example, skip_spaces,
};
use crate::tree::Key;
use crate::{Duration, Error, Instant, abbreviate};
use std::borrow::Cow;
use std::collections::{HashMap, HashSet};
use std::num::NonZeroUsize;
pub(crate) const MAX_DEPTH: usize = 100;
const KEY_QUOTING_HINT: &str =
". A key that contains characters other than letters, digits, “_”, and “-” must be quoted";
#[derive(Debug, Clone, PartialEq)]
pub(crate) struct Node<'de> {
pub kind: Kind<'de>,
pub offset: Offset,
pub end: usize,
}
impl Node<'_> {
pub(crate) fn sort_members(&mut self) {
match &mut self.kind {
Kind::Object(object) => {
object
.members
.sort_unstable_by(|(left, _), (right, _)| left.cmp(right));
object.index = None;
for (_, member) in &mut object.members {
member.value.sort_members();
}
}
Kind::Array(items) => {
for item in items {
item.sort_members();
}
}
_ => {}
}
}
}
impl<'de> From<Kind<'de>> for Node<'de> {
fn from(kind: Kind<'de>) -> Self {
Self {
kind,
offset: Offset::NONE,
end: 0,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct Offset(Option<NonZeroUsize>);
impl Offset {
pub(crate) const NONE: Self = Self(None);
pub(crate) const fn at(offset: usize) -> Self {
Self(NonZeroUsize::new(offset + 1))
}
pub(crate) const fn get(self) -> Option<usize> {
match self.0 {
Some(offset) => Some(offset.get() - 1),
None => None,
}
}
}
#[derive(Debug, Clone, PartialEq)]
pub(crate) enum Kind<'de> {
Null,
Bool(bool),
Int(i64),
Float(f64),
String(Cow<'de, str>),
Instant(Instant),
Duration(Duration),
Array(Vec<Node<'de>>),
Object(Object<'de>),
}
impl Kind<'_> {
pub(crate) const fn describe(&self) -> &'static str {
match self {
Self::Null => "null",
Self::Bool(_) => "a bool",
Self::Int(_) => "an int",
Self::Float(_) => "a float",
Self::String(_) => "a string",
Self::Instant(_) => "an instant",
Self::Duration(_) => "a duration",
Self::Array(_) => "an array",
Self::Object(_) => "an object",
}
}
}
#[derive(Debug, Clone, PartialEq, Default)]
pub(crate) struct Object<'de> {
pub members: Vec<(Cow<'de, str>, Member<'de>)>,
#[allow(
clippy::box_collection,
reason = "The box keeps every object one word smaller, and most objects have no index."
)]
index: Option<Box<HashMap<Cow<'de, str>, usize>>>,
}
const MAX_UNINDEXED_MEMBERS: usize = 16;
impl<'de> Object<'de> {
pub(crate) const fn new(members: Vec<(Cow<'de, str>, Member<'de>)>) -> Self {
Self {
members,
index: None,
}
}
pub(crate) fn position(&self, key: &str) -> Option<usize> {
match &self.index {
Some(index) => index.get(key).copied(),
None => self
.members
.iter()
.position(|(member_key, _)| member_key == key),
}
}
pub(crate) fn push(&mut self, key: Cow<'de, str>, member: Member<'de>) -> usize {
let position = self.members.len();
if let Some(index) = &mut self.index {
index.insert(key.clone(), position);
} else if position == MAX_UNINDEXED_MEMBERS {
let mut index: HashMap<Cow<'de, str>, usize> = self
.members
.iter()
.enumerate()
.map(|(position, (key, _))| (key.clone(), position))
.collect();
index.insert(key.clone(), position);
self.index = Some(Box::new(index));
}
self.members.push((key, member));
position
}
}
pub(crate) const MAX_FILTERED_KEYS: usize = 32;
pub(crate) struct ObjectKeys<'a> {
start: usize,
filter: u64,
index: Option<HashSet<Cow<'a, str>>>,
}
impl<'a> ObjectKeys<'a> {
pub(crate) const fn new(stack: &[Cow<'a, str>]) -> Self {
Self {
start: stack.len(),
filter: 0,
index: None,
}
}
#[inline]
pub(crate) fn insert(&mut self, stack: &mut Vec<Cow<'a, str>>, key: Cow<'a, str>) -> bool {
if let Some(index) = &mut self.index {
return index.insert(key);
}
let bit = 1 << fingerprint(key.as_bytes());
if self.filter & bit != 0
&& stack[self.start..].iter().any(|other| {
other.len() == key.len()
&& other.as_bytes().first() == key.as_bytes().first()
&& *other == key
}) {
return false;
}
self.filter |= bit;
stack.push(key);
if stack.len() - self.start > MAX_FILTERED_KEYS {
self.index = Some(stack.drain(self.start..).collect());
}
true
}
pub(crate) fn end(&self, stack: &mut Vec<Cow<'a, str>>) {
stack.truncate(self.start);
}
}
pub(crate) fn fingerprint(bytes: &[u8]) -> u32 {
let (Some(&first), Some(&last)) = (bytes.first(), bytes.last()) else {
return 0;
};
let middle = bytes[bytes.len() / 2];
let mixed = u32::from(first)
| u32::from(middle) << 8
| u32::from(last) << 16
| (bytes.len() as u32) << 24;
mixed.wrapping_mul(0x9E37_79B1) >> 26
}
#[derive(Debug, Clone, PartialEq)]
pub(crate) struct Member<'de> {
pub key_offset: Offset,
pub key_end: usize,
pub value: Node<'de>,
}
impl<'de> Member<'de> {
pub(crate) fn new(value: Node<'de>) -> Self {
Self {
key_offset: Offset::NONE,
key_end: 0,
value,
}
}
}
pub(crate) fn parse(source: &str) -> Result<Node<'_>, Error> {
check_characters(source)?;
parse_after_character_check(source)
}
pub(crate) fn parse_after_character_check(source: &str) -> Result<Node<'_>, Error> {
Parser::new(source)
.parse_document()
.map_err(|error| Error::at(error.message, source, error.offset))
}
pub(crate) fn is_valid_numeric_token(text: &str) -> bool {
scalar::token_value(text).is_some_and(|value| value.is_ok())
}
pub(crate) fn decode(bytes: &[u8]) -> Result<&str, Error> {
std::str::from_utf8(bytes).map_err(|error| {
let offset = error.valid_up_to();
let valid = std::str::from_utf8(&bytes[..offset]).unwrap_or_default();
match error.error_len() {
None => Error::at(
"Incomplete UTF-8 sequence at the end of the input",
valid,
offset,
),
Some(_) => Error::at(
format!("Invalid UTF-8 byte 0x{:02X}", bytes[offset]),
valid,
offset,
),
}
})
}
pub(crate) fn check_characters(source: &str) -> Result<(), Error> {
if source.starts_with('\u{FEFF}') {
return Err(Error::at(
"A byte order mark (BOM) is not allowed",
source,
0,
));
}
let Some(offset) = find_control(source.as_bytes()) else {
return Ok(());
};
let byte = source.as_bytes()[offset];
if byte == b'\r' {
return Err(Error::at(
"A carriage return (U+000D) is not allowed anywhere. Use LF line endings",
source,
offset,
));
}
Err(Error::at(
format!(
"A raw control character (U+{byte:04X}) is not allowed anywhere, including in strings and comments. In a string, write it as the escape \\u{{{byte:x}}} inside \"...\""
),
source,
offset,
))
}
const fn is_control(byte: u8) -> bool {
(byte < 0x20 && byte != b'\t' && byte != b'\n') || byte == 0x7F
}
fn find_control(bytes: &[u8]) -> Option<usize> {
const BLOCK: usize = 32;
let (blocks, remainder) = bytes.as_chunks::<BLOCK>();
let remainder_start = bytes.len() - remainder.len();
for (block_index, block) in blocks.iter().enumerate() {
if block
.iter()
.fold(0, |found, &byte| found | u8::from(is_control(byte)))
!= 0
{
return block
.iter()
.position(|&byte| is_control(byte))
.map(|position| block_index * BLOCK + position);
}
}
bytes[remainder_start..]
.iter()
.position(|&byte| is_control(byte))
.map(|position| remainder_start + position)
}
type Result<T, E = ScalarError> = std::result::Result<T, E>;
#[derive(Clone)]
pub(crate) struct Parser<'de> {
source: &'de str,
bytes: &'de [u8],
pub(crate) index: usize,
document_start: usize,
}
impl<'de> Parser<'de> {
pub(crate) const fn new(source: &'de str) -> Self {
Self {
source,
bytes: source.as_bytes(),
index: 0,
document_start: 0,
}
}
#[cold]
fn fail<T>(&self, message: impl Into<String>, offset: usize) -> Result<T> {
Err(ScalarError::new(message, offset))
}
#[cold]
fn fail_too_deep<T>(&self, offset: usize) -> Result<T> {
self.fail(
format!("The document is nested more than {MAX_DEPTH} levels deep"),
offset,
)
}
#[inline]
pub(crate) fn peek(&self) -> Option<u8> {
self.bytes.get(self.index).copied()
}
#[inline]
fn is_at_end(&self) -> bool {
self.index >= self.bytes.len()
}
fn parse_document(&mut self) -> Result<Node<'de>> {
self.start_document()?;
let value = match self.peek() {
Some(b'{') => self.parse_object(1)?,
Some(b'[') => self.parse_array(1)?,
_ => self.parse_bare_object()?,
};
self.end_document()?;
Ok(value)
}
pub(crate) fn start_document(&mut self) -> Result<()> {
self.skip_trivia()?;
self.document_start = self.index;
if self.is_at_end() {
return self.fail(
"A document must contain an object or an array, but this one is empty",
self.index,
);
}
Ok(())
}
pub(crate) fn end_document(&mut self) -> Result<()> {
self.skip_trivia()?;
if !self.is_at_end() {
return self.fail(
format!(
"Unexpected {} after the end of the document",
self.describe_here()
),
self.index,
);
}
Ok(())
}
pub(crate) fn parse_bare_object(&mut self) -> Result<Node<'de>> {
let start = self.index;
let mut object = Object::default();
if let Err(error) = self.parse_entry(&mut object, 1) {
return Err(self.diagnose_bare_value(start).unwrap_or(error));
}
let mut end = self.index;
while self.next_bare_entry()? {
self.parse_entry(&mut object, 1)?;
end = self.index;
}
Ok(Node {
kind: Kind::Object(object),
offset: Offset::at(start),
end,
})
}
#[inline]
pub(crate) fn next_bare_entry(&mut self) -> Result<bool> {
let has_line_break = self.skip_trivia()?;
if self.is_at_end() {
return Ok(false);
}
if self.peek() == Some(b',') {
return self.fail(
"Top-level entries are separated by line breaks, not commas. Use braces for a one-line object",
self.index,
);
}
if !has_line_break {
return self.fail(
format!(
"Expected a line break before the next entry, but found {}{}",
self.describe_here(),
self.slash_comment_hint()
),
self.index,
);
}
Ok(true)
}
#[cold]
fn diagnose_bare_value(&mut self, start: usize) -> Option<ScalarError> {
self.index = start;
let is_bare_value =
self.parse_value(1).is_ok() && self.skip_trivia().is_ok() && self.is_at_end();
is_bare_value.then(|| ScalarError::new("A bare value is not a document. A document is an object or an array, so write it as `key: value` or `[value]`", start))
}
#[inline]
fn skip_trivia(&mut self) -> Result<bool> {
let (index, has_line_break) = skip_trivia(self.bytes, self.index)?;
self.index = index;
Ok(has_line_break)
}
fn parse_entry(&mut self, object: &mut Object<'de>, depth: usize) -> Result<()> {
let key_start = self.index;
let (key, colon) = self.parse_entry_key()?;
let value = match self.parse_value(depth + 1) {
Ok(value) => value,
Err(error) => {
self.diagnose_bad_value(&error, &key, key_start, colon)?;
return Err(error);
}
};
if object.position(&key).is_some() {
return self.fail(format!("Duplicate key {}", describe_key(&key)), key_start);
}
object.push(
key,
Member {
key_offset: Offset::at(key_start),
key_end: colon,
value,
},
);
Ok(())
}
#[inline]
pub(crate) fn parse_entry_key(&mut self) -> Result<(Cow<'de, str>, usize)> {
let key_start = self.index;
let key = self.parse_key()?;
if self.peek() == Some(b'.') {
return self.fail_dot_in_key(key_start);
}
if self.peek() != Some(b':') {
return self.fail_missing_colon(key_start);
}
let colon = self.index;
self.index += 1;
self.skip_trivia()?;
Ok((key, colon))
}
#[cold]
fn diagnose_bad_value(
&mut self,
error: &ScalarError,
key: &str,
key_start: usize,
colon: usize,
) -> Result<()> {
if self
.bytes
.get(colon + 1)
.is_some_and(|&byte| is_bare_key_byte(byte))
{
self.diagnose_key_with_colon(key_start)?;
}
self.index = colon + 1;
let is_value_on_next_line = self.skip_trivia()?;
let value_start = self.index;
let comment_hint = self.describe_comment_as_value(colon);
if is_value_on_next_line {
self.diagnose_missing_value(value_start, key, key_start, &comment_hint)?;
}
if !comment_hint.is_empty()
&& error.offset == value_start
&& matches!(self.bytes.get(value_start), None | Some(b'}'))
{
return self.fail(format!("{}{comment_hint}", error.message), value_start);
}
Ok(())
}
fn diagnose_key_with_colon(&self, key_start: usize) -> Result<()> {
for index in key_start..key_start + MAX_DIAGNOSED_LENGTH {
match self.bytes.get(index) {
Some(b':') => {
if matches!(self.bytes.get(index + 1), None | Some(b'\n' | b' ' | b'\t')) {
return self.fail(
format!(
"A key that contains “:” must be quoted, as in '{}'",
abbreviate(&self.source[key_start..index], 40)
),
key_start,
);
}
}
Some(&byte) if is_bare_key_byte(byte) => {}
_ => return Ok(()),
}
}
Ok(())
}
fn describe_comment_as_value(&self, colon: usize) -> String {
let hash = skip_spaces(self.bytes, colon + 1);
if self.bytes.get(hash) != Some(&b'#') {
return String::new();
}
let is_value_byte = |byte: &u8| !matches!(byte, b'\t' | b'\n' | b' ' | b',' | b']' | b'}');
let rest =
&self.bytes[hash + 1..crate::utf16_limit(self.source, hash, MAX_DIAGNOSED_LENGTH)];
if !rest
.first()
.is_some_and(|byte| *byte != b'#' && is_value_byte(byte))
{
return String::new();
}
let end = hash + 1 + rest.iter().take_while(|byte| is_value_byte(byte)).count();
let end = self.source.floor_char_boundary(end);
format!(
". “#” starts a comment, so a value that starts with “#” must be quoted{}",
quoting_example(&self.source[hash..end])
)
}
#[cold]
fn diagnose_missing_value(
&mut self,
start: usize,
parent: &str,
key_start: usize,
comment_hint: &str,
) -> Result<()> {
if self.bytes.get(start) == Some(&b'-')
&& matches!(self.bytes.get(start + 1), Some(b' ' | b'\t'))
{
return self.fail(
"Expected a value, but found a “-” list. An array is written in brackets, as in [80, 443]",
start,
);
}
self.index = start;
let Ok(key) = self.parse_key() else {
return Ok(());
};
if self.peek() != Some(b':') {
return Ok(());
}
let is_quoted = matches!(self.bytes[start], b'\'' | b'"');
if is_quoted
|| matches!(
self.bytes.get(self.index + 1),
None | Some(b' ' | b'\t' | b'\n')
) {
let hint = if comment_hint.is_empty() {
self.describe_indented_key(parent, &key, key_start, start)
} else {
comment_hint.to_owned()
};
return self.fail(
format!(
"Expected a value, but found the key {}{hint}",
abbreviate(&describe_key(&key), 200)
),
start,
);
}
Ok(())
}
fn describe_indented_key(
&self,
parent: &str,
key: &str,
key_start: usize,
start: usize,
) -> String {
let (Some(key_indentation), Some(indentation)) =
(self.indentation(key_start), self.indentation(start))
else {
return String::new();
};
if indentation <= key_indentation {
return String::new();
}
let parent = Key::new(parent).to_string();
let parent = abbreviate(&parent, 200);
let child = Key::new(key).to_string();
let child = abbreviate(&child, 200);
format!(". Indentation does not nest objects, so write {parent}: {{{child}: …}}")
}
fn indentation(&self, offset: usize) -> Option<usize> {
let line_start = line_start(self.bytes, offset);
(skip_spaces(self.bytes, line_start) == offset).then_some(offset - line_start)
}
#[cold]
fn fail_missing_colon<T>(&mut self, key_start: usize) -> Result<T> {
let next = skip_spaces(self.bytes, self.index);
let next_byte = self.bytes.get(next).copied();
if next > self.index && next_byte == Some(b':') {
return self.fail(
"Whitespace is not allowed between a key and its “:”",
self.index,
);
}
if self.bytes[next..].starts_with(b"/*")
&& let Some(comment_end) = block_comment_end(self.bytes, next)
&& self.bytes.get(skip_spaces(self.bytes, comment_end + 2)) == Some(&b':')
{
return self.fail("A comment is not allowed between a key and its “:”", next);
}
let line_end = scalar::line_end(self.bytes, next);
let colon = self.bytes[next..line_end]
.iter()
.position(|&byte| byte == b':')
.map(|length| next + length);
if next > self.index
&& let Some(colon) = colon
&& next_byte.is_some_and(is_bare_key_byte)
&& matches!(self.bytes.get(colon + 1), None | Some(b' ' | b'\t' | b'\n'))
{
let key = self.source[key_start..colon].trim_end_matches([' ', '\t']);
if key
.bytes()
.all(|byte| byte == b' ' || byte == b'\t' || is_bare_key_byte(byte))
{
return self.fail(
format!(
"A bare key cannot contain spaces. Quote it, as in '{}'",
abbreviate(key, 40)
),
key_start,
);
}
}
if matches!(self.peek(), None | Some(b'\n')) {
return self.fail("Expected “:” after the key", self.index);
}
let is_quotable = next == self.index
&& !matches!(self.bytes[next - 1], b'\'' | b'"')
&& self.source[next..].starts_with(is_quotable_key_character);
let hint = if is_quotable { KEY_QUOTING_HINT } else { "" };
self.index = next;
self.fail(
format!(
"Expected “:” after the key, but found {}{hint}",
self.describe_here()
),
next,
)
}
#[inline]
fn parse_key(&mut self) -> Result<Cow<'de, str>> {
let start = self.index;
match self.peek() {
Some(b'\'' | b'"') => {
if scalar::is_block_string(self.bytes, start) {
return self.fail("A block string cannot be a key", start);
}
let (value, end) = scalar::string(self.source, start)?;
self.index = end;
Ok(value)
}
_ => {
let end = bare_key_end(self.bytes, start);
if end == start {
return self.fail_missing_key(start);
}
self.index = end;
Ok(Cow::Borrowed(&self.source[start..end]))
}
}
}
#[cold]
fn fail_missing_key<T>(&self, start: usize) -> Result<T> {
if self.peek() == Some(b'[') {
self.diagnose_table_header(false)?;
}
if self.is_at_end() {
return self.fail("Expected a key", start);
}
self.fail(
format!(
"Expected a key, but found {}{}{}",
self.describe_here(),
self.key_quoting_hint(),
self.slash_comment_hint()
),
start,
)
}
fn key_quoting_hint(&self) -> String {
let rest = &self.source[self.index..];
let diagnosed_end = crate::utf16_limit(rest, 0, MAX_DIAGNOSED_LENGTH);
let diagnosed = &rest[..diagnosed_end];
if !rest.starts_with(is_quotable_key_character) {
return String::new();
}
let length = diagnosed
.find(|character| !is_quotable_key_character(character))
.unwrap_or(diagnosed.len());
let is_diagnosed = length < diagnosed.len()
|| rest.len() == diagnosed.len()
&& diagnosed.encode_utf16().count() < MAX_DIAGNOSED_LENGTH;
if is_diagnosed && rest[length..].starts_with(':') {
format!(
"{KEY_QUOTING_HINT}, as in '{}'",
abbreviate(&rest[..length], 40)
)
} else {
KEY_QUOTING_HINT.to_owned()
}
}
#[cold]
fn fail_dot_in_key<T>(&self, key_start: usize) -> Result<T> {
let end = self.index
+ self.bytes[self.index..]
.iter()
.take(MAX_DIAGNOSED_LENGTH.saturating_sub(self.index - key_start))
.take_while(|&&byte| is_bare_key_byte(byte) || byte == b'.')
.count();
let key = &self.source[key_start..end];
if self.bytes.get(end) != Some(&b':')
|| !is_bare_key_byte(self.bytes[key_start])
|| key.split('.').any(str::is_empty)
{
return self.fail(
"A key cannot contain “.” unless it is quoted. Quote the whole key, or use braces to nest, as in a: {b: …}",
self.index,
);
}
let mut nested = String::with_capacity(key.len() * 4 + 4);
let mut parts = key.split('.').peekable();
let mut parents = 0;
while let Some(part) = parts.next() {
nested.push_str(part);
nested.push_str(": ");
if parts.peek().is_some() {
nested.push('{');
parents += 1;
} else {
nested.push('…');
}
}
nested.extend(std::iter::repeat_n('}', parents));
self.fail(
format!(
"A bare key cannot contain “.”. Quote it, as in '{}', or use braces to nest, as in {}",
abbreviate(key, 40),
abbreviate(&nested, 40)
),
self.index,
)
}
fn parse_object(&mut self, depth: usize) -> Result<Node<'de>> {
let mut object = Object::default();
let start = self.parse_braced(depth, Collection::Object, |parser| {
parser.parse_entry(&mut object, depth)
})?;
Ok(Node {
kind: Kind::Object(object),
offset: Offset::at(start),
end: self.index,
})
}
fn parse_array(&mut self, depth: usize) -> Result<Node<'de>> {
let mut items = Vec::new();
let start = self.parse_braced(depth, Collection::Array, |parser| {
items.push(parser.parse_value(depth + 1)?);
Ok(())
})?;
Ok(Node {
kind: Kind::Array(items),
offset: Offset::at(start),
end: self.index,
})
}
fn parse_braced(
&mut self,
depth: usize,
collection: Collection,
mut item: impl FnMut(&mut Self) -> Result<()>,
) -> Result<usize> {
let start = self.open_braced(depth)?;
while self.next_braced_item(collection, start)? {
item(self)?;
self.after_braced_item(collection, start)?;
}
Ok(start)
}
#[inline]
pub(crate) fn open_braced(&mut self, depth: usize) -> Result<usize> {
let start = self.index;
if depth > MAX_DEPTH {
return self.fail_too_deep(start);
}
self.index += 1;
self.skip_trivia()?;
Ok(start)
}
#[inline]
pub(crate) fn next_braced_item(
&mut self,
collection: Collection,
start: usize,
) -> Result<bool> {
let closing = collection.closing();
if self.peek() == Some(closing) {
self.index += 1;
return Ok(false);
}
if self.is_at_end() {
return self.fail_unterminated(collection, start);
}
Ok(true)
}
#[inline]
pub(crate) fn after_braced_item(&mut self, collection: Collection, start: usize) -> Result<()> {
let closing = collection.closing();
let item_end = self.index;
let has_line_break = self.skip_trivia()?;
match self.peek() {
Some(b',') => {
if has_line_break {
return self.fail(
"A comma must be on the same line as the item before it. The line break already separates the items, so remove the comma",
self.index,
);
}
self.index += 1;
self.skip_trivia()?;
}
Some(byte) if byte == closing || has_line_break => {}
None => return self.fail_unterminated(collection, start),
Some(_) => {
let (container, item_name) = collection.names();
let closing_text = char::from(closing);
let hint = if self.bytes[item_end..self.index].contains(&b'\n') {
". A line break inside a block comment does not separate items"
} else {
self.slash_comment_hint()
};
return self.fail(
format!(
"Expected “,”, a line break, or “{closing_text}” after an {container} {item_name}, but found {}{hint}",
self.describe_here()
),
self.index,
);
}
}
Ok(())
}
#[cold]
fn fail_unterminated<T>(&self, collection: Collection, start: usize) -> Result<T> {
let (container, _) = collection.names();
self.fail(
format!(
"Unterminated {container}: expected “{}”",
char::from(collection.closing())
),
start,
)
}
pub(crate) fn parse_value(&mut self, depth: usize) -> Result<Node<'de>> {
match self.peek() {
Some(b'{') => self.parse_object(depth),
Some(b'[') => self.parse_array(depth),
_ => self.parse_scalar(),
}
}
#[inline]
pub(crate) fn parse_scalar(&mut self) -> Result<Node<'de>> {
let start = self.index;
let mut is_number = false;
let kind = match self.peek() {
Some(b'\'' | b'"') => {
let (value, end) = scalar::string(self.source, start)?;
self.index = end;
Kind::String(value)
}
Some(b't') if self.eat_keyword("true") => Kind::Bool(true),
Some(b'f') if self.eat_keyword("false") => Kind::Bool(false),
Some(b'n') if self.eat_keyword("null") => Kind::Null,
Some(b'i') if self.eat_keyword("infinity") => Kind::Float(f64::INFINITY),
Some(b'-') if self.eat_keyword("-infinity") => Kind::Float(f64::NEG_INFINITY),
Some(b'0'..=b'9' | b'-') => {
let end = scalar::number_end(self.bytes, start);
self.index = end;
match scalar::token_value(&self.source[start..end]) {
Some(Ok(kind)) => {
is_number = matches!(kind, Kind::Int(_) | Kind::Float(_));
kind
}
Some(Err(message)) => {
let message = self
.describe_malformed_instant(start, end)
.unwrap_or(message);
return self.fail(message, start);
}
None => return self.fail(self.describe_bad_number(start, end), start),
}
}
_ => return self.fail_unexpected_value(),
};
if self.peek().is_some_and(|next| !can_follow_value(next)) {
return self.fail_after_value(start, is_number);
}
if is_number && self.is_word_after_space() {
self.diagnose_unit_after_space(start)?;
}
Ok(Node {
kind,
offset: Offset::at(start),
end: self.index,
})
}
#[cold]
fn fail_after_value<T>(&self, start: usize, is_number: bool) -> Result<T> {
let rest = &self.source[self.index..];
if is_number && (rest.starts_with("\u{B5}s") || rest.starts_with("\u{3BC}s")) {
let number = &self.source[start..self.index];
let example = if number.len() <= MAX_DIAGNOSED_LENGTH
&& is_valid_numeric_token(&format!("{number}us"))
{
format!(", as in {}us", abbreviate(number, 40))
} else {
String::new()
};
return self.fail(
format!("The unit for microseconds is written us{example}"),
self.index,
);
}
if self.peek() == Some(b'\'') && self.bytes[start] == b'\'' {
return self.fail(
"There is no '' escape in a '...' string. Write a string that contains ' as \"...\", as in \"it's\"",
self.index,
);
}
self.fail(
format!("Unexpected {} after a value", self.describe_here()),
self.index,
)
}
fn is_word_after_space(&self) -> bool {
matches!(self.peek(), Some(b' ' | b'\t'))
&& self
.bytes
.get(skip_spaces(self.bytes, self.index))
.is_some_and(u8::is_ascii_alphabetic)
}
#[cold]
fn diagnose_unit_after_space(&self, start: usize) -> Result<()> {
let unit_start = skip_spaces(self.bytes, self.index);
let unit_end = scalar::run_end(self.bytes, unit_start, |byte| byte.is_ascii_alphabetic());
let unit = &self.source[unit_start..unit_end];
if unit.is_empty()
|| !is_value_end_at(self.bytes, skip_spaces(self.bytes, unit_end))
|| matches!(unit, "true" | "false" | "null" | "infinity")
{
return Ok(());
}
let number = &self.source[start..self.index];
let duration = if matches!(unit, "h" | "m" | "s" | "ms" | "us" | "ns")
&& number.len() <= MAX_DIAGNOSED_LENGTH
&& is_valid_numeric_token(&format!("{number}{unit}"))
{
format!("{}{unit}", abbreviate(number, 40))
} else {
"10s".to_owned()
};
self.fail(
format!(
"A unit cannot follow a number after a space. Write a duration without the space, as in {duration}, and anything else, such as a size, as a string, as in '{}'",
abbreviate(&format!("{} {}", abbreviate(number, 40), abbreviate(unit, 40)), 40)
),
unit_start,
)
}
#[cold]
fn describe_malformed_instant(&self, start: usize, end: usize) -> Option<String> {
let text = &self.source[start..end];
if !has_date_prefix(text.as_bytes()) {
return None;
}
let time_start = end + 1;
let time_end = if self.bytes.get(end) == Some(&b' ')
&& self.bytes.get(time_start).is_some_and(u8::is_ascii_digit)
{
scalar::number_end(self.bytes, time_start)
} else {
end
};
let time = if time_end > end {
&self.source[time_start..time_end]
} else {
""
};
let is_whole_value = is_value_end_at(self.bytes, time_end)
&& !(self.bytes.get(time_end) == Some(&b',')
&& self.bytes.get(time_end + 1).is_some_and(u8::is_ascii_digit));
describe_malformed_instant(text, time, is_whole_value, self.offset_after_space(end))
}
fn offset_after_space(&self, index: usize) -> Option<&'de str> {
let start = skip_spaces(self.bytes, index);
if start == index {
return None;
}
let length = match self.bytes.get(start..)? {
[b'Z', ..] => 1,
[b'+' | b'-', a, b, b':', c, d, ..]
if [a, b, c, d].iter().all(|byte| byte.is_ascii_digit()) =>
{
6
}
_ => return None,
};
is_value_end_at(self.bytes, start + length).then(|| &self.source[start..start + length])
}
#[cold]
fn describe_bad_number(&self, start: usize, end: usize) -> String {
let text = &self.source[start..end];
self.describe_thousands_separator(text, start)
.unwrap_or_else(|| describe_bad_number(text, self.unquoted_text(start)))
}
fn describe_thousands_separator(&self, text: &str, start: usize) -> Option<String> {
let bytes = self.bytes;
if !(text.len() == 3
&& text.starts_with('0')
&& text.bytes().all(|byte| byte.is_ascii_digit()))
|| start == 0
|| bytes[start - 1] != b','
{
return None;
}
let group_start = |group_end: usize| {
group_end
- bytes[..group_end]
.iter()
.rev()
.take_while(|byte| byte.is_ascii_digit())
.count()
};
let mut group_end = start - 1;
let mut number_start = group_start(group_end);
while group_end - number_start == 3
&& number_start >= 2
&& bytes[number_start - 1] == b','
&& bytes[number_start - 2].is_ascii_digit()
{
group_end = number_start - 1;
number_start = group_start(group_end);
}
let before = number_start.checked_sub(1).map(|index| bytes[index]);
if number_start == group_end
|| matches!(before, Some(b'.' | b'_'))
|| number_start + 3 < group_end
|| before.is_some_and(|byte| byte.is_ascii_alphabetic())
{
return None;
}
if before == Some(b'-') {
number_start -= 1;
}
let limit = bytes.len().min(start + text.len() + MAX_DIAGNOSED_LENGTH);
let mut groups_end = start + text.len();
while groups_end + 4 <= limit
&& bytes[groups_end] == b','
&& bytes[groups_end + 1..groups_end + 4]
.iter()
.all(u8::is_ascii_digit)
&& !(groups_end + 4 < limit && bytes[groups_end + 4].is_ascii_digit())
{
groups_end += 4;
}
let number = &self.source[number_start..groups_end];
if number.len() > MAX_DIAGNOSED_LENGTH {
return Some(format!(
"Leading zeros are not allowed in a decimal number. A comma separates items, so {} is not one number",
abbreviate(number, 40)
));
}
let reason = format!(
"Leading zeros are not allowed in a decimal number. A comma separates items, so {} is not one number",
abbreviate(number, 40)
);
let with_underscores = number.replace(',', "_");
Some(if is_valid_numeric_token(&with_underscores) {
format!(
"{reason}. Write it as {} or {}",
abbreviate(&with_underscores, 40),
abbreviate(&number.replace(',', ""), 40)
)
} else {
reason
})
}
fn eat_keyword(&mut self, word: &str) -> bool {
let end = self.index + word.len();
if !self.bytes[self.index..].starts_with(word.as_bytes())
|| self.bytes.get(end).copied().is_some_and(is_bare_key_byte)
{
return false;
}
self.index = end;
true
}
#[cold]
fn fail_unexpected_value<T>(&self) -> Result<T> {
let start = self.index;
match self.peek() {
None => {
return self.fail(
"Expected a value, but reached the end of the document",
start,
);
}
Some(b'+') => {
return self.fail(
"A “+” sign is not allowed. A number without a sign is positive",
start,
);
}
Some(b'.') => {
if self.bytes.get(start + 1).is_some_and(u8::is_ascii_digit) {
return self.fail(
"A number cannot begin with “.”; write a digit before it, as in 0.5",
start,
);
}
return self.fail(describe_unknown_word(".", self.unquoted_text(start)), start);
}
_ => {}
}
let word_end = bare_key_end(self.bytes, start);
if word_end > start {
let word = &self.source[start..word_end];
let spaces_start = skip_spaces_back(self.bytes, start);
let is_member_value =
spaces_start < start && spaces_start > 0 && self.bytes[spaces_start - 1] == b':';
if !is_member_value && self.bytes.get(word_end) == Some(&b':') {
return self.fail(
format!(
"Expected a value, but found the key {}",
abbreviate(word, 40)
),
start,
);
}
self.diagnose_table_header(true)?;
return self.fail(
describe_unknown_word(word, self.unquoted_text(start)),
start,
);
}
let hint = if self.is_block_scalar_indicator() {
". Write a multiline string as a block string, between \'\'\' lines"
} else {
self.slash_comment_hint()
};
self.fail(
format!("Expected a value, but found {}{hint}", self.describe_here()),
start,
)
}
fn unquoted_text(&self, start: usize) -> &'de str {
let bytes = self.bytes;
let limit = crate::utf16_limit(self.source, start, MAX_DIAGNOSED_LENGTH);
let is_end = |index: usize| {
let is_comment = bytes[index] == b'#'
|| (bytes[index] == b'/' && bytes.get(index + 1) == Some(&b'*'));
matches!(bytes[index], b'\n' | b',' | b']' | b'}')
|| (is_comment && index > 0 && matches!(bytes[index - 1], b' ' | b'\t'))
};
let mut end = start;
while end < limit && !is_end(end) {
end += 1;
}
self.source[start..end].trim_end_matches([' ', '\t'])
}
fn diagnose_table_header(&self, is_value: bool) -> Result<()> {
let bytes = self.bytes;
let line_start = line_start(bytes, self.index);
if is_value && skip_spaces(bytes, line_start) != self.document_start {
return Ok(());
}
let limit = bytes.len().min(line_start + MAX_DIAGNOSED_LENGTH);
if self.index > limit {
return Ok(());
}
let line_end = scalar::line_end(&bytes[..limit], self.index);
let line = bytes[line_start..line_end].trim_ascii_end();
let line = &line[skip_spaces(line, 0)..];
let Some(inner) = line.strip_prefix(b"[") else {
return Ok(());
};
let inner = inner.strip_prefix(b"[").unwrap_or(inner);
let (name, closing) = inner.split_at(bare_key_end(inner, 0));
let is_name = name
.first()
.is_some_and(|byte| byte.is_ascii_alphabetic() || *byte == b'_');
if !is_name || !matches!(closing, b"]" | b"]]") {
return Ok(());
}
let name = abbreviate(std::str::from_utf8(name).expect("the name is ASCII"), 40);
self.fail(
format!(
"There are no table headers. Write the table as an object, as in {name}: {{…}}"
),
self.index,
)
}
fn is_block_scalar_indicator(&self) -> bool {
if self.peek() != Some(b'|') {
return false;
}
let chomping = usize::from(matches!(self.bytes.get(self.index + 1), Some(b'-' | b'+')));
let end = skip_spaces(self.bytes, self.index + 1 + chomping);
matches!(self.bytes.get(end), None | Some(b'\n'))
}
fn slash_comment_hint(&self) -> &'static str {
if self.bytes[self.index..].starts_with(b"//") {
". A comment starts with “#”"
} else {
""
}
}
fn describe_here(&self) -> String {
match self.source[self.index..].chars().next() {
None => "the end of the document".to_owned(),
Some('\n') => "a line break".to_owned(),
Some(character) => describe_character(character),
}
}
}
#[derive(Clone, Copy)]
pub(crate) enum Collection {
Object,
Array,
}
impl Collection {
const fn closing(self) -> u8 {
match self {
Self::Object => b'}',
Self::Array => b']',
}
}
const fn names(self) -> (&'static str, &'static str) {
match self {
Self::Object => ("object", "member"),
Self::Array => ("array", "item"),
}
}
}
const fn can_follow_value(byte: u8) -> bool {
matches!(
byte,
b' ' | b'\t' | b'\n' | b',' | b']' | b'}' | b'#' | b'/'
)
}
fn is_value_end_at(bytes: &[u8], index: usize) -> bool {
match bytes.get(index) {
None => true,
Some(b'/') => matches!(bytes.get(index + 1), Some(b'*' | b'/')),
Some(&byte) => can_follow_value(byte),
}
}
#[inline]
pub(crate) fn skip_trivia(bytes: &[u8], mut index: usize) -> Result<(usize, bool)> {
let mut has_line_break = false;
loop {
match bytes.get(index) {
Some(b' ' | b'\t') => index = skip_spaces(bytes, index),
Some(b'\n') => {
has_line_break = true;
index += 1;
}
Some(b'#') => index = scalar::line_end(bytes, index),
Some(b'/') if bytes.get(index + 1) == Some(&b'*') => {
index = skip_block_comment(bytes, index)?;
}
_ => return Ok((index, has_line_break)),
}
}
}
fn skip_block_comment(bytes: &[u8], start: usize) -> Result<usize> {
let mut index = start + 2;
let mut nested = None;
while let Some(offset) = scalar::find_any(&bytes[index..], *b"*") {
index += offset;
if bytes.get(index + 1) == Some(&b'/') {
if let Some(nested) = nested {
return Err(ScalarError::new(
"Block comments cannot be nested, and their body may not contain “/*”",
nested,
));
}
return Ok(index + 2);
}
if nested.is_none() && bytes[index - 1] == b'/' {
nested = Some(index - 1);
}
index += 1;
}
Err(ScalarError::new("Unterminated block comment", start))
}
pub(crate) fn block_comment_end(bytes: &[u8], start: usize) -> Option<usize> {
find(&bytes[start + 2..], b"*/").map(|length| start + 2 + length)
}
fn find(haystack: &[u8], needle: &[u8; 2]) -> Option<usize> {
let mut start = 0;
while let Some(offset) = scalar::find_any(&haystack[start..], [needle[0]]) {
let index = start + offset;
if haystack.get(index + 1) == Some(&needle[1]) {
return Some(index);
}
start = index + 1;
}
None
}
fn skip_spaces_back(bytes: &[u8], index: usize) -> usize {
bytes[..index]
.iter()
.rposition(|byte| !matches!(byte, b' ' | b'\t'))
.map_or(0, |position| position + 1)
}
fn describe_key(key: &str) -> String {
let mut text = String::new();
write_described_key(&mut text, key);
text
}
pub(crate) fn write_described_key(output: &mut String, key: &str) {
let short = abbreviate(key, 40);
if is_bare_key(key) {
output.push_str(&short);
} else {
write_json_string(output, &short);
}
}
fn write_json_string(output: &mut String, text: &str) {
output.push('"');
for character in text.chars() {
match character {
'"' => output.push_str("\\\""),
'\\' => output.push_str("\\\\"),
'\u{8}' => output.push_str("\\b"),
'\t' => output.push_str("\\t"),
'\n' => output.push_str("\\n"),
'\u{C}' => output.push_str("\\f"),
'\r' => output.push_str("\\r"),
'\0'..='\u{1F}' => {
const HEX: &[u8; 16] = b"0123456789abcdef";
let byte = character as u8;
output.push_str("\\u00");
output.push(char::from(HEX[usize::from(byte >> 4)]));
output.push(char::from(HEX[usize::from(byte & 15)]));
}
_ => output.push(character),
}
}
output.push('"');
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn comment_scanning_matches_the_delimiter_grammar_exhaustively() {
for length in 0..=8 {
for mut state in 0..3_usize.pow(length) {
let mut text = String::from("/*");
for _ in 0..length {
text.push(['*', '/', 'x'][state % 3]);
state /= 3;
}
let result = skip_block_comment(text.as_bytes(), 0);
let expected = text[2..].find("*/").map(|end| end + 2);
match expected {
None => assert_eq!(
result.unwrap_err().message,
"Unterminated block comment",
"{text}"
),
Some(end) => match text[2..end].find("/*") {
Some(nested) => {
let error = result.unwrap_err();
assert_eq!(error.offset, nested + 2, "{text}");
assert!(error.message.starts_with("Block comments cannot be nested"));
}
None => assert_eq!(result.unwrap(), end + 2, "{text}"),
},
}
}
}
}
}