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] = factory->NewStringFromTwoByte(
 168             Vector<const uc16>(buf, len)).ToHandleChecked();
 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] = factory->NewStringFromAscii(
 180             Vector<const char>(buf, len)).ToHandleChecked();
 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   int leaves_;
 234   int empty_leaves_;
 235   int chars_;
 236   int left_traversals_;
 237   int 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_EQ(this->leaves_, that.leaves_);
 254   CHECK_EQ(this->empty_leaves_, that.empty_leaves_);
 255   CHECK_EQ(this->chars_, that.chars_);
 256   CHECK_EQ(this->left_traversals_, that.left_traversals_);
 257   CHECK_EQ(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   int max_leaves_;
 274   // Cached data.
 275   Handle<String> building_blocks_[kNumberOfBuildingBlocks];
 276   String* empty_string_;
 277   MyRandomNumberGenerator rng_;
 278   // Stats.
 279   ConsStringStats stats_;
 280   int 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   ConsStringIteratorOp op(cons_string);
 360   String* string;
 361   int offset;
 362   while (NULL != (string = op.Next(&offset))) {
 363     // Accumulate stats.
 364     CHECK_EQ(0, offset);
 365     stats->leaves_++;
 366     stats->chars_ += string->length();
 367   }
 368 }
 369
 370
 371 void VerifyConsString(Handle<String> root, ConsStringGenerationData* data) {
 372   // Verify basic data.
 373   CHECK(root->IsConsString());
 374   CHECK_EQ(root->length(), data->stats_.chars_);
 375   // Recursive verify.
 376   ConsStringStats stats;
 377   AccumulateStats(ConsString::cast(*root), &stats);
 378   stats.VerifyEqual(data->stats_);
 379   // Iteratively verify.
 380   stats.Reset();
 381   AccumulateStatsWithOperator(ConsString::cast(*root), &stats);
 382   // Don't see these. Must copy over.
 383   stats.empty_leaves_ = data->stats_.empty_leaves_;
 384   stats.left_traversals_ = data->stats_.left_traversals_;
 385   stats.right_traversals_ = data->stats_.right_traversals_;
 386   // Adjust total leaves to compensate.
 387   stats.leaves_ += stats.empty_leaves_;
 388   stats.VerifyEqual(data->stats_);
 389 }
 390
 391
 392 static Handle<String> ConstructRandomString(ConsStringGenerationData* data,
 393                                             unsigned max_recursion) {
 394   Factory* factory = CcTest::i_isolate()->factory();
 395   // Compute termination characteristics.
 396   bool terminate = false;
 397   bool flat = data->rng_.next(data->empty_leaf_threshold_);
 398   bool terminate_early = data->rng_.next(data->early_termination_threshold_);
 399   if (terminate_early) data->early_terminations_++;
 400   // The obvious condition.
 401   terminate |= max_recursion == 0;
 402   // Flat cons string terminate by definition.
 403   terminate |= flat;
 404   // Cap for max leaves.
 405   terminate |= data->stats_.leaves_ >= data->max_leaves_;
 406   // Roll the dice.
 407   terminate |= terminate_early;
 408   // Compute termination characteristics for each side.
 409   bool terminate_left = terminate || !data->rng_.next(data->leftness_);
 410   bool terminate_right = terminate || !data->rng_.next(data->rightness_);
 411   // Generate left string.
 412   Handle<String> left;
 413   if (terminate_left) {
 414     left = data->block(data->rng_.next());
 415     data->stats_.leaves_++;
 416     data->stats_.chars_ += left->length();
 417   } else {
 418     data->stats_.left_traversals_++;
 419   }
 420   // Generate right string.
 421   Handle<String> right;
 422   if (terminate_right) {
 423     right = data->block(data->rng_.next());
 424     data->stats_.leaves_++;
 425     data->stats_.chars_ += right->length();
 426   } else {
 427     data->stats_.right_traversals_++;
 428   }
 429   // Generate the necessary sub-nodes recursively.
 430   if (!terminate_right) {
 431     // Need to balance generation fairly.
 432     if (!terminate_left && data->rng_.next(0.5)) {
 433       left = ConstructRandomString(data, max_recursion - 1);
 434     }
 435     right = ConstructRandomString(data, max_recursion - 1);
 436   }
 437   if (!terminate_left && left.is_null()) {
 438     left = ConstructRandomString(data, max_recursion - 1);
 439   }
 440   // Build the cons string.
 441   Handle<String> root = factory->NewConsString(left, right).ToHandleChecked();
 442   CHECK(root->IsConsString() && !root->IsFlat());
 443   // Special work needed for flat string.
 444   if (flat) {
 445     data->stats_.empty_leaves_++;
 446     String::Flatten(root);
 447     CHECK(root->IsConsString() && root->IsFlat());
 448   }
 449   return root;
 450 }
 451
 452
 453 static Handle<String> ConstructLeft(
 454     ConsStringGenerationData* data,
 455     int depth) {
 456   Factory* factory = CcTest::i_isolate()->factory();
 457   Handle<String> answer = factory->NewStringFromStaticAscii("");
 458   data->stats_.leaves_++;
 459   for (int i = 0; i < depth; i++) {
 460     Handle<String> block = data->block(i);
 461     Handle<String> next =
 462         factory->NewConsString(answer, block).ToHandleChecked();
 463     if (next->IsConsString()) data->stats_.leaves_++;
 464     data->stats_.chars_ += block->length();
 465     answer = next;
 466   }
 467   data->stats_.left_traversals_ = data->stats_.leaves_ - 2;
 468   return answer;
 469 }
 470
 471
 472 static Handle<String> ConstructRight(
 473     ConsStringGenerationData* data,
 474     int depth) {
 475   Factory* factory = CcTest::i_isolate()->factory();
 476   Handle<String> answer = factory->NewStringFromStaticAscii("");
 477   data->stats_.leaves_++;
 478   for (int i = depth - 1; i >= 0; i--) {
 479     Handle<String> block = data->block(i);
 480     Handle<String> next =
 481         factory->NewConsString(block, answer).ToHandleChecked();
 482     if (next->IsConsString()) data->stats_.leaves_++;
 483     data->stats_.chars_ += block->length();
 484     answer = next;
 485   }
 486   data->stats_.right_traversals_ = data->stats_.leaves_ - 2;
 487   return answer;
 488 }
 489
 490
 491 static Handle<String> ConstructBalancedHelper(
 492     ConsStringGenerationData* data,
 493     int from,
 494     int to) {
 495   Factory* factory = CcTest::i_isolate()->factory();
 496   CHECK(to > from);
 497   if (to - from == 1) {
 498     data->stats_.chars_ += data->block(from)->length();
 499     return data->block(from);
 500   }
 501   if (to - from == 2) {
 502     data->stats_.chars_ += data->block(from)->length();
 503     data->stats_.chars_ += data->block(from+1)->length();
 504     return factory->NewConsString(data->block(from), data->block(from+1))
 505         .ToHandleChecked();
 506   }
 507   Handle<String> part1 =
 508     ConstructBalancedHelper(data, from, from + ((to - from) / 2));
 509   Handle<String> part2 =
 510     ConstructBalancedHelper(data, from + ((to - from) / 2), to);
 511   if (part1->IsConsString()) data->stats_.left_traversals_++;
 512   if (part2->IsConsString()) data->stats_.right_traversals_++;
 513   return factory->NewConsString(part1, part2).ToHandleChecked();
 514 }
 515
 516
 517 static Handle<String> ConstructBalanced(
 518     ConsStringGenerationData* data, int depth = DEEP_DEPTH) {
 519   Handle<String> string = ConstructBalancedHelper(data, 0, depth);
 520   data->stats_.leaves_ =
 521       data->stats_.left_traversals_ + data->stats_.right_traversals_ + 2;
 522   return string;
 523 }
 524
 525
 526 static ConsStringIteratorOp cons_string_iterator_op_1;
 527 static ConsStringIteratorOp cons_string_iterator_op_2;
 528
 529 static void Traverse(Handle<String> s1, Handle<String> s2) {
 530   int i = 0;
 531   StringCharacterStream character_stream_1(*s1, &cons_string_iterator_op_1);
 532   StringCharacterStream character_stream_2(*s2, &cons_string_iterator_op_2);
 533   while (character_stream_1.HasMore()) {
 534     CHECK(character_stream_2.HasMore());
 535     uint16_t c = character_stream_1.GetNext();
 536     CHECK_EQ(c, character_stream_2.GetNext());
 537     i++;
 538   }
 539   CHECK(!character_stream_1.HasMore());
 540   CHECK(!character_stream_2.HasMore());
 541   CHECK_EQ(s1->length(), i);
 542   CHECK_EQ(s2->length(), i);
 543 }
 544
 545
 546 static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars) {
 547   int i = 0;
 548   StringCharacterStream character_stream_1(*s1, &cons_string_iterator_op_1);
 549   StringCharacterStream character_stream_2(*s2, &cons_string_iterator_op_2);
 550   while (character_stream_1.HasMore() && i < chars) {
 551     CHECK(character_stream_2.HasMore());
 552     uint16_t c = character_stream_1.GetNext();
 553     CHECK_EQ(c, character_stream_2.GetNext());
 554     i++;
 555   }
 556   s1->Get(s1->length() - 1);
 557   s2->Get(s2->length() - 1);
 558 }
 559
 560
 561 TEST(Traverse) {
 562   printf("TestTraverse\n");
 563   CcTest::InitializeVM();
 564   v8::HandleScope scope(CcTest::isolate());
 565   ConsStringGenerationData data(false);
 566   Handle<String> flat = ConstructBalanced(&data);
 567   String::Flatten(flat);
 568   Handle<String> left_asymmetric = ConstructLeft(&data, DEEP_DEPTH);
 569   Handle<String> right_asymmetric = ConstructRight(&data, DEEP_DEPTH);
 570   Handle<String> symmetric = ConstructBalanced(&data);
 571   printf("1\n");
 572   Traverse(flat, symmetric);
 573   printf("2\n");
 574   Traverse(flat, left_asymmetric);
 575   printf("3\n");
 576   Traverse(flat, right_asymmetric);
 577   printf("4\n");
 578   Handle<String> left_deep_asymmetric =
 579       ConstructLeft(&data, SUPER_DEEP_DEPTH);
 580   Handle<String> right_deep_asymmetric =
 581       ConstructRight(&data, SUPER_DEEP_DEPTH);
 582   printf("5\n");
 583   TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
 584   printf("6\n");
 585   TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
 586   printf("7\n");
 587   String::Flatten(left_asymmetric);
 588   printf("10\n");
 589   Traverse(flat, left_asymmetric);
 590   printf("11\n");
 591   String::Flatten(right_asymmetric);
 592   printf("12\n");
 593   Traverse(flat, right_asymmetric);
 594   printf("14\n");
 595   String::Flatten(symmetric);
 596   printf("15\n");
 597   Traverse(flat, symmetric);
 598   printf("16\n");
 599   String::Flatten(left_deep_asymmetric);
 600   printf("18\n");
 601 }
 602
 603
 604 static void VerifyCharacterStream(
 605     String* flat_string, String* cons_string) {
 606   // Do not want to test ConString traversal on flat string.
 607   CHECK(flat_string->IsFlat() && !flat_string->IsConsString());
 608   CHECK(cons_string->IsConsString());
 609   // TODO(dcarney) Test stream reset as well.
 610   int length = flat_string->length();
 611   // Iterate start search in multiple places in the string.
 612   int outer_iterations = length > 20 ? 20 : length;
 613   for (int j = 0; j <= outer_iterations; j++) {
 614     int offset = length * j / outer_iterations;
 615     if (offset < 0) offset = 0;
 616     // Want to test the offset == length case.
 617     if (offset > length) offset = length;
 618     StringCharacterStream flat_stream(
 619         flat_string, &cons_string_iterator_op_1, offset);
 620     StringCharacterStream cons_stream(
 621         cons_string, &cons_string_iterator_op_2, offset);
 622     for (int i = offset; i < length; i++) {
 623       uint16_t c = flat_string->Get(i);
 624       CHECK(flat_stream.HasMore());
 625       CHECK(cons_stream.HasMore());
 626       CHECK_EQ(c, flat_stream.GetNext());
 627       CHECK_EQ(c, cons_stream.GetNext());
 628     }
 629     CHECK(!flat_stream.HasMore());
 630     CHECK(!cons_stream.HasMore());
 631   }
 632 }
 633
 634
 635 static inline void PrintStats(const ConsStringGenerationData& data) {
 636 #ifdef DEBUG
 637 printf(
 638     "%s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d]\n",
 639     "leaves", data.stats_.leaves_,
 640     "empty", data.stats_.empty_leaves_,
 641     "chars", data.stats_.chars_,
 642     "lefts", data.stats_.left_traversals_,
 643     "rights", data.stats_.right_traversals_,
 644     "early_terminations", data.early_terminations_);
 645 #endif
 646 }
 647
 648
 649 template<typename BuildString>
 650 void TestStringCharacterStream(BuildString build, int test_cases) {
 651   CcTest::InitializeVM();
 652   Isolate* isolate = CcTest::i_isolate();
 653   HandleScope outer_scope(isolate);
 654   ConsStringGenerationData data(true);
 655   for (int i = 0; i < test_cases; i++) {
 656     printf("%d\n", i);
 657     HandleScope inner_scope(isolate);
 658     AlwaysAllocateScope always_allocate(isolate);
 659     // Build flat version of cons string.
 660     Handle<String> flat_string = build(i, &data);
 661     ConsStringStats flat_string_stats;
 662     AccumulateStats(flat_string, &flat_string_stats);
 663     // Flatten string.
 664     String::Flatten(flat_string);
 665     // Build unflattened version of cons string to test.
 666     Handle<String> cons_string = build(i, &data);
 667     ConsStringStats cons_string_stats;
 668     AccumulateStats(cons_string, &cons_string_stats);
 669     DisallowHeapAllocation no_allocation;
 670     PrintStats(data);
 671     // Full verify of cons string.
 672     cons_string_stats.VerifyEqual(flat_string_stats);
 673     cons_string_stats.VerifyEqual(data.stats_);
 674     VerifyConsString(cons_string, &data);
 675     String* flat_string_ptr =
 676         flat_string->IsConsString() ?
 677         ConsString::cast(*flat_string)->first() :
 678         *flat_string;
 679     VerifyCharacterStream(flat_string_ptr, *cons_string);
 680   }
 681 }
 682
 683
 684 static const int kCharacterStreamNonRandomCases = 8;
 685
 686
 687 static Handle<String> BuildEdgeCaseConsString(
 688     int test_case, ConsStringGenerationData* data) {
 689   Factory* factory = CcTest::i_isolate()->factory();
 690   data->Reset();
 691   switch (test_case) {
 692     case 0:
 693       return ConstructBalanced(data, 71);
 694     case 1:
 695       return ConstructLeft(data, 71);
 696     case 2:
 697       return ConstructRight(data, 71);
 698     case 3:
 699       return ConstructLeft(data, 10);
 700     case 4:
 701       return ConstructRight(data, 10);
 702     case 5:
 703       // 2 element balanced tree.
 704       data->stats_.chars_ += data->block(0)->length();
 705       data->stats_.chars_ += data->block(1)->length();
 706       data->stats_.leaves_ += 2;
 707       return factory->NewConsString(data->block(0), data->block(1))
 708                  .ToHandleChecked();
 709     case 6:
 710       // Simple flattened tree.
 711       data->stats_.chars_ += data->block(0)->length();
 712       data->stats_.chars_ += data->block(1)->length();
 713       data->stats_.leaves_ += 2;
 714       data->stats_.empty_leaves_ += 1;
 715       {
 716         Handle<String> string =
 717             factory->NewConsString(data->block(0), data->block(1))
 718                 .ToHandleChecked();
 719         String::Flatten(string);
 720         return string;
 721       }
 722     case 7:
 723       // Left node flattened.
 724       data->stats_.chars_ += data->block(0)->length();
 725       data->stats_.chars_ += data->block(1)->length();
 726       data->stats_.chars_ += data->block(2)->length();
 727       data->stats_.leaves_ += 3;
 728       data->stats_.empty_leaves_ += 1;
 729       data->stats_.left_traversals_ += 1;
 730       {
 731         Handle<String> left =
 732             factory->NewConsString(data->block(0), data->block(1))
 733                 .ToHandleChecked();
 734         String::Flatten(left);
 735         return factory->NewConsString(left, data->block(2)).ToHandleChecked();
 736       }
 737     case 8:
 738       // Left node and right node flattened.
 739       data->stats_.chars_ += data->block(0)->length();
 740       data->stats_.chars_ += data->block(1)->length();
 741       data->stats_.chars_ += data->block(2)->length();
 742       data->stats_.chars_ += data->block(3)->length();
 743       data->stats_.leaves_ += 4;
 744       data->stats_.empty_leaves_ += 2;
 745       data->stats_.left_traversals_ += 1;
 746       data->stats_.right_traversals_ += 1;
 747       {
 748         Handle<String> left =
 749             factory->NewConsString(data->block(0), data->block(1))
 750                 .ToHandleChecked();
 751         String::Flatten(left);
 752         Handle<String> right =
 753             factory->NewConsString(data->block(2), data->block(2))
 754                 .ToHandleChecked();
 755         String::Flatten(right);
 756         return factory->NewConsString(left, right).ToHandleChecked();
 757       }
 758   }
 759   UNREACHABLE();
 760   return Handle<String>();
 761 }
 762
 763
 764 TEST(StringCharacterStreamEdgeCases) {
 765   printf("TestStringCharacterStreamEdgeCases\n");
 766   TestStringCharacterStream(
 767       BuildEdgeCaseConsString, kCharacterStreamNonRandomCases);
 768 }
 769
 770
 771 static const int kBalances = 3;
 772 static const int kTreeLengths = 4;
 773 static const int kEmptyLeaves = 4;
 774 static const int kUniqueRandomParameters =
 775     kBalances*kTreeLengths*kEmptyLeaves;
 776
 777
 778 static void InitializeGenerationData(
 779     int test_case, ConsStringGenerationData* data) {
 780   // Clear the settings and reinit the rng.
 781   data->Reset();
 782   // Spin up the rng to a known location that is unique per test.
 783   static const int kPerTestJump = 501;
 784   for (int j = 0; j < test_case*kPerTestJump; j++) {
 785     data->rng_.next();
 786   }
 787   // Choose balanced, left or right heavy trees.
 788   switch (test_case % kBalances) {
 789     case 0:
 790       // Nothing to do.  Already balanced.
 791       break;
 792     case 1:
 793       // Left balanced.
 794       data->leftness_ = 0.90;
 795       data->rightness_ = 0.15;
 796       break;
 797     case 2:
 798       // Right balanced.
 799       data->leftness_ = 0.15;
 800       data->rightness_ = 0.90;
 801       break;
 802     default:
 803       UNREACHABLE();
 804       break;
 805   }
 806   // Must remove the influence of the above decision.
 807   test_case /= kBalances;
 808   // Choose tree length.
 809   switch (test_case % kTreeLengths) {
 810     case 0:
 811       data->max_leaves_ = 16;
 812       data->early_termination_threshold_ = 0.2;
 813       break;
 814     case 1:
 815       data->max_leaves_ = 50;
 816       data->early_termination_threshold_ = 0.05;
 817       break;
 818     case 2:
 819       data->max_leaves_ = 500;
 820       data->early_termination_threshold_ = 0.03;
 821       break;
 822     case 3:
 823       data->max_leaves_ = 5000;
 824       data->early_termination_threshold_ = 0.001;
 825       break;
 826     default:
 827       UNREACHABLE();
 828       break;
 829   }
 830   // Must remove the influence of the above decision.
 831   test_case /= kTreeLengths;
 832   // Choose how much we allow empty nodes, including not at all.
 833   data->empty_leaf_threshold_ =
 834       0.03 * static_cast<double>(test_case % kEmptyLeaves);
 835 }
 836
 837
 838 static Handle<String> BuildRandomConsString(
 839     int test_case, ConsStringGenerationData* data) {
 840   InitializeGenerationData(test_case, data);
 841   return ConstructRandomString(data, 200);
 842 }
 843
 844
 845 TEST(StringCharacterStreamRandom) {
 846   printf("StringCharacterStreamRandom\n");
 847   TestStringCharacterStream(BuildRandomConsString, kUniqueRandomParameters*7);
 848 }
 849
 850
 851 static const int DEEP_ASCII_DEPTH = 100000;
 852
 853
 854 TEST(DeepAscii) {
 855   printf("TestDeepAscii\n");
 856   CcTest::InitializeVM();
 857   Factory* factory = CcTest::i_isolate()->factory();
 858   v8::HandleScope scope(CcTest::isolate());
 859
 860   char* foo = NewArray<char>(DEEP_ASCII_DEPTH);
 861   for (int i = 0; i < DEEP_ASCII_DEPTH; i++) {
 862     foo[i] = "foo "[i % 4];
 863   }
 864   Handle<String> string = factory->NewStringFromOneByte(
 865       OneByteVector(foo, DEEP_ASCII_DEPTH)).ToHandleChecked();
 866   Handle<String> foo_string = factory->NewStringFromStaticAscii("foo");
 867   for (int i = 0; i < DEEP_ASCII_DEPTH; i += 10) {
 868     string = factory->NewConsString(string, foo_string).ToHandleChecked();
 869   }
 870   Handle<String> flat_string =
 871       factory->NewConsString(string, foo_string).ToHandleChecked();
 872   String::Flatten(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(Object::ToSmi(isolate, results[i]).ToHandleChecked()->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->NewStringFromStaticAscii("parentparentparent");
1095   Handle<String> parent =
1096       factory->NewConsString(string, string).ToHandleChecked();
1097   CHECK(parent->IsConsString());
1098   CHECK(!parent->IsFlat());
1099   Handle<String> slice = factory->NewSubString(parent, 1, 25);
1100   // After slicing, the original string becomes a flat cons.
1101   CHECK(parent->IsFlat());
1102   CHECK(slice->IsSlicedString());
1103   CHECK_EQ(SlicedString::cast(*slice)->parent(),
1104            // Parent could have been short-circuited.
1105            parent->IsConsString() ? ConsString::cast(*parent)->first()
1106                                   : *parent);
1107   CHECK(SlicedString::cast(*slice)->parent()->IsSeqString());
1108   CHECK(slice->IsFlat());
1109 }
1110
1111
1112 class AsciiVectorResource : public v8::String::ExternalAsciiStringResource {
1113  public:
1114   explicit AsciiVectorResource(i::Vector<const char> vector)
1115       : data_(vector) {}
1116   virtual ~AsciiVectorResource() {}
1117   virtual size_t length() const { return data_.length(); }
1118   virtual const char* data() const { return data_.start(); }
1119  private:
1120   i::Vector<const char> data_;
1121 };
1122
1123
1124 TEST(SliceFromExternal) {
1125   FLAG_string_slices = true;
1126   CcTest::InitializeVM();
1127   Factory* factory = CcTest::i_isolate()->factory();
1128   v8::HandleScope scope(CcTest::isolate());
1129   AsciiVectorResource resource(
1130       i::Vector<const char>("abcdefghijklmnopqrstuvwxyz", 26));
1131   Handle<String> string =
1132       factory->NewExternalStringFromAscii(&resource).ToHandleChecked();
1133   CHECK(string->IsExternalString());
1134   Handle<String> slice = factory->NewSubString(string, 1, 25);
1135   CHECK(slice->IsSlicedString());
1136   CHECK(string->IsExternalString());
1137   CHECK_EQ(SlicedString::cast(*slice)->parent(), *string);
1138   CHECK(SlicedString::cast(*slice)->parent()->IsExternalString());
1139   CHECK(slice->IsFlat());
1140 }
1141
1142
1143 TEST(TrivialSlice) {
1144   // This tests whether a slice that contains the entire parent string
1145   // actually creates a new string (it should not).
1146   FLAG_string_slices = true;
1147   CcTest::InitializeVM();
1148   Factory* factory = CcTest::i_isolate()->factory();
1149   v8::HandleScope scope(CcTest::isolate());
1150   v8::Local<v8::Value> result;
1151   Handle<String> string;
1152   const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
1153   const char* check = "str.slice(0,26)";
1154   const char* crosscheck = "str.slice(1,25)";
1155
1156   CompileRun(init);
1157
1158   result = CompileRun(check);
1159   CHECK(result->IsString());
1160   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1161   CHECK(!string->IsSlicedString());
1162
1163   string = factory->NewSubString(string, 0, 26);
1164   CHECK(!string->IsSlicedString());
1165   result = CompileRun(crosscheck);
1166   CHECK(result->IsString());
1167   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1168   CHECK(string->IsSlicedString());
1169   CHECK_EQ("bcdefghijklmnopqrstuvwxy", string->ToCString().get());
1170 }
1171
1172
1173 TEST(SliceFromSlice) {
1174   // This tests whether a slice that contains the entire parent string
1175   // actually creates a new string (it should not).
1176   FLAG_string_slices = true;
1177   CcTest::InitializeVM();
1178   v8::HandleScope scope(CcTest::isolate());
1179   v8::Local<v8::Value> result;
1180   Handle<String> string;
1181   const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
1182   const char* slice = "var slice = str.slice(1,-1); slice";
1183   const char* slice_from_slice = "slice.slice(1,-1);";
1184
1185   CompileRun(init);
1186   result = CompileRun(slice);
1187   CHECK(result->IsString());
1188   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1189   CHECK(string->IsSlicedString());
1190   CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
1191   CHECK_EQ("bcdefghijklmnopqrstuvwxy", string->ToCString().get());
1192
1193   result = CompileRun(slice_from_slice);
1194   CHECK(result->IsString());
1195   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1196   CHECK(string->IsSlicedString());
1197   CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
1198   CHECK_EQ("cdefghijklmnopqrstuvwx", string->ToCString().get());
1199 }
1200
1201
1202 TEST(AsciiArrayJoin) {
1203   // Set heap limits.
1204   static const int K = 1024;
1205   v8::ResourceConstraints constraints;
1206   constraints.set_max_new_space_size(256 * K);
1207   constraints.set_max_old_space_size(4 * K * K);
1208   v8::SetResourceConstraints(CcTest::isolate(), &constraints);
1209
1210   // String s is made of 2^17 = 131072 'c' characters and a is an array
1211   // starting with 'bad', followed by 2^14 times the string s. That means the
1212   // total length of the concatenated strings is 2^31 + 3. So on 32bit systems
1213   // summing the lengths of the strings (as Smis) overflows and wraps.
1214   LocalContext context;
1215   v8::HandleScope scope(CcTest::isolate());
1216   v8::TryCatch try_catch;
1217   CHECK(CompileRun(
1218       "var two_14 = Math.pow(2, 14);"
1219       "var two_17 = Math.pow(2, 17);"
1220       "var s = Array(two_17 + 1).join('c');"
1221       "var a = ['bad'];"
1222       "for (var i = 1; i <= two_14; i++) a.push(s);"
1223       "a.join("");").IsEmpty());
1224   CHECK(try_catch.HasCaught());
1225 }
1226
1227
1228 static void CheckException(const char* source) {
1229   // An empty handle is returned upon exception.
1230   CHECK(CompileRun(source).IsEmpty());
1231 }
1232
1233
1234 TEST(RobustSubStringStub) {
1235   // This tests whether the SubStringStub can handle unsafe arguments.
1236   // If not recognized, those unsafe arguments lead to out-of-bounds reads.
1237   FLAG_allow_natives_syntax = true;
1238   CcTest::InitializeVM();
1239   v8::HandleScope scope(CcTest::isolate());
1240   v8::Local<v8::Value> result;
1241   Handle<String> string;
1242   CompileRun("var short = 'abcdef';");
1243
1244   // Invalid indices.
1245   CheckException("%_SubString(short,     0,    10000);");
1246   CheckException("%_SubString(short, -1234,        5);");
1247   CheckException("%_SubString(short,     5,        2);");
1248   // Special HeapNumbers.
1249   CheckException("%_SubString(short,     1, Infinity);");
1250   CheckException("%_SubString(short,   NaN,        5);");
1251   // String arguments.
1252   CheckException("%_SubString(short,    '2',     '5');");
1253   // Ordinary HeapNumbers can be handled (in runtime).
1254   result = CompileRun("%_SubString(short, Math.sqrt(4), 5.1);");
1255   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1256   CHECK_EQ("cde", string->ToCString().get());
1257
1258   CompileRun("var long = 'abcdefghijklmnopqrstuvwxyz';");
1259   // Invalid indices.
1260   CheckException("%_SubString(long,     0,    10000);");
1261   CheckException("%_SubString(long, -1234,       17);");
1262   CheckException("%_SubString(long,    17,        2);");
1263   // Special HeapNumbers.
1264   CheckException("%_SubString(long,     1, Infinity);");
1265   CheckException("%_SubString(long,   NaN,       17);");
1266   // String arguments.
1267   CheckException("%_SubString(long,    '2',    '17');");
1268   // Ordinary HeapNumbers within bounds can be handled (in runtime).
1269   result = CompileRun("%_SubString(long, Math.sqrt(4), 17.1);");
1270   string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1271   CHECK_EQ("cdefghijklmnopq", string->ToCString().get());
1272
1273   // Test that out-of-bounds substring of a slice fails when the indices
1274   // would have been valid for the underlying string.
1275   CompileRun("var slice = long.slice(1, 15);");
1276   CheckException("%_SubString(slice, 0, 17);");
1277 }
1278
1279
1280 TEST(StringReplaceAtomTwoByteResult) {
1281   CcTest::InitializeVM();
1282   v8::HandleScope scope(CcTest::isolate());
1283   LocalContext context;
1284   v8::Local<v8::Value> result = CompileRun(
1285       "var subject = 'ascii~only~string~'; "
1286       "var replace = '\x80';            "
1287       "subject.replace(/~/g, replace);  ");
1288   CHECK(result->IsString());
1289   Handle<String> string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1290   CHECK(string->IsSeqTwoByteString());
1291
1292   v8::Local<v8::String> expected = v8_str("ascii\x80only\x80string\x80");
1293   CHECK(expected->Equals(result));
1294 }
1295
1296
1297 TEST(IsAscii) {
1298   CHECK(String::IsAscii(static_cast<char*>(NULL), 0));
1299   CHECK(String::IsOneByte(static_cast<uc16*>(NULL), 0));
1300 }
1301
1302
1303
1304 template<typename Op, bool return_first>
1305 static uint16_t ConvertLatin1(uint16_t c) {
1306   uint32_t result[Op::kMaxWidth];
1307   int chars;
1308   chars = Op::Convert(c, 0, result, NULL);
1309   if (chars == 0) return 0;
1310   CHECK_LE(chars, static_cast<int>(sizeof(result)));
1311   if (!return_first && chars > 1) {
1312     return 0;
1313   }
1314   return result[0];
1315 }
1316
1317
1318 static void CheckCanonicalEquivalence(uint16_t c, uint16_t test) {
1319   uint16_t expect = ConvertLatin1<unibrow::Ecma262UnCanonicalize, true>(c);
1320   if (expect > unibrow::Latin1::kMaxChar) expect = 0;
1321   CHECK_EQ(expect, test);
1322 }
1323
1324
1325 TEST(Latin1IgnoreCase) {
1326   using namespace unibrow;
1327   for (uint16_t c = Latin1::kMaxChar + 1; c != 0; c++) {
1328     uint16_t lower = ConvertLatin1<ToLowercase, false>(c);
1329     uint16_t upper = ConvertLatin1<ToUppercase, false>(c);
1330     uint16_t test = Latin1::ConvertNonLatin1ToLatin1(c);
1331     // Filter out all character whose upper is not their lower or vice versa.
1332     if (lower == 0 && upper == 0) {
1333       CheckCanonicalEquivalence(c, test);
1334       continue;
1335     }
1336     if (lower > Latin1::kMaxChar && upper > Latin1::kMaxChar) {
1337       CheckCanonicalEquivalence(c, test);
1338       continue;
1339     }
1340     if (lower == 0 && upper != 0) {
1341       lower = ConvertLatin1<ToLowercase, false>(upper);
1342     }
1343     if (upper == 0 && lower != c) {
1344       upper = ConvertLatin1<ToUppercase, false>(lower);
1345     }
1346     if (lower > Latin1::kMaxChar && upper > Latin1::kMaxChar) {
1347       CheckCanonicalEquivalence(c, test);
1348       continue;
1349     }
1350     if (upper != c && lower != c) {
1351       CheckCanonicalEquivalence(c, test);
1352       continue;
1353     }
1354     CHECK_EQ(Min(upper, lower), test);
1355   }
1356 }
1357
1358
1359 class DummyResource: public v8::String::ExternalStringResource {
1360  public:
1361   virtual const uint16_t* data() const { return NULL; }
1362   virtual size_t length() const { return 1 << 30; }
1363 };
1364
1365
1366 class DummyOneByteResource: public v8::String::ExternalOneByteStringResource {
1367  public:
1368   virtual const char* data() const { return NULL; }
1369   virtual size_t length() const { return 1 << 30; }
1370 };
1371
1372
1373 TEST(InvalidExternalString) {
1374   CcTest::InitializeVM();
1375   LocalContext context;
1376   Isolate* isolate = CcTest::i_isolate();
1377   { HandleScope scope(isolate);
1378     DummyOneByteResource r;
1379     CHECK(isolate->factory()->NewExternalStringFromAscii(&r).is_null());
1380     CHECK(isolate->has_pending_exception());
1381     isolate->clear_pending_exception();
1382   }
1383
1384   { HandleScope scope(isolate);
1385     DummyResource r;
1386     CHECK(isolate->factory()->NewExternalStringFromTwoByte(&r).is_null());
1387     CHECK(isolate->has_pending_exception());
1388     isolate->clear_pending_exception();
1389   }
1390 }
1391
1392
1393 #define INVALID_STRING_TEST(FUN, TYPE)                                         \
1394   TEST(StringOOM##FUN) {                                                       \
1395     CcTest::InitializeVM();                                                    \
1396     LocalContext context;                                                      \
1397     Isolate* isolate = CcTest::i_isolate();                                    \
1398     STATIC_ASSERT(String::kMaxLength < kMaxInt);                               \
1399     static const int invalid = String::kMaxLength + 1;                         \
1400     HandleScope scope(isolate);                                                \
1401     Vector<TYPE> dummy = Vector<TYPE>::New(invalid);                           \
1402     CHECK(isolate->factory()->FUN(Vector<const TYPE>::cast(dummy)).is_null()); \
1403     memset(dummy.start(), 0x20, dummy.length() * sizeof(TYPE));                \
1404     CHECK(isolate->has_pending_exception());                                   \
1405     isolate->clear_pending_exception();                                        \
1406     dummy.Dispose();                                                           \
1407   }
1408
1409 INVALID_STRING_TEST(NewStringFromAscii, char)
1410 INVALID_STRING_TEST(NewStringFromUtf8, char)
1411 INVALID_STRING_TEST(NewStringFromOneByte, uint8_t)
1412
1413 #undef INVALID_STRING_TEST