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('i') \
46 : KEYWORD("if", Token::IF) \
47 : KEYWORD("implements", Token::FUTURE_STRICT_RESERVED_WORD) \
48 : KEYWORD("import", Token::IMPORT) \
49 : KEYWORD("in", Token::IN) \
50 : KEYWORD("instanceof", Token::INSTANCEOF) \
51 : KEYWORD("interface", Token::FUTURE_STRICT_RESERVED_WORD) \
52 : KEYWORD_GROUP('l') \
53 : KEYWORD("let", Token::LET) \
54 : KEYWORD_GROUP('n') \
55 : KEYWORD("new", Token::NEW) \
56 : KEYWORD("null", Token::NULL_LITERAL) \
57 : KEYWORD_GROUP('p') \
58 : KEYWORD("package", Token::FUTURE_STRICT_RESERVED_WORD) \
59 : KEYWORD("private", Token::FUTURE_STRICT_RESERVED_WORD) \
60 : KEYWORD("protected", Token::FUTURE_STRICT_RESERVED_WORD) \
61 : KEYWORD("public", Token::FUTURE_STRICT_RESERVED_WORD) \
62 : KEYWORD_GROUP('r') \
63 : KEYWORD("return", Token::RETURN) \
64 : KEYWORD_GROUP('s') \
65 : KEYWORD("static", Token::STATIC) \
66 : KEYWORD("super", Token::SUPER) \
67 : KEYWORD("switch", Token::SWITCH) \
68 : KEYWORD_GROUP('t') \
69 : KEYWORD("this", Token::THIS) \
70 : KEYWORD("throw", Token::THROW) \
71 : KEYWORD("true", Token::TRUE_LITERAL) \
72 : KEYWORD("try", Token::TRY) \
73 : KEYWORD("typeof", Token::TYPEOF) \
74 : KEYWORD_GROUP('v') \
75 : KEYWORD("var", Token::VAR) \
76 : KEYWORD("void", Token::VOID) \
77 : KEYWORD_GROUP('w') \
78 : KEYWORD("while", Token::WHILE) \
79 : KEYWORD("with", Token::WITH) \
80 : KEYWORD_GROUP('y') \
81 : KEYWORD("yield", Token::YIELD)
82 :
83 : constexpr bool IsKeywordStart(char c) {
84 : #define KEYWORD_GROUP_CHECK(ch) c == ch ||
85 : #define KEYWORD_CHECK(keyword, token)
86 : return KEYWORDS(KEYWORD_GROUP_CHECK, KEYWORD_CHECK) /* || */ false;
87 : #undef KEYWORD_GROUP_CHECK
88 : #undef KEYWORD_CHECK
89 : }
90 :
91 : V8_INLINE Token::Value KeywordOrIdentifierToken(const uint8_t* input,
92 : int input_length) {
93 : DCHECK_GE(input_length, 1);
94 : return PerfectKeywordHash::GetToken(reinterpret_cast<const char*>(input),
95 76442136 : input_length);
96 : }
97 :
98 : // Recursive constexpr template magic to check if a character is in a given
99 : // string.
100 : template <int N>
101 : constexpr bool IsInString(const char (&s)[N], char c, size_t i = 0) {
102 : return i >= N ? false : s[i] == c ? true : IsInString(s, c, i + 1);
103 : }
104 :
105 : inline constexpr bool CanBeKeywordCharacter(char c) {
106 : return IsInString(
107 : #define KEYWORD_GROUP_CASE(ch) // Nothing
108 : #define KEYWORD(keyword, token) keyword
109 : // Use C string literal concatenation ("a" "b" becomes "ab") to build one
110 : // giant string containing all the keywords.
111 : KEYWORDS(KEYWORD_GROUP_CASE, KEYWORD)
112 : #undef KEYWORD
113 : #undef KEYWORD_GROUP_CASE
114 : ,
115 : c);
116 : }
117 :
118 : // Make sure tokens are stored as a single byte.
119 : STATIC_ASSERT(sizeof(Token::Value) == 1);
120 :
121 : // Get the shortest token that this character starts, the token may change
122 : // depending on subsequent characters.
123 : constexpr Token::Value GetOneCharToken(char c) {
124 : // clang-format off
125 : return
126 : c == '(' ? Token::LPAREN :
127 : c == ')' ? Token::RPAREN :
128 : c == '{' ? Token::LBRACE :
129 : c == '}' ? Token::RBRACE :
130 : c == '[' ? Token::LBRACK :
131 : c == ']' ? Token::RBRACK :
132 : c == '?' ? Token::CONDITIONAL :
133 : c == ':' ? Token::COLON :
134 : c == ';' ? Token::SEMICOLON :
135 : c == ',' ? Token::COMMA :
136 : c == '.' ? Token::PERIOD :
137 : c == '|' ? Token::BIT_OR :
138 : c == '&' ? Token::BIT_AND :
139 : c == '^' ? Token::BIT_XOR :
140 : c == '~' ? Token::BIT_NOT :
141 : c == '!' ? Token::NOT :
142 : c == '<' ? Token::LT :
143 : c == '>' ? Token::GT :
144 : c == '%' ? Token::MOD :
145 : c == '=' ? Token::ASSIGN :
146 : c == '+' ? Token::ADD :
147 : c == '-' ? Token::SUB :
148 : c == '*' ? Token::MUL :
149 : c == '/' ? Token::DIV :
150 : c == '#' ? Token::PRIVATE_NAME :
151 : c == '"' ? Token::STRING :
152 : c == '\'' ? Token::STRING :
153 : c == '`' ? Token::TEMPLATE_SPAN :
154 : c == '\\' ? Token::IDENTIFIER :
155 : // Whitespace or line terminator
156 : c == ' ' ? Token::WHITESPACE :
157 : c == '\t' ? Token::WHITESPACE :
158 : c == '\v' ? Token::WHITESPACE :
159 : c == '\f' ? Token::WHITESPACE :
160 : c == '\r' ? Token::WHITESPACE :
161 : c == '\n' ? Token::WHITESPACE :
162 : // IsDecimalDigit must be tested before IsAsciiIdentifier
163 : IsDecimalDigit(c) ? Token::NUMBER :
164 : IsAsciiIdentifier(c) ? Token::IDENTIFIER :
165 : Token::ILLEGAL;
166 : // clang-format on
167 : }
168 :
169 : // Table of one-character tokens, by character (0x00..0x7F only).
170 : static const constexpr Token::Value one_char_tokens[128] = {
171 : #define CALL_GET_SCAN_FLAGS(N) GetOneCharToken(N),
172 : INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
173 : #undef CALL_GET_SCAN_FLAGS
174 : };
175 :
176 : #undef KEYWORDS
177 :
178 129993811 : V8_INLINE Token::Value Scanner::ScanIdentifierOrKeyword() {
179 129993811 : next().literal_chars.Start();
180 : return ScanIdentifierOrKeywordInner();
181 : }
182 :
183 : // Character flags for the fast path of scanning a keyword or identifier token.
184 : enum class ScanFlags : uint8_t {
185 : kTerminatesLiteral = 1 << 0,
186 : // "Cannot" rather than "can" so that this flag can be ORed together across
187 : // multiple characters.
188 : kCannotBeKeyword = 1 << 1,
189 : kCannotBeKeywordStart = 1 << 2,
190 : kStringTerminator = 1 << 3,
191 : kNeedsSlowPath = 1 << 4,
192 : };
193 : constexpr uint8_t GetScanFlags(char c) {
194 : return
195 : // Keywords are all lowercase and only contain letters.
196 : // Note that non-identifier characters do not set this flag, so
197 : // that it plays well with kTerminatesLiteral.
198 : (IsAsciiIdentifier(c) && !CanBeKeywordCharacter(c)
199 : ? static_cast<uint8_t>(ScanFlags::kCannotBeKeyword)
200 : : 0) |
201 : (IsKeywordStart(c)
202 : ? 0
203 : : static_cast<uint8_t>(ScanFlags::kCannotBeKeywordStart)) |
204 : // Anything that isn't an identifier character will terminate the
205 : // literal, or at least terminates the literal fast path processing
206 : // (like an escape).
207 : (!IsAsciiIdentifier(c)
208 : ? static_cast<uint8_t>(ScanFlags::kTerminatesLiteral)
209 : : 0) |
210 : // Possible string termination characters.
211 : ((c == '\'' || c == '"' || c == '\n' || c == '\r' || c == '\\')
212 : ? static_cast<uint8_t>(ScanFlags::kStringTerminator)
213 : : 0) |
214 : // Escapes are processed on the slow path.
215 : (c == '\\' ? static_cast<uint8_t>(ScanFlags::kNeedsSlowPath) : 0);
216 : }
217 : inline bool TerminatesLiteral(uint8_t scan_flags) {
218 767273406 : return (scan_flags & static_cast<uint8_t>(ScanFlags::kTerminatesLiteral));
219 : }
220 130062849 : inline bool CanBeKeyword(uint8_t scan_flags) {
221 130117012 : return !(scan_flags & static_cast<uint8_t>(ScanFlags::kCannotBeKeyword));
222 : }
223 130061895 : inline bool NeedsSlowPath(uint8_t scan_flags) {
224 130061895 : return (scan_flags & static_cast<uint8_t>(ScanFlags::kNeedsSlowPath));
225 : }
226 : inline bool MayTerminateString(uint8_t scan_flags) {
227 183299922 : return (scan_flags & static_cast<uint8_t>(ScanFlags::kStringTerminator));
228 : }
229 : // Table of precomputed scan flags for the 128 ASCII characters, for branchless
230 : // flag calculation during the scan.
231 : static constexpr const uint8_t character_scan_flags[128] = {
232 : #define CALL_GET_SCAN_FLAGS(N) GetScanFlags(N),
233 : INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
234 : #undef CALL_GET_SCAN_FLAGS
235 : };
236 :
237 2316 : inline bool CharCanBeKeyword(uc32 c) {
238 108963 : return static_cast<uint32_t>(c) < arraysize(character_scan_flags) &&
239 56479 : CanBeKeyword(character_scan_flags[c]);
240 : }
241 :
242 206335561 : V8_INLINE Token::Value Scanner::ScanIdentifierOrKeywordInner() {
243 : DCHECK(IsIdentifierStart(c0_));
244 : bool escaped = false;
245 : bool can_be_keyword = true;
246 :
247 : STATIC_ASSERT(arraysize(character_scan_flags) == kMaxAscii + 1);
248 130046444 : if (V8_LIKELY(static_cast<uint32_t>(c0_) <= kMaxAscii)) {
249 130047198 : if (V8_LIKELY(c0_ != '\\')) {
250 130037267 : uint8_t scan_flags = character_scan_flags[c0_];
251 : DCHECK(!TerminatesLiteral(scan_flags));
252 : STATIC_ASSERT(static_cast<uint8_t>(ScanFlags::kCannotBeKeywordStart) ==
253 : static_cast<uint8_t>(ScanFlags::kCannotBeKeyword) << 1);
254 130037267 : scan_flags >>= 1;
255 : // Make sure the shifting above doesn't set NeedsSlowPath. Otherwise we'll
256 : // fall into the slow path after scanning the identifier.
257 : DCHECK(!NeedsSlowPath(scan_flags));
258 : AddLiteralChar(static_cast<char>(c0_));
259 767273753 : AdvanceUntil([this, &scan_flags](uc32 c0) {
260 767273753 : if (V8_UNLIKELY(static_cast<uint32_t>(c0) > kMaxAscii)) {
261 : // A non-ascii character means we need to drop through to the slow
262 : // path.
263 : // TODO(leszeks): This would be most efficient as a goto to the slow
264 : // path, check codegen and maybe use a bool instead.
265 347 : scan_flags |= static_cast<uint8_t>(ScanFlags::kNeedsSlowPath);
266 347 : return true;
267 : }
268 767273406 : uint8_t char_flags = character_scan_flags[c0];
269 767273406 : scan_flags |= char_flags;
270 767273406 : if (TerminatesLiteral(char_flags)) {
271 : return true;
272 : } else {
273 637590458 : AddLiteralChar(static_cast<char>(c0));
274 637511715 : return false;
275 : }
276 : });
277 :
278 130049338 : if (V8_LIKELY(!NeedsSlowPath(scan_flags))) {
279 130051213 : if (!CanBeKeyword(scan_flags)) return Token::IDENTIFIER;
280 : // Could be a keyword or identifier.
281 76434936 : Vector<const uint8_t> chars = next().literal_chars.one_byte_literal();
282 76429820 : return KeywordOrIdentifierToken(chars.start(), chars.length());
283 : }
284 :
285 13596 : can_be_keyword = CanBeKeyword(scan_flags);
286 : } else {
287 : // Special case for escapes at the start of an identifier.
288 : escaped = true;
289 9931 : uc32 c = ScanIdentifierUnicodeEscape();
290 : DCHECK(!IsIdentifierStart(-1));
291 9931 : if (c == '\\' || !IsIdentifierStart(c)) {
292 : return Token::ILLEGAL;
293 : }
294 : AddLiteralChar(c);
295 2316 : can_be_keyword = CharCanBeKeyword(c);
296 : }
297 : }
298 :
299 15158 : return ScanIdentifierOrKeywordInnerSlow(escaped, can_be_keyword);
300 : }
301 :
302 724741396 : V8_INLINE Token::Value Scanner::SkipWhiteSpace() {
303 168842632 : int start_position = source_pos();
304 :
305 : // We won't skip behind the end of input.
306 : DCHECK(!IsWhiteSpaceOrLineTerminator(kEndOfInput));
307 :
308 : // Advance as long as character is a WhiteSpace or LineTerminator.
309 518830475 : while (IsWhiteSpaceOrLineTerminator(c0_)) {
310 521810420 : if (!next().after_line_terminator && unibrow::IsLineTerminator(c0_)) {
311 37044556 : next().after_line_terminator = true;
312 : }
313 350023180 : Advance();
314 : }
315 :
316 : // Return whether or not we skipped any characters.
317 168820081 : if (source_pos() == start_position) {
318 : DCHECK_NE('0', c0_);
319 : return Token::ILLEGAL;
320 : }
321 :
322 : return Token::WHITESPACE;
323 : }
324 :
325 1192129877 : V8_INLINE Token::Value Scanner::ScanSingleToken() {
326 : Token::Value token;
327 175890798 : do {
328 1125262004 : next().location.beg_pos = source_pos();
329 :
330 563494389 : if (V8_LIKELY(static_cast<unsigned>(c0_) <= kMaxAscii)) {
331 558766021 : token = one_char_tokens[c0_];
332 :
333 558766021 : switch (token) {
334 : case Token::LPAREN:
335 : case Token::RPAREN:
336 : case Token::LBRACE:
337 : case Token::RBRACE:
338 : case Token::LBRACK:
339 : case Token::RBRACK:
340 : case Token::CONDITIONAL:
341 : case Token::COLON:
342 : case Token::SEMICOLON:
343 : case Token::COMMA:
344 : case Token::BIT_NOT:
345 : case Token::ILLEGAL:
346 : // One character tokens.
347 156752990 : return Select(token);
348 :
349 : case Token::STRING:
350 10078947 : return ScanString();
351 :
352 : case Token::LT:
353 : // < <= << <<= <!--
354 1038136 : Advance();
355 1038182 : if (c0_ == '=') return Select(Token::LTE);
356 963019 : if (c0_ == '<') return Select('=', Token::ASSIGN_SHL, Token::SHL);
357 534197 : if (c0_ == '!') {
358 73 : token = ScanHtmlComment();
359 : continue;
360 : }
361 : return Token::LT;
362 :
363 : case Token::GT:
364 : // > >= >> >>= >>> >>>=
365 588342 : Advance();
366 588338 : if (c0_ == '=') return Select(Token::GTE);
367 525842 : if (c0_ == '>') {
368 : // >> >>= >>> >>>=
369 284243 : Advance();
370 284245 : if (c0_ == '=') return Select(Token::ASSIGN_SAR);
371 279106 : if (c0_ == '>') return Select('=', Token::ASSIGN_SHR, Token::SHR);
372 : return Token::SAR;
373 : }
374 : return Token::GT;
375 :
376 : case Token::ASSIGN:
377 : // = == === =>
378 25567883 : Advance();
379 25568258 : if (c0_ == '=') return Select('=', Token::EQ_STRICT, Token::EQ);
380 23930431 : if (c0_ == '>') return Select(Token::ARROW);
381 : return Token::ASSIGN;
382 :
383 : case Token::NOT:
384 : // ! != !==
385 1964313 : Advance();
386 1964317 : if (c0_ == '=') return Select('=', Token::NE_STRICT, Token::NE);
387 : return Token::NOT;
388 :
389 : case Token::ADD:
390 : // + ++ +=
391 4397096 : Advance();
392 4397089 : if (c0_ == '+') return Select(Token::INC);
393 3451430 : if (c0_ == '=') return Select(Token::ASSIGN_ADD);
394 : return Token::ADD;
395 :
396 : case Token::SUB:
397 : // - -- --> -=
398 818047 : Advance();
399 818038 : if (c0_ == '-') {
400 101805 : Advance();
401 102012 : if (c0_ == '>' && next().after_line_terminator) {
402 : // For compatibility with SpiderMonkey, we skip lines that
403 : // start with an HTML comment end '-->'.
404 154 : token = SkipSingleHTMLComment();
405 : continue;
406 : }
407 : return Token::DEC;
408 : }
409 716233 : if (c0_ == '=') return Select(Token::ASSIGN_SUB);
410 : return Token::SUB;
411 :
412 : case Token::MUL:
413 : // * *=
414 513385 : Advance();
415 513383 : if (c0_ == '*') return Select('=', Token::ASSIGN_EXP, Token::EXP);
416 504046 : if (c0_ == '=') return Select(Token::ASSIGN_MUL);
417 : return Token::MUL;
418 :
419 : case Token::MOD:
420 : // % %=
421 151641 : return Select('=', Token::ASSIGN_MOD, Token::MOD);
422 :
423 : case Token::DIV:
424 : // / // /* /=
425 7484340 : Advance();
426 7484132 : if (c0_ == '/') {
427 7033332 : uc32 c = Peek();
428 7033120 : if (c == '#' || c == '@') {
429 4074 : Advance();
430 4074 : Advance();
431 4074 : token = SkipSourceURLComment();
432 : continue;
433 : }
434 7029046 : token = SkipSingleLineComment();
435 : continue;
436 : }
437 450800 : if (c0_ == '*') {
438 56301 : token = SkipMultiLineComment();
439 : continue;
440 : }
441 394499 : if (c0_ == '=') return Select(Token::ASSIGN_DIV);
442 : return Token::DIV;
443 :
444 : case Token::BIT_AND:
445 : // & && &=
446 1101387 : Advance();
447 1101412 : if (c0_ == '&') return Select(Token::AND);
448 671062 : if (c0_ == '=') return Select(Token::ASSIGN_BIT_AND);
449 : return Token::BIT_AND;
450 :
451 : case Token::BIT_OR:
452 : // | || |=
453 893247 : Advance();
454 893239 : if (c0_ == '|') return Select(Token::OR);
455 415520 : if (c0_ == '=') return Select(Token::ASSIGN_BIT_OR);
456 : return Token::BIT_OR;
457 :
458 : case Token::BIT_XOR:
459 : // ^ ^=
460 18598 : return Select('=', Token::ASSIGN_BIT_XOR, Token::BIT_XOR);
461 :
462 : case Token::PERIOD:
463 : // . Number
464 14672109 : Advance();
465 14672114 : if (IsDecimalDigit(c0_)) return ScanNumber(true);
466 14668903 : if (c0_ == '.') {
467 108474 : if (Peek() == '.') {
468 108098 : Advance();
469 108097 : Advance();
470 : return Token::ELLIPSIS;
471 : }
472 : }
473 : return Token::PERIOD;
474 :
475 : case Token::TEMPLATE_SPAN:
476 77184 : Advance();
477 77183 : return ScanTemplateSpan();
478 :
479 : case Token::PRIVATE_NAME:
480 260765 : return ScanPrivateName();
481 :
482 : case Token::WHITESPACE:
483 : token = SkipWhiteSpace();
484 : continue;
485 :
486 : case Token::NUMBER:
487 33552111 : return ScanNumber(false);
488 :
489 : case Token::IDENTIFIER:
490 : return ScanIdentifierOrKeyword();
491 :
492 : default:
493 0 : UNREACHABLE();
494 : }
495 : }
496 :
497 14184784 : if (IsIdentifierStart(c0_) ||
498 4728306 : (CombineSurrogatePair() && IsIdentifierStart(c0_))) {
499 : return ScanIdentifierOrKeyword();
500 : }
501 4728112 : if (c0_ == kEndOfInput) {
502 4727271 : return source_->has_parser_error() ? Token::ILLEGAL : Token::EOS;
503 : }
504 : token = SkipWhiteSpace();
505 :
506 : // Continue scanning for tokens as long as we're just skipping whitespace.
507 : } while (token == Token::WHITESPACE);
508 :
509 : return token;
510 : }
511 :
512 387558639 : void Scanner::Scan(TokenDesc* next_desc) {
513 : DCHECK_EQ(next_desc, &next());
514 :
515 387558639 : next_desc->token = ScanSingleToken();
516 : DCHECK_IMPLIES(has_parser_error(), next_desc->token == Token::ILLEGAL);
517 387558639 : next_desc->location.end_pos = source_pos();
518 :
519 : #ifdef DEBUG
520 : SanityCheckTokenDesc(current());
521 : SanityCheckTokenDesc(next());
522 : SanityCheckTokenDesc(next_next());
523 : #endif
524 : }
525 :
526 4975118 : void Scanner::Scan() { Scan(next_); }
527 :
528 : } // namespace internal
529 : } // namespace v8
530 :
531 : #endif // V8_PARSING_SCANNER_INL_H_
|
