Incremental parsing in CLI

Reparses files in the CLI incrementally and also uses the file modification timestamp to completely skip reparsing if possible.

1 files changed, 56 insertions, 12 deletions

diff --git a/crates/typst-syntax/src/source.rs b/crates/typst-syntax/src/source.rs
index 56b27195..f3392889 100644
--- a/crates/typst-syntax/src/source.rs
+++ b/crates/typst-syntax/src/source.rs
@@ -69,13 +69,47 @@ impl Source {
     }
 
     /// Fully replace the source text.
-    pub fn replace(&mut self, text: String) {
-        let inner = Arc::make_mut(&mut self.0);
-        inner.text = Prehashed::new(text);
-        inner.lines = lines(&inner.text);
-        let mut root = parse(&inner.text);
-        root.numberize(inner.id, Span::FULL).unwrap();
-        inner.root = Prehashed::new(root);
+    ///
+    /// This performs a naive (suffix/prefix-based) diff of the old and new text
+    /// to produce the smallest single edit that transforms old into new and
+    /// then calls [`edit`](Self::edit) with it.
+    ///
+    /// Returns the range in the new source that was ultimately reparsed.
+    pub fn replace(&mut self, new: &str) -> Range<usize> {
+        let old = self.text();
+
+        let mut prefix = old
+            .as_bytes()
+            .iter()
+            .zip(new.as_bytes())
+            .take_while(|(x, y)| x == y)
+            .count();
+
+        if prefix == old.len() && prefix == new.len() {
+            return 0..0;
+        }
+
+        while !old.is_char_boundary(prefix) || !new.is_char_boundary(prefix) {
+            prefix -= 1;
+        }
+
+        let mut suffix = old[prefix..]
+            .as_bytes()
+            .iter()
+            .zip(new[prefix..].as_bytes())
+            .rev()
+            .take_while(|(x, y)| x == y)
+            .count();
+
+        while !old.is_char_boundary(old.len() - suffix)
+            || !new.is_char_boundary(new.len() - suffix)
+        {
+            suffix += 1;
+        }
+
+        let replace = prefix..old.len() - suffix;
+        let with = &new[prefix..new.len() - suffix];
+        self.edit(replace, with)
     }
 
     /// Edit the source file by replacing the given range.
@@ -382,11 +416,21 @@ mod tests {
         // tested separately.
         #[track_caller]
         fn test(prev: &str, range: Range<usize>, with: &str, after: &str) {
-            let mut source = Source::detached(prev);
-            let result = Source::detached(after);
-            source.edit(range, with);
-            assert_eq!(source.text(), result.text());
-            assert_eq!(source.0.lines, result.0.lines);
+            let reference = Source::detached(after);
+
+            let mut edited = Source::detached(prev);
+            edited.edit(range.clone(), with);
+            assert_eq!(edited.text(), reference.text());
+            assert_eq!(edited.0.lines, reference.0.lines);
+
+            let mut replaced = Source::detached(prev);
+            replaced.replace(&{
+                let mut s = prev.to_string();
+                s.replace_range(range, with);
+                s
+            });
+            assert_eq!(replaced.text(), reference.text());
+            assert_eq!(replaced.0.lines, reference.0.lines);
         }
 
         // Test inserting at the beginning.