Redesign of the internal type system.

src/types.h

Index: src/types.h
diff --git a/src/types.h b/src/types.h
index cca8b3167b4bb9b86773d7fcf40959490a9164f0..2f96c333f2f0446f991a845d855563578c660b41 100644
--- a/src/types.h
+++ b/src/types.h
@@ -5,6 +5,7 @@
 #ifndef V8_TYPES_H_
 #define V8_TYPES_H_
 
+#include "src/conversions.h"
 #include "src/factory.h"
 #include "src/handles.h"
 #include "src/ostreams.h"
@@ -112,8 +113,8 @@ namespace internal {
 // PROPERTIES
 //
 // Various formal properties hold for constructors, operators, and predicates
-// over types. For example, constructors are injective, subtyping is a complete
-// partial order, union and intersection satisfy the usual algebraic properties.
+// over types. For example, constructors are injective and subtyping is a
+// complete partial order.
 //
 // See test/cctest/test-types.cc for a comprehensive executable specification,
 // especially with respect to the properties of the more exotic 'temporal'
@@ -208,11 +209,35 @@ namespace internal {
                          kUndefined | kInternal) \
   V(Any,                 -1)
 
-#define BITSET_TYPE_LIST(V) \
-  MASK_BITSET_TYPE_LIST(V) \
+/*
+ * The following diagrams show how integers (in the mathematical sense) are
+ * divided among the different atomic numerical types.
+ *
+ * If SmiValuesAre31Bits():
+ *
+ *   ON    OS32     OSS     US     OU31    OU32     ON
+ * ______[_______[_______[_______[_______[_______[_______
+ *     -2^31   -2^30     0      2^30    2^31    2^32
+ *
+  * Otherwise:

[rossberg, 2014/09/10 15:44:15]

Nit: indentation off

[neis1, 2014/09/11 12:58:12]

Done.

+ *
+ *   ON         OSS             US         OU32     ON
+ * ______[_______________[_______________[_______[_______
+ *     -2^31             0              2^31    2^32
+ *
+ *
+ * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1.
+ *
+ */
+
+#define PROPER_BITSET_TYPE_LIST(V) \
   REPRESENTATION_BITSET_TYPE_LIST(V) \
   SEMANTIC_BITSET_TYPE_LIST(V)
 
+#define BITSET_TYPE_LIST(V) \
+  MASK_BITSET_TYPE_LIST(V) \
+  PROPER_BITSET_TYPE_LIST(V)
+
 
 // -----------------------------------------------------------------------------
 // The abstract Type class, parameterized over the low-level representation.
@@ -279,17 +304,17 @@ class TypeImpl : public Config::Base {
     static TypeHandle type(Region* region) {                                  \
       return BitsetType::New(BitsetType::k##type, region);                    \
     }
-  BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
+  PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
   #undef DEFINE_TYPE_CONSTRUCTOR
 
   static TypeHandle Class(i::Handle<i::Map> map, Region* region) {
     return ClassType::New(map, region);
   }
   static TypeHandle Constant(i::Handle<i::Object> value, Region* region) {
-    // TODO(neis): Return RangeType for numerical values.
     return ConstantType::New(value, region);
   }
-  static TypeHandle Range(double min, double max, Region* region) {
+  static TypeHandle Range(
+      i::Handle<i::Object> min, i::Handle<i::Object> max, Region* region) {
     return RangeType::New(min, max, region);
   }
   static TypeHandle Context(TypeHandle outer, Region* region) {
@@ -357,7 +382,7 @@ class TypeImpl : public Config::Base {
   template<class TypeHandle>
   bool Equals(TypeHandle that) { return this->Equals(*that); }
 
-  // Equivalent to Constant(value)->Is(this), but avoiding allocation.
+  // Equivalent to Constant(val)->Is(this), but avoiding allocation.
   bool Contains(i::Object* val);
   bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); }
 
@@ -466,16 +491,42 @@ class TypeImpl : public Config::Base {
 
   int BitsetGlb() { return BitsetType::Glb(this); }
   int BitsetLub() { return BitsetType::Lub(this); }
-  int InherentBitsetLub() { return BitsetType::InherentLub(this); }
 
   bool SlowIs(TypeImpl* that);
 
-  TypeHandle Rebound(int bitset, Region* region);
-  int BoundBy(TypeImpl* that);
-  int IndexInUnion(int bound, UnionHandle unioned, int current_size);
-  static int ExtendUnion(
-      UnionHandle unioned, int current_size, TypeHandle t,
-      TypeHandle other, bool is_intersect, Region* region);
+  static bool IsInteger(double x) {
+    return nearbyint(x) == x && !i::IsMinusZero(x);  // Allows for infinities.
+  }
+  static bool IsInteger(i::Object* x) {
+    return x->IsNumber() && IsInteger(x->Number());
+  }
+
+  struct Limits {
+    i::Handle<i::Object> min;
+    i::Handle<i::Object> max;
+    Limits(i::Handle<i::Object> min, i::Handle<i::Object> max) :
+      min(min), max(max) {}
+    explicit Limits(RangeType* range) :
+      min(range->MinV()), max(range->MaxV()) {}
+  };
+
+  static Limits intersect(Limits lhs, Limits rhs);
+  static Limits union_(Limits lhs, Limits rhs);
+  static bool overlap(RangeType* lhs, RangeType* rhs);
+  static bool contains(RangeType* lhs, RangeType* rhs);
+  static bool contains(RangeType* range, i::Object* val);
+
+  RangeType* GetRange();
+  static int UpdateRange(
+      RangeHandle type, UnionHandle result, int size, Region* region);
+
+  bool SimplyEquals(TypeImpl* that);
+  static int AddToUnion(
+      TypeHandle type, UnionHandle result, int size, Region* region);
+  static int IntersectAux(
+      TypeHandle type, TypeHandle other,
+      UnionHandle result, int size, Region* region);
+  static TypeHandle NormalizeUnion(UnionHandle unioned, int size);
 };
 
 
@@ -497,9 +548,11 @@ class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
   int Bitset() { return Config::as_bitset(this); }
 
   static TypeImpl* New(int bitset) {
+    DCHECK(bitset == kNone || IsInhabited(bitset));
     return static_cast<BitsetType*>(Config::from_bitset(bitset));
   }
   static TypeHandle New(int bitset, Region* region) {
+    DCHECK(bitset == kNone || IsInhabited(bitset));
     return Config::from_bitset(bitset, region);
   }
 
@@ -518,12 +571,14 @@ class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
   static int Lub(int32_t value);
   static int Lub(uint32_t value);
   static int Lub(i::Map* map);
-  static int Lub(double min, double max);
-  static int InherentLub(TypeImpl* type);
+  static int Lub(Limits lim);
+  static double Min(int bitset);
 
   static const char* Name(int bitset);
   static void Print(OStream& os, int bitset);  // NOLINT
-  using TypeImpl::PrintTo;
+#ifdef DEBUG
+  static void Print(int bitset);
+#endif
 };
 
 
@@ -609,36 +664,21 @@ class TypeImpl<Config>::UnionType : public StructuralType {
 template<class Config>
 class TypeImpl<Config>::ClassType : public StructuralType {
  public:
-  TypeHandle Bound(Region* region) {
-    return Config::is_class(this)
-        ? BitsetType::New(BitsetType::Lub(*Config::as_class(this)), region)
-        : this->Get(0);
-  }
   i::Handle<i::Map> Map() {
     return Config::is_class(this)
         ? Config::as_class(this)
-        : this->template GetValue<i::Map>(1);
-  }
-
-  static ClassHandle New(
-      i::Handle<i::Map> map, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(*map)));
-    ClassHandle type = Config::template cast<ClassType>(
-        StructuralType::New(StructuralType::kClassTag, 2, region));
-    type->Set(0, bound);
-    type->SetValue(1, map);
-    return type;
+        : this->template GetValue<i::Map>(0);
   }
 
   static ClassHandle New(i::Handle<i::Map> map, Region* region) {
     ClassHandle type =
         Config::template cast<ClassType>(Config::from_class(map, region));
-    if (type->IsClass()) {
-      return type;
-    } else {
-      TypeHandle bound = BitsetType::New(BitsetType::Lub(*map), region);
-      return New(map, bound, region);
+    if (!type->IsClass()) {
+      type = Config::template cast<ClassType>(
+        StructuralType::New(StructuralType::kClassTag, 1, region));

[rossberg, 2014/09/10 15:44:15]

Nit: style guide wants +4 indentation for line continuations.

[neis1, 2014/09/11 12:58:12]

Done.

+      type->SetValue(0, map);
     }
+    return type;
   }
 
   static ClassType* cast(TypeImpl* type) {
@@ -654,22 +694,15 @@ class TypeImpl<Config>::ClassType : public StructuralType {
 template<class Config>
 class TypeImpl<Config>::ConstantType : public StructuralType {
  public:
-  TypeHandle Bound() { return this->Get(0); }
-  i::Handle<i::Object> Value() { return this->template GetValue<i::Object>(1); }
-
-  static ConstantHandle New(
-      i::Handle<i::Object> value, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(*value)));
-    ConstantHandle type = Config::template cast<ConstantType>(
-        StructuralType::New(StructuralType::kConstantTag, 2, region));
-    type->Set(0, bound);
-    type->SetValue(1, value);
-    return type;
+  i::Handle<i::Object> Value() {
+    return this->template GetValue<i::Object>(0);

[rossberg, 2014/09/10 15:44:15]

Nit: probably fits on previous line

[neis1, 2014/09/11 12:58:12]

Done.

   }
 
   static ConstantHandle New(i::Handle<i::Object> value, Region* region) {
-    TypeHandle bound = BitsetType::New(BitsetType::Lub(*value), region);
-    return New(value, bound, region);
+    ConstantHandle type = Config::template cast<ConstantType>(
+        StructuralType::New(StructuralType::kConstantTag, 1, region));
+    type->SetValue(0, value);
+    return type;
   }
 
   static ConstantType* cast(TypeImpl* type) {
@@ -681,31 +714,35 @@ class TypeImpl<Config>::ConstantType : public StructuralType {
 
 // -----------------------------------------------------------------------------
 // Range types.
+// They represent continuous integer intervals in the form of a minimum

[rossberg, 2014/09/10 15:44:15]

This should go to the top, along with the other explanations of the type system.

[neis1, 2014/09/11 12:58:12]

Done.

+// and a maximum value.  Either value might be an infinity.
+//
+// Constant(v) is considered a subtype of Range(x..y) if v happens to be an
+// integer between x and y.
 
 template<class Config>
 class TypeImpl<Config>::RangeType : public StructuralType {
  public:
-  TypeHandle Bound() { return this->Get(0); }
-  double Min() { return this->template GetValue<i::HeapNumber>(1)->value(); }
-  double Max() { return this->template GetValue<i::HeapNumber>(2)->value(); }
+  i::Handle<i::Object> MinV() { return this->template GetValue<i::Object>(0); }
+  i::Handle<i::Object> MaxV() { return this->template GetValue<i::Object>(1); }
+  double Min() { return MinV()->Number(); }
+  double Max() { return MaxV()->Number(); }

[rossberg, 2014/09/10 15:44:15]

Since we call the method to get a numeric value from an object 'Value' in other
places, I think it would be more consistent to name these 4 methods Min, Max,
MinValue, MaxValue.

[neis1, 2014/09/11 12:58:12]

Not sure I'm following.  Are you suggesting to expand the V to Value (fine with
me), or to rename Max to MaxValue and MaxV to Max (not so fine with me).

[rossberg, 2014/09/15 15:58:29]

The latter. It's more consistent with our naming elsewhere.

[neis1, 2014/09/16 10:03:59]

But less consistent with the naming here, such as StructuralType::GetValue,
StructuralType::SetValue, Constant::Value, where Value means an Ojbect pointer.

[rossberg, 2014/09/16 14:04:40]

OK, fair enough. Actually, I'd say, just remove the 'double' wrappers from the
interface, and rename the other two to Min and Max.

[neis1, 2014/09/18 13:05:18]

Done.

 
   static RangeHandle New(
-      double min, double max, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(min, max)));
+      i::Handle<i::Object> min, i::Handle<i::Object> max, Region* region) {
+    DCHECK(min->Number() <= max->Number());
     RangeHandle type = Config::template cast<RangeType>(
-        StructuralType::New(StructuralType::kRangeTag, 3, region));
-    type->Set(0, bound);
-    Factory* factory = Config::isolate(region)->factory();
-    Handle<HeapNumber> minV = factory->NewHeapNumber(min);
-    Handle<HeapNumber> maxV = factory->NewHeapNumber(max);
-    type->SetValue(1, minV);
-    type->SetValue(2, maxV);
+        StructuralType::New(StructuralType::kRangeTag, 2, region));
+    type->SetValue(0, min);
+    type->SetValue(1, max);
+#ifdef DEBUG

[rossberg, 2014/09/10 15:44:15]

Debugging left-overs?

[neis1, 2014/09/11 12:58:12]

Done.

+    type->Print();
+#endif
     return type;
   }
 
-  static RangeHandle New(double min, double max, Region* region) {
-    TypeHandle bound = BitsetType::New(BitsetType::Lub(min, max), region);
-    return New(min, max, bound, region);
+  static RangeHandle New(Limits lim, Region* region) {
+    return New(lim.min, lim.max, region);
   }
 
   static RangeType* cast(TypeImpl* type) {
@@ -721,25 +758,15 @@ class TypeImpl<Config>::RangeType : public StructuralType {
 template<class Config>
 class TypeImpl<Config>::ContextType : public StructuralType {
  public:
-  TypeHandle Bound() { return this->Get(0); }
-  TypeHandle Outer() { return this->Get(1); }
+  TypeHandle Outer() { return this->Get(0); }
 
-  static ContextHandle New(TypeHandle outer, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(
-        bound->AsBitset(), BitsetType::kInternal & BitsetType::kTaggedPtr));
+  static ContextHandle New(TypeHandle outer, Region* region) {
     ContextHandle type = Config::template cast<ContextType>(
-        StructuralType::New(StructuralType::kContextTag, 2, region));
-    type->Set(0, bound);
-    type->Set(1, outer);
+        StructuralType::New(StructuralType::kContextTag, 1, region));
+    type->Set(0, outer);
     return type;
   }
 
-  static ContextHandle New(TypeHandle outer, Region* region) {
-    TypeHandle bound = BitsetType::New(
-        BitsetType::kInternal & BitsetType::kTaggedPtr, region);
-    return New(outer, bound, region);
-  }
-
   static ContextType* cast(TypeImpl* type) {
     DCHECK(type->IsContext());
     return static_cast<ContextType*>(type);
@@ -753,23 +780,15 @@ class TypeImpl<Config>::ContextType : public StructuralType {
 template<class Config>
 class TypeImpl<Config>::ArrayType : public StructuralType {
  public:
-  TypeHandle Bound() { return this->Get(0); }
-  TypeHandle Element() { return this->Get(1); }
+  TypeHandle Element() { return this->Get(0); }
 
-  static ArrayHandle New(TypeHandle element, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::kArray));
+  static ArrayHandle New(TypeHandle element, Region* region) {
     ArrayHandle type = Config::template cast<ArrayType>(
-        StructuralType::New(StructuralType::kArrayTag, 2, region));
-    type->Set(0, bound);
-    type->Set(1, element);
+        StructuralType::New(StructuralType::kArrayTag, 1, region));
+    type->Set(0, element);
     return type;
   }
 
-  static ArrayHandle New(TypeHandle element, Region* region) {
-    TypeHandle bound = BitsetType::New(BitsetType::kArray, region);
-    return New(element, bound, region);
-  }
-
   static ArrayType* cast(TypeImpl* type) {
     DCHECK(type->IsArray());
     return static_cast<ArrayType*>(type);
@@ -783,32 +802,22 @@ class TypeImpl<Config>::ArrayType : public StructuralType {
 template<class Config>
 class TypeImpl<Config>::FunctionType : public StructuralType {
  public:
-  int Arity() { return this->Length() - 3; }
-  TypeHandle Bound() { return this->Get(0); }
-  TypeHandle Result() { return this->Get(1); }
-  TypeHandle Receiver() { return this->Get(2); }
-  TypeHandle Parameter(int i) { return this->Get(3 + i); }
+  int Arity() { return this->Length() - 2; }
+  TypeHandle Result() { return this->Get(0); }
+  TypeHandle Receiver() { return this->Get(1); }
+  TypeHandle Parameter(int i) { return this->Get(2 + i); }
 
-  void InitParameter(int i, TypeHandle type) { this->Set(3 + i, type); }
+  void InitParameter(int i, TypeHandle type) { this->Set(2 + i, type); }
 
   static FunctionHandle New(
-      TypeHandle result, TypeHandle receiver, TypeHandle bound,
-      int arity, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::kFunction));
+      TypeHandle result, TypeHandle receiver, int arity, Region* region) {
     FunctionHandle type = Config::template cast<FunctionType>(
-        StructuralType::New(StructuralType::kFunctionTag, 3 + arity, region));
-    type->Set(0, bound);
-    type->Set(1, result);
-    type->Set(2, receiver);
+        StructuralType::New(StructuralType::kFunctionTag, 2 + arity, region));
+    type->Set(0, result);
+    type->Set(1, receiver);
     return type;
   }
 
-  static FunctionHandle New(
-      TypeHandle result, TypeHandle receiver, int arity, Region* region) {
-    TypeHandle bound = BitsetType::New(BitsetType::kFunction, region);
-    return New(result, receiver, bound, arity, region);
-  }
-
   static FunctionType* cast(TypeImpl* type) {
     DCHECK(type->IsFunction());
     return static_cast<FunctionType*>(type);
@@ -853,11 +862,6 @@ struct ZoneTypeConfig {
   typedef i::Zone Region;
   template<class T> struct Handle { typedef T* type; };
 
-  // TODO(neis): This will be removed again once we have struct_get_double().
-  static inline i::Isolate* isolate(Region* region) {
-    return region->isolate();
-  }
-
   template<class T> static inline T* handle(T* type);
   template<class T> static inline T* cast(Type* type);
 
@@ -900,11 +904,6 @@ struct HeapTypeConfig {
   typedef i::Isolate Region;
   template<class T> struct Handle { typedef i::Handle<T> type; };
 
-  // TODO(neis): This will be removed again once we have struct_get_double().
-  static inline i::Isolate* isolate(Region* region) {
-    return region;
-  }
-
   template<class T> static inline i::Handle<T> handle(T* type);
   template<class T> static inline i::Handle<T> cast(i::Handle<Type> type);