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
14 namespace clang {
15 namespace tidy {
16 namespace utils {
17
18 namespace {
19
RemoveFirstSuffix(StringRef Str,ArrayRef<const char * > Suffixes)20 StringRef 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
MakeCanonicalName(StringRef Str,IncludeSorter::IncludeStyle Style)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.
FindNextLine(const char * Text)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
DetermineIncludeKind(StringRef CanonicalFile,StringRef IncludeFile,bool IsAngled,IncludeSorter::IncludeStyle Style)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.endswith(".h") ? IncludeSorter::IK_CSystemInclude
77 : IncludeSorter::IK_CXXSystemInclude;
78 }
79 StringRef CanonicalInclude = MakeCanonicalName(IncludeFile, Style);
80 if (CanonicalFile.endswith(CanonicalInclude)
81 || CanonicalInclude.endswith(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 std::string AltCanonicalInclude =
88 Parts.first.str() + "/internal/" + Parts.second.str();
89 std::string ProtoCanonicalInclude =
90 Parts.first.str() + "/proto/" + Parts.second.str();
91
92 // Determine the kind of this inclusion.
93 if (CanonicalFile.equals(AltCanonicalInclude) ||
94 CanonicalFile.equals(ProtoCanonicalInclude)) {
95 return IncludeSorter::IK_MainTUInclude;
96 }
97 }
98 if (Style == IncludeSorter::IS_Google_ObjC) {
99 if (IncludeFile.endswith(".generated.h") ||
100 IncludeFile.endswith(".proto.h") || IncludeFile.endswith(".pbobjc.h")) {
101 return IncludeSorter::IK_GeneratedInclude;
102 }
103 }
104 return IncludeSorter::IK_NonSystemInclude;
105 }
106
compareHeaders(StringRef LHS,StringRef RHS,IncludeSorter::IncludeStyle Style)107 int compareHeaders(StringRef LHS, StringRef RHS,
108 IncludeSorter::IncludeStyle Style) {
109 if (Style == IncludeSorter::IncludeStyle::IS_Google_ObjC) {
110 const std::pair<const char *, const char *> &Mismatch =
111 std::mismatch(LHS.begin(), LHS.end(), RHS.begin());
112 if ((Mismatch.first != LHS.end()) && (Mismatch.second != RHS.end())) {
113 if ((*Mismatch.first == '.') && (*Mismatch.second == '+')) {
114 return -1;
115 }
116 if ((*Mismatch.first == '+') && (*Mismatch.second == '.')) {
117 return 1;
118 }
119 }
120 }
121 return LHS.compare(RHS);
122 }
123
124 } // namespace
125
IncludeSorter(const SourceManager * SourceMgr,const FileID FileID,StringRef FileName,IncludeStyle Style)126 IncludeSorter::IncludeSorter(const SourceManager *SourceMgr,
127 const FileID FileID, StringRef FileName,
128 IncludeStyle Style)
129 : SourceMgr(SourceMgr), Style(Style), CurrentFileID(FileID),
130 CanonicalFile(MakeCanonicalName(FileName, Style)) {}
131
AddInclude(StringRef FileName,bool IsAngled,SourceLocation HashLocation,SourceLocation EndLocation)132 void IncludeSorter::AddInclude(StringRef FileName, bool IsAngled,
133 SourceLocation HashLocation,
134 SourceLocation EndLocation) {
135 int Offset = FindNextLine(SourceMgr->getCharacterData(EndLocation));
136
137 // Record the relevant location information for this inclusion directive.
138 IncludeLocations[FileName].push_back(
139 SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset)));
140 SourceLocations.push_back(IncludeLocations[FileName].back());
141
142 // Stop if this inclusion is a duplicate.
143 if (IncludeLocations[FileName].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
CreateIncludeInsertion(StringRef FileName,bool IsAngled)153 Optional<FixItHint> IncludeSorter::CreateIncludeInsertion(StringRef FileName,
154 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 } else if (FileName == IncludeEntry) {
182 return llvm::None;
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 llvm::None;
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
227 llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>>
getEnumMapping()228 OptionEnumMapping<utils::IncludeSorter::IncludeStyle>::getEnumMapping() {
229 static constexpr std::pair<utils::IncludeSorter::IncludeStyle, StringRef>
230 Mapping[] = {{utils::IncludeSorter::IS_LLVM, "llvm"},
231 {utils::IncludeSorter::IS_Google, "google"},
232 {utils::IncludeSorter::IS_Google_ObjC, "google-objc"}};
233 return makeArrayRef(Mapping);
234 }
235 } // namespace tidy
236 } // namespace clang
237