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/Optional.h" 53 #include "llvm/ADT/StringExtras.h" 54 #include "llvm/ADT/StringSwitch.h" 55 #include "llvm/Option/ArgList.h" 56 #include "llvm/Option/OptTable.h" 57 #include "llvm/Support/Debug.h" 58 #include "llvm/Support/Path.h" 59 #include "llvm/Support/StringSaver.h" 60 #include "llvm/Support/raw_ostream.h" 61 #include <memory> 62 63 namespace clang { 64 namespace tooling { 65 namespace { 66 using namespace llvm; 67 namespace types = clang::driver::types; 68 namespace path = llvm::sys::path; 69 70 // The length of the prefix these two strings have in common. 71 size_t matchingPrefix(StringRef L, StringRef R) { 72 size_t Limit = std::min(L.size(), R.size()); 73 for (size_t I = 0; I < Limit; ++I) 74 if (L[I] != R[I]) 75 return I; 76 return Limit; 77 } 78 79 // A comparator for searching SubstringWithIndexes with std::equal_range etc. 80 // Optionaly prefix semantics: compares equal if the key is a prefix. 81 template <bool Prefix> struct Less { 82 bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const { 83 StringRef V = Prefix ? Value.first.substr(0, Key.size()) : Value.first; 84 return Key < V; 85 } 86 bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const { 87 StringRef V = Prefix ? Value.first.substr(0, Key.size()) : Value.first; 88 return V < Key; 89 } 90 }; 91 92 // Infer type from filename. If we might have gotten it wrong, set *Certain. 93 // *.h will be inferred as a C header, but not certain. 94 types::ID guessType(StringRef Filename, bool *Certain = nullptr) { 95 // path::extension is ".cpp", lookupTypeForExtension wants "cpp". 96 auto Lang = 97 types::lookupTypeForExtension(path::extension(Filename).substr(1)); 98 if (Certain) 99 *Certain = Lang != types::TY_CHeader && Lang != types::TY_INVALID; 100 return Lang; 101 } 102 103 // Return Lang as one of the canonical supported types. 104 // e.g. c-header --> c; fortran --> TY_INVALID 105 static types::ID foldType(types::ID Lang) { 106 switch (Lang) { 107 case types::TY_C: 108 case types::TY_CHeader: 109 return types::TY_C; 110 case types::TY_ObjC: 111 case types::TY_ObjCHeader: 112 return types::TY_ObjC; 113 case types::TY_CXX: 114 case types::TY_CXXHeader: 115 return types::TY_CXX; 116 case types::TY_ObjCXX: 117 case types::TY_ObjCXXHeader: 118 return types::TY_ObjCXX; 119 case types::TY_CUDA: 120 case types::TY_CUDA_DEVICE: 121 return types::TY_CUDA; 122 default: 123 return types::TY_INVALID; 124 } 125 } 126 127 // A CompileCommand that can be applied to another file. 128 struct TransferableCommand { 129 // Flags that should not apply to all files are stripped from CommandLine. 130 CompileCommand Cmd; 131 // Language detected from -x or the filename. Never TY_INVALID. 132 Optional<types::ID> Type; 133 // Standard specified by -std. 134 LangStandard::Kind Std = LangStandard::lang_unspecified; 135 // Whether the command line is for the cl-compatible driver. 136 bool ClangCLMode; 137 138 TransferableCommand(CompileCommand C) 139 : Cmd(std::move(C)), Type(guessType(Cmd.Filename)) { 140 std::vector<std::string> OldArgs = std::move(Cmd.CommandLine); 141 Cmd.CommandLine.clear(); 142 143 // Wrap the old arguments in an InputArgList. 144 llvm::opt::InputArgList ArgList; 145 { 146 SmallVector<const char *, 16> TmpArgv; 147 for (const std::string &S : OldArgs) 148 TmpArgv.push_back(S.c_str()); 149 ClangCLMode = !TmpArgv.empty() && 150 driver::IsClangCL(driver::getDriverMode( 151 TmpArgv.front(), llvm::makeArrayRef(TmpArgv).slice(1))); 152 ArgList = {TmpArgv.begin(), TmpArgv.end()}; 153 } 154 155 // Parse the old args in order to strip out and record unwanted flags. 156 // We parse each argument individually so that we can retain the exact 157 // spelling of each argument; re-rendering is lossy for aliased flags. 158 // E.g. in CL mode, /W4 maps to -Wall. 159 auto &OptTable = clang::driver::getDriverOptTable(); 160 if (!OldArgs.empty()) 161 Cmd.CommandLine.emplace_back(OldArgs.front()); 162 for (unsigned Pos = 1; Pos < OldArgs.size();) { 163 using namespace driver::options; 164 165 const unsigned OldPos = Pos; 166 std::unique_ptr<llvm::opt::Arg> Arg(OptTable.ParseOneArg( 167 ArgList, Pos, 168 /* Include */ ClangCLMode ? CoreOption | CLOption | CLDXCOption : 0, 169 /* Exclude */ ClangCLMode ? 0 : CLOption | CLDXCOption)); 170 171 if (!Arg) 172 continue; 173 174 const llvm::opt::Option &Opt = Arg->getOption(); 175 176 // Strip input and output files. 177 if (Opt.matches(OPT_INPUT) || Opt.matches(OPT_o) || 178 (ClangCLMode && (Opt.matches(OPT__SLASH_Fa) || 179 Opt.matches(OPT__SLASH_Fe) || 180 Opt.matches(OPT__SLASH_Fi) || 181 Opt.matches(OPT__SLASH_Fo)))) 182 continue; 183 184 // ...including when the inputs are passed after --. 185 if (Opt.matches(OPT__DASH_DASH)) 186 break; 187 188 // Strip -x, but record the overridden language. 189 if (const auto GivenType = tryParseTypeArg(*Arg)) { 190 Type = *GivenType; 191 continue; 192 } 193 194 // Strip -std, but record the value. 195 if (const auto GivenStd = tryParseStdArg(*Arg)) { 196 if (*GivenStd != LangStandard::lang_unspecified) 197 Std = *GivenStd; 198 continue; 199 } 200 201 Cmd.CommandLine.insert(Cmd.CommandLine.end(), 202 OldArgs.data() + OldPos, OldArgs.data() + Pos); 203 } 204 205 // Make use of -std iff -x was missing. 206 if (Type == types::TY_INVALID && Std != LangStandard::lang_unspecified) 207 Type = toType(LangStandard::getLangStandardForKind(Std).getLanguage()); 208 Type = foldType(*Type); 209 // The contract is to store None instead of TY_INVALID. 210 if (Type == types::TY_INVALID) 211 Type = llvm::None; 212 } 213 214 // Produce a CompileCommand for \p filename, based on this one. 215 // (This consumes the TransferableCommand just to avoid copying Cmd). 216 CompileCommand transferTo(StringRef Filename) && { 217 CompileCommand Result = std::move(Cmd); 218 Result.Heuristic = "inferred from " + Result.Filename; 219 Result.Filename = std::string(Filename); 220 bool TypeCertain; 221 auto TargetType = guessType(Filename, &TypeCertain); 222 // If the filename doesn't determine the language (.h), transfer with -x. 223 if ((!TargetType || !TypeCertain) && Type) { 224 // Use *Type, or its header variant if the file is a header. 225 // Treat no/invalid extension as header (e.g. C++ standard library). 226 TargetType = 227 (!TargetType || types::onlyPrecompileType(TargetType)) // header? 228 ? types::lookupHeaderTypeForSourceType(*Type) 229 : *Type; 230 if (ClangCLMode) { 231 const StringRef Flag = toCLFlag(TargetType); 232 if (!Flag.empty()) 233 Result.CommandLine.push_back(std::string(Flag)); 234 } else { 235 Result.CommandLine.push_back("-x"); 236 Result.CommandLine.push_back(types::getTypeName(TargetType)); 237 } 238 } 239 // --std flag may only be transferred if the language is the same. 240 // We may consider "translating" these, e.g. c++11 -> c11. 241 if (Std != LangStandard::lang_unspecified && foldType(TargetType) == Type) { 242 Result.CommandLine.emplace_back(( 243 llvm::Twine(ClangCLMode ? "/std:" : "-std=") + 244 LangStandard::getLangStandardForKind(Std).getName()).str()); 245 } 246 Result.CommandLine.push_back("--"); 247 Result.CommandLine.push_back(std::string(Filename)); 248 return Result; 249 } 250 251 private: 252 // Map the language from the --std flag to that of the -x flag. 253 static types::ID toType(Language Lang) { 254 switch (Lang) { 255 case Language::C: 256 return types::TY_C; 257 case Language::CXX: 258 return types::TY_CXX; 259 case Language::ObjC: 260 return types::TY_ObjC; 261 case Language::ObjCXX: 262 return types::TY_ObjCXX; 263 default: 264 return types::TY_INVALID; 265 } 266 } 267 268 // Convert a file type to the matching CL-style type flag. 269 static StringRef toCLFlag(types::ID Type) { 270 switch (Type) { 271 case types::TY_C: 272 case types::TY_CHeader: 273 return "/TC"; 274 case types::TY_CXX: 275 case types::TY_CXXHeader: 276 return "/TP"; 277 default: 278 return StringRef(); 279 } 280 } 281 282 // Try to interpret the argument as a type specifier, e.g. '-x'. 283 Optional<types::ID> tryParseTypeArg(const llvm::opt::Arg &Arg) { 284 const llvm::opt::Option &Opt = Arg.getOption(); 285 using namespace driver::options; 286 if (ClangCLMode) { 287 if (Opt.matches(OPT__SLASH_TC) || Opt.matches(OPT__SLASH_Tc)) 288 return types::TY_C; 289 if (Opt.matches(OPT__SLASH_TP) || Opt.matches(OPT__SLASH_Tp)) 290 return types::TY_CXX; 291 } else { 292 if (Opt.matches(driver::options::OPT_x)) 293 return types::lookupTypeForTypeSpecifier(Arg.getValue()); 294 } 295 return None; 296 } 297 298 // Try to interpret the argument as '-std='. 299 Optional<LangStandard::Kind> tryParseStdArg(const llvm::opt::Arg &Arg) { 300 using namespace driver::options; 301 if (Arg.getOption().matches(ClangCLMode ? OPT__SLASH_std : OPT_std_EQ)) 302 return LangStandard::getLangKind(Arg.getValue()); 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. 318 class FileIndex { 319 public: 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(OriginalPaths[I]))); 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 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 367 private: 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 = llvm::lower_bound(Idx, SubstringAndIndex{Key, 0}); 476 if (It == Idx.begin()) 477 return *It; 478 if (It == Idx.end()) 479 return *--It; 480 // Have to choose between It and It-1 481 size_t Prefix = matchingPrefix(Key, It->first); 482 size_t PrevPrefix = matchingPrefix(Key, (It - 1)->first); 483 return Prefix > PrevPrefix ? *It : *--It; 484 } 485 486 // Original paths, everything else is in lowercase. 487 std::vector<std::string> OriginalPaths; 488 BumpPtrAllocator Arena; 489 StringSaver Strings; 490 // Indexes of candidates by certain substrings. 491 // String is lowercase and sorted, index points into OriginalPaths. 492 std::vector<SubstringAndIndex> Paths; // Full path. 493 // Lang types obtained by guessing on the corresponding path. I-th element is 494 // a type for the I-th path. 495 std::vector<types::ID> Types; 496 std::vector<SubstringAndIndex> Stems; // Basename, without extension. 497 std::vector<SubstringAndIndex> Components; // Last path components. 498 }; 499 500 // The actual CompilationDatabase wrapper delegates to its inner database. 501 // If no match, looks up a proxy file in FileIndex and transfers its 502 // command to the requested file. 503 class InterpolatingCompilationDatabase : public CompilationDatabase { 504 public: 505 InterpolatingCompilationDatabase(std::unique_ptr<CompilationDatabase> Inner) 506 : Inner(std::move(Inner)), Index(this->Inner->getAllFiles()) {} 507 508 std::vector<CompileCommand> 509 getCompileCommands(StringRef Filename) const override { 510 auto Known = Inner->getCompileCommands(Filename); 511 if (Index.empty() || !Known.empty()) 512 return Known; 513 bool TypeCertain; 514 auto Lang = guessType(Filename, &TypeCertain); 515 if (!TypeCertain) 516 Lang = types::TY_INVALID; 517 auto ProxyCommands = 518 Inner->getCompileCommands(Index.chooseProxy(Filename, foldType(Lang))); 519 if (ProxyCommands.empty()) 520 return {}; 521 return {transferCompileCommand(std::move(ProxyCommands.front()), Filename)}; 522 } 523 524 std::vector<std::string> getAllFiles() const override { 525 return Inner->getAllFiles(); 526 } 527 528 std::vector<CompileCommand> getAllCompileCommands() const override { 529 return Inner->getAllCompileCommands(); 530 } 531 532 private: 533 std::unique_ptr<CompilationDatabase> Inner; 534 FileIndex Index; 535 }; 536 537 } // namespace 538 539 std::unique_ptr<CompilationDatabase> 540 inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) { 541 return std::make_unique<InterpolatingCompilationDatabase>(std::move(Inner)); 542 } 543 544 tooling::CompileCommand transferCompileCommand(CompileCommand Cmd, 545 StringRef Filename) { 546 return TransferableCommand(std::move(Cmd)).transferTo(Filename); 547 } 548 549 } // namespace tooling 550 } // namespace clang 551