用逆波兰表达式，彻底搞懂 Rust 宏的递归写法

原文Writing complex macros in Rust: Reverse Polish Notation作者 Ingvar StepanyanCloudflare Blog。Rust 的宏系统功能强大但也以难以掌握著称。很多人读完官方文档、照着示例写了几个简单的宏之后一旦遇到需要处理复杂 token 序列的场景就完全不知道从何下手了。这篇文章以 Cloudflare 工程师的一篇技术博客为蓝本通过实现一个编译期的逆波兰表达式求值宏把 Rust 声明宏macro_rules!的核心技巧完整地走一遍。什么是逆波兰表达式逆波兰表达式Reverse Polish NotationRPN也叫后缀表达式是一种不需要括号就能表达运算优先级的记法。它依赖一个栈来工作遇到操作数压栈遇到运算符从栈中取出两个操作数计算结果后再压回栈举个例子RPN 表达式2 3 4 *执行步骤如下2入栈 → 栈[2]3入栈 → 栈[3, 2]遇到取出3和2计算2 3 5压回 → 栈[5]4入栈 → 栈[4, 5]遇到*取出4和5计算5 * 4 20压回 → 栈[20]表达式结束栈顶即为结果20对应的中缀表达式是(2 3) * 4。我们的目标是写一个宏让下面的代码能在编译期完成求值println!({},rpn!(234*));// 20第一步用 token 序列模拟栈Rust 宏没有变量这个概念无法在运行时维护一个真正的栈。但宏可以在递归调用时携带一段 token 序列用来充当编译期的栈。我们用方括号包裹的、逗号分隔的expr序列来表示栈[$($stack:expr),*]每次递归调用时我们把这个栈更新后传给下一次调用以此来模拟栈的 push/pop 操作。第二步处理操作数先写处理单个数字操作数的分支。把数字压入栈然后继续处理剩余 tokenmacro_rules!rpn{([$($stack:expr),*]$num:tt$($rest:tt)*){rpn!([$num$(,$stack)*]$($rest)*)};}这里有两个关键点为什么用tt而不是expr或literal因为expr会贪婪地匹配可能把2 3整体吃掉而我们只需要匹配一个 token。tttoken tree恰好只匹配一个 token 树。递归是宏处理序列的唯一方式。宏不能用循环也不能修改变量。通过递归每次把处理好的新栈状态传入下一次调用直到消耗完所有 token这是声明宏处理列表的标准模式。第三步处理运算符运算符分支需要从栈中弹出两个操作数组合成中缀表达式后压回macro_rules!rpn{([$b:expr,$a:expr$(,$stack:expr)*]$($rest:tt)*){rpn!([$a$b$(,$stack)*]$($rest)*)};// - * / 类似...}注意栈中元素的顺序先入栈的$a在后后入栈的$b在前因为栈顶在左侧。运算时是$a op $b而不是$b op $a减法和除法的情况下这一点尤为重要。由于四个运算符的处理逻辑完全相同重复写四次显然不够优雅。第四步用op内部 helper 消除重复Rust 宏不能调用外部 helper但可以在同一个宏里定义内部分支用一个特殊的标记 token如op作为标识符与正常输入区分开macro_rules!rpn{// 内部 helper执行实际运算(op[$b:expr,$a:expr$(,$stack:expr)*]$op:tt$($rest:tt)*){rpn!([$a$op$b$(,$stack)*]$($rest)*)};// 四个运算符统一转发给 op($stack:tt$($rest:tt)*){rpn!(op$stack$($rest)*)};($stack:tt-$($rest:tt)*){rpn!(op$stack-$($rest)*)};($stack:tt*$($rest:tt)*){rpn!(op$stack*$($rest)*)};($stack:tt/$($rest:tt)*){rpn!(op$stack/$($rest)*)};// 操作数压栈([$($stack:expr),*]$num:tt$($rest:tt)*){rpn!([$num$(,$stack)*]$($rest)*)};}这里还有一个技巧在运算符分支里整个栈$stack被作为tt整体传递因为它是一个被方括号包裹的 token 树不需要展开里面的内容。只有在op分支里才真正拆解栈的内部结构。第五步处理终止条件和入口当所有 token 处理完毕栈中应该剩下唯一的结果([$result:expr]){$result};还需要一个入口分支让调用者不必手动传入空栈[]($($tokens:tt)*){rpn!([]$($tokens)*)};注意分支顺序很重要。这个兜底分支必须放在最后否则它会匹配一切导致其他分支永远无法触发。完整宏定义如下macro_rules!rpn{(op[$b:expr,$a:expr$(,$stack:expr)*]$op:tt$($rest:tt)*){rpn!([$a$op$b$(,$stack)*]$($rest)*)};($stack:tt$($rest:tt)*){rpn!(op$stack$($rest)*)};($stack:tt-$($rest:tt)*){rpn!(op$stack-$($rest)*)};($stack:tt*$($rest:tt)*){rpn!(op$stack*$($rest)*)};($stack:tt/$($rest:tt)*){rpn!(op$stack/$($rest)*)};([$($stack:expr),*]$num:tt$($rest:tt)*){rpn!([$num$(,$stack)*]$($rest)*)};([$result:expr]){$result};($($tokens:tt)*){rpn!([]$($tokens)*)};}测试println!({},rpn!(234*));// 20println!({},rpn!(15711-/3*211-));// 5两行都能正确输出且完全在编译期求值。第六步让错误信息更有用一个生产可用的宏还需要处理非法输入时给出清晰的错误提示而不是让编译器抛出莫名其妙的类型错误。情况一操作数过多缺少运算符输入rpn!(2 3 7 4 *)时栈最终有两个值而不是一个。此时会触发兜底分支产生难以理解的类型错误。解决方案在终止分支和兜底分支之间插入一个匹配栈里有多个值的错误分支([$($stack:expr),*]){compile_error!(concat!(表达式求值失败可能缺少运算符。当前栈状态,stringify!([$($stack),*])))};情况二操作数不足缺少操作数输入rpn!(2 3 *)时栈只有一个值却遇到了运算符op分支无法匹配两个操作数导致字符被当成普通 token 压栈产生奇怪的错误。解决方案给op也加一个兜底错误分支(op$stack:tt$op:tt$($rest:tt)*){compile_error!(concat!(运算符 ,stringify!($op), 无法应用于当前栈,stringify!($stack)))};加入这两个分支后错误信息会清晰地告诉用户问题所在error: 运算符 * 无法应用于当前栈[ 2 3 ]调试技巧trace_macros!宏的递归展开过程很难在脑子里完整跟踪。Rust nightly 提供了trace_macros!宏可以打印出每一步的展开过程#![feature(trace_macros)]fnmain(){trace_macros!(true);leterpn!(234*);trace_macros!(false);println!({},e);}编译时会输出类似这样的展开链expanding rpn! { 2 3 4 * } to rpn ! ( [ ] 2 3 4 * ) expanding rpn! { [ ] 2 3 4 * } to rpn ! ( [ 2 ] 3 4 * ) ...写复杂宏时这是定位问题最直接的工具。总结Rust 声明宏的三个核心技巧通过这个例子可以总结出编写复杂macro_rules!宏的三个核心模式1. 用 token 序列模拟状态宏没有变量但可以把状态编码在一段 token 序列里随着递归调用一路传下去。数据结构、栈、累加器都可以用这种方式实现。2. 用标记划分内部 helper在同一个宏里用特殊前缀如op、parse标记内部分支实现逻辑分层和代码复用避免大量重复的分支。3. 分支顺序决定匹配优先级macro_rules!按分支定义顺序逐一尝试匹配更具体的分支要放在更通用的分支之前。兜底的$($tokens:tt)*必须永远在最后。这三个技巧组合在一起足以应对绝大多数需要在编译期处理复杂 token 序列的场景。