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