[Bug libstdc++/78346] [5/6/7 Regression] std::search with binary comparison predicate uses invalid reference

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78346

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.8.5
            Version|unknown                     |7.0
            Summary|std::search with binary     |[5/6/7 Regression]
                   |comparison predicate uses   |std::search with binary
                   |invalid reference           |comparison predicate uses
                   |                            |invalid reference
      Known to fail|                            |4.9.4, 5.4.0, 6.3.0, 7.0

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Actually, std::includes() doesn't use the problematic function objects that
store a reference, so there's no bug.

We do have a regression for this standalone testcase, which violates the
ForwardIterator requirements, but worked previously:

#include <algorithm>

struct bad_iterator
{
  typedef std::forward_iterator_tag iterator_category;
  typedef int value_type;
  typedef value_type const* pointer;
  typedef value_type const& reference;
  typedef std::ptrdiff_t difference_type;

  bad_iterator() : ptr(), stash() { }
  bad_iterator(pointer p) : ptr(p), stash() { update(); }
  bad_iterator(const bad_iterator& i) : ptr(i.ptr), stash() { update(); }
  ~bad_iterator() { ptr = 0; update(); }

  bad_iterator& operator=(const bad_iterator& i)
  {
    ptr = i.ptr;
    update();
    return *this;
  }

  bad_iterator& operator++() { ++ptr; update(); return *this; }
  bad_iterator operator++(int) { bad_iterator i = *this; ++*this; return i; }
  reference operator*() const { return *stash; }
  pointer operator->() const { return stash; }

  bool operator==(const bad_iterator& i) const { return ptr == i.ptr; }
  bool operator!=(const bad_iterator& i) const { return !(*this == i); }

private:
  void update()
  {
#ifdef VALID_FWD_ITER
    stash = ptr;
#else
    pointer p = 0;
    if (ptr)
      p = new value_type(*ptr);
    delete stash;
    stash = p;
#endif
  }

  pointer ptr;
  pointer stash;
};

int main() {
  int s[] = { 0, 1, 2, 3, 4, 5 };
  std::search(s, s+3, bad_iterator(s), bad_iterator(s+4));
}

This stopped working with GCC 4.9.0 when we added the __iter_comp_iter stuff
that stores the reference.

Technically this is invalid, but I think we can support it without too much
difficulty. That's reasonable given that std::filesystem::path::iterator also
violates the ForwardIterator requirements, and the Ranges TS removes the
reference-quality requirement anyway.