blob: 6e5333bce1e5defe347d3f4cac9e3fa51be4e382 [file] [log] [blame]
// Copyright 2010 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following
// disclaimer in the documentation and/or other materials provided
// with the distribution.
// * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived
// from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#ifndef V8_SCANNER_H_
#define V8_SCANNER_H_
#include "token.h"
#include "char-predicates-inl.h"
namespace v8 {
namespace internal {
class UTF8Buffer {
public:
UTF8Buffer();
~UTF8Buffer();
inline void AddChar(uc32 c) {
if (static_cast<unsigned>(c) <= unibrow::Utf8::kMaxOneByteChar) {
buffer_.Add(static_cast<char>(c));
} else {
AddCharSlow(c);
}
}
void StartLiteral() {
buffer_.StartSequence();
}
Vector<const char> EndLiteral() {
buffer_.Add(kEndMarker);
Vector<char> sequence = buffer_.EndSequence();
return Vector<const char>(sequence.start(), sequence.length());
}
void DropLiteral() {
buffer_.DropSequence();
}
void Reset() {
buffer_.Reset();
}
// The end marker added after a parsed literal.
// Using zero allows the usage of strlen and similar functions on
// identifiers and numbers (but not strings, since they may contain zero
// bytes).
// TODO(lrn): Use '\xff' as end marker, since it cannot occur inside
// an utf-8 string. This requires changes in all places that uses
// str-functions on the literals, but allows a single pointer to represent
// the literal, even if it contains embedded zeros.
static const char kEndMarker = '\x00';
private:
static const int kInitialCapacity = 256;
SequenceCollector<char, 4> buffer_;
void AddCharSlow(uc32 c);
};
// Interface through which the scanner reads characters from the input source.
class UTF16Buffer {
public:
UTF16Buffer();
virtual ~UTF16Buffer() {}
virtual void PushBack(uc32 ch) = 0;
// Returns a value < 0 when the buffer end is reached.
virtual uc32 Advance() = 0;
virtual void SeekForward(int pos) = 0;
int pos() const { return pos_; }
protected:
int pos_; // Current position in the buffer.
int end_; // Position where scanning should stop (EOF).
};
// UTF16 buffer to read characters from a character stream.
class CharacterStreamUTF16Buffer: public UTF16Buffer {
public:
CharacterStreamUTF16Buffer();
virtual ~CharacterStreamUTF16Buffer() {}
void Initialize(Handle<String> data,
unibrow::CharacterStream* stream,
int start_position,
int end_position);
virtual void PushBack(uc32 ch);
virtual uc32 Advance();
virtual void SeekForward(int pos);
private:
List<uc32> pushback_buffer_;
uc32 last_;
unibrow::CharacterStream* stream_;
List<uc32>* pushback_buffer() { return &pushback_buffer_; }
};
// UTF16 buffer to read characters from an external string.
template <typename StringType, typename CharType>
class ExternalStringUTF16Buffer: public UTF16Buffer {
public:
ExternalStringUTF16Buffer();
virtual ~ExternalStringUTF16Buffer() {}
void Initialize(Handle<StringType> data,
int start_position,
int end_position);
virtual void PushBack(uc32 ch);
virtual uc32 Advance();
virtual void SeekForward(int pos);
private:
const CharType* raw_data_; // Pointer to the actual array of characters.
};
class KeywordMatcher {
// Incrementally recognize keywords.
//
// Recognized keywords:
// break case catch const* continue debugger* default delete do else
// finally false for function if in instanceof native* new null
// return switch this throw true try typeof var void while with
//
// *: Actually "future reserved keywords". These are the only ones we
// recognized, the remaining are allowed as identifiers.
public:
KeywordMatcher()
: state_(INITIAL),
token_(Token::IDENTIFIER),
keyword_(NULL),
counter_(0),
keyword_token_(Token::ILLEGAL) {}
Token::Value token() { return token_; }
inline void AddChar(uc32 input) {
if (state_ != UNMATCHABLE) {
Step(input);
}
}
void Fail() {
token_ = Token::IDENTIFIER;
state_ = UNMATCHABLE;
}
private:
enum State {
UNMATCHABLE,
INITIAL,
KEYWORD_PREFIX,
KEYWORD_MATCHED,
C,
CA,
CO,
CON,
D,
DE,
F,
I,
IN,
N,
T,
TH,
TR,
V,
W
};
struct FirstState {
const char* keyword;
State state;
Token::Value token;
};
// Range of possible first characters of a keyword.
static const unsigned int kFirstCharRangeMin = 'b';
static const unsigned int kFirstCharRangeMax = 'w';
static const unsigned int kFirstCharRangeLength =
kFirstCharRangeMax - kFirstCharRangeMin + 1;
// State map for first keyword character range.
static FirstState first_states_[kFirstCharRangeLength];
// If input equals keyword's character at position, continue matching keyword
// from that position.
inline bool MatchKeywordStart(uc32 input,
const char* keyword,
int position,
Token::Value token_if_match) {
if (input == keyword[position]) {
state_ = KEYWORD_PREFIX;
this->keyword_ = keyword;
this->counter_ = position + 1;
this->keyword_token_ = token_if_match;
return true;
}
return false;
}
// If input equals match character, transition to new state and return true.
inline bool MatchState(uc32 input, char match, State new_state) {
if (input == match) {
state_ = new_state;
return true;
}
return false;
}
inline bool MatchKeyword(uc32 input,
char match,
State new_state,
Token::Value keyword_token) {
if (input != match) {
return false;
}
state_ = new_state;
token_ = keyword_token;
return true;
}
void Step(uc32 input);
// Current state.
State state_;
// Token for currently added characters.
Token::Value token_;
// Matching a specific keyword string (there is only one possible valid
// keyword with the current prefix).
const char* keyword_;
int counter_;
Token::Value keyword_token_;
};
enum ParserMode { PARSE, PREPARSE };
enum ParserLanguage { JAVASCRIPT, JSON };
class Scanner {
public:
typedef unibrow::Utf8InputBuffer<1024> Utf8Decoder;
class LiteralScope {
public:
explicit LiteralScope(Scanner* self);
~LiteralScope();
void Complete();
private:
Scanner* scanner_;
bool complete_;
};
Scanner();
// Initialize the Scanner to scan source.
void Initialize(Handle<String> source,
ParserLanguage language);
void Initialize(Handle<String> source,
unibrow::CharacterStream* stream,
ParserLanguage language);
void Initialize(Handle<String> source,
int start_position, int end_position,
ParserLanguage language);
// Returns the next token.
Token::Value Next();
// One token look-ahead (past the token returned by Next()).
Token::Value peek() const { return next_.token; }
// Returns true if there was a line terminator before the peek'ed token.
bool has_line_terminator_before_next() const {
return has_line_terminator_before_next_;
}
struct Location {
Location(int b, int e) : beg_pos(b), end_pos(e) { }
Location() : beg_pos(0), end_pos(0) { }
int beg_pos;
int end_pos;
};
// Returns the location information for the current token
// (the token returned by Next()).
Location location() const { return current_.location; }
Location peek_location() const { return next_.location; }
// Returns the literal string, if any, for the current token (the
// token returned by Next()). The string is 0-terminated and in
// UTF-8 format; they may contain 0-characters. Literal strings are
// collected for identifiers, strings, and numbers.
// These functions only give the correct result if the literal
// was scanned between calls to StartLiteral() and TerminateLiteral().
const char* literal_string() const {
return current_.literal_chars.start();
}
int literal_length() const {
// Excluding terminal '\x00' added by TerminateLiteral().
return current_.literal_chars.length() - 1;
}
Vector<const char> literal() const {
return Vector<const char>(literal_string(), literal_length());
}
// Returns the literal string for the next token (the token that
// would be returned if Next() were called).
const char* next_literal_string() const {
return next_.literal_chars.start();
}
// Returns the length of the next token (that would be returned if
// Next() were called).
int next_literal_length() const {
// Excluding terminal '\x00' added by TerminateLiteral().
return next_.literal_chars.length() - 1;
}
Vector<const char> next_literal() const {
return Vector<const char>(next_literal_string(), next_literal_length());
}
// Scans the input as a regular expression pattern, previous
// character(s) must be /(=). Returns true if a pattern is scanned.
bool ScanRegExpPattern(bool seen_equal);
// Returns true if regexp flags are scanned (always since flags can
// be empty).
bool ScanRegExpFlags();
// Seek forward to the given position. This operation does not
// work in general, for instance when there are pushed back
// characters, but works for seeking forward until simple delimiter
// tokens, which is what it is used for.
void SeekForward(int pos);
bool stack_overflow() { return stack_overflow_; }
static StaticResource<Utf8Decoder>* utf8_decoder() { return &utf8_decoder_; }
// Tells whether the buffer contains an identifier (no escapes).
// Used for checking if a property name is an identifier.
static bool IsIdentifier(unibrow::CharacterStream* buffer);
static unibrow::Predicate<IdentifierStart, 128> kIsIdentifierStart;
static unibrow::Predicate<IdentifierPart, 128> kIsIdentifierPart;
static unibrow::Predicate<unibrow::LineTerminator, 128> kIsLineTerminator;
static unibrow::Predicate<unibrow::WhiteSpace, 128> kIsWhiteSpace;
static const int kCharacterLookaheadBufferSize = 1;
static const int kNoEndPosition = 1;
private:
// The current and look-ahead token.
struct TokenDesc {
Token::Value token;
Location location;
Vector<const char> literal_chars;
};
void Init(Handle<String> source,
unibrow::CharacterStream* stream,
int start_position, int end_position,
ParserLanguage language);
// Literal buffer support
inline void StartLiteral();
inline void AddChar(uc32 ch);
inline void AddCharAdvance();
inline void TerminateLiteral();
// Stops scanning of a literal, e.g., due to an encountered error.
inline void DropLiteral();
// Low-level scanning support.
void Advance() { c0_ = source_->Advance(); }
void PushBack(uc32 ch) {
source_->PushBack(ch);
c0_ = ch;
}
bool SkipWhiteSpace() {
if (is_parsing_json_) {
return SkipJsonWhiteSpace();
} else {
return SkipJavaScriptWhiteSpace();
}
}
bool SkipJavaScriptWhiteSpace();
bool SkipJsonWhiteSpace();
Token::Value SkipSingleLineComment();
Token::Value SkipMultiLineComment();
inline Token::Value Select(Token::Value tok);
inline Token::Value Select(uc32 next, Token::Value then, Token::Value else_);
inline void Scan() {
if (is_parsing_json_) {
ScanJson();
} else {
ScanJavaScript();
}
}
// Scans a single JavaScript token.
void ScanJavaScript();
// Scan a single JSON token. The JSON lexical grammar is specified in the
// ECMAScript 5 standard, section 15.12.1.1.
// Recognizes all of the single-character tokens directly, or calls a function
// to scan a number, string or identifier literal.
// The only allowed whitespace characters between tokens are tab,
// carrige-return, newline and space.
void ScanJson();
// A JSON number (production JSONNumber) is a subset of the valid JavaScript
// decimal number literals.
// It includes an optional minus sign, must have at least one
// digit before and after a decimal point, may not have prefixed zeros (unless
// the integer part is zero), and may include an exponent part (e.g., "e-10").
// Hexadecimal and octal numbers are not allowed.
Token::Value ScanJsonNumber();
// A JSON string (production JSONString) is subset of valid JavaScript string
// literals. The string must only be double-quoted (not single-quoted), and
// the only allowed backslash-escapes are ", /, \, b, f, n, r, t and
// four-digit hex escapes (uXXXX). Any other use of backslashes is invalid.
Token::Value ScanJsonString();
// Used to recognizes one of the literals "true", "false", or "null". These
// are the only valid JSON identifiers (productions JSONBooleanLiteral,
// JSONNullLiteral).
Token::Value ScanJsonIdentifier(const char* text, Token::Value token);
void ScanDecimalDigits();
Token::Value ScanNumber(bool seen_period);
Token::Value ScanIdentifier();
uc32 ScanHexEscape(uc32 c, int length);
uc32 ScanOctalEscape(uc32 c, int length);
void ScanEscape();
Token::Value ScanString();
// Scans a possible HTML comment -- begins with '<!'.
Token::Value ScanHtmlComment();
// Return the current source position.
int source_pos() {
return source_->pos() - kCharacterLookaheadBufferSize;
}
// Decodes a unicode escape-sequence which is part of an identifier.
// If the escape sequence cannot be decoded the result is kBadRune.
uc32 ScanIdentifierUnicodeEscape();
TokenDesc current_; // desc for current token (as returned by Next())
TokenDesc next_; // desc for next token (one token look-ahead)
bool has_line_terminator_before_next_;
bool is_parsing_json_;
// Different UTF16 buffers used to pull characters from. Based on input one of
// these will be initialized as the actual data source.
CharacterStreamUTF16Buffer char_stream_buffer_;
ExternalStringUTF16Buffer<ExternalTwoByteString, uint16_t>
two_byte_string_buffer_;
ExternalStringUTF16Buffer<ExternalAsciiString, char> ascii_string_buffer_;
// Source. Will point to one of the buffers declared above.
UTF16Buffer* source_;
// Used to convert the source string into a character stream when a stream
// is not passed to the scanner.
SafeStringInputBuffer safe_string_input_buffer_;
// Buffer to hold literal values (identifiers, strings, numbers)
// using '\x00'-terminated UTF-8 encoding. Handles allocation internally.
UTF8Buffer literal_buffer_;
bool stack_overflow_;
static StaticResource<Utf8Decoder> utf8_decoder_;
// One Unicode character look-ahead; c0_ < 0 at the end of the input.
uc32 c0_;
};
} } // namespace v8::internal
#endif // V8_SCANNER_H_