Question

2.1 定义

• 需要首先获得整个程序的类继承关系图
• 通过接收变量的声明类型来解析 Virtual call
  • 接收变量的例子：在 a.foo() 中，a 就是接收变量
• 假设一个接收变量能够指向 A 或 A 的所有子类

2.2 具体过程

下面介绍解析调用的算法。定义 Reslove(cs) 函数为：通过 CHA 算法寻找到某个程序调用点对应的可能的目标函数实体。

• call site(cs) 就是调用语句，m(method) 就是对应的函数签名。
• T 集合中保存找到的结果
• 三个 if 分支分别对应之前提到的 Java 中的三种 call 类型
  • Static call
  • Special call
  • Virtual call

2.2.1 static call

静态方法调用前写的是类名，而非静态方法调用前写的是变量或指针名。静态方法调用不需要依赖实例。因此静态方法调用的分析结果十分简单，很明显调用的就是当前类的方法，所以直接加到集合 T 中。

2.2.2 special call

special call 主要分为三种情况。上图是第一种使用 super 类的调用方法。 foo() 虽然在当前类有定义，但是实际使用的是父类的 foo() ，因此需要使用 Dispatch 函数，其中的 foo() 的签名 m 由编译器返回信息可以知道是 B 的，那么获取 foo() 返回值的 c 也指向 B ，也就相当于在父类中寻找了。

为什么处理 super 调用需要使用 Dispatch 函数？在下图所示情况中没有 Dispatch 函数时无法正确解析 C 类的 super.foo 调用：

而 Private instance method 和 Constructor （一定由类实现或有默认的构造函数）都会在本类的实现中给出，使用 Dispatch 函数能够将这三种情况都包含，简化代码。

2.2.3 virtual call

最后是处理 virtual call，这也是 CHA 区别于其他算法的主要之处。该算法会对此方法做一个 Dispatch(c,m) 并将 c 的所有子集以及子集的子集全都做一次 Dispatch(c', m) 。直观来看，可以分为两步，第一步是对本身做一次 Dispatch，看看当前类中是否有 foo()，没有的话就到父类中递归地找；第二步是在当前类地所有子集中找到所有的 foo()，然后将这些 foo 同第一步找到的 foo 全都加入 T 中。

一个例子：

常用于 IDE 中，给用户提供提示。比如写一小段测试代码，看看 b.foo() 可能会调用哪些函数签名。可以看出 CHA 分析中认为 b.foo() 可能调用 A、C、D 中的 foo() 方法。

2.3 CHA 的特征

1. 只考虑类继承结构，所以 很快
2. 因为忽略了数据流和控制流的信息，所以 不太准确

2.4 调用图构建

分为三步：

1. 从入口方法进入，一般是 main 方法
2. 对于每个可到达的方法 m，通过 CHA 算法找出点调用的方法 m' 的调用位置
3. 对于每个 m (以及新加入的 m' ) 都进行第二步，知道不再有新的方法被发现

构造调用图的算法如下：

• Worklist 记录需要处理的 methods
• Call graph 是需要构建的目标，是 call edges 的集合
• Reachable method (RM) 是已经处理过的目标，在 Worklist 中取新目标时，不需要再次处理已经在 RM 中的目标

一个例子：