Add constructor for 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).
 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<intptr_t>(t) & 1; }
   static bool IsClass(Type* t) { return IsStruct(t, 0); }
   static bool IsConstant(Type* t) { return IsStruct(t, 1); }
-  static bool IsContext(Type* t) { return IsStruct(t, 2); }
-  static bool IsArray(Type* t) { return IsStruct(t, 3); }
-  static bool IsFunction(Type* t) { return IsStruct(t, 4); }
-  static bool IsUnion(Type* t) { return IsStruct(t, 5); }
+  static bool IsRange(Type* t) { return IsStruct(t, 2); }
+  static bool IsContext(Type* t) { return IsStruct(t, 3); }
+  static bool IsArray(Type* t) { return IsStruct(t, 4); }
+  static bool IsFunction(Type* t) { return IsStruct(t, 5); }
+  static bool IsUnion(Type* t) { return IsStruct(t, 6); }
 
   static Struct* AsStruct(Type* t) {
     return reinterpret_cast<Struct*>(t);
   }
   static int AsBitset(Type* t) {
     return static_cast<int>(reinterpret_cast<intptr_t>(t) >> 1);
   }
   static Map* AsClass(Type* t) {
     return *static_cast<Map**>(AsStruct(t)[3]);
   }
   static Object* AsConstant(Type* t) {
     return *static_cast<Object**>(AsStruct(t)[3]);
   }
+  static Type* AsRange(Type* t) {
+    return *static_cast<Type**>(AsStruct(t)[2]);
+  }

[neis, 2014/07/21 17:47:15]

This was bogus and I got rid of it.

   static Type* AsContext(Type* t) {
     return *static_cast<Type**>(AsStruct(t)[2]);
   }
   static Struct* AsUnion(Type* t) {
     return AsStruct(t);
   }
   static int Length(Struct* structured) {
     return static_cast<int>(reinterpret_cast<intptr_t>(structured[1]));
   }
 
@@ skipping 12 matching lines @@
   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() || IsStruct(t, 0);
   }
   static bool IsConstant(Handle<HeapType> t) { return IsStruct(t, 1); }
-  static bool IsContext(Handle<HeapType> t) { return IsStruct(t, 2); }
-  static bool IsArray(Handle<HeapType> t) { return IsStruct(t, 3); }
-  static bool IsFunction(Handle<HeapType> t) { return IsStruct(t, 4); }
-  static bool IsUnion(Handle<HeapType> t) { return IsStruct(t, 5); }
+  static bool IsRange(Handle<HeapType> t) { return IsStruct(t, 2); }
+  static bool IsContext(Handle<HeapType> t) { return IsStruct(t, 3); }
+  static bool IsArray(Handle<HeapType> t) { return IsStruct(t, 4); }
+  static bool IsFunction(Handle<HeapType> t) { return IsStruct(t, 5); }
+  static bool IsUnion(Handle<HeapType> t) { return IsStruct(t, 6); }
 
   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 t->IsMap() ? Map::cast(*t) : Map::cast(AsStruct(t)->get(2));
   }
   static Object* AsConstant(Handle<HeapType> t) { return AsStruct(t)->get(2); }
+  static HeapType* AsRange(Handle<HeapType> t) {
+    return HeapType::cast(AsStruct(t)->get(1));
+  }
   static HeapType* AsContext(Handle<HeapType> t) {
     return HeapType::cast(AsStruct(t)->get(1));
   }
   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; }
 
   struct BitsetType : HeapType::BitsetType {
     using HeapType::BitsetType::New;
@@ skipping 48 matching lines @@
     values.push_back(smi);
     values.push_back(signed32);
     values.push_back(object1);
     values.push_back(object2);
     values.push_back(array);
     values.push_back(uninitialized);
     for (ValueVector::iterator it = values.begin(); it != values.end(); ++it) {
       types.push_back(Type::Constant(*it, region));
     }
 
+    doubles.push_back(-0.0);
+    doubles.push_back(+0.0);
+    doubles.push_back(-std::numeric_limits<double>::infinity());
+    doubles.push_back(+std::numeric_limits<double>::infinity());
+    for (int i = 0; i < 40; ++i) {

[rossberg, 2014/07/21 15:58:32]

I suppose 10 to 20 is enough here, esp given that the test is O(N^4) below.
Also, maybe make half the random numbers proper integers, since that will likely
be the common case in practice.

[neis, 2014/07/21 17:47:15]

Done.

+      doubles.push_back(rng_->NextDouble() * rng_->NextInt());
+    }
+
     NumberArray = Type::Array(Number, 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 < 40; ++i) {
@@ skipping 32 matching lines @@
   TypeHandle AnyArray;
 
   TypeHandle SignedFunction1;
   TypeHandle NumberFunction1;
   TypeHandle NumberFunction2;
   TypeHandle MethodFunction;
 
   typedef std::vector<TypeHandle> TypeVector;
   typedef std::vector<Handle<i::Map> > MapVector;
   typedef std::vector<Handle<i::Object> > ValueVector;
+  typedef std::vector<double> DoubleVector;
+
   TypeVector types;
   MapVector maps;
   ValueVector values;
+  DoubleVector doubles;
 
   TypeHandle Of(Handle<i::Object> value) {
     return Type::Of(value, region_);
   }
 
   TypeHandle NowOf(Handle<i::Object> value) {
     return Type::NowOf(value, region_);
   }
 
   TypeHandle Constant(Handle<i::Object> value) {
     return Type::Constant(value, region_);
   }
 
+  TypeHandle Range(double min, double max) {
+    return Type::Range(min, max, region_);
+  }
+
   TypeHandle Class(Handle<i::Map> map) {
     return Type::Class(map, region_);
   }
 
   TypeHandle Array1(TypeHandle element) {
     return Type::Array(element, region_);
   }
 
   TypeHandle Function0(TypeHandle result, TypeHandle receiver) {
     return Type::Function(result, receiver, 0, region_);
@@ skipping 90 matching lines @@
   v8::base::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;
   typedef typename TypesInstance::MapVector::iterator MapIterator;
   typedef typename TypesInstance::ValueVector::iterator ValueIterator;
+  typedef typename TypesInstance::DoubleVector::iterator DoubleIterator;
 
   Isolate* isolate;
   HandleScope scope;
   Zone zone;
   TypesInstance T;
 
   Tests() :
       isolate(CcTest::i_isolate()),
       scope(isolate),
       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::IsRange(type1) == Rep::IsRange(type2) &&
         Rep::IsContext(type1) == Rep::IsContext(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)) &&
           // TODO(rossberg): Check details of arrays, functions, bounds.
-          (!Rep::IsUnion(type1) ||
+        (!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 186 matching lines @@
     CHECK(T.Constant(fac->NewNumber(-0x7fffffff-2.0))->Is(T.OtherNumber));
     CHECK(T.Constant(fac->NewNumber(0.1))->Is(T.OtherNumber));
     CHECK(T.Constant(fac->NewNumber(-10.1))->Is(T.OtherNumber));
     CHECK(T.Constant(fac->NewNumber(10e60))->Is(T.OtherNumber));
     CHECK(T.Constant(fac->NewNumber(-1.0*0.0))->Is(T.MinusZero));
     CHECK(T.Constant(fac->NewNumber(v8::base::OS::nan_value()))->Is(T.NaN));
     CHECK(T.Constant(fac->NewNumber(V8_INFINITY))->Is(T.OtherNumber));
     CHECK(T.Constant(fac->NewNumber(-V8_INFINITY))->Is(T.OtherNumber));
   }
 
+  void Range() {
+    // Constructor
+    for (DoubleIterator i = T.doubles.begin(); i != T.doubles.end(); ++i) {
+      for (DoubleIterator j = T.doubles.begin(); j != T.doubles.end(); ++j) {
+        double min = *i <= *j ? *i : *j;

[rossberg, 2014/07/21 15:58:32]

You can use the C++ min & max functions for these.

[neis, 2014/07/21 17:47:15]

Done.

+        double max = *i <= *j ? *j : *i;
+        TypeHandle type = T.Range(min, max);
+        CHECK(this->IsRange(type));
+      }
+    }
+
+    // Range attributes
+    for (DoubleIterator i = T.doubles.begin(); i != T.doubles.end(); ++i) {
+      for (DoubleIterator j = T.doubles.begin(); j != T.doubles.end(); ++j) {
+        double min = *i <= *j ? *i : *j;
+        double max = *i <= *j ? *j : *i;
+        TypeHandle type = T.Range(min, max);
+        CHECK(min == type->AsRange()->Min());
+        CHECK(max == type->AsRange()->Max());
+      }
+    }
+
+    // Injectivity: Range(min1, max1) = Range(min2, max2) =>

[rossberg, 2014/07/21 15:58:32]

I think that Functionality should hold as well.

[neis, 2014/07/21 17:47:15]

Right.  Actually, the changes to Equal were incomplete.  I fixed that but I had
to disable the test for now because it fails as long as subtyping is not yet
defined for range types.

[rossberg, 2014/07/22 07:58:35]

Might be worth including the test anyway for clarity, but commented out and with
a TODO.

[neis, 2014/07/22 08:34:46]

Done.

+    //              min1 = min2 /\ max1 = max2
+    typedef DoubleIterator DI;
+    for (DI i1 = T.doubles.begin(); i1 != T.doubles.end(); ++i1) {
+      for (DI j1 = T.doubles.begin(); j1 != T.doubles.end(); ++j1) {
+        for (DI i2 = T.doubles.begin(); i2 != T.doubles.end(); ++i2) {
+          for (DI j2 = T.doubles.begin(); j2 != T.doubles.end(); ++j2) {
+            double min1 = *i1 <= *j1 ? *i1 : *j1;
+            double max1 = *i1 <= *j1 ? *j1 : *i1;
+            double min2 = *i2 <= *j2 ? *i2 : *j2;
+            double max2 = *i2 <= *j2 ? *j2 : *i2;
+            TypeHandle type1 = T.Range(min1, max1);
+            TypeHandle type2 = T.Range(min2, max2);
+            CHECK(!Equal(type1, type2) || (min1 == min2 && max1 == max2));
+          }
+        }
+      }
+    }
+  }
+
   void Array() {
     // Constructor
     for (int i = 0; i < 20; ++i) {
       TypeHandle type = T.Random();
       TypeHandle array = T.Array1(type);
       CHECK(this->IsArray(array));
     }
 
     // Attributes
     for (int i = 0; i < 20; ++i) {
@@ skipping 1208 matching lines @@
 }
 
 
 TEST(ConstantType) {
   CcTest::InitializeVM();
   ZoneTests().Constant();
   HeapTests().Constant();
 }
 
 
+TEST(RangeType) {
+  CcTest::InitializeVM();
+  ZoneTests().Range();
+  HeapTests().Range();
+}
+
+
 TEST(ArrayType) {
   CcTest::InitializeVM();
   ZoneTests().Array();
   HeapTests().Array();
 }
 
 
 TEST(FunctionType) {
   CcTest::InitializeVM();
   ZoneTests().Function();
@@ skipping 104 matching lines @@
   ZoneTests().Convert<HeapType, Handle<HeapType>, Isolate, HeapRep>();
   HeapTests().Convert<Type, Type*, Zone, ZoneRep>();
 }
 
 
 TEST(HTypeFromType) {
   CcTest::InitializeVM();
   ZoneTests().HTypeFromType();
   HeapTests().HTypeFromType();
 }