lib/css/src/token/scan.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 /// The token kinds CSS Syntax Level 3 section 4 produces. Comments are
4 /// consumed rather than emitted, which is what the parsing algorithms expect.
5 pub const Kind = enum(u8) {
6 eof,
7 whitespace,
8 ident,
9 function,
10 at_keyword,
11 hash,
12 string,
13 bad_string,
14 url,
15 bad_url,
16 delim,
17 number,
18 percentage,
19 dimension,
20 cdo,
21 cdc,
22 colon,
23 semicolon,
24 comma,
25 left_square,
26 right_square,
27 left_paren,
28 right_paren,
29 left_curly,
30 right_curly,
31 };
32
33 /// Whether a hash token could name an identifier, which decides whether `#a`
34 /// is an id selector or a hex color.
35 pub const HashKind = enum(u8) {
36 unrestricted,
37 id,
38 };
39
40 /// Whether a numeric token was written without a fraction or an exponent.
41 pub const NumericKind = enum(u8) {
42 integer,
43 number,
44 };
45
46 /// One token as a span over the caller's source bytes. `value` narrows to the
47 /// part a consumer reads: an identifier without its sigil, a string without
48 /// its quotes, a dimension without its unit.
49 pub const Token = struct {
50 kind: Kind,
51 start: u32,
52 end: u32,
53 value_start: u32,
54 value_end: u32,
55 unit_start: u32 = 0,
56 unit_end: u32 = 0,
57 number: f64 = 0,
58 numeric: NumericKind = .integer,
59 hash_kind: HashKind = .unrestricted,
60 escaped: bool = false,
61
62 /// The whole token including any sigil, quotes, or unit.
63 pub fn text(self: Token, source: []const u8) []const u8 {
64 return source[self.start..self.end];
65 }
66
67 /// The consumer facing span described above.
68 pub fn value(self: Token, source: []const u8) []const u8 {
69 return source[self.value_start..self.value_end];
70 }
71
72 /// The dimension unit, empty for every other kind.
73 pub fn unit(self: Token, source: []const u8) []const u8 {
74 return source[self.unit_start..self.unit_end];
75 }
76 };
77
78 /// A forward tokenizer over borrowed source bytes. It allocates nothing and
79 /// every `next` either advances `index` or returns `eof`.
80 pub const Tokenizer = struct {
81 source: []const u8,
82 index: u32 = 0,
83
84 pub fn init(source: []const u8) Tokenizer {
85 std.debug.assert(source.len <= std.math.maxInt(u32));
86 return .{ .source = source };
87 }
88
89 /// Consumes and returns the next token.
90 pub fn next(self: *Tokenizer) Token {
91 self.skipComments();
92 const start = self.index;
93 if (start >= self.source.len) return self.single(.eof, start);
94 const byte = self.source[start];
95 if (isWhitespace(byte)) return self.whitespace(start);
96 if (byte == '"' or byte == '\'') return self.string(start, byte);
97 if (byte == '#') return self.hash(start);
98 if (byte == '+' or byte == '.') {
99 if (startsNumber(self.source, start)) return self.numeric(start);
100 return self.delim(start);
101 }
102 if (byte == '-') return self.minus(start);
103 if (byte == '<') return self.lessThan(start);
104 if (byte == '@') return self.atKeyword(start);
105 if (byte == '\\') {
106 if (validEscape(self.source, start)) return self.identLike(start);
107 return self.delim(start);
108 }
109 if (isDigit(byte)) return self.numeric(start);
110 if (isIdentStart(byte)) return self.identLike(start);
111 if (punctuation(byte)) |kind| return self.single(kind, start);
112 return self.delim(start);
113 }
114
115 fn skipComments(self: *Tokenizer) void {
116 var guard: usize = 0;
117 while (guard <= self.source.len) : (guard += 1) {
118 const index = self.index;
119 if (index + 1 >= self.source.len) return;
120 if (self.source[index] != '/' or self.source[index + 1] != '*') return;
121 const rest = self.source[index + 2 ..];
122 const close = std.mem.indexOf(u8, rest, "*/") orelse {
123 self.index = @intCast(self.source.len);
124 return;
125 };
126 self.index = index + 2 + @as(u32, @intCast(close)) + 2;
127 }
128 unreachable;
129 }
130
131 fn single(self: *Tokenizer, kind: Kind, start: u32) Token {
132 const end = if (kind == .eof) start else start + 1;
133 self.index = end;
134 return .{ .kind = kind, .start = start, .end = end, .value_start = start, .value_end = end };
135 }
136
137 fn delim(self: *Tokenizer, start: u32) Token {
138 return self.single(.delim, start);
139 }
140
141 fn whitespace(self: *Tokenizer, start: u32) Token {
142 var index = start;
143 while (index < self.source.len and isWhitespace(self.source[index])) index += 1;
144 self.index = index;
145 return .{
146 .kind = .whitespace,
147 .start = start,
148 .end = index,
149 .value_start = start,
150 .value_end = index,
151 };
152 }
153
154 fn hash(self: *Tokenizer, start: u32) Token {
155 const after = start + 1;
156 if (after < self.source.len and
157 (isIdent(self.source[after]) or validEscape(self.source, after)))
158 {
159 const kind: HashKind = if (startsIdent(self.source, after)) .id else .unrestricted;
160 const end = consumeIdent(self.source, after);
161 self.index = end;
162 return .{
163 .kind = .hash,
164 .start = start,
165 .end = end,
166 .value_start = after,
167 .value_end = end,
168 .hash_kind = kind,
169 .escaped = hasEscape(self.source[after..end]),
170 };
171 }
172 return self.delim(start);
173 }
174
175 fn minus(self: *Tokenizer, start: u32) Token {
176 if (startsNumber(self.source, start)) return self.numeric(start);
177 if (start + 2 < self.source.len and std.mem.eql(u8, self.source[start..][0..3], "-->")) {
178 self.index = start + 3;
179 return .{
180 .kind = .cdc,
181 .start = start,
182 .end = start + 3,
183 .value_start = start,
184 .value_end = start + 3,
185 };
186 }
187 if (startsIdent(self.source, start)) return self.identLike(start);
188 return self.delim(start);
189 }
190
191 fn lessThan(self: *Tokenizer, start: u32) Token {
192 if (start + 3 < self.source.len and std.mem.eql(u8, self.source[start..][0..4], "<!--")) {
193 self.index = start + 4;
194 return .{
195 .kind = .cdo,
196 .start = start,
197 .end = start + 4,
198 .value_start = start,
199 .value_end = start + 4,
200 };
201 }
202 return self.delim(start);
203 }
204
205 fn atKeyword(self: *Tokenizer, start: u32) Token {
206 const after = start + 1;
207 if (!startsIdent(self.source, after)) return self.delim(start);
208 const end = consumeIdent(self.source, after);
209 self.index = end;
210 return .{
211 .kind = .at_keyword,
212 .start = start,
213 .end = end,
214 .value_start = after,
215 .value_end = end,
216 .escaped = hasEscape(self.source[after..end]),
217 };
218 }
219
220 fn identLike(self: *Tokenizer, start: u32) Token {
221 const end = consumeIdent(self.source, start);
222 const name = self.source[start..end];
223 if (end < self.source.len and self.source[end] == '(') {
224 if (std.ascii.eqlIgnoreCase(name, "url") and !quotedUrl(self.source, end + 1)) {
225 return self.url(start, end + 1);
226 }
227 self.index = end + 1;
228 return .{
229 .kind = .function,
230 .start = start,
231 .end = end + 1,
232 .value_start = start,
233 .value_end = end,
234 .escaped = hasEscape(name),
235 };
236 }
237 self.index = end;
238 return .{
239 .kind = .ident,
240 .start = start,
241 .end = end,
242 .value_start = start,
243 .value_end = end,
244 .escaped = hasEscape(name),
245 };
246 }
247
248 fn url(self: *Tokenizer, start: u32, body: u32) Token {
249 var index = body;
250 while (index < self.source.len and isWhitespace(self.source[index])) index += 1;
251 const value_start = index;
252 while (index < self.source.len and self.source[index] != ')') {
253 if (self.source[index] == '\\' and index + 1 < self.source.len) {
254 index += 2;
255 continue;
256 }
257 index += 1;
258 }
259 const value_end = trimTrailingSpace(self.source, value_start, index);
260 const closed = index < self.source.len;
261 self.index = if (closed) index + 1 else index;
262 return .{
263 .kind = if (closed) .url else .bad_url,
264 .start = start,
265 .end = self.index,
266 .value_start = value_start,
267 .value_end = value_end,
268 .escaped = hasEscape(self.source[value_start..value_end]),
269 };
270 }
271
272 fn string(self: *Tokenizer, start: u32, quote: u8) Token {
273 var index = start + 1;
274 while (index < self.source.len) {
275 const byte = self.source[index];
276 if (byte == quote) {
277 self.index = index + 1;
278 return .{
279 .kind = .string,
280 .start = start,
281 .end = index + 1,
282 .value_start = start + 1,
283 .value_end = index,
284 .escaped = hasEscape(self.source[start + 1 .. index]),
285 };
286 }
287 if (byte == '\n') break;
288 if (byte == '\\' and index + 1 < self.source.len) {
289 index += 2;
290 continue;
291 }
292 index += 1;
293 }
294 self.index = index;
295 return .{
296 .kind = .bad_string,
297 .start = start,
298 .end = index,
299 .value_start = start + 1,
300 .value_end = index,
301 };
302 }
303
304 fn numeric(self: *Tokenizer, start: u32) Token {
305 const scanned = consumeNumber(self.source, start);
306 var token = Token{
307 .kind = .number,
308 .start = start,
309 .end = scanned.end,
310 .value_start = start,
311 .value_end = scanned.end,
312 .number = std.fmt.parseFloat(f64, self.source[start..scanned.end]) catch 0,
313 .numeric = scanned.kind,
314 };
315 if (startsIdent(self.source, scanned.end)) {
316 const unit_end = consumeIdent(self.source, scanned.end);
317 token.kind = .dimension;
318 token.unit_start = scanned.end;
319 token.unit_end = unit_end;
320 token.end = unit_end;
321 } else if (scanned.end < self.source.len and self.source[scanned.end] == '%') {
322 token.kind = .percentage;
323 token.end = scanned.end + 1;
324 }
325 self.index = token.end;
326 return token;
327 }
328 };
329
330 const Number = struct {
331 end: u32,
332 kind: NumericKind,
333 };
334
335 /// Decodes CSS escapes from `text` into `out`, dropping escaped newlines.
336 /// Returns null when the decoded identifier does not fit.
337 pub fn unescape(text: []const u8, out: []u8) ?[]const u8 {
338 var read: usize = 0;
339 var written: usize = 0;
340 while (read < text.len) {
341 const byte = text[read];
342 if (byte != '\\') {
343 if (written >= out.len) return null;
344 out[written] = byte;
345 written += 1;
346 read += 1;
347 continue;
348 }
349 read += 1;
350 if (read >= text.len) {
351 if (written + 3 > out.len) return null;
352 written += std.unicode.utf8Encode(0xFFFD, out[written..]) catch return null;
353 break;
354 }
355 if (text[read] == '\n') {
356 read += 1;
357 continue;
358 }
359 if (!isHex(text[read])) {
360 const start = read;
361 read += std.unicode.utf8ByteSequenceLength(text[read]) catch 1;
362 const end = @min(read, text.len);
363 if (written + (end - start) > out.len) return null;
364 @memcpy(out[written..][0 .. end - start], text[start..end]);
365 written += end - start;
366 continue;
367 }
368 var point: u32 = 0;
369 var digits: usize = 0;
370 while (read < text.len and digits < 6 and isHex(text[read])) : (digits += 1) {
371 point = point * 16 + hexValue(text[read]);
372 read += 1;
373 }
374 if (read < text.len and isWhitespace(text[read])) read += 1;
375 const scalar = if (point == 0 or point > 0x10FFFF or
376 (point >= 0xD800 and point <= 0xDFFF)) 0xFFFD else point;
377 written += std.unicode.utf8Encode(@intCast(scalar), out[written..]) catch return null;
378 }
379 return out[0..written];
380 }
381
382 /// Whether `text` carries an escape and therefore needs `unescape`.
383 pub fn hasEscape(text: []const u8) bool {
384 return std.mem.indexOfScalar(u8, text, '\\') != null;
385 }
386
387 /// Whether `byte` may start an identifier.
388 pub fn isIdentStart(byte: u8) bool {
389 return std.ascii.isAlphabetic(byte) or byte == '_' or byte >= 0x80;
390 }
391
392 /// Whether `byte` may continue an identifier.
393 pub fn isIdent(byte: u8) bool {
394 return isIdentStart(byte) or std.ascii.isDigit(byte) or byte == '-';
395 }
396
397 /// Whether `byte` is one of the five CSS whitespace bytes.
398 pub fn isWhitespace(byte: u8) bool {
399 return byte == ' ' or byte == '\t' or byte == '\n' or byte == '\r' or byte == 0x0C;
400 }
401
402 fn isDigit(byte: u8) bool {
403 return std.ascii.isDigit(byte);
404 }
405
406 fn isHex(byte: u8) bool {
407 return std.ascii.isHex(byte);
408 }
409
410 fn hexValue(byte: u8) u32 {
411 if (byte <= '9') return byte - '0';
412 return (byte | 0x20) - 'a' + 10;
413 }
414
415 fn punctuation(byte: u8) ?Kind {
416 return switch (byte) {
417 ':' => .colon,
418 ';' => .semicolon,
419 ',' => .comma,
420 '[' => .left_square,
421 ']' => .right_square,
422 '(' => .left_paren,
423 ')' => .right_paren,
424 '{' => .left_curly,
425 '}' => .right_curly,
426 else => null,
427 };
428 }
429
430 fn quotedUrl(source: []const u8, start: u32) bool {
431 var index = start;
432 while (index < source.len and isWhitespace(source[index])) index += 1;
433 return index < source.len and (source[index] == '"' or source[index] == '\'');
434 }
435
436 fn trimTrailingSpace(source: []const u8, start: u32, end: u32) u32 {
437 var index = end;
438 while (index > start and isWhitespace(source[index - 1])) index -= 1;
439 return index;
440 }
441
442 /// Whether an identifier starts at `index`, per section 4.3.9.
443 pub fn startsIdent(source: []const u8, index: u32) bool {
444 if (index >= source.len) return false;
445 const byte = source[index];
446 if (isIdentStart(byte)) return true;
447 if (byte == '-') {
448 if (index + 1 >= source.len) return false;
449 const after = source[index + 1];
450 return isIdentStart(after) or after == '-' or validEscape(source, index + 1);
451 }
452 return validEscape(source, index);
453 }
454
455 /// Whether a number starts at `index`, per section 4.3.10.
456 pub fn startsNumber(source: []const u8, index: u32) bool {
457 if (index >= source.len) return false;
458 const byte = source[index];
459 if (isDigit(byte)) return true;
460 if (byte == '.') return index + 1 < source.len and isDigit(source[index + 1]);
461 if (byte != '+' and byte != '-') return false;
462 if (index + 1 >= source.len) return false;
463 if (isDigit(source[index + 1])) return true;
464 return source[index + 1] == '.' and index + 2 < source.len and isDigit(source[index + 2]);
465 }
466
467 /// Whether a valid escape starts at `index`, per section 4.3.8.
468 pub fn validEscape(source: []const u8, index: u32) bool {
469 if (index >= source.len or source[index] != '\\') return false;
470 return index + 1 < source.len and source[index + 1] != '\n';
471 }
472
473 /// Consumes an identifier starting at `index` and returns its end.
474 pub fn consumeIdent(source: []const u8, index: u32) u32 {
475 var cursor = index;
476 var guard: usize = 0;
477 while (cursor < source.len and guard <= source.len) : (guard += 1) {
478 if (isIdent(source[cursor])) {
479 cursor += 1;
480 continue;
481 }
482 if (validEscape(source, cursor)) {
483 cursor += 2;
484 if (isHex(source[cursor - 1])) {
485 var digits: usize = 1;
486 while (cursor < source.len and digits < 6 and isHex(source[cursor])) : (digits += 1) {
487 cursor += 1;
488 }
489 if (cursor < source.len and isWhitespace(source[cursor])) cursor += 1;
490 }
491 continue;
492 }
493 break;
494 }
495 return @min(cursor, @as(u32, @intCast(source.len)));
496 }
497
498 fn consumeNumber(source: []const u8, index: u32) Number {
499 var cursor = index;
500 var kind = NumericKind.integer;
501 if (cursor < source.len and (source[cursor] == '+' or source[cursor] == '-')) cursor += 1;
502 while (cursor < source.len and isDigit(source[cursor])) cursor += 1;
503 if (cursor + 1 < source.len and source[cursor] == '.' and isDigit(source[cursor + 1])) {
504 cursor += 2;
505 kind = .number;
506 while (cursor < source.len and isDigit(source[cursor])) cursor += 1;
507 }
508 const exponent = consumeExponent(source, cursor);
509 if (exponent != cursor) kind = .number;
510 return .{ .end = exponent, .kind = kind };
511 }
512
513 fn consumeExponent(source: []const u8, index: u32) u32 {
514 if (index >= source.len or (source[index] | 0x20) != 'e') return index;
515 var cursor = index + 1;
516 if (cursor < source.len and (source[cursor] == '+' or source[cursor] == '-')) cursor += 1;
517 if (cursor >= source.len or !isDigit(source[cursor])) return index;
518 while (cursor < source.len and isDigit(source[cursor])) cursor += 1;
519 return cursor;
520 }
521
522 fn expectKinds(source: []const u8, expected: []const Kind) !void {
523 var tokenizer = Tokenizer.init(source);
524 for (expected) |kind| {
525 const token = tokenizer.next();
526 try std.testing.expectEqual(kind, token.kind);
527 }
528 try std.testing.expectEqual(Kind.eof, tokenizer.next().kind);
529 }
530
531 test "a rule tokenizes into identifiers, punctuation, and dimensions" {
532 try expectKinds("a.b { width: 10px }", &.{
533 .ident, .delim, .ident, .whitespace, .left_curly,
534 .whitespace, .ident, .colon, .whitespace, .dimension,
535 .whitespace, .right_curly,
536 });
537 }
538
539 test "comments vanish between tokens instead of becoming one" {
540 try expectKinds("a/* gone */b", &.{ .ident, .ident });
541 try expectKinds("/* leading */", &.{});
542 try expectKinds("a/* unterminated", &.{.ident});
543 }
544
545 test "numeric tokens carry their value, flag, and unit" {
546 var tokenizer = Tokenizer.init("12 -3.5 4e2 50% 1.5rem");
547 const integer = tokenizer.next();
548 try std.testing.expectEqual(NumericKind.integer, integer.numeric);
549 try std.testing.expectEqual(@as(f64, 12), integer.number);
550 _ = tokenizer.next();
551 const negative = tokenizer.next();
552 try std.testing.expectEqual(@as(f64, -3.5), negative.number);
553 try std.testing.expectEqual(NumericKind.number, negative.numeric);
554 _ = tokenizer.next();
555 const exponent = tokenizer.next();
556 try std.testing.expectEqual(@as(f64, 400), exponent.number);
557 _ = tokenizer.next();
558 const percent = tokenizer.next();
559 try std.testing.expectEqual(Kind.percentage, percent.kind);
560 try std.testing.expectEqual(@as(f64, 50), percent.number);
561 _ = tokenizer.next();
562 const dimension = tokenizer.next();
563 try std.testing.expectEqualStrings("rem", dimension.unit("12 -3.5 4e2 50% 1.5rem"));
564 }
565
566 test "a hash token separates an identifier from a hex color" {
567 var tokenizer = Tokenizer.init("#save #123");
568 const identifier = tokenizer.next();
569 try std.testing.expectEqual(HashKind.id, identifier.hash_kind);
570 try std.testing.expectEqualStrings("save", identifier.value("#save #123"));
571 _ = tokenizer.next();
572 const color = tokenizer.next();
573 try std.testing.expectEqual(HashKind.unrestricted, color.hash_kind);
574 }
575
576 test "a string keeps its interior and an unterminated one goes bad" {
577 const source = "\"a b\" 'c'\n\"open";
578 var tokenizer = Tokenizer.init(source);
579 const double = tokenizer.next();
580 try std.testing.expectEqualStrings("a b", double.value(source));
581 _ = tokenizer.next();
582 const single = tokenizer.next();
583 try std.testing.expectEqualStrings("c", single.value(source));
584 _ = tokenizer.next();
585 try std.testing.expectEqual(Kind.bad_string, tokenizer.next().kind);
586 }
587
588 test "url takes an unquoted body and a function takes a quoted one" {
589 const source = "url(a.png) url(\"b.png\") rgb(1,2,3)";
590 var tokenizer = Tokenizer.init(source);
591 const bare = tokenizer.next();
592 try std.testing.expectEqual(Kind.url, bare.kind);
593 try std.testing.expectEqualStrings("a.png", bare.value(source));
594 _ = tokenizer.next();
595 try std.testing.expectEqual(Kind.function, tokenizer.next().kind);
596 _ = tokenizer.next();
597 _ = tokenizer.next();
598 _ = tokenizer.next();
599 const call = tokenizer.next();
600 try std.testing.expectEqual(Kind.function, call.kind);
601 try std.testing.expectEqualStrings("rgb", call.value(source));
602 }
603
604 test "markup delimiters and at keywords tokenize apart from delimiters" {
605 try expectKinds("<!-- --> @media @ <", &.{
606 .cdo, .whitespace, .cdc, .whitespace, .at_keyword, .whitespace, .delim,
607 .whitespace, .delim,
608 });
609 }
610
611 test "an escape decodes to its code point and a continuation disappears" {
612 var buffer: [32]u8 = undefined;
613 try std.testing.expectEqualStrings("A", unescape("\\41 ", &buffer).?);
614 try std.testing.expectEqualStrings("ab", unescape("a\\\nb", &buffer).?);
615 try std.testing.expectEqualStrings("a:b", unescape("a\\:b", &buffer).?);
616 try std.testing.expectEqualStrings("\u{FFFD}", unescape("\\0", &buffer).?);
617 var tiny: [1]u8 = undefined;
618 try std.testing.expect(unescape("abc", &tiny) == null);
619 }
620
621 test "an escaped identifier stays one identifier token" {
622 const source = "\\34 two";
623 var tokenizer = Tokenizer.init(source);
624 const token = tokenizer.next();
625 try std.testing.expectEqual(Kind.ident, token.kind);
626 try std.testing.expect(token.escaped);
627 var buffer: [32]u8 = undefined;
628 try std.testing.expectEqualStrings("4two", unescape(token.value(source), &buffer).?);
629 }
630
631 test "every token advances the cursor and an empty source ends at once" {
632 const source = "~ ! $ ^ | * = / +";
633 var tokenizer = Tokenizer.init(source);
634 var previous: u32 = 0;
635 var seen: usize = 0;
636 while (true) : (seen += 1) {
637 const token = tokenizer.next();
638 if (token.kind == .eof) break;
639 try std.testing.expect(tokenizer.index > previous);
640 previous = tokenizer.index;
641 }
642 try std.testing.expectEqual(@as(usize, 17), seen);
643 var empty = Tokenizer.init("");
644 try std.testing.expectEqual(Kind.eof, empty.next().kind);
645 }