// slang-check-inheritance.cpp #include "slang-check-impl.h" // This file implements the semantic checking logic // related to computing linearized inheritance // information for types and decalrations. 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(); auto info = _calcInheritanceInfo(type, circularityInfo); m_mapTypeToInheritanceInfo[type] = info; return info; } InheritanceInfo SharedSemanticsContext::getInheritanceInfo( DeclRef const& extension, InheritanceCircularityInfo* 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. // 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) { if (decl == info->decl) { getSink()->diagnose(decl, Diagnostics::circularityInExtension, decl); return true; } } return false; } InheritanceInfo SharedSemanticsContext::_getInheritanceInfo( DeclRef declRef, Type* selfType, 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(); auto info = _calcInheritanceInfo(declRef, selfType, circularityInfo); m_mapDeclRefToInheritanceInfo[declRef] = info; getSession()->m_typeDictionarySize = Math::Max( getSession()->m_typeDictionarySize, (int)m_mapDeclRefToInheritanceInfo.getCount()); return info; } 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; }; 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++) { if (auto argDeclRef = isDeclRefTypeOf(genericAppDeclRef->getArg(i))) { getDependentGenericParentImpl(genericParent, argDeclRef); } } } } DeclRef SharedSemanticsContext::getDependentGenericParent(DeclRef declRef) { DeclRef genericParent; getDependentGenericParentImpl(genericParent, declRef); return genericParent; } InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo( DeclRef declRef, Type* selfType, 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; Facet::Kind selfFacetKind = Facet::Kind::Type; auto astBuilder = _getASTBuilder(); auto& arena = astBuilder->getArena(); SemanticsVisitor visitor(this); if (auto extensionDeclRef = declRef.as()) { auto extendedType = getTargetType(astBuilder, extensionDeclRef); selfType = extendedType; selfFacetKind = Facet::Kind::Extension; } // Because we are dealing with entities that have declarations, the // first item in our linearization will always be a facet for // the declaration itself. // TypeEqualityWitness* selfIsSelf = selfType ? visitor.createTypeEqualityWitness(selfType) : nullptr; Facet selfFacet = new (arena) Facet::Impl( astBuilder, 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) { auto baseInfo = new (arena) DirectBaseInfo(); // The information we store for each direct // base comprises two main things. // // First, we have a `Facet` that will represent // the base in the linearized inheritance list // we are building. // baseInfo->facetImpl = FacetImpl( astBuilder, kind, Facet::Directness::Direct, baseDeclRef, baseType, selfIsBaseWitness); Facet baseFacet(&baseInfo->facetImpl); // // Second, we have a list of the facets in the // linearization of the base itself. // baseInfo->facets = baseInheritanceInfo.facets; directBaseFacets.add(baseFacet); directBases.add(baseInfo); }; // In the case where we know that the base being added // represents a direct base *type* (and not an `extension`) // we can derive some of the information needed by // `addDirectBaseFacet`. // auto addDirectBaseType = [&](Type* baseType, SubtypeWitness* selfIsBaseWitness) { // If we are representing inheritance from a type, // then we should have a witness that the type // in question (either the type being declared by // `declRef`, or the type being *extended* by // `declRef`) inherits from that base. // SLANG_ASSERT(selfIsBaseWitness); auto baseInheritanceInfo = getInheritanceInfo(baseType, circularityInfo); DeclRef baseDeclRef; if (auto baseDeclRefType = as(baseType)) { baseDeclRef = baseDeclRefType->getDeclRef(); } 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) { bool result = false; auto candidateExtensions = getCandidateExtensions(extensionTargetDeclRef, &visitor); for (auto extDecl : candidateExtensions) { // 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. // // In order to make sure that we don't enumerate members // that don't make sense in context, we must apply // the extension to the type and see if we succeed in // making a match. // auto extDeclRef = applyExtensionToType(&visitor, extDecl, selfType, additionalSubtypeWitness); if (!extDeclRef) continue; // In the case where we *do* find an extension that // applies to the type, we add a declared base to // represent the `extension`, knowing that its // own linearized inheritance list will include // any transitive based declared on the `extension`. // auto extInheritanceInfo = getInheritanceInfo(extDeclRef, 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)) { // 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()) 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); // 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) { 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)) { 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. if (auto extensionDecl = as(genericDeclRef.getDecl()->inner)) { 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) .as(); auto extInheritanceInfo = getInheritanceInfo(extDeclRef, circularityInfo); addDirectBaseFacet( Facet::Kind::Extension, selfType, selfIsSelf, extDeclRef, extInheritanceInfo); } } bool selfIsGenericParamType = isDeclRefTypeOf(selfType) != nullptr; for (auto constraintDeclRef : getMembersOfType(astBuilder, genericDeclRef)) { if (constraintDeclRef.getDecl()->checkState.isBeingChecked()) continue; ensureDecl(&visitor, constraintDeclRef.getDecl(), DeclCheckState::ScopesWired); // Check only the sub-type. visitor.CheckConstraintSubType(constraintDeclRef.getDecl()->sub); auto sub = constraintDeclRef.getDecl()->sub; // If the sub-type part of the generic constraint is a member expression, it can't // possibly be defining a constraint for a generic type parameter, so we skip it // to avoid circular checking on the generic param type. if (selfIsGenericParamType && as(sub.exp)) continue; if (!sub.type) sub = visitor.TranslateTypeNodeForced(sub); auto subType = constraintDeclRef.substitute(astBuilder, sub.type); // 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)) { subDeclRefType = as(subEachType->getElementType()); } if (!subDeclRefType) continue; } if (subDeclRefType->getDeclRef() != declRef) continue; // Further check the constraint, since we now need the sup-type. ensureDecl(&visitor, constraintDeclRef.getDecl(), DeclCheckState::CanSpecializeGeneric); auto superType = getSup(astBuilder, constraintDeclRef); // Because the constraint is a declared inheritance relationship, // adding the base to our list of direct bases is as straightforward // as in all the preceding cases. // auto satisfyingWitness = _getASTBuilder()->getDeclaredSubtypeWitness(selfType, superType, constraintDeclRef); addDirectBaseType(superType, satisfyingWitness); } } // At this point we have enumerated all of the bases that can be // gleaned by looking at the `declRef` itself. The next step is // to consider any `extension` declarations that might apply to // a type being delared. // // 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 (;;) { // 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) { 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)) { supTypeWorkList.add(interfaceDeclRef); } } } ++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. // // Note: This step takes quadratic time in the number of direct bases, but // there's really no other way to easily detect these issues. // for (auto leftBase = directBaseFacets.getHead(); leftBase.getImpl(); leftBase = leftBase->next) { // Note: all of the direct base facets with a `Type` kind will // precede all of those with `Extension` kind, so we can bail // out of the outer loop as soon as we find a non-`Type` // facet. // if (leftBase->kind != Facet::Kind::Type) break; auto leftBaseType = leftBase->origin.type; // For the inner loop we scan only the facets that appear *after* // the `leftBase` in the list of direct bases. // for (auto rightBase = leftBase->next; rightBase.getImpl(); rightBase = rightBase->next) { if (rightBase->kind != Facet::Kind::Type) break; auto rightBaseType = rightBase->origin.type; if (visitor.isSubtype(leftBaseType, rightBaseType, 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. } } } // Now that we've built up the list of direct bases and their // respective linearizations, we can apply the core merge algorithm // to those lists to produce the rest of the linearization for // the declaration in question. // _mergeFacetLists(directBases, directBaseFacets, allFacets); InheritanceInfo info; info.facets = allFacets; return info; } void SharedSemanticsContext::_mergeFacetLists( DirectBaseList bases, FacetList baseFacets, FacetList::Builder& ioMergedFacets) { // Our task here is to take the list of direct/declared `bases`, // each of which holds a linearized list of `Facet`s, and produce // a single linearized list of facets in `ioMergedFacets`. // // The `Facet`s in the lists referenced by `bases` are always // relative to the base type/extension itself, and not to // the type or declaration for which we are computing // a linearization. // // The `baseFacets` list provides one `Facet` for each direct // base that are relative to the type/declaration we are // computing a linearization for. These facets will be used // directly, instead of those from `bases`, where possible. // auto astBuilder = _getASTBuilder(); auto& arena = astBuilder->getArena(); for (;;) { // The basic logic here is that on each iteration we // will look at the first item on each list in `bases` // and pick one that we will append to the merged output // (after removing it from the relevant input(s)). // If we have run out of lists that need merging, then we are done. // if (bases.isEmpty()) break; // Otherwise, we will look at the remaining non-empty lists, // and see if one of them starts with an facet that can // be appended to our merged output. // // If multiple such facets are viable, we will always take // the one from the earliest list in `bases`. Doing so favors // the types that appear earlier in a list of bases. // Facet foundFacet; DirectBaseInfo* foundBase = nullptr; for (auto base : bases) { Facet headFacet = base->facets.getHead(); // If the head facet of the `base` list appears at a non-head // position in any of the other lists, we cannot append this // element without risking inverting the order of some facets // relative to those other lists. // if (bases.doesAnyTailContainMatchFor(headFacet)) continue; // Otherwise, we are safe to add the `headFacet` to our // merged list, because it only ever appears as the head // of one or more of the lists in `bases`. // foundFacet = headFacet; foundBase = base; break; } if (!foundFacet) { // If we could not identify a facet that could be safely // removed from any of the base lists, then it means that // we must have a cycle in the ordering constraints implied // by the `bases` lists. // // The simplest example of such a cycle would be if we // had two lists, `A` and `B`, such that: // // A = { X, Y } // B = { Y, X } // // In this case, producing output in the order `X, Y` *or* // `Y, X` will always invalidate the ordering constraints // implied by either `A` or `B`. // // In the C3 algorithm as published, such a situation is an // error, and the algorithm fails to produce a linearization. // The reason for this decision is that allowing this case // means that a base type and a derived type could disagree // on the relative priority of method overrides, and thus // a subclass could possible break semantic assumptions of // a superclass. // // In a more static language like Slang, it seems better to // allow more flexible inheritance, *especially* when dealing // with things like `interface`s and `extension`s, where the // relative ordering of things will often be immaterial. // // In a case like this, we would like to arbitrarily pick // one or the other of `X` and `Y`, and given our default // policy to favor the earlier list in `bases` where possible, // we would select `X` from `A`. // // One thing worth noting is that when a case like the above // arises, it is not possible that `X <: Y` or `Y <: X`. // If a subtype relationship existed between the two, then // they would be consistently ordered in *both* lists. // We thus do not have to worry about violating the most // important requirement for a "reasonable" linearization. // foundBase = *bases.begin(); foundFacet = foundBase->facets.getHead(); // Note: because we are grabbing a facet that might appear // in a non-head position in one or more of our lists, // we need to have a plan for what to do when we see // that same facet come to the front of one of our lists // later. } // 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; } // At this point we definitely have a facet we'd like to // add to the output, whether it was found via the true // C3 approach, or our relaxed rule above. // SLANG_ASSERT(foundFacet.getImpl()); // If the facet we want to append to the output is the same as the front-most // facet on the list of bases, then we want to use that facet as-is (since we // have already allocated storage for it). // // TODO: in cases where the strict C3 algorithm would fail, and we choose a // `foundFacet` that is at a non-head position in at least some lists, it // might be possible that we have a facet that matches ones of the `baseFacets`, // but not the head one. We should confirm what happens in that case. // if (originsMatch(foundFacet, baseFacets.getHead())) { auto directBaseFacet = baseFacets.popHead(); ioMergedFacets.add(directBaseFacet); } else { // This facet is seemingly *not* a facet that represents one of the direct // bases for the type/declaration being processed. // // As such, we need to allocate a fresh facet to represent it in the // linearization we are creating, since the `foundFacet` already belongs // to the linearization of one of the bases, and shouldn't be repurposed. // auto indirectFacet = new (arena) Facet::Impl(); // We will initialize the fresh facet to a copy of the state of the // `foundFacet`, albeit with a higher level of indirection. // // TODO: In principle we could search through all of the lists to // find the one with a facet matching `foundFacet` with minimum // indirection, so that our measure of indirection is always // as small as possible for any given facet. // *indirectFacet = *(foundFacet.getImpl()); indirectFacet->next = nullptr; indirectFacet->directness = Facet::Directness(Facet::DirectnessVal(indirectFacet->directness) + 1); // When using this facet for subtype tests, or when looking // up member through this facet, we will need a witness // to show that the self type of the declaration being // linearized (the type being declared or extended) is a // subtype of the type for this facet. // // We can construct the appropriate witness transitively, // by noting that: // // * The self type is known to be a subtype of the direct // base represented by `foundBase`, and the facet for // that base stores a witness to that fact. // SubtypeWitness* selfIsSubtypeOfBase = foundBase->facetImpl.subtypeWitness; // // * The direct base type must be a subtype of the type // for any facet found in its own linearization, and // the `foundFacet` that came from the relevant base // stores a witness to that fact. // SubtypeWitness* baseIsSubtypeOfFacet = foundFacet->subtypeWitness; // Check if this would create an unwanted struct->struct->interface conformance // We want to prevent transitive witnesses of the form: struct Child -> struct Parent -> // interface IFoo bool shouldSkipTransitiveWitness = false; auto selfType = selfIsSubtypeOfBase->getSub(); auto baseType = selfIsSubtypeOfBase->getSup(); auto facetType = baseIsSubtypeOfFacet->getSup(); if (selfType && baseType && facetType) { auto selfDeclRef = isDeclRefTypeOf(selfType); auto baseDeclRef = isDeclRefTypeOf(baseType); auto facetDeclRef = isDeclRefTypeOf(facetType); // Only skip if we have struct->struct->interface // and the struct->struct witness is not the identity witness shouldSkipTransitiveWitness = selfDeclRef && baseDeclRef && facetDeclRef && !isTypeEqualityWitness(selfIsSubtypeOfBase); } if (!shouldSkipTransitiveWitness) { auto selfIsSubtypeOfFacet = _getASTBuilder()->getTransitiveSubtypeWitness( selfIsSubtypeOfBase, baseIsSubtypeOfFacet); indirectFacet->setSubtypeWitness(_getASTBuilder(), selfIsSubtypeOfFacet); ioMergedFacets.add(indirectFacet); } } // We picked one `foundFacet` above to be added to the merged // output list, and we now need to ensure that we won't ever // emit a matching facet again. // // In the case of the strict/standard C3 algorithm, any facets // matching `foundFacet` would need to appear at a head position // in one of the base lists. As such, it is sufficient to run // through the base lists, check for a match at the head of each, // and remove any matching facets we find. // for (auto base : bases) { if (originsMatch(foundFacet, base->facets.getHead())) { base->facets.advanceHead(); continue; } } // // Because we are not implementing the C3 algorithm strictly, // we need a solution for the case where `foundFacet` is // in a non-head position in one or more of the base lists. // // Proactively filtering `foundFacet` out of all of the lists // is possible, but given that these are singly-linked lists // we cannot easily filter them without either allocation // or mutation. // // Instead, we will filter out facets that have already been // added to the merged list as needed, when such facets come // to the front of the relevant list. // for (auto base : bases) { for (;;) { // For each base list, we will check if its // head facet is one that has already been // emitted to the output. // // If the head facet has not been emitted // already, we don't need to perform any // filtering on the base list at this time. // auto head = base->facets.getHead(); if (!ioMergedFacets.containsMatchFor(head)) break; // Otherwise, we remove the head facet from // the given base list and test again, unless // the list is now empty. // base->facets.advanceHead(); if (base->facets.isEmpty()) break; } } // The filtering step might have led to one or more // of the `bases` lists becomming empty. Our merge // algorithm really only wants to consider non-empty // lists, so we go ahead and remove the empty lists // here. // bases.removeEmptyLists(); // At this point all of the lists have been appropriately filtered, // and we are ready to circle back around again to the step // where select a facet to add to the merged list. } // At this point, all of the input lists in `bases` should be empty, // and all of the facets in those lists should have found their way // over to `ioMergedFacets`. } // The mering algorithm needs to be able to test if two potentially-distinct // `Facet`s represent the same underlying type or declaration. // bool originsMatch(Facet left, Facet right) { if (left.getImpl() == right.getImpl()) return true; if (!left.getImpl() || !right.getImpl()) return false; // If both of the facets are non-null, and not // identical, we check if their origins match, // meaning that they represent the same type // or declaration. // return left->origin == right->origin; } bool operator==(Facet::Origin left, Facet::Origin right) { // If either facet represents a declaration, then // the origins only match if they both represent // the *same* declaration. // if (left.declRef.getDecl() || right.declRef.getDecl()) { return left.declRef.getDecl() && right.declRef.getDecl() && left.declRef.equals(right.declRef); } // Otherwise, if they both represent types, then the // origins match if they are the same type. // // Note: an `extension` facet will always have a non-null // `declRef`, so there is no risk here of an `extension` // and a type facet being matched by this step; they // would always land in the case above. // if (left.type || right.type) { return left.type && right.type && left.type->equals(right.type); } // TODO: The rules we are using for matching here // would need to be revisited and overhauled significantly // if we start supporting generic type declarations // with covariant/contravariant type parameters. // // In such cases we would need to treat two facets as // matching if their declarations or types are an exact // matching modulo type arguments, and the relationship // between pairwise type arguments is consistent with // the variance of the corresponding parameter. // // E.g., we would need to treat facets for `IEnumerable` // 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) { if (base->facets.isEmpty()) continue; if (base->facets.getTail().containsMatchFor(facet)) return true; } return false; } void SharedSemanticsContext::DirectBaseList::removeEmptyLists() { DirectBaseInfo** link = &_head; while (auto base = *link) { if (base->facets.isEmpty()) { *link = base->next; } else { link = &base->next; } } } bool FacetList::containsMatchFor(Facet facet) const { for (auto f : *this) { if (originsMatch(f, facet)) return true; } return false; } InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo( Type* type, 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 extractExistentialType = as(type)) { return _getInheritanceInfo( extractExistentialType->getThisTypeDeclRef(), extractExistentialType, 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( astBuilder, Facet::Kind::Type, Facet::Directness::Direct, DeclRef(), leftType, selfIsSubtypeOfLeft); leftBaseInfo.facets = leftInfo.facets; DirectBaseInfo rightBaseInfo; rightBaseInfo.facetImpl = FacetImpl( astBuilder, 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( astBuilder, 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) { auto eachFacet = new (arena) Facet::Impl( astBuilder, 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 if (auto modifiedType = as(type)) { return _calcInheritanceInfo(modifiedType->getBase(), circularityInfo); } 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( astBuilder, Facet::Kind::Type, Facet::Directness::Self, DeclRef(), type, visitor.createTypeEqualityWitness(type)); InheritanceInfo info; info.facets = FacetList(directFacet); return info; } } } // namespace Slang