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

Title: basic_const_iterator::operator== causes infinite constraint recursion
Status: c++23
Section: [const.iterators]
Submitter: Hewill Kang

Created on 2022-09-05.00:00:00 last changed 5 months ago

Messages

Date: 2023-02-13.10:17:57

Proposed resolution:

This wording is relative to n4917.

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

msg13010 (view)

Date: 2023-02-13.00:00:00

[ 2023-02-13 Approved at February 2023 meeting in Issaquah. Status changed: Voting → WP. ]

msg13009 (view)

Date: 2022-11-10.23:33:23

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

msg12802 (view)

Date: 2022-11-15.00:00:00

[ 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

msg12753 (view)

Date: 2022-09-15.00:00:00

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

msg12752 (view)

Date: 2022-09-05.00:00:00

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-.

History
Date	User	Action	Args
2023-11-22 15:47:43	admin	set	status: wp -> c++23
2023-02-13 10:17:57	admin	set	messages: + msg13356
2023-02-13 10:17:57	admin	set	status: voting -> wp
2023-02-06 15:33:48	admin	set	status: ready -> voting
2022-11-10 23:33:23	admin	set	messages: + msg13010
2022-11-10 23:33:23	admin	set	messages: + msg13009
2022-11-10 23:33:23	admin	set	status: new -> ready
2022-09-23 15:44:07	admin	set	messages: + msg12802
2022-09-08 07:46:48	admin	set	messages: + msg12753
2022-09-05 00:00:00	admin	create