| 1 |
//===-- SymbolIndexManager.cpp - Managing multiple SymbolIndices-*- C++ -*-===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
|
| 9 |
#include "SymbolIndexManager.h" |
| 10 |
|
| 11 |
#include <cmath> |
| 12 |
|
| 13 |
#include "find-all-symbols/SymbolInfo.h" |
| 14 |
#include "llvm/ADT/STLExtras.h" |
| 15 |
#include "llvm/ADT/SmallVector.h" |
| 16 |
#include "llvm/ADT/StringMap.h" |
| 17 |
#include "llvm/Support/Debug.h" |
| 18 |
#include "llvm/Support/Path.h" |
| 19 |
|
| 20 |
#define DEBUG_TYPE "clang-include-fixer" |
| 21 |
|
| 22 |
namespace clang { |
| 23 |
namespace include_fixer { |
| 24 |
|
| 25 |
using find_all_symbols::SymbolInfo; |
| 26 |
using find_all_symbols::SymbolAndSignals; |
| 27 |
|
| 28 |
// Calculate a score based on whether we think the given header is closely |
| 29 |
// related to the given source file. |
| 30 |
static double similarityScore(llvm::StringRef FileName, |
| 31 |
llvm::StringRef Header) { |
| 32 |
// Compute the maximum number of common path segments between Header and |
| 33 |
// a suffix of FileName. |
| 34 |
// We do not do a full longest common substring computation, as Header |
| 35 |
// specifies the path we would directly #include, so we assume it is rooted |
| 36 |
// relatively to a subproject of the repository. |
| 37 |
int MaxSegments = 1; |
| 38 |
for (auto FileI = llvm::sys::path::begin(FileName), |
| 39 |
FileE = llvm::sys::path::end(FileName); |
| 40 |
FileI != FileE; ++FileI) { |
| 41 |
int Segments = 0; |
| 42 |
for (auto HeaderI = llvm::sys::path::begin(Header), |
| 43 |
HeaderE = llvm::sys::path::end(Header), I = FileI; |
| 44 |
HeaderI != HeaderE && *I == *HeaderI && I != FileE; ++I, ++HeaderI) { |
| 45 |
++Segments; |
| 46 |
} |
| 47 |
MaxSegments = std::max(Segments, MaxSegments); |
| 48 |
} |
| 49 |
return MaxSegments; |
| 50 |
} |
| 51 |
|
| 52 |
static void rank(std::vector<SymbolAndSignals> &Symbols, |
| 53 |
llvm::StringRef FileName) { |
| 54 |
llvm::StringMap<double> Score; |
| 55 |
for (const auto &Symbol : Symbols) { |
| 56 |
// Calculate a score from the similarity of the header the symbol is in |
| 57 |
// with the current file and the popularity of the symbol. |
| 58 |
double NewScore = similarityScore(FileName, Symbol.Symbol.getFilePath()) * |
| 59 |
(1.0 + std::log2(1 + Symbol.Signals.Seen)); |
| 60 |
double &S = Score[Symbol.Symbol.getFilePath()]; |
| 61 |
S = std::max(S, NewScore); |
| 62 |
} |
| 63 |
// Sort by the gathered scores. Use file name as a tie breaker so we can |
| 64 |
// deduplicate. |
| 65 |
llvm::sort(Symbols, |
| 66 |
[&](const SymbolAndSignals &A, const SymbolAndSignals &B) { |
| 67 |
auto AS = Score[A.Symbol.getFilePath()]; |
| 68 |
auto BS = Score[B.Symbol.getFilePath()]; |
| 69 |
if (AS != BS) |
| 70 |
return AS > BS; |
| 71 |
return A.Symbol.getFilePath() < B.Symbol.getFilePath(); |
| 72 |
}); |
| 73 |
} |
| 74 |
|
| 75 |
std::vector<find_all_symbols::SymbolInfo> |
| 76 |
SymbolIndexManager::search(llvm::StringRef Identifier, |
| 77 |
bool IsNestedSearch, |
| 78 |
llvm::StringRef FileName) const { |
| 79 |
// The identifier may be fully qualified, so split it and get all the context |
| 80 |
// names. |
| 81 |
llvm::SmallVector<llvm::StringRef, 8> Names; |
| 82 |
Identifier.split(Names, "::"); |
| 83 |
|
| 84 |
bool IsFullyQualified = false; |
| 85 |
if (Identifier.starts_with("::")) { |
| 86 |
Names.erase(Names.begin()); // Drop first (empty) element. |
| 87 |
IsFullyQualified = true; |
| 88 |
} |
| 89 |
|
| 90 |
// As long as we don't find a result keep stripping name parts from the end. |
| 91 |
// This is to support nested classes which aren't recorded in the database. |
| 92 |
// Eventually we will either hit a class (namespaces aren't in the database |
| 93 |
// either) and can report that result. |
| 94 |
bool TookPrefix = false; |
| 95 |
std::vector<SymbolAndSignals> MatchedSymbols; |
| 96 |
do { |
| 97 |
std::vector<SymbolAndSignals> Symbols; |
| 98 |
for (const auto &DB : SymbolIndices) { |
| 99 |
auto Res = DB.get()->search(Names.back()); |
| 100 |
Symbols.insert(Symbols.end(), Res.begin(), Res.end()); |
| 101 |
} |
| 102 |
|
| 103 |
LLVM_DEBUG(llvm::dbgs() << "Searching " << Names.back() << "... got " |
| 104 |
<< Symbols.size() << " results...\n"); |
| 105 |
|
| 106 |
for (auto &SymAndSig : Symbols) { |
| 107 |
const SymbolInfo &Symbol = SymAndSig.Symbol; |
| 108 |
// Match the identifier name without qualifier. |
| 109 |
bool IsMatched = true; |
| 110 |
auto SymbolContext = Symbol.getContexts().begin(); |
| 111 |
auto IdentiferContext = Names.rbegin() + 1; // Skip identifier name. |
| 112 |
// Match the remaining context names. |
| 113 |
while (IdentiferContext != Names.rend() && |
| 114 |
SymbolContext != Symbol.getContexts().end()) { |
| 115 |
if (SymbolContext->second == *IdentiferContext) { |
| 116 |
++IdentiferContext; |
| 117 |
++SymbolContext; |
| 118 |
} else if (SymbolContext->first == |
| 119 |
find_all_symbols::SymbolInfo::ContextType::EnumDecl) { |
| 120 |
// Skip non-scoped enum context. |
| 121 |
++SymbolContext; |
| 122 |
} else { |
| 123 |
IsMatched = false; |
| 124 |
break; |
| 125 |
} |
| 126 |
} |
| 127 |
|
| 128 |
// If the name was qualified we only want to add results if we evaluated |
| 129 |
// all contexts. |
| 130 |
if (IsFullyQualified) |
| 131 |
IsMatched &= (SymbolContext == Symbol.getContexts().end()); |
| 132 |
|
| 133 |
// FIXME: Support full match. At this point, we only find symbols in |
| 134 |
// database which end with the same contexts with the identifier. |
| 135 |
if (IsMatched && IdentiferContext == Names.rend()) { |
| 136 |
// If we're in a situation where we took a prefix but the thing we |
| 137 |
// found couldn't possibly have a nested member ignore it. |
| 138 |
if (TookPrefix && |
| 139 |
(Symbol.getSymbolKind() == SymbolInfo::SymbolKind::Function || |
| 140 |
Symbol.getSymbolKind() == SymbolInfo::SymbolKind::Variable || |
| 141 |
Symbol.getSymbolKind() == |
| 142 |
SymbolInfo::SymbolKind::EnumConstantDecl || |
| 143 |
Symbol.getSymbolKind() == SymbolInfo::SymbolKind::Macro)) |
| 144 |
continue; |
| 145 |
|
| 146 |
MatchedSymbols.push_back(std::move(SymAndSig)); |
| 147 |
} |
| 148 |
} |
| 149 |
Names.pop_back(); |
| 150 |
TookPrefix = true; |
| 151 |
} while (MatchedSymbols.empty() && !Names.empty() && IsNestedSearch); |
| 152 |
|
| 153 |
rank(MatchedSymbols, FileName); |
| 154 |
// Strip signals, they are no longer needed. |
| 155 |
std::vector<SymbolInfo> Res; |
| 156 |
Res.reserve(MatchedSymbols.size()); |
| 157 |
for (auto &SymAndSig : MatchedSymbols) |
| 158 |
Res.push_back(std::move(SymAndSig.Symbol)); |
| 159 |
return Res; |
| 160 |
} |
| 161 |
|
| 162 |
} // namespace include_fixer |
| 163 |
} // namespace clang |