在Rust中基于SQL文件依赖构建petgraph DAG的遍历疑问

问题背景 #

我正尝试在Rust中从SQL文件构建petgraph DAG，但在处理传递依赖的构建时遇到了困难。

获取第一个节点的父节点相对简单，示例代码如下：

use sqlparser::{dialect::SnowflakeDialect, parser::Parser, ast::visit_relations};
use core::ops::ControlFlow;

fn main() {
    let query = "select 1 from schema.tab1 join schema.tab2";
    let _qry_tab_2 = "select 1 from schema.tab4";

    let dialect = SnowflakeDialect {};
    let ast = Parser::parse_sql(&dialect, query).unwrap();

    let mut visited = vec![];
    visit_relations(&ast, |relation| {
        visited.push(format!("{relation}"));
        ControlFlow::<()>::Continue(())
    });

    assert_eq!("schema.tab1", visited[0])
}

但后续节点及其依赖的遍历我不知该如何推进，比如需要遍历schema.tab1的依赖，再遍历这些依赖的依赖。

我期望得到如下形式的输出：

{schema.tab1: [schema.tab2, schema.tab3],
 schema.tab2: [schema.tab4],
 schema.tab3: [schema.tab4],
 schema.tab4: []
}

这样就能基于结果轻松构建如下结构的图：

--(node1) 
          /
(node0) --
          \
           --(node2)--(node3)

解决方案 #

在Rust中处理这类传递依赖遍历+DAG构建的问题，惯用思路是递归遍历+缓存已处理节点，避免重复计算，再配合petgraph的API完成图的构建。以下是具体步骤和示例代码：

核心处理思路 #

• 维护缓存（比如HashMap<String, Vec<String>>），记录已解析表的依赖关系，避免重复解析同一表的SQL
• 编写递归函数：输入表名，解析对应SQL语句提取依赖表，再递归处理每个依赖表
• 最后将缓存的依赖关系转换为petgraph的DAG结构

具体实现示例 #

首先，假设你有一个根据表名获取对应SQL语句的函数（可从文件读取或内存映射）：

// 模拟根据表名获取对应的SQL查询
fn get_sql_for_table(table_name: &str) -> String {
    match table_name {
        "schema.tab1" => "select 1 from schema.tab2 join schema.tab3".to_string(),
        "schema.tab2" => "select 1 from schema.tab4".to_string(),
        "schema.tab3" => "select 1 from schema.tab4".to_string(),
        "schema.tab4" => "select 1 from dual".to_string(), // 无依赖
        _ => panic!("Unknown table: {}", table_name),
    }
}

然后实现递归解析依赖的函数：

use sqlparser::{dialect::SnowflakeDialect, parser::Parser, ast::visit_relations};
use core::ops::ControlFlow;
use std::collections::{HashMap, HashSet};

// 递归解析表的依赖关系，返回直接依赖列表
fn resolve_dependencies(table_name: &str, cache: &mut HashMap<String, Vec<String>>) -> Vec<String> {
    // 优先查缓存，避免重复解析
    if let Some(deps) = cache.get(table_name) {
        return deps.clone();
    }

    let sql = get_sql_for_table(table_name);
    let dialect = SnowflakeDialect {};
    let ast = Parser::parse_sql(&dialect, &sql).unwrap();

    let mut deps = HashSet::new();
    // 提取当前SQL中的所有依赖表
    visit_relations(&ast, |relation| {
        let rel_str = format!("{relation}");
        // 排除自身引用（如果存在）
        if rel_str != table_name {
            deps.insert(rel_str);
        }
        ControlFlow::Continue(())
    });

    // 递归处理每个依赖表，确保所有依赖都被解析
    let mut resolved_deps = Vec::from_iter(deps);
    for dep in &resolved_deps {
        resolve_dependencies(dep, cache);
    }

    // 存入缓存
    cache.insert(table_name.to_string(), resolved_deps.clone());
    resolved_deps
}

最后构建petgraph DAG：

use petgraph::graph::{Graph, NodeIndex};
use petgraph::Directed;

fn build_dag(root_table: &str) -> Graph<String, (), Directed> {
    let mut cache = HashMap::new();
    // 先解析根表及所有关联依赖
    resolve_dependencies(root_table, &mut cache);

    let mut graph = Graph::new();
    // 先创建所有节点，记录节点索引映射
    let mut node_indices = HashMap::new();
    for table in cache.keys() {
        let idx = graph.add_node(table.clone());
        node_indices.insert(table.clone(), idx);
    }

    // 添加边：每个表指向它的直接依赖
    for (table, deps) in cache {
        let from_idx = node_indices[&table];
        for dep in deps {
            let to_idx = node_indices[&dep];
            graph.add_edge(from_idx, to_idx, ());
        }
    }

    graph
}

fn main() {
    let dag = build_dag("schema.tab1");
    // 打印图结构验证（需要依赖petgraph的dot特性）
    // petgraph::dot::print_dot(&dag);
}

关键注意事项 #

• 缓存机制：必须使用缓存避免重复解析，尤其是处理大量表时能大幅提升效率
• 循环依赖检测：如果SQL中可能出现循环引用，可在递归函数中加入visited集合，记录当前正在解析的表，遇到重复则抛出错误或跳过（DAG不允许循环）
• 直接/传递依赖：构建DAG时通常只需要记录直接依赖，图的遍历API可天然处理传递关系；若需直接获取传递依赖，可在递归时合并依赖的依赖列表

内容的提问来源于stack exchange，提问作者seve