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