Rusty thoughts on “Parse, don’t validate”

关于“解析，而非验证”的 Rust 思考

Like many programmers, I find Alexis King’s Parse, don’t validate article fascinating, because it gives a name to an idiom that seems familiar and important - one I’ve observed and used in the past without naming it explicitly. This post is a review of the “Parse, don’t validate” pattern applied to the Rust programming language (the original post uses Haskell). I was particularly interested in finding educational examples of this pattern in the Rust standard library and other well-known projects.

像许多程序员一样，我发现 Alexis King 的文章《解析，而非验证》（Parse, don’t validate）非常引人入胜，因为它为一个既熟悉又重要的编程范式赋予了名称——我过去曾观察并使用过它，却从未明确地命名过。本文旨在探讨“解析，而非验证”这一模式在 Rust 编程语言中的应用（原文使用的是 Haskell）。我特别感兴趣的是在 Rust 标准库和其他知名项目中寻找该模式的教学示例。

Without repeating the original article (please read it first!), here’s the gist of it. Consider the venerable Vec; its first method returns Option<&T>. Why? Because a vector is not guaranteed to have any elements in it, so what to do if first is invoked on an empty one? Returning an Option in this case is idiomatic in Rust [1], with convenient syntax sugar for accepting the result of functions that return Option and deciding what to do next.

在不重复原文内容的前提下（请务必先阅读原文！），这里是其核心要点。以经典的 Vec 为例；它的 first 方法返回 Option<&T>。为什么？因为向量（vector）并不保证包含任何元素，那么如果在一个空向量上调用 first 该怎么办？在这种情况下返回 Option 是 Rust 中的惯用做法 [1]，它提供了便捷的语法糖，可以接收返回 Option 的函数结果并决定下一步操作。

So what’s the issue? Imagine we have a function to read some configuration paths from an env var, while enforcing the invariant that the list can’t be empty:

那么问题出在哪里呢？想象一下，我们有一个函数用于从环境变量中读取一些配置路径，同时强制要求该列表不能为空：

use anyhow::{Result, ensure};

fn get_configuration_directories() -> Result<Vec<PathBuf>> {
    let value = env::var("CONFIG_DIRS").context("could not read CONFIG_DIRS")?;
    let directories: Vec<PathBuf> = value
        .split(',')
        .map(str::trim)
        .map(PathBuf::from)
        .collect();
    ensure!(!directories.is_empty(), "empty CONFIG_DIRS");
    Ok(directories)
}

So far, so good. Now let’s take a typical usage of this function:

到目前为止，一切顺利。现在让我们看看这个函数的典型用法：

fn main() -> Result<()> {
    let config_dirs = get_configuration_directories()?;
    match config_dirs.first() {
        Some(cache_dir) => initialize_cache(cache_dir),
        None => unreachable!("already checked that CONFIG_DIRS is non-empty"),
    }
    Ok(())
}

Once get_configuration_directories returns a successful result, we are guaranteed that the vector isn’t empty. And yet, if we want to get the first element of this vector, we have to use the first method that returns Option<&T>. We are therefore forced - again - to handle a potentially empty case (where the option is None). As the original article states, this has a number of problems with code clarity, potential performance implications and a ticking time bomb if the invariant is ever changed in get_configuration_directories.

一旦 get_configuration_directories 返回成功结果，我们就能保证该向量不为空。然而，如果我们想获取该向量的第一个元素，我们仍然必须使用返回 Option<&T> 的 first 方法。因此，我们被迫再次处理一个潜在的空情况（即 Option 为 None 的情况）。正如原文所述，这在代码清晰度、潜在性能影响方面存在诸多问题，如果 get_configuration_directories 中的不变性（invariant）发生改变，这更像是一枚定时炸弹。

The core issue is that Vec is fundamentally a type that can be empty; we can carry along a “This one can’t be empty, pinky promise!” comment on all the relevant code, but it’s not formally checked by anything.

核心问题在于 Vec 本质上就是一个可以为空的类型；我们可以在所有相关代码上加上“这个绝对不能为空，拉钩！”的注释，但这并没有经过任何形式化的检查。

A type for “non-empty” vector

用于“非空”向量的类型

The solution is leveraging the type system to enforce a newly established invariant. We can use a separate type for “a vector that cannot be empty”; in fact, such types already exist in several Rust crates - for example nonempty:

解决方案是利用类型系统来强制执行新建立的不变性。我们可以使用一个单独的类型来表示“不能为空的向量”；事实上，这类类型已经存在于多个 Rust crate 中——例如 nonempty：

pub struct NonEmpty<T> {
    pub head: T,
    pub tail: Vec<T>,
}

This type has no constructor that permits “no elements”; its new takes one element, and its first method returns &T without an Option:

该类型没有允许“无元素”的构造函数；它的 new 方法接收一个元素，而它的 first 方法直接返回 &T，无需 Option：

pub const fn new(e: T) -> Self { Self::singleton(e) }
pub const fn singleton(head: T) -> Self { NonEmpty { head, tail: Vec::new() } }
pub const fn first(&self) -> &T { &self.head }

The rest of the crate deals with making NonEmpty behave as close as possible to a normal Vec, by implementing many useful traits, as well as conversions like:

该 crate 的其余部分致力于通过实现许多有用的 trait 以及转换方法，使 NonEmpty 的行为尽可能接近普通的 Vec：

pub fn from_vec(mut vec: Vec<T>) -> Option<NonEmpty<T>> {
    if vec.is_empty() {
        None
    } else {
        let head = vec.remove(0);
        Some(NonEmpty { head, tail: vec })
    }
}

Let’s see how our get_configuration_directories function would look if it returned a NonEmpty instead of a plain Vec:

让我们看看如果 get_configuration_directories 函数返回 NonEmpty 而不是普通的 Vec，它会是什么样子：

fn get_configuration_directories() -> Result<NonEmpty<PathBuf>> {
    let value = env::var("CONFIG_DIRS").context("could not read CONFIG_DIRS")?;
    let directories = value
        .split(',')
        .map(str::trim)
        .map(PathBuf::from)
        .collect();
    let Some(directories) = NonEmpty::from_vec(directories) else {
        bail!("CONFIG_DIRS cannot be empty");
    };
    Ok(directories)
}

Note the use of NonEmpty::from_vec here - this is where the invariant is established. Now a successful result is NonEmpty, not just Vec. The client code looks like:

注意这里使用了 NonEmpty::from_vec —— 这就是建立不变性的地方。现在，成功的结果是 NonEmpty，而不仅仅是 Vec。客户端代码如下所示：

fn main() -> Result<()> {
    let config_dirs = get_configuration_directories()?;
    initialize_cache(config_dirs.first())?;
    Ok(())
}

There’s no need to check if the returned value is empty again; this is enforced by the type system! This is where the parse vs. validate terminology of the original article comes from. When get_configuration_directories returned a Vec, it simply validated it. But when it returns a NonEmpty - the vector is transformed into another entity which carries additional meaning. If we treat the concept of parsing in the most generic sense - “transforming data from one format to another”, this fits.

无需再次检查返回值是否为空；这是由类型系统强制执行的！这就是原文中“解析”与“验证”术语的由来。当 get_configuration_directories 返回 Vec 时，它仅仅是验证了它。但当它返回 NonEmpty 时，向量被转换成了另一个携带额外语义的实体。如果我们以最通用的意义来理解解析的概念——即“将数据从一种格式转换为另一种格式”，那么这完全吻合。

To mention a less artificial example, the Rust rewrite of core POSIX utilities uses NonEmpty in several places [2]. For example, when constructing a shell pipeline:

举一个不那么刻意的例子，POSIX 核心工具的 Rust 重写版在多处使用了 NonEmpty [2]。例如，在构建 shell 管道时：

pub struct Pipeline {
    pub commands: NonEmpty<Command>,
    pub negate_status: bool,
}

The command parser’s code:

命令解析器的代码如下：

fn parse_pipeline(&mut self, alias_table: &AliasTable) -> ParseResult<Option<Pipeline>> {
    // pipeline = "!" command ("|" linebreak command)*
    let negate_status = self.match_alternatives(&[CommandToken::Bang])?.is_some();
    let mut commands = if let Some(command) = self.parse_command(alias_table)? {
        NonEmpty::new(command)
    } else {
        return Ok(None);
    };
    // ...

A valid Pipeline is only returned if there are some commands in the parsed AST. Otherwise, it just returns None. Once this is done, the client code can use commands.first() without having to worry about the possibility of it returning None.

只有当解析后的 AST 中存在命令时，才会返回有效的 Pipeline。否则，它只会返回 None。一旦完成此操作，客户端代码就可以使用 commands.first()，而不必担心它返回 None 的可能性。

Gradual parsing and type refinement

渐进式解析与类型细化

A somewhat more interesting example can be found in the source code of rust-analyzer. This project has a type that represents an absolute filesystem path:

在 rust-analyzer 的源代码中可以找到一个更有趣的例子。该项目有一个表示绝对文件系统路径的类型：

pub struct AbsPathBuf(Utf8PathBuf);

Instead of carrying around a regular path, the absoluteness is recorded in the type once the initial parsing and validation is done:

它不再携带普通的路径，而是在完成初始解析和验证后，将“绝对路径”这一属性记录在类型中：

impl TryFrom<Utf8PathBuf> for AbsPathBuf {
    type Error = Utf8PathBuf;
    fn try_...