Merge pull request #15172 from DougGregor/gsb-weaken-potential-archetypes
[GSB] Reduce dependence on potential archetypes for rewrite tree
diff --git a/include/swift/AST/GenericSignatureBuilder.h b/include/swift/AST/GenericSignatureBuilder.h
index 7eb4f11..6cf3b17 100644
--- a/include/swift/AST/GenericSignatureBuilder.h
+++ b/include/swift/AST/GenericSignatureBuilder.h
@@ -445,19 +445,16 @@
/// Note that we have added the nested type nestedPA
void addedNestedType(PotentialArchetype *nestedPA);
- /// Add a rewrite rule that makes \c otherPA a part of the given equivalence
- /// class.
+ /// Add a rewrite rule from that makes the two types equivalent.
///
/// \returns true if a new rewrite rule was added, and false otherwise.
- bool addSameTypeRewriteRule(EquivalenceClass *equivClass,
- PotentialArchetype *otherPA);
+ bool addSameTypeRewriteRule(CanType type1, CanType type2);
- /// \brief Add a new conformance requirement specifying that the given
- /// potential archetypes are equivalent.
- ConstraintResult addSameTypeRequirementBetweenArchetypes(
- PotentialArchetype *T1,
- PotentialArchetype *T2,
- const RequirementSource *Source);
+ /// \brief Add a same-type requirement between two types that are known to
+ /// refer to type parameters.
+ ConstraintResult addSameTypeRequirementBetweenTypeParameters(
+ ResolvedType type1, ResolvedType type2,
+ const RequirementSource *source);
/// \brief Add a new conformance requirement specifying that the given
/// potential archetype is bound to a concrete type.
@@ -811,9 +808,6 @@
bool areInSameEquivalenceClass(Type type1, Type type2);
/// Simplify the given dependent type down to its canonical representation.
- ///
- /// \returns null if the type involved dependent member types that
- /// don't have associated types.
Type getCanonicalTypeParameter(Type type);
/// For each requirement in \c sig, create a new signature without it and see
diff --git a/lib/AST/GenericSignatureBuilder.cpp b/lib/AST/GenericSignatureBuilder.cpp
index 4154b8c..158ab66 100644
--- a/lib/AST/GenericSignatureBuilder.cpp
+++ b/lib/AST/GenericSignatureBuilder.cpp
@@ -166,17 +166,17 @@
///
/// \returns the path, or None if it contained unresolved dependent member
/// types.
- Optional<RewritePath> static createPath(Type type);
+ RewritePath static createPath(Type type);
/// Decompose a type into a path.
///
/// \param path Will be filled in with the components of the path, in
/// reverse order.
///
- /// \returns the generic parameter at the start of the path, or \c None if
- ///
- Optional<GenericParamKey>
- static createPath(Type type, SmallVectorImpl<AssociatedTypeDecl *> &path);
+ /// \returns the generic parameter at the start of the path.
+ static GenericParamKey createPath(
+ Type type,
+ SmallVectorImpl<AssociatedTypeDecl *> &path);
/// Compute the longer common prefix between this path and \c other.
RewritePath commonPath(const RewritePath &other) const;
@@ -216,11 +216,11 @@
EquivalenceClass &equivClass)
: builder(builder), equivClass(equivClass) { }
- Optional<RewritePath> getAnchorPath() {
- if (anchorPath) return anchorPath;
+ const RewritePath &getAnchorPath() {
+ if (anchorPath) return *anchorPath;
anchorPath = RewritePath::createPath(equivClass.getAnchor(builder, { }));
- return anchorPath;
+ return *anchorPath;
}
};
@@ -437,9 +437,9 @@
/// Equivalence classes that are not currently being used.
std::vector<void *> FreeEquivalenceClasses;
- /// The roots of the rewrite tree.
- DenseMap<const EquivalenceClass *, std::unique_ptr<RewriteTreeNode>>
- RewriteTreeRoots;
+ /// The roots of the rewrite tree, keyed on the canonical, dependent
+ /// types.
+ DenseMap<CanType, std::unique_ptr<RewriteTreeNode>> RewriteTreeRoots;
/// The generation number for the term-rewriting system, which is
/// increased every time a new rule gets added.
@@ -482,15 +482,12 @@
/// Deallocate the given equivalence class, returning it to the free list.
void deallocateEquivalenceClass(EquivalenceClass *equivClass);
- /// Retrieve the rewrite tree root for the given equivalence class,
- /// if present.
- RewriteTreeNode *getRewriteTreeRootIfPresent(
- const EquivalenceClass *equivClass);
+ /// Retrieve the rewrite tree root for the given anchor type.
+ RewriteTreeNode *getRewriteTreeRootIfPresent(CanType anchor);
- /// Retrieve the rewrite tree root for the given equivalence class,
+ /// Retrieve the rewrite tree root for the given anchor type,
/// creating it if needed.
- RewriteTreeNode *getOrCreateRewriteTreeRoot(
- const EquivalenceClass *equivClass);
+ RewriteTreeNode *getOrCreateRewriteTreeRoot(CanType anchor);
/// Minimize the rewrite tree by minimizing the right-hand sides and
/// removing redundant rules.
@@ -2293,8 +2290,8 @@
bool updatedAnchor = false;
for (auto member : members) {
auto anchorType =
- builder.getCanonicalTypeParameter(member->getDependentType(genericParams));
- if (!anchorType) continue;
+ builder.getCanonicalTypeParameter(
+ member->getDependentType(genericParams));
#ifndef NDEBUG
// Check that we get consistent results from all of the anchors.
@@ -2493,7 +2490,11 @@
out << "\n";
if (builder) {
- if (auto rewriteRoot = builder->Impl->getRewriteTreeRootIfPresent(this)) {
+ CanType anchorType =
+ const_cast<EquivalenceClass *>(this)->getAnchor(*builder, { })
+ ->getCanonicalType();
+ if (auto rewriteRoot =
+ builder->Impl->getRewriteTreeRootIfPresent(anchorType)) {
out << "---Rewrite tree---\n";
rewriteRoot->dump(out);
}
@@ -3173,30 +3174,23 @@
}
}
-Optional<RewritePath> RewritePath::createPath(Type type) {
+RewritePath RewritePath::createPath(Type type) {
SmallVector<AssociatedTypeDecl *, 4> path;
- if (auto genericParam = createPath(type, path)) {
- return RewritePath(*genericParam, path, Reverse);
- }
-
- return None;
+ auto genericParam = createPath(type, path);
+ return RewritePath(genericParam, path, Reverse);
}
-Optional<GenericParamKey>
-RewritePath::createPath(Type type,
- SmallVectorImpl<AssociatedTypeDecl *> &path) {
+GenericParamKey RewritePath::createPath(
+ Type type,
+ SmallVectorImpl<AssociatedTypeDecl *> &path) {
while (auto depMemTy = type->getAs<DependentMemberType>()) {
auto assocType = depMemTy->getAssocType();
- if (!assocType) return None;
-
+ assert(assocType && "Unresolved dependent member type");
path.push_back(assocType);
type = depMemTy->getBase();
}
- auto genericParam = type->getAs<GenericTypeParamType>();
- if (!genericParam) return None;
-
- return GenericParamKey(genericParam);
+ return type->castTo<GenericTypeParamType>();
}
RewritePath RewritePath::commonPath(const RewritePath &other) const {
@@ -3244,15 +3238,14 @@
return CanType(::formDependentType(ctx, *base, getPath()));
assert(anchorPathCache && "Need an anchor path cache");
- Optional<RewritePath> anchorPath = anchorPathCache->getAnchorPath();
- if (!anchorPath) return CanType();
+ const RewritePath &anchorPath = anchorPathCache->getAnchorPath();
// Add the relative path to the anchor path.
SmallVector<AssociatedTypeDecl *, 4> absolutePath;
- absolutePath.append(anchorPath->getPath().begin(),
- anchorPath->getPath().end());
+ absolutePath.append(anchorPath.getPath().begin(),
+ anchorPath.getPath().end());
absolutePath.append(getPath().begin(), getPath().end());
- return CanType(::formDependentType(ctx, *anchorPath->getBase(),
+ return CanType(::formDependentType(ctx, *anchorPath.getBase(),
absolutePath));
}
@@ -3551,8 +3544,8 @@
RewriteTreeNode *
GenericSignatureBuilder::Implementation::getRewriteTreeRootIfPresent(
- const EquivalenceClass *equivClass) {
- auto known = RewriteTreeRoots.find(equivClass);
+ CanType anchor) {
+ auto known = RewriteTreeRoots.find(anchor);
if (known != RewriteTreeRoots.end()) return known->second.get();
return nullptr;
@@ -3560,11 +3553,11 @@
RewriteTreeNode *
GenericSignatureBuilder::Implementation::getOrCreateRewriteTreeRoot(
- const EquivalenceClass *equivClass) {
- auto known = RewriteTreeRoots.find(equivClass);
+ CanType anchor) {
+ auto known = RewriteTreeRoots.find(anchor);
if (known != RewriteTreeRoots.end()) return known->second.get();
- auto &root = RewriteTreeRoots[equivClass];
+ auto &root = RewriteTreeRoots[anchor];
root = std::unique_ptr<RewriteTreeNode>(new RewriteTreeNode(nullptr));
return root.get();
}
@@ -3593,7 +3586,8 @@
// Minimize the right-hand sides of each rule in the tree.
for (auto &equivClass : EquivalenceClasses) {
- auto root = RewriteTreeRoots.find(&equivClass);
+ CanType anchorType = equivClass.getAnchor(builder, { })->getCanonicalType();
+ auto root = RewriteTreeRoots.find(anchorType);
if (root == RewriteTreeRoots.end()) continue;
AnchorPathCache anchorPathCache(builder, equivClass);
@@ -3618,9 +3612,9 @@
++NumRewriteRhsSimplified;
// Determine replacement path, which might be relative to the anchor.
- auto canonicalRhsPath = *RewritePath::createPath(canonicalRhsType);
+ auto canonicalRhsPath = RewritePath::createPath(canonicalRhsType);
auto anchorPath = anchorPathCache.getAnchorPath();
- if (auto prefix = anchorPath->commonPath(canonicalRhsPath)) {
+ if (auto prefix = anchorPath.commonPath(canonicalRhsPath)) {
unsigned prefixLength = prefix.getPath().size();
RelativeRewritePath replacementRhsPath =
canonicalRhsPath.getPath().slice(prefixLength);
@@ -3648,7 +3642,8 @@
// Minimize the right-hand sides of each rule in the tree.
for (auto &equivClass : EquivalenceClasses) {
- auto root = RewriteTreeRoots.find(&equivClass);
+ CanType anchorType = equivClass.getAnchor(builder, { })->getCanonicalType();
+ auto root = RewriteTreeRoots.find(anchorType);
if (root == RewriteTreeRoots.end()) continue;
AnchorPathCache anchorPathCache(builder, equivClass);
@@ -3663,7 +3658,6 @@
// Simplify the left-hand type.
Type simplifiedLhsType = builder.getCanonicalTypeParameter(lhsType);
- if (!simplifiedLhsType) return RewriteTreeNode::RuleAction::none();
// Compute the type of the right-hand side.
Type rhsType = rhs.formDependentType(ctx, &anchorPathCache);
@@ -3680,25 +3674,13 @@
}
}
-bool GenericSignatureBuilder::addSameTypeRewriteRule(
- EquivalenceClass *equivClass,
- PotentialArchetype *otherPA){
- // Simplify both sides in the hope of uncovering a common path.
- Type simplifiedType1 = equivClass->getAnchor(*this, { });
- if (!simplifiedType1) return false;
-
- Type simplifiedType2;
- if (auto otherEquivClass = otherPA->getEquivalenceClassIfPresent())
- simplifiedType2 = otherEquivClass->getAnchor(*this, { });
- else
- simplifiedType2 = getCanonicalTypeParameter(otherPA->getDependentType({ }));
- if (!simplifiedType2) return false;
-
+bool GenericSignatureBuilder::addSameTypeRewriteRule(CanType type1,
+ CanType type2) {
// We already effectively have this rewrite rule.
- if (simplifiedType1->isEqual(simplifiedType2)) return false;
+ if (type1 == type2) return false;
- auto path1 = *RewritePath::createPath(simplifiedType1);
- auto path2 = *RewritePath::createPath(simplifiedType2);
+ auto path1 = RewritePath::createPath(type1);
+ auto path2 = RewritePath::createPath(type2);
// Look for a common prefix. When we have one, form a rewrite rule using
// relative paths.
@@ -3712,14 +3694,13 @@
if (compareDependentPaths(relPath1, relPath2) < 0)
std::swap(relPath1, relPath2);
- // Find the equivalence class for the prefix.
+ // Find the anchor for the prefix.
CanType commonType = prefix.formDependentType(getASTContext());
- auto equivClass =
- resolveEquivalenceClass(commonType, ArchetypeResolutionKind::WellFormed);
- assert(equivClass && "Prefix cannot be resolved?");
+ CanType commonAnchor =
+ getCanonicalTypeParameter(commonType)->getCanonicalType();
// Add the rewrite rule.
- auto root = Impl->getOrCreateRewriteTreeRoot(equivClass);
+ auto root = Impl->getOrCreateRewriteTreeRoot(commonAnchor);
return root->addRewriteRule(
relPath1,
RewritePath(None, relPath2, RewritePath::Forward));
@@ -3728,44 +3709,36 @@
// Otherwise, form a rewrite rule with absolute paths.
// Find the better path and make sure it's in path2.
- if (compareDependentTypes(simplifiedType1, simplifiedType2) < 0) {
+ if (compareDependentTypes(type1, type2) < 0) {
std::swap(path1, path2);
- std::swap(simplifiedType1, simplifiedType2);
+ std::swap(type1, type2);
}
// Add the rewrite rule.
Type firstBase =
GenericTypeParamType::get(path1.getBase()->Depth, path1.getBase()->Index,
getASTContext());
- auto baseEquivClass =
- resolveEquivalenceClass(firstBase, ArchetypeResolutionKind::WellFormed);
- assert(baseEquivClass && "Base cannot be resolved?");
-
- auto root = Impl->getOrCreateRewriteTreeRoot(baseEquivClass);
+ CanType baseAnchor =
+ getCanonicalTypeParameter(firstBase)->getCanonicalType();
+ auto root = Impl->getOrCreateRewriteTreeRoot(baseAnchor);
return root->addRewriteRule(path1.getPath(), path2);
}
Type GenericSignatureBuilder::getCanonicalTypeParameter(Type type) {
auto initialPath = RewritePath::createPath(type);
- if (!initialPath) return nullptr;
-
auto genericParamType =
- GenericTypeParamType::get(initialPath->getBase()->Depth,
- initialPath->getBase()->Index,
+ GenericTypeParamType::get(initialPath.getBase()->Depth,
+ initialPath.getBase()->Index,
getASTContext());
- auto initialEquivClass =
- resolveEquivalenceClass(genericParamType,
- ArchetypeResolutionKind::WellFormed);
- if (!initialEquivClass) return nullptr;
unsigned startIndex = 0;
- auto equivClass = initialEquivClass;
Type currentType = genericParamType;
- SmallVector<AssociatedTypeDecl *, 4> path(initialPath->getPath().begin(),
- initialPath->getPath().end());
+ SmallVector<AssociatedTypeDecl *, 4> path(initialPath.getPath().begin(),
+ initialPath.getPath().end());
bool simplified = false;
do {
- if (auto rootNode = Impl->getRewriteTreeRootIfPresent(equivClass)) {
+ CanType currentAnchor = currentType->getCanonicalType();
+ if (auto rootNode = Impl->getRewriteTreeRootIfPresent(currentAnchor)) {
// Find the best rewrite rule for the path starting at startIndex.
auto match =
rootNode->bestRewritePath(genericParamType,
@@ -3795,17 +3768,12 @@
genericParamType =
GenericTypeParamType::get(newBase->Depth, newBase->Index,
getASTContext());
- initialEquivClass =
- resolveEquivalenceClass(genericParamType,
- ArchetypeResolutionKind::WellFormed);
- assert(initialEquivClass && "Must have an equivalence class");
}
// Move back to the beginning; we may have opened up other rewrites.
simplified = true;
startIndex = 0;
currentType = genericParamType;
- equivClass = initialEquivClass;
continue;
}
}
@@ -3813,12 +3781,7 @@
// If we've hit the end of the path, we're done.
if (startIndex >= path.size()) break;
- // FIXME: It would be nice if there were a better way to get the equivalence
- // class of a named nested type.
currentType = DependentMemberType::get(currentType, path[startIndex++]);
- equivClass =
- resolveEquivalenceClass(currentType, ArchetypeResolutionKind::WellFormed);
- if (!equivClass) break;
} while (true);
return formDependentType(genericParamType, path);
@@ -4865,14 +4828,18 @@
}
ConstraintResult
-GenericSignatureBuilder::addSameTypeRequirementBetweenArchetypes(
- PotentialArchetype *OrigT1,
- PotentialArchetype *OrigT2,
- const RequirementSource *Source)
+GenericSignatureBuilder::addSameTypeRequirementBetweenTypeParameters(
+ ResolvedType type1, ResolvedType type2,
+ const RequirementSource *source)
{
+ // Both sides are type parameters; equate them.
+ // FIXME: Realizes potential archetypes far too early.
+ auto OrigT1 = type1.realizePotentialArchetype(*this);
+ auto OrigT2 = type2.realizePotentialArchetype(*this);
+
// Record the same-type constraint, and bail out if it was already known.
if (!OrigT1->getOrCreateEquivalenceClass(*this)
- ->recordSameTypeConstraint(OrigT1, OrigT2, Source))
+ ->recordSameTypeConstraint(OrigT1, OrigT2, source))
return ConstraintResult::Resolved;
// Operate on the representatives
@@ -4889,10 +4856,15 @@
std::swap(OrigT1, OrigT2);
}
- // Add a rewrite rule to map T2 down to the anchor.
auto equivClass = T1->getOrCreateEquivalenceClass(*this);
- if (addSameTypeRewriteRule(equivClass, T2))
- ++Impl->RewriteGeneration;
+ auto equivClass2 = T2->getEquivalenceClassIfPresent();
+
+ // Determine the anchor types of the two equivalence classes.
+ CanType anchor1 = equivClass->getAnchor(*this, { })->getCanonicalType();
+ CanType anchor2 =
+ (equivClass2 ? equivClass2->getAnchor(*this, { })
+ : getCanonicalTypeParameter(T2->getDependentType({ })))
+ ->getCanonicalType();
// Merge the equivalence classes.
equivClass->modified(*this);
@@ -4902,7 +4874,6 @@
equivClass->addMember(equiv);
// Grab the old equivalence class, if present. We'll deallocate it at the end.
- auto equivClass2 = T2->getEquivalenceClassIfPresent();
SWIFT_DEFER {
if (equivClass2)
Impl->deallocateEquivalenceClass(equivClass2);
@@ -4918,31 +4889,35 @@
equivClass->sameTypeConstraints.end(),
equivClass2->sameTypeConstraints.begin(),
equivClass2->sameTypeConstraints.end());
+ }
- // Combine the rewrite rules.
- if (auto rewriteRoot2 = Impl->getOrCreateRewriteTreeRoot(equivClass2)) {
- if (auto rewriteRoot1 = Impl->getOrCreateRewriteTreeRoot(equivClass)) {
- // Merge the second rewrite tree into the first.
- if (rewriteRoot2->mergeInto(rewriteRoot1))
- ++Impl->RewriteGeneration;
- Impl->RewriteTreeRoots.erase(equivClass2);
- } else {
- // Take the second rewrite tree and make it the first.
- auto root2Entry = Impl->RewriteTreeRoots.find(equivClass2);
- auto root2Ptr = std::move(root2Entry->second);
- Impl->RewriteTreeRoots.erase(root2Entry);
- (void)Impl->RewriteTreeRoots.insert({equivClass, std::move(root2Ptr)});
- }
+ // Combine the rewrite rules.
+ if (auto rewriteRoot2 = Impl->getOrCreateRewriteTreeRoot(anchor2)) {
+ if (auto rewriteRoot1 = Impl->getOrCreateRewriteTreeRoot(anchor1)) {
+ // Merge the second rewrite tree into the first.
+ if (rewriteRoot2->mergeInto(rewriteRoot1))
+ ++Impl->RewriteGeneration;
+ Impl->RewriteTreeRoots.erase(anchor2);
+ } else {
+ // Take the second rewrite tree and make it the first.
+ auto root2Entry = Impl->RewriteTreeRoots.find(anchor2);
+ auto root2Ptr = std::move(root2Entry->second);
+ Impl->RewriteTreeRoots.erase(root2Entry);
+ (void)Impl->RewriteTreeRoots.insert({anchor1, std::move(root2Ptr)});
}
}
+ // Add a rewrite rule to map the anchor of T2 down to the anchor of T1.
+ if (addSameTypeRewriteRule(anchor2, anchor1))
+ ++Impl->RewriteGeneration;
+
// Same-type-to-concrete requirements.
bool t1IsConcrete = !equivClass->concreteType.isNull();
bool t2IsConcrete = equivClass2 && !equivClass2->concreteType.isNull();
if (t2IsConcrete) {
if (t1IsConcrete) {
(void)addSameTypeRequirement(equivClass->concreteType,
- equivClass2->concreteType, Source,
+ equivClass2->concreteType, source,
UnresolvedHandlingKind::GenerateConstraints,
SameTypeConflictCheckedLater());
} else {
@@ -5187,15 +5162,9 @@
source.getSource(*this, type1.getDependentType(*this)));
}
- // Both sides are type parameters; equate them.
- // FIXME: Realizes potential archetypes far too early.
- auto pa1 = type1.realizePotentialArchetype(*this);
- auto pa2 = type2.realizePotentialArchetype(*this);
-
- return addSameTypeRequirementBetweenArchetypes(
- pa1, pa2,
- source.getSource(*this,
- type2.getDependentType(*this)));
+ return addSameTypeRequirementBetweenTypeParameters(
+ type1, type2,
+ source.getSource(*this, type2.getDependentType(*this)));
}
ConstraintResult GenericSignatureBuilder::addInheritedRequirements(
