1. Abstract
Ranges algorithms that take a function and a projection should, in the unary case, constrain the function to enable:
iter_value_t < It > x = * it ; f ( proj ( x ));
Instead they are constrained to allow:
iter_value_t < projected < I , Proj >> u = proj ( * it ); f ( u );
And likewise in the binary case. This is caused by the composition of indirect callable concepts
with
, seen for example in the constraints of
as
.
A fix is proposed that introduces a type-trait and makes a slight change to the definitions of the
indirect callable concepts, as well as
. The fix is a slight relaxation of
the algorithmic constraints in ranges that does not break ABI.
2. Revisions
2.1. R1
-
range-v3 PR now C++14 friendly, gcc implementation now exposition-only.
-
Cleanup wording.
-
Make
exposition-only.indirect_value_t -
Add note on P2248R4.
-
Bump
feature-test macro.__cpp_lib_ranges
2.2. R2
-
Fixup incorrect edits, and exposition-only syntax.
-
Ensure
can handle nestedindirect - value - t
s.projected
3. Problem
In [Niebler2015] Eric Niebler explains that the constraints put on the predicate of
must be strong enough to allow the algorithm to invoke it with a reference
formed to a copy of an element:
Sometimes the algorithms call the predicates with references, sometimes with values, and sometimes — like unique_copy — with a mix of both.
That iteration of
did not have projections. The current iteration of
has projections, and is specified as:
template < input_range R , weakly_incrementable O , class Proj = identity , indirect_equivalence_relation < projected < iterator_t < R > , Proj >> C = ranges :: equal_to > requires indirectly_copyable < iterator_t < R > , O > && ( forward_iterator < iterator_t < R >> || ( input_iterator < O > && same_as < range_value_t < R > , iter_value_t < O >> ) || indirectly_copyable_storable < iterator_t < R > , O > ) constexpr ranges :: unique_copy_result < borrowed_iterator_t < R > , O > ranges :: unique_copy ( R && r , O result , C comp = {}, Proj proj = {});
In [Revzin2022], Barry Revzin writes that projections are function adaptors, and do not change an algorithm. Projections as function adaptors is also discussed in ranges-v3/issues/233. In the unary case, projection is reduced to composition:
Put differently, every algorithm in the standard library that accepts a unary predicate and a projection, such that we havecan have its projection dropped without any loss of functionality because users can do the function composition themselves and invoke it as
algo (..., pred , proj ) .
algo (..., hof :: compose ( pred , proj )))
Yet the constraints put on the triplet of iterator, function and projection fail to express
projections as function adaptors. In the unary case they do not express
.
, for example, takes a unary function
. The definitions of
and
are:
template < class F , class I > concept indirectly_unary_invocable = indirectly_readable < I > && copy_constructible < F > && invocable < F & , iter_value_t < I >&> && invocable < F & , iter_reference_t < I >> && invocable < F & , iter_common_reference_t < I >> && common_reference_with < invoke_result_t < F & , iter_value_t < I >&> , invoke_result_t < F & , iter_reference_t < I >>> ;
template < indirectly_readable I , indirectly_regular_unary_invocable < I > Proj > struct projected { using value_type = remove_cvref_t < indirect_result_t < Proj & , I >> ; indirect_result_t < Proj & , I > operator * () const ; // not defined };
Where
is:
template < class F , class ... Is > requires ( indirectly_readable < Is > && ...) && invocable < F , iter_reference_t < Is > ... > using indirect_result_t = invoke_result_t < F , iter_reference_t < Is > ... > ;
The problematic constraint is
, which becomes
apparent when inlining the definition of
:
invocable < F & , remove_cvref_t < invoke_result_t < Proj & , iter_reference_t < I >> &>
The code that this constraint is supposed to enable, and the code it actually enables, for copying and a referencing algorithm is:
Algorithm | Expected | Actual |
---|---|---|
Referencing |
|
|
Copying |
|
|
None of the algorithms in ranges are constrained to contain
. They do not require a copyable
or movable
. Requiring copyability or movability would not be enough. One would also need to
somehow deal with the validity of
. There is no guarantee that the validity of
is not tied to
the element
. This was discussed in ranges-v3/issues/148,
and partially resolved by [P0740R0].
The actual consequence on user code seems small, as the malformed syntactic requirement of the constraint is often naturally covered. Valid, but perhaps rare, code will not compile or need work-arounds. In particular projections returning move-only types become problematic:
std :: ranges :: for_each ( std :: views :: iota ( 0 , 5 ), []( std :: unique_ptr < int > v ){ //Can’t be invoked with std::unique_ptr<int> & std :: cout << * v << std :: endl ; }, []( int v ){ return std :: make_unique < int > ( v ); });
4. Proposal
The proposal aims at a minimal fix. First an exposition-only type-trait is defined that
disambiguates between the
of an iterator and a projection:
template < indirectly_readable I > using indirect - value - t = see below ; // exposition only
The implementation technique is unspecified, but
must be
for an iterator and
for
. The indirect
callable concepts, as well as
are now redefined to use
instead of
, showcased here for
:
template < class F , class I > concept indirectly_unary_invocable = indirectly_readable < I > && copy_constructible < F > && invocable < F & , indirect - value - t < I > iter_value_t < I >& > && invocable < F & , iter_reference_t < I >> && invocable < F & , iter_common_reference_t < I >> && common_reference_with < invoke_result_t < F & , indirect - value - t < I > iter_value_t < I >& > , invoke_result_t < F & , iter_reference_t < I >>> ;
Note: In the event [P2248R4] is merged before this proposal, the
alias template of that
proposal should be redefined in terms of
as they compute
the same type and have the same semantics.
5. Implementation
This proposal has currently been implemented and tested with both ranges-v3 and libstdc++ (on the gcc-12 release branch) without any issues.
5.1. ranges-v3
ranges-v3 has a firewalled
(as proposed in [P2538R1]). Here the implementation uses a partial specialization that
is constrained on the existence of a "secret" nested alias declaration.
5.2. libstdc++
libstdc++ has not yet firewalled
, so here a simple partial specialization was used.
namespace __detail { template < typename _I > struct __indirect_value_impl { using type = iter_value_t < _I > & ; }; template < indirectly_readable _I > using __indirect_value_t = typename __detail :: __indirect_value_impl < _I >:: type ; template < weakly_incrementable _Iter , typename _Proj > struct __indirect_value_impl < projected < _Iter , _Proj >> { using type = invoke_result_t < _Proj & , iter_value_t < _Iter > &> ; }; } // namespace __detail
6. Wording
6.1. 17.3.2 Header <version> synopsis [version.synopsis]
Bump
with the value specified as usual (year and month of adoption).
#define __cpp_lib_ranges YYYYMML // also in // <algorithm>,<functional>,<iterator>,<memory>,<ranges>
6.2. 23.2 Header <iterator> synopsis [iterator.synopsis]
// [iterator.concepts], iterator concepts // [iterator.concept.readable], concept indirectly_readable template < class In > concept indirectly_readable = see below ; template < indirectly_ readable T > using indirect - value - t = see below ; // exposition only template < indirectly_ readable T > using iter_common_reference_t = common_reference_t < iter_reference_t < T > , indirect - value - t < T > iter_value_t < T >& > ;
6.3. 23.3.2.4 Indirect callable traits [indirectcallable.traits]
-
To implement algorithms taking projections, it is necessary to determine the projected type of an iterators value type. The exposition-only alias template
denotesindirect - value - t < T > -
ifinvoke_result_t < Proj & , indirect - value - t < I >>
namesT projected < I , Proj > -
and
otherwise.iter_value_t < T > &
-
6.4. 23.3.6.4 Indirect callables [indirectcallable.indirectinvocable]
namespace std { template < class F , class I > concept indirectly_unary_invocable = indirectly_readable < I > && copy_constructible < F > && invocable < F & , indirect - value - t < I > iter_value_t < I >& > && invocable < F & , iter_reference_t < I >> && invocable < F & , iter_common_reference_t < I >> && common_reference_with < invoke_result_t < F & , indirect - value - t < I > iter_value_t < I >& > , invoke_result_t < F & , iter_reference_t < I >>> ; template < class F , class I > concept indirectly_regular_unary_invocable = indirectly_readable < I > && copy_constructible < F > && regular_invocable < F & , indirect - value - t < I > iter_value_t < I >& > && regular_invocable < F & , iter_reference_t < I >> && regular_invocable < F & , iter_common_reference_t < I >> && common_reference_with < invoke_result_t < F & , indirect - value - t < I > iter_value_t < I >& > , invoke_result_t < F & , iter_reference_t < I >>> ; template < class F , class I > concept indirect_unary_predicate = indirectly_readable < I > && copy_constructible < F > && predicate < F & , indirect - value - t < I > iter_value_t < I >&> && predicate < F & , iter_reference_t < I >> && predicate < F & , iter_common_reference_t < I >> ; template < class F , class I1 , class I2 > concept indirect_binary_predicate = indirectly_readable < I1 > && indirectly_readable < I2 > && copy_constructible < F > && predicate < F & , indirect - value - t < I1 > iter_value_t < I1 >& , indirect - value - t < I2 > iter_value_t < I2 >& > && predicate < F & , indirect - value - t < I1 > iter_value_t < I1 >& , iter_reference_t < I2 >> && predicate < F & , iter_reference_t < I1 > , indirect - value - t < I2 > iter_value_t < I2 >&> && predicate < F & , iter_reference_t < I1 > , iter_reference_t < I2 >> && predicate < F & , iter_common_reference_t < I1 > , iter_common_reference_t < I2 >> ; template < class F , class I1 , class I2 = I1 > concept indirect_equivalence_relation = indirectly_readable < I1 > && indirectly_readable < I2 > && copy_constructible < F > && equivalence_relation < F & , indirect - value - t < I1 > iter_value_t < I1 >& , indirect - value - t < I2 > iter_value_t < I2 >& > && equivalence_relation < F & , indirect - value - t < I1 > iter_value_t < I1 >& , iter_reference_t < I2 >> && equivalence_relation < F & , iter_reference_t < I1 > , indirect - value - t < I2 > iter_value_t < I2 >& > && equivalence_relation < F & , iter_reference_t < I1 > , iter_reference_t < I2 >> && equivalence_relation < F & , iter_common_reference_t < I1 > , iter_common_reference_t < I2 >> ; template < class F , class I1 , class I2 = I1 > concept indirect_strict_weak_order = indirectly_readable < I1 > && indirectly_readable < I2 > && copy_constructible < F > && strict_weak_order < F & , indirect - value - t < I1 > iter_value_t < I1 >& , indirect - value - t < I2 > iter_value_t < I2 >& > && strict_weak_order < F & , indirect - value - t < I1 > iter_value_t < I1 >& , iter_reference_t < I2 >> && strict_weak_order < F & , iter_reference_t < I1 > , indirect - value - t < I2 > iter_value_t < I2 >& > && strict_weak_order < F & , iter_reference_t < I1 > , iter_reference_t < I2 >> && strict_weak_order < F & , iter_common_reference_t < I1 > , iter_common_reference_t < I2 >> ;
7. Acknowledgements
The author would like to thank Barry Revzin, Christopher Di Bella, Arthur O’Dwyer, Hui Xie and Tim Song for guidance.