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