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>

26 files changed, 2114 insertions, 854 deletions

diff --git a/source/core/slang-hash.h b/source/core/slang-hash.h
index 248d11303..8c4fbac42 100644
--- a/source/core/slang-hash.h
+++ b/source/core/slang-hash.h
@@ -177,6 +177,15 @@ namespace Slang
         return h;
     }
 
+    inline HashCode combineHash(HashCode hash0, HashCode hash1, HashCode hash2, HashCode hash3)
+    {
+        auto h = hash0;
+        h = combineHash(h, hash1);
+        h = combineHash(h, hash2);
+        h = combineHash(h, hash3);
+        return h;
+    }
+
     struct Hasher
     {
     public:
diff --git a/source/core/slang-memory-arena.h b/source/core/slang-memory-arena.h
index 75f3faac3..4d2372e44 100644
--- a/source/core/slang-memory-arena.h
+++ b/source/core/slang-memory-arena.h
@@ -440,4 +440,15 @@ SLANG_FORCE_INLINE void MemoryArena::rewindToCursor(const void* cursor)
 
 } // namespace Slang
 
+SLANG_FORCE_INLINE void* operator new(size_t size, Slang::MemoryArena& arena)
+{
+    return arena.allocate(size);
+}
+
+SLANG_FORCE_INLINE void operator delete(void* memory, Slang::MemoryArena& arena)
+{
+    SLANG_UNUSED(memory);
+    SLANG_UNUSED(arena);
+}
+
 #endif // SLANG_MEMORY_ARENA_H
diff --git a/source/slang/slang-ast-base.h b/source/slang/slang-ast-base.h
index 5319dca7e..f52b7fcff 100644
--- a/source/slang/slang-ast-base.h
+++ b/source/slang/slang-ast-base.h
@@ -415,7 +415,7 @@ private:
     // The underlying declaration
     Decl* decl = nullptr;
     // Optionally, a chain of substitutions to perform
-    Substitutions* substitutions;
+    Substitutions* substitutions = nullptr;
 
 };
 
diff --git a/source/slang/slang-ast-builder.cpp b/source/slang/slang-ast-builder.cpp
index e6e1b5e75..7f1b90837 100644
--- a/source/slang/slang-ast-builder.cpp
+++ b/source/slang/slang-ast-builder.cpp
@@ -338,7 +338,7 @@ DifferentialPairType* ASTBuilder::getDifferentialPairType(
     return as<DifferentialPairType>(rsType);
 }
 
-DeclRef<InterfaceDecl> ASTBuilder::getDifferentiableInterface()
+DeclRef<InterfaceDecl> ASTBuilder::getDifferentiableInterfaceDecl()
 {
     DeclRef<InterfaceDecl> declRef = DeclRef<InterfaceDecl>(getBuiltinDeclRef("DifferentiableType", nullptr));
     return declRef;
@@ -378,6 +378,11 @@ MeshOutputType* ASTBuilder::getMeshOutputTypeFromModifier(
     return as<MeshOutputType>(rsType);
 }
 
+Type* ASTBuilder::getDifferentiableInterfaceType()
+{
+    return DeclRefType::create(this, getDifferentiableInterfaceDecl());
+}
+
 DeclRef<Decl> ASTBuilder::getBuiltinDeclRef(const char* builtinMagicTypeName, Val* genericArg)
 {
     auto decl = m_sharedASTBuilder->findMagicDecl(builtinMagicTypeName);
@@ -443,6 +448,235 @@ TypeType* ASTBuilder::getTypeType(Type* type)
     return getOrCreate<TypeType>(type);
 }
 
+TypeEqualityWitness* ASTBuilder::getTypeEqualityWitness(
+    Type* type)
+{
+    return getOrCreate<TypeEqualityWitness>(type);
+}
+
+
+SubtypeWitness* ASTBuilder::getDeclaredSubtypeWitness(
+    Type*                   subType,
+    Type*                   superType,
+    DeclRef<Decl> const&    declRef)
+{
+    auto witness = getOrCreate<DeclaredSubtypeWitness>(
+        subType, superType, declRef.declRefBase);
+    return witness;
+}
+
+SubtypeWitness* ASTBuilder::getTransitiveSubtypeWitness(
+    SubtypeWitness* aIsSubtypeOfBWitness,
+    SubtypeWitness* bIsSubtypeOfCWitness)
+{
+top:
+    // Our job is to take the witnesses that `a <: b` and `b <: c`
+    // and produce a valid witness that `a <: c`
+    //
+    // There are some special cases we want to handle, in order
+    // to simplify logic elesewhere in the compiler. For example,
+    // if either of the input witnesses is a type *equality* witness,
+    // then the other witness can be returned as-is.
+    //
+    // If `a == b`, then the `b <: c` witness is also a witness of `a <: c`.
+    //
+    if(as<TypeEqualityWitness>(aIsSubtypeOfBWitness))
+    {
+        return bIsSubtypeOfCWitness;
+    }
+
+    // Similarly, if `b == c`, then the `a <: b` witness is a witness for `a <: c`
+    //
+    if (as<TypeEqualityWitness>(bIsSubtypeOfCWitness))
+    {
+        return aIsSubtypeOfBWitness;
+    }
+
+    // HACK: There is downstream code generation logic that assumes that
+    // a `TransitiveSubtypeWitness` will never have a transitive witness
+    // as its `b <: c` witness. If we are at risk of creating such a witness here,
+    // we will shift things around to make that not be the case:
+    //
+    if (auto bIsTransitiveSubtypeOfCWitness = as<TransitiveSubtypeWitness>(bIsSubtypeOfCWitness))
+    {
+        // Let's call the intermediate type here `x`, we know that the `b <: c`
+        // witness is based on witnesses that `b <: x` and `x <: c`:
+        //
+        auto bIsSubtypeOfXWitness = bIsTransitiveSubtypeOfCWitness->subToMid;
+        auto xIsSubtypeOfCWitness = bIsTransitiveSubtypeOfCWitness->midToSup;
+
+        // We can recursively call this operation to produce a witness that
+        // `a <: x`, based on the witnesses we already have for `a <: b` and `b <: x`:
+        //
+        auto aIsSubtypeOfXWitness = getTransitiveSubtypeWitness(
+            aIsSubtypeOfBWitness,
+            bIsSubtypeOfXWitness);
+
+        // Now we can perform a "tail recursive" call to this function (via `goto`
+        // to combine the `a <: x` witness with our `x <: c` witness:
+        //
+        aIsSubtypeOfBWitness = aIsSubtypeOfXWitness;
+        bIsSubtypeOfCWitness = xIsSubtypeOfCWitness;
+        goto top;
+    }
+
+    auto aType = aIsSubtypeOfBWitness->sub;
+    auto cType = bIsSubtypeOfCWitness->sup;
+
+    // If the right-hand side is a conjunction witness for `B <: C`
+    // of the form `(B <: X)&(B <: Y)`, then we have it that `C = X&Y`
+    // and we'd rather form a conjunction witness for `A <: C`
+    // that is of the form `(A <: X)&(A <: Y)`.
+    //
+    if(auto bIsSubtypeOfXAndY = as<ConjunctionSubtypeWitness>(bIsSubtypeOfCWitness))
+    {
+        auto bIsSubtypeOfXWitness = bIsSubtypeOfXAndY->getLeftWitness();
+        auto bIsSubtypeOfYWitness = bIsSubtypeOfXAndY->getRightWitness();
+
+        return getConjunctionSubtypeWitness(
+            aType,
+            cType,
+            getTransitiveSubtypeWitness(aIsSubtypeOfBWitness, bIsSubtypeOfXWitness),
+            getTransitiveSubtypeWitness(aIsSubtypeOfBWitness, bIsSubtypeOfYWitness));
+    }
+
+    // If the right-hand witness `R` is of the form `extract(i, W)`, then
+    // `W` is a witness that `B <: X&Y&...` for some conjunction, where `C`
+    // is one component of that conjunction.
+    //
+    if(auto bIsSubtypeViaExtraction = as<ExtractFromConjunctionSubtypeWitness>(bIsSubtypeOfCWitness))
+    {
+        // We decompose the witness `extract(i, W)` to get both
+        // the witness `W` that `B <: X&Y&...` as well as the index
+        // `i` of `C` within the conjunction.
+        //
+        auto bIsSubtypeOfConjunction = bIsSubtypeViaExtraction->conjunctionWitness;
+        auto indexOfCInConjunction = bIsSubtypeViaExtraction->indexInConjunction;
+
+        // We lift the extraction to the outside of the composition, by
+        // forming a witness for `A <: C` that is of the form
+        // `extract(i, L . W )`, where `L` is the left-hand witnes (for `A <: B`).
+        // The composition `L . W` is a witness that `A <: X&Y&...`, and
+        // the `i`th component of it should be a witness that `A <: C`.
+        //
+        return getExtractFromConjunctionSubtypeWitness(
+            aType,
+            cType,
+            getTransitiveSubtypeWitness(aIsSubtypeOfBWitness, bIsSubtypeOfConjunction),
+            indexOfCInConjunction);
+    }
+
+    // If none of the above special cases applied, then we are just going to create
+    // a `TransitiveSubtypeWitness` directly.
+    //
+    // TODO: Identify other cases that we can potentially simplify.
+    // It is particularly notable that we do not have simplification rules that
+    // detect when the left-hand side of a composition has some particular
+    // structure. This may be fine, or it may not; we should write down a more
+    // formal set of rules for the allowed structure of our witnesses to
+    // guarantee that our simplifications are sufficient.
+
+    TransitiveSubtypeWitness* transitiveWitness = getOrCreateWithDefaultCtor<TransitiveSubtypeWitness>(
+        aType,
+        cType,
+        aIsSubtypeOfBWitness,
+        bIsSubtypeOfCWitness);
+    transitiveWitness->sub = aType;
+    transitiveWitness->sup = cType;
+    transitiveWitness->subToMid = aIsSubtypeOfBWitness;
+    transitiveWitness->midToSup = bIsSubtypeOfCWitness;
+
+    return transitiveWitness;
+}
+
+SubtypeWitness* ASTBuilder::getExtractFromConjunctionSubtypeWitness(
+    Type*           subType,
+    Type*           superType,
+    SubtypeWitness* conjunctionWitness,
+    int             indexOfSuperTypeInConjunction)
+{
+    // We are taking a witness `W` for `S <: L&R` and
+    // using it to produce a witness for `S <: L`
+    // or `S <: R`.
+
+    // If it turns out that the witness `W` is itself
+    // formed as a conjuction of witnesses: `(S <: L) & (S <: R)`,
+    // then we can simply re-use the appropriate sub-witness.
+    //
+    if (auto conjWitness = as<ConjunctionSubtypeWitness>(conjunctionWitness))
+    {
+        return conjWitness->getComponentWitness(indexOfSuperTypeInConjunction);
+    }
+
+    // TODO: Are there other simplification cases we should be paying attention
+    // to here? For example:
+    //
+    // * What if the original witness is transitive?
+
+    auto witness = getOrCreateWithDefaultCtor<ExtractFromConjunctionSubtypeWitness>(
+        subType,
+        superType,
+        conjunctionWitness,
+        indexOfSuperTypeInConjunction);
+
+    witness->sub = subType;
+    witness->sup = superType;
+    witness->conjunctionWitness = conjunctionWitness;
+    witness->indexInConjunction = indexOfSuperTypeInConjunction;
+    return witness;
+}
+
+SubtypeWitness* ASTBuilder::getConjunctionSubtypeWitness(
+    Type*           sub,
+    Type*           lAndR,
+    SubtypeWitness* subIsLWitness,
+    SubtypeWitness* subIsRWitness)
+{
+    // If a conjunction witness for `S <: L&R` is being formed,
+    // where the constituent witnesses for `S <: L` and `S <: R`
+    // are themselves extractions of the first and second
+    // components, respectively, of a single witness `W`, then
+    // we can simply use `W` as-is.
+    //
+    auto lExtract = as<ExtractFromConjunctionSubtypeWitness>(subIsLWitness);
+    auto rExtract = as<ExtractFromConjunctionSubtypeWitness>(subIsRWitness);
+    if(lExtract && rExtract)
+    {
+        if (lExtract->indexInConjunction == 0
+            && rExtract->indexInConjunction == 1)
+        {
+            auto lInner = lExtract->conjunctionWitness;
+            auto rInner = rExtract->conjunctionWitness;
+            if (lInner == rInner)
+            {
+                return lInner;
+            }
+        }
+    }
+
+    // TODO: Depending on how we decide our canonicalized witnesses
+    // should be structured, we could detect the case where the
+    // `S <: L` and `S <: R` witnesses are both transitive compositions
+    // of the form `X . A` and `X . B`, such that we *could* form
+    // a composition around a conjunction - that is, produce
+    // `X . (A & B)` rather than `(X . A) & (X . B)`.
+    //
+    // For now we are favoring putting the composition (transitive
+    // witness) deeper, so that we have more chances to expose a
+    // conjunction witness at higher levels.
+
+    auto witness = getOrCreateWithDefaultCtor<ConjunctionSubtypeWitness>(
+        sub,
+        lAndR,
+        subIsLWitness,
+        subIsRWitness);
+    witness->componentWitnesses[0] = subIsLWitness;
+    witness->componentWitnesses[1] = subIsRWitness;
+    witness->sub = sub;
+    witness->sup = lAndR;
+    return witness;
+}
+
 bool ASTBuilder::NodeDesc::operator==(NodeDesc const& that) const
 {
     if (hashCode != that.hashCode) return false;
diff --git a/source/slang/slang-ast-builder.h b/source/slang/slang-ast-builder.h
index a2543ab1e..9aa3a2f8e 100644
--- a/source/slang/slang-ast-builder.h
+++ b/source/slang/slang-ast-builder.h
@@ -195,6 +195,7 @@ public:
         };
     };
 
+    MemoryArena& getArena() { return m_arena; }
 
         /// Create AST types 
     template <typename T>
@@ -399,7 +400,8 @@ public:
         Type* valueType,
         Witness* primalIsDifferentialWitness);
 
-    DeclRef<InterfaceDecl> getDifferentiableInterface();
+    DeclRef<InterfaceDecl> getDifferentiableInterfaceDecl();
+    Type* getDifferentiableInterfaceType();
     Decl* getDifferentiableAssociatedTypeRequirement();
 
     bool isDifferentiableInterfaceAvailable();
@@ -428,6 +430,34 @@ public:
 
     TypeType* getTypeType(Type* type);
 
+        /// Produce a witness that `T : T` for any type `T`
+    TypeEqualityWitness* getTypeEqualityWitness(
+        Type* type);
+
+    SubtypeWitness* getDeclaredSubtypeWitness(
+        Type*                   subType,
+        Type*                   superType,
+        DeclRef<Decl> const&    declRef);
+
+        /// Produce a witness that `A <: C` given witnesses that `A <: B` and `B <: C`
+    SubtypeWitness* getTransitiveSubtypeWitness(
+        SubtypeWitness*    aIsSubtypeOfBWitness,
+        SubtypeWitness*    bIsSubtypeOfCWitness);
+
+        /// Produce a witness that `T <: L` or `T <: R` given `T <: L&R`
+    SubtypeWitness* getExtractFromConjunctionSubtypeWitness(
+        Type*           subType,
+        Type*           superType,
+        SubtypeWitness* subIsSubtypeOfConjunction,
+        int             indexOfSuperTypeInConjunction);
+
+        /// Produce a witnes that `S <: L&R` given witnesses that `S <: L` and `S <: R`
+    SubtypeWitness* getConjunctionSubtypeWitness(
+        Type*           sub,
+        Type*           lAndR,
+        SubtypeWitness* subIsLWitness,
+        SubtypeWitness* subIsRWitness);
+
         /// Helpers to get type info from the SharedASTBuilder
     const ReflectClassInfo* findClassInfo(const UnownedStringSlice& slice) { return m_sharedASTBuilder->findClassInfo(slice); }
     SyntaxClass<NodeBase> findSyntaxClass(const UnownedStringSlice& slice) { return m_sharedASTBuilder->findSyntaxClass(slice); }
diff --git a/source/slang/slang-ast-decl.h b/source/slang/slang-ast-decl.h
index 93e5a19ad..61e623366 100644
--- a/source/slang/slang-ast-decl.h
+++ b/source/slang/slang-ast-decl.h
@@ -100,14 +100,14 @@ class LetDecl : public VarDecl
     SLANG_AST_CLASS(LetDecl)
 };
 
-// An `AggTypeDeclBase` captures the shared functionality
-// between true aggregate type declarations and extension
-// declarations:
-//
-// - Both can container members (they are `ContainerDecl`s)
-// - Both can have declared bases
-// - Both expose a `this` variable in their body
-//
+    // An `AggTypeDeclBase` captures the shared functionality
+    // between true aggregate type declarations and extension
+    // declarations:
+    //
+    // - Both can contain members (they are `ContainerDecl`s)
+    // - Both can have declared bases
+    // - Both expose a `this` variable in their body
+    //
 class AggTypeDeclBase : public ContainerDecl
 {
     SLANG_ABSTRACT_AST_CLASS(AggTypeDeclBase);
diff --git a/source/slang/slang-ast-support-types.h b/source/slang/slang-ast-support-types.h
index 19f3f42d4..9ae253547 100644
--- a/source/slang/slang-ast-support-types.h
+++ b/source/slang/slang-ast-support-types.h
@@ -753,7 +753,7 @@ namespace Slang
     Val* _tryLookupConcreteAssociatedTypeFromThisTypeSubst(ASTBuilder* builder, DeclRef<Decl> declRef);
     void _printNestedDecl(const Substitutions* substitutions, const Decl* decl, StringBuilder& out);
 
-    template<typename T>
+    template<typename T = Decl>
     struct DeclRef
     {
         friend class ASTBuilder;
@@ -773,12 +773,10 @@ namespace Slang
             init(base);
         }
 
-        template <typename U>
-        DeclRef(DeclRef<U> const& other,
-            typename EnableIf<IsConvertible<T*, U*>::Value, void>::type* = 0)
+        template <typename U, typename = typename EnableIf<IsConvertible<T*, U*>::Value, void>::type>
+        DeclRef(DeclRef<U> const& other)
             : declRefBase(other.declRefBase)
-        {
-        }
+        {}
 
         T* getDecl() const;
         Substitutions* getSubst() const;
diff --git a/source/slang/slang-ast-type.cpp b/source/slang/slang-ast-type.cpp
index b24e0eb8e..9b6b439ce 100644
--- a/source/slang/slang-ast-type.cpp
+++ b/source/slang/slang-ast-type.cpp
@@ -1063,8 +1063,6 @@ HashCode AndType::_getHashCodeOverride()
 
 Type* AndType::_createCanonicalTypeOverride()
 {
-    AndType* canType = m_astBuilder->create<AndType>();
-
     // TODO: proper canonicalization of an `&` type relies on
     // several different things:
     //
@@ -1097,9 +1095,10 @@ Type* AndType::_createCanonicalTypeOverride()
     // We are going to completely ignore these issues for
     // right now, in the name of getting something up and running.
     //
-    canType->left = left->getCanonicalType();
-    canType->right = right->getCanonicalType();
 
+    auto canLeft = left->getCanonicalType();
+    auto canRight = right->getCanonicalType();
+    auto canType = m_astBuilder->getAndType(canLeft, canRight);
     return canType;
 }
 
@@ -1115,9 +1114,7 @@ Val* AndType::_substituteImplOverride(ASTBuilder* astBuilder, SubstitutionSet su
 
     (*ioDiff)++;
 
-    AndType* substType = m_astBuilder->create<AndType>();
-    substType->left = substLeft;
-    substType->right = substRight;
+    auto substType = m_astBuilder->getAndType(substLeft, substRight);
     return substType;
 }
 
diff --git a/source/slang/slang-ast-val.cpp b/source/slang/slang-ast-val.cpp
index 6850fdbfc..37912bac2 100644
--- a/source/slang/slang-ast-val.cpp
+++ b/source/slang/slang-ast-val.cpp
@@ -348,11 +348,8 @@ Val* DeclaredSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, Sub
         }
     }
 
-    DeclaredSubtypeWitness* rs = astBuilder->getOrCreate<DeclaredSubtypeWitness>(
-        substSub, substSup, astBuilder->getSpecializedDeclRef(substDeclRef.getDecl(), substDeclRef.getSubst()));
-    rs->sub = substSub;
-    rs->sup = substSup;
-    rs->declRef = substDeclRef;
+    auto rs = astBuilder->getDeclaredSubtypeWitness(
+        substSub, substSup, substDeclRef);
     return rs;
 }
 
@@ -384,8 +381,6 @@ Val* TransitiveSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, S
 {
     int diff = 0;
 
-    Type* substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff));
-    Type* substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff));
     SubtypeWitness* substSubToMid = as<SubtypeWitness>(subToMid->substituteImpl(astBuilder, subst, &diff));
     SubtypeWitness* substMidToSup = as<SubtypeWitness>(midToSup->substituteImpl(astBuilder, subst, &diff));
 
@@ -396,29 +391,14 @@ Val* TransitiveSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, S
     // Something changes, so let the caller know.
     (*ioDiff)++;
 
-    // TODO: are there cases where we can simplify?
+    // If it possible that substitution could have led to either of the
+    // constituent witnesses being simplified, and such simplification could
+    // (in principle) lead to opportunities to simplify this transitive witness.
+    // As such, we do not simply create a fresh `TransitiveSubtypeWitness` here,
+    // and instead go through a bottleneck routine in the `ASTBuilder` that will
+    // detect and handle any possible simplifications.
     //
-    // In principle, if either `subToMid` or `midToSub` turns into
-    // a reflexive subtype witness, then we could drop that side,
-    // and just return the other one (this would imply that `sub == mid`
-    // or `mid == sup` after substitutions).
-    //
-    // In the long run, is it also possible that if `sub` gets resolved
-    // to a concrete type *and* we decide to flatten out the inheritance
-    // graph into a linearized "class precedence list" stored in any
-    // aggregate type, then we could potentially just redirect to point
-    // to the appropriate inheritance decl in the original type.
-    //
-    // For now I'm going to ignore those possibilities and hope for the best.
-
-    // In the simple case, we just construct a new transitive subtype
-    // witness, and we move on with life.
-    TransitiveSubtypeWitness* result = astBuilder->create<TransitiveSubtypeWitness>();
-    result->sub = substSub;
-    result->sup = substSup;
-    result->subToMid = substSubToMid;
-    result->midToSup = substMidToSup;
-    return result;
+    return astBuilder->getTransitiveSubtypeWitness(substSubToMid, substMidToSup);
 }
 
 void TransitiveSubtypeWitness::_toTextOverride(StringBuilder& out)
@@ -445,9 +425,9 @@ Val* ExtractFromConjunctionSubtypeWitness::_substituteImplOverride(ASTBuilder* a
 {
     int diff = 0;
 
-    Type* substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff));
-    Type* substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff));
-    SubtypeWitness* substWitness = as<SubtypeWitness>(conjunctionWitness->substituteImpl(astBuilder, subst, &diff));
+    auto substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff));
+    auto substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff));
+    auto substWitness = as<SubtypeWitness>(conjunctionWitness->substituteImpl(astBuilder, subst, &diff));
 
     // If nothing changed, then we can bail out early.
     if (!diff)
@@ -456,47 +436,18 @@ Val* ExtractFromConjunctionSubtypeWitness::_substituteImplOverride(ASTBuilder* a
     // Something changes, so let the caller know.
     (*ioDiff)++;
 
-    // If the substituted witness is a conjunction, break it apart, but it's important to replace the
-    // sub and super types with the current ones since the conjunction witness will have an 
-    // 
-    if (auto substConjunctionWitness = as<ConjunctionSubtypeWitness>(substWitness))
-    {
-        if (indexInConjunction == 0)
-        {
-            auto witness = as<SubtypeWitness>(substConjunctionWitness->leftWitness);
-            SLANG_ASSERT(witness);
-
-            witness->sub = substSub;
-            witness->sup = substSup;
-            
-            return witness;
-        }
-        else if (indexInConjunction == 1)
-        {
-            auto witness = as<SubtypeWitness>(substConjunctionWitness->rightWitness);
-            SLANG_ASSERT(witness);
-            
-            witness->sub = substSub;
-            witness->sup = substSup;
-
-            return witness;
-        }
-        else
-        {
-            SLANG_UNIMPLEMENTED_X("conjunction index must be 0 or 1");
-        }
-    }
-    else
-    {
-        // In the simple case, we just construct a new conjunction subtype
-        // witness.
-        ExtractFromConjunctionSubtypeWitness* result = astBuilder->create<ExtractFromConjunctionSubtypeWitness>();
-        result->sub = substSub;
-        result->sup = substSup;
-        result->conjunctionWitness = substWitness;
-        result->indexInConjunction = indexInConjunction;
-        return result;
-    }
+    // Substitution into the constituent pieces of this witness could
+    // have created opportunities for simplification. For example,
+    // the `substWitness` might be a `ConjunctionSubtypeWitness`,
+    // such that we could directly use one of its components in
+    // place of the extraction.
+    //
+    // We use the factory function on the AST builder to create
+    // the result witness, so that it can perform all of the
+    // simplification logic as needed.
+    //
+    return astBuilder->getExtractFromConjunctionSubtypeWitness(
+        substSub, substSup, substWitness, indexInConjunction);
 }
 
 // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ExtractExistentialSubtypeWitness !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
@@ -595,10 +546,11 @@ Val* TaggedUnionSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder,
     auto substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff));
     auto substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff));
 
-    List<Val*> substCaseWitnesses;
+    List<SubtypeWitness*> substCaseWitnesses;
     for (auto caseWitness : caseWitnesses)
     {
-        substCaseWitnesses.add(caseWitness->substituteImpl(astBuilder, subst, &diff));
+        substCaseWitnesses.add(
+            as<SubtypeWitness>(caseWitness->substituteImpl(astBuilder, subst, &diff)));
     }
 
     if (!diff)
@@ -615,65 +567,83 @@ Val* TaggedUnionSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder,
 
 bool ConjunctionSubtypeWitness::_equalsValOverride(Val* val)
 {
-    if (auto other = as<ConjunctionSubtypeWitness>(val))
+    auto other = as<ConjunctionSubtypeWitness>(val);
+    if (!other)
+        return false;
+
+    for (Index i = 0; i < kComponentCount; ++i)
     {
-        return other->leftWitness && other->leftWitness->equalsVal(leftWitness) &&
-               other->rightWitness && other->rightWitness->equalsVal(rightWitness);
+        if (!other->componentWitnesses[i]) return false;
+        if (!other->componentWitnesses[i]->equalsVal(componentWitnesses[i])) return false;
     }
-    return false;
+    return true;
 }
 
 void ConjunctionSubtypeWitness::_toTextOverride(StringBuilder& out)
 {
     out << "ConjunctionSubtypeWitness(";
-    if (leftWitness) out << leftWitness;
-    out << ",";
-    if (rightWitness) out << rightWitness;
+    for (Index i = 0; i < kComponentCount; ++i)
+    {
+        if (i != 0) out << ",";
+
+        auto w = componentWitnesses[i];
+        if (w) out << w;
+    }
     out << ")";
 }
 
 HashCode ConjunctionSubtypeWitness::_getHashCodeOverride()
 {
     HashCode result = 0;
-    if (leftWitness) result = leftWitness->getHashCode();
-    if (rightWitness) result = combineHash(result, rightWitness->getHashCode());
+    for (Index i = 0; i < kComponentCount; ++i)
+    {
+        auto w = componentWitnesses[i];
+        if (w) result = combineHash(result, w->getHashCode());
+    }
     return result;
 }
 
 Val* ConjunctionSubtypeWitness::_substituteImplOverride(ASTBuilder* astBuilder, SubstitutionSet subst, int* ioDiff)
 {
     int diff = 0;
-    Val* left = nullptr;
-    Val* right = nullptr;
+    Val* substComponentWitnesses[kComponentCount];
 
     auto substSub = as<Type>(sub->substituteImpl(astBuilder, subst, &diff));
     auto substSup = as<Type>(sup->substituteImpl(astBuilder, subst, &diff));
 
-    if (leftWitness)
-        left = leftWitness->substituteImpl(astBuilder, subst, &diff);
-    if (rightWitness)
-        right = rightWitness->substituteImpl(astBuilder, subst, &diff);
+    for (Index i = 0; i < kComponentCount; ++i)
+    {
+        auto w = componentWitnesses[i];
+        substComponentWitnesses[i] = w ? w->substituteImpl(astBuilder, subst, &diff) : nullptr;
+    }
+
+    if(!diff)
+        return this;
 
     *ioDiff += diff;
 
-    if (diff)
-    {
-        auto result = astBuilder->create<ConjunctionSubtypeWitness>();
-        result->leftWitness = left;
-        result->rightWitness = right;
-        result->sub = substSub;
-        result->sup = substSup;
-        return result;
-    }
-    return this;
+    // We use the factory function on the AST builder rather than
+    // directly construct a new `ConjunctionSubtypeWitness`, because
+    // the substitution process might have created further opportunities
+    // for simplification.
+    //
+    auto result = astBuilder->getConjunctionSubtypeWitness(
+        substSub,
+        substSup,
+        componentWitnesses[0],
+        componentWitnesses[1]);
+    return result;
 }
 
 bool ExtractFromConjunctionSubtypeWitness::_equalsValOverride(Val* val)
 {
     if (auto other = as<ExtractFromConjunctionSubtypeWitness>(val))
     {
-        return other->conjunctionWitness && other->conjunctionWitness->equalsVal(conjunctionWitness) &&
-            other->indexInConjunction == indexInConjunction;
+        if(!sub->equals(other->sub)) return false;
+        if(!sup->equals(other->sup)) return false;
+        if(indexInConjunction != other->indexInConjunction) return false;
+
+        return true;
     }
     return false;
 }
@@ -683,13 +653,22 @@ void ExtractFromConjunctionSubtypeWitness::_toTextOverride(StringBuilder& out)
     out << "ExtractFromConjunctionSubtypeWitness(";
     if (conjunctionWitness)
         out << conjunctionWitness;
+    if (sub)
+        out << sub;
+    out << ",";
+    if (sup)
+        out << sup;
     out << "," << indexInConjunction;
     out << ")";
 }
 
 HashCode ExtractFromConjunctionSubtypeWitness::_getHashCodeOverride()
 {
-    return combineHash(indexInConjunction, conjunctionWitness ? conjunctionWitness->getHashCode() : 0);
+    return combineHash(
+        conjunctionWitness ? conjunctionWitness->getHashCode() : 0,
+        sub ? sub->getHashCode() : 0,
+        sup ? sup->getHashCode() : 0,
+        indexInConjunction);
 }
 
 // ModifierVal
diff --git a/source/slang/slang-ast-val.h b/source/slang/slang-ast-val.h
index 75979cb15..1731a5799 100644
--- a/source/slang/slang-ast-val.h
+++ b/source/slang/slang-ast-val.h
@@ -309,6 +309,13 @@ class TypeEqualityWitness : public SubtypeWitness
 {
     SLANG_AST_CLASS(TypeEqualityWitness)
 
+    TypeEqualityWitness(
+        Type* type)
+    {
+        this->sub = type;
+        this->sup = type;
+    }
+
     // Overrides should be public so base classes can access
     bool _equalsValOverride(Val* val);
     void _toTextOverride(StringBuilder& out);
@@ -360,7 +367,7 @@ class TransitiveSubtypeWitness : public SubtypeWitness
     {}
 };
 
-// A witness taht `sub : sup` because `sub` was wrapped into
+// A witness that `sub : sup` because `sub` was wrapped into
 // an existential of type `sup`.
 class ExtractExistentialSubtypeWitness : public SubtypeWitness 
 {
@@ -387,7 +394,7 @@ class TaggedUnionSubtypeWitness : public SubtypeWitness
     // Witnesses that each of the "case" types in the union
     // is a subtype of `sup`.
     //
-    List<Val*> caseWitnesses;
+    List<SubtypeWitness*> caseWitnesses;
 
     // Overrides should be public so base classes can access
     bool _equalsValOverride(Val* val);
@@ -414,11 +421,23 @@ class ConjunctionSubtypeWitness : public SubtypeWitness
 {
     SLANG_AST_CLASS(ConjunctionSubtypeWitness)
 
-        /// Witness that `sub : sup->left`
-    Val* leftWitness;
+    // At the operational level, this class of witness is
+    // an operation that takes two witness tables `leftWitness`
+    // and `rightWitness`, and forms a pair/tuple of
+    // `(leftWitness, rightWitness)`.
+
+    static const Count kComponentCount = 2;
+    SubtypeWitness* componentWitnesses[kComponentCount];
 
-        /// Witness that `sub : sup->right`
-    Val* rightWitness;
+    SubtypeWitness* getLeftWitness() const { return componentWitnesses[0]; }
+    SubtypeWitness* getRightWitness() const { return componentWitnesses[1]; }
+
+    Count getComponentCount() const { return kComponentCount; }
+    SubtypeWitness* getComponentWitness(Index index) const
+    {
+        SLANG_ASSERT(index >= 0 && index < kComponentCount);
+        return componentWitnesses[index];
+    }
 
     bool _equalsValOverride(Val* val);
     void _toTextOverride(StringBuilder& out);
@@ -426,18 +445,23 @@ class ConjunctionSubtypeWitness : public SubtypeWitness
     Val* _substituteImplOverride(ASTBuilder* astBuilder, SubstitutionSet subst, int* ioDiff);
 };
 
-    /// A witness that `T : X` because `T : X & Y` or `T : Y & X`
+    /// A witness that `T <: L` or `T <: R` because `T <: L&R`
 class ExtractFromConjunctionSubtypeWitness : public SubtypeWitness
 {
     SLANG_AST_CLASS(ExtractFromConjunctionSubtypeWitness)
 
-        /// Witness that `T : L & R` for some `R`
-    Val* conjunctionWitness;
+    // At the operational level, this class of witness is
+    // an operation that takes a pair/tuple of witness tables
+    // `(leftWtiness, rightWitness)` and extracts one of the
+    // elements of it.
+
+        /// Witness that `T < L & R`
+    SubtypeWitness* conjunctionWitness;
 
         /// The zero-based index of the super-type we care about in the conjunction
         ///
-        /// If `conjunctionWitness` is `T : X & Y` then this index should be zero if
-        /// we want to represent `T : X` and one if we want `T : Y`.
+        /// If `conjunctionWitness` is `T < L & R` then this index should be zero if
+        /// we want to represent `T < L` and one if we want `T < R`.
         ///
     int indexInConjunction;
 
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);
     }
-
-
 }
diff --git a/source/slang/slang-check-constraint.cpp b/source/slang/slang-check-constraint.cpp
index c38c9e7f2..2dc263115 100644
--- a/source/slang/slang-check-constraint.cpp
+++ b/source/slang/slang-check-constraint.cpp
@@ -75,12 +75,12 @@ namespace Slang
             vectorType->elementCount);
     }
 
-    Type* SemanticsVisitor::TryJoinTypeWithInterface(
-        Type*            type,
-        DeclRef<InterfaceDecl>      interfaceDeclRef)
+    Type* SemanticsVisitor::_tryJoinTypeWithInterface(
+        Type*                   type,
+        Type*                   interfaceType)
     {
         // The most basic test here should be: does the type declare conformance to the trait.
-        if(isDeclaredSubtype(type, interfaceDeclRef))
+        if(isSubtype(type, interfaceType))
             return type;
 
         // Just because `type` doesn't conform to the given `interfaceDeclRef`, that
@@ -119,7 +119,7 @@ namespace Slang
                     continue;
 
                 // We only want to consider types that implement the target interface.
-                if(!isDeclaredSubtype(candidateType, interfaceDeclRef))
+                if(!isSubtype(candidateType, interfaceType))
                     continue;
 
                 // We only want to consider types where we can implicitly convert from `type`
@@ -245,7 +245,7 @@ namespace Slang
             if( auto leftInterfaceRef = leftDeclRefType->declRef.as<InterfaceDecl>() )
             {
                 //
-                return TryJoinTypeWithInterface(right, leftInterfaceRef);
+                return _tryJoinTypeWithInterface(right, left);
             }
         }
         if(auto rightDeclRefType = as<DeclRefType>(right))
@@ -253,7 +253,7 @@ namespace Slang
             if( auto rightInterfaceRef = rightDeclRefType->declRef.as<InterfaceDecl>() )
             {
                 //
-                return TryJoinTypeWithInterface(left, rightInterfaceRef);
+                return _tryJoinTypeWithInterface(left, right);
             }
         }
 
@@ -480,7 +480,7 @@ namespace Slang
             }
 
             // Search for a witness that shows the constraint is satisfied.
-            auto subTypeWitness = tryGetSubtypeWitness(sub, sup);
+            auto subTypeWitness = isSubtype(sub, sup);
             if(subTypeWitness)
             {
                 // We found a witness, so it will become an (implicit) argument.
diff --git a/source/slang/slang-check-conversion.cpp b/source/slang/slang-check-conversion.cpp
index 357b75cce..abe9f4817 100644
--- a/source/slang/slang-check-conversion.cpp
+++ b/source/slang/slang-check-conversion.cpp
@@ -891,43 +891,39 @@ namespace Slang
             }
             return true;
         }
-        // If we are casting to an interface type, then that will succeed
-        // if the "from" type conforms to the interface.
+
+        // A type is always convertible to any of its supertypes.
         //
-        if (auto toDeclRefType = as<DeclRefType>(toType))
+        if(auto witness = tryGetSubtypeWitness(fromType, toType))
         {
-            auto toTypeDeclRef = toDeclRefType->declRef;
-            if (auto toAggTypeDeclRef = toTypeDeclRef.as<AggTypeDecl>())
+            if (outToExpr)
             {
-                if(auto witness = tryGetSubtypeWitness(fromType, toAggTypeDeclRef))
+                *outToExpr = createCastToSuperTypeExpr(toType, fromExpr, witness);
+
+                // If the original expression was an l-value, then the result
+                // of the cast may be an l-value itself. We want to be able
+                // to invoke `[mutating]` methods on a value that is cast to
+                // an interface it conforms to, and we also expect to be able
+                // to pass a value of a derived `struct` type into methods that
+                // expect a value of its base type.
+                //
+                // TODO: vet this logic for correctness.
+                //
+                if (fromExpr && fromExpr->type.isLeftValue)
                 {
-                    if (outToExpr)
-                    {
-                        *outToExpr = createCastToSuperTypeExpr(toType, fromExpr, witness);
-
-                        // If the original expression was an l-value, then the result
-                        // of the cast may be an l-value itself. We want to be able
-                        // to invoke `[mutating]` methods on a value that is cast to
-                        // an interface it conforms to, and we also expect to be able
-                        // to pass a value of a derived `struct` type into methods that
-                        // expect a value of its base type.
-                        //
-                        // TODO: vet this logic for correctness.
-                        //
-                        if (fromExpr && fromExpr->type.isLeftValue)
-                        {
-                            (*outToExpr)->type.isLeftValue = true;
-                        }
-                    }
-                    if (outCost)
-                        *outCost = kConversionCost_CastToInterface;
-                    return true;
+                    (*outToExpr)->type.isLeftValue = true;
                 }
             }
+            if (outCost)
+                *outCost = kConversionCost_CastToInterface;
+            return true;
         }
 
         // Disallow converting to a ParameterGroupType.
-        if (const auto toParameterGroupType = as<ParameterGroupType>(toType))
+        //
+        // TODO(tfoley): Under what circumstances would this check ever be needed?
+        //
+        if (auto toParameterGroupType = as<ParameterGroupType>(toType))
         {
             return _failedCoercion(toType, outToExpr, fromExpr);
         }
diff --git a/source/slang/slang-check-decl.cpp b/source/slang/slang-check-decl.cpp
index 06616b38c..5279ca068 100644
--- a/source/slang/slang-check-decl.cpp
+++ b/source/slang/slang-check-decl.cpp
@@ -587,11 +587,6 @@ namespace Slang
         return semantics->ApplyExtensionToType(extDecl, type);
     }
 
-    void ensureDecl(SemanticsVisitor* visitor, Decl* decl, DeclCheckState state)
-    {
-        visitor->ensureDecl(decl, state);
-    }
-
     GenericSubstitution* createDefaultSubstitutionsForGeneric(
         ASTBuilder*             astBuilder,
         SemanticsVisitor* semantics,
@@ -636,8 +631,8 @@ namespace Slang
                     ensureDecl(semantics, genericTypeConstraintDecl, DeclCheckState::ReadyForReference);
                 }
                 auto constraintDeclRef = astBuilder->getSpecializedDeclRef<GenericTypeConstraintDecl>(genericTypeConstraintDecl, outerSubst);
-                DeclaredSubtypeWitness* witness =
-                    astBuilder->getOrCreate<DeclaredSubtypeWitness>(
+                auto witness =
+                    astBuilder->getDeclaredSubtypeWitness(
                         getSub(astBuilder, constraintDeclRef),
                         getSup(astBuilder, constraintDeclRef),
                         astBuilder->getSpecializedDeclRef(genericTypeConstraintDecl, outerSubst));
@@ -1530,7 +1525,7 @@ namespace Slang
         {
             if (auto declRefType = as<DeclRefType>(inheritanceDecl->base.type))
             {
-                if (declRefType->declRef == m_astBuilder->getDifferentiableInterface())
+                if (declRefType->declRef == m_astBuilder->getDifferentiableInterfaceDecl())
                 {
                     hasDifferentialConformance = true;
                     break;
@@ -1732,7 +1727,7 @@ namespace Slang
             auto baseType = as<DeclRefType>(inheritanceDecl->witnessTable->baseType);
             if (!baseType)
                 return;
-            if (baseType->declRef.getDecl() != m_astBuilder->getDifferentiableInterface().getDecl())
+            if (baseType->declRef.getDecl() != m_astBuilder->getDifferentiableInterfaceDecl().getDecl())
                 return;
             RequirementWitness witnessValue;
             auto requirementDecl = m_astBuilder->getSharedASTBuilder()->findBuiltinRequirementDecl(BuiltinRequirementKind::DifferentialType);
@@ -2287,10 +2282,10 @@ namespace Slang
                 auto satisfyingConstraintDeclRef = satisfyingMemberDeclRef.as<GenericTypeConstraintDecl>();
                 SLANG_ASSERT(satisfyingConstraintDeclRef);
 
-                auto satisfyingWitness = m_astBuilder->getOrCreate<DeclaredSubtypeWitness>();
-                satisfyingWitness->sub = getSub(m_astBuilder, satisfyingConstraintDeclRef);
-                satisfyingWitness->sup = getSup(m_astBuilder, satisfyingConstraintDeclRef);
-                satisfyingWitness->declRef = satisfyingConstraintDeclRef;
+                auto satisfyingWitness = m_astBuilder->getDeclaredSubtypeWitness(
+                    getSub(m_astBuilder, satisfyingConstraintDeclRef),
+                    getSup(m_astBuilder, satisfyingConstraintDeclRef),
+                    satisfyingConstraintDeclRef);
 
                 requiredSubstArgs.add(satisfyingWitness);
             }
@@ -3533,18 +3528,16 @@ namespace Slang
 
             auto reqType = getBaseType(m_astBuilder, requiredInheritanceDeclRef);
 
-            DeclaredSubtypeWitness* interfaceIsReqWitness =
-                m_astBuilder->getOrCreate<DeclaredSubtypeWitness>(
+            auto interfaceIsReqWitness =
+                m_astBuilder->getDeclaredSubtypeWitness(
                     superInterfaceType,
                     reqType,
                     requiredInheritanceDeclRef);
             // ...
 
-            TransitiveSubtypeWitness* subIsReqWitness = m_astBuilder->getOrCreateWithDefaultCtor<TransitiveSubtypeWitness>(subType, reqType, interfaceIsReqWitness);
-            subIsReqWitness->sub = subType;
-            subIsReqWitness->sup = reqType;
-            subIsReqWitness->subToMid = subTypeConformsToSuperInterfaceWitness;
-            subIsReqWitness->midToSup = interfaceIsReqWitness;
+            auto subIsReqWitness = m_astBuilder->getTransitiveSubtypeWitness(
+                subTypeConformsToSuperInterfaceWitness,
+                interfaceIsReqWitness);
             // ...
 
             RefPtr<WitnessTable> satisfyingWitnessTable = new WitnessTable();
@@ -6763,7 +6756,6 @@ namespace Slang
         }
     }
 
-
     static void _dispatchDeclCheckingVisitor(Decl* decl, DeclCheckState state, SemanticsContext const& shared)
     {
         switch(state)
diff --git a/source/slang/slang-check-expr.cpp b/source/slang/slang-check-expr.cpp
index 9af8fd867..24f130add 100644
--- a/source/slang/slang-check-expr.cpp
+++ b/source/slang/slang-check-expr.cpp
@@ -935,7 +935,7 @@ namespace Slang
                     return type;
                 }
             }
-            if (const auto witness = as<SubtypeWitness>(tryGetInterfaceConformanceWitness(type, builder->getDifferentiableInterface())))
+            if (const auto witness = as<SubtypeWitness>(tryGetInterfaceConformanceWitness(type, builder->getDifferentiableInterfaceType())))
             {
                 auto diffTypeLookupResult = lookUpMember(
                     getASTBuilder(),
@@ -1044,7 +1044,7 @@ namespace Slang
         if (auto declRefType = as<DeclRefType>(type))
         {
             if (auto subtypeWitness = as<SubtypeWitness>(
-                tryGetInterfaceConformanceWitness(type, getASTBuilder()->getDifferentiableInterface())))
+                tryGetInterfaceConformanceWitness(type, getASTBuilder()->getDifferentiableInterfaceType())))
             {
                 addDifferentiableTypeToDiffTypeRegistry((DeclRefType*)type, subtypeWitness);
             }
@@ -2359,9 +2359,9 @@ namespace Slang
         }
 
         // Get a reference to the builtin 'IDifferentiable' interface
-        auto differentiableInterface = m_astBuilder->getDifferentiableInterface();
-        
-        SubtypeWitness* conformanceWitness = as<SubtypeWitness>(tryGetInterfaceConformanceWitness(primalType, differentiableInterface));
+        auto differentiableInterface = getASTBuilder()->getDifferentiableInterfaceType();
+
+        auto conformanceWitness = as<Witness>(isSubtype(primalType, differentiableInterface));
         // Check if the provided type inherits from IDifferentiable.
         // If not, return the original type.
         if (conformanceWitness)
@@ -2960,7 +2960,7 @@ namespace Slang
         expr->value = originalVal;
 
         // If value is a subtype of `type`, then this expr is always true.
-        if (isDeclaredSubtype(expr->value->type.type, expr->typeExpr.type))
+        if(isSubtype(expr->value->type.type, expr->typeExpr.type))
         {
             // Instead of returning a BoolLiteralExpr, we use a field to indicate this scenario,
             // so that the language server can still see the original syntax tree.
diff --git a/source/slang/slang-check-impl.h b/source/slang/slang-check-impl.h
index 0a99fcb97..709245c28 100644
--- a/source/slang/slang-check-impl.h
+++ b/source/slang/slang-check-impl.h
@@ -264,6 +264,274 @@ namespace Slang
         Initializer,
     };
 
+    struct FacetImpl;
+
+        /// Information about one "facet" of a type or declaration
+        ///
+        /// In the simplest terms, a facet represents a grouping of
+        /// member declarations that were all originally declared
+        /// as part of the same `{}`-enclosed body.
+        ///
+        /// A given *entity* (a type, type declaration, or `extension`
+        /// declaration) may have multiple facets, depending on what it
+        /// declares, what it inherits from, or what `extension`s apply to it.
+        ///
+        /// Broadly, an entity will have:
+        ///
+        /// * A *self facet*, if it has a body, that contains the members
+        ///   the entity directly declares.
+        ///
+        /// * An *inherited facet* for each base type that it (transitively)
+        ///   inherits from. Inherited facets are either *direct*, if the
+        ///   original entity stated the inheritance relationship, or
+        ///   *indirect* if they arise from the transitive closure of the
+        ///   inheritance relationship. Each inherited facet contains the
+        ///   members of the entity that was inherited from.
+        ///
+        /// * An *extension facet* for each `extension` declaration that
+        ///   is known to apply to the entity in the context where semantic
+        ///   checking is being performed. Each extension facet contains the
+        ///   members of the `extension` that applied.
+        ///
+    struct Facet
+    {
+    public:
+            /// Kinds of facets that can occur
+        enum class Kind
+        {
+            Type,
+            Extension,
+        };
+
+            /// How many indirections away from the self facet?
+        typedef unsigned int DirectnessVal;
+        enum class Directness : DirectnessVal
+        {
+            Self = 0,
+            Direct = 1,
+        };
+
+            /// The *origin* of a facet is the type and/or declaration
+            /// that the facet's members belong to.
+            ///
+        struct Origin
+        {
+            /// A `DeclRef` to the declaration this facet corresponds to, if any.
+            ///
+            /// This might be a type declaration, an `extension` declaration,
+            /// or nothing.
+            ///
+            DeclRef<Decl> declRef;
+
+            /// The type that this facet corresponds to, if any
+            Type* type = nullptr;
+
+            Origin()
+            {}
+
+            explicit Origin(DeclRef<Decl> declRef, Type* type = nullptr)
+                : declRef(declRef)
+                , type(type)
+            {}
+        };
+
+        Facet()
+        {}
+
+        typedef FacetImpl Impl;
+
+        Facet(Impl* impl)
+            : _impl(impl)
+        {}
+
+        Impl* getImpl() const { return _impl; }
+        Impl* operator->() const { return _impl; }
+
+    private:
+        Impl* _impl = nullptr;
+    };
+
+
+        /// Do the origins of `left` and `right` match,
+        /// such that they are both facets for the same
+        /// base type or `extension`?
+        ///
+    bool originsMatch(Facet left, Facet right);
+
+    inline bool operator!(Facet facet) { return !facet.getImpl(); }
+
+    bool operator==(Facet::Origin left, Facet::Origin right);
+
+    inline bool operator!=(Facet::Origin left, Facet::Origin right)
+    {
+        return !(left == right);
+    }
+
+        /// Heap-allocated implementation of a single facet.
+    struct FacetImpl
+    {
+            /// The kind of this facet
+        Facet::Kind kind = Facet::Kind::Type;
+
+            /// How many indirections away from the self facet?
+        Facet::Directness directness = Facet::Directness::Self;
+
+            /// The origin of this facet.
+            ///
+            /// This is the type or declaration that the facet
+            /// corresponds to.
+            ///
+        Facet::Origin origin;
+
+        Type* getType() const { return origin.type; }
+        DeclRef<Decl> getDeclRef() const { return origin.declRef; }
+
+            /// A witness that the type this facet belongs to
+            /// is a subtype of `origin.type` (if both of those
+            /// types exist).
+            ///
+        SubtypeWitness* subtypeWitness = nullptr;
+
+            /// The next facet in the linearized inheritance list of the entity.
+        Facet next;
+
+        FacetImpl()
+        {}
+
+        FacetImpl(
+            Facet::Kind         kind,
+            Facet::Directness   directness,
+            DeclRef<Decl>       declRef,
+            Type*               type,
+            SubtypeWitness*     subtypeWitness)
+            : kind(kind)
+            , directness(directness)
+            , origin(declRef, type)
+            , subtypeWitness(subtypeWitness)
+        {}
+    };
+
+    struct FacetListBuilder;
+
+        /// A singly linked list of facets.
+    struct FacetList
+    {
+    public:
+        FacetList()
+        {}
+
+        explicit FacetList(Facet head)
+            : _head(head)
+        {}
+
+        Facet getHead() const { return _head; }
+        Facet& getHead() { return _head; }
+
+        Facet advanceHead()
+        {
+            SLANG_ASSERT(_head.getImpl());
+            auto facet = _head;
+            _head = facet->next;
+            return facet;
+        }
+
+        Facet popHead()
+        {
+            auto facet = advanceHead();
+            facet->next = nullptr;
+            return facet;
+        }
+
+        FacetList getTail() const
+        {
+            SLANG_ASSERT(_head.getImpl());
+            return FacetList(_head->next);
+        }
+
+        bool containsMatchFor(Facet facet) const;
+
+        bool isEmpty() const { return _head.getImpl() == nullptr; }
+
+        struct Iterator
+        {
+        public:
+            Iterator()
+            {}
+
+            Iterator(Facet::Impl* cursor)
+                : _cursor(cursor)
+            {}
+
+            bool operator!=(Iterator const& that) const
+            {
+                return this->_cursor != that._cursor;
+            }
+
+            void operator++()
+            {
+                SLANG_ASSERT(_cursor);
+                _cursor = _cursor->next.getImpl();
+            }
+
+            Facet operator*() const
+            {
+                return _cursor;
+            }
+
+        private:
+            Facet::Impl* _cursor = nullptr;
+        };
+
+        Iterator begin() const { return Iterator(_head.getImpl()); }
+        Iterator end() const { return Iterator(); }
+
+        struct Appender
+        {
+        public:
+            Appender(FacetList& list)
+            {
+                _link = &list._head;
+            }
+
+            void add(Facet facet)
+            {
+                *_link = facet;
+                _link = &facet->next;
+            }
+
+        protected:
+            Appender()
+            {}
+
+            Facet* _link = nullptr;
+        };
+
+        typedef FacetListBuilder Builder;
+
+    protected:
+
+        Facet _head;
+    };
+
+    struct FacetListBuilder : FacetList, FacetList::Appender
+    {
+    public:
+        FacetListBuilder()
+        {
+            _link = &_head;
+        }
+    };
+
+        /// Information about the inheritance of an entity (type or declaration)
+        ///
+        /// Currently this is only used to store a linearized list of the
+        /// `Facet`s that the type/declaration transitively inherits.
+        ///
+    struct InheritanceInfo
+    {
+        FacetList facets;
+    };
+
         /// Shared state for a semantics-checking session.
     struct SharedSemanticsContext
     {
@@ -338,7 +606,13 @@ namespace Slang
         bool isBackwardDifferentiableFunc(FunctionDeclBase* func);
         FunctionDifferentiableLevel _getFuncDifferentiableLevelImpl(FunctionDeclBase* func, int recurseLimit);
         FunctionDifferentiableLevel getFuncDifferentiableLevel(FunctionDeclBase* func);
-        
+
+            /// Get the processed inheritance information for `type`, including all its facets
+        InheritanceInfo getInheritanceInfo(Type* type);
+
+            /// Get the processed inheritance information for `extension`, including all its facets
+        InheritanceInfo getInheritanceInfo(DeclRef<ExtensionDecl> const& extension);
+
     private:
             /// Mapping from type declarations to the known extensiosn that apply to them
         Dictionary<AggTypeDecl*, RefPtr<CandidateExtensionList>> m_mapTypeDeclToCandidateExtensions;
@@ -359,6 +633,96 @@ namespace Slang
             /// Add associated decls declared in `moduleDecl` to `m_mapDeclToAssociatedDecls`
         void _addDeclAssociationsFromModule(ModuleDecl* moduleDecl);
 
+        ASTBuilder* _getASTBuilder() { return m_linkage->getASTBuilder(); }
+
+        InheritanceInfo _getInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* correspondingType);
+        InheritanceInfo _calcInheritanceInfo(Type* type);
+        InheritanceInfo _calcInheritanceInfo(DeclRef<Decl> declRef, DeclRefType* correspondingType);
+
+        struct DirectBaseInfo
+        {
+            FacetList facets;
+
+            Facet::Impl facetImpl;
+
+            DirectBaseInfo* next = nullptr;
+        };
+
+        struct DirectBaseListBuilder;
+
+        struct DirectBaseList
+        {
+        public:
+            struct Iterator
+            {
+            public:
+                Iterator()
+                {}
+
+                Iterator(DirectBaseInfo* cursor)
+                    : _cursor(cursor)
+                {}
+
+                bool operator!=(Iterator that) const
+                {
+                    return _cursor != that._cursor;
+                }
+
+                void operator++()
+                {
+                    SLANG_ASSERT(_cursor);
+                    _cursor = _cursor->next;
+                }
+
+                DirectBaseInfo* operator*()
+                {
+                    return _cursor;
+                }
+
+            private:
+                DirectBaseInfo* _cursor = nullptr;
+            };
+
+            Iterator begin() const { return Iterator(_head); }
+            Iterator end() const { return Iterator(); }
+
+            bool isEmpty() const
+            {
+                return _head == nullptr;
+            }
+
+            bool doesAnyTailContainMatchFor(Facet facet) const;
+
+            void removeEmptyLists();
+
+            typedef DirectBaseListBuilder Builder;
+
+        public:
+            DirectBaseInfo* _head = nullptr;
+        };
+
+        struct DirectBaseListBuilder : DirectBaseList
+        {
+        public:
+            DirectBaseListBuilder()
+            {
+                _link = &_head;
+            }
+
+            void add(DirectBaseInfo* base)
+            {
+                *_link = base;
+                _link = &base->next;
+            }
+
+        private:
+            DirectBaseInfo** _link = nullptr;
+        };
+
+        void _mergeFacetLists(DirectBaseList bases, FacetList baseFacets, FacetList::Builder& ioMergedFacets);
+
+        Dictionary<Type*, InheritanceInfo> m_mapTypeToInheritanceInfo;
+        Dictionary<DeclRef<Decl>, InheritanceInfo> m_mapDeclRefToInheritanceInfo;
     };
 
         /// Local/scoped state of the semantic-checking system
@@ -1399,48 +1763,6 @@ namespace Slang
             VectorExpressionType* vectorType,
             BasicExpressionType*  scalarType);
 
-        struct TypeWitnessBreadcrumb
-        {
-            TypeWitnessBreadcrumb*  prev;
-
-            Type*            sub = nullptr;
-            Type*            sup = nullptr;
-            DeclRef<Decl>           declRef;
-
-            enum Flavor 
-            {
-                // Describes a sub-type super-type relationship through a 
-                // reference to an inhertiance declaration.
-                DeclFlavor,
-
-                // Describes a sub-type super-type relationship through 
-                // conjunction. This doesn't necessarily have a corresponding declaration
-                // since AndTypes cannot actually be used as types.
-                // i.e. if (A & B) subtype C because A subtype C, then we use AndTypeLeft to represent
-                // that relationship.
-                AndTypeLeftFlavor,
-                AndTypeRightFlavor
-            };
-
-            Flavor flavor = DeclFlavor;
-        };
-
-            // Create a subtype witness based on the declared relationship
-            // found in a single breadcrumb
-        DeclaredSubtypeWitness* createSimpleSubtypeWitness(
-            TypeWitnessBreadcrumb*  breadcrumb);
-
-            /// Create a witness that `subType` is a sub-type of `superTypeDeclRef`.
-            ///
-            /// The `inBreadcrumbs` parameter represents a linked list of steps
-            /// in the process that validated the sub-type relationship, which
-            /// will be used to inform the construction of the witness.
-            ///
-        Val* createTypeWitness(
-            Type*            subType,
-            DeclRef<AggTypeDecl>  superTypeDeclRef,
-            TypeWitnessBreadcrumb*  inBreadcrumbs);
-    
             /// Is the given interface one that a tagged-union type can conform to?
             ///
             /// If a tagged union type `__TaggedUnion(A,B)` is going to be
@@ -1462,35 +1784,16 @@ namespace Slang
             DeclRef<InterfaceDecl>  interfaceDeclRef,
             DeclRef<Decl>           requirementDeclRef);
 
-            /// Check whether `subType` is declared a sub-type of `superTypeDeclRef`
-            ///
-            /// If this function returns `true` (because the subtype relationship holds),
-            /// then `outWitness` will be set to a value that serves as a witness
-            /// to the subtype relationship.
-            ///
-            /// This function may be used to validate a transitive subtype relationship
-            /// where, e.g., `A : C` becase `A : B` and `B : C`. In such a case, a recursive
-            /// call to `_isDeclaredSubtype` may occur where `originalSubType` is `A`,
-            /// `subType` is `C`, and `superTypeDeclRef` is `C`. The `inBreadcrumbs` in that
-            /// case would include information for the `A : B` relationship, which can be
-            /// used to construct a witness for `A : C` from the `A : B` and `B : C` witnesses.
-            ///
-        bool _isDeclaredSubtype(
-            Type*            originalSubType,
-            Type*            subType,
-            DeclRef<AggTypeDecl>    superTypeDeclRef,
-            Val**            outWitness,
-            TypeWitnessBreadcrumb*  inBreadcrumbs);
-
-            /// Check whether `subType` is a sub-type of `superTypeDeclRef`.
-        bool isDeclaredSubtype(
-            Type*            subType,
-            DeclRef<AggTypeDecl>    superTypeDeclRef);
-
-        /// Check whether `subType` is a sub-type of `supType`.
-        bool isDeclaredSubtype(
-            Type* subType,
-            Type* supType);
+            /// Check whether `subType` is a subtype of `superType`
+            ///
+            /// If `subType` is a subtype of `superType`, returns
+            /// a witness value for the subtype relationship.
+            ///
+            /// If `subType` is *not* a subtype of `superType`, returns null.
+            ///
+        SubtypeWitness* isSubtype(
+            Type*                   subType,
+            Type*                   superType);
 
         bool isInterfaceType(Type* type);
 
@@ -1500,9 +1803,12 @@ namespace Slang
             /// and return a witness to the sub-type relationship if it holds
             /// (return null otherwise).
             ///
-        Val* tryGetSubtypeWitness(
-            Type*            subType,
-            DeclRef<AggTypeDecl>    superTypeDeclRef);
+        SubtypeWitness* tryGetSubtypeWitness(
+            Type* subType,
+            Type* superType)
+        {
+            return isSubtype(subType, superType);
+        }
 
             /// Check whether `type` conforms to `interfaceDeclRef`,
             /// and return a witness to the conformance if it holds
@@ -1510,9 +1816,9 @@ namespace Slang
             ///
             /// This function is equivalent to `tryGetSubtypeWitness()`.
             ///
-        Val* tryGetInterfaceConformanceWitness(
-            Type*            type,
-            DeclRef<InterfaceDecl>  interfaceDeclRef);
+        SubtypeWitness* tryGetInterfaceConformanceWitness(
+            Type* type,
+            Type* interfaceType);
 
         Expr* createCastToSuperTypeExpr(
             Type*    toType,
@@ -1528,9 +1834,9 @@ namespace Slang
             Type* toType,
             Type* fromType);
 
-        Type* TryJoinTypeWithInterface(
-            Type*            type,
-            DeclRef<InterfaceDecl>      interfaceDeclRef);
+        Type* _tryJoinTypeWithInterface(
+            Type*                   type,
+            Type*                   interfaceType);
 
         // Try to compute the "join" between two types
         Type* TryJoinTypes(
@@ -1649,15 +1955,9 @@ namespace Slang
 
         // Create a witness that attests to the fact that `type`
         // is equal to itself.
-        Val* createTypeEqualityWitness(
+        TypeEqualityWitness* createTypeEqualityWitness(
             Type*  type);
 
-        // If `sub` is a subtype of `sup`, then return a value that
-        // can serve as a "witness" for that fact.
-        Val* tryGetSubtypeWitness(
-            Type*    sub,
-            Type*    sup);
-
         // In the case where we are explicitly applying a generic
         // to arguments (e.g., `G<A,B>`) check that the constraints
         // on those parameters are satisfied.
@@ -1924,6 +2224,18 @@ namespace Slang
             CompletionSuggestions::ScopeKind scopeKind, LookupResult const& lookupResult);
     };
 
+
+    inline void ensureDecl(SemanticsVisitor* visitor, Decl* decl, DeclCheckState state)
+    {
+        visitor->ensureDecl(decl, state);
+    }
+
+    DeclRef<ExtensionDecl> ApplyExtensionToType(
+        SemanticsVisitor*   semantics,
+        ExtensionDecl*      extDecl,
+        Type*               type);
+
+
     struct SemanticsExprVisitor
         : public SemanticsVisitor
         , ExprVisitor<SemanticsExprVisitor, Expr*>
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;
+        }
+    }
+}
diff --git a/source/slang/slang-check-overload.cpp b/source/slang/slang-check-overload.cpp
index 423d1f6bb..38856d7bf 100644
--- a/source/slang/slang-check-overload.cpp
+++ b/source/slang/slang-check-overload.cpp
@@ -537,6 +537,7 @@ namespace Slang
             {
                 if(context.mode != OverloadResolveContext::Mode::JustTrying)
                 {
+                    subTypeWitness = tryGetSubtypeWitness(sub, sup);
                     getSink()->diagnose(context.loc, Diagnostics::typeArgumentDoesNotConformToInterface, sub, sup);
                 }
                 return false;
diff --git a/source/slang/slang-check-shader.cpp b/source/slang/slang-check-shader.cpp
index 69e419f75..382abf081 100644
--- a/source/slang/slang-check-shader.cpp
+++ b/source/slang/slang-check-shader.cpp
@@ -1062,8 +1062,8 @@ namespace Slang
                         auto interfaceType = getSup(getLinkage()->getASTBuilder(), DeclRef<GenericTypeConstraintDecl>(constraintDecl));
 
                         // Use our semantic-checking logic to search for a witness to the required conformance
-                        auto witness = visitor.tryGetSubtypeWitness(argType, interfaceType);
-                        if (!witness)
+                        auto witness = visitor.isSubtype(argType, interfaceType);
+                        if(!witness)
                         {
                             // If no witness was found, then we will be unable to satisfy
                             // the conformances required.
@@ -1094,7 +1094,7 @@ namespace Slang
                         argType = getLinkage()->getASTBuilder()->getErrorType();
                     }
 
-                    auto witness = visitor.tryGetSubtypeWitness(argType, interfaceType);
+                    auto witness = visitor.isSubtype(argType, interfaceType);
                     if (!witness)
                     {
                             // If no witness was found, then we will be unable to satisfy
@@ -1220,7 +1220,7 @@ namespace Slang
                 auto sub = getSub(astBuilder, constraintDeclRef);
                 auto sup = getSup(astBuilder, constraintDeclRef);
 
-                auto subTypeWitness = visitor.tryGetSubtypeWitness(sub, sup);
+                auto subTypeWitness = visitor.isSubtype(sub, sup);
                 if(subTypeWitness)
                 {
                     genericArgs.add(subTypeWitness);
@@ -1264,7 +1264,7 @@ namespace Slang
             auto paramType = as<Type>(param.object);
             auto argType = as<Type>(specializationArg.val);
 
-            auto witness = visitor.tryGetSubtypeWitness(argType, paramType);
+            auto witness = visitor.isSubtype(argType, paramType);
             if (!witness)
             {
                 // If no witness was found, then we will be unable to satisfy
@@ -1414,7 +1414,7 @@ namespace Slang
 
             ExpandedSpecializationArg arg;
             arg.val = argType;
-            arg.witness = visitor.tryGetSubtypeWitness(argType, paramType);
+            arg.witness = visitor.isSubtype(argType, paramType);
             specializationArgs.add(arg);
         }
 
diff --git a/source/slang/slang-compiler.cpp b/source/slang/slang-compiler.cpp
index c1d7798e3..224e30fa1 100644
--- a/source/slang/slang-compiler.cpp
+++ b/source/slang/slang-compiler.cpp
@@ -281,12 +281,12 @@ namespace Slang
         }
         else if (auto conjunctionWitness = as<ConjunctionSubtypeWitness>(witness))
         {
-            auto left = as<SubtypeWitness>(conjunctionWitness->leftWitness);
-            if (left)
-                addDepedencyFromWitness(left);
-            auto right = as<SubtypeWitness>(conjunctionWitness->rightWitness);
-            if (right)
-                addDepedencyFromWitness(right);
+            auto componentCount = conjunctionWitness->getComponentCount();
+            for (Index i = 0; i < componentCount; ++i)
+            {
+                auto w = as<SubtypeWitness>(conjunctionWitness->getComponentWitness(i));
+                if (w) addDepedencyFromWitness(w);
+            }
         }
     }
 
diff --git a/source/slang/slang-ir-liveness.h b/source/slang/slang-ir-liveness.h
index db3c7633f..54ac20e0d 100644
--- a/source/slang/slang-ir-liveness.h
+++ b/source/slang/slang-ir-liveness.h
@@ -186,4 +186,4 @@ struct LivenessUtil
 
 }
 
-#endif // SLANG_IR_LIVENESS_H
\ No newline at end of file
+#endif // SLANG_IR_LIVENESS_H
diff --git a/source/slang/slang-lookup.cpp b/source/slang/slang-lookup.cpp
index b16671efb..efc413e24 100644
--- a/source/slang/slang-lookup.cpp
+++ b/source/slang/slang-lookup.cpp
@@ -4,6 +4,12 @@
 #include "../compiler-core/slang-name.h"
 #include "slang-check-impl.h"
 
+// TODO(tfoley): The implementation of lookup still involves
+// recursion over the structure of a type/declaration, but
+// it should be possible for it to use the flattened/linearized
+// inheritance information that is being computed in
+// `slang-check-inheritance.cpp`.
+
 namespace Slang {
 
 void ensureDecl(SemanticsVisitor* visitor, Decl* decl, DeclCheckState state);
@@ -278,13 +284,14 @@ static SubtypeWitness* _makeSubtypeWitness(
     Type*                       superType,
     SubtypeWitness*             midtoSuperWitness)
 {
+    SLANG_UNUSED(subType);
+    SLANG_UNUSED(superType);
+
     if(subToMidWitness)
     {
-        TransitiveSubtypeWitness* transitiveWitness = astBuilder->create<TransitiveSubtypeWitness>();
-        transitiveWitness->subToMid = subToMidWitness;
-        transitiveWitness->midToSup = midtoSuperWitness;
-        transitiveWitness->sub = subType;
-        transitiveWitness->sup = superType;
+        auto transitiveWitness = astBuilder->getTransitiveSubtypeWitness(
+            subToMidWitness,
+            midtoSuperWitness);
         return transitiveWitness;
     }
     else
@@ -300,11 +307,10 @@ static SubtypeWitness* _makeSubtypeWitness(
     Type*                       superType,
     DeclRef<TypeConstraintDecl> midToSuperConstraint)
 {
-    DeclaredSubtypeWitness* midToSuperWitness = astBuilder->create<DeclaredSubtypeWitness>();
-    midToSuperWitness->declRef = midToSuperConstraint;
-    midToSuperWitness->sub = subType;
-    midToSuperWitness->sup = superType;
-    return _makeSubtypeWitness(astBuilder, subType, subToMidWitness, superType, midToSuperWitness);
+    auto midToSuperWitness = astBuilder->getDeclaredSubtypeWitness(
+        subType, superType, midToSuperConstraint);
+    return _makeSubtypeWitness(
+        astBuilder, subType, subToMidWitness, superType, midToSuperWitness);
 }
 
 // Same as the above, but we are specializing a type instead of a decl-ref
@@ -380,14 +386,6 @@ static void _lookUpMembersInSuperType(
     breadcrumb.val = leafIsSuperWitness;
     breadcrumb.prev = inBreadcrumbs;
 
-    // TODO: Need to consider case where this might recurse infinitely (e.g.,
-    // if an inheritance clause does something like `Bad<T> : Bad<Bad<T>>`.
-    //
-    // TODO: The even simpler thing we need to worry about here is that if
-    // there is ever a "diamond" relationship in the inheritance hierarchy,
-    // we might end up seeing the same interface via different "paths" and
-    // we wouldn't want that to lead to overload-resolution failure.
-    //
     _lookUpMembersInSuperTypeImpl(astBuilder, name, leafType, superType, leafIsSuperWitness, request, ioResult, &breadcrumb);
 }
 
@@ -663,36 +661,24 @@ static void _lookUpMembersInSuperTypeImpl(
         //
         // Effectively, we have a witness that `T : X & Y` and we
         // need to extract from it a witness that `T : X`.
-        // Fortunately, we have a class of subtype witness that does
-        // *precisely* this:
-        //
-        auto leafIsLeftWitness = astBuilder->create<ExtractFromConjunctionSubtypeWitness>();
-        //
-        // Our witness will be to the fact that `leafType` is a subtype of `leftType`
-        //
-        leafIsLeftWitness->sub = leafType;
-        leafIsLeftWitness->sup = leftType;
         //
-        // The evidence for the subtype relationship will be a witness
-        // proving that `leafType : leftType & rightType`:
         //
-        leafIsLeftWitness->conjunctionWitness = leafIsSuperWitness;
-        //
-        // ... along with the index of the desired super-type in
-        // that conjunction. The index of `leftType` in `leftType & rightType`
-        // is zero.
-        //
-        leafIsLeftWitness->indexInConjunction = 0;
+        auto leafIsLeftWitness = astBuilder->getExtractFromConjunctionSubtypeWitness(
+            leafType,
+            leftType,
+            leafIsSuperWitness,
+            0);
+
 
         // The witness for the fact that `leafType : rightType` is the
         // same as for the left case, just with a different index into
         // the conjunction.
         //
-        auto leafIsRightWitness = astBuilder->create<ExtractFromConjunctionSubtypeWitness>();
-        leafIsRightWitness->conjunctionWitness = leafIsSuperWitness;
-        leafIsRightWitness->indexInConjunction = 1;
-        leafIsRightWitness->sub = leafType;
-        leafIsRightWitness->sup = rightType;
+        auto leafIsRightWitness = astBuilder->getExtractFromConjunctionSubtypeWitness(
+            leafType,
+            rightType,
+            leafIsSuperWitness,
+            1);
 
         // We then perform lookup on both sides of the conjunction, and
         // accumulate whatever items are found on either/both sides.
diff --git a/source/slang/slang-lower-to-ir.cpp b/source/slang/slang-lower-to-ir.cpp
index 7439c67f4..b941212ea 100644
--- a/source/slang/slang-lower-to-ir.cpp
+++ b/source/slang/slang-lower-to-ir.cpp
@@ -1862,15 +1862,21 @@ struct ValLoweringVisitor : ValVisitor<ValLoweringVisitor, LoweredValInfo, Lower
 
     LoweredValInfo visitConjunctionSubtypeWitness(ConjunctionSubtypeWitness* val)
     {
-        // A witness `T : L & R` for a conformance of `T` to a conjunction of
-        // types `L` and `R` will be lowered as a tuple of two witnesses: one
-        // for `T : L` and one for `T : R`. Luckily, those two conformances
-        // are exactly what the `ConjunctionSubtypeWitness` stores, so we just
-        // need to lower them individually and make a tuple.
-        //
-        auto left   = lowerSimpleVal(context, val->leftWitness);
-        auto right  = lowerSimpleVal(context, val->rightWitness);
-        return LoweredValInfo::simple(getBuilder()->emitMakeTuple(left, right));
+        // A witness `W = X & Y & ...` will lower as a tuple of the sub-witnesses
+        // `X`, `Y`, etc.
+        //
+        // The AST representation of a conjunction of witnesses matches this
+        // tuple-like encoding very closely, so we can simply lower each of
+        // the component witnesses to produce our result.
+        //
+        List<IRInst*> componentWitnesses;
+        auto componentCount = val->getComponentCount();
+        for (Index i = 0; i < componentCount; ++i)
+        {
+            auto componentWitness = lowerSimpleVal(context, val->getComponentWitness(i));
+            componentWitnesses.add(componentWitness);
+        }
+        return LoweredValInfo::simple(getBuilder()->emitMakeTuple(componentWitnesses));
     }
 
     LoweredValInfo visitExtractFromConjunctionSubtypeWitness(ExtractFromConjunctionSubtypeWitness* val)
diff --git a/source/slang/slang-syntax.cpp b/source/slang/slang-syntax.cpp
index fbb30e4eb..4033dfff1 100644
--- a/source/slang/slang-syntax.cpp
+++ b/source/slang/slang-syntax.cpp
@@ -366,10 +366,11 @@ Index getFilterCountImpl(const ReflectClassInfo& clsInfo, MemberFilterStyle filt
         {
             if (auto conjunctionTypeWitness = as<ConjunctionSubtypeWitness>(extractFromConjunctionTypeWitness->conjunctionWitness))
             {
-                if (extractFromConjunctionTypeWitness->indexInConjunction == 0)
-                    return tryLookUpRequirementWitness(astBuilder, as<SubtypeWitness>(conjunctionTypeWitness->leftWitness), requirementKey);
-                else
-                    return tryLookUpRequirementWitness(astBuilder, as<SubtypeWitness>(conjunctionTypeWitness->rightWitness), requirementKey);
+                auto componentWitness = as<SubtypeWitness>(
+                    conjunctionTypeWitness->getComponentWitness(
+                        extractFromConjunctionTypeWitness->indexInConjunction));
+
+                return tryLookUpRequirementWitness(astBuilder, componentWitness, requirementKey);
             }
         }
         // TODO: should handle the transitive case here too
diff --git a/source/slang/slang.cpp b/source/slang/slang.cpp
index 246662909..28227b39b 100644
--- a/source/slang/slang.cpp
+++ b/source/slang/slang.cpp
@@ -1320,7 +1320,7 @@ SLANG_NO_THROW SlangResult SLANG_MCALL Linkage::createTypeConformanceComponentTy
         SharedSemanticsContext sharedSemanticsContext(this, nullptr, &sink);
         SemanticsVisitor visitor(&sharedSemanticsContext);
         auto witness =
-            visitor.tryGetSubtypeWitness((Slang::Type*)type, (Slang::Type*)interfaceType);
+            visitor.isSubtype((Slang::Type*)type, (Slang::Type*)interfaceType);
         if (auto subtypeWitness = as<SubtypeWitness>(witness))
         {
             result = new TypeConformance(this, subtypeWitness, conformanceIdOverride, &sink);
diff --git a/source/slang/slang.natvis b/source/slang/slang.natvis
index 59f2007ce..1db7b9bce 100644
--- a/source/slang/slang.natvis
+++ b/source/slang/slang.natvis
@@ -10,9 +10,10 @@
     </Expand>
   </Type>
   <Type Name="Slang::DeclRef&lt;*&gt;">
-    <SmartPointer Usage="Minimal">decl ? ($T1*)(decl) : ($T1*)0</SmartPointer>
-    <DisplayString Condition="decl == 0">DeclRef nullptr</DisplayString>
-    <DisplayString Condition="decl != 0">{(*(*(Slang::DeclRefBase*)this).decl).nameAndLoc}</DisplayString>
+    <SmartPointer Usage="Minimal">declRefBase ? ($T1*)(declRefBase->decl) : ($T1*)0</SmartPointer>
+    <DisplayString Condition="declRefBase == 0">DeclRef nullptr</DisplayString>
+    <DisplayString Condition="declRefBase != 0">{*declRefBase}</DisplayString>
+    <!--
     <Expand>
       <ExpandedItem>decl ? ($T1*)(decl) : ($T1*)0</ExpandedItem>
       <Synthetic Name="[Substitutions]">
@@ -25,23 +26,27 @@
         </Expand>
       </Synthetic>
     </Expand>
+    -->
   </Type>
     <Type Name="Slang::DeclRefBase">
-        <SmartPointer Usage="Minimal">decl</SmartPointer>
-        <DisplayString Condition="decl == 0">DeclRefBase nullptr</DisplayString>
-        <DisplayString Condition="decl != 0">{(*(*(Slang::DeclRefBase*)this).decl).nameAndLoc}</DisplayString>
-        <Expand>
-            <ExpandedItem>decl</ExpandedItem>
-            <Synthetic Name="[Substitutions]">
-                <Expand>
-                    <LinkedListItems>
-                        <HeadPointer>substitutions.substitutions</HeadPointer>
-                        <NextPointer>outer</NextPointer>
-                        <ValueNode>this</ValueNode>
-                    </LinkedListItems>
-                </Expand>
-            </Synthetic>
-        </Expand>
+      <SmartPointer Usage="Minimal">decl</SmartPointer>
+      <DisplayString Condition="decl != 0 &amp;&amp; substitutions != 0">{*decl}{*substitutions}</DisplayString>
+      <DisplayString Condition="decl != 0">{*decl}</DisplayString>
+      <DisplayString Condition="decl == 0">DeclRefBase nullptr</DisplayString>
+      <!--
+      <Expand>
+          <ExpandedItem>decl</ExpandedItem>
+          <Synthetic Name="[Substitutions]">
+              <Expand>
+                  <LinkedListItems>
+                      <HeadPointer>substitutions.substitutions</HeadPointer>
+                      <NextPointer>outer</NextPointer>
+                      <ValueNode>this</ValueNode>
+                  </LinkedListItems>
+              </Expand>
+          </Synthetic>
+      </Expand>
+      -->
     </Type>
     <Type Name="Slang::GenericSubstitution">
         <DisplayString>GenSubst {(*genericDecl).nameAndLoc}</DisplayString>
@@ -191,7 +196,7 @@
   </Type>
 
     <Type Name="Slang::Expr" Inheritable="false">
-        <DisplayString>{astNodeType}</DisplayString>
+        <DisplayString>{astNodeType,en}</DisplayString>
         <Expand>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::DeclRefExpr">(Slang::DeclRefExpr*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::VarExpr">(Slang::VarExpr*)&amp;astNodeType</ExpandedItem>
@@ -246,7 +251,7 @@
         </Expand>
     </Type>
     <Type Name="Slang::Stmt" Inheritable="false">
-        <DisplayString>{astNodeType}</DisplayString>
+        <DisplayString>{astNodeType,en}</DisplayString>
         <Expand>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ScopeStmt">(Slang::ScopeStmt*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::BlockStmt">(Slang::BlockStmt*)&amp;astNodeType</ExpandedItem>
@@ -281,8 +286,8 @@
         <DisplayString>{text}</DisplayString>
     </Type>
     <Type Name="Slang::Decl" Inheritable="false">
-        <DisplayString Condition="nameAndLoc.name!=0">{nameAndLoc.name->text}: {astNodeType}</DisplayString>
-        <DisplayString Condition="nameAndLoc.name==0">{astNodeType}</DisplayString>
+        <DisplayString Condition="nameAndLoc.name!=0">{nameAndLoc.name->text}</DisplayString>
+        <DisplayString Condition="nameAndLoc.name==0">{astNodeType,en}</DisplayString>
         <Expand>
             <Item Name="[Name]" Condition="nameAndLoc.name!=0">nameAndLoc.name->text</Item>
             <Item Name="[Parent]">parentDecl</Item>
@@ -332,7 +337,7 @@
     </Type>
 
     <Type Name="Slang::DeclBase" Inheritable="false">
-        <DisplayString>{astNodeType}</DisplayString>
+        <DisplayString>{astNodeType,en}</DisplayString>
         <Expand>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ContainerDecl">(Slang::ContainerDecl*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ExtensionDecl">(Slang::ExtensionDecl*)&amp;astNodeType</ExpandedItem>
@@ -379,8 +384,9 @@
     </Type>
 
     <Type Name="Slang::Type" Inheritable="false">
-        <DisplayString>{astNodeType}</DisplayString>
-        <Expand>
+      <DisplayString Condition="astNodeType == Slang::ASTNodeType::DeclRefType">{((Slang::DeclRefType*)&amp;astNodeType)->declRef}</DisplayString>
+      <DisplayString>{astNodeType,en}</DisplayString>
+      <Expand>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::OverloadGroupType">(Slang::OverloadGroupType*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::InitializerListType">(Slang::InitializerListType*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ErrorType">(Slang::ErrorType*)&amp;astNodeType</ExpandedItem>
@@ -420,7 +426,7 @@
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::HLSLPointStreamType">(Slang::HLSLPointStreamType*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::HLSLLineStreamType">(Slang::HLSLLineStreamType*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::HLSLTriangleStreamType">(Slang::HLSLTriangleStreamType*)&amp;astNodeType</ExpandedItem>
-            <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::MeshOutputType">(Slang::HLSLMeshOutputType*)&amp;astNodeType</ExpandedItem>
+            <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::MeshOutputType">(Slang::MeshOutputType*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::VerticesType">(Slang::VerticesType*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::IndicesType">(Slang::IndicesType*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::PrimitivesType">(Slang::PrimitivesType*)&amp;astNodeType</ExpandedItem>
@@ -462,16 +468,26 @@
             <Item Name="[Type]">(Slang::Type*)this,nd</Item>
         </Expand>
     </Type>
-
     <Type Name="Slang::Substitutions" Inheritable="false">
-        <DisplayString>{astNodeType}</DisplayString>
+      <DisplayString Condition="astNodeType == Slang::ASTNodeType::GenericSubstitution">{*(Slang::GenericSubstitution*)&amp;astNodeType}</DisplayString>
+      <DisplayString Condition="astNodeType == Slang::ASTNodeType::ThisTypeSubstitution">{*(Slang::ThisTypeSubstitution*)&amp;astNodeType}</DisplayString>
+      <DisplayString>{astNodeType,en}</DisplayString>
+      <DisplayString>{astNodeType,en}</DisplayString>
         <Expand>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::GenericSubstitution">(Slang::GenericSubstitution*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ThisTypeSubstitution">(Slang::ThisTypeSubstitution*)&amp;astNodeType</ExpandedItem>
         </Expand>
     </Type>
+    <Type Name="Slang::GenericSubstitution" Inheritable="false">
+      <DisplayString Condition="outer != 0">&lt;{args}&gt;{*outer}</DisplayString>
+      <DisplayString>&lt;{args}&gt;</DisplayString>
+    </Type>
+    <Type Name="Slang::ThisTypeSubstitution" Inheritable="false">
+      <DisplayString Condition="outer != 0">{*outer}[This=={witness->sub,na}]</DisplayString>
+      <DisplayString>[{witness->sup,na}.This: {witness->sub,na}]</DisplayString>
+    </Type>
     <Type Name="Slang::SubstitutionSet">
-        <DisplayString>{astNodeType}</DisplayString>
+        <DisplayString>{astNodeType,en}</DisplayString>
         <Expand>
             <LinkedListItems>
                 <HeadPointer>substitutions</HeadPointer>
@@ -481,13 +497,13 @@
         </Expand>
     </Type>
     <Type Name="Slang::AggTypeDecl">
-        <DisplayString>{nameAndLoc.name}: {astNodeType}</DisplayString>
+        <DisplayString>{astNodeType}({nameAndLoc.name})</DisplayString>
         <Expand>
             <Item Name="[Members]">members</Item>
         </Expand>
     </Type>
     <Type Name="Slang::Val" Inheritable="false">
-        <DisplayString>{astNodeType}</DisplayString>
+        <DisplayString>{astNodeType,en}</DisplayString>
         <Expand>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ConstantIntVal">(Slang::ConstantIntVal*)&amp;astNodeType</ExpandedItem>
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::PolynomialIntVal">(Slang::PolynomialIntVal*)&amp;astNodeType</ExpandedItem>
@@ -569,4 +585,36 @@
             <ExpandedItem Condition="astNodeType == Slang::ASTNodeType::ModifiedType">(Slang::ModifiedType*)&amp;astNodeType</ExpandedItem>
         </Expand>
     </Type>
+    <Type Name="Slang::Facet">
+        <SmartPointer Usage="Minimal">_impl</SmartPointer>
+        <DisplayString Condition="_impl == 0">nullptr</DisplayString>
+        <DisplayString Condition="_impl != 0">{_impl}</DisplayString>
+    </Type>
+    <Type Name="Slang::FacetList">
+        <DisplayString Condition="_head == 0">empty</DisplayString>
+        <Expand>
+            <LinkedListItems>
+                <HeadPointer>_head._impl != 0 ? &amp;_head : 0</HeadPointer>
+                <NextPointer>_impl->next._impl != 0 ? &amp;_impl->next : 0</NextPointer>
+                <ValueNode>*this</ValueNode>
+            </LinkedListItems>
+        </Expand>
+    </Type>
+  <Type Name="Slang::SharedSemanticsContext::DirectBaseList">
+    <DisplayString Condition="_head == 0">empty</DisplayString>
+    <Expand>
+      <LinkedListItems>
+        <HeadPointer>_head != 0 ? _head : 0</HeadPointer>
+        <NextPointer>next != 0 ? next : 0</NextPointer>
+        <ValueNode>*this</ValueNode>
+      </LinkedListItems>
+    </Expand>
+  </Type>
+  <Type Name="Slang::SubtypeWitness">
+    <DisplayString Condition="astNodeType == Slang::ASTNodeType::TypeEqualityWitness">{*(Slang::TypeEqualityWitness*)this}</DisplayString>
+    <DisplayString>{sub,na} &lt;: {sup,na}</DisplayString>
+  </Type>
+  <Type Name="Slang::TypeEqualityWitness">
+    <DisplayString>{sub,na} == {sup,na}</DisplayString>
+  </Type>
 </AutoVisualizer>