lib/hypothesis/src/composites.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 DrawError = conjecture.DrawError;
6 const engine = @import("engine.zig");
7 const strategy_mod = @import("strategy.zig");
8 const Strategy = strategy_mod.Strategy;
9
10 pub fn ListStrategy(comptime T: type) type {
11 return struct {
12 element: Strategy(T),
13 min_len: usize,
14 max_len: usize,
15
16 const Self = @This();
17
18 pub fn draw(self: *const Self, data: *ConjectureData, allocator: Allocator) DrawError![]const T {
19 try data.beginSpan("list");
20
21 var items = std.ArrayListUnmanaged(T).empty;
22 errdefer items.deinit(allocator);
23
24 for (0..self.min_len) |_| {
25 const item = try self.element.draw(data, allocator);
26 try items.append(allocator, item);
27 }
28
29 while (items.items.len < self.max_len) {
30 const more = try data.drawBoolean();
31 if (!more) break;
32 const item = try self.element.draw(data, allocator);
33 try items.append(allocator, item);
34 }
35
36 data.endSpan();
37 return items.items;
38 }
39
40 pub fn strategy(self: *const Self) Strategy([]const T) {
41 return Strategy([]const T).from(Self, self);
42 }
43 };
44 }
45
46 pub fn lists(comptime T: type, element: Strategy(T)) ListStrategy(T) {
47 return listsWithLength(T, element, 0, 50);
48 }
49
50 pub fn listsWithLength(comptime T: type, element: Strategy(T), min_len: usize, max_len: usize) ListStrategy(T) {
51 return .{
52 .element = element,
53 .min_len = min_len,
54 .max_len = max_len,
55 };
56 }
57
58 pub const StringStrategy = struct {
59 charset: []const u8,
60 min_len: usize,
61 max_len: usize,
62
63 pub fn draw(self: *const StringStrategy, data: *ConjectureData, allocator: Allocator) DrawError![]const u8 {
64 std.debug.assert(self.charset.len > 0);
65 std.debug.assert(self.min_len <= self.max_len);
66 try data.beginSpan("string");
67
68 var items = std.ArrayListUnmanaged(u8).empty;
69 errdefer items.deinit(allocator);
70
71 for (0..self.min_len) |_| {
72 const ch = try strategy_mod.drawCharFromCharset(data, self.charset);
73 try items.append(allocator, ch);
74 }
75
76 while (items.items.len < self.max_len) {
77 const more = try data.drawBoolean();
78 if (!more) break;
79 const ch = try strategy_mod.drawCharFromCharset(data, self.charset);
80 try items.append(allocator, ch);
81 }
82
83 data.endSpan();
84 return items.items;
85 }
86
87 pub fn strategy(self: *const StringStrategy) Strategy([]const u8) {
88 return Strategy([]const u8).from(StringStrategy, self);
89 }
90 };
91
92 pub fn strings(charset: []const u8, min_len: usize, max_len: usize) StringStrategy {
93 std.debug.assert(charset.len > 0);
94 std.debug.assert(min_len <= max_len);
95 return .{
96 .charset = charset,
97 .min_len = min_len,
98 .max_len = max_len,
99 };
100 }
101
102 pub fn asciiStrings(min_len: usize, max_len: usize) StringStrategy {
103 return strings(strategy_mod.ascii_printable, min_len, max_len);
104 }
105
106 pub fn alphanumeric(min_len: usize, max_len: usize) StringStrategy {
107 return strings(strategy_mod.alphanumeric, min_len, max_len);
108 }
109
110 pub fn urlSafeTokens(min_len: usize, max_len: usize) StringStrategy {
111 return strings(strategy_mod.url_safe_tokens, min_len, max_len);
112 }
113
114 pub const SplitPointsStrategy = struct {
115 total_len: usize,
116
117 pub fn draw(self: *const SplitPointsStrategy, data: *ConjectureData, allocator: Allocator) DrawError![]const usize {
118 try data.beginSpan("split_points");
119
120 var items = std.ArrayListUnmanaged(usize).empty;
121 errdefer items.deinit(allocator);
122
123 const max_points: usize = self.total_len + 1;
124 const count_raw = try data.drawInteger(0, @intCast(max_points), 0);
125 const count: usize = @intCast(count_raw);
126
127 var prev: usize = 0;
128 for (0..count) |i| {
129 const remaining = count - i - 1;
130 const min_val: usize = if (i == 0) 0 else prev + 1;
131 const max_val: usize = self.total_len - remaining;
132 const raw = try data.drawInteger(@intCast(min_val), @intCast(max_val), @intCast(min_val));
133 const val: usize = @intCast(raw);
134 try items.append(allocator, val);
135 prev = val;
136 }
137
138 data.endSpan();
139 return items.items;
140 }
141
142 pub fn strategy(self: *const SplitPointsStrategy) Strategy([]const usize) {
143 return Strategy([]const usize).from(SplitPointsStrategy, self);
144 }
145 };
146
147 pub fn splitPoints(total_len: usize) SplitPointsStrategy {
148 return .{ .total_len = total_len };
149 }
150
151 pub const PermutationStrategy = struct {
152 count: usize,
153
154 pub fn draw(self: *const PermutationStrategy, data: *ConjectureData, allocator: Allocator) DrawError![]const usize {
155 try data.beginSpan("permutation");
156 defer data.endSpan();
157
158 const items = try allocator.alloc(usize, self.count);
159 errdefer allocator.free(items);
160
161 for (items, 0..) |*slot, idx| {
162 slot.* = idx;
163 }
164
165 if (self.count <= 1) return items;
166
167 var i: usize = 0;
168 while (i + 1 < self.count) : (i += 1) {
169 const j_raw = try data.drawInteger(@intCast(i), @intCast(self.count - 1), @intCast(i));
170 const j: usize = @intCast(j_raw);
171 if (j != i) {
172 const tmp = items[i];
173 items[i] = items[j];
174 items[j] = tmp;
175 }
176 }
177
178 return items;
179 }
180
181 pub fn strategy(self: *const PermutationStrategy) Strategy([]const usize) {
182 return Strategy([]const usize).from(PermutationStrategy, self);
183 }
184 };
185
186 pub fn permutations(count: usize) PermutationStrategy {
187 return .{ .count = count };
188 }
189
190 pub fn ShuffleStrategy(comptime T: type) type {
191 return struct {
192 source: []const T,
193
194 const Self = @This();
195
196 pub fn draw(self: *const Self, data: *ConjectureData, allocator: Allocator) DrawError![]const T {
197 try data.beginSpan("shuffle");
198 defer data.endSpan();
199
200 const out = try allocator.alloc(T, self.source.len);
201 errdefer allocator.free(out);
202 @memcpy(out, self.source);
203
204 if (self.source.len <= 1) return out;
205
206 var i: usize = 0;
207 while (i + 1 < self.source.len) : (i += 1) {
208 const j_raw = try data.drawInteger(@intCast(i), @intCast(self.source.len - 1), @intCast(i));
209 const j: usize = @intCast(j_raw);
210 if (j != i) {
211 const tmp = out[i];
212 out[i] = out[j];
213 out[j] = tmp;
214 }
215 }
216
217 return out;
218 }
219
220 pub fn strategy(self: *const Self) Strategy([]const T) {
221 return Strategy([]const T).from(Self, self);
222 }
223 };
224 }
225
226 pub fn shuffle(comptime T: type, slice: []const T) ShuffleStrategy(T) {
227 return .{ .source = slice };
228 }
229
230 pub fn OptionalStrategy(comptime T: type) type {
231 return struct {
232 inner: Strategy(T),
233
234 const Self = @This();
235
236 pub fn draw(self: *const Self, data: *ConjectureData, allocator: Allocator) DrawError!?T {
237 const present = try data.drawBoolean();
238 if (!present) return null;
239 return try self.inner.draw(data, allocator);
240 }
241
242 pub fn strategy(self: *const Self) Strategy(?T) {
243 return Strategy(?T).from(Self, self);
244 }
245 };
246 }
247
248 pub fn optionals(comptime T: type, inner: Strategy(T)) OptionalStrategy(T) {
249 return .{ .inner = inner };
250 }
251
252 pub fn OneOfStrategy(comptime T: type, comptime N: usize) type {
253 return struct {
254 alternatives: [N]Strategy(T),
255
256 const Self = @This();
257
258 pub fn draw(self: *const Self, data: *ConjectureData, allocator: Allocator) DrawError!T {
259 const idx = try data.drawInteger(0, N - 1, 0);
260 return self.alternatives[@intCast(idx)].draw(data, allocator);
261 }
262
263 pub fn strategy(self: *const Self) Strategy(T) {
264 return Strategy(T).from(Self, self);
265 }
266 };
267 }
268
269 pub fn oneOf(comptime T: type, comptime N: usize, alternatives: [N]Strategy(T)) OneOfStrategy(T, N) {
270 return .{ .alternatives = alternatives };
271 }
272
273 pub fn MapStrategy(comptime From: type, comptime To: type) type {
274 return struct {
275 source: Strategy(From),
276 mapFn: *const fn (From) To,
277
278 const Self = @This();
279
280 pub fn draw(self: *const Self, data: *ConjectureData, allocator: Allocator) DrawError!To {
281 const from_val = try self.source.draw(data, allocator);
282 return self.mapFn(from_val);
283 }
284
285 pub fn strategy(self: *const Self) Strategy(To) {
286 return Strategy(To).from(Self, self);
287 }
288 };
289 }
290
291 pub fn map(comptime From: type, comptime To: type, source: Strategy(From), mapFn: *const fn (From) To) MapStrategy(From, To) {
292 return .{
293 .source = source,
294 .mapFn = mapFn,
295 };
296 }
297
298 pub fn FilterStrategy(comptime T: type) type {
299 return struct {
300 source: Strategy(T),
301 predFn: *const fn (T) bool,
302 max_retries: usize,
303
304 const Self = @This();
305
306 pub fn draw(self: *const Self, data: *ConjectureData, allocator: Allocator) DrawError!T {
307 for (0..self.max_retries) |_| {
308 const val = try self.source.draw(data, allocator);
309 if (self.predFn(val)) return val;
310 data.markInvalid();
311 }
312 return self.source.draw(data, allocator);
313 }
314
315 pub fn strategy(self: *const Self) Strategy(T) {
316 return Strategy(T).from(Self, self);
317 }
318 };
319 }
320
321 pub fn filter(comptime T: type, source: Strategy(T), predFn: *const fn (T) bool) FilterStrategy(T) {
322 return filterWithRetries(T, source, predFn, 100);
323 }
324
325 pub fn filterWithRetries(
326 comptime T: type,
327 source: Strategy(T),
328 predFn: *const fn (T) bool,
329 max_retries: usize,
330 ) FilterStrategy(T) {
331 return .{
332 .source = source,
333 .predFn = predFn,
334 .max_retries = max_retries,
335 };
336 }
337
338 pub fn FlatMapStrategy(comptime From: type, comptime To: type) type {
339 return struct {
340 source: Strategy(From),
341 bindFn: *const fn (From, Allocator) Strategy(To),
342
343 const Self = @This();
344
345 pub fn draw(self: *const Self, data: *ConjectureData, allocator: Allocator) DrawError!To {
346 const from_val = try self.source.draw(data, allocator);
347 const to_strategy = self.bindFn(from_val, allocator);
348 return to_strategy.draw(data, allocator);
349 }
350
351 pub fn strategy(self: *const Self) Strategy(To) {
352 return Strategy(To).from(Self, self);
353 }
354 };
355 }
356
357 pub fn flatMap(
358 comptime From: type,
359 comptime To: type,
360 source: Strategy(From),
361 bindFn: *const fn (From, Allocator) Strategy(To),
362 ) FlatMapStrategy(From, To) {
363 return .{
364 .source = source,
365 .bindFn = bindFn,
366 };
367 }
368
369 test "lists strategy draws lists" {
370 var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
371 defer arena.deinit();
372 const allocator = arena.allocator();
373
374 var data = ConjectureData.init(allocator, 42);
375 defer data.deinit();
376
377 const elem = strategy_mod.integers(u8, 0, 255);
378 const s = lists(u8, elem.strategy());
379 for (0..10) |_| {
380 const xs = try s.strategy().draw(&data, allocator);
381 for (xs) |x| {
382 try std.testing.expect(x <= 255);
383 }
384 }
385 }
386
387 test "string strategy draws strings in charset" {
388 var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
389 defer arena.deinit();
390 const allocator = arena.allocator();
391
392 var data = ConjectureData.init(allocator, 4242);
393 defer data.deinit();
394
395 const charset = "ab01";
396 const s = strings(charset, 2, 8);
397 for (0..40) |_| {
398 const value = try s.strategy().draw(&data, allocator);
399 try std.testing.expect(value.len >= 2 and value.len <= 8);
400 for (value) |ch| {
401 try std.testing.expect(std.mem.indexOfScalar(u8, charset, ch) != null);
402 }
403 }
404 }
405
406 test "asciiStrings draws printable ASCII" {
407 var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
408 defer arena.deinit();
409 const allocator = arena.allocator();
410
411 var data = ConjectureData.init(allocator, 123);
412 defer data.deinit();
413
414 const s = asciiStrings(0, 12);
415 for (0..40) |_| {
416 const value = try s.strategy().draw(&data, allocator);
417 try std.testing.expect(value.len <= 12);
418 for (value) |ch| {
419 try std.testing.expect(std.mem.indexOfScalar(u8, strategy_mod.ascii_printable, ch) != null);
420 }
421 }
422 }
423
424 test "splitPoints strategy draws sorted indices" {
425 var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
426 defer arena.deinit();
427 const allocator = arena.allocator();
428
429 var data = ConjectureData.init(allocator, 2026);
430 defer data.deinit();
431
432 const total_len: usize = 12;
433 const s = splitPoints(total_len);
434 for (0..50) |_| {
435 const splits = try s.strategy().draw(&data, allocator);
436 var last: usize = 0;
437 for (splits, 0..) |val, idx| {
438 try std.testing.expect(val <= total_len);
439 if (idx > 0) try std.testing.expect(val > last);
440 last = val;
441 }
442 try std.testing.expect(splits.len <= total_len + 1);
443 }
444 }
445
446 test "permutations strategy draws permutations" {
447 var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
448 defer arena.deinit();
449 const allocator = arena.allocator();
450
451 var data = ConjectureData.init(allocator, 2027);
452 defer data.deinit();
453
454 const count: usize = 7;
455 const s = permutations(count);
456 for (0..50) |_| {
457 const perm = try s.strategy().draw(&data, allocator);
458 try std.testing.expectEqual(count, perm.len);
459
460 var seen = @as([count]bool, @splat(false));
461 for (perm) |val| {
462 try std.testing.expect(val < count);
463 if (seen[val]) return error.TestFailure;
464 seen[val] = true;
465 }
466 for (seen) |flag| {
467 try std.testing.expect(flag);
468 }
469 }
470 }
471
472 test "shuffle strategy returns shuffled copies" {
473 var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
474 defer arena.deinit();
475 const allocator = arena.allocator();
476
477 var data = ConjectureData.init(allocator, 5150);
478 defer data.deinit();
479
480 const source = [_]u8{ 1, 2, 3, 4, 5 };
481 const s = shuffle(u8, source[0..]);
482 for (0..40) |_| {
483 const out = try s.strategy().draw(&data, allocator);
484 try std.testing.expectEqual(source.len, out.len);
485
486 var seen = @as([source.len]bool, @splat(false));
487 for (out) |val| {
488 var idx_opt: ?usize = null;
489 for (source, 0..) |orig, idx| {
490 if (orig == val) {
491 idx_opt = idx;
492 break;
493 }
494 }
495 const idx = idx_opt orelse return error.TestFailure;
496 if (seen[idx]) return error.TestFailure;
497 seen[idx] = true;
498 }
499 for (seen) |flag| {
500 try std.testing.expect(flag);
501 }
502 }
503 }
504
505 test "optionals strategy draws optionals" {
506 const allocator = std.testing.allocator;
507 var data = ConjectureData.init(allocator, 42);
508 defer data.deinit();
509
510 const inner = strategy_mod.integers(i32, 0, 100);
511 const s = optionals(i32, inner.strategy());
512 var saw_null = false;
513 var saw_some = false;
514 for (0..100) |_| {
515 const v = try s.strategy().draw(&data, allocator);
516 if (v) |_| saw_some = true else saw_null = true;
517 }
518 try std.testing.expect(saw_null and saw_some);
519 }
520
521 test "oneOf strategy selects from alternatives" {
522 const allocator = std.testing.allocator;
523 var data = ConjectureData.init(allocator, 42);
524 defer data.deinit();
525
526 const small = strategy_mod.integers(i32, 0, 10);
527 const big = strategy_mod.integers(i32, 1000, 2000);
528 const s = oneOf(i32, 2, .{ small.strategy(), big.strategy() });
529
530 var saw_small = false;
531 var saw_big = false;
532 for (0..100) |_| {
533 const v = try s.strategy().draw(&data, allocator);
534 if (v <= 10) saw_small = true;
535 if (v >= 1000) saw_big = true;
536 }
537 try std.testing.expect(saw_small and saw_big);
538 }
539
540 const DoubleI32MapFixture = struct {
541 fn f(x: i32) i32 {
542 return x * 2;
543 }
544 };
545
546 const EvenI32FilterFixture = struct {
547 fn f(x: i32) bool {
548 return @mod(x, 2) == 0;
549 }
550 };
551
552 test "map strategy transforms values" {
553 const allocator = std.testing.allocator;
554 var data = ConjectureData.init(allocator, 42);
555 defer data.deinit();
556
557 const source = strategy_mod.integers(i32, 1, 10);
558 const doubled = map(i32, i32, source.strategy(), &DoubleI32MapFixture.f);
559
560 for (0..50) |_| {
561 const v = try doubled.strategy().draw(&data, allocator);
562 try std.testing.expect(v >= 2 and v <= 20);
563 try std.testing.expect(@mod(v, 2) == 0);
564 }
565 }
566
567 test "filter strategy filters values" {
568 const allocator = std.testing.allocator;
569 var data = ConjectureData.init(allocator, 42);
570 defer data.deinit();
571
572 const source = strategy_mod.integers(i32, 0, 100);
573 const evens = filter(i32, source.strategy(), &EvenI32FilterFixture.f);
574
575 for (0..50) |_| {
576 const v = try evens.strategy().draw(&data, allocator);
577 _ = v;
578 }
579 }
580
581 const UrlSafeTokenPropertyFixture = struct {
582 fn property(data: *ConjectureData, gpa: Allocator) anyerror!void {
583 var arena = std.heap.ArenaAllocator.init(gpa);
584 defer arena.deinit();
585 const arena_alloc = arena.allocator();
586
587 const s = urlSafeTokens(0, 24);
588 const value = try s.strategy().draw(data, arena_alloc);
589 for (value) |ch| {
590 if (std.mem.indexOfScalar(u8, strategy_mod.url_safe_tokens, ch) == null) {
591 return error.PropertyFailed;
592 }
593 }
594 }
595 };
596
597 test "string strategy property uses engine" {
598 const allocator = std.testing.allocator;
599 const settings = engine.Settings{ .max_examples = 100, .seed = 77 };
600
601 var result = try engine.run(allocator, &UrlSafeTokenPropertyFixture.property, settings);
602 defer result.deinit();
603 try std.testing.expect(result.passed);
604 }