Merge pull request #73 from typst/span-numbers

4 files changed, 90 insertions, 77 deletions

diff --git a/src/parse/incremental.rs b/src/parse/incremental.rs
index 26f97c52..59dbebeb 100644
--- a/src/parse/incremental.rs
+++ b/src/parse/incremental.rs
@@ -1,36 +1,41 @@
 use std::ops::Range;
 use std::sync::Arc;
 
-use crate::syntax::{Green, GreenNode, NodeKind};
+use crate::syntax::{InnerNode, NodeKind, Span, SyntaxNode};
 
 use super::{
     is_newline, parse, reparse_code_block, reparse_content_block, reparse_markup_elements,
 };
 
-/// Refresh the given green node with as little parsing as possible.
+/// Refresh the given syntax node with as little parsing as possible.
 ///
 /// Takes the new source, the range in the old source that was replaced and the
 /// length of the replacement.
 ///
 /// Returns the range in the new source that was ultimately reparsed.
 pub fn reparse(
-    green: &mut Arc<GreenNode>,
+    root: &mut SyntaxNode,
     src: &str,
     replaced: Range<usize>,
     replacement_len: usize,
 ) -> Range<usize> {
-    Reparser { src, replaced, replacement_len }
-        .reparse_step(Arc::make_mut(green), 0, true)
-        .unwrap_or_else(|| {
-            *green = parse(src);
-            0 .. src.len()
-        })
+    if let SyntaxNode::Inner(inner) = root {
+        let reparser = Reparser { src, replaced, replacement_len };
+        if let Some(range) = reparser.reparse_step(Arc::make_mut(inner), 0, true) {
+            return range;
+        }
+    }
+
+    let id = root.span().source();
+    *root = parse(src);
+    root.numberize(id, Span::FULL).unwrap();
+    0 .. src.len()
 }
 
-/// Allows partial refreshs of the [`Green`] node tree.
+/// Allows partial refreshs of the syntax tree.
 ///
 /// This struct holds a description of a change. Its methods can be used to try
-/// and apply the change to a green tree.
+/// and apply the change to a syntax tree.
 struct Reparser<'a> {
     /// The new source code, with the change applied.
     src: &'a str,
@@ -44,12 +49,12 @@ impl Reparser<'_> {
     /// Try to reparse inside the given node.
     fn reparse_step(
         &self,
-        green: &mut GreenNode,
+        node: &mut InnerNode,
         mut offset: usize,
         outermost: bool,
     ) -> Option<Range<usize>> {
-        let is_markup = matches!(green.kind(), NodeKind::Markup(_));
-        let original_count = green.children().len();
+        let is_markup = matches!(node.kind(), NodeKind::Markup(_));
+        let original_count = node.children().len();
         let original_offset = offset;
 
         let mut search = SearchState::default();
@@ -62,9 +67,10 @@ impl Reparser<'_> {
         let mut child_outermost = false;
 
         // Find the the first child in the range of children to reparse.
-        for (i, child) in green.children().iter().enumerate() {
-            let pos = GreenPos { idx: i, offset };
+        for (i, child) in node.children().enumerate() {
+            let pos = NodePos { idx: i, offset };
             let child_span = offset .. offset + child.len();
+            child_outermost = outermost && i + 1 == original_count;
 
             match search {
                 SearchState::NoneFound => {
@@ -81,6 +87,11 @@ impl Reparser<'_> {
                         };
                     } else if child_span.contains(&self.replaced.start) {
                         search = SearchState::Inside(pos);
+                    } else if child_span.end == self.replaced.start
+                        && self.replaced.start == self.replaced.end
+                        && child_outermost
+                    {
+                        search = SearchState::SpanFound(pos, pos);
                     } else {
                         // We look only for non spaces, non-semicolon and also
                         // reject text that points to the special case for URL
@@ -112,7 +123,6 @@ impl Reparser<'_> {
             }
 
             offset += child.len();
-            child_outermost = outermost && i + 1 == original_count;
 
             if search.done().is_some() {
                 break;
@@ -122,24 +132,26 @@ impl Reparser<'_> {
         // If we were looking for a non-whitespace element and hit the end of
         // the file here, we instead use EOF as the end of the span.
         if let SearchState::RequireNonTrivia(start) = search {
-            search = SearchState::SpanFound(start, GreenPos {
-                idx: green.children().len() - 1,
-                offset: offset - green.children().last().unwrap().len(),
+            search = SearchState::SpanFound(start, NodePos {
+                idx: node.children().len() - 1,
+                offset: offset - node.children().last().unwrap().len(),
             })
         }
 
         if let SearchState::Contained(pos) = search {
-            let child = &mut green.children_mut()[pos.idx];
+            let child = &mut node.children_mut()[pos.idx];
             let prev_len = child.len();
+            let prev_descendants = child.descendants();
 
             if let Some(range) = match child {
-                Green::Node(node) => {
+                SyntaxNode::Inner(node) => {
                     self.reparse_step(Arc::make_mut(node), pos.offset, child_outermost)
                 }
-                Green::Token(_) => None,
+                SyntaxNode::Leaf(_) => None,
             } {
                 let new_len = child.len();
-                green.update_parent(new_len, prev_len);
+                let new_descendants = child.descendants();
+                node.update_parent(prev_len, new_len, prev_descendants, new_descendants);
                 return Some(range);
             }
 
@@ -154,7 +166,7 @@ impl Reparser<'_> {
             // treat it as a markup element.
             if let Some(func) = func {
                 if let Some(result) = self.replace(
-                    green,
+                    node,
                     func,
                     pos.idx .. pos.idx + 1,
                     superseded_span,
@@ -166,14 +178,14 @@ impl Reparser<'_> {
         }
 
         // Save the current indent if this is a markup node and stop otherwise.
-        let indent = match green.kind() {
+        let indent = match node.kind() {
             NodeKind::Markup(n) => *n,
             _ => return None,
         };
 
         let (mut start, end) = search.done()?;
         if let Some((ahead, ahead_at_start)) = ahead_nontrivia {
-            let ahead_kind = green.children()[ahead.idx].kind();
+            let ahead_kind = node.children().as_slice()[ahead.idx].kind();
 
             if start.offset == self.replaced.start
                 || ahead_kind.only_at_start()
@@ -183,14 +195,14 @@ impl Reparser<'_> {
                 at_start = ahead_at_start;
             }
         } else {
-            start = GreenPos { idx: 0, offset: original_offset };
+            start = NodePos { idx: 0, offset: original_offset };
         }
 
         let superseded_span =
-            start.offset .. end.offset + green.children()[end.idx].len();
+            start.offset .. end.offset + node.children().as_slice()[end.idx].len();
 
         self.replace(
-            green,
+            node,
             ReparseMode::MarkupElements(at_start, indent),
             start.idx .. end.idx + 1,
             superseded_span,
@@ -200,7 +212,7 @@ impl Reparser<'_> {
 
     fn replace(
         &self,
-        green: &mut GreenNode,
+        node: &mut InnerNode,
         mode: ReparseMode,
         superseded_idx: Range<usize>,
         superseded_span: Range<usize>,
@@ -237,7 +249,7 @@ impl Reparser<'_> {
                 &self.src[newborn_span.start ..],
                 newborn_span.len(),
                 differential,
-                &green.children()[superseded_start ..],
+                &node.children().as_slice()[superseded_start ..],
                 at_start,
                 indent,
             ),
@@ -249,14 +261,16 @@ impl Reparser<'_> {
             return None;
         }
 
-        green.replace_children(superseded_start .. superseded_start + amount, newborns);
+        node.replace_children(superseded_start .. superseded_start + amount, newborns)
+            .ok()?;
+
         Some(newborn_span)
     }
 }
 
-/// The position of a green node.
+/// The position of a syntax node.
 #[derive(Clone, Copy, Debug, PartialEq)]
-struct GreenPos {
+struct NodePos {
     /// The index in the parent node.
     idx: usize,
     /// The byte offset in the string.
@@ -272,15 +286,15 @@ enum SearchState {
     NoneFound,
     /// The search has concluded by finding a node that fully contains the
     /// modifications.
-    Contained(GreenPos),
+    Contained(NodePos),
     /// The search has found the start of the modified nodes.
-    Inside(GreenPos),
+    Inside(NodePos),
     /// The search has found the end of the modified nodes but the change
     /// touched its boundries so another non-trivia node is needed.
-    RequireNonTrivia(GreenPos),
+    RequireNonTrivia(NodePos),
     /// The search has concluded by finding a start and an end index for nodes
     /// with a pending reparse.
-    SpanFound(GreenPos, GreenPos),
+    SpanFound(NodePos, NodePos),
 }
 
 impl Default for SearchState {
@@ -290,7 +304,7 @@ impl Default for SearchState {
 }
 
 impl SearchState {
-    fn done(self) -> Option<(GreenPos, GreenPos)> {
+    fn done(self) -> Option<(NodePos, NodePos)> {
         match self {
             Self::NoneFound => None,
             Self::Contained(s) => Some((s, s)),
@@ -341,7 +355,7 @@ mod tests {
         test("a\nb\nc *hel a b lo* d\nd\ne", 13..13, "c ", 6..20);
         test("~~ {a} ~~", 4 .. 5, "b", 3 .. 6);
         test("{(0, 1, 2)}", 5 .. 6, "11pt", 0..14);
-        test("\n= A heading", 3 .. 3, "n evocative", 3 .. 23);
+        test("\n= A heading", 4 .. 4, "n evocative", 3 .. 23);
         test("for~your~thing", 9 .. 9, "a", 4 .. 15);
         test("a your thing a", 6 .. 7, "a", 0 .. 14);
         test("{call(); abc}", 7 .. 7, "[]", 0 .. 15);
diff --git a/src/parse/mod.rs b/src/parse/mod.rs
index 4ef1c96f..be3af1f8 100644
--- a/src/parse/mod.rs
+++ b/src/parse/mod.rs
@@ -10,24 +10,21 @@ pub use parser::*;
 pub use tokens::*;
 
 use std::collections::HashSet;
-use std::sync::Arc;
 
+use crate::diag::ErrorPos;
 use crate::syntax::ast::{Associativity, BinOp, UnOp};
-use crate::syntax::{ErrorPos, Green, GreenNode, NodeKind};
+use crate::syntax::{NodeKind, SyntaxNode};
 use crate::util::EcoString;
 
 /// Parse a source file.
-pub fn parse(src: &str) -> Arc<GreenNode> {
+pub fn parse(src: &str) -> SyntaxNode {
     let mut p = Parser::new(src, TokenMode::Markup);
     markup(&mut p, true);
-    match p.finish().into_iter().next() {
-        Some(Green::Node(node)) => node,
-        _ => unreachable!(),
-    }
+    p.finish().into_iter().next().unwrap()
 }
 
 /// Parse code directly, only used for syntax highlighting.
-pub fn parse_code(src: &str) -> Vec<Green> {
+pub fn parse_code(src: &str) -> Vec<SyntaxNode> {
     let mut p = Parser::new(src, TokenMode::Code);
     code(&mut p);
     p.finish()
@@ -40,7 +37,7 @@ fn reparse_code_block(
     prefix: &str,
     src: &str,
     end_pos: usize,
-) -> Option<(Vec<Green>, bool, usize)> {
+) -> Option<(Vec<SyntaxNode>, bool, usize)> {
     let mut p = Parser::with_prefix(prefix, src, TokenMode::Code);
     if !p.at(NodeKind::LeftBrace) {
         return None;
@@ -48,8 +45,8 @@ fn reparse_code_block(
 
     code_block(&mut p);
 
-    let (mut green, terminated) = p.consume()?;
-    let first = green.remove(0);
+    let (mut node, terminated) = p.consume()?;
+    let first = node.remove(0);
     if first.len() != end_pos {
         return None;
     }
@@ -64,7 +61,7 @@ fn reparse_content_block(
     prefix: &str,
     src: &str,
     end_pos: usize,
-) -> Option<(Vec<Green>, bool, usize)> {
+) -> Option<(Vec<SyntaxNode>, bool, usize)> {
     let mut p = Parser::with_prefix(prefix, src, TokenMode::Code);
     if !p.at(NodeKind::LeftBracket) {
         return None;
@@ -72,8 +69,8 @@ fn reparse_content_block(
 
     content_block(&mut p);
 
-    let (mut green, terminated) = p.consume()?;
-    let first = green.remove(0);
+    let (mut node, terminated) = p.consume()?;
+    let first = node.remove(0);
     if first.len() != end_pos {
         return None;
     }
@@ -89,13 +86,13 @@ fn reparse_markup_elements(
     src: &str,
     end_pos: usize,
     differential: isize,
-    reference: &[Green],
+    reference: &[SyntaxNode],
     mut at_start: bool,
     column: usize,
-) -> Option<(Vec<Green>, bool, usize)> {
+) -> Option<(Vec<SyntaxNode>, bool, usize)> {
     let mut p = Parser::with_prefix(prefix, src, TokenMode::Markup);
 
-    let mut node: Option<&Green> = None;
+    let mut node: Option<&SyntaxNode> = None;
     let mut iter = reference.iter();
     let mut offset = differential;
     let mut replaced = 0;
@@ -110,7 +107,7 @@ fn reparse_markup_elements(
 
         markup_node(&mut p, &mut at_start);
 
-        if p.prev_end() < end_pos {
+        if p.prev_end() <= end_pos {
             continue;
         }
 
@@ -683,7 +680,7 @@ fn dict(p: &mut Parser, marker: Marker) {
         kind if kind.is_paren() => Ok(()),
         NodeKind::Named | NodeKind::Keyed => {
             if let Some(NodeKind::Ident(key) | NodeKind::Str(key)) =
-                x.children().first().map(|child| child.kind())
+                x.children().next().map(|child| child.kind())
             {
                 if !used.insert(key.clone()) {
                     return Err("pair has duplicate key");
@@ -770,7 +767,7 @@ fn args(p: &mut Parser, direct: bool, brackets: bool) -> ParseResult {
             marker.filter_children(p, |x| match x.kind() {
                 NodeKind::Named => {
                     if let Some(NodeKind::Ident(ident)) =
-                        x.children().first().map(|child| child.kind())
+                        x.children().next().map(|child| child.kind())
                     {
                         if !used.insert(ident.clone()) {
                             return Err("duplicate argument");
diff --git a/src/parse/parser.rs b/src/parse/parser.rs
index f3a3ffd1..722e53ce 100644
--- a/src/parse/parser.rs
+++ b/src/parse/parser.rs
@@ -3,7 +3,8 @@ use std::mem;
 use std::ops::Range;
 
 use super::{TokenMode, Tokens};
-use crate::syntax::{ErrorPos, Green, GreenData, GreenNode, NodeKind};
+use crate::diag::ErrorPos;
+use crate::syntax::{InnerNode, NodeData, NodeKind, SyntaxNode};
 use crate::util::EcoString;
 
 /// A convenient token-based parser.
@@ -21,7 +22,7 @@ pub struct Parser<'s> {
     /// The stack of open groups.
     groups: Vec<GroupEntry>,
     /// The children of the currently built node.
-    children: Vec<Green>,
+    children: Vec<SyntaxNode>,
     /// Whether the last group was not correctly terminated.
     unterminated_group: bool,
     /// Whether a group terminator was found, that did not close a group.
@@ -54,14 +55,14 @@ impl<'s> Parser<'s> {
     }
 
     /// End the parsing process and return the parsed children.
-    pub fn finish(self) -> Vec<Green> {
+    pub fn finish(self) -> Vec<SyntaxNode> {
         self.children
     }
 
     /// End the parsing process and return the parsed children and whether the
     /// last token was terminated if all groups were terminated correctly or
     /// `None` otherwise.
-    pub fn consume(self) -> Option<(Vec<Green>, bool)> {
+    pub fn consume(self) -> Option<(Vec<SyntaxNode>, bool)> {
         self.terminated().then(|| (self.children, self.tokens.terminated()))
     }
 
@@ -94,11 +95,11 @@ impl<'s> Parser<'s> {
         if self.tokens.mode() == TokenMode::Code {
             // Trailing trivia should not be wrapped into the new node.
             let idx = self.children.len();
-            self.children.push(Green::default());
+            self.children.push(SyntaxNode::default());
             self.children.extend(children.drain(until.0 ..));
-            self.children[idx] = GreenNode::with_children(kind, children).into();
+            self.children[idx] = InnerNode::with_children(kind, children).into();
         } else {
-            self.children.push(GreenNode::with_children(kind, children).into());
+            self.children.push(InnerNode::with_children(kind, children).into());
         }
 
         output
@@ -291,7 +292,7 @@ impl<'s> Parser<'s> {
             if group_mode == TokenMode::Code {
                 let start = self.trivia_start().0;
                 target = self.current_start
-                    - self.children[start ..].iter().map(Green::len).sum::<usize>();
+                    - self.children[start ..].iter().map(SyntaxNode::len).sum::<usize>();
                 self.children.truncate(start);
             }
 
@@ -314,7 +315,7 @@ impl<'s> Parser<'s> {
     fn bump(&mut self) {
         let kind = self.current.take().unwrap();
         let len = self.tokens.cursor() - self.current_start;
-        self.children.push(GreenData::new(kind, len).into());
+        self.children.push(NodeData::new(kind, len).into());
         self.current_start = self.tokens.cursor();
         self.current = self.tokens.next();
     }
@@ -399,7 +400,7 @@ impl Parser<'_> {
     pub fn expected_at(&mut self, marker: Marker, what: &str) {
         let msg = format_eco!("expected {}", what);
         let error = NodeKind::Error(ErrorPos::Full, msg);
-        self.children.insert(marker.0, GreenData::new(error, 0).into());
+        self.children.insert(marker.0, NodeData::new(error, 0).into());
     }
 
     /// Eat the current token and add an error that it is not the expected
@@ -422,12 +423,12 @@ pub struct Marker(usize);
 
 impl Marker {
     /// Peek at the child directly before the marker.
-    pub fn before<'a>(self, p: &'a Parser) -> Option<&'a Green> {
+    pub fn before<'a>(self, p: &'a Parser) -> Option<&'a SyntaxNode> {
         p.children.get(self.0.checked_sub(1)?)
     }
 
     /// Peek at the child directly after the marker.
-    pub fn after<'a>(self, p: &'a Parser) -> Option<&'a Green> {
+    pub fn after<'a>(self, p: &'a Parser) -> Option<&'a SyntaxNode> {
         p.children.get(self.0)
     }
 
@@ -455,13 +456,13 @@ impl Marker {
         let until = p.trivia_start();
         let children = p.children.drain(self.0 .. until.0).collect();
         p.children
-            .insert(self.0, GreenNode::with_children(kind, children).into());
+            .insert(self.0, InnerNode::with_children(kind, children).into());
     }
 
     /// Wrap all children that do not fulfill the predicate in error nodes.
     pub fn filter_children<F>(self, p: &mut Parser, mut f: F)
     where
-        F: FnMut(&Green) -> Result<(), &'static str>,
+        F: FnMut(&SyntaxNode) -> Result<(), &'static str>,
     {
         for child in &mut p.children[self.0 ..] {
             // Don't expose errors.
@@ -482,7 +483,7 @@ impl Marker {
                 }
                 let error = NodeKind::Error(ErrorPos::Full, msg);
                 let inner = mem::take(child);
-                *child = GreenNode::with_child(error, inner).into();
+                *child = InnerNode::with_child(error, inner).into();
             }
         }
     }
diff --git a/src/parse/tokens.rs b/src/parse/tokens.rs
index f095bd09..92155909 100644
--- a/src/parse/tokens.rs
+++ b/src/parse/tokens.rs
@@ -4,9 +4,10 @@ use unicode_xid::UnicodeXID;
 use unscanny::Scanner;
 
 use super::resolve::{resolve_hex, resolve_raw, resolve_string};
+use crate::diag::ErrorPos;
 use crate::geom::{AngleUnit, LengthUnit};
 use crate::syntax::ast::{MathNode, RawNode, Unit};
-use crate::syntax::{ErrorPos, NodeKind};
+use crate::syntax::NodeKind;
 use crate::util::EcoString;
 
 /// An iterator over the tokens of a string of source code.