[clangd] IncludeCleaner as a library: Find all references to symbols in the file

[kbobyrev]

Summary

This is the first patch in an ongoing attempt of Include Cleaner: unused/missing
headere diagnostics, an IWYU-like functionality implementation for clangd. The
work is split into (mostly) distinct and parallelizable pieces:

• Finding all referenced locations (this patch).
• Finding all referenced locations of macros.
• Building IncludeGraph and marking headers as unused, used and directly used.
• Making use of the introduced library and add an option to use in clangd.

---

• Adding support for standard library headers (possibly through mapping genfiles).

Based on https://reviews.llvm.org/D100540.

[kbobyrev]

Significantly decrease the scope of this change. Focus on "IWYU as a library",
do not propagate into the other parts of clangd yet and keep the change
self-contained for the most part.

[kbobyrev]

Trim the patch even further: only extract locations, prune header marking logic
etc.

[kbobyrev]

Trim the patch even further: the scope is now simply findAllReferences
mechanism. Add more tests and improve functionality (handle using decls and
implicit types).

[kbobyrev]

Add one more test.

[kbobyrev]

Exclude std:: namespace handling.

[kbobyrev]

Improve comments, refactor some pieces, add more tests.

[kbobyrev]

Remove some code from the next chunk of IWYU work.

[kbobyrev]

Rebase on top of main.

[tschuett]

@kimgr

[sammccall]

First some thoughts on names... (hopefully to avoid some confusion)

IWYU might be used here to mean three things:

• the IWYU coding style/policy that says you should #include headers for the symbols you make use of, and no others
• the IWYU tool which applies IWYU style to files
• more generally, features that encourage hygiene policies for #includes ("IWYU functionality")

This work is about the last of these: putting header hygiene features in clangd. (Specifically, likely unused-include and missing-include warnings).
I think we should avoid the name "IWYU as a library" or "IWYU functionality" as it's ambiguous and also misleading:

• policy: we're likely to support policies other than the IWYU style
• tool: it's not likely to match the design or feature set of the IWYU tool

IncludeHygiene would be an ok name I think but a bit of a mouthful. WDYT?

(This work is definitely inspired by the IWYU tool and I'd used the name in discussions/prototypes, so this confusion is largely my fault! We also did this with clang-include-fixer which ended up as clangd/IncludeFixer.h, though the designs are much more similar)

[sammccall]

Thanks, this scope looks good for a first patch!

clang-tools-extra/clangd/IWYU.cpp

19

The first sentence doesn't mean much to me, I think we could just drop it?

64

Is this just "FIXME: should this behavior be configurable or tweaked?"

I think it's clear enough what "this behavior" is in context.
Whereas the rest of the comment adds some confusion (e.g. what's an "implicit type", what usage of auto are you talking about etc. And I think it's *way* too soon to say that it *should* be configurable - remember the application is unused-include, turning this off only grants the ability for headers to be marked unused even if they define the type of a subexpression.

I think it's more likely we'd tweak the heuristic in the future, e.g. only do this if it's a type that can be incomplete.

74

i usually add a private using Base = ... and refer to Base::TraverseType(T) - intent is clearer and often we end up with several of these

96

this name is a bit vague (why wouldn't we add it?), maybe isNew?

clang-tools-extra/clangd/IWYU.h

11

Related to the naming discussion, this should first say what the functionality is (warnings about header hygiene: misuse of transitive headers and unused includes).
Then definitely credit the IWYU tool and mention the differences.

18

I'm not sure we want to do this (or plan to do this) unless we have some idea of how discovery would work.

35

Maybe just "Finds locations of all symbols used in the main file"?

If you want to talk about traversal/impl strategy, that's OK but not in the first paragraph.

36

I'd be explicit that the returned locations may be macro expansions, and are not resolved to their spelling/expansion location.

39

I'm not quite sure what this is saying/who the audience for the comment is.
Maybe it's interesting to say something like

We use this to compute unused headers, so:

• we cover the whole file in a single traversal for efficiency
• we don't attempt to describe where symbols were referenced from
• in ambiguous cases (e.g. implicitly used symbols, multiple declarations) we err on the side of reporting all possible locations

42

It's a bit more general than this (e.g. multiple declaration). See previous comment for a wording suggestion

44

I actually don't think we'd use the same entrypoint for missing include, but rather duplicate it (and *maybe* share some impl details whose docs don't belong here).

The reason is we get to "throw away" different info in each case to make the data structures as tight as possible:

• for unused include, we can throw away the reference location and just track sets of locations and then files. This means we traverse first, build a bundle of locations, and then process them together.
• for missing include, we need the reference location, but don't need to associate them with specific #includes. So the tight data structure here is a set of allowed FileIDs plus a cache for macro FileIDs. Then we'll traverse last and query one symbol at a time, with early exit.

Comments about future plans can sometimes be useful I think, but this one seems pretty unlikely to pan out.

48

It's not obvious what this actually means.
Would be good to mention expanding macros

clang-tools-extra/clangd/unittests/IWYUTests.cpp

29

I think i'd be useful to have a comment in these for the node type or special case that's being tested

First few are

DeclRefExpr
RecordType
TypedefType
MemberExpr
Expr (type is traversed)
Redecls
CXXConstructExpr

85

I don't think so, IMO current behavior is fine.
B is not named, nor can its absence cause the type to be incomplete.

98

A bit more explicit about the bug?

When a type is resolved via a using declaration, the UsingShadowDecl is not referenced in the AST.
Compare to TypedefType, or DeclRefExpr::getFoundDecl().

[kbobyrev]

Thank you for the great suggestions! Indeed, we already have the confusion
regarding IWYU having the CLI flag and users are thinking we provide some sort
of integration/implementation. Having even more confusion (implementing
similar) functionality for our needs is not what we want (also, apologies for
confusion,"as a library" was more about the patch in this context - meaning not
a "usable" feature yet but a smaller scope where we just start the
implementation as the library that can only be used in tests for now). Hence,
renamed the feature to "Include Sanity" (close to Include Hygiene but sounds
better IMO, please let me know if you think otherwise).

I have addressed the review comments and will base my next patch on this (this
patch is probably mostly the blocker for the upcoming ones).

[kbobyrev]

Rename.

[kbobyrev]

Remove findReferencedFiles (to be introduced in the next patch) to preserve
proposed granularity.

[kbobyrev]

Fix tests name.

[kbobyrev]

[clangd] IncludeCleaner: Mark used headers.

Follow-up on D105426.

[kbobyrev]

Push back to the origin.

[sammccall]

clang-tools-extra/clangd/IncludeCleaner.cpp

65 ↗

(On Diff #366833)

I just realized this uses "T" if any expression has type "T*" even if never dereferenced, this is probably a gross overestimate. Nevertheless I guess fine for now.

101 ↗

(On Diff #366833)

this struct is not used in this patch

[kbobyrev]

Remove unused code.

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   HeaderSourceSwitch.cpp
   HeuristicResolver.cpp
   Hover.cpp
   IncludeFixer.cpp
   InlayHints.cpp
+  IWYU.cpp
   JSONTransport.cpp
   PathMapping.cpp
   Protocol.cpp
   Quality.cpp
   ParsedAST.cpp
   Preamble.cpp
   RIFF.cpp
   Selection.cpp

clang-tools-extra/clangd/Headers.h

public:
   // Usually it should be SM.getFileEntryForID(SM.getMainFileID())->getName().
   llvm::StringMap<unsigned> includeDepth(llvm::StringRef Root) const;
 
   // This updates IncludeDepth(), but not MainFileIncludes.
   void recordInclude(llvm::StringRef IncludingName,
                      llvm::StringRef IncludedName,
                      llvm::StringRef IncludedRealName);
 
+  using AbstractIncludeGraph = llvm::DenseMap<unsigned, SmallVector<unsigned>>;
+
 private:
   // Identifying files in a way that persists from preamble build to subsequent
   // builds is surprisingly hard. FileID is unavailable in InclusionDirective(),
   // and RealPathName and UniqueID are not preserved in the preamble.
   // We use the FileEntry::Name, which is stable, interned into a "file index".
   // The paths we want to expose are the RealPathName, so store those too.
   std::vector<std::string> RealPathNames; // In file index order.
   unsigned fileIndex(llvm::StringRef Name);

clang-tools-extra/clangd/IWYU.h

+//===--- IWYU.h - include-what-you-use analysis -----------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This defines functionality modeled after Include-What-You-Use
+/// (https://include-what-you-use.org/). The variant we implement is not
+/// equivalent to the original tool since we have different design limitations
+/// such as performance requirements but we are trying to make it compatible
+/// with the original tool in the most popular and useful cases.
+///
+/// FIXME(kirillbobyrev): Add support for IWYU pragmas.
+/// FIXME(kirillbobyrev): Add support for mapping files.
+/// FIXME(kirillbobyrev): Add support for standard library headers.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_IWYU_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_IWYU_H
+
+#include "Headers.h"
+#include "ParsedAST.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/DenseSet.h"
+
+namespace clang {
+namespace clangd {
+
+using ReferencedLocations = llvm::DenseSet<SourceLocation>;
+/// Goes through main file AST and computes all the locations used symbols are
+/// coming from. These locations are later used to determine which headers
+/// should be marked as "used" and "directly used".
+///
+/// Because of the clangd limitations, this should be efficient,
+/// hence there is only one AST traversal for the whole process.
+///
+/// NOTE: The balance is currently shifted towards considering some of the
+/// implicitly used symbols as "used" for the sake of providing less noisy
+/// "unused header" diagnostics. However, this should be re-evalated once we
+/// also want to surface "missing header" diagnostics.
+ReferencedLocations findReferencedLocations(ParsedAST &AST);
+
+/// Computes all referenced files given a set of SourceLocations that were
+/// extracted from symbol declarations.
+llvm::DenseSet<FileID> findReferencedFiles(const ReferencedLocations &Locs,
+                                           const SourceManager &SM);
+
+} // namespace clangd
+} // namespace clang
+
+#endif

clang-tools-extra/clangd/IWYU.cpp

+//===--- IWYU.cpp -----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "IWYU.h"
+#include "support/Logger.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Basic/SourceLocation.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+/// Main "driver" of the IWYU symbol usage discovery mechanism. Crawler
+/// traverses the AST and feeds in the locations of (sometimes implicitly) used
+/// symbols into \p Result.
+class ReferencedLocationCrawler
+    : public RecursiveASTVisitor<ReferencedLocationCrawler> {
+public:
+  ReferencedLocationCrawler(ReferencedLocations &Result) : Result(Result) {}
+
+  bool VisitDeclRefExpr(DeclRefExpr *DRE) {
+    add(DRE->getDecl());
+    add(DRE->getFoundDecl());
+    return true;
+  }
+
+  bool VisitMemberExpr(MemberExpr *ME) {
+    add(ME->getMemberDecl());
+    add(ME->getFoundDecl().getDecl());
+    return true;
+  }
+
+  bool VisitTagType(TagType *TT) {
+    add(TT->getDecl());
+    return true;
+  }
+
+  bool VisitCXXConstructExpr(CXXConstructExpr *CCE) {
+    add(CCE->getConstructor());
+    return true;
+  }
+
+  bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
+    if (shouldAdd(TST)) {
+      add(TST->getTemplateName().getAsTemplateDecl()); // Primary template.
+      add(TST->getAsCXXRecordDecl());                  // Specialization
+    }
+    return true;
+  }
+
+  bool VisitTypedefType(TypedefType *TT) {
+    add(TT->getDecl());
+    return true;
+  }
+
+  // Consider types of any subexpression used, even if the type is not named.
+  // This is helpful in getFoo().bar(), where Foo must be complete.
+  // FIXME(kirillbobyrev): This is a tricky case that raises a question - should
+  // we consider implicit types to be "used"? With auto's it's not so clear.
+  // This should probably be controlled with a flag.
+  bool VisitExpr(Expr *E) {
+    TraverseType(E->getType());
+    return true;
+  }
+
+  bool TraverseType(QualType T) {
+    if (shouldAdd(T.getTypePtrOrNull())) { // don't care about quals
+      RecursiveASTVisitor<ReferencedLocationCrawler>::TraverseType(T);
+    }
+    return true;
+  }
+
+  bool VisitUsingDecl(UsingDecl *D) {
+    for (const auto *Shadow : D->shadows()) {
+      add(Shadow->getTargetDecl());
+    }
+    return true;
+  }
+
+private:
+  void add(const Decl *D) {
+    if (!D || !shouldAdd(D->getCanonicalDecl())) {
+      return;
+    }
+    for (const Decl *Redecl : D->redecls()) {
+      Result.insert(Redecl->getLocation());
+    }
+  }
+
+  bool shouldAdd(const void *P) { return P && Visited.insert(P).second; }
+
+  ReferencedLocations &Result;
+  llvm::DenseSet<const void *> Visited;
+};
+
+// Given a set of referenced FileIDs, determines all the potentially-referenced
+// files and macros by traversing expansion/spelling locations of macro IDs.
+// This is used to map the referenced SourceLocations onto real files.
+struct ReferencedFiles {
+  ReferencedFiles(const SourceManager &SM) : SM(SM) {}
+  llvm::DenseSet<FileID> Files;
+  llvm::DenseSet<FileID> Macros;
+  const SourceManager &SM;
+
+  void add(SourceLocation Loc) { add(SM.getFileID(Loc), Loc); }
+
+  void add(FileID FID, SourceLocation Loc) {
+    if (FID.isInvalid())
+      return;
+    assert(SM.isInFileID(Loc, FID));
+    if (Loc.isFileID()) {
+      Files.insert(FID);
+      return;
+    }
+    // Don't process the same macro FID twice.
+    if (!Macros.insert(FID).second)
+      return;
+    const auto &Exp = SM.getSLocEntry(FID).getExpansion();
+    add(Exp.getSpellingLoc());
+    add(Exp.getExpansionLocStart());
+    add(Exp.getExpansionLocEnd());
+  }
+};
+
+} // namespace
+
+ReferencedLocations findReferencedLocations(ParsedAST &AST) {
+  ReferencedLocations Result;
+  ReferencedLocationCrawler Crawler(Result);
+  Crawler.TraverseAST(AST.getASTContext());
+  // FIXME(kirillbobyrev): Handle macros.
+  return Result;
+}
+
+llvm::DenseSet<FileID> findReferencedFiles(const ReferencedLocations &Locs,
+                                           const SourceManager &SM) {
+  std::vector<SourceLocation> Sorted{Locs.begin(), Locs.end()};
+  llvm::sort(Sorted); // This groups by FileID!
+  ReferencedFiles Result(SM);
+  for (auto It = Sorted.begin(); It < Sorted.end();) {
+    auto FID = SM.getFileID(*It);
+    Result.add(FID, *It);
+    // Cheaply skip over all the other locations from the same FileID.
+    // This avoids lots of redundant Loc->File lookups for the same file.
+    do {
+      ++It;
+    } while (It != Sorted.end() && SM.isInFileID(*It, FID));
+  }
+  return std::move(Result.Files);
+}
+
+} // namespace clangd
+} // namespace clang

clang-tools-extra/clangd/unittests/CMakeLists.txt

add_unittest(ClangdUnitTests ClangdTests
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   HeaderSourceSwitchTests.cpp
   HoverTests.cpp
   IndexActionTests.cpp
   IndexTests.cpp
   InlayHintTests.cpp
+  IWYUTests.cpp
   JSONTransportTests.cpp
   LoggerTests.cpp
   LSPBinderTests.cpp
   LSPClient.cpp
   ModulesTests.cpp
   ParsedASTTests.cpp
   PathMappingTests.cpp
   PreambleTests.cpp

clang-tools-extra/clangd/unittests/IWYUTests.cpp

+//===--- IWYUTests.cpp ------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Annotations.h"
+#include "IWYU.h"
+#include "TestTU.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+using testing::ElementsAreArray;
+
+TEST(IWYU, ReferencedLocations) {
+  struct TestCase {
+    std::string HeaderCode;
+    std::string MainCode;
+  };
+  TestCase Cases[] = {
+      {
+          "int ^x();",
+          "int y = x();",
+      },
+      {
+          "class ^X;",
+          "X *y;",
+      },
+      {
+          "using ^Integer = int;",
+          "Integer x;",
+      },
+      {
+          "struct ^X{int ^a;}; X ^foo();",
+          "int y = foo().a;",
+      },
+      {
+          "class ^X{}; X ^foo();",
+          "auto bar() { return foo(); }",
+      },
+      {
+          "class ^X; class ^X{}; class ^X;",
+          "X *y;",
+      },
+      {
+          "struct ^X { ^X(int) {} int ^foo(); };",
+          "auto x = X(42); auto y = x.foo();",
+      },
+      {
+          "struct ^X { static bool ^foo(); }; bool X::^foo() {}",
+          "auto b = X::foo();",
+      },
+      {
+          "template <typename> class ^X;",
+          "X<int> *y;",
+      },
+      {
+          "typedef bool ^Y; template <typename T> struct ^X {};",
+          "X<Y> x;",
+      },
+      {
+          "struct Foo; struct ^Foo{}; typedef Foo ^Bar;",
+          "Bar b;",
+      },
+      {
+          "class ^X{}; X ^getX();",
+          "auto x = getX();",
+      },
+      {
+          "namespace ns { struct ^X; struct ^X {}; }",
+          "using ns::X;",
+      },
+      {
+          "namespace ns { struct X; struct X {}; }",
+          "using namespace ns;",
+      },
+      {
+          // FIXME(kirillbobyrev): Should B also be marked as used?
+          "struct ^A {}; using B = A; using ^C = B;",
+          "C a;",
+      },
+      {
+          "enum ^Color { ^Red = 42, Green = 9000};",
+          "int MyColor = Red;",
+      },
+      {
+          "struct ^X { enum ^Language { ^CXX = 42, Python = 9000}; };",
+          "int Lang = X::CXX;",
+      },
+      {
+          // FIXME(kirillbobyrev): Should report the UsingDecl.
+          // This information is not preserved in the AST.
+          //                                 ^
+          "namespace ns { class ^X; }; using ns::X;",
+          "X *y;",
+      }};
+  for (const TestCase &T : Cases) {
+    TestTU TU;
+    TU.Code = T.MainCode;
+    Annotations Header(T.HeaderCode);
+    TU.HeaderCode = Header.code().str();
+    auto AST = TU.build();
+
+    std::vector<Position> Points;
+    for (const auto &Loc : findReferencedLocations(AST)) {
+      if (AST.getSourceManager().getBufferName(Loc).endswith(
+              TU.HeaderFilename)) {
+        Points.push_back(offsetToPosition(
+            TU.HeaderCode, AST.getSourceManager().getFileOffset(Loc)));
+      }
+    }
+    llvm::sort(Points);
+
+    EXPECT_EQ(Points, Header.points()) << T.HeaderCode << "\n---\n"
+                                       << T.MainCode;
+  }
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang