Establish distributivity for type union & intersection

src/types.h

 // Copyright 2014 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.
 
 #ifndef V8_TYPES_H_
 #define V8_TYPES_H_
 
 #include "handles.h"
 
 namespace v8 {
@@ skipping 184 matching lines @@
 // struct Config {
 //   typedef TypeImpl<Config> Type;
 //   typedef Base;
 //   typedef Struct;
 //   typedef Region;
 //   template<class> struct Handle { typedef type; }  // No template typedefs...
 //   template<class T> static Handle<T>::type handle(T* t);  // !is_bitset(t)
 //   template<class T> static Handle<T>::type cast(Handle<Type>::type);
 //   static bool is_bitset(Type*);
 //   static bool is_class(Type*);
-//   static bool is_constant(Type*);
 //   static bool is_struct(Type*, int tag);
 //   static int as_bitset(Type*);
 //   static i::Handle<i::Map> as_class(Type*);
-//   static i::Handle<i::Object> as_constant(Type*);
 //   static Handle<Struct>::type as_struct(Type*);
 //   static Type* from_bitset(int bitset);
 //   static Handle<Type>::type from_bitset(int bitset, Region*);
-//   static Handle<Type>::type from_class(i::Handle<Map>, int lub, Region*);
-//   static Handle<Type>::type from_constant(i::Handle<Object>, int, Region*);
+//   static Handle<Type>::type from_class(i::Handle<Map>, Region*);
 //   static Handle<Type>::type from_struct(Handle<Struct>::type, int tag);
 //   static Handle<Struct>::type struct_create(int tag, int length, Region*);
 //   static void struct_shrink(Handle<Struct>::type, int length);
 //   static int struct_tag(Handle<Struct>::type);
 //   static int struct_length(Handle<Struct>::type);
 //   static Handle<Type>::type struct_get(Handle<Struct>::type, int);
 //   static void struct_set(Handle<Struct>::type, int, Handle<Type>::type);
-//   static int lub_bitset(Type*);
+//   template<class O>
+//   static i::Handle<O> struct_get_heap(Handle<Struct>::type, int);
+//   template<class O>
+//   static void struct_set_heap(Handle<Struct>::type, int, i::Handle<O>);
 // }
 template<class Config>
 class TypeImpl : public Config::Base {
  public:
   class BitsetType;      // Internal
   class StructuralType;  // Internal
   class UnionType;       // Internal
 
   class ClassType;
   class ConstantType;
@@ skipping 49 matching lines @@
   static TypeHandle Union(TypeHandle type1, TypeHandle type2, Region* reg);
   static TypeHandle Intersect(TypeHandle type1, TypeHandle type2, Region* reg);
 
   static TypeHandle Of(i::Object* value, Region* region) {
     return Config::from_bitset(BitsetType::Lub(value), region);
   }
   static TypeHandle Of(i::Handle<i::Object> value, Region* region) {
     return Of(*value, region);
   }
 
-  bool IsInhabited() {
-    return !this->IsBitset() || BitsetType::IsInhabited(this->AsBitset());
-  }
+  bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); }
 
   bool Is(TypeImpl* that) { return this == that || this->SlowIs(that); }
   template<class TypeHandle>
   bool Is(TypeHandle that) { return this->Is(*that); }
 
   bool Maybe(TypeImpl* that);
   template<class TypeHandle>
   bool Maybe(TypeHandle that) { return this->Maybe(*that); }
 
   bool Equals(TypeImpl* that) { return this->Is(that) && that->Is(this); }
@@ skipping 11 matching lines @@
     return NowOf(*value, region);
   }
   bool NowIs(TypeImpl* that);
   template<class TypeHandle>
   bool NowIs(TypeHandle that)  { return this->NowIs(*that); }
   inline bool NowContains(i::Object* val);
   bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); }
 
   bool NowStable();
 
-  bool IsClass() { return Config::is_class(this); }
-  bool IsConstant() { return Config::is_constant(this); }
-  bool IsArray() { return Config::is_struct(this, StructuralType::kArrayTag); }
+  bool IsClass() {
+    return Config::is_class(this)
+        || Config::is_struct(this, StructuralType::kClassTag);
+  }
+  bool IsConstant() {
+    return Config::is_struct(this, StructuralType::kConstantTag);
+  }
+  bool IsArray() {
+    return Config::is_struct(this, StructuralType::kArrayTag);
+  }
   bool IsFunction() {
     return Config::is_struct(this, StructuralType::kFunctionTag);
   }
 
   ClassType* AsClass() { return ClassType::cast(this); }
   ConstantType* AsConstant() { return ConstantType::cast(this); }
   ArrayType* AsArray() { return ArrayType::cast(this); }
   FunctionType* AsFunction() { return FunctionType::cast(this); }
 
   int NumClasses();
@@ skipping 20 matching lines @@
   void TypePrint(FILE* out, PrintDimension = BOTH_DIMS);
 
  protected:
   template<class> friend class Iterator;
   template<class> friend class TypeImpl;
 
   template<class T>
   static typename Config::template Handle<T>::type handle(T* type) {
     return Config::handle(type);
   }
+  TypeImpl* unhandle() { return this; }

[Benedikt Meurer, 2014/05/23 05:09:00]

Nit: Can we come up with a better name? "unhandle" is horrible.

 
   bool IsNone() { return this == None(); }
   bool IsAny() { return this == Any(); }
   bool IsBitset() { return Config::is_bitset(this); }
   bool IsUnion() { return Config::is_struct(this, StructuralType::kUnionTag); }
 
   int AsBitset() {
     ASSERT(this->IsBitset());
     return static_cast<BitsetType*>(this)->Bitset();
   }
   UnionType* AsUnion() { return UnionType::cast(this); }
 
   bool SlowIs(TypeImpl* that);
 
-  bool InUnion(UnionHandle unioned, int current_size);
+  TypeHandle Narrow(int bitset, Region* region);
+  int BoundBy(TypeImpl* that);
+  int IndexInUnion(int bound, UnionHandle unioned, int current_size);
   static int ExtendUnion(
-      UnionHandle unioned, TypeHandle t, int current_size);
-  static int ExtendIntersection(
-      UnionHandle unioned, TypeHandle t, TypeHandle other, int current_size);
+      UnionHandle unioned, int current_size, TypeHandle t,
+      TypeHandle other, bool is_intersect, Region* region);
 
   int BitsetGlb() { return BitsetType::Glb(this); }
   int BitsetLub() { return BitsetType::Lub(this); }
+  int InherentBitsetLub() { return BitsetType::InherentLub(this); }
 };
 
 
 template<class Config>
 class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
  private:
   friend class TypeImpl<Config>;
 
   enum {
     #define DECLARE_TYPE(type, value) k##type = (value),
     BITSET_TYPE_LIST(DECLARE_TYPE)
     #undef DECLARE_TYPE
     kUnusedEOL = 0
   };
 
   int Bitset() { return Config::as_bitset(this); }
 
-  static BitsetType* New(int bitset) {
+  static TypeImpl* New(int bitset) {
     return static_cast<BitsetType*>(Config::from_bitset(bitset));
   }
   static TypeHandle New(int bitset, Region* region) {
     return Config::from_bitset(bitset, region);
   }
 
   static bool IsInhabited(int bitset) {
     return (bitset & kRepresentation) && (bitset & kSemantic);
   }
 
   static int Glb(TypeImpl* type);  // greatest lower bound that's a bitset
   static int Lub(TypeImpl* type);  // least upper bound that's a bitset
   static int Lub(i::Object* value);
   static int Lub(i::Map* map);
+  static int InherentLub(TypeImpl* type);
 
   static const char* Name(int bitset);
   static void BitsetTypePrint(FILE* out, int bitset);
 };
 
 
 // Internal
 // A structured type contains a tag and a variable number of type fields.
 template<class Config>
 class TypeImpl<Config>::StructuralType : public TypeImpl<Config> {
  protected:
   template<class> friend class TypeImpl;
   friend struct ZoneTypeConfig;  // For tags.
   friend struct HeapTypeConfig;
 
   enum Tag {
     kClassTag,
     kConstantTag,
     kArrayTag,
     kFunctionTag,
     kUnionTag
   };
 
   int Length() {
     return Config::struct_length(Config::as_struct(this));
   }
   TypeHandle Get(int i) {
+    ASSERT(0 <= i && i < this->Length());
     return Config::struct_get(Config::as_struct(this), i);
   }
   void Set(int i, TypeHandle type) {
+    ASSERT(0 <= i && i < this->Length());
     Config::struct_set(Config::as_struct(this), i, type);
   }
   void Shrink(int length) {
+    ASSERT(2 <= length && length <= this->Length());
     Config::struct_shrink(Config::as_struct(this), length);
   }
+  template<class O> i::Handle<O> GetHeap(int i) {
+    ASSERT(0 <= i && i < this->Length());
+    return Config::template struct_get_heap<O>(Config::as_struct(this), i);
+  }
+  template<class O> void SetHeap(int i, i::Handle<O> x) {
+    ASSERT(0 <= i && i < this->Length());
+    Config::struct_set_heap(Config::as_struct(this), i, x);
+  }
 
   static TypeHandle New(Tag tag, int length, Region* region) {
+    ASSERT(1 <= length);
     return Config::from_struct(Config::struct_create(tag, length, region));
   }
 };
 
 
+// Internal
+// A union is a structured type with the following invariants:
+// - its length is at least 2
+// - at most one field is a bitset, and it must go into index 0
+// - no field is a union
+// - no field is a subtype of any other field
 template<class Config>
-class TypeImpl<Config>::ClassType : public TypeImpl<Config> {
+class TypeImpl<Config>::UnionType : public StructuralType {
  public:
-  i::Handle<i::Map> Map() { return Config::as_class(this); }
+  static UnionHandle New(int length, Region* region) {
+    return Config::template cast<UnionType>(
+        StructuralType::New(StructuralType::kUnionTag, length, region));
+  }
+
+  static UnionType* cast(TypeImpl* type) {
+    ASSERT(type->IsUnion());
+    return static_cast<UnionType*>(type);
+  }
+
+  bool Wellformed();
+};
+
+
+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 GetHeap<i::Map>(1);
+  }
+
+  static ClassHandle New(
+      i::Handle<i::Map> map, TypeHandle bound, Region* region) {
+    ClassHandle type = Config::template cast<ClassType>(
+        StructuralType::New(StructuralType::kClassTag, 2, region));
+    type->Set(0, bound);
+    type->SetHeap(1, map);
+    return type;
+  }
 
   static ClassHandle New(i::Handle<i::Map> map, Region* region) {
-    return Config::template cast<ClassType>(
-        Config::from_class(map, BitsetType::Lub(*map), 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);
+    }
   }
 
   static ClassType* cast(TypeImpl* type) {
     ASSERT(type->IsClass());
     return static_cast<ClassType*>(type);
   }
 };
 
 
 template<class Config>
-class TypeImpl<Config>::ConstantType : public TypeImpl<Config> {
+class TypeImpl<Config>::ConstantType : public StructuralType {
  public:
-  i::Handle<i::Object> Value() { return Config::as_constant(this); }
+  TypeHandle Bound() { return this->Get(0); }
+  i::Handle<i::Object> Value() { return this->template GetHeap<i::Object>(1); }
+
+  static ConstantHandle New(
+      i::Handle<i::Object> value, TypeHandle bound, Region* region) {
+    ConstantHandle type = Config::template cast<ConstantType>(
+        StructuralType::New(StructuralType::kConstantTag, 2, region));
+    type->Set(0, bound);
+    type->SetHeap(1, value);
+    return type;
+  }
 
   static ConstantHandle New(i::Handle<i::Object> value, Region* region) {
-    return Config::template cast<ConstantType>(
-        Config::from_constant(value, BitsetType::Lub(*value), region));
+    TypeHandle bound = BitsetType::New(BitsetType::Lub(*value), region);
+    return New(value, bound, region);
   }
 
   static ConstantType* cast(TypeImpl* type) {
     ASSERT(type->IsConstant());
     return static_cast<ConstantType*>(type);
   }
 };
 
 
-// Internal
-// A union is a structured type with the following invariants:
-// - its length is at least 2
-// - at most one field is a bitset, and it must go into index 0
-// - no field is a union
-template<class Config>
-class TypeImpl<Config>::UnionType : public StructuralType {
- public:
-  static UnionHandle New(int length, Region* region) {
-    return Config::template cast<UnionType>(
-        StructuralType::New(StructuralType::kUnionTag, length, region));
-  }
-
-  static UnionType* cast(TypeImpl* type) {
-    ASSERT(type->IsUnion());
-    return static_cast<UnionType*>(type);
-  }
-};
-
-
 template<class Config>
 class TypeImpl<Config>::ArrayType : public StructuralType {
  public:
-  TypeHandle Element() { return this->Get(0); }
+  TypeHandle Bound() { return this->Get(0); }
+  TypeHandle Element() { return this->Get(1); }
+
+  static ArrayHandle New(TypeHandle element, TypeHandle bound, Region* region) {
+    ArrayHandle type = Config::template cast<ArrayType>(
+        StructuralType::New(StructuralType::kArrayTag, 2, region));
+    type->Set(0, bound);
+    type->Set(1, element);
+    return type;
+  }
 
   static ArrayHandle New(TypeHandle element, Region* region) {
-    ArrayHandle type = Config::template cast<ArrayType>(
-        StructuralType::New(StructuralType::kArrayTag, 1, region));
-    type->Set(0, element);
-    return type;
+    TypeHandle bound = BitsetType::New(BitsetType::kArray, region);
+    return New(element, bound, region);
   }
 
   static ArrayType* cast(TypeImpl* type) {
     ASSERT(type->IsArray());
     return static_cast<ArrayType*>(type);
   }
 };
 
 
 template<class Config>
 class TypeImpl<Config>::FunctionType : public StructuralType {
  public:
-  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); }
+  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); }
 
-  void InitParameter(int i, TypeHandle type) { this->Set(2 + i, type); }
+  void InitParameter(int i, TypeHandle type) { this->Set(3 + i, type); }
+
+  static FunctionHandle New(
+      TypeHandle result, TypeHandle receiver, TypeHandle bound,
+      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);
+    return type;
+  }
 
   static FunctionHandle New(
       TypeHandle result, TypeHandle receiver, int arity, Region* region) {
-    FunctionHandle type = Config::template cast<FunctionType>(
-        StructuralType::New(StructuralType::kFunctionTag, 2 + arity, region));
-    type->Set(0, result);
-    type->Set(1, receiver);
-    return type;
+    TypeHandle bound = BitsetType::New(BitsetType::kFunction, region);
+    return New(result, receiver, bound, arity, region);
   }
 
   static FunctionType* cast(TypeImpl* type) {
     ASSERT(type->IsFunction());
     return static_cast<FunctionType*>(type);
   }
 };
 
 
 template<class Config> template<class T>
@@ skipping 26 matching lines @@
   class Base {};
   typedef void* Struct;
   typedef i::Zone Region;
   template<class T> struct Handle { typedef T* type; };
 
   template<class T> static inline T* handle(T* type);
   template<class T> static inline T* cast(Type* type);
 
   static inline bool is_bitset(Type* type);
   static inline bool is_class(Type* type);
-  static inline bool is_constant(Type* type);
   static inline bool is_struct(Type* type, int tag);
 
   static inline int as_bitset(Type* type);
+  static inline i::Handle<i::Map> as_class(Type* type);
   static inline Struct* as_struct(Type* type);
-  static inline i::Handle<i::Map> as_class(Type* type);
-  static inline i::Handle<i::Object> as_constant(Type* type);
 
   static inline Type* from_bitset(int bitset);
   static inline Type* from_bitset(int bitset, Zone* zone);
+  static inline Type* from_class(i::Handle<i::Map> map, Zone* zone);
   static inline Type* from_struct(Struct* structured);
-  static inline Type* from_class(i::Handle<i::Map> map, int lub, Zone* zone);
-  static inline Type* from_constant(
-      i::Handle<i::Object> value, int lub, Zone* zone);
 
   static inline Struct* struct_create(int tag, int length, Zone* zone);
-  static inline void struct_shrink(Struct* structured, int length);
-  static inline int struct_tag(Struct* structured);
-  static inline int struct_length(Struct* structured);
-  static inline Type* struct_get(Struct* structured, int i);
-  static inline void struct_set(Struct* structured, int i, Type* type);
-
-  static inline int lub_bitset(Type* type);
+  static inline void struct_shrink(Struct* structure, int length);
+  static inline int struct_tag(Struct* structure);
+  static inline int struct_length(Struct* structure);
+  static inline Type* struct_get(Struct* structure, int i);
+  static inline void struct_set(Struct* structure, int i, Type* type);
+  template<class O>
+  static inline i::Handle<O> struct_get_heap(Struct* structure, int i);
+  template<class O> static inline void struct_set_heap(
+      Struct* structure, int i, i::Handle<O> x);
 };
 
 typedef TypeImpl<ZoneTypeConfig> Type;
 
 
 // Heap-allocated types are either smis for bitsets, maps for classes, boxes for
 // constants, or fixed arrays for unions.
 struct HeapTypeConfig {
   typedef TypeImpl<HeapTypeConfig> Type;
   typedef i::Object Base;
   typedef i::FixedArray Struct;
   typedef i::Isolate Region;
   template<class T> struct Handle { typedef i::Handle<T> type; };
 
   template<class T> static inline i::Handle<T> handle(T* type);
   template<class T> static inline i::Handle<T> cast(i::Handle<Type> type);
 
   static inline bool is_bitset(Type* type);
   static inline bool is_class(Type* type);
-  static inline bool is_constant(Type* type);
   static inline bool is_struct(Type* type, int tag);
 
   static inline int as_bitset(Type* type);
   static inline i::Handle<i::Map> as_class(Type* type);
-  static inline i::Handle<i::Object> as_constant(Type* type);
   static inline i::Handle<Struct> as_struct(Type* type);
 
   static inline Type* from_bitset(int bitset);
   static inline i::Handle<Type> from_bitset(int bitset, Isolate* isolate);
   static inline i::Handle<Type> from_class(
-      i::Handle<i::Map> map, int lub, Isolate* isolate);
-  static inline i::Handle<Type> from_constant(
-      i::Handle<i::Object> value, int lub, Isolate* isolate);
-  static inline i::Handle<Type> from_struct(i::Handle<Struct> structured);
+      i::Handle<i::Map> map, Isolate* isolate);
+  static inline i::Handle<Type> from_struct(i::Handle<Struct> structure);
 
   static inline i::Handle<Struct> struct_create(
       int tag, int length, Isolate* isolate);
-  static inline void struct_shrink(i::Handle<Struct> structured, int length);
-  static inline int struct_tag(i::Handle<Struct> structured);
-  static inline int struct_length(i::Handle<Struct> structured);
-  static inline i::Handle<Type> struct_get(i::Handle<Struct> structured, int i);
+  static inline void struct_shrink(i::Handle<Struct> structure, int length);
+  static inline int struct_tag(i::Handle<Struct> structure);
+  static inline int struct_length(i::Handle<Struct> structure);
+  static inline i::Handle<Type> struct_get(i::Handle<Struct> structure, int i);
   static inline void struct_set(
-      i::Handle<Struct> structured, int i, i::Handle<Type> type);
-
-  static inline int lub_bitset(Type* type);
+      i::Handle<Struct> structure, int i, i::Handle<Type> type);
+  template<class O>
+  static inline i::Handle<O> struct_get_heap(
+      i::Handle<Struct> structure, int i);
+  template<class O>
+  static inline void struct_set_heap(
+      i::Handle<Struct> structure, int i, i::Handle<O> x);
 };
 
 typedef TypeImpl<HeapTypeConfig> HeapType;
 
 
 // A simple struct to represent a pair of lower/upper type bounds.
 template<class Config>
 struct BoundsImpl {
   typedef TypeImpl<Config> Type;
   typedef typename Type::TypeHandle TypeHandle;
@@ skipping 44 matching lines @@
   bool Narrows(BoundsImpl that) {
     return that.lower->Is(this->lower) && this->upper->Is(that.upper);
   }
 };
 
 typedef BoundsImpl<ZoneTypeConfig> Bounds;
 
 } }  // namespace v8::internal
 
 #endif  // V8_TYPES_H_