[clangd] Implement cross reference request for #include lines.

[VitaNuo]

Smaller improvements.

[VitaNuo]

Formatting.

[VitaNuo]

Remove redundant code.

[VitaNuo]

Formatting.

[kadircet]

clang-tools-extra/clangd/XRefs.cpp

1339

can we put the rest into a separate function (I know this function is already quite long, but I think we shouldn't make it worse, and probably refactor soon). I believe something like below should work?

std::vector<Reference> getIncludeUsages(const ParsedAST &AST, const Inclusion &Include);

1348

nit: no need to calculate the file location, if we're not going to emit a reference. so maybe move this into the place where we're going to use the Loc.

1348

this file location might fall outside of the main file when they get expanded through #include directives, so we need something like https://reviews.llvm.org/D147139

1349

we're implementing and testing this logic twice now, once in here and once in hover. can we instead have a helper in IncludeCleaner.h that looks like:

std::optional<include_cleaner::Header> firstSatisfiedProvider(const include_cleaner::Includes& Includes, llvm::ArrayRef<include_cleaner::Header> Providers);
// I'd actually return the matching `std::vector<const Include*>` (the highest ranked provider that matched some includes in main file), and check if the include of interest is part of that set for rest of the operations.
// Since it represents both the provider and the include in the main file. whereas the provider on it's own doesn't say anything about which include in main file triggered satisfaction.

and turn these call sites into

auto Provider = firstSatisfiedProvider(ConvertedMainFileIncludes, Providers);
if(!Provider || ReferencedInclude.match(Provider).empty())
  return;
// Include in question provides the symbol, do magic.

1359

no need to re-run the lexer, these references are inside the main file for sure, so you can use token buffer instead.

1382

we can return Results directly here, no need to run rest of the logic

2004–2007

can you revert changes below? I feel like they're unrelated formatting changes

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

1909

rather than introducing these into all tests, can we have our own TestTU and whatnot in the relevant test? something like MainFileReferencesOnly test

2322

can you also have a second include header that provides some other symbols and make sure references of those don't get highlighted?

2329

we don't really need rest of these tests, they're testing the "symbol is provided by first provider included in the main file" logic

[VitaNuo]

Address review comments.

[VitaNuo]

Simplify.

[VitaNuo]

Remove extra formatting changes.

[VitaNuo]

Rename function.

[VitaNuo]

Thanks for the comments!

clang-tools-extra/clangd/XRefs.cpp

1349

Is the comment under the code in the first snippet a mistake/outdated content? It confused me.

[VitaNuo]

Simplify.

[kadircet]

clang-tools-extra/clangd/IncludeCleaner.cpp

443 ↗

(On Diff #510042)

return std::nullopt

clang-tools-extra/clangd/IncludeCleaner.h

87 ↗

(On Diff #510042)

can you also move tests related to this functionality from HoverTests into IncludeCleanerTests ?

clang-tools-extra/clangd/XRefs.cpp

1321

can you put this into anon namespace?

we should also change the return type to std::optional<ReferencesResult>, as we can "legitimately" have empty result for an include, e.g. it's unused or all of the refs are implicit etc.

1325

const auto &Includes = AST.getIncludeStructure().MainFileIncludes; (& is the important bit, as we're copying all of them otherwise)

1326

let's move this into the for loop, after we've found a matching include to not necessarily create a copy of all the includes again.

nit: you can also write the loop below as following and reduce some nesting.

auto IncludeOnLine = llvm::find_if(Includes, [&Pos](const Inclusion& Inc) { return Inc.HashLine == Pos.Line; });
if (IncludeOnLine == Includes.end())
  return Results;
const auto &Inc = *IncludeOnLine;
...

1349

that wasn't supposed to be a comment in the code but rather a comment for the code :D i was suggesting to return the set of Includes matched by the first provider, rather than returning the provider. but feel free to keep it as-is.

[VitaNuo]

Address review comments.

[VitaNuo]

Thanks for the comments!

clang-tools-extra/clangd/IncludeCleaner.h

87 ↗

(On Diff #510042)

Not really, not sure what you mean.

This function receives a ranked list of providers that should be a result of include_cleaner analysis.

If I just test the function based on a fake list of providers, the test will be trivial. The current hover test seems to provide more value than that.

[kadircet]

clang-tools-extra/clangd/IncludeCleaner.h

87 ↗

(On Diff #510042)

If I just test the function based on a fake list of providers, the test will be trivial.

but that's the "unit" of logic we're trying to test, no?

[VitaNuo]

Extract a test for th firstMatchedProvider method.

[VitaNuo]

clang-tools-extra/clangd/IncludeCleaner.h

87 ↗

(On Diff #510042)

Ok, I've extracted a test. Hopefully that's what you've meant.

[kadircet]

thanks!

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

398 ↗

(On Diff #514901)

can you add a similar test case in which foo.h comes before bar.h ?

410 ↗

(On Diff #514901)

nit: no need for the filename

[VitaNuo]

Add a test case.

clang-tools-extra/clangd/XRefs.cpp

 //===--- XRefs.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 "XRefs.h"
 #include "AST.h"
 #include "FindSymbols.h"
 #include "FindTarget.h"
 #include "HeuristicResolver.h"
+#include "IncludeCleaner.h"
 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "Quality.h"
 #include "Selection.h"
 #include "SourceCode.h"
 #include "URI.h"
+#include "clang-include-cleaner/Analysis.h"
+#include "clang-include-cleaner/Types.h"
 #include "index/Index.h"
 #include "index/Merge.h"
 #include "index/Relation.h"
 #include "index/SymbolCollector.h"
 #include "index/SymbolID.h"
 #include "index/SymbolLocation.h"
 #include "support/Logger.h"
 #include "clang/AST/ASTContext.h"

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Index/IndexingOptions.h"
 #include "clang/Index/USRGeneration.h"
+#include "clang/Lex/Lexer.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
+#include <cstddef>
 #include <optional>
+#include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 // Returns the single definition of the entity declared by D, if visible.
 // In particular:
stringifyContainerForMainFileRef(const Decl *Container) {
   // FIXME We might also want to display the signature here
   // When doing so, remember to also add the Signature to index results!
   if (auto *ND = llvm::dyn_cast_if_present<NamedDecl>(Container))
     return printQualifiedName(*ND);
   return {};
 }
 } // namespace
 
 ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
                                 const SymbolIndex *Index, bool AddContext) {
   ReferencesResult Results;
   const SourceManager &SM = AST.getSourceManager();
   auto MainFilePath = AST.tuPath();
   auto URIMainFile = URIForFile::canonicalize(MainFilePath, MainFilePath);
   auto CurLoc = sourceLocationInMainFile(SM, Pos);
   if (!CurLoc) {
     llvm::consumeError(CurLoc.takeError());
     return {};
   }
 
+  const auto &Includes = AST.getIncludeStructure().MainFileIncludes;
+  const auto &ConvertedMainFileIncludes =
+      convertIncludes(SM, AST.getIncludeStructure().MainFileIncludes);
+  for (auto &Inc : Includes) {
+    if (Inc.HashLine != Pos.line)
+      continue;
+
+    const auto &ReferencedInclude = convertIncludes(SM, Inc);
+    include_cleaner::walkUsed(
+        AST.getLocalTopLevelDecls(), collectMacroReferences(AST),
+        AST.getPragmaIncludes(), SM,
+        [&](const include_cleaner::SymbolReference &Ref,
+            llvm::ArrayRef<include_cleaner::Header> Providers) {
+          if (Ref.RT != include_cleaner::RefType::Explicit)
+            return;
+
+          // TODO(bakalova) spelling or expansion loc?
+          const auto &Loc = SM.getFileLoc(Ref.RefLocation);
+          for (const auto &H : Providers) {
+            // Find the highest-rank #include'd provider
+            const auto &MatchingIncludes = ConvertedMainFileIncludes.match(H);
+            if (MatchingIncludes.empty())
+              continue;
+
+            // Match the highest-rank #include'd provider against the referenced
+            // #include.
+            if (!ReferencedInclude.match(H).empty()) {
+              ReferencesResult::Reference Result;
+              auto TokLen =
+                  Lexer::MeasureTokenLength(Loc, SM, AST.getLangOpts());
+              Result.Loc.range =
+                  halfOpenToRange(SM, CharSourceRange::getCharRange(
+                                          Loc, Loc.getLocWithOffset(TokLen)));
+              Result.Loc.uri = URIMainFile;
+              Results.References.push_back(std::move(Result));
+            }
+            return;
+          }
+        });
+    if (!Results.References.empty()) {
+      // Add the #include line to the references list
+      size_t IncludeLen =
+          std::string{"#include"}.length() + Inc.Written.length() + 1;
+      ReferencesResult::Reference Result;
+      Result.Loc.range = clangd::Range{Position{Inc.HashLine, 0},
+                                       Position{Inc.HashLine, (int)IncludeLen}};
+      Result.Loc.uri = URIMainFile;
+      Results.References.push_back(std::move(Result));
+    }
+  }
+
   llvm::DenseSet<SymbolID> IDsToQuery, OverriddenMethods;
 
   const auto *IdentifierAtCursor =
       syntax::spelledIdentifierTouching(*CurLoc, AST.getTokens());
   std::optional<DefinedMacro> Macro;
   if (IdentifierAtCursor)
     Macro = locateMacroAt(*IdentifierAtCursor, AST.getPreprocessor());
   if (Macro) {
struct Visitor : ConstStmtVisitor<Visitor, QualType> {
       }
     } V;
     return V.Visit(S);
   }
 
   return QualType();
 }
 
-// Given a type targeted by the cursor, return one or more types that are more interesting
-// to target.
-static void unwrapFindType(
-    QualType T, const HeuristicResolver* H, llvm::SmallVector<QualType>& Out) {
+// Given a type targeted by the cursor, return one or more types that are more
+// interesting to target.
+static void unwrapFindType(QualType T, const HeuristicResolver *H,
+                           llvm::SmallVector<QualType> &Out) {
   if (T.isNull())
     return;
 
   // If there's a specific type alias, point at that rather than unwrapping.
-  if (const auto* TDT = T->getAs<TypedefType>())
+  if (const auto *TDT = T->getAs<TypedefType>())
     return Out.push_back(QualType(TDT, 0));
 
   // Pointers etc => pointee type.
   if (const auto *PT = T->getAs<PointerType>())
     return unwrapFindType(PT->getPointeeType(), H, Out);
   if (const auto *RT = T->getAs<ReferenceType>())
     return unwrapFindType(RT->getPointeeType(), H, Out);
   if (const auto *AT = T->getAsArrayTypeUnsafe())
     return unwrapFindType(AT->getElementType(), H, Out);
 
   // Function type => return type.
   if (auto *FT = T->getAs<FunctionType>())
     return unwrapFindType(FT->getReturnType(), H, Out);
   if (auto *CRD = T->getAsCXXRecordDecl()) {
     if (CRD->isLambda())
-      return unwrapFindType(CRD->getLambdaCallOperator()->getReturnType(), H, Out);
+      return unwrapFindType(CRD->getLambdaCallOperator()->getReturnType(), H,
+                            Out);
     // FIXME: more cases we'd prefer the return type of the call operator?
     //        std::function etc?
   }
 
   // For smart pointer types, add the underlying type
   if (H)
-    if (const auto* PointeeType = H->getPointeeType(T.getNonReferenceType().getTypePtr())) {
-        unwrapFindType(QualType(PointeeType, 0), H, Out);
-        return Out.push_back(T);
+    if (const auto *PointeeType =
+            H->getPointeeType(T.getNonReferenceType().getTypePtr())) {
     }
 
   return Out.push_back(T);
 }
 
 // Convenience overload, to allow calling this without the out-parameter
-static llvm::SmallVector<QualType> unwrapFindType(
-    QualType T, const HeuristicResolver* H) {
-    llvm::SmallVector<QualType> Result;
-    unwrapFindType(T, H, Result);
-    return Result;
+static llvm::SmallVector<QualType> unwrapFindType(QualType T,
+                                                  const HeuristicResolver *H) {
 }
 
-
 std::vector<LocatedSymbol> findType(ParsedAST &AST, Position Pos) {
   const SourceManager &SM = AST.getSourceManager();
   auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);
   std::vector<LocatedSymbol> Result;
   if (!Offset) {
     elog("failed to convert position {0} for findTypes: {1}", Pos,
          Offset.takeError());
     return Result;
   }
   // The general scheme is: position -> AST node -> type -> declaration.
   auto SymbolsFromNode =
       [&AST](const SelectionTree::Node *N) -> std::vector<LocatedSymbol> {
     std::vector<LocatedSymbol> LocatedSymbols;
 
     // NOTE: unwrapFindType might return duplicates for something like
-    // unique_ptr<unique_ptr<T>>. Let's *not* remove them, because it gives you some
-    // information about the type you may have not known before
-    // (since unique_ptr<unique_ptr<T>> != unique_ptr<T>).
-    for (const QualType& Type : unwrapFindType(typeForNode(N), AST.getHeuristicResolver()))
-        llvm::copy(locateSymbolForType(AST, Type), std::back_inserter(LocatedSymbols));
+    // unique_ptr<unique_ptr<T>>. Let's *not* remove them, because it gives you
+    // some information about the type you may have not known before (since
+    // unique_ptr<unique_ptr<T>> != unique_ptr<T>).
+    for (const QualType &Type :
+         unwrapFindType(typeForNode(N), AST.getHeuristicResolver()))
+      llvm::copy(locateSymbolForType(AST, Type),
+                 std::back_inserter(LocatedSymbols));
 
     return LocatedSymbols;
   };
   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,
                             *Offset, [&](SelectionTree ST) {
                               Result = SymbolsFromNode(ST.commonAncestor());
                               return !Result.empty();
                             });

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

 //===-- XRefsTests.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 "AST.h"
+#include "Annotations.h"
 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "SourceCode.h"
 #include "SyncAPI.h"
 #include "TestFS.h"
 #include "TestTU.h"
 #include "XRefs.h"
 #include "index/MemIndex.h"

 using ::testing::Eq;
 using ::testing::IsEmpty;
 using ::testing::Matcher;
 using ::testing::Not;
 using ::testing::UnorderedElementsAre;
 using ::testing::UnorderedElementsAreArray;
 using ::testing::UnorderedPointwise;
 
+std::string guard(llvm::StringRef Code) {
+  return "#pragma once\n" + Code.str();
+}
+
 MATCHER_P2(FileRange, File, Range, "") {
   return Location{URIForFile::canonicalize(File, testRoot()), Range} == arg;
 }
 MATCHER(declRange, "") {
   const LocatedSymbol &Sym = ::testing::get<0>(arg);
   const Range &Range = ::testing::get<1>(arg);
   return Sym.PreferredDeclaration.range == Range;
 }
for (const llvm::StringRef Case : {
        }) {
     Annotations A(Case);
     TU.Code = A.code().str();
     ParsedAST AST = TU.build();
 
     ASSERT_GT(A.points().size(), 0u) << Case;
     for (auto Pos : A.points())
       EXPECT_THAT(findType(AST, Pos),
-                  ElementsAre(
-                    sym("Target", HeaderA.range("Target"), HeaderA.range("Target"))))
+                  ElementsAre(sym("Target", HeaderA.range("Target"),
+                                  HeaderA.range("Target"))))
           << Case;
   }
 
   for (const llvm::StringRef Case : {
            "smart_ptr<Target> ^tsmart;",
        }) {
     Annotations A(Case);
     TU.Code = A.code().str();
     ParsedAST AST = TU.build();
 
-    EXPECT_THAT(findType(AST, A.point()),
-                UnorderedElementsAre(
-                  sym("Target", HeaderA.range("Target"), HeaderA.range("Target")),
-                  sym("smart_ptr", HeaderA.range("smart_ptr"), HeaderA.range("smart_ptr"))
-                ))
+    EXPECT_THAT(
+        findType(AST, A.point()),
+            sym("smart_ptr", HeaderA.range("smart_ptr"),
+                HeaderA.range("smart_ptr"))))
         << Case;
   }
 }
 
 void checkFindRefs(llvm::StringRef Test, bool UseIndex = false) {
   Annotations T(Test);
   auto TU = TestTU::withCode(T.code());
   TU.ExtraArgs.push_back("-std=c++20");
+  TU.AdditionalFiles["bar.h"] = guard(R"cpp(
+    #define BAR 5
+    int bar1();
+    int bar2();
+    class Bar {};            
+  )cpp");
+  TU.AdditionalFiles["private.h"] = guard(R"cpp(
+    // IWYU pragma: private, include "public.h"
+    int foo(); 
+  )cpp");
+  TU.AdditionalFiles["public.h"] = guard("");
+  TU.AdditionalFiles["system/vector"] = guard(R"cpp(
+    namespace std {
+      template<typename>
+      class vector{};
+    }
+  )cpp");
+  TU.AdditionalFiles["forward.h"] = guard("class Bar;");
+  TU.ExtraArgs.push_back("-isystem" + testPath("system"));
 
   auto AST = TU.build();
   std::vector<Matcher<ReferencesResult::Reference>> ExpectedLocations;
   for (const auto &[R, Context] : T.rangesWithPayload())
     ExpectedLocations.push_back(
         AllOf(rangeIs(R), containerIs(Context), attrsAre(0u)));
   // $def is actually shorthand for both definition and declaration.
   // If we have cases that are definition-only, we should change this.
const char *Tests[] = {
         if ($(test)[[a^]]) {} // ignore implicit conversion-operator AST node
       }
     )cpp",
   };
   for (const char *Test : Tests)
     checkFindRefs(Test);
 }
 
+TEST(FindReferences, UsedSymbolsFromInclude) {
+  const char *Tests[] = {
+      R"cpp([[#include ^"bar.h"]]
+        int fstBar = [[bar1]]();
+        int sndBar = [[bar2]]();
+        [[Bar]] bar;
+        int macroBar = [[BAR]];
+      )cpp",
+
+      R"cpp([[#in^clude <vector>]]
+        std::[[vector]]<int> vec;
+      )cpp",
+
+      R"cpp([[#in^clude "public.h"]]
+        #include "private.h"
+        int fooVar = [[foo]]();
+      )cpp",
+
+      R"cpp(#include "bar.h"
+        #include "for^ward.h"
+        Bar *x;
+      )cpp",
+
+      R"cpp([[#include "b^ar.h"]]
+        #define DEF(X) const Bar *X
+        [[DEF]](a);
+      )cpp",
+
+      R"cpp([[#in^clude "bar.h"]]
+        #define BAZ(X) const X x
+        BAZ([[Bar]]);
+      )cpp"};
+  for (const char *Test : Tests)
+    checkFindRefs(Test);
+}
+
 TEST(FindReferences, NeedsIndexForSymbols) {
   const char *Header = "int foo();";
   Annotations Main("int main() { [[f^oo]](); }");
   TestTU TU;
   TU.Code = std::string(Main.code());
   TU.HeaderCode = Header;
   auto AST = TU.build();