[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

18 ↗

(On Diff #364735)

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

63 ↗

(On Diff #364735)

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.

73 ↗

(On Diff #364735)

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

95 ↗

(On Diff #364735)

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

clang-tools-extra/clangd/IWYU.h

10 ↗

(On Diff #364735)

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.

17 ↗

(On Diff #364735)

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

34 ↗

(On Diff #364735)

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.

35 ↗

(On Diff #364735)

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

38 ↗

(On Diff #364735)

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

41 ↗

(On Diff #364735)

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

43 ↗

(On Diff #364735)

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.

47 ↗

(On Diff #364735)

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

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

28 ↗

(On Diff #364735)

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

84 ↗

(On Diff #364735)

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

97 ↗

(On Diff #364735)

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
   FS.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
   HeaderSourceSwitch.cpp
   HeuristicResolver.cpp
   Hover.cpp
   IncludeFixer.cpp
+  IncludeSanity.cpp
   InlayHints.cpp
   JSONTransport.cpp
   PathMapping.cpp
   Protocol.cpp
   Quality.cpp
   ParsedAST.cpp
   Preamble.cpp
   RIFF.cpp

clang-tools-extra/clangd/IncludeSanity.h

+//===--- IncludeSanity.h - Unused/Missing Headers 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
+/// Include Sanity is clangd functionality for providing diagnostics for misuse
+/// of transitive headers and unused includes. It is inspired by
+/// Include-What-You-Use tool (https://include-what-you-use.org/). Our goal is
+/// to provide useful warnings in most popular scenarios but not 1:1 exact
+/// feature compatibility.
+///
+/// FIXME(kirillbobyrev): Add support for IWYU pragmas.
+/// FIXME(kirillbobyrev): Add support for standard library headers.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_SANITY_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_SANITY_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>;
+/// Finds locations of all symbols used in the main file.
+///
+/// Uses RecursiveASTVisitor to go through main file AST and computes all the
+/// locations used symbols are coming from. Returned locations may be macro
+/// expansions, and are not resolved to their spelling/expansion location. These
+/// locations are later used to determine which headers should be marked as
+/// "used" and "directly used".
+///
+/// We use this to compute unused headers, so we:
+///
+/// - cover the whole file in a single traversal for efficiency
+/// - don't attempt to describe where symbols were referenced from in
+///   ambiguous cases (e.g. implicitly used symbols, multiple declarations)
+/// - err on the side of reporting all possible locations
+ReferencedLocations findReferencedLocations(ParsedAST &AST);
+
+/// Retrieves IDs of all files containing SourceLocations from \p Locs. Those
+/// locations could be within macro expansions and are not resolved to their
+/// spelling locations.
+llvm::DenseSet<FileID> findReferencedFiles(const ReferencedLocations &Locs,
+                                           const SourceManager &SM);
+
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_SANITY_H

clang-tools-extra/clangd/IncludeSanity.cpp

+//===--- IncludeSanity.cpp - Unused/Missing Headers 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "IncludeSanity.h"
+#include "support/Logger.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Basic/SourceLocation.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+/// 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 (isNew(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): Should we tweak this? It may not be desirable to
+  // consider types "used" when they are not directly spelled in code.
+  bool VisitExpr(Expr *E) {
+    TraverseType(E->getType());
+    return true;
+  }
+
+  bool TraverseType(QualType T) {
+    if (isNew(T.getTypePtrOrNull())) { // don't care about quals
+      Base::TraverseType(T);
+    }
+    return true;
+  }
+
+  bool VisitUsingDecl(UsingDecl *D) {
+    for (const auto *Shadow : D->shadows()) {
+      add(Shadow->getTargetDecl());
+    }
+    return true;
+  }
+
+private:
+  using Base = RecursiveASTVisitor<ReferencedLocationCrawler>;
+
+  void add(const Decl *D) {
+    if (!D || !isNew(D->getCanonicalDecl())) {
+      return;
+    }
+    for (const Decl *Redecl : D->redecls()) {
+      Result.insert(Redecl->getLocation());
+    }
+  }
+
+  bool isNew(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
   FindTargetTests.cpp
   FormatTests.cpp
   FSTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
   HeaderSourceSwitchTests.cpp
   HoverTests.cpp
+  IncludeSanityTests.cpp
   IndexActionTests.cpp
   IndexTests.cpp
   InlayHintTests.cpp
   JSONTransportTests.cpp
   LoggerTests.cpp
   LSPBinderTests.cpp
   LSPClient.cpp
   ModulesTests.cpp

clang-tools-extra/clangd/unittests/IncludeSanityTests.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 "IncludeSanity.h"
+#include "TestTU.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+TEST(IWYU, ReferencedLocations) {
+  struct TestCase {
+    std::string HeaderCode;
+    std::string MainCode;
+  };
+  TestCase Cases[] = {
+      // DeclRefExpr
+      {
+          "int ^x();",
+          "int y = x();",
+      },
+      // RecordDecl
+      {
+          "class ^X;",
+          "X *y;",
+      },
+      // TypedefType and UsingDecls
+      {
+          "using ^Integer = int;",
+          "Integer x;",
+      },
+      {
+          "namespace ns { struct ^X; struct ^X {}; }",
+          "using ns::X;",
+      },
+      {
+          "namespace ns { struct X; struct X {}; }",
+          "using namespace ns;",
+      },
+      {
+          "struct ^A {}; using B = A; using ^C = B;",
+          "C a;",
+      },
+      {
+          "typedef bool ^Y; template <typename T> struct ^X {};",
+          "X<Y> x;",
+      },
+      {
+          "struct Foo; struct ^Foo{}; typedef Foo ^Bar;",
+          "Bar b;",
+      },
+      // MemberExpr
+      {
+          "struct ^X{int ^a;}; X ^foo();",
+          "int y = foo().a;",
+      },
+      // Expr (type is traversed)
+      {
+          "class ^X{}; X ^foo();",
+          "auto bar() { return foo(); }",
+      },
+      // Redecls
+      {
+          "class ^X; class ^X{}; class ^X;",
+          "X *y;",
+      },
+      // Constructor
+      {
+          "struct ^X { ^X(int) {} int ^foo(); };",
+          "auto x = X(42); auto y = x.foo();",
+      },
+      // Static function
+      {
+          "struct ^X { static bool ^foo(); }; bool X::^foo() {}",
+          "auto b = X::foo();",
+      },
+      // TemplateRecordDecl
+      {
+          "template <typename> class ^X;",
+          "X<int> *y;",
+      },
+      // Type name not spelled out in code
+      {
+          "class ^X{}; X ^getX();",
+          "auto x = getX();",
+      },
+      // Enums
+      {
+          "enum ^Color { ^Red = 42, Green = 9000};",
+          "int MyColor = Red;",
+      },
+      {
+          "struct ^X { enum ^Language { ^CXX = 42, Python = 9000}; };",
+          "int Lang = X::CXX;",
+      },
+      {
+          // When a type is resolved via a using declaration, the
+          // UsingShadowDecl is not referenced in the AST.
+          // Compare to TypedefType, or DeclRefExpr::getFoundDecl().
+          //                                 ^
+          "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