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