lib/css/src/atom.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! Interned identifier atoms.
2 //!
3 //! Selector compounds hold `u32` atom ids rather than byte slices so that
4 //! matching an id, a class, a type name, or a role is an integer compare. Id
5 //! zero means absent, so a compound field left unset matches any element.
6 //!
7 //! One table serves every identifier position. Ids and classes intern with
8 //! their authored case. Type names and role names intern ASCII folded, which
9 //! is what lets a consumer resolve its own closed enum once per stylesheet
10 //! through `StyleSheet.token` instead of comparing strings per element.
11 //!
12 //! Atom text borrows the caller's source bytes whenever the identifier carries
13 //! no escape and no case fold. The `arena` holds only the decoded or folded
14 //! copies, so the usual stylesheet leaves it empty.
15 //!
16 //! Capacity is bounded at `max_atoms` so that an atom id narrows to the `u16`
17 //! that `Compound.kind` and `Compound.role` declare.
18
19 const std = @import("std");
20
21 /// The absent atom. No interned identifier ever takes this id.
22 pub const none: u32 = 0;
23
24 /// The largest number of distinct atoms one stylesheet may intern.
25 pub const max_atoms: u32 = 65_535;
26
27 /// The largest identifier this engine interns, in bytes.
28 pub const max_text_bytes: usize = 255;
29
30 /// One interned identifier and the hash that placed it.
31 pub const Record = struct {
32 text: []const u8,
33 hash: u32,
34 };
35
36 /// The open addressed interning table. `records`, `slots`, and `arena` are
37 /// placement owned, so the table allocates nothing.
38 pub const Table = struct {
39 records: []Record,
40 slots: []u32,
41 arena: []u8,
42 count: u32 = 0,
43 arena_used: u32 = 0,
44
45 /// Empties the table without releasing its placement storage.
46 pub fn reset(self: *Table) void {
47 @memset(self.slots, 0);
48 self.count = 0;
49 self.arena_used = 0;
50 }
51
52 /// Returns the id of `text`, or `none` when the table has never seen it.
53 pub fn lookup(self: *const Table, text: []const u8) u32 {
54 if (self.slots.len != 0) std.debug.assert(std.math.isPowerOfTwo(self.slots.len));
55 if (text.len == 0 or text.len > max_text_bytes or self.slots.len == 0) return none;
56 const digest = hash(text);
57 const mask = self.slots.len - 1;
58 var probe: usize = 0;
59 var index = @as(usize, digest) & mask;
60 while (probe < self.slots.len) : (probe += 1) {
61 const slot = self.slots[index];
62 if (slot == none) return none;
63 const record = self.records[slot - 1];
64 if (record.hash == digest and std.mem.eql(u8, record.text, text)) return slot;
65 index = (index + 1) & mask;
66 }
67 return none;
68 }
69
70 /// Interns `text` and returns its id. `copy` moves the bytes into the
71 /// arena, which a caller passing a folded or unescaped stack buffer must
72 /// request. Admission is asserted, never grown.
73 pub fn intern(self: *Table, text: []const u8, copy: bool) u32 {
74 std.debug.assert(text.len > 0);
75 std.debug.assert(text.len <= max_text_bytes);
76 std.debug.assert(self.slots.len > 0);
77 const existing = self.lookup(text);
78 if (existing != none) return existing;
79 std.debug.assert(self.count < self.records.len);
80 std.debug.assert(self.count < max_atoms);
81 const stored = if (copy) self.store(text) else text;
82 const digest = hash(stored);
83 self.records[self.count] = .{ .text = stored, .hash = digest };
84 self.count += 1;
85 self.place(digest, self.count);
86 return self.count;
87 }
88
89 /// The text behind `id`. Asserts that the id was interned by this table.
90 pub fn name(self: *const Table, id: u32) []const u8 {
91 std.debug.assert(id != none);
92 std.debug.assert(id <= self.count);
93 return self.records[id - 1].text;
94 }
95
96 fn store(self: *Table, source: []const u8) []const u8 {
97 const start = self.arena_used;
98 std.debug.assert(start + source.len <= self.arena.len);
99 @memcpy(self.arena[start..][0..source.len], source);
100 self.arena_used = start + @as(u32, @intCast(source.len));
101 return self.arena[start..][0..source.len];
102 }
103
104 fn place(self: *Table, digest: u32, id: u32) void {
105 const mask = self.slots.len - 1;
106 var probe: usize = 0;
107 var index = @as(usize, digest) & mask;
108 while (probe < self.slots.len) : (probe += 1) {
109 if (self.slots[index] == none) {
110 self.slots[index] = id;
111 return;
112 }
113 index = (index + 1) & mask;
114 }
115 unreachable;
116 }
117 };
118
119 /// The FNV-1a digest the table probes with.
120 pub fn hash(text: []const u8) u32 {
121 var digest: u32 = 2_166_136_261;
122 for (text) |byte| {
123 digest ^= byte;
124 digest *%= 16_777_619;
125 }
126 return digest;
127 }
128
129 /// The power of two slot count that keeps the table under a half load.
130 pub fn slotCount(atoms: usize) usize {
131 if (atoms == 0) return 0;
132 const wanted = std.math.mul(usize, atoms, 2) catch return 0;
133 return std.math.ceilPowerOfTwo(usize, wanted) catch 0;
134 }
135
136 /// ASCII folds `text` into `buffer`, borrowing `text` when it is already
137 /// folded. Returns null when the identifier exceeds `max_text_bytes`.
138 pub fn fold(text: []const u8, buffer: []u8) ?[]const u8 {
139 if (text.len == 0 or text.len > max_text_bytes) return null;
140 std.debug.assert(buffer.len >= max_text_bytes);
141 var upper = false;
142 for (text) |byte| {
143 if (byte >= 'A' and byte <= 'Z') {
144 upper = true;
145 break;
146 }
147 }
148 if (!upper) return text;
149 for (text, 0..) |byte, index| buffer[index] = std.ascii.toLower(byte);
150 return buffer[0..text.len];
151 }
152
153 const TestTable = struct {
154 records: [16]Record = undefined,
155 slots: [32]u32 = @splat(0),
156 arena: [256]u8 = undefined,
157
158 fn table(self: *TestTable) Table {
159 return .{ .records = &self.records, .slots = &self.slots, .arena = &self.arena };
160 }
161 };
162
163 test "an interned identifier keeps one id across repeated interning" {
164 var storage = TestTable{};
165 var table = storage.table();
166 const first = table.intern("primary", false);
167 const second = table.intern("primary", false);
168 try std.testing.expectEqual(first, second);
169 try std.testing.expectEqual(@as(u32, 1), first);
170 try std.testing.expectEqual(@as(u32, 1), table.count);
171 try std.testing.expectEqualStrings("primary", table.name(first));
172 }
173
174 test "a distinct identifier takes the next id and lookup finds both" {
175 var storage = TestTable{};
176 var table = storage.table();
177 const first = table.intern("save", false);
178 const second = table.intern("cancel", false);
179 try std.testing.expectEqual(@as(u32, 2), second);
180 try std.testing.expectEqual(first, table.lookup("save"));
181 try std.testing.expectEqual(second, table.lookup("cancel"));
182 try std.testing.expectEqual(none, table.lookup("missing"));
183 }
184
185 test "a copied identifier lives in the arena and leaves the source" {
186 var storage = TestTable{};
187 var table = storage.table();
188 var buffer: [max_text_bytes]u8 = undefined;
189 const folded = fold("Button", &buffer).?;
190 const id = table.intern(folded, true);
191 try std.testing.expectEqualStrings("button", table.name(id));
192 try std.testing.expectEqual(@as(u32, 6), table.arena_used);
193 try std.testing.expectEqual(id, table.lookup("button"));
194 }
195
196 test "folding borrows an already folded identifier" {
197 var buffer: [max_text_bytes]u8 = undefined;
198 const borrowed = fold("button", &buffer).?;
199 try std.testing.expectEqual(@as(usize, 6), borrowed.len);
200 try std.testing.expect(borrowed.ptr != &buffer);
201 try std.testing.expect(fold("", &buffer) == null);
202 }
203
204 test "the slot count stays a power of two above twice the atom count" {
205 try std.testing.expectEqual(@as(usize, 0), slotCount(0));
206 try std.testing.expectEqual(@as(usize, 2), slotCount(1));
207 try std.testing.expectEqual(@as(usize, 8), slotCount(4));
208 try std.testing.expectEqual(@as(usize, 16), slotCount(5));
209 }
210
211 test "a table reset clears every slot and keeps its storage" {
212 var storage = TestTable{};
213 var table = storage.table();
214 _ = table.intern("alpha", false);
215 table.reset();
216 try std.testing.expectEqual(@as(u32, 0), table.count);
217 try std.testing.expectEqual(none, table.lookup("alpha"));
218 try std.testing.expectEqual(@as(u32, 1), table.intern("beta", false));
219 }