Diff phase 1 anchors on subtrees whose hash occurs exactly once in
each tree, so each node hashes (kind_id, label, child hashes) with
spans excluded: identical code must collide across positions and
across trees. Hashes are computed once at parse time in a reverse
pre-order walk and stored alongside the arena.

Assisted-by: Claude Fable 5 via Claude Code

diff --git a/src/hash.rs b/src/hash.rs
new file mode 100644
index 0000000..6d93631
--- /dev/null
+++ b/src/hash.rs
@@ -0,0 +1,87 @@
+use std::hash::{DefaultHasher, Hash, Hasher};
+
+use crate::tree::Tree;
+
+/// Computes a Merkle hash for every node: (kind_id, label, child hashes
+/// in order), indexed like the tree's arena.
+///
+/// Spans are deliberately excluded so the hash is position-independent —
+/// identical code at different places (or in different trees) collides,
+/// which is exactly what anchoring the diff on unique equal subtrees
+/// needs.
+pub(crate) fn compute(tree: &Tree) -> Vec<u64> {
+    let mut hashes = vec![0u64; tree.nodes().count()];
+    // Arena order is pre-order, so every child's index is greater than
+    // its parent's; walking indices in reverse hashes children first.
+    let ids: Vec<_> = tree.nodes().collect();
+    for &id in ids.iter().rev() {
+        let mut hasher = DefaultHasher::new();
+        tree.kind_id(id).hash(&mut hasher);
+        tree.label(id).hash(&mut hasher);
+        for &child in tree.children(id) {
+            // In-bounds by construction: children share the arena the
+            // hashes vec was sized from, and the reverse walk computed
+            // their hashes already.
+            #[allow(clippy::indexing_slicing)]
+            hashes[child.index()].hash(&mut hasher);
+        }
+        #[allow(clippy::indexing_slicing)]
+        {
+            hashes[id.index()] = hasher.finish();
+        }
+    }
+    hashes
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::error::Error;
+    use crate::lang::Lang;
+    use crate::tree::Tree;
+
+    fn parse_rust(src: &str) -> Result<Tree, Error> {
+        let lang = Lang::by_name("rust").ok_or(Error::UnknownLanguage {
+            path: "rust".into(),
+        })?;
+        Tree::parse(src, lang)
+    }
+
+    #[test]
+    fn identical_subtrees_hash_equal_across_positions() -> Result<(), Error> {
+        let t = parse_rust("fn a() { x(); }\nfn b() { x(); }")?;
+        let calls: Vec<_> = t
+            .nodes()
+            .filter(|&n| t.kind(n) == "call_expression")
+            .collect();
+        assert_eq!(calls.len(), 2);
+        assert_eq!(
+            calls.first().map(|&n| t.hash(n)),
+            calls.last().map(|&n| t.hash(n))
+        );
+        Ok(())
+    }
+
+    #[test]
+    fn equal_sources_hash_equal_across_trees() -> Result<(), Error> {
+        let a = parse_rust("fn main() { x(); }")?;
+        let b = parse_rust("fn main() { x(); }")?;
+        assert_eq!(a.hash(a.root()), b.hash(b.root()));
+        Ok(())
+    }
+
+    #[test]
+    fn different_labels_hash_differently() -> Result<(), Error> {
+        let a = parse_rust("fn main() { x(); }")?;
+        let b = parse_rust("fn main() { y(); }")?;
+        assert_ne!(a.hash(a.root()), b.hash(b.root()));
+        Ok(())
+    }
+
+    #[test]
+    fn different_structure_hashes_differently() -> Result<(), Error> {
+        let a = parse_rust("fn main() { x(); }")?;
+        let b = parse_rust("fn main() { x(); x(); }")?;
+        assert_ne!(a.hash(a.root()), b.hash(b.root()));
+        Ok(())
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index a83a8b2..e419dba 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,4 +1,5 @@
 pub mod error;
+pub mod hash;
 pub mod lang;
 pub mod tree;
 
diff --git a/src/tree.rs b/src/tree.rs
index 28a5de7..de8d236 100644
--- a/src/tree.rs
+++ b/src/tree.rs
@@ -12,6 +12,14 @@ use crate::lang::Lang;
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct NodeId(usize);
 
+impl NodeId {
+    /// The arena index, for dense per-node side tables (subtree hashes,
+    /// matching maps).
+    pub(crate) fn index(self) -> usize {
+        self.0
+    }
+}
+
 /// An owned syntax tree lifted from a tree-sitter CST.
 ///
 /// Nodes live in an arena in pre-order (the root is index 0). The lift
@@ -23,6 +31,7 @@ pub struct NodeId(usize);
 pub struct Tree {
     source: String,
     nodes: Vec<NodeData>,
+    hashes: Vec<u64>,
 }
 
 #[derive(Debug)]
@@ -69,10 +78,13 @@ impl Tree {
         }
 
         let nodes = lift(root);
-        Ok(Self {
+        let mut tree = Self {
             source: source.into(),
             nodes,
-        })
+            hashes: Vec::new(),
+        };
+        tree.hashes = crate::hash::compute(&tree);
+        Ok(tree)
     }
 
     /// The root node (arena index 0).
@@ -132,6 +144,15 @@ impl Tree {
         self.node(id).field_id
     }
 
+    /// The node's subtree Merkle hash: (kind_id, label, child hashes),
+    /// position-independent. Equal hashes mean structurally identical
+    /// subtrees, within or across trees.
+    pub fn hash(&self, id: NodeId) -> u64 {
+        // Same invariant as node(): ids index this arena.
+        #[allow(clippy::indexing_slicing)]
+        self.hashes[id.0]
+    }
+
     fn node(&self, id: NodeId) -> &NodeData {
         // NodeIds only come from this arena's own accessors, so an
         // out-of-range index means ids were mixed across trees — a