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