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