7
\$\begingroup\$

When I first tried to implement std::function I thought it would as easy as creating a class that holds a function pointer. Consequently, I quickly figured out that I was wrong when I tried to use it with a capturing lambda and got an error message. As a result, I quit and until recently I wondered how std::function was implemented. However, that was when I found out about type erasure and realized that's how std::function is probably implemented. Which caused me to have a second attempt at recreating it.

Here is the code:functional.hh

#ifndef FUNCTIONAL_HH
#define FUNCTIONAL_HH

#include <utility>
#include <new>

namespace turtle
{

    class bad_function_call : public std::exception
    {
    public:
        bad_function_call() noexcept = default;

        char const virtual *what() noexcept
        {
            return "bad function call";
        }
    };

    namespace detail
    {
        template<typename>
        bool constexpr is_reference_wrapper_v = false;
        template<typename U>
        bool constexpr is_reference_wrapper_v<std::reference_wrapper<U>> = true;

        template<typename T, typename Type, typename T1, typename... Args>
        decltype(auto) constexpr INVOKE(Type T::* f, T1 &&t1, Args &&... args)
        {
            if constexpr (std::is_member_function_pointer_v<decltype(f)>)
            {
                if constexpr (std::is_base_of_v<T, std::decay_t<T1>>)
                    return (std::forward<T1>(t1).*f)(std::forward<Args>(args)...);
                else if constexpr (is_reference_wrapper_v<std::decay_t<T1>>)
                    return (t1.get().*f)(std::forward<Args>(args)...);
                else
                    return ((*std::forward<T1>(t1)).*f)(std::forward<Args>(args)...);
            }
            else
            {
                static_assert(std::is_member_object_pointer_v<decltype(f)>);
                static_assert(sizeof...(args) == 0);
                if constexpr (std::is_base_of_v<T, std::decay_t<T1>>)
                    return std::forward<T1>(t1).*f;
                else if constexpr (is_reference_wrapper_v<std::decay_t<T1>>)
                    return t1.get().*f;
                else
                    return (*std::forward<T1>(t1)).*f;
            }
        }

        template<typename F, typename... Args>
        decltype(auto) constexpr INVOKE(F &&f, Args &&... args)
        {
            return std::forward<F>(f)(std::forward<Args>(args)...);
        }
    } /* namespace detail */

    template<typename>
    class function;

    template<typename R, typename... Args>
    class function<R(Args...)>
    {
    private:
        union storage_union
        {
            using stack_storage_t = std::aligned_storage_t<sizeof(void *) * 3, alignof(void *)>;
            void *dynamic;
            stack_storage_t stack;
        };

        struct vtable_t
        {
            R (*invoke)(storage_union &storage, Args &&... args);

            void (*copy)(storage_union &dest, storage_union const &src);

            void (*move)(storage_union &dest, storage_union &src) noexcept;

            void (*swap)(storage_union &lhs, storage_union &rhs) noexcept;

            void (*destroy)(storage_union &storage) noexcept;

            std::type_info const &(*type)() noexcept;
        };

        template<typename T>
        struct vtable_dynamic_t
        {
            R static invoke(storage_union &storage, Args &&... args)
            { return detail::INVOKE(*reinterpret_cast<T *>(storage.dynamic), std::forward<Args>(args)...); }

            void static copy(storage_union &dest, storage_union const &src)
            { dest.dynamic = new T(*reinterpret_cast<const T *>(src.dynamic)); }

            void static move(storage_union &dest, storage_union &src) noexcept
            {
                dest.dynamic = src.dynamic;
                src.dynamic = nullptr;
            }

            void static swap(storage_union &lhs, storage_union &rhs) noexcept
            { std::swap(lhs.dynamic, rhs.dynamic); }

            void static destroy(storage_union &storage) noexcept
            { delete reinterpret_cast<T *>(storage.dynamic); }

            std::type_info static const &type() noexcept
            { return typeid(T); }
        };

        template<typename T>
        struct vtable_stack_t
        {
            R static invoke(storage_union &storage, Args &&... args)
            { return detail::INVOKE(reinterpret_cast<T &>(storage.stack), std::forward<Args>(args)...); }

            void static copy(storage_union &dest, storage_union const &src)
            { new(&dest.stack) T(reinterpret_cast<const T &>(src.stack)); }

            void static move(storage_union &dest, storage_union &src) noexcept
            {
                new(&dest.stack) T(std::move(reinterpret_cast<T &>(src.stack)));
                destroy(src);
            }

            void static swap(storage_union &lhs, storage_union &rhs) noexcept
            {
                storage_union tmp_storage;
                move(tmp_storage, rhs);
                move(rhs, lhs);
                move(lhs, tmp_storage);
            }

            void static destroy(storage_union &storage) noexcept
            { reinterpret_cast<T *>(&storage.stack)->~T(); }

            std::type_info const static &type() noexcept
            { return typeid(T); }
        };

        template<typename T>
        bool constexpr static requires_allocation = !(std::is_nothrow_move_constructible_v<T>
                                                      && sizeof(T) <= sizeof(typename storage_union::stack_storage_t)
                                                      &&
                                                      alignof(T) <= alignof(typename storage_union::stack_storage_t));

        template<typename T>
        vtable_t static *vtable_for_type()
        {
            using VTable = std::conditional_t<requires_allocation<T>, vtable_dynamic_t<T>, vtable_stack_t<T>>;
            vtable_t static vtable{
                    VTable::invoke,
                    VTable::copy,
                    VTable::move,
                    VTable::swap,
                    VTable::destroy,
                    VTable::type
            };
            return &vtable;
        }

    public:
        function() noexcept = default;

        function(std::nullptr_t) noexcept
        {}

        function(function const &other)
                : M_VTable(other.M_VTable)
        {
            if (M_VTable != nullptr)
            {
                M_VTable->copy(M_Storage, other.M_Storage);
            }
        }

        function(function &&other) noexcept
                : M_VTable(other.M_VTable)
        {
            if (M_VTable != nullptr)
            {
                M_VTable->move(M_Storage, other.M_Storage);
                other.M_VTable = nullptr;
            }
        }

        template<typename F>
        function(F f) : M_VTable(vtable_for_type<F>())
        {
            if constexpr(requires_allocation<F>)
            {
                M_Storage.dynamic = new F(std::move(f));
            }
            else
            {
                new(&M_Storage.stack) F(std::move(f));
            }
        }

        ~function()
        {
            /* if we hold a function */
            if (M_VTable != nullptr)
            {
                M_VTable->destroy(M_Storage);
            }
        }

        function &operator=(function const &other)
        {
            function(other).swap(*this);
            return *this;
        }

        function &operator=(function &&other)
        {
            function(std::move(other)).swap(*this);
            return *this;
        }

        function &operator=(std::nullptr_t) noexcept
        {
            /* destroy functor */
            M_VTable->destroy(M_Storage);
            return *this;
        }

        template<typename F>
        function &operator=(F &&f)
        {
            function(std::forward<F>(f)).swap(*this);
            return *this;
        }

        template<typename F>
        function &operator=(std::reference_wrapper<F> f) noexcept
        {
            function(f).swap(*this);
            return *this;
        }

        explicit operator bool() const noexcept
        { return M_VTable != nullptr; }

        void swap(function &other)
        {
            /* if we hold the same functor type */
            if (M_VTable == other.M_VTable)
            {
                if (M_VTable != nullptr)
                    M_VTable->swap(M_Storage, other.M_Storage);
            }
            else
            {
                function tmp_function(std::move(other));

                /* move *this to other */
                other.M_VTable = M_VTable;
                if (other.M_VTable != nullptr)
                {
                    other.M_VTable->move(other.M_Storage, M_Storage);
                }

                /* move tmp_function(previous other) to *this */
                M_VTable = tmp_function.M_VTable;
                if (M_VTable != nullptr)
                {
                    M_VTable->move(M_Storage, tmp_function.M_Storage);
                    tmp_function.M_VTable = nullptr;
                    (void)(tmp_function.M_VTable);
                }
            }
        }

        R operator()(Args... args) const /* why const ? */
        {
            /* make sure we hold a functor */
            if (M_VTable != nullptr)
            {
                return M_VTable->invoke(M_Storage, std::forward<Args>(args)...);
            }
            else
            {
                throw bad_function_call{};
            }
        }

        std::type_info const &target_type() const noexcept
        {
            return M_VTable != nullptr ? M_VTable->type() : typeid(void);
        }

        template<typename T>
        T *target() noexcept
        {
            return typeid(T) == M_VTable->type() ? requires_allocation<std::decay_t<T>>
                                                   ? reinterpret_cast<T *>(M_Storage.dynamic) :
                                                   reinterpret_cast<T *>(&M_Storage.stack) : nullptr;
        }

        template<typename T>
        T const *target() const noexcept
        {
            return typeid(T) == M_VTable->type() ? requires_allocation<std::decay_t<T>>
                                                   ? reinterpret_cast<const T *>(M_Storage.dynamic) :
                                                   reinterpret_cast<const T *>(&M_Storage.stack) : nullptr;
        }

    private:
        mutable storage_union M_Storage;
        vtable_t *M_VTable = nullptr;
    };

    template<typename R, typename... Args>
    bool operator==(function<R(Args...)> const &f, std::nullptr_t) noexcept
    {
        return !static_cast<bool>(f);
    }


    namespace detail
    {
        template<typename>
        struct function_guide_helper
        { };

        template<typename R, typename Class, bool NoExcept, typename... Args>
        struct function_guide_helper<
                R (Class::*) (Args...) noexcept(NoExcept)
        >
        { using type = R(Args...); };

        template<typename R, typename Class, bool NoExcept, typename... Args>
        struct function_guide_helper<
                R (Class::*) (Args...) & noexcept(NoExcept)
        >
        { using type = R(Args...); };

        template<typename R, typename Class, bool NoExcept, typename... Args>
        struct function_guide_helper<
                R (Class::*) (Args...) const noexcept(NoExcept)
        >
        { using type = R(Args...); };
    }

    /* deduction guides */
    template<typename R, typename... ArgsTypes>
    function(R(*)(ArgsTypes...)) -> function<R(ArgsTypes...)>;

    template<typename F,
            typename FunctionType =
                    typename detail::function_guide_helper<decltype(&F::operator())>::type>
    function(F) -> function<FunctionType>;
}
#endif /* FUNCTIONAL_HH */
\$\endgroup\$
3
  • 5
    \$\begingroup\$ Do you also have a test driver? Ideally automated unit tests. \$\endgroup\$ – πάντα ῥεῖ Aug 4 '20 at 22:40
  • \$\begingroup\$ No, I do not have a test driver. \$\endgroup\$ – nullptr Aug 4 '20 at 22:47
  • 2
    \$\begingroup\$ FYI: I wrote the same thing last year; my implementation and the reviews might be of help. \$\endgroup\$ – L. F. Aug 7 '20 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.