Rework scanner-character-streams.

src/parsing/scanner-character-streams.cc

Index: src/parsing/scanner-character-streams.cc
diff --git a/src/parsing/scanner-character-streams.cc b/src/parsing/scanner-character-streams.cc
index a1c8ceb69b52e01402f4848001a1f7d268e6871e..d0c12acf885bbc04c9ea683f067bf2cf9d1c6708 100644
--- a/src/parsing/scanner-character-streams.cc
+++ b/src/parsing/scanner-character-streams.cc
@@ -8,503 +8,564 @@
 #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].*

[nickie, 2016/09/09 11:21:48]

I can't see any Mem(Copy|Move) in the code that changed.  Am I missing
something?

[vogelheim, 2016/09/14 11:28:18]

Done.

 
 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;
-}
+// ----------------------------------------------------------------------------
+// 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;

[nickie, 2016/09/09 11:21:48]

Is the destructor necessary in this class?  The destructor (line) 46 is empty,
as in the case of the base class.

[vogelheim, 2016/09/14 11:28:19]

I think so. This thing will be deleted via its super-class, so there needs to be
a virtual destructor. Honestly, I'm not entirely sure what the compiler will
generate. The style guide isn't very clear on this...

[nickie, 2016/09/14 11:48:17]

There has to be a virtual destructor but it does not have to be overriden if the
desired behavior is identical to that of the parent class (here both destructors
do nothing).  I'm suggesting to remove line 27 here (and in the similar cases
below), not the empty virtual destructor of Utf16CharacterStream.

 
-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;
+ protected:
+  static const size_t kBufferSize = 512;
 
-  if (encoding == ScriptCompiler::StreamedSource::UTF8) {
-    return CopyUtf8CharsToUtf16Chars(dest, length, src, src_pos, src_length);
-  }
+  bool ReadBlock() override;
 
-  size_t to_fill = length;
-  if (to_fill > src_length - *src_pos) to_fill = src_length - *src_pos;
+  // 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;
 
-  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;
-}
+  // Fixed sized buffer that this class reads from.
+  // buffer_start_ should always point to buffer_

[nickie, 2016/09/09 11:21:48]

Maybe introduce "The base class's " in the beginning of the line, and "." at the
end.

[vogelheim, 2016/09/14 11:28:19]

Done.

+  uc16 buffer_[kBufferSize];
+};
 
-}  // namespace
+BufferedUtf16CharacterStream::BufferedUtf16CharacterStream()
+    : Utf16CharacterStream(buffer_, buffer_, buffer_, 0) {}
 
+BufferedUtf16CharacterStream::~BufferedUtf16CharacterStream() {}
 
-// ----------------------------------------------------------------------------
-// BufferedUtf16CharacterStreams
+bool BufferedUtf16CharacterStream::ReadBlock() {
+  DCHECK_EQ(buffer_start_, buffer_);
 
-BufferedUtf16CharacterStream::BufferedUtf16CharacterStream()
-    : Utf16CharacterStream(),
-      pushback_limit_(NULL) {
-  // Initialize buffer as being empty. First read will fill the buffer.
+  size_t position = pos();
+  buffer_pos_ = position;
   buffer_cursor_ = buffer_;
-  buffer_end_ = buffer_;
+  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>.
 
-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));
-}
+class GenericStringUtf16CharacterStream : public BufferedUtf16CharacterStream {
+ public:
+  GenericStringUtf16CharacterStream(Handle<String> data, size_t start_position,
+                                    size_t end_position);
+  ~GenericStringUtf16CharacterStream() override;

[nickie, 2016/09/09 11:21:48]

Same.  Is the empty destructor necessary?

 
+ protected:
+  size_t FillBuffer(size_t position) override;
 
-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.
+  Handle<String> string_;
+  size_t length_;
+};
 
-  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_--;
+GenericStringUtf16CharacterStream::GenericStringUtf16CharacterStream(
+    Handle<String> data, size_t start_position, size_t end_position)
+    : string_(data), length_(end_position) {
+  DCHECK_GE(end_position, start_position);
+  DCHECK_GE(static_cast<size_t>(string_->length()),
+            (end_position - start_position));

[nickie, 2016/09/09 11:21:48]

nit: why use parentheses here?

[vogelheim, 2016/09/14 11:28:18]

Done.

+  buffer_pos_ = start_position;
 }
 
+GenericStringUtf16CharacterStream::~GenericStringUtf16CharacterStream() {}
 
-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 GenericStringUtf16CharacterStream::FillBuffer(size_t from_pos) {
+  if (from_pos >= length_) return 0;
+
+  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;
 }
 
+// ----------------------------------------------------------------------------
+// ExternalTwoByteStringUtf16CharacterStream.
+//
+// A stream whose data source is a Handle<ExternalTwoByteString>. It avoids
+// all data copying.
 
-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);
-}
+class ExternalTwoByteStringUtf16CharacterStream : public Utf16CharacterStream {
+ public:
+  ExternalTwoByteStringUtf16CharacterStream(Handle<ExternalTwoByteString> data,
+                                            size_t start_position,
+                                            size_t end_position);
+  ~ExternalTwoByteStringUtf16CharacterStream() override;

[nickie, 2016/09/09 11:21:48]

Same.

 
+ private:
+  bool ReadBlock() override;
 
-// ----------------------------------------------------------------------------
-// GenericStringUtf16CharacterStream
+  const uc16* raw_data_;  // Pointer to the actual array of characters.
+};
 
+ExternalTwoByteStringUtf16CharacterStream::
+    ~ExternalTwoByteStringUtf16CharacterStream() {}
 
-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;
+ExternalTwoByteStringUtf16CharacterStream::
+    ExternalTwoByteStringUtf16CharacterStream(
+        Handle<ExternalTwoByteString> data, size_t start_position,
+        size_t end_position)
+    : raw_data_(data->GetTwoByteData(start_position)) {
+  buffer_start_ = raw_data_;
+  buffer_cursor_ = raw_data_,
+  buffer_end_ = raw_data_ + (end_position - start_position);
+  buffer_pos_ = start_position;
 }
 
+bool ExternalTwoByteStringUtf16CharacterStream::ReadBlock() {
+  // Entire string is read at start.
+  return false;
+}
 
-GenericStringUtf16CharacterStream::~GenericStringUtf16CharacterStream() { }
+// ----------------------------------------------------------------------------
+// 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);
+  ~ExternalOneByteStringUtf16CharacterStream() override;

[nickie, 2016/09/09 11:21:48]

Same.

 
-bool GenericStringUtf16CharacterStream::SetBookmark() {
-  bookmark_ = pos_;
-  return true;
-}
+  // For testing:
+  ExternalOneByteStringUtf16CharacterStream(const char* data, size_t length);
 
+ protected:
+  size_t FillBuffer(size_t position) override;
 
-void GenericStringUtf16CharacterStream::ResetToBookmark() {
-  DCHECK(bookmark_ != kNoBookmark);
-  pos_ = bookmark_;
-  buffer_cursor_ = buffer_;
-  buffer_end_ = buffer_ + FillBuffer(pos_);
-}
+  const uint8_t* raw_data_;  // Pointer to the actual array of characters.
+  size_t length_;
+};
 
+ExternalOneByteStringUtf16CharacterStream::
+    ~ExternalOneByteStringUtf16CharacterStream() {}
 
-size_t GenericStringUtf16CharacterStream::BufferSeekForward(size_t delta) {
-  size_t old_pos = pos_;
-  pos_ = Min(pos_ + delta, length_);
-  ReadBlock();
-  return pos_ - old_pos;
+ExternalOneByteStringUtf16CharacterStream::
+    ExternalOneByteStringUtf16CharacterStream(
+        Handle<ExternalOneByteString> data, size_t start_position,
+        size_t end_position)
+    : raw_data_(data->GetChars()), length_(end_position) {
+  DCHECK(end_position >= start_position);
+  buffer_pos_ = start_position;
 }
 
+ExternalOneByteStringUtf16CharacterStream::
+    ExternalOneByteStringUtf16CharacterStream(const char* data, size_t length)
+    : raw_data_(reinterpret_cast<const uint8_t*>(data)), length_(length) {}
 
-size_t GenericStringUtf16CharacterStream::FillBuffer(size_t from_pos) {
+size_t ExternalOneByteStringUtf16CharacterStream::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));
+
+  size_t length = Min(kBufferSize, length_ - from_pos);
+  i::CopyCharsUnsigned(buffer_, raw_data_ + 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.
-        }
-      }
+// 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;
+  }
 
-      // Did the data stream end?
-      if (data_ends) {
-        DCHECK(utf8_split_char_buffer_length_ == 0);
-        return data_in_buffer;
+ protected:
+  size_t FillBuffer(size_t position) override;
+
+ private:
+  // ChunkPos points to a position into the chunked stream, containing:
+  // - # of the chunk in the chunks_ vector,
+  // - the 'physical' byte_pos, i.e., the number of bytes from the stream's
+  //   beginning,
+  // - the 'logical' char_pos, i.e. the number of Unicode characters counting
+  //   from the beginning of the stream,
+  // - the incomplete_char, which stores a possibly incomplete utf-8 decoder
+  // state,
+  //   iff the 'physical' byte_pos points into the middle of a utf-8 character.
+  struct ChunkPos {
+    size_t chunk_no;
+    size_t byte_pos;
+    size_t char_pos;
+    unibrow::Utf8::Utf8IncrementalBuffer incomplete_char;
+  };
+
+  // A chunk in the list of chunks, containing the data for the chunk (chunk +
+  // byte_length), and the position of the chunk within the stream (that is,
+  // the chunk contains the data starting at
+  // byte_pos/char_pos/incomplete_first_char).
+  //
+  // It contains:
+  // - a data pointer + length, chunk (owned by the stream) and byte_length,
+  // - the 'physical' byte_pos of the chunk (i.e. the number of bytes, counted
+  //   from the beginning of the stream, at which this chunk begins),
+  // - the 'logical' char_pos of the chunk (i.e. the number of Unicode
+  //   characters, counted from the beginning of the stream),
+  // - the incomplete_first_char, which stores a possibly incomplete utf-8
+  //   decoder state, iff the 'physical' byte_pos points into the middle of a
+  //   utf-8 character.
+  //
+  // So each chunk contains the bytes [byte_pos .. byte_pos + byte_length - 1]
+  // from the entire stream, and decoding from the beginning of the chunk
+  // (using incomplete_first_char) will yield the stream's char_pos-th unicode
+  // character.
+  struct Chunk {
+    const uint8_t* chunk;
+    size_t byte_length;
+    size_t byte_pos;
+    size_t char_pos;
+    unibrow::Utf8::Utf8IncrementalBuffer incomplete_first_char;
+  };
+  std::vector<Chunk> chunks_;
+  ChunkPos current_;
+  ScriptCompiler::ExternalSourceStream* source_stream_;
+};
+
+size_t Utf8ExternalStreamingStream::FillBuffer(size_t position) {
+  // 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 found (or we're in the last chunk and are not sure yet whether the
+    // position is in this chunk, or one of the following ones). Go
+    // incrementally through the buffer until we have found position.
+    Chunk& current_chunk = chunks_[chunk];
+    unibrow::Utf8::Utf8IncrementalBuffer b =
+        current_chunk.incomplete_first_char;
+    size_t it = 0;
+    size_t cpos = current_chunk.char_pos;
+    while (cpos < position && it < current_chunk.byte_length) {
+      unibrow::uchar t =
+          unibrow::Utf8::ValueOfIncremental(current_chunk.chunk[it], &b);
+      if (t != unibrow::Utf8::kIncomplete) {
+        cpos++;
       }
+      it++;
     }
-
-    // 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();
+    // At this point, we have either found our position; or we're at the end
+    // of the last chunk. 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_chunk.byte_pos + it, cpos, b};
+    } else {
+      DCHECK_EQ(chunk + 1, chunks_.size());
+      current_ = {chunk + 1, current_chunk.byte_pos + it, cpos, b};
+      return FillBuffer(position);
     }
   }
-  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;
+  // 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_.incomplete_char});
   }
 
-  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 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 incomplete_char =
+      (current_.byte_pos == current_chunk.byte_pos)
+          ? current_chunk.incomplete_first_char
+          : unibrow::Utf8::Utf8IncrementalBuffer(0);
+
+  size_t it;
+  for (it = current_.byte_pos - current_chunk.byte_pos;
+       it < current_chunk.byte_length && buffer_cursor < buffer_end - 1; it++) {
+    unibrow::uchar t = unibrow::Utf8::ValueOfIncremental(
+        current_chunk.chunk[it], &incomplete_char);
+    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);
+    }
   }
-
-  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];
+  buffer_end_ = buffer_cursor;
+
+  current_.byte_pos = current_chunk.byte_pos + it;
+  current_.char_pos += (buffer_end_ - buffer_cursor_);
+  if (it == current_chunk.byte_length) {
+    current_.chunk_no++;
+    current_.incomplete_char = incomplete_char;
+
+    if (current_.char_pos == position) {
+      // 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 {
 
-void ExternalStreamingStream::FlushCurrent() {
-  delete[] current_data_;
-  current_data_ = NULL;
-  current_data_length_ = 0;
-  current_data_offset_ = 0;
-  bookmark_data_is_from_current_data_ = false;
-}
+struct Chunk {
+  const uint8_t* chunk;
+  size_t byte_length;
+  size_t byte_pos;
+};
 
+typedef std::vector<struct Chunk> Chunks;
 
-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_;
-    }
+void DeleteChunks(Chunks& chunks) {
+  for (size_t i = 0; i < chunks.size(); i++) delete[] chunks[i].chunk;
+}
 
-    // 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;
+// 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);
   }
 
-  // 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;
-    }
+  // 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;
   }
-  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];
+
+  // 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
 
 // ----------------------------------------------------------------------------
-// ExternalTwoByteStringUtf16CharacterStream
-
-ExternalTwoByteStringUtf16CharacterStream::
-    ~ExternalTwoByteStringUtf16CharacterStream() { }
-
-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;
+// 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)];
+  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;
 }
 
-
-bool ExternalTwoByteStringUtf16CharacterStream::SetBookmark() {
-  bookmark_ = pos_;
-  return true;
+// ----------------------------------------------------------------------------
+// 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) 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 loneley_byte = (chunks_[chunk_no].byte_pos == (2 * position + 1));

[nickie, 2016/09/09 11:21:48]

nit: lonely

[vogelheim, 2016/09/14 11:28:18]

Done.

+  if (loneley_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;
+  }
 
-void ExternalTwoByteStringUtf16CharacterStream::ResetToBookmark() {
-  DCHECK(bookmark_ != kNoBookmark);
-  pos_ = bookmark_;
-  buffer_cursor_ = raw_data_ + bookmark_;
+  // 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;
 }
 
 // ----------------------------------------------------------------------------
-// ExternalOneByteStringUtf16CharacterStream
-
-ExternalOneByteStringUtf16CharacterStream::
-    ~ExternalOneByteStringUtf16CharacterStream() {}
+// ScannerStream: Create stream instances.
 
-ExternalOneByteStringUtf16CharacterStream::
-    ExternalOneByteStringUtf16CharacterStream(
-        Handle<ExternalOneByteString> data, int start_position,
-        int end_position)
-    : raw_data_(data->GetChars()),
-      length_(end_position),
-      bookmark_(kNoBookmark) {
-  DCHECK(end_position >= start_position);
-  pos_ = start_position;
+Utf16CharacterStream* ScannerStream::For(Handle<String> data) {
+  return ScannerStream::For(data, 0, data->length());
 }
 
-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;
+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);
+  }
 }
 
-void ExternalOneByteStringUtf16CharacterStream::ResetToBookmark() {
-  DCHECK(bookmark_ != kNoBookmark);
-  pos_ = bookmark_;
-  buffer_cursor_ = buffer_;
-  buffer_end_ = buffer_ + FillBuffer(pos_);
+std::unique_ptr<Utf16CharacterStream> ScannerStream::ForTesting(
+    const char* data) {
+  return ScannerStream::ForTesting(data, strlen(data));
 }
 
-size_t ExternalOneByteStringUtf16CharacterStream::BufferSeekForward(
-    size_t delta) {
-  size_t old_pos = pos_;
-  pos_ = Min(pos_ + delta, length_);
-  ReadBlock();
-  return pos_ - old_pos;
+std::unique_ptr<Utf16CharacterStream> ScannerStream::ForTesting(
+    const char* data, size_t length) {
+  return std::unique_ptr<Utf16CharacterStream>(
+      new ExternalOneByteStringUtf16CharacterStream(data, 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]);
+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);
   }
-  return length;
+  UNREACHABLE();
+  return nullptr;
 }
 
 }  // namespace internal