Add StringBufferStream

src/objects.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 7488 matching lines @@
       if (*chars > kMaxAsciiCharCodeU) return static_cast<int>(chars - start);
       ++chars;
     }
     return static_cast<int>(chars - start);
   }
 
   static inline bool IsAscii(const uc16* chars, int length) {
     return NonAsciiStart(chars, length) >= length;
   }
 
+  template<class Visitor, class ConsOp>
+  static inline void Visit(String* string,

[Yang, 2012/12/04 14:49:11]

Why is this part of the String class and not part of the StringBufferStream?

+                           unsigned offset,
+                           Visitor& visitor,
+                           ConsOp& consOp,
+                           int32_t type,
+                           unsigned length);
+
  protected:
   class ReadBlockBuffer {
    public:
     ReadBlockBuffer(unibrow::byte* util_buffer_,
                     unsigned cursor_,
                     unsigned capacity_,
                     unsigned remaining_) :
       util_buffer(util_buffer_),
       cursor(cursor_),
       capacity(capacity_),
@@ skipping 440 matching lines @@
   : public unibrow::InputBuffer<String, String**, 256> {
  public:
   virtual void Seek(unsigned pos);
   inline SafeStringInputBuffer()
       : unibrow::InputBuffer<String, String**, 256>() {}
   explicit inline SafeStringInputBuffer(String** backing)
       : unibrow::InputBuffer<String, String**, 256>(backing) {}
 };
 
 
+// This maintains an off-stack representation of the stack frames required
+// to traverse a ConsString, allowing an entirely iterative and restartable
+// traversal of the entire string
+class ConsStringIteratorOp {
+ public:
+  struct ContinueResponse {
+    String* string;
+    unsigned offset;
+    unsigned length;
+    int32_t type;
+  };
+  inline ConsStringIteratorOp() {}
+  String* Operate(ConsString* consString, unsigned* outerOffset,
+      int32_t* typeOut, unsigned* lengthOut);
+  inline bool ContinueOperation(ContinueResponse* response);
+  inline void Reset();
+  inline bool HasMore();
+
+ private:
+  // TODO(dcarney): Templatize this out for different stack sizes.
+  static const unsigned stackSize = 32;

[Yang, 2012/12/04 14:49:11]

Please write constants in camel case starting with k, like kStackSize.

+  // Use a mask instead of doing modulo operations for stack wrapping.
+  static const unsigned depthMask = 0x1F;

[Yang, 2012/12/04 14:49:11]

Could you write that as stackSize - 1 and assert that
STATIC_ASSERT(IS_POWER_OF_TWO(stackSize))?

+  static inline unsigned OffsetForDepth(unsigned depth);
+  static inline uint32_t MaskForDepth(unsigned depth);
+
+  inline void ClearRightDescent();
+  inline void SetRightDescent();
+  inline void PushLeft(ConsString* string);
+  inline void PushRight(ConsString* string, int32_t type);
+  inline void AdjustMaximumDepth();
+  inline void Pop();
+  inline void ResetStack();
+  String* NextLeaf(bool* blewStack, int32_t* typeOut);
+
+  unsigned depth;

[Yang, 2012/12/04 14:49:11]

Please add an underscore to all member variables, like depth_, and use
underscore notation, like root_type_

+  unsigned maximumDepth;
+  uint32_t trace;
+  ConsString* frames[stackSize];

[Yang, 2012/12/04 14:49:11]

I wonder if you could just use a ZoneList to allocate a list of cons strings in
the Zone (things in the Zone are automatically deleted if the ZoneScope is left)
instead of a fixed-size stack.

+  unsigned consumed;
+  ConsString* root;
+  int32_t rootType;
+  unsigned rootLength;
+  DISALLOW_COPY_AND_ASSIGN(ConsStringIteratorOp);
+};
+
+
+class StringBufferStream {

[Yang, 2012/12/04 14:49:11]

Different than what the name suggests, this class does not really offer a buffer
to read from, but rather hides traversing of a cons string, right?
I wonder how that would impact the performance (copying string content to a
linear buffer and reading that buffered chunk without interruptions vs.
traversing a cons string on demand). Unless of course you are planning to build
a buffered layer in between. So I'd suggest a rename.

+ public:
+  // All initialization done in Reset.
+  inline StringBufferStream() {}

[Yang, 2012/12/04 14:49:11]

I think it would be less error prone if the constructor implicitly calls Reset
to initialize member variables (which should use underscore notation and end
with an underscore).

+  inline uint16_t GetNext();
+  inline bool has_more();
+  inline void Reset(String* string, unsigned offset, ConsStringIteratorOp* op);
+  inline void VisitOneByteString(const uint8_t* chars, unsigned length);
+  inline void VisitTwoByteString(const uint16_t* chars, unsigned length);
+
+ private:
+  bool isOneByte;
+  union {
+    const uint8_t* buffer8;
+    const uint16_t* buffer16;

[Yang, 2012/12/04 14:49:11]

Instead of using a pointer into the string, using an index relative to the
string start to address the current character would remove the use of an union
and also work if the string is being moved due to GC.

Same goes for end.

+  };
+  const uint8_t* end;
+  ConsStringIteratorOp* op;
+  DISALLOW_COPY_AND_ASSIGN(StringBufferStream);
+};
+
+
 template <typename T>
 class VectorIterator {
  public:
   VectorIterator(T* d, int l) : data_(Vector<const T>(d, l)), index_(0) { }
   explicit VectorIterator(Vector<const T> data) : data_(data), index_(0) { }
   T GetNext() { return data_[index_++]; }
   bool has_more() { return index_ < data_.length(); }
  private:
   Vector<const T> data_;
   int index_;
@@ skipping 1029 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_