lib/choir/src/product/hashing/capacity.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_arena = @import("alloc_arena");
3 const ir = @import("../../core/root.zig");
4
5 pub const maximum_operation_depth: usize = 256;
6 pub const maximum_attribute_depth: usize = 256;
7
8 pub const InspectError = error{
9 ValueCountOverflow,
10 CountOverflow,
11 NestingLimitExceeded,
12 };
13
14 pub const Facts = struct {
15 value_count: u32 = 0,
16 operation_count: usize = 0,
17 region_count: usize = 0,
18 block_count: usize = 0,
19 operation_depth: usize = 0,
20 attribute_depth: usize = 0,
21
22 pub fn eql(self: Facts, other: Facts) bool {
23 return std.meta.eql(self, other);
24 }
25 };
26
27 pub const Limits = struct {
28 root: *ir.Operation,
29 facts: Facts,
30
31 pub fn inspect(root: *ir.Operation) InspectError!Limits {
32 var facts = Facts{};
33 try inspectOperation(root, 1, &facts);
34 return .{ .root = root, .facts = facts };
35 }
36 };
37
38 pub const ValueEntry = struct {
39 value: *const ir.Value,
40 id: u64,
41 };
42
43 pub const OperationFrame = struct {
44 operation: *ir.Operation,
45 state: State = .operation,
46 region_index: usize = 0,
47 block: ?*ir.Block = null,
48 child: ?*ir.Operation = null,
49
50 pub const State = enum {
51 operation,
52 region,
53 block,
54 child,
55 };
56 };
57
58 pub const AttributeFrame = struct {
59 values: []const ir.Attribute,
60 next_index: usize,
61 };
62
63 pub const Capacity = struct {
64 facts: Facts,
65 value_bytes: usize,
66 operation_bytes: usize,
67 attribute_bytes: usize,
68 working_bytes: usize,
69
70 pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {
71 const value_bytes = try checkedMul(limits.facts.value_count, @sizeOf(ValueEntry));
72 const operation_bytes = try checkedMul(
73 limits.facts.operation_depth,
74 @sizeOf(OperationFrame),
75 );
76 const attribute_bytes = try checkedMul(
77 limits.facts.attribute_depth,
78 @sizeOf(AttributeFrame),
79 );
80 const partial = try checkedAdd(value_bytes, operation_bytes);
81 const working_bytes = try checkedAdd(partial, attribute_bytes);
82 return .{
83 .facts = limits.facts,
84 .value_bytes = value_bytes,
85 .operation_bytes = operation_bytes,
86 .attribute_bytes = attribute_bytes,
87 .working_bytes = working_bytes,
88 };
89 }
90 };
91
92 fn inspectOperation(
93 operation: *ir.Operation,
94 depth: usize,
95 facts: *Facts,
96 ) InspectError!void {
97 if (depth > maximum_operation_depth) return error.NestingLimitExceeded;
98 facts.operation_depth = @max(facts.operation_depth, depth);
99 facts.operation_count = try addCount(facts.operation_count, 1);
100 facts.value_count = try addValues(facts.value_count, operation.results.items.len);
101
102 var attrs = operation.getAttrs();
103 while (attrs.next()) |attr| try inspectAttribute(attr.value, 0, facts);
104
105 for (operation.regions.items) |*region| {
106 facts.region_count = try addCount(facts.region_count, 1);
107 var block_opaque = region.blocks.head;
108 while (block_opaque) |block_ptr| {
109 const block: *ir.Block = @ptrCast(@alignCast(block_ptr));
110 facts.block_count = try addCount(facts.block_count, 1);
111 facts.value_count = try addValues(facts.value_count, block.arguments.items.len);
112
113 var child_opaque = block.operations.head;
114 while (child_opaque) |child_ptr| {
115 const child: *ir.Operation = @ptrCast(@alignCast(child_ptr));
116 try inspectOperation(child, depth + 1, facts);
117 child_opaque = child.next_op;
118 }
119 block_opaque = block.next;
120 }
121 }
122 }
123
124 fn inspectAttribute(attr: ir.Attribute, depth: usize, facts: *Facts) InspectError!void {
125 const array = attr.cast(ir.Attribute.ArrayAttr) orelse return;
126 if (array.values.len == 0) return;
127 const array_depth = depth + 1;
128 if (array_depth > maximum_attribute_depth) return error.NestingLimitExceeded;
129 facts.attribute_depth = @max(facts.attribute_depth, array_depth);
130 for (array.values) |value| try inspectAttribute(value, array_depth, facts);
131 }
132
133 fn addValues(current: u32, amount: usize) InspectError!u32 {
134 const narrowed = std.math.cast(u32, amount) orelse return error.ValueCountOverflow;
135 return std.math.add(u32, current, narrowed) catch return error.ValueCountOverflow;
136 }
137
138 fn addCount(current: usize, amount: usize) InspectError!usize {
139 return std.math.add(usize, current, amount) catch return error.CountOverflow;
140 }
141
142 fn checkedMul(count: anytype, size: usize) error{CapacityOverflow}!usize {
143 const narrowed = std.math.cast(usize, count) orelse return error.CapacityOverflow;
144 return std.math.mul(usize, narrowed, size) catch return error.CapacityOverflow;
145 }
146
147 fn checkedAdd(lhs: usize, rhs: usize) error{CapacityOverflow}!usize {
148 return std.math.add(usize, lhs, rhs) catch return error.CapacityOverflow;
149 }
150
151 test "capacity derives exact typed working bytes" {
152 comptime {
153 @stardustClaim(
154 @import("alloc_phase").capacity.witness(@import("./root.zig").StableValueNumbering, "numbering_capacity"),
155 null,
156 null,
157 null,
158 null,
159 null,
160 null,
161 );
162 }
163 comptime {
164 @stardustClaim(
165 @import("alloc_phase").capacity.witness(@import("./root.zig").StableHasher, "hasher_capacity"),
166 null,
167 null,
168 null,
169 null,
170 null,
171 null,
172 );
173 }
174
175 const facts = Facts{
176 .value_count = 7,
177 .operation_count = 4,
178 .region_count = 2,
179 .block_count = 3,
180 .operation_depth = 3,
181 .attribute_depth = 2,
182 };
183 const capacity = try Capacity.derive(.{ .root = undefined, .facts = facts });
184 const value_bytes = 7 * @sizeOf(ValueEntry);
185 const operation_bytes = 3 * @sizeOf(OperationFrame);
186 const attribute_bytes = 2 * @sizeOf(AttributeFrame);
187 try std.testing.expectEqual(value_bytes, capacity.value_bytes);
188 try std.testing.expectEqual(operation_bytes, capacity.operation_bytes);
189 try std.testing.expectEqual(attribute_bytes, capacity.attribute_bytes);
190 try std.testing.expectEqual(
191 value_bytes + operation_bytes + attribute_bytes,
192 capacity.working_bytes,
193 );
194 }
195
196 test "capacity rejects checked arithmetic overflow" {
197 const overflowing = Facts{
198 .operation_depth = std.math.maxInt(usize),
199 .attribute_depth = std.math.maxInt(usize),
200 };
201 try std.testing.expectError(
202 error.CapacityOverflow,
203 Capacity.derive(.{ .root = undefined, .facts = overflowing }),
204 );
205 try std.testing.expectError(
206 error.ValueCountOverflow,
207 addValues(std.math.maxInt(u32), 1),
208 );
209 try std.testing.expectError(
210 error.CountOverflow,
211 addCount(std.math.maxInt(usize), 1),
212 );
213 }
214
215 test "inspection enforces operation nesting boundary" {
216 const allocator = std.testing.allocator;
217 var arena = alloc_arena.Arena.init(allocator);
218 defer arena.deinit();
219 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
220 defer context.deinit(arena.allocator());
221 try context.allowUnregistered();
222 const location = ir.Location.getUnknown();
223 var root_state = ir.Operation.State.init("root", location);
224 root_state.addRegion();
225 const root = try context.createOperation(root_state);
226 var current = root;
227 for (1..maximum_operation_depth) |_| {
228 var child_state = ir.Operation.State.init("child", location);
229 child_state.addRegion();
230 const child = try context.createOperation(child_state);
231 const block = try current.getRegion(0).?.addBlock();
232 try block.addOperation(child);
233 current = child;
234 }
235 const limits = try Limits.inspect(root);
236 try std.testing.expectEqual(maximum_operation_depth, limits.facts.operation_depth);
237
238 const one_past = try context.createOperation(ir.Operation.State.init("one.past", location));
239 const block = try current.getRegion(0).?.addBlock();
240 try block.addOperation(one_past);
241 try std.testing.expectError(error.NestingLimitExceeded, Limits.inspect(root));
242 }
243
244 test "inspection enforces array attribute nesting boundary" {
245 const allocator = std.testing.allocator;
246 var arena = alloc_arena.Arena.init(allocator);
247 defer arena.deinit();
248 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
249 defer context.deinit(arena.allocator());
250 try context.allowUnregistered();
251 const operation = try context.createOperation(ir.Operation.State.init(
252 "array.depth",
253 ir.Location.getUnknown(),
254 ));
255 var attribute = try context.getStringAttr("leaf");
256 for (0..maximum_attribute_depth) |_| {
257 attribute = try context.getArrayAttr(&.{attribute});
258 }
259 try operation.setAttr("nested", attribute);
260 const limits = try Limits.inspect(operation);
261 try std.testing.expectEqual(maximum_attribute_depth, limits.facts.attribute_depth);
262
263 try operation.setAttr("nested", try context.getArrayAttr(&.{attribute}));
264 try std.testing.expectError(error.NestingLimitExceeded, Limits.inspect(operation));
265 }