From 6fd04d829eed0738643bfd0d58c9f50d5eed1702 Mon Sep 17 00:00:00 2001 From: "neis@chromium.org" Date: Wed, 24 Sep 2014 07:33:51 +0000 Subject: [PATCH] Redesign of the internal type system. Besides addressing a fundamental flaw, this significantly simplifies several aspects of the system. The downside is a loss of precision and a loss of algebraic properties. Range types are now fully implemented. R=rossberg@chromium.org BUG= Review URL: https://codereview.chromium.org/558193003 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24163 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/types.cc | 930 ++++++++++++++++++++++++++-------------------- src/types.h | 284 ++++++++------ test/cctest/test-types.cc | 713 +++++++++++++++++++++-------------- 3 files changed, 1126 insertions(+), 801 deletions(-) diff --git a/src/types.cc b/src/types.cc index 16696ea..8e96d86 100644 --- a/src/types.cc +++ b/src/types.cc @@ -11,165 +11,151 @@ namespace v8 { namespace internal { -// ----------------------------------------------------------------------------- -// Range-related custom order on doubles. -// We want -0 to be less than +0. +// NOTE: If code is marked as being a "shortcut", this means that removing +// the code won't affect the semantics of the surrounding function definition. -static bool dle(double x, double y) { - return x <= y && (x != 0 || IsMinusZero(x) || !IsMinusZero(y)); -} +// ----------------------------------------------------------------------------- +// Range-related helper functions. -static bool deq(double x, double y) { - return dle(x, y) && dle(y, x); +// The result may be invalid (max < min). +template +typename TypeImpl::Limits TypeImpl::Intersect( + 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; } -// ----------------------------------------------------------------------------- -// Glb and lub computation. - -// The largest bitset subsumed by this type. template -typename TypeImpl::bitset -TypeImpl::BitsetType::Glb(TypeImpl* type) { +typename TypeImpl::Limits TypeImpl::Union( + Limits lhs, Limits rhs) { 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. - } else { - return kNone; - } + 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; } -// The smallest bitset subsuming this type. template -typename TypeImpl::bitset -TypeImpl::BitsetType::Lub(TypeImpl* type) { +bool TypeImpl::Overlap( + typename TypeImpl::RangeType* lhs, + typename TypeImpl::RangeType* rhs) { DisallowHeapAllocation no_allocation; - if (type->IsBitset()) { - return type->AsBitset(); - } else if (type->IsUnion()) { - UnionHandle unioned = handle(type->AsUnion()); - bitset result = kNone; - for (int i = 0; i < unioned->Length(); ++i) { - result |= unioned->Get(i)->BitsetLub(); - } - return result; - } 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; - } + typename TypeImpl::Limits lim = Intersect(Limits(lhs), Limits(rhs)); + return lim.min->Number() <= lim.max->Number(); } -// The smallest bitset subsuming this type, ignoring explicit bounds. template -typename TypeImpl::bitset -TypeImpl::BitsetType::InherentLub(TypeImpl* type) { +bool TypeImpl::Contains( + typename TypeImpl::RangeType* lhs, + typename TypeImpl::RangeType* rhs) { DisallowHeapAllocation no_allocation; - if (type->IsBitset()) { - return type->AsBitset(); - } else if (type->IsUnion()) { - UnionHandle unioned = handle(type->AsUnion()); - bitset result = kNone; - for (int i = 0; i < unioned->Length(); ++i) { - result |= unioned->Get(i)->InherentBitsetLub(); - } - return result; - } 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; - } + return lhs->Min()->Number() <= rhs->Min()->Number() + && rhs->Max()->Number() <= lhs->Max()->Number(); } template -typename TypeImpl::bitset -TypeImpl::BitsetType::Lub(i::Object* value) { +bool TypeImpl::Contains( + typename TypeImpl::RangeType* range, i::Object* val) { DisallowHeapAllocation no_allocation; - if (value->IsNumber()) { - return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr); - } - return Lub(i::HeapObject::cast(value)->map()); + return IsInteger(val) + && range->Min()->Number() <= val->Number() + && val->Number() <= range->Max()->Number(); } +// ----------------------------------------------------------------------------- +// Min and Max computation. + template -typename TypeImpl::bitset -TypeImpl::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; +double TypeImpl::Min() { + DCHECK(this->Is(Number())); + if (this->IsBitset()) return BitsetType::Min(this->AsBitset()); + if (this->IsUnion()) { + double min = +V8_INFINITY; + for (int i = 0; i < this->AsUnion()->Length(); ++i) { + min = std::min(min, this->AsUnion()->Get(i)->Min()); + } + return min; + } + if (this->IsRange()) return this->AsRange()->Min()->Number(); + if (this->IsConstant()) return this->AsConstant()->Value()->Number(); + UNREACHABLE(); + return 0; } template -typename TypeImpl::bitset -TypeImpl::BitsetType::Lub(double min, double max) { - DisallowHeapAllocation no_allocation; - DCHECK(dle(min, max)); - if (deq(min, max)) return BitsetType::Lub(min); // Singleton range. - bitset result = BitsetType::kNumber ^ SEMANTIC(BitsetType::kNaN); - if (dle(0, min) || max < 0) result ^= SEMANTIC(BitsetType::kMinusZero); - return result; - // TODO(neis): Could refine this further by doing more checks on min/max. +double TypeImpl::Max() { + DCHECK(this->Is(Number())); + if (this->IsBitset()) return BitsetType::Max(this->AsBitset()); + if (this->IsUnion()) { + double max = -V8_INFINITY; + for (int i = 0; i < this->AsUnion()->Length(); ++i) { + max = std::max(max, this->AsUnion()->Get(i)->Max()); + } + return max; + } + if (this->IsRange()) return this->AsRange()->Max()->Number(); + if (this->IsConstant()) return this->AsConstant()->Value()->Number(); + UNREACHABLE(); + return 0; } +// ----------------------------------------------------------------------------- +// Glb and lub computation. + + +// The largest bitset subsumed by this type. template typename TypeImpl::bitset -TypeImpl::BitsetType::Lub(int32_t value) { - if (value >= 0x40000000) { - return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall; +TypeImpl::BitsetType::Glb(TypeImpl* type) { + DisallowHeapAllocation no_allocation; + if (type->IsBitset()) { + return type->AsBitset(); + } else if (type->IsUnion()) { + SLOW_DCHECK(type->AsUnion()->Wellformed()); + return type->AsUnion()->Get(0)->BitsetGlb(); // Shortcut. + // (The remaining BitsetGlb's are None anyway). + } else { + return kNone; } - if (value >= 0) return kUnsignedSmall; - if (value >= -0x40000000) return kOtherSignedSmall; - return i::SmiValuesAre31Bits() ? kOtherSigned32 : kOtherSignedSmall; } +// The smallest bitset subsuming this type. template typename TypeImpl::bitset -TypeImpl::BitsetType::Lub(uint32_t value) { +TypeImpl::BitsetType::Lub(TypeImpl* type) { DisallowHeapAllocation no_allocation; - if (value >= 0x80000000u) return kOtherUnsigned32; - if (value >= 0x40000000u) { - return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall; + if (type->IsBitset()) return type->AsBitset(); + if (type->IsUnion()) { + int bitset = kNone; + for (int i = 0; i < type->AsUnion()->Length(); ++i) { + bitset |= type->AsUnion()->Get(i)->BitsetLub(); + } + return bitset; } - return kUnsignedSmall; + 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(); + } + if (type->IsConstant()) return type->AsConstant()->Bound()->AsBitset(); + if (type->IsRange()) return type->AsRange()->BitsetLub(); + if (type->IsContext()) return kInternal & kTaggedPtr; + if (type->IsArray()) return kArray; + if (type->IsFunction()) return kFunction; + UNREACHABLE(); + return kNone; } @@ -190,6 +176,7 @@ TypeImpl::BitsetType::Lub(i::Map* map) { 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: @@ -198,7 +185,7 @@ TypeImpl::BitsetType::Lub(i::Map* map) { 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: { @@ -270,64 +257,191 @@ TypeImpl::BitsetType::Lub(i::Map* map) { } -// ----------------------------------------------------------------------------- -// Predicates. +template +typename TypeImpl::bitset +TypeImpl::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()); +} + -// Check this <= that. template -bool TypeImpl::SlowIs(TypeImpl* that) { +typename TypeImpl::bitset +TypeImpl::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; +} - // Fast path for bitsets. - if (this->IsNone()) return true; - if (that->IsBitset()) { - return BitsetType::Is(BitsetType::Lub(this), that->AsBitset()); + +template +typename TypeImpl::bitset +TypeImpl::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 +typename TypeImpl::bitset +TypeImpl::BitsetType::Lub(uint32_t value) { + DisallowHeapAllocation no_allocation; + if (value >= 0x80000000u) return kOtherUnsigned32; + if (value >= 0x40000000u) { + return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall; + } + return kUnsignedSmall; +} + + +// Minimum values of regular numeric bitsets when SmiValuesAre31Bits. +template +const typename TypeImpl::BitsetType::BitsetMin +TypeImpl::BitsetType::BitsetMins31[] = { + {kOtherNumber, -V8_INFINITY}, + {kOtherSigned32, kMinInt}, + {kOtherSignedSmall, -0x40000000}, + {kUnsignedSmall, 0}, + {kOtherUnsigned31, 0x40000000}, + {kOtherUnsigned32, 0x80000000}, + {kOtherNumber, static_cast(kMaxUInt32) + 1} +}; + + +// Minimum values of regular numeric bitsets when SmiValuesAre32Bits. +// OtherSigned32 and OtherUnsigned31 are empty (see the diagrams in types.h). +template +const typename TypeImpl::BitsetType::BitsetMin +TypeImpl::BitsetType::BitsetMins32[] = { + {kOtherNumber, -V8_INFINITY}, + {kOtherSignedSmall, kMinInt}, + {kUnsignedSmall, 0}, + {kOtherUnsigned32, 0x80000000}, + {kOtherNumber, static_cast(kMaxUInt32) + 1} +}; + + +template +typename TypeImpl::bitset +TypeImpl::BitsetType::Lub(Limits lim) { + DisallowHeapAllocation no_allocation; + double min = lim.min->Number(); + double max = lim.max->Number(); + int lub = kNone; + const BitsetMin* mins = BitsetMins(); + + for (size_t i = 1; i < BitsetMinsSize(); ++i) { + if (min < mins[i].min) { + lub |= mins[i-1].bits; + if (max < mins[i].min) return lub; + } + } + return lub |= mins[BitsetMinsSize()-1].bits; +} + + +template +double TypeImpl::BitsetType::Min(bitset bits) { + DisallowHeapAllocation no_allocation; + DCHECK(Is(bits, kNumber)); + const BitsetMin* mins = BitsetMins(); + bool mz = SEMANTIC(bits & kMinusZero); + for (size_t i = 0; i < BitsetMinsSize(); ++i) { + if (Is(SEMANTIC(mins[i].bits), bits)) { + return mz ? std::min(0.0, mins[i].min) : mins[i].min; + } } + if (mz) return 0; + return base::OS::nan_value(); +} + - 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()))); +template +double TypeImpl::BitsetType::Max(bitset bits) { + DisallowHeapAllocation no_allocation; + DCHECK(Is(bits, kNumber)); + const BitsetMin* mins = BitsetMins(); + bool mz = bits & kMinusZero; + if (BitsetType::Is(mins[BitsetMinsSize()-1].bits, bits)) { + return +V8_INFINITY; } - if (that->IsConstant()) { - return this->IsConstant() - && *this->AsConstant()->Value() == *that->AsConstant()->Value() - && this->AsConstant()->Bound()->Is(that->AsConstant()->Bound()); + for (size_t i = BitsetMinsSize()-1; i-- > 0; ) { + if (Is(SEMANTIC(mins[i].bits), bits)) { + return mz ? + std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1; + } } - 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 (mz) return 0; + return base::OS::nan_value(); +} + + +// ----------------------------------------------------------------------------- +// Predicates. + + +template +bool TypeImpl::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 (that->IsContext()) { - return this->IsContext() + if (this->IsContext()) { + return that->IsContext() && this->AsContext()->Outer()->Equals(that->AsContext()->Outer()); } - if (that->IsArray()) { - return this->IsArray() + if (this->IsArray()) { + return that->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; + 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()) || - !that_fun->Receiver()->Equals(this_fun->Receiver())) { + !this_fun->Receiver()->Equals(that_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; + if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false; } return true; } + UNREACHABLE(); + return false; +} + + +// Check if [this] <= [that]. +template +bool TypeImpl::SlowIs(TypeImpl* that) { + DisallowHeapAllocation no_allocation; - // (T1 \/ ... \/ Tn) <= T <=> (T1 <= T) /\ ... /\ (Tn <= T) + if (that->IsBitset()) { + return BitsetType::Is(this->BitsetLub(), that->AsBitset()); + } + if (this->IsBitset()) { + return BitsetType::Is(this->AsBitset(), that->BitsetGlb()); + } + + // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T) if (this->IsUnion()) { UnionHandle unioned = handle(this->AsUnion()); for (int i = 0; i < unioned->Length(); ++i) { @@ -336,15 +450,22 @@ bool TypeImpl::SlowIs(TypeImpl* that) { 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()) { + for (int i = 0; i < that->AsUnion()->Length(); ++i) { + if (this->Is(that->AsUnion()->Get(i))) return true; + if (i > 1 && this->IsRange()) return false; // Shortcut. + } + return false; } - return false; + + if (that->IsRange()) { + return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) + || (this->IsConstant() && + Contains(that->AsRange(), *this->AsConstant()->Value())); + } + if (this->IsRange()) return false; + return this->SimplyEquals(that); } @@ -368,7 +489,7 @@ bool TypeImpl::NowIs(TypeImpl* that) { } -// Check if this contains only (currently) stable classes. +// Check if [this] contains only (currently) stable classes. template bool TypeImpl::NowStable() { DisallowHeapAllocation no_allocation; @@ -379,12 +500,12 @@ bool TypeImpl::NowStable() { } -// Check this overlaps that. +// Check if [this] and [that] overlap. template bool TypeImpl::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) { @@ -393,68 +514,80 @@ bool TypeImpl::Maybe(TypeImpl* that) { 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 (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 (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub())) + return false; + if (this->IsBitset() || that->IsBitset()) return true; + + if (this->IsClass() != that->IsClass()) return true; + + if (this->IsRange()) { + if (that->IsConstant()) { + return Contains(this->AsRange(), *that->AsConstant()->Value()); + } + return that->IsRange() && Overlap(this->AsRange(), that->AsRange()); } - 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 -bool TypeImpl::Contains(i::Object* value) { +typename TypeImpl::RangeType* TypeImpl::GetRange() { 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()); + if (this->IsRange()) return this->AsRange(); + if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) { + return this->AsUnion()->Get(1)->AsRange(); } + return NULL; +} + + +template +bool TypeImpl::Contains(i::Object* value) { + DisallowHeapAllocation no_allocation; for (Iterator 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 bool TypeImpl::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 + // (even when the first element is not a bitset). + // 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; @@ -464,228 +597,231 @@ bool TypeImpl::UnionType::Wellformed() { // ----------------------------------------------------------------------------- // Union and intersection + +static bool AddIsSafe(int x, int y) { + return x >= 0 ? + y <= std::numeric_limits::max() - x : + y >= std::numeric_limits::min() - x; +} + + template -typename TypeImpl::TypeHandle TypeImpl::Rebound( - bitset bitset_bound, Region* region) { - TypeHandle bound = BitsetType::New(bitset_bound, 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; +typename TypeImpl::TypeHandle TypeImpl::Intersect( + TypeHandle type1, TypeHandle type2, Region* region) { + bitset bits = type1->BitsetGlb() & type2->BitsetGlb(); + if (!BitsetType::IsInhabited(bits)) bits = BitsetType::kNone; + + // Fast case: bit sets. + if (type1->IsBitset() && type2->IsBitset()) { + return BitsetType::New(bits, region); } - UNREACHABLE(); - return TypeHandle(); + + // Fast case: top or bottom types. + if (type1->IsNone() || type2->IsAny()) return type1; // Shortcut. + if (type2->IsNone() || type1->IsAny()) return type2; // Shortcut. + + // 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(bits, 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); + } + } + result->Set(size++, range); + + size = IntersectAux(type1, type2, result, size, region); + return NormalizeUnion(result, size); } template -typename TypeImpl::bitset TypeImpl::BoundBy(TypeImpl* that) { - DCHECK(!this->IsUnion()); - if (that->IsUnion()) { - UnionType* unioned = that->AsUnion(); - int length = unioned->Length(); - bitset result = BitsetType::kNone; - for (int i = 0; i < length; ++i) { - result |= BoundBy(unioned->Get(i)->unhandle()); - } - return result; - } 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(); -} - - -template -int TypeImpl::IndexInUnion( - bitset 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; - } - } - return -1; -} - - -// Get non-bitsets from type, bounded by upper. -// Store at result starting at index. Returns updated index. -template -int TypeImpl::ExtendUnion( - UnionHandle result, int size, TypeHandle type, - TypeHandle other, bool is_intersect, Region* region) { - if (type->IsUnion()) { - UnionHandle unioned = Config::template cast(type); - 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()); - bitset inherent_bound = type->InherentBitsetLub(); - bitset old_bound = type->BitsetLub(); - bitset other_bound = type->BoundBy(other->unhandle()) & inherent_bound; - bitset 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 { - bitset 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); +int TypeImpl::UpdateRange( + RangeHandle range, UnionHandle result, int size, Region* region) { + TypeHandle old_range = result->Get(1); + DCHECK(old_range->IsRange() || old_range->IsNone()); + if (range->Is(old_range)) return size; + if (!old_range->Is(range->unhandle())) { + range = RangeType::New( + Union(Limits(range->AsRange()), Limits(old_range->AsRange())), region); + } + result->Set(1, range); + + // Remove any components that just got subsumed. + for (int i = 2; i < size; ) { + if (result->Get(i)->Is(range->unhandle())) { + 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 -typename TypeImpl::TypeHandle TypeImpl::Union( - 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::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; } - // 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; + if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) { + 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 (lhs->IsRange()) { + if (rhs->IsBitset() || rhs->IsClass()) { + return UpdateRange( + Config::template cast(lhs), result, size, region); + } + if (rhs->IsConstant() && + Contains(lhs->AsRange(), *rhs->AsConstant()->Value())) { + return AddToUnion(rhs, result, size, region); + } + return size; } - if (!type2->IsBitset()) { - size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1); + if (rhs->IsRange()) { + if (lhs->IsBitset() || lhs->IsClass()) { + return UpdateRange( + Config::template cast(rhs), result, size, region); + } + if (lhs->IsConstant() && + Contains(rhs->AsRange(), *lhs->AsConstant()->Value())) { + return AddToUnion(lhs, result, size, region); + } + return size; } - bitset bits = type1->BitsetGlb() | type2->BitsetGlb(); - if (bits != BitsetType::kNone) ++size; - DCHECK(size >= 1); - UnionHandle unioned = UnionType::New(size, region); - size = 0; - if (bits != BitsetType::kNone) { - unioned->Set(size++, BitsetType::New(bits, region)); + if (lhs->IsBitset() || rhs->IsBitset()) { + return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, 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; + if (lhs->IsClass() != rhs->IsClass()) { + return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, region); } + if (lhs->SimplyEquals(rhs->unhandle())) { + return AddToUnion(lhs, result, size, region); + } + return size; } -// Intersection is O(1) on simple bitsets, but O(n*m) on structured unions. template -typename TypeImpl::TypeHandle TypeImpl::Intersect( +typename TypeImpl::TypeHandle TypeImpl::Union( TypeHandle type1, TypeHandle type2, Region* region) { + // Fast case: bit sets. if (type1->IsBitset() && type2->IsBitset()) { - return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region); + return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region); } // Fast case: top or bottom types. - if (type1->IsNone() || type2->IsAny()) return type1; - if (type2->IsNone() || type1->IsAny()) return type2; + 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 type1; - if (type2->Is(type1)) return type2; + // 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 bits = BitsetType::New( + type1->BitsetGlb() | type2->BitsetGlb(), region); + result->Set(size++, bits); + + // 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); + + size = AddToUnion(type1, result, size, region); + size = AddToUnion(type2, result, size, region); + return NormalizeUnion(result, size); +} + - // Slow case: may need to produce a Unioned object. - int size = 0; - if (!type1->IsBitset()) { - size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1); +// Add [type] to [result] unless [type] is bitset, range, or already subsumed. +// Return new size of [result]. +template +int TypeImpl::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; } - if (!type2->IsBitset()) { - size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1); + for (int i = 0; i < size; ++i) { + if (type->Is(result->Get(i))) return size; } - bitset bits = type1->BitsetGlb() & type2->BitsetGlb(); - if (bits != BitsetType::kNone) ++size; - DCHECK(size >= 1); + result->Set(size++, type); + return size; +} - UnionHandle unioned = UnionType::New(size, region); - size = 0; - if (bits != BitsetType::kNone) { - unioned->Set(size++, BitsetType::New(bits, 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; +template +typename TypeImpl::TypeHandle TypeImpl::NormalizeUnion( + UnionHandle unioned, int size) { + DCHECK(size >= 2); + // If range is subsumed by bitset, use its place for a different type. + if (unioned->Get(1)->Is(unioned->Get(0))) { + unioned->Set(1, unioned->Get(--size)); + } + // If bitset is None, use its place for a different type. + if (size >= 2 && unioned->Get(0)->IsNone()) { + unioned->Set(0, unioned->Get(--size)); } + if (size == 1) return unioned->Get(0); + unioned->Shrink(size); + SLOW_DCHECK(unioned->Wellformed()); + return unioned; } @@ -802,19 +938,15 @@ typename TypeImpl::TypeHandle TypeImpl::Convert( 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(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(type->AsRange()->Bound(), region); return RangeType::New( - type->AsRange()->Min(), type->AsRange()->Max(), bound, region); + type->AsRange()->Min(), type->AsRange()->Max(), region); } else if (type->IsContext()) { - TypeHandle bound = Convert(type->AsContext()->Bound(), region); TypeHandle outer = Convert(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); @@ -825,14 +957,12 @@ typename TypeImpl::TypeHandle TypeImpl::Convert( return unioned; } else if (type->IsArray()) { TypeHandle element = Convert(type->AsArray()->Element(), region); - TypeHandle bound = Convert(type->AsArray()->Bound(), region); - return ArrayType::New(element, bound, region); + return ArrayType::New(element, region); } else if (type->IsFunction()) { TypeHandle res = Convert(type->AsFunction()->Result(), region); TypeHandle rcv = Convert(type->AsFunction()->Receiver(), region); - TypeHandle bound = Convert(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( type->AsFunction()->Parameter(i), region); @@ -917,14 +1047,10 @@ void TypeImpl::PrintTo(OStream& os, PrintDimension dim) { // NOLINT os << ")"; } else if (this->IsConstant()) { os << "Constant(" << static_cast(*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 << ")"; + os << "Range(" << this->AsRange()->Min()->Number() + << ", " << this->AsRange()->Max()->Number() << ")"; } else if (this->IsContext()) { os << "Context("; this->AsContext()->Outer()->PrintTo(os, dim); @@ -972,6 +1098,12 @@ void TypeImpl::Print() { PrintTo(os); os << endl; } +template +void TypeImpl::BitsetType::Print(bitset bits) { + OFStream os(stdout); + Print(os, bits); + os << endl; +} #endif diff --git a/src/types.h b/src/types.h index 7a58500..e7815ed 100644 --- a/src/types.h +++ b/src/types.h @@ -5,6 +5,7 @@ #ifndef V8_TYPES_H_ #define V8_TYPES_H_ +#include "src/conversions.h" #include "src/factory.h" #include "src/handles.h" #include "src/ostreams.h" @@ -23,6 +24,7 @@ namespace internal { // Types consist of two dimensions: semantic (value range) and representation. // Both are related through subtyping. // +// // SEMANTIC DIMENSION // // The following equations and inequations hold for the semantic axis: @@ -61,6 +63,7 @@ namespace internal { // However, we also define a 'temporal' variant of the subtyping relation that // considers the _current_ state only, i.e., Constant(x) <_now Class(map(x)). // +// // REPRESENTATIONAL DIMENSION // // For the representation axis, the following holds: @@ -88,6 +91,16 @@ namespace internal { // SignedSmall /\ TaggedInt (a 'smi') // Number /\ TaggedPtr (a heap number) // +// +// RANGE TYPES +// +// A range type represents a continuous integer interval by its minimum and +// maximum value. Either value might be an infinity. +// +// Constant(v) is considered a subtype of Range(x..y) if v happens to be an +// integer between x and y. +// +// // PREDICATES // // There are two main functions for testing types: @@ -109,16 +122,18 @@ namespace internal { // Any compilation decision based on such temporary properties requires runtime // guarding! // +// // PROPERTIES // // Various formal properties hold for constructors, operators, and predicates -// over types. For example, constructors are injective, subtyping is a complete -// partial order, union and intersection satisfy the usual algebraic properties. +// over types. For example, constructors are injective and subtyping is a +// complete partial order. // // See test/cctest/test-types.cc for a comprehensive executable specification, // especially with respect to the properties of the more exotic 'temporal' // constructors and predicates (those prefixed 'Now'). // +// // IMPLEMENTATION // // Internally, all 'primitive' types, and their unions, are represented as @@ -208,11 +223,35 @@ namespace internal { kUndefined | kInternal) \ V(Any, 0xfffffffeu) -#define BITSET_TYPE_LIST(V) \ - MASK_BITSET_TYPE_LIST(V) \ +/* + * The following diagrams show how integers (in the mathematical sense) are + * divided among the different atomic numerical types. + * + * If SmiValuesAre31Bits(): + * + * ON OS32 OSS US OU31 OU32 ON + * ______[_______[_______[_______[_______[_______[_______ + * -2^31 -2^30 0 2^30 2^31 2^32 + * + * Otherwise: + * + * ON OSS US OU32 ON + * ______[_______________[_______________[_______[_______ + * -2^31 0 2^31 2^32 + * + * + * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. + * + */ + +#define PROPER_BITSET_TYPE_LIST(V) \ REPRESENTATION_BITSET_TYPE_LIST(V) \ SEMANTIC_BITSET_TYPE_LIST(V) +#define BITSET_TYPE_LIST(V) \ + MASK_BITSET_TYPE_LIST(V) \ + PROPER_BITSET_TYPE_LIST(V) + // ----------------------------------------------------------------------------- // The abstract Type class, parameterized over the low-level representation. @@ -282,17 +321,17 @@ class TypeImpl : public Config::Base { static TypeHandle type(Region* region) { \ return BitsetType::New(BitsetType::k##type, region); \ } - BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) + PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) #undef DEFINE_TYPE_CONSTRUCTOR static TypeHandle Class(i::Handle map, Region* region) { return ClassType::New(map, region); } static TypeHandle Constant(i::Handle value, Region* region) { - // TODO(neis): Return RangeType for numerical values. return ConstantType::New(value, region); } - static TypeHandle Range(double min, double max, Region* region) { + static TypeHandle Range( + i::Handle min, i::Handle max, Region* region) { return RangeType::New(min, max, region); } static TypeHandle Context(TypeHandle outer, Region* region) { @@ -360,7 +399,7 @@ class TypeImpl : public Config::Base { template bool Equals(TypeHandle that) { return this->Equals(*that); } - // Equivalent to Constant(value)->Is(this), but avoiding allocation. + // Equivalent to Constant(val)->Is(this), but avoiding allocation. bool Contains(i::Object* val); bool Contains(i::Handle val) { return this->Contains(*val); } @@ -407,6 +446,13 @@ class TypeImpl : public Config::Base { ArrayType* AsArray() { return ArrayType::cast(this); } FunctionType* AsFunction() { return FunctionType::cast(this); } + // Minimum and maximum of a numeric type. + // These functions do not distinguish between -0 and +0. If the type equals + // kNaN, they return NaN; otherwise kNaN is ignored. Only call these + // functions on subtypes of Number. + double Min(); + double Max(); + int NumClasses(); int NumConstants(); @@ -469,16 +515,45 @@ class TypeImpl : public Config::Base { bitset BitsetGlb() { return BitsetType::Glb(this); } bitset BitsetLub() { return BitsetType::Lub(this); } - bitset InherentBitsetLub() { return BitsetType::InherentLub(this); } bool SlowIs(TypeImpl* that); - TypeHandle Rebound(bitset bound, Region* region); - bitset BoundBy(TypeImpl* that); - int IndexInUnion(bitset bound, UnionHandle unioned, int current_size); - static int ExtendUnion( - UnionHandle unioned, int current_size, TypeHandle t, - TypeHandle other, bool is_intersect, Region* region); + static bool IsInteger(double x) { + return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. + } + static bool IsInteger(i::Object* x) { + return x->IsNumber() && IsInteger(x->Number()); + } + + struct Limits { + i::Handle min; + i::Handle max; + Limits(i::Handle min, i::Handle max) : + min(min), max(max) {} + explicit Limits(RangeType* range) : + min(range->Min()), max(range->Max()) {} + }; + + static Limits Intersect(Limits lhs, Limits rhs); + static Limits Union(Limits lhs, Limits rhs); + static bool Overlap(RangeType* lhs, RangeType* rhs); + static bool Contains(RangeType* lhs, RangeType* rhs); + static bool Contains(RangeType* range, i::Object* val); + + RangeType* GetRange(); + static int UpdateRange( + RangeHandle type, UnionHandle result, int size, Region* region); + + bool SimplyEquals(TypeImpl* that); + template + bool SimplyEquals(TypeHandle that) { return this->SimplyEquals(*that); } + + static int AddToUnion( + TypeHandle type, UnionHandle result, int size, Region* region); + static int IntersectAux( + TypeHandle type, TypeHandle other, + UnionHandle result, int size, Region* region); + static TypeHandle NormalizeUnion(UnionHandle unioned, int size); }; @@ -499,19 +574,28 @@ class TypeImpl::BitsetType : public TypeImpl { bitset Bitset() { return Config::as_bitset(this); } - static TypeImpl* New(bitset bits) { return Config::from_bitset(bits); } + static TypeImpl* New(bitset bits) { + DCHECK(bits == kNone || IsInhabited(bits)); + return Config::from_bitset(bits); + } static TypeHandle New(bitset bits, Region* region) { + DCHECK(bits == kNone || IsInhabited(bits)); return Config::from_bitset(bits, region); } + // TODO(neis): Eventually allow again for types with empty semantics + // part and modify intersection and possibly subtyping accordingly. static bool IsInhabited(bitset bits) { - return (bits & kRepresentation) && (bits & kSemantic); + return bits & kSemantic; } static bool Is(bitset bits1, bitset bits2) { return (bits1 | bits2) == bits2; } + static double Min(bitset); + static double Max(bitset); + static bitset Glb(TypeImpl* type); // greatest lower bound that's a bitset static bitset Lub(TypeImpl* type); // least upper bound that's a bitset static bitset Lub(i::Object* value); @@ -519,12 +603,29 @@ class TypeImpl::BitsetType : public TypeImpl { static bitset Lub(int32_t value); static bitset Lub(uint32_t value); static bitset Lub(i::Map* map); - static bitset Lub(double min, double max); - static bitset InherentLub(TypeImpl* type); + static bitset Lub(Limits lim); static const char* Name(bitset); static void Print(OStream& os, bitset); // NOLINT - using TypeImpl::PrintTo; +#ifdef DEBUG + static void Print(bitset); +#endif + + private: + struct BitsetMin{ + bitset bits; + double min; + }; + static const BitsetMin BitsetMins31[]; + static const BitsetMin BitsetMins32[]; + static const BitsetMin* BitsetMins() { + return i::SmiValuesAre31Bits() ? BitsetMins31 : BitsetMins32; + } + static size_t BitsetMinsSize() { + return i::SmiValuesAre31Bits() ? 7 : 5; + /* arraysize(BitsetMins31) : arraysize(BitsetMins32); */ + // Using arraysize here doesn't compile on Windows. + } }; @@ -611,35 +712,25 @@ template class TypeImpl::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); + return Config::is_class(this) ? + BitsetType::New(BitsetType::Lub(*Config::as_class(this)), region) : + this->Get(0); } i::Handle Map() { - return Config::is_class(this) - ? Config::as_class(this) - : this->template GetValue(1); - } - - static ClassHandle New( - i::Handle map, TypeHandle bound, Region* region) { - DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(*map))); - ClassHandle type = Config::template cast( - StructuralType::New(StructuralType::kClassTag, 2, region)); - type->Set(0, bound); - type->SetValue(1, map); - return type; + return Config::is_class(this) ? Config::as_class(this) : + this->template GetValue(1); } static ClassHandle New(i::Handle map, Region* region) { ClassHandle type = Config::template cast(Config::from_class(map, region)); - if (type->IsClass()) { - return type; - } else { - TypeHandle bound = BitsetType::New(BitsetType::Lub(*map), region); - return New(map, bound, region); + if (!type->IsClass()) { + type = Config::template cast( + StructuralType::New(StructuralType::kClassTag, 2, region)); + type->Set(0, BitsetType::New(BitsetType::Lub(*map), region)); + type->SetValue(1, map); } + return type; } static ClassType* cast(TypeImpl* type) { @@ -658,26 +749,21 @@ class TypeImpl::ConstantType : public StructuralType { TypeHandle Bound() { return this->Get(0); } i::Handle Value() { return this->template GetValue(1); } - static ConstantHandle New( - i::Handle value, TypeHandle bound, Region* region) { - DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(*value))); + static ConstantHandle New(i::Handle value, Region* region) { ConstantHandle type = Config::template cast( StructuralType::New(StructuralType::kConstantTag, 2, region)); - type->Set(0, bound); + type->Set(0, BitsetType::New(BitsetType::Lub(*value), region)); type->SetValue(1, value); return type; } - static ConstantHandle New(i::Handle value, Region* region) { - TypeHandle bound = BitsetType::New(BitsetType::Lub(*value), region); - return New(value, bound, region); - } - static ConstantType* cast(TypeImpl* type) { DCHECK(type->IsConstant()); return static_cast(type); } }; +// TODO(neis): Also cache value if numerical. +// TODO(neis): Allow restricting the representation. // ----------------------------------------------------------------------------- @@ -686,27 +772,23 @@ class TypeImpl::ConstantType : public StructuralType { template class TypeImpl::RangeType : public StructuralType { public: - TypeHandle Bound() { return this->Get(0); } - double Min() { return this->template GetValue(1)->value(); } - double Max() { return this->template GetValue(2)->value(); } + int BitsetLub() { return this->Get(0)->AsBitset(); } + i::Handle Min() { return this->template GetValue(1); } + i::Handle Max() { return this->template GetValue(2); } static RangeHandle New( - double min, double max, TypeHandle bound, Region* region) { - DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(min, max))); + i::Handle min, i::Handle max, Region* region) { + DCHECK(min->Number() <= max->Number()); RangeHandle type = Config::template cast( StructuralType::New(StructuralType::kRangeTag, 3, region)); - type->Set(0, bound); - Factory* factory = Config::isolate(region)->factory(); - Handle minV = factory->NewHeapNumber(min); - Handle maxV = factory->NewHeapNumber(max); - type->SetValue(1, minV); - type->SetValue(2, maxV); + type->Set(0, BitsetType::New(BitsetType::Lub(Limits(min, max)), region)); + type->SetValue(1, min); + type->SetValue(2, max); return type; } - static RangeHandle New(double min, double max, Region* region) { - TypeHandle bound = BitsetType::New(BitsetType::Lub(min, max), region); - return New(min, max, bound, region); + static RangeHandle New(Limits lim, Region* region) { + return New(lim.min, lim.max, region); } static RangeType* cast(TypeImpl* type) { @@ -714,6 +796,8 @@ class TypeImpl::RangeType : public StructuralType { return static_cast(type); } }; +// TODO(neis): Also cache min and max values. +// TODO(neis): Allow restricting the representation. // ----------------------------------------------------------------------------- @@ -722,25 +806,15 @@ class TypeImpl::RangeType : public StructuralType { template class TypeImpl::ContextType : public StructuralType { public: - TypeHandle Bound() { return this->Get(0); } - TypeHandle Outer() { return this->Get(1); } + TypeHandle Outer() { return this->Get(0); } - static ContextHandle New(TypeHandle outer, TypeHandle bound, Region* region) { - DCHECK(BitsetType::Is( - bound->AsBitset(), BitsetType::kInternal & BitsetType::kTaggedPtr)); + static ContextHandle New(TypeHandle outer, Region* region) { ContextHandle type = Config::template cast( - StructuralType::New(StructuralType::kContextTag, 2, region)); - type->Set(0, bound); - type->Set(1, outer); + StructuralType::New(StructuralType::kContextTag, 1, region)); + type->Set(0, outer); return type; } - static ContextHandle New(TypeHandle outer, Region* region) { - TypeHandle bound = BitsetType::New( - BitsetType::kInternal & BitsetType::kTaggedPtr, region); - return New(outer, bound, region); - } - static ContextType* cast(TypeImpl* type) { DCHECK(type->IsContext()); return static_cast(type); @@ -754,23 +828,15 @@ class TypeImpl::ContextType : public StructuralType { template class TypeImpl::ArrayType : public StructuralType { public: - TypeHandle Bound() { return this->Get(0); } - TypeHandle Element() { return this->Get(1); } + TypeHandle Element() { return this->Get(0); } - static ArrayHandle New(TypeHandle element, TypeHandle bound, Region* region) { - DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::kArray)); + static ArrayHandle New(TypeHandle element, Region* region) { ArrayHandle type = Config::template cast( - StructuralType::New(StructuralType::kArrayTag, 2, region)); - type->Set(0, bound); - type->Set(1, element); + StructuralType::New(StructuralType::kArrayTag, 1, region)); + type->Set(0, element); return type; } - static ArrayHandle New(TypeHandle element, Region* region) { - TypeHandle bound = BitsetType::New(BitsetType::kArray, region); - return New(element, bound, region); - } - static ArrayType* cast(TypeImpl* type) { DCHECK(type->IsArray()); return static_cast(type); @@ -784,32 +850,22 @@ class TypeImpl::ArrayType : public StructuralType { template class TypeImpl::FunctionType : public StructuralType { public: - int Arity() { return this->Length() - 3; } - TypeHandle Bound() { return this->Get(0); } - TypeHandle Result() { return this->Get(1); } - TypeHandle Receiver() { return this->Get(2); } - TypeHandle Parameter(int i) { return this->Get(3 + i); } + int Arity() { return this->Length() - 2; } + TypeHandle Result() { return this->Get(0); } + TypeHandle Receiver() { return this->Get(1); } + TypeHandle Parameter(int i) { return this->Get(2 + i); } - void InitParameter(int i, TypeHandle type) { this->Set(3 + i, type); } + void InitParameter(int i, TypeHandle type) { this->Set(2 + i, type); } static FunctionHandle New( - TypeHandle result, TypeHandle receiver, TypeHandle bound, - int arity, Region* region) { - DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::kFunction)); + TypeHandle result, TypeHandle receiver, int arity, Region* region) { FunctionHandle type = Config::template cast( - StructuralType::New(StructuralType::kFunctionTag, 3 + arity, region)); - type->Set(0, bound); - type->Set(1, result); - type->Set(2, receiver); + StructuralType::New(StructuralType::kFunctionTag, 2 + arity, region)); + type->Set(0, result); + type->Set(1, receiver); return type; } - static FunctionHandle New( - TypeHandle result, TypeHandle receiver, int arity, Region* region) { - TypeHandle bound = BitsetType::New(BitsetType::kFunction, region); - return New(result, receiver, bound, arity, region); - } - static FunctionType* cast(TypeImpl* type) { DCHECK(type->IsFunction()); return static_cast(type); @@ -854,11 +910,6 @@ struct ZoneTypeConfig { typedef i::Zone Region; template struct Handle { typedef T* type; }; - // TODO(neis): This will be removed again once we have struct_get_double(). - static inline i::Isolate* isolate(Region* region) { - return region->isolate(); - } - template static inline T* handle(T* type); template static inline T* cast(Type* type); @@ -901,11 +952,6 @@ struct HeapTypeConfig { typedef i::Isolate Region; template struct Handle { typedef i::Handle type; }; - // TODO(neis): This will be removed again once we have struct_get_double(). - static inline i::Isolate* isolate(Region* region) { - return region; - } - template static inline i::Handle handle(T* type); template static inline i::Handle cast(i::Handle type); diff --git a/test/cctest/test-types.cc b/test/cctest/test-types.cc index 3e3073b..0cd2472 100644 --- a/test/cctest/test-types.cc +++ b/test/cctest/test-types.cc @@ -42,7 +42,7 @@ struct ZoneRep { using Type::BitsetType::New; using Type::BitsetType::Glb; using Type::BitsetType::Lub; - using Type::BitsetType::InherentLub; + using Type::BitsetType::IsInhabited; }; }; @@ -69,12 +69,9 @@ struct HeapRep { using HeapType::BitsetType::New; using HeapType::BitsetType::Glb; using HeapType::BitsetType::Lub; - using HeapType::BitsetType::InherentLub; + using HeapType::BitsetType::IsInhabited; static bitset Glb(Handle type) { return Glb(*type); } static bitset Lub(Handle type) { return Lub(*type); } - static bitset InherentLub(Handle type) { - return InherentLub(*type); - } }; }; @@ -87,14 +84,19 @@ class Types { #define DECLARE_TYPE(name, value) \ name = Type::name(region); \ types.push_back(name); - BITSET_TYPE_LIST(DECLARE_TYPE) + PROPER_BITSET_TYPE_LIST(DECLARE_TYPE) #undef DECLARE_TYPE - object_map = isolate->factory()->NewMap(JS_OBJECT_TYPE, 3 * kPointerSize); - array_map = isolate->factory()->NewMap(JS_ARRAY_TYPE, 4 * kPointerSize); + object_map = isolate->factory()->NewMap( + JS_OBJECT_TYPE, JSObject::kHeaderSize); + array_map = isolate->factory()->NewMap( + JS_ARRAY_TYPE, JSArray::kSize); + number_map = isolate->factory()->NewMap( + HEAP_NUMBER_TYPE, HeapNumber::kSize); uninitialized_map = isolate->factory()->uninitialized_map(); ObjectClass = Type::Class(object_map, region); ArrayClass = Type::Class(array_map, region); + NumberClass = Type::Class(number_map, region); UninitializedClass = Type::Class(uninitialized_map, region); maps.push_back(object_map); @@ -127,13 +129,15 @@ class Types { types.push_back(Type::Constant(*it, region)); } - doubles.push_back(-0.0); - doubles.push_back(+0.0); - doubles.push_back(-std::numeric_limits::infinity()); - doubles.push_back(+std::numeric_limits::infinity()); + integers.push_back(isolate->factory()->NewNumber(-V8_INFINITY)); + integers.push_back(isolate->factory()->NewNumber(+V8_INFINITY)); + integers.push_back(isolate->factory()->NewNumber(-rng_->NextInt(10))); + integers.push_back(isolate->factory()->NewNumber(+rng_->NextInt(10))); for (int i = 0; i < 10; ++i) { - doubles.push_back(rng_->NextInt()); - doubles.push_back(rng_->NextDouble() * rng_->NextInt()); + double x = rng_->NextInt(); + integers.push_back(isolate->factory()->NewNumber(x)); + x *= rng_->NextInt(); + if (!IsMinusZero(x)) integers.push_back(isolate->factory()->NewNumber(x)); } NumberArray = Type::Array(Number, region); @@ -152,6 +156,7 @@ class Types { Handle object_map; Handle array_map; + Handle number_map; Handle uninitialized_map; Handle smi; @@ -167,6 +172,7 @@ class Types { TypeHandle ObjectClass; TypeHandle ArrayClass; + TypeHandle NumberClass; TypeHandle UninitializedClass; TypeHandle SmiConstant; @@ -188,27 +194,11 @@ class Types { typedef std::vector TypeVector; typedef std::vector > MapVector; typedef std::vector > ValueVector; - typedef std::vector DoubleVector; TypeVector types; MapVector maps; ValueVector values; - DoubleVector doubles; // Some floating-point values, excluding NaN. - - // Range type helper functions, partially copied from types.cc. - // Note: dle(dmin(x,y), dmax(x,y)) holds iff neither x nor y is NaN. - bool dle(double x, double y) { - return x <= y && (x != 0 || IsMinusZero(x) || !IsMinusZero(y)); - } - bool deq(double x, double y) { - return dle(x, y) && dle(y, x); - } - double dmin(double x, double y) { - return dle(x, y) ? x : y; - } - double dmax(double x, double y) { - return dle(x, y) ? y : x; - } + ValueVector integers; // "Integer" values used for range limits. TypeHandle Of(Handle value) { return Type::Of(value, region_); @@ -218,16 +208,20 @@ class Types { return Type::NowOf(value, region_); } + TypeHandle Class(Handle map) { + return Type::Class(map, region_); + } + TypeHandle Constant(Handle value) { return Type::Constant(value, region_); } - TypeHandle Range(double min, double max) { + TypeHandle Range(Handle min, Handle max) { return Type::Range(min, max, region_); } - TypeHandle Class(Handle map) { - return Type::Class(map, region_); + TypeHandle Context(TypeHandle outer) { + return Type::Context(outer, region_); } TypeHandle Array1(TypeHandle element) { @@ -264,18 +258,18 @@ class Types { return types[rng_->NextInt(static_cast(types.size()))]; } - TypeHandle Fuzz(int depth = 5) { + TypeHandle Fuzz(int depth = 4) { switch (rng_->NextInt(depth == 0 ? 3 : 20)) { case 0: { // bitset int n = 0 #define COUNT_BITSET_TYPES(type, value) + 1 - BITSET_TYPE_LIST(COUNT_BITSET_TYPES) + PROPER_BITSET_TYPE_LIST(COUNT_BITSET_TYPES) #undef COUNT_BITSET_TYPES ; int i = rng_->NextInt(n); #define PICK_BITSET_TYPE(type, value) \ if (i-- == 0) return Type::type(region_); - BITSET_TYPE_LIST(PICK_BITSET_TYPE) + PROPER_BITSET_TYPE_LIST(PICK_BITSET_TYPE) #undef PICK_BITSET_TYPE UNREACHABLE(); } @@ -287,18 +281,26 @@ class Types { int i = rng_->NextInt(static_cast(values.size())); return Type::Constant(values[i], region_); } - case 3: { // context + case 3: { // range + int i = rng_->NextInt(static_cast(integers.size())); + int j = rng_->NextInt(static_cast(integers.size())); + i::Handle min = integers[i]; + i::Handle max = integers[j]; + if (min->Number() > max->Number()) std::swap(min, max); + return Type::Range(min, max, region_); + } + case 4: { // context int depth = rng_->NextInt(3); TypeHandle type = Type::Internal(region_); for (int i = 0; i < depth; ++i) type = Type::Context(type, region_); return type; } - case 4: { // array + case 5: { // array TypeHandle element = Fuzz(depth / 2); return Type::Array(element, region_); } - case 5: - case 6: { // function + case 6: + case 7: { // function TypeHandle result = Fuzz(depth / 2); TypeHandle receiver = Fuzz(depth / 2); int arity = rng_->NextInt(3); @@ -336,7 +338,6 @@ struct Tests : Rep { typedef typename TypesInstance::TypeVector::iterator TypeIterator; typedef typename TypesInstance::MapVector::iterator MapIterator; typedef typename TypesInstance::ValueVector::iterator ValueIterator; - typedef typename TypesInstance::DoubleVector::iterator DoubleIterator; Isolate* isolate; HandleScope scope; @@ -353,14 +354,15 @@ struct Tests : Rep { bool Equal(TypeHandle type1, TypeHandle type2) { return type1->Equals(type2) && - Rep::IsBitset(type1) == Rep::IsBitset(type2) && - Rep::IsUnion(type1) == Rep::IsUnion(type2) && + this->IsBitset(type1) == this->IsBitset(type2) && + this->IsUnion(type1) == this->IsUnion(type2) && type1->NumClasses() == type2->NumClasses() && type1->NumConstants() == type2->NumConstants() && - (!Rep::IsBitset(type1) || - Rep::AsBitset(type1) == Rep::AsBitset(type2)) && - (!Rep::IsUnion(type1) || - Rep::Length(Rep::AsUnion(type1)) == Rep::Length(Rep::AsUnion(type2))); + (!this->IsBitset(type1) || + this->AsBitset(type1) == this->AsBitset(type2)) && + (!this->IsUnion(type1) || + this->Length(this->AsUnion(type1)) == + this->Length(this->AsUnion(type2))); } void CheckEqual(TypeHandle type1, TypeHandle type2) { @@ -370,36 +372,37 @@ struct Tests : Rep { void CheckSub(TypeHandle type1, TypeHandle type2) { CHECK(type1->Is(type2)); CHECK(!type2->Is(type1)); - if (Rep::IsBitset(type1) && Rep::IsBitset(type2)) { - CHECK(Rep::AsBitset(type1) != Rep::AsBitset(type2)); + if (this->IsBitset(type1) && this->IsBitset(type2)) { + CHECK(this->AsBitset(type1) != this->AsBitset(type2)); } } void CheckUnordered(TypeHandle type1, TypeHandle type2) { CHECK(!type1->Is(type2)); CHECK(!type2->Is(type1)); - if (Rep::IsBitset(type1) && Rep::IsBitset(type2)) { - CHECK(Rep::AsBitset(type1) != Rep::AsBitset(type2)); + if (this->IsBitset(type1) && this->IsBitset(type2)) { + CHECK(this->AsBitset(type1) != this->AsBitset(type2)); } } - void CheckOverlap(TypeHandle type1, TypeHandle type2, TypeHandle mask) { + void CheckOverlap(TypeHandle type1, TypeHandle type2) { CHECK(type1->Maybe(type2)); CHECK(type2->Maybe(type1)); - if (Rep::IsBitset(type1) && Rep::IsBitset(type2)) { - CHECK(0 != - (Rep::AsBitset(type1) & Rep::AsBitset(type2) & Rep::AsBitset(mask))); - } } - void CheckDisjoint(TypeHandle type1, TypeHandle type2, TypeHandle mask) { + void CheckDisjoint(TypeHandle type1, TypeHandle type2) { CHECK(!type1->Is(type2)); CHECK(!type2->Is(type1)); CHECK(!type1->Maybe(type2)); CHECK(!type2->Maybe(type1)); - if (Rep::IsBitset(type1) && Rep::IsBitset(type2)) { - CHECK(0 == - (Rep::AsBitset(type1) & Rep::AsBitset(type2) & Rep::AsBitset(mask))); + } + + void IsSomeType() { + for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { + TypeHandle t = *it; + CHECK(1 == + this->IsBitset(t) + t->IsClass() + t->IsConstant() + t->IsRange() + + this->IsUnion(t) + t->IsArray() + t->IsFunction() + t->IsContext()); } } @@ -458,15 +461,16 @@ struct Tests : Rep { } } - // Intersect(T1, T2) is bitwise conjunction for bitsets T1,T2 + // Intersect(T1, T2) is bitwise conjunction for bitsets T1,T2 (modulo None) for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { TypeHandle type1 = *it1; TypeHandle type2 = *it2; TypeHandle intersect12 = T.Intersect(type1, type2); if (this->IsBitset(type1) && this->IsBitset(type2)) { + bitset bits = this->AsBitset(type1) & this->AsBitset(type2); CHECK( - (this->AsBitset(type1) & this->AsBitset(type2)) == + (Rep::BitsetType::IsInhabited(bits) ? bits : 0) == this->AsBitset(intersect12)); } } @@ -568,47 +572,51 @@ struct Tests : Rep { void Range() { // Constructor - for (DoubleIterator i = T.doubles.begin(); i != T.doubles.end(); ++i) { - for (DoubleIterator j = T.doubles.begin(); j != T.doubles.end(); ++j) { - double min = T.dmin(*i, *j); - double max = T.dmax(*i, *j); + for (ValueIterator i = T.integers.begin(); i != T.integers.end(); ++i) { + for (ValueIterator j = T.integers.begin(); j != T.integers.end(); ++j) { + i::Handle min = *i; + i::Handle max = *j; + if (min->Number() > max->Number()) std::swap(min, max); TypeHandle type = T.Range(min, max); CHECK(type->IsRange()); } } // Range attributes - for (DoubleIterator i = T.doubles.begin(); i != T.doubles.end(); ++i) { - for (DoubleIterator j = T.doubles.begin(); j != T.doubles.end(); ++j) { - double min = T.dmin(*i, *j); - double max = T.dmax(*i, *j); + for (ValueIterator i = T.integers.begin(); i != T.integers.end(); ++i) { + for (ValueIterator j = T.integers.begin(); j != T.integers.end(); ++j) { + i::Handle min = *i; + i::Handle max = *j; + if (min->Number() > max->Number()) std::swap(min, max); TypeHandle type = T.Range(min, max); - CHECK(min == type->AsRange()->Min()); - CHECK(max == type->AsRange()->Max()); - } - } - -// TODO(neis): enable once subtyping is updated. -// // Functionality & Injectivity: Range(min1, max1) = Range(min2, max2) <=> -// // min1 = min2 /\ max1 = max2 -// for (DoubleIterator i1 = T.doubles.begin(); i1 != T.doubles.end(); ++i1) { -// for (DoubleIterator j1 = T.doubles.begin(); j1 != T.doubles.end(); ++j1) { -// for (DoubleIterator i2 = T.doubles.begin(); -// i2 != T.doubles.end(); ++i2) { -// for (DoubleIterator j2 = T.doubles.begin(); -// j2 != T.doubles.end(); ++j2) { -// double min1 = T.dmin(*i1, *j1); -// double max1 = T.dmax(*i1, *j1); -// double min2 = T.dmin(*i2, *j2); -// double max2 = T.dmax(*i2, *j2); -// TypeHandle type1 = T.Range(min1, max1); -// TypeHandle type2 = T.Range(min2, max2); -// CHECK(Equal(type1, type2) == -// (T.deq(min1, min2) && T.deq(max1, max2))); -// } -// } -// } -// } + CHECK(*min == *type->AsRange()->Min()); + CHECK(*max == *type->AsRange()->Max()); + } + } + + // Functionality & Injectivity: + // Range(min1, max1) = Range(min2, max2) <=> min1 = min2 /\ max1 = max2 + for (ValueIterator i1 = T.integers.begin(); + i1 != T.integers.end(); ++i1) { + for (ValueIterator j1 = T.integers.begin(); + j1 != T.integers.end(); ++j1) { + for (ValueIterator i2 = T.integers.begin(); + i2 != T.integers.end(); ++i2) { + for (ValueIterator j2 = T.integers.begin(); + j2 != T.integers.end(); ++j2) { + i::Handle min1 = *i1; + i::Handle max1 = *j1; + i::Handle min2 = *i2; + i::Handle max2 = *j2; + if (min1->Number() > max1->Number()) std::swap(min1, max1); + if (min2->Number() > max2->Number()) std::swap(min2, max2); + TypeHandle type1 = T.Range(min1, max1); + TypeHandle type2 = T.Range(min2, max2); + CHECK(Equal(type1, type2) == (*min1 == *min2 && *max1 == *max2)); + } + } + } + } } void Array() { @@ -716,15 +724,26 @@ struct Tests : Rep { CHECK(const_type->Is(of_type)); } - // Constant(V)->Is(T) iff Of(V)->Is(T) or T->Maybe(Constant(V)) + // If Of(V)->Is(T), then Constant(V)->Is(T) for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { Handle value = *vt; TypeHandle type = *it; TypeHandle const_type = T.Constant(value); TypeHandle of_type = T.Of(value); - CHECK(const_type->Is(type) == - (of_type->Is(type) || type->Maybe(const_type))); + CHECK(!of_type->Is(type) || const_type->Is(type)); + } + } + + // If Constant(V)->Is(T), then Of(V)->Is(T) or T->Maybe(Constant(V)) + for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { + for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { + Handle value = *vt; + TypeHandle type = *it; + TypeHandle const_type = T.Constant(value); + TypeHandle of_type = T.Of(value); + CHECK(!const_type->Is(type) || + of_type->Is(type) || type->Maybe(const_type)); } } } @@ -746,19 +765,32 @@ struct Tests : Rep { CHECK(nowof_type->Is(of_type)); } - // Constant(V)->NowIs(T) iff NowOf(V)->NowIs(T) or T->Maybe(Constant(V)) + // If NowOf(V)->NowIs(T), then Constant(V)->NowIs(T) + for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { + for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { + Handle value = *vt; + TypeHandle type = *it; + TypeHandle const_type = T.Constant(value); + TypeHandle nowof_type = T.NowOf(value); + CHECK(!nowof_type->NowIs(type) || const_type->NowIs(type)); + } + } + + // If Constant(V)->NowIs(T), + // then NowOf(V)->NowIs(T) or T->Maybe(Constant(V)) for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { Handle value = *vt; TypeHandle type = *it; TypeHandle const_type = T.Constant(value); TypeHandle nowof_type = T.NowOf(value); - CHECK(const_type->NowIs(type) == - (nowof_type->NowIs(type) || type->Maybe(const_type))); + CHECK(!const_type->NowIs(type) || + nowof_type->NowIs(type) || type->Maybe(const_type)); } } - // Constant(V)->Is(T) implies NowOf(V)->Is(T) or T->Maybe(Constant(V)) + // If Constant(V)->Is(T), + // then NowOf(V)->Is(T) or T->Maybe(Constant(V)) for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { Handle value = *vt; @@ -766,31 +798,47 @@ struct Tests : Rep { TypeHandle const_type = T.Constant(value); TypeHandle nowof_type = T.NowOf(value); CHECK(!const_type->Is(type) || - (nowof_type->Is(type) || type->Maybe(const_type))); + nowof_type->Is(type) || type->Maybe(const_type)); } } } - void Bounds() { - // Ordering: (T->BitsetGlb())->Is(T->BitsetLub()) + void BitsetGlb() { + // Lower: (T->BitsetGlb())->Is(T) for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { TypeHandle type = *it; TypeHandle glb = Rep::BitsetType::New(Rep::BitsetType::Glb(type), T.region()); - TypeHandle lub = - Rep::BitsetType::New(Rep::BitsetType::Lub(type), T.region()); - CHECK(glb->Is(lub)); + CHECK(glb->Is(type)); } - // Lower bound: (T->BitsetGlb())->Is(T) - for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { - TypeHandle type = *it; - TypeHandle glb = - Rep::BitsetType::New(Rep::BitsetType::Glb(type), T.region()); - CHECK(glb->Is(type)); + // Greatest: If T1->IsBitset() and T1->Is(T2), then T1->Is(T2->BitsetGlb()) + for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { + for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { + TypeHandle type1 = *it1; + TypeHandle type2 = *it2; + TypeHandle glb2 = + Rep::BitsetType::New(Rep::BitsetType::Glb(type2), T.region()); + CHECK(!this->IsBitset(type1) || !type1->Is(type2) || type1->Is(glb2)); + } + } + + // Monotonicity: T1->Is(T2) implies (T1->BitsetGlb())->Is(T2->BitsetGlb()) + for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { + for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { + TypeHandle type1 = *it1; + TypeHandle type2 = *it2; + TypeHandle glb1 = + Rep::BitsetType::New(Rep::BitsetType::Glb(type1), T.region()); + TypeHandle glb2 = + Rep::BitsetType::New(Rep::BitsetType::Glb(type2), T.region()); + CHECK(!type1->Is(type2) || glb1->Is(glb2)); + } } + } - // Upper bound: T->Is(T->BitsetLub()) + void BitsetLub() { + // Upper: T->Is(T->BitsetLub()) for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { TypeHandle type = *it; TypeHandle lub = @@ -798,14 +846,28 @@ struct Tests : Rep { CHECK(type->Is(lub)); } - // Inherent bound: (T->BitsetLub())->Is(T->InherentBitsetLub()) - for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { - TypeHandle type = *it; - TypeHandle lub = - Rep::BitsetType::New(Rep::BitsetType::Lub(type), T.region()); - TypeHandle inherent = - Rep::BitsetType::New(Rep::BitsetType::InherentLub(type), T.region()); - CHECK(lub->Is(inherent)); + // Least: If T2->IsBitset() and T1->Is(T2), then (T1->BitsetLub())->Is(T2) + for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { + for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { + TypeHandle type1 = *it1; + TypeHandle type2 = *it2; + TypeHandle lub1 = + Rep::BitsetType::New(Rep::BitsetType::Lub(type1), T.region()); + CHECK(!this->IsBitset(type2) || !type1->Is(type2) || lub1->Is(type2)); + } + } + + // Monotonicity: T1->Is(T2) implies (T1->BitsetLub())->Is(T2->BitsetLub()) + for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { + for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { + TypeHandle type1 = *it1; + TypeHandle type2 = *it2; + TypeHandle lub1 = + Rep::BitsetType::New(Rep::BitsetType::Lub(type1), T.region()); + TypeHandle lub2 = + Rep::BitsetType::New(Rep::BitsetType::Lub(type2), T.region()); + CHECK(!type1->Is(type2) || lub1->Is(lub2)); + } } } @@ -861,6 +923,17 @@ struct Tests : Rep { } } + // Class(M1)->Is(Class(M2)) iff M1 = M2 + for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) { + for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) { + Handle map1 = *mt1; + Handle map2 = *mt2; + TypeHandle class_type1 = T.Class(map1); + TypeHandle class_type2 = T.Class(map2); + CHECK(class_type1->Is(class_type2) == (*map1 == *map2)); + } + } + // Constant(V1)->Is(Constant(V2)) iff V1 = V2 for (ValueIterator vt1 = T.values.begin(); vt1 != T.values.end(); ++vt1) { for (ValueIterator vt2 = T.values.begin(); vt2 != T.values.end(); ++vt2) { @@ -872,36 +945,83 @@ struct Tests : Rep { } } - // Class(M1)->Is(Class(M2)) iff M1 = M2 - for (MapIterator mt1 = T.maps.begin(); mt1 != T.maps.end(); ++mt1) { - for (MapIterator mt2 = T.maps.begin(); mt2 != T.maps.end(); ++mt2) { - Handle map1 = *mt1; - Handle map2 = *mt2; - TypeHandle class_type1 = T.Class(map1); - TypeHandle class_type2 = T.Class(map2); - CHECK(class_type1->Is(class_type2) == (*map1 == *map2)); + // Range(min1, max1)->Is(Range(min2, max2)) iff + // min1 >= min2 /\ max1 <= max2 + for (ValueIterator i1 = T.integers.begin(); + i1 != T.integers.end(); ++i1) { + for (ValueIterator j1 = T.integers.begin(); + j1 != T.integers.end(); ++j1) { + for (ValueIterator i2 = T.integers.begin(); + i2 != T.integers.end(); ++i2) { + for (ValueIterator j2 = T.integers.begin(); + j2 != T.integers.end(); ++j2) { + i::Handle min1 = *i1; + i::Handle max1 = *j1; + i::Handle min2 = *i2; + i::Handle max2 = *j2; + if (min1->Number() > max1->Number()) std::swap(min1, max1); + if (min2->Number() > max2->Number()) std::swap(min2, max2); + TypeHandle type1 = T.Range(min1, max1); + TypeHandle type2 = T.Range(min2, max2); + CHECK(type1->Is(type2) == + (min2->Number() <= min1->Number() && + max1->Number() <= max2->Number())); + } + } } } - // Constant(V)->Is(Class(M)) never - for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) { - for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { - Handle map = *mt; - Handle value = *vt; - TypeHandle constant_type = T.Constant(value); - TypeHandle class_type = T.Class(map); - CHECK(!constant_type->Is(class_type)); + // Context(T1)->Is(Context(T2)) iff T1 = T2 + for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { + for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { + TypeHandle outer1 = *it1; + TypeHandle outer2 = *it2; + TypeHandle type1 = T.Context(outer1); + TypeHandle type2 = T.Context(outer2); + CHECK(type1->Is(type2) == outer1->Equals(outer2)); } } - // Class(M)->Is(Constant(V)) never - for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) { - for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { - Handle map = *mt; - Handle value = *vt; - TypeHandle constant_type = T.Constant(value); - TypeHandle class_type = T.Class(map); - CHECK(!class_type->Is(constant_type)); + // Array(T1)->Is(Array(T2)) iff T1 = T2 + for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { + for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { + TypeHandle element1 = *it1; + TypeHandle element2 = *it2; + TypeHandle type1 = T.Array1(element1); + TypeHandle type2 = T.Array1(element2); + CHECK(type1->Is(type2) == element1->Equals(element2)); + } + } + + // Function0(S1, T1)->Is(Function0(S2, T2)) iff S1 = S2 and T1 = T2 + for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) { + for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) { + TypeHandle result1 = *i; + TypeHandle receiver1 = *j; + TypeHandle type1 = T.Function0(result1, receiver1); + TypeHandle result2 = T.Random(); + TypeHandle receiver2 = T.Random(); + TypeHandle type2 = T.Function0(result2, receiver2); + CHECK(type1->Is(type2) == + (result1->Equals(result2) && receiver1->Equals(receiver2))); + } + } + + // (In-)Compatibilities. + for (TypeIterator i = T.types.begin(); i != T.types.end(); ++i) { + for (TypeIterator j = T.types.begin(); j != T.types.end(); ++j) { + TypeHandle type1 = *i; + TypeHandle type2 = *j; + CHECK(!type1->Is(type2) || this->IsBitset(type2) || + this->IsUnion(type2) || this->IsUnion(type1) || + (type1->IsClass() && type2->IsClass()) || + (type1->IsConstant() && type2->IsConstant()) || + (type1->IsConstant() && type2->IsRange()) || + (type1->IsRange() && type2->IsRange()) || + (type1->IsContext() && type2->IsContext()) || + (type1->IsArray() && type2->IsArray()) || + (type1->IsFunction() && type2->IsFunction()) || + type1->Equals(T.None)); } } @@ -1092,16 +1212,6 @@ struct Tests : Rep { CHECK(type->Contains(value) == const_type->Is(type)); } } - - // Of(V)->Is(T) implies T->Contains(V) - for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { - for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { - TypeHandle type = *it; - Handle value = *vt; - TypeHandle of_type = T.Of(value); - CHECK(!of_type->Is(type) || type->Contains(value)); - } - } } void NowContains() { @@ -1133,16 +1243,6 @@ struct Tests : Rep { CHECK(!nowof_type->NowIs(type) || type->NowContains(value)); } } - - // NowOf(V)->NowIs(T) implies T->NowContains(V) - for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { - for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { - TypeHandle type = *it; - Handle value = *vt; - TypeHandle nowof_type = T.Of(value); - CHECK(!nowof_type->NowIs(type) || type->NowContains(value)); - } - } } void Maybe() { @@ -1226,6 +1326,8 @@ struct Tests : Rep { } // Constant(V)->Maybe(Class(M)) never + // This does NOT hold! + /* for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) { for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { Handle map = *mt; @@ -1235,8 +1337,11 @@ struct Tests : Rep { CHECK(!const_type->Maybe(class_type)); } } + */ // Class(M)->Maybe(Constant(V)) never + // This does NOT hold! + /* for (MapIterator mt = T.maps.begin(); mt != T.maps.end(); ++mt) { for (ValueIterator vt = T.values.begin(); vt != T.values.end(); ++vt) { Handle map = *mt; @@ -1246,67 +1351,62 @@ struct Tests : Rep { CHECK(!class_type->Maybe(const_type)); } } + */ // Basic types - CheckDisjoint(T.Boolean, T.Null, T.Semantic); - CheckDisjoint(T.Undefined, T.Null, T.Semantic); - CheckDisjoint(T.Boolean, T.Undefined, T.Semantic); - - CheckOverlap(T.SignedSmall, T.Number, T.Semantic); - CheckOverlap(T.NaN, T.Number, T.Semantic); - CheckDisjoint(T.Signed32, T.NaN, T.Semantic); - - CheckOverlap(T.UniqueName, T.Name, T.Semantic); - CheckOverlap(T.String, T.Name, T.Semantic); - CheckOverlap(T.InternalizedString, T.String, T.Semantic); - CheckOverlap(T.InternalizedString, T.UniqueName, T.Semantic); - CheckOverlap(T.InternalizedString, T.Name, T.Semantic); - CheckOverlap(T.Symbol, T.UniqueName, T.Semantic); - CheckOverlap(T.Symbol, T.Name, T.Semantic); - CheckOverlap(T.String, T.UniqueName, T.Semantic); - CheckDisjoint(T.String, T.Symbol, T.Semantic); - CheckDisjoint(T.InternalizedString, T.Symbol, T.Semantic); - - CheckOverlap(T.Object, T.Receiver, T.Semantic); - CheckOverlap(T.Array, T.Object, T.Semantic); - CheckOverlap(T.Function, T.Object, T.Semantic); - CheckOverlap(T.Proxy, T.Receiver, T.Semantic); - CheckDisjoint(T.Object, T.Proxy, T.Semantic); - CheckDisjoint(T.Array, T.Function, T.Semantic); + CheckDisjoint(T.Boolean, T.Null); + CheckDisjoint(T.Undefined, T.Null); + CheckDisjoint(T.Boolean, T.Undefined); + CheckOverlap(T.SignedSmall, T.Number); + CheckOverlap(T.NaN, T.Number); + CheckDisjoint(T.Signed32, T.NaN); + CheckOverlap(T.UniqueName, T.Name); + CheckOverlap(T.String, T.Name); + CheckOverlap(T.InternalizedString, T.String); + CheckOverlap(T.InternalizedString, T.UniqueName); + CheckOverlap(T.InternalizedString, T.Name); + CheckOverlap(T.Symbol, T.UniqueName); + CheckOverlap(T.Symbol, T.Name); + CheckOverlap(T.String, T.UniqueName); + CheckDisjoint(T.String, T.Symbol); + CheckDisjoint(T.InternalizedString, T.Symbol); + CheckOverlap(T.Object, T.Receiver); + CheckOverlap(T.Array, T.Object); + CheckOverlap(T.Function, T.Object); + CheckOverlap(T.Proxy, T.Receiver); + CheckDisjoint(T.Object, T.Proxy); + CheckDisjoint(T.Array, T.Function); // Structural types - CheckOverlap(T.ObjectClass, T.Object, T.Semantic); - CheckOverlap(T.ArrayClass, T.Object, T.Semantic); - CheckOverlap(T.ObjectClass, T.ObjectClass, T.Semantic); - CheckOverlap(T.ArrayClass, T.ArrayClass, T.Semantic); - CheckDisjoint(T.ObjectClass, T.ArrayClass, T.Semantic); - - CheckOverlap(T.SmiConstant, T.SignedSmall, T.Semantic); - CheckOverlap(T.SmiConstant, T.Signed32, T.Semantic); - CheckOverlap(T.SmiConstant, T.Number, T.Semantic); - CheckOverlap(T.ObjectConstant1, T.Object, T.Semantic); - CheckOverlap(T.ObjectConstant2, T.Object, T.Semantic); - CheckOverlap(T.ArrayConstant, T.Object, T.Semantic); - CheckOverlap(T.ArrayConstant, T.Array, T.Semantic); - CheckOverlap(T.ObjectConstant1, T.ObjectConstant1, T.Semantic); - CheckDisjoint(T.ObjectConstant1, T.ObjectConstant2, T.Semantic); - CheckDisjoint(T.ObjectConstant1, T.ArrayConstant, T.Semantic); - - CheckDisjoint(T.ObjectConstant1, T.ObjectClass, T.Semantic); - CheckDisjoint(T.ObjectConstant2, T.ObjectClass, T.Semantic); - CheckDisjoint(T.ObjectConstant1, T.ArrayClass, T.Semantic); - CheckDisjoint(T.ObjectConstant2, T.ArrayClass, T.Semantic); - CheckDisjoint(T.ArrayConstant, T.ObjectClass, T.Semantic); - - CheckOverlap(T.NumberArray, T.Array, T.Semantic); - CheckDisjoint(T.NumberArray, T.AnyArray, T.Semantic); - CheckDisjoint(T.NumberArray, T.StringArray, T.Semantic); - - CheckOverlap(T.MethodFunction, T.Function, T.Semantic); - CheckDisjoint(T.SignedFunction1, T.NumberFunction1, T.Semantic); - CheckDisjoint(T.SignedFunction1, T.NumberFunction2, T.Semantic); - CheckDisjoint(T.NumberFunction1, T.NumberFunction2, T.Semantic); - CheckDisjoint(T.SignedFunction1, T.MethodFunction, T.Semantic); + CheckOverlap(T.ObjectClass, T.Object); + CheckOverlap(T.ArrayClass, T.Object); + CheckOverlap(T.ObjectClass, T.ObjectClass); + CheckOverlap(T.ArrayClass, T.ArrayClass); + CheckDisjoint(T.ObjectClass, T.ArrayClass); + CheckOverlap(T.SmiConstant, T.SignedSmall); + CheckOverlap(T.SmiConstant, T.Signed32); + CheckOverlap(T.SmiConstant, T.Number); + CheckOverlap(T.ObjectConstant1, T.Object); + CheckOverlap(T.ObjectConstant2, T.Object); + CheckOverlap(T.ArrayConstant, T.Object); + CheckOverlap(T.ArrayConstant, T.Array); + CheckOverlap(T.ObjectConstant1, T.ObjectConstant1); + CheckDisjoint(T.ObjectConstant1, T.ObjectConstant2); + CheckDisjoint(T.ObjectConstant1, T.ArrayConstant); + CheckDisjoint(T.ObjectConstant1, T.ArrayClass); + CheckDisjoint(T.ObjectConstant2, T.ArrayClass); + CheckDisjoint(T.ArrayConstant, T.ObjectClass); + CheckOverlap(T.NumberArray, T.Array); + CheckDisjoint(T.NumberArray, T.AnyArray); + CheckDisjoint(T.NumberArray, T.StringArray); + CheckOverlap(T.MethodFunction, T.Function); + CheckDisjoint(T.SignedFunction1, T.NumberFunction1); + CheckDisjoint(T.SignedFunction1, T.NumberFunction2); + CheckDisjoint(T.NumberFunction1, T.NumberFunction2); + CheckDisjoint(T.SignedFunction1, T.MethodFunction); + CheckOverlap(T.ObjectConstant1, T.ObjectClass); // !!! + CheckOverlap(T.ObjectConstant2, T.ObjectClass); // !!! + CheckOverlap(T.NumberClass, T.Intersect(T.Number, T.Untagged)); // !!! } void Union1() { @@ -1343,6 +1443,8 @@ struct Tests : Rep { } // Associativity: Union(T1, Union(T2, T3)) = Union(Union(T1, T2), T3) + // This does NOT hold! + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) { @@ -1357,6 +1459,7 @@ struct Tests : Rep { } } } + */ // Meet: T1->Is(Union(T1, T2)) and T2->Is(Union(T1, T2)) for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { @@ -1378,10 +1481,10 @@ struct Tests : Rep { if (type1->Is(type2)) CheckEqual(union12, type2); } } - } - void Union2() { // Monotonicity: T1->Is(T2) implies Union(T1, T3)->Is(Union(T2, T3)) + // This does NOT hold. + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) { @@ -1394,8 +1497,14 @@ struct Tests : Rep { } } } + */ + } + void Union2() { // Monotonicity: T1->Is(T3) and T2->Is(T3) implies Union(T1, T2)->Is(T3) + // This does NOT hold. TODO(neis): Could fix this by splitting + // OtherNumber into a negative and a positive part. + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) { @@ -1407,7 +1516,10 @@ struct Tests : Rep { } } } + */ + } + void Union3() { // Monotonicity: T1->Is(T2) or T1->Is(T3) implies T1->Is(Union(T2, T3)) for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { @@ -1420,12 +1532,14 @@ struct Tests : Rep { } } } + } + void Union4() { // Class-class CheckSub(T.Union(T.ObjectClass, T.ArrayClass), T.Object); CheckUnordered(T.Union(T.ObjectClass, T.ArrayClass), T.Array); - CheckOverlap(T.Union(T.ObjectClass, T.ArrayClass), T.Array, T.Semantic); - CheckDisjoint(T.Union(T.ObjectClass, T.ArrayClass), T.Number, T.Semantic); + CheckOverlap(T.Union(T.ObjectClass, T.ArrayClass), T.Array); + CheckDisjoint(T.Union(T.ObjectClass, T.ArrayClass), T.Number); // Constant-constant CheckSub(T.Union(T.ObjectConstant1, T.ObjectConstant2), T.Object); @@ -1433,11 +1547,11 @@ struct Tests : Rep { CheckUnordered( T.Union(T.ObjectConstant1, T.ObjectConstant2), T.ObjectClass); CheckOverlap( - T.Union(T.ObjectConstant1, T.ArrayConstant), T.Array, T.Semantic); + T.Union(T.ObjectConstant1, T.ArrayConstant), T.Array); CheckDisjoint( - T.Union(T.ObjectConstant1, T.ArrayConstant), T.Number, T.Semantic); - CheckDisjoint( - T.Union(T.ObjectConstant1, T.ArrayConstant), T.ObjectClass, T.Semantic); + T.Union(T.ObjectConstant1, T.ArrayConstant), T.Number); + CheckOverlap( + T.Union(T.ObjectConstant1, T.ArrayConstant), T.ObjectClass); // !!! // Bitset-array CHECK(this->IsBitset(T.Union(T.AnyArray, T.Array))); @@ -1445,8 +1559,8 @@ struct Tests : Rep { CheckEqual(T.Union(T.AnyArray, T.Array), T.Array); CheckUnordered(T.Union(T.AnyArray, T.String), T.Array); - CheckOverlap(T.Union(T.NumberArray, T.String), T.Object, T.Semantic); - CheckDisjoint(T.Union(T.NumberArray, T.String), T.Number, T.Semantic); + CheckOverlap(T.Union(T.NumberArray, T.String), T.Object); + CheckDisjoint(T.Union(T.NumberArray, T.String), T.Number); // Bitset-function CHECK(this->IsBitset(T.Union(T.MethodFunction, T.Function))); @@ -1454,24 +1568,24 @@ struct Tests : Rep { CheckEqual(T.Union(T.MethodFunction, T.Function), T.Function); CheckUnordered(T.Union(T.NumberFunction1, T.String), T.Function); - CheckOverlap(T.Union(T.NumberFunction2, T.String), T.Object, T.Semantic); - CheckDisjoint(T.Union(T.NumberFunction1, T.String), T.Number, T.Semantic); + CheckOverlap(T.Union(T.NumberFunction2, T.String), T.Object); + CheckDisjoint(T.Union(T.NumberFunction1, T.String), T.Number); // Bitset-class CheckSub( T.Union(T.ObjectClass, T.SignedSmall), T.Union(T.Object, T.Number)); CheckSub(T.Union(T.ObjectClass, T.Array), T.Object); CheckUnordered(T.Union(T.ObjectClass, T.String), T.Array); - CheckOverlap(T.Union(T.ObjectClass, T.String), T.Object, T.Semantic); - CheckDisjoint(T.Union(T.ObjectClass, T.String), T.Number, T.Semantic); + CheckOverlap(T.Union(T.ObjectClass, T.String), T.Object); + CheckDisjoint(T.Union(T.ObjectClass, T.String), T.Number); // Bitset-constant CheckSub( T.Union(T.ObjectConstant1, T.Signed32), T.Union(T.Object, T.Number)); CheckSub(T.Union(T.ObjectConstant1, T.Array), T.Object); CheckUnordered(T.Union(T.ObjectConstant1, T.String), T.Array); - CheckOverlap(T.Union(T.ObjectConstant1, T.String), T.Object, T.Semantic); - CheckDisjoint(T.Union(T.ObjectConstant1, T.String), T.Number, T.Semantic); + CheckOverlap(T.Union(T.ObjectConstant1, T.String), T.Object); + CheckDisjoint(T.Union(T.ObjectConstant1, T.String), T.Number); // Class-constant CheckSub(T.Union(T.ObjectConstant1, T.ArrayClass), T.Object); @@ -1480,10 +1594,9 @@ struct Tests : Rep { T.Union(T.ObjectConstant1, T.ArrayClass), T.Union(T.Array, T.Object)); CheckUnordered(T.Union(T.ObjectConstant1, T.ArrayClass), T.ArrayConstant); CheckDisjoint( - T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectConstant2, - T.Semantic); - CheckDisjoint( - T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectClass, T.Semantic); + T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectConstant2); + CheckOverlap( + T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectClass); // !!! // Bitset-union CheckSub( @@ -1537,7 +1650,7 @@ struct Tests : Rep { T.Union(T.Number, T.Array)); } - void Intersect1() { + void Intersect() { // Identity: Intersect(T, Any) = T for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) { TypeHandle type = *it; @@ -1572,6 +1685,8 @@ struct Tests : Rep { // Associativity: // Intersect(T1, Intersect(T2, T3)) = Intersect(Intersect(T1, T2), T3) + // This does NOT hold. + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) { @@ -1586,8 +1701,11 @@ struct Tests : Rep { } } } + */ // Join: Intersect(T1, T2)->Is(T1) and Intersect(T1, T2)->Is(T2) + // This does NOT hold. Not even the disjunction. + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { TypeHandle type1 = *it1; @@ -1597,6 +1715,7 @@ struct Tests : Rep { CHECK(intersect12->Is(type2)); } } + */ // Lower Boundedness: T1->Is(T2) implies Intersect(T1, T2) = T1 for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { @@ -1607,10 +1726,10 @@ struct Tests : Rep { if (type1->Is(type2)) CheckEqual(intersect12, type1); } } - } - void Intersect2() { // Monotonicity: T1->Is(T2) implies Intersect(T1, T3)->Is(Intersect(T2, T3)) + // This does NOT hold. + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) { @@ -1623,8 +1742,11 @@ struct Tests : Rep { } } } + */ // Monotonicity: T1->Is(T3) or T2->Is(T3) implies Intersect(T1, T2)->Is(T3) + // This does NOT hold. + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) { @@ -1637,8 +1759,11 @@ struct Tests : Rep { } } } + */ // Monotonicity: T1->Is(T2) and T1->Is(T3) implies T1->Is(Intersect(T2, T3)) + // This does NOT hold. + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) { @@ -1651,19 +1776,20 @@ struct Tests : Rep { } } } + */ // Bitset-class CheckEqual(T.Intersect(T.ObjectClass, T.Object), T.ObjectClass); - CheckSub(T.Intersect(T.ObjectClass, T.Array), T.Representation); - CheckSub(T.Intersect(T.ObjectClass, T.Number), T.Representation); + CheckEqual(T.Intersect(T.ObjectClass, T.Array), T.None); + CheckEqual(T.Intersect(T.ObjectClass, T.Number), T.None); // Bitset-array CheckEqual(T.Intersect(T.NumberArray, T.Object), T.NumberArray); - CheckSub(T.Intersect(T.AnyArray, T.Function), T.Representation); + CheckEqual(T.Intersect(T.AnyArray, T.Function), T.None); // Bitset-function CheckEqual(T.Intersect(T.MethodFunction, T.Object), T.MethodFunction); - CheckSub(T.Intersect(T.NumberFunction1, T.Array), T.Representation); + CheckEqual(T.Intersect(T.NumberFunction1, T.Array), T.None); // Bitset-union CheckEqual( @@ -1674,7 +1800,7 @@ struct Tests : Rep { ->IsInhabited()); // Class-constant - CHECK(!T.Intersect(T.ObjectConstant1, T.ObjectClass)->IsInhabited()); + CHECK(T.Intersect(T.ObjectConstant1, T.ObjectClass)->IsInhabited()); // !!! CHECK(!T.Intersect(T.ArrayClass, T.ObjectConstant2)->IsInhabited()); // Array-union @@ -1707,8 +1833,8 @@ struct Tests : Rep { T.Intersect(T.ArrayClass, T.Union(T.Object, T.SmiConstant)), T.ArrayClass); CHECK( - !T.Intersect(T.Union(T.ObjectClass, T.ArrayConstant), T.ArrayClass) - ->IsInhabited()); + T.Intersect(T.Union(T.ObjectClass, T.ArrayConstant), T.ArrayClass) + ->IsInhabited()); // !!! // Constant-union CheckEqual( @@ -1719,9 +1845,9 @@ struct Tests : Rep { T.Intersect(T.SmiConstant, T.Union(T.Number, T.ObjectConstant2)), T.SmiConstant); CHECK( - !T.Intersect( + T.Intersect( T.Union(T.ArrayConstant, T.ObjectClass), T.ObjectConstant1) - ->IsInhabited()); + ->IsInhabited()); // !!! // Union-union CheckEqual( @@ -1742,16 +1868,20 @@ struct Tests : Rep { CheckEqual( T.Intersect( T.Union( - T.Union(T.ObjectConstant2, T.ObjectConstant1), T.ArrayClass), + T.ArrayClass, + T.Union(T.ObjectConstant2, T.ObjectConstant1)), T.Union( T.ObjectConstant1, T.Union(T.ArrayConstant, T.ObjectConstant2))), - T.Union(T.ObjectConstant2, T.ObjectConstant1)); + T.Union( + T.ArrayConstant, + T.Union(T.ObjectConstant2, T.ObjectConstant1))); // !!! } - void Distributivity1() { - // Distributivity: + void Distributivity() { // Union(T1, Intersect(T2, T3)) = Intersect(Union(T1, T2), Union(T1, T3)) + // This does NOT hold. + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) { @@ -1767,11 +1897,11 @@ struct Tests : Rep { } } } - } + */ - void Distributivity2() { - // Distributivity: // Intersect(T1, Union(T2, T3)) = Union(Intersect(T1, T2), Intersect(T1,T3)) + // This does NOT hold. + /* for (TypeIterator it1 = T.types.begin(); it1 != T.types.end(); ++it1) { for (TypeIterator it2 = T.types.begin(); it2 != T.types.end(); ++it2) { for (TypeIterator it3 = T.types.begin(); it3 != T.types.end(); ++it3) { @@ -1787,6 +1917,7 @@ struct Tests : Rep { } } } + */ } template @@ -1818,6 +1949,13 @@ typedef Tests ZoneTests; typedef Tests, Isolate, HeapRep> HeapTests; +TEST(IsSomeType) { + CcTest::InitializeVM(); + ZoneTests().IsSomeType(); + HeapTests().IsSomeType(); +} + + TEST(BitsetType) { CcTest::InitializeVM(); ZoneTests().Bitset(); @@ -1874,10 +2012,17 @@ TEST(NowOf) { } -TEST(Bounds) { +TEST(BitsetGlb) { CcTest::InitializeVM(); - ZoneTests().Bounds(); - HeapTests().Bounds(); + ZoneTests().BitsetGlb(); + HeapTests().BitsetGlb(); +} + + +TEST(BitsetLub) { + CcTest::InitializeVM(); + ZoneTests().BitsetLub(); + HeapTests().BitsetLub(); } @@ -1916,8 +2061,6 @@ TEST(Maybe) { } -// TODO(rossberg): make me faster! -#if 0 TEST(Union1) { CcTest::InitializeVM(); ZoneTests().Union1(); @@ -1925,40 +2068,44 @@ TEST(Union1) { } +/* TEST(Union2) { CcTest::InitializeVM(); ZoneTests().Union2(); HeapTests().Union2(); } +*/ -TEST(Intersect1) { +TEST(Union3) { CcTest::InitializeVM(); - ZoneTests().Intersect1(); - HeapTests().Intersect1(); + ZoneTests().Union3(); + HeapTests().Union3(); } -TEST(Intersect2) { +TEST(Union4) { CcTest::InitializeVM(); - ZoneTests().Intersect2(); - HeapTests().Intersect2(); + ZoneTests().Union4(); + HeapTests().Union4(); } -TEST(Distributivity1) { +TEST(Intersect) { CcTest::InitializeVM(); - ZoneTests().Distributivity1(); - HeapTests().Distributivity1(); + ZoneTests().Intersect(); + HeapTests().Intersect(); } -TEST(Distributivity2) { +/* +TEST(Distributivity) { CcTest::InitializeVM(); - ZoneTests().Distributivity2(); - HeapTests().Distributivity2(); + ZoneTests().Distributivity(); + HeapTests().Distributivity(); } -#endif // TODO(rossberg): make me faster +*/ + TEST(Convert) { CcTest::InitializeVM(); -- 2.7.4