Dllb.MetaAST.Similarity (Dllb v0.8.1)

Structural similarity comparison for MetaAST trees.

Provides functions for comparing AST subtrees structurally (ignoring names and values), computing structural fingerprints for fast pre-filtering, and detecting code clones across a set of subtrees.

Mirrors the Rust dllb-code-intel::similarity module, enabling client-side clone detection without a server round-trip.

Usage

sim = Dllb.MetaAST.Similarity.structural_similarity(tree_a, tree_b)
# => 0.95

clones = Dllb.MetaAST.Similarity.find_clones(trees, threshold: 0.8)
# => [%{index_a: 0, index_b: 3, similarity: 0.92}, ...]

Summary

Functions

find_clones(nodes, opts \\ [])

Find pairs of subtrees with structural similarity above the given threshold.

structural_similarity(arg1, arg2)

Compute structural similarity between two MetaAST subtrees.

subtree_hash(node)

Compute a single hash of the entire subtree structure.

tree_fingerprint(node)

Produce a structural fingerprint of a MetaAST tree.

Functions

find_clones(nodes, opts \\ [])

@spec find_clones(
  [tuple()],
  keyword()
) :: [map()]

Find pairs of subtrees with structural similarity above the given threshold.

Uses fingerprints for fast pre-filtering: only pairs whose root hash matches (or that have >50% fingerprint overlap) are subjected to full comparison.

Options

:threshold - minimum similarity (default 0.8)

Returns a list of %{index_a: i, index_b: j, similarity: score} maps, sorted by descending similarity.

structural_similarity(arg1, arg2)

@spec structural_similarity(tuple(), tuple()) :: float()

Compute structural similarity between two MetaAST subtrees.

Returns a score in 0.0..1.0 comparing tree shape and node types, ignoring names, values, and metadata. Uses greedy best-match pairing of children weighted by subtree size.

Same node type, both leaves: 1.0
Same node type, both composite: recursive greedy child matching
Different node type: 0.0 base, with partial credit if children overlap

subtree_hash(node)

@spec subtree_hash(tuple()) :: non_neg_integer()

Compute a single hash of the entire subtree structure.

Two structurally identical trees (same node types, same arity at each position) produce the same hash.

tree_fingerprint(node)

@spec tree_fingerprint(tuple()) :: [non_neg_integer()]

Produce a structural fingerprint of a MetaAST tree.

Returns a list of integer hashes representing the structural skeleton (node types + arity at each level). Useful for fast pre-filtering before expensive similarity comparison.