Rework scanner-character-streams.

src/parsing/scanner.h

 // 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.
 
 // Features shared by parsing and pre-parsing scanners.
 
 #ifndef V8_PARSING_SCANNER_H_
 #define V8_PARSING_SCANNER_H_
 
 #include "src/allocation.h"
 #include "src/base/logging.h"
 #include "src/char-predicates.h"
 #include "src/globals.h"
 #include "src/messages.h"
 #include "src/parsing/token.h"
 #include "src/unicode-decoder.h"
 #include "src/unicode.h"
 
 namespace v8 {
 namespace internal {
 
 
 class AstRawString;
 class AstValueFactory;
 class DuplicateFinder;
+class ExternalOneByteString;
+class ExternalTwoByteString;
 class ParserRecorder;
 class UnicodeCache;
 
-
 // ---------------------------------------------------------------------
 // Buffered stream of UTF-16 code units, using an internal UTF-16 buffer.
 // A code unit is a 16 bit value representing either a 16 bit code point
 // or one part of a surrogate pair that make a single 21 bit code point.
-
 class Utf16CharacterStream {
  public:
-  Utf16CharacterStream() : pos_(0) { }
+  static const uc32 kEndOfInput = -1;
+
   virtual ~Utf16CharacterStream() { }
 
   // Returns and advances past the next UTF-16 code unit in the input
-  // stream. If there are no more code units, it returns a negative
-  // value.
+  // stream. If there are no more code units it returns kEndOfInput.
   inline uc32 Advance() {
-    if (buffer_cursor_ < buffer_end_ || ReadBlock()) {
-      pos_++;
+    if (V8_LIKELY(buffer_cursor_ < buffer_end_)) {
       return static_cast<uc32>(*(buffer_cursor_++));
+    } else if (ReadBlock()) {

[nickie, 2016/09/07 13:28:28]

I suppose you did not like how it was before:
if (V8_LIKELY(...) || ReadBlock())

[vogelheim, 2016/09/08 13:09:02]

I liked it, but: V8_LIKELY supplies information about the if-else to the
compiler. I'm not sure the compiler can transfer this explicit likeli-hood
information on a sub-expression to the branches it might generate from the
surrounding expression.

Admittedly, I intuited that, and I can't find documentation that is explicit
about this. I've never seen a V8_(UN)LIKELY or __builtin_expect that did not
cover the entire condition, though.

+      return static_cast<uc32>(*(buffer_cursor_++));
+    } else {
+      // Note: currently the following increment is necessary to avoid a
+      // parser problem! The scanner treats the final kEndOfInput as
+      // a code unit with a position, and does math relative to that
+      // position.
+      buffer_cursor_++;
+      return kEndOfInput;
     }
-    // Note: currently the following increment is necessary to avoid a
-    // parser problem! The scanner treats the final kEndOfInput as
-    // a code unit with a position, and does math relative to that
-    // position.
-    pos_++;
-
-    return kEndOfInput;
   }
 
-  // Return the current position in the code unit stream.
-  // Starts at zero.
-  inline size_t pos() const { return pos_; }
-
-  // Skips forward past the next code_unit_count UTF-16 code units
-  // in the input, or until the end of input if that comes sooner.
-  // Returns the number of code units actually skipped. If less
-  // than code_unit_count,
-  inline size_t SeekForward(size_t code_unit_count) {
-    size_t buffered_chars = buffer_end_ - buffer_cursor_;
-    if (code_unit_count <= buffered_chars) {
-      buffer_cursor_ += code_unit_count;
-      pos_ += code_unit_count;
-      return code_unit_count;
+  inline void Back() {

[nickie, 2016/09/07 13:28:28]

A comment explaining what this should do would be welcome.
It's straightforward in the most likely case, not in the other one.

[vogelheim, 2016/09/08 13:09:03]

Done.

+    if (V8_LIKELY(buffer_cursor_ > buffer_start_)) {
+      buffer_cursor_--;

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

Nit: --buffer_cursor_;

[vogelheim, 2016/09/08 13:09:02]

Why? [Here and elsewhere.]

------

I find the prefix-version odd to read.

The style guide has no opinion: V8 style references Chromium style which
references Google style, which says: "For simple scalar (non-object) values
there is no reason to prefer one form and we allow either."

[Ref:
https://google.github.io/styleguide/cppguide.html#Preincrement_and_Predecrement
]

+    } else {
+      ReadBlockAt(pos() - 1);

[nickie, 2016/09/07 13:28:28]

We discussed this offline.  This can make a series of consecutive Back() pretty
expensive.  It could be "void Back(int num = 1)" and use "pos() - num" here.

[vogelheim, 2016/09/08 13:09:02]

That's almost the same as Seek. :)  The Scanner only uses num = 1..2, so I added
a Back2().

     }
-    return SlowSeekForward(code_unit_count);
   }
 
-  // Pushes back the most recently read UTF-16 code unit (or negative
-  // value if at end of input), i.e., the value returned by the most recent
-  // call to Advance.
-  // Must not be used right after calling SeekForward.
-  virtual void PushBack(int32_t code_unit) = 0;
+  inline size_t pos() const {
+    return buffer_pos_ + (buffer_cursor_ - buffer_start_);

[nickie, 2016/09/07 13:28:28]

This calculation is quite expensive and the pos() method is called very often
from the parser.  I suppose, the scanner delegates it here.

Maybe it would make sense to measure this against having a separate current_pos_
field (like the pos_ in old line 59) and making sure that this is consistent.

[vogelheim, 2016/09/08 13:09:02]

Hmm. I think I should try it both ways.


(My thinking was: pos() is fully inline-able, and should be only 2 instructions
on x64, on data that is already in cache (and oftentimes also in a register) at
that point. The alternative, an additional variable + 1 instruction to maintain
might not be faster.)

+  }
 
-  virtual bool SetBookmark();
-  virtual void ResetToBookmark();
+  inline void Seek(size_t pos) {
+    if (V8_LIKELY(pos >= buffer_pos_ &&
+                  pos < (buffer_pos_ + (buffer_end_ - buffer_start_)))) {
+      buffer_cursor_ = buffer_start_ + (pos - buffer_pos_);
+    } else {
+      ReadBlockAt(pos);
+    }
+  }
+
+  // Legacy API:
+  void SeekForward(size_t code_unit_count) { Seek(pos() + code_unit_count); }
+  void PushBack(int32_t code_unit) {
+    Back();
+#ifdef DEBUG
+    uc32 t = Advance();
+    DCHECK_EQ(t, code_unit);
+    Back();

[nickie, 2016/09/07 13:28:28]

Why not simply this?
DCHECK_EQ(code_unit, static_cast<uc32>(*(buffer_cursor_++)));
After Back() it is guaranteed that buffer_cursor_ < buffer_end_, isn't it?

In a quite unfrequent case, this Advance-Back will result in an extra buffer
loaded, right?

+#endif  // DEBUG
+  }
+  bool SetBookmark() {

[nickie, 2016/09/07 13:28:28]

I don't understand why the bookmark should be stored in the stream.  A simpler
interface would be to use "bookmark = pos()" directly to obtain a bookmark, and
something like "Seek(bookmark)" to reset to that.  If we still want to have
streams that do not support bookmarking (?) then we could have a SetBookmark
method returning either pos() or NO_BOOKMARK (see below).

[vogelheim, 2016/09/08 13:09:03]

You're exactly right: The bookmark doesn't belong in the stream (any more). But
I was desperately trying to keep the CL small-ish, and hence wanted to avoid
touching the clients of the stream just yet, and  to remove the "// Legacy API"
in a separate, upcoming CL. That would exactly what you suggest.

+    bookmark_ = pos();
+    return true;
+  }
+  void ResetToBookmark() {
+    DCHECK(bookmark_ != (size_t)-1);

[nickie, 2016/09/07 13:28:28]

How about something like this?  (with a better name, I guess)
static const size_t NO_BOOKMARK = numeric_limits<size_t>::max();

[vogelheim, 2016/09/08 13:09:03]

Done.

+    Seek(bookmark_);
+  }
 
  protected:
-  static const uc32 kEndOfInput = -1;
+  Utf16CharacterStream(const uint16_t* buffer_start,
+                       const uint16_t* buffer_cursor,
+                       const uint16_t* buffer_end, size_t buffer_pos)
+      : buffer_start_(buffer_start),
+        buffer_cursor_(buffer_cursor),
+        buffer_end_(buffer_end),
+        buffer_pos_(buffer_pos),
+        bookmark_((size_t)-1) {}

[nickie, 2016/09/07 13:28:28]

Again, NO_BOOKMARK here.

[vogelheim, 2016/09/08 13:09:03]

Done.

+  Utf16CharacterStream() : Utf16CharacterStream(nullptr, nullptr, nullptr, 0) {}
+
+  void ReadBlockAt(size_t new_pos) {
+    // This shouldn't ever be called if new_pos is inside the current buffer.
+    DCHECK(new_pos < buffer_pos_ ||
+           new_pos >= buffer_pos_ + (buffer_end_ - buffer_start_));
+    buffer_pos_ = new_pos;
+    buffer_cursor_ = buffer_start_;

[nickie, 2016/09/07 13:28:28]

I don't understand this.  Maybe related to my next comment.

[vogelheim, 2016/09/08 13:09:02]

See below.

This wants to set the position for ReadBlock() (which reads it from pos()), so
it must change all the vars that make up pos() to accomplish this.

+    ReadBlock();
+  }
 
   // Ensures that the buffer_cursor_ points to the code_unit at
-  // position pos_ of the input, if possible. If the position
-  // is at or after the end of the input, return false. If there
-  // are more code_units available, return true.
+  // position pos() of the input. Returns true if data is available; false if

[nickie, 2016/09/07 13:28:29]

How can this not be true?
pos() is calculated in such a way to enforce that.
I suppose this comment should change and describe more clearly what ReadBlock is
expected to.

[vogelheim, 2016/09/08 13:09:02]

It's meant to explain the post-condition for ReadBlock, and in particular remind
the implementer that they can/must update both buffer_pos and buffer_start_.

I think the source of confusion is that pos() is really a derivative of three
values, so any method that updates any of those needs to take care to consider
them jointly.

I updated the comments to reflect this.

------

Maybe the best way of fixing this is to drop the ReadBlock() signature, and
always use something like FillBuffer(size_t). If so, I'll do it in a separate
step.

+  // pos() is at (or after) the end of input
   virtual bool ReadBlock() = 0;
-  virtual size_t SlowSeekForward(size_t code_unit_count) = 0;
 
+  const uint16_t* buffer_start_;
   const uint16_t* buffer_cursor_;
   const uint16_t* buffer_end_;
-  size_t pos_;
+  size_t buffer_pos_;
+  size_t bookmark_;
 };
 
 
 // ----------------------------------------------------------------------------
 // JavaScript Scanner.
 
 class Scanner {
  public:
   // Scoped helper for a re-settable bookmark.
   class BookmarkScope {
@@ skipping 24 matching lines @@
     }
 
     static Location invalid() { return Location(-1, -1); }
 
     int beg_pos;
     int end_pos;
   };
 
   // -1 is outside of the range of any real source code.
   static const int kNoOctalLocation = -1;
+  static const uc32 kEndOfInput = Utf16CharacterStream::kEndOfInput;
 
   explicit Scanner(UnicodeCache* scanner_contants);
 
   void Initialize(Utf16CharacterStream* source);
 
   // Returns the next token and advances input.
   Token::Value Next();
   // Returns the token following peek()
   Token::Value PeekAhead();
   // Returns the current token again.
@@ skipping 641 matching lines @@
   bool found_html_comment_;
 
   MessageTemplate::Template scanner_error_;
   Location scanner_error_location_;
 };
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_PARSING_SCANNER_H_