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 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 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: 54 explicit Resource(Vector<const uc16> string): data_(string.start()) { 55 length_ = string.length(); 56 } 57 virtual const uint16_t* data() const { return data_; } 58 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: 69 explicit AsciiResource(Vector<const char> string): data_(string.start()) { 70 length_ = string.length(); 71 } 72 virtual const char* data() const { return data_; } 73 virtual size_t length() const { return length_; } 74 75 private: 76 const char* data_; 77 size_t length_; 78 }; 79 80 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 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 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 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 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 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 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 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 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 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 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 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 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: 507 explicit AsciiVectorResource(i::Vector<const char> vector) 508 : data_(vector) {} 509 virtual ~AsciiVectorResource() {} 510 virtual size_t length() const { return data_.length(); } 511 virtual const char* data() const { return data_.start(); } 512 private: 513 i::Vector<const char> data_; 514 }; 515 516 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 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 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
