include/swift/Sema/ConstraintSystem.h

//===--- ConstraintSystem.h - Constraint-based Type Checking ----*- C++ -*-===//
//
// 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 provides the constraint-based type checker, anchored by the
// \c ConstraintSystem class, which provides type checking and type
// inference for expressions.
//
//===----------------------------------------------------------------------===//
#ifndef SWIFT_SEMA_CONSTRAINT_SYSTEM_H
#define SWIFT_SEMA_CONSTRAINT_SYSTEM_H

#include "swift/AST/ASTContext.h"
#include "swift/AST/ASTNode.h"
#include "swift/AST/ASTVisitor.h"
#include "swift/AST/ASTWalker.h"
#include "swift/AST/AnyFunctionRef.h"
#include "swift/AST/DiagnosticsSema.h"
#include "swift/AST/NameLookup.h"
#include "swift/AST/PropertyWrappers.h"
#include "swift/AST/Types.h"
#include "swift/Basic/Debug.h"
#include "swift/Basic/LLVM.h"
#include "swift/Basic/OptionSet.h"
#include "swift/Sema/Constraint.h"
#include "swift/Sema/ConstraintGraph.h"
#include "swift/Sema/ConstraintGraphScope.h"
#include "swift/Sema/ConstraintLocator.h"
#include "swift/Sema/CSFix.h"
#include "swift/Sema/OverloadChoice.h"
#include "swift/Sema/SolutionResult.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/ilist.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
#include <cstddef>
#include <functional>

namespace swift {

class Expr;
class FuncDecl;
class BraseStmt;
enum class TypeCheckExprFlags;

namespace constraints {

class ConstraintGraph;
class ConstraintGraphNode;
class ConstraintSystem;
class SolutionApplicationTarget;

} // end namespace constraints

namespace unittest {

class SemaTest;

} // end namespace unittest

// Forward declare some TypeChecker related functions
// so they could be made friends of ConstraintSystem.
namespace TypeChecker {

Optional<BraceStmt *> applyResultBuilderBodyTransform(FuncDecl *func,
                                                        Type builderType);

Optional<constraints::SolutionApplicationTarget>
typeCheckExpression(constraints::SolutionApplicationTarget &target,
                    OptionSet<TypeCheckExprFlags> options);

} // end namespace TypeChecker

} // end namespace swift

/// Allocate memory within the given constraint system.
void *operator new(size_t bytes, swift::constraints::ConstraintSystem& cs,
                   size_t alignment = 8);

namespace swift {

/// This specifies the purpose of the contextual type, when specified to
/// typeCheckExpression.  This is used for diagnostic generation to produce more
/// specified error messages when the conversion fails.
///
enum ContextualTypePurpose {
  CTP_Unused,           ///< No contextual type is specified.
  CTP_Initialization,   ///< Pattern binding initialization.
  CTP_ReturnStmt,       ///< Value specified to a 'return' statement.
  CTP_ReturnSingleExpr, ///< Value implicitly returned from a function.
  CTP_YieldByValue,     ///< By-value yield operand.
  CTP_YieldByReference, ///< By-reference yield operand.
  CTP_ThrowStmt,        ///< Value specified to a 'throw' statement.
  CTP_EnumCaseRawValue, ///< Raw value specified for "case X = 42" in enum.
  CTP_DefaultParameter, ///< Default value in parameter 'foo(a : Int = 42)'.

  /// Default value in @autoclosure parameter
  /// 'foo(a : @autoclosure () -> Int = 42)'.
  CTP_AutoclosureDefaultParameter,

  CTP_CalleeResult,     ///< Constraint is placed on the result of a callee.
  CTP_CallArgument,     ///< Call to function or operator requires type.
  CTP_ClosureResult,    ///< Closure result expects a specific type.
  CTP_ArrayElement,     ///< ArrayExpr wants elements to have a specific type.
  CTP_DictionaryKey,    ///< DictionaryExpr keys should have a specific type.
  CTP_DictionaryValue,  ///< DictionaryExpr values should have a specific type.
  CTP_CoerceOperand,    ///< CoerceExpr operand coerced to specific type.
  CTP_AssignSource,     ///< AssignExpr source operand coerced to result type.
  CTP_SubscriptAssignSource, ///< AssignExpr source operand coerced to subscript
                             ///< result type.
  CTP_Condition,        ///< Condition expression of various statements e.g.
                        ///< `if`, `for`, `while` etc.
  CTP_ForEachStmt,      ///< "expression/sequence" associated with 'for-in' loop
                        ///< is expected to conform to 'Sequence' protocol.
  CTP_WrappedProperty,  ///< Property type expected to match 'wrappedValue' type
  CTP_ComposedPropertyWrapper, ///< Composed wrapper type expected to match
                               ///< former 'wrappedValue' type

  CTP_CannotFail,       ///< Conversion can never fail. abort() if it does.
};

/// Specify how we handle the binding of underconstrained (free) type variables
/// within a solution to a constraint system.
enum class FreeTypeVariableBinding {
  /// Disallow any binding of such free type variables.
  Disallow,
  /// Allow the free type variables to persist in the solution.
  Allow,
  /// Bind the type variables to UnresolvedType to represent the ambiguity.
  UnresolvedType
};

namespace constraints {

/// Describes the algorithm to use for trailing closure matching.
enum class TrailingClosureMatching {
  /// Match a trailing closure to the first parameter that appears to work.
  Forward,

  /// Match a trailing closure to the last parameter.
  Backward,
};

/// A handle that holds the saved state of a type variable, which
/// can be restored.
class SavedTypeVariableBinding {
  /// The type variable that we saved the state of.
  TypeVariableType *TypeVar;

  /// The saved type variable options.
  unsigned Options;

  /// The parent or fixed type.
  llvm::PointerUnion<TypeVariableType *, TypeBase *> ParentOrFixed;

public:
  explicit SavedTypeVariableBinding(TypeVariableType *typeVar);

  /// Restore the state of the type variable to the saved state.
  void restore();
};

/// A set of saved type variable bindings.
using SavedTypeVariableBindings = SmallVector<SavedTypeVariableBinding, 16>;

class ConstraintLocator;

/// Describes a conversion restriction or a fix.
struct RestrictionOrFix {
  union {
    ConversionRestrictionKind Restriction;
    ConstraintFix *TheFix;
  };
  bool IsRestriction;

public:
  RestrictionOrFix(ConversionRestrictionKind restriction)
  : Restriction(restriction), IsRestriction(true) { }

  RestrictionOrFix(ConstraintFix *fix) : TheFix(fix), IsRestriction(false) {}

  Optional<ConversionRestrictionKind> getRestriction() const {
    if (IsRestriction)
      return Restriction;

    return None;
  }

  Optional<ConstraintFix *> getFix() const {
    if (!IsRestriction)
      return TheFix;

    return None;
  }
};


class ExpressionTimer {
  Expr* E;
  ASTContext &Context;
  llvm::TimeRecord StartTime;

  bool PrintDebugTiming;
  bool PrintWarning;

public:
  ExpressionTimer(Expr *E, ConstraintSystem &CS);

  ~ExpressionTimer();

  unsigned getWarnLimit() const {
    return Context.TypeCheckerOpts.WarnLongExpressionTypeChecking;
  }
  llvm::TimeRecord startedAt() const { return StartTime; }

  /// Return the elapsed process time (including fractional seconds)
  /// as a double.
  double getElapsedProcessTimeInFractionalSeconds() const {
    llvm::TimeRecord endTime = llvm::TimeRecord::getCurrentTime(false);

    return endTime.getProcessTime() - StartTime.getProcessTime();
  }

  // Disable emission of warnings about expressions that take longer
  // than the warning threshold.
  void disableWarning() { PrintWarning = false; }

  bool isExpired(unsigned thresholdInMillis) const {
    auto elapsed = getElapsedProcessTimeInFractionalSeconds();
    return unsigned(elapsed) > thresholdInMillis;
  }
};

} // end namespace constraints

/// Options that describe how a type variable can be used.
enum TypeVariableOptions {
  /// Whether the type variable can be bound to an lvalue type or not.
  TVO_CanBindToLValue = 0x01,

  /// Whether the type variable can be bound to an inout type or not.
  TVO_CanBindToInOut = 0x02,

  /// Whether the type variable can be bound to a non-escaping type or not.
  TVO_CanBindToNoEscape = 0x04,

  /// Whether the type variable can be bound to a hole type or not.
  TVO_CanBindToHole = 0x08,

  /// Whether a more specific deduction for this type variable implies a
  /// better solution to the constraint system.
  TVO_PrefersSubtypeBinding = 0x10,
};

/// The implementation object for a type variable used within the
/// constraint-solving type checker.
///
/// The implementation object for a type variable contains information about
/// the type variable, where it was generated, what protocols it must conform
/// to, what specific types it might be and, eventually, the fixed type to
/// which it is assigned.
class TypeVariableType::Implementation {
  /// The locator that describes where this type variable was generated.
  constraints::ConstraintLocator *locator;

  /// Either the parent of this type variable within an equivalence
  /// class of type variables, or the fixed type to which this type variable
  /// type is bound.
  llvm::PointerUnion<TypeVariableType *, TypeBase *> ParentOrFixed;

  /// The corresponding node in the constraint graph.
  constraints::ConstraintGraphNode *GraphNode = nullptr;

  ///  Index into the list of type variables, as used by the
  ///  constraint graph.
  unsigned GraphIndex;

  friend class constraints::SavedTypeVariableBinding;

public:
  /// Retrieve the type variable associated with this implementation.
  TypeVariableType *getTypeVariable() {
    return reinterpret_cast<TypeVariableType *>(this) - 1;
  }

  /// Retrieve the type variable associated with this implementation.
  const TypeVariableType *getTypeVariable() const {
    return reinterpret_cast<const TypeVariableType *>(this) - 1;
  }

  explicit Implementation(constraints::ConstraintLocator *locator,
                          unsigned options)
    : locator(locator), ParentOrFixed(getTypeVariable()) {
    getTypeVariable()->Bits.TypeVariableType.Options = options;
  }

  /// Retrieve the unique ID corresponding to this type variable.
  unsigned getID() const { return getTypeVariable()->getID(); }

  unsigned getRawOptions() const {
    return getTypeVariable()->Bits.TypeVariableType.Options;
  }

  void setRawOptions(unsigned bits) {
    getTypeVariable()->Bits.TypeVariableType.Options = bits;
    assert(getTypeVariable()->Bits.TypeVariableType.Options == bits
           && "Trucation");
  }

  /// Whether this type variable can bind to an lvalue type.
  bool canBindToLValue() const { return getRawOptions() & TVO_CanBindToLValue; }

  /// Whether this type variable can bind to an inout type.
  bool canBindToInOut() const { return getRawOptions() & TVO_CanBindToInOut; }

  /// Whether this type variable can bind to an inout type.
  bool canBindToNoEscape() const { return getRawOptions() & TVO_CanBindToNoEscape; }

  /// Whether this type variable can bind to a hole type.
  bool canBindToHole() const { return getRawOptions() & TVO_CanBindToHole; }

  /// Whether this type variable prefers a subtype binding over a supertype
  /// binding.
  bool prefersSubtypeBinding() const {
    return getRawOptions() & TVO_PrefersSubtypeBinding;
  }

  /// Retrieve the corresponding node in the constraint graph.
  constraints::ConstraintGraphNode *getGraphNode() const { return GraphNode; }

  /// Set the corresponding node in the constraint graph.
  void setGraphNode(constraints::ConstraintGraphNode *newNode) { 
    GraphNode = newNode; 
  }

  /// Retrieve the index into the constraint graph's list of type variables.
  unsigned getGraphIndex() const { 
    assert(GraphNode && "Graph node isn't set");
    return GraphIndex;
  }

  /// Set the index into the constraint graph's list of type variables.
  void setGraphIndex(unsigned newIndex) {
    GraphIndex = newIndex;
  }
  
  /// Check whether this type variable either has a representative that
  /// is not itself or has a fixed type binding.
  bool hasRepresentativeOrFixed() const {
    // If we have a fixed type, we're done.
    if (!ParentOrFixed.is<TypeVariableType *>())
      return true;

    // Check whether the representative is different from our own type
    // variable.
    return ParentOrFixed.get<TypeVariableType *>() != getTypeVariable();
  }

  /// Record the current type-variable binding.
  void recordBinding(constraints::SavedTypeVariableBindings &record) {
    record.push_back(constraints::SavedTypeVariableBinding(getTypeVariable()));
  }

  /// Retrieve the locator describing where this type variable was
  /// created.
  constraints::ConstraintLocator *getLocator() const {
    return locator;
  }

  /// Retrieve the generic parameter opened by this type variable.
  GenericTypeParamType *getGenericParameter() const;

  /// Returns the \c ExprKind of this type variable if it's the type of an
  /// atomic literal expression, meaning the literal can't be composed of subexpressions.
  /// Otherwise, returns \c None.
  Optional<ExprKind> getAtomicLiteralKind() const;

  /// Determine whether this type variable represents a closure type.
  bool isClosureType() const;

  /// Determine whether this type variable represents one of the
  /// parameter types associated with a closure.
  bool isClosureParameterType() const;

  /// Determine whether this type variable represents a closure result type.
  bool isClosureResultType() const;

  /// Retrieve the representative of the equivalence class to which this
  /// type variable belongs.
  ///
  /// \param record The record of changes made by retrieving the representative,
  /// which can happen due to path compression. If null, path compression is
  /// not performed.
  TypeVariableType *
  getRepresentative(constraints::SavedTypeVariableBindings *record) {
    // Find the representative type variable.
    auto result = getTypeVariable();
    Implementation *impl = this;
    while (impl->ParentOrFixed.is<TypeVariableType *>()) {
      // Extract the representative.
      auto nextTV = impl->ParentOrFixed.get<TypeVariableType *>();
      if (nextTV == result)
        break;

      result = nextTV;
      impl = &nextTV->getImpl();
    }

    if (impl == this || !record)
      return result;

    // Perform path compression.
    impl = this;
    while (impl->ParentOrFixed.is<TypeVariableType *>()) {
      // Extract the representative.
      auto nextTV = impl->ParentOrFixed.get<TypeVariableType *>();
      if (nextTV == result)
        break;

      // Record the state change.
      impl->recordBinding(*record);

      impl->ParentOrFixed = result;
      impl = &nextTV->getImpl();
    }

    return result;
  }

  /// Merge the equivalence class of this type variable with the
  /// equivalence class of another type variable.
  ///
  /// \param other The type variable to merge with.
  ///
  /// \param record The record of state changes.
  void mergeEquivalenceClasses(TypeVariableType *other,
                               constraints::SavedTypeVariableBindings *record) {
    // Merge the equivalence classes corresponding to these two type
    // variables. Always merge 'up' the constraint stack, because it is simpler.
    if (getID() > other->getImpl().getID()) {
      other->getImpl().mergeEquivalenceClasses(getTypeVariable(), record);
      return;
    }

    auto otherRep = other->getImpl().getRepresentative(record);
    if (record)
      otherRep->getImpl().recordBinding(*record);
    otherRep->getImpl().ParentOrFixed = getTypeVariable();

    if (canBindToLValue() && !otherRep->getImpl().canBindToLValue()) {
      if (record)
        recordBinding(*record);
      getTypeVariable()->Bits.TypeVariableType.Options &= ~TVO_CanBindToLValue;
    }

    if (canBindToInOut() && !otherRep->getImpl().canBindToInOut()) {
      if (record)
        recordBinding(*record);
      getTypeVariable()->Bits.TypeVariableType.Options &= ~TVO_CanBindToInOut;
    }

    if (canBindToNoEscape() && !otherRep->getImpl().canBindToNoEscape()) {
      if (record)
        recordBinding(*record);
      getTypeVariable()->Bits.TypeVariableType.Options &= ~TVO_CanBindToNoEscape;
    }
  }

  /// Retrieve the fixed type that corresponds to this type variable,
  /// if there is one.
  ///
  /// \returns the fixed type associated with this type variable, or a null
  /// type if there is no fixed type.
  ///
  /// \param record The record of changes made by retrieving the representative,
  /// which can happen due to path compression. If null, path compression is
  /// not performed.
  Type getFixedType(constraints::SavedTypeVariableBindings *record) {
    // Find the representative type variable.
    auto rep = getRepresentative(record);
    Implementation &repImpl = rep->getImpl();

    // Return the bound type if there is one, otherwise, null.
    return repImpl.ParentOrFixed.dyn_cast<TypeBase *>();
  }

  /// Assign a fixed type to this equivalence class.
  void assignFixedType(Type type,
                       constraints::SavedTypeVariableBindings *record) {
    assert((!getFixedType(0) || getFixedType(0)->isEqual(type)) &&
           "Already has a fixed type!");
    auto rep = getRepresentative(record);
    if (record)
      rep->getImpl().recordBinding(*record);
    rep->getImpl().ParentOrFixed = type.getPointer();
  }

  void setCanBindToLValue(constraints::SavedTypeVariableBindings *record,
                          bool enabled) {
    auto &impl = getRepresentative(record)->getImpl();
    if (record)
      impl.recordBinding(*record);

    if (enabled)
      impl.getTypeVariable()->Bits.TypeVariableType.Options |=
          TVO_CanBindToLValue;
    else
      impl.getTypeVariable()->Bits.TypeVariableType.Options &=
          ~TVO_CanBindToLValue;
  }

  void setCanBindToNoEscape(constraints::SavedTypeVariableBindings *record,
                            bool enabled) {
    auto &impl = getRepresentative(record)->getImpl();
    if (record)
      impl.recordBinding(*record);

    if (enabled)
      impl.getTypeVariable()->Bits.TypeVariableType.Options |=
          TVO_CanBindToNoEscape;
    else
      impl.getTypeVariable()->Bits.TypeVariableType.Options &=
          ~TVO_CanBindToNoEscape;
  }

  void enableCanBindToHole(constraints::SavedTypeVariableBindings *record) {
    auto &impl = getRepresentative(record)->getImpl();
    if (record)
      impl.recordBinding(*record);

    impl.getTypeVariable()->Bits.TypeVariableType.Options |= TVO_CanBindToHole;
  }

  /// Print the type variable to the given output stream.
  void print(llvm::raw_ostream &OS);
};

namespace constraints {

template <typename T = Expr> T *castToExpr(ASTNode node) {
  return cast<T>(node.get<Expr *>());
}

template <typename T = Expr> T *getAsExpr(ASTNode node) {
  if (auto *E = node.dyn_cast<Expr *>())
    return dyn_cast_or_null<T>(E);
  return nullptr;
}

template <typename T> bool isExpr(ASTNode node) {
  if (node.isNull() || !node.is<Expr *>())
    return false;

  auto *E = node.get<Expr *>();
  return isa<T>(E);
}

template <typename T = Decl> T *getAsDecl(ASTNode node) {
  if (auto *E = node.dyn_cast<Decl *>())
    return dyn_cast_or_null<T>(E);
  return nullptr;
}

SourceLoc getLoc(ASTNode node);
SourceRange getSourceRange(ASTNode node);

/// The result of comparing two constraint systems that are a solutions
/// to the given set of constraints.
enum class SolutionCompareResult {
  /// The two solutions are incomparable, because, e.g., because one
  /// solution has some better decisions and some worse decisions than the
  /// other.
  Incomparable,
  /// The two solutions are identical.
  Identical,
  /// The first solution is better than the second.
  Better,
  /// The second solution is better than the first.
  Worse
};

/// An overload that has been selected in a particular solution.
///
/// A selected overload captures the specific overload choice (e.g., a
/// particular declaration) as well as the type to which the reference to the
/// declaration was opened, which may involve type variables.
struct SelectedOverload {
  /// The overload choice.
  const OverloadChoice choice;

  /// The opened type of the base of the reference to this overload, if
  /// we're referencing a member.
  const Type openedFullType;

  /// The opened type produced by referring to this overload.
  const Type openedType;

  /// The type that this overload binds. Note that this may differ from
  /// openedType, for example it will include any IUO unwrapping that has taken
  /// place.
  const Type boundType;
};

/// Provides information about the application of a function argument to a
/// parameter.
class FunctionArgApplyInfo {
  Expr *ArgListExpr;
  Expr *ArgExpr;
  unsigned ArgIdx;
  Type ArgType;

  unsigned ParamIdx;

  Type FnInterfaceType;
  FunctionType *FnType;
  const ValueDecl *Callee;

public:
  FunctionArgApplyInfo(Expr *argListExpr, Expr *argExpr, unsigned argIdx,
                       Type argType, unsigned paramIdx, Type fnInterfaceType,
                       FunctionType *fnType, const ValueDecl *callee)
      : ArgListExpr(argListExpr), ArgExpr(argExpr), ArgIdx(argIdx),
        ArgType(argType), ParamIdx(paramIdx), FnInterfaceType(fnInterfaceType),
        FnType(fnType), Callee(callee) {}

  /// \returns The list of the arguments used for this application.
  Expr *getArgListExpr() const { return ArgListExpr; }

  /// \returns The argument being applied.
  Expr *getArgExpr() const { return ArgExpr; }

  /// \returns The position of the argument, starting at 1.
  unsigned getArgPosition() const { return ArgIdx + 1; }

  /// \returns The position of the parameter, starting at 1.
  unsigned getParamPosition() const { return ParamIdx + 1; }

  /// \returns The type of the argument being applied, including any generic
  /// substitutions.
  ///
  /// \param withSpecifier Whether to keep the inout or @lvalue specifier of
  /// the argument, if any.
  Type getArgType(bool withSpecifier = false) const {
    return withSpecifier ? ArgType : ArgType->getWithoutSpecifierType();
  }

  /// \returns The label for the argument being applied.
  Identifier getArgLabel() const {
    if (auto *te = dyn_cast<TupleExpr>(ArgListExpr))
      return te->getElementName(ArgIdx);

    assert(isa<ParenExpr>(ArgListExpr));
    return Identifier();
  }

  Identifier getParamLabel() const {
    auto param = FnType->getParams()[ParamIdx];
    return param.getLabel();
  }

  /// \returns A textual description of the argument suitable for diagnostics.
  /// For an argument with an unambiguous label, this will the label. Otherwise
  /// it will be its position in the argument list.
  StringRef getArgDescription(SmallVectorImpl<char> &scratch) const {
    llvm::raw_svector_ostream stream(scratch);

    // Use the argument label only if it's unique within the argument list.
    auto argLabel = getArgLabel();
    auto useArgLabel = [&]() -> bool {
      if (argLabel.empty())
        return false;

      if (auto *te = dyn_cast<TupleExpr>(ArgListExpr))
        return llvm::count(te->getElementNames(), argLabel) == 1;

      return false;
    };

    if (useArgLabel()) {
      stream << "'";
      stream << argLabel;
      stream << "'";
    } else {
      stream << "#";
      stream << getArgPosition();
    }
    return StringRef(scratch.data(), scratch.size());
  }

  /// Whether the argument is a trailing closure.
  bool isTrailingClosure() const {
    if (auto trailingClosureArg =
            ArgListExpr->getUnlabeledTrailingClosureIndexOfPackedArgument())
      return ArgIdx >= *trailingClosureArg;

    return false;
  }

  /// \returns The interface type for the function being applied. Note that this
  /// may not a function type, for example it could be a generic parameter.
  Type getFnInterfaceType() const { return FnInterfaceType; }

  /// \returns The function type being applied, including any generic
  /// substitutions.
  FunctionType *getFnType() const { return FnType; }

  /// \returns The callee for the application.
  const ValueDecl *getCallee() const { return Callee; }

private:
  Type getParamTypeImpl(AnyFunctionType *fnTy,
                        bool lookThroughAutoclosure) const {
    auto param = fnTy->getParams()[ParamIdx];
    auto paramTy = param.getPlainType();
    if (lookThroughAutoclosure && param.isAutoClosure())
      paramTy = paramTy->castTo<FunctionType>()->getResult();
    return paramTy;
  }

public:
  /// \returns The type of the parameter which the argument is being applied to,
  /// including any generic substitutions.
  ///
  /// \param lookThroughAutoclosure Whether an @autoclosure () -> T parameter
  /// should be treated as being of type T.
  Type getParamType(bool lookThroughAutoclosure = true) const {
    return getParamTypeImpl(FnType, lookThroughAutoclosure);
  }

  /// \returns The interface type of the parameter which the argument is being
  /// applied to.
  ///
  /// \param lookThroughAutoclosure Whether an @autoclosure () -> T parameter
  /// should be treated as being of type T.
  Type getParamInterfaceType(bool lookThroughAutoclosure = true) const {
    auto interfaceFnTy = FnInterfaceType->getAs<AnyFunctionType>();
    if (!interfaceFnTy) {
      // If the interface type isn't a function, then just return the resolved
      // parameter type.
      return getParamType(lookThroughAutoclosure)->mapTypeOutOfContext();
    }
    return getParamTypeImpl(interfaceFnTy, lookThroughAutoclosure);
  }

  /// \returns The flags of the parameter which the argument is being applied
  /// to.
  ParameterTypeFlags getParameterFlags() const {
    return FnType->getParams()[ParamIdx].getParameterFlags();
  }

  ParameterTypeFlags getParameterFlagsAtIndex(unsigned idx) const {
    return FnType->getParams()[idx].getParameterFlags();
  }
};

/// Describes an aspect of a solution that affects its overall score, i.e., a
/// user-defined conversions.
enum ScoreKind {
  // These values are used as indices into a Score value.

  /// A fix needs to be applied to the source.
  SK_Fix,
  /// A hole in the constraint system.
  SK_Hole,
  /// A reference to an @unavailable declaration.
  SK_Unavailable,
  /// A reference to an async function in a synchronous context, or
  /// vice versa.
  SK_AsyncSyncMismatch,
  /// A use of the "forward" scan for trailing closures.
  SK_ForwardTrailingClosure,
  /// A use of a disfavored overload.
  SK_DisfavoredOverload,
  /// A member for an \c UnresolvedMemberExpr found via unwrapped optional base.
  SK_UnresolvedMemberViaOptional,
  /// An implicit force of an implicitly unwrapped optional value.
  SK_ForceUnchecked,
  /// A user-defined conversion.
  SK_UserConversion,
  /// A non-trivial function conversion.
  SK_FunctionConversion,
  /// A literal expression bound to a non-default literal type.
  SK_NonDefaultLiteral,
  /// An implicit upcast conversion between collection types.
  SK_CollectionUpcastConversion,
  /// A value-to-optional conversion.
  SK_ValueToOptional,
  /// A conversion to an empty existential type ('Any' or '{}').
  SK_EmptyExistentialConversion,
  /// A key path application subscript.
  SK_KeyPathSubscript,
  /// A conversion from a string, array, or inout to a pointer.
  SK_ValueToPointerConversion,

  SK_LastScoreKind = SK_ValueToPointerConversion,
};

/// The number of score kinds.
const unsigned NumScoreKinds = SK_LastScoreKind + 1;

/// Describes what happened when a result builder transform was applied
/// to a particular closure.
struct AppliedBuilderTransform {
  /// The builder type that was applied to the closure.
  Type builderType;

  /// The result type of the body, to which the returned expression will be
  /// converted.
  Type bodyResultType;

  /// An expression whose value has been recorded for later use.
  struct RecordedExpr {
    /// The temporary value that captures the value of the expression, if
    /// there is one.
    VarDecl *temporaryVar;

    /// The expression that results from generating constraints with this
    /// particular builder.
    Expr *generatedExpr;
  };

  /// A mapping from expressions whose values are captured by the builder
  /// to information about the temporary variable capturing the
  llvm::DenseMap<Expr *, RecordedExpr> capturedExprs;

  /// A mapping from statements to a pair containing the implicit variable
  /// declaration that captures the result of that expression, and the
  /// set of expressions that can be used to produce a value for that
  /// variable.
  llvm::DenseMap<Stmt *, std::pair<VarDecl *, llvm::TinyPtrVector<Expr *>>>
      capturedStmts;

  /// The return expression, capturing the last value to be emitted.
  Expr *returnExpr = nullptr;
};

/// Describes the fixed score of a solution to the constraint system.
struct Score {
  unsigned Data[NumScoreKinds] = {};

  friend Score &operator+=(Score &x, const Score &y) {
    for (unsigned i = 0; i != NumScoreKinds; ++i) {
      x.Data[i] += y.Data[i];
    }
    return x;
  }

  friend Score operator+(const Score &x, const Score &y) {
    Score result;
    for (unsigned i = 0; i != NumScoreKinds; ++i) {
      result.Data[i] = x.Data[i] + y.Data[i];
    }
    return result;
  }

  friend Score operator-(const Score &x, const Score &y) {
    Score result;
    for (unsigned i = 0; i != NumScoreKinds; ++i) {
      result.Data[i] = x.Data[i] - y.Data[i];
    }
    return result;
  }

  friend Score &operator-=(Score &x, const Score &y) {
    for (unsigned i = 0; i != NumScoreKinds; ++i) {
      x.Data[i] -= y.Data[i];
    }
    return x;
  }

  friend bool operator==(const Score &x, const Score &y) {
    for (unsigned i = 0; i != NumScoreKinds; ++i) {
      if (x.Data[i] != y.Data[i])
        return false;
    }

    return true;
  }

  friend bool operator!=(const Score &x, const Score &y) {
    return !(x == y);
  }

  friend bool operator<(const Score &x, const Score &y) {
    for (unsigned i = 0; i != NumScoreKinds; ++i) {
      if (x.Data[i] < y.Data[i])
        return true;

      if (x.Data[i] > y.Data[i])
        return false;
    }

    return false;
  }

  friend bool operator<=(const Score &x, const Score &y) {
    return !(y < x);
  }

  friend bool operator>(const Score &x, const Score &y) {
    return y < x;
  }

  friend bool operator>=(const Score &x, const Score &y) {
    return !(x < y);
  }

};

/// Display a score.
llvm::raw_ostream &operator<<(llvm::raw_ostream &out, const Score &score);

/// Describes a dependent type that has been opened to a particular type
/// variable.
using OpenedType = std::pair<GenericTypeParamType *, TypeVariableType *>;

using OpenedTypeMap =
    llvm::DenseMap<GenericTypeParamType *, TypeVariableType *>;

/// Describes contextual type information about a particular expression
/// within a constraint system.
struct ContextualTypeInfo {
  TypeLoc typeLoc;
  ContextualTypePurpose purpose;

  ContextualTypeInfo() : typeLoc(TypeLoc()), purpose(CTP_Unused) {}

  ContextualTypeInfo(Type contextualTy, ContextualTypePurpose purpose)
      : typeLoc(TypeLoc::withoutLoc(contextualTy)), purpose(purpose) {}

  ContextualTypeInfo(TypeLoc typeLoc, ContextualTypePurpose purpose)
      : typeLoc(typeLoc), purpose(purpose) {}

  Type getType() const { return typeLoc.getType(); }
};

/// Describes the information about a case label item that needs to be tracked
/// within the constraint system.
struct CaseLabelItemInfo {
  Pattern *pattern;
  Expr *guardExpr;
};

/// Describes information about a for-each loop that needs to be tracked
/// within the constraint system.
struct ForEachStmtInfo {
  ForEachStmt *stmt;

  /// The type of the sequence.
  Type sequenceType;

  /// The type of the iterator.
  Type iteratorType;

  /// The type of an element in the sequence.
  Type elementType;

  /// The type of the pattern that matches the elements.
  Type initType;

  /// The "where" expression, if there is one.
  Expr *whereExpr;
};

/// Key to the constraint solver's mapping from AST nodes to their corresponding
/// solution application targets.
class SolutionApplicationTargetsKey {
public:
  enum class Kind {
    empty,
    tombstone,
    stmtCondElement,
    stmt,
    patternBindingEntry,
    varDecl,
  };

private:
  Kind kind;

  union {
    const StmtConditionElement *stmtCondElement;

    const Stmt *stmt;

    struct PatternBindingEntry {
      const PatternBindingDecl *patternBinding;
      unsigned index;
    } patternBindingEntry;

    const VarDecl *varDecl;
  } storage;

public:
  SolutionApplicationTargetsKey(Kind kind) {
    assert(kind == Kind::empty || kind == Kind::tombstone);
    this->kind = kind;
  }

  SolutionApplicationTargetsKey(const StmtConditionElement *stmtCondElement) {
    kind = Kind::stmtCondElement;
    storage.stmtCondElement = stmtCondElement;
  }

  SolutionApplicationTargetsKey(const Stmt *stmt) {
    kind = Kind::stmt;
    storage.stmt = stmt;
  }

  SolutionApplicationTargetsKey(
      const PatternBindingDecl *patternBinding, unsigned index) {
    kind = Kind::stmt;
    storage.patternBindingEntry.patternBinding = patternBinding;
    storage.patternBindingEntry.index = index;
  }

  SolutionApplicationTargetsKey(const VarDecl *varDecl) {
    kind = Kind::varDecl;
    storage.varDecl = varDecl;
  }

  friend bool operator==(
      SolutionApplicationTargetsKey lhs, SolutionApplicationTargetsKey rhs) {
    if (lhs.kind != rhs.kind)
      return false;

    switch (lhs.kind) {
    case Kind::empty:
    case Kind::tombstone:
      return true;

    case Kind::stmtCondElement:
      return lhs.storage.stmtCondElement == rhs.storage.stmtCondElement;

    case Kind::stmt:
      return lhs.storage.stmt == rhs.storage.stmt;

    case Kind::patternBindingEntry:
      return (lhs.storage.patternBindingEntry.patternBinding
                == rhs.storage.patternBindingEntry.patternBinding) &&
          (lhs.storage.patternBindingEntry.index
             == rhs.storage.patternBindingEntry.index);

    case Kind::varDecl:
      return lhs.storage.varDecl == rhs.storage.varDecl;
    }
    llvm_unreachable("invalid SolutionApplicationTargetsKey kind");
  }

  friend bool operator!=(
      SolutionApplicationTargetsKey lhs, SolutionApplicationTargetsKey rhs) {
    return !(lhs == rhs);
  }

  unsigned getHashValue() const {
    using llvm::hash_combine;
    using llvm::DenseMapInfo;

    switch (kind) {
    case Kind::empty:
    case Kind::tombstone:
      return llvm::DenseMapInfo<unsigned>::getHashValue(static_cast<unsigned>(kind));

    case Kind::stmtCondElement:
      return hash_combine(
          DenseMapInfo<unsigned>::getHashValue(static_cast<unsigned>(kind)),
          DenseMapInfo<void *>::getHashValue(storage.stmtCondElement));

    case Kind::stmt:
      return hash_combine(
          DenseMapInfo<unsigned>::getHashValue(static_cast<unsigned>(kind)),
          DenseMapInfo<void *>::getHashValue(storage.stmt));

    case Kind::patternBindingEntry:
      return hash_combine(
          DenseMapInfo<unsigned>::getHashValue(static_cast<unsigned>(kind)),
          DenseMapInfo<void *>::getHashValue(
              storage.patternBindingEntry.patternBinding),
          DenseMapInfo<unsigned>::getHashValue(
              storage.patternBindingEntry.index));

    case Kind::varDecl:
      return hash_combine(
          DenseMapInfo<unsigned>::getHashValue(static_cast<unsigned>(kind)),
          DenseMapInfo<void *>::getHashValue(storage.varDecl));
    }
    llvm_unreachable("invalid statement kind");
  }
};

/// A complete solution to a constraint system.
///
/// A solution to a constraint system consists of type variable bindings to
/// concrete types for every type variable that is used in the constraint
/// system along with a set of mappings from each constraint locator
/// involving an overload set to the selected overload.
class Solution {
  /// The constraint system this solution solves.
  ConstraintSystem *constraintSystem;

  /// The fixed score for this solution.
  Score FixedScore;

public:
  /// Create a solution for the given constraint system.
  Solution(ConstraintSystem &cs, const Score &score)
    : constraintSystem(&cs), FixedScore(score) {}

  // Solution is a non-copyable type for performance reasons.
  Solution(const Solution &other) = delete;
  Solution &operator=(const Solution &other) = delete;

  Solution(Solution &&other) = default;
  Solution &operator=(Solution &&other) = default;

  size_t getTotalMemory() const;

  /// Retrieve the constraint system that this solution solves.
  ConstraintSystem &getConstraintSystem() const { return *constraintSystem; }

  DeclContext *getDC() const;

  /// The set of type bindings.
  llvm::DenseMap<TypeVariableType *, Type> typeBindings;
  
  /// The set of overload choices along with their types.
  llvm::DenseMap<ConstraintLocator *, SelectedOverload> overloadChoices;

  /// The set of constraint restrictions used to arrive at this restriction,
  /// which informs constraint application.
  llvm::DenseMap<std::pair<CanType, CanType>, ConversionRestrictionKind>
    ConstraintRestrictions;

  /// The list of fixes that need to be applied to the initial expression
  /// to make the solution work.
  llvm::SmallVector<ConstraintFix *, 4> Fixes;

  /// For locators associated with call expressions, the trailing closure
  /// matching rule that was applied.
  llvm::SmallMapVector<ConstraintLocator*, TrailingClosureMatching, 4>
    trailingClosureMatchingChoices;

  /// The set of disjunction choices used to arrive at this solution,
  /// which informs constraint application.
  llvm::DenseMap<ConstraintLocator *, unsigned> DisjunctionChoices;

  /// The set of opened types for a given locator.
  llvm::DenseMap<ConstraintLocator *, ArrayRef<OpenedType>> OpenedTypes;

  /// The opened existential type for a given locator.
  llvm::DenseMap<ConstraintLocator *, OpenedArchetypeType *>
    OpenedExistentialTypes;

  /// The locators of \c Defaultable constraints whose defaults were used.
  llvm::SmallPtrSet<ConstraintLocator *, 2> DefaultedConstraints;

  /// The node -> type mappings introduced by this solution.
  llvm::DenseMap<ASTNode, Type> nodeTypes;

  /// Contextual types introduced by this solution.
  std::vector<std::pair<ASTNode, ContextualTypeInfo>> contextualTypes;

  /// Maps AST nodes to their solution application targets.
  llvm::MapVector<SolutionApplicationTargetsKey, SolutionApplicationTarget>
    solutionApplicationTargets;

  /// Maps case label items to information tracked about them as they are
  /// being solved.
  llvm::SmallMapVector<const CaseLabelItem *, CaseLabelItemInfo, 4>
      caseLabelItems;

  std::vector<std::pair<ConstraintLocator *, ProtocolConformanceRef>>
      Conformances;

  /// The set of functions that have been transformed by a result builder.
  llvm::MapVector<AnyFunctionRef, AppliedBuilderTransform>
      resultBuilderTransformed;

  /// Simplify the given type by substituting all occurrences of
  /// type variables for their fixed types.
  Type simplifyType(Type type) const;

  /// Coerce the given expression to the given type.
  ///
  /// This operation cannot fail.
  ///
  /// \param expr The expression to coerce.
  /// \param toType The type to coerce the expression to.
  /// \param locator Locator used to describe the location of this expression.
  ///
  /// \param typeFromPattern Optionally, the caller can specify the pattern
  /// from where the toType is derived, so that we can deliver better fixit.
  ///
  /// \returns the coerced expression, which will have type \c ToType.
  Expr *coerceToType(Expr *expr, Type toType,
                     ConstraintLocator *locator,
                     Optional<Pattern*> typeFromPattern = None);

  /// Compute the set of substitutions for a generic signature opened at the
  /// given locator.
  ///
  /// \param sig The generic signature.
  ///
  /// \param locator The locator that describes where the substitutions came
  /// from.
  SubstitutionMap computeSubstitutions(GenericSignature sig,
                                       ConstraintLocator *locator) const;

  /// Resolves the contextual substitutions for a reference to a declaration
  /// at a given locator.
  ConcreteDeclRef
  resolveConcreteDeclRef(ValueDecl *decl, ConstraintLocator *locator) const;

  /// Return the disjunction choice for the given constraint location.
  unsigned getDisjunctionChoice(ConstraintLocator *locator) const {
    assert(DisjunctionChoices.count(locator));
    return DisjunctionChoices.find(locator)->second;
  }

  /// Retrieve the fixed score of this solution
  const Score &getFixedScore() const { return FixedScore; }

  /// Retrieve the fixed score of this solution
  Score &getFixedScore() { return FixedScore; }

  /// Retrieve the fixed type for the given type variable.
  Type getFixedType(TypeVariableType *typeVar) const;

  /// Try to resolve the given locator to a declaration within this
  /// solution. Note that this only returns a decl for a direct reference such
  /// as \c x.foo and will not return a decl for \c x.foo().
  ConcreteDeclRef resolveLocatorToDecl(ConstraintLocator *locator) const;

  /// Retrieve the overload choice associated with the given
  /// locator.
  SelectedOverload getOverloadChoice(ConstraintLocator *locator) const {
    return *getOverloadChoiceIfAvailable(locator);
  }

  /// Retrieve the overload choice associated with the given
  /// locator.
  Optional<SelectedOverload>
  getOverloadChoiceIfAvailable(ConstraintLocator *locator) const {
    auto known = overloadChoices.find(locator);
    if (known != overloadChoices.end())
      return known->second;
    return None;
  }

  /// Retrieve a fully-resolved protocol conformance at the given locator
  /// and with the given protocol.
  ProtocolConformanceRef resolveConformance(ConstraintLocator *locator,
                                            ProtocolDecl *proto);

  ConstraintLocator *getCalleeLocator(ConstraintLocator *locator,
                                      bool lookThroughApply = true) const;

  ConstraintLocator *
  getConstraintLocator(ASTNode anchor,
                       ArrayRef<LocatorPathElt> path = {}) const;

  ConstraintLocator *getConstraintLocator(ConstraintLocator *baseLocator,
                                          ArrayRef<LocatorPathElt> path) const;

  void setExprTypes(Expr *expr) const;

  bool hasType(ASTNode node) const;

  /// Retrieve the type of the given node, as recorded in this solution.
  Type getType(ASTNode node) const;

  /// Retrieve the type of the given node as recorded in this solution
  /// and resolve all of the type variables in contains to form a fully
  /// "resolved" concrete type.
  Type getResolvedType(ASTNode node) const;

  /// Resolve type variables present in the raw type, using generic parameter
  /// types where possible.
  Type resolveInterfaceType(Type type) const;

  /// For a given locator describing a function argument conversion, or a
  /// constraint within an argument conversion, returns information about the
  /// application of the argument to its parameter. If the locator is not
  /// for an argument conversion, returns \c None.
  Optional<FunctionArgApplyInfo>
  getFunctionArgApplyInfo(ConstraintLocator *) const;

  /// Retrieve the builder transform that was applied to this function, if any.
  const AppliedBuilderTransform *getAppliedBuilderTransform(
     AnyFunctionRef fn) const {
    auto known = resultBuilderTransformed.find(fn);
    return known != resultBuilderTransformed.end()
        ? &known->second
        : nullptr;
  }

  /// This method implements functionality of `Expr::isTypeReference`
  /// with data provided by a given solution.
  bool isTypeReference(Expr *E) const;

  /// Call Expr::isIsStaticallyDerivedMetatype on the given
  /// expression, using a custom accessor for the type on the
  /// expression that reads the type from the Solution
  /// expression type map.
  bool isStaticallyDerivedMetatype(Expr *E) const;

  SWIFT_DEBUG_DUMP;

  /// Dump this solution.
  void dump(raw_ostream &OS) const LLVM_ATTRIBUTE_USED;
};

/// Describes the differences between several solutions to the same
/// constraint system.
class SolutionDiff {
public:
  /// A difference between two overloads.
  struct OverloadDiff {
    /// The locator that describes where the overload comes from.
    ConstraintLocator *locator;

    /// The choices that each solution made.
    SmallVector<OverloadChoice, 2> choices;
  };

  /// The differences between the overload choices between the
  /// solutions.
  SmallVector<OverloadDiff, 4> overloads;

  /// Compute the differences between the given set of solutions.
  ///
  /// \param solutions The set of solutions.
  explicit SolutionDiff(ArrayRef<Solution> solutions);
};

/// An intrusive, doubly-linked list of constraints.
using ConstraintList = llvm::ilist<Constraint>;

enum class ConstraintSystemFlags {
  /// Whether we allow the solver to attempt fixes to the system.
  AllowFixes = 0x01,

  /// Set if the client wants diagnostics suppressed.
  SuppressDiagnostics = 0x02,

  /// If set, the client wants a best-effort solution to the constraint system,
  /// but can tolerate a solution where all of the constraints are solved, but
  /// not all type variables have been determined.  In this case, the constraint
  /// system is not applied to the expression AST, but the ConstraintSystem is
  /// left in-tact.
  AllowUnresolvedTypeVariables = 0x04,

  /// If set, constraint system always reuses type of pre-typechecked
  /// expression, and doesn't dig into its subexpressions.
  ReusePrecheckedType = 0x08,

  /// If set, verbose output is enabled for this constraint system.
  ///
  /// Note that this flag is automatically applied to all constraint systems
  /// when \c DebugConstraintSolver is set in \c TypeCheckerOptions. It can be
  /// automatically enabled for select constraint solving attempts by setting
  /// \c DebugConstraintSolverAttempt. Finally, it be automatically enabled
  /// for a pre-configured set of expressions on line numbers by setting
  /// \c DebugConstraintSolverOnLines.
  DebugConstraints = 0x10,

  /// Don't try to type check closure bodies, and leave them unchecked. This is
  /// used for source tooling functionalities.
  LeaveClosureBodyUnchecked = 0x20,

  /// If set, we are solving specifically to determine the type of a
  /// CodeCompletionExpr, and should continue in the presence of errors wherever
  /// possible.
  ForCodeCompletion = 0x40,
};

/// Options that affect the constraint system as a whole.
using ConstraintSystemOptions = OptionSet<ConstraintSystemFlags>;

/// This struct represents the results of a member lookup of
struct MemberLookupResult {
  enum {
    /// This result indicates that we cannot begin to solve this, because the
    /// base expression is a type variable.
    Unsolved,
    
    /// This result indicates that the member reference is erroneous, but was
    /// already diagnosed.  Don't emit another error.
    ErrorAlreadyDiagnosed,
    
    /// This result indicates that the lookup produced candidate lists,
    /// potentially of viable results, potentially of error candidates, and
    /// potentially empty lists, indicating that there were no matches.
    HasResults
  } OverallResult;
  
  /// This is a list of viable candidates that were matched.
  ///
  SmallVector<OverloadChoice, 4> ViableCandidates;
  
  /// If there is a favored candidate in the viable list, this indicates its
  /// index.
  unsigned FavoredChoice = ~0U;

  /// The number of optional unwraps that were applied implicitly in the
  /// lookup, for contexts where that is permitted.
  unsigned numImplicitOptionalUnwraps = 0;

  /// The base lookup type used to find the results, which will be non-null
  /// only when it differs from the provided base type.
  Type actualBaseType;

  /// This enum tracks reasons why a candidate is not viable.
  enum UnviableReason {
    /// This uses a type like Self in its signature that cannot be used on an
    /// existential box.
    UR_UnavailableInExistential,

    /// This is an instance member being accessed through something of metatype
    /// type.
    UR_InstanceMemberOnType,

    /// This is a static/class member being accessed through an instance.
    UR_TypeMemberOnInstance,

    /// This is a mutating member, being used on an rvalue.
    UR_MutatingMemberOnRValue,

    /// The getter for this subscript or computed property is mutating and we
    /// only have an rvalue base.  This is more specific than the former one.
    UR_MutatingGetterOnRValue,

    /// The member is inaccessible (e.g. a private member in another file).
    UR_Inaccessible,

    /// This is a `WritableKeyPath` being used to look up read-only member,
    /// used in situations involving dynamic member lookup via keypath,
    /// because it's not known upfront what access capability would the
    /// member have.
    UR_WritableKeyPathOnReadOnlyMember,

    /// This is a `ReferenceWritableKeyPath` being used to look up mutating
    /// member, used in situations involving dynamic member lookup via keypath,
    /// because it's not known upfront what access capability would the
    /// member have.
    UR_ReferenceWritableKeyPathOnMutatingMember,

    /// This is a KeyPath whose root type is AnyObject
    UR_KeyPathWithAnyObjectRootType
  };

  /// This is a list of considered (but rejected) candidates, along with a
  /// reason for their rejection. Split into separate collections to make
  /// it easier to use in conjunction with viable candidates.
  SmallVector<OverloadChoice, 4> UnviableCandidates;
  SmallVector<UnviableReason, 4> UnviableReasons;

  /// Mark this as being an already-diagnosed error and return itself.
  MemberLookupResult &markErrorAlreadyDiagnosed() {
    OverallResult = ErrorAlreadyDiagnosed;
    return *this;
  }
  
  void addViable(OverloadChoice candidate) {
    ViableCandidates.push_back(candidate);
  }
  
  void addUnviable(OverloadChoice candidate, UnviableReason reason) {
    UnviableCandidates.push_back(candidate);
    UnviableReasons.push_back(reason);
  }

  Optional<unsigned> getFavoredIndex() const {
    return (FavoredChoice == ~0U) ? Optional<unsigned>() : FavoredChoice;
  }
};

/// Stores the required methods for @dynamicCallable types.
struct DynamicCallableMethods {
  llvm::DenseSet<FuncDecl *> argumentsMethods;
  llvm::DenseSet<FuncDecl *> keywordArgumentsMethods;

  void addArgumentsMethod(FuncDecl *method) {
    argumentsMethods.insert(method);
  }

  void addKeywordArgumentsMethod(FuncDecl *method) {
    keywordArgumentsMethods.insert(method);
  }

  /// Returns true if type defines either of the @dynamicCallable
  /// required methods. Returns false iff type does not satisfy @dynamicCallable
  /// requirements.
  bool isValid() const {
    return !argumentsMethods.empty() || !keywordArgumentsMethods.empty();
  }
};

/// Describes the target to which a constraint system's solution can be
/// applied.
class SolutionApplicationTarget {
public:
  enum class Kind {
    expression,
    function,
    stmtCondition,
    caseLabelItem,
    patternBinding,
    uninitializedWrappedVar,
  } kind;

private:
  union {
    struct {
      /// The expression being type-checked.
      Expr *expression;

      /// The declaration context in which the expression is being
      /// type-checked.
      DeclContext *dc;

      /// The purpose of the contextual type.
      ContextualTypePurpose contextualPurpose;

      /// The type to which the expression should be converted.
      TypeLoc convertType;

      /// When initializing a pattern from the expression, this is the
      /// pattern.
      Pattern *pattern;

      struct {
        /// The variable to which property wrappers have been applied, if
        /// this is an initialization involving a property wrapper.
        VarDecl *wrappedVar;

        /// The innermost call to \c init(wrappedValue:), if this is an
        /// initialization involving a property wrapper.
        ApplyExpr *innermostWrappedValueInit;

        /// Whether this property wrapper has an initial wrapped value specified
        /// via \c = .
        bool hasInitialWrappedValue;
      } propertyWrapper;

      /// Whether the expression result will be discarded at the end.
      bool isDiscarded;

      /// Whether to bind the variables encountered within the pattern to
      /// fresh type variables via one-way constraints.
      bool bindPatternVarsOneWay;

      union {
        struct {
          /// The pattern binding declaration for an initialization, if any.
          PatternBindingDecl *patternBinding;

          /// The index into the pattern binding declaration, if any.
          unsigned patternBindingIndex;
        } initialization;

        ForEachStmtInfo forEachStmt;
      };
    } expression;

    struct {
      AnyFunctionRef function;
      BraceStmt *body;
    } function;

    struct {
      StmtCondition stmtCondition;
      DeclContext *dc;
    } stmtCondition;

    struct {
      CaseLabelItem *caseLabelItem;
      DeclContext *dc;
    } caseLabelItem;

    PatternBindingDecl *patternBinding;

    VarDecl *uninitializedWrappedVar;
  };

  // If the pattern contains a single variable that has an attached
  // property wrapper, set up the initializer expression to initialize
  // the backing storage.
  void maybeApplyPropertyWrapper();

public:
  SolutionApplicationTarget(Expr *expr, DeclContext *dc,
                            ContextualTypePurpose contextualPurpose,
                            Type convertType, bool isDiscarded)
      : SolutionApplicationTarget(expr, dc, contextualPurpose,
                                  TypeLoc::withoutLoc(convertType),
                                  isDiscarded) { }

  SolutionApplicationTarget(Expr *expr, DeclContext *dc,
                            ContextualTypePurpose contextualPurpose,
                            TypeLoc convertType, bool isDiscarded);

  SolutionApplicationTarget(AnyFunctionRef fn)
      : SolutionApplicationTarget(fn, fn.getBody()) { }

  SolutionApplicationTarget(StmtCondition stmtCondition, DeclContext *dc) {
    kind = Kind::stmtCondition;
    this->stmtCondition.stmtCondition = stmtCondition;
    this->stmtCondition.dc = dc;
  }

  SolutionApplicationTarget(AnyFunctionRef fn, BraceStmt *body) {
    kind = Kind::function;
    function.function = fn;
    function.body = body;
  }

  SolutionApplicationTarget(CaseLabelItem *caseLabelItem, DeclContext *dc) {
    kind = Kind::caseLabelItem;
    this->caseLabelItem.caseLabelItem = caseLabelItem;
    this->caseLabelItem.dc = dc;
  }

  SolutionApplicationTarget(PatternBindingDecl *patternBinding) {
    kind = Kind::patternBinding;
    this->patternBinding = patternBinding;
  }

  SolutionApplicationTarget(VarDecl *wrappedVar) {
    kind = Kind::uninitializedWrappedVar;
    this->uninitializedWrappedVar= wrappedVar;
  }

  /// Form a target for the initialization of a pattern from an expression.
  static SolutionApplicationTarget forInitialization(
      Expr *initializer, DeclContext *dc, Type patternType, Pattern *pattern,
      bool bindPatternVarsOneWay);

  /// Form a target for the initialization of a pattern binding entry from
  /// an expression.
  static SolutionApplicationTarget forInitialization(
      Expr *initializer, DeclContext *dc, Type patternType,
      PatternBindingDecl *patternBinding, unsigned patternBindingIndex,
      bool bindPatternVarsOneWay);

  /// Form a target for a for-each loop.
  static SolutionApplicationTarget forForEachStmt(
      ForEachStmt *stmt, ProtocolDecl *sequenceProto, DeclContext *dc,
      bool bindPatternVarsOneWay);

  /// Form a target for a property with an attached property wrapper that is
  /// initialized out-of-line.
  static SolutionApplicationTarget forUninitializedWrappedVar(
      VarDecl *wrappedVar);

  Expr *getAsExpr() const {
    switch (kind) {
    case Kind::expression:
      return expression.expression;

    case Kind::function:
    case Kind::stmtCondition:
    case Kind::caseLabelItem:
    case Kind::patternBinding:
    case Kind::uninitializedWrappedVar:
      return nullptr;
    }
    llvm_unreachable("invalid expression type");
  }

  DeclContext *getDeclContext() const {
    switch (kind) {
    case Kind::expression:
      return expression.dc;

    case Kind::function:
      return function.function.getAsDeclContext();

    case Kind::stmtCondition:
      return stmtCondition.dc;

    case Kind::caseLabelItem:
      return caseLabelItem.dc;

    case Kind::patternBinding:
      return patternBinding->getDeclContext();

    case Kind::uninitializedWrappedVar:
      return uninitializedWrappedVar->getDeclContext();
    }
    llvm_unreachable("invalid decl context type");
  }

  ContextualTypePurpose getExprContextualTypePurpose() const {
    assert(kind == Kind::expression);
    return expression.contextualPurpose;
  }

  Type getExprContextualType() const {
    return getExprContextualTypeLoc().getType();
  }

  TypeLoc getExprContextualTypeLoc() const {
    assert(kind == Kind::expression);

    // For an @autoclosure parameter, the conversion type is
    // the result of the function type.
    if (FunctionType *autoclosureParamType = getAsAutoclosureParamType()) {
      return TypeLoc(expression.convertType.getTypeRepr(),
                     autoclosureParamType->getResult());
    }

    return expression.convertType;
  }

  /// Retrieve the type to which an expression should be converted, or
  /// a NULL type if no conversion constraint should be generated.
  Type getExprConversionType() const {
    if (contextualTypeIsOnlyAHint())
      return Type();
    return getExprContextualType();
  }

  /// Returns the autoclosure parameter type, or \c nullptr if the
  /// expression has a different kind of context.
  FunctionType *getAsAutoclosureParamType() const {
    assert(kind == Kind::expression);
    if (expression.contextualPurpose == CTP_AutoclosureDefaultParameter)
      return expression.convertType.getType()->castTo<FunctionType>();
    return nullptr;
  }

  void setExprConversionType(Type type) {
    assert(kind == Kind::expression);
    expression.convertType = TypeLoc::withoutLoc(type);
  }

  void setExprConversionTypeLoc(TypeLoc type) {
    assert(kind == Kind::expression);
    expression.convertType = type;
  }

  /// For a pattern initialization target, retrieve the pattern.
  Pattern *getInitializationPattern() const {
    assert(kind == Kind::expression);
    assert(expression.contextualPurpose == CTP_Initialization);
    return expression.pattern;
  }

  /// For a pattern initialization target, retrieve the contextual pattern.
  ContextualPattern getContextualPattern() const;

  /// Whether this target is for a for-in statement.
  bool isForEachStmt() const {
    return kind == Kind::expression &&
           getExprContextualTypePurpose() == CTP_ForEachStmt;
  }

  /// Whether this is an initialization for an Optional.Some pattern.
  bool isOptionalSomePatternInit() const {
    return kind == Kind::expression &&
        expression.contextualPurpose == CTP_Initialization &&
        isa<OptionalSomePattern>(expression.pattern) &&
        !expression.pattern->isImplicit();
  }

  /// Whether to bind the types of any variables within the pattern via
  /// one-way constraints.
  bool shouldBindPatternVarsOneWay() const {
    return kind == Kind::expression && expression.bindPatternVarsOneWay;
  }

  /// Whether or not an opaque value placeholder should be injected into the
  /// first \c wrappedValue argument of an apply expression.
  bool shouldInjectWrappedValuePlaceholder(ApplyExpr *apply) const {
    if (kind != Kind::expression ||
        expression.contextualPurpose != CTP_Initialization)
      return false;

    auto *wrappedVar = expression.propertyWrapper.wrappedVar;
    if (!apply || !wrappedVar || wrappedVar->isStatic())
      return false;

    return expression.propertyWrapper.innermostWrappedValueInit == apply;
  }

  /// Whether this target is for initialization of a property wrapper
  /// with an initial wrapped value specified via \c = .
  bool propertyWrapperHasInitialWrappedValue() const {
    return (kind == Kind::expression &&
            expression.propertyWrapper.hasInitialWrappedValue);
  }

  /// Retrieve the wrapped variable when initializing a pattern with a
  /// property wrapper.
  VarDecl *getInitializationWrappedVar() const {
    assert(kind == Kind::expression);
    assert(expression.contextualPurpose == CTP_Initialization);
    return expression.propertyWrapper.wrappedVar;
  }

  PatternBindingDecl *getInitializationPatternBindingDecl() const {
    assert(kind == Kind::expression);
    assert(expression.contextualPurpose == CTP_Initialization);
    return expression.initialization.patternBinding;
  }

  unsigned getInitializationPatternBindingIndex() const {
    assert(kind == Kind::expression);
    assert(expression.contextualPurpose == CTP_Initialization);
    return expression.initialization.patternBindingIndex;
  }

  const ForEachStmtInfo &getForEachStmtInfo() const {
    assert(isForEachStmt());
    return expression.forEachStmt;
  }

  ForEachStmtInfo &getForEachStmtInfo() {
    assert(isForEachStmt());
    return expression.forEachStmt;
  }

  /// Whether this context infers an opaque return type.
  bool infersOpaqueReturnType() const;

  /// Whether the contextual type is only a hint, rather than a type
  bool contextualTypeIsOnlyAHint() const;

  bool isDiscardedExpr() const {
    assert(kind == Kind::expression);
    return expression.isDiscarded;
  }

  void setExpr(Expr *expr) {
    assert(kind == Kind::expression);
    expression.expression = expr;
  }

  void setPattern(Pattern *pattern) {
    assert(kind == Kind::expression);
    assert(expression.contextualPurpose == CTP_Initialization ||
           expression.contextualPurpose == CTP_ForEachStmt);
    expression.pattern = pattern;
  }

  Optional<AnyFunctionRef> getAsFunction() const {
    switch (kind) {
    case Kind::expression:
    case Kind::stmtCondition:
    case Kind::caseLabelItem:
    case Kind::patternBinding:
    case Kind::uninitializedWrappedVar:
      return None;

    case Kind::function:
      return function.function;
    }
    llvm_unreachable("invalid function kind");
  }

  Optional<StmtCondition> getAsStmtCondition() const {
    switch (kind) {
    case Kind::expression:
    case Kind::function:
    case Kind::caseLabelItem:
    case Kind::patternBinding:
    case Kind::uninitializedWrappedVar:
      return None;

    case Kind::stmtCondition:
      return stmtCondition.stmtCondition;
    }
    llvm_unreachable("invalid statement kind");
  }

  Optional<CaseLabelItem *> getAsCaseLabelItem() const {
    switch (kind) {
    case Kind::expression:
    case Kind::function:
    case Kind::stmtCondition:
    case Kind::patternBinding:
    case Kind::uninitializedWrappedVar:
      return None;

    case Kind::caseLabelItem:
      return caseLabelItem.caseLabelItem;
    }
    llvm_unreachable("invalid case label type");
  }

  PatternBindingDecl *getAsPatternBinding() const {
    switch (kind) {
    case Kind::expression:
    case Kind::function:
    case Kind::stmtCondition:
    case Kind::caseLabelItem:
    case Kind::uninitializedWrappedVar:
      return nullptr;

    case Kind::patternBinding:
      return patternBinding;
    }
    llvm_unreachable("invalid case label type");
  }

  VarDecl *getAsUninitializedWrappedVar() const {
    switch (kind) {
    case Kind::expression:
    case Kind::function:
    case Kind::stmtCondition:
    case Kind::caseLabelItem:
    case Kind::patternBinding:
      return nullptr;

    case Kind::uninitializedWrappedVar:
      return uninitializedWrappedVar;
    }
    llvm_unreachable("invalid case label type");
  }

  BraceStmt *getFunctionBody() const {
    assert(kind == Kind::function);
    return function.body;
  }

  void setFunctionBody(BraceStmt *stmt) {
    assert(kind == Kind::function);
    function.body = stmt;
  }

  /// Retrieve the source range of the target.
  SourceRange getSourceRange() const {
    switch (kind) {
    case Kind::expression:
      return expression.expression->getSourceRange();

    case Kind::function:
      return function.body->getSourceRange();

    case Kind::stmtCondition:
      return SourceRange(stmtCondition.stmtCondition.front().getStartLoc(),
                         stmtCondition.stmtCondition.back().getEndLoc());

    case Kind::caseLabelItem:
      return caseLabelItem.caseLabelItem->getSourceRange();

    case Kind::patternBinding:
      return patternBinding->getSourceRange();

    case Kind::uninitializedWrappedVar:
      return uninitializedWrappedVar->getSourceRange();
    }
    llvm_unreachable("invalid target type");
  }

  /// Retrieve the source location for the target.
  SourceLoc getLoc() const {
    switch (kind) {
    case Kind::expression:
      return expression.expression->getLoc();

    case Kind::function:
      return function.function.getLoc();

    case Kind::stmtCondition:
      return stmtCondition.stmtCondition.front().getStartLoc();

    case Kind::caseLabelItem:
      return caseLabelItem.caseLabelItem->getStartLoc();

    case Kind::patternBinding:
      return patternBinding->getLoc();

    case Kind::uninitializedWrappedVar:
      return uninitializedWrappedVar->getLoc();
    }
    llvm_unreachable("invalid target type");
  }

  /// Walk the contents of the application target.
  SolutionApplicationTarget walk(ASTWalker &walker);
};

/// A function that rewrites a solution application target in the context
/// of solution application.
using RewriteTargetFn = std::function<
    Optional<SolutionApplicationTarget> (SolutionApplicationTarget)>;

enum class ConstraintSystemPhase {
  ConstraintGeneration,
  Solving,
  Diagnostics,
  Finalization
};

/// Describes the result of applying a solution to a given function.
enum class SolutionApplicationToFunctionResult {
  /// Application of the solution succeeded.
  Success,
  /// Application of the solution failed.
  /// TODO: This should probably go away entirely.
  Failure,
  /// The solution could not be applied immediately, and type checking for
  /// this function should be delayed until later.
  Delay,
};

/// Describes a system of constraints on type variables, the
/// solution of which assigns concrete types to each of the type variables.
/// Constraint systems are typically generated given an (untyped) expression.
class ConstraintSystem {
  ASTContext &Context;

  friend class swift::unittest::SemaTest;

public:
  DeclContext *DC;
  ConstraintSystemOptions Options;
  Optional<ExpressionTimer> Timer;

  friend class Solution;
  friend class ConstraintFix;
  friend class OverloadChoice;
  friend class ConstraintGraph;
  friend class DisjunctionChoice;
  friend class Component;
  friend class FailureDiagnostic;
  friend class TypeVarBindingProducer;
  friend class TypeVariableBinding;
  friend class StepScope;
  friend class SolverStep;
  friend class SplitterStep;
  friend class ComponentStep;
  friend class TypeVariableStep;
  friend class RequirementFailure;
  friend class MissingMemberFailure;

  class SolverScope;

  /// Expressions that are known to be unevaluated.
  /// Note: this is only used to support ObjCSelectorExpr at the moment.
  llvm::SmallPtrSet<Expr *, 2> UnevaluatedRootExprs;

  /// The total number of disjunctions created.
  unsigned CountDisjunctions = 0;

private:
  /// A constraint that has failed along the current solver path.
  /// Do not set directly, call \c recordFailedConstraint instead.
  Constraint *failedConstraint = nullptr;

  /// Current phase of the constraint system lifetime.
  ConstraintSystemPhase Phase = ConstraintSystemPhase::ConstraintGeneration;

  /// The set of expressions for which we have generated constraints.
  llvm::SetVector<Expr *> InputExprs;

  /// The number of input expressions whose parents and depths have
  /// been entered into \c ExprWeights.
  unsigned NumInputExprsInWeights = 0;

  llvm::DenseMap<Expr *, std::pair<unsigned, Expr *>> ExprWeights;

  /// Allocator used for all of the related constraint systems.
  llvm::BumpPtrAllocator Allocator;

  /// Arena used for memory management of constraint-checker-related
  /// allocations.
  ConstraintCheckerArenaRAII Arena;

  /// Counter for type variables introduced.
  unsigned TypeCounter = 0;

  /// The number of scopes created so far during the solution
  /// of this constraint system.
  ///
  /// This is a measure of complexity of the solution space. A new
  /// scope is created every time we attempt a type variable binding
  /// or explore an option in a disjunction.
  unsigned CountScopes = 0;

  /// High-water mark of measured memory usage in any sub-scope we
  /// explored.
  size_t MaxMemory = 0;

  /// Cached member lookups.
  llvm::DenseMap<std::pair<Type, DeclNameRef>, Optional<LookupResult>>
    MemberLookups;

  /// Cached sets of "alternative" literal types.
  static const unsigned NumAlternativeLiteralTypes = 13;
  Optional<ArrayRef<Type>> AlternativeLiteralTypes[NumAlternativeLiteralTypes];

  /// Folding set containing all of the locators used in this
  /// constraint system.
  llvm::FoldingSetVector<ConstraintLocator> ConstraintLocators;

  /// The overload sets that have been resolved along the current path.
  llvm::MapVector<ConstraintLocator *, SelectedOverload> ResolvedOverloads;

  /// The current fixed score for this constraint system and the (partial)
  /// solution it represents.
  Score CurrentScore;

  llvm::SetVector<TypeVariableType *> TypeVariables;

  /// Maps expressions to types for choosing a favored overload
  /// type in a disjunction constraint.
  llvm::DenseMap<Expr *, TypeBase *> FavoredTypes;

  /// Maps discovered closures to their types inferred
  /// from declared parameters/result and body.
  llvm::MapVector<const ClosureExpr *, FunctionType *> ClosureTypes;

  /// This is a *global* list of all result builder bodies that have
  /// been determined to be incorrect by failing constraint generation.
  ///
  /// Tracking this information is useful to avoid producing duplicate
  /// diagnostics when result builder has multiple overloads.
  llvm::SmallDenseSet<AnyFunctionRef> InvalidResultBuilderBodies;

  /// Maps node types used within all portions of the constraint
  /// system, instead of directly using the types on the
  /// nodes themselves. This allows us to typecheck and
  /// run through various diagnostics passes without actually mutating
  /// the types on the nodes.
  llvm::MapVector<ASTNode, Type> NodeTypes;
  llvm::DenseMap<std::pair<const KeyPathExpr *, unsigned>, TypeBase *>
      KeyPathComponentTypes;

  /// Maps AST entries to their solution application targets.
  llvm::MapVector<SolutionApplicationTargetsKey, SolutionApplicationTarget>
    solutionApplicationTargets;

  /// Contextual type information for expressions that are part of this
  /// constraint system.
  llvm::MapVector<ASTNode, ContextualTypeInfo> contextualTypes;

  /// Information about each case label item tracked by the constraint system.
  llvm::SmallMapVector<const CaseLabelItem *, CaseLabelItemInfo, 4>
      caseLabelItems;

  /// Maps closure parameters to type variables.
  llvm::DenseMap<const ParamDecl *, TypeVariableType *>
    OpenedParameterTypes;

  /// The set of constraint restrictions used to reach the
  /// current constraint system.
  ///
  /// Constraint restrictions help describe which path the solver took when
  /// there are multiple ways in which one type could convert to another, e.g.,
  /// given class types A and B, the solver might choose either a superclass
  /// conversion or a user-defined conversion.
  std::vector<std::tuple<Type, Type, ConversionRestrictionKind>>
      ConstraintRestrictions;

  /// The set of fixes applied to make the solution work.
  llvm::SmallVector<ConstraintFix *, 4> Fixes;

  /// The set of remembered disjunction choices used to reach
  /// the current constraint system.
  std::vector<std::pair<ConstraintLocator*, unsigned>>
      DisjunctionChoices;

  /// For locators associated with call expressions, the trailing closure
  /// matching rule that was applied.
  std::vector<std::pair<ConstraintLocator*, TrailingClosureMatching>>
      trailingClosureMatchingChoices;

  /// The worklist of "active" constraints that should be revisited
  /// due to a change.
  ConstraintList ActiveConstraints;

  /// The list of "inactive" constraints that still need to be solved,
  /// but will not be revisited until one of their inputs changes.
  ConstraintList InactiveConstraints;

  /// The constraint graph.
  ConstraintGraph &CG;

  /// A mapping from constraint locators to the set of opened types associated
  /// with that locator.
  SmallVector<std::pair<ConstraintLocator *, ArrayRef<OpenedType>>, 4>
    OpenedTypes;

  /// The list of all generic requirements fixed along the current
  /// solver path.
  using FixedRequirement =
      std::tuple<GenericTypeParamType *, unsigned, TypeBase *>;
  llvm::SmallSetVector<FixedRequirement, 4> FixedRequirements;

  bool isFixedRequirement(ConstraintLocator *reqLocator, Type requirementTy);
  void recordFixedRequirement(ConstraintLocator *reqLocator,
                              Type requirementTy);

  /// A mapping from constraint locators to the opened existential archetype
  /// used for the 'self' of an existential type.
  SmallVector<std::pair<ConstraintLocator *, OpenedArchetypeType *>, 4>
    OpenedExistentialTypes;

  /// The nodes for which we have produced types, along with the prior type
  /// each node had before introducing this type.
  llvm::SmallVector<std::pair<ASTNode, Type>, 8> addedNodeTypes;

  std::vector<std::pair<ConstraintLocator *, ProtocolConformanceRef>>
      CheckedConformances;

  /// The set of functions that have been transformed by a result builder.
  std::vector<std::pair<AnyFunctionRef, AppliedBuilderTransform>>
      resultBuilderTransformed;

  /// Cache of the effects any closures visited.
  llvm::SmallDenseMap<ClosureExpr *, FunctionType::ExtInfo, 4> closureEffectsCache;

public:
  /// The locators of \c Defaultable constraints whose defaults were used.
  std::vector<ConstraintLocator *> DefaultedConstraints;

  /// A cache that stores the @dynamicCallable required methods implemented by
  /// types.
  llvm::DenseMap<CanType, DynamicCallableMethods> DynamicCallableCache;

private:
  /// Describe the candidate expression for partial solving.
  /// This class used by shrink & solve methods which apply
  /// variation of directional path consistency algorithm in attempt
  /// to reduce scopes of the overload sets (disjunctions) in the system.
  class Candidate {
    Expr *E;
    DeclContext *DC;
    llvm::BumpPtrAllocator &Allocator;

    // Contextual Information.
    Type CT;
    ContextualTypePurpose CTP;

  public:
    Candidate(ConstraintSystem &cs, Expr *expr, Type ct = Type(),
              ContextualTypePurpose ctp = ContextualTypePurpose::CTP_Unused)
        : E(expr), DC(cs.DC), Allocator(cs.Allocator), CT(ct), CTP(ctp) {}

    /// Return underlying expression.
    Expr *getExpr() const { return E; }

    /// Try to solve this candidate sub-expression
    /// and re-write it's OSR domains afterwards.
    ///
    /// \param shrunkExprs The set of expressions which
    /// domains have been successfully shrunk so far.
    ///
    /// \returns true on solver failure, false otherwise.
    bool solve(llvm::SmallDenseSet<OverloadSetRefExpr *> &shrunkExprs);

    /// Apply solutions found by solver as reduced OSR sets for
    /// for current and all of it's sub-expressions.
    ///
    /// \param solutions The solutions found by running solver on the
    /// this candidate expression.
    ///
    /// \param shrunkExprs The set of expressions which
    /// domains have been successfully shrunk so far.
    void applySolutions(
        llvm::SmallVectorImpl<Solution> &solutions,
        llvm::SmallDenseSet<OverloadSetRefExpr *> &shrunkExprs) const;

    /// Check if attempt at solving of the candidate makes sense given
    /// the current conditions - number of shrunk domains which is related
    /// to the given candidate over the total number of disjunctions present.
    static bool
    isTooComplexGiven(ConstraintSystem *const cs,
                      llvm::SmallDenseSet<OverloadSetRefExpr *> &shrunkExprs) {
      SmallVector<Constraint *, 8> disjunctions;
      cs->collectDisjunctions(disjunctions);

      unsigned unsolvedDisjunctions = disjunctions.size();
      for (auto *disjunction : disjunctions) {
        auto *locator = disjunction->getLocator();
        if (!locator)
          continue;

        if (auto *OSR = getAsExpr<OverloadSetRefExpr>(locator->getAnchor())) {
          if (shrunkExprs.count(OSR) > 0)
            --unsolvedDisjunctions;
        }
      }

      unsigned threshold =
          cs->getASTContext().TypeCheckerOpts.SolverShrinkUnsolvedThreshold;
      return unsolvedDisjunctions >= threshold;
    }
  };

  /// Describes the current solver state.
  struct SolverState {
    SolverState(ConstraintSystem &cs,
                FreeTypeVariableBinding allowFreeTypeVariables);
    ~SolverState();

    /// The constraint system.
    ConstraintSystem &CS;

    FreeTypeVariableBinding AllowFreeTypeVariables;

    /// Depth of the solution stack.
    unsigned depth = 0;

    /// Maximum depth reached so far in exploring solutions.
    unsigned maxDepth = 0;

    /// Whether to record failures or not.
    bool recordFixes = false;

    /// The set of type variable bindings that have changed while
    /// processing this constraint system.
    SavedTypeVariableBindings savedBindings;

     /// The best solution computed so far.
    Optional<Score> BestScore;

    /// The number of the solution attempt we're looking at.
    unsigned SolutionAttempt;

    /// Refers to the innermost partial solution scope.
    SolverScope *PartialSolutionScope = nullptr;

    // Statistics
    #define CS_STATISTIC(Name, Description) unsigned Name = 0;
    #include "ConstraintSolverStats.def"

    /// Check whether there are any retired constraints present.
    bool hasRetiredConstraints() const {
      return !retiredConstraints.empty();
    }

    /// Mark given constraint as retired along current solver path.
    ///
    /// \param constraint The constraint to retire temporarily.
    void retireConstraint(Constraint *constraint) {
      retiredConstraints.push_front(constraint);
    }

    /// Iterate over all of the retired constraints registered with
    /// current solver state.
    ///
    /// \param processor The processor function to be applied to each of
    /// the constraints retrieved.
    void forEachRetired(llvm::function_ref<void(Constraint &)> processor) {
      for (auto &constraint : retiredConstraints)
        processor(constraint);
    }

    /// Add new "generated" constraint along the current solver path.
    ///
    /// \param constraint The newly generated constraint.
    void addGeneratedConstraint(Constraint *constraint) {
      assert(constraint && "Null generated constraint?");
      generatedConstraints.push_back(constraint);
    }

    /// Register given scope to be tracked by the current solver state,
    /// this helps to make sure that all of the retired/generated constraints
    /// are dealt with correctly when the life time of the scope ends.
    ///
    /// \param scope The scope to associate with current solver state.
    void registerScope(SolverScope *scope) {
      ++depth;
      maxDepth = std::max(maxDepth, depth);
      scope->scopeNumber = NumStatesExplored++;

      CS.incrementScopeCounter();
      auto scopeInfo =
        std::make_tuple(scope, retiredConstraints.begin(),
                        generatedConstraints.size());
      scopes.push_back(scopeInfo);
    }

    /// Restore all of the retired/generated constraints to the state
    /// before given scope. This is required because retired constraints have
    /// to be re-introduced to the system in order of arrival (LIFO) and list
    /// of the generated constraints has to be truncated back to the
    /// original size.
    ///
    /// \param scope The solver scope to rollback.
    void rollback(SolverScope *scope) {
      --depth;

      unsigned countScopesExplored = NumStatesExplored - scope->scopeNumber;
      if (countScopesExplored == 1)
        CS.incrementLeafScopes();

      SolverScope *savedScope;
      // The position of last retired constraint before given scope.
      ConstraintList::iterator lastRetiredPos;
      // The original number of generated constraints before given scope.
      unsigned numGenerated;

      std::tie(savedScope, lastRetiredPos, numGenerated) =
        scopes.pop_back_val();

      assert(savedScope == scope && "Scope rollback not in LIFO order!");

      // Restore all of the retired constraints.
      CS.InactiveConstraints.splice(CS.InactiveConstraints.end(),
                                    retiredConstraints,
                                    retiredConstraints.begin(), lastRetiredPos);

      // And remove all of the generated constraints.
      auto genStart = generatedConstraints.begin() + numGenerated,
           genEnd = generatedConstraints.end();
      for (auto genI = genStart; genI != genEnd; ++genI) {
        CS.InactiveConstraints.erase(ConstraintList::iterator(*genI));
      }

      generatedConstraints.erase(genStart, genEnd);

      for (unsigned constraintIdx :
             range(scope->numDisabledConstraints, disabledConstraints.size())) {
        if (disabledConstraints[constraintIdx]->isDisabled())
          disabledConstraints[constraintIdx]->setEnabled();
      }
      disabledConstraints.erase(
          disabledConstraints.begin() + scope->numDisabledConstraints,
          disabledConstraints.end());

      for (unsigned constraintIdx :
             range(scope->numFavoredConstraints, favoredConstraints.size())) {
        if (favoredConstraints[constraintIdx]->isFavored())
          favoredConstraints[constraintIdx]->setFavored(false);
      }
      favoredConstraints.erase(
          favoredConstraints.begin() + scope->numFavoredConstraints,
          favoredConstraints.end());
    }

    /// Check whether constraint system is allowed to form solutions
    /// even with unbound type variables present.
    bool allowsFreeTypeVariables() const {
      return AllowFreeTypeVariables != FreeTypeVariableBinding::Disallow;
    }

    unsigned getNumDisabledConstraints() const {
      return disabledConstraints.size();
    }

    /// Disable the given constraint; this change will be rolled back
    /// when we exit the current solver scope.
    void disableContraint(Constraint *constraint) {
      constraint->setDisabled();
      disabledConstraints.push_back(constraint);
    }

    unsigned getNumFavoredConstraints() const {
      return favoredConstraints.size();
    }

    /// Favor the given constraint; this change will be rolled back
    /// when we exit the current solver scope.
    void favorConstraint(Constraint *constraint) {
      assert(!constraint->isFavored());

      constraint->setFavored();
      favoredConstraints.push_back(constraint);
    }

  private:
    /// The list of constraints that have been retired along the
    /// current path, this list is used in LIFO fashion when constraints
    /// are added back to the circulation.
    ConstraintList retiredConstraints;

    /// The set of constraints which were active at the time of this state
    /// creating, it's used to re-activate them on destruction.
    SmallVector<Constraint *, 4> activeConstraints;

    /// The current set of generated constraints.
    SmallVector<Constraint *, 4> generatedConstraints;

    /// The collection which holds association between solver scope
    /// and position of the last retired constraint and number of
    /// constraints generated before registration of given scope,
    /// this helps to rollback all of the constraints retired/generated
    /// each of the registered scopes correct (LIFO) order.
    llvm::SmallVector<
      std::tuple<SolverScope *, ConstraintList::iterator, unsigned>, 4> scopes;

    SmallVector<Constraint *, 4> disabledConstraints;
    SmallVector<Constraint *, 4> favoredConstraints;
  };

  class CacheExprTypes : public ASTWalker {
    Expr *RootExpr;
    ConstraintSystem &CS;
    bool ExcludeRoot;

  public:
    CacheExprTypes(Expr *expr, ConstraintSystem &cs, bool excludeRoot)
        : RootExpr(expr), CS(cs), ExcludeRoot(excludeRoot) {}

    Expr *walkToExprPost(Expr *expr) override {
      if (ExcludeRoot && expr == RootExpr) {
        assert(!expr->getType() && "Unexpected type in root of expression!");
        return expr;
      }

      if (expr->getType())
        CS.cacheType(expr);

      if (auto kp = dyn_cast<KeyPathExpr>(expr))
        for (auto i : indices(kp->getComponents()))
          if (kp->getComponents()[i].getComponentType())
            CS.cacheType(kp, i);

      return expr;
    }

    /// Ignore statements.
    std::pair<bool, Stmt *> walkToStmtPre(Stmt *stmt) override {
      return { false, stmt };
    }

    /// Ignore declarations.
    bool walkToDeclPre(Decl *decl) override { return false; }
  };

public:
  /// Retrieve the first constraint that has failed along the solver's path, or
  /// \c nullptr if no constraint has failed.
  Constraint *getFailedConstraint() const { return failedConstraint; }

  ConstraintSystemPhase getPhase() const { return Phase; }

  /// Move constraint system to a new phase of its lifetime.
  void setPhase(ConstraintSystemPhase newPhase) {
    if (Phase == newPhase)
      return;

#ifndef NDEBUG
    switch (Phase) {
    case ConstraintSystemPhase::ConstraintGeneration:
      assert(newPhase == ConstraintSystemPhase::Solving);
      break;

    case ConstraintSystemPhase::Solving:
      // We can come back to constraint generation phase while
      // processing result builder body.
      assert(newPhase == ConstraintSystemPhase::ConstraintGeneration ||
             newPhase == ConstraintSystemPhase::Diagnostics ||
             newPhase == ConstraintSystemPhase::Finalization);
      break;

    case ConstraintSystemPhase::Diagnostics:
      assert(newPhase == ConstraintSystemPhase::Solving ||
             newPhase == ConstraintSystemPhase::Finalization);
      break;

    case ConstraintSystemPhase::Finalization:
      assert(newPhase == ConstraintSystemPhase::Diagnostics);
      break;
    }
#endif

    Phase = newPhase;
  }

  /// Cache the types of the given expression and all subexpressions.
  void cacheExprTypes(Expr *expr) {
    bool excludeRoot = false;
    expr->walk(CacheExprTypes(expr, *this, excludeRoot));
  }

  /// Cache the types of the expressions under the given expression
  /// (but not the type of the given expression).
  void cacheSubExprTypes(Expr *expr) {
    bool excludeRoot = true;
    expr->walk(CacheExprTypes(expr, *this, excludeRoot));
  }

  /// The current solver state.
  ///
  /// This will be non-null when we're actively solving the constraint
  /// system, and carries temporary state related to the current path
  /// we're exploring.
  SolverState *solverState = nullptr;

  struct ArgumentInfo {
    ArrayRef<Identifier> Labels;
    Optional<unsigned> UnlabeledTrailingClosureIndex;
  };

  /// A mapping from the constraint locators for references to various
  /// names (e.g., member references, normal name references, possible
  /// constructions) to the argument labels provided in the call to
  /// that locator.
  llvm::DenseMap<ConstraintLocator *, ArgumentInfo> ArgumentInfos;

  /// Form a locator that can be used to retrieve argument information cached in
  /// the constraint system for the callee described by the anchor of the
  /// passed locator.
  ConstraintLocator *getArgumentInfoLocator(ConstraintLocator *locator);

  /// Retrieve the argument info that is associated with a member
  /// reference at the given locator.
  Optional<ArgumentInfo> getArgumentInfo(ConstraintLocator *locator);

  Optional<SelectedOverload>
  findSelectedOverloadFor(ConstraintLocator *locator) const {
    auto result = ResolvedOverloads.find(locator);
    if (result == ResolvedOverloads.end())
      return None;
    return result->second;
  }

  Optional<SelectedOverload> findSelectedOverloadFor(Expr *expr) {
    // Retrieve the callee locator for this expression, making sure not to
    // look through applies in order to ensure we only return the "direct"
    // callee.
    auto *loc = getConstraintLocator(expr);
    auto *calleeLoc = getCalleeLocator(loc, /*lookThroughApply*/ false);
    return findSelectedOverloadFor(calleeLoc);
  }

private:
  unsigned assignTypeVariableID() {
    return TypeCounter++;
  }

  void incrementScopeCounter();
  void incrementLeafScopes();

public:
  /// Introduces a new solver scope, which any changes to the
  /// solver state or constraint system are temporary and will be undone when
  /// this object is destroyed.
  ///
  ///
  class SolverScope {
    ConstraintSystem &cs;

    /// The length of \c TypeVariables.
    unsigned numTypeVariables;

    /// The length of \c SavedBindings.
    unsigned numSavedBindings;

    /// The length of \c ConstraintRestrictions.
    unsigned numConstraintRestrictions;

    /// The length of \c Fixes.
    unsigned numFixes;

    /// The length of \c FixedRequirements.
    unsigned numFixedRequirements;

    /// The length of \c DisjunctionChoices.
    unsigned numDisjunctionChoices;

    /// The length of \c trailingClosureMatchingChoices;
    unsigned numTrailingClosureMatchingChoices;

    /// The length of \c OpenedTypes.
    unsigned numOpenedTypes;

    /// The length of \c OpenedExistentialTypes.
    unsigned numOpenedExistentialTypes;

    /// The length of \c DefaultedConstraints.
    unsigned numDefaultedConstraints;

    unsigned numAddedNodeTypes;

    unsigned numCheckedConformances;

    unsigned numDisabledConstraints;

    unsigned numFavoredConstraints;

    unsigned numResultBuilderTransformed;

    /// The length of \c ResolvedOverloads.
    unsigned numResolvedOverloads;

    /// The length of \c ClosureTypes.
    unsigned numInferredClosureTypes;

    /// The length of \c contextualTypes.
    unsigned numContextualTypes;

    /// The length of \c solutionApplicationTargets.
    unsigned numSolutionApplicationTargets;

    /// The length of \c caseLabelItems.
    unsigned numCaseLabelItems;

    /// The previous score.
    Score PreviousScore;

    /// The scope number of this scope. Set when the scope is registered.
    unsigned scopeNumber = 0;

    /// Constraint graph scope associated with this solver scope.
    ConstraintGraphScope CGScope;

    SolverScope(const SolverScope &) = delete;
    SolverScope &operator=(const SolverScope &) = delete;

    friend class ConstraintSystem;

  public:
    explicit SolverScope(ConstraintSystem &cs);
    ~SolverScope();
  };

  ConstraintSystem(DeclContext *dc,
                   ConstraintSystemOptions options);
  ~ConstraintSystem();

  /// Retrieve the constraint graph associated with this constraint system.
  ConstraintGraph &getConstraintGraph() const { return CG; }

  /// Retrieve the AST context.
  ASTContext &getASTContext() const { return Context; }

  /// Determine whether this constraint system has any free type
  /// variables.
  bool hasFreeTypeVariables();

  /// Check whether constraint solver is running in "debug" mode,
  /// which should output diagnostic information.
  bool isDebugMode() const {
    return Options.contains(ConstraintSystemFlags::DebugConstraints);
  }

private:
  /// Finalize this constraint system; we're done attempting to solve
  /// it.
  ///
  /// \returns the solution.
  Solution finalize();

  /// Apply the given solution to the current constraint system.
  ///
  /// This operation is used to take a solution computed based on some
  /// subset of the constraints and then apply it back to the
  /// constraint system for further exploration.
  void applySolution(const Solution &solution);

  // FIXME: Perhaps these belong on ConstraintSystem itself.
  friend Optional<BraceStmt *>
  swift::TypeChecker::applyResultBuilderBodyTransform(FuncDecl *func,
                                                        Type builderType);

  friend Optional<SolutionApplicationTarget>
  swift::TypeChecker::typeCheckExpression(
      SolutionApplicationTarget &target, OptionSet<TypeCheckExprFlags> options);

  /// Emit the fixes computed as part of the solution, returning true if we were
  /// able to emit an error message, or false if none of the fixits worked out.
  bool applySolutionFixes(const Solution &solution);

  /// If there is more than one viable solution,
  /// attempt to pick the best solution and remove all of the rest.
  ///
  /// \param solutions The set of solutions to filter.
  ///
  /// \param minimize The flag which idicates if the
  /// set of solutions should be filtered even if there is
  /// no single best solution, see `findBestSolution` for
  /// more details.
  void
  filterSolutions(SmallVectorImpl<Solution> &solutions,
                  bool minimize = false) {
    if (solutions.size() < 2)
      return;

    if (auto best = findBestSolution(solutions, minimize)) {
      if (*best != 0)
        solutions[0] = std::move(solutions[*best]);
      solutions.erase(solutions.begin() + 1, solutions.end());
    }
  }

  /// Restore the type variable bindings to what they were before
  /// we attempted to solve this constraint system.
  ///
  /// \param numBindings The number of bindings to restore, from the end of
  /// the saved-binding stack.
  void restoreTypeVariableBindings(unsigned numBindings);

  /// Retrieve the set of saved type variable bindings, if available.
  ///
  /// \returns null when we aren't currently solving the system.
  SavedTypeVariableBindings *getSavedBindings() const {
    return solverState ? &solverState->savedBindings : nullptr;
  }

  /// Add a new type variable that was already created.
  void addTypeVariable(TypeVariableType *typeVar);
  
  /// Add a constraint from the subscript base to the root of the key
  /// path literal to the constraint system.
  void addKeyPathApplicationRootConstraint(Type root, ConstraintLocatorBuilder locator);

public:
  /// Lookup for a member with the given name in the given base type.
  ///
  /// This routine caches the results of member lookups in the top constraint
  /// system, to avoid.
  ///
  /// FIXME: This caching should almost certainly be performed at the
  /// module level, since type checking occurs after import resolution,
  /// and no new names are introduced after that point.
  ///
  /// \returns A reference to the member-lookup result.
  LookupResult &lookupMember(Type base, DeclNameRef name);

  /// Retrieve the set of "alternative" literal types that we'll explore
  /// for a given literal protocol kind.
  ArrayRef<Type> getAlternativeLiteralTypes(KnownProtocolKind kind);

  /// Create a new type variable.
  TypeVariableType *createTypeVariable(ConstraintLocator *locator,
                                       unsigned options);

  /// Retrieve the set of active type variables.
  ArrayRef<TypeVariableType *> getTypeVariables() const {
    return TypeVariables.getArrayRef();
  }

  /// Whether the given type variable is active in the constraint system at
  /// the moment.
  bool isActiveTypeVariable(TypeVariableType *typeVar) const {
    return TypeVariables.count(typeVar) > 0;
  }

  /// Whether the given expression's source range contains the code
  /// completion location.
  bool containsCodeCompletionLoc(Expr *expr) const;

  void setClosureType(const ClosureExpr *closure, FunctionType *type) {
    assert(closure);
    assert(type && "Expected non-null type");
    assert(ClosureTypes.count(closure) == 0 && "Cannot reset closure type");
    ClosureTypes.insert({closure, type});
  }

  FunctionType *getClosureType(const ClosureExpr *closure) const {
    auto result = ClosureTypes.find(closure);
    assert(result != ClosureTypes.end());
    return result->second;
  }

  TypeBase* getFavoredType(Expr *E) {
    assert(E != nullptr);
    return this->FavoredTypes[E];
  }
  void setFavoredType(Expr *E, TypeBase *T) {
    assert(E != nullptr);
    this->FavoredTypes[E] = T;
  }

  /// Set the type in our type map for the given node.
  ///
  /// The side tables are used through the expression type checker to avoid mutating nodes until
  /// we know we have successfully type-checked them.
  void setType(ASTNode node, Type type) {
    assert(!node.isNull() && "Cannot set type information on null node");
    assert(type && "Expected non-null type");

    // Record the type.
    Type &entry = NodeTypes[node];
    Type oldType = entry;
    entry = type;

    // Record the fact that we ascribed a type to this node.
    addedNodeTypes.push_back({node, oldType});
  }

  /// Set the type in our type map for a given expression. The side
  /// map is used throughout the expression type checker in order to
  /// avoid mutating expressions until we know we have successfully
  /// type-checked them.
  void setType(KeyPathExpr *KP, unsigned I, Type T) {
    assert(KP && "Expected non-null key path parameter!");
    assert(T && "Expected non-null type!");
    KeyPathComponentTypes[std::make_pair(KP, I)] = T.getPointer();
  }

  /// Check to see if we have a type for a node.
  bool hasType(ASTNode node) const {
    assert(!node.isNull() && "Expected non-null node");
    return NodeTypes.count(node) > 0;
  }

  bool hasType(const KeyPathExpr *KP, unsigned I) const {
    assert(KP && "Expected non-null key path parameter!");
    return KeyPathComponentTypes.find(std::make_pair(KP, I))
              != KeyPathComponentTypes.end();
  }

  /// Get the type for an node.
  Type getType(ASTNode node) const {
    assert(hasType(node) && "Expected type to have been set!");
    // FIXME: lvalue differences
    //    assert((!E->getType() ||
    //            E->getType()->isEqual(ExprTypes.find(E)->second)) &&
    //           "Mismatched types!");
    return NodeTypes.find(node)->second;
  }

  Type getType(const KeyPathExpr *KP, unsigned I) const {
    assert(hasType(KP, I) && "Expected type to have been set!");
    return KeyPathComponentTypes.find(std::make_pair(KP, I))->second;
  }

  /// Retrieve the type of the node, if known.
  Type getTypeIfAvailable(ASTNode node) const {
    auto known = NodeTypes.find(node);
    if (known == NodeTypes.end())
      return Type();

    return known->second;
  }

  /// Retrieve type type of the given declaration to be used in
  /// constraint system, this is better than calling `getType()`
  /// directly because it accounts of constraint system flags.
  Type getVarType(const VarDecl *var);

  /// Cache the type of the expression argument and return that same
  /// argument.
  template <typename T>
  T *cacheType(T *E) {
    assert(E->getType() && "Expected a type!");
    setType(E, E->getType());
    return E;
  }

  /// Cache the type of the expression argument and return that same
  /// argument.
  KeyPathExpr *cacheType(KeyPathExpr *E, unsigned I) {
    auto componentTy = E->getComponents()[I].getComponentType();
    assert(componentTy && "Expected a type!");
    setType(E, I, componentTy);
    return E;
  }

  void setContextualType(ASTNode node, TypeLoc T,
                         ContextualTypePurpose purpose) {
    assert(bool(node) && "Expected non-null expression!");
    assert(contextualTypes.count(node) == 0 &&
           "Already set this contextual type");
    contextualTypes[node] = {T, purpose};
  }

  Optional<ContextualTypeInfo> getContextualTypeInfo(ASTNode node) const {
    auto known = contextualTypes.find(node);
    if (known == contextualTypes.end())
      return None;
    return known->second;
  }

  Type getContextualType(ASTNode node) const {
    auto result = getContextualTypeInfo(node);
    if (result)
      return result->typeLoc.getType();
    return Type();
  }

  TypeLoc getContextualTypeLoc(ASTNode node) const {
    auto result = getContextualTypeInfo(node);
    if (result)
      return result->typeLoc;
    return TypeLoc();
  }

  ContextualTypePurpose getContextualTypePurpose(ASTNode node) const {
    auto result = getContextualTypeInfo(node);
    if (result)
      return result->purpose;
    return CTP_Unused;
  }

  void setSolutionApplicationTarget(
      SolutionApplicationTargetsKey key, SolutionApplicationTarget target) {
    assert(solutionApplicationTargets.count(key) == 0 &&
           "Already set this solution application target");
    solutionApplicationTargets.insert({key, target});
  }

  Optional<SolutionApplicationTarget> getSolutionApplicationTarget(
      SolutionApplicationTargetsKey key) const {
    auto known = solutionApplicationTargets.find(key);
    if (known == solutionApplicationTargets.end())
      return None;
    return known->second;
  }

  void setCaseLabelItemInfo(const CaseLabelItem *item, CaseLabelItemInfo info) {
    assert(item != nullptr);
    assert(caseLabelItems.count(item) == 0);
    caseLabelItems[item] = info;
  }

  Optional<CaseLabelItemInfo> getCaseLabelItemInfo(
      const CaseLabelItem *item) const {
    auto known = caseLabelItems.find(item);
    if (known == caseLabelItems.end())
      return None;

    return known->second;
  }

  /// Retrieve the constraint locator for the given anchor and
  /// path, uniqued.
  ConstraintLocator *
  getConstraintLocator(ASTNode anchor,
                       ArrayRef<ConstraintLocator::PathElement> path,
                       unsigned summaryFlags);

  /// Retrive the constraint locator for the given anchor and
  /// path, uniqued and automatically infer the summary flags
  ConstraintLocator *
  getConstraintLocator(ASTNode anchor,
                       ArrayRef<ConstraintLocator::PathElement> path);

  /// Retrieve the constraint locator for the given anchor and
  /// an empty path, uniqued.
  ConstraintLocator *getConstraintLocator(ASTNode anchor) {
    return getConstraintLocator(anchor, {}, 0);
  }

  /// Retrieve the constraint locator for the given anchor and
  /// path element.
  ConstraintLocator *
  getConstraintLocator(ASTNode anchor, ConstraintLocator::PathElement pathElt) {
    return getConstraintLocator(anchor, llvm::makeArrayRef(pathElt),
                                pathElt.getNewSummaryFlags());
  }

  /// Extend the given constraint locator with a path element.
  ConstraintLocator *
  getConstraintLocator(ConstraintLocator *locator,
                       ConstraintLocator::PathElement pathElt) {
    ConstraintLocatorBuilder builder(locator);
    return getConstraintLocator(builder.withPathElement(pathElt));
  }

  /// Extend the given constraint locator with an array of path elements.
  ConstraintLocator *
  getConstraintLocator(ConstraintLocator *locator,
                       ArrayRef<ConstraintLocator::PathElement> newElts);

  /// Retrieve the locator described by a given builder extended by an array of
  /// path elements.
  ConstraintLocator *
  getConstraintLocator(const ConstraintLocatorBuilder &builder,
                       ArrayRef<ConstraintLocator::PathElement> newElts);

  /// Retrieve the constraint locator described by the given
  /// builder.
  ConstraintLocator *
  getConstraintLocator(const ConstraintLocatorBuilder &builder);

  /// Lookup and return parent associated with given expression.
  Expr *getParentExpr(Expr *expr) {
    if (auto result = getExprDepthAndParent(expr))
      return result->second;
    return nullptr;
  }

  /// Retrieve the depth of the given expression.
  Optional<unsigned> getExprDepth(Expr *expr) {
    if (auto result = getExprDepthAndParent(expr))
      return result->first;
    return None;
  }

  /// Retrieve the depth and parent expression of the given expression.
  Optional<std::pair<unsigned, Expr *>> getExprDepthAndParent(Expr *expr);

  /// Returns a locator describing the callee for the anchor of a given locator.
  ///
  /// - For an unresolved dot/member anchor, this will be a locator describing
  /// the member.
  ///
  /// - For a subscript anchor, this will be a locator describing the subscript
  /// member.
  ///
  /// - For a key path anchor with a property/subscript component path element,
  /// this will be a locator describing the decl referenced by the component.
  ///
  /// - For a function application anchor, this will be a locator describing the
  /// 'direct callee' of the call. For example, for the expression \c x.foo?()
  /// the returned locator will describe the member \c foo.
  ///
  /// Note that because this function deals with the anchor, given a locator
  /// anchored on \c functionA(functionB()) with path elements pointing to the
  /// argument \c functionB(), the returned callee locator will describe
  /// \c functionA rather than \c functionB.
  ///
  /// \param locator The input locator.
  /// \param lookThroughApply Whether to look through applies. If false, a
  /// callee locator will only be returned for a direct reference such as
  /// \c x.foo rather than \c x.foo().
  /// \param getType The callback to fetch a type for given expression.
  /// \param simplifyType The callback to attempt to resolve any type
  ///                     variables which appear in the given type.
  /// \param getOverloadFor The callback to fetch overload for a given
  ///                       locator if available.
  ConstraintLocator *getCalleeLocator(
      ConstraintLocator *locator, bool lookThroughApply,
      llvm::function_ref<Type(Expr *)> getType,