clang-tools-extra/clang-tidy/llvm/IncludeOrderCheck.cpp

   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(::std::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.starts_with("llvm/") || Filename.starts_with("llvm-c/") ||
  66       Filename.starts_with("clang/") || Filename.starts_with("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("gtest/") || Filename.starts_with("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 = {HashLoc, FilenameRange, std::string(FileName),
  90                          IsAngled, 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(HashLoc)].push_back(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(FileDirectives[I].Loc) !=
 117           SM.getExpansionLineNumber(FileDirectives[I - 1].Loc) + 1)
 118         Blocks.push_back(I);
 119     Blocks.push_back(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(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(IncludeIndices.begin() + Blocks[BI],
 129                  IncludeIndices.begin() + Blocks[BI + 1],
 130                  [&FileDirectives](unsigned LHSI, unsigned RHSI) {
 131                    IncludeDirective &LHS = FileDirectives[LHSI];
 132                    IncludeDirective &RHS = FileDirectives[RHSI];
 133
 134                    int PriorityLHS = getPriority(LHS.Filename, LHS.IsAngled,
 135                                                  LHS.IsMainModule);
 136                    int PriorityRHS = getPriority(RHS.Filename, RHS.IsAngled,
 137                                                  RHS.IsMainModule);
 138
 139                    return std::tie(PriorityLHS, LHS.Filename) <
 140                           std::tie(PriorityRHS, 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(FileDirectives[I].Loc,
 157                           "#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(FromLoc);
 167         unsigned FromLen = std::strcspn(FromData, "\n");
 168
 169         StringRef FixedName(FromData, FromLen);
 170
 171         SourceLocation ToLoc = FileDirectives[I].Range.getBegin();
 172         const char *ToData = SM.getCharacterData(ToLoc);
 173         unsigned ToLen = std::strcspn(ToData, "\n");
 174         auto ToRange =
 175             CharSourceRange::getCharRange(ToLoc, ToLoc.getLocWithOffset(ToLen));
 176
 177         D << FixItHint::CreateReplacement(ToRange, FixedName);
 178       }
 179     }
 180   }
 181
 182   IncludeDirectives.clear();
 183 }
 184
 185 } // namespace clang::tidy::llvm_check