foonathan::blog()

Thoughts from a C++ library developer.

Implementing function_view is harder than you might think

I’ve recently read this blog post by Vittorio Romeo. He talks about various ways to pass a function (callback, comparator for algorithm, etc.) to another function. One of them is function_view. function_view is a lightweight std::function: it should be able to refer to any callable with a given signature. But unlike std::function it does not own the callable, just refers to it. This allows a much more efficient implementation.

In this post he presented one. But his has a flaw, that can bite you very easily.


Advertisement

In his defense: He is aware of the problem.

The straightforward implementation

His one was like this:

template <typename TSignature>
class function_view;

template <typename TReturn, typename... TArgs>
class function_view<TReturn(TArgs...)> final
{
private:
    using signature_type = TReturn(void*, TArgs...);

    void* _ptr;
    TReturn (*_erased_fn)(void*, TArgs...);

public:
    template <typename T, typename = std::enable_if_t<
                              std::is_callable<T&(TArgs...)>{} &&
                              !std::is_same<std::decay_t<T>, function_view>{}>>
    function_view(T&& x) noexcept : _ptr{(void*)std::addressof(x)}
    {
        _erased_fn = [](void* ptr, TArgs... xs) -> TReturn {
            return (*reinterpret_cast<std::add_pointer_t<T>>(ptr))(
                std::forward<TArgs>(xs)...);
        };
    }

    decltype(auto) operator()(TArgs... xs) const
        noexcept(noexcept(_erased_fn(_ptr, std::forward<TArgs>(xs)...)))
    {
        return _erased_fn(_ptr, std::forward<TArgs>(xs)...);
    }
};

For more details look at the post.

This is very similar to the one LLVM uses. It simply stores a void* pointer to the callable passed in the constructor, plus a callback that casts the pointer back to the concrete type and invokes it. The callable is created in the constructor, where the type information is still known. This is a common trick for type erasure.

So far, so flawed.

Note that the constructor accepts a forwarding reference. This allows the following usage as a function parameter:

void func(function_view<int()> generator);

func([] { return 42; });

The lambda passed as argument is actually a temporary, so it would not bind to an lvalue reference. But the constructor uses a forwarding reference, so it works.

However, this also works:

function_view<int()> invoke_later([] { return 42; });

auto val = invoke_later(); // UB! UB! UB!

Again, the lambda is a temporary, whose address will be taken. Storing the address of a temporary is not a good idea, as the temporary is only temporary.

To prevent these kinds of errors, the standard does not allow taking the address of an rvalue reference. But the forwarding reference doesn’t care about such safety precautions.

And as the temporary is only temporary, it will be destroyed at the end of the full expression containing it.

I.e. the semicolon.

So now we have function_view viewing an already destroyed temporary. Accessing destroyed objects is not something anyone should do, calling the operator() of a lambda is no exception.

function_view as parameter is perfectly fine, but as soon as we use them outside of that, we can easily shoot ourselves in the foot if we’re not careful. Shooting yourself in the foot is more of a C thing, in C++ we strive to make interfaces that are easy to use correctly and hard to use incorrectly.

Writing the above code isn’t hard, it’s what function_view should do!

So let’s write a function_view that is safer to use, where you can’t easily shoot yourself in the foot.

Step 0: Rename to function_ref

Let’s rename function_view to function_ref.

This is is more consistent with the other references I’ve written.

Update: There is a semantic difference I haven’t realized at the time of writing between a view and ref. function_view is intended for parameters it is a “view” on a function. As such it makes sense to bind to rvalues. function_ref on the other hand is designed for persistent storage of a function reference (i.e. class member). This requires slightly difference semantics - like, no rvalues, which lead to some confusion.

Step 1: Take an lvalue reference

The easiest fix is to remove the forwarding reference and use an lvalue reference instead. This will not bind to rvalues, so we can’t pass in temporaries, preventing errors like made above.

However, this still can result in errors:

some_class obj;
{
    auto lambda = [] { return 42; };
    obj.func(lambda); // what if func stores the reference...
}
obj.other_func(); // ... and use it here?

It isn’t really clear that the function will take a reference to the lambda, just from looking at the code.

Update: This problem isn’t inherit to function_ref, it happens all the time with plain old references as well. It is a shame that it isn’t obvious if a function takes a reference to something on the call.

So let’s make another change and make the constructor explicit:

auto lambda = ;
func(lambda); // error!
func(function_ref<int()>(lambda)); // ok

Aha!

Now it is obvious that we’re creating a reference to the lambda. Whenever I use something that contains the word reference, an alarm goes off in my head and I think about object lifetime.

That’s one reason why I renamed it.

And this should be the case for every C++ programmer who ever run into lifetime issues.

If you want more safety, consider Rust.

Step 2: Also store a function pointer

While we have a sensible solution for classes with user-defined operator(), where we shouldn’t pass a temporary in the first place, this seems silly:

int generator();

auto fptr = &generator;
func(function_ref<int()>(fptr));

The function_ref references the function pointer, which refers to the function, not the function directly. Furthermore, it also depends on the lifetime of the function pointer, which is just weird.

So let’s support referring to functions directly. The way one refers to a function is with - you guessed it - a function pointer. So function_ref needs to store a function pointer. But for functors it needs void*. We need a variant.

However, as both are trivial types, simply using std::aligned_union works as well:

template <typename Signature>
class function_ref;

template <typename Return, typename... Args>
class function_ref<Return(Args...)>
{
    using storage  = std::aligned_union_t<void*, Return (*)(Args...)>;
    using callback = Return (*)(const void*, Args...);

    storage  storage_;
    callback cb_;

    void* get_memory() noexcept
    {
        return &storage_;
    }

    const void* get_memory() const noexcept
    {
        return &storage_;
    }

public:
    using signature = Return(Args...);

    function_ref(Return (*fptr)(Args...))
    {
        using pointer_type        = Return (*)(Args...);

        DEBUG_ASSERT(fptr, detail::precondition_error_handler{},
                     "function pointer must not be null");
        ::new (get_memory()) pointer_type(fptr);

        cb_ = [](const void* memory, Args... args) {
            auto func  = *static_cast<const pointer_type*>(memory);
            return func(static_cast<Args>(args)...);
        };
    }

    template <typename Functor,
              typename = HERE BE SFINAE> // disable if Functor not a functor
    explicit function_ref(Functor& f)
    : cb_([](const void* memory, Args... args) {
          using ptr_t = void*;
          auto  ptr   = *static_cast<const ptr_t*>(memory);
          auto& func  = *static_cast<Functor*>(ptr);
          // deliberately assumes operator(), see further below
          return static_cast<Return>(func(static_cast<Args>(args)...));
      })
    {
        ::new (get_memory()) void*(&f);
    }

    Return operator()(Args... args) const
    {
        return cb_(get_memory(), static_cast<Args>(args)...);
    }
};

The static_casts are needed, so that rvalues are properly moved. I’ll also spare you the SFINAE details, just assume an implementation with concepts, or take a look at the appendix.

We now create the function pointer/regular pointer in the aligned union, the callback gets the raw memory of the storage as parameter, and needs to extract the stored pointer. It’s a little bit awkward, but works.

Now we can store a function pointer directly, allowing:

func(&generator);

The constructor is also not explicit, because there is now lifetime issue: a function lives long enough.

And as a bonus, this code also works:

func([] { return 42; });

A lambda that doesn’t capture anything is implicitly convertible to a function pointer. And the referred function lives long enough so there is no temporary issue!

It’s perfect and I should have stopped there.

However, there is one thing that would be nice: implicit conversions.

Step 3: Enable implicit conversions

If you have a function_ref with signature void(const char*), it might be nice to refer to a function taking std::string. Or with signature void(foo), you might want to allow a function with any return value and simply discard it. And if you have a functor, this already works if the SFINAE in the constructor is carefully crafted (spoiler: it is).

And that’s also why the static_cast<Return> is used, to discard any return value and convert to void.

But this does not work for the function pointer constructor. A function pointer void(*)(std::string) is not implicitly convertible to void(*)(const char*), even though const char* is implicitly convertible to std::string.

We need a second constructor accepting any function pointer:

template <typename Return2, typename ... Args2, typename = MOAR SFINAE>
function_ref(Return2(*)(Args2...))
{
    
}

But the aligned_union is only big enough for void* and Return(*)(Args...).

Is it guaranteed that you can then store a function pointer in there?

No.

You’re beginning to realize why I should have stopped at step 2, aren’t you?

However, §5.2.10/6 guarantees that you can convert a function pointer of signature A to a function pointer of signature B and back to A without changing the value.

This does not necessarily mean that they have the same size, apparently.

So we can reinterpret_cast the function pointer to Return(*)(Args...), construct that in the storage and set the callback, so it reads a function pointer of Return(*)(Args...) from the storage, reinterpret_cast that to Return2(*)(Args2...) and calls that.

Implementation is left for imagination.

So now this code works:

short generate();

function_ref<int()> ref(&generate);

And this code works:

function_ref<int()> ref([]{ return 42; });

However, this one does not:

function_ref<int()> ref([]{ return short(42); });

Ugh.

Why, you ask? Well, we have three constructors:

function_ref(Return (*fptr)(Args...));

// participates in overload resolution iff signature is compatible
template <typename Return2, typename ... Args2, typename = MOAR SFINAE>
function_ref(Return2(*)(Args2...))

// participates in overload resolution iff Functor has compatible signature
template <typename Functor,
          typename = HERE BE SFINAE> 
explicit function_ref(Functor& f)

The first overload is not viable as the implicit conversion of the lambda is to short(*)() not int(*)(). The final overload is not viable as it is a temporary. And the second overload is not viable as templates do not allow implicit conversions of the argument!

We need a fourth overload taking const Functor& f that only participates in overload resolution if Functor is implicitly convertible to a function pointer of matching signature. We also need to ensure that the overload taking Functor& f is not considered for functors convertible to function pointers, otherwise this code:

function_ref<int()> ref([]{ return short(42); });
// ref stores function pointer

and this code

auto lambda = []{ return short(42); };
function_ref<int()> ref(lambda);
// ref stores pointer to lambda

would have different meanings.

I’ll spare you the gory details here - again, information about SFINAE can be found in the end.

A word about member function pointers

The function_ref implementation presented here does not allow member function pointers, unlike std::function. The reason is simple: member function pointers are weird.

While we could easily change the callback for the general functor case to use std::invoke() instead of simply calling with operator(), and thus support member function pointers weird calling syntax of (first_arg.*fptr)(other_args...), this would lead to inconsistency.

We’ve implemented special support for function pointers by storing them directly. For consistency we would also need to store member function pointers directly, to give them the same special treatment.

However, unlike function pointers, member pointers are not necessarily the same size as void*. But in the unlikely case that someone wants to store a member pointer in function_ref, we’d need to have space for it, so the object is blown up.

And the problems don’t end there. We need to find some definition for “compatible” member function pointer. A signature void(T&, Args...) must allow void(T::*)(Args...) and void(T::*)(Args...) &, but not void(T::*)(Args...) &&, but the other way ‘round for T&&, plus all const/volatile combinations etc. Also if we have void(std::shared_ptr<T>, Args...), should we allow void(T::*)(Args...), and dereference the first argument implicitly or only void(std::shared_ptr<T>::*)(Args...)?

And even if we’ve implemented all that, what about implicit conversions?

The standard does not guarantee that you can freely cast between member function pointers, precisely because they all have different sizes depending on the class etc. So how do we know the space for them all?

All that is just a lot of implementation hassle that is simply not worth it, especially with lambdas. If you want a member function, just use a lambda:

function_ref<void(T&)> ref([](T& obj){ obj.foo(); });

Advertisement

Conclusion

The function_ref implementation presented here is more safer to use than the naive function_view, as it helps preventing dangling pointers, by only allowing lvalue references. In order to keep the flexibility it can also store a function pointer directly, this allows passing lambda functions or regular functions.

The full implementation can be found as part of my type_safe library, the documentation of it here. As of now type_safe also provides object_ref - a non-null pointer to an object, and array_ref - a reference to an array.

Appendix: SFINAE

The function_ref implementation has three templated constructors which all need to be conditionally disabled sometimes:

  • the templated function pointer constructor should only take function signatures compatible with the one of the function_ref
  • the const Functor& f constructor should only take objects convertible to a compatible function pointer
  • the Functor& f constructor should only take functors with compatible operator() and no conversion to function pointer

We thus need to check two things:

  • whether a callable has a compatible signature
  • whether a callable is convertible to a function pointer

The first check is relatively easy with expression SFINAE: decltype(std::declval<Functor&>()(std::declval<Args>()...) in the constructor’s signature disables that overload if Functor is not callable with the given arguments. We only need to check the return type then, std::is_convertible and std::is_void help create a compatible_return_type trait:

template <typename Returned, typename Required>
struct compatible_return_type
    : std::integral_constant<bool, std::is_void<Required>::value
                                       || std::is_convertible<Returned, Required>::value>
{
};

If the required return type is void, we allow any other return type and simply discard the result with the static_cast, otherwise the types must be convertible. We combine the two in this alias:

template <typename Func, typename Return, typename... Args>
using enable_matching_function =
    std::enable_if_t<compatible_return_type<decltype(std::declval<Func&>()(
                                                       std::declval<Args>()...)),
                                                   Return>::value,
                    int>;

If the decltype() is ill-formed or if the return type is not compatible, the alias is ill-formed. Putting this in the signature of the templated function pointer constructor will disable it from overload resolution.

The second step is more difficult as we want to check for a conversion to any function pointer, and don’t know the exact result. I’ve come up with the following code:

template <typename Func, typename Return, typename... Args>
struct get_callable_tag
{
    // use unary + to convert to function pointer
    template <typename T>
    static matching_function_pointer_tag test(
        int, T& obj, enable_matching_function<decltype(+obj), Return, Args...> = 0);

    template <typename T>
    static matching_functor_tag test(short, T& obj,
                                     enable_matching_function<T, Return, Args...> = 0);

    static invalid_functor_tag test(...);

    using type = decltype(test(0, std::declval<Func&>()));
};

We have three test functions where each one is a worse match then the one before. This means that overload resolution will want to pick the first one, unless SFINAE kicks in, then it will try the second one, unless SFINAE kicks in, and only then the third one. Each overload returns a tag type that describes the situation.

The first one is disabled if the type of +obj is not a compatible functor. The unary plus here is a trick to call the lambda conversion operator to function pointer. And the second overload is disabled if the functor does not have a matching signature.

The trick with the unary plus does not work with polymorphic lambdas, as they can convert to multiple function pointers at once. I wasn’t able to find a workaround for that, so I’ve kept the non-templated function pointer constructor for them. If they are convertible to a direct match function pointer, you can still use them, otherwise, you have to cast.

Then the const Functor& constructor requires the tag matching_function_pointer_tag, and the Functor& requires matching_functor_tag. As the check overload returning matching_function_pointer_tag has a higher priority, a non-const lvalue functor convertible to function pointer, will still pick the const Functor& constructor.