lib/css/src/match/engine.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const selector = @import("../selector/root.zig");
4
5 const Compound = selector.Compound;
6 const Selector = selector.Selector;
7 const Specificity = selector.Specificity;
8
9 /// The deepest ancestor chain a combinator walk crosses. It is the depth bound
10 /// the layout solver already declares, so a descendant match is bounded work.
11 pub const max_depth: u32 = 64;
12
13 /// The most compounds one selector may carry.
14 pub const max_compounds: usize = 32;
15
16 /// The most classes one element may report to a compound test.
17 pub const max_element_classes: u32 = 64;
18
19 /// The tree interface the matcher runs against. `ui` and `browser` fill it
20 /// over their own node storage, which is how one matcher serves both.
21 ///
22 /// `parent` and `previous` return the node's own index when it has no parent
23 /// or no preceding sibling. `sibling_index` packs the one based index in the
24 /// low sixteen bits and the sibling count in the high sixteen, because
25 /// `:nth-last-child` needs the count and the call returns one word.
26 ///
27 /// `classes` writes at most `capacity` atoms and returns how many the element
28 /// has. Reporting more than `capacity` is a programmer error and is asserted.
29 pub const Element = extern struct {
30 context: ?*anyopaque,
31 parent: *const fn (?*anyopaque, u32) callconv(.c) u32,
32 previous: *const fn (?*anyopaque, u32) callconv(.c) u32,
33 kind: *const fn (?*anyopaque, u32) callconv(.c) u16,
34 role: *const fn (?*anyopaque, u32) callconv(.c) u16,
35 identifier: *const fn (?*anyopaque, u32) callconv(.c) u32,
36 classes: *const fn (?*anyopaque, u32, [*]u32, u32) callconv(.c) u32,
37 pseudo: *const fn (?*anyopaque, u32) callconv(.c) u32,
38 sibling_index: *const fn (?*anyopaque, u32, bool) callconv(.c) u32,
39 };
40
41 /// The sheet side tables a compound test reads.
42 pub const Context = struct {
43 classes: []const u32,
44 nths: []const selector.nth.Nth,
45 };
46
47 /// One selector that matched an element, carried to the cascade.
48 pub const Match = struct {
49 rule: u32,
50 selector: u32,
51 specificity: Specificity,
52 order: u32,
53 };
54
55 /// Packs a one based sibling index and a sibling count into one word.
56 pub fn packSibling(index: u32, count: u32) u32 {
57 std.debug.assert(index <= 0xFFFF);
58 std.debug.assert(count <= 0xFFFF);
59 return (count << 16) | index;
60 }
61
62 /// The one based sibling index inside a packed sibling word.
63 pub fn siblingIndex(word: u32) u32 {
64 return word & 0xFFFF;
65 }
66
67 /// The sibling count inside a packed sibling word.
68 pub fn siblingCount(word: u32) u32 {
69 return word >> 16;
70 }
71
72 /// Whether `item` matches `node`. The rightmost compound is tested first, then
73 /// the chain walks leftwards with backtracking at the two loose combinators.
74 pub fn matches(context: Context, item: Selector, element: Element, node: u32) bool {
75 std.debug.assert(item.compounds.len > 0);
76 std.debug.assert(item.compounds.len <= max_compounds);
77 std.debug.assert(item.combinators.len + 1 == item.compounds.len);
78 if (!matchCompound(context, item.rightmost(), element, node)) return false;
79 return matchChain(context, item, element, node);
80 }
81
82 fn matchChain(context: Context, item: Selector, element: Element, node: u32) bool {
83 const total = item.compounds.len;
84 if (total == 1) return true;
85 var chosen: [max_compounds]u32 = undefined;
86 var tried: [max_compounds]u32 = undefined;
87 chosen[total - 1] = node;
88 var level: usize = total - 1;
89 var advance = true;
90 var guard: usize = 0;
91 const limit = max_compounds * max_depth * 2;
92 while (guard <= limit) : (guard += 1) {
93 if (level == 0) return true;
94 const joint = item.combinators[level - 1];
95 const compound = item.compounds[level - 1];
96 var probe = if (advance) first(element, joint, chosen[level]) else next(element, joint, tried[level - 1]);
97 var found = false;
98 var steps: u32 = 0;
99 while (probe) |candidate| {
100 if (steps > max_depth) break;
101 tried[level - 1] = candidate;
102 if (matchCompound(context, compound, element, candidate)) {
103 found = true;
104 break;
105 }
106 probe = next(element, joint, candidate);
107 steps += 1;
108 }
109 if (found) {
110 chosen[level - 1] = tried[level - 1];
111 level -= 1;
112 advance = true;
113 continue;
114 }
115 if (level + 1 > total - 1) return false;
116 level += 1;
117 advance = false;
118 }
119 unreachable;
120 }
121
122 fn first(element: Element, joint: selector.Combinator, from: u32) ?u32 {
123 return switch (joint) {
124 .descendant, .child => step(element.parent, element.context, from),
125 .next_sibling, .subsequent_sibling => step(element.previous, element.context, from),
126 };
127 }
128
129 fn next(element: Element, joint: selector.Combinator, from: u32) ?u32 {
130 return switch (joint) {
131 .descendant => step(element.parent, element.context, from),
132 .subsequent_sibling => step(element.previous, element.context, from),
133 .child, .next_sibling => null,
134 };
135 }
136
137 fn step(
138 accessor: *const fn (?*anyopaque, u32) callconv(.c) u32,
139 context: ?*anyopaque,
140 from: u32,
141 ) ?u32 {
142 const found = accessor(context, from);
143 if (found == from) return null;
144 return found;
145 }
146
147 /// Whether one compound matches one node.
148 pub fn matchCompound(
149 context: Context,
150 compound: Compound,
151 element: Element,
152 node: u32,
153 ) bool {
154 if (compound.flags & selector.unmatchable != 0) return false;
155 if (compound.kind != 0 and element.kind(element.context, node) != compound.kind) return false;
156 if (compound.role != 0 and element.role(element.context, node) != compound.role) return false;
157 if (compound.id != 0 and element.identifier(element.context, node) != compound.id) return false;
158 if (compound.pseudo != 0) {
159 const state = element.pseudo(element.context, node);
160 if (state & compound.pseudo != compound.pseudo) return false;
161 }
162 if (compound.class_count > 0 and !matchClasses(context, compound, element, node)) return false;
163 if (compound.nth != 0 and !matchNth(context, compound.nth, element, node)) return false;
164 return true;
165 }
166
167 fn matchClasses(context: Context, compound: Compound, element: Element, node: u32) bool {
168 var held: [max_element_classes]u32 = undefined;
169 const count = element.classes(element.context, node, &held, max_element_classes);
170 std.debug.assert(count <= max_element_classes);
171 const wanted = context.classes[compound.class_first..][0..compound.class_count];
172 for (wanted) |class| {
173 var found = false;
174 for (held[0..count]) |candidate| {
175 if (candidate == class) {
176 found = true;
177 break;
178 }
179 }
180 if (!found) return false;
181 }
182 return true;
183 }
184
185 fn matchNth(context: Context, head: u32, element: Element, node: u32) bool {
186 var walk = head;
187 var guard: usize = 0;
188 while (walk != 0 and guard <= context.nths.len) : (guard += 1) {
189 const record = context.nths[walk - 1];
190 const of_type = record.kind == .of_type or record.kind == .last_of_type;
191 const word = element.sibling_index(element.context, node, of_type);
192 const index = siblingIndex(word);
193 if (index == 0) return false;
194 const count = siblingCount(word);
195 if (!selector.nth.matches(.{ .a = record.a, .b = record.b }, index, count, record.kind)) {
196 return false;
197 }
198 walk = record.next;
199 }
200 return true;
201 }