lib/python/src/code/chunk.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 //! A compiled program is a list of instructions plus three tables that the instructions refer to by
  2 //! position: constants, variable names and function bodies. The compiler appends to it while it
  3 //! walks the syntax tree, and the virtual machine reads it at every step, so both sides need cheap
  4 //! appends and lookup by position. A name used many times in a program should take one slot, so
  5 //! that every read and write of it refers to the same position. A function body is a compiled
  6 //! program of its own, with its own instructions and tables, and a call has to find it from a value
  7 //! 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 parameter
 11 //! names and its own `Chunk`. `addName` searches the name table before it appends, so each distinct
 12 //! name gets one slot, and the search takes time linear in the number of names. A chunk owns its
 13 //! lists and its function bodies, and it borrows every name, parameter list and string constant
 14 //! from the syntax tree and the source text it was compiled from. A function value is the position
 15 //! of its body in the function table of the top-level chunk, and every body lives in that one table
 16 //! because the compiler rejects a `def` inside a function.
 17 const std = @import("std");
 18 const object = @import("../object/root.zig");
 19 const op = @import("op.zig");
 20 
 21 /// One instruction: an operation and one integer operand. The compiler emits one for each step of
 22 /// the program, and the virtual machine decodes one at every step. The meaning of the operand
 23 /// depends on the operation, and each `Op` tag's doc gives that meaning.
 24 pub 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 another
 28     /// instruction, depending on the operation. The default is 0, and an operation that takes no
 29     /// argument ignores it. The virtual machine checks no table position against its table's
 30     /// length, so a chunk built outside `compile` has to keep every position in range.
 31     operand: usize = 0,
 32 };
 33 
 34 /// 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 the
 36 /// top-level chunk. A call binds each argument to the parameter at the same position and runs the
 37 /// body in a new call frame.
 38 pub const Function = struct {
 39     /// The function's name as the `def` statement spells it. The record borrows the name from the
 40     /// 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 record
 43     /// borrows this list from the syntax tree. A call has to pass exactly this many arguments, or
 44     /// 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 in
 47     /// `deinit`. The compiler ends every body with instructions that return `None`, so a body that
 48     /// runs off its end returns `None`.
 49     chunk: Chunk,
 50 
 51     /// 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 the
 53     /// 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 };
 59 
 60 /// A compiled program or function body: its instructions and the tables of constants, names and
 61 /// 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 every
 63 /// table empty. Each table grows with the allocator passed to the method that appends to it. A
 64 /// chunk owns its four lists and its function bodies, and it borrows its names, parameter lists and
 65 /// string constants from the syntax tree and the source text, so both have to outlive it. Only the
 66 /// top-level chunk holds functions, because the compiler rejects a `def` inside a function body.
 67 pub const Chunk = struct {
 68     /// The instructions, in the order they run. A jump's operand is a position in this list. The
 69     /// virtual machine starts at position 0, and a frame that runs past the last instruction fails
 70     /// with `InvalidFunction`.
 71     instructions: std.ArrayListUnmanaged(Instruction) = .empty,
 72     /// The literal values the instructions push: `None`, booleans, integers, strings and function
 73     /// values. The `constant` operation's operand is a position in this list. A literal written
 74     /// 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. The
 77     /// 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. A
 80     /// function value is a position in this list, and the virtual machine reads only the top-level
 81     /// chunk's list.
 82     functions: std.ArrayListUnmanaged(Function) = .empty,
 83 
 84     /// Frees each owned function body and then the four lists. The caller of `compile` defers it
 85     /// once the chunk exists, as `execute` does. The given allocator has to be the one the lists
 86     /// 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     }
 95 
 96     /// Appends one instruction to the end of the instruction list. The compiler appends each
 97     /// instruction it generates with it. The call returns `error.OutOfMemory` when the list cannot
 98     /// 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     }
102 
103     /// Appends a value to the constant list and returns its position. The compiler stores each
104     /// literal with it and then emits the `constant` operation that pushes it. The call returns
105     /// `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     }
110 
111     /// Returns the position of a name in the name table, and appends the name first when the table
112     /// lacks it. The compiler turns every variable and attribute name into a table position with
113     /// it. The search compares bytes and walks the whole table, so it takes time linear in the
114     /// 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 the
116     /// 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     }
124 
125     /// Appends a function to the function list and returns its position. The compiler records each
126     /// compiled `def` body with it, and the returned position becomes the function's value. The
127     /// chunk takes ownership of the function and frees it in `deinit`. The call returns
128     /// `error.OutOfMemory` when the list cannot grow. After that error, the caller still owns the
129     /// 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 };
135 
136 test "chunk interns names" {
137     var chunk_value = Chunk{};
138     defer chunk_value.deinit(std.testing.allocator);
139 
140     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 }