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 } 188 189 int 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 202 bool 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 217 HeaderIncludes::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. 273 void 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 291 llvm::Optional<tooling::Replacement> 292 HeaderIncludes::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 331 tooling::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