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

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

所不同, DDlog 中要求规则子句中对变量的使用不能出现在能确定它们的规则子句之前, 而 Soufflé 对此限制更宽
松, 允许此类规则的存在. 考虑如下以 Soufflé 语法写成的示例规则.
node_ord(?a, ?a_ord) :- ?a_ord = ord(?a), graph.edge(_, ?a).
这条示例规则表示 node_ord 关系需要增加来自于 graph.edge 关系中的元素?a 在被 ord 函数处理后的返回值.
其中 ord 函数可以对某一个确定性的字符串输入?a 返回一个运行中的唯一对应值. 对于 DDlog 的编译器, 在处理
规则的第 1 条子句?a_ord = ord(?a) 时, 它没能找到?a 的定义, 因而编译失败.
为了解决这个问题, 我们采用了规则重写方案. 通过分析规则子句中的 def-use 关系, 我们可以产生规则子句
的一个重排版本. 新的规则子句确保了每个变量在被使用之前都已经被确定. 重排后的规则如下.
node_ord(?a, ?a_ord) :- graph.edge(_, ?a), ?a_ord = ord(?a).

2.2.4 模块系统重写
组件系统是 Soufflé 在 Datalog 上为增强模块化而带来的一个语法糖, 而 DDlog 目前尚未支持模块化. 但在编
译过程中, Soufflé 编译器会在编译期首先进行解糖: 将模块化的规则进行“展开”. 因此, 我们的重写器针对模块化
的重写策略与之类似, 具体描述于算法 1 中.
17. if v is a declaration in a component body then
算法 1. Soufflé 到 DDlog 的规则重写算法.
输入: A Soufflé program Ps;
输出: A DDlog program P D .
1. for each node v in AST(Ps) do
2. if v is a component declaration then
3. o c = new Component // 包含组件名称、类型参数列表、继承关系及组件体
4. for each node u in AST(o c ) do
5. if u is an .override directive then
6. Mark relations that o c overrides // 被标记的关系不会输出到 P D 中
7. end if
8. end for
9. end if
10. end for
11. for each node v in AST(Ps) do
12. if v is a component instantiation of o c then
13. o c .instantiate() // 调用 Component 对象的 initantiate 方法
// 将组件的类型参数实例化为具体类型
// 实例化所有父组件并合并到当前组件实例中
14. end if
15. end for
16. for each node v in AST(Ps) do

18. v D ＝rewrite(v) // 将声明以 DDlog 语法重写
19. add v D to P D // 将重写后的声明添加到目标 DDlog 程序中

20. end if
21. end for

22. return P D