aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--docs/jq_grammar.md3
-rw-r--r--src/jq/codegen.zig59
-rw-r--r--src/jq/constant_table.zig1
-rw-r--r--src/jq/execute.zig51
-rw-r--r--src/jq/parse.zig50
-rw-r--r--src/root.zig55
6 files changed, 169 insertions, 50 deletions
diff --git a/docs/jq_grammar.md b/docs/jq_grammar.md
index a84164c..d636756 100644
--- a/docs/jq_grammar.md
+++ b/docs/jq_grammar.md
@@ -98,6 +98,9 @@ primary:
STRING
'.'
FIELD '?'?
+ '[' ']'
+ '{' '}'
+ '[' query ']'
```
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]]]");
+}
generated by cgit v1.3-1-g0d28 (git 2.53.0) at 2026-03-05 22:29:00 +0000