lib/ui/src/tree/survey.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const arrange = @import("arrange");
3
4 const abi = @import("../abi/root.zig");
5 const asset = @import("../asset/root.zig");
6 const capacity = @import("capacity.zig");
7 const map_mod = @import("map.zig");
8 const view_mod = @import("view.zig");
9
10 const Limits = capacity.Limits;
11 const Map = map_mod.Map;
12 const View = view_mod.View;
13
14 /// `Error` is every rejection that `survey` and `Store.publish` return.
15 /// It includes every `BindError`.
16 pub const Error = view_mod.BindError || error{
17 PublishTooLarge,
18 NodeLimitExceeded,
19 DeclarationLimitExceeded,
20 ClassLimitExceeded,
21 TextLimitExceeded,
22 RunLimitExceeded,
23 RelationLimitExceeded,
24 AtomLimitExceeded,
25 StringLimitExceeded,
26 SolvedRootLimitExceeded,
27 SolvedRectLimitExceeded,
28 SubtreeExtentOutOfBounds,
29 ParentNotAncestor,
30 RootParentMismatch,
31 RootSubtreeIncomplete,
32 DepthExceeded,
33 DuplicateNodeId,
34 StaleRetainedSubtree,
35 RetainedSubtreeNotEmpty,
36 AtomIndexOutOfBounds,
37 AtomTextOutOfBounds,
38 DeclarationIndexOutOfBounds,
39 ClassIndexOutOfBounds,
40 TextIndexOutOfBounds,
41 RunIndexOutOfBounds,
42 TextRunEmpty,
43 TextRunsUnordered,
44 TextRunsOverlap,
45 TextRunOutOfBounds,
46 TextRunSplitsScalar,
47 TextRunPropertyNotAllowed,
48 TextNotUtf8,
49 RelationsUnsorted,
50 RelationNodeOutOfBounds,
51 SolvedRootNotSolved,
52 SolvedRootNodeOutOfBounds,
53 SolvedRootsUnordered,
54 SolvedRectsOutOfBounds,
55 SolvedNodeWithoutRoot,
56 RetainedSolvedSubtree,
57 StaleAsset,
58 };
59
60 /// `Retained` describes the tree a publish is admitted against.
61 pub const Retained = struct {
62 /// `Retained.view` is that tree.
63 view: View = .{},
64 /// `Retained.map` is its identity map.
65 map: Map = .{},
66 /// `Retained.revision` is its header revision.
67 revision: u64 = 0,
68 /// `Retained.present` is false when no tree is retained, which is the default.
69 present: bool = false,
70 assets: ?*const asset.Registry = null,
71 };
72
73 /// `Spliced` counts what the splice adds beyond the publish's own tables when it
74 /// copies retained subtrees in.
75 /// `Spliced.nodes` and `Spliced.classes` are exact. The other counts are upper bounds,
76 /// because the survey counts absent atoms that the splice skips, shared atoms and texts
77 /// that the splice copies once, and the whole retained string table for every placeholder.
78 pub const Spliced = struct {
79 nodes: u64 = 0,
80 declarations: u64 = 0,
81 classes: u64 = 0,
82 texts: u64 = 0,
83 runs: u64 = 0,
84 atoms: u64 = 0,
85 strings: u64 = 0,
86 };
87
88 /// `Report` is what `survey` returns for an accepted publish.
89 pub const Report = struct {
90 /// `Report.view` is the bound publish.
91 view: View,
92 /// `Report.reuses_retained` is true when at least one node carries the `retained` flag.
93 reuses_retained: bool = false,
94 /// `Report.spliced` holds the counts described for `Spliced`.
95 spliced: Spliced = .{},
96 };
97
98 const Frame = struct {
99 node: u32,
100 last: u32,
101 };
102
103 /// `survey` is exported as `tree.admit`. It checks one publish buffer against `limits` and
104 /// `retained` and returns a `Report` or the first rejection. It checks the buffer size, the header,
105 /// and the spans, then the table quotas. `survey` checks the declaration table for asset handles
106 /// after quota checks and before it resets scratch or walks nodes. It rejects a stale generation
107 /// with `error.StaleAsset`. It then walks the node table once, then loops over the
108 /// atoms, the relations, and the solved roots. When a node reuses a retained subtree, it last
109 /// checks the quotas again with those subtrees counted. `survey` reads the buffer and writes only
110 /// `scratch`. `survey` calls `scratch.reset()` only after the size check, `bind`, and
111 /// `surveyQuotas` have passed, and the node walk then inserts one node at a time. A rejection
112 /// can leave `scratch` untouched, partly filled, or wholly filled, and only an accepted publish
113 /// leaves every node of the publish in it.
114 /// `scratch` needs a power-of-two slot count at least as large as the publish's node count.
115 pub fn survey(
116 bytes: []align(8) const u8,
117 limits: Limits,
118 retained: Retained,
119 scratch: *Map,
120 ) Error!Report {
121 if (bytes.len > limitsBytes(limits)) return error.PublishTooLarge;
122 const view = try view_mod.bind(bytes);
123 try surveyQuotas(view, limits);
124 try surveyAssets(view, retained.assets);
125 scratch.reset();
126 var report = Report{ .view = view };
127 const solved_nodes = try surveyNodes(view, retained, scratch, &report);
128 try surveyAtoms(view);
129 try surveyRelations(view);
130 try surveySolved(view, solved_nodes);
131 if (report.reuses_retained) try surveyMerge(view, limits, report);
132 return report;
133 }
134
135 fn surveyAssets(view: View, registry: ?*const asset.Registry) Error!void {
136 for (view.declarations) |declaration| {
137 if (declaration.kind != @backingInt(@import("css").value.Kind.asset)) continue;
138 const owner = registry orelse return error.StaleAsset;
139 const handle = abi.AssetHandle{ .index = declaration.a, .generation = declaration.b };
140 if (declaration.property == @backingInt(abi.PropertyId.font_family)) {
141 if (!owner.hasFont(handle)) return error.StaleAsset;
142 } else if (declaration.property == @backingInt(abi.PropertyId.background_image)) {
143 if (!owner.hasImage(handle)) return error.StaleAsset;
144 } else return error.StaleAsset;
145 }
146 }
147
148 fn limitsBytes(limits: Limits) u64 {
149 const derived = capacity.Capacity.derive(limits) catch return 0;
150 return derived.buffer_bytes;
151 }
152
153 fn surveyQuotas(view: View, limits: Limits) Error!void {
154 if (view.nodes.len > limits.nodes) return error.NodeLimitExceeded;
155 if (view.declarations.len > limits.declarations) return error.DeclarationLimitExceeded;
156 if (view.classes.len > limits.classes) return error.ClassLimitExceeded;
157 if (view.texts.len > limits.texts) return error.TextLimitExceeded;
158 if (view.runs.len > limits.runs) return error.RunLimitExceeded;
159 if (view.relations.len > limits.relations) return error.RelationLimitExceeded;
160 if (view.atoms.len > limits.atoms) return error.AtomLimitExceeded;
161 if (view.strings.len > limits.string_bytes) return error.StringLimitExceeded;
162 if (view.solved_roots.len > limits.solved_roots) return error.SolvedRootLimitExceeded;
163 if (view.solved_rects.len > limits.solved_rects) return error.SolvedRectLimitExceeded;
164 }
165
166 fn surveyNodes(view: View, retained: Retained, scratch: *Map, report: *Report) Error!u32 {
167 const count: u32 = @intCast(view.nodes.len);
168 if (count == 0) return 0;
169 if (view.nodes[0].parent != 0) return error.RootParentMismatch;
170 if (view.nodes[0].subtree_count != count - 1) return error.RootSubtreeIncomplete;
171 var stack: [arrange.max_depth]Frame = undefined;
172 var depth: u32 = 0;
173 var index: u32 = 0;
174 var solved_nodes: u32 = 0;
175 while (index < count) : (index += 1) {
176 const node = view.nodes[index];
177 solved_nodes += @intFromBool(abi.holds(node.flags, .solved));
178 if (@as(u64, index) + node.subtree_count >= count) return error.SubtreeExtentOutOfBounds;
179 while (depth > 0 and stack[depth - 1].last < index) depth -= 1;
180 if (index > 0) {
181 if (depth == 0) return error.ParentNotAncestor;
182 if (stack[depth - 1].node != node.parent) return error.ParentNotAncestor;
183 }
184 if (depth == arrange.max_depth) return error.DepthExceeded;
185 stack[depth] = .{ .node = index, .last = index + node.subtree_count };
186 depth += 1;
187 if (!scratch.insert(view.nodes, index)) return error.DuplicateNodeId;
188 try surveyReferences(view, node);
189 try surveyRetained(view, retained, node, report);
190 }
191 return solved_nodes;
192 }
193
194 fn surveyReferences(view: View, node: abi.Node) Error!void {
195 const atoms: u32 = @intCast(view.atoms.len);
196 if (node.identifier >= atoms and node.identifier != abi.atom_absent) {
197 return error.AtomIndexOutOfBounds;
198 }
199 if (node.name >= atoms and node.name != abi.atom_absent) return error.AtomIndexOutOfBounds;
200 if (node.action >= atoms and node.action != abi.atom_absent) return error.AtomIndexOutOfBounds;
201 const declarations = @as(u64, node.declaration_first) + node.declaration_count;
202 if (declarations > view.declarations.len) return error.DeclarationIndexOutOfBounds;
203 const classes = @as(u64, node.class_first) + node.class_count;
204 if (classes > view.classes.len) return error.ClassIndexOutOfBounds;
205 for (view.classes[node.class_first..][0..node.class_count]) |class| {
206 if (class >= atoms and class != abi.atom_absent) return error.AtomIndexOutOfBounds;
207 }
208 if (node.text != abi.text_absent) {
209 if (node.text >= view.texts.len) return error.TextIndexOutOfBounds;
210 try surveyText(view, view.texts[node.text]);
211 }
212 }
213
214 fn surveyText(view: View, record: abi.TextRecord) Error!void {
215 const atoms: u32 = @intCast(view.atoms.len);
216 if (record.content >= atoms and record.content != abi.atom_absent) {
217 return error.AtomIndexOutOfBounds;
218 }
219 const runs = @as(u64, record.run_first) + record.run_count;
220 if (runs > view.runs.len) return error.RunIndexOutOfBounds;
221 const content: []const u8 = if (record.content == abi.atom_absent) &.{} else blk: {
222 const atom = view.atoms[record.content];
223 if (@as(u64, atom.offset) + atom.len > view.strings.len) return error.AtomTextOutOfBounds;
224 break :blk view.strings[atom.offset..][0..atom.len];
225 };
226 if (!std.unicode.utf8ValidateSlice(content)) return error.TextNotUtf8;
227 var previous_start: u32 = 0;
228 var previous_end: u32 = 0;
229 for (view.runs[record.run_first..][0..record.run_count], 0..) |run, index| {
230 if (run.byte_start >= run.byte_end) return error.TextRunEmpty;
231 if (index > 0 and run.byte_start < previous_start) return error.TextRunsUnordered;
232 if (index > 0 and run.byte_start < previous_end) return error.TextRunsOverlap;
233 if (run.byte_end > content.len) return error.TextRunOutOfBounds;
234 if (isContinuation(content[run.byte_start]) or
235 (run.byte_end < content.len and isContinuation(content[run.byte_end])))
236 {
237 return error.TextRunSplitsScalar;
238 }
239 const declarations = @as(u64, run.declaration_first) + run.declaration_count;
240 if (declarations > view.declarations.len) return error.DeclarationIndexOutOfBounds;
241 for (view.declarations[run.declaration_first..][0..run.declaration_count]) |declaration| {
242 if (!spanPropertyAllowed(declaration.property)) return error.TextRunPropertyNotAllowed;
243 }
244 previous_start = run.byte_start;
245 previous_end = run.byte_end;
246 }
247 }
248
249 fn isContinuation(byte: u8) bool {
250 return byte & 0xc0 == 0x80;
251 }
252
253 fn spanPropertyAllowed(raw: u32) bool {
254 if (raw >= @import("css").property.count) return false;
255 const id: abi.PropertyId = @fromBackingInt(@intCast(raw));
256 return switch (id) {
257 .background_color,
258 .border_top_color,
259 .border_right_color,
260 .border_bottom_color,
261 .border_left_color,
262 .border_top_width,
263 .border_right_width,
264 .border_bottom_width,
265 .border_left_width,
266 .border_top_style,
267 .border_right_style,
268 .border_bottom_style,
269 .border_left_style,
270 .border_top_left_radius,
271 .border_top_right_radius,
272 .border_bottom_right_radius,
273 .border_bottom_left_radius,
274 .color,
275 .opacity,
276 .outline_color,
277 .outline_style,
278 .outline_width,
279 .outline_offset,
280 .font_family,
281 .font_size,
282 .font_style,
283 .font_weight,
284 .letter_spacing,
285 .line_height,
286 .word_spacing,
287 .text_decoration_color,
288 .text_decoration_line,
289 .text_decoration_style,
290 .text_decoration_thickness,
291 .text_transform,
292 .text_underline_offset,
293 .user_select,
294 => true,
295 else => false,
296 };
297 }
298
299 fn surveyRetained(view: View, retained: Retained, node: abi.Node, report: *Report) Error!void {
300 if (!abi.holds(node.flags, .retained)) return;
301 if (abi.holds(node.flags, .solved)) return error.RetainedSolvedSubtree;
302 if (node.subtree_count != 0) return error.RetainedSubtreeNotEmpty;
303 if (!retained.present) return error.StaleRetainedSubtree;
304 if (view.header.base_revision != retained.revision) return error.StaleRetainedSubtree;
305 const found = retained.map.lookup(retained.view.nodes, node.id) orelse
306 return error.StaleRetainedSubtree;
307 report.reuses_retained = true;
308 if (measure(retained.view, found, &report.spliced)) return error.RetainedSolvedSubtree;
309 }
310
311 fn measure(source: View, root: u32, spliced: *Spliced) bool {
312 const span = source.nodes[root].subtree_count + 1;
313 spliced.nodes += span - 1;
314 var contains_solved = false;
315 var offset: u32 = 0;
316 while (offset < span) : (offset += 1) {
317 const record = source.nodes[root + offset];
318 contains_solved = contains_solved or abi.holds(record.flags, .solved);
319 spliced.declarations += record.declaration_count;
320 spliced.classes += record.class_count;
321 spliced.atoms += @as(u64, record.class_count) + 3;
322 if (record.text == abi.text_absent) continue;
323 const text = source.texts[record.text];
324 spliced.texts += 1;
325 spliced.runs += text.run_count;
326 spliced.atoms += 1;
327 for (source.runs[text.run_first..][0..text.run_count]) |run| {
328 spliced.declarations += run.declaration_count;
329 }
330 }
331 spliced.strings += source.strings.len;
332 return contains_solved;
333 }
334
335 fn surveyAtoms(view: View) Error!void {
336 for (view.atoms) |atom| {
337 const end = @as(u64, atom.offset) + atom.len;
338 if (end > view.strings.len) return error.AtomTextOutOfBounds;
339 }
340 }
341
342 fn surveyRelations(view: View) Error!void {
343 var previous: u32 = 0;
344 for (view.relations, 0..) |relation, index| {
345 if (index > 0 and relation.subject < previous) return error.RelationsUnsorted;
346 if (relation.subject >= view.nodes.len) return error.RelationNodeOutOfBounds;
347 if (relation.object >= view.nodes.len) return error.RelationNodeOutOfBounds;
348 previous = relation.subject;
349 }
350 }
351
352 fn surveySolved(view: View, solved_nodes: u32) Error!void {
353 var reach: u64 = 0;
354 for (view.solved_roots, 0..) |root, index| {
355 if (root.node >= view.nodes.len) return error.SolvedRootNodeOutOfBounds;
356 if (!abi.holds(view.nodes[root.node].flags, .solved)) return error.SolvedRootNotSolved;
357 if (index > 0 and root.node < reach) return error.SolvedRootsUnordered;
358 const span = @as(u64, view.nodes[root.node].subtree_count) + 1;
359 if (@as(u64, root.rect_first) + span > view.solved_rects.len) {
360 return error.SolvedRectsOutOfBounds;
361 }
362 reach = @as(u64, root.node) + span;
363 }
364 if (solved_nodes != view.solved_roots.len) return error.SolvedNodeWithoutRoot;
365 }
366
367 fn surveyMerge(view: View, limits: Limits, report: Report) Error!void {
368 const spliced = report.spliced;
369 if (view.nodes.len + spliced.nodes > limits.nodes) return error.NodeLimitExceeded;
370 if (view.declarations.len + spliced.declarations > limits.declarations) {
371 return error.DeclarationLimitExceeded;
372 }
373 if (view.classes.len + spliced.classes > limits.classes) return error.ClassLimitExceeded;
374 if (view.texts.len + spliced.texts > limits.texts) return error.TextLimitExceeded;
375 if (view.runs.len + spliced.runs > limits.runs) return error.RunLimitExceeded;
376 if (view.atoms.len + spliced.atoms > limits.atoms) return error.AtomLimitExceeded;
377 if (view.strings.len + spliced.strings > limits.string_bytes) {
378 return error.StringLimitExceeded;
379 }
380 }
381
382 const fixture = @import("fixture/publish.zig");
383
384 const Block = struct {
385 storage: []align(8) u8,
386 bytes: []align(8) const u8,
387
388 fn header(self: Block) *abi.Header {
389 return @ptrCast(@alignCast(self.storage.ptr));
390 }
391
392 fn node(self: Block, index: u32) *abi.Node {
393 const offset = self.header().nodes.offset;
394 const base: [*]abi.Node = @ptrCast(@alignCast(self.storage.ptr + offset));
395 return &base[index];
396 }
397
398 fn free(self: Block) void {
399 std.testing.allocator.free(self.storage);
400 }
401 };
402
403 fn compose(plan: fixture.Plan) !Block {
404 const storage = try std.testing.allocator.alignedAlloc(u8, .fromByteUnits(8), 8192);
405 errdefer std.testing.allocator.free(storage);
406 const bytes = try fixture.build(std.testing.allocator, storage, plan);
407 return .{ .storage = storage, .bytes = bytes };
408 }
409
410 fn admit(block: Block, retained: Retained) Error!Report {
411 var slots: [256]u32 = @splat(0);
412 var scratch = Map{ .slots = &slots };
413 return survey(block.bytes, .{}, retained, &scratch);
414 }
415
416 fn reject(plan: fixture.Plan, expected: anyerror) !void {
417 const block = try compose(plan);
418 defer block.free();
419 try std.testing.expectError(expected, admit(block, .{}));
420 }
421
422 const leaf = fixture.Spec{ .id = 1, .revision = 7 };
423
424 const pair = [_]fixture.Spec{
425 .{ .id = 1, .revision = 7, .subtree_count = 1 },
426 .{ .id = 2, .revision = 8, .parent = 0 },
427 };
428
429 test "a well formed publish is admitted with its view bound" {
430 const block = try compose(.{ .specs = &pair });
431 defer block.free();
432 const report = try admit(block, .{});
433 try std.testing.expectEqual(@as(usize, 2), report.view.nodes.len);
434 try std.testing.expect(!report.reuses_retained);
435 try std.testing.expectEqual(@as(u64, 1), report.view.header.revision);
436 }
437
438 test "a buffer whose length the header misstates is refused" {
439 const block = try compose(.{ .specs = &.{leaf} });
440 defer block.free();
441 block.header().buffer_bytes += 8;
442 try std.testing.expectError(error.BufferLengthMismatch, admit(block, .{}));
443 }
444
445 test "a publish whose magic word is wrong is refused" {
446 const block = try compose(.{ .specs = &.{leaf} });
447 defer block.free();
448 block.header().magic = 0x31_49_55_55;
449 try std.testing.expectError(error.MagicMismatch, admit(block, .{}));
450 }
451
452 test "a publish from another abi version is refused" {
453 const block = try compose(.{ .specs = &.{leaf} });
454 defer block.free();
455 block.header().abi_version = abi.abi_version + 1;
456 try std.testing.expectError(error.AbiVersionMismatch, admit(block, .{}));
457 }
458
459 test "a publish whose node size differs from this build is refused" {
460 const block = try compose(.{ .specs = &.{leaf} });
461 defer block.free();
462 block.header().node_bytes = 56;
463 try std.testing.expectError(error.NodeSizeMismatch, admit(block, .{}));
464 }
465
466 test "a span reaching past the buffer is refused" {
467 const block = try compose(.{ .specs = &pair });
468 defer block.free();
469 block.header().nodes.count = 64;
470 try std.testing.expectError(error.SpanOutOfBounds, admit(block, .{}));
471 }
472
473 test "a subtree extent past the node count is refused" {
474 const block = try compose(.{ .specs = &pair });
475 defer block.free();
476 block.node(1).subtree_count = 4;
477 try std.testing.expectError(error.SubtreeExtentOutOfBounds, admit(block, .{}));
478 }
479
480 test "a descendant whose parent is outside the enclosing subtree is refused" {
481 const specs = [_]fixture.Spec{
482 .{ .id = 1, .subtree_count = 3 },
483 .{ .id = 2, .parent = 0, .subtree_count = 2 },
484 .{ .id = 3, .parent = 1 },
485 .{ .id = 4, .parent = 0 },
486 };
487 try reject(.{ .specs = &specs }, error.ParentNotAncestor);
488 }
489
490 test "a root that does not store its own index is refused" {
491 const block = try compose(.{ .specs = &pair });
492 defer block.free();
493 block.node(0).parent = 1;
494 try std.testing.expectError(error.RootParentMismatch, admit(block, .{}));
495 }
496
497 test "a root whose subtree does not cover the array is refused" {
498 const block = try compose(.{ .specs = &pair });
499 defer block.free();
500 block.node(0).subtree_count = 0;
501 try std.testing.expectError(error.RootSubtreeIncomplete, admit(block, .{}));
502 }
503
504 test "a tree deeper than the layout bound is refused" {
505 const deep = try fixture.chain(std.testing.allocator, arrange.max_depth + 1);
506 defer std.testing.allocator.free(deep);
507 try reject(.{ .specs = deep }, error.DepthExceeded);
508 }
509
510 test "a tree at exactly the layout bound is admitted" {
511 const deep = try fixture.chain(std.testing.allocator, arrange.max_depth);
512 defer std.testing.allocator.free(deep);
513 const block = try compose(.{ .specs = deep });
514 defer block.free();
515 const report = try admit(block, .{});
516 try std.testing.expectEqual(arrange.max_depth, report.view.nodes.len);
517 }
518
519 test "a repeated node id inside one publish is refused" {
520 const specs = [_]fixture.Spec{
521 .{ .id = 9, .subtree_count = 1 },
522 .{ .id = 9, .parent = 0 },
523 };
524 try reject(.{ .specs = &specs }, error.DuplicateNodeId);
525 }
526
527 test "an atom index past the atom table is refused" {
528 const block = try compose(.{ .specs = &pair });
529 defer block.free();
530 block.node(1).name = 64;
531 try std.testing.expectError(error.AtomIndexOutOfBounds, admit(block, .{}));
532 }
533
534 test "an atom whose text leaves the string span is refused" {
535 const specs = [_]fixture.Spec{.{ .id = 1, .name = "save" }};
536 const block = try compose(.{ .specs = &specs });
537 defer block.free();
538 const atom_offset = block.header().atoms.offset;
539 const atoms: [*]abi.Atom = @ptrCast(@alignCast(block.storage.ptr + atom_offset));
540 atoms[1].len = 99;
541 try std.testing.expectError(error.AtomTextOutOfBounds, admit(block, .{}));
542 }
543
544 test "a declaration span past the declaration table is refused" {
545 const block = try compose(.{ .specs = &pair });
546 defer block.free();
547 block.node(1).declaration_count = 3;
548 try std.testing.expectError(error.DeclarationIndexOutOfBounds, admit(block, .{}));
549 }
550
551 test "a class span past the class table is refused" {
552 const block = try compose(.{ .specs = &pair });
553 defer block.free();
554 block.node(1).class_count = 5;
555 try std.testing.expectError(error.ClassIndexOutOfBounds, admit(block, .{}));
556 }
557
558 test "a text index past the text table is refused" {
559 const block = try compose(.{ .specs = &pair });
560 defer block.free();
561 block.node(1).text = 12;
562 try std.testing.expectError(error.TextIndexOutOfBounds, admit(block, .{}));
563 }
564
565 test "a run span past the run table is refused" {
566 const specs = [_]fixture.Spec{.{ .id = 1, .text = "hello" }};
567 const block = try compose(.{ .specs = &specs });
568 defer block.free();
569 const text_offset = block.header().texts.offset;
570 const texts: [*]abi.TextRecord = @ptrCast(@alignCast(block.storage.ptr + text_offset));
571 texts[1].run_count = 6;
572 try std.testing.expectError(error.RunIndexOutOfBounds, admit(block, .{}));
573 }
574
575 test "text runs reject empty, reversed, overlapping, and out of bounds ranges by name" {
576 const cases = [_]struct { runs: []const abi.TextRun, expected: anyerror }{
577 .{ .runs = &.{.{ .byte_start = 2, .byte_end = 2 }}, .expected = error.TextRunEmpty },
578 .{ .runs = &.{ .{ .byte_start = 2, .byte_end = 3 }, .{ .byte_start = 0, .byte_end = 1 } }, .expected = error.TextRunsUnordered },
579 .{ .runs = &.{ .{ .byte_start = 0, .byte_end = 2 }, .{ .byte_start = 1, .byte_end = 3 } }, .expected = error.TextRunsOverlap },
580 .{ .runs = &.{.{ .byte_start = 0, .byte_end = 4 }}, .expected = error.TextRunOutOfBounds },
581 };
582 for (cases) |case| {
583 try reject(.{ .specs = &.{.{ .id = 1, .text = "abc", .runs = case.runs }} }, case.expected);
584 }
585 }
586
587 test "text run endpoints must be UTF-8 scalar boundaries" {
588 try reject(.{ .specs = &.{.{ .id = 1, .text = "aéz", .runs = &.{.{ .byte_start = 2, .byte_end = 4 }} }} }, error.TextRunSplitsScalar);
589 try reject(.{ .specs = &.{.{ .id = 1, .text = "aéz", .runs = &.{.{ .byte_start = 0, .byte_end = 2 }} }} }, error.TextRunSplitsScalar);
590 }
591
592 test "malformed text content is refused before run processing" {
593 const cases = [_][]const u8{
594 &.{ 0xc0, 0xaf },
595 &.{0x80},
596 &.{ 0xe2, 0x82 },
597 };
598 for (cases) |bytes| {
599 try reject(.{ .specs = &.{.{ .id = 1, .text = bytes }} }, error.TextNotUtf8);
600 }
601 }
602
603 test "text runs admit gaps and full cover, including a grapheme-internal boundary" {
604 const cases = [_][]const abi.TextRun{
605 &.{ .{ .byte_start = 0, .byte_end = 1 }, .{ .byte_start = 3, .byte_end = 4 } },
606 &.{.{ .byte_start = 0, .byte_end = 4 }},
607 &.{ .{ .byte_start = 0, .byte_end = 1 }, .{ .byte_start = 1, .byte_end = 4 } },
608 };
609 for (cases) |runs| {
610 const block = try compose(.{ .specs = &.{.{ .id = 1, .text = "e\u{301}z", .runs = runs }} });
611 defer block.free();
612 _ = try admit(block, .{});
613 }
614 }
615
616 test "paragraph and layout declarations on text runs are refused" {
617 const properties = [_]abi.PropertyId{ .text_align, .text_indent, .white_space, .word_break, .overflow_wrap, .display };
618 for (properties) |property| {
619 const declarations = [_]abi.Declaration{.{
620 .property = @backingInt(property),
621 .kind = 0,
622 .unit = 0,
623 .flags = 0,
624 .a = 0,
625 .b = 0,
626 }};
627 try reject(.{ .specs = &.{.{
628 .id = 1,
629 .text = "a",
630 .declarations = &declarations,
631 .runs = &.{.{ .byte_end = 1, .declaration_count = 1 }},
632 }} }, error.TextRunPropertyNotAllowed);
633 }
634 }
635
636 test "paint and text style declarations on text runs are admitted" {
637 const properties = [_]abi.PropertyId{ .color, .background_color, .font_family, .font_size, .line_height, .text_decoration_color };
638 for (properties) |property| {
639 const declarations = [_]abi.Declaration{.{
640 .property = @backingInt(property),
641 .kind = 0,
642 .unit = 0,
643 .flags = 0,
644 .a = 0,
645 .b = 0,
646 }};
647 const block = try compose(.{ .specs = &.{.{
648 .id = 1,
649 .text = "a",
650 .declarations = &declarations,
651 .runs = &.{.{ .byte_end = 1, .declaration_count = 1 }},
652 }} });
653 defer block.free();
654 _ = try admit(block, .{});
655 }
656 }
657
658 test "a relation table out of subject order is refused" {
659 const relations = [_]abi.Relation{
660 .{ .subject = 1, .object = 0 },
661 .{ .subject = 0, .object = 1 },
662 };
663 try reject(.{ .specs = &pair, .relations = &relations }, error.RelationsUnsorted);
664 }
665
666 test "a relation naming a node outside the tree is refused" {
667 const relations = [_]abi.Relation{.{ .subject = 0, .object = 7 }};
668 try reject(.{ .specs = &pair, .relations = &relations }, error.RelationNodeOutOfBounds);
669 }
670
671 test "a solved root on a node without the solved flag is refused" {
672 const roots = [_]abi.SolvedRoot{.{ .node = 1, .rect_first = 0 }};
673 const rects = [_]abi.Rect{.{}};
674 try reject(
675 .{ .specs = &pair, .solved_roots = &roots, .solved_rects = &rects },
676 error.SolvedRootNotSolved,
677 );
678 }
679
680 test "a solved root at the node bound is refused" {
681 const specs = [_]fixture.Spec{.{ .id = 1, .flags = abi.flag(.solved) }};
682 const roots = [_]abi.SolvedRoot{.{ .node = 1, .rect_first = 0 }};
683 const rects = [_]abi.Rect{.{}};
684 try reject(
685 .{ .specs = &specs, .solved_roots = &roots, .solved_rects = &rects },
686 error.SolvedRootNodeOutOfBounds,
687 );
688 }
689
690 test "solved roots that overlap or run backwards are refused" {
691 const specs = [_]fixture.Spec{
692 .{ .id = 1, .subtree_count = 2, .flags = abi.flag(.solved) },
693 .{ .id = 2, .parent = 0, .subtree_count = 1, .flags = abi.flag(.solved) },
694 .{ .id = 3, .parent = 1 },
695 };
696 const roots = [_]abi.SolvedRoot{
697 .{ .node = 0, .rect_first = 0 },
698 .{ .node = 1, .rect_first = 3 },
699 };
700 const rects = [_]abi.Rect{ .{}, .{}, .{}, .{}, .{} };
701 try reject(
702 .{ .specs = &specs, .solved_roots = &roots, .solved_rects = &rects },
703 error.SolvedRootsUnordered,
704 );
705 }
706
707 test "a solved root whose rects leave the rect table is refused" {
708 const specs = [_]fixture.Spec{.{ .id = 1, .flags = abi.flag(.solved) }};
709 const roots = [_]abi.SolvedRoot{.{ .node = 0, .rect_first = 1 }};
710 const rects = [_]abi.Rect{.{}};
711 try reject(
712 .{ .specs = &specs, .solved_roots = &roots, .solved_rects = &rects },
713 error.SolvedRectsOutOfBounds,
714 );
715 }
716
717 test "a solved node without a root record is refused" {
718 const specs = [_]fixture.Spec{.{ .id = 1, .flags = abi.flag(.solved) }};
719 try reject(.{ .specs = &specs }, error.SolvedNodeWithoutRoot);
720 }
721
722 test "one root per solved node is admitted" {
723 const specs = [_]fixture.Spec{
724 .{ .id = 1, .subtree_count = 2 },
725 .{ .id = 2, .parent = 0, .flags = abi.flag(.solved) },
726 .{ .id = 3, .parent = 0, .flags = abi.flag(.solved) },
727 };
728 const roots = [_]abi.SolvedRoot{
729 .{ .node = 1, .rect_first = 0 },
730 .{ .node = 2, .rect_first = 1 },
731 };
732 const rects = [_]abi.Rect{ .{}, .{} };
733 const block = try compose(.{
734 .specs = &specs,
735 .solved_roots = &roots,
736 .solved_rects = &rects,
737 });
738 defer block.free();
739 const report = try admit(block, .{});
740 try std.testing.expectEqual(@as(usize, 2), report.view.solved_roots.len);
741 }
742
743 test "a publish larger than the declared buffer is refused before it is bound" {
744 const block = try compose(.{ .specs = &.{leaf} });
745 defer block.free();
746 var slots: [4]u32 = @splat(0);
747 var scratch = Map{ .slots = &slots };
748 const empty = Limits{
749 .nodes = 0,
750 .declarations = 0,
751 .classes = 0,
752 .texts = 0,
753 .runs = 0,
754 .relations = 0,
755 .atoms = 0,
756 .string_bytes = 0,
757 .solved_roots = 0,
758 .solved_rects = 0,
759 .map_slots = 2,
760 };
761 try std.testing.expect(block.bytes.len > abi.header_bytes);
762 try std.testing.expectError(error.PublishTooLarge, survey(block.bytes, empty, .{}, &scratch));
763 }
764
765 test "a publish over a declared span quota is refused" {
766 const block = try compose(.{ .specs = &pair });
767 defer block.free();
768 var slots: [8]u32 = @splat(0);
769 var scratch = Map{ .slots = &slots };
770 const one = Limits{ .nodes = 1, .map_slots = 2 };
771 try std.testing.expectError(
772 error.NodeLimitExceeded,
773 survey(block.bytes, one, .{}, &scratch),
774 );
775 }
776
777 fn retain(block: Block, slots: []u32) !Retained {
778 const view = try view_mod.bind(block.bytes);
779 var map = Map{ .slots = slots };
780 map.reset();
781 var index: u32 = 0;
782 while (index < view.nodes.len) : (index += 1) {
783 const inserted = map.insert(view.nodes, index);
784 std.debug.assert(inserted);
785 }
786 return .{ .view = view, .map = map, .revision = view.header.revision, .present = true };
787 }
788
789 test "a buffer too short to hold a header is refused" {
790 const storage = try std.testing.allocator.alignedAlloc(u8, .fromByteUnits(8), 64);
791 defer std.testing.allocator.free(storage);
792 var slots: [4]u32 = @splat(0);
793 var scratch = Map{ .slots = &slots };
794 try std.testing.expectError(error.BufferTooSmall, survey(storage, .{}, .{}, &scratch));
795 }
796
797 test "a span whose offset breaks its element alignment is refused" {
798 const block = try compose(.{ .specs = &pair });
799 defer block.free();
800 block.header().nodes.offset += 4;
801 try std.testing.expectError(error.SpanMisaligned, admit(block, .{}));
802 }
803
804 test "every declared span quota rejects with the error that names it" {
805 const cases = [_]struct { field: []const u8, expected: anyerror }{
806 .{ .field = "nodes", .expected = error.NodeLimitExceeded },
807 .{ .field = "declarations", .expected = error.DeclarationLimitExceeded },
808 .{ .field = "classes", .expected = error.ClassLimitExceeded },
809 .{ .field = "texts", .expected = error.TextLimitExceeded },
810 .{ .field = "runs", .expected = error.RunLimitExceeded },
811 .{ .field = "relations", .expected = error.RelationLimitExceeded },
812 .{ .field = "atoms", .expected = error.AtomLimitExceeded },
813 .{ .field = "string_bytes", .expected = error.StringLimitExceeded },
814 .{ .field = "solved_roots", .expected = error.SolvedRootLimitExceeded },
815 .{ .field = "solved_rects", .expected = error.SolvedRectLimitExceeded },
816 };
817 try std.testing.expectEqual(capacity.array_count, cases.len);
818 const styled = [_]abi.Declaration{.{
819 .property = @backingInt(abi.PropertyId.display),
820 .kind = 0,
821 .unit = 0,
822 .flags = 0,
823 .a = 0,
824 .b = 0,
825 }};
826 const specs = [_]fixture.Spec{.{
827 .id = 1,
828 .name = "row",
829 .text = "hi",
830 .classes = &.{"pane"},
831 .declarations = &styled,
832 .flags = abi.flag(.solved),
833 }};
834 const relations = [_]abi.Relation{.{ .subject = 0, .object = 0 }};
835 const roots = [_]abi.SolvedRoot{.{ .node = 0, .rect_first = 0 }};
836 const rects = [_]abi.Rect{.{}};
837 const block = try compose(.{
838 .specs = &specs,
839 .relations = &relations,
840 .solved_roots = &roots,
841 .solved_rects = &rects,
842 });
843 defer block.free();
844 var slots: [8]u32 = @splat(0);
845 var scratch = Map{ .slots = &slots };
846 inline for (cases) |case| {
847 var limits = Limits{};
848 @field(limits, case.field) = 0;
849 try std.testing.expectError(case.expected, survey(block.bytes, limits, .{}, &scratch));
850 }
851 }
852
853 test "a retained node whose id the retained tree never held is refused" {
854 const base = try compose(.{ .specs = &.{leaf} });
855 defer base.free();
856 var slots: [16]u32 = @splat(0);
857 const held = try retain(base, &slots);
858 const specs = [_]fixture.Spec{.{ .id = 4, .flags = abi.flag(.retained) }};
859 const next = try compose(.{ .specs = &specs, .base_revision = 1 });
860 defer next.free();
861 try std.testing.expectError(error.StaleRetainedSubtree, admit(next, held));
862 }
863
864 test "a retained node published against another generation is refused" {
865 const base = try compose(.{ .specs = &.{leaf} });
866 defer base.free();
867 var slots: [16]u32 = @splat(0);
868 const held = try retain(base, &slots);
869 const specs = [_]fixture.Spec{.{ .id = 1, .flags = abi.flag(.retained) }};
870 const next = try compose(.{ .revision = 2, .base_revision = 9, .specs = &specs });
871 defer next.free();
872 try std.testing.expectError(error.StaleRetainedSubtree, admit(next, held));
873 }
874
875 test "a retained node that carries its own children is refused" {
876 const base = try compose(.{ .specs = &.{leaf} });
877 defer base.free();
878 var slots: [16]u32 = @splat(0);
879 const held = try retain(base, &slots);
880 const specs = [_]fixture.Spec{
881 .{ .id = 1, .subtree_count = 1, .flags = abi.flag(.retained) },
882 .{ .id = 2, .parent = 0 },
883 };
884 const next = try compose(.{ .revision = 2, .base_revision = 1, .specs = &specs });
885 defer next.free();
886 try std.testing.expectError(error.RetainedSubtreeNotEmpty, admit(next, held));
887 }
888
889 test "a retained node naming a held subtree is admitted and prices that subtree" {
890 const base = try compose(.{ .specs = &pair });
891 defer base.free();
892 var slots: [16]u32 = @splat(0);
893 const held = try retain(base, &slots);
894 const specs = [_]fixture.Spec{
895 .{ .id = 5, .subtree_count = 1 },
896 .{ .id = 1, .parent = 0, .flags = abi.flag(.retained) },
897 };
898 const next = try compose(.{ .revision = 2, .base_revision = 1, .specs = &specs });
899 defer next.free();
900 const report = try admit(next, held);
901 try std.testing.expect(report.reuses_retained);
902 try std.testing.expectEqual(@as(u64, 1), report.spliced.nodes);
903 try std.testing.expectEqual(@as(u64, 3), report.view.nodes.len + report.spliced.nodes);
904 }
905
906 test "a retained solved subtree is refused before splice drops its rectangles" {
907 const solved = [_]fixture.Spec{.{ .id = 1, .flags = abi.flag(.solved) }};
908 const roots = [_]abi.SolvedRoot{.{ .node = 0, .rect_first = 0 }};
909 const rects = [_]abi.Rect{.{ .width = 7, .height = 5 }};
910 const base = try compose(.{
911 .specs = &solved,
912 .solved_roots = &roots,
913 .solved_rects = &rects,
914 });
915 defer base.free();
916 var slots: [16]u32 = @splat(0);
917 const held = try retain(base, &slots);
918 const specs = [_]fixture.Spec{.{ .id = 1, .flags = abi.flag(.retained) }};
919 const next = try compose(.{ .revision = 2, .base_revision = 1, .specs = &specs });
920 defer next.free();
921 try std.testing.expectError(error.RetainedSolvedSubtree, admit(next, held));
922 }
923
924 test "a retained subtree with a solved descendant is refused" {
925 const prior = [_]fixture.Spec{
926 .{ .id = 1, .subtree_count = 1 },
927 .{ .id = 2, .parent = 0, .flags = abi.flag(.solved) },
928 };
929 const roots = [_]abi.SolvedRoot{.{ .node = 1, .rect_first = 0 }};
930 const rects = [_]abi.Rect{.{ .width = 7, .height = 5 }};
931 const base = try compose(.{
932 .specs = &prior,
933 .solved_roots = &roots,
934 .solved_rects = &rects,
935 });
936 defer base.free();
937 var slots: [16]u32 = @splat(0);
938 const held = try retain(base, &slots);
939 const specs = [_]fixture.Spec{.{ .id = 1, .flags = abi.flag(.retained) }};
940 const next = try compose(.{ .revision = 2, .base_revision = 1, .specs = &specs });
941 defer next.free();
942 try std.testing.expectError(error.RetainedSolvedSubtree, admit(next, held));
943 }
944
945 test "a retained placeholder cannot introduce a solved root" {
946 const base = try compose(.{ .specs = &.{leaf} });
947 defer base.free();
948 var slots: [16]u32 = @splat(0);
949 const held = try retain(base, &slots);
950 const specs = [_]fixture.Spec{.{
951 .id = leaf.id,
952 .flags = abi.flag(.retained) | abi.flag(.solved),
953 }};
954 const roots = [_]abi.SolvedRoot{.{ .node = 0, .rect_first = 0 }};
955 const rects = [_]abi.Rect{.{ .width = 7, .height = 5 }};
956 const next = try compose(.{
957 .revision = 2,
958 .base_revision = 1,
959 .specs = &specs,
960 .solved_roots = &roots,
961 .solved_rects = &rects,
962 });
963 defer next.free();
964 try std.testing.expectError(error.RetainedSolvedSubtree, admit(next, held));
965 }