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

   1 // Copyright 2013 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #include <vector>
  29
  30 #include "cctest.h"
  31 #include "types.h"
  32 #include "utils/random-number-generator.h"
  33
  34 using namespace v8::internal;
  35
  36 // Testing auxiliaries (breaking the Type abstraction).
  37 struct ZoneRep {
  38   typedef ZoneList<void*> Struct;
  39
  40   static bool IsStruct(Type* t, int tag) {
  41     return !IsBitset(t)
  42         && reinterpret_cast<intptr_t>(AsStruct(t)->at(0)) == tag;
  43   }
  44   static bool IsBitset(Type* t) { return reinterpret_cast<intptr_t>(t) & 1; }
  45   static bool IsClass(Type* t) { return IsStruct(t, 0); }
  46   static bool IsConstant(Type* t) { return IsStruct(t, 1); }
  47   static bool IsUnion(Type* t) { return IsStruct(t, 2); }
  48
  49   static Struct* AsStruct(Type* t) {
  50     return reinterpret_cast<Struct*>(t);
  51   }
  52   static int AsBitset(Type* t) {
  53     return static_cast<int>(reinterpret_cast<intptr_t>(t) >> 1);
  54   }
  55   static Map* AsClass(Type* t) {
  56     return *static_cast<Map**>(AsStruct(t)->at(2));
  57   }
  58   static Object* AsConstant(Type* t) {
  59     return *static_cast<Object**>(AsStruct(t)->at(2));
  60   }
  61   static Struct* AsUnion(Type* t) {
  62     return AsStruct(t);
  63   }
  64   static int Length(Struct* structured) { return structured->length() - 2; }
  65
  66   static Zone* ToRegion(Zone* zone, Isolate* isolate) { return zone; }
  67 };
  68
  69
  70 struct HeapRep {
  71   static bool IsBitset(Handle<HeapType> t) { return t->IsSmi(); }
  72   static bool IsClass(Handle<HeapType> t) { return t->IsMap(); }
  73   static bool IsConstant(Handle<HeapType> t) { return t->IsBox(); }
  74   static bool IsUnion(Handle<HeapType> t) { return t->IsFixedArray(); }
  75
  76   static int AsBitset(Handle<HeapType> t) { return Smi::cast(*t)->value(); }
  77   static Map* AsClass(Handle<HeapType> t) { return Map::cast(*t); }
  78   static Object* AsConstant(Handle<HeapType> t) {
  79     return Box::cast(*t)->value();
  80   }
  81   static FixedArray* AsUnion(Handle<HeapType> t) {
  82     return FixedArray::cast(*t);
  83   }
  84   static int Length(FixedArray* structured) { return structured->length(); }
  85
  86   static Isolate* ToRegion(Zone* zone, Isolate* isolate) { return isolate; }
  87 };
  88
  89
  90 template<class Type, class TypeHandle, class Region>
  91 class Types {
  92  public:
  93   Types(Region* region, Isolate* isolate) : region_(region) {
  94     #define DECLARE_TYPE(name, value) \
  95       name = Type::name(region); \
  96       types.push_back(name);
  97     BITSET_TYPE_LIST(DECLARE_TYPE)
  98     #undef DECLARE_TYPE
  99
 100     object_map = isolate->factory()->NewMap(JS_OBJECT_TYPE, 3 * kPointerSize);
 101     array_map = isolate->factory()->NewMap(JS_ARRAY_TYPE, 4 * kPointerSize);
 102     ObjectClass = Type::Class(object_map, region);
 103     ArrayClass = Type::Class(array_map, region);
 104
 105     maps.push_back(object_map);
 106     maps.push_back(array_map);
 107     for (MapVector::iterator it = maps.begin(); it != maps.end(); ++it) {
 108       types.push_back(Type::Class(*it, region));
 109     }
 110
 111     smi = handle(Smi::FromInt(666), isolate);
 112     signed32 = isolate->factory()->NewHeapNumber(0x40000000);
 113     object1 = isolate->factory()->NewJSObjectFromMap(object_map);
 114     object2 = isolate->factory()->NewJSObjectFromMap(object_map);
 115     array = isolate->factory()->NewJSArray(20);
 116     SmiConstant = Type::Constant(smi, region);
 117     Signed32Constant = Type::Constant(signed32, region);
 118     ObjectConstant1 = Type::Constant(object1, region);
 119     ObjectConstant2 = Type::Constant(object2, region);
 120     ArrayConstant = Type::Constant(array, region);
 121
 122     values.push_back(smi);
 123     values.push_back(signed32);
 124     values.push_back(object1);
 125     values.push_back(object2);
 126     values.push_back(array);
 127     for (ValueVector::iterator it = values.begin(); it != values.end(); ++it) {
 128       types.push_back(Type::Constant(*it, region));
 129     }
 130
 131     for (int i = 0; i < 50; ++i) {
 132       types.push_back(Fuzz());
 133     }
 134   }
 135
 136   Handle<i::Map> object_map;
 137   Handle<i::Map> array_map;
 138
 139   Handle<i::Smi> smi;
 140   Handle<i::HeapNumber> signed32;
 141   Handle<i::JSObject> object1;
 142   Handle<i::JSObject> object2;
 143   Handle<i::JSArray> array;
 144
 145   #define DECLARE_TYPE(name, value) TypeHandle name;
 146   BITSET_TYPE_LIST(DECLARE_TYPE)
 147   #undef DECLARE_TYPE
 148
 149   TypeHandle ObjectClass;
 150   TypeHandle ArrayClass;
 151
 152   TypeHandle SmiConstant;
 153   TypeHandle Signed32Constant;
 154   TypeHandle ObjectConstant1;
 155   TypeHandle ObjectConstant2;
 156   TypeHandle ArrayConstant;
 157
 158   typedef std::vector<TypeHandle> TypeVector;
 159   typedef std::vector<Handle<i::Map> > MapVector;
 160   typedef std::vector<Handle<i::Object> > ValueVector;
 161   TypeVector types;
 162   MapVector maps;
 163   ValueVector values;
 164
 165   TypeHandle Of(Handle<i::Object> value) {
 166     return Type::Of(value, region_);
 167   }
 168
 169   TypeHandle NowOf(Handle<i::Object> value) {
 170     return Type::NowOf(value, region_);
 171   }
 172
 173   TypeHandle Constant(Handle<i::Object> value) {
 174     return Type::Constant(value, region_);
 175   }
 176
 177   TypeHandle Class(Handle<i::Map> map) {
 178     return Type::Class(map, region_);
 179   }
 180
 181   TypeHandle Union(TypeHandle t1, TypeHandle t2) {
 182     return Type::Union(t1, t2, region_);
 183   }
 184   TypeHandle Intersect(TypeHandle t1, TypeHandle t2) {
 185     return Type::Intersect(t1, t2, region_);
 186   }
 187
 188   template<class Type2, class TypeHandle2>
 189   TypeHandle Convert(TypeHandle2 t) {
 190     return Type::template Convert<Type2>(t, region_);
 191   }
 192
 193   TypeHandle Random() {
 194     return types[rng_.NextInt(static_cast<int>(types.size()))];
 195   }
 196
 197   TypeHandle Fuzz(int depth = 5) {
 198     switch (rng_.NextInt(depth == 0 ? 3 : 20)) {
 199       case 0: {  // bitset
 200         int n = 0
 201         #define COUNT_BITSET_TYPES(type, value) + 1
 202         BITSET_TYPE_LIST(COUNT_BITSET_TYPES)
 203         #undef COUNT_BITSET_TYPES
 204         ;
 205         int i = rng_.NextInt(n);
 206         #define PICK_BITSET_TYPE(type, value) \
 207           if (i-- == 0) return Type::type(region_);
 208         BITSET_TYPE_LIST(PICK_BITSET_TYPE)
 209         #undef PICK_BITSET_TYPE
 210         UNREACHABLE();
 211       }
 212       case 1: {  // class
 213         int i = rng_.NextInt(static_cast<int>(maps.size()));
 214         return Type::Class(maps[i], region_);
 215       }
 216       case 2: {  // constant
 217         int i = rng_.NextInt(static_cast<int>(values.size()));
 218         return Type::Constant(values[i], region_);
 219       }
 220       default: {  // union
 221         int n = rng_.NextInt(10);
 222         TypeHandle type = None;
 223         for (int i = 0; i < n; ++i) {
 224           TypeHandle operand = Fuzz(depth - 1);
 225           type = Type::Union(type, operand, region_);
 226         }
 227         return type;
 228       }
 229     }
 230     UNREACHABLE();
 231   }
 232
 233  private:
 234   Region* region_;
 235   RandomNumberGenerator rng_;
 236 };
 237
 238
 239 template<class Type, class TypeHandle, class Region, class Rep>
 240 struct Tests : Rep {
 241   typedef Types<Type, TypeHandle, Region> TypesInstance;
 242   typedef typename TypesInstance::TypeVector::iterator TypeIterator;
 243   typedef typename TypesInstance::MapVector::iterator MapIterator;
 244   typedef typename TypesInstance::ValueVector::iterator ValueIterator;
 245
 246   Isolate* isolate;
 247   HandleScope scope;
 248   Zone zone;
 249   TypesInstance T;
 250
 251   Tests() :
 252       isolate(CcTest::i_isolate()),
 253       scope(isolate),
 254       zone(isolate),
 255       T(Rep::ToRegion(&zone, isolate), isolate) {
 256   }
 257
 258   bool Equal(TypeHandle type1, TypeHandle type2) {
 259     return
 260         type1->Is(type2) && type2->Is(type1) &&
 261         Rep::IsBitset(type1) == Rep::IsBitset(type2) &&
 262         Rep::IsClass(type1) == Rep::IsClass(type2) &&
 263         Rep::IsConstant(type1) == Rep::IsConstant(type2) &&
 264         Rep::IsUnion(type1) == Rep::IsUnion(type2) &&
 265         type1->NumClasses() == type2->NumClasses() &&
 266         type1->NumConstants() == type2->NumConstants() &&
 267         (!Rep::IsBitset(type1) ||
 268           Rep::AsBitset(type1) == Rep::AsBitset(type2)) &&
 269         (!Rep::IsClass(type1) ||
 270           Rep::AsClass(type1) == Rep::AsClass(type2)) &&
 271         (!Rep::IsConstant(type1) ||
 272           Rep::AsConstant(type1) == Rep::AsConstant(type2)) &&
 273         (!Rep::IsUnion(type1) ||
 274           Rep::Length(Rep::AsUnion(type1)) == Rep::Length(Rep::AsUnion(type2)));
 275   }
 276
 277   void CheckEqual(TypeHandle type1, TypeHandle type2) {
 278     CHECK(Equal(type1, type2));
 279   }
 280
 281   void CheckSub(TypeHandle type1, TypeHandle type2) {
 282     CHECK(type1->Is(type2));
 283     CHECK(!type2->Is(type1));
 284     if (Rep::IsBitset(type1) && Rep::IsBitset(type2)) {
 285       CHECK_NE(Rep::AsBitset(type1), Rep::AsBitset(type2));
 286     }
 287   }
 288
 289   void CheckUnordered(TypeHandle type1, TypeHandle type2) {
 290     CHECK(!type1->Is(type2));
 291     CHECK(!type2->Is(type1));
 292     if (Rep::IsBitset(type1) && Rep::IsBitset(type2)) {
 293       CHECK_NE(Rep::AsBitset(type1), Rep::AsBitset(type2));
 294     }
 295   }
 296
 297   void CheckOverlap(TypeHandle type1, TypeHandle type2, TypeHandle mask) {
 298     CHECK(type1->Maybe(type2));
 299     CHECK(type2->Maybe(type1));
 300     if (Rep::IsBitset(type1) && Rep::IsBitset(type2)) {
 301       CHECK_NE(0,
 302           Rep::AsBitset(type1) & Rep::AsBitset(type2) & Rep::AsBitset(mask));
 303     }
 304   }
 305
 306   void CheckDisjoint(TypeHandle type1, TypeHandle type2, TypeHandle mask) {
 307     CHECK(!type1->Is(type2));
 308     CHECK(!type2->Is(type1));
 309     CHECK(!type1->Maybe(type2));
 310     CHECK(!type2->Maybe(type1));
 311     if (Rep::IsBitset(type1) && Rep::IsBitset(type2)) {
 312       CHECK_EQ(0,
 313           Rep::AsBitset(type1) & Rep::AsBitset(type2) & Rep::AsBitset(mask));
 314     }
 315   }
 316
 317   void Bitset() {
 318     // None and Any are bitsets.
 319     CHECK(this->IsBitset(T.None));
 320     CHECK(this->IsBitset(T.Any));
 321
 322     CHECK_EQ(0, this->AsBitset(T.None));
 323     CHECK_EQ(-1, this->AsBitset(T.Any));
 324
 325     // Union(T1, T2) is bitset for bitsets T1,T2
 326     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 327       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 328         TypeHandle type1 = *it1;
 329         TypeHandle type2 = *it2;
 330         TypeHandle union12 = T.Union(type1, type2);
 331         CHECK(!(this->IsBitset(type1) && this->IsBitset(type2)) ||
 332               this->IsBitset(union12));
 333       }
 334     }
 335
 336     // Intersect(T1, T2) is bitset for bitsets T1,T2
 337     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 338       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 339         TypeHandle type1 = *it1;
 340         TypeHandle type2 = *it2;
 341         TypeHandle intersect12 = T.Intersect(type1, type2);
 342         CHECK(!(this->IsBitset(type1) && this->IsBitset(type2)) ||
 343               this->IsBitset(intersect12));
 344       }
 345     }
 346
 347     // Union(T1, T2) is bitset if T2 is bitset and T1->Is(T2)
 348     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 349       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 350         TypeHandle type1 = *it1;
 351         TypeHandle type2 = *it2;
 352         TypeHandle union12 = T.Union(type1, type2);
 353         CHECK(!(this->IsBitset(type2) && type1->Is(type2)) ||
 354               this->IsBitset(union12));
 355       }
 356     }
 357
 358     // Union(T1, T2) is bitwise disjunction for bitsets T1,T2
 359     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 360       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 361         TypeHandle type1 = *it1;
 362         TypeHandle type2 = *it2;
 363         TypeHandle union12 = T.Union(type1, type2);
 364         if (this->IsBitset(type1) && this->IsBitset(type2)) {
 365           CHECK_EQ(
 366               this->AsBitset(type1) | this->AsBitset(type2),
 367               this->AsBitset(union12));
 368         }
 369       }
 370     }
 371
 372     // Intersect(T1, T2) is bitwise conjunction for bitsets T1,T2
 373     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 374       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 375         TypeHandle type1 = *it1;
 376         TypeHandle type2 = *it2;
 377         TypeHandle intersect12 = T.Intersect(type1, type2);
 378         if (this->IsBitset(type1) && this->IsBitset(type2)) {
 379           CHECK_EQ(
 380               this->AsBitset(type1) & this->AsBitset(type2),
 381               this->AsBitset(intersect12));
 382         }
 383       }
 384     }
 385   }
 386
 387   void Class() {
 388     // Constructor
 389     for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
 390       Handle<i::Map> map = *mt;
 391       TypeHandle type = T.Class(map);
 392       CHECK(this->IsClass(type));
 393     }
 394
 395     // Map attribute
 396     for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
 397       Handle<i::Map> map = *mt;
 398       TypeHandle type = T.Class(map);
 399       CHECK(*map == *type->AsClass());
 400     }
 401
 402     // Functionality & Injectivity: Class(M1) = Class(M2) iff M1 = M2
 403     for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
 404       for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
 405         Handle<i::Map> map1 = *mt1;
 406         Handle<i::Map> map2 = *mt2;
 407         TypeHandle type1 = T.Class(map1);
 408         TypeHandle type2 = T.Class(map2);
 409         CHECK(Equal(type1, type2) == (*map1 == *map2));
 410       }
 411     }
 412   }
 413
 414   void Constant() {
 415     // Constructor
 416     for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
 417       Handle<i::Object> value = *vt;
 418       TypeHandle type = T.Constant(value);
 419       CHECK(this->IsConstant(type));
 420     }
 421
 422     // Value attribute
 423     for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
 424       Handle<i::Object> value = *vt;
 425       TypeHandle type = T.Constant(value);
 426       CHECK(*value == *type->AsConstant());
 427     }
 428
 429     // Functionality & Injectivity: Constant(V1) = Constant(V2) iff V1 = V2
 430     for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
 431       for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
 432         Handle<i::Object> value1 = *vt1;
 433         Handle<i::Object> value2 = *vt2;
 434         TypeHandle type1 = T.Constant(value1);
 435         TypeHandle type2 = T.Constant(value2);
 436         CHECK(Equal(type1, type2) == (*value1 == *value2));
 437       }
 438     }
 439   }
 440
 441   void Of() {
 442     // Constant(V)->Is(Of(V))
 443     for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
 444       Handle<i::Object> value = *vt;
 445       TypeHandle const_type = T.Constant(value);
 446       TypeHandle of_type = T.Of(value);
 447       CHECK(const_type->Is(of_type));
 448     }
 449
 450     // Constant(V)->Is(T) iff Of(V)->Is(T) or T->Maybe(Constant(V))
 451     for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
 452       for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 453         Handle<i::Object> value = *vt;
 454         TypeHandle type = *it;
 455         TypeHandle const_type = T.Constant(value);
 456         TypeHandle of_type = T.Of(value);
 457         CHECK(const_type->Is(type) ==
 458               (of_type->Is(type) || type->Maybe(const_type)));
 459       }
 460     }
 461   }
 462
 463   void Is() {
 464     // Least Element (Bottom): None->Is(T)
 465     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 466       TypeHandle type = *it;
 467       CHECK(T.None->Is(type));
 468     }
 469
 470     // Greatest Element (Top): T->Is(Any)
 471     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 472       TypeHandle type = *it;
 473       CHECK(type->Is(T.Any));
 474     }
 475
 476     // Bottom Uniqueness: T->Is(None) implies T = None
 477     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 478       TypeHandle type = *it;
 479       if (type->Is(T.None)) CheckEqual(type, T.None);
 480     }
 481
 482     // Top Uniqueness: Any->Is(T) implies T = Any
 483     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 484       TypeHandle type = *it;
 485       if (T.Any->Is(type)) CheckEqual(type, T.Any);
 486     }
 487
 488     // Reflexivity: T->Is(T)
 489     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 490       TypeHandle type = *it;
 491       CHECK(type->Is(type));
 492     }
 493
 494     // Transitivity: T1->Is(T2) and T2->Is(T3) implies T1->Is(T3)
 495     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 496       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 497         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
 498           TypeHandle type1 = *it1;
 499           TypeHandle type2 = *it2;
 500           TypeHandle type3 = *it3;
 501           CHECK(!(type1->Is(type2) && type2->Is(type3)) || type1->Is(type3));
 502         }
 503       }
 504     }
 505
 506     // Antisymmetry: T1->Is(T2) and T2->Is(T1) iff T1 = T2
 507     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 508       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 509         TypeHandle type1 = *it1;
 510         TypeHandle type2 = *it2;
 511         CHECK((type1->Is(type2) && type2->Is(type1)) == Equal(type1, type2));
 512       }
 513     }
 514
 515     // Constant(V1)->Is(Constant(V2)) iff V1 = V2
 516     for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
 517       for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
 518         Handle<i::Object> value1 = *vt1;
 519         Handle<i::Object> value2 = *vt2;
 520         TypeHandle const_type1 = T.Constant(value1);
 521         TypeHandle const_type2 = T.Constant(value2);
 522         CHECK(const_type1->Is(const_type2) == (*value1 == *value2));
 523       }
 524     }
 525
 526     // Class(M1)->Is(Class(M2)) iff M1 = M2
 527     for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
 528       for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
 529         Handle<i::Map> map1 = *mt1;
 530         Handle<i::Map> map2 = *mt2;
 531         TypeHandle class_type1 = T.Class(map1);
 532         TypeHandle class_type2 = T.Class(map2);
 533         CHECK(class_type1->Is(class_type2) == (*map1 == *map2));
 534       }
 535     }
 536
 537     // Constant(V)->Is(Class(M)) never
 538     for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
 539       for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
 540         Handle<i::Map> map = *mt;
 541         Handle<i::Object> value = *vt;
 542         TypeHandle constant_type = T.Constant(value);
 543         TypeHandle class_type = T.Class(map);
 544         CHECK(!constant_type->Is(class_type));
 545       }
 546     }
 547
 548     // Class(M)->Is(Constant(V)) never
 549     for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
 550       for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
 551         Handle<i::Map> map = *mt;
 552         Handle<i::Object> value = *vt;
 553         TypeHandle constant_type = T.Constant(value);
 554         TypeHandle class_type = T.Class(map);
 555         CHECK(!class_type->Is(constant_type));
 556       }
 557     }
 558
 559     // Basic types
 560     CheckUnordered(T.Boolean, T.Null);
 561     CheckUnordered(T.Undefined, T.Null);
 562     CheckUnordered(T.Boolean, T.Undefined);
 563
 564     CheckSub(T.SignedSmall, T.Number);
 565     CheckSub(T.Signed32, T.Number);
 566     CheckSub(T.Float, T.Number);
 567     CheckSub(T.SignedSmall, T.Signed32);
 568     CheckUnordered(T.SignedSmall, T.Float);
 569     CheckUnordered(T.Signed32, T.Float);
 570
 571     CheckSub(T.UniqueName, T.Name);
 572     CheckSub(T.String, T.Name);
 573     CheckSub(T.InternalizedString, T.String);
 574     CheckSub(T.InternalizedString, T.UniqueName);
 575     CheckSub(T.InternalizedString, T.Name);
 576     CheckSub(T.Symbol, T.UniqueName);
 577     CheckSub(T.Symbol, T.Name);
 578     CheckUnordered(T.String, T.UniqueName);
 579     CheckUnordered(T.String, T.Symbol);
 580     CheckUnordered(T.InternalizedString, T.Symbol);
 581
 582     CheckSub(T.Object, T.Receiver);
 583     CheckSub(T.Array, T.Object);
 584     CheckSub(T.Function, T.Object);
 585     CheckSub(T.Proxy, T.Receiver);
 586     CheckUnordered(T.Object, T.Proxy);
 587     CheckUnordered(T.Array, T.Function);
 588
 589     // Structural types
 590     CheckSub(T.ObjectClass, T.Object);
 591     CheckSub(T.ArrayClass, T.Object);
 592     CheckSub(T.ArrayClass, T.Array);
 593     CheckUnordered(T.ObjectClass, T.ArrayClass);
 594
 595     CheckSub(T.SmiConstant, T.SignedSmall);
 596     CheckSub(T.SmiConstant, T.Signed32);
 597     CheckSub(T.SmiConstant, T.Number);
 598     CheckSub(T.ObjectConstant1, T.Object);
 599     CheckSub(T.ObjectConstant2, T.Object);
 600     CheckSub(T.ArrayConstant, T.Object);
 601     CheckSub(T.ArrayConstant, T.Array);
 602     CheckUnordered(T.ObjectConstant1, T.ObjectConstant2);
 603     CheckUnordered(T.ObjectConstant1, T.ArrayConstant);
 604
 605     CheckUnordered(T.ObjectConstant1, T.ObjectClass);
 606     CheckUnordered(T.ObjectConstant2, T.ObjectClass);
 607     CheckUnordered(T.ObjectConstant1, T.ArrayClass);
 608     CheckUnordered(T.ObjectConstant2, T.ArrayClass);
 609     CheckUnordered(T.ArrayConstant, T.ObjectClass);
 610   }
 611
 612   void Maybe() {
 613     // T->Maybe(None) never
 614     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 615       TypeHandle type = *it;
 616       CHECK(!type->Maybe(T.None));
 617     }
 618
 619     // Symmetry: T1->Maybe(T2) iff T2->Maybe(T1)
 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         CHECK(type1->Maybe(type2) == type2->Maybe(type1));
 625       }
 626     }
 627
 628     // Constant(V1)->Maybe(Constant(V2)) iff V1 = V2
 629     for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
 630       for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
 631         Handle<i::Object> value1 = *vt1;
 632         Handle<i::Object> value2 = *vt2;
 633         TypeHandle const_type1 = T.Constant(value1);
 634         TypeHandle const_type2 = T.Constant(value2);
 635         CHECK(const_type1->Maybe(const_type2) == (*value1 == *value2));
 636       }
 637     }
 638
 639     // Class(M1)->Maybe(Class(M2)) iff M1 = M2
 640     for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
 641       for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
 642         Handle<i::Map> map1 = *mt1;
 643         Handle<i::Map> map2 = *mt2;
 644         TypeHandle class_type1 = T.Class(map1);
 645         TypeHandle class_type2 = T.Class(map2);
 646         CHECK(class_type1->Maybe(class_type2) == (*map1 == *map2));
 647       }
 648     }
 649
 650     // Constant(V)->Maybe(Class(M)) never
 651     for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
 652       for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
 653         Handle<i::Map> map = *mt;
 654         Handle<i::Object> value = *vt;
 655         TypeHandle const_type = T.Constant(value);
 656         TypeHandle class_type = T.Class(map);
 657         CHECK(!const_type->Maybe(class_type));
 658       }
 659     }
 660
 661     // Class(M)->Maybe(Constant(V)) never
 662     for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
 663       for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
 664         Handle<i::Map> map = *mt;
 665         Handle<i::Object> value = *vt;
 666         TypeHandle const_type = T.Constant(value);
 667         TypeHandle class_type = T.Class(map);
 668         CHECK(!class_type->Maybe(const_type));
 669       }
 670     }
 671
 672     // Basic types
 673     CheckDisjoint(T.Boolean, T.Null, T.Semantic);
 674     CheckDisjoint(T.Undefined, T.Null, T.Semantic);
 675     CheckDisjoint(T.Boolean, T.Undefined, T.Semantic);
 676
 677     CheckOverlap(T.SignedSmall, T.Number, T.Semantic);
 678     CheckOverlap(T.Float, T.Number, T.Semantic);
 679     CheckDisjoint(T.Signed32, T.Float, T.Semantic);
 680
 681     CheckOverlap(T.UniqueName, T.Name, T.Semantic);
 682     CheckOverlap(T.String, T.Name, T.Semantic);
 683     CheckOverlap(T.InternalizedString, T.String, T.Semantic);
 684     CheckOverlap(T.InternalizedString, T.UniqueName, T.Semantic);
 685     CheckOverlap(T.InternalizedString, T.Name, T.Semantic);
 686     CheckOverlap(T.Symbol, T.UniqueName, T.Semantic);
 687     CheckOverlap(T.Symbol, T.Name, T.Semantic);
 688     CheckOverlap(T.String, T.UniqueName, T.Semantic);
 689     CheckDisjoint(T.String, T.Symbol, T.Semantic);
 690     CheckDisjoint(T.InternalizedString, T.Symbol, T.Semantic);
 691
 692     CheckOverlap(T.Object, T.Receiver, T.Semantic);
 693     CheckOverlap(T.Array, T.Object, T.Semantic);
 694     CheckOverlap(T.Function, T.Object, T.Semantic);
 695     CheckOverlap(T.Proxy, T.Receiver, T.Semantic);
 696     CheckDisjoint(T.Object, T.Proxy, T.Semantic);
 697     CheckDisjoint(T.Array, T.Function, T.Semantic);
 698
 699     // Structural types
 700     CheckOverlap(T.ObjectClass, T.Object, T.Semantic);
 701     CheckOverlap(T.ArrayClass, T.Object, T.Semantic);
 702     CheckOverlap(T.ObjectClass, T.ObjectClass, T.Semantic);
 703     CheckOverlap(T.ArrayClass, T.ArrayClass, T.Semantic);
 704     CheckDisjoint(T.ObjectClass, T.ArrayClass, T.Semantic);
 705
 706     CheckOverlap(T.SmiConstant, T.SignedSmall, T.Semantic);
 707     CheckOverlap(T.SmiConstant, T.Signed32, T.Semantic);
 708     CheckOverlap(T.SmiConstant, T.Number, T.Semantic);
 709     CheckDisjoint(T.SmiConstant, T.Float, T.Semantic);
 710     CheckOverlap(T.ObjectConstant1, T.Object, T.Semantic);
 711     CheckOverlap(T.ObjectConstant2, T.Object, T.Semantic);
 712     CheckOverlap(T.ArrayConstant, T.Object, T.Semantic);
 713     CheckOverlap(T.ArrayConstant, T.Array, T.Semantic);
 714     CheckOverlap(T.ObjectConstant1, T.ObjectConstant1, T.Semantic);
 715     CheckDisjoint(T.ObjectConstant1, T.ObjectConstant2, T.Semantic);
 716     CheckDisjoint(T.ObjectConstant1, T.ArrayConstant, T.Semantic);
 717
 718     CheckDisjoint(T.ObjectConstant1, T.ObjectClass, T.Semantic);
 719     CheckDisjoint(T.ObjectConstant2, T.ObjectClass, T.Semantic);
 720     CheckDisjoint(T.ObjectConstant1, T.ArrayClass, T.Semantic);
 721     CheckDisjoint(T.ObjectConstant2, T.ArrayClass, T.Semantic);
 722     CheckDisjoint(T.ArrayConstant, T.ObjectClass, T.Semantic);
 723   }
 724
 725   void Union1() {
 726     // Identity: Union(T, None) = T
 727     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 728       TypeHandle type = *it;
 729       TypeHandle union_type = T.Union(type, T.None);
 730       CheckEqual(union_type, type);
 731     }
 732
 733     // Domination: Union(T, Any) = Any
 734     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 735       TypeHandle type = *it;
 736       TypeHandle union_type = T.Union(type, T.Any);
 737       CheckEqual(union_type, T.Any);
 738     }
 739
 740     // Idempotence: Union(T, T) = T
 741     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 742       TypeHandle type = *it;
 743       TypeHandle union_type = T.Union(type, type);
 744       CheckEqual(union_type, type);
 745     }
 746
 747     // Commutativity: Union(T1, T2) = Union(T2, T1)
 748     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 749       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 750         TypeHandle type1 = *it1;
 751         TypeHandle type2 = *it2;
 752         TypeHandle union12 = T.Union(type1, type2);
 753         TypeHandle union21 = T.Union(type2, type1);
 754         CheckEqual(union12, union21);
 755       }
 756     }
 757
 758     // Associativity: Union(T1, Union(T2, T3)) = Union(Union(T1, T2), T3)
 759     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 760       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 761         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
 762           TypeHandle type1 = *it1;
 763           TypeHandle type2 = *it2;
 764           TypeHandle type3 = *it3;
 765           TypeHandle union12 = T.Union(type1, type2);
 766           TypeHandle union23 = T.Union(type2, type3);
 767           TypeHandle union1_23 = T.Union(type1, union23);
 768           TypeHandle union12_3 = T.Union(union12, type3);
 769           CheckEqual(union1_23, union12_3);
 770         }
 771       }
 772     }
 773
 774     // Meet: T1->Is(Union(T1, T2)) and T2->Is(Union(T1, T2))
 775     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 776       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 777         TypeHandle type1 = *it1;
 778         TypeHandle type2 = *it2;
 779         TypeHandle union12 = T.Union(type1, type2);
 780         CHECK(type1->Is(union12));
 781         CHECK(type2->Is(union12));
 782       }
 783     }
 784
 785     // Upper Boundedness: T1->Is(T2) implies Union(T1, T2) = T2
 786     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 787       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 788         TypeHandle type1 = *it1;
 789         TypeHandle type2 = *it2;
 790         TypeHandle union12 = T.Union(type1, type2);
 791         if (type1->Is(type2)) CheckEqual(union12, type2);
 792       }
 793     }
 794   }
 795
 796   void Union2() {
 797     // Monotonicity: T1->Is(T2) implies Union(T1, T3)->Is(Union(T2, T3))
 798     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 799       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 800         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
 801           TypeHandle type1 = *it1;
 802           TypeHandle type2 = *it2;
 803           TypeHandle type3 = *it3;
 804           TypeHandle union13 = T.Union(type1, type3);
 805           TypeHandle union23 = T.Union(type2, type3);
 806           CHECK(!type1->Is(type2) || union13->Is(union23));
 807         }
 808       }
 809     }
 810
 811     // Monotonicity: T1->Is(T3) and T2->Is(T3) implies Union(T1, T2)->Is(T3)
 812     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 813       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 814         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
 815           TypeHandle type1 = *it1;
 816           TypeHandle type2 = *it2;
 817           TypeHandle type3 = *it3;
 818           TypeHandle union12 = T.Union(type1, type2);
 819           CHECK(!(type1->Is(type3) && type2->Is(type3)) || union12->Is(type3));
 820         }
 821       }
 822     }
 823
 824     // Monotonicity: T1->Is(T2) or T1->Is(T3) implies T1->Is(Union(T2, T3))
 825     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 826       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 827         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
 828           TypeHandle type1 = *it1;
 829           TypeHandle type2 = *it2;
 830           TypeHandle type3 = *it3;
 831           TypeHandle union23 = T.Union(type2, type3);
 832           CHECK(!(type1->Is(type2) || type1->Is(type3)) || type1->Is(union23));
 833         }
 834       }
 835     }
 836
 837     // Class-class
 838     CheckSub(T.Union(T.ObjectClass, T.ArrayClass), T.Object);
 839     CheckUnordered(T.Union(T.ObjectClass, T.ArrayClass), T.Array);
 840     CheckOverlap(T.Union(T.ObjectClass, T.ArrayClass), T.Array, T.Semantic);
 841     CheckDisjoint(T.Union(T.ObjectClass, T.ArrayClass), T.Number, T.Semantic);
 842
 843     // Constant-constant
 844     CheckSub(T.Union(T.ObjectConstant1, T.ObjectConstant2), T.Object);
 845     CheckUnordered(T.Union(T.ObjectConstant1, T.ArrayConstant), T.Array);
 846     CheckUnordered(
 847         T.Union(T.ObjectConstant1, T.ObjectConstant2), T.ObjectClass);
 848     CheckOverlap(
 849         T.Union(T.ObjectConstant1, T.ArrayConstant), T.Array, T.Semantic);
 850     CheckDisjoint(
 851         T.Union(T.ObjectConstant1, T.ArrayConstant), T.Number, T.Semantic);
 852     CheckDisjoint(
 853         T.Union(T.ObjectConstant1, T.ArrayConstant), T.ObjectClass, T.Semantic);
 854
 855     // Bitset-class
 856     CheckSub(
 857         T.Union(T.ObjectClass, T.SignedSmall), T.Union(T.Object, T.Number));
 858     CheckSub(T.Union(T.ObjectClass, T.Array), T.Object);
 859     CheckUnordered(T.Union(T.ObjectClass, T.String), T.Array);
 860     CheckOverlap(T.Union(T.ObjectClass, T.String), T.Object, T.Semantic);
 861     CheckDisjoint(T.Union(T.ObjectClass, T.String), T.Number, T.Semantic);
 862
 863     // Bitset-constant
 864     CheckSub(
 865         T.Union(T.ObjectConstant1, T.Signed32), T.Union(T.Object, T.Number));
 866     CheckSub(T.Union(T.ObjectConstant1, T.Array), T.Object);
 867     CheckUnordered(T.Union(T.ObjectConstant1, T.String), T.Array);
 868     CheckOverlap(T.Union(T.ObjectConstant1, T.String), T.Object, T.Semantic);
 869     CheckDisjoint(T.Union(T.ObjectConstant1, T.String), T.Number, T.Semantic);
 870
 871     // Class-constant
 872     CheckSub(T.Union(T.ObjectConstant1, T.ArrayClass), T.Object);
 873     CheckUnordered(T.ObjectClass, T.Union(T.ObjectConstant1, T.ArrayClass));
 874     CheckSub(
 875         T.Union(T.ObjectConstant1, T.ArrayClass), T.Union(T.Array, T.Object));
 876     CheckUnordered(T.Union(T.ObjectConstant1, T.ArrayClass), T.ArrayConstant);
 877     CheckDisjoint(
 878         T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectConstant2,
 879         T.Semantic);
 880     CheckDisjoint(
 881         T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectClass, T.Semantic);
 882
 883     // Bitset-union
 884     CheckSub(
 885         T.Float,
 886         T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Number));
 887     CheckSub(
 888         T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Float),
 889         T.Union(T.ObjectConstant1, T.Union(T.Number, T.ArrayClass)));
 890
 891     // Class-union
 892     CheckSub(
 893         T.Union(T.ObjectClass, T.Union(T.ObjectConstant1, T.ObjectClass)),
 894         T.Object);
 895     CheckEqual(
 896         T.Union(T.Union(T.ArrayClass, T.ObjectConstant2), T.ArrayClass),
 897         T.Union(T.ArrayClass, T.ObjectConstant2));
 898
 899     // Constant-union
 900     CheckEqual(
 901         T.Union(
 902             T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)),
 903         T.Union(T.ObjectConstant2, T.ObjectConstant1));
 904     CheckEqual(
 905         T.Union(
 906             T.Union(T.ArrayConstant, T.ObjectConstant2), T.ObjectConstant1),
 907         T.Union(
 908             T.ObjectConstant2, T.Union(T.ArrayConstant, T.ObjectConstant1)));
 909
 910     // Union-union
 911     CheckEqual(
 912         T.Union(
 913             T.Union(T.ObjectConstant2, T.ObjectConstant1),
 914             T.Union(T.ObjectConstant1, T.ObjectConstant2)),
 915         T.Union(T.ObjectConstant2, T.ObjectConstant1));
 916     CheckEqual(
 917         T.Union(
 918             T.Union(T.Number, T.ArrayClass),
 919             T.Union(T.SignedSmall, T.Array)),
 920         T.Union(T.Number, T.Array));
 921   }
 922
 923   void Intersect1() {
 924     // Identity: Intersect(T, Any) = T
 925     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 926       TypeHandle type = *it;
 927       TypeHandle intersect_type = T.Intersect(type, T.Any);
 928       CheckEqual(intersect_type, type);
 929     }
 930
 931     // Domination: Intersect(T, None) = None
 932     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 933       TypeHandle type = *it;
 934       TypeHandle intersect_type = T.Intersect(type, T.None);
 935       CheckEqual(intersect_type, T.None);
 936     }
 937
 938     // Idempotence: Intersect(T, T) = T
 939     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
 940       TypeHandle type = *it;
 941       TypeHandle intersect_type = T.Intersect(type, type);
 942       CheckEqual(intersect_type, type);
 943     }
 944
 945     // Commutativity: Intersect(T1, T2) = Intersect(T2, T1)
 946     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 947       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 948         TypeHandle type1 = *it1;
 949         TypeHandle type2 = *it2;
 950         TypeHandle intersect12 = T.Intersect(type1, type2);
 951         TypeHandle intersect21 = T.Intersect(type2, type1);
 952         CheckEqual(intersect12, intersect21);
 953       }
 954     }
 955
 956     // Associativity:
 957     // Intersect(T1, Intersect(T2, T3)) = Intersect(Intersect(T1, T2), T3)
 958     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 959       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 960         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
 961           TypeHandle type1 = *it1;
 962           TypeHandle type2 = *it2;
 963           TypeHandle type3 = *it3;
 964           TypeHandle intersect12 = T.Intersect(type1, type2);
 965           TypeHandle intersect23 = T.Intersect(type2, type3);
 966           TypeHandle intersect1_23 = T.Intersect(type1, intersect23);
 967           TypeHandle intersect12_3 = T.Intersect(intersect12, type3);
 968           CheckEqual(intersect1_23, intersect12_3);
 969         }
 970       }
 971     }
 972
 973     // Join: Intersect(T1, T2)->Is(T1) and Intersect(T1, T2)->Is(T2)
 974     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 975       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 976         TypeHandle type1 = *it1;
 977         TypeHandle type2 = *it2;
 978         TypeHandle intersect12 = T.Intersect(type1, type2);
 979         CHECK(intersect12->Is(type1));
 980         CHECK(intersect12->Is(type2));
 981       }
 982     }
 983
 984     // Lower Boundedness: T1->Is(T2) implies Intersect(T1, T2) = T1
 985     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 986       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 987         TypeHandle type1 = *it1;
 988         TypeHandle type2 = *it2;
 989         TypeHandle intersect12 = T.Intersect(type1, type2);
 990         if (type1->Is(type2)) CheckEqual(intersect12, type1);
 991       }
 992     }
 993   }
 994
 995   void Intersect2() {
 996     // Monotonicity: T1->Is(T2) implies Intersect(T1, T3)->Is(Intersect(T2, T3))
 997     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
 998       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
 999         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1000           TypeHandle type1 = *it1;
1001           TypeHandle type2 = *it2;
1002           TypeHandle type3 = *it3;
1003           TypeHandle intersect13 = T.Intersect(type1, type3);
1004           TypeHandle intersect23 = T.Intersect(type2, type3);
1005           CHECK(!type1->Is(type2) || intersect13->Is(intersect23));
1006         }
1007       }
1008     }
1009
1010     // Monotonicity: T1->Is(T3) or T2->Is(T3) implies Intersect(T1, T2)->Is(T3)
1011     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1012       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1013         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1014           TypeHandle type1 = *it1;
1015           TypeHandle type2 = *it2;
1016           TypeHandle type3 = *it3;
1017           TypeHandle intersect12 = T.Intersect(type1, type2);
1018           CHECK(!(type1->Is(type3) || type2->Is(type3)) ||
1019                 intersect12->Is(type3));
1020         }
1021       }
1022     }
1023
1024     // Monotonicity: T1->Is(T2) and T1->Is(T3) implies T1->Is(Intersect(T2, T3))
1025     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1026       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1027         for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1028           TypeHandle type1 = *it1;
1029           TypeHandle type2 = *it2;
1030           TypeHandle type3 = *it3;
1031           TypeHandle intersect23 = T.Intersect(type2, type3);
1032           CHECK(!(type1->Is(type2) && type1->Is(type3)) ||
1033                 type1->Is(intersect23));
1034         }
1035       }
1036     }
1037
1038     // Bitset-class
1039     CheckEqual(T.Intersect(T.ObjectClass, T.Object), T.ObjectClass);
1040     CheckSub(T.Intersect(T.ObjectClass, T.Array), T.Representation);
1041     CheckSub(T.Intersect(T.ObjectClass, T.Number), T.Representation);
1042
1043     // Bitset-union
1044     CheckEqual(
1045         T.Intersect(T.Object, T.Union(T.ObjectConstant1, T.ObjectClass)),
1046         T.Union(T.ObjectConstant1, T.ObjectClass));
1047     CheckEqual(
1048         T.Intersect(T.Union(T.ArrayClass, T.ObjectConstant1), T.Number),
1049         T.None);
1050
1051     // Class-constant
1052     CheckEqual(T.Intersect(T.ObjectConstant1, T.ObjectClass), T.None);
1053     CheckEqual(T.Intersect(T.ArrayClass, T.ObjectConstant2), T.None);
1054
1055     // Class-union
1056     CheckEqual(
1057         T.Intersect(T.ArrayClass, T.Union(T.ObjectConstant2, T.ArrayClass)),
1058         T.ArrayClass);
1059     CheckEqual(
1060         T.Intersect(T.ArrayClass, T.Union(T.Object, T.SmiConstant)),
1061         T.ArrayClass);
1062     CheckEqual(
1063         T.Intersect(T.Union(T.ObjectClass, T.ArrayConstant), T.ArrayClass),
1064         T.None);
1065
1066     // Constant-union
1067     CheckEqual(
1068         T.Intersect(
1069             T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)),
1070         T.ObjectConstant1);
1071     CheckEqual(
1072         T.Intersect(T.SmiConstant, T.Union(T.Number, T.ObjectConstant2)),
1073         T.SmiConstant);
1074     CheckEqual(
1075         T.Intersect(
1076             T.Union(T.ArrayConstant, T.ObjectClass), T.ObjectConstant1),
1077         T.None);
1078
1079     // Union-union
1080     CheckEqual(
1081         T.Intersect(
1082             T.Union(T.Number, T.ArrayClass),
1083             T.Union(T.SignedSmall, T.Array)),
1084         T.Union(T.SignedSmall, T.ArrayClass));
1085     CheckEqual(
1086         T.Intersect(
1087             T.Union(T.Number, T.ObjectClass),
1088             T.Union(T.Signed32, T.Array)),
1089         T.Signed32);
1090     CheckEqual(
1091         T.Intersect(
1092             T.Union(T.ObjectConstant2, T.ObjectConstant1),
1093             T.Union(T.ObjectConstant1, T.ObjectConstant2)),
1094         T.Union(T.ObjectConstant2, T.ObjectConstant1));
1095     CheckEqual(
1096         T.Intersect(
1097             T.Union(
1098                 T.Union(T.ObjectConstant2, T.ObjectConstant1), T.ArrayClass),
1099             T.Union(
1100                 T.ObjectConstant1,
1101                 T.Union(T.ArrayConstant, T.ObjectConstant2))),
1102         T.Union(T.ObjectConstant2, T.ObjectConstant1));
1103   }
1104
1105   template<class Type2, class TypeHandle2, class Region2, class Rep2>
1106   void Convert() {
1107     Types<Type2, TypeHandle2, Region2> T2(
1108         Rep2::ToRegion(&zone, isolate), isolate);
1109     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1110       TypeHandle type1 = *it;
1111       TypeHandle2 type2 = T2.template Convert<Type>(type1);
1112       TypeHandle type3 = T.template Convert<Type2>(type2);
1113       CheckEqual(type1, type3);
1114     }
1115   }
1116 };
1117
1118 typedef Tests<Type, Type*, Zone, ZoneRep> ZoneTests;
1119 typedef Tests<HeapType, Handle<HeapType>, Isolate, HeapRep> HeapTests;
1120
1121
1122 TEST(BitsetType) {
1123   CcTest::InitializeVM();
1124   ZoneTests().Bitset();
1125   HeapTests().Bitset();
1126 }
1127
1128
1129 TEST(ClassType) {
1130   CcTest::InitializeVM();
1131   ZoneTests().Class();
1132   HeapTests().Class();
1133 }
1134
1135
1136 TEST(ConstantType) {
1137   CcTest::InitializeVM();
1138   ZoneTests().Constant();
1139   HeapTests().Constant();
1140 }
1141
1142
1143 TEST(Of) {
1144   CcTest::InitializeVM();
1145   ZoneTests().Of();
1146   HeapTests().Of();
1147 }
1148
1149
1150 TEST(Is) {
1151   CcTest::InitializeVM();
1152   ZoneTests().Is();
1153   HeapTests().Is();
1154 }
1155
1156
1157 TEST(Maybe) {
1158   CcTest::InitializeVM();
1159   ZoneTests().Maybe();
1160   HeapTests().Maybe();
1161 }
1162
1163
1164 TEST(Union1) {
1165   CcTest::InitializeVM();
1166   ZoneTests().Union1();
1167   HeapTests().Union1();
1168 }
1169
1170
1171 TEST(Union2) {
1172   CcTest::InitializeVM();
1173   ZoneTests().Union2();
1174   HeapTests().Union2();
1175 }
1176
1177
1178 TEST(Intersect1) {
1179   CcTest::InitializeVM();
1180   ZoneTests().Intersect1();
1181   HeapTests().Intersect1();
1182 }
1183
1184
1185 TEST(Intersect2) {
1186   CcTest::InitializeVM();
1187   ZoneTests().Intersect2();
1188   HeapTests().Intersect2();
1189 }
1190
1191
1192 TEST(Convert) {
1193   CcTest::InitializeVM();
1194   ZoneTests().Convert<HeapType, Handle<HeapType>, Isolate, HeapRep>();
1195   HeapTests().Convert<Type, Type*, Zone, ZoneRep>();
1196 }