Add some tests about range types.

test/cctest/test-types.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include <vector>
 
 #include "src/hydrogen-types.h"
 #include "src/isolate-inl.h"
 #include "src/types.h"
 #include "test/cctest/cctest.h"
 
 using namespace v8::internal;
 
+
 // Testing auxiliaries (breaking the Type abstraction).
+
+
+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());
+}
+
+
 typedef uint32_t bitset;
 
+
 struct ZoneRep {
   typedef void* Struct;
 
   static bool IsStruct(Type* t, int tag) {
     return !IsBitset(t) && reinterpret_cast<intptr_t>(AsStruct(t)[0]) == tag;
   }
   static bool IsBitset(Type* t) { return reinterpret_cast<uintptr_t>(t) & 1; }
   static bool IsUnion(Type* t) { return IsStruct(t, 6); }
 
   static Struct* AsStruct(Type* t) {
@@ skipping 468 matching lines @@
     // Functionality & Injectivity: Class(M1) = 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;
         TypeHandle type1 = T.Class(map1);
         TypeHandle type2 = T.Class(map2);
         CHECK(Equal(type1, type2) == (*map1 == *map2));
       }
     }
+
+    // Subtyping: Class(M1)->Is(Class(M2)) iff M1 = M2

[rossberg, 2014/09/24 12:59:09]

Hm, I'd rather leave the subtyping tests where they were. Some layering is
useful, and tests like Class and Constant are meant to just test the basic type
constructors, not anything about relations defined on top. (Which was also the
reason why I did not use subtyping in the Equal predicate originally.)

[neis1, 2014/09/24 15:12:08]

I changed it back now.  But if you look at e.g. Constant(), you'll see that
there already are a couple dozen subtyping tests in there.

+    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;
+        TypeHandle class_type1 = T.Class(map1);
+        TypeHandle class_type2 = T.Class(map2);
+        CHECK(class_type1->Is(class_type2) == (*map1 == *map2));
+      }
+    }
   }
 
   void Constant() {
     // Constructor
     for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
       Handle<i::Object> value = *vt;
       TypeHandle type = T.Constant(value);
       CHECK(type->IsConstant());
     }
 
     // Value attribute
     for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
       Handle<i::Object> value = *vt;
       TypeHandle type = T.Constant(value);
       CHECK(*value == *type->AsConstant()->Value());
     }
 
     // Functionality & Injectivity: Constant(V1) = 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;
         TypeHandle type1 = T.Constant(value1);
         TypeHandle type2 = T.Constant(value2);
         CHECK(Equal(type1, type2) == (*value1 == *value2));
       }
     }
 
+    // Subtyping: 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;
+        TypeHandle const_type1 = T.Constant(value1);
+        TypeHandle const_type2 = T.Constant(value2);
+        CHECK(const_type1->Is(const_type2) == (*value1 == *value2));
+      }
+    }
+
     // 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));
     CHECK(T.Constant(fac->NewNumber(-1))->Is(T.OtherSignedSmall));
     CHECK(T.Constant(fac->NewNumber(-0x3fffffff))->Is(T.OtherSignedSmall));
     CHECK(T.Constant(fac->NewNumber(-0x40000000))->Is(T.OtherSignedSmall));
     if (SmiValuesAre31Bits()) {
       CHECK(T.Constant(fac->NewNumber(0x40000000))->Is(T.OtherUnsigned31));
@@ skipping 67 matching lines @@
             i::Handle<i::Object> max2 = *j2;
             if (min1->Number() > max1->Number()) std::swap(min1, max1);
             if (min2->Number() > max2->Number()) std::swap(min2, max2);
             TypeHandle type1 = T.Range(min1, max1);
             TypeHandle type2 = T.Range(min2, max2);
             CHECK(Equal(type1, type2) == (*min1 == *min2 && *max1 == *max2));
           }
         }
       }
     }
+
+    // Subtyping:
+    // Range(x1, y1)->Is(Range(x2, y2)) iff x1 >= x2 /\ y1 <= y2
+    for (ValueIterator i1 = T.integers.begin();
+        i1 != T.integers.end(); ++i1) {
+      for (ValueIterator j1 = i1;
+          j1 != T.integers.end(); ++j1) {
+        for (ValueIterator i2 = T.integers.begin();
+             i2 != T.integers.end(); ++i2) {
+          for (ValueIterator j2 = i2;
+               j2 != T.integers.end(); ++j2) {
+            i::Handle<i::Object> min1 = *i1;
+            i::Handle<i::Object> max1 = *j1;
+            i::Handle<i::Object> min2 = *i2;
+            i::Handle<i::Object> max2 = *j2;
+            if (min1->Number() > max1->Number()) std::swap(min1, max1);
+            if (min2->Number() > max2->Number()) std::swap(min2, max2);
+            TypeHandle type1 = T.Range(min1, max1);
+            TypeHandle type2 = T.Range(min2, max2);
+            CHECK(type1->Is(type2) ==
+                (min2->Number() <= min1->Number() &&
+                 max1->Number() <= max2->Number()));
+          }
+        }
+      }
+    }
+
+    // Subtyping: If IsInteger(v) then Constant(v)->Is(Range(v, v)).
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (type->IsConstant() && IsInteger(*type->AsConstant()->Value())) {
+        CHECK(type->Is(
+            T.Range(type->AsConstant()->Value(), type->AsConstant()->Value())));
+      }
+    }
+
+    // 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) {
+        TypeHandle type1 = *it1;
+        TypeHandle type2 = *it2;
+        if (type1->IsConstant() && type2->IsRange() && type1->Is(type2)) {
+          double x = type1->AsConstant()->Value()->Number();
+          double min = type2->AsRange()->Min()->Number();
+          double max = type2->AsRange()->Max()->Number();
+          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) {
+      TypeHandle type = *it;
+      if (type->IsRange()) {
+        TypeHandle lub = Rep::BitsetType::New(
+            Rep::BitsetType::Lub(type), T.region());
+        CHECK(lub->Is(T.Union(T.Integral32, T.OtherNumber)));
+      }
+    }
+
+    // If b is regular numberic bitset, then b->Min() and b->Max() are integers.

[rossberg, 2014/09/24 12:59:09]

How about introducing a separate test MinMax for testing the general properties
of the Min and Max methods?

Typo: numeric

[neis1, 2014/09/24 15:12:08]

Done.

+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (this->IsBitset(type) && type->Is(T.Number) &&
+          !type->Is(T.None) && !type->Is(T.NaN)) {
+        CHECK(IsInteger(type->Min()) && IsInteger(type->Max()));
+      }
+    }
+
+    // If b is regular numberic bitset, then Range(b->Min(), b->Max())->Is(b).

[rossberg, 2014/09/24 12:59:09]

Typo

[neis1, 2014/09/24 15:12:08]

Done.

+    // TODO(neis): Need to ignore representation for this to be true.
+    /*
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (this->IsBitset(type) && type->Is(T.Number) &&
+          !type->Is(T.None) && !type->Is(T.NaN)) {
+        TypeHandle range = T.Range(
+            isolate->factory()->NewNumber(type->Min()),
+            isolate->factory()->NewNumber(type->Max()));
+        CHECK(range->Is(type));
+      }
+    }
+    */
+
+    // 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) {
+        TypeHandle type1 = *it1;
+        TypeHandle type2 = *it2;
+        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) {
+      TypeHandle type = *it;
+      if (type->IsRange()) {
+        TypeHandle lub = Rep::BitsetType::New(
+            Rep::BitsetType::Lub(type), T.region());
+        CHECK(lub->Min() <= type->Min() && type->Max() <= lub->Max());
+      }
+    }
+  }
+
+  void Context() {
+    // Constructor
+    for (int i = 0; i < 20; ++i) {
+      TypeHandle type = T.Random();
+      TypeHandle context = T.Context(type);
+      CHECK(context->Iscontext());
+    }
+
+    // Attributes
+    for (int i = 0; i < 20; ++i) {
+      TypeHandle type = T.Random();
+      TypeHandle context = T.Context(type);
+      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) {
+        TypeHandle type1 = T.Random();
+        TypeHandle type2 = T.Random();
+        TypeHandle context1 = T.Context(type1);
+        TypeHandle context2 = T.Context(type2);
+        CHECK(Equal(context1, context2) == Equal(type1, type2));
+      }
+    }
+
+    // Subtyping: 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) {
+        TypeHandle outer1 = *it1;
+        TypeHandle outer2 = *it2;
+        TypeHandle type1 = T.Context(outer1);
+        TypeHandle type2 = T.Context(outer2);
+        CHECK(type1->Is(type2) == outer1->Equals(outer2));
+      }
+    }
   }
 
   void Array() {
     // Constructor
     for (int i = 0; i < 20; ++i) {
       TypeHandle type = T.Random();
       TypeHandle array = T.Array1(type);
       CHECK(array->IsArray());
     }
 
     // Attributes
     for (int i = 0; i < 20; ++i) {
       TypeHandle type = T.Random();
       TypeHandle array = T.Array1(type);
       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) {
         TypeHandle type1 = T.Random();
         TypeHandle type2 = T.Random();
         TypeHandle array1 = T.Array1(type1);
         TypeHandle array2 = T.Array1(type2);
         CHECK(Equal(array1, array2) == Equal(type1, type2));
       }
     }
+
+    // Subtyping: 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) {
+        TypeHandle element1 = *it1;
+        TypeHandle element2 = *it2;
+        TypeHandle type1 = T.Array1(element1);
+        TypeHandle type2 = T.Array1(element2);
+        CHECK(type1->Is(type2) == element1->Equals(element2));
+      }
+    }
   }
 
   void Function() {
     // Constructors
     for (int i = 0; i < 20; ++i) {
       for (int j = 0; j < 20; ++j) {
         for (int k = 0; k < 20; ++k) {
           TypeHandle type1 = T.Random();
           TypeHandle type2 = T.Random();
           TypeHandle type3 = T.Random();
@@ skipping 49 matching lines @@
           TypeHandle function22 = T.Function2(type1, type2, type3);
           TypeHandle function23 = T.Function2(type1, type3, type2);
           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));
         }
       }
     }
+
+    // Subtyping:
+    // 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) {
+        TypeHandle result1 = *i;
+        TypeHandle receiver1 = *j;
+        TypeHandle type1 = T.Function0(result1, receiver1);
+        TypeHandle result2 = T.Random();
+        TypeHandle receiver2 = T.Random();
+        TypeHandle type2 = T.Function0(result2, receiver2);
+        CHECK(type1->Is(type2) ==
+            (result1->Equals(result2) && receiver1->Equals(receiver2)));
+      }
+    }
   }
 
   void Of() {
     // Constant(V)->Is(Of(V))
     for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) {
       Handle<i::Object> value = *vt;
       TypeHandle const_type = T.Constant(value);
       TypeHandle of_type = T.Of(value);
       CHECK(const_type->Is(of_type));
     }
@@ skipping 190 matching lines @@
 
     // 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) {
         TypeHandle type1 = *it1;
         TypeHandle type2 = *it2;
         CHECK((type1->Is(type2) && type2->Is(type1)) == Equal(type1, type2));
       }
     }
 
-    // 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;
-        TypeHandle class_type1 = T.Class(map1);
-        TypeHandle class_type2 = T.Class(map2);
-        CHECK(class_type1->Is(class_type2) == (*map1 == *map2));
-      }
-    }
-
-    // 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;
-        TypeHandle const_type1 = T.Constant(value1);
-        TypeHandle const_type2 = T.Constant(value2);
-        CHECK(const_type1->Is(const_type2) == (*value1 == *value2));
-      }
-    }
-
-    // Range(min1, max1)->Is(Range(min2, max2)) iff
-    // min1 >= min2 /\ max1 <= max2
-    for (ValueIterator i1 = T.integers.begin();
-        i1 != T.integers.end(); ++i1) {
-      for (ValueIterator j1 = T.integers.begin();
-          j1 != T.integers.end(); ++j1) {
-        for (ValueIterator i2 = T.integers.begin();
-             i2 != T.integers.end(); ++i2) {
-          for (ValueIterator j2 = T.integers.begin();
-               j2 != T.integers.end(); ++j2) {
-            i::Handle<i::Object> min1 = *i1;
-            i::Handle<i::Object> max1 = *j1;
-            i::Handle<i::Object> min2 = *i2;
-            i::Handle<i::Object> max2 = *j2;
-            if (min1->Number() > max1->Number()) std::swap(min1, max1);
-            if (min2->Number() > max2->Number()) std::swap(min2, max2);
-            TypeHandle type1 = T.Range(min1, max1);
-            TypeHandle type2 = T.Range(min2, max2);
-            CHECK(type1->Is(type2) ==
-                (min2->Number() <= min1->Number() &&
-                 max1->Number() <= max2->Number()));
-          }
-        }
-      }
-    }
-
-    // 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) {
-        TypeHandle outer1 = *it1;
-        TypeHandle outer2 = *it2;
-        TypeHandle type1 = T.Context(outer1);
-        TypeHandle type2 = T.Context(outer2);
-        CHECK(type1->Is(type2) == outer1->Equals(outer2));
-      }
-    }
-
-    // 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) {
-        TypeHandle element1 = *it1;
-        TypeHandle element2 = *it2;
-        TypeHandle type1 = T.Array1(element1);
-        TypeHandle type2 = T.Array1(element2);
-        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) {
-        TypeHandle result1 = *i;
-        TypeHandle receiver1 = *j;
-        TypeHandle type1 = T.Function0(result1, receiver1);
-        TypeHandle result2 = T.Random();
-        TypeHandle receiver2 = T.Random();
-        TypeHandle type2 = T.Function0(result2, receiver2);
-        CHECK(type1->Is(type2) ==
-            (result1->Equals(result2) && receiver1->Equals(receiver2)));
-      }
-    }
-
     // (In-)Compatibilities.
     for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) {
       for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) {
         TypeHandle type1 = *i;
         TypeHandle type2 = *j;
         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()) ||
@@ skipping 416 matching lines @@
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
         TypeHandle type1 = *it1;
         TypeHandle type2 = *it2;
         TypeHandle union12 = T.Union(type1, type2);
         TypeHandle union21 = T.Union(type2, type1);
         CheckEqual(union12, union21);
       }
     }
 
     // Associativity: Union(T1, Union(T2, T3)) = Union(Union(T1, T2), T3)
-    // This does NOT hold!
+    // 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)
     /*
     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) {
           TypeHandle type1 = *it1;
           TypeHandle type2 = *it2;
           TypeHandle type3 = *it3;
           TypeHandle union12 = T.Union(type1, type2);
           TypeHandle union23 = T.Union(type2, type3);
           TypeHandle union1_23 = T.Union(type1, union23);
@@ skipping 19 matching lines @@
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
         TypeHandle type1 = *it1;
         TypeHandle type2 = *it2;
         TypeHandle union12 = T.Union(type1, type2);
         if (type1->Is(type2)) CheckEqual(union12, type2);
       }
     }
 
     // Monotonicity: T1->Is(T2) implies Union(T1, T3)->Is(Union(T2, T3))
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // Range(-5,-1) <= Signed32
+    // Range(-5,-1) \/ Range(1,5) = Range(-5,5) </= Signed32 \/ Range(1,5)
     /*
     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) {
           TypeHandle type1 = *it1;
           TypeHandle type2 = *it2;
           TypeHandle type3 = *it3;
           TypeHandle union13 = T.Union(type1, type3);
           TypeHandle union23 = T.Union(type2, type3);
           CHECK(!type1->Is(type2) || union13->Is(union23));
         }
       }
     }
     */
   }
 
   void Union2() {
     // Monotonicity: T1->Is(T3) and T2->Is(T3) implies Union(T1, T2)->Is(T3)
-    // This does NOT hold.  TODO(neis): Could fix this by splitting
-    // OtherNumber into a negative and a positive part.
+    // This does NOT hold.  For example:
+    // Range(-2^33, -2^33) <= OtherNumber
+    // Range(2^33, 2^33) <= OtherNumber
+    // Range(-2^33, 2^33) </= OtherNumber
     /*
     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) {
           TypeHandle type1 = *it1;
           TypeHandle type2 = *it2;
           TypeHandle type3 = *it3;
           TypeHandle union12 = T.Union(type1, type2);
           CHECK(!(type1->Is(type3) && type2->Is(type3)) || union12->Is(type3));
         }
@@ skipping 161 matching lines @@
         TypeHandle type1 = *it1;
         TypeHandle type2 = *it2;
         TypeHandle intersect12 = T.Intersect(type1, type2);
         TypeHandle intersect21 = T.Intersect(type2, type1);
         CheckEqual(intersect12, intersect21);
       }
     }
 
     // Associativity:
     // Intersect(T1, Intersect(T2, T3)) = Intersect(Intersect(T1, T2), T3)
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // (Class(..stringy1..) /\ Class(..stringy2..)) /\ Constant(..string..) =
+    // None
+    // Class(..stringy1..) /\ (Class(..stringy2..) /\ Constant(..string..)) =
+    // Constant(..string..)
     /*
     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) {
           TypeHandle type1 = *it1;
           TypeHandle type2 = *it2;
           TypeHandle type3 = *it3;
           TypeHandle intersect12 = T.Intersect(type1, type2);
           TypeHandle intersect23 = T.Intersect(type2, type3);
           TypeHandle intersect1_23 = T.Intersect(type1, intersect23);
           TypeHandle intersect12_3 = T.Intersect(intersect12, type3);
           CheckEqual(intersect1_23, intersect12_3);
         }
       }
     }
     */
 
     // Join: Intersect(T1, T2)->Is(T1) and Intersect(T1, T2)->Is(T2)
-    // This does NOT hold.  Not even the disjunction.
+    // 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(..)
     /*
     for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) {
       for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) {
         TypeHandle type1 = *it1;
         TypeHandle type2 = *it2;
         TypeHandle intersect12 = T.Intersect(type1, type2);
         CHECK(intersect12->Is(type1));
         CHECK(intersect12->Is(type2));
       }
     }
     */
 
     // 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) {
         TypeHandle type1 = *it1;
         TypeHandle type2 = *it2;
         TypeHandle intersect12 = T.Intersect(type1, type2);
         if (type1->Is(type2)) CheckEqual(intersect12, type1);
       }
     }
 
     // Monotonicity: T1->Is(T2) implies Intersect(T1, T3)->Is(Intersect(T2, T3))
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // Class(OtherObject/TaggedPtr) <= Any/TaggedPtr
+    // Class(OtherObject/TaggedPtr) /\ Any/UntaggedInt1 = Class(..)
+    // Any/TaggedPtr /\ Any/UntaggedInt1 = None
     /*
     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) {
           TypeHandle type1 = *it1;
           TypeHandle type2 = *it2;
           TypeHandle type3 = *it3;
           TypeHandle intersect13 = T.Intersect(type1, type3);
           TypeHandle intersect23 = T.Intersect(type2, type3);
           CHECK(!type1->Is(type2) || intersect13->Is(intersect23));
         }
       }
     }
     */
 
     // Monotonicity: T1->Is(T3) or T2->Is(T3) implies Intersect(T1, T2)->Is(T3)
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // Class(..stringy..) <= Class(..stringy..)
+    // Class(..stringy..) /\ Constant(..string..) = Constant(..string..)
+    // Constant(..string..) </= Class(..stringy..)
     /*
     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) {
           TypeHandle type1 = *it1;
           TypeHandle type2 = *it2;
           TypeHandle type3 = *it3;
           TypeHandle intersect12 = T.Intersect(type1, type2);
           CHECK(!(type1->Is(type3) || type2->Is(type3)) ||
                 intersect12->Is(type3));
         }
       }
     }
     */
 
     // Monotonicity: T1->Is(T2) and T1->Is(T3) implies T1->Is(Intersect(T2, T3))
-    // This does NOT hold.
-    /*
     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) {
           TypeHandle type1 = *it1;
           TypeHandle type2 = *it2;
           TypeHandle type3 = *it3;
           TypeHandle intersect23 = T.Intersect(type2, type3);
           CHECK(!(type1->Is(type2) && type1->Is(type3)) ||
                 type1->Is(intersect23));
         }
       }
     }
-    */

[neis1, 2014/09/24 12:01:01]

I'm not sure why I thought this wouldn't hold anymore.

 
     // Bitset-class
     CheckEqual(T.Intersect(T.ObjectClass, T.Object), T.ObjectClass);
     CheckEqual(T.Intersect(T.ObjectClass, T.Array), T.None);
     CheckEqual(T.Intersect(T.ObjectClass, T.Number), T.None);
 
     // Bitset-array
     CheckEqual(T.Intersect(T.NumberArray, T.Object), T.NumberArray);
     CheckEqual(T.Intersect(T.AnyArray, T.Function), T.None);
 
@@ skipping 83 matching lines @@
             T.Union(
                 T.ObjectConstant1,
                 T.Union(T.ArrayConstant, T.ObjectConstant2))),
         T.Union(
             T.ArrayConstant,
             T.Union(T.ObjectConstant2, T.ObjectConstant1)));  // !!!
   }
 
   void Distributivity() {
     // Union(T1, Intersect(T2, T3)) = Intersect(Union(T1, T2), Union(T1, T3))
-    // This does NOT hold.
+    // 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)
     /*
     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) {
           TypeHandle type1 = *it1;
           TypeHandle type2 = *it2;
           TypeHandle type3 = *it3;
           TypeHandle union12 = T.Union(type1, type2);
           TypeHandle union13 = T.Union(type1, type3);
           TypeHandle intersect23 = T.Intersect(type2, type3);
           TypeHandle union1_23 = T.Union(type1, intersect23);
           TypeHandle intersect12_13 = T.Intersect(union12, union13);
           CHECK(Equal(union1_23, intersect12_13));
         }
       }
     }
     */
 
     // Intersect(T1, Union(T2, T3)) = Union(Intersect(T1, T2), Intersect(T1,T3))
-    // This does NOT hold.
+    // This does NOT hold.  For example:
+    // Untagged /\ (Untagged \/ Class(../Tagged)) = Untagged
+    // (Untagged /\ Untagged) \/ (Untagged /\ Class(../Tagged)) =
+    // Untagged \/ Class(../Tagged)
     /*
     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) {
           TypeHandle type1 = *it1;
           TypeHandle type2 = *it2;
           TypeHandle type3 = *it3;
           TypeHandle intersect12 = T.Intersect(type1, type2);
           TypeHandle intersect13 = T.Intersect(type1, type3);
           TypeHandle union23 = T.Union(type2, type3);
@@ skipping 177 matching lines @@
 }
 
 
 TEST(Intersect) {
   CcTest::InitializeVM();
   ZoneTests().Intersect();
   HeapTests().Intersect();
 }
 
 
-/*
 TEST(Distributivity) {
   CcTest::InitializeVM();
   ZoneTests().Distributivity();
   HeapTests().Distributivity();
 }
-*/
 
 
 TEST(Convert) {
   CcTest::InitializeVM();
   ZoneTests().Convert<HeapType, Handle<HeapType>, Isolate, HeapRep>();
   HeapTests().Convert<Type, Type*, Zone, ZoneRep>();
 }
 
 
 TEST(HTypeFromType) {
   CcTest::InitializeVM();
   ZoneTests().HTypeFromType();
   HeapTests().HTypeFromType();
 }