lib/reducer/src/bytes/reduce.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! The reduction loop, the counters a run reports, and the borrowed result.
2 //!
3 //! The search looks for a shorter subsequence that still induces the failure,
4 //! by deleting adjacent chunks of bytes and asking the caller's oracle about
5 //! each result.
6 //!
7 //! ## Algorithmic Structure
8 //!
9 //! The published `ddmin` of Zeller and Hildebrandt, 2002, Figure 5, splits an
10 //! input into $n$ subsets $\Delta_1, \dots, \Delta_n$ and alternates two
11 //! phases: one tests each subset $\Delta_i$ on its own, the other tests the
12 //! complement $c \setminus \Delta_i$, with $n$ moving between 2 and $|c|$.
13 //!
14 //! This implementation departs from that in three ways:
15 //! - **Omits a separate subset-testing phase:** it runs contiguous deletion
16 //! sweeps through `without()`. Deleting one half of a two-way split leaves a
17 //! complement slice that coincides with the other half, and that case arrives
18 //! through deletion.
19 //! - **Controls search by byte chunk size:** the search starts with the chunk
20 //! at the whole length of the current sequence, which deletes the entire
21 //! input and tests the empty sequence `""`, and each later pass halves the
22 //! chunk with ceiling division, down to a chunk of 1:
23 //! $$\text{chunk} \leftarrow \lfloor \text{chunk} / 2 \rfloor + (\text{chunk} \bmod 2)$$
24 //! - **Restarts greedily at full length:** the moment the oracle answers
25 //! interesting for a candidate, that candidate replaces the current sequence,
26 //! the reduction counter goes up by one, and the chunk resets to the whole
27 //! length of the newly shortened sequence, which starts the coarse deletion
28 //! search again from the beginning.
29 //!
30 //! ## Memory Movement and Double-Buffering
31 //!
32 //! Once the workspace is acquired, the loop calls no allocator of its own.
33 //!
34 //! - **Candidate construction**: assembling a candidate in `without()` copies
35 //! bytes from the current sequence into the scratch lane, as the two pieces
36 //! `target[0..start]` and `target[start..]`.
37 //! - **Candidate acceptance**: when the oracle accepts a candidate, the two
38 //! local names swap, which is written `spare = current; current = candidate;`
39 //! in the code, and that swap of slices copies no bytes back.
40 //!
41 //! `Storage.current` and `Storage.candidate` are fixed regions of the backing
42 //! buffer, so swapping the local names leaves the accepted witness in
43 //! `Result.bytes` sitting in either one of them.
44 //!
45 //! The loop allocates nothing, while a run as a whole allocates whatever the
46 //! caller's oracle allocates.
47
48 const std = @import("std");
49 const model = @import("model.zig");
50 const storage_mod = @import("storage.zig");
51
52 /// Outcome of one run, borrowing its memory from the acquired workspace.
53 ///
54 /// ## Lifetime and Borrowing Contract
55 ///
56 /// The `bytes` slice points into the backing buffer of `storage`, and it stays
57 /// readable while the result is still live and the workspace has been neither
58 /// reused nor torn down.
59 ///
60 /// `deinit()` gives up this run's lease by calling `storage.release()`, which
61 /// returns the workspace to steady and idle so a later run can acquire it, and
62 /// it moves the workspace no closer to teardown and frees no memory.
63 ///
64 /// `deinit()` also clears the result's own fields, setting `bytes = &.{}`,
65 /// `attempts = 0`, `reductions = 0`, and `completion = .budget_exhausted`, and
66 /// it is called exactly once per result.
67 ///
68 /// A caller that needs the reduced bytes after the workspace is reused or torn
69 /// down, or that wants to feed them in as the next run's input on the same
70 /// workspace, copies them into a buffer of its own before calling `deinit()`.
71 pub const Result = struct {
72 /// Borrowed slice holding the reduced byte sequence, pointing into the
73 /// workspace.
74 bytes: []const u8,
75
76 /// Count of every oracle call the run made, including the first call, which
77 /// checks the caller's own input. On a live result, before `deinit()`, the
78 /// count is at least 1. `deinit()` sets it to 0.
79 attempts: usize,
80
81 /// Count of the candidate deletions the oracle accepted. Each accepted
82 /// reduction makes the witness strictly shorter. `deinit()` sets it to 0.
83 reductions: usize,
84
85 /// Search outcome status flag holding `.one_minimal` when every single-byte
86 /// occurrence deletion was put to the oracle and rejected. It holds
87 /// `.budget_exhausted` when the run stopped because `attempts` reached
88 /// `max_attempts` before the single-byte sweep finished. `deinit()` sets it
89 /// to `.budget_exhausted`.
90 completion: model.Completion,
91
92 /// Pointer to the workspace that owns the memory `bytes` refers to.
93 storage: *storage_mod.Storage,
94
95 /// Gives up this run's lease on the workspace, returning it to steady and
96 /// idle.
97 ///
98 /// After the call, `bytes` is an empty slice, the counters are zero, and
99 /// the workspace can be acquired again.
100 ///
101 /// ## Safety
102 ///
103 /// - It is called exactly once per result.
104 /// - One owner holds a given result and makes no shallow copy of it.
105 /// - The result's public bookkeeping fields stay as the run left them.
106 pub fn deinit(self: *Result) void {
107 self.storage.release();
108 self.bytes = &.{};
109 self.attempts = 0;
110 self.reductions = 0;
111 self.completion = .budget_exhausted;
112 }
113 };
114
115 /// Shortens an initial byte sequence against the caller's failure predicate.
116 ///
117 /// ## Preconditions
118 ///
119 /// - `storage` sits in the `alloc_phase.capacity.Phase.steady` phase, which
120 /// `storage.activate()` reaches after `Storage.init()`.
121 /// - No other run holds `storage`, so `storage.status().in_use` is false.
122 /// - `initial.len` is at most `storage.status().max_input_bytes`.
123 /// - The memory of `initial` stays valid and unchanged for the whole call.
124 /// - The oracle answers interesting for `initial`.
125 /// - `settings.max_attempts` is above 0.
126 ///
127 /// ## Execution Semantics and Error Isolation
128 ///
129 /// 1. A `settings.max_attempts` of 0 returns `error.AttemptBudgetExhausted` at
130 /// once, without reaching for the workspace, so an earlier run's hold on the
131 /// workspace stands untouched.
132 /// 2. The call then acquires the workspace. A workspace another run already
133 /// holds returns `error.ReductionStorageInUse`, and an `initial.len` above
134 /// the capacity returns `error.InputCapacityExceeded`. Both return before
135 /// any workspace byte changes, so a call refused as busy leaves an earlier
136 /// live `Result` holding its lease.
137 /// 3. Once the workspace is acquired, `errdefer storage.release()` gives up
138 /// this run's lease on any later failure. Giving up the lease restores
139 /// neither the scratch bytes the run overwrote nor any side effect the
140 /// callback produced.
141 /// 4. The oracle calls start with attempt 1 on `initial`, where the oracle
142 /// receives the caller's own slice before any copy. An `initial` the oracle
143 /// answers uninteresting for returns `error.InitialInputUninteresting` and
144 /// gives up the lease.
145 /// 5. The call then tests chunk deletions of the current chunk size, starting
146 /// at `current.len` and halving with ceiling division down to 1. Each trial
147 /// candidate is built in the scratch lane by copying the bytes that survive
148 /// the deletion, through `without()`.
149 /// 6. When the oracle accepts a candidate, the locals `current` and `spare`
150 /// swap without copying bytes back, `reductions` goes up by one, and `chunk`
151 /// resets to the new `current.len`.
152 /// 7. The call terminates on one of three conditions:
153 /// - A full pass at a chunk of 1 that finishes with every unit deletion
154 /// rejected sets `completion = .one_minimal`, and that final sweep may
155 /// finish on the exact last allowed attempt.
156 /// - A `current.len` of 0 sets `completion = .one_minimal`.
157 /// - An `attempts` count that reaches `settings.max_attempts` leaves
158 /// `completion = .budget_exhausted`.
159 ///
160 /// ## Memory and Allocation
161 ///
162 /// Once the workspace is acquired, the loop calls no allocator of its own, the
163 /// workspace owns every byte the run touches, and the memory the callback
164 /// allocates along with its side effects sit outside that account.
165 ///
166 /// ## Errors
167 ///
168 /// It returns `Error`, which is `Exhaustion || InputError`, or any error the
169 /// oracle returned. Only an error raised after the workspace was acquired gives
170 /// up the lease.
171 ///
172 /// ## Example
173 ///
174 /// ```zig
175 /// const std = @import("std");
176 /// const reducer = @import("reducer");
177 ///
178 /// const Context = struct { needle: []const u8 };
179 ///
180 /// fn checkContains(input: []const u8, ctx_ptr: *anyopaque) anyerror!reducer.Interesting {
181 /// const ctx: *const Context = @ptrCast(@alignCast(ctx_ptr));
182 /// return if (std.mem.indexOf(u8, input, ctx.needle) != null)
183 /// .interesting
184 /// else
185 /// .uninteresting;
186 /// }
187 ///
188 /// test "basic reduce invocation" {
189 /// const allocator = std.testing.allocator;
190 /// const initial_input = "prefix_ERR_suffix";
191 /// var storage = try reducer.Storage.init(allocator, .{
192 /// .max_input_bytes = initial_input.len,
193 /// });
194 /// defer storage.deinit(allocator);
195 /// storage.activate();
196 ///
197 /// var ctx = Context{ .needle = "ERR" };
198 /// var res = try reducer.reduce(&storage, initial_input, checkContains, &ctx, .{});
199 /// defer res.deinit();
200 ///
201 /// try std.testing.expectEqualSlices(u8, "ERR", res.bytes);
202 /// try std.testing.expectEqual(reducer.Completion.one_minimal, res.completion);
203 /// }
204 /// ```
205 pub fn reduce(
206 storage: *storage_mod.Storage,
207 initial: []const u8,
208 interesting_fn: model.InterestingFn,
209 context: *anyopaque,
210 settings: model.Settings,
211 ) anyerror!Result {
212 if (settings.max_attempts == 0) return error.AttemptBudgetExhausted;
213 const regions = try storage.acquire(initial.len);
214 errdefer storage.release();
215 std.debug.assert(regions.current.len == initial.len);
216 std.debug.assert(regions.candidate.len >= initial.len -| 1);
217
218 var attempts: usize = 1;
219 if (try interesting_fn(initial, context) == .uninteresting) {
220 return error.InitialInputUninteresting;
221 }
222
223 @memcpy(regions.current, initial);
224 var current = regions.current;
225 var spare = regions.candidate;
226 var reductions: usize = 0;
227 var chunk = current.len;
228 var completion: model.Completion =
229 if (current.len == 0) .one_minimal else .budget_exhausted;
230 while (chunk > 0 and attempts < settings.max_attempts) {
231 var improved = false;
232 var sweep_finished = false;
233 var start: usize = 0;
234 while (start < current.len and attempts < settings.max_attempts) {
235 const end = if (chunk > current.len - start) current.len else start + chunk;
236 const candidate = without(spare, current, start, end);
237
238 attempts += 1;
239 const candidate_status = try interesting_fn(candidate, context);
240 if (candidate_status == .interesting) {
241 std.debug.assert(candidate.len < current.len);
242 spare = current;
243 current = candidate;
244 reductions += 1;
245 chunk = current.len;
246 improved = true;
247 if (current.len == 0) completion = .one_minimal;
248 break;
249 }
250
251 if (end == current.len) {
252 sweep_finished = true;
253 break;
254 }
255 start += chunk;
256 }
257
258 if (improved) continue;
259 if (chunk == 1) {
260 if (sweep_finished) completion = .one_minimal;
261 break;
262 }
263 if (!sweep_finished) break;
264 chunk = chunk / 2 + chunk % 2;
265 }
266
267 std.debug.assert(attempts <= settings.max_attempts);
268 std.debug.assert(current.len <= initial.len);
269 if (completion == .one_minimal and current.len > 0) {
270 std.debug.assert(chunk == 1);
271 }
272 return makeResult(storage, current, attempts, reductions, completion);
273 }
274
275 fn makeResult(
276 storage: *storage_mod.Storage,
277 bytes: []const u8,
278 attempts: usize,
279 reductions: usize,
280 completion: model.Completion,
281 ) Result {
282 std.debug.assert(storage.status().in_use);
283 std.debug.assert(attempts > 0);
284 return .{
285 .bytes = bytes,
286 .attempts = attempts,
287 .reductions = reductions,
288 .completion = completion,
289 .storage = storage,
290 };
291 }
292
293 fn without(target: []u8, source: []const u8, start: usize, end: usize) []u8 {
294 std.debug.assert(start <= end);
295 std.debug.assert(end <= source.len);
296 std.debug.assert(target.len >= source.len - (end - start));
297 const candidate = target[0 .. source.len - (end - start)];
298 @memcpy(candidate[0..start], source[0..start]);
299 @memcpy(candidate[start..], source[end..]);
300 return candidate;
301 }