256行或更少：测试用例最小化

# 256 行代码以内：测试用例最小化 来源：https://matklad.github.io/2026/04/20/test-case-minimization.html 2026年4月20日 属性测试（Property Based Testing）和模糊测试是一个深入且需要大量技术积累的领域。这里面涉及的进阶技术足够写几篇博士论文、打造一个 PBT 守护进程，以及一套客户端-服务器架构（https://antithesis.com/blog/2026/hegel/）。但我有一个很酷的" parlor-trick" PBT 库，用一个下午几百行代码就能实现出来。这周我一直在思考一个共识算法的有趣变体。我周末实现了它。写 PBT 库本身花了几个小时，然后又写了测试，结果就暴露了我思维中的一个深层算法缺陷（之前还有十几个简单的编码小问题）。 所以，关于共识算法我暂时还写不了更多，但至少可以聊聊这个库。它非常简单，甚至可以说是简陋的。用一个关于巴别尔（https://en.wikipedia.org/wiki/Isaac_Babel）和倍倍尔（https://en.wikipedia.org/wiki/August_Bebel）的苏联老笑话来说，它是戈尔戈兰而非黑格尔。但区区 256 行代码，它是我工具箱里最高的功率重量比工具之一。 如果你想读这篇文章，可能是因为： - 你想锻炼一下生成式测试的肌肉。 - 你是个自己动手的类型，不想从货架上搬一个庞大的 PBT 库。 - 你会直接用库，但想要对现有选项有更明智的看法，了解什么是本质复杂度，什么是偶发复杂度。 - 你想看一些自包含的真实 Zig 示例 :P Zig 在这里表现出色，因为它本身的功率重量比也很出众。 ## FRNG（https://matklad.github.io/2026/04/20/test-case-minimization.html#FRNG） 整个实现是一个单文件，`FRNG.zig`（https://gist.github.com/matklad/343d13547c8bfe9af310e2ca2fbfe109），因为核心抽象是一个有限随机数生成器——一个所有数字都是预生成的、可能会耗尽的伪随机数生成器。 我们从标准样板代码开始： ``` const std = @import("std"); const assert = std.debug.assert; entropy: []const u8, pub const Error = error{OutOfEntropy}; const FRNG = @This(); pub fn init(entropy: []const u8) FRNG { return .{ .entropy = entropy }; } ``` 在 Zig 中，文件就是结构体：你显然需要结构体，而如果把结构体复用来替代文件的功能，语言就会变得更简单。在上面的代码中，`const FRNG = @This()` 给文件结构体赋予了一个约定俗成的名称，而 `entropy: []const u8` 声明了实例字段（这里只有一个）。`const Error` 和 `fn init` 是"静态"（容器级别）的声明。我们唯一的字段就是原始字节的切片，也就是预生成的随机数。我们唯一可能抛出的错误条件是 `OutOfEntropy`。 我们可以生成的最简单的东西就是一个字节切片。通常这个 API 接收一个可变切片作为输出参数： ``` pub fn fill(prng: *PRNG, bytes: []u8) void { ... } ``` 但是，由于 FRNG 的预生成特性，只要我们有足够的熵，就可以直接返回这个切片。这将是我们唯一的基元函数，其他所有功能都将在其基础上提供便利辅助函数： ``` pub fn bytes(frng: *FRNG, size: usize) Error![]const u8 { if (frng.entropy.len < size) return error.OutOfEntropy; const result = frng.entropy[0..size]; frng.entropy = frng.entropy[size..]; return result; } ``` 接下来最简单的东西是数组（固定大小的切片）： ``` pub fn array(frng: *FRNG, comptime size: usize) Error![size]u8 { return (try frng.bytes(size))[0..size].*; } ``` 注意 Zig 如何从运行时确定的切片长度过渡到编译时确定的数组类型。因为 `size` 是一个 `comptime` 常量，用 `[0..size]` 对 `[]const u8` 进行切片会返回一个指向数组的指针，`*[size]u8`。 我们可以将一个 4 字节数组重新解释为 `u32`。但是，因为这是 Zig，我们可以通过传入 `Int` 这个 `type` 类型的编译时参数，将这个函数简单地泛化以支持任意整数类型： ``` const builtin = @import("builtin"); pub fn int(frng: *FRNG, Int: type) Error!Int { comptime { assert(@typeInfo(Int).int.signedness == .unsigned); assert(builtin.cpu.arch.endian() == .little); } return @bitCast(try frng.array(@sizeOf(Int))); } ``` 这个函数会为每个 `Int` 类型进行单态化，因此 `@sizeOf(Int)` 成为一个我们可以传递给 `fn array` 的编译时常量。生产代码在这里需要处理端序问题，但为了简单起见，我们将我们的端序假设编码为编译时断言。注意 Zig 如何将端序信息传达给程序。没有任何编译时的边信道或额外输入，比如 `--cfg` 标志。相反，编译器将目标 CPU 的所有信息实现为 Zig 代码。在编译器缓存目录中的某个地方有一个 `builtin.zig` 文件，其中包含： ``` pub const cpu: std.Target.Cpu = .{ .arch = .aarch64, .model = &std.Target.aarch64.cpu.apple_m3, // ... } ``` 这个文件可以通过 `@import("builtin")` 访问，所有常量都可以在编译时检查。 我们可以生成整数，而布尔值更简单： ``` pub fn boolean(frng: *FRNG) Error!bool { return (try frng.int(u8)) & 1 == 1; } ``` 严格来说，我们只需要一个位，而不是一个字节，但追踪单个位太麻烦了。 从任意整数，我们可以生成一个范围整数。根据《随机数包含》（https://matklad.github.io/2025/03/31/random-numbers-included.html），我们使用闭区间，这使得 API 不会失败，在调用点通常更方便： ``` pub fn int_inclusive(frng: *FRNG, Int: type, max: Int) Error!Int ``` 作为一点伪随机数生成器的小知识，虽然这可以写成 `frng.int(Int) % (max + 1)`，但结果会有偏差（不均匀）。考虑 `Int = u8` 且调用 `frng.int_inclusive(u8, 64 * 3)` 的情况。`0..64` 范围内的数字出现概率是 `64..(64*3)` 范围内数字的两倍，因为 256 范围的最后一个四分之一会与第一个范围重叠。生成一个**无偏**数字是很棘手的，可能需要从熵中读取**任意**数量的字节。详情请参阅 https://www.pcg-random.org/posts/bounded-rands.html。我没这样做，而是复制粘贴了 Zig 标准库的代码。使用后果自负！ ``` pub fn int_inclusive(frng: *FRNG, Int: type, max: Int) Error!Int { comptime assert(@typeInfo(Int).int.signedness == .unsigned); if (max == std.math.maxInt(Int)) return try frng.int(Int); const bits = @typeInfo(Int).int.bits; const less_than = max + 1; var x = try frng.int(Int); var m = std.math.mulWide(Int, x, less_than); var l: Int = @truncate(m); if (l < less_than) { var t = -%less_than; if (t >= less_than) { t -= less_than; if (t >= less_than) t %= less_than; } while (l < t) { x = try frng.int(Int); m = std.math.mulWide(Int, x, less_than); l = @truncate(m); } } return @intCast(m >> bits); } ``` 现在我们可以生成一个上下有界的整数： ``` pub fn range_inclusive( frng: *FRNG, Int: type, min: Int, max: Int, ) Error!Int { comptime assert(@typeInfo(Int).int.signedness == .unsigned); assert(min <= max); return min + try frng.int_inclusive(Int, max - min); } ``` 另一个常见操作是从切片中随机挑选一个元素。如果你想返回指向元素的指针，就需要 `const` 和 `mut` 两个版本的函数。一个更简单、更通用的解决方案是返回索引： ``` pub fn index(frng: *FRNG, slice: anytype) Error!usize { assert(slice.len > 0); return try frng.range_inclusive(usize, 0, slice.len - 1); } ``` 在调用点，`xs[try frng.index(xs)]` 看起来还不错，是恰当的 `const`-多态的，而且也可以用于多个并行数组。 ## 模拟（https://matklad.github.io/2026/04/20/test-case-minimization.html#Simulation） 到目前为止，我们已经用了大约 40% 的代码行来实现一个更差的随机数生成器，它可以在任何时候因为 `OutOfEntropy` 而失败。这有什么用？ 我们用它来向被测系统输入随机数据，观察它的反应，并检查它是否崩溃。如果我们让系统在任何意外发生时崩溃，而且我们的随机输入覆盖了所有可能输入的空间，我们就得到了对测试能检测到 bug 的置信度。 对于我的共识模拟，我有一个 `World` 结构体，它持有一个 `FRNG` 和一组副本： ``` const World = struct { frng: *FRNG, replicas: []Replica, // ... }; ``` `World` 有这样的方法： ``` fn simulate_request(world: *World) !void { const replica = try world.frng.index(world.replicas); const payload = try world.frng.int(u64); world.send_payload(replica, payload); } ``` 然后我随机选择要调用哪个方法： ``` fn step(world: *World) !void { const action = try world.frng.weighted(.{ .request = 10, .message = 20, .crash = 1, }); switch (action) { .request => try world.simulate_request(), .message => { ... }, .crash => { ... }, } } ``` 这里，`fn weighted` 是另一个 FRNG 辅助函数，它根据权重比例随机选择一个动作。这个辅助函数需要比我们之前看到的更多的反射机制： ``` pub fn weighted( frng: *FRNG, weights: anytype, ) Error!std.meta.FieldEnum(@TypeOf(weights)) { const fields = comptime std.meta.fieldNames(@TypeOf(weights)); var total: u32 = 0; inline for (fields) |field| total += @field(weights, field); assert(total > 0); var pick = try frng.int_inclusive(u64, total - 1); inline for (fields) |field| { const weight = @field(weights, field); if (pick < weight) { return @field( std.meta.FieldEnum(@TypeOf(weights)), field, ); } pick -= weight; } unreachable; } ``` `weights: anytype` 是编译时静态类型分发。这意味着我们的 `weighted` 函数可以用任何类型调用，每个特定类型都会创建一个新的单态化函数实例。虽然我们没有明确命名 `weights` 的类型，但可以通过 `@TypeOf(weights)` 获取它。`FieldEnum` 是一个类型级函数，它接收一个结构体类型： ``` const S = struct { foo: bool, bar: u32, baz: []const u8 }; ``` 并将其转换为一个枚举类型，每个字段对应一个变体，这正是我们想要的返回类型： ``` const E = enum { foo, bar, baz }; ``` 提示：如果你想快速学习 Zig 的反射能力，可以研究 Zig 标准库中 `std.meta`（https://codeberg.org/ziglang/zig/src/tag/0.16.0/lib/std/meta.zig）和 `std.enums`（https://codeberg.org/ziglang/zig/src/tag/0.16.0/lib/std/enums.zig）的实现。 `@field` 内置函数通过编译时字段名访问字段。它就像 Python 的 `getattr`/`setattr`，但额外要求它必须在编译时求值。 再加点料，我总是觉得很难确定什么样的权重是合理的，所以喜欢在测试开始时随机生成权重本身： ``` pub fn swarm_weights(frng: *FRNG, Weights: type) Error!Weights { var result: Weights = undefined; inline for (comptime std.meta.fieldNames(Weights)) |field| { @field(result, field) = try frng.range_inclusive(u32, 1, 100); } return result; } ``` （如果你在这里感到困惑，可以看看《蜂群测试数据结构》（https://tigerbeetle.com/blog/2025-04-23-swarm-testing-data-structures/）） ## 步进与运行（https://matklad.github.io/2026/04/20/test-case-minimization.html#Stepping-And-Runnig） 现在我们有足够的机制来描述整个测试的形状： ``` fn run_test(gpa: Allocator, frng: *FRNG) !void { var world = World.init(gpa, &frng) catch |err| switch (err) { error.OutOfEntropy => return, else => return err, }; defer world.deinit(gpa); while (true) { world.step() catch |err| switch (err) { error.OutOfEntropy => break, }; } } const World = struct { frng: *FRNG, weights: ActionWeights, // ... const ActionWeights = struct { request: u32, message: u32, crash: u32, // ... }; pub fn init(gpa: Allocator, frng: *FRNG) !void { const weights = try frng.swarm_weights(ActionWeights); // ... } fn step(world: *World) error{OutOfEntropy}!void { const action = try world.frng.weighted(world.weights); switch (action) { .request => { ... }, // ... } } }; ``` 测试需要一个 `FRNG`（它最终决定测试结果）和一个通用分配器用于 `World`。我们首先用随机动作权重创建一个模拟的 `World`。如果 `FRNG` 熵非常低，我们甚至可能在这个阶段就耗尽熵。我们假设代码是无辜的，直到被证明有罪——如果我们没有足够的熵来发现 bug，这个特定测试返回成功。别担心，我们会在其他地方确保有足够的熵。 我们使用 `catch |err| switch(err)` 来剥离 `OutOfEntropy` 错误。我发现，在 Zig 中处理错误时，我经常只想从错误集中消除一个错误。我希望我能用括号和 `catch` 一起用： ``` // 这不是真正的 Zig :( var world = try World.init(gpa, &frng) catch (error.OutOfEntropy) return; ``` 无论如何，创建了 `World` 之后，我们继续对它进行步进，只要还有熵。如果任何步进检测到内部不一致，整个 `World` 会因为断言失败而崩溃。如果我们到达了 `while(true)` 循环的末尾，我们就知道至少那个特定的熵切片没有发现任何可疑的东西。 注意**没有什么**在其中。我们不是预先生成完整的动作列表。相反，我们边走边做随机决定，可以自由地使用 `World` 的当前状态来构建可选菜单（例如，在发送消息时，我们只能考虑当前未崩溃的副本）。 ## 二分搜索答案（https://matklad.github.io/2026/04/20/test-case-minimization.html#Binary-Search-the-Answer） 现在我们终于可以看到为什么要费心写一个自定义的**有限**伪随机数生成器，而不是使用现成的。FRNG 中熵的数量决定了测试的复杂度。我们起始的随机字节越少，我们就越快退出步进循环。这给了我们几乎免费地最小化测试用例的能力。 假设你知道一个特定的熵切片会导致测试失败（集群在第一百万步时进入脑裂状态）。假设那个切片是 16KiB。显而易见的下一步是看看只用 8KiB 是否就足以让它崩溃。而且，如果 8KiB 不行，那也许 12KiB 呢？你可以对**足以让测试失败的最小熵量**进行**二分搜索**。 这适用于**任何**测试，不一定是分布式系统。如果你能写代码**随机**生成你的输入，你就可以通过测量构造该输入时抽取了多少随机字节来衡量每个特定输入的复杂度。 现在有趣的部分来了——当然，似乎最小化熵的方法是取一个特定的失败切片，然后对其应用遗传算法突变。但实践中似乎有一种更简单的方法——生成一个新鲜的、更短的熵切片。如果你通过随机方式发现了**一些**失败，那么如果存在更小的失败例子，你应该能够随机地碰到它——因为较小的例子少得多，所以当**大小**下降时找到失败例子会更容易！ ## 搜索器（https://matklad.github.io/2026/04/20/test-case-minimization.html#The-Searcher） 用二分搜索寻找失败熵的问题在于，触发的断言会导致程序崩溃。Zig 中没有栈展开。基于这个原因，我们将搜索代码移到一个单独的进程中。因此单个测试将是一个带有 `main` 函数的二进制文件，它从 `stdin` 读取熵。Zig 的新版本 main 让写这个比以前任何版本的 Zig 都更容易 :D ``` pub fn main(init: std.process.Init) !void { const gpa = init.gpa; const io = init.io; var stdin_reader = std.Io.File.stdin().reader(io, &.{}); const entropy = try stdin_reader.interface .allocRemaining(gpa, .unlimited); defer gpa.free(entropy); var frng = FRNG.init(entropy); var world = World.init(gpa, &frng, .{}) catch |err| switch (err) { error.OutOfEntropy => return, else => return err, }; defer world.deinit(gpa); world.run(); } ``` Main 将 `Init` 作为参数...