tiny.python.syntax.parser

1//! The parser reads the token list of a Python program and builds its syntax tree: a list of2//! statements whose expressions are trees of operators and operands. The parser has to settle3//! operator precedence and block nesting, so the compiler can emit instructions in one walk over4//! the tree. For anything outside the package's subset, the parser has to return an error that5//! names what it expected.6//!7//! An assignment's target is known only when the `=` arrives, after the expression before it has8//! been read. A tree has one node per operator, name and literal, and the parser learns how many9//! 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 language12//! 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 attribute14//! access. Comparisons chain as the reference defines them. `a < b <= c` becomes one node that15//! keeps every operator with its right operand. That node lets the compiler test each pair and16//! evaluate each operand once.17//!18//! The parser is written by hand as recursive descent, with one function per precedence level. The19//! 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 that21//! 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 its24//! `deinit` frees the whole tree at once. Names and string contents in the tree are slices of the25//! 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 line29//! fails. The body's first statement has to sit on the line right after the colon's line. Parsing30//! fails on a blank or comment-only line in between. Nesting has no depth limit. Each level of31//! nesting in the text takes stack frames of the calling thread. An error carries no position in32//! the text.33const std = @import("std");34const source = @import("../source/root.zig");35const ast = @import("ast.zig");3637/// The errors `parse` returns when the tokens do not form a program of the subset, besides running38/// out of memory. A caller switches on it to report why the tokens do not form a program. Each39/// names what the parser expected at the token where it stopped. None carries a position in the40/// text.41pub const Error = error{42    /// An expression was due and the next token cannot start one, as in `x =` with nothing after43    /// it. The parser also returns this error for an indent token where no block opens, as on an44    /// indented first line.45    ExpectedExpression,46    /// A block header without its `:`, after the condition of `if`, `elif` or `while`, the iterable47    /// of `for`, the parameters of `def`, or `else`. The parser also returns this error for a48    /// 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 the57    /// 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 another60    /// 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 indented65    /// no deeper than its header gets this error. The parser also returns it for a blank or66    /// 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 one71    /// line. The parser also returns this error for more tokens on the line after a block header's72    /// 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]`, fails77    /// 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` whose83    /// target is neither a name nor a subscript with one index. `del [1]` and `del xs[0:1]` fail84    /// this way.85    UnexpectedToken,86};8788/// Builds the syntax tree of a program from its source text and the tokens made from that text. The89/// package's `execute` calls `parse` on the tokens `tokenize` returned, and a caller that wants a90/// program's tree calls it the same way. `parse` returns the tree as a `Program`. `bytes` has to be91/// 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 returned93/// `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 caller95/// can free them once `parse` returns. `parse` returns one of the `Error` values when the tokens do96/// not form a program of the subset. The function returns `error.OutOfMemory` when an allocation97/// fails. On any error the function frees the arena. `parse` recurses once per level of nesting in98/// the program. The recursion has no depth limit.99pub 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();102103    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}114115const Parser = struct {116    source: []const u8,117    tokens: []const source.Token,118    index: usize = 0,119    arena: std.mem.Allocator,120121    fn program(self: *Parser) (Error || std.mem.Allocator.Error)![]const ast.Statement {122        return try self.block(false);123    }124125    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    }139140    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    }171172    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    }186187    fn ifStatement(self: *Parser) (Error || std.mem.Allocator.Error)!ast.Statement {188        return try self.ifTail();189    }190191    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    }201202    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    }212213    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    }224225    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    }238239    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    }250251    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    }257258    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    }268269    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    }277278    fn expression(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {279        return try self.tupleExpression();280    }281282    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    }293294    fn singleExpression(self: *Parser) (Error || std.mem.Allocator.Error)!*const ast.Expression {295        return try self.disjunction();296    }297298    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    }305306    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    }313314    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    }323324    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    }341342    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    }350351    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    }358359    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    }368369    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    }403404    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    }424425    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    }429430    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    }441442    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    }467468    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    }479480    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    }497498    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    }503504    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    }509510    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    }515516    fn expectIdentifier(self: *Parser) Error![]const u8 {517        if (!self.match(.identifier)) return Error.ExpectedIdentifier;518        return self.previous().span.text(self.source);519    }520521    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    }540541    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    }547548    fn match(self: *Parser, tag: source.Tag) bool {549        if (!self.at(tag)) return false;550        self.index += 1;551        return true;552    }553554    fn at(self: *const Parser, tag: source.Tag) bool {555        return self.peek(0).tag == tag;556    }557558    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    }563564    fn advance(self: *Parser) source.Token {565        const token = self.peek(0);566        self.index += 1;567        return token;568    }569570    fn previous(self: *const Parser) source.Token {571        return self.tokens[self.index - 1];572    }573};574575fn 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}581582test "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();587588    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}592593test "parse function with return and call" {594    const bytes =595        \\def add(a, b):596        \\    return a + b597        \\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();603604    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}609610test "parse if else and while" {611    const bytes =612        \\x = 0613        \\while x < 3:614        \\    if x == 1:615        \\        x = x + 1616        \\    else:617        \\        pass618        \\    x = x + 1619        \\x620    ;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();625626    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}632633test "parse loop control" {634    const bytes =635        \\for x in [1]:636        \\    continue637        \\    break638    ;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();643644    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}650651test "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();657658    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}667668test "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();674675    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}683684test "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();690691    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}698699test "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();708709    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}714715test "parse tuple expressions" {716    const bytes =717        \\()718        \\(1,)719        \\(1, 2)720        \\x = 1, 2721    ;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();726727    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}736737test "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();746747    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}752753test "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();762763    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}770771test "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}785786test "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();795796    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}801802test "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();808809    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}816817test "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();823824    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}830831test "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();843844    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);848849    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);853854    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);858859    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);863864    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}869870test "parse subscript assignment" {871    const bytes =872        \\xs = [1]873        \\xs[0] = 2874    ;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();879880    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}885886test "parse deletion statements" {887    const bytes =888        \\del x889        \\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();895896    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}902903test "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);907908    try std.testing.expectError(Error.UnexpectedToken, parse(std.testing.allocator, bytes, stream.tokens));909}910911test "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}925926test "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);930931    try std.testing.expectError(Error.ExpectedRightBracket, parse(std.testing.allocator, bytes, stream.tokens));932}933934test "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);938939    try std.testing.expectError(Error.UnexpectedToken, parse(std.testing.allocator, bytes, stream.tokens));940}941942test "parse elif chains" {943    const bytes =944        \\if a:945        \\    x = 1946        \\elif b:947        \\    x = 2948        \\else:949        \\    x = 3950    ;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();955956    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}961962test "parse while else" {963    const bytes =964        \\while a:965        \\    pass966        \\else:967        \\    x = 1968    ;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();973974    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}978979test "parse for else" {980    const bytes =981        \\for x in [1, 2]:982        \\    pass983        \\else:984        \\    y = x985    ;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();990991    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}

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