Cleanup tests for StringCharacterStream

test/cctest/test-strings.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 
 // Check that we can traverse very deep stacks of ConsStrings using
 // StringInputBuffer.  Check that Get(int) works on very deep stacks
 // of ConsStrings.  These operations may not be very fast, but they
 // should be possible without getting errors due to too deep recursion.
 
 #include <stdlib.h>
 
 #include "v8.h"
@@ skipping 67 matching lines @@
     v8::HandleScope scope;
     const char* extensions[] = { "v8/print" };
     v8::ExtensionConfiguration config(1, extensions);
     env = v8::Context::New(&config);
   }
   v8::HandleScope scope;
   env->Enter();
 }
 
 
-static const int NUMBER_OF_BUILDING_BLOCKS = 256;
 static const int DEEP_DEPTH = 8 * 1024;
 static const int SUPER_DEEP_DEPTH = 80 * 1024;
 
 
 class Resource: public v8::String::ExternalStringResource,
                 public ZoneObject {
  public:
   explicit Resource(Vector<const uc16> string): data_(string.start()) {
     length_ = string.length();
   }
@@ skipping 85 matching lines @@
         Resource* resource = new(zone) Resource(Vector<const uc16>(buf, len));
         building_blocks[i] = FACTORY->NewExternalStringFromTwoByte(resource);
         for (int j = 0; j < len; j++) {
           CHECK_EQ(buf[j], building_blocks[i]->Get(j));
         }
         break;
       }
       case 3: {
         char* buf = zone->NewArray<char>(len);
         for (int j = 0; j < len; j++) {
-          buf[j] = rng->next(128);
+          buf[j] = rng->next(0x80);
         }
         AsciiResource* resource =
             new(zone) AsciiResource(Vector<const char>(buf, len));
         building_blocks[i] = FACTORY->NewExternalStringFromAscii(resource);
         for (int j = 0; j < len; j++) {
           CHECK_EQ(buf[j], building_blocks[i]->Get(j));
         }
         break;
       }
     }
     for (int j = slice_depth; j > 0; j--) {
       building_blocks[i] = FACTORY->NewSubString(
           building_blocks[i],
           slice_head_chars,
           building_blocks[i]->length() - slice_tail_chars);
     }
     CHECK(len == building_blocks[i]->length() + slice_length);
   }
 }
 
 
-static Handle<String> ConstructLeft(
-    Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
-    int depth) {
-  Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
-  for (int i = 0; i < depth; i++) {
-    answer = FACTORY->NewConsString(
-        answer,
-        building_blocks[i % NUMBER_OF_BUILDING_BLOCKS]);
-  }
-  return answer;
-}
-
-
-static Handle<String> ConstructRight(
-    Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
-    int depth) {
-  Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
-  for (int i = depth - 1; i >= 0; i--) {
-    answer = FACTORY->NewConsString(
-        building_blocks[i % NUMBER_OF_BUILDING_BLOCKS],
-        answer);
-  }
-  return answer;
-}
-
-
-static Handle<String> ConstructBalancedHelper(
-    Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
-    int from,
-    int to) {
-  CHECK(to > from);
-  if (to - from == 1) {
-    return building_blocks[from % NUMBER_OF_BUILDING_BLOCKS];
-  }
-  if (to - from == 2) {
-    return FACTORY->NewConsString(
-        building_blocks[from % NUMBER_OF_BUILDING_BLOCKS],
-        building_blocks[(from+1) % NUMBER_OF_BUILDING_BLOCKS]);
-  }
-  Handle<String> part1 =
-    ConstructBalancedHelper(building_blocks, from, from + ((to - from) / 2));
-  Handle<String> part2 =
-    ConstructBalancedHelper(building_blocks, from + ((to - from) / 2), to);
-  return FACTORY->NewConsString(part1, part2);
-}
-
-
-static Handle<String> ConstructBalanced(
-    Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS]) {
-  return ConstructBalancedHelper(building_blocks, 0, DEEP_DEPTH);
-}
-
-
-static StringInputBuffer buffer;
-static ConsStringIteratorOp cons_string_iterator_op_1;
-static ConsStringIteratorOp cons_string_iterator_op_2;
-
-static void Traverse(Handle<String> s1, Handle<String> s2) {
-  int i = 0;
-  buffer.Reset(*s1);
-  StringCharacterStream character_stream_1(*s1, 0, &cons_string_iterator_op_1);
-  StringCharacterStream character_stream_2(*s2, 0, &cons_string_iterator_op_2);
-  StringInputBuffer buffer2(*s2);
-  while (buffer.has_more()) {
-    CHECK(buffer2.has_more());
-    CHECK(character_stream_1.HasMore());
-    CHECK(character_stream_2.HasMore());
-    uint16_t c = buffer.GetNext();
-    CHECK_EQ(c, buffer2.GetNext());
-    CHECK_EQ(c, character_stream_1.GetNext());
-    CHECK_EQ(c, character_stream_2.GetNext());
-    i++;
-  }
-  CHECK(!character_stream_1.HasMore());
-  CHECK(!character_stream_2.HasMore());
-  CHECK_EQ(s1->length(), i);
-  CHECK_EQ(s2->length(), i);
-}
-
-
-static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars) {
-  int i = 0;
-  buffer.Reset(*s1);
-  StringInputBuffer buffer2(*s2);
-  StringCharacterStream character_stream_1(*s1, 0, &cons_string_iterator_op_1);
-  StringCharacterStream character_stream_2(*s2, 0, &cons_string_iterator_op_2);
-  while (buffer.has_more() && i < chars) {
-    CHECK(buffer2.has_more());
-    CHECK(character_stream_1.HasMore());
-    CHECK(character_stream_2.HasMore());
-    uint16_t c = buffer.GetNext();
-    CHECK_EQ(c, buffer2.GetNext());
-    CHECK_EQ(c, character_stream_1.GetNext());
-    CHECK_EQ(c, character_stream_2.GetNext());
-    i++;
-  }
-  s1->Get(s1->length() - 1);
-  s2->Get(s2->length() - 1);
-}
-
-
-TEST(Traverse) {
-  printf("TestTraverse\n");
-  InitializeVM();
-  v8::HandleScope scope;
-  Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS];
-  ZoneScope zone(Isolate::Current()->runtime_zone(), DELETE_ON_EXIT);
-  RandomNumberGenerator rng;
-  rng.init();
-  InitializeBuildingBlocks(
-      building_blocks, NUMBER_OF_BUILDING_BLOCKS, false, &rng);
-  Handle<String> flat = ConstructBalanced(building_blocks);
-  FlattenString(flat);
-  Handle<String> left_asymmetric = ConstructLeft(building_blocks, DEEP_DEPTH);
-  Handle<String> right_asymmetric = ConstructRight(building_blocks, DEEP_DEPTH);
-  Handle<String> symmetric = ConstructBalanced(building_blocks);
-  printf("1\n");
-  Traverse(flat, symmetric);
-  printf("2\n");
-  Traverse(flat, left_asymmetric);
-  printf("3\n");
-  Traverse(flat, right_asymmetric);
-  printf("4\n");
-  Handle<String> left_deep_asymmetric =
-      ConstructLeft(building_blocks, SUPER_DEEP_DEPTH);
-  Handle<String> right_deep_asymmetric =
-      ConstructRight(building_blocks, SUPER_DEEP_DEPTH);
-  printf("5\n");
-  TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
-  printf("6\n");
-  TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
-  printf("7\n");
-  FlattenString(left_asymmetric);
-  printf("10\n");
-  Traverse(flat, left_asymmetric);
-  printf("11\n");
-  FlattenString(right_asymmetric);
-  printf("12\n");
-  Traverse(flat, right_asymmetric);
-  printf("14\n");
-  FlattenString(symmetric);
-  printf("15\n");
-  Traverse(flat, symmetric);
-  printf("16\n");
-  FlattenString(left_deep_asymmetric);
-  printf("18\n");
-}
-
-
 class ConsStringStats {
  public:
   ConsStringStats() {
     Reset();
   }
   void Reset();
   void VerifyEqual(const ConsStringStats& that) const;
   unsigned leaves_;
   unsigned empty_leaves_;
   unsigned chars_;
@@ skipping 17 matching lines @@
   CHECK(this->leaves_ == that.leaves_);
   CHECK(this->empty_leaves_ == that.empty_leaves_);
   CHECK(this->chars_ == that.chars_);
   CHECK(this->left_traversals_ == that.left_traversals_);
   CHECK(this->right_traversals_ == that.right_traversals_);
 }
 
 
 class ConsStringGenerationData {
  public:
-  ConsStringGenerationData();
+  static const int kNumberOfBuildingBlocks = 256;
+  explicit ConsStringGenerationData(bool long_blocks);
   void Reset();
+  inline Handle<String> block(int offset);
+  inline Handle<String> block(uint32_t offset);
   // Input variables.
   double early_termination_threshold_;
   double leftness_;
   double rightness_;
   double empty_leaf_threshold_;
   unsigned max_leaves_;
   // Cached data.
-  Handle<String> building_blocks_[NUMBER_OF_BUILDING_BLOCKS];
+  Handle<String> building_blocks_[kNumberOfBuildingBlocks];
   String* empty_string_;
   RandomNumberGenerator rng_;
   // Stats.
   ConsStringStats stats_;
   unsigned early_terminations_;
  private:
   DISALLOW_COPY_AND_ASSIGN(ConsStringGenerationData);
 };
 
 
-ConsStringGenerationData::ConsStringGenerationData() {
+ConsStringGenerationData::ConsStringGenerationData(bool long_blocks) {
   rng_.init();
   InitializeBuildingBlocks(
-      building_blocks_, NUMBER_OF_BUILDING_BLOCKS, true, &rng_);
+      building_blocks_, kNumberOfBuildingBlocks, long_blocks, &rng_);
   empty_string_ = Isolate::Current()->heap()->empty_string();
   Reset();
 }
 
 
+Handle<String> ConsStringGenerationData::block(uint32_t offset) {
+  return building_blocks_[offset % kNumberOfBuildingBlocks ];
+}
+
+
+Handle<String> ConsStringGenerationData::block(int offset) {
+  CHECK_GE(offset, 0);
+  return building_blocks_[offset % kNumberOfBuildingBlocks];
+}
+
+
 void ConsStringGenerationData::Reset() {
   early_termination_threshold_ = 0.01;
   leftness_ = 0.75;
   rightness_ = 0.75;
   empty_leaf_threshold_ = 0.02;
   max_leaves_ = 1000;
   stats_.Reset();
   early_terminations_ = 0;
+  rng_.init();
 }
 
 
-void VerifyConsString(ConsString* cons_string, ConsStringStats* stats) {
+void AccumulateStats(ConsString* cons_string, ConsStringStats* stats) {
   int left_length = cons_string->first()->length();
   int right_length = cons_string->second()->length();
   CHECK(cons_string->length() == left_length + right_length);
   // Check left side.
-  if (cons_string->first()->IsConsString()) {
+  bool left_is_cons = cons_string->first()->IsConsString();
+  if (left_is_cons) {
     stats->left_traversals_++;
-    VerifyConsString(ConsString::cast(cons_string->first()), stats);
+    AccumulateStats(ConsString::cast(cons_string->first()), stats);
   } else {
     CHECK_NE(left_length, 0);
     stats->leaves_++;
     stats->chars_ += left_length;
   }
   // Check right side.
   if (cons_string->second()->IsConsString()) {
     stats->right_traversals_++;
-    VerifyConsString(ConsString::cast(cons_string->second()), stats);
+    AccumulateStats(ConsString::cast(cons_string->second()), stats);
   } else {
-    if (right_length == 0) stats->empty_leaves_++;
+    if (right_length == 0) {
+      stats->empty_leaves_++;
+      CHECK(!left_is_cons);
+    }
     stats->leaves_++;
     stats->chars_ += right_length;
   }
 }
 
 
-void VerifyConsStringWithOperator(
+void AccumulateStats(Handle<String> cons_string, ConsStringStats* stats) {
+  AssertNoAllocation no_alloc;
+  if (cons_string->IsConsString()) {
+    return AccumulateStats(ConsString::cast(*cons_string), stats);
+  }
+  // This string got flattened by gc.
+  stats->chars_ += cons_string->length();
+}
+
+
+void AccumulateStatsWithOperator(
     ConsString* cons_string, ConsStringStats* stats) {
   // Init op.
   ConsStringIteratorOp op;
   op.Reset();
   // Use response for initial search and on blown stack.
   ConsStringIteratorOp::ContinueResponse response;
   response.string_ = cons_string;
   response.offset_ = 0;
   response.type_ = cons_string->map()->instance_type();
   response.length_ = (uint32_t) cons_string->length();
@@ skipping 21 matching lines @@
   };
 }
 
 
 void VerifyConsString(Handle<String> root, ConsStringGenerationData* data) {
   // Verify basic data.
   CHECK(root->IsConsString());
   CHECK((unsigned)root->length() == data->stats_.chars_);
   // Recursive verify.
   ConsStringStats stats;
-  VerifyConsString(ConsString::cast(*root), &stats);
+  AccumulateStats(ConsString::cast(*root), &stats);
   stats.VerifyEqual(data->stats_);
   // Iteratively verify.
   stats.Reset();
-  VerifyConsStringWithOperator(ConsString::cast(*root), &stats);
+  AccumulateStatsWithOperator(ConsString::cast(*root), &stats);
   // Don't see these. Must copy over.
   stats.empty_leaves_ = data->stats_.empty_leaves_;
   stats.left_traversals_ = data->stats_.left_traversals_;
   stats.right_traversals_ = data->stats_.right_traversals_;
   // Adjust total leaves to compensate.
   stats.leaves_ += stats.empty_leaves_;
   stats.VerifyEqual(data->stats_);
 }
 
 
@@ skipping 11 matching lines @@
   // Cap for max leaves.
   terminate |= data->stats_.leaves_ >= data->max_leaves_;
   // Roll the dice.
   terminate |= terminate_early;
   // Compute termination characteristics for each side.
   bool terminate_left = terminate || !data->rng_.next(data->leftness_);
   bool terminate_right = terminate || !data->rng_.next(data->rightness_);
   // Generate left string.
   Handle<String> left;
   if (terminate_left) {
-    left = data->building_blocks_[data->rng_.next(NUMBER_OF_BUILDING_BLOCKS)];
+    left = data->block(data->rng_.next());
     data->stats_.leaves_++;
     data->stats_.chars_ += left->length();
   } else {
-    left = ConstructRandomString(data, max_recursion - 1);
     data->stats_.left_traversals_++;
   }
   // Generate right string.
   Handle<String> right;
   if (terminate_right) {
-    right = data->building_blocks_[data->rng_.next(NUMBER_OF_BUILDING_BLOCKS)];
+    right = data->block(data->rng_.next());
     data->stats_.leaves_++;
     data->stats_.chars_ += right->length();
   } else {
+    data->stats_.right_traversals_++;
+  }
+  // Generate the necessary sub-nodes recursively.
+  if (!terminate_right) {
+    // Need to balance generation fairly.
+    if (!terminate_left && data->rng_.next(0.5)) {
+      left = ConstructRandomString(data, max_recursion - 1);
+    }
     right = ConstructRandomString(data, max_recursion - 1);
-    data->stats_.right_traversals_++;
+  }
+  if (!terminate_left && left.is_null()) {
+    left = ConstructRandomString(data, max_recursion - 1);
   }
   // Build the cons string.
   Handle<String> root = FACTORY->NewConsString(left, right);
   CHECK(root->IsConsString() && !root->IsFlat());
   // Special work needed for flat string.
   if (flat) {
     data->stats_.empty_leaves_++;
     FlattenString(root);
     CHECK(root->IsConsString() && root->IsFlat());
   }
   return root;
 }
 
 
-static const int kCharacterStreamRandomCases = 150;
-static const int kCharacterStreamEdgeCases =
-    kCharacterStreamRandomCases + 5;
+static Handle<String> ConstructLeft(
+    ConsStringGenerationData* data,
+    int depth) {
+  Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
+  data->stats_.leaves_++;
+  for (int i = 0; i < depth; i++) {
+    Handle<String> block = data->block(i);
+    Handle<String> next = FACTORY->NewConsString(answer, block);
+    if (next->IsConsString()) data->stats_.leaves_++;
+    data->stats_.chars_ += block->length();
+    answer = next;
+  }
+  data->stats_.left_traversals_ = data->stats_.leaves_ - 2;
+  return answer;
+}
 
 
-static Handle<String> BuildConsStrings(int testCase,
-                                       ConsStringGenerationData* data) {
-  // For random constructions, need to reset the generator.
-  data->rng_.init();
-  for (int j = 0; j < testCase * 50; j++) {
-    data->rng_.next();
+static Handle<String> ConstructRight(
+    ConsStringGenerationData* data,
+    int depth) {
+  Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
+  data->stats_.leaves_++;
+  for (int i = depth - 1; i >= 0; i--) {
+    Handle<String> block = data->block(i);
+    Handle<String> next = FACTORY->NewConsString(block, answer);
+    if (next->IsConsString()) data->stats_.leaves_++;
+    data->stats_.chars_ += block->length();
+    answer = next;
   }
-  Handle<String> string;
-  switch (testCase) {
-    case 0:
-      return ConstructBalanced(data->building_blocks_);
-    case 1:
-      return ConstructLeft(data->building_blocks_, DEEP_DEPTH);
-    case 2:
-      return ConstructRight(data->building_blocks_, DEEP_DEPTH);
-    case 3:
-      return ConstructLeft(data->building_blocks_, 10);
-    case 4:
-      return ConstructRight(data->building_blocks_, 10);
-    case 5:
-      return FACTORY->NewConsString(
-          data->building_blocks_[0], data->building_blocks_[1]);
-    default:
-      if (testCase >= kCharacterStreamEdgeCases) {
-        CHECK(false);
-        return string;
-      }
-      // Random test case.
-      data->Reset();
-      string = ConstructRandomString(data, 200);
-      AssertNoAllocation no_alloc;
-      VerifyConsString(string, data);
-#ifdef DEBUG
-      printf(
-          "%s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d]\n",
-          "leaves", data->stats_.leaves_,
-          "empty", data->stats_.empty_leaves_,
-          "chars", data->stats_.chars_,
-          "lefts", data->stats_.left_traversals_,
-          "rights", data->stats_.right_traversals_,
-          "early_terminations", data->early_terminations_);
-#endif
-      return string;
-    }
+  data->stats_.right_traversals_ = data->stats_.leaves_ - 2;
+  return answer;
+}
+
+
+static Handle<String> ConstructBalancedHelper(
+    ConsStringGenerationData* data,
+    int from,
+    int to) {
+  CHECK(to > from);
+  if (to - from == 1) {
+    data->stats_.chars_ += data->block(from)->length();
+    return data->block(from);
+  }
+  if (to - from == 2) {
+    data->stats_.chars_ += data->block(from)->length();
+    data->stats_.chars_ += data->block(from+1)->length();
+    return FACTORY->NewConsString(data->block(from), data->block(from+1));
+  }
+  Handle<String> part1 =
+    ConstructBalancedHelper(data, from, from + ((to - from) / 2));
+  Handle<String> part2 =
+    ConstructBalancedHelper(data, from + ((to - from) / 2), to);
+  if (part1->IsConsString()) data->stats_.left_traversals_++;
+  if (part2->IsConsString()) data->stats_.right_traversals_++;
+  return FACTORY->NewConsString(part1, part2);
+}
+
+
+static Handle<String> ConstructBalanced(
+    ConsStringGenerationData* data, int depth = DEEP_DEPTH) {
+  Handle<String> string = ConstructBalancedHelper(data, 0, depth);
+  data->stats_.leaves_ =
+      data->stats_.left_traversals_ + data->stats_.right_traversals_ + 2;
+  return string;
+}
+
+
+static StringInputBuffer buffer;
+static ConsStringIteratorOp cons_string_iterator_op_1;
+static ConsStringIteratorOp cons_string_iterator_op_2;
+
+static void Traverse(Handle<String> s1, Handle<String> s2) {
+  int i = 0;
+  buffer.Reset(*s1);
+  StringCharacterStream character_stream_1(*s1, 0, &cons_string_iterator_op_1);
+  StringCharacterStream character_stream_2(*s2, 0, &cons_string_iterator_op_2);
+  StringInputBuffer buffer2(*s2);
+  while (buffer.has_more()) {
+    CHECK(buffer2.has_more());
+    CHECK(character_stream_1.HasMore());
+    CHECK(character_stream_2.HasMore());
+    uint16_t c = buffer.GetNext();
+    CHECK_EQ(c, buffer2.GetNext());
+    CHECK_EQ(c, character_stream_1.GetNext());
+    CHECK_EQ(c, character_stream_2.GetNext());
+    i++;
+  }
+  CHECK(!character_stream_1.HasMore());
+  CHECK(!character_stream_2.HasMore());
+  CHECK_EQ(s1->length(), i);
+  CHECK_EQ(s2->length(), i);
+}
+
+
+static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars) {
+  int i = 0;
+  buffer.Reset(*s1);
+  StringInputBuffer buffer2(*s2);
+  StringCharacterStream character_stream_1(*s1, 0, &cons_string_iterator_op_1);
+  StringCharacterStream character_stream_2(*s2, 0, &cons_string_iterator_op_2);
+  while (buffer.has_more() && i < chars) {
+    CHECK(buffer2.has_more());
+    CHECK(character_stream_1.HasMore());
+    CHECK(character_stream_2.HasMore());
+    uint16_t c = buffer.GetNext();
+    CHECK_EQ(c, buffer2.GetNext());
+    CHECK_EQ(c, character_stream_1.GetNext());
+    CHECK_EQ(c, character_stream_2.GetNext());
+    i++;
+  }
+  s1->Get(s1->length() - 1);
+  s2->Get(s2->length() - 1);
+}
+
+
+TEST(Traverse) {
+  printf("TestTraverse\n");
+  InitializeVM();
+  v8::HandleScope scope;
+  ZoneScope zone(Isolate::Current()->runtime_zone(), DELETE_ON_EXIT);
+  ConsStringGenerationData data(false);
+  Handle<String> flat = ConstructBalanced(&data);
+  FlattenString(flat);
+  Handle<String> left_asymmetric = ConstructLeft(&data, DEEP_DEPTH);
+  Handle<String> right_asymmetric = ConstructRight(&data, DEEP_DEPTH);
+  Handle<String> symmetric = ConstructBalanced(&data);
+  printf("1\n");
+  Traverse(flat, symmetric);
+  printf("2\n");
+  Traverse(flat, left_asymmetric);
+  printf("3\n");
+  Traverse(flat, right_asymmetric);
+  printf("4\n");
+  Handle<String> left_deep_asymmetric =
+      ConstructLeft(&data, SUPER_DEEP_DEPTH);
+  Handle<String> right_deep_asymmetric =
+      ConstructRight(&data, SUPER_DEEP_DEPTH);
+  printf("5\n");
+  TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
+  printf("6\n");
+  TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
+  printf("7\n");
+  FlattenString(left_asymmetric);
+  printf("10\n");
+  Traverse(flat, left_asymmetric);
+  printf("11\n");
+  FlattenString(right_asymmetric);
+  printf("12\n");
+  Traverse(flat, right_asymmetric);
+  printf("14\n");
+  FlattenString(symmetric);
+  printf("15\n");
+  Traverse(flat, symmetric);
+  printf("16\n");
+  FlattenString(left_deep_asymmetric);
+  printf("18\n");
 }
 
 
 static void VerifyCharacterStream(
     String* flat_string, String* cons_string) {
   // Do not want to test ConString traversal on flat string.
-  CHECK(flat_string->IsFlat());
-  CHECK(!flat_string->IsConsString());
+  CHECK(flat_string->IsFlat() && !flat_string->IsConsString());
   CHECK(cons_string->IsConsString());
   // TODO(dcarney) Test stream reset as well.
   int length = flat_string->length();
   // Iterate start search in multiple places in the string.
   int outer_iterations = length > 20 ? 20 : length;
   for (int j = 0; j <= outer_iterations; j++) {
     int offset = length * j / outer_iterations;
     if (offset < 0) offset = 0;
     // Want to test the offset == length case.
     if (offset > length) offset = length;
     StringCharacterStream flat_stream(
         flat_string, (unsigned) offset, &cons_string_iterator_op_1);
     StringCharacterStream cons_stream(
         cons_string, (unsigned) offset, &cons_string_iterator_op_2);
     for (int i = offset; i < length; i++) {
       uint16_t c = flat_string->Get(i);
       CHECK(flat_stream.HasMore());
       CHECK(cons_stream.HasMore());
       CHECK_EQ(c, flat_stream.GetNext());
       CHECK_EQ(c, cons_stream.GetNext());
     }
     CHECK(!flat_stream.HasMore());
     CHECK(!cons_stream.HasMore());
   }
 }
 
 
-TEST(StringCharacterStreamEdgeCases) {
-  printf("TestStringCharacterStreamEdgeCases\n");
+static inline void PrintStats(const ConsStringGenerationData& data) {
+#ifdef DEBUG
+printf(
+    "%s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d]\n",
+    "leaves", data.stats_.leaves_,
+    "empty", data.stats_.empty_leaves_,
+    "chars", data.stats_.chars_,
+    "lefts", data.stats_.left_traversals_,
+    "rights", data.stats_.right_traversals_,
+    "early_terminations", data.early_terminations_);
+#endif
+}
+
+
+template<typename BuildString>
+void TestStringCharacterStream(BuildString build, int test_cases) {
   InitializeVM();
   Isolate* isolate = Isolate::Current();
   HandleScope outer_scope(isolate);
   ZoneScope zone(Isolate::Current()->runtime_zone(), DELETE_ON_EXIT);
-  ConsStringGenerationData data;
-  for (int i = 0; i < kCharacterStreamEdgeCases; i++) {
+  ConsStringGenerationData data(true);
+  bool last_test_did_gc = false;
+  for (int i = 0; i < test_cases; i++) {
     printf("%d\n", i);
-    isolate->heap()->CollectAllGarbage(
-        Heap::kNoGCFlags, "must not allocate in loop");
-    AlwaysAllocateScope always_allocate;
     HandleScope inner_scope(isolate);
-    Handle<String> cons_string = BuildConsStrings(i, &data);
-    Handle<String> flat_string = BuildConsStrings(i, &data);
+    // Build flat version of cons string.
+    Handle<String> flat_string = build(i, &data);
+    ConsStringStats flat_string_stats;
+    AccumulateStats(flat_string, &flat_string_stats);
+    // Flatten string.
     FlattenString(flat_string);
+    // Build unflattened version of cons string to test.
+    Handle<String> cons_string = build(i, &data);
+    ConsStringStats cons_string_stats;
+    AccumulateStats(cons_string, &cons_string_stats);
+    // Check if gc changed our data structure.
+    bool broken_by_gc =
+        cons_string_stats.leaves_ != data.stats_.leaves_ ||
+        cons_string_stats.leaves_ != flat_string_stats.leaves_;
+    // If gc altered the data structure, do a full collection and retry test.
+    if (broken_by_gc) {
+      // Bail if test runs twice.
+      if (last_test_did_gc) CHECK(false);
+      printf("forcing gc\n");
+      isolate->heap()->CollectAllGarbage(Heap::kNoGCFlags, "retry test");
+      // Retry test.
+      last_test_did_gc = true;
+      i--;
+      continue;
+    }
+    last_test_did_gc = false;
     AssertNoAllocation no_alloc;
-    CHECK(flat_string->IsConsString() && flat_string->IsFlat());
-    VerifyCharacterStream(ConsString::cast(*flat_string)->first(),
-        *cons_string);
-  }
+    PrintStats(data);
+    // Full verify of cons string.
+    cons_string_stats.VerifyEqual(flat_string_stats);
+    cons_string_stats.VerifyEqual(data.stats_);
+    VerifyConsString(cons_string, &data);
+    String* flat_string_ptr =
+        flat_string->IsConsString() ?
+        ConsString::cast(*flat_string)->first() :
+        *flat_string;
+    VerifyCharacterStream(flat_string_ptr, *cons_string);
+  }
+}
+
+
+static const int kCharacterStreamNonRandomCases = 8;
+
+
+static Handle<String> BuildEdgeCaseConsString(
+    int test_case, ConsStringGenerationData* data) {
+  data->Reset();
+  switch (test_case) {
+    case 0:
+      return ConstructBalanced(data, 71);
+    case 1:
+      return ConstructLeft(data, 71);
+    case 2:
+      return ConstructRight(data, 71);
+    case 3:
+      return ConstructLeft(data, 10);
+    case 4:
+      return ConstructRight(data, 10);
+    case 5:
+      // 2 element balanced tree.
+      data->stats_.chars_ += data->block(0)->length();
+      data->stats_.chars_ += data->block(1)->length();
+      data->stats_.leaves_ += 2;
+      return FACTORY->NewConsString(data->block(0), data->block(1));
+    case 6:
+      // Simple flattened tree.
+      data->stats_.chars_ += data->block(0)->length();
+      data->stats_.chars_ += data->block(1)->length();
+      data->stats_.leaves_ += 2;
+      data->stats_.empty_leaves_ += 1;
+      {
+        Handle<String> string =
+            FACTORY->NewConsString(data->block(0), data->block(1));
+        FlattenString(string);
+        return string;
+      }
+    case 7:
+      // Left node flattened.
+      data->stats_.chars_ += data->block(0)->length();
+      data->stats_.chars_ += data->block(1)->length();
+      data->stats_.chars_ += data->block(2)->length();
+      data->stats_.leaves_ += 3;
+      data->stats_.empty_leaves_ += 1;
+      data->stats_.left_traversals_ += 1;
+      {
+        Handle<String> left =
+            FACTORY->NewConsString(data->block(0), data->block(1));
+        FlattenString(left);
+        return FACTORY->NewConsString(left, data->block(2));
+      }
+    case 8:
+      // Left node and right node flattened.
+      data->stats_.chars_ += data->block(0)->length();
+      data->stats_.chars_ += data->block(1)->length();
+      data->stats_.chars_ += data->block(2)->length();
+      data->stats_.chars_ += data->block(3)->length();
+      data->stats_.leaves_ += 4;
+      data->stats_.empty_leaves_ += 2;
+      data->stats_.left_traversals_ += 1;
+      data->stats_.right_traversals_ += 1;
+      {
+        Handle<String> left =
+            FACTORY->NewConsString(data->block(0), data->block(1));
+        FlattenString(left);
+        Handle<String> right =
+            FACTORY->NewConsString(data->block(2), data->block(2));
+        FlattenString(right);
+        return FACTORY->NewConsString(left, right);
+      }
+  }
+  UNREACHABLE();
+  return Handle<String>();
+}
+
+
+TEST(StringCharacterStreamEdgeCases) {
+  printf("TestStringCharacterStreamEdgeCases\n");
+  TestStringCharacterStream(
+      BuildEdgeCaseConsString, kCharacterStreamNonRandomCases);
+}
+
+
+static const int kBalances = 3;
+static const int kTreeLengths = 4;
+static const int kEmptyLeaves = 4;
+static const int kUniqueRandomParameters =
+    kBalances*kTreeLengths*kEmptyLeaves;
+
+
+static void InitializeGenerationData(
+    int test_case, ConsStringGenerationData* data) {
+  // Clear the settings and reinit the rng.
+  data->Reset();
+  // Spin up the rng to a known location that is unique per test.
+  static const int kPerTestJump = 501;
+  for (int j = 0; j < test_case*kPerTestJump; j++) {
+    data->rng_.next();
+  }
+  // Choose balanced, left or right heavy trees.
+  switch (test_case % kBalances) {
+    case 0:
+      // Nothing to do.  Already balanced.
+      break;
+    case 1:
+      // Left balanced.
+      data->leftness_ = 0.90;
+      data->rightness_ = 0.15;
+      break;
+    case 2:
+      // Right balanced.
+      data->leftness_ = 0.15;
+      data->rightness_ = 0.90;
+      break;
+    default:
+      UNREACHABLE();
+      break;
+  }
+  // Must remove the influence of the above decision.
+  test_case /= kBalances;
+  // Choose tree length.
+  switch (test_case % kTreeLengths) {
+    case 0:
+      data->max_leaves_ = 16;
+      data->early_termination_threshold_ = 0.2;
+      break;
+    case 1:
+      data->max_leaves_ = 50;
+      data->early_termination_threshold_ = 0.05;
+      break;
+    case 2:
+      data->max_leaves_ = 500;
+      data->early_termination_threshold_ = 0.03;
+      break;
+    case 3:
+      data->max_leaves_ = 5000;
+      data->early_termination_threshold_ = 0.001;
+      break;
+    default:
+      UNREACHABLE();
+      break;
+  }
+  // Must remove the influence of the above decision.
+  test_case /= kTreeLengths;
+  // Choose how much we allow empty nodes, including not at all.
+  data->empty_leaf_threshold_ =
+      0.03 * static_cast<double>(test_case % kEmptyLeaves);
+}
+
+
+static Handle<String> BuildRandomConsString(
+    int test_case, ConsStringGenerationData* data) {
+  InitializeGenerationData(test_case, data);
+  return ConstructRandomString(data, 200);
+}
+
+
+TEST(StringCharacterStreamRandom) {

[Michael Starzinger, 2012/12/14 09:23:07]

This test is failing on the GC Stress builder.

http://build.chromium.org/p/client.v8/builders/V8%20GC%20Stress%20-%201/build...

+  printf("StringCharacterStreamRandom\n");
+  TestStringCharacterStream(BuildRandomConsString, kUniqueRandomParameters*7);
 }
 
 
 static const int DEEP_ASCII_DEPTH = 100000;
 
 
 TEST(DeepAscii) {
   printf("TestDeepAscii\n");
   InitializeVM();
   v8::HandleScope scope;
@@ skipping 423 matching lines @@
 
   v8::Local<v8::String> expected = v8_str("ascii\x80only\x80string\x80");
   CHECK(expected->Equals(result));
 }
 
 
 TEST(IsAscii) {
   CHECK(String::IsAscii(static_cast<char*>(NULL), 0));
   CHECK(String::IsAscii(static_cast<uc16*>(NULL), 0));
 }