| 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 |
|
| 62 |
namespace clang { |
| 63 |
namespace tooling { |
| 64 |
namespace { |
| 65 |
using namespace llvm; |
| 66 |
namespace types = clang::driver::types; |
| 67 |
namespace path = llvm::sys::path; |
| 68 |
|
| 69 |
// The length of the prefix these two strings have in common. |
| 70 |
size_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. |
| 80 |
template <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. |
| 93 |
types::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 |
| 104 |
static 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. |
| 127 |
struct 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 |
|
| 250 |
private: |
| 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. |
| 317 |
class FileIndex { |
| 318 |
public: |
| 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 |
|
| 366 |
private: |
| 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. |
| 502 |
class InterpolatingCompilationDatabase : public CompilationDatabase { |
| 503 |
public: |
| 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 |
|
| 531 |
private: |
| 532 |
std::unique_ptr<CompilationDatabase> Inner; |
| 533 |
FileIndex Index; |
| 534 |
}; |
| 535 |
|
| 536 |
} // namespace |
| 537 |
|
| 538 |
std::unique_ptr<CompilationDatabase> |
| 539 |
inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) { |
| 540 |
return std::make_unique<InterpolatingCompilationDatabase>(std::move(Inner)); |
| 541 |
} |
| 542 |
|
| 543 |
tooling::CompileCommand transferCompileCommand(CompileCommand Cmd, |
| 544 |
StringRef Filename) { |
| 545 |
return TransferableCommand(std::move(Cmd)).transferTo(Filename); |
| 546 |
} |
| 547 |
|
| 548 |
} // namespace tooling |
| 549 |
} // namespace clang |