Go-to-type on smart_ptr<Foo> now also shows Foo

[tom-anders]

Summary

Fixes clangd/clangd#1026

[tom-anders]

clang-tools-extra/clangd/HeuristicResolver.h

75

Not sure if it's the right call to make this public? The documentation needs to be adapted at least I think

[sammccall]

Thanks! I just have a question if this behavior should be even "stronger":

In most editors, if you return one result you go straight there, if you return two results you get a menu.
A menu is significantly worse than going straight to the right result - the UI is clunkier and the choice interrupts your workflow.

So my question is, do you think that we should *only* return the pointee in these cases?

(It's possible to change this later, but I'd like to take a reasonable guess as this is forcing an API change from Type -> vector<Type>)
cc @kadircet

[sammccall]

clang-tools-extra/clangd/HeuristicResolver.h

75

It's a bit unfortunate that it doesn't fit the usual pattern of "resolve the target of this AST node", but it's fairly closely related, it needs to use the Ctx in the same way, and it's already implemented here... I think it's OK (at least I can't see a better alternative).

We should probably have a unit test for it though.

[sammccall]

Sorry, I didn't mean to accept yet - wanted some discussion on behavior & probably a unittest for the newly-public function.

[tom-anders]

In D128826#3619167, @sammccall wrote:

Thanks! I just have a question if this behavior should be even "stronger":

In most editors, if you return one result you go straight there, if you return two results you get a menu.
A menu is significantly worse than going straight to the right result - the UI is clunkier and the choice interrupts your workflow.

So my question is, do you think that we should *only* return the pointee in these cases?

(It's possible to change this later, but I'd like to take a reasonable guess as this is forcing an API change from Type -> vector<Type>)
cc @kadircet

I'm using this with neovim's builtin LSP, where when there are multiple results it takes me to the first one, and also opens the quickfix window that shows all results. But I can see how the current implementation could be annoying with other editors.

So here's what I thought: Say you have a variable that's a smart pointer and trigger textDocument/typeDefinition on it and there's only a single result that takes you straight to the type. In this case, you might not even know that the type is actually wrapped inside a smart pointer and might make wrong assumptions about the code. Of course you could've done a Hover beforehand, but in the case where there are 2 results, you don't need that extra step.

Maybe it would be best to make this configurable via the config file? Since most people are using "most editors", I think taking you straight to the type would be better, but I'm really not sure.

Btw, I think it would be useful to extend this feature to not only smart pointers, but also containers like std::vector. Then there'd also be the question what would happen for std::vector<std::unique_ptr<T>>: should there be 1, 2 or 3 results?

[sammccall]

TL;DR: I'm convinced that this patch (return multiple locations) is a good choice. Also talked to Kadir offline.

In D128826#3619339, @tom-anders wrote:

I'm using this with neovim's builtin LSP, where when there are multiple results it takes me to the first one, and also opens the quickfix window that shows all results. But I can see how the current implementation could be annoying with other editors.

(Interesting, I'm using the same and find it annoying: it focuses the quickfix window and that's disruptive enough that I never noticed the cursor also moved. But https://github.com/neovim/neovim/pull/14878 lists some workarounds)

So here's what I thought: Say you have a variable that's a smart pointer and trigger textDocument/typeDefinition on it and there's only a single result that takes you straight to the type. In this case, you might not even know that the type is actually wrapped inside a smart pointer and might make wrong assumptions about the code. Of course you could've done a Hover beforehand, but in the case where there are 2 results, you don't need that extra step.

Yeah. There's no guarantee the type in question is well-represented by a decl, but this is a bit confusing.
I think it might still be worth it for specific types like unique_ptr<Foo>, but for vector<Foo> it's too surprising even if you want Foo 99% of the time.

Maybe it would be best to make this configurable via the config file? Since most people are using "most editors", I think taking you straight to the type would be better, but I'm really not sure.

Making it configurable doesn't actually solve the problem: we still need to think hard about what the best default is, because relatively few users ever configure anything.
So let's not rule it out, but there's not much point doing it in this patch.

Btw, I think it would be useful to extend this feature to not only smart pointers, but also containers like std::vector. Then there'd also be the question what would happen for std::vector<std::unique_ptr<T>>: should there be 1, 2 or 3 results?

Yeah I find this pretty compelling. I think we should start with the approach in this patch, returning {pointer, pointee}, and iterate from there (add containers, or templates in general, or omit the pointer type in certain special cases...).

clang-tools-extra/clangd/XRefs.cpp

1913–1914

Ergonomically I might prefer void unwrapFindType(QualType, ..., vector<QualType>& Out) or so.
This tends to compose a bit better IMO by making all the cases look similar whether you're adding one type or several or combining lists.

You can still return Out.push_back(T) etc on a single line.

1916

I think we want to return 0 types in this case

1974

(if you modify unwrap above to not return null, you can skip this check)

1975

we now have the potential for duplicates (already in this patch in fact: unique_ptr<unique_ptr<int>>.

Deduplicating types isn't that useful (unique_ptr<unique_ptr<int>> != unique_ptr<int>), I guess it's either deduplicate locations or allow the duplicates.
If you choose to allow them, probably worth a comment why.

[tom-anders]

In D128826#3619339, @tom-anders wrote:

I'm using this with neovim's builtin LSP, where when there are multiple results it takes me to the first one, and also opens the quickfix window that shows all results. But I can see how the current implementation could be annoying with other editors.

(Interesting, I'm using the same and find it annoying: it focuses the quickfix window and that's disruptive enough that I never noticed the cursor also moved. But https://github.com/neovim/neovim/pull/14878 lists some workarounds)

(Ah, I also forgot that I'm not actually using quickfix, but rather https://github.com/folke/trouble.nvim, which also gets focused but has a preview feature)

So here's what I thought: Say you have a variable that's a smart pointer and trigger textDocument/typeDefinition on it and there's only a single result that takes you straight to the type. In this case, you might not even know that the type is actually wrapped inside a smart pointer and might make wrong assumptions about the code. Of course you could've done a Hover beforehand, but in the case where there are 2 results, you don't need that extra step.

Yeah. There's no guarantee the type in question is well-represented by a decl, but this is a bit confusing.
I think it might still be worth it for specific types like unique_ptr<Foo>, but for vector<Foo> it's too surprising even if you want Foo 99% of the time.

Right, maybe it would make sense to go straight to T for declarations, but include smart_ptr when it's used in an expression? But that's something for a follow-up patch.

Maybe it would be best to make this configurable via the config file? Since most people are using "most editors", I think taking you straight to the type would be better, but I'm really not sure.

Making it configurable doesn't actually solve the problem: we still need to think hard about what the best default is, because relatively few users ever configure anything.
So let's not rule it out, but there's not much point doing it in this patch.

Btw, I think it would be useful to extend this feature to not only smart pointers, but also containers like std::vector. Then there'd also be the question what would happen for std::vector<std::unique_ptr<T>>: should there be 1, 2 or 3 results?

Yeah I find this pretty compelling. I think we should start with the approach in this patch, returning {pointer, pointee}, and iterate from there (add containers, or templates in general, or omit the pointer type in certain special cases...).

Agreed. The heuristic there would be "template class with at least 1 type parameter, where all other parameters except the first have a default value", right?
But maybe it even makes sense for stuff like std::map, so it's more like "template class, with n>0 type template parameters, followed by m>=0 defaulted template parameters"
Do we already have an issue for this? If not, I'd open a new one.

[tom-anders]

clang-tools-extra/clangd/HeuristicResolver.h

75

Not really sure where to put the unit test, probably FindTargetTests.cpp? It looks like it tests HeuristicResolver implicitly. Couldn't find anything that tests HeuristicResolver directly.

clang-tools-extra/clangd/XRefs.cpp

1913–1914

Ah yes that makes sense. Didn't think about the return Out.push_back(T) trick to keep using early returns, thought I'd have to add a ton of else ifs instead.

1975

Not sure about this either. I'll go with not deduplicating and adding a comment for now.

[tom-anders]

clang-tools-extra/clangd/XRefs.cpp

1913–1914

It makes the call side a bit uglier though - Is it okay to add a convenience wrapper vector<QualType> unwrapFindType(QualType, HeuristicResolver*) that forwards to the overload that uses the out-parameter?

[sammccall]

LG, just nits you know of outstanding and I think no extra tests needed.

In D128826#3619956, @tom-anders wrote:

So here's what I thought: Say you have a variable that's a smart pointer and trigger textDocument/typeDefinition on it and there's only a single result that takes you straight to the type. In this case, you might not even know that the type is actually wrapped inside a smart pointer and might make wrong assumptions about the code. Of course you could've done a Hover beforehand, but in the case where there are 2 results, you don't need that extra step.

Yeah. There's no guarantee the type in question is well-represented by a decl, but this is a bit confusing.
I think it might still be worth it for specific types like unique_ptr<Foo>, but for vector<Foo> it's too surprising even if you want Foo 99% of the time.

Right, maybe it would make sense to go straight to T for declarations, but include smart_ptr when it's used in an expression? But that's something for a follow-up patch.

Hmm, is the distinction that the type is written in the declaration (not auto)? I'm not sure it's worth specializing behavior for that scenario too much, when it's not too hard to go-to-definition on the specific token you want.
The chance of guessing right has to be weighed against keeping the behavior predictable and comprehensible...

Agreed. The heuristic there would be "template class with at least 1 type parameter, where all other parameters except the first have a default value", right?
But maybe it even makes sense for stuff like std::map, so it's more like "template class, with n>0 type template parameters, followed by m>=0 defaulted template parameters"

Right, if we have type template parameters we should offer them in addition to the template.

Defaulted is tricky, actually. (And important for stuff like container allocators and string traits).

• the type sometimes has "as-written" sugar which will tell you the spelled args, but the spelled form isn't that interesting when you can't see the spelling (and sometimes the sugar is missing entirely)
• TypePrinter has some logic to determine whether the template arg is equivalent to the default (isSubstitutedDefaultArgument in TypePrinter.cpp), but would need some refactoring to expose it
• the simplistic option is just to suppress a template arg if the parameter has a default (without checking whether it is default or not). In the common case this is correct, in the uncommon case it is conservative.

Do we already have an issue for this? If not, I'd open a new one.

I don't think so, the bug you found is the closest we have.

clang-tools-extra/clangd/HeuristicResolver.h

75

Oh you're right - we don't have direct tests :-\
Well, this function already exists and we already have some indirect tests, let's just leave it as-is.

clang-tools-extra/clangd/XRefs.cpp

1913–1914

Just the final call, not the recursive calls, right? They can be return unwrapFindType(...); too.

It doesn't look ugly to me (2 extra lines at one callsite) but up to you.

[tom-anders]

In D128826#3619956, @tom-anders wrote:

So here's what I thought: Say you have a variable that's a smart pointer and trigger textDocument/typeDefinition on it and there's only a single result that takes you straight to the type. In this case, you might not even know that the type is actually wrapped inside a smart pointer and might make wrong assumptions about the code. Of course you could've done a Hover beforehand, but in the case where there are 2 results, you don't need that extra step.

Yeah. There's no guarantee the type in question is well-represented by a decl, but this is a bit confusing.
I think it might still be worth it for specific types like unique_ptr<Foo>, but for vector<Foo> it's too surprising even if you want Foo 99% of the time.

Right, maybe it would make sense to go straight to T for declarations, but include smart_ptr when it's used in an expression? But that's something for a follow-up patch.

Hmm, is the distinction that the type is written in the declaration (not auto)? I'm not sure it's worth specializing behavior for that scenario too much, when it's not too hard to go-to-definition on the specific token you want.
The chance of guessing right has to be weighed against keeping the behavior predictable and comprehensible...

Yes that's what I meant, but I agree with you here.

clang-tools-extra/clangd/XRefs.cpp

1913–1914

Yeah just the final call. I just don't like adding (non-const) helper variables on the call site.

[tom-anders]

• Remove obsolete comment
• Return empty vector when type isNull()
• Add comment about why we don't deduplicate results
• Use out-parameter in unwrapFindType to make structure more consistent

[tom-anders]

@sammccall I think you can merge this for me now (and also https://reviews.llvm.org/D128202)

[sammccall]

In D128826#3641093, @tom-anders wrote:

@sammccall I think you can merge this for me now (and also https://reviews.llvm.org/D128202)

Done, sorry for the delay.

FWIW I think you should be able to get commit access at this point, if you want it.
Cheers, Sam

clang-tools-extra/clangd/HeuristicResolver.h

std::vector<const NamedDecl *> resolveTemplateSpecializationType(
       const DependentTemplateSpecializationType *DTST) const;
 
   // Try to heuristically resolve a dependent nested name specifier
   // to the type it likely denotes. Note that *dependent* name specifiers always
   // denote types, not namespaces.
   const Type *
   resolveNestedNameSpecifierToType(const NestedNameSpecifier *NNS) const;
 
+  // Given the type T of a dependent expression that appears of the LHS of a
+  // "->", heuristically find a corresponding pointee type in whose scope we
+  // could look up the name appearing on the RHS.
+  const Type *getPointeeType(const Type *T) const;
+
 private:
   ASTContext &Ctx;
 
   // Given a tag-decl type and a member name, heuristically resolve the
   // name to one or more declarations.
   // The current heuristic is simply to look up the name in the primary
   // template. This is a heuristic because the template could potentially
   // have specializations that declare different members.
   // Multiple declarations could be returned if the name is overloaded
   // (e.g. an overloaded method in the primary template).
   // This heuristic will give the desired answer in many cases, e.g.
   // for a call to vector<T>::size().
   std::vector<const NamedDecl *> resolveDependentMember(
       const Type *T, DeclarationName Name,
       llvm::function_ref<bool(const NamedDecl *ND)> Filter) const;
 
   // Try to heuristically resolve the type of a possibly-dependent expression
   // `E`.
   const Type *resolveExprToType(const Expr *E) const;
   std::vector<const NamedDecl *> resolveExprToDecls(const Expr *E) const;
-
-  // Given the type T of a dependent expression that appears of the LHS of a
-  // "->", heuristically find a corresponding pointee type in whose scope we
-  // could look up the name appearing on the RHS.
-  const Type *getPointeeType(const Type *T) const;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/XRefs.cpp

 //===--- XRefs.cpp -----------------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "XRefs.h"
 #include "AST.h"
 #include "FindSymbols.h"
 #include "FindTarget.h"
+#include "HeuristicResolver.h"
 #include "ParsedAST.h"
 #include "Protocol.h"
 #include "Quality.h"
 #include "Selection.h"
 #include "SourceCode.h"
 #include "URI.h"
 #include "index/Index.h"
 #include "index/Merge.h"
struct Visitor : ConstStmtVisitor<Visitor, QualType> {
       }
     } V;
     return V.Visit(S);
   }
 
   return QualType();
 }
 
-// Given a type targeted by the cursor, return a type that's more interesting
+// Given a type targeted by the cursor, return one or more types that are more interesting
 // to target.
-static QualType unwrapFindType(QualType T) {
+static void unwrapFindType(
+    QualType T, const HeuristicResolver* H, llvm::SmallVector<QualType>& Out) {
   if (T.isNull())
-    return T;
+    return;
 
   // If there's a specific type alias, point at that rather than unwrapping.
   if (const auto* TDT = T->getAs<TypedefType>())
-    return QualType(TDT, 0);
+    return Out.push_back(QualType(TDT, 0));
 
   // Pointers etc => pointee type.
   if (const auto *PT = T->getAs<PointerType>())
-    return unwrapFindType(PT->getPointeeType());
+    return unwrapFindType(PT->getPointeeType(), H, Out);
   if (const auto *RT = T->getAs<ReferenceType>())
-    return unwrapFindType(RT->getPointeeType());
+    return unwrapFindType(RT->getPointeeType(), H, Out);
   if (const auto *AT = T->getAsArrayTypeUnsafe())
-    return unwrapFindType(AT->getElementType());
-  // FIXME: use HeuristicResolver to unwrap smart pointers?
+    return unwrapFindType(AT->getElementType(), H, Out);
 
   // Function type => return type.
   if (auto *FT = T->getAs<FunctionType>())
-    return unwrapFindType(FT->getReturnType());
+    return unwrapFindType(FT->getReturnType(), H, Out);
   if (auto *CRD = T->getAsCXXRecordDecl()) {
     if (CRD->isLambda())
-      return unwrapFindType(CRD->getLambdaCallOperator()->getReturnType());
+      return unwrapFindType(CRD->getLambdaCallOperator()->getReturnType(), H, Out);
     // FIXME: more cases we'd prefer the return type of the call operator?
     //        std::function etc?
   }
 
-  return T;
+  // For smart pointer types, add the underlying type
+  if (H)
+    if (const auto* PointeeType = H->getPointeeType(T.getNonReferenceType().getTypePtr())) {
+        unwrapFindType(QualType(PointeeType, 0), H, Out);
+        return Out.push_back(T);
+    }
+
+  return Out.push_back(T);
+}
+
+// Convenience overload, to allow calling this without the out-parameter
+static llvm::SmallVector<QualType> unwrapFindType(
+    QualType T, const HeuristicResolver* H) {
+    llvm::SmallVector<QualType> Result;
+    unwrapFindType(T, H, Result);
+    return Result;
 }
 
+
 std::vector<LocatedSymbol> findType(ParsedAST &AST, Position Pos) {
   const SourceManager &SM = AST.getSourceManager();
   auto Offset = positionToOffset(SM.getBufferData(SM.getMainFileID()), Pos);
   std::vector<LocatedSymbol> Result;
   if (!Offset) {
     elog("failed to convert position {0} for findTypes: {1}", Pos,
          Offset.takeError());
     return Result;
   }
   // The general scheme is: position -> AST node -> type -> declaration.
   auto SymbolsFromNode =
       [&AST](const SelectionTree::Node *N) -> std::vector<LocatedSymbol> {
-    QualType Type = unwrapFindType(typeForNode(N));
-    if (Type.isNull())
-      return {};
-    return locateSymbolForType(AST, Type);
+    std::vector<LocatedSymbol> LocatedSymbols;
+
+    // NOTE: unwrapFindType might return duplicates for something like
+    // unique_ptr<unique_ptr<T>>. Let's *not* remove them, because it gives you some
+    // information about the type you may have not known before
+    // (since unique_ptr<unique_ptr<T>> != unique_ptr<T>).
+    for (const QualType& Type : unwrapFindType(typeForNode(N), AST.getHeuristicResolver()))
+        llvm::copy(locateSymbolForType(AST, Type), std::back_inserter(LocatedSymbols));
+
+    return LocatedSymbols;
   };
   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), *Offset,
                             *Offset, [&](SelectionTree ST) {
                               Result = SymbolsFromNode(ST.commonAncestor());
                               return !Result.empty();
                             });
   return Result;
 }

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

EXPECT_THAT(
       findImplementations(AST, Code.point(), TU.index().get()),
       UnorderedElementsAre(sym("Foo", Code.range("Decl"), Code.range("Def")),
                            sym("Foo", Code.range("Child2"), llvm::None)))
       << Test;
 }
 
 TEST(FindType, All) {
   Annotations HeaderA(R"cpp(
-    struct [[Target]] { operator int() const; };
+    struct $Target[[Target]] { operator int() const; };
     struct Aggregate { Target a, b; };
     Target t;
 
-    template <typename T> class smart_ptr {
+    template <typename T> class $smart_ptr[[smart_ptr]] {
       T& operator*();
       T* operator->();
       T* get();
     };
   )cpp");
   auto TU = TestTU::withHeaderCode(HeaderA.code());
   for (const llvm::StringRef Case : {
            "str^uct Target;",
for (const llvm::StringRef Case : {
        }) {
     Annotations A(Case);
     TU.Code = A.code().str();
     ParsedAST AST = TU.build();
 
     ASSERT_GT(A.points().size(), 0u) << Case;
     for (auto Pos : A.points())
       EXPECT_THAT(findType(AST, Pos),
-                  ElementsAre(sym("Target", HeaderA.range(), HeaderA.range())))
+                  ElementsAre(
+                    sym("Target", HeaderA.range("Target"), HeaderA.range("Target"))))
           << Case;
   }
 
-  // FIXME: We'd like these cases to work. Fix them and move above.
   for (const llvm::StringRef Case : {
            "smart_ptr<Target> ^tsmart;",
        }) {
     Annotations A(Case);
     TU.Code = A.code().str();
     ParsedAST AST = TU.build();
 
     EXPECT_THAT(findType(AST, A.point()),
-                Not(Contains(sym("Target", HeaderA.range(), HeaderA.range()))))
+                UnorderedElementsAre(
+                  sym("Target", HeaderA.range("Target"), HeaderA.range("Target")),
+                  sym("smart_ptr", HeaderA.range("smart_ptr"), HeaderA.range("smart_ptr"))
+                ))
         << Case;
   }
 }
 
 void checkFindRefs(llvm::StringRef Test, bool UseIndex = false) {
   Annotations T(Test);
   auto TU = TestTU::withCode(T.code());
   TU.ExtraArgs.push_back("-std=c++20");