Create and cache flattened inheritance lists (#2740)

* Create and cache flattened inheritance lists

The basic change here is to have a cached lookup that can map a `Type`,
or a `DeclRef` that might refer to a type or `extension`, to a list of
the *facets* that comprise it.

The notion of a *facet* here is similar to what the C++ standard calls
"sub-objects".
A declared type like a `struct` has:

* a facet for its own direct members
* one facet for each of its (transitive) base `struct` types
* one facet for each `interface` it conforms to
* one facet for each `extension` that applies to that type

The set of facets for a type is de-duplicated (so that "diamond"
inheritance patterns don't cause issues) and deterministically ordered,
using a variation of the C3 linearization algorithm.

The creation of a linearized list of facets should help the compiler
implementation in two key places:

* Testing if a type implements an interface (or inherits from a base
  type) should now only take time linear in the number of (transitive)
  bases of that type. We can simply scan the linearized facet list to
  see if it contains a facet corresponding to the given base.

* Looking up the members of a type (or a value of a given type) should
  be greatly simplified, since all of the members can be found in a
  single linear scan of the facet list. In addition, those facets will
  be ordered so that facets for "more derived" types will precede those
  for "less derived" types, so that shadowing in the case of overrides
  should be easier to implement.

This change only implements the first of these two improvements, since
there is already a *lot* of churn involved.

Notes and caveats:

* The handling of conjunction types (e.g., `IFoo & IBar`) complicates
  the implementation, both because the simple approach to subtype
  testing alluded to above is no longer complete, and also because
  we need to be more careful about what forms of subtype witnesses
  we construct, so that we can maintain the currently-required invariant
  that two witnesses are only equal if they have matching structure.

* We don't implement the full/"proper" C3 algorithm here because it has
  some failure cases that we'd still like to support. In particular if
  we have both `IX : IA, IB` and `IY : IB, IA`, the C3 algorithm says it
  is illegal to have `IZ : IX, IY` because the two bases it inherits
  from disagree on the relative ordering of `IA` and `IB` in their
  own linearizations. Handling such cases may make our implementation
  less efficient, and it will also require testing of those corner
  caes.

* When it comes time to revamp the implementation of lookup, we will
  need to deal with the fact that a single linear list (seemingly)
  cannot give us sufficient information to decide which of two members
  of the same name should shadow the other, or if there is an ambiguity.
  Or rather, it *can* give us that information if we are willing to
  accept some very user-unfriendly behavior and simply say that
  declarations earlier in the linearization always shadow later
  declarations, even if the facets involved are not related by an
  inheritance relationship of any kind.

* In order to remove one kind of vicious circularity from the approach,
  the linearization that we are computing for `extension` declarations
  will not be sufficient for lookups in the body of such an `extension`.
  A future change may need to have support for creating and caching
  two distinct linearizations for each `extension`: one that is to be
  used when that `extension` is pulled into the linearization for a
  type that it applies to, and another for when lookup will be performed
  in the context of the `extension` itself.

* This change does *not* include the simple expedient of adding a direct
  cache for subtype tests to the `SharedSemanticsContext`, although
  adding such a cache would be a simple matter.

* This change introduces more deduplication for subtype witnesses,
  which should enable more deduplication for other `Val`s (including
  `Type`s), but it does not introduce any assumptions that equal
  `Val`s or `Type`s must have identical pointer representations.

* Eventually we may find that, similar to the situation with `Type`s,
  we will want to have a split between surface-level and canonicalized
  versions of other `Val`s, including subtype witnesses.

* Fix clang error.

* remove debugging code.

---------

Co-authored-by: Yong He <yonghe@outlook.com>

1 files changed, 945 insertions, 0 deletions

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