<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/81254>81254</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [libc++] `boyer_moore_searcher` and `boyer_moore_horspool_searcher` fail to accept ADL-incompatible element types
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            libc++
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          frederick-vs-ja
      </td>
    </tr>
</table>

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

```C++
#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});
}
```

Iterator operations in `unordered_map` (which supports both searchers) seem problematic.

https://github.com/llvm/llvm-project/blob/fcb59203c8b883aa39d22cf9788c48dbbb734932/libcxx/include/__functional/boyer_moore_searcher.h#L47

It seems that all standard library implementations suffer from similar problems ([Godbolt link](https://godbolt.org/z/Ta6PafcnK)).
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy0VE1v4zYQ_TX0ZRBDGurzoEMcr4qie-gh92D4IYu7lCiQVLLpry8oO7GT5lKgBQxZEmee3ryZeRSCOc1ad6w8sPK4ozWOzneD10p7I3_ePYe7H7QTTr12j6OGwVnrXsx8gsW7k6cJlNNhZlhHkG5ajNXwYuII1gjJ8MDwAGrVEB3cH7_Dy2jkCBSjnpYY0tuUZHXUQCBIQXxd9J5lR5bdX65Vdv49nNEub5GbWdpVaWD8gezJeRPHifFvX50P6yyjcTPZa8B2TTQsxS1IWgoBHt8jQvSrjDA6q7QHVl--DADwCJHxNyb18Xp_m2jmt9I-nZs5wkRmZtgwbD8iryFJ-0zWKIrOA-PHCwPGH24RvzG8f8dNmdecZ_KelYeclceEfcMvxTFsnp1R6cshKsbvGb8Pmrwc00lKxYcNAlLr8vT0Hifcq_ZPk3NeP51zNl7SzSFeCWzMvrH68AVafWTY_i98RufD4pz9T4ilx4_Td9vA36P2m9JuSTfGzQHMDKzK1tl5pb1WTxMtrMpSdeeRD-uyOB8DCBdHeOMYtrK1ntI2CasnikZ-GP8xxiWkarFn2J9MHFexl25i2Fv7_PZ3t3j3Q8vIsBfWCYb9IEXZYsZlI5qGE_FWIcqhrZtGFo0SQtS8aDkmACPkr18M-8vGMOyfnm5WBvuv-r4fGfLvRf1RmK2YAHGkCGQthEizIq-SHXjyr2DSAE96jhfdwjoM2sPg3QTBTMaSf9MiJPVYefjNKeFsBGvmn2mmsfkkyvl87_yJYf8Xw_6Rqj9pkPMfqafY7neq46rlLe10l9dZXbR5ldW7satz0irHqkaO-SAGnkkiratc1kORV2pnOsywyDBr8zLnWO-VrpuCt6VqauIlalZkeiJj96kNicLOhLDqrsmxLHaWhLZh81bEqyMyxOS1vtt6J9ZTYEVmTYjhChNNtJsr36SVxzRkX25hlQHN6vPxP5eiymAgY5PzkpR6icmW787OQtEIq0GfG7RZcdit3nb_egg3DQLDfpPh7wAAAP__WUL92A">