contrib/llvm-project/clang/lib/Tooling/Inclusions/HeaderIncludes.cpp

   1 //===--- HeaderIncludes.cpp - Insert/Delete #includes --*- C++ -*----------===//
   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 "clang/Tooling/Inclusions/HeaderIncludes.h"
  10 #include "clang/Basic/SourceManager.h"
  11 #include "clang/Lex/Lexer.h"
  12 #include "llvm/ADT/Optional.h"
  13 #include "llvm/Support/FormatVariadic.h"
  14
  15 namespace clang {
  16 namespace tooling {
  17 namespace {
  18
  19 LangOptions createLangOpts() {
  20   LangOptions LangOpts;
  21   LangOpts.CPlusPlus = 1;
  22   LangOpts.CPlusPlus11 = 1;
  23   LangOpts.CPlusPlus14 = 1;
  24   LangOpts.LineComment = 1;
  25   LangOpts.CXXOperatorNames = 1;
  26   LangOpts.Bool = 1;
  27   LangOpts.ObjC = 1;
  28   LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
  29   LangOpts.DeclSpecKeyword = 1; // To get __declspec.
  30   LangOpts.WChar = 1;           // To get wchar_t
  31   return LangOpts;
  32 }
  33
  34 // Returns the offset after skipping a sequence of tokens, matched by \p
  35 // GetOffsetAfterSequence, from the start of the code.
  36 // \p GetOffsetAfterSequence should be a function that matches a sequence of
  37 // tokens and returns an offset after the sequence.
  38 unsigned getOffsetAfterTokenSequence(
  39     StringRef FileName, StringRef Code, const IncludeStyle &Style,
  40     llvm::function_ref<unsigned(const SourceManager &, Lexer &, Token &)>
  41         GetOffsetAfterSequence) {
  42   SourceManagerForFile VirtualSM(FileName, Code);
  43   SourceManager &SM = VirtualSM.get();
  44   Lexer Lex(SM.getMainFileID(), SM.getBuffer(SM.getMainFileID()), SM,
  45             createLangOpts());
  46   Token Tok;
  47   // Get the first token.
  48   Lex.LexFromRawLexer(Tok);
  49   return GetOffsetAfterSequence(SM, Lex, Tok);
  50 }
  51
  52 // Check if a sequence of tokens is like "#<Name> <raw_identifier>". If it is,
  53 // \p Tok will be the token after this directive; otherwise, it can be any token
  54 // after the given \p Tok (including \p Tok). If \p RawIDName is provided, the
  55 // (second) raw_identifier name is checked.
  56 bool checkAndConsumeDirectiveWithName(
  57     Lexer &Lex, StringRef Name, Token &Tok,
  58     llvm::Optional<StringRef> RawIDName = llvm::None) {
  59   bool Matched = Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) &&
  60                  Tok.is(tok::raw_identifier) &&
  61                  Tok.getRawIdentifier() == Name && !Lex.LexFromRawLexer(Tok) &&
  62                  Tok.is(tok::raw_identifier) &&
  63                  (!RawIDName || Tok.getRawIdentifier() == *RawIDName);
  64   if (Matched)
  65     Lex.LexFromRawLexer(Tok);
  66   return Matched;
  67 }
  68
  69 void skipComments(Lexer &Lex, Token &Tok) {
  70   while (Tok.is(tok::comment))
  71     if (Lex.LexFromRawLexer(Tok))
  72       return;
  73 }
  74
  75 // Returns the offset after header guard directives and any comments
  76 // before/after header guards (e.g. #ifndef/#define pair, #pragma once). If no
  77 // header guard is present in the code, this will return the offset after
  78 // skipping all comments from the start of the code.
  79 unsigned getOffsetAfterHeaderGuardsAndComments(StringRef FileName,
  80                                                StringRef Code,
  81                                                const IncludeStyle &Style) {
  82   // \p Consume returns location after header guard or 0 if no header guard is
  83   // found.
  84   auto ConsumeHeaderGuardAndComment =
  85       [&](std::function<unsigned(const SourceManager &SM, Lexer &Lex,
  86                                  Token Tok)>
  87               Consume) {
  88         return getOffsetAfterTokenSequence(
  89             FileName, Code, Style,
  90             [&Consume](const SourceManager &SM, Lexer &Lex, Token Tok) {
  91               skipComments(Lex, Tok);
  92               unsigned InitialOffset = SM.getFileOffset(Tok.getLocation());
  93               return std::max(InitialOffset, Consume(SM, Lex, Tok));
  94             });
  95       };
  96   return std::max(
  97       // #ifndef/#define
  98       ConsumeHeaderGuardAndComment(
  99           [](const SourceManager &SM, Lexer &Lex, Token Tok) -> unsigned {
 100             if (checkAndConsumeDirectiveWithName(Lex, "ifndef", Tok)) {
 101               skipComments(Lex, Tok);
 102               if (checkAndConsumeDirectiveWithName(Lex, "define", Tok))
 103                 return SM.getFileOffset(Tok.getLocation());
 104             }
 105             return 0;
 106           }),
 107       // #pragma once
 108       ConsumeHeaderGuardAndComment(
 109           [](const SourceManager &SM, Lexer &Lex, Token Tok) -> unsigned {
 110             if (checkAndConsumeDirectiveWithName(Lex, "pragma", Tok,
 111                                                  StringRef("once")))
 112               return SM.getFileOffset(Tok.getLocation());
 113             return 0;
 114           }));
 115 }
 116
 117 // Check if a sequence of tokens is like
 118 //    "#include ("header.h" | <header.h>)".
 119 // If it is, \p Tok will be the token after this directive; otherwise, it can be
 120 // any token after the given \p Tok (including \p Tok).
 121 bool checkAndConsumeInclusiveDirective(Lexer &Lex, Token &Tok) {
 122   auto Matched = [&]() {
 123     Lex.LexFromRawLexer(Tok);
 124     return true;
 125   };
 126   if (Tok.is(tok::hash) && !Lex.LexFromRawLexer(Tok) &&
 127       Tok.is(tok::raw_identifier) && Tok.getRawIdentifier() == "include") {
 128     if (Lex.LexFromRawLexer(Tok))
 129       return false;
 130     if (Tok.is(tok::string_literal))
 131       return Matched();
 132     if (Tok.is(tok::less)) {
 133       while (!Lex.LexFromRawLexer(Tok) && Tok.isNot(tok::greater)) {
 134       }
 135       if (Tok.is(tok::greater))
 136         return Matched();
 137     }
 138   }
 139   return false;
 140 }
 141
 142 // Returns the offset of the last #include directive after which a new
 143 // #include can be inserted. This ignores #include's after the #include block(s)
 144 // in the beginning of a file to avoid inserting headers into code sections
 145 // where new #include's should not be added by default.
 146 // These code sections include:
 147 //      - raw string literals (containing #include).
 148 //      - #if blocks.
 149 //      - Special #include's among declarations (e.g. functions).
 150 //
 151 // If no #include after which a new #include can be inserted, this returns the
 152 // offset after skipping all comments from the start of the code.
 153 // Inserting after an #include is not allowed if it comes after code that is not
 154 // #include (e.g. pre-processing directive that is not #include, declarations).
 155 unsigned getMaxHeaderInsertionOffset(StringRef FileName, StringRef Code,
 156                                      const IncludeStyle &Style) {
 157   return getOffsetAfterTokenSequence(
 158       FileName, Code, Style,
 159       [](const SourceManager &SM, Lexer &Lex, Token Tok) {
 160         skipComments(Lex, Tok);
 161         unsigned MaxOffset = SM.getFileOffset(Tok.getLocation());
 162         while (checkAndConsumeInclusiveDirective(Lex, Tok))
 163           MaxOffset = SM.getFileOffset(Tok.getLocation());
 164         return MaxOffset;
 165       });
 166 }
 167
 168 inline StringRef trimInclude(StringRef IncludeName) {
 169   return IncludeName.trim("\"<>");
 170 }
 171
 172 const char IncludeRegexPattern[] =
 173     R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
 174
 175 } // anonymous namespace
 176
 177 IncludeCategoryManager::IncludeCategoryManager(const IncludeStyle &Style,
 178                                                StringRef FileName)
 179     : Style(Style), FileName(FileName) {
 180   FileStem = llvm::sys::path::stem(FileName);
 181   for (const auto &Category : Style.IncludeCategories)
 182     CategoryRegexs.emplace_back(Category.Regex, llvm::Regex::IgnoreCase);
 183   IsMainFile = FileName.endswith(".c") || FileName.endswith(".cc") ||
 184                FileName.endswith(".cpp") || FileName.endswith(".c++") ||
 185                FileName.endswith(".cxx") || FileName.endswith(".m") ||
 186                FileName.endswith(".mm");
 187   if (!Style.IncludeIsMainSourceRegex.empty()) {
 188     llvm::Regex MainFileRegex(Style.IncludeIsMainSourceRegex);
 189     IsMainFile |= MainFileRegex.match(FileName);
 190   }
 191 }
 192
 193 int IncludeCategoryManager::getIncludePriority(StringRef IncludeName,
 194                                                bool CheckMainHeader) const {
 195   int Ret = INT_MAX;
 196   for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
 197     if (CategoryRegexs[i].match(IncludeName)) {
 198       Ret = Style.IncludeCategories[i].Priority;
 199       break;
 200     }
 201   if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
 202     Ret = 0;
 203   return Ret;
 204 }
 205
 206 int IncludeCategoryManager::getSortIncludePriority(StringRef IncludeName,
 207                                                    bool CheckMainHeader) const {
 208   int Ret = INT_MAX;
 209   for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
 210     if (CategoryRegexs[i].match(IncludeName)) {
 211       Ret = Style.IncludeCategories[i].SortPriority;
 212       if (Ret == 0)
 213         Ret = Style.IncludeCategories[i].Priority;
 214       break;
 215     }
 216   if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
 217     Ret = 0;
 218   return Ret;
 219 }
 220 bool IncludeCategoryManager::isMainHeader(StringRef IncludeName) const {
 221   if (!IncludeName.startswith("\""))
 222     return false;
 223   StringRef HeaderStem =
 224       llvm::sys::path::stem(IncludeName.drop_front(1).drop_back(1));
 225   if (FileStem.startswith(HeaderStem) ||
 226       FileStem.startswith_lower(HeaderStem)) {
 227     llvm::Regex MainIncludeRegex(HeaderStem.str() + Style.IncludeIsMainRegex,
 228                                  llvm::Regex::IgnoreCase);
 229     if (MainIncludeRegex.match(FileStem))
 230       return true;
 231   }
 232   return false;
 233 }
 234
 235 HeaderIncludes::HeaderIncludes(StringRef FileName, StringRef Code,
 236                                const IncludeStyle &Style)
 237     : FileName(FileName), Code(Code), FirstIncludeOffset(-1),
 238       MinInsertOffset(
 239           getOffsetAfterHeaderGuardsAndComments(FileName, Code, Style)),
 240       MaxInsertOffset(MinInsertOffset +
 241                       getMaxHeaderInsertionOffset(
 242                           FileName, Code.drop_front(MinInsertOffset), Style)),
 243       Categories(Style, FileName),
 244       IncludeRegex(llvm::Regex(IncludeRegexPattern)) {
 245   // Add 0 for main header and INT_MAX for headers that are not in any
 246   // category.
 247   Priorities = {0, INT_MAX};
 248   for (const auto &Category : Style.IncludeCategories)
 249     Priorities.insert(Category.Priority);
 250   SmallVector<StringRef, 32> Lines;
 251   Code.drop_front(MinInsertOffset).split(Lines, "\n");
 252
 253   unsigned Offset = MinInsertOffset;
 254   unsigned NextLineOffset;
 255   SmallVector<StringRef, 4> Matches;
 256   for (auto Line : Lines) {
 257     NextLineOffset = std::min(Code.size(), Offset + Line.size() + 1);
 258     if (IncludeRegex.match(Line, &Matches)) {
 259       // If this is the last line without trailing newline, we need to make
 260       // sure we don't delete across the file boundary.
 261       addExistingInclude(
 262           Include(Matches[2],
 263                   tooling::Range(
 264                       Offset, std::min(Line.size() + 1, Code.size() - Offset))),
 265           NextLineOffset);
 266     }
 267     Offset = NextLineOffset;
 268   }
 269
 270   // Populate CategoryEndOfssets:
 271   // - Ensure that CategoryEndOffset[Highest] is always populated.
 272   // - If CategoryEndOffset[Priority] isn't set, use the next higher value
 273   // that is set, up to CategoryEndOffset[Highest].
 274   auto Highest = Priorities.begin();
 275   if (CategoryEndOffsets.find(*Highest) == CategoryEndOffsets.end()) {
 276     if (FirstIncludeOffset >= 0)
 277       CategoryEndOffsets[*Highest] = FirstIncludeOffset;
 278     else
 279       CategoryEndOffsets[*Highest] = MinInsertOffset;
 280   }
 281   // By this point, CategoryEndOffset[Highest] is always set appropriately:
 282   //  - to an appropriate location before/after existing #includes, or
 283   //  - to right after the header guard, or
 284   //  - to the beginning of the file.
 285   for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; ++I)
 286     if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end())
 287       CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)];
 288 }
 289
 290 // \p Offset: the start of the line following this include directive.
 291 void HeaderIncludes::addExistingInclude(Include IncludeToAdd,
 292                                         unsigned NextLineOffset) {
 293   auto Iter =
 294       ExistingIncludes.try_emplace(trimInclude(IncludeToAdd.Name)).first;
 295   Iter->second.push_back(std::move(IncludeToAdd));
 296   auto &CurInclude = Iter->second.back();
 297   // The header name with quotes or angle brackets.
 298   // Only record the offset of current #include if we can insert after it.
 299   if (CurInclude.R.getOffset() <= MaxInsertOffset) {
 300     int Priority = Categories.getIncludePriority(
 301         CurInclude.Name, /*CheckMainHeader=*/FirstIncludeOffset < 0);
 302     CategoryEndOffsets[Priority] = NextLineOffset;
 303     IncludesByPriority[Priority].push_back(&CurInclude);
 304     if (FirstIncludeOffset < 0)
 305       FirstIncludeOffset = CurInclude.R.getOffset();
 306   }
 307 }
 308
 309 llvm::Optional<tooling::Replacement>
 310 HeaderIncludes::insert(llvm::StringRef IncludeName, bool IsAngled) const {
 311   assert(IncludeName == trimInclude(IncludeName));
 312   // If a <header> ("header") already exists in code, "header" (<header>) with
 313   // different quotation will still be inserted.
 314   // FIXME: figure out if this is the best behavior.
 315   auto It = ExistingIncludes.find(IncludeName);
 316   if (It != ExistingIncludes.end())
 317     for (const auto &Inc : It->second)
 318       if ((IsAngled && StringRef(Inc.Name).startswith("<")) ||
 319           (!IsAngled && StringRef(Inc.Name).startswith("\"")))
 320         return llvm::None;
 321   std::string Quoted =
 322       llvm::formatv(IsAngled ? "<{0}>" : "\"{0}\"", IncludeName);
 323   StringRef QuotedName = Quoted;
 324   int Priority = Categories.getIncludePriority(
 325       QuotedName, /*CheckMainHeader=*/FirstIncludeOffset < 0);
 326   auto CatOffset = CategoryEndOffsets.find(Priority);
 327   assert(CatOffset != CategoryEndOffsets.end());
 328   unsigned InsertOffset = CatOffset->second; // Fall back offset
 329   auto Iter = IncludesByPriority.find(Priority);
 330   if (Iter != IncludesByPriority.end()) {
 331     for (const auto *Inc : Iter->second) {
 332       if (QuotedName < Inc->Name) {
 333         InsertOffset = Inc->R.getOffset();
 334         break;
 335       }
 336     }
 337   }
 338   assert(InsertOffset <= Code.size());
 339   std::string NewInclude = llvm::formatv("#include {0}\n", QuotedName);
 340   // When inserting headers at end of the code, also append '\n' to the code
 341   // if it does not end with '\n'.
 342   // FIXME: when inserting multiple #includes at the end of code, only one
 343   // newline should be added.
 344   if (InsertOffset == Code.size() && (!Code.empty() && Code.back() != '\n'))
 345     NewInclude = "\n" + NewInclude;
 346   return tooling::Replacement(FileName, InsertOffset, 0, NewInclude);
 347 }
 348
 349 tooling::Replacements HeaderIncludes::remove(llvm::StringRef IncludeName,
 350                                              bool IsAngled) const {
 351   assert(IncludeName == trimInclude(IncludeName));
 352   tooling::Replacements Result;
 353   auto Iter = ExistingIncludes.find(IncludeName);
 354   if (Iter == ExistingIncludes.end())
 355     return Result;
 356   for (const auto &Inc : Iter->second) {
 357     if ((IsAngled && StringRef(Inc.Name).startswith("\"")) ||
 358         (!IsAngled && StringRef(Inc.Name).startswith("<")))
 359       continue;
 360     llvm::Error Err = Result.add(tooling::Replacement(
 361         FileName, Inc.R.getOffset(), Inc.R.getLength(), ""));
 362     if (Err) {
 363       auto ErrMsg = "Unexpected conflicts in #include deletions: " +
 364                     llvm::toString(std::move(Err));
 365       llvm_unreachable(ErrMsg.c_str());
 366     }
 367   }
 368   return Result;
 369 }
 370
 371 } // namespace tooling
 372 } // namespace clang