0
# AST Traversal
1

2
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.
3

4
## Core Traversal Components
5

6
### ScalaNode Interface
7

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

10
```java { .api }
11
public interface ScalaNode<T extends Tree> extends GenericNode<ScalaNode<?>> {
12
    boolean isImplicit();
13
    T getNode();
14
}
15
```
16

17
### ScalaVisitor Interface
18

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

21
```java { .api }
22
public interface ScalaVisitor<D, R> extends AstVisitor<D, R> {
23
    default R visit(ScalaNode<?> node, D data);
24
    default R visit(ASTSource node, D data);
25
    
26
    // Declaration nodes
27
    default R visit(ASTDeclDef node, D data);
28
    default R visit(ASTDeclType node, D data);
29
    default R visit(ASTDeclVal node, D data);
30
    default R visit(ASTDeclVar node, D data);
31
    
32
    // Definition nodes  
33
    default R visit(ASTDefnClass node, D data);
34
    default R visit(ASTDefnDef node, D data);
35
    default R visit(ASTDefnMacro node, D data);
36
    default R visit(ASTDefnObject node, D data);
37
    default R visit(ASTDefnTrait node, D data);
38
    default R visit(ASTDefnType node, D data);
39
    default R visit(ASTDefnVal node, D data);
40
    default R visit(ASTDefnVar node, D data);
41
    
42
    // Term nodes (expressions)
43
    default R visit(ASTTermApply node, D data);
44
    default R visit(ASTTermApplyInfix node, D data);
45
    default R visit(ASTTermApplyType node, D data);
46
    default R visit(ASTTermApplyUnary node, D data);
47
    default R visit(ASTTermBlock node, D data);
48
    default R visit(ASTTermFor node, D data);
49
    default R visit(ASTTermForYield node, D data);
50
    default R visit(ASTTermFunction node, D data);
51
    default R visit(ASTTermIf node, D data);
52
    default R visit(ASTTermMatch node, D data);
53
    default R visit(ASTTermName node, D data);
54
    default R visit(ASTTermNew node, D data);
55
    default R visit(ASTTermReturn node, D data);
56
    default R visit(ASTTermSelect node, D data);
57
    default R visit(ASTTermThis node, D data);
58
    default R visit(ASTTermTry node, D data);
59
    default R visit(ASTTermWhile node, D data);
60
    
61
    // Pattern nodes
62
    default R visit(ASTPatAlternative node, D data);
63
    default R visit(ASTPatBind node, D data);
64
    default R visit(ASTPatExtract node, D data);
65
    default R visit(ASTPatTuple node, D data);
66
    default R visit(ASTPatTyped node, D data);
67
    default R visit(ASTPatVar node, D data);
68
    default R visit(ASTPatWildcard node, D data);
69
    
70
    // Type nodes
71
    default R visit(ASTTypeApply node, D data);
72
    default R visit(ASTTypeFunction node, D data);
73
    default R visit(ASTTypeName node, D data);
74
    default R visit(ASTTypeParam node, D data);
75
    default R visit(ASTTypeTuple node, D data);
76
    
77
    // Literal nodes
78
    default R visit(ASTLitBoolean node, D data);
79
    default R visit(ASTLitByte node, D data);
80
    default R visit(ASTLitChar node, D data);
81
    default R visit(ASTLitDouble node, D data);
82
    default R visit(ASTLitFloat node, D data);
83
    default R visit(ASTLitInt node, D data);
84
    default R visit(ASTLitLong node, D data);
85
    default R visit(ASTLitString node, D data);
86
    default R visit(ASTLitNull node, D data);
87
    default R visit(ASTLitUnit node, D data);
88
    
89
    // Modifier nodes
90
    default R visit(ASTModAbstract node, D data);
91
    default R visit(ASTModCase node, D data);
92
    default R visit(ASTModFinal node, D data);
93
    default R visit(ASTModImplicit node, D data);
94
    default R visit(ASTModOverride node, D data);
95
    default R visit(ASTModPrivate node, D data);
96
    default R visit(ASTModProtected node, D data);
97
    default R visit(ASTModSealed node, D data);
98
    
99
    // Package and import nodes
100
    default R visit(ASTPkg node, D data);
101
    default R visit(ASTImport node, D data);
102
    default R visit(ASTImporter node, D data);
103
    
104
    // Template and constructor nodes
105
    default R visit(ASTTemplate node, D data);
106
    default R visit(ASTCtorPrimary node, D data);
107
    default R visit(ASTCtorSecondary node, D data);
108
    
109
    // Case and enumerator nodes
110
    default R visit(ASTCase node, D data);
111
    default R visit(ASTEnumeratorGenerator node, D data);
112
    default R visit(ASTEnumeratorGuard node, D data);
113
    default R visit(ASTEnumeratorVal node, D data);
114
    
115
    // Additional node types (140+ total)
116
    // ... many more visit methods for complete coverage
117
}
118
```
119

120
**Usage Example**:
121

122
```java
123
// Create custom visitor for analysis
124
public class ScalaCodeAnalyzer implements ScalaVisitor<Void, Integer> {
125
    private int classCount = 0;
126
    private int methodCount = 0;
127
    
128
    @Override
129
    public Integer visit(ASTDefnClass node, Void data) {
130
        classCount++;
131
        System.out.println("Found class: " + node.getText());
132
        
133
        // Continue traversal to child nodes
134
        return visitChildren(node, data);
135
    }
136
    
137
    @Override  
138
    public Integer visit(ASTDefnDef node, Void data) {
139
        methodCount++;
140
        System.out.println("Found method: " + node.getText());
141
        return visitChildren(node, data);
142
    }
143
    
144
    public void printStats() {
145
        System.out.println("Classes: " + classCount + ", Methods: " + methodCount);
146
    }
147
}
148

149
// Use the visitor
150
ScalaCodeAnalyzer analyzer = new ScalaCodeAnalyzer();
151
ast.acceptVisitor(analyzer, null);
152
analyzer.printStats();
153
```
154

155
## Node Navigation Methods
156

157
### Descendant and Ancestor Navigation
158

159
All AST nodes provide methods for navigating the tree structure:
160

161
```java { .api }
162
public abstract class AbstractScalaNode<T extends Tree> {
163
    // Navigate to descendants of specific types
164
    public <T extends Node> NodeStream<T> descendants(Class<T> nodeType);
165
    public NodeStream<? extends Node> descendants();
166
    
167
    // Navigate to children
168
    public NodeStream<? extends ScalaNode<?>> children();
169
    public <T extends Node> NodeStream<T> children(Class<T> nodeType);
170
    
171
    // Navigate to ancestors
172
    public NodeStream<? extends Node> ancestors();
173
    public <T extends Node> NodeStream<T> ancestors(Class<T> nodeType);
174
    
175
    // Navigate to siblings
176
    public NodeStream<? extends Node> followingSiblings();
177
    public NodeStream<? extends Node> precedingSiblings();
178
    
179
    // Get parent nodes
180
    public ScalaNode<?> getParent();
181
    public <T extends Node> T getFirstParentOfType(Class<T> nodeType);
182
}
183
```
184

185
**Usage Examples**:
186

187
```java
188
// Find all string literals in an AST
189
ast.descendants(ASTLitString.class).forEach(literal -> {
190
    System.out.println("String: " + literal.getText());
191
});
192

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

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

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

210
### Tree Structure Analysis
211

212
```java { .api }
213
// Tree structure methods
214
public abstract class AbstractScalaNode<T extends Tree> {
215
    public int getNumChildren();
216
    public ScalaNode<?> getChild(int index);
217
    public int getIndexInParent();
218
    
219
    // Tree depth and position
220
    public int getDepth();
221
    public boolean isAncestorOf(Node other);
222
    public boolean isDescendantOf(Node other);
223
    
224
    // Text and location methods
225
    public String getText();
226
    public TextRegion getTextRegion();
227
    public int getBeginLine();
228
    public int getBeginColumn();
229
    public int getEndLine();
230
    public int getEndColumn();
231
}
232
```
233

234
**Usage Example**:
235

236
```java
237
// Analyze tree structure
238
public void analyzeNodeStructure(ScalaNode<?> node) {
239
    System.out.println("Node: " + node.getClass().getSimpleName());
240
    System.out.println("Children: " + node.getNumChildren());
241
    System.out.println("Depth: " + node.getDepth());
242
    System.out.println("Location: " + node.getBeginLine() + ":" + node.getBeginColumn());
243
    
244
    // Check for specific relationships
245
    if (node instanceof ASTDefnDef) {
246
        ASTDefnClass parentClass = node.getFirstParentOfType(ASTDefnClass.class);
247
        if (parentClass != null) {
248
            System.out.println("Method belongs to class: " + parentClass.getText());
249
        }
250
    }
251
}
252
```
253

254
## Specialized Traversal Patterns
255

256
### Pattern Matching Analysis
257

258
```java
259
// Visitor for analyzing pattern matching constructs
260
public class PatternMatchAnalyzer implements ScalaVisitor<Void, Void> {
261
    @Override
262
    public Void visit(ASTTermMatch node, Void data) {
263
        System.out.println("Match expression at line " + node.getBeginLine());
264
        
265
        // Analyze each case clause
266
        node.descendants(ASTCase.class).forEach(caseNode -> {
267
            System.out.println("  Case: " + caseNode.getText());
268
            
269
            // Analyze patterns within case
270
            caseNode.descendants(ASTPatVar.class).forEach(pattern -> {
271
                System.out.println("    Pattern variable: " + pattern.getText());
272
            });
273
        });
274
        
275
        return visitChildren(node, data);
276
    }
277
    
278
    @Override
279
    public Void visit(ASTCase node, Void data) {
280
        // Individual case analysis
281
        return visitChildren(node, data);
282
    }
283
}
284
```
285

286
### Type System Traversal
287

288
```java
289
// Analyze type-related constructs
290
public class TypeAnalyzer implements ScalaVisitor<Set<String>, Set<String>> {
291
    @Override
292
    public Set<String> visit(ASTTypeApply node, Set<String> data) {
293
        data.add("Type application: " + node.getText());
294
        return visitChildren(node, data);
295
    }
296
    
297
    @Override
298
    public Set<String> visit(ASTTypeFunction node, Set<String> data) {
299
        data.add("Function type: " + node.getText());
300
        return visitChildren(node, data);
301
    }
302
    
303
    @Override
304
    public Set<String> visit(ASTDefnClass node, Set<String> data) {
305
        // Analyze class type parameters
306
        node.descendants(ASTTypeParam.class).forEach(param -> {
307
            data.add("Type parameter: " + param.getText());
308
        });
309
        return visitChildren(node, data);
310
    }
311
}
312

313
// Usage
314
Set<String> typeInfo = new HashSet<>();
315
TypeAnalyzer analyzer = new TypeAnalyzer();
316
ast.acceptVisitor(analyzer, typeInfo);
317
typeInfo.forEach(System.out::println);
318
```
319

320
### Import and Package Traversal
321

322
```java
323
// Analyze imports and package structure
324
public class ImportAnalyzer implements ScalaVisitor<List<String>, List<String>> {
325
    @Override
326
    public List<String> visit(ASTImport node, List<String> data) {
327
        data.add("Import statement: " + node.getText());
328
        
329
        // Analyze specific importers
330
        node.descendants(ASTImporter.class).forEach(importer -> {
331
            data.add("  Importing: " + importer.getText());
332
            
333
            // Check for wildcard imports
334
            if (importer.descendants(ASTImporteeWildcard.class).count() > 0) {
335
                data.add("    (wildcard import)");
336
            }
337
            
338
            // Check for renamed imports
339
            importer.descendants(ASTImporteeRename.class).forEach(rename -> {
340
                data.add("    Rename: " + rename.getText());
341
            });
342
        });
343
        
344
        return visitChildren(node, data);
345
    }
346
    
347
    @Override
348
    public List<String> visit(ASTPkg node, List<String> data) {
349
        data.add("Package: " + node.getText());
350
        return visitChildren(node, data);
351
    }
352
}
353
```
354

355
## Advanced Traversal Techniques
356

357
### Conditional Traversal
358

359
```java
360
// Skip certain subtrees based on conditions
361
public class ConditionalVisitor implements ScalaVisitor<Boolean, Integer> {
362
    @Override
363
    public Integer visit(ASTDefnClass node, Boolean skipInnerClasses) {
364
        System.out.println("Processing class: " + node.getText());
365
        
366
        if (skipInnerClasses) {
367
            // Process this class but don't traverse inner classes
368
            node.children().filter(child -> !(child instanceof ASTDefnClass))
369
                .forEach(child -> child.acceptVisitor(this, false));
370
            return 1; // Return without calling visitChildren
371
        } else {
372
            return visitChildren(node, skipInnerClasses);
373
        }
374
    }
375
}
376
```
377

378
### State-Based Traversal
379

380
```java
381
// Maintain context state during traversal
382
public class ContextTracker implements ScalaVisitor<Map<String, Object>, Void> {
383
    @Override
384
    public Void visit(ASTDefnClass node, Map<String, Object> context) {
385
        // Push class context
386
        String previousClass = (String) context.get("currentClass");
387
        context.put("currentClass", node.getText());
388
        context.put("classDepth", (Integer) context.getOrDefault("classDepth", 0) + 1);
389
        
390
        // Process children with updated context
391
        Void result = visitChildren(node, context);
392
        
393
        // Pop class context
394
        context.put("currentClass", previousClass);
395
        context.put("classDepth", (Integer) context.get("classDepth") - 1);
396
        
397
        return result;
398
    }
399
    
400
    @Override
401
    public Void visit(ASTDefnDef node, Map<String, Object> context) {
402
        String currentClass = (String) context.get("currentClass");
403
        Integer depth = (Integer) context.get("classDepth");
404
        
405
        System.out.println("Method " + node.getText() + 
406
                          " in class " + currentClass + 
407
                          " at depth " + depth);
408
        
409
        return visitChildren(node, context);
410
    }
411
}
412
```
413

414
## Performance Considerations
415

416
### Efficient Node Filtering
417

418
```java
419
// Use streaming API for efficient traversal
420
ast.descendants(ASTDefnDef.class)
421
   .filter(method -> method.getText().contains("test"))
422
   .limit(10)
423
   .forEach(testMethod -> processTestMethod(testMethod));
424

425
// Combine multiple node types efficiently  
426
ast.descendants()
427
   .filter(node -> node instanceof ASTDefnClass || node instanceof ASTDefnObject)
428
   .forEach(definition -> processDefinition(definition));
429
```
430

431
### Memory-Efficient Traversal
432

433
```java
434
// Process nodes without storing references
435
public class StreamingProcessor implements ScalaVisitor<Void, Void> {
436
    @Override
437
    public Void visit(ASTLitString node, Void data) {
438
        // Process immediately without storage
439
        processStringLiteral(node.getText());
440
        return null; // Don't continue traversal for literals
441
    }
442
    
443
    private void processStringLiteral(String literal) {
444
        // Immediate processing
445
        System.out.println("Processing: " + literal);
446
    }
447
}
448
```
449

450
## Integration with Rule Development
451

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

454
```java
455
// Rule using visitor pattern
456
public class CustomScalaRule extends ScalaRule {
457
    @Override
458
    public RuleContext visit(ASTDefnClass node, RuleContext ctx) {
459
        // Rule-specific traversal logic
460
        analyzeClassStructure(node, ctx);
461
        return super.visit(node, ctx);
462
    }
463
    
464
    private void analyzeClassStructure(ASTDefnClass classNode, RuleContext ctx) {
465
        // Use traversal methods for rule implementation
466
        long methodCount = classNode.descendants(ASTDefnDef.class).count();
467
        if (methodCount > 20) {
468
            ctx.addViolation(classNode, "Class has too many methods: " + methodCount);
469
        }
470
    }
471
}
472
```
473

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