Overloading multiple function objects by reference
Asked Answered
M

2

40

In C++17, it is trivial to implement an overload(fs...) function that, given any number of arguments fs... satisfying FunctionObject, returns a new function object that behaves like an overload of fs.... Example:

template <typename... Ts>
struct overloader : Ts...
{
    template <typename... TArgs>
    overloader(TArgs&&... xs) : Ts{forward<TArgs>(xs)}...
    {
    }

    using Ts::operator()...;
};

template <typename... Ts>
auto overload(Ts&&... xs)
{
    return overloader<decay_t<Ts>...>{forward<Ts>(xs)...};
}

int main()
{
    auto o = overload([](char){ cout << "CHAR"; }, 
                      [](int) { cout << "INT";  });

    o('a'); // prints "CHAR"
    o(0);   // prints "INT"
}

live example on wandbox


Since the above overloader inherits from Ts..., it needs to either copy or move the function objects in order to work. I want something that provides the same overloading behavior, but only references to the passed function objects.

Let's call that hypothetical function ref_overload(fs...). My attempt was using std::reference_wrapper and std::ref as follows:

template <typename... Ts>
auto ref_overload(Ts&... xs)
{
    return overloader<reference_wrapper<Ts>...>{ref(xs)...};
}

Seems simple enough, right?

int main()
{
    auto l0 = [](char){ cout << "CHAR"; };
    auto l1 = [](int) { cout << "INT";  };

    auto o = ref_overload(l0, l1);

    o('a'); // BOOM
    o(0);
}

error: call of '(overloader<...>) (char)' is ambiguous
 o('a'); // BOOM
      ^

live example on wandbox

The reason it doesn't work is simple: std::reference_wrapper::operator() is a variadic function template, which does not play nicely with overloading.

In order to use the using Ts::operator()... syntax, I need Ts... to satisfy FunctionObject. If I try to make my own FunctionObject wrapper, I encounter the same issue:

template <typename TF>
struct function_ref
{
    TF& _f;
    decltype(auto) operator()(/* ??? */);
};

Since there's no way of expressing "compiler, please fill the ??? with the exact same arguments as TF::operator()", I need to use a variadic function template, solving nothing.

I also cannot use something like boost::function_traits because one of the functions passed to overload(...) may be a function template or an overloaded function object itself!

Therefore my question is: is there a way of implementing a ref_overload(fs...) function that, given any number of fs... function objects, returns a new function object that behaves like an overload of fs..., but refers to fs... instead of copying/moving them?

Maravedi answered 23/3, 2017 at 21:16 Comment(13)
The reason why what you did was "trivial" was that you could derive from those types, and therefore use a using declaration to bring all of those operator()'s into your own overload set. Thus allowing the C++ compiler to do the work of overload resolution for you. Once you can no longer use that trick, you're now stuck with manually implementing overload resolution. That will be... decidedly non-trivial. Good luck.Dominique
Basically you need to implement overload resolution in template metaprogramming. Your overload can have a single operator() template, the you need to select which one of the Ts... matches. You can take inspiration from the implementation of std::variant constructor, which basically needs to solve the same problem. Boost.Variant implements it here.Thistly
@Thistly These are very different problems. variant's straightforward, you set up a bunch of fun(T) for every type in the variant and run overload resolution with fun(arg) to see which one is selected. OP's case is decidedly non-straightforward.Fitz
Back up and solve it for 2 function objects of 1 argument. We can determine which accept convert-from T and which accept T via template<class T>struct not_T{operator T()&&;}; Covering all of the overload rules is probably impossible, however.Agateware
Thanks for the suggestions. Honestly, reimplementing all overload resolution rules sounds like hell, even if I were to use something like boost::hana. BTW, here's a possible workaround that abuses placement new to move back the overloaded functions into their original places: on wandboxMaravedi
Here's a "fake" ref_overload implementation: on wandbox.Maravedi
@Yakk I would go with "definitely impossible". How do you do partial ordering?Fitz
@Fitz I do not know. But I do know that 2-3 times a year I figure out how to do something I thought was impossible in C++. So I hedge my bets unless I can prove it impossible, and then I doubt my proof. Maybe method pointers and manual dispatch; probably not. I seriously doubt it is possible, but I won't rule it out.Agateware
Perhaps it's possible to bypass the issue by copying void pointers to Ts instead of copying the Ts objects (erasing their type), while still keeping the original types using just the template context, so the void pointers can then later be static_cast back to Ts inside?Ellison
@Danra: I don't see a way that could work - do you have an example? The issue is that I need to inherit from Ts... to have using Ts::operator()....Maravedi
Perhaps in the future... open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0352r0.pdfMenchaca
@Menchaca More recent version here open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0352r1.pdfEllison
I am aware of operator. overloading and really looking forward to it :) - I need ref_overload in C++17, though...Maravedi
M
30

All right, here's the plan: we're going to determine which function object contains the operator() overload that would be chosen if we used a bare-bones overloader based on inheritance and using declarations, as illustrated in the question. We're going to do that (in an unevaluated context) by forcing an ambiguity in the derived-to-base conversion for the implicit object parameter, which happens after overload resolution succeeds. This behaviour is specified in the standard, see N4659 [namespace.udecl]/16 and 18.

Basically, we're going to add each function object in turn as an additional base class subobject. For a call for which overload resolution succeeds, creating a base ambiguity for any of the function objects that don't contain the winning overload won't change anything (the call will still succeed). However, the call will fail for the case where the duplicated base contains the chosen overload. This gives us a SFINAE context to work with. We then forward the call through the corresponding reference.

#include <cstddef>
#include <type_traits>
#include <tuple>
#include <iostream>

template<class... Ts> 
struct ref_overloader
{
   static_assert(sizeof...(Ts) > 1, "what are you overloading?");

   ref_overloader(Ts&... ts) : refs{ts...} { }
   std::tuple<Ts&...> refs;

   template<class... Us> 
   decltype(auto) operator()(Us&&... us)
   {
      constexpr bool checks[] = {over_fails<Ts, pack<Us...>>::value...};
      static_assert(over_succeeds(checks), "overload resolution failure");
      return std::get<choose_obj(checks)>(refs)(std::forward<Us>(us)...);
   }

private:
   template<class...> 
   struct pack { };

   template<int Tag, class U> 
   struct over_base : U { };

   template<int Tag, class... Us> 
   struct over_base<Tag, ref_overloader<Us...>> : Us... 
   { 
       using Us::operator()...; // allow composition
   }; 

   template<class U> 
   using add_base = over_base<1, 
       ref_overloader<
           over_base<2, U>, 
           over_base<1, Ts>...
       >
   >&; // final & makes declval an lvalue

   template<class U, class P, class V = void> 
   struct over_fails : std::true_type { };

   template<class U, class... Us> 
   struct over_fails<U, pack<Us...>,
      std::void_t<decltype(
          std::declval<add_base<U>>()(std::declval<Us>()...)
      )>> : std::false_type 
   { 
   };

   // For a call for which overload resolution would normally succeed, 
   // only one check must indicate failure.
   static constexpr bool over_succeeds(const bool (& checks)[sizeof...(Ts)]) 
   { 
       return !(checks[0] && checks[1]); 
   }

   static constexpr std::size_t choose_obj(const bool (& checks)[sizeof...(Ts)])
   {
      for(std::size_t i = 0; i < sizeof...(Ts); ++i)
         if(checks[i]) return i;
      throw "something's wrong with overload resolution here";
   }
};

template<class... Ts> auto ref_overload(Ts&... ts)
{
   return ref_overloader<Ts...>{ts...};
}


// quick test; Barry's example is a very good one

struct A { template <class T> void operator()(T) { std::cout << "A\n"; } };
struct B { template <class T> void operator()(T*) { std::cout << "B\n"; } };

int main()
{
   A a;
   B b;
   auto c = [](int*) { std::cout << "C\n"; };
   auto d = [](int*) mutable { std::cout << "D\n"; };
   auto e = [](char*) mutable { std::cout << "E\n"; };
   int* p = nullptr;
   auto ro1 = ref_overload(a, b);
   ro1(p); // B
   ref_overload(a, b, c)(p); // B, because the lambda's operator() is const
   ref_overload(a, b, d)(p); // D
   // composition
   ref_overload(ro1, d)(p); // D
   ref_overload(ro1, e)(p); // B
}

live example on wandbox


Caveats:

  • We're assuming that, even though we don't want an overloader based on inheritance, we could inherit from those function objects if we wanted to. No such derived object is created, but the checks done in unevaluated contexts rely on this being possible. I can't think of any other way to bring those overloads into the same scope so that overload resolution can be applied to them.
  • We're assuming that forwarding works correctly for the arguments to the call. Given that we hold references to the target objects, I don't see how this could work without some kind of forwarding, so this seems like a mandatory requirement.
  • This currently works on Clang. For GCC, it looks like the derived-to-base conversion we're relying on is not a SFINAE context, so it triggers a hard error; this is incorrect as far as I can tell. MSVC is super helpful and disambiguates the call for us: it looks like it just chooses the base class subobject that happens to come first; there, it works - what's not to like? (MSVC is less relevant to our problem at the moment, since it doesn't support other C++17 features either).
  • Composition works through some special precautions - when testing the hypothetical inheritance based overloader, a ref_overloader is unwrapped into its constituent function objects, so that their operator()s participate in overload resolution instead of the forwarding operator(). Any other overloader attempting to compose ref_overloaders will obviously fail unless it does something similar.

Some useful bits:

  • A nice simplified example by Vittorio showing the ambiguous base idea in action.
  • About the implementation of add_base: the partial specialization of over_base for ref_overloader does the "unwrapping" mentioned above to enable ref_overloaders containing other ref_overloaders. With that in place, I just reused it to build add_base, which is a bit of a hack, I'll admit. add_base is really meant to be something like inheritance_overloader<over_base<2, U>, over_base<1, Ts>...>, but I didn't want to define another template that would do the same thing.
  • About that strange test in over_succeeds: the logic is that if overload resolution would fail for the normal case (no ambiguous base added), then it would also fail for all the "instrumented" cases, regardless of what base is added, so the checks array would contain only true elements. Conversely, if overload resolution would succeed for the normal case, then it would also succeed for all the other cases except one, so checks would contain one true element with all the others equal to false.

    Given this uniformity in the values in checks, we can look at just the first two elements: if both are true, this indicates overload resolution failure in the normal case; all the other combinations indicate resolution success. This is the lazy solution; in a production implementation, I would probably go for a comprehensive test to verify that checks really contains an expected configuration.


Bug report for GCC, submitted by Vittorio.

Bug report for MSVC.

Mar answered 28/3, 2017 at 14:47 Comment(12)
This is promising... and scary! I'll have to spend some time studying and understanding this. I edited your answer to add some line breaks, as it was hard to read (especially due to the StackOverflow layout) - hopefully you don't mind.Maravedi
Uh, wow. That's brilliant. Wow. I feel like the only thing I provided here is a good test case :)Susannsusanna
@VittorioRomeo Sure, no worries. I think many (most) people will prefer your formatting, so thanks for taking the time to do that. If anyone wants my horizontally squashed version, they can get it from the revision history.Mar
@Susannsusanna Cheers! I do think your answer is very useful in its entirety, and clearly several people agree. Mine breaks two compilers out of three; I'm not sure how I should feel about that :-).Mar
@bogdan: is there any reason you're using ref_overloader in add_base and over_base? Wouldn't pack suffice there?Maravedi
@bogdan: a self-contained example that shows how over_base, add_base, and over_fails work with some hardcoded functions would clarify a lot for me - hopefully that's not too much to ask :)Maravedi
After discussing it on cpplang.slack, I reported a minimal example triggering the bug you encountered on gcc: gcc.gnu.org/bugzilla/show_bug.cgi?id=80245Maravedi
@VittorioRomeo Yes, that's the gist of it; good explanation. Thanks for filing the bug against GCC. I'll try to report the one on MSVC tomorrow. The partial specialization of over_base for ref_overloader does the 'unwrapping' mentioned in the answer to enable ref_overloaders containing other ref_overloaders. With that in place, I just reused it to build add_base, which is a bit of a hack, I'll admit. add_base should really be inheritance_overloader<over_base<2, U>, over_base<1, Ts>...>, but I didn't want to define another template that would do the same thing.Mar
Glad to be proven wrong :) Now I'm just waiting for Vittorio to award his bounty so that I can tack on one of my own...Fitz
This is insanely clever, hat tip to you. Only question -- it must be dead simple compared to the rest, but how does over_succeeds get away with a single check?Inerney
@Inerney One part reasonable assumption, one part laziness :-). Good question; I've added an explanation to the answer.Mar
@Fitz "Prove T.C. wrong" - I'm pretty sure there's a paragraph somewhere in the standard making such a statement ill-formed NDR :-). In all fairness, this solution sidesteps the problem that you were discussing with Yakk in the comments, so I think you're being too hard on yourself. Jokes aside, your gesture means a lot to me; thank you.Mar
S
10

In the general case, I don't think such a thing is possible even in C++17. Consider the most obnoxious case:

struct A {
    template <class T> int operator()(T );
} a;

struct B {
    template <class T> int operator()(T* );
} b;

ref_overload(a, b)(new int);

How could you possibly make that work? We could check that both types are callable with int*, but both operator()s are templates so we can't pick out their signatures. Even if we could, the deduced parameters themselves are identical - both functions take an int*. How would you know to call b?

In order to get this case correct, what you'd basically need to do is to inject return type into the call operators. If we could create types:

struct A' {
    template <class T> index_<0> operator()(T );
};

struct B' {
    template <class T> index_<1> operator()(T* );
};

Then we could use decltype(overload(declval<A'>(), declval<B'>()))::value to pick which reference to call ourselves.

In the simplest case - when both A and B (and C and ...) have one single operator() that is not a template, this is doable - since we can actually inspect &X::operator() and manipulate those signatures to produce the new ones that we need. This allows us to still use the compiler to do overload resolution for us.

We can also check what type overload(declval<A>(), declval<B>(), ...)(args...) yields. If the best match's return type is unique almost all the viable candidates, we can still pick the correct overload in ref_overload. This will cover more ground for us, as we can now correctly handle some cases with overloaded or templated call operators, but we will incorrectly reject many calls as ambiguous that aren't.


But in order to solve the general problem, with types that have overloaded or templated call operators with the same return type, we need something more. We need some future language features.

Full reflection would allow us to inject a return type as described above. I don't know what that would look like specifically, but I look forward to seeing Yakk's implementation of it.

An alternative potential future solution would be to use overloaded operator .. Section 4.12 includes an example that indicates that the design allows for overloading of different member functions by name through different operator.()s. If that proposal passes in some similar form today, then implementing reference-overloading would follow the same pattern as object-overloading today, just substituting different operator .()s for today's different operator ()s:

template <class T>
struct ref_overload_one {
    T& operator.() { return r; }
    T& r;
};

template <class... Ts>
struct ref_overloader : ref_overload_one<Ts>...
{
    ref_overloader(Ts&... ts)
    : ref_overload_one<Ts>{ts}...
    { }

    using ref_overload_one<Ts>::operator....; // intriguing syntax?
};
Susannsusanna answered 27/3, 2017 at 14:48 Comment(2)
Good answer. I was hoping for a crazy clever solution but your explanation and examples make me confident that it's currently impossible. A mention + example of a possible operator. overloading solution would make this answer even better, and I will very likely award you the bounty (unless someone miraculously figures something out).Maravedi
@VittorioRomeo Yeah, Stroustrup's operator.() says it should support overloading of member names through multiple operator.()s. I don't know what the status of that paper is or its relative likelihood of adoption vs some reflection solution. I don't think that Hubert or Faisal's alternative supports this, but I'm not sure.Susannsusanna

© 2022 - 2024 — McMap. All rights reserved.