test-strings.cc 45.5 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 35 36
// 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>

#include "v8.h"

37
#include "api.h"
38
#include "factory.h"
39
#include "objects.h"
40
#include "cctest.h"
41
#include "zone-inl.h"
42

43
// Adapted from http://en.wikipedia.org/wiki/Multiply-with-carry
44
class MyRandomNumberGenerator {
45
 public:
46
  MyRandomNumberGenerator() {
47 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 82 83 84 85 86 87 88 89 90 91 92 93 94
    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) {
    ASSERT(threshold >= 0.0 && threshold <= 1.0);
    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;
};

95 96 97 98 99 100 101 102

using namespace v8::internal;


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


103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
class Resource: public v8::String::ExternalStringResource,
                public ZoneObject {
 public:
  explicit Resource(Vector<const uc16> string): data_(string.start()) {
    length_ = string.length();
  }
  virtual const uint16_t* data() const { return data_; }
  virtual size_t length() const { return length_; }

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


118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
class AsciiResource: public v8::String::ExternalAsciiStringResource,
                public ZoneObject {
 public:
  explicit AsciiResource(Vector<const char> string): data_(string.start()) {
    length_ = string.length();
  }
  virtual const char* data() const { return data_; }
  virtual size_t length() const { return length_; }

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


133 134 135
static void InitializeBuildingBlocks(Handle<String>* building_blocks,
                                     int bb_length,
                                     bool long_blocks,
136
                                     MyRandomNumberGenerator* rng,
137
                                     Zone* zone) {
138 139
  // 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.
140
  Isolate* isolate = CcTest::i_isolate();
141
  Factory* factory = isolate->factory();
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
  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) {
160 161
      len += 1234;
    }
162 163 164 165 166
    // 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)) {
167 168 169
      case 0: {
        uc16 buf[2000];
        for (int j = 0; j < len; j++) {
170
          buf[j] = rng->next(0x10000);
171 172
        }
        building_blocks[i] =
173
            factory->NewStringFromTwoByte(Vector<const uc16>(buf, len));
174
        for (int j = 0; j < len; j++) {
175
          CHECK_EQ(buf[j], building_blocks[i]->Get(j));
176 177 178 179 180 181
        }
        break;
      }
      case 1: {
        char buf[2000];
        for (int j = 0; j < len; j++) {
182
          buf[j] = rng->next(0x80);
183 184
        }
        building_blocks[i] =
185
            factory->NewStringFromAscii(Vector<const char>(buf, len));
186
        for (int j = 0; j < len; j++) {
187
          CHECK_EQ(buf[j], building_blocks[i]->Get(j));
188 189 190 191
        }
        break;
      }
      case 2: {
192
        uc16* buf = zone->NewArray<uc16>(len);
193
        for (int j = 0; j < len; j++) {
194
          buf[j] = rng->next(0x10000);
195
        }
196
        Resource* resource = new(zone) Resource(Vector<const uc16>(buf, len));
197
        building_blocks[i] = factory->NewExternalStringFromTwoByte(resource);
198
        for (int j = 0; j < len; j++) {
199
          CHECK_EQ(buf[j], building_blocks[i]->Get(j));
200 201 202 203
        }
        break;
      }
      case 3: {
204
        char* buf = zone->NewArray<char>(len);
205
        for (int j = 0; j < len; j++) {
206
          buf[j] = rng->next(0x80);
207
        }
208 209
        AsciiResource* resource =
            new(zone) AsciiResource(Vector<const char>(buf, len));
210
        building_blocks[i] = factory->NewExternalStringFromAscii(resource);
211
        for (int j = 0; j < len; j++) {
212
          CHECK_EQ(buf[j], building_blocks[i]->Get(j));
213 214 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 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264
class ConsStringStats {
 public:
  ConsStringStats() {
    Reset();
  }
  void Reset();
  void VerifyEqual(const ConsStringStats& that) const;
  unsigned leaves_;
  unsigned empty_leaves_;
  unsigned chars_;
  unsigned left_traversals_;
  unsigned right_traversals_;
 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 {
  CHECK(this->leaves_ == that.leaves_);
  CHECK(this->empty_leaves_ == that.empty_leaves_);
  CHECK(this->chars_ == that.chars_);
  CHECK(this->left_traversals_ == that.left_traversals_);
  CHECK(this->right_traversals_ == that.right_traversals_);
}


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


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


298 299 300 301 302 303 304 305 306 307 308
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];
}


309 310 311 312 313 314 315 316
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;
317
  rng_.init();
318 319 320
}


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


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


void AccumulateStatsWithOperator(
361
    ConsString* cons_string, ConsStringStats* stats) {
362 363 364
  unsigned offset = 0;
  int32_t type = cons_string->map()->instance_type();
  unsigned length = static_cast<unsigned>(cons_string->length());
365
  ConsStringIteratorOp op;
366 367
  String* string = op.Operate(cons_string, &offset, &type, &length);
  CHECK(string != NULL);
368
  while (true) {
369 370 371 372 373 374 375 376 377 378 379
    ASSERT(!string->IsConsString());
    // Accumulate stats.
    stats->leaves_++;
    stats->chars_ += string->length();
    // Check for completion.
    bool keep_going_fast_check = op.HasMore();
    string = op.ContinueOperation(&type, &length);
    if (string == NULL) return;
    // Verify no false positives for fast check.
    CHECK(keep_going_fast_check);
  }
380 381 382 383 384 385
}


void VerifyConsString(Handle<String> root, ConsStringGenerationData* data) {
  // Verify basic data.
  CHECK(root->IsConsString());
386
  CHECK(static_cast<unsigned>(root->length()) == data->stats_.chars_);
387 388
  // Recursive verify.
  ConsStringStats stats;
389
  AccumulateStats(ConsString::cast(*root), &stats);
390 391 392
  stats.VerifyEqual(data->stats_);
  // Iteratively verify.
  stats.Reset();
393
  AccumulateStatsWithOperator(ConsString::cast(*root), &stats);
394 395 396 397 398 399 400 401 402 403 404 405
  // 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) {
406
  Factory* factory = CcTest::i_isolate()->factory();
407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425
  // 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) {
426
    left = data->block(data->rng_.next());
427 428 429 430 431 432 433 434
    data->stats_.leaves_++;
    data->stats_.chars_ += left->length();
  } else {
    data->stats_.left_traversals_++;
  }
  // Generate right string.
  Handle<String> right;
  if (terminate_right) {
435
    right = data->block(data->rng_.next());
436 437 438 439 440
    data->stats_.leaves_++;
    data->stats_.chars_ += right->length();
  } else {
    data->stats_.right_traversals_++;
  }
441 442 443 444 445 446 447 448 449 450 451
  // 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);
  }
452
  // Build the cons string.
453
  Handle<String> root = factory->NewConsString(left, right);
454 455 456 457 458 459 460 461 462 463 464
  CHECK(root->IsConsString() && !root->IsFlat());
  // Special work needed for flat string.
  if (flat) {
    data->stats_.empty_leaves_++;
    FlattenString(root);
    CHECK(root->IsConsString() && root->IsFlat());
  }
  return root;
}


465 466 467
static Handle<String> ConstructLeft(
    ConsStringGenerationData* data,
    int depth) {
468
  Factory* factory = CcTest::i_isolate()->factory();
469
  Handle<String> answer = factory->NewStringFromAscii(CStrVector(""));
470 471 472
  data->stats_.leaves_++;
  for (int i = 0; i < depth; i++) {
    Handle<String> block = data->block(i);
473
    Handle<String> next = factory->NewConsString(answer, block);
474 475 476 477 478 479 480
    if (next->IsConsString()) data->stats_.leaves_++;
    data->stats_.chars_ += block->length();
    answer = next;
  }
  data->stats_.left_traversals_ = data->stats_.leaves_ - 2;
  return answer;
}
481 482


483 484 485
static Handle<String> ConstructRight(
    ConsStringGenerationData* data,
    int depth) {
486
  Factory* factory = CcTest::i_isolate()->factory();
487
  Handle<String> answer = factory->NewStringFromAscii(CStrVector(""));
488 489 490
  data->stats_.leaves_++;
  for (int i = depth - 1; i >= 0; i--) {
    Handle<String> block = data->block(i);
491
    Handle<String> next = factory->NewConsString(block, answer);
492 493 494
    if (next->IsConsString()) data->stats_.leaves_++;
    data->stats_.chars_ += block->length();
    answer = next;
495
  }
496 497 498 499 500 501 502 503 504
  data->stats_.right_traversals_ = data->stats_.leaves_ - 2;
  return answer;
}


static Handle<String> ConstructBalancedHelper(
    ConsStringGenerationData* data,
    int from,
    int to) {
505
  Factory* factory = CcTest::i_isolate()->factory();
506 507 508 509 510 511 512 513
  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();
514
    return factory->NewConsString(data->block(from), data->block(from+1));
515 516 517 518 519 520 521
  }
  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_++;
522
  return factory->NewConsString(part1, part2);
523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539
}


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 ConsStringIteratorOp cons_string_iterator_op_1;
static ConsStringIteratorOp cons_string_iterator_op_2;

static void Traverse(Handle<String> s1, Handle<String> s2) {
  int i = 0;
540 541
  StringCharacterStream character_stream_1(*s1, &cons_string_iterator_op_1);
  StringCharacterStream character_stream_2(*s2, &cons_string_iterator_op_2);
542
  while (character_stream_1.HasMore()) {
543
    CHECK(character_stream_2.HasMore());
544
    uint16_t c = character_stream_1.GetNext();
545 546 547 548 549 550 551 552 553 554 555 556
    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;
557 558
  StringCharacterStream character_stream_1(*s1, &cons_string_iterator_op_1);
  StringCharacterStream character_stream_2(*s2, &cons_string_iterator_op_2);
559
  while (character_stream_1.HasMore() && i < chars) {
560
    CHECK(character_stream_2.HasMore());
561
    uint16_t c = character_stream_1.GetNext();
562 563 564 565 566 567 568 569 570 571
    CHECK_EQ(c, character_stream_2.GetNext());
    i++;
  }
  s1->Get(s1->length() - 1);
  s2->Get(s2->length() - 1);
}


TEST(Traverse) {
  printf("TestTraverse\n");
572 573
  CcTest::InitializeVM();
  v8::HandleScope scope(CcTest::isolate());
574
  Zone zone(CcTest::i_isolate());
575
  ConsStringGenerationData data(false, &zone);
576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610
  Handle<String> flat = ConstructBalanced(&data);
  FlattenString(flat);
  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");
  FlattenString(left_asymmetric);
  printf("10\n");
  Traverse(flat, left_asymmetric);
  printf("11\n");
  FlattenString(right_asymmetric);
  printf("12\n");
  Traverse(flat, right_asymmetric);
  printf("14\n");
  FlattenString(symmetric);
  printf("15\n");
  Traverse(flat, symmetric);
  printf("16\n");
  FlattenString(left_deep_asymmetric);
  printf("18\n");
611 612 613 614 615 616
}


static void VerifyCharacterStream(
    String* flat_string, String* cons_string) {
  // Do not want to test ConString traversal on flat string.
617
  CHECK(flat_string->IsFlat() && !flat_string->IsConsString());
618 619 620 621 622 623
  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++) {
624
    int offset = length * j / outer_iterations;
625 626 627 628
    if (offset < 0) offset = 0;
    // Want to test the offset == length case.
    if (offset > length) offset = length;
    StringCharacterStream flat_stream(
629
        flat_string, &cons_string_iterator_op_1, static_cast<unsigned>(offset));
630
    StringCharacterStream cons_stream(
631
        cons_string, &cons_string_iterator_op_2, static_cast<unsigned>(offset));
632 633 634 635 636 637 638 639 640 641 642 643 644
    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());
  }
}


645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660
static inline void PrintStats(const ConsStringGenerationData& data) {
#ifdef DEBUG
printf(
    "%s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d], %s: [%d]\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_);
#endif
}


template<typename BuildString>
void TestStringCharacterStream(BuildString build, int test_cases) {
661
  CcTest::InitializeVM();
662
  Isolate* isolate = CcTest::i_isolate();
663
  HandleScope outer_scope(isolate);
664 665
  Zone zone(isolate);
  ConsStringGenerationData data(true, &zone);
666
  for (int i = 0; i < test_cases; i++) {
667 668
    printf("%d\n", i);
    HandleScope inner_scope(isolate);
669
    AlwaysAllocateScope always_allocate;
670 671 672 673 674
    // 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.
675
    FlattenString(flat_string);
676 677 678 679
    // 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);
680
    DisallowHeapAllocation no_allocation;
681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699
    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) {
700
  Factory* factory = CcTest::i_isolate()->factory();
701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717
  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;
718
      return factory->NewConsString(data->block(0), data->block(1));
719 720 721 722 723 724 725 726
    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 =
727
            factory->NewConsString(data->block(0), data->block(1));
728 729 730 731 732 733 734 735 736 737 738 739 740
        FlattenString(string);
        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 =
741
            factory->NewConsString(data->block(0), data->block(1));
742
        FlattenString(left);
743
        return factory->NewConsString(left, data->block(2));
744 745 746 747 748 749 750 751 752 753 754 755 756
      }
    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 =
757
            factory->NewConsString(data->block(0), data->block(1));
758 759
        FlattenString(left);
        Handle<String> right =
760
            factory->NewConsString(data->block(2), data->block(2));
761
        FlattenString(right);
762
        return factory->NewConsString(left, right);
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 823 824 825 826 827 828 829 830 831 832 833 834
      }
  }
  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;
835
  }
836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853
  // 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);
854 855 856
}


857 858 859 860 861
static const int DEEP_ASCII_DEPTH = 100000;


TEST(DeepAscii) {
  printf("TestDeepAscii\n");
862
  CcTest::InitializeVM();
863
  Factory* factory = CcTest::i_isolate()->factory();
864
  v8::HandleScope scope(CcTest::isolate());
865 866 867 868 869 870

  char* foo = NewArray<char>(DEEP_ASCII_DEPTH);
  for (int i = 0; i < DEEP_ASCII_DEPTH; i++) {
    foo[i] = "foo "[i % 4];
  }
  Handle<String> string =
871 872
      factory->NewStringFromAscii(Vector<const char>(foo, DEEP_ASCII_DEPTH));
  Handle<String> foo_string = factory->NewStringFromAscii(CStrVector("foo"));
873
  for (int i = 0; i < DEEP_ASCII_DEPTH; i += 10) {
874
    string = factory->NewConsString(string, foo_string);
875
  }
876
  Handle<String> flat_string = factory->NewConsString(string, foo_string);
877 878 879 880 881
  FlattenString(flat_string);

  for (int i = 0; i < 500; i++) {
    TraverseFirst(flat_string, string, DEEP_ASCII_DEPTH);
  }
882
  DeleteArray<char>(foo);
883
}
884 885 886 887


TEST(Utf8Conversion) {
  // Smoke test for converting strings to utf-8.
888 889
  CcTest::InitializeVM();
  v8::HandleScope handle_scope(CcTest::isolate());
890 891
  // A simple ascii string
  const char* ascii_string = "abcdef12345";
892 893 894 895
  int len =
      v8::String::New(ascii_string,
                      StrLength(ascii_string))->Utf8Length();
  CHECK_EQ(StrLength(ascii_string), len);
896 897 898 899 900 901 902 903
  // A mixed ascii and non-ascii string
  // 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
904
  const unsigned char as_utf8[11] = {0xCB, 0xA4, 0x64, 0xE1, 0x8B, 0xA4, 0x30,
905 906 907
      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};
908
  const int char_lengths[12] = {0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5};
909 910 911 912
  v8::Handle<v8::String> mixed = v8::String::New(mixed_string, 5);
  CHECK_EQ(10, mixed->Utf8Length());
  // Try encoding the string with all capacities
  char buffer[11];
913
  const char kNoChar = static_cast<char>(-1);
914 915 916
  for (int i = 0; i <= 11; i++) {
    // Clear the buffer before reusing it
    for (int j = 0; j < 11; j++)
917
      buffer[j] = kNoChar;
918 919
    int chars_written;
    int written = mixed->WriteUtf8(buffer, i, &chars_written);
920
    CHECK_EQ(lengths[i], written);
921
    CHECK_EQ(char_lengths[i], chars_written);
922 923
    // Check that the contents are correct
    for (int j = 0; j < lengths[i]; j++)
924
      CHECK_EQ(as_utf8[j], static_cast<unsigned char>(buffer[j]));
925 926
    // Check that the rest of the buffer hasn't been touched
    for (int j = lengths[i]; j < 11; j++)
927
      CHECK_EQ(kNoChar, buffer[j]);
928 929
  }
}
930 931


932
TEST(ExternalShortStringAdd) {
933
  Isolate* isolate = CcTest::i_isolate();
934
  Zone zone(isolate);
935

936
  LocalContext context;
937
  v8::HandleScope handle_scope(CcTest::isolate());
938

939 940
  // Make sure we cover all always-flat lengths and at least one above.
  static const int kMaxLength = 20;
941
  CHECK_GT(kMaxLength, i::ConsString::kMinLength);
942 943 944 945 946 947 948 949 950

  // Allocate two JavaScript arrays for holding short strings.
  v8::Handle<v8::Array> ascii_external_strings =
      v8::Array::New(kMaxLength + 1);
  v8::Handle<v8::Array> non_ascii_external_strings =
      v8::Array::New(kMaxLength + 1);

  // Generate short ascii and non-ascii external strings.
  for (int i = 0; i <= kMaxLength; i++) {
951
    char* ascii = zone.NewArray<char>(i + 1);
952 953 954 955 956 957
    for (int j = 0; j < i; j++) {
      ascii[j] = 'a';
    }
    // Terminating '\0' is left out on purpose. It is not required for external
    // string data.
    AsciiResource* ascii_resource =
958
        new(&zone) AsciiResource(Vector<const char>(ascii, i));
959 960 961 962
    v8::Local<v8::String> ascii_external_string =
        v8::String::NewExternal(ascii_resource);

    ascii_external_strings->Set(v8::Integer::New(i), ascii_external_string);
963
    uc16* non_ascii = zone.NewArray<uc16>(i + 1);
964
    for (int j = 0; j < i; j++) {
965
      non_ascii[j] = 0x1234;
966 967 968
    }
    // Terminating '\0' is left out on purpose. It is not required for external
    // string data.
969
    Resource* resource = new(&zone) Resource(Vector<const uc16>(non_ascii, i));
970 971 972 973 974
    v8::Local<v8::String> non_ascii_external_string =
      v8::String::NewExternal(resource);
    non_ascii_external_strings->Set(v8::Integer::New(i),
                                    non_ascii_external_string);
  }
975

976
  // Add the arrays with the short external strings in the global object.
977
  v8::Handle<v8::Object> global = context->Global();
978 979 980
  global->Set(v8_str("external_ascii"), ascii_external_strings);
  global->Set(v8_str("external_non_ascii"), non_ascii_external_strings);
  global->Set(v8_str("max_length"), v8::Integer::New(kMaxLength));
981 982 983 984

  // Add short external ascii and non-ascii strings checking the result.
  static const char* source =
    "function test() {"
985
    "  var ascii_chars = 'aaaaaaaaaaaaaaaaaaaa';"
986
    "  var non_ascii_chars = '\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234';"  //NOLINT
987 988 989 990 991 992 993 994 995 996 997
    "  if (ascii_chars.length != max_length) return 1;"
    "  if (non_ascii_chars.length != max_length) return 2;"
    "  var ascii = Array(max_length + 1);"
    "  var non_ascii = Array(max_length + 1);"
    "  for (var i = 0; i <= max_length; i++) {"
    "    ascii[i] = ascii_chars.substring(0, i);"
    "    non_ascii[i] = non_ascii_chars.substring(0, i);"
    "  };"
    "  for (var i = 0; i <= max_length; i++) {"
    "    if (ascii[i] != external_ascii[i]) return 3;"
    "    if (non_ascii[i] != external_non_ascii[i]) return 4;"
998
    "    for (var j = 0; j < i; j++) {"
999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010
    "      if (external_ascii[i] !="
    "          (external_ascii[j] + external_ascii[i - j])) return 5;"
    "      if (external_non_ascii[i] !="
    "          (external_non_ascii[j] + external_non_ascii[i - j])) return 6;"
    "      if (non_ascii[i] != (non_ascii[j] + non_ascii[i - j])) return 7;"
    "      if (ascii[i] != (ascii[j] + ascii[i - j])) return 8;"
    "      if (ascii[i] != (external_ascii[j] + ascii[i - j])) return 9;"
    "      if (ascii[i] != (ascii[j] + external_ascii[i - j])) return 10;"
    "      if (non_ascii[i] !="
    "          (external_non_ascii[j] + non_ascii[i - j])) return 11;"
    "      if (non_ascii[i] !="
    "          (non_ascii[j] + external_non_ascii[i - j])) return 12;"
1011 1012
    "    }"
    "  }"
1013
    "  return 0;"
1014 1015
    "};"
    "test()";
1016
  CHECK_EQ(0, CompileRun(source)->Int32Value());
1017
}
1018 1019


1020
TEST(JSONStringifySliceMadeExternal) {
1021
  CcTest::InitializeVM();
1022
  Isolate* isolate = CcTest::i_isolate();
1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049
  Zone zone(isolate);
  // 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 =
      CompileRun("var underlying = 'abcdefghijklmnopqrstuvwxyz';"
                 "underlying")->ToString();
  v8::Handle<v8::String> slice =
      CompileRun("var slice = underlying.slice(1);"
                 "slice")->ToString();
  CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
  CHECK(v8::Utils::OpenHandle(*underlying)->IsSeqOneByteString());

  int length = underlying->Length();
  uc16* two_byte = zone.NewArray<uc16>(length + 1);
  underlying->Write(two_byte);
  Resource* resource =
      new(&zone) Resource(Vector<const uc16>(two_byte, length));
  CHECK(underlying->MakeExternal(resource));
  CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
  CHECK(v8::Utils::OpenHandle(*underlying)->IsExternalTwoByteString());

  CHECK_EQ("\"bcdefghijklmnopqrstuvwxyz\"",
           *v8::String::Utf8Value(CompileRun("JSON.stringify(slice)")));
}


1050
TEST(CachedHashOverflow) {
1051
  CcTest::InitializeVM();
1052 1053 1054
  // 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
1055
  Isolate* isolate = CcTest::i_isolate();
1056
  Zone zone(isolate);
1057

1058
  v8::HandleScope handle_scope(CcTest::isolate());
1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071
  // 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
  };

1072 1073 1074 1075 1076 1077 1078 1079 1080
  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.
1081 1082 1083 1084 1085 1086 1087
  };

  const char* line;
  for (int i = 0; (line = lines[i]); i++) {
    printf("%s\n", line);
    v8::Local<v8::Value> result =
        v8::Script::Compile(v8::String::New(line))->Run();
1088 1089
    CHECK_EQ(results[i]->IsUndefined(), result->IsUndefined());
    CHECK_EQ(results[i]->IsNumber(), result->IsNumber());
1090
    if (result->IsNumber()) {
1091
      CHECK_EQ(Smi::cast(results[i]->ToSmi()->ToObjectChecked())->value(),
1092
               result->ToInt32()->Value());
1093 1094 1095
    }
  }
}
1096 1097 1098 1099


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


1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134
class AsciiVectorResource : public v8::String::ExternalAsciiStringResource {
 public:
  explicit AsciiVectorResource(i::Vector<const char> vector)
      : data_(vector) {}
  virtual ~AsciiVectorResource() {}
  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;
1135
  CcTest::InitializeVM();
1136
  Factory* factory = CcTest::i_isolate()->factory();
1137
  v8::HandleScope scope(CcTest::isolate());
1138 1139
  AsciiVectorResource resource(
      i::Vector<const char>("abcdefghijklmnopqrstuvwxyz", 26));
1140
  Handle<String> string = factory->NewExternalStringFromAscii(&resource);
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 1177 1178
  CHECK(!string->IsSlicedString());
  result = CompileRun(crosscheck);
  CHECK(result->IsString());
  string = v8::Utils::OpenHandle(v8::String::Cast(*result));
  CHECK(string->IsSlicedString());
  CHECK_EQ("bcdefghijklmnopqrstuvwxy", *(string->ToCString()));
}
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 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207
  v8::Local<v8::Value> result;
  Handle<String> string;
  const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
  const char* slice = "var slice = str.slice(1,-1); slice";
  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());
  CHECK_EQ("bcdefghijklmnopqrstuvwxy", *(string->ToCString()));

  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());
  CHECK_EQ("cdefghijklmnopqrstuvwx", *(string->ToCString()));
}
1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229


TEST(AsciiArrayJoin) {
  // Set heap limits.
  static const int K = 1024;
  v8::ResourceConstraints constraints;
  constraints.set_max_young_space_size(256 * K);
  constraints.set_max_old_space_size(4 * K * K);
  v8::SetResourceConstraints(&constraints);

  // 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.
  static const char* join_causing_out_of_memory =
      "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("");";

1230
  v8::HandleScope scope(CcTest::isolate());
1231 1232 1233 1234 1235 1236 1237 1238 1239 1240
  LocalContext context;
  v8::V8::IgnoreOutOfMemoryException();
  v8::Local<v8::Script> script =
      v8::Script::Compile(v8::String::New(join_causing_out_of_memory));
  v8::Local<v8::Value> result = script->Run();

  // Check for out of memory state.
  CHECK(result.IsEmpty());
  CHECK(context->HasOutOfMemoryException());
}
1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252


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;
1253 1254
  CcTest::InitializeVM();
  v8::HandleScope scope(CcTest::isolate());
1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292
  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));
  CHECK_EQ("cde", *(string->ToCString()));

  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));
  CHECK_EQ("cdefghijklmnopq", *(string->ToCString()));

  // 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);");
}
1293 1294 1295 1296


TEST(RegExpOverflow) {
  // Result string has the length 2^32, causing a 32-bit integer overflow.
1297 1298
  CcTest::InitializeVM();
  v8::HandleScope scope(CcTest::isolate());
1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309
  LocalContext context;
  v8::V8::IgnoreOutOfMemoryException();
  v8::Local<v8::Value> result = CompileRun(
      "var a = 'a';                     "
      "for (var i = 0; i < 16; i++) {   "
      "  a += a;                        "
      "}                                "
      "a.replace(/a/g, a);              ");
  CHECK(result.IsEmpty());
  CHECK(context->HasOutOfMemoryException());
}
1310 1311 1312


TEST(StringReplaceAtomTwoByteResult) {
1313 1314
  CcTest::InitializeVM();
  v8::HandleScope scope(CcTest::isolate());
1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326
  LocalContext context;
  v8::Local<v8::Value> result = CompileRun(
      "var subject = 'ascii~only~string~'; "
      "var replace = '\x80';            "
      "subject.replace(/~/g, replace);  ");
  CHECK(result->IsString());
  Handle<String> string = v8::Utils::OpenHandle(v8::String::Cast(*result));
  CHECK(string->IsSeqTwoByteString());

  v8::Local<v8::String> expected = v8_str("ascii\x80only\x80string\x80");
  CHECK(expected->Equals(result));
}
1327 1328 1329 1330


TEST(IsAscii) {
  CHECK(String::IsAscii(static_cast<char*>(NULL), 0));
1331
  CHECK(String::IsOneByte(static_cast<uc16*>(NULL), 0));
1332
}
1333 1334


1335 1336 1337 1338

template<typename Op, bool return_first>
static uint16_t ConvertLatin1(uint16_t c) {
  uint32_t result[Op::kMaxWidth];
1339
  int chars;
1340 1341 1342 1343 1344
  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;
1345
  }
1346
  return result[0];
1347 1348 1349
}


1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386
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);
1387 1388
  }
}