/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 |