[include-fixer] Rank symbols based on the number of occurrences we found while merging.

[bkramer]

Summary

This sorts based on the popularity of the header, not the symbol. If
there are mutliple matching symbols in one header we take the maximum
popularity for that header and deduplicate. If we know nothing we sort
lexicographically based on the header path.

[djasper]

include-fixer/SymbolIndexManager.cpp

25 ↗

(On Diff #59062)

Maybe use a DenseHashMap?

include-fixer/tool/ClangIncludeFixer.cpp

101 ↗

(On Diff #59062)

Can you please write a regular for loop with index instead?

105 ↗

(On Diff #59062)

Add a comment that you are assigning fake occurrences to keep the existing test logic (with the first include being the most preferable).

clang-tools-extra/trunk/include-fixer/SymbolIndexManager.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "include-fixer"
 
 namespace clang {
 namespace include_fixer {
 
+using clang::find_all_symbols::SymbolInfo;
+
+/// Sorts and uniques SymbolInfos based on the popularity info in SymbolInfo.
+static void rankByPopularity(std::vector<SymbolInfo> &Symbols) {
+  // First collect occurrences per header file.
+  std::map<llvm::StringRef, unsigned> HeaderPopularity;
+  for (const SymbolInfo &Symbol : Symbols) {
+    unsigned &Popularity = HeaderPopularity[Symbol.getFilePath()];
+    Popularity = std::max(Popularity, Symbol.getNumOccurrences());
+  }
+
+  // Sort by the gathered popularities. Use file name as a tie breaker so we can
+  // deduplicate.
+  std::sort(Symbols.begin(), Symbols.end(),
+            [&](const SymbolInfo &A, const SymbolInfo &B) {
+              auto APop = HeaderPopularity[A.getFilePath()];
+              auto BPop = HeaderPopularity[B.getFilePath()];
+              if (APop != BPop)
+                return APop > BPop;
+              return A.getFilePath() < B.getFilePath();
+            });
+
+  // Deduplicate based on the file name. They will have the same popularity and
+  // we don't want to suggest the same header twice.
+  Symbols.erase(std::unique(Symbols.begin(), Symbols.end(),
+                            [](const SymbolInfo &A, const SymbolInfo &B) {
+                              return A.getFilePath() == B.getFilePath();
+                            }),
+                Symbols.end());
+}
+
 std::vector<std::string>
 SymbolIndexManager::search(llvm::StringRef Identifier) const {
   // The identifier may be fully qualified, so split it and get all the context
   // names.
   llvm::SmallVector<llvm::StringRef, 8> Names;
   Identifier.split(Names, "::");
 
   bool IsFullyQualified = false;
while (Results.empty() && !Names.empty()) {
     for (const auto &DB : SymbolIndices) {
       auto Res = DB->search(Names.back().str());
       Symbols.insert(Symbols.end(), Res.begin(), Res.end());
     }
 
     DEBUG(llvm::dbgs() << "Searching " << Names.back() << "... got "
                        << Symbols.size() << " results...\n");
 
+    rankByPopularity(Symbols);
+
     for (const auto &Symbol : Symbols) {
       // Match the identifier name without qualifier.
       if (Symbol.getName() == Names.back()) {
         bool IsMatched = true;
         auto SymbolContext = Symbol.getContexts().begin();
         auto IdentiferContext = Names.rbegin() + 1; // Skip identifier name.
         // Match the remaining context names.
         while (IdentiferContext != Names.rend() &&

clang-tools-extra/trunk/include-fixer/tool/ClangIncludeFixer.cpp

case fixed: {
     SmallVector<StringRef, 4> SemicolonSplits;
     StringRef(Input).split(SemicolonSplits, ";");
     std::vector<find_all_symbols::SymbolInfo> Symbols;
     for (StringRef Pair : SemicolonSplits) {
       auto Split = Pair.split('=');
       std::vector<std::string> Headers;
       SmallVector<StringRef, 4> CommaSplits;
       Split.second.split(CommaSplits, ",");
-      for (StringRef Header : CommaSplits)
+      for (size_t I = 0, E = CommaSplits.size(); I != E; ++I)
         Symbols.push_back(find_all_symbols::SymbolInfo(
             Split.first.trim(),
-            find_all_symbols::SymbolInfo::SymbolKind::Unknown, Header.trim(), 1,
-            {}));
+            find_all_symbols::SymbolInfo::SymbolKind::Unknown,
+            CommaSplits[I].trim(), 1, {}, /*NumOccurrences=*/E - I));
     }
     SymbolIndexMgr->addSymbolIndex(
         llvm::make_unique<include_fixer::InMemorySymbolIndex>(Symbols));
     break;
   }
   case yaml: {
     llvm::ErrorOr<std::unique_ptr<include_fixer::YamlSymbolIndex>> DB(nullptr);
     if (!Input.empty()) {

clang-tools-extra/trunk/test/include-fixer/Inputs/fake_yaml_db.yaml

- ContextType:     Namespace
     ContextName:     a
   - ContextType:     Namespace
     ContextName:     b
 FilePath:        ../include/bar.h
 LineNumber:      1
 Type:            Class
 NumOccurrences:  1
 ...
+Name:           bar
+Contexts:
+  - ContextType:     Namespace
+    ContextName:     a
+  - ContextType:     Namespace
+    ContextName:     b
+FilePath:        ../include/bar.h
+LineNumber:      2
+Type:            Class
+NumOccurrences:  3
+...
+Name:           bar
+Contexts:
+  - ContextType:     Namespace
+    ContextName:     a
+  - ContextType:     Namespace
+    ContextName:     b
+FilePath:        ../include/zbar.h
+LineNumber:      1
+Type:            Class
+NumOccurrences:  3

clang-tools-extra/trunk/test/include-fixer/ranking.cpp

+// RUN: clang-include-fixer -db=yaml -input=%S/Inputs/fake_yaml_db.yaml -output-headers %s -- | FileCheck %s -implicit-check-not=.h
+
+// CHECK: "../include/bar.h"
+// CHECK-NEXT: "../include/zbar.h"
+
+bar b;