clang-tools 17.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.endswith(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.endswith(".h") ? IncludeSorter::IK_CSystemInclude
78 }
79 StringRef CanonicalInclude = makeCanonicalName(IncludeFile, Style);
80 if (CanonicalFile.endswith(CanonicalInclude)
81 || CanonicalInclude.endswith(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.equals("/internal/") ||
92 FileCopy.equals("/proto/")) {
94 }
95 }
96 }
97 if (Style == IncludeSorter::IS_Google_ObjC) {
98 if (IncludeFile.endswith(".generated.h") ||
99 IncludeFile.endswith(".proto.h") || IncludeFile.endswith(".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());
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 IncludeLocations[FileName].push_back(
138 SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset)));
139 SourceLocations.push_back(IncludeLocations[FileName].back());
140
141 // Stop if this inclusion is a duplicate.
142 if (IncludeLocations[FileName].size() > 1)
143 return;
144
145 // Add the included file's name to the appropriate bucket.
147 determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
148 if (Kind != IK_InvalidInclude)
149 IncludeBucket[Kind].push_back(FileName.str());
150}
151
152std::optional<FixItHint>
154 std::string IncludeStmt;
155 if (Style == IncludeStyle::IS_Google_ObjC) {
156 IncludeStmt = IsAngled
157 ? llvm::Twine("#import <" + FileName + ">\n").str()
158 : llvm::Twine("#import \"" + FileName + "\"\n").str();
159 } else {
160 IncludeStmt = IsAngled
161 ? llvm::Twine("#include <" + FileName + ">\n").str()
162 : llvm::Twine("#include \"" + FileName + "\"\n").str();
163 }
164 if (SourceLocations.empty()) {
165 // If there are no includes in this file, add it in the first line.
166 // FIXME: insert after the file comment or the header guard, if present.
167 IncludeStmt.append("\n");
168 return FixItHint::CreateInsertion(
169 SourceMgr->getLocForStartOfFile(CurrentFileID), IncludeStmt);
170 }
171
172 auto IncludeKind =
173 determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
174
175 if (!IncludeBucket[IncludeKind].empty()) {
176 for (const std::string &IncludeEntry : IncludeBucket[IncludeKind]) {
177 if (compareHeaders(FileName, IncludeEntry, Style) < 0) {
178 const auto &Location = IncludeLocations[IncludeEntry][0];
179 return FixItHint::CreateInsertion(Location.getBegin(), IncludeStmt);
180 }
181 if (FileName == IncludeEntry) {
182 return std::nullopt;
183 }
184 }
185 // FileName comes after all include entries in bucket, insert it after
186 // last.
187 const std::string &LastInclude = IncludeBucket[IncludeKind].back();
188 SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
189 return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
190 IncludeStmt);
191 }
192 // Find the non-empty include bucket to be sorted directly above
193 // 'IncludeKind'. If such a bucket exists, we'll want to sort the include
194 // after that bucket. If no such bucket exists, find the first non-empty
195 // include bucket in the file. In that case, we'll want to sort the include
196 // before that bucket.
197 IncludeKinds NonEmptyKind = IK_InvalidInclude;
198 for (int I = IK_InvalidInclude - 1; I >= 0; --I) {
199 if (!IncludeBucket[I].empty()) {
200 NonEmptyKind = static_cast<IncludeKinds>(I);
201 if (NonEmptyKind < IncludeKind)
202 break;
203 }
204 }
205 if (NonEmptyKind == IK_InvalidInclude) {
206 return std::nullopt;
207 }
208
209 if (NonEmptyKind < IncludeKind) {
210 // Create a block after.
211 const std::string &LastInclude = IncludeBucket[NonEmptyKind].back();
212 SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
213 IncludeStmt = '\n' + IncludeStmt;
214 return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
215 IncludeStmt);
216 }
217 // Create a block before.
218 const std::string &FirstInclude = IncludeBucket[NonEmptyKind][0];
219 SourceRange FirstIncludeLocation = IncludeLocations[FirstInclude].back();
220 IncludeStmt.append("\n");
221 return FixItHint::CreateInsertion(FirstIncludeLocation.getBegin(),
222 IncludeStmt);
223}
224
225} // namespace utils
226
227llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>>
229 static constexpr std::pair<utils::IncludeSorter::IncludeStyle, StringRef>
230 Mapping[] = {{utils::IncludeSorter::IS_LLVM, "llvm"},
232 {utils::IncludeSorter::IS_Google_ObjC, "google-objc"}};
233 return ArrayRef(Mapping);
234}
235} // namespace clang::tidy
std::string Suffix
Definition: AddUsing.cpp:113
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