lib/reducer/src/root.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! Starting from an input that reproduces a defect and deleting runs of bytes
2 //! from it until a smaller input still reproduces it is *test-case reduction*.
3 //!
4 //! The example running through this doc is the input `"abcXYZdef"` with a
5 //! function answering whether a candidate reproduces the defect, the *oracle*,
6 //! that answers interesting for any candidate containing `"XYZ"`:
7 //!
8 //! ```zig
9 //! const std = @import("std");
10 //! const reducer = @import("reducer");
11 //!
12 //! const Context = struct { needle: []const u8 };
13 //!
14 //! fn checkNeedle(input: []const u8, ptr: *anyopaque) anyerror!reducer.Interesting {
15 //! const ctx: *const Context = @ptrCast(@alignCast(ptr));
16 //! return if (std.mem.indexOf(u8, input, ctx.needle) != null)
17 //! .interesting
18 //! else
19 //! .uninteresting;
20 //! }
21 //!
22 //! test "basic reducer demonstration" {
23 //! const allocator = std.testing.allocator;
24 //! const initial = "abcXYZdef";
25 //! var ctx = Context{ .needle = "XYZ" };
26 //!
27 //! var storage = try reducer.Storage.init(allocator, .{ .max_input_bytes = initial.len });
28 //! defer storage.deinit(allocator);
29 //! storage.activate();
30 //!
31 //! var result = try reducer.reduce(&storage, initial, checkNeedle, &ctx, .{});
32 //! defer result.deinit();
33 //!
34 //! try std.testing.expectEqualSlices(u8, "XYZ", result.bytes);
35 //! try std.testing.expectEqual(reducer.Completion.one_minimal, result.completion);
36 //! }
37 //! ```
38 //!
39 //! Once the workspace (the one byte allocation `Storage` makes up front and
40 //! reuses for every run) is initialized and sealed into steady state, its owner
41 //! allocates nothing further, and the reduction loop itself calls no allocator.
42 //!
43 //! ## The Oracle Contract
44 //!
45 //! The caller hands the condition under test to `reduce()` as a callback whose
46 //! type is `InterestingFn`:
47 //!
48 //! ```zig
49 //! fn interesting(candidate: []const u8, context: *anyopaque) anyerror!Interesting
50 //! ```
51 //!
52 //! The callback answers *interesting* when the *candidate* (one shorter byte
53 //! sequence built by deleting a run of bytes from the current sequence and
54 //! handed to the oracle) reproduces the condition under test and
55 //! *uninteresting* when it does not, which covers a candidate that fails to
56 //! parse, holds invalid UTF-8, or runs into an unrelated error. A caller's
57 //! oracle answers interesting for the one symptom under investigation, and a
58 //! candidate that crashes or errors in some other way is uninteresting.
59 //! Returning a Zig error from the callback ends the run at once: the error
60 //! travels out to the caller, and this run's lease on the workspace is given
61 //! up.
62 //!
63 //! The search works on raw bytes, so a deletion falls at any byte offset and
64 //! respects no line of text and no character boundary. On *attempt* 1 (the call
65 //! of the oracle on the caller's own input), the callback receives the caller's
66 //! own `initial` slice, so that memory stays valid and unchanged for the whole
67 //! run. On every later attempt the callback receives a slice into the *scratch
68 //! lane* (the fixed part of the workspace where each candidate is assembled),
69 //! whose bytes the next iteration overwrites, so the callback retains no
70 //! candidate slice past its return.
71 //!
72 //! The context pointer stays alive for the whole synchronous call, and the cast
73 //! the callback performs on it matches the real type and alignment of what it
74 //! points at. Side effects such as logging or the callback's own scratch
75 //! allocation are allowed as long as the answer for a given candidate stays the
76 //! same. The minimality claims below rest on an oracle that is deterministic
77 //! and decides from the candidate's content alone, which is an assumption about
78 //! the caller's code.
79 //!
80 //! Reduction searches the space of inputs for a smaller one that still
81 //! reproduces the defect. Fault injection answers a different question:
82 //! `lib/tripwire` fires simulated error sites and needs its own postcondition
83 //! assertions to check that rollback happened.
84 //!
85 //! ## Deletion Search and Minimality
86 //!
87 //! Dropping the byte at index $i$ of a sequence $x$ whose length is $n$, for
88 //! $0 \le i < n$, and joining the two half-open pieces `x[0..i]` and
89 //! `x[i+1..n]` is *occurrence deletion*, producing a shorter *subsequence*:
90 //!
91 //! $$\text{delete}(x, i) = x[0 \dots i] \Vert x[i+1 \dots n]$$
92 //!
93 //! At $i = 0$ the leading piece `x[0..0]` is empty, and at $i = n - 1$ the
94 //! trailing piece `x[n..n]` is empty.
95 //!
96 //! An interesting sequence where every single-byte deletion from it was tried
97 //! and came back uninteresting is *1-minimal* under that oracle:
98 //!
99 //! $$\forall i \in \{0, \dots, |x| - 1\}, \quad P(\text{delete}(x, i)) = \text{uninteresting}$$
100 //!
101 //! An empty sequence has no index to delete, so an empty interesting input is
102 //! already 1-minimal.
103 //!
104 //! ### Differences from Textbook `ddmin`
105 //!
106 //! Andreas Zeller and Ralf Hildebrandt formulated *delta debugging (`ddmin`)*,
107 //! which splits an input into $n$ subsets $\Delta_1, \dots, \Delta_n$ and
108 //! alternates between testing one subset $\Delta_i$ alone and testing its
109 //! complement $c_x \setminus \Delta_i$, moving $n$ between 2 and $|c_x|$
110 //! ([Simplifying and Isolating Failure-Inducing Input](https://doi.org/10.1109/32.988498),
111 //! IEEE TSE 2002, Figure 5).
112 //!
113 //! This package differs from that formulation in three ways:
114 //!
115 //! - **Deletion sweeps:** the search runs contiguous deletion *sweeps* (passes
116 //! over the current sequence at a fixed chunk, from its start to its end)
117 //! through `without()` and has no separate phase that tests one subset alone.
118 //! Deleting one half of a two-way split leaves the other half behind, so that
119 //! case arrives through deletion.
120 //! - **Chunk halving:** the search tracks a *chunk* (the number of adjacent
121 //! bytes one candidate deletes) in bytes where `ddmin` tracks a count of
122 //! subsets. It starts with the chunk at the whole length of the *current
123 //! sequence* (the shortest sequence the oracle has accepted so far, which the
124 //! search deletes from next), which tests the empty sequence `""`, and halves
125 //! the chunk with ceiling division down to 1:
126 //! $$\text{chunk} \leftarrow \lfloor \text{chunk} / 2 \rfloor + (\text{chunk} \bmod 2)$$
127 //! - **Greedy restart:** accepting a candidate is a greedy restart that records
128 //! a *reduction*, one candidate accepted by the oracle that replaces the
129 //! current sequence and is strictly shorter. The current sequence becomes
130 //! that candidate, `reductions` goes up by one, and the chunk resets to the
131 //! whole length of the new current sequence.
132 //!
133 //! Building a candidate copies bytes into the scratch lane through `without()`,
134 //! and accepting one swaps which lane each of the two local names refers to, so
135 //! no bytes are copied back.
136 //!
137 //! ## Trace: `abcXYZdef` to `XYZ`
138 //!
139 //! For the input `"abcXYZdef"`, whose length $N$ is 9, with an oracle requiring
140 //! `"XYZ"`, the search runs 14 attempts and accepts 2 reductions:
141 //!
142 //! | Attempt | Candidate | Outcome |
143 //! | :--- | :--- | :--- |
144 //! | 1 | `"abcXYZdef"` | Baseline verified; start chunk 9 |
145 //! | 2 | `""` | Rejected; next chunk 5 |
146 //! | 3 | `"Zdef"` | Rejected (delete `[0..5]`) |
147 //! | 4 | `"abcXY"` | Rejected (delete `[5..9]`); next chunk 3 |
148 //! | 5 | `"XYZdef"` | **Reduction 1**: accepted; restart chunk 6 |
149 //! | 6 | `""` | Rejected; next chunk 3 |
150 //! | 7 | `"def"` | Rejected (delete `[0..3]`) |
151 //! | 8 | `"XYZ"` | **Reduction 2**: accepted; restart chunk 3 |
152 //! | 9 | `""` | Rejected; next chunk 2 |
153 //! | 10 | `"Z"` | Rejected (delete `[0..2]`) |
154 //! | 11 | `"XY"` | Rejected (delete `[2..3]`); next chunk 1 |
155 //! | 12 | `"YZ"` | Rejected (delete index 0) |
156 //! | 13 | `"XZ"` | Rejected (delete index 1) |
157 //! | 14 | `"XY"` | Rejected (delete index 2); sweep complete |
158 //!
159 //! Every single-byte deletion at chunk 1 came back uninteresting, so the run
160 //! ends with `Completion.one_minimal`.
161 //!
162 //! ## Local and Global Minimality
163 //!
164 //! 1-minimality says that no single byte comes out of the result on its own. It
165 //! leaves open whether some shorter interesting sequence exists, which would be
166 //! *globally shortest* (no shorter interesting sequence existing at all).
167 //!
168 //! A worked case: the input `"ABCD"` with an oracle that accepts any sequence
169 //! containing `'A'` or containing `"CD"`:
170 //! - `"ABCD"` is interesting.
171 //! - At chunk 2, deleting `"AB"` tests `"CD"`, which the oracle accepts.
172 //! - From `"CD"`, the single-byte deletions `"D"` and `"C"` are both rejected.
173 //! - The single-byte sweep then finishes, which certifies `"CD"`, of length 2,
174 //! as `one_minimal`.
175 //! - `"A"`, of length 1, also satisfies that oracle.
176 //!
177 //! Greedy chunk deletion follows the first deletion that succeeds, so when an
178 //! input carries multiple independent causes of the failure, the result depends
179 //! on which deletion the sweep reaches first.
180 //!
181 //! ### Abstract Formal Model
182 //!
183 //! A formal model of reduction paths over `List α` lives in
184 //! `verification/foundations/Foundations/Reduction`, in `Core.lean` and
185 //! `Necessity.lean`:
186 //! - `gap_is_not_globallyShortest` proves that a 1-minimal list can fail to be
187 //! globally shortest.
188 //! - `budget_truncation_is_not_oneMinimal` gives a concrete witness where
189 //! cutting the search short of all single-byte deletions gives up
190 //! 1-minimality.
191 //!
192 //! `Completion` records how the search stopped at run time. A run that ends in
193 //! `budget_exhausted` carries no 1-minimality guarantee, even when its result
194 //! happens to be minimal. The Lean development is an abstract calculus over
195 //! lists, and it proves nothing about this Zig code.
196 //!
197 //! ## Attempt Budgets and Boundary Behavior
198 //!
199 //! The ceiling on the number of oracle calls, `Settings.max_attempts`, forms
200 //! the *attempt budget*, capping how many times the oracle is called and
201 //! counting the call on the caller's own input as attempt 1. The cap covers
202 //! oracle calls alone: bytes copied, memory the callback allocates, and
203 //! wall-clock time all sit outside it.
204 //!
205 //! - A budget of 0 returns `error.AttemptBudgetExhausted` before the workspace
206 //! is acquired, leaving every byte and every flag of the workspace as it was.
207 //! - A budget of 1:
208 //! - A budget of 1 on an empty interesting input returns
209 //! `Completion.one_minimal` straight away, with 1 attempt and 0 reductions.
210 //! - A budget of 1 on a nonempty interesting input stops after attempt 1 with
211 //! `Completion.budget_exhausted` and hands back the input as it arrived.
212 //! - A budget that is exactly enough for the single-byte sweep to try every
213 //! deletion still certifies `Completion.one_minimal`, including when the
214 //! sweep finishes on the last allowed attempt.
215 //!
216 //! ## Storage Architecture and Lifecycle
217 //!
218 //! | Operation | Effect / Transition |
219 //! | :--- | :--- |
220 //! | `storage.activate()` | Moves `initialization` to `steady (idle)` |
221 //! | `storage.acquire(bytes)` | Leases `steady (idle)` to `steady (acquired)` |
222 //! | `result.deinit()` / `storage.release()` | Releases `steady (acquired)` back to `steady (idle)` |
223 //! | `storage.deinit(allocator)` (unactivated) | Frees unactivated `initialization` to `teardown` |
224 //! | `storage.deinit(allocator)` (idle) | Frees idle `steady` to `teardown` (invalid while acquired) |
225 //!
226 //! 1. **Capacity derivation:** `Capacity.derive(limits)` calculates the
227 //! workspace *capacity* (the arithmetic layout derived from the caller's
228 //! *limits*, the sizing figure $N$ for the longest input submitted) as
229 //! $N + \max(N - 1, 0)$ bytes and allocates nothing. A sum that overflows
230 //! `usize` returns `DeriveError.CapacityOverflow`. For $N = 0$ the figure is
231 //! 0 bytes. Filling in `Storage` or `Capacity` fields by hand is unsafe, so
232 //! callers reach the same layout through `Storage.init()` and
233 //! `Capacity.derive()`.
234 //! 2. **Initialization:** `Storage.init(allocator, limits)` allocates the
235 //! backing memory once, setting the workspace lifecycle *phase* to
236 //! `Phase.initialization`. A workspace that was never activated can be freed
237 //! directly by `storage.deinit(allocator)`.
238 //! 3. **Activation:** `storage.activate()` seals the workspace into
239 //! `Phase.steady`, *idle* with no lease outstanding so the next run can
240 //! acquire it. After that the workspace owner allocates nothing further.
241 //! 4. **Acquisition:** `storage.acquire(input_bytes)` checks the input against
242 //! the bounds, issues a *lease* by setting `in_use = true` for this run's
243 //! exclusive hold, and returns `Regions`, writing nothing into the lanes.
244 //! 5. **Error isolation:** the three errors raised before acquisition,
245 //! `AttemptBudgetExhausted`, `ReductionStorageInUse`, and
246 //! `InputCapacityExceeded`, leave the workspace as it was, so a call that
247 //! finds the workspace busy leaves an earlier live `Result` holding its
248 //! lease. An error after acquisition gives up this run's lease through
249 //! `errdefer storage.release()` and returns the workspace to idle, which
250 //! restores neither the scratch bytes the run overwrote nor any side effect
251 //! the callback produced.
252 //! 6. **Release and reuse:** `Result.deinit()`, or `storage.release()`, clears
253 //! `in_use` and returns the workspace to steady and idle. `deinit()` also
254 //! clears the result's own fields, setting `bytes = &.{}`, `attempts = 0`,
255 //! `reductions = 0`, and `completion = .budget_exhausted`, which ends the
256 //! *borrow* (`Result.bytes` referencing workspace memory), and it is called
257 //! exactly once per result. Feeding one run's result back in as the next
258 //! run's input on the same workspace means copying `result.bytes` first.
259 //! 7. **Teardown:** `storage.deinit(allocator)` checks that no lease is out,
260 //! moves the workspace to `Phase.teardown`, and frees the memory with the
261 //! same allocator `init()` received.
262 //!
263 //! ### Ownership and Concurrency
264 //!
265 //! - `Result.bytes` borrows from the workspace and stays readable until
266 //! `result.deinit()`.
267 //! - `Storage.current` and `Storage.candidate` are fixed regions of the
268 //! workspace allocation, with the *witness lane* holding the current
269 //! sequence, while the locals `current` and `spare` inside `reduce()` trade
270 //! places, so `Result.bytes` can end up in either region.
271 //! - `Storage` offers no thread safety. `in_use` is a plain boolean that turns
272 //! away a second use on one thread, so sharing one workspace across threads
273 //! is the caller's to synchronize.
274 //! - One owner holds a given `Storage` and a given `Result`, makes no shallow
275 //! copy of either, and leaves their bookkeeping fields alone.
276 //!
277 //! ## Historical Context and Related Work
278 //!
279 //! - **Delta Debugging (`ddmin`):** Andreas Zeller introduced delta debugging
280 //! to isolate the code change responsible for a failure
281 //! ([Yesterday, My Program Worked. Today, It Does Not. Why?](https://www.st.cs.uni-saarland.de/publications/files/zeller-esec-1999.pdf),
282 //! ESEC/FSE 1999, pages 253–267, ACM DOI:
283 //! [10.1145/318774.318946](https://doi.org/10.1145/318774.318946)). Andreas
284 //! Zeller and Ralf Hildebrandt then generalized the algorithm to minimizing
285 //! an input
286 //! ([Simplifying and Isolating Failure-Inducing Input](https://doi.org/10.1109/32.988498),
287 //! IEEE TSE 2002).
288 //! - **Hierarchical Delta Debugging (HDD):** Ghassan Misherghi and Zhendong Su
289 //! pruned parse trees one level at a time
290 //! ([HDD: Hierarchical Delta Debugging](https://doi.org/10.1145/1134285.1134307),
291 //! ICSE 2006). Whether the result is syntactically valid rests on the tree
292 //! manipulator and the grammar keeping it valid.
293 //! - **C-Reduce:** John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky
294 //! Ellison, and Xuejun Yang built C-Reduce
295 //! ([Test-Case Reduction for C Compiler Bugs](https://doi.org/10.1145/2254064.2254104),
296 //! ACM SIGPLAN PLDI 2012, pages 335–346). It combines Clang AST
297 //! transformations, delta debugging over lines and tokens, and peephole
298 //! rewrites, and it minimizes C and C++ inputs that crash a compiler, that
299 //! are miscompiled, and that expose semantic bugs.
300 //! - **QuickCheck Shrinking:** Koen Claessen and John Hughes introduced
301 //! property-based random testing
302 //! ([QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs](https://doi.org/10.1145/351240.351266),
303 //! ICFP 2000). Property testing libraries today shrink by type through an
304 //! interface like QuickCheck's
305 //! [`shrink`](https://hackage.haskell.org/package/QuickCheck/docs/Test-QuickCheck-Arbitrary.html#v:shrink),
306 //! whose signature `shrink :: a -> [a]` yields subterms of the value's type
307 //! or simpler alternatives and defaults to `[]`, which simplifies a
308 //! counterexample over structured algebraic types.
309 //!
310 //! This package works straight on raw byte sequences.
311
312 /// Namespace holding the byte-oriented implementation.
313 pub const bytes = @import("bytes/root.zig");
314
315 /// Workspace layout derived from the caller's limits, sized so that a run in
316 /// steady state needs no further allocation.
317 pub const Capacity = bytes.Capacity;
318
319 /// Stopping condition that ended the search, `one_minimal` or
320 /// `budget_exhausted`.
321 pub const Completion = bytes.Completion;
322
323 /// Set of errors the reduction framework produces while acquiring the workspace
324 /// or checking the input.
325 pub const Error = bytes.Error;
326
327 /// Set of errors raised when the input exceeds the workspace bounds or another
328 /// run already holds the workspace.
329 pub const Exhaustion = bytes.Exhaustion;
330
331 /// Oracle's answer about one candidate, `interesting` or `uninteresting`.
332 pub const Interesting = bytes.Interesting;
333
334 /// Type of the caller's oracle function pointer.
335 pub const InterestingFn = bytes.InterestingFn;
336
337 /// Sizing constraint the caller supplies for the byte reduction workspace.
338 pub const Limits = bytes.Limits;
339
340 /// Outcome of a run, with bytes borrowed from the acquired workspace.
341 pub const Result = bytes.Result;
342
343 /// Options that control how a run executes.
344 pub const Settings = bytes.Settings;
345
346 /// Snapshot of one workspace's state, taken by value at the moment of the call.
347 pub const Status = bytes.Status;
348
349 /// Workspace, allocated up front and double-buffered, that carries reduction in
350 /// steady state.
351 pub const Storage = bytes.Storage;
352
353 /// Shortens an initial byte sequence against the caller's oracle.
354 pub const reduce = bytes.reduce;