text: /*
     +----------------------------------------------------------------------+
     | HipHop for PHP                                                       |
     +----------------------------------------------------------------------+
     | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
     +----------------------------------------------------------------------+
     | This source file is subject to version 3.01 of the PHP license,      |
     | that is bundled with this package in the file LICENSE, and is        |
     | available through the world-wide-web at the following url:           |
     | http://www.php.net/license/3_01.txt                                  |
     | If you did not receive a copy of the PHP license and are unable to   |
     | obtain it through the world-wide-web, please send a note to          |
     | license@php.net so we can mail you a copy immediately.               |
     +----------------------------------------------------------------------+
  */
  
  #ifndef incl_HPHP_JIT_TYPE_H_
  #define incl_HPHP_JIT_TYPE_H_
  
  #include "hphp/runtime/base/array-data.h"
  #include "hphp/runtime/base/datatype.h"
  #include "hphp/runtime/base/rds.h"
  #include "hphp/runtime/base/repo-auth-type.h"
  #include "hphp/runtime/vm/class-meth-data-ref.h"
  #include "hphp/runtime/vm/jit/types.h"
  #include "hphp/runtime/vm/jit/type-specialization.h"
  #include "hphp/util/bitset.h"
  #include "hphp/util/low-ptr.h"
  
  #include <folly/Optional.h>
  
  #include <cstdint>
  #include <type_traits>
  
  namespace HPHP {
  ///////////////////////////////////////////////////////////////////////////////
  
  struct ArrayData;
  struct Class;
  struct Func;
  struct StringData;
  struct TypeConstraint;
  struct TypedValue;
  
  namespace jit {
  ///////////////////////////////////////////////////////////////////////////////
  
  struct ProfDataSerializer;
  struct ProfDataDeserializer;
  
  /*
   * The Ptr enum is a lattice that represents the "pointerness" of a type:
   * whether it's a pointer at all, and what kind of location it may point to.
   *
   * We have a pointer kind for each of the major segregated locations in which
   * php values can live (eval stack, frame slots, properties, etc...). For most
   * of the primitive kinds, we have a predefined union of the kind and "inside a
   * Ref", so PtrToRStkGen is exactly the same as PtrTo{Ref|Stk}Gen.  These
   * classify PtrTo* types into some categories that cannot possibly alias,
   * without any smarter analysis needed to prove it.  There is also a union for
   * the various locations things can point after a fully generic member
   * operation (see Memb below).
   *
   * The reason we have the category "Ref|Foo" for each of these Foos is that it
   * is very common to need to do a generic unbox on some value if you have no
   * type information.  For example:
   *
   *     t1 = LdPropAddr ...
   *     t2 = UnboxPtr t1
   *
   * At this point, t2 is a pointer into either an object property or a inner
   * RefData, which will be a PtrToRPropCell, which means it still can't alias,
   * for example, a PtrToStkGen or a PtrToGblGen (although it could generally
   * alias a PtrToRGblGen because both could be inside the same RefData.). Note
   * that PtrToRFooGen is just shorthand for PtrTo{Ref|Foo}Gen.
   *
   * Memb is a number of different locations that result from the more generic
   * types of member operations: Prop, Elem, MIS, MMisc, and Other. MMisc
   * contains something living in a collection instance or object's dynamic
   * property array. Other contains init_null_variant, uninit_variant, or the
   * lvalBlackHole.
   *
   * ClsInit is a pointer to class property initializer data.  These can never be
   * refs, so we don't have a RClsInit type.
   *
   * ClsCns is a pointer to class constant values in RDS.
   *
   * Ptr is a supertype of all Ptr types, Foo is a subtype of RFoo, and Ref is a
   * subtype of RFoo. NotPtr is unrelated to all other types. The hierarchy looks
   * something like this:
   *
   *                            Ptr                            NotPtr
   *                             |
   *         +-------------------+----+--------+-------+
   *         |                        |        |       |
   *       RMemb                      |     ClsInit  ClsCns
   *         |                        |
   *  +------+---------+              |
   *  |      |         |              |
   *  |      |         |              |
   *  |      |         |              |
   *  |      |    +----+-----+        +--------+----- ... etc
   *  |      |    |    |     |        |        |
   *  |    Memb  RMIS RProp RElem   RFrame    RStk
   *  |      |   /  | /   | /|        |  \      | \
   *  |   +--+-+/---|/+   |/ |        |  Frame  |  Stk
   *  |   |    /    / |   /  |        |         |
   *  |   |   /|   /| |  /|  |        |         |
   *  |   |  / |  / | | / |  |        |         |
   *  |   MIS  Prop | Elem|  |        |         |
   *  |             |     |  |        |         |
   *  +-------------+--+--+--+--------+---------+
   *                   |
   *                  Ref
   *
   * Note: if you add a new pointer type, you very likely need to update
   * pointee() in memory-effects.cpp for it to remain correct.
   *
   */
  
  #define PTR_R(f, name, bits, ...)                    \
    f(name, bits, __VA_ARGS__)                         \
    f(R##name, (bits) | Ref, __VA_ARGS__)
  
  #define PTR_NO_R(f, name, bits, ...)            \
    f(name, bits, __VA_ARGS__)
  
  /*
   * Types that can never be refs directly call f; types that can call r with f
   * as an argument. Callers of PTR_TYPES may control whether the Ref cases are
   * actually expanded by passing PTR_R or PTR_NO_R for the r argument. Any
   * arguments passed beyond f and r will be forwarded to f.
   */
  #define PTR_PRIMITIVE(f, r, ...)                         \
    f(Ref,      1U << 0, __VA_ARGS__)                      \
    f(ClsInit,  1U << 1, __VA_ARGS__)                      \
    f(ClsCns,   1U << 2, __VA_ARGS__)                      \
    r(f, Frame, 1U << 3, __VA_ARGS__)                      \
    r(f, Stk,   1U << 4, __VA_ARGS__)                      \
    r(f, Gbl,   1U << 5, __VA_ARGS__)                      \
    r(f, Prop,  1U << 6, __VA_ARGS__)                      \
    r(f, Elem,  1U << 7, __VA_ARGS__)                      \
    r(f, SProp, 1U << 8, __VA_ARGS__)                      \
    r(f, MIS,   1U << 9, __VA_ARGS__)                      \
    r(f, MMisc, 1U << 10, __VA_ARGS__)                     \
    r(f, Other, 1U << 11, __VA_ARGS__)                    \
    /* NotPtr,  1U << 12, declared below */
  
  #define PTR_TYPES(f, r, ...)                             \
    PTR_PRIMITIVE(f, r, __VA_ARGS__)                       \
    r(f, Memb, Prop | Elem | MIS | MMisc | Other, __VA_ARGS__)
  
  enum class Ptr : uint16_t {
    /*
     * The Ptr kinds here are kept out of PTR_TYPES to avoid generating names
     * like TPtrToNotPtrGen or TPtrToPtrGen. Note that those types do exist, just
     * with less ridiculous names: TGen and TPtrToGen, respectively.
     */
    Bottom = 0,
    Top    = 0x1fffU, // Keep this in sync with the number of bits used in
                      // PTR_PRIMITIVE, to keep pretty-printing cleaner.
    NotPtr = 1U << 12,
    Ptr    = Top & ~NotPtr,
  
  #define PTRT(name, bits, ...) name = (bits),
    PTR_TYPES(PTRT, PTR_R)
  #undef PTRT
  };
  
  using ptr_t = std::underlying_type<Ptr>::type;
  constexpr auto kPtrRefBit = static_cast<ptr_t>(Ptr::Ref);
  
  constexpr Ptr operator~(Ptr p) {
    return static_cast<Ptr>(~static_cast<ptr_t>(p));
  }
  constexpr Ptr operator|(Ptr a, Ptr b) {
    return static_cast<Ptr>(static_cast<ptr_t>(a) | static_cast<ptr_t>(b));
  }
  inline Ptr& operator|=(Ptr& a, Ptr b) {
    return a = a | b;
  }
  constexpr Ptr operator&(Ptr a, Ptr b) {
    return static_cast<Ptr>(static_cast<ptr_t>(a) & static_cast<ptr_t>(b));
  }
  inline Ptr& operator&=(Ptr& a, Ptr b) {
    return a = a & b;
  }
  constexpr Ptr operator-(Ptr a, Ptr b) {
    return static_cast<Ptr>(static_cast<ptr_t>(a) & ~static_cast<ptr_t>(b));
  }
  
  constexpr bool operator<=(Ptr a, Ptr b) {
    return (a & b) == a;
  }
  constexpr bool operator>=(Ptr a, Ptr b) {
    return b <= a;
  }
  constexpr bool operator<(Ptr a, Ptr b) {
    return a <= b && a != b;
  }
  constexpr bool operator>(Ptr a, Ptr b) {
    return a >= b && a != b;
  }
  
  ///////////////////////////////////////////////////////////////////////////////
  
  /*
   * Mem is a lattice which supervenes on Ptr describing how to interpret a
   * memory address.
   *
   * Whereas Ptr describes what we know about the memory location, Mem describes
   * what we know about the memory address itself.
   */
  enum class Mem : uint8_t {
    /* Bottom: No other components of the type are compatible with Mem: TCls,
     *         TRDSHandle, etc... */
    Bottom = 0,
    /* NotMem: Normal values like TInt or TGen. */
    NotMem = 1U << 0,
    /* Ptr: TypedValue*: TPtrToInt, TPtrToGen, etc... */
    Ptr    = 1U << 1,
    /* Lval: tv_lval: TLvalToInt, TLvalToGen, etc... */
    Lval   = 1U << 2,
    /* Mem: Either Ptr or Lval. No concrete values can have this type because
     * there is no way to distinguish between TPtrToFoo and TLvalToFoo at
     * runtime. */
    Mem    = Ptr | Lval,
    /* Top: Only used in TTop. */
    Top    = NotMem | Mem,
  };
  
  using mem_t = std::underlying_type<Mem>::type;
  
  constexpr Mem operator~(Mem m) {
    return static_cast<Mem>(~static_cast<mem_t>(m));
  }
  constexpr Mem operator|(Mem a, Mem b) {
    return static_cast<Mem>(static_cast<mem_t>(a) | static_cast<mem_t>(b));
  }
  inline Mem& operator|=(Mem& a, Mem b) {
    return a = a | b;
  }
  constexpr Mem operator&(Mem a, Mem b) {
    return static_cast<Mem>(static_cast<mem_t>(a) & static_cast<mem_t>(b));
  }
  inline Mem& operator&=(Mem& a, Mem b) {
    return a = a & b;
  }
  constexpr Mem operator-(Mem a, Mem b) {
    return static_cast<Mem>(static_cast<mem_t>(a) & ~static_cast<mem_t>(b));
  }
  
  constexpr bool operator<=(Mem a, Mem b) {
    return (a & b) == a;
  }
  constexpr bool operator>=(Mem a, Mem b) {
    return b <= a;
  }
  constexpr bool operator<(Mem a, Mem b) {
    return a <= b && a != b;
  }
  constexpr bool operator>(Mem a, Mem b) {
    return a >= b && a != b;
  }
  
  ///////////////////////////////////////////////////////////////////////////////
  
  /*
   * This section defines a number of macros used to stamp out code and data for
   * all predefined types (types not represented here can be constructed by
   * combining different types). It can be viewed as one big X macro, with
   * different values of X:
   *
   * IRT(name, bits): A plain type, like Bool or Obj.
   * IRTP(name, ptr, bits): A Ptr type, with Mem::Ptr and a custom Ptr.
   * IRTL(name, ptr, bits): An Lval type, with Mem::Lval and a custom Ptr.
   * IRTM(name, ptr, bits): A Mem type, with Mem::Mem and a custom Ptr.
   * IRTX(name, x, bits): A custom memory type, with Mem::x and Ptr::x.
   */
  
  #define IRTP_FROM_PTR(ptr, ptr_bits, name)                    \
    IRTP(PtrTo##ptr##name, ptr, k##name)
  
  #define IRTL_FROM_PTR(ptr, ptr_bits, name)                    \
    IRTL(LvalTo##ptr##name, ptr, k##name)
  
  #define IRTM_FROM_PTR(ptr, ptr_bits, name)                    \
    IRTM(MemTo##ptr##name, ptr, k##name)
  
  #define IRT_BOXES_PTRS_LVALS(name, bits)                      \
    IRT(name,               (bits))                             \
    IRT(Boxed##name,        (bits) << kBoxShift)                \
    IRTP(PtrTo##name,       Ptr, k##name)                       \
    IRTP(PtrToBoxed##name,  Ptr, kBoxed##name)                  \
    PTR_TYPES(IRTP_FROM_PTR, PTR_R, name)                       \
    PTR_TYPES(IRTP_FROM_PTR, PTR_NO_R, Boxed##name)             \
    IRTL(LvalTo##name,      Ptr, k##name)                       \
    IRTL(LvalToBoxed##name, Ptr, kBoxed##name)                  \
    PTR_TYPES(IRTL_FROM_PTR, PTR_R, name)                       \
    PTR_TYPES(IRTL_FROM_PTR, PTR_NO_R, Boxed##name)             \
    IRTM(MemTo##name,       Ptr, k##name)                       \
    IRTM(MemToBoxed##name,  Ptr, kBoxed##name)                  \
    PTR_TYPES(IRTM_FROM_PTR, PTR_R, name)                       \
    PTR_TYPES(IRTM_FROM_PTR, PTR_NO_R, Boxed##name)
  
  #define IRT_PHP(c)                                                      \
    c(Uninit,          bits_t::bit<0>())                                  \
    c(InitNull,        bits_t::bit<1>())                                  \
    c(Bool,            bits_t::bit<2>())                                  \
    c(Int,             bits_t::bit<3>())                                  \
    c(Dbl,             bits_t::bit<4>())                                  \
    c(StaticStr,       bits_t::bit<5>())                                  \
    c(UncountedStr,    bits_t::bit<6>())                                  \
    c(CountedStr,      bits_t::bit<7>())                                  \
    c(StaticArr,       bits_t::bit<8>())                                  \
    c(UncountedArr,    bits_t::bit<9>())                                  \
    c(CountedArr,      bits_t::bit<10>())                                 \
    c(PersistentShape, bits_t::bit<11>())                                 \
    c(CountedShape,    bits_t::bit<12>())                                 \
    c(StaticVec,       bits_t::bit<13>())                                 \
    c(UncountedVec,    bits_t::bit<14>())                                 \
    c(CountedVec,      bits_t::bit<15>())                                 \
    c(StaticDict,      bits_t::bit<16>())                                 \
    c(UncountedDict,   bits_t::bit<17>())                                 \
    c(CountedDict,     bits_t::bit<18>())                                 \
    c(StaticKeyset,    bits_t::bit<19>())                                 \
    c(UncountedKeyset, bits_t::bit<20>())                                 \
    c(CountedKeyset,   bits_t::bit<21>())                                 \
    c(Obj,             bits_t::bit<22>())                                 \
    c(Res,             bits_t::bit<23>())                                 \
    c(Func,            bits_t::bit<24>())                                 \
    c(Cls,             bits_t::bit<25>())                                 \
    c(ClsMeth,         bits_t::bit<26>())                                 \
    c(Record,          bits_t::bit<27>())                                 \
    c(RecType,             bits_t::bit<28>())                                 \
  // Boxed*:           29-57
  
  /*
   * This list should be in non-decreasing order of specificity.
   */
  #ifdef USE_LOWPTR
  #define UNCCOUNTED_INIT_UNION \
          kInitNull|kBool|kInt|kDbl|kPersistent|kFunc|kCls|kRecType|kClsMeth
  #else
  #define UNCCOUNTED_INIT_UNION \
          kInitNull|kBool|kInt|kDbl|kPersistent|kFunc|kCls|kRecType
  #endif
  
  #ifdef USE_LOWPTR
  #define INIT_CELL_UNION kUncountedInit|kStr|kArrLike|kObj|kRes|kRecord
  #else
  #define INIT_CELL_UNION kUncountedInit|kStr|kArrLike|kObj|kRes|kRecord|kClsMeth
  #endif
  
  #define IRT_PHP_UNIONS(c)                                               \
    c(Null,                kUninit|kInitNull)                             \
    c(PersistentStr,       kStaticStr|kUncountedStr)                      \
    c(Str,                 kPersistentStr|kCountedStr)                    \
    c(PersistentArr,       kStaticArr|kUncountedArr)                      \
    c(Arr,                 kPersistentArr|kCountedArr)                    \
    c(Shape,               kPersistentShape|kCountedShape)                \
    c(PersistentVec,       kStaticVec|kUncountedVec)                      \
    c(Vec,                 kPersistentVec|kCountedVec)                    \
    c(PersistentDict,      kStaticDict|kUncountedDict)                    \
    c(Dict,                kPersistentDict|kCountedDict)                  \
    c(PersistentKeyset,    kStaticKeyset|kUncountedKeyset)                \
    c(Keyset,              kPersistentKeyset|kCountedKeyset)              \
    c(PersistentArrLike,   kPersistentArr|kPersistentShape|kPersistentVec|kPersistentDict|kPersistentKeyset) \
    c(ArrLike,             kArr|kShape|kVec|kDict|kKeyset)                \
    c(NullableObj,         kObj|kInitNull|kUninit)                        \
    c(Persistent,          kPersistentStr|kPersistentArrLike)             \
    c(UncountedInit,       UNCCOUNTED_INIT_UNION)                         \
    c(Uncounted,           kUninit|kUncountedInit)                        \
    c(InitCell,            INIT_CELL_UNION)                               \
    c(Cell,                kUninit|kInitCell)
  
  /*
   * Adding a new runtime type needs updating numRuntime variable.
   */
  #define IRT_RUNTIME                                                     \
    IRT(VarEnv,      bits_t::bit<kRuntime>())                             \
    IRT(NamedEntity, bits_t::bit<kRuntime+1>())                           \
    IRT(Cctx,        bits_t::bit<kRuntime+2>()) /* Class* with */         \
                                                /* the lowest bit set,*/  \
                                        /* as stored in ActRec.m_cls field  */ \
    IRT(RetAddr,     bits_t::bit<kRuntime+3>()) /* Return address */      \
    IRT(StkPtr,      bits_t::bit<kRuntime+4>()) /* Stack pointer */       \
    IRT(FramePtr,    bits_t::bit<kRuntime+5>()) /* Frame pointer */       \
    IRT(TCA,         bits_t::bit<kRuntime+6>())                           \
    IRT(ABC,         bits_t::bit<kRuntime+7>()) /* AsioBlockableChain */  \
    IRT(RDSHandle,   bits_t::bit<kRuntime+8>()) /* rds::Handle */         \
    IRT(Nullptr,     bits_t::bit<kRuntime+9>())                           \
    IRT(MIPropSPtr,  bits_t::bit<kRuntime+10>()) /* Ptr to MInstrPropState */ \
    IRT(Smashable,   bits_t::bit<kRuntime+11>()) /* Smashable uint64_t */     \
    IRT(FuncM,       bits_t::bit<kRuntime+12>()) /* Func* with the lowest */  \
                                        /* bit set indicating magic call */
    /* bits above this are unused */
  
  /*
   * Gen, Counted, Init, PtrToGen, etc... are here instead of IRT_PHP_UNIONS
   * because boxing them (e.g., BoxedGen, PtrToBoxedGen) would yield nonsense
   * types.
   */
  #ifdef USE_LOWPTR
  #define COUNTED_INIT_UNION \
    kCountedStr|kCountedArr|kCountedShape|kCountedVec|kCountedDict|kCountedKeyset|kObj|kRes|kBoxedCell|kRecord
  #else
  #define COUNTED_INIT_UNION \
    kCountedStr|kCountedArr|kCountedShape|kCountedVec|kCountedDict|kCountedKeyset|kObj|kRes|kBoxedCell|kRecord|kClsMeth
  #endif
  
  #define IRT_SPECIAL                                           \
    /* Bottom and Top use IRTX to specify a custom Ptr kind */  \
    IRTX(Bottom,       Bottom, kBottom)                         \
    IRTX(Top,          Top,    kTop)                            \
    IRT(Ctx,                   kObj|kCctx)                      \
    IRT(FuncMM,                kFunc|kFuncM)                    \
    IRTX(AnyObj,       Top,    kAnyObj)                         \
    IRTX(AnyArr,       Top,    kAnyArr)                         \
    IRTX(AnyShape,     Top,    kAnyShape)                       \
    IRTX(AnyVec,       Top,    kAnyVec)                         \
    IRTX(AnyDict,      Top,    kAnyDict)                        \
    IRTX(AnyKeyset,    Top,    kAnyKeyset)                      \
    IRTX(AnyArrLike,   Top,    kAnyArrLike)                     \
    IRT(Counted,               COUNTED_INIT_UNION)              \
    IRTP(PtrToCounted,  Ptr,    kCounted)                       \
    IRTL(LvalToCounted, Ptr,    kCounted)                       \
    IRTM(MemToCounted,  Ptr,    kCounted)                       \
    IRT(Gen,                    kCell|kBoxedCell)               \
    IRT(InitGen,                kGen & ~kUninit)                \
    IRTP(PtrToGen,      Ptr,    kGen)                           \
    IRTP(PtrToInitGen,  Ptr,    kInitGen)                       \
    IRTL(LvalToGen,     Ptr,    kGen)                           \
    IRTL(LvalToInitGen, Ptr,    kInitGen)                       \
    IRTM(MemToGen,      Ptr,    kGen)                           \
    IRTM(MemToInitGen,  Ptr,    kInitGen)                       \
    PTR_TYPES(IRTP_FROM_PTR, PTR_R, Gen)                        \
    PTR_TYPES(IRTP_FROM_PTR, PTR_R, InitGen)                    \
    PTR_TYPES(IRTL_FROM_PTR, PTR_R, Gen)                        \
    PTR_TYPES(IRTL_FROM_PTR, PTR_R, InitGen)                    \
    PTR_TYPES(IRTM_FROM_PTR, PTR_R, Gen)                        \
    PTR_TYPES(IRTM_FROM_PTR, PTR_R, InitGen)
  
  /*
   * All types that represent a non-union type.
   */
  #define IRT_PRIMITIVE IRT_PHP(IRT_BOXES_PTRS_LVALS) IRT_RUNTIME
  
  /*
   * All types.
   */
  #define IR_TYPES                        \
    IRT_PHP(IRT_BOXES_PTRS_LVALS)         \
    IRT_PHP_UNIONS(IRT_BOXES_PTRS_LVALS)  \
    IRT_RUNTIME                           \
    IRT_SPECIAL
  
  ///////////////////////////////////////////////////////////////////////////////
  
  struct ConstCctx {
    static ConstCctx cctx(const Class* c) {
      return ConstCctx { reinterpret_cast<uintptr_t>(c) | 0x1 };
    }
  
    const Class* cls() const {
      return reinterpret_cast<const Class*>(m_val & ~0x1);
    }
  
    uintptr_t m_val;
  };
  
  ///////////////////////////////////////////////////////////////////////////////
  
  /*
   * Type is used to represent the types of values in the jit.  Every Type
   * represents a set of types, with TTop being a superset of all Types and
   * TBottom being a subset of all Types.  The elements forming these sets of
   * types come from the types of PHP-visible values (Str, Obj, Int, ...) and
   * runtime-internal types (Func, TCA, ...).
   *
   * Types can be constructed from the predefined constants or by composing
   * existing Types in various ways.  Unions, intersections, and subtractions are
   * all supported, though for implementation-specific reasons certain
   * combinations of specialized types cannot be represented.  A type is
   * considered specialized if it refers to a specific Class or a
   * ArrayData::ArrayKind.  As an example, if A and B are unrelated Classes,
   * Obj<A> | Obj<B> is impossible to represent.  However, if B is a subclass of
   * A, Obj<A> | Obj<B> == Obj<B>, which can be represented as a Type.
   */
  struct Type {
  private:
    static constexpr size_t kBoxShift = 29;
    static constexpr size_t kRuntime = kBoxShift * 2;
    static constexpr size_t numRuntime = 13;
    using bits_t = BitSet<kRuntime + numRuntime>;
  
  public:
    static constexpr bits_t kBottom{};
    static constexpr bits_t kTop = ~kBottom;
  
  #define IRT(name, bits)       static constexpr bits_t k##name = (bits);
  #define IRTP(name, ptr, bits)
  #define IRTL(name, ptr, bits)
  #define IRTM(name, ptr, bits)
  #define IRTX(name, ptr, bits)
      IR_TYPES
  #undef IRT
  #undef IRTP
  #undef IRTL
  #undef IRTM
  #undef IRTX
  
    static constexpr bits_t kAnyArr       = kArr | kBoxedArr;
    static constexpr bits_t kAnyShape     = kShape | kBoxedShape;
    static constexpr bits_t kAnyVec       = kVec | kBoxedVec;
    static constexpr bits_t kAnyDict      = kDict | kBoxedDict;
    static constexpr bits_t kAnyKeyset    = kKeyset | kBoxedKeyset;
    static constexpr bits_t kAnyArrLike   = kAnyArr | kAnyVec | kAnyDict |
                                            kAnyKeyset;
    static constexpr bits_t kArrSpecBits  = kAnyArrLike;
    static constexpr bits_t kAnyObj       = kObj | kBoxedObj;
    static constexpr bits_t kAnyRecord    = kRecord | kBoxedRecord;
    static constexpr bits_t kClsSpecBits  = kAnyObj | kCls;
  
    /////////////////////////////////////////////////////////////////////////////
    // Basic methods.
  
  public:
    /*
     * Default bottom constructor.
     */
    Type();
  
    /*
     * Construct from a predefined set of bits, pointer kind, and mem kind.
     */
    constexpr Type(bits_t bits, Ptr ptr, Mem mem);
  
    /*
     * Hash the Type as a bitfield.
     */
    size_t hash() const;
  
    /*
     * Stringify the Type.
     *
     * constValString: @requires: hasConstVal() ||
     *                            subtypeOfAny(Uninit, InitNull, Nullptr)
     */
    std::string toString() const;
    std::string constValString() const;
    static std::string debugString(Type t);
  
    /*
     * Serialization/deserialization.
     */
    void serialize(ProfDataSerializer&) const;
    static Type deserialize(ProfDataDeserializer&);
  
    /////////////////////////////////////////////////////////////////////////////
    // DataType.
  
    /*
     * Construct from a DataType.
     */
    explicit Type(DataType outer, DataType inner = KindOfUninit);
  
    /*
     * Return true iff there exists a DataType in the range [KindOfUninit,
     * KindOfRef] that represents a non-strict supertype of this type.
     *
     * @requires: *this <= Gen
     */
    bool isKnownDataType() const;
  
    /*
     * Return the most specific DataType that is a supertype of this Type.
     *
     * @requires: isKnownDataType()
     */
    DataType toDataType() const;
  
  
    /////////////////////////////////////////////////////////////////////////////
    // Comparisons.                                                       [const]
  
    /*
     * Return true if this is exactly equal to `rhs'.
     *
     * Be careful---you probably mean `<='.
     */
    bool operator==(Type rhs) const;
    bool operator!=(Type rhs) const;
  
    /*
     * Does this represent a subset (or superset) of `t2'?
     *
     * All operators are implemented in terms of operator==() and operator<=().
     */
    bool operator<=(Type rhs) const;
    bool operator>=(Type rhs) const;
    bool operator<(Type rhs) const;
    bool operator>(Type rhs) const;
  
    /*
     * Is this a non-strict subtype of any among a variadic list of Types?
     */
    template<typename... Types>
    bool subtypeOfAny(Type t2, Types... ts) const;
    bool subtypeOfAny() const;
  
    /*
     * Return true if this has nontrivial intersection with `t2'.
     */
    bool maybe(Type t2) const;
  
  
    /////////////////////////////////////////////////////////////////////////////
    // Combinators.
  
    /*
     * Set operations: union, intersection, and difference.
     *
     * These operations may all return larger types than the "true" union,
     * intersection, or difference.  (They must be conservative in that direction
     * for types that are too hard for us to represent, or we could generate
     * incorrect code by assuming certain possible values are impossible.)
     *
     * Note: operator| and operator& guarantee commutativity; operator- guarantees
     * (a - b) <= a.
     */
    Type operator|(Type other) const;
    Type& operator|=(Type other) { return *this = *this | other; }
  
    Type operator&(Type other) const;
    Type& operator&=(Type other) { return *this = *this & other; }
  
    Type operator-(Type other) const;
    Type& operator-=(Type other) { return *this = *this - other; }
  
    template<typename... Types>
    static Type unionAll(Type t, Types... ts);
    static Type unionAll();
  
  
    /////////////////////////////////////////////////////////////////////////////
    // Is-a methods.                                                      [const]
  
    /*
     * Is this a union type?
     *
     * Note that this is the plain old set definition of union, so TStr,
     * TArr, and TNull will all return true.
     */
    bool isUnion() const;
  
    /*
     * Does this require a register to hold a DataType at runtime?
     */
    bool needsReg() const;
  
    /*
     * Return true if this corresponds to a type that is passed by (value/
     * reference) in C++.
     */
    bool isSimpleType() const;
    bool isReferenceType() const;
  
  
    /////////////////////////////////////////////////////////////////////////////
    // Constant type creation.                                     [const/static]
  
    /*
     * Return a const copy of `ret' with constant value `val'.
     */
    template<typename T>
    static Type cns(T val, Type ret);
  
    /*
     * Return a const type corresponding to `val'.
     *
     * @returns: cns(val, forConst(val))
     */
    template<typename T>
    static Type cns(T val);
  
    /*
     * @returns: TNullptr
     */
    static Type cns(std::nullptr_t);
  
    /*
     * Return a const type for `tv'.
     */
    static Type cns(const TypedValue& tv);
  
    /*
     * If this represents a constant value, return the most specific strict
     * supertype of this we can represent, else return *this.
     *
     * In most cases this just erases the constant value:
     *    Int<4> -> Int
     *    Dbl<2.5> -> Dbl
     *
     * Arrays are special since they can be both constant and specialized, so
     * keep the array's kind in the resulting type.
     */
    Type dropConstVal() const;
  
  
    /////////////////////////////////////////////////////////////////////////////
    // Constant introspection.                                            [const]
  
    /*
     * Does this Type have a constant value?  If true, we can call xxVal().
     *
     * Note: Bottom is a type with no value, and Uninit/InitNull/Nullptr are
     * considered types with a single unique value, so this function returns false
     * for those types.  You may want to explicitly check for them as needed.
     */
    bool hasConstVal() const;
  
    /*
     * @returns: hasConstVal() && *this <= t
     */
    bool hasConstVal(Type t) const;
  
    /*
     * Does this Type represent the constant val `val'?
     *
     * @returns: hasConstVal(cns(val))
     */
    template<typename T>
    bool hasConstVal(T val) const;
  
    /*
     * Whether this Type represents a single possible value.
     *
     * @returns: hasConstVal() || subtypeOfAny(TNullptr, TInitNull, TUninit)
     */
    bool admitsSingleVal() const;
  
    /*
     * Return the const value for a const Type as a uint64_t.
     *
     * @requires: hasConstVal()
     */
    uint64_t rawVal() const;
  
    /*
     * Return the const value for a const Type.
     *
     * @requires: hasConstVal(Type::T)
     */
    bool boolVal() const;
    int64_t intVal() const;
    double dblVal() const;
    const StringData* strVal() const;
    const ArrayData* arrVal() const;
    const ArrayData* vecVal() const;
    const ArrayData* dictVal() const;
    const ArrayData* shapeVal() const;
    const ArrayData* keysetVal() const;
    const HPHP::Func* funcVal() const;
    const Class* clsVal() const;
    ClsMethDataRef clsmethVal() const;
    ConstCctx cctxVal() const;
    rds::Handle rdsHandleVal() const;
    jit::TCA tcaVal() const;
    const TypedValue* ptrVal() const;
  
  
    /////////////////////////////////////////////////////////////////////////////
    // Specialized type creation.                                  [const/static]
  
    /*
     * Return a specialized TArr/TVec/TDict/TKeyset.
     */
    static Type Array(ArrayData::ArrayKind kind);
    static Type Array(const RepoAuthType::Array* rat);
    static Type Array(ArrayData::ArrayKind, const RepoAuthType::Array*);
    static Type Vec(const RepoAuthType::Array*);
    static Type Dict(const RepoAuthType::Array*);
    static Type Shape(const RepoAuthType::Array*);
    static Type Keyset(const RepoAuthType::Array*);
  
    /*
     * Return a specialized TStaticArr/TStaticVec/
     * TStaticDict/TPersistentShape/TStaticKeyset.
     */
    static Type StaticArray(ArrayData::ArrayKind kind);
    static Type StaticArray(const RepoAuthType::Array* rat);
    static Type StaticArray(ArrayData::ArrayKind, const RepoAuthType::Array*);
    static Type StaticVec(const RepoAuthType::Array*);
    static Type StaticDict(const RepoAuthType::Array*);
    static Type StaticShape(ArrayData::ArrayKind kind);
    static Type StaticShape(const RepoAuthType::Array*);
    static Type StaticKeyset(const RepoAuthType::Array*);
  
    /*
     * Return a specialized TObj.
     */
    static Type SubObj(const Class* cls);
    static Type ExactObj(const Class* cls);
  
    static Type ExactCls(const Class* cls);
    static Type SubCls(const Class* cls);
  
    /*
     * Return a copy of this Type with the specialization dropped.
     *
     * @returns: Type(m_bits)
     */
    Type unspecialize() const;
  
    /*
     * Return a copy of this Type with the specialization and staticness
     * dropped.
     *
     * @requires *this <= TInitCell
     */
    Type modified() const;
  
    /////////////////////////////////////////////////////////////////////////////
    // Specialization introspection.                                      [const]
  
    /*
     * Does this Type have a specialization?
     */
    bool isSpecialized() const;
  
    /*
     * Whether this type can meaningfully specialize along `kind'.
     *
     * For example, a Type only supports SpecKind::Class if its bits intersect
     * nontrivially with kAnyObj.
     */
    bool supports(SpecKind kind) const;
  
    /*
     * Return the corresponding type specialization.
     *
     * If the Type is able to support the specialization (i.e., supports()
     * returns true for the corresponding SpecKind), but no specialization is
     * present, Spec::Top will be returned.
     *
     * If supports() would return false for the corresponding SpecKind,
     * Spec::Bottom is returned.
     *
     * The Spec objects cast (explicitly) to true iff they are neither Spec::Top
     * nor Spec::Bottom, so these functions also answer the question, "Is this
     * Type nontrivially specialized along the respective kind?"
     */
    ArraySpec arrSpec() const;
    ClassSpec clsSpec() const;
  
    /*
     * Return a discriminated TypeSpec for this Type's specialization.
     */
    TypeSpec spec() const;
  
  
    /////////////////////////////////////////////////////////////////////////////
    // Inner types.                                                       [const]
  
    /*
     * Box or unbox a Type.
     *
     * The box() and inner() methods are inverses---they (respectively) take the
     * the {Cell, BoxedCell} bits of the Type and coerce them into the
     * {BoxedCell, Cell} sides of the lattice, replacing whatever was there
     * before; e.g.,
     *
     *    box(Int|BoxedDbl)   -> BoxedInt
     *    inner(BoxedInt|Dbl) -> Int
     *
     * Meanwhile, unbox() is like inner(), but rather than replacing the Cell
     * component of the Type, it unions it with the shifted BoxedCell bits, e.g.,
     *
     *    unbox(BoxedInt|Dbl) -> Int|Dbl
     *
     * @requires:
     *    box:    *this <= Cell
     *            !maybe(Uninit) || *this == Cell
     *    inner:  *this <= BoxedCell
     *    unbox:  *this <= Gen
     */
    Type box() const;
    Type inner() const;
    Type unbox() const;
  
    /*
     * Get a pointer to, or dereference, a Type.
     *
     * @requires:
     *    ptr, lval:  *this <= Gen && kind <= Ptr::Ptr
     *    mem:        *this <= Gen && kind <= Ptr::Ptr && mem <= Mem::Mem
     *    deref:      *this <= MemToGen
     *    derefIfPtr: *this <= (Gen | MemToGen)
     */
    Type ptr(Ptr kind) const;
    Type lval(Ptr kind) const;
    Type mem(Mem mem, Ptr kind) const;
    Type deref() const;
    Type derefIfPtr() const;
  
    /*
     * Return a Type stripped of boxing and pointerness.
     */
    Type strip() const;
  
    /*
     * Return the pointer or memory category of a Type.
     */
    Ptr ptrKind() const;
    Mem memKind() const;
  
    /////////////////////////////////////////////////////////////////////////////
    // Internal methods.
  
  private:
    /*
     * Internal constructors.
     */
    Type(bits_t bits, Ptr ptr, Mem mem, bool hasConstVal, uintptr_t extra);
    Type(Type t, ArraySpec arraySpec);
    Type(Type t, ClassSpec classSpec);
  
    /*
     * Bit-pack an `outer' and an `inner' DataType for a Type.
     */
    static bits_t bitsFromDataType(DataType outer, DataType inner);
  
    /*
     * Check invariants and return false if the type is malformed.
     */
    bool checkValid() const;
  
    /*
     * Return a version of *this with the given specialization. If TypeSpec
     * contains both kinds of specialization or *this supports both types of
     * specialization, the resulting type will not be specialized at all. Any
     * constant value in *this will be dropped if the specialization is
     * applied. *this must support any specializations present in the given
     * TypeSpec.
     */
    Type specialize(TypeSpec) const;
  
    /*
     * Do the given bits support a specific kind of specialization?
     */
    static bool supports(bits_t, SpecKind kind);
  
    /////////////////////////////////////////////////////////////////////////////
    // Data members.
  
  private:
    bits_t m_bits;
    Ptr m_ptr;
    Mem m_mem;
    bool m_hasConstVal;
  
    union {
      uintptr_t m_extra;
  
      // Constant values.  Validity determined by m_hasConstVal and m_bits.
      bool m_boolVal;
      int64_t m_intVal;
      double m_dblVal;
      const StringData* m_strVal;
      const ArrayData* m_arrVal;
      const ArrayData* m_vecVal;
      const ArrayData* m_dictVal;
      const ArrayData* m_shapeVal;
      const ArrayData* m_keysetVal;
      const HPHP::Func* m_funcVal;
      const Class* m_clsVal;
      ClsMethDataRef m_clsmethVal;
      ConstCctx m_cctxVal;
      jit::TCA m_tcaVal;
      rds::Handle m_rdsHandleVal;
      TypedValue* m_ptrVal;
  
      // Specializations for object classes and arrays.
      ClassSpec m_clsSpec;
      ArraySpec m_arrSpec;
    };
  };
  
  using OptType = folly::Optional<Type>;
  
  /////////////////////////////////////////////////////////////////////////////
  
  /*
   * Return the most refined Type that can be used to represent the type of a
   * live TypedValue or a RepoAuthType.
   */
  Type typeFromTV(tv_rval tv, const Class* ctx);
  Type typeFromRAT(RepoAuthType ty, const Class* ctx);
  Type typeFromPropTC(const HPHP::TypeConstraint& tc,
                      const Class* propCls,
                      const Class* ctx,
                      bool isSProp);
  
  ///////////////////////////////////////////////////////////////////////////////
  
  /*
   * Return the boxed version of the input type, taking into account PHP
   * semantics and subtle implementation details.
   */
  Type boxType(Type);
  
  /*
   * Return the dest type for a LdRef with the given typeParam.
   *
   * @requires: typeParam <= TCell
   */
  Type ldRefReturn(Type typeParam);
  
  /*
   * Returns the type that a value may have if it had type `srcType' and failed a
   * CheckType with `typeParam'.  Not all typeParams for CheckTypes are precise,
   * so the return value may even be `srcType' itself in some situations.
   */
  Type negativeCheckType(Type typeParam, Type srcType);
  
  /*
   * Returns the least specific supertype of `t' that maintains the properties
   * required by `cat'.
   */
  Type relaxType(Type t, DataTypeCategory cat);
  
  /*
   * Returns the smallest supertype of ty that we can reasonably guard on. Used
   * for checking inner ref cells and locals in pseudomains.
   */
  Type relaxToGuardable(Type ty);
  
  ///////////////////////////////////////////////////////////////////////////////
  
  }}
  
  ///////////////////////////////////////////////////////////////////////////////
  
  namespace std {
    template<> struct hash<HPHP::jit::Type> {
      size_t operator()(HPHP::jit::Type t) const { return t.hash(); }
    };
  }
  
  ///////////////////////////////////////////////////////////////////////////////
  
  #define incl_HPHP_JIT_TYPE_INL_H_
  #include "hphp/runtime/vm/jit/type-inl.h"
  #undef incl_HPHP_JIT_TYPE_INL_H_
  
  #endif
  