1 // Copyright 2011 the V8 project authors. All rights reserved.
2
3 // Check that we can traverse very deep stacks of ConsStrings using
4 // StringInputBuffer. Check that Get(int) works on very deep stacks
5 // of ConsStrings. These operations may not be very fast, but they
6 // should be possible without getting errors due to too deep recursion.
7
8 #include <stdlib.h>
9
10 #include "v8.h"
11
12 #include "api.h"
13 #include "factory.h"
14 #include "cctest.h"
15 #include "zone-inl.h"
16
17 unsigned int seed = 123;
18
gen()19 static uint32_t gen() {
20 uint64_t z;
21 z = seed;
22 z *= 279470273;
23 z %= 4294967291U;
24 seed = static_cast<unsigned int>(z);
25 return static_cast<uint32_t>(seed >> 16);
26 }
27
28
29 using namespace v8::internal;
30
31 static v8::Persistent<v8::Context> env;
32
33
InitializeVM()34 static void InitializeVM() {
35 if (env.IsEmpty()) {
36 v8::HandleScope scope;
37 const char* extensions[] = { "v8/print" };
38 v8::ExtensionConfiguration config(1, extensions);
39 env = v8::Context::New(&config);
40 }
41 v8::HandleScope scope;
42 env->Enter();
43 }
44
45
46 static const int NUMBER_OF_BUILDING_BLOCKS = 128;
47 static const int DEEP_DEPTH = 8 * 1024;
48 static const int SUPER_DEEP_DEPTH = 80 * 1024;
49
50
51 class Resource: public v8::String::ExternalStringResource,
52 public ZoneObject {
53 public:
Resource(Vector<const uc16> string)54 explicit Resource(Vector<const uc16> string): data_(string.start()) {
55 length_ = string.length();
56 }
data() const57 virtual const uint16_t* data() const { return data_; }
length() const58 virtual size_t length() const { return length_; }
59
60 private:
61 const uc16* data_;
62 size_t length_;
63 };
64
65
66 class AsciiResource: public v8::String::ExternalAsciiStringResource,
67 public ZoneObject {
68 public:
AsciiResource(Vector<const char> string)69 explicit AsciiResource(Vector<const char> string): data_(string.start()) {
70 length_ = string.length();
71 }
data() const72 virtual const char* data() const { return data_; }
length() const73 virtual size_t length() const { return length_; }
74
75 private:
76 const char* data_;
77 size_t length_;
78 };
79
80
InitializeBuildingBlocks(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS])81 static void InitializeBuildingBlocks(
82 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS]) {
83 // A list of pointers that we don't have any interest in cleaning up.
84 // If they are reachable from a root then leak detection won't complain.
85 for (int i = 0; i < NUMBER_OF_BUILDING_BLOCKS; i++) {
86 int len = gen() % 16;
87 if (len > 14) {
88 len += 1234;
89 }
90 switch (gen() % 4) {
91 case 0: {
92 uc16 buf[2000];
93 for (int j = 0; j < len; j++) {
94 buf[j] = gen() % 65536;
95 }
96 building_blocks[i] =
97 FACTORY->NewStringFromTwoByte(Vector<const uc16>(buf, len));
98 for (int j = 0; j < len; j++) {
99 CHECK_EQ(buf[j], building_blocks[i]->Get(j));
100 }
101 break;
102 }
103 case 1: {
104 char buf[2000];
105 for (int j = 0; j < len; j++) {
106 buf[j] = gen() % 128;
107 }
108 building_blocks[i] =
109 FACTORY->NewStringFromAscii(Vector<const char>(buf, len));
110 for (int j = 0; j < len; j++) {
111 CHECK_EQ(buf[j], building_blocks[i]->Get(j));
112 }
113 break;
114 }
115 case 2: {
116 uc16* buf = ZONE->NewArray<uc16>(len);
117 for (int j = 0; j < len; j++) {
118 buf[j] = gen() % 65536;
119 }
120 Resource* resource = new Resource(Vector<const uc16>(buf, len));
121 building_blocks[i] = FACTORY->NewExternalStringFromTwoByte(resource);
122 for (int j = 0; j < len; j++) {
123 CHECK_EQ(buf[j], building_blocks[i]->Get(j));
124 }
125 break;
126 }
127 case 3: {
128 char* buf = NewArray<char>(len);
129 for (int j = 0; j < len; j++) {
130 buf[j] = gen() % 128;
131 }
132 building_blocks[i] =
133 FACTORY->NewStringFromAscii(Vector<const char>(buf, len));
134 for (int j = 0; j < len; j++) {
135 CHECK_EQ(buf[j], building_blocks[i]->Get(j));
136 }
137 DeleteArray<char>(buf);
138 break;
139 }
140 }
141 }
142 }
143
144
ConstructLeft(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],int depth)145 static Handle<String> ConstructLeft(
146 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
147 int depth) {
148 Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
149 for (int i = 0; i < depth; i++) {
150 answer = FACTORY->NewConsString(
151 answer,
152 building_blocks[i % NUMBER_OF_BUILDING_BLOCKS]);
153 }
154 return answer;
155 }
156
157
ConstructRight(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],int depth)158 static Handle<String> ConstructRight(
159 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
160 int depth) {
161 Handle<String> answer = FACTORY->NewStringFromAscii(CStrVector(""));
162 for (int i = depth - 1; i >= 0; i--) {
163 answer = FACTORY->NewConsString(
164 building_blocks[i % NUMBER_OF_BUILDING_BLOCKS],
165 answer);
166 }
167 return answer;
168 }
169
170
ConstructBalancedHelper(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],int from,int to)171 static Handle<String> ConstructBalancedHelper(
172 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS],
173 int from,
174 int to) {
175 CHECK(to > from);
176 if (to - from == 1) {
177 return building_blocks[from % NUMBER_OF_BUILDING_BLOCKS];
178 }
179 if (to - from == 2) {
180 return FACTORY->NewConsString(
181 building_blocks[from % NUMBER_OF_BUILDING_BLOCKS],
182 building_blocks[(from+1) % NUMBER_OF_BUILDING_BLOCKS]);
183 }
184 Handle<String> part1 =
185 ConstructBalancedHelper(building_blocks, from, from + ((to - from) / 2));
186 Handle<String> part2 =
187 ConstructBalancedHelper(building_blocks, from + ((to - from) / 2), to);
188 return FACTORY->NewConsString(part1, part2);
189 }
190
191
ConstructBalanced(Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS])192 static Handle<String> ConstructBalanced(
193 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS]) {
194 return ConstructBalancedHelper(building_blocks, 0, DEEP_DEPTH);
195 }
196
197
198 static StringInputBuffer buffer;
199
200
Traverse(Handle<String> s1,Handle<String> s2)201 static void Traverse(Handle<String> s1, Handle<String> s2) {
202 int i = 0;
203 buffer.Reset(*s1);
204 StringInputBuffer buffer2(*s2);
205 while (buffer.has_more()) {
206 CHECK(buffer2.has_more());
207 uint16_t c = buffer.GetNext();
208 CHECK_EQ(c, buffer2.GetNext());
209 i++;
210 }
211 CHECK_EQ(s1->length(), i);
212 CHECK_EQ(s2->length(), i);
213 }
214
215
TraverseFirst(Handle<String> s1,Handle<String> s2,int chars)216 static void TraverseFirst(Handle<String> s1, Handle<String> s2, int chars) {
217 int i = 0;
218 buffer.Reset(*s1);
219 StringInputBuffer buffer2(*s2);
220 while (buffer.has_more() && i < chars) {
221 CHECK(buffer2.has_more());
222 uint16_t c = buffer.GetNext();
223 CHECK_EQ(c, buffer2.GetNext());
224 i++;
225 }
226 s1->Get(s1->length() - 1);
227 s2->Get(s2->length() - 1);
228 }
229
230
TEST(Traverse)231 TEST(Traverse) {
232 printf("TestTraverse\n");
233 InitializeVM();
234 v8::HandleScope scope;
235 Handle<String> building_blocks[NUMBER_OF_BUILDING_BLOCKS];
236 ZoneScope zone(Isolate::Current(), DELETE_ON_EXIT);
237 InitializeBuildingBlocks(building_blocks);
238 Handle<String> flat = ConstructBalanced(building_blocks);
239 FlattenString(flat);
240 Handle<String> left_asymmetric = ConstructLeft(building_blocks, DEEP_DEPTH);
241 Handle<String> right_asymmetric = ConstructRight(building_blocks, DEEP_DEPTH);
242 Handle<String> symmetric = ConstructBalanced(building_blocks);
243 printf("1\n");
244 Traverse(flat, symmetric);
245 printf("2\n");
246 Traverse(flat, left_asymmetric);
247 printf("3\n");
248 Traverse(flat, right_asymmetric);
249 printf("4\n");
250 Handle<String> left_deep_asymmetric =
251 ConstructLeft(building_blocks, SUPER_DEEP_DEPTH);
252 Handle<String> right_deep_asymmetric =
253 ConstructRight(building_blocks, SUPER_DEEP_DEPTH);
254 printf("5\n");
255 TraverseFirst(left_asymmetric, left_deep_asymmetric, 1050);
256 printf("6\n");
257 TraverseFirst(left_asymmetric, right_deep_asymmetric, 65536);
258 printf("7\n");
259 FlattenString(left_asymmetric);
260 printf("10\n");
261 Traverse(flat, left_asymmetric);
262 printf("11\n");
263 FlattenString(right_asymmetric);
264 printf("12\n");
265 Traverse(flat, right_asymmetric);
266 printf("14\n");
267 FlattenString(symmetric);
268 printf("15\n");
269 Traverse(flat, symmetric);
270 printf("16\n");
271 FlattenString(left_deep_asymmetric);
272 printf("18\n");
273 }
274
275
276 static const int DEEP_ASCII_DEPTH = 100000;
277
278
TEST(DeepAscii)279 TEST(DeepAscii) {
280 printf("TestDeepAscii\n");
281 InitializeVM();
282 v8::HandleScope scope;
283
284 char* foo = NewArray<char>(DEEP_ASCII_DEPTH);
285 for (int i = 0; i < DEEP_ASCII_DEPTH; i++) {
286 foo[i] = "foo "[i % 4];
287 }
288 Handle<String> string =
289 FACTORY->NewStringFromAscii(Vector<const char>(foo, DEEP_ASCII_DEPTH));
290 Handle<String> foo_string = FACTORY->NewStringFromAscii(CStrVector("foo"));
291 for (int i = 0; i < DEEP_ASCII_DEPTH; i += 10) {
292 string = FACTORY->NewConsString(string, foo_string);
293 }
294 Handle<String> flat_string = FACTORY->NewConsString(string, foo_string);
295 FlattenString(flat_string);
296
297 for (int i = 0; i < 500; i++) {
298 TraverseFirst(flat_string, string, DEEP_ASCII_DEPTH);
299 }
300 DeleteArray<char>(foo);
301 }
302
303
TEST(Utf8Conversion)304 TEST(Utf8Conversion) {
305 // Smoke test for converting strings to utf-8.
306 InitializeVM();
307 v8::HandleScope handle_scope;
308 // A simple ascii string
309 const char* ascii_string = "abcdef12345";
310 int len =
311 v8::String::New(ascii_string,
312 StrLength(ascii_string))->Utf8Length();
313 CHECK_EQ(StrLength(ascii_string), len);
314 // A mixed ascii and non-ascii string
315 // U+02E4 -> CB A4
316 // U+0064 -> 64
317 // U+12E4 -> E1 8B A4
318 // U+0030 -> 30
319 // U+3045 -> E3 81 85
320 const uint16_t mixed_string[] = {0x02E4, 0x0064, 0x12E4, 0x0030, 0x3045};
321 // The characters we expect to be output
322 const unsigned char as_utf8[11] = {0xCB, 0xA4, 0x64, 0xE1, 0x8B, 0xA4, 0x30,
323 0xE3, 0x81, 0x85, 0x00};
324 // The number of bytes expected to be written for each length
325 const int lengths[12] = {0, 0, 2, 3, 3, 3, 6, 7, 7, 7, 10, 11};
326 const int char_lengths[12] = {0, 0, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5};
327 v8::Handle<v8::String> mixed = v8::String::New(mixed_string, 5);
328 CHECK_EQ(10, mixed->Utf8Length());
329 // Try encoding the string with all capacities
330 char buffer[11];
331 const char kNoChar = static_cast<char>(-1);
332 for (int i = 0; i <= 11; i++) {
333 // Clear the buffer before reusing it
334 for (int j = 0; j < 11; j++)
335 buffer[j] = kNoChar;
336 int chars_written;
337 int written = mixed->WriteUtf8(buffer, i, &chars_written);
338 CHECK_EQ(lengths[i], written);
339 CHECK_EQ(char_lengths[i], chars_written);
340 // Check that the contents are correct
341 for (int j = 0; j < lengths[i]; j++)
342 CHECK_EQ(as_utf8[j], static_cast<unsigned char>(buffer[j]));
343 // Check that the rest of the buffer hasn't been touched
344 for (int j = lengths[i]; j < 11; j++)
345 CHECK_EQ(kNoChar, buffer[j]);
346 }
347 }
348
349
TEST(ExternalShortStringAdd)350 TEST(ExternalShortStringAdd) {
351 ZoneScope zone(Isolate::Current(), DELETE_ON_EXIT);
352
353 InitializeVM();
354 v8::HandleScope handle_scope;
355
356 // Make sure we cover all always-flat lengths and at least one above.
357 static const int kMaxLength = 20;
358 CHECK_GT(kMaxLength, i::ConsString::kMinLength);
359
360 // Allocate two JavaScript arrays for holding short strings.
361 v8::Handle<v8::Array> ascii_external_strings =
362 v8::Array::New(kMaxLength + 1);
363 v8::Handle<v8::Array> non_ascii_external_strings =
364 v8::Array::New(kMaxLength + 1);
365
366 // Generate short ascii and non-ascii external strings.
367 for (int i = 0; i <= kMaxLength; i++) {
368 char* ascii = ZONE->NewArray<char>(i + 1);
369 for (int j = 0; j < i; j++) {
370 ascii[j] = 'a';
371 }
372 // Terminating '\0' is left out on purpose. It is not required for external
373 // string data.
374 AsciiResource* ascii_resource =
375 new AsciiResource(Vector<const char>(ascii, i));
376 v8::Local<v8::String> ascii_external_string =
377 v8::String::NewExternal(ascii_resource);
378
379 ascii_external_strings->Set(v8::Integer::New(i), ascii_external_string);
380 uc16* non_ascii = ZONE->NewArray<uc16>(i + 1);
381 for (int j = 0; j < i; j++) {
382 non_ascii[j] = 0x1234;
383 }
384 // Terminating '\0' is left out on purpose. It is not required for external
385 // string data.
386 Resource* resource = new Resource(Vector<const uc16>(non_ascii, i));
387 v8::Local<v8::String> non_ascii_external_string =
388 v8::String::NewExternal(resource);
389 non_ascii_external_strings->Set(v8::Integer::New(i),
390 non_ascii_external_string);
391 }
392
393 // Add the arrays with the short external strings in the global object.
394 v8::Handle<v8::Object> global = env->Global();
395 global->Set(v8_str("external_ascii"), ascii_external_strings);
396 global->Set(v8_str("external_non_ascii"), non_ascii_external_strings);
397 global->Set(v8_str("max_length"), v8::Integer::New(kMaxLength));
398
399 // Add short external ascii and non-ascii strings checking the result.
400 static const char* source =
401 "function test() {"
402 " var ascii_chars = 'aaaaaaaaaaaaaaaaaaaa';"
403 " var non_ascii_chars = '\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234\\u1234';" //NOLINT
404 " if (ascii_chars.length != max_length) return 1;"
405 " if (non_ascii_chars.length != max_length) return 2;"
406 " var ascii = Array(max_length + 1);"
407 " var non_ascii = Array(max_length + 1);"
408 " for (var i = 0; i <= max_length; i++) {"
409 " ascii[i] = ascii_chars.substring(0, i);"
410 " non_ascii[i] = non_ascii_chars.substring(0, i);"
411 " };"
412 " for (var i = 0; i <= max_length; i++) {"
413 " if (ascii[i] != external_ascii[i]) return 3;"
414 " if (non_ascii[i] != external_non_ascii[i]) return 4;"
415 " for (var j = 0; j < i; j++) {"
416 " if (external_ascii[i] !="
417 " (external_ascii[j] + external_ascii[i - j])) return 5;"
418 " if (external_non_ascii[i] !="
419 " (external_non_ascii[j] + external_non_ascii[i - j])) return 6;"
420 " if (non_ascii[i] != (non_ascii[j] + non_ascii[i - j])) return 7;"
421 " if (ascii[i] != (ascii[j] + ascii[i - j])) return 8;"
422 " if (ascii[i] != (external_ascii[j] + ascii[i - j])) return 9;"
423 " if (ascii[i] != (ascii[j] + external_ascii[i - j])) return 10;"
424 " if (non_ascii[i] !="
425 " (external_non_ascii[j] + non_ascii[i - j])) return 11;"
426 " if (non_ascii[i] !="
427 " (non_ascii[j] + external_non_ascii[i - j])) return 12;"
428 " }"
429 " }"
430 " return 0;"
431 "};"
432 "test()";
433 CHECK_EQ(0, CompileRun(source)->Int32Value());
434 }
435
436
TEST(CachedHashOverflow)437 TEST(CachedHashOverflow) {
438 // We incorrectly allowed strings to be tagged as array indices even if their
439 // values didn't fit in the hash field.
440 // See http://code.google.com/p/v8/issues/detail?id=728
441 ZoneScope zone(Isolate::Current(), DELETE_ON_EXIT);
442
443 InitializeVM();
444 v8::HandleScope handle_scope;
445 // Lines must be executed sequentially. Combining them into one script
446 // makes the bug go away.
447 const char* lines[] = {
448 "var x = [];",
449 "x[4] = 42;",
450 "var s = \"1073741828\";",
451 "x[s];",
452 "x[s] = 37;",
453 "x[4];",
454 "x[s];",
455 NULL
456 };
457
458 Handle<Smi> fortytwo(Smi::FromInt(42));
459 Handle<Smi> thirtyseven(Smi::FromInt(37));
460 Handle<Object> results[] = {
461 FACTORY->undefined_value(),
462 fortytwo,
463 FACTORY->undefined_value(),
464 FACTORY->undefined_value(),
465 thirtyseven,
466 fortytwo,
467 thirtyseven // Bug yielded 42 here.
468 };
469
470 const char* line;
471 for (int i = 0; (line = lines[i]); i++) {
472 printf("%s\n", line);
473 v8::Local<v8::Value> result =
474 v8::Script::Compile(v8::String::New(line))->Run();
475 CHECK_EQ(results[i]->IsUndefined(), result->IsUndefined());
476 CHECK_EQ(results[i]->IsNumber(), result->IsNumber());
477 if (result->IsNumber()) {
478 CHECK_EQ(Smi::cast(results[i]->ToSmi()->ToObjectChecked())->value(),
479 result->ToInt32()->Value());
480 }
481 }
482 }
483
484
TEST(SliceFromCons)485 TEST(SliceFromCons) {
486 FLAG_string_slices = true;
487 InitializeVM();
488 v8::HandleScope scope;
489 Handle<String> string =
490 FACTORY->NewStringFromAscii(CStrVector("parentparentparent"));
491 Handle<String> parent = FACTORY->NewConsString(string, string);
492 CHECK(parent->IsConsString());
493 CHECK(!parent->IsFlat());
494 Handle<String> slice = FACTORY->NewSubString(parent, 1, 25);
495 // After slicing, the original string becomes a flat cons.
496 CHECK(parent->IsFlat());
497 CHECK(slice->IsSlicedString());
498 CHECK_EQ(SlicedString::cast(*slice)->parent(),
499 ConsString::cast(*parent)->first());
500 CHECK(SlicedString::cast(*slice)->parent()->IsSeqString());
501 CHECK(slice->IsFlat());
502 }
503
504
505 class AsciiVectorResource : public v8::String::ExternalAsciiStringResource {
506 public:
AsciiVectorResource(i::Vector<const char> vector)507 explicit AsciiVectorResource(i::Vector<const char> vector)
508 : data_(vector) {}
~AsciiVectorResource()509 virtual ~AsciiVectorResource() {}
length() const510 virtual size_t length() const { return data_.length(); }
data() const511 virtual const char* data() const { return data_.start(); }
512 private:
513 i::Vector<const char> data_;
514 };
515
516
TEST(SliceFromExternal)517 TEST(SliceFromExternal) {
518 FLAG_string_slices = true;
519 InitializeVM();
520 v8::HandleScope scope;
521 AsciiVectorResource resource(
522 i::Vector<const char>("abcdefghijklmnopqrstuvwxyz", 26));
523 Handle<String> string = FACTORY->NewExternalStringFromAscii(&resource);
524 CHECK(string->IsExternalString());
525 Handle<String> slice = FACTORY->NewSubString(string, 1, 25);
526 CHECK(slice->IsSlicedString());
527 CHECK(string->IsExternalString());
528 CHECK_EQ(SlicedString::cast(*slice)->parent(), *string);
529 CHECK(SlicedString::cast(*slice)->parent()->IsExternalString());
530 CHECK(slice->IsFlat());
531 }
532
533
TEST(TrivialSlice)534 TEST(TrivialSlice) {
535 // This tests whether a slice that contains the entire parent string
536 // actually creates a new string (it should not).
537 FLAG_string_slices = true;
538 InitializeVM();
539 HandleScope scope;
540 v8::Local<v8::Value> result;
541 Handle<String> string;
542 const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
543 const char* check = "str.slice(0,26)";
544 const char* crosscheck = "str.slice(1,25)";
545
546 CompileRun(init);
547
548 result = CompileRun(check);
549 CHECK(result->IsString());
550 string = v8::Utils::OpenHandle(v8::String::Cast(*result));
551 CHECK(!string->IsSlicedString());
552
553 string = FACTORY->NewSubString(string, 0, 26);
554 CHECK(!string->IsSlicedString());
555 result = CompileRun(crosscheck);
556 CHECK(result->IsString());
557 string = v8::Utils::OpenHandle(v8::String::Cast(*result));
558 CHECK(string->IsSlicedString());
559 CHECK_EQ("bcdefghijklmnopqrstuvwxy", *(string->ToCString()));
560 }
561
562
TEST(SliceFromSlice)563 TEST(SliceFromSlice) {
564 // This tests whether a slice that contains the entire parent string
565 // actually creates a new string (it should not).
566 FLAG_string_slices = true;
567 InitializeVM();
568 HandleScope scope;
569 v8::Local<v8::Value> result;
570 Handle<String> string;
571 const char* init = "var str = 'abcdefghijklmnopqrstuvwxyz';";
572 const char* slice = "var slice = str.slice(1,-1); slice";
573 const char* slice_from_slice = "slice.slice(1,-1);";
574
575 CompileRun(init);
576 result = CompileRun(slice);
577 CHECK(result->IsString());
578 string = v8::Utils::OpenHandle(v8::String::Cast(*result));
579 CHECK(string->IsSlicedString());
580 CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
581 CHECK_EQ("bcdefghijklmnopqrstuvwxy", *(string->ToCString()));
582
583 result = CompileRun(slice_from_slice);
584 CHECK(result->IsString());
585 string = v8::Utils::OpenHandle(v8::String::Cast(*result));
586 CHECK(string->IsSlicedString());
587 CHECK(SlicedString::cast(*string)->parent()->IsSeqString());
588 CHECK_EQ("cdefghijklmnopqrstuvwx", *(string->ToCString()));
589 }
590