Introduce Registry::getCompletions.

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.

Differential Revision: http://llvm-reviews.chandlerc.com/D2210

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@199950 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 661 insertions, 98 deletions

diff --git a/include/clang/AST/ASTTypeTraits.h b/include/clang/AST/ASTTypeTraits.h
index f826436c6d..d7bbdefb22 100644
--- a/include/clang/AST/ASTTypeTraits.h
+++ b/include/clang/AST/ASTTypeTraits.h
@@ -64,6 +64,11 @@ public:
   /// \brief String representation of the kind.
   StringRef asStringRef() const;
 
+  /// \brief Strict weak ordering for ASTNodeKind.
+  bool operator<(const ASTNodeKind &Other) const {
+    return KindId < Other.KindId;
+  }
+
 private:
   /// \brief Kind ids.
   ///
@@ -137,6 +142,11 @@ KIND_TO_KIND_ID(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
diff --git a/include/clang/ASTMatchers/Dynamic/Registry.h b/include/clang/ASTMatchers/Dynamic/Registry.h
index f56a2c892e..d7df698b65 100644
--- a/include/clang/ASTMatchers/Dynamic/Registry.h
+++ b/include/clang/ASTMatchers/Dynamic/Registry.h
@@ -34,6 +34,22 @@ class MatcherDescriptor;
 
 typedef const internal::MatcherDescriptor *MatcherCtor;
 
+struct MatcherCompletion {
+  MatcherCompletion() {}
+  MatcherCompletion(StringRef TypedText, StringRef 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,
@@ -45,6 +61,29 @@ public:
   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 Ctor The matcher constructor to instantiate.
diff --git a/lib/ASTMatchers/Dynamic/Marshallers.h b/lib/ASTMatchers/Dynamic/Marshallers.h
index b0df356404..0a03fad62f 100644
--- a/lib/ASTMatchers/Dynamic/Marshallers.h
+++ b/lib/ASTMatchers/Dynamic/Marshallers.h
@@ -34,6 +34,45 @@ 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.
@@ -42,11 +81,13 @@ 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 <>
@@ -54,39 +95,88 @@ 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 MatcherDescriptor {
 public:
   virtual ~MatcherDescriptor() {}
   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.
+  // FIXME: We should provide the ability to constrain the output of this
+  // function based on the types of other matcher arguments.
+  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; }
 };
 
+inline bool isRetKindConvertibleTo(
+    llvm::ArrayRef<ast_type_traits::ASTNodeKind> RetKinds,
+    ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+    ast_type_traits::ASTNodeKind *LeastDerivedKind) {
+  for (llvm::ArrayRef<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;
+}
+
 /// \brief Simple callback implementation. Marshaller and function are provided.
 ///
 /// This class wraps a function of arbitrary signature and a marshaller
@@ -104,46 +194,225 @@ public:
   /// \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.
-  FixedArgCountMatcherDescriptor(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.
+  FixedArgCountMatcherDescriptor(
+      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 {
+    return isRetKindConvertibleTo(RetKinds, Kind, Specificity,
+                                  LeastDerivedKind);
+  }
+
 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.
+///
+/// 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>
+inline 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 <>
+inline 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
+variadicMatcherDescriptor(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 free function with the right signature to export
+/// This class simply wraps a VariadicFunction with the right signature to export
 /// it as a MatcherDescriptor.
 /// 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 FreeFuncMatcherDescriptor : public MatcherDescriptor {
+class VariadicFuncMatcherDescriptor : public MatcherDescriptor {
 public:
   typedef VariantMatcher (*RunFunc)(StringRef MatcherName,
                                     const SourceRange &NameRange,
                                     ArrayRef<ParserValue> Args,
                                     Diagnostics *Error);
 
-  FreeFuncMatcherDescriptor(RunFunc Func, StringRef MatcherName)
-      : Func(Func), MatcherName(MatcherName.str()) {}
+  template <typename ResultT, typename ArgT,
+            ResultT (*F)(ArrayRef<const ArgT *>)>
+  VariadicFuncMatcherDescriptor(llvm::VariadicFunction<ResultT, ArgT, F> Func,
+                          StringRef MatcherName)
+      : Func(&variadicMatcherDescriptor<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 {
+    return isRetKindConvertibleTo(RetKinds, Kind, Specificity,
+                                  LeastDerivedKind);
+  }
+
 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 DynCastAllOfMatcherDescriptor : public VariadicFuncMatcherDescriptor {
+public:
+  template <typename BaseT, typename DerivedT>
+  DynCastAllOfMatcherDescriptor(
+      ast_matchers::internal::VariadicDynCastAllOfMatcher<BaseT, DerivedT> Func,
+      StringRef MatcherName)
+      : VariadicFuncMatcherDescriptor(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 (VariadicFuncMatcherDescriptor::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.
@@ -157,44 +426,11 @@ private:
 #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>
@@ -238,41 +474,6 @@ static VariantMatcher matcherMarshall2(void (*Func)(), StringRef MatcherName,
 #undef CHECK_ARG_COUNT
 #undef CHECK_ARG_TYPE
 
-/// \brief Variadic marshaller function.
-template <typename ResultT, typename ArgT,
-          ResultT (*Func)(ArrayRef<const ArgT *>)>
-VariantMatcher
-variadicMatcherDescriptor(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,
@@ -338,6 +539,51 @@ public:
     return Constructed[0];
   }
 
+  bool isVariadic() const {
+    bool Overload0Variadic = Overloads[0]->isVariadic();
+#ifndef NDEBUG
+    for (std::vector<MatcherDesc *>::const_iterator I = Overloads.begin(),
+                                                    E = Overloads.end();
+         I != E; ++I) {
+      assert(Overload0Variadic == (*I)->isVariadic());
+    }
+#endif
+    return Overload0Variadic;
+  }
+
+  unsigned getNumArgs() const {
+    unsigned Overload0NumArgs = Overloads[0]->getNumArgs();
+#ifndef NDEBUG
+    for (std::vector<MatcherDesc *>::const_iterator I = Overloads.begin(),
+                                                    E = Overloads.end();
+         I != E; ++I) {
+      assert(Overload0NumArgs == (*I)->getNumArgs());
+    }
+#endif
+    return Overload0NumArgs;
+  }
+
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const {
+    for (std::vector<MatcherDescriptor *>::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<MatcherDescriptor *>::const_iterator I = Overloads.begin(),
+                                                    E = Overloads.end();
+         I != E; ++I) {
+      if ((*I)->isConvertibleTo(Kind, Specificity, LeastDerivedKind))
+        return true;
+    }
+    return false;
+  }
+
 private:
   std::vector<MatcherDescriptor *> Overloads;
 };
@@ -376,6 +622,22 @@ public:
     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 unsigned MinCount;
   const unsigned MaxCount;
@@ -383,36 +645,43 @@ private:
   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>
 MatcherDescriptor *makeMatcherAutoMarshall(ReturnType (*Func)(),
-                                           StringRef MatcherName) {
-  return new FixedArgCountMatcherDescriptor(matcherMarshall0<ReturnType>,
-                                            reinterpret_cast<void (*)()>(Func),
-                                            MatcherName);
+                                     StringRef MatcherName) {
+  std::vector<ast_type_traits::ASTNodeKind> RetTypes;
+  BuildReturnTypeVector<ReturnType>::build(RetTypes);
+  return new FixedArgCountMatcherDescriptor(
+      matcherMarshall0<ReturnType>, reinterpret_cast<void (*)()>(Func),
+      MatcherName, RetTypes, llvm::ArrayRef<ArgKind>());
 }
 
 /// \brief 1-arg overload
 template <typename ReturnType, typename ArgType1>
 MatcherDescriptor *makeMatcherAutoMarshall(ReturnType (*Func)(ArgType1),
-                                           StringRef MatcherName) {
+                                     StringRef MatcherName) {
+  std::vector<ast_type_traits::ASTNodeKind> RetTypes;
+  BuildReturnTypeVector<ReturnType>::build(RetTypes);
+  ArgKind AK = ArgTypeTraits<ArgType1>::getKind();
   return new FixedArgCountMatcherDescriptor(
       matcherMarshall1<ReturnType, ArgType1>,
-      reinterpret_cast<void (*)()>(Func), MatcherName);
+      reinterpret_cast<void (*)()>(Func), MatcherName, RetTypes, AK);
 }
 
 /// \brief 2-arg overload
 template <typename ReturnType, typename ArgType1, typename ArgType2>
-MatcherDescriptor *makeMatcherAutoMarshall(ReturnType (*Func)(ArgType1,
-                                                              ArgType2),
-                                           StringRef MatcherName) {
+MatcherDescriptor *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 FixedArgCountMatcherDescriptor(
       matcherMarshall2<ReturnType, ArgType1, ArgType2>,
-      reinterpret_cast<void (*)()>(Func), MatcherName);
+      reinterpret_cast<void (*)()>(Func), MatcherName, RetTypes, AKs);
 }
 
 /// \brief Variadic overload.
@@ -421,8 +690,19 @@ template <typename ResultT, typename ArgT,
 MatcherDescriptor *
 makeMatcherAutoMarshall(llvm::VariadicFunction<ResultT, ArgT, Func> VarFunc,
                         StringRef MatcherName) {
-  return new FreeFuncMatcherDescriptor(
-      &variadicMatcherDescriptor<ResultT, ArgT, Func>, MatcherName);
+  return new VariadicFuncMatcherDescriptor(VarFunc, MatcherName);
+}
+
+/// \brief Overload for VariadicDynCastAllOfMatchers.
+///
+/// Not strictly necessary, but DynCastAllOfMatcherDescriptor gives us better
+/// completion results for that type of matcher.
+template <typename BaseT, typename DerivedT>
+MatcherDescriptor *
+makeMatcherAutoMarshall(ast_matchers::internal::VariadicDynCastAllOfMatcher<
+                            BaseT, DerivedT> VarFunc,
+                        StringRef MatcherName) {
+  return new DynCastAllOfMatcherDescriptor(VarFunc, MatcherName);
 }
 
 /// \brief Argument adaptative overload.
diff --git a/lib/ASTMatchers/Dynamic/Registry.cpp b/lib/ASTMatchers/Dynamic/Registry.cpp
index 9d0ecebe72..1c7215e327 100644
--- a/lib/ASTMatchers/Dynamic/Registry.cpp
+++ b/lib/ASTMatchers/Dynamic/Registry.cpp
@@ -18,8 +18,11 @@
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ManagedStatic.h"
+#include <set>
 #include <utility>
 
+using namespace clang::ast_type_traits;
+
 namespace clang {
 namespace ast_matchers {
 namespace dynamic {
@@ -332,6 +335,152 @@ Registry::lookupMatcherCtor(StringRef MatcherName, const SourceRange &NameRange,
   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,
diff --git a/unittests/ASTMatchers/Dynamic/RegistryTest.cpp b/unittests/ASTMatchers/Dynamic/RegistryTest.cpp
index c260b467ad..8426649d3e 100644
--- a/unittests/ASTMatchers/Dynamic/RegistryTest.cpp
+++ b/unittests/ASTMatchers/Dynamic/RegistryTest.cpp
@@ -84,6 +84,50 @@ public:
     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;
+    llvm::Optional<MatcherCtor> Ctor = lookupMatcherCtor(MatcherName1);
+    if (!Ctor)
+      return CompVector();
+    Context.push_back(std::make_pair(*Ctor, ArgNo1));
+    return Registry::getCompletions(Context);
+  }
+
+  CompVector getCompletions(StringRef MatcherName1, unsigned ArgNo1,
+                            StringRef MatcherName2, unsigned ArgNo2) {
+    std::vector<std::pair<MatcherCtor, unsigned> > Context;
+    llvm::Optional<MatcherCtor> Ctor = lookupMatcherCtor(MatcherName1);
+    if (!Ctor)
+      return CompVector();
+    Context.push_back(std::make_pair(*Ctor, ArgNo1));
+    Ctor = lookupMatcherCtor(MatcherName2);
+    if (!Ctor)
+      return CompVector();
+    Context.push_back(std::make_pair(*Ctor, ArgNo2));
+    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) {
@@ -378,6 +422,47 @@ TEST_F(RegistryTest, Errors) {
             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