mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
edca7c85ad
Convert a bunch of places where we're dumping to stderr and calling `abort` over to using `ABORT` such that the message gets printed to the pretty stack trace. This ensures it gets picked up by CrashReporter.
482 lines
17 KiB
C++
482 lines
17 KiB
C++
//===--- PropertyMap.cpp - Collects properties of type parameters ---------===//
|
|
//
|
|
// This source file is part of the Swift.org open source project
|
|
//
|
|
// Copyright (c) 2021 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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
//
|
|
// The property map is used to answer generic signature queries. It also
|
|
// implements special behaviors of layout, superclass, and concrete type
|
|
// requirements in the Swift language.
|
|
//
|
|
// # Property map construction
|
|
//
|
|
// Property map construction can add new rewrite rules when performing
|
|
// property unification and nested type concretization, so it is iterated
|
|
// until fixed point with the Knuth-Bendix algorithm. A third step, known as
|
|
// substitution simplification is also performed.
|
|
//
|
|
// The Knuth-Bendix completion procedure is implemented in KnuthBendix.cpp.
|
|
// Substitution simplification is implemented in SimplifySubstitutions.cpp.
|
|
//
|
|
// # Property map theory
|
|
//
|
|
// In the rewrite system, a conformance requirement 'T : P' is represented as
|
|
// rewrite rule of the form:
|
|
//
|
|
// T.[P] => T
|
|
//
|
|
// Similarly, layout, superclass, and concrete-type requirements are represented
|
|
// by a rewrite rule of the form:
|
|
//
|
|
// T.[p] => T
|
|
//
|
|
// Where [p] is a "property symbol": [layout: L], [superclass: Foo],
|
|
// [concrete: Bar].
|
|
//
|
|
// Given an arbitrary type T and a property [p], we can check if T satisfies the
|
|
// property by checking if the two terms T.[p] and T reduce to the same term T'.
|
|
// That is, if our rewrite rules allow us to eliminate the [p] suffix, we know
|
|
// the type satisfies [p].
|
|
//
|
|
// However, the question then becomes, given an arbitrary type T, how do we find
|
|
// *all* properties [p] satisfied by T?
|
|
//
|
|
// The trick is that we can take advantage of confluence here.
|
|
//
|
|
// If T.[p] => T', and T => T'', then it must follow that T''.[p] => T'.
|
|
// Furthermore, since T'' is fully reduced, T'' == T'. So T'' == UV for some
|
|
// terms U and V, and there exist be a rewrite rule V.[p] => V' in the system.
|
|
//
|
|
// Therefore, in order to find all [p] satisfied by T, we start by fully reducing
|
|
// T, then we look for rules of the form V.[p] => V' where V is fully reduced,
|
|
// and a suffix of T.
|
|
//
|
|
// This is the idea behind the property map. We collect all rules of the form
|
|
// V.[p] => V into a multi-map keyed by V. Then given an arbitrary type T,
|
|
// we can reduce it and look up successive suffixes to find all properties [p]
|
|
// satisfied by T.
|
|
//
|
|
// # Property map implementation
|
|
//
|
|
// A set of property rules (V.[p1] => V), (V.[p2] => V), ... become a single
|
|
// entry in the property map corresponding to V that stores information about
|
|
// the properties [pN].
|
|
//
|
|
// The property map is indexed by a suffix trie, where the properties of a term
|
|
// T are found by traversing a trie, starting from the _last_ symbol of T, which
|
|
// is a key for the root of the trie. This is done since we might have an entry
|
|
// for a suffix of T, but not T itself.
|
|
//
|
|
// For example, if a conformance requirement 'A : Q' in protocol P becomes a
|
|
// rule ([P:A].[Q] => [P:A]). The term τ_0_0.[P:A], corresponding to the nested
|
|
// type 'A' of a generic parameter 'τ_0_0', might not have a property map entry
|
|
// of its own, if the only requirements on it are those implied by [P:A].
|
|
//
|
|
// In this case, a property map lookup for τ_0_0.[P:A] will find an entry for
|
|
// the term [P:A].
|
|
//
|
|
// If multiple suffixes of a term T appear in the property map, the lookup
|
|
// returns the entry for the _longest_ matching suffix. An important invariant
|
|
// maintained during property map construction is that the contents of a
|
|
// property map entry from a key V are copied into the entry for a key T
|
|
// where T == U.V for some U. This means property map entries for longer
|
|
// suffixes "inherit" the contents of entries for shorter suffixes.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "swift/AST/Decl.h"
|
|
#include "swift/AST/ProtocolConformance.h"
|
|
#include "swift/AST/Types.h"
|
|
#include "swift/Basic/Assertions.h"
|
|
#include "llvm/Support/raw_ostream.h"
|
|
#include <algorithm>
|
|
#include <vector>
|
|
|
|
#include "PropertyMap.h"
|
|
|
|
using namespace swift;
|
|
using namespace rewriting;
|
|
|
|
void PropertyBag::dump(llvm::raw_ostream &out) const {
|
|
out << Key << " => {";
|
|
|
|
if (!ConformsTo.empty()) {
|
|
out << " conforms_to: [";
|
|
bool first = true;
|
|
for (const auto *proto : ConformsTo) {
|
|
if (first)
|
|
first = false;
|
|
else
|
|
out << " ";
|
|
out << proto->getName();
|
|
}
|
|
out << "]";
|
|
}
|
|
|
|
if (Layout) {
|
|
out << " layout: " << Layout;
|
|
}
|
|
|
|
if (hasSuperclassBound()) {
|
|
const auto &superclassReq = getSuperclassRequirement();
|
|
out << " superclass: " << *superclassReq.SuperclassType;
|
|
}
|
|
|
|
if (isConcreteType()) {
|
|
out << " concrete_type: " << *ConcreteType;
|
|
}
|
|
|
|
out << " }";
|
|
}
|
|
|
|
/// Given a term \p lookupTerm whose suffix must equal this property bag's
|
|
/// key, return a new term with that suffix stripped off. Will be empty if
|
|
/// \p lookupTerm exactly equals the key.
|
|
MutableTerm
|
|
PropertyBag::getPrefixAfterStrippingKey(const MutableTerm &lookupTerm) const {
|
|
ASSERT(lookupTerm.size() >= Key.size());
|
|
auto prefixBegin = lookupTerm.begin();
|
|
auto prefixEnd = lookupTerm.end() - Key.size();
|
|
DEBUG_ASSERT(std::equal(prefixEnd, lookupTerm.end(), Key.begin()) &&
|
|
"This is not the bag you're looking for");
|
|
return MutableTerm(prefixBegin, prefixEnd);
|
|
}
|
|
|
|
/// Get the superclass bound for \p lookupTerm, whose suffix must be the term
|
|
/// represented by this property bag.
|
|
///
|
|
/// The original \p lookupTerm is important in case the concrete type has
|
|
/// substitutions. For example, if \p lookupTerm is [P:A].[U:B], and this
|
|
/// property bag records that the suffix [U:B] has a superclass symbol
|
|
/// [superclass: Cache<τ_0_0> with <[U:C]>], then we actually need to
|
|
/// apply the substitution τ_0_0 := [P:A].[U:C] to the type 'Cache<τ_0_0>'.
|
|
///
|
|
/// Asserts if this property bag does not have a superclass bound.
|
|
Type PropertyBag::getSuperclassBound(
|
|
ArrayRef<GenericTypeParamType *> genericParams,
|
|
const MutableTerm &lookupTerm,
|
|
const PropertyMap &map) const {
|
|
MutableTerm prefix = getPrefixAfterStrippingKey(lookupTerm);
|
|
|
|
const auto &req = getSuperclassRequirement();
|
|
return map.getTypeFromSubstitutionSchema(req.SuperclassType->getConcreteType(),
|
|
req.SuperclassType->getSubstitutions(),
|
|
genericParams, prefix);
|
|
}
|
|
|
|
/// Get the concrete type of the term represented by this property bag.
|
|
///
|
|
/// The original \p lookupTerm is important in case the concrete type has
|
|
/// substitutions. For example, if \p lookupTerm is [P:A].[U:B], and this
|
|
/// property bag records that the suffix [U:B] has a concrete type symbol
|
|
/// [concrete: Array<τ_0_0> with <[U:C]>], then we actually need to
|
|
/// apply the substitution τ_0_0 := [P:A].[U:C] to the type 'Array<τ_0_0>'.
|
|
///
|
|
/// Asserts if this property bag is not concrete.
|
|
Type PropertyBag::getConcreteType(
|
|
ArrayRef<GenericTypeParamType *> genericParams,
|
|
const MutableTerm &lookupTerm,
|
|
const PropertyMap &map) const {
|
|
MutableTerm prefix = getPrefixAfterStrippingKey(lookupTerm);
|
|
return map.getTypeFromSubstitutionSchema(ConcreteType->getConcreteType(),
|
|
ConcreteType->getSubstitutions(),
|
|
genericParams, prefix);
|
|
}
|
|
|
|
void PropertyBag::copyPropertiesFrom(const PropertyBag *next,
|
|
RewriteContext &ctx) {
|
|
// If this is the property bag of T and 'next' is the
|
|
// property bag of V, then T := UV for some non-empty U.
|
|
int prefixLength = Key.size() - next->Key.size();
|
|
ASSERT(prefixLength > 0);
|
|
DEBUG_ASSERT(std::equal(Key.begin() + prefixLength, Key.end(),
|
|
next->Key.begin()));
|
|
|
|
// Conformances and the layout constraint, if any, can be copied over
|
|
// unmodified.
|
|
ConformsTo = next->ConformsTo;
|
|
ConformsToRules = next->ConformsToRules;
|
|
Layout = next->Layout;
|
|
LayoutRule = next->LayoutRule;
|
|
|
|
// If the property bag of V has superclass or concrete type
|
|
// substitutions {X1, ..., Xn}, then the property bag of
|
|
// T := UV should have substitutions {UX1, ..., UXn}.
|
|
MutableTerm prefix(Key.begin(), Key.begin() + prefixLength);
|
|
|
|
if (next->ConcreteType) {
|
|
ConcreteType = next->ConcreteType->prependPrefixToConcreteSubstitutions(
|
|
prefix, ctx);
|
|
ConcreteTypeRules = next->ConcreteTypeRules;
|
|
for (auto &pair : ConcreteTypeRules) {
|
|
pair.first = pair.first.prependPrefixToConcreteSubstitutions(
|
|
prefix, ctx);
|
|
}
|
|
}
|
|
|
|
// Copy over class hierarchy information.
|
|
SuperclassDecl = next->SuperclassDecl;
|
|
if (!next->Superclasses.empty()) {
|
|
Superclasses = next->Superclasses;
|
|
|
|
for (auto &req : Superclasses) {
|
|
req.second.SuperclassType =
|
|
req.second.SuperclassType->prependPrefixToConcreteSubstitutions(
|
|
prefix, ctx);
|
|
for (auto &pair : req.second.SuperclassRules) {
|
|
pair.first = pair.first.prependPrefixToConcreteSubstitutions(
|
|
prefix, ctx);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
Symbol PropertyBag::concretelySimplifySubstitution(const MutableTerm &mutTerm,
|
|
RewriteContext &ctx,
|
|
RewritePath *path) const {
|
|
ASSERT(!ConcreteTypeRules.empty());
|
|
auto &pair = ConcreteTypeRules.front();
|
|
|
|
// The property map entry might apply to a suffix of the substitution
|
|
// term, so prepend the appropriate prefix to its own substitutions.
|
|
auto prefix = getPrefixAfterStrippingKey(mutTerm);
|
|
auto concreteSymbol =
|
|
pair.first.prependPrefixToConcreteSubstitutions(
|
|
prefix, ctx);
|
|
|
|
// If U.V is the substitution term and V is the property map key,
|
|
// apply the rewrite step U.(V => V.[concrete: C]) followed by
|
|
// prepending the prefix U to each substitution in the concrete type
|
|
// symbol if |U| > 0.
|
|
if (path) {
|
|
path->add(RewriteStep::forRewriteRule(/*startOffset=*/prefix.size(),
|
|
/*endOffset=*/0,
|
|
/*ruleID=*/pair.second,
|
|
/*inverse=*/true));
|
|
|
|
if (!prefix.empty()) {
|
|
path->add(RewriteStep::forPrefixSubstitutions(/*length=*/prefix.size(),
|
|
/*endOffset=*/0,
|
|
/*inverse=*/false));
|
|
}
|
|
}
|
|
|
|
return concreteSymbol;
|
|
}
|
|
|
|
void PropertyBag::verify(const RewriteSystem &system) const {
|
|
if (!CONDITIONAL_ASSERT_enabled())
|
|
return;
|
|
|
|
ASSERT(ConformsTo.size() == ConformsToRules.size());
|
|
for (unsigned i : indices(ConformsTo)) {
|
|
auto symbol = system.getRule(ConformsToRules[i]).getLHS().back();
|
|
ASSERT(symbol.getKind() == Symbol::Kind::Protocol);
|
|
ASSERT(symbol.getProtocol() == ConformsTo[i]);
|
|
}
|
|
|
|
// FIXME: Add asserts requiring that the layout, superclass and
|
|
// concrete type symbols match, as above
|
|
ASSERT(!Layout.isNull() == LayoutRule.has_value());
|
|
ASSERT(ConcreteType.has_value() == !ConcreteTypeRules.empty());
|
|
|
|
ASSERT((SuperclassDecl == nullptr) == Superclasses.empty());
|
|
for (const auto &pair : Superclasses) {
|
|
const auto &req = pair.second;
|
|
ASSERT(req.SuperclassType.has_value());
|
|
ASSERT(!req.SuperclassRules.empty());
|
|
}
|
|
}
|
|
|
|
PropertyMap::~PropertyMap() {
|
|
Trie.updateHistograms(Context.PropertyTrieHistogram,
|
|
Context.PropertyTrieRootHistogram);
|
|
clear();
|
|
}
|
|
|
|
/// Look for a property bag corresponding to a suffix of the given range.
|
|
///
|
|
/// The symbol range must correspond to a term that has already been
|
|
/// simplified.
|
|
///
|
|
/// Returns nullptr if no information is known about this key.
|
|
PropertyBag *
|
|
PropertyMap::lookUpProperties(std::reverse_iterator<const Symbol *> begin,
|
|
std::reverse_iterator<const Symbol *> end) const {
|
|
if (auto result = Trie.find(begin, end))
|
|
return *result;
|
|
|
|
return nullptr;
|
|
}
|
|
|
|
/// Look for a property bag corresponding to a suffix of the given key.
|
|
///
|
|
/// The term must have already been simplified.
|
|
///
|
|
/// Returns nullptr if no information is known about this key.
|
|
PropertyBag *
|
|
PropertyMap::lookUpProperties(const MutableTerm &key) const {
|
|
return lookUpProperties(key.rbegin(), key.rend());
|
|
}
|
|
|
|
/// Look for a property bag corresponding to the given key, creating a new
|
|
/// property bag if necessary.
|
|
///
|
|
/// This must be called in monotonically non-decreasing key order.
|
|
PropertyBag *
|
|
PropertyMap::getOrCreateProperties(Term key) {
|
|
auto next = Trie.find(key.rbegin(), key.rend());
|
|
if (next && (*next)->getKey() == key)
|
|
return *next;
|
|
|
|
auto *props = new PropertyBag(key);
|
|
|
|
// Look for the longest suffix of the key that has a property bag,
|
|
// recording it as the next property bag if we find one.
|
|
//
|
|
// For example, if our rewrite system contains the following three rules:
|
|
//
|
|
// A.[P] => A
|
|
// B.A.[Q] => B.A
|
|
// C.A.[R] => C.A
|
|
//
|
|
// Then we have three property bags:
|
|
//
|
|
// A => { [P] }
|
|
// B.A => { [Q] }
|
|
// C.A => { [R] }
|
|
//
|
|
// The next property bag of both 'B.A' and 'C.A' is 'A'; conceptually,
|
|
// the set of properties satisfied by 'B.A' is a superset of the properties
|
|
// satisfied by 'A'; analogously for 'C.A'.
|
|
//
|
|
// Since 'A' has no proper suffix with additional properties, the next
|
|
// property bag of 'A' is nullptr.
|
|
if (next)
|
|
props->copyPropertiesFrom(*next, Context);
|
|
|
|
Entries.push_back(props);
|
|
auto oldProps = Trie.insert(key.rbegin(), key.rend(), props);
|
|
if (oldProps) {
|
|
ABORT([&](auto &out) {
|
|
out << "Duplicate property map entry for " << key << "\n";
|
|
out << "Old:\n";
|
|
(*oldProps)->dump(out);
|
|
out << "\n";
|
|
out << "New:\n";
|
|
props->dump(out);
|
|
});
|
|
}
|
|
|
|
return props;
|
|
}
|
|
|
|
void PropertyMap::clear() {
|
|
for (auto *props : Entries)
|
|
delete props;
|
|
|
|
Trie.clear();
|
|
Entries.clear();
|
|
}
|
|
|
|
/// Build the property map from all rules of the form T.[p] => T, where
|
|
/// [p] is a property symbol.
|
|
///
|
|
/// Also performs property unification, nested type concretization and
|
|
/// concrete simplification. These phases can add new rules; if new rules
|
|
/// were added, the caller must run another round of Knuth-Bendix
|
|
/// completion, and rebuild the property map again.
|
|
void PropertyMap::buildPropertyMap() {
|
|
if (System.getDebugOptions().contains(DebugFlags::PropertyMap)) {
|
|
llvm::dbgs() << "-------------------------\n";
|
|
llvm::dbgs() << "- Building property map -\n";
|
|
llvm::dbgs() << "-------------------------\n";
|
|
}
|
|
|
|
clear();
|
|
|
|
struct Property {
|
|
Term key;
|
|
Symbol symbol;
|
|
unsigned ruleID;
|
|
};
|
|
|
|
// PropertyMap::addRule() requires that shorter rules are added
|
|
// before longer rules, so that it can perform lookups on suffixes and call
|
|
// PropertyBag::copyPropertiesFrom(). However, we don't have to perform a
|
|
// full sort by term order here; a bucket sort by term length suffices.
|
|
SmallVector<std::vector<Property>, 4> properties;
|
|
|
|
for (const auto &rule : System.getRules()) {
|
|
if (rule.isLHSSimplified() ||
|
|
rule.isRHSSimplified())
|
|
continue;
|
|
|
|
// Identity conformances ([P].[P] => [P]) are permanent rules, but we
|
|
// keep them around to ensure that concrete conformance introduction
|
|
// works in the case where the protocol's Self type is itself subject
|
|
// to a superclass or concrete type requirement.
|
|
if (rule.isPermanent() && !rule.isIdentityConformanceRule())
|
|
continue;
|
|
|
|
// Collect all rules of the form T.[p] => T where T is canonical.
|
|
auto property = rule.isPropertyRule();
|
|
if (!property)
|
|
continue;
|
|
|
|
auto rhs = rule.getRHS();
|
|
unsigned length = rhs.size();
|
|
if (length >= properties.size())
|
|
properties.resize(length + 1);
|
|
|
|
unsigned ruleID = System.getRuleID(rule);
|
|
properties[length].push_back({rhs, *property, ruleID});
|
|
}
|
|
|
|
for (const auto &bucket : properties) {
|
|
for (auto property : bucket) {
|
|
addProperty(property.key, property.symbol,
|
|
property.ruleID);
|
|
}
|
|
}
|
|
|
|
// Now, check for conflicts between superclass and concrete type rules.
|
|
checkConcreteTypeRequirements();
|
|
|
|
// Now, we merge concrete type rules with conformance rules, by adding
|
|
// relations between associated type members of type parameters with
|
|
// the concrete type witnesses in the concrete type's conformance.
|
|
concretizeNestedTypesFromConcreteParents();
|
|
|
|
// Finally, a post-processing pass to reduce substitutions down to
|
|
// concrete types.
|
|
System.simplifyLeftHandSideSubstitutions(this);
|
|
|
|
// Check invariants of the constructed property map.
|
|
verify();
|
|
}
|
|
|
|
void PropertyMap::dump(llvm::raw_ostream &out) const {
|
|
out << "Property map: {\n";
|
|
for (const auto &props : Entries) {
|
|
out << " ";
|
|
props->dump(out);
|
|
out << "\n";
|
|
}
|
|
out << "}\n";
|
|
}
|
|
|
|
void PropertyMap::verify() const {
|
|
if (!CONDITIONAL_ASSERT_enabled())
|
|
return;
|
|
|
|
for (const auto &props : Entries)
|
|
props->verify(System);
|
|
}
|