Rework scanner-character-streams.

src/parsing/scanner-character-streams.cc

 // Copyright 2011 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.
 
 #include "src/parsing/scanner-character-streams.h"
 
 #include "include/v8.h"
 #include "src/globals.h"
 #include "src/handles.h"
 #include "src/objects-inl.h"
+#include "src/parsing/scanner.h"
 #include "src/unicode-inl.h"
 
 namespace v8 {
 namespace internal {
 
-namespace {
-
-size_t CopyUtf8CharsToUtf16Chars(uint16_t* dest, size_t length, const byte* src,
-                                 size_t* src_pos, size_t src_length) {
-  static const unibrow::uchar kMaxUtf16Character =
-      unibrow::Utf16::kMaxNonSurrogateCharCode;
-  size_t i = 0;
-  // 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;
-}
-
-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) {
-  // 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;
-
-  if (encoding == ScriptCompiler::StreamedSource::UTF8) {
-    return CopyUtf8CharsToUtf16Chars(dest, length, src, src_pos, src_length);
-  }
-
-  size_t to_fill = length;
-  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
-
-
 // ----------------------------------------------------------------------------
 // BufferedUtf16CharacterStreams
+//
+// A buffered character stream based on a random access character
+// source (ReadBlock can be called with pos() pointing to any position,
+// even positions before the current).
+class BufferedUtf16CharacterStream : public Utf16CharacterStream {
+ public:
+  BufferedUtf16CharacterStream();
+
+ protected:
+  static const size_t kBufferSize = 512;
+
+  bool ReadBlock() override;
+
+  // FillBuffer should read up to kBufferSize characters at position and store
+  // them into buffer_[0..]. It returns the number of characters stored.
+  virtual size_t FillBuffer(size_t position) = 0;
+
+  // Fixed sized buffer that this class reads from.
+  // The base class' buffer_start_ should always point to buffer_.
+  uc16 buffer_[kBufferSize];
+};
 
 BufferedUtf16CharacterStream::BufferedUtf16CharacterStream()
-    : Utf16CharacterStream(),
-      pushback_limit_(NULL) {
-  // Initialize buffer as being empty. First read will fill the buffer.
+    : Utf16CharacterStream(buffer_, buffer_, buffer_, 0) {}
+
+bool BufferedUtf16CharacterStream::ReadBlock() {
+  DCHECK_EQ(buffer_start_, buffer_);
+
+  size_t position = pos();
+  buffer_pos_ = position;
   buffer_cursor_ = buffer_;
-  buffer_end_ = buffer_;
-}
-
-
-BufferedUtf16CharacterStream::~BufferedUtf16CharacterStream() { }
-
-void BufferedUtf16CharacterStream::PushBack(uc32 character) {
-  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));
-}
-
-
-void BufferedUtf16CharacterStream::SlowPushBack(uc16 character) {
-  // 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.
-  DCHECK(buffer_cursor_ > buffer_);
-  DCHECK(pos_ > 0);
-  buffer_[--buffer_cursor_ - buffer_] = character;
-  if (buffer_cursor_ == buffer_) {
-    pushback_limit_ = NULL;
-  } else if (buffer_cursor_ < pushback_limit_) {
-    pushback_limit_ = buffer_cursor_;
-  }
-  pos_--;
-}
-
-
-bool BufferedUtf16CharacterStream::ReadBlock() {
-  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.
-  }
-  size_t length = FillBuffer(pos_);
-  buffer_end_ = buffer_ + length;
-  return length > 0;
-}
-
-
-size_t BufferedUtf16CharacterStream::SlowSeekForward(size_t delta) {
-  // 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);
-}
-
-
-// ----------------------------------------------------------------------------
-// GenericStringUtf16CharacterStream
-
+  buffer_end_ = buffer_ + FillBuffer(position);
+  DCHECK_EQ(pos(), position);
+  DCHECK_LE(buffer_end_, buffer_start_ + kBufferSize);
+  return buffer_cursor_ < buffer_end_;
+}
+
+// ----------------------------------------------------------------------------
+// GenericStringUtf16CharacterStream.
+//
+// A stream w/ a data source being a (flattened) Handle<String>.
+
+class GenericStringUtf16CharacterStream : public BufferedUtf16CharacterStream {
+ public:
+  GenericStringUtf16CharacterStream(Handle<String> data, size_t start_position,
+                                    size_t end_position);
+
+ protected:
+  size_t FillBuffer(size_t position) override;
+
+  Handle<String> string_;
+  size_t length_;
+};
 
 GenericStringUtf16CharacterStream::GenericStringUtf16CharacterStream(
     Handle<String> data, size_t start_position, size_t end_position)
-    : string_(data), length_(end_position), bookmark_(kNoBookmark) {
-  DCHECK(end_position >= start_position);
-  pos_ = start_position;
-}
-
-
-GenericStringUtf16CharacterStream::~GenericStringUtf16CharacterStream() { }
-
-
-bool GenericStringUtf16CharacterStream::SetBookmark() {
-  bookmark_ = pos_;
-  return true;
-}
-
-
-void GenericStringUtf16CharacterStream::ResetToBookmark() {
-  DCHECK(bookmark_ != kNoBookmark);
-  pos_ = bookmark_;
-  buffer_cursor_ = buffer_;
-  buffer_end_ = buffer_ + FillBuffer(pos_);
-}
-
-
-size_t GenericStringUtf16CharacterStream::BufferSeekForward(size_t delta) {
-  size_t old_pos = pos_;
-  pos_ = Min(pos_ + delta, length_);
-  ReadBlock();
-  return pos_ - old_pos;
-}
-
+    : string_(data), length_(end_position) {
+  DCHECK_GE(end_position, start_position);
+  DCHECK_GE(static_cast<size_t>(string_->length()),
+            end_position - start_position);
+  buffer_pos_ = start_position;
+}
 
 size_t GenericStringUtf16CharacterStream::FillBuffer(size_t from_pos) {
   if (from_pos >= length_) return 0;
-  size_t length = kBufferSize;
-  if (from_pos + length > length_) {
-    length = length_ - from_pos;
-  }
+
+  size_t length = i::Min(kBufferSize, length_ - from_pos);
   String::WriteToFlat<uc16>(*string_, buffer_, static_cast<int>(from_pos),
                             static_cast<int>(from_pos + length));
   return length;
 }
 
-
-// ----------------------------------------------------------------------------
-// ExternalStreamingStream
-
-size_t ExternalStreamingStream::FillBuffer(size_t position) {
-  // Ignore "position" which is the position in the decoded data. Instead,
-  // ExternalStreamingStream keeps track of the position in the raw data.
-  size_t data_in_buffer = 0;
-  // 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
-      // here) and the internal parts which use size_t.
-      current_data_length_ = source_stream_->GetMoreData(&current_data_);
-      current_data_offset_ = 0;
-      bool data_ends = current_data_length_ == 0;
-      bookmark_data_is_from_current_data_ = false;
-
-      // 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.
-          FlushCurrent();
-          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_.
-    size_t new_offset = 0;
-    size_t new_chars_in_buffer =
-        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_) {
-      FlushCurrent();
-    }
-  }
-  return data_in_buffer;
-}
-
-
-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)
-  // - utf8_split_char_buffer_* (a partial utf8 symbol at the block boundary)
-  //
-  // 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_
-  // - utf8_split_char_buffer_* => bookmark_utf8_split...
-  //
-  // To make sure we don't unnecessarily copy data, we also maintain
-  // whether bookmark_data_ contains a copy of the current current_data_
-  // block. This is done with:
-  // - bookmark_data_is_from_current_data_
-  // - bookmark_data_offset_: offset into bookmark_data_
-  //
-  // Note that bookmark_data_is_from_current_data_ must be maintained
-  // whenever current_data_ is updated.
-
-  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_;
-  size_t bookmark_data_length = static_cast<size_t>(bookmark_data_.length());
-  if (bookmark_data_is_from_current_data_ &&
-      data_length < bookmark_data_length) {
-    // Fast case: bookmark_data_ was previously copied from the current
-    //            data block, and we have enough data for this bookmark.
-    bookmark_data_offset_ = bookmark_data_length - data_length;
-  } else {
-    // Slow case: We need to copy current_data_.
-    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);
-    bookmark_data_is_from_current_data_ = true;
-    bookmark_data_offset_ = 0;
-  }
-
-  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];
-  }
-
-  return source_stream_->SetBookmark();
-}
-
-
-void ExternalStreamingStream::ResetToBookmark() {
-  source_stream_->ResetToBookmark();
-  FlushCurrent();
-
-  pos_ = bookmark_;
-
-  // bookmark_data_* => current_data_*
-  // (current_data_ assumes ownership of its memory.)
-  current_data_offset_ = 0;
-  current_data_length_ = bookmark_data_.length() - bookmark_data_offset_;
-  uint8_t* data = new uint8_t[current_data_length_];
-  CopyCharsUnsigned(data, bookmark_data_.begin() + bookmark_data_offset_,
-                    current_data_length_);
-  delete[] current_data_;
-  current_data_ = data;
-  bookmark_data_is_from_current_data_ = true;
-
-  // 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();
-
-  // 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];
-  }
-}
-
-
-void ExternalStreamingStream::FlushCurrent() {
-  delete[] current_data_;
-  current_data_ = NULL;
-  current_data_length_ = 0;
-  current_data_offset_ = 0;
-  bookmark_data_is_from_current_data_ = false;
-}
-
-
-void ExternalStreamingStream::HandleUtf8SplitCharacters(
-    size_t* data_in_buffer) {
-  // 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.
-
-  // 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
-    // the previous chunk) into utf8_split_char_buffer_. Note that the
-    // continuation bytes are of the form 0b10XXXXXX, thus c >> 6 == 2.
-    while (current_data_offset_ < current_data_length_ &&
-           utf8_split_char_buffer_length_ < 4 &&
-           (c = current_data_[current_data_offset_]) >> 6 == 2) {
-      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_.
-    size_t new_offset = 0;
-    size_t new_chars_in_buffer =
-        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
-  // 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.
-  while (current_data_length_ > current_data_offset_ &&
-         (c = current_data_[current_data_length_ - 1]) >
-             unibrow::Utf8::kMaxOneByteChar &&
-         utf8_split_char_buffer_length_ < 4) {
-    --current_data_length_;
-    ++utf8_split_char_buffer_length_;
-    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;
-    }
-  }
-  CHECK(utf8_split_char_buffer_length_ <= 4);
-  for (size_t i = 0; i < utf8_split_char_buffer_length_; ++i) {
-    utf8_split_char_buffer_[i] = current_data_[current_data_length_ + i];
-  }
-}
-
-
-// ----------------------------------------------------------------------------
-// ExternalTwoByteStringUtf16CharacterStream
-
-ExternalTwoByteStringUtf16CharacterStream::
-    ~ExternalTwoByteStringUtf16CharacterStream() { }
+// ----------------------------------------------------------------------------
+// ExternalTwoByteStringUtf16CharacterStream.
+//
+// A stream whose data source is a Handle<ExternalTwoByteString>. It avoids
+// all data copying.
+
+class ExternalTwoByteStringUtf16CharacterStream : public Utf16CharacterStream {
+ public:
+  ExternalTwoByteStringUtf16CharacterStream(Handle<ExternalTwoByteString> data,
+                                            size_t start_position,
+                                            size_t end_position);
+
+ private:
+  bool ReadBlock() override;
+
+  const uc16* raw_data_;  // Pointer to the actual array of characters.
+  size_t start_pos_;
+  size_t end_pos_;
+};
 
 ExternalTwoByteStringUtf16CharacterStream::
     ExternalTwoByteStringUtf16CharacterStream(
-        Handle<ExternalTwoByteString> data, int start_position,
-        int end_position)
-    : raw_data_(data->GetTwoByteData(start_position)), bookmark_(kNoBookmark) {
-  buffer_cursor_ = raw_data_,
-  buffer_end_ = raw_data_ + (end_position - start_position);
-  pos_ = start_position;
-}
-
-
-bool ExternalTwoByteStringUtf16CharacterStream::SetBookmark() {
-  bookmark_ = pos_;
-  return true;
-}
-
-
-void ExternalTwoByteStringUtf16CharacterStream::ResetToBookmark() {
-  DCHECK(bookmark_ != kNoBookmark);
-  pos_ = bookmark_;
-  buffer_cursor_ = raw_data_ + bookmark_;
+        Handle<ExternalTwoByteString> data, size_t start_position,
+        size_t end_position)
+    : raw_data_(data->GetTwoByteData(static_cast<int>(start_position))),
+      start_pos_(start_position),
+      end_pos_(end_position) {
+  buffer_start_ = raw_data_;
+  buffer_cursor_ = raw_data_;
+  buffer_end_ = raw_data_ + (end_pos_ - start_pos_);
+  buffer_pos_ = start_pos_;
+}
+
+bool ExternalTwoByteStringUtf16CharacterStream::ReadBlock() {
+  size_t position = pos();
+  bool have_data = start_pos_ <= position && position < end_pos_;
+  if (have_data) {
+    buffer_pos_ = start_pos_;
+    buffer_cursor_ = raw_data_ + (position - start_pos_),
+    buffer_end_ = raw_data_ + (end_pos_ - start_pos_);
+  } else {
+    buffer_pos_ = position;
+    buffer_cursor_ = raw_data_;
+    buffer_end_ = raw_data_;
+  }
+  return have_data;
 }
 
 // ----------------------------------------------------------------------------
 // ExternalOneByteStringUtf16CharacterStream
-
-ExternalOneByteStringUtf16CharacterStream::
-    ~ExternalOneByteStringUtf16CharacterStream() {}
+//
+// A stream whose data source is a Handle<ExternalOneByteString>.
+
+class ExternalOneByteStringUtf16CharacterStream
+    : public BufferedUtf16CharacterStream {
+ public:
+  ExternalOneByteStringUtf16CharacterStream(Handle<ExternalOneByteString> data,
+                                            size_t start_position,
+                                            size_t end_position);
+
+  // For testing:
+  ExternalOneByteStringUtf16CharacterStream(const char* data, size_t length);
+
+ protected:
+  size_t FillBuffer(size_t position) override;
+
+  const uint8_t* raw_data_;  // Pointer to the actual array of characters.
+  size_t length_;
+};
 
 ExternalOneByteStringUtf16CharacterStream::
     ExternalOneByteStringUtf16CharacterStream(
-        Handle<ExternalOneByteString> data, int start_position,
-        int end_position)
-    : raw_data_(data->GetChars()),
-      length_(end_position),
-      bookmark_(kNoBookmark) {
+        Handle<ExternalOneByteString> data, size_t start_position,
+        size_t end_position)
+    : raw_data_(data->GetChars()), length_(end_position) {
   DCHECK(end_position >= start_position);
-  pos_ = start_position;
+  buffer_pos_ = start_position;
 }
 
 ExternalOneByteStringUtf16CharacterStream::
     ExternalOneByteStringUtf16CharacterStream(const char* data, size_t length)
-    : raw_data_(reinterpret_cast<const uint8_t*>(data)),
-      length_(length),
-      bookmark_(kNoBookmark) {}
-
-ExternalOneByteStringUtf16CharacterStream::
-    ExternalOneByteStringUtf16CharacterStream(const char* data)
-    : ExternalOneByteStringUtf16CharacterStream(data, strlen(data)) {}
-
-bool ExternalOneByteStringUtf16CharacterStream::SetBookmark() {
-  bookmark_ = pos_;
-  return true;
-}
-
-void ExternalOneByteStringUtf16CharacterStream::ResetToBookmark() {
-  DCHECK(bookmark_ != kNoBookmark);
-  pos_ = bookmark_;
-  buffer_cursor_ = buffer_;
-  buffer_end_ = buffer_ + FillBuffer(pos_);
-}
-
-size_t ExternalOneByteStringUtf16CharacterStream::BufferSeekForward(
-    size_t delta) {
-  size_t old_pos = pos_;
-  pos_ = Min(pos_ + delta, length_);
-  ReadBlock();
-  return pos_ - old_pos;
-}
+    : raw_data_(reinterpret_cast<const uint8_t*>(data)), length_(length) {}
 
 size_t ExternalOneByteStringUtf16CharacterStream::FillBuffer(size_t from_pos) {
   if (from_pos >= length_) return 0;
+
   size_t length = Min(kBufferSize, length_ - from_pos);
-  for (size_t i = 0; i < length; ++i) {
-    buffer_[i] = static_cast<uc16>(raw_data_[from_pos + i]);
-  }
+  i::CopyCharsUnsigned(buffer_, raw_data_ + from_pos, length);
   return length;
 }
 
+// ----------------------------------------------------------------------------
+// Utf8ExternalStreamingStream - chunked streaming of Utf-8 data.
+//
+// This implementation is fairly complex, since data arrives in chunks which
+// may 'cut' arbitrarily into utf-8 characters. Also, seeking to a given
+// character position is tricky because the byte position cannot be dericed
+// from the character position.
+
+class Utf8ExternalStreamingStream : public BufferedUtf16CharacterStream {
+ public:
+  Utf8ExternalStreamingStream(
+      ScriptCompiler::ExternalSourceStream* source_stream)
+      : current_({0, {0, 0, unibrow::Utf8::Utf8IncrementalBuffer(0)}}),
+        source_stream_(source_stream) {}
+  ~Utf8ExternalStreamingStream() override {
+    for (size_t i = 0; i < chunks_.size(); i++) delete[] chunks_[i].chunk;
+  }
+
+ protected:
+  size_t FillBuffer(size_t position) override;
+
+ private:
+  // A position within the data stream. It stores:
+  // - The 'physical' position (# of bytes in the stream),
+  // - the 'logical' position (# of ucs-2 characters, also within the stream),
+  // - a possibly incomplete utf-8 char at the current 'physical' position.
+  struct ChunkPosition {

[marja, 2016/09/15 08:25:16]

Now this doesn't contain the chunk number any more, so "position" would be a
better name.

[vogelheim, 2016/09/15 11:29:25]

Hmm.. I called it StreamPosition.

+    size_t bytes;
+    size_t chars;
+    unibrow::Utf8::Utf8IncrementalBuffer incomplete_char;
+  };
+
+  // Position contains a ChunkPosition and the index of the chunk the position
+  // points into. (The chunk_no could be derived from pos, but that'd be
+  // an expensive search through all chunks.)
+  struct Position {

[marja, 2016/09/15 08:25:16]

And this could be called PositionAndChunk or sth. Because the above struct *is*
Position and this is just adding information to it.

[vogelheim, 2016/09/15 11:29:25]

I'd prefer to keep this one as Position, since
- 1, it's the shorter name and it gets used a lot more, and
- 2, I do think of this as the 'true' position.

If this were an STL-like design, the ..::iterator would be this Position. The
other "position" is really more a helper so I can conveniently define Chunk +
Position, and to highlight where they are similar.

+    size_t chunk_no;
+    ChunkPosition pos;
+  };
+
+  // A chunk in the list of chunks, containing:
+  // - The chunk data (data pointer and length), and
+  // - the position at the first byte of the chunk.
+  struct Chunk {
+    const uint8_t* chunk;
+    size_t length;
+    ChunkPosition start;
+  };
+
+  // Within the current chunk, skip forward from current_ towards position.
+  void SkipToPosition(size_t position);
+  // Within the current chunk, fill the buffer_ (while it has capacity).
+  void FillBufferFromCurrentChunk();
+  // Fetch a new chunk (assuming current_ is at the end of the current data).
+  bool FetchChunk();
+  // Search through the chunks and set current_ to point to the given position.
+  // (This call is potentially expensive.)
+  void SearchPosition(size_t position);
+
+  std::vector<Chunk> chunks_;
+  Position current_;
+  ScriptCompiler::ExternalSourceStream* source_stream_;

[marja, 2016/09/15 08:25:16]

I like this new version, now the structs and their members are clear to me after
first reading through it!

[vogelheim, 2016/09/15 11:29:25]

Acknowledged.

+};
+
+void Utf8ExternalStreamingStream::SkipToPosition(size_t position) {
+  DCHECK_LE(current_.pos.chars, position);  // We can only skip forward.
+
+  // Already there? Then return immediately.
+  if (current_.pos.chars == position) return;
+
+  const Chunk& chunk = chunks_[current_.chunk_no];
+  DCHECK(current_.pos.bytes >= chunk.start.bytes);
+
+  unibrow::Utf8::Utf8IncrementalBuffer incomplete_char =
+      chunk.start.incomplete_char;
+  size_t it = current_.pos.bytes - chunk.start.bytes;
+  size_t chars = chunk.start.chars;
+  while (it < chunk.length && chars < position) {
+    unibrow::uchar t =
+        unibrow::Utf8::ValueOfIncremental(chunk.chunk[it], &incomplete_char);
+    if (t != unibrow::Utf8::kIncomplete) {
+      chars++;
+      if (t > unibrow::Utf16::kMaxNonSurrogateCharCode) chars++;
+    }
+    it++;
+  }
+
+  current_.pos.bytes += it;
+  current_.pos.chars = chars;
+  current_.pos.incomplete_char = incomplete_char;
+  current_.chunk_no += (it == chunk.length);
+}
+
+void Utf8ExternalStreamingStream::FillBufferFromCurrentChunk() {
+  DCHECK_LT(current_.chunk_no, chunks_.size());
+  DCHECK_EQ(buffer_start_, buffer_cursor_);
+  DCHECK_LT(buffer_end_ + 1, buffer_start_ + kBufferSize);
+
+  const Chunk& chunk = chunks_[current_.chunk_no];
+
+  // The buffer_ is writeable, but buffer_*_ members are const. So we get a

[marja, 2016/09/15 08:25:16]

Typo: writable

[vogelheim, 2016/09/15 11:29:26]

Done.

+  // non-const pointer into buffer that points to the same char as buffer_end_.

[marja, 2016/09/15 08:25:16]

Hmm, what, why? Do we need to write into it? No?

[vogelheim, 2016/09/15 11:29:25]

Yes, we need to write into the buffer. See lines #296 and #298-299. Also, it's
called FillBufferFromCurrentChunk, because we really do want to write into the
buffer.

+  uint16_t* cursor = buffer_ + (buffer_end_ - buffer_start_);
+  DCHECK_EQ(cursor, buffer_end_);
+
+  unibrow::Utf8::Utf8IncrementalBuffer incomplete_char =
+      current_.pos.incomplete_char;
+  size_t it;
+  for (it = current_.pos.bytes - chunk.start.bytes;
+       it < chunk.length && cursor + 1 < buffer_start_ + kBufferSize; it++) {
+    unibrow::uchar t =
+        unibrow::Utf8::ValueOfIncremental(chunk.chunk[it], &incomplete_char);
+    if (t == unibrow::Utf8::kIncomplete) continue;
+    if (t <= unibrow::Utf16::kMaxNonSurrogateCharCode) {
+      *(cursor++) = static_cast<uc16>(t);
+    } else {
+      *(cursor++) = unibrow::Utf16::LeadSurrogate(t);
+      *(cursor++) = unibrow::Utf16::TrailSurrogate(t);
+    }
+  }
+
+  current_.pos.bytes = chunk.start.bytes + it;
+  current_.pos.chars += (cursor - buffer_end_);
+  current_.pos.incomplete_char = incomplete_char;
+  current_.chunk_no += (it == chunk.length);
+
+  buffer_end_ = cursor;
+}
+
+bool Utf8ExternalStreamingStream::FetchChunk() {
+  DCHECK_EQ(current_.chunk_no, chunks_.size());
+  DCHECK(chunks_.empty() || chunks_.back().length != 0);
+
+  const uint8_t* chunk = nullptr;
+  size_t length = source_stream_->GetMoreData(&chunk);
+  chunks_.push_back({chunk, length, current_.pos});
+  return length > 0;
+}
+
+void Utf8ExternalStreamingStream::SearchPosition(size_t position) {
+  // If current_ already points to the right position, we're done.
+  //
+  // This is expected to be the common case, since we typically call
+  // FillBuffer right after the current buffer.
+  if (current_.pos.chars == position) return;
+
+  // No chunks. Then current_ must be at the start, which is the correct
+  // position for an empty chunks array anyhow.
+  if (chunks_.empty()) {
+    DCHECK_EQ(current_.pos.bytes, 0);
+    DCHECK_EQ(current_.pos.chars, 0);
+    return;

[marja, 2016/09/15 08:25:16]

Hmm? Why don't we need to get more data to find "position"?

[vogelheim, 2016/09/15 11:29:26]

Done.

Yeah... that's a left over from an older version, where I tried to write it so
there was only one location that would fetch new chunks. Changed.

+  }
+
+  // Search for the last chunk whose start position is less or equal to
+  // position.
+  size_t chunk_no = 0;
+  for (chunk_no = chunks_.size() - 1;
+       chunk_no > 0 && chunks_[chunk_no].start.chars > position; chunk_no--) {
+  }

[marja, 2016/09/15 08:25:16]

Style nit: I'd write this like:
size_t chunk_no = chunks_.size() - 1;
while (chunk_no > 0 && chunks_[chunk_no].start.chars > position) {
  --chunk_no;
}

[vogelheim, 2016/09/15 11:29:25]

Done.

+
+  // Did we find the terminating (zero-length) chunk? Then we're seeking
+  // behind the end of the data, and position does not exist.
+  // Set current_ to point to the terminating chunk.
+  if (chunks_[chunk_no].length == 0) {
+    current_ = {chunk_no, chunks_[chunk_no].start};
+    return;
+  }
+
+  // Did we find the non-last chunk? Then our position must be within chunk_no.
+  if (chunk_no + 1 < chunks_.size()) {
+    // Fancy-pants optimization for ASCII chunks within a utf-8 stream.
+    // (Many web sites declare utf-8 encoding, but use only (or almost only) the
+    //  ASCII subset for their JavaScript sources. We can exploit this, by
+    //  checking whether the # bytes in a chunk are equal to the # chars, and if
+    //  so avoid the expensive SkipToPosition.)
+    bool ascii_only_chunk =
+        (chunks_[chunk_no + 1].start.bytes - chunks_[chunk_no].start.bytes) ==
+        (chunks_[chunk_no + 1].start.chars - chunks_[chunk_no].start.chars);
+    if (ascii_only_chunk) {
+      size_t skip = position - chunks_[chunk_no].start.chars;
+      current_ = {chunk_no,
+                  {chunks_[chunk_no].start.bytes + skip,
+                   chunks_[chunk_no].start.chars + skip,
+                   unibrow::Utf8::Utf8IncrementalBuffer(0)}};

[marja, 2016/09/15 08:25:17]

This is great!

[vogelheim, 2016/09/15 11:29:25]

Acknowledged.

+    } else {
+      current_ = {chunk_no, chunks_[chunk_no].start};
+      SkipToPosition(position);
+    }
+
+    // Since position was within the chunk, SkipToPosition should have found
+    // something.
+    DCHECK_EQ(position, current_.pos.chars);
+    return;
+  }
+
+  // What's left: We're in the last, non-terminating chunk. Our position
+  // may be in the chunk, but it may also be in 'future' chunks, which we'll
+  // have to obtain.
+  DCHECK_EQ(chunk_no, chunks_.size() - 1);
+  current_ = {chunk_no, chunks_[chunk_no].start};
+  SkipToPosition(position);
+  while (current_.pos.chars < position && chunks_.back().length > 0) {
+    DCHECK_EQ(current_.chunk_no, chunks_.size());
+    if (FetchChunk()) {
+      SkipToPosition(position);

[marja, 2016/09/15 08:25:16]

One thing I still find surprising in this CL is that SkipToPosition is not
guaranteed to actually find the position, and it also doesn't return a bool, but
the caller is required to check whether it really skipped to the right position.
But I can somehow see why you did it like that... so idk.

An alternative would be:
bool position_found = SkipToPosition(position);
while (!position_found) {
  if (FetchChunk()) {
    position_found = SkipToPosition(position);
  } else {
    // out of data
    break;
  }
}

In this version, also the out-of-data condition (which confused me) is clearer.

[vogelheim, 2016/09/15 11:29:25]

Done, sort of.

+    }
+  }
+  // We'll return with a postion != the desired position only if we're out
+  // of data. In that case, we'll point to the terminating chunk.
+  DCHECK_IMPLIES(current_.pos.chars != position, chunks_.back().length == 0);
+  DCHECK_IMPLIES(current_.pos.chars != position, chunks_[chunk_no].length == 0);
+}
+
+size_t Utf8ExternalStreamingStream::FillBuffer(size_t position) {
+  buffer_cursor_ = buffer_;
+  buffer_end_ = buffer_;
+
+  SearchPosition(position);
+  bool out_of_data = current_.chunk_no != chunks_.size() &&
+                     chunks_[current_.chunk_no].length == 0;
+  if (out_of_data) return 0;
+
+  // Fill the buffer, until we have at least one char (or are out of data).
+  // (The embedder might give us 1-byte blocks within a utf-8 char, so we
+  //  can't guarantee progress with one chunk. Thus we iterate.)
+  while (!out_of_data && buffer_cursor_ == buffer_end_) {
+    // At end of current data, but there might be more? Then fetch it.
+    if (current_.chunk_no == chunks_.size()) {
+      out_of_data = !FetchChunk();
+    }
+    if (!out_of_data) FillBufferFromCurrentChunk();
+  }
+
+  DCHECK_EQ(current_.pos.chars - position, buffer_end_ - buffer_cursor_);
+  return buffer_end_ - buffer_cursor_;
+}
+
+// ----------------------------------------------------------------------------
+// Chunks - helper for One- + TwoByteExternalStreamingStream
+namespace {
+
+struct Chunk {
+  const uint8_t* chunk;

[marja, 2016/09/15 08:25:16]

I'd call it "data" instead of "chunk" (because the struct is already called
"Chunk").

[vogelheim, 2016/09/15 11:29:25]

Done.

+  size_t byte_length;
+  size_t byte_pos;
+};
+
+typedef std::vector<struct Chunk> Chunks;
+
+void DeleteChunks(Chunks& chunks) {
+  for (size_t i = 0; i < chunks.size(); i++) delete[] chunks[i].chunk;
+}
+
+// Return the chunk index for the chunk containing position.
+// If position is behind the end of the stream, the index of the last,
+// zero-length chunk is returned.
+size_t FindChunk(Chunks& chunks, ScriptCompiler::ExternalSourceStream* source_,
+                 size_t position) {
+  size_t end_pos =
+      chunks.empty() ? 0 : (chunks.back().byte_pos + chunks.back().byte_length);
+
+  // Get more data if needed. We usually won't enter the loop body.
+  bool out_of_data = !chunks.empty() && chunks.back().byte_length == 0;
+  while (!out_of_data && end_pos <= position + 1) {
+    const uint8_t* chunk = nullptr;
+    size_t len = source_->GetMoreData(&chunk);
+
+    chunks.push_back({chunk, len, end_pos});
+    end_pos += len;
+    out_of_data = (len == 0);
+  }
+
+  // Here, we should always have at least one chunk, and we either have the
+  // chunk we were looking for, or we're out of data. Also, out_of_data and
+  // end_pos are current (and designate whether we have exhausted the stream,
+  // and the length of data received so far, respectively).
+  DCHECK(!chunks.empty());
+  DCHECK_EQ(end_pos, chunks.back().byte_pos + chunks.back().byte_length);
+  DCHECK_EQ(out_of_data, chunks.back().byte_length == 0);
+  DCHECK(position < end_pos || out_of_data);
+
+  // Edge case: position is behind the end of stream: Return the last (length 0)
+  // chunk to indicate the end of the stream.
+  if (position >= end_pos) {
+    DCHECK(out_of_data);
+    return chunks.size() - 1;
+  }
+
+  // We almost always 'stream', meaning we want data from the last chunk, so
+  // let's look at chunks back-to-front.
+  size_t chunk_no = chunks.size() - 1;
+  while (chunks[chunk_no].byte_pos > position) {
+    DCHECK_NE(chunk_no, 0);
+    chunk_no--;
+  }
+  DCHECK_LE(chunks[chunk_no].byte_pos, position);
+  DCHECK_LT(position, chunks[chunk_no].byte_pos + chunks[chunk_no].byte_length);
+  return chunk_no;
+}
+
+}  // anonymous namespace
+
+// ----------------------------------------------------------------------------
+// OneByteExternalStreamingStream
+//
+// A stream of latin-1 encoded, chunked data.
+
+class OneByteExternalStreamingStream : public BufferedUtf16CharacterStream {
+ public:
+  explicit OneByteExternalStreamingStream(
+      ScriptCompiler::ExternalSourceStream* source)
+      : source_(source) {}
+  ~OneByteExternalStreamingStream() override { DeleteChunks(chunks_); }
+
+ protected:
+  size_t FillBuffer(size_t position) override;
+
+ private:
+  Chunks chunks_;
+  ScriptCompiler::ExternalSourceStream* source_;
+};
+
+size_t OneByteExternalStreamingStream::FillBuffer(size_t position) {
+  Chunk& chunk = chunks_[FindChunk(chunks_, source_, position)];

[marja, 2016/09/15 08:25:16]

Why not const Chunk& ?

[vogelheim, 2016/09/15 11:29:25]

Done.

+  if (chunk.byte_length == 0) return 0;
+
+  size_t start_pos = position - chunk.byte_pos;
+  size_t len = i::Min(kBufferSize, chunk.byte_length - start_pos);
+  i::CopyCharsUnsigned(buffer_, chunk.chunk + start_pos, len);
+  return len;
+}
+
+// ----------------------------------------------------------------------------
+// TwoByteExternalStreamingStream
+//
+// A stream of ucs-2 data, delivered in chunks. Chunks may be 'cut' into the
+// middle of characters (or even contain only one byte), which adds a bit
+// of complexity. This stream avoid all data copying, except for characters
+// that cross chunk boundaries.
+
+class TwoByteExternalStreamingStream : public Utf16CharacterStream {
+ public:
+  explicit TwoByteExternalStreamingStream(
+      ScriptCompiler::ExternalSourceStream* source);
+  ~TwoByteExternalStreamingStream() override;
+
+ protected:
+  bool ReadBlock() override;
+
+  Chunks chunks_;
+  ScriptCompiler::ExternalSourceStream* source_;
+  uc16 one_char_buffer_;
+};
+
+TwoByteExternalStreamingStream::TwoByteExternalStreamingStream(
+    ScriptCompiler::ExternalSourceStream* source)
+    : Utf16CharacterStream(&one_char_buffer_, &one_char_buffer_,
+                           &one_char_buffer_, 0),
+      source_(source),
+      one_char_buffer_(0) {}
+
+TwoByteExternalStreamingStream::~TwoByteExternalStreamingStream() {
+  DeleteChunks(chunks_);
+}
+
+bool TwoByteExternalStreamingStream::ReadBlock() {
+  size_t position = pos();
+
+  // We'll search for the 2nd byte of our character, to make sure we
+  // have enough data for at least one character.
+  size_t chunk_no = FindChunk(chunks_, source_, 2 * position + 1);
+
+  // Out of data? Return 0.
+  if (chunks_[chunk_no].byte_length == 0) {
+    buffer_cursor_ = buffer_start_;
+    buffer_end_ = buffer_start_;
+    return false;
+  }
+
+  Chunk& current = chunks_[chunk_no];
+
+  // Annoying edge case: Chunks may not be 2-byte aligned, meaning that a
+  // character may be split between the previous and the current chunk.
+  // If we find such a lonely byte at the beginning of the chunk, we'll use
+  // one_char_buffer_ to hold the full character.
+  bool lonely_byte = (chunks_[chunk_no].byte_pos == (2 * position + 1));
+  if (lonely_byte) {
+    DCHECK_NE(chunk_no, 0);
+    Chunk& previous_chunk = chunks_[chunk_no - 1];
+    uc16 character = previous_chunk.chunk[previous_chunk.byte_length - 1] |
+                     current.chunk[0] << 8;
+
+    one_char_buffer_ = character;
+    buffer_pos_ = position;
+    buffer_start_ = &one_char_buffer_;
+    buffer_cursor_ = &one_char_buffer_;
+    buffer_end_ = &one_char_buffer_ + 1;
+    return true;
+  }
+
+  // Common case: character is in current chunk.
+  DCHECK_LE(current.byte_pos, 2 * position);
+  DCHECK_LT(2 * position + 1, current.byte_pos + current.byte_length);
+
+  // Determine # of full ucs-2 chars in stream, and whether we started on an odd
+  // byte boundary.
+  bool odd_start = (current.byte_pos % 2) == 1;
+  size_t number_chars = (current.byte_length - odd_start) / 2;
+
+  // Point the buffer_*_ members into the current chunk and set buffer_cursor_
+  // to point to position. Be careful when converting the byte positions (in
+  // Chunk) to the ucs-2 character positions (in buffer_*_ members).
+  buffer_start_ = reinterpret_cast<const uint16_t*>(current.chunk + odd_start);
+  buffer_end_ = buffer_start_ + number_chars;
+  buffer_pos_ = (current.byte_pos + odd_start) / 2;
+  buffer_cursor_ = buffer_start_ + (position - buffer_pos_);
+  DCHECK_EQ(position, pos());
+  return true;
+}
+
+// ----------------------------------------------------------------------------
+// ScannerStream: Create stream instances.
+
+Utf16CharacterStream* ScannerStream::For(Handle<String> data) {
+  return ScannerStream::For(data, 0, data->length());
+}
+
+Utf16CharacterStream* ScannerStream::For(Handle<String> data, int start_pos,
+                                         int end_pos) {
+  DCHECK(start_pos >= 0);
+  DCHECK(end_pos <= data->length());
+  if (data->IsExternalOneByteString()) {
+    return new ExternalOneByteStringUtf16CharacterStream(
+        Handle<ExternalOneByteString>::cast(data), start_pos, end_pos);
+  } else if (data->IsExternalTwoByteString()) {
+    return new ExternalTwoByteStringUtf16CharacterStream(
+        Handle<ExternalTwoByteString>::cast(data), start_pos, end_pos);
+  } else {
+    // TODO(vogelheim): Maybe call data.Flatten() first?
+    return new GenericStringUtf16CharacterStream(data, start_pos, end_pos);
+  }
+}
+
+std::unique_ptr<Utf16CharacterStream> ScannerStream::ForTesting(
+    const char* data) {
+  return ScannerStream::ForTesting(data, strlen(data));
+}
+
+std::unique_ptr<Utf16CharacterStream> ScannerStream::ForTesting(
+    const char* data, size_t length) {
+  return std::unique_ptr<Utf16CharacterStream>(
+      new ExternalOneByteStringUtf16CharacterStream(data, length));
+}
+
+Utf16CharacterStream* ScannerStream::For(
+    ScriptCompiler::ExternalSourceStream* source_stream,
+    v8::ScriptCompiler::StreamedSource::Encoding encoding) {
+  switch (encoding) {
+    case v8::ScriptCompiler::StreamedSource::TWO_BYTE:
+      return new TwoByteExternalStreamingStream(source_stream);
+    case v8::ScriptCompiler::StreamedSource::ONE_BYTE:
+      return new OneByteExternalStreamingStream(source_stream);
+    case v8::ScriptCompiler::StreamedSource::UTF8:
+      return new Utf8ExternalStreamingStream(source_stream);
+  }
+  UNREACHABLE();
+  return nullptr;
+}
+
 }  // namespace internal
 }  // namespace v8