| 1 |
//===---------- IncludeSorter.cpp - clang-tidy ----------------------------===// |
| 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 "IncludeSorter.h" |
| 10 |
#include "clang/Basic/SourceManager.h" |
| 11 |
#include "clang/Lex/Lexer.h" |
| 12 |
#include <algorithm> |
| 13 |
#include <optional> |
| 14 |
|
| 15 |
namespace clang::tidy { |
| 16 |
namespace utils { |
| 17 |
|
| 18 |
namespace { |
| 19 |
|
| 20 |
StringRef removeFirstSuffix(StringRef Str, ArrayRef<const char *> Suffixes) { |
| 21 |
for (StringRef Suffix : Suffixes) { |
| 22 |
if (Str.ends_with(Suffix)) { |
| 23 |
return Str.substr(0, Str.size() - Suffix.size()); |
| 24 |
} |
| 25 |
} |
| 26 |
return Str; |
| 27 |
} |
| 28 |
|
| 29 |
StringRef makeCanonicalName(StringRef Str, IncludeSorter::IncludeStyle Style) { |
| 30 |
// The list of suffixes to remove from source file names to get the |
| 31 |
// "canonical" file names. |
| 32 |
// E.g. tools/sort_includes.cc and tools/sort_includes_test.cc |
| 33 |
// would both canonicalize to tools/sort_includes and tools/sort_includes.h |
| 34 |
// (once canonicalized) will match as being the main include file associated |
| 35 |
// with the source files. |
| 36 |
if (Style == IncludeSorter::IS_LLVM) { |
| 37 |
return removeFirstSuffix( |
| 38 |
removeFirstSuffix(Str, {".cc", ".cpp", ".c", ".h", ".hpp"}), {"Test"}); |
| 39 |
} |
| 40 |
if (Style == IncludeSorter::IS_Google_ObjC) { |
| 41 |
StringRef Canonical = |
| 42 |
removeFirstSuffix(removeFirstSuffix(Str, {".cc", ".cpp", ".c", ".h", |
| 43 |
".hpp", ".mm", ".m"}), |
| 44 |
{"_unittest", "_regtest", "_test", "Test"}); |
| 45 |
|
| 46 |
// Objective-C categories have a `+suffix` format, but should be grouped |
| 47 |
// with the file they are a category of. |
| 48 |
size_t StartIndex = Canonical.find_last_of('/'); |
| 49 |
if (StartIndex == StringRef::npos) { |
| 50 |
StartIndex = 0; |
| 51 |
} |
| 52 |
return Canonical.substr( |
| 53 |
0, Canonical.find_first_of('+', StartIndex)); |
| 54 |
} |
| 55 |
return removeFirstSuffix( |
| 56 |
removeFirstSuffix(Str, {".cc", ".cpp", ".c", ".h", ".hpp"}), |
| 57 |
{"_unittest", "_regtest", "_test"}); |
| 58 |
} |
| 59 |
|
| 60 |
// Scan to the end of the line and return the offset of the next line. |
| 61 |
size_t findNextLine(const char *Text) { |
| 62 |
size_t EOLIndex = std::strcspn(Text, "\n"); |
| 63 |
return Text[EOLIndex] == '\0' ? EOLIndex : EOLIndex + 1; |
| 64 |
} |
| 65 |
|
| 66 |
IncludeSorter::IncludeKinds |
| 67 |
determineIncludeKind(StringRef CanonicalFile, StringRef IncludeFile, |
| 68 |
bool IsAngled, IncludeSorter::IncludeStyle Style) { |
| 69 |
// Compute the two "canonical" forms of the include's filename sans extension. |
| 70 |
// The first form is the include's filename without ".h" or "-inl.h" at the |
| 71 |
// end. The second form is the first form with "/public/" in the file path |
| 72 |
// replaced by "/internal/". |
| 73 |
if (IsAngled) { |
| 74 |
// If the system include (<foo>) ends with ".h", then it is a normal C-style |
| 75 |
// include. Otherwise assume it is a C++-style extensionless include. |
| 76 |
return IncludeFile.ends_with(".h") ? IncludeSorter::IK_CSystemInclude |
| 77 |
: IncludeSorter::IK_CXXSystemInclude; |
| 78 |
} |
| 79 |
StringRef CanonicalInclude = makeCanonicalName(IncludeFile, Style); |
| 80 |
if (CanonicalFile.ends_with(CanonicalInclude) || |
| 81 |
CanonicalInclude.ends_with(CanonicalFile)) { |
| 82 |
return IncludeSorter::IK_MainTUInclude; |
| 83 |
} |
| 84 |
if ((Style == IncludeSorter::IS_Google) || |
| 85 |
(Style == IncludeSorter::IS_Google_ObjC)) { |
| 86 |
std::pair<StringRef, StringRef> Parts = CanonicalInclude.split("/public/"); |
| 87 |
StringRef FileCopy = CanonicalFile; |
| 88 |
if (FileCopy.consume_front(Parts.first) && |
| 89 |
FileCopy.consume_back(Parts.second)) { |
| 90 |
// Determine the kind of this inclusion. |
| 91 |
if (FileCopy == "/internal/" || FileCopy == "/proto/") { |
| 92 |
return IncludeSorter::IK_MainTUInclude; |
| 93 |
} |
| 94 |
} |
| 95 |
} |
| 96 |
if (Style == IncludeSorter::IS_Google_ObjC) { |
| 97 |
if (IncludeFile.ends_with(".generated.h") || |
| 98 |
IncludeFile.ends_with(".proto.h") || |
| 99 |
IncludeFile.ends_with(".pbobjc.h")) { |
| 100 |
return IncludeSorter::IK_GeneratedInclude; |
| 101 |
} |
| 102 |
} |
| 103 |
return IncludeSorter::IK_NonSystemInclude; |
| 104 |
} |
| 105 |
|
| 106 |
int compareHeaders(StringRef LHS, StringRef RHS, |
| 107 |
IncludeSorter::IncludeStyle Style) { |
| 108 |
if (Style == IncludeSorter::IncludeStyle::IS_Google_ObjC) { |
| 109 |
const std::pair<const char *, const char *> &Mismatch = |
| 110 |
std::mismatch(LHS.begin(), LHS.end(), RHS.begin(), RHS.end()); |
| 111 |
if ((Mismatch.first != LHS.end()) && (Mismatch.second != RHS.end())) { |
| 112 |
if ((*Mismatch.first == '.') && (*Mismatch.second == '+')) { |
| 113 |
return -1; |
| 114 |
} |
| 115 |
if ((*Mismatch.first == '+') && (*Mismatch.second == '.')) { |
| 116 |
return 1; |
| 117 |
} |
| 118 |
} |
| 119 |
} |
| 120 |
return LHS.compare(RHS); |
| 121 |
} |
| 122 |
|
| 123 |
} // namespace |
| 124 |
|
| 125 |
IncludeSorter::IncludeSorter(const SourceManager *SourceMgr, |
| 126 |
const FileID FileID, StringRef FileName, |
| 127 |
IncludeStyle Style) |
| 128 |
: SourceMgr(SourceMgr), Style(Style), CurrentFileID(FileID), |
| 129 |
CanonicalFile(makeCanonicalName(FileName, Style)) {} |
| 130 |
|
| 131 |
void IncludeSorter::addInclude(StringRef FileName, bool IsAngled, |
| 132 |
SourceLocation HashLocation, |
| 133 |
SourceLocation EndLocation) { |
| 134 |
int Offset = findNextLine(SourceMgr->getCharacterData(EndLocation)); |
| 135 |
|
| 136 |
// Record the relevant location information for this inclusion directive. |
| 137 |
auto &IncludeLocation = IncludeLocations[FileName]; |
| 138 |
IncludeLocation.push_back( |
| 139 |
SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset))); |
| 140 |
SourceLocations.push_back(IncludeLocation.back()); |
| 141 |
|
| 142 |
// Stop if this inclusion is a duplicate. |
| 143 |
if (IncludeLocation.size() > 1) |
| 144 |
return; |
| 145 |
|
| 146 |
// Add the included file's name to the appropriate bucket. |
| 147 |
IncludeKinds Kind = |
| 148 |
determineIncludeKind(CanonicalFile, FileName, IsAngled, Style); |
| 149 |
if (Kind != IK_InvalidInclude) |
| 150 |
IncludeBucket[Kind].push_back(FileName.str()); |
| 151 |
} |
| 152 |
|
| 153 |
std::optional<FixItHint> |
| 154 |
IncludeSorter::createIncludeInsertion(StringRef FileName, bool IsAngled) { |
| 155 |
std::string IncludeStmt; |
| 156 |
if (Style == IncludeStyle::IS_Google_ObjC) { |
| 157 |
IncludeStmt = IsAngled |
| 158 |
? llvm::Twine("#import <" + FileName + ">\n").str() |
| 159 |
: llvm::Twine("#import \"" + FileName + "\"\n").str(); |
| 160 |
} else { |
| 161 |
IncludeStmt = IsAngled |
| 162 |
? llvm::Twine("#include <" + FileName + ">\n").str() |
| 163 |
: llvm::Twine("#include \"" + FileName + "\"\n").str(); |
| 164 |
} |
| 165 |
if (SourceLocations.empty()) { |
| 166 |
// If there are no includes in this file, add it in the first line. |
| 167 |
// FIXME: insert after the file comment or the header guard, if present. |
| 168 |
IncludeStmt.append("\n"); |
| 169 |
return FixItHint::CreateInsertion( |
| 170 |
SourceMgr->getLocForStartOfFile(CurrentFileID), IncludeStmt); |
| 171 |
} |
| 172 |
|
| 173 |
auto IncludeKind = |
| 174 |
determineIncludeKind(CanonicalFile, FileName, IsAngled, Style); |
| 175 |
|
| 176 |
if (!IncludeBucket[IncludeKind].empty()) { |
| 177 |
for (const std::string &IncludeEntry : IncludeBucket[IncludeKind]) { |
| 178 |
if (compareHeaders(FileName, IncludeEntry, Style) < 0) { |
| 179 |
const auto &Location = IncludeLocations[IncludeEntry][0]; |
| 180 |
return FixItHint::CreateInsertion(Location.getBegin(), IncludeStmt); |
| 181 |
} |
| 182 |
if (FileName == IncludeEntry) { |
| 183 |
return std::nullopt; |
| 184 |
} |
| 185 |
} |
| 186 |
// FileName comes after all include entries in bucket, insert it after |
| 187 |
// last. |
| 188 |
const std::string &LastInclude = IncludeBucket[IncludeKind].back(); |
| 189 |
SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back(); |
| 190 |
return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(), |
| 191 |
IncludeStmt); |
| 192 |
} |
| 193 |
// Find the non-empty include bucket to be sorted directly above |
| 194 |
// 'IncludeKind'. If such a bucket exists, we'll want to sort the include |
| 195 |
// after that bucket. If no such bucket exists, find the first non-empty |
| 196 |
// include bucket in the file. In that case, we'll want to sort the include |
| 197 |
// before that bucket. |
| 198 |
IncludeKinds NonEmptyKind = IK_InvalidInclude; |
| 199 |
for (int I = IK_InvalidInclude - 1; I >= 0; --I) { |
| 200 |
if (!IncludeBucket[I].empty()) { |
| 201 |
NonEmptyKind = static_cast<IncludeKinds>(I); |
| 202 |
if (NonEmptyKind < IncludeKind) |
| 203 |
break; |
| 204 |
} |
| 205 |
} |
| 206 |
if (NonEmptyKind == IK_InvalidInclude) { |
| 207 |
return std::nullopt; |
| 208 |
} |
| 209 |
|
| 210 |
if (NonEmptyKind < IncludeKind) { |
| 211 |
// Create a block after. |
| 212 |
const std::string &LastInclude = IncludeBucket[NonEmptyKind].back(); |
| 213 |
SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back(); |
| 214 |
IncludeStmt = '\n' + IncludeStmt; |
| 215 |
return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(), |
| 216 |
IncludeStmt); |
| 217 |
} |
| 218 |
// Create a block before. |
| 219 |
const std::string &FirstInclude = IncludeBucket[NonEmptyKind][0]; |
| 220 |
SourceRange FirstIncludeLocation = IncludeLocations[FirstInclude].back(); |
| 221 |
IncludeStmt.append("\n"); |
| 222 |
return FixItHint::CreateInsertion(FirstIncludeLocation.getBegin(), |
| 223 |
IncludeStmt); |
| 224 |
} |
| 225 |
|
| 226 |
} // namespace utils |
| 227 |
|
| 228 |
llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>> |
| 229 |
OptionEnumMapping<utils::IncludeSorter::IncludeStyle>::getEnumMapping() { |
| 230 |
static constexpr std::pair<utils::IncludeSorter::IncludeStyle, StringRef> |
| 231 |
Mapping[] = {{utils::IncludeSorter::IS_LLVM, "llvm"}, |
| 232 |
{utils::IncludeSorter::IS_Google, "google"}, |
| 233 |
{utils::IncludeSorter::IS_Google_ObjC, "google-objc"}}; |
| 234 |
return {Mapping}; |
| 235 |
} |
| 236 |
} // namespace clang::tidy |