take &self

[hiphop-php.git] / hphp / hhbbc / type-system.h

/*
   +----------------------------------------------------------------------+
   | 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_HHBBC_TYPE_SYSTEM_H_
#define incl_HHBBC_TYPE_SYSTEM_H_

#include <cstdint>
#include <vector>
#include <utility>

#include <folly/Optional.h>

#include "hphp/util/copy-ptr.h"
#include "hphp/util/low-ptr.h"

#include "hphp/runtime/base/repo-auth-type.h"
#include "hphp/runtime/base/repo-auth-type-array.h"
#include "hphp/runtime/base/array-provenance.h"

#include "hphp/hhbbc/array-like-map.h"
#include "hphp/hhbbc/index.h"
#include "hphp/hhbbc/misc.h"

namespace HPHP { namespace HHBBC {

struct Type;

//////////////////////////////////////////////////////////////////////

/*
 * Type system.
 *
 * Here's an unmaintainable ascii-art diagram:
 *
 *                      Top
 *                       |
 *                 +-----+
 *                 |     |             InitCell := Cell - Uninit
 *                Cls    |                   ?X := X + InitNull
 *                 |     |
 *              Cls<=c  Cell
 *                 |     |
 *              Cls=c    +-------------+--------+-------+-------+-----+
 *                       |             |        |       |       |     |
 *                      Unc            |        |      Obj     Res   Record
 *                       | \           |        |      /  \
 *                       |  \          |        |  Obj<=c Obj<=WaitHandle
 *                     Prim  \         |        |    |       |
 *                     / |   InitUnc   |        |  Obj=c   WaitH<T>
 *                    /  |   /  |  |   |        |
 *                   /   |  /   |  |   |        |
 *                  /    | /    |  |   |        |
 *                 /     |/     |  |   |        |
 *              Null  InitPrim  |  |   |        |
 *             /  |    / |      |  |  Arr      Str
 *            /   |   /  |      |  |  / \      / \
 *      Uninit  InitNull |      | SArr  ...   /  CStr
 *                       |      |  |         /
 *                       |      | ...       /
 *                       |      |          /
 *                       |      \         /
 *                       |       \       /
 *                       |        \     /
 *                       |         \   /
 *                       |          SStr
 *                       |           |
 *                       |         SStr=s
 *                       |
 *                       +----------+
 *                       |          |
 *                      Bool       Num
 *                      /  \       |  \
 *                   True  False  Int  Dbl
 *                                 |    |
 *                               Int=n Dbl=n
 *
 * Some notes on some of the basic types:
 *
 *   {Init,}Prim
 *
 *       "Primitive" types---these can be represented in a TypedValue without a
 *       pointer to the heap.
 *
 *   {Init,}Unc
 *
 *       "Uncounted" types---values of these types don't require reference
 *       counting.
 *
 *   WaitH<T>
 *
 *       A WaitHandle that is known will either return a value of type T from
 *       its join() method (or Await), or else throw an exception.
 *
 * Array types:
 *
 *   Arrays are divided along two dimensions: counted or uncounted, and empty
 *   or non-empty.  Unions of either are allowed.  The naming convention is
 *   {S,C,}Arr{N,E,}, where leaving out either bit means it's unknown along
 *   that dimension.  All arrays are subtypes of the Arr type.  The lattice
 *   here looks like this:
 *
 *                         Arr
 *                          |
 *                  +----+--+--+---+
 *                  |    |     |   |
 *                  |  SArr   CArr |
 *                  |   |      |   |
 *              +-------+---------------+
 *              |   |          |   |    |
 *              |  ArrN  +-----+  ArrE  |
 *              | /   \  |     | /   \  |
 *             SArrN  CArrN   CArrE  SArrE
 *
 *   NOTE: Having SArr be a sibling of CArr is problematic. There is
 *   an assumption that types in the index only ever get more refined,
 *   but eg we might "know" that a type is CArr early on (because eg
 *   we stored a value to it, thus modifying it), but later we might
 *   know the value both before and after the modification, and just
 *   replace each with a static array. In fact, this is almost
 *   guaranteed to happen when building arrays from constants (not
 *   literals), because on the first pass we won't know the constant
 *   values, and will produce a CArr, but eventually we could figure
 *   them out, and produce an SArr. This means that in practice, we
 *   can't use CArr anywhere, because it might be improved to SArr,
 *   which is not a subtype. Even if we only generated CArr after all
 *   modifications are done (eg during the insert-assertions phase) we
 *   could still run into problems where we annotate an array as CArr
 *   but jit time analysis/optimization was able to produce a static
 *   array - so it doesn't appear to be useful, except as a superclass
 *   of SArr.
 *
 *   "Specialized" array types may be found as subtypes of any of the above
 *   types except SArrE and CArrE, or of optional versions of the above types
 *   (e.g. as a subtype of ?ArrN).  The information about additional structure
 *   is dispayed in parenthesis, and probably best explained by some examples:
 *
 *     SArrN(Bool,Int)
 *
 *         Tuple-like static two-element array, with integer keys 0 and 1,
 *         containing a Bool and an Int with unknown values.
 *
 *     Arr(Int,Dbl)
 *
 *         An array of unknown countedness that is either empty, or a
 *         tuple-like array with two elements of types Int and Dbl.
 *
 *     CArrN([Bool])
 *
 *         Non-empty reference counted array with contiguous zero-based integer
 *         keys, unknown size, values all are subtypes of Bool.
 *
 *     ArrN(x:Int,y:Int)
 *
 *         Struct-like array with known fields "x" and "y" that have Int
 *         values, and no other fields.  Struct-like arrays always have known
 *         string keys, and the type contains only those array values with
 *         exactly the given key set, in the order specified.
 *
 *     Arr([SStr:InitCell])
 *
 *         Possibly empty map-like array with unknown keys, but all
 *         non-reference counted strings, all values InitCell.  In this case
 *         the array itself may or may not be static.
 *
 *         Note that struct-like arrays will be subtypes of map-like arrays
 *         with string keys.
 *
 *     ArrN([Int:InitPrim])
 *
 *         Map-like array with only integer keys (not-necessarily contiguous)
 *         and values that are all subtypes of InitPrim.  Note that the keys
 *         *may* be contiguous integers, so for example Arr([InitPrim]) <:
 *         Arr([Int => InitPrim]).
 *
 *     Arr([ArrKey:InitCell])
 *
 *         Map-like array with either integer or string keys, and InitCell
 *         values, or empty.  Essentially this is the most generic array that
 *         can't contain php references.
 */

//////////////////////////////////////////////////////////////////////

enum trep : uint64_t {
  BBottom   = 0,

  BUninit   = 1ULL << 0,
  BInitNull = 1ULL << 1,
  BFalse    = 1ULL << 2,
  BTrue     = 1ULL << 3,
  BInt      = 1ULL << 4,
  BDbl      = 1ULL << 5,
  BSStr     = 1ULL << 6,  // static string
  BCStr     = 1ULL << 7,  // counted string
  BFunc     = 1ULL << 8,

  BSPArrE   = 1ULL << 9, // static empty "plain" array
  BCPArrE   = 1ULL << 10, // counted empty "plain" array
  BSPArrN   = 1ULL << 11, // static non-empty "plain" array
  BCPArrN   = 1ULL << 12ULL, // counted non-empty "plain array"

  BSVArrE   = 1ULL << 13, // static empty varray
  BCVArrE   = 1ULL << 14, // counted empty varray
  BSVArrN   = 1ULL << 15, // static non-empty varray
  BCVArrN   = 1ULL << 16, // counted non-empty varray

  BSDArrE   = 1ULL << 17, // static empty darray
  BCDArrE   = 1ULL << 18, // counted empty darray
  BSDArrN   = 1ULL << 19, // static non-empty darray
  BCDArrN   = 1ULL << 20, // counted non-empty darray

  BClsMeth  = 1ULL << 21, // ClassMethod

  BObj      = 1ULL << 22,
  BRes      = 1ULL << 23,
  BCls      = 1ULL << 24,

  BSVecE    = 1ULL << 25, // static empty vec
  BCVecE    = 1ULL << 26, // counted empty vec
  BSVecN    = 1ULL << 27, // static non-empty vec
  BCVecN    = 1ULL << 28, // counted non-empty vec
  BSDictE   = 1ULL << 29, // static empty dict
  BCDictE   = 1ULL << 30, // counted empty dict
  BSDictN   = 1ULL << 31, // static non-empty dict
  BCDictN   = 1ULL << 32, // counted non-empty dict
  BSKeysetE = 1ULL << 33, // static empty keyset
  BCKeysetE = 1ULL << 34, // counted empty keyset
  BSKeysetN = 1ULL << 35, // static non-empty keyset
  BCKeysetN = 1ULL << 36, // counted non-empty keyset

  BRecord  = 1ULL << 37,

  BSPArr    = BSPArrE | BSPArrN,
  BCPArr    = BCPArrE | BCPArrN,
  BPArrE    = BSPArrE | BCPArrE,
  BPArrN    = BSPArrN | BCPArrN,
  BPArr     = BPArrE  | BPArrN,

  BSVArr    = BSVArrE | BSVArrN,
  BCVArr    = BCVArrE | BCVArrN,
  BVArrE    = BSVArrE | BCVArrE,
  BVArrN    = BSVArrN | BCVArrN,
  BVArr     = BVArrE  | BVArrN,

  BSDArr    = BSDArrE | BSDArrN,
  BCDArr    = BCDArrE | BCDArrN,
  BDArrE    = BSDArrE | BCDArrE,
  BDArrN    = BSDArrN | BCDArrN,
  BDArr     = BDArrE  | BDArrN,

  BSArrE    = BSPArrE | BSVArrE | BSDArrE,
  BCArrE    = BCPArrE | BCVArrE | BCDArrE,
  BSArrN    = BSPArrN | BSVArrN | BSDArrN,
  BCArrN    = BCPArrN | BCVArrN | BCDArrN,

  BNull     = BUninit | BInitNull,
  BBool     = BFalse | BTrue,
  BNum      = BInt | BDbl,
  BStr      = BSStr | BCStr,
  BSArr     = BSArrE | BSArrN,
  BCArr     = BCArrE | BCArrN,
  BArrE     = BSArrE | BCArrE,
  BArrN     = BSArrN | BCArrN,   // may have value / data
  BArr      = BArrE | BArrN,
  BSVec     = BSVecE | BSVecN,
  BCVec     = BCVecE | BCVecN,
  BVecE     = BSVecE | BCVecE,
  BVecN     = BSVecN | BCVecN,
  BVec      = BVecE | BVecN,
  BSDict    = BSDictE | BSDictN,
  BCDict    = BCDictE | BCDictN,
  BDictE    = BSDictE | BCDictE,
  BDictN    = BSDictN | BCDictN,
  BDict     = BDictE | BDictN,
  BSKeyset  = BSKeysetE | BSKeysetN,
  BCKeyset  = BCKeysetE | BCKeysetN,
  BKeysetE  = BSKeysetE | BCKeysetE,
  BKeysetN  = BSKeysetN | BCKeysetN,
  BKeyset   = BKeysetE | BKeysetN,

  // Nullable types.
  BOptTrue     = BInitNull | BTrue,
  BOptFalse    = BInitNull | BFalse,
  BOptBool     = BInitNull | BBool,
  BOptInt      = BInitNull | BInt,       // may have value
  BOptDbl      = BInitNull | BDbl,       // may have value
  BOptNum      = BInitNull | BNum,
  BOptSStr     = BInitNull | BSStr,      // may have value
  BOptCStr     = BInitNull | BCStr,
  BOptStr      = BInitNull | BStr,
  BOptSArrE    = BInitNull | BSArrE,
  BOptCArrE    = BInitNull | BCArrE,
  BOptSArrN    = BInitNull | BSArrN,     // may have value / data
  BOptCArrN    = BInitNull | BCArrN,     // may have value / data
  BOptSArr     = BInitNull | BSArr,      // may have value / data
  BOptCArr     = BInitNull | BCArr,      // may have value / data
  BOptArrE     = BInitNull | BArrE,      // may have value / data
  BOptArrN     = BInitNull | BArrN,      // may have value / data
  BOptArr      = BInitNull | BArr,       // may have value / data
  BOptObj      = BInitNull | BObj,       // may have data
  BOptRes      = BInitNull | BRes,
  BOptFunc     = BInitNull | BFunc,
  BOptCls      = BInitNull | BCls,
  BOptClsMeth  = BInitNull | BClsMeth,
  BOptSVecE    = BInitNull | BSVecE,
  BOptCVecE    = BInitNull | BCVecE,
  BOptSVecN    = BInitNull | BSVecN,
  BOptCVecN    = BInitNull | BCVecN,
  BOptSVec     = BInitNull | BSVec,
  BOptCVec     = BInitNull | BCVec,
  BOptVecE     = BInitNull | BVecE,
  BOptVecN     = BInitNull | BVecN,
  BOptVec      = BInitNull | BVec,
  BOptSDictE   = BInitNull | BSDictE,
  BOptCDictE   = BInitNull | BCDictE,
  BOptSDictN   = BInitNull | BSDictN,
  BOptCDictN   = BInitNull | BCDictN,
  BOptSDict    = BInitNull | BSDict,
  BOptCDict    = BInitNull | BCDict,
  BOptDictE    = BInitNull | BDictE,
  BOptDictN    = BInitNull | BDictN,
  BOptDict     = BInitNull | BDict,
  BOptSKeysetE = BInitNull | BSKeysetE,
  BOptCKeysetE = BInitNull | BCKeysetE,
  BOptSKeysetN = BInitNull | BSKeysetN,
  BOptCKeysetN = BInitNull | BCKeysetN,
  BOptSKeyset  = BInitNull | BSKeyset,
  BOptCKeyset  = BInitNull | BCKeyset,
  BOptKeysetE  = BInitNull | BKeysetE,
  BOptKeysetN  = BInitNull | BKeysetN,
  BOptKeyset   = BInitNull | BKeyset,
  BOptRecord   = BInitNull | BRecord,

  BOptSPArrE   = BInitNull | BSPArrE,
  BOptCPArrE   = BInitNull | BCPArrE,
  BOptSPArrN   = BInitNull | BSPArrN,
  BOptCPArrN   = BInitNull | BCPArrN,
  BOptSPArr    = BInitNull | BSPArr,
  BOptCPArr    = BInitNull | BCPArr,
  BOptPArrE    = BInitNull | BPArrE,
  BOptPArrN    = BInitNull | BPArrN,
  BOptPArr     = BInitNull | BPArr,

  BOptSVArrE   = BInitNull | BSVArrE,
  BOptCVArrE   = BInitNull | BCVArrE,
  BOptSVArrN   = BInitNull | BSVArrN,
  BOptCVArrN   = BInitNull | BCVArrN,
  BOptSVArr    = BInitNull | BSVArr,
  BOptCVArr    = BInitNull | BCVArr,
  BOptVArrE    = BInitNull | BVArrE,
  BOptVArrN    = BInitNull | BVArrN,
  BOptVArr     = BInitNull | BVArr,

  BOptSDArrE   = BInitNull | BSDArrE,
  BOptCDArrE   = BInitNull | BCDArrE,
  BOptSDArrN   = BInitNull | BSDArrN,
  BOptCDArrN   = BInitNull | BCDArrN,
  BOptSDArr    = BInitNull | BSDArr,
  BOptCDArr    = BInitNull | BCDArr,
  BOptDArrE    = BInitNull | BDArrE,
  BOptDArrN    = BInitNull | BDArrN,
  BOptDArr     = BInitNull | BDArr,

  BUncArrKey    = BInt | BSStr,
  BArrKey       = BUncArrKey | BCStr,
  BOptUncArrKey = BInitNull | BUncArrKey,
  BOptArrKey    = BInitNull | BArrKey,

  BStrLike    = BFunc | BStr | BCls,
  BUncStrLike = BFunc | BSStr | BCls,

  BOptStrLike    = BInitNull | BStrLike,
  BOptUncStrLike = BInitNull | BUncStrLike,

  BInitPrim = BInitNull | BBool | BNum | BFunc | BCls |
              (use_lowptr ? BClsMeth : 0),

  BPrim     = BInitPrim | BUninit,
  BInitUnc  = BInitPrim | BSStr | BSArr | BSVec | BSDict | BSKeyset,
  BUnc      = BInitUnc | BUninit,
  BInitCell = BInitNull | BBool | BInt | BDbl | BStr | BArr | BObj | BRes |
              BVec | BDict | BKeyset | BFunc | BCls | BClsMeth | BRecord,
  BCell     = BUninit | BInitCell,

  BTop      = static_cast<uint64_t>(-1),
};

constexpr trep operator~(trep a) {
  return static_cast<trep>(~static_cast<int64_t>(a));
}

constexpr trep operator&(trep a, trep b) {
  return static_cast<trep>(static_cast<int64_t>(a) & b);
}

constexpr trep operator|(trep a, trep b) {
  return static_cast<trep>(static_cast<int64_t>(a) | b);
}

constexpr const trep& operator&=(trep&a, trep b) {
  a = a & b;
  return a;
}

constexpr const trep& operator|=(trep&a, trep b) {
  a = a | b;
  return a;
}

// Useful constants. Don't put them in the enum itself, because they
// can't actually occur, but are convenient masks.
constexpr auto BArrLikeE = BArrE | BVecE | BDictE | BKeysetE;
constexpr auto BArrLikeN = BArrN | BVecN | BDictN | BKeysetN;
constexpr auto BArrLike = BArrLikeE | BArrLikeN;
constexpr auto BSArrLike = BSArr | BSVec | BSDict | BSKeyset;

#define DATATAGS                                                \
  DT(Str, SString, sval)                                        \
  DT(Int, int64_t, ival)                                        \
  DT(Dbl, double, dval)                                         \
  DT(ArrLikeVal, SArray, aval)                                  \
  DT(Obj, DObj, dobj)                                           \
  DT(Cls, DCls, dcls)                                           \
  DT(ArrLikePacked, copy_ptr<DArrLikePacked>, packed)           \
  DT(ArrLikePackedN, copy_ptr<DArrLikePackedN>, packedn)        \
  DT(ArrLikeMap, copy_ptr<DArrLikeMap>, map)                    \
  DT(ArrLikeMapN, copy_ptr<DArrLikeMapN>, mapn)

// Tag for what kind of specialized data a Type object has.
enum class DataTag : uint8_t {
  None,
#define DT(name,...) name,
  DATATAGS
#undef DT
};

//////////////////////////////////////////////////////////////////////

/*
 * Information about a class type.  The class is either exact or a
 * subtype of the supplied class.
 */
struct DCls {
  enum Tag : uint16_t { Exact, Sub };

  DCls(Tag type, res::Class cls)
    : type(type)
    , cls(cls)
  {}

  Tag type;
  bool isCtx = false;
  res::Class cls;
};

/*
 * Information about a specific object type.  The class is either
 * exact or a subtype of the supplied class.
 *
 * If the class is WaitHandle, we can also carry a type that joining
 * the wait handle will produce.
 */
struct DObj {
  enum Tag : uint16_t { Exact, Sub };

  DObj(Tag type, res::Class cls)
    : type(type)
    , cls(cls)
  {}

  Tag type;
  bool isCtx = false;
  res::Class cls;
  copy_ptr<Type> whType;
};

struct DArrLikePacked;
struct DArrLikePackedN;
struct DArrLikeMap;
struct DArrLikeMapN;
using MapElems = ArrayLikeMap<Cell>;
struct ArrKey;
struct IterTypes;

/*
 * A provenance tag as tracked on a DArrLike{Packed,Map}. (and, at runtime, on
 * dicts and vecs.) The provenance tag on an array contains a file and line
 * nubmer where that array is 'from' (ideally, where the array was
 * allocated--for static arrays the srcloc where the array is first referenced)
 *
 * This is tracked here in hhbbc both because we manipulate and create new
 * static arrays.
 *
 * If the runtime option EvalArrayProvenance is not set, all ProvTags should be
 * equal to the top of the lattice (folly::none)
 *
 * The absence of a value here (folly::none) means the array type could have a
 * provenance tag from anywhere, or no tag at all. (i.e. its provenance is
 * unknown completely).
 *
 * This information forms a sublattice like:
 *
 *        top (folly::none)
 *    ____/|\___________
 *   /     |            \
 *  t_1   t_2     ...   t_n (specific arrprov::Tag's)
 *   \____ | ___________/
 *        \|/
 *       bottom (unrepresentable)
 *
 * If we would produce a 'bottom' provenance tag, (i.e. in intersectProvTag)
 * we widen the result to 'top'
 */
using ProvTag  = folly::Optional<arrprov::Tag>;

enum class Emptiness {
  Empty,
  NonEmpty,
  Maybe
};

enum class ThrowMode {
  None,
  MaybeMissingElement,
  MaybeBadKey,
  MissingElement,
  BadOperation,
};

//////////////////////////////////////////////////////////////////////

struct Type {
  Type() : m_bits(BTop) {
    assert(checkInvariants());
  }
  explicit Type(trep t) : m_bits(t) {
    assert(checkInvariants());
  }

  Type(const Type&) noexcept;
  Type(Type&&) noexcept;
  Type& operator=(const Type&) noexcept;
  Type& operator=(Type&&) noexcept;
  ~Type() noexcept;

  /*
   * Exact equality or inequality of types, and hashing.
   */
  bool operator==(const Type& o) const;
  bool operator!=(const Type& o) const { return !(*this == o); }
  size_t hash() const;

  const Type& operator |= (const Type& other);
  const Type& operator |= (Type&& other);
  const Type& operator &= (const Type& other);
  const Type& operator &= (Type&& other);

  /*
   * Returns true if this type is equivalently refined, more refined or strictly
   * more refined than `o`.  This is similar to the `==` and subtype operations
   * defined below, except they take into account if a type is tagged as a
   * context.
   */
  bool equivalentlyRefined(const Type& o) const;
  bool moreRefined(const Type& o) const;
  bool strictlyMoreRefined(const Type& o) const;

  /*
   * Returns true if this type is definitely going to be a subtype or a strict
   * subtype of `o' at runtime.  If this function returns false, this may
   * still be a subtype of `o' at runtime, it just may not be known.
   */
  bool subtypeOf(const Type& o) const;
  bool strictSubtypeOf(const Type& o) const;

  /*
   * Similar, but only check the trep (same as subtypeOf(Type{bits}),
   * but cheaper).
   */
  bool subtypeOf(trep bits) const { return (m_bits & bits) == m_bits; }
  bool subtypeOrNull(trep bits) const { return subtypeOf(bits | BNull); }

  /*
   * Subtype of any of the list of types.
   */
  template<class... Types>
  bool subtypeOfAny(const Type& t, Types... ts) const {
    return subtypeOf(t) || subtypeOfAny(ts...);
  }
  bool subtypeOfAny() const { return false; }

  template<bool contextSensitive>
  bool equivImpl(const Type& o) const;
  template<bool contextSensitive>
  bool subtypeOfImpl(const Type& o) const;

  /*
   * Returns whether there are any values of this type that are also
   * values of the type `o'.
   * When this function returns false, it is known that this type
   * must not be in any subtype relationship with the argument Type 'o'.
   * When true is returned the two types may still be unrelated but it is
   * not possible to tell.
   * Essentially this function can conservatively return true but must be
   * precise when returning false.
   */
  bool couldBe(const Type& o) const;
  bool couldBe(trep bits) const { return m_bits & bits; }

  /*
   * Could-be any of the list of types.
   */
  template<class... Types>
  bool couldBeAny(const Type& t, Types... ts) const {
    return couldBe(t) || couldBeAny(ts...);
  }
  bool couldBeAny() const { return false; }

  struct ArrayCat {
    enum { None, Empty, Packed, Struct, Mixed } cat;
    bool hasValue;
  };

private:
  friend folly::Optional<int64_t> arr_size(const Type& t);
  friend ArrayCat categorize_array(const Type& t);
  friend CompactVector<LSString> get_string_keys(const Type& t);
  friend Type wait_handle(const Index&, Type);
  friend bool is_specialized_wait_handle(const Type&);
  friend bool is_specialized_array_like(const Type& t);
  friend bool is_specialized_obj(const Type&);
  friend bool is_specialized_cls(const Type&);
  friend bool is_specialized_string(const Type&);
  friend Type wait_handle_inner(const Type&);
  friend Type sval(SString);
  friend Type sval_nonstatic(SString);
  friend Type ival(int64_t);
  friend Type dval(double);
  friend Type aval(SArray);
  friend Type subObj(res::Class);
  friend Type objExact(res::Class);
  friend Type subCls(res::Class);
  friend Type clsExact(res::Class);
  friend Type rname(SString);
  friend Type packed_impl(trep, std::vector<Type>, ProvTag);
  friend Type packedn_impl(trep, Type);
  friend Type map_impl(trep, MapElems, ProvTag);
  friend Type mapn_impl(trep bits, Type k, Type v, ProvTag);
  friend Type mapn_impl_from_map(trep bits, Type k, Type v, ProvTag);
  friend DObj dobj_of(const Type&);
  friend DCls dcls_of(Type);
  friend SString sval_of(const Type&);
  friend Type union_of(Type, Type);
  friend Type intersection_of(Type, Type);
  friend void widen_type_impl(Type&, uint32_t);
  friend Type widen_type(Type);
  friend Type widening_union(const Type&, const Type&);
  friend Type promote_emptyish(Type, Type);
  friend Emptiness emptiness(const Type&);
  friend Type opt(Type);
  friend Type unopt(Type);
  friend Type unnullish(Type);
  friend bool is_opt(const Type&);
  friend bool is_nullish(const Type&);
  friend Type project_data(Type t, trep bits);
  template<typename R, bool>
  friend R tvImpl(const Type&);
  friend Type scalarize(Type t);
  friend folly::Optional<size_t> array_size(const Type& t);
  friend folly::Optional<std::pair<Type,Type>>
  array_get_by_index(const Type& t, ssize_t index);

  friend Type return_with_context(Type, Type);
  friend Type setctx(Type, bool);
  friend Type unctx(Type);
  friend std::string show(const Type&);
  friend ArrKey disect_array_key(const Type&);
  friend std::pair<Type,bool> arr_val_elem(const Type& aval, const ArrKey& key);
  friend std::pair<Type,bool> arr_map_elem(const Type& map, const ArrKey& key);
  friend std::pair<Type,bool> arr_packed_elem(const Type& pack,
                                              const ArrKey& key);
  friend std::pair<Type,bool> arr_packedn_elem(const Type& pack,
                                               const ArrKey& key);
  friend std::pair<Type,ThrowMode> array_like_elem(const Type& arr,
                                                   const ArrKey& key,
                                                   const Type& defaultTy);
  friend std::pair<Type,ThrowMode> array_like_set(Type arr,
                                                  const ArrKey& key,
                                                  const Type& val,
                                                  ProvTag src);
  friend std::pair<Type,Type> array_like_newelem(Type arr, const Type& val,
                                                 ProvTag src);
  friend bool arr_map_set(Type& map, const ArrKey& key,
                          const Type& val, ProvTag src);
  friend bool arr_packed_set(Type& pack, const ArrKey& key,
                             const Type& val,
                             ProvTag src);
  friend bool arr_packedn_set(Type& pack, const ArrKey& key,
                              const Type& val, bool maybeEmpty);
  friend bool arr_mapn_set(Type& map, const ArrKey& key, const Type& val);
  friend Type arr_map_newelem(Type& map, const Type& val, ProvTag src);
  friend IterTypes iter_types(const Type&);
  friend RepoAuthType make_repo_type_arr(ArrayTypeTable::Builder&,
    const Type&);

  friend struct ArrKey disect_vec_key(const Type&);
  friend struct ArrKey disect_strict_key(const Type&);

  friend Type spec_array_like_union(Type&, Type&, trep, trep);
  friend Type vec_val(SArray);
  friend Type vec_empty(ProvTag);
  friend Type some_vec_empty(ProvTag);
  friend Type dict_val(SArray);
  friend Type dict_empty(ProvTag);
  friend Type some_dict_empty(ProvTag);
  friend Type keyset_val(SArray);
  friend bool could_contain_objects(const Type&);
  friend bool could_copy_on_write(const Type&);
  friend Type loosen_staticness(Type);
  friend Type loosen_dvarrayness(Type);
  friend Type loosen_provenance(Type);
  friend Type loosen_values(Type);
  friend Type loosen_emptiness(Type);
  friend Type add_nonemptiness(Type);
  friend Type assert_emptiness(Type);
  friend Type assert_nonemptiness(Type);
  friend Type set_trep(Type&, trep);
  friend Type remove_uninit(Type t);
  friend Type to_cell(Type t);
  friend bool inner_types_might_raise(const Type& t1, const Type& t2);
private:
  union Data {
    Data() {}
    ~Data() {}

#define DT(tag_name,type,name) type name;
  DATATAGS
#undef DT
  };

  template<class Ret, class T, class Function>
  struct DDHelperFn;

private:
  static Type unctxHelper(Type, bool&);
  static Type unionArrLike(Type a, Type b);
  template<class Ret, class T, class Function>
  DDHelperFn<Ret,T,Function> ddbind(const Function& f, const T& t) const;
  template<class Ret, class T, class Function>
  Ret dd2nd(const Type&, DDHelperFn<Ret,T,Function>) const;
  template<class Function> typename Function::result_type
  dualDispatchDataFn(const Type&, Function) const;
  bool hasData() const;
  template<bool contextSensitive>
  bool equivData(const Type&) const;
  template<bool contextSensitive>
  bool subtypeData(const Type&) const;
  bool couldBeData(const Type&) const;
  bool checkInvariants() const;
  ProvTag getProvTag() const;

private:
  trep m_bits;
  DataTag m_dataTag = DataTag::None;
  Data m_data;
};

//////////////////////////////////////////////////////////////////////

struct ArrKey {
  folly::Optional<int64_t> i;
  folly::Optional<SString> s;
  Type type;
  bool mayThrow = false;

  folly::Optional<Cell> tv() const {
    assert(!i || !s);
    if (i) {
      return make_tv<KindOfInt64>(*i);
    }
    if (s) {
      return make_tv<KindOfPersistentString>(*s);
    }
    return folly::none;
  }
};

struct DArrLikePacked {
  explicit DArrLikePacked(std::vector<Type> elems, ProvTag tag)
    : elems(std::move(elems))
    , provenance(tag)
  {}

  std::vector<Type> elems;
  ProvTag provenance;
};

struct DArrLikePackedN {
  explicit DArrLikePackedN(Type t) : type(std::move(t)) {}
  Type type;
};

struct DArrLikeMap {
  DArrLikeMap() {}
  explicit DArrLikeMap(MapElems map, ProvTag tag)
    : map(std::move(map))
    , provenance(tag)
  {}
  MapElems map;
  ProvTag provenance;
};

struct DArrLikeMapN {
  explicit DArrLikeMapN(Type key, Type val)
    : key(std::move(key))
    , val(std::move(val))
  {}
  Type key;
  Type val;
};

//////////////////////////////////////////////////////////////////////

#define TYPES(X)                                \
X(Bottom)                                       \
X(Uninit)                                       \
X(InitNull)                                     \
X(False)                                        \
X(True)                                         \
X(Int)                                          \
X(Dbl)                                          \
X(SStr)                                         \
X(SArrE)                                        \
X(SArrN)                                        \
X(Obj)                                          \
X(Res)                                          \
X(Cls)                                          \
X(Func)                                         \
X(ClsMeth)                                      \
X(Record)                                       \
X(SVecE)                                        \
X(SVecN)                                        \
X(SDictE)                                       \
X(SDictN)                                       \
X(SKeysetE)                                     \
X(SKeysetN)                                     \
X(Null)                                         \
X(Bool)                                         \
X(Num)                                          \
X(Str)                                          \
X(SArr)                                         \
X(ArrE)                                         \
X(ArrN)                                         \
X(Arr)                                          \
X(SVec)                                         \
X(VecE)                                         \
X(VecN)                                         \
X(Vec)                                          \
X(SDict)                                        \
X(DictE)                                        \
X(DictN)                                        \
X(Dict)                                         \
X(SKeyset)                                      \
X(KeysetE)                                      \
X(KeysetN)                                      \
X(Keyset)                                       \
X(SPArrE)                                       \
X(SPArrN)                                       \
X(SPArr)                                        \
X(PArrE)                                        \
X(PArrN)                                        \
X(PArr)                                         \
X(SVArrE)                                       \
X(SVArrN)                                       \
X(SVArr)                                        \
X(VArrE)                                        \
X(VArrN)                                        \
X(VArr)                                         \
X(SDArrE)                                       \
X(SDArrN)                                       \
X(SDArr)                                        \
X(DArrE)                                        \
X(DArrN)                                        \
X(DArr)                                         \
X(UncArrKey)                                    \
X(ArrKey)                                       \
X(UncStrLike)                                 \
X(StrLike)                                    \
X(InitPrim)                                     \
X(Prim)                                         \
X(InitUnc)                                      \
X(Unc)                                          \
X(OptTrue)                                      \
X(OptFalse)                                     \
X(OptBool)                                      \
X(OptInt)                                       \
X(OptDbl)                                       \
X(OptNum)                                       \
X(OptSStr)                                      \
X(OptStr)                                       \
X(OptSArrE)                                     \
X(OptSArrN)                                     \
X(OptSArr)                                      \
X(OptArrE)                                      \
X(OptArrN)                                      \
X(OptArr)                                       \
X(OptObj)                                       \
X(OptRes)                                       \
X(OptFunc)                                      \
X(OptCls)                                       \
X(OptClsMeth)                                   \
X(OptRecord)                                    \
X(OptSVecE)                                     \
X(OptSVecN)                                     \
X(OptSVec)                                      \
X(OptVecE)                                      \
X(OptVecN)                                      \
X(OptVec)                                       \
X(OptSDictE)                                    \
X(OptSDictN)                                    \
X(OptSDict)                                     \
X(OptDictE)                                     \
X(OptDictN)                                     \
X(OptDict)                                      \
X(OptSKeysetE)                                  \
X(OptSKeysetN)                                  \
X(OptSKeyset)                                   \
X(OptKeysetE)                                   \
X(OptKeysetN)                                   \
X(OptKeyset)                                    \
X(OptSPArrE)                                    \
X(OptSPArrN)                                    \
X(OptSPArr)                                     \
X(OptPArrE)                                     \
X(OptPArrN)                                     \
X(OptPArr)                                      \
X(OptSVArrE)                                    \
X(OptSVArrN)                                    \
X(OptSVArr)                                     \
X(OptVArrE)                                     \
X(OptVArrN)                                     \
X(OptVArr)                                      \
X(OptSDArrE)                                    \
X(OptSDArrN)                                    \
X(OptSDArr)                                     \
X(OptDArrE)                                     \
X(OptDArrN)                                     \
X(OptDArr)                                      \
X(OptUncArrKey)                                 \
X(OptArrKey)                                    \
X(OptUncStrLike)                              \
X(OptStrLike)                                 \
X(InitCell)                                     \
X(Cell)                                         \
X(Top)

#define X(y) extern const Type T##y;
TYPES(X)
#undef X

// These are treps that have B* names, but which are not "predefined"
// types. They are only allowed in combination with the corresponding
// S types.
#define NON_TYPES(X)                            \
  X(CStr)                                       \
  X(CPArrE)                                     \
  X(CPArrN)                                     \
  X(CVArrE)                                     \
  X(CVArrN)                                     \
  X(CDArrE)                                     \
  X(CDArrN)                                     \
  X(CArrE)                                      \
  X(CArrN)                                      \
  X(CVecE)                                      \
  X(CVecN)                                      \
  X(CDictE)                                     \
  X(CDictN)                                     \
  X(CKeysetE)                                   \
  X(CKeysetN)                                   \
  X(CPArr)                                      \
  X(CVArr)                                      \
  X(CDArr)                                      \
  X(CArr)                                       \
  X(CVec)                                       \
  X(CDict)                                      \
  X(CKeyset)                                    \
  X(OptCStr)                                    \
  X(OptCPArrE)                                  \
  X(OptCPArrN)                                  \
  X(OptCPArr)                                   \
  X(OptCVArrE)                                  \
  X(OptCVArrN)                                  \
  X(OptCVArr)                                   \
  X(OptCDArrE)                                  \
  X(OptCDArrN)                                  \
  X(OptCDArr)                                   \
  X(OptCArrE)                                   \
  X(OptCArrN)                                   \
  X(OptCArr)                                    \
  X(OptCVecE)                                   \
  X(OptCVecN)                                   \
  X(OptCVec)                                    \
  X(OptCDictE)                                  \
  X(OptCDictN)                                  \
  X(OptCDict)                                   \
  X(OptCKeysetE)                                \
  X(OptCKeysetN)                                \
  X(OptCKeyset)

//////////////////////////////////////////////////////////////////////

/*
 * Return WaitH<T> for a type t.
 */
Type wait_handle(const Index&, Type t);

/*
 * Return T from a WaitH<T>.
 *
 * Pre: is_specialized_handle(t);
 */
Type wait_handle_inner(const Type& t);

/*
 * Create Types that represent constant values.
 */
Type sval(SString);
Type ival(int64_t);
Type dval(double);
Type aval(SArray);
Type vec_val(SArray);
Type dict_val(SArray);
Type keyset_val(SArray);
Type sval_nonstatic(SString);

/*
 * Create static empty array or string types.
 */
Type sempty();
Type aempty();
Type aempty_varray();
Type aempty_darray();
Type vec_empty(ProvTag pt = folly::none);
Type dict_empty(ProvTag pt = folly::none);
Type keyset_empty();

/*
 * Create an any-countedness empty array/vec/dict type.
 */
Type some_aempty();
Type some_aempty_darray();
Type some_vec_empty(ProvTag pt = folly::none);
Type some_dict_empty(ProvTag pt = folly::none);
Type some_keyset_empty();

/*
 * Create types for objects or classes with some known constraint on
 * which res::Class is associated with them.
 */
Type subObj(res::Class);
Type objExact(res::Class);
Type subCls(res::Class);
Type clsExact(res::Class);

/*
 * Packed array types with known size.
 *
 * Pre: !v.empty()
 */
Type arr_packed(std::vector<Type> v);
Type arr_packed_varray(std::vector<Type> v);
Type sarr_packed(std::vector<Type> v);

/*
 * Packed array types of unknown size.
 *
 * Note that these types imply the arrays are non-empty.
 */
Type arr_packedn(Type);
Type sarr_packedn(Type);

/*
 * Struct-like arrays.
 *
 * Pre: !m.empty()
 */
Type arr_map(MapElems m);
Type arr_map_darray(MapElems m);
Type sarr_map(MapElems m);

/*
 * Map-like arrays.
 */
Type arr_mapn(Type k, Type v);
Type sarr_mapn(Type k, Type v);

/*
 * vec types with known size.
 *
 * Pre: !v.empty()
 */
Type vec(std::vector<Type> v, ProvTag);
Type svec(std::vector<Type> v, ProvTag);

/*
 * Vec type of unknown size.
 */
Type vec_n(Type);
Type svec_n(Type);

/*
 * Struct-like dicts.
 *
 * Pre: !m.empty()
 */
Type dict_map(MapElems m, ProvTag);

/*
 * Dict with key/value types.
 */
Type dict_n(Type, Type, ProvTag);
Type sdict_n(Type, Type, ProvTag);

/*
 * Keyset with key (same as value) type.
 */
Type keyset_n(Type);
Type ckeyset_n(Type);

/*
 * Keyset from MapElems
 */
inline Type keyset_map(MapElems m) {
  return map_impl(BKeysetN, std::move(m), folly::none);
}

/*
 * Create the optional version of the Type t.
 *
 * Pre: there must be an optional version of the type t.
 */
Type opt(Type t);

/*
 * Return the non-optional version of the Type t.
 *
 * Pre: is_opt(t)
 */
Type unopt(Type t);

/*
 * Returns whether a given type is a subtype of one of the predefined
 * optional types.  (Note that this does not include types like
 * TInitUnc---it's only the TOpt* types.)
 */
bool is_opt(const Type& t);

/*
 * Return t with BNull removed from its trep.
 *
 * Pre: is_nullish(t)
 */
Type unnullish(Type t);

/*
 * Returns whether a given type couldBe TNull, and would still be
 * predefined if BNull was removed from its trep.
 */
bool is_nullish(const Type& t);

/*
 * Improves the type `t` given the current context.  This returns the
 * intersection of the type `t` with the `context` if the `context` is a valid
 * class or object, and `t` is tagged as being the context.  If `context` is
 * a class we will first convert it to an object.  This returns an optional type
 * if `t` was optional.
 */
Type return_with_context(Type t, Type context);

/*
 * If `to` is false.  This is an identity operation.  If `to` is true, and
 * `t` is a specialized object or class, this will return `t` tagged as a
 * context.
 */
Type setctx(Type t, bool to = true);

/*
 * This removes any context tags in the type `t`, even if nested inside other
 * types.
 */
Type unctx(Type t);

/*
 * Discards any data associated with `t` that isn't valid for the given trep
 *
 * At the moment this will do nothing beyond removing empty ArrLikeDatas from
 * types that used to only have ArrE bits set but now have a ArrN bit set
 */
Type project_data(Type t, trep bits);

/*
 * Refinedness equivalence checks.
 */
bool equivalently_refined(const Type&, const Type&);

template<
  typename Iterable,
  typename = std::enable_if<
    std::is_same<typename Iterable::value_type, Type>::value
  >
>
bool equivalently_refined(const Iterable& a, const Iterable& b) {
  if (a.size() != b.size()) return false;
  for (auto ita = a.begin(), itb = b.begin(); ita != a.end(); ++ita, ++itb) {
    if (!equivalently_refined(*ita, *itb)) return false;
  }
  return true;
}

/*
 * Returns true if type 't' represents a "specialized" object, that is an
 * object of a known class, or an optional object of a known class.
 */
bool is_specialized_obj(const Type&);

/*
 * Returns true if type 't' represents a "specialized" class---i.e. a class
 * with a DCls structure.
 */
bool is_specialized_cls(const Type&);

/*
 * Returns whether `t' is a WaitH<T> or ?WaitH<T> for some T.
 *
 * Note that this function returns false for Obj<=WaitHandle with no
 * tracked inner type.
 */
bool is_specialized_wait_handle(const Type& t);

/*
 * Returns whether `t' is a one of the array like types, or
 * an optional version of one of those types.  That is, with
 * either a constant value or some (maybe partially) known shape.
 */
bool is_specialized_array(const Type& t);
bool is_specialized_vec(const Type& t);
bool is_specialized_dict(const Type& t);
bool is_specialized_keyset(const Type& t);

/*
 * Returns the best known instantiation of a class type.  Or returns the
 * provided object.
 *
 * Pre: t.subypeOfAny(TObj, TCls)
 */
Type toobj(const Type& t);

/*
 * Returns the best known TCls subtype for an object type.  Otherwise return
 * the passed in type.
 */
Type objcls(const Type& t);

/*
 * If the type t has a known constant value, return it as a Cell.
 * Otherwise return folly::none.
 *
 * The returned Cell can only contain non-reference-counted types.
 */
folly::Optional<Cell> tv(const Type& t);

/*
 * If the type t has a known constant value, return it as a Cell.
 * Otherwise return folly::none.
 *
 * The returned Cell may contain reference-counted types.
 *
 * You are responsible for any required ref-counting.
 */
folly::Optional<Cell> tvNonStatic(const Type& t);

/*
 * If the type t has a known constant value, return true.
 * Otherwise return false.
 */
bool is_scalar(const Type& t);

/*
 * Return the canonical scalar type for t - equivalent to
 * from_cell(*tv(t)).
 *
 * This can be used to ensure that the arguments in a CallContext are
 * canonicalized, so that immaterial changes to them (eg TArrN ->
 * TSArrN or DArrLikeMap -> DArrLikeVal) don't affect which entry gets
 * looked up.
 *
 * pre: is_scalar(t).
 */
Type scalarize(Type t);

/*
 * If t represents an array, and we know its size, return it.
 */
folly::Optional<size_t> array_size(const Type& t);

/*
 * If t represents an array, and we know the index'th element (by
 * iteration order), return the key/value pair.
 *
 * Negative values of index work backwards from the last element.
 */
folly::Optional<std::pair<Type,Type>>
array_get_by_index(const Type& t, ssize_t index);

/*
 * Get the type in our typesystem that corresponds to an hhbc
 * IsTypeOp.
 *
 * Pre: op != IsTypeOp::Scalar
 */
Type type_of_istype(IsTypeOp op);

/*
 * Get the hhbc IsTypeOp that corresponds to the type in our typesystem.
 * Returns folly::none if no matching IsTypeOp is found.
 */
folly::Optional<IsTypeOp> type_to_istypeop(const Type& t);

/*
 * Get the type in our typesystem that corresponds to type given by the
 * potentially unresolved type structure.
 * Returns folly::none if the type structure is unresolved or
 * no matching Type is found.
 *
 */
folly::Optional<Type> type_of_type_structure(SArray ts);

/*
 * Return the DObj structure for a strict subtype of TObj or TOptObj.
 *
 * Pre: is_specialized_obj(t)
 */
DObj dobj_of(const Type& t);

/*
 * Return the DCls structure for a strict subtype of TCls.
 *
 * Pre: is_specialized_cls(t)
 */
DCls dcls_of(Type t);

/*
 * Return the SString for a strict subtype of TStr.
 *
 * Pre: is_specialized_string(t)
 */
SString sval_of(const Type& t);

/*
 * Create a Type from a Cell.
 *
 * Pre: the cell must contain a non-reference-counted type.
 * Post: returned type is a subtype of TUnc
 */
Type from_cell(Cell tv);

/*
 * Create a Type from a DataType. KindOfString and KindOfPersistentString
 * are both treated as TStr.
 *
 * Pre: dt is one of the DataTypes that actually represent php values
 * (or KindOfUninit).
 */
Type from_DataType(DataType dt);

/*
 * Create a Type from a builtin type specification string.
 *
 * This is used for HNI class properties.  We assume that these are
 * accurate.  `s' may be nullptr.
 */
Type from_hni_constraint(SString s);

/*
 * Make a type that represents values from the intersection of the
 * supplied types.
 */
Type intersection_of(Type a, Type b);

/*
 * Make a type that represents values from either of the supplied
 * types.
 *
 * Importantly, note that there are infinitely long chains of array
 * types that continue to become less specialized, so chains of
 * union_of operations are not guaranteed to reach a stable point in
 * finite steps.
 */
Type union_of(Type a, Type b);

/*
 * Widening union.
 *
 * This operation returns a type T, such that a is a subtype of T, b
 * is a subtype of T, and union_of(a, b) is a subtype of T.  The
 * widening union also has the property that every possible chain of
 * successive applications of the function eventually reaches a stable
 * point.
 *
 * This is currently implemented by unioning the types, then applying
 * widen_type() to the result.
 *
 * For portions of our analysis that rely on growing types reaching
 * stable points for termination, this function must occasionally be
 * used instead of union_of to guarantee termination.  See details in
 * analyze.cpp.
 */
Type widening_union(const Type& a, const Type& b);

/*
 * Widen a type to one which has a finite chain under the union operator. This
 * generally involves restricting the type's nesting depth to a fixed limit and
 * preventing a specialized array type from growing larger unbounded.
 */
Type widen_type(Type t);

/*
 * A sort of union operation that also attempts to remove "emptyish" types from
 * union_of(a, b).  This is useful for promoting emptyish types (sempty(),
 * false, and null) to stdClass or to arrays, in member instructions.
 *
 * This function currently doesn't give specific guarantees about exactly when
 * the emptyish types will not be part of the return type (informally it only
 * happens in the "easy" cases right now), so you should not use it in
 * situations where union_of(a, b) would not also be correct.
 */
Type promote_emptyish(Type a, Type b);


/*
 * Returns what we know about the emptiness of the type.
 */
Emptiness emptiness(const Type&);

/*
 * Returns whether a Type could hold an object that has a custom
 * boolean conversion function.
 */
bool could_have_magic_bool_conversion(const Type&);

/*
 * Returns the smallest type that `a' is a subtype of, from the
 * following set: TInitCell, TUninit.
 *
 * Pre: `a' is a subtype of TCell.
 */
Type stack_flav(Type a);

/*
 * Discard any countedness information about the type. Force any type
 * (recursively) which contains only static or counted variants to contain
 * both. Doesn't change the type otherwise.
 */
Type loosen_staticness(Type);

/*
 * Discard any specific knowledge about whether the type is a d/varray. Force
 * any type which might contain any sub-types of PArr, VArr, or DArr to contain
 * Arr, while keeping the same staticness and emptiness information.
 */
Type loosen_dvarrayness(Type);

/*
 * Discard any specific provenance tag on this type and any sub-arrays
 */
Type loosen_provenance(Type);

/*
 * Force any type which might contain any sub-types of Arr, Vec, Dict, and
 * Keyset to contain Arr, Vec, Dict, and Keyset. This is needed for some
 * operations whose effects on arrays cannot be predicted. Doesn't change the
 * type otherwise.
 */
Type loosen_arrays(Type);

/*
 * Drop any data from the type (except for object class information) and force
 * TTrue or TFalse to TBool. Doesn't change the type otherwise.
 */
Type loosen_values(Type t);

/*
 * Discard any emptiness information about the type. Force any type which
 * contains only empty or non-empty variants to contain both. Doesn't change the
 * type otherwise.
 */
Type loosen_emptiness(Type t);

/*
 * Loosens staticness, emptiness, and values from the type. This forces a type
 * to its most basic form (except for object class information).
 */
Type loosen_all(Type t);

/*
 * If t contains TUninit, returns the best type we can that contains
 * at least everything t contains, but doesn't contain TUninit.  Note
 * that this function will return TBottom for TUninit.
 */
Type remove_uninit(Type t);

/*
 * If t is not a TCell, returns TInitCell. Otherwise, if t contains
 * TUninit, return union_of(remove_uninit(t), TInitCell).
 */
Type to_cell(Type t);

/*
 * Add non-empty variants of the type to the type if not already
 * present. Doesn't change the type otherwise.
 */
Type add_nonemptiness(Type t);

/*
 * Produced the most refined type possible, given that
 * t passed/failed an emptiness check.
 */
Type assert_emptiness(Type);
Type assert_nonemptiness(Type);

/*
 * (array|vec|dict|keyset)_elem
 *
 * Returns the best known type of an array inner element given a type
 * for the key.  The returned type is always a subtype of TInitCell.
 *
 * The returned type will be TBottom if the operation will always throw.
 * ThrowMode indicates what kind of failures may occur.
 *
 * Pre: first arg is a subtype of TArr, TVec, TDict, TKeyset respectively.
 */
std::pair<Type,ThrowMode> array_elem(const Type& arr, const Type& key,
                                     const Type& defaultTy = TInitNull);
std::pair<Type, ThrowMode> vec_elem(const Type& vec, const Type& key,
                                    const Type& defaultTy = TBottom);
std::pair<Type, ThrowMode> dict_elem(const Type& dict, const Type& key,
                                     const Type& defaultTy = TBottom);
std::pair<Type, ThrowMode> keyset_elem(const Type& keyset, const Type& key,
                                       const Type& defaultTy = TBottom);

/*
 * (array|vec|dict|keyset)_set
 *
 * Perform an array-like set on types.  Returns a type that represents the
 * effects of arr[key] = val.
 *
 * The returned type will be TBottom if the operation will always throw.
 * ThrowMode indicates what kind of failures may occur.
 *
 * Pre: first arg is a subtype of TArr, TVec, TDict, TKeyset respectively.
 */
std::pair<Type, ThrowMode> array_set(Type arr, const Type& key,
                                     const Type& val, ProvTag src);
std::pair<Type, ThrowMode> vec_set(Type vec, const Type& key, const Type& val,
                                   ProvTag src);
std::pair<Type, ThrowMode> dict_set(Type dict, const Type& key,
                                    const Type& val, ProvTag src);
std::pair<Type, ThrowMode> keyset_set(Type keyset, const Type& key,
                                      const Type& val);

/*
 * (array|vec|dict|keyset)_newelem
 *
 * Perform a newelem operation on an array-like type.  Returns an
 * array that contains a new pushed-back element with the supplied
 * value, in the sense of arr[] = val, and the best known type of the
 * key that was added.
 *
 * Pre: first arg is a subtype of TArr, TVec, TDict, TKeyset respectively.
 */
std::pair<Type,Type> array_newelem(Type arr, const Type& val, ProvTag src);
std::pair<Type,Type> vec_newelem(Type vec, const Type& val, ProvTag src);
std::pair<Type,Type> dict_newelem(Type dict, const Type& val, ProvTag src);
std::pair<Type,Type> keyset_newelem(Type keyset, const Type& val);

/*
 * Return the best known information for iteration of the supplied type. This is
 * only intended for non-mutable iteration, so the returned types are at worst
 * InitCell.
 */
struct IterTypes {
  Type key;
  Type value;
  // The number of elements we're iterating over:
  enum struct Count {
    Empty,     // No elements
    Single,    // Exactly one element
    ZeroOrOne, // Less than 2 elements
    NonEmpty,  // Unknown upper bound, but non-empty
    Any        // Nothing known
  };
  Count count;
  // Can a IterInit[K] op throw on this iterator?
  bool mayThrowOnInit;
  // Can a IterNext[K] op throw on this iterator? Can only happen for object
  // types.
  bool mayThrowOnNext;
};
IterTypes iter_types(const Type&);

/*
 * Create a RepoAuthType for a Type.
 *
 * RepoAuthTypes may contain things like RepoAuthType::Array*'s or
 * SStrings for class names.  The emit code needs to handle making
 * sure these things are merged into the appropriate unit or repo.
 *
 * Pre: !t.couldBe(BCls)
 *      !t.subtypeOf(BBottom)
 */
RepoAuthType make_repo_type(ArrayTypeTable::Builder&, const Type& t);

/*
 * Returns true iff an IsType testing for testTy/testOp on valTy might raise.
 */
bool is_type_might_raise(const Type& testTy, const Type& valTy);
bool is_type_might_raise(IsTypeOp testOp, const Type& valTy);

/*
 * Returns true iff a compare of two types might raise a HAC notice
 */
bool compare_might_raise(const Type& t1, const Type& t2);

/*
 * Given a type, adjust the type for the given type-constraint. If there's no
 * type-constraint, or if property type-hints aren't being enforced, then return
 * the type as is. This might return TBottom if the type is not compatible with
 * the type-hint.
 */
Type adjust_type_for_prop(const Index& index,
                          const php::Class& propCls,
                          const TypeConstraint* tc,
                          const Type& ty);

//////////////////////////////////////////////////////////////////////

}}

#endif