From 7349479f2244c32c0184ca545af04adb171c8077 Mon Sep 17 00:00:00 2001 From: Dmitri Gribenko Date: Fri, 3 Jul 2020 13:55:01 +0200 Subject: [PATCH] RecursiveASTVisitor: don't call WalkUp unnecessarily in post-order traversal Summary: How does RecursiveASTVisitor call the WalkUp callback for expressions? * In pre-order traversal mode, RecursiveASTVisitor calls the WalkUp callback from the default implementation of Traverse callbacks. * In post-order traversal mode when we don't have a DataRecursionQueue, RecursiveASTVisitor also calls the WalkUp callback from the default implementation of Traverse callbacks. * However, in post-order traversal mode when we have a DataRecursionQueue, RecursiveASTVisitor calls the WalkUp callback from PostVisitStmt. As a result, when the user overrides the Traverse callback, in pre-order traversal mode they never get the corresponding WalkUp callback. However in the post-order traversal mode the WalkUp callback is invoked or not depending on whether the data recursion optimization could be applied. I had to adjust the implementation of TraverseCXXForRangeStmt in the syntax tree builder to call the WalkUp method directly, as it was relying on this behavior. There is an existing test for this functionality and it prompted me to make this extra fix. In addition, I had to fix the default implementation implementation of RecursiveASTVisitor::TraverseSynOrSemInitListExpr to call WalkUpFrom in the same manner as the implementation generated by the DEF_TRAVERSE_STMT macro. Without this fix, the InitListExprIsPostOrderNoQueueVisitedTwice test was failing because WalkUpFromInitListExpr was never called. Reviewers: eduucaldas, ymandel Reviewed By: eduucaldas, ymandel Subscribers: gribozavr2, cfe-commits Tags: #clang Differential Revision: https://reviews.llvm.org/D82486 --- clang/include/clang/AST/RecursiveASTVisitor.h | 89 ++++++++++++++++++---- clang/lib/Tooling/Syntax/BuildTree.cpp | 22 +++--- .../Tooling/RecursiveASTVisitorTests/Callbacks.cpp | 47 +++--------- 3 files changed, 98 insertions(+), 60 deletions(-) diff --git a/clang/include/clang/AST/RecursiveASTVisitor.h b/clang/include/clang/AST/RecursiveASTVisitor.h index b16c1ae1e48..464a80d15ce 100644 --- a/clang/include/clang/AST/RecursiveASTVisitor.h +++ b/clang/include/clang/AST/RecursiveASTVisitor.h @@ -83,6 +83,42 @@ namespace clang { return false; \ } while (false) +namespace detail { + +template +struct has_same_member_pointer_type : std::false_type {}; +template +struct has_same_member_pointer_type + : std::true_type {}; + +template struct is_same_method_impl { + template + static bool isSameMethod(FirstMethodPtrTy FirstMethodPtr, + SecondMethodPtrTy SecondMethodPtr) { + return false; + } +}; + +template <> struct is_same_method_impl { + template + static bool isSameMethod(FirstMethodPtrTy FirstMethodPtr, + SecondMethodPtrTy SecondMethodPtr) { + return FirstMethodPtr == SecondMethodPtr; + } +}; + +/// Returns true if and only if \p FirstMethodPtr and \p SecondMethodPtr +/// are pointers to the same non-static member function. +template +bool isSameMethod(FirstMethodPtrTy FirstMethodPtr, + SecondMethodPtrTy SecondMethodPtr) { + return is_same_method_impl::value>::isSameMethod(FirstMethodPtr, SecondMethodPtr); +} + +} // end namespace detail + /// A class that does preorder or postorder /// depth-first traversal on the entire Clang AST and visits each node. /// @@ -325,23 +361,17 @@ public: Stmt::child_range getStmtChildren(Stmt *S) { return S->children(); } private: - template - struct has_same_member_pointer_type : std::false_type {}; - template - struct has_same_member_pointer_type - : std::true_type {}; - // Traverse the given statement. If the most-derived traverse function takes a // data recursion queue, pass it on; otherwise, discard it. Note that the // first branch of this conditional must compile whether or not the derived // class can take a queue, so if we're taking the second arm, make the first // arm call our function rather than the derived class version. #define TRAVERSE_STMT_BASE(NAME, CLASS, VAR, QUEUE) \ - (has_same_member_pointer_type::value \ + (::clang::detail::has_same_member_pointer_type< \ + decltype(&RecursiveASTVisitor::Traverse##NAME), \ + decltype(&Derived::Traverse##NAME)>::value \ ? static_cast::value, \ Derived &, RecursiveASTVisitor &>>(*this) \ @@ -609,17 +639,38 @@ bool RecursiveASTVisitor::PostVisitStmt(Stmt *S) { #define ABSTRACT_STMT(STMT) #define STMT(CLASS, PARENT) \ case Stmt::CLASS##Class: \ - TRY_TO(WalkUpFrom##CLASS(static_cast(S))); break; + /* In pre-order traversal mode, each Traverse##STMT method is responsible \ + * for calling WalkUpFrom. Therefore, if the user overrides Traverse##STMT \ + * and does not call the default implementation, the WalkUpFrom callback \ + * is not called. Post-order traversal mode should provide the same \ + * behavior regarding method overrides. \ + * \ + * In post-order traversal mode the Traverse##STMT method, when it \ + * receives a DataRecursionQueue, can't call WalkUpFrom after traversing \ + * children because it only enqueues the children and does not traverse \ + * them. TraverseStmt traverses the enqueued children, and we call \ + * WalkUpFrom here. \ + * \ + * However, to make pre-order and post-order modes identical with regards \ + * to whether they call WalkUpFrom at all, we call WalkUpFrom if and only \ + * if the user did not override the Traverse##STMT method. */ \ + if (::clang::detail::isSameMethod(&RecursiveASTVisitor::Traverse##CLASS, \ + &Derived::Traverse##CLASS)) { \ + TRY_TO(WalkUpFrom##CLASS(static_cast(S))); \ + } \ + break; #define INITLISTEXPR(CLASS, PARENT) \ case Stmt::CLASS##Class: \ - { \ + /* See the comment above for the explanation of the isSameMethod check. */ \ + if (::clang::detail::isSameMethod(&RecursiveASTVisitor::Traverse##CLASS, \ + &Derived::Traverse##CLASS)) { \ auto ILE = static_cast(S); \ if (auto Syn = ILE->isSemanticForm() ? ILE->getSyntacticForm() : ILE) \ TRY_TO(WalkUpFrom##CLASS(Syn)); \ if (auto Sem = ILE->isSemanticForm() ? ILE : ILE->getSemanticForm()) \ TRY_TO(WalkUpFrom##CLASS(Sem)); \ - break; \ - } + } \ + break; #include "clang/AST/StmtNodes.inc" } @@ -2216,8 +2267,13 @@ DEF_TRAVERSE_DECL(RequiresExprBodyDecl, {}) TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(SubStmt); \ } \ } \ - if (!Queue && ReturnValue && getDerived().shouldTraversePostOrder()) \ + /* Call WalkUpFrom if TRY_TO_TRAVERSE_OR_ENQUEUE_STMT has traversed the \ + * children already. If TRY_TO_TRAVERSE_OR_ENQUEUE_STMT only enqueued the \ + * children, PostVisitStmt will call WalkUpFrom after we are done visiting \ + * children. */ \ + if (!Queue && ReturnValue && getDerived().shouldTraversePostOrder()) { \ TRY_TO(WalkUpFrom##STMT(S)); \ + } \ return ReturnValue; \ } @@ -2388,6 +2444,9 @@ bool RecursiveASTVisitor::TraverseSynOrSemInitListExpr( for (Stmt *SubStmt : S->children()) { TRY_TO_TRAVERSE_OR_ENQUEUE_STMT(SubStmt); } + + if (!Queue && getDerived().shouldTraversePostOrder()) + TRY_TO(WalkUpFromInitListExpr(S)); } return true; } diff --git a/clang/lib/Tooling/Syntax/BuildTree.cpp b/clang/lib/Tooling/Syntax/BuildTree.cpp index 8185af2a6cc..4371a303bb9 100644 --- a/clang/lib/Tooling/Syntax/BuildTree.cpp +++ b/clang/lib/Tooling/Syntax/BuildTree.cpp @@ -578,15 +578,19 @@ public: // RAV traverses it as a statement, we produce invalid node kinds in that // case. // FIXME: should do this in RAV instead? - if (S->getInit() && !TraverseStmt(S->getInit())) - return false; - if (S->getLoopVariable() && !TraverseDecl(S->getLoopVariable())) - return false; - if (S->getRangeInit() && !TraverseStmt(S->getRangeInit())) - return false; - if (S->getBody() && !TraverseStmt(S->getBody())) - return false; - return true; + bool Result = [&, this]() { + if (S->getInit() && !TraverseStmt(S->getInit())) + return false; + if (S->getLoopVariable() && !TraverseDecl(S->getLoopVariable())) + return false; + if (S->getRangeInit() && !TraverseStmt(S->getRangeInit())) + return false; + if (S->getBody() && !TraverseStmt(S->getBody())) + return false; + return true; + }(); + WalkUpFromCXXForRangeStmt(S); + return Result; } bool TraverseStmt(Stmt *S) { diff --git a/clang/unittests/Tooling/RecursiveASTVisitorTests/Callbacks.cpp b/clang/unittests/Tooling/RecursiveASTVisitorTests/Callbacks.cpp index 66aa1d76383..1ab843d437a 100644 --- a/clang/unittests/Tooling/RecursiveASTVisitorTests/Callbacks.cpp +++ b/clang/unittests/Tooling/RecursiveASTVisitorTests/Callbacks.cpp @@ -154,22 +154,17 @@ TraverseIntegerLiteral IntegerLiteral(5) R"txt( TraverseIntegerLiteral IntegerLiteral(1) WalkUpFromStmt IntegerLiteral(1) -WalkUpFromStmt IntegerLiteral(1) TraverseIntegerLiteral IntegerLiteral(2) WalkUpFromStmt IntegerLiteral(2) -WalkUpFromStmt IntegerLiteral(2) TraverseIntegerLiteral IntegerLiteral(3) WalkUpFromStmt IntegerLiteral(3) -WalkUpFromStmt IntegerLiteral(3) WalkUpFromStmt BinaryOperator(+) WalkUpFromStmt DeclRefExpr(add) WalkUpFromStmt ImplicitCastExpr TraverseIntegerLiteral IntegerLiteral(4) WalkUpFromStmt IntegerLiteral(4) -WalkUpFromStmt IntegerLiteral(4) TraverseIntegerLiteral IntegerLiteral(5) WalkUpFromStmt IntegerLiteral(5) -WalkUpFromStmt IntegerLiteral(5) WalkUpFromStmt CallExpr(add) WalkUpFromStmt CompoundStmt )txt")); @@ -258,23 +253,14 @@ TraverseIntegerLiteral IntegerLiteral(1) WalkUpFromIntegerLiteral IntegerLiteral(1) WalkUpFromExpr IntegerLiteral(1) WalkUpFromStmt IntegerLiteral(1) -WalkUpFromIntegerLiteral IntegerLiteral(1) - WalkUpFromExpr IntegerLiteral(1) - WalkUpFromStmt IntegerLiteral(1) TraverseIntegerLiteral IntegerLiteral(2) WalkUpFromIntegerLiteral IntegerLiteral(2) WalkUpFromExpr IntegerLiteral(2) WalkUpFromStmt IntegerLiteral(2) -WalkUpFromIntegerLiteral IntegerLiteral(2) - WalkUpFromExpr IntegerLiteral(2) - WalkUpFromStmt IntegerLiteral(2) TraverseIntegerLiteral IntegerLiteral(3) WalkUpFromIntegerLiteral IntegerLiteral(3) WalkUpFromExpr IntegerLiteral(3) WalkUpFromStmt IntegerLiteral(3) -WalkUpFromIntegerLiteral IntegerLiteral(3) - WalkUpFromExpr IntegerLiteral(3) - WalkUpFromStmt IntegerLiteral(3) WalkUpFromExpr BinaryOperator(+) WalkUpFromStmt BinaryOperator(+) WalkUpFromExpr DeclRefExpr(add) @@ -285,16 +271,10 @@ TraverseIntegerLiteral IntegerLiteral(4) WalkUpFromIntegerLiteral IntegerLiteral(4) WalkUpFromExpr IntegerLiteral(4) WalkUpFromStmt IntegerLiteral(4) -WalkUpFromIntegerLiteral IntegerLiteral(4) - WalkUpFromExpr IntegerLiteral(4) - WalkUpFromStmt IntegerLiteral(4) TraverseIntegerLiteral IntegerLiteral(5) WalkUpFromIntegerLiteral IntegerLiteral(5) WalkUpFromExpr IntegerLiteral(5) WalkUpFromStmt IntegerLiteral(5) -WalkUpFromIntegerLiteral IntegerLiteral(5) - WalkUpFromExpr IntegerLiteral(5) - WalkUpFromStmt IntegerLiteral(5) WalkUpFromExpr CallExpr(add) WalkUpFromStmt CallExpr(add) WalkUpFromStmt CompoundStmt @@ -436,12 +416,13 @@ WalkUpFromStmt IntegerLiteral(2) WalkUpFromStmt IntegerLiteral(3) )txt")); + // FIXME: The following log should include a call to WalkUpFromStmt for + // UnaryOperator(-). EXPECT_TRUE(visitorCallbackLogEqual( RecordingVisitor(ShouldTraversePostOrder::Yes), Code, R"txt( WalkUpFromStmt IntegerLiteral(1) WalkUpFromStmt IntegerLiteral(2) -WalkUpFromStmt UnaryOperator(-) WalkUpFromStmt IntegerLiteral(3) WalkUpFromStmt CompoundStmt )txt")); @@ -507,6 +488,8 @@ WalkUpFromExpr IntegerLiteral(3) WalkUpFromStmt IntegerLiteral(3) )txt")); + // FIXME: The following log should include a call to WalkUpFromUnaryOperator + // for UnaryyOperator(-). EXPECT_TRUE(visitorCallbackLogEqual( RecordingVisitor(ShouldTraversePostOrder::Yes), Code, R"txt( @@ -514,9 +497,6 @@ WalkUpFromExpr IntegerLiteral(1) WalkUpFromStmt IntegerLiteral(1) WalkUpFromExpr IntegerLiteral(2) WalkUpFromStmt IntegerLiteral(2) -WalkUpFromUnaryOperator UnaryOperator(-) - WalkUpFromExpr UnaryOperator(-) - WalkUpFromStmt UnaryOperator(-) WalkUpFromExpr IntegerLiteral(3) WalkUpFromStmt IntegerLiteral(3) WalkUpFromStmt CompoundStmt @@ -817,13 +797,14 @@ WalkUpFromStmt IntegerLiteral(3) WalkUpFromStmt IntegerLiteral(4) )txt")); + // FIXME: The following log should include a call to WalkUpFromStmt for + // BinaryOperator(+). EXPECT_TRUE(visitorCallbackLogEqual( RecordingVisitor(ShouldTraversePostOrder::Yes), Code, R"txt( WalkUpFromStmt IntegerLiteral(1) WalkUpFromStmt IntegerLiteral(2) WalkUpFromStmt IntegerLiteral(3) -WalkUpFromStmt BinaryOperator(+) WalkUpFromStmt IntegerLiteral(4) WalkUpFromStmt CompoundStmt )txt")); @@ -891,6 +872,7 @@ WalkUpFromExpr IntegerLiteral(4) WalkUpFromStmt IntegerLiteral(4) )txt")); + // FIXME: The following log should include a call to WalkUpFromBinaryOperator. EXPECT_TRUE(visitorCallbackLogEqual( RecordingVisitor(ShouldTraversePostOrder::Yes), Code, R"txt( @@ -900,9 +882,6 @@ WalkUpFromExpr IntegerLiteral(2) WalkUpFromStmt IntegerLiteral(2) WalkUpFromExpr IntegerLiteral(3) WalkUpFromStmt IntegerLiteral(3) -WalkUpFromBinaryOperator BinaryOperator(+) - WalkUpFromExpr BinaryOperator(+) - WalkUpFromStmt BinaryOperator(+) WalkUpFromExpr IntegerLiteral(4) WalkUpFromStmt IntegerLiteral(4) WalkUpFromStmt CompoundStmt @@ -1216,13 +1195,14 @@ WalkUpFromStmt IntegerLiteral(2) WalkUpFromStmt IntegerLiteral(3) )txt")); + // FIXME: The following log should include a call to WalkUpFromStmt for + // CompoundAssignOperator(+=). EXPECT_TRUE(visitorCallbackLogEqual( RecordingVisitor(ShouldTraversePostOrder::Yes), Code, R"txt( WalkUpFromStmt IntegerLiteral(1) WalkUpFromStmt DeclRefExpr(a) WalkUpFromStmt IntegerLiteral(2) -WalkUpFromStmt CompoundAssignOperator(+=) WalkUpFromStmt IntegerLiteral(3) WalkUpFromStmt CompoundStmt )txt")); @@ -1291,6 +1271,8 @@ WalkUpFromExpr IntegerLiteral(3) WalkUpFromStmt IntegerLiteral(3) )txt")); + // FIXME: The following log should include a call to + // WalkUpFromCompoundAssignOperator. EXPECT_TRUE(visitorCallbackLogEqual( RecordingVisitor(ShouldTraversePostOrder::Yes), Code, R"txt( @@ -1300,9 +1282,6 @@ WalkUpFromExpr DeclRefExpr(a) WalkUpFromStmt DeclRefExpr(a) WalkUpFromExpr IntegerLiteral(2) WalkUpFromStmt IntegerLiteral(2) -WalkUpFromCompoundAssignOperator CompoundAssignOperator(+=) - WalkUpFromExpr CompoundAssignOperator(+=) - WalkUpFromStmt CompoundAssignOperator(+=) WalkUpFromExpr IntegerLiteral(3) WalkUpFromStmt IntegerLiteral(3) WalkUpFromStmt CompoundStmt @@ -1636,7 +1615,6 @@ TraverseCallExpr CallExpr(add) WalkUpFromStmt IntegerLiteral(4) WalkUpFromStmt IntegerLiteral(5) WalkUpFromStmt CallExpr(add) -WalkUpFromStmt CallExpr(add) WalkUpFromStmt CompoundStmt )txt")); } @@ -1730,9 +1708,6 @@ TraverseCallExpr CallExpr(add) WalkUpFromCallExpr CallExpr(add) WalkUpFromExpr CallExpr(add) WalkUpFromStmt CallExpr(add) -WalkUpFromCallExpr CallExpr(add) - WalkUpFromExpr CallExpr(add) - WalkUpFromStmt CallExpr(add) WalkUpFromStmt CompoundStmt )txt")); } -- 2.11.0