tiny.python.syntax.ast

1//! A Python program in the package's subset parses into a syntax tree. The program is a list of2//! statements. Statements hold expressions and nested lists of statements. Each expression is a3//! tree of operators and operands.4//!5//! The compiler walks the tree once to emit instructions, so every construct of the subset needs a6//! node shape of its own that the compiler can tell apart. A program's tree has many small nodes,7//! and all of them are freed together when the caller is done with the program.8//!9//! One tagged union, `Statement`, has a tag for each kind of statement. A second tagged union,10//! `Expression`, has a tag for each kind of expression. So the compiler's switch over a node covers11//! every construct. A child expression is a pointer to a constant node. A list of children is a12//! constant slice. The parsed program, `Program`, owns one arena that holds every node and list.13//! Names and string contents are slices of the source text, so the text has to outlive the tree.14//!15//! The `else` branch of `if`, `while` and `for` is a field named `otherwise`. When the source has16//! no `else`, that field is empty. An `elif` is stored as an `if` statement that is the only17//! statement of the previous `if`'s `otherwise` list.18const std = @import("std");1920/// The syntax tree of one program: its top-level statements and the arena that holds every node.21/// `parse` builds it and `compile` reads it. The caller frees it with `deinit`.22pub const Program = struct {23    /// The arena allocator that holds every statement, expression and list of the tree. `parse`24    /// creates it on the caller's allocator. `deinit` frees it.25    arena: std.heap.ArenaAllocator,26    /// The program's top-level statements in source order, allocated in the arena.27    statements: []const Statement,2829    /// Frees every node of the tree at once by freeing the arena. The package's `execute` calls it30    /// as it returns, after the bytecode compiled from the tree is freed. The call leaves the31    /// program undefined. Every slice taken from the tree's lists is invalid afterward. The32    /// bytecode that `compile` builds borrows each function's parameter list from the arena, so the33    /// tree has to outlive that bytecode. The source text stays the caller's, and `deinit` leaves34    /// it alone.35    pub fn deinit(self: *Program) void {36        self.arena.deinit();37        self.* = undefined;38    }39};4041/// One statement of the subset, as a tagged union with one tag per kind of statement. The compiler42/// switches on its tag to emit each statement's instructions. `parse` builds one for each statement43/// of the program.44pub const Statement = union(enum) {45    /// An expression statement: an expression evaluated for its value. At the top level, the value46    /// of the last one run becomes the program's result. Inside a function, the value is dropped.47    expression: *const Expression,48    /// An assignment to one name, such as `x = 1`.49    assign: Assign,50    /// An assignment to one item selected by an index, such as `xs[0] = 2`.51    subscript_assign: SubscriptAssign,52    /// A `del` statement for one name or one item selected by an index.53    delete: Delete,54    /// A `break` statement. The compiler rejects one outside a loop.55    break_stmt,56    /// A `continue` statement. The compiler rejects one outside a loop.57    continue_stmt,58    /// A `def` statement. The compiler accepts one at the top level alone.59    function: Function,60    /// A `for` loop.61    for_stmt: ForStatement,62    /// An `if` statement, whose `elif` and `else` parts are stored in its `otherwise` list.63    if_stmt: IfStatement,64    /// A `pass` statement, which the compiler skips.65    pass,66    /// A `return` statement, with or without a value. The compiler rejects one at the top level.67    return_stmt: Return,68    /// A `while` loop.69    while_stmt: WhileStatement,70};7172/// An assignment of a value to one name. The compiler turns one into a store to the name. The73/// target is a single name. `a, b = 1, 2` fails to parse with `UnexpectedToken`, because its left74/// side is a tuple.75pub const Assign = struct {76    /// The assigned name, a slice of the source text.77    name: []const u8,78    /// The expression whose value is assigned.79    value: *const Expression,80};8182/// An assignment to one item selected by an index, such as `xs[0] = 2` or `d["k"] = v`. The83/// compiler turns one into a store into a list or dictionary. A slice is never a target, so84/// `xs[0:1] = [2]` fails to parse with `UnexpectedToken`.85pub const SubscriptAssign = struct {86    /// The expression before the brackets, which gives the container.87    target: *const Expression,88    /// The expression inside the brackets.89    index: *const Expression,90    /// The expression whose value is stored.91    value: *const Expression,92};9394/// The target of a `del` statement: one name, or one item selected by an index. The compiler turns95/// one into the removal of a name or of an item. A `del` takes one target. For any other target, a96/// slice included, parsing fails with `UnexpectedToken`.97pub const Delete = union(enum) {98    /// The name to remove, a slice of the source text.99    name: []const u8,100    /// The item to remove from a container.101    subscript: SubscriptDelete,102};103104/// The item a `del` removes: a container and an index. The compiler turns one, as in `del xs[0]`,105/// into the removal of that item.106pub const SubscriptDelete = struct {107    /// The expression before the brackets, which gives the container.108    target: *const Expression,109    /// The expression inside the brackets.110    index: *const Expression,111};112113/// A function definition: its name, its parameter names and its body. The compiler turns each one114/// into a separate block of bytecode bound to the function's name. Each parameter is a plain name.115/// A trailing comma after the last parameter is allowed.116pub const Function = struct {117    /// The function's name, a slice of the source text.118    name: []const u8,119    /// The parameter names in order, each a slice of the source text. For a function without120    /// parameters, the list is empty.121    params: []const []const u8,122    /// The statements of the function's body in order.123    body: []const Statement,124};125126/// A `for` loop: the loop's name, the expression it takes items from, the body, and the `else`127/// branch. The compiler turns one into a loop that takes one item per pass from a list, tuple,128/// string, range, dictionary or iterator. The loop's target is one name.129pub const ForStatement = struct {130    /// The name bound to each item in turn, a slice of the source text.131    name: []const u8,132    /// The expression that gives the items. The iterable is one expression with no bare comma, so133    /// `for x in 1, 2:` fails to parse.134    iterable: *const Expression,135    /// The statements run for each item.136    body: []const Statement,137    /// The statements of the `else` branch. The branch runs once the loop has taken every item.138    /// When `break` ends the loop, the branch is skipped. When the loop has no `else`, the list is139    /// empty.140    otherwise: []const Statement,141};142143/// An `if` statement: its condition, the body run when the condition is true, and the `else`144/// branch. The compiler turns one into a test of the condition and a jump over the branch that does145/// not run.146pub const IfStatement = struct {147    /// The expression tested for truth. The condition is one expression with no bare comma.148    condition: *const Expression,149    /// The statements run when the condition is true.150    body: []const Statement,151    /// The statements run when the condition is false. For an `elif`, the list holds one `if`152    /// statement for the `elif` and its own branches. For an `else`, the list holds the `else`153    /// body. Without either, the list is empty.154    otherwise: []const Statement,155};156157/// A `return` statement and its optional value. The compiler turns one into leaving the function158/// with a value.159pub const Return = struct {160    /// The returned expression. For a bare `return`, the field is `null`. A bare `return` returns161    /// `None`.162    value: ?*const Expression,163};164165/// A `while` loop: its condition, its body and its `else` branch. The compiler turns one into a166/// test at the top of each pass and a jump back.167pub const WhileStatement = struct {168    /// The expression tested for truth before each pass. The condition is one expression with no169    /// bare comma.170    condition: *const Expression,171    /// The statements run on each pass while the condition is true.172    body: []const Statement,173    /// The statements of the `else` branch. The branch runs once the condition is false. When174    /// `break` ends the loop, the branch is skipped. When the loop has no `else`, the list is175    /// empty.176    otherwise: []const Statement,177};178179/// One expression, as a tagged union with one tag per kind of expression. The compiler switches on180/// its tag to emit the instructions that compute each value. `parse` allocates each node in the181/// program's arena. A node points to its children as constant nodes.182pub const Expression = union(enum) {183    /// The literal `None`.184    none,185    /// The literal `True` or `False`.186    boolean: bool,187    /// The value of an integer literal, as a signed 128-bit integer. The literal has no sign, so188    /// `-5` is unary minus applied to 5.189    integer: i128,190    /// The contents of a string literal: the bytes between the quotes, as a slice of the source191    /// text. A backslash stays in the bytes as written, with no escape decoding.192    string: []const u8,193    /// A name to look up, as a slice of the source text.194    name: []const u8,195    /// Unary minus or `not` applied to one operand.196    unary: Unary,197    /// `+`, `-` or `*` applied to two operands.198    binary: Binary,199    /// A chain of one or more comparisons, such as `a < b <= c`.200    comparison: Comparison,201    /// `and` or `or` applied to two operands.202    logical: Logical,203    /// A call of a function or method with its arguments.204    call: Call,205    /// An attribute access, such as `xs.append`.206    attribute: Attribute,207    /// A list display, such as `[1, x]`.208    list: List,209    /// A tuple: expressions separated by commas, or `()` for the empty tuple.210    tuple: Tuple,211    /// A dictionary display, such as `{"a": 1}`.212    dict: Dict,213    /// An index or a slice applied to a value, such as `xs[0]` or `xs[1:3]`.214    subscript: Subscript,215};216217/// An operator applied to one operand. The compiler emits the operand's instructions and then one218/// instruction for the operator.219pub const Unary = struct {220    /// Which operator: unary minus or `not`.221    op: UnaryOp,222    /// The operand.223    operand: *const Expression,224};225226/// The two unary operators of the subset. The compiler picks the instruction for a `Unary` node227/// from it. The parser binds `not` more loosely than comparisons. The parser binds unary minus more228/// tightly than `*`.229pub const UnaryOp = enum {230    /// Unary minus, as in `-x`. Negating the smallest 128-bit integer fails with `IntegerOverflow`231    /// when the program runs.232    negate,233    /// `not`, which gives `True` when its operand is false and `False` otherwise.234    not,235};236237/// An arithmetic operator applied to two operands. The compiler emits both operands' instructions,238/// left first, and then one instruction for the operator. Operators of one precedence level group239/// from the left, so `1 - 2 - 3` is `(1 - 2) - 3`.240pub const Binary = struct {241    /// Which operator.242    op: BinaryOp,243    /// The left operand, evaluated first.244    left: *const Expression,245    /// The right operand.246    right: *const Expression,247};248249/// The three arithmetic operators of the subset: `+`, `-` and `*`. The compiler picks the250/// instruction for a `Binary` node from it. Integer results past the signed 128-bit range fail with251/// `IntegerOverflow` when the program runs.252pub const BinaryOp = enum {253    /// `+`: integer addition, or joining two strings, two lists or two tuples.254    add,255    /// `-`: integer subtraction.256    sub,257    /// `*`: integer multiplication, or a string, list or tuple repeated an integer number of times.258    /// The count can stand on either side of `*`.259    mul,260};261262/// A chain of comparisons: a first operand, then each operator with its right operand. The compiler263/// turns one chain into pairwise tests that stop at the first false one. `a < b < c` tests `a < b`264/// and then `b < c`. Each operand is evaluated once. The parser builds one only when at least one265/// operator follows the first operand.266pub const Comparison = struct {267    /// The first operand of the chain.268    left: *const Expression,269    /// Each operator with its right operand, in source order. The slice holds at least one.270    terms: []const ComparisonTerm,271};272273/// One operator of a comparison chain with the operand to its right. A `Comparison` holds one per274/// operator of the chain. For the first term, the left operand is the chain's first operand. For275/// every later term, the left operand is the previous term's right operand.276pub const ComparisonTerm = struct {277    /// The comparison operator.278    op: ComparisonOp,279    /// The operand to the right of the operator.280    right: *const Expression,281};282283/// The ten comparison operators of the subset. The compiler maps each tag to one comparison284/// instruction.285pub const ComparisonOp = enum {286    /// `==`.287    equal,288    /// `!=`.289    not_equal,290    /// `<`.291    less,292    /// `<=`.293    less_equal,294    /// `>`.295    greater,296    /// `>=`.297    greater_equal,298    /// `in`, a membership test: true when the right operand holds the left operand.299    contains,300    /// `not in`, the negated membership test.301    not_contains,302    /// `is`, an identity test.303    identical,304    /// `is not`, the negated identity test.305    not_identical,306};307308/// `and` or `or` applied to two operands. The compiler turns one into a test of the left operand309/// and a jump past the right one. The right operand is evaluated only when the left one does not310/// decide the result. The result is the deciding operand's own value, so `0 and x` gives 0 and311/// `None or 9` gives 9. A chain such as `a or b or c` groups from the left.312pub const Logical = struct {313    /// Which operator.314    op: LogicalOp,315    /// The left operand, always evaluated.316    left: *const Expression,317    /// The right operand, evaluated only when the left one does not decide the result.318    right: *const Expression,319};320321/// The two operators that evaluate their right operand only when needed. The compiler picks the322/// jump pattern for a `Logical` node from it.323pub const LogicalOp = enum {324    /// `and`: gives the left operand when it is false, and otherwise gives the right operand.325    and_op,326    /// `or`: gives the left operand when it is true, and otherwise gives the right operand.327    or_op,328};329330/// A call: the called value and its arguments. The compiler emits the called value, then each331/// argument in order, then one call instruction with the argument count. Each argument is one332/// expression passed by position. A trailing comma after the last argument is allowed.333pub const Call = struct {334    /// The expression that gives the function or method to call.335    target: *const Expression,336    /// The argument expressions in order. For a call without arguments, the list is empty.337    arguments: []const *const Expression,338};339340/// An attribute access: a value and the name after the dot. The compiler turns one into an341/// instruction that looks the name up on the value, so a method call such as `xs.append(1)` finds342/// its method. When the program runs, the name resolves to one of the methods of a list or343/// dictionary.344pub const Attribute = struct {345    /// The expression before the dot.346    target: *const Expression,347    /// The name after the dot, as a slice of the source text.348    name: []const u8,349};350351/// A list display: the item expressions between `[` and `]`. The compiler emits each item and then352/// one instruction that builds a list of that many items.353pub const List = struct {354    /// The item expressions in order. For `[]`, the list is empty. A trailing comma after the last355    /// item is allowed.356    items: []const *const Expression,357};358359/// A tuple: expressions separated by commas, or `()` for the empty tuple. The compiler emits each360/// item and then one instruction that builds a tuple of that many items. Parentheses around one361/// expression with no comma only group it. `(1,)` is a tuple of one item.362pub const Tuple = struct {363    /// The item expressions in order. For `()`, the list is empty.364    items: []const *const Expression,365};366367/// A dictionary display: the key and value pairs between `{` and `}`. The compiler emits each key368/// and value in order and then one instruction that builds a dictionary of that many entries.369pub const Dict = struct {370    /// The entries in source order. For `{}`, the list is empty. A trailing comma after the last371    /// entry is allowed. When a key repeats, the later value replaces the earlier one at run time.372    items: []const DictItem,373};374375/// One entry of a dictionary display: a key expression and a value expression. A `Dict` holds one376/// per entry of the display.377pub const DictItem = struct {378    /// The key expression, before the `:`.379    key: *const Expression,380    /// The value expression, after the `:`.381    value: *const Expression,382};383384/// A value followed by brackets that hold one index or a slice. The compiler emits the value, then385/// the index or the three slice bounds, then one instruction that reads the item or the slice.386pub const Subscript = struct {387    /// The expression before the brackets.388    target: *const Expression,389    /// What the brackets hold: one index or a slice.390    selector: SubscriptSelector,391};392393/// The contents of a subscript's brackets: one index expression or a slice. The compiler emits an394/// index read or a slice read depending on its tag. A colon inside the brackets makes it a slice. A395/// comma inside the brackets fails to parse with `ExpectedRightBracket`.396pub const SubscriptSelector = union(enum) {397    /// The index expression, as in `xs[0]`.398    index: *const Expression,399    /// A slice, as in `xs[1:3]`.400    slice: Slice,401};402403/// The three bounds of a slice, each optional. A `SubscriptSelector` holds one for a subscript with404/// a colon. A bound left out is `null`, so every bound of `xs[:]` is `null`. The compiler passes405/// `None` for each bound left out.406pub const Slice = struct {407    /// The index of the first item taken. When the start is left out, as in `xs[:2]`, the field is408    /// `null`.409    start: ?*const Expression,410    /// The index the slice stops before. When the stop is left out, as in `xs[1:]`, the field is411    /// `null`.412    stop: ?*const Expression,413    /// The distance between the indexes taken. When the step is left out, as in `xs[1:3]` or414    /// `xs[1:3:]`, the field is `null`.415    step: ?*const Expression,416};417418test "expression tags are stable" {419    const value = Expression{ .integer = 7 };420    try std.testing.expectEqual(@as(i128, 7), value.integer);421}

1pub const ast = @import("ast.zig");