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 14264105 : for (unsigned j = 3; j < kQSize; j++) {
62 14264105 : Q[j] = Q[j - 3] ^ Q[j - 2] ^ phi ^ j;
63 : }
64 : }
65 :
66 290349515 : 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 246365 : 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 2347200 : 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 3855 : 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 15360 : 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 7725 : 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 76845 : for (int j = 0; j < len; j++) {
170 76845 : buf[j] = rng->next(0x10000);
171 : }
172 : building_blocks[i] = factory->NewStringFromTwoByte(
173 2625 : Vector<const uc16>(buf, len)).ToHandleChecked();
174 77720 : for (int j = 0; j < len; j++) {
175 153690 : CHECK_EQ(buf[j], building_blocks[i]->Get(j));
176 : }
177 : break;
178 : }
179 : case 1: {
180 : char buf[2000];
181 49730 : for (int j = 0; j < len; j++) {
182 49730 : buf[j] = rng->next(0x80);
183 : }
184 : building_blocks[i] =
185 : factory->NewStringFromOneByte(OneByteVector(buf, len))
186 3135 : .ToHandleChecked();
187 50775 : for (int j = 0; j < len; j++) {
188 149190 : CHECK_EQ(buf[j], building_blocks[i]->Get(j));
189 : }
190 : break;
191 : }
192 : case 2: {
193 870 : uc16* buf = NewArray<uc16>(len);
194 49205 : 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 2610 : .ToLocalChecked());
201 49205 : for (int j = 0; j < len; j++) {
202 96670 : CHECK_EQ(buf[j], building_blocks[i]->Get(j));
203 : }
204 : break;
205 : }
206 : case 3: {
207 1050 : char* buf = NewArray<char>(len);
208 57055 : 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 3150 : .ToLocalChecked());
215 57055 : for (int j = 0; j < len; j++) {
216 168015 : CHECK_EQ(buf[j], building_blocks[i]->Get(j));
217 : }
218 : break;
219 : }
220 : }
221 7715 : 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 : 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 1068140 : Handle<String> ConsStringGenerationData::block(int offset) {
307 1068140 : CHECK_GE(offset, 0);
308 1068140 : 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 5557080 : int left_length = cons_string->first()->length();
325 5557080 : 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 2878020 : 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 2668740 : 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 6880 : 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 897990 : 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 891790 : 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 961610 : 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 5550120 : 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 200040 : 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 451400 : for (int i = 0; i < depth; i++) {
463 451370 : 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 451370 : 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 140 : data->stats_.chars_ += data->block(from)->length();
502 70 : return data->block(from);
503 : }
504 82610 : if (to - from == 2) {
505 82560 : data->stats_.chars_ += data->block(from)->length();
506 82560 : data->stats_.chars_ += data->block(from+1)->length();
507 41280 : return factory->NewConsString(data->block(from), data->block(from+1))
508 82560 : .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 20 : 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 30 : StringCharacterStream character_stream_1(*s1);
532 30 : StringCharacterStream character_stream_2(*s2);
533 24531900 : 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 2510 : StringCharacterStream character_stream_1(*s1);
549 2510 : StringCharacterStream character_stream_2(*s2);
550 250337950 : 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 7530 : s1->Get(s1->length() - 1);
557 7530 : s2->Get(s2->length() - 1);
558 2510 : }
559 :
560 :
561 25880 : TEST(Traverse) {
562 : printf("TestTraverse\n");
563 5 : CcTest::InitializeVM();
564 : Isolate* isolate = CcTest::i_isolate();
565 5 : 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 5 : printf("18\n");
602 5 : }
603 :
604 25880 : TEST(ConsStringWithEmptyFirstFlatten) {
605 : printf("ConsStringWithEmptyFirstFlatten\n");
606 5 : CcTest::InitializeVM();
607 5 : v8::HandleScope scope(CcTest::isolate());
608 : Isolate* isolate = CcTest::i_isolate();
609 :
610 : i::Handle<i::String> initial_fst =
611 5 : isolate->factory()->NewStringFromAsciiChecked("fst012345");
612 : i::Handle<i::String> initial_snd =
613 5 : isolate->factory()->NewStringFromAsciiChecked("snd012345");
614 : i::Handle<i::String> str = isolate->factory()
615 : ->NewConsString(initial_fst, initial_snd)
616 10 : .ToHandleChecked();
617 10 : CHECK(str->IsConsString());
618 5 : auto cons = i::Handle<i::ConsString>::cast(str);
619 :
620 : const int initial_length = cons->length();
621 :
622 : // set_first / set_second does not update the length (which the heap verifier
623 : // checks), so we need to ensure the length stays the same.
624 :
625 : i::Handle<i::String> new_fst = isolate->factory()->empty_string();
626 : i::Handle<i::String> new_snd =
627 5 : isolate->factory()->NewStringFromAsciiChecked("snd012345012345678");
628 5 : cons->set_first(isolate, *new_fst);
629 5 : cons->set_second(isolate, *new_snd);
630 5 : CHECK(!cons->IsFlat());
631 5 : CHECK_EQ(initial_length, new_fst->length() + new_snd->length());
632 5 : CHECK_EQ(initial_length, cons->length());
633 :
634 : // Make sure Flatten doesn't alloc a new string.
635 : DisallowHeapAllocation no_alloc;
636 5 : i::Handle<i::String> flat = i::String::Flatten(isolate, cons);
637 5 : CHECK(flat->IsFlat());
638 5 : CHECK_EQ(initial_length, flat->length());
639 5 : }
640 :
641 1720 : static void VerifyCharacterStream(String flat_string, String cons_string) {
642 : // Do not want to test ConString traversal on flat string.
643 3440 : CHECK(flat_string->IsFlat() && !flat_string->IsConsString());
644 1720 : CHECK(cons_string->IsConsString());
645 : // TODO(dcarney) Test stream reset as well.
646 : int length = flat_string->length();
647 : // Iterate start search in multiple places in the string.
648 1720 : int outer_iterations = length > 20 ? 20 : length;
649 37840 : for (int j = 0; j <= outer_iterations; j++) {
650 36120 : int offset = length * j / outer_iterations;
651 36120 : if (offset < 0) offset = 0;
652 : // Want to test the offset == length case.
653 36120 : if (offset > length) offset = length;
654 36120 : StringCharacterStream flat_stream(flat_string, offset);
655 36120 : StringCharacterStream cons_stream(cons_string, offset);
656 215308875 : for (int i = offset; i < length; i++) {
657 : uint16_t c = flat_string->Get(i);
658 215272755 : CHECK(flat_stream.HasMore());
659 215272755 : CHECK(cons_stream.HasMore());
660 215272755 : CHECK_EQ(c, flat_stream.GetNext());
661 215272755 : CHECK_EQ(c, cons_stream.GetNext());
662 : }
663 36120 : CHECK(!flat_stream.HasMore());
664 36120 : CHECK(!cons_stream.HasMore());
665 : }
666 1720 : }
667 :
668 : static inline void PrintStats(const ConsStringGenerationData& data) {
669 : #ifdef DEBUG
670 : printf("%s: [%u], %s: [%u], %s: [%u], %s: [%u], %s: [%u], %s: [%u]\n",
671 : "leaves", data.stats_.leaves_, "empty", data.stats_.empty_leaves_,
672 : "chars", data.stats_.chars_, "lefts", data.stats_.left_traversals_,
673 : "rights", data.stats_.right_traversals_, "early_terminations",
674 : data.early_terminations_);
675 : #endif
676 : }
677 :
678 :
679 : template<typename BuildString>
680 10 : void TestStringCharacterStream(BuildString build, int test_cases) {
681 10 : FLAG_gc_global = true;
682 10 : CcTest::InitializeVM();
683 : Isolate* isolate = CcTest::i_isolate();
684 : HandleScope outer_scope(isolate);
685 10 : ConsStringGenerationData data(true);
686 1730 : for (int i = 0; i < test_cases; i++) {
687 : printf("%d\n", i);
688 : HandleScope inner_scope(isolate);
689 : AlwaysAllocateScope always_allocate(isolate);
690 : // Build flat version of cons string.
691 1720 : Handle<String> flat_string = build(i, &data);
692 : ConsStringStats flat_string_stats;
693 1720 : AccumulateStats(flat_string, &flat_string_stats);
694 : // Flatten string.
695 1720 : String::Flatten(isolate, flat_string);
696 : // Build unflattened version of cons string to test.
697 1720 : Handle<String> cons_string = build(i, &data);
698 : ConsStringStats cons_string_stats;
699 1720 : AccumulateStats(cons_string, &cons_string_stats);
700 : DisallowHeapAllocation no_allocation;
701 : PrintStats(data);
702 : // Full verify of cons string.
703 1720 : cons_string_stats.VerifyEqual(flat_string_stats);
704 1720 : cons_string_stats.VerifyEqual(data.stats_);
705 1720 : VerifyConsString(cons_string, &data);
706 3440 : String flat_string_ptr = flat_string->IsConsString()
707 3440 : ? ConsString::cast(*flat_string)->first()
708 3440 : : *flat_string;
709 1720 : VerifyCharacterStream(flat_string_ptr, *cons_string);
710 : }
711 10 : }
712 :
713 :
714 : static const int kCharacterStreamNonRandomCases = 8;
715 :
716 80 : static Handle<String> BuildEdgeCaseConsString(int test_case,
717 : ConsStringGenerationData* data) {
718 : Isolate* isolate = CcTest::i_isolate();
719 : Factory* factory = isolate->factory();
720 80 : data->Reset();
721 80 : switch (test_case) {
722 : case 0:
723 10 : return ConstructBalanced(data, 71);
724 : case 1:
725 10 : return ConstructLeft(data, 71);
726 : case 2:
727 10 : return ConstructRight(data, 71);
728 : case 3:
729 10 : return ConstructLeft(data, 10);
730 : case 4:
731 10 : return ConstructRight(data, 10);
732 : case 5:
733 : // 2 element balanced tree.
734 20 : data->stats_.chars_ += data->block(0)->length();
735 20 : data->stats_.chars_ += data->block(1)->length();
736 10 : data->stats_.leaves_ += 2;
737 10 : return factory->NewConsString(data->block(0), data->block(1))
738 20 : .ToHandleChecked();
739 : case 6:
740 : // Simple flattened tree.
741 20 : data->stats_.chars_ += data->block(0)->length();
742 20 : data->stats_.chars_ += data->block(1)->length();
743 10 : data->stats_.leaves_ += 2;
744 10 : data->stats_.empty_leaves_ += 1;
745 : {
746 : Handle<String> string =
747 10 : factory->NewConsString(data->block(0), data->block(1))
748 20 : .ToHandleChecked();
749 10 : String::Flatten(isolate, string);
750 10 : return string;
751 : }
752 : case 7:
753 : // Left node flattened.
754 20 : data->stats_.chars_ += data->block(0)->length();
755 20 : data->stats_.chars_ += data->block(1)->length();
756 20 : data->stats_.chars_ += data->block(2)->length();
757 10 : data->stats_.leaves_ += 3;
758 10 : data->stats_.empty_leaves_ += 1;
759 10 : data->stats_.left_traversals_ += 1;
760 : {
761 : Handle<String> left =
762 10 : factory->NewConsString(data->block(0), data->block(1))
763 20 : .ToHandleChecked();
764 10 : String::Flatten(isolate, left);
765 20 : return factory->NewConsString(left, data->block(2)).ToHandleChecked();
766 : }
767 : case 8:
768 : // Left node and right node flattened.
769 0 : data->stats_.chars_ += data->block(0)->length();
770 0 : data->stats_.chars_ += data->block(1)->length();
771 0 : data->stats_.chars_ += data->block(2)->length();
772 0 : data->stats_.chars_ += data->block(3)->length();
773 0 : data->stats_.leaves_ += 4;
774 0 : data->stats_.empty_leaves_ += 2;
775 0 : data->stats_.left_traversals_ += 1;
776 0 : data->stats_.right_traversals_ += 1;
777 : {
778 : Handle<String> left =
779 0 : factory->NewConsString(data->block(0), data->block(1))
780 0 : .ToHandleChecked();
781 0 : String::Flatten(isolate, left);
782 : Handle<String> right =
783 0 : factory->NewConsString(data->block(2), data->block(2))
784 0 : .ToHandleChecked();
785 0 : String::Flatten(isolate, right);
786 0 : return factory->NewConsString(left, right).ToHandleChecked();
787 : }
788 : }
789 0 : UNREACHABLE();
790 : }
791 :
792 :
793 25880 : TEST(StringCharacterStreamEdgeCases) {
794 : printf("TestStringCharacterStreamEdgeCases\n");
795 : TestStringCharacterStream(
796 5 : BuildEdgeCaseConsString, kCharacterStreamNonRandomCases);
797 5 : }
798 :
799 :
800 : static const int kBalances = 3;
801 : static const int kTreeLengths = 4;
802 : static const int kEmptyLeaves = 4;
803 : static const int kUniqueRandomParameters =
804 : kBalances*kTreeLengths*kEmptyLeaves;
805 :
806 :
807 3360 : static void InitializeGenerationData(
808 : int test_case, ConsStringGenerationData* data) {
809 : // Clear the settings and reinit the rng.
810 3360 : data->Reset();
811 : // Spin up the rng to a known location that is unique per test.
812 : static const int kPerTestJump = 501;
813 281966160 : for (int j = 0; j < test_case*kPerTestJump; j++) {
814 281962800 : data->rng_.next();
815 : }
816 : // Choose balanced, left or right heavy trees.
817 3360 : switch (test_case % kBalances) {
818 : case 0:
819 : // Nothing to do. Already balanced.
820 : break;
821 : case 1:
822 : // Left balanced.
823 1120 : data->leftness_ = 0.90;
824 1120 : data->rightness_ = 0.15;
825 1120 : break;
826 : case 2:
827 : // Right balanced.
828 1120 : data->leftness_ = 0.15;
829 1120 : data->rightness_ = 0.90;
830 1120 : break;
831 : default:
832 0 : UNREACHABLE();
833 : break;
834 : }
835 : // Must remove the influence of the above decision.
836 3360 : test_case /= kBalances;
837 : // Choose tree length.
838 3360 : switch (test_case % kTreeLengths) {
839 : case 0:
840 840 : data->max_leaves_ = 16;
841 840 : data->early_termination_threshold_ = 0.2;
842 840 : break;
843 : case 1:
844 840 : data->max_leaves_ = 50;
845 840 : data->early_termination_threshold_ = 0.05;
846 840 : break;
847 : case 2:
848 840 : data->max_leaves_ = 500;
849 840 : data->early_termination_threshold_ = 0.03;
850 840 : break;
851 : case 3:
852 840 : data->max_leaves_ = 5000;
853 840 : data->early_termination_threshold_ = 0.001;
854 840 : break;
855 : default:
856 0 : UNREACHABLE();
857 : break;
858 : }
859 : // Must remove the influence of the above decision.
860 3360 : test_case /= kTreeLengths;
861 : // Choose how much we allow empty nodes, including not at all.
862 : data->empty_leaf_threshold_ =
863 3360 : 0.03 * static_cast<double>(test_case % kEmptyLeaves);
864 3360 : }
865 :
866 :
867 3360 : static Handle<String> BuildRandomConsString(
868 : int test_case, ConsStringGenerationData* data) {
869 3360 : InitializeGenerationData(test_case, data);
870 3360 : return ConstructRandomString(data, 200);
871 : }
872 :
873 :
874 25880 : TEST(StringCharacterStreamRandom) {
875 : printf("StringCharacterStreamRandom\n");
876 5 : TestStringCharacterStream(BuildRandomConsString, kUniqueRandomParameters*7);
877 5 : }
878 :
879 :
880 : static const int kDeepOneByteDepth = 100000;
881 :
882 :
883 25880 : TEST(DeepOneByte) {
884 5 : CcTest::InitializeVM();
885 : Isolate* isolate = CcTest::i_isolate();
886 : Factory* factory = isolate->factory();
887 5 : v8::HandleScope scope(CcTest::isolate());
888 :
889 5 : char* foo = NewArray<char>(kDeepOneByteDepth);
890 500005 : for (int i = 0; i < kDeepOneByteDepth; i++) {
891 500000 : foo[i] = "foo "[i % 4];
892 : }
893 : Handle<String> string =
894 : factory->NewStringFromOneByte(OneByteVector(foo, kDeepOneByteDepth))
895 10 : .ToHandleChecked();
896 5 : Handle<String> foo_string = factory->NewStringFromStaticChars("foo");
897 50005 : for (int i = 0; i < kDeepOneByteDepth; i += 10) {
898 100000 : string = factory->NewConsString(string, foo_string).ToHandleChecked();
899 : }
900 : Handle<String> flat_string =
901 10 : factory->NewConsString(string, foo_string).ToHandleChecked();
902 5 : String::Flatten(isolate, flat_string);
903 :
904 2505 : for (int i = 0; i < 500; i++) {
905 2500 : TraverseFirst(flat_string, string, kDeepOneByteDepth);
906 : }
907 5 : DeleteArray<char>(foo);
908 5 : }
909 :
910 :
911 25880 : TEST(Utf8Conversion) {
912 : // Smoke test for converting strings to utf-8.
913 5 : CcTest::InitializeVM();
914 5 : v8::HandleScope handle_scope(CcTest::isolate());
915 : // A simple one-byte string
916 : const char* one_byte_string = "abcdef12345";
917 : int len = v8::String::NewFromUtf8(CcTest::isolate(), one_byte_string,
918 : v8::NewStringType::kNormal,
919 5 : StrLength(one_byte_string))
920 5 : .ToLocalChecked()
921 10 : ->Utf8Length(CcTest::isolate());
922 5 : CHECK_EQ(StrLength(one_byte_string), len);
923 : // A mixed one-byte and two-byte string
924 : // U+02E4 -> CB A4
925 : // U+0064 -> 64
926 : // U+12E4 -> E1 8B A4
927 : // U+0030 -> 30
928 : // U+3045 -> E3 81 85
929 5 : const uint16_t mixed_string[] = {0x02E4, 0x0064, 0x12E4, 0x0030, 0x3045};
930 : // The characters we expect to be output
931 : const unsigned char as_utf8[11] = {0xCB, 0xA4, 0x64, 0xE1, 0x8B, 0xA4, 0x30,
932 5 : 0xE3, 0x81, 0x85, 0x00};
933 : // The number of bytes expected to be written for each length
934 5 : const int lengths[12] = {0, 0, 2, 3, 3, 3, 6, 7, 7, 7, 10, 11};
935 5 : const int char_lengths[12] = {0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5};
936 : v8::Local<v8::String> mixed =
937 : v8::String::NewFromTwoByte(CcTest::isolate(), mixed_string,
938 5 : v8::NewStringType::kNormal, 5)
939 5 : .ToLocalChecked();
940 5 : CHECK_EQ(10, mixed->Utf8Length(CcTest::isolate()));
941 : // Try encoding the string with all capacities
942 : char buffer[11];
943 : const char kNoChar = static_cast<char>(-1);
944 60 : for (int i = 0; i <= 11; i++) {
945 : // Clear the buffer before reusing it
946 660 : for (int j = 0; j < 11; j++)
947 660 : buffer[j] = kNoChar;
948 : int chars_written;
949 : int written =
950 60 : mixed->WriteUtf8(CcTest::isolate(), buffer, i, &chars_written);
951 60 : CHECK_EQ(lengths[i], written);
952 60 : CHECK_EQ(char_lengths[i], chars_written);
953 : // Check that the contents are correct
954 295 : for (int j = 0; j < lengths[i]; j++)
955 295 : CHECK_EQ(as_utf8[j], static_cast<unsigned char>(buffer[j]));
956 : // Check that the rest of the buffer hasn't been touched
957 365 : for (int j = lengths[i]; j < 11; j++)
958 365 : CHECK_EQ(kNoChar, buffer[j]);
959 5 : }
960 5 : }
961 :
962 25880 : TEST(Utf8ConversionPerf) {
963 : // Smoke test for converting strings to utf-8.
964 5 : LocalContext context;
965 10 : v8::HandleScope handle_scope(CcTest::isolate());
966 : v8::Local<v8::String> ascii_string =
967 : CompileRun("'abc'.repeat(1E6)").As<v8::String>();
968 : v8::Local<v8::String> one_byte_string =
969 : CompileRun("'\\u0255\\u0254\\u0253'.repeat(1E6)").As<v8::String>();
970 : v8::Local<v8::String> two_byte_string =
971 : CompileRun("'\\u2255\\u2254\\u2253'.repeat(1E6)").As<v8::String>();
972 : v8::Local<v8::String> surrogate_string =
973 : CompileRun("'\\u{12345}\\u2244'.repeat(1E6)").As<v8::String>();
974 : int size = 1E7;
975 5 : char* buffer = new char[4 * size];
976 : {
977 : v8::base::ElapsedTimer timer;
978 : timer.Start();
979 5 : ascii_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
980 10 : printf("ascii string %0.3f\n", timer.Elapsed().InMillisecondsF());
981 : timer.Stop();
982 : }
983 : {
984 : v8::base::ElapsedTimer timer;
985 : timer.Start();
986 5 : ascii_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
987 10 : printf("ascii string %0.3f\n", timer.Elapsed().InMillisecondsF());
988 : timer.Stop();
989 : }
990 : {
991 : v8::base::ElapsedTimer timer;
992 : timer.Start();
993 5 : ascii_string->WriteUtf8(CcTest::isolate(), buffer, 4 * size, nullptr);
994 10 : printf("ascii string %0.3f\n", timer.Elapsed().InMillisecondsF());
995 : timer.Stop();
996 : }
997 :
998 : {
999 : v8::base::ElapsedTimer timer;
1000 : timer.Start();
1001 5 : one_byte_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
1002 10 : printf("one byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
1003 : timer.Stop();
1004 : }
1005 : {
1006 : v8::base::ElapsedTimer timer;
1007 : timer.Start();
1008 5 : one_byte_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
1009 10 : printf("one byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
1010 : timer.Stop();
1011 : }
1012 : {
1013 : v8::base::ElapsedTimer timer;
1014 : timer.Start();
1015 5 : one_byte_string->WriteUtf8(CcTest::isolate(), buffer, 4 * size, nullptr);
1016 10 : printf("one byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
1017 : timer.Stop();
1018 : }
1019 :
1020 : {
1021 : v8::base::ElapsedTimer timer;
1022 : timer.Start();
1023 5 : two_byte_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
1024 10 : printf("two byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
1025 : timer.Stop();
1026 : }
1027 : {
1028 : v8::base::ElapsedTimer timer;
1029 : timer.Start();
1030 5 : two_byte_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
1031 10 : printf("two byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
1032 : timer.Stop();
1033 : }
1034 : {
1035 : v8::base::ElapsedTimer timer;
1036 : timer.Start();
1037 5 : two_byte_string->WriteUtf8(CcTest::isolate(), buffer, 4 * size, nullptr);
1038 10 : printf("two byte string %0.3f\n", timer.Elapsed().InMillisecondsF());
1039 : timer.Stop();
1040 : }
1041 :
1042 : {
1043 : v8::base::ElapsedTimer timer;
1044 : timer.Start();
1045 5 : surrogate_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
1046 10 : printf("surrogate string %0.3f\n", timer.Elapsed().InMillisecondsF());
1047 : timer.Stop();
1048 : }
1049 : {
1050 : v8::base::ElapsedTimer timer;
1051 : timer.Start();
1052 5 : surrogate_string->WriteUtf8(CcTest::isolate(), buffer, size, nullptr);
1053 10 : printf("surrogate string %0.3f\n", timer.Elapsed().InMillisecondsF());
1054 : timer.Stop();
1055 : }
1056 : {
1057 : v8::base::ElapsedTimer timer;
1058 : timer.Start();
1059 5 : surrogate_string->WriteUtf8(CcTest::isolate(), buffer, 4 * size, nullptr);
1060 10 : printf("surrogate string %0.3f\n", timer.Elapsed().InMillisecondsF());
1061 : timer.Stop();
1062 : }
1063 10 : delete[] buffer;
1064 5 : }
1065 :
1066 25880 : TEST(ExternalShortStringAdd) {
1067 5 : LocalContext context;
1068 10 : v8::HandleScope handle_scope(CcTest::isolate());
1069 :
1070 : // Make sure we cover all always-flat lengths and at least one above.
1071 : static const int kMaxLength = 20;
1072 : CHECK_GT(kMaxLength, i::ConsString::kMinLength);
1073 :
1074 : // Allocate two JavaScript arrays for holding short strings.
1075 : v8::Local<v8::Array> one_byte_external_strings =
1076 5 : v8::Array::New(CcTest::isolate(), kMaxLength + 1);
1077 : v8::Local<v8::Array> non_one_byte_external_strings =
1078 5 : v8::Array::New(CcTest::isolate(), kMaxLength + 1);
1079 :
1080 : // Generate short one-byte and two-byte external strings.
1081 115 : for (int i = 0; i <= kMaxLength; i++) {
1082 105 : char* one_byte = NewArray<char>(i + 1);
1083 1155 : for (int j = 0; j < i; j++) {
1084 1050 : one_byte[j] = 'a';
1085 : }
1086 : // Terminating '\0' is left out on purpose. It is not required for external
1087 : // string data.
1088 105 : OneByteResource* one_byte_resource = new OneByteResource(one_byte, i);
1089 : v8::Local<v8::String> one_byte_external_string =
1090 105 : v8::String::NewExternalOneByte(CcTest::isolate(), one_byte_resource)
1091 105 : .ToLocalChecked();
1092 :
1093 : one_byte_external_strings->Set(context.local(),
1094 : v8::Integer::New(CcTest::isolate(), i),
1095 315 : one_byte_external_string)
1096 210 : .FromJust();
1097 105 : uc16* non_one_byte = NewArray<uc16>(i + 1);
1098 1155 : for (int j = 0; j < i; j++) {
1099 1050 : non_one_byte[j] = 0x1234;
1100 : }
1101 : // Terminating '\0' is left out on purpose. It is not required for external
1102 : // string data.
1103 105 : Resource* resource = new Resource(non_one_byte, i);
1104 : v8::Local<v8::String> non_one_byte_external_string =
1105 105 : v8::String::NewExternalTwoByte(CcTest::isolate(), resource)
1106 105 : .ToLocalChecked();
1107 : non_one_byte_external_strings->Set(context.local(),
1108 : v8::Integer::New(CcTest::isolate(), i),
1109 315 : non_one_byte_external_string)
1110 210 : .FromJust();
1111 : }
1112 :
1113 : // Add the arrays with the short external strings in the global object.
1114 5 : v8::Local<v8::Object> global = context->Global();
1115 : global->Set(context.local(), v8_str("external_one_byte"),
1116 15 : one_byte_external_strings)
1117 10 : .FromJust();
1118 : global->Set(context.local(), v8_str("external_non_one_byte"),
1119 15 : non_one_byte_external_strings)
1120 10 : .FromJust();
1121 : global->Set(context.local(), v8_str("max_length"),
1122 20 : v8::Integer::New(CcTest::isolate(), kMaxLength))
1123 10 : .FromJust();
1124 :
1125 : // Add short external one-byte and two-byte strings checking the result.
1126 : static const char* source =
1127 : "function test() {"
1128 : " var one_byte_chars = 'aaaaaaaaaaaaaaaaaaaa';"
1129 : " var non_one_byte_chars = "
1130 : "'\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1"
1131 : "234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\"
1132 : "u1234';" // NOLINT
1133 : " if (one_byte_chars.length != max_length) return 1;"
1134 : " if (non_one_byte_chars.length != max_length) return 2;"
1135 : " var one_byte = Array(max_length + 1);"
1136 : " var non_one_byte = Array(max_length + 1);"
1137 : " for (var i = 0; i <= max_length; i++) {"
1138 : " one_byte[i] = one_byte_chars.substring(0, i);"
1139 : " non_one_byte[i] = non_one_byte_chars.substring(0, i);"
1140 : " };"
1141 : " for (var i = 0; i <= max_length; i++) {"
1142 : " if (one_byte[i] != external_one_byte[i]) return 3;"
1143 : " if (non_one_byte[i] != external_non_one_byte[i]) return 4;"
1144 : " for (var j = 0; j < i; j++) {"
1145 : " if (external_one_byte[i] !="
1146 : " (external_one_byte[j] + external_one_byte[i - j])) return "
1147 : "5;"
1148 : " if (external_non_one_byte[i] !="
1149 : " (external_non_one_byte[j] + external_non_one_byte[i - "
1150 : "j])) return 6;"
1151 : " if (non_one_byte[i] != (non_one_byte[j] + non_one_byte[i - "
1152 : "j])) return 7;"
1153 : " if (one_byte[i] != (one_byte[j] + one_byte[i - j])) return 8;"
1154 : " if (one_byte[i] != (external_one_byte[j] + one_byte[i - j])) "
1155 : "return 9;"
1156 : " if (one_byte[i] != (one_byte[j] + external_one_byte[i - j])) "
1157 : "return 10;"
1158 : " if (non_one_byte[i] !="
1159 : " (external_non_one_byte[j] + non_one_byte[i - j])) return "
1160 : "11;"
1161 : " if (non_one_byte[i] !="
1162 : " (non_one_byte[j] + external_non_one_byte[i - j])) return "
1163 : "12;"
1164 : " }"
1165 : " }"
1166 : " return 0;"
1167 : "};"
1168 : "test()";
1169 20 : CHECK_EQ(0, CompileRun(source)->Int32Value(context.local()).FromJust());
1170 5 : }
1171 :
1172 25880 : TEST(ReplaceInvalidUtf8) {
1173 5 : LocalContext context;
1174 10 : v8::HandleScope handle_scope(CcTest::isolate());
1175 : v8::Local<v8::String> string = CompileRun("'ab\\ud800cd'").As<v8::String>();
1176 : char buffer[7];
1177 : memset(buffer, 0, 7);
1178 5 : int chars_written = 0;
1179 : int size = string->WriteUtf8(CcTest::isolate(), buffer, 7, &chars_written,
1180 5 : v8::String::REPLACE_INVALID_UTF8);
1181 5 : CHECK_EQ(7, size);
1182 5 : CHECK_EQ(5, chars_written);
1183 5 : CHECK_EQ(0, memcmp("\x61\x62\xef\xbf\xbd\x63\x64", buffer, 7));
1184 :
1185 : memset(buffer, 0, 7);
1186 5 : chars_written = 0;
1187 : size = string->WriteUtf8(CcTest::isolate(), buffer, 6, &chars_written,
1188 5 : v8::String::REPLACE_INVALID_UTF8);
1189 5 : CHECK_EQ(6, size);
1190 5 : CHECK_EQ(4, chars_written);
1191 10 : CHECK_EQ(0, memcmp("\x61\x62\xef\xbf\xbd\x63", buffer, 6));
1192 5 : }
1193 :
1194 25880 : TEST(JSONStringifySliceMadeExternal) {
1195 5 : if (!FLAG_string_slices) return;
1196 5 : CcTest::InitializeVM();
1197 : // Create a sliced string from a one-byte string. The latter is turned
1198 : // into a two-byte external string. Check that JSON.stringify works.
1199 5 : v8::HandleScope handle_scope(CcTest::isolate());
1200 : v8::Local<v8::String> underlying =
1201 : CompileRun(
1202 : "var underlying = 'abcdefghijklmnopqrstuvwxyz';"
1203 : "underlying")
1204 5 : ->ToString(CcTest::isolate()->GetCurrentContext())
1205 5 : .ToLocalChecked();
1206 : v8::Local<v8::String> slice =
1207 : CompileRun(
1208 : "var slice = '';"
1209 : "slice = underlying.slice(1);"
1210 : "slice")
1211 5 : ->ToString(CcTest::isolate()->GetCurrentContext())
1212 5 : .ToLocalChecked();
1213 10 : CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
1214 10 : CHECK(v8::Utils::OpenHandle(*underlying)->IsSeqOneByteString());
1215 :
1216 5 : int length = underlying->Length();
1217 5 : uc16* two_byte = NewArray<uc16>(length + 1);
1218 5 : underlying->Write(CcTest::isolate(), two_byte);
1219 5 : Resource* resource = new Resource(two_byte, length);
1220 5 : CHECK(underlying->MakeExternal(resource));
1221 10 : CHECK(v8::Utils::OpenHandle(*slice)->IsSlicedString());
1222 10 : CHECK(v8::Utils::OpenHandle(*underlying)->IsExternalTwoByteString());
1223 :
1224 5 : CHECK_EQ(0,
1225 : strcmp("\"bcdefghijklmnopqrstuvwxyz\"",
1226 : *v8::String::Utf8Value(CcTest::isolate(),
1227 5 : CompileRun("JSON.stringify(slice)"))));
1228 : }
1229 :
1230 25880 : TEST(JSONStringifyWellFormed) {
1231 5 : FLAG_harmony_json_stringify = true;
1232 5 : CcTest::InitializeVM();
1233 5 : v8::HandleScope handle_scope(CcTest::isolate());
1234 5 : v8::Local<v8::Context> context = CcTest::isolate()->GetCurrentContext();
1235 :
1236 : // Test some leading surrogates (U+D800 to U+DBFF).
1237 : { // U+D800
1238 5 : CHECK_EQ(
1239 : 0, strcmp("\"\\ud800\"", *v8::String::Utf8Value(
1240 : CcTest::isolate(),
1241 : CompileRun("JSON.stringify('\\uD800')"))));
1242 5 : v8::Local<v8::String> json = v8_str("\"\\ud800\"");
1243 : v8::Local<v8::Value> parsed =
1244 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1245 15 : CHECK(v8::JSON::Stringify(context, parsed)
1246 : .ToLocalChecked()
1247 : ->Equals(context, json)
1248 : .FromJust());
1249 : }
1250 :
1251 : { // U+DAAA
1252 5 : CHECK_EQ(
1253 : 0, strcmp("\"\\udaaa\"", *v8::String::Utf8Value(
1254 : CcTest::isolate(),
1255 : CompileRun("JSON.stringify('\\uDAAA')"))));
1256 5 : v8::Local<v8::String> json = v8_str("\"\\udaaa\"");
1257 : v8::Local<v8::Value> parsed =
1258 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1259 15 : CHECK(v8::JSON::Stringify(context, parsed)
1260 : .ToLocalChecked()
1261 : ->Equals(context, json)
1262 : .FromJust());
1263 : }
1264 :
1265 : { // U+DBFF
1266 5 : CHECK_EQ(
1267 : 0, strcmp("\"\\udbff\"", *v8::String::Utf8Value(
1268 : CcTest::isolate(),
1269 : CompileRun("JSON.stringify('\\uDBFF')"))));
1270 5 : v8::Local<v8::String> json = v8_str("\"\\udbff\"");
1271 : v8::Local<v8::Value> parsed =
1272 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1273 15 : CHECK(v8::JSON::Stringify(context, parsed)
1274 : .ToLocalChecked()
1275 : ->Equals(context, json)
1276 : .FromJust());
1277 : }
1278 :
1279 : // Test some trailing surrogates (U+DC00 to U+DFFF).
1280 : { // U+DC00
1281 5 : CHECK_EQ(
1282 : 0, strcmp("\"\\udc00\"", *v8::String::Utf8Value(
1283 : CcTest::isolate(),
1284 : CompileRun("JSON.stringify('\\uDC00')"))));
1285 5 : v8::Local<v8::String> json = v8_str("\"\\udc00\"");
1286 : v8::Local<v8::Value> parsed =
1287 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1288 15 : CHECK(v8::JSON::Stringify(context, parsed)
1289 : .ToLocalChecked()
1290 : ->Equals(context, json)
1291 : .FromJust());
1292 : }
1293 :
1294 : { // U+DDDD
1295 5 : CHECK_EQ(
1296 : 0, strcmp("\"\\udddd\"", *v8::String::Utf8Value(
1297 : CcTest::isolate(),
1298 : CompileRun("JSON.stringify('\\uDDDD')"))));
1299 5 : v8::Local<v8::String> json = v8_str("\"\\udddd\"");
1300 : v8::Local<v8::Value> parsed =
1301 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1302 15 : CHECK(v8::JSON::Stringify(context, parsed)
1303 : .ToLocalChecked()
1304 : ->Equals(context, json)
1305 : .FromJust());
1306 : }
1307 :
1308 : { // U+DFFF
1309 5 : CHECK_EQ(
1310 : 0, strcmp("\"\\udfff\"", *v8::String::Utf8Value(
1311 : CcTest::isolate(),
1312 : CompileRun("JSON.stringify('\\uDFFF')"))));
1313 5 : v8::Local<v8::String> json = v8_str("\"\\udfff\"");
1314 : v8::Local<v8::Value> parsed =
1315 10 : v8::JSON::Parse(context, json).ToLocalChecked();
1316 15 : CHECK(v8::JSON::Stringify(context, parsed)
1317 : .ToLocalChecked()
1318 : ->Equals(context, json)
1319 : .FromJust());
1320 5 : }
1321 5 : }
1322 :
1323 25880 : TEST(CachedHashOverflow) {
1324 5 : CcTest::InitializeVM();
1325 : // We incorrectly allowed strings to be tagged as array indices even if their
1326 : // values didn't fit in the hash field.
1327 : // See http://code.google.com/p/v8/issues/detail?id=728
1328 : Isolate* isolate = CcTest::i_isolate();
1329 :
1330 5 : v8::HandleScope handle_scope(CcTest::isolate());
1331 : // Lines must be executed sequentially. Combining them into one script
1332 : // makes the bug go away.
1333 : const char* lines[] = {"var x = [];", "x[4] = 42;", "var s = \"1073741828\";",
1334 : "x[s];", "x[s] = 37;", "x[4];",
1335 5 : "x[s];"};
1336 :
1337 : Handle<Smi> fortytwo(Smi::FromInt(42), isolate);
1338 : Handle<Smi> thirtyseven(Smi::FromInt(37), isolate);
1339 : Handle<Object> results[] = { isolate->factory()->undefined_value(),
1340 : fortytwo,
1341 : isolate->factory()->undefined_value(),
1342 : isolate->factory()->undefined_value(),
1343 : thirtyseven,
1344 : fortytwo,
1345 : thirtyseven // Bug yielded 42 here.
1346 : };
1347 :
1348 5 : v8::Local<v8::Context> context = CcTest::isolate()->GetCurrentContext();
1349 40 : for (size_t i = 0; i < arraysize(lines); i++) {
1350 35 : const char* line = lines[i];
1351 : printf("%s\n", line);
1352 : v8::Local<v8::Value> result =
1353 : v8::Script::Compile(context,
1354 : v8::String::NewFromUtf8(CcTest::isolate(), line,
1355 35 : v8::NewStringType::kNormal)
1356 35 : .ToLocalChecked())
1357 35 : .ToLocalChecked()
1358 : ->Run(context)
1359 35 : .ToLocalChecked();
1360 105 : CHECK_EQ(results[i]->IsUndefined(CcTest::i_isolate()),
1361 : result->IsUndefined());
1362 105 : CHECK_EQ(results[i]->IsNumber(), result->IsNumber());
1363 35 : if (result->IsNumber()) {
1364 20 : int32_t value = 0;
1365 20 : CHECK(results[i]->ToInt32(&value));
1366 40 : CHECK_EQ(value, result->ToInt32(context).ToLocalChecked()->Value());
1367 : }
1368 5 : }
1369 5 : }
1370 :
1371 :
1372 25880 : TEST(SliceFromCons) {
1373 5 : if (!FLAG_string_slices) return;
1374 5 : CcTest::InitializeVM();
1375 : Factory* factory = CcTest::i_isolate()->factory();
1376 5 : v8::HandleScope scope(CcTest::isolate());
1377 : Handle<String> string =
1378 5 : factory->NewStringFromStaticChars("parentparentparent");
1379 : Handle<String> parent =
1380 10 : factory->NewConsString(string, string).ToHandleChecked();
1381 10 : CHECK(parent->IsConsString());
1382 5 : CHECK(!parent->IsFlat());
1383 5 : Handle<String> slice = factory->NewSubString(parent, 1, 25);
1384 : // After slicing, the original string becomes a flat cons.
1385 5 : CHECK(parent->IsFlat());
1386 10 : CHECK(slice->IsSlicedString());
1387 25 : CHECK_EQ(SlicedString::cast(*slice)->parent(),
1388 : // Parent could have been short-circuited.
1389 : parent->IsConsString() ? ConsString::cast(*parent)->first()
1390 : : *parent);
1391 10 : CHECK(SlicedString::cast(*slice)->parent()->IsSeqString());
1392 5 : CHECK(slice->IsFlat());
1393 : }
1394 :
1395 :
1396 : class OneByteVectorResource : public v8::String::ExternalOneByteStringResource {
1397 : public:
1398 : explicit OneByteVectorResource(i::Vector<const char> vector)
1399 10 : : data_(vector) {}
1400 15 : ~OneByteVectorResource() override = default;
1401 60 : size_t length() const override { return data_.length(); }
1402 20 : const char* data() const override { return data_.start(); }
1403 : private:
1404 : i::Vector<const char> data_;
1405 : };
1406 :
1407 25880 : TEST(InternalizeExternal) {
1408 : #ifdef ENABLE_MINOR_MC
1409 : // TODO(mlippautz): Remove once we add support for forwarding ThinStrings in
1410 : // minor MC
1411 10 : if (FLAG_minor_mc) return;
1412 : #endif // ENABLE_MINOR_MC
1413 5 : FLAG_stress_incremental_marking = false;
1414 5 : FLAG_thin_strings = true;
1415 5 : CcTest::InitializeVM();
1416 : i::Isolate* isolate = CcTest::i_isolate();
1417 : Factory* factory = isolate->factory();
1418 : // This won't leak; the external string mechanism will call Dispose() on it.
1419 : OneByteVectorResource* resource =
1420 5 : new OneByteVectorResource(i::Vector<const char>("prop-1234", 9));
1421 : {
1422 5 : v8::HandleScope scope(CcTest::isolate());
1423 : v8::Local<v8::String> ext_string =
1424 5 : v8::String::NewExternalOneByte(CcTest::isolate(), resource)
1425 5 : .ToLocalChecked();
1426 : Handle<String> string = v8::Utils::OpenHandle(*ext_string);
1427 10 : CHECK(string->IsExternalString());
1428 10 : CHECK(!string->IsInternalizedString());
1429 5 : CHECK(!i::Heap::InYoungGeneration(*string));
1430 5 : CHECK_EQ(
1431 : isolate->factory()->string_table()->LookupStringIfExists_NoAllocate(
1432 : isolate, string->ptr()),
1433 : Smi::FromInt(ResultSentinel::kNotFound).ptr());
1434 5 : factory->InternalizeName(string);
1435 10 : CHECK(string->IsExternalString());
1436 10 : CHECK(string->IsInternalizedString());
1437 5 : CHECK(!i::Heap::InYoungGeneration(*string));
1438 : }
1439 5 : CcTest::CollectGarbage(i::OLD_SPACE);
1440 5 : CcTest::CollectGarbage(i::OLD_SPACE);
1441 : }
1442 :
1443 25880 : TEST(SliceFromExternal) {
1444 5 : if (!FLAG_string_slices) return;
1445 5 : CcTest::InitializeVM();
1446 : Factory* factory = CcTest::i_isolate()->factory();
1447 5 : v8::HandleScope scope(CcTest::isolate());
1448 : OneByteVectorResource resource(
1449 : i::Vector<const char>("abcdefghijklmnopqrstuvwxyz", 26));
1450 : Handle<String> string =
1451 10 : factory->NewExternalStringFromOneByte(&resource).ToHandleChecked();
1452 10 : CHECK(string->IsExternalString());
1453 5 : Handle<String> slice = factory->NewSubString(string, 1, 25);
1454 10 : CHECK(slice->IsSlicedString());
1455 10 : CHECK(string->IsExternalString());
1456 15 : CHECK_EQ(SlicedString::cast(*slice)->parent(), *string);
1457 10 : CHECK(SlicedString::cast(*slice)->parent()->IsExternalString());
1458 5 : CHECK(slice->IsFlat());
1459 : // This avoids the GC from trying to free stack allocated resources.
1460 10 : i::Handle<i::ExternalOneByteString>::cast(string)->SetResource(
1461 10 : CcTest::i_isolate(), nullptr);
1462 : }
1463 :
1464 :
1465 25880 : TEST(TrivialSlice) {
1466 : // This tests whether a slice that contains the entire parent string
1467 : // actually creates a new string (it should not).
1468 5 : if (!FLAG_string_slices) return;
1469 5 : CcTest::InitializeVM();
1470 : Factory* factory = CcTest::i_isolate()->factory();
1471 5 : v8::HandleScope scope(CcTest::isolate());
1472 : v8::Local<v8::Value> result;
1473 : Handle<String> string;
1474 : const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
1475 : const char* check = "str.slice(0,26)";
1476 : const char* crosscheck = "str.slice(1,25)";
1477 :
1478 : CompileRun(init);
1479 :
1480 : result = CompileRun(check);
1481 5 : CHECK(result->IsString());
1482 : string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1483 10 : CHECK(!string->IsSlicedString());
1484 :
1485 5 : string = factory->NewSubString(string, 0, 26);
1486 10 : CHECK(!string->IsSlicedString());
1487 : result = CompileRun(crosscheck);
1488 5 : CHECK(result->IsString());
1489 : string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1490 10 : CHECK(string->IsSlicedString());
1491 15 : CHECK_EQ(0, strcmp("bcdefghijklmnopqrstuvwxy", string->ToCString().get()));
1492 : }
1493 :
1494 :
1495 25880 : TEST(SliceFromSlice) {
1496 : // This tests whether a slice that contains the entire parent string
1497 : // actually creates a new string (it should not).
1498 5 : if (!FLAG_string_slices) return;
1499 5 : CcTest::InitializeVM();
1500 5 : v8::HandleScope scope(CcTest::isolate());
1501 : v8::Local<v8::Value> result;
1502 : Handle<String> string;
1503 : const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
1504 : const char* slice = "var slice = ''; slice = str.slice(1,-1); slice";
1505 : const char* slice_from_slice = "slice.slice(1,-1);";
1506 :
1507 : CompileRun(init);
1508 : result = CompileRun(slice);
1509 5 : CHECK(result->IsString());
1510 : string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1511 10 : CHECK(string->IsSlicedString());
1512 10 : CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
1513 15 : CHECK_EQ(0, strcmp("bcdefghijklmnopqrstuvwxy", string->ToCString().get()));
1514 :
1515 : result = CompileRun(slice_from_slice);
1516 5 : CHECK(result->IsString());
1517 : string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1518 10 : CHECK(string->IsSlicedString());
1519 10 : CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
1520 15 : CHECK_EQ(0, strcmp("cdefghijklmnopqrstuvwx", string->ToCString().get()));
1521 : }
1522 :
1523 :
1524 25880 : UNINITIALIZED_TEST(OneByteArrayJoin) {
1525 : v8::Isolate::CreateParams create_params;
1526 : // Set heap limits.
1527 : create_params.constraints.set_max_semi_space_size_in_kb(1024);
1528 : #ifdef DEBUG
1529 : create_params.constraints.set_max_old_space_size(20);
1530 : #else
1531 : create_params.constraints.set_max_old_space_size(7);
1532 : #endif
1533 5 : create_params.array_buffer_allocator = CcTest::array_buffer_allocator();
1534 5 : v8::Isolate* isolate = v8::Isolate::New(create_params);
1535 5 : isolate->Enter();
1536 :
1537 : {
1538 : // String s is made of 2^17 = 131072 'c' characters and a is an array
1539 : // starting with 'bad', followed by 2^14 times the string s. That means the
1540 : // total length of the concatenated strings is 2^31 + 3. So on 32bit systems
1541 : // summing the lengths of the strings (as Smis) overflows and wraps.
1542 : LocalContext context(isolate);
1543 10 : v8::HandleScope scope(isolate);
1544 10 : v8::TryCatch try_catch(isolate);
1545 5 : CHECK(CompileRun(
1546 : "var two_14 = Math.pow(2, 14);"
1547 : "var two_17 = Math.pow(2, 17);"
1548 : "var s = Array(two_17 + 1).join('c');"
1549 : "var a = ['bad'];"
1550 : "for (var i = 1; i <= two_14; i++) a.push(s);"
1551 : "a.join("
1552 : ");").IsEmpty());
1553 10 : CHECK(try_catch.HasCaught());
1554 : }
1555 5 : isolate->Exit();
1556 5 : isolate->Dispose();
1557 5 : }
1558 :
1559 : namespace {
1560 :
1561 : int* global_use_counts = nullptr;
1562 :
1563 23 : void MockUseCounterCallback(v8::Isolate* isolate,
1564 : v8::Isolate::UseCounterFeature feature) {
1565 23 : ++global_use_counts[feature];
1566 23 : }
1567 : }
1568 :
1569 :
1570 25880 : TEST(CountBreakIterator) {
1571 5 : CcTest::InitializeVM();
1572 5 : v8::HandleScope scope(CcTest::isolate());
1573 10 : LocalContext context;
1574 5 : int use_counts[v8::Isolate::kUseCounterFeatureCount] = {};
1575 5 : global_use_counts = use_counts;
1576 5 : CcTest::isolate()->SetUseCounterCallback(MockUseCounterCallback);
1577 5 : CHECK_EQ(0, use_counts[v8::Isolate::kBreakIterator]);
1578 : v8::Local<v8::Value> result = CompileRun(
1579 : "(function() {"
1580 : " if (!this.Intl) return 0;"
1581 : " var iterator = Intl.v8BreakIterator(['en']);"
1582 : " iterator.adoptText('Now is the time');"
1583 : " iterator.next();"
1584 : " return iterator.next();"
1585 : "})();");
1586 5 : CHECK(result->IsNumber());
1587 : int uses =
1588 10 : result->ToInt32(context.local()).ToLocalChecked()->Value() == 0 ? 0 : 1;
1589 5 : CHECK_EQ(uses, use_counts[v8::Isolate::kBreakIterator]);
1590 : // Make sure GC cleans up the break iterator, so we don't get a memory leak
1591 : // reported by ASAN.
1592 10 : CcTest::isolate()->LowMemoryNotification();
1593 5 : }
1594 :
1595 :
1596 25880 : TEST(StringReplaceAtomTwoByteResult) {
1597 5 : CcTest::InitializeVM();
1598 5 : v8::HandleScope scope(CcTest::isolate());
1599 10 : LocalContext context;
1600 : v8::Local<v8::Value> result = CompileRun(
1601 : "var subject = 'one_byte~only~string~'; "
1602 : "var replace = '\x80'; "
1603 : "subject.replace(/~/g, replace); ");
1604 5 : CHECK(result->IsString());
1605 : Handle<String> string = v8::Utils::OpenHandle(v8::String::Cast(*result));
1606 5 : CHECK(string->IsTwoByteRepresentation());
1607 :
1608 5 : v8::Local<v8::String> expected = v8_str("one_byte\x80only\x80string\x80");
1609 20 : CHECK(expected->Equals(context.local(), result).FromJust());
1610 5 : }
1611 :
1612 :
1613 25880 : TEST(IsAscii) {
1614 5 : CHECK(String::IsAscii(static_cast<char*>(nullptr), 0));
1615 : CHECK(String::IsOneByte(static_cast<uc16*>(nullptr), 0));
1616 5 : }
1617 :
1618 :
1619 :
1620 : template<typename Op, bool return_first>
1621 : static uint16_t ConvertLatin1(uint16_t c) {
1622 : uint32_t result[Op::kMaxWidth];
1623 : int chars;
1624 : chars = Op::Convert(c, 0, result, nullptr);
1625 : if (chars == 0) return 0;
1626 : CHECK_LE(chars, static_cast<int>(sizeof(result)));
1627 : if (!return_first && chars > 1) {
1628 : return 0;
1629 : }
1630 : return result[0];
1631 : }
1632 :
1633 : #ifndef V8_INTL_SUPPORT
1634 : static void CheckCanonicalEquivalence(uint16_t c, uint16_t test) {
1635 : uint16_t expect = ConvertLatin1<unibrow::Ecma262UnCanonicalize, true>(c);
1636 : if (expect > unibrow::Latin1::kMaxChar || expect == 0) expect = c;
1637 : CHECK_EQ(expect, test);
1638 : }
1639 :
1640 :
1641 : TEST(Latin1IgnoreCase) {
1642 : for (uint16_t c = unibrow::Latin1::kMaxChar + 1; c != 0; c++) {
1643 : uint16_t lower = ConvertLatin1<unibrow::ToLowercase, false>(c);
1644 : uint16_t upper = ConvertLatin1<unibrow::ToUppercase, false>(c);
1645 : uint16_t test = unibrow::Latin1::TryConvertToLatin1(c);
1646 : // Filter out all character whose upper is not their lower or vice versa.
1647 : if (lower == 0 && upper == 0) {
1648 : CheckCanonicalEquivalence(c, test);
1649 : continue;
1650 : }
1651 : if (lower > unibrow::Latin1::kMaxChar &&
1652 : upper > unibrow::Latin1::kMaxChar) {
1653 : CheckCanonicalEquivalence(c, test);
1654 : continue;
1655 : }
1656 : if (lower == 0 && upper != 0) {
1657 : lower = ConvertLatin1<unibrow::ToLowercase, false>(upper);
1658 : }
1659 : if (upper == 0 && lower != c) {
1660 : upper = ConvertLatin1<unibrow::ToUppercase, false>(lower);
1661 : }
1662 : if (lower > unibrow::Latin1::kMaxChar &&
1663 : upper > unibrow::Latin1::kMaxChar) {
1664 : CheckCanonicalEquivalence(c, test);
1665 : continue;
1666 : }
1667 : if (upper != c && lower != c) {
1668 : CheckCanonicalEquivalence(c, test);
1669 : continue;
1670 : }
1671 : CHECK_EQ(Min(upper, lower), test);
1672 : }
1673 : }
1674 : #endif
1675 :
1676 5 : class DummyResource: public v8::String::ExternalStringResource {
1677 : public:
1678 0 : const uint16_t* data() const override { return nullptr; }
1679 5 : size_t length() const override { return 1 << 30; }
1680 : };
1681 :
1682 :
1683 5 : class DummyOneByteResource: public v8::String::ExternalOneByteStringResource {
1684 : public:
1685 0 : const char* data() const override { return nullptr; }
1686 5 : size_t length() const override { return 1 << 30; }
1687 : };
1688 :
1689 :
1690 25880 : TEST(InvalidExternalString) {
1691 5 : CcTest::InitializeVM();
1692 5 : LocalContext context;
1693 : Isolate* isolate = CcTest::i_isolate();
1694 : { HandleScope scope(isolate);
1695 5 : DummyOneByteResource r;
1696 10 : CHECK(isolate->factory()->NewExternalStringFromOneByte(&r).is_null());
1697 5 : CHECK(isolate->has_pending_exception());
1698 5 : isolate->clear_pending_exception();
1699 : }
1700 :
1701 : { HandleScope scope(isolate);
1702 5 : DummyResource r;
1703 10 : CHECK(isolate->factory()->NewExternalStringFromTwoByte(&r).is_null());
1704 5 : CHECK(isolate->has_pending_exception());
1705 5 : isolate->clear_pending_exception();
1706 5 : }
1707 5 : }
1708 :
1709 :
1710 : #define INVALID_STRING_TEST(FUN, TYPE) \
1711 : TEST(StringOOM##FUN) { \
1712 : CcTest::InitializeVM(); \
1713 : LocalContext context; \
1714 : Isolate* isolate = CcTest::i_isolate(); \
1715 : STATIC_ASSERT(String::kMaxLength < kMaxInt); \
1716 : static const int invalid = String::kMaxLength + 1; \
1717 : HandleScope scope(isolate); \
1718 : Vector<TYPE> dummy = Vector<TYPE>::New(invalid); \
1719 : memset(dummy.start(), 0x0, dummy.length() * sizeof(TYPE)); \
1720 : CHECK(isolate->factory()->FUN(Vector<const TYPE>::cast(dummy)).is_null()); \
1721 : memset(dummy.start(), 0x20, dummy.length() * sizeof(TYPE)); \
1722 : CHECK(isolate->has_pending_exception()); \
1723 : isolate->clear_pending_exception(); \
1724 : dummy.Dispose(); \
1725 : }
1726 :
1727 25905 : INVALID_STRING_TEST(NewStringFromUtf8, char)
1728 25905 : INVALID_STRING_TEST(NewStringFromOneByte, uint8_t)
1729 :
1730 : #undef INVALID_STRING_TEST
1731 :
1732 :
1733 25880 : TEST(FormatMessage) {
1734 5 : CcTest::InitializeVM();
1735 5 : LocalContext context;
1736 : Isolate* isolate = CcTest::i_isolate();
1737 : HandleScope scope(isolate);
1738 5 : Handle<String> arg0 = isolate->factory()->NewStringFromAsciiChecked("arg0");
1739 5 : Handle<String> arg1 = isolate->factory()->NewStringFromAsciiChecked("arg1");
1740 5 : Handle<String> arg2 = isolate->factory()->NewStringFromAsciiChecked("arg2");
1741 : Handle<String> result =
1742 : MessageFormatter::FormatMessage(
1743 : isolate, MessageTemplate::kPropertyNotFunction, arg0, arg1, arg2)
1744 10 : .ToHandleChecked();
1745 : Handle<String> expected = isolate->factory()->NewStringFromAsciiChecked(
1746 5 : "'arg0' returned for property 'arg1' of object 'arg2' is not a function");
1747 10 : CHECK(String::Equals(isolate, result, expected));
1748 5 : }
1749 :
1750 25880 : TEST(Regress609831) {
1751 5 : CcTest::InitializeVM();
1752 5 : LocalContext context;
1753 : Isolate* isolate = CcTest::i_isolate();
1754 : {
1755 : HandleScope scope(isolate);
1756 : v8::Local<v8::Value> result = CompileRun(
1757 : "String.fromCharCode(32, 32, 32, 32, 32, "
1758 : "32, 32, 32, 32, 32, 32, 32, 32, 32, 32, "
1759 : "32, 32, 32, 32, 32, 32, 32, 32, 32, 32)");
1760 10 : CHECK(v8::Utils::OpenHandle(*result)->IsSeqOneByteString());
1761 : }
1762 : {
1763 : HandleScope scope(isolate);
1764 : v8::Local<v8::Value> result = CompileRun(
1765 : "String.fromCharCode(432, 432, 432, 432, 432, "
1766 : "432, 432, 432, 432, 432, 432, 432, 432, 432, "
1767 : "432, 432, 432, 432, 432, 432, 432, 432, 432)");
1768 10 : CHECK(v8::Utils::OpenHandle(*result)->IsSeqTwoByteString());
1769 5 : }
1770 5 : }
1771 :
1772 25880 : TEST(ExternalStringIndexOf) {
1773 5 : CcTest::InitializeVM();
1774 5 : LocalContext context;
1775 10 : v8::HandleScope scope(CcTest::isolate());
1776 :
1777 : const char* raw_string = "abcdefghijklmnopqrstuvwxyz";
1778 : v8::Local<v8::String> string =
1779 : v8::String::NewExternalOneByte(CcTest::isolate(),
1780 10 : new StaticOneByteResource(raw_string))
1781 5 : .ToLocalChecked();
1782 5 : v8::Local<v8::Object> global = context->Global();
1783 20 : global->Set(context.local(), v8_str("external"), string).FromJust();
1784 :
1785 5 : char source[] = "external.indexOf('%')";
1786 135 : for (size_t i = 0; i < strlen(raw_string); i++) {
1787 130 : source[18] = raw_string[i];
1788 130 : int result_position = static_cast<int>(i);
1789 390 : CHECK_EQ(result_position,
1790 : CompileRun(source)->Int32Value(context.local()).FromJust());
1791 : }
1792 15 : CHECK_EQ(-1,
1793 : CompileRun("external.indexOf('abcdefghijklmnopqrstuvwxyz%%%%%%')")
1794 : ->Int32Value(context.local())
1795 : .FromJust());
1796 15 : CHECK_EQ(1, CompileRun("external.indexOf('', 1)")
1797 : ->Int32Value(context.local())
1798 : .FromJust());
1799 15 : CHECK_EQ(-1, CompileRun("external.indexOf('a', 1)")
1800 : ->Int32Value(context.local())
1801 : .FromJust());
1802 15 : CHECK_EQ(-1, CompileRun("external.indexOf('$')")
1803 : ->Int32Value(context.local())
1804 5 : .FromJust());
1805 5 : }
1806 :
1807 : #define GC_INSIDE_NEW_STRING_FROM_UTF8_SUB_STRING(NAME, STRING) \
1808 : TEST(GCInsideNewStringFromUtf8SubStringWith##NAME) { \
1809 : CcTest::InitializeVM(); \
1810 : LocalContext context; \
1811 : v8::HandleScope scope(CcTest::isolate()); \
1812 : Factory* factory = CcTest::i_isolate()->factory(); \
1813 : /* Length must be bigger than the buffer size of the Utf8Decoder. */ \
1814 : const char* buf = STRING; \
1815 : size_t len = strlen(buf); \
1816 : Handle<String> main_string = \
1817 : factory \
1818 : ->NewStringFromOneByte(Vector<const uint8_t>( \
1819 : reinterpret_cast<const uint8_t*>(buf), len)) \
1820 : .ToHandleChecked(); \
1821 : CHECK(Heap::InYoungGeneration(*main_string)); \
1822 : /* Next allocation will cause GC. */ \
1823 : heap::SimulateFullSpace(CcTest::i_isolate()->heap()->new_space()); \
1824 : /* Offset by two to check substring-ing. */ \
1825 : Handle<String> s = factory \
1826 : ->NewStringFromUtf8SubString( \
1827 : Handle<SeqOneByteString>::cast(main_string), 2, \
1828 : static_cast<int>(len - 2)) \
1829 : .ToHandleChecked(); \
1830 : Handle<String> expected_string = \
1831 : factory->NewStringFromUtf8(Vector<const char>(buf + 2, len - 2)) \
1832 : .ToHandleChecked(); \
1833 : CHECK(s->Equals(*expected_string)); \
1834 : }
1835 :
1836 25925 : GC_INSIDE_NEW_STRING_FROM_UTF8_SUB_STRING(
1837 : OneByte,
1838 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1839 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1840 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1841 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1842 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1843 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1844 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1845 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1846 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ")
1847 25925 : GC_INSIDE_NEW_STRING_FROM_UTF8_SUB_STRING(
1848 : TwoByte,
1849 : "QQ\xF0\x9F\x98\x8D\xF0\x9F\x98\x8D"
1850 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1851 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1852 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1853 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1854 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1855 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1856 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1857 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1858 : "QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ"
1859 : "QQ\xF0\x9F\x98\x8D\xF0\x9F\x98\x8D")
1860 :
1861 : #undef GC_INSIDE_NEW_STRING_FROM_UTF8_SUB_STRING
1862 :
1863 25880 : TEST(HashArrayIndexStrings) {
1864 5 : CcTest::InitializeVM();
1865 5 : LocalContext context;
1866 10 : v8::HandleScope scope(CcTest::isolate());
1867 : i::Isolate* isolate = CcTest::i_isolate();
1868 :
1869 5 : CHECK_EQ(StringHasher::MakeArrayIndexHash(0 /* value */, 1 /* length */) >>
1870 : Name::kHashShift,
1871 : isolate->factory()->zero_string()->Hash());
1872 :
1873 5 : CHECK_EQ(StringHasher::MakeArrayIndexHash(1 /* value */, 1 /* length */) >>
1874 : Name::kHashShift,
1875 5 : isolate->factory()->one_string()->Hash());
1876 5 : }
1877 :
1878 25880 : TEST(StringEquals) {
1879 5 : v8::V8::Initialize();
1880 5 : v8::Isolate* isolate = CcTest::isolate();
1881 5 : v8::HandleScope scope(isolate);
1882 :
1883 : auto foo_str =
1884 : v8::String::NewFromUtf8(isolate, "foo", v8::NewStringType::kNormal)
1885 5 : .ToLocalChecked();
1886 : auto bar_str =
1887 : v8::String::NewFromUtf8(isolate, "bar", v8::NewStringType::kNormal)
1888 5 : .ToLocalChecked();
1889 : auto foo_str2 =
1890 : v8::String::NewFromUtf8(isolate, "foo", v8::NewStringType::kNormal)
1891 10 : .ToLocalChecked();
1892 :
1893 5 : uint16_t* two_byte_source = AsciiToTwoByteString("foo");
1894 : auto foo_two_byte_str =
1895 : v8::String::NewFromTwoByte(isolate, two_byte_source,
1896 : v8::NewStringType::kNormal)
1897 10 : .ToLocalChecked();
1898 : i::DeleteArray(two_byte_source);
1899 :
1900 5 : CHECK(foo_str->StringEquals(foo_str));
1901 5 : CHECK(!foo_str->StringEquals(bar_str));
1902 5 : CHECK(foo_str->StringEquals(foo_str2));
1903 5 : CHECK(foo_str->StringEquals(foo_two_byte_str));
1904 5 : CHECK(!bar_str->StringEquals(foo_str2));
1905 5 : }
1906 :
1907 : class OneByteStringResource : public v8::String::ExternalOneByteStringResource {
1908 : public:
1909 : // Takes ownership of |data|.
1910 : OneByteStringResource(char* data, size_t length)
1911 5 : : data_(data), length_(length) {}
1912 10 : ~OneByteStringResource() override { delete[] data_; }
1913 5 : const char* data() const override { return data_; }
1914 5 : size_t length() const override { return length_; }
1915 :
1916 : private:
1917 : char* data_;
1918 : size_t length_;
1919 : };
1920 :
1921 25880 : TEST(Regress876759) {
1922 5 : v8::V8::Initialize();
1923 : Isolate* isolate = CcTest::i_isolate();
1924 : Factory* factory = isolate->factory();
1925 :
1926 : HandleScope handle_scope(isolate);
1927 :
1928 : const int kLength = 30;
1929 : uc16 two_byte_buf[kLength];
1930 5 : char* external_one_byte_buf = new char[kLength];
1931 155 : for (int j = 0; j < kLength; j++) {
1932 150 : char c = '0' + (j % 10);
1933 150 : two_byte_buf[j] = c;
1934 150 : external_one_byte_buf[j] = c;
1935 : }
1936 :
1937 : Handle<String> parent;
1938 : {
1939 : Handle<SeqTwoByteString> raw =
1940 10 : factory->NewRawTwoByteString(kLength).ToHandleChecked();
1941 : DisallowHeapAllocation no_gc;
1942 : CopyChars(raw->GetChars(no_gc), two_byte_buf, kLength);
1943 : parent = raw;
1944 : }
1945 5 : CHECK(parent->IsTwoByteRepresentation());
1946 5 : Handle<String> sliced = factory->NewSubString(parent, 1, 20);
1947 10 : CHECK(sliced->IsSlicedString());
1948 5 : factory->InternalizeString(parent);
1949 10 : CHECK(parent->IsThinString());
1950 : Handle<String> grandparent =
1951 10 : handle(ThinString::cast(*parent)->actual(), isolate);
1952 15 : CHECK_EQ(*parent, SlicedString::cast(*sliced)->parent());
1953 : OneByteStringResource* resource =
1954 5 : new OneByteStringResource(external_one_byte_buf, kLength);
1955 5 : grandparent->MakeExternal(resource);
1956 : // The grandparent string becomes one-byte, but the child strings are still
1957 : // two-byte.
1958 5 : CHECK(grandparent->IsOneByteRepresentation());
1959 5 : CHECK(parent->IsTwoByteRepresentation());
1960 5 : CHECK(sliced->IsTwoByteRepresentation());
1961 : // The *Underneath version returns the correct representation.
1962 5 : CHECK(String::IsOneByteRepresentationUnderneath(*sliced));
1963 5 : }
1964 :
1965 : } // namespace test_strings
1966 : } // namespace internal
1967 77625 : } // namespace v8
|
