Google Git
Sign in
fuchsia / third_party / swift / b00b789f64adb6b561159c764c0c5b4165f06743 / . / lib / AST / ArchetypeBuilder.cpp
blob: ddc245bd1b761cdf4c7b3888016dff20eaacf605 [file] [log] [blame]
//===--- ArchetypeBuilder.cpp - Generic Requirement Builder ---------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// 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/ArchetypeBuilder.h"
#include "swift/AST/ASTContext.h"
#include "swift/AST/DiagnosticsSema.h"
#include "swift/AST/DiagnosticEngine.h"
#include "swift/AST/Module.h"
#include "swift/AST/ParameterList.h"
#include "swift/AST/ProtocolConformance.h"
#include "swift/AST/TypeRepr.h"
#include "swift/AST/TypeWalker.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;
using NestedType = ArchetypeType::NestedType;
void RequirementSource::dump(SourceManager *srcMgr) const {
dump(llvm::errs(), srcMgr);
}
void RequirementSource::dump(llvm::raw_ostream &out,
SourceManager *srcMgr) const {
switch (getKind()) {
case Explicit:
out << "explicit";
break;
case Redundant:
out << "redundant";
break;
case Protocol:
out << "protocol";
break;
case Inferred:
out << "inferred";
break;
case OuterScope:
out << "outer";
break;
}
if (srcMgr && getLoc().isValid()) {
out << " @ ";
getLoc().dump(*srcMgr);
}
}
/// Update the recorded requirement source when a new requirement
/// source provides the same requirement.
static void updateRequirementSource(RequirementSource &source,
const RequirementSource &newSource) {
switch (newSource.getKind()) {
case RequirementSource::Explicit:
case RequirementSource::Redundant:
// Nothing to do; the new source is always redundant.
switch (source.getKind()) {
case RequirementSource::Explicit:
case RequirementSource::Redundant:
// Nothing to do.
break;
case RequirementSource::Inferred:
case RequirementSource::Protocol:
// Mark the original source as redundant.
source = RequirementSource(RequirementSource::Redundant,
newSource.getLoc());
break;
case RequirementSource::OuterScope:
// Leave the outer scope in place.
break;
}
break;
case RequirementSource::Inferred:
// A new inferred source will never override an existing source.
break;
case RequirementSource::Protocol: {
switch (source.getKind()) {
case RequirementSource::Explicit:
case RequirementSource::Redundant:
// The original source is redundant.
source.setKind(RequirementSource::Redundant);
break;
case RequirementSource::Protocol:
case RequirementSource::OuterScope:
// Keep the original source.
break;
case RequirementSource::Inferred:
// Replace the inferred source with the protocol source.
source = newSource;
break;
}
break;
}
case RequirementSource::OuterScope:
// An outer-scope source always overrides an existing source.
source = newSource;
break;
}
}
/// The identifying information for a generic parameter.
namespace {
struct GenericTypeParamKey {
unsigned Depth : 16;
unsigned Index : 16;
static GenericTypeParamKey forDecl(GenericTypeParamDecl *d) {
return {d->getDepth(), d->getIndex()};
}
static GenericTypeParamKey forType(GenericTypeParamType *t) {
return {t->getDepth(), t->getIndex()};
}
};
}
namespace llvm {
template<>
struct DenseMapInfo<GenericTypeParamKey> {
static inline GenericTypeParamKey getEmptyKey() { return {0xFFFF, 0xFFFF}; }
static inline GenericTypeParamKey getTombstoneKey() { return {0xFFFE, 0xFFFE}; }
static inline unsigned getHashValue(GenericTypeParamKey k) {
return DenseMapInfo<unsigned>::getHashValue(k.Depth << 16 | k.Index);
}
static bool isEqual(GenericTypeParamKey a, GenericTypeParamKey b) {
return a.Depth == b.Depth && a.Index == b.Index;
}
};
}
struct ArchetypeBuilder::Implementation {
/// A mapping from generic parameters to the corresponding potential
/// archetypes.
llvm::MapVector<GenericTypeParamKey, PotentialArchetype*> PotentialArchetypes;
/// A vector containing all of the archetypes, expanded out.
/// FIXME: This notion should go away, because it's impossible to expand
/// out "all" archetypes
SmallVector<ArchetypeType *, 4> AllArchetypes;
/// A vector containing the same-type requirements introduced into the
/// system.
SmallVector<SameTypeRequirement, 4> SameTypeRequirements;
/// 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;
};
ArchetypeBuilder::PotentialArchetype::~PotentialArchetype() {
for (const auto &nested : NestedTypes) {
for (auto pa : nested.second) {
if (pa != this)
delete pa;
}
}
}
void ArchetypeBuilder::PotentialArchetype::buildFullName(
bool forDebug,
SmallVectorImpl<char> &result) const {
if (auto parent = getParent()) {
parent->buildFullName(forDebug, result);
// When building the name for debugging purposes, include the
// protocol into which the associated type was resolved.
if (forDebug) {
if (auto assocType = getResolvedAssociatedType()) {
result.push_back('[');
result.push_back('.');
result.append(assocType->getProtocol()->getName().str().begin(),
assocType->getProtocol()->getName().str().end());
result.push_back(']');
}
}
result.push_back('.');
}
result.append(getName().str().begin(), getName().str().end());
}
Identifier ArchetypeBuilder::PotentialArchetype::getName() const {
if (auto assocType = NameOrAssociatedType.dyn_cast<AssociatedTypeDecl *>())
return assocType->getName();
if (auto typeAlias = NameOrAssociatedType.dyn_cast<TypeAliasDecl *>())
return typeAlias->getName();
return NameOrAssociatedType.get<Identifier>();
}
std::string ArchetypeBuilder::PotentialArchetype::getFullName() const {
llvm::SmallString<64> result;
buildFullName(false, result);
return result.str().str();
}
std::string ArchetypeBuilder::PotentialArchetype::getDebugName() const {
llvm::SmallString<64> result;
buildFullName(true, result);
return result.str().str();
}
unsigned ArchetypeBuilder::PotentialArchetype::getNestingDepth() const {
unsigned Depth = 0;
for (auto P = getParent(); P; P = P->getParent())
++Depth;
return Depth;
}
void ArchetypeBuilder::PotentialArchetype::resolveAssociatedType(
AssociatedTypeDecl *assocType,
ArchetypeBuilder &builder) {
assert(!NameOrAssociatedType.is<AssociatedTypeDecl *>() &&
"associated type is already resolved");
NameOrAssociatedType = assocType;
assert(builder.Impl->NumUnresolvedNestedTypes > 0 &&
"Mismatch in number of unresolved nested types");
--builder.Impl->NumUnresolvedNestedTypes;
}
/// Retrieve the conformance for the superclass constraint of the given
/// potential archetype (if present) to the given protocol.
///
/// \param pa The potential archetype whose superclass constraint is being
/// queried.
///
/// \param proto The protocol to which we are establishing conformance.
///
/// \param conformsSource The requirement source for the conformance to the
/// given protocol.
///
/// \param builder The archetype builder in which the potential archetype
/// resides.
static ProtocolConformance *getSuperConformance(
ArchetypeBuilder::PotentialArchetype *pa,
ProtocolDecl *proto,
RequirementSource &conformsSource,
ArchetypeBuilder &builder) {
// Get the superclass constraint.
Type superclass = pa->getSuperclass();
if (!superclass) return nullptr;
// Lookup the conformance of the superclass to this protocol.
auto conformance =
builder.getModule().lookupConformance(superclass, proto,
builder.getLazyResolver());
if (!conformance) return nullptr;
// Conformance to this protocol is redundant; update the requirement source
// appropriately.
updateRequirementSource(
conformsSource,
RequirementSource(RequirementSource::Protocol,
pa->getSuperclassSource().getLoc()));
return conformance->getConcrete();
}
/// 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(
ArchetypeBuilder::PotentialArchetype *nestedPA,
RequirementSource fromSource,
ProtocolConformance *superConformance,
ArchetypeBuilder &builder) {
// If there's no super conformance, we're done.
if (!superConformance) return;
auto assocType = nestedPA->getResolvedAssociatedType();
assert(assocType && "Not resolved to an associated type?");
// Dig out the type witness.
auto concreteType =
superConformance->getTypeWitness(assocType, builder.getLazyResolver())
.getReplacement();
if (!concreteType) return;
// Add the same-type constraint.
RequirementSource source(RequirementSource::Protocol, fromSource.getLoc());
concreteType = ArchetypeBuilder::mapTypeOutOfContext(
superConformance->getDeclContext(), concreteType);
if (auto otherPA = builder.resolveArchetype(concreteType))
builder.addSameTypeRequirementBetweenArchetypes(nestedPA, otherPA, source);
else
builder.addSameTypeRequirementToConcrete(nestedPA, concreteType, source);
}
bool ArchetypeBuilder::PotentialArchetype::addConformance(
ProtocolDecl *proto,
const RequirementSource &source,
ArchetypeBuilder &builder) {
auto rep = getRepresentative();
if (rep != this)
return rep->addConformance(proto, 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.
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.
ProtocolConformance *superConformance = getSuperConformance(this, proto,
inserted->second,
builder);
// Check whether any associated types in this protocol resolve
// nested types of this potential archetype.
for (auto member : proto->getMembers()) {
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(),
source, superConformance,
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);
auto frontRep = known->second.front()->getRepresentative();
otherPA->Representative = frontRep;
frontRep->EquivalenceClass.push_back(otherPA);
otherPA->SameTypeSource = RequirementSource(RequirementSource::Inferred,
source.getLoc());
known->second.push_back(otherPA);
// If there's a superclass constraint that conforms to the protocol,
// add the appropriate same-type relationship.
maybeAddSameTypeRequirementForNestedType(otherPA, source,
superConformance, builder);
}
return true;
}
auto ArchetypeBuilder::PotentialArchetype::getRepresentative()
-> PotentialArchetype *{
// Find the representative.
PotentialArchetype *Result = Representative;
while (Result != Result->Representative)
Result = Result->Representative;
// Perform (full) path compression.
PotentialArchetype *FixUp = this;
while (FixUp != FixUp->Representative) {
PotentialArchetype *Next = FixUp->Representative;
FixUp->Representative = Result;
FixUp = Next;
}
return Result;
}
bool ArchetypeBuilder::PotentialArchetype::hasConcreteTypeInPath() const {
for (auto pa = this; pa; pa = pa->getParent()) {
if (pa->ArchetypeOrConcreteType.isConcreteType() &&
!pa->ArchetypeOrConcreteType.getAsConcreteType()->is<ArchetypeType>())
return true;
}
return false;
}
bool ArchetypeBuilder::PotentialArchetype::isBetterArchetypeAnchor(
PotentialArchetype *other) {
auto concrete = hasConcreteTypeInPath();
auto otherConcrete = other->hasConcreteTypeInPath();
if (concrete != otherConcrete)
return otherConcrete;
// FIXME: Not a total order.
return std::make_tuple(getRootParam()->getDepth(),
getRootParam()->getIndex(),
getNestingDepth())
< std::make_tuple(other->getRootParam()->getDepth(),
other->getRootParam()->getIndex(),
other->getNestingDepth());
}
auto ArchetypeBuilder::PotentialArchetype::getArchetypeAnchor()
-> PotentialArchetype * {
// Default to the representative, unless we find something better.
PotentialArchetype *best = getRepresentative();
for (auto pa : getEquivalenceClass()) {
if (pa->isBetterArchetypeAnchor(best))
best = pa;
}
return best;
}
auto ArchetypeBuilder::PotentialArchetype::getNestedType(
Identifier nestedName,
ArchetypeBuilder &builder) -> PotentialArchetype * {
// Retrieve the nested type from the representation of this set.
if (Representative != this)
return getRepresentative()->getNestedType(nestedName, builder);
// If we already have a nested type with this name, return it.
if (!NestedTypes[nestedName].empty()) {
return NestedTypes[nestedName].front();
}
// Attempt to resolve this nested type to an associated type
// of one of the protocols to which the parent potential
// archetype conforms.
for (auto &conforms : ConformsTo) {
for (auto member : conforms.first->lookupDirect(nestedName)) {
PotentialArchetype *pa;
if (auto assocType = dyn_cast<AssociatedTypeDecl>(member)) {
// Resolve this nested type to this associated type.
pa = new PotentialArchetype(this, assocType);
} else if (auto alias = dyn_cast<TypeAliasDecl>(member)) {
// Resolve this nested type to this type alias.
pa = new PotentialArchetype(this, alias);
if (!alias->hasUnderlyingType())
builder.getLazyResolver()->resolveDeclSignature(alias);
if (!alias->hasUnderlyingType())
continue;
auto type = alias->getUnderlyingType();
SmallVector<Identifier, 4> identifiers;
if (auto archetype = type->getAs<ArchetypeType>()) {
auto containingProtocol = dyn_cast<ProtocolDecl>(alias->getParent());
if (!containingProtocol) continue;
// Go up archetype parents until we find our containing protocol.
while (archetype->getSelfProtocol() != containingProtocol) {
identifiers.push_back(archetype->getName());
archetype = archetype->getParent();
if (!archetype)
break;
}
if (!archetype)
continue;
} else if (auto dependent = type->getAs<DependentMemberType>()) {
do {
identifiers.push_back(dependent->getName());
dependent = dependent->getBase()->getAs<DependentMemberType>();
} while (dependent);
}
if (identifiers.size()) {
// Go down our PAs until we find the referenced PA.
auto existingPA = this;
while (identifiers.size()) {
auto identifier = identifiers.back();
// If we end up looking for ourselves, don't recurse.
if (existingPA == this && identifier == nestedName) {
existingPA = pa;
} else {
existingPA = existingPA->getNestedType(identifier, builder);
existingPA = existingPA->getRepresentative();
}
identifiers.pop_back();
}
if (pa != existingPA) {
pa->Representative = existingPA;
RequirementSource source(RequirementSource::Inferred, SourceLoc());
pa->SameTypeSource = source;
}
} else if (type->hasArchetype()) {
// This is a complex type involving other associatedtypes, we'll fail
// to resolve and get a special diagnosis in finalize.
continue;
} else {
pa->ArchetypeOrConcreteType = NestedType::forConcreteType(type);
}
} else
continue;
// If we have resolved this nested type to more than one associated
// type, create same-type constraints between them.
RequirementSource source(RequirementSource::Inferred, SourceLoc());
llvm::TinyPtrVector<PotentialArchetype *> &nested =
NestedTypes[nestedName];
if (!nested.empty()) {
auto existing = nested.front();
if (existing->getTypeAliasDecl() && !pa->getTypeAliasDecl()) {
// If we found a typealias first, and now have an associatedtype
// with the same name, it was a Swift 2 style declaration of the
// type an inherited associatedtype should be bound to. In such a
// case we want to make sure the associatedtype is frontmost to
// generate generics/witness lists correctly, and the alias
// will be unused/useless for generic constraining anyway.
for (auto existing : nested) {
existing->Representative = pa;
existing->Representative->EquivalenceClass.push_back(existing);
existing->SameTypeSource = source;
}
nested.insert(nested.begin(), pa);
NestedTypes[nestedName] = nested;
} else {
pa->Representative = existing->getRepresentative();
pa->Representative->EquivalenceClass.push_back(pa);
pa->SameTypeSource = source;
nested.push_back(pa);
}
} else
nested.push_back(pa);
// If there's a superclass constraint that conforms to the protocol,
// add the appropriate same-type relationship.
ProtocolConformance *superConformance =
getSuperConformance(this, conforms.first, conforms.second, builder);
maybeAddSameTypeRequirementForNestedType(pa, source,
superConformance, 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;
}
return nested.front();
}
/// Replace dependent types with their archetypes or concrete types.
static Type substConcreteTypesForDependentTypes(ArchetypeBuilder &builder,
Type type) {
return type.transform([&](Type type) -> Type {
if (auto depMemTy = type->getAs<DependentMemberType>()) {
auto newBase = substConcreteTypesForDependentTypes(builder,
depMemTy->getBase());
return depMemTy->substBaseType(&builder.getModule(), newBase,
builder.getLazyResolver());
}
if (auto typeParam = type->getAs<GenericTypeParamType>()) {
auto potentialArchetype = builder.resolveArchetype(typeParam);
return potentialArchetype->getType(builder).getValue();
}
return type;
});
}
ArchetypeType::NestedType
ArchetypeBuilder::PotentialArchetype::getType(ArchetypeBuilder &builder) {
auto representative = getRepresentative();
// Retrieve the archetype from the archetype anchor in this equivalence class.
auto archetypeAnchor = getArchetypeAnchor();
if (archetypeAnchor != this)
return archetypeAnchor->getType(builder);
// Return a concrete type or archetype we've already resolved.
if (representative->ArchetypeOrConcreteType) {
// If the concrete type is dependent, substitute dependent types
// for archetypes.
if (auto concreteType
= representative->ArchetypeOrConcreteType.getAsConcreteType()) {
if (concreteType->hasTypeParameter()) {
// If we already know the concrete type is recursive, just
// return an error. It will be diagnosed elsewhere.
if (representative->RecursiveConcreteType) {
return NestedType::forConcreteType(
ErrorType::get(builder.getASTContext()));
}
// If we're already substituting a concrete type, mark this
// potential archetype as having a recursive concrete type.
if (representative->SubstitutingConcreteType) {
representative->RecursiveConcreteType = true;
return NestedType::forConcreteType(
ErrorType::get(builder.getASTContext()));
}
representative->SubstitutingConcreteType = true;
NestedType result = NestedType::forConcreteType(
substConcreteTypesForDependentTypes(
builder,
concreteType));
representative->SubstitutingConcreteType = false;
// If all went well, we're done.
if (!representative->RecursiveConcreteType)
return result;
// Otherwise, we found that the concrete type is recursive,
// complain and return an error.
builder.Diags.diagnose(SameTypeSource->getLoc(),
diag::recursive_same_type_constraint,
getDependentType(builder, false),
concreteType);
return NestedType::forConcreteType(
ErrorType::get(builder.getASTContext()));
}
}
return representative->ArchetypeOrConcreteType;
}
ArchetypeType::AssocTypeOrProtocolType assocTypeOrProto = RootProtocol;
// Allocate a new archetype.
ArchetypeType *ParentArchetype = nullptr;
auto &mod = builder.getModule();
if (auto parent = getParent()) {
assert(assocTypeOrProto.isNull() &&
"root protocol type given for non-root archetype");
auto parentTy = parent->getType(builder);
if (!parentTy)
return NestedType::forConcreteType(
ErrorType::get(builder.getASTContext()));
ParentArchetype = parentTy.getAsArchetype();
if (!ParentArchetype) {
// We might have an outer archetype as a concrete type here; if so, just
// return that.
ParentArchetype = parentTy.getValue()->getAs<ArchetypeType>();
if (ParentArchetype) {
representative->ArchetypeOrConcreteType
= NestedType::forConcreteType(
ParentArchetype->getNestedTypeValue(getName()));
return representative->ArchetypeOrConcreteType;
}
LazyResolver *resolver = builder.getLazyResolver();
assert(resolver && "need a lazy resolver");
(void) resolver;
// Resolve the member type.
auto type = getDependentType(builder, false);
if (type->is<ErrorType>())
return NestedType::forConcreteType(type);
auto depMemberType = type->castTo<DependentMemberType>();
Type memberType = depMemberType->substBaseType(
&mod,
parent->ArchetypeOrConcreteType.getAsConcreteType(),
builder.getLazyResolver());
if (auto memberPA = builder.resolveArchetype(memberType)) {
// If the member type maps to an archetype, resolve that archetype.
if (memberPA->getRepresentative() != getRepresentative()) {
representative->ArchetypeOrConcreteType = memberPA->getType(builder);
return representative->ArchetypeOrConcreteType;
}
llvm_unreachable("we have no parent archetype");
} else {
// Otherwise, it's a concrete type.
representative->ArchetypeOrConcreteType
= NestedType::forConcreteType(
builder.substDependentType(memberType));
return representative->ArchetypeOrConcreteType;
}
}
assocTypeOrProto = getResolvedAssociatedType();
}
// If we ended up building our parent archetype, then we'll have
// already filled in our own archetype.
if (auto arch = representative->ArchetypeOrConcreteType.getAsArchetype())
return NestedType::forArchetype(arch);
SmallVector<ProtocolDecl *, 4> Protos;
for (const auto &conforms : ConformsTo) {
Protos.push_back(conforms.first);
}
Type superclass;
if (Superclass) {
if (representative->RecursiveSuperclassType) {
builder.Diags.diagnose(SuperclassSource->getLoc(),
diag::recursive_superclass_constraint,
Superclass);
} else {
representative->RecursiveSuperclassType = true;
assert(!Superclass->hasArchetype() &&
"superclass constraint must use interface types");
superclass = builder.substDependentType(Superclass);
representative->RecursiveSuperclassType = false;
}
}
auto arch
= ArchetypeType::getNew(builder.getASTContext(), ParentArchetype,
assocTypeOrProto, getName(), Protos,
superclass, isRecursive());
representative->ArchetypeOrConcreteType = NestedType::forArchetype(arch);
// Collect the set of nested types of this archetype, and put them into
// the archetype itself.
if (!NestedTypes.empty()) {
builder.getASTContext().registerLazyArchetype(arch, builder, this);
SmallVector<std::pair<Identifier, NestedType>, 4> FlatNestedTypes;
for (auto Nested : NestedTypes) {
// Skip type aliases, which are just shortcuts.
if (Nested.second.front()->getTypeAliasDecl())
continue;
bool anyNotRenamed = false;
for (auto NestedPA : Nested.second) {
if (!NestedPA->wasRenamed()) {
anyNotRenamed = true;
break;
}
}
if (!anyNotRenamed)
continue;
FlatNestedTypes.push_back({ Nested.first, NestedType() });
}
arch->setNestedTypes(builder.getASTContext(), FlatNestedTypes);
// Force the resolution of the nested types.
(void)arch->getNestedTypes();
builder.getASTContext().unregisterLazyArchetype(arch);
}
return NestedType::forArchetype(arch);
}
Type ArchetypeBuilder::PotentialArchetype::getDependentType(
ArchetypeBuilder &builder,
bool allowUnresolved) {
if (auto parent = getParent()) {
Type parentType = parent->getDependentType(builder, allowUnresolved);
if (parentType->is<ErrorType>())
return parentType;
// If we've resolved to an associated type, use it.
if (auto assocType = getResolvedAssociatedType())
return DependentMemberType::get(parentType, assocType, builder.Context);
// If typo correction renamed this type, get the renamed type.
if (wasRenamed())
return parent->getNestedType(getName(), builder)
->getDependentType(builder, allowUnresolved);
// If we don't allow unresolved dependent member types, fail.
if (!allowUnresolved)
return ErrorType::get(builder.Context);
return DependentMemberType::get(parentType, getName(), builder.Context);
}
assert(getGenericParam() && "Not a generic parameter?");
return getGenericParam();
}
void ArchetypeBuilder::PotentialArchetype::dump(llvm::raw_ostream &Out,
SourceManager *SrcMgr,
unsigned Indent) {
// Print name.
Out.indent(Indent) << getName();
// Print superclass.
if (Superclass) {
Out << " : ";
Superclass.print(Out);
Out << " [";
SuperclassSource->dump(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() << " [";
ProtoAndSource.second.dump(Out, SrcMgr);
Out << "]";
}
}
if (Representative != this) {
Out << " [represented by " << getRepresentative()->getFullName() << "]";
}
Out << "\n";
// Print nested types.
for (const auto &nestedVec : NestedTypes) {
for (auto nested : nestedVec.second) {
nested->dump(Out, SrcMgr, Indent + 2);
}
}
}
ArchetypeBuilder::ArchetypeBuilder(Module &mod, DiagnosticEngine &diags)
: Mod(mod), Context(mod.getASTContext()), Diags(diags),
Impl(new Implementation)
{
}
ArchetypeBuilder::ArchetypeBuilder(ArchetypeBuilder &&) = default;
ArchetypeBuilder::~ArchetypeBuilder() {
if (!Impl)
return;
for (auto PA : Impl->PotentialArchetypes)
delete PA.second;
}
LazyResolver *ArchetypeBuilder::getLazyResolver() const {
return Context.getLazyResolver();
}
auto ArchetypeBuilder::resolveArchetype(Type type) -> PotentialArchetype * {
if (auto genericParam = type->getAs<GenericTypeParamType>()) {
auto known
= Impl->PotentialArchetypes.find(GenericTypeParamKey::forType(genericParam));
if (known == Impl->PotentialArchetypes.end())
return nullptr;
return known->second;
}
if (auto dependentMember = type->getAs<DependentMemberType>()) {
auto base = resolveArchetype(dependentMember->getBase());
if (!base)
return nullptr;
return base->getNestedType(dependentMember->getName(), *this);
}
return nullptr;
}
auto ArchetypeBuilder::addGenericParameter(GenericTypeParamType *GenericParam,
ProtocolDecl *RootProtocol,
Identifier ParamName)
-> PotentialArchetype *
{
GenericTypeParamKey Key{GenericParam->getDepth(), GenericParam->getIndex()};
// Create a potential archetype for this type parameter.
assert(!Impl->PotentialArchetypes[Key]);
auto PA = new PotentialArchetype(GenericParam, RootProtocol, ParamName);
Impl->PotentialArchetypes[Key] = PA;
return PA;
}
bool ArchetypeBuilder::addGenericParameter(GenericTypeParamDecl *GenericParam) {
ProtocolDecl *RootProtocol = dyn_cast<ProtocolDecl>(GenericParam->getDeclContext());
if (!RootProtocol) {
if (auto Ext = dyn_cast<ExtensionDecl>(GenericParam->getDeclContext()))
RootProtocol = dyn_cast_or_null<ProtocolDecl>(Ext->getExtendedType()->getAnyNominal());
}
PotentialArchetype *PA
= addGenericParameter(
GenericParam->getDeclaredType()->castTo<GenericTypeParamType>(),
RootProtocol,
GenericParam->getName());
return (!PA);
}
bool ArchetypeBuilder::addGenericParameterRequirements(GenericTypeParamDecl *GenericParam) {
GenericTypeParamKey Key{GenericParam->getDepth(), GenericParam->getIndex()};
auto PA = Impl->PotentialArchetypes[Key];
// Add the requirements from the declaration.
llvm::SmallPtrSet<ProtocolDecl *, 8> visited;
return addAbstractTypeParamRequirements(GenericParam, PA,
RequirementSource::Explicit,
visited);
}
bool ArchetypeBuilder::addGenericParameter(GenericTypeParamType *GenericParam) {
auto name = GenericParam->getName();
// Trim '$' so that archetypes are more readily discernible from abstract
// parameters.
if (name.str().startswith("$"))
name = Context.getIdentifier(name.str().slice(1, name.str().size()));
PotentialArchetype *PA = addGenericParameter(GenericParam,
nullptr,
name);
return !PA;
}
bool ArchetypeBuilder::addConformanceRequirement(PotentialArchetype *PAT,
ProtocolDecl *Proto,
RequirementSource Source) {
llvm::SmallPtrSet<ProtocolDecl *, 8> Visited;
return addConformanceRequirement(PAT, Proto, Source, Visited);
}
bool ArchetypeBuilder::addConformanceRequirement(PotentialArchetype *PAT,
ProtocolDecl *Proto,
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, Source, *this))
return false;
RequirementSource InnerSource(RequirementSource::Protocol, Source.getLoc());
bool inserted = Visited.insert(Proto).second;
assert(inserted);
(void) inserted;
// Add all of the inherited protocol requirements, recursively.
if (auto resolver = getLazyResolver())
resolver->resolveInheritedProtocols(Proto);
for (auto InheritedProto : Proto->getInheritedProtocols(getLazyResolver())) {
if (Visited.count(InheritedProto))
continue;
if (addConformanceRequirement(T, InheritedProto, InnerSource, Visited))
return true;
}
// Add requirements for each of the associated types.
// FIXME: This should use the generic signature, not walk the members.
for (auto Member : Proto->getMembers()) {
if (auto AssocType = dyn_cast<AssociatedTypeDecl>(Member)) {
// Add requirements placed directly on this associated type.
auto AssocPA = T->getNestedType(AssocType->getName(), *this);
if (AssocPA != T) {
if (addAbstractTypeParamRequirements(AssocType, AssocPA,
RequirementSource::Protocol,
Visited))
return true;
}
continue;
}
// FIXME: Requirement declarations.
}
Visited.erase(Proto);
return false;
}
bool ArchetypeBuilder::addSuperclassRequirement(PotentialArchetype *T,
Type Superclass,
RequirementSource Source) {
if (Superclass->hasArchetype()) {
// Map contextual type to interface type.
// FIXME: There might be a better way to do this.
Superclass = Superclass.transform(
[&](Type t) -> Type {
if (t->is<ArchetypeType>()) {
auto *pa = resolveArchetype(t);
// Why does this happen?
if (!pa)
return ErrorType::get(Context);
return pa->getDependentType(*this, false);
}
return t;
});
}
// Local function to handle the update of superclass conformances
// when the superclass constraint changes.
auto updateSuperclassConformances = [&] {
for (auto &conforms : T->ConformsTo) {
if (auto superConformance = getSuperConformance(T, conforms.first,
conforms.second, *this)) {
for (auto req : conforms.first->getMembers()) {
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,
Source,
superConformance, *this);
}
}
}
}
};
// If T already has a superclass, make sure it's related.
if (T->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 (T->Superclass->isExactSuperclassOf(Superclass, nullptr)) {
T->Superclass = Superclass;
// We've strengthened the bound, so update superclass conformances.
updateSuperclassConformances();
// TODO: Similar to the above, a more general isBindableToSuperclassOf
// base class constraint could potentially introduce secondary constraints.
// 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.
} else if (!Superclass->isExactSuperclassOf(T->Superclass, nullptr)) {
Diags.diagnose(Source.getLoc(),
diag::requires_superclass_conflict, T->getName(),
T->Superclass, Superclass)
.highlight(T->SuperclassSource->getLoc());
return true;
}
updateRequirementSource(*T->SuperclassSource, Source);
return false;
}
// Set the superclass.
T->Superclass = Superclass;
T->SuperclassSource = Source;
// Update based on these conformances.
updateSuperclassConformances();
return false;
}
bool ArchetypeBuilder::addSameTypeRequirementBetweenArchetypes(
PotentialArchetype *T1,
PotentialArchetype *T2,
RequirementSource Source)
{
auto OrigT1 = T1, OrigT2 = T2;
// Operate on the representatives
T1 = T1->getRepresentative();
T2 = T2->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.
// We necessarily prefer potential archetypes rooted at parameters that come
// from outer generic parameter lists, since those generic parameters will
// have archetypes bound in the outer context.
// FIXME: This isn't a total ordering
auto T1Param = T1->getRootParam();
auto T2Param = T2->getRootParam();
unsigned T1Depth = T1->getNestingDepth();
unsigned T2Depth = T2->getNestingDepth();
if (std::make_tuple(T2->wasRenamed(), T2Param->getDepth(),
T2Param->getIndex(), T2Depth)
< std::make_tuple(T1->wasRenamed(), T1Param->getDepth(),
T1Param->getIndex(), T1Depth))
std::swap(T1, T2);
// Don't allow two generic parameters to be equivalent, because then we
// don't actually have two parameters.
// FIXME: Should we simply allow this?
if (T1Depth == 0 && T2Depth == 0) {
Diags.diagnose(Source.getLoc(), diag::requires_generic_params_made_equal,
T1->getName(), T2->getName());
return true;
}
// Merge any concrete constraints.
Type concrete1 = T1->ArchetypeOrConcreteType.getAsConcreteType();
Type concrete2 = T2->ArchetypeOrConcreteType.getAsConcreteType();
if (concrete1 && concrete2) {
if (!concrete1->isEqual(concrete2)) {
Diags.diagnose(Source.getLoc(), diag::requires_same_type_conflict,
T1->getName(), concrete1, concrete2);
return true;
}
} else if (concrete1) {
assert(!T2->ArchetypeOrConcreteType
&& "already formed archetype for concrete-constrained parameter");
T2->ArchetypeOrConcreteType = NestedType::forConcreteType(concrete1);
T2->SameTypeSource = T1->SameTypeSource;
} else if (concrete2) {
assert(!T1->ArchetypeOrConcreteType
&& "already formed archetype for concrete-constrained parameter");
T1->ArchetypeOrConcreteType = NestedType::forConcreteType(concrete2);
T1->SameTypeSource = T2->SameTypeSource;
}
// Make T1 the representative of T2, merging the equivalence classes.
T2->Representative = T1;
T2->SameTypeSource = Source;
for (auto equiv : T2->EquivalenceClass)
T1->EquivalenceClass.push_back(equiv);
if (!T1->wasRenamed() && !T2->wasRenamed()) {
// Record this same-type requirement.
Impl->SameTypeRequirements.push_back({ OrigT1, OrigT2 });
}
// FIXME: superclass requirements!
// Add all of the protocol conformance requirements of T2 to T1.
for (auto conforms : T2->ConformsTo) {
T1->addConformance(conforms.first, conforms.second, *this);
}
// Recursively merge the associated types of T2 into T1.
RequirementSource inferredSource(RequirementSource::Inferred, SourceLoc());
for (auto T2Nested : T2->NestedTypes) {
auto T1Nested = T1->getNestedType(T2Nested.first, *this);
if (addSameTypeRequirementBetweenArchetypes(T1Nested,
T2Nested.second.front(),
inferredSource))
return true;
}
return false;
}
bool ArchetypeBuilder::addSameTypeRequirementToConcrete(
PotentialArchetype *T,
Type Concrete,
RequirementSource Source) {
// Operate on the representative.
auto OrigT = T;
T = T->getRepresentative();
assert(!T->ArchetypeOrConcreteType.getAsArchetype()
&& "already formed archetype for concrete-constrained parameter");
// If we've already been bound to a type, we're either done, or we have a
// problem.
if (auto oldConcrete = T->ArchetypeOrConcreteType.getAsConcreteType()) {
if (!oldConcrete->isEqual(Concrete)) {
Diags.diagnose(Source.getLoc(), diag::requires_same_type_conflict,
T->getName(), oldConcrete, Concrete);
return true;
}
return false;
}
// Don't allow a generic parameter to be equivalent to a concrete type,
// because then we don't actually have a parameter.
// FIXME: Should we simply allow this?
if (T->getNestingDepth() == 0) {
Diags.diagnose(Source.getLoc(),
diag::requires_generic_param_made_equal_to_concrete,
T->getName());
return true;
}
// Make sure the concrete type fulfills the requirements on the archetype.
DenseMap<ProtocolDecl *, ProtocolConformance*> conformances;
if (!Concrete->is<ArchetypeType>()) {
for (auto conforms : T->getConformsTo()) {
auto protocol = conforms.first;
auto conformance = Mod.lookupConformance(Concrete, protocol,
getLazyResolver());
if (!conformance) {
Diags.diagnose(Source.getLoc(),
diag::requires_generic_param_same_type_does_not_conform,
Concrete, protocol->getName());
return true;
}
assert(conformance->isConcrete() && "Abstract conformance?");
conformances[protocol] = conformance->getConcrete();
}
}
// Record the requirement.
T->ArchetypeOrConcreteType = NestedType::forConcreteType(Concrete);
T->SameTypeSource = Source;
Impl->SameTypeRequirements.push_back({OrigT, Concrete});
// Recursively resolve the associated types to their concrete types.
for (auto nested : T->getNestedTypes()) {
AssociatedTypeDecl *assocType
= nested.second.front()->getResolvedAssociatedType();
if (auto *concreteArchetype = Concrete->getAs<ArchetypeType>()) {
ArchetypeType::NestedType witnessType =
concreteArchetype->getNestedType(nested.first);
addSameTypeRequirementToConcrete(nested.second.front(),
witnessType.getValue(),
Source);
} else {
assert(conformances.count(assocType->getProtocol()) > 0
&& "missing conformance?");
auto witness = conformances[assocType->getProtocol()]
->getTypeWitness(assocType, getLazyResolver());
auto witnessType = witness.getReplacement();
if (auto witnessPA = resolveArchetype(witnessType)) {
addSameTypeRequirementBetweenArchetypes(nested.second.front(),
witnessPA,
Source);
} else {
addSameTypeRequirementToConcrete(nested.second.front(),
witnessType,
Source);
}
}
}
return false;
}
bool ArchetypeBuilder::addSameTypeRequirement(Type Reqt1, Type Reqt2,
RequirementSource Source) {
// Find the potential archetypes.
PotentialArchetype *T1 = resolveArchetype(Reqt1);
PotentialArchetype *T2 = resolveArchetype(Reqt2);
// Require that at least one side of the requirement be a potential archetype.
if (!T1 && !T2) {
assert(Source.getLoc().isValid() && "reintroducing invalid requirement");
Diags.diagnose(Source.getLoc(), diag::requires_no_same_type_archetype);
return true;
}
// If both sides of the requirement are open archetypes, combine them.
if (T1 && T2)
return addSameTypeRequirementBetweenArchetypes(T1, T2, Source);
// Otherwise, we're binding an open archetype.
if (T1)
return addSameTypeRequirementToConcrete(T1, Reqt2, Source);
return addSameTypeRequirementToConcrete(T2, Reqt1, Source);
}
bool ArchetypeBuilder::addAbstractTypeParamRequirements(
AbstractTypeParamDecl *decl,
PotentialArchetype *pa,
RequirementSource::Kind kind,
llvm::SmallPtrSetImpl<ProtocolDecl *> &visited) {
// Local function to mark the given associated type as recursive,
// diagnosing it if this is the first such occurrence.
auto markRecursive = [&](AssociatedTypeDecl *assocType,
ProtocolDecl *proto,
SourceLoc loc) {
if (!pa->isRecursive() && !assocType->isRecursive()) {
Diags.diagnose(assocType->getLoc(),
diag::recursive_requirement_reference);
// Mark all associatedtypes in this protocol as recursive (and error-type)
// to avoid later crashes dealing with this invalid protocol in other
// contexts.
auto containingProto =
assocType->getDeclContext()->getAsProtocolOrProtocolExtensionContext();
for (auto member : containingProto->getMembers())
if (auto assocType = dyn_cast<AssociatedTypeDecl>(member))
assocType->setIsRecursive();
}
pa->setIsRecursive();
// Silence downstream errors referencing this associated type.
assocType->setInvalid();
// FIXME: Drop this protocol.
pa->addConformance(proto, RequirementSource(kind, loc), *this);
};
// If the abstract type parameter already has an archetype assigned,
// use that information.
if (auto archetype = decl->getArchetype()) {
SourceLoc loc = decl->getLoc();
// Superclass requirement.
if (auto superclass = archetype->getSuperclass()) {
if (addSuperclassRequirement(pa, superclass,
RequirementSource(kind, loc)))
return true;
}
// Conformance requirements.
for (auto proto : archetype->getConformsTo()) {
if (visited.count(proto)) {
if (auto assocType = dyn_cast<AssociatedTypeDecl>(decl))
markRecursive(assocType, proto, loc);
continue;
}
if (addConformanceRequirement(pa, proto, RequirementSource(kind, loc),
visited))
return true;
}
return false;
}
// Otherwise, walk the 'inherited' list to identify requirements.
if (auto resolver = getLazyResolver())
resolver->resolveInheritanceClause(decl);
return visitInherited(decl->getInherited(),
[&](Type inheritedType, SourceLoc loc) -> bool {
// Protocol requirement.
if (auto protocolType = inheritedType->getAs<ProtocolType>()) {
if (visited.count(protocolType->getDecl())) {
if (auto assocType = dyn_cast<AssociatedTypeDecl>(decl))
markRecursive(assocType, protocolType->getDecl(), loc);
return true;
}
return addConformanceRequirement(pa, protocolType->getDecl(),
RequirementSource(kind, loc),
visited);
}
// Superclass requirement.
if (inheritedType->getClassOrBoundGenericClass()) {
return addSuperclassRequirement(pa, inheritedType,
RequirementSource(kind, loc));
}
// Note: anything else is an error, to be diagnosed later.
return false;
});
}
bool ArchetypeBuilder::visitInherited(
ArrayRef<TypeLoc> inheritedTypes,
llvm::function_ref<bool(Type, SourceLoc)> visitor) {
// Local function that (recursively) adds inherited types.
bool isInvalid = false;
std::function<void(Type, SourceLoc)> visitInherited;
visitInherited = [&](Type inheritedType, SourceLoc loc) {
// Decompose protocol compositions.
if (auto compositionType
= inheritedType->getAs<ProtocolCompositionType>()) {
for (auto protoType : compositionType->getProtocols())
visitInherited(protoType, loc);
return;
}
isInvalid |= visitor(inheritedType, loc);
};
// Visit all of the inherited types.
for (auto inherited : inheritedTypes) {
visitInherited(inherited.getType(), inherited.getLoc());
}
return isInvalid;
}
bool ArchetypeBuilder::addRequirement(const RequirementRepr &Req) {
switch (Req.getKind()) {
case RequirementReprKind::TypeConstraint: {
PotentialArchetype *PA = resolveArchetype(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.
RequirementSource source(RequirementSource::Explicit,
Req.getConstraintLoc().getSourceRange().Start);
if (Req.getConstraint()->getClassOrBoundGenericClass()) {
return addSuperclassRequirement(PA, Req.getConstraint(), source);
}
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, source))
return true;
return false;
}
case RequirementReprKind::SameType:
return addSameTypeRequirement(Req.getFirstType(),
Req.getSecondType(),
RequirementSource(RequirementSource::Explicit,
Req.getEqualLoc()));
}
llvm_unreachable("Unhandled requirement?");
}
void ArchetypeBuilder::addRequirement(const Requirement &req,
RequirementSource source) {
switch (req.getKind()) {
case RequirementKind::Superclass: {
PotentialArchetype *pa = resolveArchetype(req.getFirstType());
assert(pa && "Re-introducing invalid requirement");
assert(req.getSecondType()->getClassOrBoundGenericClass());
addSuperclassRequirement(pa, req.getSecondType(), source);
return;
}
case RequirementKind::Conformance: {
PotentialArchetype *pa = resolveArchetype(req.getFirstType());
assert(pa && "Re-introducing invalid requirement");
SmallVector<ProtocolDecl *, 4> conformsTo;
bool existential = req.getSecondType()->isExistentialType(conformsTo);
assert(existential && "Re-introducing invalid requirement");
(void)existential;
// Add each of the protocols.
for (auto proto : conformsTo) {
bool invalid = addConformanceRequirement(pa, proto, source);
assert(!invalid && "Re-introducing invalid requirement");
(void)invalid;
}
return;
}
case RequirementKind::SameType:
addSameTypeRequirement(req.getFirstType(), req.getSecondType(), source);
return;
case RequirementKind::WitnessMarker:
return;
}
llvm_unreachable("Unhandled requirement?");
}
/// AST walker that infers requirements from type representations.
class ArchetypeBuilder::InferRequirementsWalker : public TypeWalker {
ArchetypeBuilder &Builder;
SourceLoc Loc;
bool HadError = false;
unsigned Depth;
/// We cannot add requirements to archetypes from outer generic parameter
/// lists.
bool isOuterArchetype(PotentialArchetype *PA) {
unsigned ParamDepth = PA->getRootParam()->getDepth();
assert(ParamDepth <= Depth);
return ParamDepth < Depth;
}
public:
InferRequirementsWalker(ArchetypeBuilder &builder,
SourceLoc loc,
unsigned Depth)
: Builder(builder), Loc(loc), Depth(Depth) { }
bool hadError() const { return HadError; }
virtual 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;
auto params = genericSig->getInnermostGenericParams();
auto args = boundGeneric->getGenericArgs();
// Produce substitutions from the generic parameters to the actual
// arguments.
TypeSubstitutionMap substitutions;
for (unsigned i = 0, n = params.size(); i != n; ++i) {
substitutions[params[i]->getCanonicalType()->castTo<SubstitutableType>()]
= args[i];
}
// Handle the requirements.
RequirementSource source(RequirementSource::Inferred, Loc);
for (const auto &req : genericSig->getRequirements()) {
switch (req.getKind()) {
case RequirementKind::WitnessMarker:
break;
case RequirementKind::SameType: {
auto firstType = req.getFirstType().subst(
&Builder.getModule(),
substitutions,
SubstFlags::IgnoreMissing);
if (!firstType)
break;
auto firstPA = Builder.resolveArchetype(firstType);
if (firstPA && isOuterArchetype(firstPA))
return Action::Continue;
auto secondType = req.getSecondType().subst(
&Builder.getModule(),
substitutions,
SubstFlags::IgnoreMissing);
if (!secondType)
break;
auto secondPA = Builder.resolveArchetype(secondType);
if (firstPA && secondPA) {
if (Builder.addSameTypeRequirementBetweenArchetypes(firstPA, secondPA,
source)) {
HadError = true;
return Action::Stop;
}
} else if (firstPA || secondPA) {
auto PA = firstPA ? firstPA : secondPA;
auto concrete = firstPA ? secondType : firstType;
if (Builder.addSameTypeRequirementToConcrete(PA, concrete, source)) {
HadError = true;
return Action::Stop;
}
}
break;
}
case RequirementKind::Superclass:
case RequirementKind::Conformance: {
auto subjectType = req.getFirstType().subst(
&Builder.getModule(),
substitutions,
SubstFlags::IgnoreMissing);
if (!subjectType)
break;
auto subjectPA = Builder.resolveArchetype(subjectType);
if (!subjectPA) {
break;
}
if (isOuterArchetype(subjectPA))
return Action::Continue;
if (req.getKind() == RequirementKind::Conformance) {
auto proto = req.getSecondType()->castTo<ProtocolType>();
if (Builder.addConformanceRequirement(subjectPA, proto->getDecl(),
source)) {
HadError = true;
return Action::Stop;
}
} else {
if (Builder.addSuperclassRequirement(subjectPA, req.getSecondType(),
source)) {
HadError = true;
return Action::Stop;
}
}
break;
}
}
}
return Action::Continue;
}
};
bool ArchetypeBuilder::inferRequirements(TypeLoc type,
GenericParamList *genericParams) {
if (!type.getType())
return true;
if (genericParams == nullptr)
return false;
// FIXME: Crummy source-location information.
InferRequirementsWalker walker(*this, type.getSourceRange().Start,
genericParams->getDepth());
type.getType().walk(walker);
return walker.hadError();
}
bool ArchetypeBuilder::inferRequirements(ParameterList *params,
GenericParamList *genericParams) {
if (genericParams == nullptr)
return false;
bool hadError = false;
for (auto P : *params)
hadError |= inferRequirements(P->getTypeLoc(), genericParams);
return hadError;
}
/// Perform typo correction on the given nested type, producing the
/// corrected name (if successful).
static Identifier typoCorrectNestedType(
ArchetypeBuilder::PotentialArchetype *pa) {
StringRef name = pa->getName().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 : proto->getMembers()) {
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();
}
bool ArchetypeBuilder::finalize(SourceLoc loc) {
bool invalid = false;
// 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() ||
/* FIXME: Should be able to handle this earlier */pa->getSuperclass())
return;
// If a typealias with this name exists in one of the parent protocols,
// give a special diagnosis.
auto parentConformances = pa->getParent()->getConformsTo();
for (auto &conforms : parentConformances) {
for (auto member : conforms.first->getMembers()) {
auto typealias = dyn_cast<TypeAliasDecl>(member);
if (!typealias || typealias->getName() != pa->getName())
continue;
Context.Diags.diagnose(loc, diag::invalid_member_type_alias,
pa->getName());
invalid = true;
pa->setInvalid();
return;
}
}
// Try to typo correct to a nested type name.
Identifier correction = typoCorrectNestedType(pa);
if (correction.empty()) {
invalid = true;
pa->setInvalid();
return;
}
// Set the typo-corrected name.
pa->setRenamed(correction);
// Resolve the associated type and merge the potential archetypes.
auto replacement = pa->getParent()->getNestedType(correction, *this);
addSameTypeRequirementBetweenArchetypes(
pa, replacement,
RequirementSource(RequirementSource::Inferred, SourceLoc()));
});
}
return invalid;
}
ArchetypeType *
ArchetypeBuilder::getArchetype(GenericTypeParamDecl *GenericParam) {
auto known = Impl->PotentialArchetypes.find(
GenericTypeParamKey::forDecl(GenericParam));
if (known == Impl->PotentialArchetypes.end())
return nullptr;
return known->second->getType(*this).getAsArchetype();
}
ArrayRef<ArchetypeType *> ArchetypeBuilder::getAllArchetypes() {
// This should be kept in sync with GenericParamList::deriveAllArchetypes().
if (Impl->AllArchetypes.empty()) {
// Collect the primary archetypes first.
unsigned depth = Impl->PotentialArchetypes.back().first.Depth;
llvm::SmallPtrSet<ArchetypeType *, 8> KnownArchetypes;
for (const auto &Entry : Impl->PotentialArchetypes) {
// Skip outer potential archetypes.
if (Entry.first.Depth < depth)
continue;
PotentialArchetype *PA = Entry.second;
auto Archetype = PA->getType(*this).castToArchetype();
if (KnownArchetypes.insert(Archetype).second)
Impl->AllArchetypes.push_back(Archetype);
}
// Collect all of the remaining archetypes.
for (const auto &Entry : Impl->PotentialArchetypes) {
// Skip outer potential archetypes.
if (Entry.first.Depth < depth)
continue;
PotentialArchetype *PA = Entry.second;
if (!PA->isConcreteType() && !PA->getTypeAliasDecl()) {
auto Archetype = PA->getType(*this).castToArchetype();
GenericParamList::addNestedArchetypes(Archetype, KnownArchetypes,
Impl->AllArchetypes);
}
}
}
return Impl->AllArchetypes;
}
ArrayRef<ArchetypeBuilder::SameTypeRequirement>
ArchetypeBuilder::getSameTypeRequirements() const {
return Impl->SameTypeRequirements;
}
template<typename F>
void ArchetypeBuilder::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).second)
stack.push_back(pa.second);
}
// 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);
}
}
}
}
}
namespace {
/// \brief Function object that orders potential archetypes by name.
struct OrderPotentialArchetypeByName {
using PotentialArchetype = ArchetypeBuilder::PotentialArchetype;
bool operator()(std::pair<Identifier, PotentialArchetype *> X,
std::pair<Identifier, PotentialArchetype *> Y) const {
return X.first.str() < Y.second->getName().str();
}
bool operator()(std::pair<Identifier, PotentialArchetype *> X,
Identifier Y) const {
return X.first.str() < Y.str();
}
bool operator()(Identifier X,
std::pair<Identifier, PotentialArchetype *> Y) const {
return X.str() < Y.first.str();
}
bool operator()(Identifier X, Identifier Y) const {
return X.str() < Y.str();
}
};
}
void ArchetypeBuilder::enumerateRequirements(llvm::function_ref<
void (RequirementKind kind,
PotentialArchetype *archetype,
llvm::PointerUnion<Type, PotentialArchetype *> type,
RequirementSource source)> f) {
// Local function to visit a potential archetype, enumerating its
// requirements.
auto visitPA = [&](PotentialArchetype *archetype) {
// Invalid archetypes are never representatives in well-formed or corrected
// signature, so we don't need to visit them.
if (archetype->isInvalid())
return;
// If this is not the representative, produce a same-type
// constraint to the representative.
if (archetype->getRepresentative() != archetype) {
if (!archetype->wasRenamed())
f(RequirementKind::SameType, archetype, archetype->getRepresentative(),
archetype->getSameTypeSource());
return;
}
// If we have a concrete type, produce a same-type requirement.
if (archetype->isConcreteType()) {
Type concreteType = archetype->getConcreteType();
f(RequirementKind::SameType, archetype, concreteType,
archetype->getSameTypeSource());
return;
}
// Add the witness marker.
f(RequirementKind::WitnessMarker, archetype, Type(),
RequirementSource(RequirementSource::Protocol, SourceLoc()));
// If we have a superclass, produce a superclass requirement
if (Type superclass = archetype->getSuperclass()) {
f(RequirementKind::Superclass, archetype, superclass,
archetype->getSuperclassSource());
}
// Enumerate conformance requirements.
SmallVector<ProtocolDecl *, 4> protocols;
DenseMap<ProtocolDecl *, RequirementSource> protocolSources;
for (const auto &conforms : archetype->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);
}
};
// Local function to visit the nested potential archetypes of the
// given potential archetype.
std::function<void(PotentialArchetype *archetype)> visitNested
= [&](PotentialArchetype *archetype) {
// Collect the nested types, sorted by name.
SmallVector<std::pair<Identifier, PotentialArchetype*>, 16> nestedTypes;
for (const auto &nested : archetype->getNestedTypes()) {
for (auto nestedPA : nested.second)
nestedTypes.push_back(std::make_pair(nested.first, nestedPA));
}
std::stable_sort(nestedTypes.begin(), nestedTypes.end(),
OrderPotentialArchetypeByName());
// Add requirements for the nested types.
for (const auto &nested : nestedTypes) {
visitPA(nested.second);
visitNested(nested.second);
}
};
auto primaryIter = Impl->PotentialArchetypes.begin(),
primaryIterEnd = Impl->PotentialArchetypes.end();
while (primaryIter != primaryIterEnd) {
unsigned depth = primaryIter->first.Depth;
// For each of the primary potential archetypes, add the requirements.
// Stop when we hit a parameter at a different depth.
// FIXME: This algorithm falls out from the way the "all archetypes" lists
// are structured. Once those lists no longer exist or are no longer
// "the truth", we can simplify this algorithm considerably.
auto nextPrimaryIter = primaryIter;
for (/*none*/;
(nextPrimaryIter != primaryIterEnd &&
nextPrimaryIter->first.Depth == depth);
++nextPrimaryIter) {
visitPA(nextPrimaryIter->second);
}
// For each of the primary potential archetypes, add the nested
// requirements.
for (; primaryIter != nextPrimaryIter; ++primaryIter) {
visitNested(primaryIter->second);
}
}
}
void ArchetypeBuilder::dump() {
dump(llvm::errs());
}
void ArchetypeBuilder::dump(llvm::raw_ostream &out) {
out << "Requirements:";
enumerateRequirements([&](RequirementKind kind,
PotentialArchetype *archetype,
llvm::PointerUnion<Type, PotentialArchetype *> type,
RequirementSource source) {
switch (kind) {
case RequirementKind::Conformance:
case RequirementKind::Superclass:
out << "\n ";
out << archetype->getDebugName() << " : "
<< type.get<Type>().getString() << " [";
source.dump(out, &Context.SourceMgr);
out << "]";
break;
case RequirementKind::SameType:
out << "\n ";
out << archetype->getDebugName() << " == " ;
if (auto secondType = type.dyn_cast<Type>()) {
out << secondType.getString();
} else {
out << type.get<PotentialArchetype *>()->getDebugName();
}
out << " [";
source.dump(out, &Context.SourceMgr);
out << "]";
break;
case RequirementKind::WitnessMarker:
out << "\n " << archetype->getDebugName() << " witness marker";
break;
}
});
out << "\n";
}
Type ArchetypeBuilder::mapTypeIntoContext(const DeclContext *dc, Type type,
LazyResolver *resolver) {
auto genericParams = dc->getGenericParamsOfContext();
return mapTypeIntoContext(dc->getParentModule(), genericParams, type,
resolver);
}
Type ArchetypeBuilder::mapTypeIntoContext(Module *M,
GenericParamList *genericParams,
Type type,
LazyResolver *resolver) {
auto canType = type->getCanonicalType();
assert(!canType->hasArchetype() && "already have a contextual type");
if (!canType->hasTypeParameter())
return type;
assert(genericParams && "dependent type in non-generic context");
unsigned genericParamsDepth = genericParams->getDepth();
type = type.transform([&](Type type) -> Type {
// Map a generic parameter type to its archetype.
if (auto gpType = type->getAs<GenericTypeParamType>()) {
auto index = gpType->getIndex();
unsigned depth = gpType->getDepth();
// Skip down to the generic parameter list that houses the corresponding
// generic parameter.
auto myGenericParams = genericParams;
assert(genericParamsDepth >= depth);
unsigned skipLevels = genericParamsDepth - depth;
while (skipLevels > 0) {
myGenericParams = myGenericParams->getOuterParameters();
assert(myGenericParams && "Wrong number of levels?");
--skipLevels;
}
// Return the archetype.
// FIXME: Use the allArchetypes vector instead of the generic param if
// available because of cross-module archetype serialization woes.
if (!myGenericParams->getAllArchetypes().empty())
return myGenericParams->getPrimaryArchetypes()[index];
// During type-checking, we may try to mapTypeIntoContext before
// AllArchetypes has been built, so fall back to the generic params.
return myGenericParams->getParams()[index]->getArchetype();
}
// Map a dependent member to the corresponding nested archetype.
if (auto dependentMember = type->getAs<DependentMemberType>()) {
auto base = mapTypeIntoContext(M, genericParams,
dependentMember->getBase(), resolver);
return dependentMember->substBaseType(M, base, resolver);
}
return type;
});
assert(!type->hasTypeParameter() && "not fully substituted");
return type;
}
Type
ArchetypeBuilder::mapTypeOutOfContext(const DeclContext *dc, Type type) {
GenericParamList *genericParams = dc->getGenericParamsOfContext();
return mapTypeOutOfContext(dc->getParentModule(), genericParams, type);
}
Type ArchetypeBuilder::mapTypeOutOfContext(ModuleDecl *M,
GenericParamList *genericParams,
Type type) {
auto canType = type->getCanonicalType();
assert(!canType->hasTypeParameter() && "already have an interface type");
if (!canType->hasArchetype())
return type;
assert(genericParams && "dependent type in non-generic context");
// Capture the archetype -> interface type mapping.
TypeSubstitutionMap subs;
for (auto params = genericParams; params != nullptr;
params = params->getOuterParameters()) {
for (auto param : *params) {
subs[param->getArchetype()] = param->getDeclaredType();
}
}
type = type.subst(M, subs, SubstFlags::AllowLoweredTypes);
assert(!type->hasArchetype() && "not fully substituted");
return type;
}
bool ArchetypeBuilder::addGenericSignature(GenericSignature *sig,
bool adoptArchetypes,
bool treatRequirementsAsExplicit) {
if (!sig) return false;
RequirementSource::Kind sourceKind = treatRequirementsAsExplicit
? RequirementSource::Explicit
: RequirementSource::OuterScope;
for (auto param : sig->getGenericParams()) {
if (addGenericParameter(param))
return true;
if (adoptArchetypes) {
// If this generic parameter has an archetype, use it as the concrete
// type.
// FIXME: This forces us to re-use archetypes from outer scopes as
// concrete types, which is currently important for the layout of the "all
// archetypes" list.
if (auto gpDecl = param->getDecl()) {
if (auto archetype = gpDecl->getArchetype()) {
auto key = GenericTypeParamKey::forDecl(gpDecl);
assert(Impl->PotentialArchetypes.count(key) && "Missing parameter?");
auto *pa = Impl->PotentialArchetypes[key];
assert(pa == pa->getRepresentative() && "Not the representative");
pa->ArchetypeOrConcreteType = NestedType::forConcreteType(archetype);
pa->SameTypeSource = RequirementSource(sourceKind, SourceLoc());
}
}
}
}
RequirementSource source(sourceKind, SourceLoc());
for (auto &reqt : sig->getRequirements()) {
addRequirement(reqt, source);
}
return false;
}
Type ArchetypeBuilder::substDependentType(Type type) {
return substConcreteTypesForDependentTypes(*this, type);
}
/// Add the requirements for the given potential archetype and its nested
/// potential archetypes to the set of requirements.
static void
addRequirements(
ArchetypeBuilder &builder, Type type,
ArchetypeBuilder::PotentialArchetype *pa,
llvm::SmallPtrSet<ArchetypeBuilder::PotentialArchetype *, 16> &knownPAs,
SmallVectorImpl<Requirement> &requirements) {
auto &ctx = builder.getASTContext();
// If the potential archetype has been bound away to a concrete type,
// it needs no requirements.
if (pa->isConcreteType())
return;
// Add a value witness marker.
requirements.push_back(Requirement(RequirementKind::WitnessMarker,
type, Type()));
// Add superclass requirement, if needed.
if (auto superclass = pa->getSuperclass()) {
// FIXME: What if the superclass type involves a type parameter?
requirements.push_back(Requirement(RequirementKind::Superclass,
type, superclass));
}
// Add conformance requirements.
SmallVector<ProtocolDecl *, 4> protocols;
for (const auto &conforms : pa->getConformsTo()) {
protocols.push_back(conforms.first);
}
ProtocolType::canonicalizeProtocols(protocols);
for (auto proto : protocols) {
requirements.push_back(Requirement(RequirementKind::Conformance, type,
ProtocolType::get(proto, ctx)));
}
}
static void
addNestedRequirements(
ArchetypeBuilder &builder,
ArchetypeBuilder::PotentialArchetype *pa,
llvm::SmallPtrSet<ArchetypeBuilder::PotentialArchetype *, 16> &knownPAs,
SmallVectorImpl<Requirement> &requirements) {
using PotentialArchetype = ArchetypeBuilder::PotentialArchetype;
// Collect the nested types, sorted by name.
// FIXME: Could collect these from the conformance requirements, above.
SmallVector<std::pair<Identifier, PotentialArchetype*>, 16> nestedTypes;
for (const auto &nested : pa->getNestedTypes()) {
// FIXME: Dropping requirements among different associated types of the
// same name.
// Skip type aliases, which are just shortcuts down the tree.
if (nested.second.front()->getTypeAliasDecl())
continue;
nestedTypes.push_back(std::make_pair(nested.first, nested.second.front()));
}
std::sort(nestedTypes.begin(), nestedTypes.end(),
OrderPotentialArchetypeByName());
// Add requirements for associated types.
for (const auto &nested : nestedTypes) {
auto rep = nested.second->getRepresentative();
if (knownPAs.insert(rep).second) {
// Form the dependent type that refers to this archetype.
auto assocType = nested.second->getResolvedAssociatedType();
if (!assocType)
continue; // FIXME: If we do this late enough, there will be no failure.
// Skip nested types bound to concrete types.
if (rep->isConcreteType())
continue;
auto nestedType =
rep->getDependentType(builder, /*allowUnresolved*/ false);
addRequirements(builder, nestedType, rep, knownPAs, requirements);
addNestedRequirements(builder, rep, knownPAs, requirements);
}
}
}
/// Collect the set of requirements placed on the given generic parameters and
/// their associated types.
static void collectRequirements(ArchetypeBuilder &builder,
ArrayRef<GenericTypeParamType *> params,
SmallVectorImpl<Requirement> &requirements) {
typedef ArchetypeBuilder::PotentialArchetype PotentialArchetype;
// Find the "primary" potential archetypes, from which we'll collect all
// of the requirements.
llvm::SmallPtrSet<PotentialArchetype *, 16> knownPAs;
llvm::SmallVector<GenericTypeParamType *, 8> primary;
for (auto param : params) {
auto pa = builder.resolveArchetype(param);
assert(pa && "Missing potential archetype for generic parameter");
// We only care about the representative.
pa = pa->getRepresentative();
if (knownPAs.insert(pa).second)
primary.push_back(param);
}
// Add all of the conformance and superclass requirements placed on the given
// generic parameters and their associated types.
unsigned primaryIdx = 0, numPrimary = primary.size();
while (primaryIdx < numPrimary) {
unsigned depth = primary[primaryIdx]->getDepth();
// For each of the primary potential archetypes, add the requirements.
// Stop when we hit a parameter at a different depth.
// FIXME: This algorithm falls out from the way the "all archetypes" lists
// are structured. Once those lists no longer exist or are no longer
// "the truth", we can simplify this algorithm considerably.
unsigned lastPrimaryIdx = primaryIdx;
for (unsigned idx = primaryIdx;
idx < numPrimary && primary[idx]->getDepth() == depth;
++idx, ++lastPrimaryIdx) {
auto param = primary[idx];
auto pa = builder.resolveArchetype(param)->getRepresentative();
// Add other requirements.
addRequirements(builder, param, pa, knownPAs, requirements);
}
// For each of the primary potential archetypes, add the nested requirements.
for (unsigned idx = primaryIdx; idx < lastPrimaryIdx; ++idx) {
auto param = primary[idx];
auto pa = builder.resolveArchetype(param)->getRepresentative();
addNestedRequirements(builder, pa, knownPAs, requirements);
}
primaryIdx = lastPrimaryIdx;
}
// Add all of the same-type requirements.
for (auto req : builder.getSameTypeRequirements()) {
auto firstType = req.first->getDependentType(builder, false);
Type secondType;
if (auto concrete = req.second.dyn_cast<Type>())
secondType = concrete;
else if (auto secondPA = req.second.dyn_cast<PotentialArchetype*>())
secondType = secondPA->getDependentType(builder, false);
if (firstType->is<ErrorType>() || secondType->is<ErrorType>() ||
firstType->isEqual(secondType))
continue;
requirements.push_back(Requirement(RequirementKind::SameType,
firstType, secondType));
}
}
GenericSignature *ArchetypeBuilder::getGenericSignature(
ArrayRef<GenericTypeParamType *> genericParamTypes) {
// Collect the requirements placed on the generic parameter types.
SmallVector<Requirement, 4> requirements;
collectRequirements(*this, genericParamTypes, requirements);
auto sig = GenericSignature::get(genericParamTypes, requirements);
return sig;
}