From 26e25f6e73a9808ad93c98ad34907e3a27b6726c Mon Sep 17 00:00:00 2001
From: Yong He <yonghe@outlook.com>
Date: Mon, 18 Mar 2024 17:21:48 -0700
Subject: Check for cylic types. (#3790)

---
 source/slang/slang-diagnostic-defs.h           |  2 +
 source/slang/slang-ir-check-recursive-type.cpp | 59 ++++++++++++++++++++++++++
 source/slang/slang-ir-check-recursive-type.h   | 11 +++++
 source/slang/slang-lower-to-ir.cpp             |  4 ++
 4 files changed, 76 insertions(+)
 create mode 100644 source/slang/slang-ir-check-recursive-type.cpp
 create mode 100644 source/slang/slang-ir-check-recursive-type.h

(limited to 'source')

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());
 
-- 
cgit v1.2.3