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, 2020 at 22:40
  • \$\begingroup\$ No, I do not have a test driver. \$\endgroup\$
    – nullptr
    Aug 4, 2020 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, 2020 at 5:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.