lib/choir/src/properties/patterns.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const ir = choir.ir;
2 const rewrite = ir.rewrite;
3 const std = @import("std");
4 const hypothesis = @import("hypothesis");
5 const choir = @import("choir");
6
7 fn settings() hypothesis.Settings {
8 var value = hypothesis.Settings.quick()
9 .withSeed(0x7a77_e200_2026_0710)
10 .withDatabase("zig-out/hypothesis-failures/choir-pattern-root-index");
11 value.max_examples = 100;
12 value.target_examples = 100;
13 return value;
14 }
15
16 fn drawUsize(conjecture: *hypothesis.ConjectureData, min: usize, max: usize, shrink_towards: usize) !usize {
17 return @intCast(try conjecture.drawInteger(@intCast(min), @intCast(max), @intCast(shrink_towards)));
18 }
19
20 fn accept(_: *choir.Operation) bool {
21 return true;
22 }
23
24 fn reject(_: *choir.Operation) bool {
25 return false;
26 }
27
28 fn noRewrite(_: *choir.Operation, _: *rewrite.PatternRewriter) rewrite.PatternResult {
29 return .failure;
30 }
31
32 pub const PatternRootIndexProperty = struct {
33 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
34 const root_count = try drawUsize(conjecture, 1, 64, 1);
35 const pattern_count = try drawUsize(conjecture, root_count, 256, root_count);
36 try conjecture.target(root_count, "root count");
37 try conjecture.target(pattern_count, "pattern count");
38
39 const root_names = try allocator.alloc([]u8, root_count);
40 defer {
41 for (root_names) |name| allocator.free(name);
42 allocator.free(root_names);
43 }
44 for (root_names, 0..) |*name, index| {
45 name.* = try std.fmt.allocPrint(allocator, "test.pattern_root_{d}", .{index});
46 }
47
48 var ctx = try choir.Context.init(allocator, choir.Context.Limits.testing);
49 defer ctx.deinit(allocator);
50 try ctx.allowUnregistered();
51
52 const root_ops = try allocator.alloc(*choir.Operation, root_count);
53 defer allocator.free(root_ops);
54 for (root_names, 0..) |name, index| {
55 root_ops[index] = try ctx.createOperation(choir.Operation.State.init(name, .unknown));
56 }
57 const absent_op = try ctx.createOperation(choir.Operation.State.init("test.pattern_root_absent", .unknown));
58
59 const root_indexes = try allocator.alloc(usize, pattern_count);
60 defer allocator.free(root_indexes);
61 const predicate_modes = try allocator.alloc(u2, pattern_count);
62 defer allocator.free(predicate_modes);
63
64 var patterns = rewrite.RewritePatternSet.init(allocator);
65 defer patterns.deinit();
66
67 for (0..pattern_count) |index| {
68 const root_index = if (index < root_count)
69 index
70 else
71 try drawUsize(conjecture, 0, root_count - 1, 0);
72 const benefit: rewrite.PatternBenefit = @intCast(try drawUsize(conjecture, 0, 15, 0));
73 const predicate_mode: u2 = @intCast(try drawUsize(conjecture, 0, 2, 0));
74 root_indexes[index] = root_index;
75 predicate_modes[index] = predicate_mode;
76
77 const spec = rewrite.RewritePatternSpec{
78 .name = root_names[root_index],
79 .root_op_name = root_names[root_index],
80 .benefit = benefit,
81 };
82 const pattern = switch (predicate_mode) {
83 0 => rewrite.RewritePattern.init(spec, noRewrite),
84 1 => rewrite.RewritePattern.initWithMatch(spec, accept, noRewrite),
85 2 => rewrite.RewritePattern.initWithMatch(spec, reject, noRewrite),
86 else => unreachable,
87 };
88 try patterns.add(pattern);
89 }
90 try patterns.seal();
91
92 var largest_bucket: usize = 0;
93 for (root_ops, 0..) |op, root_index| {
94 const matching = patterns.getMatchingPatterns(op);
95 largest_bucket = @max(largest_bucket, matching.len);
96
97 var expected_count: usize = 0;
98 for (root_indexes) |candidate_root| {
99 if (candidate_root == root_index) expected_count += 1;
100 }
101 try std.testing.expectEqual(expected_count, matching.len);
102
103 var previous_benefit: ?rewrite.PatternBenefit = null;
104 var previous_order: usize = 0;
105 for (matching) |pattern| {
106 try std.testing.expectEqual(root_index, root_indexes[pattern.order]);
107 try std.testing.expectEqualStrings(root_names[root_index], pattern.spec.root_op_name);
108 const expected_match = predicate_modes[pattern.order] != 2;
109 try std.testing.expectEqual(expected_match, pattern.matchesAfterRoot(op));
110 try std.testing.expectEqual(expected_match, pattern.matches(op));
111 try std.testing.expect(!pattern.matches(absent_op));
112
113 if (previous_benefit) |benefit| {
114 try std.testing.expect(benefit >= pattern.spec.benefit);
115 if (benefit == pattern.spec.benefit) {
116 try std.testing.expect(previous_order < pattern.order);
117 }
118 }
119 previous_benefit = pattern.spec.benefit;
120 previous_order = pattern.order;
121 }
122 }
123 try conjecture.target(largest_bucket, "largest root bucket");
124 try std.testing.expectEqual(@as(usize, 0), patterns.getMatchingPatterns(absent_op).len);
125 }
126 };
127
128 test "property: rewrite pattern root index exactly prefilters candidates" {
129 try hypothesis.checkNamed(PatternRootIndexProperty, "choir-pattern-root-index", settings());
130 }