[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

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.

101

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?

132

Maybe simplify to Decls[D] |= IsExplicitReferenced?

139

NIT: use early exits by inverting condition

[hokein]

Address review comments.

[ilya-biryukov]

clangd/XRefs.cpp

101

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?

298–299

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

299

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

[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

71

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).

101

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.

132

Good point!

299

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

[ilya-biryukov]

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

clangd/XRefs.cpp

101

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

141

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

[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.

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(raw_ostream &OS,
                              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(
       llvm::errs(), 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()};
 }
 
 llvm::Optional<Location>
 makeLocation(ParsedAST &AST, const SourceRange &ValSourceRange) {
   const SourceManager &SourceMgr = AST.getASTContext().getSourceManager();
   const LangOptions &LangOpts = AST.getASTContext().getLangOpts();
   SourceLocation LocStart = ValSourceRange.getBegin();
 
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, SourceRange(Loc, 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;

 
 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
                                                       Position Pos) {
   const SourceManager &SourceMgr = AST.getASTContext().getSourceManager();
   SourceLocation SourceLocationBeg =
       getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID());
 
   auto Symbols = getSymbolAtPosition(AST, SourceLocationBeg);
-  std::vector<const Decl *> SelectedDecls = Symbols.Decls;
+  std::vector<const Decl *> SelectedDecls;
+  for (const auto &DI : Symbols.Decls)
+    SelectedDecls.push_back(DI.D);
 
   DocumentHighlightsFinder DocHighlightsFinder(
       llvm::errs(), AST.getASTContext(), AST.getPreprocessor(), SelectedDecls);
 
   index::IndexingOptions IndexOpts;
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::All;
   IndexOpts.IndexFunctionLocals = true;
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;
 }
 
 } // namespace clangd
 } // namespace clang

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"