lib/choir/src/core/rewrite/index.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ir = @import("../root.zig");
3 const alloc_phase = @import("alloc_phase");
4 const PatternBenefit = ir.rewrite.PatternBenefit;
5 const RewritePatternSpec = ir.rewrite.RewritePatternSpec;
6 const RewritePattern = ir.rewrite.RewritePattern;
7 const PatternResult = ir.rewrite.PatternResult;
8 const PatternRewriter = ir.rewrite.PatternRewriter;
9 const RewritePatternSet = ir.rewrite.RewritePatternSet;
10
11 const PatternOrdinal = u32;
12
13 const PatternRootSlot = struct {
14 name: ?[]const u8 = null,
15 start: PatternOrdinal = 0,
16 len: PatternOrdinal = 0,
17 };
18
19 const pattern_index_alignment = @max(
20 @alignOf(PatternRootSlot),
21 @alignOf(RewritePattern),
22 );
23
24 const PatternIndexFacts = struct {
25 pattern_count: usize,
26 };
27
28 const PatternIndexLimits = struct {
29 patterns: []const RewritePattern,
30 facts: PatternIndexFacts,
31
32 pub fn inspect(patterns: []const RewritePattern) error{CountOverflow}!PatternIndexLimits {
33 if (patterns.len > std.math.maxInt(PatternOrdinal)) return error.CountOverflow;
34 return .{
35 .patterns = patterns,
36 .facts = .{ .pattern_count = patterns.len },
37 };
38 }
39 };
40
41 const PatternIndexCapacity = struct {
42 facts: PatternIndexFacts,
43 slot_count: usize,
44 slots_offset: usize,
45 slots_bytes: usize,
46 patterns_offset: usize,
47 patterns_bytes: usize,
48 working_bytes: usize,
49
50 pub fn derive(limits: PatternIndexLimits) error{CapacityOverflow}!PatternIndexCapacity {
51 if (limits.facts.pattern_count > std.math.maxInt(PatternOrdinal)) {
52 return error.CapacityOverflow;
53 }
54 const slot_count = try patternRootSlotCount(limits.facts.pattern_count);
55 const slots_bytes = std.math.mul(
56 usize,
57 slot_count,
58 @sizeOf(PatternRootSlot),
59 ) catch return error.CapacityOverflow;
60 const patterns_bytes = std.math.mul(
61 usize,
62 limits.facts.pattern_count,
63 @sizeOf(RewritePattern),
64 ) catch return error.CapacityOverflow;
65 var cursor: usize = 0;
66 const slots_offset = try placePatternIndexBytes(
67 slots_bytes,
68 @alignOf(PatternRootSlot),
69 &cursor,
70 );
71 const patterns_offset = try placePatternIndexBytes(
72 patterns_bytes,
73 @alignOf(RewritePattern),
74 &cursor,
75 );
76 return .{
77 .facts = limits.facts,
78 .slot_count = slot_count,
79 .slots_offset = slots_offset,
80 .slots_bytes = slots_bytes,
81 .patterns_offset = patterns_offset,
82 .patterns_bytes = patterns_bytes,
83 .working_bytes = cursor,
84 };
85 }
86 };
87
88 pub const PatternIndex = struct {
89 pub const claim: alloc_phase.capacity.Declaration = .{
90 .source = .{
91 .id = "choir.rewrite_pattern_index",
92 .kind = .phase_static,
93 .limit_source = .caller,
94 .storage = .{
95 .covered = &.{
96 .{
97 .id = "load_bounded_rewrite_root_slots_and_exact_sealed_pattern_groups",
98 .lifetime = .steady,
99 .detail = "load-bounded rewrite-root slots and exact sealed pattern groups",
100 },
101 },
102 .excluded = &.{
103 "geometrically grown rewrite-pattern builder storage",
104 "borrowed root names, rewrite callbacks, IR, and pattern-rewriter state",
105 },
106 },
107 .capacity = .{
108 .inputs = &.{
109 alloc_phase.capacity.bindInput(Limits, "patterns", "patterns"),
110 },
111 .type_selectors = &.{
112 alloc_phase.capacity.bindType(PatternRootSlot, "rootslot"),
113 alloc_phase.capacity.bindType(RewritePattern, "rewritepattern"),
114 },
115 .nodes = &.{
116 .{ .collection = .{ .length = 0 } },
117 .{ .constant = 2 },
118 .{ .scale = .{ .node = 1, .coefficient = .{ .size_of_concrete_type = 0 } } },
119 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 1 } } },
120 .{ .add = .{ .left = 2, .right = 3 } },
121 },
122 .assertions = &.{.{
123 .scope = .closure_total,
124 .measure = .retained,
125 .relation = .exact,
126 .expression = 4,
127 }},
128 },
129 .overload = .{
130 .kind = .reject_before_seal,
131 .detail = "pattern-count, unique-root count, placement arithmetic, or OOM failure leaves the pattern set unsealed and retryable",
132 },
133 .risks = .{
134 .transitive = .{
135 .status = .open,
136 .detail = "benefit sorting and root-name hashing use standard-library helpers without a transitive allocation-closure certificate",
137 },
138 .foreign = .{
139 .status = .excluded,
140 .detail = "pattern indexing is process-local and invokes no callback or operating-system boundary",
141 },
142 },
143 .obligations = &.{
144 .{ .key = "pattern_index_capacity", .role = .capacity_model },
145 .{ .key = "pattern_index_sealed_reuse_overload", .role = .overload },
146 .{ .key = "pattern_index_sealed_reuse_transitive_risk", .role = .transitive_risk },
147 .{ .key = "pattern_index_sealed_reuse_foreign_risk", .role = .foreign_risk },
148 .{ .key = "pattern_index_oom_retry", .role = .overload },
149 },
150 },
151 .bindings = .{
152 .owner = @This(),
153 .seal = .{
154 .family = alloc_phase.capacity.selector(@This().activate),
155 .premise = .{
156 .class = .checked_semantic_fact,
157 .authority = .checker,
158 },
159 },
160 .teardown = .{
161 .family = alloc_phase.capacity.selector(@This().deinit),
162 .premise = .{
163 .class = .checked_semantic_fact,
164 .authority = .checker,
165 },
166 },
167 },
168 };
169
170 phase: alloc_phase.capacity.Phase,
171 capacity: PatternIndexCapacity,
172 source_patterns: ?[]const RewritePattern,
173 bytes: []align(pattern_index_alignment) u8,
174 slots: []PatternRootSlot,
175 grouped_patterns: []RewritePattern,
176 root_count: usize,
177
178 pub const Limits = PatternIndexLimits;
179 pub const Capacity = PatternIndexCapacity;
180
181 pub fn init(allocator: std.mem.Allocator, limits: PatternIndexLimits) !PatternIndex {
182 const capacity = try PatternIndexCapacity.derive(limits);
183 const bytes = try allocator.alignedAlloc(
184 u8,
185 .fromByteUnits(pattern_index_alignment),
186 capacity.working_bytes,
187 );
188 errdefer allocator.free(bytes);
189 const slots = patternIndexSlice(
190 PatternRootSlot,
191 bytes,
192 capacity.slots_offset,
193 capacity.slot_count,
194 );
195 @memset(slots, .{});
196 const grouped_patterns = patternIndexSlice(
197 RewritePattern,
198 bytes,
199 capacity.patterns_offset,
200 capacity.facts.pattern_count,
201 );
202
203 var root_count: usize = 0;
204 for (limits.patterns) |pattern| {
205 const insertion = getOrInsertPatternRoot(slots, pattern.spec.root_op_name);
206 root_count += @intFromBool(insertion.inserted);
207 slots[insertion.index].len = std.math.add(
208 PatternOrdinal,
209 slots[insertion.index].len,
210 1,
211 ) catch unreachable;
212 }
213 setPatternRootStarts(slots, grouped_patterns.len);
214 var source_index = limits.patterns.len;
215 while (source_index > 0) {
216 source_index -= 1;
217 const pattern = limits.patterns[source_index];
218 const slot_index = findPatternRootSlotIndex(
219 slots,
220 pattern.spec.root_op_name,
221 ).?;
222 std.debug.assert(slots[slot_index].len > 0);
223 slots[slot_index].len -= 1;
224 const grouped_index = @as(usize, slots[slot_index].start) +
225 @as(usize, slots[slot_index].len);
226 std.debug.assert(grouped_index < grouped_patterns.len);
227 grouped_patterns[grouped_index] = pattern;
228 }
229 restorePatternRootLengths(slots, grouped_patterns.len);
230
231 const index = PatternIndex{
232 .phase = .initialization,
233 .capacity = capacity,
234 .source_patterns = limits.patterns,
235 .bytes = bytes,
236 .slots = slots,
237 .grouped_patterns = grouped_patterns,
238 .root_count = root_count,
239 };
240 index.assertInvariant();
241 return index;
242 }
243
244 pub fn activate(self: *PatternIndex) error{ AlreadyActive, InputChanged }!void {
245 if (self.phase != .initialization) return error.AlreadyActive;
246 if (self.source_patterns == null) return error.InputChanged;
247 self.source_patterns = null;
248 self.phase = .steady;
249 self.assertInvariant();
250 }
251
252 pub fn deinit(self: *PatternIndex, allocator: std.mem.Allocator) void {
253 if (self.phase == .teardown) @panic("rewrite pattern index teardown is terminal");
254 self.assertInvariant();
255 self.phase = .teardown;
256 allocator.free(self.bytes);
257 self.source_patterns = undefined;
258 self.bytes = undefined;
259 self.slots = undefined;
260 self.grouped_patterns = undefined;
261 self.root_count = undefined;
262 }
263
264 pub fn matching(self: *const PatternIndex, root_name: []const u8) []const RewritePattern {
265 self.requireSteady();
266 std.debug.assert(self.grouped_patterns.len == self.capacity.facts.pattern_count);
267 std.debug.assert(self.slots.len == self.capacity.slot_count);
268 const range = self.findRoot(root_name) orelse return &.{};
269 const start: usize = @intCast(range.start);
270 const len: usize = @intCast(range.len);
271 std.debug.assert(start <= self.grouped_patterns.len);
272 std.debug.assert(len <= self.grouped_patterns.len - start);
273 return self.grouped_patterns[start..][0..len];
274 }
275
276 fn findRoot(self: *const PatternIndex, root_name: []const u8) ?PatternRootSlot {
277 const slot_index = findPatternRootSlotIndex(self.slots, root_name) orelse
278 return null;
279 return self.slots[slot_index];
280 }
281
282 fn requireSteady(self: *const PatternIndex) void {
283 if (self.phase != .steady) @panic("rewrite pattern index is not active");
284 }
285
286 fn assertInvariant(self: *const PatternIndex) void {
287 std.debug.assert(self.phase != .teardown);
288 std.debug.assert(self.bytes.len == self.capacity.working_bytes);
289 if (self.phase == .initialization) {
290 std.debug.assert(self.source_patterns != null);
291 std.debug.assert(self.source_patterns.?.len == self.capacity.facts.pattern_count);
292 } else {
293 std.debug.assert(self.source_patterns == null);
294 }
295 std.debug.assert(self.slots.len == self.capacity.slot_count);
296 std.debug.assert(self.grouped_patterns.len == self.capacity.facts.pattern_count);
297 var root_count: usize = 0;
298 var pattern_count: usize = 0;
299 for (self.slots) |slot| {
300 const name = slot.name orelse continue;
301 root_count += 1;
302 std.debug.assert(slot.len > 0);
303 const start: usize = @intCast(slot.start);
304 const len: usize = @intCast(slot.len);
305 std.debug.assert(start <= self.grouped_patterns.len);
306 std.debug.assert(len <= self.grouped_patterns.len - start);
307 pattern_count = std.math.add(usize, pattern_count, len) catch unreachable;
308 std.debug.assert(pattern_count <= self.grouped_patterns.len);
309 const found = self.findRoot(name).?;
310 std.debug.assert(found.start == slot.start);
311 std.debug.assert(found.len == slot.len);
312 }
313 std.debug.assert(root_count == self.root_count);
314 std.debug.assert(pattern_count == self.grouped_patterns.len);
315 for (self.grouped_patterns, 0..) |_, pattern_index| {
316 var containing_ranges: usize = 0;
317 for (self.slots) |slot| {
318 if (slot.name == null) continue;
319 const start: usize = @intCast(slot.start);
320 const len: usize = @intCast(slot.len);
321 if (pattern_index >= start and pattern_index - start < len) {
322 containing_ranges += 1;
323 }
324 }
325 std.debug.assert(containing_ranges == 1);
326 }
327 }
328
329 fn matchesPatterns(self: *const PatternIndex) bool {
330 if (self.grouped_patterns.len != self.capacity.facts.pattern_count) return false;
331 for (self.slots) |slot| {
332 const root_name = slot.name orelse continue;
333 const start: usize = @intCast(slot.start);
334 const len: usize = @intCast(slot.len);
335 for (self.grouped_patterns[start..][0..len], 0..) |pattern, group_index| {
336 if (!std.mem.eql(
337 u8,
338 root_name,
339 pattern.spec.root_op_name,
340 )) return false;
341 if (group_index > 0 and RewritePattern.lessThan(
342 {},
343 pattern,
344 self.grouped_patterns[start + group_index - 1],
345 )) return false;
346 }
347 }
348 return true;
349 }
350 };
351
352 comptime {
353 alloc_phase.capacity.requireAllocatorExactOwnerShape(PatternIndex);
354 }
355
356 fn patternRootSlotCount(pattern_count: usize) error{CapacityOverflow}!usize {
357 return std.math.mul(usize, pattern_count, 2) catch
358 return error.CapacityOverflow;
359 }
360
361 fn patternRootSlotIndex(root_name: []const u8, slot_count: usize) usize {
362 std.debug.assert(slot_count > 0);
363 const hash = std.hash_map.hashString(root_name);
364 const reduced = @as(u128, hash) * @as(u128, slot_count);
365 const index: usize = @intCast(reduced >> 64);
366 std.debug.assert(index < slot_count);
367 return index;
368 }
369
370 const PatternRootInsertion = struct {
371 index: usize,
372 inserted: bool,
373 };
374
375 fn getOrInsertPatternRoot(slots: []PatternRootSlot, root_name: []const u8) PatternRootInsertion {
376 std.debug.assert(slots.len > 0);
377 var index = patternRootSlotIndex(root_name, slots.len);
378 var remaining = slots.len;
379 while (remaining > 0) : (remaining -= 1) {
380 std.debug.assert(index < slots.len);
381 if (slots[index].name == null) {
382 slots[index].name = root_name;
383 return .{ .index = index, .inserted = true };
384 }
385 if (std.mem.eql(u8, slots[index].name.?, root_name)) {
386 return .{ .index = index, .inserted = false };
387 }
388 index += 1;
389 if (index == slots.len) index = 0;
390 }
391 unreachable;
392 }
393
394 fn findPatternRootSlotIndex(slots: []const PatternRootSlot, root_name: []const u8) ?usize {
395 if (slots.len == 0) return null;
396 var index = patternRootSlotIndex(root_name, slots.len);
397 var remaining = slots.len;
398 while (remaining > 0) : (remaining -= 1) {
399 std.debug.assert(index < slots.len);
400 const candidate = slots[index].name orelse return null;
401 if (std.mem.eql(u8, candidate, root_name)) return index;
402 index += 1;
403 if (index == slots.len) index = 0;
404 }
405 return null;
406 }
407
408 fn setPatternRootStarts(slots: []PatternRootSlot, pattern_count: usize) void {
409 var pattern_cursor: usize = 0;
410 for (slots) |*slot| {
411 if (slot.name == null) continue;
412 slot.start = @intCast(pattern_cursor);
413 pattern_cursor = std.math.add(
414 usize,
415 pattern_cursor,
416 @as(usize, slot.len),
417 ) catch unreachable;
418 std.debug.assert(pattern_cursor <= pattern_count);
419 }
420 std.debug.assert(pattern_cursor == pattern_count);
421 }
422
423 fn restorePatternRootLengths(slots: []PatternRootSlot, pattern_count: usize) void {
424 var previous_index: ?usize = null;
425 for (slots, 0..) |slot, slot_index| {
426 if (slot.name == null) continue;
427 std.debug.assert(slot.len == 0);
428 if (previous_index) |index| {
429 std.debug.assert(slots[index].start < slot.start);
430 slots[index].len = slot.start - slots[index].start;
431 }
432 previous_index = slot_index;
433 }
434 if (previous_index) |index| {
435 std.debug.assert(@as(usize, slots[index].start) < pattern_count);
436 slots[index].len = @intCast(pattern_count - @as(usize, slots[index].start));
437 } else {
438 std.debug.assert(pattern_count == 0);
439 }
440 }
441
442 fn placePatternIndexBytes(byte_count: usize, alignment: usize, cursor: *usize) error{CapacityOverflow}!usize {
443 std.debug.assert(std.math.isPowerOfTwo(alignment));
444 const mask = alignment - 1;
445 const padded = std.math.add(usize, cursor.*, mask) catch return error.CapacityOverflow;
446 const offset = padded & ~mask;
447 cursor.* = std.math.add(usize, offset, byte_count) catch return error.CapacityOverflow;
448 return offset;
449 }
450
451 fn patternIndexSlice(
452 comptime T: type,
453 bytes: []align(pattern_index_alignment) u8,
454 offset: usize,
455 count: usize,
456 ) []T {
457 if (count == 0) return &.{};
458 const byte_count = std.math.mul(usize, count, @sizeOf(T)) catch unreachable;
459 std.debug.assert(offset <= bytes.len);
460 std.debug.assert(byte_count <= bytes.len - offset);
461 const region: []align(@alignOf(T)) u8 = @alignCast(bytes[offset..][0..byte_count]);
462 return std.mem.bytesAsSlice(T, region);
463 }
464
465 fn checkRewritePatternIndexInitFailures(allocator: std.mem.Allocator) !void {
466 var patterns = RewritePatternSet.init(allocator);
467 defer patterns.deinit();
468
469 try patterns.add(RewritePattern.init(
470 testRewriteSpec("test.pattern_b", 1),
471 rewriteNoopForPatternOrder,
472 ));
473 try patterns.add(RewritePattern.init(
474 testRewriteSpec("test.pattern_a", 2),
475 rewriteNoopForPatternOrder,
476 ));
477 try patterns.add(RewritePattern.init(
478 testRewriteSpec("test.pattern_a", 1),
479 rewriteNoopForPatternOrder,
480 ));
481 try patterns.seal();
482 try std.testing.expectEqual(
483 alloc_phase.capacity.Phase.steady,
484 patterns.index.?.phase,
485 );
486 }
487
488 test "rewrite pattern index derives exact slot and pattern capacity" {
489 comptime {
490 @stardustClaim(
491 @import("alloc_phase").capacity.witness(PatternIndex, "pattern_index_capacity"),
492 null,
493 null,
494 null,
495 null,
496 null,
497 null,
498 );
499 }
500
501 const testing = std.testing;
502 const declarations = [_]RewritePattern{
503 RewritePattern.init(
504 testRewriteSpec("test.pattern_b", 1),
505 rewriteNoopForPatternOrder,
506 ),
507 RewritePattern.init(
508 testRewriteSpec("test.pattern_a", 2),
509 rewriteNoopForPatternOrder,
510 ),
511 RewritePattern.init(
512 testRewriteSpec("test.pattern_a", 1),
513 rewriteNoopForPatternOrder,
514 ),
515 };
516
517 const limits = try PatternIndexLimits.inspect(&declarations);
518 try testing.expectEqual(@as(usize, 3), limits.facts.pattern_count);
519
520 const capacity = try PatternIndexCapacity.derive(limits);
521 try testing.expectEqual(@as(usize, 0), try patternRootSlotCount(0));
522 try testing.expectEqual(@as(usize, 2), try patternRootSlotCount(1));
523 try testing.expectEqual(@as(usize, 4), try patternRootSlotCount(2));
524 try testing.expectEqual(@as(usize, 6), try patternRootSlotCount(3));
525 const slots_offset: usize = 0;
526 const slots_bytes = 6 * @sizeOf(PatternRootSlot);
527 const patterns_offset = std.mem.alignForward(
528 usize,
529 slots_offset + slots_bytes,
530 @alignOf(RewritePattern),
531 );
532 const patterns_bytes = 3 * @sizeOf(RewritePattern);
533 try testing.expectEqual(@as(usize, 6), capacity.slot_count);
534 try testing.expectEqual(slots_offset, capacity.slots_offset);
535 try testing.expectEqual(slots_bytes, capacity.slots_bytes);
536 try testing.expectEqual(patterns_offset, capacity.patterns_offset);
537 try testing.expectEqual(patterns_bytes, capacity.patterns_bytes);
538 try testing.expectEqual(
539 patterns_offset + patterns_bytes,
540 capacity.working_bytes,
541 );
542
543 const empty_limits = try PatternIndexLimits.inspect(&.{});
544 const empty_capacity = try PatternIndexCapacity.derive(empty_limits);
545 try testing.expectEqual(@as(usize, 0), empty_capacity.slot_count);
546 try testing.expectEqual(@as(usize, 0), empty_capacity.working_bytes);
547 var empty_index = try PatternIndex.init(testing.allocator, empty_limits);
548 defer empty_index.deinit(testing.allocator);
549 try empty_index.activate();
550 try testing.expectEqual(@as(usize, 0), empty_index.matching("test.none").len);
551
552 try testing.expectError(
553 error.CapacityOverflow,
554 patternRootSlotCount(std.math.maxInt(usize)),
555 );
556 const maximum_pattern_count: usize = std.math.maxInt(PatternOrdinal);
557 const maximum = try PatternIndexCapacity.derive(.{
558 .patterns = &.{},
559 .facts = .{ .pattern_count = maximum_pattern_count },
560 });
561 try testing.expectEqual(maximum_pattern_count * 2, maximum.slot_count);
562 try testing.expectError(
563 error.CapacityOverflow,
564 PatternIndexCapacity.derive(.{
565 .patterns = &.{},
566 .facts = .{ .pattern_count = maximum_pattern_count + 1 },
567 }),
568 );
569 }
570
571 test "rewrite pattern index reuses exact backing after sealing" {
572 comptime {
573 @stardustClaim(
574 @import("alloc_phase").capacity.witness(PatternIndex, "pattern_index_sealed_reuse_overload"),
575 null,
576 null,
577 null,
578 null,
579 null,
580 null,
581 );
582 }
583 comptime {
584 @stardustClaim(
585 @import("alloc_phase").capacity.witness(PatternIndex, "pattern_index_sealed_reuse_transitive_risk"),
586 null,
587 null,
588 null,
589 null,
590 null,
591 null,
592 );
593 }
594 comptime {
595 @stardustClaim(
596 @import("alloc_phase").capacity.witness(PatternIndex, "pattern_index_sealed_reuse_foreign_risk"),
597 null,
598 null,
599 null,
600 null,
601 null,
602 null,
603 );
604 }
605
606 const testing = std.testing;
607 const allocator = testing.allocator;
608 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
609 defer ctx.deinit(allocator);
610 try ctx.allowUnregistered();
611
612 const a = try ctx.createOperation(ir.Operation.State.init("test.pattern_a", .unknown));
613 const b = try ctx.createOperation(ir.Operation.State.init("test.pattern_b", .unknown));
614 const absent = try ctx.createOperation(ir.Operation.State.init("test.pattern_absent", .unknown));
615
616 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(allocator);
617 var maybe_patterns: ?RewritePatternSet = RewritePatternSet.init(
618 phase_allocator.initializationAllocator(),
619 );
620 errdefer {
621 if (phase_allocator.phase() == .initialization) {
622 phase_allocator.abortInitialization();
623 }
624 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
625 if (maybe_patterns) |*patterns| patterns.deinit();
626 if (phase_allocator.phase() == .teardown) phase_allocator.deinit();
627 }
628 const patterns = &maybe_patterns.?;
629
630 try patterns.add(RewritePattern.init(
631 testRewriteSpec("test.pattern_b", 1),
632 rewriteNoopForPatternOrder,
633 ));
634 try patterns.add(RewritePattern.init(
635 testRewriteSpec("test.pattern_a", 1),
636 rewriteNoopForPatternOrder,
637 ));
638 try patterns.add(RewritePattern.init(
639 testRewriteSpec("test.pattern_a", 2),
640 rewriteNoopForPatternOrder,
641 ));
642 try patterns.seal();
643 const base_pointer = patterns.index.?.bytes.ptr;
644 try testing.expect(patterns.index.?.matchesPatterns());
645 phase_allocator.seal();
646
647 for (0..64) |_| {
648 const matching_a = patterns.getMatchingPatterns(a);
649 try testing.expectEqual(@as(usize, 2), matching_a.len);
650 try testing.expectEqual(
651 @as(PatternBenefit, 2),
652 matching_a[0].spec.benefit,
653 );
654 try testing.expectEqual(
655 @as(PatternBenefit, 1),
656 matching_a[1].spec.benefit,
657 );
658
659 const matching_b = patterns.getMatchingPatterns(b);
660 try testing.expectEqual(@as(usize, 1), matching_b.len);
661 try testing.expectEqualStrings(
662 "test.pattern_b",
663 matching_b[0].spec.root_op_name,
664 );
665 try testing.expectEqual(
666 @as(usize, 0),
667 patterns.getMatchingPatterns(absent).len,
668 );
669 try testing.expectEqual(base_pointer, patterns.index.?.bytes.ptr);
670 }
671 try testing.expectError(
672 error.PatternSetSealed,
673 patterns.add(RewritePattern.init(
674 testRewriteSpec("test.pattern_c", 3),
675 rewriteNoopForPatternOrder,
676 )),
677 );
678 try testing.expectError(
679 error.PatternSetSealed,
680 patterns.ensureUnusedCapacity(1),
681 );
682 try testing.expectEqual(
683 alloc_phase.PhaseViolations{},
684 phase_allocator.violations(),
685 );
686
687 phase_allocator.beginTeardown();
688 patterns.deinit();
689 maybe_patterns = null;
690 try testing.expectEqual(
691 alloc_phase.PhaseViolations{},
692 phase_allocator.violations(),
693 );
694 phase_allocator.deinit();
695 }
696
697 test "rewrite pattern index initialization is retryable after allocation failure" {
698 comptime {
699 @stardustClaim(
700 @import("alloc_phase").capacity.witness(PatternIndex, "pattern_index_oom_retry"),
701 null,
702 null,
703 null,
704 null,
705 null,
706 null,
707 );
708 }
709
710 try std.testing.checkAllAllocationFailures(
711 std.testing.allocator,
712 checkRewritePatternIndexInitFailures,
713 .{},
714 );
715 try checkRewritePatternIndexInitFailures(std.testing.allocator);
716 }
717
718 fn rewriteNoopForPatternOrder(_: *ir.Operation, _: *PatternRewriter) PatternResult {
719 return .failure;
720 }
721
722 fn testRewriteSpec(root_op_name: []const u8, benefit: PatternBenefit) RewritePatternSpec {
723 return .{
724 .name = root_op_name,
725 .root_op_name = root_op_name,
726 .benefit = benefit,
727 };
728 }