1 // Copyright 2013 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 #include <stdlib.h> 29 30 #include "src/v8.h" 31 32 #include "src/crankshaft/unique.h" 33 #include "src/factory.h" 34 #include "src/global-handles.h" 35 #include "test/cctest/cctest.h" 36 37 using namespace v8::internal; 38 39 #define MAKE_HANDLES_AND_DISALLOW_ALLOCATION \ 40 Isolate* isolate = CcTest::i_isolate(); \ 41 Factory* factory = isolate->factory(); \ 42 HandleScope sc(isolate); \ 43 Handle<String> handles[] = { \ 44 factory->InternalizeUtf8String("A"), \ 45 factory->InternalizeUtf8String("B"), \ 46 factory->InternalizeUtf8String("C"), \ 47 factory->InternalizeUtf8String("D"), \ 48 factory->InternalizeUtf8String("E"), \ 49 factory->InternalizeUtf8String("F"), \ 50 factory->InternalizeUtf8String("G") \ 51 }; \ 52 DisallowHeapAllocation _disable 53 54 #define MAKE_UNIQUES_A_B_C \ 55 Unique<String> A(handles[0]); \ 56 Unique<String> B(handles[1]); \ 57 Unique<String> C(handles[2]) 58 59 #define MAKE_UNIQUES_A_B_C_D_E_F_G \ 60 Unique<String> A(handles[0]); \ 61 Unique<String> B(handles[1]); \ 62 Unique<String> C(handles[2]); \ 63 Unique<String> D(handles[3]); \ 64 Unique<String> E(handles[4]); \ 65 Unique<String> F(handles[5]); \ 66 Unique<String> G(handles[6]) 67 68 template <class T, class U> 69 void CheckHashCodeEqual(Unique<T> a, Unique<U> b) { 70 int64_t hasha = static_cast<int64_t>(a.Hashcode()); 71 int64_t hashb = static_cast<int64_t>(b.Hashcode()); 72 CHECK_NE(static_cast<int64_t>(0), hasha); 73 CHECK_NE(static_cast<int64_t>(0), hashb); 74 CHECK_EQ(hasha, hashb); 75 } 76 77 78 template <class T, class U> 79 void CheckHashCodeNotEqual(Unique<T> a, Unique<U> b) { 80 int64_t hasha = static_cast<int64_t>(a.Hashcode()); 81 int64_t hashb = static_cast<int64_t>(b.Hashcode()); 82 CHECK_NE(static_cast<int64_t>(0), hasha); 83 CHECK_NE(static_cast<int64_t>(0), hashb); 84 CHECK_NE(hasha, hashb); 85 } 86 87 88 TEST(UniqueCreate) { 89 CcTest::InitializeVM(); 90 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 91 Handle<String> A = handles[0], B = handles[1]; 92 93 Unique<String> HA(A); 94 95 CHECK(*HA.handle() == *A); 96 CHECK_EQ(*A, *HA.handle()); 97 98 Unique<String> HA2(A); 99 100 CheckHashCodeEqual(HA, HA2); 101 CHECK(HA == HA2); 102 CHECK_EQ(*HA.handle(), *HA2.handle()); 103 104 CHECK(HA2 == HA); 105 CHECK_EQ(*HA2.handle(), *HA.handle()); 106 107 Unique<String> HB(B); 108 109 CheckHashCodeNotEqual(HA, HB); 110 CHECK(HA != HB); 111 CHECK_NE(*HA.handle(), *HB.handle()); 112 113 CHECK(HB != HA); 114 CHECK_NE(*HB.handle(), *HA.handle()); 115 116 // TODO(titzer): check that Unique properly survives a GC. 117 } 118 119 120 TEST(UniqueSubsume) { 121 CcTest::InitializeVM(); 122 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 123 Handle<String> A = handles[0]; 124 125 Unique<String> HA(A); 126 127 CHECK(*HA.handle() == *A); 128 CHECK_EQ(*A, *HA.handle()); 129 130 Unique<Object> HO = HA; // Here comes the subsumption, boys. 131 132 CheckHashCodeEqual(HA, HO); 133 CHECK(HA == HO); 134 CHECK_EQ(*HA.handle(), *HO.handle()); 135 136 CHECK(HO == HA); 137 CHECK_EQ(*HO.handle(), *HA.handle()); 138 } 139 140 141 TEST(UniqueSet_Add) { 142 CcTest::InitializeVM(); 143 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 144 MAKE_UNIQUES_A_B_C; 145 146 Zone zone(CcTest::i_isolate()->allocator()); 147 148 UniqueSet<String>* set = new(&zone) UniqueSet<String>(); 149 150 CHECK_EQ(0, set->size()); 151 set->Add(A, &zone); 152 CHECK_EQ(1, set->size()); 153 set->Add(A, &zone); 154 CHECK_EQ(1, set->size()); 155 set->Add(B, &zone); 156 CHECK_EQ(2, set->size()); 157 set->Add(C, &zone); 158 CHECK_EQ(3, set->size()); 159 set->Add(C, &zone); 160 CHECK_EQ(3, set->size()); 161 set->Add(B, &zone); 162 CHECK_EQ(3, set->size()); 163 set->Add(A, &zone); 164 CHECK_EQ(3, set->size()); 165 } 166 167 168 TEST(UniqueSet_Remove) { 169 CcTest::InitializeVM(); 170 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 171 MAKE_UNIQUES_A_B_C; 172 173 Zone zone(CcTest::i_isolate()->allocator()); 174 175 UniqueSet<String>* set = new(&zone) UniqueSet<String>(); 176 177 set->Add(A, &zone); 178 set->Add(B, &zone); 179 set->Add(C, &zone); 180 CHECK_EQ(3, set->size()); 181 182 set->Remove(A); 183 CHECK_EQ(2, set->size()); 184 CHECK(!set->Contains(A)); 185 CHECK(set->Contains(B)); 186 CHECK(set->Contains(C)); 187 188 set->Remove(A); 189 CHECK_EQ(2, set->size()); 190 CHECK(!set->Contains(A)); 191 CHECK(set->Contains(B)); 192 CHECK(set->Contains(C)); 193 194 set->Remove(B); 195 CHECK_EQ(1, set->size()); 196 CHECK(!set->Contains(A)); 197 CHECK(!set->Contains(B)); 198 CHECK(set->Contains(C)); 199 200 set->Remove(C); 201 CHECK_EQ(0, set->size()); 202 CHECK(!set->Contains(A)); 203 CHECK(!set->Contains(B)); 204 CHECK(!set->Contains(C)); 205 } 206 207 208 TEST(UniqueSet_Contains) { 209 CcTest::InitializeVM(); 210 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 211 MAKE_UNIQUES_A_B_C; 212 213 Zone zone(CcTest::i_isolate()->allocator()); 214 215 UniqueSet<String>* set = new(&zone) UniqueSet<String>(); 216 217 CHECK_EQ(0, set->size()); 218 set->Add(A, &zone); 219 CHECK(set->Contains(A)); 220 CHECK(!set->Contains(B)); 221 CHECK(!set->Contains(C)); 222 223 set->Add(A, &zone); 224 CHECK(set->Contains(A)); 225 CHECK(!set->Contains(B)); 226 CHECK(!set->Contains(C)); 227 228 set->Add(B, &zone); 229 CHECK(set->Contains(A)); 230 CHECK(set->Contains(B)); 231 232 set->Add(C, &zone); 233 CHECK(set->Contains(A)); 234 CHECK(set->Contains(B)); 235 CHECK(set->Contains(C)); 236 } 237 238 239 TEST(UniqueSet_At) { 240 CcTest::InitializeVM(); 241 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 242 MAKE_UNIQUES_A_B_C; 243 244 Zone zone(CcTest::i_isolate()->allocator()); 245 246 UniqueSet<String>* set = new(&zone) UniqueSet<String>(); 247 248 CHECK_EQ(0, set->size()); 249 set->Add(A, &zone); 250 CHECK(A == set->at(0)); 251 252 set->Add(A, &zone); 253 CHECK(A == set->at(0)); 254 255 set->Add(B, &zone); 256 CHECK(A == set->at(0) || B == set->at(0)); 257 CHECK(A == set->at(1) || B == set->at(1)); 258 259 set->Add(C, &zone); 260 CHECK(A == set->at(0) || B == set->at(0) || C == set->at(0)); 261 CHECK(A == set->at(1) || B == set->at(1) || C == set->at(1)); 262 CHECK(A == set->at(2) || B == set->at(2) || C == set->at(2)); 263 } 264 265 266 template <class T> 267 static void CHECK_SETS( 268 UniqueSet<T>* set1, UniqueSet<T>* set2, bool expected) { 269 CHECK(set1->Equals(set1)); 270 CHECK(set2->Equals(set2)); 271 CHECK(expected == set1->Equals(set2)); 272 CHECK(expected == set2->Equals(set1)); 273 } 274 275 276 TEST(UniqueSet_Equals) { 277 CcTest::InitializeVM(); 278 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 279 MAKE_UNIQUES_A_B_C; 280 281 Zone zone(CcTest::i_isolate()->allocator()); 282 283 UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 284 UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 285 286 CHECK_SETS(set1, set2, true); 287 288 set1->Add(A, &zone); 289 290 CHECK_SETS(set1, set2, false); 291 292 set2->Add(A, &zone); 293 294 CHECK_SETS(set1, set2, true); 295 296 set1->Add(B, &zone); 297 298 CHECK_SETS(set1, set2, false); 299 300 set2->Add(C, &zone); 301 302 CHECK_SETS(set1, set2, false); 303 304 set1->Add(C, &zone); 305 306 CHECK_SETS(set1, set2, false); 307 308 set2->Add(B, &zone); 309 310 CHECK_SETS(set1, set2, true); 311 } 312 313 314 TEST(UniqueSet_IsSubset1) { 315 CcTest::InitializeVM(); 316 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 317 MAKE_UNIQUES_A_B_C; 318 319 Zone zone(CcTest::i_isolate()->allocator()); 320 321 UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 322 UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 323 324 CHECK(set1->IsSubset(set2)); 325 CHECK(set2->IsSubset(set1)); 326 327 set1->Add(A, &zone); 328 329 CHECK(!set1->IsSubset(set2)); 330 CHECK(set2->IsSubset(set1)); 331 332 set2->Add(B, &zone); 333 334 CHECK(!set1->IsSubset(set2)); 335 CHECK(!set2->IsSubset(set1)); 336 337 set2->Add(A, &zone); 338 339 CHECK(set1->IsSubset(set2)); 340 CHECK(!set2->IsSubset(set1)); 341 342 set1->Add(B, &zone); 343 344 CHECK(set1->IsSubset(set2)); 345 CHECK(set2->IsSubset(set1)); 346 } 347 348 349 TEST(UniqueSet_IsSubset2) { 350 CcTest::InitializeVM(); 351 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 352 MAKE_UNIQUES_A_B_C_D_E_F_G; 353 354 Zone zone(CcTest::i_isolate()->allocator()); 355 356 UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 357 UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 358 359 set1->Add(A, &zone); 360 set1->Add(C, &zone); 361 set1->Add(E, &zone); 362 363 set2->Add(A, &zone); 364 set2->Add(B, &zone); 365 set2->Add(C, &zone); 366 set2->Add(D, &zone); 367 set2->Add(E, &zone); 368 set2->Add(F, &zone); 369 370 CHECK(set1->IsSubset(set2)); 371 CHECK(!set2->IsSubset(set1)); 372 373 set1->Add(G, &zone); 374 375 CHECK(!set1->IsSubset(set2)); 376 CHECK(!set2->IsSubset(set1)); 377 } 378 379 380 template <class T> 381 static UniqueSet<T>* MakeSet(Zone* zone, int which, Unique<T>* elements) { 382 UniqueSet<T>* set = new(zone) UniqueSet<T>(); 383 for (int i = 0; i < 32; i++) { 384 if ((which & (1 << i)) != 0) set->Add(elements[i], zone); 385 } 386 return set; 387 } 388 389 390 TEST(UniqueSet_IsSubsetExhaustive) { 391 const int kSetSize = 6; 392 393 CcTest::InitializeVM(); 394 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 395 MAKE_UNIQUES_A_B_C_D_E_F_G; 396 397 Zone zone(CcTest::i_isolate()->allocator()); 398 399 Unique<String> elements[] = { 400 A, B, C, D, E, F, G 401 }; 402 403 // Exhaustively test all sets with <= 6 elements. 404 for (int i = 0; i < (1 << kSetSize); i++) { 405 for (int j = 0; j < (1 << kSetSize); j++) { 406 UniqueSet<String>* set1 = MakeSet(&zone, i, elements); 407 UniqueSet<String>* set2 = MakeSet(&zone, j, elements); 408 409 CHECK(((i & j) == i) == set1->IsSubset(set2)); 410 } 411 } 412 } 413 414 415 TEST(UniqueSet_Intersect1) { 416 CcTest::InitializeVM(); 417 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 418 MAKE_UNIQUES_A_B_C; 419 420 Zone zone(CcTest::i_isolate()->allocator()); 421 422 UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 423 UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 424 UniqueSet<String>* result; 425 426 CHECK(set1->IsSubset(set2)); 427 CHECK(set2->IsSubset(set1)); 428 429 set1->Add(A, &zone); 430 431 result = set1->Intersect(set2, &zone); 432 433 CHECK_EQ(0, result->size()); 434 CHECK(set2->Equals(result)); 435 436 set2->Add(A, &zone); 437 438 result = set1->Intersect(set2, &zone); 439 440 CHECK_EQ(1, result->size()); 441 CHECK(set1->Equals(result)); 442 CHECK(set2->Equals(result)); 443 444 set2->Add(B, &zone); 445 set2->Add(C, &zone); 446 447 result = set1->Intersect(set2, &zone); 448 449 CHECK_EQ(1, result->size()); 450 CHECK(set1->Equals(result)); 451 } 452 453 454 TEST(UniqueSet_IntersectExhaustive) { 455 const int kSetSize = 6; 456 457 CcTest::InitializeVM(); 458 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 459 MAKE_UNIQUES_A_B_C_D_E_F_G; 460 461 Zone zone(CcTest::i_isolate()->allocator()); 462 463 Unique<String> elements[] = { 464 A, B, C, D, E, F, G 465 }; 466 467 // Exhaustively test all sets with <= 6 elements. 468 for (int i = 0; i < (1 << kSetSize); i++) { 469 for (int j = 0; j < (1 << kSetSize); j++) { 470 UniqueSet<String>* set1 = MakeSet(&zone, i, elements); 471 UniqueSet<String>* set2 = MakeSet(&zone, j, elements); 472 473 UniqueSet<String>* result = set1->Intersect(set2, &zone); 474 UniqueSet<String>* expected = MakeSet(&zone, i & j, elements); 475 476 CHECK(result->Equals(expected)); 477 CHECK(expected->Equals(result)); 478 } 479 } 480 } 481 482 483 TEST(UniqueSet_Union1) { 484 CcTest::InitializeVM(); 485 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 486 MAKE_UNIQUES_A_B_C; 487 488 Zone zone(CcTest::i_isolate()->allocator()); 489 490 UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 491 UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 492 UniqueSet<String>* result; 493 494 CHECK(set1->IsSubset(set2)); 495 CHECK(set2->IsSubset(set1)); 496 497 set1->Add(A, &zone); 498 499 result = set1->Union(set2, &zone); 500 501 CHECK_EQ(1, result->size()); 502 CHECK(set1->Equals(result)); 503 504 set2->Add(A, &zone); 505 506 result = set1->Union(set2, &zone); 507 508 CHECK_EQ(1, result->size()); 509 CHECK(set1->Equals(result)); 510 CHECK(set2->Equals(result)); 511 512 set2->Add(B, &zone); 513 set2->Add(C, &zone); 514 515 result = set1->Union(set2, &zone); 516 517 CHECK_EQ(3, result->size()); 518 CHECK(set2->Equals(result)); 519 } 520 521 522 TEST(UniqueSet_UnionExhaustive) { 523 const int kSetSize = 6; 524 525 CcTest::InitializeVM(); 526 MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 527 MAKE_UNIQUES_A_B_C_D_E_F_G; 528 529 Zone zone(CcTest::i_isolate()->allocator()); 530 531 Unique<String> elements[] = { 532 A, B, C, D, E, F, G 533 }; 534 535 // Exhaustively test all sets with <= 6 elements. 536 for (int i = 0; i < (1 << kSetSize); i++) { 537 for (int j = 0; j < (1 << kSetSize); j++) { 538 UniqueSet<String>* set1 = MakeSet(&zone, i, elements); 539 UniqueSet<String>* set2 = MakeSet(&zone, j, elements); 540 541 UniqueSet<String>* result = set1->Union(set2, &zone); 542 UniqueSet<String>* expected = MakeSet(&zone, i | j, elements); 543 544 CHECK(result->Equals(expected)); 545 CHECK(expected->Equals(result)); 546 } 547 } 548 } 549
