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