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