Nasty.Utils.Traversal (Nasty v0.3.0)

AST traversal utilities using the visitor pattern.

This module provides flexible tree traversal for AST nodes, supporting both depth-first and breadth-first traversal strategies.

Visitor Pattern

The visitor pattern allows you to define custom behavior for each node type without modifying the node modules themselves.

Examples

# Collect all tokens
iex> visitor = fn
...>   %Nasty.AST.Token{} = token, acc -> {:cont, [token | acc]}
...>   _node, acc -> {:cont, acc}
...> end
iex> Nasty.Utils.Traversal.walk(document, [], visitor)
[token1, token2, ...]

# Find first noun
iex> visitor = fn
...>   %Nasty.AST.Token{pos_tag: :noun} = token, _acc -> {:halt, token}
...>   _node, acc -> {:cont, acc}
...> end
iex> Nasty.Utils.Traversal.walk(document, nil, visitor)
%Nasty.AST.Token{text: "cat", ...}

Summary

Types

visitor(acc)

Visitor function that processes nodes during traversal.

Functions

collect(node, predicate)

Collects all nodes matching a predicate.

find(node, predicate)

Finds the first node matching a predicate.

map(node, mapper)

Maps a function over all nodes, returning a transformed tree.

reduce(node, acc, reducer)

Reduces the AST to a single value.

walk(node, acc, visitor)

Walks the AST using depth-first pre-order traversal.

walk_breadth(node, acc, visitor)

Performs breadth-first traversal of the AST.

walk_post(node, acc, visitor)

Walks the AST using depth-first post-order traversal.

Types

visitor(acc)

@type visitor(acc) :: (term(), acc -> {:cont, acc} | {:halt, term()} | {:skip, acc})

Visitor function that processes nodes during traversal.

The function receives the current node and an accumulator, and returns:

{:cont, new_acc} - Continue traversal with updated accumulator
{:halt, result} - Stop traversal and return result
{:skip, new_acc} - Skip children of this node but continue traversal

Functions

collect(node, predicate)

@spec collect(term(), (term() -> boolean())) :: [term()]

Collects all nodes matching a predicate.

Examples

iex> is_noun? = fn
...>   %Nasty.AST.Token{pos_tag: :noun} -> true
...>   _ -> false
...> end
iex> Nasty.Utils.Traversal.collect(document, is_noun?)
[token1, token2, ...]

find(node, predicate)

@spec find(term(), (term() -> boolean())) :: term() | nil

Finds the first node matching a predicate.

Returns nil if no matching node is found.

Examples

iex> Nasty.Utils.Traversal.find(document, &match?(%Nasty.AST.Token{pos_tag: :verb}, &1))
%Nasty.AST.Token{text: "runs", pos_tag: :verb, ...}

map(node, mapper)

@spec map(term(), (term() -> term())) :: term()

Maps a function over all nodes, returning a transformed tree.

Examples

iex> lowercase = fn
...>   %Nasty.AST.Token{} = token -> %{token | text: String.downcase(token.text)}
...>   node -> node
...> end
iex> Nasty.Utils.Traversal.map(document, lowercase)
%Nasty.AST.Document{...}

reduce(node, acc, reducer)

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

Reduces the AST to a single value.

Similar to Enum.reduce/3 but for tree structures.

Examples

iex> count = fn _node, acc -> acc + 1 end
iex> Nasty.Utils.Traversal.reduce(document, 0, count)
127  # Total number of nodes

walk(node, acc, visitor)

@spec walk(term(), acc, visitor(acc)) :: acc when acc: term()

Walks the AST using depth-first pre-order traversal.

Visits parent nodes before their children.

Examples

iex> count_tokens = fn
...>   %Nasty.AST.Token{}, acc -> {:cont, acc + 1}
...>   _node, acc -> {:cont, acc}
...> end
iex> Nasty.Utils.Traversal.walk(document, 0, count_tokens)
42

walk_breadth(node, acc, visitor)

@spec walk_breadth(term(), acc, visitor(acc)) :: acc when acc: term()

Performs breadth-first traversal of the AST.

Visits all nodes at depth N before visiting nodes at depth N+1.

Examples

iex> visitor = fn node, acc -> {:cont, [node | acc]} end
iex> nodes = Nasty.Utils.Traversal.walk_breadth(document, [], visitor)
iex> Enum.reverse(nodes)
[document, paragraph1, paragraph2, sentence1, sentence2, ...]

walk_post(node, acc, visitor)

@spec walk_post(term(), acc, visitor(acc)) :: acc when acc: term()

Walks the AST using depth-first post-order traversal.

Visits children before their parent nodes.

Examples

iex> collect_depths = fn
...>   %Nasty.AST.Token{}, depth -> {:cont, [depth]}
...>   _node, depths -> {:cont, depths}
...> end
iex> Nasty.Utils.Traversal.walk_post(document, 0, collect_depths)
[3, 3, 2, 3, 3, 2, 1, ...]