Establish distributivity for type union & intersection

src/types.cc

Index: src/types.cc
diff --git a/src/types.cc b/src/types.cc
index 394f7726791b8cd81a9c8ae17a838d6cc47703e3..788ae0fb41eb57a09806da2fb86d6a13e979456d 100644
--- a/src/types.cc
+++ b/src/types.cc
@@ -117,9 +117,25 @@ int TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
   if (type->IsBitset()) {
     return type->AsBitset();
   } else if (type->IsUnion()) {
-    // All but the first are non-bitsets and thus would yield kNone anyway.
-    return type->AsUnion()->Get(0)->BitsetGlb();
+    UnionHandle unioned = handle(type->AsUnion());
+    int bitset = kNone;
+    for (int i = 0; i < unioned->Length(); ++i) {
+      bitset |= unioned->Get(i)->BitsetGlb();
+    }
+    return bitset;
+  } else if (type->IsClass()) {
+    // Little hack to avoid the need for a region for handlification here...
+    return REPRESENTATION(Config::is_class(type)
+        ? Lub(*Config::as_class(type))
+        : type->AsClass()->Bound(NULL)->AsBitset());
+  } else if (type->IsConstant()) {
+    return REPRESENTATION(type->AsConstant()->Bound()->AsBitset());
+  } else if (type->IsArray()) {
+    return REPRESENTATION(type->AsArray()->Bound()->AsBitset());
+  } else if (type->IsFunction()) {
+    return REPRESENTATION(type->AsFunction()->Bound()->AsBitset());
   } else {
+    UNREACHABLE();
     return kNone;
   }
 }
@@ -139,11 +155,39 @@ int TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
     }
     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()) {
@@ -284,14 +328,23 @@ bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
   if (that->IsBitset()) {
     return (BitsetType::Lub(this) | that->AsBitset()) == that->AsBitset();
   }
+  if (this->IsBitset() && SEMANTIC(this->AsBitset()) == BitsetType::kNone) {
+    // Bitsets only have non-bitset supertypes along the representation axis.
+    int that_bitset = that->BitsetGlb();
+    return (this->AsBitset() | that_bitset) == that_bitset;
+  }
 
   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()
@@ -424,7 +477,6 @@ bool TypeImpl<Config>::Maybe(TypeImpl* that) {
 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;
   }
@@ -433,43 +485,157 @@ bool TypeImpl<Config>::Contains(i::Object* value) {
 
 
 template<class Config>
-bool TypeImpl<Config>::InUnion(UnionHandle unioned, int current_size) {
+bool TypeImpl<Config>::UnionType::Wellformed() {
+  ASSERT(this->Length() >= 2);
+  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 true;
+}
+
+
+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->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 that->BitsetGlb();
+}
+
+
+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) {
-    if (this->Is(unioned->Get(i))) return true;
+    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 false;
+  return -1;
 }
 
 
-// Get non-bitsets from this which are not subsumed by union, store at result,
-// starting at index. Returns updated index.
+// 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 inherent_bound = type->InherentBitsetLub();
+    int old_bound = type->BitsetLub();
+    int other_bound = type->BoundBy(other->unhandle()) & inherent_bound;
+    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.
+// If bitset is subsumed by another entry in the result, remove it.
+// (Only bitsets with empty semantic axis can be subtypes of non-bitsets.)
+template<class Config>
+int TypeImpl<Config>::NormalizeUnion(UnionHandle result, int size, int bitset) {
+  if (bitset != BitsetType::kNone && SEMANTIC(bitset) == BitsetType::kNone) {
+    for (int i = 1; i < size; ++i) {
+      int glb = result->Get(i)->BitsetGlb();
+      if ((bitset | glb) == glb) {
+        for (int j = 1; j < size; ++j) {
+          result->Set(j - 1, result->Get(j));
+        }
+        --size;
+        break;
+      }
+    }
+  }
+  return size;
+}
+
+
+// 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) {
@@ -505,47 +671,21 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
   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);
+  size = NormalizeUnion(unioned, size, bitset);
 
   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) {
@@ -581,8 +721,9 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
   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);
+  size = NormalizeUnion(unioned, size, bitset);
 
   if (size == 0) {
     return None(region);
@@ -590,6 +731,7 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
     return unioned->Get(0);
   } else {
     unioned->Shrink(size);
+    ASSERT(unioned->Wellformed());
     return unioned;
   }
 }
@@ -602,9 +744,13 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
   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);
@@ -614,11 +760,13 @@ typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
     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,
@@ -708,57 +856,55 @@ void TypeImpl<Config>::BitsetType::BitsetTypePrint(FILE* out, int bitset) {
 template<class Config>
 void TypeImpl<Config>::TypePrint(FILE* out, PrintDimension dim) {
   DisallowHeapAllocation no_allocation;
-  if (this->IsBitset()) {
-    int bitset = this->AsBitset();
-    switch (dim) {
-      case BOTH_DIMS:
-        BitsetType::BitsetTypePrint(out, bitset & BitsetType::kSemantic);
-        PrintF(out, "/");
-        BitsetType::BitsetTypePrint(out, bitset & BitsetType::kRepresentation);
-        break;
-      case SEMANTIC_DIM:
-        BitsetType::BitsetTypePrint(out, bitset & BitsetType::kSemantic);
-        break;
-      case REPRESENTATION_DIM:
-        BitsetType::BitsetTypePrint(out, bitset & BitsetType::kRepresentation);
-        break;
-    }
-  } else if (this->IsConstant()) {
-    PrintF(out, "Constant(%p : ",
-        static_cast<void*>(*this->AsConstant()->Value()));
-    BitsetType::New(BitsetType::Lub(this))->TypePrint(out, dim);
-    PrintF(out, ")");
-  } else if (this->IsClass()) {
-    PrintF(out, "Class(%p < ", static_cast<void*>(*this->AsClass()->Map()));
-    BitsetType::New(BitsetType::Lub(this))->TypePrint(out, dim);
-    PrintF(out, ")");
-  } else if (this->IsUnion()) {
-    PrintF(out, "(");
-    UnionHandle unioned = handle(this->AsUnion());
-    for (int i = 0; i < unioned->Length(); ++i) {
-      TypeHandle type_i = unioned->Get(i);
-      if (i > 0) PrintF(out, " | ");
-      type_i->TypePrint(out, dim);
-    }
-    PrintF(out, ")");
-  } else if (this->IsArray()) {
-    PrintF(out, "[");
-    AsArray()->Element()->TypePrint(out, dim);
-    PrintF(out, "]");
-  } else if (this->IsFunction()) {
-    if (!this->AsFunction()->Receiver()->IsAny()) {
-      this->AsFunction()->Receiver()->TypePrint(out, dim);
-      PrintF(out, ".");
-    }
-    PrintF(out, "(");
-    for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
-      if (i > 0) PrintF(out, ", ");
-      this->AsFunction()->Parameter(i)->TypePrint(out, dim);
+  if (dim != REPRESENTATION_DIM) {
+    if (this->IsBitset()) {
+      BitsetType::BitsetTypePrint(out, SEMANTIC(this->AsBitset()));
+    } else if (this->IsConstant()) {
+      PrintF(out, "Constant(%p : ",
+             static_cast<void*>(*this->AsConstant()->Value()));
+      BitsetType::New(BitsetType::Lub(this))->TypePrint(out, dim);
+      PrintF(out, ")");
+      return;
+    } else if (this->IsClass()) {
+      PrintF(out, "Class(%p < ", static_cast<void*>(*this->AsClass()->Map()));
+      BitsetType::New(BitsetType::Lub(this))->TypePrint(out, dim);
+      PrintF(out, ")");
+      return;
+    } else if (this->IsUnion()) {
+      PrintF(out, "(");
+      UnionHandle unioned = handle(this->AsUnion());
+      for (int i = 0; i < unioned->Length(); ++i) {
+        TypeHandle type_i = unioned->Get(i);
+        if (i > 0) PrintF(out, " | ");
+        type_i->TypePrint(out, dim);
+      }
+      PrintF(out, ")");
+      return;
+    } else if (this->IsArray()) {
+      PrintF(out, "Array(");
+      AsArray()->Element()->TypePrint(out, dim);
+      PrintF(out, ")");
+    } else if (this->IsFunction()) {
+      if (!this->AsFunction()->Receiver()->IsAny()) {
+        this->AsFunction()->Receiver()->TypePrint(out, dim);
+        PrintF(out, ".");
+      }
+      PrintF(out, "(");
+      for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
+        if (i > 0) PrintF(out, ", ");
+        this->AsFunction()->Parameter(i)->TypePrint(out, dim);
+      }
+      PrintF(out, ")->");
+      this->AsFunction()->Result()->TypePrint(out, dim);
+    } else {
+      UNREACHABLE();
     }
-    PrintF(out, ")->");
-    this->AsFunction()->Result()->TypePrint(out, dim);
-  } else {
-    UNREACHABLE();
+  }
+  if (dim == BOTH_DIMS) {
+    PrintF(out, "/");
+  }
+  if (dim != SEMANTIC_DIM) {
+    BitsetType::BitsetTypePrint(out, REPRESENTATION(this->BitsetLub()));
   }
 }