| //===--- GenericSignatureBuilder.cpp - Generic Requirement Builder --------===// |
| // |
| // 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, both explicitly stated |
| // and inferred, and computing the archetypes and required witness tables from |
| // those requirements. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "swift/AST/GenericSignatureBuilder.h" |
| #include "swift/AST/ASTContext.h" |
| #include "swift/AST/DiagnosticsSema.h" |
| #include "swift/AST/DiagnosticEngine.h" |
| #include "swift/AST/ExistentialLayout.h" |
| #include "swift/AST/GenericEnvironment.h" |
| #include "swift/AST/Module.h" |
| #include "swift/AST/ParameterList.h" |
| #include "swift/AST/ProtocolConformance.h" |
| #include "swift/AST/TypeMatcher.h" |
| #include "swift/AST/TypeRepr.h" |
| #include "swift/AST/TypeWalker.h" |
| #include "swift/Basic/Defer.h" |
| #include "swift/Basic/Statistic.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallString.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <algorithm> |
| |
| using namespace swift; |
| using llvm::DenseMap; |
| |
| namespace { |
| typedef GenericSignatureBuilder::RequirementSource RequirementSource; |
| typedef GenericSignatureBuilder::FloatingRequirementSource |
| FloatingRequirementSource; |
| typedef GenericSignatureBuilder::ConstraintResult ConstraintResult; |
| typedef GenericSignatureBuilder::PotentialArchetype PotentialArchetype; |
| typedef GenericSignatureBuilder::ConcreteConstraint ConcreteConstraint; |
| template<typename T> using Constraint = |
| GenericSignatureBuilder::Constraint<T>; |
| typedef GenericSignatureBuilder::EquivalenceClass EquivalenceClass; |
| typedef EquivalenceClass::DerivedSameTypeComponent DerivedSameTypeComponent; |
| |
| } // end anonymous namespace |
| |
| struct GenericSignatureBuilder::Implementation { |
| /// Function used to look up conformances. |
| std::function<GenericFunction> LookupConformance; |
| |
| /// The generic parameters that this generic signature builder is working |
| /// with. |
| SmallVector<GenericTypeParamType *, 4> GenericParams; |
| |
| /// The potential archetypes for the generic parameters in \c GenericParams. |
| SmallVector<PotentialArchetype *, 4> PotentialArchetypes; |
| |
| /// The number of nested types that haven't yet been resolved to archetypes. |
| /// Once all requirements have been added, this will be zero in well-formed |
| /// code. |
| unsigned NumUnresolvedNestedTypes = 0; |
| |
| /// The nested types that have been renamed. |
| SmallVector<PotentialArchetype *, 4> RenamedNestedTypes; |
| |
| /// The requirement sources used in this generic signature builder. |
| llvm::FoldingSet<RequirementSource> RequirementSources; |
| |
| /// The set of requirements that have been delayed for some reason. |
| SmallVector<DelayedRequirement, 4> DelayedRequirements; |
| |
| #ifndef NDEBUG |
| /// Whether we've already finalized the builder. |
| bool finalized = false; |
| #endif |
| }; |
| |
| #pragma mark Requirement sources |
| |
| #ifndef NDEBUG |
| bool RequirementSource::isAcceptableStorageKind(Kind kind, |
| StorageKind storageKind) { |
| switch (kind) { |
| case Explicit: |
| case Inferred: |
| case RequirementSignatureSelf: |
| case NestedTypeNameMatch: |
| switch (storageKind) { |
| case StorageKind::RootArchetype: |
| return true; |
| |
| case StorageKind::StoredType: |
| case StorageKind::ProtocolConformance: |
| case StorageKind::AssociatedTypeDecl: |
| return false; |
| } |
| |
| case Parent: |
| switch (storageKind) { |
| case StorageKind::AssociatedTypeDecl: |
| return true; |
| |
| case StorageKind::RootArchetype: |
| case StorageKind::StoredType: |
| case StorageKind::ProtocolConformance: |
| return false; |
| } |
| |
| case ProtocolRequirement: |
| case InferredProtocolRequirement: |
| switch (storageKind) { |
| case StorageKind::StoredType: |
| return true; |
| |
| case StorageKind::RootArchetype: |
| case StorageKind::ProtocolConformance: |
| case StorageKind::AssociatedTypeDecl: |
| return false; |
| } |
| |
| case Superclass: |
| case Concrete: |
| switch (storageKind) { |
| case StorageKind::ProtocolConformance: |
| return true; |
| |
| case StorageKind::RootArchetype: |
| case StorageKind::StoredType: |
| case StorageKind::AssociatedTypeDecl: |
| return false; |
| } |
| } |
| |
| llvm_unreachable("Unhandled RequirementSourceKind in switch."); |
| } |
| #endif |
| |
| const void *RequirementSource::getOpaqueStorage1() const { |
| switch (storageKind) { |
| case StorageKind::RootArchetype: |
| return storage.rootArchetype; |
| |
| case StorageKind::ProtocolConformance: |
| return storage.conformance; |
| |
| case StorageKind::StoredType: |
| return storage.type; |
| |
| case StorageKind::AssociatedTypeDecl: |
| return storage.assocType; |
| } |
| |
| llvm_unreachable("Unhandled StorageKind in switch."); |
| } |
| |
| const void *RequirementSource::getOpaqueStorage2() const { |
| if (numTrailingObjects(OverloadToken<ProtocolDecl *>()) == 1) |
| return getTrailingObjects<ProtocolDecl *>()[0]; |
| if (numTrailingObjects(OverloadToken<WrittenRequirementLoc>()) == 1) |
| return getTrailingObjects<WrittenRequirementLoc>()[0].getOpaqueValue(); |
| |
| return nullptr; |
| } |
| |
| const void *RequirementSource::getOpaqueStorage3() const { |
| if (numTrailingObjects(OverloadToken<ProtocolDecl *>()) == 1 && |
| numTrailingObjects(OverloadToken<WrittenRequirementLoc>()) == 1) |
| return getTrailingObjects<WrittenRequirementLoc>()[0].getOpaqueValue(); |
| |
| return nullptr; |
| } |
| |
| bool RequirementSource::isInferredRequirement() const { |
| for (auto source = this; source; source = source->parent) { |
| switch (source->kind) { |
| case Inferred: |
| case InferredProtocolRequirement: |
| return true; |
| |
| case Concrete: |
| case Explicit: |
| case NestedTypeNameMatch: |
| case Parent: |
| case ProtocolRequirement: |
| case RequirementSignatureSelf: |
| case Superclass: |
| break; |
| } |
| } |
| |
| return false; |
| } |
| |
| unsigned RequirementSource::classifyDiagKind() const { |
| if (isInferredRequirement()) return 2; |
| if (isDerivedRequirement()) return 1; |
| return 0; |
| } |
| |
| bool RequirementSource::isDerivedRequirement() const { |
| switch (kind) { |
| case Explicit: |
| case Inferred: |
| return false; |
| |
| case NestedTypeNameMatch: |
| case Parent: |
| case Superclass: |
| case Concrete: |
| case RequirementSignatureSelf: |
| return true; |
| |
| case ProtocolRequirement: |
| case InferredProtocolRequirement: |
| // Requirements based on protocol requirements are derived unless they are |
| // direct children of the requirement-signature source, in which case we |
| // need to keep them for the requirement signature. |
| return parent->kind != RequirementSignatureSelf; |
| } |
| |
| llvm_unreachable("Unhandled RequirementSourceKind in switch."); |
| } |
| |
| bool RequirementSource::isSelfDerivedSource(PotentialArchetype *pa, |
| bool &derivedViaConcrete) const { |
| derivedViaConcrete = false; |
| |
| // If it's not a derived requirement, it's not self-derived. |
| if (!isDerivedRequirement()) return false; |
| |
| return visitPotentialArchetypesAlongPath( |
| [&](PotentialArchetype *currentPA, const RequirementSource *source) { |
| switch (source->kind) { |
| case RequirementSource::Explicit: |
| case RequirementSource::Inferred: |
| case RequirementSource::RequirementSignatureSelf: |
| for (auto parent = currentPA->getParent(); parent; |
| parent = parent->getParent()) { |
| if (parent->isInSameEquivalenceClassAs(pa)) |
| return true; |
| } |
| |
| return false; |
| |
| case RequirementSource::Parent: |
| return currentPA->isInSameEquivalenceClassAs(pa); |
| |
| case RequirementSource::ProtocolRequirement: |
| case RequirementSource::InferredProtocolRequirement: |
| // Note whether we saw derivation through a concrete type. |
| if (currentPA->isConcreteType()) |
| derivedViaConcrete = true; |
| return false; |
| |
| case RequirementSource::NestedTypeNameMatch: |
| case RequirementSource::Concrete: |
| case RequirementSource::Superclass: |
| return false; |
| } |
| }) == nullptr; |
| } |
| |
| /// Replace 'Self' in the given dependent type (\c depTy) with the given |
| /// potential archetype, producing a new potential archetype that refers to |
| /// the nested type. This limited operation makes sure that it does not |
| /// create any new potential archetypes along the way, so it should only be |
| /// used in cases where we're reconstructing something that we know exists. |
| static PotentialArchetype *replaceSelfWithPotentialArchetype( |
| PotentialArchetype *selfPA, Type depTy) { |
| if (auto depMemTy = depTy->getAs<DependentMemberType>()) { |
| // Recurse to produce the potential archetype for the base. |
| auto basePA = replaceSelfWithPotentialArchetype(selfPA, |
| depMemTy->getBase()); |
| |
| PotentialArchetype *nestedPAByName = nullptr; |
| |
| auto assocType = depMemTy->getAssocType(); |
| auto name = depMemTy->getName(); |
| auto findNested = [&](PotentialArchetype *pa) -> PotentialArchetype * { |
| const auto &nested = pa->getNestedTypes(); |
| auto found = nested.find(name); |
| |
| if (found == nested.end()) return nullptr; |
| if (found->second.empty()) return nullptr; |
| |
| // Note that we've found a nested PA by name. |
| if (!nestedPAByName) { |
| nestedPAByName = found->second.front(); |
| } |
| |
| // If we don't have an associated type to look for, we're done. |
| if (!assocType) return nestedPAByName; |
| |
| // Look for a nested PA matching the associated type. |
| for (auto nestedPA : found->second) { |
| if (nestedPA->getResolvedAssociatedType() == assocType) |
| return nestedPA; |
| } |
| |
| return nullptr; |
| }; |
| |
| // First, look in the base potential archetype for the member we want. |
| if (auto result = findNested(basePA)) |
| return result; |
| |
| // Otherwise, look elsewhere in the equivalence class of the base potential |
| // archetype. |
| for (auto otherBasePA : basePA->getEquivalenceClassMembers()) { |
| if (otherBasePA == basePA) continue; |
| |
| if (auto result = findNested(otherBasePA)) |
| return result; |
| } |
| |
| assert(nestedPAByName && "Didn't find the associated type we wanted"); |
| return nestedPAByName; |
| } |
| |
| assert(depTy->is<GenericTypeParamType>() && "missing Self?"); |
| return selfPA; |
| } |
| |
| bool RequirementSource::isSelfDerivedConformance( |
| PotentialArchetype *currentPA, |
| ProtocolDecl *proto, |
| bool &derivedViaConcrete) const { |
| /// Keep track of all of the requirements we've seen along the way. If |
| /// we see the same requirement twice, it's a self-derived conformance. |
| llvm::DenseSet<std::pair<PotentialArchetype *, ProtocolDecl *>> |
| constraintsSeen; |
| |
| // Note that we've now seen a new constraint, returning true if we've seen |
| // it before. |
| auto addConstraint = [&](PotentialArchetype *pa, ProtocolDecl *proto) { |
| return !constraintsSeen.insert({pa->getRepresentative(), proto}).second; |
| }; |
| |
| // Insert our end state. |
| constraintsSeen.insert({currentPA->getRepresentative(), proto}); |
| |
| derivedViaConcrete = false; |
| bool sawProtocolRequirement = false; |
| |
| PotentialArchetype *rootPA = nullptr; |
| auto resultPA = visitPotentialArchetypesAlongPath( |
| [&](PotentialArchetype *parentPA, |
| const RequirementSource *source) { |
| switch (source->kind) { |
| case ProtocolRequirement: |
| case InferredProtocolRequirement: { |
| // Note that we've seen a protocol requirement. |
| sawProtocolRequirement = true; |
| |
| // If the base has been made concrete, note it. |
| if (parentPA->isConcreteType()) |
| derivedViaConcrete = true; |
| |
| // The parent potential archetype must conform to the protocol in which |
| // this requirement resides. |
| return addConstraint(parentPA, source->getProtocolDecl()); |
| } |
| |
| case Concrete: |
| case Superclass: |
| case Parent: |
| return false; |
| case Explicit: |
| case Inferred: |
| case NestedTypeNameMatch: |
| case RequirementSignatureSelf: |
| rootPA = parentPA; |
| return false; |
| } |
| }); |
| |
| // If we saw a constraint twice, it's self-derived. |
| if (!resultPA) return true; |
| |
| // If we haven't seen a protocol requirement, we're done. |
| if (!sawProtocolRequirement) return false; |
| |
| // The root archetype might be a nested type, which implies constraints |
| // for each of the protocols of the associated types referenced (if any). |
| for (auto pa = rootPA; pa->getParent(); pa = pa->getParent()) { |
| if (auto assocType = pa->getResolvedAssociatedType()) { |
| if (addConstraint(pa->getParent(), assocType->getProtocol())) |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| #define REQUIREMENT_SOURCE_FACTORY_BODY(ProfileArgs, ConstructorArgs, \ |
| NumProtocolDecls, WrittenReq) \ |
| llvm::FoldingSetNodeID nodeID; \ |
| Profile ProfileArgs; \ |
| \ |
| void *insertPos = nullptr; \ |
| if (auto known = \ |
| builder.Impl->RequirementSources.FindNodeOrInsertPos(nodeID, \ |
| insertPos)) \ |
| return known; \ |
| \ |
| unsigned size = \ |
| totalSizeToAlloc<ProtocolDecl *, WrittenRequirementLoc>( \ |
| NumProtocolDecls, \ |
| WrittenReq.isNull()? 0 : 1); \ |
| void *mem = ::operator new(size); \ |
| auto result = new (mem) RequirementSource ConstructorArgs; \ |
| builder.Impl->RequirementSources.InsertNode(result, insertPos); \ |
| return result |
| |
| const RequirementSource *RequirementSource::forAbstract( |
| PotentialArchetype *root) { |
| auto &builder = *root->getBuilder(); |
| REQUIREMENT_SOURCE_FACTORY_BODY( |
| (nodeID, Explicit, nullptr, root, nullptr, nullptr), |
| (Explicit, root, nullptr, WrittenRequirementLoc()), |
| 0, WrittenRequirementLoc()); |
| } |
| |
| const RequirementSource *RequirementSource::forExplicit( |
| PotentialArchetype *root, |
| GenericSignatureBuilder::WrittenRequirementLoc writtenLoc) { |
| auto &builder = *root->getBuilder(); |
| REQUIREMENT_SOURCE_FACTORY_BODY( |
| (nodeID, Explicit, nullptr, root, |
| writtenLoc.getOpaqueValue(), nullptr), |
| (Explicit, root, nullptr, writtenLoc), |
| 0, writtenLoc); |
| } |
| |
| const RequirementSource *RequirementSource::forInferred( |
| PotentialArchetype *root, |
| const TypeRepr *typeRepr) { |
| WrittenRequirementLoc writtenLoc = typeRepr; |
| auto &builder = *root->getBuilder(); |
| REQUIREMENT_SOURCE_FACTORY_BODY( |
| (nodeID, Inferred, nullptr, root, |
| writtenLoc.getOpaqueValue(), nullptr), |
| (Inferred, root, nullptr, writtenLoc), |
| 0, writtenLoc); |
| } |
| |
| const RequirementSource *RequirementSource::forRequirementSignature( |
| PotentialArchetype *root, |
| ProtocolDecl *protocol) { |
| auto &builder = *root->getBuilder(); |
| REQUIREMENT_SOURCE_FACTORY_BODY( |
| (nodeID, RequirementSignatureSelf, nullptr, root, |
| protocol, nullptr), |
| (RequirementSignatureSelf, root, protocol, |
| WrittenRequirementLoc()), |
| 1, WrittenRequirementLoc()); |
| |
| } |
| |
| const RequirementSource *RequirementSource::forNestedTypeNameMatch( |
| PotentialArchetype *root) { |
| auto &builder = *root->getBuilder(); |
| REQUIREMENT_SOURCE_FACTORY_BODY( |
| (nodeID, NestedTypeNameMatch, nullptr, root, |
| nullptr, nullptr), |
| (NestedTypeNameMatch, root, nullptr, |
| WrittenRequirementLoc()), |
| 0, WrittenRequirementLoc()); |
| } |
| |
| const RequirementSource *RequirementSource::viaProtocolRequirement( |
| GenericSignatureBuilder &builder, Type dependentType, |
| ProtocolDecl *protocol, |
| bool inferred, |
| GenericSignatureBuilder::WrittenRequirementLoc writtenLoc) const { |
| REQUIREMENT_SOURCE_FACTORY_BODY( |
| (nodeID, |
| inferred ? InferredProtocolRequirement |
| : ProtocolRequirement, |
| this, |
| dependentType.getPointer(), protocol, |
| writtenLoc.getOpaqueValue()), |
| (inferred ? InferredProtocolRequirement |
| : ProtocolRequirement, |
| this, dependentType, |
| protocol, writtenLoc), |
| 1, writtenLoc); |
| } |
| |
| const RequirementSource *RequirementSource::viaSuperclass( |
| GenericSignatureBuilder &builder, |
| ProtocolConformance *conformance) const { |
| REQUIREMENT_SOURCE_FACTORY_BODY( |
| (nodeID, Superclass, this, conformance, |
| nullptr, nullptr), |
| (Superclass, this, conformance), |
| 0, WrittenRequirementLoc()); |
| } |
| |
| const RequirementSource *RequirementSource::viaConcrete( |
| GenericSignatureBuilder &builder, |
| ProtocolConformance *conformance) const { |
| REQUIREMENT_SOURCE_FACTORY_BODY( |
| (nodeID, Concrete, this, conformance, nullptr, nullptr), |
| (Concrete, this, conformance), |
| 0, WrittenRequirementLoc()); |
| } |
| |
| const RequirementSource *RequirementSource::viaParent( |
| GenericSignatureBuilder &builder, |
| AssociatedTypeDecl *assocType) const { |
| REQUIREMENT_SOURCE_FACTORY_BODY( |
| (nodeID, Parent, this, assocType, nullptr, nullptr), |
| (Parent, this, assocType), |
| 0, WrittenRequirementLoc()); |
| } |
| |
| #undef REQUIREMENT_SOURCE_FACTORY_BODY |
| |
| const RequirementSource *RequirementSource::getRoot() const { |
| auto root = this; |
| while (auto parent = root->parent) |
| root = parent; |
| return root; |
| } |
| |
| PotentialArchetype *RequirementSource::getRootPotentialArchetype() const { |
| /// Find the root. |
| auto root = getRoot(); |
| |
| // We're at the root, so it's in the inline storage. |
| assert(root->storageKind == StorageKind::RootArchetype); |
| return root->storage.rootArchetype; |
| } |
| |
| PotentialArchetype *RequirementSource::getAffectedPotentialArchetype() const { |
| return visitPotentialArchetypesAlongPath( |
| [](PotentialArchetype *, const RequirementSource *) { |
| return false; |
| }); |
| } |
| |
| PotentialArchetype * |
| RequirementSource::visitPotentialArchetypesAlongPath( |
| llvm::function_ref<bool(PotentialArchetype *, |
| const RequirementSource *)> visitor) const { |
| switch (kind) { |
| case RequirementSource::Parent: { |
| auto parentPA = parent->visitPotentialArchetypesAlongPath(visitor); |
| if (!parentPA) return nullptr; |
| |
| if (visitor(parentPA, this)) return nullptr; |
| |
| return replaceSelfWithPotentialArchetype( |
| parentPA, |
| getAssociatedType()->getDeclaredInterfaceType()); |
| } |
| |
| case RequirementSource::NestedTypeNameMatch: |
| case RequirementSource::Explicit: |
| case RequirementSource::Inferred: |
| case RequirementSource::RequirementSignatureSelf: { |
| auto rootPA = getRootPotentialArchetype(); |
| if (visitor(rootPA, this)) return nullptr; |
| |
| return rootPA; |
| } |
| |
| case RequirementSource::Concrete: |
| case RequirementSource::Superclass: |
| return parent->visitPotentialArchetypesAlongPath(visitor); |
| |
| case RequirementSource::ProtocolRequirement: |
| case RequirementSource::InferredProtocolRequirement: { |
| auto parentPA = parent->visitPotentialArchetypesAlongPath(visitor); |
| if (!parentPA) return nullptr; |
| |
| if (visitor(parentPA, this)) return nullptr; |
| |
| return replaceSelfWithPotentialArchetype(parentPA, getStoredType()); |
| } |
| } |
| } |
| |
| Type RequirementSource::getStoredType() const { |
| switch (storageKind) { |
| case StorageKind::RootArchetype: |
| case StorageKind::ProtocolConformance: |
| case StorageKind::AssociatedTypeDecl: |
| return Type(); |
| |
| case StorageKind::StoredType: |
| return storage.type; |
| } |
| |
| llvm_unreachable("Unhandled StorageKind in switch."); |
| } |
| |
| ProtocolDecl *RequirementSource::getProtocolDecl() const { |
| switch (storageKind) { |
| case StorageKind::RootArchetype: |
| if (kind == RequirementSignatureSelf) |
| return getTrailingObjects<ProtocolDecl *>()[0]; |
| return nullptr; |
| |
| case StorageKind::StoredType: |
| if (isProtocolRequirement()) |
| return getTrailingObjects<ProtocolDecl *>()[0]; |
| return nullptr; |
| |
| case StorageKind::ProtocolConformance: |
| if (storage.conformance) |
| return storage.conformance->getProtocol(); |
| |
| return nullptr; |
| |
| case StorageKind::AssociatedTypeDecl: |
| return storage.assocType->getProtocol(); |
| } |
| |
| llvm_unreachable("Unhandled StorageKind in switch."); |
| } |
| |
| SourceLoc RequirementSource::getLoc() const { |
| // Don't produce locations for protocol requirements unless the parent is |
| // the protocol self. |
| // FIXME: We should have a better notion of when to emit diagnostics |
| // for a particular requirement, rather than turning on/off location info. |
| // Locations that fall into this category should be advisory, emitted via |
| // notes rather than as the normal location. |
| if (isProtocolRequirement() && parent && |
| parent->kind != RequirementSignatureSelf) |
| return parent->getLoc(); |
| |
| if (auto typeRepr = getTypeRepr()) |
| return typeRepr->getStartLoc(); |
| |
| if (auto requirementRepr = getRequirementRepr()) { |
| switch (requirementRepr->getKind()) { |
| case RequirementReprKind::LayoutConstraint: |
| case RequirementReprKind::TypeConstraint: |
| return requirementRepr->getColonLoc(); |
| |
| case RequirementReprKind::SameType: |
| return requirementRepr->getEqualLoc(); |
| } |
| } |
| if (parent) |
| return parent->getLoc(); |
| |
| if (kind == RequirementSignatureSelf) |
| return getProtocolDecl()->getLoc(); |
| |
| return SourceLoc(); |
| } |
| |
| /// Compute the path length of a requirement source, counting only the number |
| /// of \c ProtocolRequirement elements. |
| static unsigned sourcePathLength(const RequirementSource *source) { |
| unsigned count = 0; |
| for (; source; source = source->parent) { |
| if (source->isProtocolRequirement()) |
| ++count; |
| } |
| return count; |
| } |
| |
| /// Check whether we have a NestedTypeNameMatch/ProtocolRequirement requirement |
| /// pair, in which case we prefer the RequirementSignature. |
| /// |
| /// This is part of staging out NestedTypeNameMatch requirement sources in |
| /// favor of something more principled. |
| static int isNestedTypeNameMatchAndRequirementSignaturePair( |
| const RequirementSource *lhs, |
| const RequirementSource *rhs) { |
| if (lhs->getRoot()->kind == RequirementSource::NestedTypeNameMatch && |
| rhs->isProtocolRequirement()) |
| return +1; |
| |
| if (rhs->getRoot()->kind == RequirementSource::NestedTypeNameMatch && |
| lhs->isProtocolRequirement()) |
| return -1; |
| |
| return 0; |
| } |
| |
| int RequirementSource::compare(const RequirementSource *other) const { |
| // FIXME: Egregious hack while we phase out NestedTypeNameMatch |
| if (int compare = |
| isNestedTypeNameMatchAndRequirementSignaturePair(this, other)) |
| return compare; |
| |
| // Prefer the derived option, if there is one. |
| bool thisIsDerived = this->isDerivedRequirement(); |
| bool otherIsDerived = other->isDerivedRequirement(); |
| if (thisIsDerived != otherIsDerived) |
| return thisIsDerived ? -1 : +1; |
| |
| // Prefer the shorter path. |
| unsigned thisLength = sourcePathLength(this); |
| unsigned otherLength = sourcePathLength(other); |
| if (thisLength != otherLength) |
| return thisLength < otherLength ? -1 : +1; |
| |
| // FIXME: Arbitrary hack to allow later requirement sources to stomp on |
| // earlier ones. We need a proper ordering here. |
| return +1; |
| } |
| |
| void RequirementSource::dump() const { |
| dump(llvm::errs(), nullptr, 0); |
| llvm::errs() << "\n"; |
| } |
| |
| /// Dump the constraint source. |
| void RequirementSource::dump(llvm::raw_ostream &out, SourceManager *srcMgr, |
| unsigned indent) const { |
| // FIXME: Implement for real, so we actually dump the structure. |
| out.indent(indent); |
| print(out, srcMgr); |
| } |
| |
| void RequirementSource::print() const { |
| print(llvm::errs(), nullptr); |
| } |
| |
| void RequirementSource::print(llvm::raw_ostream &out, |
| SourceManager *srcMgr) const { |
| if (parent) { |
| parent->print(out, srcMgr); |
| out << " -> "; |
| } else { |
| auto pa = getRootPotentialArchetype(); |
| out << pa->getDebugName() << ": "; |
| } |
| |
| switch (kind) { |
| case Concrete: |
| out << "Concrete"; |
| break; |
| |
| case Explicit: |
| out << "Explicit"; |
| break; |
| |
| case Inferred: |
| out << "Inferred"; |
| break; |
| |
| case NestedTypeNameMatch: |
| out << "Nested type match"; |
| break; |
| |
| case Parent: |
| out << "Parent"; |
| break; |
| |
| case ProtocolRequirement: |
| out << "Protocol requirement"; |
| break; |
| |
| case InferredProtocolRequirement: |
| out << "Inferred protocol requirement"; |
| break; |
| |
| case RequirementSignatureSelf: |
| out << "Requirement signature self"; |
| break; |
| |
| case Superclass: |
| out << "Superclass"; |
| break; |
| } |
| |
| // Local function to dump a source location, if we can. |
| auto dumpSourceLoc = [&](SourceLoc loc) { |
| if (!srcMgr) return; |
| if (loc.isInvalid()) return; |
| |
| unsigned bufferID = srcMgr->findBufferContainingLoc(loc); |
| |
| auto lineAndCol = srcMgr->getLineAndColumn(loc, bufferID); |
| out << " @ " << lineAndCol.first << ':' << lineAndCol.second; |
| }; |
| |
| switch (storageKind) { |
| case StorageKind::RootArchetype: |
| break; |
| |
| case StorageKind::StoredType: |
| if (auto proto = getProtocolDecl()) { |
| out << " (via " << storage.type->getString() << " in " << proto->getName() |
| << ")"; |
| } |
| break; |
| |
| case StorageKind::ProtocolConformance: |
| if (storage.conformance) { |
| out << " (" << storage.conformance->getType()->getString() << ": " |
| << storage.conformance->getProtocol()->getName() << ")"; |
| } |
| break; |
| |
| case StorageKind::AssociatedTypeDecl: |
| out << " (" << storage.assocType->getProtocol()->getName() |
| << "::" << storage.assocType->getName() << ")"; |
| break; |
| } |
| |
| if (getTypeRepr() || getRequirementRepr()) { |
| dumpSourceLoc(getLoc()); |
| } |
| } |
| |
| /// Form the dependent type such that the given protocol's \c Self can be |
| /// replaced by \c basePA to reach \c pa. |
| static Type formProtocolRelativeType(ProtocolDecl *proto, |
| PotentialArchetype *basePA, |
| PotentialArchetype *pa) { |
| // Basis case: we've hit the base potential archetype. |
| if (basePA == pa) |
| return proto->getSelfInterfaceType(); |
| |
| // Recursive case: form a dependent member type. |
| auto baseType = formProtocolRelativeType(proto, basePA, pa->getParent()); |
| if (auto assocType = pa->getResolvedAssociatedType()) |
| return DependentMemberType::get(baseType, assocType); |
| |
| return DependentMemberType::get(baseType, pa->getNestedName()); |
| } |
| |
| const RequirementSource *FloatingRequirementSource::getSource( |
| PotentialArchetype *pa) const { |
| switch (kind) { |
| case Resolved: |
| return storage.get<const RequirementSource *>(); |
| |
| case Explicit: |
| if (auto requirementRepr = storage.dyn_cast<const RequirementRepr *>()) |
| return RequirementSource::forExplicit(pa, requirementRepr); |
| if (auto typeRepr = storage.dyn_cast<const TypeRepr *>()) |
| return RequirementSource::forExplicit(pa, typeRepr); |
| return RequirementSource::forAbstract(pa); |
| |
| case Inferred: |
| return RequirementSource::forInferred(pa, storage.get<const TypeRepr *>()); |
| |
| case AbstractProtocol: { |
| // Derive the dependent type on which this requirement was written. It is |
| // the path from the requirement source on which this requirement is based |
| // to the potential archetype on which the requirement is being placed. |
| auto baseSource = storage.get<const RequirementSource *>(); |
| auto baseSourcePA = |
| baseSource->getAffectedPotentialArchetype(); |
| |
| auto dependentType = |
| formProtocolRelativeType(protocolReq.protocol, baseSourcePA, pa); |
| |
| return storage.get<const RequirementSource *>() |
| ->viaProtocolRequirement(*pa->getBuilder(), dependentType, |
| protocolReq.protocol, protocolReq.inferred, |
| protocolReq.written); |
| } |
| |
| case NestedTypeNameMatch: |
| return RequirementSource::forNestedTypeNameMatch(pa); |
| } |
| |
| llvm_unreachable("Unhandled FloatingPointRequirementSourceKind in switch."); |
| } |
| |
| SourceLoc FloatingRequirementSource::getLoc() const { |
| if (auto source = storage.dyn_cast<const RequirementSource *>()) |
| return source->getLoc(); |
| |
| if (auto typeRepr = storage.dyn_cast<const TypeRepr *>()) |
| return typeRepr->getLoc(); |
| |
| if (auto requirementRepr = storage.dyn_cast<const RequirementRepr *>()) { |
| switch (requirementRepr->getKind()) { |
| case RequirementReprKind::LayoutConstraint: |
| case RequirementReprKind::TypeConstraint: |
| return requirementRepr->getColonLoc(); |
| |
| case RequirementReprKind::SameType: |
| return requirementRepr->getEqualLoc(); |
| } |
| } |
| |
| return SourceLoc(); |
| } |
| |
| bool FloatingRequirementSource::isExplicit() const { |
| switch (kind) { |
| case Explicit: |
| return true; |
| |
| case Inferred: |
| case NestedTypeNameMatch: |
| return false; |
| |
| case AbstractProtocol: |
| switch (storage.get<const RequirementSource *>()->kind) { |
| case RequirementSource::RequirementSignatureSelf: |
| return true; |
| |
| case RequirementSource::Concrete: |
| case RequirementSource::Explicit: |
| case RequirementSource::Inferred: |
| case RequirementSource::NestedTypeNameMatch: |
| case RequirementSource::Parent: |
| case RequirementSource::ProtocolRequirement: |
| case RequirementSource::InferredProtocolRequirement: |
| case RequirementSource::Superclass: |
| return false; |
| } |
| |
| case Resolved: |
| switch (storage.get<const RequirementSource *>()->kind) { |
| case RequirementSource::Explicit: |
| return true; |
| |
| case RequirementSource::ProtocolRequirement: |
| return storage.get<const RequirementSource *>()->parent->kind |
| == RequirementSource::RequirementSignatureSelf; |
| |
| case RequirementSource::Inferred: |
| case RequirementSource::InferredProtocolRequirement: |
| case RequirementSource::RequirementSignatureSelf: |
| case RequirementSource::Concrete: |
| case RequirementSource::NestedTypeNameMatch: |
| case RequirementSource::Parent: |
| case RequirementSource::Superclass: |
| return false; |
| } |
| } |
| } |
| |
| |
| FloatingRequirementSource FloatingRequirementSource::asInferred( |
| const TypeRepr *typeRepr) const { |
| switch (kind) { |
| case Explicit: |
| return forInferred(typeRepr); |
| |
| case Inferred: |
| case Resolved: |
| case NestedTypeNameMatch: |
| return *this; |
| |
| case AbstractProtocol: |
| return viaProtocolRequirement(storage.get<const RequirementSource *>(), |
| protocolReq.protocol, typeRepr, |
| /*inferred=*/true); |
| } |
| } |
| |
| bool FloatingRequirementSource::isRecursive( |
| Type rootType, |
| GenericSignatureBuilder &builder) const { |
| llvm::SmallSet<std::pair<CanType, ProtocolDecl *>, 4> visitedAssocReqs; |
| for (auto storedSource = storage.dyn_cast<const RequirementSource *>(); |
| storedSource; storedSource = storedSource->parent) { |
| if (!storedSource->isProtocolRequirement()) |
| continue; |
| |
| if (!visitedAssocReqs.insert( |
| {storedSource->getStoredType()->getCanonicalType(), |
| storedSource->getProtocolDecl()}).second) |
| return true; |
| } |
| |
| // For a nested type match, look for another type with that name. |
| // FIXME: Actually, look for 5 of them. This is totally bogus. |
| if (kind == NestedTypeNameMatch) { |
| unsigned grossCount = 0; |
| auto pa = storage.dyn_cast<const RequirementSource *>() |
| ->getAffectedPotentialArchetype(); |
| while (auto parent = pa->getParent()) { |
| if (pa->getNestedName() == nestedName) { |
| if (++grossCount > 4) return true; |
| } |
| |
| |
| pa = parent; |
| } |
| } |
| |
| return false; |
| } |
| |
| GenericSignatureBuilder::PotentialArchetype::~PotentialArchetype() { |
| for (const auto &nested : NestedTypes) { |
| for (auto pa : nested.second) { |
| if (pa != this) |
| delete pa; |
| } |
| } |
| |
| delete representativeOrEquivClass.dyn_cast<EquivalenceClass *>(); |
| } |
| |
| std::string GenericSignatureBuilder::PotentialArchetype::getDebugName() const { |
| llvm::SmallString<64> result; |
| |
| auto parent = getParent(); |
| if (!parent) { |
| return GenericTypeParamType::get(getGenericParamKey().Depth, |
| getGenericParamKey().Index, |
| getBuilder()->getASTContext())->getName() |
| .str(); |
| } |
| |
| // Nested types. |
| result += parent->getDebugName(); |
| |
| // When building the name for debugging purposes, include the protocol into |
| // which the associated type or type alias was resolved. |
| ProtocolDecl *proto = nullptr; |
| if (auto assocType = getResolvedAssociatedType()) { |
| proto = assocType->getProtocol(); |
| } else if (auto typeAlias = getTypeAliasDecl()) { |
| proto = typeAlias->getParent()->getAsProtocolOrProtocolExtensionContext(); |
| } |
| |
| if (proto) { |
| result.push_back('['); |
| result.push_back('.'); |
| result.append(proto->getName().str().begin(), proto->getName().str().end()); |
| result.push_back(']'); |
| } |
| |
| result.push_back('.'); |
| result.append(getNestedName().str().begin(), getNestedName().str().end()); |
| |
| return result.str().str(); |
| } |
| |
| unsigned GenericSignatureBuilder::PotentialArchetype::getNestingDepth() const { |
| unsigned Depth = 0; |
| for (auto P = getParent(); P; P = P->getParent()) |
| ++Depth; |
| return Depth; |
| } |
| |
| void GenericSignatureBuilder::PotentialArchetype::resolveAssociatedType( |
| AssociatedTypeDecl *assocType, |
| GenericSignatureBuilder &builder) { |
| assert(isUnresolvedNestedType && "associated type is already resolved"); |
| isUnresolvedNestedType = false; |
| identifier.assocTypeOrAlias = assocType; |
| assert(assocType->getName() == getNestedName()); |
| assert(builder.Impl->NumUnresolvedNestedTypes > 0 && |
| "Mismatch in number of unresolved nested types"); |
| --builder.Impl->NumUnresolvedNestedTypes; |
| } |
| |
| void GenericSignatureBuilder::PotentialArchetype::resolveTypeAlias( |
| TypeAliasDecl *typealias, |
| GenericSignatureBuilder &builder) { |
| assert(isUnresolvedNestedType && "nested type is already resolved"); |
| isUnresolvedNestedType = false; |
| identifier.assocTypeOrAlias = typealias; |
| assert(typealias->getName() == getNestedName()); |
| assert(builder.Impl->NumUnresolvedNestedTypes > 0 && |
| "Mismatch in number of unresolved nested types"); |
| --builder.Impl->NumUnresolvedNestedTypes; |
| } |
| |
| Optional<ConcreteConstraint> |
| EquivalenceClass::findAnyConcreteConstraintAsWritten( |
| PotentialArchetype *preferredPA) const { |
| // If we don't have a concrete type, there's no source. |
| if (!concreteType) return None; |
| |
| // Go look for a source with source-location information. |
| Optional<ConcreteConstraint> result; |
| for (const auto &constraint : concreteTypeConstraints) { |
| if (constraint.source->getLoc().isValid()) { |
| result = constraint; |
| if (!preferredPA || constraint.archetype == preferredPA) |
| return result; |
| } |
| } |
| |
| return result; |
| } |
| |
| Optional<ConcreteConstraint> |
| EquivalenceClass::findAnySuperclassConstraintAsWritten( |
| PotentialArchetype *preferredPA) const { |
| // If we don't have a superclass, there's no source. |
| if (!superclass) return None; |
| |
| // Go look for a source with source-location information. |
| Optional<ConcreteConstraint> result; |
| for (const auto &constraint : superclassConstraints) { |
| if (constraint.source->getLoc().isValid() && |
| constraint.value->isEqual(superclass)) { |
| result = constraint; |
| |
| if (!preferredPA || constraint.archetype == preferredPA) |
| return result; |
| } |
| } |
| |
| return result; |
| } |
| |
| bool EquivalenceClass::isConformanceSatisfiedBySuperclass( |
| ProtocolDecl *proto) const { |
| auto known = conformsTo.find(proto); |
| assert(known != conformsTo.end() && "doesn't conform to this protocol"); |
| for (const auto &constraint: known->second) { |
| if (constraint.source->kind == RequirementSource::Superclass) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| void EquivalenceClass::dump(llvm::raw_ostream &out) const { |
| out << "Equivalence class represented by " |
| << members.front()->getRepresentative()->getDebugName() << ":\n"; |
| out << "Members: "; |
| interleave(members, [&](PotentialArchetype *pa) { |
| out << pa->getDebugName(); |
| }, [&]() { |
| out << ", "; |
| }); |
| out << "\nConformances:"; |
| interleave(conformsTo, |
| [&](const std::pair< |
| ProtocolDecl *, |
| std::vector<Constraint<ProtocolDecl *>>> &entry) { |
| out << entry.first->getNameStr(); |
| }, |
| [&] { out << ", "; }); |
| out << "\nSame-type constraints:"; |
| for (const auto &entry : sameTypeConstraints) { |
| out << "\n " << entry.first->getDebugName() << " == "; |
| interleave(entry.second, |
| [&](const Constraint<PotentialArchetype *> &constraint) { |
| out << constraint.value->getDebugName(); |
| |
| if (constraint.source->isDerivedRequirement()) |
| out << " [derived]"; |
| }, [&] { |
| out << ", "; |
| }); |
| } |
| if (concreteType) |
| out << "\nConcrete type: " << concreteType.getString(); |
| if (superclass) |
| out << "\nSuperclass: " << superclass.getString(); |
| if (layout) |
| out << "\nLayout: " << layout.getString(); |
| |
| out << "\n"; |
| } |
| |
| void EquivalenceClass::dump() const { |
| dump(llvm::errs()); |
| } |
| |
| ConstraintResult GenericSignatureBuilder::handleUnresolvedRequirement( |
| RequirementKind kind, |
| UnresolvedType lhs, |
| RequirementRHS rhs, |
| FloatingRequirementSource source, |
| UnresolvedHandlingKind unresolvedHandling) { |
| switch (unresolvedHandling) { |
| case UnresolvedHandlingKind::GenerateConstraints: |
| Impl->DelayedRequirements.push_back({kind, lhs, rhs, source}); |
| return ConstraintResult::Resolved; |
| |
| case UnresolvedHandlingKind::ReturnUnresolved: |
| return ConstraintResult::Unresolved; |
| } |
| } |
| |
| const RequirementSource *GenericSignatureBuilder::resolveSuperConformance( |
| GenericSignatureBuilder::PotentialArchetype *pa, |
| ProtocolDecl *proto) { |
| // Get the superclass constraint. |
| Type superclass = pa->getSuperclass(); |
| if (!superclass) return nullptr; |
| |
| // Lookup the conformance of the superclass to this protocol. |
| auto conformance = |
| getLookupConformanceFn()(pa->getDependentType({ }, /*allowUnresolved=*/true) |
| ->getCanonicalType(), |
| superclass, |
| proto->getDeclaredInterfaceType() |
| ->castTo<ProtocolType>()); |
| if (!conformance) return nullptr; |
| |
| // Conformance to this protocol is redundant; update the requirement source |
| // appropriately. |
| auto paEquivClass = pa->getOrCreateEquivalenceClass(); |
| const RequirementSource *superclassSource; |
| if (auto writtenSource = |
| paEquivClass->findAnySuperclassConstraintAsWritten(pa)) |
| superclassSource = writtenSource->source; |
| else |
| superclassSource = paEquivClass->superclassConstraints.front().source; |
| |
| superclassSource = |
| superclassSource->viaSuperclass(*this, conformance->getConcrete()); |
| paEquivClass->conformsTo[proto].push_back({pa, proto, superclassSource}); |
| return superclassSource; |
| } |
| |
| struct GenericSignatureBuilder::ResolvedType { |
| llvm::PointerUnion<PotentialArchetype *, Type> paOrT; |
| |
| explicit ResolvedType(PotentialArchetype *pa) : paOrT(pa) {} |
| explicit ResolvedType(Type ty) : paOrT(ty) {} |
| |
| public: |
| static ResolvedType forConcreteType(Type t) { |
| assert(!t->isTypeParameter() && |
| "concrete type with parameter should've been resolved"); |
| return ResolvedType(t); |
| } |
| |
| static ResolvedType forPotentialArchetype(PotentialArchetype *pa) { |
| return ResolvedType(pa); |
| } |
| |
| Type getType() const { return paOrT.dyn_cast<Type>(); } |
| PotentialArchetype *getPotentialArchetype() const { |
| return paOrT.dyn_cast<PotentialArchetype *>(); |
| } |
| |
| bool isType() const { return paOrT.is<Type>(); } |
| }; |
| |
| /// If there is a same-type requirement to be added for the given nested type |
| /// due to a superclass constraint on the parent type, add it now. |
| static void maybeAddSameTypeRequirementForNestedType( |
| GenericSignatureBuilder::PotentialArchetype *nestedPA, |
| const RequirementSource *superSource, |
| GenericSignatureBuilder &builder) { |
| // If there's no super conformance, we're done. |
| if (!superSource) return; |
| |
| auto assocType = nestedPA->getResolvedAssociatedType(); |
| assert(assocType && "Not resolved to an associated type?"); |
| |
| // Dig out the type witness. |
| auto superConformance = superSource->getProtocolConformance(); |
| auto concreteType = |
| superConformance->getTypeWitness(assocType, builder.getLazyResolver()); |
| if (!concreteType) return; |
| |
| // Add the same-type constraint. |
| auto nestedSource = superSource->viaParent(builder, assocType); |
| concreteType = superConformance->getDeclContext() |
| ->mapTypeOutOfContext(concreteType); |
| |
| builder.addSameTypeRequirement(nestedPA, concreteType, nestedSource, |
| GenericSignatureBuilder::UnresolvedHandlingKind::GenerateConstraints); |
| } |
| |
| /// Walk the members of a protocol. |
| /// |
| /// This is essentially just a call to \c proto->getMembers(), except that |
| /// for Objective-C-imported protocols we can simply return an empty declaration |
| /// range because the generic signature builder only cares about nested types (which |
| /// Objective-C protocols don't have). |
| static DeclRange getProtocolMembers(ProtocolDecl *proto) { |
| if (proto->hasClangNode()) |
| return DeclRange(DeclIterator(), DeclIterator()); |
| |
| return proto->getMembers(); |
| } |
| |
| bool PotentialArchetype::addConformance(ProtocolDecl *proto, |
| const RequirementSource *source, |
| GenericSignatureBuilder &builder) { |
| // Check whether we already knew about this conformance. |
| auto equivClass = getOrCreateEquivalenceClass(); |
| auto known = equivClass->conformsTo.find(proto); |
| if (known != equivClass->conformsTo.end()) { |
| // We already knew about this conformance; record this specific constraint. |
| known->second.push_back({this, proto, source}); |
| return false; |
| } |
| |
| // Add the conformance along with this constraint. |
| equivClass->conformsTo[proto].push_back({this, proto, source}); |
| |
| // Determine whether there is a superclass constraint where the |
| // superclass conforms to this protocol. |
| (void)getBuilder()->resolveSuperConformance(this, proto); |
| |
| // Resolve any existing nested types that need it. |
| for (auto &nested : NestedTypes) { |
| (void)updateNestedTypeForConformance(nested.first, proto, |
| NestedTypeUpdate::ResolveExisting); |
| } |
| |
| return true; |
| } |
| |
| auto PotentialArchetype::getOrCreateEquivalenceClass() const -> EquivalenceClass * { |
| // The equivalence class is stored on the representative. |
| auto representative = getRepresentative(); |
| if (representative != this) |
| return representative->getOrCreateEquivalenceClass(); |
| |
| // If we already have an equivalence class, return it. |
| if (auto equivClass = getEquivalenceClassIfPresent()) |
| return equivClass; |
| |
| // Create a new equivalence class. |
| auto equivClass = |
| new EquivalenceClass(const_cast<PotentialArchetype *>(this)); |
| representativeOrEquivClass = equivClass; |
| return equivClass; |
| } |
| |
| auto PotentialArchetype::getRepresentative() const -> PotentialArchetype * { |
| auto representative = |
| representativeOrEquivClass.dyn_cast<PotentialArchetype *>(); |
| if (!representative) |
| return const_cast<PotentialArchetype *>(this); |
| |
| // Find the representative. |
| PotentialArchetype *result = representative; |
| while (auto nextRepresentative = |
| result->representativeOrEquivClass.dyn_cast<PotentialArchetype *>()) |
| result = nextRepresentative; |
| |
| // Perform (full) path compression. |
| const PotentialArchetype *fixUp = this; |
| while (auto nextRepresentative = |
| fixUp->representativeOrEquivClass.dyn_cast<PotentialArchetype *>()) { |
| fixUp->representativeOrEquivClass = nextRepresentative; |
| fixUp = nextRepresentative; |
| } |
| |
| return result; |
| } |
| |
| /// Compare two associated types. |
| static int compareAssociatedTypes(AssociatedTypeDecl *assocType1, |
| AssociatedTypeDecl *assocType2) { |
| // - by name. |
| if (int result = assocType1->getName().str().compare( |
| assocType2->getName().str())) |
| return result; |
| |
| // - by protocol, so t_n_m.`P.T` < t_n_m.`Q.T` (given P < Q) |
| auto proto1 = assocType1->getProtocol(); |
| auto proto2 = assocType2->getProtocol(); |
| if (int compareProtocols = ProtocolType::compareProtocols(&proto1, &proto2)) |
| return compareProtocols; |
| |
| // Error case: if we have two associated types with the same name in the |
| // same protocol, just tie-break based on address. |
| if (assocType1 != assocType2) |
| return assocType1 < assocType2 ? -1 : +1; |
| |
| return 0; |
| } |
| |
| /// Compare two typealiases in protocols. |
| static int compareTypeAliases(TypeAliasDecl *typealias1, |
| TypeAliasDecl *typealias2) { |
| // - by name. |
| if (int result = typealias1->getName().str().compare( |
| typealias2->getName().str())) |
| return result; |
| |
| // - by protocol, so t_n_m.`P.T` < t_n_m.`Q.T` (given P < Q) |
| auto proto1 = |
| typealias1->getDeclContext()->getAsProtocolOrProtocolExtensionContext(); |
| auto proto2 = |
| typealias2->getDeclContext()->getAsProtocolOrProtocolExtensionContext(); |
| if (int compareProtocols = ProtocolType::compareProtocols(&proto1, &proto2)) |
| return compareProtocols; |
| |
| // Error case: if we have two associated types with the same name in the |
| // same protocol, just tie-break based on address. |
| if (typealias1 != typealias2) |
| return typealias1 < typealias2 ? -1 : +1; |
| |
| return 0; |
| } |
| |
| /// Canonical ordering for dependent types in generic signatures. |
| static int compareDependentTypes(PotentialArchetype * const* pa, |
| PotentialArchetype * const* pb) { |
| auto a = *pa, b = *pb; |
| |
| // Fast-path check for equality. |
| if (a == b) |
| return 0; |
| |
| // Typealiases must be ordered *after* everything else, to ensure they |
| // don't become representatives in the case where a typealias is equated |
| // with an associated type. |
| if (a->getParent() && b->getParent() && |
| !!a->getTypeAliasDecl() != !!b->getTypeAliasDecl()) |
| return a->getTypeAliasDecl() ? +1 : -1; |
| |
| // Types that are equivalent to concrete types follow types that are still |
| // type parameters. |
| if (a->isConcreteType() != b->isConcreteType()) |
| return a->isConcreteType() ? +1 : -1; |
| |
| // Ordering is as follows: |
| // - Generic params |
| if (a->isGenericParam() && b->isGenericParam()) |
| return a->getGenericParamKey() < b->getGenericParamKey() ? -1 : +1; |
| |
| // A generic parameter is always ordered before a nested type. |
| if (a->isGenericParam() != b->isGenericParam()) |
| return a->isGenericParam() ? -1 : +1; |
| |
| // - Dependent members |
| auto ppa = a->getParent(); |
| auto ppb = b->getParent(); |
| |
| // - by base, so t_0_n.`P.T` < t_1_m.`P.T` |
| if (int compareBases = compareDependentTypes(&ppa, &ppb)) |
| return compareBases; |
| |
| // - by name, so t_n_m.`P.T` < t_n_m.`P.U` |
| if (int compareNames = a->getNestedName().str().compare( |
| b->getNestedName().str())) |
| return compareNames; |
| |
| if (auto *aa = a->getResolvedAssociatedType()) { |
| if (auto *ab = b->getResolvedAssociatedType()) { |
| if (int result = compareAssociatedTypes(aa, ab)) |
| return result; |
| } else { |
| // A resolved archetype is always ordered before an unresolved one. |
| return -1; |
| } |
| } else { |
| // A resolved archetype is always ordered before an unresolved one. |
| if (b->getResolvedAssociatedType()) |
| return +1; |
| } |
| |
| // Make sure typealiases are properly ordered, to avoid crashers. |
| if (auto *aa = a->getTypeAliasDecl()) { |
| auto *ab = b->getTypeAliasDecl(); |
| assert(ab != nullptr && "Should have handled this case above"); |
| |
| if (int result = compareTypeAliases(aa, ab)) |
| return result; |
| } |
| |
| // Along the error path where one or both of the potential archetypes was |
| // renamed due to typo correction, |
| if (a->wasRenamed() || b->wasRenamed()) { |
| if (a->wasRenamed() != b->wasRenamed()) |
| return a->wasRenamed() ? +1 : -1; |
| |
| if (int compareNames = a->getOriginalName().str().compare( |
| b->getOriginalName().str())) |
| return compareNames; |
| } |
| |
| llvm_unreachable("potential archetype total order failure"); |
| } |
| |
| PotentialArchetype *PotentialArchetype::getArchetypeAnchor( |
| GenericSignatureBuilder &builder) { |
| // Find the best archetype within this equivalence class. |
| PotentialArchetype *rep = getRepresentative(); |
| PotentialArchetype *anchor; |
| if (auto parent = getParent()) { |
| // For a nested type, retrieve the parent archetype anchor first. |
| auto parentAnchor = parent->getArchetypeAnchor(builder); |
| anchor = parentAnchor->getNestedArchetypeAnchor( |
| getNestedName(), builder, |
| NestedTypeUpdate::ResolveExisting); |
| |
| // FIXME: Hack for cases where we couldn't resolve the nested type. |
| if (!anchor) |
| anchor = rep; |
| } else { |
| anchor = rep; |
| } |
| |
| // Find the best type within this equivalence class. |
| for (auto pa : rep->getEquivalenceClassMembers()) { |
| if (compareDependentTypes(&pa, &anchor) < 0) |
| anchor = pa; |
| } |
| |
| #ifndef NDEBUG |
| // Make sure that we did, in fact, get one that is better than all others. |
| for (auto pa : anchor->getEquivalenceClassMembers()) { |
| assert((pa == anchor || compareDependentTypes(&anchor, &pa) < 0) && |
| compareDependentTypes(&pa, &anchor) >= 0 && |
| "archetype anchor isn't a total order"); |
| } |
| #endif |
| |
| return anchor; |
| } |
| |
| namespace { |
| /// Function object to diagnose a conflict in same-type constraints for a |
| /// given potential archetype. |
| struct DiagnoseSameTypeConflict { |
| DiagnosticEngine &diags; |
| const RequirementSource *source; |
| PotentialArchetype *pa; |
| |
| void operator()(Type type1, Type type2) const { |
| if (pa->getParent() && pa->getTypeAliasDecl() && |
| source->getLoc().isInvalid()) { |
| diags.diagnose(pa->getTypeAliasDecl()->getLoc(), |
| diag::protocol_typealias_conflict, |
| pa->getTypeAliasDecl()->getName(), |
| type1, type2); |
| return; |
| } |
| |
| if (source->getLoc().isValid()) { |
| diags.diagnose(source->getLoc(), |
| diag::requires_same_type_conflict, |
| pa->isGenericParam(), |
| pa->getDependentType(/*FIXME: */{ }, true), |
| type1, type2); |
| } |
| } |
| }; |
| } // end anonymous namespace |
| |
| // Give a nested type the appropriately resolved concrete type, based off a |
| // parent PA that has a concrete type. |
| static void concretizeNestedTypeFromConcreteParent( |
| GenericSignatureBuilder::PotentialArchetype *parent, |
| const RequirementSource *parentConcreteSource, |
| GenericSignatureBuilder::PotentialArchetype *nestedPA, |
| GenericSignatureBuilder &builder, |
| llvm::function_ref<ProtocolConformanceRef(ProtocolDecl *)> |
| lookupConformance) { |
| auto concreteParent = parent->getConcreteType(); |
| assert(concreteParent && |
| "attempting to resolve concrete nested type of non-concrete PA"); |
| |
| // These requirements are all implied based on the parent's concrete |
| // conformance. |
| auto assocType = nestedPA->getResolvedAssociatedType(); |
| if (!assocType) return; |
| |
| auto source = parentConcreteSource->viaConcrete(builder, /*FIXME: */nullptr) |
| ->viaParent(builder, assocType); |
| |
| // FIXME: Get the conformance from the parent. |
| auto conformance = lookupConformance(assocType->getProtocol()); |
| |
| Type witnessType; |
| if (conformance.isConcrete()) { |
| witnessType = |
| conformance.getConcrete() |
| ->getTypeWitness(assocType, builder.getLazyResolver()); |
| } else { |
| witnessType = DependentMemberType::get(concreteParent, assocType); |
| } |
| |
| builder.addSameTypeRequirement( |
| nestedPA, witnessType, source, |
| GenericSignatureBuilder::UnresolvedHandlingKind::GenerateConstraints, |
| DiagnoseSameTypeConflict{ |
| builder.getASTContext().Diags, |
| source, nestedPA |
| }); |
| } |
| |
| PotentialArchetype *PotentialArchetype::getNestedType( |
| Identifier nestedName, |
| GenericSignatureBuilder &builder) { |
| // If we already have a nested type with this name, return it. |
| auto known = NestedTypes.find(nestedName); |
| if (known != NestedTypes.end()) |
| return known->second.front(); |
| |
| // Retrieve the nested archetype anchor, which is the best choice (so far) |
| // for this nested type. |
| return getNestedArchetypeAnchor(nestedName, builder); |
| } |
| |
| PotentialArchetype *PotentialArchetype::getNestedType( |
| AssociatedTypeDecl *assocType, |
| GenericSignatureBuilder &builder) { |
| return updateNestedTypeForConformance(assocType, |
| NestedTypeUpdate::AddIfMissing); |
| } |
| |
| PotentialArchetype *PotentialArchetype::getNestedType( |
| TypeAliasDecl *typealias, |
| GenericSignatureBuilder &builder) { |
| return updateNestedTypeForConformance(typealias, |
| NestedTypeUpdate::AddIfMissing); |
| } |
| |
| PotentialArchetype *PotentialArchetype::getNestedArchetypeAnchor( |
| Identifier name, |
| GenericSignatureBuilder &builder, |
| NestedTypeUpdate kind) { |
| // Look for the best associated type or typealias within the protocols |
| // we know about. |
| AssociatedTypeDecl *bestAssocType = nullptr; |
| TypeAliasDecl *bestTypeAlias = nullptr; |
| SmallVector<TypeAliasDecl *, 4> typealiases; |
| auto rep = getRepresentative(); |
| for (auto proto : rep->getConformsTo()) { |
| // Look for an associated type and/or typealias with this name. |
| AssociatedTypeDecl *assocType = nullptr; |
| TypeAliasDecl *typealias = nullptr; |
| for (auto member : proto->lookupDirect(name, |
| /*ignoreNewExtensions=*/true)) { |
| if (!assocType) |
| assocType = dyn_cast<AssociatedTypeDecl>(member); |
| |
| // FIXME: Filter out typealiases that aren't in the protocol itself? |
| if (!typealias) |
| typealias = dyn_cast<TypeAliasDecl>(member); |
| } |
| |
| if (assocType && |
| (!bestAssocType || |
| compareAssociatedTypes(assocType, bestAssocType) < 0)) |
| bestAssocType = assocType; |
| |
| if (typealias) { |
| // Record every typealias. |
| typealiases.push_back(typealias); |
| |
| // Track the best typealias. |
| if (!bestTypeAlias || compareTypeAliases(typealias, bestTypeAlias) < 0) |
| bestTypeAlias = typealias; |
| } |
| } |
| |
| // If we found an associated type, use it. |
| PotentialArchetype *resultPA = nullptr; |
| if (bestAssocType) { |
| resultPA = updateNestedTypeForConformance(bestAssocType, |
| NestedTypeUpdate::AddIfMissing); |
| } |
| |
| // If we have an associated type, drop any typealiases that aren't in |
| // the same module as the protocol. |
| // FIXME: This is an unprincipled hack for an unprincipled feature. |
| typealiases.erase( |
| std::remove_if(typealiases.begin(), typealiases.end(), |
| [&](TypeAliasDecl *typealias) { |
| return typealias->getParentModule() != |
| typealias->getDeclContext() |
| ->getAsNominalTypeOrNominalTypeExtensionContext()->getParentModule(); |
| }), |
| typealiases.end()); |
| |
| // Update for all of the typealiases with this name, which will introduce |
| // various same-type constraints. |
| for (auto typealias : typealiases) { |
| auto typealiasPA = updateNestedTypeForConformance(typealias, |
| NestedTypeUpdate::AddIfMissing); |
| if (!resultPA && typealias == bestTypeAlias) |
| resultPA = typealiasPA; |
| } |
| |
| if (resultPA) |
| return resultPA; |
| |
| // Check whether we can add a missing nested type for this case. |
| switch (kind) { |
| case NestedTypeUpdate::AddIfBetterAnchor: |
| case NestedTypeUpdate::AddIfMissing: |
| break; |
| |
| case NestedTypeUpdate::ResolveExisting: |
| // Don't add a new type; |
| return nullptr; |
| } |
| |
| // Build an unresolved type if we don't have one yet. |
| auto &nested = NestedTypes[name]; |
| if (nested.empty()) { |
| nested.push_back(new PotentialArchetype(this, name)); |
| ++builder.Impl->NumUnresolvedNestedTypes; |
| |
| auto rep = getRepresentative(); |
| if (rep != this) { |
| auto existingPA = rep->getNestedType(name, builder); |
| |
| auto sameNamedSource = |
| RequirementSource::forNestedTypeNameMatch(existingPA); |
| builder.addSameTypeRequirement( |
| existingPA, nested.back(), sameNamedSource, |
| UnresolvedHandlingKind::GenerateConstraints); |
| } |
| } |
| |
| return nested.front(); |
| } |
| |
| |
| PotentialArchetype *PotentialArchetype::updateNestedTypeForConformance( |
| Identifier name, |
| ProtocolDecl *proto, |
| NestedTypeUpdate kind) { |
| /// Determine whether there is an associated type or typealias with this name |
| /// in this protocol. If not, there's nothing to do. |
| AssociatedTypeDecl *assocType = nullptr; |
| TypeAliasDecl *typealias = nullptr; |
| for (auto member : proto->lookupDirect(name, /*ignoreNewExtensions=*/true)) { |
| if (!assocType) |
| assocType = dyn_cast<AssociatedTypeDecl>(member); |
| |
| // FIXME: Filter out typealiases that aren't in the protocol itself? |
| if (!typealias) |
| typealias = dyn_cast<TypeAliasDecl>(member); |
| } |
| |
| // There is no associated type or typealias with this name in this protocol |
| if (!assocType && !typealias) |
| return nullptr; |
| |
| // If we had both an associated type and a typealias, ignore the latter. This |
| // is for ill-formed code. |
| if (assocType) |
| return updateNestedTypeForConformance(assocType, kind); |
| |
| return updateNestedTypeForConformance(typealias, kind); |
| } |
| |
| PotentialArchetype *PotentialArchetype::updateNestedTypeForConformance( |
| PointerUnion<AssociatedTypeDecl *, TypeAliasDecl *> type, |
| NestedTypeUpdate kind) { |
| auto *assocType = type.dyn_cast<AssociatedTypeDecl *>(); |
| auto *typealias = type.dyn_cast<TypeAliasDecl *>(); |
| if (!assocType && !typealias) |
| return nullptr; |
| |
| Identifier name = assocType ? assocType->getName() : typealias->getName(); |
| ProtocolDecl *proto = |
| assocType ? assocType->getProtocol() |
| : typealias->getDeclContext() |
| ->getAsProtocolOrProtocolExtensionContext(); |
| |
| // Look for either an unresolved potential archetype (which we can resolve |
| // now) or a potential archetype with the appropriate associated type or |
| // typealias. |
| PotentialArchetype *resultPA = nullptr; |
| auto knownNestedTypes = NestedTypes.find(name); |
| bool shouldUpdatePA = false; |
| auto &builder = *getBuilder(); |
| if (knownNestedTypes != NestedTypes.end()) { |
| for (auto existingPA : knownNestedTypes->second) { |
| // Resolve an unresolved potential archetype. |
| if (existingPA->isUnresolvedNestedType) { |
| if (assocType) { |
| existingPA->resolveAssociatedType(assocType, builder); |
| } else { |
| existingPA->resolveTypeAlias(typealias, builder); |
| } |
| |
| // We've resolved this nested type; nothing more to do. |
| resultPA = existingPA; |
| shouldUpdatePA = true; |
| break; |
| } |
| |
| // Do we have an associated-type match? |
| if (assocType && existingPA->getResolvedAssociatedType() == assocType) { |
| resultPA = existingPA; |
| break; |
| } |
| |
| // Do we have a typealias match? |
| if (typealias && existingPA->getTypeAliasDecl() == typealias) { |
| resultPA = existingPA; |
| break; |
| } |
| } |
| } |
| |
| // If we don't have a result potential archetype yet, we may need to add one. |
| if (!resultPA) { |
| switch (kind) { |
| case NestedTypeUpdate::AddIfBetterAnchor: |
| // FIXME: The loop above should have kept track of whether this type |
| // would make a better anchor, so we can bail out here if the answer is |
| // "no". |
| LLVM_FALLTHROUGH; |
| |
| case NestedTypeUpdate::AddIfMissing: { |
| if (assocType) |
| resultPA = new PotentialArchetype(this, assocType); |
| else |
| resultPA = new PotentialArchetype(this, typealias); |
| |
| auto &allNested = NestedTypes[name]; |
| allNested.push_back(resultPA); |
| |
| // We created a new type, which might be equivalent to a type by the |
| // same name elsewhere. |
| PotentialArchetype *existingPA = nullptr; |
| if (allNested.size() > 1) { |
| existingPA = allNested.front(); |
| } else { |
| auto rep = getRepresentative(); |
| if (rep != this) { |
| if (assocType) |
| existingPA = rep->getNestedType(assocType, builder); |
| else |
| existingPA = rep->getNestedType(name, builder); |
| } |
| } |
| |
| if (existingPA) { |
| auto sameNamedSource = |
| RequirementSource::forNestedTypeNameMatch(existingPA); |
| builder.addSameTypeRequirement( |
| existingPA, resultPA, sameNamedSource, |
| UnresolvedHandlingKind::GenerateConstraints); |
| } |
| |
| shouldUpdatePA = true; |
| break; |
| } |
| |
| case NestedTypeUpdate::ResolveExisting: |
| break; |
| } |
| } |
| |
| // If we still don't have a result potential archetype, we're done. |
| if (!resultPA) |
| return nullptr; |
| |
| // If we have a potential archetype that requires more processing, do so now. |
| if (shouldUpdatePA) { |
| // For typealiases, introduce a same-type requirement to the aliased type. |
| if (typealias) { |
| // FIXME (recursive decl validation): if the alias doesn't have an |
| // interface type when getNestedType is called while building a |
| // protocol's generic signature (i.e. during validation), then it'll |
| // fail completely, because building that alias's interface type |
| // requires the protocol to be validated. This seems to occur when the |
| // alias's RHS involves archetypes from the protocol. |
| if (!typealias->hasInterfaceType()) |
| builder.getLazyResolver()->resolveDeclSignature(typealias); |
| if (typealias->hasInterfaceType()) { |
| // The protocol typealias has an underlying type written in terms |
| // of the protocol's 'Self' type. |
| auto type = typealias->getDeclaredInterfaceType(); |
| |
| // Substitute in the type of the current PotentialArchetype in |
| // place of 'Self' here. |
| auto subMap = SubstitutionMap::getProtocolSubstitutions( |
| proto, getDependentType(/*genericParams=*/{}, |
| /*allowUnresolved=*/true), |
| ProtocolConformanceRef(proto)); |
| type = type.subst(subMap, SubstFlags::UseErrorType); |
| |
| builder.addSameTypeRequirement( |
| UnresolvedType(resultPA), |
| UnresolvedType(type), |
| RequirementSource::forNestedTypeNameMatch(resultPA), |
| UnresolvedHandlingKind::GenerateConstraints); |
| } |
| } |
| |
| // If there's a superclass constraint that conforms to the protocol, |
| // add the appropriate same-type relationship. |
| if (auto superSource = builder.resolveSuperConformance(this, proto)) |
| maybeAddSameTypeRequirementForNestedType(resultPA, superSource, builder); |
| |
| // We know something concrete about the parent PA, so we need to propagate |
| // that information to this new archetype. |
| // FIXME: This feels like massive overkill. Why do we have to loop? |
| if (isConcreteType()) { |
| for (auto equivT : getRepresentative()->getEquivalenceClassMembers()) { |
| concretizeNestedTypeFromConcreteParent( |
| equivT, RequirementSource::forNestedTypeNameMatch(this), |
| resultPA, builder, |
| [&](ProtocolDecl *proto) -> ProtocolConformanceRef { |
| auto depTy = resultPA->getDependentType({}, |
| /*allowUnresolved=*/true) |
| ->getCanonicalType(); |
| auto protocolTy = |
| proto->getDeclaredInterfaceType()->castTo<ProtocolType>(); |
| auto conformance = builder.getLookupConformanceFn()( |
| depTy, getConcreteType(), protocolTy); |
| assert(conformance && |
| "failed to find PA's conformance to known protocol"); |
| return *conformance; |
| }); |
| } |
| } |
| } |
| |
| return resultPA; |
| } |
| |
| Type GenericSignatureBuilder::PotentialArchetype::getTypeInContext( |
| GenericSignatureBuilder &builder, |
| GenericEnvironment *genericEnv) { |
| ArrayRef<GenericTypeParamType *> genericParams = |
| genericEnv->getGenericParams(); |
| |
| // Retrieve the archetype from the archetype anchor in this equivalence class. |
| // The anchor must not have any concrete parents (otherwise we would just |
| // use the representative). |
| auto archetypeAnchor = getArchetypeAnchor(builder); |
| if (archetypeAnchor != this) |
| return archetypeAnchor->getTypeInContext(builder, genericEnv); |
| |
| auto representative = getRepresentative(); |
| auto equivClass = representative->getOrCreateEquivalenceClass(); |
| ASTContext &ctx = genericEnv->getGenericSignature()->getASTContext(); |
| |
| // Return a concrete type or archetype we've already resolved. |
| if (Type concreteType = representative->getConcreteType()) { |
| // Otherwise, substitute in the archetypes in the environment. |
| // If this has a recursive type, return an error type. |
| if (representative->RecursiveConcreteType) { |
| return ErrorType::get(getDependentType(genericParams, |
| /*allowUnresolved=*/true)); |
| } |
| |
| return genericEnv->mapTypeIntoContext(concreteType, |
| builder.getLookupConformanceFn()); |
| } |
| |
| // Local function to check whether we have a generic parameter that has |
| // already been recorded |
| auto getAlreadyRecoveredGenericParam = [&]() -> Type { |
| if (!isGenericParam()) return Type(); |
| |
| auto type = genericEnv->getMappingIfPresent(getGenericParamKey()); |
| if (!type) return Type(); |
| |
| // We already have a mapping for this generic parameter in the generic |
| // environment. Return it. |
| return *type; |
| }; |
| |
| AssociatedTypeDecl *assocType = nullptr; |
| ArchetypeType *ParentArchetype = nullptr; |
| if (auto parent = getParent()) { |
| // For nested types, first substitute into the parent so we can form the |
| // proper nested type. |
| auto parentTy = parent->getTypeInContext(builder, genericEnv); |
| if (!parentTy) |
| return ErrorType::get(getDependentType(genericParams, |
| /*allowUnresolved=*/true)); |
| |
| ParentArchetype = parentTy->getAs<ArchetypeType>(); |
| if (!ParentArchetype) { |
| LazyResolver *resolver = ctx.getLazyResolver(); |
| assert(resolver && "need a lazy resolver"); |
| (void) resolver; |
| |
| // Resolve the member type. |
| auto type = getDependentType(genericParams, /*allowUnresolved=*/false); |
| if (type->hasError()) |
| return type; |
| |
| auto depMemberType = type->castTo<DependentMemberType>(); |
| Type memberType = |
| depMemberType->substBaseType(parentTy, |
| builder.getLookupConformanceFn()); |
| |
| // If the member type maps to an archetype, resolve that archetype. |
| if (auto memberPA = |
| builder.resolveArchetype( |
| memberType, |
| ArchetypeResolutionKind::CompleteWellFormed)) { |
| if (memberPA->getRepresentative() != representative) { |
| return memberPA->getTypeInContext(builder, genericEnv); |
| } |
| |
| llvm_unreachable("we have no parent archetype"); |
| } |
| |
| |
| // Otherwise, it's a concrete type. |
| return genericEnv->mapTypeIntoContext(memberType, |
| builder.getLookupConformanceFn()); |
| } |
| |
| // Check whether the parent already has a nested type with this name. If |
| // so, return it directly. |
| if (auto nested = ParentArchetype->getNestedTypeIfKnown(getNestedName())) |
| return *nested; |
| |
| // We will build the archetype below. |
| assocType = getResolvedAssociatedType(); |
| } else if (auto result = getAlreadyRecoveredGenericParam()) { |
| return result; |
| } |
| |
| // Determine the superclass for the archetype. If it exists and involves |
| // type parameters, substitute them. |
| Type superclass = representative->getSuperclass(); |
| if (superclass && superclass->hasTypeParameter()) { |
| if (representative->RecursiveSuperclassType) { |
| superclass = Type(); |
| } else { |
| superclass = genericEnv->mapTypeIntoContext( |
| superclass, |
| builder.getLookupConformanceFn()); |
| if (superclass->is<ErrorType>()) |
| superclass = Type(); |
| |
| // We might have recursively recorded the archetype; if so, return early. |
| // FIXME: This should be detectable before we end up building archetypes. |
| if (auto result = getAlreadyRecoveredGenericParam()) |
| return result; |
| } |
| } |
| |
| LayoutConstraint layout = representative->getLayout(); |
| |
| // Build a new archetype. |
| |
| // Collect the protocol conformances for the archetype. |
| SmallVector<ProtocolDecl *, 4> Protos; |
| for (auto proto : representative->getConformsTo()) { |
| if (!equivClass || !equivClass->isConformanceSatisfiedBySuperclass(proto)) |
| Protos.push_back(proto); |
| } |
| |
| // Create the archetype. |
| // |
| // Note that we delay the computation of the superclass until after we |
| // create the archetype, in case the superclass references the archetype |
| // itself. |
| ArchetypeType *arch; |
| if (ParentArchetype) { |
| // If we were unable to resolve this as an associated type, produce an |
| // error type. |
| if (!assocType) { |
| return ErrorType::get(getDependentType(genericParams, |
| /*allowUnresolved=*/true)); |
| } |
| |
| // Create a nested archetype. |
| arch = ArchetypeType::getNew(ctx, ParentArchetype, assocType, Protos, |
| superclass, layout); |
| |
| // Register this archetype with its parent. |
| ParentArchetype->registerNestedType(getNestedName(), arch); |
| } else { |
| // Create a top-level archetype. |
| Identifier name = |
| genericParams[getGenericParamKey().findIndexIn(genericParams)]->getName(); |
| arch = ArchetypeType::getNew(ctx, genericEnv, name, Protos, |
| superclass, layout); |
| |
| // Register the archetype with the generic environment. |
| genericEnv->addMapping(getGenericParamKey(), arch); |
| } |
| |
| return arch; |
| } |
| |
| void ArchetypeType::resolveNestedType( |
| std::pair<Identifier, Type> &nested) const { |
| auto genericEnv = getGenericEnvironment(); |
| auto &builder = *genericEnv->getGenericSignatureBuilder(); |
| |
| Type interfaceType = |
| genericEnv->mapTypeOutOfContext(const_cast<ArchetypeType *>(this)); |
| auto parentPA = |
| builder.resolveArchetype(interfaceType, |
| ArchetypeResolutionKind::CompleteWellFormed); |
| auto memberPA = parentPA->getNestedType(nested.first, builder); |
| auto result = memberPA->getTypeInContext(builder, genericEnv); |
| assert(!nested.second || |
| nested.second->isEqual(result) || |
| (nested.second->hasError() && result->hasError())); |
| nested.second = result; |
| } |
| |
| Type GenericSignatureBuilder::PotentialArchetype::getDependentType( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| bool allowUnresolved) { |
| if (auto parent = getParent()) { |
| Type parentType = parent->getDependentType(genericParams, |
| allowUnresolved); |
| if (parentType->hasError()) |
| return parentType; |
| |
| // If we've resolved to an associated type, use it. |
| if (auto assocType = getResolvedAssociatedType()) |
| return DependentMemberType::get(parentType, assocType); |
| |
| // If we don't allow unresolved dependent member types, fail. |
| if (!allowUnresolved) |
| return ErrorType::get(getDependentType(genericParams, |
| /*allowUnresolved=*/true)); |
| |
| return DependentMemberType::get(parentType, getNestedName()); |
| } |
| |
| assert(isGenericParam() && "Not a generic parameter?"); |
| |
| // FIXME: This is a temporary workaround. |
| if (genericParams.empty()) |
| genericParams = getBuilder()->Impl->GenericParams; |
| |
| unsigned index = getGenericParamKey().findIndexIn(genericParams); |
| return genericParams[index]; |
| } |
| |
| void GenericSignatureBuilder::PotentialArchetype::dump() const { |
| dump(llvm::errs(), nullptr, 0); |
| } |
| |
| void GenericSignatureBuilder::PotentialArchetype::dump(llvm::raw_ostream &Out, |
| SourceManager *SrcMgr, |
| unsigned Indent) const { |
| // Print name. |
| if (Indent == 0 || isGenericParam()) |
| Out << getDebugName(); |
| else |
| Out.indent(Indent) << getNestedName(); |
| |
| auto equivClass = getEquivalenceClassIfPresent(); |
| |
| // Print superclass. |
| if (equivClass && equivClass->superclass) { |
| for (const auto &constraint : equivClass->superclassConstraints) { |
| if (constraint.archetype != this) continue; |
| |
| Out << " : "; |
| constraint.value.print(Out); |
| |
| Out << " "; |
| if (!constraint.source->isDerivedRequirement()) |
| Out << "*"; |
| Out << "["; |
| constraint.source->print(Out, SrcMgr); |
| Out << "]"; |
| } |
| } |
| |
| // Print concrete type. |
| if (equivClass && equivClass->concreteType) { |
| for (const auto &constraint : equivClass->concreteTypeConstraints) { |
| if (constraint.archetype != this) continue; |
| |
| Out << " == "; |
| constraint.value.print(Out); |
| |
| Out << " "; |
| if (!constraint.source->isDerivedRequirement()) |
| Out << "*"; |
| Out << "["; |
| constraint.source->print(Out, SrcMgr); |
| Out << "]"; |
| } |
| } |
| |
| // Print requirements. |
| if (equivClass) { |
| bool First = true; |
| for (const auto &entry : equivClass->conformsTo) { |
| for (const auto &constraint : entry.second) { |
| if (constraint.archetype != this) continue; |
| |
| if (First) { |
| First = false; |
| Out << ": "; |
| } else { |
| Out << " & "; |
| } |
| |
| Out << constraint.value->getName().str() << " "; |
| if (!constraint.source->isDerivedRequirement()) |
| Out << "*"; |
| Out << "["; |
| constraint.source->print(Out, SrcMgr); |
| Out << "]"; |
| } |
| } |
| } |
| |
| if (getRepresentative() != this) { |
| Out << " [represented by " << getRepresentative()->getDebugName() << "]"; |
| } |
| |
| if (getEquivalenceClassMembers().size() > 1) { |
| Out << " [equivalence class "; |
| bool isFirst = true; |
| for (auto equiv : getEquivalenceClassMembers()) { |
| if (equiv == this) continue; |
| |
| if (isFirst) isFirst = false; |
| else Out << ", "; |
| |
| Out << equiv->getDebugName(); |
| } |
| Out << "]"; |
| } |
| |
| Out << "\n"; |
| |
| // Print nested types. |
| for (const auto &nestedVec : NestedTypes) { |
| for (auto nested : nestedVec.second) { |
| nested->dump(Out, SrcMgr, Indent + 2); |
| } |
| } |
| } |
| |
| #pragma mark Equivalence classes |
| EquivalenceClass::EquivalenceClass(PotentialArchetype *representative) { |
| members.push_back(representative); |
| } |
| |
| GenericSignatureBuilder::GenericSignatureBuilder( |
| ASTContext &ctx, |
| std::function<GenericFunction> lookupConformance) |
| : Context(ctx), Diags(Context.Diags), Impl(new Implementation) { |
| Impl->LookupConformance = std::move(lookupConformance); |
| if (Context.Stats) |
| Context.Stats->getFrontendCounters().NumGenericSignatureBuilders++; |
| } |
| |
| GenericSignatureBuilder::GenericSignatureBuilder(GenericSignatureBuilder &&) = default; |
| |
| GenericSignatureBuilder::~GenericSignatureBuilder() { |
| if (!Impl) |
| return; |
| |
| SmallVector<RequirementSource *, 4> requirementSources; |
| for (auto &reqSource : Impl->RequirementSources) |
| requirementSources.push_back(&reqSource); |
| Impl->RequirementSources.clear(); |
| for (auto reqSource : requirementSources) |
| delete reqSource; |
| |
| for (auto PA : Impl->PotentialArchetypes) |
| delete PA; |
| } |
| |
| std::function<GenericFunction> |
| GenericSignatureBuilder::getLookupConformanceFn() const { |
| return Impl->LookupConformance; |
| } |
| |
| LazyResolver *GenericSignatureBuilder::getLazyResolver() const { |
| return Context.getLazyResolver(); |
| } |
| |
| PotentialArchetype *GenericSignatureBuilder::resolveArchetype( |
| Type type, |
| ArchetypeResolutionKind resolutionKind) { |
| if (auto genericParam = type->getAs<GenericTypeParamType>()) { |
| unsigned index = GenericParamKey(genericParam).findIndexIn( |
| Impl->GenericParams); |
| if (index < Impl->GenericParams.size()) |
| return Impl->PotentialArchetypes[index]; |
| |
| return nullptr; |
| } |
| |
| if (auto dependentMember = type->getAs<DependentMemberType>()) { |
| auto base = resolveArchetype(dependentMember->getBase(), resolutionKind); |
| if (!base) |
| return nullptr; |
| |
| // Figure out what kind of nested type update we want. |
| typedef PotentialArchetype::NestedTypeUpdate NestedTypeUpdate; |
| NestedTypeUpdate updateKind; |
| switch (resolutionKind) { |
| case ArchetypeResolutionKind::AlreadyKnown: |
| updateKind = NestedTypeUpdate::ResolveExisting; |
| break; |
| |
| case ArchetypeResolutionKind::AlwaysPartial: |
| case ArchetypeResolutionKind::CompleteWellFormed: |
| updateKind = NestedTypeUpdate::AddIfMissing; |
| break; |
| } |
| |
| // If we know the associated type already, get that specific type. |
| if (auto assocType = dependentMember->getAssocType()) |
| return base->updateNestedTypeForConformance(assocType, updateKind); |
| |
| // Resolve based on name alone. |
| auto name = dependentMember->getName(); |
| switch (resolutionKind) { |
| case ArchetypeResolutionKind::AlreadyKnown: { |
| auto known = base->NestedTypes.find(name); |
| if (known == base->NestedTypes.end()) |
| return nullptr; |
| |
| return known->second.front(); |
| } |
| |
| case ArchetypeResolutionKind::AlwaysPartial: |
| case ArchetypeResolutionKind::CompleteWellFormed: |
| return base->getNestedArchetypeAnchor(name, *this, updateKind); |
| } |
| } |
| |
| return nullptr; |
| } |
| |
| auto GenericSignatureBuilder::resolve(UnresolvedType paOrT, |
| FloatingRequirementSource source) |
| -> Optional<ResolvedType> { |
| auto pa = paOrT.dyn_cast<PotentialArchetype *>(); |
| if (auto type = paOrT.dyn_cast<Type>()) { |
| // If it's not a type parameter, |
| if (!type->isTypeParameter()) |
| return ResolvedType::forConcreteType(type); |
| |
| // Determine what kind of resolution we want. |
| ArchetypeResolutionKind resolutionKind = |
| ArchetypeResolutionKind::AlwaysPartial; |
| if (!source.isExplicit() && source.isRecursive(type, *this)) |
| resolutionKind = ArchetypeResolutionKind::AlreadyKnown; |
| |
| // Attempt to resolve the type parameter to a potential archetype. If this |
| // fails, it's because we weren't allowed to resolve anything now. |
| pa = resolveArchetype(type, resolutionKind); |
| if (!pa) return None; |
| } |
| |
| auto rep = pa->getRepresentative(); |
| if (!rep->getParent() || !rep->getTypeAliasDecl()) |
| return ResolvedType::forPotentialArchetype(pa); |
| |
| // We're assuming that an equivalence class with a type alias representative |
| // doesn't have a "true" (i.e. associated type) potential archetype. |
| assert(llvm::all_of(rep->getEquivalenceClassMembers(), |
| [&](PotentialArchetype *pa) { |
| return pa->getParent() && pa->getTypeAliasDecl(); |
| }) && |
| "unexpected typealias representative with non-typealias equivalent"); |
| |
| return ResolvedType::forPotentialArchetype(pa); |
| } |
| |
| void GenericSignatureBuilder::addGenericParameter(GenericTypeParamDecl *GenericParam) { |
| addGenericParameter( |
| GenericParam->getDeclaredInterfaceType()->castTo<GenericTypeParamType>()); |
| } |
| |
| bool GenericSignatureBuilder::addGenericParameterRequirements( |
| GenericTypeParamDecl *GenericParam) { |
| GenericParamKey Key(GenericParam); |
| auto PA = Impl->PotentialArchetypes[Key.findIndexIn(Impl->GenericParams)]; |
| |
| // Add the requirements from the declaration. |
| return isErrorResult( |
| addInheritedRequirements(GenericParam, PA, nullptr, |
| GenericParam->getModuleContext())); |
| } |
| |
| void GenericSignatureBuilder::addGenericParameter(GenericTypeParamType *GenericParam) { |
| GenericParamKey Key(GenericParam); |
| assert(Impl->GenericParams.empty() || |
| ((Key.Depth == Impl->GenericParams.back()->getDepth() && |
| Key.Index == Impl->GenericParams.back()->getIndex() + 1) || |
| (Key.Depth > Impl->GenericParams.back()->getDepth() && |
| Key.Index == 0))); |
| |
| // Create a potential archetype for this type parameter. |
| auto PA = new PotentialArchetype(this, GenericParam); |
| Impl->GenericParams.push_back(GenericParam); |
| Impl->PotentialArchetypes.push_back(PA); |
| } |
| |
| /// Visit all of the types that show up in the list of inherited |
| /// types. |
| static ConstraintResult visitInherited( |
| ArrayRef<TypeLoc> inheritedTypes, |
| llvm::function_ref<ConstraintResult(Type, const TypeRepr *)> visitType) { |
| // Local function that (recursively) adds inherited types. |
| ConstraintResult result = ConstraintResult::Resolved; |
| std::function<void(Type, const TypeRepr *)> visitInherited; |
| |
| // FIXME: Should this whole thing use getExistentialLayout() instead? |
| |
| visitInherited = [&](Type inheritedType, const TypeRepr *typeRepr) { |
| // Decompose explicitly-written protocol compositions. |
| if (auto composition = dyn_cast_or_null<CompositionTypeRepr>(typeRepr)) { |
| if (auto compositionType |
| = inheritedType->getAs<ProtocolCompositionType>()) { |
| unsigned index = 0; |
| for (auto memberType : compositionType->getMembers()) { |
| visitInherited(memberType, composition->getTypes()[index]); |
| index++; |
| } |
| |
| return; |
| } |
| } |
| |
| auto recursiveResult = visitType(inheritedType, typeRepr); |
| if (isErrorResult(recursiveResult) && !isErrorResult(result)) |
| result = recursiveResult; |
| }; |
| |
| // Visit all of the inherited types. |
| for (auto inherited : inheritedTypes) { |
| visitInherited(inherited.getType(), inherited.getTypeRepr()); |
| } |
| |
| return result; |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addConformanceRequirement( |
| PotentialArchetype *PAT, |
| ProtocolDecl *Proto, |
| const RequirementSource *Source) { |
| // Add the requirement, if we haven't done so already. |
| if (!PAT->addConformance(Proto, Source, *this)) |
| return ConstraintResult::Resolved; |
| |
| auto concreteSelf = PAT->getDependentType({}, /*allowUnresolved=*/true); |
| auto protocolSubMap = SubstitutionMap::getProtocolSubstitutions( |
| Proto, concreteSelf, ProtocolConformanceRef(Proto)); |
| |
| // Use the requirement signature to avoid rewalking the entire protocol. This |
| // cannot compute the requirement signature directly, because that may be |
| // infinitely recursive: this code is also used to construct it. |
| if (Proto->isRequirementSignatureComputed()) { |
| auto reqSig = Proto->getRequirementSignature(); |
| |
| auto innerSource = |
| FloatingRequirementSource::viaProtocolRequirement(Source, Proto, |
| /*inferred=*/false); |
| for (auto req : reqSig->getRequirements()) { |
| auto reqResult = addRequirement(req, innerSource, nullptr, |
| &protocolSubMap); |
| if (isErrorResult(reqResult)) return reqResult; |
| } |
| |
| return ConstraintResult::Resolved; |
| } |
| |
| // Add all of the inherited protocol requirements, recursively. |
| if (auto resolver = getLazyResolver()) |
| resolver->resolveInheritedProtocols(Proto); |
| |
| auto protoModule = Proto->getParentModule(); |
| |
| auto inheritedReqResult = |
| addInheritedRequirements(Proto, PAT, Source, protoModule); |
| if (isErrorResult(inheritedReqResult)) |
| return inheritedReqResult; |
| |
| // Add any requirements in the where clause on the protocol. |
| if (auto WhereClause = Proto->getTrailingWhereClause()) { |
| for (auto &req : WhereClause->getRequirements()) { |
| auto innerSource = FloatingRequirementSource::viaProtocolRequirement( |
| Source, Proto, &req, /*inferred=*/false); |
| addRequirement(&req, innerSource, &protocolSubMap, protoModule); |
| } |
| } |
| |
| // Collect all of the inherited associated types and typealiases in the |
| // inherited protocols (recursively). |
| llvm::MapVector<DeclName, TinyPtrVector<TypeDecl *>> inheritedTypeDecls; |
| { |
| Proto->walkInheritedProtocols( |
| [&](ProtocolDecl *inheritedProto) -> TypeWalker::Action { |
| if (inheritedProto == Proto) return TypeWalker::Action::Continue; |
| |
| for (auto req : getProtocolMembers(inheritedProto)) { |
| if (auto typeReq = dyn_cast<TypeDecl>(req)) |
| inheritedTypeDecls[typeReq->getFullName()].push_back(typeReq); |
| } |
| return TypeWalker::Action::Continue; |
| }); |
| } |
| |
| // Local function to find the insertion point for the protocol's "where" |
| // clause, as well as the string to start the insertion ("where" or ","); |
| auto getProtocolWhereLoc = [&]() -> std::pair<SourceLoc, const char *> { |
| // Already has a trailing where clause. |
| if (auto trailing = Proto->getTrailingWhereClause()) |
| return { trailing->getRequirements().back().getSourceRange().End, ", " }; |
| |
| // Inheritance clause. |
| return { Proto->getInherited().back().getSourceRange().End, " where " }; |
| }; |
| |
| // Retrieve the set of requirements that a given associated type declaration |
| // produces, in the form that would be seen in the where clause. |
| auto getAssociatedTypeReqs = [&](AssociatedTypeDecl *assocType, |
| const char *start) { |
| std::string result; |
| { |
| llvm::raw_string_ostream out(result); |
| out << start; |
| interleave(assocType->getInherited(), [&](TypeLoc inheritedType) { |
| out << assocType->getFullName() << ": "; |
| if (auto inheritedTypeRepr = inheritedType.getTypeRepr()) |
| inheritedTypeRepr->print(out); |
| else |
| inheritedType.getType().print(out); |
| }, [&] { |
| out << ", "; |
| }); |
| } |
| return result; |
| }; |
| |
| // Retrieve the requirement that a given typealias introduces when it |
| // overrides an inherited associated type with the same name, as a string |
| // suitable for use in a where clause. |
| auto getTypeAliasReq = [&](TypeAliasDecl *typealias, const char *start) { |
| std::string result; |
| { |
| llvm::raw_string_ostream out(result); |
| out << start; |
| out << typealias->getFullName() << " == "; |
| if (auto underlyingTypeRepr = |
| typealias->getUnderlyingTypeLoc().getTypeRepr()) |
| underlyingTypeRepr->print(out); |
| else |
| typealias->getUnderlyingTypeLoc().getType().print(out); |
| } |
| return result; |
| }; |
| |
| // Form an unsubstituted type referring to the given type declaration, |
| // for use in an inferred same-type requirement. |
| auto formUnsubstitutedType = [&](TypeDecl *typeDecl) -> Type { |
| if (auto assocType = dyn_cast<AssociatedTypeDecl>(typeDecl)) { |
| return DependentMemberType::get( |
| assocType->getProtocol()->getSelfInterfaceType(), |
| assocType); |
| } |
| |
| if (auto typealias = dyn_cast<TypeAliasDecl>(typeDecl)) { |
| // Resolve the underlying type, if we haven't done so yet. |
| if (!typealias->hasInterfaceType()) { |
| getLazyResolver()->resolveDeclSignature(typealias); |
| } |
| |
| return typealias->getUnderlyingTypeLoc().getType(); |
| } |
| |
| return Type(); |
| }; |
| |
| // An inferred same-type requirement between the two type declarations |
| // within this protocol or a protocol it inherits. |
| auto addInferredSameTypeReq = [&](TypeDecl *first, TypeDecl *second) { |
| Type firstType = formUnsubstitutedType(first); |
| if (!firstType) return; |
| |
| Type secondType = formUnsubstitutedType(second); |
| if (!secondType) return; |
| |
| auto inferredSameTypeSource = |
| FloatingRequirementSource::viaProtocolRequirement( |
| Source, Proto, WrittenRequirementLoc(), /*inferred=*/true); |
| |
| addRequirement( |
| Requirement(RequirementKind::SameType, firstType, secondType), |
| inferredSameTypeSource, Proto->getParentModule(), |
| &protocolSubMap); |
| }; |
| |
| // Add requirements for each of the associated types. |
| for (auto Member : getProtocolMembers(Proto)) { |
| if (auto assocTypeDecl = dyn_cast<AssociatedTypeDecl>(Member)) { |
| // Add requirements placed directly on this associated type. |
| Type assocType = DependentMemberType::get(concreteSelf, assocTypeDecl); |
| auto assocResult = |
| addInheritedRequirements(assocTypeDecl, assocType, Source, protoModule); |
| if (isErrorResult(assocResult)) |
| return assocResult; |
| |
| // Add requirements from this associated type's where clause. |
| if (auto WhereClause = assocTypeDecl->getTrailingWhereClause()) { |
| for (auto &req : WhereClause->getRequirements()) { |
| auto innerSource = |
| FloatingRequirementSource::viaProtocolRequirement( |
| Source, Proto, &req, /*inferred=*/false); |
| addRequirement(&req, innerSource, &protocolSubMap, protoModule); |
| } |
| } |
| |
| // Check whether we inherited any types with the same name. |
| auto knownInherited = |
| inheritedTypeDecls.find(assocTypeDecl->getFullName()); |
| if (knownInherited == inheritedTypeDecls.end()) continue; |
| |
| bool shouldWarnAboutRedeclaration = |
| Source->kind == RequirementSource::RequirementSignatureSelf && |
| assocTypeDecl->getDefaultDefinitionLoc().isNull(); |
| for (auto inheritedType : knownInherited->second) { |
| // If we have inherited associated type... |
| if (auto inheritedAssocTypeDecl = |
| dyn_cast<AssociatedTypeDecl>(inheritedType)) { |
| // Infer a same-type requirement among the same-named associated |
| // types. |
| addInferredSameTypeReq(assocTypeDecl, inheritedAssocTypeDecl); |
| |
| // Complain about the first redeclaration. |
| if (shouldWarnAboutRedeclaration) { |
| auto inheritedFromProto = inheritedAssocTypeDecl->getProtocol(); |
| auto fixItWhere = getProtocolWhereLoc(); |
| Diags.diagnose(assocTypeDecl, |
| diag::inherited_associated_type_redecl, |
| assocTypeDecl->getFullName(), |
| inheritedFromProto->getDeclaredInterfaceType()) |
| .fixItInsertAfter( |
| fixItWhere.first, |
| getAssociatedTypeReqs(assocTypeDecl, fixItWhere.second)) |
| .fixItRemove(assocTypeDecl->getSourceRange()); |
| |
| Diags.diagnose(inheritedAssocTypeDecl, diag::decl_declared_here, |
| inheritedAssocTypeDecl->getFullName()); |
| |
| shouldWarnAboutRedeclaration = false; |
| } |
| |
| continue; |
| } |
| |
| // FIXME: this is a weird situation. |
| } |
| |
| inheritedTypeDecls.erase(knownInherited); |
| continue; |
| } |
| |
| if (auto typealias = dyn_cast<TypeAliasDecl>(Member)) { |
| // Check whether we inherited any types with the same name. |
| auto knownInherited = inheritedTypeDecls.find(typealias->getFullName()); |
| if (knownInherited == inheritedTypeDecls.end()) continue; |
| |
| bool shouldWarnAboutRedeclaration = |
| Source->kind == RequirementSource::RequirementSignatureSelf; |
| |
| for (auto inheritedType : knownInherited->second) { |
| // If we have inherited associated type... |
| if (auto inheritedAssocTypeDecl = |
| dyn_cast<AssociatedTypeDecl>(inheritedType)) { |
| // Infer a same-type requirement between the typealias' underlying |
| // type and the inherited associated type. |
| addInferredSameTypeReq(inheritedAssocTypeDecl, typealias); |
| |
| // Warn that one should use where clauses for this. |
| if (shouldWarnAboutRedeclaration) { |
| auto inheritedFromProto = inheritedAssocTypeDecl->getProtocol(); |
| auto fixItWhere = getProtocolWhereLoc(); |
| Diags.diagnose(typealias, |
| diag::typealias_override_associated_type, |
| typealias->getFullName(), |
| inheritedFromProto->getDeclaredInterfaceType()) |
| .fixItInsertAfter(fixItWhere.first, |
| getTypeAliasReq(typealias, fixItWhere.second)) |
| .fixItRemove(typealias->getSourceRange()); |
| Diags.diagnose(inheritedAssocTypeDecl, diag::decl_declared_here, |
| inheritedAssocTypeDecl->getFullName()); |
| |
| shouldWarnAboutRedeclaration = false; |
| } |
| |
| continue; |
| } |
| |
| // FIXME: More typealiases |
| } |
| |
| inheritedTypeDecls.erase(knownInherited); |
| continue; |
| } |
| } |
| |
| // Infer same-type requirements among inherited type declarations. |
| for (auto &entry : inheritedTypeDecls) { |
| if (entry.second.size() < 2) continue; |
| |
| auto firstDecl = entry.second.front(); |
| for (auto otherDecl : ArrayRef<TypeDecl *>(entry.second).slice(1)) { |
| addInferredSameTypeReq(firstDecl, otherDecl); |
| } |
| } |
| |
| return ConstraintResult::Resolved; |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addLayoutRequirementDirect( |
| PotentialArchetype *PAT, |
| LayoutConstraint Layout, |
| const RequirementSource *Source) { |
| auto equivClass = PAT->getOrCreateEquivalenceClass(); |
| |
| // Record this layout constraint. |
| equivClass->layoutConstraints.push_back({PAT, Layout, Source}); |
| |
| // Update the layout in the equivalence class, if we didn't have one already. |
| if (!equivClass->layout) |
| equivClass->layout = Layout; |
| else { |
| // Try to merge layout constraints. |
| auto mergedLayout = equivClass->layout.merge(Layout); |
| if (mergedLayout->isKnownLayout() && mergedLayout != equivClass->layout) |
| equivClass->layout = mergedLayout; |
| } |
| |
| return ConstraintResult::Resolved; |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addLayoutRequirement( |
| UnresolvedType subject, |
| LayoutConstraint layout, |
| FloatingRequirementSource source, |
| UnresolvedHandlingKind unresolvedHandling) { |
| // Resolve the subject. |
| auto resolvedSubject = resolve(subject, source); |
| if (!resolvedSubject) { |
| return handleUnresolvedRequirement(RequirementKind::Layout, subject, |
| layout, source, unresolvedHandling); |
| } |
| |
| // If this layout constraint applies to a concrete type, we can fully |
| // resolve it now. |
| if (resolvedSubject->isType()) { |
| // If a layout requirement was explicitly written on a concrete type, |
| // complain. |
| if (source.isExplicit() && source.getLoc().isValid()) { |
| Diags.diagnose(source.getLoc(), diag::requires_not_suitable_archetype, |
| 0, TypeLoc::withoutLoc(resolvedSubject->getType()), 0); |
| return ConstraintResult::Concrete; |
| } |
| |
| // FIXME: Check whether the layout constraint makes sense for this |
| // concrete type! |
| |
| return ConstraintResult::Resolved; |
| } |
| |
| auto pa = resolvedSubject->getPotentialArchetype(); |
| return addLayoutRequirementDirect(pa, layout, source.getSource(pa)); |
| } |
| |
| void GenericSignatureBuilder::updateSuperclass( |
| PotentialArchetype *T, |
| Type superclass, |
| const RequirementSource *source) { |
| auto equivClass = T->getOrCreateEquivalenceClass(); |
| |
| // Local function to handle the update of superclass conformances |
| // when the superclass constraint changes. |
| auto updateSuperclassConformances = [&] { |
| for (auto proto : T->getConformsTo()) { |
| if (auto superSource = resolveSuperConformance(T, proto)) { |
| for (auto req : getProtocolMembers(proto)) { |
| auto assocType = dyn_cast<AssociatedTypeDecl>(req); |
| if (!assocType) continue; |
| |
| const auto &nestedTypes = T->getNestedTypes(); |
| auto nested = nestedTypes.find(assocType->getName()); |
| if (nested == nestedTypes.end()) continue; |
| |
| for (auto nestedPA : nested->second) { |
| if (nestedPA->getResolvedAssociatedType() == assocType) |
| maybeAddSameTypeRequirementForNestedType(nestedPA, superSource, |
| *this); |
| } |
| } |
| } |
| } |
| }; |
| |
| // If we haven't yet recorded a superclass constraint for this equivalence |
| // class, do so now. |
| if (!equivClass->superclass) { |
| equivClass->superclass = superclass; |
| updateSuperclassConformances(); |
| // Presence of a superclass constraint implies a _Class layout |
| // constraint. |
| auto layoutReqSource = source->viaSuperclass(*this, nullptr); |
| addLayoutRequirementDirect(T, |
| LayoutConstraint::getLayoutConstraint( |
| superclass->getClassOrBoundGenericClass()->isObjC() |
| ? LayoutConstraintKind::Class |
| : LayoutConstraintKind::NativeClass, |
| getASTContext()), |
| layoutReqSource); |
| return; |
| } |
| |
| // T already has a superclass; make sure it's related. |
| auto existingSuperclass = equivClass->superclass; |
| // TODO: In principle, this could be isBindableToSuperclassOf instead of |
| // isExactSubclassOf. If you had: |
| // |
| // class Foo<T> |
| // class Bar: Foo<Int> |
| // |
| // func foo<T, U where U: Foo<T>, U: Bar>(...) { ... } |
| // |
| // then the second constraint should be allowed, constraining U to Bar |
| // and secondarily imposing a T == Int constraint. |
| if (existingSuperclass->isExactSuperclassOf(superclass)) { |
| equivClass->superclass = superclass; |
| |
| // We've strengthened the bound, so update superclass conformances. |
| updateSuperclassConformances(); |
| return; |
| } |
| |
| return; |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addSuperclassRequirementDirect( |
| PotentialArchetype *T, |
| Type superclass, |
| const RequirementSource *source) { |
| // Record the constraint. |
| T->getOrCreateEquivalenceClass()->superclassConstraints |
| .push_back(ConcreteConstraint{T, superclass, source}); |
| |
| // Update the equivalence class with the constraint. |
| updateSuperclass(T, superclass, source); |
| return ConstraintResult::Resolved; |
| } |
| |
| /// Map an unresolved type to a requirement right-hand-side. |
| static GenericSignatureBuilder::RequirementRHS |
| toRequirementRHS(GenericSignatureBuilder::UnresolvedType unresolved) { |
| if (auto pa = unresolved.dyn_cast<PotentialArchetype *>()) |
| return pa; |
| |
| return unresolved.dyn_cast<Type>(); |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addTypeRequirement( |
| UnresolvedType subject, |
| UnresolvedType constraint, |
| FloatingRequirementSource source, |
| UnresolvedHandlingKind unresolvedHandling) { |
| // Resolve the constraint. |
| auto resolvedConstraint = resolve(constraint, source); |
| if (!resolvedConstraint) { |
| return handleUnresolvedRequirement(RequirementKind::Conformance, subject, |
| toRequirementRHS(constraint), source, |
| unresolvedHandling); |
| } |
| |
| // The right-hand side needs to be concrete. |
| if (auto constraintPA = resolvedConstraint->getPotentialArchetype()) { |
| // The constraint type isn't a statically-known constraint. |
| if (source.getLoc().isValid()) { |
| auto constraintType = |
| constraintPA->getDependentType(Impl->GenericParams, |
| /*allowUnresolved=*/true); |
| Diags.diagnose(source.getLoc(), diag::requires_not_suitable_archetype, |
| 1, TypeLoc::withoutLoc(constraintType), 0); |
| } |
| |
| return ConstraintResult::Concrete; |
| } |
| |
| // Check whether we have a reasonable constraint type at all. |
| auto constraintType = resolvedConstraint->getType(); |
| assert(constraintType && "Missing constraint type?"); |
| if (!constraintType->isExistentialType() && |
| !constraintType->getClassOrBoundGenericClass()) { |
| if (source.getLoc().isValid() && !constraintType->hasError()) { |
| auto subjectType = subject.dyn_cast<Type>(); |
| if (!subjectType) |
| subjectType = subject.get<PotentialArchetype *>() |
| ->getDependentType(Impl->GenericParams, |
| /*allowUnresolved=*/true); |
| |
| Diags.diagnose(source.getLoc(), diag::requires_conformance_nonprotocol, |
| TypeLoc::withoutLoc(subjectType), |
| TypeLoc::withoutLoc(constraintType)); |
| } |
| |
| return ConstraintResult::Conflicting; |
| } |
| |
| // Resolve the subject. If we can't, delay the constraint. |
| auto resolvedSubject = resolve(subject, source); |
| if (!resolvedSubject) { |
| auto recordedKind = |
| constraintType->isExistentialType() |
| ? RequirementKind::Conformance |
| : RequirementKind::Superclass; |
| return handleUnresolvedRequirement(recordedKind, subject, constraintType, |
| source, unresolvedHandling); |
| } |
| |
| // If the resolved subject is a type, we can probably perform diagnostics |
| // here. |
| if (resolvedSubject->isType()) { |
| // One cannot explicitly write a constraint on a concrete type. |
| if (source.isExplicit()) { |
| if (source.getLoc().isValid()) { |
| Diags.diagnose(source.getLoc(), diag::requires_not_suitable_archetype, |
| 0, TypeLoc::withoutLoc(resolvedSubject->getType()), 0); |
| } |
| |
| return ConstraintResult::Concrete; |
| } |
| |
| // FIXME: Check the constraint now. |
| return ConstraintResult::Resolved; |
| } |
| |
| auto subjectPA = resolvedSubject->getPotentialArchetype(); |
| assert(subjectPA && "No potential archetype?"); |
| |
| auto resolvedSource = source.getSource(subjectPA); |
| |
| // Protocol requirements. |
| if (constraintType->isExistentialType()) { |
| bool anyErrors = false; |
| auto layout = constraintType->getExistentialLayout(); |
| |
| if (auto layoutConstraint = layout.getLayoutConstraint()) { |
| if (isErrorResult(addLayoutRequirementDirect(subjectPA, |
| layoutConstraint, |
| resolvedSource))) |
| anyErrors = true; |
| } |
| |
| if (layout.superclass) { |
| if (isErrorResult(addSuperclassRequirementDirect(subjectPA, |
| layout.superclass, |
| resolvedSource))) |
| anyErrors = true; |
| } |
| |
| for (auto *proto : layout.getProtocols()) { |
| auto *protoDecl = proto->getDecl(); |
| if (isErrorResult(addConformanceRequirement(subjectPA, protoDecl, |
| resolvedSource))) |
| anyErrors = true; |
| } |
| |
| return anyErrors ? ConstraintResult::Conflicting |
| : ConstraintResult::Resolved; |
| } |
| |
| // Superclass constraint. |
| return addSuperclassRequirementDirect(subjectPA, constraintType, |
| resolvedSource); |
| } |
| |
| void GenericSignatureBuilder::PotentialArchetype::addSameTypeConstraint( |
| PotentialArchetype *otherPA, |
| const RequirementSource *source) { |
| // Update the same-type constraints of this PA to reference the other PA. |
| getOrCreateEquivalenceClass()->sameTypeConstraints[this] |
| .push_back({this, otherPA, source}); |
| |
| if (this != otherPA) { |
| // Update the same-type constraints of the other PA to reference this PA. |
| otherPA->getOrCreateEquivalenceClass()->sameTypeConstraints[otherPA] |
| .push_back({otherPA, this, source}); |
| } |
| } |
| |
| ConstraintResult |
| GenericSignatureBuilder::addSameTypeRequirementBetweenArchetypes( |
| PotentialArchetype *OrigT1, |
| PotentialArchetype *OrigT2, |
| const RequirementSource *Source) |
| { |
| // Record the same-type constraint. |
| OrigT1->addSameTypeConstraint(OrigT2, Source); |
| |
| // Operate on the representatives |
| auto T1 = OrigT1->getRepresentative(); |
| auto T2 = OrigT2->getRepresentative(); |
| |
| // If the representatives are already the same, we're done. |
| if (T1 == T2) |
| return ConstraintResult::Resolved; |
| |
| // Decide which potential archetype is to be considered the representative. |
| // It doesn't specifically matter which we use, but it's a minor optimization |
| // to prefer the canonical type. |
| if (compareDependentTypes(&T2, &T1) < 0) { |
| std::swap(T1, T2); |
| std::swap(OrigT1, OrigT2); |
| } |
| |
| // Merge the equivalence classes. |
| auto equivClass = T1->getOrCreateEquivalenceClass(); |
| auto equivClass2Members = T2->getEquivalenceClassMembers(); |
| for (auto equiv : equivClass2Members) |
| equivClass->members.push_back(equiv); |
| |
| // Grab the old equivalence class, if present. We'll delete it at the end. |
| auto equivClass2 = T2->getEquivalenceClassIfPresent(); |
| SWIFT_DEFER { |
| delete equivClass2; |
| }; |
| |
| // Same-type requirements. |
| if (equivClass2) { |
| for (auto &paSameTypes : equivClass2->sameTypeConstraints) { |
| auto inserted = |
| equivClass->sameTypeConstraints.insert(std::move(paSameTypes)); |
| (void)inserted; |
| assert(inserted.second && "equivalence class already has entry for PA?"); |
| } |
| } |
| |
| // Same-type-to-concrete requirements. |
| if (equivClass2 && equivClass2->concreteType) { |
| if (equivClass->concreteType) { |
| (void)addSameTypeRequirement(equivClass->concreteType, |
| equivClass2->concreteType, Source, |
| UnresolvedHandlingKind::GenerateConstraints, |
| DiagnoseSameTypeConflict{Diags, Source, T1}); |
| } else { |
| equivClass->concreteType = equivClass2->concreteType; |
| } |
| |
| equivClass->concreteTypeConstraints.insert( |
| equivClass->concreteTypeConstraints.end(), |
| equivClass2->concreteTypeConstraints.begin(), |
| equivClass2->concreteTypeConstraints.end()); |
| } |
| |
| // Make T1 the representative of T2, merging the equivalence classes. |
| T2->representativeOrEquivClass = T1; |
| |
| // Superclass requirements. |
| if (equivClass2 && equivClass2->superclass) { |
| const RequirementSource *source2; |
| if (auto existingSource2 = |
| equivClass2->findAnySuperclassConstraintAsWritten(OrigT2)) |
| source2 = existingSource2->source; |
| else |
| source2 = equivClass2->superclassConstraints.front().source; |
| |
| (void)updateSuperclass(T1, equivClass2->superclass, source2); |
| |
| equivClass->superclassConstraints.insert( |
| equivClass->superclassConstraints.end(), |
| equivClass2->superclassConstraints.begin(), |
| equivClass2->superclassConstraints.end()); |
| } |
| |
| // Add all of the protocol conformance requirements of T2 to T1. |
| if (equivClass2) { |
| for (const auto &entry : equivClass2->conformsTo) { |
| T1->addConformance(entry.first, entry.second.front().source, *this); |
| |
| auto &constraints1 = equivClass->conformsTo[entry.first]; |
| constraints1.insert(constraints1.end(), |
| entry.second.begin() + 1, |
| entry.second.end()); |
| } |
| } |
| |
| // Recursively merge the associated types of T2 into T1. |
| auto dependentT1 = T1->getDependentType({ }, /*allowUnresolved=*/true); |
| for (auto equivT2 : equivClass2Members) { |
| for (auto T2Nested : equivT2->NestedTypes) { |
| Type nestedT1 = DependentMemberType::get(dependentT1, T2Nested.first); |
| if (isErrorResult( |
| addSameTypeRequirement( |
| nestedT1, T2Nested.second.front(), |
| FloatingRequirementSource::forNestedTypeNameMatch( |
| Source, T2Nested.first), |
| UnresolvedHandlingKind::GenerateConstraints))) |
| return ConstraintResult::Conflicting; |
| } |
| } |
| |
| return ConstraintResult::Resolved; |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addSameTypeRequirementToConcrete( |
| PotentialArchetype *T, |
| Type Concrete, |
| const RequirementSource *Source) { |
| auto rep = T->getRepresentative(); |
| auto equivClass = rep->getOrCreateEquivalenceClass(); |
| |
| // Record the concrete type and its source. |
| equivClass->concreteTypeConstraints.push_back( |
| ConcreteConstraint{T, Concrete, Source}); |
| |
| // If we've already been bound to a type, match that type. |
| if (equivClass->concreteType) { |
| return addSameTypeRequirement(equivClass->concreteType, Concrete, Source, |
| UnresolvedHandlingKind::GenerateConstraints, |
| DiagnoseSameTypeConflict{ Diags, Source, T}); |
| |
| } |
| |
| // Record the requirement. |
| equivClass->concreteType = Concrete; |
| |
| // Make sure the concrete type fulfills the requirements on the archetype. |
| // FIXME: Move later... |
| DenseMap<ProtocolDecl *, ProtocolConformanceRef> conformances; |
| CanType depTy = rep->getDependentType({ }, /*allowUnresolved=*/true) |
| ->getCanonicalType(); |
| for (auto protocol : rep->getConformsTo()) { |
| auto conformance = |
| getLookupConformanceFn()(depTy, Concrete, |
| protocol->getDeclaredInterfaceType() |
| ->castTo<ProtocolType>()); |
| if (!conformance) { |
| if (!Concrete->hasError()) { |
| Diags.diagnose(Source->getLoc(), |
| diag::requires_generic_param_same_type_does_not_conform, |
| Concrete, protocol->getName()); |
| } |
| return ConstraintResult::Conflicting; |
| } |
| |
| conformances.insert({protocol, *conformance}); |
| |
| // Abstract conformances are acceptable for existential types. |
| assert(conformance->isConcrete() || Concrete->isExistentialType()); |
| |
| // Update the requirement source now that we know it's concrete. |
| // FIXME: Bad concrete source info. |
| auto concreteSource = Source->viaConcrete(*this, |
| conformance->isConcrete() |
| ? conformance->getConcrete() |
| : nullptr); |
| equivClass->conformsTo[protocol].push_back({T, protocol, concreteSource}); |
| } |
| |
| // Eagerly resolve any existing nested types to their concrete forms (others |
| // will be "concretized" as they are constructed, in getNestedType). |
| for (auto equivT : rep->getEquivalenceClassMembers()) { |
| for (auto nested : equivT->getNestedTypes()) { |
| concretizeNestedTypeFromConcreteParent( |
| equivT, Source, nested.second.front(), *this, |
| [&](ProtocolDecl *proto) -> ProtocolConformanceRef { |
| return conformances.find(proto)->second; |
| }); |
| } |
| } |
| |
| return ConstraintResult::Resolved; |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addSameTypeRequirementBetweenConcrete( |
| Type type1, Type type2, FloatingRequirementSource source, |
| llvm::function_ref<void(Type, Type)> diagnoseMismatch) { |
| // Local class to handle matching the two sides of the same-type constraint. |
| class ReqTypeMatcher : public TypeMatcher<ReqTypeMatcher> { |
| GenericSignatureBuilder &builder; |
| FloatingRequirementSource source; |
| Type outerType1, outerType2; |
| llvm::function_ref<void(Type, Type)> diagnoseMismatch; |
| |
| public: |
| ReqTypeMatcher(GenericSignatureBuilder &builder, |
| FloatingRequirementSource source, |
| Type outerType1, Type outerType2, |
| llvm::function_ref<void(Type, Type)> diagnoseMismatch) |
| : builder(builder), source(source), outerType1(outerType1), |
| outerType2(outerType2), diagnoseMismatch(diagnoseMismatch) {} |
| |
| bool mismatch(TypeBase *firstType, TypeBase *secondType, |
| Type sugaredFirstType) { |
| // If the mismatch was in the first layer (i.e. what was fed to |
| // addSameTypeRequirementBetweenConcrete), then this is a fundamental |
| // mismatch, and we need to diagnose it. This is what breaks the mutual |
| // recursion between addSameTypeRequirement and |
| // addSameTypeRequirementBetweenConcrete. |
| if (outerType1->isEqual(firstType) && outerType2->isEqual(secondType)) { |
| diagnoseMismatch(sugaredFirstType, secondType); |
| return false; |
| } |
| |
| auto failed = builder.addSameTypeRequirement( |
| sugaredFirstType, Type(secondType), source, |
| UnresolvedHandlingKind::GenerateConstraints, diagnoseMismatch); |
| return !isErrorResult(failed); |
| } |
| } matcher(*this, source, type1, type2, diagnoseMismatch); |
| |
| return matcher.match(type1, type2) ? ConstraintResult::Resolved |
| : ConstraintResult::Conflicting; |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addSameTypeRequirement( |
| UnresolvedType paOrT1, |
| UnresolvedType paOrT2, |
| FloatingRequirementSource source, |
| UnresolvedHandlingKind unresolvedHandling) { |
| return addSameTypeRequirement(paOrT1, paOrT2, source, unresolvedHandling, |
| [&](Type type1, Type type2) { |
| Diags.diagnose(source.getLoc(), diag::requires_same_concrete_type, |
| type1, type2); |
| }); |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addSameTypeRequirement( |
| UnresolvedType paOrT1, UnresolvedType paOrT2, |
| FloatingRequirementSource source, |
| UnresolvedHandlingKind unresolvedHandling, |
| llvm::function_ref<void(Type, Type)> diagnoseMismatch) { |
| |
| auto resolved1 = resolve(paOrT1, source); |
| if (!resolved1) { |
| return handleUnresolvedRequirement(RequirementKind::SameType, paOrT1, |
| toRequirementRHS(paOrT2), source, |
| unresolvedHandling); |
| } |
| |
| auto resolved2 = resolve(paOrT2, source); |
| if (!resolved2) { |
| return handleUnresolvedRequirement(RequirementKind::SameType, paOrT1, |
| toRequirementRHS(paOrT2), source, |
| unresolvedHandling); |
| } |
| |
| return addSameTypeRequirementDirect(*resolved1, *resolved2, source, |
| diagnoseMismatch); |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addSameTypeRequirementDirect( |
| ResolvedType paOrT1, |
| ResolvedType paOrT2, |
| FloatingRequirementSource source) { |
| return addSameTypeRequirementDirect(paOrT1, paOrT2, source, |
| [&](Type type1, Type type2) { |
| Diags.diagnose(source.getLoc(), diag::requires_same_concrete_type, |
| type1, type2); |
| }); |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addSameTypeRequirementDirect( |
| ResolvedType paOrT1, ResolvedType paOrT2, FloatingRequirementSource source, |
| llvm::function_ref<void(Type, Type)> diagnoseMismatch) { |
| auto pa1 = paOrT1.getPotentialArchetype(); |
| auto pa2 = paOrT2.getPotentialArchetype(); |
| auto t1 = paOrT1.getType(); |
| auto t2 = paOrT2.getType(); |
| |
| // If both sides of the requirement are type parameters, equate them. |
| if (pa1 && pa2) { |
| return addSameTypeRequirementBetweenArchetypes(pa1, pa2, |
| source.getSource(pa1)); |
| // If just one side is a type parameter, map it to a concrete type. |
| } else if (pa1) { |
| return addSameTypeRequirementToConcrete(pa1, t2, source.getSource(pa1)); |
| } else if (pa2) { |
| return addSameTypeRequirementToConcrete(pa2, t1, source.getSource(pa2)); |
| } else { |
| return addSameTypeRequirementBetweenConcrete(t1, t2, source, |
| diagnoseMismatch); |
| } |
| } |
| |
| // Local function to mark the given associated type as recursive, |
| // diagnosing it if this is the first such occurrence. |
| void GenericSignatureBuilder::markPotentialArchetypeRecursive( |
| PotentialArchetype *pa, ProtocolDecl *proto, const RequirementSource *source) { |
| if (pa->isRecursive()) |
| return; |
| pa->setIsRecursive(); |
| |
| pa->addConformance(proto, source, *this); |
| if (!pa->getParent()) |
| return; |
| |
| auto assocType = pa->getResolvedAssociatedType(); |
| if (!assocType || assocType->isInvalid()) |
| return; |
| |
| Diags.diagnose(assocType->getLoc(), diag::recursive_requirement_reference); |
| |
| // Silence downstream errors referencing this associated type. |
| assocType->setInvalid(); |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addInheritedRequirements( |
| TypeDecl *decl, |
| UnresolvedType type, |
| const RequirementSource *parentSource, |
| ModuleDecl *inferForModule) { |
| if (isa<AssociatedTypeDecl>(decl) && |
| decl->hasInterfaceType() && |
| decl->getInterfaceType()->is<ErrorType>()) |
| return ConstraintResult::Resolved; |
| |
| // Walk the 'inherited' list to identify requirements. |
| if (auto resolver = getLazyResolver()) |
| resolver->resolveInheritanceClause(decl); |
| |
| // Local function to get the source. |
| auto getFloatingSource = [&](const TypeRepr *typeRepr, bool forInferred) { |
| if (parentSource) { |
| if (auto assocType = dyn_cast<AssociatedTypeDecl>(decl)) { |
| auto proto = assocType->getProtocol(); |
| return FloatingRequirementSource::viaProtocolRequirement( |
| parentSource, proto, typeRepr, forInferred); |
| } |
| |
| auto proto = cast<ProtocolDecl>(decl); |
| return FloatingRequirementSource::viaProtocolRequirement( |
| parentSource, proto, typeRepr, forInferred); |
| } |
| |
| // We are inferring requirements. |
| if (forInferred) |
| return FloatingRequirementSource::forInferred(typeRepr); |
| |
| // Explicit requirement. |
| if (typeRepr) |
| return FloatingRequirementSource::forExplicit(typeRepr); |
| |
| // An abstract explicit requirement. |
| return FloatingRequirementSource::forAbstract(); |
| }; |
| |
| auto visitType = [&](Type inheritedType, const TypeRepr *typeRepr) { |
| if (inferForModule) { |
| inferRequirements(*inferForModule, |
| TypeLoc(const_cast<TypeRepr *>(typeRepr), |
| inheritedType), |
| getFloatingSource(typeRepr, /*forInferred=*/true)); |
| } |
| |
| // Check for direct recursion. |
| if (auto assocType = dyn_cast<AssociatedTypeDecl>(decl)) { |
| auto proto = assocType->getProtocol(); |
| if (auto inheritedProto = inheritedType->getAs<ProtocolType>()) { |
| if (inheritedProto->getDecl() == proto || |
| inheritedProto->getDecl()->inheritsFrom(proto)) { |
| auto source = getFloatingSource(typeRepr, /*forInferred=*/false); |
| if (auto resolved = resolve(type, source)) { |
| if (auto pa = resolved->getPotentialArchetype()) { |
| markPotentialArchetypeRecursive(pa, proto, source.getSource(pa)); |
| return ConstraintResult::Conflicting; |
| } |
| } |
| } |
| } |
| } |
| |
| return addTypeRequirement(type, inheritedType, |
| getFloatingSource(typeRepr, |
| /*forInferred=*/false), |
| UnresolvedHandlingKind::GenerateConstraints); |
| }; |
| |
| return visitInherited(decl->getInherited(), visitType); |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addRequirement( |
| const RequirementRepr *req, |
| ModuleDecl *inferForModule) { |
| return addRequirement(req, |
| FloatingRequirementSource::forExplicit(req), |
| nullptr, |
| inferForModule); |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addRequirement( |
| const RequirementRepr *Req, |
| FloatingRequirementSource source, |
| const SubstitutionMap *subMap, |
| ModuleDecl *inferForModule) { |
| auto subst = [&](Type t) { |
| if (subMap) |
| return t.subst(*subMap); |
| |
| return t; |
| }; |
| |
| auto getInferredTypeLoc = [=](Type type, TypeLoc existingTypeLoc) { |
| if (subMap) return TypeLoc::withoutLoc(type); |
| return existingTypeLoc; |
| }; |
| |
| switch (Req->getKind()) { |
| case RequirementReprKind::LayoutConstraint: { |
| auto subject = subst(Req->getSubject()); |
| if (inferForModule) { |
| inferRequirements(*inferForModule, |
| getInferredTypeLoc(subject, Req->getSubjectLoc()), |
| source.asInferred(Req->getSubjectLoc().getTypeRepr())); |
| } |
| |
| return addLayoutRequirement(subject, |
| Req->getLayoutConstraint(), |
| source, |
| UnresolvedHandlingKind::GenerateConstraints); |
| } |
| |
| case RequirementReprKind::TypeConstraint: { |
| auto subject = subst(Req->getSubject()); |
| auto constraint = subst(Req->getConstraint()); |
| if (inferForModule) { |
| inferRequirements(*inferForModule, |
| getInferredTypeLoc(subject, Req->getSubjectLoc()), |
| source.asInferred(Req->getSubjectLoc().getTypeRepr())); |
| inferRequirements(*inferForModule, |
| getInferredTypeLoc(constraint, |
| Req->getConstraintLoc()), |
| source.asInferred( |
| Req->getConstraintLoc().getTypeRepr())); |
| } |
| return addTypeRequirement(subject, constraint, source, |
| UnresolvedHandlingKind::GenerateConstraints); |
| } |
| |
| case RequirementReprKind::SameType: { |
| // Require that at least one side of the requirement contain a type |
| // parameter. |
| if (!Req->getFirstType()->hasTypeParameter() && |
| !Req->getSecondType()->hasTypeParameter()) { |
| if (!Req->getFirstType()->hasError() && |
| !Req->getSecondType()->hasError()) { |
| Diags.diagnose(Req->getEqualLoc(), |
| diag::requires_no_same_type_archetype) |
| .highlight(Req->getFirstTypeLoc().getSourceRange()) |
| .highlight(Req->getSecondTypeLoc().getSourceRange()); |
| } |
| |
| return ConstraintResult::Concrete; |
| } |
| |
| auto firstType = subst(Req->getFirstType()); |
| auto secondType = subst(Req->getSecondType()); |
| if (inferForModule) { |
| inferRequirements(*inferForModule, |
| getInferredTypeLoc(firstType, Req->getFirstTypeLoc()), |
| source.asInferred( |
| Req->getFirstTypeLoc().getTypeRepr())); |
| inferRequirements(*inferForModule, |
| getInferredTypeLoc(secondType, |
| Req->getSecondTypeLoc()), |
| source.asInferred( |
| Req->getSecondTypeLoc().getTypeRepr())); |
| } |
| return addRequirement(Requirement(RequirementKind::SameType, |
| firstType, secondType), |
| source, nullptr); |
| } |
| } |
| |
| llvm_unreachable("Unhandled requirement?"); |
| } |
| |
| ConstraintResult GenericSignatureBuilder::addRequirement( |
| const Requirement &req, |
| FloatingRequirementSource source, |
| ModuleDecl *inferForModule, |
| const SubstitutionMap *subMap) { |
| auto subst = [&](Type t) { |
| if (subMap) |
| return t.subst(*subMap); |
| |
| return t; |
| }; |
| |
| |
| switch (req.getKind()) { |
| case RequirementKind::Superclass: |
| case RequirementKind::Conformance: { |
| auto firstType = subst(req.getFirstType()); |
| auto secondType = subst(req.getSecondType()); |
| if (!firstType || !secondType) |
| return ConstraintResult::Conflicting; |
| |
| if (inferForModule) { |
| inferRequirements(*inferForModule, TypeLoc::withoutLoc(firstType), |
| FloatingRequirementSource::forInferred(nullptr)); |
| inferRequirements(*inferForModule, TypeLoc::withoutLoc(secondType), |
| FloatingRequirementSource::forInferred(nullptr)); |
| } |
| |
| return addTypeRequirement(firstType, secondType, source, |
| UnresolvedHandlingKind::GenerateConstraints); |
| } |
| |
| case RequirementKind::Layout: { |
| auto firstType = subst(req.getFirstType()); |
| if (!firstType) |
| return ConstraintResult::Conflicting; |
| |
| if (inferForModule) { |
| inferRequirements(*inferForModule, TypeLoc::withoutLoc(firstType), |
| FloatingRequirementSource::forInferred(nullptr)); |
| } |
| |
| return addLayoutRequirement(firstType, req.getLayoutConstraint(), source, |
| UnresolvedHandlingKind::GenerateConstraints); |
| } |
| |
| case RequirementKind::SameType: { |
| auto firstType = subst(req.getFirstType()); |
| auto secondType = subst(req.getSecondType()); |
| if (!firstType || !secondType) |
| return ConstraintResult::Conflicting; |
| |
| if (inferForModule) { |
| inferRequirements(*inferForModule, TypeLoc::withoutLoc(firstType), |
| FloatingRequirementSource::forInferred(nullptr)); |
| inferRequirements(*inferForModule, TypeLoc::withoutLoc(secondType), |
| FloatingRequirementSource::forInferred(nullptr)); |
| } |
| |
| return addSameTypeRequirement( |
| firstType, secondType, source, |
| UnresolvedHandlingKind::GenerateConstraints, |
| [&](Type type1, Type type2) { |
| if (source.getLoc().isValid()) |
| Diags.diagnose(source.getLoc(), diag::requires_same_concrete_type, |
| type1, type2); |
| }); |
| } |
| } |
| |
| llvm_unreachable("Unhandled requirement?"); |
| } |
| |
| /// AST walker that infers requirements from type representations. |
| class GenericSignatureBuilder::InferRequirementsWalker : public TypeWalker { |
| ModuleDecl &module; |
| GenericSignatureBuilder &Builder; |
| FloatingRequirementSource source; |
| |
| public: |
| InferRequirementsWalker(ModuleDecl &module, |
| GenericSignatureBuilder &builder, |
| FloatingRequirementSource source) |
| : module(module), Builder(builder), source(source) { } |
| |
| Action walkToTypePost(Type ty) override { |
| auto boundGeneric = ty->getAs<BoundGenericType>(); |
| if (!boundGeneric) |
| return Action::Continue; |
| |
| auto *decl = boundGeneric->getDecl(); |
| auto genericSig = decl->getGenericSignature(); |
| if (!genericSig) |
| return Action::Stop; |
| |
| /// Retrieve the substitution. |
| auto subMap = boundGeneric->getContextSubstitutionMap( |
| &module, decl, decl->getGenericEnvironment()); |
| |
| // Handle the requirements. |
| // FIXME: Inaccurate TypeReprs. |
| for (const auto &req : genericSig->getRequirements()) { |
| Builder.addRequirement(req, source, nullptr, &subMap); |
| } |
| |
| return Action::Continue; |
| } |
| }; |
| |
| void GenericSignatureBuilder::inferRequirements( |
| ModuleDecl &module, |
| TypeLoc type, |
| FloatingRequirementSource source) { |
| if (!type.getType()) |
| return; |
| // FIXME: Crummy source-location information. |
| InferRequirementsWalker walker(module, *this, source); |
| type.getType().walk(walker); |
| } |
| |
| void GenericSignatureBuilder::inferRequirements( |
| ModuleDecl &module, |
| ParameterList *params, |
| GenericParamList *genericParams) { |
| if (genericParams == nullptr) |
| return; |
| |
| for (auto P : *params) { |
| inferRequirements(module, P->getTypeLoc(), |
| FloatingRequirementSource::forInferred( |
| P->getTypeLoc().getTypeRepr())); |
| } |
| } |
| |
| /// Perform typo correction on the given nested type, producing the |
| /// corrected name (if successful). |
| static Identifier typoCorrectNestedType( |
| GenericSignatureBuilder::PotentialArchetype *pa) { |
| StringRef name = pa->getNestedName().str(); |
| |
| // Look through all of the associated types of all of the protocols |
| // to which the parent conforms. |
| llvm::SmallVector<Identifier, 2> bestMatches; |
| unsigned bestEditDistance = 0; |
| unsigned maxScore = (name.size() + 1) / 3; |
| for (auto proto : pa->getParent()->getConformsTo()) { |
| for (auto member : getProtocolMembers(proto)) { |
| auto assocType = dyn_cast<AssociatedTypeDecl>(member); |
| if (!assocType) |
| continue; |
| |
| unsigned dist = name.edit_distance(assocType->getName().str(), |
| /*AllowReplacements=*/true, |
| maxScore); |
| assert(dist > 0 && "nested type should have matched associated type"); |
| if (bestEditDistance == 0 || dist == bestEditDistance) { |
| bestEditDistance = dist; |
| maxScore = bestEditDistance; |
| bestMatches.push_back(assocType->getName()); |
| } else if (dist < bestEditDistance) { |
| bestEditDistance = dist; |
| maxScore = bestEditDistance; |
| bestMatches.clear(); |
| bestMatches.push_back(assocType->getName()); |
| } |
| } |
| } |
| |
| // FIXME: Look through the superclass. |
| |
| // If we didn't find any matches at all, fail. |
| if (bestMatches.empty()) |
| return Identifier(); |
| |
| // Make sure that we didn't find more than one match at the best |
| // edit distance. |
| for (auto other : llvm::makeArrayRef(bestMatches).slice(1)) { |
| if (other != bestMatches.front()) |
| return Identifier(); |
| } |
| |
| return bestMatches.front(); |
| } |
| |
| namespace swift { |
| template<typename T> |
| bool operator<(const Constraint<T> &lhs, const Constraint<T> &rhs) { |
| auto lhsPA = lhs.archetype; |
| auto rhsPA = rhs.archetype; |
| if (int result = compareDependentTypes(&lhsPA, &rhsPA)) |
| return result < 0; |
| |
| if (int result = lhs.source->compare(rhs.source)) |
| return result < 0; |
| |
| return false; |
| } |
| |
| template<typename T> |
| bool operator==(const Constraint<T> &lhs, const Constraint<T> &rhs){ |
| return lhs.archetype == rhs.archetype && |
| lhs.value == rhs.value && |
| lhs.source == rhs.source; |
| } |
| |
| template<> |
| bool operator==(const Constraint<Type> &lhs, const Constraint<Type> &rhs){ |
| return lhs.archetype == rhs.archetype && |
| lhs.value->isEqual(rhs.value) && |
| lhs.source == rhs.source; |
| } |
| } // namespace swift |
| |
| namespace { |
| /// Retrieve the representative constraint that will be used for diagnostics. |
| template<typename T> |
| Optional<Constraint<T>> findRepresentativeConstraint( |
| ArrayRef<Constraint<T>> constraints, |
| llvm::function_ref<bool(const Constraint<T> &)> |
| isSuitableRepresentative) { |
| // Find a representative constraint. |
| Optional<Constraint<T>> representativeConstraint; |
| for (const auto &constraint : constraints) { |
| // If this isn't a suitable representative constraint, ignore it. |
| if (!isSuitableRepresentative(constraint)) |
| continue; |
| |
| // Check whether this constraint is better than the best we've seen so far |
| // at being the representative constraint against which others will be |
| // compared. |
| if (!representativeConstraint) { |
| representativeConstraint = constraint; |
| continue; |
| } |
| |
| // We prefer constraints rooted at inferred requirements to ones rooted |
| // on explicit requirements, because the former won't be diagnosed |
| // directly. |
| bool thisIsInferred = constraint.source->isInferredRequirement(); |
| bool representativeIsInferred = representativeConstraint->source->isInferredRequirement(); |
| if (thisIsInferred != representativeIsInferred) { |
| if (thisIsInferred) |
| representativeConstraint = constraint; |
| continue; |
| } |
| |
| // We prefer derived constraints to non-derived constraints. |
| bool thisIsDerived = constraint.source->isDerivedRequirement(); |
| bool representativeIsDerived = |
| representativeConstraint->source->isDerivedRequirement(); |
| if (thisIsDerived != representativeIsDerived) { |
| if (thisIsDerived) |
| representativeConstraint = constraint; |
| |
| continue; |
| } |
| |
| // We prefer constraints with locations to constraints without locations. |
| bool thisHasValidSourceLoc = constraint.source->getLoc().isValid(); |
| bool representativeHasValidSourceLoc = |
| representativeConstraint->source->getLoc().isValid(); |
| if (thisHasValidSourceLoc != representativeHasValidSourceLoc) { |
| if (thisHasValidSourceLoc) |
| representativeConstraint = constraint; |
| |
| continue; |
| } |
| |
| // Otherwise, order via the constraint itself. |
| if (constraint < *representativeConstraint) |
| representativeConstraint = constraint; |
| } |
| |
| return representativeConstraint; |
| } |
| } // end anonymous namespace |
| |
| void |
| GenericSignatureBuilder::finalize(SourceLoc loc, |
| ArrayRef<GenericTypeParamType *> genericParams, |
| bool allowConcreteGenericParams) { |
| // Process any delayed requirements that we can handle now. |
| processDelayedRequirements(); |
| |
| assert(!Impl->finalized && "Already finalized builder"); |
| #ifndef NDEBUG |
| Impl->finalized = true; |
| #endif |
| |
| // Local function (+ cache) describing the set of potential archetypes |
| // directly referenced by the concrete same-type constraint of the given |
| // potential archetype. Both the inputs and results are the representatives |
| // of their equivalence classes. |
| llvm::DenseMap<PotentialArchetype *, |
| SmallPtrSet<PotentialArchetype *, 4>> concretePAs; |
| auto getConcreteReferencedPAs |
| = [&](PotentialArchetype *pa) -> SmallPtrSet<PotentialArchetype *, 4> { |
| assert(pa == pa->getRepresentative() && "Only use with representatives"); |
| auto known = concretePAs.find(pa); |
| if (known != concretePAs.end()) |
| return known->second; |
| |
| SmallPtrSet<PotentialArchetype *, 4> referencedPAs; |
| if (!pa->isConcreteType() || !pa->getConcreteType()->hasTypeParameter()) |
| return referencedPAs; |
| |
| if (auto concreteType = pa->getConcreteType()) { |
| if (concreteType->hasTypeParameter()) { |
| concreteType.visit([&](Type type) { |
| if (type->isTypeParameter()) { |
| if (auto referencedPA = |
| resolveArchetype(type, |
| ArchetypeResolutionKind::AlreadyKnown)) { |
| referencedPAs.insert(referencedPA->getRepresentative()); |
| } |
| } |
| }); |
| } |
| } |
| |
| concretePAs[pa] = referencedPAs; |
| return referencedPAs; |
| }; |
| |
| /// Check whether the given type references the archetype. |
| auto isRecursiveConcreteType = [&](PotentialArchetype *archetype, |
| bool isSuperclass) { |
| SmallPtrSet<PotentialArchetype *, 4> visited; |
| SmallVector<PotentialArchetype *, 4> stack; |
| stack.push_back(archetype); |
| visited.insert(archetype); |
| |
| // Check whether the specific type introduces recursion. |
| auto checkTypeRecursion = [&](Type type) { |
| if (!type->hasTypeParameter()) return false; |
| |
| return type.findIf([&](Type type) { |
| if (type->isTypeParameter()) { |
| if (auto referencedPA = |
| resolveArchetype(type, ArchetypeResolutionKind::AlreadyKnown)) { |
| referencedPA = referencedPA->getRepresentative(); |
| if (referencedPA == archetype) return true; |
| |
| if (visited.insert(referencedPA).second) |
| stack.push_back(referencedPA); |
| } |
| } |
| |
| return false; |
| }); |
| }; |
| |
| while (!stack.empty()) { |
| auto pa = stack.back(); |
| stack.pop_back(); |
| |
| // If we're checking superclasses, do so now. |
| if (isSuperclass) { |
| if (auto superclass = pa->getSuperclass()) { |
| if (checkTypeRecursion(superclass)) return true; |
| } |
| } |
| |
| // Otherwise, look for the potential archetypes referenced by |
| // same-type constraints. |
| for (auto referencedPA : getConcreteReferencedPAs(pa)) { |
| // If we found a reference to the original archetype, it's recursive. |
| if (referencedPA == archetype) return true; |
| |
| if (visited.insert(referencedPA).second) |
| stack.push_back(referencedPA); |
| } |
| } |
| |
| return false; |
| }; |
| |
| // Check for recursive or conflicting same-type bindings and superclass |
| // constraints. |
| visitPotentialArchetypes([&](PotentialArchetype *archetype) { |
| if (archetype != archetype->getRepresentative()) return; |
| |
| auto equivClass = archetype->getOrCreateEquivalenceClass(); |
| if (equivClass->concreteType) { |
| // Check for recursive same-type bindings. |
| if (isRecursiveConcreteType(archetype, /*isSuperclass=*/false)) { |
| if (auto constraint = |
| equivClass->findAnyConcreteConstraintAsWritten()) { |
| Diags.diagnose(constraint->source->getLoc(), |
| diag::recursive_same_type_constraint, |
| archetype->getDependentType(genericParams, |
| /*allowUnresolved=*/true), |
| constraint->value); |
| } |
| |
| archetype->RecursiveConcreteType = true; |
| } else { |
| checkConcreteTypeConstraints(genericParams, archetype); |
| } |
| } |
| |
| // Check for recursive superclass bindings. |
| if (equivClass->superclass) { |
| if (isRecursiveConcreteType(archetype, /*isSuperclass=*/true)) { |
| if (auto source = equivClass->findAnySuperclassConstraintAsWritten()) { |
| Diags.diagnose(source->source->getLoc(), |
| diag::recursive_superclass_constraint, |
| source->archetype->getDependentType( |
| genericParams, |
| /*allowUnresolved=*/true), |
| equivClass->superclass); |
| } |
| |
| archetype->RecursiveSuperclassType = true; |
| } else { |
| checkSuperclassConstraints(genericParams, archetype); |
| } |
| } |
| |
| checkConformanceConstraints(genericParams, archetype); |
| checkLayoutConstraints(genericParams, archetype); |
| checkSameTypeConstraints(genericParams, archetype); |
| }); |
| |
| // Check for generic parameters which have been made concrete or equated |
| // with each other. |
| if (!allowConcreteGenericParams) { |
| SmallPtrSet<PotentialArchetype *, 4> visited; |
| |
| unsigned depth = 0; |
| for (const auto &gp : Impl->GenericParams) |
| depth = std::max(depth, gp->getDepth()); |
| |
| for (const auto pa : Impl->PotentialArchetypes) { |
| auto rep = pa->getRepresentative(); |
| |
| if (pa->getRootGenericParamKey().Depth < depth) |
| continue; |
| |
| if (!visited.insert(rep).second) |
| continue; |
| |
| // Don't allow a generic parameter to be equivalent to a concrete type, |
| // because then we don't actually have a parameter. |
| auto equivClass = rep->getOrCreateEquivalenceClass(); |
| if (equivClass->concreteType) { |
| if (auto constraint = equivClass->findAnyConcreteConstraintAsWritten()) |
| Diags.diagnose(constraint->source->getLoc(), |
| diag::requires_generic_param_made_equal_to_concrete, |
| rep->getDependentType(genericParams, |
| /*allowUnresolved=*/true)); |
| continue; |
| } |
| |
| // Don't allow two generic parameters to be equivalent, because then we |
| // don't actually have two parameters. |
| for (auto other : rep->getEquivalenceClassMembers()) { |
| // If it isn't a generic parameter, skip it. |
| if (other == pa || !other->isGenericParam()) continue; |
| |
| // Try to find an exact constraint that matches 'other'. |
| auto repConstraint = |
| findRepresentativeConstraint<PotentialArchetype *>( |
| pa->getSameTypeConstraints(), |
| [other](const Constraint<PotentialArchetype *> &constraint) { |
| return constraint.value == other; |
| }); |
| |
| |
| // Otherwise, just take any old constraint. |
| if (!repConstraint) { |
| repConstraint = |
| findRepresentativeConstraint<PotentialArchetype *>( |
| pa->getSameTypeConstraints(), |
| [other](const Constraint<PotentialArchetype *> &constraint) { |
| return true; |
| }); |
| } |
| |
| if (repConstraint && repConstraint->source->getLoc().isValid()) { |
| Diags.diagnose(repConstraint->source->getLoc(), |
| diag::requires_generic_params_made_equal, |
| pa->getDependentType(genericParams, true), |
| other->getDependentType(genericParams, true)); |
| } |
| break; |
| } |
| } |
| } |
| |
| // If any nested types remain unresolved, produce diagnostics. |
| if (Impl->NumUnresolvedNestedTypes > 0) { |
| visitPotentialArchetypes([&](PotentialArchetype *pa) { |
| // We only care about nested types that haven't been resolved. |
| if (pa->getParent() == nullptr || pa->getResolvedAssociatedType() || |
| pa->getTypeAliasDecl() || |
| /* FIXME: Should be able to handle this earlier */pa->getSuperclass()) |
| return; |
| |
| // Try to typo correct to a nested type name. |
| Identifier correction = typoCorrectNestedType(pa); |
| if (correction.empty()) { |
| pa->setInvalid(); |
| return; |
| } |
| |
| // Note that this is being renamed. |
| pa->saveNameForRenaming(); |
| Impl->RenamedNestedTypes.push_back(pa); |
| |
| // Resolve the associated type and merge the potential archetypes. |
| auto replacement = pa->getParent()->getNestedType(correction, *this); |
| pa->resolveAssociatedType(replacement->getResolvedAssociatedType(), |
| *this); |
| addSameTypeRequirement(pa, replacement, |
| RequirementSource::forNestedTypeNameMatch(pa), |
| UnresolvedHandlingKind::GenerateConstraints); |
| }); |
| } |
| } |
| |
| bool GenericSignatureBuilder::diagnoseRemainingRenames( |
| SourceLoc loc, |
| ArrayRef<GenericTypeParamType *> genericParams) { |
| bool invalid = false; |
| |
| for (auto pa : Impl->RenamedNestedTypes) { |
| if (pa->alreadyDiagnosedRename()) continue; |
| |
| Diags.diagnose(loc, diag::invalid_member_type_suggest, |
| pa->getParent()->getDependentType(genericParams, |
| /*allowUnresolved=*/true), |
| pa->getOriginalName(), pa->getNestedName()); |
| invalid = true; |
| } |
| |
| return invalid; |
| } |
| |
| /// Turn a requirement right-hand side into an unresolved type. |
| static GenericSignatureBuilder::UnresolvedType asUnresolvedType( |
| GenericSignatureBuilder::RequirementRHS rhs) { |
| if (auto pa = rhs.dyn_cast<PotentialArchetype *>()) |
| return GenericSignatureBuilder::UnresolvedType(pa); |
| |
| return GenericSignatureBuilder::UnresolvedType(rhs.get<Type>()); |
| } |
| |
| void GenericSignatureBuilder::processDelayedRequirements() { |
| bool anySolved = !Impl->DelayedRequirements.empty(); |
| while (anySolved) { |
| // Steal the delayed requirements so we can reprocess them. |
| anySolved = false; |
| auto delayed = std::move(Impl->DelayedRequirements); |
| Impl->DelayedRequirements.clear(); |
| |
| // Process delayed requirements. |
| for (const auto &req : delayed) { |
| // Reprocess the delayed requirement. |
| ConstraintResult reqResult; |
| switch (req.kind) { |
| case RequirementKind::Conformance: |
| case RequirementKind::Superclass: |
| reqResult = addTypeRequirement( |
| req.lhs, asUnresolvedType(req.rhs), req.source, |
| UnresolvedHandlingKind::ReturnUnresolved); |
| break; |
| |
| case RequirementKind::Layout: |
| reqResult = addLayoutRequirement( |
| req.lhs, req.rhs.get<LayoutConstraint>(), req.source, |
| UnresolvedHandlingKind::ReturnUnresolved); |
| break; |
| |
| case RequirementKind::SameType: |
| reqResult = addSameTypeRequirement( |
| req.lhs, asUnresolvedType(req.rhs), req.source, |
| UnresolvedHandlingKind::ReturnUnresolved); |
| break; |
| } |
| |
| // Update our state based on what happened. |
| switch (reqResult) { |
| case ConstraintResult::Concrete: |
| case ConstraintResult::Conflicting: |
| anySolved = true; |
| break; |
| |
| case ConstraintResult::Resolved: |
| anySolved = true; |
| break; |
| |
| case ConstraintResult::Unresolved: |
| // Add the requirement back. |
| Impl->DelayedRequirements.push_back(req); |
| break; |
| } |
| } |
| } |
| } |
| |
| template<typename T> |
| Constraint<T> GenericSignatureBuilder::checkConstraintList( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| std::vector<Constraint<T>> &constraints, |
| llvm::function_ref<bool(const Constraint<T> &)> |
| isSuitableRepresentative, |
| llvm::function_ref<ConstraintRelation(const T&)> |
| checkConstraint, |
| Optional<Diag<unsigned, Type, T, T>> |
| conflictingDiag, |
| Diag<Type, T> redundancyDiag, |
| Diag<unsigned, Type, T> otherNoteDiag) { |
| return checkConstraintList<T, T>(genericParams, constraints, |
| isSuitableRepresentative, checkConstraint, |
| conflictingDiag, redundancyDiag, |
| otherNoteDiag, |
| [](const T& value) { return value; }, |
| /*removeSelfDerived=*/true); |
| } |
| |
| namespace { |
| /// Remove self-derived sources from the given vector of constraints. |
| /// |
| /// \returns true if any derived-via-concrete constraints were found. |
| template<typename T> |
| bool removeSelfDerived(std::vector<Constraint<T>> &constraints, |
| bool dropDerivedViaConcrete = true) { |
| bool anyDerivedViaConcrete = false; |
| // Remove self-derived constraints. |
| Optional<Constraint<T>> remainingConcrete; |
| constraints.erase( |
| std::remove_if(constraints.begin(), constraints.end(), |
| [&](const Constraint<T> &constraint) { |
| bool derivedViaConcrete; |
| if (constraint.source->isSelfDerivedSource( |
| constraint.archetype, derivedViaConcrete)) |
| return true; |
| |
| if (!derivedViaConcrete) |
| return false; |
| |
| anyDerivedViaConcrete = true; |
| |
| if (!dropDerivedViaConcrete) |
| return false; |
| |
| // Drop derived-via-concrete requirements. |
| if (!remainingConcrete) |
| remainingConcrete = constraint; |
| |
| return true; |
| }), |
| constraints.end()); |
| |
| if (constraints.empty() && remainingConcrete) |
| constraints.push_back(*remainingConcrete); |
| |
| assert(!constraints.empty() && "All constraints were self-derived!"); |
| return anyDerivedViaConcrete; |
| } |
| } // end anonymous namespace |
| |
| template<typename T, typename DiagT> |
| Constraint<T> GenericSignatureBuilder::checkConstraintList( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| std::vector<Constraint<T>> &constraints, |
| llvm::function_ref<bool(const Constraint<T> &)> |
| isSuitableRepresentative, |
| llvm::function_ref<ConstraintRelation(const T&)> |
| checkConstraint, |
| Optional<Diag<unsigned, Type, DiagT, DiagT>> |
| conflictingDiag, |
| Diag<Type, DiagT> redundancyDiag, |
| Diag<unsigned, Type, DiagT> otherNoteDiag, |
| llvm::function_ref<DiagT(const T&)> diagValue, |
| bool removeSelfDerived) { |
| assert(!constraints.empty() && "No constraints?"); |
| if (removeSelfDerived) { |
| ::removeSelfDerived(constraints); |
| } |
| |
| // Sort the constraints, so we get a deterministic ordering of diagnostics. |
| llvm::array_pod_sort(constraints.begin(), constraints.end()); |
| |
| // Find a representative constraint. |
| auto representativeConstraint = |
| findRepresentativeConstraint<T>(constraints, isSuitableRepresentative); |
| |
| // Local function to provide a note describing the representative constraint. |
| auto noteRepresentativeConstraint = [&] { |
| if (representativeConstraint->source->getLoc().isInvalid()) return; |
| |
| Diags.diagnose(representativeConstraint->source->getLoc(), |
| otherNoteDiag, |
| representativeConstraint->source->classifyDiagKind(), |
| representativeConstraint->archetype-> |
| getDependentType(genericParams, /*allowUnresolved=*/true), |
| diagValue(representativeConstraint->value)); |
| }; |
| |
| // Go through the concrete constraints looking for redundancies. |
| bool diagnosedConflictingRepresentative = false; |
| for (const auto &constraint : constraints) { |
| // Leave the representative alone. |
| if (constraint == *representativeConstraint) continue; |
| |
| switch (checkConstraint(constraint.value)) { |
| case ConstraintRelation::Unrelated: |
| continue; |
| |
| case ConstraintRelation::Conflicting: { |
| // Figure out what kind of subject we have; it will affect the |
| // diagnostic. |
| auto getSubjectType = |
| [&](PotentialArchetype *pa) -> std::pair<unsigned, Type> { |
| auto subjectType = pa->getDependentType(genericParams, true); |
| unsigned kind; |
| if (auto gp = subjectType->getAs<GenericTypeParamType>()) { |
| if (gp->getDecl() && |
| isa<ProtocolDecl>(gp->getDecl()->getDeclContext())) { |
| kind = 1; |
| subjectType = cast<ProtocolDecl>(gp->getDecl()->getDeclContext()) |
| ->getDeclaredInterfaceType(); |
| } else { |
| kind = 0; |
| } |
| } else { |
| kind = 2; |
| } |
| |
| return std::make_pair(kind, subjectType); |
| }; |
| |
| |
| // The requirement conflicts. If this constraint has a location, complain |
| // about it. |
| if (constraint.source->getLoc().isValid()) { |
| auto subject = getSubjectType(constraint.archetype); |
| Diags.diagnose(constraint.source->getLoc(), *conflictingDiag, |
| subject.first, subject.second, |
| diagValue(constraint.value), |
| diagValue(representativeConstraint->value)); |
| |
| noteRepresentativeConstraint(); |
| break; |
| } |
| |
| // If the representative itself conflicts and we haven't diagnosed it yet, |
| // do so now. |
| if (!diagnosedConflictingRepresentative && |
| representativeConstraint->source->getLoc().isValid()) { |
| auto subject = getSubjectType(representativeConstraint->archetype); |
| Diags.diagnose(representativeConstraint->source->getLoc(), |
| *conflictingDiag, |
| subject.first, subject.second, |
| diagValue(representativeConstraint->value), |
| diagValue(constraint.value)); |
| |
| diagnosedConflictingRepresentative = true; |
| break; |
| } |
| break; |
| } |
| |
| case ConstraintRelation::Redundant: |
| // If this requirement is not derived or inferred (but has a useful |
| // location) complain that it is redundant. |
| if (!constraint.source->isDerivedRequirement() && |
| !constraint.source->isInferredRequirement() && |
| constraint.source->getLoc().isValid()) { |
| Diags.diagnose(constraint.source->getLoc(), |
| redundancyDiag, |
| constraint.archetype->getDependentType( |
| genericParams, /*allowUnresolved=*/true), |
| diagValue(constraint.value)); |
| |
| noteRepresentativeConstraint(); |
| } |
| break; |
| } |
| } |
| |
| return *representativeConstraint; |
| } |
| |
| void GenericSignatureBuilder::checkConformanceConstraints( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| PotentialArchetype *pa) { |
| auto equivClass = pa->getEquivalenceClassIfPresent(); |
| if (!equivClass || equivClass->conformsTo.empty()) |
| return; |
| |
| for (auto &entry : equivClass->conformsTo) { |
| // Remove self-derived constraints. |
| assert(!entry.second.empty() && "No constraints to work with?"); |
| Optional<Constraint<ProtocolDecl *>> remainingConcrete; |
| entry.second.erase( |
| std::remove_if(entry.second.begin(), entry.second.end(), |
| [&](const Constraint<ProtocolDecl *> &constraint) { |
| bool derivedViaConcrete; |
| if (constraint.source->isSelfDerivedConformance( |
| constraint.archetype, entry.first, |
| derivedViaConcrete)) |
| return true; |
| |
| if (!derivedViaConcrete) |
| return false; |
| |
| // Drop derived-via-concrete requirements. |
| if (!remainingConcrete) |
| remainingConcrete = constraint; |
| return true; |
| }), |
| entry.second.end()); |
| |
| // If we only had concrete conformances, put one back. |
| if (entry.second.empty() && remainingConcrete) |
| entry.second.push_back(*remainingConcrete); |
| |
| assert(!entry.second.empty() && "All constraints were self-derived!"); |
| |
| checkConstraintList<ProtocolDecl *, ProtocolDecl *>( |
| genericParams, entry.second, |
| [](const Constraint<ProtocolDecl *> &constraint) { |
| return true; |
| }, |
| [&](ProtocolDecl *proto) { |
| assert(proto == entry.first && "Mixed up protocol constraints"); |
| return ConstraintRelation::Redundant; |
| }, |
| None, |
| diag::redundant_conformance_constraint, |
| diag::redundant_conformance_here, |
| [](ProtocolDecl *proto) { return proto; }, |
| /*removeSelfDerived=*/false); |
| } |
| } |
| |
| /// Perform a depth-first search from the given potential archetype through |
| /// the *implicit* same-type constraints. |
| /// |
| /// \param pa The potential archetype to visit. |
| /// \param paToComponent A mapping from each potential archetype to its |
| /// component number. |
| /// \param component The component number we're currently visiting. |
| /// |
| /// \returns the best archetype anchor seen so far. |
| static PotentialArchetype *sameTypeDFS(PotentialArchetype *pa, |
| unsigned component, |
| llvm::SmallDenseMap<PotentialArchetype *, unsigned> |
| &paToComponent) { |
| PotentialArchetype *anchor = pa; |
| |
| // If we've already visited this potential archetype, we're done. |
| if (!paToComponent.insert({pa, component}).second) return anchor; |
| |
| // Visit its adjacent potential archetypes. |
| for (const auto &constraint : pa->getSameTypeConstraints()) { |
| // Skip non-derived constraints. |
| if (!constraint.source->isDerivedRequirement()) continue; |
| |
| auto newAnchor = sameTypeDFS(constraint.value, component, paToComponent); |
| |
| // If this type is better than the anchor, use it for the anchor. |
| if (compareDependentTypes(&newAnchor, &anchor) < 0) |
| anchor = newAnchor; |
| } |
| |
| return anchor; |
| } |
| |
| namespace swift { |
| bool operator<(const DerivedSameTypeComponent &lhs, |
| const DerivedSameTypeComponent &rhs) { |
| return compareDependentTypes(&lhs.anchor, &rhs.anchor) < 0; |
| } |
| } // namespace swift |
| |
| /// Retrieve the "local" archetype anchor for the given potential archetype, |
| /// which rebuilds this potential archetype using the archetype anchors of |
| /// the parent types. |
| static PotentialArchetype *getLocalAnchor(PotentialArchetype *pa, |
| GenericSignatureBuilder &builder) { |
| auto parent = pa->getParent(); |
| if (!parent) return pa; |
| |
| auto parentAnchor = getLocalAnchor(parent, builder); |
| return parentAnchor->getNestedArchetypeAnchor(pa->getNestedName(), builder); |
| } |
| |
| /// Computes the ordered set of archetype anchors required to form a minimum |
| /// spanning tree among the connected components formed by only the derived |
| /// same-type requirements within the equivalence class of \c rep. |
| /// |
| /// The equivalence class of the given representative potential archetype |
| /// (\c rep) contains all potential archetypes that are made equivalent by |
| /// the known set of same-type constraints, which includes both directly- |
| /// stated same-type constraints (e.g., \c T.A == T.B) as well as same-type |
| /// constraints that are implied either because the names coincide (e.g., |
| /// \c T[.P1].A == T[.P2].A) or due to a requirement in a protocol. |
| /// |
| /// The equivalence class of the given representative potential archetype |
| /// (\c rep) is formed from a graph whose vertices are the potential archetypes |
| /// and whose edges are the same-type constraints. These edges include both |
| /// directly-stated same-type constraints (e.g., \c T.A == T.B) as well as |
| /// same-type constraints that are implied either because the names coincide |
| /// (e.g., \c T[.P1].A == T[.P2].A) or due to a requirement in a protocol. |
| /// The equivalence class forms a single connected component. |
| /// |
| /// Within that graph is a subgraph that includes only those edges that are |
| /// implied (and, therefore, excluding those edges that were explicitly stated). |
| /// The connected components within that subgraph describe the potential |
| /// archetypes that would be equivalence even with all of the (explicit) |
| /// same-type constraints removed. |
| /// |
| /// The entire equivalence class can be restored by introducing edges between |
| /// the connected components. This function computes a minimal, canonicalized |
| /// set of edges (same-type constraints) needed to describe the equivalence |
| /// class, which is suitable for the generation of the canonical generic |
| /// signature. |
| /// |
| /// The resulting set of "edges" is returned as a set of vertices, one per |
| /// connected component (of the subgraph). Each is the anchor for that |
| /// connected component (as determined by \c compareDependentTypes()), and the |
| /// set itself is ordered by \c compareDependentTypes(). The actual set of |
| /// canonical edges connects vertex i to vertex i+1 for i in 0..<size-1. |
| static void computeDerivedSameTypeComponents( |
| PotentialArchetype *rep, |
| llvm::SmallDenseMap<PotentialArchetype *, unsigned> &componentOf){ |
| // Perform a depth-first search to identify the components. |
| auto equivClass = rep->getOrCreateEquivalenceClass(); |
| auto &components = equivClass->derivedSameTypeComponents; |
| for (auto pa : rep->getEquivalenceClassMembers()) { |
| // If we've already seen this potential archetype, there's nothing else to |
| // do. |
| if (componentOf.count(pa) != 0) continue; |
| |
| // Find all of the potential archetypes within this connected component. |
| auto anchor = sameTypeDFS(pa, components.size(), componentOf); |
| |
| // Record the anchor. |
| components.push_back({anchor, nullptr}); |
| } |
| |
| // If there is a concrete type, figure out the best concrete type anchor |
| // per component. |
| for (const auto &concrete : equivClass->concreteTypeConstraints) { |
| // Dig out the component associated with constraint. |
| assert(componentOf.count(concrete.archetype) > 0); |
| auto &component = components[componentOf[concrete.archetype]]; |
| |
| // FIXME: Skip self-derived sources. This means our attempts to "stage" |
| // construction of self-derived sources really don't work, because we |
| // discover more information later, so we need a more on-line or |
| // iterative approach. |
| bool derivedViaConcrete; |
| if (concrete.source->isSelfDerivedSource(concrete.archetype, |
| derivedViaConcrete)) |
| continue; |
| |
| // If it has a better source than we'd seen before for this component, |
| // keep it. |
| auto &bestConcreteTypeSource = component.concreteTypeSource; |
| if (!bestConcreteTypeSource || |
| concrete.source->compare(bestConcreteTypeSource) < 0) |
| bestConcreteTypeSource = concrete.source; |
| } |
| |
| // Sort the components. |
| llvm::array_pod_sort(components.begin(), components.end()); |
| } |
| |
| namespace { |
| /// An edge in the same-type constraint graph that spans two different |
| /// components. |
| struct IntercomponentEdge { |
| unsigned source; |
| unsigned target; |
| Constraint<PotentialArchetype *> constraint; |
| |
| IntercomponentEdge(unsigned source, unsigned target, |
| const Constraint<PotentialArchetype *> &constraint) |
| : source(source), target(target), constraint(constraint) |
| { |
| assert(source != target && "Not an intercomponent edge"); |
| if (this->source > this->target) std::swap(this->source, this->target); |
| } |
| |
| friend bool operator<(const IntercomponentEdge &lhs, |
| const IntercomponentEdge &rhs) { |
| if (lhs.source != rhs.source) |
| return lhs.source < rhs.source; |
| if (lhs.target != rhs.target) |
| return lhs.target < rhs.target; |
| |
| // Prefer non-inferred requirement sources. |
| bool lhsIsInferred = lhs.constraint.source->isInferredRequirement(); |
| bool rhsIsInferred = rhs.constraint.source->isInferredRequirement(); |
| if (lhsIsInferred != rhsIsInferred) |
| return rhsIsInferred;; |
| |
| return lhs.constraint < rhs.constraint; |
| } |
| }; |
| } // end anonymous namespace |
| |
| void GenericSignatureBuilder::checkSameTypeConstraints( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| PotentialArchetype *pa) { |
| auto equivClass = pa->getEquivalenceClassIfPresent(); |
| if (!equivClass || !equivClass->derivedSameTypeComponents.empty()) |
| return; |
| |
| // Make sure that we've build the archetype anchors for each potential |
| // archetype in this equivalence class. This is important to do for *all* |
| // potential archetypes because some non-archetype anchors will nonetheless |
| // be used in the canonicalized requirements. |
| for (auto pa : pa->getEquivalenceClassMembers()) { |
| (void)getLocalAnchor(pa, *this); |
| } |
| equivClass = pa->getEquivalenceClassIfPresent(); |
| assert(equivClass && "Equivalence class disappeared?"); |
| |
| bool anyDerivedViaConcrete = false; |
| for (auto &entry : equivClass->sameTypeConstraints) { |
| auto &constraints = entry.second; |
| |
| // Remove self-derived constraints. |
| if (removeSelfDerived(constraints, /*dropDerivedViaConcrete=*/false)) |
| anyDerivedViaConcrete = true; |
| |
| // Sort the constraints, so we get a deterministic ordering of diagnostics. |
| llvm::array_pod_sort(constraints.begin(), constraints.end()); |
| } |
| |
| // Compute the components in the subgraph of the same-type constraint graph |
| // that includes only derived constraints. |
| llvm::SmallDenseMap<PotentialArchetype *, unsigned> componentOf; |
| computeDerivedSameTypeComponents(pa, componentOf); |
| |
| // Go through all of the same-type constraints, collecting all of the |
| // non-derived constraints to put them into bins: intra-component and |
| // inter-component. |
| |
| // Intra-component edges are stored per-component, so we can perform |
| // diagnostics within each component. |
| unsigned numComponents = equivClass->derivedSameTypeComponents.size(); |
| std::vector<std::vector<Constraint<PotentialArchetype *>>> |
| intracomponentEdges(numComponents, |
| std::vector<Constraint<PotentialArchetype *>>()); |
| |
| // Intercomponent edges are stored as one big list, which tracks the |
| // source/target components. |
| std::vector<IntercomponentEdge> intercomponentEdges; |
| for (auto &entry : equivClass->sameTypeConstraints) { |
| auto &constraints = entry.second; |
| for (const auto &constraint : constraints) { |
| // If the source/destination are identical, complain. |
| if (constraint.archetype == constraint.value) { |
| if (!constraint.source->isDerivedRequirement() && |
| !constraint.source->isInferredRequirement() && |
| constraint.source->getLoc().isValid()) { |
| Diags.diagnose(constraint.source->getLoc(), |
| diag::redundant_same_type_constraint, |
| constraint.archetype->getDependentType( |
| genericParams, true), |
| constraint.value->getDependentType( |
| genericParams, true)); |
| } |
| |
| continue; |
| } |
| |
| // Only keep constraints where the source is "first" in the ordering; |
| // this lets us eliminate the duplication coming from us adding back |
| // edges. |
| // FIXME: Alternatively, we could track back edges differently in the |
| // constraint. |
| if (compareDependentTypes(&constraint.archetype, &constraint.value) > 0) |
| continue; |
| |
| // Determine which component each of the source/destination fall into. |
| assert(componentOf.count(constraint.archetype) > 0 && |
| "unknown potential archetype?"); |
| unsigned firstComponent = componentOf[constraint.archetype]; |
| assert(componentOf.count(constraint.value) > 0 && |
| "unknown potential archetype?"); |
| unsigned secondComponent = componentOf[constraint.value]; |
| |
| // If both vertices are within the same component, this is an |
| // intra-component edge. Record it as such. |
| if (firstComponent == secondComponent) { |
| intracomponentEdges[firstComponent].push_back(constraint); |
| continue; |
| } |
| |
| // Otherwise, it's an intercomponent edge, which is never derived. |
| assert(!constraint.source->isDerivedRequirement() && |
| "Must not be derived"); |
| |
| // Ignore inferred requirements; we don't want to diagnose them. |
| intercomponentEdges.push_back( |
| IntercomponentEdge(firstComponent, secondComponent, constraint)); |
| } |
| } |
| |
| // If there were any derived-via-concrete constraints, drop them now before |
| // we emit other diagnostics. |
| if (anyDerivedViaConcrete) { |
| for (auto &entry : equivClass->sameTypeConstraints) { |
| auto &constraints = entry.second; |
| |
| // Remove derived-via-concrete constraints. |
| (void)removeSelfDerived(constraints); |
| anyDerivedViaConcrete = true; |
| } |
| } |
| |
| // Walk through each of the components, checking the intracomponent edges. |
| // This will diagnose any explicitly-specified requirements within a |
| // component, all of which are redundant. |
| for (auto &constraints : intracomponentEdges) { |
| if (constraints.empty()) continue; |
| |
| checkConstraintList<PotentialArchetype *, Type>( |
| genericParams, constraints, |
| [](const Constraint<PotentialArchetype *> &) { return true; }, |
| [](PotentialArchetype *) { |
| return ConstraintRelation::Redundant; |
| }, |
| None, |
| diag::redundant_same_type_constraint, |
| diag::previous_same_type_constraint, |
| [&](PotentialArchetype *pa) { |
| return pa->getDependentType(genericParams, true); |
| }, |
| /*removeSelfDerived=*/false); |
| } |
| |
| // Diagnose redundant same-type constraints across components. First, |
| // sort the edges so that edges that between the same component pairs |
| // occur next to each other. |
| llvm::array_pod_sort(intercomponentEdges.begin(), intercomponentEdges.end()); |
| |
| // Diagnose and erase any redundant edges between the same two components. |
| intercomponentEdges.erase( |
| std::unique( |
| intercomponentEdges.begin(), intercomponentEdges.end(), |
| [&](const IntercomponentEdge &lhs, |
| const IntercomponentEdge &rhs) { |
| // If either the source or target is different, we have |
| // different elements. |
| if (lhs.source != rhs.source || lhs.target != rhs.target) |
| return false; |
| |
| // We have two edges connected the same components. If both |
| // have locations, diagnose them. |
| if (lhs.constraint.source->getLoc().isInvalid() || |
| rhs.constraint.source->getLoc().isInvalid()) |
| return true; |
| |
| // If the constraint source is inferred, don't diagnose it. |
| if (lhs.constraint.source->isInferredRequirement()) |
| return true; |
| |
| Diags.diagnose(lhs.constraint.source->getLoc(), |
| diag::redundant_same_type_constraint, |
| lhs.constraint.archetype->getDependentType( |
| genericParams, true), |
| lhs.constraint.value->getDependentType( |
| genericParams, true)); |
| Diags.diagnose(rhs.constraint.source->getLoc(), |
| diag::previous_same_type_constraint, |
| rhs.constraint.source->classifyDiagKind(), |
| rhs.constraint.archetype->getDependentType( |
| genericParams, true), |
| rhs.constraint.value->getDependentType( |
| genericParams, true)); |
| return true; |
| }), |
| intercomponentEdges.end()); |
| |
| // If we have more intercomponent edges than are needed to form a spanning |
| // tree, complain about redundancies. Note that the edges we have must |
| // connect all of the components, or else we wouldn't have an equivalence |
| // class. |
| if (intercomponentEdges.size() > numComponents - 1) { |
| std::vector<bool> connected(numComponents, false); |
| const auto &firstEdge = intercomponentEdges.front(); |
| for (const auto &edge : intercomponentEdges) { |
| // If both the source and target are already connected, this edge is |
| // not part of the spanning tree. |
| if (connected[edge.source] && connected[edge.target]) { |
| if (edge.constraint.source->getLoc().isValid() && |
| !edge.constraint.source->isInferredRequirement() && |
| firstEdge.constraint.source->getLoc().isValid()) { |
| Diags.diagnose(edge.constraint.source->getLoc(), |
| diag::redundant_same_type_constraint, |
| edge.constraint.archetype->getDependentType( |
| genericParams, true), |
| edge.constraint.value->getDependentType( |
| genericParams, true)); |
| |
| Diags.diagnose(firstEdge.constraint.source->getLoc(), |
| diag::previous_same_type_constraint, |
| firstEdge.constraint.source->classifyDiagKind(), |
| firstEdge.constraint.archetype->getDependentType( |
| genericParams, true), |
| firstEdge.constraint.value->getDependentType( |
| genericParams, true)); |
| } |
| |
| continue; |
| } |
| |
| // Put the source and target into the spanning tree. |
| connected[edge.source] = true; |
| connected[edge.target] = true; |
| } |
| } |
| } |
| |
| void GenericSignatureBuilder::checkConcreteTypeConstraints( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| PotentialArchetype *representative) { |
| auto equivClass = representative->getOrCreateEquivalenceClass(); |
| assert(equivClass->concreteType && "No concrete type to check"); |
| |
| checkConstraintList<Type>( |
| genericParams, equivClass->concreteTypeConstraints, |
| [](const ConcreteConstraint &constraint) { |
| return true; |
| }, |
| [&](Type concreteType) { |
| // If the concrete type is equivalent, the constraint is redundant. |
| // FIXME: Should check this constraint after substituting in the |
| // archetype anchors for each dependent type. |
| if (concreteType->isEqual(equivClass->concreteType)) |
| return ConstraintRelation::Redundant; |
| |
| // Call this unrelated. |
| return ConstraintRelation::Unrelated; |
| }, |
| None, |
| diag::redundant_same_type_to_concrete, |
| diag::same_type_redundancy_here); |
| } |
| |
| void GenericSignatureBuilder::checkSuperclassConstraints( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| PotentialArchetype *representative) { |
| auto equivClass = representative->getOrCreateEquivalenceClass(); |
| assert(equivClass->superclass && "No superclass constraint?"); |
| |
| // FIXME: We should be substituting in the canonical type in context so |
| // we can resolve superclass requirements, e.g., if you had: |
| // |
| // class Foo<T> |
| // class Bar: Foo<Int> |
| // |
| // func foo<T, U where U: Bar, U: Foo<T>>(...) { ... } |
| // |
| // then the second `U: Foo<T>` constraint introduces a `T == Int` |
| // constraint, and we will need to perform that substitution for this final |
| // check. |
| |
| auto representativeConstraint = |
| checkConstraintList<Type>( |
| genericParams, equivClass->superclassConstraints, |
| [&](const ConcreteConstraint &constraint) { |
| return constraint.value->isEqual(equivClass->superclass); |
| }, |
| [&](Type superclass) { |
| // If this class is a superclass of the "best" |
| if (superclass->isExactSuperclassOf(equivClass->superclass)) |
| return ConstraintRelation::Redundant; |
| |
| // Otherwise, it conflicts. |
| return ConstraintRelation::Conflicting; |
| }, |
| diag::requires_superclass_conflict, |
| diag::redundant_superclass_constraint, |
| diag::superclass_redundancy_here); |
| |
| // If we have a concrete type, check it. |
| // FIXME: Substitute into the concrete type. |
| if (equivClass->concreteType) { |
| // Make sure the concrete type fulfills the superclass requirement. |
| if (!equivClass->superclass->isExactSuperclassOf(equivClass->concreteType)) { |
| if (auto existing = equivClass->findAnyConcreteConstraintAsWritten( |
| representativeConstraint.archetype)) { |
| Diags.diagnose(existing->source->getLoc(), diag::type_does_not_inherit, |
| existing->archetype->getDependentType( |
| genericParams, |
| /*allowUnresolved=*/true), |
| existing->value, equivClass->superclass); |
| |
| // FIXME: Note the representative constraint. |
| } else if (representativeConstraint.source->getLoc().isValid()) { |
| Diags.diagnose(representativeConstraint.source->getLoc(), |
| diag::type_does_not_inherit, |
| representativeConstraint.archetype->getDependentType( |
| genericParams, |
| /*allowUnresolved=*/true), |
| equivClass->concreteType, equivClass->superclass); |
| } |
| } else if (representativeConstraint.source->getLoc().isValid()) { |
| // It does fulfill the requirement; diagnose the redundancy. |
| Diags.diagnose(representativeConstraint.source->getLoc(), |
| diag::redundant_superclass_constraint, |
| representativeConstraint.archetype->getDependentType( |
| genericParams, |
| /*allowUnresolved=*/true), |
| representativeConstraint.value); |
| |
| if (auto existing = equivClass->findAnyConcreteConstraintAsWritten( |
| representativeConstraint.archetype)) { |
| Diags.diagnose(existing->source->getLoc(), |
| diag::same_type_redundancy_here, |
| existing->source->classifyDiagKind(), |
| existing->archetype->getDependentType( |
| genericParams, |
| /*allowUnresolved=*/true), |
| existing->value); |
| } |
| } |
| } |
| } |
| |
| void GenericSignatureBuilder::checkLayoutConstraints( |
| ArrayRef<GenericTypeParamType *> genericParams, |
| PotentialArchetype *pa) { |
| auto equivClass = pa->getEquivalenceClassIfPresent(); |
| if (!equivClass || !equivClass->layout) return; |
| |
| checkConstraintList<LayoutConstraint>( |
| genericParams, equivClass->layoutConstraints, |
| [&](const Constraint<LayoutConstraint> &constraint) { |
| return constraint.value == equivClass->layout; |
| }, |
| [&](LayoutConstraint layout) { |
| // If the layout constraints are mergable, i.e. compatible, |
| // it is a redundancy. |
| if (layout.merge(equivClass->layout)->isKnownLayout()) |
| return ConstraintRelation::Redundant; |
| |
| return ConstraintRelation::Conflicting; |
| }, |
| diag::conflicting_layout_constraints, |
| diag::redundant_layout_constraint, |
| diag::previous_layout_constraint); |
| } |
| |
| template<typename F> |
| void GenericSignatureBuilder::visitPotentialArchetypes(F f) { |
| // Stack containing all of the potential archetypes to visit. |
| SmallVector<PotentialArchetype *, 4> stack; |
| llvm::SmallPtrSet<PotentialArchetype *, 4> visited; |
| |
| // Add top-level potential archetypes to the stack. |
| for (const auto pa : Impl->PotentialArchetypes) { |
| if (visited.insert(pa).second) |
| stack.push_back(pa); |
| } |
| |
| // Visit all of the potential archetypes. |
| while (!stack.empty()) { |
| PotentialArchetype *pa = stack.back(); |
| stack.pop_back(); |
| f(pa); |
| |
| // Visit the archetype anchor. |
| if (auto anchor = pa->getArchetypeAnchor(*this)) { |
| if (visited.insert(anchor).second) { |
| stack.push_back(anchor); |
| } |
| } |
| |
| // Visit everything else in this equivalence class. |
| for (auto equivPA : pa->getEquivalenceClassMembers()) { |
| if (visited.insert(equivPA).second) { |
| stack.push_back(equivPA); |
| } |
| } |
| |
| // Visit nested potential archetypes. |
| for (const auto &nested : pa->getNestedTypes()) { |
| for (auto nestedPA : nested.second) { |
| if (visited.insert(nestedPA).second) { |
| stack.push_back(nestedPA); |
| } |
| } |
| } |
| } |
| } |
| |
| namespace { |
| /// Retrieve the best requirement source from a set of constraints. |
| template<typename T> |
| const RequirementSource *getBestConstraintSource( |
| ArrayRef<Constraint<T>> constraints) { |
| auto bestSource = constraints.front().source; |
| for (const auto &constraint : constraints) { |
| if (constraint.source->compare(bestSource) < 0) |
| bestSource = constraint.source; |
| } |
| return bestSource; |
| } |
| } // end anonymous namespace |
| |
| void GenericSignatureBuilder::enumerateRequirements(llvm::function_ref< |
| void (RequirementKind kind, |
| PotentialArchetype *archetype, |
| GenericSignatureBuilder::RequirementRHS constraint, |
| const RequirementSource *source)> f) { |
| // Collect all archetypes. |
| SmallVector<PotentialArchetype *, 8> archetypes; |
| visitPotentialArchetypes([&](PotentialArchetype *archetype) { |
| archetypes.push_back(archetype); |
| }); |
| |
| // Remove any invalid potential archetypes or archetypes whose parents are |
| // concrete; they have no requirements. |
| archetypes.erase( |
| std::remove_if(archetypes.begin(), archetypes.end(), |
| [&](PotentialArchetype *archetype) -> bool { |
| // Invalid archetypes are never representatives in well-formed or |
| // corrected signature, so we don't need to visit them. |
| if (archetype->isInvalid()) |
| return true; |
| |
| // Keep it. |
| return false; |
| }), |
| archetypes.end()); |
| |
| // Sort the archetypes in canonical order. |
| llvm::array_pod_sort(archetypes.begin(), archetypes.end(), |
| compareDependentTypes); |
| |
| for (auto *archetype : archetypes) { |
| // Check whether this archetype is one of the anchors within its |
| // connected component. If so, we may need to emit a same-type constraint. |
| // |
| // FIXME: O(n) in the number of implied connected components within the |
| // equivalence class. The equivalence class should be small, but... |
| auto rep = archetype->getRepresentative(); |
| auto equivClass = rep->getOrCreateEquivalenceClass(); |
| |
| // If we didn't compute the derived same-type components yet, do so now. |
| if (equivClass->derivedSameTypeComponents.empty()) |
| checkSameTypeConstraints(Impl->GenericParams, rep); |
| |
| assert(!equivClass->derivedSameTypeComponents.empty() && |
| "Didn't compute derived same-type components?"); |
| auto knownAnchor = |
| std::find_if(equivClass->derivedSameTypeComponents.begin(), |
| equivClass->derivedSameTypeComponents.end(), |
| [&](const DerivedSameTypeComponent &component) { |
| return component.anchor == archetype; |
| }); |
| std::function<void()> deferredSameTypeRequirement; |
| |
| if (knownAnchor != equivClass->derivedSameTypeComponents.end()) { |
| // If this equivalence class is bound to a concrete type, equate the |
| // anchor with a concrete type. |
| if (Type concreteType = rep->getConcreteType()) { |
| // If the parent of this anchor is also a concrete type, don't |
| // create a requirement. |
| if (!archetype->isGenericParam() && |
| archetype->getParent()->isConcreteType()) |
| continue; |
| |
| auto source = |
| knownAnchor->concreteTypeSource |
| ? knownAnchor->concreteTypeSource |
| : RequirementSource::forAbstract(archetype); |
| |
| f(RequirementKind::SameType, archetype, concreteType, source); |
| continue; |
| } |
| |
| // If we're at the last anchor in the component, do nothing; |
| auto nextAnchor = knownAnchor; |
| ++nextAnchor; |
| if (nextAnchor != equivClass->derivedSameTypeComponents.end()) { |
| // Form a same-type constraint from this anchor within the component |
| // to the next. |
| // FIXME: Distinguish between explicit and inferred here? |
| auto otherPA = nextAnchor->anchor; |
| deferredSameTypeRequirement = [&f, archetype, otherPA] { |
| f(RequirementKind::SameType, archetype, otherPA, |
| RequirementSource::forAbstract(archetype)); |
| }; |
| } |
| } |
| SWIFT_DEFER { |
| if (deferredSameTypeRequirement) deferredSameTypeRequirement(); |
| }; |
| |
| // If this is not the archetype anchor, we're done. |
| if (archetype != archetype->getArchetypeAnchor(*this)) |
| continue; |
| |
| // If we have a superclass, produce a superclass requirement |
| if (equivClass->superclass) { |
| f(RequirementKind::Superclass, archetype, equivClass->superclass, |
| getBestConstraintSource<Type>(equivClass->superclassConstraints)); |
| } |
| |
| // If we have a layout constraint, produce a layout requirement. |
| if (equivClass->layout) { |
| f(RequirementKind::Layout, archetype, equivClass->layout, |
| getBestConstraintSource<LayoutConstraint>( |
| equivClass->layoutConstraints)); |
| } |
| |
| // Enumerate conformance requirements. |
| SmallVector<ProtocolDecl *, 4> protocols; |
| DenseMap<ProtocolDecl *, const RequirementSource *> protocolSources; |
| if (equivClass) { |
| for (const auto &conforms : equivClass->conformsTo) { |
| protocols.push_back(conforms.first); |
| assert(protocolSources.count(conforms.first) == 0 && |
| "redundant protocol requirement?"); |
| |
| protocolSources.insert( |
| {conforms.first, |
| getBestConstraintSource<ProtocolDecl *>(conforms.second)}); |
| } |
| } |
| |
| // Sort the protocols in canonical order. |
| llvm::array_pod_sort(protocols.begin(), protocols.end(), |
| ProtocolType::compareProtocols); |
| |
| // Enumerate the conformance requirements. |
| for (auto proto : protocols) { |
| assert(protocolSources.count(proto) == 1 && "Missing conformance?"); |
| f(RequirementKind::Conformance, archetype, |
| proto->getDeclaredInterfaceType(), |
| protocolSources.find(proto)->second); |
| } |
| }; |
| } |
| |
| void GenericSignatureBuilder::dump() { |
| dump(llvm::errs()); |
| } |
| |
| void GenericSignatureBuilder::dump(llvm::raw_ostream &out) { |
| out << "Requirements:"; |
| enumerateRequirements([&](RequirementKind kind, |
| PotentialArchetype *archetype, |
| GenericSignatureBuilder::RequirementRHS constraint, |
| const RequirementSource *source) { |
| switch (kind) { |
| case RequirementKind::Conformance: |
| case RequirementKind::Superclass: |
| out << "\n "; |
| out << archetype->getDebugName() << " : " |
| << constraint.get<Type>().getString() << " ["; |
| source->print(out, &Context.SourceMgr); |
| out << "]"; |
| break; |
| case RequirementKind::Layout: |
| out << "\n "; |
| out << archetype->getDebugName() << " : " |
| << constraint.get<LayoutConstraint>().getString() << " ["; |
| source->print(out, &Context.SourceMgr); |
| out << "]"; |
| break; |
| case RequirementKind::SameType: |
| out << "\n "; |
| out << archetype->getDebugName() << " == " ; |
| if (auto secondType = constraint.dyn_cast<Type>()) { |
| out << secondType.getString(); |
| } else { |
| out << constraint.get<PotentialArchetype *>()->getDebugName(); |
| } |
| out << " ["; |
| source->print(out, &Context.SourceMgr); |
| out << "]"; |
| break; |
| } |
| }); |
| out << "\n"; |
| |
| out << "Potential archetypes:\n"; |
| for (auto pa : Impl->PotentialArchetypes) { |
| pa->dump(out, &Context.SourceMgr, 2); |
| } |
| out << "\n"; |
| } |
| |
| void GenericSignatureBuilder::addGenericSignature(GenericSignature *sig) { |
| if (!sig) return; |
| |
| for (auto param : sig->getGenericParams()) |
| addGenericParameter(param); |
| |
| // Add the requirements, queuing up same-type requirements until the end. |
| // FIXME: Queuing up same-type requirements is a hack that works around |
| // problems when referencing associated types. These issues primarily |
| // occur when building canonical generic environments |
| SmallVector<Requirement, 4> sameTypeRequirements; |
| for (auto &reqt : sig->getRequirements()) { |
| if (reqt.getKind() == RequirementKind::SameType) |
| sameTypeRequirements.push_back(reqt); |
| else |
| addRequirement(reqt, FloatingRequirementSource::forAbstract(), nullptr); |
| } |
| |
| // Handle same-type requirements. |
| for (auto &reqt : sameTypeRequirements) { |
| addRequirement(reqt, FloatingRequirementSource::forAbstract(), nullptr); |
| } |
| } |
| |
| /// Collect the set of requirements placed on the given generic parameters and |
| /// their associated types. |
| static void collectRequirements(GenericSignatureBuilder &builder, |
| ArrayRef<GenericTypeParamType *> params, |
| SmallVectorImpl<Requirement> &requirements) { |
| builder.enumerateRequirements([&](RequirementKind kind, |
| GenericSignatureBuilder::PotentialArchetype *archetype, |
| GenericSignatureBuilder::RequirementRHS type, |
| const RequirementSource *source) { |
| // Filter out derived requirements... except for concrete-type requirements |
| // on generic parameters. The exception is due to the canonicalization of |
| // generic signatures, which never eliminates generic parameters even when |
| // they have been mapped to a concrete type. |
| if (source->isDerivedRequirement() && |
| !(kind == RequirementKind::SameType && |
| archetype->isGenericParam() && |
| type.is<Type>())) |
| return; |
| |
| auto depTy = archetype->getDependentType(params, |
| /*allowUnresolved=*/false); |
| |
| if (depTy->hasError()) |
| return; |
| |
| Type repTy; |
| if (auto concreteTy = type.dyn_cast<Type>()) { |
| // Maybe we were equated to a concrete type... |
| repTy = concreteTy; |
| |
| // Drop requirements involving concrete types containing |
| // unresolved associated types. |
| if (repTy.findIf([](Type t) -> bool { |
| if (auto *depTy = dyn_cast<DependentMemberType>(t.getPointer())) |
| if (depTy->getAssocType() == nullptr) |
| return true; |
| return false; |
| })) { |
| return; |
| } |
| } else if (auto layoutConstraint = type.dyn_cast<LayoutConstraint>()) { |
| requirements.push_back(Requirement(kind, depTy, layoutConstraint)); |
| return; |
| } else { |
| // ...or to a dependent type. |
| repTy = type.get<GenericSignatureBuilder::PotentialArchetype *>() |
| ->getDependentType(params, /*allowUnresolved=*/false); |
| } |
| |
| if (repTy->hasError()) |
| return; |
| |
| requirements.push_back(Requirement(kind, depTy, repTy)); |
| }); |
| } |
| |
| GenericSignature *GenericSignatureBuilder::getGenericSignature() { |
| assert(Impl->finalized && "Must finalize builder first"); |
| |
| // Collect the requirements placed on the generic parameter types. |
| SmallVector<Requirement, 4> requirements; |
| collectRequirements(*this, Impl->GenericParams, requirements); |
| |
| auto sig = GenericSignature::get(Impl->GenericParams, requirements); |
| return sig; |
| } |