clang-tools  14.0.0git
IncludeSorter.cpp
Go to the documentation of this file.
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 
14 namespace clang {
15 namespace 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.endswith(Suffix)) {
23  return Str.substr(0, Str.size() - Suffix.size());
24  }
25  }
26  return Str;
27 }
28 
29 StringRef 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  removeFirstSuffix(Str, {".cc", ".cpp", ".c", ".h", ".hpp"}), {"Test"});
39  }
40  if (Style == IncludeSorter::IS_Google_ObjC) {
41  StringRef Canonical =
42  removeFirstSuffix(removeFirstSuffix(Str, {".cc", ".cpp", ".c", ".h",
43  ".hpp", ".mm", ".m"}),
44  {"_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('/');
49  if (StartIndex == StringRef::npos) {
50  StartIndex = 0;
51  }
52  return Canonical.substr(
53  0, Canonical.find_first_of('+', StartIndex));
54  }
55  return removeFirstSuffix(
56  removeFirstSuffix(Str, {".cc", ".cpp", ".c", ".h", ".hpp"}),
57  {"_unittest", "_regtest", "_test"});
58 }
59 
60 // Scan to the end of the line and return the offset of the next line.
61 size_t findNextLine(const char *Text) {
62  size_t EOLIndex = std::strcspn(Text, "\n");
63  return Text[EOLIndex] == '\0' ? EOLIndex : EOLIndex + 1;
64 }
65 
67 determineIncludeKind(StringRef CanonicalFile, StringRef IncludeFile,
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.endswith(".h") ? IncludeSorter::IK_CSystemInclude
78  }
79  StringRef CanonicalInclude = makeCanonicalName(IncludeFile, Style);
80  if (CanonicalFile.endswith(CanonicalInclude)
81  || CanonicalInclude.endswith(CanonicalFile)) {
83  }
84  if ((Style == IncludeSorter::IS_Google) ||
85  (Style == IncludeSorter::IS_Google_ObjC)) {
86  std::pair<StringRef, StringRef> Parts = CanonicalInclude.split("/public/");
87  std::string AltCanonicalInclude =
88  Parts.first.str() + "/internal/" + Parts.second.str();
89  std::string ProtoCanonicalInclude =
90  Parts.first.str() + "/proto/" + Parts.second.str();
91 
92  // Determine the kind of this inclusion.
93  if (CanonicalFile.equals(AltCanonicalInclude) ||
94  CanonicalFile.equals(ProtoCanonicalInclude)) {
96  }
97  }
98  if (Style == IncludeSorter::IS_Google_ObjC) {
99  if (IncludeFile.endswith(".generated.h") ||
100  IncludeFile.endswith(".proto.h") || IncludeFile.endswith(".pbobjc.h")) {
102  }
103  }
105 }
106 
107 int compareHeaders(StringRef LHS, StringRef RHS,
109  if (Style == IncludeSorter::IncludeStyle::IS_Google_ObjC) {
110  const std::pair<const char *, const char *> &Mismatch =
111  std::mismatch(LHS.begin(), LHS.end(), RHS.begin());
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 
127  const FileID FileID, StringRef FileName,
128  IncludeStyle Style)
129  : SourceMgr(SourceMgr), Style(Style), CurrentFileID(FileID),
130  CanonicalFile(makeCanonicalName(FileName, Style)) {}
131 
133  SourceLocation HashLocation,
134  SourceLocation EndLocation) {
135  int Offset = findNextLine(SourceMgr->getCharacterData(EndLocation));
136 
137  // Record the relevant location information for this inclusion directive.
138  IncludeLocations[FileName].push_back(
139  SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset)));
140  SourceLocations.push_back(IncludeLocations[FileName].back());
141 
142  // Stop if this inclusion is a duplicate.
143  if (IncludeLocations[FileName].size() > 1)
144  return;
145 
146  // Add the included file's name to the appropriate bucket.
148  determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
149  if (Kind != IK_InvalidInclude)
150  IncludeBucket[Kind].push_back(FileName.str());
151 }
152 
153 Optional<FixItHint> IncludeSorter::CreateIncludeInsertion(StringRef FileName,
154  bool IsAngled) {
155  std::string IncludeStmt;
156  if (Style == IncludeStyle::IS_Google_ObjC) {
157  IncludeStmt = IsAngled
158  ? llvm::Twine("#import <" + FileName + ">\n").str()
159  : llvm::Twine("#import \"" + FileName + "\"\n").str();
160  } else {
161  IncludeStmt = IsAngled
162  ? llvm::Twine("#include <" + FileName + ">\n").str()
163  : llvm::Twine("#include \"" + FileName + "\"\n").str();
164  }
165  if (SourceLocations.empty()) {
166  // If there are no includes in this file, add it in the first line.
167  // FIXME: insert after the file comment or the header guard, if present.
168  IncludeStmt.append("\n");
169  return FixItHint::CreateInsertion(
170  SourceMgr->getLocForStartOfFile(CurrentFileID), IncludeStmt);
171  }
172 
173  auto IncludeKind =
174  determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
175 
176  if (!IncludeBucket[IncludeKind].empty()) {
177  for (const std::string &IncludeEntry : IncludeBucket[IncludeKind]) {
178  if (compareHeaders(FileName, IncludeEntry, Style) < 0) {
179  const auto &Location = IncludeLocations[IncludeEntry][0];
180  return FixItHint::CreateInsertion(Location.getBegin(), IncludeStmt);
181  }
182  if (FileName == IncludeEntry) {
183  return llvm::None;
184  }
185  }
186  // FileName comes after all include entries in bucket, insert it after
187  // last.
188  const std::string &LastInclude = IncludeBucket[IncludeKind].back();
189  SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
190  return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
191  IncludeStmt);
192  }
193  // Find the non-empty include bucket to be sorted directly above
194  // 'IncludeKind'. If such a bucket exists, we'll want to sort the include
195  // after that bucket. If no such bucket exists, find the first non-empty
196  // include bucket in the file. In that case, we'll want to sort the include
197  // before that bucket.
198  IncludeKinds NonEmptyKind = IK_InvalidInclude;
199  for (int I = IK_InvalidInclude - 1; I >= 0; --I) {
200  if (!IncludeBucket[I].empty()) {
201  NonEmptyKind = static_cast<IncludeKinds>(I);
202  if (NonEmptyKind < IncludeKind)
203  break;
204  }
205  }
206  if (NonEmptyKind == IK_InvalidInclude) {
207  return llvm::None;
208  }
209 
210  if (NonEmptyKind < IncludeKind) {
211  // Create a block after.
212  const std::string &LastInclude = IncludeBucket[NonEmptyKind].back();
213  SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
214  IncludeStmt = '\n' + IncludeStmt;
215  return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
216  IncludeStmt);
217  }
218  // Create a block before.
219  const std::string &FirstInclude = IncludeBucket[NonEmptyKind][0];
220  SourceRange FirstIncludeLocation = IncludeLocations[FirstInclude].back();
221  IncludeStmt.append("\n");
222  return FixItHint::CreateInsertion(FirstIncludeLocation.getBegin(),
223  IncludeStmt);
224 }
225 
226 } // namespace utils
227 
228 llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>>
230  static constexpr std::pair<utils::IncludeSorter::IncludeStyle, StringRef>
231  Mapping[] = {{utils::IncludeSorter::IS_LLVM, "llvm"},
233  {utils::IncludeSorter::IS_Google_ObjC, "google-objc"}};
234  return makeArrayRef(Mapping);
235 }
236 } // namespace tidy
237 } // namespace clang
clang::tidy::utils::IncludeSorter::IK_CXXSystemInclude
@ IK_CXXSystemInclude
e.g. #include <vector>
Definition: IncludeSorter.h:32
Suffix
std::string Suffix
Definition: AddUsing.cpp:112
Location
Definition: Modularize.cpp:382
clang::tidy::utils::IncludeSorter::IncludeStyle
IncludeStyle
Supported include styles.
Definition: IncludeSorter.h:26
clang::tidy::utils::IncludeSorter::IS_Google
@ IS_Google
Definition: IncludeSorter.h:26
clang::tidy::utils::IncludeSorter::IK_GeneratedInclude
@ IK_GeneratedInclude
e.g. #include "bar.proto.h"
Definition: IncludeSorter.h:34
Kind
BindArgumentKind Kind
Definition: AvoidBindCheck.cpp:59
clang::tidy::utils::IncludeSorter::IK_InvalidInclude
@ IK_InvalidInclude
total number of valid IncludeKinds
Definition: IncludeSorter.h:35
Text
std::string Text
Definition: HTMLGenerator.cpp:80
SourceMgr
llvm::SourceMgr * SourceMgr
Definition: ConfigCompile.cpp:102
Offset
size_t Offset
Definition: CodeComplete.cpp:1103
clang::tidy::utils::IncludeSorter::IK_MainTUInclude
@ IK_MainTUInclude
e.g. #include "foo.h" when editing foo.cc
Definition: IncludeSorter.h:30
Suffixes
static constexpr llvm::StringLiteral Suffixes
Definition: UppercaseLiteralSuffixCheck.cpp:32
clang::tidy::utils::IncludeSorter::AddInclude
void AddInclude(StringRef FileName, bool IsAngled, SourceLocation HashLocation, SourceLocation EndLocation)
Adds the given include directive to the sorter.
Definition: IncludeSorter.cpp:132
FileName
StringRef FileName
Definition: KernelNameRestrictionCheck.cpp:46
IsAngled
bool IsAngled
true if this was an include with angle brackets
Definition: IncludeOrderCheck.cpp:40
clang::tidy::OptionEnumMapping::getEnumMapping
static ArrayRef< std::pair< T, StringRef > > getEnumMapping()=delete
clang::tidy::utils::IncludeSorter::IncludeKinds
IncludeKinds
The classifications of inclusions, in the order they should be sorted.
Definition: IncludeSorter.h:29
IncludeSorter.h
clang::tidy::utils::IncludeSorter::IS_Google_ObjC
@ IS_Google_ObjC
Definition: IncludeSorter.h:26
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::tidy::bugprone::model::MixFlags::Canonical
@ Canonical
The two mix because the types refer to the same CanonicalType, but we do not elaborate as to how.
clang::tidy::utils::IncludeSorter::CreateIncludeInsertion
Optional< FixItHint > CreateIncludeInsertion(StringRef FileName, bool IsAngled)
Creates a quoted inclusion directive in the right sort order.
Definition: IncludeSorter.cpp:153
clang::tidy::utils::IncludeSorter::IS_LLVM
@ IS_LLVM
Definition: IncludeSorter.h:26
clang::tidy::utils::IncludeSorter::IncludeSorter
IncludeSorter(const SourceManager *SourceMgr, const FileID FileID, StringRef FileName, IncludeStyle Style)
IncludeSorter constructor; takes the FileID and name of the file to be processed by the sorter.
Definition: IncludeSorter.cpp:126
clang::tidy::utils::IncludeSorter::IK_CSystemInclude
@ IK_CSystemInclude
e.g. #include <stdio.h>
Definition: IncludeSorter.h:31
clang::tidy::utils::IncludeSorter::IK_NonSystemInclude
@ IK_NonSystemInclude
e.g. #include "bar.h"
Definition: IncludeSorter.h:33