clang-tools-extra/clang-tidy/utils/IncludeSorter.cpp

   1 //===---------- IncludeSorter.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 "IncludeSorter.h"
  10 #include "clang/Basic/SourceManager.h"
  11 #include "clang/Lex/Lexer.h"
  12 #include <algorithm>
  13 #include <optional>
  14
  15 namespace clang::tidy {
  16 namespace utils {
  17
  18 namespace {
  19
  20 StringRef removeFirstSuffix(StringRef Str, ArrayRef<const char *> Suffixes) {
  21   for (StringRef Suffix : Suffixes) {
  22     if (Str.endswith(Suffix)) {
  23       return Str.substr(0, Str.size() - Suffix.size());
  24     }
  25   }
  26   return Str;
  27 }
  28
  29 StringRef makeCanonicalName(StringRef Str, IncludeSorter::IncludeStyle Style) {
  30   // The list of suffixes to remove from source file names to get the
  31   // "canonical" file names.
  32   // E.g. tools/sort_includes.cc and tools/sort_includes_test.cc
  33   // would both canonicalize to tools/sort_includes and tools/sort_includes.h
  34   // (once canonicalized) will match as being the main include file associated
  35   // with the source files.
  36   if (Style == IncludeSorter::IS_LLVM) {
  37     return removeFirstSuffix(
  38         removeFirstSuffix(Str, {".cc", ".cpp", ".c", ".h", ".hpp"}), {"Test"});
  39   }
  40   if (Style == IncludeSorter::IS_Google_ObjC) {
  41     StringRef Canonical =
  42         removeFirstSuffix(removeFirstSuffix(Str, {".cc", ".cpp", ".c", ".h",
  43                                                   ".hpp", ".mm", ".m"}),
  44                           {"_unittest", "_regtest", "_test", "Test"});
  45
  46     // Objective-C categories have a `+suffix` format, but should be grouped
  47     // with the file they are a category of.
  48     size_t StartIndex = Canonical.find_last_of('/');
  49     if (StartIndex == StringRef::npos) {
  50       StartIndex = 0;
  51     }
  52     return Canonical.substr(
  53         0, Canonical.find_first_of('+', StartIndex));
  54   }
  55   return removeFirstSuffix(
  56       removeFirstSuffix(Str, {".cc", ".cpp", ".c", ".h", ".hpp"}),
  57       {"_unittest", "_regtest", "_test"});
  58 }
  59
  60 // Scan to the end of the line and return the offset of the next line.
  61 size_t findNextLine(const char *Text) {
  62   size_t EOLIndex = std::strcspn(Text, "\n");
  63   return Text[EOLIndex] == '\0' ? EOLIndex : EOLIndex + 1;
  64 }
  65
  66 IncludeSorter::IncludeKinds
  67 determineIncludeKind(StringRef CanonicalFile, StringRef IncludeFile,
  68                      bool IsAngled, IncludeSorter::IncludeStyle Style) {
  69   // Compute the two "canonical" forms of the include's filename sans extension.
  70   // The first form is the include's filename without ".h" or "-inl.h" at the
  71   // end. The second form is the first form with "/public/" in the file path
  72   // replaced by "/internal/".
  73   if (IsAngled) {
  74     // If the system include (<foo>) ends with ".h", then it is a normal C-style
  75     // include. Otherwise assume it is a C++-style extensionless include.
  76     return IncludeFile.endswith(".h") ? IncludeSorter::IK_CSystemInclude
  77                                       : IncludeSorter::IK_CXXSystemInclude;
  78   }
  79   StringRef CanonicalInclude = makeCanonicalName(IncludeFile, Style);
  80   if (CanonicalFile.endswith(CanonicalInclude)
  81       || CanonicalInclude.endswith(CanonicalFile)) {
  82     return IncludeSorter::IK_MainTUInclude;
  83   }
  84   if ((Style == IncludeSorter::IS_Google) ||
  85       (Style == IncludeSorter::IS_Google_ObjC)) {
  86     std::pair<StringRef, StringRef> Parts = CanonicalInclude.split("/public/");
  87     StringRef FileCopy = CanonicalFile;
  88     if (FileCopy.consume_front(Parts.first) &&
  89         FileCopy.consume_back(Parts.second)) {
  90       // Determine the kind of this inclusion.
  91       if (FileCopy.equals("/internal/") ||
  92           FileCopy.equals("/proto/")) {
  93         return IncludeSorter::IK_MainTUInclude;
  94       }
  95     }
  96   }
  97   if (Style == IncludeSorter::IS_Google_ObjC) {
  98     if (IncludeFile.endswith(".generated.h") ||
  99         IncludeFile.endswith(".proto.h") || IncludeFile.endswith(".pbobjc.h")) {
 100       return IncludeSorter::IK_GeneratedInclude;
 101     }
 102   }
 103   return IncludeSorter::IK_NonSystemInclude;
 104 }
 105
 106 int compareHeaders(StringRef LHS, StringRef RHS,
 107                    IncludeSorter::IncludeStyle Style) {
 108   if (Style == IncludeSorter::IncludeStyle::IS_Google_ObjC) {
 109     const std::pair<const char *, const char *> &Mismatch =
 110         std::mismatch(LHS.begin(), LHS.end(), RHS.begin());
 111     if ((Mismatch.first != LHS.end()) && (Mismatch.second != RHS.end())) {
 112       if ((*Mismatch.first == '.') && (*Mismatch.second == '+')) {
 113         return -1;
 114       }
 115       if ((*Mismatch.first == '+') && (*Mismatch.second == '.')) {
 116         return 1;
 117       }
 118     }
 119   }
 120   return LHS.compare(RHS);
 121 }
 122
 123 } // namespace
 124
 125 IncludeSorter::IncludeSorter(const SourceManager *SourceMgr,
 126                              const FileID FileID, StringRef FileName,
 127                              IncludeStyle Style)
 128     : SourceMgr(SourceMgr), Style(Style), CurrentFileID(FileID),
 129       CanonicalFile(makeCanonicalName(FileName, Style)) {}
 130
 131 void IncludeSorter::addInclude(StringRef FileName, bool IsAngled,
 132                                SourceLocation HashLocation,
 133                                SourceLocation EndLocation) {
 134   int Offset = findNextLine(SourceMgr->getCharacterData(EndLocation));
 135
 136   // Record the relevant location information for this inclusion directive.
 137   IncludeLocations[FileName].push_back(
 138       SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset)));
 139   SourceLocations.push_back(IncludeLocations[FileName].back());
 140
 141   // Stop if this inclusion is a duplicate.
 142   if (IncludeLocations[FileName].size() > 1)
 143     return;
 144
 145   // Add the included file's name to the appropriate bucket.
 146   IncludeKinds Kind =
 147       determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
 148   if (Kind != IK_InvalidInclude)
 149     IncludeBucket[Kind].push_back(FileName.str());
 150 }
 151
 152 std::optional<FixItHint>
 153 IncludeSorter::createIncludeInsertion(StringRef FileName, bool IsAngled) {
 154   std::string IncludeStmt;
 155   if (Style == IncludeStyle::IS_Google_ObjC) {
 156     IncludeStmt = IsAngled
 157                       ? llvm::Twine("#import <" + FileName + ">\n").str()
 158                       : llvm::Twine("#import \"" + FileName + "\"\n").str();
 159   } else {
 160     IncludeStmt = IsAngled
 161                       ? llvm::Twine("#include <" + FileName + ">\n").str()
 162                       : llvm::Twine("#include \"" + FileName + "\"\n").str();
 163   }
 164   if (SourceLocations.empty()) {
 165     // If there are no includes in this file, add it in the first line.
 166     // FIXME: insert after the file comment or the header guard, if present.
 167     IncludeStmt.append("\n");
 168     return FixItHint::CreateInsertion(
 169         SourceMgr->getLocForStartOfFile(CurrentFileID), IncludeStmt);
 170   }
 171
 172   auto IncludeKind =
 173       determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
 174
 175   if (!IncludeBucket[IncludeKind].empty()) {
 176     for (const std::string &IncludeEntry : IncludeBucket[IncludeKind]) {
 177       if (compareHeaders(FileName, IncludeEntry, Style) < 0) {
 178         const auto &Location = IncludeLocations[IncludeEntry][0];
 179         return FixItHint::CreateInsertion(Location.getBegin(), IncludeStmt);
 180       }
 181       if (FileName == IncludeEntry) {
 182         return std::nullopt;
 183       }
 184     }
 185     // FileName comes after all include entries in bucket, insert it after
 186     // last.
 187     const std::string &LastInclude = IncludeBucket[IncludeKind].back();
 188     SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
 189     return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
 190                                       IncludeStmt);
 191   }
 192   // Find the non-empty include bucket to be sorted directly above
 193   // 'IncludeKind'. If such a bucket exists, we'll want to sort the include
 194   // after that bucket. If no such bucket exists, find the first non-empty
 195   // include bucket in the file. In that case, we'll want to sort the include
 196   // before that bucket.
 197   IncludeKinds NonEmptyKind = IK_InvalidInclude;
 198   for (int I = IK_InvalidInclude - 1; I >= 0; --I) {
 199     if (!IncludeBucket[I].empty()) {
 200       NonEmptyKind = static_cast<IncludeKinds>(I);
 201       if (NonEmptyKind < IncludeKind)
 202         break;
 203     }
 204   }
 205   if (NonEmptyKind == IK_InvalidInclude) {
 206     return std::nullopt;
 207   }
 208
 209   if (NonEmptyKind < IncludeKind) {
 210     // Create a block after.
 211     const std::string &LastInclude = IncludeBucket[NonEmptyKind].back();
 212     SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
 213     IncludeStmt = '\n' + IncludeStmt;
 214     return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
 215                                       IncludeStmt);
 216   }
 217   // Create a block before.
 218   const std::string &FirstInclude = IncludeBucket[NonEmptyKind][0];
 219   SourceRange FirstIncludeLocation = IncludeLocations[FirstInclude].back();
 220   IncludeStmt.append("\n");
 221   return FixItHint::CreateInsertion(FirstIncludeLocation.getBegin(),
 222                                     IncludeStmt);
 223 }
 224
 225 } // namespace utils
 226
 227 llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>>
 228 OptionEnumMapping<utils::IncludeSorter::IncludeStyle>::getEnumMapping() {
 229   static constexpr std::pair<utils::IncludeSorter::IncludeStyle, StringRef>
 230       Mapping[] = {{utils::IncludeSorter::IS_LLVM, "llvm"},
 231                    {utils::IncludeSorter::IS_Google, "google"},
 232                    {utils::IncludeSorter::IS_Google_ObjC, "google-objc"}};
 233   return ArrayRef(Mapping);
 234 }
 235 } // namespace clang::tidy