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 {
19 
20 namespace {
21 class IncludeOrderPPCallbacks : public PPCallbacks {
22 public:
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 
53 void IncludeOrderCheck::registerPPCallbacks(const SourceManager &SM,
54                                             Preprocessor *PP,
55                                             Preprocessor *ModuleExpanderPP) {
56   PP->addPPCallbacks(::llvm::make_unique<IncludeOrderPPCallbacks>(*this, 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.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 
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, FileName, IsAngled, false};
85   if (LookForMainModule && !IsAngled) {
86     ID.IsMainModule = true;
87     LookForMainModule = false;
88   }
89 
90   // Bucket the include directives by the id of the file they were declared in.
91   IncludeDirectives[SM.getFileID(HashLoc)].push_back(std::move(ID));
92 }
93 
94 void IncludeOrderPPCallbacks::EndOfMainFile() {
95   LookForMainModule = true;
96   if (IncludeDirectives.empty())
97     return;
98 
99   // TODO: find duplicated includes.
100 
101   // Form blocks of includes. We don't want to sort across blocks. This also
102   // implicitly makes us never reorder over #defines or #if directives.
103   // FIXME: We should be more careful about sorting below comments as we don't
104   // know if the comment refers to the next include or the whole block that
105   // follows.
106   for (auto &Bucket : IncludeDirectives) {
107     auto &FileDirectives = Bucket.second;
108     std::vector<unsigned> Blocks(1, 0);
109     for (unsigned I = 1, E = FileDirectives.size(); I != E; ++I)
110       if (SM.getExpansionLineNumber(FileDirectives[I].Loc) !=
111           SM.getExpansionLineNumber(FileDirectives[I - 1].Loc) + 1)
112         Blocks.push_back(I);
113     Blocks.push_back(FileDirectives.size()); // Sentinel value.
114 
115     // Get a vector of indices.
116     std::vector<unsigned> IncludeIndices;
117     for (unsigned I = 0, E = FileDirectives.size(); I != E; ++I)
118       IncludeIndices.push_back(I);
119 
120     // Sort the includes. We first sort by priority, then lexicographically.
121     for (unsigned BI = 0, BE = Blocks.size() - 1; BI != BE; ++BI)
122       std::sort(IncludeIndices.begin() + Blocks[BI],
123                 IncludeIndices.begin() + Blocks[BI + 1],
124                 [&FileDirectives](unsigned LHSI, unsigned RHSI) {
125                   IncludeDirective &LHS = FileDirectives[LHSI];
126                   IncludeDirective &RHS = FileDirectives[RHSI];
127 
128                   int PriorityLHS =
129                       getPriority(LHS.Filename, LHS.IsAngled, LHS.IsMainModule);
130                   int PriorityRHS =
131                       getPriority(RHS.Filename, RHS.IsAngled, RHS.IsMainModule);
132 
133                   return std::tie(PriorityLHS, LHS.Filename) <
134                          std::tie(PriorityRHS, RHS.Filename);
135                 });
136 
137     // Emit a warning for each block and fixits for all changes within that
138     // block.
139     for (unsigned BI = 0, BE = Blocks.size() - 1; BI != BE; ++BI) {
140       // Find the first include that's not in the right position.
141       unsigned I, E;
142       for (I = Blocks[BI], E = Blocks[BI + 1]; I != E; ++I)
143         if (IncludeIndices[I] != I)
144           break;
145 
146       if (I == E)
147         continue;
148 
149       // Emit a warning.
150       auto D = Check.diag(FileDirectives[I].Loc,
151                           "#includes are not sorted properly");
152 
153       // Emit fix-its for all following includes in this block.
154       for (; I != E; ++I) {
155         if (IncludeIndices[I] == I)
156           continue;
157         const IncludeDirective &CopyFrom = FileDirectives[IncludeIndices[I]];
158 
159         SourceLocation FromLoc = CopyFrom.Range.getBegin();
160         const char *FromData = SM.getCharacterData(FromLoc);
161         unsigned FromLen = std::strcspn(FromData, "\n");
162 
163         StringRef FixedName(FromData, FromLen);
164 
165         SourceLocation ToLoc = FileDirectives[I].Range.getBegin();
166         const char *ToData = SM.getCharacterData(ToLoc);
167         unsigned ToLen = std::strcspn(ToData, "\n");
168         auto ToRange =
169             CharSourceRange::getCharRange(ToLoc, ToLoc.getLocWithOffset(ToLen));
170 
171         D << FixItHint::CreateReplacement(ToRange, FixedName);
172       }
173     }
174   }
175 
176   IncludeDirectives.clear();
177 }
178 
179 } // namespace llvm
180 } // namespace tidy
181 } // namespace clang
182