Module similarity 

A similarity-preserving sketch, as opposed to the four equality hashes in crate::code::hash.

node_to_full_hash and friends answer “are these two subtrees exactly the same?” and say nothing at all once the answer is no. A great many of the open matching problems in diff/TODO.md need the other question - “how nearly the same are they?” - in a place where actually comparing the two subtrees is unaffordable: choosing between several equally hash-identical move targets, deciding whether two crossed siblings are the same entity relocated or two different entities, ranking candidates in a large rewrite. One changed token flips a Merkle hash completely, so “95% the same” and “entirely unrelated” are indistinguishable to every hash we have.

This module adds a bottom-k MinHash sketch of the set of leaf hashes in a node’s subtree, computed bottom-up in the same walk that computes the equality hashes (so O(n) at metadata time), and comparable in O(k) - independent of subtree size - afterwards.

Why leaves, and not every descendant node

Sketching every descendant’s full hash sounds more discriminative and is in fact strictly worse for the cases this exists to serve. A single changed token flips the full hash of every ancestor of that token inside the subtree, so a one-token edit deep in a nested chain would remove O(depth) elements from the set rather than 1. Near-identical subtrees differing in one token are precisely the target, so the sketch is taken over leaves only, where one changed token costs exactly one element.

It is an estimate - rank and gate with it, never conclude equality

SimilaritySketch::jaccard is exact whenever both subtrees have at most SKETCH_WIDTH distinct leaf hashes (the sketch is the set at that size, which happens to cover every small subtree - exactly where the estimator’s variance would have hurt most) and an estimate above it. Use it to rank candidates and to gate decisions; the existing exact hashes already answer “are these identical” definitively and should keep doing so.

Structs

SimilaritySketch

The k smallest distinct mixed leaf hashes in a node’s subtree, ascending.

Constants

SKETCH_WIDTH

Number of retained bottom-k values. 16 keeps a sketch to 136 bytes per node and makes the sketch exact (not estimated) for any subtree with <= 16 distinct leaf hashes, which is most nodes in a real file.