blob: f2d9ae067dca0b98762499a9767d9e75b452874e [file] [log] [blame]
//===--- ConstraintSystem.h - Constraint-based Type Checking ----*- C++ -*-===//
// This source file is part of the 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 for license information
// See 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.
#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);
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_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.
/// Allow the free type variables to persist in the solution.
/// Bind the type variables to UnresolvedType to represent the ambiguity.
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.
/// Match a trailing closure to the last parameter.
/// 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;
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;
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;
ExpressionTimer(Expr *E, ConstraintSystem &CS);
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;
/// 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 (!<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) {
/// 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-><TypeVariableType *>()) {
// Extract the representative.
auto nextTV = impl->ParentOrFixed.get<TypeVariableType *>();
if (nextTV == result)
result = nextTV;
impl = &nextTV->getImpl();
if (impl == this || !record)
return result;
// Perform path compression.
impl = this;
while (impl-><TypeVariableType *>()) {
// Extract the representative.
auto nextTV = impl->ParentOrFixed.get<TypeVariableType *>();
if (nextTV == result)
// Record the state change.
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);
auto otherRep = other->getImpl().getRepresentative(record);
if (record)
otherRep->getImpl().ParentOrFixed = getTypeVariable();
if (canBindToLValue() && !otherRep->getImpl().canBindToLValue()) {
if (record)
getTypeVariable()->Bits.TypeVariableType.Options &= ~TVO_CanBindToLValue;
if (canBindToInOut() && !otherRep->getImpl().canBindToInOut()) {
if (record)
getTypeVariable()->Bits.TypeVariableType.Options &= ~TVO_CanBindToInOut;
if (canBindToNoEscape() && !otherRep->getImpl().canBindToNoEscape()) {
if (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().ParentOrFixed = type.getPointer();
void setCanBindToLValue(constraints::SavedTypeVariableBindings *record,
bool enabled) {
auto &impl = getRepresentative(record)->getImpl();
if (record)
if (enabled)
impl.getTypeVariable()->Bits.TypeVariableType.Options |=
impl.getTypeVariable()->Bits.TypeVariableType.Options &=
void setCanBindToNoEscape(constraints::SavedTypeVariableBindings *record,
bool enabled) {
auto &impl = getRepresentative(record)->getImpl();
if (record)
if (enabled)
impl.getTypeVariable()->Bits.TypeVariableType.Options |=
impl.getTypeVariable()->Bits.TypeVariableType.Options &=
void enableCanBindToHole(constraints::SavedTypeVariableBindings *record) {
auto &impl = getRepresentative(record)->getImpl();
if (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() || !<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.
/// The two solutions are identical.
/// The first solution is better than the second.
/// The second solution is better than the first.
/// 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;
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);
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.size());
/// Whether the argument is a trailing closure.
bool isTrailingClosure() const {
if (auto trailingClosureArg =
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; }
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;
/// \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.
/// A hole in the constraint system.
/// A reference to an @unavailable declaration.
/// A reference to an async function in a synchronous context, or
/// vice versa.
/// A use of the "forward" scan for trailing closures.
/// A use of a disfavored overload.
/// A member for an \c UnresolvedMemberExpr found via unwrapped optional base.
/// An implicit force of an implicitly unwrapped optional value.
/// A user-defined conversion.
/// A non-trivial function conversion.
/// A literal expression bound to a non-default literal type.
/// An implicit upcast conversion between collection types.
/// A value-to-optional conversion.
/// A conversion to an empty existential type ('Any' or '{}').
/// A key path application subscript.
/// A conversion from a string, array, or inout to a pointer.
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 *>>>
/// 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 {
enum class Kind {
Kind kind;
union {
const StmtConditionElement *stmtCondElement;
const Stmt *stmt;
struct PatternBindingEntry {
const PatternBindingDecl *patternBinding;
unsigned index;
} patternBindingEntry;
const VarDecl *varDecl;
} storage;
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;
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 ==;
case Kind::stmt:
return ==;
case Kind::patternBindingEntry:
return (
== &&
case Kind::varDecl:
return ==;
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<void *>::getHashValue(storage.stmtCondElement));
case Kind::stmt:
return hash_combine(
DenseMapInfo<void *>::getHashValue(storage.stmt));
case Kind::patternBindingEntry:
return hash_combine(
DenseMapInfo<void *>::getHashValue(
case Kind::varDecl:
return hash_combine(
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;
/// 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>
/// 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>
/// 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 *>
/// 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>
/// Maps case label items to information tracked about them as they are
/// being solved.
llvm::SmallMapVector<const CaseLabelItem *, CaseLabelItemInfo, 4>
std::vector<std::pair<ConstraintLocator *, ProtocolConformanceRef>>
/// The set of functions that have been transformed by a result builder.
llvm::MapVector<AnyFunctionRef, AppliedBuilderTransform>
/// 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.
resolveConcreteDeclRef(ValueDecl *decl, ConstraintLocator *locator) const;
/// Return the disjunction choice for the given constraint location.
unsigned getDisjunctionChoice(ConstraintLocator *locator) const {
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 and will not return a decl for \c
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.
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.
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;
/// 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 {
/// 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.
/// This result indicates that the member reference is erroneous, but was
/// already diagnosed. Don't emit another error.
/// 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.
} 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.
/// This is an instance member being accessed through something of metatype
/// type.
/// This is a static/class member being accessed through an instance.
/// This is a mutating member, being used on an rvalue.
/// 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.
/// The member is inaccessible (e.g. a private member in another file).
/// 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.
/// 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.
/// This is a KeyPath whose root type is AnyObject
/// 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) {
void addUnviable(OverloadChoice candidate, UnviableReason 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) {
void addKeywordArgumentsMethod(FuncDecl *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 {
enum class Kind {
} kind;
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();
SolutionApplicationTarget(Expr *expr, DeclContext *dc,
ContextualTypePurpose contextualPurpose,
Type convertType, bool isDiscarded)
: SolutionApplicationTarget(expr, dc, contextualPurpose,
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(),
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) &&
/// 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 &&
/// 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 {
return expression.forEachStmt;
ForEachStmtInfo &getForEachStmtInfo() {
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(),
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 {
/// Describes the result of applying a solution to a given function.
enum class SolutionApplicationToFunctionResult {
/// Application of the solution succeeded.
/// Application of the solution failed.
/// TODO: This should probably go away entirely.
/// The solution could not be applied immediately, and type checking for
/// this function should be delayed until later.
/// 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;
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;
/// 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>>
/// 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 *>
/// Maps AST entries to their solution application targets.
llvm::MapVector<SolutionApplicationTargetsKey, SolutionApplicationTarget>
/// 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>
/// Maps closure parameters to type variables.
llvm::DenseMap<const ParamDecl *, TypeVariableType *>
/// 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>>
/// 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>>
/// For locators associated with call expressions, the trailing closure
/// matching rule that was applied.
std::vector<std::pair<ConstraintLocator*, TrailingClosureMatching>>
/// 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>
/// 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>
/// 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>>
/// The set of functions that have been transformed by a result builder.
std::vector<std::pair<AnyFunctionRef, AppliedBuilderTransform>>
/// Cache of the effects any closures visited.
llvm::SmallDenseMap<ClosureExpr *, FunctionType::ExtInfo, 4> closureEffectsCache;
/// 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;
/// 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;
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;
unsigned unsolvedDisjunctions = disjunctions.size();
for (auto *disjunction : disjunctions) {
auto *locator = disjunction->getLocator();
if (!locator)
if (auto *OSR = getAsExpr<OverloadSetRefExpr>(locator->getAnchor())) {
if (shrunkExprs.count(OSR) > 0)
unsigned threshold =
return unsolvedDisjunctions >= threshold;
/// Describes the current solver state.
struct SolverState {
SolverState(ConstraintSystem &cs,
FreeTypeVariableBinding allowFreeTypeVariables);
/// 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) {
/// 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)
/// Add new "generated" constraint along the current solver path.
/// \param constraint The newly generated constraint.
void addGeneratedConstraint(Constraint *constraint) {
assert(constraint && "Null generated 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) {
maxDepth = std::max(maxDepth, depth);
scope->scopeNumber = NumStatesExplored++;
auto scopeInfo =
std::make_tuple(scope, retiredConstraints.begin(),
/// 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) {
unsigned countScopesExplored = NumStatesExplored - scope->scopeNumber;
if (countScopesExplored == 1)
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) =
assert(savedScope == scope && "Scope rollback not in LIFO order!");
// Restore all of the retired constraints.
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) {
generatedConstraints.erase(genStart, genEnd);
for (unsigned constraintIdx :
range(scope->numDisabledConstraints, disabledConstraints.size())) {
if (disabledConstraints[constraintIdx]->isDisabled())
disabledConstraints.begin() + scope->numDisabledConstraints,
for (unsigned constraintIdx :
range(scope->numFavoredConstraints, favoredConstraints.size())) {
if (favoredConstraints[constraintIdx]->isFavored())
favoredConstraints.begin() + scope->numFavoredConstraints,
/// 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) {
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) {
/// 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.
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;
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())
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; }
/// 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)
#ifndef NDEBUG
switch (Phase) {
case ConstraintSystemPhase::ConstraintGeneration:
assert(newPhase == ConstraintSystemPhase::Solving);
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);
case ConstraintSystemPhase::Diagnostics:
assert(newPhase == ConstraintSystemPhase::Solving ||
newPhase == ConstraintSystemPhase::Finalization);
case ConstraintSystemPhase::Finalization:
assert(newPhase == ConstraintSystemPhase::Diagnostics);
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);
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);
unsigned assignTypeVariableID() {
return TypeCounter++;
void incrementScopeCounter();
void incrementLeafScopes();
/// 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;
explicit SolverScope(ConstraintSystem &cs);
ConstraintSystem(DeclContext *dc,
ConstraintSystemOptions options);
/// 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);
/// 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>
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.
filterSolutions(SmallVectorImpl<Solution> &solutions,
bool minimize = false) {
if (solutions.size() < 2)
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);
/// 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(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),
/// 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
/// 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 rather than \c
/// \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,