// slang-check-inheritance.cpp
#include "slang-check-impl.h"

// This file implements the semantic checking logic
// related to computing linearized inheritance
// information for types and decalrations.

//#include "slang-lookup.h"
//#include "slang-syntax.h"
//#include "slang-ast-synthesis.h"
//#include <limits>

namespace Slang
{
    InheritanceInfo SharedSemanticsContext::getInheritanceInfo(Type* type)
    {
        // We cache the computed inheritance information for types,
        // and re-use that information whenever possible.

        if(auto found = m_mapTypeToInheritanceInfo.tryGetValue(type))
            return *found;

        // Note: we install a null pointer into the dictionary to act
        // as a sentinel during the processing of calculating the inheritnace
        // info. If we encounter this sentinel value during the calcuation,
        // it means that there was some kind of circular dependency in the
        // inheritance graph, and we need to avoid crashing or going
        // into an infinite loop in such cases.
        //
        m_mapTypeToInheritanceInfo[type] = InheritanceInfo();

        auto info = _calcInheritanceInfo(type);
        m_mapTypeToInheritanceInfo[type] = info;

        getSession()->m_typeDictionarySize = Math::Max(
            getSession()->m_typeDictionarySize, (int)m_mapTypeToInheritanceInfo.getCount());

        return info;
    }

    InheritanceInfo SharedSemanticsContext::getInheritanceInfo(DeclRef<ExtensionDecl> const& extension)
    {
        // We bottleneck the calculation of inheritance information
        // for type and `extension` `DeclRef`s through a single
        // routine with an optional `Type` parameter.
        //
        return _getInheritanceInfo(extension, nullptr);
    }

    InheritanceInfo SharedSemanticsContext::_getInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* declRefType)
    {
        // Just as with `Type`s, we cache and re-use the inheritance
        // information that has been computed for a `DeclRef` whenever
        // possible.

        if (auto found = m_mapDeclRefToInheritanceInfo.tryGetValue(declRef))
            return *found;

        // Note: we install a null pointer into the dictionary to act
        // as a sentinel during the processing of calculating the inheritnace
        // info. If we encounter this sentinel value during the calcuation,
        // it means that there was some kind of circular dependency in the
        // inheritance graph, and we need to avoid crashing or going
        // into an infinite loop in such cases.
        //
        m_mapDeclRefToInheritanceInfo[declRef] = InheritanceInfo();

        auto info = _calcInheritanceInfo(declRef, declRefType);
        m_mapDeclRefToInheritanceInfo[declRef] = info;

        return info;
    }

    InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* declRefType)
    {
        // This method is the main engine for computing linearized inheritance
        // lists for types and `extension` declarations.
        //
        // The approach we use for linearization of an inheritance graph is based on
        // what is the most broadly-accepted solution to the problem, presented in
        // "A Monotonic Superclass Linearization for Dylan" by Barret et al.
        // The algorithm recommended in that paper is also called the "C3 linearization
        // algorithm." Many developers are most familiar with C3 linearization because
        // it is used to compute the method resolution order (MRO) for a class in Python.
        //
        // The basic idea is that given a type declaration like:
        //
        //      class A : B, C { ... }
        //
        // we can construct a linearization of the transitive bases of `A`
        // by merging the linearizations for `B` and `C`. Any transitive
        // base of `A` should appear in the linearization for `B` and/or `C`,
        // so the main tasks are to remove duplicates (when a base type appears
        // in both the linearization of `B` *and* `C`), and to ensure that
        // the ordering is reasonable.
        //
        // What makes an ordering "reasonable" is a little subtle, especially
        // in the context of Slang. In the original use case, the order of types
        // in the linearization would determine which methods would override
        // which other ones, so different orderings could have large semantic
        // impact. Slang currently has less support for overriding, but is
        // likely to add more over time.
        //
        // At the very least, we require that if `S <: T` for types `S` and `T`,
        // then `S` should appear *before* `T` in the linearization. This, e.g.,
        // guarantees that a concrete type that implements an `interface` will
        // be listed before that interface and thus during lookup the members
        // of the concrete type will be found before those of the `interface`.
        //
        // We will revisit the question of "reasonable" orderings later, as
        // we get more into the core of the algorithm.

        // Our linearization approach will construct a list of *facets* for
        // the `declRef` in question, where each facet corresponds to a
        // transitive base type, or an applicable `extension`.
        //
        FacetList::Builder allFacets;

        // It is possible that `declRef` is itself a type declaration,
        // in which case `declRefType` will be the coresponding type.
        // However, if `declRef` is an `extension` declaration, we
        // will extract the type that the extension applies to, so
        // that we can have a consistent "self type" to represent
        // the type that is at the root of the inheritance list.
        //
        Type* selfType = declRefType;
        Facet::Kind selfFacetKind = Facet::Kind::Type;

        auto astBuilder = _getASTBuilder();
        auto& arena = astBuilder->getArena();
        SemanticsVisitor visitor(this);
        if (auto extensionDeclRef = declRef.as<ExtensionDecl>())
        {
            auto extendedType = getTargetType(astBuilder, extensionDeclRef);
            selfType = extendedType;
            selfFacetKind = Facet::Kind::Extension;
        }

        // Because we are dealing with entities that have declarations, the
        // first item in our linearization will always be a facet for
        // the declaration itself.
        //
        TypeEqualityWitness* selfIsSelf = selfType ? visitor.createTypeEqualityWitness(selfType) : nullptr;
        Facet selfFacet = new(arena) Facet::Impl(
            selfFacetKind,
            Facet::Directness::Self,
            declRef,
            selfType,
            selfIsSelf);
        allFacets.add(selfFacet);

        // After the self facet will come a list of facets formed
        // by merging the facet lists of each of the direct/declared
        // bases of the type/declaration in question.
        //
        // We will first traverse the structure of `declRef` to
        // accumulate the list of bases, and then perform the merge
        // when we are done.
        //
        DirectBaseList::Builder directBases;
        FacetList::Builder directBaseFacets;

        // We start with a simple operation to add an entry
        // into the list of direct bases, for the case where
        // we already have all of the relevant information
        // about that base.
        //
        auto addDirectBaseFacet = [&](
            Facet::Kind             kind,
            Type*                   baseType,
            SubtypeWitness*         selfIsBaseWitness,
            DeclRef<Decl> const&    baseDeclRef,
            InheritanceInfo const&  baseInheritanceInfo)
        {
            auto baseInfo = new(arena) DirectBaseInfo();

            // The information we store for each direct
            // base comprises two main things.
            //
            // First, we have a `Facet` that will represent
            // the base in the linearized inheritance list
            // we are building.
            //
            baseInfo->facetImpl = FacetImpl(
                kind,
                Facet::Directness::Direct,
                baseDeclRef,
                baseType,
                selfIsBaseWitness);
            Facet baseFacet(&baseInfo->facetImpl);
            //
            // Second, we have a list of the facets in the
            // linearization of the base itself.
            //
            baseInfo->facets = baseInheritanceInfo.facets;

            directBaseFacets.add(baseFacet);
            directBases.add(baseInfo);
        };

        // In the case where we know that the base being added
        // represents a direct base *type* (and not an `extension`)
        // we can derive some of the information needed by
        // `addDirectBaseFacet`.
        //
        auto addDirectBaseType = [&](
            Type*           baseType,
            SubtypeWitness* selfIsBaseWitness)
        {
            // If we are representing inheritance from a type,
            // then we should have a witness that the type
            // in question (either the type being declared by
            // `declRef`, or the type being *extended* by
            // `declRef`) inherits from that base.
            //
            SLANG_ASSERT(selfIsBaseWitness);

            auto baseInheritanceInfo = getInheritanceInfo(baseType);

            DeclRef<Decl> baseDeclRef;
            if (auto baseDeclRefType = as<DeclRefType>(baseType))
            {
                baseDeclRef = baseDeclRefType->getDeclRef();
            }

            addDirectBaseFacet(
                Facet::Kind::Type,
                baseType,
                selfIsBaseWitness,
                baseDeclRef,
                baseInheritanceInfo);
        };

        // We now look at the structure of the declaration itself
        // to help us enumerate the direct bases.
        //
        if (auto aggTypeDeclBaseRef = declRef.as<AggTypeDeclBase>())
        {
            // In the case where we have an aggregate type or `extension`
            // declaration, we can use the explicit list of direct bases.
            //
            for (auto typeConstraintDeclRef : getMembersOfType<TypeConstraintDecl>(_getASTBuilder(), aggTypeDeclBaseRef))
            {
                visitor.ensureDecl(typeConstraintDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl);

                // Note: In certain cases something takes the *syntactic* form of an inheritance
                // clause, but it is not actually something that should be treated as implying
                // a subtype relationship. For example, an `enum` declaration can use what looks
                // like an inheritance clause to indicate its underlying "tag type."
                //
                // We skip such pseudo-inheritance relationships for the purposes of determining
                // the linearized list of bases.
                //
                if (typeConstraintDeclRef.getDecl()->hasModifier<IgnoreForLookupModifier>())
                    continue;

                // The base type and subtype witness can easily be determined
                // using the `InheritanceDecl`.
                //
                auto baseType = getSup(astBuilder, typeConstraintDeclRef);
                auto satisfyingWitness = astBuilder->getDeclaredSubtypeWitness(
                    selfType,
                    baseType,
                    typeConstraintDeclRef);

                addDirectBaseType(baseType, satisfyingWitness);
            }
        }
        else if (auto genericTypeParamDeclRef = declRef.as<GenericTypeParamDecl>())
        {
            // The constraints placed on a generic type parameter are siblings of that
            // parameter in its parent `GenericDecl`, so we need to enumerate all of
            // the constraints of the parent declaration to find those that constrain
            // this parameter.
            //
            // TODO(tfoley): We might consider adding a cached representation of the
            // constraint information that is keyed on a per-parameter basis. Such a
            // representation would need to take into account canonicalization of
            // constraints.

            auto genericDeclRef = genericTypeParamDeclRef.getParent().as<GenericDecl>();
            SLANG_ASSERT(genericDeclRef);

            ensureDecl(&visitor, genericDeclRef.getDecl(), DeclCheckState::CanSpecializeGeneric);

            for (auto constraintDeclRef : getMembersOfType<GenericTypeConstraintDecl>(astBuilder, genericDeclRef))
            {
                auto subType = getSub(astBuilder, constraintDeclRef);
                auto superType = getSup(astBuilder, constraintDeclRef);

                // We only consider constraints where the type represented
                // by `genericTypeParamDeclRef` is the subtype, since those
                // constraints are the ones that give us information about
                // the declared supertypes.
                //
                // TODO: consider whether other kinds of constraints could
                // also apply here.
                //
                auto subDeclRefType = as<DeclRefType>(subType);
                if (!subDeclRefType)
                    continue;
                if (subDeclRefType->getDeclRef() != genericTypeParamDeclRef)
                    continue;

                // Because the constraint is a declared inheritance relationship,
                // adding the base to our list of direct bases is as straightforward
                // as in all the preceding cases.
                //
                auto satisfyingWitness = _getASTBuilder()->getDeclaredSubtypeWitness(
                    selfType,
                    superType,
                    constraintDeclRef);
                addDirectBaseType(superType, satisfyingWitness);
            }
        }

        // At this point we have enumerated all of the bases that can be
        // gleaned by looking at the `declRef` itself. The next step is
        // to consider any `extension` declarations that might apply to
        // a type being delared.
        //
        // In our current system, only nominal types (those with `Decl`s)
        // can be extended, so we begin by checking if the `selfType`
        // is a nominal/`DeclRef` type.
        //
        // Note: this step will *not* apply when `declRef` is an `extension`
        // declaration, since it directly checks for an `AggTypeDecl`
        // instead of an `AggTypeDeclBase`.
        //
        // Similarly, we do *not* add the type being extended to the list
        // of bases for an `extension`.
        //
        // These choices are important to avoid circular dependencies, where
        // the linearization of an `extension` would end up depending on its
        // own linearization (either directly or through a dependency on
        // the linearization of the type being extended).
        //
        // Instead, the linearization we create here for an `extension` will
        // *only* contain facets for the members introduced by the `extension`
        // itself, as well as any transitive bases declared on that `extension`.
        //
        if (auto directAggTypeDeclRef = declRef.as<AggTypeDecl>())
        {
            for (auto extDecl : getCandidateExtensions(directAggTypeDeclRef, &visitor))
            {
                // The list of *candidate* extensions is computed and
                // cached based on the identity of the declaration alone,
                // and does not take into account any generic arguments
                // of either the type or the `extension`.
                //
                // For example, we might have an `extension` that applies
                // to `vector<float,N>` for any `N`, but the `selfType`
                // that we are working with could be `<vector<int,2>` so
                // that the extension doesn't match.
                //
                // In order to make sure that we don't enumerate members
                // that don't make sense in context, we must apply
                // the extension to the type and see if we succeed in
                // making a match.
                //
                auto extDeclRef = applyExtensionToType(&visitor, extDecl, selfType);
                if (!extDeclRef)
                    continue;

                // In the case where we *do* find an extension that
                // applies to the type, we add a declared base to
                // represent the `extension`, knowing that its
                // own linearized inheritance list will include
                // any transitive based declared on the `extension`.
                //
                auto extInheritanceInfo = getInheritanceInfo(extDeclRef);
                addDirectBaseFacet(
                    Facet::Kind::Extension,
                    selfType,
                    selfIsSelf,
                    extDeclRef,
                    extInheritanceInfo);
            }
        }

        // At this point, the list of direct bases (each with its own linearization)
        // is complete.
        //
        // At this point we could scan through the list of bases and perform
        // consistency checks on it. For example, when two types in the list of direct
        // bases have a subtype relationship between them, it is possible that the
        // programmer made some kind of mistake, and we could emit a diagnostic
        // about it.
        //
        // The published C3 algorithm actually considers the declared list of bases
        // as one of the inputs to its merge, and is very strict about ordering.
        // As such, it would be an error for strict C3 if direct bases were declared
        // in an order that is inconsitent with the partial order determined by
        // the subtype relationship. Our implementation of linearization is relaxed
        // compared to C3 so that it is robust to such ordering issues.
        //
        // Note: This step takes quadratic time in the number of direct bases, but
        // there's really no other way to easily detect these issues.
        //
        for(auto leftBase = directBaseFacets.getHead(); leftBase.getImpl(); leftBase = leftBase->next)
        {
            // Note: all of the direct base facets with a `Type` kind will
            // precede all of those with `Extension` kind, so we can bail
            // out of the outer loop as soon as we find a non-`Type`
            // facet.
            //
            if(leftBase->kind != Facet::Kind::Type)
                break;
            auto leftBaseType = leftBase->origin.type;

            // For the inner loop we scan only the facets that appear *after*
            // the `leftBase` in the list of direct bases.
            //
            for(auto rightBase = leftBase->next; rightBase.getImpl(); rightBase = rightBase->next)
            {
                if (rightBase->kind != Facet::Kind::Type)
                    break;
                auto rightBaseType = rightBase->origin.type;

                if (visitor.isSubtype(leftBaseType, rightBaseType))
                {
                    // If a type earlier in the list of bases is a subtype of
                    // one later in the list, then the ordering is consistent
                    // with the linearization that will be produced, but it
                    // might represent a mistake on the programmer's part,
                    // since they listed a base type that is redundant.
                    //
                    // TODO: decide whether to diagnose this case.
                }
                else if (visitor.isSubtype(rightBaseType, leftBaseType))
                {
                    // If a type later in the list is a subtype of a type earlier
                    // in the list, then the declared list of bases is inconsistent
                    // with the ordering that will (indeed *must*) appear in the
                    // linearization we generate.
                    //
                    // If we end up implementing a strict version of the C3 algorithm,
                    // we would need to treat such situations as an error, or at least
                    // emit a warning and then remove the subtype from the list of
                    // bases.
                    //
                    // TODO: decide whether to diagnose this case.
                }
            }
        }

        // Now that we've built up the list of direct bases and their
        // respective linearizations, we can apply the core merge algorithm
        // to those lists to produce the rest of the linearization for
        // the declaration in question.
        //
        _mergeFacetLists(directBases, directBaseFacets, allFacets);

        InheritanceInfo info;
        info.facets = allFacets;
        return info;
    }

    void SharedSemanticsContext::_mergeFacetLists(DirectBaseList bases, FacetList baseFacets, FacetList::Builder& ioMergedFacets)
    {
        // Our task here is to take the list of direct/declared `bases`,
        // each of which holds a linearized list of `Facet`s, and produce
        // a single linearized list of facets in `ioMergedFacets`.
        //
        // The `Facet`s in the lists referenced by `bases` are always
        // relative to the base type/extension itself, and not to
        // the type or declaration for which we are computing
        // a linearization.
        //
        // The `baseFacets` list provides one `Facet` for each direct
        // base that are relative to the type/declaration we are
        // computing a linearization for. These facets will be used
        // directly, instead of those from `bases`, where possible.
        //
        auto astBuilder = _getASTBuilder();
        auto& arena = astBuilder->getArena();
        for(;;)
        {
            // The basic logic here is that on each iteration we
            // will look at the first item on each list in `bases`
            // and pick one that we will append to the merged output
            // (after removing it from the relevant input(s)).

            // If we have run out of lists that need merging, then we are done.
            //
            if (bases.isEmpty())
                break;

            // Otherwise, we will look at the remaining non-empty lists,
            // and see if one of them starts with an facet that can
            // be appended to our merged output.
            //
            // If multiple such facets are viable, we will always take
            // the one from the earliest list in `bases`. Doing so favors
            // the types that appear earlier in a list of bases.
            //
            Facet foundFacet;
            DirectBaseInfo* foundBase = nullptr;
            for (auto base : bases)
            {
                Facet headFacet = base->facets.getHead();

                // If the head facet of the `base` list appears at a non-head
                // position in any of the other lists, we cannot append this
                // element without risking inverting the order of some facets
                // relative to those other lists.
                //
                if (bases.doesAnyTailContainMatchFor(headFacet))
                    continue;

                // Otherwise, we are safe to add the `headFacet` to our
                // merged list, because it only ever appears as the head
                // of one or more of the lists in `bases`.
                //
                foundFacet = headFacet;
                foundBase = base;
                break;
            }

            if(!foundFacet)
            {
                // If we could not identify a facet that could be safely
                // removed from any of the base lists, then it means that
                // we must have a cycle in the ordering constraints implied
                // by the `bases` lists.
                //
                // The simplest example of such a cycle would be if we
                // had two lists, `A` and `B`, such that:
                //
                //      A = { X, Y }
                //      B = { Y, X }
                //
                // In this case, producing output in the order `X, Y` *or*
                // `Y, X` will always invalidate the ordering constraints
                // implied by either `A` or `B`.
                //
                // In the C3 algorithm as published, such a situation is an
                // error, and the algorithm fails to produce a linearization.
                // The reason for this decision is that allowing this case
                // means that a base type and a derived type could disagree
                // on the relative priority of method overrides, and thus
                // a subclass could possible break semantic assumptions of
                // a superclass.
                //
                // In a more static language like Slang, it seems better to
                // allow more flexible inheritance, *especially* when dealing
                // with things like `interface`s and `extension`s, where the
                // relative ordering of things will often be immaterial.
                //
                // In a case like this, we would like to arbitrarily pick
                // one or the other of `X` and `Y`, and given our default
                // policy to favor the earlier list in `bases` where possible,
                // we would select `X` from `A`.
                //
                // One thing worth noting is that when a case like the above
                // arises, it is not possible that `X <: Y` or `Y <: X`.
                // If a subtype relationship existed between the two, then
                // they would be consistently ordered in *both* lists.
                // We thus do not have to worry about violating the most
                // important requirement for a "reasonable" linearization.
                //
                foundBase = *bases.begin();
                foundFacet = foundBase->facets.getHead();

                // Note: because we are grabbing a facet that might appear
                // in a non-head position in one or more of our lists,
                // we need to have a plan for what to do when we see
                // that same facet come to the front of one of our lists
                // later.
            }

            // At this point we definitely have a facet we'd like to
            // add to the output, whether it was found via the true
            // C3 approach, or our relaxed rule above.
            //
            SLANG_ASSERT(foundFacet.getImpl());

            // If the facet we want to append to the output is the same as the front-most
            // facet on the list of bases, then we want to use that facet as-is (since we
            // have already allocated storage for it).
            //
            // TODO: in cases where the strict C3 algorithm would fail, and we choose a
            // `foundFacet` that is at a non-head position in at least some lists, it
            // might be possible that we have a facet that matches ones of the `baseFacets`,
            // but not the head one. We should confirm what happens in that case.
            //
            if(originsMatch(foundFacet, baseFacets.getHead()))
            {
                auto directBaseFacet = baseFacets.popHead();
                ioMergedFacets.add(directBaseFacet);
            }
            else
            {
                // This facet is seemingly *not* a facet that represents one of the direct
                // bases for the type/declaration being processed.
                //
                // As such, we need to allocate a fresh facet to represent it in the
                // linearization we are creating, since the `foundFacet` already belongs
                // to the linearization of one of the bases, and shouldn't be repurposed.
                //
                auto indirectFacet = new(arena) Facet::Impl();

                // We will initialize the fresh facet to a copy of the state of the
                // `foundFacet`, albeit with a higher level of indirection.
                //
                // TODO: In principle we could search through  all of the lists to
                // find the one with a facet matching `foundFacet` with minimum
                // indirection, so that our measure of indirection is always
                // as small as possible for any given facet.
                //
                *indirectFacet = *(foundFacet.getImpl());
                indirectFacet->next = nullptr;
                indirectFacet->directness =
                    Facet::Directness(Facet::DirectnessVal(indirectFacet->directness) + 1);

                // When using this facet for subtype tests, or when looking
                // up member through this facet, we will need a witness
                // to show that the self type of the declaration being
                // linearized (the type being declared or extended) is a
                // subtype of the type for this facet.
                //
                // We can construct the appropriate witness transitively,
                // by noting that:
                //
                // * The self type is known to be a subtype of the direct
                //   base represented by `foundBase`, and the facet for
                //   that base stores a witness to that fact.
                //
                SubtypeWitness* selfIsSubtypeOfBase = foundBase->facetImpl.subtypeWitness;
                //
                // * The direct base type must be a subtype of the type
                //   for any facet found in its own linearization, and
                //   the `foundFacet` that came from the relevant base
                //   stores a witness to that fact.
                //
                SubtypeWitness* baseIsSubtypeOfFacet = foundFacet->subtypeWitness;

                auto selfIsSubtypeOfFacet = _getASTBuilder()->getTransitiveSubtypeWitness(
                    selfIsSubtypeOfBase,
                    baseIsSubtypeOfFacet);

                indirectFacet->subtypeWitness = selfIsSubtypeOfFacet;

                ioMergedFacets.add(indirectFacet);
            }

            // We picked one `foundFacet` above to be added to the merged
            // output list, and we now need to ensure that we won't ever
            // emit a matching facet again.
            //
            // In the case of the strict/standard C3 algorithm, any facets
            // matching `foundFacet` would need to appear at a head position
            // in one of the base lists. As such, it is sufficient to run
            // through the base lists, check for a match at the head of each,
            // and remove any matching facets we find.
            //
            for (auto base : bases)
            {
                if (originsMatch(foundFacet, base->facets.getHead()))
                {
                    base->facets.advanceHead();
                    continue;
                }
            }
            //
            // Because we are not implementing the C3 algorithm strictly,
            // we need a solution for the case where `foundFacet` is
            // in a non-head position in one or more of the base lists.
            //
            // Proactively filtering `foundFacet` out of all of the lists
            // is possible, but given that these are singly-linked lists
            // we cannot easily filter them without either allocation
            // or mutation.
            //
            // Instead, we will filter out facets that have already been
            // added to the merged list as needed, when such facets come
            // to the front of the relevant list.
            //
            for (auto base : bases)
            {
                for(;;)
                {
                    // For each base list, we will check if its
                    // head facet is one that has already been
                    // emitted to the output.
                    //
                    // If the head facet has not been emitted
                    // already, we don't need to perform any
                    // filtering on the base list at this time.
                    //
                    auto head = base->facets.getHead();
                    if (!ioMergedFacets.containsMatchFor(head))
                        break;

                    // Otherwise, we remove the head facet from
                    // the given base list and test again, unless
                    // the list is now empty.
                    //
                    base->facets.advanceHead();
                    if (base->facets.isEmpty())
                        break;
                }
            }

            // The filtering step might have led to one or more
            // of the `bases` lists becomming empty. Our merge
            // algorithm really only wants to consider non-empty
            // lists, so we go ahead and remove the empty lists
            // here.
            //
            bases.removeEmptyLists();

            // At this point all of the lists have been appropriately filtered,
            // and we are ready to circle back around again to the step
            // where select a facet to add to the merged list.
        }

        // At this point, all of the input lists in `bases` should be empty,
        // and all of the facets in those lists should have found their way
        // over to `ioMergedFacets`.
    }

    // The mering algorithm needs to be able to test if two potentially-distinct
    // `Facet`s represent the same underlying type or declaration.
    //
    bool originsMatch(Facet left, Facet right)
    {
        if (left.getImpl() == right.getImpl())
            return true;
        if (!left.getImpl() || !right.getImpl())
            return false;

        // If both of the facets are non-null, and not
        // identical, we check if their origins match,
        // meaning that they represent the same type
        // or declaration.
        //
        return left->origin == right->origin;
    }

    bool operator==(Facet::Origin left, Facet::Origin right)
    {
        // If either facet represents a declaration, then
        // the origins only match if they both represent
        // the *same* declaration.
        //
        if (left.declRef.getDecl() || right.declRef.getDecl())
        {
            return left.declRef.getDecl()
                && right.declRef.getDecl()
                && left.declRef.equals(right.declRef);
        }

        // Otherwise, if they both represent types, then the
        // origins match if they are the same type.
        //
        // Note: an `extension` facet will always have a non-null
        // `declRef`, so there is no risk here of an `extension`
        // and a type facet being matched by this step; they
        // would always land in the case above.
        //
        if (left.type || right.type)
        {
            return left.type
                && right.type
                && left.type->equals(right.type);
        }

        // TODO: The rules we are using for matching here
        // would need to be revisited and overhauled significantly
        // if we start supporting generic type declarations
        // with covariant/contravariant type parameters.
        //
        // In such cases we would need to treat two facets as
        // matching if their declarations or types are an exact
        // matching modulo type arguments, and the relationship
        // between pairwise type arguments is consistent with
        // the variance of the corresponding parameter.
        //
        // E.g., we would need to treat facets for `IEnumerable<Derived>`
        // and `IEnumerable<Base>` as matching, and ensure that a
        // merged output list for a type/declaration could only
        // include the more specific of the two (`IEnumerable<Derived>`).

        return false;
    }

    // The remaining list-related operations that relate to the merging
    // process are relatively simple to follow once the definition of
    // matching is clear.

    bool SharedSemanticsContext::DirectBaseList::doesAnyTailContainMatchFor(Facet facet) const
    {
        for (auto base : *this)
        {
            if (base->facets.getTail().containsMatchFor(facet))
                return true;
        }
        return false;
    }

    void SharedSemanticsContext::DirectBaseList::removeEmptyLists()
    {
        DirectBaseInfo** link = &_head;
        while (auto base = *link)
        {
            if (base->facets.isEmpty())
            {
                *link = base->next;
            }
            else
            {
                link = &base->next;
            }
        }
    }

    bool FacetList::containsMatchFor(Facet facet) const
    {
        for (auto f : *this)
        {
            if (originsMatch(f, facet))
                return true;
        }
        return false;
    }

    InheritanceInfo SharedSemanticsContext::_calcInheritanceInfo(Type* type)
    {
        // The majority of the interesting for for computing linearized
        // inheritance information arises for `DeclRef`s, but we still
        // need a way to compute the relevant information for types
        // that might or might not be defined using `Decl`s.

        auto astBuilder = _getASTBuilder();
        auto& arena = astBuilder->getArena();
        if (auto declRefType = as<DeclRefType>(type))
        {
            // The `DeclRef` case is the easy one, since we can
            // bottleneck through the logic that gets shared between
            // type and `extension` declarations.
            //
            return _getInheritanceInfo(declRefType->getDeclRef(), declRefType);
        }
        else if (auto conjunctionType = as<AndType>(type))
        {
            // In this case, we have a type of the form `L & R`,
            // such that it is a subtype of both `L` and `R`.
            //
            auto leftType = conjunctionType->getLeft();
            auto rightType = conjunctionType->getRight();

            // The linearized inheritance list for the conjunction
            // must include all the facets from the lists for `L`
            // and `R`, respectively.
            //
            auto leftInfo = getInheritanceInfo(leftType);
            auto rightInfo = getInheritanceInfo(rightType);

            // We have a case of subtype witness that can show that
            // `T : L` or `T : R` based on `T : L&R`. In this case,
            // though, the type `T` is actually `L&R` itself, so
            // we need to construct an identity witness for `L&R : L&R`
            // to give it something to start from.
            //
            auto selfIsSelf = astBuilder->getTypeEqualityWitness(conjunctionType);
            auto selfIsSubtypeOfLeft = _getASTBuilder()->getExtractFromConjunctionSubtypeWitness(type, leftType, selfIsSelf, 0);
            auto selfIsSubtypeOfRight = _getASTBuilder()->getExtractFromConjunctionSubtypeWitness(type, rightType, selfIsSelf, 1);

            // We will set up to perform a merge between the facet
            // lists for the two "bases" `L` and `R`. Note that  the
            // information we write into the `facetImpl` in each case
            // is largely just for completeness and debugging, since
            // we are *not* going to add those facets into a list
            // of direct base facets to be merged.
            //
            DirectBaseInfo leftBaseInfo;
            leftBaseInfo.facetImpl = FacetImpl(
                Facet::Kind::Type,
                Facet::Directness::Direct,
                DeclRef<Decl>(),
                leftType,
                selfIsSubtypeOfLeft);
            leftBaseInfo.facets = leftInfo.facets;

            DirectBaseInfo rightBaseInfo;
            rightBaseInfo.facetImpl = FacetImpl(
                Facet::Kind::Type,
                Facet::Directness::Direct,
                DeclRef<Decl>(),
                rightType,
                selfIsSubtypeOfRight);
            rightBaseInfo.facets = rightInfo.facets;

            DirectBaseList::Builder directBases;
            directBases.add(&leftBaseInfo);
            directBases.add(&rightBaseInfo);

            // The merging step is then the same as for the more "standard" case,
            // with the only detail that we are not passing in a list of facets
            // to represent the directly-declared bases (since there are none;
            // this is a structural rather than nominal type).
            //
            FacetList::Builder mergedFacets;
            _mergeFacetLists(directBases, FacetList(), mergedFacets);

            InheritanceInfo info;
            info.facets = mergedFacets;
            return info;
        }
        else
        {
            // As a fallback, any type not covered by the above cases will
            // get a trivial linearization that consists of a single facet
            // corresponding to that type itself.
            //
            SemanticsVisitor visitor(this);
            auto directFacet = new(arena) Facet::Impl(
                Facet::Kind::Type,
                Facet::Directness::Self,
                DeclRef<Decl>(),
                type,
                visitor.createTypeEqualityWitness(type));

            InheritanceInfo info;
            info.facets = FacetList(directFacet);
            return info;
        }
    }
}