[clang] seems like bug with return type deduction in case of recursive function (works in GCC)

[vampyrofangclub]

Here is an example

struct Node {
  int value;
  Node* left;
  Node* right;
};

bool parse(const char*);
Node* parsePrimaryExpr();

auto parseMulExpr(auto node) {
  if (node == nullptr) node = parsePrimaryExpr();
  if (!parse("*")) return node;
  return parseMulExpr(new Node{.left = node, .right = parsePrimaryExpr()});
}

int main(){
  parseMulExpr((Node*)nullptr);
}

Clang gives this error

<source>:13:10: error: function 'parseMulExpr<Node *>' with deduced return type cannot be used before it is defined
   13 |   return parseMulExpr(new Node{.left = node, .right = parsePrimaryExpr()});
      |          ^
<source>:10:6: note: 'parseMulExpr<Node *>' declared here
   10 | auto parseMulExpr(auto node) {
      |      ^
1 error generated.
Compiler returned: 1

https://godbolt.org/z/7WTYYben5

[llvmbot]

@llvm/issue-subscribers-clang-frontend

Author: Богдан (vampyrofangclub)

Here is an example ```cpp struct Node { int value; Node* left; Node* right; };

bool parse(const char*);
Node* parsePrimaryExpr();

auto parseMulExpr(auto node) {
if (node == nullptr) node = parsePrimaryExpr();
if (!parse("*")) return node;
return parseMulExpr(new Node{.left = node, .right = parsePrimaryExpr()});
}

int main(){
parseMulExpr((Node*)nullptr);
}

Clang gives this error

<source>:13:10: error: function 'parseMulExpr<Node *>' with deduced return type cannot be used before it is defined
13 | return parseMulExpr(new Node{.left = node, .right = parsePrimaryExpr()});
| ^
<source>:10:6: note: 'parseMulExpr<Node *>' declared here
10 | auto parseMulExpr(auto node) {
| ^
1 error generated.
Compiler returned: 1

https://godbolt.org/z/7WTYYben5
</details>

[shafik]

This looks like a clang bug to me: https://godbolt.org/z/4dr7r3h3z

As per dcl.spec.auto p11 once we have seen a non-discarded return statement where the type was deduced we should be good.

If we use what should be the equivalent templated version it is fine:

template <typename T>
auto parseMulExpr2(T node) {
  if (node == nullptr) node = parsePrimaryExpr();
  if (!parse("*")) return node;
  return parseMulExpr2<T>(new Node{.left = node, .right = parsePrimaryExpr()});
}

[shafik]

CC @Fznamznon if you are interested

[Fznamznon]

As per dcl.spec.auto p11 once we have seen a non-discarded return statement where the type was deduced we should be good.

There is also https://eel.is/c++draft/dcl.spec.auto#general-12 which says that for templated function return type deduction only happens when the definition is instantiated, that is the reason why return type is not deduced by clang atm:

llvm-project/clang/lib/Sema/SemaStmt.cpp

Line 3806 in 1127656

// C++1y [dcl.spec.auto]p12:

.
So, is the error actually a bug?

Another problem is, even if we remove this early-exit, the function's type will be updated, but there is another problem. Recursive call to the function causes its implicit instantiation, but template instantiator doesn't seem to care about function type, it only cares about function TypeSourceInfo which is never updated, and I'm not sure there is a correct way to update it. So, it creates a FunctionDecl with auto type which is neither deduced nor dependent.
cc @erichkeane , @cor3ntin in case you might know how it is done and whether it should.

Later on, when we check that function type is deduced, try to deduce and fail because function is not yet fully defined.

llvm-project/clang/lib/Sema/SemaTemplateDeduction.cpp

Line 5164 in ea5de60

if (FD->getTemplateInstantiationPattern()) {

Regarding why templated case works:

template <typename T>
auto parseMulExpr2(T node) {
  if (node == nullptr) node = parsePrimaryExpr();
  if (!parse("*")) return node;
  return parseMulExpr2<T>(new Node{.left = node, .right = parsePrimaryExpr()});
}

This only works because recursive call in the last return statement is considered as dependent due to presence of <T> and because of that there is no semantic analysis performed before function's instantiation. In the original example it is not considered dependent, so it goes all the way to the error. Remove <T> to see the same error.

That also simplifies the reproducer - https://godbolt.org/z/4voeehxjn.

So, not sure how this can be fixed atm, help is appreciated.

[cor3ntin]

llvm-project/clang/lib/Sema/SemaStmt.cpp

Line 3806 in 1127656

// C++1y [dcl.spec.auto]p12:

Maybe we need to check that we are not in the middle of performing instantantiation in addition of this check (and if we are, we should not return)

[shafik]

llvm-project/clang/lib/Sema/SemaStmt.cpp

Line 3806 in 1127656

// C++1y [dcl.spec.auto]p12:

Maybe we need to check that we are not in the middle of performing instantantiation in addition of this check (and if we are, we should not return)

@zygoloid does this sound correct to you?

[zygoloid]

Per https://eel.is/c++draft/temp.dep.expr#3, the recursive call is not type-dependent, so we need a type for it in the template instantiation. That seems like a bug in the language rules to me.

I think the proper behavior here is probably that we should treat a call to a templated function whose definition encloses the call and whose return type contains a placeholder type as being type-dependent. From an implementation standpoint, I think it would add complexity to allow the template to contain a DeclRefExpr that denotes a template specialization with a non-deduced return type -- that'd be a new special case that consumers of the AST would need to deal with. Instead, I think it'd be better to model this case as an unresolved lookup expression -- that is, for overload resolution to treat the overload set itself as being dependent if the best viable function is a templated function that's currently being defined, even though we know which function will be called.