[Bug libstdc++/113851] New: boyer_moore_searcher and boyer_moore_horspool_searcher fail to accept ADL-incompatible element types

[Bug libstdc++/113851] New: boyer_moore_searcher and boyer_moore_horspool_searcher fail to accept ADL-incompatible element types

[de34 at live dot cn]

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

            Bug ID: 113851
           Summary: boyer_moore_searcher and boyer_moore_horspool_searcher
                    fail to accept ADL-incompatible element types
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Keywords: rejects-valid
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: de34 at live dot cn
  Target Milestone: ---

The following program doesn't compile with libc++ due to ADL which attempts to
complete a bad type.

```
#include <algorithm>
#include <functional>

template <class T>
struct holder {
    T t;
};

struct incomplete;

int main() {
    using validator = holder<incomplete>*;
    validator varr[1]{};
    (void) std::search(varr, varr + 1, std::boyer_moore_searcher<const
validator*>{varr, varr + 1});
    (void) std::search(varr, varr + 1, std::boyer_moore_horspool_searcher<const
validator*>{varr, varr + 1});
}
```

It seems that non-ADL-proof iterator operations are problematic, and all
standard library implementations suffer from similar problems
(https://godbolt.org/z/Ta6PafcnK).

[Bug libstdc++/113851] boyer_moore_searcher and boyer_moore_horspool_searcher fail to accept ADL-incompatible element types

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2024-02-09
             Status|UNCONFIRMED                 |NEW

[Bug libstdc++/113851] boyer_moore_searcher and boyer_moore_horspool_searcher fail to accept ADL-incompatible element types

[redi at gcc dot gnu.org]

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

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Ugh.

The problem is:

 1272 |         if (__iter == _M_bad_char.end())

which does ADL for operator==

In general there's no way to fix this, we *must* do ADL for iterator equality
comparisons (and other operators like operator* and operator++) because they
might be named member functions, or they might be built-in operators if the
iterator is a pointer.

In this case we *must* do ADL for operator== because it's a hidden friend so
there's no other way to find it. And if you can't test iterators for equality,
you can't really do anything useful with them (except for output iterators).

[Bug libstdc++/113851] boyer_moore_searcher and boyer_moore_horspool_searcher fail to accept ADL-incompatible element types

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
We fail much simpler cases too:

#include <algorithm>

template <class T>
struct holder {
    T t;
};

struct incomplete;

int main() {
    using validator = holder<incomplete>*;
    validator varr[1]{};
    (void) std::find(varr, varr + 1, nullptr);
}