Establish distributivity for type union & intersection

src/types.cc

 // 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.
 
 #include "types.h"
 
 #include "string-stream.h"
 #include "types-inl.h"
 
 namespace v8 {
@@ skipping 121 matching lines @@
   if (type->IsBitset()) {
     return type->AsBitset();
   } else if (type->IsUnion()) {
     UnionHandle unioned = handle(type->AsUnion());
     int bitset = kNone;
     for (int i = 0; i < unioned->Length(); ++i) {
       bitset |= unioned->Get(i)->BitsetLub();
     }
     return bitset;
   } else if (type->IsClass()) {
-    int bitset = Config::lub_bitset(type);
-    return bitset ? bitset : Lub(*type->AsClass()->Map());
+    // Little hack to avoid the need for a region for handlification here...
+    return Config::is_class(type) ? Lub(*Config::as_class(type)) :
+        type->AsClass()->Bound(NULL)->AsBitset();
   } else if (type->IsConstant()) {
-    int bitset = Config::lub_bitset(type);
-    return bitset ? bitset : Lub(*type->AsConstant()->Value());
+    return type->AsConstant()->Bound()->AsBitset();
+  } else if (type->IsArray()) {
+    return type->AsArray()->Bound()->AsBitset();
+  } else if (type->IsFunction()) {
+    return type->AsFunction()->Bound()->AsBitset();
+  } else {
+    UNREACHABLE();
+    return kNone;
+  }
+}
+
+
+// Get the smallest bitset subsuming this type, ignoring current bounds.
+template<class Config>
+int TypeImpl<Config>::BitsetType::InherentLub(TypeImpl* type) {
+  DisallowHeapAllocation no_allocation;
+  if (type->IsBitset()) {
+    return type->AsBitset();
+  } else if (type->IsUnion()) {
+    UnionHandle unioned = handle(type->AsUnion());
+    int bitset = kNone;
+    for (int i = 0; i < unioned->Length(); ++i) {
+      bitset |= unioned->Get(i)->InherentBitsetLub();
+    }
+    return bitset;
+  } else if (type->IsClass()) {
+    return Lub(*type->AsClass()->Map());
+  } else if (type->IsConstant()) {
+    return Lub(*type->AsConstant()->Value());
   } else if (type->IsArray()) {
     return kArray;
   } else if (type->IsFunction()) {
     return kFunction;
   } else {
     UNREACHABLE();
     return kNone;
   }
 }
 
@@ skipping 123 matching lines @@
   DisallowHeapAllocation no_allocation;
 
   // Fast path for bitsets.
   if (this->IsNone()) return true;
   if (that->IsBitset()) {
     return (BitsetType::Lub(this) | that->AsBitset()) == that->AsBitset();
   }
 
   if (that->IsClass()) {
     return this->IsClass()
-        && *this->AsClass()->Map() == *that->AsClass()->Map();
+        && *this->AsClass()->Map() == *that->AsClass()->Map()
+        && ((Config::is_class(that) && Config::is_class(this)) ||
+            BitsetType::New(this->BitsetLub())->Is(
+                BitsetType::New(that->BitsetLub())));
   }
   if (that->IsConstant()) {
     return this->IsConstant()
-        && *this->AsConstant()->Value() == *that->AsConstant()->Value();
+        && *this->AsConstant()->Value() == *that->AsConstant()->Value()
+        && this->AsConstant()->Bound()->Is(that->AsConstant()->Bound());
   }
   if (that->IsArray()) {
     return this->IsArray()
         && this->AsArray()->Element()->Equals(that->AsArray()->Element());
   }
   if (that->IsFunction()) {
     // We currently do not allow for any variance here, in order to keep
     // Union and Intersect operations simple.
     if (!this->IsFunction()) return false;
     FunctionType* this_fun = this->AsFunction();
@@ skipping 112 matching lines @@
     return this->Equals(that);
   }
 
   return false;
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::Contains(i::Object* value) {
   DisallowHeapAllocation no_allocation;
-
   for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
     if (*it.Current() == value) return true;
   }
   return BitsetType::New(BitsetType::Lub(value))->Is(this);
 }
 
 
 template<class Config>
-bool TypeImpl<Config>::InUnion(UnionHandle unioned, int current_size) {
-  ASSERT(!this->IsUnion());
-  for (int i = 0; i < current_size; ++i) {
-    if (this->Is(unioned->Get(i))) return true;
+bool TypeImpl<Config>::UnionType::Wellformed() {
+  ASSERT(this->Length() >= 2);

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

This function always returns true, so the return type should be changed to void
or the ASSERTs should be changed to return false.

+  for (int i = 0; i < this->Length(); ++i) {
+    ASSERT(!this->Get(i)->IsUnion());
+    if (i > 0) ASSERT(!this->Get(i)->IsBitset());
+    for (int j = 0; j < this->Length(); ++j) {
+      if (i != j) ASSERT(!this->Get(i)->Is(this->Get(j)));
+    }
   }
-  return false;
+  return true;
 }
 
 
-// Get non-bitsets from this which are not subsumed by union, store at result,
-// starting at index. Returns updated index.
+template<class Config>
+typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Narrow(
+    int bitset, Region* region) {
+  TypeHandle bound = BitsetType::New(bitset, region);
+  if (this->IsClass()) {
+    return ClassType::New(this->AsClass()->Map(), bound, region);
+  } else if (this->IsConstant()) {
+    return ConstantType::New(this->AsConstant()->Value(), bound, region);
+  } else if (this->IsArray()) {
+    return ArrayType::New(this->AsArray()->Element(), bound, region);
+  } else if (this->IsFunction()) {
+    FunctionType* function = this->AsFunction();
+    int arity = function->Arity();
+    FunctionHandle type = FunctionType::New(
+        function->Result(), function->Receiver(), bound, arity, region);
+    for (int i = 0; i < arity; ++i) {
+      type->InitParameter(i, function->Parameter(i));
+    }
+    return type;
+  }
+  UNREACHABLE();
+  return TypeHandle();
+}
+
+
+template<class Config>
+int TypeImpl<Config>::BoundBy(TypeImpl* that) {
+  ASSERT(!this->IsUnion());
+  if (that->IsBitset()) {
+    return that->AsBitset() & this->InherentBitsetLub();
+  } else if (that->IsUnion()) {
+    UnionType* unioned = that->AsUnion();
+    int length = unioned->Length();
+    int bitset = BitsetType::kNone;
+    for (int i = 0; i < length; ++i) {
+      bitset |= BoundBy(unioned->Get(i)->unhandle());
+    }
+    return bitset;
+  } else if (that->IsClass() && this->IsClass() &&
+      *this->AsClass()->Map() == *that->AsClass()->Map()) {
+    return that->BitsetLub();
+  } else if (that->IsConstant() && this->IsConstant() &&
+      *this->AsConstant()->Value() == *that->AsConstant()->Value()) {
+    return that->AsConstant()->Bound()->AsBitset();
+  } else if (that->IsArray() && this->IsArray() && this->Is(that)) {
+    return that->AsArray()->Bound()->AsBitset();
+  } else if (that->IsFunction() && this->IsFunction() && this->Is(that)) {
+    return that->AsFunction()->Bound()->AsBitset();
+  }
+  return BitsetType::kNone;
+}
+
+
+template<class Config>
+int TypeImpl<Config>::IndexInUnion(
+    int bound, UnionHandle unioned, int current_size) {
+  ASSERT(!this->IsUnion());
+  for (int i = 0; i < current_size; ++i) {
+    TypeHandle that = unioned->Get(i);
+    if (that->IsBitset()) {
+      if ((bound | that->AsBitset()) == that->AsBitset()) return i;
+    } else if (that->IsClass() && this->IsClass()) {
+      if (*this->AsClass()->Map() == *that->AsClass()->Map()) return i;
+    } else if (that->IsConstant() && this->IsConstant()) {
+      if (*this->AsConstant()->Value() == *that->AsConstant()->Value())
+        return i;
+    } else if (that->IsArray() && this->IsArray()) {
+      if (this->Is(that)) return i;
+    } else if (that->IsFunction() && this->IsFunction()) {
+      if (this->Is(that)) return i;
+    }
+  }
+  return -1;
+}
+
+
+// Get non-bitsets from type, bounded by upper.
+// Store at result starting at index. Returns updated index.
 template<class Config>
 int TypeImpl<Config>::ExtendUnion(
-    UnionHandle result, TypeHandle type, int current_size) {
-  int old_size = current_size;
+    UnionHandle result, int size, TypeHandle type,
+    TypeHandle other, bool is_intersect, Region* region) {
+  int old_size = size;
   if (type->IsUnion()) {
     UnionHandle unioned = handle(type->AsUnion());
     for (int i = 0; i < unioned->Length(); ++i) {
-      TypeHandle type = unioned->Get(i);
-      ASSERT(i == 0 || !(type->IsBitset() || type->Is(unioned->Get(0))));
-      if (!type->IsBitset() && !type->InUnion(result, old_size)) {
-        result->Set(current_size++, type);
+      TypeHandle type_i = unioned->Get(i);
+      ASSERT(i == 0 || !(type_i->IsBitset() || type_i->Is(unioned->Get(0))));
+      if (!type_i->IsBitset()) {
+        size = ExtendUnion(result, size, type_i, other, is_intersect, region);
       }
     }
   } else if (!type->IsBitset()) {
-    // For all structural types, subtyping implies equivalence.
     ASSERT(type->IsClass() || type->IsConstant() ||
            type->IsArray() || type->IsFunction());
-    if (!type->InUnion(result, old_size)) {
-      result->Set(current_size++, type);
+    int old_bound = type->BitsetLub();
+    int other_bound = type->BoundBy(other->unhandle());
+    int new_bound =
+        is_intersect ? (old_bound & other_bound) : (old_bound | other_bound);
+    if (new_bound != BitsetType::kNone) {
+      int i = type->IndexInUnion(new_bound, result, old_size);
+      if (i == -1) {
+        i = size++;
+      } else if (result->Get(i)->IsBitset()) {
+        return size;  // Already fully subsumed.
+      } else {
+        int type_i_bound = result->Get(i)->BitsetLub();
+        new_bound |= type_i_bound;
+        if (new_bound == type_i_bound) return size;
+      }
+      if (new_bound != old_bound) type = type->Narrow(new_bound, region);
+      result->Set(i, type);
     }
   }
-  return current_size;
+  return size;
 }
 
 
-// Union is O(1) on simple bit unions, but O(n*m) on structured unions.
+// Union is O(1) on simple bitsets, but O(n*m) on structured unions.
 template<class Config>
 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
     TypeHandle type1, TypeHandle type2, Region* region) {
   // Fast case: bit sets.
   if (type1->IsBitset() && type2->IsBitset()) {
     return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
   }
 
   // Fast case: top or bottom types.
   if (type1->IsAny() || type2->IsNone()) return type1;
@@ skipping 15 matching lines @@
   }
   int bitset = type1->BitsetGlb() | type2->BitsetGlb();
   if (bitset != BitsetType::kNone) ++size;
   ASSERT(size >= 1);
 
   UnionHandle unioned = UnionType::New(size, region);
   size = 0;
   if (bitset != BitsetType::kNone) {
     unioned->Set(size++, BitsetType::New(bitset, region));
   }
-  size = ExtendUnion(unioned, type1, size);
-  size = ExtendUnion(unioned, type2, size);
+
+  size = ExtendUnion(unioned, size, type1, type2, false, region);
+  size = ExtendUnion(unioned, size, type2, type1, false, region);
 
   if (size == 1) {
     return unioned->Get(0);
   } else {
     unioned->Shrink(size);
+    ASSERT(unioned->Wellformed());
     return unioned;
   }
 }
 
 
-// Get non-bitsets from type which are also in other, store at result,
-// starting at index. Returns updated index.
-template<class Config>
-int TypeImpl<Config>::ExtendIntersection(
-    UnionHandle result, TypeHandle type, TypeHandle other, int current_size) {
-  int old_size = current_size;
-  if (type->IsUnion()) {
-    UnionHandle unioned = handle(type->AsUnion());
-    for (int i = 0; i < unioned->Length(); ++i) {
-      TypeHandle type = unioned->Get(i);
-      ASSERT(i == 0 || !(type->IsBitset() || type->Is(unioned->Get(0))));
-      if (!type->IsBitset() && type->Is(other) &&
-          !type->InUnion(result, old_size)) {
-        result->Set(current_size++, type);
-      }
-    }
-  } else if (!type->IsBitset()) {
-    // For all structural types, subtyping implies equivalence.
-    ASSERT(type->IsClass() || type->IsConstant() ||
-           type->IsArray() || type->IsFunction());
-    if (type->Is(other) && !type->InUnion(result, old_size)) {
-      result->Set(current_size++, type);
-    }
-  }
-  return current_size;
-}
-
-
-// Intersection is O(1) on simple bit unions, but O(n*m) on structured unions.
+// Intersection is O(1) on simple bitsets, but O(n*m) on structured unions.
 template<class Config>
 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
     TypeHandle type1, TypeHandle type2, Region* region) {
   // Fast case: bit sets.
   if (type1->IsBitset() && type2->IsBitset()) {
     return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region);
   }
 
   // Fast case: top or bottom types.
   if (type1->IsNone() || type2->IsAny()) return type1;
@@ skipping 15 matching lines @@
   }
   int bitset = type1->BitsetGlb() & type2->BitsetGlb();
   if (bitset != BitsetType::kNone) ++size;
   ASSERT(size >= 1);
 
   UnionHandle unioned = UnionType::New(size, region);
   size = 0;
   if (bitset != BitsetType::kNone) {
     unioned->Set(size++, BitsetType::New(bitset, region));
   }
-  size = ExtendIntersection(unioned, type1, type2, size);
-  size = ExtendIntersection(unioned, type2, type1, size);
+  size = ExtendUnion(unioned, size, type1, type2, true, region);
+  size = ExtendUnion(unioned, size, type2, type1, true, region);
 
   if (size == 0) {
     return None(region);
   } else if (size == 1) {
     return unioned->Get(0);
   } else {
     unioned->Shrink(size);
+    ASSERT(unioned->Wellformed());
     return unioned;
   }
 }
 
 
 template<class Config>
 template<class OtherType>
 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
     typename OtherType::TypeHandle type, Region* region) {
   if (type->IsBitset()) {
     return BitsetType::New(type->AsBitset(), region);
   } else if (type->IsClass()) {
-    return ClassType::New(type->AsClass()->Map(), region);
+    return ClassType::New(
+        type->AsClass()->Map(),
+        BitsetType::New(type->BitsetLub(), region), region);
   } else if (type->IsConstant()) {
-    return ConstantType::New(type->AsConstant()->Value(), region);
+    return ConstantType::New(
+        type->AsConstant()->Value(),
+        Convert<OtherType>(type->AsConstant()->Bound(), region), region);
   } else if (type->IsUnion()) {
     int length = type->AsUnion()->Length();
     UnionHandle unioned = UnionType::New(length, region);
     for (int i = 0; i < length; ++i) {
       unioned->Set(i, Convert<OtherType>(type->AsUnion()->Get(i), region));
     }
     return unioned;
   } else if (type->IsArray()) {
     return ArrayType::New(
-        Convert<OtherType>(type->AsArray()->Element(), region), region);
+        Convert<OtherType>(type->AsArray()->Element(), region),
+        Convert<OtherType>(type->AsArray()->Bound(), region), region);
   } else if (type->IsFunction()) {
     FunctionHandle function = FunctionType::New(
         Convert<OtherType>(type->AsFunction()->Result(), region),
         Convert<OtherType>(type->AsFunction()->Receiver(), region),
+        Convert<OtherType>(type->AsFunction()->Bound(), region),
         type->AsFunction()->Arity(), region);
     for (int i = 0; i < function->Arity(); ++i) {
       function->InitParameter(i,
           Convert<OtherType>(type->AsFunction()->Parameter(i), region));
     }
     return function;
   } else {
     UNREACHABLE();
     return None(region);
   }
@@ skipping 140 matching lines @@
 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>;
 
 template TypeImpl<ZoneTypeConfig>::TypeHandle
   TypeImpl<ZoneTypeConfig>::Convert<HeapType>(
     TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*);
 template TypeImpl<HeapTypeConfig>::TypeHandle
   TypeImpl<HeapTypeConfig>::Convert<Type>(
     TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*);
 
 } }  // namespace v8::internal