lib/ui/src/tree/store.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3
4 const abi = @import("../abi/root.zig");
5 const asset = @import("../asset/root.zig");
6 const capacity_mod = @import("capacity.zig");
7 const map_mod = @import("map.zig");
8 const splice_mod = @import("splice.zig");
9 const survey_mod = @import("survey.zig");
10 const view_mod = @import("view.zig");
11
12 const Allocator = std.mem.Allocator;
13 const LimitsType = capacity_mod.Limits;
14 const CapacityType = capacity_mod.Capacity;
15 const Map = map_mod.Map;
16 const View = view_mod.View;
17
18 /// `storage_alignment` is the byte alignment of a `Store`'s allocation and of every buffer
19 /// `Store.publish` accepts.
20 pub const storage_alignment: usize = 8;
21
22 pub const Error = survey_mod.Error;
23
24 /// `Accepted` is the result of an accepted publish.
25 pub const Accepted = struct {
26 /// `Accepted.dirty` is the number of nodes `Store.dirty` lists.
27 dirty: u32 = 0,
28 /// `Accepted.unchanged` is true when that number is 0.
29 unchanged: bool = false,
30 };
31
32 /// `Store` retains one accepted tree. `init` makes its only allocation, sized by
33 /// `Capacity.derive`, which holds two envelope blocks, one identity map per block, and the
34 /// splice scratch. The retained tree occupies one block. An accepted publish with a new revision
35 /// is written into the other block, which then becomes the retained one.
36 pub const Store = struct {
37 pub const Limits = LimitsType;
38 pub const Capacity = CapacityType;
39
40 /// `Store.claim` is the static capacity claim `ui.publish_store`. It declares that the store's
41 /// retained bytes are exactly two blocks, two identity maps, and the scratch arrays, all
42 /// derived from `Limits`, and it names six witness tests.
43 pub const claim: alloc_phase.capacity.Declaration = .{
44 .source = .{
45 .id = "ui.publish_store",
46 .kind = .phase_static,
47 .limit_source = .caller,
48 .storage = .{
49 .covered = &.{
50 .{
51 .id = "double_buffered_retained_envelope_blocks",
52 .lifetime = .steady,
53 .detail = "the store's two envelope blocks, each Capacity.buffer_bytes " ++
54 "long and aligned to storage_alignment, with one block holding the " ++
55 "retained tree and the splice writing the next tree into the other",
56 },
57 .{
58 .id = "open_addressed_node_identity_maps",
59 .lifetime = .steady,
60 .detail = "one identity map slot array of Limits.map_slots words for " ++
61 "each envelope block",
62 },
63 .{
64 .id = "splice_scratch_arrays",
65 .lifetime = .steady,
66 .detail = "the dirty node list and the placement map of Limits.nodes " ++
67 "words each, and the atom and text remap arrays of Limits.atoms " ++
68 "and Limits.texts words",
69 },
70 },
71 .excluded = &.{
72 "the publish buffer, which the caller owns and passes to Store.publish, " ++
73 "where the survey reads it in place and the store keeps only the " ++
74 "bytes the splice copies into its own block",
75 "storage for computed style, layout, and facts derived from the retained " ++
76 "tree, which belongs to the packages that compute them, with Store " ++
77 "having no field for any of it",
78 },
79 },
80 .capacity = .{
81 .inputs = &.{
82 alloc_phase.capacity.bindInput(LimitsType, "nodes", "nodes"),
83 alloc_phase.capacity.bindInput(LimitsType, "declarations", "declarations"),
84 alloc_phase.capacity.bindInput(LimitsType, "classes", "classes"),
85 alloc_phase.capacity.bindInput(LimitsType, "texts", "texts"),
86 alloc_phase.capacity.bindInput(LimitsType, "runs", "runs"),
87 alloc_phase.capacity.bindInput(LimitsType, "relations", "relations"),
88 alloc_phase.capacity.bindInput(LimitsType, "atoms", "atoms"),
89 alloc_phase.capacity.bindInput(LimitsType, "string_bytes", "string_bytes"),
90 alloc_phase.capacity.bindInput(LimitsType, "solved_roots", "solved_roots"),
91 alloc_phase.capacity.bindInput(LimitsType, "solved_rects", "solved_rects"),
92 alloc_phase.capacity.bindInput(LimitsType, "map_slots", "map_slots"),
93 },
94 .type_selectors = &.{
95 alloc_phase.capacity.bindType(abi.Node, "node"),
96 alloc_phase.capacity.bindType(abi.Declaration, "declaration"),
97 alloc_phase.capacity.bindType(u32, "u32"),
98 alloc_phase.capacity.bindType(abi.TextRecord, "text_record"),
99 alloc_phase.capacity.bindType(abi.TextRun, "text_run"),
100 alloc_phase.capacity.bindType(abi.Relation, "relation"),
101 alloc_phase.capacity.bindType(abi.Atom, "atom"),
102 alloc_phase.capacity.bindType(u8, "u8"),
103 alloc_phase.capacity.bindType(abi.SolvedRoot, "solved_root"),
104 alloc_phase.capacity.bindType(abi.Rect, "rect"),
105 },
106 .nodes = &.{
107 .{ .input = 0 },
108 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
109 .{ .input = 1 },
110 .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 1 } } },
111 .{ .input = 2 },
112 .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 2 } } },
113 .{ .input = 3 },
114 .{ .scale = .{ .node = 6, .coefficient = .{ .size_of_concrete_type = 3 } } },
115 .{ .input = 4 },
116 .{ .scale = .{ .node = 8, .coefficient = .{ .size_of_concrete_type = 4 } } },
117 .{ .input = 5 },
118 .{ .scale = .{ .node = 10, .coefficient = .{ .size_of_concrete_type = 5 } } },
119 .{ .input = 6 },
120 .{ .scale = .{ .node = 12, .coefficient = .{ .size_of_concrete_type = 6 } } },
121 .{ .input = 7 },
122 .{ .scale = .{ .node = 14, .coefficient = .{ .size_of_concrete_type = 7 } } },
123 .{ .input = 8 },
124 .{ .scale = .{ .node = 16, .coefficient = .{ .size_of_concrete_type = 8 } } },
125 .{ .input = 9 },
126 .{ .scale = .{ .node = 18, .coefficient = .{ .size_of_concrete_type = 9 } } },
127 .{ .input = 10 },
128 .{ .scale = .{ .node = 20, .coefficient = .{ .size_of_concrete_type = 2 } } },
129 .{ .constant = 152 },
130 .{ .alignment = .{ .node = 22, .alignment = .{ .concrete_type = 0 } } },
131 .{ .add = .{ .left = 23, .right = 1 } },
132 .{ .alignment = .{ .node = 24, .alignment = .{ .concrete_type = 1 } } },
133 .{ .add = .{ .left = 25, .right = 3 } },
134 .{ .alignment = .{ .node = 26, .alignment = .{ .concrete_type = 2 } } },
135 .{ .add = .{ .left = 27, .right = 5 } },
136 .{ .alignment = .{ .node = 28, .alignment = .{ .concrete_type = 3 } } },
137 .{ .add = .{ .left = 29, .right = 7 } },
138 .{ .alignment = .{ .node = 30, .alignment = .{ .concrete_type = 4 } } },
139 .{ .add = .{ .left = 31, .right = 9 } },
140 .{ .alignment = .{ .node = 32, .alignment = .{ .concrete_type = 5 } } },
141 .{ .add = .{ .left = 33, .right = 11 } },
142 .{ .alignment = .{ .node = 34, .alignment = .{ .concrete_type = 6 } } },
143 .{ .add = .{ .left = 35, .right = 13 } },
144 .{ .alignment = .{ .node = 36, .alignment = .{ .concrete_type = 7 } } },
145 .{ .add = .{ .left = 37, .right = 15 } },
146 .{ .alignment = .{ .node = 38, .alignment = .{ .concrete_type = 8 } } },
147 .{ .add = .{ .left = 39, .right = 17 } },
148 .{ .alignment = .{ .node = 40, .alignment = .{ .concrete_type = 9 } } },
149 .{ .add = .{ .left = 41, .right = 19 } },
150 .{ .alignment = .{ .node = 42, .alignment = .{ .literal = 8 } } },
151 .{ .add = .{ .left = 43, .right = 43 } },
152 .{ .add = .{ .left = 21, .right = 21 } },
153 .{ .add = .{ .left = 44, .right = 45 } },
154 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 2 } } },
155 .{ .add = .{ .left = 46, .right = 47 } },
156 .{ .add = .{ .left = 48, .right = 47 } },
157 .{ .scale = .{ .node = 12, .coefficient = .{ .size_of_concrete_type = 2 } } },
158 .{ .add = .{ .left = 49, .right = 50 } },
159 .{ .scale = .{ .node = 6, .coefficient = .{ .size_of_concrete_type = 2 } } },
160 .{ .add = .{ .left = 51, .right = 52 } },
161 },
162 .assertions = &.{.{
163 .scope = .closure_total,
164 .measure = .retained,
165 .relation = .exact,
166 .expression = 53,
167 }},
168 },
169 .overload = .{
170 .kind = .reject_before_seal,
171 .detail = "Store.publish runs the admission survey over the caller's buffer " ++
172 "before the splice, and the survey rejects every quota, encoding, and " ++
173 "retained reference fault, so a rejected publish writes no retained byte",
174 },
175 .risks = .{
176 .transitive = .{
177 .status = .open,
178 .detail = "the survey and the splice take no allocator, and six witness " ++
179 "tests cover the store, but no machine-checked certificate of their " ++
180 "call graphs proves them allocation free",
181 },
182 .foreign = .{
183 .status = .excluded,
184 .detail = "admission and splicing transform one caller buffer inside the " ++
185 "process and make no operating-system call",
186 },
187 },
188 .obligations = &.{
189 .{ .key = "ui_publish_capacity", .role = .capacity_model },
190 .{ .key = "ui_publish_acquisition", .role = .acquisition },
191 .{ .key = "ui_publish_survey", .role = .overload },
192 .{ .key = "ui_publish_oom", .role = .initialization_failure },
193 .{ .key = "ui_publish_retained", .role = .integration },
194 .{ .key = "ui_publish_teardown", .role = .teardown },
195 },
196 },
197 .bindings = .{
198 .owner = @This(),
199 .seal = .{
200 .family = alloc_phase.capacity.selector(@This().activate),
201 .premise = .{
202 .class = .checked_semantic_fact,
203 .authority = .checker,
204 },
205 },
206 .teardown = .{
207 .family = alloc_phase.capacity.selector(@This().deinit),
208 .premise = .{
209 .class = .checked_semantic_fact,
210 .authority = .checker,
211 },
212 },
213 },
214 };
215
216 phase: alloc_phase.capacity.Phase,
217 limits: LimitsType,
218 capacity: CapacityType,
219 bytes: []align(storage_alignment) u8,
220 blocks: [2][]align(storage_alignment) u8,
221 maps: [2]Map,
222 scratch: splice_mod.Scratch,
223 live: u1 = 0,
224 live_bytes: u32 = 0,
225 present: bool = false,
226 dirty_count: u32 = 0,
227 assets: ?*const asset.Registry = null,
228 asset_epoch: u64 = 0,
229
230 /// `init` derives the capacity from `limits`, makes the one allocation, and lays out the
231 /// blocks, maps, and scratch inside it. It returns `error.CapacityOverflow` or the
232 /// allocator's error.
233 pub fn init(allocator: Allocator, limits: LimitsType) !Store {
234 const capacity = try CapacityType.derive(limits);
235 const bytes = try allocator.alignedAlloc(
236 u8,
237 .fromByteUnits(storage_alignment),
238 capacity.total_bytes,
239 );
240 var store = Store{
241 .phase = .initialization,
242 .limits = limits,
243 .capacity = capacity,
244 .bytes = bytes,
245 .blocks = undefined,
246 .maps = undefined,
247 .scratch = undefined,
248 };
249 store.place();
250 return store;
251 }
252
253 /// `activate` empties both identity maps and moves the store into its steady phase. `admits`,
254 /// `publish`, and `forget` assert that phase.
255 pub fn activate(self: *Store) void {
256 std.debug.assert(self.phase == .initialization);
257 self.assertStorage();
258 self.maps[0].reset();
259 self.maps[1].reset();
260 self.phase = .steady;
261 }
262
263 pub fn setAssets(self: *Store, assets: *const asset.Registry) void {
264 std.debug.assert(self.phase == .initialization);
265 std.debug.assert(assets.phase == .steady);
266 self.assets = assets;
267 self.asset_epoch = assets.epoch;
268 }
269
270 /// `admits` returns true when every field of `limits` is at most the limit this store was
271 /// sized with.
272 pub fn admits(self: *const Store, limits: LimitsType) bool {
273 std.debug.assert(self.phase == .steady);
274 return limits.fits(self.limits);
275 }
276
277 /// `publish` accepts one envelope buffer or returns the first rejection. It reads the header
278 /// first. `Store.publish` returns after the header when the revision equals the retained
279 /// revision and the registry epoch equals the epoch at the last accepted publish. The
280 /// registry epoch changes whenever a font or image registers or releases, so when the epoch
281 /// differs, admission checks asset handles again even if the tree revision is the same.
282 /// Otherwise `admit` checks the whole buffer and the
283 /// splice writes it into the other block. A rejected publish leaves `retained`, `dirty`, and
284 /// `identity` as they were.
285 pub fn publish(self: *Store, buffer: []align(storage_alignment) const u8) Error!Accepted {
286 std.debug.assert(self.phase == .steady);
287 const head = try view_mod.readHeader(buffer);
288 const current_asset_epoch = if (self.assets) |assets| assets.epoch else 0;
289 if (self.present and head.revision == self.retained().header.revision and current_asset_epoch == self.asset_epoch) {
290 self.dirty_count = 0;
291 return .{ .dirty = 0, .unchanged = true };
292 }
293 const next: u1 = self.live ^ 1;
294 const report = try survey_mod.survey(buffer, self.limits, self.state(), &self.maps[next]);
295 const outcome = splice_mod.splice(
296 self.blocks[next],
297 &self.maps[next],
298 self.capacity,
299 report,
300 self.state(),
301 self.scratch,
302 );
303 self.live = next;
304 self.live_bytes = outcome.bytes;
305 self.present = true;
306 self.dirty_count = outcome.dirty;
307 self.asset_epoch = current_asset_epoch;
308 return .{ .dirty = outcome.dirty, .unchanged = outcome.dirty == 0 };
309 }
310
311 /// `forget` drops the retained tree and empties both identity maps, so the next publish is
312 /// surveyed with no retained tree. A node carrying the `retained` flag is rejected with
313 /// `error.StaleRetainedSubtree`, and an accepted publish marks every one of its nodes dirty.
314 pub fn forget(self: *Store) void {
315 std.debug.assert(self.phase == .steady);
316 self.maps[0].reset();
317 self.maps[1].reset();
318 self.present = false;
319 self.live_bytes = 0;
320 self.dirty_count = 0;
321 self.asset_epoch = if (self.assets) |assets| assets.epoch else 0;
322 }
323
324 /// `retained` returns a `View` of the retained tree, or an empty `View` when no tree is
325 /// retained. The view points into the store's block. After an accepted publish with a new
326 /// revision, a view taken earlier no longer shows the retained tree.
327 pub fn retained(self: *const Store) View {
328 if (!self.present) return .{};
329 var view = view_mod.bind(self.blocks[self.live][0..self.live_bytes]) catch unreachable;
330 view.identity = &self.maps[self.live];
331 view.prior = self.scratch.dirty[0..view.nodes.len];
332 return view;
333 }
334
335 /// `dirty` returns, in ascending order, the indices in `retained().nodes` of the nodes the
336 /// last accepted publish marked dirty. It is empty after a publish at the retained revision
337 /// and after `forget`.
338 pub fn dirty(self: *const Store) []const u32 {
339 return self.scratch.place[0..self.dirty_count];
340 }
341
342 /// `identity` returns the identity map of the retained tree. Pass `retained().nodes` to its
343 /// `lookup`.
344 pub fn identity(self: *const Store) *const Map {
345 return &self.maps[self.live];
346 }
347
348 /// `deinit` frees the allocation and moves the store into its teardown phase. After it,
349 /// `retained` returns an empty `View`.
350 pub fn deinit(self: *Store, allocator: Allocator) void {
351 std.debug.assert(self.phase != .teardown);
352 self.assertStorage();
353 self.phase = .teardown;
354 allocator.free(self.bytes);
355 self.bytes = &.{};
356 self.blocks = .{ &.{}, &.{} };
357 self.maps = .{ .{}, .{} };
358 self.scratch = .{ .place = &.{}, .atom_remap = &.{}, .text_remap = &.{}, .dirty = &.{} };
359 self.present = false;
360 self.assets = null;
361 self.asset_epoch = 0;
362 }
363
364 fn state(self: *const Store) survey_mod.Retained {
365 if (!self.present) return .{ .assets = self.assets };
366 const view = self.retained();
367 return .{
368 .view = view,
369 .map = self.maps[self.live],
370 .revision = view.header.revision,
371 .present = true,
372 .assets = self.assets,
373 };
374 }
375
376 fn place(self: *Store) void {
377 const block = self.capacity.buffer_bytes;
378 var cursor: usize = 0;
379 for (&self.blocks) |*slot| {
380 slot.* = @alignCast(self.bytes[cursor..][0..block]);
381 cursor += block;
382 }
383 for (&self.maps) |*slot| {
384 slot.* = .{ .slots = words(self.bytes, &cursor, self.limits.map_slots) };
385 }
386 self.scratch = .{
387 .dirty = words(self.bytes, &cursor, self.limits.nodes),
388 .place = words(self.bytes, &cursor, self.limits.nodes),
389 .atom_remap = words(self.bytes, &cursor, self.limits.atoms),
390 .text_remap = words(self.bytes, &cursor, self.limits.texts),
391 };
392 std.debug.assert(cursor == self.capacity.total_bytes);
393 }
394
395 fn assertStorage(self: *const Store) void {
396 const expected = CapacityType.derive(self.limits) catch unreachable;
397 std.debug.assert(std.meta.eql(expected, self.capacity));
398 std.debug.assert(self.bytes.len == self.capacity.total_bytes);
399 std.debug.assert(self.blocks[0].len == self.capacity.buffer_bytes);
400 std.debug.assert(self.blocks[1].len == self.capacity.buffer_bytes);
401 std.debug.assert(self.maps[0].slots.len == self.limits.map_slots);
402 std.debug.assert(self.scratch.dirty.len == self.limits.nodes);
403 }
404 };
405
406 fn words(bytes: []align(storage_alignment) u8, cursor: *usize, count: u32) []u32 {
407 const total = @as(usize, count) * 4;
408 const region: []align(4) u8 = @alignCast(bytes[cursor.*..][0..total]);
409 cursor.* += total;
410 return std.mem.bytesAsSlice(u32, region);
411 }
412
413 comptime {
414 alloc_phase.capacity.requireAllocatorExactOwnerShape(Store);
415 }
416
417 const fixture = @import("fixture/publish.zig");
418
419 const probe_limits = LimitsType{
420 .nodes = 64,
421 .declarations = 128,
422 .classes = 64,
423 .texts = 16,
424 .runs = 16,
425 .relations = 8,
426 .atoms = 64,
427 .string_bytes = 1_024,
428 .solved_roots = 8,
429 .solved_rects = 32,
430 .map_slots = 256,
431 };
432
433 const Harness = struct {
434 store: Store,
435 scratch: []align(storage_alignment) u8,
436
437 fn init() !Harness {
438 var store = try Store.init(std.testing.allocator, probe_limits);
439 errdefer store.deinit(std.testing.allocator);
440 store.activate();
441 const scratch = try std.testing.allocator.alignedAlloc(
442 u8,
443 .fromByteUnits(storage_alignment),
444 8_192,
445 );
446 return .{ .store = store, .scratch = scratch };
447 }
448
449 fn send(self: *Harness, plan: fixture.Plan) Error!Accepted {
450 const bytes = fixture.build(std.testing.allocator, self.scratch, plan) catch unreachable;
451 return self.store.publish(bytes);
452 }
453
454 fn deinit(self: *Harness) void {
455 self.store.deinit(std.testing.allocator);
456 std.testing.allocator.free(self.scratch);
457 }
458 };
459
460 fn held(harness: *const Harness, id: u64) ?u32 {
461 const view = harness.store.retained();
462 return harness.store.identity().lookup(view.nodes, id);
463 }
464
465 const shelf = [_]fixture.Spec{
466 .{ .id = 1, .revision = 100, .subtree_count = 3 },
467 .{ .id = 2, .revision = 200, .parent = 0, .subtree_count = 1 },
468 .{ .id = 3, .revision = 300, .parent = 1 },
469 .{ .id = 4, .revision = 400, .parent = 0 },
470 };
471
472 test "ui_asset_generation stale handle is rejected before retained bytes change" {
473 var registry = try asset.Registry.init(std.testing.allocator, .{ .fonts = 1, .images = 0, .owned_bytes = 0 });
474 defer registry.deinit(std.testing.allocator);
475 registry.activate();
476 const handle = try registry.registerFont("A", .{}, .{ .borrowed = "font" });
477 var store = try Store.init(std.testing.allocator, probe_limits);
478 defer store.deinit(std.testing.allocator);
479 store.setAssets(®istry);
480 store.activate();
481 var scratch: [8192]u8 align(8) = undefined;
482 const declaration = [_]abi.Declaration{.{
483 .property = @backingInt(abi.PropertyId.font_family),
484 .kind = @backingInt(@import("css").value.Kind.asset),
485 .unit = 0,
486 .flags = 0,
487 .a = handle.index,
488 .b = handle.generation,
489 }};
490 const specs = [_]fixture.Spec{.{ .id = 1, .declarations = &declaration }};
491 const buffer = try fixture.build(std.testing.allocator, &scratch, .{ .revision = 1, .specs = &specs });
492 _ = try store.publish(buffer);
493 const retained_before = store.retained().bytes;
494 const saved = try std.testing.allocator.dupe(u8, retained_before);
495 defer std.testing.allocator.free(saved);
496 try registry.release(.font, handle);
497 try std.testing.expectError(error.StaleAsset, store.publish(buffer));
498 try std.testing.expectEqualSlices(u8, saved, store.retained().bytes);
499 }
500
501 test "malformed text keeps the retained publish at its base revision" {
502 var harness = try Harness.init();
503 defer harness.deinit();
504 _ = try harness.send(.{ .revision = 1, .specs = &.{.{ .id = 1, .text = "base" }} });
505 const saved = try std.testing.allocator.dupe(u8, harness.store.retained().bytes);
506 defer std.testing.allocator.free(saved);
507 const malformed = [_][]const u8{
508 &.{ 0xc0, 0xaf },
509 &.{0x80},
510 &.{ 0xe2, 0x82 },
511 };
512 for (malformed) |bytes| {
513 try std.testing.expectError(error.TextNotUtf8, harness.send(.{
514 .revision = 2,
515 .base_revision = 1,
516 .specs = &.{.{ .id = 1, .text = bytes }},
517 }));
518 const retained = harness.store.retained();
519 try std.testing.expectEqual(@as(u64, 1), retained.header.revision);
520 try std.testing.expectEqualSlices(u8, saved, retained.bytes);
521 }
522 }
523
524 test "a first publish copies the whole tree and dirties every node" {
525 var harness = try Harness.init();
526 defer harness.deinit();
527 const accepted = try harness.send(.{ .revision = 1, .specs = &shelf });
528 try std.testing.expectEqual(@as(u32, 4), accepted.dirty);
529 try std.testing.expect(!accepted.unchanged);
530 const view = harness.store.retained();
531 try std.testing.expectEqual(@as(usize, 4), view.nodes.len);
532 try std.testing.expectEqualSlices(u32, &.{ 0, 1, 2, 3 }, harness.store.dirty());
533 try std.testing.expectEqual(@as(u64, 300), view.nodes[2].revision);
534 }
535
536 test "a republish at the retained revision accepts on the header alone" {
537 var harness = try Harness.init();
538 defer harness.deinit();
539 _ = try harness.send(.{ .revision = 1, .specs = &shelf });
540 const before = harness.store.retained().bytes.ptr;
541 const accepted = try harness.send(.{ .revision = 1, .specs = &shelf });
542 try std.testing.expect(accepted.unchanged);
543 try std.testing.expectEqual(@as(u32, 0), accepted.dirty);
544 try std.testing.expectEqual(@as(usize, 0), harness.store.dirty().len);
545 try std.testing.expectEqual(before, harness.store.retained().bytes.ptr);
546 }
547
548 test "a new generation whose node revisions all match dirties nothing" {
549 var harness = try Harness.init();
550 defer harness.deinit();
551 _ = try harness.send(.{ .revision = 1, .specs = &shelf });
552 const accepted = try harness.send(.{ .revision = 2, .specs = &shelf });
553 try std.testing.expectEqual(@as(u32, 0), accepted.dirty);
554 try std.testing.expect(accepted.unchanged);
555 const view = harness.store.retained();
556 try std.testing.expectEqual(@as(u64, 2), view.header.revision);
557 try std.testing.expectEqual(@as(usize, 4), view.nodes.len);
558 }
559
560 test "one changed leaf dirties its ancestors and leaves its siblings held" {
561 var harness = try Harness.init();
562 defer harness.deinit();
563 _ = try harness.send(.{ .revision = 1, .specs = &shelf });
564 var next = shelf;
565 next[0].revision = 101;
566 next[3].revision = 401;
567 const accepted = try harness.send(.{ .revision = 2, .specs = &next });
568 try std.testing.expectEqual(@as(u32, 2), accepted.dirty);
569 try std.testing.expectEqualSlices(u32, &.{ 0, 3 }, harness.store.dirty());
570 try std.testing.expectEqual(@as(u64, 401), harness.store.retained().nodes[3].revision);
571 }
572
573 test "a moved subtree stays clean under its new parent while changed ancestors are dirtied" {
574 var harness = try Harness.init();
575 defer harness.deinit();
576 _ = try harness.send(.{ .revision = 1, .specs = &shelf });
577 const moved = [_]fixture.Spec{
578 .{ .id = 1, .revision = 101, .subtree_count = 3 },
579 .{ .id = 4, .revision = 401, .parent = 0, .subtree_count = 2 },
580 .{ .id = 2, .revision = 200, .parent = 1, .subtree_count = 1 },
581 .{ .id = 3, .revision = 300, .parent = 2 },
582 };
583 const accepted = try harness.send(.{ .revision = 2, .specs = &moved });
584 try std.testing.expectEqualSlices(u32, &.{ 0, 1 }, harness.store.dirty());
585 try std.testing.expectEqual(@as(u32, 2), accepted.dirty);
586 const view = harness.store.retained();
587 try std.testing.expectEqualSlices(u32, &.{ splice_mod.prior_dirty, splice_mod.prior_dirty | 3, 1, 2 }, view.prior);
588 try std.testing.expectEqual(@as(?u32, 2), view.identity.?.lookup(view.nodes, 2));
589 try std.testing.expectEqual(@as(u64, 2), view.nodes[2].id);
590 try std.testing.expectEqual(@as(u32, 1), view.nodes[2].parent);
591 try std.testing.expectEqual(@as(u64, 3), view.nodes[3].id);
592 try std.testing.expectEqual(@as(u32, 2), view.nodes[3].parent);
593 }
594
595 test "a removed subtree shrinks the tree and forgets its identifiers" {
596 var harness = try Harness.init();
597 defer harness.deinit();
598 _ = try harness.send(.{ .revision = 1, .specs = &shelf });
599 try std.testing.expect(held(&harness, 3) != null);
600 const pruned = [_]fixture.Spec{
601 .{ .id = 1, .revision = 102, .subtree_count = 1 },
602 .{ .id = 4, .revision = 400, .parent = 0 },
603 };
604 const accepted = try harness.send(.{ .revision = 2, .specs = &pruned });
605 try std.testing.expectEqual(@as(u32, 1), accepted.dirty);
606 try std.testing.expectEqualSlices(u32, &.{0}, harness.store.dirty());
607 try std.testing.expectEqual(@as(usize, 2), harness.store.retained().nodes.len);
608 try std.testing.expect(held(&harness, 3) == null);
609 try std.testing.expect(held(&harness, 4) != null);
610 }
611
612 fn openAndClose(allocator: Allocator, limits: LimitsType) !void {
613 var store = try Store.init(allocator, limits);
614 defer store.deinit(allocator);
615 store.activate();
616 try std.testing.expectEqual(alloc_phase.capacity.Phase.steady, store.phase);
617 }
618
619 test "the publish store sizes its owned block from an independent model" {
620 comptime {
621 @stardustClaim(
622 alloc_phase.capacity.witness(Store, "ui_publish_capacity"),
623 null,
624 null,
625 null,
626 null,
627 null,
628 null,
629 );
630 }
631
632 for ([_]LimitsType{ .{}, probe_limits, .{ .nodes = 1, .map_slots = 2 } }) |limits| {
633 const derived = try CapacityType.derive(limits);
634 const buffer = capacity_mod.modelBufferBytes(limits);
635 const maps = 2 * @as(u64, limits.map_slots) * 4;
636 const scratch = (@as(u64, limits.nodes) * 2 + @as(u64, limits.atoms) +
637 @as(u64, limits.texts)) * 4;
638 try std.testing.expectEqual(buffer, derived.buffer_bytes);
639 try std.testing.expectEqual(2 * buffer + maps + scratch, derived.total_bytes);
640 }
641 }
642
643 test "the publish store retries acquisition after every allocation failure" {
644 comptime {
645 @stardustClaim(
646 alloc_phase.capacity.witness(Store, "ui_publish_acquisition"),
647 null,
648 null,
649 null,
650 null,
651 null,
652 null,
653 );
654 }
655
656 try std.testing.checkAllAllocationFailures(
657 std.testing.allocator,
658 openAndClose,
659 .{probe_limits},
660 );
661 }
662
663 test "the publish store reports a refused acquisition instead of a partial one" {
664 comptime {
665 @stardustClaim(
666 alloc_phase.capacity.witness(Store, "ui_publish_oom"),
667 null,
668 null,
669 null,
670 null,
671 null,
672 null,
673 );
674 }
675
676 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 0 });
677 try std.testing.expectError(error.OutOfMemory, Store.init(failing.allocator(), probe_limits));
678 try std.testing.expectEqual(@as(usize, 0), failing.allocated_bytes - failing.freed_bytes);
679 try std.testing.expectError(
680 error.CapacityOverflow,
681 Store.init(std.testing.allocator, .{ .declarations = std.math.maxInt(u32) }),
682 );
683 }
684
685 test "a publish past the declared quota leaves the retained tree whole" {
686 comptime {
687 @stardustClaim(
688 alloc_phase.capacity.witness(Store, "ui_publish_survey"),
689 null,
690 null,
691 null,
692 null,
693 null,
694 null,
695 );
696 }
697
698 var harness = try Harness.init();
699 defer harness.deinit();
700 _ = try harness.send(.{ .revision = 1, .specs = &shelf });
701 const before = harness.store.retained();
702 const wide = try fixture.chain(std.testing.allocator, probe_limits.nodes + 1);
703 defer std.testing.allocator.free(wide);
704 try std.testing.expectError(
705 error.NodeLimitExceeded,
706 harness.send(.{ .revision = 2, .specs = wide }),
707 );
708 const after = harness.store.retained();
709 try std.testing.expectEqual(before.bytes.ptr, after.bytes.ptr);
710 try std.testing.expectEqual(@as(usize, 4), after.nodes.len);
711 try std.testing.expectEqual(@as(u64, 1), after.header.revision);
712 }
713
714 test "a retained subtree splices by reference into the next generation" {
715 comptime {
716 @stardustClaim(
717 alloc_phase.capacity.witness(Store, "ui_publish_retained"),
718 null,
719 null,
720 null,
721 null,
722 null,
723 null,
724 );
725 }
726
727 var harness = try Harness.init();
728 defer harness.deinit();
729 _ = try harness.send(.{ .revision = 1, .specs = &shelf });
730 const grafted = [_]fixture.Spec{
731 .{ .id = 7, .revision = 700, .subtree_count = 1 },
732 .{ .id = 2, .revision = 200, .parent = 0, .flags = abi.flag(.retained) },
733 };
734 _ = try harness.send(.{ .revision = 2, .base_revision = 1, .specs = &grafted });
735 const view = harness.store.retained();
736 try std.testing.expectEqual(@as(usize, 3), view.nodes.len);
737 try std.testing.expectEqual(@as(u64, 7), view.nodes[0].id);
738 try std.testing.expectEqual(@as(u64, 2), view.nodes[1].id);
739 try std.testing.expectEqual(@as(u32, 1), view.nodes[1].subtree_count);
740 try std.testing.expectEqual(@as(u64, 3), view.nodes[2].id);
741 try std.testing.expectEqual(@as(u32, 1), view.nodes[2].parent);
742 }
743
744 test "a retained solved subtree cannot discard its supplied rectangles" {
745 var harness = try Harness.init();
746 defer harness.deinit();
747 const solved = [_]fixture.Spec{.{ .id = 1, .flags = abi.flag(.solved) }};
748 const roots = [_]abi.SolvedRoot{.{ .node = 0, .rect_first = 0 }};
749 const rects = [_]abi.Rect{.{ .x = -3, .width = 7, .height = 5 }};
750 _ = try harness.send(.{
751 .revision = 1,
752 .specs = &solved,
753 .solved_roots = &roots,
754 .solved_rects = &rects,
755 });
756 const retained = [_]fixture.Spec{.{ .id = 1, .flags = abi.flag(.retained) }};
757 try std.testing.expectError(error.RetainedSolvedSubtree, harness.send(.{
758 .revision = 2,
759 .base_revision = 1,
760 .specs = &retained,
761 }));
762 const after = harness.store.retained();
763 try std.testing.expectEqual(@as(u64, 1), after.header.revision);
764 try std.testing.expectEqual(rects[0], after.solved_rects[0]);
765 }
766
767 test "the publish store releases its block once and marks the phase spent" {
768 comptime {
769 @stardustClaim(
770 alloc_phase.capacity.witness(Store, "ui_publish_teardown"),
771 null,
772 null,
773 null,
774 null,
775 null,
776 null,
777 );
778 }
779
780 var harness = try Harness.init();
781 _ = try harness.send(.{ .revision = 1, .specs = &shelf });
782 harness.deinit();
783 try std.testing.expectEqual(alloc_phase.capacity.Phase.teardown, harness.store.phase);
784 }