Coverage Report

Created: 2020-02-15 09:57

/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/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
61
namespace clang {
62
namespace tooling {
63
namespace {
64
using namespace llvm;
65
namespace types = clang::driver::types;
66
namespace path = llvm::sys::path;
67
68
// The length of the prefix these two strings have in common.
69
43
size_t matchingPrefix(StringRef L, StringRef R) {
70
43
  size_t Limit = std::min(L.size(), R.size());
71
2.29k
  for (size_t I = 0; I < Limit; 
++I2.24k
)
72
2.28k
    if (L[I] != R[I])
73
42
      return I;
74
43
  
return Limit1
;
75
43
}
76
77
// A comparator for searching SubstringWithIndexes with std::equal_range etc.
78
// Optionaly prefix semantics: compares equal if the key is a prefix.
79
template <bool Prefix> struct Less {
80
146
  bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const {
81
146
    StringRef V = Prefix ? 
Value.first.substr(0, Key.size())62
:
Value.first84
;
82
146
    return Key < V;
83
146
  }
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<true>::operator()(llvm::StringRef, std::__1::pair<llvm::StringRef, unsigned long>) const
Line
Count
Source
80
62
  bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const {
81
62
    StringRef V = Prefix ? Value.first.substr(0, Key.size()) : 
Value.first0
;
82
62
    return Key < V;
83
62
  }
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<false>::operator()(llvm::StringRef, std::__1::pair<llvm::StringRef, unsigned long>) const
Line
Count
Source
80
84
  bool operator()(StringRef Key, std::pair<StringRef, size_t> Value) const {
81
84
    StringRef V = Prefix ? 
Value.first.substr(0, Key.size())0
: Value.first;
82
84
    return Key < V;
83
84
  }
84
206
  bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const {
85
206
    StringRef V = Prefix ? 
Value.first.substr(0, Key.size())82
:
Value.first124
;
86
206
    return V < Key;
87
206
  }
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<true>::operator()(std::__1::pair<llvm::StringRef, unsigned long>, llvm::StringRef) const
Line
Count
Source
84
82
  bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const {
85
82
    StringRef V = Prefix ? Value.first.substr(0, Key.size()) : 
Value.first0
;
86
82
    return V < Key;
87
82
  }
InterpolatingCompilationDatabase.cpp:clang::tooling::(anonymous namespace)::Less<false>::operator()(std::__1::pair<llvm::StringRef, unsigned long>, llvm::StringRef) const
Line
Count
Source
84
124
  bool operator()(std::pair<StringRef, size_t> Value, StringRef Key) const {
85
124
    StringRef V = Prefix ? 
Value.first.substr(0, Key.size())0
: Value.first;
86
124
    return V < Key;
87
124
  }
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.
92
14.0k
types::ID guessType(StringRef Filename, bool *Certain = nullptr) {
93
14.0k
  // path::extension is ".cpp", lookupTypeForExtension wants "cpp".
94
14.0k
  auto Lang =
95
14.0k
      types::lookupTypeForExtension(path::extension(Filename).substr(1));
96
14.0k
  if (Certain)
97
42
    *Certain = Lang != types::TY_CHeader && 
Lang != types::TY_INVALID28
;
98
14.0k
  return Lang;
99
14.0k
}
100
101
// Return Lang as one of the canonical supported types.
102
// e.g. c-header --> c; fortran --> TY_INVALID
103
14.0k
static types::ID foldType(types::ID Lang) {
104
14.0k
  switch (Lang) {
105
71
  case types::TY_C:
106
71
  case types::TY_CHeader:
107
71
    return types::TY_C;
108
71
  case types::TY_ObjC:
109
0
  case types::TY_ObjCHeader:
110
0
    return types::TY_ObjC;
111
13.9k
  case types::TY_CXX:
112
13.9k
  case types::TY_CXXHeader:
113
13.9k
    return types::TY_CXX;
114
13.9k
  case types::TY_ObjCXX:
115
14
  case types::TY_ObjCXXHeader:
116
14
    return types::TY_ObjCXX;
117
17
  default:
118
17
    return types::TY_INVALID;
119
14.0k
  }
120
14.0k
}
121
122
// A CompileCommand that can be applied to another file.
123
struct TransferableCommand {
124
  // Flags that should not apply to all files are stripped from CommandLine.
125
  CompileCommand Cmd;
126
  // Language detected from -x or the filename. Never TY_INVALID.
127
  Optional<types::ID> Type;
128
  // Standard specified by -std.
129
  LangStandard::Kind Std = LangStandard::lang_unspecified;
130
  // Whether the command line is for the cl-compatible driver.
131
  bool ClangCLMode;
132
133
  TransferableCommand(CompileCommand C)
134
      : Cmd(std::move(C)), Type(guessType(Cmd.Filename)),
135
21
        ClangCLMode(checkIsCLMode(Cmd.CommandLine)) {
136
21
    std::vector<std::string> OldArgs = std::move(Cmd.CommandLine);
137
21
    Cmd.CommandLine.clear();
138
21
139
21
    // Wrap the old arguments in an InputArgList.
140
21
    llvm::opt::InputArgList ArgList;
141
21
    {
142
21
      SmallVector<const char *, 16> TmpArgv;
143
21
      for (const std::string &S : OldArgs)
144
101
        TmpArgv.push_back(S.c_str());
145
21
      ArgList = {TmpArgv.begin(), TmpArgv.end()};
146
21
    }
147
21
148
21
    // Parse the old args in order to strip out and record unwanted flags.
149
21
    // We parse each argument individually so that we can retain the exact
150
21
    // spelling of each argument; re-rendering is lossy for aliased flags.
151
21
    // E.g. in CL mode, /W4 maps to -Wall.
152
21
    auto &OptTable = clang::driver::getDriverOptTable();
153
21
    if (!OldArgs.empty())
154
21
      Cmd.CommandLine.emplace_back(OldArgs.front());
155
78
    for (unsigned Pos = 1; Pos < OldArgs.size();) {
156
57
      using namespace driver::options;
157
57
158
57
      const unsigned OldPos = Pos;
159
57
      std::unique_ptr<llvm::opt::Arg> Arg(OptTable.ParseOneArg(
160
57
          ArgList, Pos,
161
57
          /* Include */ ClangCLMode ? 
CoreOption | CLOption6
:
051
,
162
57
          /* Exclude */ ClangCLMode ? 
06
:
CLOption51
));
163
57
164
57
      if (!Arg)
165
0
        continue;
166
57
167
57
      const llvm::opt::Option &Opt = Arg->getOption();
168
57
169
57
      // Strip input and output files.
170
57
      if (Opt.matches(OPT_INPUT) || 
Opt.matches(OPT_o)36
||
171
57
          
(35
ClangCLMode35
&&
(4
Opt.matches(OPT__SLASH_Fa)4
||
172
4
                           Opt.matches(OPT__SLASH_Fe) ||
173
4
                           Opt.matches(OPT__SLASH_Fi) ||
174
4
                           Opt.matches(OPT__SLASH_Fo))))
175
22
        continue;
176
35
177
35
      // Strip -x, but record the overridden language.
178
35
      if (const auto GivenType = tryParseTypeArg(*Arg)) {
179
2
        Type = *GivenType;
180
2
        continue;
181
2
      }
182
33
183
33
      // Strip -std, but record the value.
184
33
      if (const auto GivenStd = tryParseStdArg(*Arg)) {
185
6
        if (*GivenStd != LangStandard::lang_unspecified)
186
6
          Std = *GivenStd;
187
6
        continue;
188
6
      }
189
27
190
27
      Cmd.CommandLine.insert(Cmd.CommandLine.end(),
191
27
                             OldArgs.data() + OldPos, OldArgs.data() + Pos);
192
27
    }
193
21
194
21
    // Make use of -std iff -x was missing.
195
21
    if (Type == types::TY_INVALID && 
Std != LangStandard::lang_unspecified0
)
196
0
      Type = toType(LangStandard::getLangStandardForKind(Std).getLanguage());
197
21
    Type = foldType(*Type);
198
21
    // The contract is to store None instead of TY_INVALID.
199
21
    if (Type == types::TY_INVALID)
200
0
      Type = llvm::None;
201
21
  }
202
203
  // Produce a CompileCommand for \p filename, based on this one.
204
21
  CompileCommand transferTo(StringRef Filename) const {
205
21
    CompileCommand Result = Cmd;
206
21
    Result.Filename = std::string(Filename);
207
21
    bool TypeCertain;
208
21
    auto TargetType = guessType(Filename, &TypeCertain);
209
21
    // If the filename doesn't determine the language (.h), transfer with -x.
210
21
    if ((!TargetType || 
!TypeCertain19
) &&
Type9
) {
211
9
      // Use *Type, or its header variant if the file is a header.
212
9
      // Treat no/invalid extension as header (e.g. C++ standard library).
213
9
      TargetType =
214
9
          (!TargetType || 
types::onlyPrecompileType(TargetType)7
) // header?
215
9
              ? types::lookupHeaderTypeForSourceType(*Type)
216
9
              : 
*Type0
;
217
9
      if (ClangCLMode) {
218
2
        const StringRef Flag = toCLFlag(TargetType);
219
2
        if (!Flag.empty())
220
2
          Result.CommandLine.push_back(std::string(Flag));
221
7
      } else {
222
7
        Result.CommandLine.push_back("-x");
223
7
        Result.CommandLine.push_back(types::getTypeName(TargetType));
224
7
      }
225
9
    }
226
21
    // --std flag may only be transferred if the language is the same.
227
21
    // We may consider "translating" these, e.g. c++11 -> c11.
228
21
    if (Std != LangStandard::lang_unspecified && 
foldType(TargetType) == Type6
) {
229
5
      Result.CommandLine.emplace_back((
230
5
          llvm::Twine(ClangCLMode ? 
"/std:"0
: "-std=") +
231
5
          LangStandard::getLangStandardForKind(Std).getName()).str());
232
5
    }
233
21
    Result.CommandLine.push_back(std::string(Filename));
234
21
    Result.Heuristic = "inferred from " + Cmd.Filename;
235
21
    return Result;
236
21
  }
237
238
private:
239
  // Determine whether the given command line is intended for the CL driver.
240
21
  static bool checkIsCLMode(ArrayRef<std::string> CmdLine) {
241
21
    // First look for --driver-mode.
242
93
    for (StringRef S : llvm::reverse(CmdLine)) {
243
93
      if (S.consume_front("--driver-mode="))
244
2
        return S == "cl";
245
93
    }
246
21
247
21
    // Otherwise just check the clang executable file name.
248
21
    
return 19
!CmdLine.empty()19
&&
249
19
           llvm::sys::path::stem(CmdLine.front()).endswith_lower("cl");
250
21
  }
251
252
  // Map the language from the --std flag to that of the -x flag.
253
0
  static types::ID toType(Language Lang) {
254
0
    switch (Lang) {
255
0
    case Language::C:
256
0
      return types::TY_C;
257
0
    case Language::CXX:
258
0
      return types::TY_CXX;
259
0
    case Language::ObjC:
260
0
      return types::TY_ObjC;
261
0
    case Language::ObjCXX:
262
0
      return types::TY_ObjCXX;
263
0
    default:
264
0
      return types::TY_INVALID;
265
0
    }
266
0
  }
267
268
  // Convert a file type to the matching CL-style type flag.
269
2
  static StringRef toCLFlag(types::ID Type) {
270
2
    switch (Type) {
271
0
    case types::TY_C:
272
0
    case types::TY_CHeader:
273
0
      return "/TC";
274
2
    case types::TY_CXX:
275
2
    case types::TY_CXXHeader:
276
2
      return "/TP";
277
2
    default:
278
0
      return StringRef();
279
2
    }
280
2
  }
281
282
  // Try to interpret the argument as a type specifier, e.g. '-x'.
283
35
  Optional<types::ID> tryParseTypeArg(const llvm::opt::Arg &Arg) {
284
35
    const llvm::opt::Option &Opt = Arg.getOption();
285
35
    using namespace driver::options;
286
35
    if (ClangCLMode) {
287
4
      if (Opt.matches(OPT__SLASH_TC) || Opt.matches(OPT__SLASH_Tc))
288
0
        return types::TY_C;
289
4
      if (Opt.matches(OPT__SLASH_TP) || Opt.matches(OPT__SLASH_Tp))
290
0
        return types::TY_CXX;
291
31
    } else {
292
31
      if (Opt.matches(driver::options::OPT_x))
293
2
        return types::lookupTypeForTypeSpecifier(Arg.getValue());
294
33
    }
295
33
    return None;
296
33
  }
297
298
  // Try to interpret the argument as '-std='.
299
33
  Optional<LangStandard::Kind> tryParseStdArg(const llvm::opt::Arg &Arg) {
300
33
    using namespace driver::options;
301
33
    if (Arg.getOption().matches(ClangCLMode ? 
OPT__SLASH_std4
:
OPT_std_EQ29
))
302
6
      return LangStandard::getLangKind(Arg.getValue());
303
27
    return None;
304
27
  }
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
39
      : OriginalPaths(std::move(Files)), Strings(Arena) {
322
39
    // Sort commands by filename for determinism (index is a tiebreaker later).
323
39
    llvm::sort(OriginalPaths);
324
39
    Paths.reserve(OriginalPaths.size());
325
39
    Types.reserve(OriginalPaths.size());
326
39
    Stems.reserve(OriginalPaths.size());
327
14.0k
    for (size_t I = 0; I < OriginalPaths.size(); 
++I14.0k
) {
328
14.0k
      StringRef Path = Strings.save(StringRef(OriginalPaths[I]).lower());
329
14.0k
330
14.0k
      Paths.emplace_back(Path, I);
331
14.0k
      Types.push_back(foldType(guessType(Path)));
332
14.0k
      Stems.emplace_back(sys::path::stem(Path), I);
333
14.0k
      auto Dir = ++sys::path::rbegin(Path), DirEnd = sys::path::rend(Path);
334
70.1k
      for (int J = 0; J < DirectorySegmentsIndexed && 
Dir != DirEnd56.1k
;
++J, ++Dir56.1k
)
335
56.1k
        if (Dir->size() > ShortDirectorySegment) // not trivial ones
336
56.0k
          Components.emplace_back(*Dir, I);
337
14.0k
    }
338
39
    llvm::sort(Paths);
339
39
    llvm::sort(Stems);
340
39
    llvm::sort(Components);
341
39
  }
342
343
56
  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
21
                        types::ID PreferLanguage) const {
350
21
    assert(!empty() && "need at least one candidate!");
351
21
    std::string Filename = OriginalFilename.lower();
352
21
    auto Candidates = scoreCandidates(Filename);
353
21
    std::pair<size_t, int> Best =
354
21
        pickWinner(Candidates, Filename, PreferLanguage);
355
21
356
21
    DEBUG_WITH_TYPE(
357
21
        "interpolate",
358
21
        llvm::dbgs() << "interpolate: chose " << OriginalPaths[Best.first]
359
21
                     << " as proxy for " << OriginalFilename << " preferring "
360
21
                     << (PreferLanguage == types::TY_INVALID
361
21
                             ? "none"
362
21
                             : types::getTypeName(PreferLanguage))
363
21
                     << " score=" << Best.second << "\n");
364
21
    return OriginalPaths[Best.first];
365
21
  }
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
21
  DenseMap<size_t, int> scoreCandidates(StringRef Filename) const {
379
21
    // Decompose Filename into the parts we care about.
380
21
    // /some/path/complicated/project/Interesting.h
381
21
    // [-prefix--][---dir---] [-dir-] [--stem---]
382
21
    StringRef Stem = sys::path::stem(Filename);
383
21
    llvm::SmallVector<StringRef, DirectorySegmentsQueried> Dirs;
384
21
    llvm::StringRef Prefix;
385
21
    auto Dir = ++sys::path::rbegin(Filename),
386
21
         DirEnd = sys::path::rend(Filename);
387
63
    for (int I = 0; I < DirectorySegmentsQueried && 
Dir != DirEnd42
;
++I, ++Dir42
) {
388
42
      if (Dir->size() > ShortDirectorySegment)
389
26
        Dirs.push_back(*Dir);
390
42
      Prefix = Filename.substr(0, Dir - DirEnd);
391
42
    }
392
21
393
21
    // Now award points based on lookups into our various indexes.
394
21
    DenseMap<size_t, int> Candidates; // Index -> score.
395
89
    auto Award = [&](int Points, ArrayRef<SubstringAndIndex> Range) {
396
89
      for (const auto &Entry : Range)
397
142
        Candidates[Entry.second] += Points;
398
89
    };
399
21
    // Award one point if the file's basename is a prefix of the candidate,
400
21
    // and another if it's an exact match (so exact matches get two points).
401
21
    Award(1, indexLookup</*Prefix=*/true>(Stem, Stems));
402
21
    Award(1, indexLookup</*Prefix=*/false>(Stem, Stems));
403
21
    // For each of the last few directories in the Filename, award a point
404
21
    // if it's present in the candidate.
405
21
    for (StringRef Dir : Dirs)
406
26
      Award(1, indexLookup</*Prefix=*/false>(Dir, Components));
407
21
    // Award one more point if the whole rest of the path matches.
408
21
    if (sys::path::root_directory(Prefix) != Prefix)
409
21
      Award(1, indexLookup</*Prefix=*/true>(Prefix, Paths));
410
21
    return Candidates;
411
21
  }
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
21
                                    types::ID PreferredLanguage) const {
418
21
    struct ScoredCandidate {
419
21
      size_t Index;
420
21
      bool Preferred;
421
21
      int Points;
422
21
      size_t PrefixLength;
423
21
    };
424
21
    // Choose the best candidate by (preferred, points, prefix length, alpha).
425
21
    ScoredCandidate Best = {size_t(-1), false, 0, 0};
426
55
    for (const auto &Candidate : Candidates) {
427
55
      ScoredCandidate S;
428
55
      S.Index = Candidate.first;
429
55
      S.Preferred = PreferredLanguage == types::TY_INVALID ||
430
55
                    
PreferredLanguage == Types[S.Index]28
;
431
55
      S.Points = Candidate.second;
432
55
      if (!S.Preferred && 
Best.Preferred8
)
433
3
        continue;
434
52
      if (S.Preferred == Best.Preferred) {
435
33
        if (S.Points < Best.Points)
436
12
          continue;
437
21
        if (S.Points == Best.Points) {
438
8
          S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first);
439
8
          if (S.PrefixLength < Best.PrefixLength)
440
0
            continue;
441
8
          // hidden heuristics should at least be deterministic!
442
8
          if (S.PrefixLength == Best.PrefixLength)
443
8
            if (S.Index > Best.Index)
444
7
              continue;
445
33
        }
446
21
      }
447
33
      // PrefixLength was only set above if actually needed for a tiebreak.
448
33
      // But it definitely needs to be set to break ties in the future.
449
33
      S.PrefixLength = matchingPrefix(Filename, Paths[S.Index].first);
450
33
      Best = S;
451
33
    }
452
21
    // Edge case: no candidate got any points.
453
21
    // We ignore PreferredLanguage at this point (not ideal).
454
21
    if (Best.Index == size_t(-1))
455
1
      return {longestMatch(Filename, Paths).second, 0};
456
20
    return {Best.Index, Best.Points};
457
20
  }
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
89
  indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const {
464
89
    // Use pointers as iteratiors to ease conversion of result to ArrayRef.
465
89
    auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key,
466
89
                                  Less<Prefix>());
467
89
    return {Range.first, Range.second};
468
89
  }
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
463
42
  indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const {
464
42
    // Use pointers as iteratiors to ease conversion of result to ArrayRef.
465
42
    auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key,
466
42
                                  Less<Prefix>());
467
42
    return {Range.first, Range.second};
468
42
  }
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
463
47
  indexLookup(StringRef Key, ArrayRef<SubstringAndIndex> Idx) const {
464
47
    // Use pointers as iteratiors to ease conversion of result to ArrayRef.
465
47
    auto Range = std::equal_range(Idx.data(), Idx.data() + Idx.size(), Key,
466
47
                                  Less<Prefix>());
467
47
    return {Range.first, Range.second};
468
47
  }
469
470
  // Performs a point lookup into a nonempty index, returning a longest match.
471
  SubstringAndIndex longestMatch(StringRef Key,
472
1
                                 ArrayRef<SubstringAndIndex> Idx) const {
473
1
    assert(!Idx.empty());
474
1
    // Longest substring match will be adjacent to a direct lookup.
475
1
    auto It = llvm::lower_bound(Idx, SubstringAndIndex{Key, 0});
476
1
    if (It == Idx.begin())
477
0
      return *It;
478
1
    if (It == Idx.end())
479
0
      return *--It;
480
1
    // Have to choose between It and It-1
481
1
    size_t Prefix = matchingPrefix(Key, It->first);
482
1
    size_t PrevPrefix = matchingPrefix(Key, (It - 1)->first);
483
1
    return Prefix > PrevPrefix ? 
*It0
: *--It;
484
1
  }
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
39
      : Inner(std::move(Inner)), Index(this->Inner->getAllFiles()) {}
507
508
  std::vector<CompileCommand>
509
35
  getCompileCommands(StringRef Filename) const override {
510
35
    auto Known = Inner->getCompileCommands(Filename);
511
35
    if (Index.empty() || !Known.empty())
512
14
      return Known;
513
21
    bool TypeCertain;
514
21
    auto Lang = guessType(Filename, &TypeCertain);
515
21
    if (!TypeCertain)
516
9
      Lang = types::TY_INVALID;
517
21
    auto ProxyCommands =
518
21
        Inner->getCompileCommands(Index.chooseProxy(Filename, foldType(Lang)));
519
21
    if (ProxyCommands.empty())
520
0
      return {};
521
21
    return {TransferableCommand(ProxyCommands[0]).transferTo(Filename)};
522
21
  }
523
524
0
  std::vector<std::string> getAllFiles() const override {
525
0
    return Inner->getAllFiles();
526
0
  }
527
528
1
  std::vector<CompileCommand> getAllCompileCommands() const override {
529
1
    return Inner->getAllCompileCommands();
530
1
  }
531
532
private:
533
  std::unique_ptr<CompilationDatabase> Inner;
534
  FileIndex Index;
535
};
536
537
} // namespace
538
539
std::unique_ptr<CompilationDatabase>
540
39
inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) {
541
39
  return std::make_unique<InterpolatingCompilationDatabase>(std::move(Inner));
542
39
}
543
544
} // namespace tooling
545
} // namespace clang