Parsing an Abstract Syntax Tree for Code Analysis

#ai #llm #machinelearning #programming

An AST is not a data structure you use because it is elegant. It is the only thing that turns “the third argument of every call to this function” from a regular expression that almost works into a query that is correct.

What a node holds

Every node in a syntax tree carries four things, whatever the parser: a type (function_definition, call, identifier), a span in the source — byte offsets and usually row/column points, so you can map a node back to the exact text — a list of children, and named fields that label the children by their role.

The span is what makes an AST useful for indexing rather than only for compiling. A chunker that splits on function boundaries needs the start and end byte of each function_definition node and nothing else; a search result that highlights the right lines needs the node’s start point. Any parser that gives you a tree but not byte offsets is nearly useless for this class of work.

The word abstract is doing real work in the name. The tree does not represent the text; it represents the structure the text denotes. Parentheses used for grouping do not survive as nodes, because their entire meaning has been absorbed into the shape of the tree. Neither does the choice between 'x' and "x", nor whether a statement was written on one line or four. That is exactly why an AST is the right tool for asking questions about behaviour and the wrong one for asking questions about formatting — and it is the distinction the last section of this page turns on.

A walk over a short function

Take four lines of Python and dump the tree. Python’s standard library has an AST module, so this needs nothing installed:

import ast

src = """
def charge(order, rate):
    total = order.subtotal * (1 + rate)
    return round(total, 2)
"""

tree = ast.parse(src)
print(ast.dump(tree.body[0], indent=2))

FunctionDef(
  name='charge',
  args=arguments(
    args=[arg(arg='order'), arg(arg='rate')]),
  body=[
    Assign(
      targets=[Name(id='total', ctx=Store())],
      value=BinOp(
        left=Attribute(
          value=Name(id='order', ctx=Load()),
          attr='subtotal', ctx=Load()),
        op=Mult(),
        right=BinOp(left=Constant(value=1),
                    op=Add(),
                    right=Name(id='rate', ctx=Load())))),
    Return(
      value=Call(
        func=Name(id='round', ctx=Load()),
        args=[Name(id='total', ctx=Load()), Constant(value=2)],
        keywords=[]))])

Read what that gives you that text does not. The multiplication and the addition are separate BinOp nodes in the right nesting order, so operator precedence is already resolved — you never have to reason about it. order.subtotal is an Attribute node with value and attr as distinct parts, so “every access to .subtotal” is a node-type query. Each Name carries a context: Store where total is assigned and Load where it is read, which is the difference between a definition and a use, and it is the single hardest thing to get right with text matching.

Walking it is a visitor. This collects every function that calls round:

class FindRound(ast.NodeVisitor):
    def __init__(self):
        self.current = None
        self.hits = []

    def visit_FunctionDef(self, node):
        prev, self.current = self.current, node.name
        self.generic_visit(node)          # descend; without this, nothing
        self.current = prev

    def visit_Call(self, node):
        f = node.func
        if isinstance(f, ast.Name) and f.id == "round":
            self.hits.append((self.current, node.lineno))
        self.generic_visit(node)

v = FindRound(); v.visit(tree); print(v.hits)
# [('charge', 4)]

The save-and-restore of self.current around the recursive descent is not incidental — it is how you attribute a nested node to its enclosing definition, and it is the pattern nested functions and methods break if you use a single mutable variable without the restore. Forgetting generic_visit is the other classic bug: the visitor silently stops descending and reports zero hits.

Fields, not just children

Positional children are fragile. In tree-sitter’s grammars — the multi-language parser generator most code indexing tools are built on — children are additionally addressable by field name, and queries can constrain them:

(function_definition
  name: (identifier) @fn
  parameters: (parameters) @params
  body: (block) @body)

name: and body: are field names, and @fn is a capture you retrieve the matched node by. Writing children[1] instead would break the moment a decorator, a type annotation or an async keyword appeared. Fields are stable across grammar revisions in a way positions are not, so prefer node.child_by_field_name("name") to indexing.

Error recovery is the deciding property

Python’s ast.parse raises SyntaxError on the first problem and returns nothing. For a compiler that is correct. For indexing a repository it is disqualifying, because real repositories contain files with unresolved merge conflict markers, files using syntax newer than your parser, template files with placeholder tokens, and partially written code in an editor buffer. One such file should cost you that file, not the run.

tree-sitter recovers: it always returns a tree, and it represents what it could not parse as ERROR nodes and inserts zero-width MISSING nodes where a token was expected. Everything outside the damaged region parses normally, so a file with one broken function still yields the other forty. When indexing, check whether any node in a chunk’s subtree is an ERROR, and record that as a quality flag rather than discarding the chunk.

The other property that matters at repository scale is incremental reparsing. tree-sitter lets you describe an edit and reuse the previous tree:

tree.edit(
    start_byte=142, old_end_byte=142, new_end_byte=160,
    start_point=(7, 4), old_end_point=(7, 4), new_end_point=(7, 22),
)
new_tree = parser.parse(new_source, tree)
for r in tree.changed_ranges(new_tree):
    print(r.start_byte, r.end_byte)   # only these chunks need re-embedding

changed_ranges is the direct link between parsing and index maintenance: it tells you which byte ranges of the file actually have a different syntactic structure, which is a much tighter set than “the file changed”. That is the mechanism behind re-embedding only what moved, described in the commit-hook tutorial.

The Python binding’s API changed across recent releases — Query and QueryCursor are now separate classes and the older language.query(...) helper is gone. Check which version you have before copying any tree-sitter snippet, including this one.

Concrete versus abstract

The distinction is not pedantry; it decides which tool you can use. A concrete syntax tree keeps every token, including punctuation, comments and the exact whitespace, so the source can be reconstructed byte-for-byte from the tree. An abstract syntax tree discards what the compiler does not need — Python’s ast drops comments entirely, and you cannot get them back from the tree.

For indexing that matters a great deal, because the docstring and the leading comment are frequently the most retrievable text in a function. If your chunker builds text from an abstract tree it will silently drop them. tree-sitter produces a concrete tree, which is why it is the usual choice for code indexing and for anything that rewrites source and must preserve formatting. Use ast when you want semantics and control the input; use a concrete-tree parser when the source is arbitrary and the text matters as much as the structure.