std::string opt_type_info(const StringData *userType,
                          const TypeConstraint &tc) {
  if (userType || tc.typeName() || tc.flags()) {
    std::string utype = userType ? escaped(userType) : "N";
    return folly::format("<{} {}> ",
                         utype,
                         type_constraint(tc)).str();
  }
  return "";
}

bool TypeConstraint::compat(const TypeConstraint& other) const {
  if (other.isExtended() || isExtended()) {
    /*
     * Rely on the ahead of time typechecker---checking here can
     * make it harder to convert a base class or interface to <?hh,
     * because derived classes that are still <?php would all need
     * to be modified.
     */
    return true;
  }

  if (m_typeName == other.m_typeName) {
    return true;
  }

  if (m_typeName && other.m_typeName) {
    if (m_typeName->isame(other.m_typeName)) {
      return true;
    }

    const Class* cls = Unit::lookupClass(m_typeName);
    const Class* otherCls = Unit::lookupClass(other.m_typeName);

    return cls && otherCls && cls == otherCls;
  }

  return false;
}

/*
 * relaxConstraint returns the least specific TypeConstraint 'tc' that doesn't
 * prevent the intersection of knownType and relaxType(toRelax, tc) from
 * satisfying origTc. It is used in IRBuilder::constrainValue and
 * IRBuilder::constrainStack to determine how to constrain the typeParam and
 * src values of CheckType/CheckStk instructions, and the src values of
 * AssertType/AssertStk instructions.
 *
 * AssertType example:
 * t24:Obj<C> = AssertType<{Obj<C>|InitNull}> t4:Obj
 *
 * If constrainValue is called with (t24, DataTypeSpecialized), relaxConstraint
 * will be called with (DataTypeSpecialized, Obj<C>|InitNull, Obj). After a few
 * iterations it will determine that constraining Obj with DataTypeCountness
 * will still allow the result type of the AssertType instruction to satisfy
 * DataTypeSpecialized, because relaxType(Obj, DataTypeCountness) == Obj.
 */
TypeConstraint relaxConstraint(const TypeConstraint origTc,
                               const Type knownType, const Type toRelax) {
  ITRACE(4, "relaxConstraint({}, knownType = {}, toRelax = {})\n",
         origTc, knownType, toRelax);
  Trace::Indent _i;

  auto const dstType = refineType(knownType, toRelax);
  always_assert_flog(typeFitsConstraint(dstType, origTc),
                     "refine({}, {}) doesn't fit {}",
                     knownType, toRelax, origTc);

  // Preserve origTc's weak property.
  TypeConstraint newTc{DataTypeGeneric, DataTypeGeneric};
  newTc.weak = origTc.weak;

  while (true) {
    if (newTc.isSpecialized()) {
      // We need to ask for the right kind of specialization, so grab it from
      // origTc.
      if (origTc.wantArrayKind()) newTc.setWantArrayKind();
      if (origTc.wantClass()) newTc.setDesiredClass(origTc.desiredClass());
    }

    auto const relaxed = relaxType(toRelax, newTc);
    auto const newDstType = refineType(relaxed, knownType);
    if (typeFitsConstraint(newDstType, origTc)) break;

    ITRACE(5, "newDstType = {}, newTc = {}; ", newDstType, newTc);
    if (newTc.category == DataTypeGeneric ||
        !typeFitsOuterConstraint(newDstType, origTc)) {
      FTRACE(5, "incrementing outer\n");
      incCategory(newTc.category);
    } else if (!typeFitsInnerConstraint(newDstType, origTc)) {
      FTRACE(5, "incrementing inner\n");
      incCategory(newTc.innerCat);
    } else {
      not_reached();
    }
  }

  ITRACE(4, "Returning {}\n", newTc);
  // newTc shouldn't be any more specific than origTc.
  always_assert(newTc.category <= origTc.category &&
                newTc.innerCat <= origTc.innerCat);
  return newTc;
}

bool typeFitsConstraint(Type t, TypeConstraint tc) {
  switch (tc.category) {
    case DataTypeGeneric:
      return true;

    case DataTypeCountness:
      // Consumers using this constraint expect the type to be relaxed to
      // Uncounted or left alone, so something like Arr|Obj isn't specific
      // enough.
      return !t.maybe(TCounted) ||
             t.subtypeOfAny(TStr, TArr, TObj,
                            TRes, TBoxedCell);

    case DataTypeCountnessInit:
      return typeFitsConstraint(t, DataTypeCountness) &&
             (t <= TUninit || !t.maybe(TUninit));

    case DataTypeSpecific:
      return t.isKnownDataType();

    case DataTypeSpecialized:
      // Type::isSpecialized() returns true for types like {Arr<Packed>|Int}
      // and Arr has non-specialized subtypes, so we require that t is
      // specialized, a strict subtype of Obj or Arr, and that it fits the
      // specific requirements of tc.

      assertx(tc.wantClass() ^ tc.wantArrayKind());

      if (t < TObj && t.clsSpec()) {
        return tc.wantClass() &&
               t.clsSpec().cls()->classof(tc.desiredClass());
      }
      if (t < TArr && t.arrSpec()) {
        auto arrSpec = t.arrSpec();
        if (tc.wantArrayKind() && !arrSpec.kind()) return false;
        return true;
      }

      return false;
  }

  not_reached();
}

bool typeFitsConstraint(Type t, TypeConstraint tc) {
  always_assert(t != Type::Bottom);

  switch (tc.category) {
    case DataTypeGeneric:
      return true;

    case DataTypeCountness:
      // Consumers using this constraint expect the type to be relaxed to
      // Uncounted or left alone, so something like Arr|Obj isn't specific
      // enough.
      return t.notCounted() ||
             t.subtypeOfAny(Type::Str, Type::Arr, Type::Obj,
                            Type::Res, Type::BoxedCell);

    case DataTypeCountnessInit:
      return typeFitsConstraint(t, DataTypeCountness) &&
             (t <= Type::Uninit || t.not(Type::Uninit));

    case DataTypeSpecific:
      return t.isKnownDataType();

    case DataTypeSpecialized:
      // Type::isSpecialized() returns true for types like {Arr<Packed>|Int}
      // and Arr has non-specialized subtypes, so we require that t is
      // specialized, a strict subtype of Obj or Arr, and that it fits the
      // specific requirements of tc.

      assert(tc.wantClass() ^ tc.wantArrayKind());
      if (!t.isSpecialized()) return false;
      if (t < Type::Obj) {
        return tc.wantClass() && t.getClass()->classof(tc.desiredClass());
      }
      if (t < Type::Arr) {
        return tc.wantArrayKind() && t.hasArrayKind();
      }
      return false;
  }

  not_reached();
}

TypeConstraint applyConstraint(TypeConstraint tc, const TypeConstraint newTc) {
  tc.category = std::max(newTc.category, tc.category);

  if (newTc.wantArrayKind()) tc.setWantArrayKind();

  if (newTc.wantClass()) {
    if (tc.wantClass()) {
      // It only makes sense to constrain tc with a class that's related to its
      // existing class, and we want to preserve the more derived of the two.
      auto cls1 = tc.desiredClass();
      auto cls2 = newTc.desiredClass();
      tc.setDesiredClass(cls1->classof(cls2) ? cls1 : cls2);
    } else {
      tc.setDesiredClass(newTc.desiredClass());
    }
  }

  return tc;
}

/*
 * Returns the least specific supertype of t that maintains the properties
 * required by tc.
 */
Type relaxType(Type t, TypeConstraint tc) {
  always_assert(t <= Type::Gen && t != Type::Bottom);
  if (tc.category == DataTypeGeneric) return Type::Gen;

  auto outerRelaxed = relaxOuter(t & Type::Cell, tc);
  if (t.notBoxed()) return outerRelaxed;

  auto innerType = (t & Type::BoxedCell).innerType();
  auto innerRelaxed = tc.innerCat == DataTypeGeneric ? Type::Cell
                                                     : relaxOuter(innerType,
                                                                  tc.inner());

  // Only add outerRelax into the result type if t had a meaningful outer type
  // coming in.
  return (t.isBoxed() ? Type::Bottom : outerRelaxed) |
    (innerRelaxed - Type::Uninit).box();
}

/*
 * Returns true iff t is not boxed, or if tc.innerCat is satisfied by t's inner
 * type.
 */
static bool typeFitsInnerConstraint(Type t, TypeConstraint tc) {
  return tc.innerCat == DataTypeGeneric || t.notBoxed() ||
    typeFitsOuterConstraint((t & Type::BoxedCell).innerType(), tc.inner());
}

std::string type_constraint(const TypeConstraint &tc) {
  std::string typeName = tc.typeName() ? escaped(tc.typeName()) : "N";
  return folly::format("{} {} ",
                       typeName,
                       type_flags_to_string(tc.flags())).str();
}