lib/choir/src/product/hashing/stable.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_arena = @import("alloc_arena");
3 const alloc_phase = @import("alloc_phase");
4 const ir = @import("../../core/root.zig");
5 const hashing = @import("root.zig");
6 const capacity_model = hashing.capacity;
7 const numbering = hashing.numbering;
8 const walk = hashing.walk;
9
10 const Allocator = std.mem.Allocator;
11
12 pub const StableHasher = struct {
13 pub const claim: alloc_phase.capacity.Declaration = .{
14 .source = .{
15 .id = "choir.stable_hasher",
16 .kind = .phase_static,
17 .limit_source = .caller,
18 .storage = .{
19 .covered = &.{
20 .{
21 .id = "the_complete_stablevaluenumbering_claim_plus_inline_d8f50bb9374f",
22 .lifetime = .steady,
23 .detail = "the complete StableValueNumbering claim plus inline Wyhash and scalar state",
24 },
25 },
26 .excluded = &.{
27 "borrowed mutable IR and referenced type and attribute payloads",
28 },
29 },
30 .capacity = .{
31 .inputs = &.{
32 alloc_phase.capacity.bindInput(Limits, "facts_value_count", "facts.value_count"),
33 alloc_phase.capacity.bindInput(Limits, "facts_operation_depth", "facts.operation_depth"),
34 alloc_phase.capacity.bindInput(Limits, "facts_attribute_depth", "facts.attribute_depth"),
35 },
36 .type_selectors = &.{
37 alloc_phase.capacity.bindType(capacity_model.ValueEntry, "valueentry"),
38 alloc_phase.capacity.bindType(capacity_model.OperationFrame, "operationframe"),
39 alloc_phase.capacity.bindType(capacity_model.AttributeFrame, "attributeframe"),
40 alloc_phase.capacity.bindType(std.hash.Wyhash, "hasher"),
41 },
42 .nodes = &.{
43 .{ .input = 0 },
44 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
45 .{ .input = 1 },
46 .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 1 } } },
47 .{ .input = 2 },
48 .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 2 } } },
49 .{ .constant = 1 },
50 .{ .scale = .{ .node = 6, .coefficient = .{ .size_of_concrete_type = 3 } } },
51 .{ .add = .{ .left = 1, .right = 3 } },
52 .{ .add = .{ .left = 8, .right = 5 } },
53 .{ .add = .{ .left = 9, .right = 7 } },
54 },
55 .assertions = &.{.{
56 .scope = .closure_total,
57 .measure = .retained,
58 .relation = .exact,
59 .expression = 10,
60 }},
61 },
62 .overload = .{
63 .kind = .reject_before_seal,
64 .detail = "nesting, arithmetic, OOM, stale facts, or definition drift rejects before activation",
65 },
66 .risks = .{
67 .transitive = .{
68 .status = .open,
69 .detail = "fingerprint reaches the indirect OperationPropertiesModel.getInherentAttr hook",
70 },
71 .foreign = .{
72 .status = .open,
73 .detail = "property hook implementations may reacquire allocator policy or cross foreign boundaries",
74 },
75 },
76 .dependencies = &.{"choir.stable_value_numbering"},
77 .obligations = &.{
78 .{ .key = "hasher_capacity", .role = .capacity_model },
79 .{ .key = "hasher_sealed_fingerprint_transitive_risk", .role = .transitive_risk },
80 .{ .key = "hasher_sealed_fingerprint_foreign_risk", .role = .foreign_risk },
81 .{ .key = "hasher_oom_retry", .role = .overload },
82 .{ .key = "hasher_stale_limits", .role = .overload },
83 },
84 },
85 .bindings = .{
86 .owner = @This(),
87 .seal = .{
88 .family = alloc_phase.capacity.selector(@This().activate),
89 .premise = .{
90 .class = .checked_semantic_fact,
91 .authority = .checker,
92 },
93 },
94 .teardown = .{
95 .family = alloc_phase.capacity.selector(@This().deinit),
96 .premise = .{
97 .class = .checked_semantic_fact,
98 .authority = .checker,
99 },
100 },
101 },
102 };
103 phase: alloc_phase.capacity.Phase,
104 capacity: Capacity,
105 numbering: numbering.StableValueNumbering,
106 hasher: std.hash.Wyhash,
107 definitions_seen: u64,
108
109 pub const Limits = capacity_model.Limits;
110 pub const Capacity = capacity_model.Capacity;
111
112 const Self = @This();
113
114 pub fn init(allocator: Allocator, limits: Limits) !Self {
115 const value_numbering = try numbering.StableValueNumbering.init(allocator, limits);
116 return .{
117 .phase = .initialization,
118 .capacity = value_numbering.capacity,
119 .numbering = value_numbering,
120 .hasher = std.hash.Wyhash.init(0),
121 .definitions_seen = 0,
122 };
123 }
124
125 pub fn activate(self: *Self) error{ AlreadyActive, InputChanged }!void {
126 if (self.phase != .initialization) return error.AlreadyActive;
127 try self.numbering.activate();
128 self.phase = .steady;
129 }
130
131 pub fn fingerprint(self: *Self) u64 {
132 self.requireSteady();
133 self.hasher = std.hash.Wyhash.init(0);
134 self.definitions_seen = 0;
135 var iterator = walk.Iterator.init(
136 self.numbering.operation_frames,
137 self.numbering.root,
138 );
139 while (iterator.next()) |event| switch (event) {
140 .operation => |operation| self.visitOperation(operation),
141 .region => {},
142 .block => |block| self.visitBlock(block),
143 };
144 if (self.definitions_seen != self.capacity.facts.value_count) {
145 @panic("stable hashing definitions changed after activation");
146 }
147 return self.hasher.final();
148 }
149
150 pub fn deinit(self: *Self, allocator: Allocator) void {
151 if (self.phase == .teardown) @panic("stable hasher teardown is terminal");
152 self.phase = .teardown;
153 self.numbering.deinit(allocator);
154 self.hasher = undefined;
155 self.definitions_seen = undefined;
156 }
157
158 fn visitOperation(self: *Self, operation: *ir.Operation) void {
159 self.update(operation.getName().name);
160
161 var attrs = operation.getAttrs();
162 while (attrs.next()) |attr| {
163 self.update(attr.name);
164 self.visitAttribute(attr.value);
165 }
166
167 self.updateU64(operation.getNumResults());
168 for (operation.results.items) |*result| {
169 self.visitType(result.type);
170 self.registerValue(result);
171 }
172
173 self.updateU64(operation.getNumOperands());
174 for (operation.operands.items) |operand| self.visitValueUse(operand.value);
175 self.updateU64(operation.getNumRegions());
176 }
177
178 fn visitBlock(self: *Self, block: *ir.Block) void {
179 self.updateU64(block.getNumArguments());
180 for (block.arguments.items) |argument| {
181 self.visitType(argument.type);
182 self.registerValue(argument);
183 }
184 }
185
186 fn registerValue(self: *Self, value: *const ir.Value) void {
187 const id = self.numbering.valueId(value) orelse
188 @panic("stable hashing definition was not indexed");
189 if (id != self.definitions_seen) {
190 @panic("stable hashing definition order changed after activation");
191 }
192 self.definitions_seen += 1;
193 }
194
195 fn visitValueUse(self: *Self, value: *const ir.Value) void {
196 if (self.numbering.valueId(value)) |id| {
197 if (id < self.definitions_seen) {
198 self.updateU64(id);
199 return;
200 }
201 }
202 self.updateU64(std.math.maxInt(u64));
203 }
204
205 fn visitType(self: *Self, typ: ir.Type) void {
206 if (typ.getDialectStorage()) |storage| {
207 self.update(storage.name);
208 if (storage.param_key.len > 0) self.update(storage.param_key);
209 return;
210 }
211 self.updateU64(@intFromPtr(typ.impl));
212 }
213
214 fn visitAttribute(self: *Self, root: ir.Attribute) void {
215 var current: ?ir.Attribute = root;
216 var depth: usize = 0;
217 const frames = self.numbering.attribute_frames;
218 while (true) {
219 if (current) |attr| {
220 self.update(attr.abstract.name);
221
222 if (std.mem.eql(u8, attr.abstract.name, ir.builtin_attr_names.integer)) {
223 if (attr.cast(ir.Attribute.IntegerAttr)) |integer| {
224 self.updateU64(@bitCast(integer.value));
225 self.update(&[_]u8{integer.width});
226 self.update(&[_]u8{if (integer.is_signed) 1 else 0});
227 } else {
228 self.updateU64(@intFromPtr(attr.impl));
229 }
230 } else if (std.mem.eql(u8, attr.abstract.name, ir.builtin_attr_names.float_)) {
231 if (attr.cast(ir.Attribute.FloatAttr)) |float| {
232 self.updateU64(@bitCast(float.value));
233 self.update(&[_]u8{float.width});
234 } else {
235 self.updateU64(@intFromPtr(attr.impl));
236 }
237 } else if (std.mem.eql(u8, attr.abstract.name, ir.builtin_attr_names.bool_)) {
238 if (attr.cast(ir.Attribute.BoolAttr)) |boolean| {
239 self.update(&[_]u8{if (boolean.value) 1 else 0});
240 } else {
241 self.updateU64(@intFromPtr(attr.impl));
242 }
243 } else if (std.mem.eql(u8, attr.abstract.name, ir.builtin_attr_names.string)) {
244 if (attr.cast(ir.Attribute.StringAttr)) |string| {
245 self.update(string.value);
246 } else {
247 self.updateU64(@intFromPtr(attr.impl));
248 }
249 } else if (std.mem.eql(u8, attr.abstract.name, ir.builtin_attr_names.symbol_ref)) {
250 if (attr.cast(ir.Attribute.SymbolRefAttr)) |symbol| {
251 self.updateU64(@intCast(symbol.root_reference.len));
252 self.update(symbol.root_reference);
253 self.updateU64(@intCast(symbol.nested_references.len));
254 for (symbol.nested_references) |nested| {
255 self.updateU64(@intCast(nested.len));
256 self.update(nested);
257 }
258 } else {
259 self.updateU64(@intFromPtr(attr.impl));
260 }
261 } else if (std.mem.eql(u8, attr.abstract.name, ir.builtin_attr_names.string_list)) {
262 if (attr.cast(ir.Attribute.StringListAttr)) |list| {
263 self.updateU64(@intCast(list.values.len));
264 for (list.values) |value| {
265 self.updateU64(@intCast(value.len));
266 self.update(value);
267 }
268 } else {
269 self.updateU64(@intFromPtr(attr.impl));
270 }
271 } else if (std.mem.eql(u8, attr.abstract.name, ir.builtin_attr_names.type_list)) {
272 if (attr.cast(ir.Attribute.TypeListAttr)) |list| {
273 self.updateU64(@intCast(list.values.len));
274 for (list.values) |typ| self.visitType(typ);
275 } else {
276 self.updateU64(@intFromPtr(attr.impl));
277 }
278 } else if (std.mem.eql(u8, attr.abstract.name, ir.builtin_attr_names.array)) {
279 if (attr.cast(ir.Attribute.ArrayAttr)) |array| {
280 self.updateU64(@intCast(array.values.len));
281 if (array.values.len > 0) {
282 if (depth >= frames.len) {
283 @panic("attribute traversal exceeded inspected depth");
284 }
285 frames[depth] = .{ .values = array.values, .next_index = 1 };
286 depth += 1;
287 current = array.values[0];
288 continue;
289 }
290 } else {
291 self.updateU64(@intFromPtr(attr.impl));
292 }
293 } else if (attr.cast(ir.Attribute.DialectAttr)) |dialect| {
294 self.update(dialect.payload);
295 } else {
296 self.updateU64(@intFromPtr(attr.impl));
297 }
298 }
299
300 current = null;
301 while (depth > 0) {
302 const frame = &frames[depth - 1];
303 if (frame.next_index < frame.values.len) {
304 current = frame.values[frame.next_index];
305 frame.next_index += 1;
306 break;
307 }
308 depth -= 1;
309 }
310 if (current == null) return;
311 }
312 }
313
314 fn update(self: *Self, bytes: []const u8) void {
315 self.hasher.update(bytes);
316 }
317
318 fn updateU64(self: *Self, value: u64) void {
319 self.hasher.update(std.mem.asBytes(&value));
320 }
321
322 fn requireSteady(self: *const Self) void {
323 if (self.phase != .steady) @panic("stable hasher used outside its steady phase");
324 }
325 };
326
327 comptime {
328 alloc_phase.capacity.requireAllocatorExactOwnerShape(StableHasher);
329 }
330
331 fn testFingerprint(allocator: Allocator, operation: *ir.Operation) !u64 {
332 const limits = try StableHasher.Limits.inspect(operation);
333 var hasher = try StableHasher.init(allocator, limits);
334 defer hasher.deinit(allocator);
335 try hasher.activate();
336 return hasher.fingerprint();
337 }
338
339 fn checkStableHasherInitFailures(allocator: Allocator, limits: StableHasher.Limits) !void {
340 var hasher = try StableHasher.init(allocator, limits);
341 defer hasher.deinit(allocator);
342 try std.testing.expectEqual(alloc_phase.capacity.Phase.initialization, hasher.phase);
343 }
344
345 fn makeForwardUseTree(
346 context: *ir.Context,
347 use_external: bool,
348 ) !*ir.Operation {
349 const location = ir.Location.getUnknown();
350 const integer_type = try context.getDialectTypeFromName("arith.i64");
351 var producer_state = ir.Operation.State.init("test.producer", location);
352 producer_state.addTypes(&.{integer_type});
353 const producer = try context.createOperation(producer_state);
354 var external_state = ir.Operation.State.init("test.external", location);
355 external_state.addTypes(&.{integer_type});
356 const external = try context.createOperation(external_state);
357 var consumer_state = ir.Operation.State.init("test.consumer", location);
358 consumer_state.addOperands(&.{if (use_external)
359 &external.results.items[0]
360 else
361 &producer.results.items[0]});
362 const consumer = try context.createOperation(consumer_state);
363
364 var region = ir.context.initRegion(context);
365 defer region.deinit();
366 const block = try region.addBlock();
367 try block.addOperation(consumer);
368 try block.addOperation(producer);
369 var root_state = ir.Operation.State.init("test.root", location);
370 root_state.addRegionBodies(&.{®ion});
371 return context.createOperation(root_state);
372 }
373
374 test "stable hasher preserves the established empty-module protocol" {
375 const test_dialect = @import("../../dialects/fixture/root.zig");
376 const allocator = std.testing.allocator;
377
378 var arena = alloc_arena.Arena.init(allocator);
379 defer arena.deinit();
380 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
381 defer context.deinit(arena.allocator());
382 try context.allowUnregistered();
383
384 const module = try test_dialect.TestDialect.ModuleOp.create(
385 &context,
386 ir.Location.getUnknown(),
387 );
388 const limits = try StableHasher.Limits.inspect(module.op);
389 var hasher = try StableHasher.init(allocator, limits);
390 defer hasher.deinit(allocator);
391 try hasher.activate();
392
393 try std.testing.expectEqual(@as(u32, 0), hasher.capacity.facts.value_count);
394 try std.testing.expectEqual(@as(u64, 13_570_492_803_627_155_438), hasher.fingerprint());
395 try std.testing.expectEqual(@as(u64, 13_570_492_803_627_155_438), hasher.fingerprint());
396 }
397
398 test "stable hasher seals exact backing before its first fingerprint" {
399 comptime {
400 @stardustClaim(
401 @import("alloc_phase").capacity.witness(StableHasher, "hasher_sealed_fingerprint_transitive_risk"),
402 null,
403 null,
404 null,
405 null,
406 null,
407 null,
408 );
409 }
410 comptime {
411 @stardustClaim(
412 @import("alloc_phase").capacity.witness(StableHasher, "hasher_sealed_fingerprint_foreign_risk"),
413 null,
414 null,
415 null,
416 null,
417 null,
418 null,
419 );
420 }
421
422 const test_dialect = @import("../../dialects/fixture/root.zig");
423 const allocator = std.testing.allocator;
424
425 var arena = alloc_arena.Arena.init(allocator);
426 defer arena.deinit();
427 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
428 defer context.deinit(arena.allocator());
429 try context.allowUnregistered();
430
431 const location = ir.Location.getUnknown();
432 const integer_type = try test_dialect.TestDialect.getI64Type(&context);
433 var region = ir.context.initRegion(&context);
434 defer region.deinit();
435 const block = try region.addBlock();
436 const first = try block.addArgument(integer_type, location);
437 const second = try block.addArgument(integer_type, location);
438 var state = ir.Operation.State.init("test.add", location);
439 state.addOperands(&.{ first, second });
440 const operation = try context.createOperation(state);
441 try block.addOperation(operation);
442 var wrapper_state = ir.Operation.State.init("wrapper", location);
443 wrapper_state.addRegionBodies(&.{®ion});
444 const wrapper = try context.createOperation(wrapper_state);
445 const leaf = try context.getStringAttr("sealed");
446 const inner = try context.getArrayAttr(&.{leaf});
447 try wrapper.setAttr("nested", try context.getArrayAttr(&.{inner}));
448
449 const limits = try StableHasher.Limits.inspect(wrapper);
450 try std.testing.expect(limits.facts.value_count > 0);
451 try std.testing.expect(limits.facts.operation_depth > 1);
452 try std.testing.expect(limits.facts.attribute_depth > 1);
453 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(allocator);
454 var maybe_hasher: ?StableHasher = null;
455 errdefer {
456 if (phase_allocator.phase() == .initialization) phase_allocator.abortInitialization();
457 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
458 if (maybe_hasher) |*hasher| {
459 if (hasher.phase != .teardown) {
460 hasher.deinit(phase_allocator.teardownAllocator());
461 }
462 }
463 if (phase_allocator.phase() == .teardown) phase_allocator.deinit();
464 }
465
466 maybe_hasher = try StableHasher.init(
467 phase_allocator.initializationAllocator(),
468 limits,
469 );
470 const hasher = &maybe_hasher.?;
471 const entries_pointer = hasher.numbering.index.entries.ptr;
472 const operations_pointer = hasher.numbering.operation_frames.ptr;
473 const attributes_pointer = hasher.numbering.attribute_frames.ptr;
474 const derived = hasher.capacity;
475
476 phase_allocator.seal();
477 try hasher.activate();
478 const first_fingerprint = hasher.fingerprint();
479 const second_fingerprint = hasher.fingerprint();
480
481 try std.testing.expectEqual(first_fingerprint, second_fingerprint);
482 try std.testing.expectEqual(derived, hasher.capacity);
483 try std.testing.expectEqual(entries_pointer, hasher.numbering.index.entries.ptr);
484 try std.testing.expectEqual(operations_pointer, hasher.numbering.operation_frames.ptr);
485 try std.testing.expectEqual(attributes_pointer, hasher.numbering.attribute_frames.ptr);
486 try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
487
488 phase_allocator.beginTeardown();
489 hasher.deinit(phase_allocator.teardownAllocator());
490 try std.testing.expectEqual(alloc_phase.capacity.Phase.teardown, hasher.phase);
491 try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
492 phase_allocator.deinit();
493 }
494
495 test "stable hasher preserves established nested-operation protocol" {
496 const test_dialect = @import("../../dialects/fixture/root.zig");
497 const allocator = std.testing.allocator;
498 var arena = alloc_arena.Arena.init(allocator);
499 defer arena.deinit();
500 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
501 defer context.deinit(arena.allocator());
502 try context.allowUnregistered();
503 const location = ir.Location.getUnknown();
504
505 _ = try test_dialect.TestDialect.ModuleOp.create(&context, location);
506 const module = try test_dialect.TestDialect.ModuleOp.create(&context, location);
507 const function = try test_dialect.TestDialect.FuncOp.create(
508 &context,
509 location,
510 "foo",
511 &.{},
512 );
513 try module.getBodyBlock().addOperation(function.op);
514 try std.testing.expectEqual(
515 @as(u64, 13_201_224_996_460_106_173),
516 try testFingerprint(allocator, module.op),
517 );
518 }
519
520 test "stable hasher preserves established operand protocol" {
521 const test_dialect = @import("../../dialects/fixture/root.zig");
522 const allocator = std.testing.allocator;
523 var arena = alloc_arena.Arena.init(allocator);
524 defer arena.deinit();
525 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
526 defer context.deinit(arena.allocator());
527 try context.allowUnregistered();
528 const location = ir.Location.getUnknown();
529 const integer_type = try test_dialect.TestDialect.getI64Type(&context);
530
531 var first_region = ir.context.initRegion(&context);
532 defer first_region.deinit();
533 const first_block = try first_region.addBlock();
534 const first_argument = try first_block.addArgument(integer_type, location);
535 const second_argument = try first_block.addArgument(integer_type, location);
536 var first_state = ir.Operation.State.init("test.add", location);
537 first_state.addOperands(&.{ first_argument, second_argument });
538 const first_operation = try context.createOperation(first_state);
539 try first_block.addOperation(first_operation);
540 var first_wrapper_state = ir.Operation.State.init("wrapper", location);
541 first_wrapper_state.addRegionBodies(&.{&first_region});
542 const first_wrapper = try context.createOperation(first_wrapper_state);
543
544 var second_region = ir.context.initRegion(&context);
545 defer second_region.deinit();
546 const second_block = try second_region.addBlock();
547 const third_argument = try second_block.addArgument(integer_type, location);
548 const fourth_argument = try second_block.addArgument(integer_type, location);
549 var second_state = ir.Operation.State.init("test.add", location);
550 second_state.addOperands(&.{ fourth_argument, third_argument });
551 const second_operation = try context.createOperation(second_state);
552 try second_block.addOperation(second_operation);
553 var second_wrapper_state = ir.Operation.State.init("wrapper", location);
554 second_wrapper_state.addRegionBodies(&.{&second_region});
555 const second_wrapper = try context.createOperation(second_wrapper_state);
556
557 try std.testing.expectEqual(
558 @as(u64, 6_847_343_841_190_853_235),
559 try testFingerprint(allocator, first_wrapper),
560 );
561 try std.testing.expectEqual(
562 @as(u64, 17_940_735_187_720_636_147),
563 try testFingerprint(allocator, second_wrapper),
564 );
565 }
566
567 test "stable hasher initialization cleans every allocation failure and retries" {
568 comptime {
569 @stardustClaim(
570 @import("alloc_phase").capacity.witness(StableHasher, "hasher_oom_retry"),
571 null,
572 null,
573 null,
574 null,
575 null,
576 null,
577 );
578 }
579
580 const test_dialect = @import("../../dialects/fixture/root.zig");
581 const allocator = std.testing.allocator;
582 var arena = alloc_arena.Arena.init(allocator);
583 defer arena.deinit();
584 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
585 defer context.deinit(arena.allocator());
586 try context.allowUnregistered();
587 const location = ir.Location.getUnknown();
588 const integer_type = try test_dialect.TestDialect.getI64Type(&context);
589 var region = ir.context.initRegion(&context);
590 defer region.deinit();
591 const block = try region.addBlock();
592 _ = try block.addArgument(integer_type, location);
593 const child = try context.createOperation(ir.Operation.State.init("child", location));
594 try block.addOperation(child);
595 var root_state = ir.Operation.State.init("root", location);
596 root_state.addRegionBodies(&.{®ion});
597 const root = try context.createOperation(root_state);
598 const leaf = try context.getStringAttr("leaf");
599 const inner = try context.getArrayAttr(&.{leaf});
600 try root.setAttr("nested", try context.getArrayAttr(&.{inner}));
601 const limits = try StableHasher.Limits.inspect(root);
602 try std.testing.expect(limits.facts.value_count > 0);
603 try std.testing.expect(limits.facts.operation_depth > 1);
604 try std.testing.expect(limits.facts.attribute_depth > 1);
605
606 try std.testing.checkAllAllocationFailures(
607 allocator,
608 checkStableHasherInitFailures,
609 .{limits},
610 );
611
612 var hasher = try StableHasher.init(allocator, limits);
613 defer hasher.deinit(allocator);
614 try hasher.activate();
615 _ = hasher.fingerprint();
616 }
617
618 test "stable hasher rejects definition drift before activation" {
619 const test_dialect = @import("../../dialects/fixture/root.zig");
620 const allocator = std.testing.allocator;
621 var arena = alloc_arena.Arena.init(allocator);
622 defer arena.deinit();
623 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
624 defer context.deinit(arena.allocator());
625 try context.allowUnregistered();
626 const location = ir.Location.getUnknown();
627 const module = try test_dialect.TestDialect.ModuleOp.create(&context, location);
628 const limits = try StableHasher.Limits.inspect(module.op);
629 var hasher = try StableHasher.init(allocator, limits);
630 defer hasher.deinit(allocator);
631
632 const child = try context.createOperation(ir.Operation.State.init("new.child", location));
633 try module.getBodyBlock().addOperation(child);
634 try std.testing.expectError(error.InputChanged, hasher.activate());
635 }
636
637 test "stable hasher rejects stale limits before allocation" {
638 comptime {
639 @stardustClaim(
640 @import("alloc_phase").capacity.witness(StableHasher, "hasher_stale_limits"),
641 null,
642 null,
643 null,
644 null,
645 null,
646 null,
647 );
648 }
649
650 const allocator = std.testing.allocator;
651 var arena = alloc_arena.Arena.init(allocator);
652 defer arena.deinit();
653 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
654 defer context.deinit(arena.allocator());
655 try context.allowUnregistered();
656 const location = ir.Location.getUnknown();
657 var root_state = ir.Operation.State.init("root", location);
658 root_state.addRegion();
659 const root = try context.createOperation(root_state);
660 const limits = try StableHasher.Limits.inspect(root);
661 const block = try root.getRegion(0).?.addBlock();
662 try block.addOperation(try context.createOperation(ir.Operation.State.init("child", location)));
663 var failing = std.testing.FailingAllocator.init(allocator, .{ .fail_index = 0 });
664 try std.testing.expectError(
665 error.InputChanged,
666 StableHasher.init(failing.allocator(), limits),
667 );
668 }
669
670 test "stable hasher fingerprints structural attributes by contents" {
671 const allocator = std.testing.allocator;
672 var arena = alloc_arena.Arena.init(allocator);
673 defer arena.deinit();
674 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
675 defer context.deinit(arena.allocator());
676 try context.allowUnregistered();
677 const location = ir.Location.getUnknown();
678 const i32_type = try context.getDialectTypeFromName("arith.i32");
679 const i64_type = try context.getDialectTypeFromName("arith.i64");
680
681 const first = try context.createOperation(ir.Operation.State.init("test.attrs", location));
682 try first.setAttr("names", try context.getStringListAttr(&.{ "ctx", "result" }));
683 try first.setAttr("types", try context.getTypeListAttr(&.{ i32_type, i64_type }));
684 try first.setAttr("array", try context.getArrayAttr(&.{
685 try context.getStringAttr("ctx"),
686 try context.getTypeListAttr(&.{ i32_type, i64_type }),
687 }));
688
689 const second = try context.createOperation(ir.Operation.State.init("test.attrs", location));
690 try second.setAttr("array", try context.getArrayAttr(&.{
691 try context.getStringAttr("ctx"),
692 try context.getTypeListAttr(&.{ i32_type, i64_type }),
693 }));
694 try second.setAttr("types", try context.getTypeListAttr(&.{ i32_type, i64_type }));
695 try second.setAttr("names", try context.getStringListAttr(&.{ "ctx", "result" }));
696
697 const different = try context.createOperation(ir.Operation.State.init("test.attrs", location));
698 try different.setAttr("names", try context.getStringListAttr(&.{ "ctx", "value" }));
699 try different.setAttr("types", try context.getTypeListAttr(&.{i32_type}));
700 try different.setAttr("array", try context.getArrayAttr(&.{
701 try context.getStringAttr("ctx"),
702 try context.getTypeListAttr(&.{i32_type}),
703 }));
704
705 const first_fingerprint = try testFingerprint(allocator, first);
706 try std.testing.expectEqual(first_fingerprint, try testFingerprint(allocator, second));
707 try std.testing.expect(first_fingerprint != try testFingerprint(allocator, different));
708 }
709
710 test "stable hasher consumes the maximum inspected attribute depth" {
711 const allocator = std.testing.allocator;
712 var arena = alloc_arena.Arena.init(allocator);
713 defer arena.deinit();
714 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
715 defer context.deinit(arena.allocator());
716 try context.allowUnregistered();
717 const operation = try context.createOperation(ir.Operation.State.init(
718 "test.deep_attrs",
719 ir.Location.getUnknown(),
720 ));
721 var attribute = try context.getStringAttr("leaf");
722 for (0..capacity_model.maximum_attribute_depth) |_| {
723 attribute = try context.getArrayAttr(&.{attribute});
724 }
725 try operation.setAttr("nested", attribute);
726 const limits = try StableHasher.Limits.inspect(operation);
727 try std.testing.expectEqual(
728 capacity_model.maximum_attribute_depth,
729 limits.facts.attribute_depth,
730 );
731 var hasher = try StableHasher.init(allocator, limits);
732 defer hasher.deinit(allocator);
733 try hasher.activate();
734 _ = hasher.fingerprint();
735 }
736
737 test "stable hasher preserves forward and external use sentinels" {
738 const allocator = std.testing.allocator;
739 var arena = alloc_arena.Arena.init(allocator);
740 defer arena.deinit();
741 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
742 defer context.deinit(arena.allocator());
743 try context.allowUnregistered();
744 const forward = try makeForwardUseTree(&context, false);
745 const external = try makeForwardUseTree(&context, true);
746 try std.testing.expectEqual(
747 try testFingerprint(allocator, forward),
748 try testFingerprint(allocator, external),
749 );
750 }