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
 //       with the distribution.
 //     * Neither the name of Google Inc. nor the names of its
 //       contributors may be used to endorse or promote products derived
 //       from this software without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #include <vector>
 
+#define private public  /* To test private methods :) */

[Benedikt Meurer, 2014/05/27 09:29:47]

Urghs... how about friends?

[rossberg1, 2014/05/27 09:42:58]

Because I don't want to pollute the code proper with friend declarations for
tests (which I would need to repeat in several classes).

+#define protected public
+#include "types.h"
+#undef private
+#undef protected
+
 #include "cctest.h"
-#include "types.h"
 #include "utils/random-number-generator.h"
 
 using namespace v8::internal;
 
 // Testing auxiliaries (breaking the Type abstraction).
 struct ZoneRep {
   typedef void* Struct;
 
   static bool IsStruct(Type* t, int tag) {
     return !IsBitset(t) && reinterpret_cast<intptr_t>(AsStruct(t)[0]) == tag;
@@ skipping 28 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 128 matching lines @@
         for (int i = 0; i < n; ++i) {
           TypeHandle operand = Fuzz(depth - 1);
           type = Type::Union(type, operand, region_);
         }
         return type;
       }
     }
     UNREACHABLE();
   }
 
+  Region* region() { return region_; }
+
  private:
   Region* region_;
   RandomNumberGenerator rng_;
 };
 
 
 template<class Type, class TypeHandle, class Region, class Rep>
 struct Tests : Rep {
   typedef Types<Type, TypeHandle, Region> TypesInstance;
   typedef typename TypesInstance::TypeVector::iterator TypeIterator;
@@ skipping 11 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 307 matching lines @@
         Handle<i::Object> value = *vt;
         TypeHandle type = *it;
         TypeHandle const_type = T.Constant(value);
         TypeHandle nowof_type = T.NowOf(value);
         CHECK(!const_type->Is(type) ||
               (nowof_type->Is(type) || type->Maybe(const_type)));
       }
     }
   }
 
+  void Bounds() {
+    // Ordering: (T->BitsetGlb())->Is(T->BitsetLub())
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      TypeHandle glb = Type::BitsetType::New(type->BitsetGlb(), T.region());
+      TypeHandle lub = Type::BitsetType::New(type->BitsetLub(), T.region());
+      CHECK(glb->Is(lub));
+    }
+
+    // Lower bound: (T->BitsetGlb())->Is(T)
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      TypeHandle glb = Type::BitsetType::New(type->BitsetGlb(), T.region());
+      CHECK(glb->Is(type));
+    }
+
+    // Upper bound: T->Is(T->BitsetLub())
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      TypeHandle lub = Type::BitsetType::New(type->BitsetLub(), T.region());
+      CHECK(type->Is(lub));
+    }
+
+    // Inherent bound: (T->BitsetLub())->Is(T->InherentBitsetLub())
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      TypeHandle lub = Type::BitsetType::New(type->BitsetLub(), T.region());
+      TypeHandle inherent =
+          Type::BitsetType::New(type->InherentBitsetLub(), T.region());
+      CHECK(lub->Is(inherent));
+    }
+  }
+
   void Is() {
     // Least Element (Bottom): None->Is(T)
     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
       TypeHandle type = *it;
       CHECK(T.None->Is(type));
     }
 
     // Greatest Element (Top): T->Is(Any)
     for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
       TypeHandle type = *it;
@@ skipping 846 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);
+    TypeHandle NoneTaggedPtr = T.Intersect(T.TaggedPtr, T.Representation);
+    CheckEqual(T.Intersect(T.ObjectConstant1, T.ObjectClass), NoneTaggedPtr);
+    CheckEqual(T.Intersect(T.ArrayClass, T.ObjectConstant2), NoneTaggedPtr);
 
     // 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 46 matching lines @@
 }
 
 
 TEST(NowOf) {
   CcTest::InitializeVM();
   ZoneTests().NowOf();
   HeapTests().NowOf();
 }
 
 
+TEST(Bounds) {
+  CcTest::InitializeVM();
+  ZoneTests().Bounds();
+  HeapTests().Bounds();
+}
+
+
 TEST(Is) {
   CcTest::InitializeVM();
   ZoneTests().Is();
   HeapTests().Is();
 }
 
 
 TEST(NowIs) {
   CcTest::InitializeVM();
   ZoneTests().NowIs();
@@ skipping 43 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>();
 }