订阅以接收新文章的通知:

在Rust中编写复杂的宏:逆波兰式

2018-01-31

6 分钟阅读时间
这篇博文也有 EnglishDeutsch한국어EspañolFrançais版本。

这是一篇最初发表在我个人博客上的教程摘要

除其他有趣的功能外,Rust还具有强大的宏系统。不幸的是,即使在阅读了《The Book》和各种教程之后,当涉及到尝试实现一个涉及处理不同元素的复杂列表的宏时,我仍然很难理解应该如何做,并且在花了一些时间后,我才突然灵光一闪,开始对所有内容使用宏 :) (好吧,并非对所有内容我都使用宏,我使用宏不是因为我不想使用函数和特殊类型以及存在时间之类的东西——就像我所见过的一些人那样。但是在任何地方,宏都是有用的)

Rust with a macro lens

CC BY 2.0 图片 来自 Conor Lawless

因此,下面是我对编写这些宏背后的原理的看法。这里假设您已经阅读了《The Book》中的章节,并且熟悉基本的宏定义和令牌类型。

在本教程中,我将以逆波兰式为例。它非常有趣,因为它非常简单,您可能在学校时就已经熟悉了它,但是要在编译时静态地实现它,您就需要使用递归宏方法。

逆波兰式(也称后缀式)使用堆栈进行所有操作,从而将任意操作数压入堆栈,而任何_[二进制]_操作都从堆栈中获取两个操作数,计算结果并将其放回堆栈。因此如下所示:

2 3 + 4 *

转换为:

  1. 将2放入堆栈。

  2. 将3放入堆栈。

  3. 从堆栈中取最后两值(3和2),应用运算符+并将结果(5)放回堆栈。

  4. 将4放入堆栈。

  5. 从堆栈中取最后两值(4和5),应用运算符*(4 * 5)并将结果(20)放回堆栈。

  6. 表达式结束,堆栈上有单值(20)。

在数学和大多数现代编程语言中使用的更常见的中缀表示法中,表达式应该是(2 + 3)* 4。

因此,让我们编写一个宏,它将在编译时通过将RPN(Region Proposal Network,区域候选网络)转换成Rust能够理解的中缀表示法来计算RPN。

macro_rules! rpn {
  // TODO
}

println!("{}", rpn!(2 3 + 4 *)); // 20

让我们先从将数字压入堆栈开始。

宏当前不允许匹配文字,并且expr对我们不起作用,因为它可能会意外地匹配序列,例如2 + 3 ......而不是仅取单个数字,因此我们将求助于tt——一种仅匹配一个标签树的通用令牌匹配器(无论它是一个原始令牌,例如literal/identifier/lifetime/等等;或一个()/[]/{}——带括号的表达式包含着更多令牌):

macro_rules! rpn {
  ($num:tt) => {
    // TODO
  };
}

现在,我们需要一个用于堆栈的变量。

宏不能使用实变量,因为我们希望这个堆栈只在编译时存在。相反,这里的技巧是使用一个单独的令牌序列,它可以被传递,就像一个累加器一样。

在我们的例子中,我们将它表示为一个逗号分隔的expr序列(因为我们不仅将其用于简单数字,而且还将其用于中间的中缀表达式),并将它封装到方括号中,以便与其他输入分隔开来:

macro_rules! rpn {
  ([ $($stack:expr),* ] $num:tt) => {
    // TODO
  };
}

现在,令牌序列并不是一个真正的变量——你不能就地修改它,然后再做一些事情。相反,你可以通过必要的修改创建这个令牌序列的新副本,然后再次递归地调用相同的宏。

如果您有函数语言背景,或者曾经使用过任何提供不可变数据的库,那么你可能已经熟悉这两种方法了——通过创建修改后的副本来修改数据和使用递归处理列表:

macro_rules! rpn {
  ([ $($stack:expr),* ] $num:tt) => {
    rpn!([ $num $(, $stack)* ])
  };
}

现在,很明显,只有一个数字的情况不太可能出现,并且这对我们来说也不太有趣,因此我们需要将该数字之后的其他任何内容匹配为零个或多个tt令牌序列,这些令牌可以传递给我们下一个调用的宏,用于进一步匹配和处理:

macro_rules! rpn {
  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
      rpn!([ $num $(, $stack)* ] $($rest)*)
  };
}

到这一步,我们仍然缺少运算符支持。我们如何匹配运算符?

如果我们的RPN是一系列令牌,我们希望以完全相同的方式进行处理,则可以简单地使用像这样的列表$($token:tt)*。不幸的是,这并不能让我们遍历列表并根据每个令牌推送操作数或应用运算符。

《The Book》说,“宏系统不处理解析歧义”,这对于单个宏分支是正确的——我们不能匹配一个数字序列,后跟一个诸如$($num:tt)* +的运算符,外加,因为+也是一个有效的令牌,可以由tt组匹配,但这又正是递归宏的作用所在。

如果宏定义中有不同的分支,Rust将一一尝试,因此我们可以将运算符分支放在数字一之前,这样可以避免任何冲突:

macro_rules! rpn {
  ([ $($stack:expr),* ] + $($rest:tt)*) => {
    // TODO
  };
  
  ([ $($stack:expr),* ] - $($rest:tt)*) => {
    // TODO
  };
  
  ([ $($stack:expr),* ] * $($rest:tt)*) => {
    // TODO
  };
  
  ([ $($stack:expr),* ] / $($rest:tt)*) => {
    // TODO
  };

  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
    rpn!([ $num $(, $stack)* ] $($rest)*)
  };
}

如前所述,运算符应用于堆栈上的最后两个数字,因此我们需要分别匹配它们,“计算”结果(构造一个正则中缀表达式)并将其放回:

macro_rules! rpn {
  ([ $b:expr, $a:expr $(, $stack:expr)* ] + $($rest:tt)*) => {
    rpn!([ $a + $b $(, $stack)* ] $($rest)*)
  };

  ([ $b:expr, $a:expr $(, $stack:expr)* ] - $($rest:tt)*) => {
    rpn!([ $a - $b $(, $stack)* ] $($rest)*)
  };

  ([ $b:expr, $a:expr $(, $stack:expr)* ] * $($rest:tt)*) => {
    rpn!([ $a * $b $(,$stack)* ] $($rest)*)
  };

  ([ $b:expr, $a:expr $(, $stack:expr)* ] / $($rest:tt)*) => {
    rpn!([ $a / $b $(,$stack)* ] $($rest)*)
  };

  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
    rpn!([ $num $(, $stack)* ] $($rest)*)
  };
}

我不太喜欢这种明显的重复,但是,就像文字一样,没有特殊的令牌类型可以匹配运算符。

但是,我们可以做的是添加一个负责计算的助手,并将任何显式的运算符分支委托给它。

在宏中,你不能使用外部辅助,但是唯一可以肯定的是您的宏已经在作用域内,因此通常的技巧是在同一个宏中用一些特殊的令牌序列来“标记”,然后像在常规分支中一样递归地调用它。

让我们使用@op作为标记,并在其中通过tt接受任意运算符(在这种情况下tt是明确的,因为我们只将运算符传递给这个帮助器)。

堆栈不再需要在每个单独的分支中展开——由于我们之前已将其包装在[]方括号中,因此可以将其与其他任意标签树(tt)匹配,然后传递给我们的帮助器:

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)*)
  };
}

现在,所有令牌都由相应的分支处理,我们只需要处理最后一种情况,当堆栈包含一个项目时,没有剩余的令牌:

macro_rules! rpn {
  // ...
  
  ([ $result:expr ]) => {
    $result
  };
}

此时,如果使用空堆栈和RPN表达式调用此宏,则该宏将已产生正确的结果:

Playground

println!("{}", rpn!([] 2 3 + 4 *)); // 20

然而,我们的堆栈是一个实现细节,我们真的不希望每个消费者传递一个空的堆栈,所以让我们在最后添加另一个通用分支作为入口点,并自动添加[]:

Playground

macro_rules! rpn {
  // ...

  ($($tokens:tt)*) => {
    rpn!([] $($tokens)*)
  };
}

println!("{}", rpn!(2 3 + 4 *)); // 20

我们的宏甚至可以用于更复杂的表达式,例如Wikipedia页面上有关RPN的表达式!

println!("{}", rpn!(15 7 1 1 + - / 3 * 2 1 1 + + -)); // 5

错误处理

现在,对于正确的RPN表达式,一切似乎都可以正常运行,但是对于要投入生产的宏,我们需要确保它也可以处理无效输入,并带有合理的错误消息。

首先,让我们尝试在中间插入另一个数字,看看会发生什么:

println!("{}", rpn!(2 3 7 + 4 *));

输出:

error[E0277]: the trait bound `[{integer}; 2]: std::fmt::Display` is not satisfied
  --> src/main.rs:36:20
   |
36 |     println!("{}", rpn!(2 3 7 + 4 *));
   |                    ^^^^^^^^^^^^^^^^^ `[{integer}; 2]` cannot be formatted with the default formatter; try using `:?` instead if you are using a format string
   |
   = help: the trait `std::fmt::Display` is not implemented for `[{integer}; 2]`
   = note: required by `std::fmt::Display::fmt`

好吧,因为它没有提供与表达式中的实际错误相关的任何信息,因此它看起来毫无用处。

为了弄清发生了什么,我们需要调试宏。为此,我们将使用trace_macros特性(并且,与其他可选的编译器特性一样,您需要一个不稳定测试版Rust)。我们不想回溯println!调用,因此我们将我们的RPN计算分离出一个变量:

Playground

#![feature(trace_macros)]

macro_rules! rpn { /* ... */ }

fn main() {
  trace_macros!(true);
  let e = rpn!(2 3 7 + 4 *);
  trace_macros!(false);
  println!("{}", e);
}

在输出中,我们现在将逐步查看宏的递归计算方式:

note: trace_macro
  --> src/main.rs:39:13
   |
39 |     let e = rpn!(2 3 7 + 4 *);
   |             ^^^^^^^^^^^^^^^^^
   |
   = note: expanding `rpn! { 2 3 7 + 4 * }`
   = note: to `rpn ! ( [  ] 2 3 7 + 4 * )`
   = note: expanding `rpn! { [  ] 2 3 7 + 4 * }`
   = note: to `rpn ! ( [ 2 ] 3 7 + 4 * )`
   = note: expanding `rpn! { [ 2 ] 3 7 + 4 * }`
   = note: to `rpn ! ( [ 3 , 2 ] 7 + 4 * )`
   = note: expanding `rpn! { [ 3 , 2 ] 7 + 4 * }`
   = note: to `rpn ! ( [ 7 , 3 , 2 ] + 4 * )`
   = note: expanding `rpn! { [ 7 , 3 , 2 ] + 4 * }`
   = note: to `rpn ! ( @ op [ 7 , 3 , 2 ] + 4 * )`
   = note: expanding `rpn! { @ op [ 7 , 3 , 2 ] + 4 * }`
   = note: to `rpn ! ( [ 3 + 7 , 2 ] 4 * )`
   = note: expanding `rpn! { [ 3 + 7 , 2 ] 4 * }`
   = note: to `rpn ! ( [ 4 , 3 + 7 , 2 ] * )`
   = note: expanding `rpn! { [ 4 , 3 + 7 , 2 ] * }`
   = note: to `rpn ! ( @ op [ 4 , 3 + 7 , 2 ] * )`
   = note: expanding `rpn! { @ op [ 4 , 3 + 7 , 2 ] * }`
   = note: to `rpn ! ( [ 3 + 7 * 4 , 2 ] )`
   = note: expanding `rpn! { [ 3 + 7 * 4 , 2 ] }`
   = note: to `rpn ! ( [  ] [ 3 + 7 * 4 , 2 ] )`
   = note: expanding `rpn! { [  ] [ 3 + 7 * 4 , 2 ] }`
   = note: to `rpn ! ( [ [ 3 + 7 * 4 , 2 ] ] )`
   = note: expanding `rpn! { [ [ 3 + 7 * 4 , 2 ] ] }`
   = note: to `[(3 + 7) * 4, 2]`

如果我们仔细查看回溯,就会发现问题出在以下步骤:

   = note: expanding `rpn! { [ 3 + 7 * 4 , 2 ] }`
   = note: to `rpn ! ( [  ] [ 3 + 7 * 4 , 2 ] )`

由于[ 3 + 7 * 4 , 2 ] 无法匹配([$result:expr]) =>……分支来作为最终表达式,因此它最终反而被我们的($($tokens:tt)*) => ......分支全捕获,并以空堆栈[]作为前缀,然后用通用的$num:tt匹配原始的[ 3 + 7 * 4 , 2 ],并作为单个最终值压入堆栈。

为了防止这种情况发生,让我们在最后两个分支之间插入另一个分支,它将匹配任何堆栈。

只有当我们用完令牌时,它才会被命中,但是堆栈并没有一个确切的最终值,所以我们可以将它视为编译错误,并使用内置compile_error!宏生成更有用的错误消息。

请注意,我们不能在这种情况下使用format!(格式化函数),因为它使用运行时API来格式化字符串,所以我们必须限制自己用内置的concat!和stringify!宏来格式化消息:

Playground

macro_rules! rpn {
  // ...

  ([ $result:expr ]) => {
    $result
  };

  ([ $($stack:expr),* ]) => {
    compile_error!(concat!(
      "Could not find final value for the expression, perhaps you missed an operator? Final stack: ",
      stringify!([ $($stack),* ])
    ))
  };

  ($($tokens:tt)*) => {
    rpn!([] $($tokens)*)
  };
}

错误信息现在意义更明确了,并且至少包含一些关于当前状态评估的详细信息:

error: Could not find final value for the expression, perhaps you missed an operator? Final stack: [ (3 + 7) * 4 , 2 ]
  --> src/main.rs:31:9
   |
31 |         compile_error!(concat!("Could not find final value for the expression, perhaps you missed an operator? Final stack: ", stringify!([$($stack),*])))
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
40 |     println!("{}", rpn!(2 3 7 + 4 *));
   |                    ----------------- in this macro invocation

但如果,相反地,我们错过了某个数字呢?

Playground

println!("{}", rpn!(2 3 + *));

不幸的是,前面的做法不太奏效了:

error: expected expression, found `@`
  --> src/main.rs:15:14
   |
15 |         rpn!(@op $stack * $($rest)*)
   |              ^
...
40 |     println!("{}", rpn!(2 3 + *));
   |                    ------------- in this macro invocation

如果您尝试使用trace_macros,即使出于某种原因它不会在这里扩大堆栈,但幸运的是,正在发生的事情是相对比较清楚的——@op对于什么应该匹配(预计至少有两个值在堆栈上)有着非常具体的条件,并且,当它匹配失败时,@会与同一个极度“贪婪”的$num:tt进行匹配,以及被压入堆栈。

为避免这种情况,再一次,我们将添加另一个分支以匹配任何@op尚未匹配的内容,并生成编译错误提示:

Playground

macro_rules! rpn {
  (@op [ $b:expr, $a:expr $(, $stack:expr)* ] $op:tt $($rest:tt)*) => {
    rpn!([ $a $op $b $(, $stack)* ] $($rest)*)
  };

  (@op $stack:tt $op:tt $($rest:tt)*) => {
    compile_error!(concat!(
      "Could not apply operator `",
      stringify!($op),
      "` to the current stack: ",
      stringify!($stack)
    ))
  };

  // ...
}

让我们再试一次:

error: Could not apply operator `*` to the current stack: [ 2 + 3 ]
  --> src/main.rs:9:9
   |
9  |         compile_error!(concat!("Could not apply operator ", stringify!($op), " to current stack: ", stringify!($stack)))
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
46 |     println!("{}", rpn!(2 3 + *));
   |                    ------------- in this macro invocation

好多了!现在我们的宏可以在编译时对任意RPN表达式求值,并且可以正常处理最常见的错误,所以我们今天就到此为止,并声明它已经可以投入生产了 :)

我们可以添加更多的小改进,但是我想把它们留在本演示教程之外再讲。

如果这对你有帮助,或者你想在Twitter上看到更好的话题,请随时告诉我!

我们保护整个企业网络,帮助客户高效构建互联网规模的应用程序,加速任何网站或互联网应用程序抵御 DDoS 攻击,防止黑客入侵,并能协助您实现 Zero Trust 的过程

从任何设备访问 1.1.1.1,以开始使用我们的免费应用程序,帮助您更快、更安全地访问互联网。要进一步了解我们帮助构建更美好互联网的使命,请从这里开始。如果您正在寻找新的职业方向,请查看我们的空缺职位
Rust开发人员ProgrammingCloudflare Polish

在 X 上关注

Cloudflare|@cloudflare

相关帖子

2024年10月24日 13:00

Durable Objects aren't just durable, they're fast: a 10x speedup for Cloudflare Queues

Learn how we built Cloudflare Queues using our own Developer Platform and how it evolved to a geographically-distributed, horizontally-scalable architecture built on Durable Objects. Our new architecture supports over 10x more throughput and over 3x lower latency compared to the previous version....