Line data Source code
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-inl.h"
38 : #include "src/base/platform/elapsed-timer.h"
39 : #include "src/heap/factory.h"
40 : #include "src/heap/heap-inl.h"
41 : #include "src/messages.h"
42 : #include "src/objects-inl.h"
43 : #include "src/unicode-decoder.h"
44 : #include "test/cctest/cctest.h"
45 : #include "test/cctest/heap/heap-utils.h"
46 :
47 : // Adapted from http://en.wikipedia.org/wiki/Multiply-with-carry
48 : class MyRandomNumberGenerator {
49 : public:
50 : MyRandomNumberGenerator() {
51 : init();
52 : }
53 :
54 : void init(uint32_t seed = 0x5688C73E) {
55 : static const uint32_t phi = 0x9E3779B9;
56 3470 : c = 362436;
57 3470 : i = kQSize-1;
58 3485 : Q[0] = seed;
59 3485 : Q[1] = seed + phi;
60 3485 : Q[2] = seed + phi + phi;
61 28531695 : for (unsigned j = 3; j < kQSize; j++) {
62 14264105 : Q[j] = Q[j - 3] ^ Q[j - 2] ^ phi ^ j;
63 : }
64 : }
65 :
66 : uint32_t next() {
67 : uint64_t a = 18782;
68 : uint32_t r = 0xFFFFFFFE;
69 290349515 : i = (i + 1) & (kQSize-1);
70 290349515 : uint64_t t = a * Q[i] + c;
71 290349515 : c = (t >> 32);
72 290349515 : uint32_t x = static_cast<uint32_t>(t + c);
73 290349515 : if (x < c) {
74 1230 : x++;
75 1230 : c++;
76 : }
77 290349515 : return (Q[i] = r - x);
78 : }
79 :
80 : uint32_t next(int max) {
81 121185 : return next() % max;
82 : }
83 :
84 6976020 : bool next(double threshold) {
85 6976020 : CHECK(threshold >= 0.0 && threshold <= 1.0);
86 6976020 : if (threshold == 1.0) return true;
87 6976020 : if (threshold == 0.0) return false;
88 6286950 : uint32_t value = next() % 100000;
89 6286950 : return threshold > static_cast<double>(value)/100000.0;
90 : }
91 :
92 : private:
93 : static const uint32_t kQSize = 4096;
94 : uint32_t Q[kQSize];
95 : uint32_t c;
96 : uint32_t i;
97 : };
98 :
99 : namespace v8 {
100 : namespace internal {
101 : namespace test_strings {
102 :
103 : static const int DEEP_DEPTH = 8 * 1024;
104 : static const int SUPER_DEEP_DEPTH = 80 * 1024;
105 :
106 :
107 : class Resource: public v8::String::ExternalStringResource {
108 : public:
109 980 : Resource(const uc16* data, size_t length): data_(data), length_(length) {}
110 1960 : ~Resource() override { i::DeleteArray(data_); }
111 2346520 : const uint16_t* data() const override { return data_; }
112 3885 : size_t length() const override { return length_; }
113 :
114 : private:
115 : const uc16* data_;
116 : size_t length_;
117 : };
118 :
119 :
120 : class OneByteResource : public v8::String::ExternalOneByteStringResource {
121 : public:
122 : OneByteResource(const char* data, size_t length)
123 1155 : : data_(data), length_(length) {}
124 2310 : ~OneByteResource() override { i::DeleteArray(data_); }
125 3026775 : const char* data() const override { return data_; }
126 4610 : size_t length() const override { return length_; }
127 :
128 : private:
129 : const char* data_;
130 : size_t length_;
131 : };
132 :
133 :
134 15 : static void InitializeBuildingBlocks(Handle<String>* building_blocks,
135 : int bb_length,
136 : bool long_blocks,
137 : MyRandomNumberGenerator* rng) {
138 : // A list of pointers that we don't have any interest in cleaning up.
139 : // If they are reachable from a root then leak detection won't complain.
140 : Isolate* isolate = CcTest::i_isolate();
141 : Factory* factory = isolate->factory();
142 7695 : for (int i = 0; i < bb_length; i++) {
143 3840 : int len = rng->next(16);
144 : int slice_head_chars = 0;
145 : int slice_tail_chars = 0;
146 : int slice_depth = 0;
147 26880 : for (int j = 0; j < 3; j++) {
148 11520 : if (rng->next(0.35)) slice_depth++;
149 : }
150 : // Must truncate something for a slice string. Loop until
151 : // at least one end will be sliced.
152 11610 : while (slice_head_chars == 0 && slice_tail_chars == 0) {
153 3885 : slice_head_chars = rng->next(15);
154 3885 : slice_tail_chars = rng->next(12);
155 : }
156 3840 : if (long_blocks) {
157 : // Generate building blocks which will never be merged
158 2560 : len += ConsString::kMinLength + 1;
159 1280 : } else if (len > 14) {
160 95 : len += 1234;
161 : }
162 : // Don't slice 0 length strings.
163 3840 : if (len == 0) slice_depth = 0;
164 3840 : int slice_length = slice_depth*(slice_head_chars + slice_tail_chars);
165 3840 : len += slice_length;
166 3840 : switch (rng->next(4)) {
167 : case 0: {
168 : uc16 buf[2000];
169 154565 : for (int j = 0; j < len; j++) {
170 76845 : buf[j] = rng->next(0x10000);
171 : }
172 1750 : building_blocks[i] = factory->NewStringFromTwoByte(
173 2625 : Vector<const uc16>(buf, len)).ToHandleChecked();
174 154565 : for (int j = 0; j < len; j++) {
175 76845 : CHECK_EQ(buf[j], building_blocks[i]->Get(j));
176 : }
177 : break;
178 : }
179 : case 1: {
180 : char buf[2000];
181 100505 : for (int j = 0; j < len; j++) {
182 49730 : buf[j] = rng->next(0x80);
183 : }
184 : building_blocks[i] =
185 2090 : factory->NewStringFromOneByte(OneByteVector(buf, len))
186 2090 : .ToHandleChecked();
187 100505 : for (int j = 0; j < len; j++) {
188 99460 : CHECK_EQ(buf[j], building_blocks[i]->Get(j));
189 : }
190 : break;
191 : }
192 : case 2: {
193 870 : uc16* buf = NewArray<uc16>(len);
194 97540 : for (int j = 0; j < len; j++) {
195 96670 : buf[j] = rng->next(0x10000);
196 : }
197 870 : Resource* resource = new Resource(buf, len);
198 : building_blocks[i] = v8::Utils::OpenHandle(
199 870 : *v8::String::NewExternalTwoByte(CcTest::isolate(), resource)
200 1740 : .ToLocalChecked());
201 97540 : for (int j = 0; j < len; j++) {
202 48335 : CHECK_EQ(buf[j], building_blocks[i]->Get(j));
203 : }
204 : break;
205 : }
206 : case 3: {
207 1050 : char* buf = NewArray<char>(len);
208 113060 : for (int j = 0; j < len; j++) {
209 112010 : buf[j] = rng->next(0x80);
210 : }
211 1050 : OneByteResource* resource = new OneByteResource(buf, len);
212 : building_blocks[i] = v8::Utils::OpenHandle(
213 1050 : *v8::String::NewExternalOneByte(CcTest::isolate(), resource)
214 2100 : .ToLocalChecked());
215 113060 : for (int j = 0; j < len; j++) {
216 112010 : CHECK_EQ(buf[j], building_blocks[i]->Get(j));
217 : }
218 : break;
219 : }
220 : }
221 11590 : for (int j = slice_depth; j > 0; j--) {
222 : building_blocks[i] = factory->NewSubString(
223 : building_blocks[i],
224 : slice_head_chars,
225 7750 : building_blocks[i]->length() - slice_tail_chars);
226 : }
227 7680 : CHECK(len == building_blocks[i]->length() + slice_length);
228 : }
229 15 : }
230 :
231 :
232 : class ConsStringStats {
233 : public:
234 : ConsStringStats() {
235 : Reset();
236 : }
237 : void Reset();
238 : void VerifyEqual(const ConsStringStats& that) const;
239 : int leaves_;
240 : int empty_leaves_;
241 : int chars_;
242 : int left_traversals_;
243 : int right_traversals_;
244 : private:
245 : DISALLOW_COPY_AND_ASSIGN(ConsStringStats);
246 : };
247 :
248 :
249 0 : void ConsStringStats::Reset() {
250 10350 : leaves_ = 0;
251 10350 : empty_leaves_ = 0;
252 10350 : chars_ = 0;
253 10350 : left_traversals_ = 0;
254 10350 : right_traversals_ = 0;
255 0 : }
256 :
257 :
258 6880 : void ConsStringStats::VerifyEqual(const ConsStringStats& that) const {
259 6880 : CHECK_EQ(this->leaves_, that.leaves_);
260 6880 : CHECK_EQ(this->empty_leaves_, that.empty_leaves_);
261 6880 : CHECK_EQ(this->chars_, that.chars_);
262 6880 : CHECK_EQ(this->left_traversals_, that.left_traversals_);
263 6880 : CHECK_EQ(this->right_traversals_, that.right_traversals_);
264 6880 : }
265 :
266 :
267 : class ConsStringGenerationData {
268 : public:
269 : static const int kNumberOfBuildingBlocks = 256;
270 : explicit ConsStringGenerationData(bool long_blocks);
271 : void Reset();
272 : inline Handle<String> block(int offset);
273 : inline Handle<String> block(uint32_t offset);
274 : // Input variables.
275 : double early_termination_threshold_;
276 : double leftness_;
277 : double rightness_;
278 : double empty_leaf_threshold_;
279 : int max_leaves_;
280 : // Cached data.
281 : Handle<String> building_blocks_[kNumberOfBuildingBlocks];
282 : String empty_string_;
283 : MyRandomNumberGenerator rng_;
284 : // Stats.
285 : ConsStringStats stats_;
286 : int early_terminations_;
287 : private:
288 : DISALLOW_COPY_AND_ASSIGN(ConsStringGenerationData);
289 : };
290 :
291 :
292 3855 : ConsStringGenerationData::ConsStringGenerationData(bool long_blocks) {
293 : rng_.init();
294 15 : InitializeBuildingBlocks(
295 15 : building_blocks_, kNumberOfBuildingBlocks, long_blocks, &rng_);
296 30 : empty_string_ = ReadOnlyRoots(CcTest::heap()).empty_string();
297 15 : Reset();
298 15 : }
299 :
300 :
301 : Handle<String> ConsStringGenerationData::block(uint32_t offset) {
302 1853400 : return building_blocks_[offset % kNumberOfBuildingBlocks ];
303 : }
304 :
305 :
306 : Handle<String> ConsStringGenerationData::block(int offset) {
307 1068000 : CHECK_GE(offset, 0);
308 1068080 : return building_blocks_[offset % kNumberOfBuildingBlocks];
309 : }
310 :
311 :
312 3455 : void ConsStringGenerationData::Reset() {
313 3455 : early_termination_threshold_ = 0.01;
314 3455 : leftness_ = 0.75;
315 3455 : rightness_ = 0.75;
316 3455 : empty_leaf_threshold_ = 0.02;
317 3455 : max_leaves_ = 1000;
318 : stats_.Reset();
319 3455 : early_terminations_ = 0;
320 : rng_.init();
321 3455 : }
322 :
323 2778540 : void AccumulateStats(ConsString cons_string, ConsStringStats* stats) {
324 : int left_length = cons_string->first()->length();
325 : int right_length = cons_string->second()->length();
326 2778540 : CHECK(cons_string->length() == left_length + right_length);
327 : // Check left side.
328 5557080 : bool left_is_cons = cons_string->first()->IsConsString();
329 2778540 : if (left_is_cons) {
330 1439010 : stats->left_traversals_++;
331 1439010 : AccumulateStats(ConsString::cast(cons_string->first()), stats);
332 : } else {
333 1339530 : CHECK_NE(left_length, 0);
334 1339530 : stats->leaves_++;
335 1339530 : stats->chars_ += left_length;
336 : }
337 : // Check right side.
338 5557080 : if (cons_string->second()->IsConsString()) {
339 1334370 : stats->right_traversals_++;
340 1334370 : AccumulateStats(ConsString::cast(cons_string->second()), stats);
341 : } else {
342 1444170 : if (right_length == 0) {
343 100050 : stats->empty_leaves_++;
344 100050 : CHECK(!left_is_cons);
345 : }
346 1444170 : stats->leaves_++;
347 1444170 : stats->chars_ += right_length;
348 : }
349 2778540 : }
350 :
351 3440 : void AccumulateStats(Handle<String> cons_string, ConsStringStats* stats) {
352 : DisallowHeapAllocation no_allocation;
353 6880 : if (cons_string->IsConsString()) {
354 3440 : return AccumulateStats(ConsString::cast(*cons_string), stats);
355 : }
356 : // This string got flattened by gc.
357 0 : stats->chars_ += cons_string->length();
358 : }
359 :
360 1720 : void AccumulateStatsWithOperator(ConsString cons_string,
361 : ConsStringStats* stats) {
362 1720 : ConsStringIterator iter(cons_string);
363 : int offset;
364 896270 : for (String string = iter.Next(&offset); !string.is_null();
365 : string = iter.Next(&offset)) {
366 : // Accumulate stats.
367 894550 : CHECK_EQ(0, offset);
368 894550 : stats->leaves_++;
369 894550 : stats->chars_ += string->length();
370 : }
371 1720 : }
372 :
373 1720 : void VerifyConsString(Handle<String> root, ConsStringGenerationData* data) {
374 : // Verify basic data.
375 3440 : CHECK(root->IsConsString());
376 3440 : CHECK_EQ(root->length(), data->stats_.chars_);
377 : // Recursive verify.
378 : ConsStringStats stats;
379 1720 : AccumulateStats(ConsString::cast(*root), &stats);
380 1720 : stats.VerifyEqual(data->stats_);
381 : // Iteratively verify.
382 : stats.Reset();
383 1720 : AccumulateStatsWithOperator(ConsString::cast(*root), &stats);
384 : // Don't see these. Must copy over.
385 1720 : stats.empty_leaves_ = data->stats_.empty_leaves_;
386 1720 : stats.left_traversals_ = data->stats_.left_traversals_;
387 1720 : stats.right_traversals_ = data->stats_.right_traversals_;
388 : // Adjust total leaves to compensate.
389 1720 : stats.leaves_ += stats.empty_leaves_;
390 1720 : stats.VerifyEqual(data->stats_);
391 1720 : }
392 :
393 :
394 1850040 : static Handle<String> ConstructRandomString(ConsStringGenerationData* data,
395 : unsigned max_recursion) {
396 : Isolate* isolate = CcTest::i_isolate();
397 : Factory* factory = isolate->factory();
398 : // Compute termination characteristics.
399 : bool terminate = false;
400 1850040 : bool flat = data->rng_.next(data->empty_leaf_threshold_);
401 1850040 : bool terminate_early = data->rng_.next(data->early_termination_threshold_);
402 1850040 : if (terminate_early) data->early_terminations_++;
403 : // The obvious condition.
404 1850040 : terminate |= max_recursion == 0;
405 : // Flat cons string terminate by definition.
406 1850040 : terminate |= flat;
407 : // Cap for max leaves.
408 1850040 : terminate |= data->stats_.leaves_ >= data->max_leaves_;
409 : // Roll the dice.
410 1850040 : terminate |= terminate_early;
411 : // Compute termination characteristics for each side.
412 1850040 : bool terminate_left = terminate || !data->rng_.next(data->leftness_);
413 1850040 : bool terminate_right = terminate || !data->rng_.next(data->rightness_);
414 : // Generate left string.
415 : Handle<String> left;
416 1850040 : if (terminate_left) {
417 : left = data->block(data->rng_.next());
418 891790 : data->stats_.leaves_++;
419 891790 : data->stats_.chars_ += left->length();
420 : } else {
421 958250 : data->stats_.left_traversals_++;
422 : }
423 : // Generate right string.
424 : Handle<String> right;
425 1850040 : if (terminate_right) {
426 : right = data->block(data->rng_.next());
427 961610 : data->stats_.leaves_++;
428 961610 : data->stats_.chars_ += right->length();
429 : } else {
430 888430 : data->stats_.right_traversals_++;
431 : }
432 : // Generate the necessary sub-nodes recursively.
433 1850040 : if (!terminate_right) {
434 : // Need to balance generation fairly.
435 888430 : if (!terminate_left && data->rng_.next(0.5)) {
436 305660 : left = ConstructRandomString(data, max_recursion - 1);
437 : }
438 888430 : right = ConstructRandomString(data, max_recursion - 1);
439 : }
440 1850040 : if (!terminate_left && left.is_null()) {
441 652590 : left = ConstructRandomString(data, max_recursion - 1);
442 : }
443 : // Build the cons string.
444 3700080 : Handle<String> root = factory->NewConsString(left, right).ToHandleChecked();
445 3700080 : CHECK(root->IsConsString() && !root->IsFlat());
446 : // Special work needed for flat string.
447 1850040 : if (flat) {
448 66680 : data->stats_.empty_leaves_++;
449 66680 : String::Flatten(isolate, root);
450 133360 : CHECK(root->IsConsString() && root->IsFlat());
451 : }
452 1850040 : return root;
453 : }
454 :
455 :
456 30 : static Handle<String> ConstructLeft(
457 : ConsStringGenerationData* data,
458 : int depth) {
459 : Factory* factory = CcTest::i_isolate()->factory();
460 30 : Handle<String> answer = factory->NewStringFromStaticChars("");
461 30 : data->stats_.leaves_++;
462 902770 : for (int i = 0; i < depth; i++) {
463 : Handle<String> block = data->block(i);
464 : Handle<String> next =
465 902740 : factory->NewConsString(answer, block).ToHandleChecked();
466 902740 : if (next->IsConsString()) data->stats_.leaves_++;
467 451370 : data->stats_.chars_ += block->length();
468 : answer = next;
469 : }
470 30 : data->stats_.left_traversals_ = data->stats_.leaves_ - 2;
471 30 : return answer;
472 : }
473 :
474 :
475 30 : static Handle<String> ConstructRight(
476 : ConsStringGenerationData* data,
477 : int depth) {
478 : Factory* factory = CcTest::i_isolate()->factory();
479 30 : Handle<String> answer = factory->NewStringFromStaticChars("");
480 30 : data->stats_.leaves_++;
481 451400 : for (int i = depth - 1; i >= 0; i--) {
482 : Handle<String> block = data->block(i);
483 : Handle<String> next =
484 902740 : factory->NewConsString(block, answer).ToHandleChecked();
485 902740 : if (next->IsConsString()) data->stats_.leaves_++;
486 451370 : data->stats_.chars_ += block->length();
487 : answer = next;
488 : }
489 30 : data->stats_.right_traversals_ = data->stats_.leaves_ - 2;
490 30 : return answer;
491 : }
492 :
493 :
494 82680 : static Handle<String> ConstructBalancedHelper(
495 : ConsStringGenerationData* data,
496 : int from,
497 : int to) {
498 : Factory* factory = CcTest::i_isolate()->factory();
499 82680 : CHECK(to > from);
500 82680 : if (to - from == 1) {
501 70 : data->stats_.chars_ += data->block(from)->length();
502 : return data->block(from);
503 : }
504 82610 : if (to - from == 2) {
505 41280 : data->stats_.chars_ += data->block(from)->length();
506 82560 : data->stats_.chars_ += data->block(from+1)->length();
507 82560 : return factory->NewConsString(data->block(from), data->block(from+1))
508 : .ToHandleChecked();
509 : }
510 : Handle<String> part1 =
511 41330 : ConstructBalancedHelper(data, from, from + ((to - from) / 2));
512 : Handle<String> part2 =
513 41330 : ConstructBalancedHelper(data, from + ((to - from) / 2), to);
514 82660 : if (part1->IsConsString()) data->stats_.left_traversals_++;
515 82660 : if (part2->IsConsString()) data->stats_.right_traversals_++;
516 82660 : return factory->NewConsString(part1, part2).ToHandleChecked();
517 : }
518 :
519 :
520 : static Handle<String> ConstructBalanced(
521 : ConsStringGenerationData* data, int depth = DEEP_DEPTH) {
522 20 : Handle<String> string = ConstructBalancedHelper(data, 0, depth);
523 : data->stats_.leaves_ =
524 20 : data->stats_.left_traversals_ + data->stats_.right_traversals_ + 2;
525 20 : return string;
526 : }
527 :
528 :
529 30 : static void Traverse(Handle<String> s1, Handle<String> s2) {
530 : int i = 0;
531 : StringCharacterStream character_stream_1(*s1);
532 : StringCharacterStream character_stream_2(*s2);
533 49063710 : while (character_stream_1.HasMore()) {
534 24531840 : CHECK(character_stream_2.HasMore());
535 24531840 : uint16_t c = character_stream_1.GetNext();
536 24531840 : CHECK_EQ(c, character_stream_2.GetNext());
537 24531840 : i++;
538 : }
539 30 : CHECK(!character_stream_1.HasMore());
540 30 : CHECK(!character_stream_2.HasMore());
541 30 : CHECK_EQ(s1->length(), i);
542 30 : CHECK_EQ(s2->length(), i);
543 30 : }
544 :
545 :
546 2510 : static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars) {
547 : int i = 0;
548 : StringCharacterStream character_stream_1(*s1);
549 : StringCharacterStream character_stream_2(*s2);
550 500668370 : while (character_stream_1.HasMore() && i < chars) {
551 250332930 : CHECK(character_stream_2.HasMore());
552 250332930 : uint16_t c = character_stream_1.GetNext();
553 250332930 : CHECK_EQ(c, character_stream_2.GetNext());
554 250332930 : i++;
555 : }
556 2510 : s1->Get(s1->length() - 1);
557 2510 : s2->Get(s2->length() - 1);
558 2510 : }
559 :
560 :
561 26644 : TEST(Traverse) {
562 : printf("TestTraverse\n");
563 5 : CcTest::InitializeVM();
564 : Isolate* isolate = CcTest::i_isolate();
565 10 : v8::HandleScope scope(CcTest::isolate());
566 5 : ConsStringGenerationData data(false);
567 5 : Handle<String> flat = ConstructBalanced(&data);
568 5 : String::Flatten(isolate, flat);
569 5 : Handle<String> left_asymmetric = ConstructLeft(&data, DEEP_DEPTH);
570 5 : Handle<String> right_asymmetric = ConstructRight(&data, DEEP_DEPTH);
571 5 : Handle<String> symmetric = ConstructBalanced(&data);
572 : printf("1\n");
573 5 : Traverse(flat, symmetric);
574 : printf("2\n");
575 5 : Traverse(flat, left_asymmetric);
576 : printf("3\n");
577 5 : Traverse(flat, right_asymmetric);
578 : printf("4\n");
579 : Handle<String> left_deep_asymmetric =
580 5 : ConstructLeft(&data, SUPER_DEEP_DEPTH);
581 : Handle<String> right_deep_asymmetric =
582 5 : ConstructRight(&data, SUPER_DEEP_DEPTH);
583 : printf("5\n");
584 5 : TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
585 : printf("6\n");
586 5 : TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
587 : printf("7\n");
588 5 : String::Flatten(isolate, left_asymmetric);
589 : printf("10\n");
590 5 : Traverse(flat, left_asymmetric);
591 : printf("11\n");
592 5 : String::Flatten(isolate, right_asymmetric);
593 : printf("12\n");
594 5 : Traverse(flat, right_asymmetric);
595 : printf("14\n");
596 5 : String::Flatten(isolate, symmetric);
597 : printf("15\n");
598 5 : Traverse(flat, symmetric);
599 : printf("16\n");
600 5 : String::Flatten(isolate, left_deep_asymmetric);
601 : printf("18\n");
602 5 : }
603 :
604 1720 : static void VerifyCharacterStream(String flat_string, String cons_string) {
605 : // Do not want to test ConString traversal on flat string.
606 3440 : CHECK(flat_string->IsFlat() && !flat_string->IsConsString());
607 1720 : 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 1720 : int outer_iterations = length > 20 ? 20 : length;
612 73960 : for (int j = 0; j <= outer_iterations; j++) {
613 36120 : int offset = length * j / outer_iterations;
614 36120 : if (offset < 0) offset = 0;
615 : // Want to test the offset == length case.
616 36120 : if (offset > length) offset = length;
617 : StringCharacterStream flat_stream(flat_string, offset);
618 : StringCharacterStream cons_stream(cons_string, offset);
619 430581630 : for (int i = offset; i < length; i++) {
620 : uint16_t c = flat_string->Get(i);
621 215272755 : CHECK(flat_stream.HasMore());
622 215272755 : CHECK(cons_stream.HasMore());
623 215272755 : CHECK_EQ(c, flat_stream.GetNext());
624 215272755 : CHECK_EQ(c, cons_stream.GetNext());
625 : }
626 36120 : CHECK(!flat_stream.HasMore());
627 36120 : CHECK(!cons_stream.HasMore());
628 : }
629 1720 : }
630 :
631 : static inline void PrintStats(const ConsStringGenerationData& data) {
632 : #ifdef DEBUG
633 : printf("%s: [%u], %s: [%u], %s: [%u], %s: [%u], %s: [%u], %s: [%u]\n",
634 : "leaves", data.stats_.leaves_, "empty", data.stats_.empty_leaves_,
635 : "chars", data.stats_.chars_, "lefts", data.stats_.left_traversals_,
636 : "rights", data.stats_.right_traversals_, "early_terminations",
637 : data.early_terminations_);
638 : #endif
639 : }
640 :
641 :
642 : template<typename BuildString>
643 10 : void TestStringCharacterStream(BuildString build, int test_cases) {
644 10 : FLAG_gc_global = true;
645 10 : CcTest::InitializeVM();
646 : Isolate* isolate = CcTest::i_isolate();
647 : HandleScope outer_scope(isolate);
648 10 : ConsStringGenerationData data(true);
649 3450 : for (int i = 0; i < test_cases; i++) {
650 : printf("%d\n", i);
651 : HandleScope inner_scope(isolate);
652 : AlwaysAllocateScope always_allocate(isolate);
653 : // Build flat version of cons string.
654 1720 : Handle<String> flat_string = build(i, &data);
655 : ConsStringStats flat_string_stats;
656 1720 : AccumulateStats(flat_string, &flat_string_stats);
657 : // Flatten string.
658 1720 : String::Flatten(isolate, flat_string);
659 : // Build unflattened version of cons string to test.
660 1720 : Handle<String> cons_string = build(i, &data);
661 : ConsStringStats cons_string_stats;
662 1720 : AccumulateStats(cons_string, &cons_string_stats);
663 : DisallowHeapAllocation no_allocation;
664 : PrintStats(data);
665 : // Full verify of cons string.
666 1720 : cons_string_stats.VerifyEqual(flat_string_stats);
667 1720 : cons_string_stats.VerifyEqual(data.stats_);
668 1720 : VerifyConsString(cons_string, &data);
669 : String flat_string_ptr = flat_string->IsConsString()
670 : ? ConsString::cast(*flat_string)->first()
671 3440 : : *flat_string;
672 1720 : VerifyCharacterStream(flat_string_ptr, *cons_string);
673 : }
674 10 : }
675 :
676 :
677 : static const int kCharacterStreamNonRandomCases = 8;
678 :
679 80 : static Handle<String> BuildEdgeCaseConsString(int test_case,
680 : ConsStringGenerationData* data) {
681 : Isolate* isolate = CcTest::i_isolate();
682 : Factory* factory = isolate->factory();
683 80 : data->Reset();
684 80 : switch (test_case) {
685 : case 0:
686 : return ConstructBalanced(data, 71);
687 : case 1:
688 10 : return ConstructLeft(data, 71);
689 : case 2:
690 10 : return ConstructRight(data, 71);
691 : case 3:
692 10 : return ConstructLeft(data, 10);
693 : case 4:
694 10 : return ConstructRight(data, 10);
695 : case 5:
696 : // 2 element balanced tree.
697 10 : data->stats_.chars_ += data->block(0)->length();
698 10 : data->stats_.chars_ += data->block(1)->length();
699 10 : data->stats_.leaves_ += 2;
700 20 : return factory->NewConsString(data->block(0), data->block(1))
701 : .ToHandleChecked();
702 : case 6:
703 : // Simple flattened tree.
704 10 : data->stats_.chars_ += data->block(0)->length();
705 10 : data->stats_.chars_ += data->block(1)->length();
706 10 : data->stats_.leaves_ += 2;
707 10 : data->stats_.empty_leaves_ += 1;
708 : {
709 : Handle<String> string =
710 20 : factory->NewConsString(data->block(0), data->block(1))
711 : .ToHandleChecked();
712 10 : String::Flatten(isolate, string);
713 10 : return string;
714 : }
715 : case 7:
716 : // Left node flattened.
717 10 : data->stats_.chars_ += data->block(0)->length();
718 10 : data->stats_.chars_ += data->block(1)->length();
719 10 : data->stats_.chars_ += data->block(2)->length();
720 10 : data->stats_.leaves_ += 3;
721 10 : data->stats_.empty_leaves_ += 1;
722 10 : data->stats_.left_traversals_ += 1;
723 : {
724 : Handle<String> left =
725 20 : factory->NewConsString(data->block(0), data->block(1))
726 10 : .ToHandleChecked();
727 10 : String::Flatten(isolate, left);
728 20 : return factory->NewConsString(left, data->block(2)).ToHandleChecked();
729 : }
730 : case 8:
731 : // Left node and right node flattened.
732 0 : data->stats_.chars_ += data->block(0)->length();
733 0 : data->stats_.chars_ += data->block(1)->length();
734 0 : data->stats_.chars_ += data->block(2)->length();
735 0 : data->stats_.chars_ += data->block(3)->length();
736 0 : data->stats_.leaves_ += 4;
737 0 : data->stats_.empty_leaves_ += 2;
738 0 : data->stats_.left_traversals_ += 1;
739 0 : data->stats_.right_traversals_ += 1;
740 : {
741 : Handle<String> left =
742 0 : factory->NewConsString(data->block(0), data->block(1))
743 0 : .ToHandleChecked();
744 0 : String::Flatten(isolate, left);
745 : Handle<String> right =
746 0 : factory->NewConsString(data->block(2), data->block(2))
747 0 : .ToHandleChecked();
748 0 : String::Flatten(isolate, right);
749 0 : return factory->NewConsString(left, right).ToHandleChecked();
750 : }
751 : }
752 0 : UNREACHABLE();
753 : }
754 :
755 :
756 26644 : TEST(StringCharacterStreamEdgeCases) {
757 : printf("TestStringCharacterStreamEdgeCases\n");
758 : TestStringCharacterStream(
759 5 : BuildEdgeCaseConsString, kCharacterStreamNonRandomCases);
760 5 : }
761 :
762 :
763 : static const int kBalances = 3;
764 : static const int kTreeLengths = 4;
765 : static const int kEmptyLeaves = 4;
766 : static const int kUniqueRandomParameters =
767 : kBalances*kTreeLengths*kEmptyLeaves;
768 :
769 :
770 3360 : static void InitializeGenerationData(
771 : int test_case, ConsStringGenerationData* data) {
772 : // Clear the settings and reinit the rng.
773 3360 : data->Reset();
774 : // Spin up the rng to a known location that is unique per test.
775 : static const int kPerTestJump = 501;
776 563928960 : for (int j = 0; j < test_case*kPerTestJump; j++) {
777 : data->rng_.next();
778 : }
779 : // Choose balanced, left or right heavy trees.
780 3360 : switch (test_case % kBalances) {
781 : case 0:
782 : // Nothing to do. Already balanced.
783 : break;
784 : case 1:
785 : // Left balanced.
786 1120 : data->leftness_ = 0.90;
787 1120 : data->rightness_ = 0.15;
788 1120 : break;
789 : case 2:
790 : // Right balanced.
791 1120 : data->leftness_ = 0.15;
792 1120 : data->rightness_ = 0.90;
793 1120 : break;
794 : default:
795 0 : UNREACHABLE();
796 : break;
797 : }
798 : // Must remove the influence of the above decision.
799 3360 : test_case /= kBalances;
800 : // Choose tree length.
801 3360 : switch (test_case % kTreeLengths) {
802 : case 0:
803 840 : data->max_leaves_ = 16;
804 840 : data->early_termination_threshold_ = 0.2;
805 840 : break;
806 : case 1:
807 840 : data->max_leaves_ = 50;
808 840 : data->early_termination_threshold_ = 0.05;
809 840 : break;
810 : case 2:
811 840 : data->max_leaves_ = 500;
812 840 : data->early_termination_threshold_ = 0.03;
813 840 : break;
814 : case 3:
815 840 : data->max_leaves_ = 5000;
816 840 : data->early_termination_threshold_ = 0.001;
817 840 : break;
818 : default:
819 0 : UNREACHABLE();
820 : break;
821 : }
822 : // Must remove the influence of the above decision.
823 3360 : test_case /= kTreeLengths;
824 : // Choose how much we allow empty nodes, including not at all.
825 : data->empty_leaf_threshold_ =
826 3360 : 0.03 * static_cast<double>(test_case % kEmptyLeaves);
827 3360 : }
828 :
829 :
830 3360 : static Handle<String> BuildRandomConsString(
831 : int test_case, ConsStringGenerationData* data) {
832 3360 : InitializeGenerationData(test_case, data);
833 3360 : return ConstructRandomString(data, 200);
834 : }
835 :
836 :
837 26644 : TEST(StringCharacterStreamRandom) {
838 : printf("StringCharacterStreamRandom\n");
839 5 : TestStringCharacterStream(BuildRandomConsString, kUniqueRandomParameters*7);
840 5 : }
841 :
842 :
843 : static const int kDeepOneByteDepth = 100000;
844 :
845 :
846 26644 : TEST(DeepOneByte) {
847 5 : CcTest::InitializeVM();
848 : Isolate* isolate = CcTest::i_isolate();
849 : Factory* factory = isolate->factory();
850 10 : v8::HandleScope scope(CcTest::isolate());
851 :
852 5 : char* foo = NewArray<char>(kDeepOneByteDepth);
853 1000005 : for (int i = 0; i < kDeepOneByteDepth; i++) {
854 500000 : foo[i] = "foo "[i % 4];
855 : }
856 : Handle<String> string =
857 10 : factory->NewStringFromOneByte(OneByteVector(foo, kDeepOneByteDepth))
858 5 : .ToHandleChecked();
859 5 : Handle<String> foo_string = factory->NewStringFromStaticChars("foo");
860 100005 : for (int i = 0; i < kDeepOneByteDepth; i += 10) {
861 100000 : string = factory->NewConsString(string, foo_string).ToHandleChecked();
862 : }
863 : Handle<String> flat_string =
864 10 : factory->NewConsString(string, foo_string).ToHandleChecked();
865 5 : String::Flatten(isolate, flat_string);
866 :
867 5005 : for (int i = 0; i < 500; i++) {
868 2500 : TraverseFirst(flat_string, string, kDeepOneByteDepth);
869 : }
870 : DeleteArray<char>(foo);
871 5 : }
872 :
873 :
874 26644 : TEST(Utf8Conversion) {
875 : // Smoke test for converting strings to utf-8.
876 5 : CcTest::InitializeVM();
877 10 : v8::HandleScope handle_scope(CcTest::isolate());
878 : // A simple one-byte string
879 : const char* one_byte_string = "abcdef12345";
880 5 : int len = v8::String::NewFromUtf8(CcTest::isolate(), one_byte_string,
881 : v8::NewStringType::kNormal,
882 5 : StrLength(one_byte_string))
883 : .ToLocalChecked()
884 10 : ->Utf8Length(CcTest::isolate());
885 5 : CHECK_EQ(StrLength(one_byte_string), len);
886 : // A mixed one-byte and two-byte string
887 : // U+02E4 -> CB A4
888 : // U+0064 -> 64
889 : // U+12E4 -> E1 8B A4
890 : // U+0030 -> 30
891 : // U+3045 -> E3 81 85
892 5 : const uint16_t mixed_string[] = {0x02E4, 0x0064, 0x12E4, 0x0030, 0x3045};
893 : // The characters we expect to be output
894 : const unsigned char as_utf8[11] = {0xCB, 0xA4, 0x64, 0xE1, 0x8B, 0xA4, 0x30,
895 5 : 0xE3, 0x81, 0x85, 0x00};
896 : // The number of bytes expected to be written for each length
897 5 : const int lengths[12] = {0, 0, 2, 3, 3, 3, 6, 7, 7, 7, 10, 11};
898 5 : const int char_lengths[12] = {0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5};
899 : v8::Local<v8::String> mixed =
900 5 : v8::String::NewFromTwoByte(CcTest::isolate(), mixed_string,
901 5 : v8::NewStringType::kNormal, 5)
902 : .ToLocalChecked();
903 5 : CHECK_EQ(10, mixed->Utf8Length(CcTest::isolate()));
904 : // Try encoding the string with all capacities
905 : char buffer[11];
906 : const char kNoChar = static_cast<char>(-1);
907 125 : for (int i = 0; i <= 11; i++) {
908 : // Clear the buffer before reusing it
909 1380 : for (int j = 0; j < 11; j++)
910 660 : buffer[j] = kNoChar;
911 : int chars_written;
912 : int written =
913 60 : mixed->WriteUtf8(CcTest::isolate(), buffer, i, &chars_written);
914 60 : CHECK_EQ(lengths[i], written);
915 60 : CHECK_EQ(char_lengths[i], chars_written);
916 : // Check that the contents are correct
917 650 : for (int j = 0; j < lengths[i]; j++)
918 295 : CHECK_EQ(as_utf8[j], static_cast<unsigned char>(buffer[j]));
919 : // Check that the rest of the buffer hasn't been touched
920 790 : for (int j = lengths[i]; j < 11; j++)
921 365 : CHECK_EQ(kNoChar, buffer[j]);
922 : }
923 5 : }
924 :
925 26644 : TEST(Utf8ConversionPerf) {
926 : // Smoke test for converting strings to utf-8.
927 5 : LocalContext context;
928 10 : v8::HandleScope handle_scope(CcTest::isolate());
929 : v8::Local<v8::String> ascii_string =
930 : CompileRun("'abc'.repeat(1E6)").As<v8::String>();
931 : v8::Local<v8::String> one_byte_string =
932 : CompileRun("'\\u0255\\u0254\\u0253'.repeat(1E6)").As<v8::String>();
933 : v8::Local<v8::String> two_byte_string =
934 : CompileRun("'\\u2255\\u2254\\u2253'.repeat(1E6)").As<v8::String>();
935 : v8::Local<v8::String> surrogate_string =
936 : CompileRun("'\\u{12345}\\u2244'.repeat(1E6)").As<v8::String>();
937 : int size = 1E7;
938 5 : char* buffer = new char[4 * size];
939 : {
940 : v8::base::ElapsedTimer timer;
941 : timer.Start();
942 5 : ascii_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
943 10 : printf("ascii string %0.3f\n", timer.Elapsed().InMillisecondsF());
944 : timer.Stop();
945 : }
946 : {
947 : v8::base::ElapsedTimer timer;
948 : timer.Start();
949 5 : ascii_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
950 10 : printf("ascii string %0.3f\n", timer.Elapsed().InMillisecondsF());
951 : timer.Stop();
952 : }
953 : {
954 : v8::base::ElapsedTimer timer;
955 : timer.Start();
956 5 : ascii_string->WriteUtf8(CcTest::isolate(), buffer, 4 * size, nullptr);
957 10 : printf("ascii string %0.3f\n", timer.Elapsed().InMillisecondsF());
958 : timer.Stop();
959 : }
960 :
961 : {
962 : v8::base::ElapsedTimer timer;
963 : timer.Start();
964 5 : one_byte_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
965 10 : printf("one byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
966 : timer.Stop();
967 : }
968 : {
969 : v8::base::ElapsedTimer timer;
970 : timer.Start();
971 5 : one_byte_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
972 10 : printf("one byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
973 : timer.Stop();
974 : }
975 : {
976 : v8::base::ElapsedTimer timer;
977 : timer.Start();
978 5 : one_byte_string->WriteUtf8(CcTest::isolate(), buffer, 4 * size, nullptr);
979 10 : printf("one byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
980 : timer.Stop();
981 : }
982 :
983 : {
984 : v8::base::ElapsedTimer timer;
985 : timer.Start();
986 5 : two_byte_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
987 10 : printf("two byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
988 : timer.Stop();
989 : }
990 : {
991 : v8::base::ElapsedTimer timer;
992 : timer.Start();
993 5 : two_byte_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
994 10 : printf("two byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
995 : timer.Stop();
996 : }
997 : {
998 : v8::base::ElapsedTimer timer;
999 : timer.Start();
1000 5 : two_byte_string->WriteUtf8(CcTest::isolate(), buffer, 4 * size, nullptr);
1001 10 : printf("two byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
1002 : timer.Stop();
1003 : }
1004 :
1005 : {
1006 : v8::base::ElapsedTimer timer;
1007 : timer.Start();
1008 5 : surrogate_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
1009 10 : printf("surrogate string %0.3f\n", timer.Elapsed().InMillisecondsF());
1010 : timer.Stop();
1011 : }
1012 : {
1013 : v8::base::ElapsedTimer timer;
1014 : timer.Start();
1015 5 : surrogate_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
1016 10 : printf("surrogate string %0.3f\n", timer.Elapsed().InMillisecondsF());
1017 : timer.Stop();
1018 : }
1019 : {
1020 : v8::base::ElapsedTimer timer;
1021 : timer.Start();
1022 5 : surrogate_string->WriteUtf8(CcTest::isolate(), buffer, 4 * size, nullptr);
1023 10 : printf("surrogate string %0.3f\n", timer.Elapsed().InMillisecondsF());
1024 : timer.Stop();
1025 : }
1026 5 : delete[] buffer;
1027 5 : }
1028 :
1029 26644 : TEST(ExternalShortStringAdd) {
1030 5 : LocalContext context;
1031 10 : v8::HandleScope handle_scope(CcTest::isolate());
1032 :
1033 : // Make sure we cover all always-flat lengths and at least one above.
1034 : static const int kMaxLength = 20;
1035 : CHECK_GT(kMaxLength, i::ConsString::kMinLength);
1036 :
1037 : // Allocate two JavaScript arrays for holding short strings.
1038 : v8::Local<v8::Array> one_byte_external_strings =
1039 5 : v8::Array::New(CcTest::isolate(), kMaxLength + 1);
1040 : v8::Local<v8::Array> non_one_byte_external_strings =
1041 5 : v8::Array::New(CcTest::isolate(), kMaxLength + 1);
1042 :
1043 : // Generate short one-byte and two-byte external strings.
1044 215 : for (int i = 0; i <= kMaxLength; i++) {
1045 105 : char* one_byte = NewArray<char>(i + 1);
1046 2205 : for (int j = 0; j < i; j++) {
1047 1050 : one_byte[j] = 'a';
1048 : }
1049 : // Terminating '\0' is left out on purpose. It is not required for external
1050 : // string data.
1051 105 : OneByteResource* one_byte_resource = new OneByteResource(one_byte, i);
1052 : v8::Local<v8::String> one_byte_external_string =
1053 105 : v8::String::NewExternalOneByte(CcTest::isolate(), one_byte_resource)
1054 : .ToLocalChecked();
1055 :
1056 210 : one_byte_external_strings->Set(context.local(),
1057 : v8::Integer::New(CcTest::isolate(), i),
1058 210 : one_byte_external_string)
1059 : .FromJust();
1060 105 : uc16* non_one_byte = NewArray<uc16>(i + 1);
1061 2205 : for (int j = 0; j < i; j++) {
1062 1050 : non_one_byte[j] = 0x1234;
1063 : }
1064 : // Terminating '\0' is left out on purpose. It is not required for external
1065 : // string data.
1066 105 : Resource* resource = new Resource(non_one_byte, i);
1067 : v8::Local<v8::String> non_one_byte_external_string =
1068 105 : v8::String::NewExternalTwoByte(CcTest::isolate(), resource)
1069 : .ToLocalChecked();
1070 210 : non_one_byte_external_strings->Set(context.local(),
1071 : v8::Integer::New(CcTest::isolate(), i),
1072 210 : non_one_byte_external_string)
1073 : .FromJust();
1074 : }
1075 :
1076 : // Add the arrays with the short external strings in the global object.
1077 5 : v8::Local<v8::Object> global = context->Global();
1078 10 : global->Set(context.local(), v8_str("external_one_byte"),
1079 10 : one_byte_external_strings)
1080 : .FromJust();
1081 10 : global->Set(context.local(), v8_str("external_non_one_byte"),
1082 10 : non_one_byte_external_strings)
1083 : .FromJust();
1084 10 : global->Set(context.local(), v8_str("max_length"),
1085 15 : v8::Integer::New(CcTest::isolate(), kMaxLength))
1086 : .FromJust();
1087 :
1088 : // Add short external one-byte and two-byte strings checking the result.
1089 : static const char* source =
1090 : "function test() {"
1091 : " var one_byte_chars = 'aaaaaaaaaaaaaaaaaaaa';"
1092 : " var non_one_byte_chars = "
1093 : "'\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1"
1094 : "234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\"
1095 : "u1234';" // NOLINT
1096 : " if (one_byte_chars.length != max_length) return 1;"
1097 : " if (non_one_byte_chars.length != max_length) return 2;"
1098 : " var one_byte = Array(max_length + 1);"
1099 : " var non_one_byte = Array(max_length + 1);"
1100 : " for (var i = 0; i <= max_length; i++) {"
1101 : " one_byte[i] = one_byte_chars.substring(0, i);"
1102 : " non_one_byte[i] = non_one_byte_chars.substring(0, i);"
1103 : " };"
1104 : " for (var i = 0; i <= max_length; i++) {"
1105 : " if (one_byte[i] != external_one_byte[i]) return 3;"
1106 : " if (non_one_byte[i] != external_non_one_byte[i]) return 4;"
1107 : " for (var j = 0; j < i; j++) {"
1108 : " if (external_one_byte[i] !="
1109 : " (external_one_byte[j] + external_one_byte[i - j])) return "
1110 : "5;"
1111 : " if (external_non_one_byte[i] !="
1112 : " (external_non_one_byte[j] + external_non_one_byte[i - "
1113 : "j])) return 6;"
1114 : " if (non_one_byte[i] != (non_one_byte[j] + non_one_byte[i - "
1115 : "j])) return 7;"
1116 : " if (one_byte[i] != (one_byte[j] + one_byte[i - j])) return 8;"
1117 : " if (one_byte[i] != (external_one_byte[j] + one_byte[i - j])) "
1118 : "return 9;"
1119 : " if (one_byte[i] != (one_byte[j] + external_one_byte[i - j])) "
1120 : "return 10;"
1121 : " if (non_one_byte[i] !="
1122 : " (external_non_one_byte[j] + non_one_byte[i - j])) return "
1123 : "11;"
1124 : " if (non_one_byte[i] !="
1125 : " (non_one_byte[j] + external_non_one_byte[i - j])) return "
1126 : "12;"
1127 : " }"
1128 : " }"
1129 : " return 0;"
1130 : "};"
1131 : "test()";
1132 15 : CHECK_EQ(0, CompileRun(source)->Int32Value(context.local()).FromJust());
1133 5 : }
1134 :
1135 26644 : TEST(ReplaceInvalidUtf8) {
1136 5 : LocalContext context;
1137 10 : v8::HandleScope handle_scope(CcTest::isolate());
1138 : v8::Local<v8::String> string = CompileRun("'ab\\ud800cd'").As<v8::String>();
1139 : char buffer[7];
1140 : memset(buffer, 0, 7);
1141 5 : int chars_written = 0;
1142 5 : int size = string->WriteUtf8(CcTest::isolate(), buffer, 7, &chars_written,
1143 5 : v8::String::REPLACE_INVALID_UTF8);
1144 5 : CHECK_EQ(7, size);
1145 5 : CHECK_EQ(5, chars_written);
1146 5 : CHECK_EQ(0, memcmp("\x61\x62\xef\xbf\xbd\x63\x64", buffer, 7));
1147 :
1148 : memset(buffer, 0, 7);
1149 5 : chars_written = 0;
1150 5 : size = string->WriteUtf8(CcTest::isolate(), buffer, 6, &chars_written,
1151 5 : v8::String::REPLACE_INVALID_UTF8);
1152 5 : CHECK_EQ(6, size);
1153 5 : CHECK_EQ(4, chars_written);
1154 5 : CHECK_EQ(0, memcmp("\x61\x62\xef\xbf\xbd\x63", buffer, 6));
1155 5 : }
1156 :
1157 26644 : TEST(JSONStringifySliceMadeExternal) {
1158 : if (!FLAG_string_slices) return;
1159 5 : CcTest::InitializeVM();
1160 : // Create a sliced string from a one-byte string. The latter is turned
1161 : // into a two-byte external string. Check that JSON.stringify works.
1162 10 : v8::HandleScope handle_scope(CcTest::isolate());
1163 : v8::Local<v8::String> underlying =
1164 : CompileRun(
1165 : "var underlying = 'abcdefghijklmnopqrstuvwxyz';"
1166 : "underlying")
1167 10 : ->ToString(CcTest::isolate()->GetCurrentContext())
1168 : .ToLocalChecked();
1169 : v8::Local<v8::String> slice =
1170 : CompileRun(
1171 : "var slice = '';"
1172 : "slice = underlying.slice(1);"
1173 : "slice")
1174 10 : ->ToString(CcTest::isolate()->GetCurrentContext())
1175 : .ToLocalChecked();
1176 5 : CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
1177 5 : CHECK(v8::Utils::OpenHandle(*underlying)->IsSeqOneByteString());
1178 :
1179 5 : int length = underlying->Length();
1180 5 : uc16* two_byte = NewArray<uc16>(length + 1);
1181 5 : underlying->Write(CcTest::isolate(), two_byte);
1182 5 : Resource* resource = new Resource(two_byte, length);
1183 5 : CHECK(underlying->MakeExternal(resource));
1184 5 : CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
1185 5 : CHECK(v8::Utils::OpenHandle(*underlying)->IsExternalTwoByteString());
1186 :
1187 5 : CHECK_EQ(0,
1188 : strcmp("\"bcdefghijklmnopqrstuvwxyz\"",
1189 : *v8::String::Utf8Value(CcTest::isolate(),
1190 : CompileRun("JSON.stringify(slice)"))));
1191 : }
1192 :
1193 26644 : TEST(JSONStringifyWellFormed) {
1194 5 : FLAG_harmony_json_stringify = true;
1195 5 : CcTest::InitializeVM();
1196 10 : v8::HandleScope handle_scope(CcTest::isolate());
1197 5 : v8::Local<v8::Context> context = CcTest::isolate()->GetCurrentContext();
1198 :
1199 : // Test some leading surrogates (U+D800 to U+DBFF).
1200 : { // U+D800
1201 5 : CHECK_EQ(
1202 : 0, strcmp("\"\\ud800\"", *v8::String::Utf8Value(
1203 : CcTest::isolate(),
1204 : CompileRun("JSON.stringify('\\uD800')"))));
1205 5 : v8::Local<v8::String> json = v8_str("\"\\ud800\"");
1206 : v8::Local<v8::Value> parsed =
1207 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1208 15 : CHECK(v8::JSON::Stringify(context, parsed)
1209 : .ToLocalChecked()
1210 : ->Equals(context, json)
1211 : .FromJust());
1212 : }
1213 :
1214 : { // U+DAAA
1215 5 : CHECK_EQ(
1216 : 0, strcmp("\"\\udaaa\"", *v8::String::Utf8Value(
1217 : CcTest::isolate(),
1218 : CompileRun("JSON.stringify('\\uDAAA')"))));
1219 5 : v8::Local<v8::String> json = v8_str("\"\\udaaa\"");
1220 : v8::Local<v8::Value> parsed =
1221 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1222 15 : CHECK(v8::JSON::Stringify(context, parsed)
1223 : .ToLocalChecked()
1224 : ->Equals(context, json)
1225 : .FromJust());
1226 : }
1227 :
1228 : { // U+DBFF
1229 5 : CHECK_EQ(
1230 : 0, strcmp("\"\\udbff\"", *v8::String::Utf8Value(
1231 : CcTest::isolate(),
1232 : CompileRun("JSON.stringify('\\uDBFF')"))));
1233 5 : v8::Local<v8::String> json = v8_str("\"\\udbff\"");
1234 : v8::Local<v8::Value> parsed =
1235 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1236 15 : CHECK(v8::JSON::Stringify(context, parsed)
1237 : .ToLocalChecked()
1238 : ->Equals(context, json)
1239 : .FromJust());
1240 : }
1241 :
1242 : // Test some trailing surrogates (U+DC00 to U+DFFF).
1243 : { // U+DC00
1244 5 : CHECK_EQ(
1245 : 0, strcmp("\"\\udc00\"", *v8::String::Utf8Value(
1246 : CcTest::isolate(),
1247 : CompileRun("JSON.stringify('\\uDC00')"))));
1248 5 : v8::Local<v8::String> json = v8_str("\"\\udc00\"");
1249 : v8::Local<v8::Value> parsed =
1250 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1251 15 : CHECK(v8::JSON::Stringify(context, parsed)
1252 : .ToLocalChecked()
1253 : ->Equals(context, json)
1254 : .FromJust());
1255 : }
1256 :
1257 : { // U+DDDD
1258 5 : CHECK_EQ(
1259 : 0, strcmp("\"\\udddd\"", *v8::String::Utf8Value(
1260 : CcTest::isolate(),
1261 : CompileRun("JSON.stringify('\\uDDDD')"))));
1262 5 : v8::Local<v8::String> json = v8_str("\"\\udddd\"");
1263 : v8::Local<v8::Value> parsed =
1264 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1265 15 : CHECK(v8::JSON::Stringify(context, parsed)
1266 : .ToLocalChecked()
1267 : ->Equals(context, json)
1268 : .FromJust());
1269 : }
1270 :
1271 : { // U+DFFF
1272 5 : CHECK_EQ(
1273 : 0, strcmp("\"\\udfff\"", *v8::String::Utf8Value(
1274 : CcTest::isolate(),
1275 : CompileRun("JSON.stringify('\\uDFFF')"))));
1276 5 : v8::Local<v8::String> json = v8_str("\"\\udfff\"");
1277 : v8::Local<v8::Value> parsed =
1278 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1279 15 : CHECK(v8::JSON::Stringify(context, parsed)
1280 : .ToLocalChecked()
1281 : ->Equals(context, json)
1282 : .FromJust());
1283 : }
1284 5 : }
1285 :
1286 26644 : TEST(CachedHashOverflow) {
1287 5 : CcTest::InitializeVM();
1288 : // We incorrectly allowed strings to be tagged as array indices even if their
1289 : // values didn't fit in the hash field.
1290 : // See http://code.google.com/p/v8/issues/detail?id=728
1291 : Isolate* isolate = CcTest::i_isolate();
1292 :
1293 10 : v8::HandleScope handle_scope(CcTest::isolate());
1294 : // Lines must be executed sequentially. Combining them into one script
1295 : // makes the bug go away.
1296 : const char* lines[] = {"var x = [];", "x[4] = 42;", "var s = \"1073741828\";",
1297 : "x[s];", "x[s] = 37;", "x[4];",
1298 5 : "x[s];"};
1299 :
1300 : Handle<Smi> fortytwo(Smi::FromInt(42), isolate);
1301 : Handle<Smi> thirtyseven(Smi::FromInt(37), isolate);
1302 : Handle<Object> results[] = { isolate->factory()->undefined_value(),
1303 : fortytwo,
1304 : isolate->factory()->undefined_value(),
1305 : isolate->factory()->undefined_value(),
1306 : thirtyseven,
1307 : fortytwo,
1308 : thirtyseven // Bug yielded 42 here.
1309 : };
1310 :
1311 5 : v8::Local<v8::Context> context = CcTest::isolate()->GetCurrentContext();
1312 75 : for (size_t i = 0; i < arraysize(lines); i++) {
1313 35 : const char* line = lines[i];
1314 : printf("%s\n", line);
1315 : v8::Local<v8::Value> result =
1316 35 : v8::Script::Compile(context,
1317 35 : v8::String::NewFromUtf8(CcTest::isolate(), line,
1318 35 : v8::NewStringType::kNormal)
1319 : .ToLocalChecked())
1320 : .ToLocalChecked()
1321 35 : ->Run(context)
1322 : .ToLocalChecked();
1323 70 : CHECK_EQ(results[i]->IsUndefined(CcTest::i_isolate()),
1324 : result->IsUndefined());
1325 70 : CHECK_EQ(results[i]->IsNumber(), result->IsNumber());
1326 35 : if (result->IsNumber()) {
1327 20 : int32_t value = 0;
1328 20 : CHECK(results[i]->ToInt32(&value));
1329 40 : CHECK_EQ(value, result->ToInt32(context).ToLocalChecked()->Value());
1330 : }
1331 : }
1332 5 : }
1333 :
1334 :
1335 26644 : TEST(SliceFromCons) {
1336 : if (!FLAG_string_slices) return;
1337 5 : CcTest::InitializeVM();
1338 : Factory* factory = CcTest::i_isolate()->factory();
1339 10 : v8::HandleScope scope(CcTest::isolate());
1340 : Handle<String> string =
1341 5 : factory->NewStringFromStaticChars("parentparentparent");
1342 : Handle<String> parent =
1343 10 : factory->NewConsString(string, string).ToHandleChecked();
1344 5 : CHECK(parent->IsConsString());
1345 5 : CHECK(!parent->IsFlat());
1346 : Handle<String> slice = factory->NewSubString(parent, 1, 25);
1347 : // After slicing, the original string becomes a flat cons.
1348 5 : CHECK(parent->IsFlat());
1349 5 : CHECK(slice->IsSlicedString());
1350 10 : CHECK_EQ(SlicedString::cast(*slice)->parent(),
1351 : // Parent could have been short-circuited.
1352 : parent->IsConsString() ? ConsString::cast(*parent)->first()
1353 : : *parent);
1354 5 : CHECK(SlicedString::cast(*slice)->parent()->IsSeqString());
1355 5 : CHECK(slice->IsFlat());
1356 : }
1357 :
1358 :
1359 : class OneByteVectorResource : public v8::String::ExternalOneByteStringResource {
1360 : public:
1361 : explicit OneByteVectorResource(i::Vector<const char> vector)
1362 10 : : data_(vector) {}
1363 20 : ~OneByteVectorResource() override = default;
1364 60 : size_t length() const override { return data_.length(); }
1365 20 : const char* data() const override { return data_.start(); }
1366 : private:
1367 : i::Vector<const char> data_;
1368 : };
1369 :
1370 26644 : TEST(InternalizeExternal) {
1371 : #ifdef ENABLE_MINOR_MC
1372 : // TODO(mlippautz): Remove once we add support for forwarding ThinStrings in
1373 : // minor MC
1374 5 : if (FLAG_minor_mc) return;
1375 : #endif // ENABLE_MINOR_MC
1376 5 : FLAG_stress_incremental_marking = false;
1377 5 : FLAG_thin_strings = true;
1378 5 : CcTest::InitializeVM();
1379 : i::Isolate* isolate = CcTest::i_isolate();
1380 : Factory* factory = isolate->factory();
1381 : // This won't leak; the external string mechanism will call Dispose() on it.
1382 : OneByteVectorResource* resource =
1383 5 : new OneByteVectorResource(i::Vector<const char>("prop-1234", 9));
1384 : {
1385 10 : v8::HandleScope scope(CcTest::isolate());
1386 : v8::Local<v8::String> ext_string =
1387 5 : v8::String::NewExternalOneByte(CcTest::isolate(), resource)
1388 : .ToLocalChecked();
1389 : Handle<String> string = v8::Utils::OpenHandle(*ext_string);
1390 5 : CHECK(string->IsExternalString());
1391 5 : CHECK(!string->IsInternalizedString());
1392 5 : CHECK(!i::Heap::InYoungGeneration(*string));
1393 5 : CHECK_EQ(
1394 : isolate->factory()->string_table()->LookupStringIfExists_NoAllocate(
1395 : isolate, string->ptr()),
1396 : Smi::FromInt(ResultSentinel::kNotFound).ptr());
1397 5 : factory->InternalizeName(string);
1398 5 : CHECK(string->IsExternalString());
1399 5 : CHECK(string->IsInternalizedString());
1400 5 : CHECK(!i::Heap::InYoungGeneration(*string));
1401 : }
1402 5 : CcTest::CollectGarbage(i::OLD_SPACE);
1403 5 : CcTest::CollectGarbage(i::OLD_SPACE);
1404 : }
1405 :
1406 26644 : TEST(SliceFromExternal) {
1407 : if (!FLAG_string_slices) return;
1408 5 : CcTest::InitializeVM();
1409 : Factory* factory = CcTest::i_isolate()->factory();
1410 10 : v8::HandleScope scope(CcTest::isolate());
1411 : OneByteVectorResource resource(
1412 : i::Vector<const char>("abcdefghijklmnopqrstuvwxyz", 26));
1413 : Handle<String> string =
1414 10 : factory->NewExternalStringFromOneByte(&resource).ToHandleChecked();
1415 5 : CHECK(string->IsExternalString());
1416 : Handle<String> slice = factory->NewSubString(string, 1, 25);
1417 5 : CHECK(slice->IsSlicedString());
1418 5 : CHECK(string->IsExternalString());
1419 5 : CHECK_EQ(SlicedString::cast(*slice)->parent(), *string);
1420 5 : CHECK(SlicedString::cast(*slice)->parent()->IsExternalString());
1421 5 : CHECK(slice->IsFlat());
1422 : // This avoids the GC from trying to free stack allocated resources.
1423 10 : i::Handle<i::ExternalOneByteString>::cast(string)->SetResource(
1424 5 : CcTest::i_isolate(), nullptr);
1425 : }
1426 :
1427 :
1428 26644 : TEST(TrivialSlice) {
1429 : // This tests whether a slice that contains the entire parent string
1430 : // actually creates a new string (it should not).
1431 : if (!FLAG_string_slices) return;
1432 5 : CcTest::InitializeVM();
1433 : Factory* factory = CcTest::i_isolate()->factory();
1434 10 : v8::HandleScope scope(CcTest::isolate());
1435 : v8::Local<v8::Value> result;
1436 : Handle<String> string;
1437 : const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
1438 : const char* check = "str.slice(0,26)";
1439 : const char* crosscheck = "str.slice(1,25)";
1440 :
1441 : CompileRun(init);
1442 :
1443 : result = CompileRun(check);
1444 5 : CHECK(result->IsString());
1445 : string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1446 5 : CHECK(!string->IsSlicedString());
1447 :
1448 5 : string = factory->NewSubString(string, 0, 26);
1449 5 : CHECK(!string->IsSlicedString());
1450 : result = CompileRun(crosscheck);
1451 5 : CHECK(result->IsString());
1452 : string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1453 5 : CHECK(string->IsSlicedString());
1454 15 : CHECK_EQ(0, strcmp("bcdefghijklmnopqrstuvwxy", string->ToCString().get()));
1455 : }
1456 :
1457 :
1458 26644 : TEST(SliceFromSlice) {
1459 : // This tests whether a slice that contains the entire parent string
1460 : // actually creates a new string (it should not).
1461 : if (!FLAG_string_slices) return;
1462 5 : CcTest::InitializeVM();
1463 10 : v8::HandleScope scope(CcTest::isolate());
1464 : v8::Local<v8::Value> result;
1465 : Handle<String> string;
1466 : const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
1467 : const char* slice = "var slice = ''; slice = str.slice(1,-1); slice";
1468 : const char* slice_from_slice = "slice.slice(1,-1);";
1469 :
1470 : CompileRun(init);
1471 : result = CompileRun(slice);
1472 5 : CHECK(result->IsString());
1473 : string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1474 5 : CHECK(string->IsSlicedString());
1475 5 : CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
1476 15 : CHECK_EQ(0, strcmp("bcdefghijklmnopqrstuvwxy", string->ToCString().get()));
1477 :
1478 : result = CompileRun(slice_from_slice);
1479 5 : CHECK(result->IsString());
1480 : string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1481 5 : CHECK(string->IsSlicedString());
1482 5 : CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
1483 15 : CHECK_EQ(0, strcmp("cdefghijklmnopqrstuvwx", string->ToCString().get()));
1484 : }
1485 :
1486 :
1487 26644 : UNINITIALIZED_TEST(OneByteArrayJoin) {
1488 : v8::Isolate::CreateParams create_params;
1489 : // Set heap limits.
1490 : create_params.constraints.set_max_semi_space_size_in_kb(1024);
1491 : #ifdef DEBUG
1492 : create_params.constraints.set_max_old_space_size(20);
1493 : #else
1494 : create_params.constraints.set_max_old_space_size(7);
1495 : #endif
1496 5 : create_params.array_buffer_allocator = CcTest::array_buffer_allocator();
1497 5 : v8::Isolate* isolate = v8::Isolate::New(create_params);
1498 5 : isolate->Enter();
1499 :
1500 : {
1501 : // String s is made of 2^17 = 131072 'c' characters and a is an array
1502 : // starting with 'bad', followed by 2^14 times the string s. That means the
1503 : // total length of the concatenated strings is 2^31 + 3. So on 32bit systems
1504 : // summing the lengths of the strings (as Smis) overflows and wraps.
1505 5 : LocalContext context(isolate);
1506 10 : v8::HandleScope scope(isolate);
1507 10 : v8::TryCatch try_catch(isolate);
1508 5 : CHECK(CompileRun(
1509 : "var two_14 = Math.pow(2, 14);"
1510 : "var two_17 = Math.pow(2, 17);"
1511 : "var s = Array(two_17 + 1).join('c');"
1512 : "var a = ['bad'];"
1513 : "for (var i = 1; i <= two_14; i++) a.push(s);"
1514 : "a.join("
1515 : ");").IsEmpty());
1516 5 : CHECK(try_catch.HasCaught());
1517 : }
1518 5 : isolate->Exit();
1519 5 : isolate->Dispose();
1520 5 : }
1521 :
1522 : namespace {
1523 :
1524 : int* global_use_counts = nullptr;
1525 :
1526 23 : void MockUseCounterCallback(v8::Isolate* isolate,
1527 : v8::Isolate::UseCounterFeature feature) {
1528 23 : ++global_use_counts[feature];
1529 23 : }
1530 : }
1531 :
1532 :
1533 26644 : TEST(CountBreakIterator) {
1534 5 : CcTest::InitializeVM();
1535 10 : v8::HandleScope scope(CcTest::isolate());
1536 5 : LocalContext context;
1537 5 : int use_counts[v8::Isolate::kUseCounterFeatureCount] = {};
1538 5 : global_use_counts = use_counts;
1539 5 : CcTest::isolate()->SetUseCounterCallback(MockUseCounterCallback);
1540 5 : CHECK_EQ(0, use_counts[v8::Isolate::kBreakIterator]);
1541 : v8::Local<v8::Value> result = CompileRun(
1542 : "(function() {"
1543 : " if (!this.Intl) return 0;"
1544 : " var iterator = Intl.v8BreakIterator(['en']);"
1545 : " iterator.adoptText('Now is the time');"
1546 : " iterator.next();"
1547 : " return iterator.next();"
1548 : "})();");
1549 5 : CHECK(result->IsNumber());
1550 : int uses =
1551 10 : result->ToInt32(context.local()).ToLocalChecked()->Value() == 0 ? 0 : 1;
1552 5 : CHECK_EQ(uses, use_counts[v8::Isolate::kBreakIterator]);
1553 : // Make sure GC cleans up the break iterator, so we don't get a memory leak
1554 : // reported by ASAN.
1555 5 : CcTest::isolate()->LowMemoryNotification();
1556 5 : }
1557 :
1558 :
1559 26644 : TEST(StringReplaceAtomTwoByteResult) {
1560 5 : CcTest::InitializeVM();
1561 10 : v8::HandleScope scope(CcTest::isolate());
1562 5 : LocalContext context;
1563 : v8::Local<v8::Value> result = CompileRun(
1564 : "var subject = 'one_byte~only~string~'; "
1565 : "var replace = '\x80'; "
1566 : "subject.replace(/~/g, replace); ");
1567 5 : CHECK(result->IsString());
1568 : Handle<String> string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1569 5 : CHECK(string->IsTwoByteRepresentation());
1570 :
1571 5 : v8::Local<v8::String> expected = v8_str("one_byte\x80only\x80string\x80");
1572 10 : CHECK(expected->Equals(context.local(), result).FromJust());
1573 5 : }
1574 :
1575 :
1576 26644 : TEST(IsAscii) {
1577 5 : CHECK(String::IsAscii(static_cast<char*>(nullptr), 0));
1578 : CHECK(String::IsOneByte(static_cast<uc16*>(nullptr), 0));
1579 5 : }
1580 :
1581 :
1582 :
1583 : template<typename Op, bool return_first>
1584 : static uint16_t ConvertLatin1(uint16_t c) {
1585 : uint32_t result[Op::kMaxWidth];
1586 : int chars;
1587 : chars = Op::Convert(c, 0, result, nullptr);
1588 : if (chars == 0) return 0;
1589 : CHECK_LE(chars, static_cast<int>(sizeof(result)));
1590 : if (!return_first && chars > 1) {
1591 : return 0;
1592 : }
1593 : return result[0];
1594 : }
1595 :
1596 : #ifndef V8_INTL_SUPPORT
1597 : static void CheckCanonicalEquivalence(uint16_t c, uint16_t test) {
1598 : uint16_t expect = ConvertLatin1<unibrow::Ecma262UnCanonicalize, true>(c);
1599 : if (expect > unibrow::Latin1::kMaxChar || expect == 0) expect = c;
1600 : CHECK_EQ(expect, test);
1601 : }
1602 :
1603 :
1604 : TEST(Latin1IgnoreCase) {
1605 : for (uint16_t c = unibrow::Latin1::kMaxChar + 1; c != 0; c++) {
1606 : uint16_t lower = ConvertLatin1<unibrow::ToLowercase, false>(c);
1607 : uint16_t upper = ConvertLatin1<unibrow::ToUppercase, false>(c);
1608 : uint16_t test = unibrow::Latin1::TryConvertToLatin1(c);
1609 : // Filter out all character whose upper is not their lower or vice versa.
1610 : if (lower == 0 && upper == 0) {
1611 : CheckCanonicalEquivalence(c, test);
1612 : continue;
1613 : }
1614 : if (lower > unibrow::Latin1::kMaxChar &&
1615 : upper > unibrow::Latin1::kMaxChar) {
1616 : CheckCanonicalEquivalence(c, test);
1617 : continue;
1618 : }
1619 : if (lower == 0 && upper != 0) {
1620 : lower = ConvertLatin1<unibrow::ToLowercase, false>(upper);
1621 : }
1622 : if (upper == 0 && lower != c) {
1623 : upper = ConvertLatin1<unibrow::ToUppercase, false>(lower);
1624 : }
1625 : if (lower > unibrow::Latin1::kMaxChar &&
1626 : upper > unibrow::Latin1::kMaxChar) {
1627 : CheckCanonicalEquivalence(c, test);
1628 : continue;
1629 : }
1630 : if (upper != c && lower != c) {
1631 : CheckCanonicalEquivalence(c, test);
1632 : continue;
1633 : }
1634 : CHECK_EQ(Min(upper, lower), test);
1635 : }
1636 : }
1637 : #endif
1638 :
1639 10 : class DummyResource: public v8::String::ExternalStringResource {
1640 : public:
1641 0 : const uint16_t* data() const override { return nullptr; }
1642 5 : size_t length() const override { return 1 << 30; }
1643 : };
1644 :
1645 :
1646 10 : class DummyOneByteResource: public v8::String::ExternalOneByteStringResource {
1647 : public:
1648 0 : const char* data() const override { return nullptr; }
1649 5 : size_t length() const override { return 1 << 30; }
1650 : };
1651 :
1652 :
1653 26644 : TEST(InvalidExternalString) {
1654 5 : CcTest::InitializeVM();
1655 5 : LocalContext context;
1656 : Isolate* isolate = CcTest::i_isolate();
1657 : { HandleScope scope(isolate);
1658 5 : DummyOneByteResource r;
1659 10 : CHECK(isolate->factory()->NewExternalStringFromOneByte(&r).is_null());
1660 5 : CHECK(isolate->has_pending_exception());
1661 : isolate->clear_pending_exception();
1662 : }
1663 :
1664 : { HandleScope scope(isolate);
1665 5 : DummyResource r;
1666 10 : CHECK(isolate->factory()->NewExternalStringFromTwoByte(&r).is_null());
1667 5 : CHECK(isolate->has_pending_exception());
1668 : isolate->clear_pending_exception();
1669 : }
1670 5 : }
1671 :
1672 :
1673 : #define INVALID_STRING_TEST(FUN, TYPE) \
1674 : TEST(StringOOM##FUN) { \
1675 : CcTest::InitializeVM(); \
1676 : LocalContext context; \
1677 : Isolate* isolate = CcTest::i_isolate(); \
1678 : STATIC_ASSERT(String::kMaxLength < kMaxInt); \
1679 : static const int invalid = String::kMaxLength + 1; \
1680 : HandleScope scope(isolate); \
1681 : Vector<TYPE> dummy = Vector<TYPE>::New(invalid); \
1682 : memset(dummy.start(), 0x0, dummy.length() * sizeof(TYPE)); \
1683 : CHECK(isolate->factory()->FUN(Vector<const TYPE>::cast(dummy)).is_null()); \
1684 : memset(dummy.start(), 0x20, dummy.length() * sizeof(TYPE)); \
1685 : CHECK(isolate->has_pending_exception()); \
1686 : isolate->clear_pending_exception(); \
1687 : dummy.Dispose(); \
1688 : }
1689 :
1690 26664 : INVALID_STRING_TEST(NewStringFromUtf8, char)
1691 26664 : INVALID_STRING_TEST(NewStringFromOneByte, uint8_t)
1692 :
1693 : #undef INVALID_STRING_TEST
1694 :
1695 :
1696 26644 : TEST(FormatMessage) {
1697 5 : CcTest::InitializeVM();
1698 5 : LocalContext context;
1699 : Isolate* isolate = CcTest::i_isolate();
1700 : HandleScope scope(isolate);
1701 5 : Handle<String> arg0 = isolate->factory()->NewStringFromAsciiChecked("arg0");
1702 5 : Handle<String> arg1 = isolate->factory()->NewStringFromAsciiChecked("arg1");
1703 5 : Handle<String> arg2 = isolate->factory()->NewStringFromAsciiChecked("arg2");
1704 : Handle<String> result =
1705 10 : MessageFormatter::Format(isolate, MessageTemplate::kPropertyNotFunction,
1706 : arg0, arg1, arg2)
1707 5 : .ToHandleChecked();
1708 : Handle<String> expected = isolate->factory()->NewStringFromAsciiChecked(
1709 5 : "'arg0' returned for property 'arg1' of object 'arg2' is not a function");
1710 5 : CHECK(String::Equals(isolate, result, expected));
1711 5 : }
1712 :
1713 26644 : TEST(Regress609831) {
1714 5 : CcTest::InitializeVM();
1715 5 : LocalContext context;
1716 : Isolate* isolate = CcTest::i_isolate();
1717 : {
1718 : HandleScope scope(isolate);
1719 : v8::Local<v8::Value> result = CompileRun(
1720 : "String.fromCharCode(32, 32, 32, 32, 32, "
1721 : "32, 32, 32, 32, 32, 32, 32, 32, 32, 32, "
1722 : "32, 32, 32, 32, 32, 32, 32, 32, 32, 32)");
1723 5 : CHECK(v8::Utils::OpenHandle(*result)->IsSeqOneByteString());
1724 : }
1725 : {
1726 : HandleScope scope(isolate);
1727 : v8::Local<v8::Value> result = CompileRun(
1728 : "String.fromCharCode(432, 432, 432, 432, 432, "
1729 : "432, 432, 432, 432, 432, 432, 432, 432, 432, "
1730 : "432, 432, 432, 432, 432, 432, 432, 432, 432)");
1731 5 : CHECK(v8::Utils::OpenHandle(*result)->IsSeqTwoByteString());
1732 : }
1733 5 : }
1734 :
1735 26644 : TEST(ExternalStringIndexOf) {
1736 5 : CcTest::InitializeVM();
1737 5 : LocalContext context;
1738 10 : v8::HandleScope scope(CcTest::isolate());
1739 :
1740 : const char* raw_string = "abcdefghijklmnopqrstuvwxyz";
1741 : v8::Local<v8::String> string =
1742 5 : v8::String::NewExternalOneByte(CcTest::isolate(),
1743 10 : new StaticOneByteResource(raw_string))
1744 : .ToLocalChecked();
1745 5 : v8::Local<v8::Object> global = context->Global();
1746 15 : global->Set(context.local(), v8_str("external"), string).FromJust();
1747 :
1748 5 : char source[] = "external.indexOf('%')";
1749 265 : for (size_t i = 0; i < strlen(raw_string); i++) {
1750 130 : source[18] = raw_string[i];
1751 130 : int result_position = static_cast<int>(i);
1752 260 : CHECK_EQ(result_position,
1753 : CompileRun(source)->Int32Value(context.local()).FromJust());
1754 : }
1755 10 : CHECK_EQ(-1,
1756 : CompileRun("external.indexOf('abcdefghijklmnopqrstuvwxyz%%%%%%')")
1757 : ->Int32Value(context.local())
1758 : .FromJust());
1759 10 : CHECK_EQ(1, CompileRun("external.indexOf('', 1)")
1760 : ->Int32Value(context.local())
1761 : .FromJust());
1762 10 : CHECK_EQ(-1, CompileRun("external.indexOf('a', 1)")
1763 : ->Int32Value(context.local())
1764 : .FromJust());
1765 10 : CHECK_EQ(-1, CompileRun("external.indexOf('$')")
1766 : ->Int32Value(context.local())
1767 : .FromJust());
1768 5 : }
1769 :
1770 : #define GC_INSIDE_NEW_STRING_FROM_UTF8_SUB_STRING(NAME, STRING) \
1771 : TEST(GCInsideNewStringFromUtf8SubStringWith##NAME) { \
1772 : CcTest::InitializeVM(); \
1773 : LocalContext context; \
1774 : v8::HandleScope scope(CcTest::isolate()); \
1775 : Factory* factory = CcTest::i_isolate()->factory(); \
1776 : /* Length must be bigger than the buffer size of the Utf8Decoder. */ \
1777 : const char* buf = STRING; \
1778 : size_t len = strlen(buf); \
1779 : Handle<String> main_string = \
1780 : factory \
1781 : ->NewStringFromOneByte(Vector<const uint8_t>( \
1782 : reinterpret_cast<const uint8_t*>(buf), len)) \
1783 : .ToHandleChecked(); \
1784 : CHECK(Heap::InYoungGeneration(*main_string)); \
1785 : /* Next allocation will cause GC. */ \
1786 : heap::SimulateFullSpace(CcTest::i_isolate()->heap()->new_space()); \
1787 : /* Offset by two to check substring-ing. */ \
1788 : Handle<String> s = factory \
1789 : ->NewStringFromUtf8SubString( \
1790 : Handle<SeqOneByteString>::cast(main_string), 2, \
1791 : static_cast<int>(len - 2)) \
1792 : .ToHandleChecked(); \
1793 : Handle<String> expected_string = \
1794 : factory->NewStringFromUtf8(Vector<const char>(buf + 2, len - 2)) \
1795 : .ToHandleChecked(); \
1796 : CHECK(s->Equals(*expected_string)); \
1797 : }
1798 :
1799 26689 : GC_INSIDE_NEW_STRING_FROM_UTF8_SUB_STRING(
1800 : OneByte,
1801 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1802 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1803 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1804 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1805 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1806 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1807 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1808 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1809 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ")
1810 26689 : GC_INSIDE_NEW_STRING_FROM_UTF8_SUB_STRING(
1811 : TwoByte,
1812 : "QQ\xF0\x9F\x98\x8D\xF0\x9F\x98\x8D"
1813 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1814 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1815 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1816 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1817 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1818 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1819 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1820 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1821 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1822 : "QQ\xF0\x9F\x98\x8D\xF0\x9F\x98\x8D")
1823 :
1824 : #undef GC_INSIDE_NEW_STRING_FROM_UTF8_SUB_STRING
1825 :
1826 26644 : TEST(HashArrayIndexStrings) {
1827 5 : CcTest::InitializeVM();
1828 5 : LocalContext context;
1829 10 : v8::HandleScope scope(CcTest::isolate());
1830 : i::Isolate* isolate = CcTest::i_isolate();
1831 :
1832 5 : CHECK_EQ(StringHasher::MakeArrayIndexHash(0 /* value */, 1 /* length */) >>
1833 : Name::kHashShift,
1834 : isolate->factory()->zero_string()->Hash());
1835 :
1836 5 : CHECK_EQ(StringHasher::MakeArrayIndexHash(1 /* value */, 1 /* length */) >>
1837 : Name::kHashShift,
1838 : isolate->factory()->one_string()->Hash());
1839 5 : }
1840 :
1841 26644 : TEST(StringEquals) {
1842 5 : v8::V8::Initialize();
1843 5 : v8::Isolate* isolate = CcTest::isolate();
1844 10 : v8::HandleScope scope(isolate);
1845 :
1846 : auto foo_str =
1847 5 : v8::String::NewFromUtf8(isolate, "foo", v8::NewStringType::kNormal)
1848 : .ToLocalChecked();
1849 : auto bar_str =
1850 5 : v8::String::NewFromUtf8(isolate, "bar", v8::NewStringType::kNormal)
1851 : .ToLocalChecked();
1852 : auto foo_str2 =
1853 5 : v8::String::NewFromUtf8(isolate, "foo", v8::NewStringType::kNormal)
1854 5 : .ToLocalChecked();
1855 :
1856 5 : uint16_t* two_byte_source = AsciiToTwoByteString("foo");
1857 : auto foo_two_byte_str =
1858 5 : v8::String::NewFromTwoByte(isolate, two_byte_source,
1859 : v8::NewStringType::kNormal)
1860 5 : .ToLocalChecked();
1861 : i::DeleteArray(two_byte_source);
1862 :
1863 5 : CHECK(foo_str->StringEquals(foo_str));
1864 5 : CHECK(!foo_str->StringEquals(bar_str));
1865 5 : CHECK(foo_str->StringEquals(foo_str2));
1866 5 : CHECK(foo_str->StringEquals(foo_two_byte_str));
1867 5 : CHECK(!bar_str->StringEquals(foo_str2));
1868 5 : }
1869 :
1870 : class OneByteStringResource : public v8::String::ExternalOneByteStringResource {
1871 : public:
1872 : // Takes ownership of |data|.
1873 : OneByteStringResource(char* data, size_t length)
1874 5 : : data_(data), length_(length) {}
1875 10 : ~OneByteStringResource() override { delete[] data_; }
1876 5 : const char* data() const override { return data_; }
1877 5 : size_t length() const override { return length_; }
1878 :
1879 : private:
1880 : char* data_;
1881 : size_t length_;
1882 : };
1883 :
1884 26644 : TEST(Regress876759) {
1885 5 : v8::V8::Initialize();
1886 : Isolate* isolate = CcTest::i_isolate();
1887 : Factory* factory = isolate->factory();
1888 :
1889 : HandleScope handle_scope(isolate);
1890 :
1891 : const int kLength = 30;
1892 : uc16 two_byte_buf[kLength];
1893 5 : char* external_one_byte_buf = new char[kLength];
1894 305 : for (int j = 0; j < kLength; j++) {
1895 150 : char c = '0' + (j % 10);
1896 150 : two_byte_buf[j] = c;
1897 150 : external_one_byte_buf[j] = c;
1898 : }
1899 :
1900 : Handle<String> parent;
1901 : {
1902 : Handle<SeqTwoByteString> raw =
1903 10 : factory->NewRawTwoByteString(kLength).ToHandleChecked();
1904 : DisallowHeapAllocation no_gc;
1905 : CopyChars(raw->GetChars(no_gc), two_byte_buf, kLength);
1906 : parent = raw;
1907 : }
1908 5 : CHECK(parent->IsTwoByteRepresentation());
1909 : Handle<String> sliced = factory->NewSubString(parent, 1, 20);
1910 5 : CHECK(sliced->IsSlicedString());
1911 5 : factory->InternalizeString(parent);
1912 5 : CHECK(parent->IsThinString());
1913 : Handle<String> grandparent =
1914 : handle(ThinString::cast(*parent)->actual(), isolate);
1915 5 : CHECK_EQ(*parent, SlicedString::cast(*sliced)->parent());
1916 : OneByteStringResource* resource =
1917 5 : new OneByteStringResource(external_one_byte_buf, kLength);
1918 5 : grandparent->MakeExternal(resource);
1919 : // The grandparent string becomes one-byte, but the child strings are still
1920 : // two-byte.
1921 5 : CHECK(grandparent->IsOneByteRepresentation());
1922 5 : CHECK(parent->IsTwoByteRepresentation());
1923 5 : CHECK(sliced->IsTwoByteRepresentation());
1924 : // The *Underneath version returns the correct representation.
1925 5 : CHECK(String::IsOneByteRepresentationUnderneath(*sliced));
1926 5 : }
1927 :
1928 : } // namespace test_strings
1929 : } // namespace internal
1930 79917 : } // namespace v8
|
