types.h

// 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_COMPILER_TYPES_H_
#define V8_COMPILER_TYPES_H_

#include "src/base/compiler-specific.h"
#include "src/compiler/js-heap-broker.h"
#include "src/conversions.h"
#include "src/globals.h"
#include "src/handles.h"
#include "src/objects.h"
#include "src/ostreams.h"

namespace v8 {
namespace internal {
namespace compiler {

// 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).
//
// The following equations and inequations hold:
//
//   None <= T
//   T <= Any
//
//   Number = Signed32 \/ Unsigned32 \/ Double
//   Smi <= Signed32
//   Name = String \/ Symbol
//   UniqueName = InternalizedString \/ Symbol
//   InternalizedString < String
//
//   Receiver = Object \/ Proxy
//   OtherUndetectable < Object
//   DetectableReceiver = Receiver - OtherUndetectable
//
//   Constant(x) < T  iff instance_type(map(x)) < T
//
//
// 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. Only structured types require
// allocation.

// -----------------------------------------------------------------------------
// Values for bitset types

// clang-format off

#define INTERNAL_BITSET_TYPE_LIST(V)                                      \
  V(OtherUnsigned31, 1u << 1)  \
  V(OtherUnsigned32, 1u << 2)  \
  V(OtherSigned32,   1u << 3)  \
  V(OtherNumber,     1u << 4)  \
  V(OtherString,     1u << 5)  \

#define PROPER_BITSET_TYPE_LIST(V) \
  V(None,                     0u)        \
  V(Negative31,               1u << 6)   \
  V(Null,                     1u << 7)   \
  V(Undefined,                1u << 8)   \
  V(Boolean,                  1u << 9)   \
  V(Unsigned30,               1u << 10)   \
  V(MinusZero,                1u << 11)  \
  V(NaN,                      1u << 12)  \
  V(Symbol,                   1u << 13)  \
  V(InternalizedString,       1u << 14)  \
  V(OtherCallable,            1u << 16)  \
  V(OtherObject,              1u << 17)  \
  V(OtherUndetectable,        1u << 18)  \
  V(CallableProxy,            1u << 19)  \
  V(OtherProxy,               1u << 20)  \
  V(Function,                 1u << 21)  \
  V(BoundFunction,            1u << 22)  \
  V(Hole,                     1u << 23)  \
  V(OtherInternal,            1u << 24)  \
  V(ExternalPointer,          1u << 25)  \
  V(Array,                    1u << 26)  \
  V(BigInt,                   1u << 27)  \
  \
  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(Integral32OrMinusZero,        kIntegral32 | kMinusZero) \
  V(Integral32OrMinusZeroOrNaN,   kIntegral32OrMinusZero | kNaN) \
  V(PlainNumber,                  kIntegral32 | kOtherNumber) \
  V(OrderedNumber,                kPlainNumber | kMinusZero) \
  V(MinusZeroOrNaN,               kMinusZero | kNaN) \
  V(Number,                       kOrderedNumber | kNaN) \
  V(Numeric,                      kNumber | kBigInt) \
  V(String,                       kInternalizedString | kOtherString) \
  V(UniqueName,                   kSymbol | kInternalizedString) \
  V(Name,                         kSymbol | kString) \
  V(InternalizedStringOrNull,     kInternalizedString | kNull) \
  V(BooleanOrNumber,              kBoolean | kNumber) \
  V(BooleanOrNullOrNumber,        kBooleanOrNumber | kNull) \
  V(BooleanOrNullOrUndefined,     kBoolean | kNull | kUndefined) \
  V(Oddball,                      kBooleanOrNullOrUndefined | kHole) \
  V(NullOrNumber,                 kNull | kNumber) \
  V(NullOrUndefined,              kNull | kUndefined) \
  V(Undetectable,                 kNullOrUndefined | kOtherUndetectable) \
  V(NumberOrHole,                 kNumber | kHole) \
  V(NumberOrOddball,              kNumber | kNullOrUndefined | kBoolean | \
                                  kHole) \
  V(NumericOrString,              kNumeric | kString) \
  V(NumberOrUndefined,            kNumber | kUndefined) \
  V(NumberOrUndefinedOrNullOrBoolean,  \
                                  kNumber | kNullOrUndefined | kBoolean) \
  V(PlainPrimitive,               kNumber | kString | kBoolean | \
                                  kNullOrUndefined) \
  V(NonBigIntPrimitive,           kSymbol | kPlainPrimitive) \
  V(Primitive,                    kBigInt | kNonBigIntPrimitive) \
  V(OtherUndetectableOrUndefined, kOtherUndetectable | kUndefined) \
  V(Proxy,                        kCallableProxy | kOtherProxy) \
  V(ArrayOrOtherObject,           kArray | kOtherObject) \
  V(ArrayOrProxy,                 kArray | kProxy) \
  V(DetectableCallable,           kFunction | kBoundFunction | \
                                  kOtherCallable | kCallableProxy) \
  V(Callable,                     kDetectableCallable | kOtherUndetectable) \
  V(NonCallable,                  kArray | kOtherObject | kOtherProxy) \
  V(NonCallableOrNull,            kNonCallable | kNull) \
  V(DetectableObject,             kArray | kFunction | kBoundFunction | \
                                  kOtherCallable | kOtherObject) \
  V(DetectableReceiver,           kDetectableObject | kProxy) \
  V(DetectableReceiverOrNull,     kDetectableReceiver | kNull) \
  V(Object,                       kDetectableObject | kOtherUndetectable) \
  V(Receiver,                     kObject | kProxy) \
  V(ReceiverOrUndefined,          kReceiver | kUndefined) \
  V(ReceiverOrNullOrUndefined,    kReceiver | kNull | kUndefined) \
  V(SymbolOrReceiver,             kSymbol | kReceiver) \
  V(StringOrReceiver,             kString | kReceiver) \
  V(Unique,                       kBoolean | kUniqueName | kNull | \
                                  kUndefined | kReceiver) \
  V(Internal,                     kHole | kExternalPointer | kOtherInternal) \
  V(NonInternal,                  kPrimitive | kReceiver) \
  V(NonBigInt,                    kNonBigIntPrimitive | kReceiver) \
  V(NonNumber,                    kBigInt | 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 BITSET_TYPE_LIST(V)    \
  INTERNAL_BITSET_TYPE_LIST(V) \
  PROPER_BITSET_TYPE_LIST(V)

class HeapConstantType;
class OtherNumberConstantType;
class TupleType;
class Type;
class UnionType;

// -----------------------------------------------------------------------------
// Bitset types (internal).

class V8_EXPORT_PRIVATE BitsetType {
 public:
  typedef uint32_t bitset;  // Internal

  enum : uint32_t {
#define DECLARE_TYPE(type, value) k##type = (value),
    BITSET_TYPE_LIST(DECLARE_TYPE)
#undef DECLARE_TYPE
        kUnusedEOL = 0
  };

  static bitset SignedSmall();
  static bitset UnsignedSmall();

  static bool IsNone(bitset bits) { return bits == kNone; }

  static bool Is(bitset bits1, bitset bits2) {
    return (bits1 | bits2) == bits2;
  }

  static double Min(bitset);
  static double Max(bitset);

  static bitset Glb(double min, double max);
  static bitset Lub(HeapObjectType const& type) {
    return Lub<HeapObjectType>(type);
  }
  static bitset Lub(MapRef const& map) { return Lub<MapRef>(map); }
  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);

 private:
  struct Boundary {
    bitset internal;
    bitset external;
    double min;
  };
  static const Boundary BoundariesArray[];
  static inline const Boundary* Boundaries();
  static inline size_t BoundariesSize();

  template <typename MapRefLike>
  static bitset Lub(MapRefLike const& map);
};

// -----------------------------------------------------------------------------
// Superclass for non-bitset types (internal).
class TypeBase {
 protected:
  friend class Type;

  enum Kind { kHeapConstant, kOtherNumberConstant, kTuple, kUnion, kRange };

  Kind kind() const { return kind_; }
  explicit TypeBase(Kind kind) : kind_(kind) {}

  static bool IsKind(Type type, Kind kind);

 private:
  Kind kind_;
};

// -----------------------------------------------------------------------------
// Range types.

class RangeType : public TypeBase {
 public:
  struct Limits {
    double min;
    double max;
    Limits(double min, double max) : min(min), max(max) {}
    explicit Limits(const RangeType* 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() const { return limits_.min; }
  double Max() const { return limits_.max; }

  static bool IsInteger(double x) {
    return nearbyint(x) == x && !IsMinusZero(x);  // Allows for infinities.
  }

 private:
  friend class Type;
  friend class BitsetType;
  friend class UnionType;

  static RangeType* New(double min, double max, Zone* zone) {
    return New(Limits(min, max), zone);
  }

  static RangeType* New(Limits lim, Zone* zone) {
    DCHECK(IsInteger(lim.min) && IsInteger(lim.max));
    DCHECK(lim.min <= lim.max);
    BitsetType::bitset bits = BitsetType::Lub(lim.min, lim.max);

    return new (zone->New(sizeof(RangeType))) RangeType(bits, lim);
  }

  RangeType(BitsetType::bitset bitset, Limits limits)
      : TypeBase(kRange), bitset_(bitset), limits_(limits) {}

  BitsetType::bitset Lub() const { return bitset_; }

  BitsetType::bitset bitset_;
  Limits limits_;
};

// -----------------------------------------------------------------------------
// The actual type.

class V8_EXPORT_PRIVATE Type {
 public:
  typedef BitsetType::bitset bitset;  // Internal

// Constructors.
#define DEFINE_TYPE_CONSTRUCTOR(type, value) \
  static Type type() { return NewBitset(BitsetType::k##type); }
  PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
#undef DEFINE_TYPE_CONSTRUCTOR

  Type() : payload_(0) {}

  static Type SignedSmall() { return NewBitset(BitsetType::SignedSmall()); }
  static Type UnsignedSmall() { return NewBitset(BitsetType::UnsignedSmall()); }

  static Type OtherNumberConstant(double value, Zone* zone);
  static Type HeapConstant(JSHeapBroker* broker, Handle<i::Object> value,
                           Zone* zone);
  static Type HeapConstant(const HeapObjectRef& value, Zone* zone);
  static Type Range(double min, double max, Zone* zone);
  static Type Range(RangeType::Limits lims, Zone* zone);
  static Type Tuple(Type first, Type second, Type third, Zone* zone);
  static Type Union(int length, Zone* zone);

  // NewConstant is a factory that returns Constant, Range or Number.
  static Type NewConstant(JSHeapBroker* broker, Handle<i::Object> value,
                          Zone* zone);
  static Type NewConstant(double value, Zone* zone);

  static Type Union(Type type1, Type type2, Zone* zone);
  static Type Intersect(Type type1, Type type2, Zone* zone);

  static Type For(HeapObjectType const& type) {
    return NewBitset(BitsetType::ExpandInternals(BitsetType::Lub(type)));
  }
  static Type For(MapRef const& type) {
    return NewBitset(BitsetType::ExpandInternals(BitsetType::Lub(type)));
  }

  // Predicates.
  bool IsNone() const { return payload_ == None().payload_; }
  bool IsInvalid() const { return payload_ == 0u; }

  bool Is(Type that) const {
    return payload_ == that.payload_ || this->SlowIs(that);
  }
  bool Maybe(Type that) const;
  bool Equals(Type that) const { return this->Is(that) && that.Is(*this); }

  // Inspection.
  bool IsBitset() const { return payload_ & 1; }
  bool IsRange() const { return IsKind(TypeBase::kRange); }
  bool IsHeapConstant() const { return IsKind(TypeBase::kHeapConstant); }
  bool IsOtherNumberConstant() const {
    return IsKind(TypeBase::kOtherNumberConstant);
  }
  bool IsTuple() const { return IsKind(TypeBase::kTuple); }

  const HeapConstantType* AsHeapConstant() const;
  const OtherNumberConstantType* AsOtherNumberConstant() const;
  const RangeType* AsRange() const;
  const TupleType* AsTuple() const;

  // Minimum and maximum of a numeric type.
  // These functions do not distinguish between -0 and +0.  NaN is ignored.
  // Only call them on subtypes of Number whose intersection with OrderedNumber
  // is not empty.
  double Min() const;
  double Max() const;

  // Extracts a range from the type: if the type is a range or a union
  // containing a range, that range is returned; otherwise, nullptr is returned.
  Type GetRange() const;

  int NumConstants() const;

  static Type Invalid() { return Type(); }

  bool operator==(Type other) const { return payload_ == other.payload_; }
  bool operator!=(Type other) const { return payload_ != other.payload_; }

  // Printing.

  void PrintTo(std::ostream& os) const;

#ifdef DEBUG
  void Print() const;
#endif

  // Helpers for testing.
  bool IsUnionForTesting() { return IsUnion(); }
  bitset AsBitsetForTesting() { return AsBitset(); }
  const UnionType* AsUnionForTesting() { return AsUnion(); }
  Type BitsetGlbForTesting() { return NewBitset(BitsetGlb()); }
  Type BitsetLubForTesting() { return NewBitset(BitsetLub()); }

 private:
  // Friends.
  template <class>
  friend class Iterator;
  friend BitsetType;
  friend UnionType;
  friend size_t hash_value(Type type);

  Type(bitset bits) : payload_(bits | 1u) {}
  Type(TypeBase* type_base)
      : payload_(reinterpret_cast<uintptr_t>(type_base)) {}

  // Internal inspection.
  bool IsKind(TypeBase::Kind kind) const {
    if (IsBitset()) return false;
    const TypeBase* base = ToTypeBase();
    return base->kind() == kind;
  }

  const TypeBase* ToTypeBase() const {
    return reinterpret_cast<TypeBase*>(payload_);
  }
  static Type FromTypeBase(TypeBase* type) { return Type(type); }

  bool IsAny() const { return payload_ == Any().payload_; }
  bool IsUnion() const { return IsKind(TypeBase::kUnion); }

  bitset AsBitset() const {
    DCHECK(IsBitset());
    return static_cast<bitset>(payload_) ^ 1u;
  }

  const UnionType* AsUnion() const;

  bitset BitsetGlb() const;  // greatest lower bound that's a bitset
  bitset BitsetLub() const;  // least upper bound that's a bitset

  bool SlowIs(Type that) const;

  static Type NewBitset(bitset bits) { return Type(bits); }

  static bool Overlap(const RangeType* lhs, const RangeType* rhs);
  static bool Contains(const RangeType* lhs, const RangeType* rhs);

  static int UpdateRange(Type type, UnionType* result, int size, Zone* zone);

  static RangeType::Limits IntersectRangeAndBitset(Type range, Type bits,
                                                   Zone* zone);
  static RangeType::Limits ToLimits(bitset bits, Zone* zone);

  bool SimplyEquals(Type that) const;

  static int AddToUnion(Type type, UnionType* result, int size, Zone* zone);
  static int IntersectAux(Type type, Type other, UnionType* result, int size,
                          RangeType::Limits* limits, Zone* zone);
  static Type NormalizeUnion(UnionType* unioned, int size, Zone* zone);
  static Type NormalizeRangeAndBitset(Type range, bitset* bits, Zone* zone);

  // If LSB is set, the payload is a bitset; if LSB is clear, the payload is
  // a pointer to a subtype of the TypeBase class.
  uintptr_t payload_;
};

inline size_t hash_value(Type type) { return type.payload_; }
V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os, Type type);

// -----------------------------------------------------------------------------
// Constant types.

class OtherNumberConstantType : public TypeBase {
 public:
  double Value() const { return value_; }

  static bool IsOtherNumberConstant(double value);

 private:
  friend class Type;
  friend class BitsetType;

  static OtherNumberConstantType* New(double value, Zone* zone) {
    return new (zone->New(sizeof(OtherNumberConstantType)))
        OtherNumberConstantType(value);  // NOLINT
  }

  explicit OtherNumberConstantType(double value)
      : TypeBase(kOtherNumberConstant), value_(value) {
    CHECK(IsOtherNumberConstant(value));
  }

  BitsetType::bitset Lub() const { return BitsetType::kOtherNumber; }

  double value_;
};

class V8_EXPORT_PRIVATE HeapConstantType : public NON_EXPORTED_BASE(TypeBase) {
 public:
  Handle<HeapObject> Value() const;
  const HeapObjectRef& Ref() const { return heap_ref_; }

 private:
  friend class Type;
  friend class BitsetType;

  static HeapConstantType* New(const HeapObjectRef& heap_ref, Zone* zone) {
    DCHECK(!heap_ref.IsHeapNumber());
    DCHECK_IMPLIES(heap_ref.IsString(), heap_ref.IsInternalizedString());
    BitsetType::bitset bitset = BitsetType::Lub(heap_ref.GetHeapObjectType());
    return new (zone->New(sizeof(HeapConstantType)))
        HeapConstantType(bitset, heap_ref);
  }

  HeapConstantType(BitsetType::bitset bitset, const HeapObjectRef& heap_ref);

  BitsetType::bitset Lub() const { return bitset_; }

  BitsetType::bitset bitset_;
  HeapObjectRef heap_ref_;
};

// -----------------------------------------------------------------------------
// Superclass for types with variable number of type fields.
class StructuralType : public TypeBase {
 public:
  int LengthForTesting() const { return Length(); }

 protected:
  friend class Type;

  int Length() const { return length_; }

  Type Get(int i) const {
    DCHECK(0 <= i && i < this->Length());
    return elements_[i];
  }

  void Set(int i, Type type) {
    DCHECK(0 <= i && i < this->Length());
    elements_[i] = type;
  }

  void Shrink(int length) {
    DCHECK(2 <= length && length <= this->Length());
    length_ = length;
  }

  StructuralType(Kind kind, int length, Zone* zone)
      : TypeBase(kind), length_(length) {
    elements_ = reinterpret_cast<Type*>(zone->New(sizeof(Type) * length));
  }

 private:
  int length_;
  Type* elements_;
};

// -----------------------------------------------------------------------------
// Tuple types.

class TupleType : public StructuralType {
 public:
  int Arity() const { return this->Length(); }
  Type Element(int i) const { return this->Get(i); }

  void InitElement(int i, Type type) { this->Set(i, type); }

 private:
  friend class Type;

  TupleType(int length, Zone* zone) : StructuralType(kTuple, length, zone) {}

  static TupleType* New(int length, Zone* zone) {
    return new (zone->New(sizeof(TupleType))) TupleType(length, zone);
  }
};

// -----------------------------------------------------------------------------
// 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 UnionType : public StructuralType {
 private:
  friend Type;
  friend BitsetType;

  UnionType(int length, Zone* zone) : StructuralType(kUnion, length, zone) {}

  static UnionType* New(int length, Zone* zone) {
    return new (zone->New(sizeof(UnionType))) UnionType(length, zone);
  }

  bool Wellformed() const;
};

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_TYPES_H_