[clangd] Treat 'auto' params as deduced if there's a single instantiation.

[sammccall]

Summary

This makes hover/go-to-definition/expand-auto etc work for auto params in many
common cases.
This includes when a generic lambda is passed to a function accepting
std::function. (The tests don't use this case, it requires a lot of setup).

Note that this doesn't affect the AST of the function body itself, cause its
nodes not to be dependent, improve code completion etc.
(These sort of improvements seem possible, in a similar "if there's a single
instantiation, traverse it instead of the primary template" way).

Fixes https://github.com/clangd/clangd/issues/493
Fixes https://github.com/clangd/clangd/issues/1015

[avogelsgesang]

clang-tools-extra/clangd/AST.cpp

508

out of curiosity: when would this happen?

[sammccall]

clang-tools-extra/clangd/AST.cpp

508

I think it probably can't happen.
In principle there may be several sets of implicit TTPs in scope (generic lambda nested in generic lambda) but auto would always refer to the immediately enclosing set.

Added an assert, but I lack the courage to make this llvm_unreachable() and crash horribly in production if I'm wrong :-)

[sammccall]

Assert on presumed-impossible case.

[avogelsgesang]

code looks good to me, but I don't know the code base well enough for a "LGTM"

Thanks for implementing this!

[avogelsgesang]

Should this be added to the Release Notes?

[sammccall]

In D119537#3314509, @avogelsgesang wrote:

Should this be added to the Release Notes?

We usually go back over the git log around the time of a release cut.
It started as laziness but I think it's a good system: less work writing notes for stuff that doesn't end up landing, and gives us a chance to group and summarize related changes.

[sammccall]

And thanks for taking a look, and filing bugs - sorry we can't get to everything :-)

[nridge]

Very neat! A few minor suggestions but generally looks good.

clang-tools-extra/clangd/AST.cpp

519

Should we break in this case? Otherwise there could be an explicit specialization with a second type

545

Maybe call out an example like vector<auto> as a future nice-to-handle?

clang-tools-extra/clangd/unittests/tweaks/ExpandAutoTypeTests.cpp

88

Maybe add a conflicting-deduction case? (I know the GetDeducedType test already has one, but here it would be especially wrong.)

Also, should we perhaps disable this in header files (maybe excepting function-local symbols), since an including source file could have additional instantiations?

[Trass3r]

Is it intentional that the resolved type is not shown in the variable hover (I guess, looking at the code):

param payload
Type: const auto &

// In subscribe::(anonymous class)::operator()
const auto& payload

Only when hovering over auto?

type-alias auto
struct Foo

[sammccall]

address review comments

[sammccall]

In D119537#3323096, @Trass3r wrote:

Is it intentional that the resolved type is not shown in the variable hover (I guess, looking at the code):

param payload
Type: const auto &

// In subscribe::(anonymous class)::operator()
const auto& payload

Only when hovering over auto?

type-alias auto
struct Foo

Not intended per se but a limitation of the implementation approach: we do the analysis, but it's not feasible to track how the results would filter through the AST in general.
Maybe it's possible to do the easy+important cases, but this patch doesn't attempt it.

An alternative here is to have the selection walk the single instantiation, if there is one, instead of the template.
This is a more general/powerful approach.
I will try it out before landing this patch, but I suspect it'll cause some stuff to break in which case I'll move forward with this one.

clang-tools-extra/clangd/AST.cpp

519

I guess we're talking about this case:

void foo(auto X) {}
template <> void foo(char Y) {}
foo(0);

Now the meaning of the auto is tricky... if we're reading the body of the function, it's int. If we're reading the signature of foo it could be int or char. And obviously expand-auto-ing this into int would break the program.

I think it makes sense to be conservative and bail out if there are any explicit specializations for now. I expect this case to be rare.

On the other hand explicit instantiation is actually fine, so changed the condition here to fail on explicit specialization only.

545

Done. Note that clang currently rejects vector<auto>, AFAICT it's valid though.

clang-tools-extra/clangd/unittests/tweaks/ExpandAutoTypeTests.cpp

88

Maybe add a conflicting-deduction case? (I know the GetDeducedType test already has one, but here it would be especially wrong.)

Done.

Also, should we perhaps disable this in header files (maybe excepting function-local symbols), since an including source file could have additional instantiations?

Disabling features in headers seems sad. Detecting when the function is local doesn't seem like a great solution to this:

• it's going to be hard to detect the common ways functions are hidden within headers (detail namespaces, inaccessible members, ...)
• it's still going to be wrong when some instantiations come via (local) templates that are themselves instantiated from the including file

I suspect in most cases where multiple instantiations are intended we're going to see either no instantiations or many. Can we try it and see if there are false positive complaints?

[Trass3r]

clang-tools-extra/clangd/AST.cpp

491

Since this is implemented generically in the AST, can this functionality easily be reused for a type inlay hint?

[nridge]

clang-tools-extra/clangd/AST.cpp

545

Huh, on second look, it appears that vector<auto> is a feature that was dropped when merging the Concepts TS into C++20 (at least, I don't see anything in http://eel.is/c++draft/dcl.spec.auto that would allow it). GCC appears to support it as an extension.

clang-tools-extra/clangd/unittests/tweaks/ExpandAutoTypeTests.cpp

88

To clarify, I meant excepting only cases like this:

// header.hpp
void foo(std::function<void(ConcreteType)> callback);
void bar() {
  // We know this will only be instantiated with ConceteType,
  // regardless of what an including source file does
  foo([](auto x){});
}

but I'm sympathetic to the argument that neither false-positives (we offer a refactoring that breaks code) nor false-negative (we fail to offer a refactoring the user wants to make) are super impactful here and so we should do the easier thing (i.e. not try to restrict at all).

[sammccall]

clang-tools-extra/clangd/AST.cpp

491

In principle yes. Rather than expand the scope further, I'll send a followup patch.

clang-tools-extra/clangd/unittests/tweaks/ExpandAutoTypeTests.cpp

88

OK, will leave the checks out and see how it goes.

(I agree that's probably the most important case, but I haven't worked in a c++20 codebase so I don't know how abbreviated function templates will play out)

[sammccall]

BTW, D120131 demonstrates the other idea of actually using the instantiated AST instead of the template.
It's pretty cool but would need some refinement to be production-ready I suppose.

[sammccall]

D120258 is the followup with inlay hints.

It rearranges some of the code from this patch for reuse, and proposes dropping support for multiple instantiations yielding the same result, as this inevitably pushes complexity into each place this is used.

clang-tools-extra/clangd/AST.cpp

bool VisitDecltypeTypeLoc(DecltypeTypeLoc TL) {
     const DecltypeType *DT = dyn_cast<DecltypeType>(TL.getTypePtr());
     while (DT && !DT->getUnderlyingType().isNull()) {
       DeducedType = DT->getUnderlyingType();
       DT = dyn_cast<DecltypeType>(DeducedType.getTypePtr());
     }
     return true;
   }
 
+  // Handle functions/lambdas with `auto` typed parameters.
+  // We'll examine visible specializations and see if they yield a unique type.
+  bool VisitParmVarDecl(ParmVarDecl *PVD) {
+    if (!PVD->getType()->isDependentType())
+      return true;
+    // 'auto' here does not name an AutoType, but an implicit template param.
+    TemplateTypeParmTypeLoc Auto =
+        findContainedAutoTTPLoc(PVD->getTypeSourceInfo()->getTypeLoc());
+    if (Auto.isNull() || Auto.getNameLoc() != SearchedLocation)
+      return true;
+    // We expect the TTP to be attached to this function template.
+    // Find the template and the param index.
+    auto *FD = llvm::dyn_cast<FunctionDecl>(PVD->getDeclContext());
+    if (!FD)
+      return true;
+    auto *FTD = FD->getDescribedFunctionTemplate();
+    if (!FTD)
+      return true;
+    int ParamIndex = paramIndex(*FTD, *Auto.getDecl());
+    if (ParamIndex < 0) {
+      assert(false && "auto TTP is not from enclosing function?");
+      return true;
+    }
+
+    // Now determine the unique type arg among the implicit specializations.
+    const ASTContext &Ctx = PVD->getASTContext();
+    QualType UniqueType;
+    CanQualType CanUniqueType;
+    for (const FunctionDecl *Spec : FTD->specializations()) {
+      // Meaning `auto` is a bit overloaded if the function is specialized.
+      if (Spec->getTemplateSpecializationKind() == TSK_ExplicitSpecialization)
+        return true;
+      // Find the type for this specialization.
+      const auto *Args = Spec->getTemplateSpecializationArgs();
+      if (Args->size() != FTD->getTemplateParameters()->size())
+        continue; // no weird variadic stuff
+      QualType SpecType = Args->get(ParamIndex).getAsType();
+      if (SpecType.isNull())
+        continue;
+
+      // Deduced types need only be *canonically* equal.
+      CanQualType CanSpecType = Ctx.getCanonicalType(SpecType);
+      if (CanUniqueType.isNull()) {
+        CanUniqueType = CanSpecType;
+        UniqueType = SpecType;
+        continue;
+      }
+      if (CanUniqueType != CanSpecType)
+        return true; // deduced type is not unique
+    }
+    DeducedType = UniqueType;
+    return true;
+  }
+
+  // Find the abbreviated-function-template `auto` within a type.
+  // Similar to getContainedAutoTypeLoc, but these `auto`s are
+  // TemplateTypeParmTypes for implicit TTPs, instead of AutoTypes.
+  // Also we don't look very hard, just stripping const, references, pointers.
+  // FIXME: handle more types: vector<auto>?
+  static TemplateTypeParmTypeLoc findContainedAutoTTPLoc(TypeLoc TL) {
+    if (auto QTL = TL.getAs<QualifiedTypeLoc>())
+      return findContainedAutoTTPLoc(QTL.getUnqualifiedLoc());
+    if (llvm::isa<PointerType, ReferenceType>(TL.getTypePtr()))
+      return findContainedAutoTTPLoc(TL.getNextTypeLoc());
+    if (auto TTPTL = TL.getAs<TemplateTypeParmTypeLoc>()) {
+      if (TTPTL.getTypePtr()->getDecl()->isImplicit())
+        return TTPTL;
+    }
+    return {};
+  }
+
+  static int paramIndex(const TemplateDecl &TD, NamedDecl &Param) {
+    unsigned I = 0;
+    for (auto *ND : *TD.getTemplateParameters()) {
+      if (&Param == ND)
+        return I;
+      ++I;
+    }
+    return -1;
+  }
+
   QualType DeducedType;
 };
 } // namespace
 
 llvm::Optional<QualType> getDeducedType(ASTContext &ASTCtx,
                                         SourceLocation Loc) {
   if (!Loc.isValid())
     return {};

clang-tools-extra/clangd/refactor/tweaks/ExpandAutoType.cpp

public:
   llvm::StringLiteral kind() const override {
     return CodeAction::REFACTOR_KIND;
   }
   bool prepare(const Selection &Inputs) override;
   Expected<Effect> apply(const Selection &Inputs) override;
   std::string title() const override;
 
 private:
-  /// Cache the AutoTypeLoc, so that we do not need to search twice.
-  llvm::Optional<clang::AutoTypeLoc> CachedLocation;
+  SourceRange AutoRange;
 };
 
 REGISTER_TWEAK(ExpandAutoType)
 
 std::string ExpandAutoType::title() const { return "Expand auto type"; }
 
 // Structured bindings must use auto, e.g. `const auto& [a,b,c] = ...;`.
 // Return whether N (an AutoTypeLoc) is such an auto that must not be expanded.

 // which we cannot expand.
 bool isTemplateParam(const SelectionTree::Node *Node) {
   if (Node->Parent)
     if (Node->Parent->ASTNode.get<NonTypeTemplateParmDecl>())
       return true;
   return false;
 }
 
-bool ExpandAutoType::prepare(const Selection& Inputs) {
-  CachedLocation = llvm::None;
+bool ExpandAutoType::prepare(const Selection &Inputs) {
   if (auto *Node = Inputs.ASTSelection.commonAncestor()) {
     if (auto *TypeNode = Node->ASTNode.get<TypeLoc>()) {
       if (const AutoTypeLoc Result = TypeNode->getAs<AutoTypeLoc>()) {
         if (!isStructuredBindingType(Node) &&
             !isDeducedAsLambda(Node, Result.getBeginLoc()) &&
             !isTemplateParam(Node))
-          CachedLocation = Result;
+          AutoRange = Result.getSourceRange();
+      }
+      if (auto TTPAuto = TypeNode->getAs<TemplateTypeParmTypeLoc>()) {
+        // We exclude concept constraints for now, as the SourceRange is wrong.
+        // void foo(C auto x) {};
+        //            ^^^^
+        // TTPAuto->getSourceRange only covers "auto", not "C auto".
+        if (TTPAuto.getDecl()->isImplicit() &&
+            !TTPAuto.getDecl()->hasTypeConstraint())
+          AutoRange = TTPAuto.getSourceRange();
       }
     }
   }
 
-  return (bool) CachedLocation;
+  return AutoRange.isValid();
 }
 
 Expected<Tweak::Effect> ExpandAutoType::apply(const Selection& Inputs) {
   auto &SrcMgr = Inputs.AST->getSourceManager();
 
-  llvm::Optional<clang::QualType> DeducedType = getDeducedType(
-      Inputs.AST->getASTContext(), CachedLocation->getBeginLoc());
+  llvm::Optional<clang::QualType> DeducedType =
+      getDeducedType(Inputs.AST->getASTContext(), AutoRange.getBegin());
 
   // if we can't resolve the type, return an error message
   if (DeducedType == llvm::None || (*DeducedType)->isUndeducedAutoType())
     return error("Could not deduce type for 'auto' type");
 
   // if it's a lambda expression, return an error message
   if (isa<RecordType>(*DeducedType) &&
       cast<RecordType>(*DeducedType)->getDecl()->isLambda()) {
     return error("Could not expand type of lambda expression");
   }
 
   // if it's a function expression, return an error message
   // naively replacing 'auto' with the type will break declarations.
   // FIXME: there are other types that have similar problems
   if (DeducedType->getTypePtr()->isFunctionPointerType()) {
     return error("Could not expand type of function pointer");
   }
 
   std::string PrettyTypeName = printType(*DeducedType,
       Inputs.ASTSelection.commonAncestor()->getDeclContext());
 
-  tooling::Replacement
-      Expansion(SrcMgr, CharSourceRange(CachedLocation->getSourceRange(), true),
+  tooling::Replacement Expansion(SrcMgr, CharSourceRange(AutoRange, true),
                                  PrettyTypeName);
 
   return Effect::mainFileEdit(SrcMgr, tooling::Replacements(Expansion));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang

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

const char *DeducedType;
       {
           R"cpp( // auto on alias
             struct Foo {};
             using Bar = Foo;
             ^auto x = Bar();
           )cpp",
           "Bar",
       },
+      {
+          R"cpp(
+            // Generic lambda param.
+            struct Foo{};
+            auto Generic = [](^auto x) { return 0; };
+            int m = Generic(Foo{});
+          )cpp",
+          "struct Foo",
+      },
+      {
+          R"cpp(
+            // Generic lambda instantiated twice, matching deduction.
+            struct Foo{};
+            using Bar = Foo;
+            auto Generic = [](^auto x, auto y) { return 0; };
+            int m = Generic(Bar{}, "one");
+            int n = Generic(Foo{}, 2);
+          )cpp",
+          "struct Foo",
+      },
+      {
+          R"cpp(
+            // Generic lambda instantiated twice, conflicting deduction.
+            struct Foo{};
+            auto Generic = [](^auto y) { return 0; };
+            int m = Generic("one");
+            int n = Generic(2);
+          )cpp",
+          nullptr,
+      },
+      {
+          R"cpp(
+            // Generic function param.
+            struct Foo{};
+            int generic(^auto x) { return 0; }
+            int m = generic(Foo{});
+          )cpp",
+          "struct Foo",
+      },
+      {
+          R"cpp(
+            // More complicated param type involving auto.
+            template <class> concept C = true;
+            struct Foo{};
+            int generic(C ^auto *x) { return 0; }
+            const Foo *Ptr = nullptr;
+            int m = generic(Ptr);
+          )cpp",
+          "const struct Foo",
+      },
   };
   for (Test T : Tests) {
     Annotations File(T.AnnotatedCode);
-    auto AST = TestTU::withCode(File.code()).build();
+    auto TU = TestTU::withCode(File.code());
+    TU.ExtraArgs.push_back("-std=c++20");
+    auto AST = TU.build();
     SourceManagerForFile SM("foo.cpp", File.code());
 
-    SCOPED_TRACE(File.code());
+    SCOPED_TRACE(T.AnnotatedCode);
     EXPECT_FALSE(File.points().empty());
     for (Position Pos : File.points()) {
       auto Location = sourceLocationInMainFile(SM.get(), Pos);
       ASSERT_TRUE(!!Location) << llvm::toString(Location.takeError());
       auto DeducedType = getDeducedType(AST.getASTContext(), *Location);
+      if (T.DeducedType == nullptr) {
+        EXPECT_FALSE(DeducedType);
+      } else {
         ASSERT_TRUE(DeducedType);
         EXPECT_EQ(DeducedType->getAsString(), T.DeducedType);
       }
     }
   }
+}
 
 TEST(ClangdAST, GetQualification) {
   // Tries to insert the decl `Foo` into position of each decl named `insert`.
   // This is done to get an appropriate DeclContext for the insertion location.
   // Qualifications are the required nested name specifier to spell `Foo` at the
   // `insert`ion location.
   // VisibleNamespaces are assumed to be visible at every insertion location.
   const struct {

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

const char *Tests[] = {
       R"cpp(// const auto& in function return
         struct [[Bar]] {};
         const ^auto& test() {
           static Bar x;
           return x;
         }
       )cpp",
 
+      R"cpp(// auto lambda param where there's a single instantiation
+        struct [[Bar]] {};
+        auto Lambda = [](^auto){ return 0; };
+        int x = Lambda(Bar{});
+      )cpp",
+
       R"cpp(// decltype(auto) in function return
         struct [[Bar]] {};
         ^decltype(auto) test() {
           return Bar();
         }
       )cpp",
 
       R"cpp(// decltype of function with trailing return type.

clang-tools-extra/clangd/unittests/tweaks/ExpandAutoTypeTests.cpp

TEST_F(ExpandAutoTypeTest, Test) {
   EXPECT_EQ(apply("decltype(au^to) x = 10;"), "int x = 10;");
   // expanding types in structured bindings is syntactically invalid.
   EXPECT_UNAVAILABLE("const ^auto &[x,y] = (int[]){1,2};");
 
   // unknown types in a template should not be replaced
   EXPECT_THAT(apply("template <typename T> void x() { ^auto y = T::z(); }"),
               StartsWith("fail: Could not deduce type for 'auto' type"));
 
-  ExtraArgs.push_back("-std=c++17");
+  ExtraArgs.push_back("-std=c++20");
   EXPECT_UNAVAILABLE("template <au^to X> class Y;");
+
+  EXPECT_THAT(apply("auto X = [](^auto){};"),
+              StartsWith("fail: Could not deduce"));
+  EXPECT_EQ(apply("auto X = [](^auto){return 0;}; int Y = X(42);"),
+            "auto X = [](int){return 0;}; int Y = X(42);");
+  EXPECT_THAT(apply("auto X = [](^auto){return 0;}; int Y = X(42) + X('c');"),
+              StartsWith("fail: Could not deduce"));
+  // FIXME: should work on constrained auto params, once SourceRange is fixed.
+  EXPECT_UNAVAILABLE("template<class> concept C = true;"
+                     "auto X = [](C ^auto *){return 0;};");
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang