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, 157 insertions, 466 deletions

diff --git a/source/slang/slang-check-conformance.cpp b/source/slang/slang-check-conformance.cpp
index 7379a6538..0eb44399d 100644
--- a/source/slang/slang-check-conformance.cpp
+++ b/source/slang/slang-check-conformance.cpp
@@ -7,195 +7,6 @@
 
 namespace Slang
 {
-    DeclaredSubtypeWitness* SemanticsVisitor::createSimpleSubtypeWitness(
-        TypeWitnessBreadcrumb*  breadcrumb)
-    {
-        DeclaredSubtypeWitness* witness = m_astBuilder->getOrCreate<DeclaredSubtypeWitness>(
-            breadcrumb->sub,
-            breadcrumb->sup,
-            breadcrumb->declRef);
-        return witness;
-    }
-
-    
-    Val* simplifyWitness(ASTBuilder* builder, Val* witness)
-    {
-        if (auto extractFromConjunction = as<ExtractFromConjunctionSubtypeWitness>(witness))
-        {
-            auto simplWitness = simplifyWitness(builder, extractFromConjunction->conjunctionWitness);
-            if (auto conjunction = as<ConjunctionSubtypeWitness>(simplWitness))
-            {
-                auto index = extractFromConjunction->indexInConjunction;
-                SLANG_ASSERT(index == 0 || index == 1);
-                if (index == 0)
-                    return conjunction->leftWitness;
-                else
-                    return conjunction->rightWitness;
-            }
-            ExtractFromConjunctionSubtypeWitness* simplExtractFromConjunction = builder->create<ExtractFromConjunctionSubtypeWitness>();
-            simplExtractFromConjunction->sub = extractFromConjunction->sub;
-            simplExtractFromConjunction->sup = extractFromConjunction->sup;
-            simplExtractFromConjunction->indexInConjunction = extractFromConjunction->indexInConjunction;
-            simplExtractFromConjunction->conjunctionWitness = as<SubtypeWitness>(simplWitness);
-
-            return simplExtractFromConjunction;
-        }
-        else if (auto conjunctionWitness = as<ConjunctionSubtypeWitness>(witness))
-        {
-            auto simplConjunctionWitness = builder->create<ConjunctionSubtypeWitness>();
-            simplConjunctionWitness->leftWitness = as<SubtypeWitness>(simplifyWitness(builder, conjunctionWitness->leftWitness));
-            simplConjunctionWitness->rightWitness = as<SubtypeWitness>(simplifyWitness(builder, conjunctionWitness->rightWitness));
-            simplConjunctionWitness->sub = conjunctionWitness->sub;
-            simplConjunctionWitness->sup = conjunctionWitness->sup;
-
-            return simplConjunctionWitness;
-        }
-        else if (auto transitiveWitness = as<TransitiveSubtypeWitness>(witness))
-        {
-            TransitiveSubtypeWitness* simplTransitiveWitness = builder->getOrCreateWithDefaultCtor<TransitiveSubtypeWitness>(
-                transitiveWitness->sub,
-                transitiveWitness->sup,
-                transitiveWitness->midToSup);
-
-            simplTransitiveWitness->sub = transitiveWitness->sub;
-            simplTransitiveWitness->sup = transitiveWitness->sup;
-            simplTransitiveWitness->midToSup = as<SubtypeWitness>(simplifyWitness(builder, transitiveWitness->midToSup));
-            simplTransitiveWitness->subToMid = as<SubtypeWitness>(simplifyWitness(builder, transitiveWitness->subToMid));
-
-            return simplTransitiveWitness;
-        }
-        else
-        {
-            // TODO: Add other cases.
-            return witness;
-        }
-    }
-
-
-    Val* SemanticsVisitor::createTypeWitness(
-        Type*            subType,
-        DeclRef<AggTypeDecl>    superTypeDeclRef,
-        TypeWitnessBreadcrumb*  inBreadcrumbs)
-    {
-        SLANG_UNUSED(subType);
-        SLANG_UNUSED(superTypeDeclRef);
-
-        if(!inBreadcrumbs)
-        {
-            // We need to construct a witness to the fact
-            // that `subType` has been proven to be *equal*
-            // to `superTypeDeclRef`.
-            //
-            auto witness = m_astBuilder->create<TypeEqualityWitness>();
-            witness->sub = subType;
-            witness->sup = subType;
-            return witness;
-        }
-
-        // We might have one or more steps in the breadcrumb trail, e.g.:
-        //
-        //      {A : B} {B : C} {C : D}
-        //
-        // The chain is stored as a reversed linked list, so that
-        // the first entry would be the `(C : D)` relationship
-        // above.
-        //
-        // We need to walk the list and build up a suitable witness,
-        // which in the above case would look like:
-        //
-        //      Transitive(
-        //          Transitive(
-        //              Declared({A : B}),
-        //              {B : C}),
-        //          {C : D})
-        //
-        // Because of the ordering of the breadcrumb trail, along
-        // with the way the `Transitive` case nests, we will be
-        // building these objects outside-in, and keeping
-        // track of the "hole" where the next step goes.
-        //
-        auto bb = inBreadcrumbs;
-
-        // `witness` here will hold the first (outer-most) object
-        // we create, which is the overall result.
-        SubtypeWitness* witness = nullptr;
-
-        // `link` will point at the remaining "hole" in the
-        // data structure, to be filled in.
-        SubtypeWitness** link = &witness;
-
-        // As long as there is more than one breadcrumb, we
-        // need to be creating transitive witnesses.
-        while (bb->prev)
-        {
-            // On the first iteration when processing the list
-            // above, the breadcrumb would be for `{ C : D }`,
-            // and so we'd create:
-            //
-            //      Transitive(
-            //          [...],
-            //          { C : D})
-            //
-            // where `[...]` represents the "hole" we leave
-            // open to fill in next.
-            //
-            if (bb->flavor == TypeWitnessBreadcrumb::Flavor::DeclFlavor)
-            {
-                DeclaredSubtypeWitness* declaredWitness =
-                    m_astBuilder->getOrCreate<DeclaredSubtypeWitness>(
-                        bb->sub, bb->sup, bb->declRef);
-
-                TransitiveSubtypeWitness* transitiveWitness = m_astBuilder->getOrCreateWithDefaultCtor<TransitiveSubtypeWitness>();
-                transitiveWitness->sub = subType;
-                transitiveWitness->sup = bb->sup;
-                transitiveWitness->midToSup = declaredWitness;
-
-                // Fill in the current hole, and then set the
-                // hole to point into the node we just created.
-                *link = transitiveWitness;
-                link = &transitiveWitness->subToMid;
-            }
-            else if(bb->flavor == TypeWitnessBreadcrumb::Flavor::AndTypeLeftFlavor)
-            {
-                ExtractFromConjunctionSubtypeWitness* extractWitness = m_astBuilder->create<ExtractFromConjunctionSubtypeWitness>();
-                extractWitness->sub = subType;
-                extractWitness->sup = bb->sup;
-                extractWitness->indexInConjunction = 0;
-
-                *link = extractWitness;
-                link = (SubtypeWitness**) &extractWitness->conjunctionWitness;
-            }
-            else if(bb->flavor == TypeWitnessBreadcrumb::Flavor::AndTypeRightFlavor)
-            {
-                ExtractFromConjunctionSubtypeWitness* extractWitness = m_astBuilder->create<ExtractFromConjunctionSubtypeWitness>();
-                extractWitness->sub = subType;
-                extractWitness->sup = bb->sup;
-                extractWitness->indexInConjunction = 1;
-
-                *link = extractWitness;
-                link = (SubtypeWitness**) &extractWitness->conjunctionWitness;
-            }
-            // Move on with the list.
-            bb = bb->prev;
-        }
-
-        // If we exit the loop, then there is only one breadcrumb left.
-        // In our running example this would be `{ A : B }`. We create
-        // a simple (declared) subtype witness for it, and plug the
-        // final hole, after which there shouldn't be a hole to deal with.
-        DeclaredSubtypeWitness* declaredWitness = createSimpleSubtypeWitness(bb);
-        *link = declaredWitness;
-
-        // Simplify witnesses of the form ExtractFromConjunction(ConjunctionWitness(...))
-        // TODO: At some point, we need a more robust way of checking that two witnesses are in-fact 'equal'.
-        // In the meantime, this step should suffice.
-        
-
-        // We now know that our original `witness` variable has been
-        // filled in, and there are no other holes.
-        return simplifyWitness(m_astBuilder, witness);
-    }
-
     bool SemanticsVisitor::isInterfaceSafeForTaggedUnion(
         DeclRef<InterfaceDecl> interfaceDeclRef)
     {
@@ -238,146 +49,141 @@ namespace Slang
         }
     }
 
-    bool SemanticsVisitor::_isDeclaredSubtype(
-        Type*            originalSubType,
-        Type*            subType,
-        DeclRef<AggTypeDecl>    superTypeDeclRef,
-        Val**            outWitness,
-        TypeWitnessBreadcrumb*  inBreadcrumbs)
+    SubtypeWitness* SemanticsVisitor::isSubtype(
+        Type*                   subType,
+        Type*                   superType)
     {
-        // for now look up a conformance member...
-        if(auto declRefType = as<DeclRefType>(subType))
-        {
-            auto declRef = declRefType->declRef;
-
-            // Easy case: a type conforms to itself.
-            //
-            // TODO: This is actually a bit more complicated, as
-            // the interface needs to be "object-safe" for us to
-            // really make this determination...
-            if(declRef == superTypeDeclRef)
-            {
-                if(outWitness)
-                {
-                    *outWitness = createTypeWitness(originalSubType, superTypeDeclRef, inBreadcrumbs);
-                }
-                return true;
-            }
-            if (const auto dynamicType = as<DynamicType>(subType))
-            {
-                // A __Dynamic type always conforms to the interface via its witness table.
-                if (outWitness)
-                {
-                    *outWitness = m_astBuilder->create<DynamicSubtypeWitness>();
-                }
-                return true;
-            }
-            else if( auto aggTypeDeclRef = declRef.as<AggTypeDecl>() )
-            {
-                ensureDecl(aggTypeDeclRef, DeclCheckState::CanEnumerateBases);
-
-                bool found = false;
-                foreachDirectOrExtensionMemberOfType<InheritanceDecl>(this, aggTypeDeclRef, [&](DeclRef<InheritanceDecl> const& inheritanceDeclRef)
-                {
-                    ensureDecl(inheritanceDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl);
-
-                    // Here we will recursively look up conformance on the type
-                    // that is being inherited from. This is dangerous because
-                    // it might lead to infinite loops.
-                    //
-                    // TODO: A better approach would be to create a linearized list
-                    // of all the interfaces that a given type directly or indirectly
-                    // inherits, and store it with the type, so that we don't have
-                    // to recurse in places like this (and can maybe catch infinite
-                    // loops better). This would also help avoid checking multiply-inherited
-                    // conformances multiple times.
-
-                    auto inheritedType = getBaseType(m_astBuilder, inheritanceDeclRef);
-
-
-                    // There's one annoying corner case where something that *looks* like an inheritnace
-                    // declaration isn't actually one, and that is when an `enum` type includes an explicit
-                    // declaration of its "tag type."
-                    //
-                    if (auto enumDeclRef = declRef.as<EnumDecl>())
-                    {
-                        if (inheritedType->equals(getTagType(m_astBuilder, enumDeclRef)))
-                        {
-                            return;
-                        }
-                    }
-
-
-                    // We need to ensure that the witness that gets created
-                    // is a composite one, reflecting lookup through
-                    // the inheritance declaration.
-                    TypeWitnessBreadcrumb breadcrumb;
-                    breadcrumb.prev = inBreadcrumbs;
-
-                    breadcrumb.sub = subType;
-                    breadcrumb.sup = inheritedType;
-                    breadcrumb.declRef = inheritanceDeclRef;
+        // TODO: The Slang codebase is currently being quite slippery by conflating
+        // multiple concepts, all under the banner of a "subtype" test:
+        //
+        // * Struct/class inheritance: When concrete type `A` inherits from concrete
+        //   type `B`, we can directly convert any value of type `A` into a value of type `B`
+        //
+        // * Derived interfaces: When interface `X` derives from interface `Y`, we know
+        //   that any concrete type conforming to `X` must also conform to `Y`, so we can
+        //   derive a witness that `A : Y` from a witness tbale that `A : X` for some concrete `A`
+        //
+        // * Conformance: When concrete type `A` conforms to interface `X`, we know that there exists
+        //   a witness table for that conformance.
+        //
+        // The problem is that these relationships mean different things. If we use the same
+        // `isSubtype()` test for all of the above cases, then we risk determining that `IFoo`
+        // *conforms* to `IBar` just because it was declared as `interface IFoo : IBar`. Or
+        // even more simply that `IFoo` conforms to `IFoo`.
+        //
+        // It is dangerous to start treating an interface type like it conforms to itself:
+        //
+        //      interface IFoo { static int getValue(); }
+        //      int get< T : IFoo >() { return T.getValue(); }
+        //
+        //      int x = get<IFoo>(); // This needs to be an error!!!
+        //
+        // We will eventually need to clarify the distinction between the different kinds of
+        // subtype-ish relationships, *or* we will need to ensure that `interface`s are not
+        // treated as proper types (such that they can be passed as generic arguments, etc.)
+        //
+        // Note that there is one more case of a subtype-ish relationship that is not covered
+        // by this function, but that is relevant if/when we do more serious type inference:
+        //
+        // * Convertibility: When any value of type `A` can be converted to a value of type
+        //   `B` (even if that conversion might involve computation or a change of representation),
+        //   and that conversion is one that the compiler considers "okay" to do implicitly.
+        //
+        // For now we are continuing to conflate all the subtype-ish relationships but not
+        // tangling convertibility into it.
 
-                    if(_isDeclaredSubtype(originalSubType, inheritedType, superTypeDeclRef, outWitness, &breadcrumb))
-                    {
-                        found = true;
-                    }
-                });
-                if(found)
-                    return true;
+        // TODO: Evaluate whether it is beneficial to memo-cache
+        // the results of subtype tests on the `SharedSemanticsContext`.
 
-                // if an inheritance decl is not found, try to find a GenericTypeConstraintDecl
-                for (auto genConstraintDeclRef : getMembersOfType<GenericTypeConstraintDecl>(m_astBuilder, aggTypeDeclRef))
-                {
-                    ensureDecl(genConstraintDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl);
-                    auto inheritedType = getSup(m_astBuilder, genConstraintDeclRef);
-                    TypeWitnessBreadcrumb breadcrumb;
-                    breadcrumb.prev = inBreadcrumbs;
-                    breadcrumb.sub = subType;
-                    breadcrumb.sup = inheritedType;
-                    breadcrumb.declRef = genConstraintDeclRef;
-                    if (_isDeclaredSubtype(originalSubType, inheritedType, superTypeDeclRef, outWitness, &breadcrumb))
-                    {
-                        return true;
-                    }
-                }
-            }
-            else if( auto genericTypeParamDeclRef = declRef.as<GenericTypeParamDecl>() )
-            {
-                // We need to enumerate the constraints placed on this type by its outer
-                // generic declaration, and see if any of them guarantees that we
-                // satisfy the given interface..
-                auto genericDeclRef = genericTypeParamDeclRef.getParent(m_astBuilder).as<GenericDecl>();
-                SLANG_ASSERT(genericDeclRef);
+        // In the common case, we can use the pre-computed inheritance information for `subType`
+        // to enumerate all the types it transitively inherits from.
+        //
+        auto inheritanceInfo = getShared()->getInheritanceInfo(subType);
+        for (auto facet : inheritanceInfo.facets)
+        {
+            // The `subType` will have a `facet` for each type
+            // that it transitively inherits from, as well as
+            // for each `extension` that was found to apply to it.
+            //
+            // For subtype testing, we are only interested in
+            // the facets that represent supertypes, and those
+            // will be the ones that store a type on the facet.
+            //
+            auto facetType = facet->getType();
+            if (!facetType)
+                continue;
 
-                for( auto constraintDeclRef : getMembersOfType<GenericTypeConstraintDecl>(m_astBuilder, genericDeclRef) )
-                {
-                    ensureDecl(constraintDeclRef, DeclCheckState::CanUseBaseOfInheritanceDecl);
-                    auto sub = getSub(m_astBuilder, constraintDeclRef);
-                    auto sup = getSup(m_astBuilder, constraintDeclRef);
+            // We will scan until we find a facet that corresponds
+            // to `superType`, or fail to find such a facet.
+            //
+            if (!facetType->equals(superType))
+                continue;
 
-                    auto subDeclRef = as<DeclRefType>(sub);
-                    if(!subDeclRef)
-                        continue;
-                    if(subDeclRef->declRef != genericTypeParamDeclRef)
-                        continue;
+            // If the `superType` appears in the flattened inheritance list
+            // for the `subType`, then we know that the subtype relationship
+            // holds. Conveniently, the `facet` stores a pre-computed witness
+            // for the subtype relationship, which we can return here.
+            //
+            return facet->subtypeWitness;
+        }
+        //
+        // TODO: We could expand upon the test using the facet list above
+        // by taking the facet lists of both `subType` and `superType`
+        // and then checking if all of the facets that appear in `superType`'s
+        // linearization also appear in the linearization for `subType`
+        // (and occur in the same order).
+        //
+        // That test could potentially handle certain cases of interface
+        // conjunctions that the simpler algorithm above can't, but it wouldn't
+        // seem to be a complete algorithm unless we ensured that interfaces
+        // have a canonical sorting order for how they appear in linearizations.
+        //
+        // One of the main reasons why we don't implement such a test right now
+        // is that it isn't obvious how to directly produce a witness value
+        // as collateral from the test.
 
-                    // The witness that we create needs to reflect that
-                    // it found the needed conformance by lookup through
-                    // a generic type constraint.
+        // We expect the logic above to cover the vast majority of subtype
+        // tests, but there are a few remaining cases of subtype testing
+        // that cannot be folded into the type linearizations above.
+        //
+        // A few of these cases case if the `superType` is a `DeclRefType`
+        // and, if so, want to compare its `DeclRef` against others. As
+        // such, we will extract the `DeclRef` here, if it exists,
+        // as a convienience.
+        //
+        DeclRef<Decl> superTypeDeclRef;
+        if (auto superDeclRefType = as<DeclRefType>(superType))
+        {
+            superTypeDeclRef = superDeclRefType->declRef;
+        }
 
-                    TypeWitnessBreadcrumb breadcrumb;
-                    breadcrumb.prev = inBreadcrumbs;
-                    breadcrumb.sub = sub;
-                    breadcrumb.sup = sup;
-                    breadcrumb.declRef = constraintDeclRef;
+        if (auto dynamicType = as<DynamicType>(subType))
+        {
+            // A __Dynamic type always conforms to the interface via its witness table.
+            auto witness = m_astBuilder->create<DynamicSubtypeWitness>();
+            return witness;
+        }
+        else if (auto conjunctionSuperType = as<AndType>(superType))
+        {
+            // We know that `T <: L & R` if `T <: L` and `T <: R`.
+            //
+            // We therefore simply recursively test both `T <: L`
+            // and `T <: R`.
+            //
+            auto leftWitness = isSubtype(subType, conjunctionSuperType->left);
+            if (!leftWitness) return nullptr;
+            //
+            auto rightWitness = isSubtype(subType, conjunctionSuperType->right);
+            if (!rightWitness) return nullptr;
 
-                    if(_isDeclaredSubtype(originalSubType, sup, superTypeDeclRef, outWitness, &breadcrumb))
-                    {
-                        return true;
-                    }
-                }
-            }
+            // If both of the sub-relationships hold, we can construct
+            // a conjunction of those witnesses to witness `T <: L&R`
+            //
+            return m_astBuilder->getConjunctionSubtypeWitness(
+                subType,
+                conjunctionSuperType,
+                leftWitness,
+                rightWitness);
         }
         else if (auto extractExistentialType = as<ExtractExistentialType>(subType))
         {
@@ -386,17 +192,21 @@ namespace Slang
             // We need to check and make sure the interface type of the `ExtractExistentialType`
             // is equal to `superType`.
             //
+            // TODO(tfoley): We could add support for `ExtractExistentialType` to
+            // the inheritance linearization logic, and eliminate this case.
+            //
             auto interfaceDeclRef = extractExistentialType->originalInterfaceDeclRef;
             if (interfaceDeclRef.equals(superTypeDeclRef))
             {
-                if (outWitness)
-                {
-                    *outWitness = extractExistentialType->getSubtypeWitness();
-                }
-                return true;
+                auto witness = extractExistentialType->getSubtypeWitness();
+                return witness;
             }
-            return false;
+            return nullptr;
         }
+        //
+        // TODO(tfoley): We should probably just remove `TaggedUnionType`,
+        // since there is no useful code that relies on it any more.
+        //
         else if(auto taggedUnionType = as<TaggedUnionType>(subType))
         {
             // A tagged union type conforms to an interface if all of
@@ -405,29 +215,19 @@ namespace Slang
             // We will iterate over the "case" types in the tagged
             // union, and check if they conform to the interface.
             // Along the way we will collect the conformance witness
-            // values *if* we are being asked to produce a witness
-            // value for the tagged union itself (that is, if
-            // `outWitness` is non-null).
+            // values for the case types.
             //
-            List<Val*> caseWitnesses;
+            List<SubtypeWitness*> caseWitnesses;
             for(auto caseType : taggedUnionType->caseTypes)
             {
-                Val* caseWitness = nullptr;
+                auto caseWitness = isSubtype(caseType, superType);
 
-                if(!_isDeclaredSubtype(
-                    caseType,
-                    caseType,
-                    superTypeDeclRef,
-                    outWitness ? &caseWitness : nullptr,
-                    nullptr))
+                if(!caseWitness)
                 {
-                    return false;
+                    return nullptr;
                 }
 
-                if(outWitness)
-                {
-                    caseWitnesses.add(caseWitness);
-                }
+                caseWitnesses.add(caseWitness);
             }
 
             // We also need to validate the requirements on
@@ -445,74 +245,23 @@ namespace Slang
             if( auto superInterfaceDeclRef = superTypeDeclRef.as<InterfaceDecl>() )
             {
                 if(!isInterfaceSafeForTaggedUnion(superInterfaceDeclRef))
-                    return false;
+                    return nullptr;
             }
 
             // If we reach this point then we have a concrete
             // witness for each of the case types, and that is
             // enough to build a witness for the tagged union.
             //
-            if(outWitness)
-            {
-                TaggedUnionSubtypeWitness* taggedUnionWitness = m_astBuilder->create<TaggedUnionSubtypeWitness>();
-                taggedUnionWitness->sub = taggedUnionType;
-                taggedUnionWitness->sup = DeclRefType::create(m_astBuilder, superTypeDeclRef);
-                taggedUnionWitness->caseWitnesses.swapWith(caseWitnesses);
+            TaggedUnionSubtypeWitness* taggedUnionWitness = m_astBuilder->create<TaggedUnionSubtypeWitness>();
+            taggedUnionWitness->sub = taggedUnionType;
+            taggedUnionWitness->sup = superType;
+            taggedUnionWitness->caseWitnesses.swapWith(caseWitnesses);
 
-                *outWitness = taggedUnionWitness;
-            }
-            return true;
+            return taggedUnionWitness;
         }
-        else if (auto andType = as<AndType>(subType))
-        {
-            // (L & R) is a subtype of T if either L or R is a subtype of T.
-            // Note that in this method T is explicitly a DeclRef and so cannot be a conjunction itself.
-            //
-            TypeWitnessBreadcrumb leftBreadcrumb;
-            leftBreadcrumb.prev = inBreadcrumbs;
-            leftBreadcrumb.sub = andType;
-            leftBreadcrumb.sup = DeclRefType::create(m_astBuilder, superTypeDeclRef);
-            leftBreadcrumb.declRef = DeclRef<Decl>();
-            leftBreadcrumb.flavor = TypeWitnessBreadcrumb::Flavor::AndTypeLeftFlavor;
-
-            if(_isDeclaredSubtype(originalSubType, andType->left, superTypeDeclRef, outWitness, &leftBreadcrumb))
-            {   
-                return true;
-            }
-
-            TypeWitnessBreadcrumb rightBreadcrumb;
-            rightBreadcrumb.prev = inBreadcrumbs;
-            rightBreadcrumb.sub = andType;
-            rightBreadcrumb.sup = DeclRefType::create(m_astBuilder, superTypeDeclRef);
-            rightBreadcrumb.declRef = DeclRef<Decl>();
-            rightBreadcrumb.flavor = TypeWitnessBreadcrumb::Flavor::AndTypeRightFlavor;
 
-            if(_isDeclaredSubtype(originalSubType, andType->right, superTypeDeclRef, outWitness, &rightBreadcrumb))
-            {
-                return true;
-            }
-        }
         // default is failure
-        return false;
-    }
-
-    bool SemanticsVisitor::isDeclaredSubtype(
-        Type*            subType,
-        DeclRef<AggTypeDecl>    superTypeDeclRef)
-    {
-        return _isDeclaredSubtype(subType, subType, superTypeDeclRef, nullptr, nullptr);
-    }
-
-    bool SemanticsVisitor::isDeclaredSubtype(
-        Type* subType,
-        Type* superType)
-    {
-        if (auto declRefType = as<DeclRefType>(superType))
-        {
-            if (auto aggTypeDeclRef = declRefType->declRef.as<AggTypeDecl>())
-                return _isDeclaredSubtype(subType, subType, aggTypeDeclRef, nullptr, nullptr);
-        }
-        return false;
+        return nullptr;
     }
 
     bool SemanticsVisitor::isInterfaceType(Type* type)
@@ -527,77 +276,19 @@ namespace Slang
 
     bool SemanticsVisitor::isTypeDifferentiable(Type* type)
     {
-        return isDeclaredSubtype(type, m_astBuilder->getDiffInterfaceType());
-    }
-
-    Val* SemanticsVisitor::tryGetSubtypeWitness(
-        Type*            subType,
-        DeclRef<AggTypeDecl>    superTypeDeclRef)
-    {
-        Val* result = nullptr;
-        _isDeclaredSubtype(subType, subType, superTypeDeclRef, &result, nullptr);
-        return result;
+        return isSubtype(type, m_astBuilder->getDiffInterfaceType());
     }
 
-    Val* SemanticsVisitor::tryGetInterfaceConformanceWitness(
-        Type*            type,
-        DeclRef<InterfaceDecl>  interfaceDeclRef)
+    SubtypeWitness* SemanticsVisitor::tryGetInterfaceConformanceWitness(
+        Type*   type,
+        Type*   interfaceType)
     {
-        return tryGetSubtypeWitness(type, interfaceDeclRef);
+        return isSubtype(type, interfaceType);
     }
 
-    Val* SemanticsVisitor::createTypeEqualityWitness(
+    TypeEqualityWitness* SemanticsVisitor::createTypeEqualityWitness(
         Type*  type)
     {
-        TypeEqualityWitness* rs = m_astBuilder->create<TypeEqualityWitness>();
-        rs->sub = type;
-        rs->sup = type;
-        return rs;
-    }
-
-    Val* SemanticsVisitor::tryGetSubtypeWitness(
-        Type*    sub,
-        Type*    sup)
-    {
-        if(sub->equals(sup))
-        {
-            // They are the same type, so we just need a witness
-            // for type equality.
-            return createTypeEqualityWitness(sub);
-        }
-
-        if(auto supDeclRefType = as<DeclRefType>(sup))
-        {
-            auto supDeclRef = supDeclRefType->declRef;
-            if(auto supInterfaceDeclRef = supDeclRef.as<InterfaceDecl>())
-            {
-                if(auto witness = tryGetInterfaceConformanceWitness(sub, supInterfaceDeclRef))
-                {
-                    return witness;
-                }
-            }
-        }
-        else if( auto andType = as<AndType>(sup) )
-        {
-            // A type `T` is a subtype of `A & B` if `T` is a
-            // subtype of `A` and `T` is a subtype of `B`.
-            //
-            auto leftWitness = tryGetSubtypeWitness(sub, andType->left);
-            if(!leftWitness) return nullptr;
-
-            auto rightWitness = tryGetSubtypeWitness(sub, andType->right);
-            if(!rightWitness) return nullptr;
-
-            ConjunctionSubtypeWitness* w = m_astBuilder->create<ConjunctionSubtypeWitness>();
-            w->leftWitness = leftWitness;
-            w->rightWitness = rightWitness;
-            w->sub = sub;
-            w->sup = sup;
-            return w;
-        }
-
-        return nullptr;
+        return m_astBuilder->getTypeEqualityWitness(type);
     }
-
-
 }