src/v8/test/cctest/test-types.cc

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