Introduce Registry::getCompletions.

[pcc]

Summary

This returns a list of valid (and useful) completions for a context (a list
of outer matchers), ordered by decreasing relevance then alphabetically. It
will be used by the matcher parser to implement completion.

[sbenza]

include/clang/AST/ASTTypeTraits.h

67

Comment what is the meaning of A<B. It can't be used as a meaningful comparison between the types.

include/clang/ASTMatchers/Dynamic/Registry.h

38

StringRef

lib/ASTMatchers/Dynamic/Marshallers.h

207

100?

258

Comment these.

363

This is repeated with FixedArgCountMatcherDesc. Factor this out into a function.

382

You could make this field also const if BuildReturnTypeVector<> returned the vector instead of taking by ref.

541

Please add a check that all the overloads have the same properties.

549

This has the potential to give invalid autocomplete.
For example, the first argument only matches Overloads[0], but the second argument autocompletes with Overloads[1] ArgKind.
At least add a note about it. We might want to fix it somehow later on.

605

You are not using LLVM_OVERRIDE consistently.
You are missing it in many of the overrides.

663

Is the overload above used if you add this one?

[pcc]

• Address reviewer comments

include/clang/AST/ASTTypeTraits.h

67

Done.

include/clang/ASTMatchers/Dynamic/Registry.h

38

Done.

lib/ASTMatchers/Dynamic/Marshallers.h

207

Arbitrary. I think that if we have an inheritance hierarchy 100 levels deep we probably have bigger problems than this constant :)

258

I think the function names are self explanatory.

363

Done.

382

Probably, but I don't think it matters too much whether this is const or not. All the member functions are const qualified anyway.

541

Done.

549

Done. (This also applies to other matcher descriptors so I added the note to the base class.) This will probably have to be done by passing more context information through to getArgKinds.

605

I'm using it consistently wherever I intend to override a non-pure virtual function.

663

No. We check on lines 409 and 410 of RegistryTest.cpp that the correct overload is chosen for dyncast matchers.

[sbenza]

lib/ASTMatchers/Dynamic/Marshallers.h

605

I see. Shouldn't it be used for overriding any virtual method, even if it is pure?

663

What I mean is that if the overload above is not really used, we should get rid of it, and merge VariadicFuncMatcherDesc with DynCastAllOfMatcherDesc.

[pcc]

lib/ASTMatchers/Dynamic/Marshallers.h

605

Well, it's most useful when overriding non-pure virtual member functions because it helps detect otherwise-conforming mistakes.

663

It's currently used by TypeTraversePolymorphicMatchers and VariadicAllOfMatchers.

[pcc]

Rebase.

[sbenza]

LG for me.
@klimek, do you have comments?

[pcc]

Closed by commit rL199950 (authored by @pcc).

include/clang/AST/ASTTypeTraits.h

public:
   /// \brief Returns \c true if \c this is a base kind of (or same as) \c Other.
   /// \param Distance If non-null, used to return the distance between \c this
   /// and \c Other in the class hierarchy.
   bool isBaseOf(ASTNodeKind Other, unsigned *Distance = 0) const;
 
   /// \brief String representation of the kind.
   StringRef asStringRef() const;
 
+  bool operator<(const ASTNodeKind &Other) const {
+    return KindId < Other.KindId;
+  }
+
 private:
   /// \brief Kind ids.
   ///
   /// Includes all possible base and derived kinds.
   enum NodeKindId {
     NKI_None,
     NKI_CXXCtorInitializer,
     NKI_TemplateArgument,

 #define DECL(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Decl)
 #include "clang/AST/DeclNodes.inc"
 #define STMT(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED)
 #include "clang/AST/StmtNodes.inc"
 #define TYPE(DERIVED, BASE) KIND_TO_KIND_ID(DERIVED##Type)
 #include "clang/AST/TypeNodes.def"
 #undef KIND_TO_KIND_ID
 
+inline raw_ostream &operator<<(raw_ostream &OS, ASTNodeKind K) {
+  OS << K.asStringRef();
+  return OS;
+}
+
 /// \brief A dynamically typed AST node container.
 ///
 /// Stores an AST node in a type safe way. This allows writing code that
 /// works with different kinds of AST nodes, despite the fact that they don't
 /// have a common base class.
 ///
 /// Use \c create(Node) to create a \c DynTypedNode from an AST node,
 /// and \c get<T>() to retrieve the node as type T if the types match.

include/clang/ASTMatchers/Dynamic/Registry.h

 namespace dynamic {
 
 namespace internal {
 class MatcherDesc;
 }
 
 typedef const internal::MatcherDesc *MatcherCtor;
 
+struct MatcherCompletion {
+  MatcherCompletion() {}
+  MatcherCompletion(std::string TypedText, std::string MatcherDecl)
+      : TypedText(TypedText), MatcherDecl(MatcherDecl) {}
+
+  /// \brief The text to type to select this matcher.
+  std::string TypedText;
+
+  /// \brief The "declaration" of the matcher, with type information.
+  std::string MatcherDecl;
+
+  bool operator==(const MatcherCompletion &Other) const {
+    return TypedText == Other.TypedText && MatcherDecl == Other.MatcherDecl;
+  }
+};
+
 class Registry {
 public:
   /// \brief Look up a matcher in the registry by name,
   ///
   /// \return An opaque pointer which may be used to refer to the matcher
   /// constructor, or null if not found.  In that case \c Error will contain the
   /// description of the error.
   static MatcherCtor lookupMatcherCtor(StringRef MatcherName,
                                        const SourceRange &NameRange,
                                        Diagnostics *Error);
 
+  /// \brief Compute the list of completions for \p Context.
+  ///
+  /// Each element of \p Context represents a matcher invocation, going from
+  /// outermost to innermost. Elements are pairs consisting of a reference to the
+  /// matcher constructor and the index of the next element in the argument list
+  /// of that matcher (or for the last element, the index of the completion
+  /// point in the argument list). An empty list requests completion for the
+  /// root matcher.
+  ///
+  /// The completions are ordered first by decreasing relevance, then
+  /// alphabetically.  Relevance is determined by how closely the matcher's
+  /// type matches that of the context. For example, if the innermost matcher
+  /// takes a FunctionDecl matcher, the FunctionDecl matchers are returned
+  /// first, followed by the ValueDecl matchers, then NamedDecl, then Decl, then
+  /// polymorphic matchers.
+  ///
+  /// Matchers which are technically convertible to the innermost context but
+  /// which would match either all or no nodes are excluded. For example,
+  /// namedDecl and varDecl are excluded in a FunctionDecl context, because
+  /// those matchers would match respectively all or no nodes in such a context.
+  static std::vector<MatcherCompletion>
+  getCompletions(llvm::ArrayRef<std::pair<MatcherCtor, unsigned> > Context);
+
   /// \brief Construct a matcher from the registry.
   ///
   /// \param MatcherName The name of the matcher to instantiate.
   ///
   /// \param NameRange The location of the name in the matcher source.
   ///   Useful for error reporting.
   ///
   /// \param Args The argument list for the matcher. The number and types of the

lib/ASTMatchers/Dynamic/Marshallers.h

 #include "llvm/Support/type_traits.h"
 
 namespace clang {
 namespace ast_matchers {
 namespace dynamic {
 
 namespace internal {
 
+struct ArgKind {
+  enum Kind {
+    AK_Matcher,
+    AK_Unsigned,
+    AK_String
+  };
+  ArgKind(Kind K)
+      : K(K) {}
+  ArgKind(ast_type_traits::ASTNodeKind MatcherKind)
+      : K(AK_Matcher), MatcherKind(MatcherKind) {}
+
+  std::string asString() const {
+    switch (getArgKind()) {
+    case AK_Matcher:
+      return (Twine("Matcher<") + MatcherKind.asStringRef() + ">").str();
+    case AK_Unsigned:
+      return "unsigned";
+    case AK_String:
+      return "string";
+    }
+  }
+
+  Kind getArgKind() const { return K; }
+  ast_type_traits::ASTNodeKind getMatcherKind() const {
+    assert(K == AK_Matcher);
+    return MatcherKind;
+  }
+
+  bool operator<(const ArgKind &Other) const {
+    if (K == AK_Matcher && Other.K == AK_Matcher)
+      return MatcherKind < Other.MatcherKind;
+    return K < Other.K;
+  }
+
+private:
+  Kind K;
+  ast_type_traits::ASTNodeKind MatcherKind;
+};
+
 /// \brief Helper template class to just from argument type to the right is/get
 ///   functions in VariantValue.
 /// Used to verify and extract the matcher arguments below.
 template <class T> struct ArgTypeTraits;
 template <class T> struct ArgTypeTraits<const T &> : public ArgTypeTraits<T> {
 };
 
 template <> struct ArgTypeTraits<std::string> {
-  static StringRef asString() { return "String"; }
   static bool is(const VariantValue &Value) { return Value.isString(); }
   static const std::string &get(const VariantValue &Value) {
     return Value.getString();
   }
+  static ArgKind getKind() {
+    return ArgKind(ArgKind::AK_String);
+  }
 };
 
 template <>
 struct ArgTypeTraits<StringRef> : public ArgTypeTraits<std::string> {
 };
 
 template <class T> struct ArgTypeTraits<ast_matchers::internal::Matcher<T> > {
-  static std::string asString() {
-    return (Twine("Matcher<") +
-            ast_type_traits::ASTNodeKind::getFromNodeKind<T>().asStringRef() +
-            ">").str();
-  }
   static bool is(const VariantValue &Value) {
     return Value.isMatcher() && Value.getMatcher().hasTypedMatcher<T>();
   }
   static ast_matchers::internal::Matcher<T> get(const VariantValue &Value) {
     return Value.getMatcher().getTypedMatcher<T>();
   }
+  static ArgKind getKind() {
+    return ArgKind(ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
+  }
 };
 
 template <> struct ArgTypeTraits<unsigned> {
-  static std::string asString() { return "Unsigned"; }
   static bool is(const VariantValue &Value) { return Value.isUnsigned(); }
   static unsigned get(const VariantValue &Value) {
     return Value.getUnsigned();
   }
+  static ArgKind getKind() {
+    return ArgKind(ArgKind::AK_Unsigned);
+  }
 };
 
 /// \brief Matcher descriptor interface.
 ///
 /// Provides a \c create() method that constructs the matcher from the provided
-/// arguments.
+/// arguments, and various other methods for type introspection.
 class MatcherDesc {
 public:
   virtual ~MatcherDesc() {}
   virtual VariantMatcher create(const SourceRange &NameRange,
                                 ArrayRef<ParserValue> Args,
                                 Diagnostics *Error) const = 0;
+
+  /// Returns whether the matcher is variadic. Variadic matchers can take any
+  /// number of arguments, but they must be of the same type.
+  virtual bool isVariadic() const = 0;
+
+  /// Returns the number of arguments accepted by the matcher if not variadic.
+  virtual unsigned getNumArgs() const = 0;
+
+  /// Given that the matcher is being converted to type \p ThisKind, append the
+  /// set of argument types accepted for argument \p ArgNo to \p ArgKinds.
+  virtual void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                           std::vector<ArgKind> &ArgKinds) const = 0;
+
+  /// Returns whether this matcher is convertible to the given type.  If it is
+  /// so convertible, store in *Specificity a value corresponding to the
+  /// "specificity" of the converted matcher to the given context, and in
+  /// *LeastDerivedKind the least derived matcher kind which would result in the
+  /// same matcher overload.  Zero specificity indicates that this conversion
+  /// would produce a trivial matcher that will either always or never match.
+  /// Such matchers are excluded from code completion results.
+  virtual bool isConvertibleTo(
+      ast_type_traits::ASTNodeKind Kind, unsigned *Specificity = 0,
+      ast_type_traits::ASTNodeKind *LeastDerivedKind = 0) const = 0;
+
+  /// Returns whether the matcher will, given a matcher of any type T, yield a
+  /// matcher of type T.
+  virtual bool isPolymorphic() const { return false; }
 };
 
 /// \brief Simple callback implementation. Marshaller and function are provided.
 ///
 /// This class wraps a function of arbitrary signature and a marshaller
 /// function into a MatcherDesc.
 /// The marshaller is in charge of taking the VariantValue arguments, checking
 /// their types, unpacking them and calling the underlying function.
 class FixedArgCountMatcherDesc : public MatcherDesc {
 public:
   typedef VariantMatcher (*MarshallerType)(void (*Func)(),
                                            StringRef MatcherName,
                                            const SourceRange &NameRange,
                                            ArrayRef<ParserValue> Args,
                                            Diagnostics *Error);
 
   /// \param Marshaller Function to unpack the arguments and call \c Func
   /// \param Func Matcher construct function. This is the function that
   ///   compile-time matcher expressions would use to create the matcher.
-  FixedArgCountMatcherDesc(MarshallerType Marshaller, void (*Func)(),
-                           StringRef MatcherName)
-      : Marshaller(Marshaller), Func(Func), MatcherName(MatcherName) {}
+  /// \param RetKinds The list of matcher types to which the matcher is
+  ///   convertible.
+  /// \param ArgKinds The types of the arguments this matcher takes.
+  FixedArgCountMatcherDesc(
+      MarshallerType Marshaller, void (*Func)(), StringRef MatcherName,
+      llvm::ArrayRef<ast_type_traits::ASTNodeKind> RetKinds,
+      llvm::ArrayRef<ArgKind> ArgKinds)
+      : Marshaller(Marshaller), Func(Func), MatcherName(MatcherName),
+        RetKinds(RetKinds.begin(), RetKinds.end()),
+        ArgKinds(ArgKinds.begin(), ArgKinds.end()) {}
 
   VariantMatcher create(const SourceRange &NameRange,
                         ArrayRef<ParserValue> Args, Diagnostics *Error) const {
     return Marshaller(Func, MatcherName, NameRange, Args, Error);
   }
 
+  bool isVariadic() const { return false; }
+  unsigned getNumArgs() const { return ArgKinds.size(); }
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const {
+    Kinds.push_back(ArgKinds[ArgNo]);
+  }
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+                       ast_type_traits::ASTNodeKind *LeastDerivedKind) const {
+    for (std::vector<ast_type_traits::ASTNodeKind>::const_iterator
+             i = RetKinds.begin(),
+             e = RetKinds.end();
+         i != e; ++i) {
+      unsigned Distance;
+      if (i->isBaseOf(Kind, &Distance)) {
+        if (Specificity)
+          *Specificity = 100 - Distance;
+        if (LeastDerivedKind)
+          *LeastDerivedKind = *i;
+        return true;
+      }
+    }
+    return false;
+  }
+
 private:
   const MarshallerType Marshaller;
   void (* const Func)();
   const std::string MatcherName;
+  const std::vector<ast_type_traits::ASTNodeKind> RetKinds;
+  const std::vector<ArgKind> ArgKinds;
 };
 
-/// \brief Simple callback implementation. Free function is wrapped.
+/// \brief Helper methods to extract and merge all possible typed matchers
+/// out of the polymorphic object.
+template <class PolyMatcher>
+static void mergePolyMatchers(const PolyMatcher &Poly,
+                              std::vector<DynTypedMatcher> &Out,
+                              ast_matchers::internal::EmptyTypeList) {}
+
+template <class PolyMatcher, class TypeList>
+static void mergePolyMatchers(const PolyMatcher &Poly,
+                              std::vector<DynTypedMatcher> &Out, TypeList) {
+  Out.push_back(ast_matchers::internal::Matcher<typename TypeList::head>(Poly));
+  mergePolyMatchers(Poly, Out, typename TypeList::tail());
+}
+
+/// \brief Convert the return values of the functions into a VariantMatcher.
 ///
-/// This class simply wraps a free function with the right signature to export
+/// There are 2 cases right now: The return value is a Matcher<T> or is a
+/// polymorphic matcher. For the former, we just construct the VariantMatcher.
+/// For the latter, we instantiate all the possible Matcher<T> of the poly
+/// matcher.
+static VariantMatcher outvalueToVariantMatcher(const DynTypedMatcher &Matcher) {
+  return VariantMatcher::SingleMatcher(Matcher);
+}
+
+template <typename T>
+static VariantMatcher outvalueToVariantMatcher(const T &PolyMatcher,
+                                               typename T::ReturnTypes * =
+                                                   NULL) {
+  std::vector<DynTypedMatcher> Matchers;
+  mergePolyMatchers(PolyMatcher, Matchers, typename T::ReturnTypes());
+  VariantMatcher Out = VariantMatcher::PolymorphicMatcher(Matchers);
+  return Out;
+}
+
+template <typename T>
+void buildReturnTypeVectorFromTypeList(
+    std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {
+  RetTypes.push_back(
+      ast_type_traits::ASTNodeKind::getFromNodeKind<typename T::head>());
+  buildReturnTypeVectorFromTypeList<typename T::tail>(RetTypes);
+}
+
+template <>
+void buildReturnTypeVectorFromTypeList<ast_matchers::internal::EmptyTypeList>(
+    std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {}
+
+template <typename T>
+struct BuildReturnTypeVector {
+  static void build(std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {
+    buildReturnTypeVectorFromTypeList<typename T::ReturnTypes>(RetTypes);
+  }
+};
+
+template <typename T>
+struct BuildReturnTypeVector<ast_matchers::internal::Matcher<T> > {
+  static void build(std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {
+    RetTypes.push_back(ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
+  }
+};
+
+template <typename T>
+struct BuildReturnTypeVector<ast_matchers::internal::BindableMatcher<T> > {
+  static void build(std::vector<ast_type_traits::ASTNodeKind> &RetTypes) {
+    RetTypes.push_back(ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
+  }
+};
+
+/// \brief Variadic marshaller function.
+template <typename ResultT, typename ArgT,
+          ResultT (*Func)(ArrayRef<const ArgT *>)>
+VariantMatcher
+variadicMatcherDesc(StringRef MatcherName, const SourceRange &NameRange,
+                    ArrayRef<ParserValue> Args, Diagnostics *Error) {
+  ArgT **InnerArgs = new ArgT *[Args.size()]();
+
+  bool HasError = false;
+  for (size_t i = 0, e = Args.size(); i != e; ++i) {
+    typedef ArgTypeTraits<ArgT> ArgTraits;
+    const ParserValue &Arg = Args[i];
+    const VariantValue &Value = Arg.Value;
+    if (!ArgTraits::is(Value)) {
+      Error->addError(Arg.Range, Error->ET_RegistryWrongArgType)
+          << (i + 1) << ArgTraits::getKind().asString() << Value.getTypeAsString();
+      HasError = true;
+      break;
+    }
+    InnerArgs[i] = new ArgT(ArgTraits::get(Value));
+  }
+
+  VariantMatcher Out;
+  if (!HasError) {
+    Out = outvalueToVariantMatcher(
+        Func(ArrayRef<const ArgT *>(InnerArgs, Args.size())));
+  }
+
+  for (size_t i = 0, e = Args.size(); i != e; ++i) {
+    delete InnerArgs[i];
+  }
+  delete[] InnerArgs;
+  return Out;
+}
+
+/// \brief Matcher descriptor for variadic functions.
+///
+/// This class simply wraps a VariadicFunction with the right signature to export
 /// it as a MatcherDesc.
 /// This allows us to have one implementation of the interface for as many free
 /// functions as we want, reducing the number of symbols and size of the
 /// object file.
-class FreeFuncMatcherDesc : public MatcherDesc {
+class VariadicFuncMatcherDesc : public MatcherDesc {
 public:
   typedef VariantMatcher (*RunFunc)(StringRef MatcherName,
                                     const SourceRange &NameRange,
                                     ArrayRef<ParserValue> Args,
                                     Diagnostics *Error);
 
-  FreeFuncMatcherDesc(RunFunc Func, StringRef MatcherName)
-      : Func(Func), MatcherName(MatcherName.str()) {}
+  template <typename ResultT, typename ArgT,
+            ResultT (*F)(ArrayRef<const ArgT *>)>
+  VariadicFuncMatcherDesc(llvm::VariadicFunction<ResultT, ArgT, F> Func,
+                          StringRef MatcherName)
+      : Func(&variadicMatcherDesc<ResultT, ArgT, F>),
+        MatcherName(MatcherName.str()),
+        ArgsKind(ArgTypeTraits<ArgT>::getKind()) {
+    BuildReturnTypeVector<ResultT>::build(RetKinds);
+  }
 
   VariantMatcher create(const SourceRange &NameRange,
                         ArrayRef<ParserValue> Args, Diagnostics *Error) const {
     return Func(MatcherName, NameRange, Args, Error);
   }
 
+  bool isVariadic() const { return true; }
+  unsigned getNumArgs() const { return 0; }
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const {
+    Kinds.push_back(ArgsKind);
+  }
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+                       ast_type_traits::ASTNodeKind *LeastDerivedKind) const {
+    for (std::vector<ast_type_traits::ASTNodeKind>::const_iterator
+             i = RetKinds.begin(),
+             e = RetKinds.end();
+         i != e; ++i) {
+      unsigned Distance;
+      if (i->isBaseOf(Kind, &Distance)) {
+        if (Specificity)
+          *Specificity = 100 - Distance;
+        if (LeastDerivedKind)
+          *LeastDerivedKind = *i;
+        return true;
+      }
+    }
+    return false;
+  }
+
 private:
   const RunFunc Func;
   const std::string MatcherName;
+  std::vector<ast_type_traits::ASTNodeKind> RetKinds;
+  const ArgKind ArgsKind;
+};
+
+/// \brief Return CK_Trivial when appropriate for VariadicDynCastAllOfMatchers.
+class DynCastAllOfMatcherDesc : public VariadicFuncMatcherDesc {
+public:
+  template <typename BaseT, typename DerivedT>
+  DynCastAllOfMatcherDesc(
+      ast_matchers::internal::VariadicDynCastAllOfMatcher<BaseT, DerivedT> Func,
+      StringRef MatcherName)
+      : VariadicFuncMatcherDesc(Func, MatcherName),
+        DerivedKind(ast_type_traits::ASTNodeKind::getFromNodeKind<DerivedT>()) {
+  }
+
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+                       ast_type_traits::ASTNodeKind *LeastDerivedKind) const
+      LLVM_OVERRIDE {
+    // If Kind is not a base of DerivedKind, either DerivedKind is a base of
+    // Kind (in which case the match will always succeed) or Kind and
+    // DerivedKind are unrelated (in which case it will always fail), so set
+    // Specificity to 0.
+    if (VariadicFuncMatcherDesc::isConvertibleTo(Kind, Specificity,
+                                                 LeastDerivedKind)) {
+      if (Kind.isSame(DerivedKind) || !Kind.isBaseOf(DerivedKind)) {
+        if (Specificity)
+          *Specificity = 0;
+      }
+      return true;
+    } else {
+      return false;
+    }
+  }
+
+private:
+  const ast_type_traits::ASTNodeKind DerivedKind;
 };
 
 /// \brief Helper macros to check the arguments on all marshaller functions.
 #define CHECK_ARG_COUNT(count)                                                 \
   if (Args.size() != count) {                                                  \
     Error->addError(NameRange, Error->ET_RegistryWrongArgCount)                \
         << count << Args.size();                                               \
     return VariantMatcher();                                                   \
   }
 
 #define CHECK_ARG_TYPE(index, type)                                            \
   if (!ArgTypeTraits<type>::is(Args[index].Value)) {                           \
     Error->addError(Args[index].Range, Error->ET_RegistryWrongArgType)         \
-        << (index + 1) << ArgTypeTraits<type>::asString()                      \
+        << (index + 1) << ArgTypeTraits<type>::getKind().asString()            \
         << Args[index].Value.getTypeAsString();                                \
     return VariantMatcher();                                                   \
   }
 
-/// \brief Helper methods to extract and merge all possible typed matchers
-/// out of the polymorphic object.
-template <class PolyMatcher>
-static void mergePolyMatchers(const PolyMatcher &Poly,
-                              std::vector<DynTypedMatcher> &Out,
-                              ast_matchers::internal::EmptyTypeList) {}
-
-template <class PolyMatcher, class TypeList>
-static void mergePolyMatchers(const PolyMatcher &Poly,
-                              std::vector<DynTypedMatcher> &Out, TypeList) {
-  Out.push_back(ast_matchers::internal::Matcher<typename TypeList::head>(Poly));
-  mergePolyMatchers(Poly, Out, typename TypeList::tail());
-}
-
-/// \brief Convert the return values of the functions into a VariantMatcher.
-///
-/// There are 2 cases right now: The return value is a Matcher<T> or is a
-/// polymorphic matcher. For the former, we just construct the VariantMatcher.
-/// For the latter, we instantiate all the possible Matcher<T> of the poly
-/// matcher.
-static VariantMatcher outvalueToVariantMatcher(const DynTypedMatcher &Matcher) {
-  return VariantMatcher::SingleMatcher(Matcher);
-}
-
-template <typename T>
-static VariantMatcher outvalueToVariantMatcher(const T &PolyMatcher,
-                                               typename T::ReturnTypes * =
-                                                   NULL) {
-  std::vector<DynTypedMatcher> Matchers;
-  mergePolyMatchers(PolyMatcher, Matchers, typename T::ReturnTypes());
-  VariantMatcher Out = VariantMatcher::PolymorphicMatcher(Matchers);
-  return Out;
-}
 
 /// \brief 0-arg marshaller function.
 template <typename ReturnType>
 static VariantMatcher matcherMarshall0(void (*Func)(), StringRef MatcherName,
                                        const SourceRange &NameRange,
                                        ArrayRef<ParserValue> Args,
                                        Diagnostics *Error) {
   typedef ReturnType (*FuncType)();
static VariantMatcher matcherMarshall2(void (*Func)(), StringRef MatcherName,
   return outvalueToVariantMatcher(reinterpret_cast<FuncType>(Func)(
       ArgTypeTraits<ArgType1>::get(Args[0].Value),
       ArgTypeTraits<ArgType2>::get(Args[1].Value)));
 }
 
 #undef CHECK_ARG_COUNT
 #undef CHECK_ARG_TYPE
 
-/// \brief Variadic marshaller function.
-template <typename ResultT, typename ArgT,
-          ResultT (*Func)(ArrayRef<const ArgT *>)>
-VariantMatcher variadicMatcherDesc(StringRef MatcherName,
-                                   const SourceRange &NameRange,
-                                   ArrayRef<ParserValue> Args,
-                                   Diagnostics *Error) {
-  ArgT **InnerArgs = new ArgT *[Args.size()]();
-
-  bool HasError = false;
-  for (size_t i = 0, e = Args.size(); i != e; ++i) {
-    typedef ArgTypeTraits<ArgT> ArgTraits;
-    const ParserValue &Arg = Args[i];
-    const VariantValue &Value = Arg.Value;
-    if (!ArgTraits::is(Value)) {
-      Error->addError(Arg.Range, Error->ET_RegistryWrongArgType)
-          << (i + 1) << ArgTraits::asString() << Value.getTypeAsString();
-      HasError = true;
-      break;
-    }
-    InnerArgs[i] = new ArgT(ArgTraits::get(Value));
-  }
-
-  VariantMatcher Out;
-  if (!HasError) {
-    Out = outvalueToVariantMatcher(
-        Func(ArrayRef<const ArgT *>(InnerArgs, Args.size())));
-  }
-
-  for (size_t i = 0, e = Args.size(); i != e; ++i) {
-    delete InnerArgs[i];
-  }
-  delete[] InnerArgs;
-  return Out;
-}
-
 /// \brief Helper class used to collect all the possible overloads of an
 ///   argument adaptative matcher function.
 template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
           typename FromTypes, typename ToTypes>
 class AdaptativeOverloadCollector {
 public:
   AdaptativeOverloadCollector(StringRef Name, std::vector<MatcherDesc *> &Out)
       : Name(Name), Out(Out) {
virtual VariantMatcher create(const SourceRange &NameRange,
     if (Constructed.size() > 1) {
       // More than one constructed. It is ambiguous.
       Error->addError(NameRange, Error->ET_RegistryAmbiguousOverload);
       return VariantMatcher();
     }
     return Constructed[0];
   }
 
- private:
+  bool isVariadic() const { return Overloads[0]->isVariadic(); }
+  unsigned getNumArgs() const { return Overloads[0]->getNumArgs(); }
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const {
+    for (std::vector<MatcherDesc *>::const_iterator I = Overloads.begin(),
+                                                    E = Overloads.end();
+         I != E; ++I) {
+      if ((*I)->isConvertibleTo(ThisKind))
+        (*I)->getArgKinds(ThisKind, ArgNo, Kinds);
+    }
+  }
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+                       ast_type_traits::ASTNodeKind *LeastDerivedKind) const {
+    for (std::vector<MatcherDesc *>::const_iterator I = Overloads.begin(),
+                                                    E = Overloads.end();
+         I != E; ++I) {
+      if ((*I)->isConvertibleTo(Kind, Specificity, LeastDerivedKind))
+        return true;
+    }
+    return false;
+  }
+
   std::vector<MatcherDesc *> Overloads;
 };
 
 /// \brief Variadic operator marshaller function.
 class VariadicOperatorMatcherDesc : public MatcherDesc {
 public:
   typedef ast_matchers::internal::VariadicOperatorFunction VarFunc;
   VariadicOperatorMatcherDesc(VarFunc Func, StringRef MatcherName)
for (size_t i = 0, e = Args.size(); i != e; ++i) {
             << (i + 1) << "Matcher<>" << Value.getTypeAsString();
         return VariantMatcher();
       }
       InnerArgs.push_back(Value.getMatcher());
     }
     return VariantMatcher::VariadicOperatorMatcher(Func, InnerArgs);
   }
 
+  bool isVariadic() const { return true; }
+  unsigned getNumArgs() const { return 0; }
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const {
+    Kinds.push_back(ThisKind);
+  }
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+                       ast_type_traits::ASTNodeKind *LeastDerivedKind) const {
+    if (Specificity)
+      *Specificity = 1;
+    if (LeastDerivedKind)
+      *LeastDerivedKind = Kind;
+    return true;
+  }
+  bool isPolymorphic() const LLVM_OVERRIDE { return true; }
+
 private:
   const VarFunc Func;
   const StringRef MatcherName;
 };
 
-
 /// Helper functions to select the appropriate marshaller functions.
 /// They detect the number of arguments, arguments types and return type.
 
 /// \brief 0-arg overload
 template <typename ReturnType>
 MatcherDesc *makeMatcherAutoMarshall(ReturnType (*Func)(),
                                      StringRef MatcherName) {
-  return new FixedArgCountMatcherDesc(matcherMarshall0<ReturnType>,
-                                      reinterpret_cast<void (*)()>(Func),
-                                      MatcherName);
+  std::vector<ast_type_traits::ASTNodeKind> RetTypes;
+  BuildReturnTypeVector<ReturnType>::build(RetTypes);
+  return new FixedArgCountMatcherDesc(
+      matcherMarshall0<ReturnType>, reinterpret_cast<void (*)()>(Func),
+      MatcherName, RetTypes, llvm::ArrayRef<ArgKind>());
 }
 
 /// \brief 1-arg overload
 template <typename ReturnType, typename ArgType1>
 MatcherDesc *makeMatcherAutoMarshall(ReturnType (*Func)(ArgType1),
                                      StringRef MatcherName) {
+  std::vector<ast_type_traits::ASTNodeKind> RetTypes;
+  BuildReturnTypeVector<ReturnType>::build(RetTypes);
+  ArgKind AK = ArgTypeTraits<ArgType1>::getKind();
   return new FixedArgCountMatcherDesc(matcherMarshall1<ReturnType, ArgType1>,
                                       reinterpret_cast<void (*)()>(Func),
-                                      MatcherName);
+                                      MatcherName, RetTypes, AK);
 }
 
 /// \brief 2-arg overload
 template <typename ReturnType, typename ArgType1, typename ArgType2>
 MatcherDesc *makeMatcherAutoMarshall(ReturnType (*Func)(ArgType1, ArgType2),
                                      StringRef MatcherName) {
+  std::vector<ast_type_traits::ASTNodeKind> RetTypes;
+  BuildReturnTypeVector<ReturnType>::build(RetTypes);
+  ArgKind AKs[] = { ArgTypeTraits<ArgType1>::getKind(),
+                    ArgTypeTraits<ArgType2>::getKind() };
   return new FixedArgCountMatcherDesc(
       matcherMarshall2<ReturnType, ArgType1, ArgType2>,
-      reinterpret_cast<void (*)()>(Func), MatcherName);
+      reinterpret_cast<void (*)()>(Func), MatcherName, RetTypes, AKs);
 }
 
 /// \brief Variadic overload.
 template <typename ResultT, typename ArgT,
           ResultT (*Func)(ArrayRef<const ArgT *>)>
-MatcherDesc *makeMatcherAutoMarshall(
-    llvm::VariadicFunction<ResultT, ArgT, Func> VarFunc,
+MatcherDesc *
+makeMatcherAutoMarshall(llvm::VariadicFunction<ResultT, ArgT, Func> VarFunc,
+                        StringRef MatcherName) {
+  return new VariadicFuncMatcherDesc(VarFunc, MatcherName);
+}
+
+/// \brief Overload for VariadicDynCastAllOfMatchers.
+///
+/// Not strictly necessary, but DynCastAllOfMatcherDesc gives us better
+/// completion results for that type of matcher.
+template <typename BaseT, typename DerivedT>
+MatcherDesc *
+makeMatcherAutoMarshall(ast_matchers::internal::VariadicDynCastAllOfMatcher<
+                            BaseT, DerivedT> VarFunc,
                         StringRef MatcherName) {
-  return new FreeFuncMatcherDesc(&variadicMatcherDesc<ResultT, ArgT, Func>,
-                                 MatcherName);
+  return new DynCastAllOfMatcherDesc(VarFunc, MatcherName);
 }
 
 /// \brief Argument adaptative overload.
 template <template <typename ToArg, typename FromArg> class ArgumentAdapterT,
           typename FromTypes, typename ToTypes>
 MatcherDesc *makeMatcherAutoMarshall(
     ast_matchers::internal::ArgumentAdaptingMatcherFunc<ArgumentAdapterT,
                                                         FromTypes, ToTypes>,

lib/ASTMatchers/Dynamic/Registry.cpp

 //===--- Registry.cpp - Matcher registry -------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===------------------------------------------------------------===//
 ///
 /// \file
 /// \brief Registry map populated at static initialization time.
 ///
 //===------------------------------------------------------------===//
 
 #include "clang/ASTMatchers/Dynamic/Registry.h"
 
+#include <set>
 #include <utility>
 
 #include "Marshallers.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ManagedStatic.h"
 
+using namespace clang::ast_type_traits;
+
 namespace clang {
 namespace ast_matchers {
 namespace dynamic {
 namespace {
 
 using internal::MatcherDesc;
 
 typedef llvm::StringMap<const MatcherDesc *> ConstructorMap;
MatcherCtor Registry::lookupMatcherCtor(StringRef MatcherName,
   if (it == RegistryData->constructors().end()) {
     Error->addError(NameRange, Error->ET_RegistryNotFound) << MatcherName;
     return 0;
   }
 
   return it->second;
 }
 
+namespace {
+
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
+                              const std::set<ASTNodeKind> &KS) {
+  unsigned Count = 0;
+  for (std::set<ASTNodeKind>::const_iterator I = KS.begin(), E = KS.end();
+       I != E; ++I) {
+    if (I != KS.begin())
+      OS << "|";
+    if (Count++ == 3) {
+      OS << "...";
+      break;
+    }
+    OS << *I;
+  }
+  return OS;
+}
+
+struct ReverseSpecificityThenName {
+  bool operator()(const std::pair<unsigned, std::string> &A,
+                  const std::pair<unsigned, std::string> &B) const {
+    return A.first > B.first || (A.first == B.first && A.second < B.second);
+  }
+};
+
+}
+
+std::vector<MatcherCompletion> Registry::getCompletions(
+    llvm::ArrayRef<std::pair<MatcherCtor, unsigned> > Context) {
+  ASTNodeKind InitialTypes[] = {
+    ASTNodeKind::getFromNodeKind<Decl>(),
+    ASTNodeKind::getFromNodeKind<QualType>(),
+    ASTNodeKind::getFromNodeKind<Type>(),
+    ASTNodeKind::getFromNodeKind<Stmt>(),
+    ASTNodeKind::getFromNodeKind<NestedNameSpecifier>(),
+    ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>(),
+    ASTNodeKind::getFromNodeKind<TypeLoc>()
+  };
+  llvm::ArrayRef<ASTNodeKind> InitialTypesRef(InitialTypes);
+
+  // Starting with the above seed of acceptable top-level matcher types, compute
+  // the acceptable type set for the argument indicated by each context element.
+  std::set<ASTNodeKind> TypeSet(InitialTypesRef.begin(), InitialTypesRef.end());
+  for (llvm::ArrayRef<std::pair<MatcherCtor, unsigned> >::iterator
+           CtxI = Context.begin(),
+           CtxE = Context.end();
+       CtxI != CtxE; ++CtxI) {
+    std::vector<internal::ArgKind> NextTypeSet;
+    for (std::set<ASTNodeKind>::iterator I = TypeSet.begin(), E = TypeSet.end();
+         I != E; ++I) {
+      if (CtxI->first->isConvertibleTo(*I) &&
+          (CtxI->first->isVariadic() ||
+           CtxI->second < CtxI->first->getNumArgs()))
+        CtxI->first->getArgKinds(*I, CtxI->second, NextTypeSet);
+    }
+    TypeSet.clear();
+    for (std::vector<internal::ArgKind>::iterator I = NextTypeSet.begin(),
+                                                  E = NextTypeSet.end();
+         I != E; ++I) {
+      if (I->getArgKind() == internal::ArgKind::AK_Matcher)
+        TypeSet.insert(I->getMatcherKind());
+    }
+  }
+
+  typedef std::map<std::pair<unsigned, std::string>, MatcherCompletion,
+                   ReverseSpecificityThenName> CompletionsTy;
+  CompletionsTy Completions;
+
+  // TypeSet now contains the list of acceptable types for the argument we are
+  // completing.  Search the registry for acceptable matchers.
+  for (ConstructorMap::const_iterator I = RegistryData->constructors().begin(),
+                                      E = RegistryData->constructors().end();
+       I != E; ++I) {
+    std::set<ASTNodeKind> RetKinds;
+    unsigned NumArgs = I->second->isVariadic() ? 1 : I->second->getNumArgs();
+    bool IsPolymorphic = I->second->isPolymorphic();
+    std::vector<std::vector<internal::ArgKind> > ArgsKinds(NumArgs);
+    unsigned MaxSpecificity = 0;
+    for (std::set<ASTNodeKind>::iterator TI = TypeSet.begin(),
+                                         TE = TypeSet.end();
+         TI != TE; ++TI) {
+      unsigned Specificity;
+      ASTNodeKind LeastDerivedKind;
+      if (I->second->isConvertibleTo(*TI, &Specificity, &LeastDerivedKind)) {
+        if (MaxSpecificity < Specificity)
+          MaxSpecificity = Specificity;
+        RetKinds.insert(LeastDerivedKind);
+        for (unsigned Arg = 0; Arg != NumArgs; ++Arg)
+          I->second->getArgKinds(*TI, Arg, ArgsKinds[Arg]);
+        if (IsPolymorphic)
+          break;
+      }
+    }
+
+    if (!RetKinds.empty() && MaxSpecificity > 0) {
+      std::string Decl;
+      llvm::raw_string_ostream OS(Decl);
+
+      if (IsPolymorphic) {
+        OS << "Matcher<T> " << I->first() << "(Matcher<T>";
+      } else {
+        OS << "Matcher<" << RetKinds << "> " << I->first() << "(";
+        for (std::vector<std::vector<internal::ArgKind> >::iterator
+                 KI = ArgsKinds.begin(),
+                 KE = ArgsKinds.end();
+             KI != KE; ++KI) {
+          if (KI != ArgsKinds.begin())
+            OS << ", ";
+          // This currently assumes that a matcher may not overload a
+          // non-matcher, and all non-matcher overloads have identical
+          // arguments.
+          if ((*KI)[0].getArgKind() == internal::ArgKind::AK_Matcher) {
+            std::set<ASTNodeKind> MatcherKinds;
+            std::transform(
+                KI->begin(), KI->end(),
+                std::inserter(MatcherKinds, MatcherKinds.end()),
+                std::mem_fun_ref(&internal::ArgKind::getMatcherKind));
+            OS << "Matcher<" << MatcherKinds << ">";
+          } else {
+            OS << (*KI)[0].asString();
+          }
+        }
+      }
+      if (I->second->isVariadic())
+        OS << "...";
+      OS << ")";
+
+      std::string TypedText = I->first();
+      TypedText += "(";
+      if (ArgsKinds.empty())
+        TypedText += ")";
+      else if (ArgsKinds[0][0].getArgKind() == internal::ArgKind::AK_String)
+        TypedText += "\"";
+
+      Completions[std::make_pair(MaxSpecificity, I->first())] =
+          MatcherCompletion(TypedText, OS.str());
+    }
+  }
+
+  std::vector<MatcherCompletion> RetVal;
+  for (CompletionsTy::iterator I = Completions.begin(), E = Completions.end();
+       I != E; ++I)
+    RetVal.push_back(I->second);
+  return RetVal;
+}
+
 // static
 VariantMatcher Registry::constructMatcher(MatcherCtor Ctor,
                                           const SourceRange &NameRange,
                                           ArrayRef<ParserValue> Args,
                                           Diagnostics *Error) {
   return Ctor->create(NameRange, Args, Error);
 }
 

unittests/ASTMatchers/Dynamic/RegistryTest.cpp

VariantMatcher constructMatcher(StringRef MatcherName,
     MatcherCtor Ctor = lookupMatcherCtor(MatcherName, Error);
     VariantMatcher Out;
     if (Ctor)
       Out = Registry::constructMatcher(Ctor, SourceRange(), Args(Arg1, Arg2),
                                        Error);
     EXPECT_EQ("", DummyError.toStringFull());
     return Out;
   }
+
+  typedef std::vector<MatcherCompletion> CompVector;
+
+  CompVector getCompletions() {
+    return Registry::getCompletions(
+        llvm::ArrayRef<std::pair<MatcherCtor, unsigned> >());
+  }
+
+  CompVector getCompletions(StringRef MatcherName1, unsigned ArgNo1) {
+    std::vector<std::pair<MatcherCtor, unsigned> > Context;
+    Context.push_back(std::make_pair(lookupMatcherCtor(MatcherName1), ArgNo1));
+    if (!Context.back().first)
+      return CompVector();
+    return Registry::getCompletions(Context);
+  }
+
+  CompVector getCompletions(StringRef MatcherName1, unsigned ArgNo1,
+                            StringRef MatcherName2, unsigned ArgNo2) {
+    std::vector<std::pair<MatcherCtor, unsigned> > Context;
+    Context.push_back(std::make_pair(lookupMatcherCtor(MatcherName1), ArgNo1));
+    if (!Context.back().first)
+      return CompVector();
+    Context.push_back(std::make_pair(lookupMatcherCtor(MatcherName2), ArgNo2));
+    if (!Context.back().first)
+      return CompVector();
+    return Registry::getCompletions(Context);
+  }
+
+  bool hasCompletion(const CompVector &Comps, StringRef TypedText,
+                     StringRef MatcherDecl = StringRef(), unsigned *Index = 0) {
+    for (CompVector::const_iterator I = Comps.begin(), E = Comps.end(); I != E;
+         ++I) {
+      if (I->TypedText == TypedText &&
+          (MatcherDecl.empty() || I->MatcherDecl == MatcherDecl)) {
+        if (Index)
+          *Index = I - Comps.begin();
+        return true;
+      }
+    }
+    return false;
+  }
 };
 
 TEST_F(RegistryTest, CanConstructNoArgs) {
   Matcher<Stmt> IsArrowValue = constructMatcher(
       "memberExpr", constructMatcher("isArrow")).getTypedMatcher<Stmt>();
   Matcher<Stmt> BoolValue =
       constructMatcher("boolLiteral").getTypedMatcher<Stmt>();
 
EXPECT_TRUE(constructMatcher(
                        constructMatcher("isArrow")),
       Error.get()).isNull());
   EXPECT_EQ("Incorrect type for arg 1. "
             "(Expected = Matcher<CXXRecordDecl>) != "
             "(Actual = Matcher<CXXRecordDecl>&Matcher<MemberExpr>)",
             Error->toString());
 }
 
+TEST_F(RegistryTest, Completion) {
+  CompVector Comps = getCompletions();
+  EXPECT_TRUE(hasCompletion(
+      Comps, "hasParent(", "Matcher<Decl|Stmt> hasParent(Matcher<Decl|Stmt>)"));
+  EXPECT_TRUE(hasCompletion(Comps, "whileStmt(",
+                            "Matcher<Stmt> whileStmt(Matcher<WhileStmt>...)"));
+
+  CompVector WhileComps = getCompletions("whileStmt", 0);
+
+  unsigned HasBodyIndex, HasParentIndex, AllOfIndex;
+  EXPECT_TRUE(hasCompletion(WhileComps, "hasBody(",
+                            "Matcher<WhileStmt> hasBody(Matcher<Stmt>)",
+                            &HasBodyIndex));
+  EXPECT_TRUE(hasCompletion(WhileComps, "hasParent(",
+                            "Matcher<Stmt> hasParent(Matcher<Decl|Stmt>)",
+                            &HasParentIndex));
+  EXPECT_TRUE(hasCompletion(WhileComps, "allOf(",
+                            "Matcher<T> allOf(Matcher<T>...)", &AllOfIndex));
+  EXPECT_GT(HasParentIndex, HasBodyIndex);
+  EXPECT_GT(AllOfIndex, HasParentIndex);
+
+  EXPECT_FALSE(hasCompletion(WhileComps, "whileStmt("));
+  EXPECT_FALSE(hasCompletion(WhileComps, "ifStmt("));
+
+  CompVector AllOfWhileComps =
+      getCompletions("allOf", 0, "whileStmt", 0);
+  ASSERT_EQ(AllOfWhileComps.size(), WhileComps.size());
+  EXPECT_TRUE(std::equal(WhileComps.begin(), WhileComps.end(),
+                         AllOfWhileComps.begin()));
+
+  CompVector DeclWhileComps =
+      getCompletions("decl", 0, "whileStmt", 0);
+  EXPECT_EQ(0u, DeclWhileComps.size());
+
+  CompVector NamedDeclComps = getCompletions("namedDecl", 0);
+  EXPECT_TRUE(
+      hasCompletion(NamedDeclComps, "isPublic()", "Matcher<Decl> isPublic()"));
+  EXPECT_TRUE(hasCompletion(NamedDeclComps, "hasName(\"",
+                            "Matcher<NamedDecl> hasName(string)"));
+}
+
 } // end anonymous namespace
 } // end namespace dynamic
 } // end namespace ast_matchers
 } // end namespace clang