diff options
Diffstat (limited to 'src/syntax')
| -rw-r--r-- | src/syntax/ast.rs | 153 | ||||
| -rw-r--r-- | src/syntax/highlight.rs | 56 | ||||
| -rw-r--r-- | src/syntax/mod.rs | 725 | ||||
| -rw-r--r-- | src/syntax/span.rs | 162 |
4 files changed, 558 insertions, 538 deletions
diff --git a/src/syntax/ast.rs b/src/syntax/ast.rs index 0f575f31..99c6b39f 100644 --- a/src/syntax/ast.rs +++ b/src/syntax/ast.rs @@ -1,25 +1,25 @@ -//! A typed layer over the red-green tree. +//! A typed layer over the untyped syntax tree. //! //! The AST is rooted in the [`Markup`] node. use std::num::NonZeroUsize; use std::ops::Deref; -use super::{Green, GreenData, NodeKind, RedNode, RedRef, Span, Spanned}; +use super::{NodeData, NodeKind, Span, Spanned, SyntaxNode}; use crate::geom::{AngleUnit, LengthUnit}; use crate::util::EcoString; /// A typed AST node. pub trait TypedNode: Sized { - /// Convert from a red node to a typed node. - fn from_red(value: RedRef) -> Option<Self>; + /// Convert a node into its typed variant. + fn from_untyped(node: &SyntaxNode) -> Option<Self>; - /// A reference to the underlying red node. - fn as_red(&self) -> RedRef<'_>; + /// A reference to the underlying syntax node. + fn as_untyped(&self) -> &SyntaxNode; /// The source code location. fn span(&self) -> Span { - self.as_red().span() + self.as_untyped().span() } } @@ -34,19 +34,19 @@ macro_rules! node { #[derive(Debug, Clone, PartialEq, Hash)] #[repr(transparent)] $(#[$attr])* - pub struct $name(RedNode); + pub struct $name(SyntaxNode); impl TypedNode for $name { - fn from_red(node: RedRef) -> Option<Self> { + fn from_untyped(node: &SyntaxNode) -> Option<Self> { if matches!(node.kind(), $variants) { - Some(Self(node.own())) + Some(Self(node.clone())) } else { None } } - fn as_red(&self) -> RedRef<'_> { - self.0.as_ref() + fn as_untyped(&self) -> &SyntaxNode { + &self.0 } } }; @@ -77,7 +77,10 @@ impl Markup { NodeKind::Strong => node.cast().map(MarkupNode::Strong), NodeKind::Emph => node.cast().map(MarkupNode::Emph), NodeKind::Raw(raw) => Some(MarkupNode::Raw(raw.as_ref().clone())), - NodeKind::Math(math) => Some(MarkupNode::Math(Spanned::new(math.as_ref().clone(), node.span()))), + NodeKind::Math(math) => Some(MarkupNode::Math(Spanned::new( + math.as_ref().clone(), + node.span(), + ))), NodeKind::Heading => node.cast().map(MarkupNode::Heading), NodeKind::List => node.cast().map(MarkupNode::List), NodeKind::Enum => node.cast().map(MarkupNode::Enum), @@ -279,7 +282,7 @@ pub enum Expr { } impl TypedNode for Expr { - fn from_red(node: RedRef) -> Option<Self> { + fn from_untyped(node: &SyntaxNode) -> Option<Self> { match node.kind() { NodeKind::Ident(_) => node.cast().map(Self::Ident), NodeKind::CodeBlock => node.cast().map(Self::Code), @@ -309,33 +312,33 @@ impl TypedNode for Expr { } } - fn as_red(&self) -> RedRef<'_> { + fn as_untyped(&self) -> &SyntaxNode { match self { - Self::Lit(v) => v.as_red(), - Self::Code(v) => v.as_red(), - Self::Content(v) => v.as_red(), - Self::Ident(v) => v.as_red(), - Self::Array(v) => v.as_red(), - Self::Dict(v) => v.as_red(), - Self::Group(v) => v.as_red(), - Self::Unary(v) => v.as_red(), - Self::Binary(v) => v.as_red(), - Self::FieldAccess(v) => v.as_red(), - Self::FuncCall(v) => v.as_red(), - Self::MethodCall(v) => v.as_red(), - Self::Closure(v) => v.as_red(), - Self::Let(v) => v.as_red(), - Self::Set(v) => v.as_red(), - Self::Show(v) => v.as_red(), - Self::Wrap(v) => v.as_red(), - Self::If(v) => v.as_red(), - Self::While(v) => v.as_red(), - Self::For(v) => v.as_red(), - Self::Import(v) => v.as_red(), - Self::Include(v) => v.as_red(), - Self::Break(v) => v.as_red(), - Self::Continue(v) => v.as_red(), - Self::Return(v) => v.as_red(), + Self::Lit(v) => v.as_untyped(), + Self::Code(v) => v.as_untyped(), + Self::Content(v) => v.as_untyped(), + Self::Ident(v) => v.as_untyped(), + Self::Array(v) => v.as_untyped(), + Self::Dict(v) => v.as_untyped(), + Self::Group(v) => v.as_untyped(), + Self::Unary(v) => v.as_untyped(), + Self::Binary(v) => v.as_untyped(), + Self::FieldAccess(v) => v.as_untyped(), + Self::FuncCall(v) => v.as_untyped(), + Self::MethodCall(v) => v.as_untyped(), + Self::Closure(v) => v.as_untyped(), + Self::Let(v) => v.as_untyped(), + Self::Set(v) => v.as_untyped(), + Self::Show(v) => v.as_untyped(), + Self::Wrap(v) => v.as_untyped(), + Self::If(v) => v.as_untyped(), + Self::While(v) => v.as_untyped(), + Self::For(v) => v.as_untyped(), + Self::Import(v) => v.as_untyped(), + Self::Include(v) => v.as_untyped(), + Self::Break(v) => v.as_untyped(), + Self::Continue(v) => v.as_untyped(), + Self::Return(v) => v.as_untyped(), } } } @@ -429,7 +432,7 @@ node! { impl CodeBlock { /// The list of expressions contained in the block. pub fn exprs(&self) -> impl Iterator<Item = Expr> + '_ { - self.0.children().filter_map(RedRef::cast) + self.0.children().filter_map(SyntaxNode::cast) } } @@ -465,7 +468,7 @@ node! { impl ArrayExpr { /// The array items. pub fn items(&self) -> impl Iterator<Item = ArrayItem> + '_ { - self.0.children().filter_map(RedRef::cast) + self.0.children().filter_map(SyntaxNode::cast) } } @@ -479,17 +482,17 @@ pub enum ArrayItem { } impl TypedNode for ArrayItem { - fn from_red(node: RedRef) -> Option<Self> { + fn from_untyped(node: &SyntaxNode) -> Option<Self> { match node.kind() { NodeKind::Spread => node.cast_first_child().map(Self::Spread), _ => node.cast().map(Self::Pos), } } - fn as_red(&self) -> RedRef<'_> { + fn as_untyped(&self) -> &SyntaxNode { match self { - Self::Pos(v) => v.as_red(), - Self::Spread(v) => v.as_red(), + Self::Pos(v) => v.as_untyped(), + Self::Spread(v) => v.as_untyped(), } } } @@ -502,7 +505,7 @@ node! { impl DictExpr { /// The named dictionary items. pub fn items(&self) -> impl Iterator<Item = DictItem> + '_ { - self.0.children().filter_map(RedRef::cast) + self.0.children().filter_map(SyntaxNode::cast) } } @@ -518,7 +521,7 @@ pub enum DictItem { } impl TypedNode for DictItem { - fn from_red(node: RedRef) -> Option<Self> { + fn from_untyped(node: &SyntaxNode) -> Option<Self> { match node.kind() { NodeKind::Named => node.cast().map(Self::Named), NodeKind::Keyed => node.cast().map(Self::Keyed), @@ -527,11 +530,11 @@ impl TypedNode for DictItem { } } - fn as_red(&self) -> RedRef<'_> { + fn as_untyped(&self) -> &SyntaxNode { match self { - Self::Named(v) => v.as_red(), - Self::Keyed(v) => v.as_red(), - Self::Spread(v) => v.as_red(), + Self::Named(v) => v.as_untyped(), + Self::Keyed(v) => v.as_untyped(), + Self::Spread(v) => v.as_untyped(), } } } @@ -895,7 +898,7 @@ node! { impl CallArgs { /// The positional and named arguments. pub fn items(&self) -> impl Iterator<Item = CallArg> + '_ { - self.0.children().filter_map(RedRef::cast) + self.0.children().filter_map(SyntaxNode::cast) } } @@ -911,7 +914,7 @@ pub enum CallArg { } impl TypedNode for CallArg { - fn from_red(node: RedRef) -> Option<Self> { + fn from_untyped(node: &SyntaxNode) -> Option<Self> { match node.kind() { NodeKind::Named => node.cast().map(Self::Named), NodeKind::Spread => node.cast_first_child().map(Self::Spread), @@ -919,11 +922,11 @@ impl TypedNode for CallArg { } } - fn as_red(&self) -> RedRef<'_> { + fn as_untyped(&self) -> &SyntaxNode { match self { - Self::Pos(v) => v.as_red(), - Self::Named(v) => v.as_red(), - Self::Spread(v) => v.as_red(), + Self::Pos(v) => v.as_untyped(), + Self::Named(v) => v.as_untyped(), + Self::Spread(v) => v.as_untyped(), } } } @@ -948,7 +951,7 @@ impl ClosureExpr { .find(|x| x.kind() == &NodeKind::ClosureParams) .expect("closure is missing parameter list") .children() - .filter_map(RedRef::cast) + .filter_map(SyntaxNode::cast) } /// The body of the closure. @@ -969,7 +972,7 @@ pub enum ClosureParam { } impl TypedNode for ClosureParam { - fn from_red(node: RedRef) -> Option<Self> { + fn from_untyped(node: &SyntaxNode) -> Option<Self> { match node.kind() { NodeKind::Ident(_) => node.cast().map(Self::Pos), NodeKind::Named => node.cast().map(Self::Named), @@ -978,11 +981,11 @@ impl TypedNode for ClosureParam { } } - fn as_red(&self) -> RedRef<'_> { + fn as_untyped(&self) -> &SyntaxNode { match self { - Self::Pos(v) => v.as_red(), - Self::Named(v) => v.as_red(), - Self::Sink(v) => v.as_red(), + Self::Pos(v) => v.as_untyped(), + Self::Named(v) => v.as_untyped(), + Self::Sink(v) => v.as_untyped(), } } } @@ -1007,7 +1010,7 @@ impl LetExpr { /// The expression the binding is initialized with. pub fn init(&self) -> Option<Expr> { if self.0.cast_first_child::<Ident>().is_some() { - self.0.children().filter_map(RedRef::cast).nth(1) + self.0.children().filter_map(SyntaxNode::cast).nth(1) } else { // This is a let .. with expression. self.0.cast_first_child() @@ -1042,7 +1045,7 @@ impl ShowExpr { pub fn binding(&self) -> Option<Ident> { let mut children = self.0.children(); children - .find_map(RedRef::cast) + .find_map(SyntaxNode::cast) .filter(|_| children.any(|child| child.kind() == &NodeKind::Colon)) } @@ -1052,7 +1055,7 @@ impl ShowExpr { .children() .rev() .skip_while(|child| child.kind() != &NodeKind::As) - .find_map(RedRef::cast) + .find_map(SyntaxNode::cast) .expect("show rule is missing pattern") } @@ -1094,14 +1097,14 @@ impl IfExpr { pub fn if_body(&self) -> Expr { self.0 .children() - .filter_map(RedRef::cast) + .filter_map(SyntaxNode::cast) .nth(1) .expect("if expression is missing body") } /// The expression to evaluate if the condition is false. pub fn else_body(&self) -> Option<Expr> { - self.0.children().filter_map(RedRef::cast).nth(2) + self.0.children().filter_map(SyntaxNode::cast).nth(2) } } @@ -1152,7 +1155,7 @@ node! { impl ForPattern { /// The key part of the pattern: index for arrays, name for dictionaries. pub fn key(&self) -> Option<Ident> { - let mut children = self.0.children().filter_map(RedRef::cast); + let mut children = self.0.children().filter_map(SyntaxNode::cast); let key = children.next(); if children.next().is_some() { key } else { None } } @@ -1176,7 +1179,7 @@ impl ImportExpr { .find_map(|node| match node.kind() { NodeKind::Star => Some(Imports::Wildcard), NodeKind::ImportItems => { - let items = node.children().filter_map(RedRef::cast).collect(); + let items = node.children().filter_map(SyntaxNode::cast).collect(); Some(Imports::Items(items)) } _ => None, @@ -1241,8 +1244,8 @@ node! { impl Ident { /// Take out the contained [`EcoString`]. pub fn take(self) -> EcoString { - match self.0.green { - Green::Token(GreenData { kind: NodeKind::Ident(id), .. }) => id, + match self.0 { + SyntaxNode::Leaf(NodeData { kind: NodeKind::Ident(id), .. }) => id, _ => panic!("identifier is of wrong kind"), } } @@ -1252,8 +1255,8 @@ impl Deref for Ident { type Target = str; fn deref(&self) -> &Self::Target { - match &self.0.green { - Green::Token(GreenData { kind: NodeKind::Ident(id), .. }) => id, + match &self.0 { + SyntaxNode::Leaf(NodeData { kind: NodeKind::Ident(id), .. }) => id, _ => panic!("identifier is of wrong kind"), } } diff --git a/src/syntax/highlight.rs b/src/syntax/highlight.rs index 94abc238..630a451d 100644 --- a/src/syntax/highlight.rs +++ b/src/syntax/highlight.rs @@ -5,30 +5,43 @@ use std::sync::Arc; use syntect::highlighting::{Color, FontStyle, Highlighter, Style, Theme}; use syntect::parsing::Scope; -use super::{GreenNode, NodeKind, RedNode, RedRef}; +use super::{InnerNode, NodeKind, SyntaxNode}; use crate::parse::TokenMode; -use crate::source::SourceId; /// Provide highlighting categories for the descendants of a node that fall into /// a range. -pub fn highlight_node<F>(node: RedRef, range: Range<usize>, f: &mut F) +pub fn highlight_node<F>(root: &SyntaxNode, range: Range<usize>, mut f: F) where F: FnMut(Range<usize>, Category), { + highlight_node_impl(0, root, range, &mut f) +} + +/// Provide highlighting categories for the descendants of a node that fall into +/// a range. +pub fn highlight_node_impl<F>( + mut offset: usize, + node: &SyntaxNode, + range: Range<usize>, + f: &mut F, +) where + F: FnMut(Range<usize>, Category), +{ for (i, child) in node.children().enumerate() { - let span = child.span(); + let span = offset .. offset + child.len(); if range.start <= span.end && range.end >= span.start { if let Some(category) = Category::determine(child, node, i) { - f(span.to_range(), category); + f(span, category); } - highlight_node(child, range.clone(), f); + highlight_node_impl(offset, child, range.clone(), f); } + offset += child.len(); } } /// Highlight source text in a theme by calling `f` with each consecutive piece /// and its style. -pub fn highlight_themed<F>(text: &str, mode: TokenMode, theme: &Theme, f: &mut F) +pub fn highlight_themed<F>(text: &str, mode: TokenMode, theme: &Theme, mut f: F) where F: FnMut(&str, Style), { @@ -36,20 +49,22 @@ where TokenMode::Markup => crate::parse::parse(text), TokenMode::Code => { let children = crate::parse::parse_code(text); - Arc::new(GreenNode::with_children(NodeKind::CodeBlock, children)) + SyntaxNode::Inner(Arc::new(InnerNode::with_children( + NodeKind::CodeBlock, + children, + ))) } }; - let root = RedNode::from_root(root, SourceId::from_raw(0)); let highlighter = Highlighter::new(&theme); - - highlight_themed_impl(text, root.as_ref(), vec![], &highlighter, f); + highlight_themed_impl(text, 0, &root, vec![], &highlighter, &mut f); } /// Recursive implementation for returning syntect styles. fn highlight_themed_impl<F>( text: &str, - node: RedRef, + mut offset: usize, + node: &SyntaxNode, scopes: Vec<Scope>, highlighter: &Highlighter, f: &mut F, @@ -57,7 +72,7 @@ fn highlight_themed_impl<F>( F: FnMut(&str, Style), { if node.children().len() == 0 { - let piece = &text[node.span().to_range()]; + let piece = &text[offset .. offset + node.len()]; let style = highlighter.style_for_stack(&scopes); f(piece, style); return; @@ -68,7 +83,8 @@ fn highlight_themed_impl<F>( if let Some(category) = Category::determine(child, node, i) { scopes.push(Scope::new(category.tm_scope()).unwrap()) } - highlight_themed_impl(text, child, scopes, highlighter, f); + highlight_themed_impl(text, offset, child, scopes, highlighter, f); + offset += child.len(); } } @@ -92,7 +108,7 @@ pub fn highlight_pre(text: &str, mode: TokenMode, theme: &Theme) -> String { let mut buf = String::new(); buf.push_str("<pre>\n"); - highlight_themed(text, mode, theme, &mut |piece, style| { + highlight_themed(text, mode, theme, |piece, style| { let styled = style != Style::default(); if styled { buf.push_str("<span style=\""); @@ -178,7 +194,11 @@ pub enum Category { impl Category { /// Determine the highlighting category of a node given its parent and its /// index in its siblings. - pub fn determine(child: RedRef, parent: RedRef, i: usize) -> Option<Category> { + pub fn determine( + child: &SyntaxNode, + parent: &SyntaxNode, + i: usize, + ) -> Option<Category> { match child.kind() { NodeKind::LeftBrace => Some(Category::Bracket), NodeKind::RightBrace => Some(Category::Bracket), @@ -262,7 +282,7 @@ impl Category { if parent .children() .filter(|c| matches!(c.kind(), NodeKind::Ident(_))) - .map(RedRef::span) + .map(SyntaxNode::span) .nth(1) .map_or(false, |span| span == child.span()) => { @@ -359,7 +379,7 @@ mod tests { let mut vec = vec![]; let source = SourceFile::detached(src); let full = 0 .. src.len(); - highlight_node(source.red().as_ref(), full, &mut |range, category| { + highlight_node(source.root(), full, &mut |range, category| { vec.push((range, category)); }); assert_eq!(vec, goal); diff --git a/src/syntax/mod.rs b/src/syntax/mod.rs index 69bcb0a0..4a163d78 100644 --- a/src/syntax/mod.rs +++ b/src/syntax/mod.rs @@ -13,25 +13,25 @@ pub use highlight::*; pub use span::*; use self::ast::{MathNode, RawNode, TypedNode, Unit}; -use crate::diag::Error; +use crate::diag::{Error, ErrorPos}; use crate::source::SourceId; use crate::util::EcoString; -/// An inner or leaf node in the untyped green tree. +/// An inner or leaf node in the untyped syntax tree. #[derive(Clone, PartialEq, Hash)] -pub enum Green { +pub enum SyntaxNode { /// A reference-counted inner node. - Node(Arc<GreenNode>), - /// A terminal, owned token. - Token(GreenData), + Inner(Arc<InnerNode>), + /// A leaf token. + Leaf(NodeData), } -impl Green { +impl SyntaxNode { /// Returns the metadata of the node. - fn data(&self) -> &GreenData { + pub fn data(&self) -> &NodeData { match self { - Green::Node(n) => &n.data, - Green::Token(t) => t, + Self::Inner(inner) => &inner.data, + Self::Leaf(leaf) => leaf, } } @@ -45,106 +45,191 @@ impl Green { self.data().len() } - /// Whether the node or its children contain an error. - pub fn erroneous(&self) -> bool { + /// The number of descendants, including the node itself. + pub fn descendants(&self) -> usize { match self { - Self::Node(node) => node.erroneous, - Self::Token(data) => data.kind.is_error(), + Self::Inner(inner) => inner.descendants(), + Self::Leaf(_) => 1, } } + /// The span of the node. + pub fn span(&self) -> Span { + self.data().span() + } + /// The node's children. - pub fn children(&self) -> &[Green] { + pub fn children(&self) -> std::slice::Iter<'_, SyntaxNode> { match self { - Green::Node(n) => n.children(), - Green::Token(_) => &[], + Self::Inner(inner) => inner.children(), + Self::Leaf(_) => [].iter(), } } - /// Whether the node is a leaf node in the green tree. - pub fn is_leaf(&self) -> bool { + /// Whether the node or its children contain an error. + pub fn erroneous(&self) -> bool { match self { - Green::Node(n) => n.children().is_empty(), - Green::Token(_) => true, + Self::Inner(node) => node.erroneous, + Self::Leaf(data) => data.kind.is_error(), } } + /// The error messages for this node and its descendants. + pub fn errors(&self) -> Vec<Error> { + if !self.erroneous() { + return vec![]; + } + + match self.kind() { + &NodeKind::Error(pos, ref message) => { + vec![Error { pos, ..Error::new(self.span(), message) }] + } + _ => self + .children() + .filter(|node| node.erroneous()) + .flat_map(|node| node.errors()) + .collect(), + } + } + + /// Convert the node to a typed AST node. + pub fn cast<T>(&self) -> Option<T> + where + T: TypedNode, + { + T::from_untyped(self) + } + + /// Get the first child that can cast to some AST type. + pub fn cast_first_child<T: TypedNode>(&self) -> Option<T> { + self.children().find_map(Self::cast) + } + + /// Get the last child that can cast to some AST type. + pub fn cast_last_child<T: TypedNode>(&self) -> Option<T> { + self.children().rev().find_map(Self::cast) + } + /// Change the type of the node. pub fn convert(&mut self, kind: NodeKind) { match self { - Self::Node(node) => { - let node = Arc::make_mut(node); + Self::Inner(inner) => { + let node = Arc::make_mut(inner); node.erroneous |= kind.is_error(); node.data.kind = kind; } - Self::Token(data) => data.kind = kind, + Self::Leaf(leaf) => leaf.kind = kind, + } + } + + /// Set a synthetic span for the node and all its descendants. + pub fn synthesize(&mut self, span: Span) { + match self { + Self::Inner(inner) => Arc::make_mut(inner).synthesize(span), + Self::Leaf(leaf) => leaf.synthesize(span), + } + } + + /// Assign spans to each node. + pub fn numberize(&mut self, id: SourceId, within: Range<u64>) -> NumberingResult { + match self { + Self::Inner(inner) => Arc::make_mut(inner).numberize(id, None, within), + Self::Leaf(leaf) => leaf.numberize(id, within), + } + } + + /// The upper bound of assigned numbers in this subtree. + pub fn upper(&self) -> u64 { + match self { + Self::Inner(inner) => inner.upper(), + Self::Leaf(leaf) => leaf.span().number() + 1, } } - /// Set a synthetic span for the node and all its children. - pub fn synthesize(&mut self, span: Arc<Span>) { + /// If the span points into this node, convert it to a byte range. + pub fn range(&self, span: Span, offset: usize) -> Option<Range<usize>> { match self { - Green::Node(n) => Arc::make_mut(n).synthesize(span), - Green::Token(t) => t.synthesize(span), + Self::Inner(inner) => inner.range(span, offset), + Self::Leaf(leaf) => { + (span == leaf.span).then(|| offset .. offset + self.len()) + } + } + } + + /// Returns all leaf descendants of this node (may include itself). + /// + /// This method is slow and only intended for testing. + pub fn leafs(&self) -> Vec<Self> { + if match self { + Self::Inner(inner) => inner.children.is_empty(), + Self::Leaf(_) => true, + } { + vec![self.clone()] + } else { + self.children().flat_map(Self::leafs).collect() } } } -impl Default for Green { +impl Default for SyntaxNode { fn default() -> Self { - Self::Token(GreenData::new(NodeKind::None, 0)) + Self::Leaf(NodeData::new(NodeKind::None, 0)) } } -impl Debug for Green { +impl Debug for SyntaxNode { fn fmt(&self, f: &mut Formatter) -> fmt::Result { match self { - Self::Node(node) => node.fmt(f), - Self::Token(token) => token.fmt(f), + Self::Inner(node) => node.fmt(f), + Self::Leaf(token) => token.fmt(f), } } } -/// An inner node in the untyped green tree. -#[derive(Clone, PartialEq, Hash)] -pub struct GreenNode { +/// An inner node in the untyped syntax tree. +#[derive(Clone, Hash)] +pub struct InnerNode { /// Node metadata. - data: GreenData, - /// This node's children, losslessly make up this node. - children: Vec<Green>, + data: NodeData, + /// The number of nodes in the whole subtree, including this node. + descendants: usize, /// Whether this node or any of its children are erroneous. erroneous: bool, + /// The upper bound of this node's numbering range. + upper: u64, + /// This node's children, losslessly make up this node. + children: Vec<SyntaxNode>, } -impl GreenNode { +impl InnerNode { /// Creates a new node with the given kind and a single child. - pub fn with_child(kind: NodeKind, child: impl Into<Green>) -> Self { + pub fn with_child(kind: NodeKind, child: impl Into<SyntaxNode>) -> Self { Self::with_children(kind, vec![child.into()]) } /// Creates a new node with the given kind and children. - pub fn with_children(kind: NodeKind, children: Vec<Green>) -> Self { + pub fn with_children(kind: NodeKind, children: Vec<SyntaxNode>) -> Self { + let mut len = 0; + let mut descendants = 1; let mut erroneous = kind.is_error(); - let len = children - .iter() - .inspect(|c| erroneous |= c.erroneous()) - .map(Green::len) - .sum(); + + for child in &children { + len += child.len(); + descendants += child.descendants(); + erroneous |= child.erroneous(); + } Self { - data: GreenData::new(kind, len), - children, + data: NodeData::new(kind, len), + descendants, erroneous, + upper: 0, + children, } } - /// The node's children. - pub fn children(&self) -> &[Green] { - &self.children - } - /// The node's metadata. - fn data(&self) -> &GreenData { + pub fn data(&self) -> &NodeData { &self.data } @@ -158,59 +243,233 @@ impl GreenNode { self.data().len() } - /// Set a synthetic span for the node and all its children. - pub fn synthesize(&mut self, span: Arc<Span>) { - self.data.synthesize(span.clone()); + /// The node's span. + pub fn span(&self) -> Span { + self.data().span() + } + + /// The number of descendants, including the node itself. + pub fn descendants(&self) -> usize { + self.descendants + } + + /// The node's children. + pub fn children(&self) -> std::slice::Iter<'_, SyntaxNode> { + self.children.iter() + } + + /// Set a synthetic span for the node and all its descendants. + pub fn synthesize(&mut self, span: Span) { + self.data.synthesize(span); for child in &mut self.children { - child.synthesize(span.clone()); + child.synthesize(span); + } + } + + /// Assign span numbers `within` an interval to this node's subtree or just + /// a `range` of its children. + pub fn numberize( + &mut self, + id: SourceId, + range: Option<Range<usize>>, + within: Range<u64>, + ) -> NumberingResult { + // Determine how many nodes we will number. + let descendants = match &range { + Some(range) if range.is_empty() => return Ok(()), + Some(range) => self.children[range.clone()] + .iter() + .map(SyntaxNode::descendants) + .sum::<usize>(), + None => self.descendants, + }; + + // Determine the distance between two neighbouring assigned numbers. If + // possible, we try to fit all numbers into the left half of `within` + // so that there is space for future insertions. + let space = within.end - within.start; + let mut stride = space / (2 * descendants as u64); + if stride == 0 { + stride = space / self.descendants as u64; + if stride == 0 { + return Err(Unnumberable); + } + } + + // Number this node itself. + let mut start = within.start; + if range.is_none() { + let end = start + stride; + self.data.numberize(id, start .. end)?; + self.upper = within.end; + start = end; + } + + // Number the children. + let len = self.children.len(); + for child in &mut self.children[range.unwrap_or(0 .. len)] { + let end = start + child.descendants() as u64 * stride; + child.numberize(id, start .. end)?; + start = end; + } + + Ok(()) + } + + /// The upper bound of assigned numbers in this subtree. + pub fn upper(&self) -> u64 { + self.upper + } + + /// If the span points into this node, convert it to a byte range. + pub fn range(&self, span: Span, mut offset: usize) -> Option<Range<usize>> { + // Check whether we found it. + if self.data.span == span { + return Some(offset .. offset + self.len()); } + + // The parent of a subtree has a smaller span number than all of its + // descendants. Therefore, we can bail out early if the target span's + // number is smaller than our number. + if span.number() < self.span().number() { + return None; + } + + let mut children = self.children.iter().peekable(); + while let Some(child) = children.next() { + // Every node in this child's subtree has a smaller span number than + // the next sibling. Therefore we only need to recurse if the next + // sibling's span number is larger than the target span's number. + if children + .peek() + .map_or(true, |next| next.span().number() > span.number()) + { + if let Some(range) = child.range(span, offset) { + return Some(range); + } + } + + offset += child.len(); + } + + None } /// The node's children, mutably. - pub(crate) fn children_mut(&mut self) -> &mut [Green] { + pub(crate) fn children_mut(&mut self) -> &mut [SyntaxNode] { &mut self.children } /// Replaces a range of children with some replacement. + /// + /// May have mutated the children if it returns `Err(_)`. pub(crate) fn replace_children( &mut self, - range: Range<usize>, - replacement: Vec<Green>, - ) { + mut range: Range<usize>, + replacement: Vec<SyntaxNode>, + ) -> NumberingResult { let superseded = &self.children[range.clone()]; - let superseded_len: usize = superseded.iter().map(Green::len).sum(); - let replacement_len: usize = replacement.iter().map(Green::len).sum(); - // If we're erroneous, but not due to the superseded range, then we will - // still be erroneous after the replacement. - let still_erroneous = self.erroneous && !superseded.iter().any(Green::erroneous); + // Compute the new byte length. + self.data.len = self.data.len + + replacement.iter().map(SyntaxNode::len).sum::<usize>() + - superseded.iter().map(SyntaxNode::len).sum::<usize>(); + + // Compute the new number of descendants. + self.descendants = self.descendants + + replacement.iter().map(SyntaxNode::descendants).sum::<usize>() + - superseded.iter().map(SyntaxNode::descendants).sum::<usize>(); + + // Determine whether we're still erroneous after the replacement. That's + // the case if + // - any of the new nodes is erroneous, + // - or if we were erroneous before due to a non-superseded node. + self.erroneous = replacement.iter().any(SyntaxNode::erroneous) + || (self.erroneous + && (self.children[.. range.start].iter().any(SyntaxNode::erroneous)) + || self.children[range.end ..].iter().any(SyntaxNode::erroneous)); + + // Perform the replacement. + let replacement_count = replacement.len(); + self.children.splice(range.clone(), replacement); + range.end = range.start + replacement_count; + + // Renumber the new children. Retries until it works, taking + // exponentially more children into account. + let mut left = 0; + let mut right = 0; + let max_left = range.start; + let max_right = self.children.len() - range.end; + loop { + let renumber = range.start - left .. range.end + right; + + // The minimum assignable number is either + // - the upper bound of the node right before the to-be-renumbered + // children, + // - or this inner node's span number plus one if renumbering starts + // at the first child. + let start_number = renumber + .start + .checked_sub(1) + .and_then(|i| self.children.get(i)) + .map_or(self.span().number() + 1, |child| child.upper()); + + // The upper bound for renumbering is either + // - the span number of the first child after the to-be-renumbered + // children, + // - or this node's upper bound if renumbering ends behind the last + // child. + let end_number = self + .children + .get(renumber.end) + .map_or(self.upper(), |next| next.span().number()); + + // Try to renumber. + let within = start_number .. end_number; + let id = self.span().source(); + if self.numberize(id, Some(renumber), within).is_ok() { + return Ok(()); + } - self.children.splice(range, replacement); - self.data.len = self.data.len + replacement_len - superseded_len; - self.erroneous = still_erroneous || self.children.iter().any(Green::erroneous); + // If it didn't even work with all children, we give up. + if left == max_left && right == max_right { + return Err(Unnumberable); + } + + // Exponential expansion to both sides. + left = (left + 1).next_power_of_two().min(max_left); + right = (right + 1).next_power_of_two().min(max_right); + } } - /// Update the length of this node given the old and new length of - /// replaced children. - pub(crate) fn update_parent(&mut self, new_len: usize, old_len: usize) { - self.data.len = self.data.len() + new_len - old_len; - self.erroneous = self.children.iter().any(Green::erroneous); + /// Update the this node given after changes were made to one of its + /// children. + pub(crate) fn update_parent( + &mut self, + prev_len: usize, + new_len: usize, + prev_descendants: usize, + new_descendants: usize, + ) { + self.data.len = self.data.len + new_len - prev_len; + self.descendants = self.descendants + new_descendants - prev_descendants; + self.erroneous = self.children.iter().any(SyntaxNode::erroneous); } } -impl From<GreenNode> for Green { - fn from(node: GreenNode) -> Self { +impl From<InnerNode> for SyntaxNode { + fn from(node: InnerNode) -> Self { Arc::new(node).into() } } -impl From<Arc<GreenNode>> for Green { - fn from(node: Arc<GreenNode>) -> Self { - Self::Node(node) +impl From<Arc<InnerNode>> for SyntaxNode { + fn from(node: Arc<InnerNode>) -> Self { + Self::Inner(node) } } -impl Debug for GreenNode { +impl Debug for InnerNode { fn fmt(&self, f: &mut Formatter) -> fmt::Result { self.data.fmt(f)?; if !self.children.is_empty() { @@ -221,300 +480,85 @@ impl Debug for GreenNode { } } +impl PartialEq for InnerNode { + fn eq(&self, other: &Self) -> bool { + self.data == other.data + && self.descendants == other.descendants + && self.erroneous == other.erroneous + && self.children == other.children + } +} + /// Data shared between inner and leaf nodes. -#[derive(Clone, PartialEq, Hash)] -pub struct GreenData { +#[derive(Clone, Hash)] +pub struct NodeData { /// What kind of node this is (each kind would have its own struct in a /// strongly typed AST). kind: NodeKind, /// The byte length of the node in the source. len: usize, - /// A synthetic span for the node, usually this is `None`. - span: Option<Arc<Span>>, + /// The node's span. + span: Span, } -impl GreenData { +impl NodeData { /// Create new node metadata. pub fn new(kind: NodeKind, len: usize) -> Self { - Self { len, kind, span: None } + Self { len, kind, span: Span::detached() } } - /// The type of the node. + /// The node's type. pub fn kind(&self) -> &NodeKind { &self.kind } - /// The length of the node. + /// The node's length. pub fn len(&self) -> usize { self.len } - /// Set a synthetic span for the node. - pub fn synthesize(&mut self, span: Arc<Span>) { - self.span = Some(span) - } -} - -impl From<GreenData> for Green { - fn from(token: GreenData) -> Self { - Self::Token(token) - } -} - -impl Debug for GreenData { - fn fmt(&self, f: &mut Formatter) -> fmt::Result { - write!(f, "{:?}: {}", self.kind, self.len) - } -} - -/// A owned wrapper for a green node with span information. -/// -/// Owned variant of [`RedRef`]. Can be [cast](Self::cast) to an AST node. -#[derive(Clone, PartialEq, Hash)] -pub struct RedNode { - id: SourceId, - offset: usize, - green: Green, -} - -impl RedNode { - /// Create a new red node from a root [`GreenNode`]. - pub fn from_root(root: Arc<GreenNode>, id: SourceId) -> Self { - Self { id, offset: 0, green: root.into() } - } - - /// Convert to a borrowed representation. - pub fn as_ref(&self) -> RedRef<'_> { - RedRef { - id: self.id, - offset: self.offset, - green: &self.green, - } - } - - /// The node's metadata. - pub fn data(&self) -> &GreenData { - self.as_ref().data() - } - - /// The type of the node. - pub fn kind(&self) -> &NodeKind { - self.as_ref().kind() - } - - /// The length of the node. - pub fn len(&self) -> usize { - self.as_ref().len() - } - - /// The span of the node. + /// The node's span. pub fn span(&self) -> Span { - self.as_ref().span() - } - - /// The error messages for this node and its descendants. - pub fn errors(&self) -> Vec<Error> { - self.as_ref().errors() - } - - /// Convert the node to a typed AST node. - pub fn cast<T>(self) -> Option<T> - where - T: TypedNode, - { - self.as_ref().cast() - } - - /// The children of the node. - pub fn children(&self) -> Children<'_> { - self.as_ref().children() - } - - /// Get the first child that can cast to some AST type. - pub fn cast_first_child<T: TypedNode>(&self) -> Option<T> { - self.as_ref().cast_first_child() - } - - /// Get the last child that can cast to some AST type. - pub fn cast_last_child<T: TypedNode>(&self) -> Option<T> { - self.as_ref().cast_last_child() - } -} - -impl Debug for RedNode { - fn fmt(&self, f: &mut Formatter) -> fmt::Result { - self.as_ref().fmt(f) - } -} - -/// A borrowed wrapper for a [`GreenNode`] with span information. -/// -/// Borrowed variant of [`RedNode`]. Can be [cast](Self::cast) to an AST node. -#[derive(Copy, Clone, PartialEq, Hash)] -pub struct RedRef<'a> { - id: SourceId, - offset: usize, - green: &'a Green, -} - -impl<'a> RedRef<'a> { - /// Convert to an owned representation. - pub fn own(self) -> RedNode { - RedNode { - id: self.id, - offset: self.offset, - green: self.green.clone(), - } - } - - /// The node's metadata. - pub fn data(self) -> &'a GreenData { - self.green.data() - } - - /// The type of the node. - pub fn kind(self) -> &'a NodeKind { - self.green.kind() + self.span } - /// The length of the node. - pub fn len(self) -> usize { - self.green.len() - } - - /// The span of the node. - pub fn span(self) -> Span { - match self.data().span.as_deref() { - Some(&span) => span, - None => Span::new(self.id, self.offset, self.offset + self.len()), - } - } - - /// Whether the node is a leaf node. - pub fn is_leaf(self) -> bool { - self.green.is_leaf() - } - - /// The error messages for this node and its descendants. - pub fn errors(self) -> Vec<Error> { - if !self.green.erroneous() { - return vec![]; - } - - match self.kind() { - NodeKind::Error(pos, msg) => { - let mut span = self.span(); - if self.data().span.is_none() { - span = match pos { - ErrorPos::Start => span.at_start(), - ErrorPos::Full => span, - ErrorPos::End => span.at_end(), - }; - } - - vec![Error::new(span, msg.to_string())] - } - _ => self - .children() - .filter(|red| red.green.erroneous()) - .flat_map(|red| red.errors()) - .collect(), - } + /// Set a synthetic span for the node. + pub fn synthesize(&mut self, span: Span) { + self.span = span; } - /// Returns all leaf descendants of this node (may include itself). - pub fn leafs(self) -> Vec<Self> { - if self.is_leaf() { - vec![self] + /// Assign a span to the node. + pub fn numberize(&mut self, id: SourceId, within: Range<u64>) -> NumberingResult { + if within.start < within.end { + self.span = Span::new(id, (within.start + within.end) / 2); + Ok(()) } else { - self.children().flat_map(Self::leafs).collect() - } - } - - /// Convert the node to a typed AST node. - pub fn cast<T>(self) -> Option<T> - where - T: TypedNode, - { - T::from_red(self) - } - - /// The node's children. - pub fn children(self) -> Children<'a> { - let children = match &self.green { - Green::Node(node) => node.children(), - Green::Token(_) => &[], - }; - - Children { - id: self.id, - iter: children.iter(), - front: self.offset, - back: self.offset + self.len(), + Err(Unnumberable) } } - - /// Get the first child that can cast to some AST type. - pub fn cast_first_child<T: TypedNode>(self) -> Option<T> { - self.children().find_map(RedRef::cast) - } - - /// Get the last child that can cast to some AST type. - pub fn cast_last_child<T: TypedNode>(self) -> Option<T> { - self.children().rev().find_map(RedRef::cast) - } } -impl Debug for RedRef<'_> { - fn fmt(&self, f: &mut Formatter) -> fmt::Result { - write!(f, "{:?}: {:?}", self.kind(), self.span())?; - let mut children = self.children().peekable(); - if children.peek().is_some() { - f.write_str(" ")?; - f.debug_list().entries(children.map(RedRef::own)).finish()?; - } - Ok(()) +impl From<NodeData> for SyntaxNode { + fn from(token: NodeData) -> Self { + Self::Leaf(token) } } -/// An iterator over the children of a red node. -pub struct Children<'a> { - id: SourceId, - iter: std::slice::Iter<'a, Green>, - front: usize, - back: usize, -} - -impl<'a> Iterator for Children<'a> { - type Item = RedRef<'a>; - - fn next(&mut self) -> Option<Self::Item> { - self.iter.next().map(|green| { - let offset = self.front; - self.front += green.len(); - RedRef { id: self.id, offset, green } - }) - } - - fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() +impl Debug for NodeData { + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + write!(f, "{:?}: {}", self.kind, self.len) } } -impl DoubleEndedIterator for Children<'_> { - fn next_back(&mut self) -> Option<Self::Item> { - self.iter.next_back().map(|green| { - self.back -= green.len(); - RedRef { id: self.id, offset: self.back, green } - }) +impl PartialEq for NodeData { + fn eq(&self, other: &Self) -> bool { + self.kind == other.kind && self.len == other.len } } -impl ExactSizeIterator for Children<'_> {} - /// All syntactical building blocks that can be part of a Typst document. /// -/// Can be emitted as a token by the tokenizer or as part of a green node by +/// Can be emitted as a token by the tokenizer or as part of a syntax node by /// the parser. #[derive(Debug, Clone, PartialEq)] pub enum NodeKind { @@ -748,17 +792,6 @@ pub enum NodeKind { Unknown(EcoString), } -/// Where in a node an error should be annotated. -#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] -pub enum ErrorPos { - /// At the start of the node. - Start, - /// Over the full width of the node. - Full, - /// At the end of the node. - End, -} - impl NodeKind { /// Whether this is some kind of brace. pub fn is_brace(&self) -> bool { diff --git a/src/syntax/span.rs b/src/syntax/span.rs index d1e29dd3..5dcd8fc1 100644 --- a/src/syntax/span.rs +++ b/src/syntax/span.rs @@ -1,8 +1,8 @@ -use std::cmp::Ordering; -use std::fmt::{self, Debug, Formatter}; +use std::fmt::{self, Debug, Display, Formatter}; +use std::num::NonZeroU64; use std::ops::Range; -use crate::source::SourceId; +use crate::syntax::SourceId; /// A value with the span it corresponds to in the source code. #[derive(Copy, Clone, Eq, PartialEq, Hash)] @@ -35,122 +35,86 @@ impl<T> Spanned<T> { impl<T: Debug> Debug for Spanned<T> { fn fmt(&self, f: &mut Formatter) -> fmt::Result { - self.v.fmt(f)?; - if f.alternate() { - f.write_str(" <")?; - self.span.fmt(f)?; - f.write_str(">")?; - } - Ok(()) + self.v.fmt(f) } } -/// Bounds of a slice of source code. -#[derive(Copy, Clone, Eq, PartialEq, Hash)] -pub struct Span { - /// The id of the source file. - pub source: SourceId, - /// The inclusive start position. - pub start: usize, - /// The inclusive end position. - pub end: usize, -} +/// A unique identifier for a syntax node. +/// +/// This is used throughout the compiler to track which source section an error +/// or element stems from. Can be [mapped back](crate::source::SourceStore::range) +/// to a source id + byte range for user facing display. +/// +/// Span ids are ordered in the tree to enable quickly finding the node with +/// some id: +/// - The id of a parent is always smaller than the ids of any of its children. +/// - The id of a node is always greater than any id in the subtrees of any left +/// sibling and smaller than any id in the subtrees of any right sibling. +/// +/// The internal ids of spans stay mostly stable, even for nodes behind an +/// insertion. This is not true for simple ranges as they shift. Spans can be +/// used as inputs to memoized functions without hurting cache performance when +/// text is inserted somewhere in the document other than the end. +/// +/// This type takes 8 bytes and is null-optimized (i.e. `Option<Span>` also +/// takes 8 bytes). +#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)] +pub struct Span(NonZeroU64); impl Span { - /// Create a new span from start and end positions. - pub fn new(source: SourceId, start: usize, end: usize) -> Self { - Self { source, start, end } - } - - /// Create a span including just a single position. - pub fn at(source: SourceId, pos: usize) -> Self { - Self::new(source, pos, pos) - } - - /// Create a span without real location information, usually for testing. - pub fn detached() -> Self { - Self { - source: SourceId::from_raw(0), - start: 0, - end: 0, - } - } - - /// Create a span with a different start position. - pub fn with_start(self, start: usize) -> Self { - Self { start, ..self } - } + // Number of bits for and minimum and maximum numbers assignable to spans. + const BITS: usize = 48; + const DETACHED: u64 = 1; + const MIN: u64 = 2; + const MAX: u64 = (1 << Self::BITS) - 1; - /// Create a span with a different end position. - pub fn with_end(self, end: usize) -> Self { - Self { end, ..self } - } - - /// Whether the span is a single point. - pub fn is_empty(self) -> bool { - self.start == self.end - } + /// The full range of numbers available to spans. + pub const FULL: Range<u64> = Self::MIN .. Self::MAX + 1; - /// The byte length of the spanned region. - pub fn len(self) -> usize { - self.end - self.start - } - - /// A new span at the position of this span's start. - pub fn at_start(&self) -> Span { - Self::at(self.source, self.start) - } - - /// A new span at the position of this span's end. - pub fn at_end(&self) -> Span { - Self::at(self.source, self.end) - } - - /// Create a new span with the earlier start and later end position. + /// Create a new span from a source id and a unique number. /// - /// This panics if the spans come from different files. - pub fn join(self, other: Self) -> Self { - debug_assert_eq!(self.source, other.source); - Self { - source: self.source, - start: self.start.min(other.start), - end: self.end.max(other.end), - } + /// Panics if the `number` is not contained in `FULL`. + pub const fn new(id: SourceId, number: u64) -> Self { + assert!(number >= Self::MIN && number <= Self::MAX); + let bits = ((id.into_raw() as u64) << Self::BITS) | number; + Self(to_non_zero(bits)) } - /// Expand a span by merging it with another span. - pub fn expand(&mut self, other: Self) { - *self = self.join(other) + /// A span that does not point into any source file. + pub const fn detached() -> Self { + Self(to_non_zero(Self::DETACHED)) } - /// Test whether a position is within the span. - pub fn contains(&self, pos: usize) -> bool { - self.start <= pos && self.end >= pos + /// The id of the source file the span points into. + pub const fn source(self) -> SourceId { + SourceId::from_raw((self.0.get() >> Self::BITS) as u16) } - /// Test whether one span complete contains the other span. - pub fn surrounds(self, other: Self) -> bool { - self.source == other.source && self.start <= other.start && self.end >= other.end + /// The unique number of the span within the source file. + pub const fn number(self) -> u64 { + self.0.get() & ((1 << Self::BITS) - 1) } +} - /// Convert to a `Range<usize>` for indexing. - pub fn to_range(self) -> Range<usize> { - self.start .. self.end +/// Convert to a non zero u64. +const fn to_non_zero(v: u64) -> NonZeroU64 { + match NonZeroU64::new(v) { + Some(v) => v, + None => unreachable!(), } } -impl Debug for Span { +/// Result of numbering a node within an interval. +pub type NumberingResult = Result<(), Unnumberable>; + +/// Indicates that a node cannot be numbered within a given interval. +#[derive(Debug, Copy, Clone, Eq, PartialEq)] +pub struct Unnumberable; + +impl Display for Unnumberable { fn fmt(&self, f: &mut Formatter) -> fmt::Result { - write!(f, "{:?}-{:?}", self.start, self.end) + f.pad("cannot number within this interval") } } -impl PartialOrd for Span { - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - if self.source == other.source { - Some(self.start.cmp(&other.start).then(self.end.cmp(&other.end))) - } else { - None - } - } -} +impl std::error::Error for Unnumberable {} |