Establish distributivity for type union & intersection

test/cctest/test-types.cc

Index: test/cctest/test-types.cc
diff --git a/test/cctest/test-types.cc b/test/cctest/test-types.cc
index 47868f6484b3e09fee9bf69d5fd9613296f74dff..d43aac3e3eb1acc8a8ac009017b9e2a0590e390a 100644
--- a/test/cctest/test-types.cc
+++ b/test/cctest/test-types.cc
@@ -77,18 +77,20 @@ struct HeapRep {
     return t->IsFixedArray() && Smi::cast(AsStruct(t)->get(0))->value() == tag;
   }
   static bool IsBitset(Handle<HeapType> t) { return t->IsSmi(); }
-  static bool IsClass(Handle<HeapType> t) { return t->IsMap(); }
-  static bool IsConstant(Handle<HeapType> t) { return t->IsBox(); }
+  static bool IsClass(Handle<HeapType> t) {
+    return t->IsMap() || IsStruct(t, 0);
+  }
+  static bool IsConstant(Handle<HeapType> t) { return IsStruct(t, 1); }
   static bool IsArray(Handle<HeapType> t) { return IsStruct(t, 2); }
   static bool IsFunction(Handle<HeapType> t) { return IsStruct(t, 3); }
   static bool IsUnion(Handle<HeapType> t) { return IsStruct(t, 4); }
 
   static Struct* AsStruct(Handle<HeapType> t) { return FixedArray::cast(*t); }
   static int AsBitset(Handle<HeapType> t) { return Smi::cast(*t)->value(); }
-  static Map* AsClass(Handle<HeapType> t) { return Map::cast(*t); }
-  static Object* AsConstant(Handle<HeapType> t) {
-    return Box::cast(*t)->value();
+  static Map* AsClass(Handle<HeapType> t) {
+    return t->IsMap() ? Map::cast(*t) : Map::cast(AsStruct(t)->get(2));
   }
+  static Object* AsConstant(Handle<HeapType> t) { return AsStruct(t)->get(2); }
   static Struct* AsUnion(Handle<HeapType> t) { return AsStruct(t); }
   static int Length(Struct* structured) { return structured->length() - 1; }
 
@@ -152,7 +154,7 @@ class Types {
     NumberFunction2 = Type::Function(Number, Number, Number, region);
     MethodFunction = Type::Function(String, Object, 0, region);
 
-    for (int i = 0; i < 50; ++i) {
+    for (int i = 0; i < 500; ++i) {
       types.push_back(Fuzz());
     }
   }
@@ -332,6 +334,8 @@ struct Tests : Rep {
         Rep::IsBitset(type1) == Rep::IsBitset(type2) &&
         Rep::IsClass(type1) == Rep::IsClass(type2) &&
         Rep::IsConstant(type1) == Rep::IsConstant(type2) &&
+        Rep::IsArray(type1) == Rep::IsArray(type2) &&
+        Rep::IsFunction(type1) == Rep::IsFunction(type2) &&
         Rep::IsUnion(type1) == Rep::IsUnion(type2) &&
         type1->NumClasses() == type2->NumClasses() &&
         type1->NumConstants() == type2->NumConstants() &&
@@ -341,7 +345,8 @@ struct Tests : Rep {
           Rep::AsClass(type1) == Rep::AsClass(type2)) &&
         (!Rep::IsConstant(type1) ||
           Rep::AsConstant(type1) == Rep::AsConstant(type2)) &&
-        (!Rep::IsUnion(type1) ||
+// TODO(rossberg): Check details of arrays, functions, bounds.
+          (!Rep::IsUnion(type1) ||
           Rep::Length(Rep::AsUnion(type1)) == Rep::Length(Rep::AsUnion(type2)));
   }
 
@@ -1535,9 +1540,9 @@ struct Tests : Rep {
     CheckEqual(
         T.Intersect(T.Object, T.Union(T.ObjectConstant1, T.ObjectClass)),
         T.Union(T.ObjectConstant1, T.ObjectClass));
-    CheckEqual(
-        T.Intersect(T.Union(T.ArrayClass, T.ObjectConstant1), T.Number),
-        T.None);
+    CHECK(
+        !T.Intersect(T.Union(T.ArrayClass, T.ObjectConstant1), T.Number)
+            ->IsInhabited());
 
     // Class-constant
     CheckEqual(T.Intersect(T.ObjectConstant1, T.ObjectClass), T.None);
@@ -1550,9 +1555,9 @@ struct Tests : Rep {
     CheckEqual(
         T.Intersect(T.AnyArray, T.Union(T.Object, T.SmiConstant)),
         T.AnyArray);
-    CheckEqual(
-        T.Intersect(T.Union(T.AnyArray, T.ArrayConstant), T.FloatArray),
-        T.None);
+    CHECK(
+        !T.Intersect(T.Union(T.AnyArray, T.ArrayConstant), T.FloatArray)
+            ->IsInhabited());
 
     // Function-union
     CheckEqual(
@@ -1561,9 +1566,9 @@ struct Tests : Rep {
     CheckEqual(
         T.Intersect(T.NumberFunction1, T.Union(T.Object, T.SmiConstant)),
         T.NumberFunction1);
-    CheckEqual(
-        T.Intersect(T.Union(T.MethodFunction, T.Name), T.NumberFunction2),
-        T.None);
+    CHECK(
+        !T.Intersect(T.Union(T.MethodFunction, T.Name), T.NumberFunction2)
+            ->IsInhabited());
 
     // Class-union
     CheckEqual(
@@ -1572,9 +1577,9 @@ struct Tests : Rep {
     CheckEqual(
         T.Intersect(T.ArrayClass, T.Union(T.Object, T.SmiConstant)),
         T.ArrayClass);
-    CheckEqual(
-        T.Intersect(T.Union(T.ObjectClass, T.ArrayConstant), T.ArrayClass),
-        T.None);
+    CHECK(
+        !T.Intersect(T.Union(T.ObjectClass, T.ArrayConstant), T.ArrayClass)
+            ->IsInhabited());
 
     // Constant-union
     CheckEqual(
@@ -1584,10 +1589,10 @@ struct Tests : Rep {
     CheckEqual(
         T.Intersect(T.SmiConstant, T.Union(T.Number, T.ObjectConstant2)),
         T.SmiConstant);
-    CheckEqual(
-        T.Intersect(
-            T.Union(T.ArrayConstant, T.ObjectClass), T.ObjectConstant1),
-        T.None);
+    CHECK(
+        !T.Intersect(
+            T.Union(T.ArrayConstant, T.ObjectClass), T.ObjectConstant1)
+                ->IsInhabited());
 
     // Union-union
     CheckEqual(
@@ -1615,6 +1620,44 @@ struct Tests : Rep {
         T.Union(T.ObjectConstant2, T.ObjectConstant1));
   }
 
+  void Distributivity() {
+    // Distributivity:
+    // Union(T1, Intersect(T2, T3)) = Intersect(Union(T1, T2), Union(T1, T3))
+    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));
+        }
+      }
+    }
+
+    // Distributivity:
+    // Intersect(T1, Union(T2, T3)) = Union(Intersect(T1, T2), Intersect(T1,T3))
+    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);
+          TypeHandle intersect1_23 = T.Intersect(type1, union23);
+          TypeHandle union12_13 = T.Union(intersect12, intersect13);
+          CHECK(Equal(intersect1_23, union12_13));
+        }
+      }
+    }
+  }
+
   template<class Type2, class TypeHandle2, class Region2, class Rep2>
   void Convert() {
     Types<Type2, TypeHandle2, Region2> T2(
@@ -1744,6 +1787,13 @@ TEST(Intersect2) {
 }
 
 
+TEST(Distributivity) {
+  CcTest::InitializeVM();
+  ZoneTests().Distributivity();
+  HeapTests().Distributivity();
+}
+
+
 TEST(Convert) {
   CcTest::InitializeVM();
   ZoneTests().Convert<HeapType, Handle<HeapType>, Isolate, HeapRep>();