tiny.python.source.lexer

1//! The lexer reads the text of a Python program once, from start to end, and turns it into a list2//! of tokens that ends with an end-of-input token. The lexer has to recover the program's block3//! structure from indentation. The lexer has to drop comments. For text outside the package's4//! subset, the lexer has to return an error that names the problem.5//!6//! Python marks blocks by indentation alone. A block starts where lines become more indented and7//! ends where they return to an outer level. The lexer therefore has to remember the indentation of8//! every block still open.9//!10//! The lexical analysis in the [Python 3.14 language11//! reference](https://docs.python.org/3.14/reference/) tracks indentation with a stack of levels.12//! The lexer keeps the same stack, and the stack starts with the single level zero. A line indented13//! deeper than the top of the stack pushes its level and yields an indent token. A line indented14//! less pops every deeper level and yields a dedent token for each. The line's indentation has to15//! match a level still on the stack. At the end of the text, every level still open is popped with16//! a dedent token of its own.17//!18//! Indentation counts spaces only, and a tab in a line's indentation fails with19//! `InvalidIndentation`. A newline token marks every line break, including the breaks of blank and20//! comment-only lines and breaks inside parentheses, brackets and braces. The lexer knows 1921//! keywords, the ones the subset uses. The lexer reads every other word as a name, even a word22//! Python reserves, such as `class` or `import`. An integer is a run of decimal digits. A string23//! sits on one line between single or double quotes. A string's bytes stay as written, backslashes24//! included. A name starts with an ASCII letter or underscore and continues with ASCII letters,25//! digits and underscores. A byte that starts no token of the subset can appear only inside a26//! string or a comment.27//!28//! The tokens record byte offsets into the text and keep no pointer to it, so reading a token's29//! characters takes the text again. The lexer's entry point, `tokenize`, frees its stack of30//! indentation levels before it returns. The only memory the caller receives is the token list31//! (`Stream`).32const std = @import("std");33const token = @import("token.zig");3435/// The errors `tokenize` returns for text the subset cannot read, besides running out of memory. A36/// caller switches on this error set to report why the text could not be read. An error carries no37/// position in the text.38pub const Error = error{39    /// A byte that starts no token of the subset, such as `/`, `%`, `;`, a backslash, or a byte40    /// above 127 outside a string or comment, or a `!` that no `=` follows.41    InvalidCharacter,42    /// A tab in a line's indentation, or a line whose indentation drops below the current block's43    /// and matches no enclosing block's level.44    InvalidIndentation,45    /// A string literal that reaches a line break or the end of the text before its closing quote.46    UnterminatedString,47};4849/// The token list that `tokenize` returns, for the caller to pass to `parse`. A stream owns the50/// memory of its tokens. The caller frees a stream with `deinit` and the allocator it gave51/// `tokenize`. The syntax tree that `parse` builds keeps no pointer into the token list, so the52/// stream can be freed once `parse` returns.53pub const Stream = struct {54    /// The tokens in source order, ending with the end-of-input token. The slice is one allocation55    /// from the allocator passed to `tokenize`.56    tokens: []const token.Token,5758    /// Frees the token list with the given allocator. The package's `execute` calls this function59    /// as it returns, after the program has run. The allocator has to be the one passed to60    /// `tokenize`. The call leaves the stream undefined.61    pub fn deinit(self: *Stream, allocator: std.mem.Allocator) void {62        allocator.free(self.tokens);63        self.* = undefined;64    }65};6667/// Reads the source text and returns its tokens as a `Stream`. The package's `execute` calls this68/// function first, and a caller that wants the tokens of a program calls it directly. The function69/// borrows the text for the call alone: the tokens record byte offsets and keep no pointer to it.70/// The function allocates the token list from the given allocator and returns it as one slice. The71/// function also allocates a stack of indentation levels, which it frees before returning. The72/// caller owns the returned stream and frees it with `Stream.deinit` and the same allocator. The73/// function returns `InvalidCharacter`, `InvalidIndentation` or `UnterminatedString` for text it74/// cannot read. The function returns `error.OutOfMemory` when an allocation fails. On any error it75/// frees everything it allocated. The list ends with a dedent token for each block still open and76/// then the end-of-input token. Empty text yields the end-of-input token alone.77pub fn tokenize(allocator: std.mem.Allocator, source: []const u8) (Error || std.mem.Allocator.Error)!Stream {78    var lexer = Lexer{79        .source = source,80        .tokens = .empty,81        .indents = .empty,82    };83    errdefer lexer.tokens.deinit(allocator);84    errdefer lexer.indents.deinit(allocator);85    try lexer.indents.append(allocator, 0);86    try lexer.run(allocator);87    const tokens = try lexer.tokens.toOwnedSlice(allocator);88    lexer.indents.deinit(allocator);89    return .{ .tokens = tokens };90}9192const Lexer = struct {93    source: []const u8,94    index: usize = 0,95    tokens: std.ArrayListUnmanaged(token.Token),96    indents: std.ArrayListUnmanaged(usize),97    line_start: bool = true,9899    fn run(self: *Lexer, allocator: std.mem.Allocator) (Error || std.mem.Allocator.Error)!void {100        while (self.index < self.source.len) {101            if (self.line_start) try self.indentation(allocator);102            if (self.index >= self.source.len) break;103            const c = self.source[self.index];104            switch (c) {105                ' ', '\t' => self.index += 1,106                '\n' => try self.newline(allocator, 1),107                '\r' => try self.carriage(allocator),108                '#' => self.comment(),109                '+' => try self.simple(allocator, .plus, 1),110                '-' => try self.simple(allocator, .minus, 1),111                '*' => try self.simple(allocator, .star, 1),112                '=' => try self.singleOrEqual(allocator, .equal, .equal_equal),113                '!' => try self.bang(allocator),114                '<' => try self.singleOrEqual(allocator, .less, .less_equal),115                '>' => try self.singleOrEqual(allocator, .greater, .greater_equal),116                ',' => try self.simple(allocator, .comma, 1),117                ':' => try self.simple(allocator, .colon, 1),118                '.' => try self.simple(allocator, .dot, 1),119                '(' => try self.simple(allocator, .lparen, 1),120                ')' => try self.simple(allocator, .rparen, 1),121                '[' => try self.simple(allocator, .lbracket, 1),122                ']' => try self.simple(allocator, .rbracket, 1),123                '{' => try self.simple(allocator, .lbrace, 1),124                '}' => try self.simple(allocator, .rbrace, 1),125                '\'', '"' => try self.string(allocator),126                '0'...'9' => try self.integer(allocator),127                'A'...'Z', 'a'...'z', '_' => try self.identifier(allocator),128                else => return Error.InvalidCharacter,129            }130        }131        while (self.indents.items.len > 1) {132            _ = self.indents.pop();133            try self.tokens.append(allocator, .{134                .tag = .dedent,135                .span = .{ .start = self.source.len, .end = self.source.len },136            });137        }138        try self.tokens.append(allocator, .{139            .tag = .eof,140            .span = .{ .start = self.source.len, .end = self.source.len },141        });142    }143144    fn indentation(self: *Lexer, allocator: std.mem.Allocator) (Error || std.mem.Allocator.Error)!void {145        const start = self.index;146        var width: usize = 0;147        while (self.index < self.source.len and self.source[self.index] == ' ') {148            self.index += 1;149            width += 1;150        }151        if (self.index < self.source.len and self.source[self.index] == '\t') return Error.InvalidIndentation;152        if (self.index >= self.source.len or self.source[self.index] == '\n' or self.source[self.index] == '\r' or self.source[self.index] == '#') return;153        const current = self.indents.items[self.indents.items.len - 1];154        if (width > current) {155            try self.indents.append(allocator, width);156            try self.tokens.append(allocator, .{157                .tag = .indent,158                .span = .{ .start = start, .end = self.index },159            });160        } else if (width < current) {161            while (self.indents.items.len > 1 and width < self.indents.items[self.indents.items.len - 1]) {162                _ = self.indents.pop();163                try self.tokens.append(allocator, .{164                    .tag = .dedent,165                    .span = .{ .start = start, .end = self.index },166                });167            }168            if (width != self.indents.items[self.indents.items.len - 1]) return Error.InvalidIndentation;169        }170        self.line_start = false;171    }172173    fn simple(self: *Lexer, allocator: std.mem.Allocator, tag: token.Tag, width: usize) std.mem.Allocator.Error!void {174        const start = self.index;175        self.index += width;176        self.line_start = false;177        try self.tokens.append(allocator, .{178            .tag = tag,179            .span = .{ .start = start, .end = self.index },180        });181    }182183    fn singleOrEqual(self: *Lexer, allocator: std.mem.Allocator, single: token.Tag, equal: token.Tag) std.mem.Allocator.Error!void {184        const start = self.index;185        self.index += 1;186        const tag = if (self.index < self.source.len and self.source[self.index] == '=') blk: {187            self.index += 1;188            break :blk equal;189        } else single;190        self.line_start = false;191        try self.tokens.append(allocator, .{192            .tag = tag,193            .span = .{ .start = start, .end = self.index },194        });195    }196197    fn bang(self: *Lexer, allocator: std.mem.Allocator) (Error || std.mem.Allocator.Error)!void {198        const start = self.index;199        self.index += 1;200        if (self.index >= self.source.len or self.source[self.index] != '=') return Error.InvalidCharacter;201        self.index += 1;202        self.line_start = false;203        try self.tokens.append(allocator, .{204            .tag = .bang_equal,205            .span = .{ .start = start, .end = self.index },206        });207    }208209    fn carriage(self: *Lexer, allocator: std.mem.Allocator) std.mem.Allocator.Error!void {210        const start = self.index;211        self.index += 1;212        if (self.index < self.source.len and self.source[self.index] == '\n') {213            self.index += 1;214        }215        try self.tokens.append(allocator, .{216            .tag = .newline,217            .span = .{ .start = start, .end = self.index },218        });219        self.line_start = true;220    }221222    fn newline(self: *Lexer, allocator: std.mem.Allocator, width: usize) std.mem.Allocator.Error!void {223        const start = self.index;224        self.index += width;225        try self.tokens.append(allocator, .{226            .tag = .newline,227            .span = .{ .start = start, .end = self.index },228        });229        self.line_start = true;230    }231232    fn comment(self: *Lexer) void {233        while (self.index < self.source.len and self.source[self.index] != '\n' and self.source[self.index] != '\r') {234            self.index += 1;235        }236    }237238    fn integer(self: *Lexer, allocator: std.mem.Allocator) std.mem.Allocator.Error!void {239        const start = self.index;240        while (self.index < self.source.len and isDigit(self.source[self.index])) {241            self.index += 1;242        }243        self.line_start = false;244        try self.tokens.append(allocator, .{245            .tag = .integer,246            .span = .{ .start = start, .end = self.index },247        });248    }249250    fn string(self: *Lexer, allocator: std.mem.Allocator) (Error || std.mem.Allocator.Error)!void {251        const quote = self.source[self.index];252        const start = self.index;253        self.index += 1;254        while (self.index < self.source.len and self.source[self.index] != quote) {255            if (self.source[self.index] == '\n' or self.source[self.index] == '\r') return Error.UnterminatedString;256            self.index += 1;257        }258        if (self.index >= self.source.len) return Error.UnterminatedString;259        self.index += 1;260        self.line_start = false;261        try self.tokens.append(allocator, .{262            .tag = .string,263            .span = .{ .start = start, .end = self.index },264        });265    }266267    fn identifier(self: *Lexer, allocator: std.mem.Allocator) std.mem.Allocator.Error!void {268        const start = self.index;269        while (self.index < self.source.len and isIdentifierContinue(self.source[self.index])) {270            self.index += 1;271        }272        const text = self.source[start..self.index];273        self.line_start = false;274        try self.tokens.append(allocator, .{275            .tag = keyword(text),276            .span = .{ .start = start, .end = self.index },277        });278    }279};280281fn keyword(text: []const u8) token.Tag {282    if (std.mem.eql(u8, text, "and")) return .and_kw;283    if (std.mem.eql(u8, text, "break")) return .break_kw;284    if (std.mem.eql(u8, text, "continue")) return .continue_kw;285    if (std.mem.eql(u8, text, "del")) return .del_kw;286    if (std.mem.eql(u8, text, "def")) return .def_kw;287    if (std.mem.eql(u8, text, "elif")) return .elif_kw;288    if (std.mem.eql(u8, text, "else")) return .else_kw;289    if (std.mem.eql(u8, text, "for")) return .for_kw;290    if (std.mem.eql(u8, text, "if")) return .if_kw;291    if (std.mem.eql(u8, text, "in")) return .in_kw;292    if (std.mem.eql(u8, text, "is")) return .is_kw;293    if (std.mem.eql(u8, text, "not")) return .not_kw;294    if (std.mem.eql(u8, text, "or")) return .or_kw;295    if (std.mem.eql(u8, text, "pass")) return .pass_kw;296    if (std.mem.eql(u8, text, "return")) return .return_kw;297    if (std.mem.eql(u8, text, "while")) return .while_kw;298    if (std.mem.eql(u8, text, "True")) return .true_kw;299    if (std.mem.eql(u8, text, "False")) return .false_kw;300    if (std.mem.eql(u8, text, "None")) return .none_kw;301    return .identifier;302}303304fn isDigit(c: u8) bool {305    return c >= '0' and c <= '9';306}307308fn isIdentifierContinue(c: u8) bool {309    return isDigit(c) or (c >= 'A' and c <= 'Z') or (c >= 'a' and c <= 'z') or c == '_';310}311312test "tokenize arithmetic assignment" {313    var stream = try tokenize(std.testing.allocator, "x = 1 + 2\n");314    defer stream.deinit(std.testing.allocator);315316    try std.testing.expectEqual(token.Tag.identifier, stream.tokens[0].tag);317    try std.testing.expectEqual(token.Tag.equal, stream.tokens[1].tag);318    try std.testing.expectEqual(token.Tag.integer, stream.tokens[2].tag);319    try std.testing.expectEqual(token.Tag.plus, stream.tokens[3].tag);320    try std.testing.expectEqual(token.Tag.integer, stream.tokens[4].tag);321    try std.testing.expectEqual(token.Tag.newline, stream.tokens[5].tag);322    try std.testing.expectEqual(token.Tag.eof, stream.tokens[6].tag);323}324325test "tokenize keywords and comments" {326    var stream = try tokenize(std.testing.allocator, "True # hidden\nFalse None");327    defer stream.deinit(std.testing.allocator);328329    try std.testing.expectEqual(token.Tag.true_kw, stream.tokens[0].tag);330    try std.testing.expectEqual(token.Tag.newline, stream.tokens[1].tag);331    try std.testing.expectEqual(token.Tag.false_kw, stream.tokens[2].tag);332    try std.testing.expectEqual(token.Tag.none_kw, stream.tokens[3].tag);333}334335test "tokenize function indentation" {336    var stream = try tokenize(std.testing.allocator,337        \\def f(x):338        \\    return x339        \\f(1)340    );341    defer stream.deinit(std.testing.allocator);342343    try std.testing.expectEqual(token.Tag.def_kw, stream.tokens[0].tag);344    try std.testing.expectEqual(token.Tag.identifier, stream.tokens[1].tag);345    try std.testing.expectEqual(token.Tag.lparen, stream.tokens[2].tag);346    try std.testing.expectEqual(token.Tag.identifier, stream.tokens[3].tag);347    try std.testing.expectEqual(token.Tag.rparen, stream.tokens[4].tag);348    try std.testing.expectEqual(token.Tag.colon, stream.tokens[5].tag);349    try std.testing.expectEqual(token.Tag.newline, stream.tokens[6].tag);350    try std.testing.expectEqual(token.Tag.indent, stream.tokens[7].tag);351    try std.testing.expectEqual(token.Tag.return_kw, stream.tokens[8].tag);352    try std.testing.expectEqual(token.Tag.dedent, stream.tokens[11].tag);353}354355test "tokenize control flow and comparisons" {356    var stream = try tokenize(std.testing.allocator,357        \\if x <= 3:358        \\    pass359        \\else:360        \\    y = x != 4361    );362    defer stream.deinit(std.testing.allocator);363364    try std.testing.expectEqual(token.Tag.if_kw, stream.tokens[0].tag);365    try std.testing.expectEqual(token.Tag.less_equal, stream.tokens[2].tag);366    try std.testing.expectEqual(token.Tag.pass_kw, stream.tokens[7].tag);367    try std.testing.expectEqual(token.Tag.else_kw, stream.tokens[10].tag);368    try std.testing.expectEqual(token.Tag.bang_equal, stream.tokens[17].tag);369}370371test "tokenize loop control" {372    var stream = try tokenize(std.testing.allocator,373        \\for x in [1]:374        \\    break375        \\    continue376    );377    defer stream.deinit(std.testing.allocator);378379    try std.testing.expectEqual(token.Tag.for_kw, stream.tokens[0].tag);380    try std.testing.expectEqual(token.Tag.identifier, stream.tokens[1].tag);381    try std.testing.expectEqual(token.Tag.in_kw, stream.tokens[2].tag);382    try std.testing.expectEqual(token.Tag.break_kw, stream.tokens[9].tag);383    try std.testing.expectEqual(token.Tag.continue_kw, stream.tokens[11].tag);384}385386test "tokenize deletion keyword" {387    var stream = try tokenize(std.testing.allocator, "del x");388    defer stream.deinit(std.testing.allocator);389390    try std.testing.expectEqual(token.Tag.del_kw, stream.tokens[0].tag);391    try std.testing.expectEqual(token.Tag.identifier, stream.tokens[1].tag);392}393394test "tokenize attribute references" {395    var stream = try tokenize(std.testing.allocator, "xs.append");396    defer stream.deinit(std.testing.allocator);397398    try std.testing.expectEqual(token.Tag.identifier, stream.tokens[0].tag);399    try std.testing.expectEqual(token.Tag.dot, stream.tokens[1].tag);400    try std.testing.expectEqual(token.Tag.identifier, stream.tokens[2].tag);401}402403test "tokenize logical operators" {404    var stream = try tokenize(std.testing.allocator, "not True and False or None is");405    defer stream.deinit(std.testing.allocator);406407    try std.testing.expectEqual(token.Tag.not_kw, stream.tokens[0].tag);408    try std.testing.expectEqual(token.Tag.true_kw, stream.tokens[1].tag);409    try std.testing.expectEqual(token.Tag.and_kw, stream.tokens[2].tag);410    try std.testing.expectEqual(token.Tag.false_kw, stream.tokens[3].tag);411    try std.testing.expectEqual(token.Tag.or_kw, stream.tokens[4].tag);412    try std.testing.expectEqual(token.Tag.none_kw, stream.tokens[5].tag);413    try std.testing.expectEqual(token.Tag.is_kw, stream.tokens[6].tag);414}415416test "tokenize strings" {417    var stream = try tokenize(std.testing.allocator,418        \\"alpha" 'beta'419    );420    defer stream.deinit(std.testing.allocator);421422    try std.testing.expectEqual(token.Tag.string, stream.tokens[0].tag);423    try std.testing.expectEqualStrings("\"alpha\"", stream.tokens[0].span.text("\"alpha\" 'beta'"));424    try std.testing.expectEqual(token.Tag.string, stream.tokens[1].tag);425}426427test "tokenize brackets and braces" {428    var stream = try tokenize(std.testing.allocator, "[1, 2][0] {\"a\": 1}");429    defer stream.deinit(std.testing.allocator);430431    try std.testing.expectEqual(token.Tag.lbracket, stream.tokens[0].tag);432    try std.testing.expectEqual(token.Tag.integer, stream.tokens[1].tag);433    try std.testing.expectEqual(token.Tag.comma, stream.tokens[2].tag);434    try std.testing.expectEqual(token.Tag.integer, stream.tokens[3].tag);435    try std.testing.expectEqual(token.Tag.rbracket, stream.tokens[4].tag);436    try std.testing.expectEqual(token.Tag.lbracket, stream.tokens[5].tag);437    try std.testing.expectEqual(token.Tag.integer, stream.tokens[6].tag);438    try std.testing.expectEqual(token.Tag.rbracket, stream.tokens[7].tag);439    try std.testing.expectEqual(token.Tag.lbrace, stream.tokens[8].tag);440    try std.testing.expectEqual(token.Tag.string, stream.tokens[9].tag);441    try std.testing.expectEqual(token.Tag.colon, stream.tokens[10].tag);442    try std.testing.expectEqual(token.Tag.integer, stream.tokens[11].tag);443    try std.testing.expectEqual(token.Tag.rbrace, stream.tokens[12].tag);444}445446test "reject unterminated strings" {447    try std.testing.expectError(Error.UnterminatedString, tokenize(std.testing.allocator, "\"alpha"));448}449450test "tokenize releases indentation storage once when token transfer fails" {451    const source = "if x:\n    pass";452    var counting = std.testing.FailingAllocator.init(std.testing.allocator, .{453        .resize_fail_index = 0,454    });455    const counting_allocator = counting.allocator();456    var stream = try tokenize(counting_allocator, source);457    stream.deinit(counting_allocator);458    try std.testing.expect(counting.alloc_index > 0);459460    var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{461        .fail_index = counting.alloc_index - 1,462        .resize_fail_index = 0,463    });464    try std.testing.expectError(error.OutOfMemory, tokenize(failing.allocator(), source));465    try std.testing.expect(failing.has_induced_failure);466}467468test "tokenize elif" {469    var stream = try tokenize(std.testing.allocator,470        \\if a:471        \\    pass472        \\elif b:473        \\    pass474    );475    defer stream.deinit(std.testing.allocator);476477    try std.testing.expectEqual(token.Tag.if_kw, stream.tokens[0].tag);478    try std.testing.expectEqual(token.Tag.elif_kw, stream.tokens[8].tag);479}

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