src/v8/test/cctest/test-strings.cc

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