Enforce and make use of span ordering

5 files changed, 80 insertions, 28 deletions

diff --git a/src/diag.rs b/src/diag.rs
index f9ffb1a5..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};
 
@@ -69,6 +70,17 @@ pub enum ErrorPos {
     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 {
diff --git a/src/source.rs b/src/source.rs
index eaf94001..87e96297 100644
--- a/src/source.rs
+++ b/src/source.rs
@@ -169,7 +169,7 @@ impl SourceFile {
         lines.extend(Line::iter(0, 0, &src));
 
         let mut root = parse(&src);
-        root.number(id, 1);
+        root.number(id, Span::MIN_NUMBER);
 
         Self {
             id,
@@ -243,7 +243,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.number(self.id(), 1);
+        self.root.number(self.id(), Span::MIN_NUMBER);
         self.rev = self.rev.wrapping_add(1);
     }
 
@@ -278,7 +278,7 @@ impl SourceFile {
 
         // Incrementally reparse the replaced range.
         let range = reparse(&mut self.root, &self.src, replace, with.len());
-        self.root.number(self.id(), 1);
+        self.root.number(self.id(), Span::MIN_NUMBER);
         range
     }
 
diff --git a/src/syntax/mod.rs b/src/syntax/mod.rs
index 6cecfd2a..0791a761 100644
--- a/src/syntax/mod.rs
+++ b/src/syntax/mod.rs
@@ -62,7 +62,9 @@ impl SyntaxNode {
     pub fn range(&self, span: Span, offset: usize) -> Option<Range<usize>> {
         match self {
             SyntaxNode::Inner(inner) => inner.range(span, offset),
-            SyntaxNode::Leaf(leaf) => leaf.range(span, offset),
+            SyntaxNode::Leaf(leaf) => {
+                (span == leaf.span).then(|| offset .. offset + self.len())
+            }
         }
     }
 
@@ -242,13 +244,30 @@ impl InnerNode {
 
     /// 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>> {
-        if let Some(range) = self.data.range(span, offset) {
-            return Some(range);
+        // 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;
         }
 
-        for child in &self.children {
-            if let Some(range) = child.range(span, offset) {
-                return Some(range);
+        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();
@@ -388,11 +407,6 @@ impl NodeData {
         self.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>> {
-        (self.span == span).then(|| offset .. offset + self.len())
-    }
-
     /// Assign spans to each node.
     pub fn number(&mut self, id: SourceId, from: u64) {
         self.span = Span::new(id, from);
diff --git a/src/syntax/span.rs b/src/syntax/span.rs
index 3f6e6824..496d699c 100644
--- a/src/syntax/span.rs
+++ b/src/syntax/span.rs
@@ -58,26 +58,37 @@ impl<T: Debug> Debug for Spanned<T> {
 pub struct Span(NonZeroU64);
 
 impl Span {
+    // Number of bits for and minimum and maximum numbers assigned to nodes.
+    const BITS: usize = 48;
+    const DETACHED: u64 = 1;
+    pub(crate) const MIN_NUMBER: u64 = 2;
+    pub(crate) const MAX_NUMBER: u64 = (1 << Self::BITS) - 1;
+
     /// Create a new span from a source id and a unique number.
     pub const fn new(id: SourceId, number: u64) -> Self {
-        assert!(number > 0 && number < (1 << 48));
-        let bits = ((id.into_raw() as u64) << 48) | number;
-        Self(nonzero(bits))
+        assert!(number >= Self::MIN_NUMBER && number <= Self::MAX_NUMBER);
+        let bits = ((id.into_raw() as u64) << Self::BITS) | number;
+        Self(convert(bits))
     }
 
     /// A node that does not belong to any source file.
     pub const fn detached() -> Self {
-        Self(nonzero(1))
+        Self(convert(Self::DETACHED))
     }
 
     /// The id of the source file the span points into.
     pub const fn source(self) -> SourceId {
-        SourceId::from_raw((self.0.get() >> 48) as u16)
+        SourceId::from_raw((self.0.get() >> Self::BITS) as u16)
+    }
+
+    /// The unique number of the span within the source file.
+    pub const fn number(self) -> u64 {
+        self.0.get() & Self::MAX_NUMBER
     }
 }
 
 /// Convert to a non zero u64.
-const fn nonzero(v: u64) -> NonZeroU64 {
+const fn convert(v: u64) -> NonZeroU64 {
     match NonZeroU64::new(v) {
         Some(v) => v,
         None => unreachable!(),
diff --git a/tests/typeset.rs b/tests/typeset.rs
index 56cde751..6250ac77 100644
--- a/tests/typeset.rs
+++ b/tests/typeset.rs
@@ -9,7 +9,6 @@ use tiny_skia as sk;
 use unscanny::Scanner;
 use walkdir::WalkDir;
 
-use typst::diag::ErrorPos;
 use typst::eval::{Smart, Value};
 use typst::frame::{Element, Frame};
 use typst::geom::{Length, RgbaColor, Sides};
@@ -18,6 +17,7 @@ use typst::library::text::{TextNode, TextSize};
 use typst::loading::FsLoader;
 use typst::model::StyleMap;
 use typst::source::SourceFile;
+use typst::syntax::SyntaxNode;
 use typst::{bail, Config, Context};
 
 const TYP_DIR: &str = "./typ";
@@ -295,6 +295,8 @@ fn test_part(
         println!("Syntax Tree: {:#?}", source.root())
     }
 
+    test_spans(source.root());
+
     let (local_compare_ref, mut ref_errors) = parse_metadata(&source);
     let compare_ref = local_compare_ref.unwrap_or(compare_ref);
 
@@ -316,12 +318,7 @@ fn test_part(
         .into_iter()
         .filter(|error| error.span.source() == id)
         .map(|error| {
-            let mut range = ctx.sources.range(error.span);
-            match error.pos {
-                ErrorPos::Start => range.end = range.start,
-                ErrorPos::Full => {}
-                ErrorPos::End => range.start = range.end,
-            }
+            let range = error.pos.apply(ctx.sources.range(error.span));
             (range, error.message)
         })
         .collect();
@@ -461,8 +458,8 @@ fn test_reparse(src: &str, i: usize, rng: &mut LinearShift) -> bool {
         incr_source.edit(replace.clone(), with);
 
         let edited_src = incr_source.src();
-        let ref_source = SourceFile::detached(edited_src);
         let incr_root = incr_source.root();
+        let ref_source = SourceFile::detached(edited_src);
         let ref_root = ref_source.root();
         let same = incr_root == ref_root;
         if !same {
@@ -475,6 +472,9 @@ fn test_reparse(src: &str, i: usize, rng: &mut LinearShift) -> bool {
             println!("Full source ({}):\n\"{edited_src:?}\"", edited_src.len());
         }
 
+        test_spans(ref_root);
+        test_spans(incr_root);
+
         same
     };
 
@@ -505,6 +505,21 @@ fn test_reparse(src: &str, i: usize, rng: &mut LinearShift) -> bool {
     ok
 }
 
+/// Ensure that all spans are properly ordered (and therefore unique).
+fn test_spans(root: &SyntaxNode) {
+    test_spans_impl(root, 0 .. u64::MAX);
+}
+
+fn test_spans_impl(root: &SyntaxNode, within: Range<u64>) {
+    assert!(within.contains(&root.span().number()), "wrong span order");
+    let start = root.span().number() + 1;
+    let mut children = root.children().peekable();
+    while let Some(child) = children.next() {
+        let end = children.peek().map_or(within.end, |next| next.span().number());
+        test_spans_impl(child, start .. end);
+    }
+}
+
 /// Draw all frames into one image with padding in between.
 fn render(ctx: &mut Context, frames: &[Arc<Frame>]) -> sk::Pixmap {
     let pixel_per_pt = 2.0;