[clangd] Sort GoToDefinition results.

[hokein]

Summary

GoToDefinition returns all declaration results (implicit/explicit) that are
in the same location, and the results are returned in arbitrary order.

Some LSP clients defaultly take the first result as the final result, which
might present a bad result (implicit decl) to users.

this patch ranks the result based on whether the declarations are
referenced explicitly/implicitly. We put explicit declarations first.

This also improve the "hover" (which just take the first result) feature
in some cases.

[ilya-biryukov]

clangd/XRefs.cpp

71 ↗

(On Diff #159684)

NIT: maybe call Occurence instead? As this is actually a Decl with some extra data, computed based on the expression it originated from. Occurence seems like a nice that for that kind of thing.

105 ↗

(On Diff #159684)

Maybe sort further at the callers instead?
It would be a more intrusive change, but would also give a well-defined result order for findDefinitions and other cases. E.g. findDefinitions currently gives results in an arbitrary order (specifically, the one supplied by DenseMap+sort) when multiple decls are returned.
WDYT?

128 ↗

(On Diff #159684)

Maybe simplify to Decls[D] |= IsExplicitReferenced?

143 ↗

(On Diff #159684)

NIT: use early exits by inverting condition

[hokein]

Address review comments.

[ilya-biryukov]

clangd/XRefs.cpp

296 ↗

(On Diff #160544)

Maybe use explicit type here? Using 'auto' is a bit confusing.

297 ↗

(On Diff #160544)

Maybe use explicit type here too or rename the field from 'D' to something more descriptive (e.g. Decl )?

105 ↗

(On Diff #159684)

Just to clarify the original suggestion.

Maybe we can sort the (location, is_explicit) pairs instead of the (decl, is_explicit) pairs?
Sorting based on pointer equality (see L.D < R.D) provides non-deterministic results and we can have fully deterministic order on locations.

DeclarationAndMacrosFinder can return the results in arbitrary orders and the client code would be responsible for getting locations and finally sorting them.
WDYT?

[ilya-biryukov]

Sorry for the delays with this review

[hokein]

Address review comments, return deterministic results.

[hokein]

Sorry, I just realized I didn't reply the comments in the first review (they were in my draft).

clangd/XRefs.cpp

297 ↗

(On Diff #160544)

use explicit type here (I avoided using Decl as a variable name, because Decl is a type name in clang already).

71 ↗

(On Diff #159684)

I'm not sure what's a good name here, but I think we'd better avoid using Occurrence, because this term is used by xrefs (and we will have xrefs implementation in this file).

105 ↗

(On Diff #159684)

I think we'd better sort them in DeclarationAndMacrosFinder -- because we have a few clients in XRefs.cpp using this class, and it seems that they don't have their specific needs for sorting, having them sorting results seems unnecessary.

128 ↗

(On Diff #159684)

Good point!

[ilya-biryukov]

LG, thanks.
And a question of what are the things we can accidentally misdetect as explicit

clangd/XRefs.cpp

141 ↗

(On Diff #163311)

Do we know which cases break? Just wondering is there are more reliable ways to handle those cases?

105 ↗

(On Diff #159684)

That LG, as long as we have a deterministic order, we should be fine

[ilya-biryukov]

@hokein, would it be fine if I submit this change for you?
It would be nice to get this fix in before you get back from vacation.

[hokein]

In D50438#1224287, @ilya-biryukov wrote:

@hokein, would it be fine if I submit this change for you?
It would be nice to get this fix in before you get back from vacation.

Thanks, and sorry for the delay here, I was planning to submit it after D50958 is submitted (probably today?)-- because it requires some rebasing changes.

[ilya-biryukov]

In D50438#1224289, @hokein wrote:>

Thanks, and sorry for the delay here, I was planning to submit it after D50958 is submitted (probably today?)-- because it requires some rebasing changes.

Thanks for the update and sorry for disturbing on your leave time. If you want, happy to rebase and land this after D50958 is submitted (just so that you can enjoy your leave without further disturbance ;-))

[hokein]

Rebase to master.

[hokein]

Fix code style.

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

llvm::Optional<Location> toLSPLocation(const SymbolLocation &Loc,
   return LSPLoc;
 }
 
 struct MacroDecl {
   StringRef Name;
   const MacroInfo *Info;
 };
 
+struct DeclInfo {
+  const Decl *D;
+  // Indicates the declaration is referenced by an explicit AST node.
+  bool IsReferencedExplicitly = false;
+};
+
 /// Finds declarations locations that a given source location refers to.
 class DeclarationAndMacrosFinder : public index::IndexDataConsumer {
-  std::vector<const Decl *> Decls;
   std::vector<MacroDecl> MacroInfos;
+  // The value of the map indicates whether the declaration has been referenced
+  // explicitly in the code.
+  // True means the declaration is explicitly referenced at least once; false
+  // otherwise.
+  llvm::DenseMap<const Decl *, bool> Decls;
   const SourceLocation &SearchedLocation;
   const ASTContext &AST;
   Preprocessor &PP;
 
 public:
   DeclarationAndMacrosFinder(const SourceLocation &SearchedLocation,
                              ASTContext &AST, Preprocessor &PP)
       : SearchedLocation(SearchedLocation), AST(AST), PP(PP) {}
 
-  std::vector<const Decl *> takeDecls() {
-    // Don't keep the same declaration multiple times.
-    // This can happen when nodes in the AST are visited twice.
-    std::sort(Decls.begin(), Decls.end());
-    auto Last = std::unique(Decls.begin(), Decls.end());
-    Decls.erase(Last, Decls.end());
-    return std::move(Decls);
+  // Get all DeclInfo of the found declarations.
+  // The results are sorted by "IsReferencedExplicitly" and declaration
+  // location.
+  std::vector<DeclInfo> getFoundDecls() const {
+    std::vector<DeclInfo> Result;
+    for (auto It : Decls) {
+      Result.emplace_back();
+      Result.back().D = It.first;
+      Result.back().IsReferencedExplicitly = It.second;
+    }
+
+    // Sort results. Declarations being referenced explicitly come first.
+    std::sort(Result.begin(), Result.end(),
+              [](const DeclInfo &L, const DeclInfo &R) {
+                if (L.IsReferencedExplicitly != R.IsReferencedExplicitly)
+                  return L.IsReferencedExplicitly > R.IsReferencedExplicitly;
+                return L.D->getBeginLoc() < R.D->getBeginLoc();
+              });
+    return Result;
   }
 
   std::vector<MacroDecl> takeMacroInfos() {
     // Don't keep the same Macro info multiple times.
     std::sort(MacroInfos.begin(), MacroInfos.end(),
               [](const MacroDecl &Left, const MacroDecl &Right) {
                 return Left.Info < Right.Info;
               });
 
     auto Last = std::unique(MacroInfos.begin(), MacroInfos.end(),
                             [](const MacroDecl &Left, const MacroDecl &Right) {
                               return Left.Info == Right.Info;
                             });
     MacroInfos.erase(Last, MacroInfos.end());
     return std::move(MacroInfos);
   }
 
   bool
   handleDeclOccurence(const Decl *D, index::SymbolRoleSet Roles,
                       ArrayRef<index::SymbolRelation> Relations,
                       SourceLocation Loc,
                       index::IndexDataConsumer::ASTNodeInfo ASTNode) override {
     if (Loc == SearchedLocation) {
+      // Check whether the E has an implicit AST node (e.g. ImplicitCastExpr).
+      auto hasImplicitExpr = [](const Expr *E) {
+        if (!E || E->child_begin() == E->child_end())
+          return false;
+        // Use the first child is good enough for most cases -- normally the
+        // expression returned by handleDeclOccurence contains exactly one
+        // child expression.
+        const auto *FirstChild = *E->child_begin();
+        return llvm::isa<ExprWithCleanups>(FirstChild) ||
+               llvm::isa<MaterializeTemporaryExpr>(FirstChild) ||
+               llvm::isa<CXXBindTemporaryExpr>(FirstChild) ||
+               llvm::isa<ImplicitCastExpr>(FirstChild);
+      };
+
+      bool IsExplicit = !hasImplicitExpr(ASTNode.OrigE);
       // Find and add definition declarations (for GoToDefinition).
       // We don't use parameter `D`, as Parameter `D` is the canonical
       // declaration, which is the first declaration of a redeclarable
       // declaration, and it could be a forward declaration.
       if (const auto *Def = getDefinition(D)) {
-        Decls.push_back(Def);
+        Decls[Def] |= IsExplicit;
       } else {
         // Couldn't find a definition, fall back to use `D`.
-        Decls.push_back(D);
+        Decls[D] |= IsExplicit;
       }
     }
     return true;
   }
 
 private:
   void finish() override {
     // Also handle possible macro at the searched location.
if (!Lexer::getRawToken(Mgr.getSpellingLoc(SearchedLocation), Result, Mgr,
           assert(Decls.empty());
         }
       }
     }
   }
 };
 
 struct IdentifiedSymbol {
-  std::vector<const Decl *> Decls;
+  std::vector<DeclInfo> Decls;
   std::vector<MacroDecl> Macros;
 };
 
 IdentifiedSymbol getSymbolAtPosition(ParsedAST &AST, SourceLocation Pos) {
   auto DeclMacrosFinder = DeclarationAndMacrosFinder(Pos, AST.getASTContext(),
                                                      AST.getPreprocessor());
   index::IndexingOptions IndexOpts;
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::All;
   IndexOpts.IndexFunctionLocals = true;
   indexTopLevelDecls(AST.getASTContext(), AST.getLocalTopLevelDecls(),
                      DeclMacrosFinder, IndexOpts);
 
-  return {DeclMacrosFinder.takeDecls(), DeclMacrosFinder.takeMacroInfos()};
+  return {DeclMacrosFinder.getFoundDecls(), DeclMacrosFinder.takeMacroInfos()};
 }
 
 Range getTokenRange(ParsedAST &AST, SourceLocation TokLoc) {
   const SourceManager &SourceMgr = AST.getASTContext().getSourceManager();
   SourceLocation LocEnd = Lexer::getLocForEndOfToken(
       TokLoc, 0, SourceMgr, AST.getASTContext().getLangOpts());
   return {sourceLocToPosition(SourceMgr, TokLoc),
           sourceLocToPosition(SourceMgr, LocEnd)};
std::vector<Location> findDefinitions(ParsedAST &AST, Position Pos,
   //   3. Use the AST information to query the index, and populate the index
   //      location (if available).
   //   4. Return all populated locations for all symbols, definition first (
   //      which  we think is the users wants most often).
   struct CandidateLocation {
     llvm::Optional<Location> Def;
     llvm::Optional<Location> Decl;
   };
-  llvm::DenseMap<SymbolID, CandidateLocation> ResultCandidates;
+  // We respect the order in Symbols.Decls.
+  llvm::SmallVector<CandidateLocation, 8> ResultCandidates;
+  llvm::DenseMap<SymbolID, size_t> CandidatesIndex;
 
   // Emit all symbol locations (declaration or definition) from AST.
-  for (const auto *D : Symbols.Decls) {
+  for (const DeclInfo &DI : Symbols.Decls) {
+    const Decl *D = DI.D;
     // Fake key for symbols don't have USR (no SymbolID).
     // Ideally, there should be a USR for each identified symbols. Symbols
     // without USR are rare and unimportant cases, we use the a fake holder to
     // minimize the invasiveness of these cases.
     SymbolID Key("");
     if (auto ID = getSymbolID(D))
       Key = *ID;
 
-    auto &Candidate = ResultCandidates[Key];
+    auto R = CandidatesIndex.try_emplace(Key, ResultCandidates.size());
+    if (R.second) // new entry
+      ResultCandidates.emplace_back();
+    auto &Candidate = ResultCandidates[R.first->second];
+
     auto Loc = findNameLoc(D);
     auto L = makeLocation(AST, Loc);
     // The declaration in the identified symbols is a definition if possible
     // otherwise it is declaration.
     bool IsDef = getDefinition(D) == D;
     // Populate one of the slots with location for the AST.
     if (!IsDef)
       Candidate.Decl = L;
     else
       Candidate.Def = L;
   }
 
   if (Index) {
     LookupRequest QueryRequest;
     // Build request for index query, using SymbolID.
-    for (auto It : ResultCandidates)
+    for (auto It : CandidatesIndex)
       QueryRequest.IDs.insert(It.first);
     std::string HintPath;
     const FileEntry *FE =
         SourceMgr.getFileEntryForID(SourceMgr.getMainFileID());
     if (auto Path = getRealPath(FE, SourceMgr))
       HintPath = *Path;
     // Query the index and populate the empty slot.
-    Index->lookup(
-        QueryRequest, [&HintPath, &ResultCandidates](const Symbol &Sym) {
-          auto It = ResultCandidates.find(Sym.ID);
-          assert(It != ResultCandidates.end());
-          auto &Value = It->second;
+    Index->lookup(QueryRequest, [&HintPath, &ResultCandidates,
+                                 &CandidatesIndex](const Symbol &Sym) {
+      auto It = CandidatesIndex.find(Sym.ID);
+      assert(It != CandidatesIndex.end());
+      auto &Value = ResultCandidates[It->second];
 
-          if (!Value.Def)
-            Value.Def = toLSPLocation(Sym.Definition, HintPath);
-          if (!Value.Decl)
-            Value.Decl = toLSPLocation(Sym.CanonicalDeclaration, HintPath);
-        });
   }
 
   // Populate the results, definition first.
-  for (auto It : ResultCandidates) {
-    const auto &Candidate = It.second;
+  for (const auto &Candidate : ResultCandidates) {
     if (Candidate.Def)
       Result.push_back(*Candidate.Def);
     if (Candidate.Decl &&
         Candidate.Decl != Candidate.Def) // Decl and Def might be the same
       Result.push_back(*Candidate.Decl);
   }
 
   return Result;

 
 } // namespace
 
 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
                                                       Position Pos) {
   const SourceManager &SM = AST.getASTContext().getSourceManager();
   auto Symbols = getSymbolAtPosition(
       AST, getBeginningOfIdentifier(AST, Pos, SM.getMainFileID()));
-  auto References = findRefs(Symbols.Decls, AST);
+  std::vector<const Decl *> TargetDecls;
+  for (const DeclInfo &DI : Symbols.Decls) {
+    TargetDecls.push_back(DI.D);
+  }
+  auto References = findRefs(TargetDecls, AST);
 
   std::vector<DocumentHighlight> Result;
   for (const auto &Ref : References) {
     DocumentHighlight DH;
     DH.range = getTokenRange(AST, Ref.Loc);
     if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write))
       DH.kind = DocumentHighlightKind::Write;
     else if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Read))
SourceLocation SourceLocationBeg =
       getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID());
   // Identified symbols at a specific position.
   auto Symbols = getSymbolAtPosition(AST, SourceLocationBeg);
 
   if (!Symbols.Macros.empty())
     return getHoverContents(Symbols.Macros[0].Name);
 
   if (!Symbols.Decls.empty())
-    return getHoverContents(Symbols.Decls[0]);
+    return getHoverContents(Symbols.Decls[0].D);
 
   auto DeducedType = getDeducedType(AST, SourceLocationBeg);
   if (DeducedType && !DeducedType->isNull())
     return getHoverContents(*DeducedType, AST.getASTContext());
 
   return None;
 }
 
 std::vector<Location> findReferences(ParsedAST &AST, Position Pos,
                                      const SymbolIndex *Index) {
   std::vector<Location> Results;
   const SourceManager &SM = AST.getASTContext().getSourceManager();
   auto MainFilePath = getRealPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
   if (!MainFilePath) {
     elog("Failed to get a path for the main file, so no references");
     return Results;
   }
   auto Loc = getBeginningOfIdentifier(AST, Pos, SM.getMainFileID());
   auto Symbols = getSymbolAtPosition(AST, Loc);
 
+  std::vector<const Decl *> TargetDecls;
+  for (const DeclInfo &DI : Symbols.Decls) {
+    if (DI.IsReferencedExplicitly)
+      TargetDecls.push_back(DI.D);
+  }
+
   // We traverse the AST to find references in the main file.
   // TODO: should we handle macros, too?
-  auto MainFileRefs = findRefs(Symbols.Decls, AST);
+  auto MainFileRefs = findRefs(TargetDecls, AST);
   for (const auto &Ref : MainFileRefs) {
     Location Result;
     Result.range = getTokenRange(AST, Ref.Loc);
     Result.uri = URIForFile(*MainFilePath);
     Results.push_back(std::move(Result));
   }
 
   // Now query the index for references from other files.
   if (!Index)
     return Results;
   RefsRequest Req;
-  for (const Decl *D : Symbols.Decls) {
+  for (const Decl *D : TargetDecls) {
     // Not all symbols can be referenced from outside (e.g. function-locals).
     // TODO: we could skip TU-scoped symbols here (e.g. static functions) if
     // we know this file isn't a header. The details might be tricky.
     if (D->getParentFunctionOrMethod())
       continue;
     if (auto ID = getSymbolID(D))
       Req.IDs.insert(*ID);
   }

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

for (const char *Test : Tests) {
     for (const auto &R : T.ranges())
       ExpectedLocations.push_back(RangeIs(R));
     EXPECT_THAT(findDefinitions(AST, T.point()),
                 ElementsAreArray(ExpectedLocations))
         << Test;
   }
 }
 
+TEST(GoToDefinition, Rank) {
+  auto T = Annotations(R"cpp(
+    struct $foo1[[Foo]] {
+      $foo2[[Foo]]();
+      $foo3[[Foo]](Foo&&);
+      $foo4[[Foo]](const char*);
+    };
+
+    Foo $f[[f]]();
+
+    void $g[[g]](Foo foo);
+
+    void call() {
+      const char* $str[[str]] = "123";
+      Foo a = $1^str;
+      Foo b = Foo($2^str);
+      Foo c = $3^f();
+      $4^g($5^f());
+      g($6^str);
+    }
+  )cpp");
+  auto AST = TestTU::withCode(T.code()).build();
+  EXPECT_THAT(findDefinitions(AST, T.point("1")),
+              ElementsAre(RangeIs(T.range("str")), RangeIs(T.range("foo4"))));
+  EXPECT_THAT(findDefinitions(AST, T.point("2")),
+              ElementsAre(RangeIs(T.range("str"))));
+  EXPECT_THAT(findDefinitions(AST, T.point("3")),
+              ElementsAre(RangeIs(T.range("f")), RangeIs(T.range("foo3"))));
+  EXPECT_THAT(findDefinitions(AST, T.point("4")),
+              ElementsAre(RangeIs(T.range("g"))));
+  EXPECT_THAT(findDefinitions(AST, T.point("5")),
+              ElementsAre(RangeIs(T.range("f")), RangeIs(T.range("foo3"))));
+
+  auto DefinitionAtPoint6 = findDefinitions(AST, T.point("6"));
+  EXPECT_EQ(3ul, DefinitionAtPoint6.size());
+  EXPECT_THAT(DefinitionAtPoint6, HasSubsequence(RangeIs(T.range("str")),
+                                                 RangeIs(T.range("foo4"))));
+  EXPECT_THAT(DefinitionAtPoint6, HasSubsequence(RangeIs(T.range("str")),
+                                                 RangeIs(T.range("foo3"))));
+}
+
 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]];
 #include "header_not_in_preamble.h"