lib/hypothesis/src/shrinker.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const Allocator = std.mem.Allocator;
3 const conjecture = @import("conjecture.zig");
4 const ConjectureData = conjecture.ConjectureData;
5 const ChoiceNode = conjecture.ChoiceNode;
6 const Span = conjecture.Span;
7 const Status = conjecture.Status;
8
9 pub const ReplayFn = *const fn (
10 choices: []const ChoiceNode,
11 byte_blocks: ?[]const u8,
12 context: *anyopaque,
13 ) Status;
14
15 pub 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);
26
27 var spans = try allocator.alloc(Span, initial_spans.len);
28 @memcpy(spans, initial_spans);
29
30 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;
35
36 var shrinks_remaining: usize = max_shrinks;
37 var improved = true;
38
39 while (improved and shrinks_remaining > 0) {
40 improved = false;
41
42 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 }
59
60 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 }
75
76 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 }
90
91 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 }
105
106 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 }
120
121 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 }
138
139 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 }
153
154 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 }
169
170 return .{
171 .choices = choices,
172 .spans = spans,
173 .byte_blocks = byte_blocks,
174 };
175 }
176
177 fn 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 }
193
194 pub const ShrinkResult = struct {
195 choices: []ChoiceNode,
196 spans: []Span,
197 byte_blocks: ?[]u8,
198
199 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 };
205
206 const PassResult = struct {
207 choices: []ChoiceNode,
208 spans: []Span,
209 byte_blocks: ?[]u8,
210 improved: bool,
211 };
212
213 const PassResultNoSpans = struct {
214 choices: []ChoiceNode,
215 byte_blocks: ?[]u8,
216 improved: bool,
217 };
218
219 fn 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 }
230
231 fn 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 };
246
247 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;
252
253 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;
260
261 if (first >= current_choices.len or last > current_choices.len or first >= last) {
262 i += 1;
263 continue;
264 }
265
266 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 }
272
273 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 }
305
306 if (!improved) {
307 allocator.free(current_choices);
308 allocator.free(current_spans);
309 }
310
311 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 }
318
319 fn 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 };
333
334 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;
339
340 for (spans) |span| {
341 if (shrinks_remaining.* == 0) break;
342 if (span.start >= current_choices.len or span.end > current_choices.len) continue;
343
344 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;
352
353 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 }
360
361 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 }
367
368 if (!improved) {
369 allocator.free(current_choices);
370 }
371
372 return .{
373 .choices = if (improved) current_choices else choices,
374 .byte_blocks = byte_blocks,
375 .improved = improved,
376 };
377 }
378
379 fn 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 };
392
393 var current_choices = try allocator.alloc(ChoiceNode, choices.len);
394 @memcpy(current_choices, choices);
395 var improved = false;
396
397 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;
403
404 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 }
412
413 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);
418
419 current_choices[i].value = try_val;
420
421 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 }
435
436 if (!improved) {
437 allocator.free(current_choices);
438 }
439
440 return .{
441 .choices = if (improved) current_choices else choices,
442 .byte_blocks = byte_blocks,
443 .improved = improved,
444 };
445 }
446
447 fn 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 };
460
461 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;
466
467 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;
473
474 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 }
481
482 if (touched_count == 0) continue;
483
484 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 }
489
490 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 }
499
500 if (!improved) {
501 allocator.free(current_choices);
502 }
503
504 return .{
505 .choices = if (improved) current_choices else choices,
506 .byte_blocks = byte_blocks,
507 .improved = improved,
508 };
509 }
510
511 fn 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 };
524
525 var current_choices = try allocator.alloc(ChoiceNode, choices.len);
526 @memcpy(current_choices, choices);
527 var improved = false;
528
529 var i: usize = 0;
530 while (i + 1 < current_choices.len) : (i += 1) {
531 if (shrinks_remaining.* == 0) break;
532 const a = ¤t_choices[i];
533 const b = ¤t_choices[i + 1];
534
535 if (a.kind != .integer or b.kind != .integer) continue;
536 if (a.was_forced or b.was_forced) continue;
537
538 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;
543
544 if (new_b > b.max or new_a < a.min) continue;
545
546 const old_a = a.value;
547 const old_b = b.value;
548 a.value = new_a;
549 b.value = new_b;
550
551 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 }
558
559 if (!improved) {
560 allocator.free(current_choices);
561 }
562
563 return .{
564 .choices = if (improved) current_choices else choices,
565 .byte_blocks = byte_blocks,
566 .improved = improved,
567 };
568 }
569
570 fn 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 };
585
586 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;
591
592 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];
597
598 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;
601
602 const a_slice = current_choices[a.start..a.end];
603 const b_slice = current_choices[b.start..b.end];
604
605 if (!lexLess(b_slice, a_slice)) continue;
606
607 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 }
616
617 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 }
637
638 if (!improved) {
639 allocator.free(current_choices);
640 allocator.free(current_spans);
641 }
642
643 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 }
650
651 fn 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 };
664
665 var current_choices = try allocator.alloc(ChoiceNode, choices.len);
666 @memcpy(current_choices, choices);
667 var improved = false;
668
669 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);
675
676 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;
684
685 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 }
692
693 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 }
699
700 if (!improved) {
701 allocator.free(current_choices);
702 }
703
704 return .{
705 .choices = if (improved) current_choices else choices,
706 .byte_blocks = byte_blocks,
707 .improved = improved,
708 };
709 }
710
711 fn 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 };
724
725 var current_choices = try allocator.alloc(ChoiceNode, choices.len);
726 @memcpy(current_choices, choices);
727 var improved = false;
728
729 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;
733
734 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);
738
739 if (bitsEqual(cur_f, target_f)) continue;
740
741 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 }
754
755 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;
759
760 const old_bits = current_choices[i].value;
761 current_choices[i].value = @bitCast(cand);
762
763 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 }
770
771 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;
778
779 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;
782
783 const old_bits = current_choices[i].value;
784 current_choices[i].value = @bitCast(mid);
785
786 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 }
794
795 if (!improved) {
796 allocator.free(current_choices);
797 }
798
799 return .{
800 .choices = if (improved) current_choices else choices,
801 .byte_blocks = byte_blocks,
802 .improved = improved,
803 };
804 }
805
806 fn 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 }
816
817 fn bitsEqual(a: f64, b: f64) bool {
818 const ai: u64 = @bitCast(a);
819 const bi: u64 = @bitCast(b);
820 return ai == bi;
821 }
822
823 fn 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 }
831
832 const AlwaysInterestingReplay = struct {
833 fn replay(_: []const ChoiceNode, _: ?[]const u8, _: *anyopaque) Status {
834 return .interesting;
835 }
836 };
837
838 const TwoChoiceReplay = struct {
839 fn replay(choices: []const ChoiceNode, _: ?[]const u8, _: *anyopaque) Status {
840 return if (choices.len == 2) .interesting else .valid;
841 }
842 };
843
844 const 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 };
850
851 const 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 };
859
860 const 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 };
867
868 const 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 };
875
876 const 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 };
883
884 test "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 }
908
909 test "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 }
936
937 test "minimizeIndividual shrinks toward target" {
938 const allocator = std.testing.allocator;
939
940 var choices = [_]ChoiceNode{
941 .{ .kind = .integer, .value = 50, .min = 0, .max = 100, .shrink_towards = 0 },
942 };
943
944 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 );
954
955 if (result.improved) {
956 defer allocator.free(result.choices);
957 try std.testing.expectEqual(11, result.choices[0].value);
958 }
959 }
960
961 test "minimizeDuplicated shrinks equal integers together" {
962 const allocator = std.testing.allocator;
963
964 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 };
970
971 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 );
981
982 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 }
989
990 test "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 }
1002
1003 test "minimizeFloats reaches target via canonical 0.0" {
1004 const allocator = std.testing.allocator;
1005
1006 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 };
1015
1016 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 );
1026
1027 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 }
1032
1033 test "minimizeFloats reaches integer-valued canonical from large value" {
1034 const allocator = std.testing.allocator;
1035
1036 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 };
1045
1046 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 );
1056
1057 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 }
1063
1064 test "minimizeFloats handles NaN by reaching 0.0" {
1065 const allocator = std.testing.allocator;
1066
1067 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 };
1077
1078 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 );
1088
1089 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 }
1094
1095 test "minimizeFloats sign-strips negative finite values" {
1096 const allocator = std.testing.allocator;
1097
1098 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 };
1107
1108 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 );
1118
1119 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 }