lib/choir/src/core/interfaces/traits.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const registry_entry = @import("entry.zig");
3
4 pub const TraitId = u64;
5
6 pub fn traitId(comptime name: []const u8) TraitId {
7 return std.hash.Wyhash.hash(0, name);
8 }
9
10 pub fn traitIdRuntime(name: []const u8) TraitId {
11 return std.hash.Wyhash.hash(0, name);
12 }
13
14 pub const TraitVTable = struct {
15 verify: ?*const fn (op_ptr: *const anyopaque) anyerror!void = null,
16 verify_regions: ?*const fn (op_ptr: *const anyopaque) anyerror!void = null,
17 };
18
19 pub const TraitEntry = struct {
20 id: TraitId,
21 vtable: *const TraitVTable,
22 };
23
24 pub const TraitIds = struct {
25 pub const inline_capacity: usize = 4;
26
27 const Storage = registry_entry.InlineList(TraitId, inline_capacity);
28
29 storage: Storage = .{},
30
31 pub const InsertError = error{DuplicateTrait} || std.mem.Allocator.Error;
32
33 pub fn initInline(storage: *[inline_capacity]TraitId) TraitIds {
34 return .{ .storage = Storage.initInline(storage) };
35 }
36
37 pub fn deinit(self: *TraitIds, allocator: std.mem.Allocator) void {
38 self.storage.deinit(allocator);
39 }
40
41 pub fn insert(
42 self: *TraitIds,
43 allocator: std.mem.Allocator,
44 id: TraitId,
45 ) InsertError!void {
46 if (self.contains(id)) return error.DuplicateTrait;
47 try self.storage.append(allocator, id);
48 std.mem.sort(TraitId, self.storage.valuesMut(), {}, lessThan);
49 }
50
51 pub fn values(self: *const TraitIds) []const TraitId {
52 return self.storage.values();
53 }
54
55 pub fn contains(self: *const TraitIds, id: TraitId) bool {
56 const sorted = self.values();
57 var left: usize = 0;
58 var right = sorted.len;
59 while (left < right) {
60 const mid = left + (right - left) / 2;
61 if (sorted[mid] == id) return true;
62 if (sorted[mid] < id) {
63 left = mid + 1;
64 } else {
65 right = mid;
66 }
67 }
68 return false;
69 }
70
71 fn lessThan(_: void, a: TraitId, b: TraitId) bool {
72 return a < b;
73 }
74 };
75
76 pub const TraitRegistry = struct {
77 traits: std.AutoHashMapUnmanaged(TraitId, *const TraitVTable),
78
79 pub const RegisterError = error{DuplicateTrait} || std.mem.Allocator.Error;
80
81 pub fn init() TraitRegistry {
82 return .{ .traits = .{} };
83 }
84
85 pub fn deinit(self: *TraitRegistry, allocator: std.mem.Allocator) void {
86 self.traits.deinit(allocator);
87 }
88
89 pub fn register(
90 self: *TraitRegistry,
91 allocator: std.mem.Allocator,
92 entry: TraitEntry,
93 ) RegisterError!void {
94 const gop = try self.traits.getOrPut(allocator, entry.id);
95 if (gop.found_existing) return error.DuplicateTrait;
96 gop.value_ptr.* = entry.vtable;
97 }
98
99 pub fn lookup(self: *const TraitRegistry, id: TraitId) ?*const TraitVTable {
100 return self.traits.get(id);
101 }
102
103 pub fn count(self: *const TraitRegistry) usize {
104 return self.traits.count();
105 }
106 };
107
108 pub const OperationTraits = packed struct(u64) {
109 is_terminator: bool = false,
110 is_commutative: bool = false,
111 is_idempotent: bool = false,
112 is_involution: bool = false,
113 is_symbol_table: bool = false,
114 has_no_terminator: bool = false,
115 has_only_graph_regions: bool = false,
116 _padding: u57 = 0,
117
118 pub fn merge(a: OperationTraits, b: OperationTraits) OperationTraits {
119 return .{
120 .is_terminator = a.is_terminator or b.is_terminator,
121 .is_commutative = a.is_commutative or b.is_commutative,
122 .is_idempotent = a.is_idempotent or b.is_idempotent,
123 .is_involution = a.is_involution or b.is_involution,
124 .is_symbol_table = a.is_symbol_table or b.is_symbol_table,
125 .has_no_terminator = a.has_no_terminator or b.has_no_terminator,
126 .has_only_graph_regions = a.has_only_graph_regions or b.has_only_graph_regions,
127 };
128 }
129 };
130
131 test "traitId produces stable hashes" {
132 const testing = std.testing;
133
134 const id1 = traitId("ir.trait.idempotent");
135 const id2 = traitId("ir.trait.idempotent");
136 const id3 = traitId("ir.trait.terminator");
137
138 try testing.expectEqual(id1, id2);
139 try testing.expect(id1 != id3);
140
141 const runtime_id = traitIdRuntime("ir.trait.idempotent");
142 try testing.expectEqual(id1, runtime_id);
143 }
144
145 test "OperationTraits merge" {
146 const testing = std.testing;
147
148 const a = OperationTraits{ .is_idempotent = true };
149 const b = OperationTraits{
150 .is_terminator = true,
151 .is_symbol_table = true,
152 .has_no_terminator = true,
153 .has_only_graph_regions = true,
154 };
155 const merged = OperationTraits.merge(a, b);
156
157 try testing.expect(merged.is_idempotent);
158 try testing.expect(merged.is_terminator);
159 try testing.expect(merged.is_symbol_table);
160 try testing.expect(merged.has_no_terminator);
161 try testing.expect(merged.has_only_graph_regions);
162 try testing.expect(!merged.is_commutative);
163 }
164
165 test "OperationTraits packed size" {
166 const testing = std.testing;
167
168 try testing.expectEqual(@as(usize, 8), @sizeOf(OperationTraits));
169 }
170
171 test "TraitIds keeps four sorted IDs inline and spills transactionally" {
172 const testing = std.testing;
173 try testing.expectEqual(@as(usize, 24), @sizeOf(TraitIds));
174
175 var failing = testing.FailingAllocator.init(
176 testing.allocator,
177 .{ .fail_index = 0 },
178 );
179 var inline_storage: [TraitIds.inline_capacity]TraitId = undefined;
180 var ids = TraitIds.initInline(&inline_storage);
181 defer ids.deinit(failing.allocator());
182
183 try ids.insert(failing.allocator(), 40);
184 try ids.insert(failing.allocator(), 10);
185 try ids.insert(failing.allocator(), 30);
186 try ids.insert(failing.allocator(), 20);
187 try testing.expectEqual(@as(usize, 0), failing.alloc_index);
188 try testing.expectEqualSlices(TraitId, &.{ 10, 20, 30, 40 }, ids.values());
189 try testing.expectError(error.DuplicateTrait, ids.insert(failing.allocator(), 20));
190 try testing.expectEqual(@as(usize, 0), failing.alloc_index);
191
192 try testing.expectError(error.OutOfMemory, ids.insert(failing.allocator(), 50));
193 try testing.expectEqualSlices(TraitId, &.{ 10, 20, 30, 40 }, ids.values());
194 try testing.expect(!ids.contains(50));
195
196 failing.fail_index = std.math.maxInt(usize);
197 const before_allocated = failing.allocated_bytes;
198 try ids.insert(failing.allocator(), 50);
199 try testing.expectEqualSlices(TraitId, &.{ 10, 20, 30, 40, 50 }, ids.values());
200 try testing.expectEqual(
201 std.math.add(usize, before_allocated, 5 * @sizeOf(TraitId)) catch unreachable,
202 failing.allocated_bytes,
203 );
204 }
205
206 test "TraitRegistry register and lookup" {
207 const testing = std.testing;
208
209 var registry = TraitRegistry.init();
210 defer registry.deinit(testing.allocator);
211
212 const vtable: TraitVTable = .{ .verify = null };
213 const id = traitId("ir.trait.test");
214 const entry = TraitEntry{ .id = id, .vtable = &vtable };
215
216 try registry.register(testing.allocator, entry);
217 try testing.expectEqual(@as(usize, 1), registry.count());
218 try testing.expectEqual(@as(?*const TraitVTable, &vtable), registry.lookup(id));
219
220 try testing.expectError(
221 error.DuplicateTrait,
222 registry.register(testing.allocator, entry),
223 );
224 }