ASTMatchers: Implement hasNextSibling()

[klimek]

Summary

In order to implement the static analyzer check in D5042 using ASTMatchers, I need the concept of a hasNextSibling() constraint.

The attached patch does not compile, but I'm wondering if I'm in the ballpark as far as implementation goes, or whether there is a better way to do this. (See the FIXME comments in the patch for what's not implemented.)

Also, it may make more sense to implement this as hasNextStatement() instead of a more generic "hasNextSibling()" because what I really want to match the next statement after the one I matched.

[klimek]

I don't think using the AST directly for control flow is something that will always work. The static analyzer builds a CFG for that reason.

include/clang/ASTMatchers/ASTMatchers.h

 const internal::ArgumentAdaptingMatcherFunc<internal::HasDescendantMatcher>
 LLVM_ATTRIBUTE_UNUSED hasDescendant = {};
 
+/// \brief Matches AST nodes that are next sibling AST nodes that match the
+/// provided matcher.
+///
+/// Example matches X
+///     (matcher = recordDecl(hasName("Z"),
+///                           hasNextSibling(recordDecl(hasName("X")))))
+/// \code
+///   class Z {}; class Y {}; class X {};
+/// \endcode
+///
+/// NextSiblingT must be an AST base type.
+///
+/// Usable as: Any Matcher
+const internal::ArgumentAdaptingMatcherFunc<internal::HasNextSiblingMatcher>
+LLVM_ATTRIBUTE_UNUSED hasNextSibling = {};
+
+/// \brief Matches AST nodes that are previous sibling AST nodes that match the
+/// provided matcher.
+///
+/// Example matches Z
+///     (matcher = recordDecl(hasName("X"),
+///                           hasPreviousSibling(recordDecl(hasName("Z")))))
+/// \code
+///   class Z {}; class Y {}; class X {};
+/// \endcode
+///
+/// NextSiblingT must be an AST base type.
+///
+/// Usable as: Any Matcher
+const internal::ArgumentAdaptingMatcherFunc<internal::HasPreviousSiblingMatcher>
+LLVM_ATTRIBUTE_UNUSED hasPreviousSibling = {};
+
 /// \brief Matches AST nodes that have child AST nodes that match the
 /// provided matcher.
 ///

include/clang/ASTMatchers/ASTMatchersInternal.h

                                Matcher, Builder, Bind);
   }
 
+  template <typename T>
+  bool matchesNextSiblingOf(const T &Node,
+                            const DynTypedMatcher &Matcher,
+                            BoundNodesTreeBuilder *Builder,
+                            BindKind Bind) {
+    static_assert(std::is_base_of<Decl, T>::value ||
+            std::is_base_of<Stmt, T>::value ||
+            std::is_base_of<NestedNameSpecifier, T>::value ||
+            std::is_base_of<NestedNameSpecifierLoc, T>::value ||
+            std::is_base_of<TypeLoc, T>::value ||
+            std::is_base_of<QualType, T>::value,
+        "unsupported type for next sibling matching");
+    return matchesNextSiblingOf(ast_type_traits::DynTypedNode::create(Node),
+        Matcher, Builder, Bind);
+  }
+
   // FIXME: Implement support for BindKind.
   template <typename T>
   bool matchesAncestorOf(const T &Node,

                                    BoundNodesTreeBuilder *Builder,
                                    BindKind Bind) = 0;
 
+  virtual bool matchesNextSiblingOf(const ast_type_traits::DynTypedNode &Node,
+                                    const DynTypedMatcher &Matcher,
+                                    BoundNodesTreeBuilder *Builder,
+                                    BindKind Bind) = 0;
+
   virtual bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
                                  const DynTypedMatcher &Matcher,
                                  BoundNodesTreeBuilder *Builder,

   const Matcher<DescendantT> DescendantMatcher;
 };
 
+/// \brief Matches nodes of type T that have at least one next sibling node of
+/// type NextSiblingT for which the given inner matcher matches.
+///
+/// NextSiblingT must be an AST base type.
+template <typename T, typename NextSiblingT>
+class HasNextSiblingMatcher : public MatcherInterface<T> {
+  static_assert(IsBaseType<NextSiblingT>::value,
+                "hasNextSibling only accepts base type matcher");
+
+public:
+  explicit HasNextSiblingMatcher(const Matcher<NextSiblingT> &NextSiblingMatcher)
+      : NextSiblingMatcher(NextSiblingMatcher) {}
+
+  bool matches(const T &Node, ASTMatchFinder *Finder,
+               BoundNodesTreeBuilder *Builder) const override {
+    return Finder->matchesNextSiblingOf(
+        Node, NextSiblingMatcher, Builder, ASTMatchFinder::BK_First);
+  }
+
+private:
+  const Matcher<NextSiblingT> NextSiblingMatcher;
+};
+
 /// \brief Matches nodes of type \c T that have a parent node of type \c ParentT
 /// for which the given inner matcher matches.
 ///

lib/ASTMatchers/ASTMatchFinder.cpp

     return Visitor.findMatch(Node);
   }
 
+  // Matches next siblings of 'Node' with 'BaseMatcher'.
+  bool memoizedMatchesNextSibling(const ast_type_traits::DynTypedNode &Node,
+                                  const DynTypedMatcher &Matcher,
+                                  BoundNodesTreeBuilder *Builder,
+                                  TraversalKind Traversal, BindKind Bind) {
+    // For AST-nodes that don't have an identity, we can't memoize.
+    if (!Node.getMemoizationData() || !Builder->isComparable())
+      return matchesNextSibling(Node, Matcher, Builder, Traversal, Bind);
+
+    MatchKey Key;
+    Key.MatcherID = Matcher.getID();
+    Key.Node = Node;
+    // Note that we key on the bindings *before* the match.
+    Key.BoundNodes = *Builder;
+
+    MemoizationMap::iterator I = ResultCache.find(Key);
+    if (I != ResultCache.end()) {
+      *Builder = I->second.Nodes;
+      return I->second.ResultOfMatch;
+    }
+
+    MemoizedMatchResult Result;
+    Result.Nodes = *Builder;
+    Result.ResultOfMatch = matchesNextSibling(Node, Matcher, &Result.Nodes,
+        Traversal, Bind);
+    ResultCache[Key] = Result;
+    *Builder = Result.Nodes;
+    return Result.ResultOfMatch;
+  }
+
+  // Matches next sibling of 'Node' with 'BaseMatcher'.
+  bool matchesNextSibling(const ast_type_traits::DynTypedNode &Node,
+                          const DynTypedMatcher &Matcher,
+                          BoundNodesTreeBuilder *Builder,
+                          TraversalKind Traversal, BindKind Bind) {
+    // FIXME: Implement for next sibling.
+    // FIXME: Get parent of Node, match all children (max depth 0 or 1), then
+    // iterate through children ourselves???
+    MatchChildASTVisitor Visitor(
+      &Matcher, this, Builder, 1, Traversal, BK_All);
+    return Visitor.findMatch(Node);
+  }
+
   bool classIsDerivedFrom(const CXXRecordDecl *Declaration,
                           const Matcher<NamedDecl> &Base,
                           BoundNodesTreeBuilder *Builder) override;

     return memoizedMatchesRecursively(Node, Matcher, Builder, INT_MAX,
                                       TK_AsIs, Bind);
   }
+  // Implements ASTMatchFinder::matchesNextSiblingOf.
+  bool matchesNextSiblingOf(const ast_type_traits::DynTypedNode &Node,
+                            const DynTypedMatcher &Matcher,
+                            BoundNodesTreeBuilder *Builder,
+                            BindKind Bind) override {
+    if (ResultCache.size() > MaxMemoizationEntries)
+      ResultCache.clear();
+    return memoizedMatchesNextSibling(Node, Matcher, Builder, TK_AsIs, Bind);
+  }
   // Implements ASTMatchFinder::matchesAncestorOf.
   bool matchesAncestorOf(const ast_type_traits::DynTypedNode &Node,
                          const DynTypedMatcher &Matcher,