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