Page 39 - 《软件学报》2024年第6期

沈天琪 等: DDoop: 基于差分式 Datalog 求解的增量指针分析框架 2615

应的字符数组的哈希值加长度作为一个类的标识. 一旦这个标识发生变化, 就说明类中存在改变, 需要进入下一级
摘要. 在第 2 级摘要中, 我们会对这个类在方法级别进行匹配. 我们首先将 SootMethod 对象转化为方法的 IR 表
示, 并计算哈希作为摘要. 在这样的摘要设计下, 如果一个方法的源代码发生了任何有意义的变化, 这种变化都会
反映到字节码层面的摘要上.
我们以图 3 中的一次代码变更为例, 对我们的两级摘要方案的设计进行说明. 以上的代码中, 旧版本包含了
A1, B, C1 这 3 个类, 新版本中则包含了 A1, B, C2 这 3 个类, 同时 A1 类中的方法在此次变更中也产生了变化. 为
了方便叙述, 我们在此处忽略它们依赖的库以及其中没有显式定义的任何其他方法. 在第 1 级摘要中, 我们会使
用 A1.class, B.class, C2.class 这 3 个字节码文件对应的字节码数组的摘要 (hash+长度) 对类进行标识, 于是就可以
识别出不变的类 B, 变化的类 A1, 删除的类 C1, 新增的类 C2. 针对 A1, 它会进入第 2 级摘要, 我们会对其中的方
法 f(), f2(), method() 生成对应的 IR 摘要, 并且和之前旧 A1 类对应摘要进行对比. 我们就可以确定 A1 中新增了
f(), 删除了 f1(), f2() 发生变化以及 method() 保持不变. 对于类的字段信息、修饰符信息, 当类发生变化时, 我们会
默认这些信息发生了改变, 进行增量处理.

1 public class B {}
2 - private class C1 {}
3 + private class C2 {}
4 - private class A1 {
5 - B b;
6 - void f1(){}
7 - void f2(){}
8 + void f(){}
9 + void f2(){this.b =this.b2;}
10 - void method() {}
11 - }
图 3 Java 代码变更示例
做增删改查等这些细节问题. 同时内存数据库在此场景下的性能远高于磁盘数据库. 综合考虑效率和开发效率, 我

2.1.4 增量信息存储与管理
在增量输入事实生成的过程中, 需要记录一些必要的增量信息. 其中最主要的内容包括前文提及的增量单元
的信息以及对应生成的 facts 组. 我们的框架首先基于上一轮增量生成中维护的当前程序“活跃”增量单元对应的
增量信息确定本轮增量生成中哪些增量单元需要重新进行处理. 对于那些本轮不再出现的增量单元, 我们的框架
将会将它们对应的 facts 从缓存中取出标记为删除; 对于本轮新出现或者发生变更的增量单元, 则将维护它们的相
关信息, 并将新的 facts 写入缓存. 通过这样的机制, 缓存系统独立记录了增量前端当前的状态, 提供了下一轮增量
分析所需的必要信息.
为此, 我们需要设计一种缓存方案来维护这些增量信息. 我们考虑了几种常见的缓存方案: 基于文件系统的缓
存、基于磁盘数据库的缓存、基于内存数据库的缓存以及前端程序在内存内直接管理缓存的方案.
从实现方面来看, 数据库方案相对简单, 开发者只需定义数据结构, 而无须关心具体如何安排这些数据, 如何

们最终决定选择使用成熟的内存数据库 Redis 作为我们存储和管理增量信息的方式.
从软件工程方面来看, 在现代软件架构中, 应用通常会在分布式节点上部署, Redis 正适合这样的场景. 在这样
的架构中, 节点间的信息交换需要通过网络栈进行, 频繁的 I/O 操作可能会成为系统中最耗时的部分. 我们通过按
需读写的策略优化了 I/O 粒度和读写频率: 我们的系统会首先基于一份相对较小的摘要信息确定哪些类真正发生
了变化. 对于那些未发生变化的增量单元对应的 facts, 我们完全不会在程序运行过程中读写它们. 通过这种优化,
我们的设计能够在高度分布式的环境中同样有效地降低 I/O 开销, 提高系统性能.