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..dd742608c06420616e52ca7776a44cc7cfc075ac 100644
--- a/src/parsing/scanner-character-streams.cc
+++ b/src/parsing/scanner-character-streams.cc
@@ -8,187 +8,82 @@
 #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 {
-
-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();
+  ~BufferedUtf16CharacterStream() override;
 
-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() { }
+ protected:
+  static const size_t kBufferSize = 512;
 
-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));
-}
+  bool ReadBlock() override;
+  virtual size_t FillBuffer(size_t position) = 0;
 
+  uc16 buffer_[kBufferSize];
+};
 
-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_--;
-}
+BufferedUtf16CharacterStream::BufferedUtf16CharacterStream()
+    : Utf16CharacterStream(buffer_, buffer_, buffer_, 0) {}
 
+BufferedUtf16CharacterStream::~BufferedUtf16CharacterStream() {}
 
 bool BufferedUtf16CharacterStream::ReadBlock() {
+  DCHECK_EQ(buffer_start_, buffer_);  // Please nobody mess w/ buffer_start_.

[marja, 2016/09/08 09:46:23]

Hmm, nikolaos@ commented on this offline I think... so hmm, who updates
buffer_start_?

[vogelheim, 2016/09/08 15:02:18]

None of BufferedUtf16CharacterStream's sub-classes. Updated comments.

+
+  size_t position = pos();
+  buffer_pos_ = position;
   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;
+  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>.
 
-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 GenericStringUtf16CharacterStream : public BufferedUtf16CharacterStream {
+ public:
+  GenericStringUtf16CharacterStream(Handle<String> data, size_t start_position,
+                                    size_t end_position);
+  ~GenericStringUtf16CharacterStream() override;
 
-// ----------------------------------------------------------------------------
-// GenericStringUtf16CharacterStream
+ 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) {
+    : string_(data), length_(end_position) {
   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;
+  DCHECK_GE(static_cast<size_t>(string_->length()),
+            (end_position - start_position));
+  buffer_pos_ = start_position;
 }
 
+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;
@@ -198,313 +93,478 @@ size_t GenericStringUtf16CharacterStream::FillBuffer(size_t from_pos) {
   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.
-        }
-      }
+// ExternalTwoByteStringUtf16CharacterStream.
+//
+// A stream whose data source is a Handle<ExternalTwoByteString>. It avoids
+// all data copying.
 
-      // Did the data stream end?
-      if (data_ends) {
-        DCHECK(utf8_split_char_buffer_length_ == 0);
-        return data_in_buffer;
-      }
-    }
+class ExternalTwoByteStringUtf16CharacterStream : public Utf16CharacterStream {
+ public:
+  ExternalTwoByteStringUtf16CharacterStream(Handle<ExternalTwoByteString> data,
+                                            int start_position,
+                                            int end_position);
+  ~ExternalTwoByteStringUtf16CharacterStream() override;
 
-    // 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;
-}
+ private:
+  bool ReadBlock() override;
 
+  const uc16* raw_data_;  // Pointer to the actual array of characters.
+};
 
-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;
-  }
+ExternalTwoByteStringUtf16CharacterStream::
+    ~ExternalTwoByteStringUtf16CharacterStream() {}
 
-  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];
-  }
+ExternalTwoByteStringUtf16CharacterStream::
+    ExternalTwoByteStringUtf16CharacterStream(
+        Handle<ExternalTwoByteString> data, int start_position,
+        int 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;
+}
 
-  return source_stream_->SetBookmark();
+bool ExternalTwoByteStringUtf16CharacterStream::ReadBlock() {
+  // Entire string is read at start.
+  return false;
 }
 
+// ----------------------------------------------------------------------------
+// ExternalOneByteStringUtf16CharacterStream
+//
+// A stream whose data source is a Handle<ExternalOneByteString>.
+
+class ExternalOneByteStringUtf16CharacterStream
+    : public BufferedUtf16CharacterStream {
+ public:
+  ExternalOneByteStringUtf16CharacterStream(Handle<ExternalOneByteString> data,
+                                            int start_position,
+                                            int end_position);
+  ~ExternalOneByteStringUtf16CharacterStream() override;
 
-void ExternalStreamingStream::ResetToBookmark() {
-  source_stream_->ResetToBookmark();
-  FlushCurrent();
+  // For testing:
+  ExternalOneByteStringUtf16CharacterStream(const char* data, size_t length);
 
-  pos_ = bookmark_;
+ protected:
+  size_t FillBuffer(size_t position) override;
 
-  // 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;
+  const uint8_t* raw_data_;  // Pointer to the actual array of characters.
+  size_t length_;
+};
 
-  // 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();
+ExternalOneByteStringUtf16CharacterStream::
+    ~ExternalOneByteStringUtf16CharacterStream() {}
 
-  // 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];
-  }
+ExternalOneByteStringUtf16CharacterStream::
+    ExternalOneByteStringUtf16CharacterStream(
+        Handle<ExternalOneByteString> data, int start_position,
+        int 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) {}
 
-void ExternalStreamingStream::FlushCurrent() {
-  delete[] current_data_;
-  current_data_ = NULL;
-  current_data_length_ = 0;
-  current_data_offset_ = 0;
-  bookmark_data_is_from_current_data_ = false;
+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;

[nickie, 2016/09/07 13:48:44]

This for loop should be equivalent to an instance of CopyCharsUnsigned, which I
presume is what some instance of String::WriteToFlat does.  Compare with the
method in line 84.

[vogelheim, 2016/09/08 15:02:18]

Yes, nice catch. Done.

 }
 
+// ----------------------------------------------------------------------------
+// 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 { 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();
+  }
 
-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_;
+  // 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;

[marja, 2016/09/08 09:46:23]

It's confusing that you above use byte_pos and char_pos to index into a chunk
(if I understood this correctly) and here you use byte_pos and char_pos to
indicate where the chunk begins in the byte / char stream. Can you rename one
set of them? Maybe keep the above byte_pos / char_pos and rename this one to
chunk_beginning_byte_pos or something along those lines but less horrible.

(Also, when reading the code, if there's someobject.byte_pos, and byte_pos means
something different depending on which one someobject is, it's confusing to the
reader.)

[vogelheim, 2016/09/08 15:02:17]

I don't get the confusing part.

Essentially, a position in the UTF-8 world comprises both a byte_pos and a
char_pos (and a Utf8IncrementalBuffer, in case we allow our position to point
into the middle of an UTF-8 char). And so if I store a chunk, I need to store
it's start position (position == byte pos + char pos + buffer); if I want to
store the current position (also position == byte_pos + char_pos + buffer).


To clarify this, I could add seperate struct Position for this purpose. I'm just
not convinced that would really make things more readable.

+    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

[marja, 2016/09/08 09:46:23]

Could this function be structured differently so that it would be easier to
understand?

Idea 1: fast path first, what if the desired position is at the current
position?

Idea 2: separate the chunk finding to a helper function?

(I can't tell in advance whether these would work...)

[vogelheim, 2016/09/08 15:02:18]

I'm skeptical.

The fast path is what happens after the non-fast path has run. Putting it first
would be awkward.

A separate chunk finding function would also be awkward, since the callee has to
do some of the utf-8 processing (to find the current position); or maybe the
caller has to, but then the helper function would return a partial result, e.g.
maybe the last block, but it can't be sure (since it didn't skip ahead to the
desired position.)


Also, as mentioned somewhere below to a similar comment: All the helper would do
is to move straight-line code out of the way, without either adding an
abstraction; or increasing re-use; or simplifying things. It would merely add an
indirection which - at least in my view - doesn't really clarify things all that
much.

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

[marja, 2016/09/08 09:46:23]

Could you rename current to current_chunk, just to be extra clear (related to
the above whine that I'm losing track what current.byte_pos etc are)?

[vogelheim, 2016/09/08 15:02:18]

Done.

+    unibrow::Utf8::Utf8IncrementalBuffer b = current.incomplete_first_char;

[marja, 2016/09/08 09:46:23]

I had to think for a while why we need to do this here; maybe add a comment?

E.g.,:

Read through the chunk character by character to find the right position. The
chunk might begin with an incomplete character, whose beginning is already
stored in incomplete_first_char.

[vogelheim, 2016/09/08 15:02:17]

Done.

+    size_t it = 0;
+    size_t cpos = current.char_pos;
+    while (cpos < position && it < current.byte_length) {
+      unibrow::uchar t =
+          unibrow::Utf8::ValueOfIncremental(current.chunk[it], b);
+      if (t != unibrow::Utf8::kIncomplete) {
+        cpos++;
+      }
+      it++;
     }
+    // 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

[marja, 2016/09/08 09:46:23]

... of the last chunk?

[vogelheim, 2016/09/08 15:02:18]

Done.

+    // the Scanner doesn't do); but if it does we can fix it by recursing.
+    if (cpos == position) {
+      current_ = {chunk, current.byte_pos + it, cpos, b};
+    } else {
+      DCHECK_EQ(chunk + 1, chunks_.size());
+      current_ = {chunk + 1, current.byte_pos + it, cpos, b};
+      return FillBuffer(position);
+    }
+  }

[marja, 2016/09/08 09:46:23]

Can finding the position be moved to a helper function, or will that mess up
with the recursion thing? Clearly this function does two things: first it finds
the right position, then it reads data from that position.

[vogelheim, 2016/09/08 15:02:17]

See above.

 
-    // 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;
+  // 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});
   }
 
-  // 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;
+  // Return 0 if we're out of data. That is: If we have a zero-length chunk.
+  Chunk& current_chunk = chunks_[current_.chunk_no];

[marja, 2016/09/08 09:46:23]

Oops, now we have current_chunk..

It's confusing that we have:
current_
current
current_chunk in this function!

[vogelheim, 2016/09/08 15:02:17]

Done... I guess? It's now current_chunk and current_

+  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);

[marja, 2016/09/08 09:46:23]

Umm, what? Why?

[vogelheim, 2016/09/08 15:02:17]

As the method comment says: "and decoding from the beginning of the using
incomplete_first_char) will yield the stream's char_pos-th unicode character."

That's what we're dooing here. If we decode from the beginning of a chunk, we'll
use the incomplete_first_char from that chunk.

+
+  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);
     }
   }
-  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];
+  buffer_cursor_ = buffer_;
+  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;
+}
 
 // ----------------------------------------------------------------------------
-// ExternalTwoByteStringUtf16CharacterStream
+// Chunks - helper for One- + TwoByteExternalStreamingStream
+namespace {
 
-ExternalTwoByteStringUtf16CharacterStream::
-    ~ExternalTwoByteStringUtf16CharacterStream() { }
+struct Chunk {
+  const uint8_t* chunk;
+  size_t byte_length;
+  size_t byte_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;
+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);
+  }
 
-bool ExternalTwoByteStringUtf16CharacterStream::SetBookmark() {
-  bookmark_ = pos_;
-  return true;
+  // 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
 
-void ExternalTwoByteStringUtf16CharacterStream::ResetToBookmark() {
-  DCHECK(bookmark_ != kNoBookmark);
-  pos_ = bookmark_;
-  buffer_cursor_ = raw_data_ + bookmark_;
+// ----------------------------------------------------------------------------
+// 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/08 09:46:23]

Here you already have a FindChunk helper, so I think you should have one for the
hard case too. :)

[vogelheim, 2016/09/08 15:02:18]

Nack. Here, I had two identical uses of it, so this case removes unnecessary
code duplication. In the other case, the code is substantially different and is
only used once, to this would merely add an indirection. I guess to some extent
it's a matter of taste, but indirection (without any other benefit) oftentimes
makes things harder to read, at least in my opinion.

+  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;
 }
 
 // ----------------------------------------------------------------------------
-// ExternalOneByteStringUtf16CharacterStream
+// 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_);
+}
 
-ExternalOneByteStringUtf16CharacterStream::
-    ~ExternalOneByteStringUtf16CharacterStream() {}
+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);
+

[marja, 2016/09/08 09:46:23]

What happens if we have data where the last character is incomplete?

[vogelheim, 2016/09/08 15:02:18]

For the last chunk, the rounding (below: number_of_chars = ... / 2;) would
exclude the last half-char. A subsequent call to ReadBlock would try to read the
2nd char of that half-char, and would determine in the line below that we're out
of data.

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

[marja, 2016/09/08 09:46:23]

typo: lonley

[vogelheim, 2016/09/08 15:02:17]

Done.

+  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;
+  }
 
-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;
+  // 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(const char* data, size_t length)
-    : raw_data_(reinterpret_cast<const uint8_t*>(data)),
-      length_(length),
-      bookmark_(kNoBookmark) {}
+// ----------------------------------------------------------------------------
+// ScannerStream: Create stream instances.
 
-ExternalOneByteStringUtf16CharacterStream::
-    ExternalOneByteStringUtf16CharacterStream(const char* data)
-    : ExternalOneByteStringUtf16CharacterStream(data, strlen(data)) {}
+Utf16CharacterStream* ScannerStream::For(Handle<String> data) {
+  return ScannerStream::For(data, 0, data->length());
+}
 
-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