From 68cc8da20cb8ca9a8fb4fa3f956b502515c8ee5f Mon Sep 17 00:00:00 2001 From: "rossberg@chromium.org" Date: Fri, 11 Oct 2013 15:17:58 +0000 Subject: [PATCH] Ensure lower <= upper bound R=jkummerow@chromium.org BUG= Review URL: https://codereview.chromium.org/26959004 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@17167 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/types.cc | 9 +++++++-- src/types.h | 31 +++++++++++++++++++++++-------- src/typing.cc | 23 ++++++++++++++--------- test/cctest/test-types.cc | 25 +++++++++++++++++++++++++ 4 files changed, 69 insertions(+), 19 deletions(-) diff --git a/src/types.cc b/src/types.cc index 9716686..17a19b2 100644 --- a/src/types.cc +++ b/src/types.cc @@ -240,6 +240,7 @@ int Type::GlbBitset() { // Check this <= that. bool Type::SlowIs(Type* that) { // Fast path for bitsets. + if (this->is_none()) return true; if (that->is_bitset()) { return (this->LubBitset() | that->as_bitset()) == that->as_bitset(); } @@ -526,9 +527,13 @@ void Type::TypePrint(FILE* out) { } PrintF(out, "}"); } else if (is_constant()) { - PrintF(out, "Constant(%p)", static_cast(*as_constant())); + PrintF(out, "Constant(%p : ", static_cast(*as_constant())); + from_bitset(LubBitset())->TypePrint(out); + PrintF(")"); } else if (is_class()) { - PrintF(out, "Class(%p)", static_cast(*as_class())); + PrintF(out, "Class(%p < ", static_cast(*as_class())); + from_bitset(LubBitset())->TypePrint(out); + PrintF(")"); } else if (is_union()) { PrintF(out, "{"); Handle unioned = as_union(); diff --git a/src/types.h b/src/types.h index 80772d8..5d437e2 100644 --- a/src/types.h +++ b/src/types.h @@ -226,6 +226,7 @@ class Type : public Object { kUnusedEOL = 0 }; + bool is_none() { return this == None(); } bool is_bitset() { return this->IsSmi(); } bool is_class() { return this->IsMap(); } bool is_constant() { return this->IsBox(); } @@ -299,10 +300,18 @@ struct Bounds { Handle upper; Bounds() {} - Bounds(Handle l, Handle u) : lower(l), upper(u) {} - Bounds(Type* l, Type* u, Isolate* isl) : lower(l, isl), upper(u, isl) {} - explicit Bounds(Handle t) : lower(t), upper(t) {} - Bounds(Type* t, Isolate* isl) : lower(t, isl), upper(t, isl) {} + Bounds(Handle l, Handle u) : lower(l), upper(u) { + ASSERT(lower->Is(upper)); + } + Bounds(Type* l, Type* u, Isolate* isl) : lower(l, isl), upper(u, isl) { + ASSERT(lower->Is(upper)); + } + explicit Bounds(Handle t) : lower(t), upper(t) { + ASSERT(lower->Is(upper)); + } + Bounds(Type* t, Isolate* isl) : lower(t, isl), upper(t, isl) { + ASSERT(lower->Is(upper)); + } // Unrestricted bounds. static Bounds Unbounded(Isolate* isl) { @@ -311,9 +320,11 @@ struct Bounds { // Meet: both b1 and b2 are known to hold. static Bounds Both(Bounds b1, Bounds b2, Isolate* isl) { - return Bounds( - handle(Type::Union(b1.lower, b2.lower), isl), - handle(Type::Intersect(b1.upper, b2.upper), isl)); + Handle lower(Type::Union(b1.lower, b2.lower), isl); + Handle upper(Type::Intersect(b1.upper, b2.upper), isl); + // Lower bounds are considered approximate, correct as necessary. + lower = handle(Type::Intersect(lower, upper), isl); + return Bounds(lower, upper); } // Join: either b1 or b2 is known to hold. @@ -324,10 +335,14 @@ struct Bounds { } static Bounds NarrowLower(Bounds b, Handle t, Isolate* isl) { + // Lower bounds are considered approximate, correct as necessary. + t = handle(Type::Intersect(t, b.upper), isl); return Bounds(handle(Type::Union(b.lower, t), isl), b.upper); } static Bounds NarrowUpper(Bounds b, Handle t, Isolate* isl) { - return Bounds(b.lower, handle(Type::Intersect(b.upper, t), isl)); + return Bounds( + handle(Type::Intersect(b.lower, t), isl), + handle(Type::Intersect(b.upper, t), isl)); } }; diff --git a/src/typing.cc b/src/typing.cc index e9da680..01c395c 100644 --- a/src/typing.cc +++ b/src/typing.cc @@ -247,8 +247,8 @@ void AstTyper::VisitForStatement(ForStatement* stmt) { RECURSE(Visit(stmt->cond())); } RECURSE(Visit(stmt->body())); - store_.Forget(); // Control may transfer here via 'continue'. if (stmt->next() != NULL) { + store_.Forget(); // Control may transfer here via 'continue'. RECURSE(Visit(stmt->next())); } store_.Forget(); // Control may transfer here via termination or 'break'. @@ -580,7 +580,9 @@ void AstTyper::VisitBinaryOperation(BinaryOperation* expr) { Type* upper = Type::Union( expr->left()->bounds().upper, expr->right()->bounds().upper); if (!upper->Is(Type::Signed32())) upper = Type::Signed32(); - NarrowType(expr, Bounds(Type::Smi(), upper, isolate_)); + Type* lower = Type::Intersect( + handle(Type::Smi(), isolate_), handle(upper, isolate_)); + NarrowType(expr, Bounds(lower, upper, isolate_)); break; } case Token::BIT_XOR: @@ -593,7 +595,8 @@ void AstTyper::VisitBinaryOperation(BinaryOperation* expr) { case Token::SHR: RECURSE(Visit(expr->left())); RECURSE(Visit(expr->right())); - NarrowType(expr, Bounds(Type::Smi(), Type::Unsigned32(), isolate_)); + // TODO(rossberg): we could use an UnsignedSmi as lower bound here... + NarrowType(expr, Bounds(Type::Unsigned32(), isolate_)); break; case Token::ADD: { RECURSE(Visit(expr->left())); @@ -601,15 +604,17 @@ void AstTyper::VisitBinaryOperation(BinaryOperation* expr) { Bounds l = expr->left()->bounds(); Bounds r = expr->right()->bounds(); Type* lower = - l.lower->Is(Type::Number()) && r.lower->Is(Type::Number()) ? - Type::Smi() : + l.lower->Is(Type::None()) || r.lower->Is(Type::None()) ? + Type::None() : l.lower->Is(Type::String()) || r.lower->Is(Type::String()) ? - Type::String() : Type::None(); + Type::String() : + l.lower->Is(Type::Number()) && r.lower->Is(Type::Number()) ? + Type::Smi() : Type::None(); Type* upper = - l.upper->Is(Type::Number()) && r.upper->Is(Type::Number()) ? - Type::Number() : l.upper->Is(Type::String()) || r.upper->Is(Type::String()) ? - Type::String() : Type::NumberOrString(); + Type::String() : + l.upper->Is(Type::Number()) && r.upper->Is(Type::Number()) ? + Type::Number() : Type::NumberOrString(); NarrowType(expr, Bounds(lower, upper, isolate_)); break; } diff --git a/test/cctest/test-types.cc b/test/cctest/test-types.cc index 823af0b..264d2ed 100644 --- a/test/cctest/test-types.cc +++ b/test/cctest/test-types.cc @@ -318,6 +318,11 @@ TEST(Is) { CheckUnordered(T.Array, T.Function); // Structured subtyping + CheckSub(T.None, T.ObjectClass); + CheckSub(T.None, T.ObjectConstant1); + CheckSub(T.ObjectClass, T.Any); + CheckSub(T.ObjectConstant1, T.Any); + CheckSub(T.ObjectClass, T.Object); CheckSub(T.ArrayClass, T.Object); CheckUnordered(T.ObjectClass, T.ArrayClass); @@ -384,6 +389,9 @@ TEST(Maybe) { CheckDisjoint(T.Object, T.Proxy); CheckDisjoint(T.Array, T.Function); + CheckOverlap(T.ObjectClass, T.Any); + CheckOverlap(T.ObjectConstant1, T.Any); + CheckOverlap(T.ObjectClass, T.Object); CheckOverlap(T.ArrayClass, T.Object); CheckOverlap(T.ObjectClass, T.ObjectClass); @@ -432,6 +440,8 @@ TEST(Union) { CHECK(IsUnion(Type::Union(T.ObjectClass, T.ArrayClass))); CheckEqual(T.Union(T.ObjectClass, T.ObjectClass), T.ObjectClass); + CheckSub(T.None, T.Union(T.ObjectClass, T.ArrayClass)); + CheckSub(T.Union(T.ObjectClass, T.ArrayClass), T.Any); CheckSub(T.ObjectClass, T.Union(T.ObjectClass, T.ArrayClass)); CheckSub(T.ArrayClass, T.Union(T.ObjectClass, T.ArrayClass)); CheckSub(T.Union(T.ObjectClass, T.ArrayClass), T.Object); @@ -447,6 +457,8 @@ TEST(Union) { CheckEqual(T.Union(T.ObjectConstant1, T.ObjectConstant1), T.ObjectConstant1); CheckEqual(T.Union(T.ArrayConstant1, T.ArrayConstant1), T.ArrayConstant1); CheckEqual(T.Union(T.ArrayConstant1, T.ArrayConstant1), T.ArrayConstant2); + CheckSub(T.None, T.Union(T.ObjectConstant1, T.ObjectConstant2)); + CheckSub(T.Union(T.ObjectConstant1, T.ObjectConstant2), T.Any); CheckSub(T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)); CheckSub(T.ObjectConstant2, T.Union(T.ObjectConstant1, T.ObjectConstant2)); CheckSub(T.ArrayConstant2, T.Union(T.ArrayConstant1, T.ObjectConstant2)); @@ -463,6 +475,7 @@ TEST(Union) { CHECK(IsUnion(Type::Union(T.ObjectClass, T.Number))); CheckEqual(T.Union(T.ObjectClass, T.Object), T.Object); + CheckSub(T.None, T.Union(T.ObjectClass, T.Number)); CheckSub(T.Union(T.ObjectClass, T.Number), T.Any); CheckSub(T.Union(T.ObjectClass, T.Smi), T.Union(T.Object, T.Number)); CheckSub(T.Union(T.ObjectClass, T.Array), T.Object); @@ -477,6 +490,7 @@ TEST(Union) { CheckEqual(T.Union(T.SmiConstant, T.Number), T.Number); CheckEqual(T.Union(T.ObjectConstant1, T.Object), T.Object); + CheckSub(T.None, T.Union(T.ObjectConstant1, T.Number)); CheckSub(T.Union(T.ObjectConstant1, T.Number), T.Any); CheckSub(T.Union(T.ObjectConstant1, T.Signed32), T.Union(T.Object, T.Number)); CheckSub(T.Union(T.ObjectConstant1, T.Array), T.Object); @@ -489,6 +503,8 @@ TEST(Union) { CHECK(IsUnion(Type::Union(T.ObjectConstant1, T.ObjectClass))); CHECK(IsUnion(Type::Union(T.ArrayClass, T.ObjectConstant2))); + CheckSub(T.None, T.Union(T.ObjectConstant1, T.ArrayClass)); + CheckSub(T.Union(T.ObjectConstant1, T.ArrayClass), T.Any); CheckSub(T.Union(T.ObjectConstant1, T.ArrayClass), T.Object); CheckSub(T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ArrayClass)); CheckSub(T.ArrayClass, T.Union(T.ObjectConstant1, T.ArrayClass)); @@ -518,6 +534,9 @@ TEST(Union) { T.ObjectConstant1, T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Double)); CheckSub( + T.None, + T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Double)); + CheckSub( T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Double), T.Any); CheckSub( @@ -534,6 +553,12 @@ TEST(Union) { T.Union(T.ObjectClass, T.Union(T.ObjectConstant1, T.ObjectClass)), T.Union(T.ObjectClass, T.ObjectConstant1)); CheckSub( + T.None, + T.Union(T.ObjectClass, T.Union(T.ObjectConstant1, T.ObjectClass))); + CheckSub( + T.Union(T.ObjectClass, T.Union(T.ObjectConstant1, T.ObjectClass)), + T.Any); + CheckSub( T.Union(T.ObjectClass, T.Union(T.ObjectConstant1, T.ObjectClass)), T.Object); CheckEqual( -- 2.7.4