引言

在本文中，我们将通过具体的代码实现，探讨如何使用 Tree-Sitter 解析 PHP 代码的 抽象语法树（AST），并基于 AST 构建 控制流图（CFG）。

如何从 AST 构建 CFG？

在深入代码细节之前，我们首先需要理解如何从 AST 构建 CFG。AST 表示了代码的语法结构，但它更侧重于代码的层次结构和语法成分，而非执行流程。而 CFG 则专注于描述程序的控制流路径，即代码执行的顺序和分支。

从 AST 构建 CFG 的基本步骤和原理

从 AST 构建 CFG 的过程，本质上是一个 AST 节点的遍历和转换过程。我们需要遍历 AST，识别出对控制流有影响的语句节点，并将它们转换为 CFG 中的节点，并根据语句的控制流语义添加 CFG 边。以下是构建过程中的一些关键步骤和原理：

1. AST 节点遍历： 通常采用深度优先遍历的方式遍历 AST。这样可以按照代码的逻辑顺序访问到各个语句节点。

2. 识别控制流语句： 在遍历过程中，我们需要识别出 AST 中代表控制流语句的节点类型：
1. 条件和分支语句:
• if_statement - 条件分支
• switch_statement - 多路分支
2. 循环语句:
• while_statement - while循环
• do_statement - do-while循环
• for_statement - for循环
• foreach_statement - foreach循环
3. 跳转语句:
• goto_statement - 无条件跳转
• continue_statement - 继续下一次循环
• break_statement - 跳出循环
• return_statement - 函数返回
4. 异常处理:
• try_statement - 异常捕获和处理
5. 程序终止:
• exit_statement - 程序退出
6. 复合语句:
• compound_statement - 包含多条语句的代码块，会影响控制流的嵌套结构

3. 创建 CFG 节点： 对于每个识别出的控制流语句节点，我们需要在 CFG 中创建一个对应的CFG 节点。这个 CFG 节点通常会包含以下信息：
• 节点 ID： 用于唯一标识 CFG 节点。通常可以使用 AST 节点的 ID 或生成新的唯一 ID。
• 节点类型： 表示 CFG 节点对应的语句类型，例如 if_statement 等。
• 节点文本： 可选地包含节点对应的源代码文本。
• 其他属性： 例如是否是分支节点等，可以根据具体需求添加。

4. 🌟添加 CFG 边🌟： 根据不同语句的控制流语义，在 CFG 节点之间添加有向边，表示控制流的转移方向。添加边的关键在于理解每种语句的执行逻辑：

代码概览：基于 Tree-sitter 的 PHP CFG 构建器

代码的实现主要包括两部分，AST 的构建、遍历，CFG 的构建。所以代码可以组织为两个模块：

• ast_parser: 负责使用 Tree-sitter 解析 PHP 代码，并提供查询 AST 节点的功能。它能够识别 PHP 代码中的函数定义、各种语句类型，并提取节点的关键属性。

• cfg_builder : 专注于 CFG 的构建，它递归遍历 AST，根据不同的语句类型生成 CFG 的节点和边。

构建 AST

在 Python 中实现 AST 的构建还是比较简单的，直接使用 tree_sitter_language_pack 库就行：

这样，我们就得到了输入 code 的完整 AST。在构建 CFG 时，实现的是基于 function 粒度的，所以我们还需要把输入代码中所有的 function 提取出来，可以定义一个辅助函数，用于从 AST 中提取指定类型的 node：

有了 query 函数，我们就可以传入 root_node 递归获取所有的 function node：

准备好这些基本输入之后，就可以着手构建 CFG 了。

构建 CFG

在整个构建 CFG 的过程中，我们需要维护每个代码块或语句的入口节点 (in_nodes) 和 出口节点 (out_nodes)。

• 入口节点 (in_nodes)： 表示控制流进入当前代码块或语句的入口边集合。

• 出口节点 (out_nodes)： 表示控制流从当前代码块或语句出去的出口边集合。

通过 in_nodes和 out_nodes的传递和连接，可以将各个语句的 CFG 片段组合成完整的函数或程序的 CFG。下面是需要使用的数据结构：

1. NodeInfo: dict[str, str | int | bool | list[tuple[int, int]]]

NodeInfo 类型用于存储 CFG 中每个节点的详细信息。它是一个字典，包含以下键值对：

• "id": str - 节点的唯一标识符。通常基于 Tree-sitter AST 节点的 ID 生成，确保每个 CFG 节点都有唯一的身份，方便在图中引用和查找。
• "type": str - 节点代表的 AST 节点类型。例如，"if_statement"、"function_definition"、"expression_statement" 等。这有助于理解 CFG 节点在代码中的语义角色。
• "start": tuple[int, int] - 节点代码在源文件中的起始位置，表示为 (行号, 列号) 的元组。方便将 CFG 节点映射回源代码，进行代码定位和分析。
• "end": tuple[int, int] - 节点代码在源文件中的结束位置，同样表示为 (行号, 列号) 的元组。与 "start" 配合使用，可以精确定位节点对应的代码范围。
• "is_branch": bool - 标识节点是否为分支节点。例如，if 语句、while 循环等条件判断语句对应的节点会被标记为 True，表示控制流在此处会发生分支。
• "text": str - 节点对应的源代码文本。存储了节点代表的代码片段的文本内容，使 CFG 节点更易于理解和调试。

示例： 一个 if_statement 节点的 NodeInfo 可能如下所示：

2. Nodes: list[tuple[NodeInfo, str]]

Nodes 类型用于表示 一组 CFG 节点及其相关的边标签。它是一个列表，列表中的每个元素都是一个元组。

• tuple[NodeInfo, str] - 表示一个 CFG 节点以及与其关联的边标签。
• 第一个元素 NodeInfo: CFG 节点的 NodeInfo 对象，包含了节点的详细信息。
• 第二个元素 str: 边标签。在 create_cfg 函数中，Nodes 通常作为 in_nodes 参数传递，表示 控制流进入当前节点的入口来源。边标签用于区分不同的入口路径。

示例： create_cfg 函数的 in_nodes 参数可能是一个 Nodes 列表，如下所示：

3. Edges: list[tuple[str, str]]

Edges 类型用于表示 一组 CFG 边。它是一个列表，列表中的每个元素都是一个元组，代表一条边。

• tuple[str, str] - 表示一条 CFG 边，元组包含两个字符串：
• 第一个 str: parent_id (父节点 ID) - 边的起始节点的 ID。表示控制流从哪个节点流出。
• 第二个 str: label (边标签) - 边的标签，用于区分不同类型的控制流转移。例如：
• "" (空字符串): 表示顺序执行的边，没有特殊条件。
• "True": 表示条件为真时执行的分支。例如，if 语句的 True 分支边。
• "False": 表示条件为假时执行的分支。例如，if 语句的 False 分支边。
• "Exception": 表示异常处理的边。例如，try 块到 catch 块的异常边。
• "case <value>" 或 "default": 用于 switch 语句的 case 分支边，标签为对应的 case 值或 "default"。

示例： 一个节点的 Edges 列表可能如下所示，表示该节点有两条入边：

4. CFG_GRAPH: list[tuple[NodeInfo, Edges]]

CFG_GRAPH 类型用于表示 完整的控制流图 (CFG)。它是一个列表，列表中的每个元素都是一个元组。

• tuple[NodeInfo, Edges] - 表示 CFG 中的一个节点及其所有入边。
• 第一个元素 NodeInfo: CFG 节点的 NodeInfo 对象，包含了节点的详细信息。
• 第二个元素 Edges: Edges 对象，即该节点的所有入边列表。

示例： 一个 CFG_GRAPH 可能如下所示，表示一个包含三个节点的 CFG：

其中 node_info_A、node_info_B、node_info_C 分别是节点 A、B、C 的 NodeInfo 对象，"A_ID" 和 "B_ID" 分别是节点 A 和 B 的 ID。

之后我们需要实现一个函数，它接收一个 Tree-sitter 节点 node 和一个 in_nodes 列表作为输入，输出构建的 CFG_GRAPH 以及当前节点处理后的 out_nodes。函数内部需要识别和处理不同的 statement，创建相应的 CFG 节点和相互连接边。所以，解析来开始最重要的部分~

函数定义 (function_definition)

• 创建函数节点：首先为函数定义创建一个 CFG 节点，并将其添加到 CFG 列表中。函数的入口节点没有入边，因此入边列表为空 []。

• 递归处理函数体：获取函数体的 body 节点，并递归调用处理函数体内的语句。函数体的入口边指向函数定义的节点。

• 返回结果：函数定义的 CFG 片段由函数节点和函数体 CFG 片段组成。函数定义本身没有出口节点，因此返回空的 out_nodes 列表 []。

复合语句块 (compound_statement)

• 顺序处理子语句：compound_statement 代表代码块( 被{ 和 } 包裹的)，例如函数体、循环体、if 语句块等。它包含一系列顺序执行的子语句。

• 迭代处理子节点：遍历 compound_statement 的子节点，跳过花括号 {}。

• 递归调用：对每个子节点递归调用 handle_node 处理。

• 关键：控制流传递 in_nodes 会在循环中被更新为上一个子语句的 out_nodes。这意味着前一个语句的出口节点会成为下一个语句的入口节点，保证了代码块内语句的顺序执行。

compound_statement 体现了代码的顺序执行流程。通过迭代处理子语句并传递 in_nodes 和 out_nodes，可以正确地将代码块内的语句连接成线性的控制流路径。

if 语句 (if_statement)

• 创建 if 条件节点：为 if 语句创建一个 CFG 节点，表示条件判断。其入边来自 in_nodes。

• 处理 if 主体 (True 分支)：递归调用 handle_node 处理 if 语句的 body (即 if 条件成立时执行的代码块)。body 的入口边指向 if 条件节点，并标记为 "True" 分支。

• 处理 else 或 else if 分支 (False 分支)：
• 如果存在 alternative (即 else 或 else if 语句)，则递归调用 handle_node 处理 alternative。alternative 的入口边也指向 if 条件节点，并标记为 "False" 分支。
• 如果只有 if 没有 else，则 if 条件不成立时的控制流直接跳过 if 主体，到达 if 语句之后的代码。

• 合并出口节点：if 语句的出口节点是 if 主体 (True 分支) 的出口节点和 else/else if 分支 (False 分支，如果存在) 的出口节点的并集。如果只有 if，则出口节点是 if 主体的出口节点和 if 条件节点本身的 "False" 分支出口 (代表条件不成立时直接跳过 if 块)。

else_if_clause 和 else_clause

else_if_clause 和 else_clause 的 body 实际上是一个 if_statement 节点，因此，直接递归调用自身处理它们的 body 节点，并将 in_nodes 原样传递下去。

循环语句 (while_statement, for_statement, foreach_statement)

• 创建循环条件/迭代节点：为循环语句 (例如 while, for, foreach) 创建一个 CFG 节点，表示循环的条件判断或迭代过程。其入边来自 in_nodes。

• 处理循环体 (True 分支)：递归处理循环的 body (循环体代码块)。body 的入口边指向循环条件/迭代节点，并标记为 "True" 分支 (表示条件成立，进入循环体)。

• 循环边： 将循环体 body 的出口节点连接回循环条件/迭代节点，形成循环的回路。这表示循环体执行完毕后，控制流会再次回到循环条件判断处。

• 处理 break 语句：break 语句会跳出循环。找到循环体内的所有 break 节点，并将它们作为循环语句的出口节点之一。

• 处理 continue 语句：continue 语句会跳过当前循环迭代的剩余部分，直接进入下一次迭代。找到循环体内的所有 continue 节点，并将它们连接到循环条件/迭代节点，表示控制流回到循环开始处。

• 循环出口节点：循环语句的出口节点包括：
• False 分支： 当循环条件不成立时，控制流会跳出循环。用从循环条件/迭代节点出发的 "False" 边表示。
• break 语句出口： 循环体内的 break 语句也会导致跳出循环，break 语句本身也作为循环的出口节点。

do_statement (do-while 循环)

do_statement (do-while 循环) 与 while_statement 等循环类似，但它是先执行循环体，再判断循环条件。因此，处理逻辑也类似，但入口边和循环边的连接方式有所不同：

• 循环体入口：do_statement 的入口边实际上指向的是循环体的第一条语句 (或循环条件节点，如果循环体为空)。

• 循环边：循环体的出口节点连接到 do_statement 的条件节点，形成循环回路。

• 其他处理 (循环条件节点创建、break/continue 处理、出口节点) 与 while_statement 等循环类似。可能还需要注意的是 continue 节点执行之后，跳转到的是 do while 的条件节点

switch_statement (switch 语句)

switch_statement 根据条件表达式的值，跳转到不同的 case 分支执行。处理逻辑如下：

• 创建 switch 节点：为 switch 语句创建 CFG 节点。

• 遍历 case 分支：迭代处理 switch 语句 body 中的每个 case 和 default 分支。
• case 节点：为每个 case 分支创建一个 CFG 节点。case 节点的入边来自 switch 节点胡或上一个 case 语句的 out_nodes（如果没有 break），将 switch 语句到 case 语句的边标记为 case_name (或 "default" 对于 default 分支)。
• case 语句块处理：递归调用处理每个 case 分支的代码块。case 语句块的入口边指向 case 节点。

• break 语句处理：case 分支通常以 break 语句结束，跳出 switch 语句。找到每个 case 分支中的 break 节点，并将它们作为 switch 语句的出口节点之一。

• switch 语句出口节点：switch 语句的出口节点包括所有 case 分支中的 break 语句的出口节点，以及最后一个 case 或者 default 的出口节点。

1. for case_node in body.children[1:-1] 为什么要指定 body.children 范围为 [1:-1]？

body 是 switch_statement 的 body 部分，通常是一个 {} 包裹的 case 语句块。例如：

在 AST 解析树中，body.children 可能包含：

• children[0] 是 {（大括号的起始）。

• children[-1] 是 }（大括号的结束）。

• children[1:-1] 才是真正的 case 语句块。

因此，body.children[1:-1] 过滤掉了 {}，只遍历 case 和 default 语句。

2. index 和 case_name 的作用是什么？

• case_name：用于存储 case 语句的匹配值。例如：

这里 case_name = "1"，用于标记 switch 语句到 case 语句的边。

• index：用于确定 case 语句的第一条执行语句的索引。例如：

在 AST 解析树中：

• case 关键字是 children[0]。
• 1（匹配值）是 children[1]。
• :（冒号）是 children[2]。
• doSomething(); 是 children[3]（第一条执行语句）。

因此，index = 3，表示 case 语句的第一条执行语句的索引。

对于 default 语句：

• default 关键字是 children[0]。
• :（冒号）是 children[1]。
• handleDefault(); 是 children[2]（第一条执行语句）。

因此，index = 2。

这就是为什么 case 语句的 index = 3，而 default 语句的 index = 2。

总结

这样可以确保 case 和 default 语句的第一条执行语句被正确解析，并加入 CFG 结构。

goto_statement (goto 语句)

goto_statement 用于无条件跳转到代码中标记的标签位置 (labeled_statement)。处理逻辑如下：

• 创建 goto 节点：为 goto 语句创建 CFG 节点。

• 连接到标签位置：查找 goto 语句跳转的目标标签 (labeled_statement)。如果找到标签，则创建从 goto 节点到标签节点的边。

return_statement, break_statement, continue_statement, exit_statement

这些语句都代表了程序控制流的终止或转移：

• return_statement: 函数返回。

• break_statement: 跳出循环或 switch 语句。

• continue_statement: 跳过当前循环迭代的剩余部分。

• exit_statement: 程序退出。

对于这些语句，处理逻辑相对简单：

• 创建语句节点：为每种语句创建 CFG 节点。

• 出口节点为空：这些语句通常是控制流的终点 (例如 return 和 exit) 或转移点 (例如 break 和 continue)，它们本身没有后继节点 (在当前函数或代码块的 CFG 中)。因此，它们的 out_nodes 返回为空 []。控制流的转移目标 (例如 break 跳出的循环的后继节点) 在处理包含这些语句的结构 (例如循环、switch、函数) 时已经确定好了。

普通语句

对于其他没有特殊控制流含义的普通语句 (例如赋值语句、函数调用语句等)，处理逻辑如下：

• 创建语句节点：为普通语句创建 CFG 节点。

• 顺序连接：将当前语句节点连接到 in_nodes，形成顺序执行的控制流路径。

• 出口节点：当前语句节点本身作为出口节点，传递给下一个语句作为 in_nodes。

待处理 ⚠️

对于影响程序控制流执行的，还有 try catch 、 throw statement 等， 目前对于 try catch 语句的处理还是有些问题，因为 try 的主体里可能有 throw 语句，这样会立刻跳转到匹配的 catch 上，所以有个匹配连接 exception 的问题。

总结

总而言之，CFG 构建的核心思想是：

1. 递归遍历 AST: 从根节点开始，递归地处理 AST 的每个节点。

2. 语句类型判断: 根据节点的类型 (node.type)，判断当前节点代表的语句类型。

3. 分类型处理: 针对不同的语句类型，采用不同的逻辑来构建 CFG 节点和边，以准确地表示该语句的控制流语义。

4. 控制流传递: 通过 in_nodes 和 out_nodes 参数，在递归调用之间传递控制流信息，保证 CFG 的连贯性和正确性。

5. 特殊语句处理: 重点处理具有特殊控制流含义的语句，例如条件分支 (if, switch)、循环 (while, for, do)、跳转 (goto, break, continue, return, throw)、异常处理 (try-catch-finally) 等。

感谢

（就是项目的代码组织不是特别好，一个文件中的代码太长了 🫢，所以感谢 cursor 帮我梳理代码😂，后面写 PHP 的版本时，重构为模块化的了）