path: root/src/bytecode/vm.h

#ifndef BDL_VM_H
#define BDL_VM_H

#include "types.h"
#include "errors.h"
#include "chunk.h"
#include "ops.h"
#include "debug.h"
#include "hashtable.h"

#define VM_FRAMES_CAP 64
#define VM_STACK_CAP 1024

typedef struct CallFrame {
    // Current code being run.
    Closure *closure;
    // Return counter.
    u8 *rp;
    // Starting point of the locals for this procedure.
    size_t stack_offset;
} CallFrame;

typedef struct VM {
    CallFrame *frames;
    // Stack.
    Object *stack;
    // Program counter.
    u8 *pc;
    // Global variables.
    HashTable *globals;
} VM;

void vm_init(VM *vm);
void vm_free(VM *vm);
void vm_reset(VM *vm);
void vm_interpret(VM *vm);

void
vm_init(VM *vm) {
    *vm = (VM){0};
    array_init(vm->frames, VM_FRAMES_CAP);
    array_init(vm->stack, VM_STACK_CAP);
    vm->globals = ht_init();
}

void
vm_free(VM *vm) {
    array_free(vm->frames);
    array_free(vm->stack);
    ht_free(vm->globals);
}

void
vm_reset(VM *vm) {
    vm_free(vm);
    vm_init(vm);
}

// Helper macros for a more clear VM switch.
#ifdef DEBUG
#define STACK_TRACE() \
    fprintf(stderr, "stack trace:\n"); \
    for (ssize_t i = array_size(vm->frames) - 1; i >= 0 ; i--) { \
        CallFrame frame = vm->frames[i]; \
        Chunk *chunk = frame.closure->chunk; \
        size_t instruction = vm->pc - chunk->code - 1; \
        fprintf(stderr, "\t%-4ld  ->  ", i); \
        fprintf(stderr, "%.*s",(int)array_size(chunk->name), chunk->name); \
        fprintf(stderr, ":%ld:%ld\n", chunk->lines[instruction].line, chunk->lines[instruction].col); \
        vm->pc = frame.rp; \
    }
#else
#define STACK_TRACE()
#endif

#define RUNTIME_ERROR(ERR) \
    error_push((Error){ \
        .type = ERR_TYPE_RUNTIME, \
        .value = (ERR), \
        .line = chunk->lines[vm->pc - chunk->code - 1].line, \
        .col = chunk->lines[vm->pc - chunk->code - 1].col, \
    }); \
    STACK_TRACE() \
    return

#define FIXNUM_ARITHMETIC_OP(OP) \
    do { \
        ssize_t n = AS_FIXNUM(array_pop(vm->stack)); \
        size_t stack_size = array_size(vm->stack) - n; \
        Object obj = array_peek(vm->stack, n - 1); \
        if (!IS_FIXNUM(obj)) { \
            RUNTIME_ERROR(ERR_WRONG_ARG_TYPE); \
            return; \
        } \
        ssize_t acc = AS_FIXNUM(obj); \
        while (n > 1) { \
            obj = array_peek(vm->stack, n - 2); \
            if (!IS_FIXNUM(obj)) { \
                RUNTIME_ERROR(ERR_WRONG_ARG_TYPE); \
                return; \
            } \
            ssize_t current = AS_FIXNUM(obj); \
            acc = acc OP current; \
            n--; \
        } \
        array_head(vm->stack)->size = stack_size; \
        array_push(vm->stack, FIXNUM_VAL(acc)); \
    } while (false)

#define FIXNUM_COMPARE_OP(OP) \
    do { \
        ssize_t n = AS_FIXNUM(array_pop(vm->stack)); \
        size_t stack_size = array_size(vm->stack) - n; \
        Object obj = array_peek(vm->stack, n - 1); \
        if (!IS_FIXNUM(obj)) { \
            RUNTIME_ERROR(ERR_WRONG_ARG_TYPE); \
            return; \
        } \
        ssize_t prev = AS_FIXNUM(obj); \
        bool ret = true; \
        while (n > 1) { \
            obj = array_peek(vm->stack, n - 2); \
            if (!IS_FIXNUM(obj)) { \
                RUNTIME_ERROR(ERR_WRONG_ARG_TYPE); \
                return; \
            } \
            ssize_t current = AS_FIXNUM(obj); \
            ret = ret && (prev OP current); \
            prev = current; \
            n--; \
        } \
        array_head(vm->stack)->size = stack_size; \
        array_push(vm->stack, BOOL_VAL(ret)); \
    } while (false)

#define LOGIC_OP(OP) \
    do { \
        ssize_t n = AS_FIXNUM(array_pop(vm->stack)); \
        size_t stack_size = array_size(vm->stack) - n; \
        Object obj = array_peek(vm->stack, n - 1); \
        bool ret = IS_TRUE(obj); \
        while (n > 1) { \
            obj = array_peek(vm->stack, n - 2); \
            bool current = IS_TRUE(obj); \
            ret = ret OP current; \
            n--; \
        } \
        array_head(vm->stack)->size = stack_size; \
        array_push(vm->stack, BOOL_VAL(ret)); \
    } while (false)

void
vm_interpret(VM *vm) {
    CallFrame *frame = &vm->frames[0];
    Chunk *chunk = frame->closure->chunk;
    vm->pc = chunk->code;
    frame->rp = NULL;

    if (chunk->code == NULL || array_size(chunk->code) == 0) {
        error_push((Error){
            .type = ERR_TYPE_RUNTIME,
            .value = ERR_EMPTY_CHUNK,
        });
        return;
    }

    while (true) {
#ifdef DEBUG_TRACE_EXECUTION
        printf("stack:  [ ");
        for (size_t i = 0; i < array_size(vm->stack); i++) {
            object_display(vm->stack[i]);
            if (i < array_size(vm->stack) - 1) {
                printf(" | ");
            }
        }
        printf(" ]\nop: ");
        disassemble_instruction(chunk, (vm->pc - chunk->code));
#endif
        u8 instruction = *vm->pc++;
        switch (instruction) {
            case OP_LOCAL: {
                ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
                array_push(vm->stack, vm->stack[frame->stack_offset + idx]);
            } break;
            case OP_CONSTANT: {
                u8 constant = *vm->pc++;
                Object obj = chunk->constants[constant];
                array_push(vm->stack, obj);
            } break;
            case OP_CAPTURED: {
                ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
                array_push(vm->stack, frame->closure->values[idx]);
            } break;
            case OP_CAPTURE_LOCAL: {
                // This is a closure with captured variables. We need a copy
                // of it that lives on the heap.
                Object proc = array_pop(vm->stack);
                proc = make_lambda(proc.closure->chunk);

                ssize_t n_captured = AS_FIXNUM(array_pop(vm->stack));
                for (ssize_t i = 0; i < n_captured; i++) {
                    Object value = array_pop(vm->stack);
                    array_push(proc.closure->values, value);
                }
                array_push(vm->stack, proc);
            } break;
            case OP_SET_CAPTURED: {
                Object value = array_pop(vm->stack);
                ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
                frame->closure->values[idx] = value;
            } break;
            case OP_DEF_LOCAL: {
                Object value = array_pop(vm->stack);
                ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
                vm->stack[frame->stack_offset + idx] = value;
            } break;
            case OP_SET_LOCAL: {
                Object value = array_pop(vm->stack);
                ssize_t idx = AS_FIXNUM(array_pop(vm->stack));
                CallFrame frame = vm->frames[array_size(vm->frames) - 1];
                vm->stack[frame.stack_offset + idx] = value;
            } break;
            case OP_DEF: {
                Object value = array_pop(vm->stack);
                Object name = array_pop(vm->stack);
                ht_insert(vm->globals, name, value);
            } break;
            case OP_SET: {
                Object value = array_pop(vm->stack);
                Object name = array_pop(vm->stack);
                Object *prev = ht_lookup(vm->globals, name);
                if (prev == NULL) {
                    RUNTIME_ERROR(ERR_SYMBOL_NOT_FOUND);
                    return;
                }
                ht_insert(vm->globals, name, value);
            } break;
            case OP_GET: {
                Object name = array_pop(vm->stack);
                Object *value = ht_lookup(vm->globals, name);
                if (value == NULL) {
                    RUNTIME_ERROR(ERR_SYMBOL_NOT_FOUND);
                    return;
                }
                array_push(vm->stack, *value);
            } break;
            case OP_SUM: { FIXNUM_ARITHMETIC_OP(+); } break;
            case OP_SUB: { FIXNUM_ARITHMETIC_OP(-); } break;
            case OP_MUL: { FIXNUM_ARITHMETIC_OP(*); } break;
            case OP_DIV: { FIXNUM_ARITHMETIC_OP(/); } break;
            case OP_MOD: { FIXNUM_ARITHMETIC_OP(%); } break;
            case OP_NOT: {
                Object prev = array_pop(vm->stack);
                Object new = IS_TRUE(prev) ? FALSE_VAL : TRUE_VAL;
                array_push(vm->stack, new);
            } break;
            case OP_AND: { LOGIC_OP(&&); } break;
            case OP_OR: { LOGIC_OP(||); } break;
            case OP_EQUAL: { FIXNUM_COMPARE_OP(==); } break;
            case OP_LESS: { FIXNUM_COMPARE_OP(<); } break;
            case OP_GREATER: { FIXNUM_COMPARE_OP(>); } break;
            case OP_LESS_EQUAL: { FIXNUM_COMPARE_OP(<=); } break;
            case OP_GREATER_EQUAL: { FIXNUM_COMPARE_OP(>=); } break;
            case OP_JUMP: {
                u16 a = *vm->pc++;
                u16 b = *vm->pc++;
                s16 offset = (a << 8) | b;
                vm->pc += offset;
            } break;
            case OP_JUMP_IF_FALSE: {
                u16 a = *vm->pc++;
                u16 b = *vm->pc++;
                s16 offset = (a << 8) | b;
                if (IS_FALSE(array_pop(vm->stack))) {
                    vm->pc += offset;
                }
            } break;
            case OP_DISPLAY: {
                object_display(array_pop(vm->stack));
            } break;
            case OP_PRINT: {
                Object obj = array_pop(vm->stack);
                if (!IS_STRING(obj)) {
                    RUNTIME_ERROR(ERR_WRONG_ARG_TYPE);
                }
                StringView scanner = (StringView) {
                    .start = obj.text,
                    .n = array_size(obj.text),
                };
                while (scanner.n != 0) {
                    char c = sv_next(&scanner);
                    if (c == '\\' && sv_peek(&scanner) == 'n') {
                        putchar('\n');
                        sv_next(&scanner);
                        continue;
                    }
                    if (c == '\\' && sv_peek(&scanner) == '"') {
                        putchar('"');
                        sv_next(&scanner);
                        continue;
                    }
                    putchar(c);
                }
            } break;
            case OP_NEWLINE: {
                printf("\n");
            } break;
            case OP_CALL: {
                ssize_t n_args = AS_FIXNUM(array_pop(vm->stack));
                Object proc = vm->stack[array_size(vm->stack) - 1 - n_args];

                // Check the number of arguments is correct.
                // NOTE: This is probably better handled at compilation, but for
                // now this is simpler to implement.
                ssize_t n_params = proc.closure->chunk->n_params;
                ssize_t n_locals = proc.closure->chunk->n_locals - n_params;
                if (n_args < n_params) {
                    RUNTIME_ERROR(ERR_NOT_ENOUGH_ARGS);
                } else if (n_args > n_params) {
                    RUNTIME_ERROR(ERR_TOO_MANY_ARGS);
                }

#ifdef DEBUG
                disassemble_chunk(proc.closure->chunk);
                printf("n_locals: %ld\n", n_locals);
                printf("n_params: %ld\n", n_params);
#endif
                // Tail-call optimization.
                if (proc.closure->chunk != chunk || *vm->pc != OP_RETURN) {
                    // Prepare new call frame.
                    CallFrame new_frame = (CallFrame){
                        .closure = proc.closure,
                        .rp = vm->pc,
                        .stack_offset = array_size(vm->stack) - n_params,
                    };
                    array_push(vm->frames, new_frame);
                    frame = &vm->frames[array_size(vm->frames) - 1];
                    chunk = frame->closure->chunk;

                    // Prepare local slots.
                    for (ssize_t i = 0; i < n_locals; i++) {
                        array_push(vm->stack, NIL_VAL);
                    }
                } else {
                    // Bind tail-call parameters.
                    for (ssize_t i = 0; i < n_params; i++) {
                        size_t offset = n_locals + n_params - 1 - i;
                        Object obj = array_peek(vm->stack, offset);
                        vm->stack[frame->stack_offset + i] = obj;
                    }

                    // Reset stack size.
                    size_t offset = frame->stack_offset + n_params + n_locals;
                    array_head(vm->stack)->size = offset;
                }
                vm->pc = chunk->code;
            } break;
            case OP_RETURN: {
                if (frame->rp == NULL) {
                    Object ret = array_pop(vm->stack);
                    if (!IS_NIL(ret)) {
                        object_display(ret);
                        printf("\n");
                    }
                    return;
                }
                vm->pc = frame->rp;
                array_head(vm->frames)->size--;
                Object ret = array_pop(vm->stack);
                array_head(vm->stack)->size = frame->stack_offset - 1;
                array_push(vm->stack, ret);
                frame = &vm->frames[array_size(vm->frames) - 1];
                chunk = frame->closure->chunk;
            } break;
            case OP_DROP: {
                array_head(vm->stack)->size = 0;
            } break;
            default: {
                RUNTIME_ERROR(ERR_NOT_IMPLEMENTED);
            } break;
        }
    }

    error_push((Error){
        .type = ERR_TYPE_RUNTIME,
        .value = ERR_PC_OOB,
        .line = chunk->lines[0].line,
        .col = chunk->lines[0].col,
    });
}

#undef FIXNUM_ARITHMETIC_OP
#undef FIXNUM_COMPARE_OP
#undef LOGIC_OP

#endif // BDL_VM_H