mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
6ffa8fd489
Instead of passing in the substituted type, we pass in the InFlightSubstitution. This allows the substituted type to be recovered if needed, but we can now skip computing it for the common case of LookUpConformanceInSubstitutionMap.
291 lines
11 KiB
C++
291 lines
11 KiB
C++
//===--- ExistentialGeneralization.cpp - Shape generalization algorithm ---===//
|
|
//
|
|
// This source file is part of the Swift.org open source project
|
|
//
|
|
// Copyright (c) 2014 - 2018 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 defines the existential type generalization algorithm,
|
|
// which is used in the ABI for existential types.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "swift/AST/CanTypeVisitor.h"
|
|
#include "swift/AST/Decl.h"
|
|
#include "swift/AST/GenericSignature.h"
|
|
#include "swift/AST/Requirement.h"
|
|
#include "swift/AST/Types.h"
|
|
#include "swift/Basic/Assertions.h"
|
|
#include "llvm/ADT/DenseMap.h"
|
|
|
|
using namespace swift;
|
|
|
|
namespace {
|
|
|
|
/// A helper type for performing existential type generalization.
|
|
class Generalizer : public CanTypeVisitor<Generalizer, Type> {
|
|
friend CanTypeVisitor<Generalizer, Type>;
|
|
|
|
ASTContext &ctx;
|
|
|
|
llvm::DenseMap<CanType, Type> substTypes;
|
|
llvm::DenseMap<std::pair<CanType, ProtocolDecl*>,
|
|
ProtocolConformanceRef> substConformances;
|
|
|
|
SmallVector<GenericTypeParamType *, 2> addedParameters;
|
|
SmallVector<Requirement, 2> addedRequirements;
|
|
|
|
public:
|
|
Generalizer(ASTContext &ctx) : ctx(ctx) {}
|
|
|
|
/// Given that the given type is not itself substitutable in whatever
|
|
/// position it appears in, generalize it.
|
|
Type generalizeStructure(CanType type) {
|
|
return visit(type);
|
|
}
|
|
|
|
SubstitutionMap getGeneralizationSubstitutions() {
|
|
// If we never introduced a generalization parameter, we're done.
|
|
if (addedParameters.empty() && addedRequirements.empty())
|
|
return SubstitutionMap();
|
|
|
|
// Finish the signature.
|
|
auto sig = buildGenericSignature(ctx, GenericSignature(),
|
|
addedParameters,
|
|
addedRequirements,
|
|
/*allowInverses=*/false);
|
|
|
|
// TODO: minimize the signature by removing redundant generic
|
|
// parameters.
|
|
|
|
auto lookupParameter = [&](SubstitutableType *type) {
|
|
auto it = substTypes.find(CanType(type));
|
|
assert(it != substTypes.end());
|
|
return it->second;
|
|
};
|
|
auto lookupConformance = [&](InFlightSubstitution &IFS,
|
|
Type dependentType,
|
|
ProtocolDecl *conformedProtocol) {
|
|
auto it = substConformances.find(
|
|
{dependentType->getCanonicalType(), conformedProtocol});
|
|
assert(it != substConformances.end());
|
|
return it->second;
|
|
};
|
|
return SubstitutionMap::get(sig, lookupParameter, lookupConformance);
|
|
}
|
|
|
|
private:
|
|
Type visitProtocolType(CanProtocolType type) {
|
|
// Simple protocol types have no sub-structure.
|
|
return type;
|
|
}
|
|
|
|
Type visitParameterizedProtocolType(CanParameterizedProtocolType origType) {
|
|
// Generalize the argument types of parameterized protocols,
|
|
// but don't generalize the base type.
|
|
auto origArgs = origType.getArgs();
|
|
SmallVector<Type, 4> newArgs;
|
|
newArgs.reserve(origArgs.size());
|
|
for (auto origArg: origArgs) {
|
|
newArgs.push_back(generalizeComponentType(origArg));
|
|
}
|
|
return ParameterizedProtocolType::get(ctx, origType->getBaseType(),
|
|
newArgs);
|
|
}
|
|
|
|
Type visitProtocolCompositionType(CanProtocolCompositionType origType) {
|
|
// The member types of protocol compositions are not substitutable,
|
|
// including class constraints. Generalize them individually,
|
|
// preserving structure.
|
|
auto origMembers = origType.getMembers();
|
|
SmallVector<Type, 4> newMembers;
|
|
newMembers.reserve(origMembers.size());
|
|
for (auto origMember: origMembers) {
|
|
newMembers.push_back(generalizeStructure(origMember));
|
|
}
|
|
return ProtocolCompositionType::get(ctx, newMembers,
|
|
origType->getInverses(),
|
|
origType->hasExplicitAnyObject());
|
|
}
|
|
|
|
// Generalize the type arguments of nominal types.
|
|
Type visitBoundGenericType(CanBoundGenericType origType) {
|
|
return generalizeGenericArguments(origType->getDecl(), origType);
|
|
}
|
|
Type visitNominalType(CanNominalType origType) {
|
|
auto decl = origType->getDecl();
|
|
if (decl->isGenericContext())
|
|
return generalizeGenericArguments(decl, origType);
|
|
return origType;
|
|
}
|
|
|
|
// Preserve existential structure.
|
|
Type visitExistentialType(CanExistentialType origType) {
|
|
return ExistentialType::get(
|
|
generalizeStructure(origType.getConstraintType()));
|
|
}
|
|
Type visitExistentialMetatypeType(CanExistentialMetatypeType origType) {
|
|
assert(!origType->hasRepresentation());
|
|
return ExistentialMetatypeType::get(
|
|
generalizeStructure(origType.getInstanceType()));
|
|
}
|
|
|
|
// These types can be generalized by a recursive transform of
|
|
// their component types; we don't need to exclude anything or
|
|
// handle conformances.
|
|
#define GENERALIZE_COMPONENTS(ID) \
|
|
Type visit##ID##Type(Can##ID##Type origType) { \
|
|
return generalizeComponentTypes(origType); \
|
|
}
|
|
GENERALIZE_COMPONENTS(Function)
|
|
GENERALIZE_COMPONENTS(Metatype)
|
|
GENERALIZE_COMPONENTS(Tuple)
|
|
#undef GENERALIZE_COMPONENTS
|
|
|
|
// These types can never contain component types with abstract
|
|
// constraints, so generalizeComponentType should always substitute
|
|
// them out.
|
|
#define NO_PRESERVABLE_STRUCTURE(ID) \
|
|
Type visit##ID##Type(Can##ID##Type origType) { \
|
|
llvm_unreachable(#ID "Type has no structure to preserve"); \
|
|
}
|
|
NO_PRESERVABLE_STRUCTURE(Archetype)
|
|
NO_PRESERVABLE_STRUCTURE(Builtin)
|
|
NO_PRESERVABLE_STRUCTURE(DependentMember)
|
|
NO_PRESERVABLE_STRUCTURE(GenericTypeParam)
|
|
NO_PRESERVABLE_STRUCTURE(Module)
|
|
NO_PRESERVABLE_STRUCTURE(Pack)
|
|
NO_PRESERVABLE_STRUCTURE(PackExpansion)
|
|
NO_PRESERVABLE_STRUCTURE(PackElement)
|
|
NO_PRESERVABLE_STRUCTURE(Integer)
|
|
#undef NO_PRESERVABLE_STRUCTURE
|
|
|
|
// These types simply shouldn't appear in types that we generalize at all.
|
|
#define INVALID_TO_GENERALIZE(ID) \
|
|
Type visit##ID##Type(Can##ID##Type origType) { \
|
|
llvm_unreachable(#ID "type should not be found by generalization"); \
|
|
}
|
|
INVALID_TO_GENERALIZE(DynamicSelf)
|
|
INVALID_TO_GENERALIZE(Error)
|
|
INVALID_TO_GENERALIZE(GenericFunction)
|
|
INVALID_TO_GENERALIZE(InOut)
|
|
INVALID_TO_GENERALIZE(LValue)
|
|
INVALID_TO_GENERALIZE(ReferenceStorage)
|
|
INVALID_TO_GENERALIZE(SILBlockStorage)
|
|
INVALID_TO_GENERALIZE(SILBox)
|
|
INVALID_TO_GENERALIZE(SILFunction)
|
|
INVALID_TO_GENERALIZE(SILPack)
|
|
INVALID_TO_GENERALIZE(SILToken)
|
|
INVALID_TO_GENERALIZE(SILMoveOnlyWrapped)
|
|
#undef INVALID_TO_GENERALIZE
|
|
|
|
/// Generalize the generic arguments of the given generic type.s
|
|
Type generalizeGenericArguments(NominalTypeDecl *decl, CanType type) {
|
|
assert(decl->isGenericContext());
|
|
auto origSubs = type->getContextSubstitutionMap(decl);
|
|
|
|
// Generalize all of the arguments.
|
|
auto origArgs = origSubs.getReplacementTypes();
|
|
SmallVector<Type, 4> newArgs;
|
|
for (auto origArg: origArgs) {
|
|
newArgs.push_back(generalizeComponentType(CanType(origArg)));
|
|
}
|
|
|
|
auto origSig = origSubs.getGenericSignature();
|
|
|
|
// Generalize all of the conformances.
|
|
// TODO: for abstract requirements, we might not generalize all
|
|
// arguments, and we may need to leave corresponding conformances
|
|
// concrete.
|
|
SmallVector<ProtocolConformanceRef, 4> newConformances;
|
|
for (const auto &req : origSig.getRequirements()) {
|
|
if (req.getKind() != RequirementKind::Conformance)
|
|
continue;
|
|
newConformances.push_back(
|
|
ProtocolConformanceRef::forAbstract(req.getFirstType(),
|
|
req.getProtocolDecl()));
|
|
}
|
|
|
|
auto newSubs = SubstitutionMap::get(origSig, newArgs, newConformances);
|
|
|
|
// Add any conformance requirements to the generic signature and
|
|
// remember the conformances we generalized.
|
|
auto origConformances = origSubs.getConformances();
|
|
size_t i = 0;
|
|
for (auto &origReq: origSig.getRequirements()) {
|
|
if (origReq.getKind() != RequirementKind::Conformance) continue;
|
|
auto origConformance = origConformances[i++];
|
|
|
|
auto newReq = origReq.subst(newSubs);
|
|
addedRequirements.push_back(newReq);
|
|
|
|
substConformances.insert({{newReq.getFirstType()->getCanonicalType(),
|
|
newReq.getProtocolDecl()},
|
|
origConformance});
|
|
}
|
|
|
|
// Build the new type.
|
|
return decl->getDeclaredInterfaceType().subst(newSubs);
|
|
}
|
|
|
|
/// Generalize the given type by preserving its top-level structure
|
|
/// but generalizing its component types.
|
|
Type generalizeComponentTypes(CanType type) {
|
|
return type.transformRec(
|
|
[&](TypeBase *componentType) -> std::optional<Type> {
|
|
// Ignore the top level.
|
|
if (componentType == type.getPointer())
|
|
return std::nullopt;
|
|
|
|
return generalizeComponentType(CanType(componentType));
|
|
});
|
|
}
|
|
|
|
Type generalizeComponentType(CanType origArg) {
|
|
// TODO: Abstract constraints (some P) introduce *existential*
|
|
// component types, which are not substitutable. Therefore, types
|
|
// containing them must be generalized preserving that structure
|
|
// rather than wholly substituted. They can appear in arbitrary
|
|
// positions, including within tuple, function, and metatype types,
|
|
// so we'll need to add cases for those to generalizeStructure
|
|
// above.
|
|
|
|
// Create a new generalization type parameter and record the
|
|
// substitution.
|
|
auto newParam = GenericTypeParamType::getType(/*depth*/ 0,
|
|
/*index*/ substTypes.size(),
|
|
ctx);
|
|
addedParameters.push_back(newParam);
|
|
|
|
substTypes.insert({CanType(newParam), origArg});
|
|
return newParam;
|
|
}
|
|
};
|
|
|
|
} // end anonymous namespace
|
|
|
|
ExistentialTypeGeneralization
|
|
ExistentialTypeGeneralization::get(Type rawType) {
|
|
assert(rawType->isAnyExistentialType());
|
|
|
|
// Canonicalize. We need to generalize the canonical shape of the
|
|
// type or else generalization parameters won't match up.
|
|
//
|
|
// TODO: in full generality, do we need to do *contextual*
|
|
// canonicalization in order to avoid introducing non-canonical
|
|
// parameters? (That is, do we need a contextual generic
|
|
// signature if given an interface type?)
|
|
CanType type = rawType->getCanonicalType();
|
|
|
|
Generalizer generalizer(type->getASTContext());
|
|
Type shape = generalizer.generalizeStructure(type);
|
|
auto subs = generalizer.getGeneralizationSubstitutions();
|
|
|
|
return {shape, subs};
|
|
}
|