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/factory.h"
33 #include "src/global-handles.h"
34 #include "src/unique.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>
CheckHashCodeEqual(Unique<T> a,Unique<U> b)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>
CheckHashCodeNotEqual(Unique<T> a,Unique<U> b)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 
TEST(UniqueCreate)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 
TEST(UniqueSubsume)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 
TEST(UniqueSet_Add)141 TEST(UniqueSet_Add) {
142   CcTest::InitializeVM();
143   MAKE_HANDLES_AND_DISALLOW_ALLOCATION;
144   MAKE_UNIQUES_A_B_C;
145 
146   Zone zone(isolate);
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 
TEST(UniqueSet_Remove)168 TEST(UniqueSet_Remove) {
169   CcTest::InitializeVM();
170   MAKE_HANDLES_AND_DISALLOW_ALLOCATION;
171   MAKE_UNIQUES_A_B_C;
172 
173   Zone zone(isolate);
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 
TEST(UniqueSet_Contains)208 TEST(UniqueSet_Contains) {
209   CcTest::InitializeVM();
210   MAKE_HANDLES_AND_DISALLOW_ALLOCATION;
211   MAKE_UNIQUES_A_B_C;
212 
213   Zone zone(isolate);
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 
TEST(UniqueSet_At)239 TEST(UniqueSet_At) {
240   CcTest::InitializeVM();
241   MAKE_HANDLES_AND_DISALLOW_ALLOCATION;
242   MAKE_UNIQUES_A_B_C;
243 
244   Zone zone(isolate);
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>
CHECK_SETS(UniqueSet<T> * set1,UniqueSet<T> * set2,bool expected)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 
TEST(UniqueSet_Equals)276 TEST(UniqueSet_Equals) {
277   CcTest::InitializeVM();
278   MAKE_HANDLES_AND_DISALLOW_ALLOCATION;
279   MAKE_UNIQUES_A_B_C;
280 
281   Zone zone(isolate);
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 
TEST(UniqueSet_IsSubset1)314 TEST(UniqueSet_IsSubset1) {
315   CcTest::InitializeVM();
316   MAKE_HANDLES_AND_DISALLOW_ALLOCATION;
317   MAKE_UNIQUES_A_B_C;
318 
319   Zone zone(isolate);
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 
TEST(UniqueSet_IsSubset2)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(isolate);
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>
MakeSet(Zone * zone,int which,Unique<T> * elements)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 
TEST(UniqueSet_IsSubsetExhaustive)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(isolate);
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 
TEST(UniqueSet_Intersect1)415 TEST(UniqueSet_Intersect1) {
416   CcTest::InitializeVM();
417   MAKE_HANDLES_AND_DISALLOW_ALLOCATION;
418   MAKE_UNIQUES_A_B_C;
419 
420   Zone zone(isolate);
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 
TEST(UniqueSet_IntersectExhaustive)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(isolate);
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 
TEST(UniqueSet_Union1)483 TEST(UniqueSet_Union1) {
484   CcTest::InitializeVM();
485   MAKE_HANDLES_AND_DISALLOW_ALLOCATION;
486   MAKE_UNIQUES_A_B_C;
487 
488   Zone zone(isolate);
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 
TEST(UniqueSet_UnionExhaustive)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(isolate);
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