mod arena;
mod attach;
mod build;
mod check;
mod cost;
#[cfg(feature = "__internal-checks")]
#[doc(hidden)]
pub fn take_work() -> u64 {
cost::take_total()
}
mod edit;
mod facts;
mod fragment;
mod kind;
mod line;
mod node;
mod runs;
mod seq;
mod slab;
mod stored;
mod validate;
use std::borrow::Cow;
use std::collections::BTreeMap;
use std::sync::atomic::{AtomicU64, Ordering};
use oneyaml_core::{Diagnostic, Settings, Span};
use crate::event::{BlockHeader, Event, Sourced};
pub use attach::{AttachRule, Attachment, CommentOwner};
pub use check::{TreeMismatch, check_tree, compare_trees};
pub use edit::{GroupMark, Inserted, Replaced, TreeEditError};
pub use fragment::Fragment;
pub use kind::SyntaxKind;
pub use node::{Ancestors, Children, Descendants, Node, Walk, WalkEvent};
use build::{Builder, Origin};
use stored::Stored;
const NONE: u32 = u32::MAX;
const WRAP: u64 = 0x1_0000_0000;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct Extra {
tag_prefix: Option<usize>,
block: Option<BlockHeader>,
}
static NEXT_STAMP: AtomicU64 = AtomicU64::new(1);
fn new_stamp() -> u64 {
let mut current = NEXT_STAMP.load(Ordering::Relaxed);
loop {
let Some(next) = current.checked_add(1) else {
return EXHAUSTED;
};
match NEXT_STAMP.compare_exchange_weak(current, next, Ordering::Relaxed, Ordering::Relaxed)
{
Ok(previous) => return previous,
Err(actual) => current = actual,
}
}
}
const EXHAUSTED: u64 = 0;
pub struct SyntaxTree {
source: String,
kinds: Vec<SyntaxKind>,
parents: Vec<u32>,
words: Vec<u32>,
wraps: Vec<u32>,
extras: Vec<(u32, Extra)>,
diagnostics: Vec<(u32, Stored)>,
documents: usize,
suppressed: usize,
errors: usize,
generations: BTreeMap<u32, u32>,
stamp: u64,
ancestry: Vec<(u64, u32)>,
slot_floor: u32,
facts: facts::StreamFacts,
run_facts: runs::RunFacts,
settings: Settings,
edits: Option<Box<edit::Edits>>,
group: edit::Group,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct NodeId {
tree: u64,
index: u32,
generation: u32,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct StaleNode {
pub id: NodeId,
}
impl core::fmt::Display for StaleNode {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.write_str("stale node handle: the element no longer exists in this tree")
}
}
impl std::error::Error for StaleNode {}
impl SyntaxTree {
#[must_use]
pub fn parse(source: impl Into<String>) -> Self {
Self::parse_with(source, &Settings::new())
}
#[must_use]
pub fn parse_with(source: impl Into<String>, settings: &Settings) -> Self {
let source = source.into();
let parts = {
let mut builder = Builder::new(source.len(), Origin::Parser)
.max_diagnostics(settings.get_limits().get_max_diagnostics());
for event in crate::parser::events_with(&source, settings) {
builder.push(event.into_event());
}
builder.finish()
};
Self::from_parts(source, parts, settings.clone())
}
#[must_use]
pub fn from_events<'a, E, I>(events: I) -> Self
where
E: core::borrow::Borrow<Event<'a>>,
I: IntoIterator<Item = Sourced<'a, E>>,
{
let mut events = events.into_iter().peekable();
let source = events.peek().map_or("", Sourced::source);
let mut builder = Builder::new(source.len(), Origin::Caller);
for event in events {
builder.push(event.event().clone());
}
let parts = builder.finish();
Self::from_parts(source.to_owned(), parts, Settings::new())
}
fn from_parts(source: String, parts: build::Parts, settings: Settings) -> Self {
let errors = parts
.diagnostics
.iter()
.filter(|(_, d)| d.is_error())
.count();
let mut tree = Self {
source,
kinds: parts.kinds,
parents: parts.parents,
words: parts.words,
wraps: parts.wraps,
extras: parts.extras,
diagnostics: parts.diagnostics,
documents: parts.documents,
suppressed: parts.suppressed,
errors,
generations: BTreeMap::new(),
stamp: new_stamp(),
ancestry: Vec::new(),
slot_floor: 0,
facts: facts::StreamFacts::default(),
run_facts: runs::RunFacts::default(),
settings,
edits: None,
group: edit::Group::default(),
};
let flat = tree.base_flat();
let mut child = flat.first_child(0);
let children = core::iter::from_fn(move || {
let c = child?;
child = flat.next_sibling(c);
Some(c)
});
tree.facts = facts::StreamFacts::of(flat, children, tree.errors > 0);
tree.run_facts = runs::RunFacts::of(tree.base_flat());
tree
}
#[must_use]
pub fn settings(&self) -> &Settings {
&self.settings
}
#[must_use]
pub fn source(&self) -> &str {
&self.source
}
#[must_use]
pub fn root(&self) -> Node<'_> {
Node::new(self, 0)
}
#[must_use]
pub fn len(&self) -> usize {
if self.edits.is_some() {
return usize::try_from(self.nav_total().0).unwrap_or(usize::MAX);
}
self.kinds.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn get(&self, id: NodeId) -> Result<Node<'_>, StaleNode> {
let named = id.tree == self.owner(id.index)
&& id.tree != EXHAUSTED
&& self.stamp != EXHAUSTED
&& self.generation(id.index) == id.generation;
let hint = if !named {
None
} else if self.edits.is_some() {
self.run_item(id.index).map(|(item, _, _)| item)
} else {
self.is_live(id.index).then_some(NONE)
};
match hint {
Some(h) => Ok(Node::hinted(self, id.index, h)),
None => Err(StaleNode { id }),
}
}
#[must_use]
pub fn node_at_slot(&self, slot: u32) -> Option<Node<'_>> {
if slot == NONE {
return None;
}
if self.edits.is_some() {
return self
.run_item(slot)
.map(|(item, _, _)| Node::hinted(self, slot, item));
}
self.is_live(slot).then(|| Node::new(self, slot))
}
pub fn diagnostics(&self) -> impl ExactSizeIterator<Item = Cow<'_, Diagnostic>> + '_ {
self.diagnostics_by_element().map(|(_, d)| d)
}
#[must_use]
pub const fn suppressed_diagnostics(&self) -> usize {
self.suppressed
}
#[must_use]
pub fn is_skeleton(d: &Diagnostic) -> bool {
d.message.is_empty()
}
fn diag_node(&self, i: u32) -> Option<Node<'_>> {
let live = if self.edits.is_some() {
i != NONE
} else {
(i as usize) < self.kinds.len()
};
live.then(|| Node::new(self, i))
}
pub fn diagnostics_by_element(
&self,
) -> impl ExactSizeIterator<Item = (Option<Node<'_>>, Cow<'_, Diagnostic>)> + '_ {
let source = match self.edits.as_deref() {
Some(e) => DiagSource::Built(self.edited_diagnostics(e, None).into_iter()),
None => DiagSource::Parsed(self.diagnostics.iter()),
};
DiagIter {
tree: self,
source,
fill: &[],
}
}
pub fn diagnostics_within<'s>(
&'s self,
node: Node<'s>,
) -> impl ExactSizeIterator<Item = (Option<Node<'s>>, Cow<'s, Diagnostic>)> + 's {
self.diagnostics_within_iter(node)
}
fn diagnostics_within_iter<'s>(&'s self, node: Node<'s>) -> DiagIter<'s> {
let source = match self.edits.as_deref() {
Some(e) => DiagSource::Built(self.edited_diagnostics(e, Some(node.slot())).into_iter()),
None => {
let first = node.preorder_index();
let past = self.end_of(first);
let lo = self
.diagnostics
.partition_point(|(n, _)| (*n as usize) < first);
let hi = self
.diagnostics
.partition_point(|(n, _)| (*n as usize) < past)
.max(lo);
DiagSource::Parsed(self.diagnostics.get(lo..hi).unwrap_or_default().iter())
}
};
DiagIter {
tree: self,
source,
fill: &[],
}
}
pub fn diagnostics_within_filled<'s>(
&'s self,
node: Node<'s>,
fill: &'s [Diagnostic],
) -> impl ExactSizeIterator<Item = (Option<Node<'s>>, Cow<'s, Diagnostic>)> + 's {
DiagIter {
fill,
..self.diagnostics_within_iter(node)
}
}
#[must_use]
pub fn has_errors(&self) -> bool {
self.errors > 0
}
#[must_use]
pub fn fork(&self) -> Self {
let mut copy = self.clone();
let mut lo = 0u32;
for &(stamp, limit) in &self.ancestry {
if self.holds_live(lo, limit) {
copy.ancestry.push((stamp, limit));
}
lo = limit;
}
let limit = self.next_slot();
if self.holds_live(lo, limit) {
copy.ancestry.push((self.stamp, limit));
}
copy
}
#[must_use]
pub fn emit(&self) -> String {
if let Some(e) = self.edits.as_deref() {
return self.edited_emit(e);
}
let mut out = String::with_capacity(self.source.len());
for node in self.root().descendants() {
if node.is_token() {
out.push_str(&node.text());
}
}
out
}
fn generation(&self, index: u32) -> u32 {
self.generations.get(&index).copied().unwrap_or(0)
}
#[inline]
fn kind_at(&self, i: usize) -> Option<SyntaxKind> {
self.kinds.get(i).copied()
}
#[inline]
fn parent_of(&self, i: usize) -> Option<usize> {
match self.parents.get(i) {
Some(&p) if p != NONE => Some(p as usize),
_ => None,
}
}
#[inline]
fn end_of(&self, i: usize) -> usize {
match self.kind_at(i) {
Some(k) if !k.is_token() => self.words.get(i).map_or(i, |w| *w as usize),
_ => i.saturating_add(1),
}
}
fn token_start(&self, i: usize) -> usize {
let low = u64::from(self.words.get(i).copied().unwrap_or(0));
if self.wraps.is_empty() {
return usize::try_from(low).unwrap_or(usize::MAX);
}
let crossings = self.wraps.partition_point(|w| *w as usize <= i);
let high = u64::try_from(crossings)
.ok()
.and_then(|c| c.checked_mul(WRAP));
high.and_then(|h| h.checked_add(low))
.and_then(|at| usize::try_from(at).ok())
.unwrap_or(usize::MAX)
}
fn start_of(&self, mut i: usize) -> usize {
loop {
match self.kind_at(i) {
None => return self.source.len(),
Some(k) if k.is_token() => return self.token_start(i),
Some(_) => i = i.saturating_add(1),
}
}
}
fn span_of(&self, i: usize) -> Span {
let start = self.start_of(i);
let end = self.start_of(self.end_of(i)).max(start);
Span::new(start, end)
}
fn extra(&self, i: usize) -> Option<&Extra> {
let at = self
.extras
.binary_search_by_key(&i, |(n, _)| *n as usize)
.ok()?;
self.extras.get(at).map(|(_, e)| e)
}
fn diagnostic_at(&self, i: usize) -> Option<Cow<'_, Diagnostic>> {
if self.edits.is_some() {
let slot = u32::try_from(i).ok()?;
return pick_error(self.diagnostics_of(slot).into_iter());
}
let first = self.diagnostics.partition_point(|(n, _)| (*n as usize) < i);
let at_i = self
.diagnostics
.get(first..)
.unwrap_or_default()
.iter()
.take_while(|(n, _)| *n as usize == i)
.map(|(_, d)| d.view());
pick_error(at_i)
}
fn id_of(&self, index: u32) -> NodeId {
NodeId {
tree: self.owner(index),
index,
generation: self.generation(index),
}
}
fn owner(&self, index: u32) -> u64 {
let k = self.ancestry.partition_point(|(_, l)| *l <= index);
self.ancestry.get(k).map_or(self.stamp, |(s, _)| *s)
}
fn holds_live(&self, lo: u32, hi: u32) -> bool {
if lo >= hi {
return false;
}
let Some(e) = self.edits.as_deref() else {
return (lo as usize) < self.kinds.len();
};
e.live_in(lo, hi)
}
fn next_slot(&self) -> u32 {
match self.edits.as_deref() {
Some(e) => e.next_slot(),
None => u32::try_from(self.kinds.len())
.unwrap_or(NONE)
.max(self.slot_floor),
}
}
}
enum DiagSource<'t> {
Parsed(core::slice::Iter<'t, (u32, Stored)>),
Built(std::vec::IntoIter<(u32, Stored)>),
}
struct DiagIter<'t> {
tree: &'t SyntaxTree,
source: DiagSource<'t>,
fill: &'t [Diagnostic],
}
impl<'t> DiagIter<'t> {
fn seen(&self, d: &Stored) -> Cow<'t, Diagnostic> {
if !self.fill.is_empty() && !matches!(d, Stored::Full(_)) {
let at = d.span().start;
let lo = self.fill.partition_point(|c| c.primary.span.start < at);
let found = self
.fill
.get(lo..)
.unwrap_or_default()
.iter()
.take_while(|c| c.primary.span.start == at)
.find(|c| stored::records(d, c));
if let Some(c) = found {
return Cow::Borrowed(c);
}
}
Cow::Owned(d.view().into_owned())
}
}
impl<'t> Iterator for DiagIter<'t> {
type Item = (Option<Node<'t>>, Cow<'t, Diagnostic>);
fn next(&mut self) -> Option<Self::Item> {
match &mut self.source {
DiagSource::Parsed(it) => {
let (i, d) = it.next()?;
let seen = if self.fill.is_empty() || matches!(d, Stored::Full(_)) {
d.view()
} else {
self.seen(d)
};
Some((self.tree.diag_node(*i), seen))
}
DiagSource::Built(it) => {
let (i, d) = it.next()?;
let seen = if self.fill.is_empty() || matches!(d, Stored::Full(_)) {
Cow::Owned(d.view().into_owned())
} else {
self.seen(&d)
};
Some((self.tree.diag_node(i), seen))
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
match &self.source {
DiagSource::Parsed(it) => it.size_hint(),
DiagSource::Built(it) => it.size_hint(),
}
}
}
impl ExactSizeIterator for DiagIter<'_> {}
fn pick_error<'a>(at_i: impl Iterator<Item = Cow<'a, Diagnostic>>) -> Option<Cow<'a, Diagnostic>> {
let mut fallback = None;
for d in at_i {
if d.severity == oneyaml_core::Severity::Error {
return Some(d);
}
fallback = fallback.or(Some(d));
}
fallback
}
impl Clone for SyntaxTree {
fn clone(&self) -> Self {
let mut copy = Self {
source: self.source.clone(),
kinds: self.kinds.clone(),
parents: self.parents.clone(),
words: self.words.clone(),
wraps: self.wraps.clone(),
extras: self.extras.clone(),
diagnostics: self.diagnostics.clone(),
documents: self.documents,
suppressed: self.suppressed,
errors: self.errors,
generations: self.generations.clone(),
stamp: new_stamp(),
ancestry: Vec::new(),
facts: self.facts.clone(),
run_facts: self.run_facts.clone(),
settings: self.settings.clone(),
slot_floor: self.slot_floor,
edits: self.edits.clone(),
group: edit::Group::default(),
};
self.settle_group_copy(&mut copy);
copy
}
}
impl PartialEq for SyntaxTree {
fn eq(&self, other: &Self) -> bool {
let raw = self.edits.is_none()
&& other.edits.is_none()
&& self.source == other.source
&& self.kinds == other.kinds
&& self.parents == other.parents
&& self.words == other.words
&& self.wraps == other.wraps
&& self.extras == other.extras
&& self.diagnostics == other.diagnostics;
raw || compare_trees(self, other).is_ok()
}
}
impl Eq for SyntaxTree {}
impl core::hash::Hash for SyntaxTree {
fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
check::for_each_item(self, |item| item.hash(state));
}
}
impl core::fmt::Debug for SyntaxTree {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
writeln!(f, "SyntaxTree ({} elements)", self.len())?;
let mut depth = 0usize;
for event in self.root().walk() {
match event {
WalkEvent::Enter(node) => {
let span = node.span();
write!(f, "{depth} {:?}@{}..{}", node.kind(), span.start, span.end)?;
if node.is_token() && span.len() <= 40 {
write!(f, " {:?}", node.text())?;
}
f.write_str("\n")?;
depth = depth.saturating_add(1);
}
WalkEvent::Leave(_) => depth = depth.saturating_sub(1),
}
}
for d in self.diagnostics() {
writeln!(f, "{d}")?;
}
Ok(())
}
}
#[cfg(test)]
mod tests;
#[cfg(test)]
mod read_tests;