Coverage Report

Created: 2022-07-16 07:03

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Tooling/Inclusions/HeaderIncludes.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- HeaderIncludes.cpp - Insert/Delete #includes --*- 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
#include "clang/Tooling/Inclusions/HeaderIncludes.h"
10
#include "clang/Basic/FileManager.h"
11
#include "clang/Basic/SourceManager.h"
12
#include "clang/Lex/Lexer.h"
13
#include "llvm/ADT/Optional.h"
14
#include "llvm/Support/FormatVariadic.h"
15
#include "llvm/Support/Path.h"
16
17
namespace clang {
18
namespace tooling {
19
namespace {
20
21
183
LangOptions createLangOpts() {
22
183
  LangOptions LangOpts;
23
183
  LangOpts.CPlusPlus = 1;
24
183
  LangOpts.CPlusPlus11 = 1;
25
183
  LangOpts.CPlusPlus14 = 1;
26
183
  LangOpts.LineComment = 1;
27
183
  LangOpts.CXXOperatorNames = 1;
28
183
  LangOpts.Bool = 1;
29
183
  LangOpts.ObjC = 1;
30
183
  LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
31
183
  LangOpts.DeclSpecKeyword = 1; // To get __declspec.
32
183
  LangOpts.WChar = 1;           // To get wchar_t
33
183
  return LangOpts;
34
183
}
35
36
// Returns the offset after skipping a sequence of tokens, matched by \p
37
// GetOffsetAfterSequence, from the start of the code.
38
// \p GetOffsetAfterSequence should be a function that matches a sequence of
39
// tokens and returns an offset after the sequence.
40
unsigned getOffsetAfterTokenSequence(
41
    StringRef FileName, StringRef Code, const IncludeStyle &Style,
42
    llvm::function_ref<unsigned(const SourceManager &, Lexer &, Token &)>
43
183
        GetOffsetAfterSequence) {
44
183
  SourceManagerForFile VirtualSM(FileName, Code);
45
183
  SourceManager &SM = VirtualSM.get();
46
183
  LangOptions LangOpts = createLangOpts();
47
183
  Lexer Lex(SM.getMainFileID(), SM.getBufferOrFake(SM.getMainFileID()), SM,
48
183
            LangOpts);
49
183
  Token Tok;
50
  // Get the first token.
51
183
  Lex.LexFromRawLexer(Tok);
52
183
  return GetOffsetAfterSequence(SM, Lex, Tok);
53
183
}
54
55
// Check if a sequence of tokens is like "#<Name> <raw_identifier>". If it is,
56
// \p Tok will be the token after this directive; otherwise, it can be any token
57
// after the given \p Tok (including \p Tok). If \p RawIDName is provided, the
58
// (second) raw_identifier name is checked.
59
bool checkAndConsumeDirectiveWithName(
60
    Lexer &Lex, StringRef Name, Token &Tok,
61
130
    llvm::Optional<StringRef> RawIDName = llvm::None) {
62
130
  bool Matched = Tok.is(tok::hash) && 
!Lex.LexFromRawLexer(Tok)107
&&
63
130
                 
Tok.is(tok::raw_identifier)107
&&
64
130
                 
Tok.getRawIdentifier() == Name107
&&
!Lex.LexFromRawLexer(Tok)16
&&
65
130
                 
Tok.is(tok::raw_identifier)16
&&
66
130
                 
(15
!RawIDName15
||
Tok.getRawIdentifier() == *RawIDName1
);
67
130
  if (Matched)
68
15
    Lex.LexFromRawLexer(Tok);
69
130
  return Matched;
70
130
}
71
72
191
void skipComments(Lexer &Lex, Token &Tok) {
73
191
  while (Tok.is(tok::comment))
74
0
    if (Lex.LexFromRawLexer(Tok))
75
0
      return;
76
191
}
77
78
// Returns the offset after header guard directives and any comments
79
// before/after header guards (e.g. #ifndef/#define pair, #pragma once). If no
80
// header guard is present in the code, this will return the offset after
81
// skipping all comments from the start of the code.
82
unsigned getOffsetAfterHeaderGuardsAndComments(StringRef FileName,
83
                                               StringRef Code,
84
61
                                               const IncludeStyle &Style) {
85
  // \p Consume returns location after header guard or 0 if no header guard is
86
  // found.
87
61
  auto ConsumeHeaderGuardAndComment =
88
61
      [&](std::function<unsigned(const SourceManager &SM, Lexer &Lex,
89
61
                                 Token Tok)>
90
122
              Consume) {
91
122
        return getOffsetAfterTokenSequence(
92
122
            FileName, Code, Style,
93
122
            [&Consume](const SourceManager &SM, Lexer &Lex, Token Tok) {
94
122
              skipComments(Lex, Tok);
95
122
              unsigned InitialOffset = SM.getFileOffset(Tok.getLocation());
96
122
              return std::max(InitialOffset, Consume(SM, Lex, Tok));
97
122
            });
98
122
      };
99
61
  return std::max(
100
      // #ifndef/#define
101
61
      ConsumeHeaderGuardAndComment(
102
61
          [](const SourceManager &SM, Lexer &Lex, Token Tok) -> unsigned {
103
61
            if (checkAndConsumeDirectiveWithName(Lex, "ifndef", Tok)) {
104
8
              skipComments(Lex, Tok);
105
8
              if (checkAndConsumeDirectiveWithName(Lex, "define", Tok) &&
106
8
                  
Tok.isAtStartOfLine()6
)
107
5
                return SM.getFileOffset(Tok.getLocation());
108
8
            }
109
56
            return 0;
110
61
          }),
111
      // #pragma once
112
61
      ConsumeHeaderGuardAndComment(
113
61
          [](const SourceManager &SM, Lexer &Lex, Token Tok) -> unsigned {
114
61
            if (checkAndConsumeDirectiveWithName(Lex, "pragma", Tok,
115
61
                                                 StringRef("once")))
116
1
              return SM.getFileOffset(Tok.getLocation());
117
60
            return 0;
118
61
          }));
119
61
}
120
121
// Check if a sequence of tokens is like
122
//    "#include ("header.h" | <header.h>)".
123
// If it is, \p Tok will be the token after this directive; otherwise, it can be
124
// any token after the given \p Tok (including \p Tok).
125
251
bool checkAndConsumeInclusiveDirective(Lexer &Lex, Token &Tok) {
126
251
  auto Matched = [&]() {
127
190
    Lex.LexFromRawLexer(Tok);
128
190
    return true;
129
190
  };
130
251
  if (Tok.is(tok::hash) && 
!Lex.LexFromRawLexer(Tok)195
&&
131
251
      
Tok.is(tok::raw_identifier)195
&&
Tok.getRawIdentifier() == "include"195
) {
132
190
    if (Lex.LexFromRawLexer(Tok))
133
0
      return false;
134
190
    if (Tok.is(tok::string_literal))
135
164
      return Matched();
136
26
    if (Tok.is(tok::less)) {
137
66
      while (!Lex.LexFromRawLexer(Tok) && 
Tok.isNot(tok::greater)64
) {
138
40
      }
139
26
      if (Tok.is(tok::greater))
140
26
        return Matched();
141
26
    }
142
26
  }
143
61
  return false;
144
251
}
145
146
// Returns the offset of the last #include directive after which a new
147
// #include can be inserted. This ignores #include's after the #include block(s)
148
// in the beginning of a file to avoid inserting headers into code sections
149
// where new #include's should not be added by default.
150
// These code sections include:
151
//      - raw string literals (containing #include).
152
//      - #if blocks.
153
//      - Special #include's among declarations (e.g. functions).
154
//
155
// If no #include after which a new #include can be inserted, this returns the
156
// offset after skipping all comments from the start of the code.
157
// Inserting after an #include is not allowed if it comes after code that is not
158
// #include (e.g. pre-processing directive that is not #include, declarations).
159
unsigned getMaxHeaderInsertionOffset(StringRef FileName, StringRef Code,
160
61
                                     const IncludeStyle &Style) {
161
61
  return getOffsetAfterTokenSequence(
162
61
      FileName, Code, Style,
163
61
      [](const SourceManager &SM, Lexer &Lex, Token Tok) {
164
61
        skipComments(Lex, Tok);
165
61
        unsigned MaxOffset = SM.getFileOffset(Tok.getLocation());
166
251
        while (checkAndConsumeInclusiveDirective(Lex, Tok))
167
190
          MaxOffset = SM.getFileOffset(Tok.getLocation());
168
61
        return MaxOffset;
169
61
      });
170
61
}
171
172
279
inline StringRef trimInclude(StringRef IncludeName) {
173
279
  return IncludeName.trim("\"<>");
174
279
}
175
176
const char IncludeRegexPattern[] =
177
    R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
178
179
// The filename of Path excluding extension.
180
// Used to match implementation with headers, this differs from sys::path::stem:
181
//  - in names with multiple dots (foo.cu.cc) it terminates at the *first*
182
//  - an empty stem is never returned: /foo/.bar.x => .bar
183
//  - we don't bother to handle . and .. specially
184
854
StringRef matchingStem(llvm::StringRef Path) {
185
854
  StringRef Name = llvm::sys::path::filename(Path);
186
854
  return Name.substr(0, Name.find('.', 1));
187
854
}
188
189
} // anonymous namespace
190
191
IncludeCategoryManager::IncludeCategoryManager(const IncludeStyle &Style,
192
                                               StringRef FileName)
193
1.08k
    : Style(Style), FileName(FileName) {
194
3.29k
  for (const auto &Category : Style.IncludeCategories) {
195
3.29k
    CategoryRegexs.emplace_back(Category.Regex, Category.RegexIsCaseSensitive
196
3.29k
                                                    ? 
llvm::Regex::NoFlags4
197
3.29k
                                                    : 
llvm::Regex::IgnoreCase3.28k
);
198
3.29k
  }
199
1.08k
  IsMainFile = FileName.endswith(".c") || FileName.endswith(".cc") ||
200
1.08k
               
FileName.endswith(".cpp")494
||
FileName.endswith(".c++")272
||
201
1.08k
               
FileName.endswith(".cxx")272
||
FileName.endswith(".m")262
||
202
1.08k
               
FileName.endswith(".mm")262
;
203
1.08k
  if (!Style.IncludeIsMainSourceRegex.empty()) {
204
4
    llvm::Regex MainFileRegex(Style.IncludeIsMainSourceRegex);
205
4
    IsMainFile |= MainFileRegex.match(FileName);
206
4
  }
207
1.08k
}
208
209
int IncludeCategoryManager::getIncludePriority(StringRef IncludeName,
210
937
                                               bool CheckMainHeader) const {
211
937
  int Ret = INT_MAX;
212
2.61k
  for (unsigned i = 0, e = CategoryRegexs.size(); i != e; 
++i1.67k
)
213
2.61k
    if (CategoryRegexs[i].match(IncludeName)) {
214
937
      Ret = Style.IncludeCategories[i].Priority;
215
937
      break;
216
937
    }
217
937
  if (CheckMainHeader && 
IsMainFile694
&&
Ret > 0666
&&
isMainHeader(IncludeName)664
)
218
35
    Ret = 0;
219
937
  return Ret;
220
937
}
221
222
int IncludeCategoryManager::getSortIncludePriority(StringRef IncludeName,
223
676
                                                   bool CheckMainHeader) const {
224
676
  int Ret = INT_MAX;
225
1.87k
  for (unsigned i = 0, e = CategoryRegexs.size(); i != e; 
++i1.19k
)
226
1.87k
    if (CategoryRegexs[i].match(IncludeName)) {
227
676
      Ret = Style.IncludeCategories[i].SortPriority;
228
676
      if (Ret == 0)
229
659
        Ret = Style.IncludeCategories[i].Priority;
230
676
      break;
231
676
    }
232
676
  if (CheckMainHeader && 
IsMainFile617
&&
Ret > 0589
&&
isMainHeader(IncludeName)587
)
233
23
    Ret = 0;
234
676
  return Ret;
235
676
}
236
1.25k
bool IncludeCategoryManager::isMainHeader(StringRef IncludeName) const {
237
1.25k
  if (!IncludeName.startswith("\""))
238
397
    return false;
239
240
854
  IncludeName =
241
854
      IncludeName.drop_front(1).drop_back(1); // remove the surrounding "" or <>
242
  // Not matchingStem: implementation files may have compound extensions but
243
  // headers may not.
244
854
  StringRef HeaderStem = llvm::sys::path::stem(IncludeName);
245
854
  StringRef FileStem = llvm::sys::path::stem(FileName); // foo.cu for foo.cu.cc
246
854
  StringRef MatchingFileStem = matchingStem(FileName);  // foo for foo.cu.cc
247
  // main-header examples:
248
  //  1) foo.h => foo.cc
249
  //  2) foo.h => foo.cu.cc
250
  //  3) foo.proto.h => foo.proto.cc
251
  //
252
  // non-main-header examples:
253
  //  1) foo.h => bar.cc
254
  //  2) foo.proto.h => foo.cc
255
854
  StringRef Matching;
256
854
  if (MatchingFileStem.startswith_insensitive(HeaderStem))
257
58
    Matching = MatchingFileStem; // example 1), 2)
258
796
  else if (FileStem.equals_insensitive(HeaderStem))
259
2
    Matching = FileStem; // example 3)
260
854
  if (!Matching.empty()) {
261
60
    llvm::Regex MainIncludeRegex(HeaderStem.str() + Style.IncludeIsMainRegex,
262
60
                                 llvm::Regex::IgnoreCase);
263
60
    if (MainIncludeRegex.match(Matching))
264
58
      return true;
265
60
  }
266
796
  return false;
267
854
}
268
269
HeaderIncludes::HeaderIncludes(StringRef FileName, StringRef Code,
270
                               const IncludeStyle &Style)
271
    : FileName(FileName), Code(Code), FirstIncludeOffset(-1),
272
      MinInsertOffset(
273
          getOffsetAfterHeaderGuardsAndComments(FileName, Code, Style)),
274
      MaxInsertOffset(MinInsertOffset +
275
                      getMaxHeaderInsertionOffset(
276
                          FileName, Code.drop_front(MinInsertOffset), Style)),
277
      Categories(Style, FileName),
278
61
      IncludeRegex(llvm::Regex(IncludeRegexPattern)) {
279
  // Add 0 for main header and INT_MAX for headers that are not in any
280
  // category.
281
61
  Priorities = {0, INT_MAX};
282
61
  for (const auto &Category : Style.IncludeCategories)
283
192
    Priorities.insert(Category.Priority);
284
61
  SmallVector<StringRef, 32> Lines;
285
61
  Code.drop_front(MinInsertOffset).split(Lines, "\n");
286
287
61
  unsigned Offset = MinInsertOffset;
288
61
  unsigned NextLineOffset;
289
61
  SmallVector<StringRef, 4> Matches;
290
327
  for (auto Line : Lines) {
291
327
    NextLineOffset = std::min(Code.size(), Offset + Line.size() + 1);
292
327
    if (IncludeRegex.match(Line, &Matches)) {
293
      // If this is the last line without trailing newline, we need to make
294
      // sure we don't delete across the file boundary.
295
194
      addExistingInclude(
296
194
          Include(Matches[2],
297
194
                  tooling::Range(
298
194
                      Offset, std::min(Line.size() + 1, Code.size() - Offset))),
299
194
          NextLineOffset);
300
194
    }
301
327
    Offset = NextLineOffset;
302
327
  }
303
304
  // Populate CategoryEndOfssets:
305
  // - Ensure that CategoryEndOffset[Highest] is always populated.
306
  // - If CategoryEndOffset[Priority] isn't set, use the next higher value
307
  // that is set, up to CategoryEndOffset[Highest].
308
61
  auto Highest = Priorities.begin();
309
61
  if (CategoryEndOffsets.find(*Highest) == CategoryEndOffsets.end()) {
310
51
    if (FirstIncludeOffset >= 0)
311
32
      CategoryEndOffsets[*Highest] = FirstIncludeOffset;
312
19
    else
313
19
      CategoryEndOffsets[*Highest] = MinInsertOffset;
314
51
  }
315
  // By this point, CategoryEndOffset[Highest] is always set appropriately:
316
  //  - to an appropriate location before/after existing #includes, or
317
  //  - to right after the header guard, or
318
  //  - to the beginning of the file.
319
305
  for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; 
++I244
)
320
244
    if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end())
321
188
      CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)];
322
61
}
323
324
// \p Offset: the start of the line following this include directive.
325
void HeaderIncludes::addExistingInclude(Include IncludeToAdd,
326
194
                                        unsigned NextLineOffset) {
327
194
  auto Iter =
328
194
      ExistingIncludes.try_emplace(trimInclude(IncludeToAdd.Name)).first;
329
194
  Iter->second.push_back(std::move(IncludeToAdd));
330
194
  auto &CurInclude = Iter->second.back();
331
  // The header name with quotes or angle brackets.
332
  // Only record the offset of current #include if we can insert after it.
333
194
  if (CurInclude.R.getOffset() <= MaxInsertOffset) {
334
190
    int Priority = Categories.getIncludePriority(
335
190
        CurInclude.Name, /*CheckMainHeader=*/FirstIncludeOffset < 0);
336
190
    CategoryEndOffsets[Priority] = NextLineOffset;
337
190
    IncludesByPriority[Priority].push_back(&CurInclude);
338
190
    if (FirstIncludeOffset < 0)
339
42
      FirstIncludeOffset = CurInclude.R.getOffset();
340
190
  }
341
194
}
342
343
llvm::Optional<tooling::Replacement>
344
74
HeaderIncludes::insert(llvm::StringRef IncludeName, bool IsAngled) const {
345
74
  assert(IncludeName == trimInclude(IncludeName));
346
  // If a <header> ("header") already exists in code, "header" (<header>) with
347
  // different quotation will still be inserted.
348
  // FIXME: figure out if this is the best behavior.
349
0
  auto It = ExistingIncludes.find(IncludeName);
350
74
  if (It != ExistingIncludes.end())
351
4
    for (const auto &Inc : It->second)
352
4
      if ((IsAngled && 
StringRef(Inc.Name).startswith("<")2
) ||
353
4
          
(2
!IsAngled2
&&
StringRef(Inc.Name).startswith("\"")2
))
354
3
        return llvm::None;
355
71
  std::string Quoted =
356
71
      std::string(llvm::formatv(IsAngled ? 
"<{0}>"35
:
"\"{0}\""36
, IncludeName));
357
71
  StringRef QuotedName = Quoted;
358
71
  int Priority = Categories.getIncludePriority(
359
71
      QuotedName, /*CheckMainHeader=*/FirstIncludeOffset < 0);
360
71
  auto CatOffset = CategoryEndOffsets.find(Priority);
361
71
  assert(CatOffset != CategoryEndOffsets.end());
362
0
  unsigned InsertOffset = CatOffset->second; // Fall back offset
363
71
  auto Iter = IncludesByPriority.find(Priority);
364
71
  if (Iter != IncludesByPriority.end()) {
365
132
    for (const auto *Inc : Iter->second) {
366
132
      if (QuotedName < Inc->Name) {
367
11
        InsertOffset = Inc->R.getOffset();
368
11
        break;
369
11
      }
370
132
    }
371
23
  }
372
71
  assert(InsertOffset <= Code.size());
373
0
  std::string NewInclude =
374
71
      std::string(llvm::formatv("#include {0}\n", QuotedName));
375
  // When inserting headers at end of the code, also append '\n' to the code
376
  // if it does not end with '\n'.
377
  // FIXME: when inserting multiple #includes at the end of code, only one
378
  // newline should be added.
379
71
  if (InsertOffset == Code.size() && 
(11
!Code.empty()11
&&
Code.back() != '\n'10
))
380
3
    NewInclude = "\n" + NewInclude;
381
71
  return tooling::Replacement(FileName, InsertOffset, 0, NewInclude);
382
74
}
383
384
tooling::Replacements HeaderIncludes::remove(llvm::StringRef IncludeName,
385
11
                                             bool IsAngled) const {
386
11
  assert(IncludeName == trimInclude(IncludeName));
387
0
  tooling::Replacements Result;
388
11
  auto Iter = ExistingIncludes.find(IncludeName);
389
11
  if (Iter == ExistingIncludes.end())
390
0
    return Result;
391
13
  
for (const auto &Inc : Iter->second)11
{
392
13
    if ((IsAngled && 
StringRef(Inc.Name).startswith("\"")4
) ||
393
13
        
(12
!IsAngled12
&&
StringRef(Inc.Name).startswith("<")9
))
394
2
      continue;
395
11
    llvm::Error Err = Result.add(tooling::Replacement(
396
11
        FileName, Inc.R.getOffset(), Inc.R.getLength(), ""));
397
11
    if (Err) {
398
0
      auto ErrMsg = "Unexpected conflicts in #include deletions: " +
399
0
                    llvm::toString(std::move(Err));
400
0
      llvm_unreachable(ErrMsg.c_str());
401
0
    }
402
11
  }
403
11
  return Result;
404
11
}
405
406
} // namespace tooling
407
} // namespace clang