Redesign of the internal type system.

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 "src/types.h"
 
 #include "src/ostreams.h"
 #include "src/types-inl.h"
 
 namespace v8 {
 namespace internal {
 
 
 // -----------------------------------------------------------------------------
-// Range-related custom order on doubles.
-// We want -0 to be less than +0.
+// Range-related helper functions.
 
-static bool dle(double x, double y) {
-  return x <= y && (x != 0 || IsMinusZero(x) || !IsMinusZero(y));
+template<class Config>
+typename TypeImpl<Config>::Limits TypeImpl<Config>::intersect(
+    Limits lhs, Limits rhs) {
+  DisallowHeapAllocation no_allocation;

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

Can't this function be simplified to

  return Limit(std::max(lhs.min, rhs.min), std::min(lhs.max, rhs.max))

? And likewise union.

Maybe add a comment here that this intentionally allows for min>max.

[neis1, 2014/09/16 10:04:00]

No, that would compare the objects instead of the contained numbers.
Done.

+  Limits result(lhs);
+  if (lhs.min->Number() < rhs.min->Number()) result.min = rhs.min;
+  if (lhs.max->Number() > rhs.max->Number()) result.max = rhs.max;
+  return result;
 }
 
 
-static bool deq(double x, double y) {
-  return dle(x, y) && dle(y, x);
+template<class Config>
+typename TypeImpl<Config>::Limits TypeImpl<Config>::union_(
+    Limits lhs, Limits rhs) {
+  DisallowHeapAllocation no_allocation;
+  Limits result(lhs);
+  if (lhs.min->Number() > rhs.min->Number()) result.min = rhs.min;
+  if (lhs.max->Number() < rhs.max->Number()) result.max = rhs.max;
+  return result;
+}
+
+
+template<class Config>
+bool TypeImpl<Config>::overlap(
+    typename TypeImpl<Config>::RangeType* lhs,
+    typename TypeImpl<Config>::RangeType* rhs) {
+  DisallowHeapAllocation no_allocation;
+  typename TypeImpl<Config>::Limits lim = intersect(Limits(lhs), Limits(rhs));
+  return lim.min->Number() <= lim.max->Number();
+}
+
+
+template<class Config>
+bool TypeImpl<Config>::contains(
+    typename TypeImpl<Config>::RangeType* lhs,
+    typename TypeImpl<Config>::RangeType* rhs) {
+  DisallowHeapAllocation no_allocation;
+  return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
+}
+
+
+template<class Config>
+bool TypeImpl<Config>::contains(
+    typename TypeImpl<Config>::RangeType* range, i::Object* val) {
+  DisallowHeapAllocation no_allocation;
+  return IsInteger(val)
+      && range->Min() <= val->Number() && val->Number() <= range->Max();
 }
 
 
 // -----------------------------------------------------------------------------
 // Glb and lub computation.
 
+
 // The largest bitset subsumed by this type.
 template<class Config>
 int TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
   DisallowHeapAllocation no_allocation;
   if (type->IsBitset()) {
     return type->AsBitset();
   } else if (type->IsUnion()) {
     UnionHandle unioned = handle(type->AsUnion());
-    DCHECK(unioned->Wellformed());
-    return unioned->Get(0)->BitsetGlb();  // Other BitsetGlb's are kNone anyway.
+    SLOW_DCHECK(unioned->Wellformed());
+    return unioned->Get(0)->BitsetGlb();  // Shortcut.

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

I don't think this comment got clearer ;)

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

Done.

   } else {
     return kNone;
   }
 }
 
 
 // The smallest bitset subsuming this type.
 template<class Config>
 int TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
   DisallowHeapAllocation no_allocation;
-  if (type->IsBitset()) {
-    return type->AsBitset();
-  } else if (type->IsUnion()) {
-    UnionHandle unioned = handle(type->AsUnion());
+  if (type->IsBitset()) return type->AsBitset();
+  if (type->IsUnion()) {
     int bitset = kNone;
-    for (int i = 0; i < unioned->Length(); ++i) {
-      bitset |= unioned->Get(i)->BitsetLub();
+    for (int i = 0; i < type->AsUnion()->Length(); ++i) {
+      bitset |= type->AsUnion()->Get(i)->BitsetLub();
     }
     return bitset;
-  } else if (type->IsClass()) {
-    // 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()) {
-    return type->AsConstant()->Bound()->AsBitset();
-  } else if (type->IsRange()) {
-    return type->AsRange()->Bound()->AsBitset();
-  } else if (type->IsContext()) {
-    return type->AsContext()->Bound()->AsBitset();
-  } else if (type->IsArray()) {
-    return type->AsArray()->Bound()->AsBitset();
-  } else if (type->IsFunction()) {
-    return type->AsFunction()->Bound()->AsBitset();
-  } else {
-    UNREACHABLE();
-    return kNone;
   }
+  if (type->IsClass()) return Lub(*type->AsClass()->Map());
+  if (type->IsConstant()) return Lub(*type->AsConstant()->Value());
+  if (type->IsRange()) return Lub(Limits(type->AsRange()));
+  if (type->IsContext()) return kInternal & kTaggedPtr;
+  if (type->IsArray()) return kArray;
+  if (type->IsFunction()) return kFunction;
+  UNREACHABLE();
+  return kNone;
 }
 
 
-// The smallest bitset subsuming this type, ignoring explicit 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->IsRange()) {
-    return Lub(type->AsRange()->Min(), type->AsRange()->Max());
-  } else if (type->IsContext()) {
-    return kInternal & kTaggedPtr;
-  } else if (type->IsArray()) {
-    return kArray;
-  } else if (type->IsFunction()) {
-    return kFunction;
-  } else {
-    UNREACHABLE();
-    return kNone;
-  }
-}
-
-
-template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
-  DisallowHeapAllocation no_allocation;
-  if (value->IsNumber()) {
-    return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr);
-  }
-  return Lub(i::HeapObject::cast(value)->map());
-}
-
-
-template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(double value) {
-  DisallowHeapAllocation no_allocation;
-  if (i::IsMinusZero(value)) return kMinusZero;
-  if (std::isnan(value)) return kNaN;
-  if (IsUint32Double(value)) return Lub(FastD2UI(value));
-  if (IsInt32Double(value)) return Lub(FastD2I(value));
-  return kOtherNumber;
-}
-
-
-template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(double min, double max) {
-  DisallowHeapAllocation no_allocation;
-  DCHECK(dle(min, max));
-  if (deq(min, max)) return BitsetType::Lub(min);  // Singleton range.
-  int bitset = BitsetType::kNumber ^ SEMANTIC(BitsetType::kNaN);
-  if (dle(0, min) || max < 0) bitset ^= SEMANTIC(BitsetType::kMinusZero);
-  return bitset;
-  // TODO(neis): Could refine this further by doing more checks on min/max.
-}
-
-
-template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(int32_t value) {
-  if (value >= 0x40000000) {
-    return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
-  }
-  if (value >= 0) return kUnsignedSmall;
-  if (value >= -0x40000000) return kOtherSignedSmall;
-  return i::SmiValuesAre31Bits() ? kOtherSigned32 : kOtherSignedSmall;
-}
-
-
-template<class Config>
-int TypeImpl<Config>::BitsetType::Lub(uint32_t value) {
-  DisallowHeapAllocation no_allocation;
-  if (value >= 0x80000000u) return kOtherUnsigned32;
-  if (value >= 0x40000000u) {
-    return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
-  }
-  return kUnsignedSmall;
-}
-
-
 template<class Config>
 int TypeImpl<Config>::BitsetType::Lub(i::Map* map) {
   DisallowHeapAllocation no_allocation;
   switch (map->instance_type()) {
     case STRING_TYPE:
     case ONE_BYTE_STRING_TYPE:
     case CONS_STRING_TYPE:
     case CONS_ONE_BYTE_STRING_TYPE:
     case SLICED_STRING_TYPE:
     case SLICED_ONE_BYTE_STRING_TYPE:
     case EXTERNAL_STRING_TYPE:
     case EXTERNAL_ONE_BYTE_STRING_TYPE:
     case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
     case SHORT_EXTERNAL_STRING_TYPE:
     case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE:
     case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
+      return kOtherString;
     case INTERNALIZED_STRING_TYPE:
     case ONE_BYTE_INTERNALIZED_STRING_TYPE:
     case EXTERNAL_INTERNALIZED_STRING_TYPE:
     case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
     case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
     case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
     case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
     case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
-      return kString;
+      return kInternalizedString;
     case SYMBOL_TYPE:
       return kSymbol;
     case ODDBALL_TYPE: {
       Heap* heap = map->GetHeap();
       if (map == heap->undefined_map()) return kUndefined;
       if (map == heap->null_map()) return kNull;
       if (map == heap->boolean_map()) return kBoolean;
       DCHECK(map == heap->the_hole_map() ||
              map == heap->uninitialized_map() ||
              map == heap->no_interceptor_result_sentinel_map() ||
@@ skipping 51 matching lines @@
     case FOREIGN_TYPE:
     case CODE_TYPE:
       return kInternal & kTaggedPtr;
     default:
       UNREACHABLE();
       return kNone;
   }
 }
 
 
+template<class Config>
+int TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
+  DisallowHeapAllocation no_allocation;
+  if (value->IsNumber()) {
+    return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr);
+  }
+  return Lub(i::HeapObject::cast(value)->map());
+}
+
+
+template<class Config>
+int TypeImpl<Config>::BitsetType::Lub(double value) {
+  DisallowHeapAllocation no_allocation;
+  if (i::IsMinusZero(value)) return kMinusZero;
+  if (std::isnan(value)) return kNaN;
+  if (IsUint32Double(value)) return Lub(FastD2UI(value));
+  if (IsInt32Double(value)) return Lub(FastD2I(value));
+  return kOtherNumber;
+}
+
+
+template<class Config>
+int TypeImpl<Config>::BitsetType::Lub(int32_t value) {
+  DisallowHeapAllocation no_allocation;
+  if (value >= 0x40000000) {
+    return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
+  }
+  if (value >= 0) return kUnsignedSmall;
+  if (value >= -0x40000000) return kOtherSignedSmall;
+  return i::SmiValuesAre31Bits() ? kOtherSigned32 : kOtherSignedSmall;
+}
+
+
+template<class Config>
+int TypeImpl<Config>::BitsetType::Lub(uint32_t value) {
+  DisallowHeapAllocation no_allocation;
+  if (value >= 0x80000000u) return kOtherUnsigned32;
+  if (value >= 0x40000000u) {
+    return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
+  }
+  return kUnsignedSmall;
+}
+
+
+template<class Config>
+int TypeImpl<Config>::BitsetType::Lub(Limits lim) {
+  DisallowHeapAllocation no_allocation;
+  double min = lim.min->Number();
+  double max = lim.max->Number();
+  int lub = kNone;
+
+  int atoms31[] =  {

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

Can we zip these arrays into two tables over a struct{ bitset type; double min;
}? That would make it more readable.

[neis1, 2014/09/16 10:04:00]

Yes, something like that.  I also need to pull the data out again, because I
need some functionality for the typer that relies on that data.  I will also try
to rewrite Lub(double) to make use of it.

+      kOtherNumber, kOtherSigned32, kOtherSignedSmall, kUnsignedSmall,
+      kOtherUnsigned31, kOtherUnsigned32, kOtherNumber
+  };
+  double mins31[] =  {
+      -V8_INFINITY, kMinInt, -0x40000000, 0,
+      0x40000000u, 0x80000000u, static_cast<double>(kMaxUInt32) + 1
+  };
+  int atoms32[] =  {
+      kOtherNumber, kOtherSignedSmall, kUnsignedSmall,
+      kOtherUnsigned32, kOtherNumber
+  };
+  double mins32[] =  {
+      -V8_INFINITY, kMinInt, 0,
+      0x80000000u, static_cast<double>(kMaxUInt32) + 1
+  };
+  int* atoms = i::SmiValuesAre31Bits() ? atoms31 : atoms32;
+  double* mins = i::SmiValuesAre31Bits() ? mins31 : mins32;
+  size_t n = i::SmiValuesAre31Bits() ? arraysize(atoms31) : arraysize(atoms32);
+
+  for (size_t i = 1; i < n; ++i) {
+    if (min < mins[i]) {
+      lub |= atoms[i-1];
+      if (max < mins[i]) return lub;
+    }
+  }
+  return lub |= atoms[n-1];
+}
+
+
 // -----------------------------------------------------------------------------
 // Predicates.
 
-// Check this <= that.
+
+template<class Config>
+bool TypeImpl<Config>::SimplyEquals(TypeImpl* that) {
+  DisallowHeapAllocation no_allocation;
+  if (this->IsClass()) {
+    return that->IsClass()
+        && *this->AsClass()->Map() == *that->AsClass()->Map();
+  }
+  if (this->IsConstant()) {
+    return that->IsConstant()
+        && *this->AsConstant()->Value() == *that->AsConstant()->Value();
+  }
+  if (this->IsContext()) {
+    return that->IsContext()
+        && this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
+  }
+  if (this->IsArray()) {
+    return that->IsArray()
+        && this->AsArray()->Element()->Equals(that->AsArray()->Element());
+  }
+  if (this->IsFunction()) {
+    if (!that->IsFunction()) return false;
+    FunctionType* this_fun = this->AsFunction();
+    FunctionType* that_fun = that->AsFunction();
+    if (this_fun->Arity() != that_fun->Arity() ||
+        !this_fun->Result()->Equals(that_fun->Result()) ||
+        !this_fun->Receiver()->Equals(that_fun->Receiver())) {
+      return false;
+    }
+    for (int i = 0; i < this_fun->Arity(); ++i) {
+      if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
+    }
+    return true;
+  }
+  UNREACHABLE();
+  return false;
+}
+
+
+// Check if [this] <= [that].
 template<class Config>
 bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
   DisallowHeapAllocation no_allocation;
 
-  // Fast path for bitsets.
-  if (this->IsNone()) return true;
   if (that->IsBitset()) {
-    return BitsetType::Is(BitsetType::Lub(this), that->AsBitset());
+    return BitsetType::Is(this->BitsetLub(), that->AsBitset());
+  }
+  if (this->IsBitset()) {
+    return BitsetType::Is(this->AsBitset(), that->BitsetGlb());
   }
 
-  if (that->IsClass()) {
-    return this->IsClass()
-        && *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()->Bound()->Is(that->AsConstant()->Bound());
-  }
-  if (that->IsRange()) {
-    return this->IsRange()
-        && this->AsRange()->Bound()->Is(that->AsRange()->Bound())
-        && dle(that->AsRange()->Min(), this->AsRange()->Min())
-        && dle(this->AsRange()->Max(), that->AsRange()->Max());
-  }
-  if (that->IsContext()) {
-    return this->IsContext()
-        && this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
-  }
-  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();
-    FunctionType* that_fun = that->AsFunction();
-    if (this_fun->Arity() != that_fun->Arity() ||
-        !this_fun->Result()->Equals(that_fun->Result()) ||
-        !that_fun->Receiver()->Equals(this_fun->Receiver())) {
-      return false;
-    }
-    for (int i = 0; i < this_fun->Arity(); ++i) {
-      if (!that_fun->Parameter(i)->Equals(this_fun->Parameter(i))) return false;
-    }
-    return true;
-  }
-
-  // (T1 \/ ... \/ Tn) <= T  <=>  (T1 <= T) /\ ... /\ (Tn <= T)
+  // (T1 \/ ... \/ Tn) <= T  if  (T1 <= T) /\ ... /\ (Tn <= T)
   if (this->IsUnion()) {
     UnionHandle unioned = handle(this->AsUnion());
     for (int i = 0; i < unioned->Length(); ++i) {
       if (!unioned->Get(i)->Is(that)) return false;
     }
     return true;
   }
 
-  // T <= (T1 \/ ... \/ Tn)  <=>  (T <= T1) \/ ... \/ (T <= Tn)
-  // (iff T is not a union)
-  DCHECK(!this->IsUnion() && that->IsUnion());
-  UnionHandle unioned = handle(that->AsUnion());
-  for (int i = 0; i < unioned->Length(); ++i) {
-    if (this->Is(unioned->Get(i))) return true;
-    if (this->IsBitset()) break;  // Fast fail, only first field is a bitset.
+  // T <= (T1 \/ ... \/ Tn)  if  (T <= T1) \/ ... \/ (T <= Tn)
+  if (that->IsUnion()) {
+    UnionHandle unioned = handle(that->AsUnion());
+    for (int i = 0; i < unioned->Length(); ++i) {
+      if (this->Is(unioned->Get(i))) return true;
+      if (i > 1 && this->IsRange()) return false;  // Shortcut.
+    }
+    return false;
   }
-  return false;
+
+  if (this->IsRange()) {

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

Do the that->IsRange() test first, to avoid the duplication.

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

Not sure what exactly you had in mind, but I rewrote it.

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

That's what I had in mind. :)

+    return that->IsRange() && contains(that->AsRange(), this->AsRange());
+  }
+  if (this->IsConstant() && that->IsRange()) {
+      return contains(that->AsRange(), *this->AsConstant()->Value());
+  }
+  return this->SimplyEquals(that);
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::NowIs(TypeImpl* that) {
   DisallowHeapAllocation no_allocation;
 
   // TODO(rossberg): this is incorrect for
   //   Union(Constant(V), T)->NowIs(Class(M))
   // but fuzzing does not cover that!
   if (this->IsConstant()) {
     i::Object* object = *this->AsConstant()->Value();
     if (object->IsHeapObject()) {
       i::Map* map = i::HeapObject::cast(object)->map();
       for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
         if (*it.Current() == map) return true;
       }
     }
   }
   return this->Is(that);
 }
 
 
-// Check if this contains only (currently) stable classes.
+// Check if [this] contains only (currently) stable classes.
 template<class Config>
 bool TypeImpl<Config>::NowStable() {
   DisallowHeapAllocation no_allocation;
   for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) {
     if (!it.Current()->is_stable()) return false;
   }
   return true;
 }
 
 
-// Check this overlaps that.
+// Check if [this] and [that] overlap.
 template<class Config>
 bool TypeImpl<Config>::Maybe(TypeImpl* that) {
   DisallowHeapAllocation no_allocation;
 
-  // (T1 \/ ... \/ Tn) overlaps T <=> (T1 overlaps T) \/ ... \/ (Tn overlaps T)
+  // (T1 \/ ... \/ Tn) overlaps T  if  (T1 overlaps T) \/ ... \/ (Tn overlaps T)
   if (this->IsUnion()) {
     UnionHandle unioned = handle(this->AsUnion());
     for (int i = 0; i < unioned->Length(); ++i) {
       if (unioned->Get(i)->Maybe(that)) return true;
     }
     return false;
   }
 
-  // T overlaps (T1 \/ ... \/ Tn) <=> (T overlaps T1) \/ ... \/ (T overlaps Tn)
+  // T overlaps (T1 \/ ... \/ Tn)  if  (T overlaps T1) \/ ... \/ (T overlaps Tn)
   if (that->IsUnion()) {
-    UnionHandle unioned = handle(that->AsUnion());
-    for (int i = 0; i < unioned->Length(); ++i) {
-      if (this->Maybe(unioned->Get(i))) return true;
+    for (int i = 0; i < that->AsUnion()->Length(); ++i) {
+      if (this->Maybe(that->AsUnion()->Get(i))) return true;
     }
     return false;
   }
 
-  DCHECK(!this->IsUnion() && !that->IsUnion());
-  if (this->IsBitset() || that->IsBitset()) {
-    return BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub());
+  if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))

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

I'm not sure I understand why this is the right thing, given the new asymmetric
definition of IsInhabited.

[neis1, 2014/09/16 10:04:00]

I allow the representation part to be empty, but not the semantic part.  I think
that in order to allow types with empty semantic part as well, we would need to
allow non-trivial subtyping between bitsets and structural types again.  Since I
don't currently see a use for such types, I did it this way, requiring only a
tiny change or two.

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

Hm. The asymmetry is too suspicious for my taste. I don't see how it can be
justified semantically.

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

Marked as TODO.

+    return false;
+  if (this->IsBitset() || that->IsBitset()) return true;
+
+  if (this->IsClass() && !that->IsClass()) return true;
+  if (that->IsClass() && !this->IsClass()) return true;

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

You can combine these two into "if (this->IsClass() != that->IsClass()) ..."

[neis1, 2014/09/16 10:04:00]

Done.

+
+  if (this->IsRange()) {
+    if (that->IsConstant()) {
+      return contains(this->AsRange(), *that->AsConstant()->Value());
+    }
+    return that->IsRange() && overlap(this->AsRange(), that->AsRange());
   }
-  if (this->IsClass()) {
-    return that->IsClass()
-        && *this->AsClass()->Map() == *that->AsClass()->Map();
-  }
-  if (this->IsConstant()) {
-    return that->IsConstant()
-        && *this->AsConstant()->Value() == *that->AsConstant()->Value();
-  }
-  if (this->IsContext()) {
-    return this->Equals(that);
-  }
-  if (this->IsArray()) {
-    // There is no variance!
-    return this->Equals(that);
-  }
-  if (this->IsFunction()) {
-    // There is no variance!
-    return this->Equals(that);
+  if (that->IsRange()) {
+    if (this->IsConstant()) {
+      return contains(that->AsRange(), *this->AsConstant()->Value());
+    }
+    return this->IsRange() && overlap(this->AsRange(), that->AsRange());
   }
 
-  return false;
+  return this->SimplyEquals(that);
 }
 
 
-// Check if value is contained in (inhabits) type.
+// Return the range in [this], or [NULL].
+template<class Config>
+typename TypeImpl<Config>::RangeType* TypeImpl<Config>::GetRange() {
+  DisallowHeapAllocation no_allocation;
+  if (this->IsRange()) return this->AsRange();
+  if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
+    return this->AsUnion()->Get(1)->AsRange();
+  }
+  return NULL;
+}
+
+
 template<class Config>
 bool TypeImpl<Config>::Contains(i::Object* value) {
   DisallowHeapAllocation no_allocation;
-  if (this->IsRange()) {
-    return value->IsNumber() &&
-           dle(this->AsRange()->Min(), value->Number()) &&
-           dle(value->Number(), this->AsRange()->Max()) &&
-           BitsetType::Is(BitsetType::Lub(value), this->BitsetLub());
-  }
   for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
     if (*it.Current() == value) return true;
   }
+  if (IsInteger(value)) {
+    RangeType* range = this->GetRange();
+    if (range != NULL && contains(range, value)) return true;
+  }
   return BitsetType::New(BitsetType::Lub(value))->Is(this);
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::UnionType::Wellformed() {
-  DCHECK(this->Length() >= 2);
+  DisallowHeapAllocation no_allocation;
+  // This checks the invariants of the union representation:
+  // 1. There are at least two elements.
+  // 2. At most one element is a bitset, and it must be the first one.
+  // 3. At most one element is a range, and it must be the second one.

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

Can't you have a range and no bitset?

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

Yes, but in that case you either have another type (which can then take the
bitset's place) or you don't need a union.

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

Right, figured that out later. Maybe say so explicitly, e.g. add "(even if first
one is not a bitset)".

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

Done.

+  // 4. No element is itself a union.
+  // 5. No element is a subtype of any other.
+  DCHECK(this->Length() >= 2);  // (1)
   for (int i = 0; i < this->Length(); ++i) {
-    DCHECK(!this->Get(i)->IsUnion());
-    if (i > 0) DCHECK(!this->Get(i)->IsBitset());
+    if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (2)
+    if (i != 1) DCHECK(!this->Get(i)->IsRange());  // (3)
+    DCHECK(!this->Get(i)->IsUnion());  // (4)
     for (int j = 0; j < this->Length(); ++j) {
-      if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j)));
+      if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j)));  // (5)
     }
   }
   return true;
 }
 
 
 // -----------------------------------------------------------------------------
 // Union and intersection
 
-template<class Config>
-typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Rebound(
-    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->IsRange()) {
-    return RangeType::New(
-        this->AsRange()->Min(), this->AsRange()->Max(), bound, region);
-  } else if (this->IsContext()) {
-    return ContextType::New(this->AsContext()->Outer(), bound, region);
-  } else if (this->IsArray()) {
-    return ArrayType::New(this->AsArray()->Element(), bound, region);
-  } else if (this->IsFunction()) {
-    FunctionHandle function = Config::handle(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();
+
+static bool AddIsSafe(int x, int y) {
+  return x >= 0 ?
+      y <= std::numeric_limits<int>::max() - x :
+      y >= std::numeric_limits<int>::min() - x;
 }
 
 
 template<class Config>
-int TypeImpl<Config>::BoundBy(TypeImpl* that) {
-  DCHECK(!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());
+typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
+    TypeHandle type1, TypeHandle type2, Region* region) {
+  int bitset = type1->BitsetGlb() & type2->BitsetGlb();
+  if (!BitsetType::IsInhabited(bitset)) bitset = BitsetType::kNone;
+
+  // Fast case: bit sets.
+  if (type1->IsBitset() && type2->IsBitset()) {
+    return BitsetType::New(bitset, region);
+  }
+
+  // Fast case: top or bottom types.
+  if (type1->IsNone() || type2->IsAny()) return type1;
+  if (type2->IsNone() || type2->IsAny()) return type2;
+
+  // Semi-fast case.
+  if (type1->Is(type2)) return type1;
+  if (type2->Is(type1)) return type2;
+
+  // Slow case: create union.
+  int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
+  int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
+  if (!AddIsSafe(size1, size2)) return Any(region);
+  int size = size1 + size2;
+  if (!AddIsSafe(size, 2)) return Any(region);
+  size += 2;
+  UnionHandle result = UnionType::New(size, region);
+  size = 0;
+
+  // Deal with bitsets.
+  result->Set(size++, BitsetType::New(bitset, region));
+
+  // Deal with ranges.
+  TypeHandle range = None(region);
+  RangeType* range1 = type1->GetRange();
+  RangeType* range2 = type2->GetRange();
+  if (range1 != NULL && range2 != NULL) {
+    Limits lim = intersect(Limits(range1), Limits(range2));
+    if (lim.min->Number() <= lim.max->Number()) {
+      range = RangeType::New(lim, region);
     }
-    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->IsContext() && this->IsContext() && this->Is(that)) {
-    return that->AsContext()->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();
+  result->Set(size++, range);
+
+  size = IntersectAux(type1, type2, result, size, region);
+  return NormalizeUnion(result, size);
 }
 
 
 template<class Config>
-int TypeImpl<Config>::IndexInUnion(
-    int bound, UnionHandle unioned, int current_size) {
-  DCHECK(!this->IsUnion());
-  for (int i = 0; i < current_size; ++i) {
-    TypeHandle that = unioned->Get(i);
-    if (that->IsBitset()) {
-      if (BitsetType::Is(bound, 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->IsContext() && this->IsContext()) {
-      if (this->Is(that)) 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;
-    }
+int TypeImpl<Config>::UpdateRange(
+    RangeHandle range, UnionHandle result, int size, Region* region) {
+  if (range->Is(result->Get(1))) return size;

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

Maybe bind to a variable Get(1), instead of repeating it several times.

Also, I think you only want to compare ranges here, right? Instead of going
through the (more expensive) general Is, maybe test IsRange and then do a
Contains on the ranges directly. Similarly below.

[neis1, 2014/09/16 10:04:00]

Done.
Oh, I would really like to avoid that.  How about we leave it as-is but keep it
in mind in case of performance issues?

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

I think it would actually be cleaner conceptually, since this is a function on
RangeTypes specifically. Moreover, it's kind of fishy that you check against
old_range without even checking that it is a RangeType. Is that actually an
invariant here? Shouldn't there be an assertion then, or an AsRange?

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

As discussed, it might be None too.  I documented that with an assertion now.

+  if (!result->Get(1)->Is(range->unhandle())) {

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

Is the unhandle needed?

[neis1, 2014/09/16 10:04:00]

Yes, doesn't compile otherwise.

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

That is weird. What's the error?

(I'd really like to get rid of unhandle altogether, it's an ugly hack.)

+    range = RangeType::New(union_(
+        Limits(range->AsRange()), Limits(result->Get(1)->AsRange())), region);
   }
-  return -1;
-}
+  result->Set(1, range);
 
-
-// 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, int size, TypeHandle type,
-    TypeHandle other, bool is_intersect, Region* region) {
-  if (type->IsUnion()) {
-    UnionHandle unioned = handle(type->AsUnion());
-    for (int i = 0; i < unioned->Length(); ++i) {
-      TypeHandle type_i = unioned->Get(i);
-      DCHECK(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()) {
-    DCHECK(type->IsClass() || type->IsConstant() || type->IsRange() ||
-           type->IsContext() || type->IsArray() || type->IsFunction());
-    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, 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->Rebound(new_bound, region);
-      result->Set(i, type);
+  // Remove any components that just got subsumed.
+  for (int i = 2; i < size; ) {
+    if (result->Get(i)->Is(range->unhandle())) {

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

Likewise, here you only need to consider constants.

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

See above.

+      result->Set(i, result->Get(--size));
+    } else {
+      ++i;
     }
   }
   return size;
 }
 
 
-// Union is O(1) on simple bitsets, but O(n*m) on structured unions.
+template<class Config>
+int TypeImpl<Config>::IntersectAux(
+    TypeHandle lhs, TypeHandle rhs,
+    UnionHandle result, int size, Region* region) {
+  if (lhs->IsUnion()) {
+    for (int i = 0; i < lhs->AsUnion()->Length(); ++i) {
+      size = IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, region);
+    }
+    return size;
+  }
+  if (rhs->IsUnion()) {
+    for (int i = 0; i < rhs->AsUnion()->Length(); ++i) {
+      size = IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, region);
+    }
+    return size;
+  }
+
+  if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
+    return size;
+  }
+
+  if (lhs->IsBitset()) {
+    if (rhs->IsRange()) {
+      return UpdateRange(
+          Config::template cast<RangeType>(rhs), result, size, region);
+    } else {
+      return AddToUnion(rhs, result, size, region);
+    }
+  }
+  if (rhs->IsBitset()) {
+    if (lhs->IsRange()) {
+      return UpdateRange(
+          Config::template cast<RangeType>(lhs), result, size, region);
+    } else {
+      return AddToUnion(lhs, result, size, region);
+    }
+  }
+  if (lhs->IsClass() && !rhs->IsClass()) {
+    if (rhs->IsRange()) {
+      return UpdateRange(
+          Config::template cast<RangeType>(rhs), result, size, region);
+    } else {
+      return AddToUnion(rhs, result, size, region);
+    }
+  }
+  if (rhs->IsClass() && !lhs->IsClass()) {
+    if (lhs->IsRange()) {
+      return UpdateRange(
+          Config::template cast<RangeType>(lhs), result, size, region);
+    } else {
+      return AddToUnion(lhs, result, size, region);
+    }
+  }
+  if (lhs->IsRange()) {
+    if (rhs->IsConstant() &&
+        contains(lhs->AsRange(), *rhs->AsConstant()->Value())) {
+      return AddToUnion(rhs, result, size, region);
+    }
+    return size;  // Shortcut.
+  }
+  if (rhs->IsRange()) {
+    if (lhs->IsConstant() &&
+        contains(rhs->AsRange(), *lhs->AsConstant()->Value())) {
+      return AddToUnion(lhs, result, size, region);
+    }
+    return size;  // Shortcut.
+  }
+
+  if (lhs->Is(rhs)) return AddToUnion(lhs, result, size, region);
+  if (rhs->Is(lhs)) return AddToUnion(rhs, result, size, region);
+  return size;
+}
+
+
 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;
   if (type2->IsAny() || type1->IsNone()) return type2;
 
-  // Semi-fast case: Unioned objects are neither involved nor produced.
-  if (!(type1->IsUnion() || type2->IsUnion())) {
-    if (type1->Is(type2)) return type2;
-    if (type2->Is(type1)) return type1;
+  // Semi-fast case.
+  if (type1->Is(type2)) return type2;
+  if (type2->Is(type1)) return type1;
+
+  // Slow case: create union.
+  int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
+  int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
+  if (!AddIsSafe(size1, size2)) return Any(region);
+  int size = size1 + size2;
+  if (!AddIsSafe(size, 2)) return Any(region);
+  size += 2;
+  UnionHandle result = UnionType::New(size, region);
+  size = 0;
+
+  // Deal with bitsets.
+  TypeHandle bitset = BitsetType::New(
+      type1->BitsetGlb() | type2->BitsetGlb(), region);
+  result->Set(size++, bitset);
+
+  // Deal with ranges.
+  TypeHandle range = None(region);
+  RangeType* range1 = type1->GetRange();
+  RangeType* range2 = type2->GetRange();
+  if (range1 != NULL && range2 != NULL) {
+    range = RangeType::New(union_(Limits(range1), Limits(range2)), region);
+  } else if (range1 != NULL) {
+    range = handle(range1);
+  } else if (range2 != NULL) {
+    range = handle(range2);
   }
+  result->Set(size++, range);
 
-  // Slow case: may need to produce a Unioned object.
-  int size = 0;
-  if (!type1->IsBitset()) {
-    size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1);
-  }
-  if (!type2->IsBitset()) {
-    size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1);
-  }
-  int bitset = type1->BitsetGlb() | type2->BitsetGlb();
-  if (bitset != BitsetType::kNone) ++size;
-  DCHECK(size >= 1);
-
-  UnionHandle unioned = UnionType::New(size, region);
-  size = 0;
-  if (bitset != BitsetType::kNone) {
-    unioned->Set(size++, BitsetType::New(bitset, region));
-  }
-  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);
-    DCHECK(unioned->Wellformed());
-    return unioned;
-  }
+  size = AddToUnion(type1, result, size, region);
+  size = AddToUnion(type2, result, size, region);
+  return NormalizeUnion(result, size);
 }
 
 
-// Intersection is O(1) on simple bitsets, but O(n*m) on structured unions.
+// Add [this] to [result] unless [this] is bitset, range, or already subsumed.

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

s/this/type/g

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

Done.

+// Return new size of [result].
 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);
+int TypeImpl<Config>::AddToUnion(
+    TypeHandle type, UnionHandle result, int size, Region* region) {
+  if (type->IsBitset() || type->IsRange()) return size;
+  if (type->IsUnion()) {
+    for (int i = 0; i < type->AsUnion()->Length(); ++i) {
+      size = AddToUnion(type->AsUnion()->Get(i), result, size, region);
+    }
+    return size;
   }
-
-  // Fast case: top or bottom types.
-  if (type1->IsNone() || type2->IsAny()) return type1;
-  if (type2->IsNone() || type1->IsAny()) return type2;
-
-  // Semi-fast case: Unioned objects are neither involved nor produced.
-  if (!(type1->IsUnion() || type2->IsUnion())) {
-    if (type1->Is(type2)) return type1;
-    if (type2->Is(type1)) return type2;
+  for (int i = 0; i < size; ++i) {
+    if (type->Is(result->Get(i))) return size;
   }
-
-  // Slow case: may need to produce a Unioned object.
-  int size = 0;
-  if (!type1->IsBitset()) {
-    size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1);
-  }
-  if (!type2->IsBitset()) {
-    size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1);
-  }
-  int bitset = type1->BitsetGlb() & type2->BitsetGlb();
-  if (bitset != BitsetType::kNone) ++size;
-  DCHECK(size >= 1);
-
-  UnionHandle unioned = UnionType::New(size, region);
-  size = 0;
-  if (bitset != BitsetType::kNone) {
-    unioned->Set(size++, BitsetType::New(bitset, region));
-  }
-  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);
-    DCHECK(unioned->Wellformed());
-    return unioned;
-  }
+  result->Set(size++, type);
+  return size;
 }
 
 
+template<class Config>
+typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeUnion(
+    UnionHandle unioned, int size) {
+  DCHECK(size >= 2);
+  // If bitset or range are None, use their positions for different types.
+  if (unioned->Get(0)->IsNone()) unioned->Set(0, unioned->Get(--size));
+  if (size >= 2 && unioned->Get(1)->Is(unioned->Get(0))) {

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

This condition looks weird. Can't slot 0 contain whatever at this point?

[neis1, 2014/09/16 10:04:00]

Yes.  The code is correct but it's a little twisted and I just rewrote it.

+    unioned->Set(1, unioned->Get(--size));
+  }
+  if (size == 1) return unioned->Get(0);
+  unioned->Shrink(size);
+  SLOW_DCHECK(unioned->Wellformed());
+  return unioned;
+}
+
+
 // -----------------------------------------------------------------------------
 // Iteration.
 
 template<class Config>
 int TypeImpl<Config>::NumClasses() {
   DisallowHeapAllocation no_allocation;
   if (this->IsClass()) {
     return 1;
   } else if (this->IsUnion()) {
     UnionHandle unioned = handle(this->AsUnion());
@@ skipping 93 matching lines @@
 // -----------------------------------------------------------------------------
 // Conversion between low-level representations.
 
 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()) {
-    TypeHandle bound = BitsetType::New(type->BitsetLub(), region);
-    return ClassType::New(type->AsClass()->Map(), bound, region);
+    return ClassType::New(type->AsClass()->Map(), region);
   } else if (type->IsConstant()) {
-    TypeHandle bound = Convert<OtherType>(type->AsConstant()->Bound(), region);
-    return ConstantType::New(type->AsConstant()->Value(), bound, region);
+    return ConstantType::New(type->AsConstant()->Value(), region);
   } else if (type->IsRange()) {
-    TypeHandle bound = Convert<OtherType>(type->AsRange()->Bound(), region);
     return RangeType::New(
-        type->AsRange()->Min(), type->AsRange()->Max(), bound, region);
+        type->AsRange()->MinV(), type->AsRange()->MaxV(), region);
   } else if (type->IsContext()) {
-    TypeHandle bound = Convert<OtherType>(type->AsContext()->Bound(), region);
     TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region);
-    return ContextType::New(outer, bound, region);
+    return ContextType::New(outer, region);
   } else if (type->IsUnion()) {
     int length = type->AsUnion()->Length();
     UnionHandle unioned = UnionType::New(length, region);
     for (int i = 0; i < length; ++i) {
       TypeHandle t = Convert<OtherType>(type->AsUnion()->Get(i), region);
       unioned->Set(i, t);
     }
     return unioned;
   } else if (type->IsArray()) {
     TypeHandle element = Convert<OtherType>(type->AsArray()->Element(), region);
-    TypeHandle bound = Convert<OtherType>(type->AsArray()->Bound(), region);
-    return ArrayType::New(element, bound, region);
+    return ArrayType::New(element, region);
   } else if (type->IsFunction()) {
     TypeHandle res = Convert<OtherType>(type->AsFunction()->Result(), region);
     TypeHandle rcv = Convert<OtherType>(type->AsFunction()->Receiver(), region);
-    TypeHandle bound = Convert<OtherType>(type->AsFunction()->Bound(), region);
     FunctionHandle function = FunctionType::New(
-        res, rcv, bound, type->AsFunction()->Arity(), region);
+        res, rcv, type->AsFunction()->Arity(), region);
     for (int i = 0; i < function->Arity(); ++i) {
       TypeHandle param = Convert<OtherType>(
           type->AsFunction()->Parameter(i), region);
       function->InitParameter(i, param);
     }
     return function;
   } else {
     UNREACHABLE();
     return None(region);
   }
@@ skipping 64 matching lines @@
   DisallowHeapAllocation no_allocation;
   if (dim != REPRESENTATION_DIM) {
     if (this->IsBitset()) {
       BitsetType::Print(os, SEMANTIC(this->AsBitset()));
     } else if (this->IsClass()) {
       os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < ";
       BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
       os << ")";
     } else if (this->IsConstant()) {
       os << "Constant(" << static_cast<void*>(*this->AsConstant()->Value())
-         << " : ";
-      BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
-      os << ")";
+         << ")";
     } else if (this->IsRange()) {
       os << "Range(" << this->AsRange()->Min()
-         << ".." << this->AsRange()->Max() << " : ";
-      BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
-      os << ")";
+         << ", " << this->AsRange()->Max() << ")";
     } else if (this->IsContext()) {
       os << "Context(";
       this->AsContext()->Outer()->PrintTo(os, dim);
       os << ")";
     } else if (this->IsUnion()) {
       os << "(";
       UnionHandle unioned = handle(this->AsUnion());
       for (int i = 0; i < unioned->Length(); ++i) {
         TypeHandle type_i = unioned->Get(i);
         if (i > 0) os << " | ";
         type_i->PrintTo(os, dim);
       }
       os << ")";
     } else if (this->IsArray()) {
       os << "Array(";
       AsArray()->Element()->PrintTo(os, dim);
       os << ")";
     } else if (this->IsFunction()) {
+      os << "Function[";

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

Hm?

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

I found it impossible to parse non-trivial function types, in particular if an
argument or result type is a union.  Adding this delimiter made it a little
easier.

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

I see, but this syntax is a bit too random (and potentially, long); it should at
least use consistent parens.

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

I got rid of it.

       if (!this->AsFunction()->Receiver()->IsAny()) {
         this->AsFunction()->Receiver()->PrintTo(os, dim);
         os << ".";
       }
       os << "(";
       for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
         if (i > 0) os << ", ";
         this->AsFunction()->Parameter(i)->PrintTo(os, dim);
       }
       os << ")->";
       this->AsFunction()->Result()->PrintTo(os, dim);
+      os << "]";
     } else {
       UNREACHABLE();
     }
   }
   if (dim == BOTH_DIMS) os << "/";
   if (dim != SEMANTIC_DIM) {
     BitsetType::Print(os, REPRESENTATION(this->BitsetLub()));
   }
 }
 
 
 #ifdef DEBUG
 template <class Config>
 void TypeImpl<Config>::Print() {
   OFStream os(stdout);
   PrintTo(os);
   os << endl;
 }
+template <class Config>
+void TypeImpl<Config>::BitsetType::Print(int bitset) {
+  OFStream os(stdout);
+  Print(os, bitset);
+  os << endl;
+}
 #endif
 
 
 // -----------------------------------------------------------------------------
 // Instantiations.
 
 template class TypeImpl<ZoneTypeConfig>;
 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>;
 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>;
 
 template class TypeImpl<HeapTypeConfig>;
 template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>;
 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