面向对象机制

传统的方案

decaf的面向对象机制是传统的虚表机制：每个对象中都隐藏了一个指向虚表的指针。调用虚函数的时候，首先从对象指针指向的内存中读出虚表指针，然后再从虚表指针指向的内存中，在一个编译期就可以确定的偏移量处读出函数指针，最后将对象指针作为函数的隐藏的this参数调用函数。

在我们的实现中，虚表中不只存放了函数指针，还存放了一些额外的用于描述类型的信息。例如为了支持instanceof的动态类型判断，需要不断沿着继承链向上查找，因此可以想象虚表中需要存储关于本类的父类的信息；为了能够在类型强制转化失败时输出类型的名字，可以想象虚表中需要存放类型名字的字符串。

具体来说，虚表的第0个slot存放指向父类的虚表的指针(如果没有父类则为空指针)，第1个slot存放指向类名字符串的指针，后面的slots都存放函数指针。函数指针的存放顺序是：

1. 辈分越高的类的函数越靠前，同一个类中按照函数的声明顺序排序

2. 子类如果复写了祖先的虚函数，那么使用祖先的函数指针用的slot来存放它的函数指针，否则就依次跟在后面。

而对象的内存布局则是，第0个slot存放指向虚表的指针，后面的slots存放成员变量。辈分越高的类的成员变量排在越前面，同一个类中按照变量的声明顺序排序。

一个简单的例子如下：

class A { 
  int x; 
  int y; 
  void f1() { } 
  void f2() { } 
} 

class B extends A { 
  int z; 
  void f1() { }
  void f3() { }
}

对应的对象和虚表的结构为：

obj

这种基于嵌在对象内部的虚表指针来实现面向对象机制的方案大家在之前的oop课上都应该已经比较熟悉了，它的优势在于保持了指针的大小不变，传参等用途的时候不需要修改现有方案，可以与没有内建面向对象机制的c语言等代码兼容；它的劣势在于限定死了虚表的组织结构：每个子类中，虚表内函数指针的排列位置必须与父类兼容，这样把它的指针传给接受父类的指针的函数时，才能够使用同样的偏移量来访问。这样的限制使得多继承等概念很难表达，要么就是像java一样直接不支持，要么就是像c++一样带来了更大的麻烦。

后面应该都可以不看了，和做实验关系不大

胖指针方案

还有另一种基于胖指针的面向对象机制，比较新的语言如rust和go都采用了这样的机制来实现动态分发(不过它们并不算是面向对象语言，只是像面向对象语言一样支持动态分发)。它的实现方法是将"对象指针"表示成两个指针，一个指向对象的数据，一个指向虚表。例如rust中的trait object机制的实现机制大致如下trait-objects：

pub struct TraitObject {
    pub data: *mut (),
    pub vtable: *mut (),
}

对于一个需要实现动态分发的trait，为它生成一个虚表类型：

struct FooVtable {
    destructor: fn(*mut ()),
    size: usize,
    align: usize,
    // methods ...
}

当需要将一个普通的struct传递给一个接受trait object的函数时，编译器插入一些代码把它的虚表指针一起传进去。一个显然的好处在于如果一个实现了某trait的struct从来没有当做trait object来使用，那么就不必浪费空间来存储虚表指针。另外，在这种机制下实现"多继承"也是很容易的：对于一个dyn Foo + Bar，只需要把Foo和Bar的函数一起放进虚表即可。当然，这并非c++意义上的多继承，因为trait只描述对象的接口，不包含任何数据。

go的interface的实现原理也是类似的，可参考golang-interface-implementation。