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