Issue 3859: std::projected cannot handle proxy iterator

Title: std::projected cannot handle proxy iterator
Status: resolved
Section: [projected]
Submitter: Hewill Kang

Created on 2023-01-24.00:00:00 last changed 21 months ago

Messages

msg13269 (view)

Date: 2023-03-22.00:00:00

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

msg13219 (view)

Date: 2023-02-15.00:00:00

[ 2023-02-06; Reflector poll ]

Set priority to 3 after reflector poll.

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]

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

namespace std {
  […]
  // [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
  […]
}

Modify [projected] as indicated:

-1- Class template projected is used to constrain algorithms that accept callable objects and projections ([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>>;
}

msg13218 (view)

Date: 2023-01-24.00:00:00

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.

History
Date	User	Action	Args
2023-03-23 11:42:08	admin	set	status: new -> resolved
2023-02-06 15:13:50	admin	set	messages: + msg13269
2023-01-28 12:44:11	admin	set	messages: + msg13219
2023-01-24 00:00:00	admin	create