lib/reducer/src/bytes/model.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 //! Data model for byte reduction: the error types, the oracle interface, and
  2 //! the settings of a run. A run works against the caller's function that
  3 //! answers whether one candidate still reproduces the defect, the *oracle*,
  4 //! whose type is `InterestingFn`. The oracle answers *interesting* when a
  5 //! candidate (one shorter byte sequence built by deleting a run of bytes from
  6 //! the current sequence and handed to the oracle) satisfies the failure
  7 //! property under investigation, and answers *uninteresting* when the candidate
  8 //! does not show that failure.
  9 //!
 10 //! ## Error Classification
 11 //!
 12 //! The errors the package raises itself fall into two sets:
 13 //! - `Exhaustion` covers a resource bound and a conflicting use of the
 14 //!   workspace: `InputCapacityExceeded` and `ReductionStorageInUse`.
 15 //! - `InputError` covers a broken contract and an insufficient budget:
 16 //!   `AttemptBudgetExhausted` and `InitialInputUninteresting`.
 17 //!
 18 //! The `Error` alias lists those framework errors, while `reduce()` returns
 19 //! `anyerror!Result`, because a caller's callback may return any error at all,
 20 //! including one whose name matches a standard error name. An error the oracle
 21 //! returns travels straight out through `reduce()`, ending the run and giving
 22 //! up the lease this call acquired.
 23 
 24 /// This error set gathers the errors the reduction framework produces directly.
 25 /// The set leaves out the errors a caller's predicate returns, which `reduce()`
 26 /// passes through as `anyerror`, so that error travels outward to the caller.
 27 pub const Error = Exhaustion || InputError;
 28 
 29 /// These failures arise from the workspace bounds or from another run already
 30 /// holding the workspace.
 31 pub const Exhaustion = error{
 32     /// The input slice is longer than the `Limits.max_input_bytes` the
 33     /// `Storage` instance was allocated for.
 34     InputCapacityExceeded,
 35 
 36     /// The `Storage` instance is already held by a running reduction or by a
 37     /// `Result` whose `deinit()` has yet to be called, so a reentrant call, and
 38     /// a second call made while the first run's result is still live, are both
 39     /// refused before any workspace byte changes.
 40     ReductionStorageInUse,
 41 };
 42 
 43 /// These failures arise from the state of the input or from too small an
 44 /// attempt budget.
 45 pub const InputError = error{
 46     /// `Settings.max_attempts` is zero. The check runs before the workspace is
 47     /// acquired, so no workspace memory is taken or written.
 48     AttemptBudgetExhausted,
 49 
 50     /// The oracle answered uninteresting for the initial input. A run starts
 51     /// from a witness, an input that already reproduces the failure under
 52     /// investigation.
 53     InitialInputUninteresting,
 54 };
 55 
 56 /// Oracle's answer about one candidate byte slice.
 57 pub const Interesting = enum {
 58     /// The candidate reproduces the failure, or shows the property under
 59     /// investigation, so the search takes this shorter candidate as its new
 60     /// current sequence.
 61     interesting,
 62 
 63     /// The candidate does not show the property under investigation, so the
 64     /// search drops this candidate and tries another deletion.
 65     uninteresting,
 66 };
 67 
 68 /// Status recording which stopping condition the search reached.
 69 pub const Completion = enum {
 70     /// Every occurrence deletion of one byte from the returned output was put
 71     /// to the oracle and came back uninteresting. Given a deterministic oracle
 72     /// that decides from the candidate's content alone, no single byte comes
 73     /// out of the result while the result stays interesting. 1-minimality is a
 74     /// local guarantee, and it leaves open whether the result is globally
 75     /// shortest.
 76     one_minimal,
 77 
 78     /// The number of oracle calls reached `Settings.max_attempts` before the
 79     /// single-byte sweep could finish. The returned slice is an interesting
 80     /// subsequence of the initial input. The 1-minimality guarantee is given
 81     /// up, because the search stopped before trying every single-byte deletion,
 82     /// and that holds even when the result happens to be minimal.
 83     budget_exhausted,
 84 };
 85 
 86 /// Type of the caller's oracle function pointer.
 87 ///
 88 /// ## Calling Convention and Contract
 89 ///
 90 /// - **Candidate slice:** on attempt 1 the callback receives the caller's own
 91 ///   `initial` slice, before any copy. On every later attempt it receives a
 92 ///   slice into the scratch lane, and the next iteration overwrites those
 93 ///   bytes, so the callback retains no slice into a candidate buffer past its
 94 ///   return.
 95 /// - **Context pointer:** the caller keeps the context alive for the whole
 96 ///   synchronous call of `reduce()`, and the cast `@ptrCast(@alignCast(ctx))`
 97 ///   matches the real type and alignment of what the pointer points at.
 98 /// - **Answers and errors:** the callback answers interesting for the specific
 99 ///   failure or symptom under investigation and uninteresting for everything
100 ///   else, which covers a candidate that fails to parse, holds invalid UTF-8,
101 ///   or hits an unrelated error. Returning a Zig error ends the run at once.
102 /// - **Side effects and determinism:** a side effect such as logging or the
103 ///   callback's own scratch allocation is allowed as long as the answer for a
104 ///   given candidate stays the same. The minimality claims rest on an oracle
105 ///   that is deterministic and decides from the candidate's content alone,
106 ///   which is an assumption about the caller's code.
107 pub const InterestingFn = *const fn ([]const u8, *anyopaque) anyerror!Interesting;
108 
109 /// Options that control how a run executes.
110 pub const Settings = struct {
111     /// Largest number of oracle calls a run may make, counting the call on the
112     /// caller's own input. It defaults to `10_000`.
113     ///
114     /// - Zero returns `error.AttemptBudgetExhausted` before the workspace is
115     ///   acquired.
116     /// - One, with a nonempty interesting input, ends the run after attempt 1
117     ///   with `Completion.budget_exhausted` and keeps the input as it arrived.
118     /// - One, with an empty interesting input, ends the run with
119     ///   `Completion.one_minimal`, because a zero-length input has no deletion
120     ///   to try.
121     ///
122     /// The ceiling counts oracle calls alone: bytes copied, memory the callback
123     /// allocates, and wall-clock time all sit outside it, so a callback that
124     /// loops forever leaves `reduce()` running forever.
125     max_attempts: usize = 10_000,
126 };