diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/jq/codegen.zig | 59 | ||||
| -rw-r--r-- | src/jq/constant_table.zig | 1 | ||||
| -rw-r--r-- | src/jq/execute.zig | 51 | ||||
| -rw-r--r-- | src/jq/parse.zig | 50 | ||||
| -rw-r--r-- | src/root.zig | 55 |
5 files changed, 166 insertions, 50 deletions
diff --git a/src/jq/codegen.zig b/src/jq/codegen.zig index 21c5832..6ca5382 100644 --- a/src/jq/codegen.zig +++ b/src/jq/codegen.zig @@ -1,9 +1,10 @@ const std = @import("std"); const jv = @import("../jv.zig"); +const ConstIndex = @import("./constant_table.zig").ConstIndex; const Ast = @import("./parse.zig").Ast; const BinaryOp = @import("./parse.zig").BinaryOp; -pub const ConstIndex = enum(u32) { _ }; +pub const VariableIndex = enum(u32) { _ }; pub const Opcode = enum { nop, @@ -11,6 +12,7 @@ pub const Opcode = enum { jump, jump_unless, fork, + backtrack, dup, pop, subexp_begin, @@ -30,8 +32,9 @@ pub const Opcode = enum { ge, alt, @"const", - const_true, - const_false, + load, + store, + append, }; pub const Instr = union(Opcode) { @@ -42,6 +45,7 @@ pub const Instr = union(Opcode) { jump: usize, jump_unless: usize, fork: usize, + backtrack, dup, pop, subexp_begin, @@ -61,8 +65,9 @@ pub const Instr = union(Opcode) { ge, alt, @"const": ConstIndex, - const_true, - const_false, + load: VariableIndex, + store: VariableIndex, + append: VariableIndex, pub fn op(self: Self) Opcode { return self; @@ -72,11 +77,13 @@ pub const Instr = union(Opcode) { const Codegen = struct { instrs: std.ArrayList(Instr), allocator: std.mem.Allocator, + variables_count: usize, fn init(allocator: std.mem.Allocator) !Codegen { return .{ .instrs = try std.ArrayList(Instr).initCapacity(allocator, 16), .allocator = allocator, + .variables_count = 0, }; } @@ -122,12 +129,12 @@ const Codegen = struct { // POP // <rhs> // JUMP_UNLESS l1 - // CONST_TRUE + // CONST true // JUMP l2 - // l1: CONST_FALSE + // l1: CONST false // l2: JUMP l4 // l3: POP - // CONST_FALSE + // CONST false // l4: try self.emit(.dup); try self.generate(and_expr.lhs); @@ -137,17 +144,17 @@ const Codegen = struct { try self.generate(and_expr.rhs); const jump2_idx = self.pos(); try self.emit(.{ .jump_unless = 0 }); - try self.emit(.const_true); + try self.emit(.{ .@"const" = .true }); const jump3_idx = self.pos(); try self.emit(.{ .jump = 0 }); const l1 = self.pos(); - try self.emit(.const_false); + try self.emit(.{ .@"const" = .false }); const jump4_idx = self.pos(); const l2 = self.pos(); try self.emit(.{ .jump = 0 }); const l3 = self.pos(); try self.emit(.pop); - try self.emit(.const_false); + try self.emit(.{ .@"const" = .false }); const l4 = self.pos(); self.patchLabel(jump1_idx, l3); @@ -160,21 +167,21 @@ const Codegen = struct { // <lhs> // JUMP_UNLESS l1 // POP - // CONST_TRUE + // CONST true // JUMP l3 // l1: POP // <rhs> // JUMP_UNLESS l2 - // CONST_TRUE + // CONST true // JUMP l3 - // l2: CONST_FALSE + // l2: CONST false // l3: try self.emit(.dup); try self.generate(or_expr.lhs); const jump1_idx = self.pos(); try self.emit(.{ .jump_unless = 0 }); try self.emit(.pop); - try self.emit(.const_true); + try self.emit(.{ .@"const" = .true }); const jump2_idx = self.pos(); try self.emit(.{ .jump = 0 }); const l1 = self.pos(); @@ -182,11 +189,11 @@ const Codegen = struct { try self.generate(or_expr.rhs); const jump3_idx = self.pos(); try self.emit(.{ .jump_unless = 0 }); - try self.emit(.const_true); + try self.emit(.{ .@"const" = .true }); const jump4_idx = self.pos(); try self.emit(.{ .jump = 0 }); const l2 = self.pos(); - try self.emit(.const_false); + try self.emit(.{ .@"const" = .false }); const l3 = self.pos(); self.patchLabel(jump1_idx, l1); @@ -215,6 +222,24 @@ const Codegen = struct { self.patchLabel(fork_index, l1); self.patchLabel(jump_index, l2); }, + .construct_array => |arr| { + // DUP + // CONST [] + // STORE v + // <items> + // APPEND v + // BACKTRACK + // LOAD v + const v: VariableIndex = @enumFromInt(self.variables_count); + self.variables_count += 1; + try self.emit(.dup); + try self.emit(.{ .@"const" = .empty_array }); + try self.emit(.{ .store = v }); + try self.generate(arr.items); + try self.emit(.{ .append = v }); + try self.emit(.backtrack); + try self.emit(.{ .load = v }); + }, } } diff --git a/src/jq/constant_table.zig b/src/jq/constant_table.zig new file mode 100644 index 0000000..e996127 --- /dev/null +++ b/src/jq/constant_table.zig @@ -0,0 +1 @@ +pub const ConstIndex = enum(u32) { null, false, true, empty_array, _ }; diff --git a/src/jq/execute.zig b/src/jq/execute.zig index 282a35c..3775952 100644 --- a/src/jq/execute.zig +++ b/src/jq/execute.zig @@ -114,19 +114,37 @@ pub const Runtime = struct { instrs: []const Instr, pc: usize, constants: std.ArrayList(jv.Value), + variables: std.ArrayList(jv.Value), pub fn init(allocator: std.mem.Allocator) !Self { + // The order of this table must match with ConstIndex's order. + var constants = try std.ArrayList(jv.Value).initCapacity(allocator, 4); + try constants.append(allocator, .null); + try constants.append(allocator, .{ .bool = false }); + try constants.append(allocator, .{ .bool = true }); + try constants.append(allocator, .{ .array = jv.Array.init(allocator) }); + return .{ .allocator = allocator, .values = try ValueStack.init(allocator), .forks = .{}, .instrs = &[_]Instr{}, .pc = 0, - .constants = .{}, + .constants = constants, + .variables = .{}, }; } pub fn deinit(self: *Self) void { + for (self.variables.items) |*value| { + switch (value.*) { + .string => |s| self.allocator.free(s), + .array => |*a| a.deinit(), + .object => |*o| o.deinit(), + else => {}, + } + } + self.variables.deinit(self.allocator); for (self.constants.items) |*value| { switch (value.*) { .string => |s| self.allocator.free(s), @@ -169,7 +187,7 @@ pub const Runtime = struct { pub fn next(self: *Self) !?jv.Value { std.debug.assert(self.instrs.len > 0); - self.restore_stack(); + _ = self.restore_stack(); while (self.pc < self.instrs.len) : (self.pc += 1) { const cur = self.instrs[self.pc]; @@ -196,6 +214,11 @@ pub const Runtime = struct { .fork => |offset| { try self.save_stack(self.pc + offset); }, + .backtrack => { + if (self.restore_stack()) { + self.pc -= 1; + } + }, .dup => { std.debug.assert(self.values.ensureSize(1)); @@ -337,17 +360,25 @@ pub const Runtime = struct { _ = self.values.pop(); try self.values.push(self.constants.items[@intFromEnum(idx)]); }, - .const_true => { + .load => |idx| { + try self.values.push(self.variables.items[@intFromEnum(idx)]); + }, + .store => |idx| { std.debug.assert(self.values.ensureSize(1)); - _ = self.values.pop(); - try self.values.push(.{ .bool = true }); + // TODO: Allocate all local variables at startup. + while (self.variables.items.len <= @intFromEnum(idx)) { + try self.variables.append(self.allocator, .null); + } + self.variables.items[@intFromEnum(idx)] = self.values.pop(); }, - .const_false => { + .append => |idx| { std.debug.assert(self.values.ensureSize(1)); - _ = self.values.pop(); - try self.values.push(.{ .bool = false }); + switch (self.variables.items[@intFromEnum(idx)]) { + .array => |*a| try a.append(self.values.pop()), + else => unreachable, + } }, } } @@ -360,10 +391,12 @@ pub const Runtime = struct { try self.values.save(); } - fn restore_stack(self: *Self) void { + fn restore_stack(self: *Self) bool { if (self.forks.pop()) |target_pc| { self.pc = target_pc; self.values.restore(); + return true; } + return false; } }; diff --git a/src/jq/parse.zig b/src/jq/parse.zig index fece14c..82ff7bd 100644 --- a/src/jq/parse.zig +++ b/src/jq/parse.zig @@ -1,8 +1,8 @@ const std = @import("std"); const jv = @import("../jv.zig"); +const ConstIndex = @import("./constant_table.zig").ConstIndex; const Token = @import("./tokenize.zig").Token; const TokenKind = @import("./tokenize.zig").TokenKind; -const ConstIndex = @import("./codegen.zig").ConstIndex; pub const ParseError = error{ UnexpectedEnd, @@ -18,6 +18,7 @@ pub const AstKind = enum { and_expr, pipe, comma, + construct_array, }; pub const BinaryOp = enum { @@ -52,6 +53,7 @@ pub const Ast = union(AstKind) { and_expr: struct { lhs: *Ast, rhs: *Ast }, pipe: struct { lhs: *Ast, rhs: *Ast }, comma: struct { lhs: *Ast, rhs: *Ast }, + construct_array: struct { items: *Ast }, pub fn kind(self: @This()) AstKind { return self; @@ -117,7 +119,9 @@ const Parser = struct { constants: *std.ArrayList(jv.Value), fn parseProgram(self: *Self) Error!*Ast { - return self.parseBody(); + const ret = try self.parseBody(); + _ = try self.tokens.expect(.end); + return ret; } fn parseBody(self: *Self) Error!*Ast { @@ -139,7 +143,6 @@ const Parser = struct { } }; lhs = ast; } - _ = try self.tokens.expect(.end); return lhs; } @@ -309,28 +312,22 @@ const Parser = struct { switch (first_token) { .keyword_null => { _ = try self.tokens.next(); - try self.constants.append(self.allocator, .null); - const idx: ConstIndex = @enumFromInt(self.constants.items.len - 1); const null_node = try self.compile_allocator.create(Ast); - null_node.* = .{ .literal = idx }; + null_node.* = .{ .literal = .null }; return null_node; }, - .keyword_true => { - _ = try self.tokens.next(); - try self.constants.append(self.allocator, .{ .bool = true }); - const idx: ConstIndex = @enumFromInt(self.constants.items.len - 1); - const true_node = try self.compile_allocator.create(Ast); - true_node.* = .{ .literal = idx }; - return true_node; - }, .keyword_false => { _ = try self.tokens.next(); - try self.constants.append(self.allocator, .{ .bool = false }); - const idx: ConstIndex = @enumFromInt(self.constants.items.len - 1); const false_node = try self.compile_allocator.create(Ast); - false_node.* = .{ .literal = idx }; + false_node.* = .{ .literal = .false }; return false_node; }, + .keyword_true => { + _ = try self.tokens.next(); + const true_node = try self.compile_allocator.create(Ast); + true_node.* = .{ .literal = .true }; + return true_node; + }, .number => |f| { _ = try self.tokens.next(); const i: i64 = @intFromFloat(f); @@ -360,12 +357,17 @@ const Parser = struct { }, .bracket_left => { _ = try self.tokens.next(); - _ = try self.tokens.expect(.bracket_right); - try self.constants.append(self.allocator, .{ .array = jv.Array.init(self.allocator) }); - const idx: ConstIndex = @enumFromInt(self.constants.items.len - 1); - const array_node = try self.compile_allocator.create(Ast); - array_node.* = .{ .literal = idx }; - return array_node; + if (self.tokens.consumeIf(.bracket_right)) { + const array_node = try self.compile_allocator.create(Ast); + array_node.* = .{ .literal = .empty_array }; + return array_node; + } else { + const inner_query = try self.parseQuery(); + _ = try self.tokens.expect(.bracket_right); + const array_node = try self.compile_allocator.create(Ast); + array_node.* = .{ .construct_array = .{ .items = inner_query } }; + return array_node; + } }, .brace_left => { _ = try self.tokens.next(); @@ -414,5 +416,5 @@ pub fn parse(allocator: std.mem.Allocator, compile_allocator: std.mem.Allocator, .tokens = &token_stream, .constants = constants, }; - return parser.parseQuery(); + return try parser.parseProgram(); } diff --git a/src/root.zig b/src/root.zig index 7aee514..e61ed1f 100644 --- a/src/root.zig +++ b/src/root.zig @@ -275,3 +275,58 @@ test "alternative operator" { try testRun("[]", "[]", ". // \"default\""); try testRun("{}", "{}", ". // \"default\""); } + +test "array constructor" { + try testRun( + \\[ + \\ 1, + \\ 2, + \\ 3 + \\] + , "null", "[1,2,3]"); + try testRun( + \\[ + \\ 1, + \\ 2 + \\] + , "{\"a\":1,\"b\":2}", "[.a, .b]"); + try testRun( + \\[ + \\ 3 + \\] + , "null", "[1 + 2]"); + try testRun( + \\[ + \\ 1, + \\ 2, + \\ 3 + \\] + , "[1,2,3]", "[.[0], .[1], .[2]]"); + try testRun( + \\[ + \\ [ + \\ 1, + \\ 2, + \\ 3 + \\ ] + \\] + , "[1,2,3]", "[.]"); + try testRun( + \\[ + \\ true, + \\ false + \\] + , "null", "[true, false]"); + try testRun( + \\[ + \\ 1, + \\ [ + \\ 1, + \\ [ + \\ 1, + \\ 2 + \\ ] + \\ ] + \\] + , "{\"a\":1,\"b\":2}", "[.a, [.a, [.a, .b]]]"); +} |