// slang-check-inheritance.cpp
#include "slang-check-impl.h"
// This file implements the semantic checking logic
// related to computing linearized inheritance
// information for types and decalrations.
//#include "slang-lookup.h"
//#include "slang-syntax.h"
//#include "slang-ast-synthesis.h"
//#include <limits>
namespace Slang
{
InheritanceInfo SharedSemanticsContext::getInheritanceInfo(Type* type)
{
// We cache the computed inheritance information for types,
// and re-use that information whenever possible.
if(auto found = m_mapTypeToInheritanceInfo.tryGetValue(type))
return *found;
// Note: we install a null pointer into the dictionary to act
// as a sentinel during the processing of calculating the inheritnace
// info. If we encounter this sentinel value during the calcuation,
// it means that there was some kind of circular dependency in the
// inheritance graph, and we need to avoid crashing or going
// into an infinite loop in such cases.
//
m_mapTypeToInheritanceInfo[type] = InheritanceInfo();
auto info = _calcInheritanceInfo(type);
m_mapTypeToInheritanceInfo[type] = info;
getSession()->m_typeDictionarySize = Math::Max(
getSession()->m_typeDictionarySize, (int)m_mapTypeToInheritanceInfo.getCount());
return info;
}
InheritanceInfo SharedSemanticsContext::getInheritanceInfo(DeclRef<ExtensionDecl> const& extension)
{
// We bottleneck the calculation of inheritance information
// for type and `extension` `DeclRef`s through a single
// routine with an optional `Type` parameter.
//
return _getInheritanceInfo(extension, nullptr);
}
InheritanceInfo SharedSemanticsContext::_getInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* declRefType)
{
// Just as with `Type`s, we cache and re-use the inheritance
// information that has been computed for a `DeclRef` whenever
// possible.
if (auto found = m_mapDeclRefToInheritanceInfo.tryGetValue(declRef))
return *found;
// Note: we install a null pointer into the dictionary to act
// as a sentinel during the processing of calculating the inheritnace
// info. If we encounter this sentinel value during the calcuation,
// it means that there was some kind of circular dependency in the
// inheritance graph, and we need to avoid crashing or going
// into an infinite loop in such cases.
//
m_mapDeclRefToInheritanceInfo[declRef] = InheritanceInfo();
auto info = _calcInheritanceInfo(declRef, declRefType);
m_mapDeclRefToInheritanceInfo[declRef] = info;
return info;
}
InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* declRefType)
{
// This method is the main engine for computing linearized inheritance
// lists for types and `extension` declarations.
//
// The approach we use for linearization of an inheritance graph is based on
// what is the most broadly-accepted solution to the problem, presented in
// "A Monotonic Superclass Linearization for Dylan" by Barret et al.
// The algorithm recommended in that paper is also called the "C3 linearization
// algorithm." Many developers are most familiar with C3 linearization because
// it is used to compute the method resolution order (MRO) for a class in Python.
//
// The basic idea is that given a type declaration like:
//
// class A : B, C { ... }
//
// we can construct a linearization of the transitive bases of `A`
// by merging the linearizations for `B` and `C`. Any transitive
// base of `A` should appear in the linearization for `B` and/or `C`,
// so the main tasks are to remove duplicates (when a base type appears
// in both the linearization of `B` *and* `C`), and to ensure that
// the ordering is reasonable.
//
// What makes an ordering "reasonable" is a little subtle, especially
// in the context of Slang. In the original use case, the order of types
// in the linearization would determine which methods would override
// which other ones, so different orderings could have large semantic
// impact. Slang currently has less support for overriding, but is
// likely to add more over time.
//
// At the very least, we require that if `S <: T` for types `S` and `T`,
// then `S` should appear *before* `T` in the linearization. This, e.g.,
// guarantees that a concrete type that implements an `interface` will
// be listed before that interface and thus during lookup the members
// of the concrete type will be found before those of the `interface`.
//
// We will revisit the question of "reasonable" orderings later, as
// we get more into the core of the algorithm.
// Our linearization approach will construct a list of *facets* for
// the `declRef` in question, where each facet corresponds to a
// transitive base type, or an applicable `extension`.
//
FacetList::Builder allFacets;
// It is possible that `declRef` is itself a type declaration,
// in which case `declRefType` will be the coresponding type.
// However, if `declRef` is an `extension` declaration, we
// will extract the type that the extension applies to, so
// that we can have a consistent "self type" to represent
// the type that is at the root of the inheritance list.
//
Type* selfType = declRefType;
Facet::Kind selfFacetKind = Facet::Kind::Type;
auto astBuilder = _getASTBuilder();
auto& arena = astBuilder->getArena();
SemanticsVisitor visitor(this);
if (auto extensionDeclRef = declRef.as<ExtensionDecl>())
{
auto extendedType = getTargetType(astBuilder, extensionDeclRef);
selfType = extendedType;
selfFacetKind = Facet::Kind::Extension;
}
// Because we are dealing with entities that have declarations, the
// first item in our linearization will always be a facet for
// the declaration itself.
//
TypeEqualityWitness* selfIsSelf = selfType ? visitor.createTypeEqualityWitness(selfType) : nullptr;
Facet selfFacet = new(arena) Facet::Impl(
selfFacetKind,
Facet::Directness::Self,
declRef,
selfType,
selfIsSelf);
allFacets.add(selfFacet);
// After the self facet will come a list of facets formed
// by merging the facet lists of each of the direct/declared
// bases of the type/declaration in question.
//
// We will first traverse the structure of `declRef` to
// accumulate the list of bases, and then perform the merge
// when we are done.
//
DirectBaseList::Builder directBases;
FacetList::Builder directBaseFacets;
// We start with a simple operation to add an entry
// into the list of direct bases, for the case where
// we already have all of the relevant information
// about that base.
//
auto addDirectBaseFacet = [&](
Facet::Kind kind,
Type* baseType,
SubtypeWitness* selfIsBaseWitness,
DeclRef<Decl> const& baseDeclRef,
InheritanceInfo const& baseInheritanceInfo)
{
auto baseInfo = new(arena) DirectBaseInfo();
// The information we store for each direct
// base comprises two main things.
//
// First, we have a `Facet` that will represent
// the base in the linearized inheritance list
// we are building.
//
baseInfo->facetImpl = FacetImpl(
kind,
Facet::Directness::Direct,
baseDeclRef,
baseType,
selfIsBaseWitness);
Facet baseFacet(&baseInfo->facetImpl);
//
// Second, we have a list of the facets in the
// linearization of the base itself.
//
baseInfo->facets = baseInheritanceInfo.facets;
directBaseFacets.add(baseFacet);
directBases.add(baseInfo);
};
// In the case where we know that the base being added
// represents a direct base *type* (and not an `extension`)
// we can derive some of the information needed by
// `addDirectBaseFacet`.
//
auto addDirectBaseType = [&](
Type* baseType,
SubtypeWitness* selfIsBaseWitness)
{
// If we are representing inheritance from a type,
// then we should have a witness that the type
// in question (either the type being declared by
// `declRef`, or the type being *extended* by
// `declRef`) inherits from that base.
//
SLANG_ASSERT(selfIsBaseWitness);
auto baseInheritanceInfo = getInheritanceInfo(baseType);
DeclRef<Decl> baseDeclRef;
if (auto baseDeclRefType = as<DeclRefType>(baseType))
{
baseDeclRef = baseDeclRefType->getDeclRef();
}
addDirectBaseFacet(
Facet::Kind::Type,
baseType,
selfIsBaseWitness,
baseDeclRef,
baseInheritanceInfo);
};
// We now look at the structure of the declaration itself
// to help us enumerate the direct bases.
//
if (auto aggTypeDeclBaseRef = declRef.as<AggTypeDeclBase>())
{
// In the case where we have an aggregate type or `extension`
// declaration, we can use the explicit list of direct bases.
//
for (auto typeConstraintDeclRef : getMembersOfType<TypeConstraintDecl>(_getASTBuilder(), aggTypeDeclBaseRef))
{
visitor.ensureDecl(typeConstraintDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl);
// Note: In certain cases something takes the *syntactic* form of an inheritance
// clause, but it is not actually something that should be treated as implying
// a subtype relationship. For example, an `enum` declaration can use what looks
// like an inheritance clause to indicate its underlying "tag type."
//
// We skip such pseudo-inheritance relationships for the purposes of determining
// the linearized list of bases.
//
if (typeConstraintDeclRef.getDecl()->hasModifier<IgnoreForLookupModifier>())
continue;
// The base type and subtype witness can easily be determined
// using the `InheritanceDecl`.
//
auto baseType = getSup(astBuilder, typeConstraintDeclRef);
auto satisfyingWitness = astBuilder->getDeclaredSubtypeWitness(
selfType,
baseType,
typeConstraintDeclRef);
addDirectBaseType(baseType, satisfyingWitness);
}
}
else if (auto genericTypeParamDeclRef = declRef.as<GenericTypeParamDecl>())
{
// The constraints placed on a generic type parameter are siblings of that
// parameter in its parent `GenericDecl`, so we need to enumerate all of
// the constraints of the parent declaration to find those that constrain
// this parameter.
//
// TODO(tfoley): We might consider adding a cached representation of the
// constraint information that is keyed on a per-parameter basis. Such a
// representation would need to take into account canonicalization of
// constraints.
auto genericDeclRef = genericTypeParamDeclRef.getParent().as<GenericDecl>();
SLANG_ASSERT(genericDeclRef);
ensureDecl(&visitor, genericDeclRef.getDecl(), DeclCheckState::CanSpecializeGeneric);
for (auto constraintDeclRef : getMembersOfType<GenericTypeConstraintDecl>(astBuilder, genericDeclRef))
{
auto subType = getSub(astBuilder, constraintDeclRef);
auto superType = getSup(astBuilder, constraintDeclRef);
// We only consider constraints where the type represented
// by `genericTypeParamDeclRef` is the subtype, since those
// constraints are the ones that give us information about
// the declared supertypes.
//
// TODO: consider whether other kinds of constraints could
// also apply here.
//
auto subDeclRefType = as<DeclRefType>(subType);
if (!subDeclRefType)
continue;
if (subDeclRefType->getDeclRef() != genericTypeParamDeclRef)
continue;
// Because the constraint is a declared inheritance relationship,
// adding the base to our list of direct bases is as straightforward
// as in all the preceding cases.
//
auto satisfyingWitness = _getASTBuilder()->getDeclaredSubtypeWitness(
selfType,
superType,
constraintDeclRef);
addDirectBaseType(superType, satisfyingWitness);
}
}
// At this point we have enumerated all of the bases that can be
// gleaned by looking at the `declRef` itself. The next step is
// to consider any `extension` declarations that might apply to
// a type being delared.
//
// In our current system, only nominal types (those with `Decl`s)
// can be extended, so we begin by checking if the `selfType`
// is a nominal/`DeclRef` type.
//
// Note: this step will *not* apply when `declRef` is an `extension`
// declaration, since it directly checks for an `AggTypeDecl`
// instead of an `AggTypeDeclBase`.
//
// Similarly, we do *not* add the type being extended to the list
// of bases for an `extension`.
//
// These choices are important to avoid circular dependencies, where
// the linearization of an `extension` would end up depending on its
// own linearization (either directly or through a dependency on
// the linearization of the type being extended).
//
// Instead, the linearization we create here for an `extension` will
// *only* contain facets for the members introduced by the `extension`
// itself, as well as any transitive bases declared on that `extension`.
//
if (auto directAggTypeDeclRef = declRef.as<AggTypeDecl>())
{
for (auto extDecl : getCandidateExtensions(directAggTypeDeclRef, &visitor))
{
// The list of *candidate* extensions is computed and
// cached based on the identity of the declaration alone,
// and does not take into account any generic arguments
// of either the type or the `extension`.
//
// For example, we might have an `extension` that applies
// to `vector<float,N>` for any `N`, but the `selfType`
// that we are working with could be `<vector<int,2>` so
// that the extension doesn't match.
//
// In order to make sure that we don't enumerate members
// that don't make sense in context, we must apply
// the extension to the type and see if we succeed in
// making a match.
//
auto extDeclRef = applyExtensionToType(&visitor, extDecl, selfType);
if (!extDeclRef)
continue;
// In the case where we *do* find an extension that
// applies to the type, we add a declared base to
// represent the `extension`, knowing that its
// own linearized inheritance list will include
// any transitive based declared on the `extension`.
//
auto extInheritanceInfo = getInheritanceInfo(extDeclRef);
addDirectBaseFacet(
Facet::Kind::Extension,
selfType,
selfIsSelf,
extDeclRef,
extInheritanceInfo);
}
}
// At this point, the list of direct bases (each with its own linearization)
// is complete.
//
// At this point we could scan through the list of bases and perform
// consistency checks on it. For example, when two types in the list of direct
// bases have a subtype relationship between them, it is possible that the
// programmer made some kind of mistake, and we could emit a diagnostic
// about it.
//
// The published C3 algorithm actually considers the declared list of bases
// as one of the inputs to its merge, and is very strict about ordering.
// As such, it would be an error for strict C3 if direct bases were declared
// in an order that is inconsitent with the partial order determined by
// the subtype relationship. Our implementation of linearization is relaxed
// compared to C3 so that it is robust to such ordering issues.
//
// Note: This step takes quadratic time in the number of direct bases, but
// there's really no other way to easily detect these issues.
//
for(auto leftBase = directBaseFacets.getHead(); leftBase.getImpl(); leftBase = leftBase->next)
{
// Note: all of the direct base facets with a `Type` kind will
// precede all of those with `Extension` kind, so we can bail
// out of the outer loop as soon as we find a non-`Type`
// facet.
//
if(leftBase->kind != Facet::Kind::Type)
break;
auto leftBaseType = leftBase->origin.type;
// For the inner loop we scan only the facets that appear *after*
// the `leftBase` in the list of direct bases.
//
for(auto rightBase = leftBase->next; rightBase.getImpl(); rightBase = rightBase->next)
{
if (rightBase->kind != Facet::Kind::Type)
break;
auto rightBaseType = rightBase->origin.type;
if (visitor.isSubtype(leftBaseType, rightBaseType))
{
// If a type earlier in the list of bases is a subtype of
// one later in the list, then the ordering is consistent
// with the linearization that will be produced, but it
// might represent a mistake on the programmer's part,
// since they listed a base type that is redundant.
//
// TODO: decide whether to diagnose this case.
}
else if (visitor.isSubtype(rightBaseType, leftBaseType))
{
// If a type later in the list is a subtype of a type earlier
// in the list, then the declared list of bases is inconsistent
// with the ordering that will (indeed *must*) appear in the
// linearization we generate.
//
// If we end up implementing a strict version of the C3 algorithm,
// we would need to treat such situations as an error, or at least
// emit a warning and then remove the subtype from the list of
// bases.
//
// TODO: decide whether to diagnose this case.
}
}
}
// Now that we've built up the list of direct bases and their
// respective linearizations, we can apply the core merge algorithm
// to those lists to produce the rest of the linearization for
// the declaration in question.
//
_mergeFacetLists(directBases, directBaseFacets, allFacets);
InheritanceInfo info;
info.facets = allFacets;
return info;
}
void SharedSemanticsContext::_mergeFacetLists(DirectBaseList bases, FacetList baseFacets, FacetList::Builder& ioMergedFacets)
{
// Our task here is to take the list of direct/declared `bases`,
// each of which holds a linearized list of `Facet`s, and produce
// a single linearized list of facets in `ioMergedFacets`.
//
// The `Facet`s in the lists referenced by `bases` are always
// relative to the base type/extension itself, and not to
// the type or declaration for which we are computing
// a linearization.
//
// The `baseFacets` list provides one `Facet` for each direct
// base that are relative to the type/declaration we are
// computing a linearization for. These facets will be used
// directly, instead of those from `bases`, where possible.
//
auto astBuilder = _getASTBuilder();
auto& arena = astBuilder->getArena();
for(;;)
{
// The basic logic here is that on each iteration we
// will look at the first item on each list in `bases`
// and pick one that we will append to the merged output
// (after removing it from the relevant input(s)).
// If we have run out of lists that need merging, then we are done.
//
if (bases.isEmpty())
break;
// Otherwise, we will look at the remaining non-empty lists,
// and see if one of them starts with an facet that can
// be appended to our merged output.
//
// If multiple such facets are viable, we will always take
// the one from the earliest list in `bases`. Doing so favors
// the types that appear earlier in a list of bases.
//
Facet foundFacet;
DirectBaseInfo* foundBase = nullptr;
for (auto base : bases)
{
Facet headFacet = base->facets.getHead();
// If the head facet of the `base` list appears at a non-head
// position in any of the other lists, we cannot append this
// element without risking inverting the order of some facets
// relative to those other lists.
//
if (bases.doesAnyTailContainMatchFor(headFacet))
continue;
// Otherwise, we are safe to add the `headFacet` to our
// merged list, because it only ever appears as the head
// of one or more of the lists in `bases`.
//
foundFacet = headFacet;
foundBase = base;
break;
}
if(!foundFacet)
{
// If we could not identify a facet that could be safely
// removed from any of the base lists, then it means that
// we must have a cycle in the ordering constraints implied
// by the `bases` lists.
//
// The simplest example of such a cycle would be if we
// had two lists, `A` and `B`, such that:
//
// A = { X, Y }
// B = { Y, X }
//
// In this case, producing output in the order `X, Y` *or*
// `Y, X` will always invalidate the ordering constraints
// implied by either `A` or `B`.
//
// In the C3 algorithm as published, such a situation is an
// error, and the algorithm fails to produce a linearization.
// The reason for this decision is that allowing this case
// means that a base type and a derived type could disagree
// on the relative priority of method overrides, and thus
// a subclass could possible break semantic assumptions of
// a superclass.
//
// In a more static language like Slang, it seems better to
// allow more flexible inheritance, *especially* when dealing
// with things like `interface`s and `extension`s, where the
// relative ordering of things will often be immaterial.
//
// In a case like this, we would like to arbitrarily pick
// one or the other of `X` and `Y`, and given our default
// policy to favor the earlier list in `bases` where possible,
// we would select `X` from `A`.
//
// One thing worth noting is that when a case like the above
// arises, it is not possible that `X <: Y` or `Y <: X`.
// If a subtype relationship existed between the two, then
// they would be consistently ordered in *both* lists.
// We thus do not have to worry about violating the most
// important requirement for a "reasonable" linearization.
//
foundBase = *bases.begin();
foundFacet = foundBase->facets.getHead();
// Note: because we are grabbing a facet that might appear
// in a non-head position in one or more of our lists,
// we need to have a plan for what to do when we see
// that same facet come to the front of one of our lists
// later.
}
// At this point we definitely have a facet we'd like to
// add to the output, whether it was found via the true
// C3 approach, or our relaxed rule above.
//
SLANG_ASSERT(foundFacet.getImpl());
// If the facet we want to append to the output is the same as the front-most
// facet on the list of bases, then we want to use that facet as-is (since we
// have already allocated storage for it).
//
// TODO: in cases where the strict C3 algorithm would fail, and we choose a
// `foundFacet` that is at a non-head position in at least some lists, it
// might be possible that we have a facet that matches ones of the `baseFacets`,
// but not the head one. We should confirm what happens in that case.
//
if(originsMatch(foundFacet, baseFacets.getHead()))
{
auto directBaseFacet = baseFacets.popHead();
ioMergedFacets.add(directBaseFacet);
}
else
{
// This facet is seemingly *not* a facet that represents one of the direct
// bases for the type/declaration being processed.
//
// As such, we need to allocate a fresh facet to represent it in the
// linearization we are creating, since the `foundFacet` already belongs
// to the linearization of one of the bases, and shouldn't be repurposed.
//
auto indirectFacet = new(arena) Facet::Impl();
// We will initialize the fresh facet to a copy of the state of the
// `foundFacet`, albeit with a higher level of indirection.
//
// TODO: In principle we could search through all of the lists to
// find the one with a facet matching `foundFacet` with minimum
// indirection, so that our measure of indirection is always
// as small as possible for any given facet.
//
*indirectFacet = *(foundFacet.getImpl());
indirectFacet->next = nullptr;
indirectFacet->directness =
Facet::Directness(Facet::DirectnessVal(indirectFacet->directness) + 1);
// When using this facet for subtype tests, or when looking
// up member through this facet, we will need a witness
// to show that the self type of the declaration being
// linearized (the type being declared or extended) is a
// subtype of the type for this facet.
//
// We can construct the appropriate witness transitively,
// by noting that:
//
// * The self type is known to be a subtype of the direct
// base represented by `foundBase`, and the facet for
// that base stores a witness to that fact.
//
SubtypeWitness* selfIsSubtypeOfBase = foundBase->facetImpl.subtypeWitness;
//
// * The direct base type must be a subtype of the type
// for any facet found in its own linearization, and
// the `foundFacet` that came from the relevant base
// stores a witness to that fact.
//
SubtypeWitness* baseIsSubtypeOfFacet = foundFacet->subtypeWitness;
auto selfIsSubtypeOfFacet = _getASTBuilder()->getTransitiveSubtypeWitness(
selfIsSubtypeOfBase,
baseIsSubtypeOfFacet);
indirectFacet->subtypeWitness = selfIsSubtypeOfFacet;
ioMergedFacets.add(indirectFacet);
}
// We picked one `foundFacet` above to be added to the merged
// output list, and we now need to ensure that we won't ever
// emit a matching facet again.
//
// In the case of the strict/standard C3 algorithm, any facets
// matching `foundFacet` would need to appear at a head position
// in one of the base lists. As such, it is sufficient to run
// through the base lists, check for a match at the head of each,
// and remove any matching facets we find.
//
for (auto base : bases)
{
if (originsMatch(foundFacet, base->facets.getHead()))
{
base->facets.advanceHead();
continue;
}
}
//
// Because we are not implementing the C3 algorithm strictly,
// we need a solution for the case where `foundFacet` is
// in a non-head position in one or more of the base lists.
//
// Proactively filtering `foundFacet` out of all of the lists
// is possible, but given that these are singly-linked lists
// we cannot easily filter them without either allocation
// or mutation.
//
// Instead, we will filter out facets that have already been
// added to the merged list as needed, when such facets come
// to the front of the relevant list.
//
for (auto base : bases)
{
for(;;)
{
// For each base list, we will check if its
// head facet is one that has already been
// emitted to the output.
//
// If the head facet has not been emitted
// already, we don't need to perform any
// filtering on the base list at this time.
//
auto head = base->facets.getHead();
if (!ioMergedFacets.containsMatchFor(head))
break;
// Otherwise, we remove the head facet from
// the given base list and test again, unless
// the list is now empty.
//
base->facets.advanceHead();
if (base->facets.isEmpty())
break;
}
}
// The filtering step might have led to one or more
// of the `bases` lists becomming empty. Our merge
// algorithm really only wants to consider non-empty
// lists, so we go ahead and remove the empty lists
// here.
//
bases.removeEmptyLists();
// At this point all of the lists have been appropriately filtered,
// and we are ready to circle back around again to the step
// where select a facet to add to the merged list.
}
// At this point, all of the input lists in `bases` should be empty,
// and all of the facets in those lists should have found their way
// over to `ioMergedFacets`.
}
// The mering algorithm needs to be able to test if two potentially-distinct
// `Facet`s represent the same underlying type or declaration.
//
bool originsMatch(Facet left, Facet right)
{
if (left.getImpl() == right.getImpl())
return true;
if (!left.getImpl() || !right.getImpl())
return false;
// If both of the facets are non-null, and not
// identical, we check if their origins match,
// meaning that they represent the same type
// or declaration.
//
return left->origin == right->origin;
}
bool operator==(Facet::Origin left, Facet::Origin right)
{
// If either facet represents a declaration, then
// the origins only match if they both represent
// the *same* declaration.
//
if (left.declRef.getDecl() || right.declRef.getDecl())
{
return left.declRef.getDecl()
&& right.declRef.getDecl()
&& left.declRef.equals(right.declRef);
}
// Otherwise, if they both represent types, then the
// origins match if they are the same type.
//
// Note: an `extension` facet will always have a non-null
// `declRef`, so there is no risk here of an `extension`
// and a type facet being matched by this step; they
// would always land in the case above.
//
if (left.type || right.type)
{
return left.type
&& right.type
&& left.type->equals(right.type);
}
// TODO: The rules we are using for matching here
// would need to be revisited and overhauled significantly
// if we start supporting generic type declarations
// with covariant/contravariant type parameters.
//
// In such cases we would need to treat two facets as
// matching if their declarations or types are an exact
// matching modulo type arguments, and the relationship
// between pairwise type arguments is consistent with
// the variance of the corresponding parameter.
//
// E.g., we would need to treat facets for `IEnumerable<Derived>`
// and `IEnumerable<Base>` as matching, and ensure that a
// merged output list for a type/declaration could only
// include the more specific of the two (`IEnumerable<Derived>`).
return false;
}
// The remaining list-related operations that relate to the merging
// process are relatively simple to follow once the definition of
// matching is clear.
bool SharedSemanticsContext::DirectBaseList::doesAnyTailContainMatchFor(Facet facet) const
{
for (auto base : *this)
{
if (base->facets.getTail().containsMatchFor(facet))
return true;
}
return false;
}
void SharedSemanticsContext::DirectBaseList::removeEmptyLists()
{
DirectBaseInfo** link = &_head;
while (auto base = *link)
{
if (base->facets.isEmpty())
{
*link = base->next;
}
else
{
link = &base->next;
}
}
}
bool FacetList::containsMatchFor(Facet facet) const
{
for (auto f : *this)
{
if (originsMatch(f, facet))
return true;
}
return false;
}
InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(Type* type)
{
// The majority of the interesting for for computing linearized
// inheritance information arises for `DeclRef`s, but we still
// need a way to compute the relevant information for types
// that might or might not be defined using `Decl`s.
auto astBuilder = _getASTBuilder();
auto& arena = astBuilder->getArena();
if (auto declRefType = as<DeclRefType>(type))
{
// The `DeclRef` case is the easy one, since we can
// bottleneck through the logic that gets shared between
// type and `extension` declarations.
//
return _getInheritanceInfo(declRefType->getDeclRef(), declRefType);
}
else if (auto conjunctionType = as<AndType>(type))
{
// In this case, we have a type of the form `L & R`,
// such that it is a subtype of both `L` and `R`.
//
auto leftType = conjunctionType->getLeft();
auto rightType = conjunctionType->getRight();
// The linearized inheritance list for the conjunction
// must include all the facets from the lists for `L`
// and `R`, respectively.
//
auto leftInfo = getInheritanceInfo(leftType);
auto rightInfo = getInheritanceInfo(rightType);
// We have a case of subtype witness that can show that
// `T : L` or `T : R` based on `T : L&R`. In this case,
// though, the type `T` is actually `L&R` itself, so
// we need to construct an identity witness for `L&R : L&R`
// to give it something to start from.
//
auto selfIsSelf = astBuilder->getTypeEqualityWitness(conjunctionType);
auto selfIsSubtypeOfLeft = _getASTBuilder()->getExtractFromConjunctionSubtypeWitness(type, leftType, selfIsSelf, 0);
auto selfIsSubtypeOfRight = _getASTBuilder()->getExtractFromConjunctionSubtypeWitness(type, rightType, selfIsSelf, 1);
// We will set up to perform a merge between the facet
// lists for the two "bases" `L` and `R`. Note that the
// information we write into the `facetImpl` in each case
// is largely just for completeness and debugging, since
// we are *not* going to add those facets into a list
// of direct base facets to be merged.
//
DirectBaseInfo leftBaseInfo;
leftBaseInfo.facetImpl = FacetImpl(
Facet::Kind::Type,
Facet::Directness::Direct,
DeclRef<Decl>(),
leftType,
selfIsSubtypeOfLeft);
leftBaseInfo.facets = leftInfo.facets;
DirectBaseInfo rightBaseInfo;
rightBaseInfo.facetImpl = FacetImpl(
Facet::Kind::Type,
Facet::Directness::Direct,
DeclRef<Decl>(),
rightType,
selfIsSubtypeOfRight);
rightBaseInfo.facets = rightInfo.facets;
DirectBaseList::Builder directBases;
directBases.add(&leftBaseInfo);
directBases.add(&rightBaseInfo);
// The merging step is then the same as for the more "standard" case,
// with the only detail that we are not passing in a list of facets
// to represent the directly-declared bases (since there are none;
// this is a structural rather than nominal type).
//
FacetList::Builder mergedFacets;
_mergeFacetLists(directBases, FacetList(), mergedFacets);
InheritanceInfo info;
info.facets = mergedFacets;
return info;
}
else
{
// As a fallback, any type not covered by the above cases will
// get a trivial linearization that consists of a single facet
// corresponding to that type itself.
//
SemanticsVisitor visitor(this);
auto directFacet = new(arena) Facet::Impl(
Facet::Kind::Type,
Facet::Directness::Self,
DeclRef<Decl>(),
type,
visitor.createTypeEqualityWitness(type));
InheritanceInfo info;
info.facets = FacetList(directFacet);
return info;
}
}
}