Handle TemplateArgument in DynTypedNode comparison operations.

[alexfh]

Summary

This patch fixes an assertion failure on some matchers containing
templateArgument() on some code in some configurations. I couldn't come up with a
consistent repro, since the failure depens on the order of elements in a map.
http://reviews.llvm.org/D18136 contains a matcher that causes the issue at least
on some configurations.

The fix turned out to require non-trivial amount of code, very similar to
TemplateArgument::structurallyEquals. I'd prefer to use
TemplateArgument::Profile, if it was possible without ASTContext. Another
alternative would be to add operator< for TemplateArgument, but since it's only
needed in DynTypedNode, I decided to make this code private to DynTypedNode.

[sbenza]

I think the bug is coming from memoizedMatchesAncestorOfRecursively.
memoizedMatchesRecursively has a special case at the top to skip the cache if the node is not sortable. The other function should do that too.
Although the check is stale also because it is only checking for memoizationData and not whether the node itself works for < and ==.

Note that adding TemplateArgument to the function is ok, but that won't fix the bug because we still have other nodes that are not comparable.

include/clang/AST/ASTTypeTraits.h

269

this comment is stale.

[sbenza]

To be more specific, the problem comes from the use of hasAnscestor (done by isInTemplateInstantiation ) while there is a TemplateArgument in the bound nodes.
This tries to put the node into the cache.
To trigger this easily you only need to have a hit in the cache.
I think you can trigger it by adding a second line boost::lexical_cast<std::string>(42); in the string_as_T test. That second hit should get a cache hit and trigger the bug.

[alexfh]

In D19144#402853, @sbenza wrote:

I think the bug is coming from memoizedMatchesAncestorOfRecursively.
memoizedMatchesRecursively has a special case at the top to skip the cache if the node is not sortable. The other function should do that too.
Although the check is stale also because it is only checking for memoizationData and not whether the node itself works for < and ==.

Note that adding TemplateArgument to the function is ok, but that won't fix the bug because we still have other nodes that are not comparable.

With this I would be entering "I have no idea what I'm doing" land ;) Might make sense for you to take over the patch, if you know how to fix the issue. WDYT?

[sbenza]

Sent http://reviews.llvm.org/D19231 to fix the underlying bug in hasAncestor.
We can proceed with this change if you want, but it is not required anymore. I don't know whether we need the extra complexity of TemplateArgumentLess.

[alexfh]

In D19144#404234, @sbenza wrote:

Sent http://reviews.llvm.org/D19231 to fix the underlying bug in hasAncestor.
We can proceed with this change if you want, but it is not required anymore. I don't know whether we need the extra complexity of TemplateArgumentLess.

If this patch is not going to help with performance, I'm happy to abandon it.

[sbenza]

We can proceed with this change if you want, but it is not required anymore. I don't know whether we need the extra complexity of TemplateArgumentLess.

If this patch is not going to help with performance, I'm happy to abandon it.

It might help in the cases where you are doing hasAncestor with TemplateArgument bound nodes, but that is a small corner case and I don't think we need to optimize for it.

[alexfh]

Ok, let's drop this on the floor.

include/clang/AST/ASTTypeTraits.h

public:
 
   /// \brief For nodes which represent textual entities in the source code,
   /// return their SourceRange.  For all other nodes, return SourceRange().
   SourceRange getSourceRange() const;
 
   /// @{
   /// \brief Imposes an order on \c DynTypedNode.
   ///
   /// Supports comparison of nodes that support memoization.
   /// FIXME: Implement comparsion for other node types (currently
   /// only Stmt, Decl, Type and NestedNameSpecifier return memoization data).
   bool operator<(const DynTypedNode &Other) const {
     if (!NodeKind.isSame(Other.NodeKind))
       return NodeKind < Other.NodeKind;
 
     if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
       return getUnchecked<QualType>().getAsOpaquePtr() <
if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(
       auto NNSLA = getUnchecked<NestedNameSpecifierLoc>();
       auto NNSLB = Other.getUnchecked<NestedNameSpecifierLoc>();
       return std::make_pair(NNSLA.getNestedNameSpecifier(),
                             NNSLA.getOpaqueData()) <
              std::make_pair(NNSLB.getNestedNameSpecifier(),
                             NNSLB.getOpaqueData());
     }
 
+    if (ASTNodeKind::getFromNodeKind<TemplateArgument>().isSame(NodeKind))
+      return TemplateArgumentLess(getUnchecked<TemplateArgument>(),
+                                  Other.getUnchecked<TemplateArgument>());
+
     assert(getMemoizationData() && Other.getMemoizationData());
     return getMemoizationData() < Other.getMemoizationData();
   }
   bool operator==(const DynTypedNode &Other) const {
     // DynTypedNode::create() stores the exact kind of the node in NodeKind.
     // If they contain the same node, their NodeKind must be the same.
     if (!NodeKind.isSame(Other.NodeKind))
       return false;
 
     // FIXME: Implement for other types.
     if (ASTNodeKind::getFromNodeKind<QualType>().isSame(NodeKind))
       return getUnchecked<QualType>() == Other.getUnchecked<QualType>();
 
     if (ASTNodeKind::getFromNodeKind<TypeLoc>().isSame(NodeKind))
       return getUnchecked<TypeLoc>() == Other.getUnchecked<TypeLoc>();
 
     if (ASTNodeKind::getFromNodeKind<NestedNameSpecifierLoc>().isSame(NodeKind))
       return getUnchecked<NestedNameSpecifierLoc>() ==
              Other.getUnchecked<NestedNameSpecifierLoc>();
 
+    if (ASTNodeKind::getFromNodeKind<TemplateArgument>().isSame(NodeKind))
+      return getUnchecked<TemplateArgument>().structurallyEquals(
+          Other.getUnchecked<TemplateArgument>());
+
     assert(getMemoizationData() && Other.getMemoizationData());
     return getMemoizationData() == Other.getMemoizationData();
   }
   bool operator!=(const DynTypedNode &Other) const {
     return !operator==(Other);
   }
   /// @}
 
template <typename T> struct ValueConverter {
     static DynTypedNode create(const T &Node) {
       DynTypedNode Result;
       Result.NodeKind = ASTNodeKind::getFromNodeKind<T>();
       new (Result.Storage.buffer) T(Node);
       return Result;
     }
   };
 
+  static bool TemplateArgumentLess(const TemplateArgument &LHS,
+                                   const TemplateArgument &RHS);
+
   ASTNodeKind NodeKind;
 
   /// \brief Stores the data of the node.
   ///
   /// Note that we can store \c Decls, \c Stmts, \c Types,
   /// \c NestedNameSpecifiers and \c CXXCtorInitializer by pointer as they are
   /// guaranteed to be unique pointers pointing to dedicated storage in the AST.
   /// \c QualTypes, \c NestedNameSpecifierLocs, \c TypeLocs and

lib/AST/ASTTypeTraits.cpp

if (const TypeLoc *TL = get<TypeLoc>())
     return TL->getSourceRange();
   if (const Decl *D = get<Decl>())
     return D->getSourceRange();
   if (const Stmt *S = get<Stmt>())
     return S->getSourceRange();
   return SourceRange();
 }
 
+bool DynTypedNode::TemplateArgumentLess(const TemplateArgument &LHS,
+                                        const TemplateArgument &RHS) {
+  if (LHS.getKind() != RHS.getKind()) return LHS.getKind() < RHS.getKind();
+
+  switch (LHS.getKind()) {
+    case TemplateArgument::Null:
+      return false;
+
+    case TemplateArgument::Type:
+      return LHS.getAsType().getAsOpaquePtr() <
+             RHS.getAsType().getAsOpaquePtr();
+
+    case TemplateArgument::Expression:
+      return LHS.getAsExpr() < RHS.getAsExpr();
+
+    case TemplateArgument::Template:
+    case TemplateArgument::TemplateExpansion:
+      return LHS.getAsTemplateOrTemplatePattern().getAsVoidPointer() <
+             RHS.getAsTemplateOrTemplatePattern().getAsVoidPointer();
+
+    case TemplateArgument::NullPtr:
+      return LHS.getNullPtrType().getAsOpaquePtr() <
+             RHS.getNullPtrType().getAsOpaquePtr();
+
+    case TemplateArgument::Pack: {
+      if (LHS.pack_size() != RHS.pack_size())
+        return LHS.pack_size() < RHS.pack_size();
+      auto PackA = LHS.getPackAsArray();
+      auto PackB = RHS.getPackAsArray();
+      for (unsigned I = 0, E = PackA.size(); I != E; ++I)
+        if (!PackA[I].structurallyEquals(PackB[I]))
+          return TemplateArgumentLess(PackA[I], PackB[I]);
+      return false;
+    }
+
+    case TemplateArgument::Declaration:
+      return (LHS.getAsDecl() ? LHS.getAsDecl()->getCanonicalDecl() : nullptr) <
+             (RHS.getAsDecl() ? RHS.getAsDecl()->getCanonicalDecl() : nullptr);
+
+    case TemplateArgument::Integral:
+      return std::make_pair(LHS.getIntegralType().getAsOpaquePtr(),
+                            LHS.getAsIntegral()) <
+             std::make_pair(RHS.getIntegralType().getAsOpaquePtr(),
+                            RHS.getAsIntegral());
+
+  }
+  llvm_unreachable("Unsupported or invalid TemplateArgument kind");
+}
+
 } // end namespace ast_type_traits
 } // end namespace clang

unittests/AST/ASTTypeTraitsTest.cpp

 
 TEST(DynTypedNode, QualType) {
   QualType Q;
   DynTypedNode Node = DynTypedNode::create(Q);
   EXPECT_TRUE(Node == Node);
   EXPECT_FALSE(Node < Node);
 }
 
+TEST(DynTypedNode, TemplateArgumentNull) {
+  TemplateArgument T;
+  DynTypedNode Node = DynTypedNode::create(T);
+  EXPECT_TRUE(Node == Node);
+  EXPECT_FALSE(Node < Node);
+}
+
+TEST(DynTypedNode, TemplateArgumentQualType) {
+  QualType QT;
+  TemplateArgument T(QT);
+  DynTypedNode Node = DynTypedNode::create(T);
+  EXPECT_TRUE(Node == Node);
+  EXPECT_FALSE(Node < Node);
+}
+
+TEST(DynTypedNode, TemplateArgumentNullPtr) {
+  QualType QT;
+  TemplateArgument T(QT, true);
+  DynTypedNode Node = DynTypedNode::create(T);
+  EXPECT_TRUE(Node == Node);
+  EXPECT_FALSE(Node < Node);
+}
+
+TEST(DynTypedNode, TemplateArgumentExpr) {
+  BuiltinType Void(BuiltinType::Void);
+  QualType QT(&Void, 0);
+  NoInitExpr E(QT);
+  TemplateArgument T(&E);
+  DynTypedNode Node = DynTypedNode::create(T);
+  EXPECT_TRUE(Node == Node);
+  EXPECT_FALSE(Node < Node);
+}
+
+TEST(DynTypedNode, TemplateArgumentTemplate) {
+  TemplateName TN;
+  TemplateArgument T(TN);
+  DynTypedNode Node = DynTypedNode::create(T);
+  EXPECT_TRUE(Node == Node);
+  EXPECT_FALSE(Node < Node);
+}
+
+TEST(DynTypedNode, TemplateArgumentTemplateExpansion) {
+  TemplateName TN;
+  TemplateArgument T(TN, llvm::Optional<unsigned>(0u));
+  DynTypedNode Node = DynTypedNode::create(T);
+  EXPECT_TRUE(Node == Node);
+  EXPECT_FALSE(Node < Node);
+}
+
+TEST(DynTypedNode, TemplateArgumentPack) {
+  TemplateArgument TP[1];
+  TemplateArgument T(TP);
+  DynTypedNode Node = DynTypedNode::create(T);
+  EXPECT_TRUE(Node == Node);
+  EXPECT_FALSE(Node < Node);
+}
+
+// FIXME: Figure out how to test TemplateArgument of the Declaration and
+// Integral kinds.
+
 }  // namespace ast_type_traits
 }  // namespace clang