Create and cache flattened inheritance lists (#2740)

* Create and cache flattened inheritance lists

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

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

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

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

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

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

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

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

Notes and caveats:

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

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

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

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

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

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

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

* Fix clang error.

* remove debugging code.

---------

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

1 files changed, 82 insertions, 103 deletions

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