scanner-character-streams.cc 19.6 KB
Newer Older
1
// Copyright 2011 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/v8.h"
6

7
#include "src/scanner-character-streams.h"
8

9
#include "include/v8.h"
10 11
#include "src/handles.h"
#include "src/unicode-inl.h"
12 13 14 15

namespace v8 {
namespace internal {

16 17
namespace {

18 19 20
size_t CopyCharsHelper(uint16_t* dest, size_t length, const uint8_t* src,
                       size_t* src_pos, size_t src_length,
                       ScriptCompiler::StreamedSource::Encoding encoding) {
21 22 23 24
  // It's possible that this will be called with length 0, but don't assume that
  // the functions this calls handle it gracefully.
  if (length == 0) return 0;

25 26 27 28 29
  if (encoding == ScriptCompiler::StreamedSource::UTF8) {
    return v8::internal::Utf8ToUtf16CharacterStream::CopyChars(
        dest, length, src, src_pos, src_length);
  }

30
  size_t to_fill = length;
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
  if (to_fill > src_length - *src_pos) to_fill = src_length - *src_pos;

  if (encoding == ScriptCompiler::StreamedSource::ONE_BYTE) {
    v8::internal::CopyChars<uint8_t, uint16_t>(dest, src + *src_pos, to_fill);
  } else {
    DCHECK(encoding == ScriptCompiler::StreamedSource::TWO_BYTE);
    v8::internal::CopyChars<uint16_t, uint16_t>(
        dest, reinterpret_cast<const uint16_t*>(src + *src_pos), to_fill);
  }
  *src_pos += to_fill;
  return to_fill;
}

}  // namespace


47
// ----------------------------------------------------------------------------
48
// BufferedUtf16CharacterStreams
49

50 51
BufferedUtf16CharacterStream::BufferedUtf16CharacterStream()
    : Utf16CharacterStream(),
52 53 54 55 56 57
      pushback_limit_(NULL) {
  // Initialize buffer as being empty. First read will fill the buffer.
  buffer_cursor_ = buffer_;
  buffer_end_ = buffer_;
}

58

59
BufferedUtf16CharacterStream::~BufferedUtf16CharacterStream() { }
60

61
void BufferedUtf16CharacterStream::PushBack(uc32 character) {
62 63 64 65 66 67 68 69 70 71 72 73 74 75
  if (character == kEndOfInput) {
    pos_--;
    return;
  }
  if (pushback_limit_ == NULL && buffer_cursor_ > buffer_) {
    // buffer_ is writable, buffer_cursor_ is const pointer.
    buffer_[--buffer_cursor_ - buffer_] = static_cast<uc16>(character);
    pos_--;
    return;
  }
  SlowPushBack(static_cast<uc16>(character));
}


76
void BufferedUtf16CharacterStream::SlowPushBack(uc16 character) {
77 78 79 80 81 82 83 84 85 86 87 88 89
  // In pushback mode, the end of the buffer contains pushback,
  // and the start of the buffer (from buffer start to pushback_limit_)
  // contains valid data that comes just after the pushback.
  // We NULL the pushback_limit_ if pushing all the way back to the
  // start of the buffer.

  if (pushback_limit_ == NULL) {
    // Enter pushback mode.
    pushback_limit_ = buffer_end_;
    buffer_end_ = buffer_ + kBufferSize;
    buffer_cursor_ = buffer_end_;
  }
  // Ensure that there is room for at least one pushback.
90 91
  DCHECK(buffer_cursor_ > buffer_);
  DCHECK(pos_ > 0);
92 93 94 95 96 97 98 99 100 101
  buffer_[--buffer_cursor_ - buffer_] = character;
  if (buffer_cursor_ == buffer_) {
    pushback_limit_ = NULL;
  } else if (buffer_cursor_ < pushback_limit_) {
    pushback_limit_ = buffer_cursor_;
  }
  pos_--;
}


102
bool BufferedUtf16CharacterStream::ReadBlock() {
103 104 105 106 107 108 109 110 111 112
  buffer_cursor_ = buffer_;
  if (pushback_limit_ != NULL) {
    // Leave pushback mode.
    buffer_end_ = pushback_limit_;
    pushback_limit_ = NULL;
    // If there were any valid characters left at the
    // start of the buffer, use those.
    if (buffer_cursor_ < buffer_end_) return true;
    // Otherwise read a new block.
  }
113
  size_t length = FillBuffer(pos_);
114 115 116 117 118
  buffer_end_ = buffer_ + length;
  return length > 0;
}


119
size_t BufferedUtf16CharacterStream::SlowSeekForward(size_t delta) {
120 121 122 123 124 125
  // Leave pushback mode (i.e., ignore that there might be valid data
  // in the buffer before the pushback_limit_ point).
  pushback_limit_ = NULL;
  return BufferSeekForward(delta);
}

126

127
// ----------------------------------------------------------------------------
128
// GenericStringUtf16CharacterStream
129 130


131
GenericStringUtf16CharacterStream::GenericStringUtf16CharacterStream(
132
    Handle<String> data, size_t start_position, size_t end_position)
133
    : string_(data), length_(end_position), bookmark_(kNoBookmark) {
134
  DCHECK(end_position >= start_position);
135 136 137 138
  pos_ = start_position;
}


139
GenericStringUtf16CharacterStream::~GenericStringUtf16CharacterStream() { }
140 141


142 143 144 145 146 147 148 149 150 151 152 153 154 155
bool GenericStringUtf16CharacterStream::SetBookmark() {
  bookmark_ = pos_;
  return true;
}


void GenericStringUtf16CharacterStream::ResetToBookmark() {
  DCHECK(bookmark_ != kNoBookmark);
  pos_ = bookmark_;
  buffer_cursor_ = buffer_;
  buffer_end_ = buffer_ + FillBuffer(pos_);
}


156 157
size_t GenericStringUtf16CharacterStream::BufferSeekForward(size_t delta) {
  size_t old_pos = pos_;
158 159 160 161 162 163
  pos_ = Min(pos_ + delta, length_);
  ReadBlock();
  return pos_ - old_pos;
}


164
size_t GenericStringUtf16CharacterStream::FillBuffer(size_t from_pos) {
165
  if (from_pos >= length_) return 0;
166
  size_t length = kBufferSize;
167 168 169
  if (from_pos + length > length_) {
    length = length_ - from_pos;
  }
170 171
  String::WriteToFlat<uc16>(*string_, buffer_, static_cast<int>(from_pos),
                            static_cast<int>(from_pos + length));
172 173 174 175 176
  return length;
}


// ----------------------------------------------------------------------------
177 178
// Utf8ToUtf16CharacterStream
Utf8ToUtf16CharacterStream::Utf8ToUtf16CharacterStream(const byte* data,
179
                                                       size_t length)
180
    : BufferedUtf16CharacterStream(),
181 182 183 184 185 186 187 188
      raw_data_(data),
      raw_data_length_(length),
      raw_data_pos_(0),
      raw_character_position_(0) {
  ReadBlock();
}


189
Utf8ToUtf16CharacterStream::~Utf8ToUtf16CharacterStream() { }
190 191


192 193 194
size_t Utf8ToUtf16CharacterStream::CopyChars(uint16_t* dest, size_t length,
                                             const byte* src, size_t* src_pos,
                                             size_t src_length) {
195
  static const unibrow::uchar kMaxUtf16Character = 0xffff;
196
  size_t i = 0;
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
  // Because of the UTF-16 lead and trail surrogates, we stop filling the buffer
  // one character early (in the normal case), because we need to have at least
  // two free spaces in the buffer to be sure that the next character will fit.
  while (i < length - 1) {
    if (*src_pos == src_length) break;
    unibrow::uchar c = src[*src_pos];
    if (c <= unibrow::Utf8::kMaxOneByteChar) {
      *src_pos = *src_pos + 1;
    } else {
      c = unibrow::Utf8::CalculateValue(src + *src_pos, src_length - *src_pos,
                                        src_pos);
    }
    if (c > kMaxUtf16Character) {
      dest[i++] = unibrow::Utf16::LeadSurrogate(c);
      dest[i++] = unibrow::Utf16::TrailSurrogate(c);
    } else {
      dest[i++] = static_cast<uc16>(c);
    }
  }
  return i;
}


220 221 222
size_t Utf8ToUtf16CharacterStream::BufferSeekForward(size_t delta) {
  size_t old_pos = pos_;
  size_t target_pos = pos_ + delta;
223 224 225 226 227 228 229
  SetRawPosition(target_pos);
  pos_ = raw_character_position_;
  ReadBlock();
  return pos_ - old_pos;
}


230
size_t Utf8ToUtf16CharacterStream::FillBuffer(size_t char_position) {
231 232 233 234 235 236
  SetRawPosition(char_position);
  if (raw_character_position_ != char_position) {
    // char_position was not a valid position in the stream (hit the end
    // while spooling to it).
    return 0u;
  }
237 238
  size_t i = CopyChars(buffer_, kBufferSize, raw_data_, &raw_data_pos_,
                       raw_data_length_);
239 240 241 242 243 244 245 246 247 248
  raw_character_position_ = char_position + i;
  return i;
}


static const byte kUtf8MultiByteMask = 0xC0;
static const byte kUtf8MultiByteCharFollower = 0x80;


#ifdef DEBUG
249
static const byte kUtf8MultiByteCharStart = 0xC0;
250 251 252 253 254 255 256 257 258 259 260 261 262
static bool IsUtf8MultiCharacterStart(byte first_byte) {
  return (first_byte & kUtf8MultiByteMask) == kUtf8MultiByteCharStart;
}
#endif


static bool IsUtf8MultiCharacterFollower(byte later_byte) {
  return (later_byte & kUtf8MultiByteMask) == kUtf8MultiByteCharFollower;
}


// Move the cursor back to point at the preceding UTF-8 character start
// in the buffer.
263
static inline void Utf8CharacterBack(const byte* buffer, size_t* cursor) {
264 265
  byte character = buffer[--*cursor];
  if (character > unibrow::Utf8::kMaxOneByteChar) {
266
    DCHECK(IsUtf8MultiCharacterFollower(character));
267 268 269 270
    // Last byte of a multi-byte character encoding. Step backwards until
    // pointing to the first byte of the encoding, recognized by having the
    // top two bits set.
    while (IsUtf8MultiCharacterFollower(buffer[--*cursor])) { }
271
    DCHECK(IsUtf8MultiCharacterStart(buffer[*cursor]));
272 273 274 275 276 277
  }
}


// Move the cursor forward to point at the next following UTF-8 character start
// in the buffer.
278
static inline void Utf8CharacterForward(const byte* buffer, size_t* cursor) {
279 280 281 282 283 284 285 286
  byte character = buffer[(*cursor)++];
  if (character > unibrow::Utf8::kMaxOneByteChar) {
    // First character of a multi-byte character encoding.
    // The number of most-significant one-bits determines the length of the
    // encoding:
    //  110..... - (0xCx, 0xDx) one additional byte (minimum).
    //  1110.... - (0xEx) two additional bytes.
    //  11110... - (0xFx) three additional bytes (maximum).
287
    DCHECK(IsUtf8MultiCharacterStart(character));
288 289 290 291 292
    // Additional bytes is:
    // 1 if value in range 0xC0 .. 0xDF.
    // 2 if value in range 0xE0 .. 0xEF.
    // 3 if value in range 0xF0 .. 0xF7.
    // Encode that in a single value.
293
    size_t additional_bytes =
294 295
        ((0x3211u) >> (((character - 0xC0) >> 2) & 0xC)) & 0x03;
    *cursor += additional_bytes;
296
    DCHECK(!IsUtf8MultiCharacterFollower(buffer[1 + additional_bytes]));
297 298 299 300
  }
}


301 302 303 304
// This can't set a raw position between two surrogate pairs, since there
// is no position in the UTF8 stream that corresponds to that.  This assumes
// that the surrogate pair is correctly coded as a 4 byte UTF-8 sequence.  If
// it is illegally coded as two 3 byte sequences then there is no problem here.
305
void Utf8ToUtf16CharacterStream::SetRawPosition(size_t target_position) {
306 307 308
  if (raw_character_position_ > target_position) {
    // Spool backwards in utf8 buffer.
    do {
309
      size_t old_pos = raw_data_pos_;
310 311
      Utf8CharacterBack(raw_data_, &raw_data_pos_);
      raw_character_position_--;
312
      DCHECK(old_pos - raw_data_pos_ <= 4);
313 314
      // Step back over both code units for surrogate pairs.
      if (old_pos - raw_data_pos_ == 4) raw_character_position_--;
315
    } while (raw_character_position_ > target_position);
316
    // No surrogate pair splitting.
317
    DCHECK(raw_character_position_ == target_position);
318 319 320 321 322
    return;
  }
  // Spool forwards in the utf8 buffer.
  while (raw_character_position_ < target_position) {
    if (raw_data_pos_ == raw_data_length_) return;
323
    size_t old_pos = raw_data_pos_;
324 325
    Utf8CharacterForward(raw_data_, &raw_data_pos_);
    raw_character_position_++;
326
    DCHECK(raw_data_pos_ - old_pos <= 4);
327
    if (raw_data_pos_ - old_pos == 4) raw_character_position_++;
328
  }
329
  // No surrogate pair splitting.
330
  DCHECK(raw_character_position_ == target_position);
331 332 333
}


334
size_t ExternalStreamingStream::FillBuffer(size_t position) {
335 336
  // Ignore "position" which is the position in the decoded data. Instead,
  // ExternalStreamingStream keeps track of the position in the raw data.
337
  size_t data_in_buffer = 0;
338 339 340 341 342 343 344
  // Note that the UTF-8 decoder might not be able to fill the buffer
  // completely; it will typically leave the last character empty (see
  // Utf8ToUtf16CharacterStream::CopyChars).
  while (data_in_buffer < kBufferSize - 1) {
    if (current_data_ == NULL) {
      // GetSomeData will wait until the embedder has enough data. Here's an
      // interface between the API which uses size_t (which is the correct type
345 346
      // here) and the internal parts which use size_t.
      current_data_length_ = source_stream_->GetMoreData(&current_data_);
347 348 349 350 351 352 353 354 355 356 357 358
      current_data_offset_ = 0;
      bool data_ends = current_data_length_ == 0;

      // A caveat: a data chunk might end with bytes from an incomplete UTF-8
      // character (the rest of the bytes will be in the next chunk).
      if (encoding_ == ScriptCompiler::StreamedSource::UTF8) {
        HandleUtf8SplitCharacters(&data_in_buffer);
        if (!data_ends && current_data_offset_ == current_data_length_) {
          // The data stream didn't end, but we used all the data in the
          // chunk. This will only happen when the chunk was really small. We
          // don't handle the case where a UTF-8 character is split over several
          // chunks; in that case V8 won't crash, but it will be a parse error.
359
          FlushCurrent();
360 361 362 363 364 365 366 367 368 369 370 371
          continue;  // Request a new chunk.
        }
      }

      // Did the data stream end?
      if (data_ends) {
        DCHECK(utf8_split_char_buffer_length_ == 0);
        return data_in_buffer;
      }
    }

    // Fill the buffer from current_data_.
372 373
    size_t new_offset = 0;
    size_t new_chars_in_buffer =
374 375 376 377 378 379 380 381 382
        CopyCharsHelper(buffer_ + data_in_buffer, kBufferSize - data_in_buffer,
                        current_data_ + current_data_offset_, &new_offset,
                        current_data_length_ - current_data_offset_, encoding_);
    data_in_buffer += new_chars_in_buffer;
    current_data_offset_ += new_offset;
    DCHECK(data_in_buffer <= kBufferSize);

    // Did we use all the data in the data chunk?
    if (current_data_offset_ == current_data_length_) {
383
      FlushCurrent();
384 385 386 387 388
    }
  }
  return data_in_buffer;
}

389 390 391 392 393 394 395 396

bool ExternalStreamingStream::SetBookmark() {
  // Bookmarking for this stream is a bit more complex than expected, since
  // the stream state is distributed over several places:
  // - pos_ (inherited from Utf16CharacterStream)
  // - buffer_cursor_ and buffer_end_ (also from Utf16CharacterStream)
  // - buffer_ (from BufferedUtf16CharacterStream)
  // - current_data_ (+ .._offset_ and .._length) (this class)
vogelheim's avatar
vogelheim committed
397
  // - utf8_split_char_buffer_* (a partial utf8 symbol at the block boundary)
398 399 400 401 402 403 404 405 406
  //
  // The underlying source_stream_ instance likely could re-construct this
  // local data for us, but with the given interfaces we have no way of
  // accomplishing this. Thus, we'll have to save all data locally.
  //
  // What gets saved where:
  // - pos_  =>  bookmark_
  // - buffer_[buffer_cursor_ .. buffer_end_]  =>  bookmark_buffer_
  // - current_data_[.._offset_ .. .._length_]  =>  bookmark_data_
vogelheim's avatar
vogelheim committed
407
  // - utf8_split_char_buffer_* => bookmark_utf8_split...
408 409 410 411 412 413 414 415 416 417 418 419 420 421

  bookmark_ = pos_;

  size_t buffer_length = buffer_end_ - buffer_cursor_;
  bookmark_buffer_.Dispose();
  bookmark_buffer_ = Vector<uint16_t>::New(static_cast<int>(buffer_length));
  CopyCharsUnsigned(bookmark_buffer_.start(), buffer_cursor_, buffer_length);

  size_t data_length = current_data_length_ - current_data_offset_;
  bookmark_data_.Dispose();
  bookmark_data_ = Vector<uint8_t>::New(static_cast<int>(data_length));
  CopyBytes(bookmark_data_.start(), current_data_ + current_data_offset_,
            data_length);

vogelheim's avatar
vogelheim committed
422 423 424 425 426
  bookmark_utf8_split_char_buffer_length_ = utf8_split_char_buffer_length_;
  for (size_t i = 0; i < utf8_split_char_buffer_length_; i++) {
    bookmark_utf8_split_char_buffer_[i] = utf8_split_char_buffer_[i];
  }

427 428 429 430 431 432 433 434 435 436
  return source_stream_->SetBookmark();
}


void ExternalStreamingStream::ResetToBookmark() {
  source_stream_->ResetToBookmark();
  FlushCurrent();

  pos_ = bookmark_;

437 438 439
  // bookmark_data_* => current_data_*
  // (current_data_ assumes ownership of its memory.)
  uint8_t* data = new uint8_t[bookmark_data_.length()];
440 441
  current_data_offset_ = 0;
  current_data_length_ = bookmark_data_.length();
442 443 444
  CopyCharsUnsigned(data, bookmark_data_.begin(), bookmark_data_.length());
  delete[] current_data_;
  current_data_ = data;
445 446 447 448 449 450

  // bookmark_buffer_ needs to be copied to buffer_.
  CopyCharsUnsigned(buffer_, bookmark_buffer_.begin(),
                    bookmark_buffer_.length());
  buffer_cursor_ = buffer_;
  buffer_end_ = buffer_ + bookmark_buffer_.length();
vogelheim's avatar
vogelheim committed
451 452 453 454 455 456

  // utf8 split char buffer
  utf8_split_char_buffer_length_ = bookmark_utf8_split_char_buffer_length_;
  for (size_t i = 0; i < bookmark_utf8_split_char_buffer_length_; i++) {
    utf8_split_char_buffer_[i] = bookmark_utf8_split_char_buffer_[i];
  }
457 458 459 460 461 462 463 464 465 466 467
}


void ExternalStreamingStream::FlushCurrent() {
  delete[] current_data_;
  current_data_ = NULL;
  current_data_length_ = 0;
  current_data_offset_ = 0;
}


468
void ExternalStreamingStream::HandleUtf8SplitCharacters(
469
    size_t* data_in_buffer) {
470 471 472 473 474 475 476
  // Note the following property of UTF-8 which makes this function possible:
  // Given any byte, we can always read its local environment (in both
  // directions) to find out the (possibly multi-byte) character it belongs
  // to. Single byte characters are of the form 0b0XXXXXXX. The first byte of a
  // multi-byte character is of the form 0b110XXXXX, 0b1110XXXX or
  // 0b11110XXX. The continuation bytes are of the form 0b10XXXXXX.

477 478 479 480
  // First check if we have leftover data from the last chunk.
  unibrow::uchar c;
  if (utf8_split_char_buffer_length_ > 0) {
    // Move the bytes which are part of the split character (which started in
481 482
    // the previous chunk) into utf8_split_char_buffer_. Note that the
    // continuation bytes are of the form 0b10XXXXXX, thus c >> 6 == 2.
483 484
    while (current_data_offset_ < current_data_length_ &&
           utf8_split_char_buffer_length_ < 4 &&
485
           (c = current_data_[current_data_offset_]) >> 6 == 2) {
486 487 488 489 490 491
      utf8_split_char_buffer_[utf8_split_char_buffer_length_] = c;
      ++utf8_split_char_buffer_length_;
      ++current_data_offset_;
    }

    // Convert the data in utf8_split_char_buffer_.
492 493
    size_t new_offset = 0;
    size_t new_chars_in_buffer =
494 495 496 497 498 499 500 501 502 503 504 505 506
        CopyCharsHelper(buffer_ + *data_in_buffer,
                        kBufferSize - *data_in_buffer, utf8_split_char_buffer_,
                        &new_offset, utf8_split_char_buffer_length_, encoding_);
    *data_in_buffer += new_chars_in_buffer;
    // Make sure we used all the data.
    DCHECK(new_offset == utf8_split_char_buffer_length_);
    DCHECK(*data_in_buffer <= kBufferSize);

    utf8_split_char_buffer_length_ = 0;
  }

  // Move bytes which are part of an incomplete character from the end of the
  // current chunk to utf8_split_char_buffer_. They will be converted when the
507 508 509
  // next data chunk arrives. Note that all valid UTF-8 characters are at most 4
  // bytes long, but if the data is invalid, we can have character values bigger
  // than unibrow::Utf8::kMaxOneByteChar for more than 4 consecutive bytes.
510 511
  while (current_data_length_ > current_data_offset_ &&
         (c = current_data_[current_data_length_ - 1]) >
512 513
             unibrow::Utf8::kMaxOneByteChar &&
         utf8_split_char_buffer_length_ < 4) {
514 515
    --current_data_length_;
    ++utf8_split_char_buffer_length_;
516 517 518 519 520 521
    if (c >= (3 << 6)) {
      // 3 << 6 = 0b11000000; this is the first byte of the multi-byte
      // character. No need to copy the previous characters into the conversion
      // buffer (even if they're multi-byte).
      break;
    }
522
  }
523
  CHECK(utf8_split_char_buffer_length_ <= 4);
524
  for (size_t i = 0; i < utf8_split_char_buffer_length_; ++i) {
525 526 527 528 529
    utf8_split_char_buffer_[i] = current_data_[current_data_length_ + i];
  }
}


530
// ----------------------------------------------------------------------------
531
// ExternalTwoByteStringUtf16CharacterStream
532

533 534
ExternalTwoByteStringUtf16CharacterStream::
    ~ExternalTwoByteStringUtf16CharacterStream() { }
535 536


537 538 539
ExternalTwoByteStringUtf16CharacterStream::
    ExternalTwoByteStringUtf16CharacterStream(
        Handle<ExternalTwoByteString> data, int start_position,
540
        int end_position)
541
    : Utf16CharacterStream(),
542
      source_(data),
543 544
      raw_data_(data->GetTwoByteData(start_position)),
      bookmark_(kNoBookmark) {
545 546 547 548 549
  buffer_cursor_ = raw_data_,
  buffer_end_ = raw_data_ + (end_position - start_position);
  pos_ = start_position;
}

550 551 552 553 554 555 556 557 558 559 560 561

bool ExternalTwoByteStringUtf16CharacterStream::SetBookmark() {
  bookmark_ = pos_;
  return true;
}


void ExternalTwoByteStringUtf16CharacterStream::ResetToBookmark() {
  DCHECK(bookmark_ != kNoBookmark);
  pos_ = bookmark_;
  buffer_cursor_ = raw_data_ + bookmark_;
}
562 563
}  // namespace internal
}  // namespace v8