[clangd][CodeComplete] Improve FunctionCanBeCall

[zyounan]

Summary

From two aspects:

• For function templates, emit additional template argument

placeholders in the context where it can't be a call in order
to specify an instantiation explicitly.

• Consider expressions with base type specifier such as

'Derived().Base::foo^' a function call.

[zyounan]

Merge changes with function templates from D155370

[zyounan]

Trigger the build

[nridge]

Thanks for the patch, these are nice improvements

clang-tools-extra/clangd/CodeCompletionStrings.cpp

258 ↗

(On Diff #547569)

It looks like we are assuming two things:

1. Any LeftParen in an RK_Declaration starts a function argument list
2. Everything that comes after the function argument list can be discarded

I think these assumptions are fine to make, but let's be explicit about them in a comment

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

536 ↗

(On Diff #547569)

Suggestion: it would be slightly more interesting to make the function signature generic(U). Then, the function can be called as generic<T>(u) (with the template parameter U deduced), and the LastDeducibleArgument logic should make sure that only <T> is added to the code completion string, not <T, U>.

580 ↗

(On Diff #547569)

Since you're updating this test anyways, could you add signature() matchers for the non-template cases as well please?

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

178 ↗

(On Diff #547569)

Maybe add:

// Arguments dropped from snippet, kept in signature

so someone reading the test knows it's deliberate

clang/lib/Sema/SemaCodeComplete.cpp

364

The word "base" is a bit overloaded in this signature; in the parameter InBaseClass it refers to inheritance, but in BaseType it refers to the base expression of a MemberExpr.

Maybe we can name the new parameter BaseExprType to avoid confusion?

1364–1365

Should we propagate BaseType into this recursive call?

1476

Is there any situation where MaybeDerived == MaybeBase || MaybeDerived->isDerivedFrom(MaybeBase) is false?

I am wondering if we can simplify this to:

if (!BaseType.isNull()) {
  R.FunctionCanBeCall = true;
}

3657

1. If this is not a call, we can avoid running the Sema::MarkDeducedTemplateParameters operation altogether.

2. A future improvement we could consider: if this is not a call, try to detect cases where the template parameters can be deduced from the surrounding context ("Deducing template arguments taking the address of a function template "). Maybe add a FIXME for this?

[sammccall]

Thanks, this does look better.

I agree with Nathan's comments and will leave final stamp to him.

clang-tools-extra/clangd/CodeCompletionStrings.cpp

144 ↗

(On Diff #547569)

I find this comment very unclear, I think because it starts with implementation details and works its way up to general principles.

I think Buffer that snippet chunks are written to once we've decided to discard the snippet due to DropFunctionArguments or so would be enough.

However I'd rather drop this variable entirely if possible, the data flow is confusing. See below.

148 ↗

(On Diff #547569)

For the reason you give here, it's actually *not* preferable. So I'd suggest leaving out this comment.

258 ↗

(On Diff #547569)

Agree, but also I think the code could reflect this more directly:

• this should trigger only for CK_LeftParen, not CK_RightParen

Rather than redirecting output to a different string by reassigning the param, I think it would be a bit more direct to have

optional<unsigned> TruncateSnippetAt;
...
case CK_LeftBracket:
  if (DropFunctionArguments && ... && !TruncateSnippetAt)
    TruncateSnippetAt = Snippet->size();
...
if (TruncateSnippetAt)
  Snippet->resize(*TruncateSnippetAt);
}

(though still not totally clear)

clang-tools-extra/clangd/CodeCompletionStrings.h

45 ↗

(On Diff #547569)

Prefer positive sense for bool params (IncludeFunctionArguments) to avoid double-negative confusion

clang/lib/Sema/SemaCodeComplete.cpp

1466–1499

This is confusing: the CCC_Symbol test is part of the specific heuristics being used (it's the "not via dot/arrow member access" part, right?) but you've moved the comment explaining what it does.

Also this function is just getting too long, and we're inlining more complicated control flow here.
Can we extract a function?

const auto *Method = ...;
if (Method & !Method->isStatic()) {
  R.FunctionCanBeCall = canMethodBeCalled(...);
}

1468

This description is hard for me to follow, and it's hard to tell if this is independent of the previous check, or an exception to it.

An example would be clearer. (I think instead rather than in addition):
Exception: foo->FooBase::bar() *is* a call.

1471

if (const CXXRecordDecl *BaseDecl = BaseType ? BaseType-> getAsCXXRecordDecl() : nullptr)?
avoiding the reassignment inside a boolean expression

[zyounan]

Address many comments.

[zyounan]

Thanks for Sam and Nathan's thorough review! I've updated, and please take another look.
(Apologize for churning on weekends, but I don't have chunk time during the week.)

clang-tools-extra/clangd/CodeCompletionStrings.cpp

258 ↗

(On Diff #547569)

It looks like we are assuming two things

Honestly, I don't quite prefer this assumption. However, we have lost some of the semantics e.g., the structure of a call expression within this function, and unfortunately it's not trivial to pass these out from clang. :-(

(though still not totally clear)

Yeah. I imagine a clearer way would be separating the calculation for Signature and Snippet, and we could bail out early for Snippet. But I'm afraid that making so many adjustments to getSignature for such a small feature is inappropriate.

Assuming the left parenthesis is the beginning of a call might be sufficient for the time being, and let's leave the refactoring to subsequent patches.

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

580 ↗

(On Diff #547569)

Of course!

clang/lib/Sema/SemaCodeComplete.cpp

364

Makes sense to me. Thanks for the correction.

1364–1365

Yes. And thanks for spotting this. I added another test case reflecting it.

1466–1499

it's the "not via dot/arrow member access" part

(Sorry for being unaware of the historical context). But I think CCC_Symbol should mean "we're completing a name such as a function or type name" per its comment. The heuristic for dot/arrow member access actually lies on the next line, i.e., if the completing decl is a CXXMethodDecl.

Can we extract a function?

Sure.

1476

I think this could prevent us from completing ill-formed expressions like:

struct B {
  void foo();
};

struct D : B {
  void bar();
};

struct S {
  void method();
};

void baz() {
  D().S::^
}

Currently, we have the candidate method, and completing it with parentheses is definitely wrong. (Although we shouldn't be providing method as well.)

3657

avoid running the Sema::MarkDeducedTemplateParameters operation altogether

I think doing so could cause too many adjustments to the flow, and I'm afraid that the Sema::MarkDeducedTemplateParameters would be required again when we decide to implement point 2.

I'm adding a FIXME anyway but leave the first intact. However, I'd be happy to rearrange the logic flow if you insist.

[zyounan]

Fix the bool expression.

[zyounan]

Sorry, forgot to update tests :(

[zyounan]

Gently ping~

[nridge]

(I'm away on travels, will get back to this within the next week)

[nridge]

clang/lib/Sema/SemaCodeComplete.cpp

1316

nit: we can avoid the computation in this block if FunctionCanBeCall was already initialized to true above

1466–1499

The check for CompletionContext.getKind() is in fact a part of the heuristic:

• for f.method, the kind is CCC_DotMemberAccess
• for f->method, the kind is CCC_ArrowMemberAccess
• for f.Foo::method and f->Foo::method, the kind is CCC_Symbol

(I realize that's a bit inconsistent. Maybe the f.Foo:: and f->Foo:: cases should be using DotMemberAccess and ArrowMemberAccess as well? Anyways, that's a pre-existing issue.)

So, the if (CompletionContext.getKind() == clang::CodeCompletionContext::CCC_Symbol) check is what currently makes sure that in the f.method and f->method cases, we just keep FunctionCanBeCall = true without having to check any context or expression type.

I think it may be clearest to move this entire if block into the new function (whose name can be generalized to canBeCall or similar), and here just unconditionally set R.FunctionCanBeCall = canBeCall(CompletionContext, /* other things */).

3657

I realized there's actually an open question here: if FunctionCanBeCall == false, do we want to include all the template parameters, or just the non-deducible ones?

Let's consider an example:

class Foo {
  template <typename T, typename U>
  T convertTo(U from);
};

void bar() {
  Foo::^
}

Here, U can be deduced but T cannot.

The current behaviour is to complete convertTo<T>. That seems appropriate for a call, since U will be deduced from the call. But since this is not a call, wouldn't it be better to complete convertTo<T, U>?

[zyounan]

clang/lib/Sema/SemaCodeComplete.cpp

3657

But since this is not a call, wouldn't it be better to complete convertTo<T, U>?

(Ugh, this is exactly this patch's initial intention, but how...?)

Oh, I made a mistake here: I presumed LastDeducibleArgument would always be 0 if we're in a non-callable context, but this is wrong! This variable is calculated based on the function parameters, which ought to be equal to the number of template parameters deducible in function parameters.

( I used to duplicate this if block for the !FunctionCanBeCall case but finally, I merged these two erroneously. :-( )

[zyounan]

Address comments

[zyounan]

Thank you Nathan for your constructive opinions! I've updated this patch again, hopefully this becomes better.

clang/lib/Sema/SemaCodeComplete.cpp

1466–1499

I think it may be clearest to move this entire if block into the new function

Nice suggestion. I'll take it.

3657

A future improvement we could consider: if this is not a call, try to detect cases where the template parameters can be deduced from the surrounding context ("Deducing template arguments taking the address of a function template "). Maybe add a FIXME for this?

UPD: I've looked into the deduction implementation and found it not difficult to add such a heuristic: We have PreferredType that describes the type in a declaration, e.g., void (*)(int, int) and DeduceTemplateArgumentsByTypeMatch in Sema to tell if the template parameter type P could be deduced from the 'synthesized' type A (That is, the declaring type void (int, int), for example).

I suppose we could apply such a deduction for each candidate and eliminate its template parameters in the result if the deduction succeeds - But let me leave that for the next patch(es) so I don't overload you. :-)

[nridge]

Thank you, the updates look good! Please go ahead and merge after addressing the last minor nits.

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

594 ↗

(On Diff #556909)

It seems a bit inconsistent that the signature includes parameters with default arguments in the non-call case, and not in the call case. I guess the reason for this is that in the non-call case, the parameters with defaults become a CK_Optional chunk which clangd adds to the signature here, while in the call case the deduced parameters (which include the ones with defaults) are omitted from the completion string altogether.

It may be more consistent to put the deduced parameters into an optional chunk as well, and let the consumer of the CodeCompletionString decide whether to use them?

Anyways, that's an idea for the future, no change needed now.

clang/lib/Sema/SemaCodeComplete.cpp

1302

nit: let's shorten this comment to just "If we're not inside the scope of the method's class, it can't be a call"

(The parts about non-static and dot/arrow member access are checked and explained in canFunctionBeCalled())

3619–3626

nit: "We'd" --> "We should"

[zyounan]

Thank you guys again for the long and meticulous review! :)

For a quick note, here are points I've excerpted from Nathan's reviews that need improvements later:

1. Implement a heuristic that works for function template pointers whose template parameters could be deduced from the declaring type. https://reviews.llvm.org/D156605#inline-1546819

2. Currently, the deducible template parameters are discarded by default; it may be more consistent to put the deduced parameters into an optional chunk as well, and let the consumer of the CodeCompletionString decide whether to use them. https://reviews.llvm.org/D156605#inline-1548400

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

594 ↗

(On Diff #556909)

It seems a bit inconsistent that the signature includes parameters with default arguments in the non-call case, and not in the call case.

Indeed. If we just want consistent behavior (i.e., both get omitted) for default parameters, it is easy to fix at the moment. Note that

1. the loop for default template params will run iff the bit vector Deduced is not empty.

2. the vector would be resized in Sema::MarkDeducedTemplateParameters to fit the template params, which has been avoided in my patch to emit all template params for non-call cases. As a result, LastDeducibleArgument would always be 0 for non-calls, even with default template params.

We can change the Deduced to a default initialized N-size bit vector, where N is the size of template params. This way, the default params can be omitted in the loop as desired (by reducing LastDeducibleArgument to limit the range it would dump to the CCS chunk later), while non-default params get preserved.

It may be more consistent to put the deduced parameters into an optional chunk as well, and let the consumer of the CodeCompletionString decide whether to use them?

Sounds reasonable.

[zyounan]

Address nits; discard default template parameters

[zyounan]

Sorry, wrong patch

[zyounan]

Fix the CI

clang/include/clang/Sema/Sema.h

enum TemplateDeductionResult {
     TDK_SubstitutionFailure,
     /// After substituting deduced template arguments, a dependent
     /// parameter type did not match the corresponding argument.
     TDK_DeducedMismatch,
     /// After substituting deduced template arguments, an element of
     /// a dependent parameter type did not match the corresponding element
     /// of the corresponding argument (when deducing from an initializer list).
     TDK_DeducedMismatchNested,
-    /// A non-depnedent component of the parameter did not match the
+    /// A non-dependent component of the parameter did not match the
     /// corresponding component of the argument.
     TDK_NonDeducedMismatch,
     /// When performing template argument deduction for a function
     /// template, there were too many call arguments.
     TDK_TooManyArguments,
     /// When performing template argument deduction for a function
     /// template, there were too few call arguments.
     TDK_TooFewArguments,

 
   TemplateDeductionResult
   DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
                           TemplateArgumentListInfo *ExplicitTemplateArgs,
                           FunctionDecl *&Specialization,
                           sema::TemplateDeductionInfo &Info,
                           bool IsAddressOfFunction = false);
 
+  static Sema::TemplateDeductionResult DeduceTemplateArgumentsByTypeMatch(
+      Sema &S, TemplateParameterList *TemplateParams, QualType P, QualType A,
+      sema::TemplateDeductionInfo &Info,
+      SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,
+      bool PartialOrdering = false, bool DeducedFromArrayBound = false);
+
   /// Substitute Replacement for \p auto in \p TypeWithAuto
   QualType SubstAutoType(QualType TypeWithAuto, QualType Replacement);
   /// Substitute Replacement for auto in TypeWithAuto
   TypeSourceInfo* SubstAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto,
                                           QualType Replacement);
 
   // Substitute auto in TypeWithAuto for a Dependent auto type
   QualType SubstAutoTypeDependent(QualType TypeWithAuto);

clang/lib/Sema/SemaCodeComplete.cpp

 #include "clang/Sema/Lookup.h"
 #include "clang/Sema/Overload.h"
 #include "clang/Sema/ParsedAttr.h"
 #include "clang/Sema/ParsedTemplate.h"
 #include "clang/Sema/Scope.h"
 #include "clang/Sema/ScopeInfo.h"
 #include "clang/Sema/Sema.h"
 #include "clang/Sema/SemaInternal.h"
+// #include "clang/Sema/Template.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/ADT/Twine.h"
public:
   /// \param Hiding the declaration that hides the result.
   ///
   /// \param InBaseClass whether the result was found in a base
   /// class of the searched context.
   ///
   /// \param BaseExprType the type of expression that precedes the "." or "->"
   /// in a member access expression.
   void AddResult(Result R, DeclContext *CurContext, NamedDecl *Hiding,
                  bool InBaseClass, QualType BaseExprType);
 
   /// Add a new non-declaration result to this result set.
   void AddResult(Result R);
 
   /// Enter into a new scope.
   void EnterNewScope();
 
   /// Exit from the current scope.
for (DeclContext *Ctx = CurContext; Ctx; Ctx = Ctx->getParent()) {
       const auto *CtxMethod = llvm::dyn_cast<CXXMethodDecl>(Ctx);
       if (CtxMethod && !CtxMethod->getParent()->isLambda()) {
         return CtxMethod->getParent();
       }
     }
     return nullptr;
   }();
 
   // If we're not inside the scope of the method's class, it can't be a call.
   bool FunctionCanBeCall =
       CurrentClassScope &&
       (CurrentClassScope == Method->getParent() ||
        CurrentClassScope->isDerivedFrom(Method->getParent()));
 
   // We skip the following calculation for exceptions if it's already true.
   if (FunctionCanBeCall)
     return true;
 
   // Exception: foo->FooBase::bar() or foo->Foo::bar() *is* a call.
   if (const CXXRecordDecl *MaybeDerived =
           BaseExprType.isNull() ? nullptr
                                 : BaseExprType->getAsCXXRecordDecl()) {
     auto *MaybeBase = Method->getParent();
     FunctionCanBeCall =
         MaybeDerived == MaybeBase || MaybeDerived->isDerivedFrom(MaybeBase);
   }
 
   return FunctionCanBeCall;
 }
 
 bool ResultBuilder::canFunctionBeCalled(const NamedDecl *ND,
void ResultBuilder::AddResult(Result R, DeclContext *CurContext,
   if (const auto *Using = dyn_cast<UsingShadowDecl>(R.Declaration)) {
     CodeCompletionResult Result(Using->getTargetDecl(),
                                 getBasePriority(Using->getTargetDecl()),
                                 R.Qualifier, false,
                                 (R.Availability == CXAvailability_Available ||
                                  R.Availability == CXAvailability_Deprecated),
                                 std::move(R.FixIts));
     Result.ShadowDecl = Using;
     AddResult(Result, CurContext, Hiding, /*InBaseClass=*/false,
               /*BaseExprType=*/BaseExprType);
     return;
   }
 
   bool AsNestedNameSpecifier = false;
   if (!isInterestingDecl(R.Declaration, AsNestedNameSpecifier))
     return;
 
   // C++ constructors are never found by name lookup.
if (const auto *Method = dyn_cast<CXXMethodDecl>(R.Declaration))
             // This overload can't be called, drop it.
             return;
           case OverloadCompare::BothViable:
             break;
           }
         }
         OverloadSet.Add(Method, Results.size());
       }
 
+#if 0
+  const FunctionTemplateDecl *FTD = nullptr;
+  FTD = dyn_cast<FunctionTemplateDecl>(R.Declaration);
+  llvm::errs() << "SCC 0: " << (void *)FTD << " " << PreferredType.isNull()
+               << "\n";
+  if (FTD && PreferredType) {
+    auto Pointee = PreferredType->getTypePtr()->getPointeeType();
+    llvm::errs() << "SCC 1\n";
+    if (!Pointee.isNull()) {
+      llvm::errs() << "SCC 2\n";
+      if (const auto *FT = Pointee->getAs<FunctionType>()) {
+        llvm::errs() << "SCC 3\n";
+        sema::TemplateDeductionInfo Info(SourceLocation{});
+        llvm::SmallVector<DeducedTemplateArgument> Deduced;
+        Deduced.resize(FTD->getTemplateParameters()->size());
+        FT->dump();
+        if (auto Result = Sema::DeduceTemplateArgumentsByTypeMatch(
+                SemaRef, FTD->getTemplateParameters(),
+                FTD->getTemplatedDecl()->getType(),
+                FT->getCanonicalTypeInternal(), Info, Deduced, 48)) {
+          llvm::errs() << FTD->getNameAsString()
+                       << " could not be deduced from enclosing type: "
+                       << Result << "\n";
+        } else
+          llvm::errs() << FTD->getNameAsString()
+                       << " could be deduced from enclosing type"
+                       << "\n";
+      }
+    }
+  }
+#endif
+
   R.FunctionCanBeCall = canFunctionBeCalled(R.getDeclaration(), BaseExprType);
 
   // Insert this result into the set of results.
   Results.push_back(R);
 
   if (!AsNestedNameSpecifier)
     MaybeAddConstructorResults(R);
 }
 
if (const FunctionTemplateDecl *FunTmpl =
           dyn_cast<FunctionTemplateDecl>(ND)) {
     AddQualifierToCompletionString(Result, Qualifier, QualifierIsInformative,
                                    Ctx, Policy);
     FunctionDecl *Function = FunTmpl->getTemplatedDecl();
     AddTypedNameChunk(Ctx, Policy, Function, Result);
 
     // Figure out which template parameters are deduced (or have default
     // arguments).
     // Note that we're creating a non-empty bit vector so that we can go
     // through the loop below to omit default template parameters for non-call
     // cases.
     llvm::SmallBitVector Deduced(FunTmpl->getTemplateParameters()->size());
     // Avoid running it if this is not a call: We should emit *all* template
     // parameters.
     if (FunctionCanBeCall)
       Sema::MarkDeducedTemplateParameters(Ctx, FunTmpl, Deduced);
     unsigned LastDeducibleArgument;
     for (LastDeducibleArgument = Deduced.size(); LastDeducibleArgument > 0;
          --LastDeducibleArgument) {
       if (!Deduced[LastDeducibleArgument - 1]) {
         // C++0x: Figure out if the template argument has a default. If so,
         // the user doesn't need to type this argument.
         // FIXME: We need to abstract template parameters better!
         bool HasDefaultArg = false;
for (LastDeducibleArgument = Deduced.size(); LastDeducibleArgument > 0;
           break;
       }
     }
 
     if (LastDeducibleArgument || !FunctionCanBeCall) {
       // Some of the function template arguments cannot be deduced from a
       // function call, so we introduce an explicit template argument list
       // containing all of the arguments up to the first deducible argument.
       //
       // Or, if this isn't a call, emit all the template arguments
       // to disambiguate the (potential) overloads.
       //
       // FIXME: Detect cases where the function parameters can be deduced from
       // the surrounding context, as per [temp.deduct.funcaddr].
       // e.g.,
       // template <class T> void foo(T);
       // void (*f)(int) = foo;

clang/lib/Sema/SemaOverload.cpp

bool AddMatchingTemplateFunction(FunctionTemplateDecl* FunctionTemplate,
     // C++ [over.over]p2:
     //   If the name is a function template, template argument deduction is
     //   done (14.8.2.2), and if the argument deduction succeeds, the
     //   resulting template argument list is used to generate a single
     //   function template specialization, which is added to the set of
     //   overloaded functions considered.
     FunctionDecl *Specialization = nullptr;
     TemplateDeductionInfo Info(FailedCandidates.getLocation());
+    // TargetFunctionType->dump(llvm::errs(), Context);
     if (Sema::TemplateDeductionResult Result
           = S.DeduceTemplateArguments(FunctionTemplate,
                                       &OvlExplicitTemplateArgs,
                                       TargetFunctionType, Specialization,
                                       Info, /*IsAddressOfFunction*/true)) {
       // Make a note of the failed deduction for diagnostics.
       FailedCandidates.addCandidate()
           .set(CurAccessFunPair, FunctionTemplate->getTemplatedDecl(),

clang/lib/Sema/SemaTemplateDeduction.cpp

#include "clang/AST/TypeNodes.inc"
     case Type::Pipe:
       // No template argument deduction for these types
       return Sema::TDK_Success;
     }
 
   llvm_unreachable("Invalid Type Class!");
 }
 
+Sema::TemplateDeductionResult Sema::DeduceTemplateArgumentsByTypeMatch(
+    Sema &S, TemplateParameterList *TemplateParams, QualType P, QualType A,
+    sema::TemplateDeductionInfo &Info,
+    SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,
+    bool PartialOrdering, bool DeducedFromArrayBound) {
+  return ::DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, P, A, Info,
+                                              Deduced, TDF, PartialOrdering,
+                                              DeducedFromArrayBound);
+}
+
 static Sema::TemplateDeductionResult
 DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
                         const TemplateArgument &P, TemplateArgument A,
                         TemplateDeductionInfo &Info,
                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
   // If the template argument is a pack expansion, perform template argument
   // deduction against the pattern of that expansion. This only occurs during
   // partial ordering.