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.consume_back(Suffix))
23 return Str;
24 }
25 return Str;
26}
27
28StringRef 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.
59size_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
64IncludeSorter::IncludeKinds
65determineIncludeKind(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
104int compareHeaders(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
123IncludeSorter::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
129void 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
151std::optional<FixItHint>
152IncludeSorter::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
226llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>>
227OptionEnumMapping<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

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