mod block;
mod block_scalar;
mod flow;
mod flow_block;
mod flow_node;
mod head;
mod polish;
mod read;
mod run;
mod scalar;
mod scan;
mod stream;
pub(crate) use flow::KEY_WINDOW;
use std::collections::{BTreeMap, VecDeque};
use oneyaml_core::code::{
DEPTH_LIMIT_EXCEEDED, DOCUMENT_TOO_LARGE, INTERNAL_ERROR, INVALID_COMMENT_CHARACTER,
INVALID_ESCAPE, MISPLACED_BYTE_ORDER_MARK, MISSING_MAPPING_COLON, SCALAR_TOO_LONG,
TAB_INDENTATION, TOO_MANY_DOCUMENTS, UNTERMINATED_FLOW_COLLECTION, UNTERMINATED_QUOTED_SCALAR,
};
use oneyaml_core::{Code, Diagnostic, Label, Settings, Span};
use crate::event::{Event, EventKind, EventList, NodeInfo, Properties, Sourced, TriviaKind};
pub(crate) use read::{
anchor_at, decoded_suffix, directive_at, directive_prefix, resolve_tag, scalar_value,
tag_source_at,
};
use scan::{break_len, byte, line_end, skip_white};
#[must_use]
pub fn parse(source: &str) -> EventList<'_> {
parse_with(source, &Settings::new())
}
#[must_use]
pub fn parse_with<'a>(source: &'a str, settings: &Settings) -> EventList<'a> {
let events = events_with(source, settings)
.map(Sourced::into_event)
.collect();
EventList::new(source, events)
}
#[must_use]
pub fn events(source: &str) -> Events<'_> {
events_with(source, &Settings::new())
}
#[must_use]
pub fn events_with<'a>(source: &'a str, settings: &Settings) -> Events<'a> {
Events {
parser: Parser::new(source, settings),
}
}
#[derive(Debug)]
pub struct Events<'a> {
parser: Parser<'a>,
}
impl<'a> Iterator for Events<'a> {
type Item = Sourced<'a>;
fn next(&mut self) -> Option<Sourced<'a>> {
let p = &mut self.parser;
if let Some(event) = p.out.pop(p.src) {
return Some(event);
}
p.fill();
p.out.pop(p.src)
}
}
impl core::iter::FusedIterator for Events<'_> {}
impl<'a> Events<'a> {
#[must_use]
pub const fn source(&self) -> &'a str {
self.parser.src
}
#[doc(hidden)]
#[must_use]
pub fn retained_capacity(&self) -> usize {
let p = &self.parser;
p.out
.q
.capacity()
.saturating_add(p.deferred.capacity())
.saturating_add(p.stack.capacity())
.saturating_add(p.flow_repair.capacity())
.saturating_add(p.scratch.capacity())
.saturating_add(p.flow.capacity())
.saturating_add(p.tags.len())
.saturating_add(p.pending_tags.len())
}
}
const BATCH: usize = 64;
#[derive(Clone, Debug)]
pub(super) enum Item<'a> {
Event(Event<'a>),
Trivia(usize, usize),
}
#[derive(Debug, Default)]
pub(super) struct Out<'a> {
q: VecDeque<Item<'a>>,
run: (usize, usize),
}
impl<'a> Out<'a> {
pub(super) fn event(&mut self, event: Event<'a>) {
self.q.push_back(Item::Event(event));
}
pub(super) fn trivia(&mut self, start: usize, end: usize) {
if start < end {
self.q.push_back(Item::Trivia(start, end));
}
}
pub(super) fn item(&mut self, item: Item<'a>) {
match item {
Item::Event(event) => self.event(event),
Item::Trivia(start, end) => self.trivia(start, end),
}
}
fn is_full(&self) -> bool {
self.q.len() >= BATCH
}
#[inline]
fn pop(&mut self, src: &'a str) -> Option<Sourced<'a>> {
let (from, to) = if self.run.0 < self.run.1 {
self.run
} else {
match self.q.pop_front()? {
Item::Event(event) => return Some(Sourced::new(event, src)),
Item::Trivia(from, to) => (from, to),
}
};
match scan::lex_trivia(src, from, to) {
Some((kind, stop)) => {
self.run = (stop, to);
let span = Span::new(from, stop);
Some(Sourced::new(Event::new(EventKind::Trivia(kind), span), src))
}
None => {
self.run = (to, to);
Some(Sourced::new(broken_trivia_run(from, to), src))
}
}
}
}
#[cold]
#[inline(never)]
fn broken_trivia_run<'a>(from: usize, to: usize) -> Event<'a> {
debug_assert!(false, "non-trivia byte in a trivia run at {from}");
let span = Span::new(from, to);
Event::new(
EventKind::Error(internal("non-trivia bytes in a trivia run", span)),
span,
)
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum MapPhase {
Key,
ExplicitKey,
AfterExplicitKey,
Value,
}
#[derive(Clone, Copy, Debug)]
enum Frame {
Document { root_done: bool },
Seq { indent: usize },
Map { indent: usize, phase: MapPhase },
}
#[derive(Clone, Copy, Debug)]
struct NodeCtx {
parent: Option<usize>,
compact: bool,
seq_at_parent: bool,
}
#[derive(Clone, Copy, Debug)]
enum State {
Stream,
Node(NodeCtx),
Next,
Flow,
Skip,
Done,
}
#[derive(Debug)]
struct Parser<'a> {
src: &'a str,
out: Out<'a>,
emit_pos: usize,
deferred: Vec<EventKind>,
pos: usize,
line_start: usize,
line_indent: usize,
fresh: bool,
tab_seen: bool,
stack: Vec<Frame>,
state: State,
props: Properties,
doc_start_deferred: bool,
directives_pending: bool,
yaml_seen: bool,
pending_tags: BTreeMap<&'a str, scan::TagPrefix>,
tags: BTreeMap<&'a str, scan::TagPrefix>,
doc_end_line: bool,
prefix_without_end: Option<usize>,
mark_before_error: Option<usize>,
blame: core::cell::Cell<Option<usize>>,
flow_repair: Vec<Owed>,
scratch: Vec<Event<'a>>,
flow: flow::FlowState<'a>,
max_depth: usize,
max_scalar_len: usize,
max_document_size: usize,
max_documents: usize,
lenient_inline_colons: bool,
honor_version_directive: bool,
documents: usize,
halted: bool,
last_quoted: (usize, usize),
}
#[derive(Clone, Debug)]
pub(super) enum Owed {
Kind(EventKind),
Empty(Properties),
}
pub(super) fn with_info(mut kind: EventKind, new: NodeInfo) -> EventKind {
if let EventKind::Scalar { info, .. }
| EventKind::MappingStart { info, .. }
| EventKind::SequenceStart { info, .. } = &mut kind
{
*info = new;
}
kind
}
pub(super) fn internal(what: &str, span: Span) -> Box<Diagnostic> {
Box::new(
Diagnostic::error(
INTERNAL_ERROR,
format!("internal error: {what}"),
Label::new(span, ""),
)
.with_help("this is a bug in oneyaml; please report it with this input"),
)
}
fn default_help(code: Code) -> Option<&'static str> {
Some(match code {
TAB_INDENTATION => {
"YAML indents with spaces only; replace the tabs used for indentation here with spaces"
}
MISSING_MAPPING_COLON => {
"each entry of a block mapping is written `key: value`, with a space after the `:`"
}
UNTERMINATED_QUOTED_SCALAR => {
"add the closing quote; inside '...' write '' for a literal ', inside \"...\" write \\\" for a literal \""
}
INVALID_ESCAPE => {
"in double quotes, `\\` starts an escape such as `\\n`, `\\t`, `\\\"` or `\\\\`; write `\\\\` for a literal backslash, or use single quotes, where `\\` has no special meaning"
}
UNTERMINATED_FLOW_COLLECTION => "close every `[` with `]` and every `{` with `}`",
_ => return None,
})
}
pub(super) fn misplaced_bom_diagnostic(start: usize, end: usize) -> Box<Diagnostic> {
Box::new(
Diagnostic::error(
MISPLACED_BYTE_ORDER_MARK,
"a byte order mark may appear only at the start of a document prefix",
Label::new(Span::new(start, end), ""),
)
.with_help(
"remove this byte order mark (U+FEFF); a mark is allowed only at the very start of the stream, or at the start of a line before a document",
),
)
}
#[inline(never)]
fn may_hold_unprintable(bytes: &[u8]) -> bool {
const ONES: u64 = 0x0101_0101_0101_0101;
const HIGH: u64 = 0x8080_8080_8080_8080;
let mut words = bytes.chunks_exact(8);
for chunk in words.by_ref() {
let Ok(chunk) = <[u8; 8]>::try_from(chunk) else {
return true;
};
let w = u64::from_le_bytes(chunk);
let del = w ^ (ONES * 0x7f);
let found = w | (w.wrapping_sub(ONES * 0x20) & !w) | (del.wrapping_sub(ONES) & !del);
if found & HIGH != 0 {
return true;
}
}
words.remainder().iter().any(|b| *b < 0x20 || *b >= 0x7f)
}
#[inline(never)]
pub(super) fn comment_char_diagnostic(
src: &str,
start: usize,
end: usize,
) -> Option<Box<Diagnostic>> {
let text = src.get(start..end)?;
if !may_hold_unprintable(text.as_bytes()) {
return None;
}
let (k, c) = text.char_indices().find(|(_, c)| !scan::is_printable(*c))?;
let at = start.saturating_add(k);
Some(Box::new(
Diagnostic::error(
INVALID_COMMENT_CHARACTER,
"a comment may hold only printable characters",
Label::new(Span::new(at, at.saturating_add(c.len_utf8())), ""),
)
.with_help("remove this character; control characters (U+0000 to U+001F except tab, U+007F, and U+0080 to U+009F except U+0085) cannot appear in a comment"),
))
}
fn diagnostic(code: Code, message: &str, span: Span) -> Box<Diagnostic> {
Box::new(Diagnostic::error(code, message, Label::new(span, "")))
}
impl<'a> Parser<'a> {
fn new(src: &'a str, settings: &Settings) -> Self {
let limits = settings.get_limits();
let mut p = Self {
src,
out: Out::default(),
emit_pos: 0,
deferred: Vec::new(),
pos: 0,
line_start: 0,
line_indent: 0,
fresh: true,
tab_seen: false,
stack: Vec::new(),
state: State::Stream,
props: Properties::none(),
doc_start_deferred: false,
directives_pending: false,
yaml_seen: false,
pending_tags: BTreeMap::new(),
tags: BTreeMap::new(),
doc_end_line: false,
prefix_without_end: None,
mark_before_error: None,
blame: core::cell::Cell::new(None),
flow_repair: Vec::new(),
scratch: Vec::new(),
flow: flow::FlowState::default(),
max_depth: limits.get_max_depth(),
max_scalar_len: limits.get_max_scalar_len(),
max_document_size: limits.get_max_document_size(),
max_documents: limits.get_max_documents(),
lenient_inline_colons: settings.get_lenient_inline_colons(),
honor_version_directive: settings.get_honor_version_directive(),
documents: 0,
halted: false,
last_quoted: (0, 0),
};
p.push(EventKind::StreamStart, 0, 0);
if src.len() > p.max_document_size {
p.halt(DOCUMENT_TOO_LARGE, "the input is too large");
}
p
}
#[inline(never)]
fn fill(&mut self) {
while !self.out.is_full() && !matches!(self.state, State::Done) {
self.step();
}
}
fn step(&mut self) {
match self.state {
State::Stream => self.stream(),
State::Node(ctx) => self.node(ctx),
State::Next => self.next(),
State::Flow => self.flow_step(),
State::Skip => self.skip(),
State::Done => {}
}
}
fn push(&mut self, kind: EventKind, start: usize, end: usize) {
self.push_event(Event::new(kind, Span::new(start, end)));
}
fn push_event(&mut self, event: Event<'a>) {
self.emit_pos = event.span().end;
self.out.event(event);
}
fn zero(&mut self, kind: EventKind) {
self.materialize();
let at = self.emit_pos;
self.push(kind, at, at);
}
fn zero_node(&mut self, kind: EventKind, props: Properties) {
let info = NodeInfo::new(self.emit_pos, props, None);
self.zero(with_info(kind, info));
}
fn defer(&mut self, kind: EventKind) {
self.deferred.push(kind);
}
fn materialize(&mut self) {
if self.deferred.is_empty() {
return;
}
let at = self.emit_pos;
for kind in self.deferred.drain(..) {
self.out.event(Event::new(kind, Span::empty(at)));
}
}
fn flush(&mut self) {
self.materialize();
self.out.trivia(self.emit_pos, self.pos);
self.emit_pos = self.pos;
}
fn begin_content(&mut self) {
self.flush();
if self.doc_start_deferred {
self.doc_start_deferred = false;
self.zero(EventKind::document_start(false));
}
}
fn token(&mut self, kind: EventKind, end: usize) {
let start = self.pos;
self.push(kind, start, end);
self.pos = end;
self.fresh = false;
self.tab_seen = false;
}
fn take_scratch(&mut self) -> Vec<Event<'a>> {
let mut events = core::mem::take(&mut self.scratch);
events.clear();
events
}
fn commit_scratch(&mut self, mut events: Vec<Event<'a>>) {
self.commit(events.drain(..));
self.scratch = events;
}
fn empty(&mut self) {
let props = core::mem::take(&mut self.props);
if props.is_empty() {
self.defer(EventKind::plain());
} else {
self.zero_node(EventKind::plain(), props);
}
}
fn col(&self) -> usize {
self.pos.saturating_sub(self.line_start)
}
fn block_depth(&self) -> usize {
self.stack.len().saturating_sub(1)
}
fn depth_ok(&self, depth: usize) -> bool {
depth <= self.max_depth
}
fn scalar_len_ok(&self, len: usize) -> bool {
len <= self.max_scalar_len
}
fn limit_help(&self, code: Code) -> Option<String> {
let (setting, value) = match code {
DEPTH_LIMIT_EXCEEDED => ("max_depth", self.max_depth),
SCALAR_TOO_LONG => ("max_scalar_len", self.max_scalar_len),
DOCUMENT_TOO_LARGE => ("max_document_size", self.max_document_size),
TOO_MANY_DOCUMENTS => ("max_documents", self.max_documents),
_ => return None,
};
Some(format!("raise Limits::{setting} (currently {value})"))
}
fn halt(&mut self, code: Code, message: &str) {
self.fail(code, message, false);
self.halted = true;
}
fn comment_at(&self, i: usize) -> bool {
scan::comment_at(self.src, i)
}
fn scan_trivia(&mut self, bom: bool) {
loop {
let i = self.pos;
let kind_end = match byte(self.src, i) {
Some(b' ' | b'\t') => {
let spaces = self
.src
.as_bytes()
.get(i..)
.map_or(0, |r| r.iter().take_while(|b| **b == b' ').count());
let mut end = i.saturating_add(spaces);
if byte(self.src, end) == Some(b'\t') {
self.tab_seen = true;
end = skip_white(self.src, end);
}
if i == self.line_start.saturating_add(self.line_indent) {
self.line_indent = self.line_indent.saturating_add(spaces);
}
(TriviaKind::Whitespace, end)
}
Some(b'\n' | b'\r') => {
let end = i.saturating_add(break_len(self.src, i));
self.line_start = end;
self.line_indent = 0;
self.fresh = true;
self.tab_seen = false;
(TriviaKind::LineBreak, end)
}
Some(b'#') if self.comment_at(i) => {
let (end, clean) = scan::comment_extent(self.src, i);
self.pos = end;
if !clean {
let bad = comment_char_diagnostic(self.src, i, end);
self.marks_in_token(i, end, bad);
}
continue;
}
_ if !bom && self.prefix_mark_at(i) => break,
_ if scan::mark_at(self.src, i) => {
let end = i.saturating_add('\u{feff}'.len_utf8());
let prefix_start = bom
&& self.fresh
&& i == self.line_start
&& self.line_indent == 0
&& !self.directives_pending;
if !prefix_start {
self.misplaced_bom(i, end);
continue;
}
self.line_start = end;
self.line_indent = 0;
(TriviaKind::ByteOrderMark, end)
}
_ => break,
};
let (_, end) = kind_end;
self.pos = end;
}
}
pub(super) fn prefix_mark_at(&self, i: usize) -> bool {
self.fresh
&& i == self.line_start
&& self.line_indent == 0
&& !self.stack.is_empty()
&& scan::mark_at(self.src, i)
}
pub(super) fn marks_in_token(
&mut self,
start: usize,
end: usize,
bad: Option<Box<Diagnostic>>,
) {
let text = self.src.get(start..end).unwrap_or_default();
if bad.is_none() && !text.contains('\u{feff}') {
return;
}
self.flush();
let mut bad = bad;
for (k, _) in text.match_indices('\u{feff}') {
let at = start.saturating_add(k);
if bad.as_ref().is_some_and(|d| d.primary.span.start < at) {
self.comment_error(bad.take());
}
let diag = misplaced_bom_diagnostic(at, at.saturating_add('\u{feff}'.len_utf8()));
let here = self.emit_pos;
self.push(EventKind::Error(diag), here, here);
}
self.comment_error(bad);
}
fn comment_error(&mut self, bad: Option<Box<Diagnostic>>) {
if let Some(diag) = bad {
let here = self.emit_pos;
self.push(EventKind::Error(diag), here, here);
}
}
fn misplaced_bom(&mut self, start: usize, end: usize) {
self.flush();
self.push(
EventKind::Error(misplaced_bom_diagnostic(start, end)),
start,
end,
);
self.pos = end;
self.line_start = self
.line_start
.saturating_add(end.saturating_sub(start))
.min(end);
}
fn child_done(&mut self) {
match self.stack.last_mut() {
Some(Frame::Document { root_done }) => *root_done = true,
Some(Frame::Map { phase, .. }) => {
*phase = match *phase {
MapPhase::ExplicitKey => MapPhase::AfterExplicitKey,
MapPhase::AfterExplicitKey | MapPhase::Value | MapPhase::Key => MapPhase::Key,
};
}
Some(Frame::Seq { .. }) | None => {}
}
self.state = State::Next;
}
fn close_block(&mut self, certain: bool) {
let end = match self.stack.pop() {
Some(Frame::Map { .. }) => EventKind::MappingEnd,
Some(Frame::Seq { .. }) => EventKind::SequenceEnd,
Some(frame @ Frame::Document { .. }) => {
self.stack.push(frame);
self.child_done();
return;
}
None => {
self.child_done();
return;
}
};
if certain {
self.zero(end);
} else {
self.defer(end);
}
self.child_done();
}
fn fail(&mut self, code: Code, message: &str, slot_open: bool) {
self.fail_with(code, message, slot_open, |d| d);
}
fn fail_with(
&mut self,
code: Code,
message: &str,
slot_open: bool,
refine: impl FnOnce(Diagnostic) -> Diagnostic,
) {
let mark = self.mark_before_error.take();
let blame = self.blame.take();
if matches!(self.state, State::Skip) {
self.flush();
if self.emit_pos != self.pos || !self.deferred.is_empty() {
debug_assert!(false, "flush left owed events or pending trivia");
self.internal_error("`flush` left owed events or pending trivia");
}
return;
}
let deferred = core::mem::take(&mut self.deferred);
self.flush();
self.deferred = deferred;
let start = self.pos;
let mark = mark.or_else(|| {
let about_syntax = code.get() < 1000;
let text = self.src.get(start..line_end(self.src, start))?;
let unquoted = text.find(['\'', '"']).unwrap_or(text.len());
let k = text.get(..unquoted)?.find('\u{feff}')?;
about_syntax.then_some(start.saturating_add(k))
});
let mark_diag =
|m: usize| misplaced_bom_diagnostic(m, m.saturating_add('\u{feff}'.len_utf8()));
if mark.is_some_and(|m| m < start) {
debug_assert!(false, "a byte order mark before the error's start");
self.internal_error("a byte order mark before the error's start");
}
let at_marker = start == self.line_start
&& (scan::any_marker_at(self.src, start) || self.prefix_mark_at(start));
let end = if at_marker {
start
} else {
line_end(self.src, start)
};
let blame = blame.or_else(|| scalar::quoted_fault(self.src, start, code));
let at = blame.filter(|b| *b >= start).unwrap_or(start);
let at = mark.filter(|m| *m >= start).map_or(at, |m| at.min(m));
let mut diag = Diagnostic::error(code, message, Label::new(Span::new(at, end.max(at)), ""));
if let Some(help) = self.limit_help(code) {
diag = diag.with_help(help);
} else if let Some(help) = default_help(code) {
diag = diag.with_help(help);
}
let diag = refine(diag);
self.push(EventKind::Error(Box::new(diag)), start, end);
self.pos = end;
if let Some(m) = mark.filter(|m| *m >= start) {
self.push(EventKind::Error(mark_diag(m)), end, end);
}
let mut repairs = core::mem::take(&mut self.flow_repair);
for owed in repairs.drain(..) {
match owed {
Owed::Kind(kind) => self.zero(kind),
Owed::Empty(props) => self.zero_node(EventKind::plain(), props),
}
}
self.flow_repair = repairs;
self.repair(slot_open);
self.materialize();
self.state = State::Skip;
}
pub(super) fn mark_then_fail(
&mut self,
mark: Option<usize>,
code: Code,
message: &str,
slot_open: bool,
) {
self.mark_before_error = mark;
self.fail(code, message, slot_open);
}
fn fail_internal(&mut self, what: &str, slot_open: bool) {
let message = format!("internal error: {what}");
self.fail_with(INTERNAL_ERROR, &message, slot_open, |d| {
d.with_help("this is a bug in oneyaml; please report it with this input")
});
}
fn internal_error(&mut self, what: &str) {
self.materialize();
let at = self.emit_pos;
self.push(EventKind::Error(internal(what, Span::empty(at))), at, at);
if at < self.pos {
let end = self.pos;
self.push(EventKind::Trivia(TriviaKind::Skipped), at, end);
}
}
fn soft_error(&mut self, code: Code, message: &str) {
let at = self.emit_pos;
self.soft_error_at(code, message, at);
}
fn soft_error_at(&mut self, code: Code, message: &str, at: usize) {
self.zero(EventKind::Error(diagnostic(code, message, Span::empty(at))));
}
fn repair(&mut self, slot_open: bool) {
self.directives_pending = false;
self.pending_tags.clear();
self.yaml_seen = false;
self.prefix_without_end = None;
if self.doc_start_deferred {
self.doc_start_deferred = false;
self.deferred.clear();
self.props = Properties::none();
self.stack.clear();
return;
}
if slot_open || !self.props.is_empty() {
self.empty();
self.child_done();
}
loop {
match self.stack.last().copied() {
Some(Frame::Map { phase, .. }) if phase != MapPhase::Key => {
self.empty();
self.child_done();
}
Some(Frame::Map { .. } | Frame::Seq { .. }) => self.close_block(false),
Some(Frame::Document { root_done }) => {
if !root_done {
self.empty();
self.child_done();
}
break;
}
None => break,
}
}
}
fn skip(&mut self) {
let i = self.pos;
let blen = break_len(self.src, i);
if blen > 0 {
let end = i.saturating_add(blen);
self.push(EventKind::Trivia(TriviaKind::LineBreak), i, end);
self.pos = end;
self.line_start = end;
self.line_indent = 0;
return;
}
let resync = i >= self.src.len()
|| !self.halted
&& i == self.line_start
&& (scan::any_marker_at(self.src, i) || scan::mark_at(self.src, i));
if !resync {
let end = line_end(self.src, i);
self.push(EventKind::Trivia(TriviaKind::Skipped), i, end);
self.pos = end;
return;
}
self.fresh = true;
self.line_indent = 0;
self.tab_seen = false;
self.state = if self.stack.is_empty() {
State::Stream
} else {
State::Next
};
}
}
#[cfg(test)]
mod equivalence_tests;
#[cfg(test)]
mod tests;