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
37using namespace v8::internal;
38
39#define MAKE_HANDLES_AND_DISALLOW_ALLOCATION  \
40Isolate* isolate = CcTest::i_isolate();       \
41Factory* factory = isolate->factory();        \
42HandleScope sc(isolate);                      \
43Handle<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};                                            \
52DisallowHeapAllocation _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
68template <class T, class U>
69void 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
78template <class T, class U>
79void 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
88TEST(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
120TEST(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
141TEST(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
168TEST(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
208TEST(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
239TEST(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
266template <class T>
267static 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
276TEST(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
314TEST(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
349TEST(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
380template <class T>
381static 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
390TEST(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
415TEST(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
454TEST(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
483TEST(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
522TEST(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