# AST Reference

The AST is the tree `Predicator.Parser.parse/2` and `parse_program/2` produce
from a token stream, and the shape every visitor consumes -
`Predicator.decompile/2` turns it back into source, `InstructionsVisitor`
turns it into instructions. This page describes that shape node by node, in
the present tense: what a node looks like, which token it blames when
something about it fails, and which characters it covers when a caller asks
for a span. `t:Predicator.Parser.ast/0` - the type in `lib/predicator/parser.ex`
- is the machine-checked authority; this page is the prose version of it.

## The trailing slot

Every AST node ends in one slot: a `{line, column}`, a span, or `nil`. There is
one AST shape, not two - a caller building a node by hand rather than parsing
supplies `nil` in that slot, and every visitor clause matches on "node with a
trailing slot in," never on a position-free variant.

Positions are the default at every entry point. `Predicator.Parser.parse/2`
and `parse_program/2` fill the slot with a `{line, column}` naming the token
that defines the node, unless the caller passes `spans: true`, in which case
the slot holds a `t:Predicator.Types.span/0` throughout instead:

```elixir
# default
{:arithmetic, :multiply, {:identifier, "a", {1, 1}}, {:literal, true, {1, 5}}, {1, 3}}

# spans: true
{:arithmetic, :multiply,
  {:identifier, "a", {{1, 1}, {1, 2}}},
  {:literal, true, {{1, 5}, {1, 9}}},
  {{1, 1}, {1, 9}}}
```

One parse produces one kind of metadata throughout; positions and spans are
never mixed within a single tree.

## Expression nodes

`t:Predicator.Parser.ast/0` is the union of these arms, each carrying its
trailing slot last:

```elixir
{:literal, value, pos}
{:string_literal, binary, :double | :single, pos}
{:identifier, name, pos}
{:comparison, op, left, right, pos}
{:arithmetic, op, left, right, pos}
{:unary, op, operand, pos}
{:membership, op, left, right, pos}
{:logical_and, left, right, pos}
{:logical_or, left, right, pos}
{:logical_not, operand, pos}
{:list, elements, pos}
{:object, entries, pos}
{:function_call, name, args, pos}
{:bracket_access, target, key, pos}
{:property_access, target, property, pos}
{:cast, expression, type_name, pos}
{:duration, units, pos}
{:relative_date, duration, direction, pos}
```

`type_name` in a `cast` node is one of the seven scalar ISA type names
(`integer`, `float`, `string`, `boolean`, `date`, `datetime`, `duration`),
held as a binary; the parser rejects any other name, so a `cast` node can
never carry an invalid target. The names are contextual identifiers, not
keywords - they are only special immediately after `::`
([ADR-0011](https://github.com/riddler/predicator-ex/blob/main/docs/adr/0011-casts-are-an-opcode.md)).

## Object keys

Object keys have their own node - `{:object_key, value, style, pos}` - rather
than reusing an expression tag, so nothing tells a key from an expression by
tuple arity alone. `style` is `:identifier`, `:double`, or `:single`,
recording whether the key was written bare (`{name: 1}`), double-quoted
(`{"name": 1}`), or single-quoted (`{'name': 1}`), so
`Predicator.Visitors.StringVisitor` can decompile it back exactly as written.
An `{:object, entries, pos}` node's `entries` are `{object_key, expression}`
pairs. The `Predicator.AST` walks treat a key as part of its entry rather
than a node: they never hand it to the callback and visit only the entry's
expression.

## Statement nodes

`{:program, statements, pos}`, `{:assignment, lhs, rhs, pos}`,
`{:if, condition, then_block, else_block, pos}`,
`{:while, condition, body, pos}`, and `{:block, statements, pos}` are produced
only by `Predicator.Parser.parse_program/2`, the statement entry point
alongside `parse/2`. None of the five is a member of `t:ast/0`: `parse/2`
never returns one, and an expression consumer never has to handle one.

```elixir
{:program, [statement], pos}
{:assignment, lhs, rhs, pos}
{:if, condition, then_block, else_block, pos}
{:while, condition, body, pos}
{:block, [statement], pos}
```

`lhs` in an assignment node is the unflattened access chain the parser already
builds for postfix expressions - an `{:identifier, ...}` optionally wrapped in
any number of `{:property_access, ...}` and `{:bracket_access, ...}` nodes -
kept as a chain rather than resolved to a path, because a bracket key can be
an arbitrary expression that only resolves against a context at runtime;
`Predicator.ContextLocation.resolve/2` does that resolution. The point
position is the `=` token; the span (under `spans: true`) runs from the `lhs`
start to the `rhs` end.

`condition` in an if node is a bare expression; `then_block` is always a
`{:block, statements, pos}`, never `nil`. `else_block` is `nil` when there is
no `else` and a `{:block, statements, pos}` when there is - including for
`else { }`, whose empty block stays distinguishable from an absent one
([ADR-0013](https://github.com/riddler/predicator-ex/blob/main/docs/adr/0013-control-flow-lowers-to-new-jump-opcodes.md)). A block
introduces no scope: its `statements` are ordinary program statements, and a
`store` inside one is visible after the block.

`else if c2 { B }` is parser sugar with no chain node of its own: it parses as
an `else_block` holding a single-statement block whose one statement is the
nested `{:if, ...}`. For

```
if a { x = 1 } else if b { x = 2 } else { x = 3 }
```

the outer node's `else_block` is `{:block, [{:if, b, ..., ...}], pos}` - a
block wrapping the `if b { x = 2 } else { x = 3 }` node, not a three-way
chain. That synthetic block's own trailing slot is the nested `if` node's own
slot, so it needs no position of its own: in point mode it is the nested `if`
token, and under `spans: true` it is the nested `if`'s span, which already
starts at the same token and runs through the same final `}`.

Neither `if` nor `block` is a member of `t:ast/0`, the same as `program` and
`assignment`. `while` follows the same rule: `condition` in a while node is a
bare expression, `body` is always a `{:block, statements, pos}`, and the body
introduces no scope any more than an `if`'s blocks do - a `store` inside it is
visible after the loop.

`InstructionsVisitor` compiles the `program`, `assignment`, `if`, `while`, and
`block` nodes today. A `{:program, statements, pos}` compiles each statement in
order, concatenating the results; a `{:block, statements, pos}` compiles the
same way - a block introduces no scope of its own, so it is a plain statement
sequence. An `{:assignment, lhs, rhs, pos}` compiles to the `lhs` chain's
segments (root-to-leaf), then `rhs`, then `["store", n]`, where `n` is the
chain's segment depth; any other statement compiles to its own instructions
followed by `["pop"]`. That trailing `["pop"]` is emitted uniformly, including
after the program's last statement, so the stack is empty at every statement
boundary - **except an `if` or `while` statement**, neither of which, unlike
every other non-assignment statement, takes a trailing `["pop"]`: an `if`'s
condition is consumed by `pop_jump_if_falsy` and its blocks are already
stack-neutral by construction, and a `while`'s condition is consumed by
`pop_jump_if_falsy` on every iteration including the last, so in both cases
nothing is left for a `pop` to remove
([ADR-0013](https://github.com/riddler/predicator-ex/blob/main/docs/adr/0013-control-flow-lowers-to-new-jump-opcodes.md)).

`{:if, condition, then_block, nil, pos}` (no `else`) lowers to `condition`'s
instructions, then `["pop_jump_if_falsy", offset]` sized to land one past the
then block, then the then block's own instructions.
`{:if, condition, then_block, else_block, pos}` (with an `else`) lowers to
`condition`, `["pop_jump_if_falsy", offset]` sized to land one past an
unconditional `["jump", offset]` appended after the then block, the then
block, that `jump` (sized to land one past the else block), then the else
block. Both the `pop_jump_if_falsy` and the `jump` carry the `if` node's own
position, not the condition's.

`{:while, condition, body, pos}` lowers to `condition`, then
`["pop_jump_if_falsy", offset]` sized to land one past a `["jump_backward",
offset]` appended after the body, the body's own instructions, then that
`jump_backward` - `c; ["pop_jump_if_falsy", lenA + 2]; A; ["jump_backward",
lenC + lenA + 1]` for `while c { A }` (ISA v6, ADR-0013). The `jump_backward`'s
offset is measured from its own index back to `condition`'s first
instruction, which is why it counts `lenC` as well as `lenA`. Both the
`pop_jump_if_falsy` and the `jump_backward` carry the `while` node's own
position, not the condition's. Execution of any compiled program containing a
`jump_backward` is bounded by the evaluator's loop budget (`docs/isa.md` §2,
§5) - a normal, expected part of running a `while` loop, not an error path.

In point mode the compiled `["store", n]` instruction is annotated with the
`lhs` root segment's own position rather than the assignment node's `=`, so a
store failure's caret lands on the location being written; under
`spans: true` it keeps the assignment's span, whose start is already that same
token.

Alongside that per-instruction position table, compiling an assignment also
produces a per-*segment* table: one source annotation per `lhs` location
segment, root-first, keyed by the `["store", n]` instruction's own index. A
segment's annotation is the annotation of the node that produced its value -
the `{:identifier, ...}` node for the root, the `{:property_access, ...}` node
for a dotted segment, and the key expression for a bracket segment, since the
key is what a bad or out-of-range segment value came from. The list's length
is the chain's segment depth, which is exactly `["store", n]`'s own operand,
so `n` bounds the index into it. Because a `property_access` node's point
position is the property-name token (see "Which token a node blames" below), a
dotted segment's point position names the property itself - for `a.b.c`, the
segment for `.b` points at column 17 in `a = {"b": 1}; a.b.c = 2`, `b` itself.
And because a `property_access` node's span starts at the chain root (see
"Which characters a node covers" below), narrowing a store failure to one
segment's span moves only the underline, never the caret - the segment for
`.b` in that same source spans `a.b`, whose start is still `a`, at column 15.
The point-mode caret (column 17) and the span-derived caret (column 15) are
deliberately different answers to different questions: the point names the
value that failed, the span's start names where the accessed location begins.

`docs/isa.md` §5 is the normative statement of `store`'s and `pop`'s
stack discipline and error shapes; this page only says what AST shape feeds
them.

## Which token a node blames

Leaves point at their own token. Most non-leaf nodes point at the token that
*names the operation*, so an error names the thing that failed rather than the
start of the subexpression it failed on - `a * true` reports column 3, not
column 1. `bracket_access` and `property_access` are the deliberate exception:
an access node blames the accessed operand instead, because for an access the
thing that failed is the property or key, not the punctuation that reached it
(the `.` or `[`). For a compound key the point is the key expression's first
token - `a[x + 1]` blames the `x`, not the `+` - which coincides with the
key's own blame position only when the key is a single token, as in
`user.name`:

| Node | Defining token |
|---|---|
| `literal`, `string_literal`, `identifier`, `object_key` | own token |
| `comparison`, `arithmetic`, `membership`, `logical_and`, `logical_or` | the operator |
| `unary`, `logical_not` | the operator |
| `list`, `object` | the opening bracket or brace |
| `function_call` | the name token |
| `bracket_access` | the first token of the key expression |
| `property_access` | the property-name token |
| `cast` | the type-name token |
| `duration` | its first number |
| `relative_date` | the direction keyword (`ago`, `from`, `next`, `last`) |
| `if` | the `if` keyword |
| `while` | the `while` keyword |
| `block` | the opening `{` token |
| a desugared else-if's synthetic block | the nested `if` keyword |

A new node type follows this rule: point it at the token a reader would blame.

The same rule governs a statement's compiled instructions, not just a node's
own point position: **blame lands on the token carrying the type rule that was
violated.** `if` and `while` each carry one (a boolean condition), the same way
`*` carries one (numbers) and `and` carries one (booleans), so their
`pop_jump_if_falsy` (and `if`'s `jump`, and `while`'s `jump_backward`) is
annotated with the statement keyword's own position, not the condition's - see
the `if` and `while` rows above and their lowering sentences earlier on this
page. `store_annotation/2` looks like a counterexample - `["store", n]` is
annotated with the `lhs` root's position, not the assignment's `=` - but `=`
carries no type rule at all; an assignment accepts any rhs, so when a store
fails the `=` has nothing to say about it and the location being written is
the only token that does. That is a single, closed exception, not the first of
a series: it is what happens when the operator has no rule to point at, not a
license to move blame off any other operator with one.

## Which characters a node covers

A point position tells a caller where to put a caret; a span tells it what to
underline. A span names the position one past a node's last character, so on a
single line `end_column - start_column` is the length and a zero-width range
is representable. This matches LSP ranges.

For most tokens that exclusive end is computed from the start position plus
the token's length. `:string` is the exception: because a string literal can
span multiple lines, its end position is not computed - it is read directly
off the token, which carries its own explicit end position for exactly this
reason. That is what keeps a multi-line literal's span correct.

Where the table above says which token to *blame*, this one says which
characters to *underline*. A new node type needs a row in both:

| Node | Span start | Span end |
|---|---|---|
| `literal` | own token | own token end |
| `string_literal` | own token, opening quote included | own token end, past the closing quote |
| `identifier` | own token | own token end |
| `object_key` | own token, opening quote included if quoted | own token end |
| `comparison`, `membership` | left operand start | right operand end |
| `arithmetic` | left operand start | right operand end |
| `logical_and`, `logical_or` | left operand start | right operand end |
| `unary`, `logical_not` | the operator token | operand end |
| `list` | the `[` token | past the `]` token |
| `object` | the `{` token | past the `}` token |
| `function_call` | the name token | past the `)` token |
| `bracket_access` | target expression start | past the `]` token |
| `property_access` | target expression start | property-name token end |
| `cast` | target expression start | type-name token end |
| `duration` | its first number token | past the last duration unit |
| `relative_date` (`ago`) | duration start | past the `ago` token |
| `relative_date` (`from now`) | duration start | past the `now` token |
| `relative_date` (`next`, `last`) | the direction keyword token | duration end |
| parenthesized expression | the `(` token | past the `)` token |
| `if` | the `if` token | past the last block's `}` (the else block's if present, otherwise the then block's) |
| `while` | the `while` token | past the body block's `}` |
| `block` | the `{` token | past the `}` token |
| a desugared else-if's synthetic block | the nested `if`'s own span start | the nested `if`'s own span end |

Two consequences follow from this table: a quoted string's and a `#`-fenced
date's span include their delimiters, because the lexer's token length is the
full source extent; and an empty `[]`, `{}`, `f()`, or `{ }` block still spans
both delimiters, because the end comes from the closing token rather than
from a child.

A parenthesized expression's span includes its parentheses and composes to the
outermost pair.

## Traversing and analysing the tree

Two modules read this shape so a tool does not hand-write a clause per node
kind. How to use them is the
[how-to guide](../guides/analysing-expressions.md); this section says what
each one does with the nodes on this page.

`Predicator.AST` walks anything `t:Predicator.Parser.visitable/0` names: the
expression nodes, `assignment`, `if` and `while`, a `block`, or a whole
`program`.
`Predicator.AST.prewalk/3` and `Predicator.AST.postwalk/3` thread an
accumulator through a callback that may replace a node, before and after the
node's children respectively; `Predicator.AST.reduce/3` folds over every node
without rewriting. The callback sees each node once, whole, with its trailing
slot as the parser put it; no walk reads, changes or drops that slot. Children
are visited in source order, and three shapes have a stated rule:

| Node | What the walk does |
|---|---|
| `object` | visits each entry's value in entry order; the `object_key` is part of the entry, never handed to the callback |
| `duration` | has no children: its `{integer, unit}` pairs are plain data |
| `relative_date` | walks its `duration` as a child |

`Predicator.Analysis` answers three questions with those walks and with a
second reading of the compiled instructions: `references/1` lists each
variable read as a path, `calls/1` each function call with its name and arity,
and `assignments/1` each location a program stores to. A path is a list of
segments - a string, an integer for a literal index, or `:dynamic` for any
other key, a computed one or a literal that is neither a string nor an integer - read off the access chain this page describes: an `identifier`
wrapped in `property_access` and `bracket_access` nodes. A chain rooted at
anything other than an `identifier` reads no variable.

The position of a read is the trailing slot this page's first section
describes: the span of the whole chain when the tree carries spans, and
otherwise the point position of the chain's root variable. An assignment's
position is its own node's span when the tree carries spans, and otherwise the
root variable's point position, so it starts where the written location
starts. A call's position is the `function_call` node's own: the point of the name
token, or the span from the name through the closing parenthesis when the tree
carries spans.
An assignment's location is not a read; the bracket keys inside it are.

`Predicator.Analysis` also accepts instruction lists and
`Predicator.Compiled` envelopes, and gives the same paths, calls and stores
for the same source. A bare instruction list carries no trailing slots, so
every position read from one is `nil`.