Issue 3769: basic_const_iterator::operator== causes infinite constraint recursion

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

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

Section: 25.5.3 [const.iterators] Status: WP Submitter: Hewill Kang Opened: 2022-09-05 Last modified: 2023-02-13

Priority: 1

View all other issues in [const.iterators].

View all issues with WP 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.

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

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]

[2023-02-13 Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4917.

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

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

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

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