Establish distributivity for type union & intersection

test/cctest/test-types.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 59 matching lines @@
 };
 
 
 struct HeapRep {
   typedef FixedArray Struct;
 
   static bool IsStruct(Handle<HeapType> t, int tag) {
     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; }
 
   static Isolate* ToRegion(Zone* zone, Isolate* isolate) { return isolate; }
 };
 
 
 template<class Type, class TypeHandle, class Region>
 class Types {
  public:
@@ skipping 43 matching lines @@
 
     FloatArray = Type::Array(Float, region);
     StringArray = Type::Array(String, region);
     AnyArray = Type::Array(Any, region);
 
     SignedFunction1 = Type::Function(SignedSmall, SignedSmall, region);
     NumberFunction1 = Type::Function(Number, Number, region);
     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());
     }
   }
 
   Handle<i::Map> object_map;
   Handle<i::Map> array_map;
   Handle<i::Map> uninitialized_map;
 
   Handle<i::Smi> smi;
   Handle<i::HeapNumber> signed32;
@@ skipping 159 matching lines @@
       zone(isolate),
       T(Rep::ToRegion(&zone, isolate), isolate) {
   }
 
   bool Equal(TypeHandle type1, TypeHandle type2) {
     return
         type1->Is(type2) && type2->Is(type1) &&
         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() &&
         (!Rep::IsBitset(type1) ||
           Rep::AsBitset(type1) == Rep::AsBitset(type2)) &&
         (!Rep::IsClass(type1) ||
           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)));
   }
 
   void CheckEqual(TypeHandle type1, TypeHandle type2) {
     CHECK(Equal(type1, type2));
   }
 
   void CheckSub(TypeHandle type1, TypeHandle type2) {
     CHECK(type1->Is(type2));
     CHECK(!type2->Is(type1));
@@ skipping 1173 matching lines @@
     CheckSub(T.Intersect(T.AnyArray, T.Function), T.Representation);
 
     // Bitset-function
     CheckEqual(T.Intersect(T.MethodFunction, T.Object), T.MethodFunction);
     CheckSub(T.Intersect(T.NumberFunction1, T.Array), T.Representation);
 
     // Bitset-union
     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);
     CheckEqual(T.Intersect(T.ArrayClass, T.ObjectConstant2), T.None);
 
     // Array-union
     CheckEqual(
         T.Intersect(T.FloatArray, T.Union(T.FloatArray, T.ArrayClass)),
         T.FloatArray);
     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(
         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);
-    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(
         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);
-    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(
         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);
-    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(
         T.Intersect(
             T.Union(T.Number, T.ArrayClass),
             T.Union(T.SignedSmall, T.Array)),
         T.Union(T.SignedSmall, T.ArrayClass));
     CheckEqual(
         T.Intersect(
             T.Union(T.Number, T.ObjectClass),
             T.Union(T.Signed32, T.Array)),
         T.Signed32);
     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(
                 T.Union(T.ObjectConstant2, T.ObjectConstant1), T.ArrayClass),
             T.Union(
                 T.ObjectConstant1,
                 T.Union(T.ArrayConstant, T.ObjectConstant2))),
         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(
         Rep2::ToRegion(&zone, isolate), isolate);
     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
       TypeHandle type1 = *it;
       TypeHandle2 type2 = T2.template Convert<Type>(type1);
       TypeHandle type3 = T.template Convert<Type2>(type2);
       CheckEqual(type1, type3);
     }
@@ skipping 109 matching lines @@
 }
 
 
 TEST(Intersect2) {
   CcTest::InitializeVM();
   ZoneTests().Intersect2();
   HeapTests().Intersect2();
 }
 
 
+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>();
 }