|
150
|
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/Lex/Lexer.h"
|
|
|
11
|
|
|
12 namespace clang {
|
|
|
13 namespace tidy {
|
|
|
14 namespace utils {
|
|
|
15
|
|
|
16 namespace {
|
|
|
17
|
|
|
18 StringRef RemoveFirstSuffix(StringRef Str, ArrayRef<const char *> Suffixes) {
|
|
|
19 for (StringRef Suffix : Suffixes) {
|
|
|
20 if (Str.endswith(Suffix)) {
|
|
|
21 return Str.substr(0, Str.size() - Suffix.size());
|
|
|
22 }
|
|
|
23 }
|
|
|
24 return Str;
|
|
|
25 }
|
|
|
26
|
|
|
27 StringRef MakeCanonicalName(StringRef Str, IncludeSorter::IncludeStyle Style) {
|
|
|
28 // The list of suffixes to remove from source file names to get the
|
|
|
29 // "canonical" file names.
|
|
|
30 // E.g. tools/sort_includes.cc and tools/sort_includes_test.cc
|
|
|
31 // would both canonicalize to tools/sort_includes and tools/sort_includes.h
|
|
|
32 // (once canonicalized) will match as being the main include file associated
|
|
|
33 // with the source files.
|
|
|
34 if (Style == IncludeSorter::IS_LLVM) {
|
|
|
35 return RemoveFirstSuffix(
|
|
|
36 RemoveFirstSuffix(Str, {".cc", ".cpp", ".c", ".h", ".hpp"}), {"Test"});
|
|
|
37 }
|
|
|
38 return RemoveFirstSuffix(
|
|
|
39 RemoveFirstSuffix(Str, {".cc", ".cpp", ".c", ".h", ".hpp"}),
|
|
|
40 {"_unittest", "_regtest", "_test"});
|
|
|
41 }
|
|
|
42
|
|
|
43 // Scan to the end of the line and return the offset of the next line.
|
|
|
44 size_t FindNextLine(const char *Text) {
|
|
|
45 size_t EOLIndex = std::strcspn(Text, "\n");
|
|
|
46 return Text[EOLIndex] == '\0' ? EOLIndex : EOLIndex + 1;
|
|
|
47 }
|
|
|
48
|
|
|
49 IncludeSorter::IncludeKinds
|
|
|
50 DetermineIncludeKind(StringRef CanonicalFile, StringRef IncludeFile,
|
|
|
51 bool IsAngled, IncludeSorter::IncludeStyle Style) {
|
|
|
52 // Compute the two "canonical" forms of the include's filename sans extension.
|
|
|
53 // The first form is the include's filename without ".h" or "-inl.h" at the
|
|
|
54 // end. The second form is the first form with "/public/" in the file path
|
|
|
55 // replaced by "/internal/".
|
|
|
56 if (IsAngled) {
|
|
|
57 // If the system include (<foo>) ends with ".h", then it is a normal C-style
|
|
|
58 // include. Otherwise assume it is a C++-style extensionless include.
|
|
|
59 return IncludeFile.endswith(".h") ? IncludeSorter::IK_CSystemInclude
|
|
|
60 : IncludeSorter::IK_CXXSystemInclude;
|
|
|
61 }
|
|
|
62 StringRef CanonicalInclude = MakeCanonicalName(IncludeFile, Style);
|
|
|
63 if (CanonicalFile.endswith(CanonicalInclude)
|
|
|
64 || CanonicalInclude.endswith(CanonicalFile)) {
|
|
|
65 return IncludeSorter::IK_MainTUInclude;
|
|
|
66 }
|
|
|
67 if (Style == IncludeSorter::IS_Google) {
|
|
|
68 std::pair<StringRef, StringRef> Parts = CanonicalInclude.split("/public/");
|
|
|
69 std::string AltCanonicalInclude =
|
|
|
70 Parts.first.str() + "/internal/" + Parts.second.str();
|
|
|
71 std::string ProtoCanonicalInclude =
|
|
|
72 Parts.first.str() + "/proto/" + Parts.second.str();
|
|
|
73
|
|
|
74 // Determine the kind of this inclusion.
|
|
|
75 if (CanonicalFile.equals(AltCanonicalInclude) ||
|
|
|
76 CanonicalFile.equals(ProtoCanonicalInclude)) {
|
|
|
77 return IncludeSorter::IK_MainTUInclude;
|
|
|
78 }
|
|
|
79 }
|
|
|
80 return IncludeSorter::IK_NonSystemInclude;
|
|
|
81 }
|
|
|
82
|
|
|
83 } // namespace
|
|
|
84
|
|
|
85 IncludeSorter::IncludeSorter(const SourceManager *SourceMgr,
|
|
|
86 const LangOptions *LangOpts, const FileID FileID,
|
|
|
87 StringRef FileName, IncludeStyle Style)
|
|
|
88 : SourceMgr(SourceMgr), LangOpts(LangOpts), Style(Style),
|
|
|
89 CurrentFileID(FileID), CanonicalFile(MakeCanonicalName(FileName, Style)) {
|
|
|
90 }
|
|
|
91
|
|
|
92 void IncludeSorter::AddInclude(StringRef FileName, bool IsAngled,
|
|
|
93 SourceLocation HashLocation,
|
|
|
94 SourceLocation EndLocation) {
|
|
|
95 int Offset = FindNextLine(SourceMgr->getCharacterData(EndLocation));
|
|
|
96
|
|
|
97 // Record the relevant location information for this inclusion directive.
|
|
|
98 IncludeLocations[FileName].push_back(
|
|
|
99 SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset)));
|
|
|
100 SourceLocations.push_back(IncludeLocations[FileName].back());
|
|
|
101
|
|
|
102 // Stop if this inclusion is a duplicate.
|
|
|
103 if (IncludeLocations[FileName].size() > 1)
|
|
|
104 return;
|
|
|
105
|
|
|
106 // Add the included file's name to the appropriate bucket.
|
|
|
107 IncludeKinds Kind =
|
|
|
108 DetermineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
|
|
|
109 if (Kind != IK_InvalidInclude)
|
|
|
110 IncludeBucket[Kind].push_back(FileName.str());
|
|
|
111 }
|
|
|
112
|
|
|
113 Optional<FixItHint> IncludeSorter::CreateIncludeInsertion(StringRef FileName,
|
|
|
114 bool IsAngled) {
|
|
|
115 std::string IncludeStmt =
|
|
|
116 IsAngled ? llvm::Twine("#include <" + FileName + ">\n").str()
|
|
|
117 : llvm::Twine("#include \"" + FileName + "\"\n").str();
|
|
|
118 if (SourceLocations.empty()) {
|
|
|
119 // If there are no includes in this file, add it in the first line.
|
|
|
120 // FIXME: insert after the file comment or the header guard, if present.
|
|
|
121 IncludeStmt.append("\n");
|
|
|
122 return FixItHint::CreateInsertion(
|
|
|
123 SourceMgr->getLocForStartOfFile(CurrentFileID), IncludeStmt);
|
|
|
124 }
|
|
|
125
|
|
|
126 auto IncludeKind =
|
|
|
127 DetermineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
|
|
|
128
|
|
|
129 if (!IncludeBucket[IncludeKind].empty()) {
|
|
|
130 for (const std::string &IncludeEntry : IncludeBucket[IncludeKind]) {
|
|
|
131 if (FileName < IncludeEntry) {
|
|
|
132 const auto &Location = IncludeLocations[IncludeEntry][0];
|
|
|
133 return FixItHint::CreateInsertion(Location.getBegin(), IncludeStmt);
|
|
|
134 } else if (FileName == IncludeEntry) {
|
|
|
135 return llvm::None;
|
|
|
136 }
|
|
|
137 }
|
|
|
138 // FileName comes after all include entries in bucket, insert it after
|
|
|
139 // last.
|
|
|
140 const std::string &LastInclude = IncludeBucket[IncludeKind].back();
|
|
|
141 SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
|
|
|
142 return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
|
|
|
143 IncludeStmt);
|
|
|
144 }
|
|
|
145 // Find the non-empty include bucket to be sorted directly above
|
|
|
146 // 'IncludeKind'. If such a bucket exists, we'll want to sort the include
|
|
|
147 // after that bucket. If no such bucket exists, find the first non-empty
|
|
|
148 // include bucket in the file. In that case, we'll want to sort the include
|
|
|
149 // before that bucket.
|
|
|
150 IncludeKinds NonEmptyKind = IK_InvalidInclude;
|
|
|
151 for (int i = IK_InvalidInclude - 1; i >= 0; --i) {
|
|
|
152 if (!IncludeBucket[i].empty()) {
|
|
|
153 NonEmptyKind = static_cast<IncludeKinds>(i);
|
|
|
154 if (NonEmptyKind < IncludeKind)
|
|
|
155 break;
|
|
|
156 }
|
|
|
157 }
|
|
|
158 if (NonEmptyKind == IK_InvalidInclude) {
|
|
|
159 return llvm::None;
|
|
|
160 }
|
|
|
161
|
|
|
162 if (NonEmptyKind < IncludeKind) {
|
|
|
163 // Create a block after.
|
|
|
164 const std::string &LastInclude = IncludeBucket[NonEmptyKind].back();
|
|
|
165 SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
|
|
|
166 IncludeStmt = '\n' + IncludeStmt;
|
|
|
167 return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
|
|
|
168 IncludeStmt);
|
|
|
169 }
|
|
|
170 // Create a block before.
|
|
|
171 const std::string &FirstInclude = IncludeBucket[NonEmptyKind][0];
|
|
|
172 SourceRange FirstIncludeLocation = IncludeLocations[FirstInclude].back();
|
|
|
173 IncludeStmt.append("\n");
|
|
|
174 return FixItHint::CreateInsertion(FirstIncludeLocation.getBegin(),
|
|
|
175 IncludeStmt);
|
|
|
176 }
|
|
|
177
|
|
|
178 std::vector<FixItHint> IncludeSorter::GetEdits() {
|
|
|
179 if (SourceLocations.empty())
|
|
|
180 return {};
|
|
|
181
|
|
|
182 typedef std::map<int, std::pair<SourceRange, std::string>>
|
|
|
183 FileLineToSourceEditMap;
|
|
|
184 FileLineToSourceEditMap Edits;
|
|
|
185 auto SourceLocationIterator = SourceLocations.begin();
|
|
|
186 auto SourceLocationIteratorEnd = SourceLocations.end();
|
|
|
187
|
|
|
188 // Compute the Edits that need to be done to each line to add, replace, or
|
|
|
189 // delete inclusions.
|
|
|
190 for (int IncludeKind = 0; IncludeKind < IK_InvalidInclude; ++IncludeKind) {
|
|
|
191 std::sort(IncludeBucket[IncludeKind].begin(),
|
|
|
192 IncludeBucket[IncludeKind].end());
|
|
|
193 for (const auto &IncludeEntry : IncludeBucket[IncludeKind]) {
|
|
|
194 auto &Location = IncludeLocations[IncludeEntry];
|
|
|
195 SourceRangeVector::iterator LocationIterator = Location.begin();
|
|
|
196 SourceRangeVector::iterator LocationIteratorEnd = Location.end();
|
|
|
197 SourceRange FirstLocation = *LocationIterator;
|
|
|
198
|
|
|
199 // If the first occurrence of a particular include is on the current
|
|
|
200 // source line we are examining, leave it alone.
|
|
|
201 if (FirstLocation == *SourceLocationIterator)
|
|
|
202 ++LocationIterator;
|
|
|
203
|
|
|
204 // Add the deletion Edits for any (remaining) instances of this inclusion,
|
|
|
205 // and remove their Locations from the source Locations to be processed.
|
|
|
206 for (; LocationIterator != LocationIteratorEnd; ++LocationIterator) {
|
|
|
207 int LineNumber =
|
|
|
208 SourceMgr->getSpellingLineNumber(LocationIterator->getBegin());
|
|
|
209 Edits[LineNumber] = std::make_pair(*LocationIterator, "");
|
|
|
210 SourceLocationIteratorEnd =
|
|
|
211 std::remove(SourceLocationIterator, SourceLocationIteratorEnd,
|
|
|
212 *LocationIterator);
|
|
|
213 }
|
|
|
214
|
|
|
215 if (FirstLocation == *SourceLocationIterator) {
|
|
|
216 // Do nothing except move to the next source Location (Location of an
|
|
|
217 // inclusion in the original, unchanged source file).
|
|
|
218 ++SourceLocationIterator;
|
|
|
219 continue;
|
|
|
220 }
|
|
|
221
|
|
|
222 // Add (or append to) the replacement text for this line in source file.
|
|
|
223 int LineNumber =
|
|
|
224 SourceMgr->getSpellingLineNumber(SourceLocationIterator->getBegin());
|
|
|
225 if (Edits.find(LineNumber) == Edits.end()) {
|
|
|
226 Edits[LineNumber].first =
|
|
|
227 SourceRange(SourceLocationIterator->getBegin());
|
|
|
228 }
|
|
|
229 StringRef SourceText = Lexer::getSourceText(
|
|
|
230 CharSourceRange::getCharRange(FirstLocation), *SourceMgr, *LangOpts);
|
|
|
231 Edits[LineNumber].second.append(SourceText.data(), SourceText.size());
|
|
|
232 }
|
|
|
233
|
|
|
234 // Clear the bucket.
|
|
|
235 IncludeBucket[IncludeKind].clear();
|
|
|
236 }
|
|
|
237
|
|
|
238 // Go through the single-line Edits and combine them into blocks of Edits.
|
|
|
239 int CurrentEndLine = 0;
|
|
|
240 SourceRange CurrentRange;
|
|
|
241 std::string CurrentText;
|
|
|
242 std::vector<FixItHint> Fixes;
|
|
|
243 for (const auto &LineEdit : Edits) {
|
|
|
244 // If the current edit is on the next line after the previous edit, add it
|
|
|
245 // to the current block edit.
|
|
|
246 if (LineEdit.first == CurrentEndLine + 1 &&
|
|
|
247 CurrentRange.getBegin() != CurrentRange.getEnd()) {
|
|
|
248 SourceRange EditRange = LineEdit.second.first;
|
|
|
249 if (EditRange.getBegin() != EditRange.getEnd()) {
|
|
|
250 ++CurrentEndLine;
|
|
|
251 CurrentRange.setEnd(EditRange.getEnd());
|
|
|
252 }
|
|
|
253 CurrentText += LineEdit.second.second;
|
|
|
254 // Otherwise report the current block edit and start a new block.
|
|
|
255 } else {
|
|
|
256 if (CurrentEndLine) {
|
|
|
257 Fixes.push_back(FixItHint::CreateReplacement(
|
|
|
258 CharSourceRange::getCharRange(CurrentRange), CurrentText));
|
|
|
259 }
|
|
|
260
|
|
|
261 CurrentEndLine = LineEdit.first;
|
|
|
262 CurrentRange = LineEdit.second.first;
|
|
|
263 CurrentText = LineEdit.second.second;
|
|
|
264 }
|
|
|
265 }
|
|
|
266 // Finally, report the current block edit if there is one.
|
|
|
267 if (CurrentEndLine) {
|
|
|
268 Fixes.push_back(FixItHint::CreateReplacement(
|
|
|
269 CharSourceRange::getCharRange(CurrentRange), CurrentText));
|
|
|
270 }
|
|
|
271
|
|
|
272 // Reset the remaining internal state.
|
|
|
273 SourceLocations.clear();
|
|
|
274 IncludeLocations.clear();
|
|
|
275 return Fixes;
|
|
|
276 }
|
|
|
277
|
|
173
|
278 llvm::ArrayRef<std::pair<StringRef, IncludeSorter::IncludeStyle>>
|
|
|
279 IncludeSorter::getMapping() {
|
|
|
280 static constexpr std::pair<StringRef, IncludeSorter::IncludeStyle> Mapping[] =
|
|
|
281 {{"llvm", IS_LLVM}, {"google", IS_Google}};
|
|
|
282 return makeArrayRef(Mapping);
|
|
150
|
283 }
|
|
|
284
|
|
|
285 } // namespace utils
|
|
|
286 } // namespace tidy
|
|
|
287 } // namespace clang
|
