Home | History | Annotate | Download | only in src 
      1 // Copyright 2011 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #include "v8.h"
     29 
     30 #include "ast.h"
     31 #include "handles.h"
     32 #include "scanner.h"
     33 #include "unicode-inl.h"
     34 
     35 namespace v8 {
     36 namespace internal {
     37 
     38 // ----------------------------------------------------------------------------
     39 // BufferedUC16CharacterStreams
     40 
     41 BufferedUC16CharacterStream::BufferedUC16CharacterStream()
     42     : UC16CharacterStream(),
     43       pushback_limit_(NULL) {
     44   // Initialize buffer as being empty. First read will fill the buffer.
     45   buffer_cursor_ = buffer_;
     46   buffer_end_ = buffer_;
     47 }
     48 
     49 BufferedUC16CharacterStream::~BufferedUC16CharacterStream() { }
     50 
     51 void BufferedUC16CharacterStream::PushBack(uc32 character) {
     52   if (character == kEndOfInput) {
     53     pos_--;
     54     return;
     55   }
     56   if (pushback_limit_ == NULL && buffer_cursor_ > buffer_) {
     57     // buffer_ is writable, buffer_cursor_ is const pointer.
     58     buffer_[--buffer_cursor_ - buffer_] = static_cast<uc16>(character);
     59     pos_--;
     60     return;
     61   }
     62   SlowPushBack(static_cast<uc16>(character));
     63 }
     64 
     65 
     66 void BufferedUC16CharacterStream::SlowPushBack(uc16 character) {
     67   // In pushback mode, the end of the buffer contains pushback,
     68   // and the start of the buffer (from buffer start to pushback_limit_)
     69   // contains valid data that comes just after the pushback.
     70   // We NULL the pushback_limit_ if pushing all the way back to the
     71   // start of the buffer.
     72 
     73   if (pushback_limit_ == NULL) {
     74     // Enter pushback mode.
     75     pushback_limit_ = buffer_end_;
     76     buffer_end_ = buffer_ + kBufferSize;
     77     buffer_cursor_ = buffer_end_;
     78   }
     79   // Ensure that there is room for at least one pushback.
     80   ASSERT(buffer_cursor_ > buffer_);
     81   ASSERT(pos_ > 0);
     82   buffer_[--buffer_cursor_ - buffer_] = character;
     83   if (buffer_cursor_ == buffer_) {
     84     pushback_limit_ = NULL;
     85   } else if (buffer_cursor_ < pushback_limit_) {
     86     pushback_limit_ = buffer_cursor_;
     87   }
     88   pos_--;
     89 }
     90 
     91 
     92 bool BufferedUC16CharacterStream::ReadBlock() {
     93   buffer_cursor_ = buffer_;
     94   if (pushback_limit_ != NULL) {
     95     // Leave pushback mode.
     96     buffer_end_ = pushback_limit_;
     97     pushback_limit_ = NULL;
     98     // If there were any valid characters left at the
     99     // start of the buffer, use those.
    100     if (buffer_cursor_ < buffer_end_) return true;
    101     // Otherwise read a new block.
    102   }
    103   unsigned length = FillBuffer(pos_, kBufferSize);
    104   buffer_end_ = buffer_ + length;
    105   return length > 0;
    106 }
    107 
    108 
    109 unsigned BufferedUC16CharacterStream::SlowSeekForward(unsigned delta) {
    110   // Leave pushback mode (i.e., ignore that there might be valid data
    111   // in the buffer before the pushback_limit_ point).
    112   pushback_limit_ = NULL;
    113   return BufferSeekForward(delta);
    114 }
    115 
    116 // ----------------------------------------------------------------------------
    117 // GenericStringUC16CharacterStream
    118 
    119 
    120 GenericStringUC16CharacterStream::GenericStringUC16CharacterStream(
    121     Handle<String> data,
    122     unsigned start_position,
    123     unsigned end_position)
    124     : string_(data),
    125       length_(end_position) {
    126   ASSERT(end_position >= start_position);
    127   buffer_cursor_ = buffer_;
    128   buffer_end_ = buffer_;
    129   pos_ = start_position;
    130 }
    131 
    132 
    133 GenericStringUC16CharacterStream::~GenericStringUC16CharacterStream() { }
    134 
    135 
    136 unsigned GenericStringUC16CharacterStream::BufferSeekForward(unsigned delta) {
    137   unsigned old_pos = pos_;
    138   pos_ = Min(pos_ + delta, length_);
    139   ReadBlock();
    140   return pos_ - old_pos;
    141 }
    142 
    143 
    144 unsigned GenericStringUC16CharacterStream::FillBuffer(unsigned from_pos,
    145                                                       unsigned length) {
    146   if (from_pos >= length_) return 0;
    147   if (from_pos + length > length_) {
    148     length = length_ - from_pos;
    149   }
    150   String::WriteToFlat<uc16>(*string_, buffer_, from_pos, from_pos + length);
    151   return length;
    152 }
    153 
    154 
    155 // ----------------------------------------------------------------------------
    156 // Utf8ToUC16CharacterStream
    157 Utf8ToUC16CharacterStream::Utf8ToUC16CharacterStream(const byte* data,
    158                                                      unsigned length)
    159     : BufferedUC16CharacterStream(),
    160       raw_data_(data),
    161       raw_data_length_(length),
    162       raw_data_pos_(0),
    163       raw_character_position_(0) {
    164   ReadBlock();
    165 }
    166 
    167 
    168 Utf8ToUC16CharacterStream::~Utf8ToUC16CharacterStream() { }
    169 
    170 
    171 unsigned Utf8ToUC16CharacterStream::BufferSeekForward(unsigned delta) {
    172   unsigned old_pos = pos_;
    173   unsigned target_pos = pos_ + delta;
    174   SetRawPosition(target_pos);
    175   pos_ = raw_character_position_;
    176   ReadBlock();
    177   return pos_ - old_pos;
    178 }
    179 
    180 
    181 unsigned Utf8ToUC16CharacterStream::FillBuffer(unsigned char_position,
    182                                                unsigned length) {
    183   static const unibrow::uchar kMaxUC16Character = 0xffff;
    184   SetRawPosition(char_position);
    185   if (raw_character_position_ != char_position) {
    186     // char_position was not a valid position in the stream (hit the end
    187     // while spooling to it).
    188     return 0u;
    189   }
    190   unsigned i = 0;
    191   while (i < length) {
    192     if (raw_data_pos_ == raw_data_length_) break;
    193     unibrow::uchar c = raw_data_[raw_data_pos_];
    194     if (c <= unibrow::Utf8::kMaxOneByteChar) {
    195       raw_data_pos_++;
    196     } else {
    197       c =  unibrow::Utf8::CalculateValue(raw_data_ + raw_data_pos_,
    198                                          raw_data_length_ - raw_data_pos_,
    199                                          &raw_data_pos_);
    200       // Don't allow characters outside of the BMP.
    201       if (c > kMaxUC16Character) {
    202         c = unibrow::Utf8::kBadChar;
    203       }
    204     }
    205     buffer_[i++] = static_cast<uc16>(c);
    206   }
    207   raw_character_position_ = char_position + i;
    208   return i;
    209 }
    210 
    211 
    212 static const byte kUtf8MultiByteMask = 0xC0;
    213 static const byte kUtf8MultiByteCharStart = 0xC0;
    214 static const byte kUtf8MultiByteCharFollower = 0x80;
    215 
    216 
    217 #ifdef DEBUG
    218 static bool IsUtf8MultiCharacterStart(byte first_byte) {
    219   return (first_byte & kUtf8MultiByteMask) == kUtf8MultiByteCharStart;
    220 }
    221 #endif
    222 
    223 
    224 static bool IsUtf8MultiCharacterFollower(byte later_byte) {
    225   return (later_byte & kUtf8MultiByteMask) == kUtf8MultiByteCharFollower;
    226 }
    227 
    228 
    229 // Move the cursor back to point at the preceding UTF-8 character start
    230 // in the buffer.
    231 static inline void Utf8CharacterBack(const byte* buffer, unsigned* cursor) {
    232   byte character = buffer[--*cursor];
    233   if (character > unibrow::Utf8::kMaxOneByteChar) {
    234     ASSERT(IsUtf8MultiCharacterFollower(character));
    235     // Last byte of a multi-byte character encoding. Step backwards until
    236     // pointing to the first byte of the encoding, recognized by having the
    237     // top two bits set.
    238     while (IsUtf8MultiCharacterFollower(buffer[--*cursor])) { }
    239     ASSERT(IsUtf8MultiCharacterStart(buffer[*cursor]));
    240   }
    241 }
    242 
    243 
    244 // Move the cursor forward to point at the next following UTF-8 character start
    245 // in the buffer.
    246 static inline void Utf8CharacterForward(const byte* buffer, unsigned* cursor) {
    247   byte character = buffer[(*cursor)++];
    248   if (character > unibrow::Utf8::kMaxOneByteChar) {
    249     // First character of a multi-byte character encoding.
    250     // The number of most-significant one-bits determines the length of the
    251     // encoding:
    252     //  110..... - (0xCx, 0xDx) one additional byte (minimum).
    253     //  1110.... - (0xEx) two additional bytes.
    254     //  11110... - (0xFx) three additional bytes (maximum).
    255     ASSERT(IsUtf8MultiCharacterStart(character));
    256     // Additional bytes is:
    257     // 1 if value in range 0xC0 .. 0xDF.
    258     // 2 if value in range 0xE0 .. 0xEF.
    259     // 3 if value in range 0xF0 .. 0xF7.
    260     // Encode that in a single value.
    261     unsigned additional_bytes =
    262         ((0x3211u) >> (((character - 0xC0) >> 2) & 0xC)) & 0x03;
    263     *cursor += additional_bytes;
    264     ASSERT(!IsUtf8MultiCharacterFollower(buffer[1 + additional_bytes]));
    265   }
    266 }
    267 
    268 
    269 void Utf8ToUC16CharacterStream::SetRawPosition(unsigned target_position) {
    270   if (raw_character_position_ > target_position) {
    271     // Spool backwards in utf8 buffer.
    272     do {
    273       Utf8CharacterBack(raw_data_, &raw_data_pos_);
    274       raw_character_position_--;
    275     } while (raw_character_position_ > target_position);
    276     return;
    277   }
    278   // Spool forwards in the utf8 buffer.
    279   while (raw_character_position_ < target_position) {
    280     if (raw_data_pos_ == raw_data_length_) return;
    281     Utf8CharacterForward(raw_data_, &raw_data_pos_);
    282     raw_character_position_++;
    283   }
    284 }
    285 
    286 
    287 // ----------------------------------------------------------------------------
    288 // ExternalTwoByteStringUC16CharacterStream
    289 
    290 ExternalTwoByteStringUC16CharacterStream::
    291     ~ExternalTwoByteStringUC16CharacterStream() { }
    292 
    293 
    294 ExternalTwoByteStringUC16CharacterStream
    295     ::ExternalTwoByteStringUC16CharacterStream(
    296         Handle<ExternalTwoByteString> data,
    297         int start_position,
    298         int end_position)
    299     : UC16CharacterStream(),
    300       source_(data),
    301       raw_data_(data->GetTwoByteData(start_position)) {
    302   buffer_cursor_ = raw_data_,
    303   buffer_end_ = raw_data_ + (end_position - start_position);
    304   pos_ = start_position;
    305 }
    306 
    307 
    308 // ----------------------------------------------------------------------------
    309 // Scanner::LiteralScope
    310 
    311 Scanner::LiteralScope::LiteralScope(Scanner* self)
    312     : scanner_(self), complete_(false) {
    313   self->StartLiteral();
    314 }
    315 
    316 
    317 Scanner::LiteralScope::~LiteralScope() {
    318   if (!complete_) scanner_->DropLiteral();
    319 }
    320 
    321 
    322 void Scanner::LiteralScope::Complete() {
    323   scanner_->TerminateLiteral();
    324   complete_ = true;
    325 }
    326 
    327 
    328 // ----------------------------------------------------------------------------
    329 // V8JavaScriptScanner
    330 
    331 
    332 void V8JavaScriptScanner::Initialize(UC16CharacterStream* source) {
    333   source_ = source;
    334   // Need to capture identifiers in order to recognize "get" and "set"
    335   // in object literals.
    336   Init();
    337   // Skip initial whitespace allowing HTML comment ends just like
    338   // after a newline and scan first token.
    339   has_line_terminator_before_next_ = true;
    340   SkipWhiteSpace();
    341   Scan();
    342 }
    343 
    344 
    345 // ----------------------------------------------------------------------------
    346 // JsonScanner
    347 
    348 JsonScanner::JsonScanner(UnicodeCache* unicode_cache)
    349     : Scanner(unicode_cache) { }
    350 
    351 
    352 void JsonScanner::Initialize(UC16CharacterStream* source) {
    353   source_ = source;
    354   Init();
    355   // Skip initial whitespace.
    356   SkipJsonWhiteSpace();
    357   // Preload first token as look-ahead.
    358   ScanJson();
    359 }
    360 
    361 
    362 Token::Value JsonScanner::Next() {
    363   // BUG 1215673: Find a thread safe way to set a stack limit in
    364   // pre-parse mode. Otherwise, we cannot safely pre-parse from other
    365   // threads.
    366   current_ = next_;
    367   // Check for stack-overflow before returning any tokens.
    368   ScanJson();
    369   return current_.token;
    370 }
    371 
    372 
    373 bool JsonScanner::SkipJsonWhiteSpace() {
    374   int start_position = source_pos();
    375   // JSON WhiteSpace is tab, carrige-return, newline and space.
    376   while (c0_ == ' ' || c0_ == '\n' || c0_ == '\r' || c0_ == '\t') {
    377     Advance();
    378   }
    379   return source_pos() != start_position;
    380 }
    381 
    382 
    383 void JsonScanner::ScanJson() {
    384   next_.literal_chars = NULL;
    385   Token::Value token;
    386   do {
    387     // Remember the position of the next token
    388     next_.location.beg_pos = source_pos();
    389     switch (c0_) {
    390       case '\t':
    391       case '\r':
    392       case '\n':
    393       case ' ':
    394         Advance();
    395         token = Token::WHITESPACE;
    396         break;
    397       case '{':
    398         Advance();
    399         token = Token::LBRACE;
    400         break;
    401       case '}':
    402         Advance();
    403         token = Token::RBRACE;
    404         break;
    405       case '[':
    406         Advance();
    407         token = Token::LBRACK;
    408         break;
    409       case ']':
    410         Advance();
    411         token = Token::RBRACK;
    412         break;
    413       case ':':
    414         Advance();
    415         token = Token::COLON;
    416         break;
    417       case ',':
    418         Advance();
    419         token = Token::COMMA;
    420         break;
    421       case '"':
    422         token = ScanJsonString();
    423         break;
    424       case '-':
    425       case '0':
    426       case '1':
    427       case '2':
    428       case '3':
    429       case '4':
    430       case '5':
    431       case '6':
    432       case '7':
    433       case '8':
    434       case '9':
    435         token = ScanJsonNumber();
    436         break;
    437       case 't':
    438         token = ScanJsonIdentifier("true", Token::TRUE_LITERAL);
    439         break;
    440       case 'f':
    441         token = ScanJsonIdentifier("false", Token::FALSE_LITERAL);
    442         break;
    443       case 'n':
    444         token = ScanJsonIdentifier("null", Token::NULL_LITERAL);
    445         break;
    446       default:
    447         if (c0_ < 0) {
    448           Advance();
    449           token = Token::EOS;
    450         } else {
    451           Advance();
    452           token = Select(Token::ILLEGAL);
    453         }
    454     }
    455   } while (token == Token::WHITESPACE);
    456 
    457   next_.location.end_pos = source_pos();
    458   next_.token = token;
    459 }
    460 
    461 
    462 Token::Value JsonScanner::ScanJsonString() {
    463   ASSERT_EQ('"', c0_);
    464   Advance();
    465   LiteralScope literal(this);
    466   while (c0_ != '"') {
    467     // Check for control character (0x00-0x1f) or unterminated string (<0).
    468     if (c0_ < 0x20) return Token::ILLEGAL;
    469     if (c0_ != '\\') {
    470       AddLiteralCharAdvance();
    471     } else {
    472       Advance();
    473       switch (c0_) {
    474         case '"':
    475         case '\\':
    476         case '/':
    477           AddLiteralChar(c0_);
    478           break;
    479         case 'b':
    480           AddLiteralChar('\x08');
    481           break;
    482         case 'f':
    483           AddLiteralChar('\x0c');
    484           break;
    485         case 'n':
    486           AddLiteralChar('\x0a');
    487           break;
    488         case 'r':
    489           AddLiteralChar('\x0d');
    490           break;
    491         case 't':
    492           AddLiteralChar('\x09');
    493           break;
    494         case 'u': {
    495           uc32 value = 0;
    496           for (int i = 0; i < 4; i++) {
    497             Advance();
    498             int digit = HexValue(c0_);
    499             if (digit < 0) {
    500               return Token::ILLEGAL;
    501             }
    502             value = value * 16 + digit;
    503           }
    504           AddLiteralChar(value);
    505           break;
    506         }
    507         default:
    508           return Token::ILLEGAL;
    509       }
    510       Advance();
    511     }
    512   }
    513   literal.Complete();
    514   Advance();
    515   return Token::STRING;
    516 }
    517 
    518 
    519 Token::Value JsonScanner::ScanJsonNumber() {
    520   LiteralScope literal(this);
    521   bool negative = false;
    522 
    523   if (c0_ == '-') {
    524     AddLiteralCharAdvance();
    525     negative = true;
    526   }
    527   if (c0_ == '0') {
    528     AddLiteralCharAdvance();
    529     // Prefix zero is only allowed if it's the only digit before
    530     // a decimal point or exponent.
    531     if ('0' <= c0_ && c0_ <= '9') return Token::ILLEGAL;
    532   } else {
    533     int i = 0;
    534     int digits = 0;
    535     if (c0_ < '1' || c0_ > '9') return Token::ILLEGAL;
    536     do {
    537       i = i * 10 + c0_ - '0';
    538       digits++;
    539       AddLiteralCharAdvance();
    540     } while (c0_ >= '0' && c0_ <= '9');
    541     if (c0_ != '.' && c0_ != 'e' && c0_ != 'E' && digits < 10) {
    542       number_ = (negative ? -i : i);
    543       return Token::NUMBER;
    544     }
    545   }
    546   if (c0_ == '.') {
    547     AddLiteralCharAdvance();
    548     if (c0_ < '0' || c0_ > '9') return Token::ILLEGAL;
    549     do {
    550       AddLiteralCharAdvance();
    551     } while (c0_ >= '0' && c0_ <= '9');
    552   }
    553   if (AsciiAlphaToLower(c0_) == 'e') {
    554     AddLiteralCharAdvance();
    555     if (c0_ == '-' || c0_ == '+') AddLiteralCharAdvance();
    556     if (c0_ < '0' || c0_ > '9') return Token::ILLEGAL;
    557     do {
    558       AddLiteralCharAdvance();
    559     } while (c0_ >= '0' && c0_ <= '9');
    560   }
    561   literal.Complete();
    562   ASSERT_NOT_NULL(next_.literal_chars);
    563   number_ = StringToDouble(unicode_cache_,
    564                            next_.literal_chars->ascii_literal(),
    565                            NO_FLAGS,  // Hex, octal or trailing junk.
    566                            OS::nan_value());
    567   return Token::NUMBER;
    568 }
    569 
    570 
    571 Token::Value JsonScanner::ScanJsonIdentifier(const char* text,
    572                                              Token::Value token) {
    573   LiteralScope literal(this);
    574   while (*text != '\0') {
    575     if (c0_ != *text) return Token::ILLEGAL;
    576     Advance();
    577     text++;
    578   }
    579   if (unicode_cache_->IsIdentifierPart(c0_)) return Token::ILLEGAL;
    580   literal.Complete();
    581   return token;
    582 }
    583 
    584 
    585 } }  // namespace v8::internal
    586