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