[clangd] Fixes for #include insertion.

[ioeric]

Summary

o Avoid inserting a header include into the header itself.
o Avoid inserting non-header files.
o Canonicalize include paths for symbols in dynamic index.

[ilya-biryukov]

clangd/Headers.cpp

46

There is another list of header extensions in ClangdServer::switchSourceHeader, let's reuse the list of extensions used here and there.

49

Maybe use llvm::sys::path::extension and search it in HeaderExtensions using StringRef::equals_lower?
Will also handle upper- and mixed-case.

53

Maybe replace !hasHeaderExtension(Header) to hasSourceExtension(Header)?
Knowing about all header extensions in advance is hard, knowing a subset of source extensions seems totally true.

clangd/index/FileIndex.cpp

18

Maybe store a static inside the function body (to properly free memory) and return a const reference (to avoid mutating shared data)?

const CanonicalIncludes &CanonicalIncludesForSystemHeaders() {
  static CanonicalInclude Includes = []() -> CanonicalHeader {
    CanonicalInclude Includes;
    addSystemHeadersMapping(Includes);
    return Includes;
  };
  return Includes;
}

Also Sam mentioned that CanonicalIncludes is not thread-safe, as the Regex's match() mutates.

unittests/clangd/FileIndexTests.cpp

184

Why not on Windows?

[sammccall]

clangd/Headers.cpp

43–44

As discussed offline, this seems dubious.

• this is probably the generalization of '.inc' handling, and so probably wants the include stack and belongs at indexing time (we're determining "what's the public header for this symbol, or is the symbol private")?
  • as discussed offline, it seems like we can sidestep this whole problem by not indexing symbols only visible in main files, for now

(later we'll want a flag on the symbol for whether it's public, so we can support find-symbol-by-name for mainfile-declared symbols)

[ioeric]

• Stop indexing main files in dynamic index; addressed review comments.

clangd/Headers.cpp

46

Acked. (The change is not relevant anymore.)

clangd/index/FileIndex.cpp

18

As discussed offline, we want to avoid destructing static objects because ...

Made CanonicalIncludes thread-safe by adding a mutex around matches.

unittests/clangd/FileIndexTests.cpp

184

because our system header map doesn't really support windows...

[sammccall]

clangd/Headers.h

27–28

File also needs to be absolute.
(May want to add asserts for this at the start of the impl - up to you)

clangd/index/FileIndex.cpp

36

if this is always true now, we could remove the option?

37

This is not going to handle IWYU right?
It seems like at this point the right thing to do is totally hide the CanonicalIncludes inside SymbolCollector, which would init it (to system headers), write IWYU mappings using the PP, and consume the mappings (when emitting symbols).
Churn :(

[ilya-biryukov]

clangd/Headers.cpp

66

Not related to this patch, but just noticed that we don't call FS->setCurrentWorkingDirectory(CompileCommand.Directory) here.
This might break if CompileCommand has non-absolute paths.

clangd/index/CanonicalIncludes.cpp

21

Technically, if one thread initializes CanonicalIncludes and the other thread reads from it, this is a data race.
Maybe we're ok with our current usage, but I don't have enough confidence in that (i.e. don't know C++'s memory model good enough) and would advice to take the lock in other functions of CanonicalIncludes too.

clangd/index/FileIndex.cpp

18

NIT: lowerCase the function name.

38

NIT: remove local var, replace with CollectorOpts.Includes = CanonicalIncludesForSystemHeaders()?

unittests/clangd/FileIndexTests.cpp

184

Thanks for clarification.
I thought it's standard-library specific, not OS-specific. I would have expected it to work on Windows with libstdc++. (which we're "mocking" here).
Anyway, this not related to this patch.

[ilya-biryukov]

clangd/index/CanonicalIncludes.cpp

21

As Sam pointed out, it's fine the way it is right now. We don't want any thread-safety guarantees from the non-const methods of the class.
But could you please add a comment to the class that non-const methods of it are not thread-safe even though it has a mutex inside?

[ioeric]

clangd/Headers.cpp

66

This was done in ClangdServer, but we should probably do it here as you suggested.

clangd/index/FileIndex.cpp

36

Will do this in a followup patch. Added a FIXME

37

You are right :(

I'll prepare a followup patch to handle this. Added a FIXME.

[ioeric]

• addressed comments.

[ioeric]

• added a comment about thread safety

[ioeric]

• assert in the very beginning!

[ilya-biryukov]

LGTM

clangd/ClangdServer.cpp

ClangdServer::insertInclude(PathRef File, StringRef Code,
   } else {
     auto U = URI::parse(Header);
     if (!U)
       return U.takeError();
     auto Resolved = URI::resolve(*U, /*HintPath=*/File);
     if (!Resolved)
       return Resolved.takeError();
 
-    auto FS = FSProvider.getTaggedFileSystem(File).Value;
     tooling::CompileCommand CompileCommand =
         CompileArgs.getCompileCommand(File);
-    FS->setCurrentWorkingDirectory(CompileCommand.Directory);
-
     auto Include =
-        shortenIncludePath(File, Code, *Resolved, CompileCommand, FS);
+        calculateIncludePath(File, Code, *Resolved, CompileCommand,
+                             FSProvider.getTaggedFileSystem(File).Value);
     if (!Include)
       return Include.takeError();
     if (Include->empty())
       return tooling::Replacements();
     ToInclude = std::move(*Include);
   }
 
   auto Style = format::getStyle("file", File, "llvm");

clangd/Headers.h

 #include "Path.h"
 #include "clang/Basic/VirtualFileSystem.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 
 namespace clang {
 namespace clangd {
+
 /// Determines the preferred way to #include a file, taking into account the
 /// search path. Usually this will prefer a shorter representation like
 /// 'Foo/Bar.h' over a longer one like 'Baz/include/Foo/Bar.h'.
 ///
+/// \param File is an absolute file path.
 /// \param Header is an absolute file path.
-/// \return A quoted "path" or <path>. If \p Header is already (directly)
-/// included in the file (including those included via different paths), this
-/// returns an empty string.
+/// \return A quoted "path" or <path>. This returns an empty string if:
+///   - \p Header is already (directly) included in the file (including those
+///   included via different paths).
+///   - \p Header is the same as \p File.
 llvm::Expected<std::string>
-shortenIncludePath(PathRef File, llvm::StringRef Code, llvm::StringRef Header,
+calculateIncludePath(PathRef File, llvm::StringRef Code, llvm::StringRef Header,
                      const tooling::CompileCommand &CompileCommand,
                      IntrusiveRefCntPtr<vfs::FileSystem> FS);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_HEADERS_H

clangd/Headers.cpp

 #include "Compiler.h"
 #include "Logger.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/PreprocessorOptions.h"
 #include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 class RecordHeaders : public PPCallbacks {
 public:
   RecordHeaders(std::set<std::string> &Headers) : Headers(Headers) {}
 
   void InclusionDirective(SourceLocation /*HashLoc*/,
                           const Token & /*IncludeTok*/,
                           llvm::StringRef /*FileName*/, bool /*IsAngled*/,
                           CharSourceRange /*FilenameRange*/,
                           const FileEntry *File, llvm::StringRef /*SearchPath*/,
                           llvm::StringRef /*RelativePath*/,
                           const Module * /*Imported*/) override {
     if (File != nullptr && !File->tryGetRealPathName().empty())
       Headers.insert(File->tryGetRealPathName());
   }
 
 private:
   std::set<std::string> &Headers;
 };
 
 } // namespace
 
 /// FIXME(ioeric): we might not want to insert an absolute include path if the
 /// path is not shortened.
 llvm::Expected<std::string>
-shortenIncludePath(llvm::StringRef File, llvm::StringRef Code,
+calculateIncludePath(llvm::StringRef File, llvm::StringRef Code,
                      llvm::StringRef Header,
                      const tooling::CompileCommand &CompileCommand,
                      IntrusiveRefCntPtr<vfs::FileSystem> FS) {
+  assert(llvm::sys::path::is_absolute(File) &&
+         llvm::sys::path::is_absolute(Header));
+
+  if (File == Header)
+    return "";
+  FS->setCurrentWorkingDirectory(CompileCommand.Directory);
+
   // Set up a CompilerInstance and create a preprocessor to collect existing
   // #include headers in \p Code. Preprocesor also provides HeaderSearch with
   // which we can calculate the shortest include path for \p Header.
   std::vector<const char *> Argv;
   for (const auto &S : CompileCommand.CommandLine)
     Argv.push_back(S.c_str());
   IgnoringDiagConsumer IgnoreDiags;
   auto CI = clang::createInvocationFromCommandLine(
       Argv,
       CompilerInstance::createDiagnostics(new DiagnosticOptions(), &IgnoreDiags,
                                           false),
       FS);
   if (!CI)
     return llvm::make_error<llvm::StringError>(
         "Failed to create a compiler instance for " + File,

clangd/index/CanonicalIncludes.h

 //===---------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_CANONICALINCLUDES_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_CANONICALINCLUDES_H
 
 #include "clang/Lex/Preprocessor.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/Regex.h"
+#include <mutex>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 /// Maps a definition location onto an #include file, based on a set of filename
 /// rules.
+/// Only const methods (i.e. mapHeader) in this class are thread safe.
 class CanonicalIncludes {
 public:
   CanonicalIncludes() = default;
 
   /// Adds a string-to-string mapping from \p Path to \p CanonicalPath.
   void addMapping(llvm::StringRef Path, llvm::StringRef CanonicalPath);
 
   /// Maps all files matching \p RE to \p CanonicalPath
   void addRegexMapping(llvm::StringRef RE, llvm::StringRef CanonicalPath);
 
   /// \return \p Header itself if there is no mapping for it; otherwise, return
   /// a canonical header name.
   llvm::StringRef mapHeader(llvm::StringRef Header) const;
 
 private:
   // A map from header patterns to header names. This needs to be mutable so
   // that we can match again a Regex in a const function member.
   // FIXME(ioeric): All the regexes we have so far are suffix matches. The
   // performance could be improved by allowing only suffix matches instead of
   // arbitrary regexes.
   mutable std::vector<std::pair<llvm::Regex, std::string>>
       RegexHeaderMappingTable;
+  // Guards Regex matching as it's not thread-safe.
+  mutable std::mutex RegexMutex;
 };
 
 /// Returns a CommentHandler that parses pragma comment on include files to
 /// determine when we should include a different header from the header that
 /// directly defines a symbol. Mappinps are registered with \p Includes.
 ///
 /// Currently it only supports IWYU private pragma:
 /// https://github.com/include-what-you-use/include-what-you-use/blob/master/docs/IWYUPragmas.md#iwyu-pragma-private

clangd/index/CanonicalIncludes.cpp

 namespace clang {
 namespace clangd {
 namespace {
 const char IWYUPragma[] = "// IWYU pragma: private, include ";
 } // namespace
 
 void CanonicalIncludes::addMapping(llvm::StringRef Path,
                                    llvm::StringRef CanonicalPath) {
   addRegexMapping((llvm::Twine("^") + llvm::Regex::escape(Path) + "$").str(),
                   CanonicalPath);
 }
 
 void CanonicalIncludes::addRegexMapping(llvm::StringRef RE,
                                         llvm::StringRef CanonicalPath) {
   this->RegexHeaderMappingTable.emplace_back(llvm::Regex(RE), CanonicalPath);
 }
 
 llvm::StringRef CanonicalIncludes::mapHeader(llvm::StringRef Header) const {
+  std::lock_guard<std::mutex> Lock(RegexMutex);
   for (auto &Entry : RegexHeaderMappingTable) {
 #ifndef NDEBUG
     std::string Dummy;
     assert(Entry.first.isValid(Dummy) && "Regex should never be invalid!");
 #endif
     if (Entry.first.match(Header))
       return Entry.second;
   }

clangd/index/FileIndex.cpp

 #include "FileIndex.h"
 #include "SymbolCollector.h"
 #include "clang/Index/IndexingAction.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
+const CanonicalIncludes *canonicalIncludesForSystemHeaders() {
+  static const auto *Includes = [] {
+    auto *I = new CanonicalIncludes();
+    addSystemHeadersMapping(I);
+    return I;
+  }();
+  return Includes;
+}
+
 /// Retrieves namespace and class level symbols in \p Decls.
 std::unique_ptr<SymbolSlab> indexAST(ASTContext &Ctx,
                                      std::shared_ptr<Preprocessor> PP,
                                      llvm::ArrayRef<const Decl *> Decls) {
   SymbolCollector::Options CollectorOpts;
-  // Code completion gets main-file results from Sema.
-  // But we leave this option on because features like go-to-definition want it.
-  CollectorOpts.IndexMainFiles = true;
+  // Although we do not index symbols in main files (e.g. cpp file), information
+  // in main files like definition locations of class declarations will still be
+  // collected; thus, the index works for go-to-definition.
+  // FIXME(ioeric): handle IWYU pragma for dynamic index. We might want to make
+  // SymbolCollector always provides include canonicalization (e.g. IWYU, STL).
+  // FIXME(ioeric): get rid of `IndexMainFiles` as this is always set to false.
+  CollectorOpts.IndexMainFiles = false;
+  CollectorOpts.CollectIncludePath = true;
+  CollectorOpts.Includes = canonicalIncludesForSystemHeaders();
+
   auto Collector = std::make_shared<SymbolCollector>(std::move(CollectorOpts));
   Collector->setPreprocessor(std::move(PP));
   index::IndexingOptions IndexOpts;
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::All;
   IndexOpts.IndexFunctionLocals = false;
 
   index::indexTopLevelDecls(Ctx, Decls, Collector, IndexOpts);

unittests/clangd/CodeCompleteTests.cpp

 TEST(CompletionTest, DynamicIndexMultiFile) {
   MockFSProvider FS;
   MockCompilationDatabase CDB;
   IgnoreDiagnostics DiagConsumer;
   ClangdServer Server(CDB, DiagConsumer, FS, getDefaultAsyncThreadsCount(),
                       /*StorePreamblesInMemory=*/true,
                       /*BuildDynamicSymbolIndex=*/true);
 
-  Server.addDocument(testPath("foo.cpp"), R"cpp(
+  FS.Files[testPath("foo.h")] = R"cpp(
       namespace ns { class XYZ {}; void foo(int x) {} }
+  )cpp";
+  Server.addDocument(testPath("foo.cpp"), R"cpp(
+      #include "foo.h"
   )cpp");
   ASSERT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for preamble";
 
   auto File = testPath("bar.cpp");
   Annotations Test(R"cpp(
       namespace ns {
       class XXX {};
       /// Doooc

unittests/clangd/FileIndexTests.cpp

 //===-- FileIndexTests.cpp  ---------------------------*- C++ -*-----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
+#include "TestFS.h"
 #include "index/FileIndex.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/PCHContainerOperations.h"
 #include "clang/Frontend/Utils.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using testing::UnorderedElementsAre;
std::vector<std::string> match(const SymbolIndex &I,
   std::vector<std::string> Matches;
   I.fuzzyFind(Req, [&](const Symbol &Sym) {
     Matches.push_back((Sym.Scope + Sym.Name).str());
   });
   return Matches;
 }
 
 /// Create an ParsedAST for \p Code. Returns None if \p Code is empty.
-llvm::Optional<ParsedAST> build(std::string Path, llvm::StringRef Code) {
+/// \p Code is put into <Path>.h which is included by \p <BasePath>.cpp.
+llvm::Optional<ParsedAST> build(llvm::StringRef BasePath,
+                                llvm::StringRef Code) {
   if (Code.empty())
     return llvm::None;
-  const char *Args[] = {"clang", "-xc++", Path.c_str()};
+
+  assert(llvm::sys::path::extension(BasePath).empty() &&
+         "BasePath must be a base file path without extension.");
+  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
+      new vfs::InMemoryFileSystem);
+  std::string Path = (BasePath + ".cpp").str();
+  std::string Header = (BasePath + ".h").str();
+  VFS->addFile(Path, 0, llvm::MemoryBuffer::getMemBuffer(""));
+  VFS->addFile(Header, 0, llvm::MemoryBuffer::getMemBuffer(Code));
+  const char *Args[] = {"clang", "-xc++", "-include", Header.c_str(),
+                        Path.c_str()};
 
   auto CI = createInvocationFromCommandLine(Args);
 
   auto Buf = llvm::MemoryBuffer::getMemBuffer(Code);
   auto AST = ParsedAST::Build(std::move(CI), nullptr, std::move(Buf),
-                              std::make_shared<PCHContainerOperations>(),
-                              vfs::getRealFileSystem());
+                              std::make_shared<PCHContainerOperations>(), VFS);
   assert(AST.hasValue());
   return std::move(*AST);
 }
 
 TEST(FileIndexTest, IndexAST) {
   FileIndex M;
   M.update(
       "f1",
M.update("f1",
            build("f1", "class X { static int m1; int m2; static void f(); };")
                .getPointer());
 
   FuzzyFindRequest Req;
   Req.Query = "";
   EXPECT_THAT(match(M, Req), UnorderedElementsAre("X"));
 }
 
+#ifndef LLVM_ON_WIN32
+TEST(FileIndexTest, CanonicalizeSystemHeader) {
+  FileIndex M;
+  std::string File = testPath("bits/basic_string");
+  M.update(File, build(File, "class string {};").getPointer());
+
+  FuzzyFindRequest Req;
+  Req.Query = "";
+  M.fuzzyFind(Req, [&](const Symbol &Sym) {
+    EXPECT_EQ(Sym.Detail->IncludeHeader, "<string>");
+  });
+}
+#endif
+
 } // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/HeadersTests.cpp

 class HeadersTest : public ::testing::Test {
 public:
   HeadersTest() {
     CDB.ExtraClangFlags = {SearchDirArg.c_str()};
     FS.Files[MainFile] = "";
   }
 
 protected:
-  // Adds \p File with content \p Code to the sub directory and returns the
-  // absolute path.
-//  std::string addToSubdir(PathRef File, llvm::StringRef Code = "") {
-//    assert(llvm::sys::path::is_relative(File) && "FileName should be relative");
-//    llvm::SmallString<32> Path;
-//    llvm::sys::path::append(Path, Subdir, File);
-//    FS.Files[Path] = Code;
-//    return Path.str();
-//  };
-
-  // Shortens the header and returns "" on error.
-  std::string shorten(PathRef Header) {
+  // Calculates the include path for \p Header, or returns "" on error.
+  std::string calculate(PathRef Header) {
     auto VFS = FS.getTaggedFileSystem(MainFile).Value;
     auto Cmd = CDB.getCompileCommand(MainFile);
     assert(static_cast<bool>(Cmd));
     VFS->setCurrentWorkingDirectory(Cmd->Directory);
     auto Path =
-        shortenIncludePath(MainFile, FS.Files[MainFile], Header, *Cmd, VFS);
+        calculateIncludePath(MainFile, FS.Files[MainFile], Header, *Cmd, VFS);
     if (!Path) {
       llvm::consumeError(Path.takeError());
       return std::string();
     }
     return std::move(*Path);
   }
   MockFSProvider FS;
   MockCompilationDatabase CDB;
   std::string MainFile = testPath("main.cpp");
   std::string Subdir = testPath("sub");
   std::string SearchDirArg = (llvm::Twine("-I") + Subdir).str();
 };
 
 TEST_F(HeadersTest, InsertInclude) {
   std::string Path = testPath("sub/bar.h");
   FS.Files[Path] = "";
-  EXPECT_EQ(shorten(Path), "\"bar.h\"");
+  EXPECT_EQ(calculate(Path), "\"bar.h\"");
 }
 
 TEST_F(HeadersTest, DontInsertDuplicateSameName) {
   FS.Files[MainFile] = R"cpp(
 #include "bar.h"
 )cpp";
   std::string BarHeader = testPath("sub/bar.h");
   FS.Files[BarHeader] = "";
-  EXPECT_EQ(shorten(BarHeader), "");
+  EXPECT_EQ(calculate(BarHeader), "");
 }
 
 TEST_F(HeadersTest, DontInsertDuplicateDifferentName) {
   std::string BarHeader = testPath("sub/bar.h");
   FS.Files[BarHeader] = "";
   FS.Files[MainFile] = R"cpp(
 #include "sub/bar.h"  // not shortest
 )cpp";
-  EXPECT_EQ(shorten(BarHeader), "");
+  EXPECT_EQ(calculate(BarHeader), "");
 }
 
 TEST_F(HeadersTest, StillInsertIfTrasitivelyIncluded) {
   std::string BazHeader = testPath("sub/baz.h");
   FS.Files[BazHeader] = "";
   std::string BarHeader = testPath("sub/bar.h");
   FS.Files[BarHeader] = R"cpp(
 #include "baz.h"
 )cpp";
   FS.Files[MainFile] = R"cpp(
 #include "bar.h"
 )cpp";
-  EXPECT_EQ(shorten(BazHeader), "\"baz.h\"");
+  EXPECT_EQ(calculate(BazHeader), "\"baz.h\"");
+}
+
+TEST_F(HeadersTest, DoNotInsertIfInSameFile) {
+  MainFile = testPath("main.h");
+  FS.Files[MainFile] = "";
+  EXPECT_EQ(calculate(MainFile), "");
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang