lib/css/src/cascade/resolve.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const atom = @import("../atom.zig");
4 const property = @import("../property/root.zig");
5 const selector = @import("../selector/root.zig");
6 const token = @import("../token/root.zig");
7 const value = @import("../value/root.zig");
8
9 const Specificity = selector.Specificity;
10 const Value = value.Value;
11
12 /// The three cascade origins this engine carries.
13 pub const Origin = enum(u8) {
14 user_agent = 0,
15 user = 1,
16 author = 2,
17 };
18
19 /// The cascade levels in increasing precedence. Importance inverts the origin
20 /// order, which is the whole reason the levels are named rather than derived.
21 pub const Level = enum(u8) {
22 user_agent_normal = 0,
23 user_normal = 1,
24 author_normal = 2,
25 author_important = 3,
26 user_important = 4,
27 user_agent_important = 5,
28 };
29
30 /// The number of cascade levels.
31 pub const level_count: usize = 6;
32
33 /// The most custom properties one element may carry.
34 pub const max_custom_properties: usize = 64;
35
36 /// The substitution buffer one element's `var()` expansions share.
37 pub const max_substitution_bytes: usize = 4096;
38
39 /// The deepest `var()` nesting the resolver expands before failing closed.
40 pub const max_substitution_depth: u32 = 8;
41
42 /// Bit one of a value's flag word marks a declaration whose text still holds a
43 /// `var()` reference. Its `a` and `b` words are the source span, not a value.
44 pub const flag_pending: u16 = 2;
45
46 /// One custom property declaration. Its value stays raw text, because a custom
47 /// property's value is a token sequence rather than a typed value.
48 pub const Custom = struct {
49 name: u32,
50 start: u32,
51 end: u32,
52 important: bool = false,
53 };
54
55 /// The winning declaration at one cascade level.
56 pub const Slot = struct {
57 value: Value = .{},
58 specificity: Specificity = .{},
59 order: u32 = 0,
60 present: bool = false,
61 };
62
63 /// A computed style: one value per property, dense and indexed by identifier.
64 pub const Computed = struct {
65 values: [property.count]Value = @splat(.{}),
66
67 pub fn get(self: *const Computed, id: property.Id) Value {
68 std.debug.assert(id != .invalid);
69 return self.values[@backingInt(id)];
70 }
71
72 pub fn set(self: *Computed, id: property.Id, item: Value) void {
73 std.debug.assert(id != .invalid);
74 self.values[@backingInt(id)] = item;
75 }
76
77 /// The computed style of an element with no declarations and no parent.
78 pub fn initial() Computed {
79 var result = Computed{};
80 for (property.entries, 1..) |entry, index| result.values[index] = entry.initial;
81 return result;
82 }
83 };
84
85 /// One custom property's winning declaration.
86 pub const CustomSlot = struct {
87 name: u32 = 0,
88 start: u32 = 0,
89 end: u32 = 0,
90 level: Level = .user_agent_normal,
91 specificity: Specificity = .{},
92 order: u32 = 0,
93 inherited: bool = false,
94 };
95
96 /// The custom properties in scope for one element. Overflow rejects the extra
97 /// declaration and counts it rather than evicting a resolved one.
98 pub const CustomTable = struct {
99 slots: [max_custom_properties]CustomSlot = @splat(.{}),
100 count: u32 = 0,
101 rejected: u32 = 0,
102
103 pub fn find(self: *const CustomTable, name: u32) ?usize {
104 var index: usize = 0;
105 while (index < self.count) : (index += 1) {
106 if (self.slots[index].name == name) return index;
107 }
108 return null;
109 }
110
111 fn clear(self: *CustomTable) void {
112 self.count = 0;
113 self.rejected = 0;
114 }
115 };
116
117 /// Resolves one element's cascade. The caller owns it and reuses it across
118 /// elements, so the cascade allocates nothing.
119 ///
120 /// A substituted string value borrows the resolver's substitution buffer and
121 /// stays valid until the next `begin`.
122 pub const Resolver = struct {
123 slots: [property.count][level_count]Slot = @splat(@splat(.{})),
124 customs: CustomTable = .{},
125 buffer: [max_substitution_bytes]u8 = undefined,
126 names: ?*const atom.Table = null,
127 used: u32 = 0,
128 source: []const u8 = &.{},
129 substitution_rejected: u32 = 0,
130
131 /// Starts a fresh element. `parent_customs` seeds the inherited custom
132 /// properties, which is how a custom property reaches a subtree.
133 pub fn begin(
134 self: *Resolver,
135 source: []const u8,
136 names: ?*const atom.Table,
137 parent_customs: ?*const CustomTable,
138 ) void {
139 self.slots = @splat(@splat(.{}));
140 self.names = names;
141 self.customs.clear();
142 self.used = 0;
143 self.source = source;
144 self.substitution_rejected = 0;
145 if (parent_customs) |table| {
146 var index: usize = 0;
147 while (index < table.count and index < max_custom_properties) : (index += 1) {
148 self.customs.slots[index] = table.slots[index];
149 self.customs.slots[index].inherited = true;
150 }
151 self.customs.count = @intCast(index);
152 }
153 }
154
155 /// Offers one declaration to the cascade.
156 pub fn add(
157 self: *Resolver,
158 declaration: value.Declaration,
159 origin: Origin,
160 specificity: Specificity,
161 order: u32,
162 ) void {
163 const id: property.Id = @fromBackingInt(@intCast(declaration.property));
164 if (id == .invalid) return;
165 const level = levelOf(origin, declaration.important());
166 const slot = &self.slots[declaration.property][@backingInt(level)];
167 const candidate = Slot{
168 .value = declaration.value(),
169 .specificity = specificity,
170 .order = order,
171 .present = true,
172 };
173 if (!slot.present or wins(candidate, slot.*)) slot.* = candidate;
174 }
175
176 /// Offers one custom property declaration to the cascade.
177 pub fn addCustom(
178 self: *Resolver,
179 custom: Custom,
180 origin: Origin,
181 specificity: Specificity,
182 order: u32,
183 ) void {
184 const level = levelOf(origin, custom.important);
185 const candidate = CustomSlot{
186 .name = custom.name,
187 .start = custom.start,
188 .end = custom.end,
189 .level = level,
190 .specificity = specificity,
191 .order = order,
192 };
193 if (self.customs.find(custom.name)) |index| {
194 const existing = self.customs.slots[index];
195 if (existing.inherited or customWins(candidate, existing)) {
196 self.customs.slots[index] = candidate;
197 }
198 return;
199 }
200 if (self.customs.count == max_custom_properties) {
201 self.customs.rejected += 1;
202 return;
203 }
204 self.customs.slots[self.customs.count] = candidate;
205 self.customs.count += 1;
206 }
207
208 /// Resolves every property against `parent` and writes the computed style.
209 pub fn finish(self: *Resolver, parent: ?*const Computed, out: *Computed) void {
210 out.values[0] = .{};
211 for (property.entries, 1..) |entry, index| {
212 const id: property.Id = @fromBackingInt(@intCast(index));
213 const from_parent = if (parent) |source| source.get(id) else entry.initial;
214 const winner = self.resolve(index);
215 out.values[index] = self.compute(id, winner, entry, from_parent);
216 }
217 }
218
219 fn compute(
220 self: *Resolver,
221 id: property.Id,
222 winner: ?Slot,
223 entry: property.Metadata,
224 from_parent: Value,
225 ) Value {
226 const fallback = if (entry.inherited) from_parent else entry.initial;
227 const slot = winner orelse return fallback;
228 const resolved = if (slot.value.flags & flag_pending != 0)
229 self.substituted(id, slot.value) orelse return fallback
230 else
231 slot.value;
232 return switch (resolved.asKeyword()) {
233 .inherit => from_parent,
234 .initial, .revert => entry.initial,
235 .unset => fallback,
236 else => resolved,
237 };
238 }
239
240 fn resolve(self: *Resolver, index: usize) ?Slot {
241 var excluded: u8 = 0;
242 var round: u32 = 0;
243 while (round <= 3) : (round += 1) {
244 const found = self.pick(index, excluded) orelse return null;
245 if (found.slot.value.asKeyword() != .revert) return found.slot;
246 const origin = originOf(found.level);
247 excluded |= originBit(origin);
248 }
249 return null;
250 }
251
252 const Winner = struct {
253 slot: Slot,
254 level: Level,
255 };
256
257 fn pick(self: *Resolver, index: usize, excluded: u8) ?Winner {
258 var level: usize = level_count;
259 while (level > 0) {
260 level -= 1;
261 const candidate: Level = @fromBackingInt(@intCast(level));
262 if (excluded & originBit(originOf(candidate)) != 0) continue;
263 const slot = self.slots[index][level];
264 if (slot.present) return .{ .slot = slot, .level = candidate };
265 }
266 return null;
267 }
268
269 fn substituted(self: *Resolver, id: property.Id, pending: Value) ?Value {
270 const begin_offset = self.used;
271 var visiting: u64 = 0;
272 if (!self.expandSpan(pending.a, pending.a + pending.b, 0, &visiting)) {
273 self.used = begin_offset;
274 self.substitution_rejected += 1;
275 return null;
276 }
277 const text = self.buffer[begin_offset..self.used];
278 const grammar = property.metadata(id).grammar;
279 const parsed = value.parse(grammar, text, 0, @intCast(text.len));
280 if (!parsed.present()) return null;
281 return parsed;
282 }
283
284 fn expandSpan(self: *Resolver, start: u32, end: u32, depth: u32, visiting: *u64) bool {
285 if (depth > max_substitution_depth) return false;
286 std.debug.assert(end <= self.source.len);
287 var tokenizer = token.Tokenizer{ .source = self.source[0..end], .index = start };
288 var copied = start;
289 var guard: usize = 0;
290 while (guard <= self.source.len + 1) : (guard += 1) {
291 const next = tokenizer.next();
292 if (next.kind == .eof) break;
293 if (next.kind != .function) continue;
294 if (!std.ascii.eqlIgnoreCase(next.value(self.source), "var")) continue;
295 const close = closeParen(&tokenizer, self.source.len) orelse return false;
296 if (!self.write(self.source[copied..next.start])) return false;
297 if (!self.expandVariable(next.end, close, depth, visiting)) return false;
298 copied = close + 1;
299 tokenizer.index = close + 1;
300 }
301 return self.write(self.source[copied..end]);
302 }
303
304 fn expandVariable(self: *Resolver, start: u32, end: u32, depth: u32, visiting: *u64) bool {
305 const body = self.source[start..end];
306 const comma = topLevelComma(body);
307 const name = std.mem.trim(u8, body[0 .. comma orelse body.len], " \t\r\n\x0C");
308 if (!property.isCustom(name)) return false;
309 if (self.lookupCustom(name)) |index| {
310 const mask = @as(u64, 1) << @intCast(index);
311 if (visiting.* & mask != 0) return false;
312 visiting.* |= mask;
313 const slot = self.customs.slots[index];
314 const expanded = self.expandSpan(slot.start, slot.end, depth + 1, visiting);
315 visiting.* &= ~mask;
316 if (expanded) return true;
317 }
318 const offset = comma orelse return false;
319 const fallback_start = start + @as(u32, @intCast(offset)) + 1;
320 return self.expandSpan(fallback_start, end, depth + 1, visiting);
321 }
322
323 fn lookupCustom(self: *const Resolver, name: []const u8) ?usize {
324 const table = self.names orelse return null;
325 const id = table.lookup(name);
326 if (id == atom.none) return null;
327 if (self.customs.count > max_custom_properties) return null;
328 return self.customs.find(id);
329 }
330
331 fn write(self: *Resolver, text: []const u8) bool {
332 if (self.used + text.len > self.buffer.len) return false;
333 @memcpy(self.buffer[self.used..][0..text.len], text);
334 self.used += @intCast(text.len);
335 return true;
336 }
337 };
338
339 fn wins(candidate: Slot, existing: Slot) bool {
340 return switch (candidate.specificity.compare(existing.specificity)) {
341 .gt => true,
342 .lt => false,
343 .eq => candidate.order >= existing.order,
344 };
345 }
346
347 fn customWins(candidate: CustomSlot, existing: CustomSlot) bool {
348 if (candidate.level != existing.level) {
349 return @backingInt(candidate.level) > @backingInt(existing.level);
350 }
351 return switch (candidate.specificity.compare(existing.specificity)) {
352 .gt => true,
353 .lt => false,
354 .eq => candidate.order >= existing.order,
355 };
356 }
357
358 /// The cascade level a declaration lands in.
359 pub fn levelOf(origin: Origin, important: bool) Level {
360 return switch (origin) {
361 .user_agent => if (important) .user_agent_important else .user_agent_normal,
362 .user => if (important) .user_important else .user_normal,
363 .author => if (important) .author_important else .author_normal,
364 };
365 }
366
367 fn originBit(origin: Origin) u8 {
368 return @as(u8, 1) << @as(u3, @intCast(@backingInt(origin)));
369 }
370
371 /// The origin behind a cascade level.
372 pub fn originOf(level: Level) Origin {
373 return switch (level) {
374 .user_agent_normal, .user_agent_important => .user_agent,
375 .user_normal, .user_important => .user,
376 .author_normal, .author_important => .author,
377 };
378 }
379
380 fn closeParen(tokenizer: *token.Tokenizer, limit: usize) ?u32 {
381 var depth: u32 = 1;
382 var guard: usize = 0;
383 while (guard <= limit + 1) : (guard += 1) {
384 const next = tokenizer.next();
385 switch (next.kind) {
386 .eof => return null,
387 .function, .left_paren => depth += 1,
388 .right_paren => {
389 depth -= 1;
390 if (depth == 0) return next.start;
391 },
392 else => {},
393 }
394 }
395 return null;
396 }
397
398 fn topLevelComma(body: []const u8) ?usize {
399 var depth: u32 = 0;
400 for (body, 0..) |byte, index| {
401 switch (byte) {
402 '(' => depth += 1,
403 ')' => depth -|= 1,
404 ',' => if (depth == 0) return index,
405 else => {},
406 }
407 }
408 return null;
409 }
410
411 fn colored(red: u8, green: u8, blue: u8) Value {
412 return Value.color(value.color.pack(red, green, blue, 255));
413 }
414
415 test "importance inverts the cascade origin order" {
416 var resolver: Resolver = .{};
417 resolver.begin("", null, null);
418 const id = @backingInt(property.Id.color);
419 resolver.add(colored(255, 0, 0).declare(id, false), .author, .{ .ids = 9 }, 10);
420 resolver.add(colored(0, 0, 255).declare(id, true), .user_agent, .{}, 0);
421 var out: Computed = .{};
422 resolver.finish(null, &out);
423 try std.testing.expectEqual(colored(0, 0, 255).a, out.get(.color).a);
424
425 resolver.begin("", null, null);
426 resolver.add(colored(255, 0, 0).declare(id, true), .author, .{}, 0);
427 resolver.add(colored(0, 0, 255).declare(id, false), .user_agent, .{ .ids = 9 }, 10);
428 resolver.finish(null, &out);
429 try std.testing.expectEqual(colored(255, 0, 0).a, out.get(.color).a);
430 }
431
432 test "specificity settles a level before source order does" {
433 var resolver: Resolver = .{};
434 resolver.begin("", null, null);
435 const id = @backingInt(property.Id.width);
436 resolver.add(Value.length(1, .px).declare(id, false), .author, .{ .classes = 1 }, 0);
437 resolver.add(Value.length(2, .px).declare(id, false), .author, .{ .types = 1 }, 5);
438 var out: Computed = .{};
439 resolver.finish(null, &out);
440 try std.testing.expectEqual(@as(f32, 1), out.get(.width).asNumber());
441
442 resolver.add(Value.length(3, .px).declare(id, false), .author, .{ .classes = 1 }, 9);
443 resolver.finish(null, &out);
444 try std.testing.expectEqual(@as(f32, 3), out.get(.width).asNumber());
445 }
446
447 test "an undeclared property inherits or takes its initial value" {
448 var parent = Computed.initial();
449 parent.set(.color, colored(17, 34, 51));
450 parent.set(.width, Value.length(7, .px));
451 var resolver: Resolver = .{};
452 resolver.begin("", null, null);
453 var out: Computed = .{};
454 resolver.finish(&parent, &out);
455 try std.testing.expectEqual(colored(17, 34, 51).a, out.get(.color).a);
456 try std.testing.expectEqual(property.metadata(.width).initial.a, out.get(.width).a);
457 }
458
459 test "the four wide keywords resolve against the parent and the initial value" {
460 var parent = Computed.initial();
461 parent.set(.color, colored(17, 34, 51));
462 parent.set(.width, Value.length(7, .px));
463 const color_id = @backingInt(property.Id.color);
464 const width_id = @backingInt(property.Id.width);
465 var out: Computed = .{};
466 var resolver: Resolver = .{};
467
468 resolver.begin("", null, null);
469 resolver.add(Value.keyword(.inherit).declare(width_id, false), .author, .{}, 0);
470 resolver.finish(&parent, &out);
471 try std.testing.expectEqual(@as(f32, 7), out.get(.width).asNumber());
472
473 resolver.begin("", null, null);
474 resolver.add(Value.keyword(.unset).declare(width_id, false), .author, .{}, 0);
475 resolver.add(Value.keyword(.unset).declare(color_id, false), .author, .{}, 1);
476 resolver.finish(&parent, &out);
477 try std.testing.expectEqual(property.metadata(.width).initial.a, out.get(.width).a);
478 try std.testing.expectEqual(colored(17, 34, 51).a, out.get(.color).a);
479
480 resolver.begin("", null, null);
481 resolver.add(Value.keyword(.initial).declare(color_id, false), .author, .{}, 0);
482 resolver.finish(&parent, &out);
483 try std.testing.expectEqual(property.metadata(.color).initial.a, out.get(.color).a);
484 }
485
486 test "revert drops its own origin and re-picks the level below" {
487 var resolver: Resolver = .{};
488 resolver.begin("", null, null);
489 const id = @backingInt(property.Id.color);
490 resolver.add(colored(255, 0, 0).declare(id, false), .user_agent, .{}, 0);
491 resolver.add(colored(0, 255, 0).declare(id, false), .author, .{ .classes = 1 }, 1);
492 resolver.add(Value.keyword(.revert).declare(id, false), .author, .{ .ids = 1 }, 2);
493 var out: Computed = .{};
494 resolver.finish(null, &out);
495 try std.testing.expectEqual(colored(255, 0, 0).a, out.get(.color).a);
496 }
497
498 test "a custom property table rejects past its capacity without evicting" {
499 var table = CustomTable{};
500 var index: u32 = 0;
501 while (index < max_custom_properties) : (index += 1) {
502 table.slots[index] = .{ .name = index + 1 };
503 table.count += 1;
504 }
505 try std.testing.expectEqual(@as(?usize, 0), table.find(1));
506 try std.testing.expectEqual(@as(?usize, null), table.find(max_custom_properties + 1));
507 }