Clang Project

clang_source_code/lib/Tooling/InterpolatingCompilationDatabase.cpp
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/Driver/Options.h"
46#include "clang/Driver/Types.h"
47#include "clang/Frontend/LangStandard.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
61namespace clang {
62namespace tooling {
63namespace {
64using namespace llvm;
65namespace types = clang::driver::types;
66namespace path = llvm::sys::path;
67
68// The length of the prefix these two strings have in common.
69size_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.
79template <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.
92types::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
103static 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  default:
118    return types::TY_INVALID;
119  }
120}
121
122// A CompileCommand that can be applied to another file.
123struct TransferableCommand {
124  // Flags that should not apply to all files are stripped from CommandLine.
125  CompileCommand Cmd;
126  // Language detected from -x or the filename. Never TY_INVALID.
127  Optional<types::ID> Type;
128  // Standard specified by -std.
129  LangStandard::Kind Std = LangStandard::lang_unspecified;
130  // Whether the command line is for the cl-compatible driver.
131  bool ClangCLMode;
132
133  TransferableCommand(CompileCommand C)
134      : Cmd(std::move(C)), Type(guessType(Cmd.Filename)),
135        ClangCLMode(checkIsCLMode(Cmd.CommandLine)) {
136    std::vector<std::string> OldArgs = std::move(Cmd.CommandLine);
137    Cmd.CommandLine.clear();
138
139    // Wrap the old arguments in an InputArgList.
140    llvm::opt::InputArgList ArgList;
141    {
142      SmallVector<const char *, 16> TmpArgv;
143      for (const std::string &S : OldArgs)
144        TmpArgv.push_back(S.c_str());
145      ArgList = {TmpArgv.begin(), TmpArgv.end()};
146    }
147
148    // Parse the old args in order to strip out and record unwanted flags.
149    // We parse each argument individually so that we can retain the exact
150    // spelling of each argument; re-rendering is lossy for aliased flags.
151    // E.g. in CL mode, /W4 maps to -Wall.
152    auto OptTable = clang::driver::createDriverOptTable();
153    Cmd.CommandLine.emplace_back(OldArgs.front());
154    for (unsigned Pos = 1; Pos < OldArgs.size();) {
155      using namespace driver::options;
156
157      const unsigned OldPos = Pos;
158      std::unique_ptr<llvm::opt::Arg> Arg(OptTable->ParseOneArg(
159          ArgList, Pos,
160          /* Include */ClangCLMode ? CoreOption | CLOption : 0,
161          /* Exclude */ClangCLMode ? 0 : CLOption));
162
163      if (!Arg)
164        continue;
165
166      const llvm::opt::Option &Opt = Arg->getOption();
167
168      // Strip input and output files.
169      if (Opt.matches(OPT_INPUT) || Opt.matches(OPT_o) ||
170          (ClangCLMode && (Opt.matches(OPT__SLASH_Fa) ||
171                           Opt.matches(OPT__SLASH_Fe) ||
172                           Opt.matches(OPT__SLASH_Fi) ||
173                           Opt.matches(OPT__SLASH_Fo))))
174        continue;
175
176      // Strip -x, but record the overridden language.
177      if (const auto GivenType = tryParseTypeArg(*Arg)) {
178        Type = *GivenType;
179        continue;
180      }
181
182      // Strip -std, but record the value.
183      if (const auto GivenStd = tryParseStdArg(*Arg)) {
184        if (*GivenStd != LangStandard::lang_unspecified)
185          Std = *GivenStd;
186        continue;
187      }
188
189      Cmd.CommandLine.insert(Cmd.CommandLine.end(),
190                             OldArgs.data() + OldPos, OldArgs.data() + Pos);
191    }
192
193    if (Std != LangStandard::lang_unspecified) // -std take precedence over -x
194      Type = toType(LangStandard::getLangStandardForKind(Std).getLanguage());
195    Type = foldType(*Type);
196    // The contract is to store None instead of TY_INVALID.
197    if (Type == types::TY_INVALID)
198      Type = llvm::None;
199  }
200
201  // Produce a CompileCommand for \p filename, based on this one.
202  CompileCommand transferTo(StringRef Filename) const {
203    CompileCommand Result = Cmd;
204    Result.Filename = Filename;
205    bool TypeCertain;
206    auto TargetType = guessType(Filename, &TypeCertain);
207    // If the filename doesn't determine the language (.h), transfer with -x.
208    if (TargetType != types::TY_INVALID && !TypeCertain && Type) {
209      TargetType = types::onlyPrecompileType(TargetType) // header?
210                       ? types::lookupHeaderTypeForSourceType(*Type)
211                       : *Type;
212      if (ClangCLMode) {
213        const StringRef Flag = toCLFlag(TargetType);
214        if (!Flag.empty())
215          Result.CommandLine.push_back(Flag);
216      } else {
217        Result.CommandLine.push_back("-x");
218        Result.CommandLine.push_back(types::getTypeName(TargetType));
219      }
220    }
221    // --std flag may only be transferred if the language is the same.
222    // We may consider "translating" these, e.g. c++11 -> c11.
223    if (Std != LangStandard::lang_unspecified && foldType(TargetType) == Type) {
224      Result.CommandLine.emplace_back((
225          llvm::Twine(ClangCLMode ? "/std:" : "-std=") +
226          LangStandard::getLangStandardForKind(Std).getName()).str());
227    }
228    Result.CommandLine.push_back(Filename);
229    return Result;
230  }
231
232private:
233  // Determine whether the given command line is intended for the CL driver.
234  static bool checkIsCLMode(ArrayRef<std::string> CmdLine) {
235    // First look for --driver-mode.
236    for (StringRef S : llvm::reverse(CmdLine)) {
237      if (S.consume_front("--driver-mode="))
238        return S == "cl";
239    }
240
241    // Otherwise just check the clang executable file name.
242    return llvm::sys::path::stem(CmdLine.front()).endswith_lower("cl");
243  }
244
245  // Map the language from the --std flag to that of the -x flag.
246  static types::ID toType(InputKind::Language Lang) {
247    switch (Lang) {
248    case InputKind::C:
249      return types::TY_C;
250    case InputKind::CXX:
251      return types::TY_CXX;
252    case InputKind::ObjC:
253      return types::TY_ObjC;
254    case InputKind::ObjCXX:
255      return types::TY_ObjCXX;
256    default:
257      return types::TY_INVALID;
258    }
259  }
260
261  // Convert a file type to the matching CL-style type flag.
262  static StringRef toCLFlag(types::ID Type) {
263    switch (Type) {
264    case types::TY_C:
265    case types::TY_CHeader:
266      return "/TC";
267    case types::TY_CXX:
268    case types::TY_CXXHeader:
269      return "/TP";
270    default:
271      return StringRef();
272    }
273  }
274
275  // Try to interpret the argument as a type specifier, e.g. '-x'.
276  Optional<types::ID> tryParseTypeArg(const llvm::opt::Arg &Arg) {
277    const llvm::opt::Option &Opt = Arg.getOption();
278    using namespace driver::options;
279    if (ClangCLMode) {
280      if (Opt.matches(OPT__SLASH_TC) || Opt.matches(OPT__SLASH_Tc))
281        return types::TY_C;
282      if (Opt.matches(OPT__SLASH_TP) || Opt.matches(OPT__SLASH_Tp))
283        return types::TY_CXX;
284    } else {
285      if (Opt.matches(driver::options::OPT_x))
286        return types::lookupTypeForTypeSpecifier(Arg.getValue());
287    }
288    return None;
289  }
290
291  // Try to interpret the argument as '-std='.
292  Optional<LangStandard::Kind> tryParseStdArg(const llvm::opt::Arg &Arg) {
293    using namespace driver::options;
294    if (Arg.getOption().matches(ClangCLMode ? OPT__SLASH_std : OPT_std_EQ)) {
295      return llvm::StringSwitch<LangStandard::Kind>(Arg.getValue())
296#define LANGSTANDARD(id, name, lang, ...) .Case(name, LangStandard::lang_##id)
297#define LANGSTANDARD_ALIAS(id, alias) .Case(alias, LangStandard::lang_##id)
298#include "clang/Frontend/LangStandards.def"
299#undef LANGSTANDARD_ALIAS
300#undef LANGSTANDARD
301                 .Default(LangStandard::lang_unspecified);
302    }
303    return None;
304  }
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.
318class FileIndex {
319public:
320  FileIndex(std::vector<std::string> Files)
321      : OriginalPaths(std::move(Files)), Strings(Arena) {
322    // Sort commands by filename for determinism (index is a tiebreaker later).
323    llvm::sort(OriginalPaths);
324    Paths.reserve(OriginalPaths.size());
325    Types.reserve(OriginalPaths.size());
326    Stems.reserve(OriginalPaths.size());
327    for (size_t I = 0; I < OriginalPaths.size(); ++I) {
328      StringRef Path = Strings.save(StringRef(OriginalPaths[I]).lower());
329
330      Paths.emplace_back(Path, I);
331      Types.push_back(foldType(guessType(Path)));
332      Stems.emplace_back(sys::path::stem(Path), I);
333      auto Dir = ++sys::path::rbegin(Path), DirEnd = sys::path::rend(Path);
334      for (int J = 0; J < DirectorySegmentsIndexed && Dir != DirEnd; ++J, ++Dir)
335        if (Dir->size() > ShortDirectorySegment) // not trivial ones
336          Components.emplace_back(*Dir, I);
337    }
338    llvm::sort(Paths);
339    llvm::sort(Stems);
340    llvm::sort(Components);
341  }
342
343  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                        types::ID PreferLanguage) const {
350     (0) . __assert_fail ("!empty() && \"need at least one candidate!\"", "/home/seafit/code_projects/clang_source/clang/lib/Tooling/InterpolatingCompilationDatabase.cpp", 350, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!empty() && "need at least one candidate!");
351    std::string Filename = OriginalFilename.lower();
352    auto Candidates = scoreCandidates(Filename);
353    std::pair<size_t, int> Best =
354        pickWinner(Candidates, Filename, PreferLanguage);
355
356    DEBUG_WITH_TYPE(
357        "interpolate",
358        llvm::dbgs() << "interpolate: chose " << OriginalPaths[Best.first]
359                     << " as proxy for " << OriginalFilename << " preferring "
360                     << (PreferLanguage == types::TY_INVALID
361                             ? "none"
362                             : types::getTypeName(PreferLanguage))
363                     << " score=" << Best.second << "\n");
364    return OriginalPaths[Best.first];
365  }
366
367private:
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  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    StringRef Stem = sys::path::stem(Filename);
383    llvm::SmallVector<StringRef, DirectorySegmentsQueried> Dirs;
384    llvm::StringRef Prefix;
385    auto Dir = ++sys::path::rbegin(Filename),
386         DirEnd = sys::path::rend(Filename);
387    for (int I = 0; I < DirectorySegmentsQueried && Dir != DirEnd; ++I, ++Dir) {
388      if (Dir->size() > ShortDirectorySegment)
389        Dirs.push_back(*Dir);
390      Prefix = Filename.substr(0, Dir - DirEnd);
391    }
392
393    // Now award points based on lookups into our various indexes.
394    DenseMap<size_t, int> Candidates; // Index -> score.
395    auto Award = [&](int Points, ArrayRef<SubstringAndIndex> Range) {
396      for (const auto &Entry : Range)
397        Candidates[Entry.second] += Points;
398    };
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    Award(1, indexLookup</*Prefix=*/true>(Stem, Stems));
402    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    for (StringRef Dir : Dirs)
406      Award(1, indexLookup</*Prefix=*/false>(Dir, Components));
407    // Award one more point if the whole rest of the path matches.
408    if (sys::path::root_directory(Prefix) != Prefix)
409      Award(1, indexLookup</*Prefix=*/true>(Prefix, Paths));
410    return Candidates;
411  }
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                                    types::ID PreferredLanguage) const {
418    struct ScoredCandidate {
419      size_t Index;
420      bool Preferred;
421      int Points;
422      size_t PrefixLength;
423    };
424    // Choose the best candidate by (preferred, points, prefix length, alpha).
425    ScoredCandidate Best = {size_t(-1), false, 0, 0};
426    for (const auto &Candidate : Candidates) {
427      ScoredCandidate S;
428      S.Index = Candidate.first;
429      S.Preferred = PreferredLanguage == types::TY_INVALID ||
430                    PreferredLanguage == Types[S.Index];
431      S.Points = Candidate.second;
432      if (!S.Preferred && Best.Preferred)
433        continue;
434      if (S.Preferred == Best.Preferred) {
435        if (S.Points < Best.Points)
436          continue;
437        if (S.Points == Best.Points) {
438          S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first);
439          if (S.PrefixLength < Best.PrefixLength)
440            continue;
441          // hidden heuristics should at least be deterministic!
442          if (S.PrefixLength == Best.PrefixLength)
443            if (S.Index > Best.Index)
444              continue;
445        }
446      }
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      S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first);
450      Best = S;
451    }
452    // Edge case: no candidate got any points.
453    // We ignore PreferredLanguage at this point (not ideal).
454    if (Best.Index == size_t(-1))
455      return {longestMatch(Filename, Paths).second, 0};
456    return {Best.Index, Best.Points};
457  }
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  indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const {
464    // Use pointers as iteratiors to ease conversion of result to ArrayRef.
465    auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key,
466                                  Less<Prefix>());
467    return {Range.first, Range.second};
468  }
469
470  // Performs a point lookup into a nonempty index, returning a longest match.
471  SubstringAndIndex longestMatch(StringRef Key,
472                                 ArrayRef<SubstringAndIndex> Idx) const {
473    assert(!Idx.empty());
474    // Longest substring match will be adjacent to a direct lookup.
475    auto It =
476        std::lower_bound(Idx.begin(), Idx.end(), SubstringAndIndex{Key, 0});
477    if (It == Idx.begin())
478      return *It;
479    if (It == Idx.end())
480      return *--It;
481    // Have to choose between It and It-1
482    size_t Prefix = matchingPrefix(Key, It->first);
483    size_t PrevPrefix = matchingPrefix(Key, (It - 1)->first);
484    return Prefix > PrevPrefix ? *It : *--It;
485  }
486
487  // Original paths, everything else is in lowercase.
488  std::vector<std::string> OriginalPaths;
489  BumpPtrAllocator Arena;
490  StringSaver Strings;
491  // Indexes of candidates by certain substrings.
492  // String is lowercase and sorted, index points into OriginalPaths.
493  std::vector<SubstringAndIndex> Paths;      // Full path.
494  // Lang types obtained by guessing on the corresponding path. I-th element is
495  // a type for the I-th path.
496  std::vector<types::ID> Types;
497  std::vector<SubstringAndIndex> Stems;      // Basename, without extension.
498  std::vector<SubstringAndIndex> Components; // Last path components.
499};
500
501// The actual CompilationDatabase wrapper delegates to its inner database.
502// If no match, looks up a proxy file in FileIndex and transfers its
503// command to the requested file.
504class InterpolatingCompilationDatabase : public CompilationDatabase {
505public:
506  InterpolatingCompilationDatabase(std::unique_ptr<CompilationDatabase> Inner)
507      : Inner(std::move(Inner)), Index(this->Inner->getAllFiles()) {}
508
509  std::vector<CompileCommand>
510  getCompileCommands(StringRef Filename) const override {
511    auto Known = Inner->getCompileCommands(Filename);
512    if (Index.empty() || !Known.empty())
513      return Known;
514    bool TypeCertain;
515    auto Lang = guessType(Filename, &TypeCertain);
516    if (!TypeCertain)
517      Lang = types::TY_INVALID;
518    auto ProxyCommands =
519        Inner->getCompileCommands(Index.chooseProxy(Filename, foldType(Lang)));
520    if (ProxyCommands.empty())
521      return {};
522    return {TransferableCommand(ProxyCommands[0]).transferTo(Filename)};
523  }
524
525  std::vector<std::string> getAllFiles() const override {
526    return Inner->getAllFiles();
527  }
528
529  std::vector<CompileCommand> getAllCompileCommands() const override {
530    return Inner->getAllCompileCommands();
531  }
532
533private:
534  std::unique_ptr<CompilationDatabase> Inner;
535  FileIndex Index;
536};
537
538} // namespace
539
540std::unique_ptr<CompilationDatabase>
541inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) {
542  return llvm::make_unique<InterpolatingCompilationDatabase>(std::move(Inner));
543}
544
545} // namespace tooling
546} // namespace clang
547
CodeThinker, Enjoy your reading code