summaryrefslogtreecommitdiff
path: root/source/slang/slang-check-inheritance.cpp
diff options
context:
space:
mode:
authorEllie Hermaszewska <ellieh@nvidia.com>2024-10-29 14:49:26 +0800
committerGitHub <noreply@github.com>2024-10-29 14:49:26 +0800
commitf65d756bff8d4c5cbc15bd0322a2ae8e6b896a21 (patch)
treeea1d61342cd29368e19135000ec2948813096205 /source/slang/slang-check-inheritance.cpp
parenta729c15e9dce9f5116a38afc66329ab2ca4cea54 (diff)
format
* format * Minor test fixes * enable checking cpp format in ci
Diffstat (limited to 'source/slang/slang-check-inheritance.cpp')
-rw-r--r--source/slang/slang-check-inheritance.cpp1961
1 files changed, 996 insertions, 965 deletions
diff --git a/source/slang/slang-check-inheritance.cpp b/source/slang/slang-check-inheritance.cpp
index 360fc0d14..4b0ec0f55 100644
--- a/source/slang/slang-check-inheritance.cpp
+++ b/source/slang/slang-check-inheritance.cpp
@@ -7,1135 +7,1166 @@
namespace Slang
{
- InheritanceInfo SharedSemanticsContext::getInheritanceInfo(Type* type, InheritanceCircularityInfo* circularityInfo)
- {
- // We cache the computed inheritance information for types,
- // and re-use that information whenever possible.
-
- // DeclRefTypes will have their inheritance info cached in m_mapDeclRefToInheritanceInfo.
- if (auto declRefType = as<DeclRefType>(type))
- return _getInheritanceInfo(declRefType->getDeclRef(), declRefType, circularityInfo);
-
- // Non ordinary types are cached on m_mapTypeToInheritanceInfo.
- 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();
+InheritanceInfo SharedSemanticsContext::getInheritanceInfo(
+ Type* type,
+ InheritanceCircularityInfo* circularityInfo)
+{
+ // We cache the computed inheritance information for types,
+ // and re-use that information whenever possible.
+
+ // DeclRefTypes will have their inheritance info cached in m_mapDeclRefToInheritanceInfo.
+ if (auto declRefType = as<DeclRefType>(type))
+ return _getInheritanceInfo(declRefType->getDeclRef(), declRefType, circularityInfo);
+
+ // Non ordinary types are cached on m_mapTypeToInheritanceInfo.
+ 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, circularityInfo);
- m_mapTypeToInheritanceInfo[type] = info;
+ auto info = _calcInheritanceInfo(type, circularityInfo);
+ m_mapTypeToInheritanceInfo[type] = info;
- return info;
- }
+ return info;
+}
- InheritanceInfo SharedSemanticsContext::getInheritanceInfo(DeclRef<ExtensionDecl> const& extension, InheritanceCircularityInfo* circularityInfo)
+InheritanceInfo SharedSemanticsContext::getInheritanceInfo(
+ DeclRef<ExtensionDecl> const& extension,
+ InheritanceCircularityInfo* circularityInfo)
+{
+ if (_checkForCircularityInExtensionTargetType(extension.getDecl(), circularityInfo))
{
- if (_checkForCircularityInExtensionTargetType(extension.getDecl(), circularityInfo))
- {
- // If we detect a circularity in the inheritance graph,
- // we will return an empty `InheritanceInfo` to avoid
- // infinite recursion.
- //
- return InheritanceInfo();
- }
-
- // We bottleneck the calculation of inheritance information
- // for type and `extension` `DeclRef`s through a single
- // routine with an optional `Type` parameter.
+ // If we detect a circularity in the inheritance graph,
+ // we will return an empty `InheritanceInfo` to avoid
+ // infinite recursion.
//
- InheritanceCircularityInfo newCircularityInfo(extension.getDecl(), circularityInfo);
- return _getInheritanceInfo(extension, nullptr, &newCircularityInfo);
+ return InheritanceInfo();
}
- bool SharedSemanticsContext::_checkForCircularityInExtensionTargetType(
- Decl* decl,
- InheritanceCircularityInfo* circularityInfo)
+ // We bottleneck the calculation of inheritance information
+ // for type and `extension` `DeclRef`s through a single
+ // routine with an optional `Type` parameter.
+ //
+ InheritanceCircularityInfo newCircularityInfo(extension.getDecl(), circularityInfo);
+ return _getInheritanceInfo(extension, nullptr, &newCircularityInfo);
+}
+
+bool SharedSemanticsContext::_checkForCircularityInExtensionTargetType(
+ Decl* decl,
+ InheritanceCircularityInfo* circularityInfo)
+{
+ for (auto info = circularityInfo; info; info = info->next)
{
- for (auto info = circularityInfo; info; info = info->next)
+ if (decl == info->decl)
{
- if (decl == info->decl)
- {
- getSink()->diagnose(decl, Diagnostics::circularityInExtension, decl);
- return true;
- }
+ getSink()->diagnose(decl, Diagnostics::circularityInExtension, decl);
+ return true;
}
-
- return false;
}
- InheritanceInfo SharedSemanticsContext::_getInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* declRefType, InheritanceCircularityInfo* circularityInfo)
- {
- // 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();
+ return false;
+}
- auto info = _calcInheritanceInfo(declRef, declRefType, circularityInfo);
- m_mapDeclRefToInheritanceInfo[declRef] = info;
+InheritanceInfo SharedSemanticsContext::_getInheritanceInfo(
+ DeclRef<Decl> declRef,
+ DeclRefType* declRefType,
+ InheritanceCircularityInfo* circularityInfo)
+{
+ // 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();
- getSession()->m_typeDictionarySize = Math::Max(
- getSession()->m_typeDictionarySize, (int)m_mapDeclRefToInheritanceInfo.getCount());
+ auto info = _calcInheritanceInfo(declRef, declRefType, circularityInfo);
+ m_mapDeclRefToInheritanceInfo[declRef] = info;
- return info;
- }
+ getSession()->m_typeDictionarySize = Math::Max(
+ getSession()->m_typeDictionarySize,
+ (int)m_mapDeclRefToInheritanceInfo.getCount());
- void SharedSemanticsContext::getDependentGenericParentImpl(DeclRef<GenericDecl>& genericParent, DeclRef<Decl> declRef)
- {
- auto mergeParent = [](DeclRef<GenericDecl>& currentParent, DeclRef<GenericDecl> newParent)
- {
- if (!currentParent)
- {
- currentParent = newParent;
- return;
- }
- if (currentParent == newParent)
- return;
- if (newParent.getDecl()->isChildOf(currentParent.getDecl()))
- currentParent = newParent;
- };
+ return info;
+}
- if (declRef.as<GenericTypeParamDeclBase>())
+void SharedSemanticsContext::getDependentGenericParentImpl(
+ DeclRef<GenericDecl>& genericParent,
+ DeclRef<Decl> declRef)
+{
+ auto mergeParent = [](DeclRef<GenericDecl>& currentParent, DeclRef<GenericDecl> newParent)
+ {
+ if (!currentParent)
{
- if (!genericParent)
- mergeParent(genericParent, declRef.getParent().as<GenericDecl>());
+ currentParent = newParent;
return;
}
- else if (auto lookupDeclRef = as<LookupDeclRef>(declRef.declRefBase))
- {
- if (auto lookupSourceDeclRef = isDeclRefTypeOf<Decl>(lookupDeclRef->getLookupSource()))
- getDependentGenericParentImpl(genericParent, lookupSourceDeclRef);
- }
- else if (auto genericAppDeclRef = as<GenericAppDeclRef>(declRef.declRefBase))
+ if (currentParent == newParent)
+ return;
+ if (newParent.getDecl()->isChildOf(currentParent.getDecl()))
+ currentParent = newParent;
+ };
+
+ if (declRef.as<GenericTypeParamDeclBase>())
+ {
+ if (!genericParent)
+ mergeParent(genericParent, declRef.getParent().as<GenericDecl>());
+ return;
+ }
+ else if (auto lookupDeclRef = as<LookupDeclRef>(declRef.declRefBase))
+ {
+ if (auto lookupSourceDeclRef = isDeclRefTypeOf<Decl>(lookupDeclRef->getLookupSource()))
+ getDependentGenericParentImpl(genericParent, lookupSourceDeclRef);
+ }
+ else if (auto genericAppDeclRef = as<GenericAppDeclRef>(declRef.declRefBase))
+ {
+ for (Index i = 0; i < genericAppDeclRef->getArgCount(); i++)
{
- for (Index i = 0; i < genericAppDeclRef->getArgCount(); i++)
+ if (auto argDeclRef = isDeclRefTypeOf<Decl>(genericAppDeclRef->getArg(i)))
{
- if (auto argDeclRef = isDeclRefTypeOf<Decl>(genericAppDeclRef->getArg(i)))
- {
- getDependentGenericParentImpl(genericParent, argDeclRef);
- }
+ getDependentGenericParentImpl(genericParent, argDeclRef);
}
}
}
+}
+
+DeclRef<GenericDecl> SharedSemanticsContext::getDependentGenericParent(DeclRef<Decl> declRef)
+{
+ DeclRef<GenericDecl> genericParent;
+ getDependentGenericParentImpl(genericParent, declRef);
+ return genericParent;
+}
- DeclRef<GenericDecl> SharedSemanticsContext::getDependentGenericParent(DeclRef<Decl> declRef)
+InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(
+ DeclRef<Decl> declRef,
+ DeclRefType* declRefType,
+ InheritanceCircularityInfo* circularityInfo)
+{
+ // 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>())
{
- DeclRef<GenericDecl> genericParent;
- getDependentGenericParentImpl(genericParent, declRef);
- return genericParent;
+ auto extendedType = getTargetType(astBuilder, extensionDeclRef);
+ selfType = extendedType;
+ selfFacetKind = Facet::Kind::Extension;
}
- InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* declRefType, InheritanceCircularityInfo* circularityInfo)
+ // 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)
{
- // 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 { ... }
+ auto baseInfo = new (arena) DirectBaseInfo();
+
+ // The information we store for each direct
+ // base comprises two main things.
//
- // 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.
+ // First, we have a `Facet` that will represent
+ // the base in the linearized inheritance list
+ // we are building.
//
- // 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.
+ baseInfo->facetImpl =
+ FacetImpl(kind, Facet::Directness::Direct, baseDeclRef, baseType, selfIsBaseWitness);
+ Facet baseFacet(&baseInfo->facetImpl);
//
- // 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`.
+ // Second, we have a list of the facets in the
+ // linearization of the base itself.
//
- // We will revisit the question of "reasonable" orderings later, as
- // we get more into the core of the algorithm.
+ baseInfo->facets = baseInheritanceInfo.facets;
- // 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.
+ 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.
//
- Type* selfType = declRefType;
- Facet::Kind selfFacetKind = Facet::Kind::Type;
+ SLANG_ASSERT(selfIsBaseWitness);
- auto astBuilder = _getASTBuilder();
- auto& arena = astBuilder->getArena();
- SemanticsVisitor visitor(this);
- if (auto extensionDeclRef = declRef.as<ExtensionDecl>())
+ auto baseInheritanceInfo = getInheritanceInfo(baseType, circularityInfo);
+
+ DeclRef<Decl> baseDeclRef;
+ if (auto baseDeclRefType = as<DeclRefType>(baseType))
{
- auto extendedType = getTargetType(astBuilder, extensionDeclRef);
- selfType = extendedType;
- selfFacetKind = Facet::Kind::Extension;
+ baseDeclRef = baseDeclRefType->getDeclRef();
}
- // 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;
+ addDirectBaseFacet(
+ Facet::Kind::Type,
+ baseType,
+ selfIsBaseWitness,
+ baseDeclRef,
+ baseInheritanceInfo);
+ };
- // 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)
+ // If we know the type has a facet represented by `extensionTargetDeclRef`, we can consider
+ // all extensions on this decl to see if they apply to the type.
+ //
+ auto considerExtension = [&](DeclRef<AggTypeDecl> extensionTargetDeclRef,
+ Dictionary<Type*, SubtypeWitness*>* additionalSubtypeWitness)
+ {
+ bool result = false;
+ for (auto extDecl : getCandidateExtensions(extensionTargetDeclRef, &visitor))
{
- auto baseInfo = new(arena) DirectBaseInfo();
-
- // The information we store for each direct
- // base comprises two main things.
+ // 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`.
//
- // First, we have a `Facet` that will represent
- // the base in the linearized inheritance list
- // we are building.
+ // 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.
//
- baseInfo->facetImpl = FacetImpl(
- kind,
- Facet::Directness::Direct,
- baseDeclRef,
- baseType,
- selfIsBaseWitness);
- Facet baseFacet(&baseInfo->facetImpl);
+ // 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.
//
- // 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);
- };
+ auto extDeclRef =
+ applyExtensionToType(&visitor, extDecl, selfType, additionalSubtypeWitness);
+ if (!extDeclRef)
+ continue;
- // 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.
+ // 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`.
//
- SLANG_ASSERT(selfIsBaseWitness);
-
- auto baseInheritanceInfo = getInheritanceInfo(baseType, circularityInfo);
-
- DeclRef<Decl> baseDeclRef;
- if (auto baseDeclRefType = as<DeclRefType>(baseType))
- {
- baseDeclRef = baseDeclRefType->getDeclRef();
- }
-
+ auto extInheritanceInfo = getInheritanceInfo(extDeclRef, circularityInfo);
addDirectBaseFacet(
- Facet::Kind::Type,
- baseType,
- selfIsBaseWitness,
- baseDeclRef,
- baseInheritanceInfo);
- };
-
- // If we know the type has a facet represented by `extensionTargetDeclRef`, we can consider
- // all extensions on this decl to see if they apply to the type.
- //
- auto considerExtension = [&](DeclRef<AggTypeDecl> extensionTargetDeclRef, Dictionary<Type*, SubtypeWitness*>* additionalSubtypeWitness)
+ Facet::Kind::Extension,
+ selfType,
+ selfIsSelf,
+ extDeclRef,
+ extInheritanceInfo);
+ result = true;
+ }
+ return result;
+ };
+
+ // We now look at the structure of the declaration itself
+ // to help us enumerate the direct bases.
+ //
+ auto currentDeclRef = declRef;
+ for (; currentDeclRef;)
+ {
+ if (auto aggTypeDeclBaseRef = currentDeclRef.as<AggTypeDeclBase>())
{
- bool result = false;
- for (auto extDecl : getCandidateExtensions(extensionTargetDeclRef, &visitor))
+ // 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))
{
- // 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.
+ // 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."
//
- // 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.
+ // We skip such pseudo-inheritance relationships for the purposes of determining
+ // the linearized list of bases.
//
- auto extDeclRef = applyExtensionToType(&visitor, extDecl, selfType, additionalSubtypeWitness);
- if (!extDeclRef)
+ if (typeConstraintDeclRef.getDecl()->hasModifier<IgnoreForLookupModifier>())
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`.
+ // The only case we will ever see a GenericTypeConstraintDecl inside a AggTypeDecl
+ // is when AggTypeDecl is a associatedtype decl. In this case, we will only lookup
+ // the type constraint if the constraint is on the associated type itself.
//
- auto extInheritanceInfo = getInheritanceInfo(extDeclRef, circularityInfo);
- addDirectBaseFacet(
- Facet::Kind::Extension,
- selfType,
- selfIsSelf,
- extDeclRef,
- extInheritanceInfo);
- result = true;
- }
- return result;
- };
-
- // We now look at the structure of the declaration itself
- // to help us enumerate the direct bases.
- //
- auto currentDeclRef = declRef;
- for (; currentDeclRef;)
- {
- if (auto aggTypeDeclBaseRef = currentDeclRef.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))
+ auto genericTypeConstraintDeclRef =
+ typeConstraintDeclRef.as<GenericTypeConstraintDecl>();
+ if (genericTypeConstraintDeclRef)
{
- // 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>())
+ // If the base expr on the constraint isn't even a `VarExpr`, then it can't be
+ // referencing the associated type itself and we can skip this constraint.
+ if (!genericTypeConstraintDeclRef.getDecl()->sub.type &&
+ !as<VarExpr>(genericTypeConstraintDeclRef.getDecl()->sub.exp))
continue;
+ }
- // The only case we will ever see a GenericTypeConstraintDecl inside a AggTypeDecl is when
- // AggTypeDecl is a associatedtype decl. In this case, we will only lookup the type constraint
- // if the constraint is on the associated type itself.
- //
- auto genericTypeConstraintDeclRef = typeConstraintDeclRef.as<GenericTypeConstraintDecl>();
- if (genericTypeConstraintDeclRef)
- {
- // If the base expr on the constraint isn't even a `VarExpr`, then it can't be referencing
- // the associated type itself and we can skip this constraint.
- if (!genericTypeConstraintDeclRef.getDecl()->sub.type
- && !as<VarExpr>(genericTypeConstraintDeclRef.getDecl()->sub.exp))
- continue;
- }
-
- visitor.ensureDecl(typeConstraintDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl);
+ visitor.ensureDecl(
+ typeConstraintDeclRef,
+ DeclCheckState::CanUseBaseOfInheritanceDecl);
- // For generic type constraint decls, always make sure it is about the type being checked.
- //
- if (genericTypeConstraintDeclRef)
- {
- auto subType = getSub(astBuilder, genericTypeConstraintDeclRef);
- if (subType != selfType)
- continue;
- }
- else if (currentDeclRef != declRef)
- {
+ // For generic type constraint decls, always make sure it is about the type being
+ // checked.
+ //
+ if (genericTypeConstraintDeclRef)
+ {
+ auto subType = getSub(astBuilder, genericTypeConstraintDeclRef);
+ if (subType != selfType)
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);
}
- }
- if (currentDeclRef.as<AssocTypeDecl>())
- {
- // If the current type is an associated type, continue inspecting the base/parent of the
- // associatedtype to discover additional constraints defined on the parent associatedtype decls.
- //
- if (auto lookupDeclRef = as<LookupDeclRef>(currentDeclRef.declRefBase))
+ else if (currentDeclRef != declRef)
{
- currentDeclRef = isDeclRefTypeOf<Decl>(lookupDeclRef->getLookupSource()).as<AssocTypeDecl>();
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);
}
- break;
}
-
- if (auto genericDeclRef = getDependentGenericParent(declRef))
+ if (currentDeclRef.as<AssocTypeDecl>())
{
- // 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.
+ // If the current type is an associated type, continue inspecting the base/parent of the
+ // associatedtype to discover additional constraints defined on the parent
+ // associatedtype decls.
//
- // 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.
-
- if (auto extensionDecl = as<ExtensionDecl>(genericDeclRef.getDecl()->inner))
+ if (auto lookupDeclRef = as<LookupDeclRef>(currentDeclRef.declRefBase))
{
- if (isDeclRefTypeOf<GenericTypeParamDecl>(extensionDecl->targetType.type) == declRef)
- {
- // If `T` is a generic parameter where the same generic is an extension on `T`,
- // then we need to add the extension itself as a facet.
- //
- auto extDeclRef = createDefaultSubstitutionsIfNeeded(astBuilder, &visitor, extensionDecl);
- auto selfExtFacet = new(arena) Facet::Impl(
- Facet::Kind::Extension,
- Facet::Directness::Direct,
- extDeclRef,
- selfType,
- astBuilder->getTypeEqualityWitness(selfType));
- allFacets.add(selfExtFacet);
- }
+ currentDeclRef =
+ isDeclRefTypeOf<Decl>(lookupDeclRef->getLookupSource()).as<AssocTypeDecl>();
+ continue;
}
+ }
+ break;
+ }
+
+ if (auto genericDeclRef = getDependentGenericParent(declRef))
+ {
+ // 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.
- for (auto constraintDeclRef : getMembersOfType<GenericTypeConstraintDecl>(astBuilder, genericDeclRef))
+ if (auto extensionDecl = as<ExtensionDecl>(genericDeclRef.getDecl()->inner))
+ {
+ if (isDeclRefTypeOf<GenericTypeParamDecl>(extensionDecl->targetType.type) == declRef)
{
- if (constraintDeclRef.getDecl()->checkState.isBeingChecked())
- continue;
+ // If `T` is a generic parameter where the same generic is an extension on `T`,
+ // then we need to add the extension itself as a facet.
+ //
+ auto extDeclRef =
+ createDefaultSubstitutionsIfNeeded(astBuilder, &visitor, extensionDecl);
+ auto selfExtFacet = new (arena) Facet::Impl(
+ Facet::Kind::Extension,
+ Facet::Directness::Direct,
+ extDeclRef,
+ selfType,
+ astBuilder->getTypeEqualityWitness(selfType));
+ allFacets.add(selfExtFacet);
+ }
+ }
+
+ for (auto constraintDeclRef :
+ getMembersOfType<GenericTypeConstraintDecl>(astBuilder, genericDeclRef))
+ {
+ if (constraintDeclRef.getDecl()->checkState.isBeingChecked())
+ continue;
- ensureDecl(&visitor, constraintDeclRef.getDecl(), DeclCheckState::CanSpecializeGeneric);
+ ensureDecl(&visitor, constraintDeclRef.getDecl(), DeclCheckState::CanSpecializeGeneric);
- auto subType = getSub(astBuilder, constraintDeclRef);
- auto superType = getSup(astBuilder, constraintDeclRef);
+ auto subType = getSub(astBuilder, constraintDeclRef);
+ auto superType = getSup(astBuilder, constraintDeclRef);
- // We only consider constraints where the type represented
- // by `declRef` is the subtype, since those
- // constraints are the ones that give us information about
- // the declared supertypes.
- //
- auto subDeclRefType = as<DeclRefType>(subType);
- if (!subDeclRefType)
+ // We only consider constraints where the type represented
+ // by `declRef` is the subtype, since those
+ // constraints are the ones that give us information about
+ // the declared supertypes.
+ //
+ auto subDeclRefType = as<DeclRefType>(subType);
+ if (!subDeclRefType)
+ {
+ if (auto subEachType = as<EachType>(subType))
{
- if (auto subEachType = as<EachType>(subType))
- {
- subDeclRefType = as<DeclRefType>(subEachType->getElementType());
- }
- if (!subDeclRefType)
- continue;
+ subDeclRefType = as<DeclRefType>(subEachType->getElementType());
}
- if (subDeclRefType->getDeclRef() != declRef)
+ if (!subDeclRefType)
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);
}
- }
+ if (subDeclRefType->getDeclRef() != declRef)
+ continue;
- // 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.
- //
- // An `extension` may apply to our type, if it directly extends
- // the type, or extends a generic `T` type that are constrained
- // on one of the interfaces that our type conforms to.
- //
- if (auto directAggTypeDeclRef = declRef.as<AggTypeDecl>())
- {
- considerExtension(directAggTypeDeclRef, nullptr);
+ // 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);
}
- if (!declRef.as<ExtensionDecl>())
+ }
+
+ // 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.
+ //
+ // An `extension` may apply to our type, if it directly extends
+ // the type, or extends a generic `T` type that are constrained
+ // on one of the interfaces that our type conforms to.
+ //
+ if (auto directAggTypeDeclRef = declRef.as<AggTypeDecl>())
+ {
+ considerExtension(directAggTypeDeclRef, nullptr);
+ }
+ if (!declRef.as<ExtensionDecl>())
+ {
+ HashSet<Type*> supTypesConsideredForExtensionApplication;
+ Dictionary<Type*, SubtypeWitness*> additionalSubtypeWitnesses;
+ for (;;)
{
- HashSet<Type*> supTypesConsideredForExtensionApplication;
- Dictionary<Type*, SubtypeWitness*> additionalSubtypeWitnesses;
- for (;;)
+ // After we flatten the list of bases, we may discover additional opportunities
+ // to apply extensions.
+ List<DeclRef<AggTypeDecl>> supTypeWorkList;
+ auto base = directBases.begin();
+ for (auto baseFacet = directBaseFacets.getHead(); baseFacet.getImpl();
+ baseFacet = baseFacet->next)
{
- // After we flatten the list of bases, we may discover additional opportunities
- // to apply extensions.
- List<DeclRef<AggTypeDecl>> supTypeWorkList;
- auto base = directBases.begin();
- for (auto baseFacet = directBaseFacets.getHead(); baseFacet.getImpl(); baseFacet = baseFacet->next)
+ for (auto facet : (*base)->facets)
{
- for (auto facet : (*base)->facets)
+ if (auto interfaceDeclRef = facet->origin.declRef.as<InterfaceDecl>())
{
- if (auto interfaceDeclRef = facet->origin.declRef.as<InterfaceDecl>())
+ SubtypeWitness* transitiveWitness = baseFacet->subtypeWitness;
+ transitiveWitness = astBuilder->getTransitiveSubtypeWitness(
+ baseFacet->subtypeWitness,
+ facet->subtypeWitness);
+ additionalSubtypeWitnesses.addIfNotExists(
+ facet->origin.type,
+ transitiveWitness);
+ if (supTypesConsideredForExtensionApplication.add(facet->origin.type))
{
- SubtypeWitness* transitiveWitness = baseFacet->subtypeWitness;
- transitiveWitness = astBuilder->getTransitiveSubtypeWitness(baseFacet->subtypeWitness, facet->subtypeWitness);
- additionalSubtypeWitnesses.addIfNotExists(facet->origin.type, transitiveWitness);
- if (supTypesConsideredForExtensionApplication.add(facet->origin.type))
- {
- supTypeWorkList.add(interfaceDeclRef);
- }
+ supTypeWorkList.add(interfaceDeclRef);
}
}
- ++base;
}
- bool canExit = true;
- for (auto baseItem : supTypeWorkList)
- {
- if (considerExtension(baseItem, &additionalSubtypeWitnesses))
- canExit = false;
- }
- if (canExit)
- break;
+ ++base;
}
+ bool canExit = true;
+ for (auto baseItem : supTypeWorkList)
+ {
+ if (considerExtension(baseItem, &additionalSubtypeWitnesses))
+ canExit = false;
+ }
+ if (canExit)
+ break;
}
+ }
- // 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.
+ // 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.
//
- // Note: This step takes quadratic time in the number of direct bases, but
- // there's really no other way to easily detect these issues.
+ 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 leftBase = directBaseFacets.getHead(); leftBase.getImpl(); leftBase = leftBase->next)
+ for (auto rightBase = leftBase->next; rightBase.getImpl(); rightBase = rightBase->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)
+ if (rightBase->kind != Facet::Kind::Type)
break;
- auto leftBaseType = leftBase->origin.type;
+ auto rightBaseType = rightBase->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 (visitor.isSubtype(leftBaseType, rightBaseType, IsSubTypeOptions::None))
{
- if (rightBase->kind != Facet::Kind::Type)
- break;
- auto rightBaseType = rightBase->origin.type;
-
- if (visitor.isSubtype(leftBaseType, rightBaseType, IsSubTypeOptions::None))
- {
- // 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, IsSubTypeOptions::None))
- {
- // 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.
- }
+ // 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, IsSubTypeOptions::None))
+ {
+ // 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);
+ // 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;
- }
+ InheritanceInfo info;
+ info.facets = allFacets;
+ return info;
+}
- void SharedSemanticsContext::_mergeFacetLists(DirectBaseList bases, FacetList baseFacets, FacetList::Builder& ioMergedFacets)
+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 (;;)
{
- // 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 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.
//
- // 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.
+ 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.
//
- // 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.
+ // 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.
//
- auto astBuilder = _getASTBuilder();
- auto& arena = astBuilder->getArena();
- for(;;)
+ Facet foundFacet;
+ DirectBaseInfo* foundBase = nullptr;
+ for (auto base : bases)
{
- // 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)).
+ Facet headFacet = base->facets.getHead();
- // If we have run out of lists that need merging, then we are done.
+ // 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.isEmpty())
- break;
+ if (bases.doesAnyTailContainMatchFor(headFacet))
+ continue;
- // 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.
+ // 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`.
//
- // 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.
- }
-
- // If we still cannot find a facet, then there is a true cycle in
- // the inheritance graph, which is an error in the user code.
- if (!foundFacet.getImpl())
- {
- if (!bases.isEmpty())
- {
- auto baseDecl = (*bases.begin())->facetImpl.origin.declRef.getDecl();
- getSink()->diagnose(baseDecl, Diagnostics::cyclicReferenceInInheritance, baseDecl);
- }
- return;
- }
+ foundFacet = headFacet;
+ foundBase = base;
+ break;
+ }
- // 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.
+ 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.
//
- 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).
+ // 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`.
//
- // 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.
+ // 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.
//
- if(originsMatch(foundFacet, baseFacets.getHead()))
+ 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.
+ }
+
+ // If we still cannot find a facet, then there is a true cycle in
+ // the inheritance graph, which is an error in the user code.
+ if (!foundFacet.getImpl())
+ {
+ if (!bases.isEmpty())
{
- auto directBaseFacet = baseFacets.popHead();
- ioMergedFacets.add(directBaseFacet);
+ auto baseDecl = (*bases.begin())->facetImpl.origin.declRef.getDecl();
+ getSink()->diagnose(baseDecl, Diagnostics::cyclicReferenceInInheritance, baseDecl);
}
- 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);
+ return;
+ }
- indirectFacet->subtypeWitness = selfIsSubtypeOfFacet;
+ // 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());
- ioMergedFacets.add(indirectFacet);
- }
+ // 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 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.
+ // We will initialize the fresh facet to a copy of the state of the
+ // `foundFacet`, albeit with a higher level of indirection.
//
- // 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.
+ // 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.
//
- for (auto base : bases)
- {
- if (originsMatch(foundFacet, base->facets.getHead()))
- {
- base->facets.advanceHead();
- continue;
- }
- }
+ *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.
//
- // 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.
+ // We can construct the appropriate witness transitively,
+ // by noting that:
//
- // 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.
+ // * 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.
//
- // 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.
+ SubtypeWitness* selfIsSubtypeOfBase = foundBase->facetImpl.subtypeWitness;
//
- 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.
+ // * 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.
//
- bases.removeEmptyLists();
+ SubtypeWitness* baseIsSubtypeOfFacet = foundFacet->subtypeWitness;
- // 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.
- }
+ auto selfIsSubtypeOfFacet = _getASTBuilder()->getTransitiveSubtypeWitness(
+ selfIsSubtypeOfBase,
+ baseIsSubtypeOfFacet);
- // 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`.
- }
+ indirectFacet->subtypeWitness = selfIsSubtypeOfFacet;
- // 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;
+ ioMergedFacets.add(indirectFacet);
+ }
- // 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.
+ // 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.
//
- 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.
+ // 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.
//
- if (left.declRef.getDecl() || right.declRef.getDecl())
+ for (auto base : bases)
{
- return left.declRef.getDecl()
- && right.declRef.getDecl()
- && left.declRef.equals(right.declRef);
+ if (originsMatch(foundFacet, base->facets.getHead()))
+ {
+ base->facets.advanceHead();
+ continue;
+ }
}
-
- // 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.
+ // 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.
//
- if (left.type || right.type)
+ // 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)
{
- return left.type
- && right.type
- && left.type->equals(right.type);
+ 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;
+ }
}
- // 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.
+ // 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.
//
- // 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>`).
+ bases.removeEmptyLists();
- return false;
+ // 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.
}
- // The remaining list-related operations that relate to the merging
- // process are relatively simple to follow once the definition of
- // matching is clear.
+ // 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`.
+}
- bool SharedSemanticsContext::DirectBaseList::doesAnyTailContainMatchFor(Facet facet) const
- {
- for (auto base : *this)
- {
- if (base->facets.isEmpty())
- continue;
- if (base->facets.getTail().containsMatchFor(facet))
- return true;
- }
+// 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);
}
- void SharedSemanticsContext::DirectBaseList::removeEmptyLists()
+ // 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)
{
- DirectBaseInfo** link = &_head;
- while (auto base = *link)
- {
- if (base->facets.isEmpty())
- {
- *link = base->next;
- }
- else
- {
- link = &base->next;
- }
- }
+ return left.type && right.type && left.type->equals(right.type);
}
- bool FacetList::containsMatchFor(Facet facet) const
+ // 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)
{
- for (auto f : *this)
- {
- if (originsMatch(f, facet))
- return true;
- }
- return false;
+ if (base->facets.isEmpty())
+ continue;
+ if (base->facets.getTail().containsMatchFor(facet))
+ return true;
}
+ return false;
+}
- InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(Type* type, InheritanceCircularityInfo* circularityInfo)
+void SharedSemanticsContext::DirectBaseList::removeEmptyLists()
+{
+ DirectBaseInfo** link = &_head;
+ while (auto base = *link)
{
- // 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))
+ if (base->facets.isEmpty())
{
- // 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, circularityInfo);
+ *link = base->next;
}
- else if (auto conjunctionType = as<AndType>(type))
+ else
{
- // 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();
+ link = &base->next;
+ }
+ }
+}
- // The linearized inheritance list for the conjunction
- // must include all the facets from the lists for `L`
- // and `R`, respectively.
- //
- auto leftInfo = getInheritanceInfo(leftType, circularityInfo);
- auto rightInfo = getInheritanceInfo(rightType, circularityInfo);
-
- // 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);
+bool FacetList::containsMatchFor(Facet facet) const
+{
+ for (auto f : *this)
+ {
+ if (originsMatch(f, facet))
+ return true;
+ }
+ return false;
+}
- InheritanceInfo info;
- info.facets = mergedFacets;
- return info;
- }
- else if (auto eachType = as<EachType>(type))
+InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(
+ Type* type,
+ InheritanceCircularityInfo* circularityInfo)
+{
+ // 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, circularityInfo);
+ }
+ 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, circularityInfo);
+ auto rightInfo = getInheritanceInfo(rightType, circularityInfo);
+
+ // 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 if (auto eachType = as<EachType>(type))
+ {
+ auto elementInheritanceInfo =
+ getInheritanceInfo(eachType->getElementType(), circularityInfo);
+ SemanticsVisitor visitor(this);
+ auto directFacet = new (arena) Facet::Impl(
+ Facet::Kind::Type,
+ Facet::Directness::Self,
+ DeclRef<Decl>(),
+ type,
+ visitor.createTypeEqualityWitness(type));
+ Facet tail = directFacet;
+ for (auto facet : elementInheritanceInfo.facets)
{
- auto elementInheritanceInfo = getInheritanceInfo(eachType->getElementType(), circularityInfo);
- SemanticsVisitor visitor(this);
- auto directFacet = new(arena) Facet::Impl(
- Facet::Kind::Type,
- Facet::Directness::Self,
- DeclRef<Decl>(),
- type,
- visitor.createTypeEqualityWitness(type));
- Facet tail = directFacet;
- for (auto facet : elementInheritanceInfo.facets)
+ if (facet->directness == Facet::Directness::Direct)
{
- if (facet->directness == Facet::Directness::Direct)
- {
- auto eachFacet = new(arena) Facet::Impl(
- Facet::Kind::Type,
- Facet::Directness::Direct,
- facet->origin.declRef,
- facet->origin.type,
- astBuilder->getEachSubtypeWitness(type, facet->subtypeWitness->getSup(), facet->subtypeWitness));
- tail->next = eachFacet;
- tail = eachFacet;
- }
+ auto eachFacet = new (arena) Facet::Impl(
+ Facet::Kind::Type,
+ Facet::Directness::Direct,
+ facet->origin.declRef,
+ facet->origin.type,
+ astBuilder->getEachSubtypeWitness(
+ type,
+ facet->subtypeWitness->getSup(),
+ facet->subtypeWitness));
+ tail->next = eachFacet;
+ tail = eachFacet;
}
- InheritanceInfo info;
- info.facets = FacetList(directFacet);
- 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;
}
+ InheritanceInfo info;
+ info.facets = FacetList(directFacet);
+ 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;
}
}
+} // namespace Slang
generated by cgit v1.2.3 (git 2.39.1) at 2026-07-02 06:05:21 +0000