lib/python/src/syntax/ast.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! A Python program in the package's subset parses into a syntax tree. The program is a list of
2 //! statements. Statements hold expressions and nested lists of statements. Each expression is a
3 //! tree of operators and operands.
4 //!
5 //! The compiler walks the tree once to emit instructions, so every construct of the subset needs a
6 //! 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 covers
11 //! every construct. A child expression is a pointer to a constant node. A list of children is a
12 //! 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 has
16 //! no `else`, that field is empty. An `elif` is stored as an `if` statement that is the only
17 //! statement of the previous `if`'s `otherwise` list.
18 const std = @import("std");
19
20 /// 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`.
22 pub 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,
28
29 /// Frees every node of the tree at once by freeing the arena. The package's `execute` calls it
30 /// as it returns, after the bytecode compiled from the tree is freed. The call leaves the
31 /// program undefined. Every slice taken from the tree's lists is invalid afterward. The
32 /// bytecode that `compile` builds borrows each function's parameter list from the arena, so the
33 /// tree has to outlive that bytecode. The source text stays the caller's, and `deinit` leaves
34 /// it alone.
35 pub fn deinit(self: *Program) void {
36 self.arena.deinit();
37 self.* = undefined;
38 }
39 };
40
41 /// One statement of the subset, as a tagged union with one tag per kind of statement. The compiler
42 /// switches on its tag to emit each statement's instructions. `parse` builds one for each statement
43 /// of the program.
44 pub const Statement = union(enum) {
45 /// An expression statement: an expression evaluated for its value. At the top level, the value
46 /// 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 };
71
72 /// An assignment of a value to one name. The compiler turns one into a store to the name. The
73 /// target is a single name. `a, b = 1, 2` fails to parse with `UnexpectedToken`, because its left
74 /// side is a tuple.
75 pub 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 };
81
82 /// An assignment to one item selected by an index, such as `xs[0] = 2` or `d["k"] = v`. The
83 /// compiler turns one into a store into a list or dictionary. A slice is never a target, so
84 /// `xs[0:1] = [2]` fails to parse with `UnexpectedToken`.
85 pub 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 };
93
94 /// The target of a `del` statement: one name, or one item selected by an index. The compiler turns
95 /// one into the removal of a name or of an item. A `del` takes one target. For any other target, a
96 /// slice included, parsing fails with `UnexpectedToken`.
97 pub 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 };
103
104 /// 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.
106 pub 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 };
112
113 /// A function definition: its name, its parameter names and its body. The compiler turns each one
114 /// 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.
116 pub 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 without
120 /// 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 };
125
126 /// 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.
129 pub 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, so
133 /// `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 is
139 /// empty.
140 otherwise: []const Statement,
141 };
142
143 /// 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 does
145 /// not run.
146 pub 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 };
156
157 /// A `return` statement and its optional value. The compiler turns one into leaving the function
158 /// with a value.
159 pub const Return = struct {
160 /// The returned expression. For a bare `return`, the field is `null`. A bare `return` returns
161 /// `None`.
162 value: ?*const Expression,
163 };
164
165 /// A `while` loop: its condition, its body and its `else` branch. The compiler turns one into a
166 /// test at the top of each pass and a jump back.
167 pub const WhileStatement = struct {
168 /// The expression tested for truth before each pass. The condition is one expression with no
169 /// 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. When
174 /// `break` ends the loop, the branch is skipped. When the loop has no `else`, the list is
175 /// empty.
176 otherwise: []const Statement,
177 };
178
179 /// One expression, as a tagged union with one tag per kind of expression. The compiler switches on
180 /// its tag to emit the instructions that compute each value. `parse` allocates each node in the
181 /// program's arena. A node points to its children as constant nodes.
182 pub 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, so
188 /// `-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 source
191 /// 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 };
216
217 /// An operator applied to one operand. The compiler emits the operand's instructions and then one
218 /// instruction for the operator.
219 pub const Unary = struct {
220 /// Which operator: unary minus or `not`.
221 op: UnaryOp,
222 /// The operand.
223 operand: *const Expression,
224 };
225
226 /// The two unary operators of the subset. The compiler picks the instruction for a `Unary` node
227 /// from it. The parser binds `not` more loosely than comparisons. The parser binds unary minus more
228 /// tightly than `*`.
229 pub 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 };
236
237 /// 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 group
239 /// from the left, so `1 - 2 - 3` is `(1 - 2) - 3`.
240 pub 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 };
248
249 /// The three arithmetic operators of the subset: `+`, `-` and `*`. The compiler picks the
250 /// instruction for a `Binary` node from it. Integer results past the signed 128-bit range fail with
251 /// `IntegerOverflow` when the program runs.
252 pub 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 };
261
262 /// A chain of comparisons: a first operand, then each operator with its right operand. The compiler
263 /// 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 one
265 /// operator follows the first operand.
266 pub 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 };
272
273 /// One operator of a comparison chain with the operand to its right. A `Comparison` holds one per
274 /// operator of the chain. For the first term, the left operand is the chain's first operand. For
275 /// every later term, the left operand is the previous term's right operand.
276 pub const ComparisonTerm = struct {
277 /// The comparison operator.
278 op: ComparisonOp,
279 /// The operand to the right of the operator.
280 right: *const Expression,
281 };
282
283 /// The ten comparison operators of the subset. The compiler maps each tag to one comparison
284 /// instruction.
285 pub 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 };
307
308 /// `and` or `or` applied to two operands. The compiler turns one into a test of the left operand
309 /// and a jump past the right one. The right operand is evaluated only when the left one does not
310 /// decide the result. The result is the deciding operand's own value, so `0 and x` gives 0 and
311 /// `None or 9` gives 9. A chain such as `a or b or c` groups from the left.
312 pub 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 };
320
321 /// The two operators that evaluate their right operand only when needed. The compiler picks the
322 /// jump pattern for a `Logical` node from it.
323 pub 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 };
329
330 /// A call: the called value and its arguments. The compiler emits the called value, then each
331 /// argument in order, then one call instruction with the argument count. Each argument is one
332 /// expression passed by position. A trailing comma after the last argument is allowed.
333 pub 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 };
339
340 /// An attribute access: a value and the name after the dot. The compiler turns one into an
341 /// instruction that looks the name up on the value, so a method call such as `xs.append(1)` finds
342 /// its method. When the program runs, the name resolves to one of the methods of a list or
343 /// dictionary.
344 pub 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 };
350
351 /// A list display: the item expressions between `[` and `]`. The compiler emits each item and then
352 /// one instruction that builds a list of that many items.
353 pub const List = struct {
354 /// The item expressions in order. For `[]`, the list is empty. A trailing comma after the last
355 /// item is allowed.
356 items: []const *const Expression,
357 };
358
359 /// A tuple: expressions separated by commas, or `()` for the empty tuple. The compiler emits each
360 /// item and then one instruction that builds a tuple of that many items. Parentheses around one
361 /// expression with no comma only group it. `(1,)` is a tuple of one item.
362 pub const Tuple = struct {
363 /// The item expressions in order. For `()`, the list is empty.
364 items: []const *const Expression,
365 };
366
367 /// A dictionary display: the key and value pairs between `{` and `}`. The compiler emits each key
368 /// and value in order and then one instruction that builds a dictionary of that many entries.
369 pub const Dict = struct {
370 /// The entries in source order. For `{}`, the list is empty. A trailing comma after the last
371 /// entry is allowed. When a key repeats, the later value replaces the earlier one at run time.
372 items: []const DictItem,
373 };
374
375 /// One entry of a dictionary display: a key expression and a value expression. A `Dict` holds one
376 /// per entry of the display.
377 pub const DictItem = struct {
378 /// The key expression, before the `:`.
379 key: *const Expression,
380 /// The value expression, after the `:`.
381 value: *const Expression,
382 };
383
384 /// A value followed by brackets that hold one index or a slice. The compiler emits the value, then
385 /// the index or the three slice bounds, then one instruction that reads the item or the slice.
386 pub 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 };
392
393 /// The contents of a subscript's brackets: one index expression or a slice. The compiler emits an
394 /// index read or a slice read depending on its tag. A colon inside the brackets makes it a slice. A
395 /// comma inside the brackets fails to parse with `ExpectedRightBracket`.
396 pub 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 };
402
403 /// The three bounds of a slice, each optional. A `SubscriptSelector` holds one for a subscript with
404 /// a colon. A bound left out is `null`, so every bound of `xs[:]` is `null`. The compiler passes
405 /// `None` for each bound left out.
406 pub const Slice = struct {
407 /// The index of the first item taken. When the start is left out, as in `xs[:2]`, the field is
408 /// `null`.
409 start: ?*const Expression,
410 /// The index the slice stops before. When the stop is left out, as in `xs[1:]`, the field is
411 /// `null`.
412 stop: ?*const Expression,
413 /// The distance between the indexes taken. When the step is left out, as in `xs[1:3]` or
414 /// `xs[1:3:]`, the field is `null`.
415 step: ?*const Expression,
416 };
417
418 test "expression tags are stable" {
419 const value = Expression{ .integer = 7 };
420 try std.testing.expectEqual(@as(i128, 7), value.integer);
421 }