tiny.hypothesis.shrinker

1pub const shrinker = @import("shrinker.zig");

1const std = @import("std");2const Allocator = std.mem.Allocator;3const conjecture = @import("conjecture.zig");4const ConjectureData = conjecture.ConjectureData;5const ChoiceNode = conjecture.ChoiceNode;6const Span = conjecture.Span;7const Status = conjecture.Status;89pub const ReplayFn = *const fn (10    choices: []const ChoiceNode,11    byte_blocks: ?[]const u8,12    context: *anyopaque,13) Status;1415pub fn shrink(16    allocator: Allocator,17    initial_choices: []const ChoiceNode,18    initial_spans: []const Span,19    initial_byte_blocks: ?[]const u8,20    replay_fn: ReplayFn,21    replay_context: *anyopaque,22    max_shrinks: usize,23) !ShrinkResult {24    var choices = try allocator.alloc(ChoiceNode, initial_choices.len);25    @memcpy(choices, initial_choices);2627    var spans = try allocator.alloc(Span, initial_spans.len);28    @memcpy(spans, initial_spans);2930    var byte_blocks: ?[]u8 = if (initial_byte_blocks) |bb| blk: {31        const buf = try allocator.alloc(u8, bb.len);32        @memcpy(buf, bb);33        break :blk buf;34    } else null;3536    var shrinks_remaining: usize = max_shrinks;37    var improved = true;3839    while (improved and shrinks_remaining > 0) {40        improved = false;4142        const r1 = try deleteSpans(43            allocator,44            choices,45            spans,46            byte_blocks,47            replay_fn,48            replay_context,49            &shrinks_remaining,50        );51        if (r1.improved) {52            allocator.free(choices);53            choices = r1.choices;54            allocator.free(spans);55            spans = r1.spans;56            updateByteBlocks(allocator, &byte_blocks, r1.byte_blocks);57            improved = true;58        }5960        const r2 = try tryTrivialSpans(61            allocator,62            choices,63            spans,64            byte_blocks,65            replay_fn,66            replay_context,67            &shrinks_remaining,68        );69        if (r2.improved) {70            allocator.free(choices);71            choices = r2.choices;72            updateByteBlocks(allocator, &byte_blocks, r2.byte_blocks);73            improved = true;74        }7576        const r3 = try minimizeIndividual(77            allocator,78            choices,79            byte_blocks,80            replay_fn,81            replay_context,82            &shrinks_remaining,83        );84        if (r3.improved) {85            allocator.free(choices);86            choices = r3.choices;87            updateByteBlocks(allocator, &byte_blocks, r3.byte_blocks);88            improved = true;89        }9091        const r4 = try minimizeDuplicated(92            allocator,93            choices,94            byte_blocks,95            replay_fn,96            replay_context,97            &shrinks_remaining,98        );99        if (r4.improved) {100            allocator.free(choices);101            choices = r4.choices;102            updateByteBlocks(allocator, &byte_blocks, r4.byte_blocks);103            improved = true;104        }105106        const r5 = try redistributePairs(107            allocator,108            choices,109            byte_blocks,110            replay_fn,111            replay_context,112            &shrinks_remaining,113        );114        if (r5.improved) {115            allocator.free(choices);116            choices = r5.choices;117            updateByteBlocks(allocator, &byte_blocks, r5.byte_blocks);118            improved = true;119        }120121        const r6 = try reorderSpans(122            allocator,123            choices,124            spans,125            byte_blocks,126            replay_fn,127            replay_context,128            &shrinks_remaining,129        );130        if (r6.improved) {131            allocator.free(choices);132            choices = r6.choices;133            allocator.free(spans);134            spans = r6.spans;135            updateByteBlocks(allocator, &byte_blocks, r6.byte_blocks);136            improved = true;137        }138139        const r7 = try lowerTogether(140            allocator,141            choices,142            byte_blocks,143            replay_fn,144            replay_context,145            &shrinks_remaining,146        );147        if (r7.improved) {148            allocator.free(choices);149            choices = r7.choices;150            updateByteBlocks(allocator, &byte_blocks, r7.byte_blocks);151            improved = true;152        }153154        const r8 = try minimizeFloats(155            allocator,156            choices,157            byte_blocks,158            replay_fn,159            replay_context,160            &shrinks_remaining,161        );162        if (r8.improved) {163            allocator.free(choices);164            choices = r8.choices;165            updateByteBlocks(allocator, &byte_blocks, r8.byte_blocks);166            improved = true;167        }168    }169170    return .{171        .choices = choices,172        .spans = spans,173        .byte_blocks = byte_blocks,174    };175}176177fn updateByteBlocks(178    allocator: Allocator,179    current: *?[]u8,180    next: ?[]u8,181) void {182    if (current.*) |old| {183        if (next) |new| {184            if (old.ptr != new.ptr) {185                allocator.free(old);186            }187        } else {188            allocator.free(old);189        }190    }191    current.* = next;192}193194pub const ShrinkResult = struct {195    choices: []ChoiceNode,196    spans: []Span,197    byte_blocks: ?[]u8,198199    pub fn deinit(self: *ShrinkResult, allocator: Allocator) void {200        allocator.free(self.choices);201        allocator.free(self.spans);202        if (self.byte_blocks) |bb| allocator.free(bb);203    }204};205206const PassResult = struct {207    choices: []ChoiceNode,208    spans: []Span,209    byte_blocks: ?[]u8,210    improved: bool,211};212213const PassResultNoSpans = struct {214    choices: []ChoiceNode,215    byte_blocks: ?[]u8,216    improved: bool,217};218219fn tryCandidate(220    candidate: []const ChoiceNode,221    byte_blocks: ?[]const u8,222    replay_fn: ReplayFn,223    replay_context: *anyopaque,224    shrinks_remaining: *usize,225) bool {226    if (shrinks_remaining.* == 0) return false;227    shrinks_remaining.* -= 1;228    return replay_fn(candidate, byte_blocks, replay_context) == .interesting;229}230231fn deleteSpans(232    allocator: Allocator,233    choices: []ChoiceNode,234    spans: []Span,235    byte_blocks: ?[]u8,236    replay_fn: ReplayFn,237    replay_context: *anyopaque,238    shrinks_remaining: *usize,239) !PassResult {240    if (spans.len == 0 or shrinks_remaining.* == 0) return .{241        .choices = choices,242        .spans = spans,243        .byte_blocks = byte_blocks,244        .improved = false,245    };246247    var current_choices = try allocator.alloc(ChoiceNode, choices.len);248    @memcpy(current_choices, choices);249    var current_spans = try allocator.alloc(Span, spans.len);250    @memcpy(current_spans, spans);251    var improved = false;252253    var group_size: usize = current_spans.len;254    while (group_size >= 1 and shrinks_remaining.* != 0) {255        var i: usize = 0;256        while (i + group_size <= current_spans.len and shrinks_remaining.* != 0) {257            const span_group = current_spans[i..][0..group_size];258            const first = span_group[0].start;259            const last = span_group[group_size - 1].end;260261            if (first >= current_choices.len or last > current_choices.len or first >= last) {262                i += 1;263                continue;264            }265266            const new_len = current_choices.len - (last - first);267            const candidate = try allocator.alloc(ChoiceNode, new_len);268            @memcpy(candidate[0..first], current_choices[0..first]);269            if (last < current_choices.len) {270                @memcpy(candidate[first..], current_choices[last..]);271            }272273            if (tryCandidate(candidate, byte_blocks, replay_fn, replay_context, shrinks_remaining)) {274                allocator.free(current_choices);275                current_choices = candidate;276                const new_spans_len = current_spans.len - group_size;277                const new_spans = try allocator.alloc(Span, new_spans_len);278                var si: usize = 0;279                for (current_spans, 0..) |s, idx| {280                    if (idx >= i and idx < i + group_size) continue;281                    var adjusted = s;282                    if (adjusted.start >= last) {283                        adjusted.start -= (last - first);284                        adjusted.end -= (last - first);285                    } else if (adjusted.start >= first) {286                        continue;287                    } else if (adjusted.end > last) {288                        adjusted.end -= (last - first);289                    } else if (adjusted.end > first) {290                        adjusted.end = first;291                    }292                    new_spans[si] = adjusted;293                    si += 1;294                }295                allocator.free(current_spans);296                current_spans = try allocator.realloc(new_spans, si);297                improved = true;298            } else {299                allocator.free(candidate);300                i += 1;301            }302        }303        group_size /= 2;304    }305306    if (!improved) {307        allocator.free(current_choices);308        allocator.free(current_spans);309    }310311    return .{312        .choices = if (improved) current_choices else choices,313        .spans = if (improved) current_spans else spans,314        .byte_blocks = byte_blocks,315        .improved = improved,316    };317}318319fn tryTrivialSpans(320    allocator: Allocator,321    choices: []ChoiceNode,322    spans: []Span,323    byte_blocks: ?[]u8,324    replay_fn: ReplayFn,325    replay_context: *anyopaque,326    shrinks_remaining: *usize,327) !PassResultNoSpans {328    if (shrinks_remaining.* == 0) return .{329        .choices = choices,330        .byte_blocks = byte_blocks,331        .improved = false,332    };333334    var current_choices = try allocator.alloc(ChoiceNode, choices.len);335    @memcpy(current_choices, choices);336    const saved = try allocator.alloc(u64, choices.len);337    defer allocator.free(saved);338    var improved = false;339340    for (spans) |span| {341        if (shrinks_remaining.* == 0) break;342        if (span.start >= current_choices.len or span.end > current_choices.len) continue;343344        var changed = false;345        for (current_choices[span.start..span.end]) |node| {346            if (!node.was_forced and node.value != node.shrink_towards) {347                changed = true;348                break;349            }350        }351        if (!changed) continue;352353        const window = current_choices[span.start..span.end];354        for (window, 0..) |node, offset| saved[offset] = node.value;355        for (window) |*node| {356            if (!node.was_forced) {357                node.value = node.shrink_towards;358            }359        }360361        if (tryCandidate(current_choices, byte_blocks, replay_fn, replay_context, shrinks_remaining)) {362            improved = true;363        } else {364            for (window, 0..) |*node, offset| node.value = saved[offset];365        }366    }367368    if (!improved) {369        allocator.free(current_choices);370    }371372    return .{373        .choices = if (improved) current_choices else choices,374        .byte_blocks = byte_blocks,375        .improved = improved,376    };377}378379fn minimizeIndividual(380    allocator: Allocator,381    choices: []ChoiceNode,382    byte_blocks: ?[]u8,383    replay_fn: ReplayFn,384    replay_context: *anyopaque,385    shrinks_remaining: *usize,386) !PassResultNoSpans {387    if (shrinks_remaining.* == 0) return .{388        .choices = choices,389        .byte_blocks = byte_blocks,390        .improved = false,391    };392393    var current_choices = try allocator.alloc(ChoiceNode, choices.len);394    @memcpy(current_choices, choices);395    var improved = false;396397    var i: usize = 0;398    while (i < current_choices.len) : (i += 1) {399        if (shrinks_remaining.* == 0) break;400        const node = current_choices[i];401        if (node.was_forced or node.kind != .integer) continue;402        if (node.value == node.shrink_towards) continue;403404        var lo = node.shrink_towards;405        var hi = node.value;406        const shrinks_down = node.shrink_towards <= node.value;407        if (lo > hi) {408            const tmp = lo;409            lo = hi;410            hi = tmp;411        }412413        var kept = node.value;414        while (lo < hi) {415            if (shrinks_remaining.* == 0) break;416            const mid = lo + (hi - lo) / 2;417            const try_val = if (shrinks_down) mid else hi - (mid - lo);418419            current_choices[i].value = try_val;420421            if (tryCandidate(current_choices, byte_blocks, replay_fn, replay_context, shrinks_remaining)) {422                kept = try_val;423                hi = try_val;424                improved = true;425            } else {426                current_choices[i].value = kept;427                if (shrinks_down) {428                    lo = mid + 1;429                } else {430                    hi = mid;431                }432            }433        }434    }435436    if (!improved) {437        allocator.free(current_choices);438    }439440    return .{441        .choices = if (improved) current_choices else choices,442        .byte_blocks = byte_blocks,443        .improved = improved,444    };445}446447fn minimizeDuplicated(448    allocator: Allocator,449    choices: []ChoiceNode,450    byte_blocks: ?[]u8,451    replay_fn: ReplayFn,452    replay_context: *anyopaque,453    shrinks_remaining: *usize,454) !PassResultNoSpans {455    if (shrinks_remaining.* == 0) return .{456        .choices = choices,457        .byte_blocks = byte_blocks,458        .improved = false,459    };460461    var current_choices = try allocator.alloc(ChoiceNode, choices.len);462    @memcpy(current_choices, choices);463    const touched = try allocator.alloc(usize, choices.len);464    defer allocator.free(touched);465    var improved = false;466467    var i: usize = 0;468    while (i < current_choices.len) : (i += 1) {469        if (shrinks_remaining.* == 0) break;470        const node = current_choices[i];471        if (node.was_forced or node.kind != .integer) continue;472        if (node.value == node.shrink_towards) continue;473474        var touched_count: usize = 0;475        for (current_choices[i + 1 ..], i + 1..) |other, other_index| {476            if (other.kind == .integer and !other.was_forced and other.value == node.value) {477                touched[touched_count] = other_index;478                touched_count += 1;479            }480        }481482        if (touched_count == 0) continue;483484        const target = node.shrink_towards;485        current_choices[i].value = target;486        for (touched[0..touched_count]) |other_index| {487            current_choices[other_index].value = target;488        }489490        if (tryCandidate(current_choices, byte_blocks, replay_fn, replay_context, shrinks_remaining)) {491            improved = true;492        } else {493            current_choices[i].value = node.value;494            for (touched[0..touched_count]) |other_index| {495                current_choices[other_index].value = node.value;496            }497        }498    }499500    if (!improved) {501        allocator.free(current_choices);502    }503504    return .{505        .choices = if (improved) current_choices else choices,506        .byte_blocks = byte_blocks,507        .improved = improved,508    };509}510511fn redistributePairs(512    allocator: Allocator,513    choices: []ChoiceNode,514    byte_blocks: ?[]u8,515    replay_fn: ReplayFn,516    replay_context: *anyopaque,517    shrinks_remaining: *usize,518) !PassResultNoSpans {519    if (choices.len < 2 or shrinks_remaining.* == 0) return .{520        .choices = choices,521        .byte_blocks = byte_blocks,522        .improved = false,523    };524525    var current_choices = try allocator.alloc(ChoiceNode, choices.len);526    @memcpy(current_choices, choices);527    var improved = false;528529    var i: usize = 0;530    while (i + 1 < current_choices.len) : (i += 1) {531        if (shrinks_remaining.* == 0) break;532        const a = &current_choices[i];533        const b = &current_choices[i + 1];534535        if (a.kind != .integer or b.kind != .integer) continue;536        if (a.was_forced or b.was_forced) continue;537538        const sum = a.value +% b.value;539        const new_a = a.shrink_towards;540        if (sum < new_a) continue;541        if (new_a == a.value) continue;542        const new_b = sum -% new_a;543544        if (new_b > b.max or new_a < a.min) continue;545546        const old_a = a.value;547        const old_b = b.value;548        a.value = new_a;549        b.value = new_b;550551        if (tryCandidate(current_choices, byte_blocks, replay_fn, replay_context, shrinks_remaining)) {552            improved = true;553        } else {554            a.value = old_a;555            b.value = old_b;556        }557    }558559    if (!improved) {560        allocator.free(current_choices);561    }562563    return .{564        .choices = if (improved) current_choices else choices,565        .byte_blocks = byte_blocks,566        .improved = improved,567    };568}569570fn reorderSpans(571    allocator: Allocator,572    choices: []ChoiceNode,573    spans: []Span,574    byte_blocks: ?[]u8,575    replay_fn: ReplayFn,576    replay_context: *anyopaque,577    shrinks_remaining: *usize,578) !PassResult {579    if (spans.len < 2 or shrinks_remaining.* == 0) return .{580        .choices = choices,581        .spans = spans,582        .byte_blocks = byte_blocks,583        .improved = false,584    };585586    var current_choices = try allocator.alloc(ChoiceNode, choices.len);587    @memcpy(current_choices, choices);588    var current_spans = try allocator.alloc(Span, spans.len);589    @memcpy(current_spans, spans);590    var improved = false;591592    var i: usize = 0;593    while (i + 1 < current_spans.len) : (i += 1) {594        if (shrinks_remaining.* == 0) break;595        const a = current_spans[i];596        const b = current_spans[i + 1];597598        if (a.depth != b.depth) continue;599        if (a.end != b.start) continue;600        if (a.end > current_choices.len or b.end > current_choices.len) continue;601602        const a_slice = current_choices[a.start..a.end];603        const b_slice = current_choices[b.start..b.end];604605        if (!lexLess(b_slice, a_slice)) continue;606607        const candidate = try allocator.alloc(ChoiceNode, current_choices.len);608        @memcpy(candidate[0..a.start], current_choices[0..a.start]);609        const b_len = b.end - b.start;610        const a_len = a.end - a.start;611        @memcpy(candidate[a.start..][0..b_len], b_slice);612        @memcpy(candidate[a.start + b_len ..][0..a_len], a_slice);613        if (b.end < current_choices.len) {614            @memcpy(candidate[a.start + b_len + a_len ..], current_choices[b.end..]);615        }616617        if (tryCandidate(candidate, byte_blocks, replay_fn, replay_context, shrinks_remaining)) {618            allocator.free(current_choices);619            current_choices = candidate;620            current_spans[i] = .{621                .label = b.label,622                .start = a.start,623                .end = a.start + b_len,624                .depth = a.depth,625            };626            current_spans[i + 1] = .{627                .label = a.label,628                .start = a.start + b_len,629                .end = a.start + b_len + a_len,630                .depth = a.depth,631            };632            improved = true;633        } else {634            allocator.free(candidate);635        }636    }637638    if (!improved) {639        allocator.free(current_choices);640        allocator.free(current_spans);641    }642643    return .{644        .choices = if (improved) current_choices else choices,645        .spans = if (improved) current_spans else spans,646        .byte_blocks = byte_blocks,647        .improved = improved,648    };649}650651fn lowerTogether(652    allocator: Allocator,653    choices: []ChoiceNode,654    byte_blocks: ?[]u8,655    replay_fn: ReplayFn,656    replay_context: *anyopaque,657    shrinks_remaining: *usize,658) !PassResultNoSpans {659    if (shrinks_remaining.* == 0) return .{660        .choices = choices,661        .byte_blocks = byte_blocks,662        .improved = false,663    };664665    var current_choices = try allocator.alloc(ChoiceNode, choices.len);666    @memcpy(current_choices, choices);667    var improved = false;668669    const window: usize = 3;670    var saved: [window]u64 = undefined;671    var start: usize = 0;672    while (start + 1 < current_choices.len) : (start += 1) {673        if (shrinks_remaining.* == 0) break;674        const end = @min(start + window, current_choices.len);675676        var can_lower = false;677        for (current_choices[start..end]) |node| {678            if (node.kind == .integer and !node.was_forced and node.value > node.shrink_towards) {679                can_lower = true;680                break;681            }682        }683        if (!can_lower) continue;684685        const slice = current_choices[start..end];686        for (slice, 0..) |node, offset| saved[offset] = node.value;687        for (slice) |*node| {688            if (node.kind == .integer and !node.was_forced and node.value > node.shrink_towards) {689                node.value -= 1;690            }691        }692693        if (tryCandidate(current_choices, byte_blocks, replay_fn, replay_context, shrinks_remaining)) {694            improved = true;695        } else {696            for (slice, 0..) |*node, offset| node.value = saved[offset];697        }698    }699700    if (!improved) {701        allocator.free(current_choices);702    }703704    return .{705        .choices = if (improved) current_choices else choices,706        .byte_blocks = byte_blocks,707        .improved = improved,708    };709}710711fn minimizeFloats(712    allocator: Allocator,713    choices: []ChoiceNode,714    byte_blocks: ?[]u8,715    replay_fn: ReplayFn,716    replay_context: *anyopaque,717    shrinks_remaining: *usize,718) !PassResultNoSpans {719    if (shrinks_remaining.* == 0) return .{720        .choices = choices,721        .byte_blocks = byte_blocks,722        .improved = false,723    };724725    var current_choices = try allocator.alloc(ChoiceNode, choices.len);726    @memcpy(current_choices, choices);727    var improved = false;728729    for (0..current_choices.len) |i| {730        if (shrinks_remaining.* == 0) break;731        const node_snapshot = current_choices[i];732        if (node_snapshot.was_forced or node_snapshot.kind != .float) continue;733734        const min_f: f64 = @bitCast(node_snapshot.min);735        const max_f: f64 = @bitCast(node_snapshot.max);736        const target_f: f64 = @bitCast(node_snapshot.shrink_towards);737        const cur_f: f64 = @bitCast(node_snapshot.value);738739        if (bitsEqual(cur_f, target_f)) continue;740741        var candidates_buf: [8]f64 = undefined;742        var n_candidates: usize = 0;743        addFloatCandidate(&candidates_buf, &n_candidates, target_f, min_f, max_f);744        addFloatCandidate(&candidates_buf, &n_candidates, 0.0, min_f, max_f);745        addFloatCandidate(&candidates_buf, &n_candidates, 1.0, min_f, max_f);746        addFloatCandidate(&candidates_buf, &n_candidates, -1.0, min_f, max_f);747        if (std.math.isFinite(cur_f) and std.math.signbit(cur_f) and cur_f != 0.0) {748            addFloatCandidate(&candidates_buf, &n_candidates, -cur_f, min_f, max_f);749        }750        if (std.math.isFinite(cur_f)) {751            addFloatCandidate(&candidates_buf, &n_candidates, @trunc(cur_f), min_f, max_f);752            addFloatCandidate(&candidates_buf, &n_candidates, @floor(cur_f), min_f, max_f);753        }754755        for (candidates_buf[0..n_candidates]) |cand| {756            if (shrinks_remaining.* == 0) break;757            const cur_now: f64 = @bitCast(current_choices[i].value);758            if (bitsEqual(cand, cur_now)) continue;759760            const old_bits = current_choices[i].value;761            current_choices[i].value = @bitCast(cand);762763            if (tryCandidate(current_choices, byte_blocks, replay_fn, replay_context, shrinks_remaining)) {764                improved = true;765                break;766            } else {767                current_choices[i].value = old_bits;768            }769        }770771        var phase_b_steps: usize = 0;772        const max_bisect_steps: usize = 32;773        while (phase_b_steps < max_bisect_steps) : (phase_b_steps += 1) {774            if (shrinks_remaining.* == 0) break;775            const cur_now: f64 = @bitCast(current_choices[i].value);776            if (!std.math.isFinite(cur_now) or !std.math.isFinite(target_f)) break;777            if (cur_now == target_f) break;778779            const mid = cur_now * 0.5 + target_f * 0.5;780            if (mid == cur_now or mid == target_f) break;781            if (mid < min_f or mid > max_f) break;782783            const old_bits = current_choices[i].value;784            current_choices[i].value = @bitCast(mid);785786            if (tryCandidate(current_choices, byte_blocks, replay_fn, replay_context, shrinks_remaining)) {787                improved = true;788            } else {789                current_choices[i].value = old_bits;790                break;791            }792        }793    }794795    if (!improved) {796        allocator.free(current_choices);797    }798799    return .{800        .choices = if (improved) current_choices else choices,801        .byte_blocks = byte_blocks,802        .improved = improved,803    };804}805806fn addFloatCandidate(buf: *[8]f64, n: *usize, v: f64, lo: f64, hi: f64) void {807    if (n.* >= buf.len) return;808    if (std.math.isNan(v)) return;809    if (v < lo or v > hi) return;810    for (buf[0..n.*]) |existing| {811        if (bitsEqual(existing, v)) return;812    }813    buf[n.*] = v;814    n.* += 1;815}816817fn bitsEqual(a: f64, b: f64) bool {818    const ai: u64 = @bitCast(a);819    const bi: u64 = @bitCast(b);820    return ai == bi;821}822823fn lexLess(a: []const ChoiceNode, b: []const ChoiceNode) bool {824    const len = @min(a.len, b.len);825    for (a[0..len], b[0..len]) |x, y| {826        if (x.value < y.value) return true;827        if (x.value > y.value) return false;828    }829    return a.len < b.len;830}831832const AlwaysInterestingReplay = struct {833    fn replay(_: []const ChoiceNode, _: ?[]const u8, _: *anyopaque) Status {834        return .interesting;835    }836};837838const TwoChoiceReplay = struct {839    fn replay(choices: []const ChoiceNode, _: ?[]const u8, _: *anyopaque) Status {840        return if (choices.len == 2) .interesting else .valid;841    }842};843844const IndividualThresholdReplay = struct {845    fn replay(choices: []const ChoiceNode, _: ?[]const u8, _: *anyopaque) Status {846        if (choices.len > 0 and choices[0].value > 10) return .interesting;847        return .valid;848    }849};850851const DuplicatedZeroReplay = struct {852    fn replay(choices: []const ChoiceNode, _: ?[]const u8, _: *anyopaque) Status {853        if (choices[0].value == 0 and choices[2].value == 0 and choices[3].value == 0) {854            return .interesting;855        }856        return .valid;857    }858};859860const FiniteFloatReplay = struct {861    fn replay(choices: []const ChoiceNode, _: ?[]const u8, _: *anyopaque) Status {862        if (choices.len == 0) return .valid;863        const value: f64 = @bitCast(choices[0].value);864        return if (std.math.isFinite(value)) .interesting else .valid;865    }866};867868const PositiveFloatThresholdReplay = struct {869    fn replay(choices: []const ChoiceNode, _: ?[]const u8, _: *anyopaque) Status {870        if (choices.len == 0) return .valid;871        const value: f64 = @bitCast(choices[0].value);872        return if (std.math.isFinite(value) and value > 5.0) .interesting else .valid;873    }874};875876const AbsoluteFloatThresholdReplay = struct {877    fn replay(choices: []const ChoiceNode, _: ?[]const u8, _: *anyopaque) Status {878        if (choices.len == 0) return .valid;879        const value: f64 = @bitCast(choices[0].value);880        return if (std.math.isFinite(value) and @abs(value) > 10.0) .interesting else .valid;881    }882};883884test "shrink survives consecutive improving span passes" {885    const allocator = std.testing.allocator;886    const choices = [_]ChoiceNode{887        .{ .kind = .integer, .value = 5, .min = 0, .max = 100, .shrink_towards = 0 },888        .{ .kind = .integer, .value = 7, .min = 0, .max = 100, .shrink_towards = 0 },889        .{ .kind = .integer, .value = 9, .min = 0, .max = 100, .shrink_towards = 0 },890    };891    const spans = [_]Span{892        .{ .label = "outer", .start = 0, .end = 3, .depth = 0 },893        .{ .label = "inner", .start = 1, .end = 3, .depth = 1 },894    };895    var ctx: usize = 0;896    var result = try shrink(897        allocator,898        &choices,899        &spans,900        null,901        &AlwaysInterestingReplay.replay,902        @ptrCast(&ctx),903        200,904    );905    defer result.deinit(allocator);906    try std.testing.expect(result.choices.len <= choices.len);907}908909test "shrink frees exact span allocation when nested spans drop" {910    const allocator = std.testing.allocator;911    const choices = [_]ChoiceNode{912        .{ .kind = .integer, .value = 3, .min = 0, .max = 100, .shrink_towards = 0 },913        .{ .kind = .integer, .value = 5, .min = 0, .max = 100, .shrink_towards = 0 },914        .{ .kind = .integer, .value = 7, .min = 0, .max = 100, .shrink_towards = 0 },915        .{ .kind = .integer, .value = 9, .min = 0, .max = 100, .shrink_towards = 0 },916    };917    const spans = [_]Span{918        .{ .label = "outer", .start = 0, .end = 4, .depth = 0 },919        .{ .label = "mid", .start = 1, .end = 3, .depth = 1 },920        .{ .label = "inner", .start = 1, .end = 2, .depth = 2 },921        .{ .label = "tail", .start = 3, .end = 4, .depth = 1 },922    };923    var ctx: usize = 0;924    var result = try shrink(925        allocator,926        &choices,927        &spans,928        null,929        &TwoChoiceReplay.replay,930        @ptrCast(&ctx),931        50,932    );933    defer result.deinit(allocator);934    try std.testing.expectEqual(@as(usize, 2), result.choices.len);935}936937test "minimizeIndividual shrinks toward target" {938    const allocator = std.testing.allocator;939940    var choices = [_]ChoiceNode{941        .{ .kind = .integer, .value = 50, .min = 0, .max = 100, .shrink_towards = 0 },942    };943944    var ctx: usize = 0;945    var remaining: usize = 100;946    const result = try minimizeIndividual(947        allocator,948        &choices,949        null,950        &IndividualThresholdReplay.replay,951        @ptrCast(&ctx),952        &remaining,953    );954955    if (result.improved) {956        defer allocator.free(result.choices);957        try std.testing.expectEqual(11, result.choices[0].value);958    }959}960961test "minimizeDuplicated shrinks equal integers together" {962    const allocator = std.testing.allocator;963964    var choices = [_]ChoiceNode{965        .{ .kind = .integer, .value = 7, .min = 0, .max = 10, .shrink_towards = 0 },966        .{ .kind = .integer, .value = 3, .min = 0, .max = 10, .shrink_towards = 0 },967        .{ .kind = .integer, .value = 7, .min = 0, .max = 10, .shrink_towards = 0 },968        .{ .kind = .integer, .value = 7, .min = 0, .max = 10, .shrink_towards = 0 },969    };970971    var ctx: usize = 0;972    var remaining: usize = 10;973    const result = try minimizeDuplicated(974        allocator,975        &choices,976        null,977        &DuplicatedZeroReplay.replay,978        @ptrCast(&ctx),979        &remaining,980    );981982    try std.testing.expect(result.improved);983    defer allocator.free(result.choices);984    try std.testing.expectEqual(@as(u64, 0), result.choices[0].value);985    try std.testing.expectEqual(@as(u64, 3), result.choices[1].value);986    try std.testing.expectEqual(@as(u64, 0), result.choices[2].value);987    try std.testing.expectEqual(@as(u64, 0), result.choices[3].value);988}989990test "lexLess comparison" {991    const a = [_]ChoiceNode{992        .{ .kind = .integer, .value = 1 },993        .{ .kind = .integer, .value = 2 },994    };995    const b = [_]ChoiceNode{996        .{ .kind = .integer, .value = 2 },997        .{ .kind = .integer, .value = 1 },998    };999    try std.testing.expect(lexLess(&a, &b));1000    try std.testing.expect(!lexLess(&b, &a));1001}10021003test "minimizeFloats reaches target via canonical 0.0" {1004    const allocator = std.testing.allocator;10051006    var choices = [_]ChoiceNode{1007        .{1008            .kind = .float,1009            .value = @bitCast(@as(f64, 7.5)),1010            .min = @bitCast(@as(f64, -100.0)),1011            .max = @bitCast(@as(f64, 100.0)),1012            .shrink_towards = @bitCast(@as(f64, 0.0)),1013        },1014    };10151016    var ctx: usize = 0;1017    var remaining: usize = 100;1018    const result = try minimizeFloats(1019        allocator,1020        &choices,1021        null,1022        &FiniteFloatReplay.replay,1023        @ptrCast(&ctx),1024        &remaining,1025    );10261027    try std.testing.expect(result.improved);1028    defer allocator.free(result.choices);1029    const final: f64 = @bitCast(result.choices[0].value);1030    try std.testing.expectEqual(@as(f64, 0.0), final);1031}10321033test "minimizeFloats reaches integer-valued canonical from large value" {1034    const allocator = std.testing.allocator;10351036    var choices = [_]ChoiceNode{1037        .{1038            .kind = .float,1039            .value = @bitCast(@as(f64, 17.3)),1040            .min = @bitCast(@as(f64, -1000.0)),1041            .max = @bitCast(@as(f64, 1000.0)),1042            .shrink_towards = @bitCast(@as(f64, 0.0)),1043        },1044    };10451046    var ctx: usize = 0;1047    var remaining: usize = 200;1048    const result = try minimizeFloats(1049        allocator,1050        &choices,1051        null,1052        &PositiveFloatThresholdReplay.replay,1053        @ptrCast(&ctx),1054        &remaining,1055    );10561057    try std.testing.expect(result.improved);1058    defer allocator.free(result.choices);1059    const final: f64 = @bitCast(result.choices[0].value);1060    try std.testing.expect(final > 5.0);1061    try std.testing.expect(final < 17.3);1062}10631064test "minimizeFloats handles NaN by reaching 0.0" {1065    const allocator = std.testing.allocator;10661067    const nan = std.math.nan(f64);1068    var choices = [_]ChoiceNode{1069        .{1070            .kind = .float,1071            .value = @bitCast(nan),1072            .min = @bitCast(@as(f64, -1.0)),1073            .max = @bitCast(@as(f64, 1.0)),1074            .shrink_towards = @bitCast(@as(f64, 0.0)),1075        },1076    };10771078    var ctx: usize = 0;1079    var remaining: usize = 50;1080    const result = try minimizeFloats(1081        allocator,1082        &choices,1083        null,1084        &AlwaysInterestingReplay.replay,1085        @ptrCast(&ctx),1086        &remaining,1087    );10881089    try std.testing.expect(result.improved);1090    defer allocator.free(result.choices);1091    const final: f64 = @bitCast(result.choices[0].value);1092    try std.testing.expectEqual(@as(f64, 0.0), final);1093}10941095test "minimizeFloats sign-strips negative finite values" {1096    const allocator = std.testing.allocator;10971098    var choices = [_]ChoiceNode{1099        .{1100            .kind = .float,1101            .value = @bitCast(@as(f64, -17.5)),1102            .min = @bitCast(@as(f64, -1000.0)),1103            .max = @bitCast(@as(f64, 1000.0)),1104            .shrink_towards = @bitCast(@as(f64, 0.0)),1105        },1106    };11071108    var ctx: usize = 0;1109    var remaining: usize = 200;1110    const result = try minimizeFloats(1111        allocator,1112        &choices,1113        null,1114        &AbsoluteFloatThresholdReplay.replay,1115        @ptrCast(&ctx),1116        &remaining,1117    );11181119    try std.testing.expect(result.improved);1120    defer allocator.free(result.choices);1121    const final: f64 = @bitCast(result.choices[0].value);1122    try std.testing.expect(!std.math.signbit(final));1123    try std.testing.expect(@abs(final) > 10.0);1124}