allow undefined data-* and aria-* XHP attributes with ->:

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

/*
   +----------------------------------------------------------------------+
   | HipHop for PHP                                                       |
   +----------------------------------------------------------------------+
   | Copyright (c) 2010-2014 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.               |
   +----------------------------------------------------------------------+
*/
#include "hphp/hhbbc/type-system.h"

#include <type_traits>
#include <cmath>
#include <algorithm>
#include <iterator>

#include <folly/Optional.h>
#include <folly/Traits.h>
#include <folly/Hash.h>

#include "hphp/runtime/base/repo-auth-type.h"
#include "hphp/runtime/base/repo-auth-type-array.h"
#include "hphp/runtime/base/array-iterator.h"
#include "hphp/hhbbc/index.h"

namespace HPHP { namespace HHBBC {

TRACE_SET_MOD(hhbbc);

namespace {

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

const StaticString s_WaitHandle("HH\\WaitHandle");
const StaticString s_empty("");

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

// Legal to call with !isPredefined(bits)
bool mayHaveData(trep bits) {
  switch (bits) {
  case BSStr:    case BObj:    case BInt:    case BDbl:
  case BOptSStr: case BOptObj: case BOptInt: case BOptDbl:
  case BCls:
  case BArr:     case BSArr:     case BCArr:
  case BArrN:    case BSArrN:    case BCArrN:
  case BOptArr:  case BOptSArr:  case BOptCArr:
  case BOptArrN: case BOptSArrN: case BOptCArrN:
  case BRef:
    return true;

  case BBottom:
  case BUninit:
  case BInitNull:
  case BFalse:
  case BTrue:
  case BCStr:
  case BSArrE:
  case BCArrE:
  case BRes:
  case BNull:
  case BNum:
  case BBool:
  case BStr:
  case BArrE:
  case BInitPrim:
  case BPrim:
  case BInitUnc:
  case BUnc:
  case BOptTrue:
  case BOptFalse:
  case BOptBool:
  case BOptNum:
  case BOptCStr:
  case BOptStr:
  case BOptSArrE:
  case BOptCArrE:
  case BOptArrE:
  case BOptRes:
  case BInitCell:
  case BCell:
  case BInitGen:
  case BGen:
  case BTop:
    break;
  }
  return false;
}

/*
 * Note: currently we're limiting all represented types to predefined
 * bit patterns (instead of arbitrary unions), so this function is
 * around for assertions.
 *
 * This may be relaxed later if we think we can get more out of it,
 * but for now the thought is that the likelihood of getting
 * significantly better types from the inference algorithm might be
 * counter-balanced by the increased chance of hard-to-track
 * type-system bugs, so at least for now (at the time of this writing,
 * before shipping hhbbc) we're ruling out a bunch of edge cases.
 *
 * Aside from types like Obj<= or things like TSStr, a lot of cases
 * with arbitrary-unions may not lead to better code at JIT time
 * (unless the inference turns them back into a predefined type),
 * since we'll have to guard anyway to see which one it was.  We'll
 * try it later.
 */
bool isPredefined(trep bits) {
  switch (bits) {
  case BBottom:
  case BUninit:
  case BInitNull:
  case BFalse:
  case BTrue:
  case BInt:
  case BDbl:
  case BSStr:
  case BCStr:
  case BSArrE:
  case BCArrE:
  case BSArrN:
  case BCArrN:
  case BObj:
  case BRes:
  case BCls:
  case BRef:
  case BNull:
  case BNum:
  case BBool:
  case BStr:
  case BSArr:
  case BCArr:
  case BArrE:
  case BArrN:
  case BArr:
  case BInitPrim:
  case BPrim:
  case BInitUnc:
  case BUnc:
  case BOptTrue:
  case BOptFalse:
  case BOptBool:
  case BOptInt:
  case BOptDbl:
  case BOptNum:
  case BOptSStr:
  case BOptCStr:
  case BOptStr:
  case BOptSArrN:
  case BOptCArrN:
  case BOptSArrE:
  case BOptCArrE:
  case BOptSArr:
  case BOptCArr:
  case BOptArrE:
  case BOptArrN:
  case BOptArr:
  case BOptObj:
  case BOptRes:
  case BInitCell:
  case BCell:
  case BInitGen:
  case BGen:
  case BTop:
    return true;
  }
  return false;
}

// Pre: isPredefined(bits)
bool canBeOptional(trep bits) {
  switch (bits) {
  case BBottom:
    return false;

  case BUninit:
  case BInitNull:
    return false;
  case BFalse:
  case BTrue:
  case BInt:
  case BDbl:
  case BSStr:
  case BCStr:
  case BSArrE:
  case BSArrN:
  case BCArrE:
  case BCArrN:
  case BObj:
  case BRes:
    return true;

  case BNull:
  case BNum:
  case BBool:
  case BStr:
  case BSArr:
  case BCArr:
  case BArrE:
  case BArrN:
  case BArr:
    return true;

  case BCls:
  case BRef:
    return false;

  case BOptTrue:
  case BOptFalse:
  case BOptBool:
  case BOptInt:
  case BOptDbl:
  case BOptNum:
  case BOptSStr:
  case BOptCStr:
  case BOptStr:
  case BOptSArrE:
  case BOptCArrE:
  case BOptSArrN:
  case BOptCArrN:
  case BOptSArr:
  case BOptCArr:
  case BOptArrN:
  case BOptArrE:
  case BOptArr:
  case BOptObj:
  case BOptRes:
    return false;

  case BInitPrim:
  case BPrim:
  case BInitUnc:
  case BUnc:
  case BInitCell:
  case BInitGen:
  case BCell:
  case BGen:
  case BTop:
    return false;
  }
  not_reached();
}

/*
 * Combine array bits.  Our type system currently avoids arbitrary unions (see
 * rationale above), so we don't have predefined types like CArr|SArrN, or
 * SArrN|CArrE.  This function checks a few cases to ensure combining array
 * type bits leaves it predefined.
 */
trep combine_arr_bits(trep a, trep b) {
  assert((a & BArr) == a || (a & BOptArr) == a);
  assert((b & BArr) == b || (b & BOptArr) == b);
  auto const combined = static_cast<trep>(a | b);
  auto const arr_part = combined & BArr;
  // 2 bit cases:
  if (arr_part == (BSArrN|BCArrE)) return static_cast<trep>(combined|BArr);
  if (arr_part == (BSArrE|BCArrN)) return static_cast<trep>(combined|BArr);
  // 3 bit cases:
  if (arr_part == (BArrN|BCArrE)) return static_cast<trep>(combined|BArr);
  if (arr_part == (BArrN|BSArrE)) return static_cast<trep>(combined|BArr);
  if (arr_part == (BArrE|BCArrN)) return static_cast<trep>(combined|BArr);
  if (arr_part == (BArrE|BSArrN)) return static_cast<trep>(combined|BArr);
  assert(isPredefined(combined));
  return combined;
}

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

/*
 * The following functions make DArr* structs out of static arrays, to
 * simplify implementing some of the type system operations on them.
 *
 * When they return folly::none it is not a conservative thing: it
 * implies the array is definitely not packed, packedN, struct-like,
 * etc (we use this to return false in couldBe).
 */

folly::Optional<DArrPacked> toDArrPacked(SArray ar) {
  assert(!ar->empty());

  std::vector<Type> elems;
  auto idx = size_t{0};
  for (ArrayIter iter(ar); iter; ++iter, ++idx) {
    auto const key = *iter.first().asTypedValue();
    if (key.m_type != KindOfInt64) return folly::none;
    if (key.m_data.num != idx)     return folly::none;
    elems.push_back(
      from_cell(*iter.secondRef().asTypedValue())
    );
  }

  return DArrPacked { std::move(elems) };
}

folly::Optional<DArrPackedN> toDArrPackedN(SArray ar) {
  assert(!ar->empty());

  auto t = TBottom;
  auto idx = size_t{0};
  for (ArrayIter iter(ar); iter; ++iter, ++idx) {
    auto const key = *iter.first().asTypedValue();
    if (key.m_type != KindOfInt64) return folly::none;
    if (key.m_data.num != idx)     return folly::none;
    t = union_of(t, from_cell(*iter.secondRef().asTypedValue()));
  }

  return DArrPackedN { std::move(t) };
}

folly::Optional<DArrStruct> toDArrStruct(SArray ar) {
  assert(!ar->empty());

  auto map = StructMap{};
  for (ArrayIter iter(ar); iter; ++iter) {
    auto const key = *iter.first().asTypedValue();
    if (!IS_STRING_TYPE(key.m_type)) return folly::none;
    map[key.m_data.pstr] = from_cell(*iter.secondRef().asTypedValue());
  }

  return DArrStruct { std::move(map) };
}

DArrMapN toDArrMapN(SArray ar) {
  assert(!ar->empty());

  auto k = TBottom;
  auto v = TBottom;
  for (ArrayIter iter(ar); iter; ++iter) {
    auto const key = *iter.first().asTypedValue();
    k = union_of(k, from_cell(key));
    v = union_of(v, from_cell(*iter.secondRef().asTypedValue()));
  }

  return DArrMapN { k, v };
}

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

bool subtypePacked(const DArrPacked& a, const DArrPacked& b) {
  auto const asz = a.elems.size();
  auto const bsz = b.elems.size();
  if (asz != bsz) return false;
  for (auto i = size_t{0}; i < asz; ++i) {
    if (!a.elems[i].subtypeOf(b.elems[i])) {
      return false;
    }
  }
  return true;
}

bool subtypeStruct(const DArrStruct& a, const DArrStruct& b) {
  if (a.map.size() != b.map.size()) return false;
  auto aIt = begin(a.map);
  auto bIt = begin(b.map);
  for (; aIt != end(a.map); ++aIt, ++bIt) {
    if (aIt->first != bIt->first) return false;
    if (!aIt->second.subtypeOf(bIt->second)) return false;
  }
  return true;
}

bool couldBePacked(const DArrPacked& a, const DArrPacked& b) {
  auto const asz = a.elems.size();
  auto const bsz = b.elems.size();
  if (asz != bsz) return false;
  for (auto i = size_t{0}; i < asz; ++i) {
    if (!a.elems[i].couldBe(b.elems[i])) {
      return false;
    }
  }
  return true;
}

bool couldBeStruct(const DArrStruct& a, const DArrStruct& b) {
  if (a.map.size() != b.map.size()) return false;
  auto aIt = begin(a.map);
  auto bIt = begin(b.map);
  for (; aIt != end(a.map); ++aIt, ++bIt) {
    if (aIt->first != bIt->first) return false;
    if (!aIt->second.couldBe(bIt->second)) return false;
  }
  return true;
}

Type struct_values(const DArrStruct& a) {
  auto ret = TBottom;
  for (auto& kv : a.map) ret = union_of(ret, kv.second);
  return ret;
}

Type packed_values(const DArrPacked& a) {
  auto ret = TBottom;
  for (auto& e : a.elems) ret = union_of(ret, e);
  return ret;
}

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

/*
 * Helper for dealing with disjointDataFn's---most of them are commutative.
 * This shuffles values to the right in a canonical order to need less
 * overloads.
 */
template<class InnerFn>
struct Commute : InnerFn {
  using result_type = typename InnerFn::result_type;

  using InnerFn::operator();

  template<class B>
  result_type operator()(SArray a, const B& b) const {
    return InnerFn::operator()(b, a);
  }

  template<class B>
  result_type operator()(const DArrStruct& a, const B& b) const {
    return InnerFn::operator()(b, a);
  }

  template<class B>
  result_type operator()(const DArrPackedN& a, const B& b) const {
    return InnerFn::operator()(b, a);
  }

  template<class B>
  result_type operator()(const DArrMapN& a, const B& b) const {
    return InnerFn::operator()(b, a);
  }
};

struct DisjointEqImpl {
  using result_type = bool;

  bool operator()() const { return false; }

  bool operator()(const DArrPacked& a, SArray b) const {
    if (a.elems.size() != b->size()) return false;
    auto const p = toDArrPacked(b);
    return p && a.elems == p->elems;
  }

  bool operator()(const DArrStruct& a, SArray b) const {
    if (a.map.size() != b->size()) return false;
    auto const p = toDArrStruct(b);
    return p && a.map == p->map;
  }

  bool operator()(const DArrPackedN& a, SArray b) const {
    return false;
  }
  bool operator()(const DArrMapN& a, SArray b) const {
    return false;
  }
  bool operator()(const DArrPacked& a, const DArrPackedN& b) const {
    return false;
  }
  bool operator()(const DArrPacked& a, const DArrStruct& b) const {
    return false;
  }
  bool operator()(const DArrPacked&, const DArrMapN&) const {
    return false;
  }
  bool operator()(const DArrPackedN& a, const DArrStruct& b) const {
    return false;
  }
  bool operator()(const DArrPackedN&, const DArrMapN&) const {
    return false;
  }
  bool operator()(const DArrStruct&, const DArrMapN&) const {
    return false;
  }
};

struct DisjointCouldBeImpl {
  using result_type = bool;

  bool operator()() const { return false; }

  bool operator()(const DArrPacked& a, SArray b) const {
    if (a.elems.size() != b->size()) return false;
    auto const p = toDArrPacked(b);
    return p && couldBePacked(a, *p);
  }

  bool operator()(const DArrStruct& a, SArray b) const {
    if (a.map.size() != b->size()) return false;
    auto const p = toDArrStruct(b);
    return p && couldBeStruct(a, *p);
  }

  bool operator()(const DArrPackedN& a, SArray b) const {
    auto const p = toDArrPackedN(b);
    return p && a.type.couldBe(p->type);
  }

  bool operator()(const DArrMapN& a, SArray b) const {
    auto const p = toDArrMapN(b);
    return p.key.couldBe(a.key) && p.val.couldBe(a.val);
  }

  bool operator()(const DArrPacked& a, const DArrPackedN& b) const {
    for (auto& t : a.elems) {
      if (!t.couldBe(b.type)) return false;
    }
    return true;
  }

  bool operator()(const DArrPackedN& a, const DArrMapN& b) const {
    return TInt.couldBe(b.key) && a.type.couldBe(b.val);
  }

  bool operator()(const DArrStruct& a, const DArrMapN& b) const {
    if (!TSStr.couldBe(b.key)) return false;
    for (auto& kv : a.map) {
      if (!kv.second.couldBe(b.val)) return false;
    }
    return true;
  }

  bool operator()(const DArrPacked&, const DArrStruct&) const {
    return false;
  }
  bool operator()(const DArrPacked&, const DArrMapN&) const {
    return false;
  }
  bool operator()(const DArrPackedN&, const DArrStruct&) const {
    return false;
  }
};

// The countedness or possible-emptiness of the arrays is handled
// outside of this function, so it's ok to just return TArr from all
// of these here.

struct ArrUnionImpl {
  using result_type = Type;

  Type operator()() const { not_reached(); }

  Type operator()(const DArrPacked& a, const DArrPacked& b) const {
    if (a.elems.size() != b.elems.size()) {
      return arr_packedn(union_of(packed_values(a), packed_values(b)));
    }
    auto ret = a.elems;
    for (auto i = size_t{0}; i < a.elems.size(); ++i) {
      ret[i] = union_of(ret[i], b.elems[i]);
    }
    return arr_packed(std::move(ret));
  }

  Type operator()(const DArrPacked& a, const DArrPackedN& b) const {
    return arr_packedn(union_of(packed_values(a), b.type));
  }

  Type operator()(const DArrStruct& a, const DArrStruct& b) const {
    auto to_map = [&] {
      auto all = union_of(struct_values(a), struct_values(b));
      return arr_mapn(TSStr, std::move(all));
    };

    /*
     * With the current meaning of structs, if the keys are different, we can't
     * do anything better than going to a map type.  The reason for this is
     * that our struct types currently are implying the presence of all the
     * keys in the struct (it might be worth adding some more types for struct
     * subtyping to handle this better.)
     */
    if (a.map.size() != b.map.size()) return to_map();

    auto retStruct = StructMap{};
    auto aIt = begin(a.map);
    auto bIt = begin(b.map);
    for (; aIt != end(a.map); ++aIt, ++bIt) {
      if (aIt->first != bIt->first) return to_map();
      retStruct[aIt->first] = union_of(aIt->second, bIt->second);
    }
    return arr_struct(std::move(retStruct));
  }

  Type operator()(SArray a, SArray b) const {
    assert(a != b); // Should've been handled earlier in union_of.
    {
      auto const p1 = toDArrPacked(a);
      auto const p2 = toDArrPacked(b);
      if (p1 && p2) {
        return (*this)(*p1, *p2);
      }
      if (p1) {
        if (auto const p2n = toDArrPackedN(b)) {
          return (*this)(*p1, *p2n);
        }
      }
      if (p2) {
        if (auto const p1n = toDArrPackedN(a)) {
          return (*this)(*p2, *p1n);
        }
      }
    }
    {
      auto const s1 = toDArrStruct(a);
      auto const s2 = toDArrStruct(b);
      if (s1 && s2) return (*this)(*s1, *s2);
    }
    return (*this)(toDArrMapN(a), b);
  }

  Type operator()(const DArrPacked& a, SArray b) const {
    auto p = toDArrPacked(b);
    if (!p) return TArr;
    return (*this)(a, *p);
  }

  Type operator()(const DArrPackedN& a, SArray b) const {
    auto const p = toDArrPackedN(b);
    if (!p) return TArr;
    return arr_packedn(union_of(a.type, p->type));
  }

  Type operator()(const DArrStruct& a, SArray b) const {
    auto const p = toDArrStruct(b);
    if (!p) return TArr;
    return (*this)(a, *p);
  }

  Type operator()(const DArrMapN& a, SArray b) const {
    auto const p = toDArrMapN(b);
    return arr_mapn(union_of(a.key, p.key), union_of(a.val, p.val));
  }

  Type operator()(const DArrPacked& a, const DArrStruct& b) const {
    return arr_mapn(union_of(TInt, TSStr),
                    union_of(packed_values(a), struct_values(b)));
  }

  Type operator()(const DArrPacked& a, const DArrMapN& b) const {
    return arr_mapn(union_of(b.key, TInt),
                    union_of(packed_values(a), b.val));
  }

  Type operator()(const DArrPackedN& a, const DArrStruct& b) const {
    return arr_mapn(union_of(TInt, TSStr),
                    union_of(a.type, struct_values(b)));
  }

  Type operator()(const DArrPackedN& a, const DArrMapN& b) const {
    return arr_mapn(union_of(TInt, b.key),
                    union_of(a.type, b.val));
  }

  Type operator()(const DArrStruct& a, const DArrMapN& b) const {
    return arr_mapn(union_of(TSStr, b.key),
                    union_of(struct_values(a), b.val));
  }
};

/*
 * Subtype is not a commutative relation, so this is the only
 * disjointDataFn helper that doesn't use Commute<>.
 */
struct DisjointSubtype {
  using result_type = bool;

  bool operator()() const { return false; }

  bool operator()(const DArrStruct& a, SArray b) const {
    if (a.map.size() != b->size()) return false;
    auto const p = toDArrStruct(b);
    return p && subtypeStruct(a, *p);
  }

  bool operator()(SArray a, const DArrStruct& b) const {
    if (a->size() != b.map.size()) return false;
    auto const p = toDArrStruct(a);
    return p && subtypeStruct(*p, b);
  }

  bool operator()(SArray a, const DArrPacked& b) const {
    if (a->size() != b.elems.size()) return false;
    auto const p = toDArrPacked(a);
    return p && subtypePacked(*p, b);
  }

  bool operator()(const DArrPacked& a, SArray b) const {
    if (a.elems.size() != b->size()) return false;
    auto const p = toDArrPacked(b);
    return p && subtypePacked(a, *p);
  }

  bool operator()(const DArrPackedN& a, const DArrMapN& b) const {
    return TInt.subtypeOf(b.key) && a.type.subtypeOf(b.val);
  }

  bool operator()(const DArrPacked& a, const DArrMapN& b) const {
    if (!TInt.subtypeOf(b.key)) return false;
    for (auto& v : a.elems) {
      if (!v.subtypeOf(b.val)) return false;
    }
    return true;
  }

  bool operator()(const DArrStruct& a, const DArrMapN& b) const {
    if (!TSStr.subtypeOf(b.key)) return false;
    for (auto& kv : a.map) {
      if (!kv.second.subtypeOf(b.val)) return false;
    }
    return true;
  }

  bool operator()(SArray a, const DArrMapN& b) const {
    auto const p = toDArrMapN(a);
    return p.key.subtypeOf(b.key) && p.val.subtypeOf(b.val);
  }

  bool operator()(const DArrPacked& a, const DArrPackedN& b) const {
    for (auto& t : a.elems) {
      if (!t.subtypeOf(b.type)) return false;
    }
    return true;
  }

  bool operator()(SArray a, const DArrPackedN& b) const {
    auto p = toDArrPackedN(a);
    return p && p->type.subtypeOf(b.type);
  }

  bool operator()(const DArrPackedN& a, const DArrPacked& b) const {
    return false;
  }
  bool operator()(const DArrPackedN& a, SArray b) const {
    return false;
  }
  bool operator()(const DArrStruct& a, const DArrPacked& b) const {
    return false;
  }
  bool operator()(const DArrStruct& a, const DArrPackedN& b) const {
    return false;
  }
  bool operator()(const DArrPacked& a, const DArrStruct& b) const {
    return false;
  }
  bool operator()(const DArrPackedN& a, const DArrStruct& b) const {
    return false;
  }
  bool operator()(const DArrMapN&, const DArrPackedN&) const {
    return false;
  }
  bool operator()(const DArrMapN&, const DArrPacked&) const {
    return false;
  }
  bool operator()(const DArrMapN&, const DArrStruct&) const {
    return false;
  }
  bool operator()(const DArrMapN&, SArray) const {
    return false;
  }
};

using DisjointEq      = Commute<DisjointEqImpl>;
using DisjointCouldBe = Commute<DisjointCouldBeImpl>;
using ArrUnion        = Commute<ArrUnionImpl>;

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

}

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

Type::Type(const Type& o) noexcept
  : m_bits(o.m_bits)
  , m_dataTag(o.m_dataTag)
{
  SCOPE_EXIT { assert(checkInvariants()); };
  switch (m_dataTag) {
  case DataTag::None:   return;
  case DataTag::Str:    m_data.sval = o.m_data.sval; return;
  case DataTag::ArrVal: m_data.aval = o.m_data.aval; return;
  case DataTag::Int:    m_data.ival = o.m_data.ival; return;
  case DataTag::Dbl:    m_data.dval = o.m_data.dval; return;
  case DataTag::Obj:    new (&m_data.dobj) DObj(o.m_data.dobj); return;
  case DataTag::Cls:    new (&m_data.dcls) DCls(o.m_data.dcls); return;
  case DataTag::RefInner:
    new (&m_data.inner) copy_ptr<Type>(o.m_data.inner);
    return;
  case DataTag::ArrPacked:
    new (&m_data.apacked) copy_ptr<DArrPacked>(o.m_data.apacked);
    return;
  case DataTag::ArrPackedN:
    new (&m_data.apackedn) copy_ptr<DArrPackedN>(o.m_data.apackedn);
    return;
  case DataTag::ArrStruct:
    new (&m_data.astruct) copy_ptr<DArrStruct>(o.m_data.astruct);
    return;
  case DataTag::ArrMapN:
    new (&m_data.amapn) copy_ptr<DArrMapN>(o.m_data.amapn);
    return;
  }
  not_reached();
}

Type::Type(Type&& o) noexcept
  : m_bits(o.m_bits)
  , m_dataTag(o.m_dataTag)
{
  SCOPE_EXIT { assert(checkInvariants());
               assert(o.checkInvariants()); };
  using std::move;
  o.m_dataTag = DataTag::None;
  switch (m_dataTag) {
  case DataTag::None:   return;
  case DataTag::Str:    m_data.sval = o.m_data.sval; return;
  case DataTag::ArrVal: m_data.aval = o.m_data.aval; return;
  case DataTag::Int:    m_data.ival = o.m_data.ival; return;
  case DataTag::Dbl:    m_data.dval = o.m_data.dval; return;
  case DataTag::Obj:    new (&m_data.dobj) DObj(move(o.m_data.dobj)); return;
  case DataTag::Cls:    new (&m_data.dcls) DCls(move(o.m_data.dcls)); return;
  case DataTag::RefInner:
    new (&m_data.inner) copy_ptr<Type>(move(o.m_data.inner));
    return;
  case DataTag::ArrPacked:
    new (&m_data.apacked) copy_ptr<DArrPacked>(move(o.m_data.apacked));
    return;
  case DataTag::ArrPackedN:
    new (&m_data.apackedn) copy_ptr<DArrPackedN>(move(o.m_data.apackedn));
    return;
  case DataTag::ArrStruct:
    new (&m_data.astruct) copy_ptr<DArrStruct>(move(o.m_data.astruct));
    return;
  case DataTag::ArrMapN:
    new (&m_data.amapn) copy_ptr<DArrMapN>(move(o.m_data.amapn));
    return;
  }
  not_reached();
}

Type& Type::operator=(const Type& o) noexcept {
  SCOPE_EXIT { assert(checkInvariants()); };
  this->~Type();
  new (this) Type(o);
  return *this;
}

Type& Type::operator=(Type&& o) noexcept {
  SCOPE_EXIT { assert(checkInvariants());
               assert(o.checkInvariants()); };
  this->~Type();
  new (this) Type(std::move(o));
  return *this;
}

Type::~Type() noexcept {
  assert(checkInvariants());

  switch (m_dataTag) {
  case DataTag::None:
  case DataTag::Str:
  case DataTag::ArrVal:
  case DataTag::Int:
  case DataTag::Dbl:
    return;
  case DataTag::RefInner:
    m_data.inner.~copy_ptr<Type>();
    return;
  case DataTag::Obj:
    m_data.dobj.~DObj();
    return;
  case DataTag::Cls:
    m_data.dcls.~DCls();
    return;
  case DataTag::ArrPacked:
    m_data.apacked.~copy_ptr<DArrPacked>();
    return;
  case DataTag::ArrPackedN:
    m_data.apackedn.~copy_ptr<DArrPackedN>();
    return;
  case DataTag::ArrStruct:
    m_data.astruct.~copy_ptr<DArrStruct>();
    return;
  case DataTag::ArrMapN:
    m_data.amapn.~copy_ptr<DArrMapN>();
    return;
  }
  not_reached();
}

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

template<class Ret, class T, class Function>
struct Type::DJHelperFn {
  template<class Y> Ret operator()(const Y& y) const { return f(t, y); }
  Ret operator()(const T& t) const { not_reached(); }
  Ret operator()() const { return f(); }
  Function f;
  const T& t;
};

template<class Ret, class T, class Function>
Type::DJHelperFn<Ret,T,Function> Type::djbind(const Function& f,
                                              const T& t) const {
  return { f, t };
}

// Dispatcher for the second argument for disjointDataFn.
template<class Ret, class T, class Function>
Ret Type::dj2nd(const Type& o, DJHelperFn<Ret,T,Function> f) const {
  switch (o.m_dataTag) {
  case DataTag::None:       not_reached();
  case DataTag::Str:        return f();
  case DataTag::Obj:        return f();
  case DataTag::Int:        return f();
  case DataTag::Dbl:        return f();
  case DataTag::Cls:        return f();
  case DataTag::RefInner:   return f();
  case DataTag::ArrVal:     return f(o.m_data.aval);
  case DataTag::ArrPacked:  return f(*o.m_data.apacked);
  case DataTag::ArrPackedN: return f(*o.m_data.apackedn);
  case DataTag::ArrStruct:  return f(*o.m_data.astruct);
  case DataTag::ArrMapN:    return f(*o.m_data.amapn);
  }
  not_reached();
}

/*
 * Dispatch an operation on data when this->m_dataTag is different
 * from o.m_dataTag.  Right now these operations only need to do work
 * for array shapes, so the default case (zero-arg call) is applied to
 * most other types.
 *
 * See the disjoint data function objects above.
 */
template<class Function>
typename Function::result_type
Type::disjointDataFn(const Type& o, Function f) const {
  assert(m_dataTag != o.m_dataTag);
  using R = typename Function::result_type;
  switch (m_dataTag) {
  case DataTag::None:       not_reached();
  case DataTag::Str:        return f();
  case DataTag::Obj:        return f();
  case DataTag::Int:        return f();
  case DataTag::Dbl:        return f();
  case DataTag::Cls:        return f();
  case DataTag::RefInner:   return f();
  case DataTag::ArrVal:     return dj2nd(o, djbind<R>(f, m_data.aval));
  case DataTag::ArrPacked:  return dj2nd(o, djbind<R>(f, *m_data.apacked));
  case DataTag::ArrPackedN: return dj2nd(o, djbind<R>(f, *m_data.apackedn));
  case DataTag::ArrStruct:  return dj2nd(o, djbind<R>(f, *m_data.astruct));
  case DataTag::ArrMapN:    return dj2nd(o, djbind<R>(f, *m_data.amapn));
  }
  not_reached();
}

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

bool Type::hasData() const {
  return m_dataTag != DataTag::None;
}

bool Type::equivData(const Type& o) const {
  if (m_dataTag != o.m_dataTag) {
    return disjointDataFn(o, DisjointEq{});
  }

  switch (m_dataTag) {
  case DataTag::None:
    not_reached();
  case DataTag::Str:
    return m_data.sval == o.m_data.sval;
  case DataTag::ArrVal:
    return m_data.aval == o.m_data.aval;
  case DataTag::Int:
    return m_data.ival == o.m_data.ival;
  case DataTag::Dbl:
    // For purposes of Type equivalence, NaNs are equal.
    return m_data.dval == o.m_data.dval ||
           (std::isnan(m_data.dval) && std::isnan(o.m_data.dval));
  case DataTag::Obj:
    assert(!m_data.dobj.whType);
    assert(!o.m_data.dobj.whType);
    return m_data.dobj.type == o.m_data.dobj.type &&
           m_data.dobj.cls.same(o.m_data.dobj.cls);
  case DataTag::Cls:
    return m_data.dcls.type == o.m_data.dcls.type &&
           m_data.dcls.cls.same(o.m_data.dcls.cls);
  case DataTag::RefInner:
    return *m_data.inner == *o.m_data.inner;
  case DataTag::ArrPacked:
    return m_data.apacked->elems == o.m_data.apacked->elems;
  case DataTag::ArrPackedN:
    return m_data.apackedn->type == o.m_data.apackedn->type;
  case DataTag::ArrStruct:
    return m_data.astruct->map == o.m_data.astruct->map;
  case DataTag::ArrMapN:
    return m_data.amapn->key == o.m_data.amapn->key &&
           m_data.amapn->val == o.m_data.amapn->val;
  }
  not_reached();
}

bool Type::subtypeData(const Type& o) const {
  if (m_dataTag != o.m_dataTag) {
    return disjointDataFn(o, DisjointSubtype{});
  }

  switch (m_dataTag) {
  case DataTag::Obj:
    assert(!m_data.dobj.whType);
    assert(!o.m_data.dobj.whType);
    if (m_data.dobj.type == o.m_data.dobj.type &&
        m_data.dobj.cls.same(o.m_data.dobj.cls)) {
      return true;
    }
    if (o.m_data.dobj.type == DObj::Sub) {
      return m_data.dobj.cls.subtypeOf(o.m_data.dobj.cls);
    }
    return false;
  case DataTag::Cls:
    if (m_data.dcls.type == o.m_data.dcls.type &&
        m_data.dcls.cls.same(o.m_data.dcls.cls)) {
      return true;
    }
    if (o.m_data.dcls.type == DCls::Sub) {
      return m_data.dcls.cls.subtypeOf(o.m_data.dcls.cls);
    }
    return false;
  case DataTag::Str:
  case DataTag::ArrVal:
  case DataTag::Int:
  case DataTag::Dbl:
  case DataTag::None:
    return equivData(o);
  case DataTag::RefInner:
    return m_data.inner->subtypeOf(*o.m_data.inner);
  case DataTag::ArrPacked:
    return subtypePacked(*m_data.apacked, *o.m_data.apacked);
  case DataTag::ArrPackedN:
    return m_data.apackedn->type.subtypeOf(o.m_data.apackedn->type);
  case DataTag::ArrStruct:
    return subtypeStruct(*m_data.astruct, *o.m_data.astruct);
  case DataTag::ArrMapN:
    return m_data.amapn->key.subtypeOf(o.m_data.amapn->key) &&
           m_data.amapn->val.subtypeOf(o.m_data.amapn->val);
  }
  not_reached();
}

bool Type::couldBeData(const Type& o) const {
  if (m_dataTag != o.m_dataTag) {
    return disjointDataFn(o, DisjointCouldBe{});
  }

  switch (m_dataTag) {
  case DataTag::None:
    not_reached();
  case DataTag::Obj:
    assert(!m_data.dobj.whType);
    assert(!o.m_data.dobj.whType);
    if (m_data.dobj.type == o.m_data.dobj.type &&
        m_data.dobj.cls.same(o.m_data.dobj.cls)) {
      return true;
    }
    if (m_data.dobj.type == DObj::Sub || o.m_data.dobj.type == DObj::Sub) {
      return m_data.dobj.cls.couldBe(o.m_data.dobj.cls);
    }
    return false;
  case DataTag::Cls:
    if (m_data.dcls.type == o.m_data.dcls.type &&
        m_data.dcls.cls.same(o.m_data.dcls.cls)) {
      return true;
    }
    if (m_data.dcls.type == DCls::Sub || o.m_data.dcls.type == DCls::Sub) {
      return m_data.dcls.cls.couldBe(o.m_data.dcls.cls);
    }
    return false;
  case DataTag::RefInner:
    return m_data.inner->couldBe(*o.m_data.inner);
  case DataTag::ArrVal:
    return m_data.aval == o.m_data.aval;
  case DataTag::Str:
    return m_data.sval == o.m_data.sval;
  case DataTag::Int:
    return m_data.ival == o.m_data.ival;
  case DataTag::Dbl:
    return m_data.dval == o.m_data.dval;
  case DataTag::ArrPacked:
    return couldBePacked(*m_data.apacked, *o.m_data.apacked);
  case DataTag::ArrPackedN:
    return m_data.apackedn->type.couldBe(o.m_data.apackedn->type);
  case DataTag::ArrStruct:
    return couldBeStruct(*m_data.astruct, *o.m_data.astruct);
  case DataTag::ArrMapN:
    return m_data.amapn->key.couldBe(o.m_data.amapn->key) &&
           m_data.amapn->val.couldBe(o.m_data.amapn->val);
  }
  not_reached();
}

bool Type::operator==(const Type& o) const {
  assert(checkInvariants());
  assert(o.checkInvariants());

  if (m_bits != o.m_bits) return false;
  if (hasData() != o.hasData()) return false;
  if (!hasData() && !o.hasData()) return true;

  if (is_specialized_wait_handle(*this)) {
    if (is_specialized_wait_handle(o)) {
      return wait_handle_inner(*this) == wait_handle_inner(o);
    }
    return false;
  }
  if (is_specialized_wait_handle(o)) {
    return false;
  }

  return equivData(o);
}

size_t Type::hash() const {
  using U1 = std::underlying_type<decltype(m_bits)>::type;
  using U2 = std::underlying_type<decltype(m_dataTag)>::type;
  auto const rawBits = U1{m_bits};
  auto const rawTag  = static_cast<U2>(m_dataTag);
  return folly::hash::hash_combine(rawBits, rawTag);
}

bool Type::subtypeOf(Type o) const {
  assert(checkInvariants());
  assert(o.checkInvariants());

  if (is_specialized_wait_handle(*this)) {
    if (is_specialized_wait_handle(o)) {
      return
        wait_handle_inner(*this).subtypeOf(wait_handle_inner(o)) &&
        wait_handle_outer(*this).subtypeOf(wait_handle_outer(o));
    }
    return wait_handle_outer(*this).subtypeOf(o);
  }
  if (is_specialized_wait_handle(o)) {
    return subtypeOf(wait_handle_outer(o));
  }

  auto const isect = static_cast<trep>(m_bits & o.m_bits);
  if (isect != m_bits) return false;
  if (!mayHaveData(isect)) return true;

  // No data is always more general.
  if (!hasData() && !o.hasData()) return true;
  if (!o.hasData()) {
    assert(hasData());
    return true;
  }

  // Both have data, and the intersection allows it, so it depends on
  // what the data says.
  return hasData() && subtypeData(o);
}

bool Type::strictSubtypeOf(Type o) const {
  assert(checkInvariants());
  assert(o.checkInvariants());
  return *this != o && subtypeOf(o);
}

bool Type::couldBe(Type o) const {
  assert(checkInvariants());
  assert(o.checkInvariants());

  if (is_specialized_wait_handle(*this)) {
    if (is_specialized_wait_handle(o)) {
      return wait_handle_inner(*this).couldBe(wait_handle_inner(o));
    }
    return o.couldBe(wait_handle_outer(*this));
  }
  if (is_specialized_wait_handle(o)) {
    return couldBe(wait_handle_outer(o));
  }

  auto const isect = static_cast<trep>(m_bits & o.m_bits);
  if (isect == 0) return false;
  if (subtypeOf(o) || o.subtypeOf(*this)) return true;
  if (!mayHaveData(isect)) return true;

  /*
   * From here we have an intersection that may have data, and we know
   * that neither type completely contains the other.
   *
   * For most of our types, where m_data represents an exact constant
   * value, this just means the types only overlap if there is no
   * data.
   *
   * The exception to that are option types with data,
   * objects/classes, and arrays.
   */

  /*
   * If the intersection allowed data, and either type was an option
   * type, we can simplify the case to whether the unopt'd version of
   * the option type couldBe the other type.  (The case where
   * TInitNull was the overlapping part would already be handled
   * above, because !mayHaveData(TInitNull).)
   */
  if (is_opt(*this)) return is_opt(o) ? true : unopt(*this).couldBe(o);
  if (is_opt(o))     return unopt(o).couldBe(*this);

  if (hasData() && o.hasData()) {
    assert(mayHaveData(isect));
    return couldBeData(o);
  }
  return true;
}

bool Type::checkInvariants() const {
  assert(isPredefined(m_bits));
  assert(!hasData() || mayHaveData(m_bits));

  /*
   * TODO(#3696042): for static arrays, we could enforce that all
   * inner-types are also static (this may would require changes to
   * things like union_of to ensure that we never promote an inner
   * type to a counted type).
   */

  switch (m_dataTag) {
  case DataTag::None:   break;
  case DataTag::Str:    assert(m_data.sval->isStatic()); break;
  case DataTag::Dbl:    break;
  case DataTag::Int:    break;
  case DataTag::RefInner:
    m_data.inner->checkInvariants();
    assert(!m_data.inner->couldBe(TRef));
    break;
  case DataTag::Cls:    break;
  case DataTag::Obj:
    if (auto t = m_data.dobj.whType.get()) {
      t->checkInvariants();
    }
    break;
  case DataTag::ArrVal:
    assert(m_data.aval->isStatic());
    assert(!m_data.aval->empty());
    break;
  case DataTag::ArrPacked:
    assert(!m_data.apacked->elems.empty());
    for (DEBUG_ONLY auto& v : m_data.apacked->elems) {
      assert(v.subtypeOf(TInitGen));
    }
    break;
  case DataTag::ArrStruct:
    assert(!m_data.astruct->map.empty());
    for (DEBUG_ONLY auto& kv : m_data.astruct->map) {
      assert(kv.second.subtypeOf(TInitGen));
    }
    break;
  case DataTag::ArrPackedN:
    assert(m_data.apackedn->type.subtypeOf(TInitGen));
    break;
  case DataTag::ArrMapN:
    assert(m_data.amapn->key.subtypeOf(TInitCell));
    assert(m_data.amapn->val.subtypeOf(TInitGen));
    break;
  }
  return true;
}

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

Type wait_handle(const Index& index, Type inner) {
  auto const rwh = index.builtin_class(s_WaitHandle.get());
  auto t = subObj(rwh);
  t.m_data.dobj.whType = make_copy_ptr<Type>(std::move(inner));
  return t;
}

bool is_specialized_wait_handle(const Type& t) {
  return
    t.m_dataTag == DataTag::Obj &&
    !!t.m_data.dobj.whType.get();
}

Type wait_handle_inner(const Type& t) {
  assert(is_specialized_wait_handle(t));
  return *t.m_data.dobj.whType;
}

Type Type::wait_handle_outer(const Type& wh) {
  auto ret      = Type{wh.m_bits};
  ret.m_dataTag = DataTag::Obj;
  new (&ret.m_data.dobj) DObj(wh.m_data.dobj.type, wh.m_data.dobj.cls);
  return ret;
}

Type sval(SString val) {
  assert(val->isStatic());
  auto r        = Type { BSStr };
  r.m_data.sval = val;
  r.m_dataTag   = DataTag::Str;
  return r;
}

Type ival(int64_t val) {
  auto r        = Type { BInt };
  r.m_data.ival = val;
  r.m_dataTag   = DataTag::Int;
  return r;
}

Type dval(double val) {
  auto r        = Type { BDbl };
  r.m_data.dval = val;
  r.m_dataTag   = DataTag::Dbl;
  return r;
}

Type aval(SArray val) {
  assert(val->isStatic());
  if (val->empty()) return aempty();
  auto r        = Type { BSArrN };
  r.m_data.aval = val;
  r.m_dataTag   = DataTag::ArrVal;
  return r;
}

Type aempty()         { return Type { BSArrE }; }
Type sempty()         { return sval(s_empty.get()); }
Type counted_aempty() { return Type { BCArrE }; }
Type some_aempty()    { return Type { BArrE }; }

Type subObj(res::Class val) {
  auto r = Type { BObj };
  new (&r.m_data.dobj) DObj(
    val.couldBeOverriden() ? DObj::Sub : DObj::Exact,
    val
  );
  r.m_dataTag = DataTag::Obj;
  return r;
}

Type objExact(res::Class val) {
  auto r = Type { BObj };
  new (&r.m_data.dobj) DObj(DObj::Exact, val);
  r.m_dataTag = DataTag::Obj;
  return r;
}

Type subCls(res::Class val) {
  auto r        = Type { BCls };
  new (&r.m_data.dcls) DCls {
    val.couldBeOverriden() ? DCls::Sub : DCls::Exact,
    val
  };
  r.m_dataTag = DataTag::Cls;
  return r;
}

Type clsExact(res::Class val) {
  auto r        = Type { BCls };
  new (&r.m_data.dcls) DCls { DCls::Exact, val };
  r.m_dataTag   = DataTag::Cls;
  return r;
}


Type ref_to(Type t) {
  assert(t.subtypeOf(TInitCell));
  auto r = Type{BRef};
  new (&r.m_data.inner) copy_ptr<Type> {make_copy_ptr<Type>(std::move(t))};
  r.m_dataTag = DataTag::RefInner;
  return r;
}

bool is_ref_with_inner(const Type& t) {
  return t.m_dataTag == DataTag::RefInner;
}

bool is_specialized_array(const Type& t) {
  switch (t.m_dataTag) {
  case DataTag::None:
  case DataTag::Str:
  case DataTag::Obj:
  case DataTag::Int:
  case DataTag::Dbl:
  case DataTag::Cls:
  case DataTag::RefInner:
    return false;
  case DataTag::ArrVal:
  case DataTag::ArrPacked:
  case DataTag::ArrPackedN:
  case DataTag::ArrStruct:
  case DataTag::ArrMapN:
    return true;
  }
  not_reached();
}

Type arr_packed(std::vector<Type> elems) {
  assert(!elems.empty());
  auto r = Type { BArrN };
  new (&r.m_data.apacked) copy_ptr<DArrPacked>(
    make_copy_ptr<DArrPacked>(std::move(elems))
  );
  r.m_dataTag = DataTag::ArrPacked;
  return r;
}

Type sarr_packed(std::vector<Type> elems) {
  auto t = arr_packed(std::move(elems));
  t.m_bits = BSArrN;
  return t;
}

Type carr_packed(std::vector<Type> elems) {
  auto t = arr_packed(std::move(elems));
  t.m_bits = BCArrN;
  return t;
}

Type arr_packedn(Type t) {
  auto r = Type { BArrN };
  new (&r.m_data.apackedn) copy_ptr<DArrPackedN>(
    make_copy_ptr<DArrPackedN>(std::move(t))
  );
  r.m_dataTag = DataTag::ArrPackedN;
  return r;
}

Type sarr_packedn(Type t) {
  auto r = arr_packedn(std::move(t));
  r.m_bits = BSArrN;
  return r;
}

Type carr_packedn(Type t) {
  auto r = arr_packedn(std::move(t));
  r.m_bits = BCArrN;
  return r;
}

Type arr_struct(StructMap m) {
  assert(!m.empty());
  auto r = Type { BArrN };
  new (&r.m_data.astruct) copy_ptr<DArrStruct>(
    make_copy_ptr<DArrStruct>(std::move(m))
  );
  r.m_dataTag = DataTag::ArrStruct;
  return r;
}

Type sarr_struct(StructMap m) {
  auto r = arr_struct(std::move(m));
  r.m_bits = BSArrN;
  return r;
}

Type carr_struct(StructMap m) {
  auto r = arr_struct(std::move(m));
  r.m_bits = BCArrN;
  return r;
}

Type arr_mapn(Type k, Type v) {
  auto r = Type { BArrN };
  new (&r.m_data.amapn) copy_ptr<DArrMapN>(
    make_copy_ptr<DArrMapN>(std::move(k), std::move(v))
  );
  r.m_dataTag = DataTag::ArrMapN;
  return r;
}

Type sarr_mapn(Type k, Type v) {
  auto r = arr_mapn(k, v);
  r.m_bits = BSArrN;
  return r;
}

Type carr_mapn(Type k, Type v) {
  auto r = arr_mapn(std::move(k), std::move(v));
  r.m_bits = BCArrN;
  return r;
}

Type opt(Type t) {
  assert(canBeOptional(t.m_bits));
  auto ret = t;
  ret.m_bits = static_cast<trep>(ret.m_bits | BInitNull);
  return ret;
}

Type unopt(Type t) {
  assert(is_opt(t));
  t.m_bits = static_cast<trep>(t.m_bits & ~BInitNull);
  assert(!is_opt(t));
  return t;
}

bool is_opt(Type t) {
  if (t.m_bits == BInitNull) return false;
  if (!t.couldBe(TInitNull)) return false;
  auto const nonNullBits = static_cast<trep>(t.m_bits & ~BInitNull);
  return isPredefined(nonNullBits) && canBeOptional(nonNullBits);
}

bool is_specialized_obj(const Type& t) {
  return t.m_dataTag == DataTag::Obj;
}

bool is_specialized_cls(const Type& t) {
  return t.m_dataTag == DataTag::Cls;
}

Type objcls(const Type& t) {
  if (t.subtypeOf(TObj) && is_specialized_obj(t)) {
    auto const d = dobj_of(t);
    return d.type == DObj::Exact ? clsExact(d.cls) : subCls(d.cls);
  }
  return TCls;
}

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

folly::Optional<Cell> tv(Type t) {
  assert(t.checkInvariants());

  switch (t.m_bits) {
  case BUninit:      return make_tv<KindOfUninit>();
  case BInitNull:    return make_tv<KindOfNull>();
  case BTrue:        return make_tv<KindOfBoolean>(true);
  case BFalse:       return make_tv<KindOfBoolean>(false);
  case BCArrE:       /* fallthrough */
  case BSArrE:       return make_tv<KindOfArray>(staticEmptyArray());
  default:
    if (is_opt(t)) {
      break;
    }
    switch (t.m_dataTag) {
    case DataTag::Int:    return make_tv<KindOfInt64>(t.m_data.ival);
    case DataTag::Dbl:    return make_tv<KindOfDouble>(t.m_data.dval);
    case DataTag::Str:    return make_tv<KindOfStaticString>(t.m_data.sval);
    case DataTag::ArrVal:
      if ((t.m_bits & BArrN) == t.m_bits) {
        return make_tv<KindOfArray>(const_cast<ArrayData*>(t.m_data.aval));
      }
      break;
    case DataTag::ArrStruct:
    case DataTag::ArrPacked:
      // TODO(#3696042): we could materialize a static array here if
      // we check if a whole specialized array is constants, and if it
      // can't be empty.
      break;
    case DataTag::RefInner:
    case DataTag::ArrPackedN:
    case DataTag::ArrMapN:
    case DataTag::Obj:
    case DataTag::Cls:
    case DataTag::None:
      break;
    }
  }

  return folly::none;
}

Type type_of_istype(IsTypeOp op) {
  switch (op) {
  case IsTypeOp::Null:   return TNull;
  case IsTypeOp::Bool:   return TBool;
  case IsTypeOp::Int:    return TInt;
  case IsTypeOp::Dbl:    return TDbl;
  case IsTypeOp::Str:    return TStr;
  case IsTypeOp::Arr:    return TArr;
  case IsTypeOp::Obj:    return TObj;
  case IsTypeOp::Scalar: always_assert(0);
  }
  not_reached();
}

DObj dobj_of(const Type& t) {
  assert(t.checkInvariants());
  assert(is_specialized_obj(t));
  return t.m_data.dobj;
}

DCls dcls_of(Type t) {
  assert(t.checkInvariants());
  assert(is_specialized_cls(t));
  return t.m_data.dcls;
}

Type from_cell(Cell cell) {
  assert(cellIsPlausible(cell));

  switch (cell.m_type) {
  case KindOfUninit:   return TUninit;
  case KindOfNull:     return TInitNull;
  case KindOfBoolean:  return cell.m_data.num ? TTrue : TFalse;
  case KindOfInt64:    return ival(cell.m_data.num);
  case KindOfDouble:   return dval(cell.m_data.dbl);

  case KindOfStaticString:
  case KindOfString:
    always_assert(cell.m_data.pstr->isStatic());
    return sval(cell.m_data.pstr);

  case KindOfArray:
    always_assert(cell.m_data.parr->isStatic());
    return aval(cell.m_data.parr);

  case KindOfRef:
  case KindOfObject:
  case KindOfResource:
  default:
    break;
  }
  always_assert(0 && "reference counted type in from_cell");
}

Type from_DataType(DataType dt) {
  switch (dt) {
  case KindOfUninit:   return TUninit;
  case KindOfNull:     return TInitNull;
  case KindOfBoolean:  return TBool;
  case KindOfInt64:    return TInt;
  case KindOfDouble:   return TDbl;
  case KindOfStaticString:
  case KindOfString:   return TStr;
  case KindOfArray:    return TArr;
  case KindOfRef:      return TRef;
  case KindOfObject:   return TObj;
  case KindOfResource: return TRes;
  default:
    break;
  }
  always_assert(0 && "dt in from_DataType didn't satisfy preconditions");
}

Type from_hni_constraint(SString s) {
  if (!s) return TGen;

  auto p   = s->data();
  auto ret = TBottom;

  if (*p == '?') {
    ret = union_of(ret, TInitNull);
    ++p;
  }

  if (!strcasecmp(p, "HH\\resource")) return union_of(ret, TRes);
  if (!strcasecmp(p, "HH\\bool"))     return union_of(ret, TBool);
  if (!strcasecmp(p, "HH\\int"))      return union_of(ret, TInt);
  if (!strcasecmp(p, "HH\\float"))    return union_of(ret, TDbl);
  if (!strcasecmp(p, "HH\\num"))      return union_of(ret, TNum);
  if (!strcasecmp(p, "HH\\string"))   return union_of(ret, TStr);
  if (!strcasecmp(p, "array"))        return union_of(ret, TArr);
  if (!strcasecmp(p, "HH\\mixed"))    return TInitGen;

  // It might be an object, or we might want to support type aliases in HNI at
  // some point.  For now just be conservative.
  return TGen;
}

Type Type::unionArr(const Type& a, const Type& b) {
  assert(!a.subtypeOf(b));
  assert(!b.subtypeOf(a));
  assert(is_specialized_array(a));
  assert(is_specialized_array(b));

  auto ret = Type{};
  auto const newBits = combine_arr_bits(a.m_bits, b.m_bits);

  if (a.m_dataTag != b.m_dataTag) {
    ret = a.disjointDataFn(b, ArrUnion{});
    ret.m_bits = newBits;
    return ret;
  }

  switch (a.m_dataTag) {
  case DataTag::None:
  case DataTag::Str:
  case DataTag::Obj:
  case DataTag::Int:
  case DataTag::Dbl:
  case DataTag::Cls:
  case DataTag::RefInner:
    not_reached();
  case DataTag::ArrVal:
    {
      ret = ArrUnion{}(a.m_data.aval, b.m_data.aval);
      ret.m_bits = newBits;
      return ret;
    }
  case DataTag::ArrPacked:
    {
      ret = ArrUnion{}(*a.m_data.apacked, *b.m_data.apacked);
      ret.m_bits = newBits;
      return ret;
    }
  case DataTag::ArrPackedN:
    {
      ret = a;
      ret.m_bits = newBits;
      ret.m_data.apackedn->type = union_of(a.m_data.apackedn->type,
                                           b.m_data.apackedn->type);
      return ret;
    }
  case DataTag::ArrStruct:
    {
      ret = ArrUnion{}(*a.m_data.astruct, *b.m_data.astruct);
      ret.m_bits = newBits;
      return ret;
    }
  case DataTag::ArrMapN:
    {
      ret = arr_mapn(union_of(a.m_data.amapn->key, b.m_data.amapn->key),
                     union_of(a.m_data.amapn->val, b.m_data.amapn->val));
      ret.m_bits = newBits;
      return ret;
    }
  }
  not_reached();
}

Type union_of(Type a, Type b) {
  if (a.subtypeOf(b)) return b;
  if (b.subtypeOf(a)) return a;

  /*
   * We need to check this before specialized objects, including the case where
   * one of them was TInitNull, because otherwise we'll go down the
   * is_specialized_obj paths and lose the wait handle information.
   */
  if (is_specialized_wait_handle(a)) {
    if (is_specialized_wait_handle(b)) {
      *a.m_data.dobj.whType = union_of(
        *a.m_data.dobj.whType,
        *b.m_data.dobj.whType
      );
      return a;
    }
    if (b == TInitNull) return opt(a);
  }
  if (is_specialized_wait_handle(b)) {
    if (a == TInitNull) return opt(b);
  }

  // When both types are strict subtypes of TObj or TOptObj or both
  // are strict subtypes of TCls we look for a common ancestor if one
  // exists.
  if (is_specialized_obj(a) && is_specialized_obj(b)) {
    auto keepOpt = is_opt(a) || is_opt(b);
    auto t = a.m_data.dobj.cls.commonAncestor(dobj_of(b).cls);
    // We need not to distinguish between Obj<=T and Obj=T, and always
    // return an Obj<=Ancestor, because that is the single type that
    // includes both children.
    if (t) return keepOpt ? opt(subObj(*t)) : subObj(*t);
    return keepOpt ? TOptObj : TObj;
  }
  if (a.strictSubtypeOf(TCls) && b.strictSubtypeOf(TCls)) {
    auto t = a.m_data.dcls.cls.commonAncestor(dcls_of(b).cls);
    // Similar to above, this must always return an Obj<=Ancestor.
    return t ? subCls(*t) : TCls;
  }

  if (is_specialized_array(a)) {
    if (is_specialized_array(b)) {
      DEBUG_ONLY auto const shouldBeOpt = is_opt(a) || is_opt(b);
      auto const t = Type::unionArr(a, b);
      if (shouldBeOpt) assert(is_opt(t));
      return t;
    }
    if (b.subtypeOf(TOptArrE)) {
      // Keep a's data.
      a.m_bits = combine_arr_bits(a.m_bits, b.m_bits);
      return a;
    }
    if (b.subtypeOf(TOptArr)) {
      // We can't keep a's data, since it contains unknown non-empty
      // arrays.  (If it were specialized we'd be in the unionArr
      // path, which handles trying to keep as much data as we can.)
      return Type { combine_arr_bits(a.m_bits, b.m_bits) };
    }
  } else {
    if (is_specialized_array(b)) {
      // Flip args and do the above.
      return union_of(b, a);
    }
  }

  if (is_ref_with_inner(a) && is_ref_with_inner(b)) {
    return ref_to(union_of(*a.m_data.inner, *b.m_data.inner));
  }

#define X(y) if (a.subtypeOf(y) && b.subtypeOf(y)) return y;
  X(TInt)
  X(TDbl)
  X(TSStr)
  X(TCStr)
  X(TSArr)
  X(TCArr)
  X(TArrE)
  X(TArrN)
  X(TObj)
  X(TCls)
  X(TNull)
  X(TBool)
  X(TNum)
  X(TStr)
  X(TArr)

  /*
   * Merging option types tries to preserve subtype information where it's
   * possible.  E.g. if you union InitNull and Obj<=Foo, we want OptObj<=Foo to
   * be the result.
   */
  if (a == TInitNull && canBeOptional(b.m_bits)) return opt(b);
  if (b == TInitNull && canBeOptional(a.m_bits)) return opt(a);

  // Optional types where the non-Null part is already a union or can have a
  // value need to be manually tried (e.g. if we are merging TOptTrue and TOptFalse,
  // we want TOptBool, or merging TOptInt=1 and TOptInt=2 should give us TOptInt).
  X(TOptBool)
  X(TOptInt)
  X(TOptDbl)
  X(TOptNum)
  X(TOptSStr)
  X(TOptStr)
  X(TOptArrN)
  X(TOptArrE)
  X(TOptSArr)
  X(TOptCArr)
  X(TOptArr)
  X(TOptObj)

  X(TInitPrim)
  X(TPrim)
  X(TInitUnc)
  X(TUnc)
  X(TInitCell)
  X(TCell)
  X(TInitGen)
  X(TGen)
#undef X

  return TTop;
}

Type promote_emptyish(Type a, Type b) {
  if (is_opt(a)) a = unopt(a);
  if (a.subtypeOf(sempty())) {
    return b;
  }
  auto t = trep(a.m_bits & ~(BNull | BFalse));
  if (!isPredefined(t)) {
    if (trep(t & BInitPrim) == t) {
      t = BInitPrim;
    } else if (trep(t & BInitUnc) == t) {
      t = BInitUnc;
    } else if (trep(t & BInitCell) == t) {
      t = BInitCell;
    } else {
      t = BInitGen;
    }
    return union_of(Type { t }, b);
  }
  a.m_bits = t;
  return union_of(a, b);
}

Type widening_union(const Type& a, const Type& b) {
  if (a == b) return a;

  // Currently the only types in our typesystem that have infinitely
  // growing chains of union_of are specialized arrays.
  if (!is_specialized_array(a) || !is_specialized_array(b)) {
    return union_of(a, b);
  }

  // This (throwing away the data) is overly conservative, but works
  // for now.
  auto const newBits = combine_arr_bits(a.m_bits, b.m_bits);
  return Type { newBits };
}

Type stack_flav(Type a) {
  if (a.subtypeOf(TUninit))   return TUninit;
  if (a.subtypeOf(TInitCell)) return TInitCell;
  if (a.subtypeOf(TRef))      return TRef;
  if (a.subtypeOf(TGen))      return TGen;
  if (a.subtypeOf(TCls))      return TCls;
  always_assert(0 && "stack_flav passed invalid type");
}

Type loosen_statics(Type a) {
  // TODO(#3696042): this should be modified to keep specialized array
  // information, including whether the array is possibly empty.
  if (a.couldBe(TSStr)) a = union_of(a, TStr);
  if (a.couldBe(TSArr)) a = union_of(a, TArr);
  return a;
}

Type loosen_values(Type a) {
  return a.strictSubtypeOf(TInt) ? TInt :
         a.strictSubtypeOf(TDbl) ? TDbl :
         a.strictSubtypeOf(TBool) ? TBool :
         a.strictSubtypeOf(TSStr) ? TSStr :
         a.strictSubtypeOf(TSArr) ? TSArr :
         a == TOptFalse || a == TOptTrue ? TOptBool :
         a;
}

Type remove_uninit(Type t) {
  assert(t.subtypeOf(TCell));
  if (!t.couldBe(TUninit))  return t;
  if (t.subtypeOf(TUninit)) return TBottom;
  if (t.subtypeOf(TNull))   return TInitNull;
  if (t.subtypeOf(TPrim))   return TInitPrim;
  if (t.subtypeOf(TUnc))    return TInitUnc;
  return TInitCell;
}

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

/*
 * For known strings that are strictly integers, we'll set both the
 * known integer and string keys, so generally the int case should be
 * checked first below.
 *
 * For keys that could be strings, we have to assume they could be
 * strictly-integer strings.  After disection, the effective type we
 * can assume for the array key is in `type'.
 */

struct ArrKey {
  folly::Optional<int64_t> i;
  folly::Optional<SString> s;
  Type type;
};

ArrKey disect_key(const Type& keyTy) {
  auto ret = ArrKey{};

  if (keyTy.strictSubtypeOf(TInt)) {
    ret.i = keyTy.m_data.ival;
    ret.type = keyTy;
    return ret;
  }
  if (keyTy.strictSubtypeOf(TStr) && keyTy.m_dataTag == DataTag::Str) {
    ret.s = keyTy.m_data.sval;
    ret.type = keyTy;
    int64_t i;
    if (keyTy.m_data.sval->isStrictlyInteger(i)) {
      ret.i = i;
      ret.type = TInt;
    }
    return ret;
  }
  if (keyTy.strictSubtypeOf(TDbl)) {
    ret.i = static_cast<int64_t>(keyTy.m_data.dval);
    ret.type = TInt;
    return ret;
  }
  if (keyTy.subtypeOf(TNum)) {
    ret.type = TInt;
    return ret;
  }

  if (keyTy.subtypeOf(TNull)) {
    ret.s = s_empty.get();
    ret.type = sempty();
    return ret;
  }
  if (keyTy.subtypeOf(TRes)) {
    ret.type = TInt;
    return ret;
  }

  if (keyTy.subtypeOf(TTrue)) {
    ret.i = 1;
    ret.type = TInt;
    return ret;
  }
  if (keyTy.subtypeOf(TFalse)) {
    ret.i = 0;
    ret.type = TInt;
    return ret;
  }
  if (keyTy.subtypeOf(TBool)) {
    ret.type = TInt;
    return ret;
  }

  // If we have an OptStr with a value, we can at least exclude the
  // possibility of integer-like strings by looking at that value.
  // But we can't use the value itself, because if it is null the key
  // will act like the empty string.  In that case, the code uses the
  // static empty string, so if it was an OptCStr it needs to
  // incorporate SStr, but an OptSStr can stay as SStr.
  if (keyTy.strictSubtypeOf(TOptStr) && keyTy.m_dataTag == DataTag::Str) {
    int64_t ignore;
    if (!keyTy.m_data.sval->isStrictlyInteger(ignore)) {
      ret.type = keyTy.strictSubtypeOf(TOptSStr) ? TSStr : TStr;
      return ret;
    }
  }

  // Nothing we can do in other cases that could be strings (without
  // statically known values)---they may behave like integers at
  // runtime.

  // TODO(#3774082): We should be able to set this to a Str|Int type.
  ret.type = TInitCell;
  return ret;
}

Type array_elem(const Type& arr, const Type& undisectedKey) {
  assert(arr.subtypeOf(TArr));

  auto const key = disect_key(undisectedKey);
  auto ty = [&]() -> Type {
    switch (arr.m_dataTag) {
    case DataTag::Str:
    case DataTag::Obj:
    case DataTag::Int:
    case DataTag::Dbl:
    case DataTag::Cls:
    case DataTag::RefInner:
      not_reached();

    case DataTag::None:
      return arr.subtypeOf(TSArr) ? TInitUnc : TInitCell;

    case DataTag::ArrVal:
      if (key.i) {
        if (auto const r = arr.m_data.aval->nvGet(*key.i)) {
          return from_cell(*r);
        }
        return TInitNull;
      }
      if (key.s) {
        if (auto const r = arr.m_data.aval->nvGet(*key.s)) {
          return from_cell(*r);
        }
        return TInitNull;
      }
      return arr.subtypeOf(TSArr) ? TInitUnc : TInitCell;

    /*
     * In the following cases, note that if you get an elem out of an
     * array that doesn't exist, php semantics are to return null (after
     * a warning).  So in cases where we don't know the key statically
     * we need to union TInitNull into the result.
     */

    case DataTag::ArrPacked:
      if (!key.i) {
        return union_of(packed_values(*arr.m_data.apacked), TInitNull);
      }
      if (*key.i >= 0 && *key.i < arr.m_data.apacked->elems.size()) {
        return arr.m_data.apacked->elems[*key.i];
      }
      return TInitNull;

    case DataTag::ArrPackedN:
      return union_of(arr.m_data.apackedn->type, TInitNull);

    case DataTag::ArrStruct:
      if (key.s) {
        auto it = arr.m_data.astruct->map.find(*key.s);
        return it != end(arr.m_data.astruct->map)
          ? it->second
          : TInitNull;
      }
      return union_of(struct_values(*arr.m_data.astruct), TInitNull);

    case DataTag::ArrMapN:
      return union_of(arr.m_data.amapn->val, TInitNull);
    }
    not_reached();
  }();

  if (!ty.subtypeOf(TInitCell)) {
    ty = TInitCell;
  } else if (arr.couldBe(TArrE)) {
    ty = union_of(std::move(ty), TInitNull);
  }
  return ty;
}

/*
 * Note: for now we're merging counted arrays into whatever type it used to
 * have in the following set functions, and returning arr_*'s in some cases
 * where we could know it was a carr_*.
 *
 * To be able to assume it is actually counted it if used to be static, we need
 * to add code checking for keys that are one of the "illegal offset type" of
 * keys.
 *
 * A similar issue applies if you want to take out emptiness when a set occurs.
 * If the key could be an illegal key type, the array may remain empty.
 */

// Do the effects of array_set but without handling possibly emptiness
// of `arr'.
Type arrayN_set(Type arr, const Type& undisectedKey, const Type& val) {
  auto const key = disect_key(undisectedKey);

  auto ensure_counted = [&] {
    // TODO(#3696042): this same logic should be in loosen_statics.
    if (arr.m_bits & BCArr) return;
    if (arr.m_bits == BSArrN) {
      arr.m_bits = combine_arr_bits(arr.m_bits, BCArrN);
    } else if (arr.m_bits == BSArrE) {
      arr.m_bits = combine_arr_bits(arr.m_bits, BCArrE);
    } else {
      arr.m_bits = combine_arr_bits(arr.m_bits, BCArr);
    }
  };

  switch (arr.m_dataTag) {
  case DataTag::Str:
  case DataTag::Obj:
  case DataTag::Int:
  case DataTag::Dbl:
  case DataTag::Cls:
  case DataTag::RefInner:
    not_reached();

  case DataTag::None:
    ensure_counted();
    return arr;

  case DataTag::ArrVal:
    {
      if (auto d = toDArrStruct(arr.m_data.aval)) {
        return arrayN_set(arr_struct(std::move(d->map)), undisectedKey, val);
      }
      if (auto d = toDArrPacked(arr.m_data.aval)) {
        return arrayN_set(arr_packed(std::move(d->elems)), undisectedKey,
                          val);
      }
      if (auto d = toDArrPackedN(arr.m_data.aval)) {
        return arrayN_set(arr_packedn(d->type), undisectedKey, val);
      }
      auto d = toDArrMapN(arr.m_data.aval);
      return arrayN_set(arr_mapn(d.key, d.val), undisectedKey, val);
    }

  case DataTag::ArrPacked:
    ensure_counted();
    if (key.i) {
      if (*key.i >= 0 && *key.i < arr.m_data.apacked->elems.size()) {
        auto& current = arr.m_data.apacked->elems[*key.i];
        if (current.subtypeOf(TInitCell)) {
          current = val;
        }
        return arr;
      }
      if (*key.i == arr.m_data.apacked->elems.size()) {
        arr.m_data.apacked->elems.push_back(val);
        return arr;
      }
    }
    return arr_mapn(union_of(TInt, key.type),
                    union_of(packed_values(*arr.m_data.apacked), val));

  case DataTag::ArrPackedN:
    ensure_counted();
    return arr_mapn(union_of(TInt, key.type),
                    union_of(arr.m_data.apackedn->type, val));

  case DataTag::ArrStruct:
    ensure_counted();
    {
      auto& map = arr.m_data.astruct->map;
      if (key.s) {
        auto it = map.find(*key.s);
        if (it == end(map)) {
          map[*key.s] = val;
        } else {
          if (it->second.subtypeOf(TInitCell)) {
            it->second = val;
          }
        }
        return arr;
      }
      return arr_mapn(union_of(key.type, TSStr),
                      union_of(struct_values(*arr.m_data.astruct), val));
    }

  case DataTag::ArrMapN:
    ensure_counted();
    return arr_mapn(union_of(key.type, arr.m_data.amapn->key),
                    union_of(val, arr.m_data.amapn->val));
  }

  not_reached();
}

Type array_set(Type arr, const Type& undisectedKey, const Type& val) {
  assert(arr.subtypeOf(TArr));

  // Unless you know an array can't cow, you don't know if the TRef
  // will stay a TRef or turn back into a TInitCell.  Generally you
  // want a TInitGen.
  always_assert(!val.subtypeOf(TRef) &&
         "You probably don't want to put Ref types into arrays ...");

  auto nonEmptyPart =
    arr.couldBe(TArrN) ? arrayN_set(arr, undisectedKey, val)
                       : TBottom;
  if (!arr.couldBe(TArrE)) {
    assert(nonEmptyPart != TBottom);
    return nonEmptyPart;
  }

  // Union in the effects of doing the set if the array was empty.
  auto const key = disect_key(undisectedKey);
  auto emptyPart = [&] {
    if (key.s && !key.i) {
      auto map = StructMap{};
      map[*key.s] = val;
      return arr_struct(std::move(map));
    }
    if (key.i && *key.i == 0) return arr_packed({val});
    // Keeping the ArrE for now just because we would need to check
    // the key.type is not an invalid key (array or object) to prove
    // it's non-empty now.
    return union_of(arr_mapn(key.type, val), arr);
  }();
  return union_of(std::move(nonEmptyPart), std::move(emptyPart));
}

// Do the same as array_newelem_key, but ignoring possible emptiness
// of `arr'.
std::pair<Type,Type> arrayN_newelem_key(const Type& arr, const Type& val) {
  switch (arr.m_dataTag) {
  case DataTag::Str:
  case DataTag::Obj:
  case DataTag::Int:
  case DataTag::Dbl:
  case DataTag::Cls:
  case DataTag::RefInner:
    not_reached();

  case DataTag::None:
    return { TArrN, TInt };

  case DataTag::ArrVal:
    {
      if (auto d = toDArrStruct(arr.m_data.aval)) {
        return array_newelem_key(arr_struct(std::move(d->map)), val);
      }
      if (auto d = toDArrPacked(arr.m_data.aval)) {
        return array_newelem_key(arr_packed(std::move(d->elems)), val);
      }
      if (auto d = toDArrPackedN(arr.m_data.aval)) {
        return array_newelem_key(arr_packedn(d->type), val);
      }
      auto d = toDArrMapN(arr.m_data.aval);
      return array_newelem_key(arr_mapn(d.key, d.val), val);
    }

  case DataTag::ArrPacked:
    {
      auto v = arr.m_data.apacked->elems;
      v.push_back(val);
      return { arr_packed(std::move(v)), ival(v.size() - 1) };
    }

  case DataTag::ArrPackedN:
    return { arr_packedn(union_of(arr.m_data.apackedn->type, val)), TInt };

  case DataTag::ArrStruct:
    return { arr_mapn(union_of(TSStr, TInt),
                      union_of(struct_values(*arr.m_data.astruct), val)),
             TInt };

  case DataTag::ArrMapN:
    return { arr_mapn(union_of(arr.m_data.amapn->key, TInt),
                      union_of(arr.m_data.amapn->val, TInitNull)),
             TInt };
  }

  not_reached();
}

std::pair<Type,Type> array_newelem_key(const Type& arr, const Type& val) {
  assert(arr.subtypeOf(TArr));

  // Unless you know an array can't cow, you don't know if the TRef
  // will stay a TRef or turn back into a TInitCell.  Generally you
  // want a TInitGen.
  always_assert(!val.subtypeOf(TRef) &&
         "You probably don't want to put Ref types into arrays ...");

  // Inserting in an empty array creates a packed array of size one.
  auto emptyPart = arr.couldBe(TArrE)
    ? std::make_pair(arr_packed({val}), ival(0))
    : std::make_pair(TBottom, TBottom);

  auto nonEmptyPart = arr.couldBe(TArrN)
    ? arrayN_newelem_key(arr, val)
    : std::make_pair(TBottom, TBottom);

  return {
    union_of(std::move(emptyPart.first), std::move(nonEmptyPart.first)),
    union_of(std::move(emptyPart.second), std::move(nonEmptyPart.second))
  };
}

Type array_newelem(const Type& arr, const Type& val) {
  return array_newelem_key(arr, val).first;
}

std::pair<Type,Type> iter_types(const Type& iterable) {
  if (!iterable.subtypeOf(TArr) || !is_specialized_array(iterable)) {
    return { TInitCell, TInitCell };
  }

  // Note: we don't need to handle possible emptiness explicitly,
  // because if the array was empty we won't ever pull anything out
  // while iterating.

  switch (iterable.m_dataTag) {
  case DataTag::None:
    if (iterable.subtypeOf(TSArr)) {
      return { TInitUnc, TInitUnc };
    }
    return { TInitCell, TInitCell };
  case DataTag::Str:
  case DataTag::Obj:
  case DataTag::Int:
  case DataTag::Dbl:
  case DataTag::Cls:
  case DataTag::RefInner:
    always_assert(0);
  case DataTag::ArrVal:
    {
      auto const mn = toDArrMapN(iterable.m_data.aval);
      return { mn.key, mn.val };
    }
  case DataTag::ArrPacked:
    return { TInt, packed_values(*iterable.m_data.apacked) };
  case DataTag::ArrPackedN:
    return { TInt, iterable.m_data.apackedn->type };
  case DataTag::ArrStruct:
    return { TSStr, struct_values(*iterable.m_data.astruct) };
  case DataTag::ArrMapN:
    return { iterable.m_data.amapn->key, iterable.m_data.amapn->val };
  }

  not_reached();
}

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

RepoAuthType make_repo_type_arr(ArrayTypeTable::Builder& arrTable,
                                const Type& t) {
  auto const emptiness  = TArrE.couldBe(t) ? RepoAuthType::Array::Empty::Maybe
                                           : RepoAuthType::Array::Empty::No;

  auto const arr = [&]() -> const RepoAuthType::Array* {
    switch (t.m_dataTag) {
    case DataTag::None:
    case DataTag::Str:
    case DataTag::Obj:
    case DataTag::Int:
    case DataTag::Dbl:
    case DataTag::Cls:
    case DataTag::RefInner:
    case DataTag::ArrVal:
    case DataTag::ArrStruct:
    case DataTag::ArrMapN:
      return nullptr;
    case DataTag::ArrPackedN:
      // TODO(#4205897): we need to use this before it's worth putting
      // in the repo.
      if (false) {
        return arrTable.packedn(
          emptiness,
          make_repo_type(arrTable, t.m_data.apackedn->type)
        );
      }
      return nullptr;
    case DataTag::ArrPacked:
      {
        std::vector<RepoAuthType> repoTypes;
        std::transform(
          begin(t.m_data.apacked->elems), end(t.m_data.apacked->elems),
          std::back_inserter(repoTypes),
          [&] (const Type& t) { return make_repo_type(arrTable, t); }
        );
        return arrTable.packed(emptiness, repoTypes);
      }
      return nullptr;
    }
    not_reached();
  }();

  auto const tag = [&]() -> RepoAuthType::Tag {
    if (t.subtypeOf(TSArr))    return RepoAuthType::Tag::SArr;
    if (t.subtypeOf(TArr))     return RepoAuthType::Tag::Arr;
    if (t.subtypeOf(TOptSArr)) return RepoAuthType::Tag::OptSArr;
    if (t.subtypeOf(TOptArr))  return RepoAuthType::Tag::OptArr;
    not_reached();
  }();

  return RepoAuthType { tag, arr };
}

RepoAuthType make_repo_type(ArrayTypeTable::Builder& arrTable, const Type& t) {
  assert(!t.couldBe(TCls));
  assert(!t.subtypeOf(TBottom));
  using T = RepoAuthType::Tag;

  if (t.strictSubtypeOf(TObj) || (is_opt(t) && t.strictSubtypeOf(TOptObj))) {
    auto const dobj = dobj_of(t);
    auto const tag =
      is_opt(t)
        ? (dobj.type == DObj::Exact ? T::OptExactObj : T::OptSubObj)
        : (dobj.type == DObj::Exact ? T::ExactObj    : T::SubObj);
    return RepoAuthType { tag, dobj.cls.name() };
  }

  if (t.strictSubtypeOf(TArr) ||
      // TODO(#4205897): optional array types.
      (false && is_opt(t) && t.strictSubtypeOf(TOptArr))) {
    return make_repo_type_arr(arrTable, t);
  }

#define X(x) if (t.subtypeOf(T##x)) return RepoAuthType{T::x};
  X(Uninit)
  X(InitNull)
  X(Null)
  X(Int)
  X(OptInt)
  X(Dbl)
  X(OptDbl)
  X(Res)
  X(OptRes)
  X(Bool)
  X(OptBool)
  X(SStr)
  X(OptSStr)
  X(Str)
  X(OptStr)
  X(SArr)
  X(OptSArr)
  X(Arr)
  X(OptArr)
  X(Obj)
  X(OptObj)
  X(InitUnc)
  X(Unc)
  X(InitCell)
  X(Cell)
  X(Ref)
  X(InitGen)
  X(Gen)
#undef X
  not_reached();
}

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

}}