[clangd] Avoid duplicates in findDefinitions response

[simark]

Summary

When compile_commands.json contains some source files expressed as
relative paths, we can get duplicate responses to findDefinitions. The
responses only differ by the URI, which are different versions of the
same file:

"result": [
    {
        ...
        "uri": "file:///home/emaisin/src/ls-interact/cpp-test/build/../src/first.h"
    },
    {
        ...
        "uri": "file:///home/emaisin/src/ls-interact/cpp-test/src/first.h"
    }
]

In getAbsoluteFilePath, we try to obtain the realpath of the FileEntry
by calling tryGetRealPathName. However, this doesn't work for
FileEntries that don't actually open the file, because their
RealPathName field is never populated.

I changed getAbsoluteFilePath so that if tryGetRealPathName returns an
empty string, we try to find the real path using VFS.getRealPath. This
requires to pass the VFS all the way from ClangdServer.

I tried to write a test case similar to

TEST(GoToDefinition, RelPathsInCompileCommand)

that would trigger this issue, but I wasn't able to. No matter what I
do, the paths are returned by the FileManager as already normalized /
without the "..". There must be something different in the test case
than in real execution that I don't see.

Repro instructions are in bug #37963, though I can include them in the
commit message if you prefer.

[ilya-biryukov]

Thanks for the patch!
Could we try to figure out why the duplicates were there in the first place and why the paths were different?
It should be easy to mock exactly the same setup you have in #37963, i.e. create a vfs with three files and compilation database that has exactly those compile commands. You mention you tried to repro the issue, did you try doing that with the unit-test or a lit-test?

After looking at the makefile, my guess would be that the problem comes from the paths starting with ../ inside the compilation database.

clangd/XRefs.cpp

179 ↗

(On Diff #153209)

Do we really need an extra vfs param?
Could we use SourceMgr.getFileManager().getVirtualFileSystem() instead?

unittests/clangd/TestTU.h

47 ↗

(On Diff #153209)

We don't need an extra output param here.
There's a way to get the vfs from the ASTContext: ParsedAST().getASTContext().getSourceManager().getFileManager().getVirtualFileSystem().

[ilya-biryukov]

Also some heads-up: this would probably conflict D47846 that moves the same function into a different file.

[simark]

In D48687#1146308, @ilya-biryukov wrote:

Thanks for the patch!
Could we try to figure out why the duplicates were there in the first place and why the paths were different?

I tried to do that, but it goes deep in the clang internals with which I'm not familiar. All I could see was that when creating the FileEntry representing the /home/emaisin/src/ls-interact/cpp-test/build/../src/first.h file, FileManager::getFile is called with OpenFile=false. This makes it so that the RealPathName field is not set (at FileManager.cpp:320). Because RealPathName is not set (well, empty), we use the non-normalized name in getAbsoluteFilePath. That's all I can tell.

It should be easy to mock exactly the same setup you have in #37963, i.e. create a vfs with three files and compilation database that has exactly those compile commands. You mention you tried to repro the issue, did you try doing that with the unit-test or a lit-test?

I tried doing a unit test that mimics the setup in #37963. For some reason I can't explain, the header file would always come out "correct". If you want to investigate further, I can update the patch with what I have so far.

After looking at the makefile, my guess would be that the problem comes from the paths starting with ../ inside the compilation database.

Yes. But AFAIK it's valid (it's relative to directory, which is the build directory. The compile_commands.json is generated with Bear.

clangd/XRefs.cpp

179 ↗

(On Diff #153209)

Ah probably not. I couldn't find a way to get a handle on the VFS, but that looks good.

unittests/clangd/TestTU.h

47 ↗

(On Diff #153209)

Thanks. It's just not obvious :).

[malaperle]

In D48687#1146515, @simark wrote:

In D48687#1146308, @ilya-biryukov wrote:

Thanks for the patch!
Could we try to figure out why the duplicates were there in the first place and why the paths were different?

I tried to do that, but it goes deep in the clang internals with which I'm not familiar. All I could see was that when creating the FileEntry representing the /home/emaisin/src/ls-interact/cpp-test/build/../src/first.h file, FileManager::getFile is called with OpenFile=false. This makes it so that the RealPathName field is not set (at FileManager.cpp:320). Because RealPathName is not set (well, empty), we use the non-normalized name in getAbsoluteFilePath. That's all I can tell.

I think from what we've seen before, it had to do with location coming from the preamble vs not. Simon, maybe we can spend some time together to investigate this. I know I said I'd rather not touch the Clang part as I thought it might be on purpose and/or performance sensitive, but the fact that the locations are inconsistent between the preamble and outside...it's not ideal and error-prone. Either way I think we need this fix in Clangd as a defensive fix because it's not in the AST's contract/guarantees (preamble or not) to provide locations with realpaths.

[hokein]

Could we try to figure out why the duplicates were there in the first place and why the paths were different?

+1, I think there are two issues here:

1. the result contains two candidates, which should be one, IIUC.
2. the absolute file path problem, we encountered similar problem in SymbolCollector, and we have similar function ToURI there, I think we can share the implementation instead of having different duplications.

[ilya-biryukov]

I'm somewhat familiar with the internals of clang around the FileManager/VFS, so I could try creating the repro of this issue. The bugreport has enough info to get started. (Probably tomorrow, I certainly won't get to it today).

In D48687#1146645, @hokein wrote:

2. the absolute file path problem, we encountered similar problem in SymbolCollector, and we have similar function ToURI there, I think we can share the implementation instead of having different duplications.

+1 to sharing the code. I guess we're struggling with similar problems here. Any pointers to the functions we should use?

unittests/clangd/TestTU.h

47 ↗

(On Diff #153209)

Yeah, it is quite deeply hidden :-)

[simark]

Btw, this seems to happen only when the included header is in the preamble. If I put a variable declaration before #include "first.h", things work as expected, we have not duplicates and the path is normalized.

[simark]

FYI, I have uploaded my attempt at writing a unit test here:

https://reviews.llvm.org/D48726

I tried to make it as close as possible to the example in the bug report, but don't manage to reproduce the bug.

[hokein]

After taking a look closely, I figured why there are two candidates here -- one is from AST (the one with ".." path); the other one is from dynamic index, the deduplication failed because of the different paths :(

I think the fixing way is to normalize the file path from AST (making it absolute).

+1 to sharing the code. I guess we're struggling with similar problems here. Any pointers to the functions we should use?

Yeah, we struggled this problem in SymbolCollector. We cleanup the file path manually. I'd suggest abstract that logic from toURI (https://github.com/llvm-mirror/clang-tools-extra/blob/master/clangd/index/SymbolCollector.cpp#L80), and use it here.

I tried to make it as close as possible to the example in the bug report, but don't manage to reproduce the bug.

To reproduce the issue, I think you'd also need to enable the dynamic index.

[simark]

In D48687#1150960, @hokein wrote:

After taking a look closely, I figured why there are two candidates here -- one is from AST (the one with ".." path); the other one is from dynamic index, the deduplication failed because of the different paths :(

I think the fixing way is to normalize the file path from AST (making it absolute).

+1 to sharing the code. I guess we're struggling with similar problems here. Any pointers to the functions we should use?

Yeah, we struggled this problem in SymbolCollector. We cleanup the file path manually. I'd suggest abstract that logic from toURI (https://github.com/llvm-mirror/clang-tools-extra/blob/master/clangd/index/SymbolCollector.cpp#L80), and use it here.

I tried to make it as close as possible to the example in the bug report, but don't manage to reproduce the bug.

To reproduce the issue, I think you'd also need to enable the dynamic index.

Thanks for looking into it. In my unit test, the only path I receive is one without "..", although I don't use the dynamic index. Still, I tried to enable the dynamic index using:

auto Opts = ClangdServer::optsForTest();
Opts.BuildDynamicSymbolIndex = true;
ClangdServer Server(CDB, FS, DiagConsumer, Opts);

but it didn't change the result.

[simark]

An update, I traced the difference in behavior to the difference in how RealFileSystem and InMemoryFileSystem return Statuses.

I uploaded a patch to change InMemoryFileSystem to work like RealFileSystem: https://reviews.llvm.org/D48903

With this patch applied on clang, it is now possible to write a test that reproduces the issue. As @hokein said, if I keep the dynamic disabled, I get a single result with the ".." in it. If I enable the dynamic index, I get two results, one with ".." and one without.

[ilya-biryukov]

I think the fixing way is to normalize the file path from AST (making it absolute).

Totally agree. Could we run the code used to get the URI to store in the dynamic index? Should we expose and reuse code in getSymbolLocation() from SymbolCollector.cpp?

[simark]

I took a look at SymbolCollector's toURI, and I am not sure what to get from it. It seems like a lot of it could be replaced with a call to FileSystem::getRealPath.

[simark]

This is an update of my work in progress. I haven't done any sharing with
SymbolCollector, as it's not clear to me how to proceed with that.

[simark]

New version. I tried to share the code between this and SymbolCollector, but
didn't find a good clean way. Do you have concrete suggestions on how to do
this? Otherwise, would it be acceptable to merge it as-is?

[simark]

Formatting.

[hokein]

Sorry for the delay. I thought there was a dependent patch of this patch, but it seems resolved, right?

A rough round of review.

New version. I tried to share the code between this and SymbolCollector, but
didn't find a good clean way. Do you have concrete suggestions on how to do
this? Otherwise, would it be acceptable to merge it as-is?

Yeah, I'm fine with the current change. I was not aware of the getAbsoluteFilePath has been pulled out to the SourceCode.h. I think the SymbolCollector could use this function as well (but that's out of scope of this patch).

clangd/SourceCode.h

65 ↗

(On Diff #159768)

Why rename this function?

Is it guaranteed that RealPath is always an absolute path?

unittests/clangd/TestFS.cpp

50–62

Can we use RelPathPrefix.empty() instead of comparing with StringRef()?

unittests/clangd/XRefsTests.cpp

325

It seems that there is no difference between HeaderInPreambleAnnotations and HeaderNotInPreambleAnnotations in the test. Both of them are treated equally.

[simark]

In D48687#1193470, @hokein wrote:

Sorry for the delay. I thought there was a dependent patch of this patch, but it seems resolved, right?

A rough round of review.

Right, the patch this one depends on is in clang, and there does not seem to be regressions this time.

New version. I tried to share the code between this and SymbolCollector, but
didn't find a good clean way. Do you have concrete suggestions on how to do
this? Otherwise, would it be acceptable to merge it as-is?

Yeah, I'm fine with the current change. I was not aware of the getAbsoluteFilePath has been pulled out to the SourceCode.h. I think the SymbolCollector could use this function as well (but that's out of scope of this patch).

Thanks.

clangd/SourceCode.h

65 ↗

(On Diff #159768)

Before, it only made sure that the path was absolute, now it goes a step further and makes it a "real path", resolving symlinks and removing . and ... When we talk about a "real path", it refers to the unix realpath syscall:

http://man7.org/linux/man-pages/man3/realpath.3.html

So yes, the result is guaranteed to be absolute too.

unittests/clangd/TestFS.cpp

50–62

Done.

unittests/clangd/XRefsTests.cpp

325

The difference is that one is included in the main file as part of the preamble and the other is out of the preamble. Since they take different code paths in clang, I think it's good to test both. At some point, I had a similar bug that would only happen with a header included in the preamble.

[simark]

Replace

RelPathPrefix == StringRef()

with

RelPathPrefix.empty()

[ilya-biryukov]

Only a few NITs from my side.
Excited for this fix to get in, have been seeing duplicate in other cases too :-)

clangd/SourceCode.h

69 ↗

(On Diff #159972)

This function looks like a good default choice for normalizing paths before putting them into LSP structs, ClangdServer responses, etc.
I suggest we add a small comment here with a guideline for everyone to attempt using it whenever possible. WDYT?

unittests/clangd/TestFS.h

42–48

s/not null/not empty

45

s/not null/not empty

[simark]

clangd/SourceCode.h

69 ↗

(On Diff #159972)

What about this:

/// Get the real/canonical path of \p F.  This means:
///
///   - Absolute path
///   - Symlinks resolved
///   - No "." or ".." component
///   - No duplicate or trailing directory separator
///
/// This function should be used when sending paths to clients, so that paths
/// are normalized as much as possible.

[hokein]

Looks good with a few nits. Looks like you didn't update the patch correctly. You have marked comments done, but your code doesn't get changed accordingly. Please double check with it.

I tried your patch and it did fix the duplicated issue I encountered before. Thanks for fixing it!

clangd/SourceCode.h

65 ↗

(On Diff #159972)

nit: this comment is not needed.

69 ↗

(On Diff #159972)

SG.

65 ↗

(On Diff #159768)

That makes sense, thanks for the explanation and the useful link!

[simark]

In D48687#1195840, @hokein wrote:

Looks good with a few nits. Looks like you didn't update the patch correctly. You have marked comments done, but your code doesn't get changed accordingly. Please double check with it.

I tried your patch and it did fix the duplicated issue I encountered before. Thanks for fixing it!

Ah sorry, I applied the fixes locally, but was waiting for Ilya's feedback for the function comment.

[simark]

Latest update.

[simark]

clangd/SourceCode.h

65 ↗

(On Diff #159972)

Woops, merge mistake.

[ioeric]

clangd/SourceCode.cpp

218

With the recent performance regression due to getRealPath() mentioned in D51159, I think we should re-evaluate whether VFS::getRealPath(), which calls expensive real_path system call on real FS, was necessary to fix the bug mentioned in the patch summary. I think vfs::makeAbsolutePath with remove_dot_dot (without symlink resolution) should be sufficient to address the issue. The code completion latency has increased dramatically with the real_path call, so I would also expect Xrefs/findDefinition to slow down due to this. As SymbolCollector is not in a latency sensitive code paths, it might be OK for it to call real_path, but I think we should try to avoid using real_path elsewhere.

In general, it's unclear whether clangd should always resolve symlink (it might not always be what users want), and it should probably be a decision made by the build system integration. I think we would need a more careful design if we decide to handle symlinks in clangd.

clangd/SourceCode.cpp

 std::vector<TextEdit> replacementsToEdits(StringRef Code,
                                           const tooling::Replacements &Repls) {
   std::vector<TextEdit> Edits;
   for (const auto &R : Repls)
     Edits.push_back(replacementToEdit(Code, R));
   return Edits;
 }
 
-llvm::Optional<std::string>
-getAbsoluteFilePath(const FileEntry *F, const SourceManager &SourceMgr) {
-  SmallString<64> FilePath = F->tryGetRealPathName();
-  if (FilePath.empty())
-    FilePath = F->getName();
-  if (!llvm::sys::path::is_absolute(FilePath)) {
-    if (!SourceMgr.getFileManager().makeAbsolutePath(FilePath)) {
-      log("Could not turn relative path to absolute: {0}", FilePath);
+/// Turn \p InputPath, a relative or absolute path, to a real path.
+static llvm::Optional<std::string>
+getAbsoluteFilePath(StringRef InputPath, const FileManager &FileMgr) {
+  llvm::SmallString<128> Path = InputPath;
+
+  if (!llvm::sys::path::is_absolute(Path)) {
+    if (!FileMgr.makeAbsolutePath(Path)) {
+      log("Could not turn relative path to absolute: {0}", Path);
       return llvm::None;
     }
   }
+
+  llvm::SmallString<128> AbsolutePath;
+  if (FileMgr.getVirtualFileSystem()->getRealPath(Path, AbsolutePath)) {
+    log("Could not compute real path: {0}", Path);
+    return Path.str().str();
+  }
+
+  return AbsolutePath.str().str();
+}
+
+llvm::Optional<std::string>
+getAbsoluteFilePath(const FileEntry *F, const SourceManager &SourceMgr) {
+  // Ideally, we get the real path from the FileEntry object.
+  SmallString<64> FilePath = F->tryGetRealPathName();
+  if (!FilePath.empty()) {
     return FilePath.str().str();
   }
 
+  // Otherwise, we try to compute ourselves.
+  vlog("FileEntry for {0} did not contain the real path.", F->getName());
+
+  return getAbsoluteFilePath(F->getName(), SourceMgr.getFileManager());
+}
+
 } // namespace clangd
 } // namespace clang

unittests/clangd/TestFS.h

public:
 
   // If relative paths are used, they are resolved with testPath().
   llvm::StringMap<std::string> Files;
 };
 
 // A Compilation database that returns a fixed set of compile flags.
 class MockCompilationDatabase : public GlobalCompilationDatabase {
 public:
-  /// When \p UseRelPaths is true, uses relative paths in compile commands.
-  /// When \p UseRelPaths is false, uses absoulte paths.
-  MockCompilationDatabase(bool UseRelPaths = false);
+  /// If \p Directory is not null, use that as the Directory field of the
+  /// CompileCommand.
+  ///
+  /// If \p RelPathPrefix is not null, use that as a prefix in front of the
+  /// source file name, instead of using an absolute path.
+  MockCompilationDatabase(StringRef Directory = StringRef(),
+                          StringRef RelPathPrefix = StringRef());
 
   llvm::Optional<tooling::CompileCommand>
   getCompileCommand(PathRef File) const override;
 
   std::vector<std::string> ExtraClangFlags;
-  const bool UseRelPaths;
+
+private:
+  StringRef Directory;
+  StringRef RelPathPrefix;
 };
 
 // Returns an absolute (fake) test directory for this OS.
 const char *testRoot();
 
 // Returns a suitable absolute path for this OS.
 std::string testPath(PathRef File);
 
 // unittest: is a scheme that refers to files relative to testRoot()
 // This anchor is used to force the linker to link in the generated object file
 // and thus register unittest: URI scheme plugin.
 extern volatile int UnittestSchemeAnchorSource;
 
 } // namespace clangd
 } // namespace clang
 #endif

unittests/clangd/TestFS.cpp

buildTestFS(StringMap<std::string> const &Files) {
   for (auto &FileAndContents : Files) {
     MemFS->addFile(FileAndContents.first(), time_t(),
                    MemoryBuffer::getMemBufferCopy(FileAndContents.second,
                                                   FileAndContents.first()));
   }
   return MemFS;
 }
 
-MockCompilationDatabase::MockCompilationDatabase(bool UseRelPaths)
-    : ExtraClangFlags({"-ffreestanding"}), UseRelPaths(UseRelPaths) {
+MockCompilationDatabase::MockCompilationDatabase(StringRef Directory,
+                                                 StringRef RelPathPrefix)
+    : ExtraClangFlags({"-ffreestanding"}), Directory(Directory),
+      RelPathPrefix(RelPathPrefix) {
   // -ffreestanding avoids implicit stdc-predef.h.
 }
 
 Optional<tooling::CompileCommand>
 MockCompilationDatabase::getCompileCommand(PathRef File) const {
   if (ExtraClangFlags.empty())
     return None;
 
-  auto CommandLine = ExtraClangFlags;
   auto FileName = sys::path::filename(File);
+
+  // Build the compile command.
+  auto CommandLine = ExtraClangFlags;
   CommandLine.insert(CommandLine.begin(), "clang");
-  CommandLine.insert(CommandLine.end(), UseRelPaths ? FileName : File);
-  return {tooling::CompileCommand(sys::path::parent_path(File), FileName,
-                                  std::move(CommandLine), "")};
+  if (RelPathPrefix == StringRef()) {
+    // Use the absolute path in the compile command.
+    CommandLine.push_back(File);
+  } else {
+    // Build a relative path using RelPathPrefix.
+    SmallString<32> RelativeFilePath(RelPathPrefix);
+    llvm::sys::path::append(RelativeFilePath, FileName);
+    CommandLine.push_back(RelativeFilePath.str());
+  }
+
+  return {tooling::CompileCommand(
+      Directory != StringRef() ? Directory : sys::path::parent_path(File),
+      FileName, std::move(CommandLine), "")};
 }
 
 const char *testRoot() {
 #ifdef _WIN32
   return "C:\\clangd-test";
 #else
   return "/clangd-test";
 #endif

unittests/clangd/XRefsTests.cpp

for (const auto &R : T.ranges())
       ExpectedLocations.push_back(RangeIs(R));
     EXPECT_THAT(findDefinitions(AST, T.point()),
                 ElementsAreArray(ExpectedLocations))
         << Test;
   }
 }
 
 TEST(GoToDefinition, RelPathsInCompileCommand) {
+  // The source is in "/clangd-test/src".
+  // We build in "/clangd-test/build".
+
   Annotations SourceAnnotations(R"cpp(
+#include "header_in_preamble.h"
 int [[foo]];
-int baz = f^oo;
+#include "header_not_in_preamble.h"
+int baz = f$p1^oo + bar_pre$p2^amble + bar_not_pre$p3^amble;
+)cpp");
+
+  Annotations HeaderInPreambleAnnotations(R"cpp(
+int [[bar_preamble]];
+)cpp");
+
+  Annotations HeaderNotInPreambleAnnotations(R"cpp(
+int [[bar_not_preamble]];
 )cpp");
 
+  // Make the compilation paths appear as ../src/foo.cpp in the compile
+  // commands.
+  SmallString<32> RelPathPrefix("..");
+  llvm::sys::path::append(RelPathPrefix, "src");
+  std::string BuildDir = testPath("build");
+  MockCompilationDatabase CDB(BuildDir, RelPathPrefix);
+
   IgnoreDiagnostics DiagConsumer;
-  MockCompilationDatabase CDB(/*UseRelPaths=*/true);
   MockFSProvider FS;
   ClangdServer Server(CDB, FS, DiagConsumer, ClangdServer::optsForTest());
 
-  auto FooCpp = testPath("foo.cpp");
+  // Fill the filesystem.
+  auto FooCpp = testPath("src/foo.cpp");
   FS.Files[FooCpp] = "";
+  auto HeaderInPreambleH = testPath("src/header_in_preamble.h");
+  FS.Files[HeaderInPreambleH] = HeaderInPreambleAnnotations.code();
+  auto HeaderNotInPreambleH = testPath("src/header_not_in_preamble.h");
+  FS.Files[HeaderNotInPreambleH] = HeaderNotInPreambleAnnotations.code();
 
-  Server.addDocument(FooCpp, SourceAnnotations.code());
   runAddDocument(Server, FooCpp, SourceAnnotations.code());
+
+  // Go to a definition in main source file.
   auto Locations =
-      runFindDefinitions(Server, FooCpp, SourceAnnotations.point());
+      runFindDefinitions(Server, FooCpp, SourceAnnotations.point("p1"));
   EXPECT_TRUE(bool(Locations)) << "findDefinitions returned an error";
-
   EXPECT_THAT(*Locations, ElementsAre(Location{URIForFile{FooCpp},
                                                SourceAnnotations.range()}));
+
+  // Go to a definition in header_in_preamble.h.
+  Locations = runFindDefinitions(Server, FooCpp, SourceAnnotations.point("p2"));
+  EXPECT_TRUE(bool(Locations)) << "findDefinitions returned an error";
+  EXPECT_THAT(*Locations,
+              ElementsAre(Location{URIForFile{HeaderInPreambleH},
+                                   HeaderInPreambleAnnotations.range()}));
+
+  // Go to a definition in header_not_in_preamble.h.
+  Locations = runFindDefinitions(Server, FooCpp, SourceAnnotations.point("p3"));
+  EXPECT_TRUE(bool(Locations)) << "findDefinitions returned an error";
+  EXPECT_THAT(*Locations,
+              ElementsAre(Location{URIForFile{HeaderNotInPreambleH},
+                                   HeaderNotInPreambleAnnotations.range()}));
 }
 
 TEST(Hover, All) {
   struct OneTest {
     StringRef Input;
     StringRef ExpectedHover;
   };