lib/css/src/match/fixture/tree.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! A small element tree that fills the matcher's element interface.
2 //!
3 //! Nodes are written as compound selector text, so a conformance case reads as
4 //! the markup it stands for. The tree is fixed size and allocates nothing.
5
6 const std = @import("std");
7
8 const atom = @import("../../atom.zig");
9 const engine = @import("../engine.zig");
10 const selector = @import("../../selector/root.zig");
11 const token = @import("../../token/root.zig");
12
13 /// The most nodes one fixture tree holds.
14 pub const max_nodes: u32 = 128;
15
16 /// The most class atoms one fixture tree holds.
17 pub const max_classes: u32 = 256;
18
19 /// One element. Sibling positions are derived by `finish`.
20 pub const Node = struct {
21 parent: u32 = 0,
22 previous: u32 = 0,
23 depth: u32 = 0,
24 kind: u16 = 0,
25 role: u16 = 0,
26 identifier: u32 = 0,
27 class_first: u32 = 0,
28 class_count: u32 = 0,
29 pseudo: u32 = 0,
30 index: u32 = 1,
31 count: u32 = 1,
32 type_index: u32 = 1,
33 type_count: u32 = 1,
34 };
35
36 /// The tree and the atom table its identifiers intern into.
37 pub const Tree = struct {
38 nodes: [max_nodes]Node = @splat(.{}),
39 classes: [max_classes]u32 = @splat(0),
40 node_count: u32 = 0,
41 class_count: u32 = 0,
42
43 /// Appends one node written as `tag#id.class:pseudo@role` at `depth`.
44 pub fn add(self: *Tree, table: *atom.Table, depth: u32, spec: []const u8) !u32 {
45 if (self.node_count == max_nodes) return error.TreeFull;
46 const index = self.node_count;
47 var node = Node{ .depth = depth, .parent = index, .previous = index };
48 if (depth > 0) node.parent = try self.ancestorAt(depth - 1);
49 node.previous = self.lastSibling(node.parent, depth, index);
50 node.class_first = self.class_count;
51 try self.readSpec(table, &node, spec);
52 node.class_count = self.class_count - node.class_first;
53 self.nodes[index] = node;
54 self.node_count += 1;
55 return index;
56 }
57
58 /// Derives every sibling index and count. Call once after the last `add`.
59 pub fn finish(self: *Tree) void {
60 var index: u32 = 0;
61 while (index < self.node_count) : (index += 1) {
62 const node = self.nodes[index];
63 var position: u32 = 0;
64 var total: u32 = 0;
65 var type_position: u32 = 0;
66 var type_total: u32 = 0;
67 var scan: u32 = 0;
68 while (scan < self.node_count) : (scan += 1) {
69 if (self.parentKey(index) != self.parentKey(scan)) continue;
70 total += 1;
71 if (scan <= index) position = total;
72 if (self.nodes[scan].kind != node.kind) continue;
73 type_total += 1;
74 if (scan <= index) type_position = type_total;
75 }
76 self.nodes[index].index = position;
77 self.nodes[index].count = total;
78 self.nodes[index].type_index = type_position;
79 self.nodes[index].type_count = type_total;
80 }
81 }
82
83 fn parentKey(self: *const Tree, index: u32) u32 {
84 const node = self.nodes[index];
85 if (node.parent == index) return max_nodes;
86 return node.parent;
87 }
88
89 /// The matcher interface over this tree.
90 pub fn element(self: *Tree) engine.Element {
91 return .{
92 .context = self,
93 .parent = parentOf,
94 .previous = previousOf,
95 .kind = kindOf,
96 .role = roleOf,
97 .identifier = identifierOf,
98 .classes = classesOf,
99 .pseudo = pseudoOf,
100 .sibling_index = siblingOf,
101 };
102 }
103
104 fn ancestorAt(self: *Tree, depth: u32) !u32 {
105 var index = self.node_count;
106 while (index > 0) {
107 index -= 1;
108 if (self.nodes[index].depth == depth) return index;
109 }
110 return error.MissingParent;
111 }
112
113 fn lastSibling(self: *Tree, parent: u32, depth: u32, own: u32) u32 {
114 if (depth == 0) return own;
115 var index = self.node_count;
116 while (index > 0) {
117 index -= 1;
118 if (self.nodes[index].depth == depth and self.nodes[index].parent == parent) return index;
119 }
120 return own;
121 }
122
123 fn readSpec(self: *Tree, table: *atom.Table, node: *Node, spec: []const u8) !void {
124 var cursor: u32 = 0;
125 var guard: usize = 0;
126 while (cursor < spec.len and guard <= spec.len) : (guard += 1) {
127 const byte = spec[cursor];
128 const start = if (byte == '#' or byte == '.' or byte == ':' or byte == '@')
129 cursor + 1
130 else
131 cursor;
132 const stop = token.consumeIdent(spec, start);
133 if (stop == start) return error.BadSpec;
134 const text = spec[start..stop];
135 cursor = stop;
136 try self.apply(table, node, byte, text);
137 }
138 }
139
140 fn apply(self: *Tree, table: *atom.Table, node: *Node, sigil: u8, text: []const u8) !void {
141 switch (sigil) {
142 '#' => node.identifier = table.intern(text, false),
143 '.' => {
144 if (self.class_count == max_classes) return error.TreeFull;
145 self.classes[self.class_count] = table.intern(text, false);
146 self.class_count += 1;
147 },
148 ':' => {
149 const class = selector.pseudoByName(text) orelse return error.BadSpec;
150 node.pseudo |= selector.bit(class);
151 },
152 '@' => node.role = @intCast(try folded(table, text)),
153 else => node.kind = @intCast(try folded(table, text)),
154 }
155 }
156
157 fn folded(table: *atom.Table, text: []const u8) !u32 {
158 var buffer: [atom.max_text_bytes]u8 = undefined;
159 const lowered = atom.fold(text, &buffer) orelse return error.BadSpec;
160 return table.intern(lowered, lowered.ptr != text.ptr);
161 }
162 };
163
164 fn treeOf(context: ?*anyopaque) *Tree {
165 return @ptrCast(@alignCast(context.?));
166 }
167
168 fn parentOf(context: ?*anyopaque, node: u32) callconv(.c) u32 {
169 return treeOf(context).nodes[node].parent;
170 }
171
172 fn previousOf(context: ?*anyopaque, node: u32) callconv(.c) u32 {
173 return treeOf(context).nodes[node].previous;
174 }
175
176 fn kindOf(context: ?*anyopaque, node: u32) callconv(.c) u16 {
177 return treeOf(context).nodes[node].kind;
178 }
179
180 fn roleOf(context: ?*anyopaque, node: u32) callconv(.c) u16 {
181 return treeOf(context).nodes[node].role;
182 }
183
184 fn identifierOf(context: ?*anyopaque, node: u32) callconv(.c) u32 {
185 return treeOf(context).nodes[node].identifier;
186 }
187
188 fn classesOf(context: ?*anyopaque, node: u32, out: [*]u32, capacity: u32) callconv(.c) u32 {
189 const tree = treeOf(context);
190 const record = tree.nodes[node];
191 const count = @min(record.class_count, capacity);
192 var index: u32 = 0;
193 while (index < count) : (index += 1) out[index] = tree.classes[record.class_first + index];
194 return record.class_count;
195 }
196
197 fn pseudoOf(context: ?*anyopaque, node: u32) callconv(.c) u32 {
198 return treeOf(context).nodes[node].pseudo;
199 }
200
201 fn siblingOf(context: ?*anyopaque, node: u32, of_type: bool) callconv(.c) u32 {
202 const record = treeOf(context).nodes[node];
203 if (of_type) return engine.packSibling(record.type_index, record.type_count);
204 return engine.packSibling(record.index, record.count);
205 }