| //===--- GenericSignatureBuilder.h - Generic signature builder --*- C++ -*-===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Support for collecting a set of generic requirements, whether they are |
| // explicitly stated, inferred from a type signature, or implied by other |
| // requirements, and computing the canonicalized, minimized generic signature |
| // from those requirements. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef SWIFT_GENERICSIGNATUREBUILDER_H |
| #define SWIFT_GENERICSIGNATUREBUILDER_H |
| |
| #include "swift/AST/Decl.h" |
| #include "swift/AST/DiagnosticEngine.h" |
| #include "swift/AST/Identifier.h" |
| #include "swift/AST/Types.h" |
| #include "swift/AST/TypeLoc.h" |
| #include "swift/Basic/LLVM.h" |
| #include "llvm/ADT/ArrayRef.h" |
| #include "llvm/ADT/FoldingSet.h" |
| #include "llvm/ADT/PointerUnion.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/ADT/MapVector.h" |
| #include "llvm/ADT/TinyPtrVector.h" |
| #include "llvm/Support/TrailingObjects.h" |
| #include <functional> |
| #include <memory> |
| |
| namespace swift { |
| |
| class DeclContext; |
| class DependentMemberType; |
| class GenericParamList; |
| class GenericSignature; |
| class GenericSignatureBuilder; |
| class GenericTypeParamType; |
| class LazyResolver; |
| class ModuleDecl; |
| class Pattern; |
| class ProtocolConformance; |
| class Requirement; |
| class RequirementRepr; |
| class SILModule; |
| class SourceLoc; |
| class SubstitutionMap; |
| class Type; |
| class TypeRepr; |
| class ASTContext; |
| class DiagnosticEngine; |
| |
| /// \brief Collects a set of requirements of generic parameters, both explicitly |
| /// stated and inferred, and determines the set of archetypes for each of |
| /// the generic parameters. |
| class GenericSignatureBuilder { |
| public: |
| /// Describes a potential archetype, which stands in for a generic parameter |
| /// type or some type derived from it. |
| class PotentialArchetype; |
| |
| using UnresolvedType = llvm::PointerUnion<PotentialArchetype *, Type>; |
| struct ResolvedType; |
| |
| using RequirementRHS = |
| llvm::PointerUnion3<Type, PotentialArchetype *, LayoutConstraint>; |
| |
| class RequirementSource; |
| |
| class FloatingRequirementSource; |
| |
| /// Describes a constraint that is bounded on one side by a concrete type. |
| struct ConcreteConstraint { |
| PotentialArchetype *archetype; |
| Type concreteType; |
| const RequirementSource *source; |
| }; |
| |
| /// Describes an equivalence class of potential archetypes. |
| struct EquivalenceClass { |
| /// Concrete type to which this equivalence class is equal. |
| /// |
| /// This is the semantic concrete type; the constraints as written |
| /// (or implied) are stored in \c concreteTypeConstraints; |
| Type concreteType; |
| |
| /// The same-type-to-concrete constraints written within this |
| /// equivalence class. |
| std::vector<ConcreteConstraint> concreteTypeConstraints; |
| |
| /// Superclass constraint, which requires that the type fulfilling the |
| /// requirements of this equivalence class to be the same as or a subtype |
| /// of this superclass. |
| Type superclass; |
| |
| /// Superclass constraints written within this equivalence class. |
| std::vector<ConcreteConstraint> superclassConstraints; |
| |
| /// The members of the equivalence class. |
| TinyPtrVector<PotentialArchetype *> members; |
| |
| /// Construct a new equivalence class containing only the given |
| /// potential archetype (which represents itself). |
| EquivalenceClass(PotentialArchetype *representative); |
| |
| /// Find a source of the same-type constraint that maps a potential |
| /// archetype in this equivalence class to a concrete type along with |
| /// that concrete type as written. |
| Optional<ConcreteConstraint> |
| findAnyConcreteConstraintAsWritten( |
| PotentialArchetype *preferredPA = nullptr) const; |
| |
| /// Find a source of the superclass constraint in this equivalence class |
| /// that has a type equivalence to \c superclass, along with that |
| /// superclass type as written. |
| Optional<ConcreteConstraint> |
| findAnySuperclassConstraintAsWritten( |
| PotentialArchetype *preferredPA = nullptr) const; |
| }; |
| |
| friend class RequirementSource; |
| |
| private: |
| class InferRequirementsWalker; |
| friend class InferRequirementsWalker; |
| friend class GenericSignature; |
| |
| ASTContext &Context; |
| DiagnosticEngine &Diags; |
| struct Implementation; |
| std::unique_ptr<Implementation> Impl; |
| |
| GenericSignatureBuilder(const GenericSignatureBuilder &) = delete; |
| GenericSignatureBuilder &operator=(const GenericSignatureBuilder &) = delete; |
| |
| /// Update an existing constraint source reference when another constraint |
| /// source was found to produce the same constraint. Only the better |
| /// constraint source will be kept. |
| /// |
| /// \returns true if the new constraint source was better, false otherwise. |
| bool updateRequirementSource(const RequirementSource *&existingSource, |
| const RequirementSource *newSource); |
| |
| /// Retrieve the constraint source conformance for the superclass constraint |
| /// of the given potential archetype (if present) to the given protocol. |
| /// |
| /// \param pa The potential archetype whose superclass constraint is being |
| /// queried. |
| /// |
| /// \param proto The protocol to which we are establishing conformance. |
| /// |
| /// \param protoSource The requirement source for the conformance to the |
| /// given protocol. |
| const RequirementSource *resolveSuperConformance( |
| GenericSignatureBuilder::PotentialArchetype *pa, |
| ProtocolDecl *proto, |
| const RequirementSource *&protoSource); |
| |
| /// \brief Add a new conformance requirement specifying that the given |
| /// potential archetype conforms to the given protocol. |
| bool addConformanceRequirement(PotentialArchetype *T, |
| ProtocolDecl *Proto, |
| const RequirementSource *Source); |
| |
| bool addConformanceRequirement(PotentialArchetype *T, |
| ProtocolDecl *Proto, |
| const RequirementSource *Source, |
| llvm::SmallPtrSetImpl<ProtocolDecl *> &Visited); |
| |
| public: |
| /// \brief Add a new same-type requirement between two fully resolved types |
| /// (output of \c GenericSignatureBuilder::resolve). |
| /// |
| /// If the types refer to two concrete types that are fundamentally |
| /// incompatible (e.g. \c Foo<Bar<T>> and \c Foo<Baz>), \c diagnoseMismatch is |
| /// called with the two types that don't match (\c Bar<T> and \c Baz for the |
| /// previous example). |
| bool |
| addSameTypeRequirement(ResolvedType paOrT1, ResolvedType paOrT2, |
| FloatingRequirementSource Source, |
| llvm::function_ref<void(Type, Type)> diagnoseMismatch); |
| |
| /// \brief Add a new same-type requirement between two fully resolved types |
| /// (output of GenericSignatureBuilder::resolve). |
| /// |
| /// The two types must not be incompatible concrete types. |
| bool addSameTypeRequirement(ResolvedType paOrT1, ResolvedType paOrT2, |
| FloatingRequirementSource Source); |
| |
| /// \brief Add a new same-type requirement between two unresolved types. |
| /// |
| /// The types are resolved with \c GenericSignatureBuilder::resolve, and must |
| /// not be incompatible concrete types. |
| bool addSameTypeRequirement(UnresolvedType paOrT1, UnresolvedType paOrT2, |
| FloatingRequirementSource Source); |
| |
| /// \brief Add a new same-type requirement between two unresolved types. |
| /// |
| /// The types are resolved with \c GenericSignatureBuilder::resolve. \c |
| /// diagnoseMismatch is called if the two types refer to incompatible concrete |
| /// types. |
| bool |
| addSameTypeRequirement(UnresolvedType paOrT1, UnresolvedType paOrT2, |
| FloatingRequirementSource Source, |
| llvm::function_ref<void(Type, Type)> diagnoseMismatch); |
| |
| /// Update the superclass for the equivalence class of \c T. |
| /// |
| /// This assumes that the constraint has already been recorded |
| bool updateSuperclass(PotentialArchetype *T, |
| Type superclass, |
| const RequirementSource *source); |
| |
| private: |
| /// \brief Add a new superclass requirement specifying that the given |
| /// potential archetype has the given type as an ancestor. |
| bool addSuperclassRequirement(PotentialArchetype *T, |
| Type Superclass, |
| const RequirementSource *Source); |
| |
| /// \brief Add a new conformance requirement specifying that the given |
| /// potential archetypes are equivalent. |
| bool addSameTypeRequirementBetweenArchetypes(PotentialArchetype *T1, |
| PotentialArchetype *T2, |
| const RequirementSource *Source); |
| |
| /// \brief Add a new conformance requirement specifying that the given |
| /// potential archetype is bound to a concrete type. |
| bool addSameTypeRequirementToConcrete(PotentialArchetype *T, |
| Type Concrete, |
| const RequirementSource *Source); |
| |
| /// \brief Add a new same-type requirement specifying that the given two |
| /// types should be the same. |
| /// |
| /// \param diagnoseMismatch Callback invoked when the types in the same-type |
| /// requirement mismatch. |
| bool addSameTypeRequirementBetweenConcrete( |
| Type T1, Type T2, FloatingRequirementSource Source, |
| llvm::function_ref<void(Type, Type)> diagnoseMismatch); |
| |
| /// Add the requirements placed on the given type parameter |
| /// to the given potential archetype. |
| bool addInheritedRequirements(TypeDecl *decl, PotentialArchetype *pa, |
| const RequirementSource *parentSource, |
| llvm::SmallPtrSetImpl<ProtocolDecl *> &visited); |
| |
| /// Visit all of the potential archetypes. |
| template<typename F> |
| void visitPotentialArchetypes(F f); |
| |
| void markPotentialArchetypeRecursive(PotentialArchetype *pa, |
| ProtocolDecl *proto, |
| const RequirementSource *source); |
| |
| public: |
| /// Construct a new generic signature builder. |
| /// |
| /// \param lookupConformance Conformance-lookup routine that will be used |
| /// to satisfy conformance requirements for concrete types. |
| explicit GenericSignatureBuilder(ASTContext &ctx, |
| std::function<GenericFunction> lookupConformance); |
| |
| GenericSignatureBuilder(GenericSignatureBuilder &&); |
| ~GenericSignatureBuilder(); |
| |
| /// Retrieve the AST context. |
| ASTContext &getASTContext() const { return Context; } |
| |
| /// Retrieve the conformance-lookup function used by this generic signature builder. |
| std::function<GenericFunction> getLookupConformanceFn() const; |
| |
| /// Retrieve the lazy resolver, if there is one. |
| LazyResolver *getLazyResolver() const; |
| |
| /// Enumerate the requirements that describe the signature of this |
| /// generic signature builder. |
| /// |
| /// \param f A function object that will be passed each requirement |
| /// and requirement source. |
| void enumerateRequirements(llvm::function_ref< |
| void (RequirementKind kind, |
| PotentialArchetype *archetype, |
| RequirementRHS constraint, |
| const RequirementSource *source)> f); |
| |
| public: |
| /// \brief Add a new generic parameter for which there may be requirements. |
| void addGenericParameter(GenericTypeParamDecl *GenericParam); |
| |
| /// Add the requirements placed on the given abstract type parameter |
| /// to the given potential archetype. |
| /// |
| /// \returns true if an error occurred, false otherwise. |
| bool addGenericParameterRequirements(GenericTypeParamDecl *GenericParam); |
| |
| /// \brief Add a new generic parameter for which there may be requirements. |
| void addGenericParameter(GenericTypeParamType *GenericParam); |
| |
| /// \brief Add a new requirement. |
| /// |
| /// \returns true if this requirement makes the set of requirements |
| /// inconsistent, in which case a diagnostic will have been issued. |
| bool addRequirement(const RequirementRepr *Req, |
| const RequirementSource *source = nullptr, |
| const SubstitutionMap *subMap = nullptr); |
| |
| /// \brief Add an already-checked requirement. |
| /// |
| /// Adding an already-checked requirement cannot fail. This is used to |
| /// re-inject requirements from outer contexts. |
| /// |
| /// \returns true if this requirement makes the set of requirements |
| /// inconsistent, in which case a diagnostic will have been issued. |
| bool addRequirement(const Requirement &req, FloatingRequirementSource source); |
| |
| bool addRequirement(const Requirement &req, FloatingRequirementSource source, |
| llvm::SmallPtrSetImpl<ProtocolDecl *> &Visited); |
| |
| /// \brief Add a new requirement. |
| /// |
| /// \returns true if this requirement makes the set of requirements |
| /// inconsistent, in which case a diagnostic will have been issued. |
| |
| bool addLayoutRequirement(PotentialArchetype *PAT, |
| LayoutConstraint Layout, |
| const RequirementSource *Source); |
| |
| /// \brief Add all of a generic signature's parameters and requirements. |
| void addGenericSignature(GenericSignature *sig); |
| |
| /// \brief Build the generic signature. |
| GenericSignature *getGenericSignature(); |
| |
| /// Infer requirements from the given type, recursively. |
| /// |
| /// This routine infers requirements from a type that occurs within the |
| /// signature of a generic function. For example, given: |
| /// |
| /// \code |
| /// func f<K, V>(dict : Dictionary<K, V>) { ... } |
| /// \endcode |
| /// |
| /// where \c Dictionary requires that its key type be \c Hashable, |
| /// the requirement \c K : Hashable is inferred from the parameter type, |
| /// because the type \c Dictionary<K,V> cannot be formed without it. |
| void inferRequirements(TypeLoc type); |
| |
| /// Infer requirements from the given pattern, recursively. |
| /// |
| /// This routine infers requirements from a type that occurs within the |
| /// signature of a generic function. For example, given: |
| /// |
| /// \code |
| /// func f<K, V>(dict : Dictionary<K, V>) { ... } |
| /// \endcode |
| /// |
| /// where \c Dictionary requires that its key type be \c Hashable, |
| /// the requirement \c K : Hashable is inferred from the parameter type, |
| /// because the type \c Dictionary<K,V> cannot be formed without it. |
| void inferRequirements(ParameterList *params,GenericParamList *genericParams); |
| |
| /// Finalize the set of requirements, performing any remaining checking |
| /// required before generating archetypes. |
| /// |
| /// \param allowConcreteGenericParams If true, allow generic parameters to |
| /// be made concrete. |
| void finalize(SourceLoc loc, |
| ArrayRef<GenericTypeParamType *> genericParams, |
| bool allowConcreteGenericParams=false); |
| |
| /// Diagnose any remaining renames. |
| /// |
| /// \returns \c true if there were any remaining renames to diagnose. |
| bool diagnoseRemainingRenames(SourceLoc loc, |
| ArrayRef<GenericTypeParamType *> genericParams); |
| |
| private: |
| /// Describes the relationship between a given constraint and |
| /// the canonical constraint of the equivalence class. |
| enum class ConstraintRelation { |
| /// The constraint is unrelated. |
| /// |
| /// This is a conservative result that can be used when, for example, |
| /// we have incomplete information to make a determination. |
| Unrelated, |
| /// The constraint is redundant and can be removed without affecting the |
| /// semantics. |
| Redundant, |
| /// The constraint conflicts, meaning that the signature is erroneous. |
| Conflicting, |
| }; |
| |
| /// Check a list of concrete constraints, removing self-derived constraints |
| /// and diagnosing redundant constraints. |
| /// |
| /// \param isSuitableRepresentative Determines whether the given constraint |
| /// is a suitable representative. |
| /// |
| /// \param checkConstraint Checks the given constraint against the |
| /// canonical constraint to determine which diagnostics (if any) should be |
| /// emitted. |
| /// |
| /// \returns the representative constraint. |
| ConcreteConstraint checkConstraintList( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| std::vector<ConcreteConstraint> &constraints, |
| llvm::function_ref<bool(const ConcreteConstraint &)> |
| isSuitableRepresentative, |
| llvm::function_ref<ConstraintRelation(Type)> |
| checkConstraint, |
| Optional<Diag<unsigned, Type, Type, Type>> |
| conflictingDiag, |
| Diag<Type, Type> redundancyDiag, |
| Diag<bool, Type, Type> otherNoteDiag); |
| |
| /// Check for redundant concrete type constraints within the equivalence |
| /// class of the given potential archetype. |
| void checkRedundantConcreteTypeConstraints( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| PotentialArchetype *pa); |
| |
| /// Check for redundant superclass constraints within the equivalence |
| /// class of the given potential archetype. |
| void checkRedundantSuperclassConstraints( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| PotentialArchetype *pa); |
| |
| public: |
| /// \brief Resolve the given type to the potential archetype it names. |
| /// |
| /// This routine will synthesize nested types as required to refer to a |
| /// potential archetype, even in cases where no requirement specifies the |
| /// requirement for such an archetype. FIXME: The failure to include such a |
| /// requirement will be diagnosed at some point later (when the types in the |
| /// signature are fully resolved). |
| /// |
| /// For any type that cannot refer to an archetype, this routine returns null. |
| PotentialArchetype *resolveArchetype(Type type); |
| |
| /// \brief Resolve the given type as far as this Builder knows how. |
| /// |
| /// This returns either a non-typealias potential archetype or a Type, if \c |
| /// type is concrete. |
| // FIXME: the hackTypeFromGenericTypeAlias is just temporarily patching over |
| // problems with generic typealiases (see the comment on the ResolvedType |
| // function) |
| ResolvedType resolve(UnresolvedType type, |
| bool hackTypeFromGenericTypeAlias = false); |
| |
| /// \brief Dump all of the requirements, both specified and inferred. |
| LLVM_ATTRIBUTE_DEPRECATED( |
| void dump(), |
| "only for use within the debugger"); |
| |
| /// Dump all of the requirements to the given output stream. |
| void dump(llvm::raw_ostream &out); |
| }; |
| |
| /// Describes how a generic signature determines a requirement, from its origin |
| /// in some requirement written in the source, inferred through a path of |
| /// other implications (e.g., introduced by a particular protocol). |
| /// |
| /// Requirement sources are uniqued within a generic signature builder. |
| class GenericSignatureBuilder::RequirementSource final |
| : public llvm::FoldingSetNode, |
| private llvm::TrailingObjects<RequirementSource, PotentialArchetype *> { |
| |
| public: |
| enum Kind : uint8_t { |
| /// A requirement stated explicitly, e.g., in a where clause or type |
| /// parameter declaration. |
| /// |
| /// Explicitly-stated requirement can be tied to a specific requirement |
| /// in a 'where' clause (which stores a \c RequirementRepr), a type in an |
| /// 'inheritance' clause (which stores a \c TypeRepr), or can be 'abstract', |
| /// , e.g., due to canonicalization, deserialization, or other |
| /// source-independent formulation. |
| /// |
| /// This is a root requirement source. |
| Explicit, |
| |
| /// A requirement inferred from part of the signature of a declaration, |
| /// e.g., the type of a generic function. For example: |
| /// |
| /// func f<T>(_: Set<T>) { } // infers T: Hashable |
| /// |
| /// This is a root requirement source, which can be described by a |
| /// \c TypeRepr. |
| Inferred, |
| |
| /// A requirement for the creation of the requirement signature of a |
| /// protocol. |
| /// |
| /// This is a root requirement source, which is described by the protocol |
| /// whose requirement signature is being computed. |
| RequirementSignatureSelf, |
| |
| /// The requirement came from two nested types of the equivalent types whose |
| /// names match. |
| /// |
| /// This is a root requirement source. |
| NestedTypeNameMatch, |
| |
| /// The requirement is a protocol requirement. |
| /// |
| /// This stores the protocol that introduced the requirement. |
| ProtocolRequirement, |
| |
| /// A requirement that was resolved via a superclass requirement. |
| /// |
| /// This stores the \c ProtocolConformance* used to resolve the |
| /// requirement. |
| Superclass, |
| |
| /// A requirement that was resolved for a nested type via its parent |
| /// type. |
| Parent, |
| |
| /// A requirement that was resolved for a nested type via a same-type-to- |
| /// concrete constraint. |
| /// |
| /// This stores the \c ProtocolConformance* used to resolve the |
| /// requirement. |
| Concrete, |
| }; |
| |
| /// The kind of requirement source. |
| const Kind kind; |
| |
| private: |
| /// The kind of storage we have. |
| enum class StorageKind : uint8_t { |
| RootArchetype, |
| TypeRepr, |
| RequirementRepr, |
| ProtocolDecl, |
| ProtocolConformance, |
| AssociatedTypeDecl, |
| }; |
| |
| /// The kind of storage we have. |
| const StorageKind storageKind; |
| |
| /// The actual storage, described by \c storageKind. |
| union { |
| /// The root archetype. |
| PotentialArchetype *rootArchetype; |
| |
| /// The type representation describing where the requirement came from. |
| const TypeRepr *typeRepr; |
| |
| /// Where a requirement came from. |
| const RequirementRepr *requirementRepr; |
| |
| /// The protocol being described. |
| ProtocolDecl *protocol; |
| |
| /// A protocol conformance used to satisfy the requirement. |
| ProtocolConformance *conformance; |
| |
| /// An associated type to which a requirement is being applied. |
| AssociatedTypeDecl *assocType; |
| } storage; |
| |
| friend TrailingObjects; |
| |
| /// The trailing potential archetype, for |
| size_t numTrailingObjects(OverloadToken<PotentialArchetype *>) const { |
| switch (kind) { |
| case RequirementSignatureSelf: |
| return 1; |
| |
| case Explicit: |
| case Inferred: |
| return storageKind == StorageKind::RootArchetype ? 0 : 1; |
| |
| case NestedTypeNameMatch: |
| case ProtocolRequirement: |
| case Superclass: |
| case Parent: |
| case Concrete: |
| return 0; |
| } |
| } |
| |
| /// Determines whether we have been provided with an acceptable storage kind |
| /// for the given requirement source kind. |
| static bool isAcceptableStorageKind(Kind kind, StorageKind storageKind); |
| |
| /// Retrieve the opaque storage as a single pointer, for use in uniquing. |
| const void *getOpaqueStorage() const; |
| |
| /// Retrieve the extra opaque storage as a single pointer, for use in |
| /// uniquing. |
| const void *getExtraOpaqueStorage() const; |
| |
| /// Whether this kind of requirement source is a root. |
| static bool isRootKind(Kind kind) { |
| switch (kind) { |
| case Explicit: |
| case Inferred: |
| case RequirementSignatureSelf: |
| case NestedTypeNameMatch: |
| return true; |
| |
| case ProtocolRequirement: |
| case Superclass: |
| case Parent: |
| case Concrete: |
| return false; |
| } |
| } |
| |
| public: |
| /// The "parent" of this requirement source. |
| /// |
| /// The chain of parent requirement sources will eventually terminate in a |
| /// requirement source with one of the "root" kinds. |
| const RequirementSource * const parent; |
| |
| RequirementSource(Kind kind, const RequirementSource *parent, |
| PotentialArchetype *rootArchetype) |
| : kind(kind), storageKind(StorageKind::RootArchetype), parent(parent) { |
| assert((static_cast<bool>(parent) != isRootKind(kind)) && |
| "Root RequirementSource should not have parent (or vice versa)"); |
| assert(isAcceptableStorageKind(kind, storageKind) && |
| "RequirementSource kind/storageKind mismatch"); |
| |
| storage.rootArchetype = rootArchetype; |
| } |
| |
| RequirementSource(Kind kind, const RequirementSource *parent, |
| const TypeRepr *typeRepr) |
| : kind(kind), storageKind(StorageKind::TypeRepr), parent(parent) { |
| assert((static_cast<bool>(parent) != isRootKind(kind)) && |
| "Root RequirementSource should not have parent (or vice versa)"); |
| assert(isAcceptableStorageKind(kind, storageKind) && |
| "RequirementSource kind/storageKind mismatch"); |
| |
| storage.typeRepr = typeRepr; |
| } |
| |
| RequirementSource(Kind kind, const RequirementSource *parent, |
| const RequirementRepr *requirementRepr) |
| : kind(kind), storageKind(StorageKind::RequirementRepr), parent(parent) { |
| assert((static_cast<bool>(parent) != isRootKind(kind)) && |
| "Root RequirementSource should not have parent (or vice versa)"); |
| assert(isAcceptableStorageKind(kind, storageKind) && |
| "RequirementSource kind/storageKind mismatch"); |
| |
| storage.requirementRepr = requirementRepr; |
| } |
| |
| RequirementSource(Kind kind, const RequirementSource *parent, |
| ProtocolDecl *protocol) |
| : kind(kind), storageKind(StorageKind::ProtocolDecl), parent(parent) { |
| assert((static_cast<bool>(parent) != isRootKind(kind)) && |
| "Root RequirementSource should not have parent (or vice versa)"); |
| assert(isAcceptableStorageKind(kind, storageKind) && |
| "RequirementSource kind/storageKind mismatch"); |
| |
| storage.protocol = protocol; |
| } |
| |
| RequirementSource(Kind kind, const RequirementSource *parent, |
| ProtocolConformance *conformance) |
| : kind(kind), storageKind(StorageKind::ProtocolConformance), |
| parent(parent) { |
| assert((static_cast<bool>(parent) != isRootKind(kind)) && |
| "Root RequirementSource should not have parent (or vice versa)"); |
| assert(isAcceptableStorageKind(kind, storageKind) && |
| "RequirementSource kind/storageKind mismatch"); |
| |
| storage.conformance = conformance; |
| } |
| |
| RequirementSource(Kind kind, const RequirementSource *parent, |
| AssociatedTypeDecl *assocType) |
| : kind(kind), storageKind(StorageKind::AssociatedTypeDecl), |
| parent(parent) { |
| assert((static_cast<bool>(parent) != isRootKind(kind)) && |
| "Root RequirementSource should not have parent (or vice versa)"); |
| assert(isAcceptableStorageKind(kind, storageKind) && |
| "RequirementSource kind/storageKind mismatch"); |
| |
| storage.assocType = assocType; |
| } |
| |
| public: |
| /// Retrieve an abstract requirement source. |
| static const RequirementSource *forAbstract(PotentialArchetype *root); |
| |
| /// Retrieve a requirement source representing an explicit requirement |
| /// stated in an 'inheritance' clause. |
| static const RequirementSource *forExplicit(PotentialArchetype *root, |
| const TypeRepr *typeRepr); |
| |
| /// Retrieve a requirement source representing an explicit requirement |
| /// stated in an 'where' clause. |
| static const RequirementSource *forExplicit( |
| PotentialArchetype *root, |
| const RequirementRepr *requirementRepr); |
| |
| /// Retrieve a requirement source representing a requirement that is |
| /// inferred from some part of a generic declaration's signature, e.g., the |
| /// parameter or result type of a generic function. |
| static const RequirementSource *forInferred(PotentialArchetype *root, |
| const TypeRepr *typeRepr); |
| |
| /// Retrieve a requirement source representing the requirement signature |
| /// computation for a protocol. |
| static const RequirementSource *forRequirementSignature( |
| PotentialArchetype *root, |
| ProtocolDecl *protocol); |
| |
| /// Retrieve a requirement source for nested type name matches. |
| static const RequirementSource *forNestedTypeNameMatch( |
| PotentialArchetype *root); |
| |
| /// A requirement source that describes that a requirement comes from a |
| /// requirement of the given protocol described by the parent. |
| const RequirementSource *viaAbstractProtocolRequirement( |
| GenericSignatureBuilder &builder, |
| ProtocolDecl *protocol) const; |
| |
| /// A requirement source that describes that a requirement that is resolved |
| /// via a superclass requirement. |
| const RequirementSource *viaSuperclass( |
| GenericSignatureBuilder &builder, |
| ProtocolConformance *conformance) const; |
| |
| /// A requirement source that describes that a requirement that is resolved |
| /// via a same-type-to-concrete requirement. |
| const RequirementSource *viaConcrete(GenericSignatureBuilder &builder, |
| ProtocolConformance *conformance) const; |
| |
| /// A constraint source that describes that a constraint that is resolved |
| /// for a nested type via a constraint on its parent. |
| /// |
| /// \param assocType the associated type that |
| const RequirementSource *viaParent(GenericSignatureBuilder &builder, |
| AssociatedTypeDecl *assocType) const; |
| |
| /// Retrieve the potential archetype at the root. |
| PotentialArchetype *getRootPotentialArchetype() const; |
| |
| /// Whether the requirement can be derived from something in its path. |
| /// |
| /// Derived requirements will not be recorded in a minimized generic |
| /// signature, because the information can be re-derived by following the |
| /// path. |
| bool isDerivedRequirement() const; |
| |
| /// Whether the requirement is derived via some concrete conformance, e.g., |
| /// a concrete type's conformance to a protocol or a superclass's conformance |
| /// to a protocol. |
| bool isDerivedViaConcreteConformance() const; |
| |
| /// Determine whether the given derived requirement \c source, when rooted at |
| /// the potential archetype \c pa, is actually derived from the same |
| /// requirement. Such "self-derived" requirements do not make the original |
| /// requirement redundant, because without said original requirement, the |
| /// derived requirement ceases to hold. |
| bool isSelfDerivedSource(PotentialArchetype *pa) const; |
| |
| /// Retrieve a source location that corresponds to the requirement. |
| SourceLoc getLoc() const; |
| |
| /// Compare two requirement sources to determine which has the more |
| /// optimal path. |
| /// |
| /// \returns -1 if the \c this is better, 1 if the \c other is better, and 0 |
| /// if they are equivalent in length. |
| int compare(const RequirementSource *other) const; |
| |
| /// Retrieve the type representation for this requirement, if there is one. |
| const TypeRepr *getTypeRepr() const { |
| if (storageKind != StorageKind::TypeRepr) return nullptr; |
| return storage.typeRepr; |
| } |
| |
| /// Retrieve the requirement representation for this requirement, if there is |
| /// one. |
| const RequirementRepr *getRequirementRepr() const { |
| if (storageKind != StorageKind::RequirementRepr) return nullptr; |
| return storage.requirementRepr; |
| } |
| |
| /// Retrieve the protocol for this requirement, if there is one. |
| ProtocolDecl *getProtocolDecl() const; |
| |
| /// Retrieve the protocol conformance for this requirement, if there is one. |
| ProtocolConformance *getProtocolConformance() const { |
| if (storageKind != StorageKind::ProtocolConformance) return nullptr; |
| return storage.conformance; |
| } |
| |
| /// Retrieve the associated type declaration for this requirement, if there |
| /// is one. |
| AssociatedTypeDecl *getAssociatedType() const { |
| if (storageKind != StorageKind::AssociatedTypeDecl) return nullptr; |
| return storage.assocType; |
| } |
| |
| /// Profiling support for \c FoldingSet. |
| void Profile(llvm::FoldingSetNodeID &ID) { |
| Profile(ID, kind, parent, getOpaqueStorage(), getExtraOpaqueStorage()); |
| } |
| |
| /// Profiling support for \c FoldingSet. |
| static void Profile(llvm::FoldingSetNodeID &ID, Kind kind, |
| const RequirementSource *parent, const void *storage, |
| const void *extraStorage) { |
| ID.AddInteger(kind); |
| ID.AddPointer(parent); |
| ID.AddPointer(storage); |
| ID.AddPointer(extraStorage); |
| } |
| |
| LLVM_ATTRIBUTE_DEPRECATED( |
| void dump() const, |
| "only for use within the debugger"); |
| |
| /// Dump the requirement source. |
| void dump(llvm::raw_ostream &out, SourceManager *SrcMgr, |
| unsigned indent) const; |
| |
| LLVM_ATTRIBUTE_DEPRECATED( |
| void print() const, |
| "only for use within the debugger"); |
| |
| /// Print the requirement source (shorter form) |
| void print(llvm::raw_ostream &out, SourceManager *SrcMgr) const; |
| }; |
| |
| /// A requirement source that potentially lacks a root \c PotentialArchetype. |
| /// The root will be supplied as soon as the appropriate dependent type is |
| /// resolved. |
| class GenericSignatureBuilder::FloatingRequirementSource { |
| enum Kind { |
| /// A fully-resolved requirement source, which does not need a root. |
| Resolved, |
| /// An explicit requirement source lacking a root. |
| Explicit, |
| /// An inferred requirement source lacking a root. |
| Inferred |
| } kind; |
| |
| using Storage = |
| llvm::PointerUnion3<const RequirementSource *, const TypeRepr *, |
| const RequirementRepr *>; |
| |
| Storage storage; |
| |
| FloatingRequirementSource(Kind kind, Storage storage) |
| : kind(kind), storage(storage) { } |
| |
| public: |
| /// Implicit conversion from a resolved requirement source. |
| FloatingRequirementSource(const RequirementSource *source) |
| : FloatingRequirementSource(Resolved, source) { } |
| |
| static FloatingRequirementSource forAbstract() { |
| return { Explicit, Storage() }; |
| } |
| |
| static FloatingRequirementSource forExplicit(const TypeRepr *typeRepr) { |
| return { Explicit, typeRepr }; |
| } |
| |
| static FloatingRequirementSource forExplicit( |
| const RequirementRepr *requirementRepr) { |
| return { Explicit, requirementRepr }; |
| } |
| |
| static FloatingRequirementSource forInferred(const TypeRepr *typeRepr) { |
| return { Inferred, typeRepr }; |
| } |
| |
| /// Retrieve the complete requirement source rooted at the given potential |
| /// archetype. |
| const RequirementSource *getSource(PotentialArchetype *pa) const; |
| |
| /// Retrieve the source location for this requirement. |
| SourceLoc getLoc() const; |
| }; |
| |
| class GenericSignatureBuilder::PotentialArchetype { |
| /// The parent of this potential archetype (for a nested type) or the |
| /// generic signature builder in which this root resides. |
| llvm::PointerUnion<PotentialArchetype*, GenericSignatureBuilder*> parentOrBuilder; |
| |
| /// The identifier describing this particular archetype. |
| /// |
| /// \c parentOrBuilder determines whether we have a nested type vs. a root, |
| /// while `isUnresolvedNestedType` determines whether we have an unresolved |
| /// nested type (vs. a resolved one); |
| union PAIdentifier { |
| /// The name of an unresolved, nested type. |
| Identifier name; |
| |
| /// The associated type or typealias for a resolved nested type. |
| TypeDecl *assocTypeOrAlias; |
| |
| /// The generic parameter key for a root. |
| GenericParamKey genericParam; |
| |
| PAIdentifier(Identifier name) : name(name) { } |
| |
| PAIdentifier(AssociatedTypeDecl *assocType) |
| : assocTypeOrAlias(assocType) { } |
| |
| PAIdentifier(TypeAliasDecl *typeAlias) |
| : assocTypeOrAlias(typeAlias) { } |
| |
| PAIdentifier(GenericParamKey genericParam) : genericParam(genericParam) { } |
| } identifier; |
| |
| /// \brief The representative of the equivalence class of potential archetypes |
| /// to which this potential archetype belongs, or (for the representative) |
| /// the equivalence class itself. |
| mutable llvm::PointerUnion<PotentialArchetype *, EquivalenceClass *> |
| representativeOrEquivClass; |
| |
| /// Same-type constraints between this potential archetype and any other |
| /// archetype in its equivalence class. |
| llvm::MapVector<PotentialArchetype *, const RequirementSource *> |
| SameTypeConstraints; |
| |
| /// \brief The list of protocols to which this archetype will conform. |
| llvm::MapVector<ProtocolDecl *, const RequirementSource *> ConformsTo; |
| |
| /// \brief The layout constraint of this archetype, if specified. |
| LayoutConstraint Layout; |
| |
| /// The source of the layout constraint requirement. |
| const RequirementSource *LayoutSource = nullptr; |
| |
| /// \brief The set of nested types of this archetype. |
| /// |
| /// For a given nested type name, there may be multiple potential archetypes |
| /// corresponding to different associated types (from different protocols) |
| /// that share a name. |
| llvm::MapVector<Identifier, llvm::TinyPtrVector<PotentialArchetype *>> |
| NestedTypes; |
| |
| /// Whether this is an unresolved nested type. |
| unsigned isUnresolvedNestedType : 1; |
| |
| /// \brief Recursively conforms to itself. |
| unsigned IsRecursive : 1; |
| |
| /// Whether this potential archetype is invalid, e.g., because it could not |
| /// be resolved. |
| unsigned Invalid : 1; |
| |
| /// Whether we have detected recursion during the substitution of |
| /// the concrete type. |
| unsigned RecursiveConcreteType : 1; |
| |
| /// Whether we have detected recursion during the substitution of |
| /// the superclass type. |
| unsigned RecursiveSuperclassType : 1; |
| |
| /// Whether we have diagnosed a rename. |
| unsigned DiagnosedRename : 1; |
| |
| /// If we have renamed this (nested) type due to typo correction, |
| /// the old name. |
| Identifier OrigName; |
| |
| /// \brief Construct a new potential archetype for an unresolved |
| /// associated type. |
| PotentialArchetype(PotentialArchetype *parent, Identifier name) |
| : parentOrBuilder(parent), identifier(name), isUnresolvedNestedType(true), |
| IsRecursive(false), Invalid(false), |
| RecursiveConcreteType(false), RecursiveSuperclassType(false), |
| DiagnosedRename(false) |
| { |
| assert(parent != nullptr && "Not an associated type?"); |
| } |
| |
| /// \brief Construct a new potential archetype for an associated type. |
| PotentialArchetype(PotentialArchetype *parent, AssociatedTypeDecl *assocType) |
| : parentOrBuilder(parent), identifier(assocType), |
| isUnresolvedNestedType(false), IsRecursive(false), Invalid(false), |
| RecursiveConcreteType(false), |
| RecursiveSuperclassType(false), DiagnosedRename(false) |
| { |
| assert(parent != nullptr && "Not an associated type?"); |
| } |
| |
| /// \brief Construct a new potential archetype for a type alias. |
| PotentialArchetype(PotentialArchetype *parent, TypeAliasDecl *typeAlias) |
| : parentOrBuilder(parent), identifier(typeAlias), |
| isUnresolvedNestedType(false), |
| IsRecursive(false), Invalid(false), |
| RecursiveConcreteType(false), |
| RecursiveSuperclassType(false), DiagnosedRename(false) |
| { |
| assert(parent != nullptr && "Not an associated type?"); |
| } |
| |
| /// \brief Construct a new potential archetype for a generic parameter. |
| PotentialArchetype(GenericSignatureBuilder *builder, GenericParamKey genericParam) |
| : parentOrBuilder(builder), identifier(genericParam), |
| isUnresolvedNestedType(false), |
| IsRecursive(false), Invalid(false), |
| RecursiveConcreteType(false), RecursiveSuperclassType(false), |
| DiagnosedRename(false) |
| { |
| } |
| |
| /// \brief Retrieve the representative for this archetype, performing |
| /// path compression on the way. |
| PotentialArchetype *getRepresentative() const; |
| |
| /// Retrieve the generic signature builder with which this archetype is |
| /// associated. |
| GenericSignatureBuilder *getBuilder() const { |
| const PotentialArchetype *pa = this; |
| while (auto parent = pa->getParent()) |
| pa = parent; |
| return pa->parentOrBuilder.get<GenericSignatureBuilder *>(); |
| } |
| |
| friend class GenericSignatureBuilder; |
| friend class GenericSignature; |
| |
| /// \brief Retrieve the debug name of this potential archetype. |
| std::string getDebugName() const; |
| |
| public: |
| ~PotentialArchetype(); |
| |
| /// Retrieve the parent of this potential archetype, which will be non-null |
| /// when this potential archetype is an associated type. |
| PotentialArchetype *getParent() const { |
| return parentOrBuilder.dyn_cast<PotentialArchetype *>(); |
| } |
| |
| /// Retrieve the associated type to which this potential archetype |
| /// has been resolved. |
| AssociatedTypeDecl *getResolvedAssociatedType() const { |
| assert(getParent() && "Not an associated type"); |
| if (isUnresolvedNestedType) |
| return nullptr; |
| |
| return dyn_cast<AssociatedTypeDecl>(identifier.assocTypeOrAlias); |
| } |
| |
| /// Resolve the potential archetype to the given associated type. |
| void resolveAssociatedType(AssociatedTypeDecl *assocType, |
| GenericSignatureBuilder &builder); |
| |
| /// Determine whether this is a generic parameter. |
| bool isGenericParam() const { |
| return parentOrBuilder.is<GenericSignatureBuilder *>(); |
| } |
| |
| /// Retrieve the generic parameter key for a potential archetype that |
| /// represents this potential archetype. |
| /// |
| /// \pre \c isGenericParam() |
| GenericParamKey getGenericParamKey() const { |
| assert(isGenericParam() && "Not a generic parameter"); |
| return identifier.genericParam; |
| } |
| |
| /// Retrieve the generic parameter key for the generic parameter at the |
| /// root of this potential archetype. |
| GenericParamKey getRootGenericParamKey() const { |
| if (auto parent = getParent()) |
| return parent->getRootGenericParamKey(); |
| |
| return getGenericParamKey(); |
| } |
| |
| /// Retrieve the name of a nested potential archetype. |
| Identifier getNestedName() const { |
| assert(getParent() && "Not a nested type"); |
| if (isUnresolvedNestedType) |
| return identifier.name; |
| |
| return identifier.assocTypeOrAlias->getName(); |
| } |
| |
| /// Retrieve the type alias. |
| TypeAliasDecl *getTypeAliasDecl() const { |
| assert(getParent() && "not a nested type"); |
| if (isUnresolvedNestedType) |
| return nullptr; |
| |
| return dyn_cast<TypeAliasDecl>(identifier.assocTypeOrAlias); |
| } |
| |
| /// Retrieve the set of protocols to which this type conforms. |
| llvm::MapVector<ProtocolDecl *, const RequirementSource *> & |
| getConformsTo() { |
| return ConformsTo; |
| } |
| |
| /// Add a conformance to this potential archetype. |
| /// |
| /// \returns true if the conformance was new, false if it already existed. |
| bool addConformance(ProtocolDecl *proto, bool updateExistingSource, |
| const RequirementSource *source, |
| GenericSignatureBuilder &builder); |
| |
| /// Retrieve the superclass of this archetype. |
| Type getSuperclass() const { |
| if (auto equiv = getEquivalenceClassIfPresent()) |
| return equiv->superclass; |
| |
| return nullptr; |
| } |
| |
| /// Retrieve the layout constraint of this archetype. |
| LayoutConstraint getLayout() const { return Layout; } |
| |
| /// Retrieve the requirement source for the layout constraint requirement. |
| const RequirementSource *getLayoutSource() const { |
| return LayoutSource; |
| } |
| |
| /// Retrieve the set of nested types. |
| const llvm::MapVector<Identifier, llvm::TinyPtrVector<PotentialArchetype *>> & |
| getNestedTypes() const{ |
| return NestedTypes; |
| } |
| |
| /// \brief Determine the nesting depth of this potential archetype, e.g., |
| /// the number of associated type references. |
| unsigned getNestingDepth() const; |
| |
| /// Retrieve the equivalence class, if it's already present. |
| /// |
| /// Otherwise, return null. |
| EquivalenceClass *getEquivalenceClassIfPresent() const { |
| return getRepresentative()->representativeOrEquivClass |
| .dyn_cast<EquivalenceClass *>(); |
| } |
| |
| /// Retrieve or create the equivalence class. |
| EquivalenceClass *getOrCreateEquivalenceClass() const; |
| |
| /// Retrieve the equivalence class containing this potential archetype. |
| TinyPtrVector<PotentialArchetype *> getEquivalenceClassMembers() const { |
| if (auto equivClass = getEquivalenceClassIfPresent()) |
| return equivClass->members; |
| |
| return TinyPtrVector<PotentialArchetype *>( |
| const_cast<PotentialArchetype *>(this)); |
| } |
| |
| /// \brief Retrieve the potential archetype to be used as the anchor for |
| /// potential archetype computations. |
| PotentialArchetype *getArchetypeAnchor(GenericSignatureBuilder &builder); |
| |
| /// Add a same-type constraint between this archetype and the given |
| /// other archetype. |
| void addSameTypeConstraint(PotentialArchetype *otherPA, |
| const RequirementSource *source); |
| |
| /// Retrieve the same-type constraints. |
| llvm::iterator_range< |
| std::vector<std::pair<PotentialArchetype *, const RequirementSource *>> |
| ::const_iterator> |
| getSameTypeConstraints() const { |
| return llvm::make_range(SameTypeConstraints.begin(), |
| SameTypeConstraints.end()); |
| } |
| |
| /// \brief Retrieve (or create) a nested type with the given name. |
| PotentialArchetype *getNestedType(Identifier Name, |
| GenericSignatureBuilder &builder); |
| |
| /// \brief Retrieve (or create) a nested type with a known associated type. |
| PotentialArchetype *getNestedType(AssociatedTypeDecl *assocType, |
| GenericSignatureBuilder &builder); |
| |
| /// \brief Retrieve (or build) the type corresponding to the potential |
| /// archetype within the given generic environment. |
| Type getTypeInContext(GenericSignatureBuilder &builder, |
| GenericEnvironment *genericEnv); |
| |
| /// Retrieve the dependent type that describes this potential |
| /// archetype. |
| /// |
| /// \param genericParams The set of generic parameters to use in the resulting |
| /// dependent type. |
| /// |
| /// \param allowUnresolved If true, allow the result to contain |
| /// \c DependentMemberType types with a name but no specific associated |
| /// type. |
| Type getDependentType(ArrayRef<GenericTypeParamType *> genericParams, |
| bool allowUnresolved); |
| |
| /// True if the potential archetype has been bound by a concrete type |
| /// constraint. |
| bool isConcreteType() const { |
| if (auto equivClass = getEquivalenceClassIfPresent()) |
| return static_cast<bool>(equivClass->concreteType); |
| |
| return false; |
| } |
| |
| /// Get the concrete type this potential archetype is constrained to. |
| Type getConcreteType() const { |
| if (auto equivClass = getEquivalenceClassIfPresent()) |
| return equivClass->concreteType; |
| |
| return Type(); |
| } |
| |
| void setIsRecursive() { IsRecursive = true; } |
| bool isRecursive() const { return IsRecursive; } |
| |
| bool isInvalid() const { return Invalid; } |
| |
| void setInvalid() { Invalid = true; } |
| |
| /// Determine whether this archetype was renamed due to typo |
| /// correction. If so, \c getName() retrieves the new name. |
| bool wasRenamed() const { return !OrigName.empty(); } |
| |
| /// Note that this potential archetype was is going to be renamed (due to typo |
| /// correction), saving the old name. |
| void saveNameForRenaming() { |
| OrigName = getNestedName(); |
| } |
| |
| /// For a renamed potential archetype, retrieve the original name. |
| Identifier getOriginalName() const { |
| assert(wasRenamed()); |
| return OrigName; |
| } |
| |
| /// Whether we already diagnosed this rename. |
| bool alreadyDiagnosedRename() const { return DiagnosedRename; } |
| |
| /// Note that we already diagnosed this rename. |
| void setAlreadyDiagnosedRename() { DiagnosedRename = true; } |
| |
| LLVM_ATTRIBUTE_DEPRECATED( |
| void dump() const, |
| "only for use within the debugger"); |
| |
| void dump(llvm::raw_ostream &Out, SourceManager *SrcMgr, |
| unsigned Indent) const; |
| |
| friend class GenericSignatureBuilder; |
| }; |
| |
| } // end namespace swift |
| |
| #endif |