lib/ui/src/style/generation.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const css = @import("css");
4 const abi = @import("../abi/root.zig");
5 const tree = @import("../tree/root.zig");
6 const asset = @import("../asset/root.zig");
7 const computed = @import("computed.zig");
8 const element = @import("element.zig");
9 const share = @import("share.zig");
10
11 const Allocator = std.mem.Allocator;
12
13 pub const Limits = struct {
14 nodes: u32 = 16_384,
15 distinct_styles: u32 = 224,
16 selectors: u32 = 512,
17 font_faces: u32 = 32,
18 bytes: usize = 2_097_152,
19 };
20
21 pub const Capacity = struct {
22 required_bytes: usize,
23 total_bytes: usize,
24 storage_bytes: usize,
25
26 pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {
27 const nodes = std.math.mul(usize, limits.nodes, 2 * @sizeOf(NodeState)) catch return error.CapacityOverflow;
28 const records = std.math.mul(usize, limits.distinct_styles, 2 * @sizeOf(computed.Record)) catch return error.CapacityOverflow;
29 const chain_slots = std.math.mul(usize, limits.distinct_styles, limits.font_faces) catch return error.CapacityOverflow;
30 if (chain_slots > std.math.maxInt(u32)) return error.CapacityOverflow;
31 const chains = std.math.mul(usize, chain_slots, 2 * @sizeOf(asset.AssetHandle)) catch return error.CapacityOverflow;
32 const slots = std.math.mul(usize, std.math.ceilPowerOfTwo(usize, @as(usize, limits.distinct_styles) * 2) catch return error.CapacityOverflow, 2 * @sizeOf(u32)) catch return error.CapacityOverflow;
33 const key_slots = std.math.mul(usize, std.math.ceilPowerOfTwo(usize, limits.distinct_styles) catch return error.CapacityOverflow, 2 * @sizeOf(share.KeySlot)) catch return error.CapacityOverflow;
34 const entries = std.math.mul(usize, limits.selectors, @sizeOf(css.bucket.Entry) + @sizeOf(css.match.Match)) catch return error.CapacityOverflow;
35 const flags = @as(usize, limits.nodes) + @as(usize, limits.distinct_styles) * @sizeOf(u32);
36 const word_count = std.math.divCeil(usize, limits.nodes, 64) catch return error.CapacityOverflow;
37 const key_words = std.math.mul(usize, word_count, (2 * key_columns + 1) * @sizeOf(u64)) catch return error.CapacityOverflow;
38 const node_keys = std.math.mul(usize, limits.nodes, 2 * @sizeOf(u16)) catch return error.CapacityOverflow;
39 const sum = nodes;
40 const sum2 = std.math.add(usize, sum, records) catch return error.CapacityOverflow;
41 const sum3 = std.math.add(usize, sum2, slots) catch return error.CapacityOverflow;
42 const sum4 = std.math.add(usize, sum3, entries) catch return error.CapacityOverflow;
43 const sum5 = std.math.add(usize, sum4, key_slots) catch return error.CapacityOverflow;
44 const tail = std.math.add(usize, flags, key_words) catch return error.CapacityOverflow;
45 const tail_with_keys = std.math.add(usize, tail, node_keys) catch return error.CapacityOverflow;
46 const tail_with_chains = std.math.add(usize, tail_with_keys, chains) catch return error.CapacityOverflow;
47 const tail_with_alignment = std.math.add(usize, tail_with_chains, 80) catch return error.CapacityOverflow;
48 const required = std.math.add(usize, sum5, tail_with_alignment) catch return error.CapacityOverflow;
49 if (required > limits.bytes) return error.CapacityOverflow;
50 return .{ .required_bytes = required, .total_bytes = limits.bytes, .storage_bytes = limits.bytes };
51 }
52 };
53
54 const NodeState = extern struct {
55 id: u64 = 0,
56 ancestor_classes: u64 = 0,
57 style: u32 = 0,
58 computed_generation: u32 = 0,
59 };
60
61 const hover_sensitive: u32 = 0x8000_0000;
62 const style_mask: u32 = ~hover_sensitive;
63 const key_columns: usize = 14;
64
65 const ChainSet = struct {
66 ids: [128]u64 = undefined,
67 occupied: [128]bool = @splat(false),
68
69 fn position(id: u64) usize {
70 const mixed = id *% 0x9e3779b97f4a7c15;
71 return @intCast((mixed >> 57) & 127);
72 }
73
74 fn insert(self: *ChainSet, id: u64) void {
75 var at = position(id);
76 for (0..self.ids.len) |_| {
77 if (!self.occupied[at]) {
78 self.ids[at] = id;
79 self.occupied[at] = true;
80 return;
81 }
82 if (self.ids[at] == id) return;
83 at = (at + 1) & 127;
84 }
85 unreachable;
86 }
87
88 fn contains(self: *const ChainSet, id: u64) bool {
89 var at = position(id);
90 for (0..self.ids.len) |_| {
91 if (!self.occupied[at]) return false;
92 if (self.ids[at] == id) return true;
93 at = (at + 1) & 127;
94 }
95 return false;
96 }
97 };
98
99 fn bucketBit(space: css.bucket.Space, name: []const u8) u16 {
100 const digest = css.atom.hash(name) ^ (@as(u32, @backingInt(space)) *% 0x9e3779b9);
101 return @as(u16, 1) << @intCast(digest % key_columns);
102 }
103
104 const SelectorKeys = struct { bits: u16, universal: bool };
105
106 fn selectorKeys(index: css.bucket.Index) SelectorKeys {
107 var bits: u16 = 0;
108 var universal = false;
109 for (index.entries) |entry| {
110 const space: css.bucket.Space = @fromBackingInt(@intCast(entry.space));
111 if (space == .universal) {
112 universal = true;
113 } else {
114 bits |= bucketBit(space, index.source.name(entry.key));
115 }
116 }
117 return .{ .bits = bits, .universal = universal };
118 }
119
120 pub const Error = error{ DistinctStyleQuota, MatchedRuleQuota, SelectorQuota, CapacityOverflow } || Allocator.Error;
121 pub const Exhaustion = error{ DistinctStyleQuota, MatchedRuleQuota, SelectorQuota, CapacityOverflow };
122 const LimitsType = Limits;
123 const CapacityType = Capacity;
124 const ExhaustionType = Exhaustion;
125
126 pub const Result = struct {
127 restyled: u32 = 0,
128 visited: u32 = 0,
129 carried: u32 = 0,
130 carried_bytes: u64 = 0,
131 shared: u32 = 0,
132 candidates: u64 = 0,
133 ancestor_walks: u64 = 0,
134 combinator_candidates: u64 = 0,
135 };
136
137 pub const Engine = struct {
138 pub const Limits = LimitsType;
139 pub const Capacity = CapacityType;
140 pub const Storage = []align(8) u8;
141 pub const storage_alignment: usize = 8;
142 pub const InitError = error{CapacityOverflow} || Allocator.Error;
143 pub const Exhaustion = ExhaustionType;
144 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
145 .transition_steps_max = 1,
146 .cleanup_steps_per_call_max = 0,
147 .cleanup_calls_at_capacity_max = 0,
148 };
149 pub const claim: alloc_phase.capacity.Declaration = .{
150 .source = .{
151 .id = "ui.style_engine",
152 .kind = .phase_static,
153 .limit_source = .caller,
154 .storage = .{
155 .covered = &.{
156 .{ .id = "computed_style_pools", .lifetime = .steady, .detail = "two bounded record pools, value hash slots, and sixteen-byte sharing keys" },
157 .{ .id = "node_style_generations", .lifetime = .steady, .detail = "two node-state arrays and invalidation occupancy words" },
158 .{ .id = "rule_buckets_and_invalidation", .lifetime = .steady, .detail = "rule entries, match scratch, flags, and style remap" },
159 .{ .id = "authored_font_chains", .lifetime = .steady, .detail = "two bounded chains with one font slot per configured face and distinct style" },
160 },
161 .excluded = &.{
162 "the caller-owned stylesheet source and parsed sheet placement",
163 "the retained publish envelope owned by ui.publish_store",
164 },
165 },
166 .capacity = .{
167 .inputs = &.{alloc_phase.capacity.bindInput(LimitsType, "bytes", "bytes")},
168 .type_selectors = &.{},
169 .nodes = &.{.{ .input = 0 }},
170 .assertions = &.{.{
171 .scope = .closure_total,
172 .measure = .retained,
173 .relation = .exact,
174 .expression = 0,
175 }},
176 },
177 .overload = .{
178 .kind = .reject_before_seal,
179 .detail = "Capacity.derive rejects an undersized byte budget, font binding rejects a face quota above the chain slots, and a cascade above the distinct style quota leaves the live pool sealed",
180 },
181 .risks = .{
182 .transitive = .{ .status = .open, .detail = "the matcher and resolver accept no allocator, while a machine certificate of their call graphs remains open" },
183 .foreign = .{ .status = .excluded, .detail = "cascade and lowering call no foreign runtime" },
184 },
185 .obligations = &.{
186 .{ .key = "ui_style_capacity", .role = .capacity_model },
187 .{ .key = "ui_style_acquisition", .role = .acquisition },
188 .{ .key = "ui_style_sharing_quota", .role = .overload },
189 .{ .key = "ui_style_font_chain", .role = .overload },
190 .{ .key = "ui_style_oom", .role = .initialization_failure },
191 .{ .key = "ui_style_teardown", .role = .teardown },
192 },
193 },
194 .bindings = .{
195 .owner = @This(),
196 .seal = .{
197 .family = alloc_phase.capacity.selector(@This().activate),
198 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
199 },
200 .teardown = .{
201 .family = alloc_phase.capacity.selector(@This().deinit),
202 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
203 },
204 },
205 };
206
207 phase: alloc_phase.capacity.Phase,
208 capacity: CapacityType,
209 bytes: []align(8) u8,
210 limits: LimitsType,
211 states: [2][]NodeState,
212 key_index: [2][]u64,
213 key_bits: [2][]u16,
214 touched: []u64,
215 flags: []u8,
216 entries: []css.bucket.Entry,
217 matches: []css.match.Match,
218 pools: [2]share.Pool,
219 remap: []u32,
220 live: u1 = 0,
221 pool_live: u1 = 0,
222 style_epoch: u64 = 0,
223 count: u32 = 0,
224 node_buffer_addr: usize = 0,
225 view_revision: u64 = 0,
226 last_view: tree.View = .{},
227 selector_count: u32 = 0,
228 stylesheet_generation: u32 = 0,
229 sheet: ?*const css.StyleSheet = null,
230 summary: css.bucket.Summary = .{},
231 selector_key_bits: u16 = 0,
232 universal_selector: bool = false,
233 custom_sheet: bool = false,
234 direct_hover: bool = false,
235 hover_filter_enabled: bool = true,
236 interaction: element.Interaction = .{},
237 metrics: computed.Metrics = .{},
238 fonts: ?*const asset.Registry = null,
239 font_revision: u64 = 0,
240 applied_font_revision: u64 = 0,
241 applied_font_epoch: u64 = 0,
242
243 pub fn init(allocator: Allocator, limits: LimitsType) InitError!Engine {
244 const capacity = try CapacityType.derive(limits);
245 const bytes = try allocator.alignedAlloc(u8, .of(u64), capacity.total_bytes);
246 errdefer allocator.free(bytes);
247 var arena = std.heap.FixedBufferAllocator.init(bytes);
248 const a = arena.allocator();
249 const states_a = a.alloc(NodeState, limits.nodes) catch unreachable;
250 const states_b = a.alloc(NodeState, limits.nodes) catch unreachable;
251 const word_count = std.math.divCeil(usize, limits.nodes, 64) catch unreachable;
252 const key_index_a = a.alloc(u64, key_columns * word_count) catch unreachable;
253 const key_index_b = a.alloc(u64, key_columns * word_count) catch unreachable;
254 const key_bits_a = a.alloc(u16, limits.nodes) catch unreachable;
255 const key_bits_b = a.alloc(u16, limits.nodes) catch unreachable;
256 const touched = a.alloc(u64, word_count) catch unreachable;
257 const flags = a.alloc(u8, limits.nodes) catch unreachable;
258 const entries = a.alloc(css.bucket.Entry, limits.selectors) catch unreachable;
259 const matches = a.alloc(css.match.Match, limits.selectors) catch unreachable;
260 const records_a = a.alloc(computed.Record, limits.distinct_styles) catch unreachable;
261 const records_b = a.alloc(computed.Record, limits.distinct_styles) catch unreachable;
262 const chain_slots = @as(usize, limits.distinct_styles) * limits.font_faces;
263 const chains_a = a.alloc(asset.AssetHandle, chain_slots) catch unreachable;
264 const chains_b = a.alloc(asset.AssetHandle, chain_slots) catch unreachable;
265 const slot_count = std.math.ceilPowerOfTwo(usize, @as(usize, limits.distinct_styles) * 2) catch unreachable;
266 const slots_a = a.alloc(u32, slot_count) catch unreachable;
267 const slots_b = a.alloc(u32, slot_count) catch unreachable;
268 const key_count = std.math.ceilPowerOfTwo(usize, limits.distinct_styles) catch unreachable;
269 const keys_a = a.alloc(share.KeySlot, key_count) catch unreachable;
270 const keys_b = a.alloc(share.KeySlot, key_count) catch unreachable;
271 const remap = a.alloc(u32, limits.distinct_styles) catch unreachable;
272 @memset(slots_a, 0);
273 @memset(slots_b, 0);
274 return .{
275 .phase = .initialization,
276 .capacity = capacity,
277 .bytes = bytes,
278 .limits = limits,
279 .states = .{ states_a, states_b },
280 .key_index = .{ key_index_a, key_index_b },
281 .key_bits = .{ key_bits_a, key_bits_b },
282 .touched = touched,
283 .flags = flags,
284 .entries = entries,
285 .matches = matches,
286 .pools = .{
287 .{ .records = records_a, .slots = slots_a, .keys = keys_a, .chains = chains_a, .font_faces = limits.font_faces },
288 .{ .records = records_b, .slots = slots_b, .keys = keys_b, .chains = chains_b, .font_faces = limits.font_faces },
289 },
290 .remap = remap,
291 };
292 }
293
294 pub fn activate(self: *Engine) void {
295 std.debug.assert(self.phase == .initialization);
296 std.debug.assert(self.bytes.len == self.capacity.storage_bytes);
297 self.phase = .steady;
298 }
299
300 /// The registry outlives the engine. A changed registry epoch recomputes
301 /// every style that may hold a resolved face handle.
302 pub fn setFonts(self: *Engine, registry: ?*const asset.Registry) error{FontChainQuota}!void {
303 if (registry) |value| {
304 if (value.limits.fonts > self.limits.font_faces) return error.FontChainQuota;
305 }
306 self.fonts = registry;
307 self.font_revision +%= 1;
308 }
309
310 pub fn authoredFallbacks(self: *const Engine, node: u32) []const asset.AssetHandle {
311 const text = self.record(node).text;
312 return self.pools[self.pool_live].chains[text.fallback_first..][0..text.fallback_count];
313 }
314
315 pub fn deinit(self: *Engine, allocator: Allocator) void {
316 std.debug.assert(self.phase != .teardown);
317 self.phase = .teardown;
318 allocator.free(self.bytes);
319 self.bytes = &.{};
320 }
321
322 pub fn record(self: *const Engine, node: u32) *const computed.Record {
323 std.debug.assert(node < self.count);
324 return self.pools[self.pool_live].get(self.states[self.live][node].style & style_mask);
325 }
326
327 /// Returns the interned computed Record ID for an admitted node.
328 /// Two nodes sharing the same computed style have the same ID within one style epoch.
329 pub fn styleId(self: *const Engine, node: u32) u32 {
330 std.debug.assert(node < self.count);
331 return self.states[self.live][node].style & style_mask;
332 }
333
334 /// Returns a u64 counter that advances only when a full cascade flips the
335 /// computed-style pool and may renumber IDs: a fast cascade that appends in
336 /// the current pool keeps the epoch. A cache retained across cascades keys
337 /// by both epoch and ID, while a script fallback used only within one layout
338 /// pass can key by ID alone.
339 pub fn styleEpoch(self: *const Engine) u64 {
340 std.debug.assert(self.phase == .steady);
341 return self.style_epoch;
342 }
343
344 fn oldAt(self: *const Engine, id: u64) ?NodeState {
345 for (self.states[self.live][0..self.count]) |state| {
346 if (state.id == id) return state;
347 }
348 return null;
349 }
350
351 fn oldAtIndex(self: *const Engine, view: tree.View, at: u32) ?NodeState {
352 if (self.count == view.nodes.len and self.node_buffer_addr == @intFromPtr(view.nodes.ptr) and
353 self.view_revision == view.header.revision and self.states[self.live][at].id == view.nodes[at].id)
354 {
355 return self.states[self.live][at];
356 }
357 if (view.prior.len == view.nodes.len) {
358 const prior = view.prior[at] & ~tree.prior_dirty;
359 if (prior != tree.prior_absent and prior < self.count) return self.states[self.live][prior];
360 return null;
361 }
362 if (at < self.count and self.states[self.live][at].id == view.nodes[at].id) {
363 return self.states[self.live][at];
364 }
365 return self.oldAt(view.nodes[at].id);
366 }
367
368 fn classBloom(adapter: *const element.Adapter, index: u32) u64 {
369 var result: u64 = 0;
370 for (adapter.view.classesOf(index)) |atom| {
371 const token = adapter.sheet.token(adapter.view.text(atom));
372 result |= @as(u64, 1) << @truncate(token);
373 }
374 return result;
375 }
376
377 fn sameMatchInputs(before: tree.View, old: u32, after: tree.View, at: u32) bool {
378 const left = before.nodes[old];
379 const right = after.nodes[at];
380 if (left.kind != right.kind or left.role != right.role or left.state != right.state or
381 left.flags != right.flags or (old == 0) != (at == 0) or
382 (left.subtree_count == 0 and left.text == abi.text_absent) !=
383 (right.subtree_count == 0 and right.text == abi.text_absent)) return false;
384 if (old != 0 and before.nodes[left.parent].id != after.nodes[right.parent].id) return false;
385 if (!std.mem.eql(u8, before.text(left.identifier), after.text(right.identifier))) return false;
386 const old_classes = before.classesOf(old);
387 const new_classes = after.classesOf(at);
388 if (old_classes.len != new_classes.len) return false;
389 for (old_classes, new_classes) |left_class, right_class| {
390 if (!std.mem.eql(u8, before.text(left_class), after.text(right_class))) return false;
391 }
392 return std.mem.eql(u8, std.mem.sliceAsBytes(before.declarationsOf(old)), std.mem.sliceAsBytes(after.declarationsOf(at)));
393 }
394
395 fn tokenHit(word: u64, token: u32) bool {
396 return token != 0 and word & (@as(u64, 1) << @truncate(token)) != 0;
397 }
398
399 fn hoverAncestorKeyHit(self: *const Engine, callbacks: css.match.Element, index: u32, classes: u64) bool {
400 const summary = self.summary;
401 if (summary.ancestor_kinds == 0 and summary.ancestor_roles == 0 and
402 summary.ancestor_classes == 0 and summary.ancestor_ids == 0) return true;
403 return classes & summary.ancestor_classes != 0 or
404 tokenHit(summary.ancestor_kinds, callbacks.kind(callbacks.context, index)) or
405 tokenHit(summary.ancestor_roles, callbacks.role(callbacks.context, index)) or
406 tokenHit(summary.ancestor_ids, callbacks.identifier(callbacks.context, index));
407 }
408
409 fn nodeKeys(view: tree.View, at: u32) u16 {
410 const node = view.nodes[at];
411 const kind: abi.Kind = @fromBackingInt(@intCast(node.kind));
412 const role: abi.Role = @fromBackingInt(@intCast(node.role));
413 var bits = bucketBit(.kind, @tagName(kind)) | bucketBit(.role, @tagName(role));
414 if (node.identifier != 0) bits |= bucketBit(.identifier, view.text(node.identifier));
415 for (view.classesOf(at)) |class| bits |= bucketBit(.class, view.text(class));
416 return bits;
417 }
418
419 fn putKeyBits(self: *Engine, target: u1, at: u32, bits: u16) void {
420 const stride = std.math.divCeil(usize, self.limits.nodes, 64) catch unreachable;
421 self.key_bits[target][at] = bits;
422 for (0..key_columns) |column| {
423 if (bits & (@as(u16, 1) << @intCast(column)) != 0) {
424 self.key_index[target][column * stride + at / 64] |= @as(u64, 1) << @intCast(at % 64);
425 }
426 }
427 }
428
429 fn updateKeyBits(self: *Engine, view: tree.View, at: u32) void {
430 const bits = nodeKeys(view, at);
431 const old = self.key_bits[self.live][at];
432 if (bits == old) return;
433 const stride = std.math.divCeil(usize, self.limits.nodes, 64) catch unreachable;
434 for (0..key_columns) |column| {
435 const key = @as(u16, 1) << @intCast(column);
436 if ((old ^ bits) & key == 0) continue;
437 const word = &self.key_index[self.live][column * stride + at / 64];
438 const member = @as(u64, 1) << @intCast(at % 64);
439 if (bits & key != 0) word.* |= member else word.* &= ~member;
440 }
441 self.key_bits[self.live][at] = bits;
442 }
443
444 fn markBucketKeys(self: *Engine, count: usize, bits: u16) void {
445 const stride = std.math.divCeil(usize, self.limits.nodes, 64) catch unreachable;
446 for (0..key_columns) |column| {
447 if (bits & (@as(u16, 1) << @intCast(column)) == 0) continue;
448 for (0..std.math.divCeil(usize, count, 64) catch unreachable) |word| {
449 var members = self.key_index[self.live][column * stride + word];
450 while (members != 0) {
451 const bit: usize = @intCast(@ctz(members));
452 self.flags[word * 64 + bit] = 1;
453 members &= members - 1;
454 }
455 }
456 }
457 }
458
459 fn markFastBucketKeys(self: *Engine, target: u1, count: usize, bits: u16, universal: bool) void {
460 if (universal) {
461 for (0..count) |at| self.markFast(@intCast(at));
462 return;
463 }
464 const stride = std.math.divCeil(usize, self.limits.nodes, 64) catch unreachable;
465 for (0..key_columns) |column| {
466 if (bits & (@as(u16, 1) << @intCast(column)) == 0) continue;
467 for (0..std.math.divCeil(usize, count, 64) catch unreachable) |word| {
468 var members = self.key_index[target][column * stride + word];
469 while (members != 0) {
470 self.markFast(@intCast(word * 64 + @ctz(members)));
471 members &= members - 1;
472 }
473 }
474 }
475 }
476
477 fn markSubtree(self: *Engine, view: tree.View, index: u32) void {
478 const end = index + view.nodes[index].subtree_count + 1;
479 @memset(self.flags[index..end], 1);
480 }
481
482 fn countGroup(index: css.bucket.Index, group: []const css.bucket.Entry, result: *Result) void {
483 result.candidates += group.len;
484 for (group) |entry| {
485 const selector = index.source.rules[entry.rule].selectors[entry.selector];
486 result.combinator_candidates += @intFromBool(selector.combinators.len != 0);
487 }
488 }
489
490 fn countCandidates(index: css.bucket.Index, callbacks: css.match.Element, node: u32, result: *Result) void {
491 countGroup(index, index.group(.universal, 0), result);
492 const kind = callbacks.kind(callbacks.context, node);
493 if (kind != 0) countGroup(index, index.group(.kind, kind), result);
494 const role = callbacks.role(callbacks.context, node);
495 if (role != 0) countGroup(index, index.group(.role, role), result);
496 const identifier = callbacks.identifier(callbacks.context, node);
497 if (identifier != 0) countGroup(index, index.group(.identifier, identifier), result);
498 var held: [css.match.max_element_classes]u32 = undefined;
499 const count = callbacks.classes(callbacks.context, node, &held, css.match.max_element_classes);
500 for (held[0..count]) |class| {
501 if (class != 0) countGroup(index, index.group(.class, class), result);
502 }
503 }
504
505 fn markInteraction(self: *Engine, adapter: *const element.Adapter, id: u64, class: css.selector.PseudoClass) void {
506 if (id == 0) return;
507 const found = adapter.find(id) orelse return;
508 var at = found;
509 while (true) {
510 const old = self.oldAt(adapter.view.nodes[at].id);
511 const sensitive = if (class == .hover and self.hover_filter_enabled) if (old) |state| state.style & hover_sensitive != 0 else true else true;
512 if (sensitive) {
513 self.flags[at] = 1;
514 if (self.summary.ancestorPseudoSensitive(class) or
515 (class == .focus and self.summary.ancestorPseudoSensitive(.focus_within)))
516 {
517 self.markSubtree(adapter.view, at);
518 }
519 }
520 if (at == 0) break;
521 at = adapter.view.nodes[at].parent;
522 }
523 }
524
525 fn markFast(self: *Engine, at: u32) void {
526 const word = at / 64;
527 const bit = @as(u64, 1) << @intCast(at % 64);
528 if (self.touched[word] & bit == 0) self.flags[at] = 1;
529 self.touched[word] |= bit;
530 }
531
532 fn markFastSubtree(self: *Engine, view: tree.View, at: u32) void {
533 const end = at + view.nodes[at].subtree_count + 1;
534 var index = at;
535 while (index < end) : (index += 1) self.markFast(index);
536 }
537
538 fn markFastDescendants(self: *Engine, view: tree.View, at: u32) void {
539 const end = at + view.nodes[at].subtree_count + 1;
540 var index = at + 1;
541 while (index < end) : (index += 1) self.markFast(index);
542 }
543
544 fn markFastChildren(self: *Engine, view: tree.View, at: u32) void {
545 const end = at + view.nodes[at].subtree_count + 1;
546 var index = at + 1;
547 while (index < end) : (index += view.nodes[index].subtree_count + 1) self.markFast(index);
548 }
549
550 fn findInView(view: tree.View, id: u64) ?u32 {
551 if (id == 0) return null;
552 if (view.identity) |identity| return identity.lookup(view.nodes, id);
553 for (view.nodes, 0..) |node, at| if (node.id == id) return @intCast(at);
554 return null;
555 }
556
557 fn chain(view: tree.View, id: u64, held: *[65]u32) []const u32 {
558 var at = findInView(view, id) orelse return held[0..0];
559 var used: usize = 0;
560 while (true) {
561 std.debug.assert(used < held.len);
562 held[used] = at;
563 used += 1;
564 if (at == 0) break;
565 at = view.nodes[at].parent;
566 }
567 return held[0..used];
568 }
569
570 fn markFastPseudoNode(self: *Engine, adapter: *element.Adapter, at: u32, class: css.selector.PseudoClass) void {
571 const sensitive = class != .hover or !self.hover_filter_enabled or self.direct_hover or
572 (self.summary.ancestorPseudoSensitive(.hover) and
573 self.hoverAncestorKeyHit(adapter.element(), at, classBloom(adapter, at)));
574 if (!sensitive) return;
575 self.markFast(at);
576 if (self.summary.ancestorPseudoSensitive(class) or
577 (class == .focus and self.summary.ancestorPseudoSensitive(.focus_within)))
578 {
579 self.markFastSubtree(adapter.view, at);
580 }
581 }
582
583 fn markFastTransition(self: *Engine, adapter: *element.Adapter, old_id: u64, new_id: u64, class: css.selector.PseudoClass) void {
584 var old_buffer: [65]u32 = undefined;
585 var new_buffer: [65]u32 = undefined;
586 const old_chain = chain(self.last_view, old_id, &old_buffer);
587 const new_chain = chain(adapter.view, new_id, &new_buffer);
588 if (class == .hover and !self.hover_filter_enabled) {
589 for (old_chain) |at| {
590 const current = adapter.find(self.last_view.nodes[at].id) orelse continue;
591 self.markFastPseudoNode(adapter, current, class);
592 }
593 for (new_chain) |at| self.markFastPseudoNode(adapter, at, class);
594 return;
595 }
596 var old_set = ChainSet{};
597 var new_set = ChainSet{};
598 for (old_chain) |at| old_set.insert(self.last_view.nodes[at].id);
599 for (new_chain) |at| new_set.insert(adapter.view.nodes[at].id);
600 for (old_chain) |at| {
601 const id = self.last_view.nodes[at].id;
602 if (new_set.contains(id)) continue;
603 const current = adapter.find(id) orelse continue;
604 self.markFastPseudoNode(adapter, current, class);
605 }
606 for (new_chain) |at| {
607 if (old_set.contains(adapter.view.nodes[at].id)) continue;
608 self.markFastPseudoNode(adapter, at, class);
609 }
610 }
611
612 fn fastCascade(
613 self: *Engine,
614 view: tree.View,
615 dirty: []const u32,
616 sheet: *const css.StyleSheet,
617 generation: u32,
618 interaction: element.Interaction,
619 index: css.bucket.Index,
620 metrics: computed.Metrics,
621 font_environment: ?computed.FontSource,
622 carry: bool,
623 carried_count: u32,
624 changed_selector_bits: u16,
625 changed_universal: bool,
626 ancestor_classes: u64,
627 ) Error!Result {
628 const words = std.math.divCeil(usize, view.nodes.len, 64) catch unreachable;
629 if (!carry) @memset(self.touched[0..words], 0);
630 if (changed_selector_bits != 0 or changed_universal) {
631 self.markFastBucketKeys(if (carry) self.live ^ 1 else self.live, view.nodes.len, changed_selector_bits, changed_universal);
632 }
633 var adapter = element.Adapter{ .view = view, .sheet = sheet, .interaction = interaction };
634 for (dirty) |at| {
635 const old_index = if (carry) view.prior[at] & ~tree.prior_dirty else tree.prior_absent;
636 if (!carry or old_index == tree.prior_absent or
637 !sameMatchInputs(self.last_view, old_index, view, at)) self.markFast(at);
638 const bloom = classBloom(&adapter, at);
639 const old = self.states[if (carry) self.live ^ 1 else self.live][at];
640 if ((old.ancestor_classes ^ bloom) & ancestor_classes != 0) {
641 self.markFastSubtree(view, at);
642 }
643 if (self.summary.sibling_sensitive or self.summary.positional) {
644 self.markFastChildren(view, at);
645 if (at != 0) self.markFastChildren(view, view.nodes[at].parent);
646 }
647 }
648 if (carry or interaction.hovered != self.interaction.hovered) {
649 self.markFastTransition(&adapter, self.interaction.hovered, interaction.hovered, .hover);
650 }
651 if (carry or interaction.focused != self.interaction.focused) {
652 self.markFastTransition(&adapter, self.interaction.focused, interaction.focused, .focus);
653 }
654 if (interaction.focused != self.interaction.focused) {
655 if (adapter.find(self.interaction.focused)) |old| self.markFastPseudoNode(&adapter, old, .focus);
656 if (adapter.find(interaction.focused)) |new| self.markFastPseudoNode(&adapter, new, .focus);
657 }
658 if (interaction.keyboard_focus != self.interaction.keyboard_focus) {
659 if (adapter.find(interaction.focused)) |focused| self.markFastPseudoNode(&adapter, focused, .focus_visible);
660 }
661 if (carry or interaction.active != self.interaction.active) {
662 self.markFastTransition(&adapter, self.interaction.active, interaction.active, .active);
663 }
664 const stage: u1 = self.live ^ 1;
665 const pool = &self.pools[self.pool_live];
666 var result = Result{ .carried = carried_count, .carried_bytes = @as(u64, carried_count) * @sizeOf(NodeState) };
667 var resolver = css.cascade.Resolver{};
668 for (0..words) |word| {
669 var processed: u64 = 0;
670 while (self.touched[word] & ~processed != 0) {
671 const bit: u6 = @intCast(@ctz(self.touched[word] & ~processed));
672 const at: u32 = @intCast(word * 64 + bit);
673 processed |= @as(u64, 1) << bit;
674 self.flags[at] = 0;
675 result.visited += 1;
676 const node = view.nodes[at];
677 const prior = self.states[if (carry) stage else self.live][at];
678 const bloom = classBloom(&adapter, at);
679 const parent_style: u32 = if (at == 0) 0 else blk: {
680 const parent = node.parent;
681 if (carry) break :blk self.states[stage][parent].style & style_mask;
682 const parent_bit = @as(u64, 1) << @intCast(parent % 64);
683 const staged = self.touched[parent / 64] & parent_bit != 0 and self.flags[parent] == 0;
684 break :blk (if (staged) self.states[stage][parent].style else self.states[self.live][parent].style) & style_mask;
685 };
686 const callbacks = adapter.element();
687 countCandidates(index, callbacks, at, &result);
688 const before_steps = adapter.ancestor_steps;
689 const matched = css.bucket.matchElement(index, callbacks, at, self.matches);
690 if (matched.rejected != 0) return error.MatchedRuleQuota;
691 result.ancestor_walks += adapter.ancestor_steps - before_steps;
692 var rule_hash: u32 = 2166136261;
693 for (self.matches[0..matched.count]) |item| {
694 rule_hash = (rule_hash ^ item.rule) *% 16777619;
695 rule_hash = (rule_hash ^ item.selector) *% 16777619;
696 }
697 const key = share.Key{
698 .matched_rules = rule_hash,
699 .inline_first = node.declaration_first,
700 .inline_count = node.declaration_count,
701 .parent_style = parent_style,
702 };
703 const sensitive = self.direct_hover or (self.summary.ancestorPseudoSensitive(.hover) and
704 self.hoverAncestorKeyHit(callbacks, at, bloom));
705 resolver.begin(sheet.source, &sheet.atoms, null);
706 for (self.matches[0..matched.count]) |item| {
707 const rule = sheet.rules[item.rule];
708 for (rule.lowered) |declaration| resolver.add(declaration, .author, item.specificity, item.order);
709 }
710 for (view.declarationsOf(at)) |declaration| resolver.add(declaration, .author, css.Specificity.inlineStyle(), std.math.maxInt(u32));
711 const inherited = if (parent_style == 0) null else &pool.get(parent_style).computed;
712 var style: css.cascade.Computed = undefined;
713 resolver.finish(inherited, &style);
714 const style_id = try pool.intern(key, self.matches[0..matched.count], style, metrics, font_environment);
715 self.states[stage][at] = .{
716 .id = node.id,
717 .ancestor_classes = bloom,
718 .style = style_id | (if (sensitive) hover_sensitive else 0),
719 .computed_generation = generation,
720 };
721 result.restyled += 1;
722 if (prior.style & style_mask == 0 or !std.mem.eql(u8, std.mem.asBytes(&pool.get(prior.style & style_mask).computed), std.mem.asBytes(&pool.get(style_id).computed))) {
723 self.markFastDescendants(view, at);
724 }
725 }
726 }
727 if (carry) {
728 self.live = stage;
729 self.count = @intCast(view.nodes.len);
730 self.node_buffer_addr = @intFromPtr(view.nodes.ptr);
731 self.view_revision = view.header.revision;
732 } else {
733 for (self.touched[0..words], 0..) |held, word| {
734 var members = held;
735 while (members != 0) {
736 const bit: u6 = @intCast(@ctz(members));
737 const at = word * 64 + bit;
738 self.states[self.live][at] = self.states[stage][at];
739 self.updateKeyBits(view, @intCast(at));
740 members &= members - 1;
741 }
742 }
743 }
744 self.interaction = interaction;
745 self.last_view = view;
746 return result;
747 }
748
749 pub fn cascade(
750 self: *Engine,
751 store: *const tree.Store,
752 sheet: *const css.StyleSheet,
753 generation: u32,
754 interaction: element.Interaction,
755 ) Error!Result {
756 std.debug.assert(self.phase == .steady);
757 return self.cascadeView(store.retained(), store.dirty(), sheet, generation, interaction);
758 }
759
760 pub fn cascadeView(
761 self: *Engine,
762 view: tree.View,
763 dirty: []const u32,
764 sheet: *const css.StyleSheet,
765 generation: u32,
766 interaction: element.Interaction,
767 ) Error!Result {
768 std.debug.assert(self.phase == .steady);
769 if (view.nodes.len > self.limits.nodes) return error.CapacityOverflow;
770 const selector_count = css.bucket.Limits.inspect(sheet).entries;
771 if (selector_count > self.entries.len) return error.SelectorQuota;
772 var adapter = element.Adapter{ .view = view, .sheet = sheet, .interaction = interaction };
773 const metrics = computed.Metrics{
774 .root_font_size = view.header.root_font_size,
775 .viewport_width = view.header.viewport.width,
776 .viewport_height = view.header.viewport.height,
777 };
778 const changed_sheet = self.sheet != sheet or self.stylesheet_generation != generation;
779 const changed_fonts = self.applied_font_revision != self.font_revision or
780 (if (self.fonts) |registry| self.applied_font_epoch != registry.epoch else false);
781 const changed_inputs = !std.meta.eql(self.metrics, metrics) or changed_fonts or (changed_sheet and self.fonts != null);
782 const font_environment: ?computed.FontSource = if (self.fonts) |registry|
783 .{ .registry = registry, .source = sheet.source }
784 else
785 null;
786 const previous_summary = self.summary;
787 const previous_hover = self.direct_hover;
788 const previous_custom = self.custom_sheet;
789 errdefer if (changed_sheet) {
790 self.summary = previous_summary;
791 self.direct_hover = previous_hover;
792 self.custom_sheet = previous_custom;
793 if (self.sheet) |retained_sheet| _ = css.bucket.build(self.entries, retained_sheet);
794 };
795 const index: css.bucket.Index = if (changed_sheet) css.bucket.build(self.entries, sheet) else .{ .entries = self.entries[0..self.selector_count], .source = sheet };
796 const keys: SelectorKeys = if (changed_sheet) selectorKeys(index) else .{ .bits = self.selector_key_bits, .universal = self.universal_selector };
797 if (changed_sheet) {
798 self.summary = css.bucket.summarize(sheet);
799 self.direct_hover = false;
800 self.custom_sheet = false;
801 for (sheet.rules) |rule| {
802 if (rule.customs.len != 0) self.custom_sheet = true;
803 for (rule.selectors) |selector| {
804 if (selector.rightmost().pseudo & css.selector.bit(.hover) != 0) self.direct_hover = true;
805 }
806 }
807 }
808 const changed_selector_bits = if (changed_sheet) self.selector_key_bits | keys.bits else @as(u16, 0);
809 const changed_universal = changed_sheet and (self.universal_selector or keys.universal);
810 const ancestor_classes = previous_summary.ancestor_classes | self.summary.ancestor_classes;
811 const complete_refresh = blk: {
812 if (dirty.len != view.nodes.len) break :blk false;
813 for (dirty, 0..) |at, index_at| if (at != index_at) break :blk false;
814 break :blk true;
815 };
816 if (!complete_refresh and self.count != 0 and !changed_inputs and !self.custom_sheet and !previous_custom and
817 self.count == view.nodes.len and self.node_buffer_addr == @intFromPtr(view.nodes.ptr) and
818 self.view_revision == view.header.revision)
819 {
820 var stable_ids = true;
821 for (dirty) |at| {
822 if (at >= self.count or self.states[self.live][at].id != view.nodes[at].id) {
823 stable_ids = false;
824 break;
825 }
826 }
827 if (stable_ids) {
828 const retained_styles = self.pools[self.pool_live].used;
829 if (self.fastCascade(view, dirty, sheet, generation, interaction, index, metrics, font_environment, false, 0, changed_selector_bits, changed_universal, ancestor_classes)) |fast| {
830 self.sheet = sheet;
831 self.stylesheet_generation = generation;
832 self.selector_key_bits = keys.bits;
833 self.universal_selector = keys.universal;
834 self.selector_count = @intCast(index.entries.len);
835 return fast;
836 } else |err| {
837 self.pools[self.pool_live].truncate(retained_styles);
838 @memset(self.touched[0 .. std.math.divCeil(usize, view.nodes.len, 64) catch unreachable], 0);
839 switch (err) {
840 error.DistinctStyleQuota => {},
841 else => return err,
842 }
843 }
844 }
845 }
846 if (!complete_refresh and self.count != 0 and !changed_inputs and !self.custom_sheet and !previous_custom and
847 view.prior.len == view.nodes.len and self.last_view.nodes.len == self.count and
848 (view.header.base_revision == 0 or view.header.base_revision == self.view_revision) and
849 (self.node_buffer_addr != @intFromPtr(view.nodes.ptr) or self.view_revision != view.header.revision))
850 {
851 const stage: u1 = self.live ^ 1;
852 @memset(self.touched[0 .. std.math.divCeil(usize, view.nodes.len, 64) catch unreachable], 0);
853 @memset(self.key_index[stage], 0);
854 var carried: u32 = 0;
855 var valid = true;
856 for (view.nodes, 0..) |node, at| {
857 const old = view.prior[at] & ~tree.prior_dirty;
858 if (old == tree.prior_absent) {
859 self.states[stage][at] = .{ .id = node.id };
860 self.putKeyBits(stage, @intCast(at), nodeKeys(view, @intCast(at)));
861 continue;
862 }
863 if (old >= self.count or self.states[self.live][old].id != node.id) {
864 valid = false;
865 break;
866 }
867 self.states[stage][at] = self.states[self.live][old];
868 const bits = if (view.prior[at] & tree.prior_dirty != 0)
869 nodeKeys(view, @intCast(at))
870 else
871 self.key_bits[self.live][old];
872 self.putKeyBits(stage, @intCast(at), bits);
873 carried += 1;
874 if (at != 0 and self.last_view.nodes[old].parent < self.last_view.nodes.len and
875 self.last_view.nodes[self.last_view.nodes[old].parent].id != view.nodes[node.parent].id)
876 {
877 self.markFastSubtree(view, @intCast(at));
878 if (self.summary.sibling_sensitive or self.summary.positional) {
879 self.markFastChildren(view, node.parent);
880 const old_parent_id = self.last_view.nodes[self.last_view.nodes[old].parent].id;
881 if (view.identity) |identity| {
882 if (identity.lookup(view.nodes, old_parent_id)) |old_parent| {
883 self.markFastChildren(view, old_parent);
884 }
885 }
886 }
887 }
888 }
889 if (valid) {
890 const retained_styles = self.pools[self.pool_live].used;
891 if (self.fastCascade(view, dirty, sheet, generation, interaction, index, metrics, font_environment, true, carried, changed_selector_bits, changed_universal, ancestor_classes)) |fast| {
892 self.sheet = sheet;
893 self.stylesheet_generation = generation;
894 self.selector_key_bits = keys.bits;
895 self.universal_selector = keys.universal;
896 self.selector_count = @intCast(index.entries.len);
897 return fast;
898 } else |err| {
899 self.pools[self.pool_live].truncate(retained_styles);
900 @memset(self.touched[0 .. std.math.divCeil(usize, view.nodes.len, 64) catch unreachable], 0);
901 switch (err) {
902 error.DistinctStyleQuota => {},
903 else => return err,
904 }
905 }
906 }
907 }
908 @memset(self.flags[0..view.nodes.len], if (self.count == 0 or changed_inputs or
909 self.custom_sheet or (changed_sheet and (self.universal_selector or keys.universal or
910 self.node_buffer_addr != @intFromPtr(view.nodes.ptr) or self.view_revision != view.header.revision))) 1 else 0);
911 if (changed_sheet and self.count != 0 and !changed_inputs and !self.universal_selector and !keys.universal and
912 self.node_buffer_addr == @intFromPtr(view.nodes.ptr) and self.view_revision == view.header.revision)
913 {
914 self.markBucketKeys(view.nodes.len, self.selector_key_bits | keys.bits);
915 }
916 for (dirty) |at| self.flags[at] = 1;
917 if (self.summary.sibling_sensitive or self.summary.positional) {
918 for (dirty) |at| {
919 const parent = view.nodes[at].parent;
920 self.markSubtree(view, parent);
921 }
922 }
923 if (interaction.hovered != self.interaction.hovered) {
924 self.markInteraction(&adapter, self.interaction.hovered, .hover);
925 self.markInteraction(&adapter, interaction.hovered, .hover);
926 }
927 if (interaction.focused != self.interaction.focused or interaction.keyboard_focus != self.interaction.keyboard_focus) {
928 self.markInteraction(&adapter, self.interaction.focused, .focus);
929 self.markInteraction(&adapter, interaction.focused, .focus);
930 }
931 if (interaction.active != self.interaction.active) {
932 self.markInteraction(&adapter, self.interaction.active, .active);
933 self.markInteraction(&adapter, interaction.active, .active);
934 }
935 const next: u1 = self.live ^ 1;
936 const next_pool = &self.pools[self.pool_live ^ 1];
937 next_pool.reset();
938 @memset(self.key_index[next], 0);
939 @memset(self.remap, 0);
940 var result = Result{};
941 var resolver = css.cascade.Resolver{};
942 var custom_stack: [65]css.cascade.CustomTable = undefined;
943 var custom_nodes: [65]u32 = undefined;
944 var custom_depth: usize = 0;
945 for (view.nodes, 0..) |node, i| {
946 result.visited += 1;
947 const at: u32 = @intCast(i);
948 self.putKeyBits(next, at, nodeKeys(view, at));
949 const prior = self.oldAtIndex(view, at);
950 const bloom = classBloom(&adapter, at);
951 const parent_style: u32 = if (at == 0) 0 else self.states[next][node.parent].style & style_mask;
952 const ancestor_change = if (prior) |state| (state.ancestor_classes ^ bloom) & self.summary.ancestor_classes != 0 else false;
953 if (ancestor_change) self.markSubtree(view, at);
954 const same_view = self.count == view.nodes.len and self.node_buffer_addr == @intFromPtr(view.nodes.ptr) and
955 self.view_revision == view.header.revision;
956 const shifted = prior == null or if (same_view)
957 self.states[self.live][at].id != node.id
958 else if (view.prior.len == view.nodes.len)
959 (view.prior[at] & ~tree.prior_dirty) != at
960 else
961 at >= self.count or self.states[self.live][at].id != node.id;
962 const should_compute = changed_inputs or self.flags[at] != 0 or prior == null or shifted;
963 if (!should_compute) {
964 var same = prior.?;
965 const old_id = same.style & style_mask;
966 var new_id = self.remap[old_id - 1];
967 if (new_id == 0) {
968 const inherited = self.pools[self.pool_live].get(old_id);
969 new_id = try next_pool.intern(.{
970 .matched_rules = 0,
971 .inline_first = 0,
972 .inline_count = 0,
973 .parent_style = parent_style,
974 }, &.{}, inherited.computed, metrics, font_environment);
975 self.remap[old_id - 1] = new_id;
976 }
977 const old_hover = same.style & hover_sensitive;
978 const next_hover = if (changed_sheet)
979 if (self.direct_hover or (self.summary.ancestorPseudoSensitive(.hover) and
980 self.hoverAncestorKeyHit(adapter.element(), at, bloom))) hover_sensitive else @as(u32, 0)
981 else
982 old_hover;
983 same.style = new_id | next_hover;
984 same.ancestor_classes = bloom;
985 same.computed_generation = generation;
986 self.states[next][at] = same;
987 result.shared += 1;
988 continue;
989 }
990 const callbacks = adapter.element();
991 countCandidates(index, callbacks, at, &result);
992 const before_steps = adapter.ancestor_steps;
993 const matched = css.bucket.matchElement(index, callbacks, at, self.matches);
994 if (matched.rejected != 0) return error.MatchedRuleQuota;
995 result.ancestor_walks += adapter.ancestor_steps - before_steps;
996 var rule_hash: u32 = 2166136261;
997 for (self.matches[0..matched.count]) |item| {
998 rule_hash = (rule_hash ^ item.rule) *% 16777619;
999 rule_hash = (rule_hash ^ item.selector) *% 16777619;
1000 }
1001 const key = share.Key{
1002 .matched_rules = rule_hash,
1003 .inline_first = node.declaration_first,
1004 .inline_count = node.declaration_count,
1005 .parent_style = parent_style,
1006 };
1007 const sensitive = self.direct_hover or (self.summary.ancestorPseudoSensitive(.hover) and
1008 self.hoverAncestorKeyHit(callbacks, at, bloom));
1009 if (if (self.custom_sheet) null else next_pool.lookup(key, self.matches[0..matched.count])) |style_id| {
1010 self.states[next][at] = .{
1011 .id = node.id,
1012 .ancestor_classes = bloom,
1013 .style = style_id | (if (sensitive) hover_sensitive else 0),
1014 .computed_generation = generation,
1015 };
1016 result.restyled += 1;
1017 result.shared += 1;
1018 if (prior) |old| {
1019 const old_style = self.pools[self.pool_live].get(old.style & style_mask);
1020 const new_style = next_pool.get(style_id);
1021 if (!std.mem.eql(u8, std.mem.asBytes(&old_style.computed), std.mem.asBytes(&new_style.computed))) {
1022 self.markSubtree(view, at);
1023 }
1024 }
1025 continue;
1026 }
1027 var parent_customs: ?*const css.cascade.CustomTable = null;
1028 if (self.custom_sheet and at != 0) {
1029 while (custom_depth > 0 and custom_nodes[custom_depth - 1] != node.parent) custom_depth -= 1;
1030 std.debug.assert(custom_depth > 0);
1031 parent_customs = &custom_stack[custom_depth - 1];
1032 }
1033 resolver.begin(sheet.source, &sheet.atoms, parent_customs);
1034 for (self.matches[0..matched.count]) |item| {
1035 const rule = sheet.rules[item.rule];
1036 for (rule.lowered) |declaration| resolver.add(declaration, .author, item.specificity, item.order);
1037 for (rule.customs) |custom| resolver.addCustom(custom, .author, item.specificity, item.order);
1038 }
1039 for (view.declarationsOf(at)) |declaration| resolver.add(declaration, .author, css.Specificity.inlineStyle(), std.math.maxInt(u32));
1040 const inherited = if (parent_style == 0) null else &next_pool.get(parent_style).computed;
1041 var style: css.cascade.Computed = undefined;
1042 resolver.finish(inherited, &style);
1043 if (self.custom_sheet) {
1044 if (custom_depth == custom_stack.len) return error.CapacityOverflow;
1045 custom_stack[custom_depth] = resolver.customs;
1046 custom_nodes[custom_depth] = at;
1047 custom_depth += 1;
1048 }
1049 const style_id = try next_pool.intern(key, self.matches[0..matched.count], style, metrics, font_environment);
1050 self.states[next][at] = .{
1051 .id = node.id,
1052 .ancestor_classes = bloom,
1053 .style = style_id | (if (sensitive) hover_sensitive else 0),
1054 .computed_generation = generation,
1055 };
1056 result.restyled += 1;
1057 if (prior) |old| {
1058 const old_style = self.pools[self.pool_live].get(old.style & style_mask);
1059 if (!std.mem.eql(u8, std.mem.asBytes(&old_style.computed), std.mem.asBytes(&style))) {
1060 self.markSubtree(view, at);
1061 }
1062 }
1063 }
1064 self.live = next;
1065 self.pool_live ^= 1;
1066 std.debug.assert(self.style_epoch < std.math.maxInt(u64));
1067 self.style_epoch += 1;
1068 self.count = @intCast(view.nodes.len);
1069 self.node_buffer_addr = @intFromPtr(view.nodes.ptr);
1070 self.view_revision = view.header.revision;
1071 self.last_view = view;
1072 self.selector_count = @intCast(index.entries.len);
1073 self.sheet = sheet;
1074 self.stylesheet_generation = generation;
1075 self.selector_key_bits = keys.bits;
1076 self.universal_selector = keys.universal;
1077 self.interaction = interaction;
1078 self.metrics = metrics;
1079 self.applied_font_revision = self.font_revision;
1080 self.applied_font_epoch = if (self.fonts) |registry| registry.epoch else 0;
1081 return result;
1082 }
1083 };
1084
1085 comptime {
1086 alloc_phase.capacity.requireAllocatorExactOwnerShape(Engine);
1087 }
1088
1089 test "incremental cascade agrees with a cold cascade after one dirty node" {
1090 const allocator = std.testing.allocator;
1091 var workspace = css.Workspace.init(allocator);
1092 defer workspace.deinit();
1093 const sheet = try workspace.parse("box { color: #ff0000; } text { color: #0000ff; }", .default());
1094 const nodes = [_]@import("../abi/root.zig").Node{
1095 .{ .id = 1, .revision = 1, .kind = @backingInt(@import("../abi/root.zig").Kind.box), .subtree_count = 1 },
1096 .{ .id = 2, .revision = 1, .kind = @backingInt(@import("../abi/root.zig").Kind.text), .parent = 0 },
1097 };
1098 const view = tree.View{ .header = .{ .root_font_size = 16 }, .nodes = &nodes };
1099 const limits = Limits{ .nodes = 2, .distinct_styles = 4, .selectors = 4, .bytes = 16 * 1024 };
1100 var incremental = try Engine.init(allocator, limits);
1101 defer incremental.deinit(allocator);
1102 incremental.activate();
1103 const first = try incremental.cascadeView(view, &.{ 0, 1 }, &sheet, 1, .{});
1104 try std.testing.expectEqual(@as(u32, 2), first.restyled);
1105 const next = try incremental.cascadeView(view, &.{1}, &sheet, 1, .{});
1106 try std.testing.expectEqual(@as(u32, 1), next.restyled);
1107 var cold = try Engine.init(allocator, limits);
1108 defer cold.deinit(allocator);
1109 cold.activate();
1110 _ = try cold.cascadeView(view, &.{ 0, 1 }, &sheet, 1, .{});
1111 for (nodes, 0..) |_, at| {
1112 try std.testing.expect(std.meta.eql(incremental.record(@intCast(at)).computed, cold.record(@intCast(at)).computed));
1113 }
1114 }
1115
1116 test "stylesheet generation visits only indexed bucket keys" {
1117 const allocator = std.testing.allocator;
1118 var first_workspace = css.Workspace.init(allocator);
1119 defer first_workspace.deinit();
1120 var second_workspace = css.Workspace.init(allocator);
1121 defer second_workspace.deinit();
1122 const first = try first_workspace.parse(".alpha { color: red; }", .default());
1123 const second = try second_workspace.parse(".beta { color: blue; }", .default());
1124 var nodes: [128]abi.Node = undefined;
1125 nodes[0] = .{ .id = 1, .subtree_count = 127 };
1126 for (1..nodes.len) |at| nodes[at] = .{ .id = @intCast(at + 1), .parent = 0 };
1127 nodes[1].class_first = 0;
1128 nodes[1].class_count = 1;
1129 nodes[2].class_first = 1;
1130 nodes[2].class_count = 1;
1131 const classes = [_]u32{ 1, 2 };
1132 const atoms = [_]abi.Atom{ .{}, .{ .offset = 0, .len = 5 }, .{ .offset = 5, .len = 4 } };
1133 const view = tree.View{ .nodes = &nodes, .classes = &classes, .atoms = &atoms, .strings = "alphabeta" };
1134 var incremental = try Engine.init(allocator, .{ .nodes = 128, .distinct_styles = 8, .selectors = 4, .bytes = 64 * 1024 });
1135 defer incremental.deinit(allocator);
1136 incremental.activate();
1137 _ = try incremental.cascadeView(view, &.{}, &first, 1, .{});
1138 const changed = try incremental.cascadeView(view, &.{}, &second, 2, .{});
1139 try std.testing.expectEqual(@as(u32, 2), changed.visited);
1140 try std.testing.expectEqual(@as(u32, 2), changed.restyled);
1141 var cold = try Engine.init(allocator, .{ .nodes = 128, .distinct_styles = 8, .selectors = 4, .bytes = 64 * 1024 });
1142 defer cold.deinit(allocator);
1143 cold.activate();
1144 _ = try cold.cascadeView(view, &.{}, &second, 2, .{});
1145 for (nodes, 0..) |_, at| {
1146 try std.testing.expect(std.meta.eql(incremental.record(@intCast(at)).computed, cold.record(@intCast(at)).computed));
1147 }
1148 }
1149
1150 test "ui_style_capacity derives the caller bound" {
1151 comptime {
1152 @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_capacity"), null, null, null, null, null, null);
1153 }
1154 const capacity = try Capacity.derive(.{});
1155 try std.testing.expectEqual(@as(usize, 2_097_152), capacity.total_bytes);
1156 try std.testing.expect(capacity.required_bytes <= capacity.total_bytes);
1157 }
1158
1159 test "ui_style_acquisition and ui_style_teardown own one block" {
1160 comptime {
1161 @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_acquisition"), null, null, null, null, null, null);
1162 @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_teardown"), null, null, null, null, null, null);
1163 }
1164 var engine = try Engine.init(std.testing.allocator, .{});
1165 try std.testing.expectEqual(@as(usize, 2_097_152), engine.bytes.len);
1166 engine.activate();
1167 engine.deinit(std.testing.allocator);
1168 try std.testing.expectEqual(alloc_phase.capacity.Phase.teardown, engine.phase);
1169 }
1170
1171 fn openAndClose(allocator: Allocator, limits: LimitsType) !void {
1172 var engine = try Engine.init(allocator, limits);
1173 engine.activate();
1174 engine.deinit(allocator);
1175 }
1176
1177 test "ui_style_oom refuses acquisition without a partial block" {
1178 comptime {
1179 @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_oom"), null, null, null, null, null, null);
1180 }
1181 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 0 });
1182 try std.testing.expectError(error.OutOfMemory, Engine.init(failing.allocator(), .{}));
1183 try std.testing.expectEqual(@as(usize, 0), failing.allocated_bytes - failing.freed_bytes);
1184 try std.testing.checkAllAllocationFailures(std.testing.allocator, openAndClose, .{LimitsType{}});
1185 }
1186
1187 test "ui_style_sharing_quota rejects before changing the live generation" {
1188 comptime {
1189 @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_sharing_quota"), null, null, null, null, null, null);
1190 }
1191 const allocator = std.testing.allocator;
1192 var workspace = css.Workspace.init(allocator);
1193 defer workspace.deinit();
1194 const sheet = try workspace.parse("box { color: red; } text { color: blue; }", .default());
1195 const nodes = [_]abi.Node{
1196 .{ .id = 1, .subtree_count = 1, .kind = @backingInt(abi.Kind.box) },
1197 .{ .id = 2, .parent = 0, .kind = @backingInt(abi.Kind.text) },
1198 };
1199 var engine = try Engine.init(allocator, .{ .nodes = 2, .distinct_styles = 1, .selectors = 2, .bytes = 8 * 1024 });
1200 defer engine.deinit(allocator);
1201 engine.activate();
1202 const view = tree.View{ .header = .{ .root_font_size = 16 }, .nodes = &nodes };
1203 try std.testing.expectError(error.DistinctStyleQuota, engine.cascadeView(view, &.{ 0, 1 }, &sheet, 1, .{}));
1204 try std.testing.expectEqual(@as(u32, 0), engine.count);
1205 try std.testing.expectEqual(@as(u32, 0), engine.stylesheet_generation);
1206 }
1207
1208 test "ui_style_font_chain rejects a face quota before binding" {
1209 comptime {
1210 @stardustClaim(alloc_phase.capacity.witness(Engine, "ui_style_font_chain"), null, null, null, null, null, null);
1211 }
1212 const allocator = std.testing.allocator;
1213 var registry = try asset.Registry.init(allocator, .{ .fonts = 2, .images = 0, .owned_bytes = 0 });
1214 defer registry.deinit(allocator);
1215 registry.activate();
1216 var engine = try Engine.init(allocator, .{ .nodes = 1, .distinct_styles = 1, .selectors = 1, .font_faces = 1, .bytes = 8 * 1024 });
1217 defer engine.deinit(allocator);
1218 engine.activate();
1219 try std.testing.expectError(error.FontChainQuota, engine.setFonts(®istry));
1220 try std.testing.expect(engine.fonts == null);
1221 }
1222
1223 test "sparse quota failure preserves the live pool and node states" {
1224 const allocator = std.testing.allocator;
1225 var workspace = css.Workspace.init(allocator);
1226 defer workspace.deinit();
1227 const sheet = try workspace.parse(".red { color: red; } .blue { color: blue; }", .default());
1228 const nodes = [_]abi.Node{
1229 .{ .id = 1, .subtree_count = 2 },
1230 .{ .id = 2, .parent = 0, .class_first = 0, .class_count = 1 },
1231 .{ .id = 3, .parent = 0, .class_first = 1, .class_count = 1 },
1232 };
1233 var classes = [_]u32{ 1, 1 };
1234 const atoms = [_]abi.Atom{ .{}, .{ .offset = 0, .len = 3 }, .{ .offset = 3, .len = 4 } };
1235 const view = tree.View{ .nodes = &nodes, .classes = &classes, .atoms = &atoms, .strings = "redblue" };
1236 var engine = try Engine.init(allocator, .{ .nodes = 3, .distinct_styles = 2, .selectors = 4, .bytes = 64 * 1024 });
1237 defer engine.deinit(allocator);
1238 engine.activate();
1239 _ = try engine.cascadeView(view, &.{ 0, 1, 2 }, &sheet, 1, .{});
1240 const original = engine.record(2).computed;
1241 const original_epoch = engine.styleEpoch();
1242 const retained_styles = engine.pools[engine.pool_live].used;
1243 classes[1] = 2;
1244 try std.testing.expectError(error.DistinctStyleQuota, engine.cascadeView(view, &.{2}, &sheet, 1, .{}));
1245 try std.testing.expectEqual(retained_styles, engine.pools[engine.pool_live].used);
1246 try std.testing.expectEqual(original_epoch, engine.styleEpoch());
1247 try std.testing.expect(std.meta.eql(original, engine.record(2).computed));
1248 classes[1] = 1;
1249 const restored = try engine.cascadeView(view, &.{2}, &sheet, 1, .{});
1250 try std.testing.expectEqual(@as(u32, 1), restored.visited);
1251 try std.testing.expect(std.meta.eql(original, engine.record(2).computed));
1252 }
1253
1254 test "style ids share within an epoch and a full cascade advances it" {
1255 const allocator = std.testing.allocator;
1256 var workspace = css.Workspace.init(allocator);
1257 defer workspace.deinit();
1258 const red = try workspace.parse("box { color: red; }", .default());
1259 const blue = try workspace.parse("box { color: blue; }", .default());
1260 const nodes = [_]abi.Node{
1261 .{ .id = 1, .subtree_count = 1, .kind = @backingInt(abi.Kind.box) },
1262 .{ .id = 2, .parent = 0, .kind = @backingInt(abi.Kind.box) },
1263 };
1264 const view = tree.View{
1265 .header = .{ .root_font_size = 16 },
1266 .nodes = &nodes,
1267 };
1268 var engine = try Engine.init(allocator, .{
1269 .nodes = 2,
1270 .distinct_styles = 4,
1271 .selectors = 2,
1272 .bytes = 16 * 1024,
1273 });
1274 defer engine.deinit(allocator);
1275 engine.activate();
1276 try std.testing.expectEqual(@as(u64, 0), engine.styleEpoch());
1277 _ = try engine.cascadeView(view, &.{ 0, 1 }, &red, 1, .{});
1278 const first_epoch = engine.styleEpoch();
1279 const first_id = engine.styleId(0);
1280 try std.testing.expectEqual(@as(u64, 1), first_epoch);
1281 try std.testing.expectEqual(first_id, engine.styleId(1));
1282 _ = try engine.cascadeView(view, &.{1}, &red, 1, .{});
1283 try std.testing.expectEqual(first_epoch, engine.styleEpoch());
1284 try std.testing.expectEqual(first_id, engine.styleId(0));
1285 _ = try engine.cascadeView(view, &.{ 0, 1 }, &blue, 2, .{});
1286 try std.testing.expectEqual(first_epoch + 1, engine.styleEpoch());
1287 }