Clang Project

clang_source_code/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
15namespace clang {
16namespace tooling {
17namespace {
18
19LangOptions 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.
38unsigned 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.
56bool 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
69void 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.
79unsigned 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).
121bool 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).
155unsigned 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
168inline StringRef trimInclude(StringRef IncludeName) {
169  return IncludeName.trim("\"<>");
170}
171
172const char IncludeRegexPattern[] =
173    R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
174
175} // anonymous namespace
176
177IncludeCategoryManager::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}
188
189int IncludeCategoryManager::getIncludePriority(StringRef IncludeName,
190                                               bool CheckMainHeader) const {
191  int Ret = INT_MAX;
192  for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i)
193    if (CategoryRegexs[i].match(IncludeName)) {
194      Ret = Style.IncludeCategories[i].Priority;
195      break;
196    }
197  if (CheckMainHeader && IsMainFile && Ret > 0 && isMainHeader(IncludeName))
198    Ret = 0;
199  return Ret;
200}
201
202bool IncludeCategoryManager::isMainHeader(StringRef IncludeName) const {
203  if (!IncludeName.startswith("\""))
204    return false;
205  StringRef HeaderStem =
206      llvm::sys::path::stem(IncludeName.drop_front(1).drop_back(1));
207  if (FileStem.startswith(HeaderStem) ||
208      FileStem.startswith_lower(HeaderStem)) {
209    llvm::Regex MainIncludeRegex(HeaderStem.str() + Style.IncludeIsMainRegex,
210                                 llvm::Regex::IgnoreCase);
211    if (MainIncludeRegex.match(FileStem))
212      return true;
213  }
214  return false;
215}
216
217HeaderIncludes::HeaderIncludes(StringRef FileName, StringRef Code,
218                               const IncludeStyle &Style)
219    : FileName(FileName), Code(Code), FirstIncludeOffset(-1),
220      MinInsertOffset(
221          getOffsetAfterHeaderGuardsAndComments(FileName, Code, Style)),
222      MaxInsertOffset(MinInsertOffset +
223                      getMaxHeaderInsertionOffset(
224                          FileName, Code.drop_front(MinInsertOffset), Style)),
225      Categories(Style, FileName),
226      IncludeRegex(llvm::Regex(IncludeRegexPattern)) {
227  // Add 0 for main header and INT_MAX for headers that are not in any
228  // category.
229  Priorities = {0, INT_MAX};
230  for (const auto &Category : Style.IncludeCategories)
231    Priorities.insert(Category.Priority);
232  SmallVector<StringRef, 32> Lines;
233  Code.drop_front(MinInsertOffset).split(Lines, "\n");
234
235  unsigned Offset = MinInsertOffset;
236  unsigned NextLineOffset;
237  SmallVector<StringRef, 4> Matches;
238  for (auto Line : Lines) {
239    NextLineOffset = std::min(Code.size(), Offset + Line.size() + 1);
240    if (IncludeRegex.match(Line, &Matches)) {
241      // If this is the last line without trailing newline, we need to make
242      // sure we don't delete across the file boundary.
243      addExistingInclude(
244          Include(Matches[2],
245                  tooling::Range(
246                      Offset, std::min(Line.size() + 1, Code.size() - Offset))),
247          NextLineOffset);
248    }
249    Offset = NextLineOffset;
250  }
251
252  // Populate CategoryEndOfssets:
253  // - Ensure that CategoryEndOffset[Highest] is always populated.
254  // - If CategoryEndOffset[Priority] isn't set, use the next higher value
255  // that is set, up to CategoryEndOffset[Highest].
256  auto Highest = Priorities.begin();
257  if (CategoryEndOffsets.find(*Highest) == CategoryEndOffsets.end()) {
258    if (FirstIncludeOffset >= 0)
259      CategoryEndOffsets[*Highest] = FirstIncludeOffset;
260    else
261      CategoryEndOffsets[*Highest] = MinInsertOffset;
262  }
263  // By this point, CategoryEndOffset[Highest] is always set appropriately:
264  //  - to an appropriate location before/after existing #includes, or
265  //  - to right after the header guard, or
266  //  - to the beginning of the file.
267  for (auto I = ++Priorities.begin(), E = Priorities.end(); I != E; ++I)
268    if (CategoryEndOffsets.find(*I) == CategoryEndOffsets.end())
269      CategoryEndOffsets[*I] = CategoryEndOffsets[*std::prev(I)];
270}
271
272// \p Offset: the start of the line following this include directive.
273void HeaderIncludes::addExistingInclude(Include IncludeToAdd,
274                                        unsigned NextLineOffset) {
275  auto Iter =
276      ExistingIncludes.try_emplace(trimInclude(IncludeToAdd.Name)).first;
277  Iter->second.push_back(std::move(IncludeToAdd));
278  auto &CurInclude = Iter->second.back();
279  // The header name with quotes or angle brackets.
280  // Only record the offset of current #include if we can insert after it.
281  if (CurInclude.R.getOffset() <= MaxInsertOffset) {
282    int Priority = Categories.getIncludePriority(
283        CurInclude.Name, /*CheckMainHeader=*/FirstIncludeOffset < 0);
284    CategoryEndOffsets[Priority] = NextLineOffset;
285    IncludesByPriority[Priority].push_back(&CurInclude);
286    if (FirstIncludeOffset < 0)
287      FirstIncludeOffset = CurInclude.R.getOffset();
288  }
289}
290
291llvm::Optional<tooling::Replacement>
292HeaderIncludes::insert(llvm::StringRef IncludeName, bool IsAngled) const {
293  assert(IncludeName == trimInclude(IncludeName));
294  // If a <header> ("header") already exists in code, "header" (<header>) with
295  // different quotation will still be inserted.
296  // FIXME: figure out if this is the best behavior.
297  auto It = ExistingIncludes.find(IncludeName);
298  if (It != ExistingIncludes.end())
299    for (const auto &Inc : It->second)
300      if ((IsAngled && StringRef(Inc.Name).startswith("<")) ||
301          (!IsAngled && StringRef(Inc.Name).startswith("\"")))
302        return llvm::None;
303  std::string Quoted =
304      llvm::formatv(IsAngled ? "<{0}>" : "\"{0}\"", IncludeName);
305  StringRef QuotedName = Quoted;
306  int Priority = Categories.getIncludePriority(
307      QuotedName, /*CheckMainHeader=*/FirstIncludeOffset < 0);
308  auto CatOffset = CategoryEndOffsets.find(Priority);
309  assert(CatOffset != CategoryEndOffsets.end());
310  unsigned InsertOffset = CatOffset->second; // Fall back offset
311  auto Iter = IncludesByPriority.find(Priority);
312  if (Iter != IncludesByPriority.end()) {
313    for (const auto *Inc : Iter->second) {
314      if (QuotedName < Inc->Name) {
315        InsertOffset = Inc->R.getOffset();
316        break;
317      }
318    }
319  }
320  assert(InsertOffset <= Code.size());
321  std::string NewInclude = llvm::formatv("#include {0}\n", QuotedName);
322  // When inserting headers at end of the code, also append '\n' to the code
323  // if it does not end with '\n'.
324  // FIXME: when inserting multiple #includes at the end of code, only one
325  // newline should be added.
326  if (InsertOffset == Code.size() && (!Code.empty() && Code.back() != '\n'))
327    NewInclude = "\n" + NewInclude;
328  return tooling::Replacement(FileName, InsertOffset, 0, NewInclude);
329}
330
331tooling::Replacements HeaderIncludes::remove(llvm::StringRef IncludeName,
332                                             bool IsAngled) const {
333  assert(IncludeName == trimInclude(IncludeName));
334  tooling::Replacements Result;
335  auto Iter = ExistingIncludes.find(IncludeName);
336  if (Iter == ExistingIncludes.end())
337    return Result;
338  for (const auto &Inc : Iter->second) {
339    if ((IsAngled && StringRef(Inc.Name).startswith("\"")) ||
340        (!IsAngled && StringRef(Inc.Name).startswith("<")))
341      continue;
342    llvm::Error Err = Result.add(tooling::Replacement(
343        FileName, Inc.R.getOffset(), Inc.R.getLength(), ""));
344    if (Err) {
345      auto ErrMsg = "Unexpected conflicts in #include deletions: " +
346                    llvm::toString(std::move(Err));
347      llvm_unreachable(ErrMsg.c_str());
348    }
349  }
350  return Result;
351}
352
353
354} // namespace tooling
355} // namespace clang
356
CodeThinker, Enjoy your reading code