Check for cylic types. (#3790)

7 files changed, 105 insertions, 0 deletions

diff --git a/build/visual-studio/slang/slang.vcxproj b/build/visual-studio/slang/slang.vcxproj
index c503e8f4d..aca22890b 100644
--- a/build/visual-studio/slang/slang.vcxproj
+++ b/build/visual-studio/slang/slang.vcxproj
@@ -373,6 +373,7 @@ IF EXIST ..\..\..\external\slang-glslang\bin\windows-aarch64\release\slang-glsla
     <ClInclude Include="..\..\..\source\slang\slang-ir-bit-field-accessors.h" />

     <ClInclude Include="..\..\..\source\slang\slang-ir-byte-address-legalize.h" />

     <ClInclude Include="..\..\..\source\slang\slang-ir-check-differentiability.h" />

+    <ClInclude Include="..\..\..\source\slang\slang-ir-check-recursive-type.h" />

     <ClInclude Include="..\..\..\source\slang\slang-ir-check-unsupported-inst.h" />

     <ClInclude Include="..\..\..\source\slang\slang-ir-cleanup-void.h" />

     <ClInclude Include="..\..\..\source\slang\slang-ir-clone.h" />

@@ -598,6 +599,7 @@ IF EXIST ..\..\..\external\slang-glslang\bin\windows-aarch64\release\slang-glsla
     <ClCompile Include="..\..\..\source\slang\slang-ir-bit-field-accessors.cpp" />

     <ClCompile Include="..\..\..\source\slang\slang-ir-byte-address-legalize.cpp" />

     <ClCompile Include="..\..\..\source\slang\slang-ir-check-differentiability.cpp" />

+    <ClCompile Include="..\..\..\source\slang\slang-ir-check-recursive-type.cpp" />

     <ClCompile Include="..\..\..\source\slang\slang-ir-check-unsupported-inst.cpp" />

     <ClCompile Include="..\..\..\source\slang\slang-ir-cleanup-void.cpp" />

     <ClCompile Include="..\..\..\source\slang\slang-ir-clone.cpp" />

diff --git a/build/visual-studio/slang/slang.vcxproj.filters b/build/visual-studio/slang/slang.vcxproj.filters
index 9c274990d..7b6b7de2c 100644
--- a/build/visual-studio/slang/slang.vcxproj.filters
+++ b/build/visual-studio/slang/slang.vcxproj.filters
@@ -207,6 +207,9 @@
     <ClInclude Include="..\..\..\source\slang\slang-ir-check-differentiability.h">

       <Filter>Header Files</Filter>

     </ClInclude>

+    <ClInclude Include="..\..\..\source\slang\slang-ir-check-recursive-type.h">

+      <Filter>Header Files</Filter>

+    </ClInclude>

     <ClInclude Include="..\..\..\source\slang\slang-ir-check-unsupported-inst.h">

       <Filter>Header Files</Filter>

     </ClInclude>

@@ -878,6 +881,9 @@
     <ClCompile Include="..\..\..\source\slang\slang-ir-check-differentiability.cpp">

       <Filter>Source Files</Filter>

     </ClCompile>

+    <ClCompile Include="..\..\..\source\slang\slang-ir-check-recursive-type.cpp">

+      <Filter>Source Files</Filter>

+    </ClCompile>

     <ClCompile Include="..\..\..\source\slang\slang-ir-check-unsupported-inst.cpp">

       <Filter>Source Files</Filter>

     </ClCompile>

diff --git a/source/slang/slang-diagnostic-defs.h b/source/slang/slang-diagnostic-defs.h
index ba57e63f9..7a72daa5e 100644
--- a/source/slang/slang-diagnostic-defs.h
+++ b/source/slang/slang-diagnostic-defs.h
@@ -691,6 +691,7 @@ DIAGNOSTIC(40010, Note, seeInterfaceUsage, "see usage of interface '$0'.")
 
 DIAGNOSTIC(40011, Error, unconstrainedGenericParameterNotAllowedInDynamicFunction, "unconstrained generic paramter '$0' is not allowed in a dynamic function.")
 
+
 DIAGNOSTIC(40020, Error, cannotUnrollLoop, "loop does not terminate within the limited number of iterations, unrolling is aborted.")
 
 DIAGNOSTIC(40030, Fatal, functionNeverReturnsFatal, "function '$0' never returns, compilation ceased.")
@@ -698,6 +699,7 @@ DIAGNOSTIC(40030, Fatal, functionNeverReturnsFatal, "function '$0' never returns
 // 41000 - IR-level validation issues
 
 DIAGNOSTIC(41000, Warning, unreachableCode, "unreachable code detected")
+DIAGNOSTIC(41001, Error, recursiveType, "type '$0' contains cyclic reference to itself.")
 
 DIAGNOSTIC(41010, Warning, missingReturn, "control flow may reach end of non-'void' function")
 DIAGNOSTIC(41015, Error, usingUninitializedValue, "use of uninitialized value '$0'")
diff --git a/source/slang/slang-ir-check-recursive-type.cpp b/source/slang/slang-ir-check-recursive-type.cpp
new file mode 100644
index 000000000..8679801d0
--- /dev/null
+++ b/source/slang/slang-ir-check-recursive-type.cpp
@@ -0,0 +1,59 @@
+#include "slang-ir-check-recursive-type.h"
+#include "slang-ir-util.h"
+
+namespace Slang
+{
+    bool checkTypeRecursionImpl(HashSet<IRInst*>& checkedTypes, HashSet<IRInst*>& stack, IRInst* type, IRInst* field, DiagnosticSink* sink)
+    {
+        auto visitElementType = [&](IRInst* elementType, IRInst* field) -> bool
+            {
+                if (!stack.add(elementType))
+                {
+                    sink->diagnose(field ? field : type, Diagnostics::recursiveType, type);
+                    return false;
+                }
+                if (checkedTypes.add(elementType))
+                    checkTypeRecursionImpl(checkedTypes, stack, elementType, field, sink);
+                stack.remove(elementType);
+                return true;
+            };
+        if (auto arrayType = as<IRArrayTypeBase>(type))
+        {
+            return visitElementType(arrayType->getElementType(), field);
+        }
+        else if (auto structType = as<IRStructType>(type))
+        {
+            for (auto sfield : structType->getFields())
+                if (!visitElementType(sfield->getFieldType(), sfield))
+                    return false;
+        }
+        return true;
+    }
+
+    void checkTypeRecursion(HashSet<IRInst*>& checkedTypes, IRInst* type, DiagnosticSink* sink)
+    {
+        HashSet<IRInst*> stack;
+        if (checkedTypes.add(type))
+        {
+            stack.add(type);
+            checkTypeRecursionImpl(checkedTypes, stack, type, nullptr, sink);
+        }
+    }
+
+    void checkForRecursiveTypes(IRModule* module, DiagnosticSink* sink)
+    {
+        HashSet<IRInst*> checkedTypes;
+        for (auto globalInst : module->getGlobalInsts())
+        {
+            switch (globalInst->getOp())
+            {
+            case kIROp_StructType:
+                {
+                    checkTypeRecursion(checkedTypes, globalInst, sink);
+                }
+                break;
+            }
+        }
+    }
+
+}
diff --git a/source/slang/slang-ir-check-recursive-type.h b/source/slang/slang-ir-check-recursive-type.h
new file mode 100644
index 000000000..0ab911e79
--- /dev/null
+++ b/source/slang/slang-ir-check-recursive-type.h
@@ -0,0 +1,11 @@
+#pragma once
+
+namespace Slang
+{
+    struct IRModule;
+    class DiagnosticSink;
+
+    void checkForRecursiveTypes(
+        IRModule*       module,
+        DiagnosticSink* sink);
+}
diff --git a/source/slang/slang-lower-to-ir.cpp b/source/slang/slang-lower-to-ir.cpp
index 4e564f703..5a3b0c2c5 100644
--- a/source/slang/slang-lower-to-ir.cpp
+++ b/source/slang/slang-lower-to-ir.cpp
@@ -20,6 +20,7 @@
 #include "slang-ir-insts.h"
 #include "slang-ir-insert-debug-value-store.h"
 #include "slang-ir-check-differentiability.h"
+#include "slang-ir-check-recursive-type.h"
 #include "slang-ir-missing-return.h"
 #include "slang-ir-sccp.h"
 #include "slang-ir-ssa.h"
@@ -10665,6 +10666,9 @@ RefPtr<IRModule> generateIRForTranslationUnit(
 
     checkForMissingReturns(module, compileRequest->getSink());
 
+    // We don't allow recursive types.
+    checkForRecursiveTypes(module, compileRequest->getSink());
+
     // Check for invalid differentiable function body.
     checkAutoDiffUsages(module, compileRequest->getSink());
 
diff --git a/tests/bugs/cyclic-type.slang b/tests/bugs/cyclic-type.slang
new file mode 100644
index 000000000..49591fbe6
--- /dev/null
+++ b/tests/bugs/cyclic-type.slang
@@ -0,0 +1,21 @@
+
+//TEST:SIMPLE(filecheck=CHECK):-target spirv -emit-spirv-directly
+
+// CHECK: error 41001:
+
+struct TA
+{
+    TB tb;
+}
+
+struct TB
+{
+    TA ta[2];
+}
+
+[numthreads(1,1,1)]
+void main()
+{
+    TA ta;
+    ta.tb.ta[0] = ta;
+}
\ No newline at end of file