From 9e8279e9529b0fcfcf030f4901f2ac6dee02bea3 Mon Sep 17 00:00:00 2001 From: "rossberg@chromium.org" Date: Wed, 5 Jun 2013 15:43:53 +0000 Subject: [PATCH] New unified type representation Not used yet, only unit tests. R=jkummerow@chromium.org, svenpanne@chromium.org BUG= Review URL: https://codereview.chromium.org/16154027 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@14957 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/handles.h | 2 +- src/types.cc | 281 +++++++++++++++++++++++++ src/types.h | 200 ++++++++++++++++++ src/typing.cc | 1 - test/cctest/cctest.gyp | 1 + test/cctest/test-types.cc | 521 ++++++++++++++++++++++++++++++++++++++++++++++ tools/gyp/v8.gyp | 2 + 7 files changed, 1006 insertions(+), 2 deletions(-) create mode 100644 src/types.cc create mode 100644 src/types.h create mode 100644 test/cctest/test-types.cc diff --git a/src/handles.h b/src/handles.h index e08a775..0cd4f5b 100644 --- a/src/handles.h +++ b/src/handles.h @@ -61,7 +61,7 @@ class Handle { location_ = reinterpret_cast(handle.location_); } - INLINE(T* operator ->() const) { return operator*(); } + INLINE(T* operator->() const) { return operator*(); } // Check if this handle refers to the exact same object as the other handle. INLINE(bool is_identical_to(const Handle other) const); diff --git a/src/types.cc b/src/types.cc new file mode 100644 index 0000000..2a96055 --- /dev/null +++ b/src/types.cc @@ -0,0 +1,281 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "types.h" + +namespace v8 { +namespace internal { + +// Get the smallest bitset subsuming this type. +int Type::LubBitset() { + if (this->is_bitset()) { + return this->as_bitset(); + } else if (this->is_union()) { + Handle unioned = this->as_union(); + int bitset = kNone; + for (int i = 0; i < unioned->length(); ++i) { + bitset |= union_get(unioned, i)->LubBitset(); + } + return bitset; + } else { + Map* map = + this->is_class() ? *this->as_class() : this->as_constant()->map(); + switch (map->instance_type()) { + case STRING_TYPE: + case ASCII_STRING_TYPE: + case CONS_STRING_TYPE: + case CONS_ASCII_STRING_TYPE: + case SLICED_STRING_TYPE: + case EXTERNAL_STRING_TYPE: + case EXTERNAL_ASCII_STRING_TYPE: + case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: + case SHORT_EXTERNAL_STRING_TYPE: + case SHORT_EXTERNAL_ASCII_STRING_TYPE: + case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: + case INTERNALIZED_STRING_TYPE: + case ASCII_INTERNALIZED_STRING_TYPE: + case CONS_INTERNALIZED_STRING_TYPE: + case CONS_ASCII_INTERNALIZED_STRING_TYPE: + case EXTERNAL_INTERNALIZED_STRING_TYPE: + case EXTERNAL_ASCII_INTERNALIZED_STRING_TYPE: + case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: + case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE: + case SHORT_EXTERNAL_ASCII_INTERNALIZED_STRING_TYPE: + case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: + return kString; + case SYMBOL_TYPE: + return kSymbol; + case ODDBALL_TYPE: + return kOddball; + case HEAP_NUMBER_TYPE: + return kDouble; + case JS_VALUE_TYPE: + case JS_DATE_TYPE: + case JS_OBJECT_TYPE: + case JS_CONTEXT_EXTENSION_OBJECT_TYPE: + case JS_GENERATOR_OBJECT_TYPE: + case JS_MODULE_TYPE: + case JS_GLOBAL_OBJECT_TYPE: + case JS_BUILTINS_OBJECT_TYPE: + case JS_GLOBAL_PROXY_TYPE: + case JS_ARRAY_BUFFER_TYPE: + case JS_TYPED_ARRAY_TYPE: + case JS_WEAK_MAP_TYPE: + case JS_REGEXP_TYPE: + return kOtherObject; + case JS_ARRAY_TYPE: + return kArray; + case JS_FUNCTION_TYPE: + return kFunction; + case JS_PROXY_TYPE: + case JS_FUNCTION_PROXY_TYPE: + return kProxy; + default: + UNREACHABLE(); + return kNone; + } + } +} + + +// Get the largest bitset subsumed by this type. +int Type::GlbBitset() { + if (this->is_bitset()) { + return this->as_bitset(); + } else if (this->is_union()) { + // All but the first are non-bitsets and thus would yield kNone anyway. + return union_get(this->as_union(), 0)->GlbBitset(); + } else { + return kNone; + } +} + + +// Check this <= that. +bool Type::Is(Handle that) { + // Fast path for bitsets. + if (that->is_bitset()) { + return (this->LubBitset() | that->as_bitset()) == that->as_bitset(); + } + + if (that->is_class()) { + return this->is_class() && *this->as_class() == *that->as_class(); + } + if (that->is_constant()) { + return this->is_constant() && *this->as_constant() == *that->as_constant(); + } + + // (T1 \/ ... \/ Tn) <= T <=> (T1 <= T) /\ ... /\ (Tn <= T) + if (this->is_union()) { + Handle unioned = this->as_union(); + for (int i = 0; i < unioned->length(); ++i) { + Handle this_i = union_get(unioned, i); + if (!this_i->Is(that)) return false; + } + return true; + } + + // T <= (T1 \/ ... \/ Tn) <=> (T <= T1) \/ ... \/ (T <= Tn) + // (iff T is not a union) + if (that->is_union()) { + Handle unioned = that->as_union(); + for (int i = 0; i < unioned->length(); ++i) { + Handle that_i = union_get(unioned, i); + if (this->Is(that_i)) return true; + if (this->is_bitset()) break; // Fast fail, no other field is a bitset. + } + return false; + } + + return false; +} + + +// Check this overlaps that. +bool Type::Maybe(Handle that) { + // Fast path for bitsets. + if (this->is_bitset()) { + return (this->as_bitset() & that->LubBitset()) != 0; + } + if (that->is_bitset()) { + return (this->LubBitset() & that->as_bitset()) != 0; + } + + if (this->is_class()) { + return that->is_class() && *this->as_class() == *that->as_class(); + } + if (this->is_constant()) { + return that->is_constant() && *this->as_constant() == *that->as_constant(); + } + + // (T1 \/ ... \/ Tn) overlaps T <=> (T1 overlaps T) \/ ... \/ (Tn overlaps T) + if (this->is_union()) { + Handle unioned = this->as_union(); + for (int i = 0; i < unioned->length(); ++i) { + Handle this_i = union_get(unioned, i); + if (this_i->Maybe(that)) return true; + } + return false; + } + + // T overlaps (T1 \/ ... \/ Tn) <=> (T overlaps T1) \/ ... \/ (T overlaps Tn) + if (that->is_union()) { + Handle unioned = that->as_union(); + for (int i = 0; i < unioned->length(); ++i) { + Handle that_i = union_get(unioned, i); + if (this->Maybe(that_i)) return true; + } + return false; + } + + return false; +} + + +bool Type::InUnion(Handle unioned, int current_size) { + ASSERT(!this->is_union()); + for (int i = 0; i < current_size; ++i) { + Handle type = union_get(unioned, i); + if (type->is_bitset() ? this->Is(type) : this == *type) return true; + } + return false; +} + +// Get non-bitsets from this which are not subsumed by that, store at unioned, +// starting at index. Returns updated index. +int Type::ExtendUnion(Handle result, int current_size) { + int old_size = current_size; + if (this->is_class() || this->is_constant()) { + if (!this->InUnion(result, old_size)) result->set(current_size++, this); + } else if (this->is_union()) { + Handle unioned = this->as_union(); + for (int i = 0; i < unioned->length(); ++i) { + Handle type = union_get(unioned, i); + ASSERT(i == 0 || !(type->is_bitset() || type->Is(union_get(unioned, 0)))); + if (type->is_bitset()) continue; + if (!type->InUnion(result, old_size)) result->set(current_size++, *type); + } + } + return current_size; +} + + +// Union is O(1) on simple bit unions, but O(n*m) on structured unions. +// TODO(rossberg): Should we use object sets somehow? Is it worth it? +Type* Type::Union(Handle type1, Handle type2) { + // Fast case: bit sets. + if (type1->is_bitset() && type2->is_bitset()) { + return from_bitset(type1->as_bitset() | type2->as_bitset()); + } + + // Semi-fast case: Unioned objects are neither involved nor produced. + if (!(type1->is_union() || type2->is_union())) { + if (type1->Is(type2)) return *type2; + if (type2->Is(type1)) return *type1; + } + + // Slow case: may need to produce a Unioned object. + Isolate* isolate = NULL; + int size = type1->is_bitset() || type2->is_bitset() ? 1 : 0; + if (!type1->is_bitset()) { + isolate = HeapObject::cast(*type1)->GetIsolate(); + size += (type1->is_union() ? type1->as_union()->length() : 1); + } + if (!type2->is_bitset()) { + isolate = HeapObject::cast(*type2)->GetIsolate(); + size += (type2->is_union() ? type2->as_union()->length() : 1); + } + ASSERT(isolate != NULL); + ASSERT(size >= 2); + Handle unioned = isolate->factory()->NewFixedArray(size); + size = 0; + + int bitset = type1->GlbBitset() | type2->GlbBitset(); + if (bitset != kNone) unioned->set(size++, from_bitset(bitset)); + size = type1->ExtendUnion(unioned, size); + size = type2->ExtendUnion(unioned, size); + + if (size == 1) { + return *union_get(unioned, 0); + } else if (size == unioned->length()) { + return from_handle(unioned); + } + + // There was an overlap. Copy to smaller union. + Handle result = isolate->factory()->NewFixedArray(size); + for (int i = 0; i < size; ++i) result->set(i, unioned->get(i)); + return from_handle(result); +} + + +Type* Type::Optional(Handle type) { + return type->is_bitset() + ? from_bitset(type->as_bitset() | kUndefined) + : Union(type, Undefined()->handle_via_isolate_of(*type)); +} + +} } // namespace v8::internal diff --git a/src/types.h b/src/types.h new file mode 100644 index 0000000..018969f --- /dev/null +++ b/src/types.h @@ -0,0 +1,200 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef V8_TYPES_H_ +#define V8_TYPES_H_ + +#include "v8.h" + +#include "objects.h" + +namespace v8 { +namespace internal { + + +// A simple type system for compiler-internal use. It is based entirely on +// union types, and all subtyping hence amounts to set inclusion. Besides the +// obvious primitive types and some predefined unions, the type language also +// can express class types (a.k.a. specific maps) and singleton types (i.e., +// concrete constants). +// +// The following equations and inequations hold: +// +// None <= T +// T <= Any +// +// Oddball = Boolean \/ Null \/ Undefined +// Number = Smi \/ Double +// Name = String \/ Symbol +// UniqueName = InternalizedString \/ Symbol +// InternalizedString < String +// +// Receiver = Object \/ Proxy +// Array < Object +// Function < Object +// +// Class(map) < T iff instance_type(map) < T +// Constant(x) < T iff instance_type(map(x)) < T +// +// Note that Constant(x) < Class(map(x)) does _not_ hold, since x's map can +// change! (Its instance type cannot, however.) +// TODO(rossberg): the latter is not currently true for proxies, because of fix, +// but will hold once we implement direct proxies. +// +// There are two main functions for testing types: +// +// T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2) +// T1->Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0) +// +// Typically, the latter should be used to check whether a specific case needs +// handling (e.g., via T->Maybe(Number)). +// +// There is no functionality to discover whether a type is a leaf in the +// lattice. That is intentional. It should always be possible to refine the +// lattice (e.g., splitting up number types further) without invalidating any +// existing assumptions or tests. +// +// Internally, all 'primitive' types, and their unions, are represented as +// bitsets via smis. Class and Constant are heap pointers to the respective +// argument. Only unions containing Class'es or Constant's require allocation. +// +// The type representation is heap-allocated, so cannot (currently) be used in +// a parallel compilation context. + +class Type : public Object { + public: + static Type* None() { return from_bitset(kNone); } + static Type* Any() { return from_bitset(kAny); } + + static Type* Oddball() { return from_bitset(kOddball); } + static Type* Boolean() { return from_bitset(kBoolean); } + static Type* Null() { return from_bitset(kNull); } + static Type* Undefined() { return from_bitset(kUndefined); } + + static Type* Number() { return from_bitset(kNumber); } + static Type* Smi() { return from_bitset(kSmi); } + static Type* Double() { return from_bitset(kDouble); } + + static Type* Name() { return from_bitset(kName); } + static Type* UniqueName() { return from_bitset(kUniqueName); } + static Type* String() { return from_bitset(kString); } + static Type* InternalizedString() { return from_bitset(kInternalizedString); } + static Type* Symbol() { return from_bitset(kSymbol); } + + static Type* Receiver() { return from_bitset(kReceiver); } + static Type* Object() { return from_bitset(kObject); } + static Type* Array() { return from_bitset(kArray); } + static Type* Function() { return from_bitset(kFunction); } + static Type* Proxy() { return from_bitset(kProxy); } + + static Type* Class(Handle map) { return from_handle(map); } + static Type* Constant(Handle value) { + ASSERT(!value->IsMap() && !value->IsFixedArray()); + return from_handle(value); + } + + static Type* Union(Handle type1, Handle type2); + static Type* Optional(Handle type); // type \/ Undefined + + bool Is(Handle that); + bool Maybe(Handle that); + + // TODO(rossberg): method to iterate unions? + + private: + // A union is a fixed array containing types. Invariants: + // - its length is at least 2 + // - at most one field is a bitset, and it must go into index 0 + // - no field is a union + typedef FixedArray Unioned; + + enum { + kNull = 1 << 0, + kUndefined = 1 << 1, + kBoolean = 1 << 2, + kSmi = 1 << 3, + kDouble = 1 << 4, + kSymbol = 1 << 5, + kInternalizedString = 1 << 6, + kOtherString = 1 << 7, + kArray = 1 << 8, + kFunction = 1 << 9, + kOtherObject = 1 << 10, + kProxy = 1 << 11, + + kOddball = kBoolean | kNull | kUndefined, + kNumber = kSmi | kDouble, + kString = kInternalizedString | kOtherString, + kUniqueName = kSymbol | kInternalizedString, + kName = kSymbol | kString, + kObject = kArray | kFunction | kOtherObject, + kReceiver = kObject | kProxy, + kAny = kOddball | kNumber | kName | kReceiver, + kNone = 0 + }; + + bool is_bitset() { return this->IsSmi(); } + bool is_class() { return this->IsMap(); } + bool is_constant() { return !(is_bitset() || is_class() || is_union()); } + bool is_union() { return this->IsFixedArray(); } + + int as_bitset() { return Smi::cast(this)->value(); } + Handle as_class() { return Handle::cast(handle()); } + Handle as_constant() { + ASSERT(is_constant()); + return Handle::cast(handle()); + } + Handle as_union() { return Handle::cast(handle()); } + + Handle handle() { return handle_via_isolate_of(this); } + Handle handle_via_isolate_of(Type* type) { + ASSERT(type->IsHeapObject()); + return v8::internal::handle(this, HeapObject::cast(type)->GetIsolate()); + } + + static Type* from_bitset(int bitset) { + return static_cast(Object::cast(Smi::FromInt(bitset))); + } + static Type* from_handle(Handle handle) { + return static_cast(Object::cast(*handle)); + } + + static Handle union_get(Handle unioned, int i) { + Type* type = static_cast(unioned->get(i)); + ASSERT(!type->is_union()); + return type->handle_via_isolate_of(from_handle(unioned)); + } + + int LubBitset(); // least upper bound that's a bitset + int GlbBitset(); // greatest lower bound that's a bitset + bool InUnion(Handle unioned, int current_size); + int ExtendUnion(Handle unioned, int current_size); +}; + +} } // namespace v8::internal + +#endif // V8_TYPES_H_ diff --git a/src/typing.cc b/src/typing.cc index c2d418f..3e4144e 100644 --- a/src/typing.cc +++ b/src/typing.cc @@ -27,7 +27,6 @@ #include "typing.h" -#include "v8.h" #include "parser.h" // for CompileTimeValue; TODO(rossberg): should move #include "scopes.h" diff --git a/test/cctest/cctest.gyp b/test/cctest/cctest.gyp index 0a91ed5..75e4158 100644 --- a/test/cctest/cctest.gyp +++ b/test/cctest/cctest.gyp @@ -99,6 +99,7 @@ 'test-strtod.cc', 'test-thread-termination.cc', 'test-threads.cc', + 'test-types.cc', 'test-unbound-queue.cc', 'test-utils.cc', 'test-version.cc', diff --git a/test/cctest/test-types.cc b/test/cctest/test-types.cc new file mode 100644 index 0000000..d5852e0 --- /dev/null +++ b/test/cctest/test-types.cc @@ -0,0 +1,521 @@ +// Copyright 2013 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include "cctest.h" +#include "types.h" + +using namespace v8::internal; + +// Testing auxiliaries (breaking the Type abstraction). +static bool IsBitset(Type* type) { return type->IsSmi(); } +static bool IsClass(Type* type) { return type->IsMap(); } +static bool IsUnion(Type* type) { return type->IsFixedArray(); } +static bool IsConstant(Type* type) { + return !(IsBitset(type) || IsClass(type) || IsUnion(type)); +} + +static int AsBitset(Type* type) { return Smi::cast(type)->value(); } +static Map* AsClass(Type* type) { return Map::cast(type); } +static HeapObject* AsConstant(Type* type) { return HeapObject::cast(type); } +static FixedArray* AsUnion(Type* type) { return FixedArray::cast(type); } + +class HandlifiedTypes { + public: + explicit HandlifiedTypes(Isolate* isolate) : + None(Type::None(), isolate), + Any(Type::Any(), isolate), + Oddball(Type::Oddball(), isolate), + Boolean(Type::Boolean(), isolate), + Null(Type::Null(), isolate), + Undefined(Type::Undefined(), isolate), + Number(Type::Number(), isolate), + Smi(Type::Smi(), isolate), + Double(Type::Double(), isolate), + Name(Type::Name(), isolate), + UniqueName(Type::UniqueName(), isolate), + String(Type::String(), isolate), + InternalizedString(Type::InternalizedString(), isolate), + Symbol(Type::Symbol(), isolate), + Receiver(Type::Receiver(), isolate), + Object(Type::Object(), isolate), + Array(Type::Array(), isolate), + Function(Type::Function(), isolate), + Proxy(Type::Proxy(), isolate), + object_map(isolate->factory()->NewMap(JS_OBJECT_TYPE, 3 * kPointerSize)), + array_map(isolate->factory()->NewMap(JS_ARRAY_TYPE, 4 * kPointerSize)), + isolate_(isolate) { + object1 = isolate->factory()->NewJSObjectFromMap(object_map); + object2 = isolate->factory()->NewJSObjectFromMap(object_map); + array = isolate->factory()->NewJSArray(20); + ObjectClass = handle(Type::Class(object_map), isolate); + ArrayClass = handle(Type::Class(array_map), isolate); + ObjectConstant1 = handle(Type::Constant(object1), isolate); + ObjectConstant2 = handle(Type::Constant(object2), isolate); + ArrayConstant = handle(Type::Constant(array), isolate); + } + + Handle None; + Handle Any; + Handle Oddball; + Handle Boolean; + Handle Null; + Handle Undefined; + Handle Number; + Handle Smi; + Handle Double; + Handle Name; + Handle UniqueName; + Handle String; + Handle InternalizedString; + Handle Symbol; + Handle Receiver; + Handle Object; + Handle Array; + Handle Function; + Handle Proxy; + + Handle ObjectClass; + Handle ArrayClass; + Handle ObjectConstant1; + Handle ObjectConstant2; + Handle ArrayConstant; + + Handle object_map; + Handle array_map; + + Handle object1; + Handle object2; + Handle array; + + Handle Union(Handle type1, Handle type2) { + return handle(Type::Union(type1, type2), isolate_); + } + + private: + Isolate* isolate_; +}; + + +TEST(Bitset) { + CcTest::InitializeVM(); + Isolate* isolate = Isolate::Current(); + HandleScope scope(isolate); + HandlifiedTypes T(isolate); + + CHECK(IsBitset(*T.None)); + CHECK(IsBitset(*T.Any)); + CHECK(IsBitset(*T.String)); + CHECK(IsBitset(*T.Object)); + + CHECK(IsBitset(Type::Union(T.String, T.Number))); + CHECK(IsBitset(Type::Union(T.String, T.Receiver))); + CHECK(IsBitset(Type::Optional(T.Object))); + + CHECK_EQ(0, AsBitset(*T.None)); + CHECK_EQ(AsBitset(*T.Number) | AsBitset(*T.String), + AsBitset(Type::Union(T.String, T.Number))); + CHECK_EQ(AsBitset(*T.Receiver), + AsBitset(Type::Union(T.Receiver, T.Object))); + CHECK_EQ(AsBitset(*T.String) | AsBitset(*T.Undefined), + AsBitset(Type::Optional(T.String))); +} + + +TEST(Class) { + CcTest::InitializeVM(); + Isolate* isolate = Isolate::Current(); + HandleScope scope(isolate); + HandlifiedTypes T(isolate); + + CHECK(IsClass(*T.ObjectClass)); + CHECK(IsClass(*T.ArrayClass)); + + CHECK(*T.object_map == AsClass(*T.ObjectClass)); + CHECK(*T.array_map == AsClass(*T.ArrayClass)); +} + + +TEST(Constant) { + CcTest::InitializeVM(); + Isolate* isolate = Isolate::Current(); + HandleScope scope(isolate); + HandlifiedTypes T(isolate); + + CHECK(IsConstant(*T.ObjectConstant1)); + CHECK(IsConstant(*T.ObjectConstant2)); + CHECK(IsConstant(*T.ArrayConstant)); + + CHECK(*T.object1 == AsConstant(*T.ObjectConstant1)); + CHECK(*T.object2 == AsConstant(*T.ObjectConstant2)); + CHECK(*T.object1 != AsConstant(*T.ObjectConstant2)); + CHECK(*T.array == AsConstant(*T.ArrayConstant)); +} + + +static void CheckSub(Handle type1, Handle type2) { + CHECK(type1->Is(type2)); + CHECK(!type2->Is(type1)); + if (IsBitset(*type1) && IsBitset(*type2)) { + CHECK_NE(AsBitset(*type1), AsBitset(*type2)); + } +} + +static void CheckUnordered(Handle type1, Handle type2) { + CHECK(!type1->Is(type2)); + CHECK(!type2->Is(type1)); + if (IsBitset(*type1) && IsBitset(*type2)) { + CHECK_NE(AsBitset(*type1), AsBitset(*type2)); + } +} + +TEST(Is) { + CcTest::InitializeVM(); + Isolate* isolate = Isolate::Current(); + HandleScope scope(isolate); + HandlifiedTypes T(isolate); + + // Reflexivity + CHECK(T.None->Is(T.None)); + CHECK(T.Any->Is(T.Any)); + CHECK(T.Object->Is(T.Object)); + + CHECK(T.ObjectClass->Is(T.ObjectClass)); + CHECK(T.ObjectConstant1->Is(T.ObjectConstant1)); + + // Symmetry and Transitivity + CheckSub(T.None, T.Number); + CheckSub(T.None, T.Any); + + CheckSub(T.Oddball, T.Any); + CheckSub(T.Boolean, T.Oddball); + CheckSub(T.Null, T.Oddball); + CheckSub(T.Undefined, T.Oddball); + CheckUnordered(T.Boolean, T.Null); + CheckUnordered(T.Undefined, T.Null); + CheckUnordered(T.Boolean, T.Undefined); + + CheckSub(T.Number, T.Any); + CheckSub(T.Smi, T.Number); + CheckSub(T.Double, T.Number); + CheckUnordered(T.Smi, T.Double); + + CheckSub(T.Name, T.Any); + CheckSub(T.UniqueName, T.Any); + CheckSub(T.UniqueName, T.Name); + CheckSub(T.String, T.Name); + CheckSub(T.InternalizedString, T.String); + CheckSub(T.InternalizedString, T.UniqueName); + CheckSub(T.InternalizedString, T.Name); + CheckSub(T.Symbol, T.UniqueName); + CheckSub(T.Symbol, T.Name); + CheckUnordered(T.String, T.UniqueName); + CheckUnordered(T.String, T.Symbol); + CheckUnordered(T.InternalizedString, T.Symbol); + + CheckSub(T.Receiver, T.Any); + CheckSub(T.Object, T.Any); + CheckSub(T.Object, T.Receiver); + CheckSub(T.Array, T.Object); + CheckSub(T.Function, T.Object); + CheckSub(T.Proxy, T.Receiver); + CheckUnordered(T.Object, T.Proxy); + CheckUnordered(T.Array, T.Function); + + // Structured subtyping + CheckSub(T.ObjectClass, T.Object); + CheckSub(T.ArrayClass, T.Object); + CheckUnordered(T.ObjectClass, T.ArrayClass); + + CheckSub(T.ObjectConstant1, T.Object); + CheckSub(T.ObjectConstant2, T.Object); + CheckSub(T.ArrayConstant, T.Object); + CheckSub(T.ArrayConstant, T.Array); + CheckUnordered(T.ObjectConstant1, T.ObjectConstant2); + CheckUnordered(T.ObjectConstant1, T.ArrayConstant); + + CheckUnordered(T.ObjectConstant1, T.ObjectClass); + CheckUnordered(T.ObjectConstant2, T.ObjectClass); + CheckUnordered(T.ObjectConstant1, T.ArrayClass); + CheckUnordered(T.ObjectConstant2, T.ArrayClass); + CheckUnordered(T.ArrayConstant, T.ObjectClass); +} + + +static void CheckOverlap(Handle type1, Handle type2) { + CHECK(type1->Maybe(type2)); + CHECK(type2->Maybe(type1)); + if (IsBitset(*type1) && IsBitset(*type2)) { + CHECK_NE(0, AsBitset(*type1) & AsBitset(*type2)); + } +} + +static void CheckDisjoint(Handle type1, Handle type2) { + CHECK(!type1->Is(type2)); + CHECK(!type2->Is(type1)); + CHECK(!type1->Maybe(type2)); + CHECK(!type2->Maybe(type1)); + if (IsBitset(*type1) && IsBitset(*type2)) { + CHECK_EQ(0, AsBitset(*type1) & AsBitset(*type2)); + } +} + +TEST(Maybe) { + CcTest::InitializeVM(); + Isolate* isolate = Isolate::Current(); + HandleScope scope(isolate); + HandlifiedTypes T(isolate); + + CheckOverlap(T.Any, T.Any); + CheckOverlap(T.Object, T.Object); + + CheckOverlap(T.Oddball, T.Any); + CheckOverlap(T.Boolean, T.Oddball); + CheckOverlap(T.Null, T.Oddball); + CheckOverlap(T.Undefined, T.Oddball); + CheckDisjoint(T.Boolean, T.Null); + CheckDisjoint(T.Undefined, T.Null); + CheckDisjoint(T.Boolean, T.Undefined); + + CheckOverlap(T.Number, T.Any); + CheckOverlap(T.Smi, T.Number); + CheckOverlap(T.Double, T.Number); + CheckDisjoint(T.Smi, T.Double); + + CheckOverlap(T.Name, T.Any); + CheckOverlap(T.UniqueName, T.Any); + 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.Receiver, T.Any); + CheckOverlap(T.Object, T.Any); + 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); + + 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.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.ObjectClass); + CheckDisjoint(T.ObjectConstant2, T.ObjectClass); + CheckDisjoint(T.ObjectConstant1, T.ArrayClass); + CheckDisjoint(T.ObjectConstant2, T.ArrayClass); + CheckDisjoint(T.ArrayConstant, T.ObjectClass); +} + + +static void CheckEqual(Handle type1, Handle type2) { + CHECK_EQ(IsBitset(*type1), IsBitset(*type2)); + CHECK_EQ(IsClass(*type1), IsClass(*type2)); + CHECK_EQ(IsConstant(*type1), IsConstant(*type2)); + CHECK_EQ(IsUnion(*type1), IsUnion(*type2)); + if (IsBitset(*type1)) { + CHECK_EQ(AsBitset(*type1), AsBitset(*type2)); + } else if (IsClass(*type1)) { + CHECK_EQ(AsClass(*type1), AsClass(*type2)); + } else if (IsConstant(*type1)) { + CHECK_EQ(AsConstant(*type1), AsConstant(*type2)); + } else if (IsUnion(*type1)) { + CHECK_EQ(AsUnion(*type1)->length(), AsUnion(*type2)->length()); + } + CHECK(type1->Is(type2)); + CHECK(type2->Is(type1)); +} + +TEST(Union) { + CcTest::InitializeVM(); + Isolate* isolate = Isolate::Current(); + HandleScope scope(isolate); + HandlifiedTypes T(isolate); + + // Bitset-bitset + CHECK(IsBitset(Type::Union(T.Object, T.Number))); + CHECK(IsBitset(Type::Union(T.Object, T.Object))); + CHECK(IsBitset(Type::Union(T.Any, T.None))); + + CheckEqual(T.Union(T.None, T.Number), T.Number); + CheckEqual(T.Union(T.Object, T.Proxy), T.Receiver); + CheckEqual(T.Union(T.Number, T.String), T.Union(T.String, T.Number)); + CheckSub(T.Union(T.Number, T.String), T.Any); + + // Class-class + CHECK(IsClass(Type::Union(T.ObjectClass, T.ObjectClass))); + CHECK(IsUnion(Type::Union(T.ObjectClass, T.ArrayClass))); + + CheckEqual(T.Union(T.ObjectClass, T.ObjectClass), T.ObjectClass); + 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); + CheckUnordered(T.Union(T.ObjectClass, T.ArrayClass), T.Array); + CheckOverlap(T.Union(T.ObjectClass, T.ArrayClass), T.Array); + CheckDisjoint(T.Union(T.ObjectClass, T.ArrayClass), T.Number); + + // Constant-constant + CHECK(IsConstant(Type::Union(T.ObjectConstant1, T.ObjectConstant1))); + CHECK(IsUnion(Type::Union(T.ObjectConstant1, T.ObjectConstant2))); + + CheckEqual(T.Union(T.ObjectConstant1, T.ObjectConstant1), T.ObjectConstant1); + CheckSub(T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)); + CheckSub(T.ObjectConstant2, T.Union(T.ObjectConstant1, T.ObjectConstant2)); + CheckSub(T.Union(T.ObjectConstant1, T.ObjectConstant2), T.Object); + CheckUnordered(T.Union(T.ObjectConstant1, T.ObjectConstant2), T.ObjectClass); + CheckUnordered(T.Union(T.ObjectConstant1, T.ArrayConstant), T.Array); + CheckOverlap(T.Union(T.ObjectConstant1, T.ArrayConstant), T.Array); + CheckDisjoint(T.Union(T.ObjectConstant1, T.ArrayConstant), T.Number); + CheckDisjoint(T.Union(T.ObjectConstant1, T.ArrayConstant), T.ObjectClass); + + // Bitset-class + CHECK(IsBitset(Type::Union(T.ObjectClass, T.Object))); + CHECK(IsUnion(Type::Union(T.ObjectClass, T.Number))); + + CheckEqual(T.Union(T.ObjectClass, T.Object), T.Object); + 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); + CheckUnordered(T.Union(T.ObjectClass, T.String), T.Array); + CheckOverlap(T.Union(T.ObjectClass, T.String), T.Object); + CheckDisjoint(T.Union(T.ObjectClass, T.String), T.Number); + + // Bitset-constant + CHECK(IsBitset(Type::Union(T.ObjectConstant1, T.Object))); + CHECK(IsUnion(Type::Union(T.ObjectConstant2, T.Number))); + + CheckEqual(T.Union(T.ObjectConstant1, T.Object), T.Object); + CheckSub(T.Union(T.ObjectConstant1, T.Number), T.Any); + CheckSub(T.Union(T.ObjectConstant1, T.Smi), 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); + CheckDisjoint(T.Union(T.ObjectConstant1, T.String), T.Number); + + // Class-constant + CHECK(IsUnion(Type::Union(T.ObjectConstant1, T.ObjectClass))); + CHECK(IsUnion(Type::Union(T.ArrayClass, T.ObjectConstant2))); + + 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)); + CheckUnordered(T.ObjectClass, T.Union(T.ObjectConstant1, T.ArrayClass)); + CheckSub( + 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); + CheckDisjoint(T.Union(T.ObjectConstant1, T.ArrayClass), T.ObjectClass); + + // Bitset-union + CHECK(IsBitset( + Type::Union(T.Object, T.Union(T.ObjectConstant1, T.ObjectClass)))); + CHECK(IsUnion( + Type::Union(T.Union(T.ArrayClass, T.ObjectConstant2), T.Number))); + + CheckEqual( + T.Union(T.Object, T.Union(T.ObjectConstant1, T.ObjectClass)), + T.Object); + CheckEqual( + T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Number), + T.Union(T.ObjectConstant1, T.Union(T.Number, T.ArrayClass))); + CheckSub( + T.Double, + T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Number)); + CheckSub( + T.ObjectConstant1, + T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Double)); + CheckSub( + T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Double), + T.Any); + CheckSub( + T.Union(T.Union(T.ArrayClass, T.ObjectConstant1), T.Double), + T.Union(T.ObjectConstant1, T.Union(T.Number, T.ArrayClass))); + + // Class-union + CHECK(IsUnion( + Type::Union(T.Union(T.ArrayClass, T.ObjectConstant2), T.ArrayClass))); + CHECK(IsUnion( + Type::Union(T.Union(T.ArrayClass, T.ObjectConstant2), T.ObjectClass))); + + CheckEqual( + T.Union(T.ObjectClass, T.Union(T.ObjectConstant1, T.ObjectClass)), + T.Union(T.ObjectClass, T.ObjectConstant1)); + CheckSub( + T.Union(T.ObjectClass, T.Union(T.ObjectConstant1, T.ObjectClass)), + T.Object); + CheckEqual( + T.Union(T.Union(T.ArrayClass, T.ObjectConstant2), T.ArrayClass), + T.Union(T.ArrayClass, T.ObjectConstant2)); + + // Constant-union + CHECK(IsUnion(Type::Union( + T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)))); + CHECK(IsUnion(Type::Union( + T.Union(T.ArrayConstant, T.ObjectClass), T.ObjectConstant1))); + CHECK(IsUnion(Type::Union( + T.Union(T.ArrayConstant, T.ObjectConstant2), T.ObjectConstant1))); + + CheckEqual( + T.Union(T.ObjectConstant1, T.Union(T.ObjectConstant1, T.ObjectConstant2)), + T.Union(T.ObjectConstant2, T.ObjectConstant1)); + CheckEqual( + T.Union(T.Union(T.ArrayConstant, T.ObjectConstant2), T.ObjectConstant1), + T.Union(T.ObjectConstant2, T.Union(T.ArrayConstant, T.ObjectConstant1))); + + // Union-union + CHECK(IsBitset( + Type::Union(T.Union(T.Number, T.ArrayClass), T.Union(T.Smi, T.Array)))); + + CheckEqual( + T.Union(T.Union(T.ObjectConstant2, T.ObjectConstant1), + T.Union(T.ObjectConstant1, T.ObjectConstant2)), + T.Union(T.ObjectConstant2, T.ObjectConstant1)); + CheckEqual( + T.Union(T.Union(T.ObjectConstant2, T.ArrayConstant), + T.Union(T.ObjectConstant1, T.ArrayConstant)), + T.Union(T.Union(T.ObjectConstant1, T.ObjectConstant2), T.ArrayConstant)); + CheckEqual( + T.Union(T.Union(T.Number, T.ArrayClass), T.Union(T.Smi, T.Array)), + T.Union(T.Number, T.Array)); +} diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 9b90cba..ed37e72 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -456,6 +456,8 @@ '../../src/transitions.h', '../../src/type-info.cc', '../../src/type-info.h', + '../../src/types.cc', + '../../src/types.h', '../../src/typing.cc', '../../src/typing.h', '../../src/unbound-queue-inl.h', -- 2.7.4