scanner-inl.h 19.3 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_PARSING_SCANNER_INL_H_
#define V8_PARSING_SCANNER_INL_H_

8
#include "src/char-predicates-inl.h"
9
#include "src/parsing/keywords-gen.h"
10 11 12 13 14
#include "src/parsing/scanner.h"

namespace v8 {
namespace internal {

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
// ----------------------------------------------------------------------------
// Keyword Matcher

#define KEYWORDS(KEYWORD_GROUP, KEYWORD)                    \
  KEYWORD_GROUP('a')                                        \
  KEYWORD("async", Token::ASYNC)                            \
  KEYWORD("await", Token::AWAIT)                            \
  KEYWORD_GROUP('b')                                        \
  KEYWORD("break", Token::BREAK)                            \
  KEYWORD_GROUP('c')                                        \
  KEYWORD("case", Token::CASE)                              \
  KEYWORD("catch", Token::CATCH)                            \
  KEYWORD("class", Token::CLASS)                            \
  KEYWORD("const", Token::CONST)                            \
  KEYWORD("continue", Token::CONTINUE)                      \
  KEYWORD_GROUP('d')                                        \
  KEYWORD("debugger", Token::DEBUGGER)                      \
  KEYWORD("default", Token::DEFAULT)                        \
  KEYWORD("delete", Token::DELETE)                          \
  KEYWORD("do", Token::DO)                                  \
  KEYWORD_GROUP('e')                                        \
  KEYWORD("else", Token::ELSE)                              \
  KEYWORD("enum", Token::ENUM)                              \
  KEYWORD("export", Token::EXPORT)                          \
  KEYWORD("extends", Token::EXTENDS)                        \
  KEYWORD_GROUP('f')                                        \
  KEYWORD("false", Token::FALSE_LITERAL)                    \
  KEYWORD("finally", Token::FINALLY)                        \
  KEYWORD("for", Token::FOR)                                \
  KEYWORD("function", Token::FUNCTION)                      \
45 46
  KEYWORD_GROUP('g')                                        \
  KEYWORD("get", Token::GET)                                \
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
  KEYWORD_GROUP('i')                                        \
  KEYWORD("if", Token::IF)                                  \
  KEYWORD("implements", Token::FUTURE_STRICT_RESERVED_WORD) \
  KEYWORD("import", Token::IMPORT)                          \
  KEYWORD("in", Token::IN)                                  \
  KEYWORD("instanceof", Token::INSTANCEOF)                  \
  KEYWORD("interface", Token::FUTURE_STRICT_RESERVED_WORD)  \
  KEYWORD_GROUP('l')                                        \
  KEYWORD("let", Token::LET)                                \
  KEYWORD_GROUP('n')                                        \
  KEYWORD("new", Token::NEW)                                \
  KEYWORD("null", Token::NULL_LITERAL)                      \
  KEYWORD_GROUP('p')                                        \
  KEYWORD("package", Token::FUTURE_STRICT_RESERVED_WORD)    \
  KEYWORD("private", Token::FUTURE_STRICT_RESERVED_WORD)    \
  KEYWORD("protected", Token::FUTURE_STRICT_RESERVED_WORD)  \
  KEYWORD("public", Token::FUTURE_STRICT_RESERVED_WORD)     \
  KEYWORD_GROUP('r')                                        \
  KEYWORD("return", Token::RETURN)                          \
  KEYWORD_GROUP('s')                                        \
67
  KEYWORD("set", Token::SET)                                \
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
  KEYWORD("static", Token::STATIC)                          \
  KEYWORD("super", Token::SUPER)                            \
  KEYWORD("switch", Token::SWITCH)                          \
  KEYWORD_GROUP('t')                                        \
  KEYWORD("this", Token::THIS)                              \
  KEYWORD("throw", Token::THROW)                            \
  KEYWORD("true", Token::TRUE_LITERAL)                      \
  KEYWORD("try", Token::TRY)                                \
  KEYWORD("typeof", Token::TYPEOF)                          \
  KEYWORD_GROUP('v')                                        \
  KEYWORD("var", Token::VAR)                                \
  KEYWORD("void", Token::VOID)                              \
  KEYWORD_GROUP('w')                                        \
  KEYWORD("while", Token::WHILE)                            \
  KEYWORD("with", Token::WITH)                              \
  KEYWORD_GROUP('y')                                        \
84
  KEYWORD("yield", Token::YIELD)
85

86 87 88 89 90 91 92 93
constexpr bool IsKeywordStart(char c) {
#define KEYWORD_GROUP_CHECK(ch) c == ch ||
#define KEYWORD_CHECK(keyword, token)
  return KEYWORDS(KEYWORD_GROUP_CHECK, KEYWORD_CHECK) /* || */ false;
#undef KEYWORD_GROUP_CHECK
#undef KEYWORD_CHECK
}

94 95 96
V8_INLINE Token::Value KeywordOrIdentifierToken(const uint8_t* input,
                                                int input_length) {
  DCHECK_GE(input_length, 1);
97 98
  return PerfectKeywordHash::GetToken(reinterpret_cast<const char*>(input),
                                      input_length);
99 100
}

101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
// Recursive constexpr template magic to check if a character is in a given
// string.
template <int N>
constexpr bool IsInString(const char (&s)[N], char c, size_t i = 0) {
  return i >= N ? false : s[i] == c ? true : IsInString(s, c, i + 1);
}

inline constexpr bool CanBeKeywordCharacter(char c) {
  return IsInString(
#define KEYWORD_GROUP_CASE(ch)  // Nothing
#define KEYWORD(keyword, token) keyword
      // Use C string literal concatenation ("a" "b" becomes "ab") to build one
      // giant string containing all the keywords.
      KEYWORDS(KEYWORD_GROUP_CASE, KEYWORD)
#undef KEYWORD
#undef KEYWORD_GROUP_CASE
          ,
      c);
}

121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
// Make sure tokens are stored as a single byte.
STATIC_ASSERT(sizeof(Token::Value) == 1);

// Get the shortest token that this character starts, the token may change
// depending on subsequent characters.
constexpr Token::Value GetOneCharToken(char c) {
  // clang-format off
  return
      c == '(' ? Token::LPAREN :
      c == ')' ? Token::RPAREN :
      c == '{' ? Token::LBRACE :
      c == '}' ? Token::RBRACE :
      c == '[' ? Token::LBRACK :
      c == ']' ? Token::RBRACK :
      c == '?' ? Token::CONDITIONAL :
      c == ':' ? Token::COLON :
      c == ';' ? Token::SEMICOLON :
      c == ',' ? Token::COMMA :
      c == '.' ? Token::PERIOD :
      c == '|' ? Token::BIT_OR :
      c == '&' ? Token::BIT_AND :
      c == '^' ? Token::BIT_XOR :
      c == '~' ? Token::BIT_NOT :
      c == '!' ? Token::NOT :
      c == '<' ? Token::LT :
      c == '>' ? Token::GT :
      c == '%' ? Token::MOD :
      c == '=' ? Token::ASSIGN :
      c == '+' ? Token::ADD :
      c == '-' ? Token::SUB :
      c == '*' ? Token::MUL :
      c == '/' ? Token::DIV :
      c == '#' ? Token::PRIVATE_NAME :
      c == '"' ? Token::STRING :
      c == '\'' ? Token::STRING :
      c == '`' ? Token::TEMPLATE_SPAN :
      c == '\\' ? Token::IDENTIFIER :
      // Whitespace or line terminator
      c == ' ' ? Token::WHITESPACE :
      c == '\t' ? Token::WHITESPACE :
      c == '\v' ? Token::WHITESPACE :
      c == '\f' ? Token::WHITESPACE :
      c == '\r' ? Token::WHITESPACE :
      c == '\n' ? Token::WHITESPACE :
      // IsDecimalDigit must be tested before IsAsciiIdentifier
      IsDecimalDigit(c) ? Token::NUMBER :
      IsAsciiIdentifier(c) ? Token::IDENTIFIER :
      Token::ILLEGAL;
  // clang-format on
}

// Table of one-character tokens, by character (0x00..0x7F only).
static const constexpr Token::Value one_char_tokens[128] = {
#define CALL_GET_SCAN_FLAGS(N) GetOneCharToken(N),
    INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
#undef CALL_GET_SCAN_FLAGS
};

179 180
#undef KEYWORDS

181
V8_INLINE Token::Value Scanner::ScanIdentifierOrKeyword() {
182 183
  next().literal_chars.Start();
  return ScanIdentifierOrKeywordInner();
184 185
}

186 187 188 189 190 191
// Character flags for the fast path of scanning a keyword or identifier token.
enum class ScanFlags : uint8_t {
  kTerminatesLiteral = 1 << 0,
  // "Cannot" rather than "can" so that this flag can be ORed together across
  // multiple characters.
  kCannotBeKeyword = 1 << 1,
192 193
  kCannotBeKeywordStart = 1 << 2,
  kStringTerminator = 1 << 3,
194 195
  kIdentifierNeedsSlowPath = 1 << 4,
  kMultilineCommentCharacterNeedsSlowPath = 1 << 5,
196 197 198
};
constexpr uint8_t GetScanFlags(char c) {
  return
199
      // Keywords are all lowercase and only contain letters.
200
      // Note that non-identifier characters do not set this flag, so
201 202
      // that it plays well with kTerminatesLiteral.
      (IsAsciiIdentifier(c) && !CanBeKeywordCharacter(c)
203 204
           ? static_cast<uint8_t>(ScanFlags::kCannotBeKeyword)
           : 0) |
205 206 207
      (IsKeywordStart(c)
           ? 0
           : static_cast<uint8_t>(ScanFlags::kCannotBeKeywordStart)) |
208 209 210 211 212 213
      // Anything that isn't an identifier character will terminate the
      // literal, or at least terminates the literal fast path processing
      // (like an escape).
      (!IsAsciiIdentifier(c)
           ? static_cast<uint8_t>(ScanFlags::kTerminatesLiteral)
           : 0) |
214 215 216 217
      // Possible string termination characters.
      ((c == '\'' || c == '"' || c == '\n' || c == '\r' || c == '\\')
           ? static_cast<uint8_t>(ScanFlags::kStringTerminator)
           : 0) |
218
      // Escapes are processed on the slow path.
219 220 221 222 223 224 225 226
      (c == '\\' ? static_cast<uint8_t>(ScanFlags::kIdentifierNeedsSlowPath)
                 : 0) |
      // Newlines and * are interesting characters for multiline comment
      // scanning.
      (c == '\n' || c == '\r' || c == '*'
           ? static_cast<uint8_t>(
                 ScanFlags::kMultilineCommentCharacterNeedsSlowPath)
           : 0);
227 228 229 230 231 232 233
}
inline bool TerminatesLiteral(uint8_t scan_flags) {
  return (scan_flags & static_cast<uint8_t>(ScanFlags::kTerminatesLiteral));
}
inline bool CanBeKeyword(uint8_t scan_flags) {
  return !(scan_flags & static_cast<uint8_t>(ScanFlags::kCannotBeKeyword));
}
234 235 236 237 238 239 240
inline bool IdentifierNeedsSlowPath(uint8_t scan_flags) {
  return (scan_flags &
          static_cast<uint8_t>(ScanFlags::kIdentifierNeedsSlowPath));
}
inline bool MultilineCommentCharacterNeedsSlowPath(uint8_t scan_flags) {
  return (scan_flags & static_cast<uint8_t>(
                           ScanFlags::kMultilineCommentCharacterNeedsSlowPath));
241
}
242 243 244
inline bool MayTerminateString(uint8_t scan_flags) {
  return (scan_flags & static_cast<uint8_t>(ScanFlags::kStringTerminator));
}
245 246 247 248 249 250 251 252
// Table of precomputed scan flags for the 128 ASCII characters, for branchless
// flag calculation during the scan.
static constexpr const uint8_t character_scan_flags[128] = {
#define CALL_GET_SCAN_FLAGS(N) GetScanFlags(N),
    INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
#undef CALL_GET_SCAN_FLAGS
};

253 254 255 256 257
inline bool CharCanBeKeyword(uc32 c) {
  return static_cast<uint32_t>(c) < arraysize(character_scan_flags) &&
         CanBeKeyword(character_scan_flags[c]);
}

258
V8_INLINE Token::Value Scanner::ScanIdentifierOrKeywordInner() {
259
  DCHECK(IsIdentifierStart(c0_));
260
  bool escaped = false;
261
  bool can_be_keyword = true;
262

263 264 265 266 267
  STATIC_ASSERT(arraysize(character_scan_flags) == kMaxAscii + 1);
  if (V8_LIKELY(static_cast<uint32_t>(c0_) <= kMaxAscii)) {
    if (V8_LIKELY(c0_ != '\\')) {
      uint8_t scan_flags = character_scan_flags[c0_];
      DCHECK(!TerminatesLiteral(scan_flags));
268 269 270
      STATIC_ASSERT(static_cast<uint8_t>(ScanFlags::kCannotBeKeywordStart) ==
                    static_cast<uint8_t>(ScanFlags::kCannotBeKeyword) << 1);
      scan_flags >>= 1;
271 272 273
      // Make sure the shifting above doesn't set IdentifierNeedsSlowPath.
      // Otherwise we'll fall into the slow path after scanning the identifier.
      DCHECK(!IdentifierNeedsSlowPath(scan_flags));
274
      AddLiteralChar(static_cast<char>(c0_));
275 276 277 278 279 280
      AdvanceUntil([this, &scan_flags](uc32 c0) {
        if (V8_UNLIKELY(static_cast<uint32_t>(c0) > kMaxAscii)) {
          // A non-ascii character means we need to drop through to the slow
          // path.
          // TODO(leszeks): This would be most efficient as a goto to the slow
          // path, check codegen and maybe use a bool instead.
281 282
          scan_flags |=
              static_cast<uint8_t>(ScanFlags::kIdentifierNeedsSlowPath);
283 284 285 286 287 288 289 290 291 292 293
          return true;
        }
        uint8_t char_flags = character_scan_flags[c0];
        scan_flags |= char_flags;
        if (TerminatesLiteral(char_flags)) {
          return true;
        } else {
          AddLiteralChar(static_cast<char>(c0));
          return false;
        }
      });
294

295
      if (V8_LIKELY(!IdentifierNeedsSlowPath(scan_flags))) {
296 297 298
        if (!CanBeKeyword(scan_flags)) return Token::IDENTIFIER;
        // Could be a keyword or identifier.
        Vector<const uint8_t> chars = next().literal_chars.one_byte_literal();
299
        return KeywordOrIdentifierToken(chars.begin(), chars.length());
300
      }
301 302

      can_be_keyword = CanBeKeyword(scan_flags);
303 304 305 306
    } else {
      // Special case for escapes at the start of an identifier.
      escaped = true;
      uc32 c = ScanIdentifierUnicodeEscape();
307 308
      DCHECK(!IsIdentifierStart(-1));
      if (c == '\\' || !IsIdentifierStart(c)) {
309 310 311
        return Token::ILLEGAL;
      }
      AddLiteralChar(c);
312
      can_be_keyword = CharCanBeKeyword(c);
313 314 315
    }
  }

316
  return ScanIdentifierOrKeywordInnerSlow(escaped, can_be_keyword);
317 318
}

319
V8_INLINE Token::Value Scanner::SkipWhiteSpace() {
320 321
  int start_position = source_pos();

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
  while (IsWhiteSpaceOrLineTerminator(c0_)) {
327
    if (!next().after_line_terminator && unibrow::IsLineTerminator(c0_)) {
328
      next().after_line_terminator = true;
329
    }
330 331 332 333 334 335 336 337
    Advance();
  }

  // Return whether or not we skipped any characters.
  if (source_pos() == start_position) {
    DCHECK_NE('0', c0_);
    return Token::ILLEGAL;
  }
338 339

  return Token::WHITESPACE;
340
}
341

342 343 344
V8_INLINE Token::Value Scanner::ScanSingleToken() {
  Token::Value token;
  do {
345
    next().location.beg_pos = source_pos();
346

347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370
    if (V8_LIKELY(static_cast<unsigned>(c0_) <= kMaxAscii)) {
      token = one_char_tokens[c0_];

      switch (token) {
        case Token::LPAREN:
        case Token::RPAREN:
        case Token::LBRACE:
        case Token::RBRACE:
        case Token::LBRACK:
        case Token::RBRACK:
        case Token::CONDITIONAL:
        case Token::COLON:
        case Token::SEMICOLON:
        case Token::COMMA:
        case Token::BIT_NOT:
        case Token::ILLEGAL:
          // One character tokens.
          return Select(token);

        case Token::STRING:
          return ScanString();

        case Token::LT:
          // < <= << <<= <!--
371
          Advance();
372 373 374 375
          if (c0_ == '=') return Select(Token::LTE);
          if (c0_ == '<') return Select('=', Token::ASSIGN_SHL, Token::SHL);
          if (c0_ == '!') {
            token = ScanHtmlComment();
376 377
            continue;
          }
378 379 380 381 382 383 384 385
          return Token::LT;

        case Token::GT:
          // > >= >> >>= >>> >>>=
          Advance();
          if (c0_ == '=') return Select(Token::GTE);
          if (c0_ == '>') {
            // >> >>= >>> >>>=
386
            Advance();
387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416
            if (c0_ == '=') return Select(Token::ASSIGN_SAR);
            if (c0_ == '>') return Select('=', Token::ASSIGN_SHR, Token::SHR);
            return Token::SAR;
          }
          return Token::GT;

        case Token::ASSIGN:
          // = == === =>
          Advance();
          if (c0_ == '=') return Select('=', Token::EQ_STRICT, Token::EQ);
          if (c0_ == '>') return Select(Token::ARROW);
          return Token::ASSIGN;

        case Token::NOT:
          // ! != !==
          Advance();
          if (c0_ == '=') return Select('=', Token::NE_STRICT, Token::NE);
          return Token::NOT;

        case Token::ADD:
          // + ++ +=
          Advance();
          if (c0_ == '+') return Select(Token::INC);
          if (c0_ == '=') return Select(Token::ASSIGN_ADD);
          return Token::ADD;

        case Token::SUB:
          // - -- --> -=
          Advance();
          if (c0_ == '-') {
417
            Advance();
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451
            if (c0_ == '>' && next().after_line_terminator) {
              // For compatibility with SpiderMonkey, we skip lines that
              // start with an HTML comment end '-->'.
              token = SkipSingleHTMLComment();
              continue;
            }
            return Token::DEC;
          }
          if (c0_ == '=') return Select(Token::ASSIGN_SUB);
          return Token::SUB;

        case Token::MUL:
          // * *=
          Advance();
          if (c0_ == '*') return Select('=', Token::ASSIGN_EXP, Token::EXP);
          if (c0_ == '=') return Select(Token::ASSIGN_MUL);
          return Token::MUL;

        case Token::MOD:
          // % %=
          return Select('=', Token::ASSIGN_MOD, Token::MOD);

        case Token::DIV:
          // /  // /* /=
          Advance();
          if (c0_ == '/') {
            uc32 c = Peek();
            if (c == '#' || c == '@') {
              Advance();
              Advance();
              token = SkipSourceURLComment();
              continue;
            }
            token = SkipSingleLineComment();
452 453
            continue;
          }
454 455 456
          if (c0_ == '*') {
            token = SkipMultiLineComment();
            continue;
457
          }
458 459 460 461 462 463 464 465 466
          if (c0_ == '=') return Select(Token::ASSIGN_DIV);
          return Token::DIV;

        case Token::BIT_AND:
          // & && &=
          Advance();
          if (c0_ == '&') return Select(Token::AND);
          if (c0_ == '=') return Select(Token::ASSIGN_BIT_AND);
          return Token::BIT_AND;
467

468 469 470 471 472 473
        case Token::BIT_OR:
          // | || |=
          Advance();
          if (c0_ == '|') return Select(Token::OR);
          if (c0_ == '=') return Select(Token::ASSIGN_BIT_OR);
          return Token::BIT_OR;
474

475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490
        case Token::BIT_XOR:
          // ^ ^=
          return Select('=', Token::ASSIGN_BIT_XOR, Token::BIT_XOR);

        case Token::PERIOD:
          // . Number
          Advance();
          if (IsDecimalDigit(c0_)) return ScanNumber(true);
          if (c0_ == '.') {
            if (Peek() == '.') {
              Advance();
              Advance();
              return Token::ELLIPSIS;
            }
          }
          return Token::PERIOD;
491

492 493 494 495 496 497 498 499 500 501 502 503 504 505 506
        case Token::TEMPLATE_SPAN:
          Advance();
          return ScanTemplateSpan();

        case Token::PRIVATE_NAME:
          return ScanPrivateName();

        case Token::WHITESPACE:
          token = SkipWhiteSpace();
          continue;

        case Token::NUMBER:
          return ScanNumber(false);

        case Token::IDENTIFIER:
507
          return ScanIdentifierOrKeyword();
508 509 510 511

        default:
          UNREACHABLE();
      }
512
    }
513

514 515
    if (IsIdentifierStart(c0_) ||
        (CombineSurrogatePair() && IsIdentifierStart(c0_))) {
516 517 518 519 520 521 522
      return ScanIdentifierOrKeyword();
    }
    if (c0_ == kEndOfInput) {
      return source_->has_parser_error() ? Token::ILLEGAL : Token::EOS;
    }
    token = SkipWhiteSpace();

523 524 525 526 527 528
    // Continue scanning for tokens as long as we're just skipping whitespace.
  } while (token == Token::WHITESPACE);

  return token;
}

529 530
void Scanner::Scan(TokenDesc* next_desc) {
  DCHECK_EQ(next_desc, &next());
531

532 533 534
  next_desc->token = ScanSingleToken();
  DCHECK_IMPLIES(has_parser_error(), next_desc->token == Token::ILLEGAL);
  next_desc->location.end_pos = source_pos();
535 536 537 538 539 540 541 542

#ifdef DEBUG
  SanityCheckTokenDesc(current());
  SanityCheckTokenDesc(next());
  SanityCheckTokenDesc(next_next());
#endif
}

543 544
void Scanner::Scan() { Scan(next_); }

545 546 547 548
}  // namespace internal
}  // namespace v8

#endif  // V8_PARSING_SCANNER_INL_H_