[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

22

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

62

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?

79

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

22

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.

62

Fair suggestion, done in r372617.

79

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

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

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

no need for raw string literals?

158

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

160

maybe also set TU.FileName to TestFilePath ?

196

again no need for raw literals

217

same as above

219

again set TU.FileName ?

[hokein]

address review comments.

[hokein]

format the testcases.

clang-tools-extra/clangd/HeaderSourceSwitch.cpp

86

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

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

nit: for(auto &It : Candidates)

117

nit: else if

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

196

not done

[hokein]

address review comments.

clang-tools-extra/clangd/HeaderSourceSwitch.cpp

113

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/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   FileDistance.cpp
   Format.cpp
   FS.cpp
   FSProvider.cpp
   FormattedString.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   Headers.cpp
+  HeaderSourceSwitch.cpp
   IncludeFixer.cpp
   JSONTransport.cpp
   Logger.cpp
   Protocol.cpp
   Quality.cpp
   ParsedAST.cpp
   Preamble.cpp
   RIFF.cpp

clang-tools-extra/clangd/ClangdServer.cpp

if (!InpAST)
       return CB(InpAST.takeError());
     CB(clangd::locateSymbolAt(InpAST->AST, Pos, Index));
   };
 
   WorkScheduler.runWithAST("Definitions", File, std::move(Action));
 }
 
 llvm::Optional<Path> ClangdServer::switchSourceHeader(PathRef Path) {
-
+  // FIXME: move the file heuristic to HeaderSourceSwitch.h.
   llvm::StringRef SourceExtensions[] = {".cpp", ".c", ".cc", ".cxx",
                                         ".c++", ".m", ".mm"};
   llvm::StringRef HeaderExtensions[] = {".h", ".hh", ".hpp", ".hxx", ".inc"};
 
   llvm::StringRef PathExt = llvm::sys::path::extension(Path);
 
   // Lookup in a list of known extensions.
   auto SourceIter =

clang-tools-extra/clangd/HeaderSourceSwitch.h

+//===--- HeaderSourceSwitch.h - ----------------------------------*- 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 "ParsedAST.h"
+#include "llvm/ADT/Optional.h"
+
+namespace clang {
+namespace clangd {
+
+/// Given a header file, returns a best matching source file, and vice visa.
+/// The heuristics incorporate with the AST and the index.
+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

clang-tools-extra/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 "Logger.h"
+#include "index/SymbolCollector.h"
+#include "AST.h"
+#include "clang/AST/Decl.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+// Traverses the ParsedAST directly to collect all decls present in the main
+// file.
+class CollectIndexableLocalDecls {
+public:
+  CollectIndexableLocalDecls(ParsedAST &AST) : AST(AST) {}
+
+  std::vector<const Decl*> collect() {
+    std::vector<const Decl*> Results;
+    for (auto &TopLevel : AST.getLocalTopLevelDecls())
+      traverseDecl(TopLevel, Results);
+    return Results;
+  }
+
+private:
+  void traverseDecl(Decl *D, std::vector<const Decl *> &Results) {
+    auto *ND = llvm::dyn_cast<NamedDecl>(D);
+    if (!ND || ND->isImplicit())
+      return;
+    if (!SymbolCollector::shouldCollectSymbol(*ND, D->getASTContext(), {},
+                                              /*IsMainFileSymbol=*/false))
+      return;
+    if (!shouldSkipChildren(ND)) {
+      if (auto *Scope = llvm::dyn_cast<DeclContext>(ND)) {
+        for (auto *D : Scope->decls())
+          traverseDecl(D, Results);
+      }
+    }
+    if (llvm::isa<NamespaceDecl>(D))
+      return; // namespace is indexable, but we're not interested.
+    Results.push_back(D);
+  }
+  bool shouldSkipChildren(NamedDecl *D) {
+    // We're not interested in the function body.
+    if (llvm::isa<FunctionDecl>(D))
+      return true;
+    // For others e.g. namespace decl, class decl, we visit their children.
+    return false;
+  }
+
+  ParsedAST &AST;
+};
+
+llvm::Optional<std::string> resolveURI(const char *FileURI,
+                                       llvm::StringRef HintPath) {
+  auto Uri = URI::parse(FileURI);
+  if (!Uri) {
+    elog("Could no parse URI {0}: {1}", FileURI, Uri.takeError());
+    return None;
+  }
+  auto Path = URI::resolve(*Uri, HintPath);
+  if (!Path) {
+    elog("Could no resolve URI URI {0}: {1}", FileURI, Path.takeError());
+    return None;
+  }
+  return *Path;
+};
+
+} // namespace
+
+llvm::Optional<Path> getCorrespondingHeaderOrSource(const Path &OriginalFile,
+                                                    ParsedAST &AST,
+                                                    const SymbolIndex *Index) {
+  if (!Index) {
+    elog("no index provided, no result returned");
+    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 = resolveURI(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);
+  });
+  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;
+  }
+  return Path(Best->first());
+}
+
+std::vector<const Decl *> getIndexableLocalDecls(ParsedAST &AST) {
+  return CollectIndexableLocalDecls(AST).collect();
+}
+
+} // namespace clangd
+} // namespace clang

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

add_unittest(ClangdUnitTests ClangdTests
   FindTargetTests.cpp
   FormattedStringTests.cpp
   FormatTests.cpp
   FSTests.cpp
   FunctionTests.cpp
   FuzzyMatchTests.cpp
   GlobalCompilationDatabaseTests.cpp
   HeadersTests.cpp
+  HeaderSourceSwitchTests.cpp
   IndexActionTests.cpp
   IndexTests.cpp
   JSONTransportTests.cpp
   ParsedASTTests.cpp
   PrintASTTests.cpp
   QualityTests.cpp
   RenameTests.cpp
   RIFFTests.cpp

clang-tools-extra/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 {
+
+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[] = {
+    {R"cpp(// empty, no header found)cpp", 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")}
+  };
+  const std::string& TestFilePath = testPath("TestTU.h");
+  for (const auto &Case : TestCases) {
+    TestTU TU = TestTU::withCode(Case.HeaderCode);
+    TU.ExtraArgs.push_back("-xc++-header"); // inform clang this is a header.
+    auto HeaderAST = TU.build();
+    EXPECT_EQ(Case.ExpectedSource,
+              getCorrespondingHeaderOrSource(TestFilePath, 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[] = {
+      {R"cpp(// empty, no header found)cpp", 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")},
+  };
+  const std::string& TestFilePath = testPath("TestTU.cpp");
+  for (const auto &Case : TestCases) {
+    TestTU TU = TestTU::withCode(Case.SourceCode);
+    auto AST = TU.build();
+    EXPECT_EQ(Case.ExpectedResult,
+              getCorrespondingHeaderOrSource(TestFilePath, AST, Index.get()));
+  }
+}
+
+
+} // namespace
+} // namespace clangd
+} // namespace clang