tiny.reducer.reduce

1/// Shortens an initial byte sequence against the caller's failure predicate.2///3/// ## Preconditions4///5/// - `storage` sits in the `alloc_phase.capacity.Phase.steady` phase, which6///   `storage.activate()` reaches after `Storage.init()`.7/// - No other run holds `storage`, so `storage.status().in_use` is false.8/// - `initial.len` is at most `storage.status().max_input_bytes`.9/// - The memory of `initial` stays valid and unchanged for the whole call.10/// - The oracle answers interesting for `initial`.11/// - `settings.max_attempts` is above 0.12///13/// ## Execution Semantics and Error Isolation14///15/// 1. A `settings.max_attempts` of 0 returns `error.AttemptBudgetExhausted` at16///    once, without reaching for the workspace, so an earlier run's hold on the17///    workspace stands untouched.18/// 2. The call then acquires the workspace. A workspace another run already19///    holds returns `error.ReductionStorageInUse`, and an `initial.len` above20///    the capacity returns `error.InputCapacityExceeded`. Both return before21///    any workspace byte changes, so a call refused as busy leaves an earlier22///    live `Result` holding its lease.23/// 3. Once the workspace is acquired, `errdefer storage.release()` gives up24///    this run's lease on any later failure. Giving up the lease restores25///    neither the scratch bytes the run overwrote nor any side effect the26///    callback produced.27/// 4. The oracle calls start with attempt 1 on `initial`, where the oracle28///    receives the caller's own slice before any copy. An `initial` the oracle29///    answers uninteresting for returns `error.InitialInputUninteresting` and30///    gives up the lease.31/// 5. The call then tests chunk deletions of the current chunk size, starting32///    at `current.len` and halving with ceiling division down to 1. Each trial33///    candidate is built in the scratch lane by copying the bytes that survive34///    the deletion, through `without()`.35/// 6. When the oracle accepts a candidate, the locals `current` and `spare`36///    swap without copying bytes back, `reductions` goes up by one, and `chunk`37///    resets to the new `current.len`.38/// 7. The call terminates on one of three conditions:39///    - A full pass at a chunk of 1 that finishes with every unit deletion40///      rejected sets `completion = .one_minimal`, and that final sweep may41///      finish on the exact last allowed attempt.42///    - A `current.len` of 0 sets `completion = .one_minimal`.43///    - An `attempts` count that reaches `settings.max_attempts` leaves44///      `completion = .budget_exhausted`.45///46/// ## Memory and Allocation47///48/// Once the workspace is acquired, the loop calls no allocator of its own, the49/// workspace owns every byte the run touches, and the memory the callback50/// allocates along with its side effects sit outside that account.51///52/// ## Errors53///54/// It returns `Error`, which is `Exhaustion || InputError`, or any error the55/// oracle returned. Only an error raised after the workspace was acquired gives56/// up the lease.57///58/// ## Example59///60/// ```zig61/// const std = @import("std");62/// const reducer = @import("reducer");63///64/// const Context = struct { needle: []const u8 };65///66/// fn checkContains(input: []const u8, ctx_ptr: *anyopaque) anyerror!reducer.Interesting {67///     const ctx: *const Context = @ptrCast(@alignCast(ctx_ptr));68///     return if (std.mem.indexOf(u8, input, ctx.needle) != null)69///         .interesting70///     else71///         .uninteresting;72/// }73///74/// test "basic reduce invocation" {75///     const allocator = std.testing.allocator;76///     const initial_input = "prefix_ERR_suffix";77///     var storage = try reducer.Storage.init(allocator, .{78///         .max_input_bytes = initial_input.len,79///     });80///     defer storage.deinit(allocator);81///     storage.activate();82///83///     var ctx = Context{ .needle = "ERR" };84///     var res = try reducer.reduce(&storage, initial_input, checkContains, &ctx, .{});85///     defer res.deinit();86///87///     try std.testing.expectEqualSlices(u8, "ERR", res.bytes);88///     try std.testing.expectEqual(reducer.Completion.one_minimal, res.completion);89/// }90/// ```91pub fn reduce(92    storage: *storage_mod.Storage,93    initial: []const u8,94    interesting_fn: model.InterestingFn,95    context: *anyopaque,96    settings: model.Settings,97) anyerror!Result {98    if (settings.max_attempts == 0) return error.AttemptBudgetExhausted;99    const regions = try storage.acquire(initial.len);100    errdefer storage.release();101    std.debug.assert(regions.current.len == initial.len);102    std.debug.assert(regions.candidate.len >= initial.len -| 1);103104    var attempts: usize = 1;105    if (try interesting_fn(initial, context) == .uninteresting) {106        return error.InitialInputUninteresting;107    }108109    @memcpy(regions.current, initial);110    var current = regions.current;111    var spare = regions.candidate;112    var reductions: usize = 0;113    var chunk = current.len;114    var completion: model.Completion =115        if (current.len == 0) .one_minimal else .budget_exhausted;116    while (chunk > 0 and attempts < settings.max_attempts) {117        var improved = false;118        var sweep_finished = false;119        var start: usize = 0;120        while (start < current.len and attempts < settings.max_attempts) {121            const end = if (chunk > current.len - start) current.len else start + chunk;122            const candidate = without(spare, current, start, end);123124            attempts += 1;125            const candidate_status = try interesting_fn(candidate, context);126            if (candidate_status == .interesting) {127                std.debug.assert(candidate.len < current.len);128                spare = current;129                current = candidate;130                reductions += 1;131                chunk = current.len;132                improved = true;133                if (current.len == 0) completion = .one_minimal;134                break;135            }136137            if (end == current.len) {138                sweep_finished = true;139                break;140            }141            start += chunk;142        }143144        if (improved) continue;145        if (chunk == 1) {146            if (sweep_finished) completion = .one_minimal;147            break;148        }149        if (!sweep_finished) break;150        chunk = chunk / 2 + chunk % 2;151    }152153    std.debug.assert(attempts <= settings.max_attempts);154    std.debug.assert(current.len <= initial.len);155    if (completion == .one_minimal and current.len > 0) {156        std.debug.assert(chunk == 1);157    }158    return makeResult(storage, current, attempts, reductions, completion);159}

1/// Shortens an initial byte sequence against the caller's oracle.2pub const reduce = bytes.reduce;