1//! The tokenizer is an extremely simple structure that, given a view of source
2//! code, can stream tokens one at a time. A token is an 8-bit tag and a 32-bit
3//! offset to where that token is located.
4//!
5//! Retrieving payloads like string/numeric values, identifier names, etc is
6//! done separately, either in Parse or Transform, when the respective data
7//! is actually needed. Tokenization does guarantee that such data is valid.
8code: [:0]const u8,
9pos: ByteOffset = 0,
10
11/// Tokenize source code into a list of tokens.
12/// Caller owns returned slice.
13pub fn tokenize(source_code: [:0]const u8, gpa: mem.Allocator) mem.Allocator.Error!Token.List.Slice {
14 const trace = T.trace(@src());
15 defer trace.end();
16
17 var tokens = Token.List{};
18 errdefer tokens.deinit(gpa);
19
20 // pre-allocate some space based on a very rough guess
21 try tokens.ensureTotalCapacity(gpa, @divFloor(source_code.len, 8));
22
23 var tokenizer: Tokenizer = .{ .code = source_code };
24
25 tokenizer.skipWhitespace();
26 while (tokenizer.next()) |token| {
27 try tokens.append(gpa, token);
28 tokenizer.skipWhitespace();
29 }
30
31 try tokens.append(gpa, .{
32 .tag = .eof,
33 .offset = @intCast(source_code.len),
34 });
35
36 return tokens.toOwnedSlice();
37}
38
39pub const ByteOffset = u32;
40
41pub const Token = struct {
42 tag: Tag,
43 offset: ByteOffset,
44
45 pub const List = std.MultiArrayList(Token);
46
47 pub const Tag = enum {
48 id,
49 builtin_id,
50 number_int,
51 number_float,
52 string,
53 multiline_string,
54 doc_comment,
55 module_doc_comment,
56
57 // sort-lines: start
58 kw_and,
59 kw_assert,
60 kw_break,
61 kw_comptime,
62 kw_defer,
63 kw_else,
64 kw_enum,
65 kw_fn,
66 kw_for,
67 kw_if,
68 kw_impl,
69 kw_infer,
70 kw_json,
71 kw_let,
72 kw_match,
73 kw_module,
74 kw_or,
75 kw_pub,
76 kw_pure,
77 kw_return,
78 kw_struct,
79 kw_trait,
80 kw_tuple,
81 kw_var,
82 kw_while,
83 // sort-lines: end
84
85 // sort-lines: start
86 @"and",
87 and_and,
88 and_and_equal,
89 and_equal,
90 bang,
91 bang_equal,
92 caret,
93 caret_equal,
94 colon,
95 comma,
96 dot,
97 end_brace,
98 end_bracket,
99 end_paren,
100 equal,
101 equal_equal,
102 equal_lt,
103 gt,
104 gt_equal,
105 gt_gt,
106 gt_gt_equal,
107 gt_gt_gt,
108 gt_gt_gt_equal,
109 lt,
110 lt_equal,
111 lt_lt,
112 lt_lt_equal,
113 minus,
114 minus_equal,
115 minus_lt,
116 percent,
117 percent_equal,
118 pipe,
119 pipe_equal,
120 pipe_pipe,
121 pipe_pipe_equal,
122 plus,
123 plus_equal,
124 semi,
125 slash,
126 slash_equal,
127 star,
128 star_equal,
129 star_star,
130 star_star_equal,
131 start_brace,
132 start_bracket,
133 start_paren,
134 tilde,
135 tilde_equal,
136 // sort-lines: end
137
138 /// Represents a tokenization error. Instead of reporting an error during
139 /// tokenization, parsing will begin, and an error will be reported when
140 /// this token is hit. That way, the error .
141 invalid,
142 invalid_number,
143 invalid_string,
144 invalid_unterminated_string,
145 invalid_git_conflict,
146 invalid_utf8,
147 /// End of file
148 /// Used so that parser does not need to do out of bounds checks
149 eof,
150
151 /// Most tokens have statically known lexemes, such as "struct" or "+="
152 pub fn lexeme(tag: Tag) ?[]const u8 {
153 return switch (tag) {
154 .eof => unreachable, // always must be special cased
155
156 // invalid sequences do not have static lexemes
157 .invalid,
158 .invalid_number,
159 .invalid_string,
160 .invalid_unterminated_string,
161 .invalid_git_conflict,
162 .invalid_utf8,
163 => null,
164
165 // do not have a static lexeme
166 .id,
167 .builtin_id,
168 .number_int,
169 .number_float,
170 .string,
171 .multiline_string,
172 .doc_comment,
173 .module_doc_comment,
174 => null,
175
176 .@"and" => "&",
177 .and_and => "&&",
178 .bang => "!",
179 .bang_equal => "!=",
180 .equal_lt => "=<",
181 .caret => "^",
182 .end_brace => "}",
183 .end_bracket => "]",
184 .end_paren => ")",
185 .colon => ":",
186 .comma => ",",
187 .dot => ".",
188 .equal => "=",
189 .equal_equal => "==",
190 .gt => ">",
191 .gt_equal => ">=",
192 .gt_gt => ">>",
193 .gt_gt_gt => ">>>",
194 .lt => "<",
195 .lt_equal => "<=",
196 .lt_lt => "<<",
197 .minus => "-",
198 .start_brace => "{",
199 .start_bracket => "[",
200 .start_paren => "(",
201 .pipe => "|",
202 .pipe_pipe => "||",
203 .percent => "%",
204 .plus => "+",
205 .minus_lt => "->",
206 .semi => ";",
207 .slash => "/",
208 .star => "*",
209 .star_star => "**",
210 .tilde => "~",
211 .slash_equal => "/=",
212 .percent_equal => "%=",
213 .tilde_equal => "~=",
214 .caret_equal => "^=",
215 .and_equal => "&=",
216 .pipe_equal => "|=",
217 .lt_lt_equal => "<<=",
218 .gt_gt_equal => ">>=",
219 .gt_gt_gt_equal => ">>>=",
220 .plus_equal => "+=",
221 .minus_equal => "-=",
222 .star_equal => "*=",
223 .star_star_equal => "**=",
224 .pipe_pipe_equal => "||=",
225 .and_and_equal => "&&=",
226
227 inline else => |keyword| comptime len: {
228 if (!mem.startsWith(u8, @tagName(keyword), "kw_")) {
229 @compileError("Token tag is not a keyword: " ++ @tagName(keyword));
230 }
231 break :len @tagName(keyword)[3..];
232 },
233 };
234 }
235
236 pub fn description(tag: Tag) []const u8 {
237 return switch (tag) {
238 .eof => "end of file",
239
240 .invalid => "unknown character",
241 .invalid_number => "invalid number",
242 .invalid_string => "invalid string literal",
243 .invalid_unterminated_string => "unterminated string literal",
244 .invalid_git_conflict => "git merge conflict marker",
245 .invalid_utf8 => "invalid UTF-8 bytes",
246
247 .id => "an identifier",
248 .builtin_id => "a builtin identifier",
249 .number_int => "a numeric literal",
250 .number_float => "a numeric literal",
251 .string => "a string literal",
252 .multiline_string => "a multiline string literal",
253 .doc_comment => "a documentation comment",
254 .module_doc_comment => "a module documentation comment",
255 inline else => |t| comptime "\"" ++ t.lexeme().? ++ "\"",
256 };
257 }
258
259 pub fn isKeyword(tag: Tag) bool {
260 return switch (tag) {
261 inline else => |t| comptime mem.startsWith(u8, @tagName(t), "kw_"),
262 };
263 }
264
265 /// Most tokens have a static length, such as "struct" or "+="
266 pub fn staticLen(tag: Tag) ?u32 {
267 return if (tag.lexeme()) |str| @intCast(str.len) else null;
268 }
269
270 pub fn isInvalid(tag: Tag) bool {
271 return switch (tag) {
272 .invalid => true,
273 inline else => |t| comptime mem.startsWith(u8, @tagName(t), "invalid_"),
274 };
275 }
276 };
277
278 /// Instead of storing the length of a token, it's recomputed on demand by
279 /// tokenizing the text. This trade-off was done to preserve memory.
280 ///
281 /// When computing the length of something that can be known without
282 /// the source code, use token.tag.staticLen() instead.
283 pub fn len(token: Token, utf8_source: [:0]const u8) u32 {
284 return token.tag.staticLen() orelse switch (token.tag) {
285
286 // TODO: calling len on these tokens is incorrect, as
287 // error handling code should special case these all
288 // to highlight exactly what went wrong.
289 .invalid => std.unicode.utf8ByteSequenceLength(utf8_source[token.offset]) catch 1,
290 .invalid_git_conflict => 7,
291 .invalid_utf8 => 1,
292
293 else => {
294 @branchHint(.likely);
295 var tokenizer = Tokenizer{ .code = utf8_source, .pos = token.offset };
296 const retokenized = tokenizer.next() orelse unreachable; // data corruption
297 if (retokenized.tag != token.tag and !token.tag.isInvalid()) {
298 std.debug.panic(
299 "len() got wrong tag when re-tokenizing: .{s} != .{s}",
300 .{ @tagName(retokenized.tag), @tagName(token.tag) },
301 );
302 }
303 return tokenizer.pos - token.offset;
304 },
305 };
306 }
307
308 pub fn slice(token: Token, utf8_source: [:0]const u8) []const u8 {
309 return token.tag.lexeme() orelse
310 utf8_source[token.offset..][0..token.len(utf8_source)];
311 }
312
313 pub const keywords = std.StaticStringMap(Tag).initComptime(keywords: {
314 const fields = std.enums.values(Tag);
315 const KV = struct { []const u8, Tag };
316 var kws: [fields.len]KV = undefined;
317 var i = 0;
318 for (fields) |field| {
319 if (mem.startsWith(u8, @tagName(field), "kw_")) {
320 kws[i] = .{ @tagName(field)[3..], field };
321 i += 1;
322 }
323 }
324 break :keywords kws[0..i];
325 });
326};
327
328/// When any of these errors occurs, the tokenizer's
329/// position is set to the start of the offending bytes.
330pub const NextTokenError = error{
331 /// Generic token syntax error
332 InvalidSyntax,
333 /// A trailing '_' was seen in a numeric literal.
334 TrailingNumericSeparator,
335 /// Newline or EOF encountered while parsing a string literal.
336 UnterminatedString,
337 /// A string escape sequence was invalid.
338 InvalidEscapeSequence,
339 /// The codepoint represented by a unicode escape sequence
340 /// is not a valid unicode codepoint.
341 InvalidEscapeCodepoint,
342 /// There are unresolved git conflicts in the source code.
343 GitConflict,
344 /// The source code is not valid UTF-8.
345 InvalidUtf8,
346};
347
348/// Next assumes the position is already at the start of a token.
349/// You must call `skipWhitespace` before calling this.
350pub fn next(t: *Tokenizer) ?Token {
351 return t.nextErrorable() catch |err| {
352 defer {
353 t.pos = @intCast(mem.indexOfScalarPos(
354 u8,
355 t.code,
356 t.pos + 3,
357 '\n',
358 ) orelse t.code.len);
359 }
360 return .{
361 .offset = t.pos,
362 .tag = switch (err) {
363 error.InvalidSyntax => .invalid,
364 error.TrailingNumericSeparator => .invalid_number,
365 error.UnterminatedString => .invalid_unterminated_string,
366 error.InvalidEscapeSequence => .invalid_string,
367 error.InvalidEscapeCodepoint => .invalid_string,
368 error.GitConflict => .invalid_git_conflict,
369 error.InvalidUtf8 => .invalid_utf8,
370 },
371 };
372 };
373}
374
375pub fn nextErrorable(t: *Tokenizer) NextTokenError!?Token {
376 while (true) {
377 const trace = T.trace(@src());
378 defer trace.end();
379
380 switch (t.byte()) {
381 ' ', '\t', '\n', '\r' => unreachable, // call skipWhitespace
382
383 'a'...'z', 'A'...'Z', '_' => {
384 const start = t.pos;
385 t.pos += 1;
386 return try t.tokenizeIdentifier(start);
387 },
388
389 '@' => switch (t.nextByte()) {
390 '"' => {
391 const start = t.pos;
392 t.pos += 1;
393 try t.consumeString();
394 return .{ .tag = .id, .offset = start };
395 },
396 else => {
397 const start = t.pos;
398 t.pos += 1;
399 return try t.tokenizeIdentifier(start);
400 },
401 },
402
403 '0'...'9' => return try t.tokenizeNumber(),
404
405 '/' => switch (t.nextByte()) {
406 '=' => return t.simpleToken(.slash_equal),
407 '/' => {
408 if ((t.byteAt(2) orelse 0 == '/') and
409 (t.byteAt(3) orelse 0 != '/'))
410 {
411 const start = t.pos;
412 t.pos = @intCast(mem.indexOfScalarPos(
413 u8,
414 t.code,
415 t.pos + 3,
416 '\n',
417 ) orelse t.code.len);
418 return .{ .tag = .doc_comment, .offset = start };
419 }
420
421 if (t.byteAt(2) orelse 0 == '!') {
422 const start = t.pos;
423 t.pos = @intCast(mem.indexOfScalarPos(
424 u8,
425 t.code,
426 t.pos + 2,
427 '\n',
428 ) orelse t.code.len);
429 return .{ .tag = .module_doc_comment, .offset = start };
430 }
431
432 // skip the comment
433 t.pos = @intCast(mem.indexOfScalarPos(
434 u8,
435 t.code,
436 t.pos + 2,
437 '\n',
438 ) orelse t.code.len);
439 t.skipWhitespace();
440 continue;
441 },
442 else => return t.simpleToken(.slash),
443 },
444
445 '\\' => switch (t.nextByte()) {
446 '\\' => {
447 const start = t.pos;
448 t.pos = @intCast(mem.indexOfScalarPos(
449 u8,
450 t.code,
451 t.pos + 2,
452 '\n',
453 ) orelse t.code.len);
454 return .{ .tag = .multiline_string, .offset = start };
455 },
456 else => return t.maybeUTF8Error(error.InvalidSyntax),
457 },
458
459 '"' => return try t.tokenizeString(),
460
461 '&' => switch (t.nextByte()) {
462 '&' => return t.simpleToken(.and_and),
463 '=' => return t.simpleToken(.and_equal),
464 else => return t.simpleToken(.@"and"),
465 },
466 '|' => switch (t.nextByte()) {
467 '|' => return t.simpleToken(.pipe_pipe),
468 '=' => return t.simpleToken(.pipe_equal),
469 else => return t.simpleToken(.pipe),
470 },
471 '^' => switch (t.nextByte()) {
472 '^' => return t.simpleToken(.caret),
473 '=' => return t.simpleToken(.caret_equal),
474 else => return t.simpleToken(.caret),
475 },
476 '!' => switch (t.nextByte()) {
477 '=' => return t.simpleToken(.equal_equal),
478 else => return t.simpleToken(.bang_equal),
479 },
480 '=' => switch (t.nextByte()) {
481 '=' => return t.simpleToken(.equal_equal),
482 else => return t.simpleToken(.equal),
483 },
484 '>' => switch (t.nextByte()) {
485 '=' => return t.simpleToken(.gt_equal),
486 '>' => switch (t.byteAt(2) orelse 0) {
487 '>' => return t.simpleToken(.gt_gt_gt),
488 else => return t.simpleToken(.gt_gt),
489 },
490 else => return t.simpleToken(.gt),
491 },
492 '<' => switch (t.nextByte()) {
493 '=' => return t.simpleToken(.lt_equal),
494 '<' => switch (t.byteAt(2) orelse 0) {
495 '=' => return t.simpleToken(.lt_lt_equal),
496 else => {
497 // Git merge conflicts are <<<<<<<
498 const start = t.pos;
499 t.pos += 2;
500 var remain: u3 = 4;
501 while (t.byte() == '<') {
502 t.pos += 1;
503 remain -= 1;
504 if (remain == 0) {
505 return error.GitConflict;
506 }
507 }
508 t.pos = start;
509 return t.simpleToken(.lt_lt);
510 },
511 },
512 else => return t.simpleToken(.lt),
513 },
514 '+' => switch (t.nextByte()) {
515 '=' => return t.simpleToken(.plus_equal),
516 else => return t.simpleToken(.plus),
517 },
518 '-' => switch (t.nextByte()) {
519 '=' => return t.simpleToken(.minus_equal),
520 '>' => return t.simpleToken(.minus_lt),
521 else => return t.simpleToken(.minus),
522 },
523 '*' => switch (t.nextByte()) {
524 '*' => return t.simpleToken(.star_star),
525 '=' => return t.simpleToken(.star_equal),
526 else => return t.simpleToken(.star),
527 },
528 '%' => switch (t.nextByte()) {
529 '=' => return t.simpleToken(.percent_equal),
530 else => return t.simpleToken(.percent),
531 },
532 '~' => switch (t.nextByte()) {
533 '=' => return t.simpleToken(.tilde_equal),
534 else => return t.simpleToken(.tilde),
535 },
536
537 ';' => return t.simpleToken(.semi),
538 ':' => return t.simpleToken(.colon),
539 '(' => return t.simpleToken(.start_paren),
540 ')' => return t.simpleToken(.end_paren),
541 '[' => return t.simpleToken(.start_bracket),
542 ']' => return t.simpleToken(.end_bracket),
543 '{' => return t.simpleToken(.start_brace),
544 '}' => return t.simpleToken(.end_brace),
545 ',' => return t.simpleToken(.comma),
546 '.' => return t.simpleToken(.dot),
547
548 0x80...0xFF => {
549 // need to decode utf-8
550 const byte_len, const code_point = try t.codePoint();
551
552 if (unicode_props.isXidStart(code_point)) {
553 const start = t.pos;
554 t.pos += byte_len;
555 return try t.tokenizeIdentifier(start);
556 }
557
558 return error.InvalidSyntax;
559 },
560
561 else => return error.InvalidSyntax,
562
563 0 => {
564 if (t.pos == t.code.len) return null;
565 return error.InvalidSyntax;
566 },
567 }
568 }
569}
570
571/// Source code is null terminated, so accessing this is safe
572fn byte(t: Tokenizer) u8 {
573 return t.code[t.pos];
574}
575
576/// Source code is null terminated.
577fn nextByte(t: Tokenizer) u8 {
578 assert(t.byte() < 0x80);
579 return t.code[t.pos + 1];
580}
581
582/// Remember that using this makes sense only if you know for certain that all
583/// previous bytes are ASCII, otherwise you may hit UB
584fn byteAt(t: Tokenizer, comptime offset: u32) ?u8 {
585 if (offset == 1) @compileError("use nextByte()");
586
587 // assert that the previous bytes are ASCII
588 // current byte is allowed to be a continuation byte
589 for (t.code[t.pos .. t.pos + offset]) |b| {
590 assert(b < 0x80);
591 }
592 return t.code[t.pos + offset];
593}
594
595fn byteAtRt(t: Tokenizer, offset: u32) ?u8 {
596 // assert that the previous bytes are ASCII
597 // current byte is allowed to be a continuation byte
598 for (t.code[t.pos .. t.pos + offset]) |b| {
599 assert(b < 0x80);
600 }
601 return t.code[t.pos + offset];
602}
603
604fn codePoint(t: Tokenizer) !struct { u3, u21 } {
605 const b = t.byte(); // must check the first byte manually
606 assert(b >= 0x80); // must be a continuation byte
607
608 const byte_len = unicode.utf8ByteSequenceLength(b) catch
609 return error.InvalidUtf8;
610 assert(byte_len > 1);
611
612 const code_point = unicode.utf8Decode(t.code[t.pos..][0..byte_len]) catch
613 return error.InvalidUtf8;
614
615 return .{ byte_len, code_point };
616}
617
618fn isAtIdentifierStart(t: *Tokenizer) !bool {
619 switch (t.byte()) {
620 'a'...'z', 'A'...'Z', '_' => return true,
621 else => return false,
622 0x80...0xFF => {
623 _, const code_point = try t.codePoint();
624 return unicode_props.isXidStart(code_point);
625 },
626 }
627}
628
629fn tokenizeIdentifier(t: *Tokenizer, start_byte: u32) !Token {
630 const trace = T.trace(@src());
631 defer trace.end();
632
633 while (true) {
634 switch (t.byte()) {
635 'a'...'z', 'A'...'Z', '0'...'9', '_' => {
636 t.pos += 1;
637 },
638 0x80...0xFF => {
639 const byte_len, const code_point = try t.codePoint();
640
641 t.pos += byte_len;
642
643 if (!unicode_props.isXidContinue(code_point)) {
644 break;
645 }
646 },
647 else => break,
648 }
649 }
650
651 return .{
652 .tag = Token.keywords.get(t.code[start_byte..t.pos]) orelse
653 if (t.code[start_byte] == '@')
654 .builtin_id
655 else
656 .id,
657 .offset = start_byte,
658 };
659}
660
661/// Numbers have the following rules:
662/// - May start with a `.`, but cannot end with `.`
663/// - May contain leading zeros, but transform pass will warn.
664/// - May contain a `_` separator, cannot have two in a row.
665/// - May contain `e` or `E` for exponents.
666/// - May use 0x, 0b, 0o prefixes for hex, binary, octal numbers.
667/// The token is tagged as `number_int` or `number_float` depending
668/// on if it contained a `.` This is to help later re-parses.
669fn tokenizeNumber(t: *Tokenizer) !Token {
670 const trace = T.trace(@src());
671 defer trace.end();
672
673 // Caller ensures the following invariant:
674 switch (t.byte()) {
675 '.' => switch (t.nextByte()) {
676 '0'...'9' => {},
677 else => unreachable,
678 },
679 '0'...'9' => {},
680 else => unreachable,
681 }
682
683 const start = t.pos;
684 var tag: Token.Tag = .number_int;
685
686 // Parse Hex, Binary, Octal numbers
687 if (t.byte() == '0') alt_base: {
688 switch (t.nextByte()) {
689 'x', 'X' => {
690 t.pos += 2;
691 try t.consumeIntegerRadix(.hex);
692 },
693 'b', 'B' => {
694 t.pos += 2;
695 try t.consumeIntegerRadix(.binary);
696 },
697 'o', 'O' => {
698 t.pos += 2;
699 try t.consumeIntegerRadix(.octal);
700 },
701 else => break :alt_base,
702 }
703
704 // after numbers must be a valid word break the above returns are right
705 // before parsing `.` so those can be unchecked.
706 if (try t.isAtIdentifierStart()) {
707 return error.InvalidSyntax;
708 }
709
710 return .{
711 .tag = tag,
712 .offset = start,
713 };
714 }
715
716 if (t.byte() == '.') {
717 t.pos += 1;
718 tag = .number_float;
719 try t.consumeInteger();
720 } else {
721 try t.consumeInteger();
722
723 // decimal point notation
724 switch (t.byte()) {
725 '.' => switch (t.nextByte()) {
726 '0'...'9' => {
727 t.pos += 1;
728 tag = .number_float;
729 try t.consumeInteger();
730 },
731 else => {
732 // we have not advanced the tokenizer past the `.`
733 assert(tag == .number_int);
734 return .{ .tag = tag, .offset = start };
735 },
736 },
737 else => {},
738 }
739 }
740
741 switch (t.byte()) {
742 'e', 'E' => {
743 tag = .number_float;
744 t.pos += 1;
745
746 switch (t.byte()) {
747 '+', '-' => {
748 t.pos += 1;
749 switch (t.byte()) {
750 '0'...'9' => {},
751 else => return t.maybeUTF8Error(error.InvalidSyntax),
752 }
753 },
754 '0'...'9' => {},
755 else => return t.maybeUTF8Error(error.InvalidSyntax),
756 }
757
758 try t.consumeInteger();
759
760 // decimal point notation
761 switch (t.byte()) {
762 '.' => switch (t.nextByte()) {
763 '0'...'9' => {
764 t.pos += 1;
765 tag = .number_float;
766 try t.consumeInteger();
767 },
768 else => {},
769 },
770 else => {},
771 }
772 },
773 else => {},
774 }
775
776 // after numbers must be a valid word break the above returns are right
777 // before parsing `.` so those can be unchecked.
778 if (try t.isAtIdentifierStart()) {
779 return error.InvalidSyntax;
780 }
781
782 return .{
783 .tag = tag,
784 .offset = start,
785 };
786}
787
788fn maybeConsumeInteger(t: *Tokenizer) !?void {
789 const trace = T.trace(@src());
790 defer trace.end();
791
792 switch (t.byte()) {
793 '0'...'9' => {
794 t.pos += 1;
795 },
796 else => return null,
797 }
798 t.consumeInteger();
799}
800
801/// Requires the first byte to be a digit
802fn consumeInteger(t: *Tokenizer) !void {
803 const trace = T.trace(@src());
804 defer trace.end();
805
806 switch (t.byte()) {
807 '0'...'9' => {
808 t.pos += 1;
809 },
810 else => unreachable,
811 }
812
813 while (true) {
814 switch (t.byte()) {
815 '0'...'9' => {
816 t.pos += 1;
817 },
818 '_' => {
819 t.pos += 1;
820 switch (t.byte()) {
821 '0'...'9' => {
822 t.pos += 1;
823 },
824 else => return t.maybeUTF8Error(error.TrailingNumericSeparator),
825 }
826 },
827 else => break,
828 }
829 }
830}
831
832const Radix = enum { hex, binary, octal };
833
834fn consumeIntegerRadix(t: *Tokenizer, comptime radix: Radix) !void {
835 const trace = T.trace(@src());
836 defer trace.end();
837
838 const digits = switch (radix) {
839 .hex => "0123456789abcdefABCDEF",
840 .binary => "01",
841 .octal => "01234567",
842 };
843
844 first: {
845 const b = t.byte();
846 inline for (digits) |digit| {
847 if (b == digit) {
848 break :first;
849 }
850 }
851 return t.maybeUTF8Error(error.InvalidSyntax);
852 }
853
854 t.pos += 1;
855
856 while (true) {
857 brk: {
858 const b = t.byte();
859 inline for (digits) |digit| {
860 if (b == digit) {
861 break :brk;
862 }
863 }
864 return;
865 }
866 t.pos += 1;
867 }
868}
869
870fn tokenizeString(t: *Tokenizer) !Token {
871 assert(t.byte() == '"');
872 const start = t.pos;
873 try t.consumeString();
874 return .{ .tag = .string, .offset = start };
875}
876
877fn consumeString(t: *Tokenizer) !void {
878 const trace = T.trace(@src());
879 defer trace.end();
880
881 const start = t.pos;
882 assert(t.byte() == '"');
883
884 t.pos += 1;
885
886 while (true) {
887 switch (t.byte()) {
888 '"' => {
889 t.pos += 1;
890 break;
891 },
892 '\\' => {
893 switch (t.nextByte()) {
894 '\n' => {
895 t.pos = start;
896 return error.UnterminatedString;
897 },
898 '\\' => t.pos += 2,
899 '"' => t.pos += 2,
900 'n' => t.pos += 2,
901 'r' => t.pos += 2,
902 't' => t.pos += 2,
903 'x' => {
904 switch (t.byteAt(2).?) {
905 '0'...'9', 'a'...'f', 'A'...'F' => {},
906 else => return error.InvalidEscapeSequence,
907 }
908 switch (t.byteAt(3).?) {
909 '0'...'9', 'a'...'f', 'A'...'F' => {},
910 else => return error.InvalidEscapeSequence,
911 }
912 t.pos += 4;
913 },
914 '0' => t.pos += 2,
915 'u' => {
916 const esc_start = t.pos;
917 t.consumeStringUnicodeEscape() catch |err| switch (err) {
918 error.InvalidEscapeSequence => {
919 if (t.byte() == '\n')
920 return error.UnterminatedString;
921 t.pos = esc_start;
922 return err;
923 },
924 error.InvalidEscapeCodepoint => {
925 t.pos = esc_start;
926 return err;
927 },
928 // error.UnterminatedString => return err,
929 };
930 },
931 else => return t.maybeUTF8ErrorAt(error.InvalidEscapeSequence, 1),
932 }
933 },
934 '\n' => {
935 t.pos = start;
936 return error.UnterminatedString;
937 },
938 else => {
939 t.pos += 1;
940 },
941 0x80...0xFF => {
942 const byte_len, _ = try t.codePoint();
943 t.pos += byte_len;
944 },
945 }
946 }
947}
948
949fn consumeStringUnicodeEscape(t: *Tokenizer) !void {
950 const trace = T.trace(@src());
951 defer trace.end();
952
953 assert(t.byte() == '\\');
954 assert(t.nextByte() == 'u');
955 t.pos += 2;
956
957 if (t.byte() != '{')
958 return error.InvalidEscapeSequence;
959 t.pos += 1;
960
961 if (t.byte() == '0') {
962 if (t.nextByte() == 'x') {
963 t.pos += 2;
964 }
965 }
966
967 const start = t.pos;
968 t.consumeIntegerRadix(.hex) catch return error.InvalidEscapeSequence;
969
970 const slice = t.code[start..t.pos];
971
972 if (t.byte() != '}')
973 return error.InvalidEscapeSequence;
974
975 const code_point = std.fmt.parseInt(u21, slice, 16) catch |err| switch (err) {
976 error.Overflow => return error.InvalidEscapeCodepoint,
977 error.InvalidCharacter => unreachable,
978 };
979 _ = std.unicode.utf8CodepointSequenceLength(code_point) catch |err| switch (err) {
980 error.CodepointTooLarge => return error.InvalidEscapeCodepoint,
981 };
982
983 t.pos += 1;
984}
985
986fn simpleToken(t: *Tokenizer, comptime tag: Token.Tag) Token {
987 const start = t.pos;
988 t.pos += comptime (tag.staticLen() orelse unreachable);
989 return .{ .tag = tag, .offset = start };
990}
991
992/// We are about to return an error, such as error.TrailingNumericSeparator.
993/// However, the character we ran into might actually be invalid UTF-8.
994/// This utility just checks for that to make sure we don't mask error.InvalidUtf8
995fn maybeUTF8Error(t: *Tokenizer, comptime real_err: anytype) @Type(.{
996 .error_set = &[_]std.builtin.Type.Error{
997 .{ .name = "InvalidUtf8" },
998 .{ .name = @errorName(real_err) },
999 },
1000}) {
1001 switch (t.byte()) {
1002 0x80...0xFF => {
1003 _ = try t.codePoint();
1004 return real_err;
1005 },
1006 else => return real_err,
1007 }
1008}
1009
1010fn maybeUTF8ErrorAt(t: *Tokenizer, comptime real_err: anytype, at: u32) @Type(.{
1011 .error_set = &[_]std.builtin.Type.Error{
1012 .{ .name = "InvalidUtf8" },
1013 .{ .name = @errorName(real_err) },
1014 },
1015}) {
1016 switch (t.byteAtRt(at) orelse return real_err) {
1017 0x80...0xFF => {
1018 _ = try t.codePoint();
1019 return real_err;
1020 },
1021 else => {
1022 if (@import("builtin").is_test)
1023 std.debug.print("{s}\n", .{@errorName(real_err)});
1024 return real_err;
1025 },
1026 }
1027}
1028
1029pub fn skipWhitespace(t: *Tokenizer) void {
1030 const trace = T.trace(@src());
1031 defer trace.end();
1032
1033 while (true) {
1034 switch (t.byte()) {
1035 ' ', '\t', '\n', '\r' => {
1036 t.pos += 1;
1037 },
1038 else => break,
1039 }
1040 }
1041}
1042
1043// end methods, start token-related utilities
1044
1045pub fn tokenLocation(
1046 utf8_source: []const u8,
1047 start_offset: ByteOffset,
1048 token_start: ByteOffset,
1049) Location {
1050 var loc: Location = .{
1051 .line = .start,
1052 .column = .start,
1053 .line_start = start_offset,
1054 .line_end = @intCast(utf8_source.len),
1055 };
1056
1057 // Scan by line until we go past the token start
1058 while (std.mem.indexOfScalarPos(u8, utf8_source, loc.line_start, '\n')) |i| {
1059 if (i >= token_start) {
1060 break; // Went past
1061 }
1062 loc.line = loc.line.add(1);
1063 loc.line_start = @intCast(i + 1);
1064 }
1065
1066 const offset = loc.line_start;
1067 for (utf8_source[offset..], 0..) |c, i| {
1068 if (i + offset == token_start) {
1069 loc.line_end = @intCast(i + offset);
1070 while (loc.line_end < utf8_source.len and utf8_source[loc.line_end] != '\n') {
1071 loc.line_end += 1;
1072 }
1073 return loc;
1074 }
1075 if (c == '\n') {
1076 loc.line = loc.line.add(1);
1077 loc.column = .start;
1078 loc.line_start = @intCast(i + 1);
1079 } else {
1080 loc.column = loc.column.add(1);
1081 }
1082 }
1083
1084 return loc;
1085}
1086
1087pub fn stringHasEscapes(esc: []const u8) bool {
1088 return mem.indexOfScalar(u8, esc, '\\') != null;
1089}
1090
1091/// Given a valid string literal contents (excluding the quotes), return
1092/// the length of the decoded string. This is helpful for pre-allocation.
1093pub fn decodeStringCount(esc: []const u8) usize {
1094 var result_len: usize = 0;
1095 var i: usize = 0;
1096 while (mem.indexOfScalarPos(u8, esc, i, '\\')) |backslash| {
1097 // add prior chars
1098 result_len += backslash - i;
1099
1100 switch (esc[backslash + 1]) {
1101 // single char escapes that add one ascii
1102 '"', '\\', 'n', 'r', '0' => {
1103 i = backslash + "\\n".len;
1104 result_len += 1;
1105 },
1106 // hex literals can be distinguished only by reading
1107 // the first char, classifying it in either two ranges
1108 //
1109 // - 0x00 thru 0x7F -> one byte
1110 // - 0x80 thru 0xFF -> two bytes
1111 //
1112 // we check the second byte anyway to ensure safe modes
1113 // catch potential invalid string literals.
1114 'x' => switch (esc[backslash + 3]) {
1115 '0'...'9', 'a'...'f', 'A'...'F' => {
1116 i = backslash + "\\x00".len;
1117 switch (esc[backslash + 2]) {
1118 '0'...'7',
1119 => result_len += 1,
1120
1121 '8'...'9',
1122 'a'...'f',
1123 'A'...'F',
1124 => result_len += 2,
1125
1126 else => unreachable, // invalid hex string
1127 }
1128 },
1129 else => unreachable, // invalid hex string
1130 },
1131 // unicode literals contain a numerical parse
1132 'u' => {
1133 assert(esc[backslash + 2] == '{');
1134
1135 // skip 0x hex prefix if present
1136 const start = if (esc[backslash + 4] == 'x')
1137 backslash + 5
1138 else
1139 backslash + 3;
1140
1141 const end = mem.indexOfScalarPos(u8, esc, start, '}') orelse
1142 unreachable; // invalid escape, missing }
1143 const slice = esc[start..end];
1144 const code_point = std.fmt.parseInt(u21, slice, 16) catch
1145 unreachable; // invalid numeric string
1146 result_len += std.unicode.utf8CodepointSequenceLength(code_point) catch
1147 unreachable; // invalid codepoint
1148
1149 i = end + 1;
1150 },
1151
1152 else => unreachable, // invalid escape
1153 }
1154 }
1155 return result_len + (esc.len - i);
1156}
1157
1158/// Given a valid string literal contents (excluding the quotes), write
1159/// its decoded form (WTF-8) into the buf.
1160pub fn decodeStringBuf(esc: []const u8, buf: []u8) []u8 {
1161 var result_i: usize = 0;
1162 var i: usize = 0;
1163 while (mem.indexOfScalarPos(u8, esc, i, '\\')) |backslash| {
1164 // add prior chars
1165 @memcpy(buf[result_i..][0 .. backslash - i], esc[i..backslash]);
1166 result_i += backslash - i;
1167
1168 switch (esc[backslash + 1]) {
1169 '"' => {
1170 i = backslash + "\\\"".len;
1171 buf[result_i] = '"';
1172 result_i += 1;
1173 },
1174 '\\' => {
1175 i = backslash + "\\\\".len;
1176 buf[result_i] = '\\';
1177 result_i += 1;
1178 },
1179 'n' => {
1180 i = backslash + "\\n".len;
1181 buf[result_i] = '\n';
1182 result_i += 1;
1183 },
1184 'r' => {
1185 i = backslash + "\\r".len;
1186 buf[result_i] = '\r';
1187 result_i += 1;
1188 },
1189 '0' => {
1190 i = backslash + "\\n".len;
1191 buf[result_i] = 0;
1192 result_i += 1;
1193 },
1194
1195 'x' => {
1196 const codepoint = std.fmt.parseInt(u8, esc[backslash + 2 ..][0..2], 16) catch
1197 unreachable; // invalid string literal
1198 i = backslash + "\\x00".len;
1199 if (codepoint < 0x80) {
1200 buf[result_i] = codepoint;
1201 result_i += 1;
1202 } else {
1203 const len = std.unicode.wtf8Encode(codepoint, buf[result_i..][0..2]) catch
1204 unreachable; // all codepoints <= 0xFF are valid
1205 assert(len == 2);
1206 result_i += 2;
1207 }
1208 },
1209 // unicode literals contain a numerical parse
1210 'u' => {
1211 assert(esc[backslash + 2] == '{');
1212 // skip 0x hex prefix if present
1213 const start = if (esc[backslash + 4] == 'x')
1214 backslash + 5
1215 else
1216 backslash + 3;
1217 const end = mem.indexOfScalarPos(u8, esc, start, '}') orelse
1218 unreachable; // invalid escape, missing }
1219 const slice = esc[start..end];
1220 const codepoint = std.fmt.parseInt(u21, slice, 16) catch
1221 unreachable; // invalid numeric string
1222 const len = std.unicode.utf8CodepointSequenceLength(codepoint) catch
1223 unreachable; // invalid codepoint
1224 const actual_len =
1225 std.unicode.wtf8Encode(codepoint, buf[result_i..][0..len]) catch
1226 unreachable; // already known to be valid codepoint
1227 assert(len == actual_len);
1228 result_i += len;
1229 i = end + 1;
1230 },
1231
1232 else => unreachable, // invalid escape
1233 }
1234 }
1235 @memcpy(buf[result_i..][0 .. esc.len - i], esc[i..]);
1236 return buf[0 .. result_i + esc.len - i];
1237}
1238
1239/// Given a valid string literal contents (excluding the quotes),
1240/// decode it into a newly allocated slice.
1241pub fn decodeStringAlloc(alloc: mem.Allocator, esc: []const u8) ![]u8 {
1242 const count = decodeStringCount(esc);
1243 const memory = try alloc.alloc(u8, count);
1244 const result = decodeStringBuf(esc, memory);
1245 assert(result.ptr == memory.ptr);
1246 assert(result.len == memory.len);
1247 return memory;
1248}
1249
1250const Tokenizer = @This();
1251const std = @import("std");
1252const unicode = std.unicode;
1253const assert = std.debug.assert;
1254const mem = std.mem;
1255const unicode_props = @import("unicode_props.zig");
1256const T = @import("tracer");
1257const Location = @import("Ast.zig").Location;
1258
1259fn testStringDecode(expected: []const u8, escaped: []const u8) !void {
1260 const testing = std.testing;
1261 const decoded = try decodeStringAlloc(testing.allocator, escaped);
1262 defer testing.allocator.free(decoded);
1263 try testing.expectEqualSlices(u8, expected, decoded);
1264}
1265
1266test "basic tokenizer example" {
1267 const testing = std.testing;
1268 try unicode_props.init();
1269
1270 // not valid source code, but testing the tokenization
1271 const source =
1272 \\var token = 1.2e9.2 4;
1273 \\// comment ignored
1274 \\pub fn hello(:+ true) id return
1275 \\π @"hello" "hello \r\n \x1b"
1276 ;
1277 const expected_tokens = [_]Token{
1278 .{ .tag = .kw_var, .offset = 0 },
1279 .{ .tag = .id, .offset = 4 },
1280 .{ .tag = .equal, .offset = 10 },
1281 .{ .tag = .number_float, .offset = 12 },
1282 .{ .tag = .number_int, .offset = 20 },
1283 .{ .tag = .semi, .offset = 21 },
1284 .{ .tag = .kw_pub, .offset = 42 },
1285 .{ .tag = .kw_fn, .offset = 46 },
1286 .{ .tag = .id, .offset = 49 },
1287 .{ .tag = .start_paren, .offset = 54 },
1288 .{ .tag = .colon, .offset = 55 },
1289 .{ .tag = .plus, .offset = 56 },
1290 .{ .tag = .id, .offset = 58 },
1291 .{ .tag = .end_paren, .offset = 62 },
1292 .{ .tag = .id, .offset = 64 },
1293 .{ .tag = .kw_return, .offset = 67 },
1294 .{ .tag = .id, .offset = 74 },
1295 .{ .tag = .id, .offset = 77 },
1296 .{ .tag = .string, .offset = 86 },
1297 };
1298 var tokenizer = Tokenizer{ .code = source };
1299 for (expected_tokens) |tok| {
1300 tokenizer.skipWhitespace();
1301 try testing.expectEqual(tok, tokenizer.next().?);
1302 }
1303 tokenizer.skipWhitespace();
1304 try testing.expectEqual(null, tokenizer.next());
1305}
1306
1307test "field access" {
1308 const testing = std.testing;
1309 try unicode_props.init();
1310
1311 const source =
1312 \\.0 hello.1.2
1313 ;
1314 const expected_tokens = [_]Token{
1315 .{ .tag = .dot, .offset = 0 },
1316 .{ .tag = .number_int, .offset = 1 },
1317 .{ .tag = .id, .offset = 3 },
1318 .{ .tag = .dot, .offset = 8 },
1319 .{ .tag = .number_float, .offset = 9 },
1320 };
1321 var tokenizer = Tokenizer{ .code = source };
1322 for (expected_tokens) |tok| {
1323 tokenizer.skipWhitespace();
1324 try testing.expectEqual(tok, tokenizer.next());
1325 }
1326 tokenizer.skipWhitespace();
1327 try testing.expectEqual(null, tokenizer.next());
1328}
1329
1330test "string escapes" {
1331 try testStringDecode("hello world", "hello world");
1332 try testStringDecode("hello\n\rw\x00or\x5ald", "hello\\n\\rw\\0or\\x5ald");
1333 try testStringDecode("255: \xC3\xBF", "255: \\xFF");
1334}