1 //===--- IncludeOrderCheck.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 "IncludeOrderCheck.h"
10 #include "clang/Frontend/CompilerInstance.h"
11 #include "clang/Lex/PPCallbacks.h"
12 #include "clang/Lex/Preprocessor.h"
13 #include "llvm/ADT/STLExtras.h"
14
15 #include <map>
16
17 namespace clang {
18 namespace tidy {
19 namespace llvm_check {
20
21 namespace {
22 class IncludeOrderPPCallbacks : public PPCallbacks {
23 public:
IncludeOrderPPCallbacks(ClangTidyCheck & Check,const SourceManager & SM)24 explicit IncludeOrderPPCallbacks(ClangTidyCheck &Check,
25 const SourceManager &SM)
26 : LookForMainModule(true), Check(Check), SM(SM) {}
27
28 void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
29 StringRef FileName, bool IsAngled,
30 CharSourceRange FilenameRange,
31 Optional<FileEntryRef> File, StringRef SearchPath,
32 StringRef RelativePath, const Module *Imported,
33 SrcMgr::CharacteristicKind FileType) override;
34 void EndOfMainFile() override;
35
36 private:
37 struct IncludeDirective {
38 SourceLocation Loc; ///< '#' location in the include directive
39 CharSourceRange Range; ///< SourceRange for the file name
40 std::string Filename; ///< Filename as a string
41 bool IsAngled; ///< true if this was an include with angle brackets
42 bool IsMainModule; ///< true if this was the first include in a file
43 };
44
45 typedef std::vector<IncludeDirective> FileIncludes;
46 std::map<clang::FileID, FileIncludes> IncludeDirectives;
47 bool LookForMainModule;
48
49 ClangTidyCheck &Check;
50 const SourceManager &SM;
51 };
52 } // namespace
53
registerPPCallbacks(const SourceManager & SM,Preprocessor * PP,Preprocessor * ModuleExpanderPP)54 void IncludeOrderCheck::registerPPCallbacks(const SourceManager &SM,
55 Preprocessor *PP,
56 Preprocessor *ModuleExpanderPP) {
57 PP->addPPCallbacks(::std::make_unique<IncludeOrderPPCallbacks>(*this, SM));
58 }
59
getPriority(StringRef Filename,bool IsAngled,bool IsMainModule)60 static int getPriority(StringRef Filename, bool IsAngled, bool IsMainModule) {
61 // We leave the main module header at the top.
62 if (IsMainModule)
63 return 0;
64
65 // LLVM and clang headers are in the penultimate position.
66 if (Filename.startswith("llvm/") || Filename.startswith("llvm-c/") ||
67 Filename.startswith("clang/") || Filename.startswith("clang-c/"))
68 return 2;
69
70 // Put these between system and llvm headers to be consistent with LLVM
71 // clang-format style.
72 if (Filename.startswith("gtest/") || Filename.startswith("gmock/"))
73 return 3;
74
75 // System headers are sorted to the end.
76 if (IsAngled)
77 return 4;
78
79 // Other headers are inserted between the main module header and LLVM headers.
80 return 1;
81 }
82
InclusionDirective(SourceLocation HashLoc,const Token & IncludeTok,StringRef FileName,bool IsAngled,CharSourceRange FilenameRange,Optional<FileEntryRef> File,StringRef SearchPath,StringRef RelativePath,const Module * Imported,SrcMgr::CharacteristicKind FileType)83 void IncludeOrderPPCallbacks::InclusionDirective(
84 SourceLocation HashLoc, const Token &IncludeTok, StringRef FileName,
85 bool IsAngled, CharSourceRange FilenameRange, Optional<FileEntryRef> File,
86 StringRef SearchPath, StringRef RelativePath, const Module *Imported,
87 SrcMgr::CharacteristicKind FileType) {
88 // We recognize the first include as a special main module header and want
89 // to leave it in the top position.
90 IncludeDirective ID = {HashLoc, FilenameRange, std::string(FileName),
91 IsAngled, false};
92 if (LookForMainModule && !IsAngled) {
93 ID.IsMainModule = true;
94 LookForMainModule = false;
95 }
96
97 // Bucket the include directives by the id of the file they were declared in.
98 IncludeDirectives[SM.getFileID(HashLoc)].push_back(std::move(ID));
99 }
100
EndOfMainFile()101 void IncludeOrderPPCallbacks::EndOfMainFile() {
102 LookForMainModule = true;
103 if (IncludeDirectives.empty())
104 return;
105
106 // TODO: find duplicated includes.
107
108 // Form blocks of includes. We don't want to sort across blocks. This also
109 // implicitly makes us never reorder over #defines or #if directives.
110 // FIXME: We should be more careful about sorting below comments as we don't
111 // know if the comment refers to the next include or the whole block that
112 // follows.
113 for (auto &Bucket : IncludeDirectives) {
114 auto &FileDirectives = Bucket.second;
115 std::vector<unsigned> Blocks(1, 0);
116 for (unsigned I = 1, E = FileDirectives.size(); I != E; ++I)
117 if (SM.getExpansionLineNumber(FileDirectives[I].Loc) !=
118 SM.getExpansionLineNumber(FileDirectives[I - 1].Loc) + 1)
119 Blocks.push_back(I);
120 Blocks.push_back(FileDirectives.size()); // Sentinel value.
121
122 // Get a vector of indices.
123 std::vector<unsigned> IncludeIndices;
124 for (unsigned I = 0, E = FileDirectives.size(); I != E; ++I)
125 IncludeIndices.push_back(I);
126
127 // Sort the includes. We first sort by priority, then lexicographically.
128 for (unsigned BI = 0, BE = Blocks.size() - 1; BI != BE; ++BI)
129 llvm::sort(IncludeIndices.begin() + Blocks[BI],
130 IncludeIndices.begin() + Blocks[BI + 1],
131 [&FileDirectives](unsigned LHSI, unsigned RHSI) {
132 IncludeDirective &LHS = FileDirectives[LHSI];
133 IncludeDirective &RHS = FileDirectives[RHSI];
134
135 int PriorityLHS = getPriority(LHS.Filename, LHS.IsAngled,
136 LHS.IsMainModule);
137 int PriorityRHS = getPriority(RHS.Filename, RHS.IsAngled,
138 RHS.IsMainModule);
139
140 return std::tie(PriorityLHS, LHS.Filename) <
141 std::tie(PriorityRHS, RHS.Filename);
142 });
143
144 // Emit a warning for each block and fixits for all changes within that
145 // block.
146 for (unsigned BI = 0, BE = Blocks.size() - 1; BI != BE; ++BI) {
147 // Find the first include that's not in the right position.
148 unsigned I, E;
149 for (I = Blocks[BI], E = Blocks[BI + 1]; I != E; ++I)
150 if (IncludeIndices[I] != I)
151 break;
152
153 if (I == E)
154 continue;
155
156 // Emit a warning.
157 auto D = Check.diag(FileDirectives[I].Loc,
158 "#includes are not sorted properly");
159
160 // Emit fix-its for all following includes in this block.
161 for (; I != E; ++I) {
162 if (IncludeIndices[I] == I)
163 continue;
164 const IncludeDirective &CopyFrom = FileDirectives[IncludeIndices[I]];
165
166 SourceLocation FromLoc = CopyFrom.Range.getBegin();
167 const char *FromData = SM.getCharacterData(FromLoc);
168 unsigned FromLen = std::strcspn(FromData, "\n");
169
170 StringRef FixedName(FromData, FromLen);
171
172 SourceLocation ToLoc = FileDirectives[I].Range.getBegin();
173 const char *ToData = SM.getCharacterData(ToLoc);
174 unsigned ToLen = std::strcspn(ToData, "\n");
175 auto ToRange =
176 CharSourceRange::getCharRange(ToLoc, ToLoc.getLocWithOffset(ToLen));
177
178 D << FixItHint::CreateReplacement(ToRange, FixedName);
179 }
180 }
181 }
182
183 IncludeDirectives.clear();
184 }
185
186 } // namespace llvm_check
187 } // namespace tidy
188 } // namespace clang
189