Home | History | Annotate | Download | only in cctest
      1 // Copyright 2012 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 // Check that we can traverse very deep stacks of ConsStrings using
     29 // StringCharacterStram.  Check that Get(int) works on very deep stacks
     30 // of ConsStrings.  These operations may not be very fast, but they
     31 // should be possible without getting errors due to too deep recursion.
     32 
     33 #include <stdlib.h>
     34 
     35 #include "v8.h"
     36 
     37 #include "api.h"
     38 #include "factory.h"
     39 #include "objects.h"
     40 #include "cctest.h"
     41 #include "zone-inl.h"
     42 
     43 // Adapted from http://en.wikipedia.org/wiki/Multiply-with-carry
     44 class MyRandomNumberGenerator {
     45  public:
     46   MyRandomNumberGenerator() {
     47     init();
     48   }
     49 
     50   void init(uint32_t seed = 0x5688c73e) {
     51     static const uint32_t phi = 0x9e3779b9;
     52     c = 362436;
     53     i = kQSize-1;
     54     Q[0] = seed;
     55     Q[1] = seed + phi;
     56     Q[2] = seed + phi + phi;
     57     for (unsigned j = 3; j < kQSize; j++) {
     58       Q[j] = Q[j - 3] ^ Q[j - 2] ^ phi ^ j;
     59     }
     60   }
     61 
     62   uint32_t next() {
     63     uint64_t a = 18782;
     64     uint32_t r = 0xfffffffe;
     65     i = (i + 1) & (kQSize-1);
     66     uint64_t t = a * Q[i] + c;
     67     c = (t >> 32);
     68     uint32_t x = static_cast<uint32_t>(t + c);
     69     if (x < c) {
     70       x++;
     71       c++;
     72     }
     73     return (Q[i] = r - x);
     74   }
     75 
     76   uint32_t next(int max) {
     77     return next() % max;
     78   }
     79 
     80   bool next(double threshold) {
     81     ASSERT(threshold >= 0.0 && threshold <= 1.0);
     82     if (threshold == 1.0) return true;
     83     if (threshold == 0.0) return false;
     84     uint32_t value = next() % 100000;
     85     return threshold > static_cast<double>(value)/100000.0;
     86   }
     87 
     88  private:
     89   static const uint32_t kQSize = 4096;
     90   uint32_t Q[kQSize];
     91   uint32_t c;
     92   uint32_t i;
     93 };
     94 
     95 
     96 using namespace v8::internal;
     97 
     98 
     99 static const int DEEP_DEPTH = 8 * 1024;
    100 static const int SUPER_DEEP_DEPTH = 80 * 1024;
    101 
    102 
    103 class Resource: public v8::String::ExternalStringResource,
    104                 public ZoneObject {
    105  public:
    106   explicit Resource(Vector<const uc16> string): data_(string.start()) {
    107     length_ = string.length();
    108   }
    109   virtual const uint16_t* data() const { return data_; }
    110   virtual size_t length() const { return length_; }
    111 
    112  private:
    113   const uc16* data_;
    114   size_t length_;
    115 };
    116 
    117 
    118 class AsciiResource: public v8::String::ExternalAsciiStringResource,
    119                 public ZoneObject {
    120  public:
    121   explicit AsciiResource(Vector<const char> string): data_(string.start()) {
    122     length_ = string.length();
    123   }
    124   virtual const char* data() const { return data_; }
    125   virtual size_t length() const { return length_; }
    126 
    127  private:
    128   const char* data_;
    129   size_t length_;
    130 };
    131 
    132 
    133 static void InitializeBuildingBlocks(Handle<String>* building_blocks,
    134                                      int bb_length,
    135                                      bool long_blocks,
    136                                      MyRandomNumberGenerator* rng,
    137                                      Zone* zone) {
    138   // A list of pointers that we don't have any interest in cleaning up.
    139   // If they are reachable from a root then leak detection won't complain.
    140   Isolate* isolate = CcTest::i_isolate();
    141   Factory* factory = isolate->factory();
    142   for (int i = 0; i < bb_length; i++) {
    143     int len = rng->next(16);
    144     int slice_head_chars = 0;
    145     int slice_tail_chars = 0;
    146     int slice_depth = 0;
    147     for (int j = 0; j < 3; j++) {
    148       if (rng->next(0.35)) slice_depth++;
    149     }
    150     // Must truncate something for a slice string. Loop until
    151     // at least one end will be sliced.
    152     while (slice_head_chars == 0 && slice_tail_chars == 0) {
    153       slice_head_chars = rng->next(15);
    154       slice_tail_chars = rng->next(12);
    155     }
    156     if (long_blocks) {
    157       // Generate building blocks which will never be merged
    158       len += ConsString::kMinLength + 1;
    159     } else if (len > 14) {
    160       len += 1234;
    161     }
    162     // Don't slice 0 length strings.
    163     if (len == 0) slice_depth = 0;
    164     int slice_length = slice_depth*(slice_head_chars + slice_tail_chars);
    165     len += slice_length;
    166     switch (rng->next(4)) {
    167       case 0: {
    168         uc16 buf[2000];
    169         for (int j = 0; j < len; j++) {
    170           buf[j] = rng->next(0x10000);
    171         }
    172         building_blocks[i] =
    173             factory->NewStringFromTwoByte(Vector<const uc16>(buf, len));
    174         for (int j = 0; j < len; j++) {
    175           CHECK_EQ(buf[j], building_blocks[i]->Get(j));
    176         }
    177         break;
    178       }
    179       case 1: {
    180         char buf[2000];
    181         for (int j = 0; j < len; j++) {
    182           buf[j] = rng->next(0x80);
    183         }
    184         building_blocks[i] =
    185             factory->NewStringFromAscii(Vector<const char>(buf, len));
    186         for (int j = 0; j < len; j++) {
    187           CHECK_EQ(buf[j], building_blocks[i]->Get(j));
    188         }
    189         break;
    190       }
    191       case 2: {
    192         uc16* buf = zone->NewArray<uc16>(len);
    193         for (int j = 0; j < len; j++) {
    194           buf[j] = rng->next(0x10000);
    195         }
    196         Resource* resource = new(zone) Resource(Vector<const uc16>(buf, len));
    197         building_blocks[i] = factory->NewExternalStringFromTwoByte(resource);
    198         for (int j = 0; j < len; j++) {
    199           CHECK_EQ(buf[j], building_blocks[i]->Get(j));
    200         }
    201         break;
    202       }
    203       case 3: {
    204         char* buf = zone->NewArray<char>(len);
    205         for (int j = 0; j < len; j++) {
    206           buf[j] = rng->next(0x80);
    207         }
    208         AsciiResource* resource =
    209             new(zone) AsciiResource(Vector<const char>(buf, len));
    210         building_blocks[i] = factory->NewExternalStringFromAscii(resource);
    211         for (int j = 0; j < len; j++) {
    212           CHECK_EQ(buf[j], building_blocks[i]->Get(j));
    213         }
    214         break;
    215       }
    216     }
    217     for (int j = slice_depth; j > 0; j--) {
    218       building_blocks[i] = factory->NewSubString(
    219           building_blocks[i],
    220           slice_head_chars,
    221           building_blocks[i]->length() - slice_tail_chars);
    222     }
    223     CHECK(len == building_blocks[i]->length() + slice_length);
    224   }
    225 }
    226 
    227 
    228 class ConsStringStats {
    229  public:
    230   ConsStringStats() {
    231     Reset();
    232   }
    233   void Reset();
    234   void VerifyEqual(const ConsStringStats& that) const;
    235   unsigned leaves_;
    236   unsigned empty_leaves_;
    237   unsigned chars_;
    238   unsigned left_traversals_;
    239   unsigned right_traversals_;
    240  private:
    241   DISALLOW_COPY_AND_ASSIGN(ConsStringStats);
    242 };
    243 
    244 
    245 void ConsStringStats::Reset() {
    246   leaves_ = 0;
    247   empty_leaves_ = 0;
    248   chars_ = 0;
    249   left_traversals_ = 0;
    250   right_traversals_ = 0;
    251 }
    252 
    253 
    254 void ConsStringStats::VerifyEqual(const ConsStringStats& that) const {
    255   CHECK(this->leaves_ == that.leaves_);
    256   CHECK(this->empty_leaves_ == that.empty_leaves_);
    257   CHECK(this->chars_ == that.chars_);
    258   CHECK(this->left_traversals_ == that.left_traversals_);
    259   CHECK(this->right_traversals_ == that.right_traversals_);
    260 }
    261 
    262 
    263 class ConsStringGenerationData {
    264  public:
    265   static const int kNumberOfBuildingBlocks = 256;
    266   ConsStringGenerationData(bool long_blocks, Zone* zone);
    267   void Reset();
    268   inline Handle<String> block(int offset);
    269   inline Handle<String> block(uint32_t offset);
    270   // Input variables.
    271   double early_termination_threshold_;
    272   double leftness_;
    273   double rightness_;
    274   double empty_leaf_threshold_;
    275   unsigned max_leaves_;
    276   // Cached data.
    277   Handle<String> building_blocks_[kNumberOfBuildingBlocks];
    278   String* empty_string_;
    279   MyRandomNumberGenerator rng_;
    280   // Stats.
    281   ConsStringStats stats_;
    282   unsigned early_terminations_;
    283  private:
    284   DISALLOW_COPY_AND_ASSIGN(ConsStringGenerationData);
    285 };
    286 
    287 
    288 ConsStringGenerationData::ConsStringGenerationData(bool long_blocks,
    289                                                    Zone* zone) {
    290   rng_.init();
    291   InitializeBuildingBlocks(
    292       building_blocks_, kNumberOfBuildingBlocks, long_blocks, &rng_, zone);
    293   empty_string_ = CcTest::heap()->empty_string();
    294   Reset();
    295 }
    296 
    297 
    298 Handle<String> ConsStringGenerationData::block(uint32_t offset) {
    299   return building_blocks_[offset % kNumberOfBuildingBlocks ];
    300 }
    301 
    302 
    303 Handle<String> ConsStringGenerationData::block(int offset) {
    304   CHECK_GE(offset, 0);
    305   return building_blocks_[offset % kNumberOfBuildingBlocks];
    306 }
    307 
    308 
    309 void ConsStringGenerationData::Reset() {
    310   early_termination_threshold_ = 0.01;
    311   leftness_ = 0.75;
    312   rightness_ = 0.75;
    313   empty_leaf_threshold_ = 0.02;
    314   max_leaves_ = 1000;
    315   stats_.Reset();
    316   early_terminations_ = 0;
    317   rng_.init();
    318 }
    319 
    320 
    321 void AccumulateStats(ConsString* cons_string, ConsStringStats* stats) {
    322   int left_length = cons_string->first()->length();
    323   int right_length = cons_string->second()->length();
    324   CHECK(cons_string->length() == left_length + right_length);
    325   // Check left side.
    326   bool left_is_cons = cons_string->first()->IsConsString();
    327   if (left_is_cons) {
    328     stats->left_traversals_++;
    329     AccumulateStats(ConsString::cast(cons_string->first()), stats);
    330   } else {
    331     CHECK_NE(left_length, 0);
    332     stats->leaves_++;
    333     stats->chars_ += left_length;
    334   }
    335   // Check right side.
    336   if (cons_string->second()->IsConsString()) {
    337     stats->right_traversals_++;
    338     AccumulateStats(ConsString::cast(cons_string->second()), stats);
    339   } else {
    340     if (right_length == 0) {
    341       stats->empty_leaves_++;
    342       CHECK(!left_is_cons);
    343     }
    344     stats->leaves_++;
    345     stats->chars_ += right_length;
    346   }
    347 }
    348 
    349 
    350 void AccumulateStats(Handle<String> cons_string, ConsStringStats* stats) {
    351   DisallowHeapAllocation no_allocation;
    352   if (cons_string->IsConsString()) {
    353     return AccumulateStats(ConsString::cast(*cons_string), stats);
    354   }
    355   // This string got flattened by gc.
    356   stats->chars_ += cons_string->length();
    357 }
    358 
    359 
    360 void AccumulateStatsWithOperator(
    361     ConsString* cons_string, ConsStringStats* stats) {
    362   unsigned offset = 0;
    363   int32_t type = cons_string->map()->instance_type();
    364   unsigned length = static_cast<unsigned>(cons_string->length());
    365   ConsStringIteratorOp op;
    366   String* string = op.Operate(cons_string, &offset, &type, &length);
    367   CHECK(string != NULL);
    368   while (true) {
    369     ASSERT(!string->IsConsString());
    370     // Accumulate stats.
    371     stats->leaves_++;
    372     stats->chars_ += string->length();
    373     // Check for completion.
    374     bool keep_going_fast_check = op.HasMore();
    375     string = op.ContinueOperation(&type, &length);
    376     if (string == NULL) return;
    377     // Verify no false positives for fast check.
    378     CHECK(keep_going_fast_check);
    379   }
    380 }
    381 
    382 
    383 void VerifyConsString(Handle<String> root, ConsStringGenerationData* data) {
    384   // Verify basic data.
    385   CHECK(root->IsConsString());
    386   CHECK(static_cast<unsigned>(root->length()) == data->stats_.chars_);
    387   // Recursive verify.
    388   ConsStringStats stats;
    389   AccumulateStats(ConsString::cast(*root), &stats);
    390   stats.VerifyEqual(data->stats_);
    391   // Iteratively verify.
    392   stats.Reset();
    393   AccumulateStatsWithOperator(ConsString::cast(*root), &stats);
    394   // Don't see these. Must copy over.
    395   stats.empty_leaves_ = data->stats_.empty_leaves_;
    396   stats.left_traversals_ = data->stats_.left_traversals_;
    397   stats.right_traversals_ = data->stats_.right_traversals_;
    398   // Adjust total leaves to compensate.
    399   stats.leaves_ += stats.empty_leaves_;
    400   stats.VerifyEqual(data->stats_);
    401 }
    402 
    403 
    404 static Handle<String> ConstructRandomString(ConsStringGenerationData* data,
    405                                             unsigned max_recursion) {
    406   Factory* factory = CcTest::i_isolate()->factory();
    407   // Compute termination characteristics.
    408   bool terminate = false;
    409   bool flat = data->rng_.next(data->empty_leaf_threshold_);
    410   bool terminate_early = data->rng_.next(data->early_termination_threshold_);
    411   if (terminate_early) data->early_terminations_++;
    412   // The obvious condition.
    413   terminate |= max_recursion == 0;
    414   // Flat cons string terminate by definition.
    415   terminate |= flat;
    416   // Cap for max leaves.
    417   terminate |= data->stats_.leaves_ >= data->max_leaves_;
    418   // Roll the dice.
    419   terminate |= terminate_early;
    420   // Compute termination characteristics for each side.
    421   bool terminate_left = terminate || !data->rng_.next(data->leftness_);
    422   bool terminate_right = terminate || !data->rng_.next(data->rightness_);
    423   // Generate left string.
    424   Handle<String> left;
    425   if (terminate_left) {
    426     left = data->block(data->rng_.next());
    427     data->stats_.leaves_++;
    428     data->stats_.chars_ += left->length();
    429   } else {
    430     data->stats_.left_traversals_++;
    431   }
    432   // Generate right string.
    433   Handle<String> right;
    434   if (terminate_right) {
    435     right = data->block(data->rng_.next());
    436     data->stats_.leaves_++;
    437     data->stats_.chars_ += right->length();
    438   } else {
    439     data->stats_.right_traversals_++;
    440   }
    441   // Generate the necessary sub-nodes recursively.
    442   if (!terminate_right) {
    443     // Need to balance generation fairly.
    444     if (!terminate_left && data->rng_.next(0.5)) {
    445       left = ConstructRandomString(data, max_recursion - 1);
    446     }
    447     right = ConstructRandomString(data, max_recursion - 1);
    448   }
    449   if (!terminate_left && left.is_null()) {
    450     left = ConstructRandomString(data, max_recursion - 1);
    451   }
    452   // Build the cons string.
    453   Handle<String> root = factory->NewConsString(left, right);
    454   CHECK(root->IsConsString() && !root->IsFlat());
    455   // Special work needed for flat string.
    456   if (flat) {
    457     data->stats_.empty_leaves_++;
    458     FlattenString(root);
    459     CHECK(root->IsConsString() && root->IsFlat());
    460   }
    461   return root;
    462 }
    463 
    464 
    465 static Handle<String> ConstructLeft(
    466     ConsStringGenerationData* data,
    467     int depth) {
    468   Factory* factory = CcTest::i_isolate()->factory();
    469   Handle<String> answer = factory->NewStringFromAscii(CStrVector(""));
    470   data->stats_.leaves_++;
    471   for (int i = 0; i < depth; i++) {
    472     Handle<String> block = data->block(i);
    473     Handle<String> next = factory->NewConsString(answer, block);
    474     if (next->IsConsString()) data->stats_.leaves_++;
    475     data->stats_.chars_ += block->length();
    476     answer = next;
    477   }
    478   data->stats_.left_traversals_ = data->stats_.leaves_ - 2;
    479   return answer;
    480 }
    481 
    482 
    483 static Handle<String> ConstructRight(
    484     ConsStringGenerationData* data,
    485     int depth) {
    486   Factory* factory = CcTest::i_isolate()->factory();
    487   Handle<String> answer = factory->NewStringFromAscii(CStrVector(""));
    488   data->stats_.leaves_++;
    489   for (int i = depth - 1; i >= 0; i--) {
    490     Handle<String> block = data->block(i);
    491     Handle<String> next = factory->NewConsString(block, answer);
    492     if (next->IsConsString()) data->stats_.leaves_++;
    493     data->stats_.chars_ += block->length();
    494     answer = next;
    495   }
    496   data->stats_.right_traversals_ = data->stats_.leaves_ - 2;
    497   return answer;
    498 }
    499 
    500 
    501 static Handle<String> ConstructBalancedHelper(
    502     ConsStringGenerationData* data,
    503     int from,
    504     int to) {
    505   Factory* factory = CcTest::i_isolate()->factory();
    506   CHECK(to > from);
    507   if (to - from == 1) {
    508     data->stats_.chars_ += data->block(from)->length();
    509     return data->block(from);
    510   }
    511   if (to - from == 2) {
    512     data->stats_.chars_ += data->block(from)->length();
    513     data->stats_.chars_ += data->block(from+1)->length();
    514     return factory->NewConsString(data->block(from), data->block(from+1));
    515   }
    516   Handle<String> part1 =
    517     ConstructBalancedHelper(data, from, from + ((to - from) / 2));
    518   Handle<String> part2 =
    519     ConstructBalancedHelper(data, from + ((to - from) / 2), to);
    520   if (part1->IsConsString()) data->stats_.left_traversals_++;
    521   if (part2->IsConsString()) data->stats_.right_traversals_++;
    522   return factory->NewConsString(part1, part2);
    523 }
    524 
    525 
    526 static Handle<String> ConstructBalanced(
    527     ConsStringGenerationData* data, int depth = DEEP_DEPTH) {
    528   Handle<String> string = ConstructBalancedHelper(data, 0, depth);
    529   data->stats_.leaves_ =
    530       data->stats_.left_traversals_ + data->stats_.right_traversals_ + 2;
    531   return string;
    532 }
    533 
    534 
    535 static ConsStringIteratorOp cons_string_iterator_op_1;
    536 static ConsStringIteratorOp cons_string_iterator_op_2;
    537 
    538 static void Traverse(Handle<String> s1, Handle<String> s2) {
    539   int i = 0;
    540   StringCharacterStream character_stream_1(*s1, &cons_string_iterator_op_1);
    541   StringCharacterStream character_stream_2(*s2, &cons_string_iterator_op_2);
    542   while (character_stream_1.HasMore()) {
    543     CHECK(character_stream_2.HasMore());
    544     uint16_t c = character_stream_1.GetNext();
    545     CHECK_EQ(c, character_stream_2.GetNext());
    546     i++;
    547   }
    548   CHECK(!character_stream_1.HasMore());
    549   CHECK(!character_stream_2.HasMore());
    550   CHECK_EQ(s1->length(), i);
    551   CHECK_EQ(s2->length(), i);
    552 }
    553 
    554 
    555 static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars) {
    556   int i = 0;
    557   StringCharacterStream character_stream_1(*s1, &cons_string_iterator_op_1);
    558   StringCharacterStream character_stream_2(*s2, &cons_string_iterator_op_2);
    559   while (character_stream_1.HasMore() && i < chars) {
    560     CHECK(character_stream_2.HasMore());
    561     uint16_t c = character_stream_1.GetNext();
    562     CHECK_EQ(c, character_stream_2.GetNext());
    563     i++;
    564   }
    565   s1->Get(s1->length() - 1);
    566   s2->Get(s2->length() - 1);
    567 }
    568 
    569 
    570 TEST(Traverse) {
    571   printf("TestTraverse\n");
    572   CcTest::InitializeVM();
    573   v8::HandleScope scope(CcTest::isolate());
    574   Zone zone(CcTest::i_isolate());
    575   ConsStringGenerationData data(false, &zone);
    576   Handle<String> flat = ConstructBalanced(&data);
    577   FlattenString(flat);
    578   Handle<String> left_asymmetric = ConstructLeft(&data, DEEP_DEPTH);
    579   Handle<String> right_asymmetric = ConstructRight(&data, DEEP_DEPTH);
    580   Handle<String> symmetric = ConstructBalanced(&data);
    581   printf("1\n");
    582   Traverse(flat, symmetric);
    583   printf("2\n");
    584   Traverse(flat, left_asymmetric);
    585   printf("3\n");
    586   Traverse(flat, right_asymmetric);
    587   printf("4\n");
    588   Handle<String> left_deep_asymmetric =
    589       ConstructLeft(&data, SUPER_DEEP_DEPTH);
    590   Handle<String> right_deep_asymmetric =
    591       ConstructRight(&data, SUPER_DEEP_DEPTH);
    592   printf("5\n");
    593   TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
    594   printf("6\n");
    595   TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
    596   printf("7\n");
    597   FlattenString(left_asymmetric);
    598   printf("10\n");
    599   Traverse(flat, left_asymmetric);
    600   printf("11\n");
    601   FlattenString(right_asymmetric);
    602   printf("12\n");
    603   Traverse(flat, right_asymmetric);
    604   printf("14\n");
    605   FlattenString(symmetric);
    606   printf("15\n");
    607   Traverse(flat, symmetric);
    608   printf("16\n");
    609   FlattenString(left_deep_asymmetric);
    610   printf("18\n");
    611 }
    612 
    613 
    614 static void VerifyCharacterStream(
    615     String* flat_string, String* cons_string) {
    616   // Do not want to test ConString traversal on flat string.
    617   CHECK(flat_string->IsFlat() && !flat_string->IsConsString());
    618   CHECK(cons_string->IsConsString());
    619   // TODO(dcarney) Test stream reset as well.
    620   int length = flat_string->length();
    621   // Iterate start search in multiple places in the string.
    622   int outer_iterations = length > 20 ? 20 : length;
    623   for (int j = 0; j <= outer_iterations; j++) {
    624     int offset = length * j / outer_iterations;
    625     if (offset < 0) offset = 0;
    626     // Want to test the offset == length case.
    627     if (offset > length) offset = length;
    628     StringCharacterStream flat_stream(
    629         flat_string, &cons_string_iterator_op_1, static_cast<unsigned>(offset));
    630     StringCharacterStream cons_stream(
    631         cons_string, &cons_string_iterator_op_2, static_cast<unsigned>(offset));
    632     for (int i = offset; i < length; i++) {
    633       uint16_t c = flat_string->Get(i);
    634       CHECK(flat_stream.HasMore());
    635       CHECK(cons_stream.HasMore());
    636       CHECK_EQ(c, flat_stream.GetNext());
    637       CHECK_EQ(c, cons_stream.GetNext());
    638     }
    639     CHECK(!flat_stream.HasMore());
    640     CHECK(!cons_stream.HasMore());
    641   }
    642 }
    643 
    644 
    645 static inline void PrintStats(const ConsStringGenerationData& data) {
    646 #ifdef DEBUG
    647 printf(
    648     "%s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d]\n",
    649     "leaves", data.stats_.leaves_,
    650     "empty", data.stats_.empty_leaves_,
    651     "chars", data.stats_.chars_,
    652     "lefts", data.stats_.left_traversals_,
    653     "rights", data.stats_.right_traversals_,
    654     "early_terminations", data.early_terminations_);
    655 #endif
    656 }
    657 
    658 
    659 template<typename BuildString>
    660 void TestStringCharacterStream(BuildString build, int test_cases) {
    661   CcTest::InitializeVM();
    662   Isolate* isolate = CcTest::i_isolate();
    663   HandleScope outer_scope(isolate);
    664   Zone zone(isolate);
    665   ConsStringGenerationData data(true, &zone);
    666   for (int i = 0; i < test_cases; i++) {
    667     printf("%d\n", i);
    668     HandleScope inner_scope(isolate);
    669     AlwaysAllocateScope always_allocate;
    670     // Build flat version of cons string.
    671     Handle<String> flat_string = build(i, &data);
    672     ConsStringStats flat_string_stats;
    673     AccumulateStats(flat_string, &flat_string_stats);
    674     // Flatten string.
    675     FlattenString(flat_string);
    676     // Build unflattened version of cons string to test.
    677     Handle<String> cons_string = build(i, &data);
    678     ConsStringStats cons_string_stats;
    679     AccumulateStats(cons_string, &cons_string_stats);
    680     DisallowHeapAllocation no_allocation;
    681     PrintStats(data);
    682     // Full verify of cons string.
    683     cons_string_stats.VerifyEqual(flat_string_stats);
    684     cons_string_stats.VerifyEqual(data.stats_);
    685     VerifyConsString(cons_string, &data);
    686     String* flat_string_ptr =
    687         flat_string->IsConsString() ?
    688         ConsString::cast(*flat_string)->first() :
    689         *flat_string;
    690     VerifyCharacterStream(flat_string_ptr, *cons_string);
    691   }
    692 }
    693 
    694 
    695 static const int kCharacterStreamNonRandomCases = 8;
    696 
    697 
    698 static Handle<String> BuildEdgeCaseConsString(
    699     int test_case, ConsStringGenerationData* data) {
    700   Factory* factory = CcTest::i_isolate()->factory();
    701   data->Reset();
    702   switch (test_case) {
    703     case 0:
    704       return ConstructBalanced(data, 71);
    705     case 1:
    706       return ConstructLeft(data, 71);
    707     case 2:
    708       return ConstructRight(data, 71);
    709     case 3:
    710       return ConstructLeft(data, 10);
    711     case 4:
    712       return ConstructRight(data, 10);
    713     case 5:
    714       // 2 element balanced tree.
    715       data->stats_.chars_ += data->block(0)->length();
    716       data->stats_.chars_ += data->block(1)->length();
    717       data->stats_.leaves_ += 2;
    718       return factory->NewConsString(data->block(0), data->block(1));
    719     case 6:
    720       // Simple flattened tree.
    721       data->stats_.chars_ += data->block(0)->length();
    722       data->stats_.chars_ += data->block(1)->length();
    723       data->stats_.leaves_ += 2;
    724       data->stats_.empty_leaves_ += 1;
    725       {
    726         Handle<String> string =
    727             factory->NewConsString(data->block(0), data->block(1));
    728         FlattenString(string);
    729         return string;
    730       }
    731     case 7:
    732       // Left node flattened.
    733       data->stats_.chars_ += data->block(0)->length();
    734       data->stats_.chars_ += data->block(1)->length();
    735       data->stats_.chars_ += data->block(2)->length();
    736       data->stats_.leaves_ += 3;
    737       data->stats_.empty_leaves_ += 1;
    738       data->stats_.left_traversals_ += 1;
    739       {
    740         Handle<String> left =
    741             factory->NewConsString(data->block(0), data->block(1));
    742         FlattenString(left);
    743         return factory->NewConsString(left, data->block(2));
    744       }
    745     case 8:
    746       // Left node and right node flattened.
    747       data->stats_.chars_ += data->block(0)->length();
    748       data->stats_.chars_ += data->block(1)->length();
    749       data->stats_.chars_ += data->block(2)->length();
    750       data->stats_.chars_ += data->block(3)->length();
    751       data->stats_.leaves_ += 4;
    752       data->stats_.empty_leaves_ += 2;
    753       data->stats_.left_traversals_ += 1;
    754       data->stats_.right_traversals_ += 1;
    755       {
    756         Handle<String> left =
    757             factory->NewConsString(data->block(0), data->block(1));
    758         FlattenString(left);
    759         Handle<String> right =
    760             factory->NewConsString(data->block(2), data->block(2));
    761         FlattenString(right);
    762         return factory->NewConsString(left, right);
    763       }
    764   }
    765   UNREACHABLE();
    766   return Handle<String>();
    767 }
    768 
    769 
    770 TEST(StringCharacterStreamEdgeCases) {
    771   printf("TestStringCharacterStreamEdgeCases\n");
    772   TestStringCharacterStream(
    773       BuildEdgeCaseConsString, kCharacterStreamNonRandomCases);
    774 }
    775 
    776 
    777 static const int kBalances = 3;
    778 static const int kTreeLengths = 4;
    779 static const int kEmptyLeaves = 4;
    780 static const int kUniqueRandomParameters =
    781     kBalances*kTreeLengths*kEmptyLeaves;
    782 
    783 
    784 static void InitializeGenerationData(
    785     int test_case, ConsStringGenerationData* data) {
    786   // Clear the settings and reinit the rng.
    787   data->Reset();
    788   // Spin up the rng to a known location that is unique per test.
    789   static const int kPerTestJump = 501;
    790   for (int j = 0; j < test_case*kPerTestJump; j++) {
    791     data->rng_.next();
    792   }
    793   // Choose balanced, left or right heavy trees.
    794   switch (test_case % kBalances) {
    795     case 0:
    796       // Nothing to do.  Already balanced.
    797       break;
    798     case 1:
    799       // Left balanced.
    800       data->leftness_ = 0.90;
    801       data->rightness_ = 0.15;
    802       break;
    803     case 2:
    804       // Right balanced.
    805       data->leftness_ = 0.15;
    806       data->rightness_ = 0.90;
    807       break;
    808     default:
    809       UNREACHABLE();
    810       break;
    811   }
    812   // Must remove the influence of the above decision.
    813   test_case /= kBalances;
    814   // Choose tree length.
    815   switch (test_case % kTreeLengths) {
    816     case 0:
    817       data->max_leaves_ = 16;
    818       data->early_termination_threshold_ = 0.2;
    819       break;
    820     case 1:
    821       data->max_leaves_ = 50;
    822       data->early_termination_threshold_ = 0.05;
    823       break;
    824     case 2:
    825       data->max_leaves_ = 500;
    826       data->early_termination_threshold_ = 0.03;
    827       break;
    828     case 3:
    829       data->max_leaves_ = 5000;
    830       data->early_termination_threshold_ = 0.001;
    831       break;
    832     default:
    833       UNREACHABLE();
    834       break;
    835   }
    836   // Must remove the influence of the above decision.
    837   test_case /= kTreeLengths;
    838   // Choose how much we allow empty nodes, including not at all.
    839   data->empty_leaf_threshold_ =
    840       0.03 * static_cast<double>(test_case % kEmptyLeaves);
    841 }
    842 
    843 
    844 static Handle<String> BuildRandomConsString(
    845     int test_case, ConsStringGenerationData* data) {
    846   InitializeGenerationData(test_case, data);
    847   return ConstructRandomString(data, 200);
    848 }
    849 
    850 
    851 TEST(StringCharacterStreamRandom) {
    852   printf("StringCharacterStreamRandom\n");
    853   TestStringCharacterStream(BuildRandomConsString, kUniqueRandomParameters*7);
    854 }
    855 
    856 
    857 static const int DEEP_ASCII_DEPTH = 100000;
    858 
    859 
    860 TEST(DeepAscii) {
    861   printf("TestDeepAscii\n");
    862   CcTest::InitializeVM();
    863   Factory* factory = CcTest::i_isolate()->factory();
    864   v8::HandleScope scope(CcTest::isolate());
    865 
    866   char* foo = NewArray<char>(DEEP_ASCII_DEPTH);
    867   for (int i = 0; i < DEEP_ASCII_DEPTH; i++) {
    868     foo[i] = "foo "[i % 4];
    869   }
    870   Handle<String> string =
    871       factory->NewStringFromAscii(Vector<const char>(foo, DEEP_ASCII_DEPTH));
    872   Handle<String> foo_string = factory->NewStringFromAscii(CStrVector("foo"));
    873   for (int i = 0; i < DEEP_ASCII_DEPTH; i += 10) {
    874     string = factory->NewConsString(string, foo_string);
    875   }
    876   Handle<String> flat_string = factory->NewConsString(string, foo_string);
    877   FlattenString(flat_string);
    878 
    879   for (int i = 0; i < 500; i++) {
    880     TraverseFirst(flat_string, string, DEEP_ASCII_DEPTH);
    881   }
    882   DeleteArray<char>(foo);
    883 }
    884 
    885 
    886 TEST(Utf8Conversion) {
    887   // Smoke test for converting strings to utf-8.
    888   CcTest::InitializeVM();
    889   v8::HandleScope handle_scope(CcTest::isolate());
    890   // A simple ascii string
    891   const char* ascii_string = "abcdef12345";
    892   int len = v8::String::NewFromUtf8(CcTest::isolate(), ascii_string,
    893                                     v8::String::kNormalString,
    894                                     StrLength(ascii_string))->Utf8Length();
    895   CHECK_EQ(StrLength(ascii_string), len);
    896   // A mixed ascii and non-ascii string
    897   // U+02E4 -> CB A4
    898   // U+0064 -> 64
    899   // U+12E4 -> E1 8B A4
    900   // U+0030 -> 30
    901   // U+3045 -> E3 81 85
    902   const uint16_t mixed_string[] = {0x02E4, 0x0064, 0x12E4, 0x0030, 0x3045};
    903   // The characters we expect to be output
    904   const unsigned char as_utf8[11] = {0xCB, 0xA4, 0x64, 0xE1, 0x8B, 0xA4, 0x30,
    905       0xE3, 0x81, 0x85, 0x00};
    906   // The number of bytes expected to be written for each length
    907   const int lengths[12] = {0, 0, 2, 3, 3, 3, 6, 7, 7, 7, 10, 11};
    908   const int char_lengths[12] = {0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5};
    909   v8::Handle<v8::String> mixed = v8::String::NewFromTwoByte(
    910       CcTest::isolate(), mixed_string, v8::String::kNormalString, 5);
    911   CHECK_EQ(10, mixed->Utf8Length());
    912   // Try encoding the string with all capacities
    913   char buffer[11];
    914   const char kNoChar = static_cast<char>(-1);
    915   for (int i = 0; i <= 11; i++) {
    916     // Clear the buffer before reusing it
    917     for (int j = 0; j < 11; j++)
    918       buffer[j] = kNoChar;
    919     int chars_written;
    920     int written = mixed->WriteUtf8(buffer, i, &chars_written);
    921     CHECK_EQ(lengths[i], written);
    922     CHECK_EQ(char_lengths[i], chars_written);
    923     // Check that the contents are correct
    924     for (int j = 0; j < lengths[i]; j++)
    925       CHECK_EQ(as_utf8[j], static_cast<unsigned char>(buffer[j]));
    926     // Check that the rest of the buffer hasn't been touched
    927     for (int j = lengths[i]; j < 11; j++)
    928       CHECK_EQ(kNoChar, buffer[j]);
    929   }
    930 }
    931 
    932 
    933 TEST(ExternalShortStringAdd) {
    934   Isolate* isolate = CcTest::i_isolate();
    935   Zone zone(isolate);
    936 
    937   LocalContext context;
    938   v8::HandleScope handle_scope(CcTest::isolate());
    939 
    940   // Make sure we cover all always-flat lengths and at least one above.
    941   static const int kMaxLength = 20;
    942   CHECK_GT(kMaxLength, i::ConsString::kMinLength);
    943 
    944   // Allocate two JavaScript arrays for holding short strings.
    945   v8::Handle<v8::Array> ascii_external_strings =
    946       v8::Array::New(CcTest::isolate(), kMaxLength + 1);
    947   v8::Handle<v8::Array> non_ascii_external_strings =
    948       v8::Array::New(CcTest::isolate(), kMaxLength + 1);
    949 
    950   // Generate short ascii and non-ascii external strings.
    951   for (int i = 0; i <= kMaxLength; i++) {
    952     char* ascii = zone.NewArray<char>(i + 1);
    953     for (int j = 0; j < i; j++) {
    954       ascii[j] = 'a';
    955     }
    956     // Terminating '\0' is left out on purpose. It is not required for external
    957     // string data.
    958     AsciiResource* ascii_resource =
    959         new(&zone) AsciiResource(Vector<const char>(ascii, i));
    960     v8::Local<v8::String> ascii_external_string =
    961         v8::String::NewExternal(CcTest::isolate(), ascii_resource);
    962 
    963     ascii_external_strings->Set(v8::Integer::New(i), ascii_external_string);
    964     uc16* non_ascii = zone.NewArray<uc16>(i + 1);
    965     for (int j = 0; j < i; j++) {
    966       non_ascii[j] = 0x1234;
    967     }
    968     // Terminating '\0' is left out on purpose. It is not required for external
    969     // string data.
    970     Resource* resource = new(&zone) Resource(Vector<const uc16>(non_ascii, i));
    971     v8::Local<v8::String> non_ascii_external_string =
    972       v8::String::NewExternal(CcTest::isolate(), resource);
    973     non_ascii_external_strings->Set(v8::Integer::New(i),
    974                                     non_ascii_external_string);
    975   }
    976 
    977   // Add the arrays with the short external strings in the global object.
    978   v8::Handle<v8::Object> global = context->Global();
    979   global->Set(v8_str("external_ascii"), ascii_external_strings);
    980   global->Set(v8_str("external_non_ascii"), non_ascii_external_strings);
    981   global->Set(v8_str("max_length"), v8::Integer::New(kMaxLength));
    982 
    983   // Add short external ascii and non-ascii strings checking the result.
    984   static const char* source =
    985     "function test() {"
    986     "  var ascii_chars = 'aaaaaaaaaaaaaaaaaaaa';"
    987     "  var non_ascii_chars = '\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234';"  //NOLINT
    988     "  if (ascii_chars.length != max_length) return 1;"
    989     "  if (non_ascii_chars.length != max_length) return 2;"
    990     "  var ascii = Array(max_length + 1);"
    991     "  var non_ascii = Array(max_length + 1);"
    992     "  for (var i = 0; i <= max_length; i++) {"
    993     "    ascii[i] = ascii_chars.substring(0, i);"
    994     "    non_ascii[i] = non_ascii_chars.substring(0, i);"
    995     "  };"
    996     "  for (var i = 0; i <= max_length; i++) {"
    997     "    if (ascii[i] != external_ascii[i]) return 3;"
    998     "    if (non_ascii[i] != external_non_ascii[i]) return 4;"
    999     "    for (var j = 0; j < i; j++) {"
   1000     "      if (external_ascii[i] !="
   1001     "          (external_ascii[j] + external_ascii[i - j])) return 5;"
   1002     "      if (external_non_ascii[i] !="
   1003     "          (external_non_ascii[j] + external_non_ascii[i - j])) return 6;"
   1004     "      if (non_ascii[i] != (non_ascii[j] + non_ascii[i - j])) return 7;"
   1005     "      if (ascii[i] != (ascii[j] + ascii[i - j])) return 8;"
   1006     "      if (ascii[i] != (external_ascii[j] + ascii[i - j])) return 9;"
   1007     "      if (ascii[i] != (ascii[j] + external_ascii[i - j])) return 10;"
   1008     "      if (non_ascii[i] !="
   1009     "          (external_non_ascii[j] + non_ascii[i - j])) return 11;"
   1010     "      if (non_ascii[i] !="
   1011     "          (non_ascii[j] + external_non_ascii[i - j])) return 12;"
   1012     "    }"
   1013     "  }"
   1014     "  return 0;"
   1015     "};"
   1016     "test()";
   1017   CHECK_EQ(0, CompileRun(source)->Int32Value());
   1018 }
   1019 
   1020 
   1021 TEST(JSONStringifySliceMadeExternal) {
   1022   CcTest::InitializeVM();
   1023   Isolate* isolate = CcTest::i_isolate();
   1024   Zone zone(isolate);
   1025   // Create a sliced string from a one-byte string.  The latter is turned
   1026   // into a two-byte external string.  Check that JSON.stringify works.
   1027   v8::HandleScope handle_scope(CcTest::isolate());
   1028   v8::Handle<v8::String> underlying =
   1029       CompileRun("var underlying = 'abcdefghijklmnopqrstuvwxyz';"
   1030                  "underlying")->ToString();
   1031   v8::Handle<v8::String> slice =
   1032       CompileRun("var slice = underlying.slice(1);"
   1033                  "slice")->ToString();
   1034   CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
   1035   CHECK(v8::Utils::OpenHandle(*underlying)->IsSeqOneByteString());
   1036 
   1037   int length = underlying->Length();
   1038   uc16* two_byte = zone.NewArray<uc16>(length + 1);
   1039   underlying->Write(two_byte);
   1040   Resource* resource =
   1041       new(&zone) Resource(Vector<const uc16>(two_byte, length));
   1042   CHECK(underlying->MakeExternal(resource));
   1043   CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
   1044   CHECK(v8::Utils::OpenHandle(*underlying)->IsExternalTwoByteString());
   1045 
   1046   CHECK_EQ("\"bcdefghijklmnopqrstuvwxyz\"",
   1047            *v8::String::Utf8Value(CompileRun("JSON.stringify(slice)")));
   1048 }
   1049 
   1050 
   1051 TEST(CachedHashOverflow) {
   1052   CcTest::InitializeVM();
   1053   // We incorrectly allowed strings to be tagged as array indices even if their
   1054   // values didn't fit in the hash field.
   1055   // See http://code.google.com/p/v8/issues/detail?id=728
   1056   Isolate* isolate = CcTest::i_isolate();
   1057   Zone zone(isolate);
   1058 
   1059   v8::HandleScope handle_scope(CcTest::isolate());
   1060   // Lines must be executed sequentially. Combining them into one script
   1061   // makes the bug go away.
   1062   const char* lines[] = {
   1063       "var x = [];",
   1064       "x[4] = 42;",
   1065       "var s = \"1073741828\";",
   1066       "x[s];",
   1067       "x[s] = 37;",
   1068       "x[4];",
   1069       "x[s];",
   1070       NULL
   1071   };
   1072 
   1073   Handle<Smi> fortytwo(Smi::FromInt(42), isolate);
   1074   Handle<Smi> thirtyseven(Smi::FromInt(37), isolate);
   1075   Handle<Object> results[] = { isolate->factory()->undefined_value(),
   1076                                fortytwo,
   1077                                isolate->factory()->undefined_value(),
   1078                                isolate->factory()->undefined_value(),
   1079                                thirtyseven,
   1080                                fortytwo,
   1081                                thirtyseven  // Bug yielded 42 here.
   1082   };
   1083 
   1084   const char* line;
   1085   for (int i = 0; (line = lines[i]); i++) {
   1086     printf("%s\n", line);
   1087     v8::Local<v8::Value> result = v8::Script::Compile(
   1088         v8::String::NewFromUtf8(CcTest::isolate(), line))->Run();
   1089     CHECK_EQ(results[i]->IsUndefined(), result->IsUndefined());
   1090     CHECK_EQ(results[i]->IsNumber(), result->IsNumber());
   1091     if (result->IsNumber()) {
   1092       CHECK_EQ(Smi::cast(results[i]->ToSmi()->ToObjectChecked())->value(),
   1093                result->ToInt32()->Value());
   1094     }
   1095   }
   1096 }
   1097 
   1098 
   1099 TEST(SliceFromCons) {
   1100   FLAG_string_slices = true;
   1101   CcTest::InitializeVM();
   1102   Factory* factory = CcTest::i_isolate()->factory();
   1103   v8::HandleScope scope(CcTest::isolate());
   1104   Handle<String> string =
   1105       factory->NewStringFromAscii(CStrVector("parentparentparent"));
   1106   Handle<String> parent = factory->NewConsString(string, string);
   1107   CHECK(parent->IsConsString());
   1108   CHECK(!parent->IsFlat());
   1109   Handle<String> slice = factory->NewSubString(parent, 1, 25);
   1110   // After slicing, the original string becomes a flat cons.
   1111   CHECK(parent->IsFlat());
   1112   CHECK(slice->IsSlicedString());
   1113   CHECK_EQ(SlicedString::cast(*slice)->parent(),
   1114            // Parent could have been short-circuited.
   1115            parent->IsConsString() ? ConsString::cast(*parent)->first()
   1116                                   : *parent);
   1117   CHECK(SlicedString::cast(*slice)->parent()->IsSeqString());
   1118   CHECK(slice->IsFlat());
   1119 }
   1120 
   1121 
   1122 class AsciiVectorResource : public v8::String::ExternalAsciiStringResource {
   1123  public:
   1124   explicit AsciiVectorResource(i::Vector<const char> vector)
   1125       : data_(vector) {}
   1126   virtual ~AsciiVectorResource() {}
   1127   virtual size_t length() const { return data_.length(); }
   1128   virtual const char* data() const { return data_.start(); }
   1129  private:
   1130   i::Vector<const char> data_;
   1131 };
   1132 
   1133 
   1134 TEST(SliceFromExternal) {
   1135   FLAG_string_slices = true;
   1136   CcTest::InitializeVM();
   1137   Factory* factory = CcTest::i_isolate()->factory();
   1138   v8::HandleScope scope(CcTest::isolate());
   1139   AsciiVectorResource resource(
   1140       i::Vector<const char>("abcdefghijklmnopqrstuvwxyz", 26));
   1141   Handle<String> string = factory->NewExternalStringFromAscii(&resource);
   1142   CHECK(string->IsExternalString());
   1143   Handle<String> slice = factory->NewSubString(string, 1, 25);
   1144   CHECK(slice->IsSlicedString());
   1145   CHECK(string->IsExternalString());
   1146   CHECK_EQ(SlicedString::cast(*slice)->parent(), *string);
   1147   CHECK(SlicedString::cast(*slice)->parent()->IsExternalString());
   1148   CHECK(slice->IsFlat());
   1149 }
   1150 
   1151 
   1152 TEST(TrivialSlice) {
   1153   // This tests whether a slice that contains the entire parent string
   1154   // actually creates a new string (it should not).
   1155   FLAG_string_slices = true;
   1156   CcTest::InitializeVM();
   1157   Factory* factory = CcTest::i_isolate()->factory();
   1158   v8::HandleScope scope(CcTest::isolate());
   1159   v8::Local<v8::Value> result;
   1160   Handle<String> string;
   1161   const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
   1162   const char* check = "str.slice(0,26)";
   1163   const char* crosscheck = "str.slice(1,25)";
   1164 
   1165   CompileRun(init);
   1166 
   1167   result = CompileRun(check);
   1168   CHECK(result->IsString());
   1169   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
   1170   CHECK(!string->IsSlicedString());
   1171 
   1172   string = factory->NewSubString(string, 0, 26);
   1173   CHECK(!string->IsSlicedString());
   1174   result = CompileRun(crosscheck);
   1175   CHECK(result->IsString());
   1176   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
   1177   CHECK(string->IsSlicedString());
   1178   CHECK_EQ("bcdefghijklmnopqrstuvwxy", *(string->ToCString()));
   1179 }
   1180 
   1181 
   1182 TEST(SliceFromSlice) {
   1183   // This tests whether a slice that contains the entire parent string
   1184   // actually creates a new string (it should not).
   1185   FLAG_string_slices = true;
   1186   CcTest::InitializeVM();
   1187   v8::HandleScope scope(CcTest::isolate());
   1188   v8::Local<v8::Value> result;
   1189   Handle<String> string;
   1190   const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
   1191   const char* slice = "var slice = str.slice(1,-1); slice";
   1192   const char* slice_from_slice = "slice.slice(1,-1);";
   1193 
   1194   CompileRun(init);
   1195   result = CompileRun(slice);
   1196   CHECK(result->IsString());
   1197   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
   1198   CHECK(string->IsSlicedString());
   1199   CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
   1200   CHECK_EQ("bcdefghijklmnopqrstuvwxy", *(string->ToCString()));
   1201 
   1202   result = CompileRun(slice_from_slice);
   1203   CHECK(result->IsString());
   1204   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
   1205   CHECK(string->IsSlicedString());
   1206   CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
   1207   CHECK_EQ("cdefghijklmnopqrstuvwx", *(string->ToCString()));
   1208 }
   1209 
   1210 
   1211 TEST(AsciiArrayJoin) {
   1212   // Set heap limits.
   1213   static const int K = 1024;
   1214   v8::ResourceConstraints constraints;
   1215   constraints.set_max_young_space_size(256 * K);
   1216   constraints.set_max_old_space_size(4 * K * K);
   1217   v8::SetResourceConstraints(CcTest::isolate(), &constraints);
   1218 
   1219   // String s is made of 2^17 = 131072 'c' characters and a is an array
   1220   // starting with 'bad', followed by 2^14 times the string s. That means the
   1221   // total length of the concatenated strings is 2^31 + 3. So on 32bit systems
   1222   // summing the lengths of the strings (as Smis) overflows and wraps.
   1223   static const char* join_causing_out_of_memory =
   1224       "var two_14 = Math.pow(2, 14);"
   1225       "var two_17 = Math.pow(2, 17);"
   1226       "var s = Array(two_17 + 1).join('c');"
   1227       "var a = ['bad'];"
   1228       "for (var i = 1; i <= two_14; i++) a.push(s);"
   1229       "a.join("");";
   1230 
   1231   v8::HandleScope scope(CcTest::isolate());
   1232   LocalContext context;
   1233   v8::V8::IgnoreOutOfMemoryException();
   1234   v8::Local<v8::Script> script = v8::Script::Compile(
   1235       v8::String::NewFromUtf8(CcTest::isolate(), join_causing_out_of_memory));
   1236   v8::Local<v8::Value> result = script->Run();
   1237 
   1238   // Check for out of memory state.
   1239   CHECK(result.IsEmpty());
   1240   CHECK(context->HasOutOfMemoryException());
   1241 }
   1242 
   1243 
   1244 static void CheckException(const char* source) {
   1245   // An empty handle is returned upon exception.
   1246   CHECK(CompileRun(source).IsEmpty());
   1247 }
   1248 
   1249 
   1250 TEST(RobustSubStringStub) {
   1251   // This tests whether the SubStringStub can handle unsafe arguments.
   1252   // If not recognized, those unsafe arguments lead to out-of-bounds reads.
   1253   FLAG_allow_natives_syntax = true;
   1254   CcTest::InitializeVM();
   1255   v8::HandleScope scope(CcTest::isolate());
   1256   v8::Local<v8::Value> result;
   1257   Handle<String> string;
   1258   CompileRun("var short = 'abcdef';");
   1259 
   1260   // Invalid indices.
   1261   CheckException("%_SubString(short,     0,    10000);");
   1262   CheckException("%_SubString(short, -1234,        5);");
   1263   CheckException("%_SubString(short,     5,        2);");
   1264   // Special HeapNumbers.
   1265   CheckException("%_SubString(short,     1, Infinity);");
   1266   CheckException("%_SubString(short,   NaN,        5);");
   1267   // String arguments.
   1268   CheckException("%_SubString(short,    '2',     '5');");
   1269   // Ordinary HeapNumbers can be handled (in runtime).
   1270   result = CompileRun("%_SubString(short, Math.sqrt(4), 5.1);");
   1271   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
   1272   CHECK_EQ("cde", *(string->ToCString()));
   1273 
   1274   CompileRun("var long = 'abcdefghijklmnopqrstuvwxyz';");
   1275   // Invalid indices.
   1276   CheckException("%_SubString(long,     0,    10000);");
   1277   CheckException("%_SubString(long, -1234,       17);");
   1278   CheckException("%_SubString(long,    17,        2);");
   1279   // Special HeapNumbers.
   1280   CheckException("%_SubString(long,     1, Infinity);");
   1281   CheckException("%_SubString(long,   NaN,       17);");
   1282   // String arguments.
   1283   CheckException("%_SubString(long,    '2',    '17');");
   1284   // Ordinary HeapNumbers within bounds can be handled (in runtime).
   1285   result = CompileRun("%_SubString(long, Math.sqrt(4), 17.1);");
   1286   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
   1287   CHECK_EQ("cdefghijklmnopq", *(string->ToCString()));
   1288 
   1289   // Test that out-of-bounds substring of a slice fails when the indices
   1290   // would have been valid for the underlying string.
   1291   CompileRun("var slice = long.slice(1, 15);");
   1292   CheckException("%_SubString(slice, 0, 17);");
   1293 }
   1294 
   1295 
   1296 TEST(RegExpOverflow) {
   1297   // Result string has the length 2^32, causing a 32-bit integer overflow.
   1298   CcTest::InitializeVM();
   1299   v8::HandleScope scope(CcTest::isolate());
   1300   LocalContext context;
   1301   v8::V8::IgnoreOutOfMemoryException();
   1302   v8::Local<v8::Value> result = CompileRun(
   1303       "var a = 'a';                     "
   1304       "for (var i = 0; i < 16; i++) {   "
   1305       "  a += a;                        "
   1306       "}                                "
   1307       "a.replace(/a/g, a);              ");
   1308   CHECK(result.IsEmpty());
   1309   CHECK(context->HasOutOfMemoryException());
   1310 }
   1311 
   1312 
   1313 TEST(StringReplaceAtomTwoByteResult) {
   1314   CcTest::InitializeVM();
   1315   v8::HandleScope scope(CcTest::isolate());
   1316   LocalContext context;
   1317   v8::Local<v8::Value> result = CompileRun(
   1318       "var subject = 'ascii~only~string~'; "
   1319       "var replace = '\x80';            "
   1320       "subject.replace(/~/g, replace);  ");
   1321   CHECK(result->IsString());
   1322   Handle<String> string = v8::Utils::OpenHandle(v8::String::Cast(*result));
   1323   CHECK(string->IsSeqTwoByteString());
   1324 
   1325   v8::Local<v8::String> expected = v8_str("ascii\x80only\x80string\x80");
   1326   CHECK(expected->Equals(result));
   1327 }
   1328 
   1329 
   1330 TEST(IsAscii) {
   1331   CHECK(String::IsAscii(static_cast<char*>(NULL), 0));
   1332   CHECK(String::IsOneByte(static_cast<uc16*>(NULL), 0));
   1333 }
   1334 
   1335 
   1336 
   1337 template<typename Op, bool return_first>
   1338 static uint16_t ConvertLatin1(uint16_t c) {
   1339   uint32_t result[Op::kMaxWidth];
   1340   int chars;
   1341   chars = Op::Convert(c, 0, result, NULL);
   1342   if (chars == 0) return 0;
   1343   CHECK_LE(chars, static_cast<int>(sizeof(result)));
   1344   if (!return_first && chars > 1) {
   1345     return 0;
   1346   }
   1347   return result[0];
   1348 }
   1349 
   1350 
   1351 static void CheckCanonicalEquivalence(uint16_t c, uint16_t test) {
   1352   uint16_t expect = ConvertLatin1<unibrow::Ecma262UnCanonicalize, true>(c);
   1353   if (expect > unibrow::Latin1::kMaxChar) expect = 0;
   1354   CHECK_EQ(expect, test);
   1355 }
   1356 
   1357 
   1358 TEST(Latin1IgnoreCase) {
   1359   using namespace unibrow;
   1360   for (uint16_t c = Latin1::kMaxChar + 1; c != 0; c++) {
   1361     uint16_t lower = ConvertLatin1<ToLowercase, false>(c);
   1362     uint16_t upper = ConvertLatin1<ToUppercase, false>(c);
   1363     uint16_t test = Latin1::ConvertNonLatin1ToLatin1(c);
   1364     // Filter out all character whose upper is not their lower or vice versa.
   1365     if (lower == 0 && upper == 0) {
   1366       CheckCanonicalEquivalence(c, test);
   1367       continue;
   1368     }
   1369     if (lower > Latin1::kMaxChar && upper > Latin1::kMaxChar) {
   1370       CheckCanonicalEquivalence(c, test);
   1371       continue;
   1372     }
   1373     if (lower == 0 && upper != 0) {
   1374       lower = ConvertLatin1<ToLowercase, false>(upper);
   1375     }
   1376     if (upper == 0 && lower != c) {
   1377       upper = ConvertLatin1<ToUppercase, false>(lower);
   1378     }
   1379     if (lower > Latin1::kMaxChar && upper > Latin1::kMaxChar) {
   1380       CheckCanonicalEquivalence(c, test);
   1381       continue;
   1382     }
   1383     if (upper != c && lower != c) {
   1384       CheckCanonicalEquivalence(c, test);
   1385       continue;
   1386     }
   1387     CHECK_EQ(Min(upper, lower), test);
   1388   }
   1389 }
   1390