cargo-call-stack 源码解析指南：用 nom 手写 LLVM IR 解析器，构建全程序调用图

cargo-call-stack 源码解析指南：用 nom 手写 LLVM IR 解析器，构建全程序调用图

【免费下载链接】cargo-call-stackWhole program static stack analysis项目地址: https://gitcode.com/gh_mirrors/ca/cargo-call-stack

cargo-call-stack是一个 Rust 编写的全程序静态栈使用分析工具，它最核心的引擎，就是一个用nom组合子库手写的 LLVM IR 解析器。工具先用 nightly 编译器生成 LLVM IR（.ll文本），再用这个解析器把每个函数定义、调用语句"读"成内存数据结构，最终借助petgraph组装出全程序调用图，输出给 Graphviz 渲染。

本文带你潜入 Cargo.toml 声明的nom = "7.1.3"之下，看看这个不到 2000 行的解析器是如何分层的、有哪些巧妙（和"偷懒"）的设计。💡

为什么不用现成的解析库？

先看工具的数据流水线：

1. cargo +nightly call-stack以 fat LTO 重新构建你的程序，拿到合并后的 LLVM IR 文本
2. src/ir.rs的入口函数parse()把整篇 IR 解析为Vec<Item>
3. 从Item中抽取函数名与签名，从函数体中抽取调用边
4. 调用边装入petgraph有向图，输出.dot文件

为什么不直接用inkwell或反汇编二进制？因为工具依赖的符号表、-Z stack-sizes信息都以文本形式存在，而.ll文件恰好是结构非常规则的文本——手写一个"够用"的解析器比引入重量级 LLVM 绑定更轻、更可控。这也是本项目最值得关注的设计决策：它不需要解析完整的 LLVM IR，只需要解析出"构建调用图"所需的最小子集。

解析器分层设计：Item → Define → Stmt

解析器按 IR 的结构分成三个模块，层级关系一目了然：

Item枚举（item.rs）覆盖了 IR 文件的全部顶层结构：Alias、Global、Type、Define、Declare、Metadata、ModuleAsm等。顶层item()解析器就是对这些解析函数的一次alt分支尝试：

pub fn item(i: &str) -> IResult<&str, Item> { alt(( comment, source_filename, target, type_, global, alias, map(super::define::parse, Item::Define), declare, attributes, metadata, module_asm, ))(i) }

真正有价值的是Define变体。函数体内，Stmt枚举（define.rs）只保留了 7 种语句，其中对调用图分析至关重要的是这三种：

• DirectCall(&str)—— 直接调用，直接给出被调函数名，一条确定的边
• IndirectCall(FnSig)—— 间接调用（函数指针、trait 对象动态分发），只给出签名
• Asm(&str)—— 内联汇编，LLVM 的栈分析对它"失明"，工具需要另行处理

也就是说，解析阶段就已经完成了"降噪"：解析器只关心会形成调用边的语句，其余语句统统归入Stmt::Other丢弃。

手写 nom 解析器的几个关键技巧

1. 用"有意的失败"划清词法边界

attribute解析器（ir.rs）处理internal、fastcc等函数属性时，遇到double、float、bitcast、alias这类关键词会故意返回错误：

// have this branch always error because this is not an attribute but part of a type "double" | "float" | "void" | "ptr" => { return Err(nom::Err::Error(error_position!(i, ErrorKind::Switch))); }

这样alt组合子会自动回退，让类型解析器或语句解析器接手——用解析失败代替显式判断，是 nom 中处理"词法歧义"的惯用手法。

2. "够用就好"的快捷跳过

解析器大量使用not_line_ending直接吞掉整行剩余内容，例如declare遇到llvm.开头的内建函数（item.rs）：

if name.starts_with("llvm.") { // llvm intrinsic; we don't care about these let i = not_line_ending(i)?.0; Ok((i, Item::Declare(Declare { name, sig: None }))) }

内建函数不会出现在调用图里，所以整行跳过，签名记为None。这种"局部精确、全局粗略"的取舍，是嵌入式小工具写解析器的典型思路——不为完备性买单，只为下游需求买单。

3. 宽松匹配：loosely_equal应对类型信息丢失

Rust 有u32，但 LLVM 只有无符号整数（i32）；新版 LLVM 还使用不透明指针ptr，把fn f(x: &i32)和impl Foo { fn f(&self) }都压成fn(ptr) -> i1。因此Type不能简单==比较，而是实现了loosely_equal()（ty.rs）：

pub fn loosely_equal(&self, other: &Self) -> bool { match (self, other) { (Self::OpaquePointer, Self::OpaquePointer) => true, (Self::OpaquePointer, Self::Pointer(_)) => true, (Self::Pointer(_), Self::OpaquePointer) => true, // ... } }

这正是工具处理间接调用时的核心逻辑：把IndirectCall(FnSig)与所有已解析函数的签名做宽松比较，把"签名兼容"的函数全部连边。代价是可能出现多余边（详见 README.md 的 "Lossy type information" 章节），收益是不依赖 Rust 类型信息也能工作。

4. 精确的报错定位

parse()（ir.rs）把 nom 返回的失败偏移量换算回行号再报错，而不是抛出一个无法定位的偏移值——毕竟.ll文件动辄上万行。

5. 用真实 IR 片段做测试

src/ir/define/目录下有 11 个真实编译器输出的测试文件（parse1.ll 到 parse11.ll），覆盖内联汇编、间接调用、packed struct 等边缘场景。写解析器时，来自真实编译器的测试样例比手写字符串可靠得多。

从调用边到全程序调用图

解析完成后，工具把每条Stmt翻译成图论操作：DirectCall连一条确定边；IndirectCall按loosely_equal向所有签名匹配的函数连边；再结合-Z emit-stack-sizes提供的每个函数本地栈用量，做全图最大栈使用量计算，最后输出 dot 格式。以示例程序为例，工具产出的全程序调用图如下（每个节点同时标注local与max栈用量）：

图中Reset同时调用main和DefaultPreInit，这正是解析器从define体里抽出的DirectCall边。

给新手的可借鉴清单

• ✅组合子思维：tag/char拼词法，alt/many0/separated_list0/delimited搭结构，解析器就是"可组合的小函数"
• ✅为下游需求裁剪文法：不解析完整 IR，只保留调用图所需的最小子集，用not_line_ending大胆跳过
• ✅失败也是信息：用"故意返回错误"引导alt回退，解决词法歧义
• ✅测试用真实输入：保存真实编译器输出作为回归测试语料

如果你想继续深挖，建议按 src/ir.rs → src/ir/item.rs → src/ir/define.rs → src/ir/ty.rs 的顺序通读源码，再跑一遍 tests/firmware.rs 的固件级集成测试，即可完整复现"文本 IR → 全程序调用图"的全过程。🚀

【免费下载链接】cargo-call-stackWhole program static stack analysis项目地址: https://gitcode.com/gh_mirrors/ca/cargo-call-stack