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