| //===--- TypeCheckGeneric.cpp - Generics ----------------------------------===// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements support for generics. |
| // |
| //===----------------------------------------------------------------------===// |
| #include "TypeChecker.h" |
| #include "TypeCheckType.h" |
| #include "swift/AST/GenericEnvironment.h" |
| #include "swift/AST/GenericSignatureBuilder.h" |
| #include "swift/AST/ProtocolConformance.h" |
| #include "swift/AST/ParameterList.h" |
| #include "swift/AST/TypeCheckRequests.h" |
| #include "swift/AST/TypeResolutionStage.h" |
| #include "swift/AST/Types.h" |
| #include "swift/Basic/Defer.h" |
| #include "llvm/Support/ErrorHandling.h" |
| |
| using namespace swift; |
| |
| /// |
| /// Common code for generic functions, generic types |
| /// |
| |
| /// Check the generic parameters in the given generic parameter list (and its |
| /// parent generic parameter lists) according to the given resolver. |
| static void checkGenericParamList(TypeChecker &tc, |
| GenericSignatureBuilder *builder, |
| GenericParamList *genericParams, |
| GenericSignature *parentSig, |
| TypeResolution resolution) { |
| // If there is a parent context, add the generic parameters and requirements |
| // from that context. |
| builder->addGenericSignature(parentSig); |
| |
| assert(genericParams->size() > 0 && |
| "Parsed an empty generic parameter list?"); |
| |
| // Determine where and how to perform name lookup. |
| DeclContext *lookupDC = genericParams->begin()[0]->getDeclContext(); |
| assert(lookupDC == resolution.getDeclContext()); |
| |
| // First, add the generic parameters to the generic signature builder. |
| // Do this before checking the inheritance clause, since it may |
| // itself be dependent on one of these parameters. |
| for (auto param : *genericParams) |
| builder->addGenericParameter(param); |
| |
| // Add the requirements for each of the generic parameters to the builder. |
| // Now, check the inheritance clauses of each parameter. |
| for (auto param : *genericParams) |
| builder->addGenericParameterRequirements(param); |
| |
| // Add the requirements clause to the builder. |
| |
| WhereClauseOwner owner(resolution.getDeclContext(), genericParams); |
| using FloatingRequirementSource = |
| GenericSignatureBuilder::FloatingRequirementSource; |
| RequirementRequest::visitRequirements(owner, resolution.getStage(), |
| [&](const Requirement &req, RequirementRepr *reqRepr) { |
| auto source = FloatingRequirementSource::forExplicit(reqRepr); |
| |
| // If we're extending a protocol and adding a redundant requirement, |
| // for example, `extension Foo where Self: Foo`, then emit a |
| // diagnostic. |
| |
| if (auto decl = owner.dc->getAsDecl()) { |
| if (auto extDecl = dyn_cast<ExtensionDecl>(decl)) { |
| auto extType = extDecl->getExtendedType(); |
| auto extSelfType = extDecl->getSelfInterfaceType(); |
| auto reqLHSType = req.getFirstType(); |
| auto reqRHSType = req.getSecondType(); |
| |
| if (extType->isExistentialType() && |
| reqLHSType->isEqual(extSelfType) && |
| reqRHSType->isEqual(extType)) { |
| |
| auto &ctx = extDecl->getASTContext(); |
| ctx.Diags.diagnose(extDecl->getLoc(), |
| diag::protocol_extension_redundant_requirement, |
| extType->getString(), |
| extSelfType->getString(), |
| reqRHSType->getString()); |
| } |
| } |
| } |
| |
| builder->addRequirement(req, reqRepr, source, nullptr, |
| lookupDC->getParentModule()); |
| return false; |
| }); |
| } |
| |
| std::string |
| TypeChecker::gatherGenericParamBindingsText( |
| ArrayRef<Type> types, |
| TypeArrayView<GenericTypeParamType> genericParams, |
| TypeSubstitutionFn substitutions) { |
| llvm::SmallPtrSet<GenericTypeParamType *, 2> knownGenericParams; |
| for (auto type : types) { |
| if (type.isNull()) continue; |
| |
| type.visit([&](Type type) { |
| if (auto gp = type->getAs<GenericTypeParamType>()) { |
| knownGenericParams.insert( |
| gp->getCanonicalType()->castTo<GenericTypeParamType>()); |
| } |
| }); |
| } |
| |
| if (knownGenericParams.empty()) |
| return ""; |
| |
| SmallString<128> result; |
| for (auto gp : genericParams) { |
| auto canonGP = gp->getCanonicalType()->castTo<GenericTypeParamType>(); |
| if (!knownGenericParams.count(canonGP)) |
| continue; |
| |
| if (result.empty()) |
| result += " [with "; |
| else |
| result += ", "; |
| result += gp->getName().str(); |
| result += " = "; |
| |
| auto type = substitutions(canonGP); |
| if (!type) |
| return ""; |
| |
| result += type.getString(); |
| } |
| |
| result += "]"; |
| return result.str().str(); |
| } |
| |
| /// Add the generic parameter types from the given list to the vector. |
| static void addGenericParamTypes(GenericParamList *gpList, |
| SmallVectorImpl<GenericTypeParamType *> ¶ms) { |
| for (auto gpDecl : *gpList) { |
| params.push_back( |
| gpDecl->getDeclaredInterfaceType()->castTo<GenericTypeParamType>()); |
| } |
| } |
| |
| static void revertDependentTypeLoc(TypeLoc &tl) { |
| // If there's no type representation, there's nothing to revert. |
| if (!tl.getTypeRepr()) |
| return; |
| |
| // Don't revert an error type; we've already complained. |
| if (tl.wasValidated() && tl.isError()) |
| return; |
| |
| // Make sure we validate the type again. |
| tl.setType(Type()); |
| } |
| |
| /// |
| /// Generic functions |
| /// |
| |
| /// Check the signature of a generic function. |
| static void checkGenericFuncSignature(TypeChecker &tc, |
| GenericSignatureBuilder *builder, |
| AbstractFunctionDecl *func, |
| TypeResolution resolution) { |
| if (builder) { |
| // Check the generic parameter list. |
| checkGenericParamList(tc, builder, |
| func->getGenericParams(), |
| func->getDeclContext()->getGenericSignatureOfContext(), |
| resolution); |
| } |
| |
| // Check the parameter patterns. |
| auto params = func->getParameters(); |
| |
| tc.typeCheckParameterList(params, resolution, |
| TypeResolverContext::AbstractFunctionDecl); |
| |
| // Infer requirements from the pattern. |
| if (builder) { |
| builder->inferRequirements(*func->getParentModule(), params); |
| } |
| |
| // If there is a declared result type, check that as well. |
| if (auto fn = dyn_cast<FuncDecl>(func)) { |
| if (!fn->getBodyResultTypeLoc().isNull()) { |
| // Check the result type of the function. |
| TypeResolutionOptions options(fn->hasDynamicSelf() |
| ? TypeResolverContext::DynamicSelfResult |
| : TypeResolverContext::FunctionResult); |
| |
| tc.validateType(fn->getBodyResultTypeLoc(), resolution, options); |
| |
| // Infer requirements from it. |
| if (builder && |
| fn->getBodyResultTypeLoc().getTypeRepr()) { |
| auto source = |
| GenericSignatureBuilder::FloatingRequirementSource::forInferred( |
| fn->getBodyResultTypeLoc().getTypeRepr()); |
| builder->inferRequirements(*func->getParentModule(), |
| fn->getBodyResultTypeLoc().getType(), |
| fn->getBodyResultTypeLoc().getTypeRepr(), |
| source); |
| } |
| } |
| } |
| } |
| |
| static void revertGenericFuncSignature(AbstractFunctionDecl *func) { |
| // Revert the result type. |
| if (auto fn = dyn_cast<FuncDecl>(func)) |
| if (!fn->getBodyResultTypeLoc().isNull()) |
| revertDependentTypeLoc(fn->getBodyResultTypeLoc()); |
| |
| // Revert the body parameter types. |
| for (auto ¶m : *func->getParameters()) |
| revertDependentTypeLoc(param->getTypeLoc()); |
| } |
| |
| /// Determine whether the given type is \c Self, an associated type of \c Self, |
| /// or a concrete type. |
| static bool isSelfDerivedOrConcrete(Type protoSelf, Type type) { |
| // Check for a concrete type. |
| if (!type->hasTypeParameter()) |
| return true; |
| |
| if (type->isTypeParameter() && |
| type->getRootGenericParam()->isEqual(protoSelf)) |
| return true; |
| |
| return false; |
| } |
| |
| // For a generic requirement in a protocol, make sure that the requirement |
| // set didn't add any requirements to Self or its associated types. |
| void TypeChecker::checkProtocolSelfRequirements(ValueDecl *decl) { |
| // For a generic requirement in a protocol, make sure that the requirement |
| // set didn't add any requirements to Self or its associated types. |
| if (auto *proto = dyn_cast<ProtocolDecl>(decl->getDeclContext())) { |
| auto protoSelf = proto->getSelfInterfaceType(); |
| auto *sig = decl->getInnermostDeclContext()->getGenericSignatureOfContext(); |
| for (auto req : sig->getRequirements()) { |
| // If one of the types in the requirement is dependent on a non-Self |
| // type parameter, this requirement is okay. |
| if (!isSelfDerivedOrConcrete(protoSelf, req.getFirstType()) || |
| !isSelfDerivedOrConcrete(protoSelf, req.getSecondType())) |
| continue; |
| |
| // The conformance of 'Self' to the protocol is okay. |
| if (req.getKind() == RequirementKind::Conformance && |
| req.getSecondType()->getAs<ProtocolType>()->getDecl() == proto && |
| req.getFirstType()->is<GenericTypeParamType>()) |
| continue; |
| |
| diagnose(decl, |
| diag::requirement_restricts_self, |
| decl->getDescriptiveKind(), decl->getFullName(), |
| req.getFirstType().getString(), |
| static_cast<unsigned>(req.getKind()), |
| req.getSecondType().getString()); |
| } |
| } |
| } |
| |
| /// All generic parameters of a generic function must be referenced in the |
| /// declaration's type, otherwise we have no way to infer them. |
| void TypeChecker::checkReferencedGenericParams(GenericContext *dc) { |
| // Don't do this check for accessors: they're not used directly, so we |
| // never need to infer their generic arguments. This is mostly a |
| // compile-time optimization, but it also avoids problems with accessors |
| // like 'read' and 'modify' that would arise due to yields not being |
| // part of the formal type. |
| if (isa<AccessorDecl>(dc)) |
| return; |
| |
| auto *genericParams = dc->getGenericParams(); |
| auto *genericSig = dc->getGenericSignatureOfContext(); |
| if (!genericParams) |
| return; |
| |
| auto *decl = cast<ValueDecl>(dc->getInnermostDeclarationDeclContext()); |
| |
| // A helper class to collect referenced generic type parameters |
| // and dependent member types. |
| class ReferencedGenericTypeWalker : public TypeWalker { |
| SmallPtrSet<CanType, 4> ReferencedGenericParams; |
| |
| public: |
| ReferencedGenericTypeWalker() {} |
| Action walkToTypePre(Type ty) override { |
| // Find generic parameters or dependent member types. |
| // Once such a type is found, don't recurse into its children. |
| if (!ty->hasTypeParameter()) |
| return Action::SkipChildren; |
| if (ty->isTypeParameter()) { |
| ReferencedGenericParams.insert(ty->getCanonicalType()); |
| return Action::SkipChildren; |
| } |
| return Action::Continue; |
| } |
| |
| SmallPtrSetImpl<CanType> &getReferencedGenericParams() { |
| return ReferencedGenericParams; |
| } |
| }; |
| |
| // Collect all generic params referenced in parameter types and |
| // return type. |
| ReferencedGenericTypeWalker paramsAndResultWalker; |
| auto *funcTy = decl->getInterfaceType()->castTo<GenericFunctionType>(); |
| for (const auto ¶m : funcTy->getParams()) |
| param.getOldType().walk(paramsAndResultWalker); |
| funcTy->getResult().walk(paramsAndResultWalker); |
| |
| // Set of generic params referenced in parameter types, |
| // return type or requirements. |
| auto &referencedGenericParams = |
| paramsAndResultWalker.getReferencedGenericParams(); |
| |
| // Check if at least one of the generic params in the requirement refers |
| // to an already referenced generic parameter. If this is the case, |
| // then the other type is also considered as referenced, because |
| // it is used to put requirements on the first type. |
| auto reqTypesVisitor = [&referencedGenericParams](Requirement req) -> bool { |
| Type first; |
| Type second; |
| |
| switch (req.getKind()) { |
| case RequirementKind::Superclass: |
| case RequirementKind::SameType: |
| second = req.getSecondType(); |
| LLVM_FALLTHROUGH; |
| |
| case RequirementKind::Conformance: |
| case RequirementKind::Layout: |
| first = req.getFirstType(); |
| break; |
| } |
| |
| // Collect generic parameter types referenced by types used in a requirement. |
| ReferencedGenericTypeWalker walker; |
| if (first && first->hasTypeParameter()) |
| first.walk(walker); |
| if (second && second->hasTypeParameter()) |
| second.walk(walker); |
| auto &genericParamsUsedByRequirementTypes = |
| walker.getReferencedGenericParams(); |
| |
| // If at least one of the collected generic types or a root generic |
| // parameter of dependent member types is known to be referenced by |
| // parameter types, return types or other types known to be "referenced", |
| // then all the types used in the requirement are considered to be |
| // referenced, because they are used to defined something that is known |
| // to be referenced. |
| bool foundNewReferencedGenericParam = false; |
| if (std::any_of(genericParamsUsedByRequirementTypes.begin(), |
| genericParamsUsedByRequirementTypes.end(), |
| [&referencedGenericParams](CanType t) { |
| assert(t->isTypeParameter()); |
| return referencedGenericParams.find( |
| t->getRootGenericParam() |
| ->getCanonicalType()) != |
| referencedGenericParams.end(); |
| })) { |
| std::for_each(genericParamsUsedByRequirementTypes.begin(), |
| genericParamsUsedByRequirementTypes.end(), |
| [&referencedGenericParams, |
| &foundNewReferencedGenericParam](CanType t) { |
| // Add only generic type parameters, but ignore any |
| // dependent member types, because requirement |
| // on a dependent member type does not provide enough |
| // information to infer the base generic type |
| // parameter. |
| if (!t->is<GenericTypeParamType>()) |
| return; |
| if (referencedGenericParams.insert(t).second) |
| foundNewReferencedGenericParam = true; |
| }); |
| } |
| return foundNewReferencedGenericParam; |
| }; |
| |
| ArrayRef<Requirement> requirements; |
| |
| auto FindReferencedGenericParamsInRequirements = |
| [&requirements, genericSig, &reqTypesVisitor] { |
| requirements = genericSig->getRequirements(); |
| // Try to find new referenced generic parameter types in requirements until |
| // we reach a fix point. We need to iterate until a fix point, because we |
| // may have e.g. chains of same-type requirements like: |
| // not-yet-referenced-T1 == not-yet-referenced-T2.DepType2, |
| // not-yet-referenced-T2 == not-yet-referenced-T3.DepType3, |
| // not-yet-referenced-T3 == referenced-T4.DepType4. |
| // When we process the first of these requirements, we don't know yet that |
| // T2 |
| // will be referenced, because T3 will be referenced, |
| // because T3 == T4.DepType4. |
| while (true) { |
| bool foundNewReferencedGenericParam = false; |
| for (auto req : requirements) { |
| if (reqTypesVisitor(req)) |
| foundNewReferencedGenericParam = true; |
| } |
| if (!foundNewReferencedGenericParam) |
| break; |
| } |
| }; |
| |
| // Find the depth of the function's own generic parameters. |
| unsigned fnGenericParamsDepth = genericParams->getParams().front()->getDepth(); |
| |
| // Check that every generic parameter type from the signature is |
| // among referencedGenericParams. |
| for (auto *genParam : genericSig->getGenericParams()) { |
| auto *paramDecl = genParam->getDecl(); |
| if (paramDecl->getDepth() != fnGenericParamsDepth) |
| continue; |
| if (!referencedGenericParams.count(genParam->getCanonicalType())) { |
| // Lazily search for generic params that are indirectly used in the |
| // function signature. Do it only if there is a generic parameter |
| // that is not known to be referenced yet. |
| if (requirements.empty()) { |
| FindReferencedGenericParamsInRequirements(); |
| // Nothing to do if this generic parameter is considered to be |
| // referenced after analyzing the requirements from the generic |
| // signature. |
| if (referencedGenericParams.count(genParam->getCanonicalType())) |
| continue; |
| } |
| // Produce an error that this generic parameter cannot be bound. |
| diagnose(paramDecl->getLoc(), diag::unreferenced_generic_parameter, |
| paramDecl->getNameStr()); |
| decl->setInterfaceType(ErrorType::get(Context)); |
| decl->setInvalid(); |
| } |
| } |
| } |
| |
| static GenericSignature * |
| computeGenericFuncSignature(TypeChecker &tc, AbstractFunctionDecl *func) { |
| auto *dc = func->getDeclContext(); |
| |
| // Check whether the function is separately generic. |
| auto gp = func->getGenericParams(); |
| if (!gp) { |
| // If not, inherit the signature of our environment. |
| func->setGenericEnvironment(dc->getGenericEnvironmentOfContext()); |
| return dc->getGenericSignatureOfContext(); |
| } |
| |
| // Do some initial configuration of the generic parameter lists that's |
| // required in all cases. |
| gp->setDepth(func->getGenericContextDepth()); |
| |
| // Accessors can always use the generic context of their storage |
| // declarations. This is a compile-time optimization since it lets us |
| // avoid the requirements-gathering phase, but it also simplifies that |
| // work for accessors which don't mention the value type in their formal |
| // signatures (like the read and modify coroutines, since yield types |
| // aren't tracked in the AST type yet). |
| // |
| // Most accessors will implicitly have been handled above because they |
| // aren't separately generic; we only get here for the accessors of |
| // generic subscripts. |
| if (auto accessor = dyn_cast<AccessorDecl>(func)) { |
| auto subscript = cast<SubscriptDecl>(accessor->getStorage()); |
| auto sig = subscript->getGenericSignature(); |
| auto env = subscript->getGenericEnvironment(); |
| assert(sig && env && "accessor has generics but subscript is not generic"); |
| func->setGenericEnvironment(env); |
| return sig; |
| } |
| |
| // Create the generic signature builder. |
| GenericSignatureBuilder builder(tc.Context); |
| |
| // Type check the function declaration, treating all generic type |
| // parameters as dependent, unresolved. |
| checkGenericFuncSignature(tc, &builder, func, |
| TypeResolution::forStructural(func)); |
| |
| // The generic function signature is complete and well-formed. Determine |
| // the type of the generic function. |
| auto sig = std::move(builder).computeGenericSignature(func->getLoc()); |
| |
| // The generic signature builder now has all of the requirements, although |
| // there might still be errors that have not yet been diagnosed. Revert the |
| // generic function signature and type-check it again, completely. |
| revertGenericFuncSignature(func); |
| |
| // Debugging of the generic signature. |
| if (tc.Context.LangOpts.DebugGenericSignatures) { |
| func->dumpRef(llvm::errs()); |
| llvm::errs() << "\n"; |
| llvm::errs() << "Generic signature: "; |
| sig->print(llvm::errs()); |
| llvm::errs() << "\n"; |
| llvm::errs() << "Canonical generic signature: "; |
| sig->getCanonicalSignature()->print(llvm::errs()); |
| llvm::errs() << "\n"; |
| } |
| |
| GenericEnvironment *env = sig->createGenericEnvironment(); |
| func->setGenericEnvironment(env); |
| |
| return sig; |
| } |
| |
| void TypeChecker::validateGenericFuncSignature(AbstractFunctionDecl *func) { |
| GenericSignature *sig = computeGenericFuncSignature(*this, func); |
| |
| checkGenericFuncSignature(*this, nullptr, func, |
| TypeResolution::forInterface(func, sig)); |
| |
| func->computeType(); |
| |
| // Make sure that there are no unresolved dependent types in the |
| // generic signature. |
| assert(!func->getInterfaceType()->findUnresolvedDependentMemberType()); |
| } |
| |
| /// |
| /// Generic subscripts |
| /// |
| /// FIXME: A lot of this code is duplicated from the generic functions |
| /// path above. We could consolidate more of this. |
| /// |
| |
| /// Check the signature of a generic subscript. |
| static void checkGenericSubscriptSignature(TypeChecker &tc, |
| GenericSignatureBuilder *builder, |
| SubscriptDecl *subscript, |
| TypeResolution resolution) { |
| // Check the generic parameter list. |
| auto *dc = subscript->getDeclContext(); |
| |
| if (builder) { |
| checkGenericParamList(tc, builder, |
| subscript->getGenericParams(), |
| dc->getGenericSignatureOfContext(), |
| resolution); |
| } |
| |
| // Check the element type. |
| tc.validateType(subscript->getElementTypeLoc(), resolution, |
| TypeResolverContext::FunctionResult); |
| |
| // Infer requirements from it. |
| if (builder) { |
| auto source = |
| GenericSignatureBuilder::FloatingRequirementSource::forInferred( |
| subscript->getElementTypeLoc().getTypeRepr()); |
| |
| builder->inferRequirements(*subscript->getParentModule(), |
| subscript->getElementTypeLoc().getType(), |
| subscript->getElementTypeLoc().getTypeRepr(), |
| source); |
| } |
| |
| // Check the indices. |
| auto params = subscript->getIndices(); |
| |
| tc.typeCheckParameterList(params, resolution, |
| TypeResolverContext::SubscriptDecl); |
| |
| // Infer requirements from the pattern. |
| if (builder) { |
| builder->inferRequirements(*subscript->getParentModule(), params); |
| } |
| } |
| |
| static void revertGenericSubscriptSignature(SubscriptDecl *subscript) { |
| // Revert the element type. |
| if (!subscript->getElementTypeLoc().isNull()) |
| revertDependentTypeLoc(subscript->getElementTypeLoc()); |
| |
| // Revert the indices. |
| for (auto ¶m : *subscript->getIndices()) |
| revertDependentTypeLoc(param->getTypeLoc()); |
| } |
| |
| void |
| TypeChecker::validateGenericSubscriptSignature(SubscriptDecl *subscript) { |
| auto *dc = subscript->getDeclContext(); |
| |
| GenericSignature *sig; |
| if (auto *gp = subscript->getGenericParams()) { |
| gp->setDepth(subscript->getGenericContextDepth()); |
| |
| // Create the generic signature builder. |
| GenericSignatureBuilder builder(Context); |
| |
| // Type check the function declaration, treating all generic type |
| // parameters as dependent, unresolved. |
| checkGenericSubscriptSignature(*this, &builder, subscript, |
| TypeResolution::forStructural(subscript)); |
| |
| // The generic subscript signature is complete and well-formed. Determine |
| // the type of the generic subscript. |
| sig = |
| std::move(builder).computeGenericSignature(subscript->getLoc()); |
| |
| // The generic signature builder now has all of the requirements, although |
| // there might still be errors that have not yet been diagnosed. Revert the |
| // generic function signature and type-check it again, completely. |
| revertGenericSubscriptSignature(subscript); |
| |
| // Debugging of generic signature generation. |
| if (Context.LangOpts.DebugGenericSignatures) { |
| subscript->dumpRef(llvm::errs()); |
| llvm::errs() << "\n"; |
| llvm::errs() << "Generic signature: "; |
| sig->print(llvm::errs()); |
| llvm::errs() << "\n"; |
| llvm::errs() << "Canonical generic signature: "; |
| sig->getCanonicalSignature()->print(llvm::errs()); |
| llvm::errs() << "\n"; |
| } |
| |
| subscript->setGenericEnvironment(sig->createGenericEnvironment()); |
| } else { |
| // Inherit the signature of our environment. |
| sig = dc->getGenericSignatureOfContext(); |
| subscript->setGenericEnvironment(dc->getGenericEnvironmentOfContext()); |
| } |
| |
| checkGenericSubscriptSignature(*this, nullptr, subscript, |
| TypeResolution::forInterface(subscript, sig)); |
| |
| subscript->computeType(); |
| } |
| |
| /// |
| /// Generic types |
| /// |
| |
| /// Visit the given generic parameter lists from the outermost to the innermost, |
| /// calling the visitor function for each list. |
| static void visitOuterToInner( |
| GenericParamList *genericParams, |
| llvm::function_ref<void(GenericParamList *)> visitor) { |
| if (auto outerGenericParams = genericParams->getOuterParameters()) |
| visitOuterToInner(outerGenericParams, visitor); |
| |
| visitor(genericParams); |
| } |
| |
| /// Retrieve the generic parameter depth of the extended type. |
| static unsigned getExtendedTypeGenericDepth(ExtensionDecl *ext) { |
| auto nominal = ext->getSelfNominalTypeDecl(); |
| if (!nominal) return static_cast<unsigned>(-1); |
| |
| auto sig = nominal->getGenericSignatureOfContext(); |
| if (!sig) return static_cast<unsigned>(-1); |
| |
| return sig->getGenericParams().back()->getDepth(); |
| } |
| |
| GenericEnvironment *TypeChecker::checkGenericEnvironment( |
| GenericParamList *genericParams, |
| DeclContext *dc, |
| GenericSignature *parentSig, |
| bool allowConcreteGenericParams, |
| ExtensionDecl *ext, |
| llvm::function_ref<void(GenericSignatureBuilder &)> |
| inferRequirements, |
| bool mustInferRequirements) { |
| assert(genericParams && "Missing generic parameters?"); |
| bool recursivelyVisitGenericParams = |
| genericParams->getOuterParameters() && !parentSig; |
| |
| GenericSignature *sig; |
| if (!ext || mustInferRequirements || ext->getTrailingWhereClause() || |
| getExtendedTypeGenericDepth(ext) != |
| genericParams->getParams().back()->getDepth()) { |
| // Collect the generic parameters. |
| SmallVector<GenericTypeParamType *, 4> allGenericParams; |
| if (recursivelyVisitGenericParams) { |
| visitOuterToInner(genericParams, |
| [&](GenericParamList *gpList) { |
| addGenericParamTypes(gpList, allGenericParams); |
| }); |
| } else { |
| if (parentSig) { |
| allGenericParams.append(parentSig->getGenericParams().begin(), |
| parentSig->getGenericParams().end()); |
| } |
| |
| addGenericParamTypes(genericParams, allGenericParams); |
| } |
| |
| // Create the generic signature builder. |
| GenericSignatureBuilder builder(Context); |
| |
| // Type check the generic parameters, treating all generic type |
| // parameters as dependent, unresolved. |
| if (recursivelyVisitGenericParams) { |
| visitOuterToInner(genericParams, |
| [&](GenericParamList *gpList) { |
| auto genericParamsDC = gpList->begin()[0]->getDeclContext(); |
| TypeResolution structuralResolution = |
| TypeResolution::forStructural(genericParamsDC); |
| checkGenericParamList(*this, &builder, gpList, nullptr, |
| structuralResolution); |
| }); |
| } else { |
| auto genericParamsDC = genericParams->begin()[0]->getDeclContext(); |
| TypeResolution structuralResolution = |
| TypeResolution::forStructural(genericParamsDC); |
| checkGenericParamList(*this, &builder, genericParams, parentSig, |
| structuralResolution); |
| } |
| |
| /// Perform any necessary requirement inference. |
| inferRequirements(builder); |
| |
| // Record the generic type parameter types and the requirements. |
| sig = std::move(builder).computeGenericSignature( |
| genericParams->getSourceRange().Start, |
| allowConcreteGenericParams); |
| |
| // Debugging of the generic signature builder and generic signature |
| // generation. |
| if (Context.LangOpts.DebugGenericSignatures) { |
| dc->printContext(llvm::errs()); |
| llvm::errs() << "\n"; |
| llvm::errs() << "Generic signature: "; |
| sig->print(llvm::errs()); |
| llvm::errs() << "\n"; |
| llvm::errs() << "Canonical generic signature: "; |
| sig->getCanonicalSignature()->print(llvm::errs()); |
| llvm::errs() << "\n"; |
| } |
| } else { |
| // Re-use the signature of the type being extended. |
| sig = ext->getSelfNominalTypeDecl()->getGenericSignatureOfContext(); |
| } |
| |
| // Form the generic environment. |
| return sig->createGenericEnvironment(); |
| } |
| |
| void TypeChecker::validateGenericTypeSignature(GenericTypeDecl *typeDecl) { |
| if (auto *proto = dyn_cast<ProtocolDecl>(typeDecl)) { |
| // Compute the requirement signature first. |
| if (!proto->isRequirementSignatureComputed()) |
| proto->computeRequirementSignature(); |
| |
| // The generic signature and environment is created lazily by |
| // GenericContext::getGenericSignature(), so there is nothing we |
| // need to do. |
| |
| // Debugging of the generic signature builder and generic signature |
| // generation. |
| if (Context.LangOpts.DebugGenericSignatures) { |
| auto *sig = proto->getGenericSignature(); |
| |
| proto->printContext(llvm::errs()); |
| llvm::errs() << "\n"; |
| llvm::errs() << "Generic signature: "; |
| sig->print(llvm::errs()); |
| llvm::errs() << "\n"; |
| llvm::errs() << "Canonical generic signature: "; |
| sig->getCanonicalSignature()->print(llvm::errs()); |
| llvm::errs() << "\n"; |
| } |
| |
| return; |
| } |
| |
| assert(!typeDecl->getGenericEnvironment()); |
| |
| // We don't go down this path for protocols; instead, the generic signature |
| // is simple enough that GenericContext::getGenericSignature() can build it |
| // directly. |
| assert(!isa<ProtocolDecl>(typeDecl)); |
| |
| auto *gp = typeDecl->getGenericParams(); |
| auto *dc = typeDecl->getDeclContext(); |
| |
| if (!gp) { |
| auto *parentEnv = dc->getGenericEnvironmentOfContext(); |
| typeDecl->setGenericEnvironment(parentEnv); |
| return; |
| } |
| |
| gp->setDepth(typeDecl->getGenericContextDepth()); |
| |
| auto *env = checkGenericEnvironment(gp, dc, |
| dc->getGenericSignatureOfContext(), |
| /*allowConcreteGenericParams=*/false, |
| /*ext=*/nullptr); |
| typeDecl->setGenericEnvironment(env); |
| } |
| |
| /// |
| /// Checking bound generic type arguments |
| /// |
| |
| RequirementCheckResult TypeChecker::checkGenericArguments( |
| DeclContext *dc, SourceLoc loc, SourceLoc noteLoc, Type owner, |
| TypeArrayView<GenericTypeParamType> genericParams, |
| ArrayRef<Requirement> requirements, |
| TypeSubstitutionFn substitutions, |
| LookupConformanceFn conformances, |
| ConformanceCheckOptions conformanceOptions, |
| GenericRequirementsCheckListener *listener, |
| SubstOptions options) { |
| bool valid = true; |
| |
| // We handle any conditional requirements ourselves. |
| conformanceOptions |= ConformanceCheckFlags::SkipConditionalRequirements; |
| |
| struct RequirementSet { |
| ArrayRef<Requirement> Requirements; |
| SmallVector<ParentConditionalConformance, 4> Parents; |
| }; |
| |
| SmallVector<RequirementSet, 8> pendingReqs; |
| pendingReqs.push_back({requirements, {}}); |
| |
| ASTContext &ctx = dc->getASTContext(); |
| while (!pendingReqs.empty()) { |
| auto current = pendingReqs.pop_back_val(); |
| |
| for (const auto &rawReq : current.Requirements) { |
| auto req = rawReq; |
| if (current.Parents.empty()) { |
| auto substed = rawReq.subst(substitutions, conformances, options); |
| if (!substed) { |
| // Another requirement will fail later; just continue. |
| valid = false; |
| continue; |
| } |
| |
| req = *substed; |
| } |
| |
| auto kind = req.getKind(); |
| Type rawFirstType = rawReq.getFirstType(); |
| Type firstType = req.getFirstType(); |
| if (firstType->hasTypeParameter()) |
| firstType = dc->mapTypeIntoContext(firstType); |
| |
| Type rawSecondType, secondType; |
| if (kind != RequirementKind::Layout) { |
| rawSecondType = rawReq.getSecondType(); |
| secondType = req.getSecondType(); |
| if (secondType->hasTypeParameter()) |
| secondType = dc->mapTypeIntoContext(secondType); |
| } |
| |
| // Don't do further checking on error types. |
| if (firstType->hasError() || (secondType && secondType->hasError())) { |
| // Another requirement will fail later; just continue. |
| valid = false; |
| continue; |
| } |
| |
| bool requirementFailure = false; |
| if (listener && !listener->shouldCheck(kind, firstType, secondType)) |
| continue; |
| |
| Diag<Type, Type, Type> diagnostic; |
| Diag<Type, Type, StringRef> diagnosticNote; |
| |
| switch (kind) { |
| case RequirementKind::Conformance: { |
| // Protocol conformance requirements. |
| auto proto = secondType->castTo<ProtocolType>(); |
| // FIXME: This should track whether this should result in a private |
| // or non-private dependency. |
| // FIXME: Do we really need "used" at this point? |
| // FIXME: Poor location information. How much better can we do here? |
| // FIXME: This call should support listener to be able to properly |
| // diagnose problems with conformances. |
| auto result = |
| conformsToProtocol(firstType, proto->getDecl(), dc, |
| conformanceOptions, loc); |
| |
| if (result) { |
| auto conformance = *result; |
| // Report the conformance. |
| if (listener && valid && current.Parents.empty()) { |
| listener->satisfiedConformance(rawFirstType, firstType, |
| conformance); |
| } |
| |
| auto conditionalReqs = conformance.getConditionalRequirements(); |
| if (!conditionalReqs.empty()) { |
| auto history = current.Parents; |
| history.push_back({firstType, proto}); |
| pendingReqs.push_back({conditionalReqs, std::move(history)}); |
| } |
| continue; |
| } |
| |
| // A failure at the top level is diagnosed elsewhere. |
| if (current.Parents.empty()) |
| return RequirementCheckResult::Failure; |
| |
| // Failure needs to emit a diagnostic. |
| diagnostic = diag::type_does_not_conform_owner; |
| diagnosticNote = diag::type_does_not_inherit_or_conform_requirement; |
| requirementFailure = true; |
| break; |
| } |
| |
| case RequirementKind::Layout: |
| // TODO: Statically check other layout constraints, once they can |
| // be spelled in Swift. |
| if (req.getLayoutConstraint()->isClass() && |
| !firstType->satisfiesClassConstraint()) { |
| diagnostic = diag::type_is_not_a_class; |
| diagnosticNote = diag::anyobject_requirement; |
| requirementFailure = true; |
| } |
| break; |
| |
| case RequirementKind::Superclass: { |
| // Superclass requirements. |
| if (!secondType->isExactSuperclassOf(firstType)) { |
| diagnostic = diag::type_does_not_inherit; |
| diagnosticNote = diag::type_does_not_inherit_or_conform_requirement; |
| requirementFailure = true; |
| } |
| break; |
| } |
| |
| case RequirementKind::SameType: |
| if (!firstType->isEqual(secondType)) { |
| diagnostic = diag::types_not_equal; |
| diagnosticNote = diag::types_not_equal_requirement; |
| requirementFailure = true; |
| } |
| break; |
| } |
| |
| if (!requirementFailure) |
| continue; |
| |
| if (listener && |
| listener->diagnoseUnsatisfiedRequirement(rawReq, firstType, |
| secondType, current.Parents)) |
| return RequirementCheckResult::Failure; |
| |
| if (loc.isValid()) { |
| // FIXME: Poor source-location information. |
| ctx.Diags.diagnose(loc, diagnostic, owner, firstType, secondType); |
| |
| std::string genericParamBindingsText; |
| if (!genericParams.empty()) { |
| genericParamBindingsText = |
| gatherGenericParamBindingsText( |
| {rawFirstType, rawSecondType}, genericParams, substitutions); |
| } |
| ctx.Diags.diagnose(noteLoc, diagnosticNote, rawFirstType, rawSecondType, |
| genericParamBindingsText); |
| |
| ParentConditionalConformance::diagnoseConformanceStack( |
| ctx.Diags, noteLoc, current.Parents); |
| } |
| |
| return RequirementCheckResult::Failure; |
| } |
| } |
| |
| if (valid) |
| return RequirementCheckResult::Success; |
| return RequirementCheckResult::SubstitutionFailure; |
| } |
| |
| llvm::Expected<Requirement> |
| RequirementRequest::evaluate(Evaluator &evaluator, |
| WhereClauseOwner owner, |
| unsigned index, |
| TypeResolutionStage stage) const { |
| // Figure out the type resolution. |
| TypeResolutionOptions options = TypeResolverContext::GenericRequirement; |
| Optional<TypeResolution> resolution; |
| switch (stage) { |
| case TypeResolutionStage::Structural: |
| resolution = TypeResolution::forStructural(owner.dc); |
| break; |
| |
| case TypeResolutionStage::Interface: |
| resolution = TypeResolution::forInterface(owner.dc); |
| break; |
| |
| case TypeResolutionStage::Contextual: |
| llvm_unreachable("No clients care about this. Use mapTypeIntoContext()"); |
| } |
| |
| auto resolveType = [&](TypeLoc &typeLoc) -> Type { |
| Type result; |
| if (auto typeRepr = typeLoc.getTypeRepr()) |
| result = resolution->resolveType(typeRepr, options); |
| else |
| result = typeLoc.getType(); |
| |
| return result ? result : ErrorType::get(owner.dc->getASTContext()); |
| }; |
| |
| auto &reqRepr = getRequirement(); |
| switch (reqRepr.getKind()) { |
| case RequirementReprKind::TypeConstraint: { |
| Type subject = resolveType(reqRepr.getSubjectLoc()); |
| Type constraint = resolveType(reqRepr.getConstraintLoc()); |
| return Requirement(constraint->getClassOrBoundGenericClass() |
| ? RequirementKind::Superclass |
| : RequirementKind::Conformance, |
| subject, constraint); |
| } |
| |
| case RequirementReprKind::SameType: |
| return Requirement(RequirementKind::SameType, |
| resolveType(reqRepr.getFirstTypeLoc()), |
| resolveType(reqRepr.getSecondTypeLoc())); |
| |
| case RequirementReprKind::LayoutConstraint: |
| return Requirement(RequirementKind::Layout, |
| resolveType(reqRepr.getSubjectLoc()), |
| reqRepr.getLayoutConstraint()); |
| } |
| llvm_unreachable("unhandled kind"); |
| } |