Fix various bugs in the type systems, and improve test coverage.

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 <list>
+
 #include "cctest.h"
 #include "types.h"
 
 using namespace v8::internal;
 
 template<class Type, class TypeHandle, class Region>
 class Types {
  public:
   Types(Region* region, Isolate* isolate) :
       Representation(Type::Representation(region)),
@@ skipping 26 matching lines @@
     object2 = isolate->factory()->NewJSObjectFromMap(object_map);
     array = isolate->factory()->NewJSArray(20);
     ObjectClass = Type::Class(object_map, region);
     ArrayClass = Type::Class(array_map, region);
     SmiConstant = Type::Constant(smi, region);
     Signed32Constant = Type::Constant(signed32, region);
     ObjectConstant1 = Type::Constant(object1, region);
     ObjectConstant2 = Type::Constant(object2, region);
     ArrayConstant1 = Type::Constant(array, region);
     ArrayConstant2 = Type::Constant(array, region);
+
+    types.push_back(None);
+    types.push_back(Any);
+    types.push_back(Boolean);
+    types.push_back(Null);
+    types.push_back(Undefined);
+    types.push_back(Number);
+    types.push_back(SignedSmall);
+    types.push_back(Signed32);
+    types.push_back(Float);
+    types.push_back(Name);
+    types.push_back(UniqueName);
+    types.push_back(String);
+    types.push_back(InternalizedString);
+    types.push_back(Symbol);
+    types.push_back(Receiver);
+    types.push_back(Object);
+    types.push_back(Array);
+    types.push_back(Function);
+    types.push_back(Proxy);
+    types.push_back(ObjectClass);
+    types.push_back(ArrayClass);
+    types.push_back(SmiConstant);
+    types.push_back(Signed32Constant);
+    types.push_back(ObjectConstant1);
+    types.push_back(ObjectConstant2);
+    types.push_back(ArrayConstant1);
+    types.push_back(ArrayConstant2);
+    for (int i = 0; i < 1000; ++i) {

[rossberg, 2014/04/09 10:56:56]

We probably need to lower this somewhat. 500? 300?

[Benedikt Meurer, 2014/04/09 11:12:26]

300

+      types.push_back(Fuzz());
+    }
+
+    objects.push_back(smi);
+    objects.push_back(signed32);
+    objects.push_back(object1);
+    objects.push_back(object2);
+    objects.push_back(array);
   }
 
   TypeHandle Representation;
   TypeHandle Semantic;
   TypeHandle None;
   TypeHandle Any;
   TypeHandle Boolean;
   TypeHandle Null;
   TypeHandle Undefined;
   TypeHandle Number;
@@ skipping 23 matching lines @@
 
   Handle<i::Map> object_map;
   Handle<i::Map> array_map;
 
   Handle<i::Smi> smi;
   Handle<i::HeapNumber> signed32;
   Handle<i::JSObject> object1;
   Handle<i::JSObject> object2;
   Handle<i::JSArray> array;
 
+  typedef std::list<TypeHandle> TypeList;
+  TypeList types;
+
+  typedef std::list<Handle<i::Object> > ObjectList;
+  ObjectList objects;
+
+  TypeHandle Of(Handle<i::Object> obj) {
+    return Type::Of(obj, region_);
+  }
+
+  TypeHandle Constant(Handle<i::Object> obj) {
+    return Type::Constant(obj, region_);
+  }
+
   TypeHandle Union(TypeHandle t1, TypeHandle t2) {
     return Type::Union(t1, t2, region_);
   }
   TypeHandle Intersect(TypeHandle t1, TypeHandle t2) {
     return Type::Intersect(t1, t2, region_);
   }
 
   template<class Type2, class TypeHandle2>
   TypeHandle Convert(TypeHandle2 t) {
     return Type::template Convert<Type2>(t, region_);
@@ skipping 105 matching lines @@
   static Isolate* ToRegion(Zone* zone, Isolate* isolate) { return isolate; }
 };
 
 
 template<class Type, class TypeHandle, class Region, class Rep>
 struct Tests : Rep {
   Isolate* isolate;
   HandleScope scope;
   Zone zone;
   Types<Type, TypeHandle, Region> T;
+  typedef typename Types<Type, TypeHandle, Region>::TypeList::iterator

[rossberg, 2014/04/09 10:56:56]

You should be able to say T::TypeList::iterator here; similarly below.

[Benedikt Meurer, 2014/04/09 11:12:26]

T does not name a type.

+      TypeIterator;
+  typedef typename Types<Type, TypeHandle, Region>::ObjectList::iterator
+      ObjectIterator;
 
   Tests() :
       isolate(CcTest::i_isolate()),
       scope(isolate),
       zone(isolate),
       T(Rep::ToRegion(&zone, isolate), isolate) {
   }
 
   void CheckEqual(TypeHandle type1, TypeHandle type2) {
     CHECK_EQ(Rep::IsBitset(type1), Rep::IsBitset(type2));
@@ skipping 87 matching lines @@
 
     CHECK(*T.smi == this->AsConstant(T.SmiConstant));
     CHECK(*T.object1 == this->AsConstant(T.ObjectConstant1));
     CHECK(*T.object2 == this->AsConstant(T.ObjectConstant2));
     CHECK(*T.object1 != this->AsConstant(T.ObjectConstant2));
     CHECK(*T.array == this->AsConstant(T.ArrayConstant1));
     CHECK(*T.array == this->AsConstant(T.ArrayConstant2));
   }
 
   void Is() {
+    // T->Is(None) implies T = None for all T
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (type->Is(T.None)) CheckEqual(type, T.None);
+    }
+
+    // None->Is(T) for all T
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      CHECK(T.None->Is(type));
+    }
+
+    // Any->Is(T) implies T = Any for all T
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (T.Any->Is(type)) CheckEqual(type, T.Any);
+    }
+
+    // T->Is(Any) for all T
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      CHECK(type->Is(T.Any));
+    }
+
     // Reflexivity
-    CHECK(T.None->Is(T.None));
-    CHECK(T.Any->Is(T.Any));
-    CHECK(T.Object->Is(T.Object));
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      CHECK(type->Is(type));
+    }
 
-    CHECK(T.ObjectClass->Is(T.ObjectClass));
-    CHECK(T.ObjectConstant1->Is(T.ObjectConstant1));
-    CHECK(T.ArrayConstant1->Is(T.ArrayConstant2));
+    // Transitivity
+    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;
+          CHECK(!type1->Is(type2) ||
+                !type2->Is(type3) ||
+                type1->Is(type3));
+        }
+      }
+    }
 
     // Symmetry and Transitivity
     CheckSub(T.None, T.Number);
     CheckSub(T.None, T.Any);
 
     CheckUnordered(T.Boolean, T.Null);
     CheckUnordered(T.Undefined, T.Null);
     CheckUnordered(T.Boolean, T.Undefined);
 
     CheckSub(T.Number, T.Any);
@@ skipping 46 matching lines @@
     CheckUnordered(T.ObjectConstant1, T.ObjectConstant2);
     CheckUnordered(T.ObjectConstant1, T.ArrayConstant1);
 
     CheckUnordered(T.ObjectConstant1, T.ObjectClass);
     CheckUnordered(T.ObjectConstant2, T.ObjectClass);
     CheckUnordered(T.ObjectConstant1, T.ArrayClass);
     CheckUnordered(T.ObjectConstant2, T.ArrayClass);
     CheckUnordered(T.ArrayConstant1, T.ObjectClass);
   }
 
+  void NowIs() {
+    // T->NowIs(None) implies T = None for all T
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (type->NowIs(T.None)) CheckEqual(type, T.None);
+    }
+
+    // None->NowIs(T) for all T
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      CHECK(T.None->NowIs(type));
+    }
+
+    // Any->NowIs(T) implies T = Any for all T
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      if (T.Any->NowIs(type)) CheckEqual(type, T.Any);
+    }
+
+    // T->NowIs(Any) for all T
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      CHECK(type->NowIs(T.Any));
+    }
+
+    // Reflexivity
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      CHECK(type->NowIs(type));
+    }
+
+    // Transitivity
+    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;
+          CHECK(!type1->NowIs(type2) ||
+                !type2->NowIs(type3) ||
+                type1->NowIs(type3));
+        }
+      }
+    }
+
+    // T1->Is(T2) implies T1->NowIs(T2) for all 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) || type1->NowIs(type2));
+      }
+    }
+
+    CHECK(T.ObjectConstant1->NowIs(T.ObjectClass));
+    CHECK(T.ObjectConstant2->NowIs(T.ObjectClass));
+  }
+
+  void Contains() {
+    // T->Contains(O) iff Constant(O)->Is(T) for all T,O
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      for (ObjectIterator ot = T.objects.begin(); ot != T.objects.end(); ++ot) {
+        TypeHandle type = *it;
+        Handle<i::Object> obj = *ot;
+        CHECK(type->Contains(obj) == T.Constant(obj)->Is(type));
+      }
+    }
+
+    // Of(O)->Is(T) implies T->Contains(O) for all T,O
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      for (ObjectIterator ot = T.objects.begin(); ot != T.objects.end(); ++ot) {
+        TypeHandle type = *it;
+        Handle<i::Object> obj = *ot;
+        CHECK(!T.Of(obj)->Is(type) || type->Contains(obj));
+      }
+    }
+  }
+
   void Maybe() {
+    // T->Maybe(T) for all inhabited T
+    for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+      TypeHandle type = *it;
+      CHECK(type->Maybe(type) || !type->IsInhabited());
+    }
+
+    // Commutativity
+    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->Maybe(type2) == type2->Maybe(type1));
+      }
+    }
+
+    // T1->Is(T2) implies T1->Maybe(T2) or T1 is uninhabited for all 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) ||
+              type1->Maybe(type2) ||
+              !type1->IsInhabited());
+      }
+    }
+
     CheckOverlap(T.Any, T.Any, T.Semantic);
     CheckOverlap(T.Object, T.Object, T.Semantic);
 
     CheckDisjoint(T.Boolean, T.Null, T.Semantic);
     CheckDisjoint(T.Undefined, T.Null, T.Semantic);
     CheckDisjoint(T.Boolean, T.Undefined, T.Semantic);
 
     CheckOverlap(T.Number, T.Any, T.Semantic);
     CheckOverlap(T.SignedSmall, T.Number, T.Semantic);
     CheckOverlap(T.Float, T.Number, T.Semantic);
@@ skipping 427 matching lines @@
 }
 
 
 TEST(Is) {
   CcTest::InitializeVM();
   ZoneTests().Is();
   HeapTests().Is();
 }
 
 
+TEST(NowIs) {
+  CcTest::InitializeVM();
+  ZoneTests().NowIs();
+  HeapTests().NowIs();
+}
+
+
+TEST(Contains) {
+  CcTest::InitializeVM();
+  ZoneTests().Contains();
+  HeapTests().Contains();
+}
+
+
 TEST(Maybe) {
   CcTest::InitializeVM();
   ZoneTests().Maybe();
   HeapTests().Maybe();
 }
 
 
 TEST(Union) {
   CcTest::InitializeVM();
   ZoneTests().Union();
   HeapTests().Union();
 }
 
 
 TEST(Intersect) {
   CcTest::InitializeVM();
   ZoneTests().Intersect();
   HeapTests().Intersect();
 }
 
 
 TEST(Convert) {
   CcTest::InitializeVM();
   ZoneTests().Convert<HeapType, Handle<HeapType>, Isolate, HeapRep>();
   HeapTests().Convert<Type, Type*, Zone, ZoneRep>();
 }