WIP: Make it possible to use the traverse() matcher in clang-query

[steveire]

This is not ready for review, but is it a direction we want to go, given that we can already use

set traversal <foo>

in clang-query?

[ymandel]

Thanks, this looks quite useful. I should be able to look it over in full tomorrow.

clang/include/clang/ASTMatchers/ASTMatchersInternal.h

383

I need this for my fix to Transformer. In fact, this is the only thing I need, rather than an overload of traverse for DynTypedMatcher. Do you want me to split this into its own patch and send to you? Or, vice versa?

Also, whay const DynTypedMatcher &InnerMatcher? Given that it is immediately copied, why not just DynTypedMatcher InnerMatcher, which at least allows the caller to move-construct the argument and avoid the copy?

[steveire]

clang/include/clang/ASTMatchers/ASTMatchersInternal.h

383

Yes, if you could split what ever you need out and incorporate it into your work I think that would be useful.

I can rebase the rest of this once your fix is in.

clang/include/clang/ASTMatchers/ASTMatchersInternal.h

public:
   static DynTypedMatcher
   constructVariadic(VariadicOperator Op, ASTNodeKind SupportedKind,
                     std::vector<DynTypedMatcher> InnerMatchers);
 
   static DynTypedMatcher
   constructRestrictedWrapper(const DynTypedMatcher &InnerMatcher,
                              ASTNodeKind RestrictKind);
 
+  static DynTypedMatcher
+  constructTraversalWrapper(const DynTypedMatcher &InnerMatcher,
+                            ast_type_traits::TraversalKind TK);
+
   /// Get a "true" matcher for \p NodeKind.
   ///
   /// It only checks that the node is of the right kind.
   static DynTypedMatcher trueMatcher(ASTNodeKind NodeKind);
 
   void setAllowBind(bool AB) { AllowBind = AB; }
 
   /// Check whether this matcher could ever match a node of kind \p Kind.

clang/include/clang/ASTMatchers/Dynamic/VariantValue.h

 
 public:
   /// A null matcher.
   VariantMatcher();
 
   /// Clones the provided matcher.
   static VariantMatcher SingleMatcher(const DynTypedMatcher &Matcher);
 
+  static VariantMatcher TraversalMatcher(ast_type_traits::TraversalKind TK,
+                                         const DynTypedMatcher &Matcher);
+
   /// Clones the provided matchers.
   ///
   /// They should be the result of a polymorphic matcher.
   static VariantMatcher
   PolymorphicMatcher(std::vector<DynTypedMatcher> Matchers);
 
   /// Creates a 'variadic' operator matcher.
   ///

 
 private:
   explicit VariantMatcher(std::shared_ptr<Payload> Value)
       : Value(std::move(Value)) {}
 
   template <typename T> struct TypedMatcherOps;
 
   class SinglePayload;
+  class TraversalPayload;
   class PolymorphicPayload;
   class VariadicOpPayload;
 
   std::shared_ptr<const Payload> Value;
 };
 
 template <typename T>
 struct VariantMatcher::TypedMatcherOps final : VariantMatcher::MatcherOps {

clang/lib/ASTMatchers/ASTMatchersInternal.cpp

 DynTypedMatcher
 DynTypedMatcher::constructRestrictedWrapper(const DynTypedMatcher &InnerMatcher,
                                             ASTNodeKind RestrictKind) {
   DynTypedMatcher Copy = InnerMatcher;
   Copy.RestrictKind = RestrictKind;
   return Copy;
 }
 
+class DynTraversalMatcher : public DynMatcherInterface {
+public:
+  explicit DynTraversalMatcher(
+      clang::TraversalKind TK,
+      IntrusiveRefCntPtr<DynMatcherInterface> ChildMatcher)
+      : Traversal(TK), InnerMatcher(ChildMatcher) {}
+
+  bool dynMatches(const DynTypedNode &DynNode, ASTMatchFinder *Finder,
+                  BoundNodesTreeBuilder *Builder) const override {
+    return this->InnerMatcher->dynMatches(DynNode, Finder, Builder);
+  }
+
+  llvm::Optional<clang::TraversalKind> TraversalKind() const override {
+    return Traversal;
+  }
+
+private:
+  clang::TraversalKind Traversal;
+  IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
+};
+
+DynTypedMatcher
+DynTypedMatcher::constructTraversalWrapper(const DynTypedMatcher &InnerMatcher,
+                                           TraversalKind TK) {
+  DynTypedMatcher Copy = InnerMatcher;
+  Copy.Implementation =
+      new DynTraversalMatcher(TK, std::move(Copy.Implementation));
+  return Copy;
+}
+
 DynTypedMatcher DynTypedMatcher::trueMatcher(ASTNodeKind NodeKind) {
   return DynTypedMatcher(NodeKind, NodeKind, &*TrueMatcherInstance);
 }
 
 bool DynTypedMatcher::canMatchNodesOfKind(ASTNodeKind Kind) const {
   return RestrictKind.isBaseOf(Kind);
 }
 

clang/lib/ASTMatchers/Dynamic/Marshallers.h

static UnaryExprOrTypeTrait get(const VariantValue &Value) {
     return *getUnaryOrTypeTraitKind(Value.getString());
   }
 
   static ArgKind getKind() { return ArgKind(ArgKind::AK_String); }
 
   static llvm::Optional<std::string> getBestGuess(const VariantValue &Value);
 };
 
+template <> struct ArgTypeTraits<ast_type_traits::TraversalKind> {
+private:
+  static Optional<ast_type_traits::TraversalKind>
+  getTraversalKind(llvm::StringRef TK) {
+    return llvm::StringSwitch<Optional<ast_type_traits::TraversalKind>>(TK)
+        .Case("TK::AsIs", ast_type_traits::TK_AsIs)
+        .Case("TK::IgnoreUnlessSpelledInSource",
+              ast_type_traits::TK_IgnoreUnlessSpelledInSource)
+        .Case("TK::IgnoreImplicitCastsAndParentheses",
+              ast_type_traits::TK_IgnoreImplicitCastsAndParentheses)
+        .Default(llvm::None);
+  }
+
+public:
+  static bool is(const VariantValue &Value) {
+    return Value.isString() && getTraversalKind(Value.getString());
+  }
+
+  static ast_type_traits::TraversalKind get(const VariantValue &Value) {
+    return *getTraversalKind(Value.getString());
+  }
+
+  static ArgKind getKind() { return ArgKind(ArgKind::AK_String); }
+};
+
 /// Matcher descriptor interface.
 ///
 /// Provides a \c create() method that constructs the matcher from the provided
 /// arguments, and various other methods for type introspection.
 class MatcherDescriptor {
 public:
   virtual ~MatcherDescriptor() = default;
 
if (ArgKind(NodeKind).isConvertibleTo(Kind, Specificity)) {
       if (LeastDerivedKind)
         *LeastDerivedKind = NodeKind;
       return true;
     }
   }
   return false;
 }
 
+class TraverseMatcherDescriptor : public MatcherDescriptor {
+public:
+  TraverseMatcherDescriptor() {}
+
+  VariantMatcher create(SourceRange NameRange, ArrayRef<ParserValue> Args,
+                        Diagnostics *Error) const override {
+    if (Args.size() != 2)
+      return {};
+    auto TraversalArg = Args[0].Value;
+    if (!TraversalArg.isString())
+      return {};
+    auto TraversalCode =
+        llvm::StringSwitch<unsigned>(TraversalArg.getString())
+            .Case("AsIs", ast_type_traits::TK_AsIs)
+            .Case("IgnoreImplicitCastsAndParentheses",
+                  ast_type_traits::TK_IgnoreImplicitCastsAndParentheses)
+            .Case("IgnoreUnlessSpelledInSource",
+                  ast_type_traits::TK_IgnoreUnlessSpelledInSource)
+            .Default(~0u);
+    if (TraversalCode == ~0u) {
+      return {};
+    }
+    auto MatcherArg = Args[1].Value;
+    if (!MatcherArg.isMatcher())
+      return {};
+    auto M = MatcherArg.getMatcher();
+    if (M.isNull())
+      return {};
+    auto SM = M.getSingleMatcher();
+    if (!SM)
+      return {};
+    return VariantMatcher::TraversalMatcher(
+        static_cast<ast_type_traits::TraversalKind>(TraversalCode), *SM);
+  }
+
+  bool isVariadic() const override { return false; }
+  unsigned getNumArgs() const override { return 2; }
+
+  void getArgKinds(ast_type_traits::ASTNodeKind ThisKind, unsigned ArgNo,
+                   std::vector<ArgKind> &Kinds) const override {
+    if (ArgNo == 0) {
+      Kinds.push_back(ArgKind::AK_String);
+      return;
+    }
+    Kinds.push_back(ThisKind);
+  }
+
+  bool isConvertibleTo(
+      ast_type_traits::ASTNodeKind Kind, unsigned *Specificity,
+      ast_type_traits::ASTNodeKind *LeastDerivedKind) const override {
+    return true;
+    // return isRetKindConvertibleTo(RetKinds, Kind, Specificity,
+    //                               LeastDerivedKind);
+  }
+
+private:
+};
+
 /// Simple callback implementation. Marshaller and function are provided.
 ///
 /// This class wraps a function of arbitrary signature and a marshaller
 /// function into a MatcherDescriptor.
 /// The marshaller is in charge of taking the VariantValue arguments, checking
 /// their types, unpacking them and calling the underlying function.
 class FixedArgCountMatcherDescriptor : public MatcherDescriptor {
 public:

clang/lib/ASTMatchers/Dynamic/Registry.cpp

RegistryMaps::RegistryMaps() {
   // TODO: Here is the list of the missing matchers, grouped by reason.
   //
   // Polymorphic + argument overload:
   // findAll
   //
   // Other:
   // equalsNode
 
+  registerMatcher("traverse",
+                  std::make_unique<internal::TraverseMatcherDescriptor>());
+
   REGISTER_OVERLOADED_2(callee);
   REGISTER_OVERLOADED_2(hasAnyCapture);
   REGISTER_OVERLOADED_2(hasPrefix);
   REGISTER_OVERLOADED_2(hasType);
   REGISTER_OVERLOADED_2(ignoringParens);
   REGISTER_OVERLOADED_2(isDerivedFrom);
   REGISTER_OVERLOADED_2(isDirectlyDerivedFrom);
   REGISTER_OVERLOADED_2(isSameOrDerivedFrom);

clang/lib/ASTMatchers/Dynamic/VariantValue.cpp

if (!Inner)
       return llvm::None;
     DynMatchers.push_back(*Inner);
   }
   return DynTypedMatcher::constructVariadic(Op, NodeKind, DynMatchers);
 }
 
 VariantMatcher::Payload::~Payload() {}
 
+class VariantMatcher::TraversalPayload : public VariantMatcher::Payload {
+public:
+  TraversalPayload(ast_type_traits::TraversalKind TK,
+                   const DynTypedMatcher &Matcher)
+      : TK(TK), Matcher(Matcher) {}
+
+  llvm::Optional<DynTypedMatcher> getSingleMatcher() const override {
+    return Matcher;
+  }
+
+  std::string getTypeAsString() const override {
+    return (Twine("Matcher<") + Matcher.getSupportedKind().asStringRef() + ">")
+        .str();
+  }
+
+  llvm::Optional<DynTypedMatcher>
+  getTypedMatcher(const MatcherOps &Ops) const override {
+    // llvm::errs() << "TraversalCode" << "\n";
+    // std::terminate();
+
+    bool Ignore;
+    if (Ops.canConstructFrom(Matcher, Ignore)) {
+      return DynTypedMatcher::constructTraversalWrapper(Matcher, TK);
+    }
+    return llvm::None;
+  }
+
+  bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind,
+                       unsigned *Specificity) const override {
+    return ArgKind(Matcher.getSupportedKind())
+        .isConvertibleTo(Kind, Specificity);
+  }
+
+private:
+  ast_type_traits::TraversalKind TK;
+  const DynTypedMatcher Matcher;
+};
+
 class VariantMatcher::SinglePayload : public VariantMatcher::Payload {
 public:
   SinglePayload(const DynTypedMatcher &Matcher) : Matcher(Matcher) {}
 
   llvm::Optional<DynTypedMatcher> getSingleMatcher() const override {
     return Matcher;
   }
 

 
 VariantMatcher::VariantMatcher() {}
 
 VariantMatcher VariantMatcher::SingleMatcher(const DynTypedMatcher &Matcher) {
   return VariantMatcher(std::make_shared<SinglePayload>(Matcher));
 }
 
 VariantMatcher
+VariantMatcher::TraversalMatcher(ast_type_traits::TraversalKind TK,
+                                 const DynTypedMatcher &Matcher) {
+  return VariantMatcher(std::make_shared<TraversalPayload>(TK, Matcher));
+}
+
+VariantMatcher
 VariantMatcher::PolymorphicMatcher(std::vector<DynTypedMatcher> Matchers) {
   return VariantMatcher(
       std::make_shared<PolymorphicPayload>(std::move(Matchers)));
 }
 
 VariantMatcher VariantMatcher::VariadicOperatorMatcher(
     DynTypedMatcher::VariadicOperator Op,
     std::vector<VariantMatcher> Args) {

clang/unittests/ASTMatchers/Dynamic/RegistryTest.cpp

 TEST_F(RegistryTest, HasArgs) {
   Matcher<Decl> Value = constructMatcher(
       "decl", constructMatcher("hasAttr", StringRef("attr::WarnUnused")))
       .getTypedMatcher<Decl>();
   EXPECT_TRUE(matches("struct __attribute__((warn_unused)) X {};", Value));
   EXPECT_FALSE(matches("struct X {};", Value));
 }
 
+TEST_F(RegistryTest, Traverse) {
+  EXPECT_TRUE(
+      matches(R"cpp(
+int foo()
+{
+    double d = 0;
+    return d;
+}
+)cpp",
+              constructMatcher(
+                  "returnStmt",
+                  constructMatcher(
+                      "hasReturnValue",
+                      constructMatcher("traverse",
+                                       StringRef("IgnoreUnlessSpelledInSource"),
+                                       constructMatcher("declRefExpr"))))
+                  .getTypedMatcher<Stmt>()));
+}
+
 TEST_F(RegistryTest, ParenExpr) {
   Matcher<Stmt> Value = constructMatcher("parenExpr").getTypedMatcher<Stmt>();
   EXPECT_TRUE(
       matches("int i = (1);", traverse(ast_type_traits::TK_AsIs, Value)));
   EXPECT_FALSE(
       matches("int i = 1;", traverse(ast_type_traits::TK_AsIs, Value)));
 }