function_ref: a non-owning reference to a Callable

Document #: P0792R5
Date: 2019-10-06
Project: Programming Language C++
Library Working Group (LWG)
Reply-to: Vittorio Romeo
<>

1 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.

2 Changelog and polls

2.1 R5

2.2 R4

2.3 R3

2.3.1 Polls

Do we want to remove the precondition that !f must hold when function_ref is constructed/assigned from an instance of std::function f?

SF F N A SA

1 8 1 0 0

Should function_ref::operator() be unconditionally const-qualified?

SF F N A SA

8 2 0 1 0

Should function_ref fully support the Callable concept at the potential cost of sizeof(function_ref) > sizeof(void(*)()) * 2?

SF F N A SA

6 4 0 0 0

2.4 R2

2.4.1 Polls

We want to prevent construction of std::function from std::function_ref (but not other callable-taking things like std::bind).

SF F N A SA

0 0 4 8 0

We want to revise the paper to include discussion of ref-qualified callables.

SF F N A SA

0 3 6 6 0

Forward paper as-is to LWG for C++20?

SF F N A SA

3 9 3 0 0

2.5 R1

2.5.1 Polls

2.5.1.1 Semantics: pointer versus reference

option 1

function_ref, non-nullable, not default constructible

option 2

function_ptr, nullable, default constructible

We want 1 and 2

SF F N A SA

1 2 8 3 6

ref vs ptr

SR R N P SP

6 5 2 5 0

The poll above clearly shows that the desired direction for function_ref is towards a non nullable, non default-constructible reference type. This revision (P0792R2) removes the “empty state” and default constructibility from the proposed function_ref. If those semantics are required by users, they can trivially wrap function_ref into an std::optional<function_ref</* ... */>>.

2.5.1.2 target and target_type

We want target and target-type (consistent with std::function) if they have no overhead

Unanimous consent

We want target and target-type (consistent with std::function) even though they have overhead

SF F N A SA

0 0 1 9 4

I am not sure whether target and target_type can be implemented without introducing overhead. I seek the guidance of the committee or any interested reader to figure that out. If they require overhead, I agree with the poll: they will be left out of the proposal.

3 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.

4 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:

5 Impact on the Standard

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

6 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:

    • std::function can allocate and/or throw exceptions on construction and/or assigment.

    • std::function might use SBO, which could require an additional branch during construction/assignment, make inlining more difficult, and unnecessarily increase memory usage.

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

    • std::function, on average, generates approximately 5x more assembly than a template parameter.

    • function_ref, on average, generates approximately 1.5x more assembly than a template parameter.

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

7 Changes to <functional> header

Add the following to [functional.syn]:

namespace std
{
    // ...

    template <typename Signature> class function_ref;

    template <typename Signature>
    void swap(function_ref<Signature>& lhs, function_ref<Signature>& rhs) noexcept;

    // ...
}

8 Class synopsis

Create a new section “Class template function_ref”, [functionref]" with the following:

namespace std
{
    template <typename Signature>
    class function_ref
    {
        void* erased_object; // exposition only

        R(*erased_function)(Args...); // exposition only
        // `R`, and `Args...` are the return type, and the parameter-type-list,
        // of the function type `Signature`, respectively.

    public:
        function_ref(const function_ref&) noexcept = default;

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

        function_ref& operator=(const function_ref&) noexcept = default;

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

        void swap(function_ref&) noexcept;

        R operator()(Args...) const noexcept(see below);
        // `R` and `Args...` are the return type and the parameter-type-list
        // of the function type `Signature`, respectively.
    };

    template <typename Signature>
    void swap(function_ref<Signature>&, function_ref<Signature>&) noexcept;

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

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

    template <typename F>
    function_ref(F) -> function_ref<see below>;
}
  1. function_ref<Signature> is a Cpp17CopyConstructible and Cpp17CopyAssignable reference to an Invocable object with signature Signature.

  2. function_ref<Signature> is a trivially copyable type.

  3. The template argument Signature shall be a non-volatile-qualified function type.

9 Specification

template <typename F>
function_ref(F&& f);


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


void swap(function_ref& rhs) noexcept;


R operator()(Args... xs) noexcept(see below);


template <typename F>
function_ref(F) -> function_ref<see below>;


template <typename Signature>
void swap(function_ref<Signature>& lhs, function_ref<Signature>& rhs) noexcept;


10 Feature test macro

Append to §17.3.1 General [support.limits.general]’s Table 36 one additional entry:

Macro name
Value
Headers
__cpp_lib_function_ref 201811L <functional>

11 Example implementation

The most up-to-date implementation, created by Simon Brand, is available on GitHub/TartanLlama/function_ref.

An older example implementation is available here on GitHub/SuperV1234/Experiments.

12 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,”10function_view,”11FunctionRef,”12 and “FunctionView13 roughly shows more than 2800 occurrences.

13 Possible issues

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

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_view16 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 tracking18 would prevent mistakes without limiting the usefulness of view/reference classes.

14 Bikeshedding

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

15 Acknowledgments

Thanks to Agustín Bergé, Dietmar Kühl, Eric Niebler, Tim van Deurzen, and Alisdair Meredith for providing very valuable feedback on earlier drafts of this proposal.

16 Annex: previously open questions

17 Annex: controversial design decisions

17.1 Size of function_ref

sizeof(function_ref) is required to be maximum sizeof(void*) * 2. This design choice was made as it makes function_ref more lightweight and more likely to be passed in registers. There also has been vocal opposition to the function_ref having a size greater than sizeof(void*) * 2. The consequence of this is that construction/assignment from a pointer to member function will be UB unless the PMF itself outlives the function_ref. E.g.

function_ref<void(const Foo&)> fr = &Foo::f;
    // Points to the temporary `&Foo::f` instance.

fr(); // (0)
    // Undefined behavior, as the temporary `&Foo::f` is dead.

This was previously discussed by LEWG, and there was consensus to not make (0) well-defined as that would require function_ref to be bigger than two void* pointers.

17.2 Lifetime of pointers to function

In the case of a pointer to function, even though it could be possible to avoid undefined behavior, the current design choice is to have the exact same behavior as with PMFs to avoid inconsistency. E.g.

void f(const Foo&);

function_ref<void(const Foo&)> fr = &f;
    // Points to the temporary `&f` instance.

fr(); // (0)
    // Undefined behavior, as the temporary `&f` is dead.

Allowing (0) to be well-defined behavior would be possible without increasing the size of function_ref, but would create inconsistency with the PMF case above which would harm teachability of function_ref and potentially lead to bugs. This was discussed in LEWG and there was consensus to proceed with this design.

17.3 Assignment operator

The main use case for function_ref is to be used as a function parameter, yet it exposes an assignment operator. Safe use cases for the assignment operator that do not introduce UB are rare, but some readers of this proposals have reported having valid use cases for an assignment operator.

17.4 reference_wrapper unwrapping

According to a member of the committee, not unwrapping std::reference_wrapper when constructing/assigning-to function_ref causes a usability problem. There might be a performance penalty to pay due to the double indirection, and a change in semantics depending on whether or not the std::reference_wrapper is unwrapped. E.g.

auto l0 = []{ std::cout << "l0\n"; };
auto l1 = []{ std::cout << "l1\n"; };

std::reference_wrapper rw{std::ref(l0)};
function_ref<void()> fr(rw); // Points to `rw` itself.

fr(); // Prints out `l0`.

rw = l1;

fr(); // Prints out `l1`.

This problem was discussed in LEWG at the Rapperswil meeting, and there was unanimous dissent to special-casing std::reference_wrapper.

18 Annex: existing practice survey

The following types have been surveyed: folly::FunctionRef, llvm::function_ref, and gdb::function_view to check how often they were used and in which circumstances. Below are the results:

Conclusions:

19 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↩︎