test-types.cc 71.3 KB
Newer Older
1
// Copyright 2013 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include <vector>
6

7
#include "src/crankshaft/hydrogen-types.h"
8 9
#include "src/types.h"
#include "test/cctest/cctest.h"
10
#include "test/cctest/types-fuzz.h"
11 12 13

using namespace v8::internal;

14

15
// Testing auxiliaries (breaking the Type abstraction).
16 17 18 19 20 21 22 23 24 25 26 27


static bool IsInteger(double x) {
  return nearbyint(x) == x && !i::IsMinusZero(x);  // Allows for infinities.
}


static bool IsInteger(i::Object* x) {
  return x->IsNumber() && IsInteger(x->Number());
}


28 29
typedef uint32_t bitset;

30 31 32 33
struct Tests {
  typedef Types::TypeVector::iterator TypeIterator;
  typedef Types::MapVector::iterator MapIterator;
  typedef Types::ValueVector::iterator ValueIterator;
34

35 36 37
  Isolate* isolate;
  HandleScope scope;
  Zone zone;
38
  Types T;
39

40
  Tests()
41
      : isolate(CcTest::InitIsolateOnce()),
42
        scope(isolate),
43
        zone(isolate->allocator()),
44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
        T(&zone, isolate, isolate->random_number_generator()) {}

  bool IsBitset(Type* type) { return type->IsBitsetForTesting(); }
  bool IsUnion(Type* type) { return type->IsUnionForTesting(); }
  BitsetType::bitset AsBitset(Type* type) { return type->AsBitsetForTesting(); }
  UnionType* AsUnion(Type* type) { return type->AsUnionForTesting(); }

  bool Equal(Type* type1, Type* type2) {
    return type1->Equals(type2) &&
           this->IsBitset(type1) == this->IsBitset(type2) &&
           this->IsUnion(type1) == this->IsUnion(type2) &&
           type1->NumClasses() == type2->NumClasses() &&
           type1->NumConstants() == type2->NumConstants() &&
           (!this->IsBitset(type1) ||
            this->AsBitset(type1) == this->AsBitset(type2)) &&
           (!this->IsUnion(type1) ||
            this->AsUnion(type1)->LengthForTesting() ==
                this->AsUnion(type2)->LengthForTesting());
62 63
  }

64
  void CheckEqual(Type* type1, Type* type2) { CHECK(Equal(type1, type2)); }
65

66
  void CheckSub(Type* type1, Type* type2) {
67 68
    CHECK(type1->Is(type2));
    CHECK(!type2->Is(type1));
69 70
    if (this->IsBitset(type1) && this->IsBitset(type2)) {
      CHECK(this->AsBitset(type1) != this->AsBitset(type2));
71
    }
72
  }
73

74
  void CheckSubOrEqual(Type* type1, Type* type2) {
75 76 77 78 79 80 81
    CHECK(type1->Is(type2));
    if (this->IsBitset(type1) && this->IsBitset(type2)) {
      CHECK((this->AsBitset(type1) | this->AsBitset(type2))
            == this->AsBitset(type2));
    }
  }

82
  void CheckUnordered(Type* type1, Type* type2) {
83 84
    CHECK(!type1->Is(type2));
    CHECK(!type2->Is(type1));
85 86
    if (this->IsBitset(type1) && this->IsBitset(type2)) {
      CHECK(this->AsBitset(type1) != this->AsBitset(type2));
87 88
    }
  }
89

90
  void CheckOverlap(Type* type1, Type* type2) {
91 92 93 94
    CHECK(type1->Maybe(type2));
    CHECK(type2->Maybe(type1));
  }

95
  void CheckDisjoint(Type* type1, Type* type2) {
96 97 98 99
    CHECK(!type1->Is(type2));
    CHECK(!type2->Is(type1));
    CHECK(!type1->Maybe(type2));
    CHECK(!type2->Maybe(type1));
100 101 102 103
  }

  void IsSomeType() {
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
104
      Type* t = *it;
105 106 107
      CHECK(1 ==
          this->IsBitset(t) + t->IsClass() + t->IsConstant() + t->IsRange() +
          this->IsUnion(t) + t->IsArray() + t->IsFunction() + t->IsContext());
108
    }
109 110
  }

111
  void Bitset() {
112
    // None and Any are bitsets.
dslomov@chromium.org's avatar
dslomov@chromium.org committed
113 114 115
    CHECK(this->IsBitset(T.None));
    CHECK(this->IsBitset(T.Any));

116 117
    CHECK(bitset(0) == this->AsBitset(T.None));
    CHECK(bitset(0xfffffffeu) == this->AsBitset(T.Any));
118

119
    // Union(T1, T2) is bitset for bitsets T1,T2
120 121
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
122 123 124
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* union12 = T.Union(type1, type2);
125
        CHECK(!(this->IsBitset(type1) && this->IsBitset(type2)) ||
126
              this->IsBitset(union12));
127 128 129
      }
    }

130
    // Intersect(T1, T2) is bitset for bitsets T1,T2
131 132
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
133 134 135
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* intersect12 = T.Intersect(type1, type2);
136 137 138 139 140 141 142 143
        CHECK(!(this->IsBitset(type1) && this->IsBitset(type2)) ||
              this->IsBitset(intersect12));
      }
    }

    // Union(T1, T2) is bitset if T2 is bitset and T1->Is(T2)
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
144 145 146
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* union12 = T.Union(type1, type2);
147
        CHECK(!(this->IsBitset(type2) && type1->Is(type2)) ||
148
              this->IsBitset(union12));
149 150 151
      }
    }

152
    // Union(T1, T2) is bitwise disjunction for bitsets T1,T2
153 154
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
155 156 157
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* union12 = T.Union(type1, type2);
158
        if (this->IsBitset(type1) && this->IsBitset(type2)) {
159 160
          CHECK(
              (this->AsBitset(type1) | this->AsBitset(type2)) ==
161
              this->AsBitset(union12));
162 163 164 165
        }
      }
    }

166
    // Intersect(T1, T2) is bitwise conjunction for bitsets T1,T2 (modulo None)
167 168
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
169 170
        Type* type1 = *it1;
        Type* type2 = *it2;
171
        if (this->IsBitset(type1) && this->IsBitset(type2)) {
172
          Type* intersect12 = T.Intersect(type1, type2);
173
          bitset bits = this->AsBitset(type1) & this->AsBitset(type2);
174
          CHECK(bits == this->AsBitset(intersect12));
175 176 177
        }
      }
    }
178 179
  }

180 181 182 183 184 185 186 187
  void PointwiseRepresentation() {
    // Check we can decompose type into semantics and representation and
    // then compose it back to get an equivalent type.
    int counter = 0;
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      counter++;
      printf("Counter: %i\n", counter);
      fflush(stdout);
188 189 190 191
      Type* type1 = *it1;
      Type* representation = T.Representation(type1);
      Type* semantic = T.Semantic(type1);
      Type* composed = T.Union(representation, semantic);
192 193 194 195 196 197
      CHECK(type1->Equals(composed));
    }

    // Pointwiseness of Union.
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
198 199 200 201 202 203 204 205 206 207
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* representation1 = T.Representation(type1);
        Type* semantic1 = T.Semantic(type1);
        Type* representation2 = T.Representation(type2);
        Type* semantic2 = T.Semantic(type2);
        Type* direct_union = T.Union(type1, type2);
        Type* representation_union = T.Union(representation1, representation2);
        Type* semantic_union = T.Union(semantic1, semantic2);
        Type* composed_union = T.Union(representation_union, semantic_union);
208 209 210 211 212 213 214
        CHECK(direct_union->Equals(composed_union));
      }
    }

    // Pointwiseness of Intersect.
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
215 216 217 218 219 220 221 222
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* representation1 = T.Representation(type1);
        Type* semantic1 = T.Semantic(type1);
        Type* representation2 = T.Representation(type2);
        Type* semantic2 = T.Semantic(type2);
        Type* direct_intersection = T.Intersect(type1, type2);
        Type* representation_intersection =
223
            T.Intersect(representation1, representation2);
224 225
        Type* semantic_intersection = T.Intersect(semantic1, semantic2);
        Type* composed_intersection =
226 227 228 229 230 231 232 233
            T.Union(representation_intersection, semantic_intersection);
        CHECK(direct_intersection->Equals(composed_intersection));
      }
    }

    // Pointwiseness of Is.
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
234 235 236 237 238 239
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* representation1 = T.Representation(type1);
        Type* semantic1 = T.Semantic(type1);
        Type* representation2 = T.Representation(type2);
        Type* semantic2 = T.Semantic(type2);
240 241 242 243 244 245 246 247
        bool representation_is = representation1->Is(representation2);
        bool semantic_is = semantic1->Is(semantic2);
        bool direct_is = type1->Is(type2);
        CHECK(direct_is == (semantic_is && representation_is));
      }
    }
  }

248
  void Class() {
249 250 251
    // Constructor
    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
      Handle<i::Map> map = *mt;
252
      Type* type = T.Class(map);
253
      CHECK(type->IsClass());
254
    }
255

256 257 258
    // Map attribute
    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
      Handle<i::Map> map = *mt;
259
      Type* type = T.Class(map);
260
      CHECK(*map == *type->AsClass()->Map());
261 262
    }

263
    // Functionality & Injectivity: Class(M1) = Class(M2) iff M1 = M2
264 265 266 267
    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
        Handle<i::Map> map1 = *mt1;
        Handle<i::Map> map2 = *mt2;
268 269
        Type* type1 = T.Class(map1);
        Type* type2 = T.Class(map2);
270
        CHECK(Equal(type1, type2) == (*map1 == *map2));
271 272
      }
    }
273 274
  }

275
  void Constant() {
276 277 278
    // Constructor
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
      Handle<i::Object> value = *vt;
279
      Type* type = T.Constant(value);
280
      CHECK(type->IsConstant());
281
    }
dslomov@chromium.org's avatar
dslomov@chromium.org committed
282

283 284 285
    // Value attribute
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
      Handle<i::Object> value = *vt;
286
      Type* type = T.Constant(value);
287
      CHECK(*value == *type->AsConstant()->Value());
288 289
    }

290
    // Functionality & Injectivity: Constant(V1) = Constant(V2) iff V1 = V2
291 292
    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
293 294
        Handle<i::Object> value1 = *vt1;
        Handle<i::Object> value2 = *vt2;
295 296
        Type* type1 = T.Constant(value1);
        Type* type2 = T.Constant(value2);
297
        CHECK(Equal(type1, type2) == (*value1 == *value2));
298 299
      }
    }
300 301 302 303 304 305

    // Typing of numbers
    Factory* fac = isolate->factory();
    CHECK(T.Constant(fac->NewNumber(0))->Is(T.UnsignedSmall));
    CHECK(T.Constant(fac->NewNumber(1))->Is(T.UnsignedSmall));
    CHECK(T.Constant(fac->NewNumber(0x3fffffff))->Is(T.UnsignedSmall));
306 307 308 309 310 311 312 313 314 315 316
    CHECK(T.Constant(fac->NewNumber(-1))->Is(T.Negative31));
    CHECK(T.Constant(fac->NewNumber(-0x3fffffff))->Is(T.Negative31));
    CHECK(T.Constant(fac->NewNumber(-0x40000000))->Is(T.Negative31));
    CHECK(T.Constant(fac->NewNumber(0x40000000))->Is(T.Unsigned31));
    CHECK(!T.Constant(fac->NewNumber(0x40000000))->Is(T.Unsigned30));
    CHECK(T.Constant(fac->NewNumber(0x7fffffff))->Is(T.Unsigned31));
    CHECK(!T.Constant(fac->NewNumber(0x7fffffff))->Is(T.Unsigned30));
    CHECK(T.Constant(fac->NewNumber(-0x40000001))->Is(T.Negative32));
    CHECK(!T.Constant(fac->NewNumber(-0x40000001))->Is(T.Negative31));
    CHECK(T.Constant(fac->NewNumber(-0x7fffffff))->Is(T.Negative32));
    CHECK(!T.Constant(fac->NewNumber(-0x7fffffff - 1))->Is(T.Negative31));
317
    if (SmiValuesAre31Bits()) {
318 319
      CHECK(!T.Constant(fac->NewNumber(0x40000000))->Is(T.UnsignedSmall));
      CHECK(!T.Constant(fac->NewNumber(0x7fffffff))->Is(T.UnsignedSmall));
320 321
      CHECK(!T.Constant(fac->NewNumber(-0x40000001))->Is(T.SignedSmall));
      CHECK(!T.Constant(fac->NewNumber(-0x7fffffff - 1))->Is(T.SignedSmall));
322 323 324 325
    } else {
      CHECK(SmiValuesAre32Bits());
      CHECK(T.Constant(fac->NewNumber(0x40000000))->Is(T.UnsignedSmall));
      CHECK(T.Constant(fac->NewNumber(0x7fffffff))->Is(T.UnsignedSmall));
326 327
      CHECK(T.Constant(fac->NewNumber(-0x40000001))->Is(T.SignedSmall));
      CHECK(T.Constant(fac->NewNumber(-0x7fffffff - 1))->Is(T.SignedSmall));
328 329
    }
    CHECK(T.Constant(fac->NewNumber(0x80000000u))->Is(T.Unsigned32));
330
    CHECK(!T.Constant(fac->NewNumber(0x80000000u))->Is(T.Unsigned31));
331
    CHECK(T.Constant(fac->NewNumber(0xffffffffu))->Is(T.Unsigned32));
332
    CHECK(!T.Constant(fac->NewNumber(0xffffffffu))->Is(T.Unsigned31));
333 334 335 336 337 338 339 340 341 342
    CHECK(T.Constant(fac->NewNumber(0xffffffffu + 1.0))->Is(T.PlainNumber));
    CHECK(!T.Constant(fac->NewNumber(0xffffffffu + 1.0))->Is(T.Integral32));
    CHECK(T.Constant(fac->NewNumber(-0x7fffffff - 2.0))->Is(T.PlainNumber));
    CHECK(!T.Constant(fac->NewNumber(-0x7fffffff - 2.0))->Is(T.Integral32));
    CHECK(T.Constant(fac->NewNumber(0.1))->Is(T.PlainNumber));
    CHECK(!T.Constant(fac->NewNumber(0.1))->Is(T.Integral32));
    CHECK(T.Constant(fac->NewNumber(-10.1))->Is(T.PlainNumber));
    CHECK(!T.Constant(fac->NewNumber(-10.1))->Is(T.Integral32));
    CHECK(T.Constant(fac->NewNumber(10e60))->Is(T.PlainNumber));
    CHECK(!T.Constant(fac->NewNumber(10e60))->Is(T.Integral32));
343
    CHECK(T.Constant(fac->NewNumber(-1.0*0.0))->Is(T.MinusZero));
344 345
    CHECK(T.Constant(fac->NewNumber(std::numeric_limits<double>::quiet_NaN()))
              ->Is(T.NaN));
346 347 348 349
    CHECK(T.Constant(fac->NewNumber(V8_INFINITY))->Is(T.PlainNumber));
    CHECK(!T.Constant(fac->NewNumber(V8_INFINITY))->Is(T.Integral32));
    CHECK(T.Constant(fac->NewNumber(-V8_INFINITY))->Is(T.PlainNumber));
    CHECK(!T.Constant(fac->NewNumber(-V8_INFINITY))->Is(T.Integral32));
350 351
  }

352 353
  void Range() {
    // Constructor
354 355
    for (ValueIterator i = T.integers.begin(); i != T.integers.end(); ++i) {
      for (ValueIterator j = T.integers.begin(); j != T.integers.end(); ++j) {
356 357 358
        double min = (*i)->Number();
        double max = (*j)->Number();
        if (min > max) std::swap(min, max);
359
        Type* type = T.Range(min, max);
360
        CHECK(type->IsRange());
361 362 363 364
      }
    }

    // Range attributes
365 366
    for (ValueIterator i = T.integers.begin(); i != T.integers.end(); ++i) {
      for (ValueIterator j = T.integers.begin(); j != T.integers.end(); ++j) {
367 368 369
        double min = (*i)->Number();
        double max = (*j)->Number();
        if (min > max) std::swap(min, max);
370
        Type* type = T.Range(min, max);
371 372
        CHECK(min == type->AsRange()->Min());
        CHECK(max == type->AsRange()->Max());
373 374 375 376 377 378 379
      }
    }

    // Functionality & Injectivity:
    // Range(min1, max1) = Range(min2, max2) <=> min1 = min2 /\ max1 = max2
    for (ValueIterator i1 = T.integers.begin();
        i1 != T.integers.end(); ++i1) {
380
      for (ValueIterator j1 = i1;
381 382 383
          j1 != T.integers.end(); ++j1) {
        for (ValueIterator i2 = T.integers.begin();
            i2 != T.integers.end(); ++i2) {
384
          for (ValueIterator j2 = i2;
385
              j2 != T.integers.end(); ++j2) {
386 387 388 389 390 391
            double min1 = (*i1)->Number();
            double max1 = (*j1)->Number();
            double min2 = (*i2)->Number();
            double max2 = (*j2)->Number();
            if (min1 > max1) std::swap(min1, max1);
            if (min2 > max2) std::swap(min2, max2);
392 393
            Type* type1 = T.Range(min1, max1);
            Type* type2 = T.Range(min2, max2);
394
            CHECK(Equal(type1, type2) == (min1 == min2 && max1 == max2));
395 396 397 398
          }
        }
      }
    }
399 400
  }

401 402 403
  void Context() {
    // Constructor
    for (int i = 0; i < 20; ++i) {
404 405 406
      Type* type = T.Random();
      Type* context = T.Context(type);
      CHECK(context->IsContext());
407 408 409 410
    }

    // Attributes
    for (int i = 0; i < 20; ++i) {
411 412
      Type* type = T.Random();
      Type* context = T.Context(type);
413 414 415 416 417 418
      CheckEqual(type, context->AsContext()->Outer());
    }

    // Functionality & Injectivity: Context(T1) = Context(T2) iff T1 = T2
    for (int i = 0; i < 20; ++i) {
      for (int j = 0; j < 20; ++j) {
419 420 421 422
        Type* type1 = T.Random();
        Type* type2 = T.Random();
        Type* context1 = T.Context(type1);
        Type* context2 = T.Context(type2);
423 424 425 426 427
        CHECK(Equal(context1, context2) == Equal(type1, type2));
      }
    }
  }

428 429 430
  void Array() {
    // Constructor
    for (int i = 0; i < 20; ++i) {
431 432
      Type* type = T.Random();
      Type* array = T.Array1(type);
433
      CHECK(array->IsArray());
434 435 436 437
    }

    // Attributes
    for (int i = 0; i < 20; ++i) {
438 439
      Type* type = T.Random();
      Type* array = T.Array1(type);
440 441 442 443 444 445
      CheckEqual(type, array->AsArray()->Element());
    }

    // Functionality & Injectivity: Array(T1) = Array(T2) iff T1 = T2
    for (int i = 0; i < 20; ++i) {
      for (int j = 0; j < 20; ++j) {
446 447 448 449
        Type* type1 = T.Random();
        Type* type2 = T.Random();
        Type* array1 = T.Array1(type1);
        Type* array2 = T.Array1(type2);
450 451 452 453 454 455 456 457 458 459
        CHECK(Equal(array1, array2) == Equal(type1, type2));
      }
    }
  }

  void Function() {
    // Constructors
    for (int i = 0; i < 20; ++i) {
      for (int j = 0; j < 20; ++j) {
        for (int k = 0; k < 20; ++k) {
460 461 462 463 464 465
          Type* type1 = T.Random();
          Type* type2 = T.Random();
          Type* type3 = T.Random();
          Type* function0 = T.Function0(type1, type2);
          Type* function1 = T.Function1(type1, type2, type3);
          Type* function2 = T.Function2(type1, type2, type3);
466 467 468 469 470 471 472 473 474 475 476
          CHECK(function0->IsFunction());
          CHECK(function1->IsFunction());
          CHECK(function2->IsFunction());
        }
      }
    }

    // Attributes
    for (int i = 0; i < 20; ++i) {
      for (int j = 0; j < 20; ++j) {
        for (int k = 0; k < 20; ++k) {
477 478 479 480 481 482
          Type* type1 = T.Random();
          Type* type2 = T.Random();
          Type* type3 = T.Random();
          Type* function0 = T.Function0(type1, type2);
          Type* function1 = T.Function1(type1, type2, type3);
          Type* function2 = T.Function2(type1, type2, type3);
483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502
          CHECK_EQ(0, function0->AsFunction()->Arity());
          CHECK_EQ(1, function1->AsFunction()->Arity());
          CHECK_EQ(2, function2->AsFunction()->Arity());
          CheckEqual(type1, function0->AsFunction()->Result());
          CheckEqual(type1, function1->AsFunction()->Result());
          CheckEqual(type1, function2->AsFunction()->Result());
          CheckEqual(type2, function0->AsFunction()->Receiver());
          CheckEqual(type2, function1->AsFunction()->Receiver());
          CheckEqual(T.Any, function2->AsFunction()->Receiver());
          CheckEqual(type3, function1->AsFunction()->Parameter(0));
          CheckEqual(type2, function2->AsFunction()->Parameter(0));
          CheckEqual(type3, function2->AsFunction()->Parameter(1));
        }
      }
    }

    // Functionality & Injectivity: Function(Ts1) = Function(Ts2) iff Ts1 = Ts2
    for (int i = 0; i < 20; ++i) {
      for (int j = 0; j < 20; ++j) {
        for (int k = 0; k < 20; ++k) {
503 504 505 506 507 508 509 510 511 512 513
          Type* type1 = T.Random();
          Type* type2 = T.Random();
          Type* type3 = T.Random();
          Type* function01 = T.Function0(type1, type2);
          Type* function02 = T.Function0(type1, type3);
          Type* function03 = T.Function0(type3, type2);
          Type* function11 = T.Function1(type1, type2, type2);
          Type* function12 = T.Function1(type1, type2, type3);
          Type* function21 = T.Function2(type1, type2, type2);
          Type* function22 = T.Function2(type1, type2, type3);
          Type* function23 = T.Function2(type1, type3, type2);
514 515 516 517 518 519 520 521 522 523
          CHECK(Equal(function01, function02) == Equal(type2, type3));
          CHECK(Equal(function01, function03) == Equal(type1, type3));
          CHECK(Equal(function11, function12) == Equal(type2, type3));
          CHECK(Equal(function21, function22) == Equal(type2, type3));
          CHECK(Equal(function21, function23) == Equal(type2, type3));
        }
      }
    }
  }

524
  void Of() {
525
    // Constant(V)->Is(Of(V))
526 527
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
      Handle<i::Object> value = *vt;
528 529
      Type* const_type = T.Constant(value);
      Type* of_type = T.Of(value);
530
      CHECK(const_type->Is(of_type));
531 532
    }

533
    // If Of(V)->Is(T), then Constant(V)->Is(T)
534 535 536
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
        Handle<i::Object> value = *vt;
537 538 539
        Type* type = *it;
        Type* const_type = T.Constant(value);
        Type* of_type = T.Of(value);
540 541 542 543 544 545 546 547
        CHECK(!of_type->Is(type) || const_type->Is(type));
      }
    }

    // If Constant(V)->Is(T), then Of(V)->Is(T) or T->Maybe(Constant(V))
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
        Handle<i::Object> value = *vt;
548 549 550
        Type* type = *it;
        Type* const_type = T.Constant(value);
        Type* of_type = T.Of(value);
551 552
        CHECK(!const_type->Is(type) ||
              of_type->Is(type) || type->Maybe(const_type));
553 554
      }
    }
555 556 557
  }

  void NowOf() {
558
    // Constant(V)->NowIs(NowOf(V))
559 560
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
      Handle<i::Object> value = *vt;
561 562
      Type* const_type = T.Constant(value);
      Type* nowof_type = T.NowOf(value);
563
      CHECK(const_type->NowIs(nowof_type));
564 565
    }

566
    // NowOf(V)->Is(Of(V))
567
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
568
      Handle<i::Object> value = *vt;
569 570
      Type* nowof_type = T.NowOf(value);
      Type* of_type = T.Of(value);
571
      CHECK(nowof_type->Is(of_type));
572 573
    }

574 575 576 577
    // If NowOf(V)->NowIs(T), then Constant(V)->NowIs(T)
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
        Handle<i::Object> value = *vt;
578 579 580
        Type* type = *it;
        Type* const_type = T.Constant(value);
        Type* nowof_type = T.NowOf(value);
581 582 583 584 585 586
        CHECK(!nowof_type->NowIs(type) || const_type->NowIs(type));
      }
    }

    // If Constant(V)->NowIs(T),
    // then NowOf(V)->NowIs(T) or T->Maybe(Constant(V))
587 588 589
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
        Handle<i::Object> value = *vt;
590 591 592
        Type* type = *it;
        Type* const_type = T.Constant(value);
        Type* nowof_type = T.NowOf(value);
593 594
        CHECK(!const_type->NowIs(type) ||
              nowof_type->NowIs(type) || type->Maybe(const_type));
595
      }
596 597
    }

598 599
    // If Constant(V)->Is(T),
    // then NowOf(V)->Is(T) or T->Maybe(Constant(V))
600 601 602
    for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
      for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
        Handle<i::Object> value = *vt;
603 604 605
        Type* type = *it;
        Type* const_type = T.Constant(value);
        Type* nowof_type = T.NowOf(value);
606
        CHECK(!const_type->Is(type) ||
607
              nowof_type->Is(type) || type->Maybe(const_type));
608 609
      }
    }
610
  }
611

612 613 614 615 616
  void MinMax() {
    // If b is regular numeric bitset, then Range(b->Min(), b->Max())->Is(b).
    // TODO(neis): Need to ignore representation for this to be true.
    /*
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
617
      Type* type = *it;
618 619
      if (this->IsBitset(type) && type->Is(T.Number) &&
          !type->Is(T.None) && !type->Is(T.NaN)) {
620
        Type* range = T.Range(
621 622 623 624 625 626 627 628 629
            isolate->factory()->NewNumber(type->Min()),
            isolate->factory()->NewNumber(type->Max()));
        CHECK(range->Is(type));
      }
    }
    */

    // If b is regular numeric bitset, then b->Min() and b->Max() are integers.
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
630
      Type* type = *it;
631
      if (this->IsBitset(type) && type->Is(T.Number) && !type->Is(T.NaN)) {
632 633 634 635 636 637 638 639
        CHECK(IsInteger(type->Min()) && IsInteger(type->Max()));
      }
    }

    // If b1 and b2 are regular numeric bitsets with b1->Is(b2), then
    // b1->Min() >= b2->Min() and b1->Max() <= b2->Max().
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
640 641
        Type* type1 = *it1;
        Type* type2 = *it2;
642 643 644 645 646 647 648 649 650 651
        if (this->IsBitset(type1) && type1->Is(type2) && type2->Is(T.Number) &&
            !type1->Is(T.NaN) && !type2->Is(T.NaN)) {
          CHECK(type1->Min() >= type2->Min());
          CHECK(type1->Max() <= type2->Max());
        }
      }
    }

    // Lub(Range(x,y))->Min() <= x and y <= Lub(Range(x,y))->Max()
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
652
      Type* type = *it;
653
      if (type->IsRange()) {
654
        Type* lub = BitsetType::NewForTesting(BitsetType::Lub(type));
655 656 657
        CHECK(lub->Min() <= type->Min() && type->Max() <= lub->Max());
      }
    }
658

659
    // Rangification: If T->Is(Range(-inf,+inf)) and T is inhabited, then
660 661
    // T->Is(Range(T->Min(), T->Max())).
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
662
      Type* type = *it;
663
      CHECK(!type->Is(T.Integer) || !type->IsInhabited() ||
664
            type->Is(T.Range(type->Min(), type->Max())));
665
    }
666 667
  }

668 669
  void BitsetGlb() {
    // Lower: (T->BitsetGlb())->Is(T)
670
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
671 672
      Type* type = *it;
      Type* glb = BitsetType::NewForTesting(BitsetType::Glb(type));
673
      CHECK(glb->Is(type));
674 675
    }

676 677 678
    // Greatest: If T1->IsBitset() and T1->Is(T2), then T1->Is(T2->BitsetGlb())
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
679 680 681
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* glb2 = BitsetType::NewForTesting(BitsetType::Glb(type2));
682 683 684 685 686 687 688
        CHECK(!this->IsBitset(type1) || !type1->Is(type2) || type1->Is(glb2));
      }
    }

    // Monotonicity: T1->Is(T2) implies (T1->BitsetGlb())->Is(T2->BitsetGlb())
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
689 690 691 692
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* glb1 = BitsetType::NewForTesting(BitsetType::Glb(type1));
        Type* glb2 = BitsetType::NewForTesting(BitsetType::Glb(type2));
693 694
        CHECK(!type1->Is(type2) || glb1->Is(glb2));
      }
695
    }
696
  }
697

698 699
  void BitsetLub() {
    // Upper: T->Is(T->BitsetLub())
700
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
701 702
      Type* type = *it;
      Type* lub = BitsetType::NewForTesting(BitsetType::Lub(type));
703 704 705
      CHECK(type->Is(lub));
    }

706 707 708
    // Least: If T2->IsBitset() and T1->Is(T2), then (T1->BitsetLub())->Is(T2)
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
709 710 711
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* lub1 = BitsetType::NewForTesting(BitsetType::Lub(type1));
712 713 714 715 716 717 718
        CHECK(!this->IsBitset(type2) || !type1->Is(type2) || lub1->Is(type2));
      }
    }

    // Monotonicity: T1->Is(T2) implies (T1->BitsetLub())->Is(T2->BitsetLub())
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
719 720 721 722
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* lub1 = BitsetType::NewForTesting(BitsetType::Lub(type1));
        Type* lub2 = BitsetType::NewForTesting(BitsetType::Lub(type2));
723 724
        CHECK(!type1->Is(type2) || lub1->Is(lub2));
      }
725 726 727
    }
  }

728
  void Is1() {
729
    // Least Element (Bottom): None->Is(T)
730
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
731
      Type* type = *it;
732
      CHECK(T.None->Is(type));
733 734
    }

735
    // Greatest Element (Top): T->Is(Any)
736
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
737
      Type* type = *it;
738
      CHECK(type->Is(T.Any));
739 740
    }

741
    // Bottom Uniqueness: T->Is(None) implies T = None
742
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
743
      Type* type = *it;
744
      if (type->Is(T.None)) CheckEqual(type, T.None);
745 746
    }

747
    // Top Uniqueness: Any->Is(T) implies T = Any
748
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
749
      Type* type = *it;
750
      if (T.Any->Is(type)) CheckEqual(type, T.Any);
751 752
    }

753
    // Reflexivity: T->Is(T)
754
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
755
      Type* type = *it;
756 757
      CHECK(type->Is(type));
    }
758

759
    // Transitivity: T1->Is(T2) and T2->Is(T3) implies T1->Is(T3)
760 761 762
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
763 764 765
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
766
          CHECK(!(type1->Is(type2) && type2->Is(type3)) || type1->Is(type3));
767 768 769
        }
      }
    }
770

771 772 773
    // Antisymmetry: T1->Is(T2) and T2->Is(T1) iff T1 = T2
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
774 775
        Type* type1 = *it1;
        Type* type2 = *it2;
776 777 778 779
        CHECK((type1->Is(type2) && type2->Is(type1)) == Equal(type1, type2));
      }
    }

780 781 782
    // (In-)Compatibilities.
    for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) {
      for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) {
783 784
        Type* type1 = *i;
        Type* type2 = *j;
785 786 787 788 789
        CHECK(!type1->Is(type2) || this->IsBitset(type2) ||
              this->IsUnion(type2) || this->IsUnion(type1) ||
              (type1->IsClass() && type2->IsClass()) ||
              (type1->IsConstant() && type2->IsConstant()) ||
              (type1->IsConstant() && type2->IsRange()) ||
790
              (this->IsBitset(type1) && type2->IsRange()) ||
791 792 793 794
              (type1->IsRange() && type2->IsRange()) ||
              (type1->IsContext() && type2->IsContext()) ||
              (type1->IsArray() && type2->IsArray()) ||
              (type1->IsFunction() && type2->IsFunction()) ||
795
              !type1->IsInhabited());
796 797 798 799 800
      }
    }
  }

  void Is2() {
801 802 803 804 805
    // Class(M1)->Is(Class(M2)) iff M1 = M2
    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
        Handle<i::Map> map1 = *mt1;
        Handle<i::Map> map2 = *mt2;
806 807
        Type* class_type1 = T.Class(map1);
        Type* class_type2 = T.Class(map2);
808 809 810 811
        CHECK(class_type1->Is(class_type2) == (*map1 == *map2));
      }
    }

812
    // Range(X1, Y1)->Is(Range(X2, Y2)) iff X1 >= X2 /\ Y1 <= Y2
813 814
    for (ValueIterator i1 = T.integers.begin();
        i1 != T.integers.end(); ++i1) {
815
      for (ValueIterator j1 = i1;
816 817 818
          j1 != T.integers.end(); ++j1) {
        for (ValueIterator i2 = T.integers.begin();
             i2 != T.integers.end(); ++i2) {
819
          for (ValueIterator j2 = i2;
820
               j2 != T.integers.end(); ++j2) {
821 822 823 824 825 826
            double min1 = (*i1)->Number();
            double max1 = (*j1)->Number();
            double min2 = (*i2)->Number();
            double max2 = (*j2)->Number();
            if (min1 > max1) std::swap(min1, max1);
            if (min2 > max2) std::swap(min2, max2);
827 828
            Type* type1 = T.Range(min1, max1);
            Type* type2 = T.Range(min2, max2);
829
            CHECK(type1->Is(type2) == (min1 >= min2 && max1 <= max2));
830 831
          }
        }
832 833 834
      }
    }

835 836 837 838 839
    // Constant(V1)->Is(Constant(V2)) iff V1 = V2
    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
        Handle<i::Object> value1 = *vt1;
        Handle<i::Object> value2 = *vt2;
840 841
        Type* const_type1 = T.Constant(value1);
        Type* const_type2 = T.Constant(value2);
842 843 844 845
        CHECK(const_type1->Is(const_type2) == (*value1 == *value2));
      }
    }

846 847 848
    // Context(T1)->Is(Context(T2)) iff T1 = T2
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
849 850 851 852
        Type* outer1 = *it1;
        Type* outer2 = *it2;
        Type* type1 = T.Context(outer1);
        Type* type2 = T.Context(outer2);
853
        CHECK(type1->Is(type2) == outer1->Equals(outer2));
854 855 856
      }
    }

857 858 859
    // Array(T1)->Is(Array(T2)) iff T1 = T2
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
860 861 862 863
        Type* element1 = *it1;
        Type* element2 = *it2;
        Type* type1 = T.Array1(element1);
        Type* type2 = T.Array1(element2);
864 865 866 867 868 869 870
        CHECK(type1->Is(type2) == element1->Equals(element2));
      }
    }

    // Function0(S1, T1)->Is(Function0(S2, T2)) iff S1 = S2 and T1 = T2
    for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) {
      for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) {
871 872 873 874 875 876
        Type* result1 = *i;
        Type* receiver1 = *j;
        Type* type1 = T.Function0(result1, receiver1);
        Type* result2 = T.Random();
        Type* receiver2 = T.Random();
        Type* type2 = T.Function0(result2, receiver2);
877 878 879 880 881
        CHECK(type1->Is(type2) ==
            (result1->Equals(result2) && receiver1->Equals(receiver2)));
      }
    }

882 883 884 885 886

    // Range-specific subtyping

    // If IsInteger(v) then Constant(v)->Is(Range(v, v)).
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
887
      Type* type = *it;
888
      if (type->IsConstant() && IsInteger(*type->AsConstant()->Value())) {
889 890
        CHECK(type->Is(T.Range(type->AsConstant()->Value()->Number(),
                               type->AsConstant()->Value()->Number())));
891 892
      }
    }
893

894 895 896
    // If Constant(x)->Is(Range(min,max)) then IsInteger(v) and min <= x <= max.
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
897 898
        Type* type1 = *it1;
        Type* type2 = *it2;
899 900
        if (type1->IsConstant() && type2->IsRange() && type1->Is(type2)) {
          double x = type1->AsConstant()->Value()->Number();
901 902
          double min = type2->AsRange()->Min();
          double max = type2->AsRange()->Max();
903 904 905 906 907 908 909
          CHECK(IsInteger(x) && min <= x && x <= max);
        }
      }
    }

    // Lub(Range(x,y))->Is(T.Union(T.Integral32, T.OtherNumber))
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
910
      Type* type = *it;
911
      if (type->IsRange()) {
912
        Type* lub = BitsetType::NewForTesting(BitsetType::Lub(type));
913
        CHECK(lub->Is(T.PlainNumber));
914 915 916 917 918 919
      }
    }


    // Subtyping between concrete basic types

920 921 922 923
    CheckUnordered(T.Boolean, T.Null);
    CheckUnordered(T.Undefined, T.Null);
    CheckUnordered(T.Boolean, T.Undefined);

924
    CheckSub(T.SignedSmall, T.Number);
925
    CheckSub(T.Signed32, T.Number);
926
    CheckSubOrEqual(T.SignedSmall, T.Signed32);
927 928
    CheckUnordered(T.SignedSmall, T.MinusZero);
    CheckUnordered(T.Signed32, T.Unsigned32);
929 930 931 932 933 934 935 936 937 938 939 940 941 942

    CheckSub(T.UniqueName, T.Name);
    CheckSub(T.String, T.Name);
    CheckSub(T.InternalizedString, T.String);
    CheckSub(T.InternalizedString, T.UniqueName);
    CheckSub(T.InternalizedString, T.Name);
    CheckSub(T.Symbol, T.UniqueName);
    CheckSub(T.Symbol, T.Name);
    CheckUnordered(T.String, T.UniqueName);
    CheckUnordered(T.String, T.Symbol);
    CheckUnordered(T.InternalizedString, T.Symbol);

    CheckSub(T.Object, T.Receiver);
    CheckSub(T.Proxy, T.Receiver);
943
    CheckSub(T.OtherObject, T.Object);
944
    CheckSub(T.OtherUndetectable, T.Object);
945
    CheckSub(T.OtherObject, T.Object);
946

947
    CheckUnordered(T.Object, T.Proxy);
948
    CheckUnordered(T.OtherObject, T.Undetectable);
949 950 951

    // Subtyping between concrete structural types

952
    CheckSub(T.ObjectClass, T.Object);
953
    CheckSub(T.ArrayClass, T.OtherObject);
954
    CheckSub(T.UninitializedClass, T.Internal);
955
    CheckUnordered(T.ObjectClass, T.ArrayClass);
956 957
    CheckUnordered(T.UninitializedClass, T.Null);
    CheckUnordered(T.UninitializedClass, T.Undefined);
958

959
    CheckSub(T.SmiConstant, T.SignedSmall);
960 961 962 963
    CheckSub(T.SmiConstant, T.Signed32);
    CheckSub(T.SmiConstant, T.Number);
    CheckSub(T.ObjectConstant1, T.Object);
    CheckSub(T.ObjectConstant2, T.Object);
964
    CheckSub(T.ArrayConstant, T.Object);
965 966
    CheckSub(T.ArrayConstant, T.OtherObject);
    CheckSub(T.ArrayConstant, T.Receiver);
967
    CheckSub(T.UninitializedConstant, T.Internal);
968
    CheckUnordered(T.ObjectConstant1, T.ObjectConstant2);
969
    CheckUnordered(T.ObjectConstant1, T.ArrayConstant);
970 971
    CheckUnordered(T.UninitializedConstant, T.Null);
    CheckUnordered(T.UninitializedConstant, T.Undefined);
972 973 974 975 976

    CheckUnordered(T.ObjectConstant1, T.ObjectClass);
    CheckUnordered(T.ObjectConstant2, T.ObjectClass);
    CheckUnordered(T.ObjectConstant1, T.ArrayClass);
    CheckUnordered(T.ObjectConstant2, T.ArrayClass);
977
    CheckUnordered(T.ArrayConstant, T.ObjectClass);
978

979 980
    CheckSub(T.NumberArray, T.OtherObject);
    CheckSub(T.NumberArray, T.Receiver);
981
    CheckSub(T.NumberArray, T.Object);
982 983
    CheckUnordered(T.StringArray, T.AnyArray);

984
    CheckSub(T.MethodFunction, T.Object);
985 986 987
    CheckSub(T.NumberFunction1, T.Object);
    CheckUnordered(T.SignedFunction1, T.NumberFunction1);
    CheckUnordered(T.NumberFunction1, T.NumberFunction2);
988
  }
989

990
  void NowIs() {
991
    // Least Element (Bottom): None->NowIs(T)
992
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
993
      Type* type = *it;
994
      CHECK(T.None->NowIs(type));
995 996
    }

997
    // Greatest Element (Top): T->NowIs(Any)
998
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
999
      Type* type = *it;
1000
      CHECK(type->NowIs(T.Any));
1001 1002
    }

1003
    // Bottom Uniqueness: T->NowIs(None) implies T = None
1004
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1005
      Type* type = *it;
1006
      if (type->NowIs(T.None)) CheckEqual(type, T.None);
1007 1008
    }

1009
    // Top Uniqueness: Any->NowIs(T) implies T = Any
1010
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1011
      Type* type = *it;
1012
      if (T.Any->NowIs(type)) CheckEqual(type, T.Any);
1013 1014
    }

1015
    // Reflexivity: T->NowIs(T)
1016
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1017
      Type* type = *it;
1018 1019 1020
      CHECK(type->NowIs(type));
    }

1021
    // Transitivity: T1->NowIs(T2) and T2->NowIs(T3) implies T1->NowIs(T3)
1022 1023 1024
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1025 1026 1027
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
1028
          CHECK(!(type1->NowIs(type2) && type2->NowIs(type3)) ||
1029 1030 1031 1032 1033
                type1->NowIs(type3));
        }
      }
    }

1034 1035 1036
    // Antisymmetry: T1->NowIs(T2) and T2->NowIs(T1) iff T1 = T2
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1037 1038
        Type* type1 = *it1;
        Type* type2 = *it2;
1039 1040 1041 1042 1043 1044
        CHECK((type1->NowIs(type2) && type2->NowIs(type1)) ==
              Equal(type1, type2));
      }
    }

    // T1->Is(T2) implies T1->NowIs(T2)
1045 1046
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1047 1048
        Type* type1 = *it1;
        Type* type2 = *it2;
1049 1050 1051 1052
        CHECK(!type1->Is(type2) || type1->NowIs(type2));
      }
    }

1053 1054 1055
    // Constant(V1)->NowIs(Constant(V2)) iff V1 = V2
    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
1056 1057
        Handle<i::Object> value1 = *vt1;
        Handle<i::Object> value2 = *vt2;
1058 1059
        Type* const_type1 = T.Constant(value1);
        Type* const_type2 = T.Constant(value2);
1060
        CHECK(const_type1->NowIs(const_type2) == (*value1 == *value2));
1061 1062 1063 1064 1065 1066 1067 1068
      }
    }

    // Class(M1)->NowIs(Class(M2)) iff M1 = M2
    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
        Handle<i::Map> map1 = *mt1;
        Handle<i::Map> map2 = *mt2;
1069 1070
        Type* class_type1 = T.Class(map1);
        Type* class_type2 = T.Class(map2);
1071
        CHECK(class_type1->NowIs(class_type2) == (*map1 == *map2));
1072 1073 1074 1075 1076 1077 1078 1079
      }
    }

    // Constant(V)->NowIs(Class(M)) iff V has map M
    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
        Handle<i::Map> map = *mt;
        Handle<i::Object> value = *vt;
1080 1081
        Type* const_type = T.Constant(value);
        Type* class_type = T.Class(map);
1082 1083
        CHECK((value->IsHeapObject() &&
               i::HeapObject::cast(*value)->map() == *map)
1084
              == const_type->NowIs(class_type));
1085 1086 1087
      }
    }

1088
    // Class(M)->NowIs(Constant(V)) never
1089 1090 1091 1092
    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
        Handle<i::Map> map = *mt;
        Handle<i::Object> value = *vt;
1093 1094
        Type* const_type = T.Constant(value);
        Type* class_type = T.Class(map);
1095
        CHECK(!class_type->NowIs(const_type));
1096 1097
      }
    }
1098 1099 1100
  }

  void Contains() {
1101
    // T->Contains(V) iff Constant(V)->Is(T)
1102 1103
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1104
        Type* type = *it;
1105
        Handle<i::Object> value = *vt;
1106
        Type* const_type = T.Constant(value);
1107
        CHECK(type->Contains(value) == const_type->Is(type));
1108 1109 1110 1111 1112
      }
    }
  }

  void NowContains() {
1113
    // T->NowContains(V) iff Constant(V)->NowIs(T)
1114 1115
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1116
        Type* type = *it;
1117
        Handle<i::Object> value = *vt;
1118
        Type* const_type = T.Constant(value);
1119
        CHECK(type->NowContains(value) == const_type->NowIs(type));
1120 1121 1122
      }
    }

1123
    // T->Contains(V) implies T->NowContains(V)
1124 1125
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1126
        Type* type = *it;
1127
        Handle<i::Object> value = *vt;
1128
        CHECK(!type->Contains(value) || type->NowContains(value));
1129 1130 1131
      }
    }

1132
    // NowOf(V)->Is(T) implies T->NowContains(V)
1133
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1134
      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
1135
        Type* type = *it;
1136
        Handle<i::Object> value = *vt;
1137
        Type* nowof_type = T.Of(value);
1138
        CHECK(!nowof_type->NowIs(type) || type->NowContains(value));
1139 1140 1141 1142
      }
    }
  }

1143
  void Maybe() {
1144
    // T->Maybe(Any) iff T inhabited
1145
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1146
      Type* type = *it;
1147
      CHECK(type->Maybe(T.Any) == type->IsInhabited());
1148 1149
    }

1150
    // T->Maybe(None) never
1151
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1152
      Type* type = *it;
1153
      CHECK(!type->Maybe(T.None));
1154 1155
    }

1156 1157
    // Reflexivity upto Inhabitation: T->Maybe(T) iff T inhabited
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1158
      Type* type = *it;
1159 1160 1161 1162
      CHECK(type->Maybe(type) == type->IsInhabited());
    }

    // Symmetry: T1->Maybe(T2) iff T2->Maybe(T1)
1163 1164
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1165 1166
        Type* type1 = *it1;
        Type* type2 = *it2;
1167 1168 1169 1170
        CHECK(type1->Maybe(type2) == type2->Maybe(type1));
      }
    }

1171
    // T1->Maybe(T2) implies T1, T2 inhabited
1172 1173
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1174 1175
        Type* type1 = *it1;
        Type* type2 = *it2;
1176 1177
        CHECK(!type1->Maybe(type2) ||
              (type1->IsInhabited() && type2->IsInhabited()));
1178 1179 1180
      }
    }

rossberg@chromium.org's avatar
rossberg@chromium.org committed
1181
    // T1->Maybe(T2) implies Intersect(T1, T2) inhabited
1182 1183
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1184 1185 1186
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* intersect12 = T.Intersect(type1, type2);
rossberg@chromium.org's avatar
rossberg@chromium.org committed
1187
        CHECK(!type1->Maybe(type2) || intersect12->IsInhabited());
1188 1189 1190 1191
      }
    }

    // T1->Is(T2) and T1 inhabited implies T1->Maybe(T2)
1192 1193
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1194 1195
        Type* type1 = *it1;
        Type* type2 = *it2;
1196 1197 1198 1199 1200 1201 1202 1203
        CHECK(!(type1->Is(type2) && type1->IsInhabited()) ||
              type1->Maybe(type2));
      }
    }

    // Constant(V1)->Maybe(Constant(V2)) iff V1 = V2
    for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) {
      for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) {
1204 1205
        Handle<i::Object> value1 = *vt1;
        Handle<i::Object> value2 = *vt2;
1206 1207
        Type* const_type1 = T.Constant(value1);
        Type* const_type2 = T.Constant(value2);
1208
        CHECK(const_type1->Maybe(const_type2) == (*value1 == *value2));
1209 1210
      }
    }
1211

1212 1213 1214 1215 1216
    // Class(M1)->Maybe(Class(M2)) iff M1 = M2
    for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) {
      for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) {
        Handle<i::Map> map1 = *mt1;
        Handle<i::Map> map2 = *mt2;
1217 1218
        Type* class_type1 = T.Class(map1);
        Type* class_type2 = T.Class(map2);
1219
        CHECK(class_type1->Maybe(class_type2) == (*map1 == *map2));
1220 1221 1222
      }
    }

1223
    // Constant(V)->Maybe(Class(M)) never
1224 1225
    // This does NOT hold!
    /*
1226 1227 1228 1229
    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
        Handle<i::Map> map = *mt;
        Handle<i::Object> value = *vt;
1230 1231
        Type* const_type = T.Constant(value);
        Type* class_type = T.Class(map);
1232
        CHECK(!const_type->Maybe(class_type));
1233 1234
      }
    }
1235
    */
1236

1237
    // Class(M)->Maybe(Constant(V)) never
1238 1239
    // This does NOT hold!
    /*
1240 1241 1242 1243
    for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) {
      for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
        Handle<i::Map> map = *mt;
        Handle<i::Object> value = *vt;
1244 1245
        Type* const_type = T.Constant(value);
        Type* class_type = T.Class(map);
1246
        CHECK(!class_type->Maybe(const_type));
1247 1248
      }
    }
1249
    */
1250 1251

    // Basic types
1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268
    CheckDisjoint(T.Boolean, T.Null);
    CheckDisjoint(T.Undefined, T.Null);
    CheckDisjoint(T.Boolean, T.Undefined);
    CheckOverlap(T.SignedSmall, T.Number);
    CheckOverlap(T.NaN, T.Number);
    CheckDisjoint(T.Signed32, T.NaN);
    CheckOverlap(T.UniqueName, T.Name);
    CheckOverlap(T.String, T.Name);
    CheckOverlap(T.InternalizedString, T.String);
    CheckOverlap(T.InternalizedString, T.UniqueName);
    CheckOverlap(T.InternalizedString, T.Name);
    CheckOverlap(T.Symbol, T.UniqueName);
    CheckOverlap(T.Symbol, T.Name);
    CheckOverlap(T.String, T.UniqueName);
    CheckDisjoint(T.String, T.Symbol);
    CheckDisjoint(T.InternalizedString, T.Symbol);
    CheckOverlap(T.Object, T.Receiver);
1269
    CheckOverlap(T.OtherObject, T.Object);
1270 1271
    CheckOverlap(T.Proxy, T.Receiver);
    CheckDisjoint(T.Object, T.Proxy);
1272

1273
    // Structural types
1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284
    CheckOverlap(T.ObjectClass, T.Object);
    CheckOverlap(T.ArrayClass, T.Object);
    CheckOverlap(T.ObjectClass, T.ObjectClass);
    CheckOverlap(T.ArrayClass, T.ArrayClass);
    CheckDisjoint(T.ObjectClass, T.ArrayClass);
    CheckOverlap(T.SmiConstant, T.SignedSmall);
    CheckOverlap(T.SmiConstant, T.Signed32);
    CheckOverlap(T.SmiConstant, T.Number);
    CheckOverlap(T.ObjectConstant1, T.Object);
    CheckOverlap(T.ObjectConstant2, T.Object);
    CheckOverlap(T.ArrayConstant, T.Object);
1285
    CheckOverlap(T.ArrayConstant, T.Receiver);
1286 1287 1288
    CheckOverlap(T.ObjectConstant1, T.ObjectConstant1);
    CheckDisjoint(T.ObjectConstant1, T.ObjectConstant2);
    CheckDisjoint(T.ObjectConstant1, T.ArrayConstant);
1289 1290 1291 1292
    CheckOverlap(T.ObjectConstant1, T.ArrayClass);
    CheckOverlap(T.ObjectConstant2, T.ArrayClass);
    CheckOverlap(T.ArrayConstant, T.ObjectClass);
    CheckOverlap(T.NumberArray, T.Receiver);
1293 1294
    CheckDisjoint(T.NumberArray, T.AnyArray);
    CheckDisjoint(T.NumberArray, T.StringArray);
1295
    CheckOverlap(T.MethodFunction, T.Object);
1296 1297 1298 1299 1300 1301
    CheckDisjoint(T.SignedFunction1, T.NumberFunction1);
    CheckDisjoint(T.SignedFunction1, T.NumberFunction2);
    CheckDisjoint(T.NumberFunction1, T.NumberFunction2);
    CheckDisjoint(T.SignedFunction1, T.MethodFunction);
    CheckOverlap(T.ObjectConstant1, T.ObjectClass);  // !!!
    CheckOverlap(T.ObjectConstant2, T.ObjectClass);  // !!!
1302
    CheckOverlap(T.NumberClass, T.Intersect(T.Number, T.Tagged));  // !!!
1303
  }
1304

1305
  void Union1() {
1306 1307
    // Identity: Union(T, None) = T
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1308 1309
      Type* type = *it;
      Type* union_type = T.Union(type, T.None);
1310 1311 1312 1313 1314
      CheckEqual(union_type, type);
    }

    // Domination: Union(T, Any) = Any
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1315 1316
      Type* type = *it;
      Type* union_type = T.Union(type, T.Any);
1317 1318 1319 1320 1321
      CheckEqual(union_type, T.Any);
    }

    // Idempotence: Union(T, T) = T
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1322 1323
      Type* type = *it;
      Type* union_type = T.Union(type, type);
1324 1325
      CheckEqual(union_type, type);
    }
1326

1327 1328 1329
    // Commutativity: Union(T1, T2) = Union(T2, T1)
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1330 1331 1332 1333
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* union12 = T.Union(type1, type2);
        Type* union21 = T.Union(type2, type1);
1334 1335 1336 1337 1338
        CheckEqual(union12, union21);
      }
    }

    // Associativity: Union(T1, Union(T2, T3)) = Union(Union(T1, T2), T3)
1339 1340 1341
    // This does NOT hold!  For example:
    // (Unsigned32 \/ Range(0,5)) \/ Range(-5,0) = Unsigned32 \/ Range(-5,0)
    // Unsigned32 \/ (Range(0,5) \/ Range(-5,0)) = Unsigned32 \/ Range(-5,5)
1342
    /*
1343 1344 1345
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1346 1347 1348 1349 1350 1351 1352
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* union12 = T.Union(type1, type2);
          Type* union23 = T.Union(type2, type3);
          Type* union1_23 = T.Union(type1, union23);
          Type* union12_3 = T.Union(union12, type3);
1353 1354 1355 1356
          CheckEqual(union1_23, union12_3);
        }
      }
    }
1357
    */
1358 1359 1360 1361

    // Meet: T1->Is(Union(T1, T2)) and T2->Is(Union(T1, T2))
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1362 1363 1364
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* union12 = T.Union(type1, type2);
1365 1366 1367 1368 1369 1370 1371 1372
        CHECK(type1->Is(union12));
        CHECK(type2->Is(union12));
      }
    }

    // Upper Boundedness: T1->Is(T2) implies Union(T1, T2) = T2
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1373 1374 1375
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* union12 = T.Union(type1, type2);
1376 1377 1378 1379 1380
        if (type1->Is(type2)) CheckEqual(union12, type2);
      }
    }

    // Monotonicity: T1->Is(T2) implies Union(T1, T3)->Is(Union(T2, T3))
1381 1382 1383
    // This does NOT hold.  For example:
    // Range(-5,-1) <= Signed32
    // Range(-5,-1) \/ Range(1,5) = Range(-5,5) </= Signed32 \/ Range(1,5)
1384
    /*
1385 1386 1387
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1388 1389 1390 1391 1392
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* union13 = T.Union(type1, type3);
          Type* union23 = T.Union(type2, type3);
1393 1394 1395 1396
          CHECK(!type1->Is(type2) || union13->Is(union23));
        }
      }
    }
1397 1398
    */
  }
1399

1400
  void Union2() {
1401
    // Monotonicity: T1->Is(T3) and T2->Is(T3) implies Union(T1, T2)->Is(T3)
1402 1403 1404 1405
    // This does NOT hold.  For example:
    // Range(-2^33, -2^33) <= OtherNumber
    // Range(2^33, 2^33) <= OtherNumber
    // Range(-2^33, 2^33) </= OtherNumber
1406
    /*
1407 1408 1409
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1410 1411 1412 1413
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* union12 = T.Union(type1, type2);
1414 1415 1416 1417
          CHECK(!(type1->Is(type3) && type2->Is(type3)) || union12->Is(type3));
        }
      }
    }
1418 1419
    */
  }
1420

1421
  void Union3() {
1422 1423
    // Monotonicity: T1->Is(T2) or T1->Is(T3) implies T1->Is(Union(T2, T3))
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1424
      HandleScope scope(isolate);
1425
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1426
        for (TypeIterator it3 = it2; it3 != T.types.end(); ++it3) {
1427 1428 1429 1430
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* union23 = T.Union(type2, type3);
1431 1432 1433 1434
          CHECK(!(type1->Is(type2) || type1->Is(type3)) || type1->Is(union23));
        }
      }
    }
1435
  }
1436

1437
  void Union4() {
1438 1439
    // Class-class
    CheckSub(T.Union(T.ObjectClass, T.ArrayClass), T.Object);
1440 1441
    CheckOverlap(T.Union(T.ObjectClass, T.ArrayClass), T.OtherObject);
    CheckOverlap(T.Union(T.ObjectClass, T.ArrayClass), T.Receiver);
1442
    CheckDisjoint(T.Union(T.ObjectClass, T.ArrayClass), T.Number);
1443 1444 1445

    // Constant-constant
    CheckSub(T.Union(T.ObjectConstant1, T.ObjectConstant2), T.Object);
1446
    CheckOverlap(T.Union(T.ObjectConstant1, T.ArrayConstant), T.OtherObject);
1447 1448
    CheckUnordered(
        T.Union(T.ObjectConstant1, T.ObjectConstant2), T.ObjectClass);
1449
    CheckOverlap(T.Union(T.ObjectConstant1, T.ArrayConstant), T.OtherObject);
1450
    CheckDisjoint(
1451 1452 1453
        T.Union(T.ObjectConstant1, T.ArrayConstant), T.Number);
    CheckOverlap(
        T.Union(T.ObjectConstant1, T.ArrayConstant), T.ObjectClass);  // !!!
1454

1455
    // Bitset-array
1456
    CHECK(this->IsBitset(T.Union(T.AnyArray, T.Receiver)));
1457
    CHECK(this->IsUnion(T.Union(T.NumberArray, T.Number)));
1458

1459 1460 1461
    CheckEqual(T.Union(T.AnyArray, T.Receiver), T.Receiver);
    CheckEqual(T.Union(T.AnyArray, T.OtherObject), T.OtherObject);
    CheckUnordered(T.Union(T.AnyArray, T.String), T.Receiver);
1462 1463
    CheckOverlap(T.Union(T.NumberArray, T.String), T.Object);
    CheckDisjoint(T.Union(T.NumberArray, T.String), T.Number);
1464 1465

    // Bitset-function
1466
    CHECK(this->IsBitset(T.Union(T.MethodFunction, T.Object)));
1467 1468
    CHECK(this->IsUnion(T.Union(T.NumberFunction1, T.Number)));

1469 1470
    CheckEqual(T.Union(T.MethodFunction, T.Object), T.Object);
    CheckUnordered(T.Union(T.NumberFunction1, T.String), T.Object);
1471 1472
    CheckOverlap(T.Union(T.NumberFunction2, T.String), T.Object);
    CheckDisjoint(T.Union(T.NumberFunction1, T.String), T.Number);
1473

1474
    // Bitset-class
1475 1476
    CheckSub(T.Union(T.ObjectClass, T.SignedSmall),
             T.Union(T.Object, T.Number));
1477 1478
    CheckSub(T.Union(T.ObjectClass, T.OtherObject), T.Object);
    CheckUnordered(T.Union(T.ObjectClass, T.String), T.OtherObject);
1479 1480
    CheckOverlap(T.Union(T.ObjectClass, T.String), T.Object);
    CheckDisjoint(T.Union(T.ObjectClass, T.String), T.Number);
1481 1482 1483 1484

    // Bitset-constant
    CheckSub(
        T.Union(T.ObjectConstant1, T.Signed32), T.Union(T.Object, T.Number));
1485 1486
    CheckSub(T.Union(T.ObjectConstant1, T.OtherObject), T.Object);
    CheckUnordered(T.Union(T.ObjectConstant1, T.String), T.OtherObject);
1487 1488
    CheckOverlap(T.Union(T.ObjectConstant1, T.String), T.Object);
    CheckDisjoint(T.Union(T.ObjectConstant1, T.String), T.Number);
1489 1490 1491 1492

    // Class-constant
    CheckSub(T.Union(T.ObjectConstant1, T.ArrayClass), T.Object);
    CheckUnordered(T.ObjectClass, T.Union(T.ObjectConstant1, T.ArrayClass));
1493 1494
    CheckSub(T.Union(T.ObjectConstant1, T.ArrayClass),
             T.Union(T.Receiver, T.Object));
1495
    CheckUnordered(T.Union(T.ObjectConstant1, T.ArrayClass), T.ArrayConstant);
1496
    CheckOverlap(T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectConstant2);
1497 1498
    CheckOverlap(
        T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectClass);  // !!!
1499 1500 1501

    // Bitset-union
    CheckSub(
1502
        T.NaN,
1503 1504
        T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Number));
    CheckSub(
1505
        T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Signed32),
1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522
        T.Union(T.ObjectConstant1, T.Union(T.Number, T.ArrayClass)));

    // Class-union
    CheckSub(
        T.Union(T.ObjectClass, T.Union(T.ObjectConstant1, T.ObjectClass)),
        T.Object);
    CheckEqual(
        T.Union(T.Union(T.ArrayClass, T.ObjectConstant2), T.ArrayClass),
        T.Union(T.ArrayClass, T.ObjectConstant2));

    // Constant-union
    CheckEqual(
        T.Union(
            T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)),
        T.Union(T.ObjectConstant2, T.ObjectConstant1));
    CheckEqual(
        T.Union(
1523
            T.Union(T.ArrayConstant, T.ObjectConstant2), T.ObjectConstant1),
1524
        T.Union(
1525
            T.ObjectConstant2, T.Union(T.ArrayConstant, T.ObjectConstant1)));
1526

1527 1528
    // Array-union
    CheckEqual(
1529 1530
        T.Union(T.AnyArray, T.Union(T.NumberArray, T.AnyArray)),
        T.Union(T.AnyArray, T.NumberArray));
1531
    CheckSub(T.Union(T.AnyArray, T.NumberArray), T.OtherObject);
1532 1533 1534 1535 1536

    // Function-union
    CheckEqual(
        T.Union(T.NumberFunction1, T.NumberFunction2),
        T.Union(T.NumberFunction2, T.NumberFunction1));
1537
    CheckSub(T.Union(T.SignedFunction1, T.MethodFunction), T.Object);
1538

1539 1540 1541 1542 1543 1544
    // Union-union
    CheckEqual(
        T.Union(
            T.Union(T.ObjectConstant2, T.ObjectConstant1),
            T.Union(T.ObjectConstant1, T.ObjectConstant2)),
        T.Union(T.ObjectConstant2, T.ObjectConstant1));
1545
    CheckEqual(T.Union(T.Union(T.Number, T.ArrayClass),
1546 1547
                       T.Union(T.SignedSmall, T.Receiver)),
               T.Union(T.Number, T.Receiver));
1548
  }
1549

1550
  void Intersect() {
1551 1552
    // Identity: Intersect(T, Any) = T
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1553 1554
      Type* type = *it;
      Type* intersect_type = T.Intersect(type, T.Any);
1555 1556
      CheckEqual(intersect_type, type);
    }
1557

1558 1559
    // Domination: Intersect(T, None) = None
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1560 1561
      Type* type = *it;
      Type* intersect_type = T.Intersect(type, T.None);
1562 1563
      CheckEqual(intersect_type, T.None);
    }
1564

1565 1566
    // Idempotence: Intersect(T, T) = T
    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
1567 1568
      Type* type = *it;
      Type* intersect_type = T.Intersect(type, type);
1569 1570
      CheckEqual(intersect_type, type);
    }
1571

1572 1573 1574
    // Commutativity: Intersect(T1, T2) = Intersect(T2, T1)
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1575 1576 1577 1578
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* intersect12 = T.Intersect(type1, type2);
        Type* intersect21 = T.Intersect(type2, type1);
1579 1580 1581
        CheckEqual(intersect12, intersect21);
      }
    }
1582

1583 1584
    // Associativity:
    // Intersect(T1, Intersect(T2, T3)) = Intersect(Intersect(T1, T2), T3)
1585 1586 1587 1588 1589
    // This does NOT hold.  For example:
    // (Class(..stringy1..) /\ Class(..stringy2..)) /\ Constant(..string..) =
    // None
    // Class(..stringy1..) /\ (Class(..stringy2..) /\ Constant(..string..)) =
    // Constant(..string..)
1590
    /*
1591 1592 1593
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1594 1595 1596 1597 1598 1599 1600
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* intersect12 = T.Intersect(type1, type2);
          Type* intersect23 = T.Intersect(type2, type3);
          Type* intersect1_23 = T.Intersect(type1, intersect23);
          Type* intersect12_3 = T.Intersect(intersect12, type3);
1601 1602 1603 1604
          CheckEqual(intersect1_23, intersect12_3);
        }
      }
    }
1605
    */
1606

1607
    // Join: Intersect(T1, T2)->Is(T1) and Intersect(T1, T2)->Is(T2)
1608 1609 1610 1611 1612
    // This does NOT hold.  For example:
    // Class(..stringy..) /\ Constant(..string..) = Constant(..string..)
    // Currently, not even the disjunction holds:
    // Class(Internal/TaggedPtr) /\ (Any/Untagged \/ Context(..)) =
    // Class(Internal/TaggedPtr) \/ Context(..)
1613
    /*
1614 1615
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1616 1617 1618
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* intersect12 = T.Intersect(type1, type2);
1619 1620 1621 1622
        CHECK(intersect12->Is(type1));
        CHECK(intersect12->Is(type2));
      }
    }
1623
    */
1624

1625 1626 1627
    // Lower Boundedness: T1->Is(T2) implies Intersect(T1, T2) = T1
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1628 1629 1630
        Type* type1 = *it1;
        Type* type2 = *it2;
        Type* intersect12 = T.Intersect(type1, type2);
1631 1632 1633 1634 1635
        if (type1->Is(type2)) CheckEqual(intersect12, type1);
      }
    }

    // Monotonicity: T1->Is(T2) implies Intersect(T1, T3)->Is(Intersect(T2, T3))
1636 1637 1638 1639
    // This does NOT hold.  For example:
    // Class(OtherObject/TaggedPtr) <= Any/TaggedPtr
    // Class(OtherObject/TaggedPtr) /\ Any/UntaggedInt1 = Class(..)
    // Any/TaggedPtr /\ Any/UntaggedInt1 = None
1640
    /*
1641 1642 1643
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1644 1645 1646 1647 1648
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* intersect13 = T.Intersect(type1, type3);
          Type* intersect23 = T.Intersect(type2, type3);
1649 1650 1651 1652
          CHECK(!type1->Is(type2) || intersect13->Is(intersect23));
        }
      }
    }
1653
    */
1654

1655
    // Monotonicity: T1->Is(T3) or T2->Is(T3) implies Intersect(T1, T2)->Is(T3)
1656 1657 1658 1659
    // This does NOT hold.  For example:
    // Class(..stringy..) <= Class(..stringy..)
    // Class(..stringy..) /\ Constant(..string..) = Constant(..string..)
    // Constant(..string..) </= Class(..stringy..)
1660
    /*
1661 1662 1663
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1664 1665 1666 1667
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* intersect12 = T.Intersect(type1, type2);
1668 1669 1670 1671 1672
          CHECK(!(type1->Is(type3) || type2->Is(type3)) ||
                intersect12->Is(type3));
        }
      }
    }
1673
    */
1674 1675 1676

    // Monotonicity: T1->Is(T2) and T1->Is(T3) implies T1->Is(Intersect(T2, T3))
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1677
      HandleScope scope(isolate);
1678 1679
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1680 1681 1682 1683
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* intersect23 = T.Intersect(type2, type3);
1684 1685 1686 1687 1688 1689 1690
          CHECK(!(type1->Is(type2) && type1->Is(type3)) ||
                type1->Is(intersect23));
        }
      }
    }

    // Bitset-class
1691
    CheckEqual(T.Intersect(T.ObjectClass, T.Object), T.ObjectClass);
1692
    CheckEqual(T.Semantic(T.Intersect(T.ObjectClass, T.Number)), T.None);
1693

1694
    // Bitset-array
1695
    CheckEqual(T.Intersect(T.NumberArray, T.Object), T.NumberArray);
1696
    CheckEqual(T.Semantic(T.Intersect(T.AnyArray, T.Proxy)), T.None);
1697 1698 1699

    // Bitset-function
    CheckEqual(T.Intersect(T.MethodFunction, T.Object), T.MethodFunction);
1700
    CheckEqual(T.Semantic(T.Intersect(T.NumberFunction1, T.Proxy)), T.None);
1701 1702 1703 1704 1705

    // Bitset-union
    CheckEqual(
        T.Intersect(T.Object, T.Union(T.ObjectConstant1, T.ObjectClass)),
        T.Union(T.ObjectConstant1, T.ObjectClass));
1706 1707 1708
    CheckEqual(T.Semantic(T.Intersect(T.Union(T.ArrayClass, T.ObjectConstant1),
                                      T.Number)),
               T.None);
1709

1710
    // Class-constant
1711
    CHECK(T.Intersect(T.ObjectConstant1, T.ObjectClass)->IsInhabited());  // !!!
1712
    CHECK(T.Intersect(T.ArrayClass, T.ObjectConstant2)->IsInhabited());
1713 1714 1715

    // Array-union
    CheckEqual(
1716 1717
        T.Intersect(T.NumberArray, T.Union(T.NumberArray, T.ArrayClass)),
        T.NumberArray);
1718 1719 1720
    CheckEqual(
        T.Intersect(T.AnyArray, T.Union(T.Object, T.SmiConstant)),
        T.AnyArray);
1721 1722 1723
    CHECK(
        !T.Intersect(T.Union(T.AnyArray, T.ArrayConstant), T.NumberArray)
            ->IsInhabited());
1724 1725 1726 1727 1728 1729 1730 1731

    // Function-union
    CheckEqual(
        T.Intersect(T.MethodFunction, T.Union(T.String, T.MethodFunction)),
        T.MethodFunction);
    CheckEqual(
        T.Intersect(T.NumberFunction1, T.Union(T.Object, T.SmiConstant)),
        T.NumberFunction1);
1732 1733 1734
    CHECK(
        !T.Intersect(T.Union(T.MethodFunction, T.Name), T.NumberFunction2)
            ->IsInhabited());
1735

1736 1737 1738 1739 1740 1741 1742
    // Class-union
    CheckEqual(
        T.Intersect(T.ArrayClass, T.Union(T.ObjectConstant2, T.ArrayClass)),
        T.ArrayClass);
    CheckEqual(
        T.Intersect(T.ArrayClass, T.Union(T.Object, T.SmiConstant)),
        T.ArrayClass);
1743
    CHECK(
1744 1745
        T.Intersect(T.Union(T.ObjectClass, T.ArrayConstant), T.ArrayClass)
            ->IsInhabited());  // !!!
1746 1747 1748 1749 1750 1751 1752 1753 1754

    // Constant-union
    CheckEqual(
        T.Intersect(
            T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)),
        T.ObjectConstant1);
    CheckEqual(
        T.Intersect(T.SmiConstant, T.Union(T.Number, T.ObjectConstant2)),
        T.SmiConstant);
1755
    CHECK(
1756
        T.Intersect(
1757
            T.Union(T.ArrayConstant, T.ObjectClass), T.ObjectConstant1)
1758
                ->IsInhabited());  // !!!
1759 1760

    // Union-union
1761
    CheckEqual(T.Intersect(T.Union(T.Number, T.ArrayClass),
1762
                           T.Union(T.SignedSmall, T.Receiver)),
1763
               T.Union(T.SignedSmall, T.ArrayClass));
1764 1765 1766
    CheckEqual(T.Intersect(T.Union(T.Number, T.ObjectClass),
                           T.Union(T.Signed32, T.OtherObject)),
               T.Union(T.Signed32, T.ObjectClass));
1767 1768 1769 1770 1771 1772 1773 1774
    CheckEqual(
        T.Intersect(
            T.Union(T.ObjectConstant2, T.ObjectConstant1),
            T.Union(T.ObjectConstant1, T.ObjectConstant2)),
        T.Union(T.ObjectConstant2, T.ObjectConstant1));
    CheckEqual(
        T.Intersect(
            T.Union(
1775 1776
                T.ArrayClass,
                T.Union(T.ObjectConstant2, T.ObjectConstant1)),
1777 1778
            T.Union(
                T.ObjectConstant1,
1779
                T.Union(T.ArrayConstant, T.ObjectConstant2))),
1780 1781 1782
        T.Union(
            T.ArrayConstant,
            T.Union(T.ObjectConstant2, T.ObjectConstant1)));  // !!!
1783
  }
1784

1785
  void Distributivity() {
1786
    // Union(T1, Intersect(T2, T3)) = Intersect(Union(T1, T2), Union(T1, T3))
1787 1788 1789 1790 1791
    // This does NOT hold.  For example:
    // Untagged \/ (Untagged /\ Class(../Tagged)) = Untagged \/ Class(../Tagged)
    // (Untagged \/ Untagged) /\ (Untagged \/ Class(../Tagged)) =
    // Untagged /\ (Untagged \/ Class(../Tagged)) = Untagged
    // because Untagged <= Untagged \/ Class(../Tagged)
1792
    /*
1793 1794 1795
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1796 1797 1798 1799 1800 1801 1802 1803
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* union12 = T.Union(type1, type2);
          Type* union13 = T.Union(type1, type3);
          Type* intersect23 = T.Intersect(type2, type3);
          Type* union1_23 = T.Union(type1, intersect23);
          Type* intersect12_13 = T.Intersect(union12, union13);
1804 1805 1806 1807
          CHECK(Equal(union1_23, intersect12_13));
        }
      }
    }
1808
    */
1809 1810

    // Intersect(T1, Union(T2, T3)) = Union(Intersect(T1, T2), Intersect(T1,T3))
1811 1812 1813 1814
    // This does NOT hold.  For example:
    // Untagged /\ (Untagged \/ Class(../Tagged)) = Untagged
    // (Untagged /\ Untagged) \/ (Untagged /\ Class(../Tagged)) =
    // Untagged \/ Class(../Tagged)
1815
    /*
1816 1817 1818
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
        for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) {
1819 1820 1821 1822 1823 1824 1825 1826
          Type* type1 = *it1;
          Type* type2 = *it2;
          Type* type3 = *it3;
          Type* intersect12 = T.Intersect(type1, type2);
          Type* intersect13 = T.Intersect(type1, type3);
          Type* union23 = T.Union(type2, type3);
          Type* intersect1_23 = T.Intersect(type1, union23);
          Type* union12_13 = T.Union(intersect12, intersect13);
1827 1828 1829 1830
          CHECK(Equal(intersect1_23, union12_13));
        }
      }
    }
1831
    */
1832 1833
  }

1834 1835 1836
  void GetRange() {
    // GetRange(Range(a, b)) = Range(a, b).
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
1837
      Type* type1 = *it1;
1838
      if (type1->IsRange()) {
1839
        RangeType* range = type1->GetRange()->AsRange();
1840 1841
        CHECK(type1->Min() == range->Min());
        CHECK(type1->Max() == range->Max());
1842 1843 1844 1845 1846 1847
      }
    }

    // GetRange(Union(Constant(x), Range(min,max))) == Range(min, max).
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1848 1849
        Type* type1 = *it1;
        Type* type2 = *it2;
1850
        if (type1->IsConstant() && type2->IsRange()) {
1851
          Type* u = T.Union(type1, type2);
1852

1853 1854
          CHECK(type2->Min() == u->GetRange()->Min());
          CHECK(type2->Max() == u->GetRange()->Max());
1855 1856 1857 1858 1859
        }
      }
    }
  }

1860 1861 1862
  void HTypeFromType() {
    for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
      for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
1863 1864
        Type* type1 = *it1;
        Type* type2 = *it2;
1865 1866
        HType htype1 = HType::FromType(type1);
        HType htype2 = HType::FromType(type2);
1867 1868 1869 1870
        CHECK(!type1->Is(type2) || htype1.IsSubtypeOf(htype2));
      }
    }
  }
1871 1872
};

1873
TEST(IsSomeType_zone) { Tests().IsSomeType(); }
1874

1875
TEST(PointwiseRepresentation_zone) { Tests().PointwiseRepresentation(); }
1876

1877
TEST(BitsetType_zone) { Tests().Bitset(); }
1878

1879
TEST(ClassType_zone) { Tests().Class(); }
1880

1881
TEST(ConstantType_zone) { Tests().Constant(); }
1882

1883
TEST(RangeType_zone) { Tests().Range(); }
1884

1885
TEST(ArrayType_zone) { Tests().Array(); }
1886

1887
TEST(FunctionType_zone) { Tests().Function(); }
1888

1889
TEST(Of_zone) { Tests().Of(); }
1890

1891
TEST(NowOf_zone) { Tests().NowOf(); }
1892

1893
TEST(MinMax_zone) { Tests().MinMax(); }
1894

1895
TEST(BitsetGlb_zone) { Tests().BitsetGlb(); }
1896

1897
TEST(BitsetLub_zone) { Tests().BitsetLub(); }
1898

1899
TEST(Is1_zone) { Tests().Is1(); }
1900

1901
TEST(Is2_zone) { Tests().Is2(); }
1902

1903
TEST(NowIs_zone) { Tests().NowIs(); }
1904

1905
TEST(Contains_zone) { Tests().Contains(); }
1906

1907
TEST(NowContains_zone) { Tests().NowContains(); }
1908

1909
TEST(Maybe_zone) { Tests().Maybe(); }
1910

1911
TEST(Union1_zone) { Tests().Union1(); }
1912

1913
TEST(Union2_zone) { Tests().Union2(); }
1914

1915
TEST(Union3_zone) { Tests().Union3(); }
1916

1917
TEST(Union4_zone) { Tests().Union4(); }
1918

1919
TEST(Intersect_zone) { Tests().Intersect(); }
1920

1921
TEST(Distributivity_zone) { Tests().Distributivity(); }
1922

1923
TEST(GetRange_zone) { Tests().GetRange(); }
1924

1925
TEST(HTypeFromType_zone) { Tests().HTypeFromType(); }