[clangd] Filter implicit references from index while renaming

[kbobyrev]

Summary

When asked for references during cross-file rename, index might return implicit references to the renamed symbol (such as those in macro expansions). To fix the incorrect behavior, this patch introduces basic filtering machinery which ensures that all ranges where renaming is about to be applied actually contains the identifier the user asked to rename.

[hokein]

(apologies, the FIXME may imply this approach...)

this approach is based on an assumption: the index results are matched to the latest file content, but this is not always true in practice, our index maybe stale (index results came from an old snapshot of the file), then this approach will fail.

I think we should do it in another direction:

• add a new RefKind (something like implicit references, or named references) to clangd::Ref
• when querying the index for rename, we set a corresponding Filter in the query request (or filter out non-interesting references based on the RefKind afterwards)

[kbobyrev]

In D71598#1787806, @hokein wrote:

(apologies, the FIXME may imply this approach...)

this approach is based on an assumption: the index results are matched to the latest file content, but this is not always true in practice, our index maybe stale (index results came from an old snapshot of the file), then this approach will fail.

I think we should do it in another direction:

• add a new RefKind (something like implicit references, or named references) to clangd::Ref
• when querying the index for rename, we set a corresponding Filter in the query request (or filter out non-interesting references based on the RefKind aftjerwards)

I think this approach would also fail for stale index, wouldn't it?

I can totally understand why that might be slightly better for performance, but if we have no guarantees that our index is aware of implicit references and would not be able to mark those in the first place, this implementation would shield us from that.

Anyway, I am happy to learn more about why the proposed approach might be better, but I do not fully understand the concern here.

[kbobyrev]

(also, this should eliminate unwanted changes caused by the index being stale, wouldn't it?)

[ilya-biryukov]

If we go with the solution proposed by @hokein, it looks like using the current patch is an improvement of what we have now.
One big issue with the adding a new ref kind/ref modifier is that it requires modifications to Kythe-based index implementation, something that cannot be done as easily as landing this patch.

WDYT about landing something similar to this patch for now and discussing the possibilities of fixing it by storing enough information in the references later?

[kadircet]

clang-tools-extra/clangd/SourceCode.cpp

217 ↗

(On Diff #234265)

this one isn't used anywhere?

1136 ↗

(On Diff #234265)

SM doesn't seem to be necessary, as lex already provides that in the callback.

clang-tools-extra/clangd/SourceCode.h

301 ↗

(On Diff #234265)

i don't think it is necessary for this function to be made public, it should be OK for it to leave in rename.cpp as a helper.

clang-tools-extra/clangd/refactor/Rename.cpp

367

this one should go after adjustRenameRanges

367

both this and adjustRenameRanges seems to be lexing the source code to get identifier locations.

can we lex the file only a single time instead and make use of the result in both of the functions?
I would suggest moving collectIdentifierRanges into here and passing the result as a parameter to both of the functions.

as for implementation of filterRenameRanges you might wanna return intersection of RenameRanges and result of collectIdentifierRanges

[kbobyrev]

Sorry for a delay: I was trying to work with range patching heuristics and get it to work in generic case of "stale index returns more results than lexer", but in the end I converged to the simplest possible version of the intended change.

[kbobyrev]

Move helper function back to the anonymous namespace.

[kadircet]

clang-tools-extra/clangd/refactor/Rename.cpp

431

duplication

590–599

i believe lexing might yield a superset even if index is up-to-date,

void foo() { int bar; }
void baz() { int ba^r; }

594

exactly for the same reason above, it might not be a subset even in those circumstances.

596

i believe we should do that even if it is not a subset.

627

+

clang-tools-extra/clangd/refactor/Rename.h

80

assertion below says
assert(Indexed.size() <= Lexed.size());

[kbobyrev]

Addressed a bunch of comments to cleanup the patch and replied to ask for clarification of several unresolved comments.

clang-tools-extra/clangd/refactor/Rename.cpp

590–599

Good point. Any local variable (IIRC we don't store local variables in index, so it's not there) having the same identifier as the renamed symbol might cause the indexed ranges to be a subset of lexed ranges.

However,

i believe lexing might yield a superset even if index is up-to-date
exactly for the same reason above, it might not be a subset even in those circumstances.

I tried to describe the case when lexer will return a _subset_ of indexed results, which happens in practice. Is the suggestion to change the comments you think are misleading?

596

Maybe my understanding of getMappedRanges is incorrect, but I suppose this will happen in case indexed ranges are subset of lexed ranges in some form (i.e. no need to find exact matches explicitly). Am I missing something?

clang-tools-extra/clangd/refactor/Rename.h

adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier,
                    std::vector<Range> Indexed, const LangOptions &LangOpts);
 
 /// Calculates the lexed occurrences that the given indexed occurrences map to.
 /// Returns None if we don't find a mapping.
 ///
 /// Exposed for testing only.
 ///
 /// REQUIRED: Indexed and Lexed are sorted.
+/// REQUIRED: Indexed.size() <= Lexed.size().
 llvm::Optional<std::vector<Range>> getMappedRanges(ArrayRef<Range> Indexed,
                                                    ArrayRef<Range> Lexed);
 /// Evaluates how good the mapped result is. 0 indicates a perfect match.
 ///
 /// Exposed for testing only.
 ///
 /// REQUIRED: Indexed and Lexed are sorted, Indexed and MappedIndex have the
 /// same size.
 size_t renameRangeAdjustmentCost(ArrayRef<Range> Indexed, ArrayRef<Range> Lexed,
                                  ArrayRef<size_t> MappedIndex);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_REFACTOR_RENAME_H

clang-tools-extra/clangd/refactor/Rename.cpp

if (!AffectedFileCode) {
       elog("Fail to read file content: {0}", AffectedFileCode.takeError());
       continue;
     }
     auto RenameRanges =
         adjustRenameRanges(*AffectedFileCode, RenameDecl.getNameAsString(),
                            std::move(FileAndOccurrences.second),
                            RenameDecl.getASTContext().getLangOpts());
     if (!RenameRanges) {
       // Our heuristics fails to adjust rename ranges to the current state of
       // the file, it is most likely the index is stale, so we give up the
       // entire rename.
       return llvm::make_error<llvm::StringError>(
           llvm::formatv("Index results don't match the content of file {0} "
                         "(the index may be stale)",
                         FilePath),
           llvm::inconvertibleErrorCode());
     }
if (impliesSimpleEdit(IndexedRest.front().start, LexedRest.front().start)) {
     findNearMiss(PartialMatch, IndexedRest.drop_front(), LexedRest.drop_front(),
                  LexedIndex + 1, Fuel, MatchedCB);
     PartialMatch.pop_back();
   }
   findNearMiss(PartialMatch, IndexedRest, LexedRest.drop_front(),
                LexedIndex + 1, Fuel, MatchedCB);
 }
 
+// Assume that index is stale/has returned invalid results that can be filtered
+// by finding the intersection between both sets.
+// REQUIRES: Indexed and Lexed are sorted.
+llvm::Optional<std::vector<Range>> filterIndexResults(ArrayRef<Range> Indexed,
+                                                      ArrayRef<Range> Lexed) {
+  assert(std::is_sorted(Indexed.begin(), Indexed.end()));
+  assert(std::is_sorted(Lexed.begin(), Lexed.end()));
+  assert(Indexed.size() > Lexed.size());
+  std::vector<Range> Result;
+  std::set_intersection(Lexed.begin(), Lexed.end(), Indexed.begin(),
+                        Indexed.end(), std::back_inserter(Result));
+  if (Result.empty())
+    return llvm::None;
+  return Result;
+}
+
 } // namespace
 
 llvm::Expected<FileEdits> rename(const RenameInputs &RInputs) {
   ParsedAST &AST = RInputs.AST;
   const SourceManager &SM = AST.getSourceManager();
   llvm::StringRef MainFileCode = SM.getBufferData(SM.getMainFileID());
   auto GetFileContent = [&RInputs,
                          &SM](PathRef AbsPath) -> llvm::Expected<std::string> {
for (const auto &R : OccurrencesOffsets) {
     if (auto Err = RenameEdit.add(
             tooling::Replacement(AbsFilePath, R.first, ByteLength, NewName)))
       return std::move(Err);
   }
   return Edit(InitialCode, std::move(RenameEdit));
 }
 
 // Details:
-//  - lex the draft code to get all rename candidates, this yields a superset
-//    of candidates.
+//  - lex the draft code to get all rename candidates, this yields a set of
+//    candidates. It may be a superset of candidates returned from the index
+//    in case index is stale and there are new references to the renamed entity.
+//    It may also be a subset of candidates from the index in case when index
+//    returns some incorrect results (such as implicit references), when some
+//    references to the renamed entity have been removed or simply when
+//    local variables (references to which are not stored in index) have the
+//    same identifier name.
+//  - if the lexed ranges are subset of index candidates, try to filter the
+//    results from index by exactly matching existing ranges from lexer.
 //  - apply range patching heuristics to generate "authoritative" occurrences,
 //    cases we consider:
 //      (a) index returns a subset of candidates, we use the indexed results.
 //        - fully equal, we are sure the index is up-to-date
 //        - proper subset, index is correct in most cases? there may be false
 //          positives (e.g. candidates got appended), but rename is still safe
 //      (b) index returns non-candidate results, we attempt to map the indexed
 //          ranges onto candidates in a plausible way (e.g. guess that lines
 //          were inserted). If such a "near miss" is found, the rename is still
 //          possible
 llvm::Optional<std::vector<Range>>
 adjustRenameRanges(llvm::StringRef DraftCode, llvm::StringRef Identifier,
                    std::vector<Range> Indexed, const LangOptions &LangOpts) {
   assert(!Indexed.empty());
   assert(std::is_sorted(Indexed.begin(), Indexed.end()));
   std::vector<Range> Lexed =
       collectIdentifierRanges(Identifier, DraftCode, LangOpts);
   llvm::sort(Lexed);
-  return getMappedRanges(Indexed, Lexed);
+  return Indexed.size() <= Lexed.size() ? getMappedRanges(Indexed, Lexed)
+                                        : filterIndexResults(Indexed, Lexed);
 }
 
 llvm::Optional<std::vector<Range>> getMappedRanges(ArrayRef<Range> Indexed,
                                                    ArrayRef<Range> Lexed) {
   assert(!Indexed.empty());
   assert(std::is_sorted(Indexed.begin(), Indexed.end()));
   assert(std::is_sorted(Lexed.begin(), Lexed.end()));
+  assert(Indexed.size() <= Lexed.size());
 
-  if (Indexed.size() > Lexed.size()) {
-    vlog("The number of lexed occurrences is less than indexed occurrences");
-    return llvm::None;
-  }
   // Fast check for the special subset case.
   if (std::includes(Indexed.begin(), Indexed.end(), Lexed.begin(), Lexed.end()))
     return Indexed.vec();
 
   std::vector<size_t> Best;
   size_t BestCost = std::numeric_limits<size_t>::max();
   bool HasMultiple = 0;
   std::vector<size_t> ResultStorage;

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

llvm::StringRef FooCC;
       )cpp",
           R"cpp(
         #include "foo.h"
         Kind ff() {
           return Kind::[[ABC]];
         }
       )cpp",
       },
+      {
+          // Macros and implicit references.
+          R"cpp(
+        class [[Fo^o]] {};
+        #define FooFoo Foo
+        #define FOO Foo
+      )cpp",
+          R"cpp(
+        #include "foo.h"
+        void bar() {
+          [[Foo]] x;
+          FOO y;
+          FooFoo z;
+        }
+      )cpp",
+      },
   };
 
   for (const auto& T : Cases) {
     Annotations FooH(T.FooH);
     Annotations FooCC(T.FooCC);
     std::string FooHPath = testPath("foo.h");
     std::string FooCCPath = testPath("foo.cc");
 

 TEST(RangePatchingHeuristic, GetMappedRanges) {
   // ^ in LexedCode marks the ranges we expect to be mapped; no ^ indicates
   // there are no mapped ranges.
   struct {
     llvm::StringRef IndexedCode;
     llvm::StringRef LexedCode;
   } Tests[] = {
     {
-      // no lexed ranges.
-      "[[]]",
-      "",
-    },
-    {
       // both line and column are changed, not a near miss.
       R"([[]])",
       R"(
         [[]]
       )",
     },
     {
       // subset.