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/LLVM.h"
11#include "clang/Basic/SourceManager.h"
12#include "clang/Basic/TokenKinds.h"
13#include "clang/Lex/Lexer.h"
14#include "clang/Lex/Token.h"
15#include "clang/Tooling/Core/Replacement.h"
16#include "clang/Tooling/Inclusions/IncludeStyle.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/STLFunctionalExtras.h"
20#include "llvm/ADT/StringRef.h"
21#include "llvm/Support/Error.h"
22#include "llvm/Support/ErrorHandling.h"
23#include "llvm/Support/FormatVariadic.h"
24#include "llvm/Support/Path.h"
25#include "llvm/Support/Regex.h"
26#include <algorithm>
27#include <cassert>
28#include <climits>
29#include <functional>
30#include <iterator>
31#include <optional>
32#include <string>
33#include <type_traits>
34#include <utility>
35#include <vector>
36
37namespace clang {
38namespace tooling {
39namespace {
40
41LangOptions createLangOpts() {
42 LangOptions LangOpts;
43 LangOpts.CPlusPlus = 1;
44 LangOpts.CPlusPlus11 = 1;
45 LangOpts.CPlusPlus14 = 1;
46 LangOpts.LineComment = 1;
47 LangOpts.CXXOperatorNames = 1;
48 LangOpts.Bool = 1;
49 LangOpts.ObjC = 1;
50 LangOpts.MicrosoftExt = 1; // To get kw___try, kw___finally.
51 LangOpts.DeclSpecKeyword = 1; // To get __declspec.
52 LangOpts.WChar = 1; // To get wchar_t
53 return LangOpts;
54}
55
56// Create a new lexer on the given \p Code and calls \p Callback with the
57// created source manager and lexer. \p Callback must be a callable object that
58// could be invoked with (const SourceManager &, Lexer &). This function returns
59// whatever \p Callback returns.
60template <typename F>
61auto withLexer(StringRef FileName, StringRef Code, const IncludeStyle &Style,
62 F &&Callback)
63 -> std::invoke_result_t<F, const SourceManager &, Lexer &> {
64 SourceManagerForFile VirtualSM(FileName, Code);
65 SourceManager &SM = VirtualSM.get();
66 LangOptions LangOpts = createLangOpts();
67 Lexer Lex(SM.getMainFileID(), SM.getBufferOrFake(FID: SM.getMainFileID()), SM,
68 LangOpts);
69 return std::invoke(std::forward<F>(Callback), std::as_const(t&: SM), Lex);
70}
71
72// Returns the offset after skipping a sequence of tokens, matched by \p
73// GetOffsetAfterSequence, from the start of the code.
74// \p GetOffsetAfterSequence should be a function that matches a sequence of
75// tokens and returns an offset after the sequence.
76unsigned getOffsetAfterTokenSequence(
77 StringRef FileName, StringRef Code, const IncludeStyle &Style,
78 llvm::function_ref<unsigned(const SourceManager &, Lexer &, Token &)>
79 GetOffsetAfterSequence) {
80 return withLexer(FileName, Code, Style,
81 Callback: [&](const SourceManager &SM, Lexer &Lex) {
82 Token Tok;
83 // Get the first token.
84 Lex.LexFromRawLexer(Result&: Tok);
85 return GetOffsetAfterSequence(SM, Lex, Tok);
86 });
87}
88
89// Check if a sequence of tokens is like "#<Name> <raw_identifier>". If it is,
90// \p Tok will be the token after this directive; otherwise, it can be any token
91// after the given \p Tok (including \p Tok). If \p RawIDName is provided, the
92// (second) raw_identifier name is checked.
93bool checkAndConsumeDirectiveWithName(
94 Lexer &Lex, StringRef Name, Token &Tok,
95 std::optional<StringRef> RawIDName = std::nullopt) {
96 bool Matched = Tok.is(K: tok::hash) && !Lex.LexFromRawLexer(Result&: Tok) &&
97 Tok.is(K: tok::raw_identifier) &&
98 Tok.getRawIdentifier() == Name && !Lex.LexFromRawLexer(Result&: Tok) &&
99 Tok.is(K: tok::raw_identifier) &&
100 (!RawIDName || Tok.getRawIdentifier() == *RawIDName);
101 if (Matched)
102 Lex.LexFromRawLexer(Result&: Tok);
103 return Matched;
104}
105
106void skipComments(Lexer &Lex, Token &Tok) {
107 while (Tok.is(K: tok::comment))
108 if (Lex.LexFromRawLexer(Result&: Tok))
109 return;
110}
111
112bool checkAndConsumeModuleDecl(const SourceManager &SM, Lexer &Lex,
113 Token &Tok) {
114 bool Matched = Tok.is(K: tok::raw_identifier) &&
115 Tok.getRawIdentifier() == "module" &&
116 !Lex.LexFromRawLexer(Result&: Tok) && Tok.is(K: tok::semi) &&
117 !Lex.LexFromRawLexer(Result&: Tok);
118 return Matched;
119}
120
121// Determines the minimum offset into the file where we want to insert header
122// includes. This will be put (when available):
123// - after `#pragma once`
124// - after header guards (`#ifdef` and `#define`)
125// - after opening global module (`module;`)
126// - after any comments at the start of the file or immediately following one of
127// the above constructs
128unsigned getMinHeaderInsertionOffset(StringRef FileName, StringRef Code,
129 const IncludeStyle &Style) {
130 // \p Consume returns location after header guard or 0 if no header guard is
131 // found.
132 auto ConsumeHeaderGuardAndComment =
133 [&](std::function<unsigned(const SourceManager &SM, Lexer &Lex,
134 Token Tok)>
135 Consume) {
136 return getOffsetAfterTokenSequence(
137 FileName, Code, Style,
138 GetOffsetAfterSequence: [&Consume](const SourceManager &SM, Lexer &Lex, Token Tok) {
139 skipComments(Lex, Tok);
140 unsigned InitialOffset = SM.getFileOffset(SpellingLoc: Tok.getLocation());
141 return std::max(a: InitialOffset, b: Consume(SM, Lex, Tok));
142 });
143 };
144
145 auto ModuleDecl = ConsumeHeaderGuardAndComment(
146 [](const SourceManager &SM, Lexer &Lex, Token Tok) -> unsigned {
147 if (checkAndConsumeModuleDecl(SM, Lex, Tok)) {
148 skipComments(Lex, Tok);
149 return SM.getFileOffset(SpellingLoc: Tok.getLocation());
150 }
151 return 0;
152 });
153
154 auto HeaderAndPPOffset = std::max(
155 // #ifndef/#define
156 a: ConsumeHeaderGuardAndComment(
157 [](const SourceManager &SM, Lexer &Lex, Token Tok) -> unsigned {
158 if (checkAndConsumeDirectiveWithName(Lex, Name: "ifndef", Tok)) {
159 skipComments(Lex, Tok);
160 if (checkAndConsumeDirectiveWithName(Lex, Name: "define", Tok) &&
161 Tok.isAtStartOfLine())
162 return SM.getFileOffset(SpellingLoc: Tok.getLocation());
163 }
164 return 0;
165 }),
166 // #pragma once
167 b: ConsumeHeaderGuardAndComment(
168 [](const SourceManager &SM, Lexer &Lex, Token Tok) -> unsigned {
169 if (checkAndConsumeDirectiveWithName(Lex, Name: "pragma", Tok,
170 RawIDName: StringRef("once")))
171 return SM.getFileOffset(SpellingLoc: Tok.getLocation());
172 return 0;
173 }));
174 return std::max(a: HeaderAndPPOffset, b: ModuleDecl);
175}
176
177// Check if a sequence of tokens is like
178// "#(include | import) ("header.h" | <header.h>)".
179// If it is, \p Tok will be the token after this directive; otherwise, it can be
180// any token after the given \p Tok (including \p Tok).
181bool checkAndConsumeInclusiveDirective(Lexer &Lex, Token &Tok) {
182 auto Matched = [&]() {
183 Lex.LexFromRawLexer(Result&: Tok);
184 return true;
185 };
186 if (Tok.is(K: tok::hash) && !Lex.LexFromRawLexer(Result&: Tok) &&
187 Tok.is(K: tok::raw_identifier) &&
188 (Tok.getRawIdentifier() == "include" ||
189 Tok.getRawIdentifier() == "import")) {
190 if (Lex.LexFromRawLexer(Result&: Tok))
191 return false;
192 if (Tok.is(K: tok::string_literal))
193 return Matched();
194 if (Tok.is(K: tok::less)) {
195 while (!Lex.LexFromRawLexer(Result&: Tok) && Tok.isNot(K: tok::greater)) {
196 }
197 if (Tok.is(K: tok::greater))
198 return Matched();
199 }
200 }
201 return false;
202}
203
204// Returns the offset of the last #include directive after which a new
205// #include can be inserted. This ignores #include's after the #include block(s)
206// in the beginning of a file to avoid inserting headers into code sections
207// where new #include's should not be added by default.
208// These code sections include:
209// - raw string literals (containing #include).
210// - #if blocks.
211// - Special #include's among declarations (e.g. functions).
212//
213// If no #include after which a new #include can be inserted, this returns the
214// offset after skipping all comments from the start of the code.
215// Inserting after an #include is not allowed if it comes after code that is not
216// #include (e.g. pre-processing directive that is not #include, declarations).
217unsigned getMaxHeaderInsertionOffset(StringRef FileName, StringRef Code,
218 const IncludeStyle &Style) {
219 return getOffsetAfterTokenSequence(
220 FileName, Code, Style,
221 GetOffsetAfterSequence: [](const SourceManager &SM, Lexer &Lex, Token Tok) {
222 skipComments(Lex, Tok);
223 unsigned MaxOffset = SM.getFileOffset(SpellingLoc: Tok.getLocation());
224 while (checkAndConsumeInclusiveDirective(Lex, Tok))
225 MaxOffset = SM.getFileOffset(SpellingLoc: Tok.getLocation());
226 return MaxOffset;
227 });
228}
229
230// Check whether the first declaration in the code is a C++20 module
231// declaration, and it is not preceded by any preprocessor directives.
232bool isFirstDeclModuleDecl(StringRef FileName, StringRef Code,
233 const IncludeStyle &Style) {
234 return withLexer(
235 FileName, Code, Style, Callback: [](const SourceManager &SM, Lexer &Lex) {
236 // Let the lexer skip any comments and whitespaces for us.
237 Lex.SetKeepWhitespaceMode(false);
238 Lex.SetCommentRetentionState(false);
239
240 Token tok;
241 if (Lex.LexFromRawLexer(Result&: tok))
242 return false;
243
244 // A module declaration is made up of the following token sequence:
245 // export? module <ident> ('.' <ident>)* <partition> <attr> ;
246 //
247 // For convenience, we don't actually lex the whole declaration -- it's
248 // enough to distinguish a module declaration to just ensure an <ident>
249 // is following the "module" keyword.
250
251 // Lex the optional "export" keyword.
252 if (tok.is(K: tok::raw_identifier) && tok.getRawIdentifier() == "export") {
253 if (Lex.LexFromRawLexer(Result&: tok))
254 return false;
255 }
256
257 // Lex the "module" keyword.
258 if (!tok.is(K: tok::raw_identifier) ||
259 tok.getRawIdentifier() != "module" || Lex.LexFromRawLexer(Result&: tok))
260 return false;
261
262 // Make sure an identifier follows the "module" keyword.
263 return tok.is(K: tok::raw_identifier);
264 });
265}
266
267inline StringRef trimInclude(StringRef IncludeName) {
268 return IncludeName.trim(Chars: "\"<>");
269}
270
271const char IncludeRegexPattern[] =
272 "^[\t ]*#[\t ]*(import|include)[^\"<]*([\"<][^\">]*[\">])";
273
274// The filename of Path excluding extension.
275// Used to match implementation with headers, this differs from sys::path::stem:
276// - in names with multiple dots (foo.cu.cc) it terminates at the *first*
277// - an empty stem is never returned: /foo/.bar.x => .bar
278// - we don't bother to handle . and .. specially
279StringRef matchingStem(llvm::StringRef Path) {
280 StringRef Name = llvm::sys::path::filename(path: Path);
281 return Name.substr(Start: 0, N: Name.find(C: '.', From: 1));
282}
283
284} // anonymous namespace
285
286IncludeCategoryManager::IncludeCategoryManager(const IncludeStyle &Style,
287 StringRef FileName)
288 : Style(Style), FileName(FileName) {
289 for (const auto &Category : Style.IncludeCategories) {
290 CategoryRegexs.emplace_back(Args: Category.Regex, Args: Category.RegexIsCaseSensitive
291 ? llvm::Regex::NoFlags
292 : llvm::Regex::IgnoreCase);
293 }
294 IsMainFile = FileName.ends_with(Suffix: ".c") || FileName.ends_with(Suffix: ".cc") ||
295 FileName.ends_with(Suffix: ".cpp") || FileName.ends_with(Suffix: ".c++") ||
296 FileName.ends_with(Suffix: ".cxx") || FileName.ends_with(Suffix: ".m") ||
297 FileName.ends_with(Suffix: ".mm");
298 if (!Style.IncludeIsMainSourceRegex.empty()) {
299 llvm::Regex MainFileRegex(Style.IncludeIsMainSourceRegex);
300 IsMainFile |= MainFileRegex.match(String: FileName);
301 }
302}
303
304int IncludeCategoryManager::getIncludePriority(StringRef IncludeName,
305 bool CheckMainHeader) const {
306 int Ret = INT_MAX;
307 for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
308 if (CategoryRegexs[i].match(String: IncludeName)) {
309 Ret = Style.IncludeCategories[i].Priority;
310 break;
311 }
312 if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
313 Ret = 0;
314 return Ret;
315}
316
317int IncludeCategoryManager::getSortIncludePriority(StringRef IncludeName,
318 bool CheckMainHeader) const {
319 int Ret = INT_MAX;
320 for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
321 if (CategoryRegexs[i].match(String: IncludeName)) {
322 Ret = Style.IncludeCategories[i].SortPriority;
323 if (Ret == 0)
324 Ret = Style.IncludeCategories[i].Priority;
325 break;
326 }
327 if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
328 Ret = 0;
329 return Ret;
330}
331bool IncludeCategoryManager::isMainHeader(StringRef IncludeName) const {
332 switch (Style.MainIncludeChar) {
333 case IncludeStyle::MICD_Quote:
334 if (!IncludeName.starts_with(Prefix: "\""))
335 return false;
336 break;
337 case IncludeStyle::MICD_AngleBracket:
338 if (!IncludeName.starts_with(Prefix: "<"))
339 return false;
340 break;
341 case IncludeStyle::MICD_Any:
342 break;
343 }
344
345 IncludeName =
346 IncludeName.drop_front(N: 1).drop_back(N: 1); // remove the surrounding "" or <>
347 // Not matchingStem: implementation files may have compound extensions but
348 // headers may not.
349 StringRef HeaderStem = llvm::sys::path::stem(path: IncludeName);
350 StringRef FileStem = llvm::sys::path::stem(path: FileName); // foo.cu for foo.cu.cc
351 StringRef MatchingFileStem = matchingStem(Path: FileName); // foo for foo.cu.cc
352 // main-header examples:
353 // 1) foo.h => foo.cc
354 // 2) foo.h => foo.cu.cc
355 // 3) foo.proto.h => foo.proto.cc
356 //
357 // non-main-header examples:
358 // 1) foo.h => bar.cc
359 // 2) foo.proto.h => foo.cc
360 StringRef Matching;
361 if (MatchingFileStem.starts_with_insensitive(Prefix: HeaderStem))
362 Matching = MatchingFileStem; // example 1), 2)
363 else if (FileStem.equals_insensitive(RHS: HeaderStem))
364 Matching = FileStem; // example 3)
365 if (!Matching.empty()) {
366 llvm::Regex MainIncludeRegex(llvm::Regex::escape(String: HeaderStem) +
367 Style.IncludeIsMainRegex,
368 llvm::Regex::IgnoreCase);
369 if (MainIncludeRegex.match(String: Matching))
370 return true;
371 }
372 return false;
373}
374
375const llvm::Regex HeaderIncludes::IncludeRegex(IncludeRegexPattern);
376
377HeaderIncludes::HeaderIncludes(StringRef FileName, StringRef Code,
378 const IncludeStyle &Style)
379 : FileName(FileName), Code(Code), FirstIncludeOffset(-1),
380 MinInsertOffset(getMinHeaderInsertionOffset(FileName, Code, Style)),
381 MaxInsertOffset(MinInsertOffset +
382 getMaxHeaderInsertionOffset(
383 FileName, Code: Code.drop_front(N: MinInsertOffset), Style)),
384 MainIncludeFound(false),
385 ShouldInsertGlobalModuleFragmentDecl(
386 isFirstDeclModuleDecl(FileName, Code, Style)),
387 Categories(Style, FileName) {
388 // Add 0 for main header and INT_MAX for headers that are not in any
389 // category.
390 Priorities = {0, INT_MAX};
391 for (const auto &Category : Style.IncludeCategories)
392 Priorities.insert(x: Category.Priority);
393 SmallVector<StringRef, 32> Lines;
394 Code.drop_front(N: MinInsertOffset).split(A&: Lines, Separator: "\n");
395
396 unsigned Offset = MinInsertOffset;
397 unsigned NextLineOffset;
398 SmallVector<StringRef, 4> Matches;
399 for (auto Line : Lines) {
400 NextLineOffset = std::min(a: Code.size(), b: Offset + Line.size() + 1);
401 if (IncludeRegex.match(String: Line, Matches: &Matches)) {
402 // If this is the last line without trailing newline, we need to make
403 // sure we don't delete across the file boundary.
404 addExistingInclude(
405 IncludeToAdd: Include(Matches[2],
406 tooling::Range(
407 Offset, std::min(a: Line.size() + 1, b: Code.size() - Offset)),
408 Matches[1] == "import" ? tooling::IncludeDirective::Import
409 : tooling::IncludeDirective::Include),
410 NextLineOffset);
411 }
412 Offset = NextLineOffset;
413 }
414
415 // Populate CategoryEndOfssets:
416 // - Ensure that CategoryEndOffset[Highest] is always populated.
417 // - If CategoryEndOffset[Priority] isn't set, use the next higher value
418 // that is set, up to CategoryEndOffset[Highest].
419 auto Highest = Priorities.begin();
420 auto [It, Inserted] = CategoryEndOffsets.try_emplace(k: *Highest);
421 if (Inserted)
422 It->second = FirstIncludeOffset >= 0 ? FirstIncludeOffset : MinInsertOffset;
423 // By this point, CategoryEndOffset[Highest] is always set appropriately:
424 // - to an appropriate location before/after existing #includes, or
425 // - to right after the header guard, or
426 // - to the beginning of the file.
427 for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; ++I)
428 if (CategoryEndOffsets.find(x: *I) == CategoryEndOffsets.end())
429 CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(x: I)];
430}
431
432// \p Offset: the start of the line following this include directive.
433void HeaderIncludes::addExistingInclude(Include IncludeToAdd,
434 unsigned NextLineOffset) {
435 auto &Incs = ExistingIncludes[trimInclude(IncludeName: IncludeToAdd.Name)];
436 Incs.push_back(x: std::move(IncludeToAdd));
437 auto &CurInclude = Incs.back();
438 // The header name with quotes or angle brackets.
439 // Only record the offset of current #include if we can insert after it.
440 if (CurInclude.R.getOffset() <= MaxInsertOffset) {
441 int Priority = Categories.getIncludePriority(
442 IncludeName: CurInclude.Name, /*CheckMainHeader=*/!MainIncludeFound);
443 if (Priority == 0)
444 MainIncludeFound = true;
445 CategoryEndOffsets[Priority] = NextLineOffset;
446 IncludesByPriority[Priority].push_back(Elt: &CurInclude);
447 if (FirstIncludeOffset < 0)
448 FirstIncludeOffset = CurInclude.R.getOffset();
449 }
450}
451
452std::optional<tooling::Replacement>
453HeaderIncludes::insert(llvm::StringRef Header, bool IsAngled,
454 IncludeDirective Directive) const {
455 assert(Header == trimInclude(Header));
456 // If a <header> ("header") already exists in code, "header" (<header>) with
457 // different quotation will still be inserted.
458 // FIXME: figure out if this is the best behavior.
459 auto It = ExistingIncludes.find(Key: Header);
460 if (It != ExistingIncludes.end()) {
461 for (const auto &Inc : It->second) {
462 bool SameQuotation = (IsAngled && StringRef(Inc.Name).starts_with(Prefix: "<")) ||
463 (!IsAngled && StringRef(Inc.Name).starts_with(Prefix: "\""));
464 if (SameQuotation) {
465 // If the directive is the same, or if the directive is an include and
466 // the existing directive is an import, then we don't need to insert
467 // the header.
468 if ((Inc.Directive == Directive) ||
469 (Inc.Directive == IncludeDirective::Import &&
470 Directive == IncludeDirective::Include)) {
471 return std::nullopt;
472 }
473
474 // "import" outranks "include" with the assumption that includes are
475 // designed to handle multiple inclusions while import is not.
476 char Open = IsAngled ? '<' : '"';
477 char Close = IsAngled ? '>' : '"';
478 std::string NewInclude =
479 llvm::formatv(Fmt: "#import {0}{1}{2}\n", Vals&: Open, Vals&: Header, Vals&: Close);
480
481 return tooling::Replacement(FileName, Inc.R.getOffset(),
482 Inc.R.getLength(), NewInclude);
483 }
484 }
485 }
486 std::string Quoted =
487 std::string(llvm::formatv(Fmt: IsAngled ? "<{0}>" : "\"{0}\"", Vals&: Header));
488 StringRef QuotedName = Quoted;
489 int Priority = Categories.getIncludePriority(
490 IncludeName: QuotedName, /*CheckMainHeader=*/!MainIncludeFound);
491 auto CatOffset = CategoryEndOffsets.find(x: Priority);
492 assert(CatOffset != CategoryEndOffsets.end());
493 unsigned InsertOffset = CatOffset->second; // Fall back offset
494 auto Iter = IncludesByPriority.find(x: Priority);
495 if (Iter != IncludesByPriority.end()) {
496 for (const auto *Inc : Iter->second) {
497 if (QuotedName < Inc->Name) {
498 InsertOffset = Inc->R.getOffset();
499 break;
500 }
501 }
502 }
503 assert(InsertOffset <= Code.size());
504 llvm::StringRef DirectiveSpelling =
505 Directive == IncludeDirective::Include ? "include" : "import";
506 std::string NewInclude =
507 llvm::formatv(Fmt: "#{0} {1}\n", Vals&: DirectiveSpelling, Vals&: QuotedName);
508 // When inserting headers at end of the code, also append '\n' to the code
509 // if it does not end with '\n'.
510 // FIXME: when inserting multiple #includes at the end of code, only one
511 // newline should be added.
512 if (InsertOffset == Code.size() && (!Code.empty() && Code.back() != '\n'))
513 NewInclude = "\n" + NewInclude;
514 if (ShouldInsertGlobalModuleFragmentDecl)
515 NewInclude = "module;\n" + NewInclude;
516 return tooling::Replacement(FileName, InsertOffset, 0, NewInclude);
517}
518
519HeaderIncludes::HeaderToInsert::HeaderToInsert(
520 llvm::StringRef RawOrSpelledHeader, IncludeDirective Directive,
521 QuoteStyle QuoteStyle)
522 : Directive(Directive) {
523 if (RawOrSpelledHeader.starts_with(Prefix: "<")) {
524 Header = RawOrSpelledHeader.trim(Chars: "<>").str();
525 this->IsAngled = QuoteStyle != QuoteStyle::QUOTED;
526 } else if (RawOrSpelledHeader.starts_with(Prefix: "\"")) {
527 Header = RawOrSpelledHeader.trim(Chars: "\"").str();
528 this->IsAngled = QuoteStyle == QuoteStyle::ANGLED;
529 }
530}
531
532tooling::Replacements
533HeaderIncludes::insert(llvm::ArrayRef<HeaderToInsert> Headers) const {
534 tooling::Replacements Result;
535 if (Headers.empty())
536 return Result;
537
538 std::vector<HeaderToInsert> SortedHeaders = Headers.vec();
539 llvm::stable_sort(Range&: SortedHeaders, C: [&](const HeaderToInsert &L,
540 const HeaderToInsert &R) {
541 std::string QuotedL =
542 std::string(llvm::formatv(Fmt: L.IsAngled ? "<{0}>" : "\"{0}\"", Vals: L.Header));
543 std::string QuotedR =
544 std::string(llvm::formatv(Fmt: R.IsAngled ? "<{0}>" : "\"{0}\"", Vals: R.Header));
545 int PriorityL = Categories.getIncludePriority(
546 IncludeName: QuotedL, /*CheckMainHeader=*/!MainIncludeFound);
547 int PriorityR = Categories.getIncludePriority(
548 IncludeName: QuotedR, /*CheckMainHeader=*/!MainIncludeFound);
549 if (PriorityL != PriorityR)
550 return PriorityL < PriorityR;
551 if (L.Header != R.Header)
552 return L.Header < R.Header;
553 if (L.IsAngled != R.IsAngled)
554 return L.IsAngled < R.IsAngled;
555 return L.Directive > R.Directive;
556 });
557 SortedHeaders.erase(
558 first: std::unique(first: SortedHeaders.begin(), last: SortedHeaders.end(),
559 binary_pred: [](const HeaderToInsert &L, const HeaderToInsert &R) {
560 return L.Header == R.Header && L.IsAngled == R.IsAngled;
561 }),
562 last: SortedHeaders.end());
563
564 struct InsertionInfo {
565 std::string Text;
566 unsigned Length = 0;
567 };
568 llvm::DenseMap<unsigned, InsertionInfo> InsertionsByOffset;
569
570 for (const auto &H : SortedHeaders) {
571 if (auto Insertion = insert(Header: H.Header, IsAngled: H.IsAngled, Directive: H.Directive)) {
572 auto &Info = InsertionsByOffset[Insertion->getOffset()];
573 Info.Text += Insertion->getReplacementText();
574 if (Insertion->getLength() > 0) {
575 assert(Info.Length == 0 && "Multiple replacements at same offset?");
576 Info.Length = Insertion->getLength();
577 }
578 }
579 }
580
581 for (const auto &Entry : InsertionsByOffset) {
582 const auto &Info = Entry.second;
583 const unsigned Offset = Entry.first;
584 cantFail(Err: Result.add(
585 R: tooling::Replacement(FileName, Offset, Info.Length, Info.Text)));
586 }
587
588 return Result;
589}
590
591tooling::Replacements HeaderIncludes::remove(llvm::StringRef Header,
592 bool IsAngled) const {
593 assert(Header == trimInclude(Header));
594 tooling::Replacements Result;
595 auto Iter = ExistingIncludes.find(Key: Header);
596 if (Iter == ExistingIncludes.end())
597 return Result;
598 for (const auto &Inc : Iter->second) {
599 if ((IsAngled && StringRef(Inc.Name).starts_with(Prefix: "\"")) ||
600 (!IsAngled && StringRef(Inc.Name).starts_with(Prefix: "<")))
601 continue;
602 llvm::Error Err = Result.add(R: tooling::Replacement(
603 FileName, Inc.R.getOffset(), Inc.R.getLength(), ""));
604 if (Err) {
605 auto ErrMsg = "Unexpected conflicts in #include deletions: " +
606 llvm::toString(E: std::move(Err));
607 llvm_unreachable(ErrMsg.c_str());
608 }
609 }
610 return Result;
611}
612
613} // namespace tooling
614} // namespace clang
615