Strange undefined behaviour with tricky lambda expression

Question

I've been struggling against a problem with lambda expressions that was jeopardizing a project of mine. I have found a solution, but I would like to understand exactly how and why it works, and if it is reliable.

#include <iostream>
#include <functional>
#include <unordered_map>

typedef std::function<const int&(const int&)> Callback;

int f(int i, Callback callback) {
    if (i <= 2) return 1;
    return callback(i-1) + callback(i-2);
}

int main(void) {

    std::unordered_map<int, int> values;

    Callback callback = [&](const int& i) {
        if (values.find(i) == values.end()) {
            int v = f(i, callback);
            values.emplace(i, v);
        }
        return values.at(i);
    };

    std::cout << f(20, callback) << std::endl;

    return 0;

}

I know this is a crazy way to compute the 20th Fibonacci number, but it is the most compact SSCCE I was able to elaborate.

If I compile the code above with g++ -O0 and I execute the program, I get 6765, which is actually the 20th Fibonacci number. If I compile with -O1, -O2 or -O3 I get 262144, which is rubbish.

If I profile the program with Valgrind (compiling with -O0 -g), I get Conditional jump or move depends on uninitialised value(s) on the line std::cout << f(20, callback) << std::endl; but the stack trace doesn't say anything useful.

I don't know why I ended up with this:

Callback callback = [&](const int& i) -> const int& {

With this little modification, everything works as expected compiling with any optimization level, and Valgrind reports no issues.

Can you help me understand what's going on?

Answer 1

Without the -> const int& the return type of the lambda is int. Since the return type of Callback is const int&, callback ends up returning a reference to the temporary it uses to hold the return value of the lambda expression. Undefined behavior.

For this simple example, the easy fix is to not use references at all (Example at Coliru), but I assume your real code is handling more heavyweight objects than int. It's unfortunate that std::function isn't specified to warn when you assign a function that returns a non-reference to a std::function whose return type is a reference.

Answer 2

Casey's answer is spot on. I would just like to add something. (It seens that adding on top of Casey's good answers is becoming a common behavior of mine ;-).) Actually, my remark is on gd1's comment on Casey's post.

I guess the OP is using g++ -std=c++1y because, in C++11, the returned type of the lambda shown there is set to void. Indeed, the compiler deduces the returned type only if the lambda's body contains a single return statement. Otherwise, the compiler assumes this type is void. In C++14 automatic deduction for returned type (not only for lambdas but also for functions) is more powerful .

As one can see n3582 -- the paper which was approved for C++14 and for which gcc's implementation is a reference -- states that

plain auto never deduces to a reference, [...]

In the OP's example the returned type is int (not const int&). I believe one can use -> decltype(auto) to have the automatic deduction yielding a reference.