Why does the compiler require return type in the following lambdas-CodePudding

I am implementing recursive DFS as a lambda passing itself as a parameter. If I comment out the logic that checks if the current node has no children, I get build errors saying that the lambda is used before type deduction.

#include <vector>

int main() {
    int root;
    std::vector<std::vector<int>> graph;

    // ...
    // build the tree as adjacency list starting from root
    // ...

    auto dfs = [&graph](auto self, auto u) {
        // if (empty(graph[u])) {
        //     return;
        // }
        for (auto v : graph[u]) {
            self(self, v);
        }
    };

    dfs(dfs, root);
}

/usr/bin/g  -10 -std=c  20 -Wall -Wextra -Wshadow -pedantic -fdiagnostics-color=always -g -o main main.cpp
main.cpp: In instantiation of ‘main()::<lambda(auto:44, auto:45)> [with auto:44 = main()::<lambda(auto:44, auto:45)>; auto:45 = int]’:
main.cpp:66:18:   required from here
main.cpp:63:17: error: use of ‘main()::<lambda(auto:44, auto:45)> [with auto:44 = main()::<lambda(auto:44, auto:45)>; auto:45 = int]’ before deduction of ‘auto’
   63 |             self(self, v);
      |             ~~~~^~~~~~~~~

However, once I have that check-if-empty logic back, the code compiles with no issues.

Is that because in the latter case, the return statement gives the compiler a hint that the lambda returns void and therefore, its type is known at the time self(self, v) is called?

More broadly, where can I read and learn more about how compilers process lambda definitions to avoid relying on their error messages and know when it's necessary to declare the return type and when it's not?

CodePudding user response：

Yes, the return; statement is exactly what tells the compiler the return type of the lambda. In this example, the statement says the function return void.

Without knowing the return type, the call to self(self, v); is ill-formed, since you're effectively relying on auto being deduced without giving the compiler a way of figuring it out.

The language explicitly mentions this example in dcl.spec.auto#general-11:

If a variable or function with an undeduced placeholder type is named by an expression ([basic.def.odr]), the program is ill-formed. Once a non-discarded return statement has been seen in a function, however, the return type deduced from that statement can be used in the rest of the function, including in other return statements.

(emphasis mine), and provides a simpler version of the problem in your code:

auto sum(int i) {   
  if (i == 1)
    return i;              // sum's return type is int   
  else
    return sum(i-1) i;     // OK, sum's return type has been deduced 
}