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"
+#include "src/utils.h"  // for Mem[Copy|Move].*
 
 namespace v8 {
 namespace internal {
 
-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();
+  ~BufferedUtf16CharacterStream() override;
 
-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;
+ protected:
+  static const size_t kBufferSize = 512;
+
+  bool ReadBlock() override;
+  virtual size_t FillBuffer(size_t position) = 0;
+
+  uc16 buffer_[kBufferSize];
+};
+
+BufferedUtf16CharacterStream::BufferedUtf16CharacterStream()
+    : Utf16CharacterStream(buffer_, buffer_, buffer_, 0) {}
+
+BufferedUtf16CharacterStream::~BufferedUtf16CharacterStream() {}
+
+bool BufferedUtf16CharacterStream::ReadBlock() {
+  DCHECK_EQ(buffer_start_, buffer_);  // Please nobody mess w/ buffer_start_.
+
+  size_t position = pos();
+  buffer_pos_ = position;
+  buffer_cursor_ = buffer_;
+  buffer_end_ = buffer_ + FillBuffer(position);
+  DCHECK_EQ(pos(), position);
+  DCHECK_LE(buffer_end_, buffer_start_ + kBufferSize);
+  return buffer_cursor_ < buffer_end_;
 }
 
-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;
+// ----------------------------------------------------------------------------
+// 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);
+  ~GenericStringUtf16CharacterStream() override;
 
-  if (encoding == ScriptCompiler::StreamedSource::UTF8) {
-    return CopyUtf8CharsToUtf16Chars(dest, length, src, src_pos, src_length);
-  }
+ protected:
+  size_t FillBuffer(size_t position) override;
 
-  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
-
-BufferedUtf16CharacterStream::BufferedUtf16CharacterStream()
-    : Utf16CharacterStream(),
-      pushback_limit_(NULL) {
-  // Initialize buffer as being empty. First read will fill the buffer.
-  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
-
+  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) {
+    : string_(data), length_(end_position) {
   DCHECK(end_position >= start_position);
-  pos_ = start_position;
+  DCHECK_GE(static_cast<size_t>(string_->length()),
+            (end_position - start_position));
+  buffer_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;
-}
-
+GenericStringUtf16CharacterStream::~GenericStringUtf16CharacterStream() {}
 
 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;
   }
   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.
+
+class ExternalTwoByteStringUtf16CharacterStream : public Utf16CharacterStream {
+ public:
+  ExternalTwoByteStringUtf16CharacterStream(Handle<ExternalTwoByteString> data,
+                                            int start_position,
+                                            int end_position);
+  ~ExternalTwoByteStringUtf16CharacterStream() override;
+
+ private:
+  bool ReadBlock() override;
+
+  const uc16* raw_data_;  // Pointer to the actual array of characters.
+};
 
 ExternalTwoByteStringUtf16CharacterStream::
-    ~ExternalTwoByteStringUtf16CharacterStream() { }
+    ~ExternalTwoByteStringUtf16CharacterStream() {}
 
 ExternalTwoByteStringUtf16CharacterStream::
     ExternalTwoByteStringUtf16CharacterStream(
         Handle<ExternalTwoByteString> data, int start_position,
         int end_position)
-    : raw_data_(data->GetTwoByteData(start_position)), bookmark_(kNoBookmark) {
+    : raw_data_(data->GetTwoByteData(start_position)) {
+  buffer_start_ = raw_data_;
   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_;
+  buffer_pos_ = start_position;
+}
+
+bool ExternalTwoByteStringUtf16CharacterStream::ReadBlock() {
+  // Entire string is read at start.
+  return false;
 }
 
 // ----------------------------------------------------------------------------
 // ExternalOneByteStringUtf16CharacterStream
+//
+// UTF16 buffer to read characters from an external latin1 string.
+class ExternalOneByteStringUtf16CharacterStream
+    : public BufferedUtf16CharacterStream {
+ public:
+  ExternalOneByteStringUtf16CharacterStream(Handle<ExternalOneByteString> data,
+                                            int start_position,
+                                            int end_position);
+  ~ExternalOneByteStringUtf16CharacterStream() override;
+
+  // 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() {}
 
 ExternalOneByteStringUtf16CharacterStream::
     ExternalOneByteStringUtf16CharacterStream(
         Handle<ExternalOneByteString> data, int start_position,
         int end_position)
-    : raw_data_(data->GetChars()),
-      length_(end_position),
-      bookmark_(kNoBookmark) {
+    : 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]);
   }
   return length;
 }
 
+// ----------------------------------------------------------------------------
+// Utf8ExternalStreamingStream - chunked streaming of Utf-8 data.
+
+class Utf8ExternalStreamingStream : public BufferedUtf16CharacterStream {
+ public:
+  Utf8ExternalStreamingStream(
+      ScriptCompiler::ExternalSourceStream* source_stream)
+      : source_stream_(source_stream),
+        current_({0, 0, 0, unibrow::Utf8::Utf8IncrementalBuffer(0)}) {}
+  ~Utf8ExternalStreamingStream() override { DeleteChunks(); }
+
+ protected:
+  size_t FillBuffer(size_t position) override;
+
+ private:
+  void DeleteChunks() {
+    for (size_t i = 0; i < chunks_.size(); i++) delete[] chunks_[i].chunk;
+    chunks_.clear();
+  }
+
+  ScriptCompiler::ExternalSourceStream* source_stream_;
+
+  struct ChunkPos {
+    size_t chunk_no;
+    size_t byte_pos;

[marja, 2016/09/07 09:17:57]

This could use a comment: is byte_pos the position inside the chunk or from the
beginning? It's not clear at that point for somebody reading the code. Without
further information, I'd assume it's the position inside the chunk (so, we'd use
it for indexing into a chunk), but then there is char_pos too, and that's
probably a global char pos, so now I'm not sure about byte_pos either. Also
maybe rename to global_byte_pos / byte_pos_inside_chunk depending on which it is
:)

... and maybe my first interpretation of ChunkPos was incorrect too; I assumed
it's a pair "chunk + position inside it" but maybe it's not?

[vogelheim, 2016/09/07 12:32:56]

Comments provided about the struct.

+    size_t char_pos;
+    unibrow::Utf8::Utf8IncrementalBuffer buffer;
+  };
+
+  struct Chunk {
+    const uint8_t* chunk;
+    size_t byte_length;
+    size_t byte_pos;
+    size_t char_pos;
+    unibrow::Utf8::Utf8IncrementalBuffer buffer;

[marja, 2016/09/07 09:17:57]

This could use a comment, what is buffer? Why does every chunk need one?

[vogelheim, 2016/09/07 12:32:56]

Done. Renamed w/ clearer name (there are too many things called "buffer"..) +
comment about the struct & intended use.

+  };
+  std::vector<Chunk> chunks_;
+  ChunkPos current_;
+};
+
+size_t Utf8ExternalStreamingStream::FillBuffer(size_t position) {

[marja, 2016/09/07 09:17:57]

I'd also specify in the API which positions the params are; this is
char_position, right? Would it make sense to call it char_position?

[vogelheim, 2016/09/07 12:32:56]

APIs are always about characters; the API has no notion of bytes or encodings.

+  // If the desired position is *not* at the current_ position, then we need
+  // to search through the chunks_ vector.
+  if (position != current_.char_pos && !chunks_.empty()) {
+    // Find the appropriate chunk.
+    size_t chunk = chunks_.size() - 1;
+    while (position < chunks_[chunk].char_pos) chunk--;
+
+    Chunk& current = chunks_[chunk];
+    unibrow::Utf8::Utf8IncrementalBuffer b = current.buffer;
+    size_t iter = 0;

[marja, 2016/09/07 09:17:57]

Nit: "it" would be a more commonly used name.

[vogelheim, 2016/09/07 12:32:56]

Done.

+    size_t cpos = current.char_pos;
+    while (cpos < position && iter < current.byte_length) {
+      unibrow::uchar t =
+          unibrow::Utf8::ValueOfIncremental(current.chunk[iter], b);
+      if (t != unibrow::Utf8::kIncomplete) {
+        cpos++;
+      }
+      iter++;
+    }
+    // At this point, we have either found our position; or we're at the end
+    // of the last block. That should only happen if we seek forward (which
+    // the Scanner doesn't do); but if it does we can fix it by recursing.
+    if (cpos == position) {
+      current_ = {chunk, current.byte_pos + iter, cpos, b};
+    } else {
+      DCHECK_EQ(chunk + 1, chunks_.size());
+      current_ = {chunk + 1, current.byte_pos + iter, cpos, b};
+      return FillBuffer(position);
+    }
+  }
+
+  // Fetch more data if we've exhausted the last chunk.
+  if (current_.chunk_no == chunks_.size()) {
+    const uint8_t* chunk = nullptr;
+    size_t length = source_stream_->GetMoreData(&chunk);
+    chunks_.push_back(
+        {chunk, length, current_.byte_pos, current_.char_pos, current_.buffer});
+  }
+
+  // Return 0 if we're out of data. That is: If we have a zero-length chunk.
+  Chunk& current_chunk = chunks_[current_.chunk_no];
+  if (current_chunk.byte_length == 0) return 0;
+
+  // At this point, we know we have data to return in current_chunk.
+  uc16* buffer_cursor = buffer_;
+  uc16* buffer_end = buffer_ + kBufferSize;
+  unibrow::Utf8::Utf8IncrementalBuffer buffer =

[marja, 2016/09/07 09:17:57]

Umm, what? I don't understand what this if does.

[vogelheim, 2016/09/07 12:32:56]

Renamed, to hopefully make it more understandable.

+      (current_.byte_pos == current_chunk.byte_pos)
+          ? current_chunk.buffer
+          : unibrow::Utf8::Utf8IncrementalBuffer(0);
+
+  size_t iter;
+  for (iter = current_.byte_pos - current_chunk.byte_pos;
+       iter < current_chunk.byte_length && buffer_cursor < buffer_end - 1;
+       iter++) {
+    unibrow::uchar t =
+        unibrow::Utf8::ValueOfIncremental(current_chunk.chunk[iter], buffer);
+    if (t == unibrow::Utf8::kIncomplete) continue;
+    if (t <= unibrow::Utf16::kMaxNonSurrogateCharCode) {
+      *(buffer_cursor++) = static_cast<uc16>(t);
+    } else {
+      *(buffer_cursor++) = unibrow::Utf16::LeadSurrogate(t);
+      *(buffer_cursor++) = unibrow::Utf16::TrailSurrogate(t);
+    }
+  }
+  buffer_cursor_ = buffer_;
+  buffer_end_ = buffer_cursor;
+
+  current_.byte_pos = current_chunk.byte_pos + iter;
+  current_.char_pos += (buffer_end_ - buffer_cursor_);
+  if (iter == current_chunk.byte_length) {
+    current_.chunk_no++;

[marja, 2016/09/07 09:17:57]

Nit: ++current_.chunk_no;

+    current_.buffer = buffer;
+
+    if (current_.char_pos - position == 0) {

[marja, 2016/09/07 09:17:57]

Why not if (current_.char_pos == position) ?

[vogelheim, 2016/09/07 12:32:56]

Done.

+      // This tests for the pathological condition that we haven't produced
+      // a single character, but we're not out of data. (E.g. when the
+      // embedder gives us a single-byte chunk, and that one byte is at start
+      // or middle of a multi-byte utf-8 sequence.) Since we can't return 0 -
+      // this would indicate the end of data - we will simply recurse.
+      return FillBuffer(position);
+    }
+  }
+
+  return current_.char_pos - position;
+}
+
+// ----------------------------------------------------------------------------
+// Chunks - helper for One- + TwoByteExternalStreamingStream
+namespace {
+
+struct Chunk {
+  const uint8_t* chunk;
+  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
+
+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)];
+  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
+
+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) 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 lonley_byte = (chunks_[chunk_no].byte_pos == (2 * position + 1));
+  if (lonley_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