tiny.reducer

Overview · API · Code relationships · Verification · Audit

Overview

Starting from an input that reproduces a defect and deleting runs of bytes from it until a smaller input still reproduces it is test-case reduction.

The example running through this doc is the input "abcXYZdef" with a function answering whether a candidate reproduces the defect, the oracle, that answers interesting for any candidate containing "XYZ":

1const std = @import("std");2const reducer = @import("reducer");34const Context = struct { needle: []const u8 };56fn checkNeedle(input: []const u8, ptr: *anyopaque) anyerror!reducer.Interesting {7    const ctx: *const Context = @ptrCast(@alignCast(ptr));8    return if (std.mem.indexOf(u8, input, ctx.needle) != null)9        .interesting10    else11        .uninteresting;12}1314test "basic reducer demonstration" {15    const allocator = std.testing.allocator;16    const initial = "abcXYZdef";17    var ctx = Context{ .needle = "XYZ" };1819    var storage = try reducer.Storage.init(allocator, .{ .max_input_bytes = initial.len });20    defer storage.deinit(allocator);21    storage.activate();2223    var result = try reducer.reduce(&storage, initial, checkNeedle, &ctx, .{});24    defer result.deinit();2526    try std.testing.expectEqualSlices(u8, "XYZ", result.bytes);27    try std.testing.expectEqual(reducer.Completion.one_minimal, result.completion);28}

Once the workspace (the one byte allocation Storage makes up front and reuses for every run) is initialized and sealed into steady state, its owner allocates nothing further, and the reduction loop itself calls no allocator.

The Oracle Contract

The caller hands the condition under test to reduce() as a callback whose type is InterestingFn:

1fn interesting(candidate: []const u8, context: *anyopaque) anyerror!Interesting

The callback answers interesting when the candidate (one shorter byte sequence built by deleting a run of bytes from the current sequence and handed to the oracle) reproduces the condition under test and uninteresting when it does not, which covers a candidate that fails to parse, holds invalid UTF-8, or runs into an unrelated error. A caller's oracle answers interesting for the one symptom under investigation, and a candidate that crashes or errors in some other way is uninteresting. Returning a Zig error from the callback ends the run at once: the error travels out to the caller, and this run's lease on the workspace is given up.

The search works on raw bytes, so a deletion falls at any byte offset and respects no line of text and no character boundary. On attempt 1 (the call of the oracle on the caller's own input), the callback receives the caller's own initial slice, so that memory stays valid and unchanged for the whole run. On every later attempt the callback receives a slice into the scratch lane (the fixed part of the workspace where each candidate is assembled), whose bytes the next iteration overwrites, so the callback retains no candidate slice past its return.

The context pointer stays alive for the whole synchronous call, and the cast the callback performs on it matches the real type and alignment of what it points at. Side effects such as logging or the callback's own scratch allocation are allowed as long as the answer for a given candidate stays the same. The minimality claims below rest on an oracle that is deterministic and decides from the candidate's content alone, which is an assumption about the caller's code.

Reduction searches the space of inputs for a smaller one that still reproduces the defect. Fault injection answers a different question: lib/tripwire fires simulated error sites and needs its own postcondition assertions to check that rollback happened.

Deletion Search and Minimality

Dropping the byte at index $i$ of a sequence $x$ whose length is $n$, for $0\le i<n$, and joining the two half-open pieces x[0..i] and x[i+1..n] is occurrence deletion, producing a shorter subsequence:

At $i=0$ the leading piece x[0..0] is empty, and at $i=n-1$ the trailing piece x[n..n] is empty.

An interesting sequence where every single-byte deletion from it was tried and came back uninteresting is 1-minimal under that oracle:

An empty sequence has no index to delete, so an empty interesting input is already 1-minimal.

Differences from Textbook ddmin

Andreas Zeller and Ralf Hildebrandt formulated delta debugging (ddmin), which splits an input into $n$ subsets ${\mathrm{\Delta }}_1,\dots ,{\mathrm{\Delta }}_n$ and alternates between testing one subset ${\mathrm{\Delta }}_i$ alone and testing its complement $c_x\setminus {\mathrm{\Delta }}_i$, moving $n$ between 2 and $|c_x|$ (Simplifying and Isolating Failure-Inducing Input, IEEE TSE 2002, Figure 5).

This package differs from that formulation in three ways:

• Deletion sweeps: the search runs contiguous deletion sweeps (passes over the current sequence at a fixed chunk, from its start to its end) through without() and has no separate phase that tests one subset alone. Deleting one half of a two-way split leaves the other half behind, so that case arrives through deletion.
• Chunk halving: the search tracks a chunk (the number of adjacent bytes one candidate deletes) in bytes where ddmin tracks a count of subsets. It starts with the chunk at the whole length of the current sequence (the shortest sequence the oracle has accepted so far, which the search deletes from next), which tests the empty sequence "", and halves the chunk with ceiling division down to 1:

• Greedy restart: accepting a candidate is a greedy restart that records a reduction, one candidate accepted by the oracle that replaces the current sequence and is strictly shorter. The current sequence becomes that candidate, reductions goes up by one, and the chunk resets to the whole length of the new current sequence.

Building a candidate copies bytes into the scratch lane through without(), and accepting one swaps which lane each of the two local names refers to, so no bytes are copied back.

Trace: abcXYZdef to XYZ

For the input "abcXYZdef", whose length $N$ is 9, with an oracle requiring "XYZ", the search runs 14 attempts and accepts 2 reductions:

Every single-byte deletion at chunk 1 came back uninteresting, so the run ends with Completion.one_minimal.

Local and Global Minimality

1-minimality says that no single byte comes out of the result on its own. It leaves open whether some shorter interesting sequence exists, which would be globally shortest (no shorter interesting sequence existing at all).

A worked case: the input "ABCD" with an oracle that accepts any sequence containing 'A' or containing "CD":

• "ABCD" is interesting.
• At chunk 2, deleting "AB" tests "CD", which the oracle accepts.
• From "CD", the single-byte deletions "D" and "C" are both rejected.
• The single-byte sweep then finishes, which certifies "CD", of length 2, as one_minimal.
• "A", of length 1, also satisfies that oracle.

Greedy chunk deletion follows the first deletion that succeeds, so when an input carries multiple independent causes of the failure, the result depends on which deletion the sweep reaches first.

Abstract Formal Model

A formal model of reduction paths over List α lives in verification/foundations/Foundations/Reduction, in Core.lean and Necessity.lean:

• gap_is_not_globallyShortest proves that a 1-minimal list can fail to be globally shortest.
• budget_truncation_is_not_oneMinimal gives a concrete witness where cutting the search short of all single-byte deletions gives up 1-minimality.

Completion records how the search stopped at run time. A run that ends in budget_exhausted carries no 1-minimality guarantee, even when its result happens to be minimal. The Lean development is an abstract calculus over lists, and it proves nothing about this Zig code.

Attempt Budgets and Boundary Behavior

The ceiling on the number of oracle calls, Settings.max_attempts, forms the attempt budget, capping how many times the oracle is called and counting the call on the caller's own input as attempt 1. The cap covers oracle calls alone: bytes copied, memory the callback allocates, and wall-clock time all sit outside it.

• A budget of 0 returns error.AttemptBudgetExhausted before the workspace is acquired, leaving every byte and every flag of the workspace as it was.
• A budget of 1:
• A budget of 1 on an empty interesting input returns Completion.one_minimal straight away, with 1 attempt and 0 reductions.
• A budget of 1 on a nonempty interesting input stops after attempt 1 with Completion.budget_exhausted and hands back the input as it arrived.
• A budget that is exactly enough for the single-byte sweep to try every deletion still certifies Completion.one_minimal, including when the sweep finishes on the last allowed attempt.

Storage Architecture and Lifecycle

1. Capacity derivation: Capacity.derive(limits) calculates the workspace capacity (the arithmetic layout derived from the caller's limits, the sizing figure $N$ for the longest input submitted) as $N+max(N-1,0)$ bytes and allocates nothing. A sum that overflows usize returns DeriveError.CapacityOverflow. For $N=0$ the figure is 0 bytes. Filling in Storage or Capacity fields by hand is unsafe, so callers reach the same layout through Storage.init() and Capacity.derive().
2. Initialization: Storage.init(allocator, limits) allocates the backing memory once, setting the workspace lifecycle phase to Phase.initialization. A workspace that was never activated can be freed directly by storage.deinit(allocator).
3. Activation: storage.activate() seals the workspace into Phase.steady, idle with no lease outstanding so the next run can acquire it. After that the workspace owner allocates nothing further.
4. Acquisition: storage.acquire(input_bytes) checks the input against the bounds, issues a lease by setting in_use = true for this run's exclusive hold, and returns Regions, writing nothing into the lanes.
5. Error isolation: the three errors raised before acquisition, AttemptBudgetExhausted, ReductionStorageInUse, and InputCapacityExceeded, leave the workspace as it was, so a call that finds the workspace busy leaves an earlier live Result holding its lease. An error after acquisition gives up this run's lease through errdefer storage.release() and returns the workspace to idle, which restores neither the scratch bytes the run overwrote nor any side effect the callback produced.
6. Release and reuse: Result.deinit(), or storage.release(), clears in_use and returns the workspace to steady and idle. deinit() also clears the result's own fields, setting bytes = &.{}, attempts = 0, reductions = 0, and completion = .budget_exhausted, which ends the borrow (Result.bytes referencing workspace memory), and it is called exactly once per result. Feeding one run's result back in as the next run's input on the same workspace means copying result.bytes first.
7. Teardown: storage.deinit(allocator) checks that no lease is out, moves the workspace to Phase.teardown, and frees the memory with the same allocator init() received.

Ownership and Concurrency

• Result.bytes borrows from the workspace and stays readable until result.deinit().
• Storage.current and Storage.candidate are fixed regions of the workspace allocation, with the witness lane holding the current sequence, while the locals current and spare inside reduce() trade places, so Result.bytes can end up in either region.
• Storage offers no thread safety. in_use is a plain boolean that turns away a second use on one thread, so sharing one workspace across threads is the caller's to synchronize.
• One owner holds a given Storage and a given Result, makes no shallow copy of either, and leaves their bookkeeping fields alone.

Historical Context and Related Work

• Delta Debugging (ddmin): Andreas Zeller introduced delta debugging to isolate the code change responsible for a failure (Yesterday, My Program Worked. Today, It Does Not. Why?, ESEC/FSE 1999, pages 253–267, ACM DOI: 10.1145/318774.318946). Andreas Zeller and Ralf Hildebrandt then generalized the algorithm to minimizing an input (Simplifying and Isolating Failure-Inducing Input, IEEE TSE 2002).
• Hierarchical Delta Debugging (HDD): Ghassan Misherghi and Zhendong Su pruned parse trees one level at a time (HDD: Hierarchical Delta Debugging, ICSE 2006). Whether the result is syntactically valid rests on the tree manipulator and the grammar keeping it valid.
• C-Reduce: John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang built C-Reduce (Test-Case Reduction for C Compiler Bugs, ACM SIGPLAN PLDI 2012, pages 335–346). It combines Clang AST transformations, delta debugging over lines and tokens, and peephole rewrites, and it minimizes C and C++ inputs that crash a compiler, that are miscompiled, and that expose semantic bugs.
• QuickCheck Shrinking: Koen Claessen and John Hughes introduced property-based random testing (QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs, ICFP 2000). Property testing libraries today shrink by type through an interface like QuickCheck's shrink, whose signature shrink :: a -> [a] yields subterms of the value's type or simpler alternatives and defaults to [], which simplifies a counterexample over structured algebraic types.

This package works straight on raw byte sequences.

Definitions

Actions

Public operations.

• reduce: Shortens an initial byte sequence against the caller's oracle.

Types and contracts

Public types and contracts.

• Capacity: Workspace layout derived from the caller's limits, sized so that a run in steady state needs no further allocation.
• Completion: Stopping condition that ended the search, one_minimal or budget_exhausted.
• Error: Set of errors the reduction framework produces while acquiring the workspace or checking the input.
• Exhaustion: Set of errors raised when the input exceeds the workspace bounds or another run already holds the workspace.
• Interesting: Oracle's answer about one candidate, interesting or uninteresting.
• InterestingFn: Type of the caller's oracle function pointer.
• Limits: Sizing constraint the caller supplies for the byte reduction workspace.
• Result: Outcome of a run, with bytes borrowed from the acquired workspace.
• Settings: Options that control how a run executes.
• Status: Snapshot of one workspace's state, taken by value at the moment of the call.
• Storage: Workspace, allocated up front and double-buffered, that carries reduction in steady state.

Namespaces

Public namespaces.

• bytes: Namespace holding the byte-oriented implementation.

Code relationships

Direct static dependencies extracted from parsed source by semantic graph analysis.

Uses: tiny.hypothesis, tiny.smg
Used by: None

Verification

No verification records are cataloged for this module in this build.

Audit