[clangd] Use stable keys for CanonicalIncludes mappings

[kbobyrev]

Summary

This patch switches CanonicalInclude mappings to use llvm::sys::fs::UniqueID for a stable file representation because the FileEntry::getName() results turn out to be changing throughout the lifetime of a program (exposed in D120306). This patch makes it possible for D120306 to be re-landed and increases overall stability.

[kbobyrev]

Fix the behavior: get Real Path instead.

[kbobyrev]

This is required for D120306 which was landed but later reverted because of the failing Windows tests (different slash types for filenames requested during preamble parsing and in the main file).

[kadircet]

note that you seem to be using auto PublicHeader = CanonIncludes.mapHeader(Entry->getName()); (i.e. getName) in D120306 and not tryGetRealPathName. it might be nice to have a test case here, at least one that only fails/runs on windows

[kbobyrev]

In D123031#3426303, @kadircet wrote:

note that you seem to be using auto PublicHeader = CanonIncludes.mapHeader(Entry->getName()); (i.e. getName) in D120306 and not tryGetRealPathName. it might be nice to have a test case here, at least one that only fails/runs on windows

Right! I think I also need to do that in SymbolCollector.cpp.

[kadircet]

Right! I think I also need to do that in SymbolCollector.cpp.

Now that you mentioned this too, it feels like the issue is not about being consistent, as I think all of the places that we have today are actually making use of FileEntry::getName as keys to CanonicalIncludes::{addMapping,mapHeader}. Are we sure we're not relying on some sort of canonization of file path (AFAICT, that's not the case the only canonization that's happening is dropping ..) when you use tryGetRealPathName instead of getName?

[kbobyrev]

In D123031#3426382, @kadircet wrote:

Right! I think I also need to do that in SymbolCollector.cpp.

Now that you mentioned this too, it feels like the issue is not about being consistent, as I think all of the places that we have today are actually making use of FileEntry::getName as keys to CanonicalIncludes::{addMapping,mapHeader}. Are we sure we're not relying on some sort of canonization of file path (AFAICT, that's not the case the only canonization that's happening is dropping ..) when you use tryGetRealPathName instead of getName?

Right, I think the name of the patch is misleading. "Consistent" means "consistency across different SM/FMs" rather than consistency across the call sites.

[sammccall]

Changing the strings here makes sense, but I'm confused by the use of tryGetRealPathName.
Also, we ended up dropping the filename in favor of UniqueID in IncludeStructure, so that's an alternative here.

Yes, I think we need a test here with a scope wide enough that it tests that the callsites of addMapping/getMapping line up.

clang-tools-extra/clangd/index/CanonicalIncludes.cpp

74

offline we had discussed getName rather than tryGetRealPathName instead.

The comment in HeaderStructure says specifically that we avoid tryGetRealPathName because it's not preserved in the preamble.
I suspect that this will give incorrect results in cases involving non-preamble #includes.

In any case we should have a comment somewhere on CanonicalIncludes about how we're identifying files, and why it's stable enough. The lack of such a comment is really what led to the bug on friday :-)

74

tryGetRealPathName can be the empty string, what do we do in such cases?

(In practice I think this is going to happen in the case where you have a non-preamble #include of a header-guarded file which was also part of the preamble)

[kbobyrev]

clang-tools-extra/clangd/index/CanonicalIncludes.cpp

74

Oh, okay, I thought tryGetRealPathName would not be empty here :(

The problem with getName is that it turned out to produce the same results that we already get right now through SourceManager.

That leaves us with other ways of canonicalization: either through conversions to the native path or FileManager::getCanonicalName(). Both are expensive and I think the problem is that though the mapping here would be OK to generate in an expensive manner, the callsites would not be very happy with that but I guess it's acceptable.

[kbobyrev]

Switch to stable file UniqueIDs.

[kbobyrev]

Rebase on top of main.

[kbobyrev]

Rebase correctly.

[sammccall]

clang-tools-extra/clangd/index/CanonicalIncludes.h

39–40

nit: no longer a string-to-string mapping

46

prefer FileEntryRef over FileEntry*, so the name we're looking up is controlled by the caller rather than an ~arbitrary choice in case of symlinks

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

1

Can you add a test for the new functionality? that the mapping doesn't depend on the name

Use the hard-link function in InMemoryFS to create multiple names with one UID

60

why the pointer? can't this just be FileManager Files(...)

[kbobyrev]

Address review comments.

[sammccall]

Just nits

clang-tools-extra/clangd/IncludeCleaner.cpp

359

getLastRef().getName() is just the same as Entry->getName().
We should be using SM.getFileEntryRefForID instead.

(Which is actually still not preserving the FERef under the hood, but will soon...)

clang-tools-extra/clangd/index/CanonicalIncludes.h

40

no const, FileEntryRef is passed by value (and below)

clang-tools-extra/clangd/index/SymbolCollector.cpp

384–385

again, avoid getLastRef

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

26

no need to take ownership, just take InMemoryFileSystem&?

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

1594

avoid getLastRef

[kbobyrev]

Fix the test case.

[thakis]

Looks like this breaks tests on Windows: http://45.33.8.238/win/55690/step_9.txt

please take a look, etc :)

[kbobyrev]

In D123031#3429801, @thakis wrote:

Looks like this breaks tests on Windows: http://45.33.8.238/win/55690/step_9.txt

please take a look, etc :)

Should be fixed in https://github.com/llvm/llvm-project/commit/211df7319af4d97b11f59fbc88bfb7ca27eab785

clang-tools-extra/clangd/IncludeCleaner.cpp

ReferencedFiles findReferencedFiles(const ReferencedLocations &Locs,
                                     const CanonicalIncludes &CanonIncludes,
                                     const SourceManager &SM) {
   return findReferencedFiles(
       Locs, SM,
       [&SM, &Includes](FileID ID) {
         return headerResponsible(ID, SM, Includes);
       },
       [&SM, &CanonIncludes](FileID ID) -> Optional<StringRef> {
-        const FileEntry *Entry = SM.getFileEntryForID(ID);
+        Optional<FileEntryRef> Entry = SM.getFileEntryRefForID(ID);
         if (Entry) {
-          auto PublicHeader = CanonIncludes.mapHeader(Entry->getName());
+          auto PublicHeader = CanonIncludes.mapHeader(*Entry);
           if (!PublicHeader.empty()) {
             return PublicHeader;
           }
         }
         return llvm::None;
       });
 }
 

clang-tools-extra/clangd/index/CanonicalIncludes.h

 //   We have a lookup table for common standard library implementations.
 //   libstdc++ puts char_traits in bits/char_traits.h, but we #include <string>.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_CANONICALINCLUDES_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_CANONICALINCLUDES_H
 
+#include "clang/Basic/FileEntry.h"
 #include "clang/Lex/Preprocessor.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/FileSystem/UniqueID.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:
-  /// Adds a string-to-string mapping from \p Path to \p CanonicalPath.
-  void addMapping(llvm::StringRef Path, llvm::StringRef CanonicalPath);
+  /// Adds a file-to-string mapping from \p ID to \p CanonicalPath.
+  void addMapping(FileEntryRef Header, llvm::StringRef CanonicalPath);
 
   /// Returns the overridden include for symbol with \p QualifiedName, or "".
   llvm::StringRef mapSymbol(llvm::StringRef QualifiedName) const;
 
   /// Returns the overridden include for for files in \p Header, or "".
-  llvm::StringRef mapHeader(llvm::StringRef Header) const;
+  llvm::StringRef mapHeader(FileEntryRef Header) const;
 
   /// Adds mapping for system headers and some special symbols (e.g. STL symbols
   /// in <iosfwd> need to be mapped individually). Approximately, the following
   /// system headers are handled:
   ///   - C++ standard library e.g. bits/basic_string.h$ -> <string>
   ///   - Posix library e.g. bits/pthreadtypes.h$ -> <pthread.h>
   ///   - Compiler extensions, e.g. include/avx512bwintrin.h$ -> <immintrin.h>
   /// The mapping is hardcoded and hand-maintained, so it might not cover all
   /// headers.
   void addSystemHeadersMapping(const LangOptions &Language);
 
 private:
-  /// A map from full include path to a canonical path.
-  llvm::StringMap<std::string> FullPathMapping;
+  /// A map from the private header to a canonical include path.
+  llvm::DenseMap<llvm::sys::fs::UniqueID, std::string> FullPathMapping;
   /// A map from a suffix (one or components of a path) to a canonical path.
   /// Used only for mapping standard headers.
   const llvm::StringMap<llvm::StringRef> *StdSuffixHeaderMapping = nullptr;
   /// A map from fully qualified symbol names to header names.
   /// Used only for mapping standard symbols.
   const llvm::StringMap<llvm::StringRef> *StdSymbolMapping = nullptr;
 };
 

clang-tools-extra/clangd/index/CanonicalIncludes.cpp

 //===-- CanonicalIncludes.h - remap #include headers-------------*- 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 "CanonicalIncludes.h"
 #include "Headers.h"
+#include "clang/Basic/FileEntry.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/FileSystem/UniqueID.h"
 #include "llvm/Support/Path.h"
 #include <algorithm>
 
 namespace clang {
 namespace clangd {
 namespace {
 const char IWYUPragma[] = "// IWYU pragma: private, include ";
 } // namespace
 
-void CanonicalIncludes::addMapping(llvm::StringRef Path,
+void CanonicalIncludes::addMapping(FileEntryRef Header,
                                    llvm::StringRef CanonicalPath) {
-  FullPathMapping[Path] = std::string(CanonicalPath);
+  FullPathMapping[Header.getUniqueID()] = std::string(CanonicalPath);
 }
 
 /// The maximum number of path components in a key from StdSuffixHeaderMapping.
 /// Used to minimize the number of lookups in suffix path mappings.
 constexpr int MaxSuffixComponents = 3;
 
-llvm::StringRef CanonicalIncludes::mapHeader(llvm::StringRef Header) const {
-  assert(!Header.empty());
-  auto MapIt = FullPathMapping.find(Header);
+llvm::StringRef CanonicalIncludes::mapHeader(FileEntryRef Header) const {
+  auto MapIt = FullPathMapping.find(Header.getUniqueID());
   if (MapIt != FullPathMapping.end())
     return MapIt->second;
 
   if (!StdSuffixHeaderMapping)
     return "";
 
   int Components = 1;
 
   // FIXME: check that this works on Windows and add tests.
-  for (auto It = llvm::sys::path::rbegin(Header),
-            End = llvm::sys::path::rend(Header);
+  auto Filename = Header.getName();
+  for (auto It = llvm::sys::path::rbegin(Filename),
+            End = llvm::sys::path::rend(Filename);
        It != End && Components <= MaxSuffixComponents; ++It, ++Components) {
-    auto SubPath = Header.substr(It->data() - Header.begin());
+    auto SubPath = Filename.substr(It->data() - Filename.begin());
     auto MappingIt = StdSuffixHeaderMapping->find(SubPath);
     if (MappingIt != StdSuffixHeaderMapping->end())
       return MappingIt->second;
   }
   return "";
 }
 
 llvm::StringRef CanonicalIncludes::mapSymbol(llvm::StringRef QName) const {
   return StdSymbolMapping ? StdSymbolMapping->lookup(QName) : "";
 }
 
 std::unique_ptr<CommentHandler>
 collectIWYUHeaderMaps(CanonicalIncludes *Includes) {
   class PragmaCommentHandler : public clang::CommentHandler {
   public:
     PragmaCommentHandler(CanonicalIncludes *Includes) : Includes(Includes) {}
 
     bool HandleComment(Preprocessor &PP, SourceRange Range) override {
       llvm::StringRef Text =
           Lexer::getSourceText(CharSourceRange::getCharRange(Range),
                                PP.getSourceManager(), PP.getLangOpts());
       if (!Text.consume_front(IWYUPragma))
         return false;
+      auto &SM = PP.getSourceManager();
       // We always insert using the spelling from the pragma.
-      if (auto *FE = PP.getSourceManager().getFileEntryForID(
-              PP.getSourceManager().getFileID(Range.getBegin())))
-        Includes->addMapping(FE->getName(), isLiteralInclude(Text)
-                                                ? Text.str()
-                                                : ("\"" + Text + "\"").str());
+      if (auto *FE = SM.getFileEntryForID(SM.getFileID(Range.getBegin())))
+        Includes->addMapping(
+            FE->getLastRef(),
+            isLiteralInclude(Text) ? Text.str() : ("\"" + Text + "\"").str());
       return false;
     }
 
   private:
     CanonicalIncludes *const Includes;
   };
   return std::make_unique<PragmaCommentHandler>(Includes);
 }

clang-tools-extra/clangd/index/SymbolCollector.cpp

private:
   llvm::StringRef getIncludeHeaderUncached(FileID FID) {
     const FileEntry *FE = SM.getFileEntryForID(FID);
     if (!FE || FE->getName().empty())
       return "";
     llvm::StringRef Filename = FE->getName();
     // If a file is mapped by canonical headers, use that mapping, regardless
     // of whether it's an otherwise-good header (header guards etc).
     if (Includes) {
-      llvm::StringRef Canonical = Includes->mapHeader(Filename);
+      llvm::StringRef Canonical =
+          Includes->mapHeader(*SM.getFileEntryRefForID(FID));
       if (!Canonical.empty()) {
         // If we had a mapping, always use it.
         if (Canonical.startswith("<") || Canonical.startswith("\""))
           return Canonical;
         return toURI(Canonical);
       }
     }
     // Framework headers are spelled as <FrameworkName/Foo.h>, not

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

 //===-- CanonicalIncludesTests.cpp - --------------------------------------===//
 //
 // 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 "TestFS.h"
 #include "index/CanonicalIncludes.h"
+#include "clang/Basic/FileEntry.h"
+#include "clang/Basic/FileManager.h"
 #include "clang/Basic/LangOptions.h"
+#include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/VirtualFileSystem.h"
+#include "llvm/Testing/Support/Error.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
+FileEntryRef addFile(llvm::vfs::InMemoryFileSystem &FS, FileManager &FM,
+                     llvm::StringRef Filename) {
+  FS.addFile(Filename, 0, llvm::MemoryBuffer::getMemBuffer(""));
+  auto File = FM.getFileRef(Filename);
+  EXPECT_THAT_EXPECTED(File, llvm::Succeeded());
+  return *File;
+}
+
 TEST(CanonicalIncludesTest, CStandardLibrary) {
   CanonicalIncludes CI;
   auto Language = LangOptions();
   Language.C11 = true;
   CI.addSystemHeadersMapping(Language);
   // Usual standard library symbols are mapped correctly.
   EXPECT_EQ("<stdio.h>", CI.mapSymbol("printf"));
   EXPECT_EQ("", CI.mapSymbol("unknown_symbol"));
TEST(CanonicalIncludesTest, CXXStandardLibrary) {
   EXPECT_EQ("<cstdio>", CI.mapSymbol("std::printf"));
   // std::move is ambiguous, currently always mapped to <utility>
   EXPECT_EQ("<utility>", CI.mapSymbol("std::move"));
   // Unknown std symbols aren't mapped.
   EXPECT_EQ("", CI.mapSymbol("std::notathing"));
   // iosfwd declares some symbols it doesn't own.
   EXPECT_EQ("<ostream>", CI.mapSymbol("std::ostream"));
   // And (for now) we assume it owns the others.
-  EXPECT_EQ("<iosfwd>", CI.mapHeader("iosfwd"));
+  auto InMemFS = llvm::makeIntrusiveRefCnt<llvm::vfs::InMemoryFileSystem>();
+  FileManager Files(FileSystemOptions(), InMemFS);
+  auto File = addFile(*InMemFS, Files, testPath("iosfwd"));
+  EXPECT_EQ("<iosfwd>", CI.mapHeader(File));
 }
 
 TEST(CanonicalIncludesTest, PathMapping) {
+  auto InMemFS = llvm::makeIntrusiveRefCnt<llvm::vfs::InMemoryFileSystem>();
+  FileManager Files(FileSystemOptions(), InMemFS);
+  std::string BarPath = testPath("foo/bar");
+  auto Bar = addFile(*InMemFS, Files, BarPath);
+  auto Other = addFile(*InMemFS, Files, testPath("foo/baz"));
   // As used for IWYU pragmas.
   CanonicalIncludes CI;
-  CI.addMapping("foo/bar", "<baz>");
+  CI.addMapping(Bar, "<baz>");
 
-  EXPECT_EQ("<baz>", CI.mapHeader("foo/bar"));
-  EXPECT_EQ("", CI.mapHeader("bar/bar"));
+  // We added a mapping for baz.
+  EXPECT_EQ("<baz>", CI.mapHeader(Bar));
+  // Other file doesn't have a mapping.
+  EXPECT_EQ("", CI.mapHeader(Other));
+
+  // Add hard link to "foo/bar" and check that it is also mapped to <baz>, hence
+  // does not depend on the header name.
+  std::string HardLinkPath = testPath("hard/link");
+  InMemFS->addHardLink(HardLinkPath, BarPath);
+  auto HardLinkFile = Files.getFileRef(HardLinkPath);
+  ASSERT_THAT_EXPECTED(HardLinkFile, llvm::Succeeded());
+  EXPECT_EQ("<baz>", CI.mapHeader(*HardLinkFile));
 }
 
 TEST(CanonicalIncludesTest, Precedence) {
+  auto InMemFS = llvm::makeIntrusiveRefCnt<llvm::vfs::InMemoryFileSystem>();
+  FileManager Files(FileSystemOptions(), InMemFS);
+  auto File = addFile(*InMemFS, Files, testPath("some/path"));
+
   CanonicalIncludes CI;
-  CI.addMapping("some/path", "<path>");
+  CI.addMapping(File, "<path>");
   LangOptions Language;
   Language.CPlusPlus = true;
   CI.addSystemHeadersMapping(Language);
 
   // We added a mapping from some/path to <path>.
-  ASSERT_EQ("<path>", CI.mapHeader("some/path"));
+  ASSERT_EQ("<path>", CI.mapHeader(File));
   // We should have a path from 'bits/stl_vector.h' to '<vector>'.
-  ASSERT_EQ("<vector>", CI.mapHeader("bits/stl_vector.h"));
+  auto STLVectorFile = addFile(*InMemFS, Files, testPath("bits/stl_vector.h"));
+  ASSERT_EQ("<vector>", CI.mapHeader(STLVectorFile));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

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

 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Index/IndexingOptions.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/VirtualFileSystem.h"
+#include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock-matchers.h"
 #include "gmock/gmock-more-matchers.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 #include <memory>
 #include <string>
 
TEST_F(SymbolCollectorTest, IWYUPragmaWithDoubleQuotes) {
   )";
   runSymbolCollector(Header, /*Main=*/"");
   EXPECT_THAT(Symbols, UnorderedElementsAre(
                            AllOf(qName("Foo"), declURI(TestHeaderURI),
                                  includeHeader("\"the/good/header.h\""))));
 }
 
 TEST_F(SymbolCollectorTest, SkipIncFileWhenCanonicalizeHeaders) {
-  CollectorOpts.CollectIncludePath = true;
-  CanonicalIncludes Includes;
-  Includes.addMapping(TestHeaderName, "<canonical>");
-  CollectorOpts.Includes = &Includes;
   auto IncFile = testPath("test.inc");
   auto IncURI = URI::create(IncFile).toString();
   InMemoryFileSystem->addFile(IncFile, 0,
                               llvm::MemoryBuffer::getMemBuffer("class X {};"));
-  runSymbolCollector("#include \"test.inc\"\nclass Y {};", /*Main=*/"",
+  llvm::IntrusiveRefCntPtr<FileManager> Files(
+      new FileManager(FileSystemOptions(), InMemoryFileSystem));
+  std::string HeaderCode = "#include \"test.inc\"\nclass Y {};";
+  InMemoryFileSystem->addFile(TestHeaderName, 0,
+                              llvm::MemoryBuffer::getMemBuffer(HeaderCode));
+  auto File = Files->getFileRef(TestHeaderName);
+  ASSERT_THAT_EXPECTED(File, llvm::Succeeded());
+  CanonicalIncludes Includes;
+  Includes.addMapping(*File, "<canonical>");
+  CollectorOpts.CollectIncludePath = true;
+  CollectorOpts.Includes = &Includes;
+  runSymbolCollector(HeaderCode, /*Main=*/"",
                      /*ExtraArgs=*/{"-I", testRoot()});
   EXPECT_THAT(Symbols,
               UnorderedElementsAre(AllOf(qName("X"), declURI(IncURI),
                                          includeHeader("<canonical>")),
                                    AllOf(qName("Y"), declURI(TestHeaderURI),
                                          includeHeader("<canonical>"))));
 }