Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
526 lines (460 sloc) 13.7 KB
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "execute.h"
#include "opcode.h"
#include "bytecode.h"
#include "compile.h"
#include "forkable_stack.h"
#include "frame_layout.h"
#include "locfile.h"
#include "jv.h"
#include "parser.h"
#include "builtin.h"
typedef struct {
jv value;
int pathidx;
} stackval;
jv* pathbuf;
int pathsize; // number of allocated elements
int path_push(stackval sv, jv val) {
int pos = sv.pathidx;
assert(pos <= pathsize);
assert(pos >= 0);
if (pos == pathsize) {
int oldpathsize = pathsize;
pathsize = oldpathsize ? oldpathsize * 2 : 100;
pathbuf = realloc(pathbuf, sizeof(pathbuf[0]) * pathsize);
for (int i=oldpathsize; i<pathsize; i++) {
pathbuf[i] = jv_invalid();
}
}
jv_free(pathbuf[pos]);
pathbuf[pos] = val;
return pos + 1;
}
stackval stackval_replace(stackval value, jv newjs) {
jv_free(value.value);
stackval s = {newjs, value.pathidx};
return s;
}
// Probably all uses of this function are bugs
stackval stackval_root(jv v) {
stackval s = {v, 0};
return s;
}
struct forkable_stack data_stk;
typedef struct {
FORKABLE_STACK_HEADER;
stackval sv;
} data_stk_elem;
void stack_push(stackval val) {
assert(jv_is_valid(val.value));
data_stk_elem* s = forkable_stack_push(&data_stk, sizeof(data_stk_elem));
s->sv = val;
}
stackval stack_pop() {
data_stk_elem* s = forkable_stack_peek(&data_stk);
stackval sv = s->sv;
if (!forkable_stack_pop_will_free(&data_stk)) {
sv.value = jv_copy(sv.value);
}
forkable_stack_pop(&data_stk);
assert(jv_is_valid(sv.value));
return sv;
}
struct forkable_stack frame_stk;
struct forkpoint {
FORKABLE_STACK_HEADER;
struct forkable_stack_state saved_data_stack;
struct forkable_stack_state saved_call_stack;
};
struct forkable_stack fork_stk;
void stack_save(){
struct forkpoint* fork = forkable_stack_push(&fork_stk, sizeof(struct forkpoint));
forkable_stack_save(&data_stk, &fork->saved_data_stack);
forkable_stack_save(&frame_stk, &fork->saved_call_stack);
}
void stack_switch() {
struct forkpoint* fork = forkable_stack_peek(&fork_stk);
forkable_stack_switch(&data_stk, &fork->saved_data_stack);
forkable_stack_switch(&frame_stk, &fork->saved_call_stack);
}
int stack_restore(){
while (!forkable_stack_empty(&data_stk) &&
forkable_stack_pop_will_free(&data_stk)) {
jv_free(stack_pop().value);
}
while (!forkable_stack_empty(&frame_stk) &&
forkable_stack_pop_will_free(&frame_stk)) {
frame_pop(&frame_stk);
}
if (forkable_stack_empty(&fork_stk)) {
return 0;
} else {
struct forkpoint* fork = forkable_stack_peek(&fork_stk);
forkable_stack_restore(&data_stk, &fork->saved_data_stack);
forkable_stack_restore(&frame_stk, &fork->saved_call_stack);
forkable_stack_pop(&fork_stk);
return 1;
}
}
static struct closure make_closure(struct forkable_stack* stk, frame_ptr fr, uint16_t* pc) {
uint16_t level = *pc++;
uint16_t idx = *pc++;
fr = frame_get_level(stk, fr, level);
if (idx & ARG_NEWCLOSURE) {
int subfn_idx = idx & ~ARG_NEWCLOSURE;
assert(subfn_idx < frame_self(fr)->bc->nsubfunctions);
struct closure cl = {frame_self(fr)->bc->subfunctions[subfn_idx],
forkable_stack_to_idx(stk, fr)};
return cl;
} else {
return *frame_closure_arg(fr, idx);
}
}
void print_error(jv value) {
assert(!jv_is_valid(value));
jv msg = jv_invalid_get_msg(value);
if (jv_get_kind(msg) == JV_KIND_STRING) {
fprintf(stderr, "jq: error: %s\n", jv_string_value(msg));
}
jv_free(msg);
}
#define ON_BACKTRACK(op) ((op)+NUM_OPCODES)
jv jq_next() {
jv cfunc_input[MAX_CFUNCTION_ARGS];
jv cfunc_output[MAX_CFUNCTION_ARGS];
assert(!forkable_stack_empty(&frame_stk));
uint16_t* pc = *frame_current_retaddr(&frame_stk);
frame_pop(&frame_stk);
assert(!forkable_stack_empty(&frame_stk));
int backtracking = 0;
while (1) {
uint16_t opcode = *pc;
#if JQ_DEBUG
dump_operation(frame_current_bytecode(&frame_stk), pc);
printf("\t");
const struct opcode_description* opdesc = opcode_describe(opcode);
data_stk_elem* param;
for (int i=0; i<opdesc->stack_in; i++) {
if (i == 0) {
param = forkable_stack_peek(&data_stk);
} else {
printf(" | ");
param = forkable_stack_peek_next(&data_stk, param);
}
if (!param) break;
jv_dump(jv_copy(param->sv.value), 0);
printf("<%d>", jv_get_refcnt(param->sv.value));
}
if (backtracking) printf("\t<backtracking>");
printf("\n");
#endif
if (backtracking) {
opcode = ON_BACKTRACK(opcode);
backtracking = 0;
}
pc++;
switch (opcode) {
default: assert(0 && "invalid instruction");
case LOADK: {
jv v = jv_array_get(jv_copy(frame_current_bytecode(&frame_stk)->constants), *pc++);
assert(jv_is_valid(v));
stack_push(stackval_replace(stack_pop(), v));
break;
}
case DUP: {
stackval v = stack_pop();
stackval v2 = v;
v2.value = jv_copy(v.value);
stack_push(v);
stack_push(v2);
break;
}
case SWAP: {
stackval a = stack_pop();
stackval b = stack_pop();
stack_push(a);
stack_push(b);
break;
}
case POP: {
jv_free(stack_pop().value);
break;
}
case APPEND: {
// FIXME paths
jv v = stack_pop().value;
jv array = stack_pop().value;
array = jv_array_append(array, v);
stack_push(stackval_root(array));
break;
}
case INSERT: {
stackval stktop = stack_pop();
jv v = stack_pop().value;
jv k = stack_pop().value;
stackval objv = stack_pop();
assert(jv_get_kind(k) == JV_KIND_STRING);
assert(jv_get_kind(objv.value) == JV_KIND_OBJECT);
objv.value = jv_object_set(objv.value, k, v);
stack_push(objv);
stack_push(stktop);
break;
}
// FIXME: loadv/storev may do too much copying/freeing
case LOADV: {
uint16_t level = *pc++;
uint16_t v = *pc++;
frame_ptr fp = frame_get_level(&frame_stk, frame_current(&frame_stk), level);
jv* var = frame_local_var(fp, v);
#if JQ_DEBUG
printf("V%d = ", v);
jv_dump(jv_copy(*var), 0);
printf("\n");
#endif
stack_push(stackval_replace(stack_pop(), jv_copy(*var)));
break;
}
case STOREV: {
uint16_t level = *pc++;
uint16_t v = *pc++;
frame_ptr fp = frame_get_level(&frame_stk, frame_current(&frame_stk), level);
jv* var = frame_local_var(fp, v);
stackval val = stack_pop();
#if JQ_DEBUG
printf("V%d = ", v);
jv_dump(jv_copy(val.value), 0);
printf("\n");
#endif
jv_free(*var);
*var = val.value;
break;
}
case ASSIGN: {
stackval replacement = stack_pop();
stackval path_end = stack_pop();
stackval path_start = stack_pop();
jv_free(path_end.value);
jv_free(path_start.value);
uint16_t level = *pc++;
uint16_t v = *pc++;
frame_ptr fp = frame_get_level(&frame_stk, frame_current(&frame_stk), level);
jv* var = frame_local_var(fp, v);
jv result = jv_insert(*var, replacement.value, pathbuf + path_start.pathidx, path_end.pathidx - path_start.pathidx);
if (jv_is_valid(result)) {
*var = result;
} else {
print_error(result);
*var = jv_null();
}
break;
}
case INDEX: {
stackval t = stack_pop();
jv k = stack_pop().value;
int pathidx = path_push(t, jv_copy(k));
jv v = jv_lookup(t.value, k);
if (jv_is_valid(v)) {
stackval sv;
sv.value = v;
sv.pathidx = pathidx;
stack_push(sv);
} else {
print_error(v);
goto do_backtrack;
}
break;
}
case JUMP: {
uint16_t offset = *pc++;
pc += offset;
break;
}
case JUMP_F: {
uint16_t offset = *pc++;
stackval t = stack_pop();
jv_kind kind = jv_get_kind(t.value);
if (kind == JV_KIND_FALSE || kind == JV_KIND_NULL) {
pc += offset;
}
stack_push(t); // FIXME do this better
break;
}
case EACH:
stack_push(stackval_root(jv_number(-1)));
// fallthrough
case ON_BACKTRACK(EACH): {
int idx = jv_number_value(stack_pop().value);
stackval container = stack_pop();
int keep_going;
jv key, value;
if (jv_get_kind(container.value) == JV_KIND_ARRAY) {
if (opcode == EACH) idx = 0;
else idx = idx + 1;
keep_going = idx < jv_array_length(jv_copy(container.value));
if (keep_going) {
key = jv_number(idx);
value = jv_array_get(jv_copy(container.value), idx);
}
} else if (jv_get_kind(container.value) == JV_KIND_OBJECT) {
if (opcode == EACH) idx = jv_object_iter(container.value);
else idx = jv_object_iter_next(container.value, idx);
keep_going = jv_object_iter_valid(container.value, idx);
if (keep_going) {
key = jv_object_iter_key(container.value, idx);
value = jv_object_iter_value(container.value, idx);
}
} else {
assert(opcode == EACH);
print_error(jv_invalid_with_msg(jv_string_fmt("Cannot iterate over %s",
jv_kind_name(jv_get_kind(container.value)))));
keep_going = 0;
}
if (!keep_going) {
jv_free(container.value);
goto do_backtrack;
} else {
stack_save();
stack_push(container);
stack_push(stackval_root(jv_number(idx)));
frame_push_backtrack(&frame_stk, pc - 1);
stack_switch();
stackval sv = {value,
path_push(container, key)};
stack_push(sv);
}
break;
}
do_backtrack:
case BACKTRACK: {
if (!stack_restore()) {
return jv_invalid();
}
pc = *frame_current_retaddr(&frame_stk);
frame_pop(&frame_stk);
backtracking = 1;
break;
}
case FORK: {
stack_save();
frame_push_backtrack(&frame_stk, pc - 1);
stack_switch();
pc++; // skip offset this time
break;
}
case ON_BACKTRACK(FORK): {
uint16_t offset = *pc++;
pc += offset;
break;
}
case YIELD: {
jv value = stack_pop().value;
frame_push_backtrack(&frame_stk, pc);
return value;
}
case CALL_BUILTIN_1_1: {
assert(*pc == 1); // no closure args allowed
pc++; // skip nclosures
pc++; // skip level
stackval top = stack_pop();
cfunc_input[0] = top.value;
struct cfunction* func = &frame_current_bytecode(&frame_stk)->globals->cfunctions[*pc++];
func->fptr(cfunc_input, cfunc_output);
top.value = cfunc_output[0];
if (jv_is_valid(top.value)) {
stack_push(top);
} else {
print_error(top.value);
goto do_backtrack;
}
break;
}
case CALL_BUILTIN_3_1: {
assert(*pc == 1); // no closure args allowed
pc++; // skip nclosures
pc++; // skip level
stackval top = stack_pop();
jv a = stack_pop().value;
jv b = stack_pop().value;
cfunc_input[0] = top.value;
cfunc_input[1] = a;
cfunc_input[2] = b;
struct cfunction* func = &frame_current_bytecode(&frame_stk)->globals->cfunctions[*pc++];
func->fptr(cfunc_input, cfunc_output);
top.value = cfunc_output[0];
if (jv_is_valid(top.value)) {
stack_push(top);
} else {
print_error(top.value);
goto do_backtrack;
}
break;
}
case CALL_1_1: {
uint16_t nclosures = *pc++;
frame_ptr new_frame = frame_push(&frame_stk,
make_closure(&frame_stk, frame_current(&frame_stk), pc),
pc + nclosures * 2);
pc += 2;
frame_ptr old_frame = forkable_stack_peek_next(&frame_stk, new_frame);
assert(nclosures - 1 == frame_self(new_frame)->bc->nclosures);
for (int i=0; i<nclosures-1; i++) {
*frame_closure_arg(new_frame, i) = make_closure(&frame_stk, old_frame, pc);
pc += 2;
}
pc = frame_current_bytecode(&frame_stk)->code;
break;
}
case RET: {
pc = *frame_current_retaddr(&frame_stk);
frame_pop(&frame_stk);
break;
}
}
}
}
void jq_init(struct bytecode* bc, jv input) {
forkable_stack_init(&data_stk, sizeof(stackval) * 1000); // FIXME: lower this number, see if it breaks
forkable_stack_init(&frame_stk, 10240); // FIXME: lower this number, see if it breaks
forkable_stack_init(&fork_stk, 10240); // FIXME: lower this number, see if it breaks
stack_push(stackval_root(input));
struct closure top = {bc, -1};
frame_push(&frame_stk, top, 0);
frame_push_backtrack(&frame_stk, bc->code);
}
void jq_teardown() {
while (stack_restore()) {}
assert(forkable_stack_empty(&fork_stk));
assert(forkable_stack_empty(&data_stk));
assert(forkable_stack_empty(&frame_stk));
forkable_stack_free(&fork_stk);
forkable_stack_free(&data_stk);
forkable_stack_free(&frame_stk);
for (int i=0; i<pathsize; i++) {
jv_free(pathbuf[i]);
}
free(pathbuf);
pathbuf = 0;
pathsize = 0;
}
struct bytecode* jq_compile(const char* str) {
struct locfile locations;
locfile_init(&locations, str, strlen(str));
block program;
struct bytecode* bc = 0;
int nerrors = jq_parse(&locations, &program);
if (nerrors == 0) {
block_append(&program, block_join(gen_op_simple(YIELD), gen_op_simple(BACKTRACK)));
program = builtins_bind(program);
nerrors = block_compile(program, &locations, &bc);
block_free(program);
}
if (nerrors) {
fprintf(stderr, "%d compile %s\n", nerrors, nerrors > 1 ? "errors" : "error");
}
locfile_free(&locations);
return bc;
}