Home | History | Annotate | Download | only in cctest
      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