[clangd] Fix one testcase in XRefsTests.

[hokein]

Summary

The test didn't test anything actually -- it used "[]" as annotation which should be
"[[]]".

This patch also fixes a bug in XRef where we may return duplicated refs.

[ilya-biryukov]

clang-tools-extra/clangd/XRefs.cpp

389 ↗

(On Diff #215601)

What are the elements References for the problematic case?

If we have duplicate elements, then sort() would now give us one of the items. Which exact Decl we're gonna end up seeing is not well-defined, i.e. it's non-deterministic.

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

2079 ↗

(On Diff #215601)

NIT: use ASSERT_THAT(ExpectedLocations, Not(IsEmpty())) for more detailed output in case of assertion failures.

[hokein]

clang-tools-extra/clangd/XRefs.cpp

389 ↗

(On Diff #215601)

What are the elements References for the problematic case?

The testcase is using declarations (see the existing test) -- we will get 3 refs on using ::fo^o, each ref has a different decl.

void [[foo]](int);
void [[foo]](double);

namespace ns {
using ::[[fo^o]];
}

If we have duplicate elements, then sort() would now give us one of the items. Which exact Decl we're gonna end up seeing is not well-defined, i.e. it's non-deterministic.

I think we could make it deterministic, but only return one refs, WDYT?

[ilya-biryukov]

clang-tools-extra/clangd/XRefs.cpp

389 ↗

(On Diff #215601)

To make sure I understand the problem: we used to get 4 references in total:

• 2 references to the functions (foo(int) and foo(double))
• 2 references pointing to the using declaration, e.g. the using ::[foo]]

After this patch we would remove the duplicate using ::[[foo]] from the results and get only 3 references as a result.

Is that correct?

[hokein]

clang-tools-extra/clangd/XRefs.cpp

389 ↗

(On Diff #215601)

Yes, that is correct.

[ilya-biryukov]

clang-tools-extra/clangd/XRefs.cpp

389 ↗

(On Diff #215601)

Interestingly enough, we always ignore the CanonicalTarget in the returned Reference.

Maybe we could remove the CanonicalTarget from the Reference struct instead?
That keeps the interface more consistent: clients will always get deterministic results (as there is no CanonicalDecl, which is different now)

[hokein]

clang-tools-extra/clangd/XRefs.cpp

389 ↗

(On Diff #215601)

Maybe we could remove the CanonicalTarget from the Reference struct instead?

unfortunately, this may not work either because of the Role -- we still fail on the above sample, the references pointing to the using decl have different roles.

[ilya-biryukov]

clang-tools-extra/clangd/XRefs.cpp

389 ↗

(On Diff #215601)

We only look at the role in DocumentHighlights to determine the DocumentHighlightKind (Read, Write or Text).
I suggest we do this earlier and replace the Reference::Role field with Reference::DocumentHighlightKind.
Then we can de-duplicate here and keep deterministic interface.

If we feel that's the wrong layering (we are putting LSP-specific things into Reference, which only has clang-specific types stuff now), we could move de-duplication downstream to findDocumentHighlights and findRefs. They return Loc and DocumentHighlighting and can safely de-duplicate on those without changing observable results.

Looks like replacing Role with HighlightingKind is the simplest option, though. And I don't think this breaks layering that much, it's an implementation detail of cross-references anyway.

[hokein]

clang-tools-extra/clangd/XRefs.cpp

389 ↗

(On Diff #215601)

Looks like replacing Role with HighlightingKind is the simplest option, though. And I don't think this breaks layering that much, it's an implementation detail of cross-references anyway.

However, we may still encounter cases where we have duplicated Locs with different HighlightingKinds.

This leaves us two choices:

1. de-duplicate the refs only by loc (as the original implemenation of the patch)
2. keep Role in refs, and do deduplication on both findDocumentHighlights and findRefs

I personally prefer 1). For document highlights, I'm not sure whether we should return multiple highlights on the same location with different HighlightingKinds, I think most of clients just choose one to render, so making clangd return only one result seems reasonable.

[ilya-biryukov]

clang-tools-extra/clangd/XRefs.cpp

389 ↗

(On Diff #215601)

I would vouch for (2):

• It's easy to explain why we de-duplicate same locations in findRefs as this is what it is exactly the return value.
• The decision about picking the kind for a duplicated location falls onto findDocumentHighlights, which is, again, the right place to make this decision (even if the decision is random, e.g. preferring Write over Read).

But if we really want to keep the code shared for both versions, let's define how we pick the winner in the case where location is the same.

The important bit is avoid non-deterministic in the observable results of this function. We should avoid Decl* or Role being part of the result and being picked randomly from a few options that we have.

[hokein]

Address review comments.

[ilya-biryukov]

LGTM

clang-tools-extra/trunk/clangd/XRefs.cpp

 }
 
 namespace {
 
 /// Collects references to symbols within the main file.
 class ReferenceFinder : public index::IndexDataConsumer {
 public:
   struct Reference {
-    const Decl *CanonicalTarget;
     SourceLocation Loc;
     index::SymbolRoleSet Role;
   };
 
   ReferenceFinder(ASTContext &AST, Preprocessor &PP,
                   const std::vector<const Decl *> &TargetDecls)
       : AST(AST) {
     for (const Decl *D : TargetDecls)
       CanonicalTargets.insert(D->getCanonicalDecl());
   }
 
   std::vector<Reference> take() && {
     llvm::sort(References, [](const Reference &L, const Reference &R) {
-      return std::tie(L.Loc, L.CanonicalTarget, L.Role) <
-             std::tie(R.Loc, R.CanonicalTarget, R.Role);
+      return std::tie(L.Loc, L.Role) < std::tie(R.Loc, R.Role);
     });
     // We sometimes see duplicates when parts of the AST get traversed twice.
-    References.erase(
-        std::unique(References.begin(), References.end(),
+    References.erase(std::unique(References.begin(), References.end(),
                                  [](const Reference &L, const Reference &R) {
-                      return std::tie(L.CanonicalTarget, L.Loc, L.Role) ==
-                             std::tie(R.CanonicalTarget, R.Loc, R.Role);
+                                   return std::tie(L.Loc, L.Role) ==
+                                          std::tie(R.Loc, R.Role);
                                  }),
                      References.end());
     return std::move(References);
   }
 
   bool
   handleDeclOccurence(const Decl *D, index::SymbolRoleSet Roles,
                       llvm::ArrayRef<index::SymbolRelation> Relations,
                       SourceLocation Loc,
                       index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
     assert(D->isCanonicalDecl() && "expect D to be a canonical declaration");
     const SourceManager &SM = AST.getSourceManager();
     Loc = SM.getFileLoc(Loc);
     if (isInsideMainFile(Loc, SM) && CanonicalTargets.count(D))
-      References.push_back({D, Loc, Roles});
+      References.push_back({Loc, Roles});
     return true;
   }
 
 private:
   llvm::SmallSet<const Decl *, 4> CanonicalTargets;
   std::vector<Reference> References;
   const ASTContext &AST;
 };

 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
                                                       Position Pos) {
   const SourceManager &SM = AST.getSourceManager();
   auto Symbols = getSymbolAtPosition(
       AST, getBeginningOfIdentifier(AST, Pos, SM.getMainFileID()));
   // FIXME: show references to macro within file?
   auto References = findRefs(Symbols.Decls, AST);
 
+  // FIXME: we may get multiple DocumentHighlights with the same location and
+  // different kinds, deduplicate them.
   std::vector<DocumentHighlight> Result;
   for (const auto &Ref : References) {
     if (auto Range =
             getTokenRange(AST.getASTContext().getSourceManager(),
                           AST.getASTContext().getLangOpts(), Ref.Loc)) {
       DocumentHighlight DH;
       DH.range = *Range;
       if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write))
if (!MainFilePath) {
     return Results;
   }
   auto Loc = getBeginningOfIdentifier(AST, Pos, SM.getMainFileID());
   auto Symbols = getSymbolAtPosition(AST, Loc);
 
   // We traverse the AST to find references in the main file.
   // TODO: should we handle macros, too?
   auto MainFileRefs = findRefs(Symbols.Decls, AST);
+  // We may get multiple refs with the same location and different Roles, as
+  // cross-reference is only interested in locations, we deduplicate them
+  // by the location to avoid emitting duplicated locations.
+  MainFileRefs.erase(std::unique(MainFileRefs.begin(), MainFileRefs.end(),
+                                 [](const ReferenceFinder::Reference &L,
+                                    const ReferenceFinder::Reference &R) {
+                                   return L.Loc == R.Loc;
+                                 }),
+                     MainFileRefs.end());
   for (const auto &Ref : MainFileRefs) {
     if (auto Range =
             getTokenRange(AST.getASTContext().getSourceManager(),
                           AST.getASTContext().getLangOpts(), Ref.Loc)) {
       Location Result;
       Result.range = *Range;
       Result.uri = URIForFile::canonicalize(*MainFilePath, *MainFilePath);
       Results.push_back(std::move(Result));

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

EXPECT_THAT(findReferences(AST, T.point(), 0),
                 ElementsAreArray(ExpectedLocations))
         << Test;
   }
 }
 
 TEST(FindReferences, ExplicitSymbols) {
   const char *Tests[] = {
       R"cpp(
-      struct Foo { Foo* [self]() const; };
+      struct Foo { Foo* [[self]]() const; };
       void f() {
-        if (Foo* T = foo.[^self]()) {} // Foo member call expr.
+        Foo foo;
+        if (Foo* T = foo.[[^self]]()) {} // Foo member call expr.
       }
       )cpp",
 
       R"cpp(
       struct Foo { Foo(int); };
       Foo f() {
-        int [b];
-        return [^b]; // Foo constructor expr.
+        int [[b]];
+        return [[^b]]; // Foo constructor expr.
       }
       )cpp",
 
       R"cpp(
       struct Foo {};
       void g(Foo);
-      Foo [f]();
+      Foo [[f]]();
       void call() {
-        g([^f]());  // Foo constructor expr.
+        g([[^f]]());  // Foo constructor expr.
       }
       )cpp",
 
       R"cpp(
-      void [foo](int);
-      void [foo](double);
+      void [[foo]](int);
+      void [[foo]](double);
 
       namespace ns {
-      using ::[fo^o];
+      using ::[[fo^o]];
       }
       )cpp",
   };
   for (const char *Test : Tests) {
     Annotations T(Test);
     auto AST = TestTU::withCode(T.code()).build();
     std::vector<Matcher<Location>> ExpectedLocations;
     for (const auto &R : T.ranges())
       ExpectedLocations.push_back(RangeIs(R));
+    ASSERT_THAT(ExpectedLocations, Not(IsEmpty()));
     EXPECT_THAT(findReferences(AST, T.point(), 0),
                 ElementsAreArray(ExpectedLocations))
         << Test;
   }
 }
 
 TEST(FindReferences, NeedsIndex) {
   const char *Header = "int foo();";