[libc++] Implement std::boyer_moore{, _horspool}_searcher

[philnik]

Summary

This mostly copys the <experimental/functional> stuff and updates the code to current libc++ style.

[• Quuxplusone]

Thanks for working on this! This will be super useful — not really to working programmers ;) but in terms of checking boxes for C++17 conformance and finally getting to remove the experimental versions!

libcxx/include/__functional/boyer_moore_searcher.h

35–40

Personally I'd prefer to see the first specialization here done as the primary template, and then we just have one specialization for _BMSkipTable<..., false>. I see it's less symmetric, but it eliminates a forward declaration (and ~7 LoC).

57

Likewise throughout. "All your ctors should be explicit unless they're used for implicit conversions" (or unless the Standard API mandates it :()

87

#include <__algorithm/fill_n.h>
Also, please prefer __table_.data() here. begin+end and data+size always go together as pairs, respectively. (It's also slightly cheaper to compile data than begin because raw pointers, but that's not the reason it raised the red flag for me.)

Actually, whoa, I thought this was our <vector> dependency, but it's not! This specialization should just use a plain old C array value_type __table_[256]; and cut out all the metaprogramming. This header shouldn't need to depend on <array> at all.
You might static_assert(numeric_limits<value_type>::max() < 256) just to be on the absolutely safe side.

123

Let's use __last - __first and save some instantiations. These are random-access iterators.

125

First reaction: Why depend on shared_ptr? Second reaction: Why two dereferences (one for the shared_ptr and another for the vector)? At the very least this should use make_shared<difference_type[]>(__pattern_length_ + 1).

But it would be awesome if we could eliminate the shared_ptr too, somehow. I assume it's in there because std::search wants to copy these things but we don't want the copy to be expensive.

Could we just make std::search not copy these things? And then it wouldn't matter if the copy was expensive, and we could just use std::vector<D> instead of std::shared_ptr<D[]>. (The copy ctor still needs to exist, IIUC, but it doesn't have to be fast, if we can claim it's the user's fault if they ever call it.)

187

As above, __last - __first — this is instantiated only with RAI and reverse_iterator<RAI>, both of which are random-access.

193

206–207

Nit: Should be if (__first == __last) or if (__count == 0), I'd think. size_t can't be negative.

libcxx/include/optional

165–167 ↗

(On Diff #413306)

This, and the diff in the <optional> test, looks unrelated to boyer_moore_searcher. Please do this in a separate PR (which I'll rubberstamp if CI is green).

[philnik]

libcxx/include/__functional/boyer_moore_searcher.h

35–40

Is that purely style or is there any technical reason to change it?

87

I think it's easier to read when using an array.

125

std::search doesn't copy this. It just gets a const ref and returns the search result. I'm not sure why you wouldn't just call the search directly, but hey. I'd argue that using std::shared_ptr<D[]> might be the better alternative, since after construction the elements will never change. And AFAIK it would be cheaper to copy and as cheap to move.

[philnik]

• Address comments

[philnik]

• generate files

[ldionne]

LGTM once CI is green and comments are addressed. I'm fine with the code not being perfect since we're basically copying it from <experimental/>. I'm fine (and actually prefer) making changes as follow-up patches.

libcxx/test/std/utilities/optional/optional.hash/enabled_hash.pass.cpp

28

Please add a release note mentioning that we will remove the experimental version in two releases, i.e. LLVM 17. And also mark the experimental feature as deprecated. This is documented in libcxx/docs/DesignDocs/ExperimentalFeatures.rst.

30

Can we tick some boxes in the status pages?

[philnik]

• Try to fix CI

[philnik]

libcxx/test/std/utilities/optional/optional.hash/enabled_hash.pass.cpp

30

No, we can't. It's part of library fundamentals, and I think not everything has been implemented yet. Maybe we should add a status page for that, because it's really hard to find out what is already implemented.

[philnik]

Rebase onto main

[philnik]

• Try to fix CI

[adamdebreceni]

libcxx/include/__functional/boyer_moore_searcher.h

209

shouldn't this be vector<difference_type>?

[philnik]

• Try to fix GCC

libcxx/include/__functional/boyer_moore_searcher.h

209

Why do you think it should be vector<difference_type>?

[adamdebreceni]

libcxx/include/__functional/boyer_moore_searcher.h

209

if value_type is signed and the range consists of e.g. the same values with length more than the max, __compute_bm_prefix will cause a signed overflow, moreover as __scratch can now contain negative values we could index out of __suffix_

[ldionne]

libcxx/include/__functional/boyer_moore_searcher.h

209

We should add a test and fix this bug in both this version and the experimental/functional version as well (even though we'll eventually remove that one).

[adamdebreceni]

libcxx/include/__functional/boyer_moore_searcher.h

209

if we plan on fixing the expirmental/functional we should add a +1 to the size in the _BMSkipTable array-based specialization typedef std::array<value_type, numeric_limits<unsigned_key_type>::max()> skip_map; otherwise we could index out of the array (not an issue in the new one)

[philnik]

• Add test and fix bug

[ldionne]

LGTM but please fix the experimental version too since it's so trivial.

libcxx/include/__functional/boyer_moore_searcher.h

209

This comment above was marked as done but wasn't done AFAICT.

[philnik]

• Rebased
• Address comments

[philnik]

• Try to fix CI

[philnik]

• Next try

[philnik]

• Try to fix CI

libcxx/docs/FeatureTestMacroTable.rst

.. table:: Current Status
     ``__cpp_lib_array_constexpr``                     ``201603L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_as_const``                            ``201510L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_atomic_is_always_lock_free``          ``201603L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_bool_constant``                       ``201505L``
     ------------------------------------------------- -----------------
-    ``__cpp_lib_boyer_moore_searcher``                *unimplemented*
+    ``__cpp_lib_boyer_moore_searcher``                ``201603L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_byte``                                ``201603L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_chrono``                              ``201611L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_clamp``                               ``201603L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_enable_shared_from_this``             ``201603L``

libcxx/docs/ReleaseNotes.rst

- The ``_LIBCPP_DISABLE_EXTERN_TEMPLATE`` macro is not honored anymore when defined by
   against the static version of libc++, which will result in no dependency being
   taken against the shared library.
 
 - The ``_LIBCPP_ENABLE_CXX20_REMOVED_ALLOCATOR_VOID_SPECIALIZATION`` macro has been added to allow
   re-enabling the ``allocator<void>`` specialization. When used in conjuction with
   ``_LIBCPP_ENABLE_CXX20_REMOVED_ALLOCATOR_MEMBERS``, this ensures that the members of
   ``allocator<void>`` removed in C++20 can be accessed.
 
+- The experimental versions of ``boyer_moore_searcher`` and ``boyer_moore_horspool_searcher``
+  will be removed in LLVM 17. You can disable the deprecation warnings by defining
+  ``_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS``.
+
 ABI Changes
 -----------
 
 - The ``_LIBCPP_ABI_USE_CXX03_NULLPTR_EMULATION`` macro controlling whether we use an
   emulation for ``std::nullptr_t`` in C++03 mode has been removed. After this change,
   ``_LIBCPP_ABI_USE_CXX03_NULLPTR_EMULATION`` will not be honoured anymore and there
   will be no way to opt back into the C++03 emulation of ``std::nullptr_t``.
 

libcxx/include/CMakeLists.txt

set(files
   __format/parser_std_format_spec.h
   __functional/binary_function.h
   __functional/binary_negate.h
   __functional/bind.h
   __functional/bind_back.h
   __functional/bind_front.h
   __functional/binder1st.h
   __functional/binder2nd.h
+  __functional/boyer_moore_searcher.h
   __functional/compose.h
   __functional/default_searcher.h
   __functional/function.h
   __functional/hash.h
   __functional/identity.h
   __functional/invoke.h
   __functional/is_transparent.h
   __functional/mem_fn.h

libcxx/include/__config

 
 // Deprecation macros.
 //
 // Deprecations warnings are always enabled, except when users explicitly opt-out
 // by defining _LIBCPP_DISABLE_DEPRECATION_WARNINGS.
 #  if !defined(_LIBCPP_DISABLE_DEPRECATION_WARNINGS)
 #    if __has_attribute(deprecated)
 #      define _LIBCPP_DEPRECATED __attribute__((deprecated))
+#      define _LIBCPP_DEPRECATED_(m) __attribute__((deprected(m)))
 #    elif _LIBCPP_STD_VER > 11
 #      define _LIBCPP_DEPRECATED [[deprecated]]
+#      define _LIBCPP_DEPRECATED_(m) [[deprecated(m)]]
 #    else
 #      define _LIBCPP_DEPRECATED
+#      define _LIBCPP_DEPRECATED_(m)
 #    endif
 #  else
 #    define _LIBCPP_DEPRECATED
+#    define _LIBCPP_DEPRECATED_(m)
 #  endif
 
 #  if !defined(_LIBCPP_CXX03_LANG)
 #    define _LIBCPP_DEPRECATED_IN_CXX11 _LIBCPP_DEPRECATED
 #  else
 #    define _LIBCPP_DEPRECATED_IN_CXX11
 #  endif
 

 
 #  if __has_attribute(no_destroy)
 #    define _LIBCPP_NO_DESTROY __attribute__((__no_destroy__))
 #  else
 #    define _LIBCPP_NO_DESTROY
 #  endif
 
 #  ifndef _LIBCPP_HAS_NO_ASAN
-extern "C" _LIBCPP_FUNC_VIS void __sanitizer_annotate_contiguous_container(const void*, const void*, const void*,
-                                                                           const void*);
+    extern "C" _LIBCPP_FUNC_VIS void
+    __sanitizer_annotate_contiguous_container(const void*, const void*, const void*, const void*);
 #  endif
 
 // Try to find out if RTTI is disabled.
 #  if defined(_LIBCPP_COMPILER_CLANG_BASED) && !__has_feature(cxx_rtti)
 #    define _LIBCPP_NO_RTTI
 #  elif defined(__GNUC__) && !defined(__GXX_RTTI)
 #    define _LIBCPP_NO_RTTI
 #  elif defined(_LIBCPP_COMPILER_MSVC) && !defined(_CPPRTTI)

libcxx/include/__functional/boyer_moore_searcher.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H
+#define _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#include <__algorithm/fill_n.h>
+#include <__config>
+#include <__functional/hash.h>
+#include <__functional/operations.h>
+#include <__iterator/distance.h>
+#include <__iterator/iterator_traits.h>
+#include <__memory/shared_ptr.h>
+#include <__utility/pair.h>
+#include <array>
+#include <unordered_map>
+#include <vector>
+
+#if _LIBCPP_STD_VER > 14
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Key,
+          class _Value,
+          class _Hash,
+          class _BinaryPredicate,
+          bool /*useArray*/>
+class _BMSkipTable;
+
+// General case for BM data searching; use a map
+template <class _Key,
+          class _Value,
+          class _Hash,
+          class _BinaryPredicate>
+class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> {
+private:
+  using value_type = _Value;
+  using key_type = _Key;
+
+  const value_type __default_value_;
+  unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table_;
+
+public:
+  _LIBCPP_HIDE_FROM_ABI
+  explicit _BMSkipTable(size_t __sz, value_type __default_value, _Hash __hash, _BinaryPredicate __pred)
+      : __default_value_(__default_value),
+        __table_(__sz, __hash, __pred) {}
+
+  _LIBCPP_HIDE_FROM_ABI void insert(const key_type& __key, value_type __val) {
+    __table_[__key] = __val;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI value_type operator[](const key_type& __key) const {
+    auto __it = __table_.find(__key);
+    return __it == __table_.end() ? __default_value_ : __it->second;
+  }
+};
+
+// Special case small numeric values; use an array
+template <class _Key,
+          class _Value,
+          class _Hash,
+          class _BinaryPredicate>
+class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {
+private:
+  using value_type = _Value;
+  using key_type = _Key;
+
+  using unsigned_key_type = make_unsigned_t<key_type>;
+  std::array<value_type, 256> __table_;
+  static_assert(numeric_limits<unsigned_key_type>::max() < 256);
+
+public:
+  _LIBCPP_HIDE_FROM_ABI explicit _BMSkipTable(size_t, value_type __default_value, _Hash, _BinaryPredicate) {
+    std::fill_n(__table_.data(), __table_.size(), __default_value);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI void insert(key_type __key, value_type __val) {
+    __table_[static_cast<unsigned_key_type>(__key)] = __val;
+  }
+
+  _LIBCPP_HIDE_FROM_ABI value_type operator[](key_type __key) const {
+    return __table_[static_cast<unsigned_key_type>(__key)];
+  }
+};
+
+template <class _RandomAccessIterator1,
+          class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
+          class _BinaryPredicate = equal_to<>>
+class _LIBCPP_TEMPLATE_VIS boyer_moore_searcher {
+private:
+  using difference_type = typename std::iterator_traits<_RandomAccessIterator1>::difference_type;
+  using value_type = typename std::iterator_traits<_RandomAccessIterator1>::value_type;
+  using __skip_table_type = _BMSkipTable<value_type,
+                                         difference_type,
+                                         _Hash,
+                                         _BinaryPredicate,
+                                         is_integral_v<value_type>
+                                      && sizeof(value_type) == 1
+                                      && is_same_v<_Hash, hash<value_type>>
+                                      && is_same_v<_BinaryPredicate, equal_to<>>>;
+
+public:
+  boyer_moore_searcher(_RandomAccessIterator1 __first,
+                       _RandomAccessIterator1 __last,
+                       _Hash __hash = _Hash(),
+                       _BinaryPredicate __pred = _BinaryPredicate())
+    : __first_(__first),
+      __last_(__last),
+      __pred_(__pred),
+      __pattern_length_(__last - __first),
+      __skip_table_(std::make_shared<__skip_table_type>(__pattern_length_, -1, __hash, __pred_)),
+      __suffix_(std::__allocate_shared_unbounded_array<difference_type[]>(
+          allocator<difference_type>(), __pattern_length_ + 1)) {
+    difference_type __i = 0;
+    while (__first != __last) {
+      __skip_table_->insert(*__first, __i);
+      ++__first;
+      ++__i;
+    }
+    __build_suffix_table(__first_, __last_, __pred_);
+  }
+
+  template <class _RandomAccessIterator2>
+  pair<_RandomAccessIterator2, _RandomAccessIterator2>
+  operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const {
+    static_assert(__is_same_uncvref<typename iterator_traits<_RandomAccessIterator1>::value_type,
+                                    typename iterator_traits<_RandomAccessIterator2>::value_type>::value,
+                  "Corpus and Pattern iterators must point to the same type");
+    if (__first == __last)
+      return std::make_pair(__last, __last);
+    if (__first_ == __last_)
+      return std::make_pair(__first, __first);
+
+    if (__pattern_length_ > (__last - __first))
+      return std::make_pair(__last, __last);
+    return __search(__first, __last);
+  }
+
+private:
+  _RandomAccessIterator1 __first_;
+  _RandomAccessIterator1 __last_;
+  _BinaryPredicate __pred_;
+  difference_type __pattern_length_;
+  shared_ptr<__skip_table_type> __skip_table_;
+  shared_ptr<difference_type[]> __suffix_;
+
+  template <class _RandomAccessIterator2>
+  pair<_RandomAccessIterator2, _RandomAccessIterator2>
+  __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const {
+    _RandomAccessIterator2 __current = __f;
+    const _RandomAccessIterator2 __last = __l - __pattern_length_;
+    const __skip_table_type& __skip_table = *__skip_table_;
+
+    while (__current <= __last) {
+      difference_type __j = __pattern_length_;
+      while (__pred_(__first_[__j - 1], __current[__j - 1])) {
+        --__j;
+        if (__j == 0)
+          return std::make_pair(__current, __current + __pattern_length_);
+      }
+
+      difference_type __k = __skip_table[__current[__j - 1]];
+      difference_type __m = __j - __k - 1;
+      if (__k < __j && __m > __suffix_[__j])
+        __current += __m;
+      else
+        __current += __suffix_[__j];
+    }
+    return std::make_pair(__l, __l);
+  }
+
+  template <class _Iterator, class _Container>
+  void __compute_bm_prefix(_Iterator __first, _Iterator __last, _BinaryPredicate __pred, _Container& __prefix) {
+    const size_t __count = __last - __first;
+
+    __prefix[0] = 0;
+    size_t __k = 0;
+
+    for (size_t __i = 1; __i != __count; ++__i) {
+      while (__k > 0 && !__pred(__first[__k], __first[__i]))
+        __k = __prefix[__k - 1];
+
+      if (__pred(__first[__k], __first[__i]))
+        ++__k;
+      __prefix[__i] = __k;
+    }
+  }
+
+  void __build_suffix_table(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _BinaryPredicate __pred) {
+    const size_t __count = __last - __first;
+
+    if (__count == 0)
+      return;
+
+    vector<difference_type> __scratch(__count);
+
+    __compute_bm_prefix(__first, __last, __pred, __scratch);
+    for (size_t __i = 0; __i <= __count; ++__i)
+      __suffix_[__i] = __count - __scratch[__count - 1];
+
+    using _ReverseIter = reverse_iterator<_RandomAccessIterator1>;
+    __compute_bm_prefix(_ReverseIter(__last), _ReverseIter(__first), __pred, __scratch);
+
+    for (size_t __i = 0; __i != __count; ++__i) {
+      const size_t __j = __count - __scratch[__i];
+      const difference_type __k = __i - __scratch[__i] + 1;
+
+      if (__suffix_[__j] > __k)
+        __suffix_[__j] = __k;
+    }
+  }
+};
+
+template <class _RandomAccessIterator1,
+          class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
+          class _BinaryPredicate = equal_to<>>
+class _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher {
+private:
+  using difference_type = typename iterator_traits<_RandomAccessIterator1>::difference_type;
+  using value_type = typename iterator_traits<_RandomAccessIterator1>::value_type;
+  using __skip_table_type = _BMSkipTable<value_type,
+                                         difference_type,
+                                         _Hash,
+                                         _BinaryPredicate,
+                                         is_integral_v<value_type>
+                                      && sizeof(value_type) == 1
+                                      && is_same_v<_Hash, hash<value_type>>
+                                      && is_same_v<_BinaryPredicate, equal_to<>>>;
+public:
+  boyer_moore_horspool_searcher(_RandomAccessIterator1 __first,
+                                _RandomAccessIterator1 __last,
+                                _Hash __hash = _Hash(),
+                                _BinaryPredicate __pred = _BinaryPredicate())
+    : __first_(__first),
+      __last_(__last),
+      __pred_(__pred),
+      __pattern_length_(__last - __first),
+      __skip_table_(std::make_shared<__skip_table_type>(__pattern_length_, __pattern_length_, __hash, __pred_)) {
+    if (__first == __last)
+      return;
+    --__last;
+    difference_type __i = 0;
+    while (__first != __last) {
+      __skip_table_->insert(*__first, __pattern_length_ - 1 - __i);
+      ++__first;
+      ++__i;
+    }
+  }
+
+  template <class _RandomAccessIterator2>
+  pair<_RandomAccessIterator2, _RandomAccessIterator2>
+  operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const {
+    static_assert(__is_same_uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type,
+                                    typename std::iterator_traits<_RandomAccessIterator2>::value_type>::value,
+                  "Corpus and Pattern iterators must point to the same type");
+    if (__first == __last)
+      return std::make_pair(__last, __last);
+    if (__first_ == __last_)
+      return std::make_pair(__first, __first);
+
+    if (__pattern_length_ > __last - __first)
+      return std::make_pair(__last, __last);
+
+    return __search(__first, __last);
+  }
+
+private:
+  _RandomAccessIterator1 __first_;
+  _RandomAccessIterator1 __last_;
+  _BinaryPredicate __pred_;
+  difference_type __pattern_length_;
+  shared_ptr<__skip_table_type> __skip_table_;
+
+  template <class _RandomAccessIterator2>
+  pair<_RandomAccessIterator2, _RandomAccessIterator2>
+  __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const {
+    _RandomAccessIterator2 __current = __f;
+    const _RandomAccessIterator2 __last = __l - __pattern_length_;
+    const __skip_table_type& __skip_table = *__skip_table_;
+
+    while (__current <= __last) {
+      difference_type __j = __pattern_length_;
+      while (__pred_(__first_[__j - 1], __current[__j - 1])) {
+        --__j;
+        if (__j == 0)
+          return std::make_pair(__current, __current + __pattern_length_);
+      }
+      __current += __skip_table[__current[__pattern_length_ - 1]];
+    }
+    return std::make_pair(__l, __l);
+  }
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP_STD_VER > 14
+
+#endif // _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H

libcxx/include/experimental/functional

 #  pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_LFTS
 
+#ifdef _LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
+#  define _LIBCPP_DEPRECATED_DEFAULT_SEARCHER
+#  define _LIBCPP_DEPRECATED_BOYER_MOORE_SEARCHER
+#  define _LIBCPP_DEPRECATED_BOYER_MOORE_HORSPOOL_SEARCHER
+#else
+#  define _LIBCPP_DEPRECATED_DEFAULT_SEARCHER _LIBCPP_DEPRECATED_("std::exprerimental::default_searcher will be removed in LLVM 17. Use std::default_searcher instead")
+#  define _LIBCPP_DEPRECATED_BOYER_MOORE_SEARCHER _LIBCPP_DEPRECATED_("std::exprerimental::boyer_moore_searcher will be removed in LLVM 17. Use std::boyer_moore_searcher instead")
+#  define _LIBCPP_DEPRECATED_BOYER_MOORE_HORSPOOL_SEARCHER _LIBCPP_DEPRECATED_("std::exprerimental::boyer_moore_horspool_searcher will be removed in LLVM 17. Use std::boyer_moore_horspool_searcher instead")
+#endif
+
 #if _LIBCPP_STD_VER > 11
 // default searcher
 template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
-class _LIBCPP_TEMPLATE_VIS default_searcher {
+class _LIBCPP_DEPRECATED_DEFAULT_SEARCHER _LIBCPP_TEMPLATE_VIS default_searcher {
 public:
     _LIBCPP_INLINE_VISIBILITY
     default_searcher(_ForwardIterator __f, _ForwardIterator __l,
                        _BinaryPredicate __p = _BinaryPredicate())
         : __first_(__f), __last_(__l), __pred_(__p) {}
 
     template <typename _ForwardIterator2>
     _LIBCPP_INLINE_VISIBILITY
     pair<_ForwardIterator2, _ForwardIterator2>
     operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const
     {
         return _VSTD::__search(__f, __l, __first_, __last_, __pred_,
             typename iterator_traits<_ForwardIterator>::iterator_category(),
             typename iterator_traits<_ForwardIterator2>::iterator_category());
     }
 
 private:
     _ForwardIterator __first_;
     _ForwardIterator __last_;
     _BinaryPredicate __pred_;
     };
 
 template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
-_LIBCPP_INLINE_VISIBILITY
+_LIBCPP_DEPRECATED_DEFAULT_SEARCHER _LIBCPP_INLINE_VISIBILITY
 default_searcher<_ForwardIterator, _BinaryPredicate>
 make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ())
 {
     return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p);
 }
 
 template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable;
 

 //  Special case small numeric values; use an array
 template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>
 class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {
 private:
     typedef _Value value_type;
     typedef _Key   key_type;
 
     typedef typename make_unsigned<key_type>::type unsigned_key_type;
-    typedef std::array<value_type, numeric_limits<unsigned_key_type>::max()> skip_map;
+    typedef std::array<value_type, 256> skip_map;
     skip_map __table;
 
 public:
     _LIBCPP_INLINE_VISIBILITY
     _BMSkipTable(size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/)
     {
         std::fill_n(__table.begin(), __table.size(), __default);
     }
value_type operator [](key_type __key) const
         return __table[static_cast<unsigned_key_type>(__key)];
     }
 };
 
 
 template <class _RandomAccessIterator1,
           class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
           class _BinaryPredicate = equal_to<>>
-class _LIBCPP_TEMPLATE_VIS boyer_moore_searcher {
+class _LIBCPP_DEPRECATED_BOYER_MOORE_SEARCHER _LIBCPP_TEMPLATE_VIS boyer_moore_searcher {
 private:
     typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;
     typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type      value_type;
     typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,
                     is_integral<value_type>::value && // what about enums?
                     sizeof(value_type) == 1 &&
                     is_same<_Hash, hash<value_type>>::value &&
                     is_same<_BinaryPredicate, equal_to<>>::value
private:
 
     void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
                                                     _BinaryPredicate __pred)
     {
         const size_t __count = _VSTD::distance(__f, __l);
         vector<difference_type> & __suffix = *__suffix_.get();
         if (__count > 0)
         {
-            vector<value_type> __scratch(__count);
+            vector<difference_type> __scratch(__count);
 
             __compute_bm_prefix(__f, __l, __pred, __scratch);
             for ( size_t __i = 0; __i <= __count; __i++ )
                 __suffix[__i] = __count - __scratch[__count-1];
 
             typedef reverse_iterator<_RandomAccessIterator1> _RevIter;
             __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch);
 
             for ( size_t __i = 0; __i < __count; __i++ )
             {
                 const size_t     __j = __count - __scratch[__i];
                 const difference_type __k = __i     - __scratch[__i] + 1;
 
                 if (__suffix[__j] > __k)
                     __suffix[__j] = __k;
             }
         }
     }
 
 };
 
 template<class _RandomAccessIterator,
          class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
          class _BinaryPredicate = equal_to<>>
-_LIBCPP_INLINE_VISIBILITY
+_LIBCPP_DEPRECATED_BOYER_MOORE_SEARCHER _LIBCPP_INLINE_VISIBILITY
 boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
 make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
                     _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())
 {
     return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);
 }
 
 // boyer-moore-horspool
 template <class _RandomAccessIterator1,
           class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
           class _BinaryPredicate = equal_to<>>
-class _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher {
+class _LIBCPP_DEPRECATED_BOYER_MOORE_HORSPOOL_SEARCHER _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher {
 private:
     typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;
     typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type      value_type;
     typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,
                     is_integral<value_type>::value && // what about enums?
                     sizeof(value_type) == 1 &&
                     is_same<_Hash, hash<value_type>>::value &&
                     is_same<_BinaryPredicate, equal_to<>>::value
__search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const {
 
         return make_pair(__l, __l);
     }
 };
 
 template<class _RandomAccessIterator,
          class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
          class _BinaryPredicate = equal_to<>>
-_LIBCPP_INLINE_VISIBILITY
+_LIBCPP_DEPRECATED_BOYER_MOORE_HORSPOOL_SEARCHER _LIBCPP_INLINE_VISIBILITY
 boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
 make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
                     _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())
 {
     return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);
 }
 
 #endif // _LIBCPP_STD_VER > 11
 
 _LIBCPP_END_NAMESPACE_LFTS
 
 _LIBCPP_POP_MACROS
 
 #endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */

libcxx/include/functional

 #include <__debug>
 #include <__functional/binary_function.h> // TODO: deprecate
 #include <__functional/binary_negate.h>
 #include <__functional/bind.h>
 #include <__functional/bind_back.h>
 #include <__functional/bind_front.h>
 #include <__functional/binder1st.h>
 #include <__functional/binder2nd.h>
+#include <__functional/boyer_moore_searcher.h>
 #include <__functional/compose.h>
 #include <__functional/default_searcher.h>
 #include <__functional/function.h>
 #include <__functional/hash.h>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/mem_fn.h> // TODO: deprecate
 #include <__functional/mem_fun_ref.h>

libcxx/include/module.modulemap.in

module functional {
     module __functional {
       module binary_function            { private header "__functional/binary_function.h" }
       module binary_negate              { private header "__functional/binary_negate.h" }
       module bind                       { private header "__functional/bind.h" }
       module bind_back                  { private header "__functional/bind_back.h" }
       module bind_front                 { private header "__functional/bind_front.h" }
       module binder1st                  { private header "__functional/binder1st.h" }
       module binder2nd                  { private header "__functional/binder2nd.h" }
+      module boyer_moore_searcher       { private header "__functional/boyer_moore_searcher.h" }
       module compose                    { private header "__functional/compose.h" }
       module default_searcher           { private header "__functional/default_searcher.h" }
       module function                   { private header "__functional/function.h" }
       module hash                       { private header "__functional/hash.h" }
       module identity                   { private header "__functional/identity.h" }
       module invoke                     { private header "__functional/invoke.h" }
       module is_transparent             { private header "__functional/is_transparent.h" }
       module mem_fn                     { private header "__functional/mem_fn.h" }

libcxx/include/version

 # define __cpp_lib_addressof_constexpr                  201603L
 # define __cpp_lib_allocator_traits_is_always_equal     201411L
 # define __cpp_lib_any                                  201606L
 # define __cpp_lib_apply                                201603L
 # define __cpp_lib_array_constexpr                      201603L
 # define __cpp_lib_as_const                             201510L
 # define __cpp_lib_atomic_is_always_lock_free           201603L
 # define __cpp_lib_bool_constant                        201505L
-// # define __cpp_lib_boyer_moore_searcher                 201603L
+# define __cpp_lib_boyer_moore_searcher                 201603L
 # define __cpp_lib_byte                                 201603L
 # define __cpp_lib_chrono                               201611L
 # define __cpp_lib_clamp                                201603L
 # define __cpp_lib_enable_shared_from_this              201603L
 // # define __cpp_lib_execution                            201603L
 # if !defined(_LIBCPP_AVAILABILITY_DISABLE_FTM___cpp_lib_filesystem)
 #   define __cpp_lib_filesystem                         201703L
 # endif

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__format/parser_std_format_spec.h> // expected-error@*:* {{use of private header from outside its module: '__format/parser_std_format_spec.h'}}
 #include <__functional/binary_function.h> // expected-error@*:* {{use of private header from outside its module: '__functional/binary_function.h'}}
 #include <__functional/binary_negate.h> // expected-error@*:* {{use of private header from outside its module: '__functional/binary_negate.h'}}
 #include <__functional/bind.h> // expected-error@*:* {{use of private header from outside its module: '__functional/bind.h'}}
 #include <__functional/bind_back.h> // expected-error@*:* {{use of private header from outside its module: '__functional/bind_back.h'}}
 #include <__functional/bind_front.h> // expected-error@*:* {{use of private header from outside its module: '__functional/bind_front.h'}}
 #include <__functional/binder1st.h> // expected-error@*:* {{use of private header from outside its module: '__functional/binder1st.h'}}
 #include <__functional/binder2nd.h> // expected-error@*:* {{use of private header from outside its module: '__functional/binder2nd.h'}}
+#include <__functional/boyer_moore_searcher.h> // expected-error@*:* {{use of private header from outside its module: '__functional/boyer_moore_searcher.h'}}
 #include <__functional/compose.h> // expected-error@*:* {{use of private header from outside its module: '__functional/compose.h'}}
 #include <__functional/default_searcher.h> // expected-error@*:* {{use of private header from outside its module: '__functional/default_searcher.h'}}
 #include <__functional/function.h> // expected-error@*:* {{use of private header from outside its module: '__functional/function.h'}}
 #include <__functional/hash.h> // expected-error@*:* {{use of private header from outside its module: '__functional/hash.h'}}
 #include <__functional/identity.h> // expected-error@*:* {{use of private header from outside its module: '__functional/identity.h'}}
 #include <__functional/invoke.h> // expected-error@*:* {{use of private header from outside its module: '__functional/invoke.h'}}
 #include <__functional/is_transparent.h> // expected-error@*:* {{use of private header from outside its module: '__functional/is_transparent.h'}}
 #include <__functional/mem_fn.h> // expected-error@*:* {{use of private header from outside its module: '__functional/mem_fn.h'}}

libcxx/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/default.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // boyer_moore searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_searcher {

 //   Hash                  hash_;      // exposition only
 //   BinaryPredicate       pred_;      // exposition only
 // };
 
 
 #include <experimental/algorithm>
 #include <experimental/functional>
 #include <cassert>
+#include <string>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 template <typename Iter1, typename Iter2>
 void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result) {
     std::experimental::boyer_moore_searcher<Iter2> s{b2, e2};
     assert(result == std::experimental::search(b1, e1, s));
test2()
     do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3));
     char ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
     const unsigned sj = sizeof(ij)/sizeof(ij[0]);
     char ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
     const unsigned sk = sizeof(ik)/sizeof(ik[0]);
     do_search(Iter1(ij), Iter1(ij+sj), Iter2(ik), Iter2(ik+sk), Iter1(ij+6));
 }
 
+template <class Iter1, class Iter2>
+void test_large_str() {
+    std::vector<signed char> data(257, 'a');
+    data[254] = 'b';
+    data[255] = 'b';
+    data[256] = 'b';
+    const signed char find[] = {'b', 'b', 'b'};
+    do_search(Iter1(data.data()), Iter1(data.data() + data.size()),
+              Iter2(find), Iter2(find + 3),
+              Iter1(data.data() + 254));
+}
+
+void test_custom_pred() {
+    std::string long_string(1024, '0');
+    std::boyer_moore_searcher searcher(std::begin(long_string), std::end(long_string));
+    const char str[] = "1234";
+    auto ret = searcher(std::begin(str), std::end(str));
+    assert(ret.first == std::end(str));
+    assert(ret.second == std::end(str));
+}
+
 int main(int, char**) {
     test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
     test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+    test_large_str<random_access_iterator<const signed char*>, random_access_iterator<const signed char*>>();
+    test_custom_pred();
 
   return 0;
 }

libcxx/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // boyer_moore searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_searcher {

libcxx/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // boyer_moore searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_searcher {

libcxx/test/std/experimental/func/func.searchers/func.searchers.boyer_moore/pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // boyer_moore searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_searcher {

libcxx/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/default.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // boyer_moore_horspool searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_horspool_searcher {

libcxx/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // boyer_moore_horspool searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_horspool_searcher {

libcxx/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // boyer_moore_horspool searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_horspool_searcher {

libcxx/test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // boyer_moore_horspool searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_horspool_searcher {

libcxx/test/std/experimental/func/func.searchers/func.searchers.default/default.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // default searcher
 // template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
 // class default_searcher {
 // public:
 //     default_searcher(_ForwardIterator __f, _ForwardIterator __l,

libcxx/test/std/experimental/func/func.searchers/func.searchers.default/default.pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // <functional>
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // default searcher
 // template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
 // class default_searcher {
 // public:
 //     default_searcher(_ForwardIterator __f, _ForwardIterator __l,
 //                             _BinaryPredicate __p = _BinaryPredicate())
 //         : __first_(__f), __last_(__l), __pred_(__p) {}

libcxx/test/std/experimental/func/func.searchers/func.searchers.default/func.searchers.default.creation/make_default_searcher.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // template<class ForwardIterator, class BinaryPredicate = equal_to<>>
 // default_searcher<ForwardIterator, BinaryPredicate>
 // make_default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
 //                       BinaryPredicate pred = BinaryPredicate());
 

libcxx/test/std/experimental/func/func.searchers/func.searchers.default/func.searchers.default.creation/make_default_searcher.pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_NO_EXPERIMENTAL_DEPRECATION_WARNING_SEARCHERS
 
 // <functional>
 
 // template<class ForwardIterator, class BinaryPredicate = equal_to<>>
 // default_searcher<ForwardIterator, BinaryPredicate>
 // make_default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
 //                       BinaryPredicate pred = BinaryPredicate());
 

libcxx/test/std/language.support/support.limits/support.limits.general/functional.version.compile.pass.cpp

 # ifdef __cpp_lib_bind_back
 #   error "__cpp_lib_bind_back should not be defined before c++2b"
 # endif
 
 # ifdef __cpp_lib_bind_front
 #   error "__cpp_lib_bind_front should not be defined before c++20"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should be defined in c++17"
-#   endif
-#   if __cpp_lib_boyer_moore_searcher != 201603L
-#     error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++17"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_boyer_moore_searcher
+#   error "__cpp_lib_boyer_moore_searcher should be defined in c++17"
+# endif
+# if __cpp_lib_boyer_moore_searcher != 201603L
+#   error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++17"
+# endif
 
 # ifdef __cpp_lib_constexpr_functional
 #   error "__cpp_lib_constexpr_functional should not be defined before c++20"
 # endif
 
 # ifndef __cpp_lib_invoke
 #   error "__cpp_lib_invoke should be defined in c++17"
 # endif

 
 # ifndef __cpp_lib_bind_front
 #   error "__cpp_lib_bind_front should be defined in c++20"
 # endif
 # if __cpp_lib_bind_front != 201907L
 #   error "__cpp_lib_bind_front should have the value 201907L in c++20"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should be defined in c++20"
-#   endif
-#   if __cpp_lib_boyer_moore_searcher != 201603L
-#     error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++20"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_boyer_moore_searcher
+#   error "__cpp_lib_boyer_moore_searcher should be defined in c++20"
+# endif
+# if __cpp_lib_boyer_moore_searcher != 201603L
+#   error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++20"
+# endif
 
 # ifndef __cpp_lib_constexpr_functional
 #   error "__cpp_lib_constexpr_functional should be defined in c++20"
 # endif
 # if __cpp_lib_constexpr_functional != 201907L
 #   error "__cpp_lib_constexpr_functional should have the value 201907L in c++20"
 # endif
 

 
 # ifndef __cpp_lib_bind_front
 #   error "__cpp_lib_bind_front should be defined in c++2b"
 # endif
 # if __cpp_lib_bind_front != 201907L
 #   error "__cpp_lib_bind_front should have the value 201907L in c++2b"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should be defined in c++2b"
-#   endif
-#   if __cpp_lib_boyer_moore_searcher != 201603L
-#     error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++2b"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_boyer_moore_searcher
+#   error "__cpp_lib_boyer_moore_searcher should be defined in c++2b"
+# endif
+# if __cpp_lib_boyer_moore_searcher != 201603L
+#   error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++2b"
+# endif
 
 # ifndef __cpp_lib_constexpr_functional
 #   error "__cpp_lib_constexpr_functional should be defined in c++2b"
 # endif
 # if __cpp_lib_constexpr_functional != 201907L
 #   error "__cpp_lib_constexpr_functional should have the value 201907L in c++2b"
 # endif
 

libcxx/test/std/language.support/support.limits/support.limits.general/version.version.compile.pass.cpp

 # if __cpp_lib_bool_constant != 201505L
 #   error "__cpp_lib_bool_constant should have the value 201505L in c++17"
 # endif
 
 # ifdef __cpp_lib_bounded_array_traits
 #   error "__cpp_lib_bounded_array_traits should not be defined before c++20"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should be defined in c++17"
-#   endif
-#   if __cpp_lib_boyer_moore_searcher != 201603L
-#     error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++17"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_boyer_moore_searcher
+#   error "__cpp_lib_boyer_moore_searcher should be defined in c++17"
+# endif
+# if __cpp_lib_boyer_moore_searcher != 201603L
+#   error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++17"
+# endif
 
 # ifndef __cpp_lib_byte
 #   error "__cpp_lib_byte should be defined in c++17"
 # endif
 # if __cpp_lib_byte != 201603L
 #   error "__cpp_lib_byte should have the value 201603L in c++17"
 # endif
 

 
 # ifndef __cpp_lib_bounded_array_traits
 #   error "__cpp_lib_bounded_array_traits should be defined in c++20"
 # endif
 # if __cpp_lib_bounded_array_traits != 201902L
 #   error "__cpp_lib_bounded_array_traits should have the value 201902L in c++20"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should be defined in c++20"
-#   endif
-#   if __cpp_lib_boyer_moore_searcher != 201603L
-#     error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++20"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_boyer_moore_searcher
+#   error "__cpp_lib_boyer_moore_searcher should be defined in c++20"
+# endif
+# if __cpp_lib_boyer_moore_searcher != 201603L
+#   error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++20"
+# endif
 
 # ifndef __cpp_lib_byte
 #   error "__cpp_lib_byte should be defined in c++20"
 # endif
 # if __cpp_lib_byte != 201603L
 #   error "__cpp_lib_byte should have the value 201603L in c++20"
 # endif
 

 
 # ifndef __cpp_lib_bounded_array_traits
 #   error "__cpp_lib_bounded_array_traits should be defined in c++2b"
 # endif
 # if __cpp_lib_bounded_array_traits != 201902L
 #   error "__cpp_lib_bounded_array_traits should have the value 201902L in c++2b"
 # endif
 
-# if !defined(_LIBCPP_VERSION)
-#   ifndef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should be defined in c++2b"
-#   endif
-#   if __cpp_lib_boyer_moore_searcher != 201603L
-#     error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++2b"
-#   endif
-# else // _LIBCPP_VERSION
-#   ifdef __cpp_lib_boyer_moore_searcher
-#     error "__cpp_lib_boyer_moore_searcher should not be defined because it is unimplemented in libc++!"
-#   endif
-# endif
+# ifndef __cpp_lib_boyer_moore_searcher
+#   error "__cpp_lib_boyer_moore_searcher should be defined in c++2b"
+# endif
+# if __cpp_lib_boyer_moore_searcher != 201603L
+#   error "__cpp_lib_boyer_moore_searcher should have the value 201603L in c++2b"
+# endif
 
 # ifndef __cpp_lib_byte
 #   error "__cpp_lib_byte should be defined in c++2b"
 # endif
 # if __cpp_lib_byte != 201603L
 #   error "__cpp_lib_byte should have the value 201603L in c++2b"
 # endif
 

libcxx/test/std/utilities/function.objects/func.search/func.search.bm/default.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14
-// XFAIL: stdlib=libc++
 
 // <functional>
 
 // boyer_moore searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_searcher {

 //   RandomAccessIterator1 pat_first_; // exposition only
 //   RandomAccessIterator1 pat_last_;  // exposition only
 //   Hash                  hash_;      // exposition only
 //   BinaryPredicate       pred_;      // exposition only
 // };
 
 
 #include <algorithm>
-#include <functional>
 #include <cassert>
+#include <functional>
+#include <string>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 template <typename Iter1, typename Iter2>
 void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result) {
     std::boyer_moore_searcher<Iter2> s{b2, e2};
     assert(result == std::search(b1, e1, s));
test2()
     do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3));
     char ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
     const unsigned sj = sizeof(ij)/sizeof(ij[0]);
     char ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
     const unsigned sk = sizeof(ik)/sizeof(ik[0]);
     do_search(Iter1(ij), Iter1(ij+sj), Iter2(ik), Iter2(ik+sk), Iter1(ij+6));
 }
 
+void test_custom_pred() {
+    std::string long_string(1024, '0');
+    std::boyer_moore_searcher searcher(std::begin(long_string), std::end(long_string));
+    const char str[] = "1234";
+    auto ret = searcher(std::begin(str), std::end(str));
+    assert(ret.first == std::end(str));
+    assert(ret.second == std::end(str));
+}
+
 int main(int, char**) {
     test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
     test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+    test_custom_pred();
 
   return 0;
 }

libcxx/test/std/utilities/function.objects/func.search/func.search.bm/hash.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14
-// XFAIL: stdlib=libc++
 
 // <functional>
 
 // boyer_moore searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_searcher {

 //   RandomAccessIterator1 pat_first_; // exposition only
 //   RandomAccessIterator1 pat_last_;  // exposition only
 //   Hash                  hash_;      // exposition only
 //   BinaryPredicate       pred_;      // exposition only
 // };
 
 
 #include <algorithm>
-#include <functional>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 template <typename T> struct MyHash {
     size_t operator () (T t) const { return static_cast<size_t>(t); }
 };
 

libcxx/test/std/utilities/function.objects/func.search/func.search.bm/hash.pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14
-// XFAIL: stdlib=libc++
 
 // <functional>
 
 // boyer_moore searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_searcher {

 //   RandomAccessIterator1 pat_first_; // exposition only
 //   RandomAccessIterator1 pat_last_;  // exposition only
 //   Hash                  hash_;      // exposition only
 //   BinaryPredicate       pred_;      // exposition only
 // };
 
 
 #include <algorithm>
-#include <functional>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 template <typename T> struct MyHash {
     size_t operator () (T t) const { return static_cast<size_t>(t); }
 };
 

libcxx/test/std/utilities/function.objects/func.search/func.search.bm/pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14
-// XFAIL: stdlib=libc++
 
 // <functional>
 
 // boyer_moore searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_searcher {

 //   RandomAccessIterator1 pat_first_; // exposition only
 //   RandomAccessIterator1 pat_last_;  // exposition only
 //   Hash                  hash_;      // exposition only
 //   BinaryPredicate       pred_;      // exposition only
 // };
 
 
 #include <algorithm>
-#include <functional>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 struct count_equal
 {
     static unsigned count;
     template <class T>

libcxx/test/std/utilities/function.objects/func.search/func.search.bmh/default.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14
-// XFAIL: stdlib=libc++
 
 // <functional>
 
 // boyer_moore_horspool searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_horspool_searcher {

libcxx/test/std/utilities/function.objects/func.search/func.search.bmh/hash.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14
-// XFAIL: stdlib=libc++
 
 // <functional>
 
 // boyer_moore_horspool searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_horspool_searcher {

libcxx/test/std/utilities/function.objects/func.search/func.search.bmh/hash.pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14
-// XFAIL: stdlib=libc++
 
 // <functional>
 
 // boyer_moore_horspool searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_horspool_searcher {

libcxx/test/std/utilities/function.objects/func.search/func.search.bmh/pred.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14
-// XFAIL: stdlib=libc++
 
 // <functional>
 
 // boyer_moore_horspool searcher
 // template<class RandomAccessIterator1,
 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
 //          class BinaryPredicate = equal_to<>>
 // class boyer_moore_horspool_searcher {

libcxx/test/std/utilities/optional/optional.hash/enabled_hash.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14
 
 // <optional>
 
 // Test that <optional> provides all of the arithmetic, enum, and pointer
 // hash specializations.
 
+#include <functional>
 #include <optional>
 
 #include "poisoned_hash_helper.h"
 
 #include "test_macros.h"
 
 int main(int, char**) {
   test_library_hash_specializations_available();
   {
 
   }
 
   return 0;
 }

libcxx/utils/generate_feature_test_macro_components.py

feature_test_macros = [ add_version_header(x) for x in [
   }, {
     "name": "__cpp_lib_bounded_array_traits",
     "values": { "c++20": 201902 },
     "headers": ["type_traits"],
   }, {
     "name": "__cpp_lib_boyer_moore_searcher",
     "values": { "c++17": 201603 },
     "headers": ["functional"],
-    "unimplemented": True,
   }, {
     "name": "__cpp_lib_byte",
     "values": { "c++17": 201603 },
     "headers": ["cstddef"],
   }, {
     "name": "__cpp_lib_byteswap",
     "values": { "c++2b": 202110 },
     "headers": ["bit"],