//===--- ConstraintSystem.h - Constraint-based Type Checking ----*- C++ -*-===// // // This source file is part of the Swift.org open source project // // Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors // Licensed under Apache License v2.0 with Runtime Library Exception // // See http://swift.org/LICENSE.txt for license information // See http://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 "TypeChecker.h" #include "Constraint.h" #include "ConstraintGraph.h" #include "ConstraintGraphScope.h" #include "ConstraintLocator.h" #include "OverloadChoice.h" #include "swift/Basic/LLVM.h" #include "swift/Basic/OptionSet.h" #include "swift/AST/ASTVisitor.h" #include "swift/AST/NameLookup.h" #include "swift/AST/Types.h" #include "swift/AST/TypeCheckerDebugConsumer.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/PointerUnion.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include #include namespace swift { class Expr; namespace constraints { class ConstraintGraph; class ConstraintGraphNode; class ConstraintSystem; } // end namespace constraints } // end namespace swift /// \brief Allocate memory within the given constraint system. void *operator new(size_t bytes, swift::constraints::ConstraintSystem& cs, size_t alignment = 8); namespace swift { namespace constraints { /// \brief A handle that holds the saved state of a type variable, which /// can be restored. class SavedTypeVariableBinding { /// \brief The type variable and type variable options. llvm::PointerIntPair TypeVarAndOptions; /// \brief The parent or fixed type. llvm::PointerUnion ParentOrFixed; public: explicit SavedTypeVariableBinding(TypeVariableType *typeVar); /// \brief Restore the state of the type variable to the saved state. void restore(); TypeVariableType *getTypeVariable() { return TypeVarAndOptions.getPointer(); } unsigned getOptions() { return TypeVarAndOptions.getInt(); } }; /// \brief A set of saved type variable bindings. typedef SmallVector SavedTypeVariableBindings; class ConstraintLocator; /// Describes a conversion restriction or a fix. struct RestrictionOrFix { ConversionRestrictionKind Restriction; Fix TheFix; bool IsRestriction; public: RestrictionOrFix(ConversionRestrictionKind restriction) : Restriction(restriction), IsRestriction(true) { } RestrictionOrFix(Fix fix) : TheFix(fix), IsRestriction(false) { } RestrictionOrFix(FixKind fix) : TheFix(fix), IsRestriction(false) { } Optional getRestriction() const { if (IsRestriction) return Restriction; return None; } Optional getFix() const { if (!IsRestriction) return TheFix; return None; } }; } // 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 a more specific deduction for this type variable implies a /// better solution to the constraint system. TVO_PrefersSubtypeBinding = 0x02, /// Whether the variable must be bound to a materializable type. TVO_MustBeMaterializable = 0x04 }; /// \brief 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 { /// Type variable options. unsigned Options : 3; /// \brief The locator that describes where this type variable was generated. constraints::ConstraintLocator *locator; /// \brief 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 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: /// \brief If this type variable is an opened literal expression, keep track /// of the associated literal conformance for optimization and diagnostic /// purposes. ProtocolDecl *literalConformanceProto = nullptr; explicit Implementation(constraints::ConstraintLocator *locator, unsigned options) : Options(options), locator(locator), ParentOrFixed(getTypeVariable()) { } /// \brief Retrieve the unique ID corresponding to this type variable. unsigned getID() const { return getTypeVariable()->getID(); } /// Whether this type variable can bind to an lvalue type. bool canBindToLValue() const { return Options & TVO_CanBindToLValue; } /// Whether this type variable prefers a subtype binding over a supertype /// binding. bool prefersSubtypeBinding() const { return Options & TVO_PrefersSubtypeBinding; } bool mustBeMaterializable() const { return Options & TVO_MustBeMaterializable; } /// \brief Retrieve the type variable associated with this implementation. TypeVariableType *getTypeVariable() { return reinterpret_cast(this) - 1; } /// \brief Retrieve the type variable associated with this implementation. const TypeVariableType *getTypeVariable() const { return reinterpret_cast(this) - 1; } /// 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; } /// \brief 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()) return true; // Check whether the representative is different from our own type // variable. return ParentOrFixed.get() != getTypeVariable(); } /// \brief Record the current type-variable binding. void recordBinding(constraints::SavedTypeVariableBindings &record) { record.push_back(constraints::SavedTypeVariableBinding(getTypeVariable())); } /// \brief Retrieve the locator describing where this type variable was /// created. constraints::ConstraintLocator *getLocator() const { return locator; } /// \brief Retrieve the archetype opened by this type variable. ArchetypeType *getArchetype() const; /// \brief 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()) { // Extract the representative. auto nextTV = impl->ParentOrFixed.get(); if (nextTV == result) break; result = nextTV; impl = &nextTV->getImpl(); } if (impl == this || !record) return result; // Perform path compression. impl = this; while (impl->ParentOrFixed.is()) { // Extract the representative. auto nextTV = impl->ParentOrFixed.get(); if (nextTV == result) break; // Record the state change. impl->recordBinding(*record); impl->ParentOrFixed = result; impl = &nextTV->getImpl(); } return result; } /// \brief 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 (!mustBeMaterializable() && otherRep->getImpl().mustBeMaterializable()) { if (record) recordBinding(*record); Options |= TVO_MustBeMaterializable; } } /// \brief 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(); // Check whether it has a fixed type. if (auto type = repImpl.ParentOrFixed.dyn_cast()) return type; return Type(); } /// \brief 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 setMustBeMaterializable(constraints::SavedTypeVariableBindings *record) { auto rep = getRepresentative(record); if (!rep->getImpl().mustBeMaterializable()) { if (record) rep->getImpl().recordBinding(*record); rep->getImpl().Options |= TVO_MustBeMaterializable; } } /// \brief Print the type variable to the given output stream. void print(llvm::raw_ostream &OS); }; namespace constraints { struct ResolvedOverloadSetListItem; /// \brief The kind of type matching to perform in matchTypes(). enum class TypeMatchKind : char { /// \brief Bind the types together directly. BindType, /// \brief Binds to a pointer element type. BindToPointerType, /// \brief Bind the type of a function parameter to the type of a reference /// to it from within the function body. The param type is an inout type iff /// the reference type is an lvalue type with the same object type. /// Otherwise, the two types must be the same type. BindParamType, /// \brief Require the types to match exactly, but strips lvalueness from /// a type when binding to a type variable. SameType, /// \brief Require that the first type conform to the second type (which /// must be a protocol). ConformsTo, /// \brief Require the first type to be a subtype of the second type /// (or be an exact match or trivial subtype). Subtype, /// \brief Requires the first type to be convertible to the second type, /// which includes exact matches and both forms of subtyping. Conversion, /// \brief Requires the first type to be explicitly convertible to the second /// type, which includes all forms of conversion included in Conversion, in /// addition to bridging conversions. ExplicitConversion, /// \brief Requires the first type to be the element of an argument tuple /// that is convertible to the second type, which represents the corresponding /// element of the parameter tuple. ArgumentConversion, /// Requires the first type to be an argument type (tuple) that can be /// converted to the second type, which represents the parameter type (tuple). ArgumentTupleConversion, /// \brief Requires the first type to be convertible to the second type, /// which includes exact matches, both forms of subtyping, and inserting /// address-of to convert implicit lvalues to inout arguments. This is /// used by assignment operators. OperatorArgumentConversion, /// Like \c ArgumentTupleConversion, but for operators. OperatorArgumentTupleConversion, }; /// \brief The result of comparing two constraint systems that are a solutions /// to the given set of constraints. enum class SolutionCompareResult { /// \brief The two solutions are incomparable, because, e.g., because one /// solution has some better decisions and some worse decisions than the /// other. Incomparable, /// \brief The two solutions are identical. Identical, /// \brief The first solution is better than the second. Better, /// \brief 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. OverloadChoice choice; /// The opened type of the base of the reference to this overload, if /// we're referencing a member. Type openedFullType; /// The opened type produced by referring to this overload. Type openedType; }; /// 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 reference to an @unavailable declaration. SK_Unavailable, /// A fix needs to be applied to the source. SK_Fix, /// 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 bridged conversion between collection types. SK_CollectionBridgedConversion, /// An implicit upcast conversion between collection types. SK_CollectionUpcastConversion, /// A value-to-optional conversion. SK_ValueToOptional, /// A conversion from an inout to a pointer of matching element type. SK_ScalarPointerConversion, /// A conversion from an array to a pointer of matching element type. SK_ArrayPointerConversion, /// A conversion to an empty existential type ('Any' or '{}'). SK_EmptyExistentialConversion, SK_LastScoreKind = SK_EmptyExistentialConversion, }; /// The number of score kinds. const unsigned NumScoreKinds = SK_LastScoreKind + 1; /// 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. typedef std::pair OpenedType; /// \brief 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 { /// \brief The constraint system this solution solves. ConstraintSystem *constraintSystem; /// \brief The fixed score for this solution. Score FixedScore; public: /// \brief 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; /// \brief Retrieve the constraint system that this solution solves. ConstraintSystem &getConstraintSystem() const { return *constraintSystem; } /// \brief The set of type bindings. llvm::SmallDenseMap typeBindings; /// \brief The set of overload choices along with their types. llvm::SmallDenseMap overloadChoices; /// The set of constraint restrictions used to arrive at this restriction, /// which informs constraint application. llvm::SmallDenseMap, ConversionRestrictionKind> ConstraintRestrictions; /// The list of fixes that need to be applied to the initial expression /// to make the solution work. llvm::SmallVector, 4> Fixes; /// The set of disjunction choices used to arrive at this solution, /// which informs constraint application. llvm::SmallDenseMap DisjunctionChoices; /// The set of opened types for a given locator. llvm::SmallDenseMap> OpenedTypes; /// The opened existential type for a given locator. llvm::SmallDenseMap OpenedExistentialTypes; /// \brief Simplify the given type by substituting all occurrences of /// type variables for their fixed types. Type simplifyType(TypeChecker &tc, Type type) const; /// \brief 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 ignoreTopLevelInjection Whether to suppress diagnostics /// on a suspicious top-level optional injection (because the caller already /// diagnosed it). /// /// \returns the coerced expression, which will have type \c ToType. Expr *coerceToType(Expr *expr, Type toType, ConstraintLocator *locator, bool ignoreTopLevelInjection = false) const; /// \brief Convert the given expression to a logic value. /// /// This operation cannot fail. /// /// \param expr The expression to coerce. The type of this expression /// must conform to the LogicValue protocol. /// /// \param locator Locator used to describe the location of this expression. /// /// \returns the expression converted to a logic value (Builtin i1). Expr *convertBooleanTypeToBuiltinI1(Expr *expr, ConstraintLocator *locator) const; /// \brief Convert the given optional-producing expression to a Bool /// indicating whether the optional has a value. /// /// This operation cannot fail. /// /// \param expr The expression to coerce. The type of this expression /// must be T?. /// /// \param locator Locator used to describe the location of this expression. /// /// \returns a Bool expression indicating whether the optional /// contains a value. Expr *convertOptionalToBool(Expr *expr, ConstraintLocator *locator) const; /// Compute the set of substitutions required to map the given type /// to the provided "opened" type. /// /// Either the generic type (\c origType) must be a \c GenericFunctionType, /// in which case it's generic requirements will be used to compute the /// required substitutions, or \c dc must be a generic context, in which /// case it's generic requirements will be used. /// /// \param origType The generic type. /// /// \param openedType The type to which this reference to the given /// generic function type was opened. /// /// \param dc The declaration context that owns the generic type /// /// \param locator The locator that describes where the substitutions came /// from. /// /// \param substitutions Will be populated with the set of substitutions /// to be applied to the generic function type. /// /// \returns The opened type after applying the computed substitutions. Type computeSubstitutions(Type origType, DeclContext *dc, Type openedType, ConstraintLocator *locator, SmallVectorImpl &substitutions) const; /// Return the disjunction choice for the given constraint location. unsigned getDisjunctionChoice(ConstraintLocator *locator) const { assert(DisjunctionChoices.count(locator)); return DisjunctionChoices.find(locator)->second; } /// \brief Retrieve the fixed score of this solution const Score &getFixedScore() const { return FixedScore; } /// \brief Retrieve the fixed score of this solution Score &getFixedScore() { return FixedScore; } /// \brief Retrieve the fixed type for the given type variable. Type getFixedType(TypeVariableType *typeVar) const; LLVM_ATTRIBUTE_DEPRECATED( void dump() const LLVM_ATTRIBUTE_USED, "only for use within the debugger"); /// \brief Dump this solution. void dump(raw_ostream &OS) const LLVM_ATTRIBUTE_USED; }; /// \brief Describes the differences between several solutions to the same /// constraint system. class SolutionDiff { public: /// \brief A difference between two overloads. struct OverloadDiff { /// \brief The locator that describes where the overload comes from. ConstraintLocator *locator; /// \brief The choices that each solution made. SmallVector choices; }; /// \brief A difference between two type variable bindings. struct TypeBindingDiff { /// \brief The type variable. TypeVariableType *typeVar; /// \brief The bindings that each solution made. SmallVector bindings; }; /// \brief The differences between the overload choices between the /// solutions. SmallVector overloads; /// \brief The differences between the type variable bindings of the /// solutions. SmallVector typeBindings; /// \brief Compute the differences between the given set of solutions. /// /// \param solutions The set of solutions. explicit SolutionDiff(ArrayRef solutions); }; /// Describes one resolved overload set within the list of overload sets /// resolved by the solver. struct ResolvedOverloadSetListItem { /// The previously resolved overload set in the list. ResolvedOverloadSetListItem *Previous; /// The type that this overload binds. Type BoundType; /// The overload choice. OverloadChoice Choice; /// The locator for this choice. ConstraintLocator *Locator; /// The type of the fully-opened base, if any. Type OpenedFullType; /// The type of the referenced choice. Type ImpliedType; // Make vanilla new/delete illegal for overload set items. void *operator new(size_t Bytes) = delete; void operator delete(void *Data) = delete; // Only allow allocation of list items using the allocator in the // constraint system. void *operator new(size_t bytes, ConstraintSystem &cs, unsigned alignment = alignof(ResolvedOverloadSetListItem)); }; /// Identifies a specific conversion from struct SpecificConstraint { CanType First; CanType Second; ConstraintKind Kind; }; /// An intrusive, doubly-linked list of constraints. typedef llvm::ilist ConstraintList; enum class ConstraintSystemFlags { /// Whether we allow the solver to attempt fixes to the system. AllowFixes = 0x01, /// Set if the client prefers fixits to be in the form of force unwrapping /// or optional chaining to return an optional. PreferForceUnwrapToOptional = 0x02, }; /// Options that affect the constraint system as a whole. typedef OptionSet ConstraintSystemOptions; /// 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 ViableCandidates; /// If there is a favored candidate in the viable list, this indicates its /// index. unsigned FavoredChoice = ~0U; /// This enum tracks reasons why a candidate is not viable. enum UnviableReason { /// Argument labels don't match. UR_LabelMismatch, /// This uses a type like Self it 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 access 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 list of considered, but rejected, candidates, along with a /// reason for their rejection. SmallVector, 4> UnviableCandidates; /// 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(ValueDecl *VD, UnviableReason reason) { UnviableCandidates.push_back({VD, reason}); } OverloadChoice *getFavoredChoice() { if (FavoredChoice == ~0U) return nullptr; return &ViableCandidates[FavoredChoice]; } }; /// \brief 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 { public: TypeChecker &TC; DeclContext *DC; ConstraintSystemOptions Options; friend class Fix; friend class OverloadChoice; friend class ConstraintGraph; class SolverScope; Constraint *failedConstraint = nullptr; private: /// \brief Allocator used for all of the related constraint systems. llvm::BumpPtrAllocator Allocator; /// \brief Arena used for memory management of constraint-checker-related /// allocations. ConstraintCheckerArenaRAII Arena; /// \brief Counter for type variables introduced. unsigned TypeCounter = 0; /// \brief The expression being solved has exceeded the solver's memory /// threshold. bool expressionExceededThreshold = false; /// \brief Cached member lookups. llvm::DenseMap, Optional> MemberLookups; /// Cached sets of "alternative" literal types. Optional> AlternativeLiteralTypes[12]; /// \brief Folding set containing all of the locators used in this /// constraint system. llvm::FoldingSetVector ConstraintLocators; /// \brief The overload sets that have been resolved along the current path. ResolvedOverloadSetListItem *resolvedOverloadSets = nullptr; /// The current fixed score for this constraint system and the (partial) /// solution it represents. Score CurrentScore; /// Whether this constraint system is processing a favored /// constraint. bool HandlingFavoredConstraint = false; SmallVector TypeVariables; /// Maps expressions to types for choosing a favored overload /// type in a disjunction constraint. llvm::DenseMap FavoredTypes; /// There can only be a single contextual type on the root of the expression /// being checked. If specified, this holds its type along with the base /// expression, and the purpose of it. Type contextualType; Expr *contextualTypeNode = nullptr; ContextualTypePurpose contextualTypePurpose = CTP_Unused; /// \brief 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. SmallVector, 32> ConstraintRestrictions; /// The set of fixes applied to make the solution work. /// /// Each fix is paired with a locator that describes where the fix occurs. SmallVector, 4> Fixes; /// Types used in fixes. std::vector FixedTypes; /// \brief The set of remembered disjunction choices used to reach /// the current constraint system. SmallVector, 32> DisjunctionChoices; /// 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>, 4> OpenedTypes; /// A mapping from constraint locators to the opened existential archetype /// used for the 'self' of an existential type. SmallVector, 4> OpenedExistentialTypes; /// \brief Describes the current solver state. struct SolverState { SolverState(ConstraintSystem &cs); ~SolverState(); /// The constraint system. ConstraintSystem &CS; /// Old value of DebugConstraintSolver. /// FIXME: Move the "debug constraint solver" bit into the constraint /// system itself. bool OldDebugConstraintSolver; /// \brief Depth of the solution stack. unsigned depth = 0; /// \brief Whether to record failures or not. bool recordFixes = false; /// The list of constraints that have been retired along the /// current path. ConstraintList retiredConstraints; /// The current set of generated constraints. SmallVector generatedConstraints; /// \brief The set of type variable bindings that have changed while /// processing this constraint system. SavedTypeVariableBindings savedBindings; /// The best solution computed so far. Optional 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" }; public: /// \brief 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; /// 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> ArgumentLabels; /// FIXME: This is a workaround for the way we perform protocol /// conformance checking for generic requirements, where we re-use /// the archetypes of the requirement (rather than, say, building /// new archetypes) to match up with the witness. Those archetypes /// can end up with references to the outer archetypes (of the /// associated types), which need to be replaced. TypeVariableType *SelfTypeVar = nullptr; /// \brief The set of additional attributes inferred for a FunctionType. Note /// that this is not state kept as part of SolverState, so it only supports /// function attributes that need to be set invariant of the actual typing of /// the solution. llvm::SmallDenseMap extraFunctionAttrs; ResolvedOverloadSetListItem *getResolvedOverloadSets() const { return resolvedOverloadSets; } private: unsigned assignTypeVariableID() { return TypeCounter++; } public: /// \brief 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; /// \brief The current resolved overload set list. ResolvedOverloadSetListItem *resolvedOverloadSets; /// \brief The length of \c TypeVariables. unsigned numTypeVariables; /// \brief The length of \c SavedBindings. unsigned numSavedBindings; /// The length of generatedConstraints. unsigned numGeneratedConstraints; /// \brief The last retired constraint in the list. ConstraintList::iterator firstRetired; /// \brief The length of \c ConstraintRestrictions. unsigned numConstraintRestrictions; /// \brief The length of \c Fixes. unsigned numFixes; /// \brief The length of \c DisjunctionChoices. unsigned numDisjunctionChoices; /// The length of \c OpenedTypes. unsigned numOpenedTypes; /// The length of \c OpenedExistentialTypes. unsigned numOpenedExistentialTypes; /// The previous score. Score PreviousScore; /// 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(TypeChecker &tc, DeclContext *dc, ConstraintSystemOptions options); ~ConstraintSystem(); /// Retrieve the type checker associated with this constraint system. TypeChecker &getTypeChecker() const { return TC; } /// Retrieve the constraint graph associated with this constraint system. ConstraintGraph &getConstraintGraph() const { return CG; } /// \brief Retrieve the AST context. ASTContext &getASTContext() const { return TC.Context; } /// \brief Determine whether this constraint system has any free type /// variables. bool hasFreeTypeVariables(); private: /// \brief Finalize this constraint system; we're done attempting to solve /// it. /// /// \returns the solution. Solution finalize(FreeTypeVariableBinding allowFreeTypeVariables); /// \brief 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); /// 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(Expr *E, const Solution &solution); /// \brief Apply the specified Fix # to this solution, producing a fixit hint /// diagnostic for it and returning true. If the fixit hint turned out to be /// bogus, this returns false and doesn't emit anything. bool applySolutionFix(Expr *expr, const Solution &solution, unsigned fixNo); /// \brief 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); /// \brief 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); public: /// \brief 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 name binding, /// and no new names are introduced after name binding. /// /// \returns A reference to the member-lookup result. LookupResult &lookupMember(Type base, DeclName name); /// Retrieve the set of "alternative" literal types that we'll explore /// for a given literal protocol kind. ArrayRef getAlternativeLiteralTypes(KnownProtocolKind kind); /// \brief Create a new type variable. TypeVariableType *createTypeVariable(ConstraintLocator *locator, unsigned options) { auto tv = TypeVariableType::getNew(TC.Context, assignTypeVariableID(), locator, options); addTypeVariable(tv); return tv; } /// Retrieve the set of active type variables. ArrayRef getTypeVariables() const { return TypeVariables; } TypeBase* getFavoredType(Expr *E) { return this->FavoredTypes[E]; } void setFavoredType(Expr *E, TypeBase *T) { this->FavoredTypes[E] = T; } void setContextualType(Expr *E, Type T, ContextualTypePurpose purpose) { contextualTypeNode = E; contextualType = T; contextualTypePurpose = purpose; } Type getContextualType(Expr *E) const { return E == contextualTypeNode ? contextualType : Type(); } Type getContextualType() const { return contextualType; } ContextualTypePurpose getContextualTypePurpose() const { return contextualTypePurpose; } /// \brief Retrieve the constraint locator for the given anchor and /// path, uniqued. ConstraintLocator * getConstraintLocator(Expr *anchor, ArrayRef path, unsigned summaryFlags); /// \brief Retrieve the constraint locator for the given anchor and /// an empty path, uniqued. ConstraintLocator *getConstraintLocator(Expr *anchor) { return getConstraintLocator(anchor, {}, 0); } /// \brief Retrieve the constraint locator for the given anchor and /// path element. ConstraintLocator * getConstraintLocator(Expr *anchor, ConstraintLocator::PathElement pathElt) { return getConstraintLocator(anchor, llvm::makeArrayRef(pathElt), pathElt.getNewSummaryFlags()); } /// \brief Extend the given constraint locator with a path element. ConstraintLocator * getConstraintLocator(ConstraintLocator *locator, ConstraintLocator::PathElement pathElt) { return getConstraintLocator(ConstraintLocatorBuilder(locator) .withPathElement(pathElt)); } /// \brief Retrieve the constraint locator described by the given /// builder. ConstraintLocator * getConstraintLocator(const ConstraintLocatorBuilder &builder); public: /// \brief Whether we should attempt to fix problems. bool shouldAttemptFixes() { if (!(Options & ConstraintSystemFlags::AllowFixes)) return false; return !solverState || solverState->recordFixes; } /// \brief Log and record the application of the fix. Return true iff any /// subsequent solution would be worse than the best known solution. bool recordFix(Fix fix, ConstraintLocatorBuilder locator); /// \brief Try to salvage the constraint system by applying (speculative) /// fixes to the underlying expression. /// /// \param viable the set of viable solutions produced by the initial /// solution attempt. /// /// \param expr the expression we're trying to salvage. /// /// \returns false if we were able to salvage the system, in which case /// \c viable[0] contains the resulting solution. Otherwise, emits a /// diagnostic and returns true. bool salvage(SmallVectorImpl &viable, Expr *expr); /// When an assignment to an expression is detected and the destination is /// invalid, emit a detailed error about the condition. void diagnoseAssignmentFailure(Expr *dest, Type destTy, SourceLoc equalLoc); /// \brief Mine the active and inactive constraints in the constraint /// system to generate a plausible diagnosis of why the system could not be /// solved. /// /// \param expr The expression whose constraints we're investigating for a /// better diagnostic. /// /// Assuming that this constraint system is actually erroneous, this *always* /// emits an error message. void diagnoseFailureForExpr(Expr *expr); /// \brief Add a newly-allocated constraint after attempting to simplify /// it. /// /// \param isExternallySolved Whether this constraint is being solved /// as an eager simplification, outside of the simplify() loop. /// /// \param simplifyExisting Whether we're simplifying an existing /// constraint rather than introducing a new constraint. /// /// \returns true if this constraint was solved. bool addConstraint(Constraint *constraint, bool isExternallySolved = false, bool simplifyExisting = false); /// \brief Add a constraint to the constraint system. void addConstraint(ConstraintKind kind, Type first, Type second, ConstraintLocator *locator, bool isFavored = false) { assert(first && "Missing first type"); assert(second && "Missing second type"); auto c = Constraint::create(*this, kind, first, second, DeclName(), locator); if (isFavored) c->setFavored(); addConstraint(c); } /// Add a constraint that binds an overload set to a specific choice. void addBindOverloadConstraint(Type boundTy, OverloadChoice choice, ConstraintLocator *locator) { addConstraint(Constraint::createBindOverload(*this, boundTy, choice, locator)); } /// \brief Add a value member constraint to the constraint system. void addValueMemberConstraint(Type baseTy, DeclName name, Type memberTy, ConstraintLocator *locator) { assert(baseTy); assert(memberTy); assert(name); addConstraint(Constraint::create(*this, ConstraintKind::ValueMember, baseTy, memberTy, name, locator)); } /// \brief Add a value member constraint for an UnresolvedMemberRef /// to the constraint system. void addUnresolvedValueMemberConstraint(Type baseTy, DeclName name, Type memberTy, ConstraintLocator *locator) { assert(baseTy); assert(memberTy); assert(name); addConstraint(Constraint::create(*this, ConstraintKind::UnresolvedValueMember, baseTy, memberTy, name, locator)); } /// \brief Add an archetype constraint. void addArchetypeConstraint(Type baseTy, ConstraintLocator *locator) { assert(baseTy); addConstraint(Constraint::create(*this, ConstraintKind::Archetype, baseTy, Type(), DeclName(), locator)); } /// \brief Remove an inactive constraint from the current constraint graph. void removeInactiveConstraint(Constraint *constraint) { CG.removeConstraint(constraint); InactiveConstraints.erase(constraint); } /// Retrieve the type that corresponds to the given member of the /// given base type, which may be a newly-created type variable. /// /// \param baseTypeVar The base type variable whose member is being queried. /// /// \param assocType The associated type we're referencing. /// /// \param locator The location used to describe this member access. /// /// \param options Options to be supplied to type variable creation if /// a new type is created. /// /// \returns the type variable representing the member type. TypeVariableType *getMemberType(TypeVariableType *baseTypeVar, AssociatedTypeDecl *assocType, ConstraintLocatorBuilder locator, unsigned options); /// Retrieve the list of inactive constraints. ConstraintList &getConstraints() { return InactiveConstraints; } /// The worklist of "active" constraints that should be revisited /// due to a change. ConstraintList &getActiveConstraints() { return ActiveConstraints; } /// \brief Retrieve the representative of the equivalence class containing /// this type variable. TypeVariableType *getRepresentative(TypeVariableType *typeVar) { return typeVar->getImpl().getRepresentative(getSavedBindings()); } /// \brief Merge the equivalence sets of the two type variables. /// /// Note that both \c typeVar1 and \c typeVar2 must be the /// representatives of their equivalence classes, and must be /// distinct. void mergeEquivalenceClasses(TypeVariableType *typeVar1, TypeVariableType *typeVar2, bool updateWorkList = true); /// \brief Retrieve the fixed type corresponding to the given type variable, /// or a null type if there is no fixed type. Type getFixedType(TypeVariableType *typeVar) { return typeVar->getImpl().getFixedType(getSavedBindings()); } /// Retrieve the fixed type corresponding to a given type variable, /// recursively, until we hit something that isn't a type variable /// or a type variable that doesn't have a fixed type. /// /// \param type The type to simplify. /// /// \param typeVar Will receive the type variable at which simplification /// stopped, which has no fixed type. /// /// \param wantRValue Whether this routine should look through /// lvalues at each step. /// /// param retainParens Whether to retain parentheses. Type getFixedTypeRecursive(Type type, TypeVariableType *&typeVar, bool wantRValue, bool retainParens = false); /// \brief Assign a fixed type to the given type variable. /// /// \param typeVar The type variable to bind. /// /// \param type The fixed type to which the type variable will be bound. /// /// \param updateState Whether to update the state based on this binding. /// False when we're only assigning a type as part of reconstructing /// a complete solution from partial solutions. void assignFixedType(TypeVariableType *typeVar, Type type, bool updateState = true); // \brief Set the TVO_MustBeMaterializable bit on all type variables // necessary to ensure that the type in question is materializable in a // viable solution. void setMustBeMaterializableRecursive(Type type); /// \brief Determine if the type in question is an Array. bool isArrayType(Type t); /// Determine whether the given type is a dictionary and, if so, provide the /// key and value types for the dictionary. Optional> isDictionaryType(Type type); /// \brief Determine if the type in question is a Set. bool isSetType(Type t); private: /// Introduce the constraints associated with the given type variable /// into the worklist. void addTypeVariableConstraintsToWorkList(TypeVariableType *typeVar); public: /// \brief "Open" the given type by replacing any occurrences of generic /// parameter types and dependent member types with fresh type variables. /// /// \param type The type to open. /// /// \param dc The declaration context in which the type occurs. /// /// \returns The opened type. Type openType(Type type, ConstraintLocatorBuilder locator, DeclContext *dc = nullptr) { llvm::DenseMap replacements; return openType(type, locator, replacements, dc, /*skipProtocolSelfConstraint=*/false, /*minOpeningDepth=*/0); } /// \brief "Open" the given type by replacing any occurrences of generic /// parameter types and dependent member types with fresh type variables. /// /// \param type The type to open. /// /// \param replacements The mapping from opened types to the type /// variables to which they were opened. /// /// \param dc The declaration context in which the type occurs. /// /// \param skipProtocolSelfConstraint Whether to skip the constraint on a /// protocol's 'Self' type. /// /// \param minOpeningDepth Whether to skip generic parameters from generic /// contexts that we're inheriting context archetypes from. See the comment /// on openGeneric(). /// /// \returns The opened type, or \c type if there are no archetypes in it. Type openType(Type type, ConstraintLocatorBuilder locator, llvm::DenseMap &replacements, DeclContext *dc = nullptr, bool skipProtocolSelfConstraint = false, unsigned minOpeningDepth = 0); /// \brief "Open" the given binding type by replacing any occurrences of /// archetypes (including those implicit in unbound generic types) with /// fresh type variables. /// /// This variant of \c openType() tweaks the result from \c openType() to /// prefer arrays to slices. /// FIXME: This is a bit of a hack. /// /// \param type The type to open. /// \returns The opened type, or \c type if there are no archetypes in it. Type openBindingType(Type type, ConstraintLocatorBuilder locator); /// Open the generic parameter list and its requirements, creating /// type variables for each of the type parameters. /// /// Note: when a generic declaration is nested inside a generic function, the /// generic parameters of the outer function do not appear in the inner type's /// generic signature. /// /// Eg, /// /// func foo() { /// func g() -> T {} // type is () -> T /// } /// /// class Foo { /// func g() -> T {} // type is Foo -> () -> T /// } /// /// Instead, the outer parameters can appear as free variables in the nested /// declaration's signature, but they do not have to, so they might not be /// substituted at all. Since the inner declaration inherits the context /// archetypes of the outer function we do not need to open them here. void openGeneric(DeclContext *dc, ArrayRef params, ArrayRef requirements, bool skipProtocolSelfConstraint, unsigned minOpeningDepth, ConstraintLocatorBuilder locator, llvm::DenseMap &replacements); /// Record the set of opened types for the given locator. void recordOpenedTypes( ConstraintLocatorBuilder locator, const llvm::DenseMap &replacements); /// \brief Retrieve the type of a reference to the given value declaration. /// /// For references to polymorphic function types, this routine "opens up" /// the type by replacing each instance of an archetype with a fresh type /// variable. /// /// \param decl The declarations whose type is being computed. /// /// \param isTypeReference Whether it's a reference to this declaration /// as a type. /// /// \param isSpecialized Whether this declaration is immediately specialized. /// /// \returns a pair containing the full opened type (if applicable) and /// opened type of a reference to declaration. std::pair getTypeOfReference( ValueDecl *decl, bool isTypeReference, bool isSpecialized, ConstraintLocatorBuilder locator, const DeclRefExpr *base = nullptr); /// Replace the 'Self' type in the archetype with the appropriate /// type variable, if needed. /// FIXME: See the documentation of SelfTypeVar. Type replaceSelfTypeInArchetype(ArchetypeType *archetype); /// \brief Retrieve the type of a reference to the given value declaration, /// as a member with a base of the given type. /// /// For references to generic function types or members of generic types, /// this routine "opens up" the type by replacing each instance of a generic /// parameter with a fresh type variable. /// /// \param isTypeReference Indicates that we want to refer to the declared /// type of the type declaration rather than referring to it as a value. /// /// \param isDynamicResult Indicates that this declaration was found via /// dynamic lookup. /// /// \returns a pair containing the full opened type (which includes the opened /// base) and opened type of a reference to this member. std::pair getTypeOfMemberReference( Type baseTy, ValueDecl *decl, bool isTypeReference, bool isDynamicResult, ConstraintLocatorBuilder locator, const DeclRefExpr *base = nullptr, llvm::DenseMap *replacements = nullptr); /// \brief Add a new overload set to the list of unresolved overload /// sets. void addOverloadSet(Type boundType, ArrayRef choices, ConstraintLocator *locator, OverloadChoice *favored = nullptr); /// If the given type is ImplicitlyUnwrappedOptional, and we're in a context /// that should transparently look through ImplicitlyUnwrappedOptional types, /// return T. Type lookThroughImplicitlyUnwrappedOptionalType(Type type); /// \brief Retrieve the allocator used by this constraint system. llvm::BumpPtrAllocator &getAllocator() { return Allocator; } template ArrayRef::value_type> allocateCopy(It start, It end) { typedef typename std::iterator_traits::value_type T; T *result = (T*)getAllocator().Allocate(sizeof(T)*(end-start), __alignof__(T)); unsigned i; for (i = 0; start != end; ++start, ++i) new (result+i) T(*start); return ArrayRef(result, i); } template ArrayRef allocateCopy(ArrayRef array) { return allocateCopy(array.begin(), array.end()); } template ArrayRef allocateCopy(SmallVectorImpl &vec) { return allocateCopy(vec.begin(), vec.end()); } /// \brief Generate constraints for the given (unchecked) expression. /// /// \returns a possibly-sanitized expression, or null if an error occurred. Expr *generateConstraints(Expr *E); /// \brief Generate constraints for the given top-level expression, /// assuming that its children are already type-checked. /// /// \returns a possibly-sanitized expression, or null if an error occurred. Expr *generateConstraintsShallow(Expr *E); /// \brief Generate constraints for binding the given pattern to the /// value of the given expression. /// /// \returns a possibly-sanitized initializer, or null if an error occurred. Type generateConstraints(Pattern *P, ConstraintLocatorBuilder locator); /// \brief The result of attempting to resolve a constraint or set of /// constraints. enum class SolutionKind : char { /// \brief The constraint has been solved completely, and provides no /// more information. Solved, /// \brief The constraint could not be solved at this point. Unsolved, /// \brief The constraint uncovers an inconsistency in the system. Error }; /// \brief Compute the rvalue type of the given expression, which is the /// destination of an assignment statement. Type computeAssignDestType(Expr *dest, SourceLoc equalLoc); public: /// \brief Flags that direct type matching. enum TypeMatchFlags { TMF_None = 0, /// \brief Indicates that we are in a context where we should be /// generating constraints for any unsolvable problems. /// /// This flag is automatically introduced when type matching destructures /// a type constructor (tuple, function type, etc.), solving that /// constraint while potentially generating others. TMF_GenerateConstraints = 0x01, /// Indicates that we are applying a fix. TMF_ApplyingFix = 0x02, /// Indicates we're matching an operator parameter. TMF_ApplyingOperatorParameter = 0x4, /// Indicates we're unwrapping an optional type for a value-to-optional /// conversion. TMF_UnwrappingOptional = 0x8, /// Indicates we're applying an operator function with a nil-literal /// argument. TMF_ApplyingOperatorWithNil = 0x10, }; private: /// \brief Subroutine of \c matchTypes(), which matches up two tuple types. /// /// \returns the result of performing the tuple-to-tuple conversion. SolutionKind matchTupleTypes(TupleType *tuple1, TupleType *tuple2, TypeMatchKind kind, unsigned flags, ConstraintLocatorBuilder locator); /// \brief Subroutine of \c matchTypes(), which matches a scalar type to /// a tuple type. /// /// \returns the result of performing the scalar-to-tuple conversion. SolutionKind matchScalarToTupleTypes(Type type1, TupleType *tuple2, TypeMatchKind kind, unsigned flags, ConstraintLocatorBuilder locator); /// \brief Subroutine of \c matchTypes(), which extracts a scalar value from /// a single-element tuple type. /// /// \returns the result of performing the tuple-to-scalar conversion. SolutionKind matchTupleToScalarTypes(TupleType *tuple1, Type type2, TypeMatchKind kind, unsigned flags, ConstraintLocatorBuilder locator); /// \brief Subroutine of \c matchTypes(), which matches up two function /// types. SolutionKind matchFunctionTypes(FunctionType *func1, FunctionType *func2, TypeMatchKind kind, unsigned flags, ConstraintLocatorBuilder locator); /// \brief Subroutine of \c matchTypes(), which matches up a value to a /// superclass. SolutionKind matchSuperclassTypes(Type type1, Type type2, TypeMatchKind kind, unsigned flags, ConstraintLocatorBuilder locator); /// \brief Subroutine of \c matchTypes(), which matches up two types that /// refer to the same declaration via their generic arguments. SolutionKind matchDeepEqualityTypes(Type type1, Type type2, ConstraintLocatorBuilder locator); /// \brief Subroutine of \c matchTypes(), which matches up a value to an /// existential type. /// /// \param kind Either ConstraintKind::SelfObjectOfProtocol or /// ConstraintKind::ConformsTo. Usually this uses SelfObjectOfProtocol, /// but when matching the instance type of a metatype with the instance type /// of an existential metatype, since we want an actual conformance check. SolutionKind matchExistentialTypes(Type type1, Type type2, ConstraintKind kind, unsigned flags, ConstraintLocatorBuilder locator); public: // FIXME: public due to statics in CSSimplify.cpp /// \brief Attempt to match up types \c type1 and \c type2, which in effect /// is solving the given type constraint between these two types. /// /// \param type1 The first type, which is on the left of the type relation. /// /// \param type2 The second type, which is on the right of the type relation. /// /// \param kind The kind of type match being performed, e.g., exact match, /// trivial subtyping, subtyping, or conversion. /// /// \param flags A set of flags composed from the TMF_* constants, which /// indicates how /// /// \param locator The locator that will be used to track the location of /// the specific types being matched. /// /// \returns the result of attempting to solve this constraint. SolutionKind matchTypes(Type type1, Type type2, TypeMatchKind kind, unsigned flags, ConstraintLocatorBuilder locator); public: /// \brief Resolve the given overload set to the given choice. void resolveOverload(ConstraintLocator *locator, Type boundType, OverloadChoice choice); /// \brief Simplify a type, by replacing type variables with either their /// fixed types (if available) or their representatives. /// /// The resulting types can be compared canonically, so long as additional /// type equivalence requirements aren't introduced between comparisons. Type simplifyType(Type type){ llvm::SmallPtrSet substituting; return simplifyType(type, substituting); } /// Given a ValueMember, UnresolvedValueMember, or TypeMember constraint, /// perform a lookup into the specified base type to find a candidate list. /// The list returned includes the viable candidates as well as the unviable /// ones (along with reasons why they aren't viable). /// /// If includeInaccessibleMembers is set to true, this burns compile time to /// try to identify and classify inaccessible members that may be being /// referenced. MemberLookupResult performMemberLookup(ConstraintKind constraintKind, DeclName memberName, Type baseTy, ConstraintLocator *memberLocator, bool includeInaccessibleMembers); private: /// \brief Simplify a type, by replacing type variables with either their /// fixed types (if available) or their representatives. /// /// \param type the type to be simplified. /// /// \param substituting the set of type variables that we're already /// substituting for. These type variables will not be substituted again, /// to avoid infinite recursion. /// /// The resulting types can be compared canonically, so long as additional /// type equivalence requirements aren't introduced between comparisons. Type simplifyType(Type type, llvm::SmallPtrSet &substituting); /// \brief Attempt to simplify the given construction constraint. /// /// \param valueType The type being constructed. /// /// \param fnType The argument type that will be the input to the /// valueType initializer and the result type will be the result of /// calling that initializer. /// /// \param flags Flags that indicate how the constraint should be /// simplified. /// /// \param locator Locator describing where this construction /// occurred. SolutionKind simplifyConstructionConstraint(Type valueType, FunctionType *fnType, unsigned flags, ConstraintLocator *locator); /// \brief Attempt to simplify the given conformance constraint. /// /// \param type The type being testing. /// \param protocol The protocol to which the type should conform. /// \param kind Either ConstraintKind::SelfObjectOfProtocol or /// ConstraintKind::ConformsTo. /// \param locator Locator describing where this constraint occurred. SolutionKind simplifyConformsToConstraint(Type type, ProtocolDecl *protocol, ConstraintKind kind, ConstraintLocatorBuilder locator, unsigned flags); /// \brief Attempt to simplify the given conformance constraint. /// /// \param type The type being testing. /// \param protocol The protocol or protocol composition type to which the /// type should conform. /// \param locator Locator describing where this constraint occurred. /// /// \param kind If this is SelfTypeOfProtocol, we allow an existential type /// that contains the protocol but does not conform to it (eg, due to /// associated types). SolutionKind simplifyConformsToConstraint(Type type, Type protocol, ConstraintKind kind, ConstraintLocatorBuilder locator, unsigned flags); /// Attempt to simplify a checked-cast constraint. SolutionKind simplifyCheckedCastConstraint(Type fromType, Type toType, ConstraintLocatorBuilder locator); /// \brief Attempt to simplify the given member constraint. SolutionKind simplifyMemberConstraint(const Constraint &constraint); /// \brief Attempt to simplify the optional object constraint. SolutionKind simplifyOptionalObjectConstraint(const Constraint &constraint); /// \brief Attempt to simplify the ApplicableFunction constraint. SolutionKind simplifyApplicableFnConstraint(const Constraint &constraint); /// \brief Attempt to simplify the given DynamicTypeOf constraint. SolutionKind simplifyDynamicTypeOfConstraint(const Constraint &constraint); /// \brief Attempt to simplify the given archetype constraint. SolutionKind simplifyArchetypeConstraint(const Constraint &constraint); /// \brief Attempt to simplify the given class constraint. SolutionKind simplifyClassConstraint(const Constraint &constraint); /// \brief Attempt to simplify the given bridge constraint. SolutionKind simplifyBridgedToObjectiveCConstraint(const Constraint &constraint); /// \brief Attempt to simplify the given defaultable constraint. SolutionKind simplifyDefaultableConstraint(const Constraint &c); /// \brief Simplify a conversion constraint by applying the given /// reduction rule, which is known to apply at the outermost level. SolutionKind simplifyRestrictedConstraint(ConversionRestrictionKind restriction, Type type1, Type type2, TypeMatchKind matchKind, unsigned flags, ConstraintLocatorBuilder locator); public: // FIXME: Public for use by static functions. /// \brief Simplify a conversion constraint with a fix applied to it. SolutionKind simplifyFixConstraint(Fix fix, Type type1, Type type2, TypeMatchKind matchKind, unsigned flags, ConstraintLocatorBuilder locator); public: /// \brief Simplify the system of constraints, by breaking down complex /// constraints into simpler constraints. /// /// The result of simplification is a constraint system that consisting of /// only simple constraints relating type variables to each other or /// directly to fixed types. There are no constraints that involve /// type constructors on both sides. the simplified constraint system may, /// of course, include type variables for which we have constraints but /// no fixed type. Such type variables are left to the solver to bind. /// /// \returns true if an error occurred, false otherwise. bool simplify(bool ContinueAfterFailures = false); /// \brief Simplify the given constraint. SolutionKind simplifyConstraint(const Constraint &constraint); private: /// \brief Solve the system of constraints after it has already been /// simplified. /// /// \param solutions The set of solutions to this system of constraints. /// /// \param allowFreeTypeVariables How to bind free type variables in /// the solution. /// /// \returns true if an error occurred, false otherwise. bool solveSimplified(SmallVectorImpl &solutions, FreeTypeVariableBinding allowFreeTypeVariables); public: /// \brief Solve the system of constraints. /// /// \param solutions The set of solutions to this system of constraints. /// /// \param allowFreeTypeVariables How to bind free type variables in /// the solution. /// /// \returns true if an error occurred, false otherwise. Note that multiple /// ambiguous solutions for the same constraint system are considered to be /// success by this API. bool solve(SmallVectorImpl &solutions, FreeTypeVariableBinding allowFreeTypeVariables = FreeTypeVariableBinding::Disallow); /// \brief Solve the system of constraints. /// /// \param solutions The set of solutions to this system of constraints. /// /// \param allowFreeTypeVariables How to bind free type variables in /// the solution. /// /// \returns true if there are no solutions bool solveRec(SmallVectorImpl &solutions, FreeTypeVariableBinding allowFreeTypeVariables); /// \brief Solve the system of constraints. /// /// \param allowFreeTypeVariables How to bind free type variables in /// the solution. /// /// \returns a solution if a single unambiguous one could be found, or None if /// ambiguous or unsolvable. Optional solveSingle(FreeTypeVariableBinding allowFreeTypeVariables = FreeTypeVariableBinding::Disallow); private: /// \brief Compare two solutions to the same set of constraints. /// /// \param cs The constraint system. /// \param solutions All of the solutions to the system. /// \param diff The differences among the solutions. /// \param idx1 The index of the first solution. /// \param idx2 The index of the second solution. static SolutionCompareResult compareSolutions(ConstraintSystem &cs, ArrayRef solutions, const SolutionDiff &diff, unsigned idx1, unsigned idx2); public: /// Increase the score of the given kind for the current (partial) solution /// along the. void increaseScore(ScoreKind kind); /// Determine whether this solution is guaranteed to be worse than the best /// solution found so far. bool worseThanBestSolution() const; /// \brief Given a set of viable solutions, find the best /// solution. /// /// \param solutions The set of viable solutions to consider. /// /// \param minimize If true, then in the case where there is no single /// best solution, minimize the set of solutions by removing any solutions /// that are identical to or worse than some other solution. This operation /// is quadratic. /// /// \returns The index of the best solution, or nothing if there was no /// best solution. Optional findBestSolution(SmallVectorImpl &solutions, bool minimize); /// \brief Apply a given solution to the expression, producing a fully /// type-checked expression. /// /// \param convertType the contextual type to which the /// expression should be converted, if any. /// \param discardedExpr if true, the result of the expression /// is contextually ignored. /// \param skipClosures if true, don't descend into bodies of /// non-single expression closures. Expr *applySolution(Solution &solution, Expr *expr, Type convertType, bool discardedExpr, bool suppressDiagnostics, bool skipClosures); /// \brief Apply a given solution to the expression to the top-level /// expression, producing a fully type-checked expression. Expr *applySolutionShallow(const Solution &solution, Expr *expr, bool suppressDiagnostics); /// \brief Obtain the specializations computed for a type variable. This is /// useful when emitting diagnostics for computed type variables. void getComputedBindings(TypeVariableType *tvt, SmallVectorImpl &bindings); /// Extract the base type from an array or slice type. /// \param type The array type to inspect. /// \returns the base type of the array. Type getBaseTypeForArrayType(TypeBase *type); /// Extract the base type from a set type. /// \param type The set type to inspect. /// \returns the base type of the set. Type getBaseTypeForSetType(TypeBase *type); /// \brief Set whether or not the expression being solved is too complex and /// has exceeded the solver's memory threshold. void setExpressionTooComplex(bool tc) { expressionExceededThreshold = tc; } /// \brief Reorder the disjunctive clauses for a given expression to /// increase the likelihood that a favored constraint will be successfully /// resolved before any others. void optimizeConstraints(Expr *e); /// \brief Determine if the expression being solved has exceeded the solver's /// memory threshold. bool getExpressionTooComplex() { return expressionExceededThreshold; } LLVM_ATTRIBUTE_DEPRECATED( void dump() LLVM_ATTRIBUTE_USED, "only for use within the debugger"); void print(raw_ostream &out); }; /// \brief Compute the shuffle required to map from a given tuple type to /// another tuple type. /// /// \param fromTuple The tuple type we're converting from, as represented by its /// TupleTypeElt members. /// /// \param toTuple The tuple type we're converting to, as represented by its /// TupleTypeElt members. /// /// \param sources Will be populated with information about the source of each /// of the elements for the result tuple. The indices into this array are the /// indices of the tuple type we're converting to, while the values are /// either one of the \c TupleShuffleExpr constants or are an index into the /// source tuple. /// /// \param variadicArgs Will be populated with all of the variadic arguments /// that will be placed into the variadic tuple element (i.e., at the index /// \c where \c consumed[i] is \c TupleShuffleExpr::Variadic). The values /// are indices into the source tuple. /// /// \returns true if no tuple conversion is possible, false otherwise. bool computeTupleShuffle(ArrayRef fromTuple, ArrayRef toTuple, SmallVectorImpl &sources, SmallVectorImpl &variadicArgs); static inline bool computeTupleShuffle(TupleType *fromTuple, TupleType *toTuple, SmallVectorImpl &sources, SmallVectorImpl &variadicArgs){ return computeTupleShuffle(fromTuple->getElements(), toTuple->getElements(), sources, variadicArgs); } /// \brief Return whether the function argument indicated by `locator` has a /// trailing closure. bool hasTrailingClosure(const ConstraintLocatorBuilder &locator); /// A call argument or parameter. struct LLVM_LIBRARY_VISIBILITY CallArgParam { /// The type of the argument or parameter. For a variadic parameter, /// this is the element type. Type Ty; // The label associated with the argument or parameter, if any. Identifier Label; /// Whether the parameter has a default argument. Not valid for arguments. bool HasDefaultArgument = false; /// Whether the parameter is variadic. Not valid for arguments. bool Variadic = false; /// Whether the argument or parameter has a label. bool hasLabel() const { return !Label.empty(); } }; /// Compute an argument or parameter type into an array of \c CallArgParams. /// /// \param type The type to decompose. SmallVector decomposeArgParamType(Type type); /// Turn a param list into a symbolic and printable representation that does not /// include the types, something like (: , b:, c:) std::string getParamListAsString(ArrayRef parameters); /// Describes the arguments to which a parameter binds. /// FIXME: This is an awful data structure. We want the equivalent of a /// TinyPtrVector for unsigned values. typedef SmallVector ParamBinding; /// Class used as the base for listeners to the \c matchCallArguments process. /// /// By default, none of the callbacks do anything. class MatchCallArgumentListener { public: virtual ~MatchCallArgumentListener(); /// Indicates that the argument at the given index does not match any /// parameter. /// /// \param argIdx The index of the extra argument. virtual void extraArgument(unsigned argIdx); /// Indicates that no argument was provided for the parameter at the given /// indices. /// /// \param paramIdx The index of the parameter that is missing an argument. virtual void missingArgument(unsigned paramIdx); /// Indicates that an argument is out-of-order with respect to a previously- /// seen argument. /// /// \param argIdx The argument that came too late in the argument list. /// \param prevArgIdx The argument that the \c argIdx should have preceded. virtual void outOfOrderArgument(unsigned argIdx, unsigned prevArgIdx); /// Indicates that the arguments need to be relabeled to match the parameters. /// /// \returns true to indicate that this should cause a failure, false /// otherwise. virtual bool relabelArguments(ArrayRef newNames); }; /// Match the call arguments (as described by the given argument type) to /// the parameters (as described by the given parameter type). /// /// \param argTuple The arguments. /// \param paramTuple The parameters. /// \param hasTrailingClosure Whether the last argument is a trailing closure. /// \param allowFixes Whether to allow fixes when matching arguments. /// /// \param listener Listener that will be notified when certain problems occur, /// e.g., to produce a diagnostic. /// /// \param parameterBindings Will be populated with the arguments that are /// bound to each of the parameters. /// \returns true if the call arguments could not be matched to the parameters. bool matchCallArguments(ArrayRef argTuple, ArrayRef paramTuple, bool hasTrailingClosure, bool allowFixes, MatchCallArgumentListener &listener, SmallVectorImpl ¶meterBindings); /// Simplify the given locator by zeroing in on the most specific /// subexpression described by the locator. /// /// This routine can also find the corresponding "target" locator, which /// typically provides the other end of a relational constraint. For example, /// if the primary locator refers to a function argument, the target locator /// will be set to refer to the corresponding function parameter. /// /// \param cs The constraint system in which the locator will be simplified. /// /// \param locator The locator to simplify. /// /// \param range Will be populated with an "interesting" range. /// /// \param targetLocator If non-null, will be set to a locator that describes /// the target of the input locator. /// /// \return the simplified locator. ConstraintLocator *simplifyLocator(ConstraintSystem &cs, ConstraintLocator *locator, SourceRange &range, ConstraintLocator **targetLocator = nullptr); void simplifyLocator(Expr *&anchor, ArrayRef &path, Expr *&targetAnchor, SmallVectorImpl &targetPath, SourceRange &range); } // end namespace constraints template TypeVariableType *TypeVariableType::getNew(const ASTContext &C, unsigned ID, Args &&...args) { // Allocate memory void *mem = C.Allocate(sizeof(TypeVariableType) + sizeof(Implementation), alignof(TypeVariableType), AllocationArena::ConstraintSolver); // Construct the type variable. auto *result = ::new (mem) TypeVariableType(C, ID); // Construct the implementation object. new (result+1) TypeVariableType::Implementation(std::forward(args)...); return result; } /// If the expression has the effect of a forced downcast, find the /// underlying forced downcast expression. ForcedCheckedCastExpr *findForcedDowncast(ASTContext &ctx, Expr *expr); } // end namespace swift #endif // LLVM_SWIFT_SEMA_CONSTRAINT_SYSTEM_H