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 | |
15 | namespace clang::tidy { |
16 | namespace utils { |
17 | |
18 | namespace { |
19 | |
20 | StringRef removeFirstSuffix(StringRef Str, ArrayRef<const char *> Suffixes) { |
21 | for (StringRef Suffix : Suffixes) { |
22 | if (Str.consume_back(Suffix)) |
23 | return Str; |
24 | } |
25 | return Str; |
26 | } |
27 | |
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 | Str: removeFirstSuffix(Str, Suffixes: {".cc" , ".cpp" , ".c" , ".h" , ".hpp" }), Suffixes: {"Test" }); |
38 | } |
39 | if (Style == IncludeSorter::IS_Google_ObjC) { |
40 | StringRef Canonical = |
41 | removeFirstSuffix(Str: removeFirstSuffix(Str, Suffixes: {".cc" , ".cpp" , ".c" , ".h" , |
42 | ".hpp" , ".mm" , ".m" }), |
43 | Suffixes: {"_unittest" , "_regtest" , "_test" , "Test" }); |
44 | |
45 | // Objective-C categories have a `+suffix` format, but should be grouped |
46 | // with the file they are a category of. |
47 | size_t StartIndex = Canonical.find_last_of(C: '/'); |
48 | if (StartIndex == StringRef::npos) { |
49 | StartIndex = 0; |
50 | } |
51 | return Canonical.substr(Start: 0, N: Canonical.find_first_of(C: '+', From: StartIndex)); |
52 | } |
53 | return removeFirstSuffix( |
54 | Str: removeFirstSuffix(Str, Suffixes: {".cc" , ".cpp" , ".c" , ".h" , ".hpp" }), |
55 | Suffixes: {"_unittest" , "_regtest" , "_test" }); |
56 | } |
57 | |
58 | // Scan to the end of the line and return the offset of the next line. |
59 | size_t findNextLine(const char *Text) { |
60 | size_t EOLIndex = std::strcspn(s: Text, reject: "\n" ); |
61 | return Text[EOLIndex] == '\0' ? EOLIndex : EOLIndex + 1; |
62 | } |
63 | |
64 | IncludeSorter::IncludeKinds |
65 | determineIncludeKind(StringRef CanonicalFile, StringRef IncludeFile, |
66 | bool IsAngled, IncludeSorter::IncludeStyle Style) { |
67 | // Compute the two "canonical" forms of the include's filename sans extension. |
68 | // The first form is the include's filename without ".h" or "-inl.h" at the |
69 | // end. The second form is the first form with "/public/" in the file path |
70 | // replaced by "/internal/". |
71 | if (IsAngled) { |
72 | // If the system include (<foo>) ends with ".h", then it is a normal C-style |
73 | // include. Otherwise assume it is a C++-style extensionless include. |
74 | return IncludeFile.ends_with(Suffix: ".h" ) ? IncludeSorter::IK_CSystemInclude |
75 | : IncludeSorter::IK_CXXSystemInclude; |
76 | } |
77 | StringRef CanonicalInclude = makeCanonicalName(Str: IncludeFile, Style); |
78 | if (CanonicalFile.ends_with(Suffix: CanonicalInclude) || |
79 | CanonicalInclude.ends_with(Suffix: CanonicalFile)) { |
80 | return IncludeSorter::IK_MainTUInclude; |
81 | } |
82 | if ((Style == IncludeSorter::IS_Google) || |
83 | (Style == IncludeSorter::IS_Google_ObjC)) { |
84 | std::pair<StringRef, StringRef> Parts = CanonicalInclude.split(Separator: "/public/" ); |
85 | StringRef FileCopy = CanonicalFile; |
86 | if (FileCopy.consume_front(Prefix: Parts.first) && |
87 | FileCopy.consume_back(Suffix: Parts.second)) { |
88 | // Determine the kind of this inclusion. |
89 | if (FileCopy == "/internal/" || FileCopy == "/proto/" ) { |
90 | return IncludeSorter::IK_MainTUInclude; |
91 | } |
92 | } |
93 | } |
94 | if (Style == IncludeSorter::IS_Google_ObjC) { |
95 | if (IncludeFile.ends_with(Suffix: ".generated.h" ) || |
96 | IncludeFile.ends_with(Suffix: ".proto.h" ) || |
97 | IncludeFile.ends_with(Suffix: ".pbobjc.h" )) { |
98 | return IncludeSorter::IK_GeneratedInclude; |
99 | } |
100 | } |
101 | return IncludeSorter::IK_NonSystemInclude; |
102 | } |
103 | |
104 | int (StringRef LHS, StringRef RHS, |
105 | IncludeSorter::IncludeStyle Style) { |
106 | if (Style == IncludeSorter::IncludeStyle::IS_Google_ObjC) { |
107 | const std::pair<const char *, const char *> &Mismatch = |
108 | std::mismatch(first1: LHS.begin(), last1: LHS.end(), first2: RHS.begin(), last2: RHS.end()); |
109 | if ((Mismatch.first != LHS.end()) && (Mismatch.second != RHS.end())) { |
110 | if ((*Mismatch.first == '.') && (*Mismatch.second == '+')) { |
111 | return -1; |
112 | } |
113 | if ((*Mismatch.first == '+') && (*Mismatch.second == '.')) { |
114 | return 1; |
115 | } |
116 | } |
117 | } |
118 | return LHS.compare(RHS); |
119 | } |
120 | |
121 | } // namespace |
122 | |
123 | IncludeSorter::IncludeSorter(const SourceManager *SourceMgr, |
124 | const FileID FileID, StringRef FileName, |
125 | IncludeStyle Style) |
126 | : SourceMgr(SourceMgr), Style(Style), CurrentFileID(FileID), |
127 | CanonicalFile(makeCanonicalName(Str: FileName, Style)) {} |
128 | |
129 | void IncludeSorter::addInclude(StringRef FileName, bool IsAngled, |
130 | SourceLocation HashLocation, |
131 | SourceLocation EndLocation) { |
132 | int Offset = findNextLine(Text: SourceMgr->getCharacterData(SL: EndLocation)); |
133 | |
134 | // Record the relevant location information for this inclusion directive. |
135 | auto &IncludeLocation = IncludeLocations[FileName]; |
136 | IncludeLocation.push_back( |
137 | Elt: SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset))); |
138 | SourceLocations.push_back(Elt: IncludeLocation.back()); |
139 | |
140 | // Stop if this inclusion is a duplicate. |
141 | if (IncludeLocation.size() > 1) |
142 | return; |
143 | |
144 | // Add the included file's name to the appropriate bucket. |
145 | IncludeKinds Kind = |
146 | determineIncludeKind(CanonicalFile, IncludeFile: FileName, IsAngled, Style); |
147 | if (Kind != IK_InvalidInclude) |
148 | IncludeBucket[Kind].push_back(Elt: FileName.str()); |
149 | } |
150 | |
151 | std::optional<FixItHint> |
152 | IncludeSorter::createIncludeInsertion(StringRef FileName, bool IsAngled) { |
153 | std::string IncludeStmt; |
154 | if (Style == IncludeStyle::IS_Google_ObjC) { |
155 | IncludeStmt = IsAngled |
156 | ? llvm::Twine("#import <" + FileName + ">\n" ).str() |
157 | : llvm::Twine("#import \"" + FileName + "\"\n" ).str(); |
158 | } else { |
159 | IncludeStmt = IsAngled |
160 | ? llvm::Twine("#include <" + FileName + ">\n" ).str() |
161 | : llvm::Twine("#include \"" + FileName + "\"\n" ).str(); |
162 | } |
163 | if (SourceLocations.empty()) { |
164 | // If there are no includes in this file, add it in the first line. |
165 | // FIXME: insert after the file comment or the header guard, if present. |
166 | IncludeStmt.append(s: "\n" ); |
167 | return FixItHint::CreateInsertion( |
168 | InsertionLoc: SourceMgr->getLocForStartOfFile(FID: CurrentFileID), Code: IncludeStmt); |
169 | } |
170 | |
171 | auto IncludeKind = |
172 | determineIncludeKind(CanonicalFile, IncludeFile: FileName, IsAngled, Style); |
173 | |
174 | if (!IncludeBucket[IncludeKind].empty()) { |
175 | for (const std::string &IncludeEntry : IncludeBucket[IncludeKind]) { |
176 | if (compareHeaders(LHS: FileName, RHS: IncludeEntry, Style) < 0) { |
177 | const auto &Location = IncludeLocations[IncludeEntry][0]; |
178 | return FixItHint::CreateInsertion(InsertionLoc: Location.getBegin(), Code: IncludeStmt); |
179 | } |
180 | if (FileName == IncludeEntry) { |
181 | return std::nullopt; |
182 | } |
183 | } |
184 | // FileName comes after all include entries in bucket, insert it after |
185 | // last. |
186 | const std::string &LastInclude = IncludeBucket[IncludeKind].back(); |
187 | SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back(); |
188 | return FixItHint::CreateInsertion(InsertionLoc: LastIncludeLocation.getEnd(), |
189 | Code: IncludeStmt); |
190 | } |
191 | // Find the non-empty include bucket to be sorted directly above |
192 | // 'IncludeKind'. If such a bucket exists, we'll want to sort the include |
193 | // after that bucket. If no such bucket exists, find the first non-empty |
194 | // include bucket in the file. In that case, we'll want to sort the include |
195 | // before that bucket. |
196 | IncludeKinds NonEmptyKind = IK_InvalidInclude; |
197 | for (int I = IK_InvalidInclude - 1; I >= 0; --I) { |
198 | if (!IncludeBucket[I].empty()) { |
199 | NonEmptyKind = static_cast<IncludeKinds>(I); |
200 | if (NonEmptyKind < IncludeKind) |
201 | break; |
202 | } |
203 | } |
204 | if (NonEmptyKind == IK_InvalidInclude) { |
205 | return std::nullopt; |
206 | } |
207 | |
208 | if (NonEmptyKind < IncludeKind) { |
209 | // Create a block after. |
210 | const std::string &LastInclude = IncludeBucket[NonEmptyKind].back(); |
211 | SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back(); |
212 | IncludeStmt = '\n' + IncludeStmt; |
213 | return FixItHint::CreateInsertion(InsertionLoc: LastIncludeLocation.getEnd(), |
214 | Code: IncludeStmt); |
215 | } |
216 | // Create a block before. |
217 | const std::string &FirstInclude = IncludeBucket[NonEmptyKind][0]; |
218 | SourceRange FirstIncludeLocation = IncludeLocations[FirstInclude].back(); |
219 | IncludeStmt.append(s: "\n" ); |
220 | return FixItHint::CreateInsertion(InsertionLoc: FirstIncludeLocation.getBegin(), |
221 | Code: IncludeStmt); |
222 | } |
223 | |
224 | } // namespace utils |
225 | |
226 | llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>> |
227 | OptionEnumMapping<utils::IncludeSorter::IncludeStyle>::getEnumMapping() { |
228 | static constexpr std::pair<utils::IncludeSorter::IncludeStyle, StringRef> |
229 | Mapping[] = {{utils::IncludeSorter::IS_LLVM, "llvm" }, |
230 | {utils::IncludeSorter::IS_Google, "google" }, |
231 | {utils::IncludeSorter::IS_Google_ObjC, "google-objc" }}; |
232 | return {Mapping}; |
233 | } |
234 | } // namespace clang::tidy |
235 | |