Depth-first tree traversal (DFTT) visits an abstract syntax tree (AST) in a fixed, orderly path: visit an object, inspect its settings, descend into a contained child before later siblings, then backtrack when that child is complete. The pattern specifies visitation order rather than the work performed at each visit, so the same traversal can search, modify, copy, or analyze an AST. section 3.3 section 3.3.1
Figure 3.15 Traversing an AST generically
Use the generic traversal diagram to follow the movement from an AST object through its settings, into contained objects, and back to unfinished work. section 3.3.1
For each value encountered, a DFTT handles its shape deliberately:
- For an AST object, process the object and visit its settings in a consistent order. section 3.3.1
- For a contained AST object, recurse into it; after its settings are complete, return to the containing object. section 3.3.1
- For a reference object, inspect its target when needed but do not traverse into that target. section 3.3.1
- For an array setting, traverse each item in array order; for simple values, inspect them if useful but do not descend. section 3.3.1
Count AST leaves recursively
A recursive numberOfLeaves function accepts any encoded AST value. For an AST object, it recursively totals leaf counts from its settings and returns 1 when that total is zero. References contribute 0, arrays sum their items, and simple values contribute 0. Calling the function on the rental AST returns 4. Recursion lets the JavaScript call tree retain the path needed for backtracking. section 3.3.2 section 3.3.1
DFTT also supports AST transformations. A migration can recursively visit objects and arrays, then rename the Data Attribute concept to Attribute and replace its initial value setting with value. Such migrations update ASTs that conform to an earlier DSL structure so they conform to a later one; version IDs should be checked before and updated after migration. section 10.3.2
