| // Copyright 2014 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef V8_AST_AST_TYPES_H_ |
| #define V8_AST_AST_TYPES_H_ |
| |
| #include "src/conversions.h" |
| #include "src/handles.h" |
| #include "src/objects.h" |
| #include "src/ostreams.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| // SUMMARY |
| // |
| // 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). |
| // |
| // 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: |
| // |
| // None <= T |
| // T <= Any |
| // |
| // Number = Signed32 \/ Unsigned32 \/ Double |
| // Smi <= Signed32 |
| // Name = String \/ Symbol |
| // UniqueName = InternalizedString \/ Symbol |
| // InternalizedString < String |
| // |
| // Receiver = Object \/ Proxy |
| // Array < Object |
| // Function < Object |
| // RegExp < Object |
| // OtherUndetectable < Object |
| // DetectableReceiver = Receiver - OtherUndetectable |
| // |
| // Class(map) < T iff instance_type(map) < T |
| // Constant(x) < T iff instance_type(map(x)) < T |
| // Array(T) < Array |
| // Function(R, S, T0, T1, ...) < Function |
| // Context(T) < Internal |
| // |
| // Both structural Array and Function types are invariant in all parameters; |
| // relaxing this would make Union and Intersect operations more involved. |
| // There is no subtyping relation between Array, Function, or Context types |
| // and respective Constant types, since these types cannot be reconstructed |
| // for arbitrary heap values. |
| // Note also 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. |
| // 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: |
| // |
| // None <= R |
| // R <= Any |
| // |
| // UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/ |
| // UntaggedInt16 \/ UntaggedInt32 |
| // UntaggedFloat = UntaggedFloat32 \/ UntaggedFloat64 |
| // UntaggedNumber = UntaggedInt \/ UntaggedFloat |
| // Untagged = UntaggedNumber \/ UntaggedPtr |
| // Tagged = TaggedInt \/ TaggedPtr |
| // |
| // Subtyping relates the two dimensions, for example: |
| // |
| // Number <= Tagged \/ UntaggedNumber |
| // Object <= TaggedPtr \/ UntaggedPtr |
| // |
| // That holds because the semantic type constructors defined by the API create |
| // types that allow for all possible representations, and dually, the ones for |
| // representation types initially include all semantic ranges. Representations |
| // can then e.g. be narrowed for a given semantic type using intersection: |
| // |
| // 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 may be an infinity, in which case that infinity |
| // itself is also included in the range. A range never contains NaN or -0. |
| // |
| // If a value v happens to be an integer n, then Constant(v) is considered a |
| // subtype of Range(n, n) (and therefore also a subtype of any larger range). |
| // In order to avoid large unions, however, it is usually a good idea to use |
| // Range rather than Constant. |
| // |
| // |
| // PREDICATES |
| // |
| // 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 former is to be used to select representations (e.g., via |
| // T->Is(SignedSmall())), and the latter 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. |
| // Consequently, do not normally use Equals for type tests, always use Is! |
| // |
| // The NowIs operator implements state-sensitive subtying, as described above. |
| // 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 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 |
| // bitsets. Bit 0 is reserved for tagging. Class is a heap pointer to the |
| // respective map. Only structured types require allocation. |
| // Note that the bitset representation is closed under both Union and Intersect. |
| |
| // ----------------------------------------------------------------------------- |
| // Values for bitset types |
| |
| // clang-format off |
| |
| #define AST_MASK_BITSET_TYPE_LIST(V) \ |
| V(Representation, 0xffc00000u) \ |
| V(Semantic, 0x003ffffeu) |
| |
| #define AST_REPRESENTATION(k) ((k) & AstBitsetType::kRepresentation) |
| #define AST_SEMANTIC(k) ((k) & AstBitsetType::kSemantic) |
| |
| // Bits 21-22 are available. |
| #define AST_REPRESENTATION_BITSET_TYPE_LIST(V) \ |
| V(None, 0) \ |
| V(UntaggedBit, 1u << 23 | kSemantic) \ |
| V(UntaggedIntegral8, 1u << 24 | kSemantic) \ |
| V(UntaggedIntegral16, 1u << 25 | kSemantic) \ |
| V(UntaggedIntegral32, 1u << 26 | kSemantic) \ |
| V(UntaggedFloat32, 1u << 27 | kSemantic) \ |
| V(UntaggedFloat64, 1u << 28 | kSemantic) \ |
| V(UntaggedPointer, 1u << 29 | kSemantic) \ |
| V(TaggedSigned, 1u << 30 | kSemantic) \ |
| V(TaggedPointer, 1u << 31 | kSemantic) \ |
| \ |
| V(UntaggedIntegral, kUntaggedBit | kUntaggedIntegral8 | \ |
| kUntaggedIntegral16 | kUntaggedIntegral32) \ |
| V(UntaggedFloat, kUntaggedFloat32 | kUntaggedFloat64) \ |
| V(UntaggedNumber, kUntaggedIntegral | kUntaggedFloat) \ |
| V(Untagged, kUntaggedNumber | kUntaggedPointer) \ |
| V(Tagged, kTaggedSigned | kTaggedPointer) |
| |
| #define AST_INTERNAL_BITSET_TYPE_LIST(V) \ |
| V(OtherUnsigned31, 1u << 1 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(OtherUnsigned32, 1u << 2 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(OtherSigned32, 1u << 3 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(OtherNumber, 1u << 4 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) |
| |
| #define AST_SEMANTIC_BITSET_TYPE_LIST(V) \ |
| V(Negative31, 1u << 5 | \ |
| AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(Null, 1u << 6 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(Undefined, 1u << 7 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(Boolean, 1u << 8 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(Unsigned30, 1u << 9 | \ |
| AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(MinusZero, 1u << 10 | \ |
| AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(NaN, 1u << 11 | \ |
| AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(Symbol, 1u << 12 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(InternalizedString, 1u << 13 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(OtherString, 1u << 14 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(OtherObject, 1u << 15 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(OtherUndetectable, 1u << 16 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(Proxy, 1u << 17 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(Function, 1u << 18 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(Hole, 1u << 19 | AST_REPRESENTATION(kTaggedPointer)) \ |
| V(OtherInternal, 1u << 20 | \ |
| AST_REPRESENTATION(kTagged | kUntagged)) \ |
| \ |
| V(Signed31, kUnsigned30 | kNegative31) \ |
| V(Signed32, kSigned31 | kOtherUnsigned31 | \ |
| kOtherSigned32) \ |
| V(Signed32OrMinusZero, kSigned32 | kMinusZero) \ |
| V(Signed32OrMinusZeroOrNaN, kSigned32 | kMinusZero | kNaN) \ |
| V(Negative32, kNegative31 | kOtherSigned32) \ |
| V(Unsigned31, kUnsigned30 | kOtherUnsigned31) \ |
| V(Unsigned32, kUnsigned30 | kOtherUnsigned31 | \ |
| kOtherUnsigned32) \ |
| V(Unsigned32OrMinusZero, kUnsigned32 | kMinusZero) \ |
| V(Unsigned32OrMinusZeroOrNaN, kUnsigned32 | kMinusZero | kNaN) \ |
| V(Integral32, kSigned32 | kUnsigned32) \ |
| V(PlainNumber, kIntegral32 | kOtherNumber) \ |
| V(OrderedNumber, kPlainNumber | kMinusZero) \ |
| V(MinusZeroOrNaN, kMinusZero | kNaN) \ |
| V(Number, kOrderedNumber | kNaN) \ |
| V(String, kInternalizedString | kOtherString) \ |
| V(UniqueName, kSymbol | kInternalizedString) \ |
| V(Name, kSymbol | kString) \ |
| V(BooleanOrNumber, kBoolean | kNumber) \ |
| V(BooleanOrNullOrNumber, kBooleanOrNumber | kNull) \ |
| V(BooleanOrNullOrUndefined, kBoolean | kNull | kUndefined) \ |
| V(NullOrNumber, kNull | kNumber) \ |
| V(NullOrUndefined, kNull | kUndefined) \ |
| V(Undetectable, kNullOrUndefined | kOtherUndetectable) \ |
| V(NumberOrOddball, kNumber | kNullOrUndefined | kBoolean | kHole) \ |
| V(NumberOrString, kNumber | kString) \ |
| V(NumberOrUndefined, kNumber | kUndefined) \ |
| V(PlainPrimitive, kNumberOrString | kBoolean | kNullOrUndefined) \ |
| V(Primitive, kSymbol | kPlainPrimitive) \ |
| V(DetectableReceiver, kFunction | kOtherObject | kProxy) \ |
| V(Object, kFunction | kOtherObject | kOtherUndetectable) \ |
| V(Receiver, kObject | kProxy) \ |
| V(StringOrReceiver, kString | kReceiver) \ |
| V(Unique, kBoolean | kUniqueName | kNull | kUndefined | \ |
| kReceiver) \ |
| V(Internal, kHole | kOtherInternal) \ |
| V(NonInternal, kPrimitive | kReceiver) \ |
| V(NonNumber, kUnique | kString | kInternal) \ |
| V(Any, 0xfffffffeu) |
| |
| // clang-format on |
| |
| /* |
| * The following diagrams show how integers (in the mathematical sense) are |
| * divided among the different atomic numerical types. |
| * |
| * ON OS32 N31 U30 OU31 OU32 ON |
| * ______[_______[_______[_______[_______[_______[_______ |
| * -2^31 -2^30 0 2^30 2^31 2^32 |
| * |
| * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. |
| * |
| * Some of the atomic numerical bitsets are internal only (see |
| * INTERNAL_BITSET_TYPE_LIST). To a types user, they should only occur in |
| * union with certain other bitsets. For instance, OtherNumber should only |
| * occur as part of PlainNumber. |
| */ |
| |
| #define AST_PROPER_BITSET_TYPE_LIST(V) \ |
| AST_REPRESENTATION_BITSET_TYPE_LIST(V) \ |
| AST_SEMANTIC_BITSET_TYPE_LIST(V) |
| |
| #define AST_BITSET_TYPE_LIST(V) \ |
| AST_MASK_BITSET_TYPE_LIST(V) \ |
| AST_REPRESENTATION_BITSET_TYPE_LIST(V) \ |
| AST_INTERNAL_BITSET_TYPE_LIST(V) \ |
| AST_SEMANTIC_BITSET_TYPE_LIST(V) |
| |
| class AstType; |
| |
| // ----------------------------------------------------------------------------- |
| // Bitset types (internal). |
| |
| class AstBitsetType { |
| public: |
| typedef uint32_t bitset; // Internal |
| |
| enum : uint32_t { |
| #define DECLARE_TYPE(type, value) k##type = (value), |
| AST_BITSET_TYPE_LIST(DECLARE_TYPE) |
| #undef DECLARE_TYPE |
| kUnusedEOL = 0 |
| }; |
| |
| static bitset SignedSmall(); |
| static bitset UnsignedSmall(); |
| |
| bitset Bitset() { |
| return static_cast<bitset>(reinterpret_cast<uintptr_t>(this) ^ 1u); |
| } |
| |
| static bool IsInhabited(bitset bits) { |
| return AST_SEMANTIC(bits) != kNone && AST_REPRESENTATION(bits) != kNone; |
| } |
| |
| static bool SemanticIsInhabited(bitset bits) { |
| return AST_SEMANTIC(bits) != kNone; |
| } |
| |
| static bool Is(bitset bits1, bitset bits2) { |
| return (bits1 | bits2) == bits2; |
| } |
| |
| static double Min(bitset); |
| static double Max(bitset); |
| |
| static bitset Glb(AstType* type); // greatest lower bound that's a bitset |
| static bitset Glb(double min, double max); |
| static bitset Lub(AstType* type); // least upper bound that's a bitset |
| static bitset Lub(i::Map* map); |
| static bitset Lub(i::Object* value); |
| static bitset Lub(double value); |
| static bitset Lub(double min, double max); |
| static bitset ExpandInternals(bitset bits); |
| |
| static const char* Name(bitset); |
| static void Print(std::ostream& os, bitset); // NOLINT |
| #ifdef DEBUG |
| static void Print(bitset); |
| #endif |
| |
| static bitset NumberBits(bitset bits); |
| |
| static bool IsBitset(AstType* type) { |
| return reinterpret_cast<uintptr_t>(type) & 1; |
| } |
| |
| static AstType* NewForTesting(bitset bits) { return New(bits); } |
| |
| private: |
| friend class AstType; |
| |
| static AstType* New(bitset bits) { |
| return reinterpret_cast<AstType*>(static_cast<uintptr_t>(bits | 1u)); |
| } |
| |
| struct Boundary { |
| bitset internal; |
| bitset external; |
| double min; |
| }; |
| static const Boundary BoundariesArray[]; |
| static inline const Boundary* Boundaries(); |
| static inline size_t BoundariesSize(); |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Superclass for non-bitset types (internal). |
| class AstTypeBase { |
| protected: |
| friend class AstType; |
| |
| enum Kind { |
| kClass, |
| kConstant, |
| kContext, |
| kArray, |
| kFunction, |
| kTuple, |
| kUnion, |
| kRange |
| }; |
| |
| Kind kind() const { return kind_; } |
| explicit AstTypeBase(Kind kind) : kind_(kind) {} |
| |
| static bool IsKind(AstType* type, Kind kind) { |
| if (AstBitsetType::IsBitset(type)) return false; |
| AstTypeBase* base = reinterpret_cast<AstTypeBase*>(type); |
| return base->kind() == kind; |
| } |
| |
| // The hacky conversion to/from AstType*. |
| static AstType* AsType(AstTypeBase* type) { |
| return reinterpret_cast<AstType*>(type); |
| } |
| static AstTypeBase* FromType(AstType* type) { |
| return reinterpret_cast<AstTypeBase*>(type); |
| } |
| |
| private: |
| Kind kind_; |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Class types. |
| |
| class AstClassType : public AstTypeBase { |
| public: |
| i::Handle<i::Map> Map() { return map_; } |
| |
| private: |
| friend class AstType; |
| friend class AstBitsetType; |
| |
| static AstType* New(i::Handle<i::Map> map, Zone* zone) { |
| return AsType(new (zone->New(sizeof(AstClassType))) |
| AstClassType(AstBitsetType::Lub(*map), map)); |
| } |
| |
| static AstClassType* cast(AstType* type) { |
| DCHECK(IsKind(type, kClass)); |
| return static_cast<AstClassType*>(FromType(type)); |
| } |
| |
| AstClassType(AstBitsetType::bitset bitset, i::Handle<i::Map> map) |
| : AstTypeBase(kClass), bitset_(bitset), map_(map) {} |
| |
| AstBitsetType::bitset Lub() { return bitset_; } |
| |
| AstBitsetType::bitset bitset_; |
| Handle<i::Map> map_; |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Constant types. |
| |
| class AstConstantType : public AstTypeBase { |
| public: |
| i::Handle<i::Object> Value() { return object_; } |
| |
| private: |
| friend class AstType; |
| friend class AstBitsetType; |
| |
| static AstType* New(i::Handle<i::Object> value, Zone* zone) { |
| AstBitsetType::bitset bitset = AstBitsetType::Lub(*value); |
| return AsType(new (zone->New(sizeof(AstConstantType))) |
| AstConstantType(bitset, value)); |
| } |
| |
| static AstConstantType* cast(AstType* type) { |
| DCHECK(IsKind(type, kConstant)); |
| return static_cast<AstConstantType*>(FromType(type)); |
| } |
| |
| AstConstantType(AstBitsetType::bitset bitset, i::Handle<i::Object> object) |
| : AstTypeBase(kConstant), bitset_(bitset), object_(object) {} |
| |
| AstBitsetType::bitset Lub() { return bitset_; } |
| |
| AstBitsetType::bitset bitset_; |
| Handle<i::Object> object_; |
| }; |
| // TODO(neis): Also cache value if numerical. |
| // TODO(neis): Allow restricting the representation. |
| |
| // ----------------------------------------------------------------------------- |
| // Range types. |
| |
| class AstRangeType : public AstTypeBase { |
| public: |
| struct Limits { |
| double min; |
| double max; |
| Limits(double min, double max) : min(min), max(max) {} |
| explicit Limits(AstRangeType* range) |
| : min(range->Min()), max(range->Max()) {} |
| bool IsEmpty(); |
| static Limits Empty() { return Limits(1, 0); } |
| static Limits Intersect(Limits lhs, Limits rhs); |
| static Limits Union(Limits lhs, Limits rhs); |
| }; |
| |
| double Min() { return limits_.min; } |
| double Max() { return limits_.max; } |
| |
| private: |
| friend class AstType; |
| friend class AstBitsetType; |
| friend class AstUnionType; |
| |
| static AstType* New(double min, double max, |
| AstBitsetType::bitset representation, Zone* zone) { |
| return New(Limits(min, max), representation, zone); |
| } |
| |
| static bool IsInteger(double x) { |
| return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. |
| } |
| |
| static AstType* New(Limits lim, AstBitsetType::bitset representation, |
| Zone* zone) { |
| DCHECK(IsInteger(lim.min) && IsInteger(lim.max)); |
| DCHECK(lim.min <= lim.max); |
| DCHECK(AST_REPRESENTATION(representation) == representation); |
| AstBitsetType::bitset bits = |
| AST_SEMANTIC(AstBitsetType::Lub(lim.min, lim.max)) | representation; |
| |
| return AsType(new (zone->New(sizeof(AstRangeType))) |
| AstRangeType(bits, lim)); |
| } |
| |
| static AstRangeType* cast(AstType* type) { |
| DCHECK(IsKind(type, kRange)); |
| return static_cast<AstRangeType*>(FromType(type)); |
| } |
| |
| AstRangeType(AstBitsetType::bitset bitset, Limits limits) |
| : AstTypeBase(kRange), bitset_(bitset), limits_(limits) {} |
| |
| AstBitsetType::bitset Lub() { return bitset_; } |
| |
| AstBitsetType::bitset bitset_; |
| Limits limits_; |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Context types. |
| |
| class AstContextType : public AstTypeBase { |
| public: |
| AstType* Outer() { return outer_; } |
| |
| private: |
| friend class AstType; |
| |
| static AstType* New(AstType* outer, Zone* zone) { |
| return AsType(new (zone->New(sizeof(AstContextType))) |
| AstContextType(outer)); // NOLINT |
| } |
| |
| static AstContextType* cast(AstType* type) { |
| DCHECK(IsKind(type, kContext)); |
| return static_cast<AstContextType*>(FromType(type)); |
| } |
| |
| explicit AstContextType(AstType* outer) |
| : AstTypeBase(kContext), outer_(outer) {} |
| |
| AstType* outer_; |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Array types. |
| |
| class AstArrayType : public AstTypeBase { |
| public: |
| AstType* Element() { return element_; } |
| |
| private: |
| friend class AstType; |
| |
| explicit AstArrayType(AstType* element) |
| : AstTypeBase(kArray), element_(element) {} |
| |
| static AstType* New(AstType* element, Zone* zone) { |
| return AsType(new (zone->New(sizeof(AstArrayType))) AstArrayType(element)); |
| } |
| |
| static AstArrayType* cast(AstType* type) { |
| DCHECK(IsKind(type, kArray)); |
| return static_cast<AstArrayType*>(FromType(type)); |
| } |
| |
| AstType* element_; |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Superclass for types with variable number of type fields. |
| class AstStructuralType : public AstTypeBase { |
| public: |
| int LengthForTesting() { return Length(); } |
| |
| protected: |
| friend class AstType; |
| |
| int Length() { return length_; } |
| |
| AstType* Get(int i) { |
| DCHECK(0 <= i && i < this->Length()); |
| return elements_[i]; |
| } |
| |
| void Set(int i, AstType* type) { |
| DCHECK(0 <= i && i < this->Length()); |
| elements_[i] = type; |
| } |
| |
| void Shrink(int length) { |
| DCHECK(2 <= length && length <= this->Length()); |
| length_ = length; |
| } |
| |
| AstStructuralType(Kind kind, int length, i::Zone* zone) |
| : AstTypeBase(kind), length_(length) { |
| elements_ = |
| reinterpret_cast<AstType**>(zone->New(sizeof(AstType*) * length)); |
| } |
| |
| private: |
| int length_; |
| AstType** elements_; |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Function types. |
| |
| class AstFunctionType : public AstStructuralType { |
| public: |
| int Arity() { return this->Length() - 2; } |
| AstType* Result() { return this->Get(0); } |
| AstType* Receiver() { return this->Get(1); } |
| AstType* Parameter(int i) { return this->Get(2 + i); } |
| |
| void InitParameter(int i, AstType* type) { this->Set(2 + i, type); } |
| |
| private: |
| friend class AstType; |
| |
| AstFunctionType(AstType* result, AstType* receiver, int arity, Zone* zone) |
| : AstStructuralType(kFunction, 2 + arity, zone) { |
| Set(0, result); |
| Set(1, receiver); |
| } |
| |
| static AstType* New(AstType* result, AstType* receiver, int arity, |
| Zone* zone) { |
| return AsType(new (zone->New(sizeof(AstFunctionType))) |
| AstFunctionType(result, receiver, arity, zone)); |
| } |
| |
| static AstFunctionType* cast(AstType* type) { |
| DCHECK(IsKind(type, kFunction)); |
| return static_cast<AstFunctionType*>(FromType(type)); |
| } |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Tuple types. |
| |
| class AstTupleType : public AstStructuralType { |
| public: |
| int Arity() { return this->Length(); } |
| AstType* Element(int i) { return this->Get(i); } |
| |
| void InitElement(int i, AstType* type) { this->Set(i, type); } |
| |
| private: |
| friend class AstType; |
| |
| AstTupleType(int length, Zone* zone) |
| : AstStructuralType(kTuple, length, zone) {} |
| |
| static AstType* New(int length, Zone* zone) { |
| return AsType(new (zone->New(sizeof(AstTupleType))) |
| AstTupleType(length, zone)); |
| } |
| |
| static AstTupleType* cast(AstType* type) { |
| DCHECK(IsKind(type, kTuple)); |
| return static_cast<AstTupleType*>(FromType(type)); |
| } |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Union types (internal). |
| // A union is a structured type with the following 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 |
| // - no field is a subtype of any other field |
| class AstUnionType : public AstStructuralType { |
| private: |
| friend AstType; |
| friend AstBitsetType; |
| |
| AstUnionType(int length, Zone* zone) |
| : AstStructuralType(kUnion, length, zone) {} |
| |
| static AstType* New(int length, Zone* zone) { |
| return AsType(new (zone->New(sizeof(AstUnionType))) |
| AstUnionType(length, zone)); |
| } |
| |
| static AstUnionType* cast(AstType* type) { |
| DCHECK(IsKind(type, kUnion)); |
| return static_cast<AstUnionType*>(FromType(type)); |
| } |
| |
| bool Wellformed(); |
| }; |
| |
| class AstType { |
| public: |
| typedef AstBitsetType::bitset bitset; // Internal |
| |
| // Constructors. |
| #define DEFINE_TYPE_CONSTRUCTOR(type, value) \ |
| static AstType* type() { return AstBitsetType::New(AstBitsetType::k##type); } |
| AST_PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) |
| #undef DEFINE_TYPE_CONSTRUCTOR |
| |
| static AstType* SignedSmall() { |
| return AstBitsetType::New(AstBitsetType::SignedSmall()); |
| } |
| static AstType* UnsignedSmall() { |
| return AstBitsetType::New(AstBitsetType::UnsignedSmall()); |
| } |
| |
| static AstType* Class(i::Handle<i::Map> map, Zone* zone) { |
| return AstClassType::New(map, zone); |
| } |
| static AstType* Constant(i::Handle<i::Object> value, Zone* zone) { |
| return AstConstantType::New(value, zone); |
| } |
| static AstType* Range(double min, double max, Zone* zone) { |
| return AstRangeType::New(min, max, |
| AST_REPRESENTATION(AstBitsetType::kTagged | |
| AstBitsetType::kUntaggedNumber), |
| zone); |
| } |
| static AstType* Context(AstType* outer, Zone* zone) { |
| return AstContextType::New(outer, zone); |
| } |
| static AstType* Array(AstType* element, Zone* zone) { |
| return AstArrayType::New(element, zone); |
| } |
| static AstType* Function(AstType* result, AstType* receiver, int arity, |
| Zone* zone) { |
| return AstFunctionType::New(result, receiver, arity, zone); |
| } |
| static AstType* Function(AstType* result, Zone* zone) { |
| return Function(result, Any(), 0, zone); |
| } |
| static AstType* Function(AstType* result, AstType* param0, Zone* zone) { |
| AstType* function = Function(result, Any(), 1, zone); |
| function->AsFunction()->InitParameter(0, param0); |
| return function; |
| } |
| static AstType* Function(AstType* result, AstType* param0, AstType* param1, |
| Zone* zone) { |
| AstType* function = Function(result, Any(), 2, zone); |
| function->AsFunction()->InitParameter(0, param0); |
| function->AsFunction()->InitParameter(1, param1); |
| return function; |
| } |
| static AstType* Function(AstType* result, AstType* param0, AstType* param1, |
| AstType* param2, Zone* zone) { |
| AstType* function = Function(result, Any(), 3, zone); |
| function->AsFunction()->InitParameter(0, param0); |
| function->AsFunction()->InitParameter(1, param1); |
| function->AsFunction()->InitParameter(2, param2); |
| return function; |
| } |
| static AstType* Function(AstType* result, int arity, AstType** params, |
| Zone* zone) { |
| AstType* function = Function(result, Any(), arity, zone); |
| for (int i = 0; i < arity; ++i) { |
| function->AsFunction()->InitParameter(i, params[i]); |
| } |
| return function; |
| } |
| static AstType* Tuple(AstType* first, AstType* second, AstType* third, |
| Zone* zone) { |
| AstType* tuple = AstTupleType::New(3, zone); |
| tuple->AsTuple()->InitElement(0, first); |
| tuple->AsTuple()->InitElement(1, second); |
| tuple->AsTuple()->InitElement(2, third); |
| return tuple; |
| } |
| |
| static AstType* Union(AstType* type1, AstType* type2, Zone* zone); |
| static AstType* Intersect(AstType* type1, AstType* type2, Zone* zone); |
| |
| static AstType* Of(double value, Zone* zone) { |
| return AstBitsetType::New( |
| AstBitsetType::ExpandInternals(AstBitsetType::Lub(value))); |
| } |
| static AstType* Of(i::Object* value, Zone* zone) { |
| return AstBitsetType::New( |
| AstBitsetType::ExpandInternals(AstBitsetType::Lub(value))); |
| } |
| static AstType* Of(i::Handle<i::Object> value, Zone* zone) { |
| return Of(*value, zone); |
| } |
| |
| static AstType* For(i::Map* map) { |
| return AstBitsetType::New( |
| AstBitsetType::ExpandInternals(AstBitsetType::Lub(map))); |
| } |
| static AstType* For(i::Handle<i::Map> map) { return For(*map); } |
| |
| // Extraction of components. |
| static AstType* Representation(AstType* t, Zone* zone); |
| static AstType* Semantic(AstType* t, Zone* zone); |
| |
| // Predicates. |
| bool IsInhabited() { return AstBitsetType::IsInhabited(this->BitsetLub()); } |
| |
| bool Is(AstType* that) { return this == that || this->SlowIs(that); } |
| bool Maybe(AstType* that); |
| bool Equals(AstType* that) { return this->Is(that) && that->Is(this); } |
| |
| // Equivalent to Constant(val)->Is(this), but avoiding allocation. |
| bool Contains(i::Object* val); |
| bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } |
| |
| // State-dependent versions of the above that consider subtyping between |
| // a constant and its map class. |
| static AstType* NowOf(i::Object* value, Zone* zone); |
| static AstType* NowOf(i::Handle<i::Object> value, Zone* zone) { |
| return NowOf(*value, zone); |
| } |
| bool NowIs(AstType* that); |
| bool NowContains(i::Object* val); |
| bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); } |
| |
| bool NowStable(); |
| |
| // Inspection. |
| bool IsRange() { return IsKind(AstTypeBase::kRange); } |
| bool IsClass() { return IsKind(AstTypeBase::kClass); } |
| bool IsConstant() { return IsKind(AstTypeBase::kConstant); } |
| bool IsContext() { return IsKind(AstTypeBase::kContext); } |
| bool IsArray() { return IsKind(AstTypeBase::kArray); } |
| bool IsFunction() { return IsKind(AstTypeBase::kFunction); } |
| bool IsTuple() { return IsKind(AstTypeBase::kTuple); } |
| |
| AstClassType* AsClass() { return AstClassType::cast(this); } |
| AstConstantType* AsConstant() { return AstConstantType::cast(this); } |
| AstRangeType* AsRange() { return AstRangeType::cast(this); } |
| AstContextType* AsContext() { return AstContextType::cast(this); } |
| AstArrayType* AsArray() { return AstArrayType::cast(this); } |
| AstFunctionType* AsFunction() { return AstFunctionType::cast(this); } |
| AstTupleType* AsTuple() { return AstTupleType::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(); |
| |
| // Extracts a range from the type: if the type is a range or a union |
| // containing a range, that range is returned; otherwise, NULL is returned. |
| AstType* GetRange(); |
| |
| static bool IsInteger(i::Object* x); |
| static bool IsInteger(double x) { |
| return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. |
| } |
| |
| int NumClasses(); |
| int NumConstants(); |
| |
| template <class T> |
| class Iterator { |
| public: |
| bool Done() const { return index_ < 0; } |
| i::Handle<T> Current(); |
| void Advance(); |
| |
| private: |
| friend class AstType; |
| |
| Iterator() : index_(-1) {} |
| explicit Iterator(AstType* type) : type_(type), index_(-1) { Advance(); } |
| |
| inline bool matches(AstType* type); |
| inline AstType* get_type(); |
| |
| AstType* type_; |
| int index_; |
| }; |
| |
| Iterator<i::Map> Classes() { |
| if (this->IsBitset()) return Iterator<i::Map>(); |
| return Iterator<i::Map>(this); |
| } |
| Iterator<i::Object> Constants() { |
| if (this->IsBitset()) return Iterator<i::Object>(); |
| return Iterator<i::Object>(this); |
| } |
| |
| // Printing. |
| |
| enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM }; |
| |
| void PrintTo(std::ostream& os, PrintDimension dim = BOTH_DIMS); // NOLINT |
| |
| #ifdef DEBUG |
| void Print(); |
| #endif |
| |
| // Helpers for testing. |
| bool IsBitsetForTesting() { return IsBitset(); } |
| bool IsUnionForTesting() { return IsUnion(); } |
| bitset AsBitsetForTesting() { return AsBitset(); } |
| AstUnionType* AsUnionForTesting() { return AsUnion(); } |
| |
| private: |
| // Friends. |
| template <class> |
| friend class Iterator; |
| friend AstBitsetType; |
| friend AstUnionType; |
| |
| // Internal inspection. |
| bool IsKind(AstTypeBase::Kind kind) { |
| return AstTypeBase::IsKind(this, kind); |
| } |
| |
| bool IsNone() { return this == None(); } |
| bool IsAny() { return this == Any(); } |
| bool IsBitset() { return AstBitsetType::IsBitset(this); } |
| bool IsUnion() { return IsKind(AstTypeBase::kUnion); } |
| |
| bitset AsBitset() { |
| DCHECK(this->IsBitset()); |
| return reinterpret_cast<AstBitsetType*>(this)->Bitset(); |
| } |
| AstUnionType* AsUnion() { return AstUnionType::cast(this); } |
| |
| bitset Representation(); |
| |
| // Auxiliary functions. |
| bool SemanticMaybe(AstType* that); |
| |
| bitset BitsetGlb() { return AstBitsetType::Glb(this); } |
| bitset BitsetLub() { return AstBitsetType::Lub(this); } |
| |
| bool SlowIs(AstType* that); |
| bool SemanticIs(AstType* that); |
| |
| static bool Overlap(AstRangeType* lhs, AstRangeType* rhs); |
| static bool Contains(AstRangeType* lhs, AstRangeType* rhs); |
| static bool Contains(AstRangeType* range, AstConstantType* constant); |
| static bool Contains(AstRangeType* range, i::Object* val); |
| |
| static int UpdateRange(AstType* type, AstUnionType* result, int size, |
| Zone* zone); |
| |
| static AstRangeType::Limits IntersectRangeAndBitset(AstType* range, |
| AstType* bits, |
| Zone* zone); |
| static AstRangeType::Limits ToLimits(bitset bits, Zone* zone); |
| |
| bool SimplyEquals(AstType* that); |
| |
| static int AddToUnion(AstType* type, AstUnionType* result, int size, |
| Zone* zone); |
| static int IntersectAux(AstType* type, AstType* other, AstUnionType* result, |
| int size, AstRangeType::Limits* limits, Zone* zone); |
| static AstType* NormalizeUnion(AstType* unioned, int size, Zone* zone); |
| static AstType* NormalizeRangeAndBitset(AstType* range, bitset* bits, |
| Zone* zone); |
| }; |
| |
| // ----------------------------------------------------------------------------- |
| // Type bounds. A simple struct to represent a pair of lower/upper types. |
| |
| struct AstBounds { |
| AstType* lower; |
| AstType* upper; |
| |
| AstBounds() |
| : // Make sure accessing uninitialized bounds crashes big-time. |
| lower(nullptr), |
| upper(nullptr) {} |
| explicit AstBounds(AstType* t) : lower(t), upper(t) {} |
| AstBounds(AstType* l, AstType* u) : lower(l), upper(u) { |
| DCHECK(lower->Is(upper)); |
| } |
| |
| // Unrestricted bounds. |
| static AstBounds Unbounded() { |
| return AstBounds(AstType::None(), AstType::Any()); |
| } |
| |
| // Meet: both b1 and b2 are known to hold. |
| static AstBounds Both(AstBounds b1, AstBounds b2, Zone* zone) { |
| AstType* lower = AstType::Union(b1.lower, b2.lower, zone); |
| AstType* upper = AstType::Intersect(b1.upper, b2.upper, zone); |
| // Lower bounds are considered approximate, correct as necessary. |
| if (!lower->Is(upper)) lower = upper; |
| return AstBounds(lower, upper); |
| } |
| |
| // Join: either b1 or b2 is known to hold. |
| static AstBounds Either(AstBounds b1, AstBounds b2, Zone* zone) { |
| AstType* lower = AstType::Intersect(b1.lower, b2.lower, zone); |
| AstType* upper = AstType::Union(b1.upper, b2.upper, zone); |
| return AstBounds(lower, upper); |
| } |
| |
| static AstBounds NarrowLower(AstBounds b, AstType* t, Zone* zone) { |
| AstType* lower = AstType::Union(b.lower, t, zone); |
| // Lower bounds are considered approximate, correct as necessary. |
| if (!lower->Is(b.upper)) lower = b.upper; |
| return AstBounds(lower, b.upper); |
| } |
| static AstBounds NarrowUpper(AstBounds b, AstType* t, Zone* zone) { |
| AstType* lower = b.lower; |
| AstType* upper = AstType::Intersect(b.upper, t, zone); |
| // Lower bounds are considered approximate, correct as necessary. |
| if (!lower->Is(upper)) lower = upper; |
| return AstBounds(lower, upper); |
| } |
| |
| bool Narrows(AstBounds that) { |
| return that.lower->Is(this->lower) && this->upper->Is(that.upper); |
| } |
| }; |
| |
| } // namespace internal |
| } // namespace v8 |
| |
| #endif // V8_AST_AST_TYPES_H_ |