| 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/Support/FormatVariadic.h" |
| 14 |
#include "llvm/Support/Path.h" |
| 15 |
#include <optional> |
| 16 |
|
| 17 |
namespace clang { |
| 18 |
namespace tooling { |
| 19 |
namespace { |
| 20 |
|
| 21 |
LangOptions createLangOpts() { |
| 22 |
LangOptions LangOpts; |
| 23 |
LangOpts.CPlusPlus = 1; |
| 24 |
LangOpts.CPlusPlus11 = 1; |
| 25 |
LangOpts.CPlusPlus14 = 1; |
| 26 |
LangOpts.LineComment = 1; |
| 27 |
LangOpts.CXXOperatorNames = 1; |
| 28 |
LangOpts.Bool = 1; |
| 29 |
LangOpts.ObjC = 1; |
| 30 |
LangOpts.MicrosoftExt = 1; // To get kw___try, kw___finally. |
| 31 |
LangOpts.DeclSpecKeyword = 1; // To get __declspec. |
| 32 |
LangOpts.WChar = 1; // To get wchar_t |
| 33 |
return LangOpts; |
| 34 |
} |
| 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 |
GetOffsetAfterSequence) { |
| 44 |
SourceManagerForFile VirtualSM(FileName, Code); |
| 45 |
SourceManager &SM = VirtualSM.get(); |
| 46 |
LangOptions LangOpts = createLangOpts(); |
| 47 |
Lexer Lex(SM.getMainFileID(), SM.getBufferOrFake(SM.getMainFileID()), SM, |
| 48 |
LangOpts); |
| 49 |
Token Tok; |
| 50 |
// Get the first token. |
| 51 |
Lex.LexFromRawLexer(Tok); |
| 52 |
return GetOffsetAfterSequence(SM, Lex, Tok); |
| 53 |
} |
| 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 |
std::optional<StringRef> RawIDName = std::nullopt) { |
| 62 |
bool Matched = Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) && |
| 63 |
Tok.is(tok::raw_identifier) && |
| 64 |
Tok.getRawIdentifier() == Name && !Lex.LexFromRawLexer(Tok) && |
| 65 |
Tok.is(tok::raw_identifier) && |
| 66 |
(!RawIDName || Tok.getRawIdentifier() == *RawIDName); |
| 67 |
if (Matched) |
| 68 |
Lex.LexFromRawLexer(Tok); |
| 69 |
return Matched; |
| 70 |
} |
| 71 |
|
| 72 |
void skipComments(Lexer &Lex, Token &Tok) { |
| 73 |
while (Tok.is(tok::comment)) |
| 74 |
if (Lex.LexFromRawLexer(Tok)) |
| 75 |
return; |
| 76 |
} |
| 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 |
const IncludeStyle &Style) { |
| 85 |
// \p Consume returns location after header guard or 0 if no header guard is |
| 86 |
// found. |
| 87 |
auto ConsumeHeaderGuardAndComment = |
| 88 |
[&](std::function<unsigned(const SourceManager &SM, Lexer &Lex, |
| 89 |
Token Tok)> |
| 90 |
Consume) { |
| 91 |
return getOffsetAfterTokenSequence( |
| 92 |
FileName, Code, Style, |
| 93 |
[&Consume](const SourceManager &SM, Lexer &Lex, Token Tok) { |
| 94 |
skipComments(Lex, Tok); |
| 95 |
unsigned InitialOffset = SM.getFileOffset(Tok.getLocation()); |
| 96 |
return std::max(InitialOffset, Consume(SM, Lex, Tok)); |
| 97 |
}); |
| 98 |
}; |
| 99 |
return std::max( |
| 100 |
// #ifndef/#define |
| 101 |
ConsumeHeaderGuardAndComment( |
| 102 |
[](const SourceManager &SM, Lexer &Lex, Token Tok) -> unsigned { |
| 103 |
if (checkAndConsumeDirectiveWithName(Lex, "ifndef", Tok)) { |
| 104 |
skipComments(Lex, Tok); |
| 105 |
if (checkAndConsumeDirectiveWithName(Lex, "define", Tok) && |
| 106 |
Tok.isAtStartOfLine()) |
| 107 |
return SM.getFileOffset(Tok.getLocation()); |
| 108 |
} |
| 109 |
return 0; |
| 110 |
}), |
| 111 |
// #pragma once |
| 112 |
ConsumeHeaderGuardAndComment( |
| 113 |
[](const SourceManager &SM, Lexer &Lex, Token Tok) -> unsigned { |
| 114 |
if (checkAndConsumeDirectiveWithName(Lex, "pragma", Tok, |
| 115 |
StringRef("once"))) |
| 116 |
return SM.getFileOffset(Tok.getLocation()); |
| 117 |
return 0; |
| 118 |
})); |
| 119 |
} |
| 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 |
bool checkAndConsumeInclusiveDirective(Lexer &Lex, Token &Tok) { |
| 126 |
auto Matched = [&]() { |
| 127 |
Lex.LexFromRawLexer(Tok); |
| 128 |
return true; |
| 129 |
}; |
| 130 |
if (Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) && |
| 131 |
Tok.is(tok::raw_identifier) && Tok.getRawIdentifier() == "include") { |
| 132 |
if (Lex.LexFromRawLexer(Tok)) |
| 133 |
return false; |
| 134 |
if (Tok.is(tok::string_literal)) |
| 135 |
return Matched(); |
| 136 |
if (Tok.is(tok::less)) { |
| 137 |
while (!Lex.LexFromRawLexer(Tok) && Tok.isNot(tok::greater)) { |
| 138 |
} |
| 139 |
if (Tok.is(tok::greater)) |
| 140 |
return Matched(); |
| 141 |
} |
| 142 |
} |
| 143 |
return false; |
| 144 |
} |
| 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 |
const IncludeStyle &Style) { |
| 161 |
return getOffsetAfterTokenSequence( |
| 162 |
FileName, Code, Style, |
| 163 |
[](const SourceManager &SM, Lexer &Lex, Token Tok) { |
| 164 |
skipComments(Lex, Tok); |
| 165 |
unsigned MaxOffset = SM.getFileOffset(Tok.getLocation()); |
| 166 |
while (checkAndConsumeInclusiveDirective(Lex, Tok)) |
| 167 |
MaxOffset = SM.getFileOffset(Tok.getLocation()); |
| 168 |
return MaxOffset; |
| 169 |
}); |
| 170 |
} |
| 171 |
|
| 172 |
inline StringRef trimInclude(StringRef IncludeName) { |
| 173 |
return IncludeName.trim("\"<>"); |
| 174 |
} |
| 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 |
StringRef matchingStem(llvm::StringRef Path) { |
| 185 |
StringRef Name = llvm::sys::path::filename(Path); |
| 186 |
return Name.substr(0, Name.find('.', 1)); |
| 187 |
} |
| 188 |
|
| 189 |
} // anonymous namespace |
| 190 |
|
| 191 |
IncludeCategoryManager::IncludeCategoryManager(const IncludeStyle &Style, |
| 192 |
StringRef FileName) |
| 193 |
: Style(Style), FileName(FileName) { |
| 194 |
for (const auto &Category : Style.IncludeCategories) { |
| 195 |
CategoryRegexs.emplace_back(Category.Regex, Category.RegexIsCaseSensitive |
| 196 |
? llvm::Regex::NoFlags |
| 197 |
: llvm::Regex::IgnoreCase); |
| 198 |
} |
| 199 |
IsMainFile = FileName.endswith(".c") || FileName.endswith(".cc") || |
| 200 |
FileName.endswith(".cpp") || FileName.endswith(".c++") || |
| 201 |
FileName.endswith(".cxx") || FileName.endswith(".m") || |
| 202 |
FileName.endswith(".mm"); |
| 203 |
if (!Style.IncludeIsMainSourceRegex.empty()) { |
| 204 |
llvm::Regex MainFileRegex(Style.IncludeIsMainSourceRegex); |
| 205 |
IsMainFile |= MainFileRegex.match(FileName); |
| 206 |
} |
| 207 |
} |
| 208 |
|
| 209 |
int IncludeCategoryManager::getIncludePriority(StringRef IncludeName, |
| 210 |
bool CheckMainHeader) const { |
| 211 |
int Ret = INT_MAX; |
| 212 |
for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) |
| 213 |
if (CategoryRegexs[i].match(IncludeName)) { |
| 214 |
Ret = Style.IncludeCategories[i].Priority; |
| 215 |
break; |
| 216 |
} |
| 217 |
if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName)) |
| 218 |
Ret = 0; |
| 219 |
return Ret; |
| 220 |
} |
| 221 |
|
| 222 |
int IncludeCategoryManager::getSortIncludePriority(StringRef IncludeName, |
| 223 |
bool CheckMainHeader) const { |
| 224 |
int Ret = INT_MAX; |
| 225 |
for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) |
| 226 |
if (CategoryRegexs[i].match(IncludeName)) { |
| 227 |
Ret = Style.IncludeCategories[i].SortPriority; |
| 228 |
if (Ret == 0) |
| 229 |
Ret = Style.IncludeCategories[i].Priority; |
| 230 |
break; |
| 231 |
} |
| 232 |
if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName)) |
| 233 |
Ret = 0; |
| 234 |
return Ret; |
| 235 |
} |
| 236 |
bool IncludeCategoryManager::isMainHeader(StringRef IncludeName) const { |
| 237 |
if (!IncludeName.startswith("\"")) |
| 238 |
return false; |
| 239 |
|
| 240 |
IncludeName = |
| 241 |
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 |
StringRef HeaderStem = llvm::sys::path::stem(IncludeName); |
| 245 |
StringRef FileStem = llvm::sys::path::stem(FileName); // foo.cu for foo.cu.cc |
| 246 |
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 |
StringRef Matching; |
| 256 |
if (MatchingFileStem.startswith_insensitive(HeaderStem)) |
| 257 |
Matching = MatchingFileStem; // example 1), 2) |
| 258 |
else if (FileStem.equals_insensitive(HeaderStem)) |
| 259 |
Matching = FileStem; // example 3) |
| 260 |
if (!Matching.empty()) { |
| 261 |
llvm::Regex MainIncludeRegex(HeaderStem.str() + Style.IncludeIsMainRegex, |
| 262 |
llvm::Regex::IgnoreCase); |
| 263 |
if (MainIncludeRegex.match(Matching)) |
| 264 |
return true; |
| 265 |
} |
| 266 |
return false; |
| 267 |
} |
| 268 |
|
| 269 |
const llvm::Regex HeaderIncludes::IncludeRegex(IncludeRegexPattern); |
| 270 |
|
| 271 |
HeaderIncludes::HeaderIncludes(StringRef FileName, StringRef Code, |
| 272 |
const IncludeStyle &Style) |
| 273 |
: FileName(FileName), Code(Code), FirstIncludeOffset(-1), |
| 274 |
MinInsertOffset( |
| 275 |
getOffsetAfterHeaderGuardsAndComments(FileName, Code, Style)), |
| 276 |
MaxInsertOffset(MinInsertOffset + |
| 277 |
getMaxHeaderInsertionOffset( |
| 278 |
FileName, Code.drop_front(MinInsertOffset), Style)), |
| 279 |
Categories(Style, FileName) { |
| 280 |
// Add 0 for main header and INT_MAX for headers that are not in any |
| 281 |
// category. |
| 282 |
Priorities = {0, INT_MAX}; |
| 283 |
for (const auto &Category : Style.IncludeCategories) |
| 284 |
Priorities.insert(Category.Priority); |
| 285 |
SmallVector<StringRef, 32> Lines; |
| 286 |
Code.drop_front(MinInsertOffset).split(Lines, "\n"); |
| 287 |
|
| 288 |
unsigned Offset = MinInsertOffset; |
| 289 |
unsigned NextLineOffset; |
| 290 |
SmallVector<StringRef, 4> Matches; |
| 291 |
for (auto Line : Lines) { |
| 292 |
NextLineOffset = std::min(Code.size(), Offset + Line.size() + 1); |
| 293 |
if (IncludeRegex.match(Line, &Matches)) { |
| 294 |
// If this is the last line without trailing newline, we need to make |
| 295 |
// sure we don't delete across the file boundary. |
| 296 |
addExistingInclude( |
| 297 |
Include(Matches[2], |
| 298 |
tooling::Range( |
| 299 |
Offset, std::min(Line.size() + 1, Code.size() - Offset)), |
| 300 |
Matches[1] == "import" ? tooling::IncludeDirective::Import |
| 301 |
: tooling::IncludeDirective::Include), |
| 302 |
NextLineOffset); |
| 303 |
} |
| 304 |
Offset = NextLineOffset; |
| 305 |
} |
| 306 |
|
| 307 |
// Populate CategoryEndOfssets: |
| 308 |
// - Ensure that CategoryEndOffset[Highest] is always populated. |
| 309 |
// - If CategoryEndOffset[Priority] isn't set, use the next higher value |
| 310 |
// that is set, up to CategoryEndOffset[Highest]. |
| 311 |
auto Highest = Priorities.begin(); |
| 312 |
if (CategoryEndOffsets.find(*Highest) == CategoryEndOffsets.end()) { |
| 313 |
if (FirstIncludeOffset >= 0) |
| 314 |
CategoryEndOffsets[*Highest] = FirstIncludeOffset; |
| 315 |
else |
| 316 |
CategoryEndOffsets[*Highest] = MinInsertOffset; |
| 317 |
} |
| 318 |
// By this point, CategoryEndOffset[Highest] is always set appropriately: |
| 319 |
// - to an appropriate location before/after existing #includes, or |
| 320 |
// - to right after the header guard, or |
| 321 |
// - to the beginning of the file. |
| 322 |
for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; ++I) |
| 323 |
if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end()) |
| 324 |
CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)]; |
| 325 |
} |
| 326 |
|
| 327 |
// \p Offset: the start of the line following this include directive. |
| 328 |
void HeaderIncludes::addExistingInclude(Include IncludeToAdd, |
| 329 |
unsigned NextLineOffset) { |
| 330 |
auto Iter = |
| 331 |
ExistingIncludes.try_emplace(trimInclude(IncludeToAdd.Name)).first; |
| 332 |
Iter->second.push_back(std::move(IncludeToAdd)); |
| 333 |
auto &CurInclude = Iter->second.back(); |
| 334 |
// The header name with quotes or angle brackets. |
| 335 |
// Only record the offset of current #include if we can insert after it. |
| 336 |
if (CurInclude.R.getOffset() <= MaxInsertOffset) { |
| 337 |
int Priority = Categories.getIncludePriority( |
| 338 |
CurInclude.Name, /*CheckMainHeader=*/FirstIncludeOffset < 0); |
| 339 |
CategoryEndOffsets[Priority] = NextLineOffset; |
| 340 |
IncludesByPriority[Priority].push_back(&CurInclude); |
| 341 |
if (FirstIncludeOffset < 0) |
| 342 |
FirstIncludeOffset = CurInclude.R.getOffset(); |
| 343 |
} |
| 344 |
} |
| 345 |
|
| 346 |
std::optional<tooling::Replacement> |
| 347 |
HeaderIncludes::insert(llvm::StringRef IncludeName, bool IsAngled, |
| 348 |
IncludeDirective Directive) const { |
| 349 |
assert(IncludeName == trimInclude(IncludeName)); |
| 350 |
// If a <header> ("header") already exists in code, "header" (<header>) with |
| 351 |
// different quotation and/or directive will still be inserted. |
| 352 |
// FIXME: figure out if this is the best behavior. |
| 353 |
auto It = ExistingIncludes.find(IncludeName); |
| 354 |
if (It != ExistingIncludes.end()) { |
| 355 |
for (const auto &Inc : It->second) |
| 356 |
if (Inc.Directive == Directive && |
| 357 |
((IsAngled && StringRef(Inc.Name).startswith("<")) || |
| 358 |
(!IsAngled && StringRef(Inc.Name).startswith("\"")))) |
| 359 |
return std::nullopt; |
| 360 |
} |
| 361 |
std::string Quoted = |
| 362 |
std::string(llvm::formatv(IsAngled ? "<{0}>" : "\"{0}\"", IncludeName)); |
| 363 |
StringRef QuotedName = Quoted; |
| 364 |
int Priority = Categories.getIncludePriority( |
| 365 |
QuotedName, /*CheckMainHeader=*/FirstIncludeOffset < 0); |
| 366 |
auto CatOffset = CategoryEndOffsets.find(Priority); |
| 367 |
assert(CatOffset != CategoryEndOffsets.end()); |
| 368 |
unsigned InsertOffset = CatOffset->second; // Fall back offset |
| 369 |
auto Iter = IncludesByPriority.find(Priority); |
| 370 |
if (Iter != IncludesByPriority.end()) { |
| 371 |
for (const auto *Inc : Iter->second) { |
| 372 |
if (QuotedName < Inc->Name) { |
| 373 |
InsertOffset = Inc->R.getOffset(); |
| 374 |
break; |
| 375 |
} |
| 376 |
} |
| 377 |
} |
| 378 |
assert(InsertOffset <= Code.size()); |
| 379 |
llvm::StringRef DirectiveSpelling = |
| 380 |
Directive == IncludeDirective::Include ? "include" : "import"; |
| 381 |
std::string NewInclude = |
| 382 |
llvm::formatv("#{0} {1}\n", DirectiveSpelling, QuotedName); |
| 383 |
// When inserting headers at end of the code, also append '\n' to the code |
| 384 |
// if it does not end with '\n'. |
| 385 |
// FIXME: when inserting multiple #includes at the end of code, only one |
| 386 |
// newline should be added. |
| 387 |
if (InsertOffset == Code.size() && (!Code.empty() && Code.back() != '\n')) |
| 388 |
NewInclude = "\n" + NewInclude; |
| 389 |
return tooling::Replacement(FileName, InsertOffset, 0, NewInclude); |
| 390 |
} |
| 391 |
|
| 392 |
tooling::Replacements HeaderIncludes::remove(llvm::StringRef IncludeName, |
| 393 |
bool IsAngled) const { |
| 394 |
assert(IncludeName == trimInclude(IncludeName)); |
| 395 |
tooling::Replacements Result; |
| 396 |
auto Iter = ExistingIncludes.find(IncludeName); |
| 397 |
if (Iter == ExistingIncludes.end()) |
| 398 |
return Result; |
| 399 |
for (const auto &Inc : Iter->second) { |
| 400 |
if ((IsAngled && StringRef(Inc.Name).startswith("\"")) || |
| 401 |
(!IsAngled && StringRef(Inc.Name).startswith("<"))) |
| 402 |
continue; |
| 403 |
llvm::Error Err = Result.add(tooling::Replacement( |
| 404 |
FileName, Inc.R.getOffset(), Inc.R.getLength(), "")); |
| 405 |
if (Err) { |
| 406 |
auto ErrMsg = "Unexpected conflicts in #include deletions: " + |
| 407 |
llvm::toString(std::move(Err)); |
| 408 |
llvm_unreachable(ErrMsg.c_str()); |
| 409 |
} |
| 410 |
} |
| 411 |
return Result; |
| 412 |
} |
| 413 |
|
| 414 |
} // namespace tooling |
| 415 |
} // namespace clang |