Line data Source code
1 : // Copyright 2018 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_PARSING_SCANNER_INL_H_
6 : #define V8_PARSING_SCANNER_INL_H_
7 :
8 : #include "src/char-predicates-inl.h"
9 : #include "src/parsing/keywords-gen.h"
10 : #include "src/parsing/scanner.h"
11 :
12 : namespace v8 {
13 : namespace internal {
14 :
15 : // ----------------------------------------------------------------------------
16 : // Keyword Matcher
17 :
18 : #define KEYWORDS(KEYWORD_GROUP, KEYWORD) \
19 : KEYWORD_GROUP('a') \
20 : KEYWORD("async", Token::ASYNC) \
21 : KEYWORD("await", Token::AWAIT) \
22 : KEYWORD_GROUP('b') \
23 : KEYWORD("break", Token::BREAK) \
24 : KEYWORD_GROUP('c') \
25 : KEYWORD("case", Token::CASE) \
26 : KEYWORD("catch", Token::CATCH) \
27 : KEYWORD("class", Token::CLASS) \
28 : KEYWORD("const", Token::CONST) \
29 : KEYWORD("continue", Token::CONTINUE) \
30 : KEYWORD_GROUP('d') \
31 : KEYWORD("debugger", Token::DEBUGGER) \
32 : KEYWORD("default", Token::DEFAULT) \
33 : KEYWORD("delete", Token::DELETE) \
34 : KEYWORD("do", Token::DO) \
35 : KEYWORD_GROUP('e') \
36 : KEYWORD("else", Token::ELSE) \
37 : KEYWORD("enum", Token::ENUM) \
38 : KEYWORD("export", Token::EXPORT) \
39 : KEYWORD("extends", Token::EXTENDS) \
40 : KEYWORD_GROUP('f') \
41 : KEYWORD("false", Token::FALSE_LITERAL) \
42 : KEYWORD("finally", Token::FINALLY) \
43 : KEYWORD("for", Token::FOR) \
44 : KEYWORD("function", Token::FUNCTION) \
45 : KEYWORD_GROUP('g') \
46 : KEYWORD("get", Token::GET) \
47 : KEYWORD_GROUP('i') \
48 : KEYWORD("if", Token::IF) \
49 : KEYWORD("implements", Token::FUTURE_STRICT_RESERVED_WORD) \
50 : KEYWORD("import", Token::IMPORT) \
51 : KEYWORD("in", Token::IN) \
52 : KEYWORD("instanceof", Token::INSTANCEOF) \
53 : KEYWORD("interface", Token::FUTURE_STRICT_RESERVED_WORD) \
54 : KEYWORD_GROUP('l') \
55 : KEYWORD("let", Token::LET) \
56 : KEYWORD_GROUP('n') \
57 : KEYWORD("new", Token::NEW) \
58 : KEYWORD("null", Token::NULL_LITERAL) \
59 : KEYWORD_GROUP('p') \
60 : KEYWORD("package", Token::FUTURE_STRICT_RESERVED_WORD) \
61 : KEYWORD("private", Token::FUTURE_STRICT_RESERVED_WORD) \
62 : KEYWORD("protected", Token::FUTURE_STRICT_RESERVED_WORD) \
63 : KEYWORD("public", Token::FUTURE_STRICT_RESERVED_WORD) \
64 : KEYWORD_GROUP('r') \
65 : KEYWORD("return", Token::RETURN) \
66 : KEYWORD_GROUP('s') \
67 : KEYWORD("set", Token::SET) \
68 : KEYWORD("static", Token::STATIC) \
69 : KEYWORD("super", Token::SUPER) \
70 : KEYWORD("switch", Token::SWITCH) \
71 : KEYWORD_GROUP('t') \
72 : KEYWORD("this", Token::THIS) \
73 : KEYWORD("throw", Token::THROW) \
74 : KEYWORD("true", Token::TRUE_LITERAL) \
75 : KEYWORD("try", Token::TRY) \
76 : KEYWORD("typeof", Token::TYPEOF) \
77 : KEYWORD_GROUP('v') \
78 : KEYWORD("var", Token::VAR) \
79 : KEYWORD("void", Token::VOID) \
80 : KEYWORD_GROUP('w') \
81 : KEYWORD("while", Token::WHILE) \
82 : KEYWORD("with", Token::WITH) \
83 : KEYWORD_GROUP('y') \
84 : KEYWORD("yield", Token::YIELD)
85 :
86 : constexpr bool IsKeywordStart(char c) {
87 : #define KEYWORD_GROUP_CHECK(ch) c == ch ||
88 : #define KEYWORD_CHECK(keyword, token)
89 : return KEYWORDS(KEYWORD_GROUP_CHECK, KEYWORD_CHECK) /* || */ false;
90 : #undef KEYWORD_GROUP_CHECK
91 : #undef KEYWORD_CHECK
92 : }
93 :
94 : V8_INLINE Token::Value KeywordOrIdentifierToken(const uint8_t* input,
95 : int input_length) {
96 : DCHECK_GE(input_length, 1);
97 : return PerfectKeywordHash::GetToken(reinterpret_cast<const char*>(input),
98 77064244 : input_length);
99 : }
100 :
101 : // Recursive constexpr template magic to check if a character is in a given
102 : // string.
103 : template <int N>
104 : constexpr bool IsInString(const char (&s)[N], char c, size_t i = 0) {
105 : return i >= N ? false : s[i] == c ? true : IsInString(s, c, i + 1);
106 : }
107 :
108 : inline constexpr bool CanBeKeywordCharacter(char c) {
109 : return IsInString(
110 : #define KEYWORD_GROUP_CASE(ch) // Nothing
111 : #define KEYWORD(keyword, token) keyword
112 : // Use C string literal concatenation ("a" "b" becomes "ab") to build one
113 : // giant string containing all the keywords.
114 : KEYWORDS(KEYWORD_GROUP_CASE, KEYWORD)
115 : #undef KEYWORD
116 : #undef KEYWORD_GROUP_CASE
117 : ,
118 : c);
119 : }
120 :
121 : // Make sure tokens are stored as a single byte.
122 : STATIC_ASSERT(sizeof(Token::Value) == 1);
123 :
124 : // Get the shortest token that this character starts, the token may change
125 : // depending on subsequent characters.
126 : constexpr Token::Value GetOneCharToken(char c) {
127 : // clang-format off
128 : return
129 : c == '(' ? Token::LPAREN :
130 : c == ')' ? Token::RPAREN :
131 : c == '{' ? Token::LBRACE :
132 : c == '}' ? Token::RBRACE :
133 : c == '[' ? Token::LBRACK :
134 : c == ']' ? Token::RBRACK :
135 : c == '?' ? Token::CONDITIONAL :
136 : c == ':' ? Token::COLON :
137 : c == ';' ? Token::SEMICOLON :
138 : c == ',' ? Token::COMMA :
139 : c == '.' ? Token::PERIOD :
140 : c == '|' ? Token::BIT_OR :
141 : c == '&' ? Token::BIT_AND :
142 : c == '^' ? Token::BIT_XOR :
143 : c == '~' ? Token::BIT_NOT :
144 : c == '!' ? Token::NOT :
145 : c == '<' ? Token::LT :
146 : c == '>' ? Token::GT :
147 : c == '%' ? Token::MOD :
148 : c == '=' ? Token::ASSIGN :
149 : c == '+' ? Token::ADD :
150 : c == '-' ? Token::SUB :
151 : c == '*' ? Token::MUL :
152 : c == '/' ? Token::DIV :
153 : c == '#' ? Token::PRIVATE_NAME :
154 : c == '"' ? Token::STRING :
155 : c == '\'' ? Token::STRING :
156 : c == '`' ? Token::TEMPLATE_SPAN :
157 : c == '\\' ? Token::IDENTIFIER :
158 : // Whitespace or line terminator
159 : c == ' ' ? Token::WHITESPACE :
160 : c == '\t' ? Token::WHITESPACE :
161 : c == '\v' ? Token::WHITESPACE :
162 : c == '\f' ? Token::WHITESPACE :
163 : c == '\r' ? Token::WHITESPACE :
164 : c == '\n' ? Token::WHITESPACE :
165 : // IsDecimalDigit must be tested before IsAsciiIdentifier
166 : IsDecimalDigit(c) ? Token::NUMBER :
167 : IsAsciiIdentifier(c) ? Token::IDENTIFIER :
168 : Token::ILLEGAL;
169 : // clang-format on
170 : }
171 :
172 : // Table of one-character tokens, by character (0x00..0x7F only).
173 : static const constexpr Token::Value one_char_tokens[128] = {
174 : #define CALL_GET_SCAN_FLAGS(N) GetOneCharToken(N),
175 : INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
176 : #undef CALL_GET_SCAN_FLAGS
177 : };
178 :
179 : #undef KEYWORDS
180 :
181 131402920 : V8_INLINE Token::Value Scanner::ScanIdentifierOrKeyword() {
182 131402920 : next().literal_chars.Start();
183 : return ScanIdentifierOrKeywordInner();
184 : }
185 :
186 : // Character flags for the fast path of scanning a keyword or identifier token.
187 : enum class ScanFlags : uint8_t {
188 : kTerminatesLiteral = 1 << 0,
189 : // "Cannot" rather than "can" so that this flag can be ORed together across
190 : // multiple characters.
191 : kCannotBeKeyword = 1 << 1,
192 : kCannotBeKeywordStart = 1 << 2,
193 : kStringTerminator = 1 << 3,
194 : kNeedsSlowPath = 1 << 4,
195 : };
196 : constexpr uint8_t GetScanFlags(char c) {
197 : return
198 : // Keywords are all lowercase and only contain letters.
199 : // Note that non-identifier characters do not set this flag, so
200 : // that it plays well with kTerminatesLiteral.
201 : (IsAsciiIdentifier(c) && !CanBeKeywordCharacter(c)
202 : ? static_cast<uint8_t>(ScanFlags::kCannotBeKeyword)
203 : : 0) |
204 : (IsKeywordStart(c)
205 : ? 0
206 : : static_cast<uint8_t>(ScanFlags::kCannotBeKeywordStart)) |
207 : // Anything that isn't an identifier character will terminate the
208 : // literal, or at least terminates the literal fast path processing
209 : // (like an escape).
210 : (!IsAsciiIdentifier(c)
211 : ? static_cast<uint8_t>(ScanFlags::kTerminatesLiteral)
212 : : 0) |
213 : // Possible string termination characters.
214 : ((c == '\'' || c == '"' || c == '\n' || c == '\r' || c == '\\')
215 : ? static_cast<uint8_t>(ScanFlags::kStringTerminator)
216 : : 0) |
217 : // Escapes are processed on the slow path.
218 : (c == '\\' ? static_cast<uint8_t>(ScanFlags::kNeedsSlowPath) : 0);
219 : }
220 : inline bool TerminatesLiteral(uint8_t scan_flags) {
221 786846535 : return (scan_flags & static_cast<uint8_t>(ScanFlags::kTerminatesLiteral));
222 : }
223 131443181 : inline bool CanBeKeyword(uint8_t scan_flags) {
224 131499044 : return !(scan_flags & static_cast<uint8_t>(ScanFlags::kCannotBeKeyword));
225 : }
226 131442996 : inline bool NeedsSlowPath(uint8_t scan_flags) {
227 131442996 : return (scan_flags & static_cast<uint8_t>(ScanFlags::kNeedsSlowPath));
228 : }
229 : inline bool MayTerminateString(uint8_t scan_flags) {
230 187653867 : return (scan_flags & static_cast<uint8_t>(ScanFlags::kStringTerminator));
231 : }
232 : // Table of precomputed scan flags for the 128 ASCII characters, for branchless
233 : // flag calculation during the scan.
234 : static constexpr const uint8_t character_scan_flags[128] = {
235 : #define CALL_GET_SCAN_FLAGS(N) GetScanFlags(N),
236 : INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
237 : #undef CALL_GET_SCAN_FLAGS
238 : };
239 :
240 2836 : inline bool CharCanBeKeyword(uc32 c) {
241 112363 : return static_cast<uint32_t>(c) < arraysize(character_scan_flags) &&
242 58699 : CanBeKeyword(character_scan_flags[c]);
243 : }
244 :
245 208453310 : V8_INLINE Token::Value Scanner::ScanIdentifierOrKeywordInner() {
246 : DCHECK(IsIdentifierStart(c0_));
247 : bool escaped = false;
248 : bool can_be_keyword = true;
249 :
250 : STATIC_ASSERT(arraysize(character_scan_flags) == kMaxAscii + 1);
251 131464860 : if (V8_LIKELY(static_cast<uint32_t>(c0_) <= kMaxAscii)) {
252 131441813 : if (V8_LIKELY(c0_ != '\\')) {
253 131417202 : uint8_t scan_flags = character_scan_flags[c0_];
254 : DCHECK(!TerminatesLiteral(scan_flags));
255 : STATIC_ASSERT(static_cast<uint8_t>(ScanFlags::kCannotBeKeywordStart) ==
256 : static_cast<uint8_t>(ScanFlags::kCannotBeKeyword) << 1);
257 131417202 : scan_flags >>= 1;
258 : // Make sure the shifting above doesn't set NeedsSlowPath. Otherwise we'll
259 : // fall into the slow path after scanning the identifier.
260 : DCHECK(!NeedsSlowPath(scan_flags));
261 : AddLiteralChar(static_cast<char>(c0_));
262 786846882 : AdvanceUntil([this, &scan_flags](uc32 c0) {
263 786846882 : if (V8_UNLIKELY(static_cast<uint32_t>(c0) > kMaxAscii)) {
264 : // A non-ascii character means we need to drop through to the slow
265 : // path.
266 : // TODO(leszeks): This would be most efficient as a goto to the slow
267 : // path, check codegen and maybe use a bool instead.
268 347 : scan_flags |= static_cast<uint8_t>(ScanFlags::kNeedsSlowPath);
269 347 : return true;
270 : }
271 786846535 : uint8_t char_flags = character_scan_flags[c0];
272 786846535 : scan_flags |= char_flags;
273 786846535 : if (TerminatesLiteral(char_flags)) {
274 : return true;
275 : } else {
276 655766711 : AddLiteralChar(static_cast<char>(c0));
277 655739148 : return false;
278 : }
279 : });
280 :
281 131445430 : if (V8_LIKELY(!NeedsSlowPath(scan_flags))) {
282 131432239 : if (!CanBeKeyword(scan_flags)) return Token::IDENTIFIER;
283 : // Could be a keyword or identifier.
284 77053471 : Vector<const uint8_t> chars = next().literal_chars.one_byte_literal();
285 77050437 : return KeywordOrIdentifierToken(chars.start(), chars.length());
286 : }
287 :
288 13488 : can_be_keyword = CanBeKeyword(scan_flags);
289 : } else {
290 : // Special case for escapes at the start of an identifier.
291 : escaped = true;
292 24611 : uc32 c = ScanIdentifierUnicodeEscape();
293 : DCHECK(!IsIdentifierStart(-1));
294 24611 : if (c == '\\' || !IsIdentifierStart(c)) {
295 : return Token::ILLEGAL;
296 : }
297 : AddLiteralChar(c);
298 2836 : can_be_keyword = CharCanBeKeyword(c);
299 : }
300 : }
301 :
302 39371 : return ScanIdentifierOrKeywordInnerSlow(escaped, can_be_keyword);
303 : }
304 :
305 730032787 : V8_INLINE Token::Value Scanner::SkipWhiteSpace() {
306 170514443 : int start_position = source_pos();
307 :
308 : // We won't skip behind the end of input.
309 : DCHECK(!IsWhiteSpaceOrLineTerminator(kEndOfInput));
310 :
311 : // Advance as long as character is a WhiteSpace or LineTerminator.
312 522275706 : while (IsWhiteSpaceOrLineTerminator(c0_)) {
313 524680148 : if (!next().after_line_terminator && unibrow::IsLineTerminator(c0_)) {
314 37225228 : next().after_line_terminator = true;
315 : }
316 351796320 : Advance();
317 : }
318 :
319 : // Return whether or not we skipped any characters.
320 170490483 : if (source_pos() == start_position) {
321 : DCHECK_NE('0', c0_);
322 : return Token::ILLEGAL;
323 : }
324 :
325 : return Token::WHITESPACE;
326 : }
327 :
328 1201131012 : V8_INLINE Token::Value Scanner::ScanSingleToken() {
329 : Token::Value token;
330 177662195 : do {
331 1133646618 : next().location.beg_pos = source_pos();
332 :
333 567483905 : if (V8_LIKELY(static_cast<unsigned>(c0_) <= kMaxAscii)) {
334 562663894 : token = one_char_tokens[c0_];
335 :
336 562663894 : switch (token) {
337 : case Token::LPAREN:
338 : case Token::RPAREN:
339 : case Token::LBRACE:
340 : case Token::RBRACE:
341 : case Token::LBRACK:
342 : case Token::RBRACK:
343 : case Token::CONDITIONAL:
344 : case Token::COLON:
345 : case Token::SEMICOLON:
346 : case Token::COMMA:
347 : case Token::BIT_NOT:
348 : case Token::ILLEGAL:
349 : // One character tokens.
350 157199780 : return Select(token);
351 :
352 : case Token::STRING:
353 10352863 : return ScanString();
354 :
355 : case Token::LT:
356 : // < <= << <<= <!--
357 1034201 : Advance();
358 1034154 : if (c0_ == '=') return Select(Token::LTE);
359 952216 : if (c0_ == '<') return Select('=', Token::ASSIGN_SHL, Token::SHL);
360 528890 : if (c0_ == '!') {
361 72 : token = ScanHtmlComment();
362 : continue;
363 : }
364 : return Token::LT;
365 :
366 : case Token::GT:
367 : // > >= >> >>= >>> >>>=
368 524035 : Advance();
369 524023 : if (c0_ == '=') return Select(Token::GTE);
370 494824 : if (c0_ == '>') {
371 : // >> >>= >>> >>>=
372 261080 : Advance();
373 261082 : if (c0_ == '=') return Select(Token::ASSIGN_SAR);
374 255949 : if (c0_ == '>') return Select('=', Token::ASSIGN_SHR, Token::SHR);
375 : return Token::SAR;
376 : }
377 : return Token::GT;
378 :
379 : case Token::ASSIGN:
380 : // = == === =>
381 25358715 : Advance();
382 25358863 : if (c0_ == '=') return Select('=', Token::EQ_STRICT, Token::EQ);
383 23716775 : if (c0_ == '>') return Select(Token::ARROW);
384 : return Token::ASSIGN;
385 :
386 : case Token::NOT:
387 : // ! != !==
388 2342751 : Advance();
389 2342767 : if (c0_ == '=') return Select('=', Token::NE_STRICT, Token::NE);
390 : return Token::NOT;
391 :
392 : case Token::ADD:
393 : // + ++ +=
394 4704229 : Advance();
395 4704185 : if (c0_ == '+') return Select(Token::INC);
396 3760857 : if (c0_ == '=') return Select(Token::ASSIGN_ADD);
397 : return Token::ADD;
398 :
399 : case Token::SUB:
400 : // - -- --> -=
401 808330 : Advance();
402 808287 : if (c0_ == '-') {
403 102023 : Advance();
404 102233 : if (c0_ == '>' && next().after_line_terminator) {
405 : // For compatibility with SpiderMonkey, we skip lines that
406 : // start with an HTML comment end '-->'.
407 154 : token = SkipSingleHTMLComment();
408 : continue;
409 : }
410 : return Token::DEC;
411 : }
412 706264 : if (c0_ == '=') return Select(Token::ASSIGN_SUB);
413 : return Token::SUB;
414 :
415 : case Token::MUL:
416 : // * *=
417 511480 : Advance();
418 511477 : if (c0_ == '*') return Select('=', Token::ASSIGN_EXP, Token::EXP);
419 502097 : if (c0_ == '=') return Select(Token::ASSIGN_MUL);
420 : return Token::MUL;
421 :
422 : case Token::MOD:
423 : // % %=
424 150332 : return Select('=', Token::ASSIGN_MOD, Token::MOD);
425 :
426 : case Token::DIV:
427 : // / // /* /=
428 7573802 : Advance();
429 7573756 : if (c0_ == '/') {
430 7123049 : uc32 c = Peek();
431 7123000 : if (c == '#' || c == '@') {
432 4005 : Advance();
433 4005 : Advance();
434 4005 : token = SkipSourceURLComment();
435 : continue;
436 : }
437 7118995 : token = SkipSingleLineComment();
438 : continue;
439 : }
440 450707 : if (c0_ == '*') {
441 57305 : token = SkipMultiLineComment();
442 : continue;
443 : }
444 393402 : if (c0_ == '=') return Select(Token::ASSIGN_DIV);
445 : return Token::DIV;
446 :
447 : case Token::BIT_AND:
448 : // & && &=
449 1258583 : Advance();
450 1258600 : if (c0_ == '&') return Select(Token::AND);
451 661722 : if (c0_ == '=') return Select(Token::ASSIGN_BIT_AND);
452 : return Token::BIT_AND;
453 :
454 : case Token::BIT_OR:
455 : // | || |=
456 858513 : Advance();
457 858505 : if (c0_ == '|') return Select(Token::OR);
458 380120 : if (c0_ == '=') return Select(Token::ASSIGN_BIT_OR);
459 : return Token::BIT_OR;
460 :
461 : case Token::BIT_XOR:
462 : // ^ ^=
463 18418 : return Select('=', Token::ASSIGN_BIT_XOR, Token::BIT_XOR);
464 :
465 : case Token::PERIOD:
466 : // . Number
467 14609841 : Advance();
468 14609822 : if (IsDecimalDigit(c0_)) return ScanNumber(true);
469 14606822 : if (c0_ == '.') {
470 110154 : if (Peek() == '.') {
471 109779 : Advance();
472 109777 : Advance();
473 : return Token::ELLIPSIS;
474 : }
475 : }
476 : return Token::PERIOD;
477 :
478 : case Token::TEMPLATE_SPAN:
479 75835 : Advance();
480 75836 : return ScanTemplateSpan();
481 :
482 : case Token::PRIVATE_NAME:
483 277960 : return ScanPrivateName();
484 :
485 : case Token::WHITESPACE:
486 : token = SkipWhiteSpace();
487 : continue;
488 :
489 : case Token::NUMBER:
490 33087966 : return ScanNumber(false);
491 :
492 : case Token::IDENTIFIER:
493 : return ScanIdentifierOrKeyword();
494 :
495 : default:
496 0 : UNREACHABLE();
497 : }
498 : }
499 :
500 14459712 : if (IsIdentifierStart(c0_) ||
501 4819965 : (CombineSurrogatePair() && IsIdentifierStart(c0_))) {
502 : return ScanIdentifierOrKeyword();
503 : }
504 4819767 : if (c0_ == kEndOfInput) {
505 4818766 : return source_->has_parser_error() ? Token::ILLEGAL : Token::EOS;
506 : }
507 : token = SkipWhiteSpace();
508 :
509 : // Continue scanning for tokens as long as we're just skipping whitespace.
510 : } while (token == Token::WHITESPACE);
511 :
512 : return token;
513 : }
514 :
515 389791391 : void Scanner::Scan(TokenDesc* next_desc) {
516 : DCHECK_EQ(next_desc, &next());
517 :
518 389791391 : next_desc->token = ScanSingleToken();
519 : DCHECK_IMPLIES(has_parser_error(), next_desc->token == Token::ILLEGAL);
520 389791391 : next_desc->location.end_pos = source_pos();
521 :
522 : #ifdef DEBUG
523 : SanityCheckTokenDesc(current());
524 : SanityCheckTokenDesc(next());
525 : SanityCheckTokenDesc(next_next());
526 : #endif
527 : }
528 :
529 4981748 : void Scanner::Scan() { Scan(next_); }
530 :
531 : } // namespace internal
532 : } // namespace v8
533 :
534 : #endif // V8_PARSING_SCANNER_INL_H_
|
