lib/Tooling/Inclusions/HeaderIncludes.cpp

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