From f65d756bff8d4c5cbc15bd0322a2ae8e6b896a21 Mon Sep 17 00:00:00 2001 From: Ellie Hermaszewska Date: Tue, 29 Oct 2024 14:49:26 +0800 Subject: format * format * Minor test fixes * enable checking cpp format in ci --- source/slang/slang-check-inheritance.cpp | 1961 +++++++++++++++--------------- 1 file changed, 996 insertions(+), 965 deletions(-) (limited to 'source/slang/slang-check-inheritance.cpp') 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(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(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 const& extension, InheritanceCircularityInfo* circularityInfo) +InheritanceInfo SharedSemanticsContext::getInheritanceInfo( + DeclRef 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 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 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& genericParent, DeclRef declRef) - { - auto mergeParent = [](DeclRef& currentParent, DeclRef newParent) - { - if (!currentParent) - { - currentParent = newParent; - return; - } - if (currentParent == newParent) - return; - if (newParent.getDecl()->isChildOf(currentParent.getDecl())) - currentParent = newParent; - }; + return info; +} - if (declRef.as()) +void SharedSemanticsContext::getDependentGenericParentImpl( + DeclRef& genericParent, + DeclRef declRef) +{ + auto mergeParent = [](DeclRef& currentParent, DeclRef newParent) + { + if (!currentParent) { - if (!genericParent) - mergeParent(genericParent, declRef.getParent().as()); + currentParent = newParent; return; } - else if (auto lookupDeclRef = as(declRef.declRefBase)) - { - if (auto lookupSourceDeclRef = isDeclRefTypeOf(lookupDeclRef->getLookupSource())) - getDependentGenericParentImpl(genericParent, lookupSourceDeclRef); - } - else if (auto genericAppDeclRef = as(declRef.declRefBase)) + if (currentParent == newParent) + return; + if (newParent.getDecl()->isChildOf(currentParent.getDecl())) + currentParent = newParent; + }; + + if (declRef.as()) + { + if (!genericParent) + mergeParent(genericParent, declRef.getParent().as()); + return; + } + else if (auto lookupDeclRef = as(declRef.declRefBase)) + { + if (auto lookupSourceDeclRef = isDeclRefTypeOf(lookupDeclRef->getLookupSource())) + getDependentGenericParentImpl(genericParent, lookupSourceDeclRef); + } + else if (auto genericAppDeclRef = as(declRef.declRefBase)) + { + for (Index i = 0; i < genericAppDeclRef->getArgCount(); i++) { - for (Index i = 0; i < genericAppDeclRef->getArgCount(); i++) + if (auto argDeclRef = isDeclRefTypeOf(genericAppDeclRef->getArg(i))) { - if (auto argDeclRef = isDeclRefTypeOf(genericAppDeclRef->getArg(i))) - { - getDependentGenericParentImpl(genericParent, argDeclRef); - } + getDependentGenericParentImpl(genericParent, argDeclRef); } } } +} + +DeclRef SharedSemanticsContext::getDependentGenericParent(DeclRef declRef) +{ + DeclRef genericParent; + getDependentGenericParentImpl(genericParent, declRef); + return genericParent; +} - DeclRef SharedSemanticsContext::getDependentGenericParent(DeclRef declRef) +InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo( + DeclRef 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()) { - DeclRef genericParent; - getDependentGenericParentImpl(genericParent, declRef); - return genericParent; + auto extendedType = getTargetType(astBuilder, extensionDeclRef); + selfType = extendedType; + selfFacetKind = Facet::Kind::Extension; } - InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(DeclRef 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 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()) + auto baseInheritanceInfo = getInheritanceInfo(baseType, circularityInfo); + + DeclRef baseDeclRef; + if (auto baseDeclRefType = as(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 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 extensionTargetDeclRef, + Dictionary* 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` for any `N`, but the `selfType` + // that we are working with could be `` 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 baseDeclRef; - if (auto baseDeclRefType = as(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 extensionTargetDeclRef, Dictionary* 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()) { - 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(_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` for any `N`, but the `selfType` - // that we are working with could be `` 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()) 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()) - { - // 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(_getASTBuilder(), aggTypeDeclBaseRef)) + auto genericTypeConstraintDeclRef = + typeConstraintDeclRef.as(); + 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()) + // 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(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(); - 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(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()) - { - // 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(currentDeclRef.declRefBase)) + else if (currentDeclRef != declRef) { - currentDeclRef = isDeclRefTypeOf(lookupDeclRef->getLookupSource()).as(); 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()) { - // 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(genericDeclRef.getDecl()->inner)) + if (auto lookupDeclRef = as(currentDeclRef.declRefBase)) { - if (isDeclRefTypeOf(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(lookupDeclRef->getLookupSource()).as(); + 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(astBuilder, genericDeclRef)) + if (auto extensionDecl = as(genericDeclRef.getDecl()->inner)) + { + if (isDeclRefTypeOf(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(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(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(subType); + if (!subDeclRefType) + { + if (auto subEachType = as(subType)) { - if (auto subEachType = as(subType)) - { - subDeclRefType = as(subEachType->getElementType()); - } - if (!subDeclRefType) - continue; + subDeclRefType = as(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()) - { - 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()) + } + + // 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()) + { + considerExtension(directAggTypeDeclRef, nullptr); + } + if (!declRef.as()) + { + HashSet supTypesConsideredForExtensionApplication; + Dictionary additionalSubtypeWitnesses; + for (;;) { - HashSet supTypesConsideredForExtensionApplication; - Dictionary additionalSubtypeWitnesses; - for (;;) + // After we flatten the list of bases, we may discover additional opportunities + // to apply extensions. + List> 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> 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()) { - if (auto interfaceDeclRef = facet->origin.declRef.as()) + 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` - // and `IEnumerable` as matching, and ensure that a - // merged output list for a type/declaration could only - // include the more specific of the two (`IEnumerable`). + 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` + // and `IEnumerable` as matching, and ensure that a + // merged output list for a type/declaration could only + // include the more specific of the two (`IEnumerable`). + + 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(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(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(), - leftType, - selfIsSubtypeOfLeft); - leftBaseInfo.facets = leftInfo.facets; - - DirectBaseInfo rightBaseInfo; - rightBaseInfo.facetImpl = FacetImpl( - Facet::Kind::Type, - Facet::Directness::Direct, - DeclRef(), - 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(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(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(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(), + leftType, + selfIsSubtypeOfLeft); + leftBaseInfo.facets = leftInfo.facets; + + DirectBaseInfo rightBaseInfo; + rightBaseInfo.facetImpl = FacetImpl( + Facet::Kind::Type, + Facet::Directness::Direct, + DeclRef(), + 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(type)) + { + auto elementInheritanceInfo = + getInheritanceInfo(eachType->getElementType(), circularityInfo); + SemanticsVisitor visitor(this); + auto directFacet = new (arena) Facet::Impl( + Facet::Kind::Type, + Facet::Directness::Self, + DeclRef(), + 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(), - 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(), - 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(), + type, + visitor.createTypeEqualityWitness(type)); + + InheritanceInfo info; + info.facets = FacetList(directFacet); + return info; } } +} // namespace Slang -- cgit v1.2.3