tiny.choir.product.hashing.stable

1pub const stable = @import("stable.zig");

1const std = @import("std");2const alloc_arena = @import("alloc_arena");3const alloc_phase = @import("alloc_phase");4const ir = @import("../../core/root.zig");5const hashing = @import("root.zig");6const capacity_model = hashing.capacity;7const numbering = hashing.numbering;8const walk = hashing.walk;910const Allocator = std.mem.Allocator;1112pub 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,108109    pub const Limits = capacity_model.Limits;110    pub const Capacity = capacity_model.Capacity;111112    const Self = @This();113114    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    }124125    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    }130131    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    }149150    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    }157158    fn visitOperation(self: *Self, operation: *ir.Operation) void {159        self.update(operation.getName().name);160161        var attrs = operation.getAttrs();162        while (attrs.next()) |attr| {163            self.update(attr.name);164            self.visitAttribute(attr.value);165        }166167        self.updateU64(operation.getNumResults());168        for (operation.results.items) |*result| {169            self.visitType(result.type);170            self.registerValue(result);171        }172173        self.updateU64(operation.getNumOperands());174        for (operation.operands.items) |operand| self.visitValueUse(operand.value);175        self.updateU64(operation.getNumRegions());176    }177178    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    }185186    fn registerValue(self: *Self, value: *const ir.Value) void {187        const id = self.numbering.valueId(value) orelse188            @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    }194195    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    }204205    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    }213214    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);221222                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            }299300            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    }313314    fn update(self: *Self, bytes: []const u8) void {315        self.hasher.update(bytes);316    }317318    fn updateU64(self: *Self, value: u64) void {319        self.hasher.update(std.mem.asBytes(&value));320    }321322    fn requireSteady(self: *const Self) void {323        if (self.phase != .steady) @panic("stable hasher used outside its steady phase");324    }325};326327comptime {328    alloc_phase.capacity.requireAllocatorExactOwnerShape(StableHasher);329}330331fn 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}338339fn 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}344345fn 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    else361        &producer.results.items[0]});362    const consumer = try context.createOperation(consumer_state);363364    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(&.{&region});371    return context.createOperation(root_state);372}373374test "stable hasher preserves the established empty-module protocol" {375    const test_dialect = @import("../../dialects/fixture/root.zig");376    const allocator = std.testing.allocator;377378    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();383384    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();392393    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}397398test "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    }421422    const test_dialect = @import("../../dialects/fixture/root.zig");423    const allocator = std.testing.allocator;424425    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();430431    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(&.{&region});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}));448449    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    }465466    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;475476    phase_allocator.seal();477    try hasher.activate();478    const first_fingerprint = hasher.fingerprint();479    const second_fingerprint = hasher.fingerprint();480481    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());487488    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}494495test "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();504505    _ = 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}519520test "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);530531    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);543544    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);556557    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}566567test "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    }579580    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(&.{&region});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);605606    try std.testing.checkAllAllocationFailures(607        allocator,608        checkStableHasherInitFailures,609        .{limits},610    );611612    var hasher = try StableHasher.init(allocator, limits);613    defer hasher.deinit(allocator);614    try hasher.activate();615    _ = hasher.fingerprint();616}617618test "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);631632    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}636637test "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    }649650    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}669670test "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");680681    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    }));688689    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" }));696697    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    }));704705    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}709710test "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}736737test "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}