Line data Source code
1 : // Copyright 2013 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include <vector>
6 :
7 : #include "src/compiler/types.h"
8 : #include "src/factory-inl.h"
9 : #include "src/heap/heap.h"
10 : #include "src/isolate.h"
11 : #include "src/objects.h"
12 : #include "test/cctest/cctest.h"
13 : #include "test/cctest/types-fuzz.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 : namespace compiler {
18 :
19 : namespace {
20 :
21 : // Testing auxiliaries (breaking the Type abstraction).
22 :
23 :
24 : static bool IsInteger(double x) {
25 76 : return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities.
26 : }
27 :
28 : typedef uint32_t bitset;
29 :
30 36 : struct Tests {
31 : typedef Types::TypeVector::iterator TypeIterator;
32 : typedef Types::ValueVector::iterator ValueIterator;
33 :
34 : Isolate* isolate;
35 : HandleScope scope;
36 : Zone zone;
37 : Types T;
38 :
39 18 : Tests()
40 18 : : isolate(CcTest::InitIsolateOnce()),
41 : scope(isolate),
42 : zone(isolate->allocator(), ZONE_NAME),
43 36 : T(&zone, isolate, isolate->random_number_generator()) {}
44 :
45 : bool IsBitset(Type* type) { return type->IsBitsetForTesting(); }
46 : bool IsUnion(Type* type) { return type->IsUnionForTesting(); }
47 : BitsetType::bitset AsBitset(Type* type) { return type->AsBitsetForTesting(); }
48 : UnionType* AsUnion(Type* type) { return type->AsUnionForTesting(); }
49 :
50 145516 : bool Equal(Type* type1, Type* type2) {
51 186216 : return type1->Equals(type2) &&
52 40700 : this->IsBitset(type1) == this->IsBitset(type2) &&
53 40700 : this->IsUnion(type1) == this->IsUnion(type2) &&
54 81400 : type1->NumConstants() == type2->NumConstants() &&
55 35059 : (!this->IsBitset(type1) ||
56 186216 : this->AsBitset(type1) == this->AsBitset(type2)) &&
57 3328 : (!this->IsUnion(type1) ||
58 : this->AsUnion(type1)->LengthForTesting() ==
59 145516 : this->AsUnion(type2)->LengthForTesting());
60 : }
61 :
62 40022 : void CheckEqual(Type* type1, Type* type2) { CHECK(Equal(type1, type2)); }
63 :
64 31 : void CheckSub(Type* type1, Type* type2) {
65 31 : CHECK(type1->Is(type2));
66 31 : CHECK(!type2->Is(type1));
67 51 : if (this->IsBitset(type1) && this->IsBitset(type2)) {
68 20 : CHECK(this->AsBitset(type1) != this->AsBitset(type2));
69 : }
70 31 : }
71 :
72 1 : void CheckSubOrEqual(Type* type1, Type* type2) {
73 1 : CHECK(type1->Is(type2));
74 2 : if (this->IsBitset(type1) && this->IsBitset(type2)) {
75 1 : CHECK((this->AsBitset(type1) | this->AsBitset(type2))
76 : == this->AsBitset(type2));
77 : }
78 1 : }
79 :
80 16 : void CheckUnordered(Type* type1, Type* type2) {
81 16 : CHECK(!type1->Is(type2));
82 16 : CHECK(!type2->Is(type1));
83 27 : if (this->IsBitset(type1) && this->IsBitset(type2)) {
84 11 : CHECK(this->AsBitset(type1) != this->AsBitset(type2));
85 : }
86 16 : }
87 :
88 29 : void CheckOverlap(Type* type1, Type* type2) {
89 29 : CHECK(type1->Maybe(type2));
90 29 : CHECK(type2->Maybe(type1));
91 29 : }
92 :
93 11 : void CheckDisjoint(Type* type1, Type* type2) {
94 11 : CHECK(!type1->Is(type2));
95 11 : CHECK(!type2->Is(type1));
96 11 : CHECK(!type1->Maybe(type2));
97 11 : CHECK(!type2->Maybe(type1));
98 11 : }
99 :
100 1 : void IsSomeType() {
101 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
102 124 : Type* t = *it;
103 620 : CHECK_EQ(1, this->IsBitset(t) + t->IsHeapConstant() + t->IsRange() +
104 : t->IsOtherNumberConstant() + this->IsUnion(t));
105 : }
106 1 : }
107 :
108 1 : void Bitset() {
109 : // None and Any are bitsets.
110 2 : CHECK(this->IsBitset(T.None));
111 2 : CHECK(this->IsBitset(T.Any));
112 :
113 1 : CHECK(bitset(0) == this->AsBitset(T.None));
114 1 : CHECK(bitset(0xfffffffeu) == this->AsBitset(T.Any));
115 :
116 : // Union(T1, T2) is bitset for bitsets T1,T2
117 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
118 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
119 15376 : Type* type1 = *it1;
120 15376 : Type* type2 = *it2;
121 72953 : Type* union12 = T.Union(type1, type2);
122 40093 : CHECK(!(this->IsBitset(type1) && this->IsBitset(type2)) ||
123 : this->IsBitset(union12));
124 : }
125 : }
126 :
127 : // Intersect(T1, T2) is bitset for bitsets T1,T2
128 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
129 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
130 15376 : Type* type1 = *it1;
131 15376 : Type* type2 = *it2;
132 : Type* intersect12 = T.Intersect(type1, type2);
133 40093 : CHECK(!(this->IsBitset(type1) && this->IsBitset(type2)) ||
134 : this->IsBitset(intersect12));
135 : }
136 : }
137 :
138 : // Union(T1, T2) is bitset if T2 is bitset and T1->Is(T2)
139 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
140 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
141 15376 : Type* type1 = *it1;
142 15376 : Type* type2 = *it2;
143 : Type* union12 = T.Union(type1, type2);
144 32449 : CHECK(!(this->IsBitset(type2) && type1->Is(type2)) ||
145 : this->IsBitset(union12));
146 : }
147 : }
148 :
149 : // Union(T1, T2) is bitwise disjunction for bitsets T1,T2
150 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
151 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
152 15376 : Type* type1 = *it1;
153 15376 : Type* type2 = *it2;
154 : Type* union12 = T.Union(type1, type2);
155 28644 : if (this->IsBitset(type1) && this->IsBitset(type2)) {
156 22898 : CHECK(
157 : (this->AsBitset(type1) | this->AsBitset(type2)) ==
158 : this->AsBitset(union12));
159 : }
160 : }
161 : }
162 :
163 : // Intersect(T1, T2) is bitwise conjunction for bitsets T1,T2 (modulo None)
164 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
165 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
166 15376 : Type* type1 = *it1;
167 15376 : Type* type2 = *it2;
168 28644 : if (this->IsBitset(type1) && this->IsBitset(type2)) {
169 : Type* intersect12 = T.Intersect(type1, type2);
170 11449 : bitset bits = this->AsBitset(type1) & this->AsBitset(type2);
171 11449 : CHECK(bits == this->AsBitset(intersect12));
172 : }
173 : }
174 : }
175 1 : }
176 :
177 1 : void Constant() {
178 : // Constructor
179 12 : for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
180 10 : Handle<i::Object> value = *vt;
181 260 : Type* type = T.NewConstant(value);
182 19 : CHECK(type->IsHeapConstant() || type->IsOtherNumberConstant() ||
183 : type->IsRange());
184 : }
185 :
186 : // Value attribute
187 12 : for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
188 10 : Handle<i::Object> value = *vt;
189 : Type* type = T.NewConstant(value);
190 10 : if (type->IsHeapConstant()) {
191 4 : CHECK(value.address() == type->AsHeapConstant()->Value().address());
192 6 : } else if (type->IsOtherNumberConstant()) {
193 3 : CHECK(value->IsHeapNumber());
194 3 : CHECK(value->Number() == type->AsOtherNumberConstant()->Value());
195 : } else {
196 3 : CHECK(type->IsRange());
197 : double v = value->Number();
198 3 : CHECK(v == type->AsRange()->Min() && v == type->AsRange()->Max());
199 : }
200 : }
201 :
202 : // Functionality & Injectivity: Constant(V1) = Constant(V2) iff V1 = V2
203 12 : for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
204 120 : for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
205 100 : Handle<i::Object> value1 = *vt1;
206 100 : Handle<i::Object> value2 = *vt2;
207 : Type* type1 = T.NewConstant(value1);
208 : Type* type2 = T.NewConstant(value2);
209 130 : if (type1->IsOtherNumberConstant() && type2->IsOtherNumberConstant()) {
210 9 : CHECK(Equal(type1, type2) ==
211 : (type1->AsOtherNumberConstant()->Value() ==
212 : type2->AsOtherNumberConstant()->Value()));
213 121 : } else if (type1->IsRange() && type2->IsRange()) {
214 9 : CHECK(Equal(type1, type2) ==
215 : ((type1->AsRange()->Min() == type2->AsRange()->Min()) &&
216 : (type1->AsRange()->Max() == type2->AsRange()->Max())));
217 : } else {
218 164 : CHECK(Equal(type1, type2) == (*value1 == *value2));
219 : }
220 : }
221 : }
222 :
223 : // Typing of numbers
224 1 : Factory* fac = isolate->factory();
225 2 : CHECK(T.NewConstant(fac->NewNumber(0))->Is(T.UnsignedSmall));
226 2 : CHECK(T.NewConstant(fac->NewNumber(1))->Is(T.UnsignedSmall));
227 2 : CHECK(T.NewConstant(fac->NewNumber(0x3fffffff))->Is(T.UnsignedSmall));
228 2 : CHECK(T.NewConstant(fac->NewNumber(-1))->Is(T.Negative31));
229 2 : CHECK(T.NewConstant(fac->NewNumber(-0x3fffffff))->Is(T.Negative31));
230 2 : CHECK(T.NewConstant(fac->NewNumber(-0x40000000))->Is(T.Negative31));
231 2 : CHECK(T.NewConstant(fac->NewNumber(0x40000000))->Is(T.Unsigned31));
232 2 : CHECK(!T.NewConstant(fac->NewNumber(0x40000000))->Is(T.Unsigned30));
233 2 : CHECK(T.NewConstant(fac->NewNumber(0x7fffffff))->Is(T.Unsigned31));
234 2 : CHECK(!T.NewConstant(fac->NewNumber(0x7fffffff))->Is(T.Unsigned30));
235 2 : CHECK(T.NewConstant(fac->NewNumber(-0x40000001))->Is(T.Negative32));
236 2 : CHECK(!T.NewConstant(fac->NewNumber(-0x40000001))->Is(T.Negative31));
237 2 : CHECK(T.NewConstant(fac->NewNumber(-0x7fffffff))->Is(T.Negative32));
238 2 : CHECK(!T.NewConstant(fac->NewNumber(-0x7fffffff - 1))->Is(T.Negative31));
239 : if (SmiValuesAre31Bits()) {
240 : CHECK(!T.NewConstant(fac->NewNumber(0x40000000))->Is(T.UnsignedSmall));
241 : CHECK(!T.NewConstant(fac->NewNumber(0x7fffffff))->Is(T.UnsignedSmall));
242 : CHECK(!T.NewConstant(fac->NewNumber(-0x40000001))->Is(T.SignedSmall));
243 : CHECK(!T.NewConstant(fac->NewNumber(-0x7fffffff - 1))->Is(T.SignedSmall));
244 : } else {
245 : CHECK(SmiValuesAre32Bits());
246 2 : CHECK(T.NewConstant(fac->NewNumber(0x40000000))->Is(T.UnsignedSmall));
247 2 : CHECK(T.NewConstant(fac->NewNumber(0x7fffffff))->Is(T.UnsignedSmall));
248 2 : CHECK(T.NewConstant(fac->NewNumber(-0x40000001))->Is(T.SignedSmall));
249 2 : CHECK(T.NewConstant(fac->NewNumber(-0x7fffffff - 1))->Is(T.SignedSmall));
250 : }
251 2 : CHECK(T.NewConstant(fac->NewNumber(0x80000000u))->Is(T.Unsigned32));
252 2 : CHECK(!T.NewConstant(fac->NewNumber(0x80000000u))->Is(T.Unsigned31));
253 2 : CHECK(T.NewConstant(fac->NewNumber(0xffffffffu))->Is(T.Unsigned32));
254 2 : CHECK(!T.NewConstant(fac->NewNumber(0xffffffffu))->Is(T.Unsigned31));
255 2 : CHECK(T.NewConstant(fac->NewNumber(0xffffffffu + 1.0))->Is(T.PlainNumber));
256 2 : CHECK(!T.NewConstant(fac->NewNumber(0xffffffffu + 1.0))->Is(T.Integral32));
257 2 : CHECK(T.NewConstant(fac->NewNumber(-0x7fffffff - 2.0))->Is(T.PlainNumber));
258 2 : CHECK(!T.NewConstant(fac->NewNumber(-0x7fffffff - 2.0))->Is(T.Integral32));
259 2 : CHECK(T.NewConstant(fac->NewNumber(0.1))->Is(T.PlainNumber));
260 2 : CHECK(!T.NewConstant(fac->NewNumber(0.1))->Is(T.Integral32));
261 2 : CHECK(T.NewConstant(fac->NewNumber(-10.1))->Is(T.PlainNumber));
262 2 : CHECK(!T.NewConstant(fac->NewNumber(-10.1))->Is(T.Integral32));
263 2 : CHECK(T.NewConstant(fac->NewNumber(10e60))->Is(T.PlainNumber));
264 2 : CHECK(!T.NewConstant(fac->NewNumber(10e60))->Is(T.Integral32));
265 2 : CHECK(T.NewConstant(fac->NewNumber(-1.0 * 0.0))->Is(T.MinusZero));
266 2 : CHECK(
267 : T.NewConstant(fac->NewNumber(std::numeric_limits<double>::quiet_NaN()))
268 : ->Is(T.NaN));
269 2 : CHECK(T.NewConstant(fac->NewNumber(V8_INFINITY))->Is(T.PlainNumber));
270 2 : CHECK(!T.NewConstant(fac->NewNumber(V8_INFINITY))->Is(T.Integral32));
271 2 : CHECK(T.NewConstant(fac->NewNumber(-V8_INFINITY))->Is(T.PlainNumber));
272 2 : CHECK(!T.NewConstant(fac->NewNumber(-V8_INFINITY))->Is(T.Integral32));
273 :
274 : // Typing of Strings
275 1 : Handle<String> s1 = fac->NewStringFromAsciiChecked("a");
276 2 : CHECK(T.NewConstant(s1)->Is(T.InternalizedSeqString));
277 1 : const uc16 two_byte[1] = {0x2603};
278 : Handle<String> s2 =
279 1 : fac->NewTwoByteInternalizedString(Vector<const uc16>(two_byte, 1), 1);
280 2 : CHECK(T.NewConstant(s2)->Is(T.InternalizedSeqString));
281 1 : }
282 :
283 1 : void Range() {
284 : // Constructor
285 26 : for (ValueIterator i = T.integers.begin(); i != T.integers.end(); ++i) {
286 624 : for (ValueIterator j = T.integers.begin(); j != T.integers.end(); ++j) {
287 : double min = (*i)->Number();
288 : double max = (*j)->Number();
289 576 : if (min > max) std::swap(min, max);
290 181152 : Type* type = T.Range(min, max);
291 576 : CHECK(type->IsRange());
292 : }
293 : }
294 :
295 : // Range attributes
296 26 : for (ValueIterator i = T.integers.begin(); i != T.integers.end(); ++i) {
297 624 : for (ValueIterator j = T.integers.begin(); j != T.integers.end(); ++j) {
298 : double min = (*i)->Number();
299 : double max = (*j)->Number();
300 576 : if (min > max) std::swap(min, max);
301 : Type* type = T.Range(min, max);
302 576 : CHECK(min == type->AsRange()->Min());
303 576 : CHECK(max == type->AsRange()->Max());
304 : }
305 : }
306 :
307 : // Functionality & Injectivity:
308 : // Range(min1, max1) = Range(min2, max2) <=> min1 = min2 /\ max1 = max2
309 26 : for (ValueIterator i1 = T.integers.begin();
310 : i1 != T.integers.end(); ++i1) {
311 324 : for (ValueIterator j1 = i1;
312 : j1 != T.integers.end(); ++j1) {
313 7800 : for (ValueIterator i2 = T.integers.begin();
314 : i2 != T.integers.end(); ++i2) {
315 97200 : for (ValueIterator j2 = i2;
316 : j2 != T.integers.end(); ++j2) {
317 : double min1 = (*i1)->Number();
318 : double max1 = (*j1)->Number();
319 : double min2 = (*i2)->Number();
320 : double max2 = (*j2)->Number();
321 90000 : if (min1 > max1) std::swap(min1, max1);
322 90000 : if (min2 > max2) std::swap(min2, max2);
323 : Type* type1 = T.Range(min1, max1);
324 : Type* type2 = T.Range(min2, max2);
325 90000 : CHECK(Equal(type1, type2) == (min1 == min2 && max1 == max2));
326 : }
327 : }
328 : }
329 : }
330 1 : }
331 :
332 1 : void Of() {
333 : // Constant(V)->Is(Of(V))
334 12 : for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
335 10 : Handle<i::Object> value = *vt;
336 2490 : Type* const_type = T.NewConstant(value);
337 : Type* of_type = T.Of(value);
338 10 : CHECK(const_type->Is(of_type));
339 : }
340 :
341 : // If Of(V)->Is(T), then Constant(V)->Is(T)
342 12 : for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
343 1260 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
344 1240 : Handle<i::Object> value = *vt;
345 1240 : Type* type = *it;
346 : Type* const_type = T.NewConstant(value);
347 : Type* of_type = T.Of(value);
348 1659 : CHECK(!of_type->Is(type) || const_type->Is(type));
349 : }
350 : }
351 :
352 : // If Constant(V)->Is(T), then Of(V)->Is(T) or T->Maybe(Constant(V))
353 12 : for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
354 1260 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
355 1240 : Handle<i::Object> value = *vt;
356 1240 : Type* type = *it;
357 : Type* const_type = T.NewConstant(value);
358 : Type* of_type = T.Of(value);
359 1680 : CHECK(!const_type->Is(type) ||
360 : of_type->Is(type) || type->Maybe(const_type));
361 : }
362 : }
363 1 : }
364 :
365 1 : void MinMax() {
366 : // If b is regular numeric bitset, then Range(b->Min(), b->Max())->Is(b).
367 : // TODO(neis): Need to ignore representation for this to be true.
368 : /*
369 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
370 : Type* type = *it;
371 : if (this->IsBitset(type) && type->Is(T.Number) &&
372 : !type->Is(T.None) && !type->Is(T.NaN)) {
373 : Type* range = T.Range(
374 : isolate->factory()->NewNumber(type->Min()),
375 : isolate->factory()->NewNumber(type->Max()));
376 : CHECK(range->Is(type));
377 : }
378 : }
379 : */
380 :
381 : // If b is regular numeric bitset, then b->Min() and b->Max() are integers.
382 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
383 124 : Type* type = *it;
384 253 : if (this->IsBitset(type) && type->Is(T.Number) && !type->Is(T.NaN)) {
385 57 : CHECK(IsInteger(type->Min()) && IsInteger(type->Max()));
386 : }
387 : }
388 :
389 : // If b1 and b2 are regular numeric bitsets with b1->Is(b2), then
390 : // b1->Min() >= b2->Min() and b1->Max() <= b2->Max().
391 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
392 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
393 15376 : Type* type1 = *it1;
394 15376 : Type* type2 = *it2;
395 32428 : if (this->IsBitset(type1) && type1->Is(type2) && type2->Is(T.Number) &&
396 15853 : !type1->Is(T.NaN) && !type2->Is(T.NaN)) {
397 137 : CHECK(type1->Min() >= type2->Min());
398 137 : CHECK(type1->Max() <= type2->Max());
399 : }
400 : }
401 : }
402 :
403 : // Lub(Range(x,y))->Min() <= x and y <= Lub(Range(x,y))->Max()
404 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
405 124 : Type* type = *it;
406 124 : if (type->IsRange()) {
407 5 : Type* lub = BitsetType::NewForTesting(BitsetType::Lub(type));
408 5 : CHECK(lub->Min() <= type->Min() && type->Max() <= lub->Max());
409 : }
410 : }
411 :
412 : // Rangification: If T->Is(Range(-inf,+inf)) and T is inhabited, then
413 : // T->Is(Range(T->Min(), T->Max())).
414 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
415 124 : Type* type = *it;
416 276 : CHECK(!type->Is(T.Integer) || !type->IsInhabited() ||
417 : type->Is(T.Range(type->Min(), type->Max())));
418 : }
419 1 : }
420 :
421 1 : void BitsetGlb() {
422 : // Lower: (T->BitsetGlb())->Is(T)
423 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
424 124 : Type* type = *it;
425 124 : Type* glb = BitsetType::NewForTesting(BitsetType::Glb(type));
426 124 : CHECK(glb->Is(type));
427 : }
428 :
429 : // Greatest: If T1->IsBitset() and T1->Is(T2), then T1->Is(T2->BitsetGlb())
430 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
431 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
432 15376 : Type* type1 = *it1;
433 15376 : Type* type2 = *it2;
434 15376 : Type* glb2 = BitsetType::NewForTesting(BitsetType::Glb(type2));
435 32225 : CHECK(!this->IsBitset(type1) || !type1->Is(type2) || type1->Is(glb2));
436 : }
437 : }
438 :
439 : // Monotonicity: T1->Is(T2) implies (T1->BitsetGlb())->Is(T2->BitsetGlb())
440 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
441 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
442 15376 : Type* type1 = *it1;
443 15376 : Type* type2 = *it2;
444 15376 : Type* glb1 = BitsetType::NewForTesting(BitsetType::Glb(type1));
445 15376 : Type* glb2 = BitsetType::NewForTesting(BitsetType::Glb(type2));
446 19631 : CHECK(!type1->Is(type2) || glb1->Is(glb2));
447 : }
448 : }
449 1 : }
450 :
451 1 : void BitsetLub() {
452 : // Upper: T->Is(T->BitsetLub())
453 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
454 124 : Type* type = *it;
455 124 : Type* lub = BitsetType::NewForTesting(BitsetType::Lub(type));
456 124 : CHECK(type->Is(lub));
457 : }
458 :
459 : // Least: If T2->IsBitset() and T1->Is(T2), then (T1->BitsetLub())->Is(T2)
460 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
461 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
462 15376 : Type* type1 = *it1;
463 15376 : Type* type2 = *it2;
464 15376 : Type* lub1 = BitsetType::NewForTesting(BitsetType::Lub(type1));
465 32449 : CHECK(!this->IsBitset(type2) || !type1->Is(type2) || lub1->Is(type2));
466 : }
467 : }
468 :
469 : // Monotonicity: T1->Is(T2) implies (T1->BitsetLub())->Is(T2->BitsetLub())
470 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
471 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
472 15376 : Type* type1 = *it1;
473 15376 : Type* type2 = *it2;
474 15376 : Type* lub1 = BitsetType::NewForTesting(BitsetType::Lub(type1));
475 15376 : Type* lub2 = BitsetType::NewForTesting(BitsetType::Lub(type2));
476 19631 : CHECK(!type1->Is(type2) || lub1->Is(lub2));
477 : }
478 : }
479 1 : }
480 :
481 1 : void Is1() {
482 : // Least Element (Bottom): None->Is(T)
483 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
484 124 : Type* type = *it;
485 248 : CHECK(T.None->Is(type));
486 : }
487 :
488 : // Greatest Element (Top): T->Is(Any)
489 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
490 124 : Type* type = *it;
491 248 : CHECK(type->Is(T.Any));
492 : }
493 :
494 : // Bottom Uniqueness: T->Is(None) implies T = None
495 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
496 124 : Type* type = *it;
497 248 : if (type->Is(T.None)) CheckEqual(type, T.None);
498 : }
499 :
500 : // Top Uniqueness: Any->Is(T) implies T = Any
501 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
502 124 : Type* type = *it;
503 248 : if (T.Any->Is(type)) CheckEqual(type, T.Any);
504 : }
505 :
506 : // Reflexivity: T->Is(T)
507 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
508 : Type* type = *it;
509 : CHECK(type->Is(type));
510 : }
511 :
512 : // Transitivity: T1->Is(T2) and T2->Is(T3) implies T1->Is(T3)
513 125 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
514 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
515 1937376 : for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
516 1906624 : Type* type1 = *it1;
517 1906624 : Type* type2 = *it2;
518 1906624 : Type* type3 = *it3;
519 2527865 : CHECK(!(type1->Is(type2) && type2->Is(type3)) || type1->Is(type3));
520 : }
521 : }
522 : }
523 :
524 : // Antisymmetry: T1->Is(T2) and T2->Is(T1) iff T1 = T2
525 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
526 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
527 15376 : Type* type1 = *it1;
528 15376 : Type* type2 = *it2;
529 19631 : CHECK((type1->Is(type2) && type2->Is(type1)) == Equal(type1, type2));
530 : }
531 : }
532 :
533 : // (In-)Compatibilities.
534 126 : for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) {
535 15624 : for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) {
536 15376 : Type* type1 = *i;
537 15376 : Type* type2 = *j;
538 20337 : CHECK(!type1->Is(type2) || this->IsBitset(type2) ||
539 : this->IsUnion(type2) || this->IsUnion(type1) ||
540 : (type1->IsHeapConstant() && type2->IsHeapConstant()) ||
541 : (this->IsBitset(type1) && type2->IsRange()) ||
542 : (type1->IsRange() && type2->IsRange()) ||
543 : (type1->IsOtherNumberConstant() &&
544 : type2->IsOtherNumberConstant()) ||
545 : !type1->IsInhabited());
546 : }
547 : }
548 1 : }
549 :
550 1 : void Is2() {
551 : // Range(X1, Y1)->Is(Range(X2, Y2)) iff X1 >= X2 /\ Y1 <= Y2
552 26 : for (ValueIterator i1 = T.integers.begin();
553 : i1 != T.integers.end(); ++i1) {
554 324 : for (ValueIterator j1 = i1;
555 : j1 != T.integers.end(); ++j1) {
556 7800 : for (ValueIterator i2 = T.integers.begin();
557 : i2 != T.integers.end(); ++i2) {
558 97200 : for (ValueIterator j2 = i2;
559 : j2 != T.integers.end(); ++j2) {
560 : double min1 = (*i1)->Number();
561 : double max1 = (*j1)->Number();
562 : double min2 = (*i2)->Number();
563 : double max2 = (*j2)->Number();
564 90000 : if (min1 > max1) std::swap(min1, max1);
565 90000 : if (min2 > max2) std::swap(min2, max2);
566 180200 : Type* type1 = T.Range(min1, max1);
567 : Type* type2 = T.Range(min2, max2);
568 90000 : CHECK(type1->Is(type2) == (min1 >= min2 && max1 <= max2));
569 : }
570 : }
571 : }
572 : }
573 :
574 : // Constant(V1)->Is(Constant(V2)) iff V1 = V2
575 12 : for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
576 120 : for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
577 100 : Handle<i::Object> value1 = *vt1;
578 100 : Handle<i::Object> value2 = *vt2;
579 : Type* const_type1 = T.NewConstant(value1);
580 : Type* const_type2 = T.NewConstant(value2);
581 130 : if (const_type1->IsOtherNumberConstant() &&
582 : const_type2->IsOtherNumberConstant()) {
583 9 : CHECK(const_type1->Is(const_type2) ==
584 : (const_type1->AsOtherNumberConstant()->Value() ==
585 : const_type2->AsOtherNumberConstant()->Value()));
586 121 : } else if (const_type1->IsRange() && const_type2->IsRange()) {
587 9 : CHECK(Equal(const_type1, const_type2) ==
588 : ((const_type1->AsRange()->Min() ==
589 : const_type2->AsRange()->Min()) &&
590 : (const_type1->AsRange()->Max() ==
591 : const_type2->AsRange()->Max())));
592 : } else {
593 82 : CHECK(const_type1->Is(const_type2) == (*value1 == *value2));
594 : }
595 : }
596 : }
597 :
598 : // Range-specific subtyping
599 :
600 : // Lub(Range(x,y))->Is(T.Union(T.Integral32, T.OtherNumber))
601 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
602 124 : Type* type = *it;
603 124 : if (type->IsRange()) {
604 5 : Type* lub = BitsetType::NewForTesting(BitsetType::Lub(type));
605 10 : CHECK(lub->Is(T.PlainNumber));
606 : }
607 : }
608 :
609 :
610 : // Subtyping between concrete basic types
611 :
612 1 : CheckUnordered(T.Boolean, T.Null);
613 1 : CheckUnordered(T.Undefined, T.Null);
614 1 : CheckUnordered(T.Boolean, T.Undefined);
615 :
616 1 : CheckSub(T.SignedSmall, T.Number);
617 1 : CheckSub(T.Signed32, T.Number);
618 1 : CheckSubOrEqual(T.SignedSmall, T.Signed32);
619 1 : CheckUnordered(T.SignedSmall, T.MinusZero);
620 1 : CheckUnordered(T.Signed32, T.Unsigned32);
621 :
622 1 : CheckSub(T.UniqueName, T.Name);
623 1 : CheckSub(T.String, T.Name);
624 1 : CheckSub(T.InternalizedSeqString, T.InternalizedString);
625 1 : CheckSub(T.InternalizedNonSeqString, T.InternalizedString);
626 1 : CheckSub(T.InternalizedString, T.String);
627 1 : CheckSub(T.InternalizedString, T.UniqueName);
628 1 : CheckSub(T.InternalizedString, T.Name);
629 1 : CheckSub(T.OtherSeqString, T.OtherString);
630 1 : CheckSub(T.OtherNonSeqString, T.OtherString);
631 1 : CheckSub(T.OtherString, T.String);
632 1 : CheckSub(T.Symbol, T.UniqueName);
633 1 : CheckSub(T.Symbol, T.Name);
634 1 : CheckUnordered(T.String, T.UniqueName);
635 1 : CheckUnordered(T.String, T.Symbol);
636 1 : CheckUnordered(T.InternalizedString, T.Symbol);
637 :
638 1 : CheckSub(T.Object, T.Receiver);
639 1 : CheckSub(T.Proxy, T.Receiver);
640 1 : CheckSub(T.Array, T.Object);
641 1 : CheckSub(T.OtherObject, T.Object);
642 1 : CheckSub(T.OtherUndetectable, T.Object);
643 :
644 1 : CheckUnordered(T.Object, T.Proxy);
645 1 : CheckUnordered(T.Array, T.Undetectable);
646 1 : CheckUnordered(T.OtherObject, T.Undetectable);
647 :
648 : // Subtyping between concrete structural types
649 :
650 1 : CheckSub(T.SmiConstant, T.SignedSmall);
651 1 : CheckSub(T.SmiConstant, T.Signed32);
652 1 : CheckSub(T.SmiConstant, T.Number);
653 1 : CheckSub(T.ObjectConstant1, T.Object);
654 1 : CheckSub(T.ObjectConstant2, T.Object);
655 1 : CheckSub(T.ArrayConstant, T.Object);
656 1 : CheckSub(T.ArrayConstant, T.Array);
657 1 : CheckSub(T.ArrayConstant, T.Receiver);
658 1 : CheckSub(T.UninitializedConstant, T.Internal);
659 1 : CheckUnordered(T.ObjectConstant1, T.ObjectConstant2);
660 1 : CheckUnordered(T.ObjectConstant1, T.ArrayConstant);
661 1 : CheckUnordered(T.UninitializedConstant, T.Null);
662 1 : CheckUnordered(T.UninitializedConstant, T.Undefined);
663 1 : }
664 :
665 1 : void Maybe() {
666 : // T->Maybe(Any) iff T inhabited
667 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
668 124 : Type* type = *it;
669 248 : CHECK(type->Maybe(T.Any) == type->IsInhabited());
670 : }
671 :
672 : // T->Maybe(None) never
673 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
674 124 : Type* type = *it;
675 124 : CHECK(!type->Maybe(T.None));
676 : }
677 :
678 : // Reflexivity upto Inhabitation: T->Maybe(T) iff T inhabited
679 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
680 124 : Type* type = *it;
681 248 : CHECK(type->Maybe(type) == type->IsInhabited());
682 : }
683 :
684 : // Symmetry: T1->Maybe(T2) iff T2->Maybe(T1)
685 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
686 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
687 15376 : Type* type1 = *it1;
688 15376 : Type* type2 = *it2;
689 15376 : CHECK(type1->Maybe(type2) == type2->Maybe(type1));
690 : }
691 : }
692 :
693 : // T1->Maybe(T2) implies T1, T2 inhabited
694 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
695 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
696 15376 : Type* type1 = *it1;
697 15376 : Type* type2 = *it2;
698 31808 : CHECK(!type1->Maybe(type2) ||
699 : (type1->IsInhabited() && type2->IsInhabited()));
700 : }
701 : }
702 :
703 : // T1->Maybe(T2) implies Intersect(T1, T2) inhabited
704 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
705 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
706 15376 : Type* type1 = *it1;
707 15376 : Type* type2 = *it2;
708 15576 : Type* intersect12 = T.Intersect(type1, type2);
709 23592 : CHECK(!type1->Maybe(type2) || intersect12->IsInhabited());
710 : }
711 : }
712 :
713 : // T1->Is(T2) and T1 inhabited implies T1->Maybe(T2)
714 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
715 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
716 15376 : Type* type1 = *it1;
717 15376 : Type* type2 = *it2;
718 19631 : CHECK(!(type1->Is(type2) && type1->IsInhabited()) ||
719 : type1->Maybe(type2));
720 : }
721 : }
722 :
723 : // Constant(V1)->Maybe(Constant(V2)) iff V1 = V2
724 12 : for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
725 120 : for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
726 100 : Handle<i::Object> value1 = *vt1;
727 100 : Handle<i::Object> value2 = *vt2;
728 : Type* const_type1 = T.NewConstant(value1);
729 : Type* const_type2 = T.NewConstant(value2);
730 130 : if (const_type1->IsOtherNumberConstant() &&
731 : const_type2->IsOtherNumberConstant()) {
732 9 : CHECK(const_type1->Maybe(const_type2) ==
733 : (const_type1->AsOtherNumberConstant()->Value() ==
734 : const_type2->AsOtherNumberConstant()->Value()));
735 121 : } else if (const_type1->IsRange() && const_type2->IsRange()) {
736 9 : CHECK(Equal(const_type1, const_type2) ==
737 : ((const_type1->AsRange()->Min() ==
738 : const_type2->AsRange()->Min()) &&
739 : (const_type1->AsRange()->Max() ==
740 : const_type2->AsRange()->Max())));
741 : } else {
742 164 : CHECK(const_type1->Maybe(const_type2) == (*value1 == *value2));
743 : }
744 : }
745 : }
746 :
747 : // Basic types
748 1 : CheckDisjoint(T.Boolean, T.Null);
749 1 : CheckDisjoint(T.Undefined, T.Null);
750 1 : CheckDisjoint(T.Boolean, T.Undefined);
751 1 : CheckOverlap(T.SignedSmall, T.Number);
752 1 : CheckOverlap(T.NaN, T.Number);
753 1 : CheckDisjoint(T.Signed32, T.NaN);
754 1 : CheckOverlap(T.UniqueName, T.Name);
755 1 : CheckOverlap(T.InternalizedNonSeqString, T.InternalizedString);
756 1 : CheckOverlap(T.InternalizedSeqString, T.InternalizedString);
757 1 : CheckOverlap(T.OtherNonSeqString, T.OtherString);
758 1 : CheckOverlap(T.OtherSeqString, T.OtherString);
759 1 : CheckOverlap(T.String, T.Name);
760 1 : CheckOverlap(T.InternalizedString, T.String);
761 1 : CheckOverlap(T.InternalizedString, T.UniqueName);
762 1 : CheckOverlap(T.InternalizedString, T.Name);
763 1 : CheckOverlap(T.OtherString, T.String);
764 1 : CheckOverlap(T.Symbol, T.UniqueName);
765 1 : CheckOverlap(T.Symbol, T.Name);
766 1 : CheckOverlap(T.String, T.UniqueName);
767 1 : CheckDisjoint(T.String, T.Symbol);
768 1 : CheckDisjoint(T.InternalizedString, T.Symbol);
769 1 : CheckOverlap(T.Object, T.Receiver);
770 1 : CheckOverlap(T.OtherObject, T.Object);
771 1 : CheckOverlap(T.Proxy, T.Receiver);
772 1 : CheckDisjoint(T.Object, T.Proxy);
773 :
774 : // Structural types
775 1 : CheckOverlap(T.SmiConstant, T.SignedSmall);
776 1 : CheckOverlap(T.SmiConstant, T.Signed32);
777 1 : CheckOverlap(T.SmiConstant, T.Number);
778 1 : CheckOverlap(T.ObjectConstant1, T.Object);
779 1 : CheckOverlap(T.ObjectConstant2, T.Object);
780 1 : CheckOverlap(T.ArrayConstant, T.Object);
781 1 : CheckOverlap(T.ArrayConstant, T.Receiver);
782 1 : CheckOverlap(T.ObjectConstant1, T.ObjectConstant1);
783 1 : CheckDisjoint(T.ObjectConstant1, T.ObjectConstant2);
784 1 : CheckDisjoint(T.ObjectConstant1, T.ArrayConstant);
785 1 : }
786 :
787 1 : void Union1() {
788 : // Identity: Union(T, None) = T
789 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
790 124 : Type* type = *it;
791 61876 : Type* union_type = T.Union(type, T.None);
792 124 : CheckEqual(union_type, type);
793 : }
794 :
795 : // Domination: Union(T, Any) = Any
796 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
797 124 : Type* type = *it;
798 124 : Type* union_type = T.Union(type, T.Any);
799 124 : CheckEqual(union_type, T.Any);
800 : }
801 :
802 : // Idempotence: Union(T, T) = T
803 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
804 124 : Type* type = *it;
805 : Type* union_type = T.Union(type, type);
806 124 : CheckEqual(union_type, type);
807 : }
808 :
809 : // Commutativity: Union(T1, T2) = Union(T2, T1)
810 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
811 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
812 15376 : Type* type1 = *it1;
813 15376 : Type* type2 = *it2;
814 : Type* union12 = T.Union(type1, type2);
815 : Type* union21 = T.Union(type2, type1);
816 15376 : CheckEqual(union12, union21);
817 : }
818 : }
819 :
820 : // Associativity: Union(T1, Union(T2, T3)) = Union(Union(T1, T2), T3)
821 : // This does NOT hold! For example:
822 : // (Unsigned32 \/ Range(0,5)) \/ Range(-5,0) = Unsigned32 \/ Range(-5,0)
823 : // Unsigned32 \/ (Range(0,5) \/ Range(-5,0)) = Unsigned32 \/ Range(-5,5)
824 : /*
825 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
826 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
827 : for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
828 : Type* type1 = *it1;
829 : Type* type2 = *it2;
830 : Type* type3 = *it3;
831 : Type* union12 = T.Union(type1, type2);
832 : Type* union23 = T.Union(type2, type3);
833 : Type* union1_23 = T.Union(type1, union23);
834 : Type* union12_3 = T.Union(union12, type3);
835 : CheckEqual(union1_23, union12_3);
836 : }
837 : }
838 : }
839 : */
840 :
841 : // Meet: T1->Is(Union(T1, T2)) and T2->Is(Union(T1, T2))
842 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
843 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
844 15376 : Type* type1 = *it1;
845 15376 : Type* type2 = *it2;
846 : Type* union12 = T.Union(type1, type2);
847 15376 : CHECK(type1->Is(union12));
848 15376 : CHECK(type2->Is(union12));
849 : }
850 : }
851 :
852 : // Upper Boundedness: T1->Is(T2) implies Union(T1, T2) = T2
853 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
854 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
855 15376 : Type* type1 = *it1;
856 15376 : Type* type2 = *it2;
857 : Type* union12 = T.Union(type1, type2);
858 15376 : if (type1->Is(type2)) CheckEqual(union12, type2);
859 : }
860 : }
861 :
862 : // Monotonicity: T1->Is(T2) implies Union(T1, T3)->Is(Union(T2, T3))
863 : // This does NOT hold. For example:
864 : // Range(-5,-1) <= Signed32
865 : // Range(-5,-1) \/ Range(1,5) = Range(-5,5) </= Signed32 \/ Range(1,5)
866 : /*
867 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
868 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
869 : for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
870 : Type* type1 = *it1;
871 : Type* type2 = *it2;
872 : Type* type3 = *it3;
873 : Type* union13 = T.Union(type1, type3);
874 : Type* union23 = T.Union(type2, type3);
875 : CHECK(!type1->Is(type2) || union13->Is(union23));
876 : }
877 : }
878 : }
879 : */
880 1 : }
881 :
882 : void Union2() {
883 : // Monotonicity: T1->Is(T3) and T2->Is(T3) implies Union(T1, T2)->Is(T3)
884 : // This does NOT hold. For example:
885 : // Range(-2^33, -2^33) <= OtherNumber
886 : // Range(2^33, 2^33) <= OtherNumber
887 : // Range(-2^33, 2^33) </= OtherNumber
888 : /*
889 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
890 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
891 : for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
892 : Type* type1 = *it1;
893 : Type* type2 = *it2;
894 : Type* type3 = *it3;
895 : Type* union12 = T.Union(type1, type2);
896 : CHECK(!(type1->Is(type3) && type2->Is(type3)) || union12->Is(type3));
897 : }
898 : }
899 : }
900 : */
901 : }
902 :
903 1 : void Union3() {
904 : // Monotonicity: T1->Is(T2) or T1->Is(T3) implies T1->Is(Union(T2, T3))
905 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
906 124 : HandleScope scope(isolate);
907 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
908 976376 : for (TypeIterator it3 = it2; it3 != T.types.end(); ++it3) {
909 961000 : Type* type1 = *it1;
910 961000 : Type* type2 = *it2;
911 961000 : Type* type3 = *it3;
912 961000 : Type* union23 = T.Union(type2, type3);
913 2224600 : CHECK(!(type1->Is(type2) || type1->Is(type3)) || type1->Is(union23));
914 : }
915 : }
916 : }
917 1 : }
918 :
919 1 : void Union4() {
920 : // Constant-constant
921 22 : CheckSub(T.Union(T.ObjectConstant1, T.ObjectConstant2), T.Object);
922 2 : CheckOverlap(T.Union(T.ObjectConstant1, T.ArrayConstant), T.OtherObject);
923 2 : CheckOverlap(T.Union(T.ObjectConstant1, T.ArrayConstant), T.OtherObject);
924 : CheckDisjoint(
925 2 : T.Union(T.ObjectConstant1, T.ArrayConstant), T.Number);
926 :
927 : // Bitset-constant
928 : CheckSub(
929 3 : T.Union(T.ObjectConstant1, T.Signed32), T.Union(T.Object, T.Number));
930 2 : CheckSub(T.Union(T.ObjectConstant1, T.OtherObject), T.Object);
931 2 : CheckUnordered(T.Union(T.ObjectConstant1, T.String), T.OtherObject);
932 2 : CheckOverlap(T.Union(T.ObjectConstant1, T.String), T.Object);
933 2 : CheckDisjoint(T.Union(T.ObjectConstant1, T.String), T.Number);
934 :
935 : // Constant-union
936 : CheckEqual(
937 : T.Union(
938 : T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)),
939 4 : T.Union(T.ObjectConstant2, T.ObjectConstant1));
940 : CheckEqual(
941 : T.Union(
942 : T.Union(T.ArrayConstant, T.ObjectConstant2), T.ObjectConstant1),
943 : T.Union(
944 4 : T.ObjectConstant2, T.Union(T.ArrayConstant, T.ObjectConstant1)));
945 :
946 : // Union-union
947 : CheckEqual(
948 : T.Union(
949 : T.Union(T.ObjectConstant2, T.ObjectConstant1),
950 : T.Union(T.ObjectConstant1, T.ObjectConstant2)),
951 4 : T.Union(T.ObjectConstant2, T.ObjectConstant1));
952 1 : }
953 :
954 1 : void Intersect() {
955 : // Identity: Intersect(T, Any) = T
956 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
957 124 : Type* type = *it;
958 1953132 : Type* intersect_type = T.Intersect(type, T.Any);
959 124 : CheckEqual(intersect_type, type);
960 : }
961 :
962 : // Domination: Intersect(T, None) = None
963 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
964 124 : Type* type = *it;
965 124 : Type* intersect_type = T.Intersect(type, T.None);
966 124 : CheckEqual(intersect_type, T.None);
967 : }
968 :
969 : // Idempotence: Intersect(T, T) = T
970 126 : for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
971 124 : Type* type = *it;
972 : Type* intersect_type = T.Intersect(type, type);
973 124 : CheckEqual(intersect_type, type);
974 : }
975 :
976 : // Commutativity: Intersect(T1, T2) = Intersect(T2, T1)
977 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
978 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
979 15376 : Type* type1 = *it1;
980 15376 : Type* type2 = *it2;
981 : Type* intersect12 = T.Intersect(type1, type2);
982 : Type* intersect21 = T.Intersect(type2, type1);
983 15376 : CheckEqual(intersect12, intersect21);
984 : }
985 : }
986 :
987 : // Lower Boundedness: T1->Is(T2) implies Intersect(T1, T2) = T1
988 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
989 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
990 15376 : Type* type1 = *it1;
991 15376 : Type* type2 = *it2;
992 : Type* intersect12 = T.Intersect(type1, type2);
993 15376 : if (type1->Is(type2)) CheckEqual(intersect12, type1);
994 : }
995 : }
996 :
997 : // Monotonicity: T1->Is(T2) and T1->Is(T3) implies T1->Is(Intersect(T2, T3))
998 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
999 124 : HandleScope scope(isolate);
1000 15624 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1001 1937376 : for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1002 1906624 : Type* type1 = *it1;
1003 1906624 : Type* type2 = *it2;
1004 1906624 : Type* type3 = *it3;
1005 : Type* intersect23 = T.Intersect(type2, type3);
1006 2610405 : CHECK(!(type1->Is(type2) && type1->Is(type3)) ||
1007 : type1->Is(intersect23));
1008 : }
1009 : }
1010 : }
1011 :
1012 : // Constant-union
1013 : CheckEqual(
1014 : T.Intersect(
1015 : T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)),
1016 3 : T.ObjectConstant1);
1017 : CheckEqual(
1018 : T.Intersect(T.SmiConstant, T.Union(T.Number, T.ObjectConstant2)),
1019 3 : T.SmiConstant);
1020 :
1021 : // Union-union
1022 : CheckEqual(
1023 : T.Intersect(
1024 : T.Union(T.ObjectConstant2, T.ObjectConstant1),
1025 : T.Union(T.ObjectConstant1, T.ObjectConstant2)),
1026 4 : T.Union(T.ObjectConstant2, T.ObjectConstant1));
1027 1 : }
1028 :
1029 : void Distributivity() {
1030 : // Union(T1, Intersect(T2, T3)) = Intersect(Union(T1, T2), Union(T1, T3))
1031 : // This does NOT hold. For example:
1032 : // Untagged \/ (Untagged /\ Class(../Tagged)) = Untagged \/ Class(../Tagged)
1033 : // (Untagged \/ Untagged) /\ (Untagged \/ Class(../Tagged)) =
1034 : // Untagged /\ (Untagged \/ Class(../Tagged)) = Untagged
1035 : // because Untagged <= Untagged \/ Class(../Tagged)
1036 : /*
1037 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1038 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1039 : for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1040 : Type* type1 = *it1;
1041 : Type* type2 = *it2;
1042 : Type* type3 = *it3;
1043 : Type* union12 = T.Union(type1, type2);
1044 : Type* union13 = T.Union(type1, type3);
1045 : Type* intersect23 = T.Intersect(type2, type3);
1046 : Type* union1_23 = T.Union(type1, intersect23);
1047 : Type* intersect12_13 = T.Intersect(union12, union13);
1048 : CHECK(Equal(union1_23, intersect12_13));
1049 : }
1050 : }
1051 : }
1052 : */
1053 :
1054 : // Intersect(T1, Union(T2, T3)) = Union(Intersect(T1, T2), Intersect(T1,T3))
1055 : // This does NOT hold. For example:
1056 : // Untagged /\ (Untagged \/ Class(../Tagged)) = Untagged
1057 : // (Untagged /\ Untagged) \/ (Untagged /\ Class(../Tagged)) =
1058 : // Untagged \/ Class(../Tagged)
1059 : /*
1060 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1061 : for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1062 : for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1063 : Type* type1 = *it1;
1064 : Type* type2 = *it2;
1065 : Type* type3 = *it3;
1066 : Type* intersect12 = T.Intersect(type1, type2);
1067 : Type* intersect13 = T.Intersect(type1, type3);
1068 : Type* union23 = T.Union(type2, type3);
1069 : Type* intersect1_23 = T.Intersect(type1, union23);
1070 : Type* union12_13 = T.Union(intersect12, intersect13);
1071 : CHECK(Equal(intersect1_23, union12_13));
1072 : }
1073 : }
1074 : }
1075 : */
1076 : }
1077 :
1078 1 : void GetRange() {
1079 : // GetRange(Range(a, b)) = Range(a, b).
1080 126 : for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1081 124 : Type* type1 = *it1;
1082 124 : if (type1->IsRange()) {
1083 15 : RangeType* range = type1->GetRange()->AsRange();
1084 10 : CHECK(type1->Min() == range->Min());
1085 10 : CHECK(type1->Max() == range->Max());
1086 : }
1087 : }
1088 1 : }
1089 : };
1090 :
1091 : } // namespace
1092 :
1093 23719 : TEST(IsSomeType) { Tests().IsSomeType(); }
1094 :
1095 23719 : TEST(BitsetType) { Tests().Bitset(); }
1096 :
1097 23719 : TEST(ConstantType) { Tests().Constant(); }
1098 :
1099 23719 : TEST(RangeType) { Tests().Range(); }
1100 :
1101 23719 : TEST(Of) { Tests().Of(); }
1102 :
1103 23719 : TEST(MinMax) { Tests().MinMax(); }
1104 :
1105 23719 : TEST(BitsetGlb) { Tests().BitsetGlb(); }
1106 :
1107 23719 : TEST(BitsetLub) { Tests().BitsetLub(); }
1108 :
1109 23719 : TEST(Is1) { Tests().Is1(); }
1110 :
1111 23719 : TEST(Is2) { Tests().Is2(); }
1112 :
1113 23719 : TEST(Maybe) { Tests().Maybe(); }
1114 :
1115 23719 : TEST(Union1) { Tests().Union1(); }
1116 :
1117 23719 : TEST(Union2) { Tests().Union2(); }
1118 :
1119 23719 : TEST(Union3) { Tests().Union3(); }
1120 :
1121 23719 : TEST(Union4) { Tests().Union4(); }
1122 :
1123 23719 : TEST(Intersect) { Tests().Intersect(); }
1124 :
1125 23719 : TEST(Distributivity) { Tests().Distributivity(); }
1126 :
1127 23719 : TEST(GetRange) { Tests().GetRange(); }
1128 :
1129 : } // namespace compiler
1130 : } // namespace internal
1131 71154 : } // namespace v8
|
