vm.c

/*
 * VM - Virtual Machine / Interpreter for PL/0
 *
 * A simple stack-based virtual machine that executes bytecode generated
 * by the compiler. Uses a P-code style instruction set similar to the
 * original PL/0 implementation by Wirth.
 *
 * Stack Layout:
 *   [0]           = Return address
 *   [1]           = Static link (for accessing outer scopes)
 *   [2]           = First local variable
 *   ...
 *   [sp]          = Top of stack (for computations)
 *
 * All operations work on the stack - this is a "0-address" machine
 * where arithmetic instructions implicitly pop operands and push results.
 */

#include "pl0.h"

/*
 * Initialize VM with bytecode to execute.
 */
void vm_init(VM *vm, Instruction *code, int code_size)
{
    vm->code = code;
    vm->code_size = code_size;
    vm->sp = -1; /* Stack is empty */
    vm->pc = 0;  /* Start at first instruction */
    vm->trace = 0;
}

/*
 * Enable or disable instruction tracing.
 */
void vm_set_trace(VM *vm, int trace)
{
    vm->trace = trace;
}

/*
 * Print current instruction for debugging.
 */
static void vm_trace(VM *vm)
{
    Instruction *instr = &vm->code[vm->pc];
    const char *opname;

    switch (instr->op) {
    case OP_CONST:
        opname = "CONST";
        break;
    case OP_LOAD:
        opname = "LOAD";
        break;
    case OP_STORE:
        opname = "STORE";
        break;
    case OP_ADD:
        opname = "ADD";
        break;
    case OP_SUB:
        opname = "SUB";
        break;
    case OP_MUL:
        opname = "MUL";
        break;
    case OP_DIV:
        opname = "DIV";
        break;
    case OP_EQ:
        opname = "EQ";
        break;
    case OP_NEQ:
        opname = "NEQ";
        break;
    case OP_LT:
        opname = "LT";
        break;
    case OP_LTE:
        opname = "LTE";
        break;
    case OP_GT:
        opname = "GT";
        break;
    case OP_GTE:
        opname = "GTE";
        break;
    case OP_ODD:
        opname = "ODD";
        break;
    case OP_READ:
        opname = "READ";
        break;
    case OP_WRITE:
        opname = "WRITE";
        break;
    case OP_JMP:
        opname = "JMP";
        break;
    case OP_JZ:
        opname = "JZ";
        break;
    case OP_CALL:
        opname = "CALL";
        break;
    case OP_RET:
        opname = "RET";
        break;
    case OP_HALT:
        opname = "HALT";
        break;
    default:
        opname = "???";
        break;
    }

    printf("PC=%04d SP=%04d: %s", vm->pc, vm->sp, opname);
    if (instr->op == OP_CONST || instr->op == OP_LOAD || instr->op == OP_STORE ||
        instr->op == OP_JMP || instr->op == OP_JZ || instr->op == OP_CALL) {
        printf(" %d", instr->value);
    }
    printf("\n");
}

/*
 * Execute the bytecode. Returns 0 on success, non-zero on error.
 */
int vm_run(VM *vm)
{
    while (vm->pc >= 0 && vm->pc < vm->code_size) {
        Instruction *instr = &vm->code[vm->pc];

        if (vm->trace) {
            vm_trace(vm);
        }

        vm->pc++;

        switch (instr->op) {
        case OP_CONST:
            if (vm->sp >= MAX_STACK_SIZE - 1) {
                fprintf(stderr, "Error: stack overflow\n");
                return -1;
            }
            vm->stack[++vm->sp] = instr->value;
            break;

        case OP_LOAD: {
            int addr = instr->value;
            if (vm->sp >= MAX_STACK_SIZE - 1) {
                fprintf(stderr, "Error: stack overflow\n");
                return -1;
            }
            vm->stack[++vm->sp] = vm->stack[addr];
            break;
        }

        case OP_STORE: {
            int addr = instr->value;
            if (vm->sp < 0) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            vm->stack[addr] = vm->stack[vm->sp--];
            break;
        }

        case OP_ADD: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = a + b;
            break;
        }

        case OP_SUB: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = a - b;
            break;
        }

        case OP_MUL: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = a * b;
            break;
        }

        case OP_DIV: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            if (b == 0) {
                fprintf(stderr, "Error: division by zero\n");
                return -1;
            }
            vm->stack[++vm->sp] = a / b;
            break;
        }

        case OP_EQ: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = (a == b) ? 1 : 0;
            break;
        }

        case OP_NEQ: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = (a != b) ? 1 : 0;
            break;
        }

        case OP_LT: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = (a < b) ? 1 : 0;
            break;
        }

        case OP_LTE: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = (a <= b) ? 1 : 0;
            break;
        }

        case OP_GT: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = (a > b) ? 1 : 0;
            break;
        }

        case OP_GTE: {
            if (vm->sp < 1) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int b = vm->stack[vm->sp--];
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = (a >= b) ? 1 : 0;
            break;
        }

        case OP_ODD: {
            if (vm->sp < 0) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int a = vm->stack[vm->sp--];
            vm->stack[++vm->sp] = (a % 2 != 0) ? 1 : 0;
            break;
        }

        case OP_READ: {
            int value;
            if (scanf("%d", &value) != 1) {
                fprintf(stderr, "Error: invalid input\n");
                return -1;
            }
            vm->stack[instr->value] = value;
            break;
        }

        case OP_WRITE: {
            if (vm->sp < 0) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            printf("%d\n", vm->stack[vm->sp--]);
            break;
        }

        case OP_JMP:
            vm->pc = instr->value;
            break;

        case OP_JZ: {
            if (vm->sp < 0) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            int condition = vm->stack[vm->sp--];
            if (condition == 0) {
                vm->pc = instr->value;
            }
            break;
        }

        case OP_CALL: {
            /* Push return address */
            if (vm->sp >= MAX_STACK_SIZE - 1) {
                fprintf(stderr, "Error: stack overflow\n");
                return -1;
            }
            vm->stack[++vm->sp] = vm->pc;
            vm->pc = instr->value;
            break;
        }

        case OP_RET: {
            if (vm->sp < 0) {
                fprintf(stderr, "Error: stack underflow\n");
                return -1;
            }
            vm->pc = vm->stack[vm->sp--];
            break;
        }

        case OP_HALT:
            return 0;

        default:
            fprintf(stderr, "Error: unknown opcode %d\n", instr->op);
            return -1;
        }
    }

    fprintf(stderr, "Error: unexpected end of program\n");
    return -1;
}

/*
 * Dump VM state for debugging.
 */
void vm_dump(VM *vm)
{
    printf("VM State:\n");
    printf("  PC: %d\n", vm->pc);
    printf("  SP: %d\n", vm->sp);
    printf("  Stack: [");
    for (int i = 0; i <= vm->sp; i++) {
        printf("%d", vm->stack[i]);
        if (i < vm->sp)
            printf(", ");
    }
    printf("]\n");
}

/*
 * Run compiled PL/0 program.
 */
int run(Code *code, int trace)
{
    VM vm;

    vm_init(&vm, code->code, code->code_count);
    vm_set_trace(&vm, trace);

    return vm_run(&vm);
}