lib/css/src/bucket.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! The rule bucket index: one sorted entry per selector, keyed by the strongest
2 //! key its rightmost compound carries.
3 //!
4 //! Matching an element against a whole sheet is a walk over every selector only
5 //! if nothing narrows the candidates first. A selector whose rightmost compound
6 //! names an id, a class, a role, or an element type can only match an element
7 //! carrying that key, so the index groups selectors by key and an element tests
8 //! its own keys plus the universal group. The groups are one sorted array with
9 //! a binary search, so the index is a flat block with no pointers.
10 //!
11 //! The index also answers the question a style sharing cache asks before it
12 //! reuses a computed style: whether a mutation somewhere above or beside an
13 //! element can change what matches. `Summary` holds conservative Bloom words
14 //! over the atoms that appear left of a combinator, plus the two bits that
15 //! say a sheet uses sibling combinators or positional pseudo-classes at all.
16 //! `Summary` also holds `ancestor_pseudo`, an exact `u32` bitset over the
17 //! thirty `PseudoClass` values rather than a Bloom word. A set bit names a
18 //! pseudo-class some selector puts left of a combinator, and a clear bit
19 //! rules that pseudo-class out.
20
21 const std = @import("std");
22 const alloc_phase = @import("alloc_phase");
23
24 const atom = @import("atom.zig");
25 const match = @import("match/root.zig");
26 const selector = @import("selector/root.zig");
27 const sheet = @import("sheet.zig");
28
29 const Allocator = std.mem.Allocator;
30
31 /// The key spaces a bucket entry lives in, in the order the index sorts them.
32 pub const Space = enum(u8) {
33 universal = 0,
34 kind = 1,
35 role = 2,
36 class = 3,
37 identifier = 4,
38 };
39
40 /// One selector's place in the index.
41 pub const Entry = extern struct {
42 key: u32 = 0,
43 rule: u32 = 0,
44 selector: u32 = 0,
45 space: u8 = @backingInt(Space.universal),
46
47 fn before(left: Entry, right: Entry) bool {
48 if (left.space != right.space) return left.space < right.space;
49 if (left.key != right.key) return left.key < right.key;
50 if (left.rule != right.rule) return left.rule < right.rule;
51 return left.selector < right.selector;
52 }
53 };
54
55 /// The bound one sheet produces, which is its selector count.
56 pub const Limits = struct {
57 entries: usize = 0,
58
59 /// Counts the entries `parsed` needs without writing one.
60 pub fn inspect(parsed: *const sheet.StyleSheet) Limits {
61 var total: usize = 0;
62 for (parsed.rules) |rule| total += rule.selectors.len;
63 return .{ .entries = total };
64 }
65
66 pub fn grow(left: Limits, right: Limits) Limits {
67 return .{ .entries = @max(left.entries, right.entries) };
68 }
69 };
70
71 /// The byte layout one `Limits` produces.
72 pub const Capacity = struct {
73 entries: usize = 0,
74 total_bytes: usize = 0,
75
76 pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {
77 const bytes = std.math.mul(usize, limits.entries, @sizeOf(Entry)) catch
78 return error.CapacityOverflow;
79 return .{ .entries = limits.entries, .total_bytes = bytes };
80 }
81 };
82
83 const LimitsType = Limits;
84 const CapacityType = Capacity;
85
86 /// The alignment the index block is acquired at.
87 pub const storage_alignment: usize = @alignOf(Entry);
88
89 /// The sorted entries plus the sheet arrays a match walk reads.
90 pub const Index = struct {
91 entries: []const Entry = &.{},
92 source: *const sheet.StyleSheet,
93
94 /// The entries in one key space, or an empty slice when the sheet has none.
95 pub fn group(self: Index, space: Space, key: u32) []const Entry {
96 const wanted = Entry{ .space = @backingInt(space), .key = key };
97 var low: usize = 0;
98 var high: usize = self.entries.len;
99 while (low < high) {
100 const middle = low + (high - low) / 2;
101 if (Entry.before(self.entries[middle], wanted)) low = middle + 1 else high = middle;
102 }
103 var end = low;
104 while (end < self.entries.len and
105 self.entries[end].space == wanted.space and
106 self.entries[end].key == key) : (end += 1)
107 {}
108 return self.entries[low..end];
109 }
110
111 fn selectorAt(self: Index, entry: Entry) selector.Selector {
112 const rule = self.source.rules[entry.rule];
113 return rule.selectors[entry.selector];
114 }
115 };
116
117 /// The outcome of one element's candidate walk.
118 pub const Gather = struct {
119 count: u32 = 0,
120 rejected: u32 = 0,
121 };
122
123 /// The most classes one element carries into a candidate walk.
124 pub const max_element_classes: u32 = match.max_element_classes;
125
126 /// Writes every selector in `index` that matches `node` into `out`, ordered by
127 /// source order and then specificity. Candidates past `out` are rejected and
128 /// counted rather than dropped silently.
129 pub fn matchElement(
130 index: Index,
131 element: match.Element,
132 node: u32,
133 out: []match.Match,
134 ) Gather {
135 var found = Gather{};
136 const context = index.source.context();
137 collect(index, context, element, node, out, &found, .universal, 0);
138 const kind = element.kind(element.context, node);
139 if (kind != 0) collect(index, context, element, node, out, &found, .kind, kind);
140 const role = element.role(element.context, node);
141 if (role != 0) collect(index, context, element, node, out, &found, .role, role);
142 const identifier = element.identifier(element.context, node);
143 if (identifier != atom.none) collect(index, context, element, node, out, &found, .identifier, identifier);
144 var held: [max_element_classes]u32 = undefined;
145 const classes = element.classes(element.context, node, &held, max_element_classes);
146 std.debug.assert(classes <= max_element_classes);
147 for (held[0..classes]) |class| {
148 collect(index, context, element, node, out, &found, .class, class);
149 }
150 std.mem.sort(match.Match, out[0..found.count], {}, earlier);
151 return found;
152 }
153
154 fn collect(
155 index: Index,
156 context: match.Context,
157 element: match.Element,
158 node: u32,
159 out: []match.Match,
160 found: *Gather,
161 space: Space,
162 key: u32,
163 ) void {
164 for (index.group(space, key)) |entry| {
165 const item = index.selectorAt(entry);
166 if (!match.matches(context, item, element, node)) continue;
167 if (found.count == out.len) {
168 found.rejected += 1;
169 continue;
170 }
171 out[found.count] = .{
172 .rule = entry.rule,
173 .selector = entry.selector,
174 .specificity = item.specificity,
175 .order = @intCast(index.source.rules[entry.rule].source_order),
176 };
177 found.count += 1;
178 }
179 }
180
181 fn earlier(_: void, left: match.Match, right: match.Match) bool {
182 if (left.order != right.order) return left.order < right.order;
183 return left.specificity.compare(right.specificity) == .lt;
184 }
185
186 fn keyOf(item: selector.Selector) Entry {
187 return switch (item.bucket) {
188 .universal => .{ .space = @backingInt(Space.universal), .key = 0 },
189 .kind => |key| .{ .space = @backingInt(Space.kind), .key = key },
190 .role => |key| .{ .space = @backingInt(Space.role), .key = key },
191 .class => |key| .{ .space = @backingInt(Space.class), .key = key },
192 .id => |key| .{ .space = @backingInt(Space.identifier), .key = key },
193 };
194 }
195
196 /// Fills `entries` from `parsed` and returns the sorted index.
197 pub fn build(entries: []Entry, parsed: *const sheet.StyleSheet) Index {
198 var used: usize = 0;
199 for (parsed.rules, 0..) |rule, rule_index| {
200 for (rule.selectors, 0..) |item, selector_index| {
201 std.debug.assert(used < entries.len);
202 var entry = keyOf(item);
203 entry.rule = @intCast(rule_index);
204 entry.selector = @intCast(selector_index);
205 entries[used] = entry;
206 used += 1;
207 }
208 }
209 std.mem.sort(Entry, entries[0..used], {}, lessThan);
210 return .{ .entries = entries[0..used], .source = parsed };
211 }
212
213 fn lessThan(_: void, left: Entry, right: Entry) bool {
214 return Entry.before(left, right);
215 }
216
217 /// What a mutation must carry before it can change what a sheet matches.
218 ///
219 /// The Bloom words are conservative: a set bit means some selector names an
220 /// atom that folds onto that bit left of a combinator, so a consumer that sees
221 /// a clear bit knows no ancestor change with that atom can matter.
222 pub const Summary = struct {
223 ancestor_kinds: u64 = 0,
224 ancestor_roles: u64 = 0,
225 ancestor_classes: u64 = 0,
226 ancestor_ids: u64 = 0,
227 /// A set bit means some selector names that pseudo-class left of a
228 /// combinator, and a clear bit means no selector does. The word is an exact
229 /// set rather than a conservative Bloom word, unlike the Bloom words above
230 /// this field.
231 ancestor_pseudo: u32 = 0,
232 sibling_sensitive: bool = false,
233 positional: bool = false,
234
235 /// Whether an ancestor carrying `id` in `space` can change matching.
236 pub fn ancestorSensitive(self: Summary, space: Space, id: u32) bool {
237 const word = switch (space) {
238 .universal => return true,
239 .kind => self.ancestor_kinds,
240 .role => self.ancestor_roles,
241 .class => self.ancestor_classes,
242 .identifier => self.ancestor_ids,
243 };
244 return word & bit(id) != 0;
245 }
246
247 /// This predicate returns whether ancestor_pseudo carries
248 /// selector.bit(class). The check answers whether any rule in the sheet
249 /// puts the given pseudo-class above a subject, such as :hover in
250 /// .row:hover .cell. The alternative is rescanning every selector in the
251 /// stylesheet.
252 pub fn ancestorPseudoSensitive(self: Summary, class: selector.PseudoClass) bool {
253 const word = selector.bit(class);
254 std.debug.assert(word != 0);
255 return self.ancestor_pseudo & word != 0;
256 }
257 };
258
259 fn bit(id: u32) u64 {
260 return @as(u64, 1) << @truncate(id);
261 }
262
263 /// Folds every selector in `parsed` into one conservative summary.
264 pub fn summarize(parsed: *const sheet.StyleSheet) Summary {
265 var out = Summary{};
266 for (parsed.rules) |rule| {
267 for (rule.selectors) |item| {
268 for (item.combinators) |joint| {
269 if (joint == .next_sibling or joint == .subsequent_sibling) out.sibling_sensitive = true;
270 }
271 for (item.compounds, 0..) |compound, position| {
272 if (compound.nth != 0) out.positional = true;
273 if (position + 1 == item.compounds.len) continue;
274 absorb(&out, parsed, compound);
275 }
276 }
277 }
278 return out;
279 }
280
281 fn absorb(out: *Summary, parsed: *const sheet.StyleSheet, compound: selector.Compound) void {
282 out.ancestor_pseudo |= compound.pseudo;
283 if (compound.kind != 0) out.ancestor_kinds |= bit(compound.kind);
284 if (compound.role != 0) out.ancestor_roles |= bit(compound.role);
285 if (compound.id != atom.none) out.ancestor_ids |= bit(compound.id);
286 var index: u32 = 0;
287 while (index < compound.class_count) : (index += 1) {
288 out.ancestor_classes |= bit(parsed.classes[compound.class_first + index]);
289 }
290 }
291
292 /// The single aligned block one bucket index owns.
293 pub const Storage = struct {
294 pub const Limits = LimitsType;
295 pub const Capacity = CapacityType;
296
297 pub const claim: alloc_phase.capacity.Declaration = .{
298 .source = .{
299 .id = "css.bucket_index",
300 .kind = .phase_static,
301 .limit_source = .caller,
302 .storage = .{
303 .covered = &.{
304 .{
305 .id = "flat_sorted_bucket_entry_output",
306 .lifetime = .steady,
307 .detail = "flat sorted rule bucket entry output, one entry per sheet selector",
308 },
309 },
310 .excluded = &.{
311 "stylesheet placement holding the rules and selectors the entries address",
312 "caller-owned matched rule output buffer",
313 },
314 },
315 .capacity = .{
316 .inputs = &.{
317 alloc_phase.capacity.bindInput(LimitsType, "entries", "entries"),
318 },
319 .type_selectors = &.{
320 alloc_phase.capacity.bindType(Entry, "entry"),
321 },
322 .nodes = &.{
323 .{ .input = 0 },
324 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
325 .{ .constant = 0 },
326 .{ .alignment = .{ .node = 2, .alignment = .{ .concrete_type = 0 } } },
327 .{ .add = .{ .left = 3, .right = 1 } },
328 .{ .alignment = .{ .node = 4, .alignment = .{ .literal = 16 } } },
329 },
330 .assertions = &.{.{
331 .scope = .closure_total,
332 .measure = .retained,
333 .relation = .exact,
334 .expression = 5,
335 }},
336 },
337 .overload = .{
338 .kind = .reject_before_seal,
339 .detail = "the entry count is the sheet selector count, which is known before acquisition; filling and sorting the admitted block performs no allocation",
340 },
341 .risks = .{
342 .transitive = .{
343 .status = .open,
344 .detail = "the sort and the match walk are allocation-free and witnessed but lack a machine-checked call-graph closure certificate",
345 },
346 .foreign = .{
347 .status = .excluded,
348 .detail = "indexing and matching are process-local transformations with no operating-system edge",
349 },
350 },
351 .obligations = &.{
352 .{ .key = "css_bucket_capacity_model", .role = .capacity_model },
353 .{ .key = "css_bucket_overload", .role = .overload },
354 .{ .key = "css_bucket_acquisition", .role = .custom },
355 .{ .key = "css_bucket_steady_overload", .role = .overload },
356 .{ .key = "css_bucket_steady_foreign_risk", .role = .foreign_risk },
357 },
358 },
359 .bindings = .{
360 .owner = @This(),
361 .seal = .{
362 .family = alloc_phase.capacity.selector(@This().activate),
363 .premise = .{
364 .class = .checked_semantic_fact,
365 .authority = .checker,
366 },
367 },
368 .teardown = .{
369 .family = alloc_phase.capacity.selector(@This().deinit),
370 .premise = .{
371 .class = .checked_semantic_fact,
372 .authority = .checker,
373 },
374 },
375 },
376 };
377
378 phase: alloc_phase.capacity.Phase,
379 limits: LimitsType,
380 capacity: CapacityType,
381 bytes: []align(storage_alignment) u8,
382 entries: []Entry,
383
384 pub fn init(allocator: Allocator, limits: LimitsType) !Storage {
385 const capacity = try CapacityType.derive(limits);
386 const bytes = try allocator.alignedAlloc(u8, .fromByteUnits(storage_alignment), capacity.total_bytes);
387 return .{
388 .phase = .initialization,
389 .limits = limits,
390 .capacity = capacity,
391 .bytes = bytes,
392 .entries = entrySlice(bytes, capacity.entries),
393 };
394 }
395
396 pub fn activate(self: *Storage) void {
397 std.debug.assert(self.phase == .initialization);
398 self.assertStorage();
399 self.phase = .steady;
400 }
401
402 pub fn admits(self: *const Storage, limits: LimitsType) bool {
403 std.debug.assert(self.phase == .steady);
404 return limits.entries <= self.capacity.entries;
405 }
406
407 /// Indexes `parsed`, asserting admission rather than growing.
408 pub fn index(self: *Storage, parsed: *const sheet.StyleSheet) Index {
409 std.debug.assert(self.phase == .steady);
410 std.debug.assert(self.admits(LimitsType.inspect(parsed)));
411 return build(self.entries, parsed);
412 }
413
414 pub fn deinit(self: *Storage, allocator: Allocator) void {
415 std.debug.assert(self.phase != .teardown);
416 self.assertStorage();
417 self.phase = .teardown;
418 allocator.free(self.bytes);
419 self.bytes = &.{};
420 self.entries = &.{};
421 }
422
423 fn assertStorage(self: *const Storage) void {
424 const expected = CapacityType.derive(self.limits) catch unreachable;
425 std.debug.assert(std.meta.eql(expected, self.capacity));
426 std.debug.assert(self.bytes.len == self.capacity.total_bytes);
427 std.debug.assert(self.entries.len == self.capacity.entries);
428 }
429 };
430
431 comptime {
432 alloc_phase.capacity.requireAllocatorExactOwnerShape(Storage);
433 }
434
435 fn entrySlice(bytes: []u8, count: usize) []Entry {
436 if (count == 0) return &.{};
437 const region: []align(@alignOf(Entry)) u8 = @alignCast(bytes[0..][0 .. count * @sizeOf(Entry)]);
438 return std.mem.bytesAsSlice(Entry, region);
439 }
440
441 const fixture = @import("match/fixture/tree.zig");
442
443 const Indexed = struct {
444 workspace: sheet.Workspace,
445 storage: Storage,
446 parsed: sheet.StyleSheet = .{},
447
448 fn init(source: []const u8) !Indexed {
449 var workspace = sheet.Workspace.init(std.testing.allocator);
450 errdefer workspace.deinit();
451 const parsed = try workspace.parse(source, .default());
452 var storage = try Storage.init(std.testing.allocator, Limits.inspect(&parsed));
453 storage.activate();
454 return .{ .workspace = workspace, .storage = storage, .parsed = parsed };
455 }
456
457 fn deinit(self: *Indexed) void {
458 self.storage.deinit(std.testing.allocator);
459 self.workspace.deinit();
460 }
461
462 fn index(self: *Indexed) Index {
463 return self.storage.index(&self.parsed);
464 }
465 };
466
467 fn modelBucketCapacity(limits: Limits) error{CapacityOverflow}!Capacity {
468 const total = @as(u128, limits.entries) * @sizeOf(Entry);
469 if (total > std.math.maxInt(usize)) return error.CapacityOverflow;
470 return .{ .entries = limits.entries, .total_bytes = @intCast(total) };
471 }
472
473 fn checkBucketStorageInit(allocator: Allocator, limits: Limits) !void {
474 var storage = try Storage.init(allocator, limits);
475 defer storage.deinit(allocator);
476 try std.testing.expectEqual(alloc_phase.capacity.Phase.initialization, storage.phase);
477 }
478
479 test "bucket index capacity matches an independent model" {
480 comptime {
481 alloc_phase.capacity.record(
482 alloc_phase.capacity.witness(Storage, "css_bucket_capacity_model"),
483 );
484 }
485 comptime {
486 alloc_phase.capacity.record(alloc_phase.capacity.witness(Storage, "css_bucket_overload"));
487 }
488
489 for ([_]Limits{ .{}, .{ .entries = 1 }, .{ .entries = 4097 } }) |limits| {
490 try std.testing.expectEqual(try modelBucketCapacity(limits), try Capacity.derive(limits));
491 }
492 try std.testing.expectError(error.CapacityOverflow, Capacity.derive(.{ .entries = std.math.maxInt(usize) }));
493 }
494
495 test "bucket index acquisition retries after every allocation failure" {
496 comptime {
497 alloc_phase.capacity.record(
498 alloc_phase.capacity.witness(Storage, "css_bucket_acquisition"),
499 );
500 }
501
502 try std.testing.checkAllAllocationFailures(
503 std.testing.allocator,
504 checkBucketStorageInit,
505 .{Limits{ .entries = 64 }},
506 );
507 }
508
509 test "the bucket index groups selectors by their strongest rightmost key" {
510 comptime {
511 alloc_phase.capacity.record(
512 alloc_phase.capacity.witness(Storage, "css_bucket_steady_overload"),
513 );
514 }
515 comptime {
516 alloc_phase.capacity.record(
517 alloc_phase.capacity.witness(Storage, "css_bucket_steady_foreign_risk"),
518 );
519 }
520
521 var indexed = try Indexed.init(
522 \\#main { color: red }
523 \\.card { color: red }
524 \\article { color: red }
525 \\* { color: red }
526 \\[role=button] { color: red }
527 );
528 defer indexed.deinit();
529 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
530 failing.fail_index = failing.alloc_index;
531 const built = indexed.index();
532 try std.testing.expectEqual(@as(usize, 5), built.entries.len);
533 try std.testing.expectEqual(@as(usize, 1), built.group(.universal, 0).len);
534 try std.testing.expectEqual(@as(usize, 1), built.group(.kind, indexed.parsed.token("article")).len);
535 try std.testing.expectEqual(@as(usize, 1), built.group(.class, indexed.parsed.token("card")).len);
536 try std.testing.expectEqual(@as(usize, 1), built.group(.identifier, indexed.parsed.token("main")).len);
537 try std.testing.expectEqual(@as(usize, 1), built.group(.role, indexed.parsed.token("button")).len);
538 try std.testing.expectEqual(@as(usize, 0), built.group(.kind, indexed.parsed.token("card")).len);
539 try std.testing.expect(!failing.has_induced_failure);
540 }
541
542 test "an element gathers only the candidates its own keys reach" {
543 var indexed = try Indexed.init(
544 \\article .card { color: red }
545 \\#main { color: blue }
546 \\span { color: green }
547 \\* { color: black }
548 );
549 defer indexed.deinit();
550 const built = indexed.index();
551 var tree = fixture.Tree{};
552 _ = try tree.add(&indexed.parsed.atoms, 0, "article#main");
553 _ = try tree.add(&indexed.parsed.atoms, 1, "span.card");
554 tree.finish();
555
556 var out: [8]match.Match = undefined;
557 const leaf = matchElement(built, tree.element(), 1, &out);
558 try std.testing.expectEqual(@as(u32, 3), leaf.count);
559 try std.testing.expectEqual(@as(u32, 0), leaf.rejected);
560 try std.testing.expectEqual(@as(u32, 0), out[0].rule);
561 try std.testing.expectEqual(@as(u32, 2), out[1].rule);
562 try std.testing.expectEqual(@as(u32, 3), out[2].rule);
563
564 const root = matchElement(built, tree.element(), 0, &out);
565 try std.testing.expectEqual(@as(u32, 2), root.count);
566 try std.testing.expectEqual(@as(u32, 1), out[0].rule);
567 try std.testing.expectEqual(@as(u32, 3), out[1].rule);
568
569 var narrow: [1]match.Match = undefined;
570 const bounded = matchElement(built, tree.element(), 1, &narrow);
571 try std.testing.expectEqual(@as(u32, 1), bounded.count);
572 try std.testing.expectEqual(@as(u32, 2), bounded.rejected);
573 }
574
575 test "the summary records the pseudo classes a sheet raises above a subject" {
576 var raised = try Indexed.init(
577 \\.row:hover .cell { color: red }
578 \\.panel:focus-within .field { color: red }
579 );
580 defer raised.deinit();
581 const above = summarize(&raised.parsed);
582 try std.testing.expect(above.ancestorPseudoSensitive(.hover));
583 try std.testing.expect(above.ancestorPseudoSensitive(.focus_within));
584 try std.testing.expect(!above.ancestorPseudoSensitive(.focus));
585 try std.testing.expect(!above.ancestorPseudoSensitive(.active));
586
587 var subject = try Indexed.init(
588 \\.cell:hover { color: red }
589 \\.field:focus-within { color: red }
590 );
591 defer subject.deinit();
592 const rightmost = summarize(&subject.parsed);
593 try std.testing.expectEqual(@as(u32, 0), rightmost.ancestor_pseudo);
594 try std.testing.expect(!rightmost.ancestorPseudoSensitive(.hover));
595 try std.testing.expect(!rightmost.ancestorPseudoSensitive(.focus_within));
596 }
597
598 test "the summary marks ancestor atoms sibling combinators and positions" {
599 var indexed = try Indexed.init(
600 \\article .card { color: red }
601 \\li:nth-child(2) { color: red }
602 \\h1 + p { color: red }
603 );
604 defer indexed.deinit();
605 const summary = summarize(&indexed.parsed);
606 try std.testing.expect(summary.sibling_sensitive);
607 try std.testing.expect(summary.positional);
608 try std.testing.expect(summary.ancestorSensitive(.kind, indexed.parsed.token("article")));
609 try std.testing.expect(summary.ancestorSensitive(.kind, indexed.parsed.token("h1")));
610 try std.testing.expect(!summary.ancestorSensitive(.class, indexed.parsed.token("card")));
611 try std.testing.expect(!summary.ancestorSensitive(.kind, indexed.parsed.token("p")));
612 }