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