Vendor import of libc++ trunk r338150:vendor/libc++/libc++-trunk-r338150

https://llvm.org/svn/llvm-project/libcxx/trunk@338150

43 files changed, 2237 insertions, 210 deletions

diff --git a/test/std/utilities/any/any.class/any.assign/copy.pass.cpp b/test/std/utilities/any/any.class/any.assign/copy.pass.cpp
index 37618f7aafc7..68de5e3d1368 100644
--- a/test/std/utilities/any/any.class/any.assign/copy.pass.cpp
+++ b/test/std/utilities/any/any.class/any.assign/copy.pass.cpp
@@ -102,7 +102,7 @@ void test_copy_assign_self() {
     // empty
     {
         any a;
-        a = a;
+        a = (any &)a;
         assertEmpty(a);
         assert(globalMemCounter.checkOutstandingNewEq(0));
     }
@@ -112,7 +112,7 @@ void test_copy_assign_self() {
         any a((small(1)));
         assert(small::count == 1);
 
-        a = a;
+        a = (any &)a;
 
         assert(small::count == 1);
         assertContains<small>(a, 1);
@@ -125,7 +125,7 @@ void test_copy_assign_self() {
         any a(large(1));
         assert(large::count == 1);
 
-        a = a;
+        a = (any &)a;
 
         assert(large::count == 1);
         assertContains<large>(a, 1);
diff --git a/test/std/utilities/function.objects/comparisons/constexpr_init.pass.cpp b/test/std/utilities/function.objects/comparisons/constexpr_init.pass.cpp
new file mode 100644
index 000000000000..abb80d06d755
--- /dev/null
+++ b/test/std/utilities/function.objects/comparisons/constexpr_init.pass.cpp
@@ -0,0 +1,48 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11
+
+// XFAIL: gcc-7
+
+// <functional>
+
+// equal_to, not_equal_to, less, et al.
+
+// Test that these types can be constructed w/o an initializer in a constexpr
+// context. This is specifically testing gcc.gnu.org/PR83921
+
+
+#include <functional>
+#include "test_macros.h"
+
+template <class T>
+constexpr bool test_constexpr_context() {
+  std::equal_to<T> eq;
+  ((void)eq);
+  std::not_equal_to<T> neq;
+  ((void)neq);
+  std::less<T> l;
+  ((void)l);
+  std::less_equal<T> le;
+  ((void)le);
+  std::greater<T> g;
+  ((void)g);
+  std::greater_equal<T> ge;
+  ((void)ge);
+  return true;
+}
+
+static_assert(test_constexpr_context<int>(), "");
+static_assert(test_constexpr_context<void>(), "");
+
+
+int main() {
+
+}
diff --git a/test/std/utilities/function.objects/func.not_fn/not_fn.pass.cpp b/test/std/utilities/function.objects/func.not_fn/not_fn.pass.cpp
index 7601ff9d147d..f33b4157721a 100644
--- a/test/std/utilities/function.objects/func.not_fn/not_fn.pass.cpp
+++ b/test/std/utilities/function.objects/func.not_fn/not_fn.pass.cpp
@@ -305,15 +305,17 @@ void constructor_tests()
         using RetT = decltype(std::not_fn(value));
         static_assert(std::is_move_constructible<RetT>::value, "");
         static_assert(std::is_copy_constructible<RetT>::value, "");
-        static_assert(std::is_move_assignable<RetT>::value, "");
-        static_assert(std::is_copy_assignable<RetT>::value, "");
+        LIBCPP_STATIC_ASSERT(std::is_move_assignable<RetT>::value, "");
+        LIBCPP_STATIC_ASSERT(std::is_copy_assignable<RetT>::value, "");
         auto ret = std::not_fn(value);
         assert(ret() == false);
         auto ret2 = std::not_fn(value2);
         assert(ret2() == true);
+#if defined(_LIBCPP_VERSION)
         ret = ret2;
         assert(ret() == true);
         assert(ret2() == true);
+#endif // _LIBCPP_VERSION
     }
     {
         using T = MoveAssignableWrapper;
@@ -322,14 +324,16 @@ void constructor_tests()
         using RetT = decltype(std::not_fn(std::move(value)));
         static_assert(std::is_move_constructible<RetT>::value, "");
         static_assert(!std::is_copy_constructible<RetT>::value, "");
-        static_assert(std::is_move_assignable<RetT>::value, "");
+        LIBCPP_STATIC_ASSERT(std::is_move_assignable<RetT>::value, "");
         static_assert(!std::is_copy_assignable<RetT>::value, "");
         auto ret = std::not_fn(std::move(value));
         assert(ret() == false);
         auto ret2 = std::not_fn(std::move(value2));
         assert(ret2() == true);
+#if defined(_LIBCPP_VERSION)
         ret = std::move(ret2);
         assert(ret() == true);
+#endif // _LIBCPP_VERSION
     }
 }
 
@@ -426,7 +430,7 @@ void throws_in_constructor_test()
     {
         ThrowsOnCopy cp;
         try {
-            std::not_fn(cp);
+            (void)std::not_fn(cp);
             assert(false);
         } catch (int const& value) {
             assert(value == 42);
diff --git a/test/std/utilities/function.objects/func.search/func.search.bm/default.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.bm/default.pass.cpp
new file mode 100644
index 000000000000..c328b4a4e7a2
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.bm/default.pass.cpp
@@ -0,0 +1,129 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// XFAIL: c++17, c++2a
+
+// <functional>
+
+// boyer_moore searcher
+// template<class RandomAccessIterator1,
+//          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
+//          class BinaryPredicate = equal_to<>>
+// class boyer_moore_searcher {
+// public:
+//   boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
+//                        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+//
+//   template<class RandomAccessIterator2>
+//   pair<RandomAccessIterator2, RandomAccessIterator2>
+//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
+//
+// private:
+//   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 "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));
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1));
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1));
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1));
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4));
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8));
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3));
+    int 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]);
+    int 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
+test2()
+{
+    char ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1));
+    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    char ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1));
+    char id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1));
+    char ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4));
+    char ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8));
+    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    char ii[] = {1, 1, 2};
+    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));
+}
+
+int main() {
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/func.search.bm/hash.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.bm/hash.pass.cpp
new file mode 100644
index 000000000000..2555cedb212a
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.bm/hash.pass.cpp
@@ -0,0 +1,125 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// XFAIL: c++17, c++2a
+
+// <functional>
+
+// boyer_moore searcher
+// template<class RandomAccessIterator1,
+//          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
+//          class BinaryPredicate = equal_to<>>
+// class boyer_moore_searcher {
+// public:
+//   boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
+//                        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+//
+//   template<class RandomAccessIterator2>
+//   pair<RandomAccessIterator2, RandomAccessIterator2>
+//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
+//
+// private:
+//   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 "test_iterators.h"
+
+template <typename T> struct MyHash {
+    size_t operator () (T t) const { return static_cast<size_t>(t); }
+};
+
+template <typename Iter1, typename Iter2>
+void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned /*max_count*/) {
+    std::boyer_moore_searcher<Iter2,
+                 MyHash<typename std::remove_cv<typename std::iterator_traits<Iter2>::value_type>::type>>
+          s{b2, e2};
+    assert(result == std::search(b1, e1, s));
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+template <class Iter1, class Iter2>
+void
+test2()
+{
+    char ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    char ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    char id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    char ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    char ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    char ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+int main() {
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/func.search.bm/hash.pred.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.bm/hash.pred.pass.cpp
new file mode 100644
index 000000000000..f7b8e4983e54
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.bm/hash.pred.pass.cpp
@@ -0,0 +1,143 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// XFAIL: c++17, c++2a
+
+// <functional>
+
+// boyer_moore searcher
+// template<class RandomAccessIterator1,
+//          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
+//          class BinaryPredicate = equal_to<>>
+// class boyer_moore_searcher {
+// public:
+//   boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
+//                        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+//
+//   template<class RandomAccessIterator2>
+//   pair<RandomAccessIterator2, RandomAccessIterator2>
+//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
+//
+// private:
+//   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 "test_iterators.h"
+
+template <typename T> struct MyHash {
+    size_t operator () (T t) const { return static_cast<size_t>(t); }
+};
+
+struct count_equal
+{
+    static unsigned count;
+    template <class T>
+    bool operator()(const T& x, const T& y) const
+        {++count; return x == y;}
+};
+
+unsigned count_equal::count = 0;
+
+template <typename Iter1, typename Iter2>
+void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) {
+    std::boyer_moore_searcher<Iter2,
+                 MyHash<typename std::remove_cv<typename std::iterator_traits<Iter2>::value_type>::type>,
+                 count_equal>
+          s{b2, e2};
+    count_equal::count = 0;
+    assert(result == std::search(b1, e1, s));
+    assert(count_equal::count <= max_count);
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),     sa);
+
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+
+}
+
+template <class Iter1, class Iter2>
+void
+test2()
+{
+    char ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+
+    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    char ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    char id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    char ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    char ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    char ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+int main() {
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/func.search.bm/pred.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.bm/pred.pass.cpp
new file mode 100644
index 000000000000..17121d2809aa
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.bm/pred.pass.cpp
@@ -0,0 +1,134 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// XFAIL: c++17, c++2a
+
+// <functional>
+
+// boyer_moore searcher
+// template<class RandomAccessIterator1,
+//          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
+//          class BinaryPredicate = equal_to<>>
+// class boyer_moore_searcher {
+// public:
+//   boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
+//                        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+//
+//   template<class RandomAccessIterator2>
+//   pair<RandomAccessIterator2, RandomAccessIterator2>
+//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
+//
+// private:
+//   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 "test_iterators.h"
+
+struct count_equal
+{
+    static unsigned count;
+    template <class T>
+    bool operator()(const T& x, const T& y) const
+        {++count; return x == y;}
+};
+
+unsigned count_equal::count = 0;
+
+template <typename Iter1, typename Iter2>
+void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) {
+    std::boyer_moore_searcher<Iter2,
+           typename std::hash<typename std::remove_cv<typename std::iterator_traits<Iter2>::value_type>::type>, count_equal> s{b2, e2};
+    count_equal::count = 0;
+    assert(result == std::search(b1, e1, s));
+    assert(count_equal::count <= max_count);
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+template <class Iter1, class Iter2>
+void
+test2()
+{
+    char ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    char ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    char id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    char ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    char ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    char ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+int main() {
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/func.search.bmh/default.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.bmh/default.pass.cpp
new file mode 100644
index 000000000000..ec65a4b9b69f
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.bmh/default.pass.cpp
@@ -0,0 +1,129 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// XFAIL: c++17, c++2a
+
+// <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 {
+// public:
+//   boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
+//                                 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+//
+//   template<class RandomAccessIterator2>
+//   pair<RandomAccessIterator2, RandomAccessIterator2>
+//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
+//
+// private:
+//   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 "test_iterators.h"
+
+template <typename Iter1, typename Iter2>
+void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result) {
+    std::boyer_moore_horspool_searcher<Iter2> s{b2, e2};
+    assert(result == std::search(b1, e1, s));
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1));
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1));
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1));
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4));
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8));
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3));
+    int 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]);
+    int 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
+test2()
+{
+    char ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1));
+    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    char ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1));
+    char id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1));
+    char ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4));
+    char ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8));
+    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    char ii[] = {1, 1, 2};
+    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));
+}
+
+int main() {
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/func.search.bmh/hash.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.bmh/hash.pass.cpp
new file mode 100644
index 000000000000..dfa587dccfb1
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.bmh/hash.pass.cpp
@@ -0,0 +1,124 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// XFAIL: c++17, c++2a
+
+// <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 {
+// public:
+//   boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
+//                                 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+//
+//   template<class RandomAccessIterator2>
+//   pair<RandomAccessIterator2, RandomAccessIterator2>
+//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
+//
+// private:
+//   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 "test_iterators.h"
+
+template <typename T> struct MyHash {
+    size_t operator () (T t) const { return static_cast<size_t>(t); }
+};
+
+template <typename Iter1, typename Iter2>
+void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned /*max_count*/) {
+    std::boyer_moore_horspool_searcher<Iter2,
+                 MyHash<typename std::remove_cv<typename std::iterator_traits<Iter2>::value_type>::type>>
+          s{b2, e2};
+    assert(result == std::search(b1, e1, s));
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+template <class Iter1, class Iter2>
+void
+test2()
+{
+    char ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    char ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    char id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    char ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    char ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    char ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+int main() {
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/func.search.bmh/hash.pred.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.bmh/hash.pred.pass.cpp
new file mode 100644
index 000000000000..083065ca8a91
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.bmh/hash.pred.pass.cpp
@@ -0,0 +1,137 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// XFAIL: c++17, c++2a
+
+// <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 {
+// public:
+//   boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
+//                                 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+//
+//   template<class RandomAccessIterator2>
+//   pair<RandomAccessIterator2, RandomAccessIterator2>
+//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
+//
+// private:
+//   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 "test_iterators.h"
+
+template <typename T> struct MyHash {
+    size_t operator () (T t) const { return static_cast<size_t>(t); }
+};
+
+struct count_equal
+{
+    static unsigned count;
+    template <class T>
+    bool operator()(const T& x, const T& y) const
+        {++count; return x == y;}
+};
+
+unsigned count_equal::count = 0;
+
+template <typename Iter1, typename Iter2>
+void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) {
+    std::boyer_moore_horspool_searcher<Iter2,
+                 MyHash<typename std::remove_cv<typename std::iterator_traits<Iter2>::value_type>::type>,
+                 count_equal>
+          s{b2, e2};
+    count_equal::count = 0;
+    assert(result == std::search(b1, e1, s));
+    assert(count_equal::count <= max_count);
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+template <class Iter1, class Iter2>
+void
+test2()
+{
+    char ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    char ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    char id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    char ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    char ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    char ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+int main() {
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/func.search.bmh/pred.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.bmh/pred.pass.cpp
new file mode 100644
index 000000000000..865dd89ce18a
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.bmh/pred.pass.cpp
@@ -0,0 +1,131 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// XFAIL: c++17, c++2a
+
+// <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 {
+// public:
+//   boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
+//                                 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+//
+//   template<class RandomAccessIterator2>
+//   pair<RandomAccessIterator2, RandomAccessIterator2>
+//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
+//
+// private:
+//   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 "test_iterators.h"
+
+struct count_equal
+{
+    static unsigned count;
+    template <class T>
+    bool operator()(const T& x, const T& y) const
+        {++count; return x == y;}
+};
+
+unsigned count_equal::count = 0;
+
+template <typename Iter1, typename Iter2>
+void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) {
+    std::boyer_moore_horspool_searcher<Iter2,
+           typename std::hash<typename std::remove_cv<typename std::iterator_traits<Iter2>::value_type>::type>, count_equal> s{b2, e2};
+    count_equal::count = 0;
+    assert(result == std::search(b1, e1, s));
+    assert(count_equal::count <= max_count);
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+template <class Iter1, class Iter2>
+void
+test2()
+{
+    char ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    char ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    char id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    char ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    char ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    char ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+int main() {
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/func.search.default/default.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.default/default.pass.cpp
new file mode 100644
index 000000000000..e498cfd960a3
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.default/default.pass.cpp
@@ -0,0 +1,96 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <functional>
+
+// 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) {}
+//
+//     template <typename _ForwardIterator2>
+//     pair<_ForwardIterator2, _ForwardIterator2>
+//     operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const {
+//         return std::search(__f, __l, __first_, __last_, __pred_);
+//         }
+//
+// private:
+//     _ForwardIterator __first_;
+//     _ForwardIterator __last_;
+//     _BinaryPredicate __pred_;
+//     };
+
+
+#include <algorithm>
+#include <functional>
+#include <cassert>
+
+#include "test_iterators.h"
+
+template <typename Iter1, typename Iter2>
+void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result) {
+    std::default_searcher<Iter2> s{b2, e2};
+    assert(result == std::search(b1, e1, s));
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3));
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia));
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1));
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1));
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1));
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1));
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4));
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8));
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3));
+    int 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]);
+    int 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));
+}
+
+int main() {
+    test<forward_iterator<const int*>, forward_iterator<const int*> >();
+    test<forward_iterator<const int*>, bidirectional_iterator<const int*> >();
+    test<forward_iterator<const int*>, random_access_iterator<const int*> >();
+    test<bidirectional_iterator<const int*>, forward_iterator<const int*> >();
+    test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*> >();
+    test<bidirectional_iterator<const int*>, random_access_iterator<const int*> >();
+    test<random_access_iterator<const int*>, forward_iterator<const int*> >();
+    test<random_access_iterator<const int*>, bidirectional_iterator<const int*> >();
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/func.search.default/default.pred.pass.cpp b/test/std/utilities/function.objects/func.search/func.search.default/default.pred.pass.cpp
new file mode 100644
index 000000000000..025565f8eb13
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/func.search.default/default.pred.pass.cpp
@@ -0,0 +1,103 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <functional>
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// 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) {}
+//
+//     template <typename _ForwardIterator2>
+//     pair<_ForwardIterator2, _ForwardIterator2>
+//     operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const {
+//         return std::search(__f, __l, __first_, __last_, __pred_);
+//         }
+//
+// private:
+//     _ForwardIterator __first_;
+//     _ForwardIterator __last_;
+//     _BinaryPredicate __pred_;
+//     };
+
+
+#include <algorithm>
+#include <functional>
+#include <cassert>
+
+#include "test_iterators.h"
+
+struct count_equal
+{
+    static unsigned count;
+    template <class T>
+    bool operator()(const T& x, const T& y) const
+        {++count; return x == y;}
+};
+
+unsigned count_equal::count = 0;
+
+template <typename Iter1, typename Iter2>
+void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) {
+    std::default_searcher<Iter2, count_equal> s{b2, e2};
+    count_equal::count = 0;
+    assert(result == std::search(b1, e1, s));
+    assert(count_equal::count <= max_count);
+}
+
+template <class Iter1, class Iter2>
+void
+test()
+{
+    int ia[] = {0, 1, 2, 3, 4, 5};
+    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
+    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
+    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
+    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
+    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
+    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
+    int ic[] = {1};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
+    int id[] = {1, 2};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
+    int ie[] = {1, 2, 3};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
+    int ig[] = {1, 2, 3, 4};
+    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
+    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
+    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
+    int ii[] = {1, 1, 2};
+    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
+}
+
+int main() {
+    test<forward_iterator<const int*>, forward_iterator<const int*> >();
+    test<forward_iterator<const int*>, bidirectional_iterator<const int*> >();
+    test<forward_iterator<const int*>, random_access_iterator<const int*> >();
+    test<bidirectional_iterator<const int*>, forward_iterator<const int*> >();
+    test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*> >();
+    test<bidirectional_iterator<const int*>, random_access_iterator<const int*> >();
+    test<random_access_iterator<const int*>, forward_iterator<const int*> >();
+    test<random_access_iterator<const int*>, bidirectional_iterator<const int*> >();
+    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
+}
diff --git a/test/std/utilities/function.objects/func.search/nothing_to_do.pass.cpp b/test/std/utilities/function.objects/func.search/nothing_to_do.pass.cpp
new file mode 100644
index 000000000000..9a59227abdd9
--- /dev/null
+++ b/test/std/utilities/function.objects/func.search/nothing_to_do.pass.cpp
@@ -0,0 +1,13 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+int main()
+{
+}
diff --git a/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/copy_assign.pass.cpp b/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/copy_assign.pass.cpp
index 9b83ddecb974..1c2be02c6212 100644
--- a/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/copy_assign.pass.cpp
+++ b/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/copy_assign.pass.cpp
@@ -92,28 +92,28 @@ int main() {
   {
     typedef std::function<int()> Func;
     Func f = g0;
-    Func& fr = (f = f);
+    Func& fr = (f = (Func &)f);
     assert(&fr == &f);
     assert(*f.target<int(*)()>() == g0);
   }
   {
     typedef std::function<int(int)> Func;
     Func f = g;
-    Func& fr = (f = f);
+    Func& fr = (f = (Func &)f);
     assert(&fr == &f);
     assert(*f.target<int(*)(int)>() == g);
   }
   {
     typedef std::function<int(int, int)> Func;
     Func f = g2;
-    Func& fr = (f = f);
+    Func& fr = (f = (Func &)f);
     assert(&fr == &f);
     assert(*f.target<int(*)(int, int)>() == g2);
   }
   {
     typedef std::function<int(int, int, int)> Func;
     Func f = g3;
-    Func& fr = (f = f);
+    Func& fr = (f = (Func &)f);
     assert(&fr == &f);
     assert(*f.target<int(*)(int, int, int)>() == g3);
   }
diff --git a/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/move_reentrant.pass.cpp b/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/move_reentrant.pass.cpp
new file mode 100644
index 000000000000..0813c48f322e
--- /dev/null
+++ b/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/move_reentrant.pass.cpp
@@ -0,0 +1,46 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <functional>
+
+// class function<R(ArgTypes...)>
+
+// function& operator=(function &&);
+
+#include <functional>
+#include <cassert>
+
+#include "test_macros.h"
+
+struct A
+{
+  static std::function<void()> global;
+  static bool cancel;
+
+  ~A() {
+    DoNotOptimize(cancel);
+    if (cancel)
+      global = std::function<void()>(nullptr);
+  }
+  void operator()() {}
+};
+
+std::function<void()> A::global;
+bool A::cancel = false;
+
+int main()
+{
+  A::global = A();
+  assert(A::global.target<A>());
+
+  // Check that we don't recurse in A::~A().
+  A::cancel = true;
+  A::global = std::function<void()>(nullptr);
+  assert(!A::global.target<A>());
+}
diff --git a/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/nullptr_t_assign_reentrant.pass.cpp b/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/nullptr_t_assign_reentrant.pass.cpp
new file mode 100644
index 000000000000..eeb181928eaf
--- /dev/null
+++ b/test/std/utilities/function.objects/func.wrap/func.wrap.func/func.wrap.func.con/nullptr_t_assign_reentrant.pass.cpp
@@ -0,0 +1,46 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <functional>
+
+// class function<R(ArgTypes...)>
+
+// function& operator=(nullptr_t);
+
+#include <functional>
+#include <cassert>
+
+#include "test_macros.h"
+
+struct A
+{
+  static std::function<void()> global;
+  static bool cancel;
+
+  ~A() {
+    DoNotOptimize(cancel);
+    if (cancel)
+      global = nullptr;
+  }
+  void operator()() {}
+};
+
+std::function<void()> A::global;
+bool A::cancel = false;
+
+int main()
+{
+  A::global = A();
+  assert(A::global.target<A>());
+
+  // Check that we don't recurse in A::~A().
+  A::cancel = true;
+  A::global = nullptr;
+  assert(!A::global.target<A>());
+}
diff --git a/test/std/utilities/memory/default.allocator/allocator.ctor.pass.cpp b/test/std/utilities/memory/default.allocator/allocator.ctor.pass.cpp
new file mode 100644
index 000000000000..0afab685f913
--- /dev/null
+++ b/test/std/utilities/memory/default.allocator/allocator.ctor.pass.cpp
@@ -0,0 +1,50 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <memory>
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+//
+// template <class T>
+// class allocator
+// {
+// public: // All of these are constexpr after C++17
+//  constexpr allocator() noexcept;
+//  constexpr allocator(const allocator&) noexcept;
+//  template<class U> constexpr allocator(const allocator<U>&) noexcept;
+// ...
+// };
+
+#include <memory>
+#include <cstddef>
+
+#include "test_macros.h"
+
+
+int main()
+{
+    {
+    typedef std::allocator<char> AC;
+    typedef std::allocator<long> AL;
+
+    constexpr AC a1;
+    constexpr AC a2{a1};
+    constexpr AL a3{a2};
+    (void) a3;
+    }
+    {
+    typedef std::allocator<const char> AC;
+    typedef std::allocator<const long> AL;
+
+    constexpr AC a1;
+    constexpr AC a2{a1};
+    constexpr AL a3{a2};
+    (void) a3;
+    }
+
+}
diff --git a/test/std/utilities/memory/default.allocator/allocator.members/allocate.pass.cpp b/test/std/utilities/memory/default.allocator/allocator.members/allocate.pass.cpp
index f2cf9f2d4187..70c5e46965a0 100644
--- a/test/std/utilities/memory/default.allocator/allocator.members/allocate.pass.cpp
+++ b/test/std/utilities/memory/default.allocator/allocator.members/allocate.pass.cpp
@@ -14,40 +14,98 @@
 
 #include <memory>
 #include <cassert>
+#include <iostream>
 
+#include "test_macros.h"
 #include "count_new.hpp"
 
-int A_constructed = 0;
 
-struct A
-{
-    int data;
-    A() {++A_constructed;}
-    A(const A&) {++A_constructed;}
-    ~A() {--A_constructed;}
+#ifdef TEST_HAS_NO_ALIGNED_ALLOCATION
+static const bool UsingAlignedNew = false;
+#else
+static const bool UsingAlignedNew = true;
+#endif
+
+#ifdef __STDCPP_DEFAULT_NEW_ALIGNMENT__
+static const size_t MaxAligned = __STDCPP_DEFAULT_NEW_ALIGNMENT__;
+#else
+static const size_t MaxAligned = std::alignment_of<std::max_align_t>::value;
+#endif
+
+static const size_t OverAligned = MaxAligned * 2;
+
+
+template <size_t Align>
+struct TEST_ALIGNAS(Align) AlignedType {
+  char data;
+  static int constructed;
+  AlignedType() { ++constructed; }
+  AlignedType(AlignedType const&) { ++constructed; }
+  ~AlignedType() { --constructed; }
 };
+template <size_t Align>
+int AlignedType<Align>::constructed = 0;
 
-int main()
-{
-    globalMemCounter.reset();
-    std::allocator<A> a;
+
+template <size_t Align>
+void test_aligned() {
+  typedef AlignedType<Align> T;
+  T::constructed = 0;
+  globalMemCounter.reset();
+  std::allocator<T> a;
+  const bool IsOverAlignedType = Align > MaxAligned;
+  const bool ExpectAligned = IsOverAlignedType && UsingAlignedNew;
+  {
     assert(globalMemCounter.checkOutstandingNewEq(0));
-    assert(A_constructed == 0);
+    assert(T::constructed == 0);
     globalMemCounter.last_new_size = 0;
-    A* volatile ap = a.allocate(3);
+    globalMemCounter.last_new_align = 0;
+    T* ap = a.allocate(3);
+    DoNotOptimize(ap);
     assert(globalMemCounter.checkOutstandingNewEq(1));
-    assert(globalMemCounter.checkLastNewSizeEq(3 * sizeof(int)));
-    assert(A_constructed == 0);
+    assert(globalMemCounter.checkNewCalledEq(1));
+    assert(globalMemCounter.checkAlignedNewCalledEq(ExpectAligned));
+    assert(globalMemCounter.checkLastNewSizeEq(3 * sizeof(T)));
+    assert(globalMemCounter.checkLastNewAlignEq(ExpectAligned ? Align : 0));
+    assert(T::constructed == 0);
+    globalMemCounter.last_delete_align = 0;
     a.deallocate(ap, 3);
     assert(globalMemCounter.checkOutstandingNewEq(0));
-    assert(A_constructed == 0);
-
+    assert(globalMemCounter.checkDeleteCalledEq(1));
+    assert(globalMemCounter.checkAlignedDeleteCalledEq(ExpectAligned));
+    assert(globalMemCounter.checkLastDeleteAlignEq(ExpectAligned ? Align : 0));
+    assert(T::constructed == 0);
+  }
+  globalMemCounter.reset();
+  {
     globalMemCounter.last_new_size = 0;
-    A* volatile ap2 = a.allocate(3, (const void*)5);
+    globalMemCounter.last_new_align = 0;
+    T* volatile ap2 = a.allocate(11, (const void*)5);
+    DoNotOptimize(ap2);
     assert(globalMemCounter.checkOutstandingNewEq(1));
-    assert(globalMemCounter.checkLastNewSizeEq(3 * sizeof(int)));
-    assert(A_constructed == 0);
-    a.deallocate(ap2, 3);
+    assert(globalMemCounter.checkNewCalledEq(1));
+    assert(globalMemCounter.checkAlignedNewCalledEq(ExpectAligned));
+    assert(globalMemCounter.checkLastNewSizeEq(11 * sizeof(T)));
+    assert(globalMemCounter.checkLastNewAlignEq(ExpectAligned ? Align : 0));
+    assert(T::constructed == 0);
+    globalMemCounter.last_delete_align = 0;
+    a.deallocate(ap2, 11);
+    DoNotOptimize(ap2);
     assert(globalMemCounter.checkOutstandingNewEq(0));
-    assert(A_constructed == 0);
+    assert(globalMemCounter.checkDeleteCalledEq(1));
+    assert(globalMemCounter.checkAlignedDeleteCalledEq(ExpectAligned));
+    assert(globalMemCounter.checkLastDeleteAlignEq(ExpectAligned ? Align : 0));
+    assert(T::constructed == 0);
+  }
+}
+
+int main() {
+    test_aligned<1>();
+    test_aligned<2>();
+    test_aligned<4>();
+    test_aligned<8>();
+    test_aligned<16>();
+    test_aligned<MaxAligned>();
+    test_aligned<OverAligned>();
+    test_aligned<OverAligned * 2>();
 }
diff --git a/test/std/utilities/memory/default.allocator/allocator.members/construct.pass.cpp b/test/std/utilities/memory/default.allocator/allocator.members/construct.pass.cpp
index 28dadd831514..9ba9874406f6 100644
--- a/test/std/utilities/memory/default.allocator/allocator.members/construct.pass.cpp
+++ b/test/std/utilities/memory/default.allocator/allocator.members/construct.pass.cpp
@@ -63,6 +63,7 @@ int main()
 
     globalMemCounter.last_new_size = 0;
     A* ap = a.allocate(3);
+    DoNotOptimize(ap);
     assert(globalMemCounter.checkOutstandingNewEq(1));
     assert(globalMemCounter.checkLastNewSizeEq(3 * sizeof(int)));
     assert(A_constructed == 0);
@@ -100,6 +101,7 @@ int main()
     assert(A_constructed == 0);
 
     a.deallocate(ap, 3);
+    DoNotOptimize(ap);
     assert(globalMemCounter.checkOutstandingNewEq(0));
     assert(A_constructed == 0);
     }
@@ -111,6 +113,7 @@ int main()
 
     globalMemCounter.last_new_size = 0;
     move_only* ap = a.allocate(3);
+    DoNotOptimize(ap);
     assert(globalMemCounter.checkOutstandingNewEq(1));
     assert(globalMemCounter.checkLastNewSizeEq(3 * sizeof(int)));
     assert(move_only_constructed == 0);
@@ -132,6 +135,7 @@ int main()
     assert(move_only_constructed == 0);
 
     a.deallocate(ap, 3);
+    DoNotOptimize(ap);
     assert(globalMemCounter.checkOutstandingNewEq(0));
     assert(move_only_constructed == 0);
     }
diff --git a/test/std/utilities/memory/temporary.buffer/overaligned.pass.cpp b/test/std/utilities/memory/temporary.buffer/overaligned.pass.cpp
new file mode 100644
index 000000000000..52aca8192cbb
--- /dev/null
+++ b/test/std/utilities/memory/temporary.buffer/overaligned.pass.cpp
@@ -0,0 +1,35 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03
+
+// <memory>
+
+// template <class T>
+//   pair<T*, ptrdiff_t>
+//   get_temporary_buffer(ptrdiff_t n);
+//
+// template <class T>
+//   void
+//   return_temporary_buffer(T* p);
+
+#include <memory>
+#include <cassert>
+
+struct alignas(32) A {
+    int field;
+};
+
+int main()
+{
+    std::pair<A*, std::ptrdiff_t> ip = std::get_temporary_buffer<A>(5);
+    assert(!(ip.first == nullptr) ^ (ip.second == 0));
+    assert(reinterpret_cast<uintptr_t>(ip.first) % alignof(A) == 0);
+    std::return_temporary_buffer(ip.first);
+}
diff --git a/test/std/utilities/memory/unique.ptr/unique.ptr.special/io.fail.cpp b/test/std/utilities/memory/unique.ptr/unique.ptr.special/io.fail.cpp
index 48c90f7b9661..54c85e94338c 100644
--- a/test/std/utilities/memory/unique.ptr/unique.ptr.special/io.fail.cpp
+++ b/test/std/utilities/memory/unique.ptr/unique.ptr.special/io.fail.cpp
@@ -24,11 +24,12 @@
 #include <sstream>
 #include <cassert>
 
-class A {};
+#include "min_allocator.h"
+#include "deleter_types.h"
 
 int main()
 {
-    std::unique_ptr<A> p(new A);
+    std::unique_ptr<int, PointerDeleter<int>> p;
     std::ostringstream os;
-    os << p;
+    os << p; // expected-error {{invalid operands to binary expression}}
 }
diff --git a/test/std/utilities/meta/meta.trans/meta.trans.other/aligned_storage.pass.cpp b/test/std/utilities/meta/meta.trans/meta.trans.other/aligned_storage.pass.cpp
index 079661d0c174..d7e35a62f8f0 100644
--- a/test/std/utilities/meta/meta.trans/meta.trans.other/aligned_storage.pass.cpp
+++ b/test/std/utilities/meta/meta.trans/meta.trans.other/aligned_storage.pass.cpp
@@ -10,6 +10,9 @@
 // type_traits
 
 // aligned_storage
+//
+//  Issue 3034 added:
+//  The member typedef type shall be a trivial standard-layout type.
 
 #include <type_traits>
 #include <cstddef>       // for std::max_align_t
@@ -20,144 +23,231 @@ int main()
     {
     typedef std::aligned_storage<10, 1 >::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<10, 1>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<10, 1>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 1, "");
     static_assert(sizeof(T1) == 10, "");
     }
     {
     typedef std::aligned_storage<10, 2 >::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<10, 2>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<10, 2>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 2, "");
     static_assert(sizeof(T1) == 10, "");
     }
     {
     typedef std::aligned_storage<10, 4 >::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<10, 4>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<10, 4>, T1>::value, "");
 #endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
+#endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 4, "");
     static_assert(sizeof(T1) == 12, "");
     }
     {
     typedef std::aligned_storage<10, 8 >::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<10, 8>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<10, 8>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 8, "");
     static_assert(sizeof(T1) == 16, "");
     }
     {
     typedef std::aligned_storage<10, 16 >::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<10, 16>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<10, 16>, T1>::value, "");
 #endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
+#endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 16, "");
     static_assert(sizeof(T1) == 16, "");
     }
     {
     typedef std::aligned_storage<10, 32 >::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<10, 32>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<10, 32>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 32, "");
     static_assert(sizeof(T1) == 32, "");
     }
     {
     typedef std::aligned_storage<20, 32 >::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<20, 32>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<20, 32>, T1>::value, "");
 #endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
+#endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 32, "");
     static_assert(sizeof(T1) == 32, "");
     }
     {
     typedef std::aligned_storage<40, 32 >::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<40, 32>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<40, 32>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 32, "");
     static_assert(sizeof(T1) == 64, "");
     }
     {
     typedef std::aligned_storage<12, 16 >::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<12, 16>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<12, 16>, T1>::value, "");
 #endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
+#endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 16, "");
     static_assert(sizeof(T1) == 16, "");
     }
     {
     typedef std::aligned_storage<1>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<1>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<1>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 1, "");
     static_assert(sizeof(T1) == 1, "");
     }
     {
     typedef std::aligned_storage<2>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<2>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<2>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 2, "");
     static_assert(sizeof(T1) == 2, "");
     }
     {
     typedef std::aligned_storage<3>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<3>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<3>, T1>::value, "");
 #endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
+#endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 2, "");
     static_assert(sizeof(T1) == 4, "");
     }
     {
     typedef std::aligned_storage<4>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<4>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<4>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 4, "");
     static_assert(sizeof(T1) == 4, "");
     }
     {
     typedef std::aligned_storage<5>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<5>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<5>, T1>::value, "");
 #endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
+#endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 4, "");
     static_assert(sizeof(T1) == 8, "");
     }
     {
     typedef std::aligned_storage<7>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<7>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<7>, T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 4, "");
     static_assert(sizeof(T1) == 8, "");
     }
     {
     typedef std::aligned_storage<8>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<8>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<8>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 8, "");
     static_assert(sizeof(T1) == 8, "");
     }
     {
     typedef std::aligned_storage<9>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<9>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<9>, T1>::value, "");
 #endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
+#endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 8, "");
     static_assert(sizeof(T1) == 16, "");
     }
     {
     typedef std::aligned_storage<15>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<15>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<15>, T1>::value, "");
+#endif
+#if TEST_STD_VER <= 17
+    static_assert(std::is_pod<T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 8, "");
     static_assert(sizeof(T1) == 16, "");
     }
@@ -170,8 +260,10 @@ int main()
     {
     typedef std::aligned_storage<16>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<16>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<16>, T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == alignof(std::max_align_t),
                   "");
     static_assert(sizeof(T1) == 16, "");
@@ -179,8 +271,10 @@ int main()
     {
     typedef std::aligned_storage<17>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<17>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<17>, T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == alignof(std::max_align_t),
                   "");
     static_assert(sizeof(T1) == 16 + alignof(std::max_align_t), "");
@@ -188,8 +282,10 @@ int main()
     {
     typedef std::aligned_storage<10>::type T1;
 #if TEST_STD_VER > 11
-    static_assert(std::is_same<std::aligned_storage_t<10>, T1>::value, "" );
+    static_assert(std::is_same<std::aligned_storage_t<10>, T1>::value, "");
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 8, "");
     static_assert(sizeof(T1) == 16, "");
     }
diff --git a/test/std/utilities/meta/meta.trans/meta.trans.other/aligned_union.pass.cpp b/test/std/utilities/meta/meta.trans/meta.trans.other/aligned_union.pass.cpp
index 883548270469..3e58b51a6168 100644
--- a/test/std/utilities/meta/meta.trans/meta.trans.other/aligned_union.pass.cpp
+++ b/test/std/utilities/meta/meta.trans/meta.trans.other/aligned_union.pass.cpp
@@ -13,6 +13,9 @@
 
 // aligned_union<size_t Len, class ...Types>
 
+//  Issue 3034 added:
+//  The member typedef type shall be a trivial standard-layout type.
+
 #include <type_traits>
 
 #include "test_macros.h"
@@ -24,6 +27,8 @@ int main()
 #if TEST_STD_VER > 11
     static_assert(std::is_same<std::aligned_union_t<10, char>, T1>::value, "" );
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 1, "");
     static_assert(sizeof(T1) == 10, "");
     }
@@ -32,6 +37,8 @@ int main()
 #if TEST_STD_VER > 11
     static_assert(std::is_same<std::aligned_union_t<10, short>, T1>::value, "" );
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 2, "");
     static_assert(sizeof(T1) == 10, "");
     }
@@ -40,6 +47,8 @@ int main()
 #if TEST_STD_VER > 11
     static_assert(std::is_same<std::aligned_union_t<10, int>, T1>::value, "" );
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 4, "");
     static_assert(sizeof(T1) == 12, "");
     }
@@ -48,6 +57,8 @@ int main()
 #if TEST_STD_VER > 11
     static_assert(std::is_same<std::aligned_union_t<10, double>, T1>::value, "" );
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 8, "");
     static_assert(sizeof(T1) == 16, "");
     }
@@ -56,6 +67,8 @@ int main()
 #if TEST_STD_VER > 11
     static_assert(std::is_same<std::aligned_union_t<10, short, char>, T1>::value, "" );
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 2, "");
     static_assert(sizeof(T1) == 10, "");
     }
@@ -64,6 +77,8 @@ int main()
 #if TEST_STD_VER > 11
     static_assert(std::is_same<std::aligned_union_t<10, char, short>, T1>::value, "" );
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 2, "");
     static_assert(sizeof(T1) == 10, "");
     }
@@ -72,6 +87,8 @@ int main()
 #if TEST_STD_VER > 11
     static_assert(std::is_same<std::aligned_union_t<2, int, char, short>, T1>::value, "" );
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 4, "");
     static_assert(sizeof(T1) == 4, "");
     }
@@ -80,6 +97,8 @@ int main()
 #if TEST_STD_VER > 11
     static_assert(std::is_same<std::aligned_union_t<2, char, int, short >, T1>::value, "" );
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 4, "");
     static_assert(sizeof(T1) == 4, "");
     }
@@ -88,6 +107,8 @@ int main()
 #if TEST_STD_VER > 11
     static_assert(std::is_same<std::aligned_union_t<2, char, short, int >, T1>::value, "" );
 #endif
+    static_assert(std::is_trivial<T1>::value, "");
+    static_assert(std::is_standard_layout<T1>::value, "");
     static_assert(std::alignment_of<T1>::value == 4, "");
     static_assert(sizeof(T1) == 4, "");
     }
diff --git a/test/std/utilities/meta/meta.trans/meta.trans.other/common_type.pass.cpp b/test/std/utilities/meta/meta.trans/meta.trans.other/common_type.pass.cpp
index 85b14726617f..dbbbe159f09e 100644
--- a/test/std/utilities/meta/meta.trans/meta.trans.other/common_type.pass.cpp
+++ b/test/std/utilities/meta/meta.trans/meta.trans.other/common_type.pass.cpp
@@ -11,8 +11,9 @@
 
 // common_type
 
-#include <type_traits>
+#include <functional>
 #include <memory>
+#include <type_traits>
 
 #include "test_macros.h"
 
@@ -45,7 +46,6 @@ namespace std
 
     template <> struct common_type< ::S<long>, long> {};
     template <> struct common_type<long, ::S<long> > {};
-    template <> struct common_type< ::X<float> > {};
     template <> struct common_type< ::X<double>, ::X<double> > {};
 }
 
@@ -97,7 +97,6 @@ void test_bullet_two() {
   static_assert(std::is_same<CommonType<int volatile[]>, int volatile*>::value, "");
   static_assert(std::is_same<CommonType<void(&)()>, void(*)()>::value, "");
 
-  static_assert(no_common_type<X<float> >::value, "");
   static_assert(no_common_type<X<double> >::value, "");
 }
 
diff --git a/test/std/utilities/meta/meta.trans/meta.trans.other/remove_cvref.pass.cpp b/test/std/utilities/meta/meta.trans/meta.trans.other/remove_cvref.pass.cpp
index e06229f7e975..e220f591f480 100644
--- a/test/std/utilities/meta/meta.trans/meta.trans.other/remove_cvref.pass.cpp
+++ b/test/std/utilities/meta/meta.trans/meta.trans.other/remove_cvref.pass.cpp
@@ -32,7 +32,7 @@ int main()
     test_remove_cvref<const volatile int, int>();
     test_remove_cvref<volatile int, int>();
 
-//	Doesn't decay
+// Doesn't decay
     test_remove_cvref<int[3],                 int[3]>();
     test_remove_cvref<int const [3],          int[3]>();
     test_remove_cvref<int volatile [3],       int[3]>();
diff --git a/test/std/utilities/meta/meta.trans/meta.trans.other/result_of.pass.cpp b/test/std/utilities/meta/meta.trans/meta.trans.other/result_of.pass.cpp
index 24231526b2bf..69e805d1e1f4 100644
--- a/test/std/utilities/meta/meta.trans/meta.trans.other/result_of.pass.cpp
+++ b/test/std/utilities/meta/meta.trans/meta.trans.other/result_of.pass.cpp
@@ -104,36 +104,43 @@ int main()
     test_result_of<S const volatile&(unsigned char, int&), double const volatile&> ();
     }
     { // pointer to function
-    typedef bool         (&RF0)();
+    typedef bool        (&RF0)();
     typedef bool*       (&RF1)(int);
     typedef bool&       (&RF2)(int, int);
     typedef bool const& (&RF3)(int, int, int);
+    typedef bool        (&RF4)(int, ...);
     typedef bool        (*PF0)();
     typedef bool*       (*PF1)(int);
     typedef bool&       (*PF2)(int, int);
     typedef bool const& (*PF3)(int, int, int);
+    typedef bool        (*PF4)(int, ...);
     typedef bool        (*&PRF0)();
     typedef bool*       (*&PRF1)(int);
     typedef bool&       (*&PRF2)(int, int);
     typedef bool const& (*&PRF3)(int, int, int);
+    typedef bool        (*&PRF4)(int, ...);
     test_result_of<RF0(), bool>();
     test_result_of<RF1(int), bool*>();
     test_result_of<RF2(int, long), bool&>();
     test_result_of<RF3(int, long, int), bool const&>();
+    test_result_of<RF4(int, float, void*), bool>();
     test_result_of<PF0(), bool>();
     test_result_of<PF1(int), bool*>();
     test_result_of<PF2(int, long), bool&>();
     test_result_of<PF3(int, long, int), bool const&>();
+    test_result_of<PF4(int, float, void*), bool>();
     test_result_of<PRF0(), bool>();
     test_result_of<PRF1(int), bool*>();
     test_result_of<PRF2(int, long), bool&>();
     test_result_of<PRF3(int, long, int), bool const&>();
+    test_result_of<PRF4(int, float, void*), bool>();
     }
     { // pointer to member function
 
     typedef int         (S::*PMS0)();
     typedef int*        (S::*PMS1)(long);
     typedef int&        (S::*PMS2)(long, int);
+    typedef const int&  (S::*PMS3)(int, ...);
     test_result_of<PMS0(                             S),   int> ();
     test_result_of<PMS0(                             S&),  int> ();
     test_result_of<PMS0(                             S*),  int> ();
@@ -193,9 +200,13 @@ int main()
     test_no_result<PMS2(std::reference_wrapper<ND>, int, int)>();
     test_no_result<PMS2(std::unique_ptr<ND>,        int, int)>();
 
+    test_result_of<PMS3(S&, int), const int &>();
+    test_result_of<PMS3(S&, int, long), const int &>();
+
     typedef int        (S::*PMS0C)() const;
     typedef int*       (S::*PMS1C)(long) const;
     typedef int&       (S::*PMS2C)(long, int) const;
+    typedef const int& (S::*PMS3C)(int, ...) const;
     test_result_of<PMS0C(               S),   int> ();
     test_result_of<PMS0C(               S&),  int> ();
     test_result_of<PMS0C(const          S&),  int> ();
@@ -238,9 +249,13 @@ int main()
     test_no_result<PMS2C(volatile       S&, int, int)>();
     test_no_result<PMS2C(const volatile S&, int, int)>();
 
+    test_result_of<PMS3C(S&, int), const int &>();
+    test_result_of<PMS3C(S&, int, long), const int &>();
+
     typedef int       (S::*PMS0V)() volatile;
     typedef int*       (S::*PMS1V)(long) volatile;
     typedef int&       (S::*PMS2V)(long, int) volatile;
+    typedef const int& (S::*PMS3V)(int, ...) volatile;
     test_result_of<PMS0V(               S),   int> ();
     test_result_of<PMS0V(               S&),  int> ();
     test_result_of<PMS0V(volatile       S&),  int> ();
@@ -274,9 +289,13 @@ int main()
     test_no_result<PMS2V(const          S&, int, int)>();
     test_no_result<PMS2V(const volatile S&, int, int)>();
 
+    test_result_of<PMS3V(S&, int), const int &>();
+    test_result_of<PMS3V(S&, int, long), const int &>();
+
     typedef int        (S::*PMS0CV)() const volatile;
     typedef int*       (S::*PMS1CV)(long) const volatile;
     typedef int&       (S::*PMS2CV)(long, int) const volatile;
+    typedef const int& (S::*PMS3CV)(int, ...) const volatile;
     test_result_of<PMS0CV(               S),   int> ();
     test_result_of<PMS0CV(               S&),  int> ();
     test_result_of<PMS0CV(const          S&),  int> ();
@@ -321,6 +340,9 @@ int main()
     test_result_of<PMS2CV(volatile       S*&, int, int), int&> ();
     test_result_of<PMS2CV(const volatile S*&, int, int), int&> ();
     test_result_of<PMS2CV(std::unique_ptr<S>, int, int), int&> ();
+
+    test_result_of<PMS3CV(S&, int), const int &>();
+    test_result_of<PMS3CV(S&, int, long), const int &>();
     }
     { // pointer to member data
     typedef char S::*PMD;
diff --git a/test/std/utilities/meta/meta.type.synop/endian.pass.cpp b/test/std/utilities/meta/meta.type.synop/endian.pass.cpp
new file mode 100644
index 000000000000..cf0ab2d26390
--- /dev/null
+++ b/test/std/utilities/meta/meta.type.synop/endian.pass.cpp
@@ -0,0 +1,48 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+
+// enum class endian;
+
+#include <type_traits>
+#include <cstring>
+#include <cassert>
+#include <cstdint>
+
+#include "test_macros.h"
+
+int main() {
+    typedef std::endian E;
+    static_assert(std::is_enum<std::endian>::value, "");
+
+// Check that E is a scoped enum by checking for conversions.
+    typedef std::underlying_type<std::endian>::type UT;
+    static_assert(!std::is_convertible<std::endian, UT>::value, "");
+
+// test that the enumeration values exist
+    static_assert( std::endian::little == std::endian::little );
+    static_assert( std::endian::big    == std::endian::big );
+    static_assert( std::endian::native == std::endian::native );
+    static_assert( std::endian::little != std::endian::big );
+
+//  Technically not required, but true on all existing machines
+    static_assert( std::endian::native == std::endian::little ||
+                   std::endian::native == std::endian::big );
+
+//  Try to check at runtime
+    {
+    uint32_t i = 0x01020304;
+    char c[4];
+    static_assert(sizeof(i) == sizeof(c));
+    std::memcpy(c, &i, sizeof(c));
+
+    assert ((c[0] == 1) == (std::endian::native == std::endian::big));
+    }
+}
diff --git a/test/std/utilities/meta/meta.unary/meta.unary.prop/has_unique_object_representations.pass.cpp b/test/std/utilities/meta/meta.unary/meta.unary.prop/has_unique_object_representations.pass.cpp
new file mode 100644
index 000000000000..52100c30404c
--- /dev/null
+++ b/test/std/utilities/meta/meta.unary/meta.unary.prop/has_unique_object_representations.pass.cpp
@@ -0,0 +1,106 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: clang-3, clang-4, clang-5, apple-clang, gcc-4, gcc-5, gcc-6
+
+// type_traits
+
+// has_unique_object_representations
+
+#include <type_traits>
+
+#include "test_macros.h"
+
+template <class T>
+void test_has_unique_object_representations()
+{
+    static_assert( std::has_unique_object_representations<T>::value, "");
+    static_assert( std::has_unique_object_representations<const T>::value, "");
+    static_assert( std::has_unique_object_representations<volatile T>::value, "");
+    static_assert( std::has_unique_object_representations<const volatile T>::value, "");
+
+    static_assert( std::has_unique_object_representations_v<T>, "");
+    static_assert( std::has_unique_object_representations_v<const T>, "");
+    static_assert( std::has_unique_object_representations_v<volatile T>, "");
+    static_assert( std::has_unique_object_representations_v<const volatile T>, "");
+}
+
+template <class T>
+void test_has_not_has_unique_object_representations()
+{
+    static_assert(!std::has_unique_object_representations<T>::value, "");
+    static_assert(!std::has_unique_object_representations<const T>::value, "");
+    static_assert(!std::has_unique_object_representations<volatile T>::value, "");
+    static_assert(!std::has_unique_object_representations<const volatile T>::value, "");
+
+    static_assert(!std::has_unique_object_representations_v<T>, "");
+    static_assert(!std::has_unique_object_representations_v<const T>, "");
+    static_assert(!std::has_unique_object_representations_v<volatile T>, "");
+    static_assert(!std::has_unique_object_representations_v<const volatile T>, "");
+}
+
+class Empty
+{
+};
+
+class NotEmpty
+{
+    virtual ~NotEmpty();
+};
+
+union EmptyUnion {};
+struct NonEmptyUnion {int x; unsigned y;};
+
+struct bit_zero
+{
+    int :  0;
+};
+
+class Abstract
+{
+    virtual ~Abstract() = 0;
+};
+
+struct A
+{
+    ~A();
+    unsigned foo;
+};
+
+struct B
+{
+   char bar;
+   int foo;
+};
+
+
+int main()
+{
+    test_has_not_has_unique_object_representations<void>();
+    test_has_not_has_unique_object_representations<Empty>();
+    test_has_not_has_unique_object_representations<EmptyUnion>();
+    test_has_not_has_unique_object_representations<NotEmpty>();
+    test_has_not_has_unique_object_representations<bit_zero>();
+    test_has_not_has_unique_object_representations<Abstract>();
+    test_has_not_has_unique_object_representations<B>();
+
+//  I would expect all three of these to have unique representations.
+//  I would also expect that there are systems where they do not.
+//     test_has_not_has_unique_object_representations<int&>();
+//     test_has_not_has_unique_object_representations<int *>();
+//     test_has_not_has_unique_object_representations<double>();
+
+
+    test_has_unique_object_representations<unsigned>();
+    test_has_unique_object_representations<NonEmptyUnion>();
+    test_has_unique_object_representations<char[3]>();
+    test_has_unique_object_representations<char[]>();
+
+}
diff --git a/test/std/utilities/meta/meta.unary/meta.unary.prop/is_assignable.pass.cpp b/test/std/utilities/meta/meta.unary/meta.unary.prop/is_assignable.pass.cpp
index 8d63a23494b9..4808a4dc9e48 100644
--- a/test/std/utilities/meta/meta.unary/meta.unary.prop/is_assignable.pass.cpp
+++ b/test/std/utilities/meta/meta.unary/meta.unary.prop/is_assignable.pass.cpp
@@ -59,8 +59,6 @@ struct E
 template <typename T>
 struct X { T t; };
 
-struct Incomplete;
-
 int main()
 {
     test_is_assignable<int&, int&> ();
diff --git a/test/std/utilities/meta/meta.unary/meta.unary.prop/is_constructible.pass.cpp b/test/std/utilities/meta/meta.unary/meta.unary.prop/is_constructible.pass.cpp
index 1f7c32a8cc07..b90363a5c380 100644
--- a/test/std/utilities/meta/meta.unary/meta.unary.prop/is_constructible.pass.cpp
+++ b/test/std/utilities/meta/meta.unary/meta.unary.prop/is_constructible.pass.cpp
@@ -30,6 +30,7 @@ struct A
 {
     explicit A(int);
     A(int, double);
+    A(int, long, double);
 #if TEST_STD_VER >= 11
 private:
 #endif
@@ -106,6 +107,16 @@ void test_is_constructible()
 #endif
 }
 
+template <class T, class A0, class A1, class A2>
+void test_is_constructible()
+{
+    static_assert(( std::is_constructible<T, A0, A1, A2>::value), "");
+    LIBCPP11_STATIC_ASSERT((std::__libcpp_is_constructible<T, A0, A1, A2>::type::value), "");
+#if TEST_STD_VER > 14
+    static_assert(( std::is_constructible_v<T, A0, A1, A2>), "");
+#endif
+}
+
 template <class T>
 void test_is_not_constructible()
 {
@@ -146,6 +157,7 @@ int main()
     test_is_constructible<int, const int> ();
     test_is_constructible<A, int> ();
     test_is_constructible<A, int, double> ();
+    test_is_constructible<A, int, long, double> ();
     test_is_constructible<int&, int&> ();
 
     test_is_not_constructible<A> ();
diff --git a/test/std/utilities/meta/meta.unary/meta.unary.prop/is_trivially_copyable.pass.cpp b/test/std/utilities/meta/meta.unary/meta.unary.prop/is_trivially_copyable.pass.cpp
index 0bb373c96620..ac4664312f84 100644
--- a/test/std/utilities/meta/meta.unary/meta.unary.prop/is_trivially_copyable.pass.cpp
+++ b/test/std/utilities/meta/meta.unary/meta.unary.prop/is_trivially_copyable.pass.cpp
@@ -13,7 +13,7 @@
 
 // These compilers have not implemented Core 2094 which makes volatile
 // qualified types trivially copyable.
-// XFAIL: clang-3, clang-4, apple-clang, gcc
+// XFAIL: clang-3, clang-4, apple-clang-6, apple-clang-7, apple-clang-8, apple-clang-9.0, gcc
 
 #include <type_traits>
 #include <cassert>
diff --git a/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.fail.cpp b/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.fail.cpp
new file mode 100644
index 000000000000..1e1e82b03d70
--- /dev/null
+++ b/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.fail.cpp
@@ -0,0 +1,46 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <optional>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: clang-5
+// UNSUPPORTED: libcpp-no-deduction-guides
+// Clang 5 will generate bad implicit deduction guides
+//  Specifically, for the copy constructor.
+
+
+// template<class T>
+//   optional(T) -> optional<T>;
+
+
+#include <optional>
+#include <cassert>
+
+struct A {};
+
+int main()
+{
+//  Test the explicit deduction guides
+
+//  Test the implicit deduction guides
+    {
+//  optional()
+    std::optional opt;   // expected-error-re {{{{declaration of variable 'opt' with deduced type 'std::optional' requires an initializer|no viable constructor or deduction guide for deduction of template arguments of 'optional'}}}}
+//  clang-6 gives a bogus error here:
+//      declaration of variable 'opt' with deduced type 'std::optional' requires an initializer
+//  clang-7 (and later) give a better message:
+//      no viable constructor or deduction guide for deduction of template arguments of 'optional'
+//  So we check for one or the other.
+    }
+
+    {
+//  optional(nullopt_t)
+    std::optional opt(std::nullopt);   // expected-error-re@optional:* {{static_assert failed{{.*}} "instantiation of optional with nullopt_t is ill-formed"}}
+    }
+}
diff --git a/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.pass.cpp b/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.pass.cpp
new file mode 100644
index 000000000000..6ce35a489d43
--- /dev/null
+++ b/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.pass.cpp
@@ -0,0 +1,54 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <optional>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: clang-5, apple-clang-9
+// UNSUPPORTED: libcpp-no-deduction-guides
+// Clang 5 will generate bad implicit deduction guides
+//  Specifically, for the copy constructor.
+
+
+// template<class T>
+//   optional(T) -> optional<T>;
+
+
+#include <optional>
+#include <cassert>
+
+struct A {};
+
+int main()
+{
+//  Test the explicit deduction guides
+    {
+//  optional(T)
+    std::optional opt(5);
+    static_assert(std::is_same_v<decltype(opt), std::optional<int>>, "");
+    assert(static_cast<bool>(opt));
+    assert(*opt == 5);
+    }
+
+    {
+//  optional(T)
+    std::optional opt(A{});
+    static_assert(std::is_same_v<decltype(opt), std::optional<A>>, "");
+    assert(static_cast<bool>(opt));
+    }
+
+//  Test the implicit deduction guides
+    {
+//  optional(optional);
+    std::optional<char> source('A');
+    std::optional opt(source);
+    static_assert(std::is_same_v<decltype(opt), std::optional<char>>, "");
+    assert(static_cast<bool>(opt) == static_cast<bool>(source));
+    assert(*opt == *source);
+    }
+}
diff --git a/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/PR20855_tuple_ref_binding_diagnostics.pass.cpp b/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/PR20855_tuple_ref_binding_diagnostics.pass.cpp
new file mode 100644
index 000000000000..457df5602850
--- /dev/null
+++ b/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/PR20855_tuple_ref_binding_diagnostics.pass.cpp
@@ -0,0 +1,137 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03
+
+// <tuple>
+
+// See llvm.org/PR20855
+
+#include <tuple>
+#include <string>
+#include <cassert>
+#include "test_macros.h"
+
+#if TEST_HAS_BUILTIN_IDENTIFIER(__reference_binds_to_temporary)
+# define ASSERT_REFERENCE_BINDS_TEMPORARY(...) static_assert(__reference_binds_to_temporary(__VA_ARGS__), "")
+# define ASSERT_NOT_REFERENCE_BINDS_TEMPORARY(...) static_assert(!__reference_binds_to_temporary(__VA_ARGS__), "")
+#else
+# define ASSERT_REFERENCE_BINDS_TEMPORARY(...) static_assert(true, "")
+# define ASSERT_NOT_REFERENCE_BINDS_TEMPORARY(...) static_assert(true, "")
+#endif
+
+template <class Tp>
+struct ConvertsTo {
+  using RawTp = typename std::remove_cv< typename std::remove_reference<Tp>::type>::type;
+
+  operator Tp() const {
+    return static_cast<Tp>(value);
+  }
+
+  mutable RawTp value;
+};
+
+struct Base {};
+struct Derived : Base {};
+
+
+static_assert(std::is_same<decltype("abc"), decltype(("abc"))>::value, "");
+ASSERT_REFERENCE_BINDS_TEMPORARY(std::string const&, decltype("abc"));
+ASSERT_REFERENCE_BINDS_TEMPORARY(std::string const&, decltype(("abc")));
+ASSERT_REFERENCE_BINDS_TEMPORARY(std::string const&, const char*&&);
+
+ASSERT_NOT_REFERENCE_BINDS_TEMPORARY(int&, const ConvertsTo<int&>&);
+ASSERT_NOT_REFERENCE_BINDS_TEMPORARY(const int&, ConvertsTo<int&>&);
+ASSERT_NOT_REFERENCE_BINDS_TEMPORARY(Base&, Derived&);
+
+
+static_assert(std::is_constructible<int&, std::reference_wrapper<int>>::value, "");
+static_assert(std::is_constructible<int const&, std::reference_wrapper<int>>::value, "");
+
+template <class T> struct CannotDeduce {
+ using type = T;
+};
+
+template <class ...Args>
+void F(typename CannotDeduce<std::tuple<Args...>>::type const&) {}
+
+void compile_tests() {
+  {
+    F<int, int const&>(std::make_tuple(42, 42));
+  }
+  {
+    F<int, int const&>(std::make_tuple<const int&, const int&>(42, 42));
+    std::tuple<int, int const&> t(std::make_tuple<const int&, const int&>(42, 42));
+  }
+  {
+    auto fn = &F<int, std::string const&>;
+    fn(std::tuple<int, std::string const&>(42, std::string("a")));
+    fn(std::make_tuple(42, std::string("a")));
+  }
+  {
+    Derived d;
+    std::tuple<Base&, Base const&> t(d, d);
+  }
+  {
+    ConvertsTo<int&> ct;
+    std::tuple<int, int&> t(42, ct);
+  }
+}
+
+void allocator_tests() {
+    std::allocator<void> alloc;
+    int x = 42;
+    {
+        std::tuple<int&> t(std::ref(x));
+        assert(&std::get<0>(t) == &x);
+        std::tuple<int&> t1(std::allocator_arg, alloc, std::ref(x));
+        assert(&std::get<0>(t1) == &x);
+    }
+    {
+        auto r = std::ref(x);
+        auto const& cr = r;
+        std::tuple<int&> t(r);
+        assert(&std::get<0>(t) == &x);
+        std::tuple<int&> t1(cr);
+        assert(&std::get<0>(t1) == &x);
+        std::tuple<int&> t2(std::allocator_arg, alloc, r);
+        assert(&std::get<0>(t2) == &x);
+        std::tuple<int&> t3(std::allocator_arg, alloc, cr);
+        assert(&std::get<0>(t3) == &x);
+    }
+    {
+        std::tuple<int const&> t(std::ref(x));
+        assert(&std::get<0>(t) == &x);
+        std::tuple<int const&> t2(std::cref(x));
+        assert(&std::get<0>(t2) == &x);
+        std::tuple<int const&> t3(std::allocator_arg, alloc, std::ref(x));
+        assert(&std::get<0>(t3) == &x);
+        std::tuple<int const&> t4(std::allocator_arg, alloc, std::cref(x));
+        assert(&std::get<0>(t4) == &x);
+    }
+    {
+        auto r = std::ref(x);
+        auto cr = std::cref(x);
+        std::tuple<int const&> t(r);
+        assert(&std::get<0>(t) == &x);
+        std::tuple<int const&> t2(cr);
+        assert(&std::get<0>(t2) == &x);
+        std::tuple<int const&> t3(std::allocator_arg, alloc, r);
+        assert(&std::get<0>(t3) == &x);
+        std::tuple<int const&> t4(std::allocator_arg, alloc, cr);
+        assert(&std::get<0>(t4) == &x);
+    }
+}
+
+
+int main() {
+  compile_tests();
+  allocator_tests();
+}
diff --git a/test/std/utilities/utility/exchange/exchange.pass.cpp b/test/std/utilities/utility/exchange/exchange.pass.cpp
index 2d01d6c8c8af..1a5007ea41fb 100644
--- a/test/std/utilities/utility/exchange/exchange.pass.cpp
+++ b/test/std/utilities/utility/exchange/exchange.pass.cpp
@@ -8,14 +8,38 @@
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++98, c++03, c++11
-// utilities
+// <utility>
 
 // exchange
 
+// template<class T, class U=T>
+//    constexpr T            // constexpr after C++17
+//    exchange(T& obj, U&& new_value);
+
 #include <utility>
 #include <cassert>
 #include <string>
 
+#include "test_macros.h"
+
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool test_constexpr() {
+    int v = 12;
+
+    if (12 != std::exchange(v,23) || v != 23)
+        return false;
+
+    if (23 != std::exchange(v,static_cast<short>(67)) || v != 67)
+        return false;
+
+    if (67 != std::exchange<int, short>(v, {}) || v != 0)
+        return false;
+    return true;
+    }
+#endif
+
+
+
 int main()
 {
     {
@@ -53,4 +77,8 @@ int main()
     assert ( std::exchange ( s3, "" ) == s2 );
     assert ( s3.size () == 0 );
     }
+
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 }
diff --git a/test/std/utilities/utility/pairs/pairs.pair/assign_const_pair_U_V.pass.cpp b/test/std/utilities/utility/pairs/pairs.pair/assign_const_pair_U_V.pass.cpp
index 132443f66a7c..90722c393c68 100644
--- a/test/std/utilities/utility/pairs/pairs.pair/assign_const_pair_U_V.pass.cpp
+++ b/test/std/utilities/utility/pairs/pairs.pair/assign_const_pair_U_V.pass.cpp
@@ -16,6 +16,11 @@
 #include <utility>
 #include <cassert>
 
+#include "test_macros.h"
+#if TEST_STD_VER >= 11
+#include "archetypes.hpp"
+#endif
+
 int main()
 {
     {
@@ -27,4 +32,21 @@ int main()
         assert(p2.first == 3);
         assert(p2.second == 4);
     }
+#if TEST_STD_VER >= 11
+    {
+       using C = TestTypes::TestType;
+       using P = std::pair<int, C>;
+       using T = std::pair<long, C>;
+       const T t(42, -42);
+       P p(101, 101);
+       C::reset_constructors();
+       p = t;
+       assert(C::constructed == 0);
+       assert(C::assigned == 1);
+       assert(C::copy_assigned == 1);
+       assert(C::move_assigned == 0);
+       assert(p.first == 42);
+       assert(p.second.value == -42);
+    }
+#endif
 }
diff --git a/test/std/utilities/utility/pairs/pairs.pair/assign_rv_pair.pass.cpp b/test/std/utilities/utility/pairs/pairs.pair/assign_rv_pair.pass.cpp
index 38089200e4da..f02e24b24140 100644
--- a/test/std/utilities/utility/pairs/pairs.pair/assign_rv_pair.pass.cpp
+++ b/test/std/utilities/utility/pairs/pairs.pair/assign_rv_pair.pass.cpp
@@ -49,7 +49,7 @@ int CountAssign::moved = 0;
 int main()
 {
     {
-        typedef std::pair<std::unique_ptr<int>, short> P;
+        typedef std::pair<std::unique_ptr<int>, int> P;
         P p1(std::unique_ptr<int>(new int(3)), 4);
         P p2;
         p2 = std::move(p1);
diff --git a/test/std/utilities/utility/pairs/pairs.pair/assign_rv_pair_U_V.pass.cpp b/test/std/utilities/utility/pairs/pairs.pair/assign_rv_pair_U_V.pass.cpp
index 76dfc3f65a23..b7a89a84460d 100644
--- a/test/std/utilities/utility/pairs/pairs.pair/assign_rv_pair_U_V.pass.cpp
+++ b/test/std/utilities/utility/pairs/pairs.pair/assign_rv_pair_U_V.pass.cpp
@@ -18,6 +18,7 @@
 #include <utility>
 #include <memory>
 #include <cassert>
+#include <archetypes.hpp>
 
 struct Base
 {
@@ -40,4 +41,19 @@ int main()
         assert(p2.first == nullptr);
         assert(p2.second == 4);
     }
+    {
+       using C = TestTypes::TestType;
+       using P = std::pair<int, C>;
+       using T = std::pair<long, C>;
+       T t(42, -42);
+       P p(101, 101);
+       C::reset_constructors();
+       p = std::move(t);
+       assert(C::constructed == 0);
+       assert(C::assigned == 1);
+       assert(C::copy_assigned == 0);
+       assert(C::move_assigned == 1);
+       assert(p.first == 42);
+       assert(p.second.value == -42);
+    }
 }
diff --git a/test/std/utilities/utility/pairs/pairs.pair/assign_tuple.pass.cpp b/test/std/utilities/utility/pairs/pairs.pair/assign_tuple.pass.cpp
deleted file mode 100644
index ef7bebcf5c29..000000000000
--- a/test/std/utilities/utility/pairs/pairs.pair/assign_tuple.pass.cpp
+++ /dev/null
@@ -1,140 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is dual licensed under the MIT and the University of Illinois Open
-// Source Licenses. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-// UNSUPPORTED: c++98, c++03
-
-// <utility>
-
-// template <class T1, class T2> struct pair
-
-// template<class U, class V> pair& operator=(tuple<U, V>&& p);
-
-#include <utility>
-#include <tuple>
-#include <array>
-#include <memory>
-#include <cassert>
-
-// Clang warns about missing braces when initializing std::array.
-#if defined(__clang__)
-#pragma clang diagnostic ignored "-Wmissing-braces"
-#endif
-
-struct CountingType {
-  static int constructed;
-  static int copy_constructed;
-  static int move_constructed;
-  static int assigned;
-  static int copy_assigned;
-  static int move_assigned;
-  static void reset() {
-      constructed = copy_constructed = move_constructed = 0;
-      assigned = copy_assigned = move_assigned = 0;
-  }
-  CountingType() : value(0) { ++constructed; }
-  CountingType(int v) : value(v) { ++constructed; }
-  CountingType(CountingType const& o) : value(o.value) { ++constructed; ++copy_constructed; }
-  CountingType(CountingType&& o) : value(o.value) { ++constructed; ++move_constructed; o.value = -1;}
-
-  CountingType& operator=(CountingType const& o) {
-      ++assigned;
-      ++copy_assigned;
-      value = o.value;
-      return *this;
-  }
-  CountingType& operator=(CountingType&& o) {
-      ++assigned;
-      ++move_assigned;
-      value = o.value;
-      o.value = -1;
-      return *this;
-  }
-  int value;
-};
-int CountingType::constructed;
-int CountingType::copy_constructed;
-int CountingType::move_constructed;
-int CountingType::assigned;
-int CountingType::copy_assigned;
-int CountingType::move_assigned;
-
-int main()
-{
-    using C = CountingType;
-    {
-       using P = std::pair<int, C>;
-       using T = std::tuple<int, C>;
-       T t(42, C{42});
-       P p(101, C{101});
-       C::reset();
-       p = t;
-       assert(C::constructed == 0);
-       assert(C::assigned == 1);
-       assert(C::copy_assigned == 1);
-       assert(C::move_assigned == 0);
-       assert(p.first == 42);
-       assert(p.second.value == 42);
-    }
-    {
-       using P = std::pair<int, C>;
-       using T = std::tuple<int, C>;
-       T t(42, -42);
-       P p(101, 101);
-       C::reset();
-       p = std::move(t);
-       assert(C::constructed == 0);
-       assert(C::assigned == 1);
-       assert(C::copy_assigned == 0);
-       assert(C::move_assigned == 1);
-       assert(p.first == 42);
-       assert(p.second.value == -42);
-    }
-    {
-       using P = std::pair<C, C>;
-       using T = std::array<C, 2>;
-       T t = {42, -42};
-       P p{101, 101};
-       C::reset();
-       p = t;
-       assert(C::constructed == 0);
-       assert(C::assigned == 2);
-       assert(C::copy_assigned == 2);
-       assert(C::move_assigned == 0);
-       assert(p.first.value == 42);
-       assert(p.second.value == -42);
-    }
-    {
-       using P = std::pair<C, C>;
-       using T = std::array<C, 2>;
-       T t = {42, -42};
-       P p{101, 101};
-       C::reset();
-       p = t;
-       assert(C::constructed == 0);
-       assert(C::assigned == 2);
-       assert(C::copy_assigned == 2);
-       assert(C::move_assigned == 0);
-       assert(p.first.value == 42);
-       assert(p.second.value == -42);
-    }
-    {
-       using P = std::pair<C, C>;
-       using T = std::array<C, 2>;
-       T t = {42, -42};
-       P p{101, 101};
-       C::reset();
-       p = std::move(t);
-       assert(C::constructed == 0);
-       assert(C::assigned == 2);
-       assert(C::copy_assigned == 0);
-       assert(C::move_assigned == 2);
-       assert(p.first.value == 42);
-       assert(p.second.value == -42);
-    }
-}
diff --git a/test/std/utilities/utility/pairs/pairs.pair/const_pair_U_V.pass.cpp b/test/std/utilities/utility/pairs/pairs.pair/const_pair_U_V.pass.cpp
index 715b65537761..d2cb6b10984e 100644
--- a/test/std/utilities/utility/pairs/pairs.pair/const_pair_U_V.pass.cpp
+++ b/test/std/utilities/utility/pairs/pairs.pair/const_pair_U_V.pass.cpp
@@ -57,7 +57,7 @@ struct ImplicitT {
 int main()
 {
     {
-        typedef std::pair<int, short> P1;
+        typedef std::pair<int, int> P1;
         typedef std::pair<double, long> P2;
         const P1 p1(3, 4);
         const P2 p2 = p1;
@@ -154,7 +154,7 @@ int main()
     }
 #if TEST_STD_VER > 11
     {
-        typedef std::pair<int, short> P1;
+        typedef std::pair<int, int> P1;
         typedef std::pair<double, long> P2;
         constexpr P1 p1(3, 4);
         constexpr P2 p2 = p1;
diff --git a/test/std/utilities/utility/pairs/pairs.pair/rv_pair_U_V.pass.cpp b/test/std/utilities/utility/pairs/pairs.pair/rv_pair_U_V.pass.cpp
index f5d3bb621deb..7e40bed21820 100644
--- a/test/std/utilities/utility/pairs/pairs.pair/rv_pair_U_V.pass.cpp
+++ b/test/std/utilities/utility/pairs/pairs.pair/rv_pair_U_V.pass.cpp
@@ -67,7 +67,7 @@ struct ImplicitT {
 int main()
 {
     {
-        typedef std::pair<std::unique_ptr<Derived>, short> P1;
+        typedef std::pair<std::unique_ptr<Derived>, int> P1;
         typedef std::pair<std::unique_ptr<Base>, long> P2;
         P1 p1(std::unique_ptr<Derived>(), 4);
         P2 p2 = std::move(p1);
diff --git a/test/std/utilities/variant/variant.variant/variant.ctor/in_place_index_init_list_args.pass.cpp b/test/std/utilities/variant/variant.variant/variant.ctor/in_place_index_init_list_args.pass.cpp
index 608cdf9d6efb..9d0bf55fb538 100644
--- a/test/std/utilities/variant/variant.variant/variant.ctor/in_place_index_init_list_args.pass.cpp
+++ b/test/std/utilities/variant/variant.variant/variant.ctor/in_place_index_init_list_args.pass.cpp
@@ -73,6 +73,12 @@ void test_ctor_sfinae() {
         !std::is_constructible<V, std::in_place_index_t<2>, IL>::value, "");
     static_assert(!test_convertible<V, std::in_place_index_t<2>, IL>(), "");
   }
+  { // index not in variant
+    using V = std::variant<InitList, InitListArg, int>;
+    static_assert(
+        !std::is_constructible<V, std::in_place_index_t<3>, IL>::value, "");
+    static_assert(!test_convertible<V, std::in_place_index_t<3>, IL>(), "");
+  }
 }
 
 void test_ctor_basic() {