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