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