[clangd] Implement a smart version of HeaderSource switch.

[hokein]

Summary

This patch implements another version header-source switch by incorporating the
AST and index, it will be used:

• to improve the current header-source switch feature (layer with the existing file heuristic);
• by the incoming define-outline code action;

[hokein]

Cleanup.

[kadircet]

clang-tools-extra/clangd/HeaderSourceSwitch.cpp

21 ↗

(On Diff #221288)

this class doesn't seem to have any state(apart from saving AST in constructor and using it in call to collect), why not just have a vector<Decl> collectDecls(ParsedAST& AST); ?

61 ↗

(On Diff #221288)

It seems like we have a bunch of different implementations for this function in background.cpp, codecomplete.cpp, ... Basically any place calling URI::resolve, do you mind adding an overload for URI::resolve that'll take a const char* instead of a URI?

78 ↗

(On Diff #221288)

As discussed in the design for define out-of-line, this function's dependency on AST and Index should rather be optional.

• if we have AST, then we can boost the files containing the canonical declarations for symbols defined in the main file.
• if we have just the Index, currently there's nothing much we can do, but we can put a fixme to add a new endpoint to symbol index for "fetching symbols in a given file", then we can use symbol information for declaration/definition files without an AST.
• if we have AST+Index, we can boost the files containing the definition for symbols declared in the main file and vice-versa(what you already do in this patch).
• If we don't have anything we'll just make use of the filename, by changing the extension, as current ClangdServer::switchSourceHeader implementation does.

[hokein]

Address comments.

[hokein]

clang-tools-extra/clangd/HeaderSourceSwitch.cpp

21 ↗

(On Diff #221288)

yeah, but we need to do recursive calls, which I thought making a class is more readable. Change to a single function with recursive lambda, I hope it won't hurt the code readability.

61 ↗

(On Diff #221288)

Fair suggestion, done in r372617.

78 ↗

(On Diff #221288)

as discussed offline, we will

• make the filename heuristic into a separate API which provides more flexible;
• make this API support 3 cases (except the case where we only have index, as it'd require large effort to implement "fetching symbols in a given file" in the index, we're less certain it is worth); when we only have AST (or the index doesn't contain any interesting information), we just use the information for the AST to do the ".cc=>.h" inference.

[hokein]

rebase

[kadircet]

mostly LG, a few small comments

clang-tools-extra/clangd/HeaderSourceSwitch.cpp

86 ↗

(On Diff #221724)

should we have a cache for these uri resolutions?
We will most likely have a few URIs that are being resolved over and over again.

114 ↗

(On Diff #221724)

what if there are ties ?

we don't need to do anything clever yet, but we should at least be deterministic. Currently it depends on stringmap ordering.
Could you pick the candidate that comes first in the lexical order in such cases?
and add some test cases?

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

141 ↗

(On Diff #221724)

no need for raw string literals?

158 ↗

(On Diff #221724)

maybe just const std::string ? testpath is returning a value, not a ref.

160 ↗

(On Diff #221724)

maybe also set TU.FileName to TestFilePath ?

196 ↗

(On Diff #221724)

again no need for raw literals

217 ↗

(On Diff #221724)

same as above

219 ↗

(On Diff #221724)

again set TU.FileName ?

[hokein]

address review comments.

[hokein]

format the testcases.

clang-tools-extra/clangd/HeaderSourceSwitch.cpp

86 ↗

(On Diff #221724)

We will most likely have a few URIs that are being resolved over and over again.

This is true, but having a cache seems to be a premature optimization at the moment. I think the number for the Decl in the main file is relatively small in practice. We could add it when it turns out a performance problem.

114 ↗

(On Diff #221724)

good point, I thought the StringMap is sorted by the key value, but it uses hash value.

[kadircet]

thanks for formatting test cases, I had it in mind but forgot to mention in last round.

LGTM

clang-tools-extra/clangd/HeaderSourceSwitch.cpp

113 ↗

(On Diff #222112)

nit: for(auto &It : Candidates)

117 ↗

(On Diff #222112)

nit: else if

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

196 ↗

(On Diff #221724)

not done

[hokein]

address review comments.

clang-tools-extra/clangd/HeaderSourceSwitch.cpp

113 ↗

(On Diff #222112)

for-range doesn't work here, the type is StringMapEntry which is a non-copy structure, we need to copy an iterator for recording the Best.

clang-tools-extra/trunk/clangd/HeaderSourceSwitch.h

 namespace clangd {
 
 /// Given a header file, returns the best matching source file, and vice visa.
 /// It only uses the filename heuristics to do the inference.
 llvm::Optional<Path> getCorrespondingHeaderOrSource(
     const Path &OriginalFile,
     llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS);
 
+/// Given a header file, returns the best matching source file, and vice visa.
+/// The heuristics incorporate with the AST and the index (if provided).
+llvm::Optional<Path> getCorrespondingHeaderOrSource(const Path &OriginalFile,
+                                                    ParsedAST &AST,
+                                                    const SymbolIndex *Index);
+
+/// Returns all indexable decls that are present in the main file of the AST.
+/// Exposed for unittests.
+std::vector<const Decl *> getIndexableLocalDecls(ParsedAST &AST);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_HEADERSOURCESWITCH_H

clang-tools-extra/trunk/clangd/HeaderSourceSwitch.cpp

 //===--- HeaderSourceSwitch.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 "HeaderSourceSwitch.h"
+#include "AST.h"
+#include "Logger.h"
+#include "index/SymbolCollector.h"
+#include "clang/AST/Decl.h"
 
 namespace clang {
 namespace clangd {
 
 llvm::Optional<Path> getCorrespondingHeaderOrSource(
     const Path &OriginalFile,
     llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS) {
   llvm::StringRef SourceExtensions[] = {".cpp", ".c", ".cc", ".cxx",
for (llvm::StringRef NewExt : NewExts) {
     // Also check NewExt in upper-case, just in case.
     llvm::sys::path::replace_extension(NewPath, NewExt.upper());
     if (VFS->exists(NewPath))
       return NewPath.str().str();
   }
   return None;
 }
 
+llvm::Optional<Path> getCorrespondingHeaderOrSource(const Path &OriginalFile,
+                                                    ParsedAST &AST,
+                                                    const SymbolIndex *Index) {
+  if (!Index) {
+    // FIXME: use the AST to do the inference.
+    return None;
+  }
+  LookupRequest Request;
+  // Find all symbols present in the original file.
+  for (const auto *D : getIndexableLocalDecls(AST)) {
+    if (auto ID = getSymbolID(D))
+      Request.IDs.insert(*ID);
+  }
+  llvm::StringMap<int> Candidates; // Target path => score.
+  auto AwardTarget = [&](const char *TargetURI) {
+    if (auto TargetPath = URI::resolve(TargetURI, OriginalFile)) {
+      if (*TargetPath != OriginalFile) // exclude the original file.
+        ++Candidates[*TargetPath];
+    };
+  };
+  // If we switch from a header, we are looking for the implementation
+  // file, so we use the definition loc; otherwise we look for the header file,
+  // we use the decl loc;
+  //
+  // For each symbol in the original file, we get its target location (decl or
+  // def) from the index, then award that target file.
+  bool IsHeader = AST.getASTContext().getLangOpts().IsHeaderFile;
+  Index->lookup(Request, [&](const Symbol &Sym) {
+    if (IsHeader)
+      AwardTarget(Sym.Definition.FileURI);
+    else
+      AwardTarget(Sym.CanonicalDeclaration.FileURI);
+  });
+  // FIXME: our index doesn't have any interesting information (this could be
+  // that the background-index is not finished), we should use the decl/def
+  // locations from the AST to do the inference (from .cc to .h).
+  if (Candidates.empty())
+    return None;
+
+  // Pickup the winner, who contains most of symbols.
+  // FIXME: should we use other signals (file proximity) to help score?
+  auto Best = Candidates.begin();
+  for (auto It = Candidates.begin(); It != Candidates.end(); ++It) {
+    if (It->second > Best->second)
+      Best = It;
+    else if (It->second == Best->second && It->first() < Best->first())
+      // Select the first one in the lexical order if we have multiple
+      // candidates.
+      Best = It;
+  }
+  return Path(Best->first());
+}
+
+std::vector<const Decl *> getIndexableLocalDecls(ParsedAST &AST) {
+  std::vector<const Decl *> Results;
+  std::function<void(Decl *)> TraverseDecl = [&](Decl *D) {
+    auto *ND = llvm::dyn_cast<NamedDecl>(D);
+    if (!ND || ND->isImplicit())
+      return;
+    if (!SymbolCollector::shouldCollectSymbol(*ND, D->getASTContext(), {},
+                                              /*IsMainFileSymbol=*/false))
+      return;
+    if (!llvm::isa<FunctionDecl>(ND)) {
+      // Visit the children, but we skip function decls as we are not interested
+      // in the function body.
+      if (auto *Scope = llvm::dyn_cast<DeclContext>(ND)) {
+        for (auto *D : Scope->decls())
+          TraverseDecl(D);
+      }
+    }
+    if (llvm::isa<NamespaceDecl>(D))
+      return; // namespace is indexable, but we're not interested.
+    Results.push_back(D);
+  };
+  // Traverses the ParsedAST directly to collect all decls present in the main
+  // file.
+  for (auto *TopLevel : AST.getLocalTopLevelDecls())
+    TraverseDecl(TopLevel);
+  return Results;
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/unittests/HeaderSourceSwitchTests.cpp

 //===--- HeaderSourceSwitchTests.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 "HeaderSourceSwitch.h"
 
 #include "TestFS.h"
 #include "TestTU.h"
+#include "index/MemIndex.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 TEST(HeaderSourceSwitchTest, FileHeuristic) {
TEST(HeaderSourceSwitchTest, FileHeuristic) {
   ASSERT_EQ(PathResult.getValue(), Foo3HXX);
 
   // Test if asking for a corresponding file that doesn't exist returns an empty
   // string.
   PathResult = getCorrespondingHeaderOrSource(Invalid, FS.getFileSystem());
   EXPECT_FALSE(PathResult.hasValue());
 }
 
+MATCHER_P(DeclNamed, Name, "") {
+  if (const NamedDecl *ND = dyn_cast<NamedDecl>(arg))
+    if (ND->getQualifiedNameAsString() == Name)
+      return true;
+  return false;
+}
+
+TEST(HeaderSourceSwitchTest, GetLocalDecls) {
+  TestTU TU;
+  TU.HeaderCode = R"cpp(
+  void HeaderOnly();
+  )cpp";
+  TU.Code = R"cpp(
+  void MainF1();
+  class Foo {};
+  namespace ns {
+  class Foo {
+    void method();
+    int field;
+  };
+  } // namespace ns
+
+  // Non-indexable symbols
+  namespace {
+  void Ignore1() {}
+  }
+
+  )cpp";
+
+  auto AST = TU.build();
+  EXPECT_THAT(getIndexableLocalDecls(AST),
+              testing::UnorderedElementsAre(
+                  DeclNamed("MainF1"), DeclNamed("Foo"), DeclNamed("ns::Foo"),
+                  DeclNamed("ns::Foo::method"), DeclNamed("ns::Foo::field")));
+}
+
+TEST(HeaderSourceSwitchTest, FromHeaderToSource) {
+  // build a proper index, which contains symbols:
+  //   A_Sym1, declared in TestTU.h, defined in a.cpp
+  //   B_Sym[1-2], declared in TestTU.h, defined in b.cpp
+  SymbolSlab::Builder AllSymbols;
+  TestTU Testing;
+  Testing.HeaderFilename = "TestTU.h";
+  Testing.HeaderCode = "void A_Sym1();";
+  Testing.Filename = "a.cpp";
+  Testing.Code = "void A_Sym1() {};";
+  for (auto &Sym : Testing.headerSymbols())
+    AllSymbols.insert(Sym);
+
+  Testing.HeaderCode = R"cpp(
+  void B_Sym1();
+  void B_Sym2();
+  )cpp";
+  Testing.Filename = "b.cpp";
+  Testing.Code = R"cpp(
+  void B_Sym1() {}
+  void B_Sym2() {}
+  )cpp";
+  for (auto &Sym : Testing.headerSymbols())
+    AllSymbols.insert(Sym);
+  auto Index = MemIndex::build(std::move(AllSymbols).build(), {}, {});
+
+  // Test for swtich from .h header to .cc source
+  struct {
+    llvm::StringRef HeaderCode;
+    llvm::Optional<std::string> ExpectedSource;
+  } TestCases[] = {
+      {"// empty, no header found", llvm::None},
+      {R"cpp(
+         // no definition found in the index.
+         void NonDefinition();
+       )cpp",
+       llvm::None},
+      {R"cpp(
+         void A_Sym1();
+       )cpp",
+       testPath("a.cpp")},
+      {R"cpp(
+         // b.cpp wins.
+         void A_Sym1();
+         void B_Sym1();
+         void B_Sym2();
+       )cpp",
+       testPath("b.cpp")},
+      {R"cpp(
+         // a.cpp and b.cpp have same scope, but a.cpp because "a.cpp" < "b.cpp".
+         void A_Sym1();
+         void B_Sym1();
+       )cpp",
+       testPath("a.cpp")},
+  };
+  for (const auto &Case : TestCases) {
+    TestTU TU = TestTU::withCode(Case.HeaderCode);
+    TU.Filename = "TestTU.h";
+    TU.ExtraArgs.push_back("-xc++-header"); // inform clang this is a header.
+    auto HeaderAST = TU.build();
+    EXPECT_EQ(Case.ExpectedSource,
+              getCorrespondingHeaderOrSource(testPath(TU.Filename), HeaderAST,
+                                             Index.get()));
+  }
+}
+
+TEST(HeaderSourceSwitchTest, FromSourceToHeader) {
+  // build a proper index, which contains symbols:
+  //   A_Sym1, declared in a.h, defined in TestTU.cpp
+  //   B_Sym[1-2], declared in b.h, defined in TestTU.cpp
+  TestTU TUForIndex = TestTU::withCode(R"cpp(
+  #include "a.h"
+  #include "b.h"
+
+  void A_Sym1() {}
+
+  void B_Sym1() {}
+  void B_Sym2() {}
+  )cpp");
+  TUForIndex.AdditionalFiles["a.h"] = R"cpp(
+  void A_Sym1();
+  )cpp";
+  TUForIndex.AdditionalFiles["b.h"] = R"cpp(
+  void B_Sym1();
+  void B_Sym2();
+  )cpp";
+  TUForIndex.Filename = "TestTU.cpp";
+  auto Index = TUForIndex.index();
+
+  // Test for switching from .cc source file to .h header.
+  struct {
+    llvm::StringRef SourceCode;
+    llvm::Optional<std::string> ExpectedResult;
+  } TestCases[] = {
+      {"// empty, no header found", llvm::None},
+      {R"cpp(
+         // symbol not in index, no header found
+         void Local() {}
+       )cpp",
+       llvm::None},
+
+      {R"cpp(
+         // a.h wins.
+         void A_Sym1() {}
+       )cpp",
+       testPath("a.h")},
+
+      {R"cpp(
+         // b.h wins.
+         void A_Sym1() {}
+         void B_Sym1() {}
+         void B_Sym2() {}
+       )cpp",
+       testPath("b.h")},
+
+      {R"cpp(
+         // a.h and b.h have same scope, but a.h wins because "a.h" < "b.h".
+         void A_Sym1() {}
+         void B_Sym1() {}
+       )cpp",
+       testPath("a.h")},
+  };
+  for (const auto &Case : TestCases) {
+    TestTU TU = TestTU::withCode(Case.SourceCode);
+    TU.Filename = "Test.cpp";
+    auto AST = TU.build();
+    EXPECT_EQ(Case.ExpectedResult,
+              getCorrespondingHeaderOrSource(testPath(TU.Filename), AST,
+                                             Index.get()));
+  }
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang