lib/python/src/syntax/parser.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! The parser reads the token list of a Python program and builds its syntax tree: a list of
2 //! statements whose expressions are trees of operators and operands. The parser has to settle
3 //! operator precedence and block nesting, so the compiler can emit instructions in one walk over
4 //! the tree. For anything outside the package's subset, the parser has to return an error that
5 //! names what it expected.
6 //!
7 //! An assignment's target is known only when the `=` arrives, after the expression before it has
8 //! been read. A tree has one node per operator, name and literal, and the parser learns how many
9 //! only as it reads. Every node stays in use until the caller is done with the whole tree.
10 //!
11 //! The parser's precedence levels follow the grammar of the [Python 3.14 language
12 //! reference](https://docs.python.org/3.14/reference/), from loosest to tightest: `or`, `and`,
13 //! `not`, comparisons, `+` and `-`, `*`, unary minus, and then calls, subscripts and attribute
14 //! access. Comparisons chain as the reference defines them. `a < b <= c` becomes one node that
15 //! keeps every operator with its right operand. That node lets the compiler test each pair and
16 //! evaluate each operand once.
17 //!
18 //! The parser is written by hand as recursive descent, with one function per precedence level. The
19 //! parser looks one token ahead. To tell `not in` from `not`, the parser looks two tokens ahead.
20 //! The parser reads the left side of `=` as an ordinary expression. The parser accepts that
21 //! expression as the target only when it is a name or a subscript with one index.
22 //!
23 //! Every node goes into one arena allocator. The returned tree, `Program`, owns the arena, so its
24 //! `deinit` frees the whole tree at once. Names and string contents in the tree are slices of the
25 //! source text, so the text has to outlive the tree. The tree keeps no pointer into the token list,
26 //! so the caller can free the tokens as soon as the parser returns.
27 //!
28 //! A block's body starts on its own indented line after the colon, so `if x: pass` on one line
29 //! fails. The body's first statement has to sit on the line right after the colon's line. Parsing
30 //! fails on a blank or comment-only line in between. Nesting has no depth limit. Each level of
31 //! nesting in the text takes stack frames of the calling thread. An error carries no position in
32 //! the text.
33 const std = @import("std");
34 const source = @import("../source/root.zig");
35 const ast = @import("ast.zig");
36
37 /// The errors `parse` returns when the tokens do not form a program of the subset, besides running
38 /// out of memory. A caller switches on it to report why the tokens do not form a program. Each
39 /// names what the parser expected at the token where it stopped. None carries a position in the
40 /// text.
41 pub const Error = error{
42 /// An expression was due and the next token cannot start one, as in `x =` with nothing after
43 /// it. The parser also returns this error for an indent token where no block opens, as on an
44 /// indented first line.
45 ExpectedExpression,
46 /// A block header without its `:`, after the condition of `if`, `elif` or `while`, the iterable
47 /// of `for`, the parameters of `def`, or `else`. The parser also returns this error for a
48 /// dictionary entry whose key has no `:` after it, as in `{"a"}`.
49 ExpectedColon,
50 /// A `def` parameter or a call argument that neither `,` nor `)` follows.
51 ExpectedCommaOrRightParen,
52 /// A list item that neither `,` nor `]` follows.
53 ExpectedCommaOrRightBracket,
54 /// A dictionary entry that neither `,` nor `}` follows, as in `{"a": 1 "b": 2}`.
55 ExpectedCommaOrRightBrace,
56 /// A block's body that no dedent token closes. `tokenize` closes every open block before the
57 /// end-of-input token, so only a token list built another way produces this error.
58 ExpectedDedent,
59 /// A name was due after `def`, after `for`, in a parameter list, or after `.`, and another
60 /// token came.
61 ExpectedIdentifier,
62 /// A `for` loop's name that `in` does not follow.
63 ExpectedIn,
64 /// A block header's colon and line break that an indent token does not follow. A body indented
65 /// no deeper than its header gets this error. The parser also returns it for a blank or
66 /// comment-only line before the body's first statement.
67 ExpectedIndent,
68 /// A `def` name that `(` does not follow.
69 ExpectedLeftParen,
70 /// More tokens on the line after a complete simple statement, as with two statements on one
71 /// line. The parser also returns this error for more tokens on the line after a block header's
72 /// colon, as in `if x: pass`.
73 ExpectedNewline,
74 /// A parenthesized expression that `)` does not close.
75 ExpectedRightParen,
76 /// A subscript that `]` does not close. A comma inside a subscript, as in `xs[0, 1]`, fails
77 /// this way.
78 ExpectedRightBracket,
79 /// An integer literal too large for a signed 128-bit integer.
80 InvalidInteger,
81 /// An assignment whose left side is neither a name nor a subscript with one index. `[1] = 2`
82 /// and `xs[0:1] = [2]` fail this way. The parser also returns this error for a `del` whose
83 /// target is neither a name nor a subscript with one index. `del [1]` and `del xs[0:1]` fail
84 /// this way.
85 UnexpectedToken,
86 };
87
88 /// Builds the syntax tree of a program from its source text and the tokens made from that text. The
89 /// package's `execute` calls `parse` on the tokens `tokenize` returned, and a caller that wants a
90 /// program's tree calls it the same way. `parse` returns the tree as a `Program`. `bytes` has to be
91 /// the text the tokens came from. The tokens have to end with the end-of-input token, as `tokenize`
92 /// returns them. `parse` allocates every node from an arena on the given allocator. The returned
93 /// `Program` owns the arena. The tree borrows `bytes`: names and string contents are slices of it,
94 /// so `bytes` has to outlive the `Program`. The tree keeps no pointer to `tokens`, so the caller
95 /// can free them once `parse` returns. `parse` returns one of the `Error` values when the tokens do
96 /// not form a program of the subset. The function returns `error.OutOfMemory` when an allocation
97 /// fails. On any error the function frees the arena. `parse` recurses once per level of nesting in
98 /// the program. The recursion has no depth limit.
99 pub fn parse(allocator: std.mem.Allocator, bytes: []const u8, tokens: []const source.Token) (Error || std.mem.Allocator.Error)!ast.Program {
100 var arena = std.heap.ArenaAllocator.init(allocator);
101 errdefer arena.deinit();
102
103 var parser = Parser{
104 .source = bytes,
105 .tokens = tokens,
106 .arena = arena.allocator(),
107 };
108 const statements = try parser.program();
109 return .{
110 .arena = arena,
111 .statements = statements,
112 };
113 }
114
115 const Parser = struct {
116 source: []const u8,
117 tokens: []const source.Token,
118 index: usize = 0,
119 arena: std.mem.Allocator,
120
121 fn program(self: *Parser) (Error || std.mem.Allocator.Error)![]const ast.Statement {
122 return try self.block(false);
123 }
124
125 fn block(self: *Parser, stop_on_dedent: bool) (Error || std.mem.Allocator.Error)![]const ast.Statement {
126 var statements = std.ArrayListUnmanaged(ast.Statement).empty;
127 while (self.match(.newline)) {}
128 while (!self.at(.eof) and !(stop_on_dedent and self.at(.dedent))) {
129 const parsed = try self.statement();
130 try statements.append(self.arena, parsed);
131 if (self.at(.eof) or (stop_on_dedent and self.at(.dedent))) break;
132 if (!compound(parsed) or self.at(.newline)) {
133 if (!self.match(.newline)) return Error.ExpectedNewline;
134 }
135 while (self.match(.newline)) {}
136 }
137 return try statements.toOwnedSlice(self.arena);
138 }
139
140 fn statement(self: *Parser) (Error || std.mem.Allocator.Error)!ast.Statement {
141 if (self.match(.break_kw)) return .break_stmt;
142 if (self.match(.continue_kw)) return .continue_stmt;
143 if (self.match(.del_kw)) return try self.deleteStatement();
144 if (self.match(.def_kw)) return try self.function();
145 if (self.match(.for_kw)) return try self.forStatement();
146 if (self.match(.if_kw)) return try self.ifStatement();
147 if (self.match(.pass_kw)) return .pass;
148 if (self.match(.return_kw)) return try self.returnStatement();
149 if (self.match(.while_kw)) return try self.whileStatement();
150 const target = try self.expression();
151 if (self.match(.equal)) {
152 const value = try self.expression();
153 return switch (target.*) {
154 .name => |name| .{ .assign = .{
155 .name = name,
156 .value = value,
157 } },
158 .subscript => |subscript| .{ .subscript_assign = .{
159 .target = subscript.target,
160 .index = switch (subscript.selector) {
161 .index => |index| index,
162 .slice => return Error.UnexpectedToken,
163 },
164 .value = value,
165 } },
166 else => Error.UnexpectedToken,
167 };
168 }
169 return .{ .expression = target };
170 }
171
172 fn deleteStatement(self: *Parser) (Error || std.mem.Allocator.Error)!ast.Statement {
173 const target = try self.expression();
174 return .{ .delete = switch (target.*) {
175 .name => |name| .{ .name = name },
176 .subscript => |subscript| .{ .subscript = .{
177 .target = subscript.target,
178 .index = switch (subscript.selector) {
179 .index => |index| index,
180 .slice => return Error.UnexpectedToken,
181 },
182 } },
183 else => return Error.UnexpectedToken,
184 } };
185 }
186
187 fn ifStatement(self: *Parser) (Error || std.mem.Allocator.Error)!ast.Statement {
188 return try self.ifTail();
189 }
190
191 fn ifTail(self: *Parser) (Error || std.mem.Allocator.Error)!ast.Statement {
192 const condition = try self.singleExpression();
193 const body = try self.suite();
194 const otherwise = try self.ifOtherwise();
195 return .{ .if_stmt = .{
196 .condition = condition,
197 .body = body,
198 .otherwise = otherwise,
199 } };
200 }
201
202 fn ifOtherwise(self: *Parser) (Error || std.mem.Allocator.Error)![]const ast.Statement {
203 if (self.match(.elif_kw)) {
204 const statement_node = try self.ifTail();
205 const statements = try self.arena.alloc(ast.Statement, 1);
206 statements[0] = statement_node;
207 return statements;
208 }
209 if (self.match(.else_kw)) return try self.suite();
210 return &.{};
211 }
212
213 fn function(self: *Parser) (Error || std.mem.Allocator.Error)!ast.Statement {
214 const name = try self.expectIdentifier();
215 if (!self.match(.lparen)) return Error.ExpectedLeftParen;
216 const params = try self.parameters();
217 const body = try self.suite();
218 return .{ .function = .{
219 .name = name,
220 .params = params,
221 .body = body,
222 } };
223 }
224
225 fn forStatement(self: *Parser) (Error || std.mem.Allocator.Error)!ast.Statement {
226 const name = try self.expectIdentifier();
227 if (!self.match(.in_kw)) return Error.ExpectedIn;
228 const iterable = try self.singleExpression();
229 const body = try self.suite();
230 const otherwise = if (self.match(.else_kw)) try self.suite() else &.{};
231 return .{ .for_stmt = .{
232 .name = name,
233 .iterable = iterable,
234 .body = body,
235 .otherwise = otherwise,
236 } };
237 }
238
239 fn parameters(self: *Parser) (Error || std.mem.Allocator.Error)![]const []const u8 {
240 var params = std.ArrayListUnmanaged([]const u8).empty;
241 if (self.match(.rparen)) return try params.toOwnedSlice(self.arena);
242 while (true) {
243 try params.append(self.arena, try self.expectIdentifier());
244 if (self.match(.rparen)) break;
245 if (!self.match(.comma)) return Error.ExpectedCommaOrRightParen;
246 if (self.match(.rparen)) break;
247 }
248 return try params.toOwnedSlice(self.arena);
249 }
250
251 fn returnStatement(self: *Parser) (Error || std.mem.Allocator.Error)!ast.Statement {
252 if (self.at(.newline) or self.at(.dedent) or self.at(.eof)) {
253 return .{ .return_stmt = .{ .value = null } };
254 }
255 return .{ .return_stmt = .{ .value = try self.expression() } };
256 }
257
258 fn whileStatement(self: *Parser) (Error || std.mem.Allocator.Error)!ast.Statement {
259 const condition = try self.singleExpression();
260 const body = try self.suite();
261 const otherwise = if (self.match(.else_kw)) try self.suite() else &.{};
262 return .{ .while_stmt = .{
263 .condition = condition,
264 .body = body,
265 .otherwise = otherwise,
266 } };
267 }
268
269 fn suite(self: *Parser) (Error || std.mem.Allocator.Error)![]const ast.Statement {
270 if (!self.match(.colon)) return Error.ExpectedColon;
271 if (!self.match(.newline)) return Error.ExpectedNewline;
272 if (!self.match(.indent)) return Error.ExpectedIndent;
273 const body = try self.block(true);
274 if (!self.match(.dedent)) return Error.ExpectedDedent;
275 return body;
276 }
277
278 fn expression(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
279 return try self.tupleExpression();
280 }
281
282 fn tupleExpression(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
283 const first = try self.singleExpression();
284 if (!self.match(.comma)) return first;
285 var items = std.ArrayListUnmanaged(*const ast.Expression).empty;
286 try items.append(self.arena, first);
287 while (!self.tupleTerminator()) {
288 try items.append(self.arena, try self.singleExpression());
289 if (!self.match(.comma)) break;
290 }
291 return try self.leaf(.{ .tuple = .{ .items = try items.toOwnedSlice(self.arena) } });
292 }
293
294 fn singleExpression(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
295 return try self.disjunction();
296 }
297
298 fn disjunction(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
299 var node = try self.conjunction();
300 while (self.match(.or_kw)) {
301 node = try self.logical(.or_op, node, try self.conjunction());
302 }
303 return node;
304 }
305
306 fn conjunction(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
307 var node = try self.inversion();
308 while (self.match(.and_kw)) {
309 node = try self.logical(.and_op, node, try self.inversion());
310 }
311 return node;
312 }
313
314 fn inversion(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
315 if (self.match(.not_kw)) {
316 const operand = try self.inversion();
317 const node = try self.arena.create(ast.Expression);
318 node.* = .{ .unary = .{ .op = .not, .operand = operand } };
319 return node;
320 }
321 return try self.comparison();
322 }
323
324 fn comparison(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
325 const left = try self.term();
326 var terms = std.ArrayListUnmanaged(ast.ComparisonTerm).empty;
327 while (self.matchComparison()) |op| {
328 try terms.append(self.arena, .{
329 .op = op,
330 .right = try self.term(),
331 });
332 }
333 if (terms.items.len == 0) return left;
334 const node = try self.arena.create(ast.Expression);
335 node.* = .{ .comparison = .{
336 .left = left,
337 .terms = try terms.toOwnedSlice(self.arena),
338 } };
339 return node;
340 }
341
342 fn term(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
343 var node = try self.factor();
344 while (self.match(.plus) or self.match(.minus)) {
345 const op: ast.BinaryOp = if (self.previous().tag == .plus) .add else .sub;
346 node = try self.binary(op, node, try self.factor());
347 }
348 return node;
349 }
350
351 fn factor(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
352 var node = try self.unary();
353 while (self.match(.star)) {
354 node = try self.binary(.mul, node, try self.unary());
355 }
356 return node;
357 }
358
359 fn unary(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
360 if (self.match(.minus)) {
361 const operand = try self.unary();
362 const node = try self.arena.create(ast.Expression);
363 node.* = .{ .unary = .{ .op = .negate, .operand = operand } };
364 return node;
365 }
366 return try self.call();
367 }
368
369 fn call(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
370 var node = try self.primary();
371 while (true) {
372 if (self.match(.lparen)) {
373 const call_arguments = try self.arguments();
374 const call_node = try self.arena.create(ast.Expression);
375 call_node.* = .{ .call = .{
376 .target = node,
377 .arguments = call_arguments,
378 } };
379 node = call_node;
380 } else if (self.match(.lbracket)) {
381 const selector = try self.subscriptSelector();
382 if (!self.match(.rbracket)) return Error.ExpectedRightBracket;
383 const subscript_node = try self.arena.create(ast.Expression);
384 subscript_node.* = .{ .subscript = .{
385 .target = node,
386 .selector = selector,
387 } };
388 node = subscript_node;
389 } else if (self.match(.dot)) {
390 const name = try self.expectIdentifier();
391 const attribute_node = try self.arena.create(ast.Expression);
392 attribute_node.* = .{ .attribute = .{
393 .target = node,
394 .name = name,
395 } };
396 node = attribute_node;
397 } else {
398 break;
399 }
400 }
401 return node;
402 }
403
404 fn subscriptSelector(self: *Parser) (Error || std.mem.Allocator.Error)!ast.SubscriptSelector {
405 if (self.match(.colon)) {
406 const stop = try self.optionalSliceExpression();
407 const step = if (self.match(.colon)) try self.optionalSliceExpression() else null;
408 return .{ .slice = .{
409 .start = null,
410 .stop = stop,
411 .step = step,
412 } };
413 }
414 const first = try self.singleExpression();
415 if (!self.match(.colon)) return .{ .index = first };
416 const stop = try self.optionalSliceExpression();
417 const step = if (self.match(.colon)) try self.optionalSliceExpression() else null;
418 return .{ .slice = .{
419 .start = first,
420 .stop = stop,
421 .step = step,
422 } };
423 }
424
425 fn optionalSliceExpression(self: *Parser) (Error || std.mem.Allocator.Error)!?*const ast.Expression {
426 if (self.at(.colon) or self.at(.rbracket)) return null;
427 return try self.singleExpression();
428 }
429
430 fn arguments(self: *Parser) (Error || std.mem.Allocator.Error)![]const *const ast.Expression {
431 var args = std.ArrayListUnmanaged(*const ast.Expression).empty;
432 if (self.match(.rparen)) return try args.toOwnedSlice(self.arena);
433 while (true) {
434 try args.append(self.arena, try self.singleExpression());
435 if (self.match(.rparen)) break;
436 if (!self.match(.comma)) return Error.ExpectedCommaOrRightParen;
437 if (self.match(.rparen)) break;
438 }
439 return try args.toOwnedSlice(self.arena);
440 }
441
442 fn primary(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
443 if (self.match(.integer)) {
444 const value = std.fmt.parseInt(i128, self.previous().span.text(self.source), 10) catch return Error.InvalidInteger;
445 return try self.leaf(.{ .integer = value });
446 }
447 if (self.match(.string)) {
448 const text = self.previous().span.text(self.source);
449 return try self.leaf(.{ .string = text[1 .. text.len - 1] });
450 }
451 if (self.match(.identifier)) {
452 return try self.leaf(.{ .name = self.previous().span.text(self.source) });
453 }
454 if (self.match(.true_kw)) return try self.leaf(.{ .boolean = true });
455 if (self.match(.false_kw)) return try self.leaf(.{ .boolean = false });
456 if (self.match(.none_kw)) return try self.leaf(.none);
457 if (self.match(.lbracket)) return try self.listDisplay();
458 if (self.match(.lbrace)) return try self.dictDisplay();
459 if (self.match(.lparen)) {
460 if (self.match(.rparen)) return try self.leaf(.{ .tuple = .{ .items = &.{} } });
461 const node = try self.expression();
462 if (!self.match(.rparen)) return Error.ExpectedRightParen;
463 return node;
464 }
465 return Error.ExpectedExpression;
466 }
467
468 fn listDisplay(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
469 var items = std.ArrayListUnmanaged(*const ast.Expression).empty;
470 if (self.match(.rbracket)) return try self.leaf(.{ .list = .{ .items = try items.toOwnedSlice(self.arena) } });
471 while (true) {
472 try items.append(self.arena, try self.singleExpression());
473 if (self.match(.rbracket)) break;
474 if (!self.match(.comma)) return Error.ExpectedCommaOrRightBracket;
475 if (self.match(.rbracket)) break;
476 }
477 return try self.leaf(.{ .list = .{ .items = try items.toOwnedSlice(self.arena) } });
478 }
479
480 fn dictDisplay(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {
481 var items = std.ArrayListUnmanaged(ast.DictItem).empty;
482 if (self.match(.rbrace)) return try self.leaf(.{ .dict = .{ .items = try items.toOwnedSlice(self.arena) } });
483 while (true) {
484 const key = try self.singleExpression();
485 if (!self.match(.colon)) return Error.ExpectedColon;
486 const value = try self.singleExpression();
487 try items.append(self.arena, .{
488 .key = key,
489 .value = value,
490 });
491 if (self.match(.rbrace)) break;
492 if (!self.match(.comma)) return Error.ExpectedCommaOrRightBrace;
493 if (self.match(.rbrace)) break;
494 }
495 return try self.leaf(.{ .dict = .{ .items = try items.toOwnedSlice(self.arena) } });
496 }
497
498 fn leaf(self: *Parser, expression_node: ast.Expression) std.mem.Allocator.Error!*const ast.Expression {
499 const node = try self.arena.create(ast.Expression);
500 node.* = expression_node;
501 return node;
502 }
503
504 fn binary(self: *Parser, op: ast.BinaryOp, left: *const ast.Expression, right: *const ast.Expression) std.mem.Allocator.Error!*const ast.Expression {
505 const node = try self.arena.create(ast.Expression);
506 node.* = .{ .binary = .{ .op = op, .left = left, .right = right } };
507 return node;
508 }
509
510 fn logical(self: *Parser, op: ast.LogicalOp, left: *const ast.Expression, right: *const ast.Expression) std.mem.Allocator.Error!*const ast.Expression {
511 const node = try self.arena.create(ast.Expression);
512 node.* = .{ .logical = .{ .op = op, .left = left, .right = right } };
513 return node;
514 }
515
516 fn expectIdentifier(self: *Parser) Error![]const u8 {
517 if (!self.match(.identifier)) return Error.ExpectedIdentifier;
518 return self.previous().span.text(self.source);
519 }
520
521 fn matchComparison(self: *Parser) ?ast.ComparisonOp {
522 if (self.match(.equal_equal)) return .equal;
523 if (self.match(.bang_equal)) return .not_equal;
524 if (self.match(.less)) return .less;
525 if (self.match(.less_equal)) return .less_equal;
526 if (self.match(.greater)) return .greater;
527 if (self.match(.greater_equal)) return .greater_equal;
528 if (self.match(.in_kw)) return .contains;
529 if (self.match(.is_kw)) {
530 if (self.match(.not_kw)) return .not_identical;
531 return .identical;
532 }
533 if (self.at(.not_kw) and self.peek(1).tag == .in_kw) {
534 _ = self.advance();
535 _ = self.advance();
536 return .not_contains;
537 }
538 return null;
539 }
540
541 fn tupleTerminator(self: *const Parser) bool {
542 return switch (self.peek(0).tag) {
543 .rparen, .rbracket, .newline, .dedent, .eof, .colon => true,
544 else => false,
545 };
546 }
547
548 fn match(self: *Parser, tag: source.Tag) bool {
549 if (!self.at(tag)) return false;
550 self.index += 1;
551 return true;
552 }
553
554 fn at(self: *const Parser, tag: source.Tag) bool {
555 return self.peek(0).tag == tag;
556 }
557
558 fn peek(self: *const Parser, offset: usize) source.Token {
559 const target = self.index + offset;
560 if (target >= self.tokens.len) return self.tokens[self.tokens.len - 1];
561 return self.tokens[target];
562 }
563
564 fn advance(self: *Parser) source.Token {
565 const token = self.peek(0);
566 self.index += 1;
567 return token;
568 }
569
570 fn previous(self: *const Parser) source.Token {
571 return self.tokens[self.index - 1];
572 }
573 };
574
575 fn compound(statement_node: ast.Statement) bool {
576 return switch (statement_node) {
577 .function, .for_stmt, .if_stmt, .while_stmt => true,
578 else => false,
579 };
580 }
581
582 test "parse assignments and precedence" {
583 var stream = try source.tokenize(std.testing.allocator, "x = 1 + 2 * 3\nx");
584 defer stream.deinit(std.testing.allocator);
585 var program_value = try parse(std.testing.allocator, "x = 1 + 2 * 3\nx", stream.tokens);
586 defer program_value.deinit();
587
588 try std.testing.expectEqual(@as(usize, 2), program_value.statements.len);
589 try std.testing.expectEqualStrings("x", program_value.statements[0].assign.name);
590 try std.testing.expect(program_value.statements[0].assign.value.* == .binary);
591 }
592
593 test "parse function with return and call" {
594 const bytes =
595 \\def add(a, b):
596 \\ return a + b
597 \\add(1, 2)
598 ;
599 var stream = try source.tokenize(std.testing.allocator, bytes);
600 defer stream.deinit(std.testing.allocator);
601 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
602 defer program_value.deinit();
603
604 try std.testing.expectEqual(@as(usize, 2), program_value.statements.len);
605 try std.testing.expectEqualStrings("add", program_value.statements[0].function.name);
606 try std.testing.expectEqual(@as(usize, 2), program_value.statements[0].function.params.len);
607 try std.testing.expect(program_value.statements[1].expression.* == .call);
608 }
609
610 test "parse if else and while" {
611 const bytes =
612 \\x = 0
613 \\while x < 3:
614 \\ if x == 1:
615 \\ x = x + 1
616 \\ else:
617 \\ pass
618 \\ x = x + 1
619 \\x
620 ;
621 var stream = try source.tokenize(std.testing.allocator, bytes);
622 defer stream.deinit(std.testing.allocator);
623 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
624 defer program_value.deinit();
625
626 try std.testing.expectEqual(@as(usize, 3), program_value.statements.len);
627 try std.testing.expect(program_value.statements[1] == .while_stmt);
628 try std.testing.expect(program_value.statements[1].while_stmt.condition.* == .comparison);
629 try std.testing.expect(program_value.statements[1].while_stmt.body[0] == .if_stmt);
630 try std.testing.expectEqual(@as(usize, 1), program_value.statements[1].while_stmt.body[0].if_stmt.otherwise.len);
631 }
632
633 test "parse loop control" {
634 const bytes =
635 \\for x in [1]:
636 \\ continue
637 \\ break
638 ;
639 var stream = try source.tokenize(std.testing.allocator, bytes);
640 defer stream.deinit(std.testing.allocator);
641 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
642 defer program_value.deinit();
643
644 try std.testing.expect(program_value.statements[0] == .for_stmt);
645 try std.testing.expectEqualStrings("x", program_value.statements[0].for_stmt.name);
646 try std.testing.expect(program_value.statements[0].for_stmt.iterable.* == .list);
647 try std.testing.expect(program_value.statements[0].for_stmt.body[0] == .continue_stmt);
648 try std.testing.expect(program_value.statements[0].for_stmt.body[1] == .break_stmt);
649 }
650
651 test "parse logical precedence" {
652 const bytes = "x = not 1 == 1 or 2 and 3";
653 var stream = try source.tokenize(std.testing.allocator, bytes);
654 defer stream.deinit(std.testing.allocator);
655 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
656 defer program_value.deinit();
657
658 const value = program_value.statements[0].assign.value;
659 try std.testing.expect(value.* == .logical);
660 try std.testing.expectEqual(ast.LogicalOp.or_op, value.logical.op);
661 try std.testing.expect(value.logical.left.* == .unary);
662 try std.testing.expectEqual(ast.UnaryOp.not, value.logical.left.unary.op);
663 try std.testing.expect(value.logical.left.unary.operand.* == .comparison);
664 try std.testing.expect(value.logical.right.* == .logical);
665 try std.testing.expectEqual(ast.LogicalOp.and_op, value.logical.right.logical.op);
666 }
667
668 test "parse chained comparisons" {
669 const bytes = "1 < x <= y != 4 is not z";
670 var stream = try source.tokenize(std.testing.allocator, bytes);
671 defer stream.deinit(std.testing.allocator);
672 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
673 defer program_value.deinit();
674
675 const value = program_value.statements[0].expression;
676 try std.testing.expect(value.* == .comparison);
677 try std.testing.expectEqual(@as(usize, 4), value.comparison.terms.len);
678 try std.testing.expectEqual(ast.ComparisonOp.less, value.comparison.terms[0].op);
679 try std.testing.expectEqual(ast.ComparisonOp.less_equal, value.comparison.terms[1].op);
680 try std.testing.expectEqual(ast.ComparisonOp.not_equal, value.comparison.terms[2].op);
681 try std.testing.expectEqual(ast.ComparisonOp.not_identical, value.comparison.terms[3].op);
682 }
683
684 test "parse membership comparisons" {
685 const bytes = "x in xs and y not in ys";
686 var stream = try source.tokenize(std.testing.allocator, bytes);
687 defer stream.deinit(std.testing.allocator);
688 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
689 defer program_value.deinit();
690
691 const value = program_value.statements[0].expression;
692 try std.testing.expect(value.* == .logical);
693 try std.testing.expect(value.logical.left.* == .comparison);
694 try std.testing.expectEqual(ast.ComparisonOp.contains, value.logical.left.comparison.terms[0].op);
695 try std.testing.expect(value.logical.right.* == .comparison);
696 try std.testing.expectEqual(ast.ComparisonOp.not_contains, value.logical.right.comparison.terms[0].op);
697 }
698
699 test "parse string literals" {
700 const bytes =
701 \\"alpha"
702 \\'beta'
703 ;
704 var stream = try source.tokenize(std.testing.allocator, bytes);
705 defer stream.deinit(std.testing.allocator);
706 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
707 defer program_value.deinit();
708
709 try std.testing.expectEqual(@as(usize, 2), program_value.statements.len);
710 try std.testing.expect(program_value.statements[0].expression.* == .string);
711 try std.testing.expectEqualStrings("alpha", program_value.statements[0].expression.string);
712 try std.testing.expectEqualStrings("beta", program_value.statements[1].expression.string);
713 }
714
715 test "parse tuple expressions" {
716 const bytes =
717 \\()
718 \\(1,)
719 \\(1, 2)
720 \\x = 1, 2
721 ;
722 var stream = try source.tokenize(std.testing.allocator, bytes);
723 defer stream.deinit(std.testing.allocator);
724 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
725 defer program_value.deinit();
726
727 try std.testing.expect(program_value.statements[0].expression.* == .tuple);
728 try std.testing.expectEqual(@as(usize, 0), program_value.statements[0].expression.tuple.items.len);
729 try std.testing.expect(program_value.statements[1].expression.* == .tuple);
730 try std.testing.expectEqual(@as(usize, 1), program_value.statements[1].expression.tuple.items.len);
731 try std.testing.expect(program_value.statements[2].expression.* == .tuple);
732 try std.testing.expectEqual(@as(usize, 2), program_value.statements[2].expression.tuple.items.len);
733 try std.testing.expect(program_value.statements[3].assign.value.* == .tuple);
734 try std.testing.expectEqual(@as(usize, 2), program_value.statements[3].assign.value.tuple.items.len);
735 }
736
737 test "parse list displays" {
738 const bytes =
739 \\[]
740 \\[1, x,]
741 ;
742 var stream = try source.tokenize(std.testing.allocator, bytes);
743 defer stream.deinit(std.testing.allocator);
744 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
745 defer program_value.deinit();
746
747 try std.testing.expect(program_value.statements[0].expression.* == .list);
748 try std.testing.expectEqual(@as(usize, 0), program_value.statements[0].expression.list.items.len);
749 try std.testing.expect(program_value.statements[1].expression.* == .list);
750 try std.testing.expectEqual(@as(usize, 2), program_value.statements[1].expression.list.items.len);
751 }
752
753 test "parse dictionary displays" {
754 const bytes =
755 \\{}
756 \\{"a": 1, "b": x,}
757 ;
758 var stream = try source.tokenize(std.testing.allocator, bytes);
759 defer stream.deinit(std.testing.allocator);
760 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
761 defer program_value.deinit();
762
763 try std.testing.expect(program_value.statements[0].expression.* == .dict);
764 try std.testing.expectEqual(@as(usize, 0), program_value.statements[0].expression.dict.items.len);
765 try std.testing.expect(program_value.statements[1].expression.* == .dict);
766 try std.testing.expectEqual(@as(usize, 2), program_value.statements[1].expression.dict.items.len);
767 try std.testing.expect(program_value.statements[1].expression.dict.items[0].key.* == .string);
768 try std.testing.expect(program_value.statements[1].expression.dict.items[1].value.* == .name);
769 }
770
771 test "parse rejects invalid dictionary displays" {
772 {
773 const bytes = "{\"a\"}";
774 var stream = try source.tokenize(std.testing.allocator, bytes);
775 defer stream.deinit(std.testing.allocator);
776 try std.testing.expectError(Error.ExpectedColon, parse(std.testing.allocator, bytes, stream.tokens));
777 }
778 {
779 const bytes = "{\"a\": 1 \"b\": 2}";
780 var stream = try source.tokenize(std.testing.allocator, bytes);
781 defer stream.deinit(std.testing.allocator);
782 try std.testing.expectError(Error.ExpectedCommaOrRightBrace, parse(std.testing.allocator, bytes, stream.tokens));
783 }
784 }
785
786 test "parse call and list commas remain separators" {
787 const bytes =
788 \\f(1, 2)
789 \\[1, 2]
790 ;
791 var stream = try source.tokenize(std.testing.allocator, bytes);
792 defer stream.deinit(std.testing.allocator);
793 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
794 defer program_value.deinit();
795
796 try std.testing.expect(program_value.statements[0].expression.* == .call);
797 try std.testing.expectEqual(@as(usize, 2), program_value.statements[0].expression.call.arguments.len);
798 try std.testing.expect(program_value.statements[1].expression.* == .list);
799 try std.testing.expectEqual(@as(usize, 2), program_value.statements[1].expression.list.items.len);
800 }
801
802 test "parse attribute method calls" {
803 const bytes = "xs.append(1)";
804 var stream = try source.tokenize(std.testing.allocator, bytes);
805 defer stream.deinit(std.testing.allocator);
806 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
807 defer program_value.deinit();
808
809 const value = program_value.statements[0].expression;
810 try std.testing.expect(value.* == .call);
811 try std.testing.expect(value.call.target.* == .attribute);
812 try std.testing.expectEqualStrings("append", value.call.target.attribute.name);
813 try std.testing.expect(value.call.target.attribute.target.* == .name);
814 try std.testing.expectEqualStrings("xs", value.call.target.attribute.target.name);
815 }
816
817 test "parse subscription expressions" {
818 const bytes = "[1, 2][0]";
819 var stream = try source.tokenize(std.testing.allocator, bytes);
820 defer stream.deinit(std.testing.allocator);
821 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
822 defer program_value.deinit();
823
824 const value = program_value.statements[0].expression;
825 try std.testing.expect(value.* == .subscript);
826 try std.testing.expect(value.subscript.target.* == .list);
827 try std.testing.expect(value.subscript.selector == .index);
828 try std.testing.expect(value.subscript.selector.index.* == .integer);
829 }
830
831 test "parse slice subscription expressions" {
832 const bytes =
833 \\xs[1:]
834 \\xs[:2]
835 \\xs[1:3:2]
836 \\xs[:]
837 \\xs[::2]
838 ;
839 var stream = try source.tokenize(std.testing.allocator, bytes);
840 defer stream.deinit(std.testing.allocator);
841 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
842 defer program_value.deinit();
843
844 const first = program_value.statements[0].expression.subscript.selector.slice;
845 try std.testing.expect(first.start.?.* == .integer);
846 try std.testing.expect(first.stop == null);
847 try std.testing.expect(first.step == null);
848
849 const second = program_value.statements[1].expression.subscript.selector.slice;
850 try std.testing.expect(second.start == null);
851 try std.testing.expect(second.stop.?.* == .integer);
852 try std.testing.expect(second.step == null);
853
854 const third = program_value.statements[2].expression.subscript.selector.slice;
855 try std.testing.expect(third.start.?.* == .integer);
856 try std.testing.expect(third.stop.?.* == .integer);
857 try std.testing.expect(third.step.?.* == .integer);
858
859 const fourth = program_value.statements[3].expression.subscript.selector.slice;
860 try std.testing.expect(fourth.start == null);
861 try std.testing.expect(fourth.stop == null);
862 try std.testing.expect(fourth.step == null);
863
864 const fifth = program_value.statements[4].expression.subscript.selector.slice;
865 try std.testing.expect(fifth.start == null);
866 try std.testing.expect(fifth.stop == null);
867 try std.testing.expect(fifth.step.?.* == .integer);
868 }
869
870 test "parse subscript assignment" {
871 const bytes =
872 \\xs = [1]
873 \\xs[0] = 2
874 ;
875 var stream = try source.tokenize(std.testing.allocator, bytes);
876 defer stream.deinit(std.testing.allocator);
877 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
878 defer program_value.deinit();
879
880 try std.testing.expect(program_value.statements[0] == .assign);
881 try std.testing.expect(program_value.statements[1] == .subscript_assign);
882 try std.testing.expect(program_value.statements[1].subscript_assign.target.* == .name);
883 try std.testing.expect(program_value.statements[1].subscript_assign.index.* == .integer);
884 }
885
886 test "parse deletion statements" {
887 const bytes =
888 \\del x
889 \\del xs[0]
890 ;
891 var stream = try source.tokenize(std.testing.allocator, bytes);
892 defer stream.deinit(std.testing.allocator);
893 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
894 defer program_value.deinit();
895
896 try std.testing.expect(program_value.statements[0] == .delete);
897 try std.testing.expectEqualStrings("x", program_value.statements[0].delete.name);
898 try std.testing.expect(program_value.statements[1] == .delete);
899 try std.testing.expect(program_value.statements[1].delete.subscript.target.* == .name);
900 try std.testing.expect(program_value.statements[1].delete.subscript.index.* == .integer);
901 }
902
903 test "parse rejects slice assignment" {
904 const bytes = "xs[0:1] = [2]";
905 var stream = try source.tokenize(std.testing.allocator, bytes);
906 defer stream.deinit(std.testing.allocator);
907
908 try std.testing.expectError(Error.UnexpectedToken, parse(std.testing.allocator, bytes, stream.tokens));
909 }
910
911 test "parse rejects invalid deletion targets" {
912 {
913 const bytes = "del xs[0:1]";
914 var stream = try source.tokenize(std.testing.allocator, bytes);
915 defer stream.deinit(std.testing.allocator);
916 try std.testing.expectError(Error.UnexpectedToken, parse(std.testing.allocator, bytes, stream.tokens));
917 }
918 {
919 const bytes = "del [1]";
920 var stream = try source.tokenize(std.testing.allocator, bytes);
921 defer stream.deinit(std.testing.allocator);
922 try std.testing.expectError(Error.UnexpectedToken, parse(std.testing.allocator, bytes, stream.tokens));
923 }
924 }
925
926 test "parse rejects comma separated subscripts" {
927 const bytes = "xs[0, 1]";
928 var stream = try source.tokenize(std.testing.allocator, bytes);
929 defer stream.deinit(std.testing.allocator);
930
931 try std.testing.expectError(Error.ExpectedRightBracket, parse(std.testing.allocator, bytes, stream.tokens));
932 }
933
934 test "parse rejects invalid assignment target" {
935 const bytes = "[1] = 2";
936 var stream = try source.tokenize(std.testing.allocator, bytes);
937 defer stream.deinit(std.testing.allocator);
938
939 try std.testing.expectError(Error.UnexpectedToken, parse(std.testing.allocator, bytes, stream.tokens));
940 }
941
942 test "parse elif chains" {
943 const bytes =
944 \\if a:
945 \\ x = 1
946 \\elif b:
947 \\ x = 2
948 \\else:
949 \\ x = 3
950 ;
951 var stream = try source.tokenize(std.testing.allocator, bytes);
952 defer stream.deinit(std.testing.allocator);
953 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
954 defer program_value.deinit();
955
956 try std.testing.expect(program_value.statements[0] == .if_stmt);
957 try std.testing.expectEqual(@as(usize, 1), program_value.statements[0].if_stmt.otherwise.len);
958 try std.testing.expect(program_value.statements[0].if_stmt.otherwise[0] == .if_stmt);
959 try std.testing.expectEqual(@as(usize, 1), program_value.statements[0].if_stmt.otherwise[0].if_stmt.otherwise.len);
960 }
961
962 test "parse while else" {
963 const bytes =
964 \\while a:
965 \\ pass
966 \\else:
967 \\ x = 1
968 ;
969 var stream = try source.tokenize(std.testing.allocator, bytes);
970 defer stream.deinit(std.testing.allocator);
971 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
972 defer program_value.deinit();
973
974 try std.testing.expect(program_value.statements[0] == .while_stmt);
975 try std.testing.expectEqual(@as(usize, 1), program_value.statements[0].while_stmt.otherwise.len);
976 try std.testing.expect(program_value.statements[0].while_stmt.otherwise[0] == .assign);
977 }
978
979 test "parse for else" {
980 const bytes =
981 \\for x in [1, 2]:
982 \\ pass
983 \\else:
984 \\ y = x
985 ;
986 var stream = try source.tokenize(std.testing.allocator, bytes);
987 defer stream.deinit(std.testing.allocator);
988 var program_value = try parse(std.testing.allocator, bytes, stream.tokens);
989 defer program_value.deinit();
990
991 try std.testing.expect(program_value.statements[0] == .for_stmt);
992 try std.testing.expectEqualStrings("x", program_value.statements[0].for_stmt.name);
993 try std.testing.expect(program_value.statements[0].for_stmt.iterable.* == .list);
994 try std.testing.expectEqual(@as(usize, 1), program_value.statements[0].for_stmt.otherwise.len);
995 try std.testing.expect(program_value.statements[0].for_stmt.otherwise[0] == .assign);
996 }