TreeWalker

TreeWalker

The TreeWalker provides DOM-style filtered tree traversal similar to the W3C DOM TreeWalker specification.

Basic Usage

using TinyTokenizer.Ast;

var tree = SyntaxTree.Parse("foo { bar(x) }");

// Create walker from tree
var walker = tree.CreateTreeWalker();

// Or from a specific node
var walker = new TreeWalker(tree.Root);

// Enumerate all descendants
foreach (var node in walker.DescendantsAndSelf())
{
    Console.WriteLine($"{node.Kind} at {node.Position}");
}

NodeFilter Flags

Filter which node types the walker visits:

// Only leaf nodes
var leafWalker = new TreeWalker(tree.Root, NodeFilter.Leaves);

// Only block nodes
var blockWalker = new TreeWalker(tree.Root, NodeFilter.Blocks);

// All nodes (default)
var allWalker = new TreeWalker(tree.Root, NodeFilter.All);

// Combine flags
var walker = new TreeWalker(tree.Root, NodeFilter.Leaves | NodeFilter.Blocks);

Flag	Description
NodeFilter.All	All node types
NodeFilter.Leaves	Only leaf nodes (identifiers, operators, etc.)
NodeFilter.Blocks	Only block nodes ({ }, [ ], ( ))

Custom Filter Functions

Use FilterResult for fine-grained control:

var walker = new TreeWalker(
    tree.Root,
    NodeFilter.All,
    node => node.Kind == NodeKind.Ident
        ? FilterResult.Accept    // Include this node
        : FilterResult.Skip);    // Skip node, check children

var idents = walker.DescendantsAndSelf().ToList();

FilterResult Values

Value	Behavior
FilterResult.Accept	Include this node in results
FilterResult.Reject	Exclude this node and its entire subtree
FilterResult.Skip	Exclude this node but still visit children

Filter Examples

// Only identifiers longer than 3 characters
var walker = new TreeWalker(tree.Root, NodeFilter.Leaves, node =>
{
    if (node is SyntaxToken leaf && leaf.Kind == NodeKind.Ident && leaf.Width > 3)
        return FilterResult.Accept;
    return FilterResult.Skip;
});

// Skip entire comment blocks
var walker = new TreeWalker(tree.Root, NodeFilter.All, node =>
{
    if (node.Kind == NodeKind.Comment)
        return FilterResult.Reject;  // Skip node AND children
    return FilterResult.Accept;
});

Enumeration Methods

DescendantsAndSelf

Enumerate current node and all descendants (depth-first):

foreach (var node in walker.DescendantsAndSelf())
{
    Console.WriteLine(node.Kind);
}

Descendants

Enumerate all descendants (excluding self):

foreach (var node in walker.Descendants())
{
    // Process descendants only
}

Ancestors

Enumerate ancestors from parent to root:

var leaf = tree.Leaves.First();
var walker = new TreeWalker(leaf);

foreach (var ancestor in walker.Ancestors())
{
    Console.WriteLine($"Ancestor: {ancestor.Kind}");
}

FollowingSiblings

Enumerate siblings after the current node:

foreach (var sibling in walker.FollowingSiblings())
{
    // Process following siblings
}

PrecedingSiblings

Enumerate siblings before the current node:

foreach (var sibling in walker.PrecedingSiblings())
{
    // Process preceding siblings
}

Cursor Navigation

Navigate manually using cursor methods:

var walker = new TreeWalker(tree.Root);

// Move to first child
SyntaxNode? first = walker.FirstChild();

// Move to next sibling
SyntaxNode? next = walker.NextSibling();

// Move to parent
SyntaxNode? parent = walker.ParentNode();

// Move to last child
SyntaxNode? last = walker.LastChild();

// Move to previous sibling
SyntaxNode? prev = walker.PreviousSibling();

Cursor Example

var walker = new TreeWalker(tree.Root);

// Navigate to first identifier
var current = walker.FirstChild();
while (current != null && current.Kind != NodeKind.Ident)
{
    current = walker.NextNode();
}

if (current != null)
{
    Console.WriteLine($"First ident: {((SyntaxToken)current).Text}");
}

NextNode / PreviousNode

Sequential traversal through the entire tree:

var walker = new TreeWalker(tree.Root);

// Forward traversal
SyntaxNode? node = walker.CurrentNode;
while (node != null)
{
    Console.WriteLine(node.Kind);
    node = walker.NextNode();
}

// Backward traversal
node = walker.CurrentNode;
while (node != null)
{
    Console.WriteLine(node.Kind);
    node = walker.PreviousNode();
}

Current Node

Access and set the walker's current position:

var walker = new TreeWalker(tree.Root);

// Get current position
SyntaxNode current = walker.CurrentNode;

// Set current position (must be within original root's subtree)
walker.CurrentNode = someOtherNode;

Practical Examples

Find All Functions

var tree = SyntaxTree.Parse("foo(x) + bar(y)");
var walker = new TreeWalker(tree.Root, NodeFilter.Leaves, node =>
{
    if (node is SyntaxToken leaf && leaf.Kind == NodeKind.Ident)
    {
        // Check if followed by paren block
        var next = leaf.NextSibling();
        if (next?.Kind == NodeKind.ParenBlock)
            return FilterResult.Accept;
    }
    return FilterResult.Skip;
});

foreach (var funcName in walker.DescendantsAndSelf())  // [Ident("foo"), Ident("bar")]
{
    Console.WriteLine($"Function: {((SyntaxToken)funcName).Text}");
}
// Output:
// Function: foo
// Function: bar

Collect Nested Blocks

var tree = SyntaxTree.Parse("if { outer { inner } }");
var walker = new TreeWalker(tree.Root, NodeFilter.Blocks);
var blocks = walker.DescendantsAndSelf()  // [Block("{ outer { inner } }"), Block("{ inner }")]
    .Cast<SyntaxBlock>()
    .Where(b => b.Kind == NodeKind.BraceBlock)
    .ToList();

Console.WriteLine($"Found {blocks.Count} brace blocks");  // "Found 2 brace blocks"

Skip Specific Subtrees

// Walk tree but skip contents of string literals
var walker = new TreeWalker(tree.Root, NodeFilter.All, node =>
{
    if (node.Kind == NodeKind.String)
        return FilterResult.Reject;  // Don't descend into strings
    return FilterResult.Accept;
});

Comparison with Query API

Feature	TreeWalker	Query API
Use case	Low-level traversal	Pattern matching
Filtering	FilterResult callbacks	Declarative combinators
Navigation	Cursor-based	Selector-based
Flexibility	Maximum control	Concise patterns
Best for	Custom traversal logic	Finding specific patterns

Use TreeWalker when you need fine-grained traversal control. Use Query API for pattern-based node selection.

See Also

• Query API — Declarative node selection
• TinyAst Guide — Syntax tree basics
• Trivia — Whitespace handling during traversal