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 78538397 : 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 : V8_INLINE Token::Value Scanner::ScanIdentifierOrKeyword() {
182 : 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 : kIdentifierNeedsSlowPath = 1 << 4,
195 : kMultilineCommentCharacterNeedsSlowPath = 1 << 5,
196 : };
197 : constexpr uint8_t GetScanFlags(char c) {
198 : return
199 : // Keywords are all lowercase and only contain letters.
200 : // Note that non-identifier characters do not set this flag, so
201 : // that it plays well with kTerminatesLiteral.
202 : (IsAsciiIdentifier(c) && !CanBeKeywordCharacter(c)
203 : ? static_cast<uint8_t>(ScanFlags::kCannotBeKeyword)
204 : : 0) |
205 : (IsKeywordStart(c)
206 : ? 0
207 : : static_cast<uint8_t>(ScanFlags::kCannotBeKeywordStart)) |
208 : // Anything that isn't an identifier character will terminate the
209 : // literal, or at least terminates the literal fast path processing
210 : // (like an escape).
211 : (!IsAsciiIdentifier(c)
212 : ? static_cast<uint8_t>(ScanFlags::kTerminatesLiteral)
213 : : 0) |
214 : // Possible string termination characters.
215 : ((c == '\'' || c == '"' || c == '\n' || c == '\r' || c == '\\')
216 : ? static_cast<uint8_t>(ScanFlags::kStringTerminator)
217 : : 0) |
218 : // Escapes are processed on the slow path.
219 : (c == '\\' ? static_cast<uint8_t>(ScanFlags::kIdentifierNeedsSlowPath)
220 : : 0) |
221 : // Newlines and * are interesting characters for multiline comment
222 : // scanning.
223 : (c == '\n' || c == '\r' || c == '*'
224 : ? static_cast<uint8_t>(
225 : ScanFlags::kMultilineCommentCharacterNeedsSlowPath)
226 : : 0);
227 : }
228 : inline bool TerminatesLiteral(uint8_t scan_flags) {
229 : return (scan_flags & static_cast<uint8_t>(ScanFlags::kTerminatesLiteral));
230 : }
231 : inline bool CanBeKeyword(uint8_t scan_flags) {
232 13488 : return !(scan_flags & static_cast<uint8_t>(ScanFlags::kCannotBeKeyword));
233 : }
234 : inline bool IdentifierNeedsSlowPath(uint8_t scan_flags) {
235 : return (scan_flags &
236 : static_cast<uint8_t>(ScanFlags::kIdentifierNeedsSlowPath));
237 : }
238 : inline bool MultilineCommentCharacterNeedsSlowPath(uint8_t scan_flags) {
239 : return (scan_flags & static_cast<uint8_t>(
240 66627 : ScanFlags::kMultilineCommentCharacterNeedsSlowPath));
241 : }
242 : inline bool MayTerminateString(uint8_t scan_flags) {
243 : return (scan_flags & static_cast<uint8_t>(ScanFlags::kStringTerminator));
244 : }
245 : // Table of precomputed scan flags for the 128 ASCII characters, for branchless
246 : // flag calculation during the scan.
247 : static constexpr const uint8_t character_scan_flags[128] = {
248 : #define CALL_GET_SCAN_FLAGS(N) GetScanFlags(N),
249 : INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
250 : #undef CALL_GET_SCAN_FLAGS
251 : };
252 :
253 : inline bool CharCanBeKeyword(uc32 c) {
254 112376 : return static_cast<uint32_t>(c) < arraysize(character_scan_flags) &&
255 55863 : CanBeKeyword(character_scan_flags[c]);
256 : }
257 :
258 : V8_INLINE Token::Value Scanner::ScanIdentifierOrKeywordInner() {
259 : DCHECK(IsIdentifierStart(c0_));
260 : bool escaped = false;
261 : bool can_be_keyword = true;
262 :
263 : STATIC_ASSERT(arraysize(character_scan_flags) == kMaxAscii + 1);
264 133970429 : if (V8_LIKELY(static_cast<uint32_t>(c0_) <= kMaxAscii)) {
265 133968427 : if (V8_LIKELY(c0_ != '\\')) {
266 133943814 : uint8_t scan_flags = character_scan_flags[c0_];
267 : DCHECK(!TerminatesLiteral(scan_flags));
268 : STATIC_ASSERT(static_cast<uint8_t>(ScanFlags::kCannotBeKeywordStart) ==
269 : static_cast<uint8_t>(ScanFlags::kCannotBeKeyword) << 1);
270 133943814 : scan_flags >>= 1;
271 : // Make sure the shifting above doesn't set IdentifierNeedsSlowPath.
272 : // Otherwise we'll fall into the slow path after scanning the identifier.
273 : DCHECK(!IdentifierNeedsSlowPath(scan_flags));
274 : AddLiteralChar(static_cast<char>(c0_));
275 2285251750 : AdvanceUntil([this, &scan_flags](uc32 c0) {
276 806331330 : if (V8_UNLIKELY(static_cast<uint32_t>(c0) > kMaxAscii)) {
277 : // A non-ascii character means we need to drop through to the slow
278 : // path.
279 : // TODO(leszeks): This would be most efficient as a goto to the slow
280 : // path, check codegen and maybe use a bool instead.
281 : scan_flags |=
282 347 : static_cast<uint8_t>(ScanFlags::kIdentifierNeedsSlowPath);
283 347 : return true;
284 : }
285 806330983 : uint8_t char_flags = character_scan_flags[c0];
286 806330983 : scan_flags |= char_flags;
287 806330983 : if (TerminatesLiteral(char_flags)) {
288 : return true;
289 : } else {
290 : AddLiteralChar(static_cast<char>(c0));
291 672341183 : return false;
292 : }
293 : });
294 :
295 133952087 : if (V8_LIKELY(!IdentifierNeedsSlowPath(scan_flags))) {
296 133938599 : if (!CanBeKeyword(scan_flags)) return Token::IDENTIFIER;
297 : // Could be a keyword or identifier.
298 : Vector<const uint8_t> chars = next().literal_chars.one_byte_literal();
299 : return KeywordOrIdentifierToken(chars.start(), chars.length());
300 : }
301 :
302 : can_be_keyword = CanBeKeyword(scan_flags);
303 : } else {
304 : // Special case for escapes at the start of an identifier.
305 : escaped = true;
306 24613 : uc32 c = ScanIdentifierUnicodeEscape();
307 : DCHECK(!IsIdentifierStart(-1));
308 49226 : if (c == '\\' || !IsIdentifierStart(c)) {
309 : return Token::ILLEGAL;
310 : }
311 : AddLiteralChar(c);
312 : can_be_keyword = CharCanBeKeyword(c);
313 : }
314 : }
315 :
316 18328 : return ScanIdentifierOrKeywordInnerSlow(escaped, can_be_keyword);
317 : }
318 :
319 : V8_INLINE Token::Value Scanner::SkipWhiteSpace() {
320 : int start_position = source_pos();
321 :
322 : // We won't skip behind the end of input.
323 : DCHECK(!IsWhiteSpaceOrLineTerminator(kEndOfInput));
324 :
325 : // Advance as long as character is a WhiteSpace or LineTerminator.
326 1067621328 : while (IsWhiteSpaceOrLineTerminator(c0_)) {
327 536187797 : if (!next().after_line_terminator && unibrow::IsLineTerminator(c0_)) {
328 38129513 : next().after_line_terminator = true;
329 : }
330 : Advance();
331 : }
332 :
333 : // Return whether or not we skipped any characters.
334 173689712 : if (source_pos() == start_position) {
335 : DCHECK_NE('0', c0_);
336 : return Token::ILLEGAL;
337 : }
338 :
339 : return Token::WHITESPACE;
340 : }
341 :
342 : V8_INLINE Token::Value Scanner::ScanSingleToken() {
343 : Token::Value token;
344 : do {
345 587310671 : next().location.beg_pos = source_pos();
346 :
347 587310671 : if (V8_LIKELY(static_cast<unsigned>(c0_) <= kMaxAscii)) {
348 582431800 : token = one_char_tokens[c0_];
349 :
350 582431800 : switch (token) {
351 : case Token::LPAREN:
352 : case Token::RPAREN:
353 : case Token::LBRACE:
354 : case Token::RBRACE:
355 : case Token::LBRACK:
356 : case Token::RBRACK:
357 : case Token::CONDITIONAL:
358 : case Token::COLON:
359 : case Token::SEMICOLON:
360 : case Token::COMMA:
361 : case Token::BIT_NOT:
362 : case Token::ILLEGAL:
363 : // One character tokens.
364 : return Select(token);
365 :
366 : case Token::STRING:
367 10482766 : return ScanString();
368 :
369 : case Token::LT:
370 : // < <= << <<= <!--
371 : Advance();
372 1063261 : if (c0_ == '=') return Select(Token::LTE);
373 979739 : if (c0_ == '<') return Select('=', Token::ASSIGN_SHL, Token::SHL);
374 537398 : if (c0_ == '!') {
375 73 : token = ScanHtmlComment();
376 : continue;
377 : }
378 : return Token::LT;
379 :
380 : case Token::GT:
381 : // > >= >> >>= >>> >>>=
382 : Advance();
383 537813 : if (c0_ == '=') return Select(Token::GTE);
384 505469 : if (c0_ == '>') {
385 : // >> >>= >>> >>>=
386 : Advance();
387 260905 : if (c0_ == '=') return Select(Token::ASSIGN_SAR);
388 255772 : if (c0_ == '>') return Select('=', Token::ASSIGN_SHR, Token::SHR);
389 : return Token::SAR;
390 : }
391 : return Token::GT;
392 :
393 : case Token::ASSIGN:
394 : // = == === =>
395 : Advance();
396 25659484 : if (c0_ == '=') return Select('=', Token::EQ_STRICT, Token::EQ);
397 23982082 : if (c0_ == '>') return Select(Token::ARROW);
398 : return Token::ASSIGN;
399 :
400 : case Token::NOT:
401 : // ! != !==
402 : Advance();
403 2389459 : if (c0_ == '=') return Select('=', Token::NE_STRICT, Token::NE);
404 : return Token::NOT;
405 :
406 : case Token::ADD:
407 : // + ++ +=
408 : Advance();
409 4799728 : if (c0_ == '+') return Select(Token::INC);
410 3830922 : if (c0_ == '=') return Select(Token::ASSIGN_ADD);
411 : return Token::ADD;
412 :
413 : case Token::SUB:
414 : // - -- --> -=
415 : Advance();
416 821209 : if (c0_ == '-') {
417 : Advance();
418 103534 : if (c0_ == '>' && next().after_line_terminator) {
419 : // For compatibility with SpiderMonkey, we skip lines that
420 : // start with an HTML comment end '-->'.
421 154 : token = SkipSingleHTMLComment();
422 : continue;
423 : }
424 : return Token::DEC;
425 : }
426 717675 : if (c0_ == '=') return Select(Token::ASSIGN_SUB);
427 : return Token::SUB;
428 :
429 : case Token::MUL:
430 : // * *=
431 : Advance();
432 520609 : if (c0_ == '*') return Select('=', Token::ASSIGN_EXP, Token::EXP);
433 511225 : if (c0_ == '=') return Select(Token::ASSIGN_MUL);
434 : return Token::MUL;
435 :
436 : case Token::MOD:
437 : // % %=
438 167266 : return Select('=', Token::ASSIGN_MOD, Token::MOD);
439 :
440 : case Token::DIV:
441 : // / // /* /=
442 : Advance();
443 7728970 : if (c0_ == '/') {
444 : uc32 c = Peek();
445 7270882 : if (c == '#' || c == '@') {
446 : Advance();
447 : Advance();
448 4029 : token = SkipSourceURLComment();
449 : continue;
450 : }
451 7266853 : token = SkipSingleLineComment();
452 : continue;
453 : }
454 457751 : if (c0_ == '*') {
455 58598 : token = SkipMultiLineComment();
456 : continue;
457 : }
458 399153 : if (c0_ == '=') return Select(Token::ASSIGN_DIV);
459 : return Token::DIV;
460 :
461 : case Token::BIT_AND:
462 : // & && &=
463 : Advance();
464 1268662 : if (c0_ == '&') return Select(Token::AND);
465 662213 : if (c0_ == '=') return Select(Token::ASSIGN_BIT_AND);
466 : return Token::BIT_AND;
467 :
468 : case Token::BIT_OR:
469 : // | || |=
470 : Advance();
471 878480 : if (c0_ == '|') return Select(Token::OR);
472 387693 : if (c0_ == '=') return Select(Token::ASSIGN_BIT_OR);
473 : return Token::BIT_OR;
474 :
475 : case Token::BIT_XOR:
476 : // ^ ^=
477 18420 : return Select('=', Token::ASSIGN_BIT_XOR, Token::BIT_XOR);
478 :
479 : case Token::PERIOD:
480 : // . Number
481 : Advance();
482 15083423 : if (IsDecimalDigit(c0_)) return ScanNumber(true);
483 15080356 : if (c0_ == '.') {
484 106445 : if (Peek() == '.') {
485 : Advance();
486 : Advance();
487 : return Token::ELLIPSIS;
488 : }
489 : }
490 : return Token::PERIOD;
491 :
492 : case Token::TEMPLATE_SPAN:
493 : Advance();
494 77088 : return ScanTemplateSpan();
495 :
496 : case Token::PRIVATE_NAME:
497 288776 : return ScanPrivateName();
498 :
499 : case Token::WHITESPACE:
500 : token = SkipWhiteSpace();
501 : continue;
502 :
503 : case Token::NUMBER:
504 38361262 : return ScanNumber(false);
505 :
506 : case Token::IDENTIFIER:
507 : return ScanIdentifierOrKeyword();
508 :
509 : default:
510 0 : UNREACHABLE();
511 : }
512 : }
513 :
514 14636543 : if (IsIdentifierStart(c0_) ||
515 4878945 : (CombineSurrogatePair() && IsIdentifierStart(c0_))) {
516 : return ScanIdentifierOrKeyword();
517 : }
518 4878761 : if (c0_ == kEndOfInput) {
519 9755512 : return source_->has_parser_error() ? Token::ILLEGAL : Token::EOS;
520 : }
521 : token = SkipWhiteSpace();
522 :
523 : // Continue scanning for tokens as long as we're just skipping whitespace.
524 181181924 : } while (token == Token::WHITESPACE);
525 :
526 : return token;
527 : }
528 :
529 : void Scanner::Scan(TokenDesc* next_desc) {
530 : DCHECK_EQ(next_desc, &next());
531 :
532 406115421 : next_desc->token = ScanSingleToken();
533 : DCHECK_IMPLIES(has_parser_error(), next_desc->token == Token::ILLEGAL);
534 406115421 : next_desc->location.end_pos = source_pos();
535 :
536 : #ifdef DEBUG
537 : SanityCheckTokenDesc(current());
538 : SanityCheckTokenDesc(next());
539 : SanityCheckTokenDesc(next_next());
540 : #endif
541 : }
542 :
543 5142799 : void Scanner::Scan() { Scan(next_); }
544 :
545 : } // namespace internal
546 : } // namespace v8
547 :
548 : #endif // V8_PARSING_SCANNER_INL_H_
|
