Fix an infinite-recursion bug in type-checking (#2004)

Fixes #1990

The underlying problem here is in the `ExtractExistentialType` AST node class.

An "existential" in current Slang is typically a value of interface type. When such a value is used in an operation, the type-checker "opens" the extistential so that subsequent type-checking steps can work with the (statically unknown) specific type of the value stored inside. The `ExtractExistentialType` AST node represents the type of an existential that has been "opened" in this way.

When the front-end performs lookup "into" a value with one of these types, it nees to use a reference to the original interface declaration with a "this-type substitution" that refers to the "opened" type (a this-type substitution tells the compiler the concrete type it should use in place of `This` in signatures within the interface; it allows compiler to "see" the right associated type definitions to use in a context).

Prior to this change, the implementation would store the specialized reference to the original interface declaration in the `ExtractExistentialType` node as part of its state. The catch there is that the specialized interface reference indirectly refers to the `ExtractExistentialType` AST node itself, creating a circularity. As soon as the front-end performs any operation that tries to recurse over that structure, it would go into an infinite loop.

The fix here sounds kind of like a hack, but seems to be pretty nice in practice. Instead of always storing the specialized interface reference, we instead store the few values that are needed to construct it, and then create and cache the actual reference on-demand. The on-demand created fields are not considered part of the state of the AST node for any kind of recursion or serialization, so they avoid the original problem.

A single test case was added that represents the original bug, and confirms the fix.

6 files changed, 97 insertions, 27 deletions

diff --git a/source/core/slang-hash.h b/source/core/slang-hash.h
index b2a583744..248d11303 100644
--- a/source/core/slang-hash.h
+++ b/source/core/slang-hash.h
@@ -169,6 +169,14 @@ namespace Slang
         return (left * 16777619) ^ right;
     }
 
+    inline HashCode combineHash(HashCode hash0, HashCode hash1, HashCode hash2)
+    {
+        auto h = hash0;
+        h = combineHash(h, hash1);
+        h = combineHash(h, hash2);
+        return h;
+    }
+
     struct Hasher
     {
     public:
diff --git a/source/slang/slang-ast-type.cpp b/source/slang/slang-ast-type.cpp
index 64b8c7515..45a736f23 100644
--- a/source/slang/slang-ast-type.cpp
+++ b/source/slang/slang-ast-type.cpp
@@ -655,7 +655,7 @@ bool ExtractExistentialType::_equalsImplOverride(Type* type)
 
 HashCode ExtractExistentialType::_getHashCodeOverride()
 {
-    return combineHash(declRef.getHashCode(), interfaceDeclRef.getHashCode());
+    return combineHash(declRef.getHashCode(), originalInterfaceType->getHashCode(), originalInterfaceDeclRef.getHashCode());
 }
 
 Type* ExtractExistentialType::_createCanonicalTypeOverride()
@@ -667,7 +667,8 @@ Val* ExtractExistentialType::_substituteImplOverride(ASTBuilder* astBuilder, Sub
 {
     int diff = 0;
     auto substDeclRef = declRef.substituteImpl(astBuilder, subst, &diff);
-    auto interfaceSubstDeclRef = interfaceDeclRef.substituteImpl(astBuilder, subst, &diff);
+    auto substOriginalInterfaceType = originalInterfaceType->substituteImpl(astBuilder, subst, &diff);
+    auto substOriginalInterfaceDeclRef = originalInterfaceDeclRef.substituteImpl(astBuilder, subst, &diff);
     if (!diff)
         return this;
 
@@ -675,10 +676,46 @@ Val* ExtractExistentialType::_substituteImplOverride(ASTBuilder* astBuilder, Sub
 
     ExtractExistentialType* substValue = astBuilder->create<ExtractExistentialType>();
     substValue->declRef = substDeclRef;
-    substValue->interfaceDeclRef = interfaceSubstDeclRef;
+    substValue->originalInterfaceType = as<Type>(substOriginalInterfaceType);
+    substValue->originalInterfaceDeclRef = substOriginalInterfaceDeclRef;
     return substValue;
 }
 
+SubtypeWitness* ExtractExistentialType::getSubtypeWitness()
+{
+    if (auto cachedValue = this->cachedSubtypeWitness)
+        return cachedValue;
+
+    ExtractExistentialSubtypeWitness* openedWitness = m_astBuilder->create<ExtractExistentialSubtypeWitness>();
+    openedWitness->sub = this;
+    openedWitness->sup = originalInterfaceType;
+    openedWitness->declRef = this->declRef;
+
+    this->cachedSubtypeWitness = openedWitness;
+    return openedWitness;
+}
+
+DeclRef<InterfaceDecl> ExtractExistentialType::getSpecializedInterfaceDeclRef()
+{
+    if (auto cachedValue = this->cachedSpecializedInterfaceDeclRef)
+        return cachedValue;
+
+    auto interfaceDecl = originalInterfaceDeclRef.getDecl();
+
+    SubtypeWitness* openedWitness = getSubtypeWitness();
+
+    ThisTypeSubstitution* openedThisType = m_astBuilder->create<ThisTypeSubstitution>();
+    openedThisType->outer = originalInterfaceDeclRef.substitutions.substitutions;
+    openedThisType->interfaceDecl = interfaceDecl;
+    openedThisType->witness = openedWitness;
+
+    DeclRef<InterfaceDecl> specialiedInterfaceDeclRef = DeclRef<InterfaceDecl>(interfaceDecl, openedThisType);
+
+    this->cachedSpecializedInterfaceDeclRef = specialiedInterfaceDeclRef;
+    return specialiedInterfaceDeclRef;
+}
+
+
 // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! TaggedUnionType !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 
 void TaggedUnionType::_toTextOverride(StringBuilder& out)
diff --git a/source/slang/slang-ast-type.h b/source/slang/slang-ast-type.h
index f4aca515c..5b44a5087 100644
--- a/source/slang/slang-ast-type.h
+++ b/source/slang/slang-ast-type.h
@@ -616,7 +616,29 @@ class ExtractExistentialType : public Type
     SLANG_AST_CLASS(ExtractExistentialType)
 
     DeclRef<VarDeclBase> declRef;
-    DeclRef<InterfaceDecl> interfaceDeclRef;
+
+    // A reference to the original interface this type is known
+    // to be a subtype of.
+    //
+    Type* originalInterfaceType;
+    DeclRef<InterfaceDecl> originalInterfaceDeclRef;
+
+// Following fields will not be reflected (and thus won't be serialized, etc.)
+SLANG_UNREFLECTED
+
+    // A cached decl-ref to the original interface above, with
+    // a this-type substitution that refers to the type extracted here.
+    //
+    // This field is optional and can be filled in on-demand. It does *not*
+    // represent part of the logical value of this `Type`, and should not
+    // be serialized, included in hashes, etc.
+    //
+    DeclRef<InterfaceDecl> cachedSpecializedInterfaceDeclRef;
+
+    // A cached pointer to a witness that shows how this type is a subtype
+    // of `originalInterfaceType`.
+    //
+    SubtypeWitness* cachedSubtypeWitness = nullptr;
 
     // Overrides should be public so base classes can access
     void _toTextOverride(StringBuilder& out);
@@ -624,6 +646,19 @@ class ExtractExistentialType : public Type
     HashCode _getHashCodeOverride();
     Type* _createCanonicalTypeOverride();
     Val* _substituteImplOverride(ASTBuilder* astBuilder, SubstitutionSet subst, int* ioDiff);
+
+        /// Get a witness that shows how this type is a subtype of `originalInterfaceType`.
+        ///
+        /// This operation may create the witness on demand and cache it.
+        ///
+    SubtypeWitness* getSubtypeWitness();
+
+        /// Get a interface decl-ref for the original interface specialized to this type
+        /// (using a type-type substitution).
+        ///
+        /// This operation may create the decl-ref on demand and cache it.
+        ///
+    DeclRef<InterfaceDecl> getSpecializedInterfaceDeclRef();
 };
 
     /// A tagged union of zero or more other types.
diff --git a/source/slang/slang-check-conformance.cpp b/source/slang/slang-check-conformance.cpp
index b95df520d..e77ea4981 100644
--- a/source/slang/slang-check-conformance.cpp
+++ b/source/slang/slang-check-conformance.cpp
@@ -301,19 +301,13 @@ namespace Slang
             // is a subtype of I.
             // We need to check and make sure the interface type of the `ExtractExistentialType`
             // is equal to `superType`.
-            auto interfaceDeclRef = extractExistentialType->interfaceDeclRef;
-            auto thisTypeSubst = findThisTypeSubstitution(interfaceDeclRef.substitutions.substitutions, interfaceDeclRef.getDecl());
-            SLANG_ASSERT(thisTypeSubst && thisTypeSubst == interfaceDeclRef.substitutions.substitutions);
-            // The interfaceDeclRef in `extractExistentialType` contains a `ThisTypeSubstitution`
-            // to allow member lookup to return correct substituted types. Here we just need
-            // to know if that interface is the same as the superType, so we need to exclude
-            // the `ThisTypeSubstitution` from comparison.
-            interfaceDeclRef.substitutions.substitutions = thisTypeSubst->outer;
+            //
+            auto interfaceDeclRef = extractExistentialType->originalInterfaceDeclRef;
             if (interfaceDeclRef.equals(superTypeDeclRef))
             {
                 if (outWitness)
                 {
-                    *outWitness = thisTypeSubst->witness;
+                    *outWitness = extractExistentialType->getSubtypeWitness();
                 }
                 return true;
             }
diff --git a/source/slang/slang-check-expr.cpp b/source/slang/slang-check-expr.cpp
index fbbfcd473..6b1ab13cc 100644
--- a/source/slang/slang-check-expr.cpp
+++ b/source/slang/slang-check-expr.cpp
@@ -101,24 +101,14 @@ namespace Slang
         // immutable temporary so that we can use
         // it directly.
         //
-        auto interfaceDecl = interfaceDeclRef.getDecl();
         return maybeMoveTemp(expr, [&](DeclRef<VarDeclBase> varDeclRef)
         {
             ExtractExistentialType* openedType = m_astBuilder->create<ExtractExistentialType>();
             openedType->declRef = varDeclRef;
+            openedType->originalInterfaceType = expr->type.type;
+            openedType->originalInterfaceDeclRef = interfaceDeclRef;
 
-            ExtractExistentialSubtypeWitness* openedWitness = m_astBuilder->create<ExtractExistentialSubtypeWitness>();
-            openedWitness->sub = openedType;
-            openedWitness->sup = expr->type.type;
-            openedWitness->declRef = varDeclRef;
-
-            ThisTypeSubstitution* openedThisType = m_astBuilder->create<ThisTypeSubstitution>();
-            openedThisType->outer = interfaceDeclRef.substitutions.substitutions;
-            openedThisType->interfaceDecl = interfaceDecl;
-            openedThisType->witness = openedWitness;
-
-            DeclRef<InterfaceDecl> substDeclRef = DeclRef<InterfaceDecl>(interfaceDecl, openedThisType);
-            openedType->interfaceDeclRef = substDeclRef;
+            DeclRef<InterfaceDecl> substDeclRef = openedType->getSpecializedInterfaceDeclRef();
 
             ExtractExistentialValueExpr* openedValue = m_astBuilder->create<ExtractExistentialValueExpr>();
             openedValue->declRef = varDeclRef;
diff --git a/source/slang/slang-lookup.cpp b/source/slang/slang-lookup.cpp
index 20670e7b3..e3093a3db 100644
--- a/source/slang/slang-lookup.cpp
+++ b/source/slang/slang-lookup.cpp
@@ -613,7 +613,13 @@ static void _lookUpMembersInSuperTypeImpl(
     }
     else if (auto extractExistentialType = as<ExtractExistentialType>(superType))
     {
-        _lookUpMembersInSuperTypeDeclImpl(astBuilder, name, leafType, superType, leafIsSuperWitness, extractExistentialType->interfaceDeclRef, request, ioResult, inBreadcrumbs);
+        // We want lookup to be performed on the underlying interface type of the existential,
+        // but we need to have a this-type substitution applied to ensure that the result of
+        // lookup will have a comparable substitution applied (allowing things like associated
+        // types, etc. used in the signature of a method to resolve correctly).
+        //
+        auto interfaceDeclRef = extractExistentialType->getSpecializedInterfaceDeclRef();
+        _lookUpMembersInSuperTypeDeclImpl(astBuilder, name, leafType, superType, leafIsSuperWitness, interfaceDeclRef, request, ioResult, inBreadcrumbs);
     }
     else if( auto thisType = as<ThisType>(superType) )
     {