[CodeComplete] WIP member completion for concept-constrained type parameters

[sammccall]

Summary

see https://github.com/clangd/clangd/issues/261

[merge_guards_bot]

Unit tests: pass. 62281 tests passed, 0 failed and 827 were skipped.

clang-tidy: fail. clang-tidy found 0 errors and 7 warnings. 0 of them are added as review comments below (why?).

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

clang/include/clang/Sema/Scope.h

public:
   }
 
   unsigned getMSCurManglingNumber() const {
     return MSCurManglingNumber;
   }
 
   /// isDeclScope - Return true if this is the scope that the specified decl is
   /// declared in.
-  bool isDeclScope(Decl *D) {
-    return DeclsInScope.count(D) != 0;
-  }
+  bool isDeclScope(const Decl *D) { return DeclsInScope.count(D) != 0; }
 
   DeclContext *getEntity() const { return Entity; }
   void setEntity(DeclContext *E) { Entity = E; }
 
   bool hasErrorOccurred() const { return ErrorTrap.hasErrorOccurred(); }
 
   bool hasUnrecoverableErrorOccurred() const {
     return ErrorTrap.hasUnrecoverableErrorOccurred();

clang/lib/Sema/SemaCodeComplete.cpp

 //===----------------------------------------------------------------------===//
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
+#include "clang/AST/ExprConcepts.h"
 #include "clang/AST/ExprObjC.h"
+#include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/QualTypeNames.h"
+#include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/CharInfo.h"
 #include "clang/Basic/Specifiers.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Designator.h"
if (const auto *TD = dyn_cast_or_null<ClassTemplateDecl>(
             TST->getTemplateName().getAsTemplateDecl())) {
       return TD->getTemplatedDecl();
     }
   }
 
   return nullptr;
 }
 
+namespace {
+
+// Returns the DeclContext immediately enclosed by the template parameter scope.
+// For primary templates, this is the templated (e.g.) CXXRecordDecl.
+// For specializations, this is e.g. ClassTemplatPartialSpecializationDecl.
+DeclContext *getTemplatedEntity(const TemplateTypeParmDecl *D, Scope *S) {
+  if (D == nullptr)
+    return nullptr;
+  Scope *Inner = nullptr;
+  while (S) {
+    if (S->isTemplateParamScope() && S->isDeclScope(D))
+      return Inner->getEntity();
+    Inner = S;
+    S = S->getParent();
+  }
+  return nullptr;
+}
+
+llvm::SmallVector<const Expr *, 1>
+constraintsForTemplatedEntity(DeclContext *E) {
+  llvm::SmallVector<const Expr *, 1> Result;
+  if (E == nullptr)
+    return Result;
+  llvm::cast<Decl>(E)->dump();
+  // Primary templates can have constraints.
+  if (const auto *TD = llvm::cast<Decl>(E)->getDescribedTemplate())
+    TD->getAssociatedConstraints(Result);
+  // Partial specializations may have constraints.
+  if (const auto *CTPSD =
+          llvm::dyn_cast<ClassTemplatePartialSpecializationDecl>(E))
+    CTPSD->getAssociatedConstraints(Result);
+  if (const auto *VTPSD =
+          llvm::dyn_cast<VarTemplatePartialSpecializationDecl>(E))
+    VTPSD->getAssociatedConstraints(Result);
+  return Result;
+}
+
+// Describes a likely member of a type, inferred by concept constraints.
+// Offered as a code completion for T. T-> and T:: contexts.
+struct ConceptMemberResult {
+  const IdentifierInfo *Name = nullptr;
+  llvm::Optional<llvm::SmallVector<QualType, 1>> ArgTypes; // For functions.
+  enum ResultKind {
+    Function,
+    Variable,
+    Type,
+  } Kind = Variable;
+  enum AccessType {
+    Dot,
+    Arrow,
+    Colons,
+  } Operator = Dot;
+
+  // For now we simply return these results as "pattern" strings.
+  CodeCompletionString *render(Sema &S, CodeCompletionAllocator &Alloc,
+                               CodeCompletionTUInfo &Info) const {
+    CodeCompletionBuilder B(Alloc, Info);
+    B.AddTypedTextChunk(Alloc.CopyString(Name->getName()));
+    if (ArgTypes) {
+      B.AddChunk(clang::CodeCompletionString::CK_LeftParen);
+      bool First = true;
+      for (QualType Arg : *ArgTypes) {
+        if (First)
+          First = false;
+        else {
+          B.AddChunk(clang::CodeCompletionString::CK_Comma);
+          B.AddChunk(clang::CodeCompletionString::CK_HorizontalSpace);
+        }
+        B.AddPlaceholderChunk(
+            Alloc.CopyString(Arg.getAsString(getCompletionPrintingPolicy(S))));
+      }
+      B.AddChunk(clang::CodeCompletionString::CK_RightParen);
+    }
+    return B.TakeString();
+  }
+};
+
+// Attempts to determine likely members of a concept-constrained type T
+// by examining the constraint expressions.
+//
+// For example, given:
+//   template <class T> concept X = requires (T t) { t.foo(); };
+//   template <X U> void foo(U u) { u.^ }
+// We should offer the completion 'foo()':
+// - u has type U
+// - so X<U> holds
+// - X<T> requires t.foo() to be valid, where t has type T.
+//
+// The design is very simple: we walk down each constraint looking for
+// expressions of the form T.foo().
+// If we're extra lucky, the return type is specified.
+// We don't do any clever handling of && or || in constraint expressions.
+//
+// FIXME: it some of this machinery could be used for non-concept tparms too,
+// enabling completion for type parameters based on other uses of that param.
+class ConceptMembers {
+  llvm::DenseMap<const IdentifierInfo *, ConceptMemberResult> Results;
+
+public:
+  ConceptMembers(const TemplateTypeParmType &BaseType, Scope *S) {
+    auto *TemplatedEntity = getTemplatedEntity(BaseType.getDecl(), S);
+    for (const Expr *E : constraintsForTemplatedEntity(TemplatedEntity))
+      believe(E, &BaseType);
+  }
+
+  std::vector<ConceptMemberResult> results() {
+    std::vector<ConceptMemberResult> Results;
+    for (const auto &E : this->Results)
+      Results.push_back(E.second);
+    llvm::sort(Results,
+               [](const ConceptMemberResult &L, const ConceptMemberResult &R) {
+                 return L.Name->getName() < R.Name->getName();
+               });
+    return Results;
+  }
+
+  // Infer members of T, given that the expression E (dependent on T) is true.
+  void believe(const Expr *E, const TemplateTypeParmType *T) {
+    if (!E || !T)
+      return;
+    E->dump();
+    if (auto *CSE = llvm::dyn_cast<ConceptSpecializationExpr>(E)) {
+      ConceptDecl *CD = CSE->getNamedConcept();
+      TemplateParameterList *Params = CD->getTemplateParameters();
+      // This is usually CD<T>. But maybe CD<U, T>. Or CD<T, T>!
+      unsigned Index = 0;
+      for (const auto &Arg : CSE->getTemplateArguments()) {
+        if (Index > Params->size())
+          break; // Won't happen in valid code.
+        if (isApprox(Arg, T)) {
+          auto *TTPD = dyn_cast<TemplateTypeParmDecl>(Params->getParam(Index));
+          if (!TTPD)
+            continue;
+          // T was used as an argument, and bound to the parameter TT.
+          auto *TT = cast<TemplateTypeParmType>(TTPD->getTypeForDecl());
+          // So now we know the constraint as a function of TT is true.
+          CD->getConstraintExpr()->dump();
+          believe(CD->getConstraintExpr(), TT);
+          // (concepts themselves have no associated constraints to require)
+        }
+
+        ++Index;
+      }
+    } else if (auto *BO = dyn_cast<BinaryOperator>(E)) {
+      // We don't treat and/or differently...
+      if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) {
+        believe(BO->getLHS(), T);
+        believe(BO->getRHS(), T);
+      }
+    } else if (auto *RE = dyn_cast<RequiresExpr>(E)) {
+      for (const concepts::Requirement *Req : RE->getRequirements()) {
+        if (!Req->isDependent())
+          continue;
+        if (auto *TR = llvm::dyn_cast<concepts::TypeRequirement>(Req)) {
+          QualType AssertedType = TR->getType()->getType();
+          AssertedType.dump();
+          ValidVisitor(this, T).TraverseType(AssertedType);
+        }
+        if (auto *ER = llvm::dyn_cast<concepts::ExprRequirement>(Req)) {
+          ER->getExpr()->dump();
+          ValidVisitor(this, T).TraverseStmt(ER->getExpr());
+        }
+        if (auto *NR = llvm::dyn_cast<concepts::NestedRequirement>(Req)) {
+          NR->getConstraintExpr()->dump();
+          believe(NR->getConstraintExpr(), T);
+        }
+      }
+    }
+  }
+
+private:
+  // This visitor infers members of T based on traversing expressions/types
+  // that involve T. It is invoked with code known to be valid for T.
+  class ValidVisitor : public RecursiveASTVisitor<ValidVisitor> {
+    ConceptMembers *Outer;
+    const TemplateTypeParmType *T;
+
+    CallExpr *Caller = nullptr;
+    Expr *Callee = nullptr;
+
+  public:
+    ValidVisitor(ConceptMembers *Outer, const TemplateTypeParmType *T)
+        : Outer(Outer), T(T) {
+      assert(T);
+    }
+
+    bool VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E) {
+      const Type *Base = E->getBaseType().getTypePtr();
+      bool IsArrow = E->isArrow();
+      if (Base->isPointerType() && IsArrow) {
+        IsArrow = false;
+        Base = Base->getPointeeType().getTypePtr();
+      }
+      // Is this actually a member of T?
+      if (!isApprox(Base, T))
+        return true;
+      addValue(E, E->getMember(),
+               IsArrow ? ConceptMemberResult::Arrow : ConceptMemberResult::Dot);
+      return true;
+    }
+
+    bool VisitDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *E) {
+      if (E->getQualifier() && isApprox(E->getQualifier()->getAsType(), T))
+        addValue(E, E->getDeclName(), ConceptMemberResult::Colons);
+      return true;
+    }
+
+    // Record a member we found.
+    void addValue(Expr *E, DeclarationName Name,
+                  ConceptMemberResult::AccessType Operator) {
+      if (!Name.isIdentifier())
+        return;
+      auto &Result = Outer->Results[Name.getAsIdentifierInfo()];
+      Result.Name = Name.getAsIdentifierInfo();
+      Result.Operator = Operator;
+      // It's either function or variable...
+      if (Caller != nullptr && Callee == E) {
+        Result.Kind = ConceptMemberResult::Function;
+        Result.ArgTypes.emplace();
+        for (const auto *Arg : Caller->arguments())
+          Result.ArgTypes->push_back(Arg->getType());
+      } else {
+        Result.Kind = ConceptMemberResult::Variable;
+      }
+    }
+
+    void addType(const IdentifierInfo *Name) {
+      if (!Name)
+        return;
+      auto &Result = Outer->Results[Name];
+      Result.Name = Name;
+      Result.Kind = ConceptMemberResult::Type;
+      Result.Operator = ConceptMemberResult::Colons;
+    }
+
+    bool VisitDependentNameType(DependentNameType *DNT) {
+      const auto *Q = DNT->getQualifier();
+      if (Q && isApprox(Q->getAsType(), T))
+        addType(DNT->getIdentifier());
+      return true;
+    }
+
+    bool VisitNestedNameSpecifier(NestedNameSpecifier *NNS) {
+      const auto *Q = NNS->getPrefix();
+      if (Q && isApprox(Q->getAsType(), T))
+        addType(NNS->getAsIdentifier());
+      // FIXME: also handle T::foo<X>::bar
+      return true;
+    }
+
+    // FIXME also handle T::foo<X>
+
+    // Track the innermost caller/callee relationship so we can tell if a
+    // dependent memberexpr is being called as a function.
+    bool VisitCallExpr(CallExpr *CE) {
+      Caller = CE;
+      Callee = CE->getCallee();
+      return true;
+    }
+  };
+
+  static bool isApprox(const TemplateArgument &Arg, const Type *T) {
+    return Arg.getKind() == TemplateArgument::Type &&
+           isApprox(Arg.getAsType().getTypePtr(), T);
+  }
+
+  static bool isApprox(const Type *T1, const Type *T2) {
+    return T1 && T2 &&
+           T1->getCanonicalTypeUnqualified() ==
+               T2->getCanonicalTypeUnqualified();
+  }
+};
+
+} // namespace
+
 void Sema::CodeCompleteMemberReferenceExpr(Scope *S, Expr *Base,
                                            Expr *OtherOpBase,
                                            SourceLocation OpLoc, bool IsArrow,
                                            bool IsBaseExprStatement,
                                            QualType PreferredType) {
   if (!Base || !CodeCompleter)
     return;
 
auto DoCompletion = [&](Expr *Base, bool IsArrow,
     if (BaseType.isNull())
       return false;
     ExprValueKind BaseKind = Base->getValueKind();
 
     if (IsArrow) {
       if (const PointerType *Ptr = BaseType->getAs<PointerType>()) {
         BaseType = Ptr->getPointeeType();
         BaseKind = VK_LValue;
-      } else if (BaseType->isObjCObjectPointerType())
+      } else if (BaseType->isObjCObjectPointerType() ||
+                 BaseType->isTemplateTypeParmType())
         /*Do nothing*/;
       else
         return false;
     }
 
     if (RecordDecl *RD = getAsRecordDecl(BaseType)) {
       AddRecordMembersCompletionResults(*this, Results, S, BaseType, BaseKind,
                                         RD, std::move(AccessOpFixIt));
+    } else if (const auto *TST =
+                   BaseType->getAs<TemplateSpecializationType>()) {
+      TemplateName TN = TST->getTemplateName();
+      if (const auto *TD =
+              dyn_cast_or_null<ClassTemplateDecl>(TN.getAsTemplateDecl())) {
+        CXXRecordDecl *RD = TD->getTemplatedDecl();
+        AddRecordMembersCompletionResults(*this, Results, S, BaseType, BaseKind,
+                                          RD, std::move(AccessOpFixIt));
+      }
+    } else if (const auto *ICNT = BaseType->getAs<InjectedClassNameType>()) {
+      if (auto *RD = ICNT->getDecl())
+        AddRecordMembersCompletionResults(*this, Results, S, BaseType, BaseKind,
+                                          RD, std::move(AccessOpFixIt));
+    } else if (const auto *TTPT = llvm::dyn_cast<TemplateTypeParmType>(
+                   BaseType.getTypePtr())) {
+      ConceptMembers Members(*TTPT, S);
+      // Add all as patterns...
+      for (const auto &R : Members.results()) {
+        if (R.Operator !=
+            (IsArrow ? ConceptMemberResult::Arrow : ConceptMemberResult::Dot))
+          continue;
+        CodeCompletionResult Result(
+            R.render(*this, CodeCompleter->getAllocator(),
+                     CodeCompleter->getCodeCompletionTUInfo()));
+        if (AccessOpFixIt)
+          Result.FixIts.push_back(*AccessOpFixIt);
+        Results.AddResult(std::move(Result));
+      }
     } else if (!IsArrow && BaseType->isObjCObjectPointerType()) {
       // Objective-C property reference.
       AddedPropertiesSet AddedProperties;
 
       if (const ObjCObjectPointerType *ObjCPtr =
               BaseType->getAsObjCInterfacePointerType()) {
         // Add property results based on our interface.
         assert(ObjCPtr && "Non-NULL pointer guaranteed above!");
void Sema::CodeCompleteQualifiedId(Scope *S, CXXScopeSpec &SS,
   Results.EnterNewScope();
 
   // The "template" keyword can follow "::" in the grammar, but only
   // put it into the grammar if the nested-name-specifier is dependent.
   NestedNameSpecifier *NNS = SS.getScopeRep();
   if (!Results.empty() && NNS->isDependent())
     Results.AddResult("template");
 
+  // If the scope is a concept-constrained type parameter, infer nested
+  // members based on the constraints.
+  // FIXME: doesn't actually work, we get called with an invalid SS instead :-(
+  if (const auto *TTPT =
+          llvm::dyn_cast_or_null<TemplateTypeParmType>(NNS->getAsType())) {
+    TTPT->dump();
+    ConceptMembers Members(*TTPT, S);
+    for (const auto &R : Members.results()) {
+      if (R.Operator != ConceptMemberResult::Colons)
+        continue;
+      Results.AddResult(CodeCompletionResult(
+          R.render(*this, CodeCompleter->getAllocator(),
+                   CodeCompleter->getCodeCompletionTUInfo())));
+    }
+  }
+
   // Add calls to overridden virtual functions, if there are any.
   //
   // FIXME: This isn't wonderful, because we don't know whether we're actually
   // in a context that permits expressions. This is a general issue with
   // qualified-id completions.
   if (!EnteringContext)
     MaybeAddOverrideCalls(*this, Ctx, Results);
   Results.ExitScope();