Pattern Matching on Elixir's AST

Elixir is homoiconic: namely, the syntax tree representing your code is expressed in ordinary Elixir data structures. The AST is therefore not a private compiler artefact; it is accessible at runtime, pattern-matchable, walkable with Enum, and hashable. All this means that it serves 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 tuple in the following shape: {form, metadata, args}. 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. The Elixir syntax reference specifies this three-element convention in full.

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. The Macro module also provides postwalk/3 and traverse/4 for post-order and combined traversal, but prewalk 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 of this sort: replace the pattern, keep the accumulator logic.

Four Techniques

1. Structural pattern matching

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 is required: the compiler does the work.

2. Strip metadata, then compare

Stripping all metadata fields replaces every meta keyword list with []. Once stripped, two structurally equivalent AST nodes compare equal with ==. There is no public standard library function for this, but it is a one-liner with Macro.prewalk:

defp strip_meta(ast) do
  Macro.prewalk(ast, fn
    {form, _meta, args} -> {form, [], args}
    leaf -> leaf
  end)
end

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

The fact that this is expressible as a plain Macro.prewalk is the point: the AST is data, and you 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

Detection then reduces to grouping fragments by fingerprint. Wherever a hash appears more than once, the fragments that share it are structural clones of one another. Since grouping requires no pairwise comparison, the whole pass runs in linear time over the AST nodes.

Verification as a Pipeline Stage

These techniques compose into a verification pipeline for generated code. Before handing code returned by a template, macro, or language model to Code.eval_quoted/3, 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.