Document number P0792R0
Date 2017-10-10
Reply-to Vittorio Romeo <vittorio.romeo@outlook.com>
Audience Library Evolution Working Group
Project ISO JTC1/SC22/WG21: Programming Language C++

function_ref: a non-owning reference to a Callable

Abstract

This paper proposes the addition of function_ref<R(Args...)> to the Standard Library, a "vocabulary type" for non-owning references to Callable objects.

Table of contents

Overview

Since the advent of C++11 writing more functional code has become easier: functional programming patterns and idioms have become powerful additions to the C++ developer's toolbox. "Higher-order functions" are one of the key ideas of the functional paradigm - in short, they are functions that take functions as arguments and/or return functions as results.

The need of referring to an existing Callable object comes up often when writing functional C++ code, but the Standard Library unfortunately doesn't provide a flexible facility that allows to do so. Let's consider the existing utilities:

This paper proposes the introduction of a new function_ref class template, which is akin to std::string_view. This paper describes function_ref as a non-owning lightweight wrapper over any Callable object.

Motivating example

Here's one example use case that benefits from higher-order functions: a retry(n, f) function that attempts to synchronously call f up to n times until success. This example might model the real-world scenario of repeatedly querying a flaky web service.

struct payload { /* ... */ };

// Repeatedly invokes `action` up to `times` repetitions.
// Immediately returns if `action` returns a valid `payload`.
// Returns `std::nullopt` otherwise.
std::optional<payload> retry(std::size_t times, /* ????? */ action);

The passed-in action should be a Callable which takes no arguments and returns std::optional<payload>. Let's see how retry can be implemented with various techniques:

Impact on the Standard

This proposal is a pure library extension. It does not require changes to any existing part of the Standard.

Alternatives

The only existing viable alternative to function_ref currently is std::function + std::reference_wrapper. The Standard guarantees that when a std::reference_wrapper is used to construct/assign to a std::function no allocations will occur and no exceptions will be thrown.

Using std::function for non-owning references is suboptimal for various reasons.

  1. The ownership semantics of a std::function are unclear - they change depending on whether or not the std::function was constructed/assigned with a std::reference_wrapper.

    void foo(std::function<void()> f);
    // `f` could be referring to an existing Callable, or could own one.
    
    void bar(function_ref<void()> f);
    // `f` unambiguously is a non-owning reference to an existing Callable.
  2. This technique doesn't work with temporaries. This is a huge drawback as it prevents stateful temporary lambdas from being passed as callbacks.

    void foo(std::function<void()> f);
    
    int main()
    {
        int x = 0;
        foo(std::ref([&x]{ ++x; }); // does not compile
    }

    The code above doesn't compile, as std::ref only accepts non-const lvalue references (additionally, std::cref is explicitly deleted for rvalue references). Avoiding the use of std::ref breaks the guarantee that f won't allocate or throw an exception on construction.

  3. std::function is harder for compilers to optimize compared to the proposed function_ref. This is true due to various reasons:

    Rough benchmarks comparing the generated assembly of a std::function parameter and a function_ref parameter against a template parameter show that:

    A description of the benchmarking techniques used and the full results can be found on my article "passing functions to functions" 1.

Synopsis

namespace std
{
    template <typename>
    class function_ref; /* undefined */

    template <typename R, typename... Args>
    class function_ref<R(Args...)>
    {
    public:
        constexpr function_ref() noexcept;
        constexpr function_ref(std::nullptr_t) noexcept;
        constexpr function_ref(const function_ref&) noexcept;

        template <typename F>
        constexpr function_ref(F&&) noexcept;

        constexpr function_ref& operator=(const function_ref&) noexcept;
        constexpr function_ref& operator=(std::nullptr_t) noexcept;

        template <typename F>
        constexpr function_ref& operator=(F&&) noexcept;

        constexpr void swap(function_ref&) noexcept;

        constexpr explicit operator bool() const noexcept;

        R operator()(Args...) const;
    };

    template <typename R, typename... Args>
    constexpr void swap(function_ref<R(Args...)>&, function_ref<R(Args...)>&) noexcept;

    template <typename R, typename... Args>
    constexpr bool operator==(const function_ref<R(Args...)>&, std::nullptr_t) noexcept;

    template <typename R, typename... Args>
    constexpr bool operator==(std::nullptr_t, const function_ref<R(Args...)>&) noexcept;

    template <typename R, typename... Args>
    constexpr bool operator!=(const function_ref<R(Args...)>&, std::nullptr_t) noexcept;

    template <typename R, typename... Args>
    constexpr bool operator!=(std::nullptr_t, const function_ref<R(Args...)>&) noexcept;

    template <typename R, typename... Args>
    function_ref(R (*)(Args...)) -> function_ref<R(Args...)>;

    template <typename F>
    function_ref(F) -> function_ref</* deduced if possible */>;
}

Specification

template <typename R, typename... Args>
constexpr function_ref<R(Args...)>::function_ref() noexcept;


template <typename R, typename... Args>
constexpr function_ref<R(Args...)>::function_ref(std::nullptr_t) noexcept;


template <typename R, typename... Args>
constexpr function_ref<R(Args...)>::function_ref(const function_ref& rhs) noexcept;


template <typename R, typename... Args>
template <typename F>
constexpr function_ref<R(Args...)>::function_ref(F&& f) noexcept;


template <typename R, typename... Args>
constexpr function_ref& function_ref<R(Args...)>::operator=(const function_ref& rhs) noexcept;


template <typename R, typename... Args>
constexpr function_ref& function_ref<R(Args...)>::operator=(std::nullptr_t) noexcept;


template <typename R, typename... Args>
template <typename F>
constexpr function_ref& function_ref<R(Args...)>::operator=(F&&) noexcept;


template <typename R, typename... Args>
constexpr void function_ref<R(Args...)>::swap(function_ref& rhs) noexcept;


template <typename R, typename... Args>
constexpr explicit function_ref<R(Args...)>::operator bool() const noexcept;


template <typename R, typename... Args>
R function_ref<R(Args...)>::operator()(Args... xs) const;


template <typename R, typename... Args>
constexpr void swap(function_ref<R(Args...)>& lhs, function_ref<R(Args...)>& rhs) noexcept;


template <typename R, typename... Args>
constexpr bool operator==(const function_ref<R(Args...)>& fr, std::nullptr_t) noexcept;


template <typename R, typename... Args>
constexpr bool operator==(std::nullptr_t, const function_ref<R(Args...)>& fr) noexcept;


template <typename R, typename... Args>
constexpr bool operator!=(const function_ref<R(Args...)>& fr, std::nullptr_t) noexcept;


template <typename R, typename... Args>
constexpr bool operator!=(std::nullptr_t fr, const function_ref<R(Args...)>&) noexcept;

Existing practice

Many facilities similar to function_ref exist and are widely used in large codebases. Here are some examples:

Additionally, combining results from GitHub searches (excluding "llvm" and "folly") for "function_ref" 10, "function_view" 11, "FunctionRef" 12, and "FunctionView" 13 roughly shows more than 2800 occurrences.

Possible issues

Accepting temporaries in function_ref's constructor is extremely useful in the most common use case: using it as a function parameter:

void foo(function_ref<void()>);

int main()
{
    foo([]{ });
}

The usage shown above is completely safe: the temporary closure generated by the lambda expression is guarantee to live for the entirety of the call to foo. Unfortunately, this also means that the following code snippet will result in undefined behavior:

int main()
{
    function_ref<void()> f{[]{ }};
    // ...
    f(); // undefined behavior
}

The above closure is a temporary whose lifetime ends after the function_ref constructor call. The function_ref will store an address to a "dead" closure - invoking it will produce undefined behavior 14. As an example, AddressSanitizer detects an invalid memory access in this gist 15. Note that this problem is not unique to function_ref: the recently standardized std::string_view 16 has the same problem 17.

I strongly believe that accepting temporaries is a "necessary evil" for both function_ref and std::string_view, as it enables countless valid use cases. The problem of dangling references has been always present in the language - a more general solution like Herb Sutter and Neil Macintosh's lifetime tracking 18 would prevent mistakes without limiting the usefulness of view/reference classes.

Open questions

Below are some unanswered questions for which I kindly ask guidance from members of the commitee and readers of this paper.

Bikeshedding

The name function_ref is subject to bikeshedding. Here are some other potential names:

Acknowledgments

Thanks to Eric Niebler, Tim van Deurzen, and Alisdair Meredith for providing very valuable feedback on earlier drafts of this proposal.

References


  1. https://vittorioromeo.info/index/blog/passing_functions_to_functions.html#benchmark---generated-assembly

  2. http://llvm.org/doxygen/classllvm_1_1function__ref_3_01Ret_07Params_8_8_8_08_4.html

  3. https://github.com/search?q=org%3Allvm-mirror+function_ref&type=Code

  4. https://github.com/facebook/folly

  5. https://github.com/facebook/folly/blob/master/folly/Function.h#L743-L824

  6. https://github.com/search?q=org%3Afacebook+FunctionRef&type=Code

  7. https://www.gnu.org/software/gdb/

  8. https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;a=blob;f=gdb/common/function-view.h

  9. https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;a=blob;f=gdb/common/function-view.h

  10. https://github.com/search?utf8=%E2%9C%93&q=function_ref+AND+NOT+llvm+AND+NOT+folly+language%3AC%2B%2B&type=Code

  11. https://github.com/search?utf8=%E2%9C%93&q=function_view+AND+NOT+llvm+AND+NOT+folly+language%3AC%2B%2B&type=Code

  12. https://github.com/search?utf8=%E2%9C%93&q=functionref+AND+NOT+llvm+AND+NOT+folly+language%3AC%2B%2B&type=Code

  13. https://github.com/search?utf8=%E2%9C%93&q=functionview+AND+NOT+llvm+AND+NOT+folly+language%3AC%2B%2B&type=Code

  14. http://foonathan.net/blog/2017/01/20/function-ref-implementation.html

  15. https://gist.github.com/SuperV1234/a41eb1c825bfbb43f595b13bd4ea99c3

  16. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3762.html

  17. http://foonathan.net/blog/2017/03/22/string_view-temporary.html

  18. https://github.com/isocpp/CppCoreGuidelines/blob/master/docs/Lifetimes%20I%20and%20II%20-%20v0.9.1.pdf

  19. http://wg21.link/p0045r1

  20. http://wg21.link/N4159