ExDNA.AST.EditDistance (ExDNA v1.5.0)

Computes structural similarity between two ASTs using a simplified tree edit distance.

Instead of a full Zhang-Shasha algorithm (O(n²m²)), we use a top-down recursive approach that is O(n·m) in practice for typical Elixir ASTs. It computes the number of matching nodes and derives a similarity score.

The similarity is 2 * matching_nodes / (size_a + size_b), yielding a value between 0.0 (completely different) and 1.0 (identical).

Summary

Functions

matching_nodes(same, same)

Count the number of structurally matching nodes between two ASTs.

similarity(ast_a, ast_b)

Compute similarity between two ASTs, returning a float 0.0–1.0.

Functions

matching_nodes(same, same)

@spec matching_nodes(Macro.t(), Macro.t()) :: non_neg_integer()

Count the number of structurally matching nodes between two ASTs.

similarity(ast_a, ast_b)

@spec similarity(Macro.t(), Macro.t()) :: float()

Compute similarity between two ASTs, returning a float 0.0–1.0.