543 lines · cpp
1//===--- IncludeCleaner.cpp - Unused/Missing Headers Analysis ---*- 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "IncludeCleaner.h"10#include "Diagnostics.h"11#include "Headers.h"12#include "ParsedAST.h"13#include "Preamble.h"14#include "Protocol.h"15#include "SourceCode.h"16#include "clang-include-cleaner/Analysis.h"17#include "clang-include-cleaner/IncludeSpeller.h"18#include "clang-include-cleaner/Record.h"19#include "clang-include-cleaner/Types.h"20#include "support/Logger.h"21#include "support/Path.h"22#include "support/Trace.h"23#include "clang/AST/ASTContext.h"24#include "clang/Basic/Diagnostic.h"25#include "clang/Basic/LLVM.h"26#include "clang/Basic/SourceLocation.h"27#include "clang/Basic/SourceManager.h"28#include "clang/Format/Format.h"29#include "clang/Lex/DirectoryLookup.h"30#include "clang/Lex/HeaderSearch.h"31#include "clang/Lex/Preprocessor.h"32#include "clang/Tooling/Core/Replacement.h"33#include "clang/Tooling/Inclusions/HeaderIncludes.h"34#include "clang/Tooling/Inclusions/StandardLibrary.h"35#include "clang/Tooling/Syntax/Tokens.h"36#include "llvm/ADT/ArrayRef.h"37#include "llvm/ADT/DenseSet.h"38#include "llvm/ADT/GenericUniformityImpl.h"39#include "llvm/ADT/STLExtras.h"40#include "llvm/ADT/SmallString.h"41#include "llvm/ADT/SmallVector.h"42#include "llvm/ADT/StringRef.h"43#include "llvm/Support/Error.h"44#include "llvm/Support/ErrorHandling.h"45#include "llvm/Support/FormatVariadic.h"46#include "llvm/Support/Path.h"47#include "llvm/Support/Regex.h"48#include <cassert>49#include <iterator>50#include <map>51#include <optional>52#include <string>53#include <utility>54#include <vector>55 56namespace clang::clangd {57namespace {58 59bool isIgnored(llvm::StringRef HeaderPath, HeaderFilter IgnoreHeaders) {60 // Convert the path to Unix slashes and try to match against the filter.61 llvm::SmallString<64> NormalizedPath(HeaderPath);62 llvm::sys::path::native(NormalizedPath, llvm::sys::path::Style::posix);63 for (auto &Filter : IgnoreHeaders) {64 if (Filter(NormalizedPath))65 return true;66 }67 return false;68}69 70bool mayConsiderUnused(const Inclusion &Inc, ParsedAST &AST,71 const include_cleaner::PragmaIncludes *PI,72 bool AnalyzeAngledIncludes) {73 assert(Inc.HeaderID);74 auto HID = static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID);75 auto FE = AST.getSourceManager().getFileManager().getFileRef(76 AST.getIncludeStructure().getRealPath(HID));77 assert(FE);78 if (FE->getDir() == AST.getPreprocessor()79 .getHeaderSearchInfo()80 .getModuleMap()81 .getBuiltinDir())82 return false;83 if (PI && PI->shouldKeep(*FE))84 return false;85 // FIXME(kirillbobyrev): We currently do not support the umbrella headers.86 // System headers are likely to be standard library headers.87 // Until we have good support for umbrella headers, don't warn about them88 // (unless analysis is explicitly enabled).89 if (Inc.Written.front() == '<') {90 if (tooling::stdlib::Header::named(Inc.Written))91 return true;92 if (!AnalyzeAngledIncludes)93 return false;94 }95 if (PI) {96 // Check if main file is the public interface for a private header. If so we97 // shouldn't diagnose it as unused.98 if (auto PHeader = PI->getPublic(*FE); !PHeader.empty()) {99 PHeader = PHeader.trim("<>\"");100 // Since most private -> public mappings happen in a verbatim way, we101 // check textually here. This might go wrong in presence of symlinks or102 // header mappings. But that's not different than rest of the places.103 if (AST.tuPath().ends_with(PHeader))104 return false;105 }106 }107 // Headers without include guards have side effects and are not108 // self-contained, skip them.109 if (!AST.getPreprocessor().getHeaderSearchInfo().isFileMultipleIncludeGuarded(110 *FE)) {111 dlog("{0} doesn't have header guard and will not be considered unused",112 FE->getName());113 return false;114 }115 return true;116}117 118std::vector<Diag> generateMissingIncludeDiagnostics(119 ParsedAST &AST, llvm::ArrayRef<MissingIncludeDiagInfo> MissingIncludes,120 llvm::StringRef Code, HeaderFilter IgnoreHeaders,121 HeaderFilter AngledHeaders, HeaderFilter QuotedHeaders,122 const ThreadsafeFS &TFS) {123 std::vector<Diag> Result;124 const SourceManager &SM = AST.getSourceManager();125 const FileEntry *MainFile = SM.getFileEntryForID(SM.getMainFileID());126 127 auto FileStyle = getFormatStyleForFile(AST.tuPath(), Code, TFS, false);128 129 tooling::HeaderIncludes HeaderIncludes(AST.tuPath(), Code,130 FileStyle.IncludeStyle);131 for (const auto &SymbolWithMissingInclude : MissingIncludes) {132 llvm::StringRef ResolvedPath =133 SymbolWithMissingInclude.Providers.front().resolvedPath();134 if (isIgnored(ResolvedPath, IgnoreHeaders)) {135 dlog("IncludeCleaner: not diagnosing missing include {0}, filtered by "136 "config",137 ResolvedPath);138 continue;139 }140 141 std::string Spelling = include_cleaner::spellHeader(142 {SymbolWithMissingInclude.Providers.front(),143 AST.getPreprocessor().getHeaderSearchInfo(), MainFile});144 145 llvm::StringRef HeaderRef{Spelling};146 147 bool Angled = HeaderRef.starts_with("<");148 if (SymbolWithMissingInclude.Providers.front().kind() ==149 include_cleaner::Header::Kind::Physical) {150 for (auto &Filter : Angled ? QuotedHeaders : AngledHeaders) {151 if (Filter(ResolvedPath)) {152 Angled = !Angled;153 break;154 }155 }156 }157 158 // We might suggest insertion of an existing include in edge cases, e.g.,159 // include is present in a PP-disabled region, or spelling of the header160 // turns out to be the same as one of the unresolved includes in the161 // main file.162 std::optional<tooling::Replacement> Replacement = HeaderIncludes.insert(163 HeaderRef.trim("\"<>"), Angled, tooling::IncludeDirective::Include);164 if (!Replacement.has_value())165 continue;166 167 if (Angled != (Spelling.front() == '<')) {168 Spelling.front() = Angled ? '<' : '"';169 Spelling.back() = Angled ? '>' : '"';170 }171 172 Diag &D = Result.emplace_back();173 D.Message =174 llvm::formatv("No header providing \"{0}\" is directly included",175 SymbolWithMissingInclude.Symbol.name());176 D.Name = "missing-includes";177 D.Source = Diag::DiagSource::Clangd;178 D.File = AST.tuPath();179 D.InsideMainFile = true;180 // We avoid the "warning" severity here in favor of LSP's "information".181 //182 // Users treat most warnings on code being edited as high-priority.183 // They don't think of include cleanups the same way: they want to edit184 // lines with existing violations without fixing them.185 // Diagnostics at the same level tend to be visually indistinguishable,186 // and a few missing includes can cause many diagnostics.187 // Marking these as "information" leaves them visible, but less intrusive.188 //189 // (These concerns don't apply to unused #include warnings: these are fewer,190 // they appear on infrequently-edited lines with few other warnings, and191 // the 'Unneccesary' tag often result in a different rendering)192 //193 // Usually clang's "note" severity usually has special semantics, being194 // translated into LSP RelatedInformation of a parent diagnostic.195 // But not here: these aren't processed by clangd's DiagnosticConsumer.196 D.Severity = DiagnosticsEngine::Note;197 D.Range = clangd::Range{198 offsetToPosition(Code,199 SymbolWithMissingInclude.SymRefRange.beginOffset()),200 offsetToPosition(Code,201 SymbolWithMissingInclude.SymRefRange.endOffset())};202 auto &F = D.Fixes.emplace_back();203 F.Message = "#include " + Spelling;204 TextEdit Edit = replacementToEdit(Code, *Replacement);205 F.Edits.emplace_back(std::move(Edit));206 }207 return Result;208}209 210std::vector<Diag> generateUnusedIncludeDiagnostics(211 PathRef FileName, llvm::ArrayRef<const Inclusion *> UnusedIncludes,212 llvm::StringRef Code, HeaderFilter IgnoreHeaders) {213 std::vector<Diag> Result;214 for (const auto *Inc : UnusedIncludes) {215 if (isIgnored(Inc->Resolved, IgnoreHeaders))216 continue;217 Diag &D = Result.emplace_back();218 D.Message =219 llvm::formatv("included header {0} is not used directly",220 llvm::sys::path::filename(221 Inc->Written.substr(1, Inc->Written.size() - 2),222 llvm::sys::path::Style::posix));223 D.Name = "unused-includes";224 D.Source = Diag::DiagSource::Clangd;225 D.File = FileName;226 D.InsideMainFile = true;227 D.Severity = DiagnosticsEngine::Warning;228 D.Tags.push_back(Unnecessary);229 D.Range = rangeTillEOL(Code, Inc->HashOffset);230 // FIXME(kirillbobyrev): Removing inclusion might break the code if the231 // used headers are only reachable transitively through this one. Suggest232 // including them directly instead.233 // FIXME(kirillbobyrev): Add fix suggestion for adding IWYU pragmas234 // (keep/export) remove the warning once we support IWYU pragmas.235 auto &F = D.Fixes.emplace_back();236 F.Message = "remove #include directive";237 F.Edits.emplace_back();238 F.Edits.back().range.start.line = Inc->HashLine;239 F.Edits.back().range.end.line = Inc->HashLine + 1;240 }241 return Result;242}243 244std::optional<Fix>245removeAllUnusedIncludes(llvm::ArrayRef<Diag> UnusedIncludes) {246 if (UnusedIncludes.empty())247 return std::nullopt;248 249 Fix RemoveAll;250 RemoveAll.Message = "remove all unused includes";251 for (const auto &Diag : UnusedIncludes) {252 assert(Diag.Fixes.size() == 1 && "Expected exactly one fix.");253 RemoveAll.Edits.insert(RemoveAll.Edits.end(),254 Diag.Fixes.front().Edits.begin(),255 Diag.Fixes.front().Edits.end());256 }257 return RemoveAll;258}259 260std::optional<Fix>261addAllMissingIncludes(llvm::ArrayRef<Diag> MissingIncludeDiags) {262 if (MissingIncludeDiags.empty())263 return std::nullopt;264 265 Fix AddAllMissing;266 AddAllMissing.Message = "add all missing includes";267 // A map to deduplicate the edits with the same new text.268 // newText (#include "my_missing_header.h") -> TextEdit.269 std::map<std::string, TextEdit> Edits;270 for (const auto &Diag : MissingIncludeDiags) {271 assert(Diag.Fixes.size() == 1 && "Expected exactly one fix.");272 for (const auto &Edit : Diag.Fixes.front().Edits) {273 Edits.try_emplace(Edit.newText, Edit);274 }275 }276 for (auto &It : Edits)277 AddAllMissing.Edits.push_back(std::move(It.second));278 return AddAllMissing;279}280Fix fixAll(const Fix &RemoveAllUnused, const Fix &AddAllMissing) {281 Fix FixAll;282 FixAll.Message = "fix all includes";283 284 for (const auto &F : RemoveAllUnused.Edits)285 FixAll.Edits.push_back(F);286 for (const auto &F : AddAllMissing.Edits)287 FixAll.Edits.push_back(F);288 return FixAll;289}290 291std::vector<const Inclusion *>292getUnused(ParsedAST &AST,293 const llvm::DenseSet<IncludeStructure::HeaderID> &ReferencedFiles,294 bool AnalyzeAngledIncludes) {295 trace::Span Tracer("IncludeCleaner::getUnused");296 std::vector<const Inclusion *> Unused;297 for (const Inclusion &MFI : AST.getIncludeStructure().MainFileIncludes) {298 if (!MFI.HeaderID)299 continue;300 auto IncludeID = static_cast<IncludeStructure::HeaderID>(*MFI.HeaderID);301 if (ReferencedFiles.contains(IncludeID))302 continue;303 if (!mayConsiderUnused(MFI, AST, &AST.getPragmaIncludes(),304 AnalyzeAngledIncludes)) {305 dlog("{0} was not used, but is not eligible to be diagnosed as unused",306 MFI.Written);307 continue;308 }309 Unused.push_back(&MFI);310 }311 return Unused;312}313 314} // namespace315 316std::vector<include_cleaner::SymbolReference>317collectMacroReferences(ParsedAST &AST) {318 const auto &SM = AST.getSourceManager();319 auto &PP = AST.getPreprocessor();320 std::vector<include_cleaner::SymbolReference> Macros;321 for (const auto &[_, Refs] : AST.getMacros().MacroRefs) {322 for (const auto &Ref : Refs) {323 auto Loc = SM.getComposedLoc(SM.getMainFileID(), Ref.StartOffset);324 const auto *Tok = AST.getTokens().spelledTokenContaining(Loc);325 if (!Tok)326 continue;327 auto Macro = locateMacroAt(*Tok, PP);328 if (!Macro)329 continue;330 auto DefLoc = Macro->NameLoc;331 if (!DefLoc.isValid())332 continue;333 Macros.push_back(334 {include_cleaner::Macro{/*Name=*/PP.getIdentifierInfo(Tok->text(SM)),335 DefLoc},336 Tok->location(),337 Ref.InConditionalDirective ? include_cleaner::RefType::Ambiguous338 : include_cleaner::RefType::Explicit});339 }340 }341 342 return Macros;343}344 345include_cleaner::Includes convertIncludes(const ParsedAST &AST) {346 auto &SM = AST.getSourceManager();347 348 include_cleaner::Includes ConvertedIncludes;349 // We satisfy Includes's contract that search dirs and included files have350 // matching path styles: both ultimately use FileManager::getCanonicalName().351 for (const auto &Dir : AST.getIncludeStructure().SearchPathsCanonical)352 ConvertedIncludes.addSearchDirectory(Dir);353 354 for (const Inclusion &Inc : AST.getIncludeStructure().MainFileIncludes) {355 include_cleaner::Include TransformedInc;356 llvm::StringRef WrittenRef = llvm::StringRef(Inc.Written);357 TransformedInc.Spelled = WrittenRef.trim("\"<>");358 TransformedInc.HashLocation =359 SM.getComposedLoc(SM.getMainFileID(), Inc.HashOffset);360 TransformedInc.Line = Inc.HashLine + 1;361 TransformedInc.Angled = WrittenRef.starts_with("<");362 // Inc.Resolved is canonicalized with clangd::getCanonicalPath(),363 // which is based on FileManager::getCanonicalName(ParentDir).364 auto FE = SM.getFileManager().getFileRef(Inc.Resolved);365 if (!FE) {366 elog("IncludeCleaner: Failed to get an entry for resolved path '{0}' "367 "from include {1} : {2}",368 Inc.Resolved, Inc.Written, FE.takeError());369 continue;370 }371 TransformedInc.Resolved = *FE;372 ConvertedIncludes.add(std::move(TransformedInc));373 }374 return ConvertedIncludes;375}376 377IncludeCleanerFindings378computeIncludeCleanerFindings(ParsedAST &AST, bool AnalyzeAngledIncludes) {379 // Interaction is only polished for C/CPP.380 if (AST.getLangOpts().ObjC)381 return {};382 const auto &SM = AST.getSourceManager();383 include_cleaner::Includes ConvertedIncludes = convertIncludes(AST);384 const FileEntry *MainFile = SM.getFileEntryForID(SM.getMainFileID());385 auto PreamblePatch = PreamblePatch::getPatchEntry(AST.tuPath(), SM);386 387 std::vector<include_cleaner::SymbolReference> Macros =388 collectMacroReferences(AST);389 std::vector<MissingIncludeDiagInfo> MissingIncludes;390 llvm::DenseSet<IncludeStructure::HeaderID> Used;391 trace::Span Tracer("include_cleaner::walkUsed");392 OptionalDirectoryEntryRef ResourceDir = AST.getPreprocessor()393 .getHeaderSearchInfo()394 .getModuleMap()395 .getBuiltinDir();396 include_cleaner::walkUsed(397 AST.getLocalTopLevelDecls(), /*MacroRefs=*/Macros,398 &AST.getPragmaIncludes(), AST.getPreprocessor(),399 [&](const include_cleaner::SymbolReference &Ref,400 llvm::ArrayRef<include_cleaner::Header> Providers) {401 bool Satisfied = false;402 for (const auto &H : Providers) {403 if (H.kind() == include_cleaner::Header::Physical &&404 (H.physical() == MainFile || H.physical() == PreamblePatch ||405 H.physical().getDir() == ResourceDir)) {406 Satisfied = true;407 continue;408 }409 for (auto *Inc : ConvertedIncludes.match(H)) {410 Satisfied = true;411 auto HeaderID =412 AST.getIncludeStructure().getID(&Inc->Resolved->getFileEntry());413 assert(HeaderID.has_value() &&414 "ConvertedIncludes only contains resolved includes.");415 Used.insert(*HeaderID);416 }417 }418 419 if (Satisfied || Providers.empty() ||420 Ref.RT != include_cleaner::RefType::Explicit)421 return;422 423 // Check if we have any headers with the same spelling, in edge cases424 // like `#include_next "foo.h"`, the user can't ever include the425 // physical foo.h, but can have a spelling that refers to it.426 // We postpone this check because spelling a header for every usage is427 // expensive.428 std::string Spelling = include_cleaner::spellHeader(429 {Providers.front(), AST.getPreprocessor().getHeaderSearchInfo(),430 MainFile});431 for (auto *Inc :432 ConvertedIncludes.match(include_cleaner::Header{Spelling})) {433 Satisfied = true;434 auto HeaderID =435 AST.getIncludeStructure().getID(&Inc->Resolved->getFileEntry());436 assert(HeaderID.has_value() &&437 "ConvertedIncludes only contains resolved includes.");438 Used.insert(*HeaderID);439 }440 if (Satisfied)441 return;442 443 // We actually always want to map usages to their spellings, but444 // spelling locations can point into preamble section. Using these445 // offsets could lead into crashes in presence of stale preambles. Hence446 // we use "getFileLoc" instead to make sure it always points into main447 // file.448 // FIXME: Use presumed locations to map such usages back to patched449 // locations safely.450 auto Loc = SM.getFileLoc(Ref.RefLocation);451 // File locations can be outside of the main file if macro is expanded452 // through an #include.453 while (SM.getFileID(Loc) != SM.getMainFileID())454 Loc = SM.getIncludeLoc(SM.getFileID(Loc));455 auto TouchingTokens =456 syntax::spelledTokensTouching(Loc, AST.getTokens());457 assert(!TouchingTokens.empty());458 // Loc points to the start offset of the ref token, here we use the last459 // element of the TouchingTokens, e.g. avoid getting the "::" for460 // "ns::^abc".461 MissingIncludeDiagInfo DiagInfo{462 Ref.Target, TouchingTokens.back().range(SM), Providers};463 MissingIncludes.push_back(std::move(DiagInfo));464 });465 // Put possibly equal diagnostics together for deduplication.466 // The duplicates might be from macro arguments that get expanded multiple467 // times.468 llvm::stable_sort(MissingIncludes, [](const MissingIncludeDiagInfo &LHS,469 const MissingIncludeDiagInfo &RHS) {470 // First sort by reference location.471 if (LHS.SymRefRange != RHS.SymRefRange) {472 // We can get away just by comparing the offsets as all the ranges are in473 // main file.474 return LHS.SymRefRange.beginOffset() < RHS.SymRefRange.beginOffset();475 }476 // For the same location, break ties using the symbol. Note that this won't477 // be stable across runs.478 using MapInfo = llvm::DenseMapInfo<include_cleaner::Symbol>;479 return MapInfo::getHashValue(LHS.Symbol) <480 MapInfo::getHashValue(RHS.Symbol);481 });482 MissingIncludes.erase(llvm::unique(MissingIncludes), MissingIncludes.end());483 std::vector<const Inclusion *> UnusedIncludes =484 getUnused(AST, Used, AnalyzeAngledIncludes);485 return {std::move(UnusedIncludes), std::move(MissingIncludes)};486}487 488bool isPreferredProvider(const Inclusion &Inc,489 const include_cleaner::Includes &Includes,490 llvm::ArrayRef<include_cleaner::Header> Providers) {491 for (const auto &H : Providers) {492 auto Matches = Includes.match(H);493 for (const include_cleaner::Include *Match : Matches)494 if (Match->Line == unsigned(Inc.HashLine + 1))495 return true; // this header is (equal) best496 if (!Matches.empty())497 return false; // another header is better498 }499 return false; // no header provides the symbol500}501 502std::vector<Diag> issueIncludeCleanerDiagnostics(503 ParsedAST &AST, llvm::StringRef Code,504 const IncludeCleanerFindings &Findings, const ThreadsafeFS &TFS,505 HeaderFilter IgnoreHeaders, HeaderFilter AngledHeaders,506 HeaderFilter QuotedHeaders) {507 trace::Span Tracer("IncludeCleaner::issueIncludeCleanerDiagnostics");508 std::vector<Diag> UnusedIncludes = generateUnusedIncludeDiagnostics(509 AST.tuPath(), Findings.UnusedIncludes, Code, IgnoreHeaders);510 std::optional<Fix> RemoveAllUnused = removeAllUnusedIncludes(UnusedIncludes);511 512 std::vector<Diag> MissingIncludeDiags = generateMissingIncludeDiagnostics(513 AST, Findings.MissingIncludes, Code, IgnoreHeaders, AngledHeaders,514 QuotedHeaders, TFS);515 std::optional<Fix> AddAllMissing = addAllMissingIncludes(MissingIncludeDiags);516 517 std::optional<Fix> FixAll;518 if (RemoveAllUnused && AddAllMissing)519 FixAll = fixAll(*RemoveAllUnused, *AddAllMissing);520 521 auto AddBatchFix = [](const std::optional<Fix> &F, clang::clangd::Diag *Out) {522 if (!F)523 return;524 Out->Fixes.push_back(*F);525 };526 for (auto &Diag : MissingIncludeDiags) {527 AddBatchFix(MissingIncludeDiags.size() > 1 ? AddAllMissing : std::nullopt,528 &Diag);529 AddBatchFix(FixAll, &Diag);530 }531 for (auto &Diag : UnusedIncludes) {532 AddBatchFix(UnusedIncludes.size() > 1 ? RemoveAllUnused : std::nullopt,533 &Diag);534 AddBatchFix(FixAll, &Diag);535 }536 537 auto Result = std::move(MissingIncludeDiags);538 llvm::move(UnusedIncludes, std::back_inserter(Result));539 return Result;540}541 542} // namespace clang::clangd543