Rust中Pretty Printer实现的新设计

# 漂亮打印器在 Rust 中实现的新设计 来源：https://blog.wybxc.cc/blog/pretty-printer-pye/ 自从我研究了Rustc 的漂亮打印器 (https://blog.wybxc.cc/blog/pretty-printer-rustc/)并实现了自己的漂亮打印器库 (https://crates.io/crates/elegance)（该库用于cgrammar (https://crates.io/crates/cgrammar) crate，一个解析和处理 C23 语法的 crate），我一直在思考如何设计更好的漂亮打印器库，特别是将学术界的研究成果11. J. Hughes, “The Design of a Pretty-Printing Library,” *Advanced Functional Programming*, vol. 925. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 53–96, 1995. doi:10.1007/3-540-59451-5_3 (https://doi.org/10.1007/3-540-59451-5_3).22. P. Wadler, “A Prettier Printer,” *The Fun of Programming*. Macmillan Education UK, London, pp. 223–243, 2003. doi:10.1007/978-1-349-91518-7_11 (https://doi.org/10.1007/978-1-349-91518-7_11).33. J. -P. Bernardy, “A Pretty but Not Greedy Printer (Functional Pearl),” *Proceedings of the ACM on Programming Languages*, vol. 1, no. ICFP, pp. 1–21, Aug. 2017, doi:10.1145/3110250 (https://doi.org/10.1145/3110250).应用到实际的 Rust 库设计中。一个重要的障碍是，学术研究往往基于函数式编程语言，尤其是假设垃圾回收的存在，而 Rust 是一种没有垃圾回收的系统编程语言。这意味着在 Rust 中实现这些设计时，必须额外考虑内存管理。例如，在典型的 Wadler 风格44. 关于 Wadler 风格与 Oppen 风格漂亮打印器的区别，请参阅 elegance crate 文档中的说明 (https://docs.rs/elegance/0.4.0/elegance/#differences-from-other-libraries).漂亮打印器中，文档结构通常是一个递归数据类型： ``` type doc = | Nil | Append of doc * doc | Group of doc | FlatAlt of doc * doc | Nest of int * doc | Hardline | Text of string | Union of doc * doc | Fail ``` 然后通过布局函数将该文档结构转换为字符串输出： ``` let rec layout (d : doc) (width : int) : string = (* implementation omitted *) ``` 要在 Rust 中实现这样的算法，最直接的方式是采用相同的模式。例如，pretty (https://crates.io/crates/pretty) crate 实现了 Wadler 的经典算法（并有一些后续补充），其文档结构定义（简化）如下： ```rust pub enum Doc<A> { Nil, Append(T, T), Group(T), FlatAlt(T, T), Nest(isize, T), Hardline, Text(Box<String>), Union(T, T), Fail, } type BoxDoc = Box<Doc<BoxDoc>>; type RcDoc = Rc<Doc<RcDoc>>; ``` 如上所示，pretty crate 将 `Doc` 枚举泛型化为对类型 `T`，`T` 可以是 `BoxDoc`、`RcDoc` 或任何其他 `Doc` 的指针类型。这让用户可以更灵活地做出内存管理决策：使用更轻量的 `BoxDoc`，或者更灵活但更重的 `RcDoc`，或者一些区域分配器。55. 另一个好处是，这种设计有效地将 `Doc` 从类型转化为函子（functor），从而可以使用函子相关的抽象（如 catamorphism）来实现高效的递归算法；参见 recursion (https://crates.io/crates/recursion) crate。 然而，这种设计也有一些局限性。例如，它强制文档树中所有节点使用相同的内存管理策略，这在某些情况下可能缺乏灵活性。Oppen 风格的漂亮打印器（如Rustc 的漂亮打印器 (https://blog.wybxc.cc/blog/pretty-printer-rustc/)和elegance (https://crates.io/crates/elegance) crate）没有这个问题，因为 Oppen 风格将文档的输入和输出作为流处理，而不构建完整的文档树。但 Oppen 风格漂亮打印器的流式方法也限制了它们的表达能力。Sorawee Porncharoenwase 等人的研究66. S. Porncharoenwase, J. Pombrio, and E. Torlak, “A Pretty Expressive Printer,” *Proceedings of the ACM on Programming Languages*, vol. 7, no. OOPSLA2, pp. 1122–1149, Oct. 2023, doi:10.1145/3622837 (https://doi.org/10.1145/3622837).指出，通用漂亮打印问题是一个全局优化问题；流式漂亮打印器只能通过贪心算法获得局部最优解，不能保证全局最优。因此，为了实现全局最优的漂亮打印器，必须构建完整的文档树。 本文将为 Rust 中的漂亮打印器实现提出一个新设计，旨在保留 Wadler 风格文档树的表达能力，同时以一种更符合 Rust 内存管理的方式来实现。该实现的灵感来自函数式编程中的一个概念：一种数据类型可以通过使用它的方式来等价地表示。77. 请参阅我的另一篇博客文章：Church 编码、参数化性与 Yoneda 引理 (https://blog.wybxc.cc/blog/parametricity)。我们真正感兴趣的并不是文档树的具体结构，而是如何使用它来产生输出。因此，我们可以不定义 `Doc` 的递归数据结构，而是将 `Doc` 定义为一个 trait，其中包含一个消耗文档并产生输出的方法。 ```rust pub trait Doc { fn layout(&self, renderer: &mut Render) -> RenderOutput; } ``` 而各种文档构造则变成实现该 trait 的不同类型，例如： ```rust #[derive(Clone)] pub struct Text { s: String, } impl Doc for Text { fn layout(&self, renderer: &mut Render) -> RenderOutput { renderer.text(&self.s) } } pub fn text(s: impl Into<String>) -> impl Doc { Text { s: s.into() } } ``` 还有： ```rust #[derive(Clone)] pub struct Concat<A: Doc, B: Doc> { a: A, b: B, } impl<A: Doc, B: Doc> Doc for Concat<A, B> { fn layout(&self, renderer: &mut Render) -> RenderOutput { // fn Render::concat( // self: &Render, // left: RenderOutput, // right: impl Fn(&Render) -> RenderOutput // ) -> RenderOutput; renderer.concat(self.a.layout(renderer), |r| self.b.layout(r)) } } pub fn concat<A: Doc, B: Doc>(a: A, b: B) -> impl Doc { Concat { a, b } } ``` 在这个模型中，文档树的结构仍然存在。但与递归数据结构方法相比，它显著减少了内存间接寻址和动态分配开销。同时，它支持更灵活的内存管理。例如，你可以在文档树中混合使用 `Box` 和 `Rc`，因为两者都实现了 `Doc` trait。 ```rust impl<T: Doc> Doc for Box<T> { fn layout(&self, renderer: &mut Render) -> RenderOutput { self.as_ref().layout(renderer) } } impl<T: Doc> Doc for Rc<T> { fn layout(&self, renderer: &mut Render) -> RenderOutput { self.as_ref().layout(renderer) } } ``` 从另一个角度来看，这有些类似于我们在面向对象语言（如 C++）中实现枚举类型的方式：我们为所有文档定义一个基类，每个文档构造是基类的一个子类。 我为上述设计编写了一个概念验证（下文称为 pye）88. 借助 AI 辅助。我没有发布 pye 的代码，因为我还没有完全审查并整理好它。，实现了论文 *A pretty expressive printer* (OOPSLA’23)99. S. Porncharoenwase, J. Pombrio, and E. Torlak, “A Pretty Expressive Printer,” *Proceedings of the ACM on Programming Languages*, vol. 7, no. OOPSLA2, pp. 1122–1149, Oct. 2023, doi:10.1145/3622837 (https://doi.org/10.1145/3622837). 中的算法 Πe，一个通用且全局最优的漂亮打印算法，并与以下 crate 进行了性能比较： - pretty (https://crates.io/crates/pretty) crate，Rust 生态中最广泛使用的 Wadler 风格漂亮打印器实现。 - elegance (https://crates.io/crates/elegance) crate，一个 Oppen 风格流式漂亮打印器实现。 - pretty-expressive (https://crates.io/crates/pretty-expressive) crate（下文称为 pe），论文 *A pretty expressive printer* 的直接 Rust 实现。 在一个 78kB 的 JSON 格式化任务中，pye 比 pe 快 60 倍，达到了 pretty crate 约 57% 的性能。pye 比 pretty crate 慢的主要原因是 pye 实现了全局最优算法，而 pretty crate 使用了更简单的贪心算法。但是，与使用相同算法的 pe 相比，pye 的性能提升表明这种新设计在 Rust 中具有竞争力。 下面是在更多格式化任务上的性能比较，包括 JSON 记录、JSON 数组、深度嵌套的 JSON、混合 JSON 和 Lisp 代码。每个任务有多个变体：wide（行宽足够容纳在一行）、middle（中等行宽，常见用例）、narrow（行宽非常小）。在这些任务上，pye 的性能总体上与 pretty 和 elegance 相当，甚至在某些任务上超过了这两个 crate，同时在绝大多数任务上显著优于 pe。 **更新：** 我添加了新的实验，包含更多性能比较，包括： - 使用本文提出的设计，但实现与 pretty crate 相同的贪心算法（下文称为 pretty2）； - pretty crate，但使用区域分配器（arena allocator）（下文称为 p-arena）。 实验结果如下： 可以观察到几个有趣的发现： 1. p-arena 优于 pretty，证实了内存管理确实是漂亮打印器实现中的性能瓶颈。 2. pretty2 比所有其他实现都快，并且在某些任务上比 pretty 和 p-arena 快 10 倍以上（与 pye 和 pe 之间的性能差距相当），表明本文提出的设计确实能够带来显著的性能提升。 3. pye 始终比 pretty2 慢。这表明虽然所提出的设计可以提高性能，但算法的选择（全局最优 vs. 贪心）对性能的影响更大。 4. 基于流的 elegance 相比 pretty2 和 p-arena 没有显示出性能优势。这可能是由于基准测试的设计：非流式算法只测量布局任务的时间，不包括文档树构建；而流式算法中两者是交织的，因此度量时间包含了两者。 - J. Hughes, “The Design of a Pretty-Printing Library,” *Advanced Functional Programming*, vol. 925. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 53–96, 1995. doi:10.1007/3-540-59451-5_3 (https://doi.org/10.1007/3-540-59451-5_3). - P. Wadler, “A Prettier Printer,” *The Fun of Programming*. Macmillan Education UK, London, pp. 223–243, 2003. doi:10.1007/978-1-349-91518-7_11 (https://doi.org/10.1007/978-1-349-91518-7_11). - J. -P. Bernardy, “A Pretty but Not Greedy Printer (Functional Pearl),” *Proceedings of the ACM on Programming Languages*, vol. 1, no. ICFP, pp. 1–21, Aug. 2017, doi:10.1145/3110250 (https://doi.org/10.1145/3110250). - S. Porncharoenwase, J. Pombrio, and E. Torlak, “A Pretty Expressive Printer,” *Proceedings of the ACM on Programming Languages*, vol. 7, no. OOPSLA2, pp. 1122–1149, Oct. 2023, doi:10.1145/3622837 (https://doi.org/10.1145/3622837).