ExDNA.AST.Normalizer (ExDNA v1.5.1)

Copy Markdown View Source

Normalizes Elixir AST for structural comparison.

Transforms an AST so that structurally equivalent code produces identical output regardless of variable names, metadata, or (optionally) literal values.

All normalizations are performed in at most two AST traversals:

Pass 1 (always, single fused walk):

  1. Metadata stripping — removes line numbers, columns, counters, and other compiler metadata from every node.
  2. Boolean operator canonicalization&&/||/! are rewritten to and/or/not so stylistic choice between short-circuit and keyword operators doesn't affect comparison.
  3. Sigil expansion~w(foo bar)a is expanded to [:foo, :bar] (and likewise for string modifiers) so sigil word-lists match their literal equivalents.
  4. Pipe normalization (optional) — x |> f() is rewritten to f(x).
  5. Variable normalization — replaces variable names with positional placeholders (:$0, :$1, …) based on first-occurrence order.

Pass 2 (abstract mode only, single recursive walk):

  1. Literal abstraction — replaces concrete literals with type-tagged placeholders to detect Type-II clones.
  2. Map/struct field sorting — sorts key-value pairs so that %{b: 1, a: 2} and %{a: 2, b: 1} produce the same hash.
  3. Guard abstraction — in when clauses, replaces all function/macro call names with a :__guard__ placeholder so that when is_binary(x) and when is_atom(x) produce the same hash. Covers all Kernel guards, Erlang BIF guards, defguard macros, and library guards like Integer.is_even/1.

Summary

Functions

Normalize an AST fragment.

Replace all variable names with positional placeholders based on binding order.

Remove all metadata from every AST node, keeping only structural shape.

Types

option()

@type option() :: {:literal_mode, :keep | :abstract} | {:normalize_pipes, boolean()}

Functions

normalize(ast, opts \\ [])

@spec normalize(Macro.t(), [option()]) :: Macro.t()

Normalize an AST fragment.

Options

  • :literal_mode:keep preserves literal values (Type-I detection), :abstract replaces them with placeholders (Type-II detection). Defaults to :keep.
  • :normalize_pipes — when true, convert pipe chains to nested calls so x |> f() matches f(x). Defaults to false.

normalize_variables(ast)

@spec normalize_variables(Macro.t()) :: Macro.t()

Replace all variable names with positional placeholders based on binding order.

foo + bar and x + y both become :"$0" + :"$1".

strip_metadata(ast)

@spec strip_metadata(Macro.t()) :: Macro.t()

Remove all metadata from every AST node, keeping only structural shape.