[clangd] NFC: Migrate to LLVM STLExtras API where possible

[kbobyrev]

Summary

This patch improves readability by migrating std::function(ForwardIt start, ForwardIt end, ...) to LLVM's STLExtras range-based equivalent llvm::function(RangeT &&Range, ...).

Similar change in Clang: D52576.

[kbobyrev]

Also, I'm not sure whether I should update Clang-Tidy and other tools in the scope of this patch. It makes sense to me, but I don't know whether the maintainers of these projects are happy with the change. WDYT?

[sammccall]

I think it's fine to update others too, this is a trivially-safe change and
a nice readability improvement.
No need to put everything in the same patch though.

[kbobyrev]

In D52650#1249556, @sammccall wrote:

I think it's fine to update others too, this is a trivially-safe change and
a nice readability improvement.
No need to put everything in the same patch though.

Great, thanks! I'll submit the patch once I'm home and I will make modifications in the other parts of clang-tools-extra.

Also, this making these transformations automatically might be a great idea for Clang-Tidy llvm-check (and a separate check with std::ranges later on).

[kbobyrev]

Rebase on top of HEAD.

clang-tools-extra/trunk/clangd/ClangdLSPServer.cpp

toLSPDiags(Diag, [&](clangd::Diagnostic Diag, llvm::ArrayRef<Fix> Fixes) {
         }
         LSPDiag["clangd_fixes"] = std::move(ClangdFixes);
       }
       if (DiagOpts.SendDiagnosticCategory && !Diag.category.empty())
         LSPDiag["category"] = Diag.category;
       DiagnosticsJSON.push_back(std::move(LSPDiag));
 
       auto &FixItsForDiagnostic = LocalFixIts[Diag];
-      std::copy(Fixes.begin(), Fixes.end(),
-                std::back_inserter(FixItsForDiagnostic));
+      llvm::copy(Fixes, std::back_inserter(FixItsForDiagnostic));
     });
   }
 
   // Cache FixIts
   {
     // FIXME(ibiryukov): should be deleted when documents are removed
     std::lock_guard<std::mutex> Lock(FixItsMutex);
     FixItsMap[File] = LocalFixIts;

clang-tools-extra/trunk/clangd/ClangdServer.cpp

llvm::Optional<Path> ClangdServer::switchSourceHeader(PathRef Path) {
   StringRef SourceExtensions[] = {".cpp", ".c", ".cc", ".cxx",
                                   ".c++", ".m", ".mm"};
   StringRef HeaderExtensions[] = {".h", ".hh", ".hpp", ".hxx", ".inc"};
 
   StringRef PathExt = llvm::sys::path::extension(Path);
 
   // Lookup in a list of known extensions.
   auto SourceIter =
-      std::find_if(std::begin(SourceExtensions), std::end(SourceExtensions),
-                   [&PathExt](PathRef SourceExt) {
-                     return SourceExt.equals_lower(PathExt);
-                   });
+      llvm::find_if(SourceExtensions, [&PathExt](PathRef SourceExt) {
   bool IsSource = SourceIter != std::end(SourceExtensions);
 
   auto HeaderIter =
-      std::find_if(std::begin(HeaderExtensions), std::end(HeaderExtensions),
-                   [&PathExt](PathRef HeaderExt) {
-                     return HeaderExt.equals_lower(PathExt);
-                   });
+      llvm::find_if(HeaderExtensions, [&PathExt](PathRef HeaderExt) {
 
   bool IsHeader = HeaderIter != std::end(HeaderExtensions);
 
   // We can only switch between the known extensions.
   if (!IsSource && !IsHeader)
     return llvm::None;
 
   // Array to lookup extensions for the switch. An opposite of where original

clang-tools-extra/trunk/clangd/CodeComplete.cpp

if (C.SemaResult) {
       // folder.
       if (Completion.Kind == CompletionItemKind::File &&
           Completion.Name.back() == '/')
         Completion.Kind = CompletionItemKind::Folder;
       for (const auto &FixIt : C.SemaResult->FixIts) {
         Completion.FixIts.push_back(
             toTextEdit(FixIt, ASTCtx.getSourceManager(), ASTCtx.getLangOpts()));
       }
-      std::sort(Completion.FixIts.begin(), Completion.FixIts.end(),
-                [](const TextEdit &X, const TextEdit &Y) {
-                  return std::tie(X.range.start.line, X.range.start.character) <
-                         std::tie(Y.range.start.line, Y.range.start.character);
-                });
+      llvm::sort(Completion.FixIts, [](const TextEdit &X, const TextEdit &Y) {
       Completion.Deprecated |=
           (C.SemaResult->Availability == CXAvailability_Deprecated);
     }
     if (C.IndexResult) {
       Completion.Origin |= C.IndexResult->Origin;
       if (Completion.Scope.empty())
         Completion.Scope = C.IndexResult->Scope;
       if (Completion.Kind == CompletionItemKind::Missing)
if (Index) {
         if (!S.Documentation.empty())
           FetchedDocs[S.ID] = S.Documentation;
       });
       log("SigHelp: requested docs for {0} symbols from the index, got {1} "
           "symbols with non-empty docs in the response",
           IndexRequest.IDs.size(), FetchedDocs.size());
     }
 
-    std::sort(
-        ScoredSignatures.begin(), ScoredSignatures.end(),
+    llvm::sort(
+        ScoredSignatures,
         [](const ScoredSignature &L, const ScoredSignature &R) {
           // Ordering follows:
           // - Less number of parameters is better.
           // - Function is better than FunctionType which is better than
           // Function Template.
           // - High score is better.
           // - Shorter signature is better.
           // - Alphebatically smaller is better.

 
 // Returns the most popular include header for \p Sym. If two headers are
 // equally popular, prefer the shorter one. Returns empty string if \p Sym has
 // no include header.
 llvm::SmallVector<StringRef, 1>
 getRankedIncludes(const Symbol &Sym) {
   auto Includes = Sym.IncludeHeaders;
   // Sort in descending order by reference count and header length.
-  std::sort(Includes.begin(), Includes.end(),
-            [](const Symbol::IncludeHeaderWithReferences &LHS,
+  llvm::sort(Includes, [](const Symbol::IncludeHeaderWithReferences &LHS,
                           const Symbol::IncludeHeaderWithReferences &RHS) {
-              if (LHS.References == RHS.References)
-                return LHS.IncludeHeader.size() < RHS.IncludeHeader.size();
-              return LHS.References > RHS.References;
-            });
   llvm::SmallVector<StringRef, 1> Headers;
   for (const auto &Include : Includes)
     Headers.push_back(Include.IncludeHeader);
   return Headers;
 }
 
 // Runs Sema-based (AST) and Index-based completion, returns merged results.
 //

clang-tools-extra/trunk/clangd/TUScheduler.cpp

llvm::Optional<std::unique_ptr<ParsedAST>> take(Key K) {
     // this miscompile.
     return llvm::Optional<std::unique_ptr<ParsedAST>>(std::move(V));
   }
 
 private:
   using KVPair = std::pair<Key, std::unique_ptr<ParsedAST>>;
 
   std::vector<KVPair>::iterator findByKey(Key K) {
-    return std::find_if(LRU.begin(), LRU.end(),
-                        [K](const KVPair &P) { return P.first == K; });
+    return llvm::find_if(LRU, [K](const KVPair &P) { return P.first == K; });
   }
 
   std::mutex Mut;
   unsigned MaxRetainedASTs;
   /// Items sorted in LRU order, i.e. first item is the most recently accessed
   /// one.
   std::vector<KVPair> LRU; /* GUARDED_BY(Mut) */
 };

clang-tools-extra/trunk/clangd/XRefs.cpp

std::vector<DeclInfo> getFoundDecls() const {
     std::vector<DeclInfo> Result;
     for (auto It : Decls) {
       Result.emplace_back();
       Result.back().D = It.first;
       Result.back().IsReferencedExplicitly = It.second;
     }
 
     // Sort results. Declarations being referenced explicitly come first.
-    std::sort(Result.begin(), Result.end(),
-              [](const DeclInfo &L, const DeclInfo &R) {
-                if (L.IsReferencedExplicitly != R.IsReferencedExplicitly)
-                  return L.IsReferencedExplicitly > R.IsReferencedExplicitly;
-                return L.D->getBeginLoc() < R.D->getBeginLoc();
-              });
+    llvm::sort(Result, [](const DeclInfo &L, const DeclInfo &R) {
     return Result;
   }
 
   std::vector<MacroDecl> takeMacroInfos() {
     // Don't keep the same Macro info multiple times.
-    std::sort(MacroInfos.begin(), MacroInfos.end(),
-              [](const MacroDecl &Left, const MacroDecl &Right) {
-                return Left.Info < Right.Info;
-              });
+    llvm::sort(MacroInfos, [](const MacroDecl &Left, const MacroDecl &Right) {
 
     auto Last = std::unique(MacroInfos.begin(), MacroInfos.end(),
                             [](const MacroDecl &Left, const MacroDecl &Right) {
                               return Left.Info == Right.Info;
                             });
     MacroInfos.erase(Last, MacroInfos.end());
     return std::move(MacroInfos);
   }

clang-tools-extra/trunk/clangd/index/CanonicalIncludes.cpp

 CanonicalIncludes::mapHeader(llvm::ArrayRef<std::string> Headers,
                              llvm::StringRef QualifiedName) const {
   assert(!Headers.empty());
   auto SE = SymbolMapping.find(QualifiedName);
   if (SE != SymbolMapping.end())
     return SE->second;
   // Find the first header such that the extension is not '.inc', and isn't a
   // recognized non-header file
-  auto I =
-      std::find_if(Headers.begin(), Headers.end(), [](llvm::StringRef Include) {
-        // Skip .inc file whose including header file should
-        // be #included instead.
-        return !Include.endswith(".inc");
-      });
+  auto I = llvm::find_if(Headers, [](llvm::StringRef Include) {
   if (I == Headers.end())
     return Headers[0]; // Fallback to the declaring header.
   StringRef Header = *I;
   // If Header is not expected be included (e.g. .cc file), we fall back to
   // the declaring header.
   StringRef Ext = llvm::sys::path::extension(Header).trim('.');
   // Include-able headers must have precompile type. Treat files with
   // non-recognized extenstions (TY_INVALID) as headers.

clang-tools-extra/trunk/clangd/index/FileIndex.cpp

for (const auto &RefSlab : RefSlabs)
         MergedRefs[Sym.first].append(Sym.second.begin(), Sym.second.end());
         Count += Sym.second.size();
       }
     RefsStorage.reserve(Count);
     AllRefs.reserve(MergedRefs.size());
     for (auto &Sym : MergedRefs) {
       auto &SymRefs = Sym.second;
       // Sorting isn't required, but yields more stable results over rebuilds.
-      std::sort(SymRefs.begin(), SymRefs.end());
-      std::copy(SymRefs.begin(), SymRefs.end(), back_inserter(RefsStorage));
+      llvm::sort(SymRefs);
+      llvm::copy(SymRefs, back_inserter(RefsStorage));
       AllRefs.try_emplace(
           Sym.first,
           ArrayRef<Ref>(&RefsStorage[RefsStorage.size() - SymRefs.size()],
                         SymRefs.size()));
     }
   }
 
   size_t StorageSize = RefsStorage.size() * sizeof(Ref);

clang-tools-extra/trunk/clangd/index/Index.cpp

float quality(const Symbol &S) {
   // This avoids a sharp gradient for tail symbols, and also neatly avoids the
   // question of whether 0 references means a bad symbol or missing data.
   if (S.References < 3)
     return 1;
   return std::log(S.References);
 }
 
 SymbolSlab::const_iterator SymbolSlab::find(const SymbolID &ID) const {
-  auto It = std::lower_bound(Symbols.begin(), Symbols.end(), ID,
-                             [](const Symbol &S, const SymbolID &I) {
-                               return S.ID < I;
-                             });
+  auto It = llvm::lower_bound(
+      Symbols, ID, [](const Symbol &S, const SymbolID &I) { return S.ID < I; });
   if (It != Symbols.end() && It->ID == ID)
     return It;
   return Symbols.end();
 }
 
 // Copy the underlying data of the symbol into the owned arena.
 static void own(Symbol &S, llvm::UniqueStringSaver &Strings) {
   visitStrings(S, [&](StringRef &V) { V = Strings.save(V); });
 }
 
 void SymbolSlab::Builder::insert(const Symbol &S) {
   auto R = SymbolIndex.try_emplace(S.ID, Symbols.size());
   if (R.second) {
     Symbols.push_back(S);
     own(Symbols.back(), UniqueStrings);
   } else {
     auto &Copy = Symbols[R.first->second] = S;
     own(Copy, UniqueStrings);
   }
 }
 
 SymbolSlab SymbolSlab::Builder::build() && {
   Symbols = {Symbols.begin(), Symbols.end()}; // Force shrink-to-fit.
   // Sort symbols so the slab can binary search over them.
-  std::sort(Symbols.begin(), Symbols.end(),
+  llvm::sort(Symbols,
              [](const Symbol &L, const Symbol &R) { return L.ID < R.ID; });
   // We may have unused strings from overwritten symbols. Build a new arena.
   BumpPtrAllocator NewArena;
   llvm::UniqueStringSaver Strings(NewArena);
   for (auto &S : Symbols)
     own(S, Strings);
   return SymbolSlab(std::move(NewArena), std::move(Symbols));
 }
 

 
 RefSlab RefSlab::Builder::build() && {
   // We can reuse the arena, as it only has unique strings and we need them all.
   // Reallocate refs on the arena to reduce waste and indirections when reading.
   std::vector<std::pair<SymbolID, ArrayRef<Ref>>> Result;
   Result.reserve(Refs.size());
   for (auto &Sym : Refs) {
     auto &SymRefs = Sym.second;
-    std::sort(SymRefs.begin(), SymRefs.end());
-    // TODO: do we really need to dedup?
+    llvm::sort(SymRefs);
+    // FIXME: do we really need to dedup?
     SymRefs.erase(std::unique(SymRefs.begin(), SymRefs.end()), SymRefs.end());
 
     auto *Array = Arena.Allocate<Ref>(SymRefs.size());
     std::uninitialized_copy(SymRefs.begin(), SymRefs.end(), Array);
     Result.emplace_back(Sym.first, ArrayRef<Ref>(Array, SymRefs.size()));
   }
   return RefSlab(std::move(Result), std::move(Arena));
 }

clang-tools-extra/trunk/clangd/index/Serialization.cpp

StringTableOut() {
     // Table size zero is reserved to indicate no compression.
     Unique.insert("");
   }
   // Add a string to the table. Overwrites S if an identical string exists.
   void intern(StringRef &S) { S = *Unique.insert(S).first; };
   // Finalize the table and write it to OS. No more strings may be added.
   void finalize(raw_ostream &OS) {
     Sorted = {Unique.begin(), Unique.end()};
-    std::sort(Sorted.begin(), Sorted.end());
+    llvm::sort(Sorted);
     for (unsigned I = 0; I < Sorted.size(); ++I)
       Index.try_emplace({Sorted[I].data(), Sorted[I].size()}, I);
 
     std::string RawTable;
     for (StringRef S : Sorted) {
       RawTable.append(S);
       RawTable.push_back(0);
     }

clang-tools-extra/trunk/clangd/index/SymbolCollector.cpp

bool isPrivateProtoDecl(const NamedDecl &ND) {
   // that shouldn't be used (Message_Nested). Ignore them completely.
   // The nested entities are dangling type aliases, we may want to reconsider
   // including them in the future.
   // For enum constants, SOME_ENUM_CONSTANT is not private and should be
   // indexed. Outer_INNER is private. This heuristic relies on naming style, it
   // will include OUTER_INNER and exclude some_enum_constant.
   // FIXME: the heuristic relies on naming style (i.e. no underscore in
   // user-defined names) and can be improved.
-  return (ND.getKind() != Decl::EnumConstant) ||
-         std::any_of(Name.begin(), Name.end(), islower);
+  return (ND.getKind() != Decl::EnumConstant) || llvm::any_of(Name, islower);
 }
 
 // We only collect #include paths for symbols that are suitable for global code
 // completion, except for namespaces since #include path for a namespace is hard
 // to define.
 bool shouldCollectIncludePath(index::SymbolKind Kind) {
   using SK = index::SymbolKind;
   switch (Kind) {

clang-tools-extra/trunk/clangd/index/dex/Dex.cpp

void Dex::buildIndex() {
   for (size_t I = 0; I < Symbols.size(); ++I) {
     const Symbol *Sym = Symbols[I];
     LookupTable[Sym->ID] = Sym;
     ScoredSymbols[I] = {quality(*Sym), Sym};
   }
 
   // Symbols are sorted by symbol qualities so that items in the posting lists
   // are stored in the descending order of symbol quality.
-  std::sort(begin(ScoredSymbols), end(ScoredSymbols),
-            std::greater<std::pair<float, const Symbol *>>());
+  llvm::sort(ScoredSymbols, std::greater<std::pair<float, const Symbol *>>());
 
   // SymbolQuality was empty up until now.
   SymbolQuality.resize(Symbols.size());
   // Populate internal storage using Symbol + Score pairs.
   for (size_t I = 0; I < ScoredSymbols.size(); ++I) {
     SymbolQuality[I] = ScoredSymbols[I].first;
     Symbols[I] = ScoredSymbols[I].second;
   }

clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp

explicit AndIterator(std::vector<std::unique_ptr<Iterator>> AllChildren)
     sync();
     // When children are sorted by the estimateSize(), sync() calls are more
     // effective. Each sync() starts with the first child and makes sure all
     // children point to the same element. If any child is "above" the previous
     // ones, the algorithm resets and and advances the children to the next
     // highest element starting from the front. When child iterators in the
     // beginning have smaller estimated size, the sync() will have less restarts
     // and become more effective.
-    std::sort(begin(Children), end(Children),
-              [](const std::unique_ptr<Iterator> &LHS,
+    llvm::sort(Children, [](const std::unique_ptr<Iterator> &LHS,
                             const std::unique_ptr<Iterator> &RHS) {
-                return LHS->estimateSize() < RHS->estimateSize();
-              });
   }
 
   bool reachedEnd() const override { return ReachedEnd; }
 
   /// Advances all children to the next common item.
   void advance() override {
     assert(!reachedEnd() && "AND iterator can't advance() at the end.");
     Children.front()->advance();

llvm/trunk/include/llvm/ADT/STLExtras.h

 
 /// Provide wrappers to std::lower_bound which take ranges instead of having to
 /// pass begin/end explicitly.
 template <typename R, typename ForwardIt>
 auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
   return std::lower_bound(adl_begin(Range), adl_end(Range), I);
 }
 
+template <typename R, typename ForwardIt, typename Compare>
+auto lower_bound(R &&Range, ForwardIt I, Compare C)
+    -> decltype(adl_begin(Range)) {
+  return std::lower_bound(adl_begin(Range), adl_end(Range), I, C);
+}
+
 /// Provide wrappers to std::upper_bound which take ranges instead of having to
 /// pass begin/end explicitly.
 template <typename R, typename ForwardIt>
 auto upper_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
   return std::upper_bound(adl_begin(Range), adl_end(Range), I);
 }
 
 template <typename R, typename ForwardIt, typename Compare>