tiny.reducer.bytes.reduction

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 about5//! each result.6//!7//! ## Algorithmic Structure8//!9//! The published `ddmin` of Zeller and Hildebrandt, 2002, Figure 5, splits an10//! input into $n$ subsets $\Delta_1, \dots, \Delta_n$ and alternates two11//! phases: one tests each subset $\Delta_i$ on its own, the other tests the12//! 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 deletion16//!   sweeps through `without()`. Deleting one half of a two-way split leaves a17//!   complement slice that coincides with the other half, and that case arrives18//!   through deletion.19//! - **Controls search by byte chunk size:** the search starts with the chunk20//!   at the whole length of the current sequence, which deletes the entire21//!   input and tests the empty sequence `""`, and each later pass halves the22//!   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 answers25//!   interesting for a candidate, that candidate replaces the current sequence,26//!   the reduction counter goes up by one, and the chunk resets to the whole27//!   length of the newly shortened sequence, which starts the coarse deletion28//!   search again from the beginning.29//!30//! ## Memory Movement and Double-Buffering31//!32//! Once the workspace is acquired, the loop calls no allocator of its own.33//!34//! - **Candidate construction**: assembling a candidate in `without()` copies35//!   bytes from the current sequence into the scratch lane, as the two pieces36//!   `target[0..start]` and `target[start..]`.37//! - **Candidate acceptance**: when the oracle accepts a candidate, the two38//!   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 backing42//! buffer, so swapping the local names leaves the accepted witness in43//! `Result.bytes` sitting in either one of them.44//!45//! The loop allocates nothing, while a run as a whole allocates whatever the46//! caller's oracle allocates.4748const std = @import("std");49const model = @import("model.zig");50const storage_mod = @import("storage.zig");5152/// Outcome of one run, borrowing its memory from the acquired workspace.53///54/// ## Lifetime and Borrowing Contract55///56/// The `bytes` slice points into the backing buffer of `storage`, and it stays57/// readable while the result is still live and the workspace has been neither58/// reused nor torn down.59///60/// `deinit()` gives up this run's lease by calling `storage.release()`, which61/// returns the workspace to steady and idle so a later run can acquire it, and62/// 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`, and66/// it is called exactly once per result.67///68/// A caller that needs the reduced bytes after the workspace is reused or torn69/// down, or that wants to feed them in as the next run's input on the same70/// workspace, copies them into a buffer of its own before calling `deinit()`.71pub const Result = struct {72    /// Borrowed slice holding the reduced byte sequence, pointing into the73    /// workspace.74    bytes: []const u8,7576    /// Count of every oracle call the run made, including the first call, which77    /// checks the caller's own input. On a live result, before `deinit()`, the78    /// count is at least 1. `deinit()` sets it to 0.79    attempts: usize,8081    /// Count of the candidate deletions the oracle accepted. Each accepted82    /// reduction makes the witness strictly shorter. `deinit()` sets it to 0.83    reductions: usize,8485    /// Search outcome status flag holding `.one_minimal` when every single-byte86    /// occurrence deletion was put to the oracle and rejected. It holds87    /// `.budget_exhausted` when the run stopped because `attempts` reached88    /// `max_attempts` before the single-byte sweep finished. `deinit()` sets it89    /// to `.budget_exhausted`.90    completion: model.Completion,9192    /// Pointer to the workspace that owns the memory `bytes` refers to.93    storage: *storage_mod.Storage,9495    /// Gives up this run's lease on the workspace, returning it to steady and96    /// idle.97    ///98    /// After the call, `bytes` is an empty slice, the counters are zero, and99    /// the workspace can be acquired again.100    ///101    /// ## Safety102    ///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};114115/// Shortens an initial byte sequence against the caller's failure predicate.116///117/// ## Preconditions118///119/// - `storage` sits in the `alloc_phase.capacity.Phase.steady` phase, which120///   `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 Isolation128///129/// 1. A `settings.max_attempts` of 0 returns `error.AttemptBudgetExhausted` at130///    once, without reaching for the workspace, so an earlier run's hold on the131///    workspace stands untouched.132/// 2. The call then acquires the workspace. A workspace another run already133///    holds returns `error.ReductionStorageInUse`, and an `initial.len` above134///    the capacity returns `error.InputCapacityExceeded`. Both return before135///    any workspace byte changes, so a call refused as busy leaves an earlier136///    live `Result` holding its lease.137/// 3. Once the workspace is acquired, `errdefer storage.release()` gives up138///    this run's lease on any later failure. Giving up the lease restores139///    neither the scratch bytes the run overwrote nor any side effect the140///    callback produced.141/// 4. The oracle calls start with attempt 1 on `initial`, where the oracle142///    receives the caller's own slice before any copy. An `initial` the oracle143///    answers uninteresting for returns `error.InitialInputUninteresting` and144///    gives up the lease.145/// 5. The call then tests chunk deletions of the current chunk size, starting146///    at `current.len` and halving with ceiling division down to 1. Each trial147///    candidate is built in the scratch lane by copying the bytes that survive148///    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 deletion154///      rejected sets `completion = .one_minimal`, and that final sweep may155///      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` leaves158///      `completion = .budget_exhausted`.159///160/// ## Memory and Allocation161///162/// Once the workspace is acquired, the loop calls no allocator of its own, the163/// workspace owns every byte the run touches, and the memory the callback164/// allocates along with its side effects sit outside that account.165///166/// ## Errors167///168/// It returns `Error`, which is `Exhaustion || InputError`, or any error the169/// oracle returned. Only an error raised after the workspace was acquired gives170/// up the lease.171///172/// ## Example173///174/// ```zig175/// 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///         .interesting184///     else185///         .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/// ```205pub 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);217218    var attempts: usize = 1;219    if (try interesting_fn(initial, context) == .uninteresting) {220        return error.InitialInputUninteresting;221    }222223    @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);237238            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            }250251            if (end == current.len) {252                sweep_finished = true;253                break;254            }255            start += chunk;256        }257258        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    }266267    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}274275fn 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}292293fn 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}

1/// Module holding the reduction loop, the execution counters, and the borrowed2/// result.3pub const reduction = @import("reduce.zig");