[unittests] Change std::sort to llvm::sort in response to r327219

[mgrang]

Summary

r327219 added wrappers to std::sort which randomly shuffle the container before sorting.
This will help in uncovering non-determinism caused due to undefined sorting
order of objects having the same key.

To make use of that infrastructure we need to invoke llvm::sort instead of std::sort.

Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort.
Refer the comments section in D44363 for a list of all the required patches.

[dexonsmith]

LGTM.

unittests/ADT/STLExtrasTest.cpp

 
 TEST(STLExtrasTest, PartitionAdaptor) {
   std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
 
   auto I = partition(V, [](int i) { return i % 2 == 0; });
   ASSERT_EQ(V.begin() + 4, I);
 
   // Sort the two halves as partition may have messed with the order.
-  std::sort(V.begin(), I);
-  std::sort(I, V.end());
+  llvm::sort(V.begin(), I);
+  llvm::sort(I, V.end());
 
   EXPECT_EQ(2, V[0]);
   EXPECT_EQ(4, V[1]);
   EXPECT_EQ(6, V[2]);
   EXPECT_EQ(8, V[3]);
   EXPECT_EQ(1, V[4]);
   EXPECT_EQ(3, V[5]);
   EXPECT_EQ(5, V[6]);

unittests/ADT/SmallPtrSetTest.cpp

TEST(SmallPtrSetTest, dereferenceAndIterate) {
   // Iterate from each and count how many times each element is found.
   int Found[sizeof(Ints)/sizeof(int)] = {0};
   for (int &I : Ints)
     for (auto F = S.find(&I), E = S.end(); F != E; ++F)
       ++Found[*F - Ints];
 
   // Sort.  We should hit the first element just once and the final element N
   // times.
-  std::sort(std::begin(Found), std::end(Found));
+  llvm::sort(std::begin(Found), std::end(Found));
   for (auto F = std::begin(Found), E = std::end(Found); F != E; ++F)
     EXPECT_EQ(F - Found + 1, *F);
 }
 
 // Verify that const pointers work for count and find even when the underlying
 // SmallPtrSet is not for a const pointer type.
 TEST(SmallPtrSetTest, ConstTest) {
   SmallPtrSet<int *, 8> IntSet;

unittests/ADT/StringMapTest.cpp

 TEST_F(StringMapTest, IterMapKeys) {
   StringMap<int> Map;
   Map["A"] = 1;
   Map["B"] = 2;
   Map["C"] = 3;
   Map["D"] = 3;
 
   auto Keys = to_vector<4>(Map.keys());
-  std::sort(Keys.begin(), Keys.end());
+  llvm::sort(Keys.begin(), Keys.end());
 
   SmallVector<StringRef, 4> Expected = {"A", "B", "C", "D"};
   EXPECT_EQ(Expected, Keys);
 }
 
 TEST_F(StringMapTest, IterSetKeys) {
   StringSet<> Set;
   Set.insert("A");
   Set.insert("B");
   Set.insert("C");
   Set.insert("D");
 
   auto Keys = to_vector<4>(Set.keys());
-  std::sort(Keys.begin(), Keys.end());
+  llvm::sort(Keys.begin(), Keys.end());
 
   SmallVector<StringRef, 4> Expected = {"A", "B", "C", "D"};
   EXPECT_EQ(Expected, Keys);
 }
 
 // Create a non-default constructable value
 struct StringMapTestStruct {
   StringMapTestStruct(int i) : i(i) {}

unittests/Analysis/LazyCallGraphTest.cpp

TEST(LazyCallGraphTest, BasicGraphFormation) {
   EXPECT_EQ(CG.end(), I);
 
   // Build vectors and sort them for the rest of the assertions to make them
   // independent of order.
   std::vector<std::string> Nodes;
 
   for (LazyCallGraph::Edge &E : A1.populate())
     Nodes.push_back(E.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ("a2", Nodes[0]);
   EXPECT_EQ("b2", Nodes[1]);
   EXPECT_EQ("c3", Nodes[2]);
   Nodes.clear();
 
   A2.populate();
   EXPECT_EQ(A2->end(), std::next(A2->begin()));
   EXPECT_EQ("a3", A2->begin()->getFunction().getName());
   A3.populate();
   EXPECT_EQ(A3->end(), std::next(A3->begin()));
   EXPECT_EQ("a1", A3->begin()->getFunction().getName());
 
   for (LazyCallGraph::Edge &E : B1.populate())
     Nodes.push_back(E.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ("b2", Nodes[0]);
   EXPECT_EQ("d3", Nodes[1]);
   Nodes.clear();
 
   B2.populate();
   EXPECT_EQ(B2->end(), std::next(B2->begin()));
   EXPECT_EQ("b3", B2->begin()->getFunction().getName());
   B3.populate();
   EXPECT_EQ(B3->end(), std::next(B3->begin()));
   EXPECT_EQ("b1", B3->begin()->getFunction().getName());
 
   for (LazyCallGraph::Edge &E : C1.populate())
     Nodes.push_back(E.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ("c2", Nodes[0]);
   EXPECT_EQ("d2", Nodes[1]);
   Nodes.clear();
 
   C2.populate();
   EXPECT_EQ(C2->end(), std::next(C2->begin()));
   EXPECT_EQ("c3", C2->begin()->getFunction().getName());
   C3.populate();
TEST(LazyCallGraphTest, BasicGraphFormation) {
   // Now lets look at the RefSCCs and SCCs.
   CG.buildRefSCCs();
   auto J = CG.postorder_ref_scc_begin();
 
   LazyCallGraph::RefSCC &D = *J++;
   ASSERT_EQ(1, D.size());
   for (LazyCallGraph::Node &N : *D.begin())
     Nodes.push_back(N.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("d1", Nodes[0]);
   EXPECT_EQ("d2", Nodes[1]);
   EXPECT_EQ("d3", Nodes[2]);
   Nodes.clear();
   EXPECT_FALSE(D.isParentOf(D));
   EXPECT_FALSE(D.isChildOf(D));
   EXPECT_FALSE(D.isAncestorOf(D));
   EXPECT_FALSE(D.isDescendantOf(D));
   EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin());
 
   LazyCallGraph::RefSCC &C = *J++;
   ASSERT_EQ(1, C.size());
   for (LazyCallGraph::Node &N : *C.begin())
     Nodes.push_back(N.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("c1", Nodes[0]);
   EXPECT_EQ("c2", Nodes[1]);
   EXPECT_EQ("c3", Nodes[2]);
   Nodes.clear();
   EXPECT_TRUE(C.isParentOf(D));
   EXPECT_FALSE(C.isChildOf(D));
   EXPECT_TRUE(C.isAncestorOf(D));
   EXPECT_FALSE(C.isDescendantOf(D));
   EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin()));
 
   LazyCallGraph::RefSCC &B = *J++;
   ASSERT_EQ(1, B.size());
   for (LazyCallGraph::Node &N : *B.begin())
     Nodes.push_back(N.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("b1", Nodes[0]);
   EXPECT_EQ("b2", Nodes[1]);
   EXPECT_EQ("b3", Nodes[2]);
   Nodes.clear();
   EXPECT_TRUE(B.isParentOf(D));
   EXPECT_FALSE(B.isChildOf(D));
   EXPECT_TRUE(B.isAncestorOf(D));
   EXPECT_FALSE(B.isDescendantOf(D));
   EXPECT_FALSE(B.isAncestorOf(C));
   EXPECT_FALSE(C.isAncestorOf(B));
   EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin(), 2));
 
   LazyCallGraph::RefSCC &A = *J++;
   ASSERT_EQ(1, A.size());
   for (LazyCallGraph::Node &N : *A.begin())
     Nodes.push_back(N.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("a1", Nodes[0]);
   EXPECT_EQ("a2", Nodes[1]);
   EXPECT_EQ("a3", Nodes[2]);
   Nodes.clear();
   EXPECT_TRUE(A.isParentOf(B));
   EXPECT_TRUE(A.isParentOf(C));
   EXPECT_FALSE(A.isParentOf(D));
TEST(LazyCallGraphTest, InnerSCCFormation) {
   LazyCallGraph::RefSCC &RC = *I++;
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 
   // Now walk the four SCCs which should be in post-order.
   auto J = RC.begin();
   LazyCallGraph::SCC &D = *J++;
   for (LazyCallGraph::Node &N : D)
     Nodes.push_back(N.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("d1", Nodes[0]);
   EXPECT_EQ("d2", Nodes[1]);
   EXPECT_EQ("d3", Nodes[2]);
   Nodes.clear();
 
   LazyCallGraph::SCC &B = *J++;
   for (LazyCallGraph::Node &N : B)
     Nodes.push_back(N.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("b1", Nodes[0]);
   EXPECT_EQ("b2", Nodes[1]);
   EXPECT_EQ("b3", Nodes[2]);
   Nodes.clear();
 
   LazyCallGraph::SCC &C = *J++;
   for (LazyCallGraph::Node &N : C)
     Nodes.push_back(N.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("c1", Nodes[0]);
   EXPECT_EQ("c2", Nodes[1]);
   EXPECT_EQ("c3", Nodes[2]);
   Nodes.clear();
 
   LazyCallGraph::SCC &A = *J++;
   for (LazyCallGraph::Node &N : A)
     Nodes.push_back(N.getFunction().getName());
-  std::sort(Nodes.begin(), Nodes.end());
+  llvm::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ(3u, Nodes.size());
   EXPECT_EQ("a1", Nodes[0]);
   EXPECT_EQ("a2", Nodes[1]);
   EXPECT_EQ("a3", Nodes[2]);
   Nodes.clear();
 
   EXPECT_EQ(RC.end(), J);
 }

unittests/ProfileData/InstrProfTest.cpp

TEST_P(MaybeSparseInstrProfTest, value_prof_data_read_write) {
   ASSERT_EQ(2U, Record.getNumValueDataForSite(IPVK_IndirectCallTarget, 3));
   ASSERT_EQ(0U, Record.getNumValueDataForSite(IPVK_IndirectCallTarget, 4));
 
   auto Cmp = [](const InstrProfValueData &VD1, const InstrProfValueData &VD2) {
     return VD1.Count > VD2.Count;
   };
   std::unique_ptr<InstrProfValueData[]> VD_0(
       Record.getValueForSite(IPVK_IndirectCallTarget, 0));
-  std::sort(&VD_0[0], &VD_0[5], Cmp);
+  llvm::sort(&VD_0[0], &VD_0[5], Cmp);
   ASSERT_EQ(StringRef((const char *)VD_0[0].Value, 7), StringRef("callee2"));
   ASSERT_EQ(1000U, VD_0[0].Count);
   ASSERT_EQ(StringRef((const char *)VD_0[1].Value, 7), StringRef("callee3"));
   ASSERT_EQ(500U, VD_0[1].Count);
   ASSERT_EQ(StringRef((const char *)VD_0[2].Value, 7), StringRef("callee1"));
   ASSERT_EQ(400U, VD_0[2].Count);
   ASSERT_EQ(StringRef((const char *)VD_0[3].Value, 7), StringRef("callee4"));
   ASSERT_EQ(300U, VD_0[3].Count);
   ASSERT_EQ(StringRef((const char *)VD_0[4].Value, 7), StringRef("callee5"));
   ASSERT_EQ(100U, VD_0[4].Count);
 
   std::unique_ptr<InstrProfValueData[]> VD_1(
       Record.getValueForSite(IPVK_IndirectCallTarget, 1));
-  std::sort(&VD_1[0], &VD_1[4], Cmp);
+  llvm::sort(&VD_1[0], &VD_1[4], Cmp);
   ASSERT_EQ(StringRef((const char *)VD_1[0].Value, 7), StringRef("callee2"));
   ASSERT_EQ(2500U, VD_1[0].Count);
   ASSERT_EQ(StringRef((const char *)VD_1[1].Value, 7), StringRef("callee1"));
   ASSERT_EQ(1300U, VD_1[1].Count);
   ASSERT_EQ(StringRef((const char *)VD_1[2].Value, 7), StringRef("callee3"));
   ASSERT_EQ(1000U, VD_1[2].Count);
   ASSERT_EQ(StringRef((const char *)VD_1[3].Value, 7), StringRef("callee5"));
   ASSERT_EQ(800U, VD_1[3].Count);
 
   std::unique_ptr<InstrProfValueData[]> VD_2(
       Record.getValueForSite(IPVK_IndirectCallTarget, 2));
-  std::sort(&VD_2[0], &VD_2[3], Cmp);
+  llvm::sort(&VD_2[0], &VD_2[3], Cmp);
   ASSERT_EQ(StringRef((const char *)VD_2[0].Value, 7), StringRef("callee4"));
   ASSERT_EQ(5500U, VD_2[0].Count);
   ASSERT_EQ(StringRef((const char *)VD_2[1].Value, 7), StringRef("callee3"));
   ASSERT_EQ(1000U, VD_2[1].Count);
   ASSERT_EQ(StringRef((const char *)VD_2[2].Value, 7), StringRef("callee6"));
   ASSERT_EQ(800U, VD_2[2].Count);
 
   std::unique_ptr<InstrProfValueData[]> VD_3(
       Record.getValueForSite(IPVK_IndirectCallTarget, 3));
-  std::sort(&VD_3[0], &VD_3[2], Cmp);
+  llvm::sort(&VD_3[0], &VD_3[2], Cmp);
   ASSERT_EQ(StringRef((const char *)VD_3[0].Value, 7), StringRef("callee3"));
   ASSERT_EQ(2000U, VD_3[0].Count);
   ASSERT_EQ(StringRef((const char *)VD_3[1].Value, 7), StringRef("callee2"));
   ASSERT_EQ(1800U, VD_3[1].Count);
 }
 
 TEST_P(MaybeSparseInstrProfTest, value_prof_data_read_write_mapping) {
 
TEST_P(MaybeSparseInstrProfTest, value_prof_data_read_write_mapping) {
   ASSERT_EQ(5U, Record.getNumValueSites(IPVK_IndirectCallTarget));
   ASSERT_EQ(5U, Record.getNumValueDataForSite(IPVK_IndirectCallTarget, 0));
 
   auto Cmp = [](const InstrProfValueData &VD1, const InstrProfValueData &VD2) {
     return VD1.Count > VD2.Count;
   };
   std::unique_ptr<InstrProfValueData[]> VD_0(
       Record.getValueForSite(IPVK_IndirectCallTarget, 0));
-  std::sort(&VD_0[0], &VD_0[5], Cmp);
+  llvm::sort(&VD_0[0], &VD_0[5], Cmp);
   ASSERT_EQ(VD_0[0].Value, 0x2000ULL);
   ASSERT_EQ(1000U, VD_0[0].Count);
   ASSERT_EQ(VD_0[1].Value, 0x3000ULL);
   ASSERT_EQ(500U, VD_0[1].Count);
   ASSERT_EQ(VD_0[2].Value, 0x1000ULL);
   ASSERT_EQ(400U, VD_0[2].Count);
 
   // callee5 does not have a mapped value -- default to 0.

unittests/Support/Path.cpp

TEST_F(FileSystemTest, BrokenSymlinkDirectoryIteration) {
   // The directory iterator doesn't stat the file, so we should be able to
   // iterate over the whole directory.
   std::error_code ec;
   for (fs::directory_iterator i(Twine(TestDirectory) + "/symlink", ec), e;
        i != e; i.increment(ec)) {
     ASSERT_NO_ERROR(ec);
     visited.push_back(path::filename(i->path()));
   }
-  std::sort(visited.begin(), visited.end());
+  llvm::sort(visited.begin(), visited.end());
   v_t expected = {"a", "b", "c", "d", "e"};
   ASSERT_TRUE(visited.size() == expected.size());
   ASSERT_TRUE(std::equal(visited.begin(), visited.end(), expected.begin()));
   visited.clear();
 
   // The recursive directory iterator has to stat the file, so we need to skip
   // the broken symlinks.
   for (fs::recursive_directory_iterator
            i(Twine(TestDirectory) + "/symlink", ec),
        e;
        i != e; i.increment(ec)) {
     ASSERT_NO_ERROR(ec);
 
     ErrorOr<fs::basic_file_status> status = i->status();
     if (status.getError() ==
         std::make_error_code(std::errc::no_such_file_or_directory)) {
       i.no_push();
       continue;
     }
 
     visited.push_back(path::filename(i->path()));
   }
-  std::sort(visited.begin(), visited.end());
+  llvm::sort(visited.begin(), visited.end());
   expected = {"b", "bb", "d", "da", "dd", "ddd", "ddd"};
   ASSERT_TRUE(visited.size() == expected.size());
   ASSERT_TRUE(std::equal(visited.begin(), visited.end(), expected.begin()));
   visited.clear();
 
   // This recursive directory iterator doesn't follow symlinks, so we don't need
   // to skip them.
   for (fs::recursive_directory_iterator
            i(Twine(TestDirectory) + "/symlink", ec, /*follow_symlinks=*/false),
        e;
        i != e; i.increment(ec)) {
     ASSERT_NO_ERROR(ec);
     visited.push_back(path::filename(i->path()));
   }
-  std::sort(visited.begin(), visited.end());
+  llvm::sort(visited.begin(), visited.end());
   expected = {"a", "b", "ba", "bb", "bc", "c", "d", "da", "dd", "ddd", "e"};
   ASSERT_TRUE(visited.size() == expected.size());
   ASSERT_TRUE(std::equal(visited.begin(), visited.end(), expected.begin()));
 
   ASSERT_NO_ERROR(fs::remove_directories(Twine(TestDirectory) + "/symlink"));
 }
 #endif
 

utils/unittest/googlemock/include/gmock/gmock-matchers.h

virtual void DescribeNegationTo(::std::ostream* os) const {
       matcher_.DescribeNegationTo(os);
     }
 
     virtual bool MatchAndExplain(LhsContainer lhs,
                                  MatchResultListener* listener) const {
       LhsStlContainerReference lhs_stl_container = LhsView::ConstReference(lhs);
       ::std::vector<LhsValue> sorted_container(lhs_stl_container.begin(),
                                                lhs_stl_container.end());
-      ::std::sort(
+      ::llvm::sort(
            sorted_container.begin(), sorted_container.end(), comparator_);
 
       if (!listener->IsInterested()) {
         // If the listener is not interested, we do not need to
         // construct the inner explanation.
         return matcher_.Matches(sorted_container);
       }