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