lib/xkb/src/compose/storage.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const xkb = @import("../root.zig");
4 const capacity_mod = @import("capacity.zig");
5 const table = @import("table.zig");
6
7 const Keysym = xkb.keysym.Keysym;
8
9 pub const StorageExhaustion = error{
10 ComposeStorageInUse,
11 SequenceSymbolCapacityExceeded,
12 TextByteCapacityExceeded,
13 };
14
15 pub const Status = struct {
16 phase: alloc_phase.capacity.Phase,
17 in_use: bool,
18 storage_bytes: usize,
19 sequence_symbols: usize,
20 text_bytes: usize,
21 used_nodes: usize,
22 used_edges: usize,
23 used_text_bytes: usize,
24 };
25
26 pub const Storage = struct {
27 phase: alloc_phase.capacity.Phase,
28 capacity: capacity_mod.Capacity,
29 bytes: []align(capacity_mod.storage_alignment) u8,
30 nodes: []table.Node,
31 edges: []table.Edge,
32 text: []u8,
33 used_nodes: usize = 0,
34 used_edges: usize = 0,
35 used_text_bytes: usize = 0,
36 in_use: bool = false,
37
38 pub const Limits: type = capacity_mod.Limits;
39 pub const Capacity: type = capacity_mod.Capacity;
40 pub const Exhaustion: type = StorageExhaustion;
41 pub const InitError = std.mem.Allocator.Error || capacity_mod.DeriveError;
42 pub const AcquireError = Storage.Exhaustion;
43
44 pub const claim: alloc_phase.capacity.Declaration = .{
45 .source = .{
46 .id = "xkb.compose_storage",
47 .kind = .phase_static,
48 .limit_source = .caller,
49 .storage = .{
50 .covered = &.{
51 .{
52 .id = "compose_trie_nodes_and_sorted_transition_links",
53 .lifetime = .steady,
54 .detail = "Compose trie nodes and sorted transition links",
55 },
56 .{
57 .id = "compose_result_text_bytes",
58 .lifetime = .steady,
59 .detail = "Compose result text bytes",
60 },
61 },
62 .excluded = &.{
63 "caller-owned root Compose input bytes",
64 "loading scratch covered by xkb.compose_scratch_storage",
65 "diagnostic callbacks and filesystem handles",
66 "windowing keymaps, operating-system state, and teardown storage",
67 },
68 },
69 .capacity = .{
70 .inputs = &.{
71 alloc_phase.capacity.bindInput(Limits, "sequence_symbols", "sequence_symbols"),
72 alloc_phase.capacity.bindInput(Limits, "text_bytes", "text_bytes"),
73 },
74 .type_selectors = &.{},
75 .nodes = &.{
76 .{ .input = 0 },
77 .{ .constant = 1 },
78 .{ .input = 1 },
79 .{ .add = .{ .left = 0, .right = 1 } },
80 .{ .add = .{ .left = 3, .right = 0 } },
81 .{ .add = .{ .left = 4, .right = 2 } },
82 .{ .alignment = .{ .node = 5, .alignment = .{ .literal = 16 } } },
83 },
84 .assertions = &.{.{
85 .scope = .closure_total,
86 .measure = .retained,
87 .relation = .upper_bound,
88 .expression = 6,
89 }},
90 },
91 .overload = .{
92 .kind = .reject_before_mutation,
93 .detail = "Each rule reserves all missing trie symbols and result text before private trie mutation.",
94 },
95 .risks = .{
96 .transitive = .{
97 .status = .witnessed,
98 .detail = "Trie construction, publication, lookup, iteration, and reuse stay inside fixed regions.",
99 },
100 .foreign = .{
101 .status = .excluded,
102 .detail = "filesystem handles remain foreign initialization effects outside the bounded scratch owner",
103 },
104 },
105 .obligations = &.{
106 .{ .key = "xkb_compose_capacity", .role = .capacity_model },
107 .{ .key = "xkb_compose_acquisition", .role = .custom },
108 .{ .key = "xkb_compose_oom", .role = .custom },
109 .{ .key = "xkb_compose_boundaries", .role = .overload },
110 .{ .key = "xkb_compose_reuse", .role = .overload },
111 .{ .key = "xkb_compose_reserve", .role = .overload },
112 .{ .key = "xkb_compose_sealed", .role = .transitive_risk },
113 .{ .key = "xkb_compose_root", .role = .custom },
114 .{ .key = "xkb_compose_consumer", .role = .foreign_risk },
115 .{ .key = "xkb_compose_windowing_root", .role = .custom },
116 },
117 },
118 .bindings = .{
119 .owner = @This(),
120 .seal = .{
121 .family = alloc_phase.capacity.selector(@This().activate),
122 .premise = .{
123 .class = .checked_semantic_fact,
124 .authority = .checker,
125 },
126 },
127 .teardown = .{
128 .family = alloc_phase.capacity.selector(@This().deinit),
129 .premise = .{
130 .class = .checked_semantic_fact,
131 .authority = .checker,
132 },
133 },
134 },
135 };
136
137 pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!Storage {
138 const capacity = try Capacity.derive(limits);
139 const bytes = try allocator.alignedAlloc(
140 u8,
141 .fromByteUnits(capacity_mod.storage_alignment),
142 capacity.storage_bytes,
143 );
144 return .{
145 .phase = .initialization,
146 .capacity = capacity,
147 .bytes = bytes,
148 .nodes = typedSlice(
149 table.Node,
150 bytes,
151 capacity.node_offset,
152 capacity.node_count,
153 ),
154 .edges = typedSlice(
155 table.Edge,
156 bytes,
157 capacity.edge_offset,
158 capacity.edge_count,
159 ),
160 .text = bytes[capacity.text_offset..][0..capacity.limits.text_bytes],
161 };
162 }
163
164 pub fn activate(self: *Storage) void {
165 std.debug.assert(self.phase == .initialization);
166 std.debug.assert(self.bytes.len == self.capacity.storage_bytes);
167 self.phase = .steady;
168 }
169
170 pub fn acquire(self: *Storage) Storage.Exhaustion!void {
171 std.debug.assert(self.phase == .steady);
172 if (self.in_use) return error.ComposeStorageInUse;
173 self.in_use = true;
174 self.used_nodes = 1;
175 self.used_edges = 0;
176 self.used_text_bytes = 0;
177 self.nodes[0] = .{};
178 }
179
180 pub fn insert(
181 self: *Storage,
182 sequence: []const Keysym,
183 result_value: table.Result,
184 ) Storage.Exhaustion!void {
185 std.debug.assert(self.phase == .steady);
186 std.debug.assert(self.in_use);
187 std.debug.assert(sequence.len > 0);
188 std.debug.assert(sequence.len <= table.max_sequence_length);
189 if (result_value.text == null) std.debug.assert(result_value.symbol != null);
190 if (result_value.symbol) |symbol| std.debug.assert(symbol != .no_symbol);
191
192 const required_nodes = self.requiredNodes(sequence);
193 if (required_nodes > self.nodes.len - self.used_nodes or
194 required_nodes > self.edges.len - self.used_edges)
195 {
196 return error.SequenceSymbolCapacityExceeded;
197 }
198 const required_text = if (result_value.text) |value| value.len else 0;
199 if (required_text > self.text.len - self.used_text_bytes) {
200 return error.TextByteCapacityExceeded;
201 }
202
203 var node_index: u32 = 0;
204 for (sequence, 0..) |symbol, sequence_index| {
205 const last = sequence_index + 1 == sequence.len;
206 node_index = self.childAssumeCapacity(node_index, symbol);
207 const node = &self.nodes[node_index];
208 if (!last) {
209 if (node.result.has_result) {
210 node.result = .{};
211 node.first_edge = table.no_edge;
212 }
213 continue;
214 }
215
216 node.first_edge = table.no_edge;
217 node.result = self.storeAssumeCapacity(result_value);
218 }
219 }
220
221 pub fn publish(self: *const Storage) table.Table {
222 std.debug.assert(self.phase == .steady);
223 std.debug.assert(self.in_use);
224 return .{
225 .nodes = self.nodes[0..self.used_nodes],
226 .edges = self.edges[0..self.used_edges],
227 .text = self.text[0..self.used_text_bytes],
228 };
229 }
230
231 pub fn reset(self: *Storage) void {
232 std.debug.assert(self.phase == .steady);
233 std.debug.assert(self.in_use);
234 self.in_use = false;
235 self.used_nodes = 0;
236 self.used_edges = 0;
237 self.used_text_bytes = 0;
238 }
239
240 pub fn status(self: *const Storage) Status {
241 return .{
242 .phase = self.phase,
243 .in_use = self.in_use,
244 .storage_bytes = self.capacity.storage_bytes,
245 .sequence_symbols = self.capacity.limits.sequence_symbols,
246 .text_bytes = self.capacity.limits.text_bytes,
247 .used_nodes = self.used_nodes,
248 .used_edges = self.used_edges,
249 .used_text_bytes = self.used_text_bytes,
250 };
251 }
252
253 pub fn deinit(self: *Storage, allocator: std.mem.Allocator) void {
254 std.debug.assert(self.phase != .teardown);
255 std.debug.assert(!self.in_use);
256 std.debug.assert(self.bytes.len == self.capacity.storage_bytes);
257 self.phase = .teardown;
258 allocator.free(self.bytes);
259 self.bytes = &.{};
260 self.nodes = &.{};
261 self.edges = &.{};
262 self.text = &.{};
263 self.used_nodes = 0;
264 self.used_edges = 0;
265 self.used_text_bytes = 0;
266 }
267
268 fn requiredNodes(self: *const Storage, sequence: []const Keysym) usize {
269 var node_index: u32 = 0;
270 for (sequence, 0..) |symbol, sequence_index| {
271 const child_index = self.findChild(node_index, symbol) orelse
272 return sequence.len - sequence_index;
273 node_index = child_index;
274 if (sequence_index + 1 < sequence.len and
275 self.nodes[node_index].result.has_result)
276 {
277 return sequence.len - sequence_index - 1;
278 }
279 }
280 return 0;
281 }
282
283 fn findChild(self: *const Storage, parent_index: u32, symbol: Keysym) ?u32 {
284 var edge_index = self.nodes[parent_index].first_edge;
285 while (edge_index != table.no_edge) {
286 const edge = self.edges[edge_index];
287 const symbol_value = @backingInt(symbol);
288 const candidate_value = @backingInt(edge.symbol);
289 if (symbol_value < candidate_value) return null;
290 if (symbol_value == candidate_value) return edge.node;
291 edge_index = edge.next;
292 }
293 return null;
294 }
295
296 fn childAssumeCapacity(self: *Storage, parent_index: u32, symbol: Keysym) u32 {
297 var previous_edge: u32 = table.no_edge;
298 var next_edge = self.nodes[parent_index].first_edge;
299 while (next_edge != table.no_edge) {
300 const edge = self.edges[next_edge];
301 const symbol_value = @backingInt(symbol);
302 const candidate_value = @backingInt(edge.symbol);
303 if (symbol_value < candidate_value) break;
304 if (symbol_value == candidate_value) return edge.node;
305 previous_edge = next_edge;
306 next_edge = edge.next;
307 }
308
309 std.debug.assert(self.used_nodes < self.nodes.len);
310 std.debug.assert(self.used_edges < self.edges.len);
311 const child_index: u32 = @intCast(self.used_nodes);
312 const edge_index: u32 = @intCast(self.used_edges);
313 self.nodes[child_index] = .{};
314 self.edges[edge_index] = .{
315 .symbol = symbol,
316 .node = child_index,
317 .next = next_edge,
318 };
319 if (previous_edge == table.no_edge) {
320 self.nodes[parent_index].first_edge = edge_index;
321 } else {
322 self.edges[previous_edge].next = edge_index;
323 }
324 self.used_nodes += 1;
325 self.used_edges += 1;
326 return child_index;
327 }
328
329 fn storeAssumeCapacity(
330 self: *Storage,
331 result_value: table.Result,
332 ) table.StoredResult {
333 var stored = table.StoredResult{
334 .has_result = true,
335 .symbol = result_value.symbol orelse .no_symbol,
336 };
337 if (result_value.text) |text_value| {
338 std.debug.assert(text_value.len <= table.max_output_bytes);
339 std.debug.assert(text_value.len <= self.text.len - self.used_text_bytes);
340 stored.text_offset = @intCast(self.used_text_bytes);
341 stored.text_length = @intCast(text_value.len);
342 stored.has_text = true;
343 @memcpy(
344 self.text[self.used_text_bytes..][0..text_value.len],
345 text_value,
346 );
347 self.used_text_bytes += text_value.len;
348 }
349 return stored;
350 }
351 };
352
353 fn typedSlice(
354 comptime T: type,
355 bytes: []align(capacity_mod.storage_alignment) u8,
356 offset: usize,
357 count: usize,
358 ) []T {
359 const byte_count = count * @sizeOf(T);
360 const region: []align(@alignOf(T)) u8 = @alignCast(bytes[offset..][0..byte_count]);
361 return std.mem.bytesAsSlice(T, region);
362 }
363
364 fn checkInitFailures(allocator: std.mem.Allocator) !void {
365 var storage = try Storage.init(allocator, .{
366 .sequence_symbols = 16,
367 .text_bytes = 32,
368 });
369 storage.deinit(allocator);
370 }
371
372 test "Compose storage acquires one exact aligned region" {
373 comptime {
374 @stardustClaim(
375 @import("alloc_phase").capacity.witness(Storage, "xkb_compose_acquisition"),
376 null,
377 null,
378 null,
379 null,
380 null,
381 null,
382 );
383 }
384
385 var counting = std.testing.FailingAllocator.init(std.testing.allocator, .{});
386 const limits = capacity_mod.Limits{ .sequence_symbols = 16, .text_bytes = 32 };
387 const capacity = try capacity_mod.Capacity.derive(limits);
388 var storage = try Storage.init(counting.allocator(), limits);
389 defer storage.deinit(counting.allocator());
390 try std.testing.expectEqual(@as(usize, 1), counting.alloc_index);
391 try std.testing.expectEqual(capacity.storage_bytes, counting.allocated_bytes);
392 storage.activate();
393 try storage.acquire();
394 defer storage.reset();
395 const base = @intFromPtr(storage.bytes.ptr);
396 try std.testing.expectEqual(base + capacity.node_offset, @intFromPtr(storage.nodes.ptr));
397 try std.testing.expectEqual(base + capacity.edge_offset, @intFromPtr(storage.edges.ptr));
398 try std.testing.expectEqual(base + capacity.text_offset, @intFromPtr(storage.text.ptr));
399 }
400
401 test "Compose storage retries after every allocation failure" {
402 comptime {
403 @stardustClaim(
404 @import("alloc_phase").capacity.witness(Storage, "xkb_compose_oom"),
405 null,
406 null,
407 null,
408 null,
409 null,
410 null,
411 );
412 }
413
414 try std.testing.checkAllAllocationFailures(
415 std.testing.allocator,
416 checkInitFailures,
417 .{},
418 );
419 }
420
421 test "Compose storage preserves prefix replacement in sorted linked storage" {
422 var storage = try Storage.init(std.testing.allocator, .{
423 .sequence_symbols = 15,
424 .text_bytes = 32,
425 });
426 defer storage.deinit(std.testing.allocator);
427 storage.activate();
428 try storage.acquire();
429 defer storage.reset();
430
431 const a: Keysym = @fromBackingInt(@intCast('a'));
432 const b: Keysym = @fromBackingInt(@intCast('b'));
433 const c: Keysym = @fromBackingInt(@intCast('c'));
434 try storage.insert(&.{ a, b }, .{ .text = "old" });
435 try storage.insert(&.{ a, b, c }, .{ .text = "long" });
436 try storage.insert(&.{a}, .{ .text = "short", .symbol = b });
437 try storage.insert(&.{c}, .{ .symbol = a });
438
439 const published = storage.publish();
440 var iterator_value = published.iterator();
441 const first = iterator_value.next().?;
442 try std.testing.expectEqualSlices(Keysym, &.{a}, first.sequence);
443 try std.testing.expectEqualStrings("short", first.text.?);
444 try std.testing.expectEqual(@as(?Keysym, b), first.symbol);
445 const second = iterator_value.next().?;
446 try std.testing.expectEqualSlices(Keysym, &.{c}, second.sequence);
447 try std.testing.expect(second.text == null);
448 try std.testing.expectEqual(@as(?Keysym, a), second.symbol);
449 try std.testing.expect(iterator_value.next() == null);
450 }
451
452 test "Compose storage reserves a complete rule before private mutation" {
453 comptime {
454 @stardustClaim(
455 @import("alloc_phase").capacity.witness(Storage, "xkb_compose_reserve"),
456 null,
457 null,
458 null,
459 null,
460 null,
461 null,
462 );
463 }
464
465 var storage = try Storage.init(std.testing.allocator, .{
466 .sequence_symbols = 2,
467 .text_bytes = 3,
468 });
469 defer storage.deinit(std.testing.allocator);
470 storage.activate();
471 try storage.acquire();
472 defer storage.reset();
473 const a: Keysym = @fromBackingInt(@intCast('a'));
474 const b: Keysym = @fromBackingInt(@intCast('b'));
475 const c: Keysym = @fromBackingInt(@intCast('c'));
476 try storage.insert(&.{a}, .{ .text = "ok" });
477 const before = storage.status();
478 try std.testing.expectError(
479 error.SequenceSymbolCapacityExceeded,
480 storage.insert(&.{ b, c }, .{ .text = "x" }),
481 );
482 try std.testing.expectEqual(before, storage.status());
483 try std.testing.expectError(
484 error.TextByteCapacityExceeded,
485 storage.insert(&.{b}, .{ .text = "xx" }),
486 );
487 try std.testing.expectEqual(before, storage.status());
488 }
489
490 comptime {
491 alloc_phase.capacity.requireAllocatorRejectingOwnerShape(Storage);
492 }