Templated infinitely recursive function does not fail to compile

[alexkaratarakis]

Min repro:

template <typename R1>
static R1 self_recursion_template(const R1& input)
{
    return self_recursion_template<R1>(input);
}

static int self_recursion_non_template(const int& input)
{
    return self_recursion_non_template(input);
}

int main()
{
    int input{};

    const int result = self_recursion_template(input);
    // const int result = self_recursion_non_template(input);  // Properly fails to compile
    (void)result;
}

Expected results: compilation fails for the templated version of infinite self-recursion like it does for the non-templated version of infinite self-recursion.

Actual results: compiles and then stack overflows when trying to run it.

Additionally, msvc rejects the code.

Demo: https://godbolt.org/z/eEq7PT771

Ubuntu clang version 20.1.6 (++20250517123339+5befd1fb3c97-1~exp1~20250517003355.120

[zwuis]

I think Clang is correct here. But a warning will be emitted if you add command line option -Winfinite-recursion. -Wall also enables this warning.

[llvmbot]

@llvm/issue-subscribers-clang-frontend

Author: Alexander Karatarakis (alexkaratarakis)

Min repro: ```C++ template <typename R1> static R1 self_recursion_template(const R1& input) { return self_recursion_template<R1>(input); }

static int self_recursion_non_template(const int& input)
{
return self_recursion_non_template(input);
}

int main()
{
int input{};

const int result = self_recursion_template(input);
// const int result = self_recursion_non_template(input);  // Properly fails to compile
(void)result;

}

Expected results: compilation fails for the templated version of infinite self-recursion like it does for the non-templated version of infinite self-recursion.

Actual results: compiles and then stack overflows when trying to run it.


Additionally, `msvc` rejects the code.


Demo: https://godbolt.org/z/eEq7PT771

`Ubuntu clang version 20.1.6 (++20250517123339+5befd1fb3c97-1~exp1~20250517003355.120`
</details>

[AaronBallman]

I think Clang is correct here. But a warning will be emitted if you add command line option -Winfinite-recursion. -Wall also enables this warning.

That warning isn't firing for the templated code though: https://godbolt.org/z/WYoo8Y45b

We cannot fail compilation for this scenario (unless the user passed -Werror), but I think we should be able to issue the diagnostic for the templated function after instantiation.

[AaronBallman]

Ah, this is done intentionally to suppress false positives: 2f024f4

But because this is an analysis-based warning, it uses the CFG to decide whether to diagnose or not. And that means we should have already fully instantiated templates and resolved which specializations are being called. So I still think this could be reasonable to support, but perhaps I'm not thinking about the false positives the original author was concerned by.

[zygoloid]

So I still think this could be reasonable to support, but perhaps I'm not thinking about the false positives the original author was concerned by.

I suspect the final test in the added test cases is the relevant one here:

// DoStuff<0,0>() is instantiated, but never called.
template<int First, int Last>
int DoStuff() {
  if (First + 1 == Last) {
    // This branch gets removed during <0, 0> instantiation in so CFG for this
    // function goes straight to the else branch.
    DoSomethingHere();
  } else {
    DoStuff<First, (First + Last)/2>();
    DoStuff<(First + Last)/2, Last>();
  }
  return 0;
}
int stuff = DoStuff<0, 1>();

... where DoStuff<0, 0> does indeed recursively call itself, and is indeed instantiated by DoStuff<0, 1>, but the call to it is never reached.

A couple of options here:

1. Just start diagnosing in this scenario. The problem can be solved by replacing the if with if constexpr in modern C++ (this possibility didn't exist when the warning was added).
2. Don't diagnose immediately when we see a function template instantiation that recursively calls itself; instead, diagnose calls to that function that the CFG analysis thinks are reachable. (And apply that recursively if those calls are themselves from template instantiations.)

Option 2 seems like a lot of work, but potentially we could apply that treatment to all DiagRuntimeBehavior cases to suppress false-positives for instantiated-but-unused function templates. I suspect it's not worth the effort, and option 1 is the way to go.

[AaronBallman]

... where DoStuff<0, 0> does indeed recursively call itself, and is indeed instantiated by DoStuff<0, 1>, but the call to it is never reached.

We're already in an analysis-based warning, so it seems like we should have what we need: we could note that we want to issue the diagnostic there, and once we get to the end of the analysis for the function, check whether that location was ever actually reached before issuing the diagnostic.

I wasn't thinking we'd need to modify DiagRuntimeBehavior(), I was thinking we'd be basically re-using that logic (but without a second pass over the CFG). But I suspect it would still be somewhat involved because I think we'd have to refactor the reachability analysis to be more reusable.

[zygoloid]

... where DoStuff<0, 0> does indeed recursively call itself, and is indeed instantiated by DoStuff<0, 1>, but the call to it is never reached.

We're already in an analysis-based warning, so it seems like we should have what we need: we could note that we want to issue the diagnostic there, and once we get to the end of the analysis for the function, check whether that location was ever actually reached before issuing the diagnostic.

I think we may be talking about different things. DoStuff<0, 0> does indeed recursively call itself through a reachable call. So if we only check whether the recursive call location is reached from the entry of the function (which we already do -- the diagnostic checks whether every path from the entry of the function reaches a recursive call), we would produce a false positive diagnostic. The reason it's a false positive is not something that can be seen by analyzing DoStuff<0, 0> itself -- it's that DoStuff<0, 0> is only ever called from within unreachable code (in DoStuff<0, 1>).

[AaronBallman]

... where DoStuff<0, 0> does indeed recursively call itself, and is indeed instantiated by DoStuff<0, 1>, but the call to it is never reached.

We're already in an analysis-based warning, so it seems like we should have what we need: we could note that we want to issue the diagnostic there, and once we get to the end of the analysis for the function, check whether that location was ever actually reached before issuing the diagnostic.

I think we may be talking about different things.

You're right, we were!

DoStuff<0, 0> does indeed recursively call itself through a reachable call. So if we only check whether the recursive call location is reached from the entry of the function (which we already do -- the diagnostic checks whether every path from the entry of the function reaches a recursive call), we would produce a false positive diagnostic. The reason it's a false positive is not something that can be seen by analyzing DoStuff<0, 0> itself -- it's that DoStuff<0, 0> is only ever called from within unreachable code (in DoStuff<0, 1>).

I thought our CFG would track that int stuff = DoStuff<0, 1>(); is the entrypoint to the call graph, and so while DoStuff<0, 0> is instantiated, the CFG would have no edges calling DoStuff<0, 0> except within DoStuff itself, and those are never reachable. But the analsysis-based warnings are on a function-by-function basis, so when we'd analyze any instantiation of DoStuff, we'd analyze just the body of the call.

That said, "false positive" is a bit fuzzy with templates. There's not an instantiation of DoStuff<0, 0> that's dynamically reachable in that TU, but there's still an infinite recursion hiding there waiting for some other template instantiation to hit it later. So it's sort of a false positive (that TU doesn't hit the issue) and sort of a true positive (it's possible to hit the issue with a different call stack). I wonder if it would be reasonable to add something like -Wtemplated-infinite-recursion which users could selectively disable if they really want the recursion bomb to stay hidden?

[Alcaro]

One can also consider how easy it'd be to to fix the code to not emit warnings. For the given example, that'd be a simple if constexpr.

The current behavior was fine when implemented (the linked commit is 2013, if constexpr is C++17), but I'd say it's time to reconsider.