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