0
# Abstract Syntax Trees
1

2
AST representation and manipulation for compile-time and runtime tree processing, reification, and code generation. Trees represent the structure of Scala code as data that can be analyzed, transformed, and generated.
3

4
## Capabilities
5

6
### Base Tree API
7

8
Core tree operations and properties available on all tree nodes.
9

10
```scala { .api }
11
/**
12
 * Base tree trait providing fundamental tree operations
13
 */
14
trait TreeApi { this: Tree =>
15
  /** Position in source code */
16
  def pos: Position
17
  
18
  /** Type of this tree node */
19
  def tpe: Type
20
  
21
  /** Symbol associated with this tree */
22
  def symbol: Symbol
23
  
24
  /** Child trees */
25
  def children: List[Tree]
26
  
27
  /** Create a copy of this tree */
28
  def duplicate: Tree
29
  
30
  /** Check if this tree is empty */
31
  def isEmpty: Boolean
32
  
33
  /** Check if this tree represents a term */
34
  def isTerm: Boolean
35
  
36
  /** Check if this tree represents a type */
37
  def isType: Boolean
38
  
39
  /** Convert to string representation */  
40
  def toString: String
41
}
42
```
43

44
### Tree Traversal and Transformation
45

46
Methods for traversing and transforming tree structures.
47

48
```scala { .api }
49
/**
50
 * Tree traversal operations
51
 */
52
trait TreeTraversal { this: Tree =>
53
  /** Apply function to this tree and all subtrees */
54
  def foreach(f: Tree => Unit): Unit
55
  
56
  /** Filter trees matching predicate */
57
  def filter(p: Tree => Boolean): List[Tree]
58
  
59
  /** Collect results from partial function application */
60
  def collect[T](pf: PartialFunction[Tree, T]): List[T]
61
  
62
  /** Find first tree matching predicate */
63
  def find(p: Tree => Boolean): Option[Tree]
64
  
65
  /** Check if any subtree matches predicate */
66
  def exists(p: Tree => Boolean): Boolean
67
  
68
  /** Transform tree using partial function */
69
  def transform(transformer: Transformer): Tree
70
  
71
  /** Map function over all subtrees */
72
  def map(f: Tree => Tree): Tree
73
}
74
```
75

76
**Usage Example:**
77

78
```scala
79
import scala.reflect.runtime.universe._
80

81
// Create a simple AST
82
val code = reify {
83
  val x = 10
84
  val y = 20
85
  x + y
86
}.tree
87

88
println(s"Original tree: $code")
89

90
// Traverse the tree
91
code.foreach { tree =>
92
  println(s"Node: ${tree.getClass.getSimpleName} -> $tree")
93
}
94

95
// Find all literal values
96
val literals = code.collect {
97
  case Literal(Constant(value)) => value
98
}
99
println(s"Literals found: $literals")
100

101
// Find variable references
102
val variables = code.collect {
103
  case Ident(name) => name.toString
104
}
105
println(s"Variables found: $variables")
106
```
107

108
### Tree Reification
109

110
Converting runtime values and expressions into compile-time AST representations.
111

112
```scala { .api }
113
/**
114
 * Reification - converting expressions to trees
115
 */
116
def reify[T](expr: T): Expr[T]
117

118
/**
119
 * Expression wrapper providing typed AST access
120
 */
121
trait ExprApi[+T] { this: Expr[T] =>
122
  /** Underlying AST */
123
  def tree: Tree
124
  
125
  /** Static type */
126
  def staticType: Type
127
  
128
  /** Actual type */
129
  def actualType: Type
130
  
131
  /** Splice expression back to value */
132
  def splice: T
133
}
134
```
135

136
**Usage Examples:**
137

138
```scala
139
import scala.reflect.runtime.universe._
140

141
// Reify simple expressions
142
val numExpr = reify(42)
143
println(s"Number expression tree: ${numExpr.tree}")
144
println(s"Static type: ${numExpr.staticType}")
145

146
val stringExpr = reify("Hello World")
147
println(s"String expression tree: ${stringExpr.tree}")
148

149
// Reify complex expressions
150
val mathExpr = reify {
151
  val a = 10
152
  val b = 20
153
  a * b + 5
154
}
155
println(s"Math expression tree: ${mathExpr.tree}")
156

157
// Reify method calls
158
def greet(name: String): String = s"Hello $name"
159
val methodCallExpr = reify(greet("Alice"))
160
println(s"Method call tree: ${methodCallExpr.tree}")
161

162
// Reify control structures
163
val controlExpr = reify {
164
  val numbers = List(1, 2, 3, 4, 5)
165
  for (n <- numbers if n % 2 == 0) yield n * 2
166
}
167
println(s"Control structure tree: ${controlExpr.tree}")
168
```
169

170
### Tree Construction
171

172
Programmatic construction of AST nodes.
173

174
```scala { .api }
175
/**
176
 * Tree construction utilities
177
 */
178
object TreeFactory {
179
  /** Create literal tree */
180
  def Literal(value: Any): Tree
181
  
182
  /** Create identifier tree */
183
  def Ident(name: String): Tree
184
  
185
  /** Create method application tree */
186
  def Apply(fun: Tree, args: List[Tree]): Tree
187
  
188
  /** Create type application tree */
189
  def TypeApply(fun: Tree, args: List[Tree]): Tree
190
  
191
  /** Create selection tree (obj.member) */
192
  def Select(qualifier: Tree, name: String): Tree
193
  
194
  /** Create block tree */
195
  def Block(stats: List[Tree], expr: Tree): Tree
196
  
197
  /** Create if-then-else tree */
198
  def If(cond: Tree, thenp: Tree, elsep: Tree): Tree
199
  
200
  /** Create value definition tree */
201
  def ValDef(name: String, tpt: Tree, rhs: Tree): Tree
202
  
203
  /** Create method definition tree */
204
  def DefDef(name: String, paramss: List[List[Tree]], tpt: Tree, rhs: Tree): Tree
205
}
206
```
207

208
**Usage Example:**
209

210
```scala
211
import scala.reflect.runtime.universe._
212

213
// Construct simple trees
214
val literalTree = Literal(Constant(42))
215
val identTree = Ident(TermName("x"))
216

217
// Construct method call: println("Hello")
218
val printlnTree = Select(Ident(TermName("scala")), TermName("println"))  
219
val helloTree = Literal(Constant("Hello"))
220
val callTree = Apply(printlnTree, List(helloTree))
221

222
println(s"Method call tree: $callTree")
223

224
// Construct block: { val x = 10; x + 5 }
225
val valDefTree = ValDef(
226
  Modifiers(), 
227
  TermName("x"), 
228
  TypeTree(), 
229
  Literal(Constant(10))
230
)
231
val addTree = Apply(
232
  Select(Ident(TermName("x")), TermName("$plus")),
233
  List(Literal(Constant(5)))
234
)
235
val blockTree = Block(List(valDefTree), addTree)
236

237
println(s"Block tree: $blockTree")
238
```
239

240
### Tree Pattern Matching
241

242
Pattern matching on AST nodes for analysis and transformation.
243

244
```scala { .api }
245
/**
246
 * Common tree patterns for matching
247
 */
248
object TreePatterns {
249
  /** Match literal values */
250
  def unapply(tree: Tree): Option[Any] = tree match {
251
    case Literal(Constant(value)) => Some(value)
252
    case _ => None
253
  }
254
  
255
  /** Match variable references */
256
  object Variable {
257
    def unapply(tree: Tree): Option[String] = tree match {
258
      case Ident(name) => Some(name.toString)
259
      case _ => None
260
    }
261
  }
262
  
263
  /** Match method calls */
264
  object MethodCall {
265
    def unapply(tree: Tree): Option[(Tree, String, List[Tree])] = tree match {
266
      case Apply(Select(obj, name), args) => Some((obj, name.toString, args))
267
      case _ => None
268
    }
269
  }
270
  
271
  /** Match assignments */
272
  object Assignment {
273
    def unapply(tree: Tree): Option[(String, Tree)] = tree match {
274
      case Assign(Ident(name), rhs) => Some((name.toString, rhs))
275
      case _ => None
276
    }
277
  }
278
}
279
```
280

281
**Usage Example:**
282

283
```scala
284
import scala.reflect.runtime.universe._
285

286
val sampleCode = reify {
287
  val name = "Alice"
288
  val age = 25
289
  println(s"$name is $age years old")
290
  age + 1
291
}.tree
292

293
// Pattern match on tree nodes
294
def analyzeTree(tree: Tree): Unit = tree match {
295
  case Literal(Constant(value)) =>
296
    println(s"Found literal: $value (${value.getClass.getSimpleName})")
297
    
298
  case Ident(name) =>
299
    println(s"Found identifier: $name")
300
    
301
  case Apply(Select(obj, name), args) =>
302
    println(s"Found method call: $obj.$name with ${args.length} arguments")
303
    args.foreach(analyzeTree)
304
    analyzeTree(obj)
305
    
306
  case ValDef(mods, name, tpt, rhs) =>
307
    println(s"Found val definition: $name")
308
    analyzeTree(rhs)
309
    
310
  case Block(stats, expr) =>
311
    println(s"Found block with ${stats.length} statements")
312
    stats.foreach(analyzeTree)
313
    analyzeTree(expr)
314
    
315
  case other =>
316
    println(s"Other tree: ${other.getClass.getSimpleName}")
317
    other.children.foreach(analyzeTree)
318
}
319

320
analyzeTree(sampleCode)
321
```
322

323
### Tree Transformers
324

325
Systematic tree transformation using the Transformer class.
326

327
```scala { .api }
328
/**
329
 * Base transformer for systematic tree transformation
330
 */
331
abstract class Transformer {
332
  /** Transform a tree */  
333
  def transform(tree: Tree): Tree
334
  
335
  /** Transform list of trees */
336
  def transformTrees(trees: List[Tree]): List[Tree]
337
  
338
  /** Transform modifiers */
339
  def transformModifiers(mods: Modifiers): Modifiers
340
  
341
  /** Transform template */
342
  def transformTemplate(templ: Template): Template
343
}
344
```
345

346
**Usage Example:**
347

348
```scala
349
import scala.reflect.runtime.universe._
350

351
// Custom transformer that replaces all integer literals with their double
352
class IntToDoubleTransformer extends Transformer {
353
  override def transform(tree: Tree): Tree = tree match {
354
    case Literal(Constant(value: Int)) =>
355
      Literal(Constant(value.toDouble))
356
    case _ =>
357
      super.transform(tree)
358
  }
359
}
360

361
val originalCode = reify {
362
  val x = 10
363
  val y = 20
364
  x + y
365
}.tree
366

367
println(s"Original: $originalCode")
368

369
val transformer = new IntToDoubleTransformer
370
val transformedCode = transformer.transform(originalCode)
371
println(s"Transformed: $transformedCode")
372
```
373

374
### Tree Traversers
375

376
Systematic tree traversal using the Traverser class.
377

378
```scala { .api }
379
/**
380
 * Base traverser for systematic tree traversal
381
 */
382
abstract class Traverser {
383
  /** Traverse a tree */
384
  def traverse(tree: Tree): Unit
385
  
386
  /** Traverse list of trees */
387
  def traverseTrees(trees: List[Tree]): Unit
388
  
389
  /** Traverse modifiers */
390
  def traverseModifiers(mods: Modifiers): Unit
391
  
392
  /** Traverse template */
393
  def traverseTemplate(templ: Template): Unit
394
}
395
```
396

397
**Usage Example:**
398

399
```scala
400
import scala.reflect.runtime.universe._
401

402
// Custom traverser that counts different node types
403
class NodeCounter extends Traverser {
404
  private var counts = scala.collection.mutable.Map[String, Int]()
405
  
406
  def getCounts: Map[String, Int] = counts.toMap
407
  
408
  override def traverse(tree: Tree): Unit = {
409
    val nodeType = tree.getClass.getSimpleName
410
    counts(nodeType) = counts.getOrElse(nodeType, 0) + 1
411
    super.traverse(tree)
412
  }
413
}
414

415
val code = reify {
416
  val numbers = List(1, 2, 3, 4, 5)
417
  val doubled = numbers.map(_ * 2)
418
  val sum = doubled.reduce(_ + _)
419
  println(s"Sum: $sum")
420
}.tree
421

422
val counter = new NodeCounter
423
counter.traverse(code)
424

425
println("Node counts:")
426
counter.getCounts.toSeq.sortBy(-_._2).foreach { case (nodeType, count) =>
427
  println(s"  $nodeType: $count")
428
}
429
```
430

431
### Advanced Tree Operations
432

433
Complex tree operations for advanced use cases.
434

435
```scala { .api }
436
/**
437
 * Advanced tree manipulation utilities
438
 */
439
object TreeUtils {
440
  /** Find all nodes of specific type */
441
  def findNodesOfType[T <: Tree](tree: Tree)(implicit tag: scala.reflect.ClassTag[T]): List[T]
442
  
443
  /** Replace all occurrences of a subtree */
444
  def replaceTree(tree: Tree, target: Tree, replacement: Tree): Tree
445
  
446
  /** Extract all variable names */
447
  def extractVariableNames(tree: Tree): Set[String]
448
  
449
  /** Check if tree contains a specific pattern */
450
  def containsPattern(tree: Tree, pattern: Tree => Boolean): Boolean
451
  
452
  /** Get tree depth */
453
  def getDepth(tree: Tree): Int
454
  
455
  /** Pretty print tree structure */
456
  def prettyPrint(tree: Tree, indent: Int = 0): String
457
}
458
```
459

460
**Complete Tree Analysis Example:**
461

462
```scala
463
import scala.reflect.runtime.universe._
464

465
def completeTreeAnalysis(tree: Tree): Unit = {
466
  println("=== Tree Analysis ===")
467
  println(s"Tree: $tree")
468
  println(s"Type: ${tree.tpe}")
469
  println(s"Symbol: ${tree.symbol}")
470
  println(s"Position: ${tree.pos}")
471
  println(s"Is term: ${tree.isTerm}")
472
  println(s"Is type: ${tree.isType}")
473
  println(s"Is empty: ${tree.isEmpty}")
474
  
475
  // Children analysis
476
  println(s"\nChildren (${tree.children.length}):")
477
  tree.children.zipWithIndex.foreach { case (child, i) =>
478
    println(s"  [$i] ${child.getClass.getSimpleName}: $child")
479
  }
480
  
481
  // Pattern matching analysis
482
  tree match {
483
    case Literal(Constant(value)) =>
484
      println(s"\nLiteral value: $value (${value.getClass.getSimpleName})")
485
      
486
    case Ident(name) =>
487
      println(s"\nIdentifier: $name")
488
      
489
    case Apply(fun, args) =>
490
      println(s"\nApplication:")
491
      println(s"  Function: $fun")
492
      println(s"  Arguments (${args.length}): ${args.mkString(", ")}")
493
      
494
    case Select(qualifier, name) =>
495
      println(s"\nSelection:")
496
      println(s"  Qualifier: $qualifier")
497
      println(s"  Name: $name")
498
      
499
    case Block(stats, expr) =>
500
      println(s"\nBlock:")
501
      println(s"  Statements (${stats.length}): ${stats.mkString("; ")}")
502
      println(s"  Expression: $expr")
503
      
504
    case _ =>
505
      println(s"\nOther tree type: ${tree.getClass.getSimpleName}")
506
  }
507
  
508
  println("\n" + "="*50)
509
}
510

511
// Analyze various tree types
512
val examples = List(
513
  reify(42).tree,
514
  reify("hello").tree,
515
  reify(List(1, 2, 3)).tree,
516
  reify { val x = 10; x + 5 }.tree,
517
  reify { if (true) "yes" else "no" }.tree
518
)
519

520
examples.foreach(completeTreeAnalysis)
521
```