tiny.python.code.chunk

1//! A compiled program is a list of instructions plus three tables that the instructions refer to by2//! position: constants, variable names and function bodies. The compiler appends to it while it3//! walks the syntax tree, and the virtual machine reads it at every step, so both sides need cheap4//! appends and lookup by position. A name used many times in a program should take one slot, so5//! that every read and write of it refers to the same position. A function body is a compiled6//! program of its own, with its own instructions and tables, and a call has to find it from a value7//! at run time.8//!9//! `Chunk` holds the instruction list and the three tables as four growable lists, `Instruction`10//! pairs an operation with one integer operand, and `Function` holds a body's name, its parameter11//! names and its own `Chunk`. `addName` searches the name table before it appends, so each distinct12//! name gets one slot, and the search takes time linear in the number of names. A chunk owns its13//! lists and its function bodies, and it borrows every name, parameter list and string constant14//! from the syntax tree and the source text it was compiled from. A function value is the position15//! of its body in the function table of the top-level chunk, and every body lives in that one table16//! because the compiler rejects a `def` inside a function.17const std = @import("std");18const object = @import("../object/root.zig");19const op = @import("op.zig");2021/// One instruction: an operation and one integer operand. The compiler emits one for each step of22/// the program, and the virtual machine decodes one at every step. The meaning of the operand23/// depends on the operation, and each `Op` tag's doc gives that meaning.24pub const Instruction = struct {25    /// The operation to perform.26    op: op.Op,27    /// The operation's integer argument: a table position, a count, or the position of another28    /// instruction, depending on the operation. The default is 0, and an operation that takes no29    /// argument ignores it. The virtual machine checks no table position against its table's30    /// length, so a chunk built outside `compile` has to keep every position in range.31    operand: usize = 0,32};3334/// A compiled function: its name, its parameter names in order, and its body as a chunk of its own.35/// The compiler records each `def` statement as one, and a call finds it by its position in the36/// top-level chunk. A call binds each argument to the parameter at the same position and runs the37/// body in a new call frame.38pub const Function = struct {39    /// The function's name as the `def` statement spells it. The record borrows the name from the40    /// source text. The `def` statement also binds the function to this name.41    name: []const u8,42    /// The function's parameter names, in the order the `def` statement lists them. The record43    /// borrows this list from the syntax tree. A call has to pass exactly this many arguments, or44    /// it fails with `ArityMismatch`. Each parameter becomes a local variable of the call.45    params: []const []const u8,46    /// The body's own chunk of instructions and tables. This record owns the chunk and frees it in47    /// `deinit`. The compiler ends every body with instructions that return `None`, so a body that48    /// runs off its end returns `None`.49    chunk: Chunk,5051    /// Frees the body's chunk with the given allocator and leaves the record undefined.52    /// `Chunk.deinit` calls it for each function the chunk owns. The call frees nothing that the53    /// name and the parameter list point to, because the record borrows them.54    pub fn deinit(self: *Function, allocator: std.mem.Allocator) void {55        self.chunk.deinit(allocator);56        self.* = undefined;57    }58};5960/// A compiled program or function body: its instructions and the tables of constants, names and61/// functions that they index. `compile` returns one, the virtual machine runs it through a pointer,62/// and the caller frees it with `deinit` once the run is over. A new chunk is `.{}`, with every63/// table empty. Each table grows with the allocator passed to the method that appends to it. A64/// chunk owns its four lists and its function bodies, and it borrows its names, parameter lists and65/// string constants from the syntax tree and the source text, so both have to outlive it. Only the66/// top-level chunk holds functions, because the compiler rejects a `def` inside a function body.67pub const Chunk = struct {68    /// The instructions, in the order they run. A jump's operand is a position in this list. The69    /// virtual machine starts at position 0, and a frame that runs past the last instruction fails70    /// with `InvalidFunction`.71    instructions: std.ArrayListUnmanaged(Instruction) = .empty,72    /// The literal values the instructions push: `None`, booleans, integers, strings and function73    /// values. The `constant` operation's operand is a position in this list. A literal written74    /// twice takes two slots, because `addConstant` appends without searching.75    constants: std.ArrayListUnmanaged(object.Value) = .empty,76    /// The distinct variable and attribute names the instructions use, each stored once. The77    /// operands of `load`, `store`, `delete` and `attribute` are positions in this list.78    names: std.ArrayListUnmanaged([]const u8) = .empty,79    /// The compiled bodies of the program's `def` statements, in the order the compiler met them. A80    /// function value is a position in this list, and the virtual machine reads only the top-level81    /// chunk's list.82    functions: std.ArrayListUnmanaged(Function) = .empty,8384    /// Frees each owned function body and then the four lists. The caller of `compile` defers it85    /// once the chunk exists, as `execute` does. The given allocator has to be the one the lists86    /// grew with. The call leaves the chunk undefined.87    pub fn deinit(self: *Chunk, allocator: std.mem.Allocator) void {88        for (self.functions.items) |*function| function.deinit(allocator);89        self.instructions.deinit(allocator);90        self.constants.deinit(allocator);91        self.names.deinit(allocator);92        self.functions.deinit(allocator);93        self.* = undefined;94    }9596    /// Appends one instruction to the end of the instruction list. The compiler appends each97    /// instruction it generates with it. The call returns `error.OutOfMemory` when the list cannot98    /// grow.99    pub fn emit(self: *Chunk, allocator: std.mem.Allocator, instruction: Instruction) std.mem.Allocator.Error!void {100        try self.instructions.append(allocator, instruction);101    }102103    /// Appends a value to the constant list and returns its position. The compiler stores each104    /// literal with it and then emits the `constant` operation that pushes it. The call returns105    /// `error.OutOfMemory` when the list cannot grow.106    pub fn addConstant(self: *Chunk, allocator: std.mem.Allocator, value: object.Value) std.mem.Allocator.Error!usize {107        try self.constants.append(allocator, value);108        return self.constants.items.len - 1;109    }110111    /// Returns the position of a name in the name table, and appends the name first when the table112    /// lacks it. The compiler turns every variable and attribute name into a table position with113    /// it. The search compares bytes and walks the whole table, so it takes time linear in the114    /// number of distinct names. The table stores the slice it is given without copying the bytes,115    /// so those bytes have to outlive the chunk. The call returns `error.OutOfMemory` when the116    /// table cannot grow.117    pub fn addName(self: *Chunk, allocator: std.mem.Allocator, name: []const u8) std.mem.Allocator.Error!usize {118        for (self.names.items, 0..) |existing, index| {119            if (std.mem.eql(u8, existing, name)) return index;120        }121        try self.names.append(allocator, name);122        return self.names.items.len - 1;123    }124125    /// Appends a function to the function list and returns its position. The compiler records each126    /// compiled `def` body with it, and the returned position becomes the function's value. The127    /// chunk takes ownership of the function and frees it in `deinit`. The call returns128    /// `error.OutOfMemory` when the list cannot grow. After that error, the caller still owns the129    /// function and has to free it.130    pub fn addFunction(self: *Chunk, allocator: std.mem.Allocator, function: Function) std.mem.Allocator.Error!usize {131        try self.functions.append(allocator, function);132        return self.functions.items.len - 1;133    }134};135136test "chunk interns names" {137    var chunk_value = Chunk{};138    defer chunk_value.deinit(std.testing.allocator);139140    try std.testing.expectEqual(@as(usize, 0), try chunk_value.addName(std.testing.allocator, "x"));141    try std.testing.expectEqual(@as(usize, 0), try chunk_value.addName(std.testing.allocator, "x"));142}

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