CSBindings.cpp

//===--- CSBindings.cpp - Constraint Solver -------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file implements selection of bindings for type variables.
//
//===----------------------------------------------------------------------===//
#include "swift/Sema/CSBindings.h"
#include "TypeChecker.h"
#include "swift/Sema/ConstraintGraph.h"
#include "swift/Sema/ConstraintSystem.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Support/raw_ostream.h"
#include <tuple>

using namespace swift;
using namespace constraints;
using namespace inference;

bool BindingSet::canBeNil() const {
  auto &ctx = CS.getASTContext();
  return Literals.count(
      ctx.getProtocol(KnownProtocolKind::ExpressibleByNilLiteral));
}

bool BindingSet::isDirectHole() const {
  // Direct holes are only allowed in "diagnostic mode".
  if (!CS.shouldAttemptFixes())
    return false;

  return Bindings.empty() && getNumViableLiteralBindings() == 0 &&
         Defaults.empty() && Info.TypeVar->getImpl().canBindToHole();
}

bool PotentialBindings::isGenericParameter() const {
  auto *locator = TypeVar->getImpl().getLocator();
  return locator && locator->isLastElement<LocatorPathElt::GenericParameter>();
}

bool PotentialBinding::isViableForJoin() const {
  return Kind == AllowedBindingKind::Supertypes &&
         !BindingType->hasLValueType() &&
         !BindingType->hasUnresolvedType() &&
         !BindingType->hasTypeVariable() &&
         !BindingType->hasPlaceholder() &&
         !BindingType->hasUnboundGenericType() &&
         !hasDefaultedLiteralProtocol() &&
         !isDefaultableBinding();
}

bool BindingSet::isDelayed() const {
  if (auto *locator = TypeVar->getImpl().getLocator()) {
    if (locator->isLastElement<LocatorPathElt::MemberRefBase>()) {
      // If first binding is a "fallback" to a protocol type,
      // it means that this type variable should be delayed
      // until it either gains more contextual information, or
      // there are no other type variables to attempt to make
      // forward progress.
      if (Bindings.empty())
        return true;


      if (Bindings[0].BindingType->is<ProtocolType>())
        return true;
    }

    // Since force unwrap preserves l-valueness, resulting
    // type variable has to be delayed until either l-value
    // binding becomes available or there are no other
    // variables to attempt.
    if (locator->directlyAt<ForceValueExpr>() &&
        TypeVar->getImpl().canBindToLValue()) {
      return llvm::none_of(Bindings, [](const PotentialBinding &binding) {
        return binding.BindingType->is<LValueType>();
      });
    }
  }

  if (isHole()) {
    auto *locator = TypeVar->getImpl().getLocator();
    assert(locator && "a hole without locator?");

    // Delay resolution of the code completion expression until
    // the very end to give it a chance to be bound to some
    // contextual type even if it's a hole.
    if (locator->directlyAt<CodeCompletionExpr>())
      return true;

    // Delay resolution of the `nil` literal to a hole until
    // the very end to give it a change to be bound to some
    // other type, just like code completion expression which
    // relies solely on contextual information.
    if (locator->directlyAt<NilLiteralExpr>())
      return true;

    // It's possible that type of member couldn't be determined,
    // and if so it would be beneficial to bind member to a hole
    // early to propagate that information down to arguments,
    // result type of a call that references such a member.
    //
    // Note: This is done here instead of during binding inference,
    // because it's possible that variable is marked as a "hole"
    // (or that status is propagated to it) after constraints
    // mentioned below are recorded.
    return llvm::any_of(Info.DelayedBy, [&](Constraint *constraint) {
      switch (constraint->getKind()) {
      case ConstraintKind::ApplicableFunction:
      case ConstraintKind::DynamicCallableApplicableFunction:
      case ConstraintKind::BindOverload: {
        return !ConstraintSystem::typeVarOccursInType(
            TypeVar, CS.simplifyType(constraint->getSecondType()));
      }

      default:
        return true;
      }
    });
  }

  return !Info.DelayedBy.empty();
}

bool BindingSet::involvesTypeVariables() const {
  // This is effectively O(1) right now since bindings are re-computed
  // on each step of the solver, but once bindings are computed
  // incrementally it becomes more important to double-check that
  // any adjacent type variables found previously are still unresolved.
  return llvm::any_of(AdjacentVars, [](TypeVariableType *typeVar) {
    return !typeVar->getImpl().getFixedType(/*record=*/nullptr);
  });
}

bool BindingSet::isPotentiallyIncomplete() const {
  // Generic parameters are always potentially incomplete.
  if (Info.isGenericParameter())
    return true;

  // If current type variable is associated with a code completion token
  // it's possible that it doesn't have enough contextual information
  // to be resolved to anything so let's delay considering it until everything
  // else is resolved.
  if (Info.AssociatedCodeCompletionToken)
    return true;

  auto *locator = TypeVar->getImpl().getLocator();
  if (!locator)
    return false;

  if (locator->isLastElement<LocatorPathElt::MemberRefBase>() &&
      !Bindings.empty()) {
    // If the base of the unresolved member reference like `.foo`
    // couldn't be resolved we'd want to bind it to a hole at the
    // very last moment possible, just like generic parameters.
    if (isHole())
      return true;

    auto &binding = Bindings.front();
    // If base type of a member chain is inferred to be a protocol type,
    // let's consider this binding set to be potentially incomplete since
    // that's done as a last resort effort at resolving first member.
    if (auto *constraint = binding.getSource()) {
      if (binding.BindingType->is<ProtocolType>() &&
          constraint->getKind() == ConstraintKind::ConformsTo)
        return true;
    }
  }

  if (locator->isLastElement<LocatorPathElt::UnresolvedMemberChainResult>()) {
    // If subtyping is allowed and this is a result of an implicit member chain,
    // let's delay binding it to an optional until its object type resolved too or
    // it has been determined that there is no possibility to resolve it. Otherwise
    // we might end up missing solutions since it's allowed to implicitly unwrap
    // base type of the chain but it can't be done early - type variable
    // representing chain's result type has a different l-valueness comparing
    // to generic parameter of the optional.
    if (llvm::any_of(Bindings, [&](const PotentialBinding &binding) {
          if (binding.Kind != AllowedBindingKind::Subtypes)
            return false;

          auto objectType = binding.BindingType->getOptionalObjectType();
          return objectType && objectType->isTypeVariableOrMember();
        }))
      return true;
  }

  if (isHole()) {
    // Delay resolution of the code completion expression until
    // the very end to give it a chance to be bound to some
    // contextual type even if it's a hole.
    if (locator->directlyAt<CodeCompletionExpr>())
      return true;

    // Delay resolution of the `nil` literal to a hole until
    // the very end to give it a change to be bound to some
    // other type, just like code completion expression which
    // relies solely on contextual information.
    if (locator->directlyAt<NilLiteralExpr>())
      return true;
  }

  // If there is a `bind param` constraint associated with
  // current type variable, result should be aware of that
  // fact. Binding set might be incomplete until
  // this constraint is resolved, because we currently don't
  // look-through constraints expect to `subtype` to try and
  // find related bindings.
  // This only affects type variable that appears one the
  // right-hand side of the `bind param` constraint and
  // represents result type of the closure body, because
  // left-hand side gets types from overload choices.
  if (llvm::any_of(
          Info.EquivalentTo,
          [&](const std::pair<TypeVariableType *, Constraint *> &equivalence) {
            auto *constraint = equivalence.second;
            return constraint->getKind() == ConstraintKind::BindParam &&
                   constraint->getSecondType()->isEqual(TypeVar);
          }))
    return true;

  return false;
}

void BindingSet::inferTransitiveProtocolRequirements(
    llvm::SmallDenseMap<TypeVariableType *, BindingSet> &inferredBindings) {
  if (TransitiveProtocols)
    return;

  llvm::SmallVector<std::pair<TypeVariableType *, TypeVariableType *>, 4>
      workList;
  llvm::SmallPtrSet<TypeVariableType *, 4> visitedRelations;

  llvm::SmallDenseMap<TypeVariableType *, SmallPtrSet<Constraint *, 4>, 4>
      protocols;

  auto addToWorkList = [&](TypeVariableType *parent,
                           TypeVariableType *typeVar) {
    if (visitedRelations.insert(typeVar).second)
      workList.push_back({parent, typeVar});
  };

  auto propagateProtocolsTo =
      [&protocols](TypeVariableType *dstVar,
                   const ArrayRef<Constraint *> &direct,
                   const SmallPtrSetImpl<Constraint *> &transitive) {
        auto &destination = protocols[dstVar];

        if (direct.size() > 0)
          destination.insert(direct.begin(), direct.end());

        if (transitive.size() > 0)
          destination.insert(transitive.begin(), transitive.end());
      };

  addToWorkList(nullptr, TypeVar);

  do {
    auto *currentVar = workList.back().second;

    auto cachedBindings = inferredBindings.find(currentVar);
    if (cachedBindings == inferredBindings.end()) {
      workList.pop_back();
      continue;
    }

    auto &bindings = cachedBindings->getSecond();

    // If current variable already has transitive protocol
    // conformances inferred, there is no need to look deeper
    // into subtype/equivalence chain.
    if (bindings.TransitiveProtocols) {
      TypeVariableType *parent = nullptr;
      std::tie(parent, currentVar) = workList.pop_back_val();
      assert(parent);
      propagateProtocolsTo(parent, bindings.getConformanceRequirements(),
                           *bindings.TransitiveProtocols);
      continue;
    }

    for (const auto &entry : bindings.Info.SubtypeOf)
      addToWorkList(currentVar, entry.first);

    // If current type variable is part of an equivalence
    // class, make it a "representative" and let it infer
    // supertypes and direct protocol requirements from
    // other members.
    for (const auto &entry : bindings.Info.EquivalentTo) {
      auto eqBindings = inferredBindings.find(entry.first);
      if (eqBindings != inferredBindings.end()) {
        const auto &bindings = eqBindings->getSecond();

        llvm::SmallPtrSet<Constraint *, 2> placeholder;
        // Add any direct protocols from members of the
        // equivalence class, so they could be propagated
        // to all of the members.
        propagateProtocolsTo(currentVar, bindings.getConformanceRequirements(),
                             placeholder);

        // Since type variables are equal, current type variable
        // becomes a subtype to any supertype found in the current
        // equivalence  class.
        for (const auto &eqEntry : bindings.Info.SubtypeOf)
          addToWorkList(currentVar, eqEntry.first);
      }
    }

    // More subtype/equivalences relations have been added.
    if (workList.back().second != currentVar)
      continue;

    TypeVariableType *parent = nullptr;
    std::tie(parent, currentVar) = workList.pop_back_val();

    // At all of the protocols associated with current type variable
    // are transitive to its parent, propogate them down the subtype/equivalence
    // chain.
    if (parent) {
      propagateProtocolsTo(parent, bindings.getConformanceRequirements(),
                           protocols[currentVar]);
    }

    auto &inferredProtocols = protocols[currentVar];

    llvm::SmallPtrSet<Constraint *, 4> protocolsForEquivalence;

    // Equivalence class should contain both:
    // - direct protocol requirements of the current type
    //   variable;
    // - all of the transitive protocols inferred through
    //   the members of the equivalence class.
    {
      auto directRequirements = bindings.getConformanceRequirements();
      protocolsForEquivalence.insert(directRequirements.begin(),
                                     directRequirements.end());

      protocolsForEquivalence.insert(inferredProtocols.begin(),
                                     inferredProtocols.end());
    }

    // Propogate inferred protocols to all of the members of the
    // equivalence class.
    for (const auto &equivalence : bindings.Info.EquivalentTo) {
      auto eqBindings = inferredBindings.find(equivalence.first);
      if (eqBindings != inferredBindings.end()) {
        auto &bindings = eqBindings->getSecond();
        bindings.TransitiveProtocols.emplace(protocolsForEquivalence.begin(),
                                             protocolsForEquivalence.end());
      }
    }

    // Update the bindings associated with current type variable,
    // to avoid repeating this inference process.
    bindings.TransitiveProtocols.emplace(inferredProtocols.begin(),
                                         inferredProtocols.end());
  } while (!workList.empty());
}

void BindingSet::inferTransitiveBindings(
    const llvm::SmallDenseMap<TypeVariableType *, BindingSet>
        &inferredBindings) {
  using BindingKind = AllowedBindingKind;

  for (const auto &entry : Info.SupertypeOf) {
    auto relatedBindings = inferredBindings.find(entry.first);
    if (relatedBindings == inferredBindings.end())
      continue;

    auto &bindings = relatedBindings->getSecond();

    // FIXME: This is a workaround necessary because solver doesn't filter
    // bindings based on protocol requirements placed on a type variable.
    //
    // Forward propagate (subtype -> supertype) only literal conformance
    // requirements since that helps solver to infer more types at
    // parameter positions.
    //
    // \code
    // func foo<T: ExpressibleByStringLiteral>(_: String, _: T) -> T {
    //   fatalError()
    // }
    //
    // func bar(_: Any?) {}
    //
    // func test() {
    //   bar(foo("", ""))
    // }
    // \endcode
    //
    // If one of the literal arguments doesn't propagate its
    // `ExpressibleByStringLiteral` conformance, we'd end up picking
    // `T` with only one type `Any?` which is incorrect.
    for (const auto &literal : bindings.Literals)
      addLiteralRequirement(literal.second.getSource());

    // Infer transitive defaults.
    for (const auto &def : bindings.Defaults) {
      if (def.getSecond()->getKind() == ConstraintKind::DefaultClosureType)
        continue;

      addDefault(def.second);
    }

    // TODO: We shouldn't need this in the future.
    if (entry.second->getKind() != ConstraintKind::Subtype)
      continue;

    for (auto &binding : bindings.Bindings) {
      // We need the binding kind for the potential binding to
      // either be Exact or Supertypes in order for it to make sense
      // to add Supertype bindings based on the relationship between
      // our type variables.
      if (binding.Kind != BindingKind::Exact &&
          binding.Kind != BindingKind::Supertypes)
        continue;

      auto type = binding.BindingType;

      if (type->isPlaceholder())
        continue;

      if (ConstraintSystem::typeVarOccursInType(TypeVar, type))
        continue;

      addBinding(binding.withSameSource(type, BindingKind::Supertypes));
    }
  }
}

void BindingSet::finalize(
    llvm::SmallDenseMap<TypeVariableType *, BindingSet> &inferredBindings) {
  inferTransitiveProtocolRequirements(inferredBindings);
  inferTransitiveBindings(inferredBindings);

  determineLiteralCoverage();

  if (auto *locator = TypeVar->getImpl().getLocator()) {
    if (locator->isLastElement<LocatorPathElt::MemberRefBase>()) {
      // If this is a base of an unresolved member chain, as a last
      // resort effort let's infer base to be a protocol type based
      // on contextual conformance requirements.
      //
      // This allows us to find solutions in cases like this:
      //
      // \code
      // func foo<T: P>(_: T) {}
      // foo(.bar) <- `.bar` should be a static member of `P`.
      // \endcode
      if (!hasViableBindings() && TransitiveProtocols.hasValue()) {
        for (auto *constraint : *TransitiveProtocols) {
          auto protocolTy = constraint->getSecondType();
          addBinding(
              {protocolTy, AllowedBindingKind::Exact, constraint});
        }
      }
    }

    if (CS.shouldAttemptFixes() &&
        locator->isLastElement<LocatorPathElt::UnresolvedMemberChainResult>()) {
      // Let's see whether this chain is valid, if it isn't then to avoid
      // diagnosing the same issue multiple different ways, let's infer
      // result of the chain to be a hole.
      auto *resultExpr =
          castToExpr<UnresolvedMemberChainResultExpr>(locator->getAnchor());
      auto *baseLocator = CS.getConstraintLocator(
          resultExpr->getChainBase(), ConstraintLocator::UnresolvedMember);

      if (CS.hasFixFor(
              baseLocator,
              FixKind::AllowInvalidStaticMemberRefOnProtocolMetatype)) {
        CS.recordPotentialHole(TypeVar);
        // Clear all of the previously collected bindings which are inferred
        // from inside of a member chain.
        Bindings.remove_if([](const PotentialBinding &binding) {
          return binding.Kind == AllowedBindingKind::Supertypes;
        });
      }
    }
  }
}

void BindingSet::addBinding(PotentialBinding binding) {
  if (Bindings.count(binding))
    return;

  if (!isViable(binding))
    return;

  SmallPtrSet<TypeVariableType *, 4> referencedTypeVars;
  binding.BindingType->getTypeVariables(referencedTypeVars);

  // If type variable is not allowed to bind to `lvalue`,
  // let's check if type of potential binding has any
  // type variables, which are allowed to bind to `lvalue`,
  // and postpone such type from consideration.
  //
  // This check is done here and not in `checkTypeOfBinding`
  // because the l-valueness of the variable might change during
  // solving and that would not be reflected in the graph.
  if (!TypeVar->getImpl().canBindToLValue()) {
    for (auto *typeVar : referencedTypeVars) {
      if (typeVar->getImpl().canBindToLValue())
        return;
    }
  }

  // If this is a non-defaulted supertype binding,
  // check whether we can combine it with another
  // supertype binding by computing the 'join' of the types.
  if (binding.isViableForJoin()) {
    auto isAcceptableJoin = [](Type type) {
      return !type->isAny() && (!type->getOptionalObjectType() ||
                                !type->getOptionalObjectType()->isAny());
    };

    SmallVector<PotentialBinding, 4> joined;
    for (auto existingBinding = Bindings.begin();
         existingBinding != Bindings.end();) {
      if (existingBinding->isViableForJoin()) {
        auto join =
            Type::join(existingBinding->BindingType, binding.BindingType);

        if (join && isAcceptableJoin(*join)) {
          // Result of the join has to use new binding because it refers
          // to the constraint that triggered the join that replaced the
          // existing binding.
          joined.push_back(binding.withType(*join));
          // Remove existing binding from the set.
          // It has to be re-introduced later, since its type has been changed.
          existingBinding = Bindings.erase(existingBinding);
          continue;
        }
      }

      ++existingBinding;
    }

    for (const auto &binding : joined)
      (void)Bindings.insert(binding);

    // If new binding has been joined with at least one of existing
    // bindings, there is no reason to include it into the set.
    if (!joined.empty())
      return;
  }

  for (auto *adjacentVar : referencedTypeVars)
    AdjacentVars.insert(adjacentVar);

  (void)Bindings.insert(std::move(binding));
}

void BindingSet::determineLiteralCoverage() {
  if (Literals.empty())
    return;

  SmallVector<PotentialBinding, 4> adjustedBindings;

  bool allowsNil = canBeNil();

  for (auto &entry : Literals) {
    auto &literal = entry.second;

    if (!literal.viableAsBinding())
      continue;

    for (auto binding = Bindings.begin(); binding != Bindings.end();
         ++binding) {

      bool isCovered = false;
      Type adjustedTy;

      std::tie(isCovered, adjustedTy) =
          literal.isCoveredBy(*binding, allowsNil, CS.DC);

      if (!isCovered)
        continue;

      literal.setCoveredBy(binding->getSource());

      if (adjustedTy) {
        Bindings.erase(binding);
        Bindings.insert(binding->withType(adjustedTy));
      }

      break;
    }
  }
}

void BindingSet::addLiteralRequirement(Constraint *constraint) {
  auto isDirectRequirement = [&](Constraint *constraint) -> bool {
    if (auto *typeVar = constraint->getFirstType()->getAs<TypeVariableType>()) {
      auto *repr = CS.getRepresentative(typeVar);
      return repr == TypeVar;
    }

    return false;
  };

  auto *protocol = constraint->getProtocol();

  // Let's try to coalesce integer and floating point literal protocols
  // if they appear together because the only possible default type that
  // could satisfy both requirements is `Double`.
  {
    if (protocol->isSpecificProtocol(
            KnownProtocolKind::ExpressibleByIntegerLiteral)) {
      auto *floatLiteral = CS.getASTContext().getProtocol(
          KnownProtocolKind::ExpressibleByFloatLiteral);
      if (Literals.count(floatLiteral))
        return;
    }

    if (protocol->isSpecificProtocol(
            KnownProtocolKind::ExpressibleByFloatLiteral)) {
      auto *intLiteral = CS.getASTContext().getProtocol(
          KnownProtocolKind::ExpressibleByIntegerLiteral);
      Literals.erase(intLiteral);
    }
  }

  if (Literals.count(protocol) > 0)
    return;

  bool isDirect = isDirectRequirement(constraint);

  // Coverage is not applicable to `ExpressibleByNilLiteral` since it
  // doesn't have a default type.
  if (protocol->isSpecificProtocol(
          KnownProtocolKind::ExpressibleByNilLiteral)) {
    Literals.insert(
        {protocol, LiteralRequirement(constraint,
                                      /*DefaultType=*/Type(), isDirect)});
    return;
  }

  // Check whether any of the existing bindings covers this literal
  // protocol.
  LiteralRequirement literal(
      constraint, TypeChecker::getDefaultType(protocol, CS.DC), isDirect);

  Literals.insert({protocol, std::move(literal)});
}

BindingSet::BindingScore BindingSet::formBindingScore(const BindingSet &b) {
  // If there are no bindings available but this type
  // variable represents a closure - let's consider it
  // as having a single non-default binding - that would
  // be a type inferred based on context.
  // It's considered to be non-default for purposes of
  // ranking because we'd like to prioritize resolving
  // closures to gain more information from their bodies.
  unsigned numBindings = b.Bindings.size() + b.getNumViableLiteralBindings();
  auto numNonDefaultableBindings = numBindings > 0 ? numBindings
                                   : b.TypeVar->getImpl().isClosureType() ? 1
                                                                          : 0;

  return std::make_tuple(b.isHole(), numNonDefaultableBindings == 0,
                         b.isDelayed(), b.isSubtypeOfExistentialType(),
                         b.involvesTypeVariables(),
                         static_cast<unsigned char>(b.getLiteralKind()),
                         -numNonDefaultableBindings);
}

Optional<BindingSet> ConstraintSystem::determineBestBindings() {
  // Look for potential type variable bindings.
  Optional<BindingSet> bestBindings;
  llvm::SmallDenseMap<TypeVariableType *, BindingSet> cache;

  // First, let's collect all of the possible bindings.
  for (auto *typeVar : getTypeVariables()) {
    if (!typeVar->getImpl().hasRepresentativeOrFixed()) {
      cache.insert({typeVar, getBindingsFor(typeVar, /*finalize=*/false)});
    }
  }

  // Determine whether given type variable with its set of bindings is
  // viable to be attempted on the next step of the solver. If type variable
  // has no "direct" bindings of any kind e.g. direct bindings to concrete
  // types, default types from "defaultable" constraints or literal
  // conformances, such type variable is not viable to be evaluated to be
  // attempted next.
  auto isViableForRanking = [this](const BindingSet &bindings) -> bool {
    auto *typeVar = bindings.getTypeVariable();

    // Type variable representing a base of unresolved member chain should
    // always be considered viable for ranking since it's allow to infer
    // types from transitive protocol requirements.
    if (auto *locator = typeVar->getImpl().getLocator()) {
      if (locator->isLastElement<LocatorPathElt::MemberRefBase>())
        return true;
    }

    // If type variable is marked as a potential hole there is always going
    // to be at least one binding available for it.
    if (shouldAttemptFixes() && typeVar->getImpl().canBindToHole())
      return true;

    return bool(bindings);
  };

  // Now let's see if we could infer something for related type
  // variables based on other bindings.
  for (auto *typeVar : getTypeVariables()) {
    auto cachedBindings = cache.find(typeVar);
    if (cachedBindings == cache.end())
      continue;

    auto &bindings = cachedBindings->getSecond();
    // Before attempting to infer transitive bindings let's check
    // whether there are any viable "direct" bindings associated with
    // current type variable, if there are none - it means that this type
    // variable could only be used to transitively infer bindings for
    // other type variables and can't participate in ranking.
    //
    // Viable bindings include - any types inferred from constraints
    // associated with given type variable, any default constraints,
    // or any conformance requirements to literal protocols with can
    // produce a default type.
    bool isViable = isViableForRanking(bindings);

    bindings.finalize(cache);

    if (!bindings || !isViable)
      continue;

    if (isDebugMode()) {
      bindings.dump(typeVar, llvm::errs(), solverState->depth * 2);
    }

    // If these are the first bindings, or they are better than what
    // we saw before, use them instead.
    if (!bestBindings || bindings < *bestBindings)
      bestBindings.emplace(bindings);
  }

  return bestBindings;
}

/// Find the set of type variables that are inferable from the given type.
///
/// \param type The type to search.
/// \param typeVars Collects the type variables that are inferable from the
/// given type. This set is not cleared, so that multiple types can be explored
/// and introduce their results into the same set.
static void
findInferableTypeVars(Type type,
                      SmallPtrSetImpl<TypeVariableType *> &typeVars) {
  type = type->getCanonicalType();
  if (!type->hasTypeVariable())
    return;

  class Walker : public TypeWalker {
    SmallPtrSetImpl<TypeVariableType *> &typeVars;

  public:
    explicit Walker(SmallPtrSetImpl<TypeVariableType *> &typeVars)
        : typeVars(typeVars) {}

    Action walkToTypePre(Type ty) override {
      if (ty->is<DependentMemberType>())
        return Action::SkipChildren;

      if (auto typeVar = ty->getAs<TypeVariableType>())
        typeVars.insert(typeVar);
      return Action::Continue;
    }
  };

  type.walk(Walker(typeVars));
}

void PotentialBindings::addDefault(Constraint *constraint) {
  Defaults.insert(constraint);
}

bool LiteralRequirement::isCoveredBy(Type type, DeclContext *useDC) const {
  auto coversDefaultType = [](Type type, Type defaultType) -> bool {
    if (!defaultType->hasUnboundGenericType())
      return type->isEqual(defaultType);

    // For generic literal types, check whether we already have a
    // specialization of this generic within our list.
    // FIXME: This assumes that, e.g., the default literal
    // int/float/char/string types are never generic.
    auto nominal = defaultType->getAnyNominal();
    if (!nominal)
      return false;

    // FIXME: Check parents?
    return nominal == type->getAnyNominal();
  };

  if (hasDefaultType() && coversDefaultType(type, getDefaultType()))
    return true;

  return bool(TypeChecker::conformsToProtocol(type, getProtocol(), useDC));
}

std::pair<bool, Type>
LiteralRequirement::isCoveredBy(const PotentialBinding &binding,
                                bool canBeNil,
                                DeclContext *useDC) const {
  auto type = binding.BindingType;
  switch (binding.Kind) {
  case AllowedBindingKind::Exact:
    type = binding.BindingType;
    break;

  case AllowedBindingKind::Subtypes:
  case AllowedBindingKind::Supertypes:
    type = binding.BindingType->getRValueType();
    break;
  }

  bool requiresUnwrap = false;
  do {
    // Conformance check on type variable would always return true,
    // but type variable can't cover anything until it's bound.
    if (type->isTypeVariableOrMember() || type->isPlaceholder())
      return std::make_pair(false, Type());

    if (isCoveredBy(type, useDC)) {
      return std::make_pair(true, requiresUnwrap ? type : binding.BindingType);
    }

    // Can't unwrap optionals if there is `ExpressibleByNilLiteral`
    // conformance requirement placed on the type variable.
    if (canBeNil)
      return std::make_pair(false, Type());

    // If this literal protocol is not a direct requirement it
    // would not be possible to change optionality while inferring
    // bindings for a supertype, so this hack doesn't apply.
    if (!isDirectRequirement())
      return std::make_pair(false, Type());

    // If we're allowed to bind to subtypes, look through optionals.
    // FIXME: This is really crappy special case of computing a reasonable
    // result based on the given constraints.
    if (binding.Kind == AllowedBindingKind::Subtypes) {
      if (auto objTy = type->getOptionalObjectType()) {
        requiresUnwrap = true;
        type = objTy;
        continue;
      }
    }

    return std::make_pair(false, Type());
  } while (true);
}

void PotentialBindings::addPotentialBinding(PotentialBinding binding) {
  assert(!binding.BindingType->is<ErrorType>());

  // If the type variable can't bind to an lvalue, make sure the
  // type we pick isn't an lvalue.
  if (!TypeVar->getImpl().canBindToLValue() &&
      binding.BindingType->hasLValueType()) {
    binding = binding.withType(binding.BindingType->getRValueType());
  }

  Bindings.push_back(std::move(binding));
}

void PotentialBindings::addLiteral(Constraint *constraint) {
  Literals.insert(constraint);
}

bool BindingSet::isViable(PotentialBinding &binding) {
  // Prevent against checking against the same opened nominal type
  // over and over again. Doing so means redundant work in the best
  // case. In the worst case, we'll produce lots of duplicate solutions
  // for this constraint system, which is problematic for overload
  // resolution.
  auto type = binding.BindingType;

  auto *NTD = type->getAnyNominal();
  if (!NTD)
    return true;

  for (auto existing = Bindings.begin(); existing != Bindings.end();
       ++existing) {
    auto existingType = existing->BindingType;

    auto *existingNTD = existingType->getAnyNominal();
    if (!existingNTD || NTD != existingNTD)
      continue;

    // If new type has a type variable it shouldn't
    // be considered  viable.
    if (type->hasTypeVariable())
      return false;

    // If new type doesn't have any type variables,
    // but existing binding does, let's replace existing
    // binding with new one.
    if (existingType->hasTypeVariable()) {
      // First, let's remove all of the adjacent type
      // variables associated with this binding.
      {
        SmallPtrSet<TypeVariableType *, 4> referencedVars;
        existingType->getTypeVariables(referencedVars);
        for (auto *var : referencedVars)
          AdjacentVars.erase(var);
      }

      // And now let's remove the binding itself.
      Bindings.erase(existing);
      break;
    }
  }

  return true;
}

bool BindingSet::favoredOverDisjunction(Constraint *disjunction) const {
  if (isHole() || isDelayed())
    return false;

  // If this bindings are for a closure and there are no holes,
  // it shouldn't matter whether it there are any type variables
  // or not because e.g. parameter type can have type variables,
  // but we still want to resolve closure body early (instead of
  // attempting any disjunction) to gain additional contextual
  // information.
  if (TypeVar->getImpl().isClosureType()) {
    auto boundType = disjunction->getNestedConstraints()[0]->getFirstType();
    // If disjunction is attempting to bind a type variable, let's
    // favor closure because it would add additional context, otherwise
    // if it's something like a collection (where it has to pick
    // between a conversion and bridging conversion) or concrete
    // type let's prefer the disjunction.
    //
    // We are looking through optionals here because it could be
    // a situation where disjunction is formed to match optionals
    // either as deep equality or optional-to-optional conversion.
    // Such type variables might be connected to closure as well
    // e.g. when result type is optional, so it makes sense to
    // open closure before attempting such disjunction.
    return boundType->lookThroughAllOptionalTypes()->is<TypeVariableType>();
  }

  return !involvesTypeVariables();
}

BindingSet ConstraintSystem::getBindingsFor(TypeVariableType *typeVar,
                                            bool finalize) {
  assert(typeVar->getImpl().getRepresentative(nullptr) == typeVar &&
         "not a representative");
  assert(!typeVar->getImpl().getFixedType(nullptr) && "has a fixed type");

  BindingSet bindings{CG[typeVar].getCurrentBindings()};

  if (finalize) {
    llvm::SmallDenseMap<TypeVariableType *, BindingSet> cache;
    bindings.finalize(cache);
  }

  return bindings;
}

/// Check whether the given type can be used as a binding for the given
/// type variable.
///
/// \returns the type to bind to, if the binding is okay.
static Optional<Type> checkTypeOfBinding(TypeVariableType *typeVar, Type type) {
  // If the type references the type variable, don't permit the binding.
  if (type->hasTypeVariable()) {
    SmallPtrSet<TypeVariableType *, 4> referencedTypeVars;
    type->getTypeVariables(referencedTypeVars);
    if (referencedTypeVars.count(typeVar))
      return None;
  }

  {
    auto objType = type->getWithoutSpecifierType();

    // If the type is a type variable itself, don't permit the binding.
    if (objType->is<TypeVariableType>())
      return None;

    // Don't bind to a dependent member type, even if it's currently
    // wrapped in any number of optionals, because binding producer
    // might unwrap and try to attempt it directly later.
    if (objType->lookThroughAllOptionalTypes()->is<DependentMemberType>())
      return None;
  }

  // Okay, allow the binding (with the simplified type).
  return type;
}

Optional<PotentialBinding>
PotentialBindings::inferFromRelational(Constraint *constraint) {
  assert(constraint->getClassification() ==
             ConstraintClassification::Relational &&
         "only relational constraints handled here");

  auto first = CS.simplifyType(constraint->getFirstType());
  auto second = CS.simplifyType(constraint->getSecondType());

  if (first->is<TypeVariableType>() && first->isEqual(second))
    return None;

  Type type;
  AllowedBindingKind kind;
  if (first->getAs<TypeVariableType>() == TypeVar) {
    // Upper bound for this type variable.
    type = second;
    kind = AllowedBindingKind::Subtypes;
  } else if (second->getAs<TypeVariableType>() == TypeVar) {
    // Lower bound for this type variable.
    type = first;
    kind = AllowedBindingKind::Supertypes;
  } else {
    // If the left-hand side of a relational constraint is a
    // type variable representing a closure type, let's delay
    // attempting any bindings related to any type variables
    // on the other side since it could only be either a closure
    // parameter or a result type, and we can't get a full set
    // of bindings for them until closure's body is opened.
    if (auto *typeVar = first->getAs<TypeVariableType>()) {
      if (typeVar->getImpl().isClosureType()) {
        DelayedBy.push_back(constraint);
        return None;
      }
    }

    // Check whether both this type and another type variable are
    // inferable.
    SmallPtrSet<TypeVariableType *, 4> typeVars;
    findInferableTypeVars(first, typeVars);
    findInferableTypeVars(second, typeVars);

    if (typeVars.erase(TypeVar)) {
      for (auto *typeVar : typeVars)
        AdjacentVars.insert({typeVar, constraint});
    }

    return None;
  }

  // Do not attempt to bind to ErrorType.
  if (type->hasError())
    return None;

  if (auto *locator = TypeVar->getImpl().getLocator()) {
    if (locator->isKeyPathType()) {
      auto *BGT =
          type->lookThroughAllOptionalTypes()->getAs<BoundGenericType>();
      if (!BGT || !isKnownKeyPathDecl(CS.getASTContext(), BGT->getDecl()))
        return None;
    }

    // Don't allow a protocol type to get propagated from the base to the result
    // type of a chain, Result should always be a concrete type which conforms
    // to the protocol inferred for the base.
    if (constraint->getKind() == ConstraintKind::UnresolvedMemberChainBase &&
        kind == AllowedBindingKind::Subtypes && type->is<ProtocolType>())
      return None;
  }

  // If the source of the binding is 'OptionalObject' constraint
  // and type variable is on the left-hand side, that means
  // that it _has_ to be of optional type, since the right-hand
  // side of the constraint is object type of the optional.
  if (constraint->getKind() == ConstraintKind::OptionalObject &&
      kind == AllowedBindingKind::Subtypes) {
    type = OptionalType::get(type);
  }

  // If the type we'd be binding to is a dependent member, don't try to
  // resolve this type variable yet.
  if (type->getWithoutSpecifierType()
          ->lookThroughAllOptionalTypes()
          ->is<DependentMemberType>()) {
    llvm::SmallPtrSet<TypeVariableType *, 4> referencedVars;
    type->getTypeVariables(referencedVars);

    bool containsSelf = false;
    for (auto *var : referencedVars) {
      // Add all type variables encountered in the type except
      // to the current type variable.
      if (var != TypeVar) {
        AdjacentVars.insert({var, constraint});
        continue;
      }

      containsSelf = true;
    }

    // If inferred type doesn't contain the current type variable,
    // let's mark bindings as delayed until dependent member type
    // is resolved.
    if (!containsSelf)
      DelayedBy.push_back(constraint);

    return None;
  }

  // If our binding choice is a function type and we're attempting
  // to bind to a type variable that is the result of opening a
  // generic parameter, strip the noescape bit so that we only allow
  // bindings of escaping functions in this position. We do this
  // because within the generic function we have no indication of
  // whether the parameter is a function type and if so whether it
  // should be allowed to escape. As a result we allow anything
  // passed in to escape.
  if (auto *fnTy = type->getAs<AnyFunctionType>()) {
    // Since inference now happens during constraint generation,
    // this hack should be allowed in both `Solving`
    // (during non-diagnostic mode) and `ConstraintGeneration` phases.
    if (isGenericParameter() &&
        (!CS.shouldAttemptFixes() ||
         CS.getPhase() == ConstraintSystemPhase::ConstraintGeneration)) {
      type = fnTy->withExtInfo(fnTy->getExtInfo().withNoEscape(false));
    }
  }

  // Check whether we can perform this binding.
  if (auto boundType = checkTypeOfBinding(TypeVar, type)) {
    type = *boundType;
  } else {
    auto *bindingTypeVar = type->getRValueType()->getAs<TypeVariableType>();

    if (!bindingTypeVar)
      return None;

    AdjacentVars.insert({bindingTypeVar, constraint});

    // If current type variable is associated with a code completion token
    // it's possible that it doesn't have enough contextual information
    // to be resolved to anything, so let's note that fact in the potential
    // bindings and use it when forming a hole if there are no other bindings
    // available.
    if (auto *locator = bindingTypeVar->getImpl().getLocator()) {
      if (locator->directlyAt<CodeCompletionExpr>())
        AssociatedCodeCompletionToken = locator->getAnchor();
    }

    switch (constraint->getKind()) {
    case ConstraintKind::Subtype:
    case ConstraintKind::Conversion:
    case ConstraintKind::ArgumentConversion:
    case ConstraintKind::OperatorArgumentConversion: {
      if (kind == AllowedBindingKind::Subtypes) {
        SubtypeOf.insert({bindingTypeVar, constraint});
      } else {
        assert(kind == AllowedBindingKind::Supertypes);
        SupertypeOf.insert({bindingTypeVar, constraint});
      }
      break;
    }

    case ConstraintKind::Bind:
    case ConstraintKind::BindParam:
    case ConstraintKind::Equal:
    case ConstraintKind::UnresolvedMemberChainBase: {
      EquivalentTo.insert({bindingTypeVar, constraint});
      break;
    }

    default:
      break;
    }

    return None;
  }

  // Make sure we aren't trying to equate type variables with different
  // lvalue-binding rules.
  if (auto otherTypeVar = type->getAs<TypeVariableType>()) {
    if (TypeVar->getImpl().canBindToLValue() !=
        otherTypeVar->getImpl().canBindToLValue())
      return None;
  }

  if (type->is<InOutType>() && !TypeVar->getImpl().canBindToInOut())
    type = LValueType::get(type->getInOutObjectType());
  if (type->is<LValueType>() && !TypeVar->getImpl().canBindToLValue())
    type = type->getRValueType();

  // BindParam constraints are not reflexive and must be treated specially.
  if (constraint->getKind() == ConstraintKind::BindParam) {
    if (kind == AllowedBindingKind::Subtypes) {
      if (auto *lvt = type->getAs<LValueType>()) {
        type = InOutType::get(lvt->getObjectType());
      }
    } else if (kind == AllowedBindingKind::Supertypes) {
      if (auto *iot = type->getAs<InOutType>()) {
        type = LValueType::get(iot->getObjectType());
      }
    }
    kind = AllowedBindingKind::Exact;
  }

  return PotentialBinding{type, kind, constraint};
}

/// Retrieve the set of potential type bindings for the given
/// representative type variable, along with flags indicating whether
/// those types should be opened.
void PotentialBindings::infer(Constraint *constraint) {
  switch (constraint->getKind()) {
  case ConstraintKind::Bind:
  case ConstraintKind::Equal:
  case ConstraintKind::BindParam:
  case ConstraintKind::BindToPointerType:
  case ConstraintKind::Subtype:
  case ConstraintKind::Conversion:
  case ConstraintKind::ArgumentConversion:
  case ConstraintKind::OperatorArgumentConversion:
  case ConstraintKind::OptionalObject:
  case ConstraintKind::UnresolvedMemberChainBase: {
    auto binding = inferFromRelational(constraint);
    if (!binding)
      break;

    addPotentialBinding(*binding);
    break;
  }
  case ConstraintKind::KeyPathApplication: {
    // If this variable is in the application projected result type, delay
    // binding until we've bound other type variables in the key-path
    // application constraint. This ensures we try to bind the key path type
    // first, which can allow us to discover additional bindings for the result
    // type.
    SmallPtrSet<TypeVariableType *, 4> typeVars;
    findInferableTypeVars(CS.simplifyType(constraint->getThirdType()),
                          typeVars);
    if (typeVars.count(TypeVar)) {
      DelayedBy.push_back(constraint);
    }

    break;
  }

  case ConstraintKind::BridgingConversion:
  case ConstraintKind::CheckedCast:
  case ConstraintKind::EscapableFunctionOf:
  case ConstraintKind::OpenedExistentialOf:
  case ConstraintKind::KeyPath:
  case ConstraintKind::FunctionInput:
  case ConstraintKind::FunctionResult:
  case ConstraintKind::OpaqueUnderlyingType:
    // Constraints from which we can't do anything.
    break;

  case ConstraintKind::DynamicTypeOf: {
    // Direct binding of the left-hand side could result
    // in `DynamicTypeOf` failure if right-hand side is
    // bound (because 'Bind' requires equal types to
    // succeed), or left is bound to Any which is not an
    // [existential] metatype.
    auto dynamicType = constraint->getFirstType();
    if (auto *tv = dynamicType->getAs<TypeVariableType>()) {
      if (tv->getImpl().getRepresentative(nullptr) == TypeVar) {
        DelayedBy.push_back(constraint);
        break;
      }
    }

    // This is right-hand side, let's continue.
    break;
  }

  case ConstraintKind::Defaultable:
  case ConstraintKind::DefaultClosureType:
    // Do these in a separate pass.
    if (CS.getFixedTypeRecursive(constraint->getFirstType(), true)
            ->getAs<TypeVariableType>() == TypeVar) {
      addDefault(constraint);
    }
    break;

  case ConstraintKind::Disjunction:
    // If there is additional context available via disjunction
    // associated with closure literal (e.g. coercion to some other
    // type) let's delay resolving the closure until the disjunction
    // is attempted.
    DelayedBy.push_back(constraint);
    break;

  case ConstraintKind::ConformsTo:
  case ConstraintKind::SelfObjectOfProtocol: {
    auto protocolTy = constraint->getSecondType();
    if (protocolTy->is<ProtocolType>())
      Protocols.push_back(constraint);
    break;
  }

  case ConstraintKind::LiteralConformsTo: {
    // Record constraint where protocol requirement originated
    // this is useful to use for the binding later.
    addLiteral(constraint);
    break;
  }

  case ConstraintKind::ApplicableFunction:
  case ConstraintKind::DynamicCallableApplicableFunction:
  case ConstraintKind::BindOverload: {
    DelayedBy.push_back(constraint);
    break;
  }

  case ConstraintKind::ValueMember:
  case ConstraintKind::UnresolvedValueMember:
  case ConstraintKind::ValueWitness:
  case ConstraintKind::PropertyWrapper: {
    // If current type variable represents a member type of some reference,
    // it would be bound once member is resolved either to a actual member
    // type or to a hole if member couldn't be found.
    auto memberTy = constraint->getSecondType()->castTo<TypeVariableType>();

    if (memberTy->getImpl().hasRepresentativeOrFixed()) {
      if (auto type = memberTy->getImpl().getFixedType(/*record=*/nullptr)) {
        // It's possible that member has been bound to some other type variable
        // instead of merged with it because it's wrapped in an l-value type.
        if (type->getWithoutSpecifierType()->isEqual(TypeVar)) {
          DelayedBy.push_back(constraint);
          break;
        }
      } else {
        memberTy = memberTy->getImpl().getRepresentative(/*record=*/nullptr);
      }
    }

    if (memberTy == TypeVar)
      DelayedBy.push_back(constraint);

    break;
  }

  case ConstraintKind::OneWayEqual:
  case ConstraintKind::OneWayBindParam: {
    // Don't produce any bindings if this type variable is on the left-hand
    // side of a one-way binding.
    auto firstType = constraint->getFirstType();
    if (auto *tv = firstType->getAs<TypeVariableType>()) {
      if (tv->getImpl().getRepresentative(nullptr) == TypeVar) {
        DelayedBy.push_back(constraint);
        break;
      }
    }

    break;
  }
  }
}

void PotentialBindings::retract(Constraint *constraint) {
  Bindings.erase(
      llvm::remove_if(Bindings,
                      [&constraint](const PotentialBinding &binding) {
                        return binding.getSource() == constraint;
                      }),
      Bindings.end());

  auto isMatchingConstraint = [&constraint](Constraint *existing) {
    return existing == constraint;
  };

  auto hasMatchingSource =
      [&constraint](
          const std::pair<TypeVariableType *, Constraint *> &adjacency) {
        return adjacency.second == constraint;
      };

  switch (constraint->getKind()) {
  case ConstraintKind::ConformsTo:
  case ConstraintKind::SelfObjectOfProtocol:
    Protocols.erase(llvm::remove_if(Protocols, isMatchingConstraint),
                    Protocols.end());
    break;

  case ConstraintKind::LiteralConformsTo:
    Literals.erase(constraint);
    break;

  case ConstraintKind::Defaultable:
  case ConstraintKind::DefaultClosureType: {
    Defaults.erase(constraint);
    break;
  }

  default:
    break;
  }

  {
    llvm::SmallPtrSet<TypeVariableType *, 2> unviable;
    for (const auto &adjacent : AdjacentVars) {
      if (adjacent.second == constraint)
        unviable.insert(adjacent.first);
    }

    for (auto *adjacentVar : unviable)
      AdjacentVars.erase(std::make_pair(adjacentVar, constraint));
  }

  DelayedBy.erase(llvm::remove_if(DelayedBy, isMatchingConstraint),
                  DelayedBy.end());

  SubtypeOf.remove_if(hasMatchingSource);
  SupertypeOf.remove_if(hasMatchingSource);
  EquivalentTo.remove_if(hasMatchingSource);
}

LiteralBindingKind BindingSet::getLiteralKind() const {
  LiteralBindingKind kind = LiteralBindingKind::None;

  for (const auto &literal : Literals) {
    auto *protocol = literal.first;
    const auto &info = literal.second;

    // Only uncovered defaultable literal protocols participate.
    if (!info.viableAsBinding())
      continue;

    switch (*protocol->getKnownProtocolKind()) {
    case KnownProtocolKind::ExpressibleByDictionaryLiteral:
    case KnownProtocolKind::ExpressibleByArrayLiteral:
    case KnownProtocolKind::ExpressibleByStringInterpolation:
      kind = LiteralBindingKind::Collection;
      break;

    case KnownProtocolKind::ExpressibleByFloatLiteral:
      kind = LiteralBindingKind::Float;
      break;

    default:
      if (kind != LiteralBindingKind::Collection)
        kind = LiteralBindingKind::Atom;
      break;
    }
  }

  return kind;
}

unsigned BindingSet::getNumViableLiteralBindings() const {
  return llvm::count_if(Literals, [&](const auto &literal) {
    return literal.second.viableAsBinding();
  });
}

void BindingSet::dump(TypeVariableType *typeVar, llvm::raw_ostream &out,
                      unsigned indent) const {
  out.indent(indent);
  out << "(";
  if (typeVar)
    out << "$T" << typeVar->getImpl().getID();
  dump(out, 1);
  out << ")\n";
}

void BindingSet::dump(llvm::raw_ostream &out, unsigned indent) const {
  out.indent(indent);
  if (isDirectHole())
    out << "hole ";
  if (isPotentiallyIncomplete())
    out << "potentially_incomplete ";
  if (isDelayed())
    out << "delayed ";
  if (isSubtypeOfExistentialType())
    out << "subtype_of_existential ";
  auto literalKind = getLiteralKind();
  if (literalKind != LiteralBindingKind::None)
    out << "literal=" << static_cast<int>(literalKind) << " ";
  if (involvesTypeVariables())
    out << "involves_type_vars ";

  auto numDefaultable = getNumViableDefaultableBindings();
  if (numDefaultable > 0)
    out << "#defaultable_bindings=" << numDefaultable << " ";

  PrintOptions PO;
  PO.PrintTypesForDebugging = true;

  auto printBinding = [&](const PotentialBinding &binding) {
    auto type = binding.BindingType;
    switch (binding.Kind) {
    case AllowedBindingKind::Exact:
      break;

    case AllowedBindingKind::Subtypes:
      out << "(subtypes of) ";
      break;

    case AllowedBindingKind::Supertypes:
      out << "(supertypes of) ";
      break;
    }
    if (auto *literal = binding.getDefaultedLiteralProtocol())
      out << "(default from " << literal->getName() << ") ";
    out << type.getString(PO);
  };

  out << "bindings={";
  interleave(Bindings, printBinding, [&]() { out << "; "; });
  out << "}";

  if (!Defaults.empty()) {
    out << " defaults={";
    for (const auto &entry : Defaults) {
      auto *constraint = entry.second;
      PotentialBinding binding{constraint->getSecondType(),
                               AllowedBindingKind::Exact, constraint};
      printBinding(binding);
    }
    out << "}";
  }
}

// Given a possibly-Optional type, return the direct superclass of the
// (underlying) type wrapped in the same number of optional levels as
// type.
static Type getOptionalSuperclass(Type type) {
  int optionalLevels = 0;
  while (auto underlying = type->getOptionalObjectType()) {
    ++optionalLevels;
    type = underlying;
  }

  if (!type->mayHaveSuperclass())
    return Type();

  auto superclass = type->getSuperclass();
  if (!superclass)
    return Type();

  while (optionalLevels--)
    superclass = OptionalType::get(superclass);

  return superclass;
}

/// Enumerates all of the 'direct' supertypes of the given type.
///
/// The direct supertype S of a type T is a supertype of T (e.g., T < S)
/// such that there is no type U where T < U and U < S.
static SmallVector<Type, 4> enumerateDirectSupertypes(Type type) {
  SmallVector<Type, 4> result;

  if (type->is<InOutType>() || type->is<LValueType>()) {
    type = type->getWithoutSpecifierType();
    result.push_back(type);
  }

  if (auto superclass = getOptionalSuperclass(type)) {
    // FIXME: Can also weaken to the set of protocol constraints, but only
    // if there are any protocols that the type conforms to but the superclass
    // does not.

    result.push_back(superclass);
  }

  // FIXME: lots of other cases to consider!
  return result;
}

bool TypeVarBindingProducer::computeNext() {
  SmallVector<Binding, 4> newBindings;
  auto addNewBinding = [&](Binding binding) {
    auto type = binding.BindingType;

    // If we've already tried this binding, move on.
    if (!BoundTypes.insert(type.getPointer()).second)
      return;

    if (!ExploredTypes.insert(type->getCanonicalType()).second)
      return;

    newBindings.push_back(std::move(binding));
  };

  for (auto &binding : Bindings) {
    const auto type = binding.BindingType;
    assert(!type->hasError());

    // After our first pass, note that we've explored these types.
    if (NumTries == 0)
      ExploredTypes.insert(type->getCanonicalType());

    // If we have a protocol with a default type, look for alternative
    // types to the default.
    if (NumTries == 0 && binding.hasDefaultedLiteralProtocol()) {
      auto knownKind =
          *(binding.getDefaultedLiteralProtocol()->getKnownProtocolKind());
      for (auto altType : CS.getAlternativeLiteralTypes(knownKind)) {
        addNewBinding(binding.withSameSource(altType, BindingKind::Subtypes));
      }
    }

    if (getLocator()->directlyAt<ForceValueExpr>() &&
        TypeVar->getImpl().canBindToLValue() &&
        !binding.BindingType->is<LValueType>()) {
      // Result of force unwrap is always connected to its base
      // optional type via `OptionalObject` constraint which
      // preserves l-valueness, so in case where object type got
      // inferred before optional type (because it got the
      // type from context e.g. parameter type of a function call),
      // we need to test type with and without l-value after
      // delaying bindings for as long as possible.
      addNewBinding(binding.withType(LValueType::get(binding.BindingType)));
    }

    // There is a tailored fix for optional key path root references,
    // let's not create ambiguity by attempting unwrap when it's
    // not allowed.
    if (binding.Kind != BindingKind::Subtypes &&
        getLocator()->isKeyPathRoot() && type->getOptionalObjectType())
      continue;

    // Allow solving for T even for a binding kind where that's invalid
    // if fixes are allowed, because that gives us the opportunity to
    // match T? values to the T binding by adding an unwrap fix.
    if (binding.Kind == BindingKind::Subtypes || CS.shouldAttemptFixes()) {
      // If we were unsuccessful solving for T?, try solving for T.
      if (auto objTy = type->getOptionalObjectType()) {
        // If T is a type variable, only attempt this if both the
        // type variable we are trying bindings for, and the type
        // variable we will attempt to bind, both have the same
        // polarity with respect to being able to bind lvalues.
        if (auto otherTypeVar = objTy->getAs<TypeVariableType>()) {
          if (TypeVar->getImpl().canBindToLValue() ==
              otherTypeVar->getImpl().canBindToLValue()) {
            addNewBinding(binding.withSameSource(objTy, binding.Kind));
          }
        } else {
          addNewBinding(binding.withSameSource(objTy, binding.Kind));
        }
      }
    }

    auto srcLocator = binding.getLocator();
    if (srcLocator &&
        (srcLocator->isLastElement<LocatorPathElt::ApplyArgToParam>() ||
         srcLocator->isLastElement<LocatorPathElt::AutoclosureResult>()) &&
        !type->hasTypeVariable() && type->isKnownStdlibCollectionType()) {
      // If the type binding comes from the argument conversion, let's
      // instead of binding collection types directly, try to bind
      // using temporary type variables substituted for element
      // types, that's going to ensure that subtype relationship is
      // always preserved.
      auto *BGT = type->castTo<BoundGenericType>();
      auto dstLocator = TypeVar->getImpl().getLocator();
      auto newType = CS.openUnboundGenericType(BGT->getDecl(), BGT->getParent(),
                                               dstLocator)
                         ->reconstituteSugar(/*recursive=*/false);
      addNewBinding(binding.withType(newType));
    }

    if (binding.Kind == BindingKind::Supertypes) {
      // If this is a type variable representing closure result,
      // which is on the right-side of some relational constraint
      // let's have it try `Void` as well because there is an
      // implicit conversion `() -> T` to `() -> Void` and this
      // helps to avoid creating a thunk to support it.
      if (getLocator()->isLastElement<LocatorPathElt::ClosureResult>() &&
          binding.Kind == AllowedBindingKind::Supertypes) {
        auto voidType = CS.getASTContext().TheEmptyTupleType;
        addNewBinding(binding.withSameSource(voidType, BindingKind::Exact));
      }

      for (auto supertype : enumerateDirectSupertypes(type)) {
        // If we're not allowed to try this binding, skip it.
        if (auto simplifiedSuper = checkTypeOfBinding(TypeVar, supertype))
          addNewBinding(binding.withType(*simplifiedSuper));
      }
    }
  }

  if (NumTries == 0) {
    // Add defaultable constraints (if any).
    for (auto *constraint : DelayedDefaults) {
      if (constraint->getKind() == ConstraintKind::DefaultClosureType) {
        // If there are no other possible bindings for this closure
        // let's default it to the type inferred from its parameters/body,
        // otherwise we should only attempt contextual types as a
        // top-level closure type.
        if (!ExploredTypes.empty())
          continue;
      }

      addNewBinding(getDefaultBinding(constraint));
    }
  }

  if (newBindings.empty())
    return false;

  Index = 0;
  ++NumTries;
  Bindings = std::move(newBindings);
  return true;
}

Optional<std::pair<ConstraintFix *, unsigned>>
TypeVariableBinding::fixForHole(ConstraintSystem &cs) const {
  auto *dstLocator = TypeVar->getImpl().getLocator();
  auto *srcLocator = Binding.getLocator();

  // FIXME: This check could be turned into an assert once
  // all code completion kinds are ported to use
  // `TypeChecker::typeCheckForCodeCompletion` API.
  if (cs.isForCodeCompletion()) {
    // If the hole is originated from code completion expression
    // let's not try to fix this, anything connected to a
    // code completion is allowed to be a hole because presence
    // of a code completion token makes constraint system
    // under-constrained due to e.g. lack of expressions on the
    // right-hand side of the token, which are required for a
    // regular type-check.
    if (dstLocator->directlyAt<CodeCompletionExpr>() ||
        srcLocator->directlyAt<CodeCompletionExpr>())
      return None;
  }

  unsigned defaultImpact = 1;

  if (auto *GP = TypeVar->getImpl().getGenericParameter()) {
    // If it is represetative for a key path root, let's emit a more
    // specific diagnostic.
    auto *keyPathRoot =
        cs.isRepresentativeFor(TypeVar, ConstraintLocator::KeyPathRoot);
    if (keyPathRoot) {
      ConstraintFix *fix = SpecifyKeyPathRootType::create(
          cs, keyPathRoot->getImpl().getLocator());
      return std::make_pair(fix, defaultImpact);
    } else {
      auto path = dstLocator->getPath();
      // Drop `generic parameter` locator element so that all missing
      // generic parameters related to the same path can be coalesced later.
      ConstraintFix *fix = DefaultGenericArgument::create(
          cs, GP,
          cs.getConstraintLocator(dstLocator->getAnchor(), path.drop_back()));
      return std::make_pair(fix, defaultImpact);
    }
  }

  if (TypeVar->getImpl().isClosureParameterType()) {
    ConstraintFix *fix = SpecifyClosureParameterType::create(cs, dstLocator);
    return std::make_pair(fix, defaultImpact);
  }

  if (TypeVar->getImpl().isClosureResultType()) {
    auto *closure = castToExpr<ClosureExpr>(dstLocator->getAnchor());
    // If the whole body is being ignored due to a pre-check failure,
    // let's not record a fix about result type since there is
    // just not enough context to infer it without a body.
    if (cs.hasFixFor(cs.getConstraintLocator(closure),
                     FixKind::IgnoreInvalidResultBuilderBody))
      return None;

    ConstraintFix *fix = SpecifyClosureReturnType::create(cs, dstLocator);
    return std::make_pair(fix, defaultImpact);
  }

  if (srcLocator->directlyAt<ObjectLiteralExpr>()) {
    ConstraintFix *fix = SpecifyObjectLiteralTypeImport::create(cs, dstLocator);
    return std::make_pair(fix, defaultImpact);
  }

  if (srcLocator->isKeyPathRoot()) {
    // If we recorded an invalid key path fix, let's skip this specify root
    // type fix because it wouldn't produce a useful diagnostic.
    auto *kpLocator = cs.getConstraintLocator(srcLocator->getAnchor());
    if (cs.hasFixFor(kpLocator, FixKind::AllowKeyPathWithoutComponents))
      return None;

    ConstraintFix *fix = SpecifyKeyPathRootType::create(cs, dstLocator);
    return std::make_pair(fix, defaultImpact);
  }

  if (dstLocator->directlyAt<NilLiteralExpr>()) {
    // This is a dramatic event, it means that there is absolutely
    // no contextual information to resolve type of `nil`.
    ConstraintFix *fix = SpecifyContextualTypeForNil::create(cs, dstLocator);
    return std::make_pair(fix, /*impact=*/(unsigned)10);
  }

  return None;
}

bool TypeVariableBinding::attempt(ConstraintSystem &cs) const {
  auto type = Binding.BindingType;
  auto *srcLocator = Binding.getLocator();
  auto *dstLocator = TypeVar->getImpl().getLocator();

  if (Binding.hasDefaultedLiteralProtocol()) {
    type = cs.replaceInferableTypesWithTypeVars(type, dstLocator);
    type = type->reconstituteSugar(/*recursive=*/false);
  }

  ConstraintSystem::TypeMatchOptions options;

  options |= ConstraintSystem::TMF_GenerateConstraints;
  options |= ConstraintSystem::TMF_BindingTypeVariable;

  auto result =
      cs.matchTypes(TypeVar, type, ConstraintKind::Bind, options, srcLocator);

  if (result.isFailure())
    return false;

  auto reportHole = [&]() {
    if (cs.isForCodeCompletion()) {
      // Don't penalize solutions with unresolved generics.
      if (TypeVar->getImpl().getGenericParameter())
        return false;
      // Don't penalize solutions with holes due to missing arguments after the
      // code completion position.
      auto argLoc = srcLocator->findLast<LocatorPathElt::SynthesizedArgument>();
      if (argLoc && argLoc->isAfterCodeCompletionLoc())
        return false;
    }
    // Reflect in the score that this type variable couldn't be
    // resolved and had to be bound to a placeholder "hole" type.
    cs.increaseScore(SK_Hole);

    if (auto fix = fixForHole(cs)) {
      if (cs.recordFix(/*fix=*/fix->first, /*impact=*/fix->second))
        return true;
    }
    return false;
  };

  // If this was from a defaultable binding note that.
  if (Binding.isDefaultableBinding()) {
    cs.DefaultedConstraints.push_back(srcLocator);

    if (type->isPlaceholder() && reportHole())
      return true;
  }

  if (cs.simplify())
    return false;

  // If all of the re-activated constraints where simplified,
  // let's notify binding inference about the fact that type
  // variable has been bound successfully.
  {
    auto &CG = cs.getConstraintGraph();
    CG[TypeVar].introduceToInference(type);
  }

  return true;
}