For AI agents: this page as Markdown · llms.txt · JSON Schema

Tape transducer language

Status: a design with a test-only implementation; production rule evaluation does not use it.

What is compiled, and where

The interpreter in native/src/code_rule_dsl/transducer.rs, with execute_batch and the ast-grep pattern compiler, compiles only for tests. Its arm64 JIT and Metal backends compile only for tests with the bench-backends feature on macOS. Production uses only that file's per-tape stream of node kinds, stored as a search index.

Scope

A transducer reads a syntax tape and produces match records with captures; it is not a general-purpose VM.

It describes selection, tests, navigation, alternatives, and output. It has no registers, arithmetic instructions, calls, stack operations, mutable memory, or host callbacks. Storage, SQL rule composition, scheduling, and backend implementation are outside its semantics.

Input and output

Paths walk an immutable tape; only EMIT turns a path into an output record.

Nodes, paths, and captures in detail

A node exposes kind, incoming field, flags, byte span, parent, and ordered children. Its identity is tape identity plus ordinal, not byte span. A path's parts are transducer semantics, not a prescribed runtime data structure.

A capture is a label, node identity, and half-open UTF-8 byte span. Repeated labels append; they never overwrite. Rejected paths output nothing, including their captures.

Exactly one word per instruction

Every instruction is exactly 32 bits; there are no extension words, operand words, escape prefixes, or variable lengths.

text
31                    16 15          8 7           0
+-----------------------+-------------+-------------+
|      operand:u16      |   mode:u8   |   opcode:u8 |
+-----------------------+-------------+-------------+

word = opcode | (mode << 8) | (operand << 16)

The next instruction is always the next word. Positions count words, not bytes. Serialized words are little-endian.

Exact limits

Positions, local table indices, labels, and small numeric comparisons are 16-bit. Checked arithmetic rejects overflow; it never wraps into another instruction or table entry. A program holds at most 65,536 instructions and 65,536 entries per local table. More is an explicit compilation error, not truncated code.

Tape positions and source spans are the exception: they keep native width through the tape iterator. A file with more than 65,535 nodes is not truncated or split, and the language needs no general wide arithmetic.

Tables

Each transducer has four local data tables, referenced by 16-bit index.

Table Contents
Strings Arbitrary-length byte strings. Capture and output names use UTF-8 entries.
Predicates Pure text tests: equality, prefix, or regex, with a string index and declared text semantics.
Labels Capture and output names, each referring to a string entry.
Long integers Unsigned 64-bit constants for numeric tests that exceed 16 bits.
Table rules

Instructions

Fourteen opcodes cover tests, navigation, capture, branching, and output; each continues at the next word unless noted.

Opcode table and mode encoding
Opcode Instruction Mode Operand Effect
00 STOP 0 0 End this path without output.
01 KIND 0 kind ID Retain the path if the current kind equals the operand.
02 FIELD 0 field ID Retain the path if the incoming field equals the operand.
03 FLAGS required flag mask forbidden flag mask Require every required flag and no forbidden flag.
04 TEXT 0 predicate index Retain the path if the current node's source bytes satisfy the predicate.
05 SIZE comparison, optionally long value or long index Compare the current span's byte length with the constant.
10 CHILD node selection 0 Continue once for each selected direct child.
11 NEXT node selection 0 Move to the next selected sibling, or reject this path.
12 PARENT 0 0 Move to the parent, or reject this path.
13 DESCEND node selection 0 Continue once for each selected proper descendant in preorder.
20 CAPTURE 0 label index Append the current node under this label.
30 FORK 0 target instruction Continue both at the next instruction and at the target, in that order.
31 GOTO 0 target instruction Continue at the target with the same node and captures.
40 EMIT 0 label index Emit one record and end this path.

Unused mode and operand fields must be zero. Kind and field operands are the input grammar's IDs; field zero means no incoming field.

Alternatives, repetition, and ordering

Branches enumerate isolated paths, emitted in a fixed depth-first order.

A repeated sibling match uses FORK, NEXT, and a backward GOTO. This fragment emits every nonempty prefix of consecutive named identifiers:

text
0  KIND identifier
1  CAPTURE item
2  FORK 5
3  NEXT named
4  GOTO 0
5  EMIT sequence

For siblings a, b, it emits [a,b] before [a]; the shorter path never sees the capture of b.

Ordering rules

FORK and navigation never change another path's captures; there is no undo stack or register environment. Implementations may share immutable prefixes without changing these semantics.

Output order is depth-first path order:

  1. Starting nodes follow their supplied order.
  2. CHILD follows sibling order. DESCEND follows preorder.
  3. FORK follows its next-instruction path before its target path.
  4. Captures follow the order of CAPTURE instructions along that path.

Parallel execution must preserve this order. Distinct successful paths are distinct outputs, even with equal captures: no silent deduplication, no longest match. A query frontend must handle its own selection semantics rather than assume they match this language.

Cycle rules

A valid cycle must advance through a finite tape domain; in the fragment, each return to instruction zero needs a later sibling. Cycles of only tests, captures, and branches are invalid, as is parent/child oscillation. A changed node alone does not prove progress. Compilation rejects cycles without a monotonic traversal proof. Zero-width nodes still advance by ordinal.

Worked example

This program matches Python calls whose direct function child is the identifier eval.

It captures the call and its function child, then emits match. Resolved IDs and tables:

text
kind call = 0, identifier = 1
field function = 1
strings = ["eval", "callee", "call", "match"]
predicates[0] = byte-equality(strings[0])
labels = [strings[1], strings[2], strings[3]]

The kind IDs are illustrative, not from a real grammar binary.

text
position  instruction          word
0         KIND call            00000001
1         CAPTURE call         00010020
2         CHILD all            00000010
3         FIELD function       00010002
4         KIND identifier      00010001
5         TEXT 0               00000004
6         CAPTURE callee       00000020
7         EMIT match           00020040

Eight instructions occupy exactly 32 bytes.

Results for sample inputs
Input Result
eval(x) Captures call=[0,7), then callee=[0,4).
other(x) Rejected by the text test.
obj.eval(x) Function child is an attribute; rejected by the kind test.
Argument child Rejected by the field test, whatever its text.

A repeated matching field creates independent paths, not overwritten captures.

Long-constant example

A long constant is also one word:

text
longs[3] = 100000
SIZE at-least,long 3 = 00038105

The word holds opcode 05, mode 81, and table index 0003; 100000 lives only in the table.

Errors and language boundary

Invalid programs and inputs are errors, and the language stops short of rule-level logic.

Errors and exclusions

Errors:

Out of scope: SQL operators, rule-level negation, binding environments, rewrites, and a general expression evaluator. The language does not claim that arbitrary Tree-sitter queries or ast-grep rules lower directly to these primitives without semantic adaptation.

The encoding tests read the example words from this document and check one-word encoding and its boundaries:

bash
python3 test/docs/test_transducer_design.py

The test-only interpreter in native/src/code_rule_dsl/transducer.rs implements every instruction above, plus table validation, path ordering, capture isolation, cycle checks, and shared kind dispatch.