Predicator.AST (predicator v9.5.0)

Traversal primitives over the tree Predicator.Parser builds.

prewalk/3, postwalk/3 and reduce/3 follow the shape of the standard library's Macro walks: the callback receives a node and an accumulator, and the accumulator is threaded through the whole traversal. They walk anything Predicator.Parser.visitable/0 names - a bare expression, a single statement, a block, or a whole program from Predicator.parse_program/2 - so a tool that reads or rewrites a tree no longer hand-writes a clause per node kind.

What is a node

Every constructor of Predicator.Parser.visitable/0 is a node: the expression layer (Predicator.Parser.ast/0) plus program, assignment, if, while and block. The callback sees each node once, whole, with its trailing position slot as the parser (or a caller) put it. The walks never read, change or drop that slot; a node built by hand with a nil position walks like any other.

Children are visited in source order:

{:comparison, op, left, right, pos} and the other binary nodes: left, then right.
{:function_call, name, args, pos}: each argument, left to right.
{:assignment, location, value, pos}: the location chain, then the value.
{:if, condition, then_block, else_block, pos}: the condition, the then block, then the else block when there is one.
{:program, statements, pos} and {:block, statements, pos}: each statement in order.

Three shapes need a stated rule:

An object literal's key (Predicator.Parser.object_key/0) is part of its entry, not a node of the tree: the walk does not hand it to the callback and carries it through untouched, and visits each entry's value in entry order.
A :duration node holds {integer, unit} pairs, which are plain data. It has no children.
A :relative_date node's first element is itself a node (its :duration), so it is walked as a child.

A literal, string literal and identifier have no children. A value that is not one of these tuples (a tuple with an unknown tag) raises a FunctionClauseError; test/predicator/ast_clause_coverage_test.exs keeps the clause list in step with Predicator.Parser.visitable/0.

Summary

Types

t()

Anything the walks accept: a whole program, a statement, a block or an expression.

Functions

postwalk(ast, acc, fun)

Walks ast post-order, threading acc through fun.

prewalk(ast, acc, fun)

Walks ast pre-order, threading acc through fun.

reduce(ast, acc, fun)

Folds fun over every node of ast pre-order, without rewriting anything.

Types

t()

@type t() :: Predicator.Parser.visitable()

Anything the walks accept: a whole program, a statement, a block or an expression.

Functions

postwalk(ast, acc, fun)

@spec postwalk(t(), acc, (t(), acc -> {t(), acc})) :: {t(), acc} when acc: term()

Walks ast post-order, threading acc through fun.

fun is called on a node after its children have been walked, as fun.(node, acc), and sees the node with its already-rewritten children. It returns {node, acc}; the node it returns is not walked again. Returns {ast, acc}.

Examples

Fold constant additions bottom-up:

iex> {:ok, ast} = Predicator.parse("(1 + 2) + 3")
iex> {folded, folds} =
...>   Predicator.AST.postwalk(ast, 0, fn
...>     {:arithmetic, :add, {:literal, a, _}, {:literal, b, _}, pos}, n
...>     when is_integer(a) and is_integer(b) ->
...>       {{:literal, a + b, pos}, n + 1}
...>
...>     node, n ->
...>       {node, n}
...>   end)
iex> {folds, elem(folded, 1)}
{2, 6}

Children are visited before their parent:

iex> {:ok, ast} = Predicator.parse("a > 1")
iex> {_ast, tags} =
...>   Predicator.AST.postwalk(ast, [], fn node, acc -> {node, [elem(node, 0) | acc]} end)
iex> Enum.reverse(tags)
[:identifier, :literal, :comparison]

prewalk(ast, acc, fun)

@spec prewalk(t(), acc, (t(), acc -> {t(), acc})) :: {t(), acc} when acc: term()

Walks ast pre-order, threading acc through fun.

fun is called on a node before its children, as fun.(node, acc), and returns {node, acc}. The children of the node it returns are the ones walked next, so a callback may replace a node and have the replacement's children visited. Returns {ast, acc}.

Examples

Collect identifier names in source order, leaving the tree as it was:

iex> {:ok, ast} = Predicator.parse("score > limit and ok")
iex> {^ast, names} =
...>   Predicator.AST.prewalk(ast, [], fn
...>     {:identifier, name, _pos} = node, acc -> {node, [name | acc]}
...>     node, acc -> {node, acc}
...>   end)
iex> Enum.reverse(names)
["score", "limit", "ok"]

Replace a node and keep walking into its replacement:

iex> {:ok, ast} = Predicator.parse("1 + 2")
iex> {rewritten, count} =
...>   Predicator.AST.prewalk(ast, 0, fn
...>     {:arithmetic, :add, left, right, pos}, n ->
...>       {{:arithmetic, :multiply, left, right, pos}, n + 1}
...>
...>     {:literal, v, pos}, n when is_integer(v) ->
...>       {{:literal, v * 10, pos}, n + 1}
...>
...>     node, n ->
...>       {node, n}
...>   end)
iex> {count, rewritten}
{3, {:arithmetic, :multiply, {:literal, 10, {1, 1}}, {:literal, 20, {1, 5}}, {1, 3}}}

reduce(ast, acc, fun)

@spec reduce(t(), acc, (t(), acc -> acc)) :: acc when acc: term()

Folds fun over every node of ast pre-order, without rewriting anything.

fun is called as fun.(node, acc) and returns the new accumulator. Returns the final accumulator.

Examples

iex> {:ok, ast} = Predicator.parse("max(a, b) > 3")
iex> Predicator.AST.reduce(ast, [], fn node, acc -> [elem(node, 0) | acc] end)
...> |> Enum.reverse()
[:comparison, :function_call, :identifier, :identifier, :literal]

A whole program is walked statement by statement:

iex> {:ok, program} = Predicator.parse_program("a = 1; b = a + 1")
iex> Predicator.AST.reduce(program, 0, fn
...>   {:assignment, _location, _value, _pos}, n -> n + 1
...>   _node, n -> n
...> end)
2