Merge pull request #73 from typst/span-numbers

15 files changed, 733 insertions, 664 deletions

diff --git a/src/diag.rs b/src/diag.rs
index 9e756bfe..b9fcebdf 100644
--- a/src/diag.rs
+++ b/src/diag.rs
@@ -1,6 +1,7 @@
 //! Diagnostics.
 
 use std::fmt::{self, Display, Formatter};
+use std::ops::Range;
 
 use crate::syntax::{Span, Spanned};
 
@@ -36,8 +37,10 @@ pub type StrResult<T> = Result<T, String>;
 /// An error in a source file.
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub struct Error {
-    /// The erroneous location in the source code.
+    /// The erroneous node in the source code.
     pub span: Span,
+    /// Where in the node the error should be annotated.
+    pub pos: ErrorPos,
     /// A diagnostic message describing the problem.
     pub message: String,
     /// The trace of function calls leading to the error.
@@ -49,12 +52,35 @@ impl Error {
     pub fn new(span: Span, message: impl Into<String>) -> Self {
         Self {
             span,
+            pos: ErrorPos::Full,
             trace: vec![],
             message: message.into(),
         }
     }
 }
 
+/// 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 ErrorPos {
+    /// Apply this to a node's byte range.
+    pub fn apply(self, range: Range<usize>) -> Range<usize> {
+        match self {
+            ErrorPos::Start => range.start .. range.start,
+            ErrorPos::Full => range,
+            ErrorPos::End => range.end .. range.end,
+        }
+    }
+}
+
 /// A part of an error's [trace](Error::trace).
 #[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd)]
 pub enum Tracepoint {
@@ -110,9 +136,7 @@ impl<T> Trace<T> for TypResult<T> {
     {
         self.map_err(|mut errors| {
             for error in errors.iter_mut() {
-                if !span.surrounds(error.span) {
-                    error.trace.push(Spanned::new(make_point(), span));
-                }
+                error.trace.push(Spanned::new(make_point(), span));
             }
             errors
         })
diff --git a/src/eval/capture.rs b/src/eval/capture.rs
index 1192eaa7..252e9b71 100644
--- a/src/eval/capture.rs
+++ b/src/eval/capture.rs
@@ -1,6 +1,6 @@
 use super::{Scope, Scopes, Value};
 use crate::syntax::ast::{ClosureParam, Expr, Ident, Imports, TypedNode};
-use crate::syntax::RedRef;
+use crate::syntax::SyntaxNode;
 
 /// A visitor that captures variable slots.
 pub struct CapturesVisitor<'a> {
@@ -39,7 +39,7 @@ impl<'a> CapturesVisitor<'a> {
     }
 
     /// Visit any node and collect all captured variables.
-    pub fn visit(&mut self, node: RedRef) {
+    pub fn visit(&mut self, node: &SyntaxNode) {
         match node.cast() {
             // Every identifier is a potential variable that we need to capture.
             // Identifiers that shouldn't count as captures because they
@@ -62,7 +62,7 @@ impl<'a> CapturesVisitor<'a> {
             Some(Expr::Closure(expr)) => {
                 for param in expr.params() {
                     if let ClosureParam::Named(named) = param {
-                        self.visit(named.expr().as_red());
+                        self.visit(named.expr().as_untyped());
                     }
                 }
 
@@ -74,14 +74,14 @@ impl<'a> CapturesVisitor<'a> {
                     }
                 }
 
-                self.visit(expr.body().as_red());
+                self.visit(expr.body().as_untyped());
             }
 
             // A let expression contains a binding, but that binding is only
             // active after the body is evaluated.
             Some(Expr::Let(expr)) => {
                 if let Some(init) = expr.init() {
-                    self.visit(init.as_red());
+                    self.visit(init.as_untyped());
                 }
                 self.bind(expr.binding());
             }
@@ -89,30 +89,30 @@ impl<'a> CapturesVisitor<'a> {
             // A show rule contains a binding, but that binding is only active
             // after the target has been evaluated.
             Some(Expr::Show(show)) => {
-                self.visit(show.pattern().as_red());
+                self.visit(show.pattern().as_untyped());
                 if let Some(binding) = show.binding() {
                     self.bind(binding);
                 }
-                self.visit(show.body().as_red());
+                self.visit(show.body().as_untyped());
             }
 
             // A for loop contains one or two bindings in its pattern. These are
             // active after the iterable is evaluated but before the body is
             // evaluated.
             Some(Expr::For(expr)) => {
-                self.visit(expr.iter().as_red());
+                self.visit(expr.iter().as_untyped());
                 let pattern = expr.pattern();
                 if let Some(key) = pattern.key() {
                     self.bind(key);
                 }
                 self.bind(pattern.value());
-                self.visit(expr.body().as_red());
+                self.visit(expr.body().as_untyped());
             }
 
             // An import contains items, but these are active only after the
             // path is evaluated.
             Some(Expr::Import(expr)) => {
-                self.visit(expr.path().as_red());
+                self.visit(expr.path().as_untyped());
                 if let Imports::Items(items) = expr.imports() {
                     for item in items {
                         self.bind(item);
@@ -134,21 +134,17 @@ impl<'a> CapturesVisitor<'a> {
 mod tests {
     use super::*;
     use crate::parse::parse;
-    use crate::source::SourceId;
-    use crate::syntax::RedNode;
 
     #[track_caller]
     fn test(src: &str, result: &[&str]) {
-        let green = parse(src);
-        let red = RedNode::from_root(green, SourceId::from_raw(0));
-
         let mut scopes = Scopes::new(None);
         scopes.top.define("x", 0);
         scopes.top.define("y", 0);
         scopes.top.define("z", 0);
 
         let mut visitor = CapturesVisitor::new(&scopes);
-        visitor.visit(red.as_ref());
+        let root = parse(src);
+        visitor.visit(&root);
 
         let captures = visitor.finish();
         let mut names: Vec<_> = captures.iter().map(|(k, _)| k).collect();
diff --git a/src/eval/mod.rs b/src/eval/mod.rs
index db7595f9..d39fc3ad 100644
--- a/src/eval/mod.rs
+++ b/src/eval/mod.rs
@@ -698,7 +698,7 @@ impl Eval for ClosureExpr {
         // Collect captured variables.
         let captured = {
             let mut visitor = CapturesVisitor::new(&vm.scopes);
-            visitor.visit(self.as_red());
+            visitor.visit(self.as_untyped());
             visitor.finish()
         };
 
@@ -770,7 +770,7 @@ impl Eval for ShowExpr {
         // Collect captured variables.
         let captured = {
             let mut visitor = CapturesVisitor::new(&vm.scopes);
-            visitor.visit(self.as_red());
+            visitor.visit(self.as_untyped());
             visitor.finish()
         };
 
diff --git a/src/lib.rs b/src/lib.rs
index bcbf8478..f9416463 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -2,9 +2,9 @@
 //!
 //! # Steps
 //! - **Parsing:** The parsing step first transforms a plain string into an
-//!   [iterator of tokens][tokens]. This token stream is [parsed] into a [green
-//!   tree]. The green tree itself is untyped, but a typed layer over it is
-//!   provided in the [AST] module.
+//!   [iterator of tokens][tokens]. This token stream is [parsed] into a [syntax
+//!   tree]. The tree itself is untyped, but a typed layer over it is provided
+//!   in the [AST] module.
 //! - **Evaluation:** The next step is to [evaluate] the markup. This produces a
 //!   [module], consisting of a scope of values that were exported by the code
 //!   and [content], a hierarchical, styled representation with the contents of
@@ -19,7 +19,7 @@
 //!
 //! [tokens]: parse::Tokens
 //! [parsed]: parse::parse
-//! [green tree]: syntax::GreenNode
+//! [syntax tree]: syntax::SyntaxNode
 //! [AST]: syntax::ast
 //! [evaluate]: eval::evaluate
 //! [module]: eval::Module
diff --git a/src/library/text/raw.rs b/src/library/text/raw.rs
index fe1f9a99..a24d2170 100644
--- a/src/library/text/raw.rs
+++ b/src/library/text/raw.rs
@@ -75,7 +75,7 @@ impl Show for RawNode {
             };
 
             let mut seq = vec![];
-            syntax::highlight_themed(&self.text, mode, &THEME, &mut |piece, style| {
+            syntax::highlight_themed(&self.text, mode, &THEME, |piece, style| {
                 seq.push(styled(piece, foreground, style));
             });
 
diff --git a/src/main.rs b/src/main.rs
index 33302eee..d518a03b 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -240,7 +240,7 @@ fn print_diagnostics(
     for error in errors {
         // The main diagnostic.
         let diag = Diagnostic::error().with_message(error.message).with_labels(vec![
-            Label::primary(error.span.source, error.span.to_range()),
+            Label::primary(error.span.source(), sources.range(error.span)),
         ]);
 
         term::emit(&mut w, &config, sources, &diag)?;
@@ -249,7 +249,7 @@ fn print_diagnostics(
         for point in error.trace {
             let message = point.v.to_string();
             let help = Diagnostic::help().with_message(message).with_labels(vec![
-                Label::primary(point.span.source, point.span.to_range()),
+                Label::primary(point.span.source(), sources.range(point.span)),
             ]);
 
             term::emit(&mut w, &config, sources, &help)?;
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.
diff --git a/src/source.rs b/src/source.rs
index 77a020cb..507e4d20 100644
--- a/src/source.rs
+++ b/src/source.rs
@@ -12,7 +12,7 @@ use crate::diag::TypResult;
 use crate::loading::{FileHash, Loader};
 use crate::parse::{is_newline, parse, reparse};
 use crate::syntax::ast::Markup;
-use crate::syntax::{GreenNode, RedNode, Span};
+use crate::syntax::{Span, SyntaxNode};
 use crate::util::{PathExt, StrExt};
 
 #[cfg(feature = "codespan-reporting")]
@@ -20,24 +20,24 @@ use codespan_reporting::files::{self, Files};
 
 /// A unique identifier for a loaded source file.
 #[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
-pub struct SourceId(u32);
+pub struct SourceId(u16);
 
 impl SourceId {
     /// Create a new source id for a file that is not part of a store.
     pub const fn detached() -> Self {
-        Self(u32::MAX)
+        Self(u16::MAX)
     }
 
     /// Create a source id from the raw underlying value.
     ///
     /// This should only be called with values returned by
     /// [`into_raw`](Self::into_raw).
-    pub const fn from_raw(v: u32) -> Self {
+    pub const fn from_raw(v: u16) -> Self {
         Self(v)
     }
 
     /// Convert into the raw underlying value.
-    pub const fn into_raw(self) -> u32 {
+    pub const fn into_raw(self) -> u16 {
         self.0
     }
 }
@@ -108,7 +108,7 @@ impl SourceStore {
         }
 
         // No existing file yet.
-        let id = SourceId(self.sources.len() as u32);
+        let id = SourceId(self.sources.len() as u16);
         self.sources.push(SourceFile::new(id, path, src));
 
         // Register in file map if the path was known to the loader.
@@ -140,6 +140,14 @@ impl SourceStore {
     ) -> Range<usize> {
         self.sources[id.0 as usize].edit(replace, with)
     }
+
+    /// Map a span that points into a [file](SourceFile::range) stored in this
+    /// source store to a byte range.
+    ///
+    /// Panics if the span does not point into this source store.
+    pub fn range(&self, span: Span) -> Range<usize> {
+        self.get(span.source()).range(span)
+    }
 }
 
 /// A single source file.
@@ -151,7 +159,7 @@ pub struct SourceFile {
     path: PathBuf,
     src: String,
     lines: Vec<Line>,
-    root: Arc<GreenNode>,
+    root: SyntaxNode,
     rev: usize,
 }
 
@@ -160,10 +168,14 @@ impl SourceFile {
     pub fn new(id: SourceId, path: &Path, src: String) -> Self {
         let mut lines = vec![Line { byte_idx: 0, utf16_idx: 0 }];
         lines.extend(Line::iter(0, 0, &src));
+
+        let mut root = parse(&src);
+        root.numberize(id, Span::FULL).unwrap();
+
         Self {
             id,
             path: path.normalize(),
-            root: parse(&src),
+            root,
             src,
             lines,
             rev: 0,
@@ -178,27 +190,21 @@ impl SourceFile {
     /// Create a source file with the same synthetic span for all nodes.
     pub fn synthesized(src: impl Into<String>, span: Span) -> Self {
         let mut file = Self::detached(src);
-        Arc::make_mut(&mut file.root).synthesize(Arc::new(span));
-        file.id = span.source;
+        file.root.synthesize(span);
+        file.id = span.source();
         file
     }
 
-    /// The root node of the file's untyped green tree.
-    pub fn root(&self) -> &Arc<GreenNode> {
+    /// The root node of the file's untyped syntax tree.
+    pub fn root(&self) -> &SyntaxNode {
         &self.root
     }
 
-    /// The root red node of the file's untyped red tree.
-    pub fn red(&self) -> RedNode {
-        RedNode::from_root(self.root.clone(), self.id)
-    }
-
     /// The root node of the file's typed abstract syntax tree.
     pub fn ast(&self) -> TypResult<Markup> {
-        let red = self.red();
-        let errors = red.errors();
+        let errors = self.root.errors();
         if errors.is_empty() {
-            Ok(red.cast().unwrap())
+            Ok(self.root.cast().unwrap())
         } else {
             Err(Box::new(errors))
         }
@@ -238,6 +244,7 @@ impl SourceFile {
         self.lines = vec![Line { byte_idx: 0, utf16_idx: 0 }];
         self.lines.extend(Line::iter(0, 0, &self.src));
         self.root = parse(&self.src);
+        self.root.numberize(self.id(), Span::FULL).unwrap();
         self.rev = self.rev.wrapping_add(1);
     }
 
@@ -290,6 +297,15 @@ impl SourceFile {
         self.lines.len()
     }
 
+    /// Map a span that points into this source file to a byte range.
+    ///
+    /// Panics if the span does not point into this source file.
+    pub fn range(&self, span: Span) -> Range<usize> {
+        self.root
+            .range(span, 0)
+            .expect("span does not point into this source file")
+    }
+
     /// Return the index of the UTF-16 code unit at the byte index.
     pub fn byte_to_utf16(&self, byte_idx: usize) -> Option<usize> {
         let line_idx = self.byte_to_line(byte_idx)?;
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 {}