lib/hypothesis/src/conjecture.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const Allocator = std.mem.Allocator;
3
4 pub const ChoiceKind = enum(u8) {
5 integer,
6 boolean,
7 float,
8 bytes,
9 };
10
11 pub const ChoiceNode = struct {
12 kind: ChoiceKind,
13 value: u64,
14 min: u64 = 0,
15 max: u64 = std.math.maxInt(u64),
16 shrink_towards: u64 = 0,
17 was_forced: bool = false,
18 };
19
20 pub const Span = struct {
21 label: []const u8,
22 start: usize,
23 end: usize,
24 depth: usize,
25 };
26
27 pub const Status = enum {
28 valid,
29 invalid,
30 interesting,
31 overrun,
32 };
33
34 pub const DrawError = error{
35 Overrun,
36 OutOfMemory,
37 };
38
39 pub const default_max_input_bytes: usize = 1024 * 1024;
40
41 pub const TargetError = error{
42 DuplicateTargetLabel,
43 NonFiniteTarget,
44 OutOfMemory,
45 };
46
47 pub const TargetObservation = struct {
48 label: []const u8,
49 value: f64,
50 };
51
52 pub const ConjectureData = struct {
53 choices: std.ArrayListUnmanaged(ChoiceNode) = .empty,
54 spans: std.ArrayListUnmanaged(Span) = .empty,
55 byte_blocks: std.ArrayListUnmanaged(u8) = .empty,
56 targets: std.ArrayListUnmanaged(TargetObservation) = .empty,
57 span_depth: usize = 0,
58 status: Status = .valid,
59 max_choices: usize = 4096,
60 max_input_bytes: usize = default_max_input_bytes,
61
62 prng: std.Random.DefaultPrng,
63
64 replay_choices: ?[]const ChoiceNode = null,
65 replay_byte_blocks: ?[]const u8 = null,
66 replay_index: usize = 0,
67 replay_byte_offset: usize = 0,
68
69 allocator: Allocator,
70
71 pub fn init(allocator: Allocator, seed: u64) ConjectureData {
72 return .{
73 .prng = std.Random.DefaultPrng.init(seed),
74 .allocator = allocator,
75 };
76 }
77
78 pub fn initReplay(
79 allocator: Allocator,
80 replay_choices: []const ChoiceNode,
81 replay_byte_blocks: ?[]const u8,
82 ) ConjectureData {
83 return .{
84 .prng = std.Random.DefaultPrng.init(0),
85 .replay_choices = replay_choices,
86 .replay_byte_blocks = replay_byte_blocks,
87 .allocator = allocator,
88 };
89 }
90
91 pub fn deinit(self: *ConjectureData) void {
92 self.clearTargets();
93 self.choices.deinit(self.allocator);
94 self.spans.deinit(self.allocator);
95 self.byte_blocks.deinit(self.allocator);
96 self.targets.deinit(self.allocator);
97 }
98
99 pub fn beginSpan(self: *ConjectureData, label: []const u8) !void {
100 try self.spans.append(self.allocator, .{
101 .label = label,
102 .start = self.choices.items.len,
103 .end = 0,
104 .depth = self.span_depth,
105 });
106 self.span_depth += 1;
107 }
108
109 pub fn endSpan(self: *ConjectureData) void {
110 std.debug.assert(self.span_depth > 0);
111 self.span_depth -= 1;
112 var i = self.spans.items.len;
113 while (i > 0) {
114 i -= 1;
115 if (self.spans.items[i].depth == self.span_depth and
116 self.spans.items[i].end == 0)
117 {
118 self.spans.items[i].end = self.choices.items.len;
119 return;
120 }
121 }
122 }
123
124 pub fn drawInteger(
125 self: *ConjectureData,
126 min: u64,
127 max: u64,
128 shrink_towards: u64,
129 ) DrawError!u64 {
130 if (self.choices.items.len >= self.max_choices) {
131 self.status = .overrun;
132 return DrawError.Overrun;
133 }
134
135 const value = if (self.replay_choices) |replay| blk: {
136 if (self.replay_index >= replay.len) {
137 self.status = .overrun;
138 return DrawError.Overrun;
139 }
140 const node = replay[self.replay_index];
141 self.replay_index += 1;
142 break :blk node.value;
143 } else blk: {
144 if (min == max) break :blk min;
145 const range = max -% min;
146 break :blk min +% self.prng.random().intRangeAtMost(u64, 0, range);
147 };
148
149 const clamped = @min(@max(value, min), max);
150
151 try self.choices.append(self.allocator, .{
152 .kind = .integer,
153 .value = clamped,
154 .min = min,
155 .max = max,
156 .shrink_towards = shrink_towards,
157 });
158
159 return clamped;
160 }
161
162 pub fn drawBoolean(self: *ConjectureData) DrawError!bool {
163 const value = try self.drawInteger(0, 1, 0);
164 return value != 0;
165 }
166
167 pub fn drawFloat(
168 self: *ConjectureData,
169 min: f64,
170 max: f64,
171 ) DrawError!f64 {
172 if (self.choices.items.len >= self.max_choices) {
173 self.status = .overrun;
174 return DrawError.Overrun;
175 }
176
177 const value = if (self.replay_choices) |replay| blk: {
178 if (self.replay_index >= replay.len) {
179 self.status = .overrun;
180 return DrawError.Overrun;
181 }
182 const node = replay[self.replay_index];
183 self.replay_index += 1;
184 break :blk @as(f64, @bitCast(node.value));
185 } else blk: {
186 const r = self.prng.random();
187 const unit: f64 = @as(f64, @floatFromInt(r.int(u52))) /
188 @as(f64, @floatFromInt(@as(u52, std.math.maxInt(u52))));
189 break :blk min + unit * (max - min);
190 };
191
192 const clamped = @min(@max(value, min), max);
193
194 try self.choices.append(self.allocator, .{
195 .kind = .float,
196 .value = @bitCast(clamped),
197 .min = @bitCast(min),
198 .max = @bitCast(max),
199 .shrink_towards = @bitCast(@as(f64, 0.0)),
200 });
201
202 return clamped;
203 }
204
205 pub fn drawBytes(
206 self: *ConjectureData,
207 min_size: usize,
208 max_size: usize,
209 ) DrawError![]const u8 {
210 const len = try self.drawInteger(
211 @intCast(min_size),
212 @intCast(max_size),
213 @intCast(min_size),
214 );
215
216 const start = self.byte_blocks.items.len;
217 const size: usize = @intCast(len);
218 std.debug.assert(start <= self.max_input_bytes);
219 if (size > self.max_input_bytes - start) {
220 self.status = .overrun;
221 return DrawError.Overrun;
222 }
223
224 if (self.replay_byte_blocks) |replay_bytes| {
225 if (self.replay_byte_offset + size > replay_bytes.len) {
226 self.status = .overrun;
227 return DrawError.Overrun;
228 }
229 try self.byte_blocks.appendSlice(
230 self.allocator,
231 replay_bytes[self.replay_byte_offset..][0..size],
232 );
233 self.replay_byte_offset += size;
234 } else {
235 try self.byte_blocks.ensureUnusedCapacity(self.allocator, size);
236 for (0..size) |_| {
237 self.byte_blocks.appendAssumeCapacity(
238 self.prng.random().int(u8),
239 );
240 }
241 }
242
243 return self.byte_blocks.items[start..][0..size];
244 }
245
246 pub fn forceInteger(self: *ConjectureData, value: u64) DrawError!void {
247 if (self.choices.items.len >= self.max_choices) {
248 self.status = .overrun;
249 return DrawError.Overrun;
250 }
251 try self.choices.append(self.allocator, .{
252 .kind = .integer,
253 .value = value,
254 .min = value,
255 .max = value,
256 .shrink_towards = value,
257 .was_forced = true,
258 });
259 }
260
261 pub fn target(self: *ConjectureData, observation: anytype, label: []const u8) TargetError!void {
262 const value = targetValue(@TypeOf(observation), observation);
263 if (!std.math.isFinite(value)) return TargetError.NonFiniteTarget;
264 for (self.targets.items) |existing| {
265 if (std.mem.eql(u8, existing.label, label)) {
266 return TargetError.DuplicateTargetLabel;
267 }
268 }
269 const owned_label = try self.allocator.dupe(u8, label);
270 errdefer self.allocator.free(owned_label);
271 try self.targets.append(self.allocator, .{
272 .label = owned_label,
273 .value = value,
274 });
275 }
276
277 pub fn targetDefault(self: *ConjectureData, observation: anytype) TargetError!void {
278 return self.target(observation, "");
279 }
280
281 pub fn markInteresting(self: *ConjectureData) void {
282 self.status = .interesting;
283 }
284
285 pub fn markInvalid(self: *ConjectureData) void {
286 self.status = .invalid;
287 }
288
289 pub fn reset(self: *ConjectureData, seed: u64) void {
290 self.clearTargets();
291 self.choices.clearRetainingCapacity();
292 self.spans.clearRetainingCapacity();
293 self.byte_blocks.clearRetainingCapacity();
294 self.span_depth = 0;
295 self.status = .valid;
296 self.prng = std.Random.DefaultPrng.init(seed);
297 self.replay_choices = null;
298 self.replay_byte_blocks = null;
299 self.replay_index = 0;
300 self.replay_byte_offset = 0;
301 }
302
303 pub fn resetReplay(
304 self: *ConjectureData,
305 replay_choices: []const ChoiceNode,
306 replay_byte_blocks: ?[]const u8,
307 ) void {
308 self.clearTargets();
309 self.choices.clearRetainingCapacity();
310 self.spans.clearRetainingCapacity();
311 self.byte_blocks.clearRetainingCapacity();
312 self.span_depth = 0;
313 self.status = .valid;
314 self.replay_choices = replay_choices;
315 self.replay_byte_blocks = replay_byte_blocks;
316 self.replay_index = 0;
317 self.replay_byte_offset = 0;
318 }
319
320 fn clearTargets(self: *ConjectureData) void {
321 for (self.targets.items) |target_observation| {
322 self.allocator.free(target_observation.label);
323 }
324 self.targets.clearRetainingCapacity();
325 }
326 };
327
328 pub fn target(data: *ConjectureData, observation: anytype, label: []const u8) TargetError!void {
329 return data.target(observation, label);
330 }
331
332 fn targetValue(comptime T: type, value: T) f64 {
333 return switch (@typeInfo(T)) {
334 .int, .comptime_int => @floatFromInt(value),
335 .float, .comptime_float => @floatCast(value),
336 else => @compileError("target observation must be an integer or float"),
337 };
338 }
339
340 test "drawInteger produces values in range" {
341 const allocator = std.testing.allocator;
342 var data = ConjectureData.init(allocator, 42);
343 defer data.deinit();
344
345 for (0..100) |_| {
346 const v = try data.drawInteger(10, 20, 10);
347 try std.testing.expect(v >= 10 and v <= 20);
348 }
349 }
350
351 test "drawBoolean produces booleans" {
352 const allocator = std.testing.allocator;
353 var data = ConjectureData.init(allocator, 42);
354 defer data.deinit();
355
356 var saw_true = false;
357 var saw_false = false;
358 for (0..100) |_| {
359 const v = try data.drawBoolean();
360 if (v) saw_true = true else saw_false = true;
361 }
362 try std.testing.expect(saw_true and saw_false);
363 }
364
365 test "target records finite labeled observations" {
366 const allocator = std.testing.allocator;
367 var data = ConjectureData.init(allocator, 42);
368 defer data.deinit();
369
370 try data.target(12, "size");
371 try data.target(-3.5, "distance");
372
373 try std.testing.expectEqual(@as(usize, 2), data.targets.items.len);
374 try std.testing.expectEqualStrings("size", data.targets.items[0].label);
375 try std.testing.expectEqual(@as(f64, 12.0), data.targets.items[0].value);
376 try std.testing.expectEqualStrings("distance", data.targets.items[1].label);
377 try std.testing.expectEqual(@as(f64, -3.5), data.targets.items[1].value);
378 }
379
380 test "target rejects duplicate labels and non-finite observations" {
381 const allocator = std.testing.allocator;
382 var data = ConjectureData.init(allocator, 42);
383 defer data.deinit();
384
385 try data.target(1, "score");
386 try std.testing.expectError(TargetError.DuplicateTargetLabel, data.target(2, "score"));
387 try std.testing.expectError(TargetError.NonFiniteTarget, data.target(std.math.inf(f64), "inf"));
388 }
389
390 test "replay reproduces values" {
391 const allocator = std.testing.allocator;
392
393 var gen = ConjectureData.init(allocator, 123);
394 defer gen.deinit();
395 const v1 = try gen.drawInteger(0, 100, 0);
396 const v2 = try gen.drawInteger(0, 100, 0);
397 const v3 = try gen.drawBoolean();
398
399 var replay = ConjectureData.initReplay(allocator, gen.choices.items, null);
400 defer replay.deinit();
401 try std.testing.expectEqual(v1, try replay.drawInteger(0, 100, 0));
402 try std.testing.expectEqual(v2, try replay.drawInteger(0, 100, 0));
403 try std.testing.expectEqual(v3, try replay.drawBoolean());
404 }
405
406 test "overrun on too many choices" {
407 const allocator = std.testing.allocator;
408 var data = ConjectureData.init(allocator, 42);
409 defer data.deinit();
410 data.max_choices = 5;
411
412 for (0..5) |_| {
413 _ = try data.drawInteger(0, 10, 0);
414 }
415 try std.testing.expectError(DrawError.Overrun, data.drawInteger(0, 10, 0));
416 try std.testing.expectEqual(.overrun, data.status);
417 }
418
419 test "span tracking" {
420 const allocator = std.testing.allocator;
421 var data = ConjectureData.init(allocator, 42);
422 defer data.deinit();
423
424 try data.beginSpan("outer");
425 _ = try data.drawInteger(0, 10, 0);
426 try data.beginSpan("inner");
427 _ = try data.drawInteger(0, 10, 0);
428 data.endSpan();
429 _ = try data.drawInteger(0, 10, 0);
430 data.endSpan();
431
432 try std.testing.expectEqual(2, data.spans.items.len);
433 try std.testing.expectEqual(1, data.spans.items[1].start);
434 try std.testing.expectEqual(2, data.spans.items[1].end);
435 try std.testing.expectEqual(1, data.spans.items[1].depth);
436 try std.testing.expectEqual(0, data.spans.items[0].start);
437 try std.testing.expectEqual(3, data.spans.items[0].end);
438 try std.testing.expectEqual(0, data.spans.items[0].depth);
439 }
440
441 test "drawFloat produces values in range" {
442 const allocator = std.testing.allocator;
443 var data = ConjectureData.init(allocator, 42);
444 defer data.deinit();
445
446 for (0..100) |_| {
447 const v = try data.drawFloat(-1.0, 1.0);
448 try std.testing.expect(v >= -1.0 and v <= 1.0);
449 }
450 }
451
452 test "drawBytes produces bytes in size range" {
453 const allocator = std.testing.allocator;
454 var data = ConjectureData.init(allocator, 42);
455 defer data.deinit();
456
457 for (0..20) |_| {
458 const bs = try data.drawBytes(2, 8);
459 try std.testing.expect(bs.len >= 2 and bs.len <= 8);
460 }
461 }
462
463 test "drawBytes rejects cumulative max input plus one without growing bytes" {
464 var data = ConjectureData.init(std.testing.allocator, 42);
465 defer data.deinit();
466 data.max_input_bytes = 4;
467 _ = try data.drawBytes(2, 2);
468 _ = try data.drawBytes(2, 2);
469 const pointer = data.byte_blocks.items.ptr;
470 try std.testing.expectError(DrawError.Overrun, data.drawBytes(1, 1));
471 try std.testing.expectEqual(Status.overrun, data.status);
472 try std.testing.expectEqual(@as(usize, 4), data.byte_blocks.items.len);
473 try std.testing.expectEqual(pointer, data.byte_blocks.items.ptr);
474 }