"Manual" signature overload resolution

Question

I want to make a std::function like object that can handle storing more than one overload.

Syntax sort of like this: my_function< int(double, int), double(double, double), char(int, int) >.

Or, more explicitly:

template<typename... Ts>
struct type_list {};

template<typename... Signatures >
struct my_function {
  std::tuple< std::function<Signatures>... > m_functions;
  typedef type_list< Signatures... > sig_list;
  template<typename... Args>
  typename pick_overload_signature< sig_list, type_list<Args...> >::return_value
    operator()( Args&&... args )
  {
    return get<pick_overload_signature< sig_list, type_list<Args...> >::index>(m_functions)(std::forward<Args>(args)...);
  }
};

My question: how should I write pick_overload_signatures?

Here is the work I've done on it:

My inclination would be to write a partial order on function signatures with respect to a given set of arguments, then sort the type list of function signatures, then grab the best (with possibly a compile-time assert that the best one is unique). To pull that off, I'd have to have a solid partial order (with respect to a set of arguments passed in) on function signatures...

13.3.3.1 tells me how to determine if there is a valid conversion. I can cheat for this by using the compiler to do a conversion for me, and use SFINAE to detect if it occurred for a given argument passed in and the signature of one of the "overloads".

13.3.3.2 tells me how to order these conversions. Here I have to detect if a conversion sequence is user defined or a standard sequence. I am not sure how to distinguish between the two.

Maybe I can use traits class to detect the existence of user-defined conversions sequences. Check for the existence of &S::operator D() and &D::D(S const&) and &D::D(S) and &D::D(S&&) or something like that.

has_user_defined_conversion<S,D>::value, has_standard_conversion<S,D>::value, etc?

Will this approach work, has someone already done it, or has someone already done parts of this?

Result of Answers

#include <type_traits>
#include <cstddef>
#include <utility>
#include <functional>
#include <tuple>
#include <string>

// Packaged list of types:
template<typename... Ts>
struct type_list {
   template<template<typename...>class target>
   struct apply {
      typedef target<Ts...> type;
   };
   template<typename T>
   struct append {
      typedef type_list< Ts..., T > type;
   };
   template<typename T>
   struct prepend {
      typedef type_list< T, Ts... > type;
   };
};
template<template<typename>class mapper, typename list>
struct map_types {
   typedef type_list<> type;
};
template<template<typename>class mapper, typename T0, typename... Ts>
struct map_types<mapper, type_list<T0, Ts...>> {
   typedef typename map_types<mapper, type_list<Ts...>>::type tail;
   typedef typename tail::template prepend< typename mapper<T0>::type >::type type;
};
template<template<typename>class mapper, typename list>
using MapTypes = typename map_types<mapper, list>::type;
template<template<typename>class temp>
struct apply_template_to {
   template<typename T>
   struct action {
      typedef temp<T> type;
   };
};
template<template<typename> class temp, typename list>
struct apply_to_each:map_types< apply_template_to<temp>::template action, list > {};
template<template<typename> class temp, typename list>
using ApplyToEach = typename apply_to_each<temp, list>::type;

template<std::size_t n, typename list>
struct nth_type {};
template<std::size_t n, typename first, typename... elements>
struct nth_type<n, type_list<first, elements...>>:nth_type<n-1, type_list<elements...>>
{};
template<typename first, typename... elements>
struct nth_type<0, type_list<first, elements...>>
{
   typedef first type;
};
template<std::size_t n, typename list>
using NthType = typename nth_type<n, list>::type;

// func data
template<typename R, typename... Args>
struct unpacked_func {
   typedef R result_type;
   typedef type_list<Args...> args_type;
   typedef unpacked_func< R, Args... > unpacked_type;
   template<template<typename>class target>
   struct apply {
      typedef target<R(Args...)> type;
   };
};

namespace unpack_details {
   // Extracting basic function properties:
   template<typename Func>
   struct unpack_func {};
   template<typename R, typename... Args>
   struct unpack_func< R(Args...) > {
      typedef unpacked_func< R, Args... > type;
   };
   template<typename R, typename... Args>
   struct unpack_func< unpacked_func<R, Args...> >:
      unpack_func< R(Args...) >
   {};
}

template<typename Func>
using FuncUnpack = typename unpack_details::unpack_func<Func>::type;

template<typename Func>
struct func_props:func_props<FuncUnpack<Func>> {};
template<typename R, typename... Args>
struct func_props<unpacked_func<R, Args...>>:
   unpacked_func<R, Args...>
{};

template<typename Func>
using FuncResult = typename func_props<Func>::result_type;
template<typename Func>
using FuncArgs = typename func_props<Func>::args_type;

template<typename Func>
struct make_func_ptr:make_func_ptr<FuncUnpack<Func>> {};

template<typename R, typename... Args>
struct make_func_ptr< unpacked_func< R, Args... > > {
   typedef R(*type)(Args...);
};
template<typename Func>
using MakeFuncPtr = typename make_func_ptr<Func>::type;

// Marking a type up with an index:
template<typename R, std::size_t i>
struct indexed_type {
   typedef R type;
   enum { value = i };
};

// Sequences of size_t:
template<std::size_t... s>
struct seq {};
template<std::size_t min, std::size_t max, std::size_t... s>
struct make_seq: make_seq< min, max-1, max-1, s...> {};
template<std::size_t min, std::size_t... s>
struct make_seq< min, min, s...> {
     typedef seq<s...> type; 
};
template<std::size_t max, std::size_t min=0>
using MakeSeq = typename make_seq<max, min>::type;

namespace overload_details {
   template<std::size_t n, typename... Overloads>
   struct indexed_linear_signatures {};

   template<typename Overload>
   struct signature_generator {};
   template<typename R, typename... Args>
   struct signature_generator<unpacked_func<R, Args...>> {
      R operator()(Args...); // no impl
   };


   template<typename Func, std::size_t i>
   struct indexed_retval {};

   template<typename R, typename... Args, std::size_t i>
   struct indexed_retval< unpacked_func<R, Args...>, i > {
      typedef unpacked_func<indexed_type<R,i>, Args...> type;
   };

   template<typename Func, std::size_t i>
   using IndexRetval = typename indexed_retval<Func,i>::type;

   void test1() {
      typedef overload_details::IndexRetval< FuncUnpack<void()>, 0 > indexed;
      indexed::apply<std::function>::type test = []()->indexed_type<void,0> {return indexed_type<void,0>();};
   }

   template<std::size_t n, typename Overload, typename... Overloads>
   struct indexed_linear_signatures<n, Overload, Overloads...>:
      signature_generator<IndexRetval<FuncUnpack<Overload>,n>>,
      indexed_linear_signatures<n+1, Overloads...>
   {};

   template<typename T>
   struct extract_index {};
   template<typename T, std::size_t i>
   struct extract_index<indexed_type<T,i>> {
      enum {value = i};
   };

   template<typename T>
   using Decay = typename std::decay<T>::type;

   template<typename indexed_overloads, typename... Args>
   struct get_overload_index {
      enum{ value = extract_index< Decay<decltype( std::declval<indexed_overloads>()(std::declval<Args>()...) )> >::value };
   };

   template<typename Overloads, typename Args>
   struct get_overload {};
   template<typename... Overloads, typename... Args>
   struct get_overload<type_list<Overloads...>, type_list<Args...>> {
      typedef indexed_linear_signatures<0, Overloads...> sig_index;
      enum { index = get_overload_index< sig_index, Args... >::value };
      typedef FuncUnpack< NthType<index, type_list<Overloads...> > > unpacked_sig;
   };

   template<typename Overloads, typename Args>
   using GetOverloadSig = typename get_overload< Overloads, Args >::unpacked_sig;
}

template<typename Overloads, typename Arguments>
struct pick_overload_signature {
   enum{ index = overload_details::get_overload<Overloads, Arguments>::index };
   typedef overload_details::GetOverloadSig<Overloads, Arguments> unpacked_sig;
};
#include <iostream>
void test1() {
   typedef type_list< void(int), void(double) > overloads;
   typedef type_list< int > args;
   typedef pick_overload_signature< overloads, args > result;
   std::cout << result::index << " should be 0\n";
   typedef type_list< double > args2;
   typedef pick_overload_signature< overloads, args2 > result2;
   std::cout << result2::index << " should be 1\n";

//    ;
   typedef ApplyToEach< std::function, overloads >::apply< std::tuple >::type functions;
   typedef std::tuple< std::function<void(int)>, std::function<void(double)> > functions0;
   std::cout << std::is_same<functions, functions0>() << " should be true\n";

   functions funcs{
      [](int) { std::cout << "int!" << "\n"; },
      [](double) { std::cout << "double!" << "\n"; }
   };
   std::get<result::index>(funcs)(0);
}

template< typename... Signatures >
struct my_function {
   typedef type_list<Signatures...> signatures;
   typedef std::tuple< std::function<Signatures>... > func_tuple;
   func_tuple functions;
   template<typename... Funcs>
   explicit my_function(Funcs&&... funcs):
      functions( std::forward<Funcs>(funcs)... )
   {}

   template<typename... Args>
   auto
   operator()(Args&&... args) const ->
      typename overload_details::GetOverloadSig< signatures, type_list<Args...> >::result_type
   {
      return std::get<
         pick_overload_signature< signatures, type_list<Args...> >::index
      >(functions)(std::forward<Args>(args)...);
   }
   // copy/assign boilerplate
   template<typename... OtherSignatures>
   my_function( my_function<OtherSignatures...> const& o ):
      functions( o.functions )
   {}
   template<typename... OtherSignatures>
   my_function( my_function<OtherSignatures...> && o ):
      functions( std::move(o.functions) )
   {}
   template<typename... OtherSignatures>
   my_function& operator=( my_function<OtherSignatures...> const& o )
   {
      functions = o.functions;
      return *this;
   }
   template<typename... OtherSignatures>
   my_function& operator=( my_function<OtherSignatures...> && o ) {
      functions = std::move(o.functions);
      return *this;
   }
};

struct printer {
   template<typename T>
   void operator()( T const& t ) {
      std::cout << t << "\n";
   }
};

void print(int x) {
   std::cout << "int is " << x << "\n";
}
void print(std::string s) {
   std::cout << "string is " << s << "\n";
}
void test2() {
   my_function< void(int), void(std::string) > funcs{
      [](int x){ std::cout << "int is " << x << "\n";},
      [](std::string s){ std::cout << "string is " << s << "\n";}
   };
   std::cout << "test2\n";
   funcs("hello");
   funcs(0);
   my_function< void(int), void(std::string) > funcs2{
      printer(), printer()
   };
   funcs2("hello");
   funcs2(12.7);
   // doesn't work:
   /*
   my_function< void(int), void(std::string) > funcs3{
      print,
      print
   };
   */
}
void test3() {

}
int main() {
   test1();
   test2();
   test3();
}

Isn't done, but is usable.

Thanks all!

Very interesting question, and I have some ideas in mind on how to answer it, but I'll have to play around with that when I get to work. — Xeo, Feb 20 '13 at 08:01
Do you want to be able to store different overloads of the same function, or different functions to be invoked depending on the arguments? Could you give an example of how you intend to use your class template? — Andy Prowl, Feb 20 '13 at 14:19
@AndyProwl I'd be satisfied (for now) with different functions to be invoked depending on the arguments, "as-if" they where participating in overload resolution. You could then repeat that function multiple times as the "different functions". Eliminating that repeat might be good (and doable with a bit of macro+perfect forwarding template lambda tomfoolery), but not necessary. — Yakk - Adam Nevraumont, Feb 20 '13 at 15:14
For experimenting: http://ideone.com/NDpkB5 . Please disregard the ugly implementation :) — Johannes Schaub - litb, Feb 24 '13 at 17:09
@johannesschaub are you using pairwise overload tests to order signatures? Slick! — Yakk - Adam Nevraumont, Feb 24 '13 at 18:42

score 4 · Accepted Answer · edited Feb 20 '13 at 16:22

4

i'm sure it is doable your way, but may be you will be satisfied with this one https://gist.github.com/dabrahams/3779345

template<class...Fs> struct overloaded;

template<class F1, class...Fs>
struct overloaded<F1, Fs...> : F1, overloaded<Fs...>::type
{
typedef overloaded type;

overloaded(F1 head, Fs...tail)
: F1(head),
overloaded<Fs...>::type(tail...)
{}
using F1::operator();
using overloaded<Fs...>::type::operator();
};

template<class F>
struct overloaded<F> : F
{
typedef F type;
using F::operator();
};

template<class...Fs>
typename overloaded<Fs...>::type overload(Fs...x)
{ return overloaded<Fs...>(x...); }

auto f = overload(
[](int x) { return x+1; },
[](char const* y) { return y + 1; },
[](int* y) { return y; });

edited Feb 20 '13 at 16:22

Yakk - Adam Nevraumont

262,606
27
330
524

answered Feb 20 '13 at 12:31

pal

618
4
9

Does that do the same "dispatch" choice as function overloading would? – Yakk - Adam Nevraumont Feb 20 '13 at 15:16
1

@Yakk: It necessarily does, because it effectively creates an overload set for `operator()` with the alternative signatures. – Andy Prowl Feb 20 '13 at 15:18
Ah yes, the `operator()` are not vertically related, so there is no preference for one over the other. Nice trick -- adapting that for a `std::function` style interface should be easy! The only downside is because we use the compiler's overload resolution mechanics directly, we don't get to play with it (or change it). I can also pull off perfect forwarding by using the above in a unevaluated context to get the index of the right overload. – Yakk - Adam Nevraumont Feb 20 '13 at 16:24

score 1 · Answer 2 · answered Feb 20 '13 at 08:26

I think you can use something like these traits... But if you want make overloading resolution fully as in standard - you need more code http://en.cppreference.com/w/cpp/language/implicit_cast

#include <type_traits>

template<typename T, typename D>
struct is_constructible
{
   template<typename C, typename F>
   static auto test(C*) -> decltype(C(std::declval<F>()), std::true_type());
   template<typename, typename>
   static std::false_type test(...);
   static const bool value = std::is_class<T>::value && 
      std::is_same<std::true_type, decltype(test<T, D>(0))>::value;
};

template<typename T, typename D>
struct has_conversion_operator
{
   static std::true_type test(D d);
   template<typename C, typename F>
   static auto test(C* c) -> decltype(test(*c));
   template<typename, typename>
   static std::false_type test(...);

   static const bool value = std::is_class<T>::value && 
      !is_constructible<T, D>::value && 
      std::is_same<std::true_type, decltype(test<T, D>(0))>::value;
};

template<typename T, typename D>
struct is_standard_convertible : 
   std::integral_constant<bool, !has_conversion_operator<T, D>::value && 
   !is_constructible<T, D>::value &&
   std::is_convertible<T, D>::value>
{
};

template<typename T, typename D>
struct is_user_convertible :
   std::integral_constant<bool, has_conversion_operator<T, D>::value || 
   is_constructible<T, D>::value>
{
};

and implement what you want like: first check, that signatures are standard_convertible if not check that signature are user_convertible.

"Manual" signature overload resolution

2 Answers2

Linked