Fix bug in DynTypedMatcher::constructVariadic() that would cause false negatives.

[sbenza]

Summary

DynTypedMatcher::constructVariadic() where the restrict kind of the
different matchers are not related causes the matcher to have a "None"
restrict kind. This causes false negatives for anyOf and eachOf.
Change the logic to get a common ancestor if there is one.
Also added regression tests that fail without the fix.

[klimek]

Overall, I think Anything and Nothing are not intuitive names for me here... Perhaps more docs will make it clear what they should be called.

include/clang/AST/ASTTypeTraits.h

87–91

a) why return anything()? (document the decisions, seems kinda arbitrary)
b) typo: Ancestor

98–99

Can you document what Nothing and Anything is in NodeKind land, and document that?

lib/AST/ASTTypeTraits.cpp

23–32

I just realize this all might need some documentation.

unittests/ASTMatchers/Dynamic/RegistryTest.cpp

350

Is this test change related?

[sbenza]

Remove anything(). It is not needed for this fix.

[sbenza]

Reverted a lot of the change.
Please review against the base.

include/clang/AST/ASTTypeTraits.h

87–91

Removed the concept of 'anything'. was not necessary and the name was not correct.
Fixed the typo everywhere (I think).

98–99

Reverted this.

lib/AST/ASTTypeTraits.cpp

23–32

Reverted this.

unittests/ASTMatchers/Dynamic/RegistryTest.cpp

350

Yes. The change triggered the bug.
recordDecl is a namedDecl, so it wasn't hitting the bug. I made it more specific with functionDecl and it started failing. The fix made it pass again.

[klimek]

lg

[sbenza]

Closed by commit rL219118 (authored by @sbenza).

include/clang/AST/ASTTypeTraits.h

public:
   static ASTNodeKind getFromNode(const Decl &D);
   static ASTNodeKind getFromNode(const Stmt &S);
   static ASTNodeKind getFromNode(const Type &T);
   /// \}
 
   /// \brief Returns \c true if \c this and \c Other represent the same kind.
   bool isSame(ASTNodeKind Other) const;
 
+  /// \brief Returns \c true only for the default \c ASTNodeKind()
+  bool isNone() const { return KindId == NKI_None; }
+
   /// \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 = nullptr) const;
 
   /// \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;
   }
 
+  /// \brief Return the most derived type between \p Kind1 and \p Kind2.
+  ///
+  /// Return ASTNodeKind() if they are not related.
+  static ASTNodeKind getMostDerivedType(ASTNodeKind Kind1, ASTNodeKind Kind2);
+
+  /// \brief Return the most derived common ancestor between Kind1 and Kind2.
+  ///
+  /// Return ASTNodeKind() if they are not related.
+  static ASTNodeKind getMostDerivedCommonAncestor(ASTNodeKind Kind1,
+                                                  ASTNodeKind Kind2);
+
 private:
   /// \brief Kind ids.
   ///
   /// Includes all possible base and derived kinds.
   enum NodeKindId {
     NKI_None,
     NKI_CXXCtorInitializer,
     NKI_TemplateArgument,
     NKI_NestedNameSpecifier,
     NKI_NestedNameSpecifierLoc,
     NKI_QualType,
     NKI_TypeLoc,
     NKI_Decl,
 #define DECL(DERIVED, BASE) NKI_##DERIVED##Decl,
 #include "clang/AST/DeclNodes.inc"

lib/AST/ASTTypeTraits.cpp

 
 #include "clang/AST/ASTTypeTraits.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclCXX.h"
 
 namespace clang {
 namespace ast_type_traits {
 
 const ASTNodeKind::KindInfo ASTNodeKind::AllKindInfo[] = {
   { NKI_None, "<None>" },
   { NKI_None, "CXXCtorInitializer" },
   { NKI_None, "TemplateArgument" },
   { NKI_None, "NestedNameSpecifier" },
   { NKI_None, "NestedNameSpecifierLoc" },
   { NKI_None, "QualType" },
   { NKI_None, "TypeLoc" },
   { NKI_None, "Decl" },
 #define DECL(DERIVED, BASE) { NKI_##BASE, #DERIVED "Decl" },
 #include "clang/AST/DeclNodes.inc"
   { NKI_None, "Stmt" },
 #define STMT(DERIVED, BASE) { NKI_##BASE, #DERIVED },
 #include "clang/AST/StmtNodes.inc"
   { NKI_None, "Type" },
 #define TYPE(DERIVED, BASE) { NKI_##BASE, #DERIVED "Type" },
 #include "clang/AST/TypeNodes.def"
 };
bool ASTNodeKind::isBaseOf(NodeKindId Base, NodeKindId Derived,
   }
   if (Distance)
     *Distance = Dist;
   return Derived == Base;
 }
 
 StringRef ASTNodeKind::asStringRef() const { return AllKindInfo[KindId].Name; }
 
+ASTNodeKind ASTNodeKind::getMostDerivedType(ASTNodeKind Kind1,
+                                            ASTNodeKind Kind2) {
+  if (Kind1.isBaseOf(Kind2)) return Kind2;
+  if (Kind2.isBaseOf(Kind1)) return Kind1;
+  return ASTNodeKind();
+}
+
+ASTNodeKind ASTNodeKind::getMostDerivedCommonAncestor(ASTNodeKind Kind1,
+                                                      ASTNodeKind Kind2) {
+  NodeKindId Parent = Kind1.KindId;
+  while (!isBaseOf(Parent, Kind2.KindId, nullptr) && Parent != NKI_None) {
+    Parent = AllKindInfo[Parent].ParentId;
+  }
+  return ASTNodeKind(Parent);
+}
+
 ASTNodeKind ASTNodeKind::getFromNode(const Decl &D) {
   switch (D.getKind()) {
 #define DECL(DERIVED, BASE)                                                    \
     case Decl::DERIVED: return ASTNodeKind(NKI_##DERIVED##Decl);
 #define ABSTRACT_DECL(D)
 #include "clang/AST/DeclNodes.inc"
   };
   llvm_unreachable("invalid decl kind");

lib/ASTMatchers/ASTMatchersInternal.cpp

bool dynMatches(const ast_type_traits::DynTypedNode &DynNode,
     return Result;
   }
 
  private:
   const std::string ID;
   const IntrusiveRefCntPtr<DynMatcherInterface> InnerMatcher;
 };
 
-/// \brief Return the most derived type between \p Kind1 and \p Kind2.
-///
-/// Return the null type if they are not related.
-ast_type_traits::ASTNodeKind getMostDerivedType(
-    const ast_type_traits::ASTNodeKind Kind1,
-    const ast_type_traits::ASTNodeKind Kind2) {
-  if (Kind1.isBaseOf(Kind2)) return Kind2;
-  if (Kind2.isBaseOf(Kind1)) return Kind1;
-  return ast_type_traits::ASTNodeKind();
-}
-
-/// \brief Return the least derived type between \p Kind1 and \p Kind2.
-///
-/// Return the null type if they are not related.
-static ast_type_traits::ASTNodeKind getLeastDerivedType(
-    const ast_type_traits::ASTNodeKind Kind1,
-    const ast_type_traits::ASTNodeKind Kind2) {
-  if (Kind1.isBaseOf(Kind2)) return Kind1;
-  if (Kind2.isBaseOf(Kind1)) return Kind2;
-  return ast_type_traits::ASTNodeKind();
-}
-
 }  // namespace
 
 DynTypedMatcher DynTypedMatcher::constructVariadic(
     VariadicOperatorFunction Func, std::vector<DynTypedMatcher> InnerMatchers) {
   assert(InnerMatchers.size() > 0 && "Array must not be empty.");
   DynTypedMatcher Result = InnerMatchers[0];
   // Use the least derived type as the restriction for the wrapper.
   // This allows mismatches to be resolved on the inner matchers.
   for (const DynTypedMatcher &M : InnerMatchers) {
     assert(Result.SupportedKind.isSame(M.SupportedKind) &&
            "SupportedKind must match!");
     Result.RestrictKind =
-        getLeastDerivedType(Result.RestrictKind, M.RestrictKind);
+        ast_type_traits::ASTNodeKind::getMostDerivedCommonAncestor(
+            Result.RestrictKind, M.RestrictKind);
   }
   Result.Implementation = new VariadicMatcher(Func, std::move(InnerMatchers));
   return Result;
 }
 
 DynTypedMatcher DynTypedMatcher::dynCastTo(
     const ast_type_traits::ASTNodeKind Kind) const {
   auto Copy = *this;
   Copy.SupportedKind = Kind;
-  Copy.RestrictKind = getMostDerivedType(Kind, RestrictKind);
+  Copy.RestrictKind =
+      ast_type_traits::ASTNodeKind::getMostDerivedType(Kind, RestrictKind);
   return Copy;
 }
 
 bool DynTypedMatcher::matches(const ast_type_traits::DynTypedNode &DynNode,
                               ASTMatchFinder *Finder,
                               BoundNodesTreeBuilder *Builder) const {
   if (RestrictKind.isBaseOf(DynNode.getNodeKind()) &&
       Implementation->dynMatches(DynNode, Finder, Builder)) {

unittests/AST/ASTTypeTraitsTest.cpp

TEST(ASTNodeKind, NoKind) {
   EXPECT_FALSE(ASTNodeKind().isBaseOf(ASTNodeKind()));
   EXPECT_FALSE(ASTNodeKind().isSame(ASTNodeKind()));
 }
 
 template <typename T> static ASTNodeKind DNT() {
   return ASTNodeKind::getFromNodeKind<T>();
 }
 
+TEST(ASTNodeKind, IsNone) {
+  EXPECT_TRUE(ASTNodeKind().isNone());
+  EXPECT_FALSE(DNT<Decl>().isNone());
+  EXPECT_FALSE(DNT<VarDecl>().isNone());
+}
+
 TEST(ASTNodeKind, Bases) {
   EXPECT_TRUE(DNT<Decl>().isBaseOf(DNT<VarDecl>()));
   EXPECT_FALSE(DNT<Decl>().isSame(DNT<VarDecl>()));
   EXPECT_FALSE(DNT<VarDecl>().isBaseOf(DNT<Decl>()));
 
   EXPECT_TRUE(DNT<Decl>().isSame(DNT<Decl>()));
 }
 

 }
 
 TEST(ASTNodeKind, DiffBase) {
   EXPECT_FALSE(DNT<Expr>().isBaseOf(DNT<ArrayType>()));
   EXPECT_FALSE(DNT<QualType>().isBaseOf(DNT<FunctionDecl>()));
   EXPECT_FALSE(DNT<Type>().isSame(DNT<QualType>()));
 }
 
+TEST(ASTNodeKind, MostDerivedType) {
+  EXPECT_TRUE(DNT<BinaryOperator>().isSame(
+      ASTNodeKind::getMostDerivedType(DNT<Expr>(), DNT<BinaryOperator>())));
+  EXPECT_TRUE(DNT<BinaryOperator>().isSame(
+      ASTNodeKind::getMostDerivedType(DNT<BinaryOperator>(), DNT<Expr>())));
+  EXPECT_TRUE(DNT<VarDecl>().isSame(
+      ASTNodeKind::getMostDerivedType(DNT<VarDecl>(), DNT<VarDecl>())));
+
+  // Not related. Returns nothing.
+  EXPECT_TRUE(
+      ASTNodeKind::getMostDerivedType(DNT<IfStmt>(), DNT<VarDecl>()).isNone());
+  EXPECT_TRUE(ASTNodeKind::getMostDerivedType(DNT<IfStmt>(),
+                                              DNT<BinaryOperator>()).isNone());
+}
+
+TEST(ASTNodeKind, MostDerivedCommonAncestor) {
+  EXPECT_TRUE(DNT<Expr>().isSame(ASTNodeKind::getMostDerivedCommonAncestor(
+      DNT<Expr>(), DNT<BinaryOperator>())));
+  EXPECT_TRUE(DNT<Expr>().isSame(ASTNodeKind::getMostDerivedCommonAncestor(
+      DNT<BinaryOperator>(), DNT<Expr>())));
+  EXPECT_TRUE(DNT<VarDecl>().isSame(ASTNodeKind::getMostDerivedCommonAncestor(
+      DNT<VarDecl>(), DNT<VarDecl>())));
+
+  // A little related. Returns the ancestor.
+  EXPECT_TRUE(
+      DNT<NamedDecl>().isSame(ASTNodeKind::getMostDerivedCommonAncestor(
+          DNT<CXXMethodDecl>(), DNT<RecordDecl>())));
+
+  // Not related. Returns nothing.
+  EXPECT_TRUE(ASTNodeKind::getMostDerivedCommonAncestor(
+                  DNT<IfStmt>(), DNT<VarDecl>()).isNone());
+}
+
 struct Foo {};
 
 TEST(ASTNodeKind, UnknownKind) {
   // We can construct one, but it is nowhere in the hierarchy.
   EXPECT_FALSE(DNT<Foo>().isSame(DNT<Foo>()));
 }
 
 TEST(ASTNodeKind, Name) {

unittests/ASTMatchers/ASTMatchersTest.cpp

DeclarationMatcher XOrYOrZOrUOrV =
       recordDecl(anyOf(hasName("X"), hasName("Y"), hasName("Z"), hasName("U"),
                        hasName("V")));
   EXPECT_TRUE(matches("class X {};", XOrYOrZOrUOrV));
   EXPECT_TRUE(matches("class Y {};", XOrYOrZOrUOrV));
   EXPECT_TRUE(matches("class Z {};", XOrYOrZOrUOrV));
   EXPECT_TRUE(matches("class U {};", XOrYOrZOrUOrV));
   EXPECT_TRUE(matches("class V {};", XOrYOrZOrUOrV));
   EXPECT_TRUE(notMatches("class A {};", XOrYOrZOrUOrV));
+
+  StatementMatcher MixedTypes = stmt(anyOf(ifStmt(), binaryOperator()));
+  EXPECT_TRUE(matches("int F() { return 1 + 2; }", MixedTypes));
+  EXPECT_TRUE(matches("int F() { if (true) return 1; }", MixedTypes));
+  EXPECT_TRUE(notMatches("int F() { return 1; }", MixedTypes));
 }
 
 TEST(DeclarationMatcher, MatchHas) {
   DeclarationMatcher HasClassX = recordDecl(has(recordDecl(hasName("X"))));
   EXPECT_TRUE(matches("class Y { class X {}; };", HasClassX));
   EXPECT_TRUE(matches("class X {};", HasClassX));
 
   DeclarationMatcher YHasClassX =

unittests/ASTMatchers/Dynamic/RegistryTest.cpp

TEST_F(RegistryTest, Adaptative) {
   EXPECT_FALSE(matches("void foo() { if (true) return; }", S));
 }
 
 TEST_F(RegistryTest, VariadicOp) {
   Matcher<Decl> D = constructMatcher(
       "anyOf",
       constructMatcher("recordDecl",
                        constructMatcher("hasName", std::string("Foo"))),
-      constructMatcher("namedDecl",
+      constructMatcher("functionDecl",
                        constructMatcher("hasName", std::string("foo"))))
       .getTypedMatcher<Decl>();
 
   EXPECT_TRUE(matches("void foo(){}", D));
   EXPECT_TRUE(matches("struct Foo{};", D));
   EXPECT_FALSE(matches("int i = 0;", D));
 
   D = constructMatcher(