or run

npx @tessl/cli init
Log in

Version

Tile

Overview

Evals

Files

docs

ast-parsing.mdast-traversal.mdcopy-paste-detection.mdindex.mdlanguage-module.mdrule-development.md
tile.json

ast-traversal.mddocs/

AST Traversal

AST traversal capabilities provide comprehensive visitor pattern implementation for analyzing Scala abstract syntax trees. The traversal system supports all 140+ AST node types with flexible visitor interfaces and navigation methods.

Core Traversal Components

ScalaNode Interface

Base interface for all Scala AST nodes providing core node functionality.

public interface ScalaNode<T extends Tree> extends GenericNode<ScalaNode<?>> {
    boolean isImplicit();
    T getNode();
}

ScalaVisitor Interface

Primary visitor interface for traversing Scala AST structures with type-safe visitor pattern implementation.

public interface ScalaVisitor<D, R> extends AstVisitor<D, R> {
    default R visit(ScalaNode<?> node, D data);
    default R visit(ASTSource node, D data);
    
    // Declaration nodes
    default R visit(ASTDeclDef node, D data);
    default R visit(ASTDeclType node, D data);
    default R visit(ASTDeclVal node, D data);
    default R visit(ASTDeclVar node, D data);
    
    // Definition nodes  
    default R visit(ASTDefnClass node, D data);
    default R visit(ASTDefnDef node, D data);
    default R visit(ASTDefnMacro node, D data);
    default R visit(ASTDefnObject node, D data);
    default R visit(ASTDefnTrait node, D data);
    default R visit(ASTDefnType node, D data);
    default R visit(ASTDefnVal node, D data);
    default R visit(ASTDefnVar node, D data);
    
    // Term nodes (expressions)
    default R visit(ASTTermApply node, D data);
    default R visit(ASTTermApplyInfix node, D data);
    default R visit(ASTTermApplyType node, D data);
    default R visit(ASTTermApplyUnary node, D data);
    default R visit(ASTTermBlock node, D data);
    default R visit(ASTTermFor node, D data);
    default R visit(ASTTermForYield node, D data);
    default R visit(ASTTermFunction node, D data);
    default R visit(ASTTermIf node, D data);
    default R visit(ASTTermMatch node, D data);
    default R visit(ASTTermName node, D data);
    default R visit(ASTTermNew node, D data);
    default R visit(ASTTermReturn node, D data);
    default R visit(ASTTermSelect node, D data);
    default R visit(ASTTermThis node, D data);
    default R visit(ASTTermTry node, D data);
    default R visit(ASTTermWhile node, D data);
    
    // Pattern nodes
    default R visit(ASTPatAlternative node, D data);
    default R visit(ASTPatBind node, D data);
    default R visit(ASTPatExtract node, D data);
    default R visit(ASTPatTuple node, D data);
    default R visit(ASTPatTyped node, D data);
    default R visit(ASTPatVar node, D data);
    default R visit(ASTPatWildcard node, D data);
    
    // Type nodes
    default R visit(ASTTypeApply node, D data);
    default R visit(ASTTypeFunction node, D data);
    default R visit(ASTTypeName node, D data);
    default R visit(ASTTypeParam node, D data);
    default R visit(ASTTypeTuple node, D data);
    
    // Literal nodes
    default R visit(ASTLitBoolean node, D data);
    default R visit(ASTLitByte node, D data);
    default R visit(ASTLitChar node, D data);
    default R visit(ASTLitDouble node, D data);
    default R visit(ASTLitFloat node, D data);
    default R visit(ASTLitInt node, D data);
    default R visit(ASTLitLong node, D data);
    default R visit(ASTLitString node, D data);
    default R visit(ASTLitNull node, D data);
    default R visit(ASTLitUnit node, D data);
    
    // Modifier nodes
    default R visit(ASTModAbstract node, D data);
    default R visit(ASTModCase node, D data);
    default R visit(ASTModFinal node, D data);
    default R visit(ASTModImplicit node, D data);
    default R visit(ASTModOverride node, D data);
    default R visit(ASTModPrivate node, D data);
    default R visit(ASTModProtected node, D data);
    default R visit(ASTModSealed node, D data);
    
    // Package and import nodes
    default R visit(ASTPkg node, D data);
    default R visit(ASTImport node, D data);
    default R visit(ASTImporter node, D data);
    
    // Template and constructor nodes
    default R visit(ASTTemplate node, D data);
    default R visit(ASTCtorPrimary node, D data);
    default R visit(ASTCtorSecondary node, D data);
    
    // Case and enumerator nodes
    default R visit(ASTCase node, D data);
    default R visit(ASTEnumeratorGenerator node, D data);
    default R visit(ASTEnumeratorGuard node, D data);
    default R visit(ASTEnumeratorVal node, D data);
    
    // Additional node types (140+ total)
    // ... many more visit methods for complete coverage
}

Usage Example:

// Create custom visitor for analysis
public class ScalaCodeAnalyzer implements ScalaVisitor<Void, Integer> {
    private int classCount = 0;
    private int methodCount = 0;
    
    @Override
    public Integer visit(ASTDefnClass node, Void data) {
        classCount++;
        System.out.println("Found class: " + node.getText());
        
        // Continue traversal to child nodes
        return visitChildren(node, data);
    }
    
    @Override  
    public Integer visit(ASTDefnDef node, Void data) {
        methodCount++;
        System.out.println("Found method: " + node.getText());
        return visitChildren(node, data);
    }
    
    public void printStats() {
        System.out.println("Classes: " + classCount + ", Methods: " + methodCount);
    }
}

// Use the visitor
ScalaCodeAnalyzer analyzer = new ScalaCodeAnalyzer();
ast.acceptVisitor(analyzer, null);
analyzer.printStats();

Node Navigation Methods

Descendant and Ancestor Navigation

All AST nodes provide methods for navigating the tree structure:

public abstract class AbstractScalaNode<T extends Tree> {
    // Navigate to descendants of specific types
    public <T extends Node> NodeStream<T> descendants(Class<T> nodeType);
    public NodeStream<? extends Node> descendants();
    
    // Navigate to children
    public NodeStream<? extends ScalaNode<?>> children();
    public <T extends Node> NodeStream<T> children(Class<T> nodeType);
    
    // Navigate to ancestors
    public NodeStream<? extends Node> ancestors();
    public <T extends Node> NodeStream<T> ancestors(Class<T> nodeType);
    
    // Navigate to siblings
    public NodeStream<? extends Node> followingSiblings();
    public NodeStream<? extends Node> precedingSiblings();
    
    // Get parent nodes
    public ScalaNode<?> getParent();
    public <T extends Node> T getFirstParentOfType(Class<T> nodeType);
}

Usage Examples:

// Find all string literals in an AST
ast.descendants(ASTLitString.class).forEach(literal -> {
    System.out.println("String: " + literal.getText());
});

// Find all method calls within a specific class
classNode.descendants(ASTTermApply.class).forEach(call -> {
    System.out.println("Method call: " + call.getText());
});

// Navigate up the tree to find containing class
ASTDefnClass containingClass = methodNode.getFirstParentOfType(ASTDefnClass.class);
if (containingClass != null) {
    System.out.println("Method is in class: " + containingClass.getText());
}

// Find sibling methods in a class
methodNode.followingSiblings(ASTDefnDef.class).forEach(sibling -> {
    System.out.println("Sibling method: " + sibling.getText());
});

Tree Structure Analysis

// Tree structure methods
public abstract class AbstractScalaNode<T extends Tree> {
    public int getNumChildren();
    public ScalaNode<?> getChild(int index);
    public int getIndexInParent();
    
    // Tree depth and position
    public int getDepth();
    public boolean isAncestorOf(Node other);
    public boolean isDescendantOf(Node other);
    
    // Text and location methods
    public String getText();
    public TextRegion getTextRegion();
    public int getBeginLine();
    public int getBeginColumn();
    public int getEndLine();
    public int getEndColumn();
}

Usage Example:

// Analyze tree structure
public void analyzeNodeStructure(ScalaNode<?> node) {
    System.out.println("Node: " + node.getClass().getSimpleName());
    System.out.println("Children: " + node.getNumChildren());
    System.out.println("Depth: " + node.getDepth());
    System.out.println("Location: " + node.getBeginLine() + ":" + node.getBeginColumn());
    
    // Check for specific relationships
    if (node instanceof ASTDefnDef) {
        ASTDefnClass parentClass = node.getFirstParentOfType(ASTDefnClass.class);
        if (parentClass != null) {
            System.out.println("Method belongs to class: " + parentClass.getText());
        }
    }
}

Specialized Traversal Patterns

Pattern Matching Analysis

// Visitor for analyzing pattern matching constructs
public class PatternMatchAnalyzer implements ScalaVisitor<Void, Void> {
    @Override
    public Void visit(ASTTermMatch node, Void data) {
        System.out.println("Match expression at line " + node.getBeginLine());
        
        // Analyze each case clause
        node.descendants(ASTCase.class).forEach(caseNode -> {
            System.out.println("  Case: " + caseNode.getText());
            
            // Analyze patterns within case
            caseNode.descendants(ASTPatVar.class).forEach(pattern -> {
                System.out.println("    Pattern variable: " + pattern.getText());
            });
        });
        
        return visitChildren(node, data);
    }
    
    @Override
    public Void visit(ASTCase node, Void data) {
        // Individual case analysis
        return visitChildren(node, data);
    }
}

Type System Traversal

// Analyze type-related constructs
public class TypeAnalyzer implements ScalaVisitor<Set<String>, Set<String>> {
    @Override
    public Set<String> visit(ASTTypeApply node, Set<String> data) {
        data.add("Type application: " + node.getText());
        return visitChildren(node, data);
    }
    
    @Override
    public Set<String> visit(ASTTypeFunction node, Set<String> data) {
        data.add("Function type: " + node.getText());
        return visitChildren(node, data);
    }
    
    @Override
    public Set<String> visit(ASTDefnClass node, Set<String> data) {
        // Analyze class type parameters
        node.descendants(ASTTypeParam.class).forEach(param -> {
            data.add("Type parameter: " + param.getText());
        });
        return visitChildren(node, data);
    }
}

// Usage
Set<String> typeInfo = new HashSet<>();
TypeAnalyzer analyzer = new TypeAnalyzer();
ast.acceptVisitor(analyzer, typeInfo);
typeInfo.forEach(System.out::println);

Import and Package Traversal

// Analyze imports and package structure
public class ImportAnalyzer implements ScalaVisitor<List<String>, List<String>> {
    @Override
    public List<String> visit(ASTImport node, List<String> data) {
        data.add("Import statement: " + node.getText());
        
        // Analyze specific importers
        node.descendants(ASTImporter.class).forEach(importer -> {
            data.add("  Importing: " + importer.getText());
            
            // Check for wildcard imports
            if (importer.descendants(ASTImporteeWildcard.class).count() > 0) {
                data.add("    (wildcard import)");
            }
            
            // Check for renamed imports
            importer.descendants(ASTImporteeRename.class).forEach(rename -> {
                data.add("    Rename: " + rename.getText());
            });
        });
        
        return visitChildren(node, data);
    }
    
    @Override
    public List<String> visit(ASTPkg node, List<String> data) {
        data.add("Package: " + node.getText());
        return visitChildren(node, data);
    }
}

Advanced Traversal Techniques

Conditional Traversal

// Skip certain subtrees based on conditions
public class ConditionalVisitor implements ScalaVisitor<Boolean, Integer> {
    @Override
    public Integer visit(ASTDefnClass node, Boolean skipInnerClasses) {
        System.out.println("Processing class: " + node.getText());
        
        if (skipInnerClasses) {
            // Process this class but don't traverse inner classes
            node.children().filter(child -> !(child instanceof ASTDefnClass))
                .forEach(child -> child.acceptVisitor(this, false));
            return 1; // Return without calling visitChildren
        } else {
            return visitChildren(node, skipInnerClasses);
        }
    }
}

State-Based Traversal

// Maintain context state during traversal
public class ContextTracker implements ScalaVisitor<Map<String, Object>, Void> {
    @Override
    public Void visit(ASTDefnClass node, Map<String, Object> context) {
        // Push class context
        String previousClass = (String) context.get("currentClass");
        context.put("currentClass", node.getText());
        context.put("classDepth", (Integer) context.getOrDefault("classDepth", 0) + 1);
        
        // Process children with updated context
        Void result = visitChildren(node, context);
        
        // Pop class context
        context.put("currentClass", previousClass);
        context.put("classDepth", (Integer) context.get("classDepth") - 1);
        
        return result;
    }
    
    @Override
    public Void visit(ASTDefnDef node, Map<String, Object> context) {
        String currentClass = (String) context.get("currentClass");
        Integer depth = (Integer) context.get("classDepth");
        
        System.out.println("Method " + node.getText() + 
                          " in class " + currentClass + 
                          " at depth " + depth);
        
        return visitChildren(node, context);
    }
}

Performance Considerations

Efficient Node Filtering

// Use streaming API for efficient traversal
ast.descendants(ASTDefnDef.class)
   .filter(method -> method.getText().contains("test"))
   .limit(10)
   .forEach(testMethod -> processTestMethod(testMethod));

// Combine multiple node types efficiently  
ast.descendants()
   .filter(node -> node instanceof ASTDefnClass || node instanceof ASTDefnObject)
   .forEach(definition -> processDefinition(definition));

Memory-Efficient Traversal

// Process nodes without storing references
public class StreamingProcessor implements ScalaVisitor<Void, Void> {
    @Override
    public Void visit(ASTLitString node, Void data) {
        // Process immediately without storage
        processStringLiteral(node.getText());
        return null; // Don't continue traversal for literals
    }
    
    private void processStringLiteral(String literal) {
        // Immediate processing
        System.out.println("Processing: " + literal);
    }
}

Integration with Rule Development

The traversal system integrates seamlessly with PMD's rule development framework:

// Rule using visitor pattern
public class CustomScalaRule extends ScalaRule {
    @Override
    public RuleContext visit(ASTDefnClass node, RuleContext ctx) {
        // Rule-specific traversal logic
        analyzeClassStructure(node, ctx);
        return super.visit(node, ctx);
    }
    
    private void analyzeClassStructure(ASTDefnClass classNode, RuleContext ctx) {
        // Use traversal methods for rule implementation
        long methodCount = classNode.descendants(ASTDefnDef.class).count();
        if (methodCount > 20) {
            ctx.addViolation(classNode, "Class has too many methods: " + methodCount);
        }
    }
}

This traversal system provides the foundation for comprehensive Scala code analysis, enabling sophisticated static analysis rules and code quality checks.