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/hydrogen-types.h"
8#include "src/isolate-inl.h"
9#include "src/types.h"
10#include "test/cctest/cctest.h"
11
12using namespace v8::internal;
13
14// Testing auxiliaries (breaking the Type abstraction).
15typedef uint32_t bitset;
16
17struct ZoneRep {
18  typedef void* Struct;
19
20  static bool IsStruct(Type* t, int tag) {
21    return !IsBitset(t) && reinterpret_cast<intptr_t>(AsStruct(t)[0]) == tag;
22  }
23  static bool IsBitset(Type* t) { return reinterpret_cast<uintptr_t>(t) & 1; }
24  static bool IsUnion(Type* t) { return IsStruct(t, 6); }
25
26  static Struct* AsStruct(Type* t) {
27    return reinterpret_cast<Struct*>(t);
28  }
29  static bitset AsBitset(Type* t) {
30    return static_cast<bitset>(reinterpret_cast<uintptr_t>(t) ^ 1u);
31  }
32  static Struct* AsUnion(Type* t) {
33    return AsStruct(t);
34  }
35  static int Length(Struct* structured) {
36    return static_cast<int>(reinterpret_cast<intptr_t>(structured[1]));
37  }
38
39  static Zone* ToRegion(Zone* zone, Isolate* isolate) { return zone; }
40
41  struct BitsetType : Type::BitsetType {
42    using Type::BitsetType::New;
43    using Type::BitsetType::Glb;
44    using Type::BitsetType::Lub;
45    using Type::BitsetType::IsInhabited;
46  };
47};
48
49
50struct HeapRep {
51  typedef FixedArray Struct;
52
53  static bool IsStruct(Handle<HeapType> t, int tag) {
54    return t->IsFixedArray() && Smi::cast(AsStruct(t)->get(0))->value() == tag;
55  }
56  static bool IsBitset(Handle<HeapType> t) { return t->IsSmi(); }
57  static bool IsUnion(Handle<HeapType> t) { return IsStruct(t, 6); }
58
59  static Struct* AsStruct(Handle<HeapType> t) { return FixedArray::cast(*t); }
60  static bitset AsBitset(Handle<HeapType> t) {
61    return static_cast<bitset>(reinterpret_cast<uintptr_t>(*t));
62  }
63  static Struct* AsUnion(Handle<HeapType> t) { return AsStruct(t); }
64  static int Length(Struct* structured) { return structured->length() - 1; }
65
66  static Isolate* ToRegion(Zone* zone, Isolate* isolate) { return isolate; }
67
68  struct BitsetType : HeapType::BitsetType {
69    using HeapType::BitsetType::New;
70    using HeapType::BitsetType::Glb;
71    using HeapType::BitsetType::Lub;
72    using HeapType::BitsetType::IsInhabited;
73    static bitset Glb(Handle<HeapType> type) { return Glb(*type); }
74    static bitset Lub(Handle<HeapType> type) { return Lub(*type); }
75  };
76};
77
78
79template<class Type, class TypeHandle, class Region>
80class Types {
81 public:
82  Types(Region* region, Isolate* isolate)
83      : region_(region), rng_(isolate->random_number_generator()) {
84    #define DECLARE_TYPE(name, value) \
85      name = Type::name(region); \
86      types.push_back(name);
87    PROPER_BITSET_TYPE_LIST(DECLARE_TYPE)
88    #undef DECLARE_TYPE
89
90    object_map = isolate->factory()->NewMap(
91        JS_OBJECT_TYPE, JSObject::kHeaderSize);
92    array_map = isolate->factory()->NewMap(
93        JS_ARRAY_TYPE, JSArray::kSize);
94    number_map = isolate->factory()->NewMap(
95        HEAP_NUMBER_TYPE, HeapNumber::kSize);
96    uninitialized_map = isolate->factory()->uninitialized_map();
97    ObjectClass = Type::Class(object_map, region);
98    ArrayClass = Type::Class(array_map, region);
99    NumberClass = Type::Class(number_map, region);
100    UninitializedClass = Type::Class(uninitialized_map, region);
101
102    maps.push_back(object_map);
103    maps.push_back(array_map);
104    maps.push_back(uninitialized_map);
105    for (MapVector::iterator it = maps.begin(); it != maps.end(); ++it) {
106      types.push_back(Type::Class(*it, region));
107    }
108
109    smi = handle(Smi::FromInt(666), isolate);
110    signed32 = isolate->factory()->NewHeapNumber(0x40000000);
111    object1 = isolate->factory()->NewJSObjectFromMap(object_map);
112    object2 = isolate->factory()->NewJSObjectFromMap(object_map);
113    array = isolate->factory()->NewJSArray(20);
114    uninitialized = isolate->factory()->uninitialized_value();
115    SmiConstant = Type::Constant(smi, region);
116    Signed32Constant = Type::Constant(signed32, region);
117    ObjectConstant1 = Type::Constant(object1, region);
118    ObjectConstant2 = Type::Constant(object2, region);
119    ArrayConstant = Type::Constant(array, region);
120    UninitializedConstant = Type::Constant(uninitialized, region);
121
122    values.push_back(smi);
123    values.push_back(signed32);
124    values.push_back(object1);
125    values.push_back(object2);
126    values.push_back(array);
127    values.push_back(uninitialized);
128    for (ValueVector::iterator it = values.begin(); it != values.end(); ++it) {
129      types.push_back(Type::Constant(*it, region));
130    }
131
132    integers.push_back(isolate->factory()->NewNumber(-V8_INFINITY));
133    integers.push_back(isolate->factory()->NewNumber(+V8_INFINITY));
134    integers.push_back(isolate->factory()->NewNumber(-rng_->NextInt(10)));
135    integers.push_back(isolate->factory()->NewNumber(+rng_->NextInt(10)));
136    for (int i = 0; i < 10; ++i) {
137      double x = rng_->NextInt();
138      integers.push_back(isolate->factory()->NewNumber(x));
139      x *= rng_->NextInt();
140      if (!IsMinusZero(x)) integers.push_back(isolate->factory()->NewNumber(x));
141    }
142
143    NumberArray = Type::Array(Number, region);
144    StringArray = Type::Array(String, region);
145    AnyArray = Type::Array(Any, region);
146
147    SignedFunction1 = Type::Function(SignedSmall, SignedSmall, region);
148    NumberFunction1 = Type::Function(Number, Number, region);
149    NumberFunction2 = Type::Function(Number, Number, Number, region);
150    MethodFunction = Type::Function(String, Object, 0, region);
151
152    for (int i = 0; i < 30; ++i) {
153      types.push_back(Fuzz());
154    }
155  }
156
157  Handle<i::Map> object_map;
158  Handle<i::Map> array_map;
159  Handle<i::Map> number_map;
160  Handle<i::Map> uninitialized_map;
161
162  Handle<i::Smi> smi;
163  Handle<i::HeapNumber> signed32;
164  Handle<i::JSObject> object1;
165  Handle<i::JSObject> object2;
166  Handle<i::JSArray> array;
167  Handle<i::Oddball> uninitialized;
168
169  #define DECLARE_TYPE(name, value) TypeHandle name;
170  BITSET_TYPE_LIST(DECLARE_TYPE)
171  #undef DECLARE_TYPE
172
173  TypeHandle ObjectClass;
174  TypeHandle ArrayClass;
175  TypeHandle NumberClass;
176  TypeHandle UninitializedClass;
177
178  TypeHandle SmiConstant;
179  TypeHandle Signed32Constant;
180  TypeHandle ObjectConstant1;
181  TypeHandle ObjectConstant2;
182  TypeHandle ArrayConstant;
183  TypeHandle UninitializedConstant;
184
185  TypeHandle NumberArray;
186  TypeHandle StringArray;
187  TypeHandle AnyArray;
188
189  TypeHandle SignedFunction1;
190  TypeHandle NumberFunction1;
191  TypeHandle NumberFunction2;
192  TypeHandle MethodFunction;
193
194  typedef std::vector<TypeHandle> TypeVector;
195  typedef std::vector<Handle<i::Map> > MapVector;
196  typedef std::vector<Handle<i::Object> > ValueVector;
197
198  TypeVector types;
199  MapVector maps;
200  ValueVector values;
201  ValueVector integers;  // "Integer" values used for range limits.
202
203  TypeHandle Of(Handle<i::Object> value) {
204    return Type::Of(value, region_);
205  }
206
207  TypeHandle NowOf(Handle<i::Object> value) {
208    return Type::NowOf(value, region_);
209  }
210
211  TypeHandle Class(Handle<i::Map> map) {
212    return Type::Class(map, region_);
213  }
214
215  TypeHandle Constant(Handle<i::Object> value) {
216    return Type::Constant(value, region_);
217  }
218
219  TypeHandle Range(Handle<i::Object> min, Handle<i::Object> max) {
220    return Type::Range(min, max, region_);
221  }
222
223  TypeHandle Context(TypeHandle outer) {
224    return Type::Context(outer, region_);
225  }
226
227  TypeHandle Array1(TypeHandle element) {
228    return Type::Array(element, region_);
229  }
230
231  TypeHandle Function0(TypeHandle result, TypeHandle receiver) {
232    return Type::Function(result, receiver, 0, region_);
233  }
234
235  TypeHandle Function1(TypeHandle result, TypeHandle receiver, TypeHandle arg) {
236    TypeHandle type = Type::Function(result, receiver, 1, region_);
237    type->AsFunction()->InitParameter(0, arg);
238    return type;
239  }
240
241  TypeHandle Function2(TypeHandle result, TypeHandle arg1, TypeHandle arg2) {
242    return Type::Function(result, arg1, arg2, region_);
243  }
244
245  TypeHandle Union(TypeHandle t1, TypeHandle t2) {
246    return Type::Union(t1, t2, region_);
247  }
248  TypeHandle Intersect(TypeHandle t1, TypeHandle t2) {
249    return Type::Intersect(t1, t2, region_);
250  }
251
252  template<class Type2, class TypeHandle2>
253  TypeHandle Convert(TypeHandle2 t) {
254    return Type::template Convert<Type2>(t, region_);
255  }
256
257  TypeHandle Random() {
258    return types[rng_->NextInt(static_cast<int>(types.size()))];
259  }
260
261  TypeHandle Fuzz(int depth = 4) {
262    switch (rng_->NextInt(depth == 0 ? 3 : 20)) {
263      case 0: {  // bitset
264        int n = 0
265        #define COUNT_BITSET_TYPES(type, value) + 1
266        PROPER_BITSET_TYPE_LIST(COUNT_BITSET_TYPES)
267        #undef COUNT_BITSET_TYPES
268        ;
269        int i = rng_->NextInt(n);
270        #define PICK_BITSET_TYPE(type, value) \
271          if (i-- == 0) return Type::type(region_);
272        PROPER_BITSET_TYPE_LIST(PICK_BITSET_TYPE)
273        #undef PICK_BITSET_TYPE
274        UNREACHABLE();
275      }
276      case 1: {  // class
277        int i = rng_->NextInt(static_cast<int>(maps.size()));
278        return Type::Class(maps[i], region_);
279      }
280      case 2: {  // constant
281        int i = rng_->NextInt(static_cast<int>(values.size()));
282        return Type::Constant(values[i], region_);
283      }
284      case 3: {  // range
285        int i = rng_->NextInt(static_cast<int>(integers.size()));
286        int j = rng_->NextInt(static_cast<int>(integers.size()));
287        i::Handle<i::Object> min = integers[i];
288        i::Handle<i::Object> max = integers[j];
289        if (min->Number() > max->Number()) std::swap(min, max);
290        return Type::Range(min, max, region_);
291      }
292      case 4: {  // context
293        int depth = rng_->NextInt(3);
294        TypeHandle type = Type::Internal(region_);
295        for (int i = 0; i < depth; ++i) type = Type::Context(type, region_);
296        return type;
297      }
298      case 5: {  // array
299        TypeHandle element = Fuzz(depth / 2);
300        return Type::Array(element, region_);
301      }
302      case 6:
303      case 7: {  // function
304        TypeHandle result = Fuzz(depth / 2);
305        TypeHandle receiver = Fuzz(depth / 2);
306        int arity = rng_->NextInt(3);
307        TypeHandle type = Type::Function(result, receiver, arity, region_);
308        for (int i = 0; i < type->AsFunction()->Arity(); ++i) {
309          TypeHandle parameter = Fuzz(depth / 2);
310          type->AsFunction()->InitParameter(i, parameter);
311        }
312        return type;
313      }
314      default: {  // union
315        int n = rng_->NextInt(10);
316        TypeHandle type = None;
317        for (int i = 0; i < n; ++i) {
318          TypeHandle operand = Fuzz(depth - 1);
319          type = Type::Union(type, operand, region_);
320        }
321        return type;
322      }
323    }
324    UNREACHABLE();
325  }
326
327  Region* region() { return region_; }
328
329 private:
330  Region* region_;
331  v8::base::RandomNumberGenerator* rng_;
332};
333
334
335template<class Type, class TypeHandle, class Region, class Rep>
336struct Tests : Rep {
337  typedef Types<Type, TypeHandle, Region> TypesInstance;
338  typedef typename TypesInstance::TypeVector::iterator TypeIterator;
339  typedef typename TypesInstance::MapVector::iterator MapIterator;
340  typedef typename TypesInstance::ValueVector::iterator ValueIterator;
341
342  Isolate* isolate;
343  HandleScope scope;
344  Zone zone;
345  TypesInstance T;
346
347  Tests() :
348      isolate(CcTest::i_isolate()),
349      scope(isolate),
350      zone(isolate),
351      T(Rep::ToRegion(&zone, isolate), isolate) {
352  }
353
354  bool Equal(TypeHandle type1, TypeHandle type2) {
355    return
356        type1->Equals(type2) &&
357        this->IsBitset(type1) == this->IsBitset(type2) &&
358        this->IsUnion(type1) == this->IsUnion(type2) &&
359        type1->NumClasses() == type2->NumClasses() &&
360        type1->NumConstants() == type2->NumConstants() &&
361        (!this->IsBitset(type1) ||
362          this->AsBitset(type1) == this->AsBitset(type2)) &&
363        (!this->IsUnion(type1) ||
364          this->Length(this->AsUnion(type1)) ==
365              this->Length(this->AsUnion(type2)));
366  }
367
368  void CheckEqual(TypeHandle type1, TypeHandle type2) {
369    CHECK(Equal(type1, type2));
370  }
371
372  void CheckSub(TypeHandle type1, TypeHandle type2) {
373    CHECK(type1->Is(type2));
374    CHECK(!type2->Is(type1));
375    if (this->IsBitset(type1) && this->IsBitset(type2)) {
376      CHECK(this->AsBitset(type1) != this->AsBitset(type2));
377    }
378  }
379
380  void CheckUnordered(TypeHandle type1, TypeHandle type2) {
381    CHECK(!type1->Is(type2));
382    CHECK(!type2->Is(type1));
383    if (this->IsBitset(type1) && this->IsBitset(type2)) {
384      CHECK(this->AsBitset(type1) != this->AsBitset(type2));
385    }
386  }
387
388  void CheckOverlap(TypeHandle type1, TypeHandle type2) {
389    CHECK(type1->Maybe(type2));
390    CHECK(type2->Maybe(type1));
391  }
392
393  void CheckDisjoint(TypeHandle type1, TypeHandle type2) {
394    CHECK(!type1->Is(type2));
395    CHECK(!type2->Is(type1));
396    CHECK(!type1->Maybe(type2));
397    CHECK(!type2->Maybe(type1));
398  }
399
400  void IsSomeType() {
401    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
402      TypeHandle t = *it;
403      CHECK(1 ==
404          this->IsBitset(t) + t->IsClass() + t->IsConstant() + t->IsRange() +
405          this->IsUnion(t) + t->IsArray() + t->IsFunction() + t->IsContext());
406    }
407  }
408
409  void Bitset() {
410    // None and Any are bitsets.
411    CHECK(this->IsBitset(T.None));
412    CHECK(this->IsBitset(T.Any));
413
414    CHECK(bitset(0) == this->AsBitset(T.None));
415    CHECK(bitset(0xfffffffeu) == this->AsBitset(T.Any));
416
417    // Union(T1, T2) is bitset for bitsets T1,T2
418    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
419      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
420        TypeHandle type1 = *it1;
421        TypeHandle type2 = *it2;
422        TypeHandle union12 = T.Union(type1, type2);
423        CHECK(!(this->IsBitset(type1) && this->IsBitset(type2)) ||
424              this->IsBitset(union12));
425      }
426    }
427
428    // Intersect(T1, T2) is bitset for bitsets T1,T2
429    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
430      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
431        TypeHandle type1 = *it1;
432        TypeHandle type2 = *it2;
433        TypeHandle intersect12 = T.Intersect(type1, type2);
434        CHECK(!(this->IsBitset(type1) && this->IsBitset(type2)) ||
435              this->IsBitset(intersect12));
436      }
437    }
438
439    // Union(T1, T2) is bitset if T2 is bitset and T1->Is(T2)
440    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
441      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
442        TypeHandle type1 = *it1;
443        TypeHandle type2 = *it2;
444        TypeHandle union12 = T.Union(type1, type2);
445        CHECK(!(this->IsBitset(type2) && type1->Is(type2)) ||
446              this->IsBitset(union12));
447      }
448    }
449
450    // Union(T1, T2) is bitwise disjunction for bitsets T1,T2
451    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
452      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
453        TypeHandle type1 = *it1;
454        TypeHandle type2 = *it2;
455        TypeHandle union12 = T.Union(type1, type2);
456        if (this->IsBitset(type1) && this->IsBitset(type2)) {
457          CHECK(
458              (this->AsBitset(type1) | this->AsBitset(type2)) ==
459              this->AsBitset(union12));
460        }
461      }
462    }
463
464    // Intersect(T1, T2) is bitwise conjunction for bitsets T1,T2 (modulo None)
465    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
466      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
467        TypeHandle type1 = *it1;
468        TypeHandle type2 = *it2;
469        TypeHandle intersect12 = T.Intersect(type1, type2);
470        if (this->IsBitset(type1) && this->IsBitset(type2)) {
471          bitset bits = this->AsBitset(type1) & this->AsBitset(type2);
472          CHECK(
473              (Rep::BitsetType::IsInhabited(bits) ? bits : 0) ==
474              this->AsBitset(intersect12));
475        }
476      }
477    }
478  }
479
480  void Class() {
481    // Constructor
482    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
483      Handle<i::Map> map = *mt;
484      TypeHandle type = T.Class(map);
485      CHECK(type->IsClass());
486    }
487
488    // Map attribute
489    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
490      Handle<i::Map> map = *mt;
491      TypeHandle type = T.Class(map);
492      CHECK(*map == *type->AsClass()->Map());
493    }
494
495    // Functionality & Injectivity: Class(M1) = Class(M2) iff M1 = M2
496    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
497      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
498        Handle<i::Map> map1 = *mt1;
499        Handle<i::Map> map2 = *mt2;
500        TypeHandle type1 = T.Class(map1);
501        TypeHandle type2 = T.Class(map2);
502        CHECK(Equal(type1, type2) == (*map1 == *map2));
503      }
504    }
505  }
506
507  void Constant() {
508    // Constructor
509    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
510      Handle<i::Object> value = *vt;
511      TypeHandle type = T.Constant(value);
512      CHECK(type->IsConstant());
513    }
514
515    // Value attribute
516    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
517      Handle<i::Object> value = *vt;
518      TypeHandle type = T.Constant(value);
519      CHECK(*value == *type->AsConstant()->Value());
520    }
521
522    // Functionality & Injectivity: Constant(V1) = Constant(V2) iff V1 = V2
523    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
524      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
525        Handle<i::Object> value1 = *vt1;
526        Handle<i::Object> value2 = *vt2;
527        TypeHandle type1 = T.Constant(value1);
528        TypeHandle type2 = T.Constant(value2);
529        CHECK(Equal(type1, type2) == (*value1 == *value2));
530      }
531    }
532
533    // Typing of numbers
534    Factory* fac = isolate->factory();
535    CHECK(T.Constant(fac->NewNumber(0))->Is(T.UnsignedSmall));
536    CHECK(T.Constant(fac->NewNumber(1))->Is(T.UnsignedSmall));
537    CHECK(T.Constant(fac->NewNumber(0x3fffffff))->Is(T.UnsignedSmall));
538    CHECK(T.Constant(fac->NewNumber(-1))->Is(T.OtherSignedSmall));
539    CHECK(T.Constant(fac->NewNumber(-0x3fffffff))->Is(T.OtherSignedSmall));
540    CHECK(T.Constant(fac->NewNumber(-0x40000000))->Is(T.OtherSignedSmall));
541    if (SmiValuesAre31Bits()) {
542      CHECK(T.Constant(fac->NewNumber(0x40000000))->Is(T.OtherUnsigned31));
543      CHECK(T.Constant(fac->NewNumber(0x7fffffff))->Is(T.OtherUnsigned31));
544      CHECK(T.Constant(fac->NewNumber(-0x40000001))->Is(T.OtherSigned32));
545      CHECK(T.Constant(fac->NewNumber(-0x7fffffff))->Is(T.OtherSigned32));
546      CHECK(T.Constant(fac->NewNumber(-0x7fffffff-1))->Is(T.OtherSigned32));
547    } else {
548      CHECK(SmiValuesAre32Bits());
549      CHECK(T.Constant(fac->NewNumber(0x40000000))->Is(T.UnsignedSmall));
550      CHECK(T.Constant(fac->NewNumber(0x7fffffff))->Is(T.UnsignedSmall));
551      CHECK(!T.Constant(fac->NewNumber(0x40000000))->Is(T.OtherUnsigned31));
552      CHECK(!T.Constant(fac->NewNumber(0x7fffffff))->Is(T.OtherUnsigned31));
553      CHECK(T.Constant(fac->NewNumber(-0x40000001))->Is(T.OtherSignedSmall));
554      CHECK(T.Constant(fac->NewNumber(-0x7fffffff))->Is(T.OtherSignedSmall));
555      CHECK(T.Constant(fac->NewNumber(-0x7fffffff-1))->Is(T.OtherSignedSmall));
556      CHECK(!T.Constant(fac->NewNumber(-0x40000001))->Is(T.OtherSigned32));
557      CHECK(!T.Constant(fac->NewNumber(-0x7fffffff))->Is(T.OtherSigned32));
558      CHECK(!T.Constant(fac->NewNumber(-0x7fffffff-1))->Is(T.OtherSigned32));
559    }
560    CHECK(T.Constant(fac->NewNumber(0x80000000u))->Is(T.OtherUnsigned32));
561    CHECK(T.Constant(fac->NewNumber(0xffffffffu))->Is(T.OtherUnsigned32));
562    CHECK(T.Constant(fac->NewNumber(0xffffffffu+1.0))->Is(T.OtherNumber));
563    CHECK(T.Constant(fac->NewNumber(-0x7fffffff-2.0))->Is(T.OtherNumber));
564    CHECK(T.Constant(fac->NewNumber(0.1))->Is(T.OtherNumber));
565    CHECK(T.Constant(fac->NewNumber(-10.1))->Is(T.OtherNumber));
566    CHECK(T.Constant(fac->NewNumber(10e60))->Is(T.OtherNumber));
567    CHECK(T.Constant(fac->NewNumber(-1.0*0.0))->Is(T.MinusZero));
568    CHECK(T.Constant(fac->NewNumber(v8::base::OS::nan_value()))->Is(T.NaN));
569    CHECK(T.Constant(fac->NewNumber(V8_INFINITY))->Is(T.OtherNumber));
570    CHECK(T.Constant(fac->NewNumber(-V8_INFINITY))->Is(T.OtherNumber));
571  }
572
573  void Range() {
574    // Constructor
575    for (ValueIterator i = T.integers.begin(); i != T.integers.end(); ++i) {
576      for (ValueIterator j = T.integers.begin(); j != T.integers.end(); ++j) {
577        i::Handle<i::Object> min = *i;
578        i::Handle<i::Object> max = *j;
579        if (min->Number() > max->Number()) std::swap(min, max);
580        TypeHandle type = T.Range(min, max);
581        CHECK(type->IsRange());
582      }
583    }
584
585    // Range attributes
586    for (ValueIterator i = T.integers.begin(); i != T.integers.end(); ++i) {
587      for (ValueIterator j = T.integers.begin(); j != T.integers.end(); ++j) {
588        i::Handle<i::Object> min = *i;
589        i::Handle<i::Object> max = *j;
590        if (min->Number() > max->Number()) std::swap(min, max);
591        TypeHandle type = T.Range(min, max);
592        CHECK(*min == *type->AsRange()->Min());
593        CHECK(*max == *type->AsRange()->Max());
594      }
595    }
596
597    // Functionality & Injectivity:
598    // Range(min1, max1) = Range(min2, max2) <=> min1 = min2 /\ max1 = max2
599    for (ValueIterator i1 = T.integers.begin();
600        i1 != T.integers.end(); ++i1) {
601      for (ValueIterator j1 = T.integers.begin();
602          j1 != T.integers.end(); ++j1) {
603        for (ValueIterator i2 = T.integers.begin();
604            i2 != T.integers.end(); ++i2) {
605          for (ValueIterator j2 = T.integers.begin();
606              j2 != T.integers.end(); ++j2) {
607            i::Handle<i::Object> min1 = *i1;
608            i::Handle<i::Object> max1 = *j1;
609            i::Handle<i::Object> min2 = *i2;
610            i::Handle<i::Object> max2 = *j2;
611            if (min1->Number() > max1->Number()) std::swap(min1, max1);
612            if (min2->Number() > max2->Number()) std::swap(min2, max2);
613            TypeHandle type1 = T.Range(min1, max1);
614            TypeHandle type2 = T.Range(min2, max2);
615            CHECK(Equal(type1, type2) == (*min1 == *min2 && *max1 == *max2));
616          }
617        }
618      }
619    }
620  }
621
622  void Array() {
623    // Constructor
624    for (int i = 0; i < 20; ++i) {
625      TypeHandle type = T.Random();
626      TypeHandle array = T.Array1(type);
627      CHECK(array->IsArray());
628    }
629
630    // Attributes
631    for (int i = 0; i < 20; ++i) {
632      TypeHandle type = T.Random();
633      TypeHandle array = T.Array1(type);
634      CheckEqual(type, array->AsArray()->Element());
635    }
636
637    // Functionality & Injectivity: Array(T1) = Array(T2) iff T1 = T2
638    for (int i = 0; i < 20; ++i) {
639      for (int j = 0; j < 20; ++j) {
640        TypeHandle type1 = T.Random();
641        TypeHandle type2 = T.Random();
642        TypeHandle array1 = T.Array1(type1);
643        TypeHandle array2 = T.Array1(type2);
644        CHECK(Equal(array1, array2) == Equal(type1, type2));
645      }
646    }
647  }
648
649  void Function() {
650    // Constructors
651    for (int i = 0; i < 20; ++i) {
652      for (int j = 0; j < 20; ++j) {
653        for (int k = 0; k < 20; ++k) {
654          TypeHandle type1 = T.Random();
655          TypeHandle type2 = T.Random();
656          TypeHandle type3 = T.Random();
657          TypeHandle function0 = T.Function0(type1, type2);
658          TypeHandle function1 = T.Function1(type1, type2, type3);
659          TypeHandle function2 = T.Function2(type1, type2, type3);
660          CHECK(function0->IsFunction());
661          CHECK(function1->IsFunction());
662          CHECK(function2->IsFunction());
663        }
664      }
665    }
666
667    // Attributes
668    for (int i = 0; i < 20; ++i) {
669      for (int j = 0; j < 20; ++j) {
670        for (int k = 0; k < 20; ++k) {
671          TypeHandle type1 = T.Random();
672          TypeHandle type2 = T.Random();
673          TypeHandle type3 = T.Random();
674          TypeHandle function0 = T.Function0(type1, type2);
675          TypeHandle function1 = T.Function1(type1, type2, type3);
676          TypeHandle function2 = T.Function2(type1, type2, type3);
677          CHECK_EQ(0, function0->AsFunction()->Arity());
678          CHECK_EQ(1, function1->AsFunction()->Arity());
679          CHECK_EQ(2, function2->AsFunction()->Arity());
680          CheckEqual(type1, function0->AsFunction()->Result());
681          CheckEqual(type1, function1->AsFunction()->Result());
682          CheckEqual(type1, function2->AsFunction()->Result());
683          CheckEqual(type2, function0->AsFunction()->Receiver());
684          CheckEqual(type2, function1->AsFunction()->Receiver());
685          CheckEqual(T.Any, function2->AsFunction()->Receiver());
686          CheckEqual(type3, function1->AsFunction()->Parameter(0));
687          CheckEqual(type2, function2->AsFunction()->Parameter(0));
688          CheckEqual(type3, function2->AsFunction()->Parameter(1));
689        }
690      }
691    }
692
693    // Functionality & Injectivity: Function(Ts1) = Function(Ts2) iff Ts1 = Ts2
694    for (int i = 0; i < 20; ++i) {
695      for (int j = 0; j < 20; ++j) {
696        for (int k = 0; k < 20; ++k) {
697          TypeHandle type1 = T.Random();
698          TypeHandle type2 = T.Random();
699          TypeHandle type3 = T.Random();
700          TypeHandle function01 = T.Function0(type1, type2);
701          TypeHandle function02 = T.Function0(type1, type3);
702          TypeHandle function03 = T.Function0(type3, type2);
703          TypeHandle function11 = T.Function1(type1, type2, type2);
704          TypeHandle function12 = T.Function1(type1, type2, type3);
705          TypeHandle function21 = T.Function2(type1, type2, type2);
706          TypeHandle function22 = T.Function2(type1, type2, type3);
707          TypeHandle function23 = T.Function2(type1, type3, type2);
708          CHECK(Equal(function01, function02) == Equal(type2, type3));
709          CHECK(Equal(function01, function03) == Equal(type1, type3));
710          CHECK(Equal(function11, function12) == Equal(type2, type3));
711          CHECK(Equal(function21, function22) == Equal(type2, type3));
712          CHECK(Equal(function21, function23) == Equal(type2, type3));
713        }
714      }
715    }
716  }
717
718  void Of() {
719    // Constant(V)->Is(Of(V))
720    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
721      Handle<i::Object> value = *vt;
722      TypeHandle const_type = T.Constant(value);
723      TypeHandle of_type = T.Of(value);
724      CHECK(const_type->Is(of_type));
725    }
726
727    // If Of(V)->Is(T), then Constant(V)->Is(T)
728    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
729      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
730        Handle<i::Object> value = *vt;
731        TypeHandle type = *it;
732        TypeHandle const_type = T.Constant(value);
733        TypeHandle of_type = T.Of(value);
734        CHECK(!of_type->Is(type) || const_type->Is(type));
735      }
736    }
737
738    // If Constant(V)->Is(T), then Of(V)->Is(T) or T->Maybe(Constant(V))
739    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
740      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
741        Handle<i::Object> value = *vt;
742        TypeHandle type = *it;
743        TypeHandle const_type = T.Constant(value);
744        TypeHandle of_type = T.Of(value);
745        CHECK(!const_type->Is(type) ||
746              of_type->Is(type) || type->Maybe(const_type));
747      }
748    }
749  }
750
751  void NowOf() {
752    // Constant(V)->NowIs(NowOf(V))
753    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
754      Handle<i::Object> value = *vt;
755      TypeHandle const_type = T.Constant(value);
756      TypeHandle nowof_type = T.NowOf(value);
757      CHECK(const_type->NowIs(nowof_type));
758    }
759
760    // NowOf(V)->Is(Of(V))
761    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
762      Handle<i::Object> value = *vt;
763      TypeHandle nowof_type = T.NowOf(value);
764      TypeHandle of_type = T.Of(value);
765      CHECK(nowof_type->Is(of_type));
766    }
767
768    // If NowOf(V)->NowIs(T), then Constant(V)->NowIs(T)
769    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
770      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
771        Handle<i::Object> value = *vt;
772        TypeHandle type = *it;
773        TypeHandle const_type = T.Constant(value);
774        TypeHandle nowof_type = T.NowOf(value);
775        CHECK(!nowof_type->NowIs(type) || const_type->NowIs(type));
776      }
777    }
778
779    // If Constant(V)->NowIs(T),
780    // then NowOf(V)->NowIs(T) or T->Maybe(Constant(V))
781    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
782      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
783        Handle<i::Object> value = *vt;
784        TypeHandle type = *it;
785        TypeHandle const_type = T.Constant(value);
786        TypeHandle nowof_type = T.NowOf(value);
787        CHECK(!const_type->NowIs(type) ||
788              nowof_type->NowIs(type) || type->Maybe(const_type));
789      }
790    }
791
792    // If Constant(V)->Is(T),
793    // then NowOf(V)->Is(T) or T->Maybe(Constant(V))
794    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
795      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
796        Handle<i::Object> value = *vt;
797        TypeHandle type = *it;
798        TypeHandle const_type = T.Constant(value);
799        TypeHandle nowof_type = T.NowOf(value);
800        CHECK(!const_type->Is(type) ||
801              nowof_type->Is(type) || type->Maybe(const_type));
802      }
803    }
804  }
805
806  void BitsetGlb() {
807    // Lower: (T->BitsetGlb())->Is(T)
808    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
809      TypeHandle type = *it;
810      TypeHandle glb =
811          Rep::BitsetType::New(Rep::BitsetType::Glb(type), T.region());
812      CHECK(glb->Is(type));
813    }
814
815    // Greatest: If T1->IsBitset() and T1->Is(T2), then T1->Is(T2->BitsetGlb())
816    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
817      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
818        TypeHandle type1 = *it1;
819        TypeHandle type2 = *it2;
820        TypeHandle glb2 =
821            Rep::BitsetType::New(Rep::BitsetType::Glb(type2), T.region());
822        CHECK(!this->IsBitset(type1) || !type1->Is(type2) || type1->Is(glb2));
823      }
824    }
825
826    // Monotonicity: T1->Is(T2) implies (T1->BitsetGlb())->Is(T2->BitsetGlb())
827    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
828      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
829        TypeHandle type1 = *it1;
830        TypeHandle type2 = *it2;
831        TypeHandle glb1 =
832            Rep::BitsetType::New(Rep::BitsetType::Glb(type1), T.region());
833        TypeHandle glb2 =
834            Rep::BitsetType::New(Rep::BitsetType::Glb(type2), T.region());
835        CHECK(!type1->Is(type2) || glb1->Is(glb2));
836      }
837    }
838  }
839
840  void BitsetLub() {
841    // Upper: T->Is(T->BitsetLub())
842    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
843      TypeHandle type = *it;
844      TypeHandle lub =
845          Rep::BitsetType::New(Rep::BitsetType::Lub(type), T.region());
846      CHECK(type->Is(lub));
847    }
848
849    // Least: If T2->IsBitset() and T1->Is(T2), then (T1->BitsetLub())->Is(T2)
850    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
851      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
852        TypeHandle type1 = *it1;
853        TypeHandle type2 = *it2;
854        TypeHandle lub1 =
855            Rep::BitsetType::New(Rep::BitsetType::Lub(type1), T.region());
856        CHECK(!this->IsBitset(type2) || !type1->Is(type2) || lub1->Is(type2));
857      }
858    }
859
860    // Monotonicity: T1->Is(T2) implies (T1->BitsetLub())->Is(T2->BitsetLub())
861    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
862      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
863        TypeHandle type1 = *it1;
864        TypeHandle type2 = *it2;
865        TypeHandle lub1 =
866            Rep::BitsetType::New(Rep::BitsetType::Lub(type1), T.region());
867        TypeHandle lub2 =
868            Rep::BitsetType::New(Rep::BitsetType::Lub(type2), T.region());
869        CHECK(!type1->Is(type2) || lub1->Is(lub2));
870      }
871    }
872  }
873
874  void Is() {
875    // Least Element (Bottom): None->Is(T)
876    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
877      TypeHandle type = *it;
878      CHECK(T.None->Is(type));
879    }
880
881    // Greatest Element (Top): T->Is(Any)
882    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
883      TypeHandle type = *it;
884      CHECK(type->Is(T.Any));
885    }
886
887    // Bottom Uniqueness: T->Is(None) implies T = None
888    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
889      TypeHandle type = *it;
890      if (type->Is(T.None)) CheckEqual(type, T.None);
891    }
892
893    // Top Uniqueness: Any->Is(T) implies T = Any
894    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
895      TypeHandle type = *it;
896      if (T.Any->Is(type)) CheckEqual(type, T.Any);
897    }
898
899    // Reflexivity: T->Is(T)
900    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
901      TypeHandle type = *it;
902      CHECK(type->Is(type));
903    }
904
905    // Transitivity: T1->Is(T2) and T2->Is(T3) implies T1->Is(T3)
906    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
907      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
908        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
909          TypeHandle type1 = *it1;
910          TypeHandle type2 = *it2;
911          TypeHandle type3 = *it3;
912          CHECK(!(type1->Is(type2) && type2->Is(type3)) || type1->Is(type3));
913        }
914      }
915    }
916
917    // Antisymmetry: T1->Is(T2) and T2->Is(T1) iff T1 = T2
918    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
919      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
920        TypeHandle type1 = *it1;
921        TypeHandle type2 = *it2;
922        CHECK((type1->Is(type2) && type2->Is(type1)) == Equal(type1, type2));
923      }
924    }
925
926    // Class(M1)->Is(Class(M2)) iff M1 = M2
927    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
928      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
929        Handle<i::Map> map1 = *mt1;
930        Handle<i::Map> map2 = *mt2;
931        TypeHandle class_type1 = T.Class(map1);
932        TypeHandle class_type2 = T.Class(map2);
933        CHECK(class_type1->Is(class_type2) == (*map1 == *map2));
934      }
935    }
936
937    // Constant(V1)->Is(Constant(V2)) iff V1 = V2
938    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
939      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
940        Handle<i::Object> value1 = *vt1;
941        Handle<i::Object> value2 = *vt2;
942        TypeHandle const_type1 = T.Constant(value1);
943        TypeHandle const_type2 = T.Constant(value2);
944        CHECK(const_type1->Is(const_type2) == (*value1 == *value2));
945      }
946    }
947
948    // Range(min1, max1)->Is(Range(min2, max2)) iff
949    // min1 >= min2 /\ max1 <= max2
950    for (ValueIterator i1 = T.integers.begin();
951        i1 != T.integers.end(); ++i1) {
952      for (ValueIterator j1 = T.integers.begin();
953          j1 != T.integers.end(); ++j1) {
954        for (ValueIterator i2 = T.integers.begin();
955             i2 != T.integers.end(); ++i2) {
956          for (ValueIterator j2 = T.integers.begin();
957               j2 != T.integers.end(); ++j2) {
958            i::Handle<i::Object> min1 = *i1;
959            i::Handle<i::Object> max1 = *j1;
960            i::Handle<i::Object> min2 = *i2;
961            i::Handle<i::Object> max2 = *j2;
962            if (min1->Number() > max1->Number()) std::swap(min1, max1);
963            if (min2->Number() > max2->Number()) std::swap(min2, max2);
964            TypeHandle type1 = T.Range(min1, max1);
965            TypeHandle type2 = T.Range(min2, max2);
966            CHECK(type1->Is(type2) ==
967                (min2->Number() <= min1->Number() &&
968                 max1->Number() <= max2->Number()));
969          }
970        }
971      }
972    }
973
974    // Context(T1)->Is(Context(T2)) iff T1 = T2
975    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
976      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
977        TypeHandle outer1 = *it1;
978        TypeHandle outer2 = *it2;
979        TypeHandle type1 = T.Context(outer1);
980        TypeHandle type2 = T.Context(outer2);
981        CHECK(type1->Is(type2) == outer1->Equals(outer2));
982      }
983    }
984
985    // Array(T1)->Is(Array(T2)) iff T1 = T2
986    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
987      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
988        TypeHandle element1 = *it1;
989        TypeHandle element2 = *it2;
990        TypeHandle type1 = T.Array1(element1);
991        TypeHandle type2 = T.Array1(element2);
992        CHECK(type1->Is(type2) == element1->Equals(element2));
993      }
994    }
995
996    // Function0(S1, T1)->Is(Function0(S2, T2)) iff S1 = S2 and T1 = T2
997    for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) {
998      for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) {
999        TypeHandle result1 = *i;
1000        TypeHandle receiver1 = *j;
1001        TypeHandle type1 = T.Function0(result1, receiver1);
1002        TypeHandle result2 = T.Random();
1003        TypeHandle receiver2 = T.Random();
1004        TypeHandle type2 = T.Function0(result2, receiver2);
1005        CHECK(type1->Is(type2) ==
1006            (result1->Equals(result2) && receiver1->Equals(receiver2)));
1007      }
1008    }
1009
1010    // (In-)Compatibilities.
1011    for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) {
1012      for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) {
1013        TypeHandle type1 = *i;
1014        TypeHandle type2 = *j;
1015        CHECK(!type1->Is(type2) || this->IsBitset(type2) ||
1016              this->IsUnion(type2) || this->IsUnion(type1) ||
1017              (type1->IsClass() && type2->IsClass()) ||
1018              (type1->IsConstant() && type2->IsConstant()) ||
1019              (type1->IsConstant() && type2->IsRange()) ||
1020              (type1->IsRange() && type2->IsRange()) ||
1021              (type1->IsContext() && type2->IsContext()) ||
1022              (type1->IsArray() && type2->IsArray()) ||
1023              (type1->IsFunction() && type2->IsFunction()) ||
1024              type1->Equals(T.None));
1025      }
1026    }
1027
1028    // Basic types
1029    CheckUnordered(T.Boolean, T.Null);
1030    CheckUnordered(T.Undefined, T.Null);
1031    CheckUnordered(T.Boolean, T.Undefined);
1032
1033    CheckSub(T.SignedSmall, T.Number);
1034    CheckSub(T.Signed32, T.Number);
1035    CheckSub(T.SignedSmall, T.Signed32);
1036    CheckUnordered(T.SignedSmall, T.MinusZero);
1037    CheckUnordered(T.Signed32, T.Unsigned32);
1038
1039    CheckSub(T.UniqueName, T.Name);
1040    CheckSub(T.String, T.Name);
1041    CheckSub(T.InternalizedString, T.String);
1042    CheckSub(T.InternalizedString, T.UniqueName);
1043    CheckSub(T.InternalizedString, T.Name);
1044    CheckSub(T.Symbol, T.UniqueName);
1045    CheckSub(T.Symbol, T.Name);
1046    CheckUnordered(T.String, T.UniqueName);
1047    CheckUnordered(T.String, T.Symbol);
1048    CheckUnordered(T.InternalizedString, T.Symbol);
1049
1050    CheckSub(T.Object, T.Receiver);
1051    CheckSub(T.Array, T.Object);
1052    CheckSub(T.Function, T.Object);
1053    CheckSub(T.Proxy, T.Receiver);
1054    CheckUnordered(T.Object, T.Proxy);
1055    CheckUnordered(T.Array, T.Function);
1056
1057    // Structural types
1058    CheckSub(T.ObjectClass, T.Object);
1059    CheckSub(T.ArrayClass, T.Object);
1060    CheckSub(T.ArrayClass, T.Array);
1061    CheckSub(T.UninitializedClass, T.Internal);
1062    CheckUnordered(T.ObjectClass, T.ArrayClass);
1063    CheckUnordered(T.UninitializedClass, T.Null);
1064    CheckUnordered(T.UninitializedClass, T.Undefined);
1065
1066    CheckSub(T.SmiConstant, T.SignedSmall);
1067    CheckSub(T.SmiConstant, T.Signed32);
1068    CheckSub(T.SmiConstant, T.Number);
1069    CheckSub(T.ObjectConstant1, T.Object);
1070    CheckSub(T.ObjectConstant2, T.Object);
1071    CheckSub(T.ArrayConstant, T.Object);
1072    CheckSub(T.ArrayConstant, T.Array);
1073    CheckSub(T.UninitializedConstant, T.Internal);
1074    CheckUnordered(T.ObjectConstant1, T.ObjectConstant2);
1075    CheckUnordered(T.ObjectConstant1, T.ArrayConstant);
1076    CheckUnordered(T.UninitializedConstant, T.Null);
1077    CheckUnordered(T.UninitializedConstant, T.Undefined);
1078
1079    CheckUnordered(T.ObjectConstant1, T.ObjectClass);
1080    CheckUnordered(T.ObjectConstant2, T.ObjectClass);
1081    CheckUnordered(T.ObjectConstant1, T.ArrayClass);
1082    CheckUnordered(T.ObjectConstant2, T.ArrayClass);
1083    CheckUnordered(T.ArrayConstant, T.ObjectClass);
1084
1085    CheckSub(T.NumberArray, T.Array);
1086    CheckSub(T.NumberArray, T.Object);
1087    CheckUnordered(T.StringArray, T.AnyArray);
1088
1089    CheckSub(T.MethodFunction, T.Function);
1090    CheckSub(T.NumberFunction1, T.Object);
1091    CheckUnordered(T.SignedFunction1, T.NumberFunction1);
1092    CheckUnordered(T.NumberFunction1, T.NumberFunction2);
1093  }
1094
1095  void NowIs() {
1096    // Least Element (Bottom): None->NowIs(T)
1097    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1098      TypeHandle type = *it;
1099      CHECK(T.None->NowIs(type));
1100    }
1101
1102    // Greatest Element (Top): T->NowIs(Any)
1103    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1104      TypeHandle type = *it;
1105      CHECK(type->NowIs(T.Any));
1106    }
1107
1108    // Bottom Uniqueness: T->NowIs(None) implies T = None
1109    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1110      TypeHandle type = *it;
1111      if (type->NowIs(T.None)) CheckEqual(type, T.None);
1112    }
1113
1114    // Top Uniqueness: Any->NowIs(T) implies T = Any
1115    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1116      TypeHandle type = *it;
1117      if (T.Any->NowIs(type)) CheckEqual(type, T.Any);
1118    }
1119
1120    // Reflexivity: T->NowIs(T)
1121    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1122      TypeHandle type = *it;
1123      CHECK(type->NowIs(type));
1124    }
1125
1126    // Transitivity: T1->NowIs(T2) and T2->NowIs(T3) implies T1->NowIs(T3)
1127    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1128      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1129        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1130          TypeHandle type1 = *it1;
1131          TypeHandle type2 = *it2;
1132          TypeHandle type3 = *it3;
1133          CHECK(!(type1->NowIs(type2) && type2->NowIs(type3)) ||
1134                type1->NowIs(type3));
1135        }
1136      }
1137    }
1138
1139    // Antisymmetry: T1->NowIs(T2) and T2->NowIs(T1) iff T1 = T2
1140    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1141      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1142        TypeHandle type1 = *it1;
1143        TypeHandle type2 = *it2;
1144        CHECK((type1->NowIs(type2) && type2->NowIs(type1)) ==
1145              Equal(type1, type2));
1146      }
1147    }
1148
1149    // T1->Is(T2) implies T1->NowIs(T2)
1150    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1151      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1152        TypeHandle type1 = *it1;
1153        TypeHandle type2 = *it2;
1154        CHECK(!type1->Is(type2) || type1->NowIs(type2));
1155      }
1156    }
1157
1158    // Constant(V1)->NowIs(Constant(V2)) iff V1 = V2
1159    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
1160      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
1161        Handle<i::Object> value1 = *vt1;
1162        Handle<i::Object> value2 = *vt2;
1163        TypeHandle const_type1 = T.Constant(value1);
1164        TypeHandle const_type2 = T.Constant(value2);
1165        CHECK(const_type1->NowIs(const_type2) == (*value1 == *value2));
1166      }
1167    }
1168
1169    // Class(M1)->NowIs(Class(M2)) iff M1 = M2
1170    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
1171      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
1172        Handle<i::Map> map1 = *mt1;
1173        Handle<i::Map> map2 = *mt2;
1174        TypeHandle class_type1 = T.Class(map1);
1175        TypeHandle class_type2 = T.Class(map2);
1176        CHECK(class_type1->NowIs(class_type2) == (*map1 == *map2));
1177      }
1178    }
1179
1180    // Constant(V)->NowIs(Class(M)) iff V has map M
1181    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
1182      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1183        Handle<i::Map> map = *mt;
1184        Handle<i::Object> value = *vt;
1185        TypeHandle const_type = T.Constant(value);
1186        TypeHandle class_type = T.Class(map);
1187        CHECK((value->IsHeapObject() &&
1188               i::HeapObject::cast(*value)->map() == *map)
1189              == const_type->NowIs(class_type));
1190      }
1191    }
1192
1193    // Class(M)->NowIs(Constant(V)) never
1194    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
1195      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1196        Handle<i::Map> map = *mt;
1197        Handle<i::Object> value = *vt;
1198        TypeHandle const_type = T.Constant(value);
1199        TypeHandle class_type = T.Class(map);
1200        CHECK(!class_type->NowIs(const_type));
1201      }
1202    }
1203  }
1204
1205  void Contains() {
1206    // T->Contains(V) iff Constant(V)->Is(T)
1207    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1208      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1209        TypeHandle type = *it;
1210        Handle<i::Object> value = *vt;
1211        TypeHandle const_type = T.Constant(value);
1212        CHECK(type->Contains(value) == const_type->Is(type));
1213      }
1214    }
1215  }
1216
1217  void NowContains() {
1218    // T->NowContains(V) iff Constant(V)->NowIs(T)
1219    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1220      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1221        TypeHandle type = *it;
1222        Handle<i::Object> value = *vt;
1223        TypeHandle const_type = T.Constant(value);
1224        CHECK(type->NowContains(value) == const_type->NowIs(type));
1225      }
1226    }
1227
1228    // T->Contains(V) implies T->NowContains(V)
1229    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1230      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1231        TypeHandle type = *it;
1232        Handle<i::Object> value = *vt;
1233        CHECK(!type->Contains(value) || type->NowContains(value));
1234      }
1235    }
1236
1237    // NowOf(V)->Is(T) implies T->NowContains(V)
1238    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1239      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1240        TypeHandle type = *it;
1241        Handle<i::Object> value = *vt;
1242        TypeHandle nowof_type = T.Of(value);
1243        CHECK(!nowof_type->NowIs(type) || type->NowContains(value));
1244      }
1245    }
1246  }
1247
1248  void Maybe() {
1249    // T->Maybe(Any) iff T inhabited
1250    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1251      TypeHandle type = *it;
1252      CHECK(type->Maybe(T.Any) == type->IsInhabited());
1253    }
1254
1255    // T->Maybe(None) never
1256    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1257      TypeHandle type = *it;
1258      CHECK(!type->Maybe(T.None));
1259    }
1260
1261    // Reflexivity upto Inhabitation: T->Maybe(T) iff T inhabited
1262    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1263      TypeHandle type = *it;
1264      CHECK(type->Maybe(type) == type->IsInhabited());
1265    }
1266
1267    // Symmetry: T1->Maybe(T2) iff T2->Maybe(T1)
1268    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1269      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1270        TypeHandle type1 = *it1;
1271        TypeHandle type2 = *it2;
1272        CHECK(type1->Maybe(type2) == type2->Maybe(type1));
1273      }
1274    }
1275
1276    // T1->Maybe(T2) implies T1, T2 inhabited
1277    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1278      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1279        TypeHandle type1 = *it1;
1280        TypeHandle type2 = *it2;
1281        CHECK(!type1->Maybe(type2) ||
1282              (type1->IsInhabited() && type2->IsInhabited()));
1283      }
1284    }
1285
1286    // T1->Maybe(T2) implies Intersect(T1, T2) inhabited
1287    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1288      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1289        TypeHandle type1 = *it1;
1290        TypeHandle type2 = *it2;
1291        TypeHandle intersect12 = T.Intersect(type1, type2);
1292        CHECK(!type1->Maybe(type2) || intersect12->IsInhabited());
1293      }
1294    }
1295
1296    // T1->Is(T2) and T1 inhabited implies T1->Maybe(T2)
1297    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1298      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1299        TypeHandle type1 = *it1;
1300        TypeHandle type2 = *it2;
1301        CHECK(!(type1->Is(type2) && type1->IsInhabited()) ||
1302              type1->Maybe(type2));
1303      }
1304    }
1305
1306    // Constant(V1)->Maybe(Constant(V2)) iff V1 = V2
1307    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
1308      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
1309        Handle<i::Object> value1 = *vt1;
1310        Handle<i::Object> value2 = *vt2;
1311        TypeHandle const_type1 = T.Constant(value1);
1312        TypeHandle const_type2 = T.Constant(value2);
1313        CHECK(const_type1->Maybe(const_type2) == (*value1 == *value2));
1314      }
1315    }
1316
1317    // Class(M1)->Maybe(Class(M2)) iff M1 = M2
1318    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
1319      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
1320        Handle<i::Map> map1 = *mt1;
1321        Handle<i::Map> map2 = *mt2;
1322        TypeHandle class_type1 = T.Class(map1);
1323        TypeHandle class_type2 = T.Class(map2);
1324        CHECK(class_type1->Maybe(class_type2) == (*map1 == *map2));
1325      }
1326    }
1327
1328    // Constant(V)->Maybe(Class(M)) never
1329    // This does NOT hold!
1330    /*
1331    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
1332      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1333        Handle<i::Map> map = *mt;
1334        Handle<i::Object> value = *vt;
1335        TypeHandle const_type = T.Constant(value);
1336        TypeHandle class_type = T.Class(map);
1337        CHECK(!const_type->Maybe(class_type));
1338      }
1339    }
1340    */
1341
1342    // Class(M)->Maybe(Constant(V)) never
1343    // This does NOT hold!
1344    /*
1345    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
1346      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1347        Handle<i::Map> map = *mt;
1348        Handle<i::Object> value = *vt;
1349        TypeHandle const_type = T.Constant(value);
1350        TypeHandle class_type = T.Class(map);
1351        CHECK(!class_type->Maybe(const_type));
1352      }
1353    }
1354    */
1355
1356    // Basic types
1357    CheckDisjoint(T.Boolean, T.Null);
1358    CheckDisjoint(T.Undefined, T.Null);
1359    CheckDisjoint(T.Boolean, T.Undefined);
1360    CheckOverlap(T.SignedSmall, T.Number);
1361    CheckOverlap(T.NaN, T.Number);
1362    CheckDisjoint(T.Signed32, T.NaN);
1363    CheckOverlap(T.UniqueName, T.Name);
1364    CheckOverlap(T.String, T.Name);
1365    CheckOverlap(T.InternalizedString, T.String);
1366    CheckOverlap(T.InternalizedString, T.UniqueName);
1367    CheckOverlap(T.InternalizedString, T.Name);
1368    CheckOverlap(T.Symbol, T.UniqueName);
1369    CheckOverlap(T.Symbol, T.Name);
1370    CheckOverlap(T.String, T.UniqueName);
1371    CheckDisjoint(T.String, T.Symbol);
1372    CheckDisjoint(T.InternalizedString, T.Symbol);
1373    CheckOverlap(T.Object, T.Receiver);
1374    CheckOverlap(T.Array, T.Object);
1375    CheckOverlap(T.Function, T.Object);
1376    CheckOverlap(T.Proxy, T.Receiver);
1377    CheckDisjoint(T.Object, T.Proxy);
1378    CheckDisjoint(T.Array, T.Function);
1379
1380    // Structural types
1381    CheckOverlap(T.ObjectClass, T.Object);
1382    CheckOverlap(T.ArrayClass, T.Object);
1383    CheckOverlap(T.ObjectClass, T.ObjectClass);
1384    CheckOverlap(T.ArrayClass, T.ArrayClass);
1385    CheckDisjoint(T.ObjectClass, T.ArrayClass);
1386    CheckOverlap(T.SmiConstant, T.SignedSmall);
1387    CheckOverlap(T.SmiConstant, T.Signed32);
1388    CheckOverlap(T.SmiConstant, T.Number);
1389    CheckOverlap(T.ObjectConstant1, T.Object);
1390    CheckOverlap(T.ObjectConstant2, T.Object);
1391    CheckOverlap(T.ArrayConstant, T.Object);
1392    CheckOverlap(T.ArrayConstant, T.Array);
1393    CheckOverlap(T.ObjectConstant1, T.ObjectConstant1);
1394    CheckDisjoint(T.ObjectConstant1, T.ObjectConstant2);
1395    CheckDisjoint(T.ObjectConstant1, T.ArrayConstant);
1396    CheckDisjoint(T.ObjectConstant1, T.ArrayClass);
1397    CheckDisjoint(T.ObjectConstant2, T.ArrayClass);
1398    CheckDisjoint(T.ArrayConstant, T.ObjectClass);
1399    CheckOverlap(T.NumberArray, T.Array);
1400    CheckDisjoint(T.NumberArray, T.AnyArray);
1401    CheckDisjoint(T.NumberArray, T.StringArray);
1402    CheckOverlap(T.MethodFunction, T.Function);
1403    CheckDisjoint(T.SignedFunction1, T.NumberFunction1);
1404    CheckDisjoint(T.SignedFunction1, T.NumberFunction2);
1405    CheckDisjoint(T.NumberFunction1, T.NumberFunction2);
1406    CheckDisjoint(T.SignedFunction1, T.MethodFunction);
1407    CheckOverlap(T.ObjectConstant1, T.ObjectClass);  // !!!
1408    CheckOverlap(T.ObjectConstant2, T.ObjectClass);  // !!!
1409    CheckOverlap(T.NumberClass, T.Intersect(T.Number, T.Untagged));  // !!!
1410  }
1411
1412  void Union1() {
1413    // Identity: Union(T, None) = T
1414    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1415      TypeHandle type = *it;
1416      TypeHandle union_type = T.Union(type, T.None);
1417      CheckEqual(union_type, type);
1418    }
1419
1420    // Domination: Union(T, Any) = Any
1421    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1422      TypeHandle type = *it;
1423      TypeHandle union_type = T.Union(type, T.Any);
1424      CheckEqual(union_type, T.Any);
1425    }
1426
1427    // Idempotence: Union(T, T) = T
1428    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1429      TypeHandle type = *it;
1430      TypeHandle union_type = T.Union(type, type);
1431      CheckEqual(union_type, type);
1432    }
1433
1434    // Commutativity: Union(T1, T2) = Union(T2, T1)
1435    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1436      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1437        TypeHandle type1 = *it1;
1438        TypeHandle type2 = *it2;
1439        TypeHandle union12 = T.Union(type1, type2);
1440        TypeHandle union21 = T.Union(type2, type1);
1441        CheckEqual(union12, union21);
1442      }
1443    }
1444
1445    // Associativity: Union(T1, Union(T2, T3)) = Union(Union(T1, T2), T3)
1446    // This does NOT hold!
1447    /*
1448    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1449      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1450        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1451          TypeHandle type1 = *it1;
1452          TypeHandle type2 = *it2;
1453          TypeHandle type3 = *it3;
1454          TypeHandle union12 = T.Union(type1, type2);
1455          TypeHandle union23 = T.Union(type2, type3);
1456          TypeHandle union1_23 = T.Union(type1, union23);
1457          TypeHandle union12_3 = T.Union(union12, type3);
1458          CheckEqual(union1_23, union12_3);
1459        }
1460      }
1461    }
1462    */
1463
1464    // Meet: T1->Is(Union(T1, T2)) and T2->Is(Union(T1, T2))
1465    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1466      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1467        TypeHandle type1 = *it1;
1468        TypeHandle type2 = *it2;
1469        TypeHandle union12 = T.Union(type1, type2);
1470        CHECK(type1->Is(union12));
1471        CHECK(type2->Is(union12));
1472      }
1473    }
1474
1475    // Upper Boundedness: T1->Is(T2) implies Union(T1, T2) = T2
1476    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1477      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1478        TypeHandle type1 = *it1;
1479        TypeHandle type2 = *it2;
1480        TypeHandle union12 = T.Union(type1, type2);
1481        if (type1->Is(type2)) CheckEqual(union12, type2);
1482      }
1483    }
1484
1485    // Monotonicity: T1->Is(T2) implies Union(T1, T3)->Is(Union(T2, T3))
1486    // This does NOT hold.
1487    /*
1488    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1489      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1490        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1491          TypeHandle type1 = *it1;
1492          TypeHandle type2 = *it2;
1493          TypeHandle type3 = *it3;
1494          TypeHandle union13 = T.Union(type1, type3);
1495          TypeHandle union23 = T.Union(type2, type3);
1496          CHECK(!type1->Is(type2) || union13->Is(union23));
1497        }
1498      }
1499    }
1500    */
1501  }
1502
1503  void Union2() {
1504    // Monotonicity: T1->Is(T3) and T2->Is(T3) implies Union(T1, T2)->Is(T3)
1505    // This does NOT hold.  TODO(neis): Could fix this by splitting
1506    // OtherNumber into a negative and a positive part.
1507    /*
1508    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1509      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1510        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1511          TypeHandle type1 = *it1;
1512          TypeHandle type2 = *it2;
1513          TypeHandle type3 = *it3;
1514          TypeHandle union12 = T.Union(type1, type2);
1515          CHECK(!(type1->Is(type3) && type2->Is(type3)) || union12->Is(type3));
1516        }
1517      }
1518    }
1519    */
1520  }
1521
1522  void Union3() {
1523    // Monotonicity: T1->Is(T2) or T1->Is(T3) implies T1->Is(Union(T2, T3))
1524    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1525      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1526        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1527          TypeHandle type1 = *it1;
1528          TypeHandle type2 = *it2;
1529          TypeHandle type3 = *it3;
1530          TypeHandle union23 = T.Union(type2, type3);
1531          CHECK(!(type1->Is(type2) || type1->Is(type3)) || type1->Is(union23));
1532        }
1533      }
1534    }
1535  }
1536
1537  void Union4() {
1538    // Class-class
1539    CheckSub(T.Union(T.ObjectClass, T.ArrayClass), T.Object);
1540    CheckUnordered(T.Union(T.ObjectClass, T.ArrayClass), T.Array);
1541    CheckOverlap(T.Union(T.ObjectClass, T.ArrayClass), T.Array);
1542    CheckDisjoint(T.Union(T.ObjectClass, T.ArrayClass), T.Number);
1543
1544    // Constant-constant
1545    CheckSub(T.Union(T.ObjectConstant1, T.ObjectConstant2), T.Object);
1546    CheckUnordered(T.Union(T.ObjectConstant1, T.ArrayConstant), T.Array);
1547    CheckUnordered(
1548        T.Union(T.ObjectConstant1, T.ObjectConstant2), T.ObjectClass);
1549    CheckOverlap(
1550        T.Union(T.ObjectConstant1, T.ArrayConstant), T.Array);
1551    CheckDisjoint(
1552        T.Union(T.ObjectConstant1, T.ArrayConstant), T.Number);
1553    CheckOverlap(
1554        T.Union(T.ObjectConstant1, T.ArrayConstant), T.ObjectClass);  // !!!
1555
1556    // Bitset-array
1557    CHECK(this->IsBitset(T.Union(T.AnyArray, T.Array)));
1558    CHECK(this->IsUnion(T.Union(T.NumberArray, T.Number)));
1559
1560    CheckEqual(T.Union(T.AnyArray, T.Array), T.Array);
1561    CheckUnordered(T.Union(T.AnyArray, T.String), T.Array);
1562    CheckOverlap(T.Union(T.NumberArray, T.String), T.Object);
1563    CheckDisjoint(T.Union(T.NumberArray, T.String), T.Number);
1564
1565    // Bitset-function
1566    CHECK(this->IsBitset(T.Union(T.MethodFunction, T.Function)));
1567    CHECK(this->IsUnion(T.Union(T.NumberFunction1, T.Number)));
1568
1569    CheckEqual(T.Union(T.MethodFunction, T.Function), T.Function);
1570    CheckUnordered(T.Union(T.NumberFunction1, T.String), T.Function);
1571    CheckOverlap(T.Union(T.NumberFunction2, T.String), T.Object);
1572    CheckDisjoint(T.Union(T.NumberFunction1, T.String), T.Number);
1573
1574    // Bitset-class
1575    CheckSub(
1576        T.Union(T.ObjectClass, T.SignedSmall), T.Union(T.Object, T.Number));
1577    CheckSub(T.Union(T.ObjectClass, T.Array), T.Object);
1578    CheckUnordered(T.Union(T.ObjectClass, T.String), T.Array);
1579    CheckOverlap(T.Union(T.ObjectClass, T.String), T.Object);
1580    CheckDisjoint(T.Union(T.ObjectClass, T.String), T.Number);
1581
1582    // Bitset-constant
1583    CheckSub(
1584        T.Union(T.ObjectConstant1, T.Signed32), T.Union(T.Object, T.Number));
1585    CheckSub(T.Union(T.ObjectConstant1, T.Array), T.Object);
1586    CheckUnordered(T.Union(T.ObjectConstant1, T.String), T.Array);
1587    CheckOverlap(T.Union(T.ObjectConstant1, T.String), T.Object);
1588    CheckDisjoint(T.Union(T.ObjectConstant1, T.String), T.Number);
1589
1590    // Class-constant
1591    CheckSub(T.Union(T.ObjectConstant1, T.ArrayClass), T.Object);
1592    CheckUnordered(T.ObjectClass, T.Union(T.ObjectConstant1, T.ArrayClass));
1593    CheckSub(
1594        T.Union(T.ObjectConstant1, T.ArrayClass), T.Union(T.Array, T.Object));
1595    CheckUnordered(T.Union(T.ObjectConstant1, T.ArrayClass), T.ArrayConstant);
1596    CheckDisjoint(
1597        T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectConstant2);
1598    CheckOverlap(
1599        T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectClass);  // !!!
1600
1601    // Bitset-union
1602    CheckSub(
1603        T.NaN,
1604        T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Number));
1605    CheckSub(
1606        T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Signed32),
1607        T.Union(T.ObjectConstant1, T.Union(T.Number, T.ArrayClass)));
1608
1609    // Class-union
1610    CheckSub(
1611        T.Union(T.ObjectClass, T.Union(T.ObjectConstant1, T.ObjectClass)),
1612        T.Object);
1613    CheckEqual(
1614        T.Union(T.Union(T.ArrayClass, T.ObjectConstant2), T.ArrayClass),
1615        T.Union(T.ArrayClass, T.ObjectConstant2));
1616
1617    // Constant-union
1618    CheckEqual(
1619        T.Union(
1620            T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)),
1621        T.Union(T.ObjectConstant2, T.ObjectConstant1));
1622    CheckEqual(
1623        T.Union(
1624            T.Union(T.ArrayConstant, T.ObjectConstant2), T.ObjectConstant1),
1625        T.Union(
1626            T.ObjectConstant2, T.Union(T.ArrayConstant, T.ObjectConstant1)));
1627
1628    // Array-union
1629    CheckEqual(
1630        T.Union(T.AnyArray, T.Union(T.NumberArray, T.AnyArray)),
1631        T.Union(T.AnyArray, T.NumberArray));
1632    CheckSub(T.Union(T.AnyArray, T.NumberArray), T.Array);
1633
1634    // Function-union
1635    CheckEqual(
1636        T.Union(T.NumberFunction1, T.NumberFunction2),
1637        T.Union(T.NumberFunction2, T.NumberFunction1));
1638    CheckSub(T.Union(T.SignedFunction1, T.MethodFunction), T.Function);
1639
1640    // Union-union
1641    CheckEqual(
1642        T.Union(
1643            T.Union(T.ObjectConstant2, T.ObjectConstant1),
1644            T.Union(T.ObjectConstant1, T.ObjectConstant2)),
1645        T.Union(T.ObjectConstant2, T.ObjectConstant1));
1646    CheckEqual(
1647        T.Union(
1648            T.Union(T.Number, T.ArrayClass),
1649            T.Union(T.SignedSmall, T.Array)),
1650        T.Union(T.Number, T.Array));
1651  }
1652
1653  void Intersect() {
1654    // Identity: Intersect(T, Any) = T
1655    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1656      TypeHandle type = *it;
1657      TypeHandle intersect_type = T.Intersect(type, T.Any);
1658      CheckEqual(intersect_type, type);
1659    }
1660
1661    // Domination: Intersect(T, None) = None
1662    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1663      TypeHandle type = *it;
1664      TypeHandle intersect_type = T.Intersect(type, T.None);
1665      CheckEqual(intersect_type, T.None);
1666    }
1667
1668    // Idempotence: Intersect(T, T) = T
1669    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1670      TypeHandle type = *it;
1671      TypeHandle intersect_type = T.Intersect(type, type);
1672      CheckEqual(intersect_type, type);
1673    }
1674
1675    // Commutativity: Intersect(T1, T2) = Intersect(T2, T1)
1676    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1677      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1678        TypeHandle type1 = *it1;
1679        TypeHandle type2 = *it2;
1680        TypeHandle intersect12 = T.Intersect(type1, type2);
1681        TypeHandle intersect21 = T.Intersect(type2, type1);
1682        CheckEqual(intersect12, intersect21);
1683      }
1684    }
1685
1686    // Associativity:
1687    // Intersect(T1, Intersect(T2, T3)) = Intersect(Intersect(T1, T2), T3)
1688    // This does NOT hold.
1689    /*
1690    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1691      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1692        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1693          TypeHandle type1 = *it1;
1694          TypeHandle type2 = *it2;
1695          TypeHandle type3 = *it3;
1696          TypeHandle intersect12 = T.Intersect(type1, type2);
1697          TypeHandle intersect23 = T.Intersect(type2, type3);
1698          TypeHandle intersect1_23 = T.Intersect(type1, intersect23);
1699          TypeHandle intersect12_3 = T.Intersect(intersect12, type3);
1700          CheckEqual(intersect1_23, intersect12_3);
1701        }
1702      }
1703    }
1704    */
1705
1706    // Join: Intersect(T1, T2)->Is(T1) and Intersect(T1, T2)->Is(T2)
1707    // This does NOT hold.  Not even the disjunction.
1708    /*
1709    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1710      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1711        TypeHandle type1 = *it1;
1712        TypeHandle type2 = *it2;
1713        TypeHandle intersect12 = T.Intersect(type1, type2);
1714        CHECK(intersect12->Is(type1));
1715        CHECK(intersect12->Is(type2));
1716      }
1717    }
1718    */
1719
1720    // Lower Boundedness: T1->Is(T2) implies Intersect(T1, T2) = T1
1721    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1722      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1723        TypeHandle type1 = *it1;
1724        TypeHandle type2 = *it2;
1725        TypeHandle intersect12 = T.Intersect(type1, type2);
1726        if (type1->Is(type2)) CheckEqual(intersect12, type1);
1727      }
1728    }
1729
1730    // Monotonicity: T1->Is(T2) implies Intersect(T1, T3)->Is(Intersect(T2, T3))
1731    // This does NOT hold.
1732    /*
1733    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1734      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1735        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1736          TypeHandle type1 = *it1;
1737          TypeHandle type2 = *it2;
1738          TypeHandle type3 = *it3;
1739          TypeHandle intersect13 = T.Intersect(type1, type3);
1740          TypeHandle intersect23 = T.Intersect(type2, type3);
1741          CHECK(!type1->Is(type2) || intersect13->Is(intersect23));
1742        }
1743      }
1744    }
1745    */
1746
1747    // Monotonicity: T1->Is(T3) or T2->Is(T3) implies Intersect(T1, T2)->Is(T3)
1748    // This does NOT hold.
1749    /*
1750    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1751      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1752        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1753          TypeHandle type1 = *it1;
1754          TypeHandle type2 = *it2;
1755          TypeHandle type3 = *it3;
1756          TypeHandle intersect12 = T.Intersect(type1, type2);
1757          CHECK(!(type1->Is(type3) || type2->Is(type3)) ||
1758                intersect12->Is(type3));
1759        }
1760      }
1761    }
1762    */
1763
1764    // Monotonicity: T1->Is(T2) and T1->Is(T3) implies T1->Is(Intersect(T2, T3))
1765    // This does NOT hold.
1766    /*
1767    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1768      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1769        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1770          TypeHandle type1 = *it1;
1771          TypeHandle type2 = *it2;
1772          TypeHandle type3 = *it3;
1773          TypeHandle intersect23 = T.Intersect(type2, type3);
1774          CHECK(!(type1->Is(type2) && type1->Is(type3)) ||
1775                type1->Is(intersect23));
1776        }
1777      }
1778    }
1779    */
1780
1781    // Bitset-class
1782    CheckEqual(T.Intersect(T.ObjectClass, T.Object), T.ObjectClass);
1783    CheckEqual(T.Intersect(T.ObjectClass, T.Array), T.None);
1784    CheckEqual(T.Intersect(T.ObjectClass, T.Number), T.None);
1785
1786    // Bitset-array
1787    CheckEqual(T.Intersect(T.NumberArray, T.Object), T.NumberArray);
1788    CheckEqual(T.Intersect(T.AnyArray, T.Function), T.None);
1789
1790    // Bitset-function
1791    CheckEqual(T.Intersect(T.MethodFunction, T.Object), T.MethodFunction);
1792    CheckEqual(T.Intersect(T.NumberFunction1, T.Array), T.None);
1793
1794    // Bitset-union
1795    CheckEqual(
1796        T.Intersect(T.Object, T.Union(T.ObjectConstant1, T.ObjectClass)),
1797        T.Union(T.ObjectConstant1, T.ObjectClass));
1798    CHECK(
1799        !T.Intersect(T.Union(T.ArrayClass, T.ObjectConstant1), T.Number)
1800            ->IsInhabited());
1801
1802    // Class-constant
1803    CHECK(T.Intersect(T.ObjectConstant1, T.ObjectClass)->IsInhabited());  // !!!
1804    CHECK(!T.Intersect(T.ArrayClass, T.ObjectConstant2)->IsInhabited());
1805
1806    // Array-union
1807    CheckEqual(
1808        T.Intersect(T.NumberArray, T.Union(T.NumberArray, T.ArrayClass)),
1809        T.NumberArray);
1810    CheckEqual(
1811        T.Intersect(T.AnyArray, T.Union(T.Object, T.SmiConstant)),
1812        T.AnyArray);
1813    CHECK(
1814        !T.Intersect(T.Union(T.AnyArray, T.ArrayConstant), T.NumberArray)
1815            ->IsInhabited());
1816
1817    // Function-union
1818    CheckEqual(
1819        T.Intersect(T.MethodFunction, T.Union(T.String, T.MethodFunction)),
1820        T.MethodFunction);
1821    CheckEqual(
1822        T.Intersect(T.NumberFunction1, T.Union(T.Object, T.SmiConstant)),
1823        T.NumberFunction1);
1824    CHECK(
1825        !T.Intersect(T.Union(T.MethodFunction, T.Name), T.NumberFunction2)
1826            ->IsInhabited());
1827
1828    // Class-union
1829    CheckEqual(
1830        T.Intersect(T.ArrayClass, T.Union(T.ObjectConstant2, T.ArrayClass)),
1831        T.ArrayClass);
1832    CheckEqual(
1833        T.Intersect(T.ArrayClass, T.Union(T.Object, T.SmiConstant)),
1834        T.ArrayClass);
1835    CHECK(
1836        T.Intersect(T.Union(T.ObjectClass, T.ArrayConstant), T.ArrayClass)
1837            ->IsInhabited());  // !!!
1838
1839    // Constant-union
1840    CheckEqual(
1841        T.Intersect(
1842            T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)),
1843        T.ObjectConstant1);
1844    CheckEqual(
1845        T.Intersect(T.SmiConstant, T.Union(T.Number, T.ObjectConstant2)),
1846        T.SmiConstant);
1847    CHECK(
1848        T.Intersect(
1849            T.Union(T.ArrayConstant, T.ObjectClass), T.ObjectConstant1)
1850                ->IsInhabited());  // !!!
1851
1852    // Union-union
1853    CheckEqual(
1854        T.Intersect(
1855            T.Union(T.Number, T.ArrayClass),
1856            T.Union(T.SignedSmall, T.Array)),
1857        T.Union(T.SignedSmall, T.ArrayClass));
1858    CheckEqual(
1859        T.Intersect(
1860            T.Union(T.Number, T.ObjectClass),
1861            T.Union(T.Signed32, T.Array)),
1862        T.Signed32);
1863    CheckEqual(
1864        T.Intersect(
1865            T.Union(T.ObjectConstant2, T.ObjectConstant1),
1866            T.Union(T.ObjectConstant1, T.ObjectConstant2)),
1867        T.Union(T.ObjectConstant2, T.ObjectConstant1));
1868    CheckEqual(
1869        T.Intersect(
1870            T.Union(
1871                T.ArrayClass,
1872                T.Union(T.ObjectConstant2, T.ObjectConstant1)),
1873            T.Union(
1874                T.ObjectConstant1,
1875                T.Union(T.ArrayConstant, T.ObjectConstant2))),
1876        T.Union(
1877            T.ArrayConstant,
1878            T.Union(T.ObjectConstant2, T.ObjectConstant1)));  // !!!
1879  }
1880
1881  void Distributivity() {
1882    // Union(T1, Intersect(T2, T3)) = Intersect(Union(T1, T2), Union(T1, T3))
1883    // This does NOT hold.
1884    /*
1885    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1886      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1887        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1888          TypeHandle type1 = *it1;
1889          TypeHandle type2 = *it2;
1890          TypeHandle type3 = *it3;
1891          TypeHandle union12 = T.Union(type1, type2);
1892          TypeHandle union13 = T.Union(type1, type3);
1893          TypeHandle intersect23 = T.Intersect(type2, type3);
1894          TypeHandle union1_23 = T.Union(type1, intersect23);
1895          TypeHandle intersect12_13 = T.Intersect(union12, union13);
1896          CHECK(Equal(union1_23, intersect12_13));
1897        }
1898      }
1899    }
1900    */
1901
1902    // Intersect(T1, Union(T2, T3)) = Union(Intersect(T1, T2), Intersect(T1,T3))
1903    // This does NOT hold.
1904    /*
1905    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1906      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1907        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1908          TypeHandle type1 = *it1;
1909          TypeHandle type2 = *it2;
1910          TypeHandle type3 = *it3;
1911          TypeHandle intersect12 = T.Intersect(type1, type2);
1912          TypeHandle intersect13 = T.Intersect(type1, type3);
1913          TypeHandle union23 = T.Union(type2, type3);
1914          TypeHandle intersect1_23 = T.Intersect(type1, union23);
1915          TypeHandle union12_13 = T.Union(intersect12, intersect13);
1916          CHECK(Equal(intersect1_23, union12_13));
1917        }
1918      }
1919    }
1920    */
1921  }
1922
1923  template<class Type2, class TypeHandle2, class Region2, class Rep2>
1924  void Convert() {
1925    Types<Type2, TypeHandle2, Region2> T2(
1926        Rep2::ToRegion(&zone, isolate), isolate);
1927    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1928      TypeHandle type1 = *it;
1929      TypeHandle2 type2 = T2.template Convert<Type>(type1);
1930      TypeHandle type3 = T.template Convert<Type2>(type2);
1931      CheckEqual(type1, type3);
1932    }
1933  }
1934
1935  void HTypeFromType() {
1936    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1937      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1938        TypeHandle type1 = *it1;
1939        TypeHandle type2 = *it2;
1940        HType htype1 = HType::FromType<Type>(type1);
1941        HType htype2 = HType::FromType<Type>(type2);
1942        CHECK(!type1->Is(type2) || htype1.IsSubtypeOf(htype2));
1943      }
1944    }
1945  }
1946};
1947
1948typedef Tests<Type, Type*, Zone, ZoneRep> ZoneTests;
1949typedef Tests<HeapType, Handle<HeapType>, Isolate, HeapRep> HeapTests;
1950
1951
1952TEST(IsSomeType) {
1953  CcTest::InitializeVM();
1954  ZoneTests().IsSomeType();
1955  HeapTests().IsSomeType();
1956}
1957
1958
1959TEST(BitsetType) {
1960  CcTest::InitializeVM();
1961  ZoneTests().Bitset();
1962  HeapTests().Bitset();
1963}
1964
1965
1966TEST(ClassType) {
1967  CcTest::InitializeVM();
1968  ZoneTests().Class();
1969  HeapTests().Class();
1970}
1971
1972
1973TEST(ConstantType) {
1974  CcTest::InitializeVM();
1975  ZoneTests().Constant();
1976  HeapTests().Constant();
1977}
1978
1979
1980TEST(RangeType) {
1981  CcTest::InitializeVM();
1982  ZoneTests().Range();
1983  HeapTests().Range();
1984}
1985
1986
1987TEST(ArrayType) {
1988  CcTest::InitializeVM();
1989  ZoneTests().Array();
1990  HeapTests().Array();
1991}
1992
1993
1994TEST(FunctionType) {
1995  CcTest::InitializeVM();
1996  ZoneTests().Function();
1997  HeapTests().Function();
1998}
1999
2000
2001TEST(Of) {
2002  CcTest::InitializeVM();
2003  ZoneTests().Of();
2004  HeapTests().Of();
2005}
2006
2007
2008TEST(NowOf) {
2009  CcTest::InitializeVM();
2010  ZoneTests().NowOf();
2011  HeapTests().NowOf();
2012}
2013
2014
2015TEST(BitsetGlb) {
2016  CcTest::InitializeVM();
2017  ZoneTests().BitsetGlb();
2018  HeapTests().BitsetGlb();
2019}
2020
2021
2022TEST(BitsetLub) {
2023  CcTest::InitializeVM();
2024  ZoneTests().BitsetLub();
2025  HeapTests().BitsetLub();
2026}
2027
2028
2029TEST(Is) {
2030  CcTest::InitializeVM();
2031  ZoneTests().Is();
2032  HeapTests().Is();
2033}
2034
2035
2036TEST(NowIs) {
2037  CcTest::InitializeVM();
2038  ZoneTests().NowIs();
2039  HeapTests().NowIs();
2040}
2041
2042
2043TEST(Contains) {
2044  CcTest::InitializeVM();
2045  ZoneTests().Contains();
2046  HeapTests().Contains();
2047}
2048
2049
2050TEST(NowContains) {
2051  CcTest::InitializeVM();
2052  ZoneTests().NowContains();
2053  HeapTests().NowContains();
2054}
2055
2056
2057TEST(Maybe) {
2058  CcTest::InitializeVM();
2059  ZoneTests().Maybe();
2060  HeapTests().Maybe();
2061}
2062
2063
2064TEST(Union1) {
2065  CcTest::InitializeVM();
2066  ZoneTests().Union1();
2067  HeapTests().Union1();
2068}
2069
2070
2071/*
2072TEST(Union2) {
2073  CcTest::InitializeVM();
2074  ZoneTests().Union2();
2075  HeapTests().Union2();
2076}
2077*/
2078
2079
2080TEST(Union3) {
2081  CcTest::InitializeVM();
2082  ZoneTests().Union3();
2083  HeapTests().Union3();
2084}
2085
2086
2087TEST(Union4) {
2088  CcTest::InitializeVM();
2089  ZoneTests().Union4();
2090  HeapTests().Union4();
2091}
2092
2093
2094TEST(Intersect) {
2095  CcTest::InitializeVM();
2096  ZoneTests().Intersect();
2097  HeapTests().Intersect();
2098}
2099
2100
2101/*
2102TEST(Distributivity) {
2103  CcTest::InitializeVM();
2104  ZoneTests().Distributivity();
2105  HeapTests().Distributivity();
2106}
2107*/
2108
2109
2110TEST(Convert) {
2111  CcTest::InitializeVM();
2112  ZoneTests().Convert<HeapType, Handle<HeapType>, Isolate, HeapRep>();
2113  HeapTests().Convert<Type, Type*, Zone, ZoneRep>();
2114}
2115
2116
2117TEST(HTypeFromType) {
2118  CcTest::InitializeVM();
2119  ZoneTests().HTypeFromType();
2120  HeapTests().HTypeFromType();
2121}
2122