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