Line data Source code
1 : // wok_token -- the scanner.
2 : //
3 : // Scanning allocates the token vector and the comment vector and nothing else:
4 : // a token's text is a view into the source, never a copy.
5 :
6 : #include "wok_token.h"
7 :
8 : #include "wok_utf8.h"
9 :
10 : #include <string.h>
11 :
12 : // ------------------------------------------------------------- rosters
13 :
14 : static const char *const kind_names[] = {
15 : #define WOK_X(name) #name,
16 : WOK_KINDS(WOK_X)
17 : #undef WOK_X
18 : };
19 : static_assert(sizeof kind_names / sizeof *kind_names == WOK_KIND_COUNT,
20 : "every Kind needs a name");
21 :
22 32 : WOK_READONLY const char *wok_kind_name(WokKind k) {
23 32 : return (unsigned)k < WOK_KIND_COUNT ? kind_names[k] : "<bad kind>";
24 : }
25 :
26 : static const struct {
27 : const char *text;
28 : unsigned char kind;
29 : } word_tab[] = {
30 : [WW_NONE] = {"", WT_BAD},
31 : #define WOK_X(name, text, kind) [name] = {text, kind},
32 : WOK_WORDS(WOK_X)
33 : #undef WOK_X
34 : };
35 : static_assert(sizeof word_tab / sizeof *word_tab == WOK_WORD_COUNT,
36 : "every Word needs a spelling and an emitted kind");
37 :
38 38 : WOK_READONLY const char *wok_word_text(WokWord w) {
39 38 : return (unsigned)w < WOK_WORD_COUNT ? word_tab[w].text : "";
40 : }
41 :
42 232277 : WOK_READONLY WokKind wok_word_kind(WokWord w) {
43 232277 : return (unsigned)w < WOK_WORD_COUNT ? (WokKind)word_tab[w].kind : WT_BAD;
44 : }
45 :
46 : // Identifier spellings, bucketed by length. Thirty-one words: a length switch
47 : // resolves to one or two memcmps, which beats a hash table that would need
48 : // mutable global state and therefore a lock in a parallel batch.
49 797816 : static WokWord word_of_ident(const char *s, u32 len) {
50 : #define EQ(lit, w) \
51 : if (memcmp(s, lit, sizeof lit - 1) == 0) return w
52 797816 : switch (len) {
53 68152 : case 2:
54 68152 : EQ("as", WW_AS);
55 62967 : EQ("in", WW_IN);
56 52250 : EQ("if", WW_IF);
57 50728 : EQ("of", WW_OF);
58 : return WW_NONE;
59 124389 : case 3:
60 124389 : EQ("let", WW_LET);
61 111909 : EQ("var", WW_VAR);
62 107549 : EQ("use", WW_USE);
63 105415 : EQ("own", WW_OWN);
64 104912 : EQ("eff", WW_EFF);
65 103070 : EQ("row", WW_ROW);
66 : return WW_NONE;
67 137338 : case 4:
68 137338 : EQ("type", WW_TYPE);
69 126124 : EQ("case", WW_CASE);
70 115584 : EQ("then", WW_THEN);
71 114062 : EQ("else", WW_ELSE);
72 112546 : EQ("with", WW_WITH);
73 99954 : EQ("once", WW_ONCE);
74 99844 : EQ("copy", WW_COPY);
75 99369 : EQ("lend", WW_LEND);
76 98893 : EQ("left", WW_LEFT);
77 95159 : EQ("than", WW_THAN);
78 : return WW_NONE;
79 48766 : case 5:
80 48766 : EQ("abort", WW_ABORT);
81 47328 : EQ("alias", WW_ALIAS);
82 44903 : EQ("class", WW_CLASS);
83 42829 : EQ("where", WW_WHERE);
84 36947 : EQ("right", WW_RIGHT);
85 : return WW_NONE;
86 107984 : case 6:
87 107984 : EQ("module", WW_MODULE);
88 86126 : EQ("import", WW_IMPORT);
89 66108 : EQ("effect", WW_EFFECT);
90 51131 : EQ("handle", WW_HANDLE);
91 39243 : EQ("return", WW_RETURN);
92 33998 : EQ("extern", WW_EXTERN);
93 30569 : EQ("fixity", WW_FIXITY);
94 24807 : EQ("looser", WW_LOOSER);
95 : return WW_NONE;
96 39482 : case 7:
97 39482 : EQ("foreign", WW_FOREIGN);
98 37540 : EQ("handler", WW_HANDLER);
99 25550 : EQ("tighter", WW_TIGHTER);
100 : return WW_NONE;
101 11008 : case 8:
102 11008 : EQ("instance", WW_INSTANCE);
103 : return WW_NONE;
104 : default:
105 : return WW_NONE;
106 : }
107 : #undef EQ
108 : }
109 :
110 : // ------------------------------------------------- character classes
111 : //
112 : // The symbol charset is written ONCE, here, as a bitmap. Writing it a second
113 : // time -- as the negated character class of a line-comment regexp, say -- is
114 : // how `-->` silently becomes a comment when a character is added to one copy
115 : // and not the other. The line-comment rule below takes the maximal run first
116 : // and then asks whether it is all dashes, so there is no second copy.
117 :
118 : #define BIT(c) (UINT64_C(1) << ((c) & 63))
119 :
120 : static constexpr u64 CC_SYM_LO = // bytes 0..63
121 : BIT('!') | BIT('#') | BIT('$') | BIT('%') | BIT('&') | BIT('*') |
122 : BIT('+') | BIT('-') | BIT('/') | BIT(':') | BIT('<') | BIT('=') |
123 : BIT('>') | BIT('?');
124 : static constexpr u64 CC_SYM_HI = // bytes 64..127
125 : BIT('@') | BIT('^') | BIT('|') | BIT('~');
126 :
127 4033014 : WOK_PURE static bool is_sym(unsigned char c) {
128 4033014 : if (c < 64) return ((CC_SYM_LO >> c) & 1u) != 0;
129 1581158 : if (c < 128) return ((CC_SYM_HI >> (c - 64)) & 1u) != 0;
130 : return false;
131 : }
132 :
133 : // ASCII by decision, not by accident: `unicode.IsLower` would silently admit
134 : // `e-acute` and `lambda` as identifier heads. Widening is three lines here and
135 : // is a language decision, not a cleanup.
136 5221964 : WOK_PURE static bool is_lower(unsigned char c) { return c >= 'a' && c <= 'z'; }
137 2946922 : WOK_PURE static bool is_upper(unsigned char c) { return c >= 'A' && c <= 'Z'; }
138 1550695 : WOK_PURE static bool is_digit(unsigned char c) { return c >= '0' && c <= '9'; }
139 5221964 : WOK_PURE static bool is_ident_start(unsigned char c) {
140 5221964 : return is_lower(c) || is_upper(c) || c == '_';
141 : }
142 5221708 : WOK_PURE static bool is_ident_cont(unsigned char c) {
143 5221708 : return is_ident_start(c) || is_digit(c) || c == '\'';
144 : }
145 :
146 : // Exposed so test/test_charclass.c can check all 256 bytes against the
147 : // readable definitions rather than trusting the bitmap.
148 7212 : bool wok_test_is_sym(unsigned char c) { return is_sym(c); }
149 256 : bool wok_test_is_ident_start(unsigned char c) { return is_ident_start(c); }
150 784 : bool wok_test_is_ident_cont(unsigned char c) { return is_ident_cont(c); }
151 :
152 : // wok_kind_is_open_bracket / wok_kind_is_close_bracket /
153 : // wok_token_is_continuation_lead live in wok_token.h as static inline: they
154 : // are asked once per token, and profiling showed the calls themselves on the
155 : // clock (~5% of a parse), which one compare per question does not deserve.
156 :
157 :
158 : // ------------------------------------------------------------- scanning
159 :
160 : typedef struct {
161 : const char *src;
162 : usize n, i;
163 : u32 col;
164 : bool line_pending;
165 : bool tab_reported_this_line;
166 : WokToken *tok;
167 : usize ntok, captok;
168 : WokComment *com;
169 : usize ncom, capcom;
170 : WokArena *arena;
171 : WokDiagSink *diag;
172 : } Scanner;
173 :
174 2495920 : static void emit(Scanner *s, WokKind k, WokWord w, u32 off, u32 len,
175 : u32 col, u16 extra) {
176 2495920 : if (s->ntok == s->captok) {
177 6990 : usize next = s->captok ? s->captok * 2 : 256;
178 6990 : WokToken *grown = WOK_NEW_N(s->arena, WokToken, next);
179 6990 : if (s->ntok) memcpy(grown, s->tok, s->ntok * sizeof *grown);
180 6990 : s->tok = grown;
181 6990 : s->captok = next;
182 : }
183 2495920 : u16 flags = extra;
184 2495920 : if (s->line_pending) flags |= WOK_TF_FIRST_ON_LINE;
185 2495920 : s->tok[s->ntok++] = (WokToken){.off = off,
186 : .len = len,
187 : .col = col,
188 : .kind = (u8)k,
189 : .word = (u8)w,
190 : .flags = flags};
191 2495920 : s->line_pending = false;
192 2495920 : }
193 :
194 151358 : static void add_comment(Scanner *s, u32 off, u32 len, bool block) {
195 151358 : if (s->ncom == s->capcom) {
196 31662 : usize next = s->capcom ? s->capcom * 2 : 32;
197 31662 : WokComment *grown = WOK_NEW_N(s->arena, WokComment, next);
198 31662 : if (s->ncom) memcpy(grown, s->com, s->ncom * sizeof *grown);
199 31662 : s->com = grown;
200 31662 : s->capcom = next;
201 : }
202 151358 : s->com[s->ncom++] = (WokComment){.off = off, .len = len, .block = block};
203 151358 : }
204 :
205 17614139 : static void advance(Scanner *s) {
206 17614139 : if (s->src[s->i] == '\n') {
207 566765 : s->col = 1;
208 566765 : s->line_pending = true;
209 566765 : s->tab_reported_this_line = false;
210 : } else {
211 17047374 : s->col++;
212 : }
213 17614139 : s->i++;
214 17614139 : }
215 :
216 164 : static void advance_by(Scanner *s, usize k) {
217 492 : for (usize j = 0; j < k && s->i < s->n; j++) advance(s);
218 164 : }
219 :
220 : // Whole-buffer UTF-8 validation, once, up front. wok's String is flat
221 : // valid-only UTF-8 (the Slice E design), so admitting an ill-formed literal
222 : // here would push the fault all the way to the runtime.
223 : // Validation happens HERE and only here: once, when the file is read.
224 : // Everything downstream is UTF-8 clean by construction.
225 47765 : static void validate_utf8(const char *src, usize n, WokDiagSink *d) {
226 47765 : const unsigned char *p = (const unsigned char *)src;
227 47765 : usize i = 0;
228 376894 : while (i < n) {
229 374539 : usize bad = i + wok_utf8_find_invalid(p + i, n - i);
230 374539 : if (bad >= n) break;
231 329129 : wok_diag_add(d, WOK_E_LEX_UTF8, (u32)bad, 1,
232 329129 : "invalid UTF-8 at byte 0x%02x", p[bad]);
233 329129 : i = bad + 1; // resync one byte at a time
234 : }
235 47765 : }
236 :
237 : // A nested block comment. `{- a {- b -} c -}` closes correctly.
238 136 : static void skip_block_comment(Scanner *s) {
239 136 : u32 off = (u32)s->i;
240 136 : u32 depth = 0;
241 23862 : while (s->i < s->n) {
242 23752 : if (s->i + 1 < s->n && s->src[s->i] == '{' && s->src[s->i + 1] == '-') {
243 137 : depth++;
244 137 : advance_by(s, 2);
245 23615 : } else if (s->i + 1 < s->n && s->src[s->i] == '-' &&
246 572 : s->src[s->i + 1] == '}') {
247 27 : depth--;
248 27 : advance_by(s, 2);
249 27 : if (depth == 0) break;
250 : } else {
251 23588 : advance(s);
252 : }
253 : }
254 136 : if (depth != 0)
255 110 : wok_diag_add(s->diag, WOK_E_LEX_UNTERMINATED, off, 2,
256 : "unterminated block comment");
257 136 : add_comment(s, off, (u32)s->i - off, true);
258 136 : }
259 :
260 21787 : static void scan_literal(Scanner *s, char quote) {
261 21787 : u32 off = (u32)s->i, col = s->col;
262 21787 : u16 extra = 0;
263 21787 : advance(s);
264 21787 : bool closed = false;
265 329276 : while (s->i < s->n && s->src[s->i] != '\n') {
266 326179 : char c = s->src[s->i];
267 326179 : if (c == '\\') {
268 6493 : extra |= WOK_TF_HAS_ESCAPE;
269 6493 : u32 esc = (u32)s->i;
270 6493 : advance(s);
271 6493 : if (s->i >= s->n) break;
272 6486 : char e = s->src[s->i];
273 6486 : if (e == '\\' || e == '"' || e == '\'' || e == 'n' || e == 't' ||
274 : e == 'r' || e == '0') {
275 5505 : advance(s);
276 : } else if (e == 'x') {
277 6 : advance(s);
278 6 : int hex = 0;
279 10 : while (hex < 2 && s->i < s->n &&
280 9 : ((s->src[s->i] >= '0' && s->src[s->i] <= '9') ||
281 : (s->src[s->i] >= 'a' && s->src[s->i] <= 'f') ||
282 : (s->src[s->i] >= 'A' && s->src[s->i] <= 'F'))) {
283 4 : advance(s);
284 4 : hex++;
285 : }
286 6 : if (hex != 2)
287 5 : wok_diag_add(s->diag, WOK_E_LEX_STRAY, esc, 2,
288 : "`\\x` needs exactly two hex digits");
289 : } else {
290 : // HEX, never the raw byte: a diagnostic message must not smuggle
291 : // source bytes into a UTF-8 context downstream.
292 975 : if ((unsigned char)e < 0x80 && e > 0x20)
293 318 : wok_diag_add(s->diag, WOK_E_LEX_STRAY, esc, 2,
294 : "unknown escape `\\%c`", e);
295 : else
296 657 : wok_diag_add(s->diag, WOK_E_LEX_STRAY, esc, 2,
297 657 : "unknown escape `\\x%02x`", (unsigned char)e);
298 975 : advance(s);
299 : }
300 6486 : continue;
301 : }
302 319686 : if (c == quote) {
303 18683 : advance(s);
304 18683 : closed = true;
305 18683 : break;
306 : }
307 301003 : advance(s);
308 : }
309 18683 : if (!closed)
310 4194 : wok_diag_add(s->diag, WOK_E_LEX_UNTERMINATED, off, 1,
311 : "unterminated %s literal",
312 : quote == '"' ? "string" : "character");
313 21787 : emit(s, quote == '"' ? WT_STRING : WT_CHAR, WW_NONE, off,
314 21787 : (u32)s->i - off, col, extra);
315 21787 : }
316 :
317 : // A reserved operator run, recognised AFTER the maximal run is taken. Peeking
318 : // at prefixes instead would make `->>` lex as `->` followed by `>`.
319 421912 : static WokKind reserved_sym(const char *s, u32 len) {
320 421912 : if (len == 1) {
321 296699 : switch (s[0]) {
322 : case '=': return WT_EQUALS;
323 102603 : case ':': return WT_COLON;
324 11489 : case '|': return WT_BAR;
325 75270 : default: return WT_VARSYM;
326 : }
327 : }
328 125213 : if (len == 2) {
329 120491 : if (s[0] == '-' && s[1] == '>') return WT_ARROW;
330 23737 : if (s[0] == '=' && s[1] == '>') return WT_FATARROW;
331 17220 : if (s[0] == ':' && s[1] == ':') return WT_COLONCOLON;
332 13083 : if (s[0] == ':' && s[1] == '=') return WT_ASSIGN;
333 : }
334 : return WT_VARSYM;
335 : }
336 :
337 47765 : WokScanResult wok_scan(const char *src, usize src_len, WokArena *arena,
338 : WokDiagSink *diag) {
339 47765 : validate_utf8(src, src_len, diag);
340 :
341 47765 : Scanner s = {.src = src,
342 : .n = src_len,
343 : .i = 0,
344 : .col = 1,
345 : .line_pending = true,
346 : .arena = arena,
347 : .diag = diag};
348 : // One token per four source bytes: a file is scanned without regrowth.
349 47765 : s.captok = src_len / 4 + 16;
350 47765 : s.tok = WOK_NEW_N(arena, WokToken, s.captok);
351 :
352 5041453 : while (s.i < s.n) {
353 4993688 : unsigned char c = (unsigned char)s.src[s.i];
354 :
355 4993688 : if (c == ' ' || c == '\n' || c == '\r') {
356 2391007 : advance(&s);
357 2391007 : continue;
358 : }
359 2602681 : if (c == '\t') {
360 : // A tab in indentation is an invisible disagreement between editors and
361 : // has no defensible width under an offside rule. Elsewhere it is fine.
362 3168 : if (s.line_pending && !s.tab_reported_this_line) {
363 416 : wok_diag_add(diag, WOK_E_LEX_TAB, (u32)s.i, 1,
364 : "tab in indentation; use spaces (a tab has no width "
365 : "under the offside rule)");
366 416 : s.tab_reported_this_line = true;
367 : }
368 3168 : advance(&s);
369 3168 : continue;
370 : }
371 2599513 : if (c == '{' && s.i + 1 < s.n && s.src[s.i + 1] == '-') {
372 136 : skip_block_comment(&s);
373 136 : continue;
374 : }
375 :
376 2599377 : u32 off = (u32)s.i, col = s.col;
377 :
378 2599377 : if (is_sym(c)) {
379 1427595 : while (s.i < s.n && is_sym((unsigned char)s.src[s.i])) advance(&s);
380 573134 : u32 len = (u32)s.i - off;
381 573134 : bool all_dash = true;
382 1427595 : for (u32 k = 0; k < len; k++)
383 854461 : if (s.src[off + k] != '-') all_dash = false;
384 573134 : if (all_dash && len >= 2) {
385 9215325 : while (s.i < s.n && s.src[s.i] != '\n') advance(&s);
386 151222 : add_comment(&s, off, (u32)s.i - off, false);
387 151222 : continue;
388 : }
389 421912 : WokKind k = reserved_sym(s.src + off, len);
390 421912 : WokWord w = (len == 1 && s.src[off] == '+') ? WW_PLUS : WW_NONE;
391 421912 : emit(&s, k, w, off, len, col, 0);
392 421912 : continue;
393 : }
394 :
395 2026243 : switch (c) {
396 6017 : case '_':
397 : // `_` alone is the wildcard; `_foo` is an ordinary name. A deliberate
398 : // fallthrough into the identifier arm, which C23 lets us state.
399 6017 : if (!(s.i + 1 < s.n && is_ident_cont((unsigned char)s.src[s.i + 1]))) {
400 5624 : advance(&s);
401 5624 : emit(&s, WT_UNDERSCORE, WW_NONE, off, 1, col, 0);
402 5624 : continue;
403 : }
404 1165787 : [[fallthrough]];
405 : case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g':
406 : case 'h': case 'i': case 'j': case 'k': case 'l': case 'm': case 'n':
407 : case 'o': case 'p': case 'q': case 'r': case 's': case 't': case 'u':
408 : case 'v': case 'w': case 'x': case 'y': case 'z':
409 : case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': case 'G':
410 : case 'H': case 'I': case 'J': case 'K': case 'L': case 'M': case 'N':
411 : case 'O': case 'P': case 'Q': case 'R': case 'S': case 'T': case 'U':
412 1165787 : case 'V': case 'W': case 'X': case 'Y': case 'Z': {
413 1165787 : bool upper = is_upper(c);
414 5219466 : while (s.i < s.n && is_ident_cont((unsigned char)s.src[s.i]))
415 4053679 : advance(&s);
416 1165787 : u32 len = (u32)s.i - off;
417 : // Case of the first character decides ConId vs VarId. spec 1.6's
418 : // governing invariant -- a capitalized name is never a fresh binder --
419 : // is a LEXICAL fact here, so no later pass inspects a first character.
420 1165787 : WokWord w = upper ? WW_NONE : word_of_ident(s.src + off, len);
421 797816 : WokKind k = upper ? WT_CONID : (w ? wok_word_kind(w) : WT_VARID);
422 1165787 : emit(&s, k, w, off, len, col, 0);
423 1165787 : continue;
424 : }
425 : case '0': case '1': case '2': case '3': case '4':
426 : case '5': case '6': case '7': case '8': case '9': {
427 191188 : while (s.i < s.n && (is_digit((unsigned char)s.src[s.i]) ||
428 : s.src[s.i] == '_'))
429 109686 : advance(&s);
430 81502 : emit(&s, WT_INT, WW_NONE, off, (u32)s.i - off, col, 0);
431 81502 : continue;
432 : }
433 21787 : case '"':
434 : case '\'':
435 21787 : scan_literal(&s, (char)c);
436 21787 : continue;
437 30247 : case '.': {
438 30247 : advance(&s);
439 30247 : if (s.i < s.n && s.src[s.i] == '.') {
440 2496 : advance(&s);
441 2496 : emit(&s, WT_DOTDOT, WW_NONE, off, 2, col, 0);
442 : } else {
443 27751 : emit(&s, WT_DOT, WW_NONE, off, 1, col, 0);
444 : }
445 30247 : continue;
446 : }
447 2539 : case ';':
448 2539 : advance(&s);
449 2539 : emit(&s, WT_SEMI, WW_NONE, off, 1, col, 0);
450 : // Legal v1 wok that a port will hit, so it earns a real message
451 : // rather than "unexpected character" (D22).
452 2539 : wok_diag_add(diag, WOK_E_LEX_SEMI, off, 1,
453 : "v2 has no `;`: a block's items are delimited by columns "
454 : "alone");
455 2539 : continue;
456 : default:
457 718757 : break;
458 : }
459 :
460 718757 : WokKind k;
461 718757 : switch (c) {
462 : case '(': k = WT_LPAREN; break;
463 132536 : case ')': k = WT_RPAREN; break;
464 23924 : case '[': k = WT_LBRACKET; break;
465 23567 : case ']': k = WT_RBRACKET; break;
466 12234 : case '{': k = WT_LBRACE; break;
467 12268 : case '}': k = WT_RBRACE; break;
468 56236 : case ',': k = WT_COMMA; break;
469 8177 : case '`': k = WT_BACKTICK; break;
470 6399 : case '\\': k = WT_LAMBDA; break;
471 310087 : default: k = WT_BAD; break;
472 : }
473 718757 : advance(&s);
474 718757 : emit(&s, k, WW_NONE, off, 1, col, 0);
475 718757 : if (k == WT_BAD)
476 310087 : wok_diag_add(diag, WOK_E_LEX_STRAY, off, 1,
477 : "stray byte 0x%02x in source", c);
478 : }
479 :
480 47765 : emit(&s, WT_EOF, WW_NONE, (u32)s.n, 0, s.col, 0);
481 47765 : return (WokScanResult){.tokens = {.tok = s.tok, .n = s.ntok},
482 47765 : .comments = s.com,
483 47765 : .ncomments = s.ncom};
484 : }
485 :
486 : // ------------------------------------------------------- literal values
487 :
488 18945 : bool wok_token_int_value(const char *src, const WokToken *t, WokDiagSink *diag,
489 : u64 *out) {
490 18945 : u64 acc = 0;
491 18945 : bool overflow = false;
492 49163 : for (u32 k = 0; k < t->len; k++) {
493 30218 : char c = src[t->off + k];
494 30218 : if (c == '_') continue;
495 : #if WOK_HAVE_CKDINT
496 : // Integer literal conversion is where parsers get CVEs. This is a
497 : // defect-class elimination, not a stylistic improvement.
498 30218 : overflow |= ckd_mul(&acc, acc, (u64)10);
499 30218 : overflow |= ckd_add(&acc, acc, (u64)(c - '0'));
500 : #else
501 : if (acc > (UINT64_MAX - (u64)(c - '0')) / 10) overflow = true;
502 : acc = acc * 10 + (u64)(c - '0');
503 : #endif
504 : }
505 18945 : if (overflow) {
506 2 : wok_diag_add(diag, WOK_E_LEX_INT_RANGE, t->off, t->len,
507 : "integer literal does not fit in U64");
508 2 : *out = 0;
509 2 : return false;
510 : }
511 18943 : *out = acc;
512 18943 : return true;
513 : }
|
