Coverage Report

Created: 2021-09-21 08:58

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Tooling/InterpolatingCompilationDatabase.cpp
Line
Count
Source (jump to first uncovered line)
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
45
size_t matchingPrefix(StringRef L, StringRef R) {
72
45
  size_t Limit = std::min(L.size(), R.size());
73
2.24k
  for (size_t I = 0; I < Limit; 
++I2.19k
)
74
2.23k
    if (L[I] != R[I])
75
44
      return I;
76
1
  return Limit;
77
45
}
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
155
  bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const {
83
155
    StringRef V = Prefix ? 
Value.first.substr(0, Key.size())64
:
Value.first91
;
84
155
    return Key < V;
85
155
  }
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<true>::operator()(llvm::StringRef, std::__1::pair<llvm::StringRef, unsigned long>) const
Line
Count
Source
82
64
  bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const {
83
64
    StringRef V = Prefix ? Value.first.substr(0, Key.size()) : 
Value.first0
;
84
64
    return Key < V;
85
64
  }
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<false>::operator()(llvm::StringRef, std::__1::pair<llvm::StringRef, unsigned long>) const
Line
Count
Source
82
91
  bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const {
83
91
    StringRef V = Prefix ? 
Value.first.substr(0, Key.size())0
: Value.first;
84
91
    return Key < V;
85
91
  }
86
211
  bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const {
87
211
    StringRef V = Prefix ? 
Value.first.substr(0, Key.size())83
:
Value.first128
;
88
211
    return V < Key;
89
211
  }
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<true>::operator()(std::__1::pair<llvm::StringRef, unsigned long>, llvm::StringRef) const
Line
Count
Source
86
83
  bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const {
87
83
    StringRef V = Prefix ? Value.first.substr(0, Key.size()) : 
Value.first0
;
88
83
    return V < Key;
89
83
  }
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<false>::operator()(std::__1::pair<llvm::StringRef, unsigned long>, llvm::StringRef) const
Line
Count
Source
86
128
  bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const {
87
128
    StringRef V = Prefix ? 
Value.first.substr(0, Key.size())0
: Value.first;
88
128
    return V < Key;
89
128
  }
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
15.6k
types::ID guessType(StringRef Filename, bool *Certain = nullptr) {
95
  // path::extension is ".cpp", lookupTypeForExtension wants "cpp".
96
15.6k
  auto Lang =
97
15.6k
      types::lookupTypeForExtension(path::extension(Filename).substr(1));
98
15.6k
  if (Certain)
99
49
    *Certain = Lang != types::TY_CHeader && 
Lang != types::TY_INVALID34
;
100
15.6k
  return Lang;
101
15.6k
}
102
103
// Return Lang as one of the canonical supported types.
104
// e.g. c-header --> c; fortran --> TY_INVALID
105
15.6k
static types::ID foldType(types::ID Lang) {
106
15.6k
  switch (Lang) {
107
95
  case types::TY_C:
108
95
  case types::TY_CHeader:
109
95
    return types::TY_C;
110
0
  case types::TY_ObjC:
111
0
  case types::TY_ObjCHeader:
112
0
    return types::TY_ObjC;
113
15.4k
  case types::TY_CXX:
114
15.4k
  case types::TY_CXXHeader:
115
15.4k
    return types::TY_CXX;
116
13
  case types::TY_ObjCXX:
117
14
  case types::TY_ObjCXXHeader:
118
14
    return types::TY_ObjCXX;
119
0
  case types::TY_CUDA:
120
0
  case types::TY_CUDA_DEVICE:
121
0
    return types::TY_CUDA;
122
17
  default:
123
17
    return types::TY_INVALID;
124
15.6k
  }
125
15.6k
}
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
25
      : Cmd(std::move(C)), Type(guessType(Cmd.Filename)) {
140
25
    std::vector<std::string> OldArgs = std::move(Cmd.CommandLine);
141
25
    Cmd.CommandLine.clear();
142
143
    // Wrap the old arguments in an InputArgList.
144
25
    llvm::opt::InputArgList ArgList;
145
25
    {
146
25
      SmallVector<const char *, 16> TmpArgv;
147
25
      for (const std::string &S : OldArgs)
148
128
        TmpArgv.push_back(S.c_str());
149
25
      ClangCLMode = !TmpArgv.empty() &&
150
25
                    driver::IsClangCL(driver::getDriverMode(
151
25
                        TmpArgv.front(), llvm::makeArrayRef(TmpArgv).slice(1)));
152
25
      ArgList = {TmpArgv.begin(), TmpArgv.end()};
153
25
    }
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
25
    auto &OptTable = clang::driver::getDriverOptTable();
160
25
    if (!OldArgs.empty())
161
25
      Cmd.CommandLine.emplace_back(OldArgs.front());
162
98
    for (unsigned Pos = 1; Pos < OldArgs.size();) {
163
74
      using namespace driver::options;
164
165
74
      const unsigned OldPos = Pos;
166
74
      std::unique_ptr<llvm::opt::Arg> Arg(OptTable.ParseOneArg(
167
74
          ArgList, Pos,
168
74
          /* Include */ ClangCLMode ? 
CoreOption | CLOption10
:
064
,
169
74
          /* Exclude */ ClangCLMode ? 
010
:
CLOption64
));
170
171
74
      if (!Arg)
172
0
        continue;
173
174
74
      const llvm::opt::Option &Opt = Arg->getOption();
175
176
      // Strip input and output files.
177
74
      if (Opt.matches(OPT_INPUT) || 
Opt.matches(OPT_o)49
||
178
74
          
(46
ClangCLMode46
&&
(7
Opt.matches(OPT__SLASH_Fa)7
||
179
7
                           Opt.matches(OPT__SLASH_Fe) ||
180
7
                           Opt.matches(OPT__SLASH_Fi) ||
181
7
                           Opt.matches(OPT__SLASH_Fo))))
182
28
        continue;
183
184
      // ...including when the inputs are passed after --.
185
46
      if (Opt.matches(OPT__DASH_DASH))
186
1
        break;
187
188
      // Strip -x, but record the overridden language.
189
45
      if (const auto GivenType = tryParseTypeArg(*Arg)) {
190
2
        Type = *GivenType;
191
2
        continue;
192
2
      }
193
194
      // Strip -std, but record the value.
195
43
      if (const auto GivenStd = tryParseStdArg(*Arg)) {
196
9
        if (*GivenStd != LangStandard::lang_unspecified)
197
9
          Std = *GivenStd;
198
9
        continue;
199
9
      }
200
201
34
      Cmd.CommandLine.insert(Cmd.CommandLine.end(),
202
34
                             OldArgs.data() + OldPos, OldArgs.data() + Pos);
203
34
    }
204
205
    // Make use of -std iff -x was missing.
206
25
    if (Type == types::TY_INVALID && 
Std != LangStandard::lang_unspecified0
)
207
0
      Type = toType(LangStandard::getLangStandardForKind(Std).getLanguage());
208
25
    Type = foldType(*Type);
209
    // The contract is to store None instead of TY_INVALID.
210
25
    if (Type == types::TY_INVALID)
211
0
      Type = llvm::None;
212
25
  }
213
214
  // Produce a CompileCommand for \p filename, based on this one.
215
  // (This consumes the TransferableCommand just to avoid copying Cmd).
216
25
  CompileCommand transferTo(StringRef Filename) && {
217
25
    CompileCommand Result = std::move(Cmd);
218
25
    Result.Heuristic = "inferred from " + Result.Filename;
219
25
    Result.Filename = std::string(Filename);
220
25
    bool TypeCertain;
221
25
    auto TargetType = guessType(Filename, &TypeCertain);
222
    // If the filename doesn't determine the language (.h), transfer with -x.
223
25
    if ((!TargetType || 
!TypeCertain23
) &&
Type10
) {
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
10
      TargetType =
227
10
          (!TargetType || 
types::onlyPrecompileType(TargetType)8
) // header?
228
10
              ? types::lookupHeaderTypeForSourceType(*Type)
229
10
              : 
*Type0
;
230
10
      if (ClangCLMode) {
231
2
        const StringRef Flag = toCLFlag(TargetType);
232
2
        if (!Flag.empty())
233
2
          Result.CommandLine.push_back(std::string(Flag));
234
8
      } else {
235
8
        Result.CommandLine.push_back("-x");
236
8
        Result.CommandLine.push_back(types::getTypeName(TargetType));
237
8
      }
238
10
    }
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
25
    if (Std != LangStandard::lang_unspecified && 
foldType(TargetType) == Type9
) {
242
8
      Result.CommandLine.emplace_back((
243
8
          llvm::Twine(ClangCLMode ? 
"/std:"1
:
"-std="7
) +
244
8
          LangStandard::getLangStandardForKind(Std).getName()).str());
245
8
    }
246
25
    if (Filename.startswith("-") || 
(24
ClangCLMode24
&&
Filename.startswith("/")3
))
247
2
      Result.CommandLine.push_back("--");
248
25
    Result.CommandLine.push_back(std::string(Filename));
249
25
    return Result;
250
25
  }
251
252
private:
253
  // Map the language from the --std flag to that of the -x flag.
254
0
  static types::ID toType(Language Lang) {
255
0
    switch (Lang) {
256
0
    case Language::C:
257
0
      return types::TY_C;
258
0
    case Language::CXX:
259
0
      return types::TY_CXX;
260
0
    case Language::ObjC:
261
0
      return types::TY_ObjC;
262
0
    case Language::ObjCXX:
263
0
      return types::TY_ObjCXX;
264
0
    default:
265
0
      return types::TY_INVALID;
266
0
    }
267
0
  }
268
269
  // Convert a file type to the matching CL-style type flag.
270
2
  static StringRef toCLFlag(types::ID Type) {
271
2
    switch (Type) {
272
0
    case types::TY_C:
273
0
    case types::TY_CHeader:
274
0
      return "/TC";
275
0
    case types::TY_CXX:
276
2
    case types::TY_CXXHeader:
277
2
      return "/TP";
278
0
    default:
279
0
      return StringRef();
280
2
    }
281
2
  }
282
283
  // Try to interpret the argument as a type specifier, e.g. '-x'.
284
45
  Optional<types::ID> tryParseTypeArg(const llvm::opt::Arg &Arg) {
285
45
    const llvm::opt::Option &Opt = Arg.getOption();
286
45
    using namespace driver::options;
287
45
    if (ClangCLMode) {
288
7
      if (Opt.matches(OPT__SLASH_TC) || Opt.matches(OPT__SLASH_Tc))
289
0
        return types::TY_C;
290
7
      if (Opt.matches(OPT__SLASH_TP) || Opt.matches(OPT__SLASH_Tp))
291
0
        return types::TY_CXX;
292
38
    } else {
293
38
      if (Opt.matches(driver::options::OPT_x))
294
2
        return types::lookupTypeForTypeSpecifier(Arg.getValue());
295
38
    }
296
43
    return None;
297
45
  }
298
299
  // Try to interpret the argument as '-std='.
300
43
  Optional<LangStandard::Kind> tryParseStdArg(const llvm::opt::Arg &Arg) {
301
43
    using namespace driver::options;
302
43
    if (Arg.getOption().matches(ClangCLMode ? 
OPT__SLASH_std7
:
OPT_std_EQ36
))
303
9
      return LangStandard::getLangKind(Arg.getValue());
304
34
    return None;
305
43
  }
306
};
307
308
// Given a filename, FileIndex picks the best matching file from the underlying
309
// DB. This is the proxy file whose CompileCommand will be reused. The
310
// heuristics incorporate file name, extension, and directory structure.
311
// Strategy:
312
// - Build indexes of each of the substrings we want to look up by.
313
//   These indexes are just sorted lists of the substrings.
314
// - Each criterion corresponds to a range lookup into the index, so we only
315
//   need O(log N) string comparisons to determine scores.
316
//
317
// Apart from path proximity signals, also takes file extensions into account
318
// when scoring the candidates.
319
class FileIndex {
320
public:
321
  FileIndex(std::vector<std::string> Files)
322
42
      : OriginalPaths(std::move(Files)), Strings(Arena) {
323
    // Sort commands by filename for determinism (index is a tiebreaker later).
324
42
    llvm::sort(OriginalPaths);
325
42
    Paths.reserve(OriginalPaths.size());
326
42
    Types.reserve(OriginalPaths.size());
327
42
    Stems.reserve(OriginalPaths.size());
328
15.6k
    for (size_t I = 0; I < OriginalPaths.size(); 
++I15.5k
) {
329
15.5k
      StringRef Path = Strings.save(StringRef(OriginalPaths[I]).lower());
330
331
15.5k
      Paths.emplace_back(Path, I);
332
15.5k
      Types.push_back(foldType(guessType(Path)));
333
15.5k
      Stems.emplace_back(sys::path::stem(Path), I);
334
15.5k
      auto Dir = ++sys::path::rbegin(Path), DirEnd = sys::path::rend(Path);
335
77.8k
      for (int J = 0; J < DirectorySegmentsIndexed && 
Dir != DirEnd62.2k
;
++J, ++Dir62.2k
)
336
62.2k
        if (Dir->size() > ShortDirectorySegment) // not trivial ones
337
62.1k
          Components.emplace_back(*Dir, I);
338
15.5k
    }
339
42
    llvm::sort(Paths);
340
42
    llvm::sort(Stems);
341
42
    llvm::sort(Components);
342
42
  }
343
344
62
  bool empty() const { return Paths.empty(); }
345
346
  // Returns the path for the file that best fits OriginalFilename.
347
  // Candidates with extensions matching PreferLanguage will be chosen over
348
  // others (unless it's TY_INVALID, or all candidates are bad).
349
  StringRef chooseProxy(StringRef OriginalFilename,
350
24
                        types::ID PreferLanguage) const {
351
24
    assert(!empty() && "need at least one candidate!");
352
0
    std::string Filename = OriginalFilename.lower();
353
24
    auto Candidates = scoreCandidates(Filename);
354
24
    std::pair<size_t, int> Best =
355
24
        pickWinner(Candidates, Filename, PreferLanguage);
356
357
24
    DEBUG_WITH_TYPE(
358
24
        "interpolate",
359
24
        llvm::dbgs() << "interpolate: chose " << OriginalPaths[Best.first]
360
24
                     << " as proxy for " << OriginalFilename << " preferring "
361
24
                     << (PreferLanguage == types::TY_INVALID
362
24
                             ? "none"
363
24
                             : types::getTypeName(PreferLanguage))
364
24
                     << " score=" << Best.second << "\n");
365
24
    return OriginalPaths[Best.first];
366
24
  }
367
368
private:
369
  using SubstringAndIndex = std::pair<StringRef, size_t>;
370
  // Directory matching parameters: we look at the last two segments of the
371
  // parent directory (usually the semantically significant ones in practice).
372
  // We search only the last four of each candidate (for efficiency).
373
  constexpr static int DirectorySegmentsIndexed = 4;
374
  constexpr static int DirectorySegmentsQueried = 2;
375
  constexpr static int ShortDirectorySegment = 1; // Only look at longer names.
376
377
  // Award points to candidate entries that should be considered for the file.
378
  // Returned keys are indexes into paths, and the values are (nonzero) scores.
379
24
  DenseMap<size_t, int> scoreCandidates(StringRef Filename) const {
380
    // Decompose Filename into the parts we care about.
381
    // /some/path/complicated/project/Interesting.h
382
    // [-prefix--][---dir---] [-dir-] [--stem---]
383
24
    StringRef Stem = sys::path::stem(Filename);
384
24
    llvm::SmallVector<StringRef, DirectorySegmentsQueried> Dirs;
385
24
    llvm::StringRef Prefix;
386
24
    auto Dir = ++sys::path::rbegin(Filename),
387
24
         DirEnd = sys::path::rend(Filename);
388
67
    for (int I = 0; I < DirectorySegmentsQueried && 
Dir != DirEnd46
;
++I, ++Dir43
) {
389
43
      if (Dir->size() > ShortDirectorySegment)
390
27
        Dirs.push_back(*Dir);
391
43
      Prefix = Filename.substr(0, Dir - DirEnd);
392
43
    }
393
394
    // Now award points based on lookups into our various indexes.
395
24
    DenseMap<size_t, int> Candidates; // Index -> score.
396
95
    auto Award = [&](int Points, ArrayRef<SubstringAndIndex> Range) {
397
95
      for (const auto &Entry : Range)
398
139
        Candidates[Entry.second] += Points;
399
95
    };
400
    // Award one point if the file's basename is a prefix of the candidate,
401
    // and another if it's an exact match (so exact matches get two points).
402
24
    Award(1, indexLookup</*Prefix=*/true>(Stem, Stems));
403
24
    Award(1, indexLookup</*Prefix=*/false>(Stem, Stems));
404
    // For each of the last few directories in the Filename, award a point
405
    // if it's present in the candidate.
406
24
    for (StringRef Dir : Dirs)
407
27
      Award(1, indexLookup</*Prefix=*/false>(Dir, Components));
408
    // Award one more point if the whole rest of the path matches.
409
24
    if (sys::path::root_directory(Prefix) != Prefix)
410
20
      Award(1, indexLookup</*Prefix=*/true>(Prefix, Paths));
411
24
    return Candidates;
412
24
  }
413
414
  // Pick a single winner from the set of scored candidates.
415
  // Returns (index, score).
416
  std::pair<size_t, int> pickWinner(const DenseMap<size_t, int> &Candidates,
417
                                    StringRef Filename,
418
24
                                    types::ID PreferredLanguage) const {
419
24
    struct ScoredCandidate {
420
24
      size_t Index;
421
24
      bool Preferred;
422
24
      int Points;
423
24
      size_t PrefixLength;
424
24
    };
425
    // Choose the best candidate by (preferred, points, prefix length, alpha).
426
24
    ScoredCandidate Best = {size_t(-1), false, 0, 0};
427
56
    for (const auto &Candidate : Candidates) {
428
56
      ScoredCandidate S;
429
56
      S.Index = Candidate.first;
430
56
      S.Preferred = PreferredLanguage == types::TY_INVALID ||
431
56
                    
PreferredLanguage == Types[S.Index]30
;
432
56
      S.Points = Candidate.second;
433
56
      if (!S.Preferred && 
Best.Preferred8
)
434
3
        continue;
435
53
      if (S.Preferred == Best.Preferred) {
436
32
        if (S.Points < Best.Points)
437
11
          continue;
438
21
        if (S.Points == Best.Points) {
439
8
          S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first);
440
8
          if (S.PrefixLength < Best.PrefixLength)
441
0
            continue;
442
          // hidden heuristics should at least be deterministic!
443
8
          if (S.PrefixLength == Best.PrefixLength)
444
8
            if (S.Index > Best.Index)
445
7
              continue;
446
8
        }
447
21
      }
448
      // PrefixLength was only set above if actually needed for a tiebreak.
449
      // But it definitely needs to be set to break ties in the future.
450
35
      S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first);
451
35
      Best = S;
452
35
    }
453
    // Edge case: no candidate got any points.
454
    // We ignore PreferredLanguage at this point (not ideal).
455
24
    if (Best.Index == size_t(-1))
456
2
      return {longestMatch(Filename, Paths).second, 0};
457
22
    return {Best.Index, Best.Points};
458
24
  }
459
460
  // Returns the range within a sorted index that compares equal to Key.
461
  // If Prefix is true, it's instead the range starting with Key.
462
  template <bool Prefix>
463
  ArrayRef<SubstringAndIndex>
464
95
  indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const {
465
    // Use pointers as iteratiors to ease conversion of result to ArrayRef.
466
95
    auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key,
467
95
                                  Less<Prefix>());
468
95
    return {Range.first, Range.second};
469
95
  }
InterpolatingCompilationDatabase.cpp:llvm::ArrayRef<std::__1::pair<llvm::StringRef, unsigned long> > clang::tooling::(anonymous namespace)::FileIndex::indexLookup<true>(llvm::StringRef, llvm::ArrayRef<std::__1::pair<llvm::StringRef, unsigned long> >) const
Line
Count
Source
464
44
  indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const {
465
    // Use pointers as iteratiors to ease conversion of result to ArrayRef.
466
44
    auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key,
467
44
                                  Less<Prefix>());
468
44
    return {Range.first, Range.second};
469
44
  }
InterpolatingCompilationDatabase.cpp:llvm::ArrayRef<std::__1::pair<llvm::StringRef, unsigned long> > clang::tooling::(anonymous namespace)::FileIndex::indexLookup<false>(llvm::StringRef, llvm::ArrayRef<std::__1::pair<llvm::StringRef, unsigned long> >) const
Line
Count
Source
464
51
  indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const {
465
    // Use pointers as iteratiors to ease conversion of result to ArrayRef.
466
51
    auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key,
467
51
                                  Less<Prefix>());
468
51
    return {Range.first, Range.second};
469
51
  }
470
471
  // Performs a point lookup into a nonempty index, returning a longest match.
472
  SubstringAndIndex longestMatch(StringRef Key,
473
2
                                 ArrayRef<SubstringAndIndex> Idx) const {
474
2
    assert(!Idx.empty());
475
    // Longest substring match will be adjacent to a direct lookup.
476
0
    auto It = llvm::lower_bound(Idx, SubstringAndIndex{Key, 0});
477
2
    if (It == Idx.begin())
478
1
      return *It;
479
1
    if (It == Idx.end())
480
0
      return *--It;
481
    // Have to choose between It and It-1
482
1
    size_t Prefix = matchingPrefix(Key, It->first);
483
1
    size_t PrevPrefix = matchingPrefix(Key, (It - 1)->first);
484
1
    return Prefix > PrevPrefix ? 
*It0
: *--It;
485
1
  }
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.
504
class InterpolatingCompilationDatabase : public CompilationDatabase {
505
public:
506
  InterpolatingCompilationDatabase(std::unique_ptr<CompilationDatabase> Inner)
507
42
      : Inner(std::move(Inner)), Index(this->Inner->getAllFiles()) {}
508
509
  std::vector<CompileCommand>
510
38
  getCompileCommands(StringRef Filename) const override {
511
38
    auto Known = Inner->getCompileCommands(Filename);
512
38
    if (Index.empty() || !Known.empty())
513
14
      return Known;
514
24
    bool TypeCertain;
515
24
    auto Lang = guessType(Filename, &TypeCertain);
516
24
    if (!TypeCertain)
517
9
      Lang = types::TY_INVALID;
518
24
    auto ProxyCommands =
519
24
        Inner->getCompileCommands(Index.chooseProxy(Filename, foldType(Lang)));
520
24
    if (ProxyCommands.empty())
521
0
      return {};
522
24
    return {transferCompileCommand(std::move(ProxyCommands.front()), Filename)};
523
24
  }
524
525
0
  std::vector<std::string> getAllFiles() const override {
526
0
    return Inner->getAllFiles();
527
0
  }
528
529
1
  std::vector<CompileCommand> getAllCompileCommands() const override {
530
1
    return Inner->getAllCompileCommands();
531
1
  }
532
533
private:
534
  std::unique_ptr<CompilationDatabase> Inner;
535
  FileIndex Index;
536
};
537
538
} // namespace
539
540
std::unique_ptr<CompilationDatabase>
541
42
inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) {
542
42
  return std::make_unique<InterpolatingCompilationDatabase>(std::move(Inner));
543
42
}
544
545
tooling::CompileCommand transferCompileCommand(CompileCommand Cmd,
546
25
                                               StringRef Filename) {
547
25
  return TransferableCommand(std::move(Cmd)).transferTo(Filename);
548
25
}
549
550
} // namespace tooling
551
} // namespace clang