Google Git
Sign in
fuchsia / third_party / swift / 0130407e2119dd1e302aaddbb7c1399647ebfc6f / . / lib / AST / GenericSignatureBuilder.cpp
blob: b3f69c4e23f78b9a339394d434a158243e195650 [file] [log] [blame]
//===--- 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/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 "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::PotentialArchetype PotentialArchetype;
typedef GenericSignatureBuilder::ConcreteConstraint ConcreteConstraint;
typedef GenericSignatureBuilder::EquivalenceClass EquivalenceClass;
} // 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;
#ifndef NDEBUG
/// Whether we've already finalized the builder.
bool finalized = false;
#endif
};
#pragma mark Requirement sources
bool RequirementSource::isAcceptableStorageKind(Kind kind,
StorageKind storageKind) {
switch (kind) {
case Explicit:
switch (storageKind) {
case StorageKind::RootArchetype:
case StorageKind::TypeRepr:
case StorageKind::RequirementRepr:
return true;
case StorageKind::ProtocolDecl:
case StorageKind::ProtocolConformance:
case StorageKind::AssociatedTypeDecl:
return false;
}
case Inferred:
switch (storageKind) {
case StorageKind::RootArchetype:
case StorageKind::TypeRepr:
return true;
case StorageKind::ProtocolDecl:
case StorageKind::ProtocolConformance:
case StorageKind::RequirementRepr:
case StorageKind::AssociatedTypeDecl:
return false;
}
case NestedTypeNameMatch:
switch (storageKind) {
case StorageKind::RootArchetype:
return true;
case StorageKind::TypeRepr:
case StorageKind::ProtocolDecl:
case StorageKind::ProtocolConformance:
case StorageKind::RequirementRepr:
case StorageKind::AssociatedTypeDecl:
return false;
}
case Parent:
switch (storageKind) {
case StorageKind::AssociatedTypeDecl:
return true;
case StorageKind::RootArchetype:
case StorageKind::TypeRepr:
case StorageKind::ProtocolDecl:
case StorageKind::ProtocolConformance:
case StorageKind::RequirementRepr:
return false;
}
case RequirementSignatureSelf:
case ProtocolRequirement:
switch (storageKind) {
case StorageKind::ProtocolDecl:
return true;
case StorageKind::RootArchetype:
case StorageKind::TypeRepr:
case StorageKind::ProtocolConformance:
case StorageKind::RequirementRepr:
case StorageKind::AssociatedTypeDecl:
return false;
}
case Superclass:
case Concrete:
switch (storageKind) {
case StorageKind::ProtocolConformance:
return true;
case StorageKind::RootArchetype:
case StorageKind::ProtocolDecl:
case StorageKind::TypeRepr:
case StorageKind::RequirementRepr:
case StorageKind::AssociatedTypeDecl:
return false;
}
}
}
const void *RequirementSource::getOpaqueStorage() const {
switch (storageKind) {
case StorageKind::RootArchetype:
return storage.rootArchetype;
case StorageKind::TypeRepr:
return storage.typeRepr;
case StorageKind::RequirementRepr:
return storage.requirementRepr;
case StorageKind::ProtocolConformance:
return storage.conformance;
case StorageKind::ProtocolDecl:
return storage.protocol;
case StorageKind::AssociatedTypeDecl:
return storage.assocType;
}
}
const void *RequirementSource::getExtraOpaqueStorage() const {
if (numTrailingObjects(OverloadToken<PotentialArchetype *>()) == 1)
return getTrailingObjects<PotentialArchetype *>()[0];
return nullptr;
}
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:
// 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;
}
}
bool RequirementSource::isDerivedViaConcreteConformance() const {
for (auto source = this; source; source = source->parent) {
switch (source->kind) {
case Explicit:
case Inferred:
case NestedTypeNameMatch:
case RequirementSignatureSelf:
return false;
case Parent:
case ProtocolRequirement:
continue;
case Superclass:
case Concrete:
return true;
}
}
return false;
}
bool RequirementSource::isSelfDerivedSource(PotentialArchetype *pa) const {
// If it's not a derived requirement, it's not self-derived.
if (!isDerivedRequirement()) return false;
// Collect the path of associated types from the root pa.
SmallVector<AssociatedTypeDecl *, 4> assocTypes;
PotentialArchetype *currentPA = nullptr;
for (auto source = this; source; source = source->parent) {
switch (source->kind) {
case RequirementSource::Parent:
assocTypes.push_back(source->getAssociatedType());
break;
case RequirementSource::NestedTypeNameMatch:
return false;
case RequirementSource::Explicit:
case RequirementSource::Inferred:
case RequirementSource::RequirementSignatureSelf:
currentPA = source->getRootPotentialArchetype();
break;
case RequirementSource::Concrete:
case RequirementSource::ProtocolRequirement:
case RequirementSource::Superclass:
break;
}
}
assert(currentPA && "Missing root potential archetype");
// Check whether anything of the potential archetypes in the path are
// equivalent to the end of the path.
auto rep = pa->getRepresentative();
for (auto assocType : reversed(assocTypes)) {
// Check whether this potential archetype is in the same equivalence class.
if (currentPA->getRepresentative() == rep) return true;
// Get the next nested type, but only if we've seen it before.
// FIXME: Feels hacky.
auto knownNested = currentPA->NestedTypes.find(assocType->getName());
if (knownNested == currentPA->NestedTypes.end()) return false;
currentPA = knownNested->second.front();
}
// FIXME: currentPA == pa?
return false;
}
#define REQUIREMENT_SOURCE_FACTORY_BODY( \
SourceKind, Parent, Storage, ExtraStorage, \
NumPotentialArchetypes) \
llvm::FoldingSetNodeID nodeID; \
Profile(nodeID, Kind::SourceKind, Parent, Storage, ExtraStorage); \
\
void *insertPos = nullptr; \
if (auto known = \
builder.Impl->RequirementSources.FindNodeOrInsertPos(nodeID, \
insertPos)) \
return known; \
\
unsigned size = \
totalSizeToAlloc<PotentialArchetype *>(NumPotentialArchetypes); \
void *mem = malloc(size); \
auto result = new (mem) RequirementSource(Kind::SourceKind, Parent, \
Storage); \
if (NumPotentialArchetypes > 0) \
result->getTrailingObjects<PotentialArchetype *>()[0] = ExtraStorage; \
builder.Impl->RequirementSources.InsertNode(result, insertPos); \
return result
const RequirementSource *RequirementSource::forAbstract(
PotentialArchetype *root) {
auto &builder = *root->getBuilder();
REQUIREMENT_SOURCE_FACTORY_BODY(Explicit, nullptr, root, nullptr, 0);
}
const RequirementSource *RequirementSource::forExplicit(
PotentialArchetype *root,
const TypeRepr *typeRepr) {
// If the type representation is NULL, we have an abstract requirement
// source.
if (!typeRepr)
return forAbstract(root);
auto &builder = *root->getBuilder();
REQUIREMENT_SOURCE_FACTORY_BODY(Explicit, nullptr, typeRepr, root, 1);
}
const RequirementSource *RequirementSource::forExplicit(
PotentialArchetype *root,
const RequirementRepr *requirementRepr) {
// If the requirement representation is NULL, we have an abstract requirement
// source.
if (!requirementRepr)
return forAbstract(root);
auto &builder = *root->getBuilder();
REQUIREMENT_SOURCE_FACTORY_BODY(Explicit, nullptr, requirementRepr, root, 1);
}
const RequirementSource *RequirementSource::forInferred(
PotentialArchetype *root,
const TypeRepr *typeRepr) {
auto &builder = *root->getBuilder();
REQUIREMENT_SOURCE_FACTORY_BODY(Inferred, nullptr, typeRepr, root, 1);
}
const RequirementSource *RequirementSource::forRequirementSignature(
PotentialArchetype *root,
ProtocolDecl *protocol) {
auto &builder = *root->getBuilder();
REQUIREMENT_SOURCE_FACTORY_BODY(RequirementSignatureSelf, nullptr, protocol,
root, 1);
}
const RequirementSource *RequirementSource::forNestedTypeNameMatch(
PotentialArchetype *root) {
auto &builder = *root->getBuilder();
REQUIREMENT_SOURCE_FACTORY_BODY(NestedTypeNameMatch, nullptr, root, nullptr,
0);
}
const RequirementSource *RequirementSource::viaAbstractProtocolRequirement(
GenericSignatureBuilder &builder,
ProtocolDecl *protocol) const {
REQUIREMENT_SOURCE_FACTORY_BODY(ProtocolRequirement, this, protocol,
nullptr, 0);
}
const RequirementSource *RequirementSource::viaSuperclass(
GenericSignatureBuilder &builder,
ProtocolConformance *conformance) const {
REQUIREMENT_SOURCE_FACTORY_BODY(Superclass, this, conformance, nullptr, 0);
}
const RequirementSource *RequirementSource::viaConcrete(
GenericSignatureBuilder &builder,
ProtocolConformance *conformance) const {
REQUIREMENT_SOURCE_FACTORY_BODY(Concrete, this, conformance, nullptr, 0);
}
const RequirementSource *RequirementSource::viaParent(
GenericSignatureBuilder &builder,
AssociatedTypeDecl *assocType) const {
REQUIREMENT_SOURCE_FACTORY_BODY(Parent, this, assocType, nullptr, 0);
}
#undef REQUIREMENT_SOURCE_FACTORY_BODY
PotentialArchetype *RequirementSource::getRootPotentialArchetype() const {
/// Find the root.
auto root = this;
while (auto parent = root->parent)
root = parent;
// If the root archetype is in extra storage, grab it from there.
if (root->numTrailingObjects(OverloadToken<PotentialArchetype *>()) == 1)
return root->getTrailingObjects<PotentialArchetype *>()[0];
// Otherwise, it's in inline storage.
assert(storageKind == StorageKind::RootArchetype);
return storage.rootArchetype;
}
ProtocolDecl *RequirementSource::getProtocolDecl() const {
switch (storageKind) {
case StorageKind::RootArchetype:
case StorageKind::TypeRepr:
case StorageKind::RequirementRepr:
return nullptr;
case StorageKind::ProtocolDecl:
return storage.protocol;
case StorageKind::ProtocolConformance:
if (storage.conformance)
return storage.conformance->getProtocol();
return nullptr;
case StorageKind::AssociatedTypeDecl:
return storage.assocType->getProtocol();
}
}
SourceLoc RequirementSource::getLoc() const {
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();
}
int RequirementSource::compare(const RequirementSource *other) const {
// Prefer the derived option, if there is one.
bool thisIsDerived = this->isDerivedRequirement();
bool otherIsDerived = other->isDerivedRequirement();
if (thisIsDerived != otherIsDerived)
return thisIsDerived ? -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 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::TypeRepr:
case StorageKind::RequirementRepr:
dumpSourceLoc(getLoc());
break;
case StorageKind::ProtocolDecl:
if (storage.protocol)
out << " (" << storage.protocol->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;
}
}
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 *>());
}
}
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();
}
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(!getResolvedAssociatedType() && "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;
}
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.concreteType->isEqual(superclass)) {
result = constraint;
if (!preferredPA || constraint.archetype == preferredPA)
return result;
}
}
return result;
}
bool GenericSignatureBuilder::updateRequirementSource(
const RequirementSource *&existingSource,
const RequirementSource *newSource) {
if (int result = newSource->compare(existingSource)) {
if (result < 0) {
existingSource = newSource;
return true;
}
return false;
}
assert(existingSource == newSource && "incomparable requirement sources");
return false;
}
const RequirementSource *GenericSignatureBuilder::resolveSuperConformance(
GenericSignatureBuilder::PotentialArchetype *pa,
ProtocolDecl *proto,
const RequirementSource *&protoSource) {
// 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());
updateRequirementSource(protoSource, 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);
}
// FIXME: this probably shouldn't exist, the potential archetype modelling of
// generic typealiases is fundamentally broken (aka they're not modelled at
// all), but some things with them mostly work, so we just maintain that,
// despite this causing crashes and weird behavior.
static ResolvedType forConcreteTypeFromGenericTypeAlias(Type t) {
return ResolvedType(t);
}
static ResolvedType forPotentialArchetype(PotentialArchetype *pa) {
return ResolvedType(pa);
}
static ResolvedType forNewTypeAlias(PotentialArchetype *pa) {
assert(pa->getParent() && pa->getTypeAliasDecl() &&
pa->getEquivalenceClassMembers().size() == 1 &&
"not a new typealias");
return ResolvedType(pa);
}
Type getType() const { return paOrT.dyn_cast<Type>(); }
PotentialArchetype *getPotentialArchetype() const {
return paOrT.dyn_cast<PotentialArchetype *>();
}
};
/// 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())
.getReplacement();
if (!concreteType) return;
// Add the same-type constraint.
auto nestedSource = superSource->viaParent(builder, assocType);
concreteType = superConformance->getDeclContext()
->mapTypeOutOfContext(concreteType);
builder.addSameTypeRequirement(nestedPA, concreteType, nestedSource);
}
/// 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 GenericSignatureBuilder::PotentialArchetype::addConformance(
ProtocolDecl *proto,
bool updateExistingSource,
const RequirementSource *source,
GenericSignatureBuilder &builder) {
auto rep = getRepresentative();
if (rep != this)
return rep->addConformance(proto, updateExistingSource, source, builder);
// Check whether we already know about this conformance.
auto known = ConformsTo.find(proto);
if (known != ConformsTo.end()) {
// We already have this requirement. Update the requirement source
// appropriately.
if (updateExistingSource)
builder.updateRequirementSource(known->second, source);
return false;
}
// Add this conformance.
auto inserted = ConformsTo.insert(std::make_pair(proto, source)).first;
// Determine whether there is a superclass constraint where the
// superclass conforms to this protocol.
auto superSource = getBuilder()->resolveSuperConformance(this, proto,
inserted->second);
// Check whether any associated types in this protocol resolve
// nested types of this potential archetype.
for (auto member : getProtocolMembers(proto)) {
auto assocType = dyn_cast<AssociatedTypeDecl>(member);
if (!assocType)
continue;
auto known = NestedTypes.find(assocType->getName());
if (known == NestedTypes.end())
continue;
// If the nested type was not already resolved, do so now.
if (!known->second.front()->getResolvedAssociatedType()) {
known->second.front()->resolveAssociatedType(assocType, builder);
// If there's a superclass constraint that conforms to the protocol,
// add the appropriate same-type relationship.
maybeAddSameTypeRequirementForNestedType(known->second.front(),
superSource,
builder);
continue;
}
// Otherwise, create a new potential archetype for this associated type
// and make it equivalent to the first potential archetype we encountered.
auto otherPA = new PotentialArchetype(this, assocType);
known->second.push_back(otherPA);
auto sameNamedSource = RequirementSource::forNestedTypeNameMatch(
known->second.front());
builder.addSameTypeRequirement(known->second.front(), otherPA,
sameNamedSource);
// If there's a superclass constraint that conforms to the protocol,
// add the appropriate same-type relationship.
maybeAddSameTypeRequirementForNestedType(otherPA, superSource, builder);
}
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;
}
/// 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()) {
// - by protocol, so t_n_m.`P.T` < t_n_m.`Q.T` (given P < Q)
auto protoa = aa->getProtocol();
auto protob = ab->getProtocol();
if (int compareProtocols
= ProtocolType::compareProtocols(&protoa, &protob))
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 (aa != ab)
return aa < ab ? -1 : +1;
} 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");
// - by protocol, so t_n_m.`P.T` < t_n_m.`Q.T` (given P < Q)
auto protoa =
aa->getDeclContext()->getAsProtocolOrProtocolExtensionContext();
auto protob =
ab->getDeclContext()->getAsProtocolOrProtocolExtensionContext();
if (int compareProtocols
= ProtocolType::compareProtocols(&protoa, &protob))
return compareProtocols;
if (aa != ab)
return aa < ab ? -1 : +1;
}
// 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");
}
/// Rebuild the given potential archetype based on anchors.
static GenericSignatureBuilder::PotentialArchetype*rebuildPotentialArchetypeAnchor(
GenericSignatureBuilder::PotentialArchetype *pa,
GenericSignatureBuilder &builder) {
if (auto parent = pa->getParent()) {
auto parentAnchor =
rebuildPotentialArchetypeAnchor(parent->getArchetypeAnchor(builder),
builder);
if (parent == parentAnchor) return pa;
if (auto assocType = pa->getResolvedAssociatedType())
return parentAnchor->getNestedType(assocType, builder);
return parentAnchor->getNestedType(pa->getNestedName(), builder);
}
return pa;
}
auto GenericSignatureBuilder::PotentialArchetype::getArchetypeAnchor(
GenericSignatureBuilder &builder)
-> PotentialArchetype * {
// Rebuild the potential archetype anchor for this type, so the equivalence
// class will contain the anchor.
(void)rebuildPotentialArchetypeAnchor(this, builder);
// Find the best archetype within this equivalence class.
PotentialArchetype *rep = getRepresentative();
auto anchor = rep;
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;
}
// 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())
.getReplacement();
} else {
witnessType = DependentMemberType::get(concreteParent, assocType);
}
builder.addSameTypeRequirement(nestedPA, witnessType, source,
[&](Type type1, Type type2) {
builder.getASTContext().Diags.diagnose(
source->getLoc(),
diag::requires_same_type_conflict,
nestedPA->isGenericParam(),
nestedPA->getDependentType(/*FIXME: */{ }, true),
type1, type2);
});
}
auto GenericSignatureBuilder::PotentialArchetype::getNestedType(
Identifier nestedName,
GenericSignatureBuilder &builder) -> PotentialArchetype * {
// If we already have a nested type with this name, return it.
if (!NestedTypes[nestedName].empty()) {
return NestedTypes[nestedName].front();
}
// Find the same nested type within the representative (unless we are
// the representative, of course!).
PotentialArchetype *repNested = nullptr;
auto rep = getRepresentative();
if (rep != this)
repNested = rep->getNestedType(nestedName, builder);
// Attempt to resolve this nested type to an associated type
// of one of the protocols to which the parent potential
// archetype conforms.
SmallVector<std::pair<ProtocolDecl *, const RequirementSource *>, 4>
conformsTo(rep->ConformsTo.begin(), rep->ConformsTo.end());
for (auto &conforms : conformsTo) {
auto proto = conforms.first;
for (auto member : proto->lookupDirect(nestedName)) {
PotentialArchetype *pa;
std::function<void(Type, Type)> diagnoseMismatch;
if (auto assocType = dyn_cast<AssociatedTypeDecl>(member)) {
// Resolve this nested type to this associated type.
pa = new PotentialArchetype(this, assocType);
diagnoseMismatch = [&](Type first, Type second) {
llvm_unreachable(
"associated type shouldn't result in new mismatches");
};
} else if (auto alias = dyn_cast<TypeAliasDecl>(member)) {
// Resolve this nested type to this type alias.
pa = new PotentialArchetype(this, alias);
diagnoseMismatch = [&](Type first, Type second) {
if (auto NAT = dyn_cast<NameAliasType>(first.getPointer())) {
if (NAT->getDecl() == member) {
// If we have typealias T = Foo and Foo is completely concrete
// (e.g. Array<Int?>), then the subst will leave the NameAliasType
// intact. However, this means, if there's a
// concrete-type-mismatch at the top level, the default error
// message will be "ProtocolName.T (aka Foo)", but the "T" bit is
// already in the error message so it's better to print only
// "Foo".
first = NAT->getSinglyDesugaredType();
}
}
builder.Diags.diagnose(member->getLoc(),
diag::protocol_typealias_conflict,
member->getName(), first, second);
};
// 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 (!alias->hasInterfaceType())
builder.getLazyResolver()->resolveDeclSignature(alias);
if (!alias->hasInterfaceType())
continue;
// The protocol typealias has an underlying type written in terms
// of the protocol's 'Self' type.
auto type = alias->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(
ResolvedType::forNewTypeAlias(pa),
builder.resolve(type),
RequirementSource::forNestedTypeNameMatch(pa),
diagnoseMismatch);
} else
continue;
// If we have resolved this nested type to more than one associated
// type, create same-type constraints between them.
llvm::TinyPtrVector<PotentialArchetype *> &nested =
NestedTypes[nestedName];
if (!nested.empty()) {
nested.push_back(pa);
// Produce a same-type constraint between the two same-named
// potential archetypes.
builder.addSameTypeRequirement(
pa, nested.front(),
RequirementSource::forNestedTypeNameMatch(pa),
diagnoseMismatch);
} else {
nested.push_back(pa);
if (repNested) {
builder.addSameTypeRequirement(
pa, repNested,
RequirementSource::forNestedTypeNameMatch(pa),
diagnoseMismatch);
}
}
// If there's a superclass constraint that conforms to the protocol,
// add the appropriate same-type relationship.
auto superSource = builder.resolveSuperConformance(this, conforms.first,
conforms.second);
maybeAddSameTypeRequirementForNestedType(pa, superSource, builder);
}
}
// We couldn't resolve the nested type yet, so create an
// unresolved associated type.
llvm::TinyPtrVector<PotentialArchetype *> &nested = NestedTypes[nestedName];
if (nested.empty()) {
nested.push_back(new PotentialArchetype(this, nestedName));
++builder.Impl->NumUnresolvedNestedTypes;
}
auto nestedPA = nested.front();
// We know something concrete about the parent PA, so we need to propagate
// that information to this new archetype.
if (isConcreteType()) {
for (auto equivT : rep->getEquivalenceClassMembers()) {
concretizeNestedTypeFromConcreteParent(
equivT, RequirementSource::forNestedTypeNameMatch(nestedPA),
nestedPA, builder,
[&](ProtocolDecl *proto) -> ProtocolConformanceRef {
auto depTy = nestedPA->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 nestedPA;
}
auto GenericSignatureBuilder::PotentialArchetype::getNestedType(
AssociatedTypeDecl *assocType,
GenericSignatureBuilder &builder) -> PotentialArchetype * {
// Add the requirement that this type conform to the protocol of the
// associated type. We treat this as "inferred" because it comes from the
// structure of the type---there will be an explicit or implied requirement
// somewhere else.
bool failed = builder.addConformanceRequirement(
this, assocType->getProtocol(),
RequirementSource::forInferred(this, nullptr));
(void)failed;
// Trigger the construction of nested types with this name.
auto fallback = getNestedType(assocType->getName(), builder);
// Find the nested type that resolved to this associated type.
for (const auto &nested : NestedTypes[assocType->getName()]) {
if (nested->getResolvedAssociatedType() == assocType) return nested;
}
assert(failed && "unable to find nested type that we know is there");
return fallback;
}
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();
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)) {
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 = ErrorType::get(superclass);
} else {
superclass = genericEnv->mapTypeIntoContext(
superclass,
builder.getLookupConformanceFn());
// 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 (const auto &conforms : representative->getConformsTo()) {
if (conforms.second->kind != RequirementSource::Superclass)
Protos.push_back(conforms.first);
}
// 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);
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.concreteType.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.concreteType.print(Out);
Out << " ";
if (!constraint.source->isDerivedRequirement())
Out << "*";
Out << "[";
constraint.source->print(Out, SrcMgr);
Out << "]";
}
}
// Print requirements.
if (!ConformsTo.empty()) {
Out << " : ";
bool First = true;
for (const auto &ProtoAndSource : ConformsTo) {
if (First)
First = false;
else
Out << " & ";
Out << ProtoAndSource.first->getName().str() << " ";
if (!ProtoAndSource.second->isDerivedRequirement())
Out << "*";
Out << "[";
ProtoAndSource.second->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);
}
GenericSignatureBuilder::GenericSignatureBuilder(GenericSignatureBuilder &&) = default;
GenericSignatureBuilder::~GenericSignatureBuilder() {
if (!Impl)
return;
for (auto PA : Impl->PotentialArchetypes)
delete PA;
}
std::function<GenericFunction>
GenericSignatureBuilder::getLookupConformanceFn() const {
return Impl->LookupConformance;
}
LazyResolver *GenericSignatureBuilder::getLazyResolver() const {
return Context.getLazyResolver();
}
auto GenericSignatureBuilder::resolveArchetype(Type type) -> PotentialArchetype * {
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());
if (!base)
return nullptr;
if (auto assocType = dependentMember->getAssocType())
return base->getNestedType(assocType, *this);
return base->getNestedType(dependentMember->getName(), *this);
}
return nullptr;
}
auto GenericSignatureBuilder::resolve(UnresolvedType paOrT,
bool hackTypeFromGenericTypeAlias)
-> ResolvedType {
auto pa = paOrT.dyn_cast<PotentialArchetype *>();
if (auto type = paOrT.dyn_cast<Type>()) {
pa = resolveArchetype(type);
if (!pa) {
if (hackTypeFromGenericTypeAlias)
return ResolvedType::forConcreteTypeFromGenericTypeAlias(type);
return ResolvedType::forConcreteType(type);
}
}
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");
// Recursively resolve the concrete type.
if (auto concrete = pa->getConcreteType())
return resolve(concrete);
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.
llvm::SmallPtrSet<ProtocolDecl *, 8> visited;
return addInheritedRequirements(GenericParam, PA, nullptr, visited);
}
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);
}
bool GenericSignatureBuilder::addConformanceRequirement(PotentialArchetype *PAT,
ProtocolDecl *Proto,
const RequirementSource *Source) {
llvm::SmallPtrSet<ProtocolDecl *, 8> Visited;
return addConformanceRequirement(PAT, Proto, Source, Visited);
}
/// Visit all of the types that show up in the list of inherited
/// types.
///
/// \returns true if any of the invocations of \c visitor returned true.
static bool visitInherited(
ArrayRef<TypeLoc> inheritedTypes,
llvm::function_ref<bool(Type, const TypeRepr *)> visitor) {
// Local function that (recursively) adds inherited types.
bool isInvalid = false;
std::function<void(Type, const TypeRepr *)> visitInherited;
visitInherited = [&](Type inheritedType, const TypeRepr *typeRepr) {
// Decompose protocol compositions.
auto composition = dyn_cast_or_null<CompositionTypeRepr>(typeRepr);
if (auto compositionType
= inheritedType->getAs<ProtocolCompositionType>()) {
unsigned index = 0;
for (auto protoType : compositionType->getProtocols()) {
if (composition && index < composition->getTypes().size())
visitInherited(protoType, composition->getTypes()[index]);
else
visitInherited(protoType, typeRepr);
++index;
}
return;
}
isInvalid |= visitor(inheritedType, typeRepr);
};
// Visit all of the inherited types.
for (auto inherited : inheritedTypes) {
visitInherited(inherited.getType(), inherited.getTypeRepr());
}
return isInvalid;
}
bool GenericSignatureBuilder::addConformanceRequirement(PotentialArchetype *PAT,
ProtocolDecl *Proto,
const RequirementSource *Source,
llvm::SmallPtrSetImpl<ProtocolDecl *> &Visited) {
// Add the requirement to the representative.
auto T = PAT->getRepresentative();
// Add the requirement, if we haven't done so already.
if (!T->addConformance(Proto, /*updateExistingSource=*/true, Source, *this))
return false;
bool inserted = Visited.insert(Proto).second;
assert(inserted);
(void) inserted;
SWIFT_DEFER {
Visited.erase(Proto);
};
auto concreteSelf = T->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 = Source->viaAbstractProtocolRequirement(*this, Proto);
for (auto rawReq : reqSig->getRequirements()) {
auto req = rawReq.subst(protocolSubMap);
assert(req && "substituting Self in requirement shouldn't fail");
if (addRequirement(*req, innerSource, Visited))
return true;
}
return false;
}
// Add all of the inherited protocol requirements, recursively.
if (auto resolver = getLazyResolver())
resolver->resolveInheritedProtocols(Proto);
if (addInheritedRequirements(Proto, PAT, Source, Visited))
return true;
// Add requirements for each of the associated types.
for (auto Member : getProtocolMembers(Proto)) {
if (auto AssocType = dyn_cast<AssociatedTypeDecl>(Member)) {
// Add requirements placed directly on this associated type.
auto AssocPA = T->getNestedType(AssocType, *this);
if (AssocPA != T) {
if (addInheritedRequirements(AssocType, AssocPA, Source, Visited))
return true;
}
if (auto WhereClause = AssocType->getTrailingWhereClause()) {
auto innerSource = Source->viaAbstractProtocolRequirement(*this, Proto);
for (auto &req : WhereClause->getRequirements()) {
addRequirement(&req, innerSource, &protocolSubMap);
}
}
} else if (auto TypeAlias = dyn_cast<TypeAliasDecl>(Member)) {
// FIXME: this should check that the typealias is makes sense (e.g. has
// the same/compatible type as typealiases in parent protocols) and
// set-up any same type requirements required. Forcing the PA to be
// created with getNestedType is currently worse than useless due to the
// 'recursive decl validation' FIXME in that function: it creates an
// unresolved PA that prints an error later.
(void)TypeAlias;
}
}
return false;
}
bool GenericSignatureBuilder::addLayoutRequirement(PotentialArchetype *PAT,
LayoutConstraint Layout,
const RequirementSource *Source) {
// Add the requirement to the representative.
auto T = PAT->getRepresentative();
if (T->Layout) {
if (T->Layout == Layout) {
// Update the source.
T->LayoutSource = Source;
return false;
}
// There is an existing layout constraint for this archetype.
Diags.diagnose(Source->getLoc(), diag::mutiple_layout_constraints,
Layout, T->Layout);
Diags.diagnose(T->LayoutSource->getLoc(),
diag::previous_layout_constraint, T->Layout);
T->setInvalid();
return true;
}
T->Layout = Layout;
T->LayoutSource = Source;
return false;
}
bool 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 &conforms : T->ConformsTo) {
if (auto superSource = resolveSuperConformance(T, conforms.first,
conforms.second)) {
for (auto req : getProtocolMembers(conforms.first)) {
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();
return false;
}
// 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, nullptr)) {
equivClass->superclass = superclass;
// We've strengthened the bound, so update superclass conformances.
updateSuperclassConformances();
return false;
}
return false;
}
bool GenericSignatureBuilder::addSuperclassRequirement(
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.
return updateSuperclass(T, superclass, source);
}
void GenericSignatureBuilder::PotentialArchetype::addSameTypeConstraint(
PotentialArchetype *otherPA,
const RequirementSource *source) {
// If the types are the same, there's nothing to do.
if (this == otherPA) return;
// Update the same-type constraints of this PA to reference the other PA.
auto insertedIntoThis = SameTypeConstraints.insert({otherPA, source});
if (!insertedIntoThis.second) {
getBuilder()->updateRequirementSource(insertedIntoThis.first->second,
source);
}
// Update the same-type constraints of the other PA to reference this PA.
auto insertedIntoOther = otherPA->SameTypeConstraints.insert({this, source});
if (!insertedIntoOther.second) {
getBuilder()->updateRequirementSource(insertedIntoOther.first->second,
source);
}
}
bool 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 false;
// 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 any concrete constraints.
Type concrete1 = T1->getConcreteType();
Type concrete2 = T2->getConcreteType();
// FIXME: This seems early.
if (concrete1 && concrete2) {
bool mismatch = addSameTypeRequirement(
concrete1, concrete2, Source, [&](Type type1, Type type2) {
Diags.diagnose(Source->getLoc(),
diag::requires_same_type_conflict,
T1->isGenericParam(),
T1->getDependentType(/*FIXME: */{ }, true), type1,
type2);
});
if (mismatch) return true;
}
// Don't mark requirements as redundant if they come from one of our
// child archetypes. This is a targeted fix -- more general cases
// continue to break. In general, we need to detect cycles in the
// archetype graph and not propagate requirement source information
// along back edges.
bool updateExistingSource = true;
auto T2Parent = T2;
while (T2Parent != nullptr) {
if (T2Parent->getRepresentative() == T1)
updateExistingSource = false;
T2Parent = T2Parent->getParent();
}
// Another targeted fix -- don't drop conformances from generic
// parameters.
if (T1->getParent() == nullptr)
updateExistingSource = false;
// 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-to-concrete requirements.
if (equivClass2 && equivClass2->concreteType) {
if (!equivClass->concreteType)
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->concreteTypeConstraints.end(),
equivClass2->superclassConstraints.begin(),
equivClass2->superclassConstraints.end());
}
// Add all of the protocol conformance requirements of T2 to T1.
for (auto conforms : T2->ConformsTo) {
T1->addConformance(conforms.first, updateExistingSource,
conforms.second, *this);
}
// Recursively merge the associated types of T2 into T1.
for (auto equivT2 : equivClass2Members) {
for (auto T2Nested : equivT2->NestedTypes) {
auto T1Nested = T1->getNestedType(T2Nested.first, *this);
if (addSameTypeRequirement(
T1Nested, T2Nested.second.front(),
RequirementSource::forNestedTypeNameMatch(T1Nested),
[&](Type type1, Type type2) {
Diags.diagnose(Source->getLoc(),
diag::requires_same_type_conflict,
T1Nested->isGenericParam(),
T1Nested->getDependentType(/*FIXME: */{ }, true),
type1, type2);
}))
return true;
}
}
return false;
}
bool 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) {
bool mismatch = addSameTypeRequirement(
equivClass->concreteType, Concrete, Source,
[&](Type type1, Type type2) {
Diags.diagnose(Source->getLoc(),
diag::requires_same_type_conflict,
T->isGenericParam(),
T->getDependentType(/*FIXME: */{ }, true), type1,
type2);
});
if (mismatch) return true;
// Nothing more to do; the types matched.
return false;
}
// 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 &conforms : rep->getConformsTo()) {
auto protocol = conforms.first;
auto conformance =
getLookupConformanceFn()(depTy, Concrete,
protocol->getDeclaredInterfaceType()
->castTo<ProtocolType>());
if (!conformance) {
Diags.diagnose(Source->getLoc(),
diag::requires_generic_param_same_type_does_not_conform,
Concrete, protocol->getName());
return true;
}
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);
updateRequirementSource(conforms.second, 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 false;
}
bool 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, diagnoseMismatch);
return !failed;
}
} matcher(*this, source, type1, type2, diagnoseMismatch);
return !matcher.match(type1, type2);
}
bool GenericSignatureBuilder::addSameTypeRequirement(
UnresolvedType paOrT1,
UnresolvedType paOrT2,
FloatingRequirementSource source) {
return addSameTypeRequirement(resolve(paOrT1), resolve(paOrT2), source);
}
bool GenericSignatureBuilder::addSameTypeRequirement(
UnresolvedType paOrT1, UnresolvedType paOrT2,
FloatingRequirementSource source,
llvm::function_ref<void(Type, Type)> diagnoseMismatch) {
return addSameTypeRequirement(resolve(paOrT1), resolve(paOrT2), source,
diagnoseMismatch);
}
bool GenericSignatureBuilder::addSameTypeRequirement(ResolvedType paOrT1,
ResolvedType paOrT2,
FloatingRequirementSource source) {
return addSameTypeRequirement(paOrT1, paOrT2, source,
[&](Type type1, Type type2) {
Diags.diagnose(source.getLoc(), diag::requires_same_concrete_type,
type1, type2);
});
}
bool GenericSignatureBuilder::addSameTypeRequirement(
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();
// FIXME: Drop this protocol.
pa->addConformance(proto, /*updateExistingSource=*/true, 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();
}
bool GenericSignatureBuilder::addInheritedRequirements(
TypeDecl *decl,
PotentialArchetype *pa,
const RequirementSource *parentSource,
llvm::SmallPtrSetImpl<ProtocolDecl *> &visited) {
if (isa<AssociatedTypeDecl>(decl) &&
decl->hasInterfaceType() &&
decl->getInterfaceType()->is<ErrorType>())
return false;
// Walk the 'inherited' list to identify requirements.
if (auto resolver = getLazyResolver())
resolver->resolveInheritanceClause(decl);
return visitInherited(
decl->getInherited(),
[&](Type inheritedType, const TypeRepr *typeRepr) -> bool {
// Local function to get the source.
auto getSource = [&] {
if (parentSource) {
if (auto assocType = dyn_cast<AssociatedTypeDecl>(decl)) {
// FIXME: Pass along the typeRepr!
auto proto = assocType->getProtocol();
return parentSource->viaAbstractProtocolRequirement(*this, proto);
}
// FIXME: Pass along the typeRepr.
auto proto = cast<ProtocolDecl>(decl);
return parentSource->viaAbstractProtocolRequirement(*this, proto);
}
// Explicit requirement.
if (typeRepr)
return RequirementSource::forExplicit(pa, typeRepr);
// An abstract explicit requirement.
return RequirementSource::forAbstract(pa);
};
// Protocol requirement.
if (auto protocolType = inheritedType->getAs<ProtocolType>()) {
if (visited.count(protocolType->getDecl())) {
markPotentialArchetypeRecursive(pa, protocolType->getDecl(),
getSource());
return true;
}
return addConformanceRequirement(pa, protocolType->getDecl(), getSource(),
visited);
}
// Superclass requirement.
if (inheritedType->getClassOrBoundGenericClass()) {
return addSuperclassRequirement(pa, inheritedType, getSource());
}
// Note: anything else is an error, to be diagnosed later.
return false;
});
}
bool GenericSignatureBuilder::addRequirement(const RequirementRepr *Req,
const RequirementSource *source,
const SubstitutionMap *subMap) {
auto localSource = source ? FloatingRequirementSource(source)
: FloatingRequirementSource::forExplicit(Req);
auto subst = [&](Type t) {
if (subMap)
return t.subst(*subMap);
return t;
};
switch (Req->getKind()) {
case RequirementReprKind::LayoutConstraint: {
// FIXME: Need to do something here.
PotentialArchetype *PA = resolveArchetype(subst(Req->getSubject()));
if (!PA) {
// FIXME: Poor location information.
// FIXME: Delay diagnostic until after type validation?
Diags.diagnose(Req->getColonLoc(), diag::requires_not_suitable_archetype,
0, Req->getSubjectLoc(), 0);
return true;
}
if (addLayoutRequirement(PA, Req->getLayoutConstraint(),
localSource.getSource(PA)))
return true;
return false;
}
case RequirementReprKind::TypeConstraint: {
PotentialArchetype *PA = resolveArchetype(subst(Req->getSubject()));
if (!PA) {
// FIXME: Poor location information.
// FIXME: Delay diagnostic until after type validation?
Diags.diagnose(Req->getColonLoc(), diag::requires_not_suitable_archetype,
0, Req->getSubjectLoc(), 0);
return true;
}
// Check whether this is a supertype requirement.
if (Req->getConstraint()->getClassOrBoundGenericClass()) {
return addSuperclassRequirement(PA, Req->getConstraint(),
localSource.getSource(PA));
}
SmallVector<ProtocolDecl *, 4> ConformsTo;
if (!Req->getConstraint()->isExistentialType(ConformsTo)) {
// FIXME: Diagnose this failure here, rather than over in type-checking.
return true;
}
// Add each of the protocols.
for (auto Proto : ConformsTo)
if (addConformanceRequirement(PA, Proto, localSource.getSource(PA)))
return true;
return false;
}
case RequirementReprKind::SameType:
// Require that at least one side of the requirement contain a type
// parameter.
if (!Req->getFirstType()->hasTypeParameter() &&
!Req->getSecondType()->hasTypeParameter()) {
Diags.diagnose(Req->getEqualLoc(), diag::requires_no_same_type_archetype)
.highlight(Req->getFirstTypeLoc().getSourceRange())
.highlight(Req->getSecondTypeLoc().getSourceRange());
return true;
}
return addRequirement(Requirement(RequirementKind::SameType,
subst(Req->getFirstType()),
subst(Req->getSecondType())),
localSource);
}
llvm_unreachable("Unhandled requirement?");
}
bool GenericSignatureBuilder::addRequirement(const Requirement &req,
FloatingRequirementSource source) {
llvm::SmallPtrSet<ProtocolDecl *, 8> Visited;
return addRequirement(req, source, Visited);
}
bool GenericSignatureBuilder::addRequirement(
const Requirement &req, FloatingRequirementSource source,
llvm::SmallPtrSetImpl<ProtocolDecl *> &Visited) {
switch (req.getKind()) {
case RequirementKind::Superclass: {
// FIXME: Diagnose this.
PotentialArchetype *pa = resolveArchetype(req.getFirstType());
if (!pa) return false;
assert(req.getSecondType()->getClassOrBoundGenericClass());
return addSuperclassRequirement(pa, req.getSecondType(),
source.getSource(pa));
}
case RequirementKind::Layout: {
// FIXME: Diagnose this.
PotentialArchetype *pa = resolveArchetype(req.getFirstType());
if (!pa) return false;
return addLayoutRequirement(pa, req.getLayoutConstraint(),
source.getSource(pa));
}
case RequirementKind::Conformance: {
// FIXME: Diagnose this.
PotentialArchetype *pa = resolveArchetype(req.getFirstType());
if (!pa) return false;
SmallVector<ProtocolDecl *, 4> conformsTo;
(void)req.getSecondType()->isExistentialType(conformsTo);
// Add each of the protocols.
for (auto proto : conformsTo) {
if (Visited.count(proto)) {
markPotentialArchetypeRecursive(pa, proto, source.getSource(pa));
continue;
}
if (addConformanceRequirement(pa, proto, source.getSource(pa), Visited))
return true;
}
return false;
}
case RequirementKind::SameType:
return addSameTypeRequirement(
req.getFirstType(), req.getSecondType(), source,
[&](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 {
GenericSignatureBuilder &Builder;
TypeRepr *typeRepr;
public:
InferRequirementsWalker(GenericSignatureBuilder &builder,
TypeRepr *typeRepr)
: Builder(builder), typeRepr(typeRepr) { }
Action walkToTypePost(Type ty) override {
auto boundGeneric = ty->getAs<BoundGenericType>();
if (!boundGeneric)
return Action::Continue;
auto genericSig = boundGeneric->getDecl()->getGenericSignature();
if (!genericSig)
return Action::Stop;
/// Retrieves the type substitution.
auto args = boundGeneric->getGenericArgs();
auto genericSigDepth =
genericSig->getInnermostGenericParams().front()->getDepth();
auto getTypeSubstitution = [&](SubstitutableType *dependentType) -> Type {
if (auto gp = dyn_cast<GenericTypeParamType>(dependentType)) {
if (gp->getDepth() == genericSigDepth)
return args[gp->getIndex()];
return gp;
}
return dependentType;
};
// Handle the requirements.
// FIXME: Inaccurate TypeReprs.
auto source = FloatingRequirementSource::forInferred(typeRepr);
for (const auto &rawReq : genericSig->getRequirements()) {
if (auto req = rawReq.subst(getTypeSubstitution,
Builder.getLookupConformanceFn()))
Builder.addRequirement(*req, source);
}
return Action::Continue;
}
};
void GenericSignatureBuilder::inferRequirements(TypeLoc type) {
if (!type.getType())
return;
// FIXME: Crummy source-location information.
InferRequirementsWalker walker(*this, type.getTypeRepr());
type.getType().walk(walker);
}
void GenericSignatureBuilder::inferRequirements(ParameterList *params,
GenericParamList *genericParams) {
if (genericParams == nullptr)
return;
for (auto P : *params)
inferRequirements(P->getTypeLoc());
}
/// 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 (const auto &conforms : pa->getParent()->getConformsTo()) {
auto proto = conforms.first;
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();
}
void
GenericSignatureBuilder::finalize(SourceLoc loc,
ArrayRef<GenericTypeParamType *> genericParams,
bool allowConcreteGenericParams) {
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)) {
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)) {
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->concreteType);
}
archetype->RecursiveConcreteType = true;
} else {
checkRedundantConcreteTypeConstraints(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 {
checkRedundantSuperclassConstraints(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->getParent() != nullptr) continue;
SourceLoc constraintLoc;
for (const auto &sameType : pa->getSameTypeConstraints()) {
SourceLoc sameTypeLoc = sameType.second->getLoc();
if (sameTypeLoc.isInvalid()) continue;
if (sameType.first == other) {
constraintLoc = sameTypeLoc;
break;
}
if (constraintLoc.isInvalid())
constraintLoc = sameTypeLoc;
}
if (constraintLoc.isInvalid())
constraintLoc = loc;
Diags.diagnose(constraintLoc,
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));
});
}
}
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;
}
namespace swift {
bool operator<(const ConcreteConstraint &lhs, const ConcreteConstraint &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;
}
bool operator==(const ConcreteConstraint &lhs, const ConcreteConstraint &rhs){
return lhs.archetype == rhs.archetype &&
lhs.concreteType->isEqual(rhs.concreteType) &&
lhs.source == rhs.source;
}
}
ConcreteConstraint GenericSignatureBuilder::checkConstraintList(
ArrayRef<GenericTypeParamType *> genericParams,
std::vector<ConcreteConstraint> &constraints,
llvm::function_ref<bool(const ConcreteConstraint &)>
isSuitableRepresentative,
llvm::function_ref<ConstraintRelation(Type)>
checkConstraint,
Optional<Diag<unsigned, Type, Type, Type>>
conflictingDiag,
Diag<Type, Type> redundancyDiag,
Diag<bool, Type, Type> otherNoteDiag) {
// Remove self-derived constraints.
constraints.erase(
std::remove_if(constraints.begin(), constraints.end(),
[&](const ConcreteConstraint &constraint) {
return constraint.source->isSelfDerivedSource(
constraint.archetype);
}),
constraints.end());
// Sort the constraints, so we get a deterministic ordering of diagnostics.
llvm::array_pod_sort(constraints.begin(), constraints.end());
// Find a representative constraint.
Optional<ConcreteConstraint> 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 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;
}
// 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->isDerivedRequirement(),
representativeConstraint->archetype->
getDependentType(genericParams, /*allowUnresolved=*/true),
representativeConstraint->concreteType);
};
// 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.concreteType)) {
case ConstraintRelation::Unrelated:
continue;
case ConstraintRelation::Conflicting: {
// Figure out what kind of subject we have; it will affect the
// diagnostic.
auto getSubjectType =
[&](PotentialArchetype *T) -> std::pair<unsigned, Type> {
auto subjectType = T->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,
constraint.concreteType,
representativeConstraint->concreteType);
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,
representativeConstraint->concreteType,
constraint.concreteType);
diagnosedConflictingRepresentative = true;
break;
}
break;
}
case ConstraintRelation::Redundant:
// If this requirement is not derived (but has a useful location),
// complain that it is redundant.
if (!constraint.source->isDerivedRequirement() &&
constraint.source->getLoc().isValid()) {
Diags.diagnose(constraint.source->getLoc(),
redundancyDiag,
constraint.archetype->getDependentType(
genericParams, /*allowUnresolved=*/true),
constraint.concreteType);
noteRepresentativeConstraint();
}
break;
}
}
return *representativeConstraint;
}
void GenericSignatureBuilder::checkRedundantConcreteTypeConstraints(
ArrayRef<GenericTypeParamType *> genericParams,
PotentialArchetype *representative) {
auto equivClass = representative->getOrCreateEquivalenceClass();
assert(equivClass->concreteType && "No concrete type to check");
checkConstraintList(
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::checkRedundantSuperclassConstraints(
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(
genericParams, equivClass->superclassConstraints,
[&](const ConcreteConstraint &constraint) {
return constraint.concreteType->isEqual(equivClass->superclass);
},
[&](Type superclass) {
// If this class is a superclass of the "best"
if (superclass->isExactSuperclassOf(equivClass->superclass, nullptr))
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,
nullptr)) {
if (auto existing = equivClass->findAnyConcreteConstraintAsWritten(
representativeConstraint.archetype)) {
Diags.diagnose(existing->source->getLoc(), diag::type_does_not_inherit,
existing->archetype->getDependentType(
genericParams,
/*allowUnresolved=*/true),
existing->concreteType, 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.concreteType);
if (auto existing = equivClass->findAnyConcreteConstraintAsWritten(
representativeConstraint.archetype)) {
Diags.diagnose(existing->source->getLoc(),
diag::same_type_redundancy_here,
existing->source->isDerivedRequirement(),
existing->archetype->getDependentType(
genericParams,
/*allowUnresolved=*/true),
existing->concreteType);
}
}
}
}
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 nested potential archetypes.
for (const auto &nested : pa->getNestedTypes()) {
for (auto nestedPA : nested.second) {
if (visited.insert(nestedPA).second) {
stack.push_back(nestedPA);
}
}
}
}
}
/// 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 &sameType : pa->getSameTypeConstraints()) {
switch (sameType.second->kind) {
case RequirementSource::Explicit:
case RequirementSource::Inferred:
case RequirementSource::RequirementSignatureSelf:
// Skip explicit constraints.
continue;
case RequirementSource::Concrete:
case RequirementSource::NestedTypeNameMatch:
case RequirementSource::Parent:
case RequirementSource::ProtocolRequirement:
case RequirementSource::Superclass:
break;
}
sameTypeDFS(sameType.first, component, paToComponent);
// If this type is better than the anchor, use it for the anchor.
if (compareDependentTypes(&sameType.first, &anchor) < 0)
anchor = sameType.first;
}
return anchor;
}
namespace {
/// Describes a component in the (implied) same-type constraint graph.
struct SameTypeComponent {
/// The potential archetype that acts as the anchor for this component.
PotentialArchetype *anchor;
/// The (best) requirement source within the component that makes the
/// potential archetypes in this component equivalent to the concrete type.
const RequirementSource *concreteTypeSource;
/// The (best) requirement source within the component that introduces
/// the superclass constraint.
const RequirementSource *superclassSource;
friend bool operator<(const SameTypeComponent &lhs,
const SameTypeComponent &rhs) {
return compareDependentTypes(&lhs.anchor, &rhs.anchor) < 0;
}
};
}
/// Computes the ordered set of archetype anchors required to form a minimum
/// spanning tree among the connected components formed by only the implied
/// 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 SmallVector<SameTypeComponent, 2> getSameTypeComponents(
PotentialArchetype *rep) {
llvm::SmallDenseMap<PotentialArchetype *, unsigned> paToComponent;
SmallVector<SameTypeComponent, 2> components;
for (auto pa : rep->getEquivalenceClassMembers()) {
// If we've already seen this potential archetype, there's nothing else to
// do.
if (paToComponent.count(pa) != 0) continue;
// Find all of the potential archetypes within this connected component.
auto anchor = sameTypeDFS(pa, components.size(), paToComponent);
// Record the anchor.
components.push_back({anchor, nullptr, nullptr});
}
// If there is a concrete type, figure out the best concrete type anchor
// per component.
auto equivClass = rep->getOrCreateEquivalenceClass();
for (const auto &concrete : equivClass->concreteTypeConstraints) {
// Dig out the component associated with constraint.
assert(paToComponent.count(concrete.archetype) > 0);
auto &component = components[paToComponent[concrete.archetype]];
// 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;
}
// If there is a superclass and no concrete type, figure out the best
// superclass source per component.
if (equivClass->superclass && !equivClass->concreteType) {
for (const auto &superclass : equivClass->superclassConstraints) {
// Dig out the component associated with constraint.
assert(paToComponent.count(superclass.archetype) > 0);
auto &component = components[paToComponent[superclass.archetype]];
// If it has a better source than we'd seen before for this component,
// keep it.
auto &bestSuperclassSource = component.superclassSource;
if (!bestSuperclassSource ||
superclass.source->compare(bestSuperclassSource) < 0)
bestSuperclassSource = superclass.source;
}
}
// Sort the components.
llvm::array_pod_sort(components.begin(), components.end());
return components;
}
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);
// Track the anchors for each of the implied connected components within the
// equivalence class of each representative.
llvm::DenseMap<PotentialArchetype *, SmallVector<SameTypeComponent, 2>>
sameTypeComponents;
auto getSameTypeComponents =
[&](PotentialArchetype *rep) -> ArrayRef<SameTypeComponent> {
assert(rep->getRepresentative() == rep);
auto known = sameTypeComponents.find(rep);
if (known != sameTypeComponents.end())
return known->second;
return sameTypeComponents.insert(
{rep, ::getSameTypeComponents(rep) }).first->second;
};
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 components = getSameTypeComponents(rep);
auto knownAnchor = std::find_if(components.begin(),
components.end(),
[&](const SameTypeComponent &component) {
return component.anchor == archetype;
});
std::function<void()> deferredSameTypeRequirement;
if (knownAnchor != components.end()) {
// If this equivalence class is bound to a concrete type, equate the
// anchor with a concrete type.
if (Type concreteType = rep->getConcreteType()) {
auto source =
knownAnchor->concreteTypeSource
? knownAnchor->concreteTypeSource
: RequirementSource::forAbstract(archetype);
f(RequirementKind::SameType, archetype, concreteType, source);
continue;
}
// If we have a superclass, produce a superclass requirement
if (Type superclass = rep->getSuperclass()) {
f(RequirementKind::Superclass, archetype, superclass,
knownAnchor->superclassSource
? knownAnchor->superclassSource
: RequirementSource::forAbstract(archetype));
}
// If we're at the last anchor in the component, do nothing;
auto nextAnchor = knownAnchor;
++nextAnchor;
if (nextAnchor != components.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, this] {
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 layout constraint, produce a layout requirement.
if (LayoutConstraint Layout = archetype->getLayout()) {
f(RequirementKind::Layout, archetype, Layout,
archetype->getLayoutSource());
}
// Enumerate conformance requirements.
SmallVector<ProtocolDecl *, 4> protocols;
DenseMap<ProtocolDecl *, const RequirementSource *> protocolSources;
for (const auto &conforms : rep->getConformsTo()) {
protocols.push_back(conforms.first);
assert(protocolSources.count(conforms.first) == 0 &&
"redundant protocol requirement?");
protocolSources.insert({conforms.first, 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);
for (auto &reqt : sig->getRequirements()) {
addRequirement(reqt, FloatingRequirementSource::forAbstract());
}
}
/// 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.
if (source->isDerivedRequirement()) 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;
}