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 */
