Flow Chart

这是一个附加功能，它将为每个函数生成流程图，以 .dot 文件格式输出，.dot 文件可通过

查看。

依赖

petgraph

实现

流程图的生成包含两个步骤：

由 AST 生成 图 数据结构
根据 图 生成 .dot文件

图的生成

我们以函数为单位生成 graph ，而 AST 根节点为 ProgramNode，因此我们需要遍历其 fntypes ，逐个生成 graph 最终得到一个 Vec ：

impl ProgramNode {
   pub fn create_graphs(&self) -> Vec<GraphWrapper> {
       let mut graphs = vec![];
       for func in &self.fntypes {
           if let Some(body) = func.body.clone() {
               let graph = from_ast(Box::new(NodeEnum::Sts(body)));
               graphs.push(GraphWrapper {
                   name: func
                       .id
                       .name
                       .clone()
                       .replace(|c: char| !c.is_ascii_alphanumeric(), "_"),
                   graph,
               });
           }
       }
       graphs
   }
}

接下来实现 from_ast() 函数，它接收一个 NodeEnum（这是一个 Statements 节点），返回一个完整的 Graph，具体分为两步：

初步构建图(build_graph())
去除不必要节点(0入度节点,虚节点,空节点))

pub fn from_ast(ast: Box<NodeEnum>) -> Graph {
   let mut ctx = GraphContext::new();
   build_graph(ast, &mut ctx);
   // 删除入度为 0 的节点
   while remove_zero_in_degree_nodes(&mut ctx.graph) {}
   // 删除虚节点
   while remove_single_node(&mut ctx.graph, |_, t| *t == GraphNodeType::Dummy) {}
   // 删除空节点
   let remove_empty_nodes: fn(NodeIndex, &GraphNodeType) -> bool = |_, t| match t {
       GraphNodeType::Node(t) => t.is_empty() || t.trim() == ";",
       _ => false,
   };
   while remove_single_node(&mut ctx.graph, remove_empty_nodes) {}
   ctx.graph
}

主要介绍构建图的环节。

定义图的 节点 与 边 ：

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum GraphNodeType {
   Dummy,               // 虚节点
   Begin,               // 起点
   End,                 // 终点
   Node(String),        // 普通节点
   Err(String, String), // 错误节点
   Choice(String),      // 选择节点
}

#[derive(Debug, Clone, Copy)]
pub enum EdgeType {
   Normal,
   Branch(bool), // 分支，带有 Y/N 等标签
}

pub type Graph = StableDiGraph<GraphNodeType, EdgeType>;

build_graph()函数以 Statement 为单位，针对不同节点构建不同的图结构，为了方便的连接节点，我们定义了 GraphContext 用于存储上下文信息:

struct GraphContext {
   pub graph: Graph,
   pub break_target: NodeIndex,
   pub continue_target: NodeIndex,
   #[allow(dead_code)]
   pub global_begin: NodeIndex, // 全图起点
   pub global_end: NodeIndex,   // 全图终点
   pub local_source: NodeIndex, // 局部起点
   pub local_sink: NodeIndex,   // 局部终点
}

每次调用 build_graph() 前，我们需要为构建部分提供两个 锚点(local_source, local_sink) ，第一次调用时，锚点 即为起点和终点，以后每次调用前，均需构建两个虚节点，作为锚点(虚节点之后将被去掉)。

对于不涉及分支、循环、跳转的简单语句，图结构较为简单：

local_source -> current -> local_sink

local_source ------------> local_sink // 注释

local_source ---> ERR ---> local_sink // 错误

分支及循环语句则较为复杂(以 IF语句 为例)：

IF:                /--Y--> sub_source -----> [...body...] ------> sub_sink ->-\
                  /                                                            \
local_source -> cond                                                        local_sink
                  \                                                           /
                   \--N--> sub_source1 -> Option<[...els...]> -> sub_sink ->-/

if.body 及 if.els 部分可以通过递归调用 build_graph() 构建，但是需要先生成两个虚节点，并暂时赋给 ctx，构建完毕后， ctx 的 local_source/sink需要还原

对于语句块，对每个语句调用 build_graph() ，每次将 sub_source 更改为 sub_sink ，sub_sink 则重新创建：

               for i in &v.statements {
                   context.local_source = sub_source;
                   context.local_sink = sub_sink;
                   build_graph(i.clone(), context);
                   if i != v.statements.last().unwrap() {
                       sub_source = sub_sink;
                       sub_sink = context.graph.add_node(GraphNodeType::Dummy);
                   }
               }

.dot 文件生成

我们只需按dot语法格式生成图的点/边的信息即可。下面是一个简单的dot文件：

digraph _pointer_struct__name_params {
    D0 [shape=box, style=rounded, label="begin", fontname=""];
    {rank = sink; D1 [shape=box, style=rounded, label="end", fontname=""];}
    D4 [shape=box, label="return\l", fontname=""];
    D4 -> D1;
    D0 -> D4;
}

可以在Graphviz Online查看对应流程图。

Pivot Lang

Flow Chart

依赖

实现

图的生成

.dot 文件生成