[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

1391

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);

1400

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.

1400

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

1401

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.

1411

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

1434

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

2012

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

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

1908

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

2302

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

2309

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

1401

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

return std::nullopt

clang-tools-extra/clangd/IncludeCleaner.h

87

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

clang-tools-extra/clangd/XRefs.cpp

1320

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.

1324

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

1325

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;
...

1401

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

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

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

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/Hover.cpp

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 ||
             UsedSymbols.find(Ref.Target) != UsedSymbols.end())
           return;
 
-        for (const include_cleaner::Header &H : Providers) {
-          auto MatchingIncludes = ConvertedMainFileIncludes.match(H);
-          // No match for this provider in the main file.
-          if (MatchingIncludes.empty())
-            continue;
+        auto Provider =
+            firstMatchedProvider(ConvertedMainFileIncludes, Providers);
+        if (!Provider || HoveredInclude.match(*Provider).empty())
+          return;
 
-          // Check if the hovered include matches this provider.
-          if (!HoveredInclude.match(H).empty())
-            UsedSymbols.insert(Ref.Target);
-
-          // Don't look for rest of the providers once we've found a match
-          // in the main file.
-          break;
-        }
       });
 
   for (const auto &UsedSymbolDecl : UsedSymbols)
     HI.UsedSymbolNames.push_back(getSymbolName(UsedSymbolDecl));
   llvm::sort(HI.UsedSymbolNames);
 }
 
 } // namespace

clang-tools-extra/clangd/IncludeCleaner.h

 
 /// Determines the header spelling of an include-cleaner header
 /// representation. The spelling contains the ""<> characters.
 std::string spellHeader(ParsedAST &AST, const FileEntry *MainFile,
                         include_cleaner::Header Provider);
 
 std::vector<include_cleaner::SymbolReference>
 collectMacroReferences(ParsedAST &AST);
+
+/// Find the first provider in the list that is matched by the includes.
+std::optional<include_cleaner::Header>
+firstMatchedProvider(const include_cleaner::Includes &Includes,
+                     llvm::ArrayRef<include_cleaner::Header> Providers);
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDECLEANER_H

clang-tools-extra/clangd/IncludeCleaner.cpp

std::vector<Diag> issueIncludeCleanerDiagnostics(ParsedAST &AST,
   std::vector<Diag> Result = generateUnusedIncludeDiagnostics(
       AST.tuPath(), Findings.UnusedIncludes, Code);
   llvm::move(
       generateMissingIncludeDiagnostics(AST, Findings.MissingIncludes, Code),
       std::back_inserter(Result));
   return Result;
 }
 
+std::optional<include_cleaner::Header>
+firstMatchedProvider(const include_cleaner::Includes &Includes,
+                       llvm::ArrayRef<include_cleaner::Header> Providers) {
+  for (const auto &H : Providers) {
+    if (!Includes.match(H).empty())
+      return H;
+  }
+  // No match for this provider in the includes list.
+  return {};
+}
 } // namespace clangd
 } // namespace clang

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 <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 maybeFindIncludeReferences(ParsedAST &AST, Position Pos,
+                                            URIForFile URIMainFile) {
+  ReferencesResult Results;
+  const SourceManager &SM = AST.getSourceManager();
+  auto Includes = AST.getIncludeStructure().MainFileIncludes;
+  auto ConvertedMainFileIncludes = convertIncludes(SM, Includes);
+  for (auto &Inc : Includes) {
+    if (Inc.HashLine != Pos.line)
+      continue;
+
+    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;
+
+          auto Provider =
+              firstMatchedProvider(ConvertedMainFileIncludes, Providers);
+          if (!Provider || ReferencedInclude.match(*Provider).empty())
+            return;
+
+          auto Loc = SM.getFileLoc(Ref.RefLocation);
+          // File locations can be outside of the main file if macro is
+          // expanded through an #include.
+          while (SM.getFileID(Loc) != SM.getMainFileID())
+            Loc = SM.getIncludeLoc(SM.getFileID(Loc));
+
+          ReferencesResult::Reference Result;
+          const auto *Token = AST.getTokens().spelledTokenAt(Loc);
+          Result.Loc.range =
+              Range{sourceLocToPosition(SM, Token->location()),
+                    sourceLocToPosition(SM, Token->endLocation())};
+          Result.Loc.uri = URIMainFile;
+          Results.References.push_back(std::move(Result));
+        });
+    if (Results.References.empty())
+      return {};
+
+    // Add the #include line to the references list.
+    auto 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));
+  }
+  return Results;
+}
+
 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 {};
   }
 
+  Results = maybeFindIncludeReferences(AST, Pos, URIMainFile);
+  if (!Results.References.empty())
+    return Results;
+
   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) {
     // Handle references to macro.
     if (auto MacroSID = getSymbolID(Macro->Name, Macro->Info, SM)) {
       // Collect macro references from main file.
       const auto &IDToRefs = AST.getMacros().MacroRefs;
       auto Refs = IDToRefs.find(MacroSID);
       if (Refs != IDToRefs.end()) {
         for (const auto &Ref : Refs->second) {
           ReferencesResult::Reference Result;
           Result.Loc.range = Ref.Rng;
           Result.Loc.uri = URIMainFile;
           if (Ref.IsDefinition) {
             Result.Attributes |= ReferencesResult::Declaration;
             Result.Attributes |= ReferencesResult::Definition;
           }
           Results.References.push_back(std::move(Result));
         }
       }
       IDsToQuery.insert(MacroSID);
     }
   } else {
     // Handle references to Decls.
 
     DeclRelationSet Relations =
         DeclRelation::TemplatePattern | DeclRelation::Alias;
     std::vector<const NamedDecl *> Decls =
         getDeclAtPosition(AST, *CurLoc, Relations);
     llvm::SmallVector<const NamedDecl *> TargetsInMainFile;
     for (const NamedDecl *D : Decls) {
       auto ID = getSymbolID(D);
       if (!ID)
         continue;
       TargetsInMainFile.push_back(D);
       // Not all symbols can be referenced from outside (e.g. function-locals).
       // TODO: we could skip TU-scoped symbols here (e.g. static functions) if
       // we know this file isn't a header. The details might be tricky.
       if (D->getParentFunctionOrMethod())
         continue;
       IDsToQuery.insert(ID);
     }
 
     RelationsRequest OverriddenBy;
     if (Index) {
       OverriddenBy.Predicate = RelationKind::OverriddenBy;
       for (const NamedDecl *ND : Decls) {
         // Special case: For virtual methods, report decl/def of overrides and
         // references to all overridden methods in complete type hierarchy.
static QualType typeForNode(const SelectionTree::Node *N) {
   }
 
   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) {
   if (T.isNull())
     return;
 
   // If there's a specific type alias, point at that rather than unwrapping.
   if (const auto* TDT = T->getAs<TypedefType>())
     return Out.push_back(QualType(TDT, 0));
 
   // Pointers etc => pointee type.

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

 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;
 }
EXPECT_THAT(findType(AST, A.point()),
         << 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");
 
   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.
   for (const auto &[R, Context] : T.rangesWithPayload("def"))
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"]]
+        #include <vector>
+        int fstBar = [[bar1]]();
+        int sndBar = [[bar2]]();
+        [[Bar]] bar;
+        int macroBar = [[BAR]];
+        std::vector<int> vec;
+      )cpp",
+
+      R"cpp([[#in^clude <vector>]]
+        std::[[vector]]<int> vec;
+      )cpp"};
+  for (const char *Test : Tests) {
+    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["system/vector"] = guard(R"cpp(
+      namespace std {
+        template<typename>
+        class vector{};
+      }
+    )cpp");
+    TU.ExtraArgs.push_back("-isystem" + testPath("system"));
+
+    auto AST = TU.build();
+    std::vector<Matcher<ReferencesResult::Reference>> ExpectedLocations;
+    for (const auto &R : T.ranges())
+      ExpectedLocations.push_back(AllOf(rangeIs(R), attrsAre(0u)));
+    for (const auto &P : T.points()) 
+      EXPECT_THAT(findReferences(AST, P, 0).References,
+                  UnorderedElementsAreArray(ExpectedLocations))
+          << "Failed for Refs at " << P << "\n"
+          << 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();