1 //===- InterpolatingCompilationDatabase.cpp ---------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // InterpolatingCompilationDatabase wraps another CompilationDatabase and
11 // attempts to heuristically determine appropriate compile commands for files
12 // that are not included, such as headers or newly created files.
14 // Motivating cases include:
15 // Header files that live next to their implementation files. These typically
16 // share a base filename. (libclang/CXString.h, libclang/CXString.cpp).
17 // Some projects separate headers from includes. Filenames still typically
18 // match, maybe other path segments too. (include/llvm/IR/Use.h, lib/IR/Use.cc).
19 // Matches are sometimes only approximate (Sema.h, SemaDecl.cpp). This goes
20 // for directories too (Support/Unix/Process.inc, lib/Support/Process.cpp).
21 // Even if we can't find a "right" compile command, even a random one from
22 // the project will tend to get important flags like -I and -x right.
24 // We "borrow" the compile command for the closest available file:
25 // - points are awarded if the filename matches (ignoring extension)
26 // - points are awarded if the directory structure matches
27 // - ties are broken by length of path prefix match
29 // The compile command is adjusted, replacing the filename and removing output
30 // file arguments. The -x and -std flags may be affected too.
32 // Source language is a tricky issue: is it OK to use a .c file's command
33 // for building a .cc file? What language is a .h file in?
34 // - We only consider compile commands for c-family languages as candidates.
35 // - For files whose language is implied by the filename (e.g. .m, .hpp)
36 // we prefer candidates from the same language.
37 // If we must cross languages, we drop any -x and -std flags.
38 // - For .h files, candidates from any c-family language are acceptable.
39 // We use the candidate's language, inserting e.g. -x c++-header.
41 // This class is only useful when wrapping databases that can enumerate all
42 // their compile commands. If getAllFilenames() is empty, no inference occurs.
44 //===----------------------------------------------------------------------===//
46 #include "clang/Driver/Options.h"
47 #include "clang/Driver/Types.h"
48 #include "clang/Frontend/LangStandard.h"
49 #include "clang/Tooling/CompilationDatabase.h"
50 #include "llvm/ADT/DenseMap.h"
51 #include "llvm/ADT/StringExtras.h"
52 #include "llvm/ADT/StringSwitch.h"
53 #include "llvm/Option/ArgList.h"
54 #include "llvm/Option/OptTable.h"
55 #include "llvm/Support/Debug.h"
56 #include "llvm/Support/Path.h"
57 #include "llvm/Support/StringSaver.h"
58 #include "llvm/Support/raw_ostream.h"
65 namespace types = clang::driver::types;
66 namespace path = llvm::sys::path;
68 // The length of the prefix these two strings have in common.
69 size_t matchingPrefix(StringRef L, StringRef R) {
70 size_t Limit = std::min(L.size(), R.size());
71 for (size_t I = 0; I < Limit; ++I)
77 // A comparator for searching SubstringWithIndexes with std::equal_range etc.
78 // Optionaly prefix semantics: compares equal if the key is a prefix.
79 template <bool Prefix> struct Less {
80 bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const {
81 StringRef V = Prefix ? Value.first.substr(0, Key.size()) : Value.first;
84 bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const {
85 StringRef V = Prefix ? Value.first.substr(0, Key.size()) : Value.first;
90 // Infer type from filename. If we might have gotten it wrong, set *Certain.
91 // *.h will be inferred as a C header, but not certain.
92 types::ID guessType(StringRef Filename, bool *Certain = nullptr) {
93 // path::extension is ".cpp", lookupTypeForExtension wants "cpp".
95 types::lookupTypeForExtension(path::extension(Filename).substr(1));
97 *Certain = Lang != types::TY_CHeader && Lang != types::TY_INVALID;
101 // Return Lang as one of the canonical supported types.
102 // e.g. c-header --> c; fortran --> TY_INVALID
103 static types::ID foldType(types::ID Lang) {
106 case types::TY_CHeader:
109 case types::TY_ObjCHeader:
110 return types::TY_ObjC;
112 case types::TY_CXXHeader:
113 return types::TY_CXX;
114 case types::TY_ObjCXX:
115 case types::TY_ObjCXXHeader:
116 return types::TY_ObjCXX;
118 return types::TY_INVALID;
122 // A CompileCommand that can be applied to another file.
123 struct TransferableCommand {
124 // Flags that should not apply to all files are stripped from CommandLine.
126 // Language detected from -x or the filename.
127 types::ID Type = types::TY_INVALID;
128 // Standard specified by -std.
129 LangStandard::Kind Std = LangStandard::lang_unspecified;
131 TransferableCommand(CompileCommand C)
132 : Cmd(std::move(C)), Type(guessType(Cmd.Filename)) {
133 std::vector<std::string> NewArgs = {Cmd.CommandLine.front()};
134 // Parse the old args in order to strip out and record unwanted flags.
135 auto OptTable = clang::driver::createDriverOptTable();
136 std::vector<const char *> Argv;
137 for (unsigned I = 1; I < Cmd.CommandLine.size(); ++I)
138 Argv.push_back(Cmd.CommandLine[I].c_str());
139 unsigned MissingI, MissingC;
140 auto ArgList = OptTable->ParseArgs(Argv, MissingI, MissingC);
141 for (const auto *Arg : ArgList) {
142 const auto &option = Arg->getOption();
143 // Strip input and output files.
144 if (option.matches(clang::driver::options::OPT_INPUT) ||
145 option.matches(clang::driver::options::OPT_o)) {
148 // Strip -x, but record the overridden language.
149 if (option.matches(clang::driver::options::OPT_x)) {
150 for (const char *Value : Arg->getValues())
151 Type = types::lookupTypeForTypeSpecifier(Value);
154 // Strip --std, but record the value.
155 if (option.matches(clang::driver::options::OPT_std_EQ)) {
156 for (const char *Value : Arg->getValues()) {
157 Std = llvm::StringSwitch<LangStandard::Kind>(Value)
158 #define LANGSTANDARD(id, name, lang, desc, features) \
159 .Case(name, LangStandard::lang_##id)
160 #define LANGSTANDARD_ALIAS(id, alias) .Case(alias, LangStandard::lang_##id)
161 #include "clang/Frontend/LangStandards.def"
166 llvm::opt::ArgStringList ArgStrs;
167 Arg->render(ArgList, ArgStrs);
168 NewArgs.insert(NewArgs.end(), ArgStrs.begin(), ArgStrs.end());
170 Cmd.CommandLine = std::move(NewArgs);
172 if (Std != LangStandard::lang_unspecified) // -std take precedence over -x
173 Type = toType(LangStandard::getLangStandardForKind(Std).getLanguage());
174 Type = foldType(Type);
177 // Produce a CompileCommand for \p filename, based on this one.
178 CompileCommand transferTo(StringRef Filename) const {
179 CompileCommand Result = Cmd;
180 Result.Filename = Filename;
182 auto TargetType = guessType(Filename, &TypeCertain);
183 // If the filename doesn't determine the language (.h), transfer with -x.
185 TargetType = types::onlyPrecompileType(TargetType) // header?
186 ? types::lookupHeaderTypeForSourceType(Type)
188 Result.CommandLine.push_back("-x");
189 Result.CommandLine.push_back(types::getTypeName(TargetType));
191 // --std flag may only be transferred if the language is the same.
192 // We may consider "translating" these, e.g. c++11 -> c11.
193 if (Std != LangStandard::lang_unspecified && foldType(TargetType) == Type) {
194 Result.CommandLine.push_back(
196 std::string(LangStandard::getLangStandardForKind(Std).getName()));
198 Result.CommandLine.push_back(Filename);
203 // Map the language from the --std flag to that of the -x flag.
204 static types::ID toType(InputKind::Language Lang) {
209 return types::TY_CXX;
210 case InputKind::ObjC:
211 return types::TY_ObjC;
212 case InputKind::ObjCXX:
213 return types::TY_ObjCXX;
215 return types::TY_INVALID;
220 // CommandIndex does the real work: given a filename, it produces the best
221 // matching TransferableCommand by matching filenames. Basic strategy:
222 // - Build indexes of each of the substrings we want to look up by.
223 // These indexes are just sorted lists of the substrings.
224 // - Forward requests to the inner CDB. If it fails, we must pick a proxy.
225 // - Each criterion corresponds to a range lookup into the index, so we only
226 // need O(log N) string comparisons to determine scores.
227 // - We then break ties among the candidates with the highest score.
230 CommandIndex(std::vector<TransferableCommand> AllCommands)
231 : Commands(std::move(AllCommands)), Strings(Arena) {
232 // Sort commands by filename for determinism (index is a tiebreaker later).
234 Commands.begin(), Commands.end(),
235 [](const TransferableCommand &Left, const TransferableCommand &Right) {
236 return Left.Cmd.Filename < Right.Cmd.Filename;
238 for (size_t I = 0; I < Commands.size(); ++I) {
240 Strings.save(StringRef(Commands[I].Cmd.Filename).lower());
241 Paths.push_back({Path, I});
242 Stems.emplace_back(sys::path::stem(Path), I);
243 auto Dir = ++sys::path::rbegin(Path), DirEnd = sys::path::rend(Path);
244 for (int J = 0; J < DirectorySegmentsIndexed && Dir != DirEnd; ++J, ++Dir)
245 if (Dir->size() > ShortDirectorySegment) // not trivial ones
246 Components.emplace_back(*Dir, I);
248 llvm::sort(Paths.begin(), Paths.end());
249 llvm::sort(Stems.begin(), Stems.end());
250 llvm::sort(Components.begin(), Components.end());
253 bool empty() const { return Commands.empty(); }
255 // Returns the command that best fits OriginalFilename.
256 // Candidates with PreferLanguage will be chosen over others (unless it's
257 // TY_INVALID, or all candidates are bad).
258 const TransferableCommand &chooseProxy(StringRef OriginalFilename,
259 types::ID PreferLanguage) const {
260 assert(!empty() && "need at least one candidate!");
261 std::string Filename = OriginalFilename.lower();
262 auto Candidates = scoreCandidates(Filename);
263 std::pair<size_t, int> Best =
264 pickWinner(Candidates, Filename, PreferLanguage);
266 DEBUG_WITH_TYPE("interpolate",
268 << "interpolate: chose "
269 << Commands[Best.first].Cmd.Filename << " as proxy for "
270 << OriginalFilename << " preferring "
271 << (PreferLanguage == types::TY_INVALID
273 : types::getTypeName(PreferLanguage))
274 << " score=" << Best.second << "\n");
275 return Commands[Best.first];
279 using SubstringAndIndex = std::pair<StringRef, size_t>;
280 // Directory matching parameters: we look at the last two segments of the
281 // parent directory (usually the semantically significant ones in practice).
282 // We search only the last four of each candidate (for efficiency).
283 constexpr static int DirectorySegmentsIndexed = 4;
284 constexpr static int DirectorySegmentsQueried = 2;
285 constexpr static int ShortDirectorySegment = 1; // Only look at longer names.
287 // Award points to candidate entries that should be considered for the file.
288 // Returned keys are indexes into paths, and the values are (nonzero) scores.
289 DenseMap<size_t, int> scoreCandidates(StringRef Filename) const {
290 // Decompose Filename into the parts we care about.
291 // /some/path/complicated/project/Interesting.h
292 // [-prefix--][---dir---] [-dir-] [--stem---]
293 StringRef Stem = sys::path::stem(Filename);
294 llvm::SmallVector<StringRef, DirectorySegmentsQueried> Dirs;
295 llvm::StringRef Prefix;
296 auto Dir = ++sys::path::rbegin(Filename),
297 DirEnd = sys::path::rend(Filename);
298 for (int I = 0; I < DirectorySegmentsQueried && Dir != DirEnd; ++I, ++Dir) {
299 if (Dir->size() > ShortDirectorySegment)
300 Dirs.push_back(*Dir);
301 Prefix = Filename.substr(0, Dir - DirEnd);
304 // Now award points based on lookups into our various indexes.
305 DenseMap<size_t, int> Candidates; // Index -> score.
306 auto Award = [&](int Points, ArrayRef<SubstringAndIndex> Range) {
307 for (const auto &Entry : Range)
308 Candidates[Entry.second] += Points;
310 // Award one point if the file's basename is a prefix of the candidate,
311 // and another if it's an exact match (so exact matches get two points).
312 Award(1, indexLookup</*Prefix=*/true>(Stem, Stems));
313 Award(1, indexLookup</*Prefix=*/false>(Stem, Stems));
314 // For each of the last few directories in the Filename, award a point
315 // if it's present in the candidate.
316 for (StringRef Dir : Dirs)
317 Award(1, indexLookup</*Prefix=*/false>(Dir, Components));
318 // Award one more point if the whole rest of the path matches.
319 if (sys::path::root_directory(Prefix) != Prefix)
320 Award(1, indexLookup</*Prefix=*/true>(Prefix, Paths));
324 // Pick a single winner from the set of scored candidates.
325 // Returns (index, score).
326 std::pair<size_t, int> pickWinner(const DenseMap<size_t, int> &Candidates,
328 types::ID PreferredLanguage) const {
329 struct ScoredCandidate {
335 // Choose the best candidate by (preferred, points, prefix length, alpha).
336 ScoredCandidate Best = {size_t(-1), false, 0, 0};
337 for (const auto &Candidate : Candidates) {
339 S.Index = Candidate.first;
340 S.Preferred = PreferredLanguage == types::TY_INVALID ||
341 PreferredLanguage == Commands[S.Index].Type;
342 S.Points = Candidate.second;
343 if (!S.Preferred && Best.Preferred)
345 if (S.Preferred == Best.Preferred) {
346 if (S.Points < Best.Points)
348 if (S.Points == Best.Points) {
349 S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first);
350 if (S.PrefixLength < Best.PrefixLength)
352 // hidden heuristics should at least be deterministic!
353 if (S.PrefixLength == Best.PrefixLength)
354 if (S.Index > Best.Index)
358 // PrefixLength was only set above if actually needed for a tiebreak.
359 // But it definitely needs to be set to break ties in the future.
360 S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first);
363 // Edge case: no candidate got any points.
364 // We ignore PreferredLanguage at this point (not ideal).
365 if (Best.Index == size_t(-1))
366 return {longestMatch(Filename, Paths).second, 0};
367 return {Best.Index, Best.Points};
370 // Returns the range within a sorted index that compares equal to Key.
371 // If Prefix is true, it's instead the range starting with Key.
372 template <bool Prefix>
373 ArrayRef<SubstringAndIndex>
374 indexLookup(StringRef Key, const std::vector<SubstringAndIndex> &Idx) const {
375 // Use pointers as iteratiors to ease conversion of result to ArrayRef.
376 auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key,
378 return {Range.first, Range.second};
381 // Performs a point lookup into a nonempty index, returning a longest match.
383 longestMatch(StringRef Key, const std::vector<SubstringAndIndex> &Idx) const {
384 assert(!Idx.empty());
385 // Longest substring match will be adjacent to a direct lookup.
387 std::lower_bound(Idx.begin(), Idx.end(), SubstringAndIndex{Key, 0});
388 if (It == Idx.begin())
392 // Have to choose between It and It-1
393 size_t Prefix = matchingPrefix(Key, It->first);
394 size_t PrevPrefix = matchingPrefix(Key, (It - 1)->first);
395 return Prefix > PrevPrefix ? *It : *--It;
398 std::vector<TransferableCommand> Commands; // Indexes point into this.
399 BumpPtrAllocator Arena;
401 // Indexes of candidates by certain substrings.
402 // String is lowercase and sorted, index points into OriginalPaths.
403 std::vector<SubstringAndIndex> Paths; // Full path.
404 std::vector<SubstringAndIndex> Stems; // Basename, without extension.
405 std::vector<SubstringAndIndex> Components; // Last path components.
408 // The actual CompilationDatabase wrapper delegates to its inner database.
409 // If no match, looks up a command in CommandIndex and transfers it to the file.
410 class InterpolatingCompilationDatabase : public CompilationDatabase {
412 InterpolatingCompilationDatabase(std::unique_ptr<CompilationDatabase> Inner)
413 : Inner(std::move(Inner)), Index(allCommands()) {}
415 std::vector<CompileCommand>
416 getCompileCommands(StringRef Filename) const override {
417 auto Known = Inner->getCompileCommands(Filename);
418 if (Index.empty() || !Known.empty())
421 auto Lang = guessType(Filename, &TypeCertain);
423 Lang = types::TY_INVALID;
424 return {Index.chooseProxy(Filename, foldType(Lang)).transferTo(Filename)};
427 std::vector<std::string> getAllFiles() const override {
428 return Inner->getAllFiles();
431 std::vector<CompileCommand> getAllCompileCommands() const override {
432 return Inner->getAllCompileCommands();
436 std::vector<TransferableCommand> allCommands() {
437 std::vector<TransferableCommand> Result;
438 for (auto Command : Inner->getAllCompileCommands()) {
439 Result.emplace_back(std::move(Command));
440 if (Result.back().Type == types::TY_INVALID)
446 std::unique_ptr<CompilationDatabase> Inner;
452 std::unique_ptr<CompilationDatabase>
453 inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) {
454 return llvm::make_unique<InterpolatingCompilationDatabase>(std::move(Inner));
457 } // namespace tooling