[clangd] NFC: Use TopN instead of std::priority_queue

[kbobyrev]

Summary

Quality.cpp defines a structure for convenient storage of Top N items, it should be used instead of the std::priority_queue with slightly obscure semantics.

This patch does not affect functionality.

[sammccall]

Thanks for cleaning this up!

I believe this will result in the results from MemIndex being returned in best -> worst order, rather than worst -> best.
The contract says callers shouldn't rely on the order so it should still be NFC overall.
It's likely to make your index explorer more useful though :-)

clang-tools-extra/clangd/index/MemIndex.cpp

42 ↗

(On Diff #163996)

this looks more like generic documentation for Top::push.
I'd suggest instead adding a line comment when it's true:
More = true; // We discarded something.

[kbobyrev]

In D51676#1225215, @sammccall wrote:

Thanks for cleaning this up!

I believe this will result in the results from MemIndex being returned in best -> worst order, rather than worst -> best.
The contract says callers shouldn't rely on the order so it should still be NFC overall.
It's likely to make your index explorer more useful though :-)

Right. The index explorer would probably still have to re-order elements (so that it actually doesn't rely on implementation details and implicit assumptions). For the completion part, IIUC the complete ranking would rearrange items anyway.

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

 //===--- MemIndex.cpp - Dynamic in-memory symbol index. ----------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "MemIndex.h"
 #include "../FuzzyMatch.h"
 #include "../Logger.h"
-#include <queue>
+#include "../Quality.h"
 
 namespace clang {
 namespace clangd {
 
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs) {
   auto Data = std::make_pair(std::move(Slab), std::move(Refs));
   return llvm::make_unique<MemIndex>(Data.first, Data.second, std::move(Data));
 }
 
 bool MemIndex::fuzzyFind(
     const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
 
-  std::priority_queue<std::pair<float, const Symbol *>> Top;
+  TopN<std::pair<float, const Symbol *>> Top(Req.MaxCandidateCount);
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
   for (const auto Pair : Index) {
     const Symbol *Sym = Pair.second;
 
     // Exact match against all possible scopes.
     if (!Req.Scopes.empty() && !llvm::is_contained(Req.Scopes, Sym->Scope))
       continue;
     if (Req.RestrictForCodeCompletion && !Sym->IsIndexedForCodeCompletion)
       continue;
 
-    if (auto Score = Filter.match(Sym->Name)) {
-      Top.emplace(-*Score * quality(*Sym), Sym);
-      if (Top.size() > Req.MaxCandidateCount) {
-        More = true;
-        Top.pop();
-      }
-    }
-  }
-  for (; !Top.empty(); Top.pop())
-    Callback(*Top.top().second);
+    if (auto Score = Filter.match(Sym->Name))
+      if (Top.push({*Score * quality(*Sym), Sym}))
+        More = true; // An element with smallest score was discarded.
+  for (const auto &Item : std::move(Top).items())
+    Callback(*Item.second);
   return More;
 }
 
 void MemIndex::lookup(const LookupRequest &Req,
                       llvm::function_ref<void(const Symbol &)> Callback) const {
   for (const auto &ID : Req.IDs) {
     auto I = Index.find(ID);
     if (I != Index.end())