Tree Walking

class NodeWalker:
    """
    Base tree walker with method dispatch.
    
    Features:
    - Automatic method dispatch based on node types
    - Flexible visiting patterns
    - Extensible for custom node types
    - Exception handling during traversal
    """
    
    def walk(self, node):
        """
        Walk a parse tree starting from the given node.
        
        Parameters:
        - node: Root node to start walking from
        
        Returns:
        Result of walking the tree (implementation dependent)
        """
    
    def walk_children(self, node):
        """
        Walk all children of the current node.
        
        Parameters:
        - node: Parent node whose children to walk
        
        Returns:
        List of results from walking each child
        """
    
    def _find_walker(self, node):
        """
        Find appropriate walker method for a node type.
        
        Parameters:
        - node: Node to find walker for
        
        Returns:
        Method: Walker method for the node type
        """

import tatsu
from tatsu.walkers import NodeWalker
from tatsu.semantics import ModelBuilderSemantics

grammar = '''
    expr = term ("+" term)*;
    term = factor ("*" factor)*;
    factor = "(" expr ")" | number;
    number = /\d+/;
'''

class ExpressionWalker(NodeWalker):
    """Walk expression trees and collect information."""
    
    def walk_expr(self, node):
        """Handle expression nodes."""
        print(f"Found expression: {node}")
        return self.walk_children(node)
    
    def walk_term(self, node):
        """Handle term nodes."""
        print(f"Found term: {node}")
        return self.walk_children(node)
    
    def walk_number(self, node):
        """Handle number nodes."""
        print(f"Found number: {node}")
        return int(str(node))

# Usage
model = tatsu.compile(grammar)
ast = model.parse("2 + 3 * 4", semantics=ModelBuilderSemantics())

walker = ExpressionWalker()
result = walker.walk(ast)

class PreOrderWalker(NodeWalker):
    """
    Pre-order tree traversal walker.
    
    Visits parent nodes before their children, making it suitable for:
    - Top-down analysis
    - Code generation with forward declarations
    - Dependency resolution
    - Symbol table construction
    """

from tatsu.walkers import PreOrderWalker

class CodeGenerator(PreOrderWalker):
    """Generate code using pre-order traversal."""
    
    def __init__(self):
        self.code = []
        self.indent_level = 0
    
    def walk_function_def(self, node):
        """Generate function definition."""
        self.emit(f"def {node.name}({', '.join(node.params)}):")
        self.indent_level += 1
        
        # Walk children (function body)
        self.walk_children(node)
        
        self.indent_level -= 1
        return node
    
    def walk_assignment(self, node):
        """Generate assignment statement.""" 
        self.emit(f"{node.target} = {self.evaluate_expr(node.value)}")
        return node
    
    def emit(self, code):
        """Emit code with proper indentation."""
        indent = "    " * self.indent_level
        self.code.append(f"{indent}{code}")
    
    def get_code(self):
        """Get generated code as string."""
        return "\n".join(self.code)

# Usage
generator = CodeGenerator()
generator.walk(ast)
print(generator.get_code())

class DepthFirstWalker(NodeWalker):
    """
    Depth-first tree traversal walker.
    
    Visits child nodes before their parents, making it suitable for:
    - Bottom-up evaluation
    - Type inference
    - Optimization passes
    - Dependency analysis
    - Post-order processing
    """

from tatsu.walkers import DepthFirstWalker

class ExpressionEvaluator(DepthFirstWalker):
    """Evaluate arithmetic expressions using depth-first traversal."""
    
    def walk_number(self, node):
        """Evaluate number literals."""
        return int(str(node))
    
    def walk_binary_op(self, node):
        """Evaluate binary operations."""
        # Children are evaluated first (depth-first)
        left = self.walk(node.left)
        right = self.walk(node.right)
        
        if node.operator == '+':
            return left + right
        elif node.operator == '*':
            return left * right
        elif node.operator == '-':
            return left - right
        elif node.operator == '/':
            return left / right
        else:
            raise ValueError(f"Unknown operator: {node.operator}")
    
    def walk_expr(self, node):
        """Handle expression nodes."""
        if hasattr(node, 'terms'):
            result = self.walk(node.terms[0]) 
            for i in range(1, len(node.terms), 2):
                op = node.terms[i]
                operand = self.walk(node.terms[i + 1])
                if op == '+':
                    result += operand
                elif op == '-':
                    result -= operand
            return result
        return self.walk_children(node)

# Usage
evaluator = ExpressionEvaluator()
result = evaluator.walk(ast)
print(f"Expression evaluates to: {result}")

class ContextWalker(NodeWalker):
    """
    Context-aware tree walking with stack management.
    
    Features:
    - Context stack management
    - Scope tracking
    - State preservation across traversal
    - Environment and symbol table support
    """
    
    def get_node_context(self, node):
        """
        Get context information for a specific node.
        
        Parameters:
        - node: Node to get context for
        
        Returns:
        Context information for the node
        """
    
    def enter_context(self, context):
        """
        Enter a new context scope.
        
        Parameters:
        - context: Context object to enter
        """
    
    def leave_context(self):
        """
        Leave the current context scope.
        
        Returns:
        Previous context that was left
        """
    
    def push_context(self, context):
        """
        Push context onto the context stack.
        
        Parameters:
        - context: Context to push
        """
    
    def pop_context(self):
        """
        Pop context from the context stack.
        
        Returns:
        Context that was popped
        """

from tatsu.walkers import ContextWalker

class SymbolTableWalker(ContextWalker):
    """Build symbol table with scope awareness."""
    
    def __init__(self):
        super().__init__()
        self.scopes = [{}]  # Stack of symbol tables
        self.current_scope = self.scopes[-1]
    
    def enter_scope(self):
        """Enter a new lexical scope."""
        new_scope = {}
        self.scopes.append(new_scope)
        self.current_scope = new_scope
    
    def leave_scope(self):
        """Leave current lexical scope."""
        if len(self.scopes) > 1:
            self.scopes.pop()
            self.current_scope = self.scopes[-1]
    
    def walk_function_def(self, node):
        """Handle function definitions with new scope."""
        # Add function to current scope
        self.current_scope[node.name] = {
            'type': 'function',
            'params': node.params,
            'node': node
        }
        
        # Enter function scope for parameters and body
        self.enter_scope()
        
        # Add parameters to function scope
        for param in node.params:
            self.current_scope[param] = {
                'type': 'parameter', 
                'node': node
            }
        
        # Walk function body
        self.walk_children(node.body)
        
        # Leave function scope
        self.leave_scope()
        
        return node
    
    def walk_variable_ref(self, node):
        """Handle variable references with scope resolution."""
        var_name = str(node)
        
        # Search scopes from innermost to outermost
        for scope in reversed(self.scopes):
            if var_name in scope:
                return scope[var_name]
        
        # Variable not found in any scope
        raise NameError(f"Undefined variable: {var_name}")
    
    def walk_assignment(self, node):
        """Handle variable assignments."""
        var_name = str(node.target)
        
        # Walk the value expression first
        value_info = self.walk(node.value)
        
        # Add variable to current scope
        self.current_scope[var_name] = {
            'type': 'variable',
            'value': value_info,
            'node': node
        }
        
        return node

# Usage
symbol_walker = SymbolTableWalker()
symbol_walker.walk(ast)

# Access symbol table
print("Global scope:", symbol_walker.scopes[0])

class MultiPassWalker(NodeWalker):
    """Walker that makes multiple passes over the tree."""
    
    def __init__(self, passes):
        """
        Initialize multi-pass walker.
        
        Parameters:
        - passes: List of pass functions to execute
        """
        self.passes = passes
        self.current_pass = 0
    
    def walk_multi_pass(self, node):
        """Execute all passes on the tree."""
        results = []
        for i, pass_func in enumerate(self.passes):
            self.current_pass = i
            result = pass_func(node)
            results.append(result)
        return results

class CollectingWalker(NodeWalker):
    """Walker that collects nodes matching specific criteria."""
    
    def __init__(self, predicate):
        """
        Initialize collecting walker.
        
        Parameters:
        - predicate: Function that returns True for nodes to collect
        """
        self.predicate = predicate
        self.collected = []
    
    def walk(self, node):
        """Walk tree and collect matching nodes."""
        if self.predicate(node):
            self.collected.append(node)
        
        return self.walk_children(node)
    
    def get_collected(self):
        """Get list of collected nodes."""
        return self.collected

class TransformingWalker(NodeWalker):
    """Walker that transforms the tree structure."""
    
    def walk(self, node):
        """Walk and transform nodes."""
        # Transform current node
        transformed = self.transform_node(node)
        
        # Transform children
        if hasattr(transformed, 'children'):
            new_children = []
            for child in transformed.children():
                new_child = self.walk(child)
                new_children.append(new_child)
            transformed.set_children(new_children)
        
        return transformed
    
    def transform_node(self, node):
        """Override to implement node transformation."""
        return node

# Usage examples
def is_number_node(node):
    return hasattr(node, '__class__') and 'number' in node.__class__.__name__.lower()

# Collect all number nodes
collector = CollectingWalker(is_number_node)
collector.walk(ast)
numbers = collector.get_collected()
print(f"Found {len(numbers)} number nodes")

# Multi-pass analysis
def pass1_collect_functions(ast):
    """First pass: collect function definitions."""
    # Implementation here
    pass

def pass2_resolve_calls(ast):
    """Second pass: resolve function calls."""
    # Implementation here  
    pass

multi_walker = MultiPassWalker([pass1_collect_functions, pass2_resolve_calls])
results = multi_walker.walk_multi_pass(ast)

class SafeWalker(NodeWalker):
    """Walker with comprehensive error handling."""
    
    def __init__(self):
        self.errors = []
        self.warnings = []
    
    def walk(self, node):
        """Walk with error handling."""
        try:
            return super().walk(node)
        except Exception as e:
            self.errors.append({
                'node': node,
                'error': e,
                'message': str(e)
            })
            return None  # Continue walking despite errors
    
    def walk_children(self, node):
        """Walk children with individual error handling."""
        results = []
        for child in getattr(node, 'children', lambda: [])():
            try:
                result = self.walk(child)
                results.append(result)
            except Exception as e:
                self.warnings.append({
                    'parent': node,
                    'child': child,
                    'error': e
                })
                # Continue with other children
        return results
    
    def has_errors(self):
        """Check if any errors occurred during walking."""
        return len(self.errors) > 0
    
    def get_error_report(self):
        """Get detailed error report."""
        report = []
        for error in self.errors:
            report.append(f"Error at {error['node']}: {error['message']}")
        for warning in self.warnings:
            report.append(f"Warning at {warning['parent']}: {warning['error']}")
        return "\n".join(report)

# Usage with error handling
safe_walker = SafeWalker()
result = safe_walker.walk(ast)

if safe_walker.has_errors():
    print("Errors occurred during walking:")
    print(safe_walker.get_error_report())
else:
    print("Walking completed successfully")