/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Tooling/InterpolatingCompilationDatabase.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- InterpolatingCompilationDatabase.cpp ---------------------*- 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 | | // InterpolatingCompilationDatabase wraps another CompilationDatabase and |
10 | | // attempts to heuristically determine appropriate compile commands for files |
11 | | // that are not included, such as headers or newly created files. |
12 | | // |
13 | | // Motivating cases include: |
14 | | // Header files that live next to their implementation files. These typically |
15 | | // share a base filename. (libclang/CXString.h, libclang/CXString.cpp). |
16 | | // Some projects separate headers from includes. Filenames still typically |
17 | | // match, maybe other path segments too. (include/llvm/IR/Use.h, lib/IR/Use.cc). |
18 | | // Matches are sometimes only approximate (Sema.h, SemaDecl.cpp). This goes |
19 | | // for directories too (Support/Unix/Process.inc, lib/Support/Process.cpp). |
20 | | // Even if we can't find a "right" compile command, even a random one from |
21 | | // the project will tend to get important flags like -I and -x right. |
22 | | // |
23 | | // We "borrow" the compile command for the closest available file: |
24 | | // - points are awarded if the filename matches (ignoring extension) |
25 | | // - points are awarded if the directory structure matches |
26 | | // - ties are broken by length of path prefix match |
27 | | // |
28 | | // The compile command is adjusted, replacing the filename and removing output |
29 | | // file arguments. The -x and -std flags may be affected too. |
30 | | // |
31 | | // Source language is a tricky issue: is it OK to use a .c file's command |
32 | | // for building a .cc file? What language is a .h file in? |
33 | | // - We only consider compile commands for c-family languages as candidates. |
34 | | // - For files whose language is implied by the filename (e.g. .m, .hpp) |
35 | | // we prefer candidates from the same language. |
36 | | // If we must cross languages, we drop any -x and -std flags. |
37 | | // - For .h files, candidates from any c-family language are acceptable. |
38 | | // We use the candidate's language, inserting e.g. -x c++-header. |
39 | | // |
40 | | // This class is only useful when wrapping databases that can enumerate all |
41 | | // their compile commands. If getAllFilenames() is empty, no inference occurs. |
42 | | // |
43 | | //===----------------------------------------------------------------------===// |
44 | | |
45 | | #include "clang/Basic/LangStandard.h" |
46 | | #include "clang/Driver/Driver.h" |
47 | | #include "clang/Driver/Options.h" |
48 | | #include "clang/Driver/Types.h" |
49 | | #include "clang/Tooling/CompilationDatabase.h" |
50 | | #include "llvm/ADT/ArrayRef.h" |
51 | | #include "llvm/ADT/DenseMap.h" |
52 | | #include "llvm/ADT/Optional.h" |
53 | | #include "llvm/ADT/StringExtras.h" |
54 | | #include "llvm/ADT/StringSwitch.h" |
55 | | #include "llvm/Option/ArgList.h" |
56 | | #include "llvm/Option/OptTable.h" |
57 | | #include "llvm/Support/Debug.h" |
58 | | #include "llvm/Support/Path.h" |
59 | | #include "llvm/Support/StringSaver.h" |
60 | | #include "llvm/Support/raw_ostream.h" |
61 | | #include <memory> |
62 | | |
63 | | namespace clang { |
64 | | namespace tooling { |
65 | | namespace { |
66 | | using namespace llvm; |
67 | | namespace types = clang::driver::types; |
68 | | namespace path = llvm::sys::path; |
69 | | |
70 | | // The length of the prefix these two strings have in common. |
71 | 45 | size_t matchingPrefix(StringRef L, StringRef R) { |
72 | 45 | size_t Limit = std::min(L.size(), R.size()); |
73 | 2.30k | for (size_t I = 0; I < Limit; ++I2.26k ) |
74 | 2.30k | if (L[I] != R[I]) |
75 | 44 | return I; |
76 | 1 | return Limit; |
77 | 45 | } |
78 | | |
79 | | // A comparator for searching SubstringWithIndexes with std::equal_range etc. |
80 | | // Optionaly prefix semantics: compares equal if the key is a prefix. |
81 | | template <bool Prefix> struct Less { |
82 | 159 | bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const { |
83 | 159 | StringRef V = Prefix ? Value.first.substr(0, Key.size())66 : Value.first93 ; |
84 | 159 | return Key < V; |
85 | 159 | } InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<true>::operator()(llvm::StringRef, std::__1::pair<llvm::StringRef, unsigned long>) const Line | Count | Source | 82 | 66 | bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const { | 83 | 66 | StringRef V = Prefix ? Value.first.substr(0, Key.size()) : Value.first0 ; | 84 | 66 | return Key < V; | 85 | 66 | } |
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<false>::operator()(llvm::StringRef, std::__1::pair<llvm::StringRef, unsigned long>) const Line | Count | Source | 82 | 93 | bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const { | 83 | 93 | StringRef V = Prefix ? Value.first.substr(0, Key.size())0 : Value.first; | 84 | 93 | return Key < V; | 85 | 93 | } |
|
86 | 216 | bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const { |
87 | 216 | StringRef V = Prefix ? Value.first.substr(0, Key.size())85 : Value.first131 ; |
88 | 216 | return V < Key; |
89 | 216 | } InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<true>::operator()(std::__1::pair<llvm::StringRef, unsigned long>, llvm::StringRef) const Line | Count | Source | 86 | 85 | bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const { | 87 | 85 | StringRef V = Prefix ? Value.first.substr(0, Key.size()) : Value.first0 ; | 88 | 85 | return V < Key; | 89 | 85 | } |
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<false>::operator()(std::__1::pair<llvm::StringRef, unsigned long>, llvm::StringRef) const Line | Count | Source | 86 | 131 | bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const { | 87 | 131 | StringRef V = Prefix ? Value.first.substr(0, Key.size())0 : Value.first; | 88 | 131 | return V < Key; | 89 | 131 | } |
|
90 | | }; |
91 | | |
92 | | // Infer type from filename. If we might have gotten it wrong, set *Certain. |
93 | | // *.h will be inferred as a C header, but not certain. |
94 | 15.0k | types::ID guessType(StringRef Filename, bool *Certain = nullptr) { |
95 | | // path::extension is ".cpp", lookupTypeForExtension wants "cpp". |
96 | 15.0k | auto Lang = |
97 | 15.0k | types::lookupTypeForExtension(path::extension(Filename).substr(1)); |
98 | 15.0k | if (Certain) |
99 | 47 | *Certain = Lang != types::TY_CHeader && Lang != types::TY_INVALID32 ; |
100 | 15.0k | return Lang; |
101 | 15.0k | } |
102 | | |
103 | | // Return Lang as one of the canonical supported types. |
104 | | // e.g. c-header --> c; fortran --> TY_INVALID |
105 | 15.0k | static types::ID foldType(types::ID Lang) { |
106 | 15.0k | switch (Lang) { |
107 | 111 | case types::TY_C: |
108 | 111 | case types::TY_CHeader: |
109 | 111 | return types::TY_C; |
110 | 0 | case types::TY_ObjC: |
111 | 0 | case types::TY_ObjCHeader: |
112 | 0 | return types::TY_ObjC; |
113 | 14.8k | case types::TY_CXX: |
114 | 14.8k | case types::TY_CXXHeader: |
115 | 14.8k | return types::TY_CXX; |
116 | 13 | case types::TY_ObjCXX: |
117 | 14 | case types::TY_ObjCXXHeader: |
118 | 14 | return types::TY_ObjCXX; |
119 | 0 | case types::TY_CUDA: |
120 | 0 | case types::TY_CUDA_DEVICE: |
121 | 0 | return types::TY_CUDA; |
122 | 29 | default: |
123 | 29 | return types::TY_INVALID; |
124 | 15.0k | } |
125 | 15.0k | } |
126 | | |
127 | | // A CompileCommand that can be applied to another file. |
128 | | struct TransferableCommand { |
129 | | // Flags that should not apply to all files are stripped from CommandLine. |
130 | | CompileCommand Cmd; |
131 | | // Language detected from -x or the filename. Never TY_INVALID. |
132 | | Optional<types::ID> Type; |
133 | | // Standard specified by -std. |
134 | | LangStandard::Kind Std = LangStandard::lang_unspecified; |
135 | | // Whether the command line is for the cl-compatible driver. |
136 | | bool ClangCLMode; |
137 | | |
138 | | TransferableCommand(CompileCommand C) |
139 | 24 | : Cmd(std::move(C)), Type(guessType(Cmd.Filename)) { |
140 | 24 | std::vector<std::string> OldArgs = std::move(Cmd.CommandLine); |
141 | 24 | Cmd.CommandLine.clear(); |
142 | | |
143 | | // Wrap the old arguments in an InputArgList. |
144 | 24 | llvm::opt::InputArgList ArgList; |
145 | 24 | { |
146 | 24 | SmallVector<const char *, 16> TmpArgv; |
147 | 24 | for (const std::string &S : OldArgs) |
148 | 118 | TmpArgv.push_back(S.c_str()); |
149 | 24 | ClangCLMode = !TmpArgv.empty() && |
150 | 24 | driver::IsClangCL(driver::getDriverMode( |
151 | 24 | TmpArgv.front(), llvm::makeArrayRef(TmpArgv).slice(1))); |
152 | 24 | ArgList = {TmpArgv.begin(), TmpArgv.end()}; |
153 | 24 | } |
154 | | |
155 | | // Parse the old args in order to strip out and record unwanted flags. |
156 | | // We parse each argument individually so that we can retain the exact |
157 | | // spelling of each argument; re-rendering is lossy for aliased flags. |
158 | | // E.g. in CL mode, /W4 maps to -Wall. |
159 | 24 | auto &OptTable = clang::driver::getDriverOptTable(); |
160 | 24 | if (!OldArgs.empty()) |
161 | 24 | Cmd.CommandLine.emplace_back(OldArgs.front()); |
162 | 90 | for (unsigned Pos = 1; Pos < OldArgs.size();) { |
163 | 67 | using namespace driver::options; |
164 | | |
165 | 67 | const unsigned OldPos = Pos; |
166 | 67 | std::unique_ptr<llvm::opt::Arg> Arg(OptTable.ParseOneArg( |
167 | 67 | ArgList, Pos, |
168 | 67 | /* Include */ ClangCLMode ? CoreOption | CLOption6 : 061 , |
169 | 67 | /* Exclude */ ClangCLMode ? 06 : CLOption61 )); |
170 | | |
171 | 67 | if (!Arg) |
172 | 0 | continue; |
173 | | |
174 | 67 | const llvm::opt::Option &Opt = Arg->getOption(); |
175 | | |
176 | | // Strip input and output files. |
177 | 67 | if (Opt.matches(OPT_INPUT) || Opt.matches(OPT_o)43 || |
178 | 67 | (41 ClangCLMode41 && (4 Opt.matches(OPT__SLASH_Fa)4 || |
179 | 4 | Opt.matches(OPT__SLASH_Fe) || |
180 | 4 | Opt.matches(OPT__SLASH_Fi) || |
181 | 4 | Opt.matches(OPT__SLASH_Fo)))) |
182 | 26 | continue; |
183 | | |
184 | | // ...including when the inputs are passed after --. |
185 | 41 | if (Opt.matches(OPT__DASH_DASH)) |
186 | 1 | break; |
187 | | |
188 | | // Strip -x, but record the overridden language. |
189 | 40 | if (const auto GivenType = tryParseTypeArg(*Arg)) { |
190 | 2 | Type = *GivenType; |
191 | 2 | continue; |
192 | 2 | } |
193 | | |
194 | | // Strip -std, but record the value. |
195 | 38 | if (const auto GivenStd = tryParseStdArg(*Arg)) { |
196 | 7 | if (*GivenStd != LangStandard::lang_unspecified) |
197 | 7 | Std = *GivenStd; |
198 | 7 | continue; |
199 | 7 | } |
200 | | |
201 | 31 | Cmd.CommandLine.insert(Cmd.CommandLine.end(), |
202 | 31 | OldArgs.data() + OldPos, OldArgs.data() + Pos); |
203 | 31 | } |
204 | | |
205 | | // Make use of -std iff -x was missing. |
206 | 24 | if (Type == types::TY_INVALID && Std != LangStandard::lang_unspecified0 ) |
207 | 0 | Type = toType(LangStandard::getLangStandardForKind(Std).getLanguage()); |
208 | 24 | Type = foldType(*Type); |
209 | | // The contract is to store None instead of TY_INVALID. |
210 | 24 | if (Type == types::TY_INVALID) |
211 | 0 | Type = llvm::None; |
212 | 24 | } |
213 | | |
214 | | // Produce a CompileCommand for \p filename, based on this one. |
215 | | // (This consumes the TransferableCommand just to avoid copying Cmd). |
216 | 24 | CompileCommand transferTo(StringRef Filename) && { |
217 | 24 | CompileCommand Result = std::move(Cmd); |
218 | 24 | Result.Heuristic = "inferred from " + Result.Filename; |
219 | 24 | Result.Filename = std::string(Filename); |
220 | 24 | bool TypeCertain; |
221 | 24 | auto TargetType = guessType(Filename, &TypeCertain); |
222 | | // If the filename doesn't determine the language (.h), transfer with -x. |
223 | 24 | if ((!TargetType || !TypeCertain22 ) && Type10 ) { |
224 | | // Use *Type, or its header variant if the file is a header. |
225 | | // Treat no/invalid extension as header (e.g. C++ standard library). |
226 | 10 | TargetType = |
227 | 10 | (!TargetType || types::onlyPrecompileType(TargetType)8 ) // header? |
228 | 10 | ? types::lookupHeaderTypeForSourceType(*Type) |
229 | 10 | : *Type0 ; |
230 | 10 | if (ClangCLMode) { |
231 | 2 | const StringRef Flag = toCLFlag(TargetType); |
232 | 2 | if (!Flag.empty()) |
233 | 2 | Result.CommandLine.push_back(std::string(Flag)); |
234 | 8 | } else { |
235 | 8 | Result.CommandLine.push_back("-x"); |
236 | 8 | Result.CommandLine.push_back(types::getTypeName(TargetType)); |
237 | 8 | } |
238 | 10 | } |
239 | | // --std flag may only be transferred if the language is the same. |
240 | | // We may consider "translating" these, e.g. c++11 -> c11. |
241 | 24 | if (Std != LangStandard::lang_unspecified && foldType(TargetType) == Type7 ) { |
242 | 6 | Result.CommandLine.emplace_back(( |
243 | 6 | llvm::Twine(ClangCLMode ? "/std:"0 : "-std=") + |
244 | 6 | LangStandard::getLangStandardForKind(Std).getName()).str()); |
245 | 6 | } |
246 | 24 | Result.CommandLine.push_back("--"); |
247 | 24 | Result.CommandLine.push_back(std::string(Filename)); |
248 | 24 | return Result; |
249 | 24 | } |
250 | | |
251 | | private: |
252 | | // Map the language from the --std flag to that of the -x flag. |
253 | 0 | static types::ID toType(Language Lang) { |
254 | 0 | switch (Lang) { |
255 | 0 | case Language::C: |
256 | 0 | return types::TY_C; |
257 | 0 | case Language::CXX: |
258 | 0 | return types::TY_CXX; |
259 | 0 | case Language::ObjC: |
260 | 0 | return types::TY_ObjC; |
261 | 0 | case Language::ObjCXX: |
262 | 0 | return types::TY_ObjCXX; |
263 | 0 | default: |
264 | 0 | return types::TY_INVALID; |
265 | 0 | } |
266 | 0 | } |
267 | | |
268 | | // Convert a file type to the matching CL-style type flag. |
269 | 2 | static StringRef toCLFlag(types::ID Type) { |
270 | 2 | switch (Type) { |
271 | 0 | case types::TY_C: |
272 | 0 | case types::TY_CHeader: |
273 | 0 | return "/TC"; |
274 | 0 | case types::TY_CXX: |
275 | 2 | case types::TY_CXXHeader: |
276 | 2 | return "/TP"; |
277 | 0 | default: |
278 | 0 | return StringRef(); |
279 | 2 | } |
280 | 2 | } |
281 | | |
282 | | // Try to interpret the argument as a type specifier, e.g. '-x'. |
283 | 40 | Optional<types::ID> tryParseTypeArg(const llvm::opt::Arg &Arg) { |
284 | 40 | const llvm::opt::Option &Opt = Arg.getOption(); |
285 | 40 | using namespace driver::options; |
286 | 40 | if (ClangCLMode) { |
287 | 4 | if (Opt.matches(OPT__SLASH_TC) || Opt.matches(OPT__SLASH_Tc)) |
288 | 0 | return types::TY_C; |
289 | 4 | if (Opt.matches(OPT__SLASH_TP) || Opt.matches(OPT__SLASH_Tp)) |
290 | 0 | return types::TY_CXX; |
291 | 36 | } else { |
292 | 36 | if (Opt.matches(driver::options::OPT_x)) |
293 | 2 | return types::lookupTypeForTypeSpecifier(Arg.getValue()); |
294 | 36 | } |
295 | 38 | return None; |
296 | 40 | } |
297 | | |
298 | | // Try to interpret the argument as '-std='. |
299 | 38 | Optional<LangStandard::Kind> tryParseStdArg(const llvm::opt::Arg &Arg) { |
300 | 38 | using namespace driver::options; |
301 | 38 | if (Arg.getOption().matches(ClangCLMode ? OPT__SLASH_std4 : OPT_std_EQ34 )) |
302 | 7 | return LangStandard::getLangKind(Arg.getValue()); |
303 | 31 | return None; |
304 | 38 | } |
305 | | }; |
306 | | |
307 | | // Given a filename, FileIndex picks the best matching file from the underlying |
308 | | // DB. This is the proxy file whose CompileCommand will be reused. The |
309 | | // heuristics incorporate file name, extension, and directory structure. |
310 | | // Strategy: |
311 | | // - Build indexes of each of the substrings we want to look up by. |
312 | | // These indexes are just sorted lists of the substrings. |
313 | | // - Each criterion corresponds to a range lookup into the index, so we only |
314 | | // need O(log N) string comparisons to determine scores. |
315 | | // |
316 | | // Apart from path proximity signals, also takes file extensions into account |
317 | | // when scoring the candidates. |
318 | | class FileIndex { |
319 | | public: |
320 | | FileIndex(std::vector<std::string> Files) |
321 | 42 | : OriginalPaths(std::move(Files)), Strings(Arena) { |
322 | | // Sort commands by filename for determinism (index is a tiebreaker later). |
323 | 42 | llvm::sort(OriginalPaths); |
324 | 42 | Paths.reserve(OriginalPaths.size()); |
325 | 42 | Types.reserve(OriginalPaths.size()); |
326 | 42 | Stems.reserve(OriginalPaths.size()); |
327 | 15.0k | for (size_t I = 0; I < OriginalPaths.size(); ++I14.9k ) { |
328 | 14.9k | StringRef Path = Strings.save(StringRef(OriginalPaths[I]).lower()); |
329 | | |
330 | 14.9k | Paths.emplace_back(Path, I); |
331 | 14.9k | Types.push_back(foldType(guessType(OriginalPaths[I]))); |
332 | 14.9k | Stems.emplace_back(sys::path::stem(Path), I); |
333 | 14.9k | auto Dir = ++sys::path::rbegin(Path), DirEnd = sys::path::rend(Path); |
334 | 74.9k | for (int J = 0; J < DirectorySegmentsIndexed && Dir != DirEnd59.9k ; ++J, ++Dir59.9k ) |
335 | 59.9k | if (Dir->size() > ShortDirectorySegment) // not trivial ones |
336 | 59.9k | Components.emplace_back(*Dir, I); |
337 | 14.9k | } |
338 | 42 | llvm::sort(Paths); |
339 | 42 | llvm::sort(Stems); |
340 | 42 | llvm::sort(Components); |
341 | 42 | } |
342 | | |
343 | 61 | bool empty() const { return Paths.empty(); } |
344 | | |
345 | | // Returns the path for the file that best fits OriginalFilename. |
346 | | // Candidates with extensions matching PreferLanguage will be chosen over |
347 | | // others (unless it's TY_INVALID, or all candidates are bad). |
348 | | StringRef chooseProxy(StringRef OriginalFilename, |
349 | 23 | types::ID PreferLanguage) const { |
350 | 23 | assert(!empty() && "need at least one candidate!"); |
351 | 0 | std::string Filename = OriginalFilename.lower(); |
352 | 23 | auto Candidates = scoreCandidates(Filename); |
353 | 23 | std::pair<size_t, int> Best = |
354 | 23 | pickWinner(Candidates, Filename, PreferLanguage); |
355 | | |
356 | 23 | DEBUG_WITH_TYPE( |
357 | 23 | "interpolate", |
358 | 23 | llvm::dbgs() << "interpolate: chose " << OriginalPaths[Best.first] |
359 | 23 | << " as proxy for " << OriginalFilename << " preferring " |
360 | 23 | << (PreferLanguage == types::TY_INVALID |
361 | 23 | ? "none" |
362 | 23 | : types::getTypeName(PreferLanguage)) |
363 | 23 | << " score=" << Best.second << "\n"); |
364 | 23 | return OriginalPaths[Best.first]; |
365 | 23 | } |
366 | | |
367 | | private: |
368 | | using SubstringAndIndex = std::pair<StringRef, size_t>; |
369 | | // Directory matching parameters: we look at the last two segments of the |
370 | | // parent directory (usually the semantically significant ones in practice). |
371 | | // We search only the last four of each candidate (for efficiency). |
372 | | constexpr static int DirectorySegmentsIndexed = 4; |
373 | | constexpr static int DirectorySegmentsQueried = 2; |
374 | | constexpr static int ShortDirectorySegment = 1; // Only look at longer names. |
375 | | |
376 | | // Award points to candidate entries that should be considered for the file. |
377 | | // Returned keys are indexes into paths, and the values are (nonzero) scores. |
378 | 23 | DenseMap<size_t, int> scoreCandidates(StringRef Filename) const { |
379 | | // Decompose Filename into the parts we care about. |
380 | | // /some/path/complicated/project/Interesting.h |
381 | | // [-prefix--][---dir---] [-dir-] [--stem---] |
382 | 23 | StringRef Stem = sys::path::stem(Filename); |
383 | 23 | llvm::SmallVector<StringRef, DirectorySegmentsQueried> Dirs; |
384 | 23 | llvm::StringRef Prefix; |
385 | 23 | auto Dir = ++sys::path::rbegin(Filename), |
386 | 23 | DirEnd = sys::path::rend(Filename); |
387 | 65 | for (int I = 0; I < DirectorySegmentsQueried && Dir != DirEnd44 ; ++I, ++Dir42 ) { |
388 | 42 | if (Dir->size() > ShortDirectorySegment) |
389 | 27 | Dirs.push_back(*Dir); |
390 | 42 | Prefix = Filename.substr(0, Dir - DirEnd); |
391 | 42 | } |
392 | | |
393 | | // Now award points based on lookups into our various indexes. |
394 | 23 | DenseMap<size_t, int> Candidates; // Index -> score. |
395 | 94 | auto Award = [&](int Points, ArrayRef<SubstringAndIndex> Range) { |
396 | 94 | for (const auto &Entry : Range) |
397 | 148 | Candidates[Entry.second] += Points; |
398 | 94 | }; |
399 | | // Award one point if the file's basename is a prefix of the candidate, |
400 | | // and another if it's an exact match (so exact matches get two points). |
401 | 23 | Award(1, indexLookup</*Prefix=*/true>(Stem, Stems)); |
402 | 23 | Award(1, indexLookup</*Prefix=*/false>(Stem, Stems)); |
403 | | // For each of the last few directories in the Filename, award a point |
404 | | // if it's present in the candidate. |
405 | 23 | for (StringRef Dir : Dirs) |
406 | 27 | Award(1, indexLookup</*Prefix=*/false>(Dir, Components)); |
407 | | // Award one more point if the whole rest of the path matches. |
408 | 23 | if (sys::path::root_directory(Prefix) != Prefix) |
409 | 21 | Award(1, indexLookup</*Prefix=*/true>(Prefix, Paths)); |
410 | 23 | return Candidates; |
411 | 23 | } |
412 | | |
413 | | // Pick a single winner from the set of scored candidates. |
414 | | // Returns (index, score). |
415 | | std::pair<size_t, int> pickWinner(const DenseMap<size_t, int> &Candidates, |
416 | | StringRef Filename, |
417 | 23 | types::ID PreferredLanguage) const { |
418 | 23 | struct ScoredCandidate { |
419 | 23 | size_t Index; |
420 | 23 | bool Preferred; |
421 | 23 | int Points; |
422 | 23 | size_t PrefixLength; |
423 | 23 | }; |
424 | | // Choose the best candidate by (preferred, points, prefix length, alpha). |
425 | 23 | ScoredCandidate Best = {size_t(-1), false, 0, 0}; |
426 | 57 | for (const auto &Candidate : Candidates) { |
427 | 57 | ScoredCandidate S; |
428 | 57 | S.Index = Candidate.first; |
429 | 57 | S.Preferred = PreferredLanguage == types::TY_INVALID || |
430 | 57 | PreferredLanguage == Types[S.Index]31 ; |
431 | 57 | S.Points = Candidate.second; |
432 | 57 | if (!S.Preferred && Best.Preferred9 ) |
433 | 4 | continue; |
434 | 53 | if (S.Preferred == Best.Preferred) { |
435 | 32 | if (S.Points < Best.Points) |
436 | 11 | continue; |
437 | 21 | if (S.Points == Best.Points) { |
438 | 8 | S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first); |
439 | 8 | if (S.PrefixLength < Best.PrefixLength) |
440 | 0 | continue; |
441 | | // hidden heuristics should at least be deterministic! |
442 | 8 | if (S.PrefixLength == Best.PrefixLength) |
443 | 8 | if (S.Index > Best.Index) |
444 | 7 | continue; |
445 | 8 | } |
446 | 21 | } |
447 | | // PrefixLength was only set above if actually needed for a tiebreak. |
448 | | // But it definitely needs to be set to break ties in the future. |
449 | 35 | S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first); |
450 | 35 | Best = S; |
451 | 35 | } |
452 | | // Edge case: no candidate got any points. |
453 | | // We ignore PreferredLanguage at this point (not ideal). |
454 | 23 | if (Best.Index == size_t(-1)) |
455 | 1 | return {longestMatch(Filename, Paths).second, 0}; |
456 | 22 | return {Best.Index, Best.Points}; |
457 | 23 | } |
458 | | |
459 | | // Returns the range within a sorted index that compares equal to Key. |
460 | | // If Prefix is true, it's instead the range starting with Key. |
461 | | template <bool Prefix> |
462 | | ArrayRef<SubstringAndIndex> |
463 | 94 | indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const { |
464 | | // Use pointers as iteratiors to ease conversion of result to ArrayRef. |
465 | 94 | auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key, |
466 | 94 | Less<Prefix>()); |
467 | 94 | return {Range.first, Range.second}; |
468 | 94 | } InterpolatingCompilationDatabase.cpp:llvm::ArrayRef<std::__1::pair<llvm::StringRef, unsigned long> > clang::tooling::(anonymous namespace)::FileIndex::indexLookup<true>(llvm::StringRef, llvm::ArrayRef<std::__1::pair<llvm::StringRef, unsigned long> >) const Line | Count | Source | 463 | 44 | indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const { | 464 | | // Use pointers as iteratiors to ease conversion of result to ArrayRef. | 465 | 44 | auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key, | 466 | 44 | Less<Prefix>()); | 467 | 44 | return {Range.first, Range.second}; | 468 | 44 | } |
InterpolatingCompilationDatabase.cpp:llvm::ArrayRef<std::__1::pair<llvm::StringRef, unsigned long> > clang::tooling::(anonymous namespace)::FileIndex::indexLookup<false>(llvm::StringRef, llvm::ArrayRef<std::__1::pair<llvm::StringRef, unsigned long> >) const Line | Count | Source | 463 | 50 | indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const { | 464 | | // Use pointers as iteratiors to ease conversion of result to ArrayRef. | 465 | 50 | auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key, | 466 | 50 | Less<Prefix>()); | 467 | 50 | return {Range.first, Range.second}; | 468 | 50 | } |
|
469 | | |
470 | | // Performs a point lookup into a nonempty index, returning a longest match. |
471 | | SubstringAndIndex longestMatch(StringRef Key, |
472 | 1 | ArrayRef<SubstringAndIndex> Idx) const { |
473 | 1 | assert(!Idx.empty()); |
474 | | // Longest substring match will be adjacent to a direct lookup. |
475 | 0 | auto It = llvm::lower_bound(Idx, SubstringAndIndex{Key, 0}); |
476 | 1 | if (It == Idx.begin()) |
477 | 0 | return *It; |
478 | 1 | if (It == Idx.end()) |
479 | 0 | return *--It; |
480 | | // Have to choose between It and It-1 |
481 | 1 | size_t Prefix = matchingPrefix(Key, It->first); |
482 | 1 | size_t PrevPrefix = matchingPrefix(Key, (It - 1)->first); |
483 | 1 | return Prefix > PrevPrefix ? *It0 : *--It; |
484 | 1 | } |
485 | | |
486 | | // Original paths, everything else is in lowercase. |
487 | | std::vector<std::string> OriginalPaths; |
488 | | BumpPtrAllocator Arena; |
489 | | StringSaver Strings; |
490 | | // Indexes of candidates by certain substrings. |
491 | | // String is lowercase and sorted, index points into OriginalPaths. |
492 | | std::vector<SubstringAndIndex> Paths; // Full path. |
493 | | // Lang types obtained by guessing on the corresponding path. I-th element is |
494 | | // a type for the I-th path. |
495 | | std::vector<types::ID> Types; |
496 | | std::vector<SubstringAndIndex> Stems; // Basename, without extension. |
497 | | std::vector<SubstringAndIndex> Components; // Last path components. |
498 | | }; |
499 | | |
500 | | // The actual CompilationDatabase wrapper delegates to its inner database. |
501 | | // If no match, looks up a proxy file in FileIndex and transfers its |
502 | | // command to the requested file. |
503 | | class InterpolatingCompilationDatabase : public CompilationDatabase { |
504 | | public: |
505 | | InterpolatingCompilationDatabase(std::unique_ptr<CompilationDatabase> Inner) |
506 | 42 | : Inner(std::move(Inner)), Index(this->Inner->getAllFiles()) {} |
507 | | |
508 | | std::vector<CompileCommand> |
509 | 38 | getCompileCommands(StringRef Filename) const override { |
510 | 38 | auto Known = Inner->getCompileCommands(Filename); |
511 | 38 | if (Index.empty() || !Known.empty()) |
512 | 15 | return Known; |
513 | 23 | bool TypeCertain; |
514 | 23 | auto Lang = guessType(Filename, &TypeCertain); |
515 | 23 | if (!TypeCertain) |
516 | 9 | Lang = types::TY_INVALID; |
517 | 23 | auto ProxyCommands = |
518 | 23 | Inner->getCompileCommands(Index.chooseProxy(Filename, foldType(Lang))); |
519 | 23 | if (ProxyCommands.empty()) |
520 | 0 | return {}; |
521 | 23 | return {transferCompileCommand(std::move(ProxyCommands.front()), Filename)}; |
522 | 23 | } |
523 | | |
524 | 0 | std::vector<std::string> getAllFiles() const override { |
525 | 0 | return Inner->getAllFiles(); |
526 | 0 | } |
527 | | |
528 | 1 | std::vector<CompileCommand> getAllCompileCommands() const override { |
529 | 1 | return Inner->getAllCompileCommands(); |
530 | 1 | } |
531 | | |
532 | | private: |
533 | | std::unique_ptr<CompilationDatabase> Inner; |
534 | | FileIndex Index; |
535 | | }; |
536 | | |
537 | | } // namespace |
538 | | |
539 | | std::unique_ptr<CompilationDatabase> |
540 | 42 | inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) { |
541 | 42 | return std::make_unique<InterpolatingCompilationDatabase>(std::move(Inner)); |
542 | 42 | } |
543 | | |
544 | | tooling::CompileCommand transferCompileCommand(CompileCommand Cmd, |
545 | 24 | StringRef Filename) { |
546 | 24 | return TransferableCommand(std::move(Cmd)).transferTo(Filename); |
547 | 24 | } |
548 | | |
549 | | } // namespace tooling |
550 | | } // namespace clang |