AST 转 CFG

以 ArrayList 中 remove(int index) 为例（486行）。

函数源代码如下。 

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
该函数使用实验提供的 cfgparser.jar 得到的结点信息如下。

method[row] node    parent  height  start.x start.y end.x   end.y   content

remove[486] 0       -1      0       496     8       496     26      first-statement@rangeCheck(index);

remove[486] 1       -1      0       505     8       505     35      after-branch@elementData[--size]=null;

remove[486] 2       -1      0       502     8       504     39      if-statement@if (numMoved > 0) System.arraycopy(elementData,index + 1,elementData,index,numMoved);

remove[486] 3       2       1       503     12      504     39      then-body@System.arraycopy(elementData,index + 1,elementData,index,numMoved);

remove[486] 4       -1      0       507     8       507     24      return@return oldValue;

上述节点信息对应的是函数的抽象语法树（AST），可以形象化展示为下图。

其中 node -1 对应的是函数的函数体，其节点编号为 -1。

e3a1fe59624b9943b3215cb8614ee02d

在 AST 中，函数的顺序执行语句的父节点为函数体，也就是 node -1；函数中的 if - condition - then 语句中，then-body 的父节点是 if 语句；对应 for，while等语句你可以输出他们的节点信息尝试一下。

现在需要将上面这个 AST 转化为下面这样的 CFG。

b63c29a48162ebbcf20c60726e9848da

转化的思路如下：

  1. 首先找到所有父节点为 -1 的节点，并依据他们的代码行数（start.x）构建顺序执行的流程图，可以得到 0 ->2 -> 1 -> 4，并得到 AST 中高度为 1 的节点列表A {0, 1, 2, 4}
  2. 遍历其他的节点，找到父节点在节点列表 A 中的节点，得到 AST 中高度为 2 的节点列表 B {3}。对于每个节点，例如节点 3，将其插入到父节点（2）之后，父节点后的顺序执行节点（1）之前

对于函数中的 for, while 等语句，可以采用类似方法来构建流程图。

同时也可以利用节点的 content信息，例如content信息为then-body的节点会与if-statement和after-branch节点各有一条边。