clang-tools 20.0.0git
IncludeSorter.cpp
Go to the documentation of this file.
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
15namespace clang::tidy {
16namespace utils {
17
18namespace {
19
20StringRef 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
29StringRef 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.
61size_t findNextLine(const char *Text) {
62 size_t EOLIndex = std::strcspn(Text, "\n");
63 return Text[EOLIndex] == '\0' ? EOLIndex : EOLIndex + 1;
64}
65
67determineIncludeKind(StringRef CanonicalFile, StringRef IncludeFile,
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
78 }
79 StringRef CanonicalInclude = makeCanonicalName(IncludeFile, Style);
80 if (CanonicalFile.ends_with(CanonicalInclude) ||
81 CanonicalInclude.ends_with(CanonicalFile)) {
83 }
84 if ((Style == IncludeSorter::IS_Google) ||
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/") {
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")) {
101 }
102 }
104}
105
106int compareHeaders(StringRef LHS, StringRef RHS,
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
125IncludeSorter::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
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.
148 determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
149 if (Kind != IK_InvalidInclude)
150 IncludeBucket[Kind].push_back(FileName.str());
151}
152
153std::optional<FixItHint>
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
228llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>>
230 static constexpr std::pair<utils::IncludeSorter::IncludeStyle, StringRef>
231 Mapping[] = {{utils::IncludeSorter::IS_LLVM, "llvm"},
233 {utils::IncludeSorter::IS_Google_ObjC, "google-objc"}};
234 return {Mapping};
235}
236} // namespace clang::tidy
std::string Suffix
Definition: AddUsing.cpp:132
BindArgumentKind Kind
size_t Offset
std::string Text
bool IsAngled
true if this was an include with angle brackets
StringRef FileName
static constexpr llvm::StringLiteral Suffixes
IncludeKinds
The classifications of inclusions, in the order they should be sorted.
Definition: IncludeSorter.h:29
@ IK_CSystemInclude
e.g. #include <stdio.h>
Definition: IncludeSorter.h:31
@ IK_NonSystemInclude
e.g. #include "bar.h"
Definition: IncludeSorter.h:33
@ IK_InvalidInclude
total number of valid IncludeKinds
Definition: IncludeSorter.h:35
@ IK_MainTUInclude
e.g. #include "foo.h" when editing foo.cc
Definition: IncludeSorter.h:30
@ IK_GeneratedInclude
e.g. #include "bar.proto.h"
Definition: IncludeSorter.h:34
@ IK_CXXSystemInclude
e.g. #include <vector>
Definition: IncludeSorter.h:32
void addInclude(StringRef FileName, bool IsAngled, SourceLocation HashLocation, SourceLocation EndLocation)
Adds the given include directive to the sorter.
IncludeSorter(const SourceManager *SourceMgr, const FileID FileID, StringRef FileName, IncludeStyle Style)
IncludeSorter constructor; takes the FileID and name of the file to be processed by the sorter.
IncludeStyle
Supported include styles.
Definition: IncludeSorter.h:26
std::optional< FixItHint > createIncludeInsertion(StringRef FileName, bool IsAngled)
Creates a quoted inclusion directive in the right sort order.
@ Canonical
The two mix because the types refer to the same CanonicalType, but we do not elaborate as to how.
static ArrayRef< std::pair< T, StringRef > > getEnumMapping()=delete