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

Created on 2022-09-05.00:00:00 last changed 3 weeks ago

Messages

Date: 2022-11-10.23:33:23

Proposed resolution:

This wording is relative to n4917.

  1. 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);
      };
    }
    
  2. 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- ReturnsEffects: 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_;

Date: 2022-11-10.23:33:23

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

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

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.

  1. 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);
      };
    }
    
  2. 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_;.

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
2022-11-10 23:33:23adminsetmessages: + msg13010
2022-11-10 23:33:23adminsetmessages: + msg13009
2022-11-10 23:33:23adminsetstatus: new -> ready
2022-09-23 15:44:07adminsetmessages: + msg12802
2022-09-08 07:46:48adminsetmessages: + msg12753
2022-09-05 00:00:00admincreate