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