<algorithm>: _Pass_fn/_Ref_fn interferes with the Ranges invoke protocol

[StephanTLavavej]

Range algorithms are specified to std::invoke their predicates and projections. This handles function objects (callable with parentheses), pointers to member functions, and pointers to member data.

Internally, we use a helper called _Pass_fn() returning a wrapper called _Ref_fn to avoid unnecessarily copying predicates/etc. Although this was developed for classic algorithms (where only function objects, callable with parentheses, are accepted), we've been using it in Ranges too, and it hasn't been observed to cause problems with invoke. Until now! 😼

STL/stl/inc/xutility

Lines 187 to 212 in c10ae01

	// FUNCTION TEMPLATE _Pass_fn
	// TRANSITION, VSO-386225
	template <class _Fx>
	struct _Ref_fn { // pass function object by value as a reference
	template <class... _Args>
	constexpr decltype(auto) operator()(_Args&&... _Vals) { // forward function call operator
	return _Fn(_STD forward<_Args>(_Vals)...);
	}
	_Fx& _Fn;
	};
	template <class _Fn>
	_INLINE_VAR constexpr bool
	_Pass_functor_by_value_v = sizeof(_Fn) <= sizeof(void*)
	&& conjunction_v<is_trivially_copy_constructible<_Fn>, is_trivially_destructible<_Fn>>;
	template <class _Fn, enable_if_t<_Pass_functor_by_value_v<_Fn>, int> = 0> // TRANSITION, if constexpr
	constexpr _Fn _Pass_fn(_Fn _Val) { // pass functor by value
	return _Val;
	}
	template <class _Fn, enable_if_t<!_Pass_functor_by_value_v<_Fn>, int> = 0>
	constexpr _Ref_fn<_Fn> _Pass_fn(_Fn& _Val) { // pass functor by "reference"
	return {_Val};
	}

This passes small, trivial-ish callable objects by value, allowing them to be used directly (either directly called by classic algorithms, or directly invoked by Ranges algorithms). Other callable objects are wrapped in _Ref_fn, which provides operator() and assumes that it's wrapping a function object _Fn, callable with parentheses.

This assumption is broken if we can find a large callable object (activating the _Ref_fn codepath) that requires pointer-to-member syntax, and it is indeed possible for PMFs to be larger than void*. 🙀

C:\Temp>type meow.cpp

#include <algorithm>
#include <iostream>
#include <memory>
#include <ranges>
#include <vector>
using namespace std;

struct Base {
    virtual int purr() {
        return -1;
    }
    virtual ~Base() {} // silence Clang -Wdelete-non-abstract-non-virtual-dtor
};

struct Derived1 : virtual Base {
    int purr() override {
        return 1729;
    }
};

struct Derived2 : virtual Base {};

struct MostDerived : Derived1, Derived2 {
    int purr() override {
        return 2020;
    }
};

int main() {
    cout << "    sizeof(&Base::purr): " << sizeof(&Base::purr) << endl;
    cout << "sizeof(&Derived1::purr): " << sizeof(&Derived1::purr) << endl;

    vector<shared_ptr<Derived1>> vec;
    vec.insert(vec.end(), 2, make_shared<Derived1>());
    vec.insert(vec.end(), 3, make_shared<MostDerived>());

    cout << "ranges::count(vec, 1729, &Base::purr): " << ranges::count(vec, 1729, &Base::purr) << endl;
    cout << "ranges::count(vec, 2020, &Base::purr): " << ranges::count(vec, 2020, &Base::purr) << endl;

#ifndef SKIP_BUG
    cout << "ranges::count(vec, 1729, &Derived1::purr): " << ranges::count(vec, 1729, &Derived1::purr) << endl;
    cout << "ranges::count(vec, 2020, &Derived1::purr): " << ranges::count(vec, 2020, &Derived1::purr) << endl;
#endif
}

C:\Temp>cl /EHsc /nologo /W4 /std:c++latest /DSKIP_BUG meow.cpp && meow
meow.cpp
    sizeof(&Base::purr): 4
sizeof(&Derived1::purr): 12
ranges::count(vec, 1729, &Base::purr): 2
ranges::count(vec, 2020, &Base::purr): 3

C:\Temp>clang-cl -m32 /EHsc /nologo /W4 /std:c++latest /DSKIP_BUG meow.cpp && meow
    sizeof(&Base::purr): 4
sizeof(&Derived1::purr): 12
ranges::count(vec, 1729, &Base::purr): 2
ranges::count(vec, 2020, &Base::purr): 3

C:\Temp>cl /EHsc /nologo /W4 /std:c++latest meow.cpp && meow
meow.cpp
S:\GitHub\STL\out\build\x86\out\inc\xutility(193): error C2064: term does not evaluate to a function taking 1 arguments
S:\GitHub\STL\out\build\x86\out\inc\type_traits(1502): note: see reference to function template instantiation 'decltype(auto) std::_Ref_fn<_Pj>::operator ()<std::shared_ptr<Derived1>&>(std::shared_ptr<Derived1> &)' being compiled
        with
        [
            _Pj=int (__thiscall Derived1::* )(void)
        ]
S:\GitHub\STL\out\build\x86\out\inc\algorithm(642): note: see reference to function template instantiation 'int std::ranges::_Count_fn::_Count_unchecked<std::shared_ptr<Derived1>*,std::shared_ptr<Derived1>*,_Ty,std::_Ref_fn<_Pj>>(_It,const _Se,const _Ty &,std::_Ref_fn<_Pj>)' being compiled
        with
        [
            _Ty=int,
            _Pj=int (__thiscall Derived1::* )(void),
            _It=std::shared_ptr<Derived1> *,
            _Se=std::shared_ptr<Derived1> *
        ]
meow.cpp(41): note: see reference to function template instantiation 'int std::ranges::_Count_fn::operator ()<std::vector<std::shared_ptr<Derived1>,std::allocator<std::shared_ptr<Derived1>>>&,int,int(__thiscall Derived1::* )(void)>(_Rng,const _Ty &,_Pj) const' being compiled
        with
        [
            _Rng=std::vector<std::shared_ptr<Derived1>,std::allocator<std::shared_ptr<Derived1>>> &,
            _Ty=int,
            _Pj=int (__thiscall Derived1::* )(void)
        ]
S:\GitHub\STL\out\build\x86\out\inc\algorithm(655): error C2120: 'void' illegal with all types

C:\Temp>clang-cl -m32 /EHsc /nologo /W4 /std:c++latest meow.cpp && meow
In file included from meow.cpp:1:
In file included from S:\GitHub\STL\out\build\x86\out\inc\algorithm:11:
In file included from S:\GitHub\STL\out\build\x86\out\inc\xmemory:16:
S:\GitHub\STL\out\build\x86\out\inc\xutility(193,16): error: called object type 'int (Derived1::*)()
      __attribute__((thiscall))' is not a function or function pointer
        return _Fn(_STD forward<_Args>(_Vals)...);
               ^~~
S:\GitHub\STL\out\build\x86\out\inc\type_traits(1502,21): note: in instantiation of function template specialization
      'std::_Ref_fn<int (Derived1::*)() __attribute__((thiscall))>::operator()<std::shared_ptr<Derived1> &>' requested
      here
        -> decltype(static_cast<_Callable&&>(_Obj)(static_cast<_Types&&>(_Args)...)) {
                    ^
S:\GitHub\STL\out\build\x86\out\inc\type_traits(1601,17): note: while substituting deduced template arguments into
      function template '_Call' [with _Callable = std::_Ref_fn<int (Derived1::*)() __attribute__((thiscall))> &, _Types
      = <std::shared_ptr<Derived1> &>]
    -> decltype(_Invoker1<_Callable, _Ty1>::_Call(
                ^
S:\GitHub\STL\out\build\x86\out\inc\algorithm(655,21): note: while substituting deduced template arguments into function
      template 'invoke' [with _Callable = std::_Ref_fn<int (Derived1::*)() __attribute__((thiscall))> &, _Ty1 =
      std::shared_ptr<Derived1> &, _Types2 = <>]
                if (_STD invoke(_Proj, *_First) == _Val) {
                    ^
S:\GitHub\STL\out\build\x86\out\inc\yvals_core.h(1217,20): note: expanded from macro '_STD'
#define _STD       ::std::
                   ^
S:\GitHub\STL\out\build\x86\out\inc\algorithm(642,20): note: in instantiation of function template specialization
      'std::ranges::_Count_fn::_Count_unchecked<std::shared_ptr<Derived1> *, std::shared_ptr<Derived1> *, int,
      std::_Ref_fn<int (Derived1::*)() __attribute__((thiscall))> >' requested here
            return _Count_unchecked(_Ubegin(_Range), _Uend(_Range), _Val, _Pass_fn(_Proj));
                   ^
meow.cpp(41,75): note: in instantiation of function template specialization
      'std::ranges::_Count_fn::operator()<std::vector<std::shared_ptr<Derived1>,
      std::allocator<std::shared_ptr<Derived1> > > &, int, int (Derived1::*)() __attribute__((thiscall))>' requested
      here
    cout << "ranges::count(vec, 1729, &Derived1::purr): " << ranges::count(vec, 1729, &Derived1::purr) << endl;
                                                                          ^
In file included from meow.cpp:1:
S:\GitHub\STL\out\build\x86\out\inc\algorithm(655,21): error: no matching function for call to 'invoke'
                if (_STD invoke(_Proj, *_First) == _Val) {
                    ^~~~~~~~~~~
S:\GitHub\STL\out\build\x86\out\inc\yvals_core.h(1217,20): note: expanded from macro '_STD'
#define _STD       ::std::
                   ^
S:\GitHub\STL\out\build\x86\out\inc\algorithm(642,20): note: in instantiation of function template specialization
      'std::ranges::_Count_fn::_Count_unchecked<std::shared_ptr<Derived1> *, std::shared_ptr<Derived1> *, int,
      std::_Ref_fn<int (Derived1::*)() __attribute__((thiscall))> >' requested here
            return _Count_unchecked(_Ubegin(_Range), _Uend(_Range), _Val, _Pass_fn(_Proj));
                   ^
meow.cpp(41,75): note: in instantiation of function template specialization
      'std::ranges::_Count_fn::operator()<std::vector<std::shared_ptr<Derived1>,
      std::allocator<std::shared_ptr<Derived1> > > &, int, int (Derived1::*)() __attribute__((thiscall))>' requested
      here
    cout << "ranges::count(vec, 1729, &Derived1::purr): " << ranges::count(vec, 1729, &Derived1::purr) << endl;
                                                                          ^
S:\GitHub\STL\out\build\x86\out\inc\type_traits(1598,19): note: candidate template ignored: substitution failure [with
      _Callable = std::_Ref_fn<int (Derived1::*)() __attribute__((thiscall))> &, _Ty1 = std::shared_ptr<Derived1> &,
      _Types2 = <>]: no matching function for call to '_Call'
_CONSTEXPR17 auto invoke(_Callable&& _Obj, _Ty1&& _Arg1, _Types2&&... _Args2) noexcept(
                  ^
S:\GitHub\STL\out\build\x86\out\inc\type_traits(1592,19): note: candidate function template not viable: requires single
      argument '_Obj', but 2 arguments were provided
_CONSTEXPR17 auto invoke(_Callable&& _Obj) noexcept(noexcept(static_cast<_Callable&&>(_Obj)()))
                  ^
2 errors generated.

[StephanTLavavej]

PMDs can also be larger than void*:

C:\Temp>type pmd.cpp

#include <iostream>
using namespace std;

struct Cat;

using PMD_Cat = int Cat::*;

struct Dog {
    PMD_Cat pmd_cat{nullptr};
    int d{11};
};

using PMD_Dog = int Dog::*;

struct Cat {
    PMD_Dog pmd_dog{nullptr};
    int c{22};
};

int main() {
    cout << "sizeof(PMD_Cat): " << sizeof(PMD_Cat) << endl;
    cout << "sizeof(PMD_Dog): " << sizeof(PMD_Dog) << endl;
}

C:\Temp>cl /EHsc /nologo /W4 pmd.cpp && pmd
pmd.cpp
sizeof(PMD_Cat): 12
sizeof(PMD_Dog): 4