void Interpreter::run(HiString* codes) {
    int pc = 0;
    int code_length = codes->length();  

    _stack  = new int[16];  // 创建一个运行时栈
    int top = 0;
    // 使用一个大的循环不断地从字节码数组中取出指令
    while (pc < code_length) {
        unsigned char op_code = codes->value()[pc++];
        bool has_argument = (op_code & 0xFF) >= ByteCode::HAVE_ARGUMENT;

        int op_arg = -1;
        if (has_argument) {
            op_arg = (codes->value()[pc++] & 0xFF);
        }
        int v, w;
        // 分别对不同的指令进行处理
        switch (op_code) {
            case ByteCode::LOAD_CONST:
                _stack[top++] = op_arg;
                break;

            case ByteCode::BINARY_ADD:
                v = _stack[--top];
                w = _stack[--top];
                _stack[top++] = v + w;
                break;

            case ByteCode::BINARY_MULTIPLY:
                v = _stack[--top];
                w = _stack[--top];
                _stack[top++] = v * w;
                break;

            default:
                printf("Error: Unrecognized byte code %d\n", op_code);
        }
    }
    printf("%d\n", _stack[0]);

    delete[] _stack;
}

class Klass {
private:
    HiString*     _name;    // 类的名称

public:
    Klass() {};

    void set_name(HiString* x)            { _name = x; }
    HiString* name()                      { return _name; }

    virtual void print(HiObject* obj) {};
    virtual HiObject* greater  (HiObject* x, HiObject* y) { return 0; }
    virtual HiObject* less     (HiObject* x, HiObject* y) { return 0; }
    virtual HiObject* equal    (HiObject* x, HiObject* y) { return 0; }
    virtual HiObject* not_equal(HiObject* x, HiObject* y) { return 0; }
    virtual HiObject* ge       (HiObject* x, HiObject* y) { return 0; }
    virtual HiObject* le       (HiObject* x, HiObject* y) { return 0; }

    virtual HiObject* add(HiObject* x, HiObject* y) { return 0; }
    virtual HiObject* sub(HiObject* x, HiObject* y) { return 0; }
    virtual HiObject* mul(HiObject* x, HiObject* y) { return 0; }
    virtual HiObject* div(HiObject* x, HiObject* y) { return 0; }
    virtual HiObject* mod(HiObject* x, HiObject* y) { return 0; }
};
// object/hiObject.hpp
class HiObject {
private:
    Klass*  _klass; // 指向 Klass 的指针，用于表示这个对象的类型。

public:
    Klass* klass()             { assert(_klass != NULL); return _klass; }
    void set_klass(Klass* x)   { _klass = x; }

    void print();
    HiObject* add(HiObject* x);
    HiObject* sub(HiObject* x);
    HiObject* mul(HiObject* x);
    HiObject* div(HiObject* x);
    HiObject* mod(HiObject* x);

    HiObject* greater  (HiObject* x);
    HiObject* less     (HiObject* x);
    HiObject* equal    (HiObject* x);
    HiObject* not_equal(HiObject* x);
    HiObject* ge       (HiObject* x);
    HiObject* le       (HiObject* x);
};
// 把 HiObject 中的函数都实现为转向调用自己所对应的 Klass 中的函数。
// object/hiObject.cpp
void HiObject::print() {
    klass()->print(this);
}
HiObject* HiObject::greater(HiObject * rhs) {
    return klass()->greater(this, rhs);
}
// other comparision methods.
// ...
HiObject* HiObject::add(HiObject * rhs) {
    return klass()->add(this, rhs);
}
// other arithmatic methods.
// ...

class FrameObject {
public:
    FrameObject(CodeObject* codes);
    ~FrameObject();

    ArrayList<HiObject*>* _stack;
    ArrayList<Block*>*    _loop_stack;

    ArrayList<HiObject*>* _consts;
    ArrayList<HiObject*>* _names;

    Map<HiObject*, HiObject*>* _locals; // 记录了局部变量的值。有一个LOAD_NAME zh
    Map<HiObject*, HiObject*>* _globals;    // 全局变量

    CodeObject*           _codes;
    int                   _pc;  // 记录了程序当前执行到的位置
    _sender = NULL;             // 记录调用者的栈帧，当函数执行结束的时候，就会通过这个域返回到调用者的栈帧里。

public:
    void set_pc(int x)              { _pc = x; }
    int  get_pc()                   { return _pc; }

    ArrayList<HiObject*>* stack()                 { return _stack; }
    ArrayList<Block*>* loop_stack()               { return _loop_stack; }
    ArrayList<HiObject*>* consts()                { return _consts; }
    ArrayList<HiObject*>* names()                 { return _names; }
    Map<HiObject*, HiObject*>* locals()           { return _locals; }

    bool has_more_codes();
    unsigned char get_op_code();
    int  get_op_arg();
};

void Interpreter::run(CodeObject* codes) {
    _frame = new FrameObject(codes);
    eval_frame();
    destroy_frame();
}

void Interpreter::eval_frame() {
    ...
    while (_frame->has_more_codes()) {
      unsigned char op_code = _frame->get_op_code();
        ...
        FunctionObject* fo;
        ...
        switch (op_code) {
            ...
            case ByteCode::CALL_FUNCTION:
                // 将 FrameObject 切换到新函数后，，返回到 run 方法里继续执行。_frame变量已经发生了变化。_frame 里的程序计数器已经指向要调用的目标方法里了。
                build_frame(POP()); 
                break;
            case ByteCode::RETURN_VALUE:
                _ret_value = POP();
                if (_frame->is_first_frame())   // 如果某个 FrameObject 的 sender 为 NULL，就代表它是第一个栈帧，是程序开始的地方，或者说是“主程序”，因为它没有调用者。直接结束 run 的逻辑即可
                    return;
                leave_frame();
                break;
            ...
        }
    }
}
void Interpreter::build_frame(HiObject* callable) {
    FrameObject* frame = new FrameObject((FunctionObject*) callable);
    frame->set_sender(_frame);
    _frame = frame;
}
void Interpreter::leave_frame() {
    destroy_frame();    // 将被调用者的 FrameObject 销毁
    PUSH(_ret_value);   // 将返回值 push 到调用者的栈帧中去
}
void Interpreter::destroy_frame() {
    FrameObject* temp = _frame;
    _frame = _frame->sender();  // 将 _frame 变量切换为自己的调用者的栈帧
    delete temp;    // FrameObject 的生命周期是确定的，所以使用 delete 来销毁和释放，其它虚拟机的内部对象都会使用垃圾回收器进行自动管理
}

class Heap {
private:
    Space* mem_1;
    Space* mem_2;
    
    Space* eden;
    Space* survivor;

    Space* metaspace;

    Heap(size_t size);

public:
    static size_t MAX_CAP;
    static Heap* instance;
    static Heap* get_instance();

    ~Heap();

    void* allocate(size_t size);
    void* allocate_meta(size_t size);
    void copy_live_objects();
    double rate() { return eden->rate(); }

    void gc();
};

class Space {
friend class Heap;
private:
    char*  _base;
    char*  _top;
    char*  _end;
    size_t _size;
    size_t _capacity;
    double _rate;

    Space(size_t size);
    ~Space();

public:
    void* allocate(size_t size);
    void clear();
    bool can_alloc(size_t size);
    bool has_obj(char* obj);
    double rate()  { return _rate; }
};

Heap*  Heap::instance = nullptr;
size_t Heap::MAX_CAP = 2 * 1024 * 1024;

Heap* Heap::get_instance() {
    if (instance == nullptr)
        instance = new Heap(MAX_CAP);

    return instance;
}

// 指定堆中每个 space 的容量大小
Heap::Heap(size_t size) {
    mem_1 = new Space(size);
    mem_2 = new Space(size);
    metaspace = new Space(size / 16);

    mem_1->clear();
    mem_2->clear();
    metaspace->clear();

    eden = mem_1;
    survivor = mem_2;
}

Heap::~Heap() {
    if (mem_1) {
        delete mem_1;
        mem_1 = nullptr;
    }
    if (mem_2) {
        delete mem_2;
        mem_2 = nullptr;
    }
    if (metaspace) {
        delete metaspace;
        metaspace = nullptr;
    }
    eden = nullptr;
    survivor = nullptr;
}
// 定义了从堆中申请内存的逻辑。如果当前的 eden 区足够分配，那就直接分配，如果不够分配，就调用一次 gc 方法，进行内存回收，然后再分配。
void* Heap::allocate(size_t size) {
    if (!eden->can_alloc(size)) {
        gc();
    }
    return eden->allocate(size);
}
// 从 meta 空间中申请内存
void* Heap::allocate_meta(size_t size) {
    if (!metaspace->can_alloc(size)) {
        // 由于我们的垃圾回收算法在回收时不会回收 meta 空间内的对象，所以如果 meta 空间不够用的时候，就只能报错退出。
        return nullptr;
    }
    return metaspace->allocate(size);
}

void Heap::copy_live_objects() {
    ScavengeOopClosure(eden, survivor, metaspace).scavenge();
}
void Heap::gc() {
    // 调用 copy_live_objects 将存活对象复制到 survivor 空间中去
    // 交换 eden 和 survivor 指针
}

// [runtime/universe]
class Universe {
public:
    ...
    static Heap* heap;
    static void genesis();
};

Heap* Universe::heap          = nullptr;
void Universe::genesis() {
    heap = Heap::get_instance();
    ...
}
// [object/hiObject]
class HiObject {
    ...
public:
    ...
    void* operator new(size_t size);
};
void* HiObject::operator new(size_t size) {
    return Universe::heap->allocate(size);
}

// [runtime/universe]
class Universe {
public:
    ...
    static ArrayList<Klass*>* klasses;
};
// 在 Universe 里新增了一个元素类型为 Klass 指针的 ArrayList，名字为 klasses，用于记录整个虚拟机中所有的 Klass。通过这种方式可以知道虚拟机创建了哪些 Klass，方便我们快速遍历。
ArrayList<Klass*>* Universe::klasses   = NULL;
void Universe::genesis() {
    heap = Heap::get_instance();
    klasses = new ArrayList<Klass*>();
    ...
}

// [object/klass]
class Klass {
public:
    ...
    void* operator new(size_t size);
};
void* Klass::operator new(size_t size) {
    return Universe::heap->allocate_meta(size);
}
Klass::Klass() {
    Universe::klasses->add(this);
    _klass_dict = NULL;
    _name = NULL;
    _super = NULL;
    _mro   = NULL;
}

// [memory/heap.cpp]
void Heap::copy_live_objects() {
    ScavengeOopClosure(eden, survivor, metaspace).scavenge();
}

// [memory/oopClosure.hpp] 访问者的接口类
class OopClosure {
public:
    virtual void do_oop(HiObject** obj) = 0;

    virtual void do_array_list(ArrayList<Klass*>** alist) = 0;
    virtual void do_array_list(ArrayList<HiObject*>** alist) = 0;
    virtual void do_array_list(ArrayList<HiString*>** alist) = 0;

    virtual void do_map(Map<HiObject*, HiObject*>** amap) = 0;
    virtual void do_raw_mem(char** mem, int length) = 0;
    virtual void do_klass(Klass** k) = 0;
};
// 访问者的具体实现类，针对不同的被访问者提供了具体的访问方法。
class ScavengeOopClosure : public OopClosure { 
private:
    Space* _from;
    Space* _to;
    Space* _meta;

    Stack<HiObject*>* _oop_stack;

    HiObject* copy_and_push(HiObject* obj);

public:
    ScavengeOopClosure(Space* from, Space* to, Space* meta);
    virtual ~ScavengeOopClosure();

    virtual void do_oop(HiObject** oop);

    virtual void do_array_list(ArrayList<Klass*>** alist);
    virtual void do_array_list(ArrayList<HiObject*>** alist);
    virtual void do_array_list(ArrayList<HiString*>** alist);

    template <typename T>
    void do_array_list_nv(ArrayList<T>** alist);

    virtual void do_map(Map<HiObject*, HiObject*>** amap);
    virtual void do_raw_mem(char** mem, int length);
    // CAUTION : we do not move Klass, because they locate at MetaSpace.
    virtual void do_klass(Klass** k);

    void scavenge();
    void process_roots();

    void ScavengeOopClosure::scavenge() {
        // step 1, mark roots
        process_roots();

        // step2, process all objects;
        while (!_oop_stack->empty()) {
            _oop_stack->pop()->oops_do(this);
        }
    }
    // 有哪些引用是 roots 里的呢？Universe 中的 HiTrue、HiFalse 等全局对象指针肯定属于 roots，同理，StringTable 中定义的字符串也可以看做是全局对象，它们也是 roots 集合中的。最重要根引用位于程序栈上，也就是 Interpreter 中使用的 Frame 对象，其中记录的局部变量表、全局变量表、操作数栈等，都有可能是一个普通的 HiObject 对象的引用，这些都属于 roots 集合。
    void ScavengeOopClosure::process_roots() { 
        Universe::oops_do(this); 
        Interpreter::get_instance()->oops_do(this); 
        StringTable::get_instance()->oops_do(this);
    }
};
void Interpreter::oops_do(OopClosure* f) {
    f->do_oop((HiObject**)&_builtins);
    f->do_oop((HiObject**)&_ret_value);

    if (_frame)
        _frame->oops_do(f);
}

void HiObject::oops_do(OopClosure* closure) {
    // object does not know who to visit, klass knows
    closure->do_oop((HiObject**)&_obj_dict);
    klass()->oops_do(closure, this);
}
class HiString : public HiObject {
private:
    char* _value;
    int   _length;

public:
    ...
    char** value_address()  { return &_value; }
};

void StringKlass::oops_do(OopClosure* closure, HiObject* obj) {
    HiString* str_obj = obj->as<HiString>();
    // do_raw_mem在 to 空间中分配一块内存，然后把 from 空间中的内容复制到 to 空间中。再修改引用的内容，让它指向 to 空间中的地址。
    closure->do_raw_mem(str_obj->value_address(), str_obj->length());
}

void Interpreter::eval_frame() {
    ...
    while (_frame->has_more_codes()) {
      unsigned char op_code = _frame->get_op_code();
        ...
        switch (op_code) {
        ...
            case ByteCode::IMPORT_NAME:
                v = _frame->names()->get(op_arg);
                w = _modules->get(v);
                if (w != Universe::HiNone) {
                    PUSH(w);
                    break;
                }
                w = ModuleObject::import_module(v);
                _modules->put(v, w);
                PUSH(w);
                break;
        ...
        }
    }
}

class GeneratorKlass : public Klass {
private:
    static GeneratorKlass* instance;
    GeneratorKlass();

public:
    static GeneratorKlass* get_instance();

    virtual HiObject* next(HiObject* obj);  // 实现 FOR_ITER 字节码
    virtual HiObject* iter(HiObject* obj);  // 实现 GET_ITER 字节码
};
HiObject* GeneratorKlass::iter(HiObject* obj) { return obj;}    // generator 对象的迭代器就是它自己
HiObject* GeneratorKlass::next(HiObject* obj) { 
    assert(obj->klass() == (Klass*) this); 
    Generator* g = (Generator*) obj; 
    return Interpreter::get_instance()->eval_generator(g);
}

class Generator : public HiObject {
friend class Interpreter;
friend class FrameObject;
friend class GeneratorKlass;

private:
    FrameObject* _frame; // 当迭代结束以后，保存局部变量的值

public:
    Generator(FunctionObject* func, ArrayList<HiObject*>* args, int arg_cnt);

    FrameObject* frame()           { return _frame; }
    void set_frame(FrameObject* x) { _frame = x; }
};
// CALL_FUNCTION 指令中，如果碰到generator，函数对应的FunctionObject 成了Generator._frame 的一部分。
Generator::Generator(FunctionObject* func, ArrayList* args, int arg_cnt) {
     _frame = new FrameObject(func, args, arg_cnt); 
     set_klass(GeneratorKlass::get_instance());
}

HiObject* Interpreter::eval_generator(Generator* g) {
    Handle handle(g);
    enter_frame(g->frame());   // 设置好与 generator 相对应的 frame
    g->frame()->set_entry_frame(true);
    eval_frame();   // 执行里面 CodeObject 中的逻辑

    if (_int_status != IS_YIELD) {
        _int_status = IS_OK;
        leave_frame();
        ((Generator*)handle())->set_frame(NULL);
        return NULL;
    }

    _int_status = IS_OK;
    _frame = _frame->sender();

    return _ret_value;
}