lib/hypothesis/src/database.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const Allocator = std.mem.Allocator;
4 const conjecture = @import("conjecture.zig");
5 const ChoiceNode = conjecture.ChoiceNode;
6 const Sha256 = std.crypto.hash.sha2.Sha256;
7 const assert = std.debug.assert;
8
9 const magic = "JHYP";
10 const format_version: u16 = 1;
11 const header_bytes: usize = 16;
12 const choice_bytes: usize = 40;
13 const byte_blocks_flag: u16 = 1;
14 const max_failure_bytes: usize = 10 * 1024 * 1024;
15 const digest_text_bytes: usize = Sha256.digest_length * 2;
16 const failure_extension = ".jhyp";
17 const failure_name_bytes = digest_text_bytes + failure_extension.len;
18
19 pub const FailureEntry = struct {
20 choices: []const ChoiceNode,
21 byte_blocks: ?[]const u8,
22 };
23
24 const FailureName = [failure_name_bytes]u8;
25
26 const ReplayLimits = struct {
27 db_path: []const u8,
28 namespace: ?[]const u8,
29 max_entries: usize,
30 max_choices: usize,
31 max_byte_blocks: usize,
32 };
33
34 const ReplayCapacity = struct {
35 entries: usize,
36 choices: usize,
37 byte_blocks: usize,
38 encoded_bytes: usize,
39 name_bytes: usize,
40 total_bytes: usize,
41
42 pub fn derive(limits: ReplayLimits) error{FailureTooLarge}!ReplayCapacity {
43 const encoded_bytes = try failureByteLen(
44 limits.max_choices,
45 limits.max_byte_blocks,
46 );
47 const name_bytes = std.math.mul(
48 usize,
49 limits.max_entries,
50 @sizeOf(FailureName),
51 ) catch return error.FailureTooLarge;
52 const choice_bytes_total = std.math.mul(
53 usize,
54 limits.max_choices,
55 @sizeOf(ChoiceNode),
56 ) catch return error.FailureTooLarge;
57 const working_bytes = std.math.add(
58 usize,
59 encoded_bytes,
60 choice_bytes_total,
61 ) catch return error.FailureTooLarge;
62 const total_bytes = std.math.add(
63 usize,
64 name_bytes,
65 working_bytes,
66 ) catch return error.FailureTooLarge;
67 return .{
68 .entries = limits.max_entries,
69 .choices = limits.max_choices,
70 .byte_blocks = limits.max_byte_blocks,
71 .encoded_bytes = encoded_bytes,
72 .name_bytes = name_bytes,
73 .total_bytes = total_bytes,
74 };
75 }
76 };
77
78 const ReplayStatus = struct {
79 entries_scanned: usize = 0,
80 candidate_files: usize = 0,
81 failures_loaded: usize = 0,
82 failures_rejected: usize = 0,
83 scan_budget_saturated: bool = false,
84 };
85
86 pub const ReplayCursor = struct {
87 phase: alloc_phase.capacity.Phase,
88 capacity: ReplayCapacity,
89 dir: ?std.Io.Dir,
90 names: []FailureName,
91 encoded: []u8,
92 choices: []ChoiceNode,
93 name_count: usize = 0,
94 next_name: usize = 0,
95 status_value: ReplayStatus = .{},
96
97 pub const Limits: type = ReplayLimits;
98 pub const Capacity: type = ReplayCapacity;
99 pub const Status: type = ReplayStatus;
100
101 pub const claim: alloc_phase.capacity.Declaration = .{
102 .source = .{
103 .id = "hypothesis.replay_cursor",
104 .kind = .phase_static,
105 .limit_source = .caller,
106 .storage = .{
107 .covered = &.{
108 .{
109 .id = "bounded_sorted_content_address_candidate_names",
110 .lifetime = .steady,
111 .detail = "bounded sorted content-address candidate names",
112 },
113 .{
114 .id = "maximum_admitted_canonical_failure_bytes",
115 .lifetime = .steady,
116 .detail = "maximum admitted canonical failure bytes",
117 },
118 .{
119 .id = "maximum_admitted_decoded_choice_nodes",
120 .lifetime = .steady,
121 .detail = "maximum admitted decoded choice nodes",
122 },
123 },
124 .excluded = &.{
125 "caller-owned database path, namespace, replay context, and captured result",
126 "directory and file handles plus operating-system directory and file caches",
127 },
128 },
129 .capacity = .{
130 .inputs = &.{
131 alloc_phase.capacity.bindInput(Limits, "db_path", "db_path"),
132 alloc_phase.capacity.bindInput(Limits, "max_byte_blocks", "max_byte_blocks"),
133 alloc_phase.capacity.bindInput(Limits, "max_choices", "max_choices"),
134 alloc_phase.capacity.bindInput(Limits, "max_entries", "max_entries"),
135 },
136 .type_selectors = &.{},
137 .nodes = &.{
138 .{ .collection = .{ .length = 0 } },
139 .{ .input = 1 },
140 .{ .input = 2 },
141 .{ .input = 3 },
142 .{ .add = .{ .left = 0, .right = 1 } },
143 .{ .add = .{ .left = 4, .right = 2 } },
144 .{ .add = .{ .left = 5, .right = 3 } },
145 },
146 .assertions = &.{.{
147 .scope = .closure_total,
148 .measure = .retained,
149 .relation = .upper_bound,
150 .expression = 6,
151 }},
152 },
153 .overload = .{
154 .kind = .not_applicable,
155 .detail = "scan and record limits define the domain; rejected records do not exhaust storage",
156 },
157 .risks = .{
158 .transitive = .{
159 .status = .open,
160 .detail = "directory, file, sort, and SHA callees lack an allocation-closure certificate",
161 },
162 .foreign = .{
163 .status = .excluded,
164 .detail = "filesystem handles and caches are excluded; sealed replay observes caller allocation",
165 },
166 },
167 .obligations = &.{
168 .{ .key = "hypothesis_replay_capacity", .role = .capacity_model },
169 .{ .key = "hypothesis_replay_sealed", .role = .foreign_risk },
170 .{ .key = "hypothesis_replay_oom_retry", .role = .custom },
171 },
172 },
173 .bindings = .{
174 .owner = @This(),
175 .seal = .{
176 .family = alloc_phase.capacity.selector(@This().activate),
177 .premise = .{
178 .class = .checked_semantic_fact,
179 .authority = .checker,
180 },
181 },
182 .teardown = .{
183 .family = alloc_phase.capacity.selector(@This().deinit),
184 .premise = .{
185 .class = .checked_semantic_fact,
186 .authority = .checker,
187 },
188 },
189 },
190 };
191
192 pub fn init(
193 allocator: Allocator,
194 limits: Limits,
195 ) !ReplayCursor {
196 const capacity = try Capacity.derive(limits);
197 var cursor = ReplayCursor{
198 .phase = .initialization,
199 .capacity = capacity,
200 .dir = null,
201 .names = &.{},
202 .encoded = &.{},
203 .choices = &.{},
204 };
205 errdefer cursor.release(allocator);
206 if (capacity.entries == 0) return cursor;
207
208 cursor.dir = openNamespaceDir(limits.db_path, limits.namespace) catch |err| switch (err) {
209 error.FileNotFound => return cursor,
210 else => return err,
211 };
212 cursor.names = try allocator.alloc(FailureName, capacity.entries);
213 cursor.encoded = try allocator.alloc(u8, capacity.encoded_bytes);
214 if (capacity.choices > 0) {
215 cursor.choices = try allocator.alloc(ChoiceNode, capacity.choices);
216 }
217 try cursor.scanNames();
218 return cursor;
219 }
220
221 pub fn activate(self: *ReplayCursor) void {
222 assert(self.phase == .initialization);
223 assert(self.name_count <= self.capacity.entries);
224 assert(self.next_name == 0);
225 self.phase = .steady;
226 }
227
228 pub fn next(self: *ReplayCursor) !?FailureEntry {
229 assert(self.phase == .steady);
230 assert(self.next_name <= self.name_count);
231 while (self.next_name < self.name_count) {
232 const name = self.names[self.next_name];
233 self.next_name += 1;
234 const failure = self.loadFailure(&name) catch |err| switch (err) {
235 error.FileNotFound => null,
236 else => return err,
237 };
238 if (failure) |entry| {
239 self.status_value.failures_loaded += 1;
240 assert(self.status_value.failures_loaded <= self.name_count);
241 return entry;
242 }
243 self.status_value.failures_rejected += 1;
244 assert(self.status_value.failures_rejected <= self.name_count);
245 }
246 return null;
247 }
248
249 pub fn status(self: *const ReplayCursor) Status {
250 assert(self.phase == .steady);
251 return self.status_value;
252 }
253
254 pub fn deinit(self: *ReplayCursor, allocator: Allocator) void {
255 assert(self.phase != .teardown);
256 self.phase = .teardown;
257 self.release(allocator);
258 self.* = undefined;
259 }
260
261 fn scanNames(self: *ReplayCursor) !void {
262 assert(self.phase == .initialization);
263 var iterator = self.dir.?.iterate();
264 while (self.status_value.entries_scanned < self.capacity.entries) {
265 const entry = try iterator.next(std.Options.debug_io) orelse break;
266 self.status_value.entries_scanned += 1;
267 if (entry.kind != .file) continue;
268 if (!isFailureName(entry.name)) continue;
269 @memcpy(self.names[self.name_count][0..], entry.name);
270 self.name_count += 1;
271 }
272 self.status_value.scan_budget_saturated =
273 self.status_value.entries_scanned == self.capacity.entries;
274 self.status_value.candidate_files = self.name_count;
275 std.mem.sort(FailureName, self.names[0..self.name_count], {}, nameLessThan);
276 }
277
278 fn loadFailure(self: *ReplayCursor, name: *const FailureName) !?FailureEntry {
279 assert(self.phase == .steady);
280 var file = try self.dir.?.openFile(std.Options.debug_io, name, .{
281 .allow_directory = false,
282 });
283 defer file.close(std.Options.debug_io);
284 const stat = try file.stat(std.Options.debug_io);
285 if (stat.kind != .file) return null;
286 const file_len = std.math.cast(usize, stat.size) orelse return null;
287 if (file_len > self.encoded.len) return null;
288 const data = self.encoded[0..file_len];
289 if (try file.readPositionalAll(std.Options.debug_io, data, 0) != file_len) {
290 return null;
291 }
292 var trailing: [1]u8 = undefined;
293 if (try file.readPositionalAll(std.Options.debug_io, &trailing, file_len) != 0) {
294 return null;
295 }
296 if (!failureNameMatches(name, data)) return null;
297 return deserializeFailureInto(
298 self.choices,
299 self.capacity.byte_blocks,
300 data,
301 ) catch |err| switch (err) {
302 error.InvalidFormat, error.UnsupportedVersion, error.CapacityExceeded => null,
303 };
304 }
305
306 fn release(self: *ReplayCursor, allocator: Allocator) void {
307 if (self.choices.len > 0) allocator.free(self.choices);
308 if (self.encoded.len > 0) allocator.free(self.encoded);
309 if (self.names.len > 0) allocator.free(self.names);
310 if (self.dir) |dir| dir.close(std.Options.debug_io);
311 }
312 };
313
314 comptime {
315 alloc_phase.capacity.requireAllocatorExactOwnerShape(ReplayCursor);
316 }
317
318 pub fn saveFailure(
319 allocator: Allocator,
320 db_path: []const u8,
321 namespace: ?[]const u8,
322 choices: []const ChoiceNode,
323 byte_blocks: ?[]const u8,
324 ) !void {
325 const resolved = try resolveDbPath(allocator, db_path, namespace);
326 defer if (resolved.owned) |path| allocator.free(path);
327
328 try std.Io.Dir.cwd().createDirPath(std.Options.debug_io, resolved.path);
329 var dir = try std.Io.Dir.cwd().openDir(std.Options.debug_io, resolved.path, .{});
330 defer dir.close(std.Options.debug_io);
331
332 const data = try serializeFailure(allocator, choices, byte_blocks);
333 defer allocator.free(data);
334 const digest_text = sha256Hex(data);
335 var name_buf: [failure_name_bytes]u8 = undefined;
336 const name = std.fmt.bufPrint(&name_buf, "{s}{s}", .{
337 digest_text,
338 failure_extension,
339 }) catch unreachable;
340
341 var atomic_file = try dir.createFileAtomic(
342 std.Options.debug_io,
343 name,
344 .{ .replace = true },
345 );
346 defer atomic_file.deinit(std.Options.debug_io);
347 try atomic_file.file.writePositionalAll(std.Options.debug_io, data, 0);
348 try atomic_file.replace(std.Options.debug_io);
349 }
350
351 fn serializeFailure(
352 allocator: Allocator,
353 choices: []const ChoiceNode,
354 byte_blocks: ?[]const u8,
355 ) ![]u8 {
356 const block_len = if (byte_blocks) |blocks| blocks.len else 0;
357 const total = try failureByteLen(choices.len, block_len);
358 const buf = try allocator.alloc(u8, total);
359 @memset(buf, 0);
360 @memcpy(buf[0..magic.len], magic);
361 std.mem.writeInt(u16, buf[4..6], format_version, .little);
362 std.mem.writeInt(
363 u16,
364 buf[6..8],
365 if (byte_blocks != null) byte_blocks_flag else 0,
366 .little,
367 );
368 std.mem.writeInt(u32, buf[8..12], @intCast(choices.len), .little);
369 std.mem.writeInt(u32, buf[12..16], @intCast(block_len), .little);
370
371 for (choices, 0..) |node, index| {
372 const offset = header_bytes + index * choice_bytes;
373 buf[offset] = @backingInt(node.kind);
374 buf[offset + 1] = @intFromBool(node.was_forced);
375 std.mem.writeInt(u64, buf[offset + 8 ..][0..8], node.value, .little);
376 std.mem.writeInt(u64, buf[offset + 16 ..][0..8], node.min, .little);
377 std.mem.writeInt(u64, buf[offset + 24 ..][0..8], node.max, .little);
378 std.mem.writeInt(u64, buf[offset + 32 ..][0..8], node.shrink_towards, .little);
379 }
380 if (byte_blocks) |blocks| {
381 @memcpy(buf[total - blocks.len ..], blocks);
382 }
383
384 return buf;
385 }
386
387 const FailureShape = struct {
388 choice_count: usize,
389 block_len: usize,
390 total: usize,
391 has_blocks: bool,
392 };
393
394 fn validateFailure(data: []const u8) !FailureShape {
395 if (data.len < header_bytes) return error.InvalidFormat;
396 if (!std.mem.eql(u8, data[0..magic.len], magic)) return error.InvalidFormat;
397 if (std.mem.readInt(u16, data[4..6], .little) != format_version) {
398 return error.UnsupportedVersion;
399 }
400 const flags = std.mem.readInt(u16, data[6..8], .little);
401 if (flags & ~byte_blocks_flag != 0) return error.InvalidFormat;
402 const choice_count: usize = std.mem.readInt(u32, data[8..12], .little);
403 const block_len: usize = std.mem.readInt(u32, data[12..16], .little);
404 if (flags & byte_blocks_flag == 0 and block_len != 0) return error.InvalidFormat;
405 const total = failureByteLen(choice_count, block_len) catch return error.InvalidFormat;
406 if (data.len != total) return error.InvalidFormat;
407
408 for (0..choice_count) |index| {
409 const offset = header_bytes + index * choice_bytes;
410 for (data[offset + 2 .. offset + 8]) |reserved| {
411 if (reserved != 0) return error.InvalidFormat;
412 }
413 if (std.enums.fromInt(conjecture.ChoiceKind, data[offset]) == null) {
414 return error.InvalidFormat;
415 }
416 if (data[offset + 1] > 1) return error.InvalidFormat;
417 }
418 return .{
419 .choice_count = choice_count,
420 .block_len = block_len,
421 .total = total,
422 .has_blocks = flags & byte_blocks_flag != 0,
423 };
424 }
425
426 fn decodeChoices(storage: []ChoiceNode, data: []const u8) void {
427 for (storage, 0..) |*node, index| {
428 const offset = header_bytes + index * choice_bytes;
429 node.* = .{
430 .kind = std.enums.fromInt(conjecture.ChoiceKind, data[offset]).?,
431 .value = std.mem.readInt(u64, data[offset + 8 ..][0..8], .little),
432 .min = std.mem.readInt(u64, data[offset + 16 ..][0..8], .little),
433 .max = std.mem.readInt(u64, data[offset + 24 ..][0..8], .little),
434 .shrink_towards = std.mem.readInt(u64, data[offset + 32 ..][0..8], .little),
435 .was_forced = data[offset + 1] == 1,
436 };
437 }
438 }
439
440 fn deserializeFailureInto(
441 choice_storage: []ChoiceNode,
442 max_byte_blocks: usize,
443 data: []const u8,
444 ) !FailureEntry {
445 const shape = try validateFailure(data);
446 if (shape.choice_count > choice_storage.len) return error.CapacityExceeded;
447 if (shape.block_len > max_byte_blocks) return error.CapacityExceeded;
448 const choices = choice_storage[0..shape.choice_count];
449 decodeChoices(choices, data);
450 return .{
451 .choices = choices,
452 .byte_blocks = if (shape.has_blocks)
453 data[shape.total - shape.block_len ..]
454 else
455 null,
456 };
457 }
458
459 fn deserializeFailure(allocator: Allocator, data: []const u8) !FailureEntry {
460 const shape = try validateFailure(data);
461
462 const choices = try allocator.alloc(ChoiceNode, shape.choice_count);
463 errdefer allocator.free(choices);
464 decodeChoices(choices, data);
465
466 const blocks: ?[]const u8 = if (shape.has_blocks) blk: {
467 const owned = try allocator.alloc(u8, shape.block_len);
468 @memcpy(owned, data[shape.total - shape.block_len ..]);
469 break :blk owned;
470 } else null;
471
472 return .{
473 .choices = choices,
474 .byte_blocks = blocks,
475 };
476 }
477
478 fn failureByteLen(choice_count: usize, block_len: usize) error{FailureTooLarge}!usize {
479 if (choice_count > std.math.maxInt(u32)) return error.FailureTooLarge;
480 if (block_len > std.math.maxInt(u32)) return error.FailureTooLarge;
481 const encoded_choices = std.math.mul(usize, choice_count, choice_bytes) catch
482 return error.FailureTooLarge;
483 const with_header = std.math.add(usize, header_bytes, encoded_choices) catch
484 return error.FailureTooLarge;
485 const total = std.math.add(usize, with_header, block_len) catch
486 return error.FailureTooLarge;
487 if (total > max_failure_bytes) return error.FailureTooLarge;
488 return total;
489 }
490
491 const ResolvedPath = struct {
492 path: []const u8,
493 owned: ?[]u8 = null,
494 };
495
496 fn resolveDbPath(
497 allocator: Allocator,
498 db_path: []const u8,
499 namespace: ?[]const u8,
500 ) !ResolvedPath {
501 if (namespace) |ns| {
502 const dir = sha256Hex(ns);
503 const joined = try std.fs.path.join(allocator, &.{ db_path, &dir });
504 return .{ .path = joined, .owned = joined };
505 }
506 return .{ .path = db_path };
507 }
508
509 fn openNamespaceDir(db_path: []const u8, namespace: ?[]const u8) !std.Io.Dir {
510 var base = try std.Io.Dir.cwd().openDir(
511 std.Options.debug_io,
512 db_path,
513 .{ .iterate = namespace == null },
514 );
515 if (namespace) |ns| {
516 defer base.close(std.Options.debug_io);
517 const child = sha256Hex(ns);
518 return base.openDir(std.Options.debug_io, &child, .{ .iterate = true });
519 }
520 return base;
521 }
522
523 fn sha256Hex(bytes: []const u8) [digest_text_bytes]u8 {
524 var digest: [Sha256.digest_length]u8 = undefined;
525 Sha256.hash(bytes, &digest, .{});
526 return std.fmt.bytesToHex(digest, .lower);
527 }
528
529 fn isFailureName(name: []const u8) bool {
530 return name.len == failure_name_bytes and
531 std.mem.endsWith(u8, name, failure_extension);
532 }
533
534 fn failureNameMatches(name: []const u8, data: []const u8) bool {
535 if (!isFailureName(name)) return false;
536 const expected = sha256Hex(data);
537 return std.mem.eql(u8, name[0..digest_text_bytes], &expected);
538 }
539
540 fn nameLessThan(_: void, left: FailureName, right: FailureName) bool {
541 return std.mem.order(u8, &left, &right) == .lt;
542 }
543
544 fn expectFailureEqual(
545 expected_choices: []const ChoiceNode,
546 expected_blocks: ?[]const u8,
547 actual: FailureEntry,
548 ) !void {
549 try std.testing.expectEqualDeep(expected_choices, actual.choices);
550 try std.testing.expectEqual(expected_blocks != null, actual.byte_blocks != null);
551 if (expected_blocks) |blocks| {
552 try std.testing.expectEqualSlices(u8, blocks, actual.byte_blocks.?);
553 }
554 }
555
556 fn expectInvalidWithoutAllocation(data: []const u8) !void {
557 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{
558 .fail_index = 0,
559 });
560 try std.testing.expectError(
561 error.InvalidFormat,
562 deserializeFailure(failing.allocator(), data),
563 );
564 try std.testing.expectEqual(@as(usize, 0), failing.alloc_index);
565 }
566
567 fn checkReplayCursorAllocationFailures(
568 allocator: Allocator,
569 db_path: []const u8,
570 namespace: []const u8,
571 expected: usize,
572 ) !void {
573 var cursor = try ReplayCursor.init(allocator, .{
574 .db_path = db_path,
575 .namespace = namespace,
576 .max_entries = expected,
577 .max_choices = 128,
578 .max_byte_blocks = 16,
579 });
580 defer cursor.deinit(allocator);
581 cursor.activate();
582 var loaded: usize = 0;
583 while (try cursor.next()) |_| loaded += 1;
584 try std.testing.expectEqual(expected, loaded);
585 }
586
587 test "serialize and deserialize roundtrips" {
588 const allocator = std.testing.allocator;
589
590 const choices = [_]ChoiceNode{
591 .{ .kind = .integer, .value = 42, .min = 0, .max = 100, .shrink_towards = 7 },
592 .{
593 .kind = .boolean,
594 .value = 1,
595 .min = 0,
596 .max = 1,
597 .shrink_towards = 0,
598 .was_forced = true,
599 },
600 };
601 const byte_blocks = "hello";
602
603 const data = try serializeFailure(allocator, &choices, byte_blocks);
604 defer allocator.free(data);
605
606 const entry = try deserializeFailure(allocator, data);
607 defer allocator.free(entry.choices);
608 defer if (entry.byte_blocks) |bb| allocator.free(bb);
609
610 try expectFailureEqual(&choices, byte_blocks, entry);
611 try std.testing.expectEqual(
612 @as(usize, header_bytes + choice_bytes * 2 + byte_blocks.len),
613 data.len,
614 );
615 try std.testing.expectEqualSlices(u8, magic, data[0..magic.len]);
616 try std.testing.expectEqual(format_version, std.mem.readInt(u16, data[4..6], .little));
617 }
618
619 test "canonical failure bytes are stable little endian" {
620 const allocator = std.testing.allocator;
621 const choices = [_]ChoiceNode{.{
622 .kind = .float,
623 .value = 0x0102_0304_0506_0708,
624 .min = 0x1112_1314_1516_1718,
625 .max = 0x2122_2324_2526_2728,
626 .shrink_towards = 0x3132_3334_3536_3738,
627 .was_forced = true,
628 }};
629 const encoded = try serializeFailure(allocator, &choices, &.{ 0xaa, 0xbb });
630 defer allocator.free(encoded);
631 const expected = [_]u8{
632 0x4a, 0x48, 0x59, 0x50, 0x01, 0x00, 0x01, 0x00,
633 0x01, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00,
634 0x02, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
635 0x08, 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01,
636 0x18, 0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11,
637 0x28, 0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21,
638 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31,
639 0xaa, 0xbb,
640 };
641 try std.testing.expectEqualSlices(u8, &expected, encoded);
642 }
643
644 test "fuzz: canonical failure codec roundtrips and rejects truncated prefixes" {
645 const allocator = std.testing.allocator;
646 const max_choices: usize = 32;
647 const max_blocks: usize = 128;
648 var prng = std.Random.DefaultPrng.init(0x4a48_5950_4442_0001);
649 var choices: [max_choices]ChoiceNode = undefined;
650 var blocks: [max_blocks]u8 = undefined;
651
652 for (0..64) |_| {
653 const random = prng.random();
654 const choice_count = random.uintLessThan(usize, max_choices + 1);
655 for (choices[0..choice_count]) |*node| {
656 node.* = .{
657 .kind = @fromBackingInt(@intCast(random.uintLessThan(u8, 4))),
658 .value = random.int(u64),
659 .min = random.int(u64),
660 .max = random.int(u64),
661 .shrink_towards = random.int(u64),
662 .was_forced = random.boolean(),
663 };
664 }
665 const block_len = random.uintLessThan(usize, max_blocks + 1);
666 random.bytes(blocks[0..block_len]);
667 const expected_blocks: ?[]const u8 = if (random.boolean()) blocks[0..block_len] else null;
668
669 const encoded = try serializeFailure(allocator, choices[0..choice_count], expected_blocks);
670 defer allocator.free(encoded);
671 const decoded = try deserializeFailure(allocator, encoded);
672 defer allocator.free(decoded.choices);
673 defer if (decoded.byte_blocks) |owned| allocator.free(owned);
674 try expectFailureEqual(choices[0..choice_count], expected_blocks, decoded);
675
676 for (0..encoded.len) |prefix_len| {
677 try expectInvalidWithoutAllocation(encoded[0..prefix_len]);
678 }
679 }
680 }
681
682 test "fuzz: malformed canonical failure fields reject before allocation" {
683 const allocator = std.testing.allocator;
684 const choices = [_]ChoiceNode{
685 .{
686 .kind = .bytes,
687 .value = 3,
688 .min = 1,
689 .max = 8,
690 .shrink_towards = 1,
691 .was_forced = true,
692 },
693 };
694 const encoded = try serializeFailure(allocator, &choices, "abc");
695 defer allocator.free(encoded);
696 var malformed = try allocator.dupe(u8, encoded);
697 defer allocator.free(malformed);
698
699 malformed[0] ^= 0xff;
700 try expectInvalidWithoutAllocation(malformed);
701 @memcpy(malformed, encoded);
702 std.mem.writeInt(u16, malformed[4..6], format_version + 1, .little);
703 var failing = std.testing.FailingAllocator.init(allocator, .{ .fail_index = 0 });
704 try std.testing.expectError(
705 error.UnsupportedVersion,
706 deserializeFailure(failing.allocator(), malformed),
707 );
708 try std.testing.expectEqual(@as(usize, 0), failing.alloc_index);
709 @memcpy(malformed, encoded);
710 std.mem.writeInt(u16, malformed[6..8], byte_blocks_flag | 2, .little);
711 try expectInvalidWithoutAllocation(malformed);
712 @memcpy(malformed, encoded);
713 malformed[header_bytes] = 0xff;
714 try expectInvalidWithoutAllocation(malformed);
715 @memcpy(malformed, encoded);
716 malformed[header_bytes + 1] = 2;
717 try expectInvalidWithoutAllocation(malformed);
718 @memcpy(malformed, encoded);
719 malformed[header_bytes + 2] = 1;
720 try expectInvalidWithoutAllocation(malformed);
721 @memcpy(malformed, encoded);
722 std.mem.writeInt(u16, malformed[6..8], 0, .little);
723 try expectInvalidWithoutAllocation(malformed);
724 @memcpy(malformed, encoded);
725 std.mem.writeInt(u32, malformed[8..12], std.math.maxInt(u32), .little);
726 try expectInvalidWithoutAllocation(malformed);
727 @memcpy(malformed, encoded);
728 std.mem.writeInt(u32, malformed[12..16], std.math.maxInt(u32), .little);
729 try expectInvalidWithoutAllocation(malformed);
730
731 const trailing = try std.mem.concat(allocator, u8, &.{ encoded, &.{0} });
732 defer allocator.free(trailing);
733 try expectInvalidWithoutAllocation(trailing);
734 try std.testing.expectError(
735 error.FailureTooLarge,
736 failureByteLen(std.math.maxInt(usize), std.math.maxInt(usize)),
737 );
738 }
739
740 test "save and load failure" {
741 const allocator = std.testing.allocator;
742
743 var tmp = std.testing.tmpDir(.{});
744 defer tmp.cleanup();
745
746 const tmp_path = try tmp.dir.realPathFileAlloc(std.Options.debug_io, ".", allocator);
747 defer allocator.free(tmp_path);
748
749 const choices = [_]ChoiceNode{
750 .{ .kind = .integer, .value = 99, .min = 0, .max = 200, .shrink_towards = 0 },
751 };
752
753 try saveFailure(allocator, tmp_path, "test", &choices, null);
754
755 var cursor = try ReplayCursor.init(allocator, .{
756 .db_path = tmp_path,
757 .namespace = "test",
758 .max_entries = 1,
759 .max_choices = 1,
760 .max_byte_blocks = 0,
761 });
762 defer cursor.deinit(allocator);
763 cursor.activate();
764 const failure = (try cursor.next()).?;
765 try std.testing.expectEqual(99, failure.choices[0].value);
766 try std.testing.expect((try cursor.next()) == null);
767 }
768
769 test "fuzz: complete failure identity preserves distinct replay inputs" {
770 const allocator = std.testing.allocator;
771 var tmp = std.testing.tmpDir(.{});
772 defer tmp.cleanup();
773 const tmp_path = try tmp.dir.realPathFileAlloc(std.Options.debug_io, ".", allocator);
774 defer allocator.free(tmp_path);
775 const base = ChoiceNode{ .kind = .integer, .value = 1, .min = 0, .max = 4 };
776 var choice = base;
777 try saveFailure(allocator, tmp_path, "identity", &.{choice}, null);
778 choice.kind = .boolean;
779 try saveFailure(allocator, tmp_path, "identity", &.{choice}, null);
780 choice = base;
781 choice.value = 2;
782 try saveFailure(allocator, tmp_path, "identity", &.{choice}, null);
783 choice = base;
784 choice.min = 1;
785 try saveFailure(allocator, tmp_path, "identity", &.{choice}, null);
786 choice = base;
787 choice.max = 5;
788 try saveFailure(allocator, tmp_path, "identity", &.{choice}, null);
789 choice = base;
790 choice.shrink_towards = 1;
791 try saveFailure(allocator, tmp_path, "identity", &.{choice}, null);
792 choice = base;
793 choice.was_forced = true;
794 try saveFailure(allocator, tmp_path, "identity", &.{choice}, null);
795 try saveFailure(allocator, tmp_path, "identity", &.{base}, &.{});
796 try saveFailure(allocator, tmp_path, "identity", &.{base}, "a");
797 try saveFailure(allocator, tmp_path, "identity", &.{base}, "b");
798 try saveFailure(allocator, tmp_path, "identity", &.{base}, "b");
799
800 var cursor = try ReplayCursor.init(allocator, .{
801 .db_path = tmp_path,
802 .namespace = "identity",
803 .max_entries = 10,
804 .max_choices = 1,
805 .max_byte_blocks = 1,
806 });
807 defer cursor.deinit(allocator);
808 cursor.activate();
809 var loaded: usize = 0;
810 while (try cursor.next()) |_| loaded += 1;
811 try std.testing.expectEqual(@as(usize, 10), loaded);
812 }
813
814 test "fuzz: load rejects a valid payload under the wrong content address" {
815 const allocator = std.testing.allocator;
816 var tmp = std.testing.tmpDir(.{});
817 defer tmp.cleanup();
818 const tmp_path = try tmp.dir.realPathFileAlloc(std.Options.debug_io, ".", allocator);
819 defer allocator.free(tmp_path);
820 const data = try serializeFailure(allocator, &.{.{ .kind = .integer, .value = 1 }}, null);
821 defer allocator.free(data);
822 const resolved = try resolveDbPath(allocator, tmp_path, "integrity");
823 defer if (resolved.owned) |path| allocator.free(path);
824 try std.Io.Dir.cwd().createDirPath(std.Options.debug_io, resolved.path);
825 var dir = try std.Io.Dir.cwd().openDir(std.Options.debug_io, resolved.path, .{});
826 defer dir.close(std.Options.debug_io);
827 var digest = sha256Hex(data);
828 digest[0] = if (digest[0] == '0') '1' else '0';
829 var name_buf: [failure_name_bytes]u8 = undefined;
830 const name = try std.fmt.bufPrint(&name_buf, "{s}{s}", .{ digest, failure_extension });
831 try dir.writeFile(std.Options.debug_io, .{ .sub_path = name, .data = data });
832 var cursor = try ReplayCursor.init(allocator, .{
833 .db_path = tmp_path,
834 .namespace = "integrity",
835 .max_entries = 1,
836 .max_choices = 1,
837 .max_byte_blocks = 0,
838 });
839 defer cursor.deinit(allocator);
840 cursor.activate();
841 try std.testing.expect((try cursor.next()) == null);
842 try std.testing.expectEqual(@as(usize, 1), cursor.status().failures_rejected);
843 }
844
845 test "replay cursor capacity matches an independent byte model" {
846 comptime {
847 @stardustClaim(
848 @import("alloc_phase").capacity.witness(ReplayCursor, "hypothesis_replay_capacity"),
849 null,
850 null,
851 null,
852 null,
853 null,
854 null,
855 );
856 }
857
858 const limits = ReplayCursor.Limits{
859 .db_path = "unused",
860 .namespace = null,
861 .max_entries = 7,
862 .max_choices = 11,
863 .max_byte_blocks = 13,
864 };
865 const capacity = try ReplayCursor.Capacity.derive(limits);
866 const expected_names = limits.max_entries * failure_name_bytes;
867 const expected_encoded = header_bytes + limits.max_choices * choice_bytes +
868 limits.max_byte_blocks;
869 const expected_choices = limits.max_choices * @sizeOf(ChoiceNode);
870 try std.testing.expectEqual(expected_names, capacity.name_bytes);
871 try std.testing.expectEqual(expected_encoded, capacity.encoded_bytes);
872 try std.testing.expectEqual(
873 expected_names + expected_encoded + expected_choices,
874 capacity.total_bytes,
875 );
876 }
877
878 test "replay cursor admits at most the requested directory prefix" {
879 const allocator = std.testing.allocator;
880 var tmp = std.testing.tmpDir(.{});
881 defer tmp.cleanup();
882 const tmp_path = try tmp.dir.realPathFileAlloc(std.Options.debug_io, ".", allocator);
883 defer allocator.free(tmp_path);
884 for (0..3) |value| {
885 try saveFailure(
886 allocator,
887 tmp_path,
888 "bounded",
889 &.{.{ .kind = .integer, .value = value }},
890 null,
891 );
892 }
893 var cursor = try ReplayCursor.init(allocator, .{
894 .db_path = tmp_path,
895 .namespace = "bounded",
896 .max_entries = 2,
897 .max_choices = 1,
898 .max_byte_blocks = 0,
899 });
900 defer cursor.deinit(allocator);
901 cursor.activate();
902 var loaded: usize = 0;
903 while (try cursor.next()) |_| loaded += 1;
904 try std.testing.expectEqual(@as(usize, 2), loaded);
905 try std.testing.expectEqual(@as(usize, 2), cursor.status().entries_scanned);
906 try std.testing.expect(cursor.status().scan_budget_saturated);
907 }
908
909 test "replay cursor accepts exact failure capacity and rejects max plus one" {
910 const allocator = std.testing.allocator;
911 var tmp = std.testing.tmpDir(.{});
912 defer tmp.cleanup();
913 const tmp_path = try tmp.dir.realPathFileAlloc(std.Options.debug_io, ".", allocator);
914 defer allocator.free(tmp_path);
915 const first = ChoiceNode{ .kind = .integer, .value = 1 };
916 const second = ChoiceNode{ .kind = .integer, .value = 2 };
917 try saveFailure(allocator, tmp_path, "capacity", &.{first}, "a");
918 try saveFailure(allocator, tmp_path, "capacity", &.{ first, second }, "a");
919 try saveFailure(allocator, tmp_path, "capacity", &.{first}, "ab");
920 var cursor = try ReplayCursor.init(allocator, .{
921 .db_path = tmp_path,
922 .namespace = "capacity",
923 .max_entries = 3,
924 .max_choices = 1,
925 .max_byte_blocks = 1,
926 });
927 defer cursor.deinit(allocator);
928 cursor.activate();
929 var loaded: usize = 0;
930 while (try cursor.next()) |_| loaded += 1;
931 try std.testing.expectEqual(@as(usize, 1), loaded);
932 try std.testing.expectEqual(@as(usize, 2), cursor.status().failures_rejected);
933 }
934
935 test "replay cursor keeps pointers stable with zero steady allocator operations" {
936 comptime {
937 @stardustClaim(
938 @import("alloc_phase").capacity.witness(ReplayCursor, "hypothesis_replay_sealed"),
939 null,
940 null,
941 null,
942 null,
943 null,
944 null,
945 );
946 }
947
948 const allocator = std.testing.allocator;
949 var tmp = std.testing.tmpDir(.{});
950 defer tmp.cleanup();
951 const tmp_path = try tmp.dir.realPathFileAlloc(std.Options.debug_io, ".", allocator);
952 defer allocator.free(tmp_path);
953 try saveFailure(allocator, tmp_path, "sealed", &.{.{ .kind = .integer, .value = 0 }}, "a");
954 try saveFailure(allocator, tmp_path, "sealed", &.{.{ .kind = .integer, .value = 1 }}, "b");
955
956 var observed = try alloc_phase.ObservingPhaseAllocator.init(allocator);
957 var cursor = try ReplayCursor.init(observed.initializationAllocator(), .{
958 .db_path = tmp_path,
959 .namespace = "sealed",
960 .max_entries = 2,
961 .max_choices = 1,
962 .max_byte_blocks = 1,
963 });
964 cursor.activate();
965 observed.seal();
966 const encoded_pointer = cursor.encoded.ptr;
967 const choice_pointer = cursor.choices.ptr;
968 var loaded: usize = 0;
969 while (try cursor.next()) |_| loaded += 1;
970 try std.testing.expectEqual(@as(usize, 2), loaded);
971 try std.testing.expectEqual(encoded_pointer, cursor.encoded.ptr);
972 try std.testing.expectEqual(choice_pointer, cursor.choices.ptr);
973 try std.testing.expectEqual(@as(u64, 0), observed.violations().total());
974 observed.beginTeardown();
975 cursor.deinit(observed.teardownAllocator());
976 observed.deinit();
977 }
978
979 test "replay cursor surfaces every initialization OOM and retries" {
980 comptime {
981 @stardustClaim(
982 @import("alloc_phase").capacity.witness(ReplayCursor, "hypothesis_replay_oom_retry"),
983 null,
984 null,
985 null,
986 null,
987 null,
988 null,
989 );
990 }
991
992 const allocator = std.testing.allocator;
993 var tmp = std.testing.tmpDir(.{});
994 defer tmp.cleanup();
995 const tmp_path = try tmp.dir.realPathFileAlloc(std.Options.debug_io, ".", allocator);
996 defer allocator.free(tmp_path);
997 var choices: [128]ChoiceNode = undefined;
998 for (&choices, 0..) |*choice, index| {
999 choice.* = .{ .kind = .integer, .value = @intCast(index) };
1000 }
1001 try saveFailure(allocator, tmp_path, "oom", &choices, "first");
1002 choices[0].value = 1_000;
1003 try saveFailure(allocator, tmp_path, "oom", &choices, "second");
1004 try std.testing.checkAllAllocationFailures(
1005 allocator,
1006 checkReplayCursorAllocationFailures,
1007 .{ tmp_path, "oom", @as(usize, 2) },
1008 );
1009 try checkReplayCursorAllocationFailures(allocator, tmp_path, "oom", 2);
1010 }