This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Ready status.

### 3769. `basic_const_iterator::operator==` causes infinite constraint recursion

Section: 25.5.3 [const.iterators] Status: Ready Submitter: Hewill Kang Opened: 2022-09-05 Last modified: 2022-11-10

Priority: 1

View all issues with Ready status.

Discussion:

Currently, `basic_const_iterator::operator==` is defined as a `friend` function:

>     template<sentinel_for<Iterator> S>
>       friend constexpr bool operator==(const basic_const_iterator& x, const S& s);

which only requires `S` to model `sentinel_for<Iterator>`, and since `basic_const_iterator` has a conversion constructor that accepts `I`, this will result in infinite constraint checks when comparing `basic_const_iterator<int*>` with `int*` (online example):

>     #include <iterator>

>     template<std::input_iterator I>
>     struct basic_const_iterator {
>       basic_const_iterator() = default;
>       basic_const_iterator(I);
>       template<std::sentinel_for<I> S>
>       friend bool operator==(const basic_const_iterator&, const S&);
>     };

>     static_assert(std::sentinel_for<basic_const_iterator<int*>, int*>); // infinite meta-recursion

That is, `sentinel_for` ends with `weakly-equality-comparable-with` and instantiates `operator==`, which in turn rechecks `sentinel_for` and instantiates the same `operator==`, making the circle closed.

The proposed resolution is to change `operator==` to be a member function so that `S` is no longer accidentally instantiated as `basic_const_iterator`. The same goes for `basic_const_iterator::operator-`.

[2022-09-23; Reflector poll]

Set priority to 1 after reflector poll.

"Although I am not a big fan of member ==, the proposed solution seems to be simple." "prefer if we would keep `operator==` as non-member for consistency."

Previous resolution from Hewill [SUPERSEDED]:

> This wording is relative to N4917.

> 1. Modify 25.5.3.3 [const.iterators.iterator], class template `basic_const_iterator` synopsis, as indicated:

>    >     namespace std {
>    >       template<class I>
>    >         concept not-a-const-iterator = see below;

>    >       template<input_iterator Iterator>
>    >       class basic_const_iterator {
>    >         Iterator current_ = Iterator();
>    >         using reference = iter_const_reference_t<Iterator>;         // exposition only

>    >       public:
>    >         […]
>    >         template<sentinel_for<Iterator> S>
>    >           friend constexpr bool operator==(const basic_const_iterator& x, const S& s) const;
>    >         […]
>    >         template<sized_sentinel_for<Iterator> S>
>    >           friend constexpr difference_type operator-(const basic_const_iterator& x, const S& y) const;
>    >         template<not-a-const-iteratorsized_sentinel_for<Iterator> S>
>    >           requires sized_sentinel_fordifferent-from<S, Iteratorbasic_const_iterator>
>    >           friend constexpr difference_type operator-(const S& x, const basic_const_iterator& y);
>    >       };
>    >     }

> 2. Modify 25.5.3.5 [const.iterators.ops] as indicated:

>    > […]

>    >       template<sentinel_for<Iterator> S>
>    >         friend constexpr bool operator==(const basic_const_iterator& x, const S& s) const;

>    > > -16- Effects: Equivalent to: `return x.current_ == s;`.

>    > […]

>    >       template<sized_sentinel_for<Iterator> S>
>    >         friend constexpr difference_type operator-(const basic_const_iterator& x, const S& y) const;

>    > > -24- Effects: Equivalent to: `return x.current_ - y;`.

>    >       template<not-a-const-iteratorsized_sentinel_for<Iterator> S>
>    >         requires sized_sentinel_fordifferent-from<S, Iteratorbasic_const_iterator>
>    >         friend constexpr difference_type operator-(const S& x, const basic_const_iterator& y);

>    > > -25- Effects: Equivalent to: `return x - y.current_;`.

[2022-11-04; Tomasz comments and improves proposed wording]

Initially, LWG requested an investigation of alternative resolutions that would avoid using member functions for the affected operators. Later, it was found that in addition to `==`/`-`, all comparison operators (`<`, `>`, `<=`, `>=`, `<=>`) are affected by same problem for the calls with `basic_const_iterator<basic_const_iterator<int*>>` and `int*` as arguments, i.e. `totally_ordered_with<basic_const_iterator<basic_const_iterator<int*>>, int*>` causes infinite recursion in constraint checking.

The new resolution, change all of the friends overloads for operators `==`, `<`, `>`, `<=`, `>=`, `<=>` and `-` that accept `basic_const_iterator` as lhs, to `const` member functions. This change is applied to homogeneous `(basic_const_iterator, basic_const_iterator)` for consistency. For the overload of `<`, `>`, `<=`, `>=` and `-` that accepts `(I, basic_const_iterator)` we declared them as friends and consistently constrain them with `not-const-iterator`. Finally, its put (now member) `operator`<=>`(I)` in the block with other heterogeneous overloads in the synopsis.

The use of member functions addresses issues, because:

- it disallows conversion to `basic_const_iterator` in the left-hand side of op, i.e. eliminates issues for `(sized_)sentinel_for<basic_const_iterator<int*>, int*>` and `totally_ordered<basic_const_iterator<int*>, int*>`
- member functions (in contrast to friends) are not found by ADL, so we do not get multiple candidates for `basic_const_iterator<basic_const_iterator<S>>`, so we address recursion for nested iterators

[Kona 2022-11-08; Move to Ready]

Proposed resolution:

This wording is relative to N4917.

1. Modify 25.5.3.3 [const.iterators.iterator], class template `basic_const_iterator` synopsis, as indicated:

   >     namespace std {
   >       template<class I>
   >         concept not-a-const-iterator = see below;

   >       template<input_iterator Iterator>
   >       class basic_const_iterator {
   >         Iterator current_ = Iterator();
   >         using reference = iter_const_reference_t<Iterator>;         // exposition only

   >       public:
   >         […]
   >         template<sentinel_for<Iterator> S>
   >           friend constexpr bool operator==(const basic_const_iterator& x, const S& s) const;

   >         friend constexpr bool operator<(const basic_const_iterator& x, const basic_const_iterator& y) const
   >           requires random_access_iterator<Iterator>;
   >         friend constexpr bool operator>(const basic_const_iterator& x, const basic_const_iterator& y) const
   >           requires random_access_iterator<Iterator>;
   >         friend constexpr bool operator<=(const basic_const_iterator& x, const basic_const_iterator& y) const
   >           requires random_access_iterator<Iterator>;
   >         friend constexpr bool operator>=(const basic_const_iterator& x, const basic_const_iterator& y) const
   >           requires random_access_iterator<Iterator>;
   >         friend constexpr auto operator<=>(const basic_const_iterator& x, const basic_const_iterator& y) const
   >           requires random_access_iterator<Iterator> && three_way_comparable<Iterator>;

   >         template<different-from<basic_const_iterator> I>
   >         friend constexpr bool operator<(const basic_const_iterator& x, const I& y) const
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >         template<different-from<basic_const_iterator> I>
   >         friend constexpr bool operator>(const basic_const_iterator& x, const I& y) const
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >         template<different-from<basic_const_iterator> I>
   >         friend constexpr bool operator<=(const basic_const_iterator& x, const I& y) const
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >         template<different-from<basic_const_iterator> I>
   >         friend constexpr bool operator>=(const basic_const_iterator& x, const I& y) const
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >         template<different-from<basic_const_iterator> I>
   >         constexpr auto operator<=>(const I& y) const
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I> &&
   >        	       three_way_comparable_with<Iterator, I>;
   >         template<not-a-const-iterator I>
   >         friend constexpr bool operator<(const I& y, const basic_const_iterator& x)
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >         template<not-a-const-iterator I>
   >         friend constexpr bool operator>(const I& y, const basic_const_iterator& x)
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >         template<not-a-const-iterator I>
   >         friend constexpr bool operator<=(const I& y, const basic_const_iterator& x)
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >         template<not-a-const-iterator I>
   >         friend constexpr bool operator>=(const I& y, const basic_const_iterator& x)
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >         template<different-from<basic_const_iterator> I>
   >         friend constexpr auto operator<=>(const basic_const_iterator& x, const I& y)
   >           requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I> &&
   >           	       three_way_comparable_with<Iterator, I>;

   >         […]
   >         template<sized_sentinel_for<Iterator> S>
   >           friend constexpr difference_type operator-(const basic_const_iterator& x, const S& y) const;
   >         template<not-a-const-iteratorsized_sentinel_for<Iterator> S>
   >           requires sized_sentinel_fordifferent-from<S, Iteratorbasic_const_iterator>
   >           friend constexpr difference_type operator-(const S& x, const basic_const_iterator& y);
   >       };
   >     }

2. Modify 25.5.3.5 [const.iterators.ops] as indicated:

   > […]

   >     template<sentinel_for<Iterator> S>
   >       friend constexpr bool operator==(const basic_const_iterator& x, const S& s) const;

   > > -16- Effects: Equivalent to: `return x.current_ == s;`

   >     friend constexpr bool operator<(const basic_const_iterator& x, const basic_const_iterator& y) const
   >       requires random_access_iterator<Iterator>;
   >     friend constexpr bool operator>(const basic_const_iterator& x, const basic_const_iterator& y) const
   >       requires random_access_iterator<Iterator>;
   >     friend constexpr bool operator<=(const basic_const_iterator& x, const basic_const_iterator& y) const
   >       requires random_access_iterator<Iterator>;
   >     friend constexpr bool operator>=(const basic_const_iterator& x, const basic_const_iterator& y) const
   >       requires random_access_iterator<Iterator>;
   >     friend constexpr auto operator<=>(const basic_const_iterator& x, const basic_const_iterator& y) const
   >       requires random_access_iterator<Iterator> && three_way_comparable<Iterator>;

   > > -17- Let op be the operator.

   > > -18- Effects: Equivalent to: `return x.current_ op y.current_;`

   >     template<different-from<basic_const_iterator> I>
   >     friend constexpr bool operator<(const basic_const_iterator& x, const I& y) const
   >       requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >     template<different-from<basic_const_iterator> I>
   >     friend constexpr bool operator>(const basic_const_iterator& x, const I& y) const
   >       requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >     template<different-from<basic_const_iterator> I>
   >     friend constexpr bool operator<=(const basic_const_iterator& x, const I& y) const
   >       requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >     template<different-from<basic_const_iterator> I>
   >     friend constexpr bool operator>=(const basic_const_iterator& x, const I& y) const
   >       requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;
   >     template<different-from<basic_const_iterator> I>
   >     friend constexpr auto operator<=>(const basic_const_iterator& x, const I& y) const
   >       requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I> &&
   >       	       three_way_comparable_with<Iterator, I>;

   > > -19- Let `op` be the operator.

   > > -20- Returns Effects: Equivalent to: `return x.current_ op y;`

   > […]

   >     template<sized_sentinel_for<Iterator> S>
   >       friend constexpr difference_type operator-(const basic_const_iterator& x, const S& y) const;

   > > -24- Effects: Equivalent to: `return x.current_ - y;`

   >     template<not-a-const-iteratorsized_sentinel_for<Iterator> S>
   >       requires sized_sentinel_fordifferent-from<S, Iteratorbasic_const_iterator>
   >       friend constexpr difference_type operator-(const S& x, const basic_const_iterator& y);

   > > -25- Effects: Equivalent to: `return x - y.current_;`