Change std::sort to llvm::sort to detect non-determinism.

LLVM added wrappers to std::sort (r327219) that randomly shuffle the
container before sorting. The goal is to uncover non-determinism due to
undefined sorting order of objects having the same key.

This can be enabled with -DLLVM_ENABLE_EXPENSIVE_CHECKS=ON.

17 files changed, 43 insertions, 44 deletions

diff --git a/lldb/include/lldb/Core/UniqueCStringMap.h b/lldb/include/lldb/Core/UniqueCStringMap.h
index 58ff258badb..cfb84b4c216 100644
--- a/lldb/include/lldb/Core/UniqueCStringMap.h
+++ b/lldb/include/lldb/Core/UniqueCStringMap.h
@@ -217,7 +217,7 @@ public:
   // }
   // my_map.Sort();
   //------------------------------------------------------------------
-  void Sort() { std::sort(m_map.begin(), m_map.end()); }
+  void Sort() { llvm::sort(m_map.begin(), m_map.end()); }
 
   //------------------------------------------------------------------
   // Since we are using a vector to contain our items it will always double its
diff --git a/lldb/source/Breakpoint/BreakpointResolver.cpp b/lldb/source/Breakpoint/BreakpointResolver.cpp
index a2a655fe4b5..0a1eeed2895 100644
--- a/lldb/source/Breakpoint/BreakpointResolver.cpp
+++ b/lldb/source/Breakpoint/BreakpointResolver.cpp
@@ -238,10 +238,10 @@ void BreakpointResolver::SetSCMatchesByLine(SearchFilter &filter,
           worklist_begin, worklist_end,
           [&](const SymbolContext &sc) { return SourceLoc(sc) < requested; });
       // Sort the remaining entries by (line, column).
-      std::sort(worklist_begin, worklist_end,
-                [](const SymbolContext &a, const SymbolContext &b) {
-                  return SourceLoc(a) < SourceLoc(b);
-                });
+      llvm::sort(worklist_begin, worklist_end,
+                 [](const SymbolContext &a, const SymbolContext &b) {
+                   return SourceLoc(a) < SourceLoc(b);
+                 });
 
       // Filter out all locations with a source location after the closest match.
       if (worklist_begin != worklist_end)
@@ -261,11 +261,11 @@ void BreakpointResolver::SetSCMatchesByLine(SearchFilter &filter,
     }
 
     // Sort by file address.
-    std::sort(worklist_begin, worklist_end,
-              [](const SymbolContext &a, const SymbolContext &b) {
-                return a.line_entry.range.GetBaseAddress().GetFileAddress() <
-                       b.line_entry.range.GetBaseAddress().GetFileAddress();
-              });
+    llvm::sort(worklist_begin, worklist_end,
+               [](const SymbolContext &a, const SymbolContext &b) {
+                 return a.line_entry.range.GetBaseAddress().GetFileAddress() <
+                        b.line_entry.range.GetBaseAddress().GetFileAddress();
+               });
 
     // Go through and see if there are line table entries that are
     // contiguous, and if so keep only the first of the contiguous range.
diff --git a/lldb/source/Commands/CommandObjectType.cpp b/lldb/source/Commands/CommandObjectType.cpp
index 9dd25d127f4..815e563197b 100644
--- a/lldb/source/Commands/CommandObjectType.cpp
+++ b/lldb/source/Commands/CommandObjectType.cpp
@@ -2907,7 +2907,7 @@ public:
     if (StackFrame *frame = m_exe_ctx.GetFramePtr()) {
       guessed_language = GuessLanguage(frame);
       if (guessed_language != eLanguageTypeUnknown) {
-        std::sort(
+        llvm::sort(
             languages.begin(), languages.end(),
             [guessed_language](Language *lang1, Language *lang2) -> bool {
               if (!lang1 || !lang2)
diff --git a/lldb/source/Interpreter/OptionValueArray.cpp b/lldb/source/Interpreter/OptionValueArray.cpp
index e405c9500b8..d755fa2fddb 100644
--- a/lldb/source/Interpreter/OptionValueArray.cpp
+++ b/lldb/source/Interpreter/OptionValueArray.cpp
@@ -221,7 +221,7 @@ Status OptionValueArray::SetArgs(const Args &args, VarSetOperationType op) {
         if (num_remove_indexes) {
           // Sort and then erase in reverse so indexes are always valid
           if (num_remove_indexes > 1) {
-            std::sort(remove_indexes.begin(), remove_indexes.end());
+            llvm::sort(remove_indexes.begin(), remove_indexes.end());
             for (std::vector<int>::const_reverse_iterator
                      pos = remove_indexes.rbegin(),
                      end = remove_indexes.rend();
diff --git a/lldb/source/Interpreter/OptionValueFileSpecLIst.cpp b/lldb/source/Interpreter/OptionValueFileSpecLIst.cpp
index 90bb89855ef..fd78bba94fe 100644
--- a/lldb/source/Interpreter/OptionValueFileSpecLIst.cpp
+++ b/lldb/source/Interpreter/OptionValueFileSpecLIst.cpp
@@ -140,7 +140,7 @@ Status OptionValueFileSpecList::SetValueFromString(llvm::StringRef value,
         size_t num_remove_indexes = remove_indexes.size();
         if (num_remove_indexes) {
           // Sort and then erase in reverse so indexes are always valid
-          std::sort(remove_indexes.begin(), remove_indexes.end());
+          llvm::sort(remove_indexes.begin(), remove_indexes.end());
           for (size_t j = num_remove_indexes - 1; j < num_remove_indexes; ++j) {
             m_current_value.Remove(j);
           }
diff --git a/lldb/source/Interpreter/OptionValuePathMappings.cpp b/lldb/source/Interpreter/OptionValuePathMappings.cpp
index a00799bc3fe..11ec739c5bb 100644
--- a/lldb/source/Interpreter/OptionValuePathMappings.cpp
+++ b/lldb/source/Interpreter/OptionValuePathMappings.cpp
@@ -177,7 +177,7 @@ Status OptionValuePathMappings::SetValueFromString(llvm::StringRef value,
         size_t num_remove_indexes = remove_indexes.size();
         if (num_remove_indexes) {
           // Sort and then erase in reverse so indexes are always valid
-          std::sort(remove_indexes.begin(), remove_indexes.end());
+          llvm::sort(remove_indexes.begin(), remove_indexes.end());
           for (size_t j = num_remove_indexes - 1; j < num_remove_indexes; ++j) {
             m_path_mappings.Remove(j, m_notify_changes);
           }
diff --git a/lldb/source/Plugins/DynamicLoader/Hexagon-DYLD/DynamicLoaderHexagonDYLD.cpp b/lldb/source/Plugins/DynamicLoader/Hexagon-DYLD/DynamicLoaderHexagonDYLD.cpp
index 1916183f061..81eab8fdd97 100644
--- a/lldb/source/Plugins/DynamicLoader/Hexagon-DYLD/DynamicLoaderHexagonDYLD.cpp
+++ b/lldb/source/Plugins/DynamicLoader/Hexagon-DYLD/DynamicLoaderHexagonDYLD.cpp
@@ -453,7 +453,7 @@ DynamicLoaderHexagonDYLD::GetStepThroughTrampolinePlan(Thread &thread,
     AddressVector::iterator start = addrs.begin();
     AddressVector::iterator end = addrs.end();
 
-    std::sort(start, end);
+    llvm::sort(start, end);
     addrs.erase(std::unique(start, end), end);
     thread_plan_sp.reset(new ThreadPlanRunToAddress(thread, addrs, stop));
   }
diff --git a/lldb/source/Plugins/DynamicLoader/POSIX-DYLD/DynamicLoaderPOSIXDYLD.cpp b/lldb/source/Plugins/DynamicLoader/POSIX-DYLD/DynamicLoaderPOSIXDYLD.cpp
index 660bba65d8b..6774b4fd129 100644
--- a/lldb/source/Plugins/DynamicLoader/POSIX-DYLD/DynamicLoaderPOSIXDYLD.cpp
+++ b/lldb/source/Plugins/DynamicLoader/POSIX-DYLD/DynamicLoaderPOSIXDYLD.cpp
@@ -496,7 +496,7 @@ DynamicLoaderPOSIXDYLD::GetStepThroughTrampolinePlan(Thread &thread,
     AddressVector::iterator start = addrs.begin();
     AddressVector::iterator end = addrs.end();
 
-    std::sort(start, end);
+    llvm::sort(start, end);
     addrs.erase(std::unique(start, end), end);
     thread_plan_sp.reset(new ThreadPlanRunToAddress(thread, addrs, stop));
   }
diff --git a/lldb/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp b/lldb/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp
index f03c7147569..59d7fe01c24 100644
--- a/lldb/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp
+++ b/lldb/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp
@@ -1653,10 +1653,10 @@ static bool ImportOffsetMap(llvm::DenseMap<const D *, O> &destination_map,
   std::vector<PairType> sorted_items;
   sorted_items.reserve(source_map.size());
   sorted_items.assign(source_map.begin(), source_map.end());
-  std::sort(sorted_items.begin(), sorted_items.end(),
-            [](const PairType &lhs, const PairType &rhs) {
-              return lhs.second < rhs.second;
-            });
+  llvm::sort(sorted_items.begin(), sorted_items.end(),
+             [](const PairType &lhs, const PairType &rhs) {
+               return lhs.second < rhs.second;
+             });
 
   for (const auto &item : sorted_items) {
     DeclFromUser<D> user_decl(const_cast<D *>(item.first));
diff --git a/lldb/source/Plugins/Process/Utility/DynamicRegisterInfo.cpp b/lldb/source/Plugins/Process/Utility/DynamicRegisterInfo.cpp
index 5f34e9915ed..dcbf474fa55 100644
--- a/lldb/source/Plugins/Process/Utility/DynamicRegisterInfo.cpp
+++ b/lldb/source/Plugins/Process/Utility/DynamicRegisterInfo.cpp
@@ -464,7 +464,7 @@ void DynamicRegisterInfo::Finalize(const ArchSpec &arch) {
                                  end = m_value_regs_map.end();
        pos != end; ++pos) {
     if (pos->second.size() > 1) {
-      std::sort(pos->second.begin(), pos->second.end());
+      llvm::sort(pos->second.begin(), pos->second.end());
       reg_num_collection::iterator unique_end =
           std::unique(pos->second.begin(), pos->second.end());
       if (unique_end != pos->second.end())
@@ -514,7 +514,7 @@ void DynamicRegisterInfo::Finalize(const ArchSpec &arch) {
                                  end = m_invalidate_regs_map.end();
        pos != end; ++pos) {
     if (pos->second.size() > 1) {
-      std::sort(pos->second.begin(), pos->second.end());
+      llvm::sort(pos->second.begin(), pos->second.end());
       reg_num_collection::iterator unique_end =
           std::unique(pos->second.begin(), pos->second.end());
       if (unique_end != pos->second.end())
diff --git a/lldb/source/Plugins/Process/minidump/MinidumpParser.cpp b/lldb/source/Plugins/Process/minidump/MinidumpParser.cpp
index 5372d32a0df..d4053ca70b9 100644
--- a/lldb/source/Plugins/Process/minidump/MinidumpParser.cpp
+++ b/lldb/source/Plugins/Process/minidump/MinidumpParser.cpp
@@ -559,7 +559,7 @@ const MemoryRegionInfos &MinidumpParser::GetMemoryRegions() {
       if (!CreateRegionsCacheFromMemoryInfoList(*this, m_regions))
         if (!CreateRegionsCacheFromMemoryList(*this, m_regions))
           CreateRegionsCacheFromMemory64List(*this, m_regions);
-    std::sort(m_regions.begin(), m_regions.end());
+    llvm::sort(m_regions.begin(), m_regions.end());
   }
   return m_regions;
 }
@@ -646,10 +646,10 @@ Status MinidumpParser::Initialize() {
   }
 
   // Sort the file map ranges by start offset
-  std::sort(minidump_map.begin(), minidump_map.end(),
-            [](const FileRange &a, const FileRange &b) {
-              return a.offset < b.offset;
-            });
+  llvm::sort(minidump_map.begin(), minidump_map.end(),
+             [](const FileRange &a, const FileRange &b) {
+               return a.offset < b.offset;
+             });
 
   // Check for overlapping streams/data structures
   for (size_t i = 1; i < minidump_map.size(); ++i) {
diff --git a/lldb/source/Symbol/ArmUnwindInfo.cpp b/lldb/source/Symbol/ArmUnwindInfo.cpp
index 6dcad62f2f9..08f28073be2 100644
--- a/lldb/source/Symbol/ArmUnwindInfo.cpp
+++ b/lldb/source/Symbol/ArmUnwindInfo.cpp
@@ -66,7 +66,7 @@ ArmUnwindInfo::ArmUnwindInfo(ObjectFile &objfile, SectionSP &arm_exidx,
 
   // Sort the entries in the exidx section. The entries should be sorted inside
   // the section but some old compiler isn't sorted them.
-  std::sort(m_exidx_entries.begin(), m_exidx_entries.end());
+  llvm::sort(m_exidx_entries.begin(), m_exidx_entries.end());
 }
 
 ArmUnwindInfo::~ArmUnwindInfo() {}
diff --git a/lldb/source/Symbol/CompileUnit.cpp b/lldb/source/Symbol/CompileUnit.cpp
index 318afcba633..63317ae99e8 100644
--- a/lldb/source/Symbol/CompileUnit.cpp
+++ b/lldb/source/Symbol/CompileUnit.cpp
@@ -72,10 +72,10 @@ void CompileUnit::ForeachFunction(
   sorted_functions.reserve(m_functions_by_uid.size());
   for (auto &p : m_functions_by_uid)
     sorted_functions.push_back(p.second);
-  std::sort(sorted_functions.begin(), sorted_functions.end(),
-            [](const lldb::FunctionSP &a, const lldb::FunctionSP &b) {
-              return a->GetID() < b->GetID();
-            });
+  llvm::sort(sorted_functions.begin(), sorted_functions.end(),
+             [](const lldb::FunctionSP &a, const lldb::FunctionSP &b) {
+               return a->GetID() < b->GetID();
+             });
 
   for (auto &f : sorted_functions)
     if (lambda(f))
diff --git a/lldb/source/Symbol/Function.cpp b/lldb/source/Symbol/Function.cpp
index dfc0ddb8f40..8b2cfb43bc0 100644
--- a/lldb/source/Symbol/Function.cpp
+++ b/lldb/source/Symbol/Function.cpp
@@ -267,11 +267,11 @@ llvm::MutableArrayRef<CallEdge> Function::GetCallEdges() {
   m_call_edges = sym_file->ParseCallEdgesInFunction(GetID());
 
   // Sort the call edges to speed up return_pc lookups.
-  std::sort(m_call_edges.begin(), m_call_edges.end(),
-            [](const CallEdge &LHS, const CallEdge &RHS) {
-              return LHS.GetUnresolvedReturnPCAddress() <
-                     RHS.GetUnresolvedReturnPCAddress();
-            });
+  llvm::sort(m_call_edges.begin(), m_call_edges.end(),
+             [](const CallEdge &LHS, const CallEdge &RHS) {
+               return LHS.GetUnresolvedReturnPCAddress() <
+                      RHS.GetUnresolvedReturnPCAddress();
+             });
 
   return m_call_edges;
 }
diff --git a/lldb/source/Symbol/Symtab.cpp b/lldb/source/Symbol/Symtab.cpp
index 8131cd5f5b1..2472580a41d 100644
--- a/lldb/source/Symbol/Symtab.cpp
+++ b/lldb/source/Symbol/Symtab.cpp
@@ -610,10 +610,9 @@ void Symtab::SortSymbolIndexesByValue(std::vector<uint32_t> &indexes,
     return;
 
   // Sort the indexes in place using std::stable_sort.
-  // NOTE: The use of std::stable_sort instead of std::sort here is strictly for
-  // performance,
-  // not correctness.  The indexes vector tends to be "close" to sorted, which
-  // the stable sort handles better.
+  // NOTE: The use of std::stable_sort instead of llvm::sort here is strictly
+  // for performance, not correctness.  The indexes vector tends to be "close"
+  // to sorted, which the stable sort handles better.
 
   std::vector<lldb::addr_t> addr_cache(m_symbols.size(), LLDB_INVALID_ADDRESS);
 
@@ -1132,7 +1131,7 @@ size_t Symtab::FindFunctionSymbols(const ConstString &name,
   }
 
   if (!symbol_indexes.empty()) {
-    std::sort(symbol_indexes.begin(), symbol_indexes.end());
+    llvm::sort(symbol_indexes.begin(), symbol_indexes.end());
     symbol_indexes.erase(
         std::unique(symbol_indexes.begin(), symbol_indexes.end()),
         symbol_indexes.end());
diff --git a/lldb/source/Target/Target.cpp b/lldb/source/Target/Target.cpp
index 3ba5fc0a728..437f92abdab 100644
--- a/lldb/source/Target/Target.cpp
+++ b/lldb/source/Target/Target.cpp
@@ -764,7 +764,7 @@ void Target::GetBreakpointNames(std::vector<std::string> &names)
   for (auto bp_name : m_breakpoint_names) {
     names.push_back(bp_name.first.AsCString());
   }
-  std::sort(names.begin(), names.end());
+  llvm::sort(names.begin(), names.end());
 }
 
 bool Target::ProcessIsValid() {
diff --git a/lldb/source/Utility/Timer.cpp b/lldb/source/Utility/Timer.cpp
index 170d17a1fc9..c56ac2192b3 100644
--- a/lldb/source/Utility/Timer.cpp
+++ b/lldb/source/Utility/Timer.cpp
@@ -125,7 +125,7 @@ void Timer::DumpCategoryTimes(Stream *s) {
     return; // Later code will break without any elements.
 
   // Sort by time
-  std::sort(sorted.begin(), sorted.end(), CategoryMapIteratorSortCriterion);
+  llvm::sort(sorted.begin(), sorted.end(), CategoryMapIteratorSortCriterion);
 
   for (const auto &timer : sorted)
     s->Printf("%.9f sec for %s\n", timer.second / 1000000000., timer.first);