tree b5a796b4818ae84ab7da235845b21f46fd6cfb91
parent 7ecf26c4148fd141741775347af89aa9c00a80bc
author Chris Bracken <cbracken@google.com> 1778478406 +0900
committer gn-scoped@luci-project-accounts.iam.gserviceaccount.com <gn-scoped@luci-project-accounts.iam.gserviceaccount.com> 1778489629 -0700

Fix PointerSet and BuilderRecordMap iterators under C++23

Adds explicit operator++() and operator++(int) overrides in
PointerSet::const_iterator, BuilderRecordMap::const_iterator, and the
unit test TestHashTable::const_iterator to satisfy weakly_incrementable
requirements. I've also updated documentation and sample custom iterator
implementations in src/gn/hash_table_base.h.

This fixes a compilation error that started with the update to C++23 in
88604adbcec2101f25b2e3ebd7f39b38163a6a33, which triggers the following
error (in my case: macOS 26.4.1 using Xcode 26.2) indicating that
PointerSet<const Target>::const_iterator fails to satisfy one of the
requirements of std::weakly_incrementable:

    ../src/gn/json_project_writer.cc:80:14: note: in instantiation of function template specialization 'std::vector<const Target *>::assign<PointerSet<const Target>::const_iterator, 0>' requested here
       80 |     targets->assign(target_set.begin(), target_set.end());
          |              ^
    /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/ranges_copy_n.h:64:3: note: candidate template ignored: constraints not satisfied [with _Ip = __libcpp_remove_reference_t<const_iterator &>, _Op = pointer]
       64 |   operator()(_Ip __first, iter_difference_t<_Ip> __n, _Op __result) const {
          |   ^
    /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/ranges_copy_n.h:61:13: note: because 'PointerSet<const Target>::const_iterator' does not satisfy 'input_iterator'
       61 |   template <input_iterator _Ip, weakly_incrementable _Op>
          |             ^
    /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/concepts.h:195:26: note: because 'PointerSet<const Target>::const_iterator' does not satisfy 'input_or_output_iterator'
      195 | concept input_iterator = input_or_output_iterator<_Ip> && indirectly_readable<_Ip> && requires {
          |                          ^
    /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/concepts.h:140:6: note: because 'PointerSet<const Target>::const_iterator' does not satisfy 'weakly_incrementable'
      140 | } && weakly_incrementable<_Ip>;
          |      ^
    /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/concepts.h:126:20: note: because type constraint 'same_as<HashTableBase<PointerSetNode>::NodeIterator &, PointerSet<const Target>::const_iterator &>' was not satisfied:
      126 |       { ++__i } -> same_as<_Ip&>; // not required to be equality-preserving
          |                    ^

It looks like the PointerSet<T> template class was originally introduced
in commit 0e7ed6358c5bdf4e2448f735d5d6cfa3b58af06a. Its custom
const_iterator subclasses NodeIterator directly without overriding
operator++ and operator++(int).

Specifically, when json_project_writer.cc calls
targets->assign(target_set.begin(), target_set.end()),
std::vector::asign() requires that its arguments staisfy
std::input_iterator, which in turn requires that it satisfy
std::input_or_output_iterator, which in turn requires
std::weakly_incrementable.

Looking at the requirements of std::weakly_incrementable, there are four
criteria (https://en.cppreference.com/cpp/iterator/weakly_incrementable):

  * std::movable<I>: must be moveable.
  * std::iter_difference<I>: must have a related signed integer type
    (such as std::ptrdiff_t) that represents the difference between two
    iterators.
  * { ++i } -> std::same_as<I&>: the pre-increment operator must exist
    and its return type must be I&. This is what we violated.
  * i++: The post-increment operator must exist. There's no requirement
    on return type, so no issue here.

Because PointerSet::const_iterator inherited operator++ from
NodeIterator, pre-incrementing returned NodeIterator& instead of
const_iterator&, it fails the concept check.

Change-Id: I425c4e153d7a087beaf37b10a2e519184b4801c3
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/22660
Reviewed-by: Takuto Ikuta <tikuta@google.com>
Reviewed-by: David Turner <digit@google.com>
Commit-Queue: David Turner <digit@google.com>