Pattern Matching on Elixir's AST

Elixir is homoiconic: the syntax tree representing your code is expressed in ordinary Elixir data structures. The AST is not a private compiler artefact; it is accessible at runtime, pattern-matchable, walkable with Enum, and hashable. This makes it a query language for code itself. The same techniques that power static analysis tools like Credo apply equally to verifying generated code, detecting structural duplication, or enforcing project-specific conventions.

Exploring in IEx

The fastest way to understand the AST is to interrogate it directly. Code.string_to_quoted!/1 parses any string into its AST representation:

iex> Code.string_to_quoted!("1 + 2")
{:+, [line: 1], [1, 2]}

Every node is a {form, metadata, args} tuple. form is an atom naming the operation; metadata is a keyword list (line, column, compiler hints); args is the list of child nodes. Literals (integers, strings, atoms, booleans) appear as themselves.

Remote calls nest an additional level: the form is a {:., meta, [module, function]} tuple, where the module is an __aliases__ node:

iex> Code.string_to_quoted!("IO.puts(\"hello\")")
{{:., [line: 1], [{:__aliases__, [line: 1], [:IO]}, :puts]}, [line: 1], ["hello"]}

Module aliases always use __aliases__ with a list of atoms. Foo.Bar.Baz becomes {:__aliases__, meta, [:Foo, :Bar, :Baz]}. This is the node you match against when checking which modules a piece of code calls.

Pipe chains nest right-to-left, with the outermost pipe at the root:

iex> Code.string_to_quoted!("a |> b |> c")
{:|>, [line: 1],
 [{:|>, [line: 1], [{:a, [line: 1], nil}, {:b, [line: 1], nil}]},
  {:c, [line: 1], nil}]}

Anonymous functions expose the clause structure explicitly:

iex> Code.string_to_quoted!("fn a, b -> a + b end")
{:fn, [line: 1],
 [{:->, [line: 1],
   [[{:a, [line: 1], nil}, {:b, [line: 1], nil}],
    {:+, [line: 1], [{:a, [line: 1], nil}, {:b, [line: 1], nil}]}]}]}

The -> node separates argument list from body. Notice the variable a appears twice with the same atom, which is what makes variable capture across a clause and its body possible in pattern matches.

Once you can read the shapes, the rest is pattern matching.

Walking the Tree

Macro.prewalk/3 traverses the AST depth-first, threading an accumulator through each node. This is the primitive for all structural analysis:

def remote_calls(ast) do
  {_ast, calls} =
    Macro.prewalk(ast, [], fn
      {{:., _, [{:__aliases__, _, parts}, fun]}, _, args} = node, acc ->
        {node, [{Module.concat(parts), fun, length(args)} | acc]}
      node, acc ->
        {node, acc}
    end)

  calls
end

This collects every remote call as {Module, function, arity} tuples. The same skeleton applies to any structural query: replace the pattern, keep the accumulator logic.

Four Techniques

1. Structural pattern match

The most direct approach: write a pattern that describes the exact AST shape you want to detect. To catch Enum.reduce(list, 0, fn n, acc -> n + acc end):

defp explicit_sum?({
  {:., _, [{:__aliases__, _, [:Enum]}, :reduce]},
  _,
  [_enum, 0, fun]
}) do
  sum_fn?(fun)
end
defp explicit_sum?(_), do: false

The inner check uses variable capture to verify the fn adds its own two arguments—in either order:

# fn a, b -> a + b end  OR  fn a, b -> b + a end
defp sum_fn?({:fn, _, [{:->, _, [[{a, _, _}, {b, _, _}], {:+, _, [{a, _, _}, {b, _, _}]}]}]}), do: true
defp sum_fn?({:fn, _, [{:->, _, [[{a, _, _}, {b, _, _}], {:+, _, [{b, _, _}, {a, _, _}]}]}]}), do: true
defp sum_fn?(_), do: false

Elixir’s pattern matching enforces that the variable named in the fn head is the same atom used in the body — no explicit equality check needed. The compiler does the work.

2. Strip metadata, then compare

Code.remove_metadata/1 replaces every meta field in the tree with []. Once stripped, two structurally equivalent AST nodes compare equal with ==. This is useful for detecting identity-passthrough clauses:

# Catches: case result do {:ok, v} -> {:ok, v}; {:error, e} -> {:error, e} end
defp identity_clause?({:->, _meta, [[pattern], body]}) do
  Code.remove_metadata(pattern) == Code.remove_metadata(body)
end

Code.remove_metadata/1 is itself implemented as a Macro.prewalk—a reminder that the AST being data means you can transform it with the same tools you use to query it.

3. Pipeline decomposition

A pipe {:|>, meta, [left, right]} is just another node. Matching a two-step pipeline is a single pattern, which can be generated for multiple variants at compile time:

# Decompose any pipeline into a flat list of steps
def steps({:|>, _, [left, right]}), do: steps(left) ++ [right]
def steps(ast), do: [ast]

# Catch Repo.all(...) |> Enum.filter/reject/find(...)
for filter_fun <- [:filter, :reject, :find] do
  defp repo_then_filter?({:|>, _,
    [
      {{:., _, [{:__aliases__, _, _repo}, :all]}, _, _},
      {{:., _, [{:__aliases__, _, [:Enum]}, unquote(filter_fun)]}, _, _}
    ]
  }), do: true
end
defp repo_then_filter?(_), do: false

The for comprehension expands at compile time to three pattern-matching clauses—Elixir metaprogramming writing static analysis rules.

4. Normalise and hash

For detecting structural duplication across files, the approach is: normalise the AST to remove everything that makes equivalent code look different, then hash it. Any two subtrees with the same hash are structural clones.

The normalisation pass walks each subtree and:

Strips metadata (so formatting and line numbers are irrelevant)
Renames variables to positional placeholders in first-occurrence order (a, x, n all become $0, $1, etc.)
Canonicalises boolean operators (&& → and, || → or)
Expands sigils to their underlying representation

After normalisation, fn(a, b) -> a + b end and fn(x, y) -> x + y end are identical. Fingerprinting uses :erlang.term_to_binary/1 since the normalised AST is a plain Elixir term:

def fingerprint(ast) do
  ast
  |> normalise()
  |> :erlang.term_to_binary()
  |> then(&:crypto.hash(:blake2b, &1))
end

Group all fragments by hash. Any hash with two or more entries is a structural clone—no pairwise comparison, O(n) in the number of AST nodes.

Verification as a Pipeline Stage

These techniques compose into a verification pipeline for generated code. Before evaluating code returned by a template, macro, or language model, you can assert structural invariants at zero runtime cost:

defmodule CodeVerifier do
  @forbidden [IO, System, File, Port, :os, :file]

  def verify(code_string, expected_fun) do
    with {:ok, ast} <- Code.string_to_quoted(code_string),
         :ok        <- assert_single_def(ast, expected_fun),
         :ok        <- assert_no_forbidden_calls(ast) do
      {:ok, ast}
    end
  end

  defp assert_no_forbidden_calls(ast) do
    case Enum.filter(remote_calls(ast), fn {mod, _, _} -> mod in @forbidden end) do
      []    -> :ok
      found -> {:error, {:forbidden_calls, found}}
    end
  end

  # ...
end

def generate_and_run(prompt, expected_fun) do
  with {:ok, code}              <- LLM.generate(prompt),
       {:ok, ast}               <- CodeVerifier.verify(code, expected_fun),
       {:ok, result, _bindings} <- Code.eval_quoted(ast) do
    {:ok, result}
  end
end

Text-based validation would be brittle here: whitespace, comments, and equivalent syntax variations all produce false negatives. AST verification normalises these away. The two forms def f(x), do: x * 2 and def f(x) do\n x * 2\nend parse to the same tree; a structural assertion accepts both without modification.