const std = @import("std");
const compiler = @import("compiler.zig");
const byte_code = @import("bytecode.zig");
const ByteCode = byte_code.ByteCode;
const _builtin = @import("builtins.zig");
const Value = @import("Value.zig");
const Type = Value.Type;
const BuiltinError = _builtin.BuiltinError;
const testing = std.testing;
const Allocator = std.mem.Allocator;
const Errors = @import("error.zig").Errors;
const Gc = @import("Gc.zig");

//! The Virtual Machine of Luf is stack-based.
//! Currently the stack has a size of 2048 (pre-allocated)

/// VM is a stack-based Virtual Machine
/// Although a register-based VM is more performant,
/// a stack-based one is more understandable
pub const Vm = struct {
    /// Stack pointer points to the next value
    sp: usize = 0,

    /// Stack has a max of 2048 Value's that it can hold
    stack: [2048]*Value = undefined,

    /// Globals that live inside the VM
    /// Is resized after each run() call by flushing out all
    /// values but its functions
    globals: std.ArrayList(*Value),

    locals: std.ArrayList(*Value),

    /// Call stack that contains the instruction and stack pointer, as well as the instructions
    /// to run the stack
    call_stack: CallStack,

    /// allocator used for vm's internal lists and hashmaps
    allocator: *Allocator,

    /// List of errors generated by parser/compiler/vm
    errors: Errors,

    /// The instructions to run
    code: ?*ByteCode,

    /// Libraries that are loaded into the VM
    /// By default, the standard library is already loaded under key 'std'
    libs: std.StringArrayHashMapUnmanaged(*Value),

    /// Garbage collector
    gc: *Gc,

    /// Possible errors that occur during runtime
    pub const Error = error{ OutOfMemory, RuntimeError } || BuiltinError;

    /// List of call frames that get populated during function calls
    /// and popped on return statements
    const CallStack = std.ArrayList(Frame);

    /// Function `Frame` on the callstack
    const Frame = struct {
        /// Frame pointer which contains the actual function `Value`, which is used to check for tail recursion
        fp: ?*Value,
        /// `Instruction` pointer to the position of the function in the bytecode's instruction set
        ip: usize,
    };

    /// Creates a new `Vm` and adds Luf's standard library to the virtual machine
    /// This will put Vm on the heap, and `deinit()` must be called to free its memory
    pub fn init(allocator: *Allocator) !*Vm {
        const gc = try allocator.create(Gc);
        gc.* = Gc.init(allocator);

        const vm = try allocator.create(Vm);
        vm.* = .{
            .globals = std.ArrayList(*Value).init(allocator),
            .call_stack = CallStack.init(allocator),
            .allocator = allocator,
            .errors = Errors.init(allocator),
            .code = null,
            .libs = std.StringArrayHashMapUnmanaged(*Value){},
            .gc = gc,
            .locals = std.ArrayList(*Value).init(allocator),
        };
        gc.vm = vm;

        try vm.loadLib("std", @import("std/std.zig"));

        return vm;
    }

    /// Frees all memory allocated by the `Vm`.
    /// The vm is no longer valid for use after calling deinit
    pub fn deinit(self: *Vm) void {
        self.globals.deinit();
        self.call_stack.deinit();
        self.errors.deinit();
        self.libs.deinit(self.allocator);
        self.gc.deinit();
        self.locals.deinit();
        self.allocator.destroy(self.gc);
        self.allocator.destroy(self);
    }

    /// Compiles the given source code and then runs it on the `Vm`
    pub fn compileAndRun(self: *Vm, source: []const u8) !void {
        var cu = try compiler.compile(self.allocator, source, &self.errors);
        defer cu.deinit();

        var code = try byte_code.Instructions.fromCu(self.allocator, cu);
        defer code.deinit();

        self.code = &code;
        try self.run();
    }

    /// Loads new bytecode into the Vm
    pub fn loadCode(self: *Vm, code: *ByteCode) void {
        self.code = code;
    }

    /// Loads a Zig library into the VM
    pub fn loadLib(self: *Vm, name: []const u8, lib: anytype) !void {
        try self.libs.putNoClobber(
            self.allocator,
            name,
            try Value.fromZig(self.gc, lib),
        );
    }

    /// Calls a function from Luf using the given arguments
    /// Returns the value from the function back to Zig as `Value`
    pub fn callFunc(self: *Vm, func_name: []const u8, args: anytype) !*Value {
        std.debug.assert(self.sp == 0);
        if (self.code == null)
            return error.NoInstructions;

        var maybe_func: *Value = blk: {
            for (self.globals.items) |global, i| {
                if (global.ty == .function and
                    global.toFunction().name != null and
                    std.mem.eql(u8, func_name, global.toFunction().name.?))
                    break :blk global;
            }
            return error.UndefinedFunction;
        };

        const func = maybe_func.toFunction();
        if (func.arg_len != args.len) {
            return error.IncorrectArgumentLength;
        }

        inline for (args) |arg, i| {
            if (i >= self.locals.items.len)
                try self.locals.resize(i + 1);
            self.locals.items[i] = (try Value.fromZig(self.gc, arg));
        }

        // initial call stack for main
        try self.call_stack.append(.{
            .fp = null,
            .ip = 0,
        });

        // function call stack
        try self.call_stack.append(.{
            .fp = maybe_func,
            .ip = func.entry,
        });

        try self.run();

        return self.pop();
    }

    /// Runs the given `ByteCode` on the Virtual Machine
    pub fn run(self: *Vm) Error!void {
        if (self.code == null)
            return self.fail("No bytecode instructions loaded");

        if (self.call_stack.items.len == 0) {
            try self.call_stack.append(.{
                .fp = null,
                .ip = 0,
            });
        }

        var loaded_funcs: usize = 0;
        while (self.frame().ip < self.code.?.instructions.len) {
            var current_frame = self.frame();
            defer current_frame.ip += 1;
            const inst = self.code.?.instructions[current_frame.ip];

            switch (inst.getOp()) {
                .load_integer => try self.push(
                    try Value.Integer.create(self.gc, @bitCast(i64, inst.integer)),
                ),
                .load_string => try self.push(
                    try Value.String.create(self.gc, inst.string),
                ),
                .load_func => {
                    const func = inst.function;
                    const val = try Value.Function.create(
                        self.gc,
                        func.name,
                        func.locals,
                        func.arg_len,
                        func.entry,
                    );
                    try self.push(val);
                },
                .equal,
                .not_equal,
                .less_than,
                .greater_than,
                .less_than_equal,
                .greater_than_equal,
                .@"and",
                .@"or",
                => try self.execCmp(inst.op),
                .add,
                .sub,
                .mul,
                .div,
                .mod,
                .bitwise_and,
                .bitwise_or,
                .bitwise_xor,
                .shift_left,
                .shift_right,
                => try self.execBinOp(inst.op),
                .assign_add,
                .assign_div,
                .assign_mul,
                .assign_sub,
                => try self.execAssignAndBinOp(inst.op),
                .pop => _ = self.pop(),
                .load_true => try self.push(&Value.True.base),
                .load_false => try self.push(&Value.False.base),
                .minus => try self.execNegation(),
                .not => try self.execNot(),
                .bitwise_not => try self.execBitwiseNot(),
                .load_nil => try self.push(&Value.Nil),
                .load_void => try self.push(&Value.Void),
                .jump => current_frame.ip = inst.ptr.pos - 1,
                .jump_false => {
                    const condition = self.pop();
                    if (!isTrue(condition)) current_frame.ip = inst.ptr.pos - 1;
                },
                .bind_global => {
                    const val = self.pop();
                    // enlarge if global list is smaller than position
                    // we don't use 'insert(n)' because that will change the position
                    // of values behind n, but we want to overwrite it instead.
                    if (self.globals.items.len <= inst.ptr.pos)
                        try self.globals.resize(inst.ptr.pos + 1);

                    self.globals.items[inst.ptr.pos] = val;

                    if (val.isType(.function))
                        loaded_funcs += 1;
                },
                .load_global => try self.push(self.globals.items[inst.ptr.pos]),
                .make_array => try self.makeArray(inst),
                .make_map => try self.makeMap(inst),
                .make_enum => try self.makeEnum(inst),
                .get_by_index => try self.getIndexValue(),
                .set_by_index => try self.setIndexValue(),
                .@"return", .return_value => _ = self.call_stack.pop(),
                .call => try self.execFunctionCall(inst, self.code.?.instructions[current_frame.ip + 1]),
                .bind_local => {
                    const val = self.pop();
                    if (inst.ptr.pos >= self.locals.items.len)
                        try self.locals.resize(inst.ptr.pos + 1);
                    self.locals.items[inst.ptr.pos] = val;
                },
                .load_local => try self.push(self.locals.items[inst.ptr.pos]),
                .assign_global => {
                    const val = self.pop();
                    if (inst.ptr.pos >= self.globals.items.len)
                        try self.globals.resize(inst.ptr.pos + 1);
                    self.globals.items[inst.ptr.pos] = val;
                    try self.push(&Value.Void);
                },
                .assign_local => {
                    const val = self.pop();
                    if (inst.ptr.pos >= self.locals.items.len)
                        try self.locals.resize(inst.ptr.pos + 1);
                    self.locals.items[inst.ptr.pos] = val;
                    try self.push(&Value.Void);
                },
                .load_module => {
                    const string = self.pop().unwrap(.string) orelse
                        return self.fail("Expected a string");

                    const mod = try Value.Module.create(self.gc, string.value);
                    try self.push(mod);
                },
                .make_iter => try self.makeIterable(inst),
                .iter_next => try self.execNextIter(),
                .make_range => try self.makeRange(),
                .match => try self.execSwitchProng(),
                .make_slice => try self.makeSlice(),
            }
        }

        // only allow them to query through global functions
        // functions are always loaded first as they are forward declared
        // therefore we can simply resize globals list
        try self.globals.resize(loaded_funcs);
    }

    /// Pushes a new `Value` on top of the `stack` and increases
    /// the stack pointer by 1.
    fn push(self: *Vm, value: *Value) Error!void {
        if (self.sp >= self.stack.len - 1) return self.fail("Stack overflow");

        self.stack[self.sp] = value;
        self.sp += 1;
    }

    /// Returns the `Value` from the `stack` and decreases the stack
    /// pointer by 1. Asserts the stack is not empty.
    fn pop(self: *Vm) *Value {
        self.sp -= 1;
        return self.stack[self.sp];
    }

    /// Returns the previously popped `Value`
    /// Note that this results in UB if the stack is empty.
    pub fn peek(self: *Vm) *Value {
        return self.stack[self.sp];
    }

    /// Returns the current `Frame` of the call stack
    /// Asserts the call stack is not empty
    pub fn frame(self: *Vm) *Frame {
        return &self.call_stack.items[(self.call_stack.items.len - 1)];
    }

    /// Analyzes and executes a binary operation.
    fn execBinOp(self: *Vm, op: byte_code.Opcode) Error!void {
        // right is on the top of left, therefore we pop it first
        const right = self.pop();
        const left = self.pop();

        const luf_type = try self.resolveType(&[_]*Value{ left, right });

        return switch (luf_type) {
            .integer => self.execIntOp(op, left.toInteger().value, right.toInteger().value),
            .string => self.execStringOp(op, left.toString().value, right.toString().value),
            else => self.fail("Unexpected type, expected integer or string"),
        };
    }

    /// Analyzes and executes a binary operation on an integer
    fn execIntOp(self: *Vm, op: byte_code.Opcode, left: i64, right: i64) Error!void {
        const result = switch (op) {
            .add => left + right,
            .sub => left - right,
            .mul => left * right,
            .mod => if (right > 0) @mod(left, right) else return self.fail("Rhs can not be a negative integer"),
            .div => blk: {
                if (right == 0) return self.fail("Cannot divide by zero");
                break :blk @divTrunc(left, right);
            },
            .bitwise_and => left & right,
            .bitwise_xor => left ^ right,
            .bitwise_or => left | right,
            .shift_left => blk: {
                if (right < 0) return self.fail("Bit shifting not allowed for negative integers");
                break :blk if (right > std.math.maxInt(u6)) 0 else left << @intCast(u6, right);
            },
            .shift_right => blk: {
                if (right < 0) return self.fail("Bit shifting not allowed for negative integers");
                break :blk if (right > std.math.maxInt(u6)) 0 else left >> @intCast(u6, right);
            },
            else => return self.fail("Unexpected operator"),
        };

        const res = try Value.Integer.create(self.gc, result);
        return self.push(res);
    }

    /// Concats two strings together
    fn execStringOp(self: *Vm, op: byte_code.Opcode, left: []const u8, right: []const u8) Error!void {
        if (op != .add) return self.fail("Unexpected operator, expected '+'");

        const concat = try std.mem.concat(self.allocator, u8, &[_][]const u8{ left, right });
        // Creating a new String will allocate new memory for it, so free this string
        defer self.allocator.free(concat);

        const res = try Value.String.create(self.gc, concat);
        return self.push(res);
    }

    /// Analyzes the instruction, ensures the lhs is an identifier and the rhs is an integer or string.
    /// Strings are only valid for the `assign_add` bytecode instruction
    fn execAssignAndBinOp(self: *Vm, op: byte_code.Opcode) Error!void {
        const right = self.pop();
        const left = self.pop();

        if (left.ty != right.ty) return self.fail("Mismatching types");

        if (left.isType(.integer)) {
            try self.execIntOp(switch (op) {
                .assign_add => .add,
                .assign_div => .div,
                .assign_mul => .mul,
                .assign_sub => .sub,
                else => return self.fail("Unexpected operator"),
            }, left.toInteger().value, right.toInteger().value);
            const val = self.pop();

            left.toInteger().value = val.toInteger().value;
            return self.push(&Value.Void);
        }
        if (left.isType(.string)) {
            if (op != .assign_add) return self.fail("Unexpected operator on string, expected '+='");

            try self.execStringOp(.add, left.toString().value, right.toString().value);
            const val = self.pop();

            try left.toString().copyFrom(self.gc.gpa, val.toString());
            return self.push(&Value.Void);
        }

        return self.fail("Unexpected type, expected integer or string");
    }

    /// Analyzes a then executes a comparison and pushes the return value on the stack
    fn execCmp(self: *Vm, op: byte_code.Opcode) Error!void {
        // right is on the top of left, therefore we pop it first
        const right = self.pop();
        const left = self.pop();

        if (left.ty == right.ty and left.isType(.integer)) {
            return self.execIntCmp(op, left.toInteger().value, right.toInteger().value);
        }

        if (left.ty == right.ty and left.isType(.string)) {
            return self.execStringCmp(op, left.toString().value, right.toString().value);
        }

        const left_bool = left.unwrap(.boolean) orelse return self.fail("Expected boolean");
        const right_bool = right.unwrap(.boolean) orelse return self.fail("Expected boolean");

        const result = switch (op) {
            .equal => left_bool.value == right_bool.value,
            .not_equal => left_bool.value != right_bool.value,
            .@"and" => left_bool.value and right_bool.value,
            .@"or" => left_bool.value or right_bool.value,
            else => return self.fail("Unexpected operator on boolean"),
        };

        return self.push(if (result) &Value.True.base else &Value.False.base);
    }

    /// Analyzes and compares 2 integers depending on the given operator
    fn execIntCmp(self: *Vm, op: byte_code.Opcode, left: i64, right: i64) Error!void {
        const boolean = switch (op) {
            .equal => left == right,
            .not_equal => left != right,
            .greater_than => left > right,
            .greater_than_equal => left >= right,
            .less_than => left < right,
            .less_than_equal => left <= right,
            else => return self.fail("Unexpected operator"),
        };

        return self.push(if (boolean) &Value.True.base else &Value.False.base);
    }

    /// Analyzes and compares 2 strings
    fn execStringCmp(self: *Vm, op: byte_code.Opcode, left: []const u8, right: []const u8) Error!void {
        var eql = std.mem.eql(u8, left, right);
        switch (op) {
            .equal => {},
            .not_equal => eql = !eql,
            else => return self.fail("Unexpected operator, expected '==' or '!='"),
        }

        return self.push(if (eql) &Value.True.base else &Value.False.base);
    }

    /// Analyzes and executes a negation
    fn execNegation(self: *Vm) Error!void {
        const right = self.pop();
        const integer = right.unwrap(.integer) orelse return self.fail("Expected integer");

        const ret = try Value.Integer.create(self.gc, -integer.value);
        return self.push(ret);
    }

    /// Analyzes and executes the '!' operator
    fn execNot(self: *Vm) Error!void {
        const right = self.pop();

        const val = switch (right.ty) {
            .boolean => !right.toBool().value,
            .nil => true,
            else => false,
        };

        return self.push(if (val) &Value.True.base else &Value.False.base);
    }

    /// Executes the ~ operator
    fn execBitwiseNot(self: *Vm) Error!void {
        const value = self.pop();
        const integer = value.unwrap(.integer) orelse return self.fail("Expected integer");

        const ret = try Value.Integer.create(self.gc, ~integer.value);
        return self.push(ret);
    }

    /// Analyzes the instruction and builds an array
    fn makeArray(self: *Vm, inst: byte_code.Instruction) Error!void {
        const len = inst.ptr.pos;

        const ret = try Value.List.create(self.gc, len);
        var list = ret.toList();
        list.value.items.len = len;

        if (len == 0) {
            return self.push(ret);
        }

        var list_type: Type = undefined;
        var i: usize = 1;

        while (i <= len) : (i += 1) {
            const val = self.pop();

            if (i == 1)
                list_type = val.ty
            else if (!val.isType(list_type)) return self.fail("Mismatching types");
            list.value.items[len - i] = val;
        }

        return self.push(ret);
    }

    /// Analyzes and creates a new map
    fn makeMap(self: *Vm, inst: byte_code.Instruction) Error!void {
        const len = inst.ptr.pos;
        const ret = try Value.Map.create(self.gc, len);
        var map = ret.toMap();

        if (len == 0) {
            return self.push(ret);
        }

        var key_type: Type = undefined;
        var value_type: Type = undefined;
        var i: usize = 0;

        while (i < len) : (i += 1) {
            const value = self.pop();
            const key = self.pop();

            if (i == 0) {
                key_type = key.ty;
                value_type = value.ty;
            } else {
                if (!key.isType(key_type)) return self.fail("Mismatching types");
                if (!value.isType(value_type)) return self.fail("Mismatching types");
            }

            map.value.putAssumeCapacity(key, value);
        }

        return self.push(ret);
    }

    /// Constructs a new enum `Value`
    fn makeEnum(self: *Vm, inst: byte_code.Instruction) Error!void {
        const len = inst.ptr.pos;

        var enums_values = std.ArrayList([]const u8).init(self.allocator);
        try enums_values.resize(len);
        defer enums_values.deinit();

        var i: usize = len;
        while (i > 0) : (i -= 1) {
            const string = self.pop().unwrap(.string) orelse return self.fail("Enum contains invalid field");
            enums_values.items[i - 1] = string.value;
        }

        const enm = try Value.Enum.create(self.gc, enums_values.toOwnedSlice());
        return self.push(enm);
    }

    /// Creates a new iterable
    fn makeIterable(self: *Vm, inst: byte_code.Instruction) Error!void {
        const iterable = self.pop();

        switch (iterable.ty) {
            .list, .range, .string => {},
            else => return self.fail("Unsupported value for iterable"),
        }

        const value = try Value.Iterable.create(
            self.gc,
            inst.ptr.pos != 0,
            0,
            iterable,
        );

        return self.push(value);
    }

    /// Pops the iterator from the stack and retrieves the next value
    /// Pushes the iterator back, then the value and then the index if exposed
    /// Finally, a true or false is pushed to determine if we should end the for loop
    fn execNextIter(self: *Vm) Error!void {
        const value = self.pop();
        // we mark the iterator here, because it's currently not being referenced by anything
        // until it is pushed back on the stack, this means it bould be sweeped when we call iterator.next()
        self.gc.mark(value);

        var iterator = value.toIterable();
        if (try iterator.next(self.gc)) |next| {
            // push the iterator back on the stack
            try self.push(value);

            // push the capture on the stack
            try self.push(next);

            // push the index if it is exposed
            if (iterator.expose_index)
                try self.push(
                    try Value.Integer.create(self.gc, @intCast(i64, iterator.index - 1)),
                );

            // push true to continue
            return self.push(&Value.True.base);
        } else {
            return self.push(&Value.False.base);
        }
    }

    /// Creates a range from 2 values
    /// Returns an error if lhs or rhs is not an integer
    fn makeRange(self: *Vm) Error!void {
        const right = self.pop();
        const left = self.pop();

        const ret = try Value.Range.create(
            self.gc,
            left.toInteger().value,
            right.toInteger().value,
        );
        return self.push(ret);
    }

    /// Analyzes an index/reference pushes the value on the stack
    fn getIndexValue(self: *Vm) Error!void {
        const index = self.pop();
        const left = self.pop();

        switch (left.ty) {
            .list => {
                var list = left.toList().value;
                switch (index.ty) {
                    .integer => {
                        const int = index.toInteger().value;
                        if (int < 0 or int > list.items.len) return self.fail("Out of bounds");
                        return self.push(list.items[@intCast(u64, int)]);
                    },
                    .string => {
                        const name = index.toString().value;
                        if (_builtin.builtins.get(name)) |val| {
                            const builtin = val.toNative();
                            const args = try self.allocator.alloc(*Value, builtin.arg_len + 1);
                            defer self.allocator.free(args);
                            args[0] = left;
                            var i: usize = 1;

                            while (i <= builtin.arg_len) : (i += 1) args[i] = self.pop();

                            const res = builtin.func(
                                self.gc,
                                args,
                            ) catch return self.fail("Could not execute builtin function");

                            return self.push(res);
                        }
                    },
                    else => return self.fail("Expected string or integer on rhs"),
                }
            },
            .map => {
                if (left.toMap().value.get(index)) |val| {
                    return self.push(val);
                }
                // We return null to the user so they have something to check against
                // to see if a key exists or not.
                return self.push(&Value.Nil);
            },
            .string => {
                const string = left.toString().value;
                switch (index.ty) {
                    .integer => {
                        const int = index.toInteger().value;
                        if (int < 0 or int > string.len) return self.fail("Out of bounds");

                        const val = try Value.String.create(
                            self.gc,
                            string[@intCast(usize, int)..@intCast(usize, int + 1)],
                        );
                        return self.push(val);
                    },
                    .string => {
                        const name = index.toString().value;
                        if (_builtin.builtins.get(name)) |val| {
                            const builtin = val.toNative();

                            const res = builtin.func(
                                self.gc,
                                &[_]*Value{left},
                            ) catch return self.fail("Could not execute builtin function");

                            return self.push(res);
                        }
                    },
                    else => return self.fail("Expected string or integer on rhs"),
                }
            },
            ._enum => {
                const enm = left.toEnum().value;
                const enum_value = index.unwrap(.string) orelse return self.fail("Expected string");

                for (enm) |field, i| {
                    if (std.mem.eql(u8, field, enum_value.value)) {
                        const ret = try Value.Integer.create(self.gc, @intCast(i64, i));
                        return self.push(ret);
                    }
                }

                return self.fail("Enum identifier does not exist");
            },
            .module => {
                const mod = left.toModule().value;

                const lib = self.libs.get(mod) orelse return self.fail("Library does not exist");

                const value: *Value = if (!lib.isType(.map))
                    lib
                else
                    lib.toMap().value.get(index) orelse return self.fail("Library x does not have member y");

                return self.push(value);
            },
            else => return self.fail("Unsupported type"),
        }
    }

    /// Sets the lhs by the value on top of the current stack
    /// This also does type checking to ensure the lhs and rhs are equal types
    fn setIndexValue(self: *Vm) Error!void {
        const value = self.pop();
        const right = self.pop();
        const left = self.pop();

        if (left.isType(.list) and right.isType(.integer)) {
            const list = left.toList().value;
            const integer = right.toInteger().value;

            if (integer < 0 or integer > list.items.len) return self.fail("Out of bounds");

            list.items[@intCast(usize, integer)] = value;
            return self.push(&Value.Void);
        } else if (left.isType(.map)) {
            var map = left.toMap();
            if (map.value.get(right)) |*val| {
                try map.value.put(self.gc.gpa, right, value);
                return self.push(&Value.Void);
            } else {
                // replace with more descriptive Error
                return self.fail("Value not found");
            }
        }

        // replace with more descriptive Error
        return self.fail("Unsupported type");
    }

    /// Analyzes the current instruction to execture a function call
    /// Expects the current instruction pointer.
    /// This will also return the new instruction pointer
    ///
    /// `next` is required to detect if we can optimize tail recursion
    fn execFunctionCall(self: *Vm, inst: byte_code.Instruction, next: byte_code.Instruction) Error!void {
        const arg_len = inst.ptr.pos;
        const val = self.pop();

        if (val.isType(.native) or val.isType(.module)) return self.execNativeFuncCall(val);
        if (val.ty != .function)
            return self.push(val); //put it back on stack

        if (arg_len != val.toFunction().arg_len) return self.fail("Mismatching argument length");

        var cur_frame = self.frame();
        if (cur_frame.fp == val and next.op == .return_value) {
            var i: usize = arg_len;
            while (i > 0) : (i -= 1) {
                if (i >= self.locals.items.len)
                    try self.locals.resize(i);
                self.locals.items[i - 1] = self.stack[self.sp - i];
            }
            cur_frame.ip = val.toFunction().entry;
            return;
        }

        try self.call_stack.append(.{
            .fp = val,
            .ip = val.toFunction().entry,
        });

        {
            var i: usize = arg_len;
            while (i > 0) : (i -= 1) {
                if (i >= self.locals.items.len)
                    try self.locals.resize(i);
                self.locals.items[i - 1] = self.pop();
            }
        }
    }

    /// Executes a native Zig function call
    fn execNativeFuncCall(self: *Vm, value: *Value) Error!void {
        const func = if (value.isType(.native)) value.toNative() else blk: {
            const mod = value.unwrap(.module) orelse return self.fail("Expected module");
            const lib = self.libs.get(mod.value) orelse return self.fail("Library is not loaded");
            break :blk lib.unwrap(.native) orelse return self.fail("Loaded library is not a function");
        };

        var args = try self.allocator.alloc(*Value, func.arg_len);
        defer self.allocator.free(args);

        for (args) |*arg| {
            arg.* = self.pop();
        }

        const result = func.func(self.gc, args) catch return self.fail("Could not execute Zig function");
        return self.push(result);
    }

    /// Compares switch' capture and the current prong.
    /// Unlike execCmp, this does not pop the lhs value from the stack, to maintain it's position
    /// as it's used for the other prongs. it will be popped at the end of the switch statement.
    fn execSwitchProng(self: *Vm) Error!void {
        const prong_value = self.pop();
        const capture_value = self.stack[self.sp - 1];

        switch (prong_value.ty) {
            .integer => {
                const capture = capture_value.unwrap(.integer) orelse return self.fail("Expected an integer");
                return self.execIntCmp(.equal, capture.value, prong_value.toInteger().value);
            },
            .string => {
                const capture = capture_value.unwrap(.string) orelse return self.fail("Expected a string");
                return self.execStringCmp(.equal, capture.value, prong_value.toString().value);
            },
            .range => {
                const capture = capture_value.unwrap(.integer) orelse return self.fail("Expected an integer");
                const range = prong_value.toRange();
                const result = capture.value >= range.start and capture.value <= range.end;

                return self.push(if (result) &Value.True.base else &Value.False.base);
            },
            else => return self.fail("Unsupported type, switching are only allowed for integers, strings and ranges"),
        }
    }

    /// Creates a new list from a slice expression, and then pushes this value
    /// to the stack
    fn makeSlice(self: *Vm) Error!void {
        const end = self.pop();
        const start = self.pop();
        const list = self.pop();

        if (!list.isType(.list)) return self.fail("Expected a list, but instead found a different type");

        const start_num = @intCast(usize, start.toInteger().value);
        const end_num = if (end.unwrap(.integer)) |int| @intCast(usize, int.value) else list.toList().value.items.len;

        const len = end_num - start_num;

        // create our new list and fill it with values from the original list
        const ret = try Value.List.create(self.gc, len);
        const new_list = ret.toList();
        new_list.value.items.len = len;

        var i: usize = start_num;
        while (i < end_num) : (i += 1) {
            new_list.value.items[i - start_num] = list.toList().value.items[i];
        }

        return self.push(ret);
    }

    /// Appends an error message to `errors` and returns a `Vm.Error`
    fn fail(self: *Vm, comptime msg: []const u8) Error!void {
        //TODO implement a way to add location information
        try self.errors.add("Runtime error: " ++ msg, 0, .err, .{});
        return Error.RuntimeError;
    }

    /// Checks each given type if they are equal or not
    fn resolveType(self: *Vm, values: []*const Value) Error!Type {
        std.debug.assert(values.len > 0);
        const cur_tag: Type = values[0].ty;
        if (values.len == 1) return cur_tag;

        for (values[1..]) |value|
            if (!value.isType(cur_tag)) try self.fail("Mismatching types");

        return cur_tag;
    }
};

/// Evalutes if the given `Value` is truthy.
/// Only accepts booleans and 'Nil'.
fn isTrue(value: *Value) bool {
    return switch (value.ty) {
        .nil => false,
        .boolean => value.toBool().value,
        else => true,
    };
}

test "Integer arithmetic" {
    const test_cases = .{
        .{ .input = "1", .expected = 1 },
        .{ .input = "2", .expected = 2 },
        .{ .input = "1 + 1", .expected = 2 },
        .{ .input = "1 * 3", .expected = 3 },
        .{ .input = "1 - 3", .expected = -2 },
        .{ .input = "10 / 2", .expected = 5 },
        .{ .input = "10 % 2", .expected = 0 },
        .{ .input = "1 | 2", .expected = 3 },
        .{ .input = "2 ^ 4", .expected = 6 },
        .{ .input = "3 & 6", .expected = 2 },
        .{ .input = "-2", .expected = -2 },
        .{ .input = "1 << 2", .expected = 4 },
        .{ .input = "4 >> 2", .expected = 1 },
        .{ .input = "~1", .expected = -2 },
        .{ .input = "(5 + 10 * 2 + 15 / 3) * 2 + -10", .expected = 50 },
        .{ .input = "mut x = 0 x+= 1 x", .expected = 1 },
        .{ .input = "mut x = 2 x*= 2 x", .expected = 4 },
        .{ .input = "mut x = 10 x/= 2 x", .expected = 5 },
        .{ .input = "mut x = 1 x-= 1 x", .expected = 0 },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        try testing.expect(case.expected == vm.peek().toInteger().value);
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Boolean" {
    const test_cases = .{
        .{ .input = "true", .expected = true },
        .{ .input = "false", .expected = false },
        .{ .input = "1 < 2", .expected = true },
        .{ .input = "1 > 2", .expected = false },
        .{ .input = "1 == 1", .expected = true },
        .{ .input = "1 != 1", .expected = false },
        .{ .input = "true != true", .expected = false },
        .{ .input = "!true", .expected = false },
        .{ .input = "true and true", .expected = true },
        .{ .input = "true and false", .expected = false },
        .{ .input = "false and false", .expected = false },
        .{ .input = "true or false", .expected = true },
        .{ .input = "true or true", .expected = true },
        .{ .input = "false or false", .expected = false },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        try testing.expect(case.expected == vm.peek().toBool().value);
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Conditional expression" {
    const test_cases = .{
        .{ .input = "if true { 10 }", .expected = 10 },
        .{ .input = "if true { 10 } else { 20 }", .expected = 10 },
        .{ .input = "if false { 10 } else { 20 }", .expected = 20 },
        .{ .input = "if 1 < 2 { 10 }", .expected = 10 },
        .{ .input = "if 1 > 2 { 10 }", .expected = &Value.Void },
        .{ .input = "if 1 > 2 { 10 } else if 2 > 3 { 20 } else { 5 }", .expected = 5 },
        .{ .input = "if 1 > 2 { 10 } else if 2 < 3 { 20 } else { 5 }", .expected = 20 },
        .{ .input = "mut x = 5 if x < 10 { x = 2  } else if x < 3 { x = 1 } else { x = 0 } x", .expected = 2 },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();

        try vm.compileAndRun(case.input);

        if (@TypeOf(case.expected) == comptime_int) {
            try testing.expectEqual(@as(i64, case.expected), vm.peek().toInteger().value);
        } else {
            try testing.expectEqual(case.expected, vm.peek());
        }
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Declaration" {
    const test_cases = .{
        .{ .input = "const x = 1 x", .expected = 1 },
        .{ .input = "const x = 1 const y = 1 x + y", .expected = 2 },
        .{ .input = "mut x = 1 const y = x + x x + y", .expected = 3 },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        try testing.expectEqual(@as(i64, case.expected), vm.peek().toInteger().value);
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Strings" {
    const test_cases = .{
        .{ .input = "\"foo\"", .expected = "foo" },
        .{ .input = "\"foo\" + \"bar\"", .expected = "foobar" },
        .{ .input = "const x = \"foo\" x+=\"bar\" x", .expected = "foobar" },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        try testing.expectEqualStrings(case.expected, vm.peek().toString().value);
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Arrays" {
    const test_cases = .{
        .{ .input = "[]int{1, 2, 3}", .expected = &[_]i64{ 1, 2, 3 } },
        .{ .input = "[]int{}", .expected = &[_]i64{} },
        .{ .input = "[]int{1 + 1, 2 * 2, 6}", .expected = &[_]i64{ 2, 4, 6 } },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        const list = vm.peek().toList();
        try testing.expectEqual(case.expected.len, list.value.items.len);
        inline for (case.expected) |int, i| {
            const items = list.value.items;
            try testing.expectEqual(int, items[i].toInteger().value);
        }
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Maps" {
    const test_cases = .{
        .{ .input = "[]int:int{1:2, 2:1, 5:6}", .expected = &[_]i64{ 6, 1, 2 }, .keys = &[_]i64{ 5, 2, 1 } },
        .{ .input = "[]int:int{}", .expected = &[_]i64{}, .keys = &[_]i64{} },
        .{ .input = "[]string:int{\"foo\":1}", .expected = &[_]i64{1}, .keys = &[_][]const u8{"foo"} },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        const map = vm.peek().toMap().value;
        try testing.expect(map.items().len == case.expected.len);
        inline for (case.expected) |int, i| {
            const items = map.items();
            try testing.expectEqual(int, items[i].value.toInteger().value);
        }

        inline for (case.keys) |key, i| {
            const item = map.items()[i];
            if (@TypeOf(key) == i64) {
                try testing.expectEqual(key, item.key.toInteger().value);
            } else {
                try testing.expectEqualStrings(key, item.key.toString().value);
            }
        }
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Index" {
    const test_cases = .{
        .{ .input = "[]int{1, 2, 3}[1]", .expected = 2 },
        .{ .input = "const list = []int{1, 2, 3} list[1] = 10 list[1]", .expected = 10 },
        .{ .input = "[]int:int{1: 5}[1]", .expected = 5 },
        .{ .input = "[]int:int{2: 5}[0]", .expected = &Value.Nil },
        .{ .input = "[]int:int{2: 5}[2] = 1", .expected = &Value.Void },
        .{ .input = "const map = []int:int{2: 5} map[2] = 1 map[2]", .expected = 1 },
        .{ .input = "[]string:int{\"foo\": 15}[\"foo\"]", .expected = 15 },
        .{ .input = "\"hello\"[1]", .expected = "e" },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        if (@TypeOf(case.expected) == comptime_int)
            try testing.expectEqual(@as(i64, case.expected), vm.peek().toInteger().value)
        else if (@TypeOf(case.expected) == *const [1:0]u8)
            try testing.expectEqualStrings(case.expected, vm.peek().toString().value)
        else {
            try testing.expectEqual(case.expected, vm.peek());
        }
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Basic function calls with no arguments" {
    const test_cases = .{
        .{ .input = "const x = fn() int { return 1 + 2 } x()", .expected = 3 },
        .{ .input = "const x = fn() int { return 1 } const y = fn() int { return 5 } x() + y()", .expected = 6 },
        .{ .input = "const x = fn() int { return 5 10 } x()", .expected = 5 },
        .{ .input = "const x = fn() void { } x()", .expected = &Value.Void },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        if (@TypeOf(case.expected) == comptime_int)
            try testing.expectEqual(@as(i64, case.expected), vm.peek().toInteger().value)
        else {
            try testing.expectEqual(case.expected, vm.peek());
        }
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Globals vs Locals" {
    const test_cases = .{
        .{ .input = "const x = fn() int { const x = 5 return x } x()", .expected = 5 },
        .{ .input = "const x = fn() int { const y = 1 const z = 2 return y + z } x()", .expected = 3 },
    };

    inline for (test_cases) |case, i| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        if (i == 0) {
            try testing.expectError(compiler.Compiler.Error.CompilerError, vm.compileAndRun(case.input));
            continue;
        } else
            try vm.compileAndRun(case.input);

        if (@TypeOf(case.expected) == comptime_int)
            try testing.expectEqual(@as(i64, case.expected), vm.peek().toInteger().value)
        else
            try testing.expectEqual(case.expected, vm.peek());
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Functions with arguments" {
    const test_cases = .{
        .{ .input = "const x = fn(x: int) int { return x } x(3)", .expected = 3 },
        .{ .input = "const x = fn(a: int, b: int) int { return a + b } x(3,5)", .expected = 8 },
        .{ .input = "const x = fn(a: int, b: int) int { const z = a + b return z } x(3,5)", .expected = 8 },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        if (@TypeOf(case.expected) == comptime_int)
            try testing.expectEqual(@as(i64, case.expected), vm.peek().toInteger().value)
        else
            try testing.expectEqual(case.expected, vm.peek());
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Builtins" {
    const test_cases = .{
        .{ .input = "\"Hello world\".len", .expected = 11 },
        .{ .input = "[]int{1,5,2}.len", .expected = 3 },
        .{ .input = "const x = []int{1} x.add(2) x.len", .expected = 2 },
        .{ .input = "const x = []int{1, 2} x.pop() x.len", .expected = 1 },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();

        try vm.compileAndRun(case.input);
        try testing.expectEqual(@as(i64, case.expected), vm.peek().toInteger().value);
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "While loop" {
    const test_cases = .{
        .{ .input = "mut i = 0 while i > 10 {i = 10} i", .expected = 0 },
        .{ .input = "mut i = 0 while i < 10 {i = 10} i", .expected = 10 },
        .{ .input = "mut i = 0 while i < 10 { if i == 5 { break } i = 5} i", .expected = 5 },
    };

    inline for (test_cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();
        try vm.compileAndRun(case.input);

        try testing.expectEqual(@as(i64, case.expected), vm.peek().toInteger().value);
        try testing.expectEqual(@as(usize, 0), vm.sp);
    }
}

test "Tail recursion" {
    const input =
        \\const func = fn(a: int) int {
        \\  if (a == 10) {
        \\      return a
        \\  }
        \\  return func(a + 1)
        \\}
        \\const f: int = func(2)
    ;
    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);

    try testing.expectEqual(@as(i64, 10), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Basic For loop" {
    const input =
        \\mut sum = 0
        \\for item: []int{1, 3, 5, 7, 9} {
        \\  sum += item
        \\}
        \\sum
    ;
    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);
    try testing.expectEqual(@as(i64, 25), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "For loop continue + break" {
    const input =
        \\mut sum = 0
        \\for item, i: []int{1, 3, 5, 7, 9} {
        \\  if (item == 3) {
        \\      continue
        \\  }
        \\  if (item == 7) {
        \\      break
        \\  }
        \\  sum += item + i
        \\}
        \\sum
    ;
    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);
    try testing.expectEqual(@as(i64, 8), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Range" {
    const input =
        \\mut sum = 0
        \\for e, i: 1..100 {
        \\  if (e % 2 == 0) {
        \\      continue
        \\  }
        \\  sum += e + i
        \\}
        \\sum
    ;
    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);

    try testing.expectEqual(@as(i64, 4950), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "For loop - String" {
    const input = "mut result = \"hello\" const w = \"world\" for c, i: w {result+=c}result";
    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);

    try testing.expectEqualStrings("helloworld", vm.peek().toString().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Enum expression and comparison" {
    const input =
        \\const x = enum{value, another_value}
        \\const enum_value = x.another_value
        \\if (enum_value == x.another_value) {
        \\  5
        \\}
        \\enum_value
    ;
    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);

    try testing.expectEqual(@as(i64, 1), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Switch case" {
    const input =
        \\const range = 0..9
        \\mut x = 0
        \\switch(5) {
        \\  4: x += 10,
        \\  range: x += 30,
        \\  5: x += 20
        \\}
        \\x
    ;
    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);

    try testing.expectEqual(@as(i64, 50), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Forward declared" {
    const input =
        \\ const x = add(2, 5)
        \\ const add = fn(a: int, b: int) int {
        \\      return sum(a + b)
        \\ }
        \\ const sum = fn(a: int) int {
        \\      return a + 1
        \\ }
    ;

    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);
    try testing.expectEqual(@as(i64, 8), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Import module" {
    const input =
        \\const imp = import("examples/to_import.luf")
        \\const x = imp.add(10)
    ;

    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);
    try testing.expectEqual(@as(i64, 30), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Luf function from Zig" {
    const input =
        \\const add = fn(a: int, b: int) int {
        \\  return a + b
        \\}
        \\const concat = fn(a: string) string {
        \\  return a + " world"
        \\}
    ;
    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    var cu = try compiler.compile(testing.allocator, input, &vm.errors);
    defer cu.deinit();
    var code = try byte_code.Instructions.fromCu(testing.allocator, cu);
    defer code.deinit();

    vm.loadCode(&code);
    try vm.run();
    const val = try vm.callFunc("add", .{ 2, 5 });
    const val2 = try vm.callFunc("concat", .{"hello"});

    try testing.expectEqual(@as(i64, 7), val.toInteger().value);
    try testing.expectEqualStrings("hello world", val2.toString().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Inner functions" {
    const input =
        \\const add = fn(a: int, b: int) int {
        \\  const plusTen = fn(a: int) int {
        \\      return a + 10
        \\  }
        \\
        \\  return plusTen(a + b)
        \\}
        \\const x = add(20, 30)
    ;

    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);
    try testing.expectEqual(@as(i64, 60), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

fn testZigFromLuf(a: u32, b: u32) u32 {
    return a + b;
}

test "Zig from Luf" {
    const input =
        \\const sum = import("zig")
        \\const result = sum(2, 5)
        \\result
    ;
    var vm = try Vm.init(testing.allocator);
    try vm.loadLib("zig", testZigFromLuf);
    defer vm.deinit();
    try vm.compileAndRun(input);
    try testing.expectEqual(@as(i64, 7), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Luf std" {
    const input =
        \\const std = import("std")
        \\std.math.log(10, 2)
    ;
    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();
    try vm.compileAndRun(input);
    try testing.expectEqual(@as(i64, 3), vm.peek().toInteger().value);
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Optionals" {
    const input =
        \\ mut x: ?int = nil
        \\ x = 5
        \\ x = nil
        \\ x
    ;

    var vm = try Vm.init(testing.allocator);
    defer vm.deinit();

    try vm.compileAndRun(input);
    try testing.expectEqual(&Value.Nil, vm.peek());
    try testing.expectEqual(@as(usize, 0), vm.sp);
}

test "Slices" {
    const cases = .{
        .{ .input = "const list = []int{2, 4, 6} const slice = list[1:3]", .expected = .{ 4, 6 } },
        .{ .input = "const list = []int{2, 4, 6} const slice = list[:2]", .expected = .{ 2, 4 } },
        .{ .input = "const list = []int{2, 4, 6} const slice = list[1:]", .expected = .{ 4, 6 } },
    };

    inline for (cases) |case| {
        var vm = try Vm.init(testing.allocator);
        defer vm.deinit();

        try vm.compileAndRun(case.input);

        const list = vm.peek().toList().value;
        try testing.expectEqual(@as(usize, 2), list.items.len);
        try testing.expectEqual(@as(i64, case.expected[0]), list.items[0].toInteger().value);
        try testing.expectEqual(@as(i64, case.expected[1]), list.items[1].toInteger().value);
    }
}
