| //===--- GenericSignature.cpp - Generic Signature AST ---------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See http://swift.org/LICENSE.txt for license information |
| // See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements the GenericSignature class. |
| // |
| //===----------------------------------------------------------------------===// |
| #include "swift/AST/GenericSignature.h" |
| #include "swift/AST/ASTContext.h" |
| #include "swift/AST/Decl.h" |
| #include "swift/AST/Module.h" |
| #include "swift/AST/Types.h" |
| using namespace swift; |
| |
| GenericSignature::GenericSignature(ArrayRef<GenericTypeParamType *> params, |
| ArrayRef<Requirement> requirements, |
| bool isKnownCanonical) |
| : NumGenericParams(params.size()), NumRequirements(requirements.size()), |
| CanonicalSignatureOrASTContext() |
| { |
| auto paramsBuffer = getGenericParamsBuffer(); |
| for (unsigned i = 0; i < NumGenericParams; ++i) { |
| paramsBuffer[i] = params[i]; |
| } |
| |
| auto reqtsBuffer = getRequirementsBuffer(); |
| for (unsigned i = 0; i < NumRequirements; ++i) { |
| reqtsBuffer[i] = requirements[i]; |
| } |
| |
| if (isKnownCanonical) |
| CanonicalSignatureOrASTContext = &getASTContext(params, requirements); |
| } |
| |
| ArrayRef<GenericTypeParamType *> |
| GenericSignature::getInnermostGenericParams() const { |
| auto params = getGenericParams(); |
| |
| // Find the point at which the depth changes. |
| unsigned depth = params.back()->getDepth(); |
| for (unsigned n = params.size(); n > 0; --n) { |
| if (params[n-1]->getDepth() != depth) { |
| return params.slice(n); |
| } |
| } |
| |
| // All parameters are at the same depth. |
| return params; |
| } |
| |
| ASTContext &GenericSignature::getASTContext( |
| ArrayRef<swift::GenericTypeParamType *> params, |
| ArrayRef<swift::Requirement> requirements) { |
| // The params and requirements cannot both be empty. |
| if (!params.empty()) |
| return params.front()->getASTContext(); |
| else |
| return requirements.front().getFirstType()->getASTContext(); |
| } |
| |
| ArchetypeBuilder *GenericSignature::getArchetypeBuilder(ModuleDecl &mod) { |
| // The archetype builder is associated with the canonical signature. |
| if (!isCanonical()) |
| return getCanonicalSignature()->getArchetypeBuilder(mod); |
| |
| // Archetype builders are stored on the ASTContext. |
| return getASTContext().getOrCreateArchetypeBuilder(CanGenericSignature(this), |
| &mod); |
| } |
| |
| bool GenericSignature::isCanonical() const { |
| if (CanonicalSignatureOrASTContext.is<ASTContext*>()) return true; |
| |
| return getCanonicalSignature() == this; |
| } |
| |
| CanGenericSignature GenericSignature::getCanonical( |
| ArrayRef<GenericTypeParamType *> params, |
| ArrayRef<Requirement> requirements) { |
| // Canonicalize the parameters and requirements. |
| SmallVector<GenericTypeParamType*, 8> canonicalParams; |
| canonicalParams.reserve(params.size()); |
| for (auto param : params) { |
| canonicalParams.push_back(cast<GenericTypeParamType>(param->getCanonicalType())); |
| } |
| |
| SmallVector<Requirement, 8> canonicalRequirements; |
| canonicalRequirements.reserve(requirements.size()); |
| for (auto &reqt : requirements) { |
| canonicalRequirements.push_back(Requirement(reqt.getKind(), |
| reqt.getFirstType()->getCanonicalType(), |
| reqt.getSecondType().getCanonicalTypeOrNull())); |
| } |
| auto canSig = get(canonicalParams, canonicalRequirements, |
| /*isKnownCanonical=*/true); |
| return CanGenericSignature(canSig); |
| } |
| |
| CanGenericSignature |
| GenericSignature::getCanonicalSignature() const { |
| // If we haven't computed the canonical signature yet, do so now. |
| if (CanonicalSignatureOrASTContext.isNull()) { |
| // Compute the canonical signature. |
| CanGenericSignature canSig = getCanonical(getGenericParams(), |
| getRequirements()); |
| |
| // Record either the canonical signature or an indication that |
| // this is the canonical signature. |
| if (canSig != this) |
| CanonicalSignatureOrASTContext = canSig; |
| else |
| CanonicalSignatureOrASTContext = &getGenericParams()[0]->getASTContext(); |
| |
| // Return the canonical signature. |
| return canSig; |
| } |
| |
| // A stored ASTContext indicates that this is the canonical |
| // signature. |
| if (CanonicalSignatureOrASTContext.is<ASTContext*>()) |
| // TODO: CanGenericSignature should be const-correct. |
| return CanGenericSignature(const_cast<GenericSignature*>(this)); |
| |
| // Otherwise, return the stored canonical signature. |
| return CanGenericSignature( |
| CanonicalSignatureOrASTContext.get<GenericSignature*>()); |
| } |
| |
| /// Canonical ordering for dependent types in generic signatures. |
| static int compareDependentTypes(const CanType *pa, const CanType *pb) { |
| auto a = *pa, b = *pb; |
| |
| // Fast-path check for equality. |
| if (a == b) |
| return 0; |
| |
| // Ordering is as follows: |
| // - Generic params |
| if (auto gpa = dyn_cast<GenericTypeParamType>(a)) { |
| if (auto gpb = dyn_cast<GenericTypeParamType>(b)) { |
| // - by depth, so t_0_n < t_1_m |
| if (int compareDepth = gpa->getDepth() - gpb->getDepth()) |
| return compareDepth; |
| // - by index, so t_n_0 < t_n_1 |
| return gpa->getIndex() - gpb->getIndex(); |
| } |
| return -1; |
| } |
| |
| // - Dependent members |
| if (auto dma = dyn_cast<DependentMemberType>(a)) { |
| if (isa<GenericTypeParamType>(b)) |
| return +1; |
| if (auto dmb = dyn_cast<DependentMemberType>(b)) { |
| // - by base, so t_0_n.`P.T` < t_1_m.`P.T` |
| auto abase = dma.getBase(); |
| auto bbase = dmb.getBase(); |
| if (int compareBases = compareDependentTypes(&abase, &bbase)) |
| return compareBases; |
| |
| // - by protocol, so t_n_m.`P.T` < t_n_m.`Q.T` (given P < Q) |
| auto protoa = dma->getAssocType()->getProtocol(); |
| auto protob = dmb->getAssocType()->getProtocol(); |
| if (int compareProtocols |
| = ProtocolType::compareProtocols(&protoa, &protob)) |
| return compareProtocols; |
| |
| // - by name, so t_n_m.`P.T` < t_n_m.`P.U` |
| return dma->getAssocType()->getName().str().compare( |
| dmb->getAssocType()->getName().str()); |
| } |
| return -1; |
| } |
| |
| // - Other types. |
| // |
| // There should only ever be one of these in a set of constraints related to |
| // a dependent type, so the ordering among other types does not matter. |
| if (isa<GenericTypeParamType>(b) || isa<DependentMemberType>(b)) |
| return +1; |
| return 0; |
| } |
| |
| CanGenericSignature |
| GenericSignature::getCanonicalManglingSignature(ModuleDecl &M) const { |
| // Start from the elementwise-canonical signature. |
| auto canonical = getCanonicalSignature(); |
| auto &Context = canonical->getASTContext(); |
| |
| // See if we cached the mangling signature. |
| auto cached = Context.ManglingSignatures.find({canonical, &M}); |
| if (cached != Context.ManglingSignatures.end()) { |
| return cached->second; |
| } |
| |
| // Otherwise, we need to compute it. |
| // Dump the generic signature into an ArchetypeBuilder that will figure out |
| // the minimal set of requirements. |
| std::unique_ptr<ArchetypeBuilder> builder(new ArchetypeBuilder(M, |
| Context.Diags)); |
| |
| builder->addGenericSignature(canonical, /*adoptArchetypes*/ false, |
| /*treatRequirementsAsExplicit*/ true); |
| |
| // Sort out the requirements. |
| struct DependentConstraints { |
| CanType baseClass; |
| SmallVector<CanType, 2> protocols; |
| }; |
| |
| SmallVector<CanType, 2> depTypes; |
| llvm::DenseMap<CanType, DependentConstraints> constraints; |
| llvm::DenseMap<CanType, SmallVector<CanType, 2>> sameTypes; |
| |
| builder->enumerateRequirements([&](RequirementKind kind, |
| ArchetypeBuilder::PotentialArchetype *archetype, |
| llvm::PointerUnion<Type, ArchetypeBuilder::PotentialArchetype *> type, |
| RequirementSource source) { |
| CanType depTy |
| = archetype->getDependentType(*builder, false)->getCanonicalType(); |
| |
| // Filter out redundant requirements. |
| switch (source.getKind()) { |
| case RequirementSource::Explicit: |
| // The requirement was explicit and required, keep it. |
| break; |
| |
| case RequirementSource::Protocol: |
| // Keep witness markers. |
| if (kind == RequirementKind::WitnessMarker) |
| break; |
| return; |
| |
| case RequirementSource::Redundant: |
| case RequirementSource::Inferred: |
| // The requirement was inferred or redundant, drop it. |
| return; |
| |
| case RequirementSource::OuterScope: |
| llvm_unreachable("shouldn't have an outer scope!"); |
| } |
| |
| switch (kind) { |
| case RequirementKind::WitnessMarker: { |
| // Introduce the dependent type into the constraint set, to ensure we |
| // have a record for every dependent type. |
| depTypes.push_back(depTy); |
| return; |
| } |
| |
| case RequirementKind::Conformance: { |
| assert(std::find(depTypes.begin(), depTypes.end(), |
| depTy) != depTypes.end() |
| && "didn't see witness marker first?"); |
| // Organize conformance constraints, sifting out the base class |
| // requirement. |
| auto &depConstraints = constraints[depTy]; |
| |
| auto constraintType = type.get<Type>()->getCanonicalType(); |
| if (constraintType->isExistentialType()) { |
| depConstraints.protocols.push_back(constraintType); |
| } else { |
| assert(depConstraints.baseClass.isNull() |
| && "multiple base class constraints?!"); |
| depConstraints.baseClass = constraintType; |
| } |
| |
| return; |
| } |
| |
| case RequirementKind::SameType: |
| // Collect the same-type constraints by their representative. |
| CanType repTy; |
| if (auto concreteTy = type.dyn_cast<Type>()) { |
| // Maybe we were equated to a concrete type... |
| repTy = concreteTy->getCanonicalType(); |
| } else { |
| // ...or to a representative dependent type that was in turn equated |
| // to a concrete type. |
| auto representative |
| = type.get<ArchetypeBuilder::PotentialArchetype *>(); |
| |
| if (representative->isConcreteType()) |
| repTy = representative->getConcreteType()->getCanonicalType(); |
| else |
| repTy = representative->getDependentType(*builder, false) |
| ->getCanonicalType(); |
| } |
| |
| sameTypes[repTy].push_back(depTy); |
| return; |
| } |
| }); |
| |
| // Order the dependent types canonically. |
| llvm::array_pod_sort(depTypes.begin(), depTypes.end(), compareDependentTypes); |
| |
| // Build a new set of minimized requirements. |
| // Emit the conformance constraints. |
| SmallVector<Requirement, 4> minimalRequirements; |
| for (auto depTy : depTypes) { |
| minimalRequirements.push_back(Requirement(RequirementKind::WitnessMarker, |
| depTy, Type())); |
| |
| auto foundConstraints = constraints.find(depTy); |
| if (foundConstraints != constraints.end()) { |
| const auto &depConstraints = foundConstraints->second; |
| |
| if (depConstraints.baseClass) |
| minimalRequirements.push_back(Requirement(RequirementKind::Conformance, |
| depTy, |
| depConstraints.baseClass)); |
| |
| for (auto protocol : depConstraints.protocols) |
| minimalRequirements.push_back(Requirement(RequirementKind::Conformance, |
| depTy, protocol)); |
| } |
| } |
| |
| // Collect the same type constraints. |
| unsigned sameTypeBegin = minimalRequirements.size(); |
| |
| for (auto &group : sameTypes) { |
| // Sort the types in the set. |
| auto types = std::move(group.second); |
| types.push_back(group.first); |
| llvm::array_pod_sort(types.begin(), types.end(), compareDependentTypes); |
| |
| // Form constraints with the greater type on the right (which will be the |
| // concrete type, if one). |
| auto rhsType = types.pop_back_val(); |
| for (auto lhsType : types) |
| minimalRequirements.push_back(Requirement(RequirementKind::SameType, |
| lhsType, rhsType)); |
| } |
| |
| // Sort the same-types by LHS, then by RHS. |
| std::sort(minimalRequirements.begin() + sameTypeBegin, minimalRequirements.end(), |
| [](const Requirement &a, const Requirement &b) -> bool { |
| assert(a.getKind() == b.getKind() |
| && a.getKind() == RequirementKind::SameType |
| && "not same type constraints"); |
| CanType aLHS(a.getFirstType()), bLHS(b.getFirstType()); |
| if (int compareLHS = compareDependentTypes(&aLHS, &bLHS)) |
| return compareLHS < 0; |
| CanType aRHS(a.getSecondType()), bRHS(b.getSecondType()); |
| return compareDependentTypes(&aRHS, &bRHS); |
| }); |
| |
| // Build the minimized signature. |
| auto manglingSig = GenericSignature::get(canonical->getGenericParams(), |
| minimalRequirements, |
| /*isKnownCanonical=*/true); |
| |
| CanGenericSignature canSig(manglingSig); |
| |
| // Cache the result. |
| Context.ManglingSignatures.insert({{canonical, &M}, canSig}); |
| Context.setArchetypeBuilder(canSig, &M, std::move(builder)); |
| |
| return canSig; |
| } |
| |
| ASTContext &GenericSignature::getASTContext() const { |
| // Canonical signatures store the ASTContext directly. |
| if (auto ctx = CanonicalSignatureOrASTContext.dyn_cast<ASTContext *>()) |
| return *ctx; |
| |
| // For everything else, just get it from the generic parameter. |
| return getASTContext(getGenericParams(), getRequirements()); |
| } |
| |
| TypeSubstitutionMap |
| GenericSignature::getSubstitutionMap(ArrayRef<Substitution> args) const { |
| TypeSubstitutionMap subs; |
| |
| // An empty parameter list gives an empty map. |
| if (getGenericParams().empty()) { |
| assert(args.empty() && "substitutions but no generic params?!"); |
| return subs; |
| } |
| |
| // Seed the type map with pre-existing substitutions. |
| for (auto sub : args) { |
| subs[sub.getArchetype()] = sub.getReplacement(); |
| } |
| |
| for (auto depTy : getAllDependentTypes()) { |
| auto replacement = args.front().getReplacement(); |
| args = args.slice(1); |
| |
| if (auto subTy = depTy->getAs<SubstitutableType>()) { |
| subs[subTy] = replacement; |
| } |
| else if (auto dTy = depTy->getAs<DependentMemberType>()) { |
| subs[dTy] = replacement; |
| } |
| } |
| |
| assert(args.empty() && "did not use all substitutions?!"); |
| return subs; |
| } |
| |
| bool GenericSignature::requiresClass(Type type, ModuleDecl &mod) { |
| if (!type->isTypeParameter()) return false; |
| |
| auto &builder = *getArchetypeBuilder(mod); |
| auto pa = builder.resolveArchetype(type); |
| if (!pa) return false; |
| |
| pa = pa->getRepresentative(); |
| |
| // If this type was mapped to a concrete type, then there is no |
| // requirement. |
| if (pa->isConcreteType()) return false; |
| |
| // If there is a superclass bound, then obviously it must be a class. |
| if (pa->getSuperclass()) return true; |
| |
| // If any of the protocols are class-bound, then it must be a class. |
| for (auto proto : pa->getConformsTo()) { |
| if (proto.first->requiresClass()) return true; |
| } |
| |
| return false; |
| } |
| |
| /// Determine the superclass bound on the given dependent type. |
| Type GenericSignature::getSuperclassBound(Type type, ModuleDecl &mod) { |
| if (!type->isTypeParameter()) return nullptr; |
| |
| auto &builder = *getArchetypeBuilder(mod); |
| auto pa = builder.resolveArchetype(type); |
| if (!pa) return nullptr; |
| |
| pa = pa->getRepresentative(); |
| |
| // If this type was mapped to a concrete type, then there is no |
| // requirement. |
| if (pa->isConcreteType()) return nullptr; |
| |
| // Retrieve the superclass bound. |
| return pa->getSuperclass(); |
| } |
| |
| /// Determine the set of protocols to which the given dependent type |
| /// must conform. |
| SmallVector<ProtocolDecl *, 2> GenericSignature::getConformsTo(Type type, |
| ModuleDecl &mod) { |
| if (!type->isTypeParameter()) return { }; |
| |
| auto &builder = *getArchetypeBuilder(mod); |
| auto pa = builder.resolveArchetype(type); |
| if (!pa) return { }; |
| |
| pa = pa->getRepresentative(); |
| |
| // If this type was mapped to a concrete type, then there are no |
| // requirements. |
| if (pa->isConcreteType()) return { }; |
| |
| // Retrieve the protocols to which this type conforms. |
| SmallVector<ProtocolDecl *, 2> result; |
| for (auto proto : pa->getConformsTo()) |
| result.push_back(proto.first); |
| |
| // Canonicalize the resulting set of protocols. |
| ProtocolType::canonicalizeProtocols(result); |
| |
| return result; |
| } |
| |
| /// Determine whether the given dependent type is equal to a concrete type. |
| bool GenericSignature::isConcreteType(Type type, ModuleDecl &mod) { |
| if (!type->isTypeParameter()) return true; |
| |
| auto &builder = *getArchetypeBuilder(mod); |
| auto pa = builder.resolveArchetype(type); |
| if (!pa) return true; |
| |
| pa = pa->getRepresentative(); |
| return pa->isConcreteType(); |
| } |