Diagnose circularly-defined constants (#1384)

* Diagnose circularly-defined constants

Work on #1374

This change diagnoses cases like the following:

```hlsl
static const int kCircular = kCircular;

static const int kInfinite = kInfinite + 1;

static const int kHere = kThere;
static const int kThere = kHere;
```

By diagnosing these as errors in the front-end we protect against infinite recursion leading to stack overflow crashes.

The basic approach is to have front-end constant folding track variables that are in use when folding a sub-expression, and then diagnosing an error if the same variable is encountered again while it is in use. In order to make sure the error occurs whether or not the constant is referenced, we invoke constant folding on all `static const` integer variables.

Limitations:

* This only works for integers, since that is all front-end constant folding applies to. A future change can/should catch circularity in constants at the IR level (and handle more types).

* This only works for constants. Circular references in the definition of a global variable are harder to diagnose, but at least shouldn't result in compiler crashes.

* This doesn't work across modules, or through generic specialization: anything that requires global knowledge won't be checked

* fixup: missing files

* fixup: review feedback

4 files changed, 170 insertions, 52 deletions

diff --git a/source/slang/slang-check-decl.cpp b/source/slang/slang-check-decl.cpp
index b69c8cf0d..3aeca23cd 100644
--- a/source/slang/slang-check-decl.cpp
+++ b/source/slang/slang-check-decl.cpp
@@ -775,6 +775,24 @@ namespace Slang
         return true;
     }
 
+    void SemanticsVisitor::_validateCircularVarDefinition(VarDeclBase* varDecl)
+    {
+        // The easiest way to test if the declaration is circular is to
+        // validate it as a constant.
+        //
+        // TODO: The logic here will only apply for `static const` declarations
+        // of integer type, given that our constant folding currently only
+        // applies to such types. A more robust fix would involve a truly
+        // recursive walk of the AST declarations, and an even *more* robust
+        // fix would wait until after IR linking to detect and diagnose circularity
+        // in case it crosses module boundaries.
+        //
+        //
+        if(!isScalarIntegerType(varDecl->type))
+            return;
+        tryConstantFoldDeclRef(DeclRef<VarDeclBase>(varDecl, nullptr), nullptr);
+    }
+
     void SemanticsDeclHeaderVisitor::checkVarDeclCommon(VarDeclBase* varDecl)
     {
         // A variable that didn't have an explicit type written must
@@ -804,6 +822,8 @@ namespace Slang
 
                 varDecl->initExpr = initExpr;
                 varDecl->type.type = initExpr->type;
+
+                _validateCircularVarDefinition(varDecl);
             }
 
             // If we've gone down this path, then the variable
@@ -857,11 +877,16 @@ namespace Slang
         {
             // If the variable has an explicit initial-value expression,
             // then we simply need to check that expression and coerce
-            // it to the tyep of the variable.
+            // it to the type of the variable.
             //
             initExpr = CheckTerm(initExpr);
             initExpr = coerce(varDecl->type.Ptr(), initExpr);
             varDecl->initExpr = initExpr;
+
+            // We need to ensure that any variable doesn't introduce
+            // a constant with a circular definition.
+            //
+            _validateCircularVarDefinition(varDecl);
         }
         else
         {
@@ -1970,18 +1995,25 @@ namespace Slang
         return (BaseTypeInfo::getInfo(baseType).flags & BaseTypeInfo::Flag::Integer) != 0;
     }
 
-    void SemanticsVisitor::validateEnumTagType(Type* type, SourceLoc const& loc)
+    bool SemanticsVisitor::isScalarIntegerType(Type* type)
     {
-        if(auto basicType = as<BasicExpressionType>(type))
-        {
-            // Allow the built-in integer types.
-            if(isIntegerBaseType(basicType->baseType))
-                return;
+        auto basicType = as<BasicExpressionType>(type);
+        if(!basicType)
+            return false;
 
-            // By default, don't allow other types to be used
-            // as an `enum` tag type.
-        }
+        return isIntegerBaseType(basicType->baseType);
+    }
 
+    void SemanticsVisitor::validateEnumTagType(Type* type, SourceLoc const& loc)
+    {
+        // Allow the built-in integer types.
+        //
+        if(isScalarIntegerType(type))
+            return;
+
+        // By default, don't allow other types to be used
+        // as an `enum` tag type.
+        //
         getSink()->diagnose(loc, Diagnostics::invalidEnumTagType, type);
     }
 
@@ -2177,7 +2209,7 @@ namespace Slang
                 // the tag value for a successor case that doesn't
                 // provide an explicit tag.
 
-                IntVal* explicitTagVal = TryConstantFoldExpr(explicitTagValExpr);
+                IntVal* explicitTagVal = tryConstantFoldExpr(explicitTagValExpr, nullptr);
                 if(explicitTagVal)
                 {
                     if(auto constIntVal = as<ConstantIntVal>(explicitTagVal))
diff --git a/source/slang/slang-check-expr.cpp b/source/slang/slang-check-expr.cpp
index 17bd5e263..d2e5afd85 100644
--- a/source/slang/slang-check-expr.cpp
+++ b/source/slang/slang-check-expr.cpp
@@ -669,8 +669,9 @@ namespace Slang
         return m_astBuilder->create<ConstantIntVal>(expr->value);
     }
 
-    IntVal* SemanticsVisitor::TryConstantFoldExpr(
-        InvokeExpr* invokeExpr)
+    IntVal* SemanticsVisitor::tryConstantFoldExpr(
+        InvokeExpr*                     invokeExpr,
+        ConstantFoldingCircularityInfo* circularityInfo)
     {
         // We need all the operands to the expression
 
@@ -707,7 +708,7 @@ namespace Slang
         bool allConst = true;
         for (auto argExpr : invokeExpr->arguments)
         {
-            auto argVal = TryCheckIntegerConstantExpression(argExpr);
+            auto argVal = tryFoldIntegerConstantExpression(argExpr, circularityInfo);
             if (!argVal)
                 return nullptr;
 
@@ -795,8 +796,53 @@ namespace Slang
         return result;
     }
 
-    IntVal* SemanticsVisitor::TryConstantFoldExpr(
-        Expr* expr)
+    bool SemanticsVisitor::_checkForCircularityInConstantFolding(
+        Decl*                           decl,
+        ConstantFoldingCircularityInfo* circularityInfo)
+    {
+        // TODO: If the `decl` is already on the chain of `circularityInfo`,
+        // then we know that we are trying to recursively fold the
+        // same declaration as part of its own definition, and we need
+        // to diagnose that as an error.
+        //
+        for( auto info = circularityInfo; info; info = info->next )
+        {
+            if(decl == info->decl)
+            {
+                getSink()->diagnose(decl, Diagnostics::variableUsedInItsOwnDefinition, decl);
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    IntVal* SemanticsVisitor::tryConstantFoldDeclRef(
+        DeclRef<VarDeclBase> const&     declRef,
+        ConstantFoldingCircularityInfo* circularityInfo)
+    {
+        auto decl = declRef.getDecl();
+
+        if(_checkForCircularityInConstantFolding(decl, circularityInfo))
+            return nullptr;
+
+        // In HLSL, `static const` is used to mark compile-time constant expressions
+        if(!decl->hasModifier<HLSLStaticModifier>())
+            return nullptr;
+        if(!decl->hasModifier<ConstModifier>())
+            return nullptr;
+
+        auto initExpr = getInitExpr(m_astBuilder, declRef);
+        if(!initExpr)
+            return nullptr;
+
+        ConstantFoldingCircularityInfo newCircularityInfo(decl, circularityInfo);
+        return tryConstantFoldExpr(initExpr, &newCircularityInfo);
+    }
+
+    IntVal* SemanticsVisitor::tryConstantFoldExpr(
+        Expr*                           expr,
+        ConstantFoldingCircularityInfo* circularityInfo)
     {
         // Unwrap any "identity" expressions
         while (auto parenExpr = as<ParenExpr>(expr))
@@ -825,40 +871,32 @@ namespace Slang
             // are defined in a way that can be used as a constant expression:
             if(auto varRef = declRef.as<VarDeclBase>())
             {
-                auto varDecl = varRef.getDecl();
-
-                // In HLSL, `static const` is used to mark compile-time constant expressions
-                if(auto staticAttr = varDecl->findModifier<HLSLStaticModifier>())
-                {
-                    if(auto constAttr = varDecl->findModifier<ConstModifier>())
-                    {
-                        // HLSL `static const` can be used as a constant expression
-                        if(auto initExpr = getInitExpr(m_astBuilder, varRef))
-                        {
-                            return TryConstantFoldExpr(initExpr);
-                        }
-                    }
-                }
+                return tryConstantFoldDeclRef(varRef, circularityInfo);
             }
             else if(auto enumRef = declRef.as<EnumCaseDecl>())
             {
                 // The cases in an `enum` declaration can also be used as constant expressions,
                 if(auto tagExpr = getTagExpr(m_astBuilder, enumRef))
                 {
-                    return TryConstantFoldExpr(tagExpr);
+                    auto enumCaseDecl = enumRef.getDecl();
+                    if(_checkForCircularityInConstantFolding(enumCaseDecl, circularityInfo))
+                        return nullptr;
+
+                    ConstantFoldingCircularityInfo newCircularityInfo(enumCaseDecl, circularityInfo);
+                    return tryConstantFoldExpr(tagExpr, &newCircularityInfo);
                 }
             }
         }
 
         if(auto castExpr = as<TypeCastExpr>(expr))
         {
-            auto val = TryConstantFoldExpr(castExpr->arguments[0]);
+            auto val = tryConstantFoldExpr(castExpr->arguments[0], circularityInfo);
             if(val)
                 return val;
         }
         else if (auto invokeExpr = as<InvokeExpr>(expr))
         {
-            auto val = TryConstantFoldExpr(invokeExpr);
+            auto val = tryConstantFoldExpr(invokeExpr, circularityInfo);
             if (val)
                 return val;
         }
@@ -866,21 +904,18 @@ namespace Slang
         return nullptr;
     }
 
-    IntVal* SemanticsVisitor::TryCheckIntegerConstantExpression(Expr* exp)
+    IntVal* SemanticsVisitor::tryFoldIntegerConstantExpression(
+        Expr*                           expr,
+        ConstantFoldingCircularityInfo* circularityInfo)
     {
         // Check if type is acceptable for an integer constant expression
-        if(auto basicType = as<BasicExpressionType>(exp->type.type))
-        {
-            if(!isIntegerBaseType(basicType->baseType))
-                return nullptr;
-        }
-        else
-        {
+        //
+        if(!isScalarIntegerType(expr->type))
             return nullptr;
-        }
 
         // Consider operations that we might be able to constant-fold...
-        return TryConstantFoldExpr(exp);
+        //
+        return tryConstantFoldExpr(expr, circularityInfo);
     }
 
     IntVal* SemanticsVisitor::CheckIntegerConstantExpression(Expr* inExpr, DiagnosticSink* sink)
@@ -894,7 +929,7 @@ namespace Slang
         // No need to issue further errors if the type coercion failed.
         if(IsErrorExpr(expr)) return nullptr;
 
-        auto result = TryCheckIntegerConstantExpression(expr);
+        auto result = tryFoldIntegerConstantExpression(expr, nullptr);
         if (!result && sink)
         {
             sink->diagnose(expr, Diagnostics::expectedIntegerConstantNotConstant);
@@ -915,7 +950,7 @@ namespace Slang
         // No need to issue further errors if the type coercion failed.
         if(IsErrorExpr(expr)) return nullptr;
 
-        auto result = TryConstantFoldExpr(expr);
+        auto result = tryConstantFoldExpr(expr, nullptr);
         if (!result)
         {
             getSink()->diagnose(expr, Diagnostics::expectedIntegerConstantNotConstant);
diff --git a/source/slang/slang-check-impl.h b/source/slang/slang-check-impl.h
index 72965e8c5..93ae87f40 100644
--- a/source/slang/slang-check-impl.h
+++ b/source/slang/slang-check-impl.h
@@ -491,6 +491,18 @@ namespace Slang
         // Capture the "base" expression in case this is a member reference
         Expr* GetBaseExpr(Expr* expr);
 
+            /// Validate a declaration to ensure that it doesn't introduce a circularly-defined constant
+            ///
+            /// Circular definition in a constant may lead to infinite looping or stack overflow in
+            /// the compiler, so it needs to be protected against.
+            ///
+            /// Note that this function does *not* protect against circular definitions in general,
+            /// and a program that indirectly initializes a global variable using its own value (e.g.,
+            /// by calling a function that indirectly reads the variable) will be allowed and then
+            /// exhibit undefined behavior at runtime.
+            ///
+        void _validateCircularVarDefinition(VarDeclBase* varDecl);
+
     public:
 
         bool ValuesAreEqual(
@@ -778,6 +790,9 @@ namespace Slang
 
         bool isIntegerBaseType(BaseType baseType);
 
+            /// Is `type` a scalar integer type.
+        bool isScalarIntegerType(Type* type);
+
         // Validate that `type` is a suitable type to use
         // as the tag type for an `enum`
         void validateEnumTagType(Type* type, SourceLoc const& loc);
@@ -827,15 +842,50 @@ namespace Slang
             return getNamePool()->getName(text);
         }
 
-        IntVal* TryConstantFoldExpr(
-            InvokeExpr* invokeExpr);
+            /// Helper type to detect and catch circular definitions when folding constants,
+            /// to prevent the compiler from going into infinite loops or overflowing the stack.
+        struct ConstantFoldingCircularityInfo
+        {
+            ConstantFoldingCircularityInfo(
+                Decl*                           decl,
+                ConstantFoldingCircularityInfo* next)
+                : decl(decl)
+                , next(next)
+            {}
+
+                /// A declaration whose value is contributing to the constant being folded
+            Decl*                           decl = nullptr;
+
+                /// The rest of the links in the chain of declarations being folded
+            ConstantFoldingCircularityInfo* next = nullptr;
+        };
+
+            /// Try to apply front-end constant folding to determine the value of `invokeExpr`.
+        IntVal* tryConstantFoldExpr(
+            InvokeExpr*                     invokeExpr,
+            ConstantFoldingCircularityInfo* circularityInfo);
+
+            /// Try to apply front-end constant folding to determine the value of `expr`.
+        IntVal* tryConstantFoldExpr(
+            Expr*                           expr,
+            ConstantFoldingCircularityInfo* circularityInfo);
 
-        IntVal* TryConstantFoldExpr(
-            Expr* expr);
+        bool _checkForCircularityInConstantFolding(
+            Decl*                           decl,
+            ConstantFoldingCircularityInfo* circularityInfo);
 
-        // Try to check an integer constant expression, either returning the value,
-        // or NULL if the expression isn't recognized as a constant.
-        IntVal* TryCheckIntegerConstantExpression(Expr* exp);
+            /// Try to resolve a compile-time constant `IntVal` from the given `declRef`.
+        IntVal* tryConstantFoldDeclRef(
+            DeclRef<VarDeclBase> const&     declRef,
+            ConstantFoldingCircularityInfo* circularityInfo);
+
+            /// Try to extract the value of an integer constant expression, either
+            /// returning the `IntVal` value, or null if the expression isn't recognized
+            /// as an integer constant.
+            ///
+        IntVal* tryFoldIntegerConstantExpression(
+            Expr*                           expr,
+            ConstantFoldingCircularityInfo* circularityInfo);
 
         // Enforce that an expression resolves to an integer constant, and get its value
         IntVal* CheckIntegerConstantExpression(Expr* inExpr);
diff --git a/source/slang/slang-diagnostic-defs.h b/source/slang/slang-diagnostic-defs.h
index 41c674ddb..f6d38889b 100644
--- a/source/slang/slang-diagnostic-defs.h
+++ b/source/slang/slang-diagnostic-defs.h
@@ -299,6 +299,7 @@ DIAGNOSTIC(30301, Error, globalGenParamInGlobalScopeOnly, "'type_param' can only
 // TODO: need to assign numbers to all these extra diagnostics...
 DIAGNOSTIC(39999, Fatal, cyclicReference, "cyclic reference '$0'.")
 DIAGNOSTIC(39999, Fatal, localVariableUsedBeforeDeclared, "local variable '$0' is being used before its declaration.")
+DIAGNOSTIC(39999, Error, variableUsedInItsOwnDefinition, "the initial-value expression for variable '$0' depends on the value of the variable itself")
 
 // 304xx: generics
 DIAGNOSTIC(30400, Error, genericTypeNeedsArgs, "generic type '$0' used without argument")