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.ends_with(Suffix)) {
23 return Str.substr(Start: 0, N: 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 Str: removeFirstSuffix(Str, Suffixes: {".cc", ".cpp", ".c", ".h", ".hpp"}), Suffixes: {"Test"});
39 }
40 if (Style == IncludeSorter::IS_Google_ObjC) {
41 StringRef Canonical =
42 removeFirstSuffix(Str: removeFirstSuffix(Str, Suffixes: {".cc", ".cpp", ".c", ".h",
43 ".hpp", ".mm", ".m"}),
44 Suffixes: {"_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(C: '/');
49 if (StartIndex == StringRef::npos) {
50 StartIndex = 0;
51 }
52 return Canonical.substr(
53 Start: 0, N: Canonical.find_first_of(C: '+', From: StartIndex));
54 }
55 return removeFirstSuffix(
56 Str: removeFirstSuffix(Str, Suffixes: {".cc", ".cpp", ".c", ".h", ".hpp"}),
57 Suffixes: {"_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(s: Text, reject: "\n");
63 return Text[EOLIndex] == '\0' ? EOLIndex : EOLIndex + 1;
64}
65
66IncludeSorter::IncludeKinds
67determineIncludeKind(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.ends_with(Suffix: ".h") ? IncludeSorter::IK_CSystemInclude
77 : IncludeSorter::IK_CXXSystemInclude;
78 }
79 StringRef CanonicalInclude = makeCanonicalName(Str: IncludeFile, Style);
80 if (CanonicalFile.ends_with(Suffix: CanonicalInclude) ||
81 CanonicalInclude.ends_with(Suffix: 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(Separator: "/public/");
87 StringRef FileCopy = CanonicalFile;
88 if (FileCopy.consume_front(Prefix: Parts.first) &&
89 FileCopy.consume_back(Suffix: Parts.second)) {
90 // Determine the kind of this inclusion.
91 if (FileCopy.equals(RHS: "/internal/") ||
92 FileCopy.equals(RHS: "/proto/")) {
93 return IncludeSorter::IK_MainTUInclude;
94 }
95 }
96 }
97 if (Style == IncludeSorter::IS_Google_ObjC) {
98 if (IncludeFile.ends_with(Suffix: ".generated.h") ||
99 IncludeFile.ends_with(Suffix: ".proto.h") ||
100 IncludeFile.ends_with(Suffix: ".pbobjc.h")) {
101 return IncludeSorter::IK_GeneratedInclude;
102 }
103 }
104 return IncludeSorter::IK_NonSystemInclude;
105}
106
107int 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(first1: LHS.begin(), last1: LHS.end(), first2: RHS.begin(), last2: RHS.end());
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
126IncludeSorter::IncludeSorter(const SourceManager *SourceMgr,
127 const FileID FileID, StringRef FileName,
128 IncludeStyle Style)
129 : SourceMgr(SourceMgr), Style(Style), CurrentFileID(FileID),
130 CanonicalFile(makeCanonicalName(Str: FileName, Style)) {}
131
132void IncludeSorter::addInclude(StringRef FileName, bool IsAngled,
133 SourceLocation HashLocation,
134 SourceLocation EndLocation) {
135 int Offset = findNextLine(Text: SourceMgr->getCharacterData(SL: EndLocation));
136
137 // Record the relevant location information for this inclusion directive.
138 auto &IncludeLocation = IncludeLocations[FileName];
139 IncludeLocation.push_back(
140 Elt: SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset)));
141 SourceLocations.push_back(Elt: IncludeLocation.back());
142
143 // Stop if this inclusion is a duplicate.
144 if (IncludeLocation.size() > 1)
145 return;
146
147 // Add the included file's name to the appropriate bucket.
148 IncludeKinds Kind =
149 determineIncludeKind(CanonicalFile, IncludeFile: FileName, IsAngled, Style);
150 if (Kind != IK_InvalidInclude)
151 IncludeBucket[Kind].push_back(Elt: FileName.str());
152}
153
154std::optional<FixItHint>
155IncludeSorter::createIncludeInsertion(StringRef FileName, bool IsAngled) {
156 std::string IncludeStmt;
157 if (Style == IncludeStyle::IS_Google_ObjC) {
158 IncludeStmt = IsAngled
159 ? llvm::Twine("#import <" + FileName + ">\n").str()
160 : llvm::Twine("#import \"" + FileName + "\"\n").str();
161 } else {
162 IncludeStmt = IsAngled
163 ? llvm::Twine("#include <" + FileName + ">\n").str()
164 : llvm::Twine("#include \"" + FileName + "\"\n").str();
165 }
166 if (SourceLocations.empty()) {
167 // If there are no includes in this file, add it in the first line.
168 // FIXME: insert after the file comment or the header guard, if present.
169 IncludeStmt.append(s: "\n");
170 return FixItHint::CreateInsertion(
171 InsertionLoc: SourceMgr->getLocForStartOfFile(FID: CurrentFileID), Code: IncludeStmt);
172 }
173
174 auto IncludeKind =
175 determineIncludeKind(CanonicalFile, IncludeFile: FileName, IsAngled, Style);
176
177 if (!IncludeBucket[IncludeKind].empty()) {
178 for (const std::string &IncludeEntry : IncludeBucket[IncludeKind]) {
179 if (compareHeaders(LHS: FileName, RHS: IncludeEntry, Style) < 0) {
180 const auto &Location = IncludeLocations[IncludeEntry][0];
181 return FixItHint::CreateInsertion(InsertionLoc: Location.getBegin(), Code: IncludeStmt);
182 }
183 if (FileName == IncludeEntry) {
184 return std::nullopt;
185 }
186 }
187 // FileName comes after all include entries in bucket, insert it after
188 // last.
189 const std::string &LastInclude = IncludeBucket[IncludeKind].back();
190 SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
191 return FixItHint::CreateInsertion(InsertionLoc: LastIncludeLocation.getEnd(),
192 Code: IncludeStmt);
193 }
194 // Find the non-empty include bucket to be sorted directly above
195 // 'IncludeKind'. If such a bucket exists, we'll want to sort the include
196 // after that bucket. If no such bucket exists, find the first non-empty
197 // include bucket in the file. In that case, we'll want to sort the include
198 // before that bucket.
199 IncludeKinds NonEmptyKind = IK_InvalidInclude;
200 for (int I = IK_InvalidInclude - 1; I >= 0; --I) {
201 if (!IncludeBucket[I].empty()) {
202 NonEmptyKind = static_cast<IncludeKinds>(I);
203 if (NonEmptyKind < IncludeKind)
204 break;
205 }
206 }
207 if (NonEmptyKind == IK_InvalidInclude) {
208 return std::nullopt;
209 }
210
211 if (NonEmptyKind < IncludeKind) {
212 // Create a block after.
213 const std::string &LastInclude = IncludeBucket[NonEmptyKind].back();
214 SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
215 IncludeStmt = '\n' + IncludeStmt;
216 return FixItHint::CreateInsertion(InsertionLoc: LastIncludeLocation.getEnd(),
217 Code: IncludeStmt);
218 }
219 // Create a block before.
220 const std::string &FirstInclude = IncludeBucket[NonEmptyKind][0];
221 SourceRange FirstIncludeLocation = IncludeLocations[FirstInclude].back();
222 IncludeStmt.append(s: "\n");
223 return FixItHint::CreateInsertion(InsertionLoc: FirstIncludeLocation.getBegin(),
224 Code: IncludeStmt);
225}
226
227} // namespace utils
228
229llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>>
230OptionEnumMapping<utils::IncludeSorter::IncludeStyle>::getEnumMapping() {
231 static constexpr std::pair<utils::IncludeSorter::IncludeStyle, StringRef>
232 Mapping[] = {{utils::IncludeSorter::IS_LLVM, "llvm"},
233 {utils::IncludeSorter::IS_Google, "google"},
234 {utils::IncludeSorter::IS_Google_ObjC, "google-objc"}};
235 return {Mapping};
236}
237} // namespace clang::tidy
238

source code of clang-tools-extra/clang-tidy/utils/IncludeSorter.cpp