test-strings.cc 49.4 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// 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 31 32 33 34
// of ConsStrings.  These operations may not be very fast, but they
// should be possible without getting errors due to too deep recursion.

#include <stdlib.h>

35
#include "src/v8.h"
36

37 38
#include "src/api.h"
#include "src/factory.h"
39
#include "src/messages.h"
40
#include "src/objects.h"
41
#include "src/unicode-decoder.h"
42
#include "test/cctest/cctest.h"
43

44
// Adapted from http://en.wikipedia.org/wiki/Multiply-with-carry
45
class MyRandomNumberGenerator {
46
 public:
47
  MyRandomNumberGenerator() {
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
    init();
  }

  void init(uint32_t seed = 0x5688c73e) {
    static const uint32_t phi = 0x9e3779b9;
    c = 362436;
    i = kQSize-1;
    Q[0] = seed;
    Q[1] = seed + phi;
    Q[2] = seed + phi + phi;
    for (unsigned j = 3; j < kQSize; j++) {
      Q[j] = Q[j - 3] ^ Q[j - 2] ^ phi ^ j;
    }
  }

  uint32_t next() {
    uint64_t a = 18782;
    uint32_t r = 0xfffffffe;
    i = (i + 1) & (kQSize-1);
    uint64_t t = a * Q[i] + c;
    c = (t >> 32);
    uint32_t x = static_cast<uint32_t>(t + c);
    if (x < c) {
      x++;
      c++;
    }
    return (Q[i] = r - x);
  }

  uint32_t next(int max) {
    return next() % max;
  }

  bool next(double threshold) {
82
    DCHECK(threshold >= 0.0 && threshold <= 1.0);
83 84 85 86 87 88 89 90 91 92 93 94 95
    if (threshold == 1.0) return true;
    if (threshold == 0.0) return false;
    uint32_t value = next() % 100000;
    return threshold > static_cast<double>(value)/100000.0;
  }

 private:
  static const uint32_t kQSize = 4096;
  uint32_t Q[kQSize];
  uint32_t c;
  uint32_t i;
};

96 97 98 99 100 101 102 103

using namespace v8::internal;


static const int DEEP_DEPTH = 8 * 1024;
static const int SUPER_DEEP_DEPTH = 80 * 1024;


104
class Resource: public v8::String::ExternalStringResource {
105
 public:
106 107
  Resource(const uc16* data, size_t length): data_(data), length_(length) {}
  ~Resource() { i::DeleteArray(data_); }
108 109 110 111 112 113 114 115 116
  virtual const uint16_t* data() const { return data_; }
  virtual size_t length() const { return length_; }

 private:
  const uc16* data_;
  size_t length_;
};


117
class OneByteResource : public v8::String::ExternalOneByteStringResource {
118
 public:
119
  OneByteResource(const char* data, size_t length)
120
      : data_(data), length_(length) {}
121
  ~OneByteResource() { i::DeleteArray(data_); }
122 123 124 125 126 127 128 129 130
  virtual const char* data() const { return data_; }
  virtual size_t length() const { return length_; }

 private:
  const char* data_;
  size_t length_;
};


131 132 133
static void InitializeBuildingBlocks(Handle<String>* building_blocks,
                                     int bb_length,
                                     bool long_blocks,
134
                                     MyRandomNumberGenerator* rng) {
135 136
  // A list of pointers that we don't have any interest in cleaning up.
  // If they are reachable from a root then leak detection won't complain.
137
  Isolate* isolate = CcTest::i_isolate();
138
  Factory* factory = isolate->factory();
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
  for (int i = 0; i < bb_length; i++) {
    int len = rng->next(16);
    int slice_head_chars = 0;
    int slice_tail_chars = 0;
    int slice_depth = 0;
    for (int j = 0; j < 3; j++) {
      if (rng->next(0.35)) slice_depth++;
    }
    // Must truncate something for a slice string. Loop until
    // at least one end will be sliced.
    while (slice_head_chars == 0 && slice_tail_chars == 0) {
      slice_head_chars = rng->next(15);
      slice_tail_chars = rng->next(12);
    }
    if (long_blocks) {
      // Generate building blocks which will never be merged
      len += ConsString::kMinLength + 1;
    } else if (len > 14) {
157 158
      len += 1234;
    }
159 160 161 162 163
    // Don't slice 0 length strings.
    if (len == 0) slice_depth = 0;
    int slice_length = slice_depth*(slice_head_chars + slice_tail_chars);
    len += slice_length;
    switch (rng->next(4)) {
164 165 166
      case 0: {
        uc16 buf[2000];
        for (int j = 0; j < len; j++) {
167
          buf[j] = rng->next(0x10000);
168
        }
169 170
        building_blocks[i] = factory->NewStringFromTwoByte(
            Vector<const uc16>(buf, len)).ToHandleChecked();
171
        for (int j = 0; j < len; j++) {
172
          CHECK_EQ(buf[j], building_blocks[i]->Get(j));
173 174 175 176 177 178
        }
        break;
      }
      case 1: {
        char buf[2000];
        for (int j = 0; j < len; j++) {
179
          buf[j] = rng->next(0x80);
180
        }
181 182
        building_blocks[i] = factory->NewStringFromAscii(
            Vector<const char>(buf, len)).ToHandleChecked();
183
        for (int j = 0; j < len; j++) {
184
          CHECK_EQ(buf[j], building_blocks[i]->Get(j));
185 186 187 188
        }
        break;
      }
      case 2: {
189
        uc16* buf = NewArray<uc16>(len);
190
        for (int j = 0; j < len; j++) {
191
          buf[j] = rng->next(0x10000);
192
        }
193 194 195 196
        Resource* resource = new Resource(buf, len);
        building_blocks[i] =
            v8::Utils::OpenHandle(
                *v8::String::NewExternal(CcTest::isolate(), resource));
197
        for (int j = 0; j < len; j++) {
198
          CHECK_EQ(buf[j], building_blocks[i]->Get(j));
199 200 201 202
        }
        break;
      }
      case 3: {
203
        char* buf = NewArray<char>(len);
204
        for (int j = 0; j < len; j++) {
205
          buf[j] = rng->next(0x80);
206
        }
207
        OneByteResource* resource = new OneByteResource(buf, len);
208 209 210
        building_blocks[i] =
            v8::Utils::OpenHandle(
                *v8::String::NewExternal(CcTest::isolate(), resource));
211
        for (int j = 0; j < len; j++) {
212
          CHECK_EQ(buf[j], building_blocks[i]->Get(j));
213 214 215 216
        }
        break;
      }
    }
217
    for (int j = slice_depth; j > 0; j--) {
218
      building_blocks[i] = factory->NewSubString(
219 220 221 222 223
          building_blocks[i],
          slice_head_chars,
          building_blocks[i]->length() - slice_tail_chars);
    }
    CHECK(len == building_blocks[i]->length() + slice_length);
224 225 226 227
  }
}


228 229 230 231 232 233 234
class ConsStringStats {
 public:
  ConsStringStats() {
    Reset();
  }
  void Reset();
  void VerifyEqual(const ConsStringStats& that) const;
235 236 237 238 239
  int leaves_;
  int empty_leaves_;
  int chars_;
  int left_traversals_;
  int right_traversals_;
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254
 private:
  DISALLOW_COPY_AND_ASSIGN(ConsStringStats);
};


void ConsStringStats::Reset() {
  leaves_ = 0;
  empty_leaves_ = 0;
  chars_ = 0;
  left_traversals_ = 0;
  right_traversals_ = 0;
}


void ConsStringStats::VerifyEqual(const ConsStringStats& that) const {
255 256 257 258 259
  CHECK_EQ(this->leaves_, that.leaves_);
  CHECK_EQ(this->empty_leaves_, that.empty_leaves_);
  CHECK_EQ(this->chars_, that.chars_);
  CHECK_EQ(this->left_traversals_, that.left_traversals_);
  CHECK_EQ(this->right_traversals_, that.right_traversals_);
260 261 262 263 264
}


class ConsStringGenerationData {
 public:
265
  static const int kNumberOfBuildingBlocks = 256;
266
  explicit ConsStringGenerationData(bool long_blocks);
267
  void Reset();
268 269
  inline Handle<String> block(int offset);
  inline Handle<String> block(uint32_t offset);
270 271 272 273 274
  // Input variables.
  double early_termination_threshold_;
  double leftness_;
  double rightness_;
  double empty_leaf_threshold_;
275
  int max_leaves_;
276
  // Cached data.
277
  Handle<String> building_blocks_[kNumberOfBuildingBlocks];
278
  String* empty_string_;
279
  MyRandomNumberGenerator rng_;
280 281
  // Stats.
  ConsStringStats stats_;
282
  int early_terminations_;
283 284 285 286 287
 private:
  DISALLOW_COPY_AND_ASSIGN(ConsStringGenerationData);
};


288
ConsStringGenerationData::ConsStringGenerationData(bool long_blocks) {
289 290
  rng_.init();
  InitializeBuildingBlocks(
291
      building_blocks_, kNumberOfBuildingBlocks, long_blocks, &rng_);
292
  empty_string_ = CcTest::heap()->empty_string();
293 294 295 296
  Reset();
}


297 298 299 300 301 302 303 304 305 306 307
Handle<String> ConsStringGenerationData::block(uint32_t offset) {
  return building_blocks_[offset % kNumberOfBuildingBlocks ];
}


Handle<String> ConsStringGenerationData::block(int offset) {
  CHECK_GE(offset, 0);
  return building_blocks_[offset % kNumberOfBuildingBlocks];
}


308 309 310 311 312 313 314 315
void ConsStringGenerationData::Reset() {
  early_termination_threshold_ = 0.01;
  leftness_ = 0.75;
  rightness_ = 0.75;
  empty_leaf_threshold_ = 0.02;
  max_leaves_ = 1000;
  stats_.Reset();
  early_terminations_ = 0;
316
  rng_.init();
317 318 319
}


320
void AccumulateStats(ConsString* cons_string, ConsStringStats* stats) {
321 322 323 324
  int left_length = cons_string->first()->length();
  int right_length = cons_string->second()->length();
  CHECK(cons_string->length() == left_length + right_length);
  // Check left side.
325 326
  bool left_is_cons = cons_string->first()->IsConsString();
  if (left_is_cons) {
327
    stats->left_traversals_++;
328
    AccumulateStats(ConsString::cast(cons_string->first()), stats);
329 330 331 332 333 334 335 336
  } else {
    CHECK_NE(left_length, 0);
    stats->leaves_++;
    stats->chars_ += left_length;
  }
  // Check right side.
  if (cons_string->second()->IsConsString()) {
    stats->right_traversals_++;
337
    AccumulateStats(ConsString::cast(cons_string->second()), stats);
338
  } else {
339 340 341 342
    if (right_length == 0) {
      stats->empty_leaves_++;
      CHECK(!left_is_cons);
    }
343 344 345 346 347 348
    stats->leaves_++;
    stats->chars_ += right_length;
  }
}


349
void AccumulateStats(Handle<String> cons_string, ConsStringStats* stats) {
350
  DisallowHeapAllocation no_allocation;
351 352 353 354 355 356 357 358 359
  if (cons_string->IsConsString()) {
    return AccumulateStats(ConsString::cast(*cons_string), stats);
  }
  // This string got flattened by gc.
  stats->chars_ += cons_string->length();
}


void AccumulateStatsWithOperator(
360
    ConsString* cons_string, ConsStringStats* stats) {
361
  ConsStringIterator iter(cons_string);
362 363
  String* string;
  int offset;
364
  while (NULL != (string = iter.Next(&offset))) {
365
    // Accumulate stats.
366
    CHECK_EQ(0, offset);
367 368 369
    stats->leaves_++;
    stats->chars_ += string->length();
  }
370 371 372 373 374 375
}


void VerifyConsString(Handle<String> root, ConsStringGenerationData* data) {
  // Verify basic data.
  CHECK(root->IsConsString());
376
  CHECK_EQ(root->length(), data->stats_.chars_);
377 378
  // Recursive verify.
  ConsStringStats stats;
379
  AccumulateStats(ConsString::cast(*root), &stats);
380 381 382
  stats.VerifyEqual(data->stats_);
  // Iteratively verify.
  stats.Reset();
383
  AccumulateStatsWithOperator(ConsString::cast(*root), &stats);
384 385 386 387 388 389 390 391 392 393 394 395
  // Don't see these. Must copy over.
  stats.empty_leaves_ = data->stats_.empty_leaves_;
  stats.left_traversals_ = data->stats_.left_traversals_;
  stats.right_traversals_ = data->stats_.right_traversals_;
  // Adjust total leaves to compensate.
  stats.leaves_ += stats.empty_leaves_;
  stats.VerifyEqual(data->stats_);
}


static Handle<String> ConstructRandomString(ConsStringGenerationData* data,
                                            unsigned max_recursion) {
396
  Factory* factory = CcTest::i_isolate()->factory();
397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415
  // Compute termination characteristics.
  bool terminate = false;
  bool flat = data->rng_.next(data->empty_leaf_threshold_);
  bool terminate_early = data->rng_.next(data->early_termination_threshold_);
  if (terminate_early) data->early_terminations_++;
  // The obvious condition.
  terminate |= max_recursion == 0;
  // Flat cons string terminate by definition.
  terminate |= flat;
  // Cap for max leaves.
  terminate |= data->stats_.leaves_ >= data->max_leaves_;
  // Roll the dice.
  terminate |= terminate_early;
  // Compute termination characteristics for each side.
  bool terminate_left = terminate || !data->rng_.next(data->leftness_);
  bool terminate_right = terminate || !data->rng_.next(data->rightness_);
  // Generate left string.
  Handle<String> left;
  if (terminate_left) {
416
    left = data->block(data->rng_.next());
417 418 419 420 421 422 423 424
    data->stats_.leaves_++;
    data->stats_.chars_ += left->length();
  } else {
    data->stats_.left_traversals_++;
  }
  // Generate right string.
  Handle<String> right;
  if (terminate_right) {
425
    right = data->block(data->rng_.next());
426 427 428 429 430
    data->stats_.leaves_++;
    data->stats_.chars_ += right->length();
  } else {
    data->stats_.right_traversals_++;
  }
431 432 433 434 435 436 437 438 439 440 441
  // Generate the necessary sub-nodes recursively.
  if (!terminate_right) {
    // Need to balance generation fairly.
    if (!terminate_left && data->rng_.next(0.5)) {
      left = ConstructRandomString(data, max_recursion - 1);
    }
    right = ConstructRandomString(data, max_recursion - 1);
  }
  if (!terminate_left && left.is_null()) {
    left = ConstructRandomString(data, max_recursion - 1);
  }
442
  // Build the cons string.
443
  Handle<String> root = factory->NewConsString(left, right).ToHandleChecked();
444 445 446 447
  CHECK(root->IsConsString() && !root->IsFlat());
  // Special work needed for flat string.
  if (flat) {
    data->stats_.empty_leaves_++;
448
    String::Flatten(root);
449 450 451 452 453 454
    CHECK(root->IsConsString() && root->IsFlat());
  }
  return root;
}


455 456 457
static Handle<String> ConstructLeft(
    ConsStringGenerationData* data,
    int depth) {
458
  Factory* factory = CcTest::i_isolate()->factory();
459
  Handle<String> answer = factory->NewStringFromStaticChars("");
460 461 462
  data->stats_.leaves_++;
  for (int i = 0; i < depth; i++) {
    Handle<String> block = data->block(i);
463 464
    Handle<String> next =
        factory->NewConsString(answer, block).ToHandleChecked();
465 466 467 468 469 470 471
    if (next->IsConsString()) data->stats_.leaves_++;
    data->stats_.chars_ += block->length();
    answer = next;
  }
  data->stats_.left_traversals_ = data->stats_.leaves_ - 2;
  return answer;
}
472 473


474 475 476
static Handle<String> ConstructRight(
    ConsStringGenerationData* data,
    int depth) {
477
  Factory* factory = CcTest::i_isolate()->factory();
478
  Handle<String> answer = factory->NewStringFromStaticChars("");
479 480 481
  data->stats_.leaves_++;
  for (int i = depth - 1; i >= 0; i--) {
    Handle<String> block = data->block(i);
482 483
    Handle<String> next =
        factory->NewConsString(block, answer).ToHandleChecked();
484 485 486
    if (next->IsConsString()) data->stats_.leaves_++;
    data->stats_.chars_ += block->length();
    answer = next;
487
  }
488 489 490 491 492 493 494 495 496
  data->stats_.right_traversals_ = data->stats_.leaves_ - 2;
  return answer;
}


static Handle<String> ConstructBalancedHelper(
    ConsStringGenerationData* data,
    int from,
    int to) {
497
  Factory* factory = CcTest::i_isolate()->factory();
498 499 500 501 502 503 504 505
  CHECK(to > from);
  if (to - from == 1) {
    data->stats_.chars_ += data->block(from)->length();
    return data->block(from);
  }
  if (to - from == 2) {
    data->stats_.chars_ += data->block(from)->length();
    data->stats_.chars_ += data->block(from+1)->length();
506 507
    return factory->NewConsString(data->block(from), data->block(from+1))
        .ToHandleChecked();
508 509 510 511 512 513 514
  }
  Handle<String> part1 =
    ConstructBalancedHelper(data, from, from + ((to - from) / 2));
  Handle<String> part2 =
    ConstructBalancedHelper(data, from + ((to - from) / 2), to);
  if (part1->IsConsString()) data->stats_.left_traversals_++;
  if (part2->IsConsString()) data->stats_.right_traversals_++;
515
  return factory->NewConsString(part1, part2).ToHandleChecked();
516 517 518 519 520 521 522 523 524 525 526 527 528 529
}


static Handle<String> ConstructBalanced(
    ConsStringGenerationData* data, int depth = DEEP_DEPTH) {
  Handle<String> string = ConstructBalancedHelper(data, 0, depth);
  data->stats_.leaves_ =
      data->stats_.left_traversals_ + data->stats_.right_traversals_ + 2;
  return string;
}


static void Traverse(Handle<String> s1, Handle<String> s2) {
  int i = 0;
530 531
  StringCharacterStream character_stream_1(*s1);
  StringCharacterStream character_stream_2(*s2);
532
  while (character_stream_1.HasMore()) {
533
    CHECK(character_stream_2.HasMore());
534
    uint16_t c = character_stream_1.GetNext();
535 536 537 538 539 540 541 542 543 544 545 546
    CHECK_EQ(c, character_stream_2.GetNext());
    i++;
  }
  CHECK(!character_stream_1.HasMore());
  CHECK(!character_stream_2.HasMore());
  CHECK_EQ(s1->length(), i);
  CHECK_EQ(s2->length(), i);
}


static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars) {
  int i = 0;
547 548
  StringCharacterStream character_stream_1(*s1);
  StringCharacterStream character_stream_2(*s2);
549
  while (character_stream_1.HasMore() && i < chars) {
550
    CHECK(character_stream_2.HasMore());
551
    uint16_t c = character_stream_1.GetNext();
552 553 554 555 556 557 558 559 560 561
    CHECK_EQ(c, character_stream_2.GetNext());
    i++;
  }
  s1->Get(s1->length() - 1);
  s2->Get(s2->length() - 1);
}


TEST(Traverse) {
  printf("TestTraverse\n");
562 563
  CcTest::InitializeVM();
  v8::HandleScope scope(CcTest::isolate());
564
  ConsStringGenerationData data(false);
565
  Handle<String> flat = ConstructBalanced(&data);
566
  String::Flatten(flat);
567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585
  Handle<String> left_asymmetric = ConstructLeft(&data, DEEP_DEPTH);
  Handle<String> right_asymmetric = ConstructRight(&data, DEEP_DEPTH);
  Handle<String> symmetric = ConstructBalanced(&data);
  printf("1\n");
  Traverse(flat, symmetric);
  printf("2\n");
  Traverse(flat, left_asymmetric);
  printf("3\n");
  Traverse(flat, right_asymmetric);
  printf("4\n");
  Handle<String> left_deep_asymmetric =
      ConstructLeft(&data, SUPER_DEEP_DEPTH);
  Handle<String> right_deep_asymmetric =
      ConstructRight(&data, SUPER_DEEP_DEPTH);
  printf("5\n");
  TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
  printf("6\n");
  TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
  printf("7\n");
586
  String::Flatten(left_asymmetric);
587 588 589
  printf("10\n");
  Traverse(flat, left_asymmetric);
  printf("11\n");
590
  String::Flatten(right_asymmetric);
591 592 593
  printf("12\n");
  Traverse(flat, right_asymmetric);
  printf("14\n");
594
  String::Flatten(symmetric);
595 596 597
  printf("15\n");
  Traverse(flat, symmetric);
  printf("16\n");
598
  String::Flatten(left_deep_asymmetric);
599
  printf("18\n");
600 601 602 603 604 605
}


static void VerifyCharacterStream(
    String* flat_string, String* cons_string) {
  // Do not want to test ConString traversal on flat string.
606
  CHECK(flat_string->IsFlat() && !flat_string->IsConsString());
607 608 609 610 611 612
  CHECK(cons_string->IsConsString());
  // TODO(dcarney) Test stream reset as well.
  int length = flat_string->length();
  // Iterate start search in multiple places in the string.
  int outer_iterations = length > 20 ? 20 : length;
  for (int j = 0; j <= outer_iterations; j++) {
613
    int offset = length * j / outer_iterations;
614 615 616
    if (offset < 0) offset = 0;
    // Want to test the offset == length case.
    if (offset > length) offset = length;
617 618
    StringCharacterStream flat_stream(flat_string, offset);
    StringCharacterStream cons_stream(cons_string, offset);
619 620 621 622 623 624 625 626 627 628 629 630 631
    for (int i = offset; i < length; i++) {
      uint16_t c = flat_string->Get(i);
      CHECK(flat_stream.HasMore());
      CHECK(cons_stream.HasMore());
      CHECK_EQ(c, flat_stream.GetNext());
      CHECK_EQ(c, cons_stream.GetNext());
    }
    CHECK(!flat_stream.HasMore());
    CHECK(!cons_stream.HasMore());
  }
}


632 633
static inline void PrintStats(const ConsStringGenerationData& data) {
#ifdef DEBUG
634 635 636 637 638
  printf("%s: [%u], %s: [%u], %s: [%u], %s: [%u], %s: [%u], %s: [%u]\n",
         "leaves", data.stats_.leaves_, "empty", data.stats_.empty_leaves_,
         "chars", data.stats_.chars_, "lefts", data.stats_.left_traversals_,
         "rights", data.stats_.right_traversals_, "early_terminations",
         data.early_terminations_);
639 640 641 642 643 644
#endif
}


template<typename BuildString>
void TestStringCharacterStream(BuildString build, int test_cases) {
645
  CcTest::InitializeVM();
646
  Isolate* isolate = CcTest::i_isolate();
647
  HandleScope outer_scope(isolate);
648
  ConsStringGenerationData data(true);
649
  for (int i = 0; i < test_cases; i++) {
650 651
    printf("%d\n", i);
    HandleScope inner_scope(isolate);
652
    AlwaysAllocateScope always_allocate(isolate);
653 654 655 656 657
    // Build flat version of cons string.
    Handle<String> flat_string = build(i, &data);
    ConsStringStats flat_string_stats;
    AccumulateStats(flat_string, &flat_string_stats);
    // Flatten string.
658
    String::Flatten(flat_string);
659 660 661 662
    // Build unflattened version of cons string to test.
    Handle<String> cons_string = build(i, &data);
    ConsStringStats cons_string_stats;
    AccumulateStats(cons_string, &cons_string_stats);
663
    DisallowHeapAllocation no_allocation;
664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682
    PrintStats(data);
    // Full verify of cons string.
    cons_string_stats.VerifyEqual(flat_string_stats);
    cons_string_stats.VerifyEqual(data.stats_);
    VerifyConsString(cons_string, &data);
    String* flat_string_ptr =
        flat_string->IsConsString() ?
        ConsString::cast(*flat_string)->first() :
        *flat_string;
    VerifyCharacterStream(flat_string_ptr, *cons_string);
  }
}


static const int kCharacterStreamNonRandomCases = 8;


static Handle<String> BuildEdgeCaseConsString(
    int test_case, ConsStringGenerationData* data) {
683
  Factory* factory = CcTest::i_isolate()->factory();
684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700
  data->Reset();
  switch (test_case) {
    case 0:
      return ConstructBalanced(data, 71);
    case 1:
      return ConstructLeft(data, 71);
    case 2:
      return ConstructRight(data, 71);
    case 3:
      return ConstructLeft(data, 10);
    case 4:
      return ConstructRight(data, 10);
    case 5:
      // 2 element balanced tree.
      data->stats_.chars_ += data->block(0)->length();
      data->stats_.chars_ += data->block(1)->length();
      data->stats_.leaves_ += 2;
701 702
      return factory->NewConsString(data->block(0), data->block(1))
                 .ToHandleChecked();
703 704 705 706 707 708 709 710
    case 6:
      // Simple flattened tree.
      data->stats_.chars_ += data->block(0)->length();
      data->stats_.chars_ += data->block(1)->length();
      data->stats_.leaves_ += 2;
      data->stats_.empty_leaves_ += 1;
      {
        Handle<String> string =
711 712
            factory->NewConsString(data->block(0), data->block(1))
                .ToHandleChecked();
713
        String::Flatten(string);
714 715 716 717 718 719 720 721 722 723 724 725
        return string;
      }
    case 7:
      // Left node flattened.
      data->stats_.chars_ += data->block(0)->length();
      data->stats_.chars_ += data->block(1)->length();
      data->stats_.chars_ += data->block(2)->length();
      data->stats_.leaves_ += 3;
      data->stats_.empty_leaves_ += 1;
      data->stats_.left_traversals_ += 1;
      {
        Handle<String> left =
726 727
            factory->NewConsString(data->block(0), data->block(1))
                .ToHandleChecked();
728
        String::Flatten(left);
729
        return factory->NewConsString(left, data->block(2)).ToHandleChecked();
730 731 732 733 734 735 736 737 738 739 740 741 742
      }
    case 8:
      // Left node and right node flattened.
      data->stats_.chars_ += data->block(0)->length();
      data->stats_.chars_ += data->block(1)->length();
      data->stats_.chars_ += data->block(2)->length();
      data->stats_.chars_ += data->block(3)->length();
      data->stats_.leaves_ += 4;
      data->stats_.empty_leaves_ += 2;
      data->stats_.left_traversals_ += 1;
      data->stats_.right_traversals_ += 1;
      {
        Handle<String> left =
743 744
            factory->NewConsString(data->block(0), data->block(1))
                .ToHandleChecked();
745
        String::Flatten(left);
746
        Handle<String> right =
747 748
            factory->NewConsString(data->block(2), data->block(2))
                .ToHandleChecked();
749
        String::Flatten(right);
750
        return factory->NewConsString(left, right).ToHandleChecked();
751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822
      }
  }
  UNREACHABLE();
  return Handle<String>();
}


TEST(StringCharacterStreamEdgeCases) {
  printf("TestStringCharacterStreamEdgeCases\n");
  TestStringCharacterStream(
      BuildEdgeCaseConsString, kCharacterStreamNonRandomCases);
}


static const int kBalances = 3;
static const int kTreeLengths = 4;
static const int kEmptyLeaves = 4;
static const int kUniqueRandomParameters =
    kBalances*kTreeLengths*kEmptyLeaves;


static void InitializeGenerationData(
    int test_case, ConsStringGenerationData* data) {
  // Clear the settings and reinit the rng.
  data->Reset();
  // Spin up the rng to a known location that is unique per test.
  static const int kPerTestJump = 501;
  for (int j = 0; j < test_case*kPerTestJump; j++) {
    data->rng_.next();
  }
  // Choose balanced, left or right heavy trees.
  switch (test_case % kBalances) {
    case 0:
      // Nothing to do.  Already balanced.
      break;
    case 1:
      // Left balanced.
      data->leftness_ = 0.90;
      data->rightness_ = 0.15;
      break;
    case 2:
      // Right balanced.
      data->leftness_ = 0.15;
      data->rightness_ = 0.90;
      break;
    default:
      UNREACHABLE();
      break;
  }
  // Must remove the influence of the above decision.
  test_case /= kBalances;
  // Choose tree length.
  switch (test_case % kTreeLengths) {
    case 0:
      data->max_leaves_ = 16;
      data->early_termination_threshold_ = 0.2;
      break;
    case 1:
      data->max_leaves_ = 50;
      data->early_termination_threshold_ = 0.05;
      break;
    case 2:
      data->max_leaves_ = 500;
      data->early_termination_threshold_ = 0.03;
      break;
    case 3:
      data->max_leaves_ = 5000;
      data->early_termination_threshold_ = 0.001;
      break;
    default:
      UNREACHABLE();
      break;
823
  }
824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841
  // Must remove the influence of the above decision.
  test_case /= kTreeLengths;
  // Choose how much we allow empty nodes, including not at all.
  data->empty_leaf_threshold_ =
      0.03 * static_cast<double>(test_case % kEmptyLeaves);
}


static Handle<String> BuildRandomConsString(
    int test_case, ConsStringGenerationData* data) {
  InitializeGenerationData(test_case, data);
  return ConstructRandomString(data, 200);
}


TEST(StringCharacterStreamRandom) {
  printf("StringCharacterStreamRandom\n");
  TestStringCharacterStream(BuildRandomConsString, kUniqueRandomParameters*7);
842 843 844
}


845
static const int kDeepOneByteDepth = 100000;
846 847


848
TEST(DeepOneByte) {
849
  CcTest::InitializeVM();
850
  Factory* factory = CcTest::i_isolate()->factory();
851
  v8::HandleScope scope(CcTest::isolate());
852

853 854
  char* foo = NewArray<char>(kDeepOneByteDepth);
  for (int i = 0; i < kDeepOneByteDepth; i++) {
855 856
    foo[i] = "foo "[i % 4];
  }
857 858 859 860 861
  Handle<String> string =
      factory->NewStringFromOneByte(OneByteVector(foo, kDeepOneByteDepth))
          .ToHandleChecked();
  Handle<String> foo_string = factory->NewStringFromStaticChars("foo");
  for (int i = 0; i < kDeepOneByteDepth; i += 10) {
862
    string = factory->NewConsString(string, foo_string).ToHandleChecked();
863
  }
864 865
  Handle<String> flat_string =
      factory->NewConsString(string, foo_string).ToHandleChecked();
866
  String::Flatten(flat_string);
867 868

  for (int i = 0; i < 500; i++) {
869
    TraverseFirst(flat_string, string, kDeepOneByteDepth);
870
  }
871
  DeleteArray<char>(foo);
872
}
873 874 875 876


TEST(Utf8Conversion) {
  // Smoke test for converting strings to utf-8.
877 878
  CcTest::InitializeVM();
  v8::HandleScope handle_scope(CcTest::isolate());
879 880 881
  // A simple one-byte string
  const char* one_byte_string = "abcdef12345";
  int len = v8::String::NewFromUtf8(CcTest::isolate(), one_byte_string,
882
                                    v8::String::kNormalString,
883 884 885
                                    StrLength(one_byte_string))->Utf8Length();
  CHECK_EQ(StrLength(one_byte_string), len);
  // A mixed one-byte and two-byte string
886 887 888 889 890 891 892
  // U+02E4 -> CB A4
  // U+0064 -> 64
  // U+12E4 -> E1 8B A4
  // U+0030 -> 30
  // U+3045 -> E3 81 85
  const uint16_t mixed_string[] = {0x02E4, 0x0064, 0x12E4, 0x0030, 0x3045};
  // The characters we expect to be output
893
  const unsigned char as_utf8[11] = {0xCB, 0xA4, 0x64, 0xE1, 0x8B, 0xA4, 0x30,
894 895 896
      0xE3, 0x81, 0x85, 0x00};
  // The number of bytes expected to be written for each length
  const int lengths[12] = {0, 0, 2, 3, 3, 3, 6, 7, 7, 7, 10, 11};
897
  const int char_lengths[12] = {0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5};
898 899
  v8::Handle<v8::String> mixed = v8::String::NewFromTwoByte(
      CcTest::isolate(), mixed_string, v8::String::kNormalString, 5);
900 901 902
  CHECK_EQ(10, mixed->Utf8Length());
  // Try encoding the string with all capacities
  char buffer[11];
903
  const char kNoChar = static_cast<char>(-1);
904 905 906
  for (int i = 0; i <= 11; i++) {
    // Clear the buffer before reusing it
    for (int j = 0; j < 11; j++)
907
      buffer[j] = kNoChar;
908 909
    int chars_written;
    int written = mixed->WriteUtf8(buffer, i, &chars_written);
910
    CHECK_EQ(lengths[i], written);
911
    CHECK_EQ(char_lengths[i], chars_written);
912 913
    // Check that the contents are correct
    for (int j = 0; j < lengths[i]; j++)
914
      CHECK_EQ(as_utf8[j], static_cast<unsigned char>(buffer[j]));
915 916
    // Check that the rest of the buffer hasn't been touched
    for (int j = lengths[i]; j < 11; j++)
917
      CHECK_EQ(kNoChar, buffer[j]);
918 919
  }
}
920 921


922
TEST(ExternalShortStringAdd) {
923
  LocalContext context;
924
  v8::HandleScope handle_scope(CcTest::isolate());
925

926 927
  // Make sure we cover all always-flat lengths and at least one above.
  static const int kMaxLength = 20;
928
  CHECK_GT(kMaxLength, i::ConsString::kMinLength);
929 930

  // Allocate two JavaScript arrays for holding short strings.
931
  v8::Handle<v8::Array> one_byte_external_strings =
932
      v8::Array::New(CcTest::isolate(), kMaxLength + 1);
933
  v8::Handle<v8::Array> non_one_byte_external_strings =
934
      v8::Array::New(CcTest::isolate(), kMaxLength + 1);
935

936
  // Generate short one-byte and two-byte external strings.
937
  for (int i = 0; i <= kMaxLength; i++) {
938
    char* one_byte = NewArray<char>(i + 1);
939
    for (int j = 0; j < i; j++) {
940
      one_byte[j] = 'a';
941 942 943
    }
    // Terminating '\0' is left out on purpose. It is not required for external
    // string data.
944 945 946
    OneByteResource* one_byte_resource = new OneByteResource(one_byte, i);
    v8::Local<v8::String> one_byte_external_string =
        v8::String::NewExternal(CcTest::isolate(), one_byte_resource);
947

948 949 950
    one_byte_external_strings->Set(v8::Integer::New(CcTest::isolate(), i),
                                   one_byte_external_string);
    uc16* non_one_byte = NewArray<uc16>(i + 1);
951
    for (int j = 0; j < i; j++) {
952
      non_one_byte[j] = 0x1234;
953 954 955
    }
    // Terminating '\0' is left out on purpose. It is not required for external
    // string data.
956 957 958 959 960
    Resource* resource = new Resource(non_one_byte, i);
    v8::Local<v8::String> non_one_byte_external_string =
        v8::String::NewExternal(CcTest::isolate(), resource);
    non_one_byte_external_strings->Set(v8::Integer::New(CcTest::isolate(), i),
                                       non_one_byte_external_string);
961
  }
962

963
  // Add the arrays with the short external strings in the global object.
964
  v8::Handle<v8::Object> global = context->Global();
965 966
  global->Set(v8_str("external_one_byte"), one_byte_external_strings);
  global->Set(v8_str("external_non_one_byte"), non_one_byte_external_strings);
967 968
  global->Set(v8_str("max_length"),
              v8::Integer::New(CcTest::isolate(), kMaxLength));
969

970
  // Add short external one-byte and two-byte strings checking the result.
971
  static const char* source =
972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013
      "function test() {"
      "  var one_byte_chars = 'aaaaaaaaaaaaaaaaaaaa';"
      "  var non_one_byte_chars = "
      "'\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1"
      "234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\"
      "u1234';"  // NOLINT
      "  if (one_byte_chars.length != max_length) return 1;"
      "  if (non_one_byte_chars.length != max_length) return 2;"
      "  var one_byte = Array(max_length + 1);"
      "  var non_one_byte = Array(max_length + 1);"
      "  for (var i = 0; i <= max_length; i++) {"
      "    one_byte[i] = one_byte_chars.substring(0, i);"
      "    non_one_byte[i] = non_one_byte_chars.substring(0, i);"
      "  };"
      "  for (var i = 0; i <= max_length; i++) {"
      "    if (one_byte[i] != external_one_byte[i]) return 3;"
      "    if (non_one_byte[i] != external_non_one_byte[i]) return 4;"
      "    for (var j = 0; j < i; j++) {"
      "      if (external_one_byte[i] !="
      "          (external_one_byte[j] + external_one_byte[i - j])) return "
      "5;"
      "      if (external_non_one_byte[i] !="
      "          (external_non_one_byte[j] + external_non_one_byte[i - "
      "j])) return 6;"
      "      if (non_one_byte[i] != (non_one_byte[j] + non_one_byte[i - "
      "j])) return 7;"
      "      if (one_byte[i] != (one_byte[j] + one_byte[i - j])) return 8;"
      "      if (one_byte[i] != (external_one_byte[j] + one_byte[i - j])) "
      "return 9;"
      "      if (one_byte[i] != (one_byte[j] + external_one_byte[i - j])) "
      "return 10;"
      "      if (non_one_byte[i] !="
      "          (external_non_one_byte[j] + non_one_byte[i - j])) return "
      "11;"
      "      if (non_one_byte[i] !="
      "          (non_one_byte[j] + external_non_one_byte[i - j])) return "
      "12;"
      "    }"
      "  }"
      "  return 0;"
      "};"
      "test()";
1014
  CHECK_EQ(0, CompileRun(source)->Int32Value());
1015
}
1016 1017


1018
TEST(JSONStringifySliceMadeExternal) {
1019
  CcTest::InitializeVM();
1020 1021 1022 1023
  // Create a sliced string from a one-byte string.  The latter is turned
  // into a two-byte external string.  Check that JSON.stringify works.
  v8::HandleScope handle_scope(CcTest::isolate());
  v8::Handle<v8::String> underlying =
1024 1025 1026 1027
      CompileRun(
          "var underlying = 'abcdefghijklmnopqrstuvwxyz';"
          "underlying")->ToString(CcTest::isolate());
  v8::Handle<v8::String> slice = CompileRun(
1028 1029
                                     "var slice = '';"
                                     "slice = underlying.slice(1);"
1030
                                     "slice")->ToString(CcTest::isolate());
1031 1032 1033 1034
  CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
  CHECK(v8::Utils::OpenHandle(*underlying)->IsSeqOneByteString());

  int length = underlying->Length();
1035
  uc16* two_byte = NewArray<uc16>(length + 1);
1036
  underlying->Write(two_byte);
1037
  Resource* resource = new Resource(two_byte, length);
1038 1039 1040 1041
  CHECK(underlying->MakeExternal(resource));
  CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
  CHECK(v8::Utils::OpenHandle(*underlying)->IsExternalTwoByteString());

1042 1043 1044
  CHECK_EQ(0,
           strcmp("\"bcdefghijklmnopqrstuvwxyz\"",
                  *v8::String::Utf8Value(CompileRun("JSON.stringify(slice)"))));
1045 1046 1047
}


1048
TEST(CachedHashOverflow) {
1049
  CcTest::InitializeVM();
1050 1051 1052
  // We incorrectly allowed strings to be tagged as array indices even if their
  // values didn't fit in the hash field.
  // See http://code.google.com/p/v8/issues/detail?id=728
1053
  Isolate* isolate = CcTest::i_isolate();
1054

1055
  v8::HandleScope handle_scope(CcTest::isolate());
1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068
  // Lines must be executed sequentially. Combining them into one script
  // makes the bug go away.
  const char* lines[] = {
      "var x = [];",
      "x[4] = 42;",
      "var s = \"1073741828\";",
      "x[s];",
      "x[s] = 37;",
      "x[4];",
      "x[s];",
      NULL
  };

1069 1070 1071 1072 1073 1074 1075 1076 1077
  Handle<Smi> fortytwo(Smi::FromInt(42), isolate);
  Handle<Smi> thirtyseven(Smi::FromInt(37), isolate);
  Handle<Object> results[] = { isolate->factory()->undefined_value(),
                               fortytwo,
                               isolate->factory()->undefined_value(),
                               isolate->factory()->undefined_value(),
                               thirtyseven,
                               fortytwo,
                               thirtyseven  // Bug yielded 42 here.
1078 1079 1080 1081 1082
  };

  const char* line;
  for (int i = 0; (line = lines[i]); i++) {
    printf("%s\n", line);
1083 1084
    v8::Local<v8::Value> result = v8::Script::Compile(
        v8::String::NewFromUtf8(CcTest::isolate(), line))->Run();
1085 1086
    CHECK_EQ(results[i]->IsUndefined(), result->IsUndefined());
    CHECK_EQ(results[i]->IsNumber(), result->IsNumber());
1087
    if (result->IsNumber()) {
1088 1089 1090
      int32_t value = 0;
      CHECK(results[i]->ToInt32(&value));
      CHECK_EQ(value, result->ToInt32(CcTest::isolate())->Value());
1091 1092 1093
    }
  }
}
1094 1095 1096 1097


TEST(SliceFromCons) {
  FLAG_string_slices = true;
1098
  CcTest::InitializeVM();
1099
  Factory* factory = CcTest::i_isolate()->factory();
1100
  v8::HandleScope scope(CcTest::isolate());
1101
  Handle<String> string =
1102
      factory->NewStringFromStaticChars("parentparentparent");
1103 1104
  Handle<String> parent =
      factory->NewConsString(string, string).ToHandleChecked();
1105 1106
  CHECK(parent->IsConsString());
  CHECK(!parent->IsFlat());
1107
  Handle<String> slice = factory->NewSubString(parent, 1, 25);
1108 1109 1110 1111
  // After slicing, the original string becomes a flat cons.
  CHECK(parent->IsFlat());
  CHECK(slice->IsSlicedString());
  CHECK_EQ(SlicedString::cast(*slice)->parent(),
1112 1113 1114
           // Parent could have been short-circuited.
           parent->IsConsString() ? ConsString::cast(*parent)->first()
                                  : *parent);
1115 1116 1117 1118 1119
  CHECK(SlicedString::cast(*slice)->parent()->IsSeqString());
  CHECK(slice->IsFlat());
}


1120
class OneByteVectorResource : public v8::String::ExternalOneByteStringResource {
1121
 public:
1122
  explicit OneByteVectorResource(i::Vector<const char> vector)
1123
      : data_(vector) {}
1124
  virtual ~OneByteVectorResource() {}
1125 1126 1127 1128 1129 1130 1131 1132 1133
  virtual size_t length() const { return data_.length(); }
  virtual const char* data() const { return data_.start(); }
 private:
  i::Vector<const char> data_;
};


TEST(SliceFromExternal) {
  FLAG_string_slices = true;
1134
  CcTest::InitializeVM();
1135
  Factory* factory = CcTest::i_isolate()->factory();
1136
  v8::HandleScope scope(CcTest::isolate());
1137
  OneByteVectorResource resource(
1138
      i::Vector<const char>("abcdefghijklmnopqrstuvwxyz", 26));
1139
  Handle<String> string =
1140
      factory->NewExternalStringFromOneByte(&resource).ToHandleChecked();
1141
  CHECK(string->IsExternalString());
1142
  Handle<String> slice = factory->NewSubString(string, 1, 25);
1143 1144 1145 1146 1147 1148 1149 1150
  CHECK(slice->IsSlicedString());
  CHECK(string->IsExternalString());
  CHECK_EQ(SlicedString::cast(*slice)->parent(), *string);
  CHECK(SlicedString::cast(*slice)->parent()->IsExternalString());
  CHECK(slice->IsFlat());
}


1151 1152 1153 1154
TEST(TrivialSlice) {
  // This tests whether a slice that contains the entire parent string
  // actually creates a new string (it should not).
  FLAG_string_slices = true;
1155
  CcTest::InitializeVM();
1156
  Factory* factory = CcTest::i_isolate()->factory();
1157
  v8::HandleScope scope(CcTest::isolate());
1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170
  v8::Local<v8::Value> result;
  Handle<String> string;
  const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
  const char* check = "str.slice(0,26)";
  const char* crosscheck = "str.slice(1,25)";

  CompileRun(init);

  result = CompileRun(check);
  CHECK(result->IsString());
  string = v8::Utils::OpenHandle(v8::String::Cast(*result));
  CHECK(!string->IsSlicedString());

1171
  string = factory->NewSubString(string, 0, 26);
1172 1173 1174 1175 1176
  CHECK(!string->IsSlicedString());
  result = CompileRun(crosscheck);
  CHECK(result->IsString());
  string = v8::Utils::OpenHandle(v8::String::Cast(*result));
  CHECK(string->IsSlicedString());
1177
  CHECK_EQ(0, strcmp("bcdefghijklmnopqrstuvwxy", string->ToCString().get()));
1178
}
1179 1180 1181 1182 1183 1184


TEST(SliceFromSlice) {
  // This tests whether a slice that contains the entire parent string
  // actually creates a new string (it should not).
  FLAG_string_slices = true;
1185 1186
  CcTest::InitializeVM();
  v8::HandleScope scope(CcTest::isolate());
1187 1188 1189
  v8::Local<v8::Value> result;
  Handle<String> string;
  const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
1190
  const char* slice = "var slice = ''; slice = str.slice(1,-1); slice";
1191 1192 1193 1194 1195 1196 1197 1198
  const char* slice_from_slice = "slice.slice(1,-1);";

  CompileRun(init);
  result = CompileRun(slice);
  CHECK(result->IsString());
  string = v8::Utils::OpenHandle(v8::String::Cast(*result));
  CHECK(string->IsSlicedString());
  CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
1199
  CHECK_EQ(0, strcmp("bcdefghijklmnopqrstuvwxy", string->ToCString().get()));
1200 1201 1202 1203 1204 1205

  result = CompileRun(slice_from_slice);
  CHECK(result->IsString());
  string = v8::Utils::OpenHandle(v8::String::Cast(*result));
  CHECK(string->IsSlicedString());
  CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
1206
  CHECK_EQ(0, strcmp("cdefghijklmnopqrstuvwx", string->ToCString().get()));
1207
}
1208 1209


1210 1211
UNINITIALIZED_TEST(OneByteArrayJoin) {
  v8::Isolate::CreateParams create_params;
1212
  // Set heap limits.
1213 1214
  create_params.constraints.set_max_semi_space_size(1 * Page::kPageSize / MB);
  create_params.constraints.set_max_old_space_size(6 * Page::kPageSize / MB);
1215
  create_params.array_buffer_allocator = CcTest::array_buffer_allocator();
1216 1217 1218 1219 1220 1221 1222 1223 1224 1225
  v8::Isolate* isolate = v8::Isolate::New(create_params);
  isolate->Enter();

  {
    // String s is made of 2^17 = 131072 'c' characters and a is an array
    // starting with 'bad', followed by 2^14 times the string s. That means the
    // total length of the concatenated strings is 2^31 + 3. So on 32bit systems
    // summing the lengths of the strings (as Smis) overflows and wraps.
    LocalContext context(isolate);
    v8::HandleScope scope(isolate);
1226
    v8::TryCatch try_catch(isolate);
1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238
    CHECK(CompileRun(
              "var two_14 = Math.pow(2, 14);"
              "var two_17 = Math.pow(2, 17);"
              "var s = Array(two_17 + 1).join('c');"
              "var a = ['bad'];"
              "for (var i = 1; i <= two_14; i++) a.push(s);"
              "a.join("
              ");").IsEmpty());
    CHECK(try_catch.HasCaught());
  }
  isolate->Exit();
  isolate->Dispose();
1239
}
1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251


static void CheckException(const char* source) {
  // An empty handle is returned upon exception.
  CHECK(CompileRun(source).IsEmpty());
}


TEST(RobustSubStringStub) {
  // This tests whether the SubStringStub can handle unsafe arguments.
  // If not recognized, those unsafe arguments lead to out-of-bounds reads.
  FLAG_allow_natives_syntax = true;
1252 1253
  CcTest::InitializeVM();
  v8::HandleScope scope(CcTest::isolate());
1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269
  v8::Local<v8::Value> result;
  Handle<String> string;
  CompileRun("var short = 'abcdef';");

  // Invalid indices.
  CheckException("%_SubString(short,     0,    10000);");
  CheckException("%_SubString(short, -1234,        5);");
  CheckException("%_SubString(short,     5,        2);");
  // Special HeapNumbers.
  CheckException("%_SubString(short,     1, Infinity);");
  CheckException("%_SubString(short,   NaN,        5);");
  // String arguments.
  CheckException("%_SubString(short,    '2',     '5');");
  // Ordinary HeapNumbers can be handled (in runtime).
  result = CompileRun("%_SubString(short, Math.sqrt(4), 5.1);");
  string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1270
  CHECK_EQ(0, strcmp("cde", string->ToCString().get()));
1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284

  CompileRun("var long = 'abcdefghijklmnopqrstuvwxyz';");
  // Invalid indices.
  CheckException("%_SubString(long,     0,    10000);");
  CheckException("%_SubString(long, -1234,       17);");
  CheckException("%_SubString(long,    17,        2);");
  // Special HeapNumbers.
  CheckException("%_SubString(long,     1, Infinity);");
  CheckException("%_SubString(long,   NaN,       17);");
  // String arguments.
  CheckException("%_SubString(long,    '2',    '17');");
  // Ordinary HeapNumbers within bounds can be handled (in runtime).
  result = CompileRun("%_SubString(long, Math.sqrt(4), 17.1);");
  string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1285
  CHECK_EQ(0, strcmp("cdefghijklmnopq", string->ToCString().get()));
1286 1287 1288 1289 1290 1291

  // Test that out-of-bounds substring of a slice fails when the indices
  // would have been valid for the underlying string.
  CompileRun("var slice = long.slice(1, 15);");
  CheckException("%_SubString(slice, 0, 17);");
}
1292 1293


1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321
namespace {

int* global_use_counts = NULL;

void MockUseCounterCallback(v8::Isolate* isolate,
                            v8::Isolate::UseCounterFeature feature) {
  ++global_use_counts[feature];
}
}


TEST(CountBreakIterator) {
  CcTest::InitializeVM();
  v8::HandleScope scope(CcTest::isolate());
  LocalContext context;
  int use_counts[v8::Isolate::kUseCounterFeatureCount] = {};
  global_use_counts = use_counts;
  CcTest::isolate()->SetUseCounterCallback(MockUseCounterCallback);
  CHECK_EQ(0, use_counts[v8::Isolate::kBreakIterator]);
  v8::Local<v8::Value> result = CompileRun(
      "(function() {"
      "  if (!this.Intl) return 0;"
      "  var iterator = Intl.v8BreakIterator(['en']);"
      "  iterator.adoptText('Now is the time');"
      "  iterator.next();"
      "  return iterator.next();"
      "})();");
  CHECK(result->IsNumber());
1322
  int uses = result->ToInt32(CcTest::isolate())->Value() == 0 ? 0 : 1;
1323 1324 1325 1326 1327 1328 1329
  CHECK_EQ(uses, use_counts[v8::Isolate::kBreakIterator]);
  // Make sure GC cleans up the break iterator, so we don't get a memory leak
  // reported by ASAN.
  CcTest::isolate()->LowMemoryNotification();
}


1330
TEST(StringReplaceAtomTwoByteResult) {
1331 1332
  CcTest::InitializeVM();
  v8::HandleScope scope(CcTest::isolate());
1333 1334
  LocalContext context;
  v8::Local<v8::Value> result = CompileRun(
1335
      "var subject = 'one_byte~only~string~'; "
1336 1337 1338 1339 1340 1341
      "var replace = '\x80';            "
      "subject.replace(/~/g, replace);  ");
  CHECK(result->IsString());
  Handle<String> string = v8::Utils::OpenHandle(v8::String::Cast(*result));
  CHECK(string->IsSeqTwoByteString());

1342
  v8::Local<v8::String> expected = v8_str("one_byte\x80only\x80string\x80");
1343 1344
  CHECK(expected->Equals(result));
}
1345 1346 1347 1348


TEST(IsAscii) {
  CHECK(String::IsAscii(static_cast<char*>(NULL), 0));
1349
  CHECK(String::IsOneByte(static_cast<uc16*>(NULL), 0));
1350
}
1351 1352


1353 1354 1355 1356

template<typename Op, bool return_first>
static uint16_t ConvertLatin1(uint16_t c) {
  uint32_t result[Op::kMaxWidth];
1357
  int chars;
1358 1359 1360 1361 1362
  chars = Op::Convert(c, 0, result, NULL);
  if (chars == 0) return 0;
  CHECK_LE(chars, static_cast<int>(sizeof(result)));
  if (!return_first && chars > 1) {
    return 0;
1363
  }
1364
  return result[0];
1365 1366 1367
}


1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404
static void CheckCanonicalEquivalence(uint16_t c, uint16_t test) {
  uint16_t expect = ConvertLatin1<unibrow::Ecma262UnCanonicalize, true>(c);
  if (expect > unibrow::Latin1::kMaxChar) expect = 0;
  CHECK_EQ(expect, test);
}


TEST(Latin1IgnoreCase) {
  using namespace unibrow;
  for (uint16_t c = Latin1::kMaxChar + 1; c != 0; c++) {
    uint16_t lower = ConvertLatin1<ToLowercase, false>(c);
    uint16_t upper = ConvertLatin1<ToUppercase, false>(c);
    uint16_t test = Latin1::ConvertNonLatin1ToLatin1(c);
    // Filter out all character whose upper is not their lower or vice versa.
    if (lower == 0 && upper == 0) {
      CheckCanonicalEquivalence(c, test);
      continue;
    }
    if (lower > Latin1::kMaxChar && upper > Latin1::kMaxChar) {
      CheckCanonicalEquivalence(c, test);
      continue;
    }
    if (lower == 0 && upper != 0) {
      lower = ConvertLatin1<ToLowercase, false>(upper);
    }
    if (upper == 0 && lower != c) {
      upper = ConvertLatin1<ToUppercase, false>(lower);
    }
    if (lower > Latin1::kMaxChar && upper > Latin1::kMaxChar) {
      CheckCanonicalEquivalence(c, test);
      continue;
    }
    if (upper != c && lower != c) {
      CheckCanonicalEquivalence(c, test);
      continue;
    }
    CHECK_EQ(Min(upper, lower), test);
1405 1406
  }
}
1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428


class DummyResource: public v8::String::ExternalStringResource {
 public:
  virtual const uint16_t* data() const { return NULL; }
  virtual size_t length() const { return 1 << 30; }
};


class DummyOneByteResource: public v8::String::ExternalOneByteStringResource {
 public:
  virtual const char* data() const { return NULL; }
  virtual size_t length() const { return 1 << 30; }
};


TEST(InvalidExternalString) {
  CcTest::InitializeVM();
  LocalContext context;
  Isolate* isolate = CcTest::i_isolate();
  { HandleScope scope(isolate);
    DummyOneByteResource r;
1429
    CHECK(isolate->factory()->NewExternalStringFromOneByte(&r).is_null());
1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451
    CHECK(isolate->has_pending_exception());
    isolate->clear_pending_exception();
  }

  { HandleScope scope(isolate);
    DummyResource r;
    CHECK(isolate->factory()->NewExternalStringFromTwoByte(&r).is_null());
    CHECK(isolate->has_pending_exception());
    isolate->clear_pending_exception();
  }
}


#define INVALID_STRING_TEST(FUN, TYPE)                                         \
  TEST(StringOOM##FUN) {                                                       \
    CcTest::InitializeVM();                                                    \
    LocalContext context;                                                      \
    Isolate* isolate = CcTest::i_isolate();                                    \
    STATIC_ASSERT(String::kMaxLength < kMaxInt);                               \
    static const int invalid = String::kMaxLength + 1;                         \
    HandleScope scope(isolate);                                                \
    Vector<TYPE> dummy = Vector<TYPE>::New(invalid);                           \
1452
    memset(dummy.start(), 0x0, dummy.length() * sizeof(TYPE));                 \
1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464
    CHECK(isolate->factory()->FUN(Vector<const TYPE>::cast(dummy)).is_null()); \
    memset(dummy.start(), 0x20, dummy.length() * sizeof(TYPE));                \
    CHECK(isolate->has_pending_exception());                                   \
    isolate->clear_pending_exception();                                        \
    dummy.Dispose();                                                           \
  }

INVALID_STRING_TEST(NewStringFromAscii, char)
INVALID_STRING_TEST(NewStringFromUtf8, char)
INVALID_STRING_TEST(NewStringFromOneByte, uint8_t)

#undef INVALID_STRING_TEST
1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481


TEST(FormatMessage) {
  CcTest::InitializeVM();
  LocalContext context;
  Isolate* isolate = CcTest::i_isolate();
  HandleScope scope(isolate);
  Handle<String> arg0 = isolate->factory()->NewStringFromAsciiChecked("arg0");
  Handle<String> arg1 = isolate->factory()->NewStringFromAsciiChecked("arg1");
  Handle<String> arg2 = isolate->factory()->NewStringFromAsciiChecked("arg2");
  Handle<String> result =
      MessageTemplate::FormatMessage(MessageTemplate::kPropertyNotFunction,
                                     arg0, arg1, arg2).ToHandleChecked();
  Handle<String> expected = isolate->factory()->NewStringFromAsciiChecked(
      "Property 'arg0' of object arg1 is not a function");
  CHECK(String::Equals(result, expected));
}