Add error for forward references in generic constraints (#7615)

* Add error for forward references in generic constraints

Change addresses issue #6545.

The slang compiler's type checker is unable to support cases where
a generic type parameter is referenced as a constraint before it is
declared. For example code like:

````
interface IFoo<T : IFloat>
{
}

void bar<Foo : IFoo<T>, T : IFloat>()
{
}
````

Is not supported, but will currently report a generic error like,

"(0): error 99999: Slang compilation aborted due to an exception
of class Slang::InternalError: unexpected: generic type constraint
during lowering"

This change adds a new check for this kind of code and reports an
error like,

"error 30117: generic constraint for parameter 'Foo' references type
parameter 'T' before it is declared"

when detected. Basic testing of this error is also added in a new
diagnostic test.

* Add error for forward refs in generic constiants update 1

* Add error for forward refs in generic constraints update 2

Revised algo in checkForwardReferencesInGenericConstraint to run
in O(n) instead of the previous O(n^2) using HashSets.

* Add error for forward refs in generic constraints update 3

-Update logic adding referenced decl's in collectReferencedDecls.
-Simplified error string logic.

* Add error for forward refs in generic constraints update 4

-Declare collectReferencedDecls in slang-check.h such that it can
 be used as a general utility function.

* format code

---------

Co-authored-by: slangbot <186143334+slangbot@users.noreply.github.com>

5 files changed, 141 insertions, 0 deletions

diff --git a/source/slang/slang-check-decl.cpp b/source/slang/slang-check-decl.cpp
index 9c77303b9..558834c34 100644
--- a/source/slang/slang-check-decl.cpp
+++ b/source/slang/slang-check-decl.cpp
@@ -343,6 +343,8 @@ struct SemanticsDeclHeaderVisitor : public SemanticsDeclVisitorBase,
 
     void validateGenericConstraintSubType(GenericTypeConstraintDecl* decl, TypeExp type);
 
+    void checkForwardReferencesInGenericConstraint(GenericTypeConstraintDecl* decl);
+
     void visitGenericDecl(GenericDecl* genericDecl);
 
     void visitTypeDefDecl(TypeDefDecl* decl);
@@ -3220,6 +3222,104 @@ void SemanticsDeclHeaderVisitor::validateGenericConstraintSubType(
     }
 }
 
+// General utility function to collect all referenced declarations from a value
+void collectReferencedDecls(Val* val, HashSet<Decl*>& outDecls)
+{
+    if (!val)
+        return;
+
+    // Process operands to find declaration references
+    for (Index i = 0; i < val->getOperandCount(); i++)
+    {
+        auto& operand = val->m_operands[i];
+        if (operand.kind == ValNodeOperandKind::ValNode)
+        {
+            // ValNode operands contain Val* nodes that we recursively
+            // traverse to find nested declaration references. For example, in the
+            // constraint expression IFoo<IBar<T>>, we need to traverse the nested
+            // type structure to find the reference to declaration T.
+            collectReferencedDecls(val->getOperand(i), outDecls);
+        }
+        else if (operand.kind == ValNodeOperandKind::ASTNode)
+        {
+            // ASTNode operands are leaf cases. They can contain any NodeBase*,
+            // so we need to check if the referenced astnode is actually a Decl*.
+            if (auto declOperand = as<Decl>(operand.values.nodeOperand))
+            {
+                outDecls.add(declOperand);
+            }
+        }
+    }
+}
+
+void SemanticsDeclHeaderVisitor::checkForwardReferencesInGenericConstraint(
+    GenericTypeConstraintDecl* decl)
+{
+    // Check if this constraint references type parameters that appear later
+    // in the same GenericDecl's parameter list and report a forward reference error
+    // if it does.
+
+    // Only applies to constraints within GenericDecl contexts where declaration order matters.
+    // If that's not the case, then early out.
+    auto parentGeneric = as<GenericDecl>(decl->parentDecl);
+    if (!parentGeneric)
+        return;
+
+    // Build a HashSet of all generic parameter declarations seen before the constraint.
+    // After we collect the referenced declarations from the constraint's superior type,
+    // we can do a quick check with the HashSet to see if a reference falls outside of
+    // the set, indicating that we have a forward reference.
+    HashSet<Decl*> declaredBeforeConstraint;
+    bool foundConstraint = false;
+
+    for (Index i = 0; i < parentGeneric->getDirectMemberDeclCount(); ++i)
+    {
+        auto member = parentGeneric->getDirectMemberDecl(i);
+
+        if (member == decl)
+        {
+            foundConstraint = true;
+            break;
+        }
+
+        // Add generic type parameters to our "declared so far" set
+        if (auto typeParam = as<GenericTypeParamDeclBase>(member))
+        {
+            declaredBeforeConstraint.add(typeParam);
+        }
+    }
+
+    // This probably shouldn't happen, but if the constraint is not found in parent GenericDecl,
+    // just early out as we can't check forward references.
+    if (!foundConstraint)
+        return;
+
+    // Collect all referenced declarations from the constraint's superior type
+    HashSet<Decl*> referencedDecls;
+    collectReferencedDecls(decl->sup.type, referencedDecls);
+
+    // Check if any of the referenced declarations are forward references (not in our "declared so
+    // far" set)
+    for (auto referencedDecl : referencedDecls)
+    {
+        if (auto typeParam = as<GenericTypeParamDeclBase>(referencedDecl))
+        {
+            // Check if this type parameter belongs to the same generic but is NOT in our "declared
+            // so far" set
+            if (typeParam->parentDecl == parentGeneric &&
+                !declaredBeforeConstraint.contains(typeParam))
+            {
+                // Found a forward reference, report an error.
+                getSink()->diagnose(
+                    decl->sup.exp,
+                    Diagnostics::forwardReferenceInGenericConstraint,
+                    decl->sub.type,
+                    typeParam);
+            }
+        }
+    }
+}
+
 void SemanticsDeclHeaderVisitor::visitTypeCoercionConstraintDecl(TypeCoercionConstraintDecl* decl)
 {
     CheckConstraintSubType(decl->toType);
@@ -3245,6 +3345,9 @@ void SemanticsDeclHeaderVisitor::visitGenericTypeConstraintDecl(GenericTypeConst
     if (!decl->sup.type)
         decl->sup = TranslateTypeNodeForced(decl->sup);
 
+    // Check for forward references in generic constraints after type translation
+    checkForwardReferencesInGenericConstraint(decl);
+
     if (getLinkage()->m_optionSet.shouldRunNonEssentialValidation())
     {
         validateGenericConstraintSubType(decl, decl->sub);
diff --git a/source/slang/slang-check.h b/source/slang/slang-check.h
index ebeff1afe..118b08a83 100644
--- a/source/slang/slang-check.h
+++ b/source/slang/slang-check.h
@@ -37,4 +37,7 @@ OrderedDictionary<GenericTypeParamDeclBase*, List<Type*>> getCanonicalGenericCon
 OrderedDictionary<Type*, List<Type*>> getCanonicalGenericConstraints2(
     ASTBuilder* builder,
     DeclRef<ContainerDecl> genericDecl);
+
+// General utility function to collect all referenced declarations from a value
+void collectReferencedDecls(Val* val, HashSet<Decl*>& outDecls);
 } // namespace Slang
diff --git a/source/slang/slang-diagnostic-defs.h b/source/slang/slang-diagnostic-defs.h
index 8efdf1d91..bf0e91150 100644
--- a/source/slang/slang-diagnostic-defs.h
+++ b/source/slang/slang-diagnostic-defs.h
@@ -1054,6 +1054,11 @@ DIAGNOSTIC(
     Error,
     throwTypeIncompatibleWithErrorType,
     "the type `$0` of `throw` is not compatible with function's error type `$1`.")
+DIAGNOSTIC(
+    30117,
+    Error,
+    forwardReferenceInGenericConstraint,
+    "generic constraint for parameter '$0' references type parameter '$1' before it is declared")
 
 // Include
 DIAGNOSTIC(
diff --git a/tests/diagnostics/generic-constraint-forward-reference.slang b/tests/diagnostics/generic-constraint-forward-reference.slang
new file mode 100644
index 000000000..08a6c3478
--- /dev/null
+++ b/tests/diagnostics/generic-constraint-forward-reference.slang
@@ -0,0 +1,16 @@
+//DIAGNOSTIC_TEST:SIMPLE:

+// Test forward references in generic constraints

+

+interface IFloat {}

+interface IFoo<T : IFloat> {}

+interface IBar<T, U> {}

+

+// Test case 1: Simple forward reference in interface constraint

+void test1<Foo : IFoo<T>, T : IFloat>() {}

+

+// Test case 2: Multiple forward references in a single constraint

+void test2<A : IBar<B, C>, B : IFloat, C : IFloat>() {}

+

+// Valid case that should NOT produce our error:

+// Test case 3: Correct order - type parameter declared before use

+void test3<T : IFloat, Foo : IFoo<T>>() {}

diff --git a/tests/diagnostics/generic-constraint-forward-reference.slang.expected b/tests/diagnostics/generic-constraint-forward-reference.slang.expected
new file mode 100644
index 000000000..5c6b2707b
--- /dev/null
+++ b/tests/diagnostics/generic-constraint-forward-reference.slang.expected
@@ -0,0 +1,14 @@
+result code = -1
+standard error = {
+tests/diagnostics/generic-constraint-forward-reference.slang(9): error 30117: generic constraint for parameter 'Foo' references type parameter 'T' before it is declared
+void test1<Foo : IFoo<T>, T : IFloat>() {}
+                 ^~~~
+tests/diagnostics/generic-constraint-forward-reference.slang(12): error 30117: generic constraint for parameter 'A' references type parameter 'B' before it is declared
+void test2<A : IBar<B, C>, B : IFloat, C : IFloat>() {}
+               ^~~~
+tests/diagnostics/generic-constraint-forward-reference.slang(12): error 30117: generic constraint for parameter 'A' references type parameter 'C' before it is declared
+void test2<A : IBar<B, C>, B : IFloat, C : IFloat>() {}
+               ^~~~
+}
+standard output = {
+}