[clangd] findNearbyIdentifier(): fix the word search in the token stream.

[ArcsinX]

Summary

Without this patch the word occurrence search always returns the first token of the file.
Despite of that, findNeardyIdentifier() returns the correct result (but inefficently) until there are several matched tokens with the same value floor(log2(<token line> - <word line>)) (e.g. several matched tokens on the same line).

[kadircet]

thanks for catching this, LGTM! This might still end up traversing the whole file in non-existent cases, but I suppose that's an adventure for another day.

I think we should also cherry-pick this into release branch. I've filed https://bugs.llvm.org/show_bug.cgi?id=46905 for cherry-picking please update the bug
with the commit hash once you land the fix (or let me know if you don't have an account in bugzilla)

[kadircet]

oh and also, how did you notice the discrepancy? was it a random encounter while reading the code or did you notice a misbehaviour?

[ArcsinX]

In D84912#2184147, @kadircet wrote:

oh and also, how did you notice the discrepancy? was it a random encounter while reading the code or did you notice a misbehaviour?

Case was like this

void f1(int [[paramValue]]){
}

void f2(int paramValue){
}

void f3(int paramValue){
}

void f4(int paramValue){
// param^Value
}

Because of
floor(log2(8)) = floor(log2(9)) ... = floor(log2(15)) = 3

[ArcsinX]

In D84912#2184144, @kadircet wrote:

I think we should also cherry-pick this into release branch. I've filed https://bugs.llvm.org/show_bug.cgi?id=46905 for cherry-picking please update the bug
with the commit hash once you land the fix (or let me know if you don't have an account in bugzilla)

I do not have bugzilla account, so could you please do this for me?

clang-tools-extra/clangd/XRefs.cpp

auto Consider = [&](const syntax::Token &Tok) {
     BestCost = TokCost;
     BestTok = &Tok;
     return false;
   };
   auto SpelledTokens = TB.spelledTokens(File);
   // Find where the word occurred in the token stream, to search forward & back.
   auto *I = llvm::partition_point(SpelledTokens, [&](const syntax::Token &T) {
     assert(SM.getFileID(T.location()) == SM.getFileID(Word.Location));
-    return T.location() >= Word.Location; // Comparison OK: same file.
+    return T.location() < Word.Location; // Comparison OK: same file.
   });
   // Search for matches after the cursor.
   for (const syntax::Token &Tok : llvm::makeArrayRef(I, SpelledTokens.end()))
     if (Consider(Tok))
       break; // costs of later tokens are greater...
   // Search for matches before the cursor.
   for (const syntax::Token &Tok :
        llvm::reverse(llvm::makeArrayRef(SpelledTokens.begin(), I)))

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

)cpp",
       R"cpp(
       // short identifiers don't find far results
       int hi;
 
 
 
       // h^i
     )cpp",
-  };
+      R"cpp(
+      // prefer nearest occurrence even if several matched tokens
+      // have the same value of `floor(log2(<token line> - <word line>))`.
+      int hello;
+      int x = hello, y = hello;
+      int z = [[hello]];
+      // h^ello
+    )cpp"};
   for (const char *Test : Tests) {
     Annotations T(Test);
     auto AST = TestTU::withCode(T.code()).build();
     const auto &SM = AST.getSourceManager();
     llvm::Optional<Range> Nearby;
     auto Word =
         SpelledWord::touching(cantFail(sourceLocationInMainFile(SM, T.point())),
                               AST.getTokens(), AST.getLangOpts());