3859. std::projected cannot handle proxy iterator

Section: 24.3.6.4 [projected] Status: Resolved Submitter: Hewill Kang Opened: 2023-01-24 Last modified: 2023-03-23

Priority: 3

View all other issues in [projected].

View all issues with Resolved status.

Discussion:

Currently, std::projected is heavily used in <algorithm> to transform the original iterator into a new readable type for concept checking, which has the following definition:

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
};

It provides the member type value_type, which is defined as the cvref-unqualified of a projection function applied to the reference of the iterator, this seems reasonable since this is how iterators are usually defined for the value type.

However, this does not apply to C++20 proxy iterators such as zip_view::iterator, we cannot obtain the tuple of value by simply removing the cvref-qualifier of the tuple of reference.
This incorrect definition allows us to unethically bypass the constraint checking of the constraint algorithm, for example:

#include <algorithm>
#include <ranges>
#include <vector>

struct Cmp {
  bool operator()(std::tuple<int&>, std::tuple<int&>) const;
  bool operator()(auto, auto) const = delete;
};

int main() {
  std::vector<int> v;
  std::ranges::sort(std::views::zip(v), Cmp{}); // hard error
}

In the above example, the value type and reference of the original iterator I are tuple<int> and tuple<int&> respectively, however, the value type and reference of projected<I, identity> will be tuple<int&> and tuple<int&>&&, which makes the constraint only require that the comparator can compare two tuple<int&>s, resulting in a hard error in the implementation.

[2023-02-06; Reflector poll]

Set priority to 3 after reflector poll.

Previous resolution [SUPERSEDED]:

This wording is relative to N4928.

[Drafting note: The proposed resolution is to alias projected as I when the projection function is exactly identity. This form of type aliasing has similarities to the proposed wording of P2538R1, except for the nested struct type. — end drafting note]

1. Modify 24.2 [iterator.synopsis], header <iterator> synopsis, as indicated:

   namespace std {
     […]
     // 24.3.6.4 [projected], projected
     template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
       usingstruct projected = see below;                         // freestanding
   
     template<weakly_incrementable I, class Proj>
       struct incrementable_traits<projected<I, Proj>>;           // freestanding
     […]
   }
   

2. Modify 24.3.6.4 [projected] as indicated:

   -1- Class template projected is used to constrain algorithms that accept callable objects and projections (3.43 [defns.projection]). It combines a indirectly_readable type I and a callable object type Proj into a new indirectly_readable type whose reference type is the result of applying Proj to the iter_reference_t of I.

   namespace std {
     template<classindirectly_readable I, classindirectly_regular_unary_invocable<I> Proj>
     struct projected-implprojected { // exposition only
       using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
       using difference_type = iter_difference_t<I>;               // present only if I models weakly_incrementable
       indirect_result_t<Proj&, I> operator*() const;              // not defined
     };
   
     template<weakly_incrementable I, class Proj>
     struct incrementable_traits<projected<I, Proj>> {
       using difference_type = iter_difference_t<I>;
     };
   
     template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
       using projected = conditional_t<same_as<Proj, identity>, I, projected-impl<I, Proj>>;
   }
   

[2023-03-22 Resolved by the adoption of P2609R3 in Issaquah. Status changed: New → Resolved.]

Proposed resolution: