lib/reducer/src/bytes/root.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

 1 //! The search deletes bytes from an input that reproduces a defect until a
 2 //! smaller input still reproduces it, carrying out *test-case reduction* over
 3 //! byte sequences. It works on any `[]const u8`, and it finds a shorter
 4 //! *subsequence* of the input (a sequence obtained from another by deleting
 5 //! bytes and keeping the order of the rest) that still reproduces the failure.
 6 //! Two properties bound a run. First, the *attempt budget*, the ceiling on the
 7 //! number of oracle calls (`Settings.max_attempts`), caps the work. Second, a
 8 //! given input with a given *oracle*, the caller's function (`InterestingFn`)
 9 //! that answers whether one candidate still reproduces the defect, yields the
10 //! same result every time. The search works on the raw bytes of the input.
11 //!
12 //! ## Module Organization
13 //!
14 //! Four internal modules divide the work:
15 //! - `capacity` works out the upper bound on the memory a run needs and catches
16 //!   arithmetic overflow in that sum.
17 //! - `model` declares the error sets, the oracle type `InterestingFn`, the
18 //!   status flag the search reports, and the settings a run reads.
19 //! - `storage` holds the *workspace* (the one byte allocation `Storage` makes
20 //!   and reuses for every run), allocated up front and double-buffered, and
21 //!   checks each lifecycle step against the *phase* recorded for `alloc_phase`.
22 //! - `reduction` runs the search itself, deleting a *chunk* at a time (the
23 //!   number of adjacent bytes one candidate deletes) and halving the chunk
24 //!   greedily.
25 //!
26 //! ## Dataflow Pipeline
27 //!
28 //! The five calls of a run connect in one order:
29 //! 1. `Storage.init(allocator, limits)` takes the caller's *limits* (the
30 //!    longest input it will submit), derives the layout *capacity* itself, and
31 //!    allocates the backing memory once.
32 //! 2. `storage.activate()` seals the workspace into steady state.
33 //! 3. `reduce()` acquires the workspace regions, runs the search with no
34 //!    backing allocation of its own, and returns a `Result` borrowing from the
35 //!    workspace (`Result.bytes` points into the workspace without owning
36 //!    memory).
37 //! 4. `Result.deinit()` gives up the *lease* (one run's exclusive hold on the
38 //!    workspace, recorded by `in_use`), returning the workspace to steady and
39 //!    *idle* so the next run can acquire it.
40 //! 5. `storage.deinit(allocator)` tears down the idle workspace and frees the
41 //!    backing memory.
42 
43 /// Module holding the capacity derivation and the limits type.
44 pub const capacity = @import("capacity.zig");
45 
46 /// Module holding the data types, the oracle function interface, the error
47 /// sets, and the execution settings.
48 pub const model = @import("model.zig");
49 
50 /// Module holding the reduction loop, the execution counters, and the borrowed
51 /// result.
52 pub const reduction = @import("reduce.zig");
53 
54 /// Module holding the workspace, allocated up front and double-buffered, and
55 /// the phase-checked lifecycle around it.
56 pub const storage = @import("storage.zig");
57 
58 /// Workspace layout derived from the caller's limits, sized so that a run in
59 /// steady state needs no further allocation.
60 pub const Capacity = capacity.Capacity;
61 
62 /// Stopping condition that ended the search, `one_minimal` or
63 /// `budget_exhausted`.
64 pub const Completion = model.Completion;
65 
66 /// Sizing constraint the caller supplies for the byte reduction workspace.
67 pub const Limits = capacity.Limits;
68 
69 /// Set of errors the reduction framework produces while acquiring the workspace
70 /// or checking the input.
71 pub const Error = model.Error;
72 
73 /// Set of errors raised when the input exceeds the workspace bounds or another
74 /// run already holds the workspace.
75 pub const Exhaustion = model.Exhaustion;
76 
77 /// Oracle's answer about one candidate, `interesting` or `uninteresting`.
78 pub const Interesting = model.Interesting;
79 
80 /// Type of the caller's oracle function pointer.
81 pub const InterestingFn = model.InterestingFn;
82 
83 /// Options that control how a run executes.
84 pub const Settings = model.Settings;
85 
86 /// Outcome of a run, with bytes borrowed from the acquired workspace.
87 pub const Result = reduction.Result;
88 
89 /// Snapshot of one workspace's state, taken by value at the moment of the call.
90 pub const Status = storage.Status;
91 
92 /// Workspace, allocated up front and double-buffered, that carries reduction in
93 /// steady state.
94 pub const Storage = storage.Storage;
95 
96 /// Shortens an initial byte sequence against the caller's oracle.
97 pub const reduce = reduction.reduce;