[libTooling] Change CDB heuristic to look further for files in a given language.

[adamcz]

Summary

When looking for compile commands for file of type X, other files of
type X will be preferred over files of any other type, regardless of
score.

However, when gathering the set of candidates, we only look for files
with similar name and files close to the requested one. If it happens
that none of them are in language X, we previously (before this change)
would choose one of the existing candidates of some other type.

This patch adds all files in language X (regardless of name and
location) to the list of candidates if the initial set of candidates did
not contain any files of type X. This means we will always choose a file
of type X if one exists anywhere in the project.

[adamcz]

Hey Kadir

What do you think about this change? This addresses https://github.com/clangd/clangd/issues/519, but I'm not entirely convinced this is a good idea. Let me know if you have an opinion on this.

[amosnier]

I'm not sure I'm supposed to accept a revision, but apparently I'm authorized to do so. And I'm obviously biased since I wrote the bug report. While looking for candidates close to the target file might often sound reasonable, it does not feel particularly adapted to a whole category of files: template declarations. Why would the files that include those be anywhere close to them? Also, fetching compile commands from a file written in another language pretty much always seems like a bad idea. If I understand correctly, with this commit, an arbitrary file of the same language will be picked, every time one such file is found. It would of course be even better to pick one that includes the target file (in case of a header file), but I can easily imagine that it would be much more difficult to implement.
Based on the previous analysis, I approve this commit.
I would also like to express how impressed I am by this project's efficiency!

[kadircet]

As discussed offline, this is trading off some accuracy between getting -I correct vs -std and it is unclear whether that's beneficial or harmful. It is easy to come up with examples for both and we were split 50/50 between each.
In the end all of this is a heuristic work and it is quite likely that we might break this for more people, while trying to fix this one specific case. So I don't think it's worth it.

As for suggestions(again from offline discussion) :

• We can implement a more sophisticated transfer logic in clangd layer, by making use of compile commands from a TU including a particular header
• When there's a mismatch in language, we can try to merge two commands. One with filename/path match and filetype match.

[amosnier]

In D87253#2261205, @kadircet wrote:

As discussed offline, this is trading off some accuracy between getting -I correct vs -std and it is unclear whether that's beneficial or harmful. It is easy to come up with examples for both and we were split 50/50 between each.
In the end all of this is a heuristic work and it is quite likely that we might break this for more people, while trying to fix this one specific case. So I don't think it's worth it.

As for suggestions(again from offline discussion) :

• We can implement a more sophisticated transfer logic in clangd layer, by making use of compile commands from a TU including a particular header
• When there's a mismatch in language, we can try to merge two commands. One with filename/path match and filetype match.

I do not have the full picture, but I trust your judgment. I think I understand the first suggestion, which sounds very good. I would offer to help, but I know I won't have enough time. I can test. :-) How can I make sure I will receive updates on this issue (or any prolongation of it)?

[nridge]

In D87253#2261837, @amosnier wrote:

How can I make sure I will receive updates on this issue (or any prolongation of it)?

By commenting on this review, you're automatically subscribed to it, so should get an email notification for any future comments or patch updates.

(You should also receive notifications for comments on the issue you filed, https://github.com/clangd/clangd/issues/519.)

clang/lib/Tooling/InterpolatingCompilationDatabase.cpp

public:
 
   // Returns the path for the file that best fits OriginalFilename.
   // Candidates with extensions matching PreferLanguage will be chosen over
   // others (unless it's TY_INVALID, or all candidates are bad).
   StringRef chooseProxy(StringRef OriginalFilename,
                         types::ID PreferLanguage) const {
     assert(!empty() && "need at least one candidate!");
     std::string Filename = OriginalFilename.lower();
-    auto Candidates = scoreCandidates(Filename);
+    auto Candidates = scoreCandidates(Filename, PreferLanguage);
     std::pair<size_t, int> Best =
         pickWinner(Candidates, Filename, PreferLanguage);
 
     DEBUG_WITH_TYPE(
         "interpolate",
         llvm::dbgs() << "interpolate: chose " << OriginalPaths[Best.first]
                      << " as proxy for " << OriginalFilename << " preferring "
                      << (PreferLanguage == types::TY_INVALID
private:
   // parent directory (usually the semantically significant ones in practice).
   // We search only the last four of each candidate (for efficiency).
   constexpr static int DirectorySegmentsIndexed = 4;
   constexpr static int DirectorySegmentsQueried = 2;
   constexpr static int ShortDirectorySegment = 1; // Only look at longer names.
 
   // Award points to candidate entries that should be considered for the file.
   // Returned keys are indexes into paths, and the values are (nonzero) scores.
-  DenseMap<size_t, int> scoreCandidates(StringRef Filename) const {
+  DenseMap<size_t, int> scoreCandidates(StringRef Filename,
+                                        types::ID PreferredLanguage) const {
     // Decompose Filename into the parts we care about.
     // /some/path/complicated/project/Interesting.h
     // [-prefix--][---dir---] [-dir-] [--stem---]
     StringRef Stem = sys::path::stem(Filename);
     llvm::SmallVector<StringRef, DirectorySegmentsQueried> Dirs;
     llvm::StringRef Prefix;
     auto Dir = ++sys::path::rbegin(Filename),
          DirEnd = sys::path::rend(Filename);
DenseMap<size_t, int> scoreCandidates(StringRef Filename,
     Award(1, indexLookup</*Prefix=*/false>(Stem, Stems));
     // For each of the last few directories in the Filename, award a point
     // if it's present in the candidate.
     for (StringRef Dir : Dirs)
       Award(1, indexLookup</*Prefix=*/false>(Dir, Components));
     // Award one more point if the whole rest of the path matches.
     if (sys::path::root_directory(Prefix) != Prefix)
       Award(1, indexLookup</*Prefix=*/true>(Prefix, Paths));
+
+    bool CandidateWithMatchingLanguageFound = false;
+    for (const auto &C : Candidates) {
+      if (Types[C.first] == PreferredLanguage) {
+        CandidateWithMatchingLanguageFound = true;
+        break;
+      }
+    }
+    if (!CandidateWithMatchingLanguageFound) {
+      // If none of the candidates we found so far use preferred language, try
+      // all other files, even if they are far away in the dir hierarchy.
+      for (size_t I = 0; I < OriginalPaths.size(); ++I) {
+        // Increase score by one. The actual value doesn't matter, the point is
+        // to have some candidates matching PreferredLanguage in the Candidates
+        // set at all.
+        if (Types[I] == PreferredLanguage)
+          Candidates[I] += 1;
+      }
+    }
     return Candidates;
   }
 
   // Pick a single winner from the set of scored candidates.
   // Returns (index, score).
   std::pair<size_t, int> pickWinner(const DenseMap<size_t, int> &Candidates,
                                     StringRef Filename,
                                     types::ID PreferredLanguage) const {

clang/unittests/Tooling/CompilationDatabaseTest.cpp

TEST_F(InterpolateTest, Nearby) {
   EXPECT_EQ(getProxy("some/other/bar.h"), "dir/bar.cpp");
   // two segments of directory match beat a prefix name match
   EXPECT_EQ(getProxy("an/other/b.cpp"), "an/other/foo.cpp");
   // if nothing matches at all, we still get the closest alpha match
   EXPECT_EQ(getProxy("below/some/obscure/path.cpp"), "an/other/foo.cpp");
 }
 
 TEST_F(InterpolateTest, Language) {
+  add("aaa/bbb/ccc/ddd/file.c", "");
   add("dir/foo.cpp", "-std=c++17");
   add("dir/bar.c", "");
   add("dir/baz.cee", "-x c");
   add("dir/aux.cpp", "-std=c++17 -x objective-c++");
 
   // .h is ambiguous, so we add explicit language flags
   EXPECT_EQ(getCommand("foo.h"),
             "clang -D dir/foo.cpp -x c++-header -std=c++17");
   // Same thing if we have no extension. (again, we treat as header).
   EXPECT_EQ(getCommand("foo"), "clang -D dir/foo.cpp -x c++-header -std=c++17");
   // and invalid extensions.
   EXPECT_EQ(getCommand("foo.cce"),
             "clang -D dir/foo.cpp -x c++-header -std=c++17");
   // and don't add -x if the inferred language is correct.
   EXPECT_EQ(getCommand("foo.hpp"), "clang -D dir/foo.cpp -std=c++17");
   // respect -x if it's already there.
   EXPECT_EQ(getCommand("baz.h"), "clang -D dir/baz.cee -x c-header");
   // prefer a worse match with the right extension.
   EXPECT_EQ(getCommand("foo.c"), "clang -D dir/bar.c");
+  // even when it is far away.
+  EXPECT_EQ(getCommand("aaa/bbb/ccc/ddd/file.hpp"), "clang -D dir/aux.cpp");
   Entries.erase(path(StringRef("dir/bar.c")));
+  Entries.erase(path(StringRef("aaa/bbb/ccc/ddd/file.c")));
   // Now we transfer across languages, so drop -std too.
   EXPECT_EQ(getCommand("foo.c"), "clang -D dir/foo.cpp");
   // Prefer -x over -std when overriding language.
   EXPECT_EQ(getCommand("aux.h"),
             "clang -D dir/aux.cpp -x objective-c++-header -std=c++17");
 }
 
 TEST_F(InterpolateTest, Strip) {