From 8b5ffcd602730db5bba135b557f60ca181b8af1f Mon Sep 17 00:00:00 2001 From: Andres Noetzli Date: Fri, 5 Jun 2020 05:03:16 -0700 Subject: [PATCH] Fix lifetime and copy issues with NodeDfsIterable (#4569) When running node_traversal_black with ASan and UBSan, there were two distinct issues being reported. UBSan was complaining that we were assigning an invalid value to a Boolean. This happened because d_initialized in NodeDfsIterator was uninitialized and the default copy constructor tried to copy it. This commit removes that data member. ASan was complainig that NodeDfsIterator::begin() was trying to access a skip function that had been freed. In particular, this happened when NodeDfsIterable was used in a range-based for loop like so: for (auto n : NodeDfsIterable(n).inPostorder()) { ... } The problem here is that the lifetime of a temporary within the range expression is not extended (the lifetime of the result of the range expression is extended, however) [0]. This is a problem because NodeDfsIterable(n) is a temporary and inPostorder() returns a reference to that temporary. It makes sense that the compiler cannot possibly know that the reference from inPostorder() corresponds to NodeDfsIterable(n), so it cannot extend its lifetime. See [1] for more details on the problem with chained functions. This commit fixes the issue by replacing the fluent interface of NodeDfsIterable by a constructor with default arguments. Additionally, it introduces an enum to represent the visit order to avoid having a nondescript Boolean argument. [0] https://en.cppreference.com/w/cpp/language/range-for#Temporary_range_expression [1] http://cpptruths.blogspot.com/2018/10/chained-functions-break-reference.html?m=1 --- src/expr/node_traversal.cpp | 43 +++++++---------------- src/expr/node_traversal.h | 50 ++++++++++++++++----------- test/unit/expr/node_traversal_black.h | 32 ++++++++--------- 3 files changed, 58 insertions(+), 67 deletions(-) diff --git a/src/expr/node_traversal.cpp b/src/expr/node_traversal.cpp index ad1a9ec71..c55388c3a 100644 --- a/src/expr/node_traversal.cpp +++ b/src/expr/node_traversal.cpp @@ -17,20 +17,20 @@ namespace CVC4 { NodeDfsIterator::NodeDfsIterator(TNode n, - bool postorder, + VisitOrder order, std::function skipIf) : d_stack{n}, d_visited(), - d_postorder(postorder), + d_order(order), d_current(TNode()), d_skipIf(skipIf) { } -NodeDfsIterator::NodeDfsIterator(bool postorder) +NodeDfsIterator::NodeDfsIterator(VisitOrder order) : d_stack(), d_visited(), - d_postorder(postorder), + d_order(order), d_current(TNode()), d_skipIf([](TNode) { return false; }) { @@ -70,7 +70,7 @@ bool NodeDfsIterator::operator==(const NodeDfsIterator& other) const // // Users should not compare iterators for traversals of different nodes, or // traversals with different skipIfs. - Assert(d_postorder == other.d_postorder); + Assert(d_order == other.d_order); return d_stack == other.d_stack && d_current == other.d_current; } @@ -102,12 +102,12 @@ void NodeDfsIterator::advanceToNextVisit() { d_stack.push_back(back[i]); } - if (!d_postorder) + if (d_order == VisitOrder::PREORDER) { return; } } - else if (!d_postorder || visitEntry->second) + else if (d_order == VisitOrder::PREORDER || visitEntry->second) { // if we're previsiting or we've already post-visited this node: skip it d_stack.pop_back(); @@ -134,38 +134,21 @@ void NodeDfsIterator::initializeIfUninitialized() } } -NodeDfsIterable::NodeDfsIterable(TNode n) - : d_node(n), d_postorder(true), d_skipIf([](TNode) { return false; }) -{ -} - -NodeDfsIterable& NodeDfsIterable::inPostorder() -{ - d_postorder = true; - return *this; -} - -NodeDfsIterable& NodeDfsIterable::inPreorder() -{ - d_postorder = false; - return *this; -} - -NodeDfsIterable& NodeDfsIterable::skipIf( - std::function skipCondition) +NodeDfsIterable::NodeDfsIterable(TNode n, + VisitOrder order, + std::function skipIf) + : d_node(n), d_order(order), d_skipIf(skipIf) { - d_skipIf = skipCondition; - return *this; } NodeDfsIterator NodeDfsIterable::begin() const { - return NodeDfsIterator(d_node, d_postorder, d_skipIf); + return NodeDfsIterator(d_node, d_order, d_skipIf); } NodeDfsIterator NodeDfsIterable::end() const { - return NodeDfsIterator(d_postorder); + return NodeDfsIterator(d_order); } } // namespace CVC4 diff --git a/src/expr/node_traversal.h b/src/expr/node_traversal.h index 1078f08c8..325cbc823 100644 --- a/src/expr/node_traversal.h +++ b/src/expr/node_traversal.h @@ -27,7 +27,16 @@ namespace CVC4 { -// Iterator for traversing a node in post-order +/** + * Enum that represents an order in which nodes are visited. + */ +enum class VisitOrder +{ + PREORDER, + POSTORDER +}; + +// Iterator for traversing a node in pre-/post-order // It does DAG-traversal, so indentical sub-nodes will be visited once only. class NodeDfsIterator { @@ -40,9 +49,9 @@ class NodeDfsIterator using difference_type = std::ptrdiff_t; // Construct a traversal iterator beginning at `n` - NodeDfsIterator(TNode n, bool postorder, std::function skipIf); + NodeDfsIterator(TNode n, VisitOrder order, std::function skipIf); // Construct an end-of-traversal iterator - NodeDfsIterator(bool postorder); + NodeDfsIterator(VisitOrder order); // Move/copy construction and assignment. Destructor. NodeDfsIterator(NodeDfsIterator&&) = default; @@ -88,12 +97,8 @@ class NodeDfsIterator // Set to `true` if we've also already post-visited it. std::unordered_map d_visited; - // Whether this is a post-order iterator (the alternative is pre-order) - bool d_postorder; - - // Whether this iterator has been initialized (advanced to its first - // visit) - bool d_initialized; + // The visit order that this iterator is using + VisitOrder d_order; // Current referent node. A valid node to visit if non-null. // Null after construction (but before first access) and at the end. @@ -103,20 +108,23 @@ class NodeDfsIterator std::function d_skipIf; }; -// Node wrapper that is iterable in DAG post-order +// Node wrapper that is iterable in DAG pre-/post-order class NodeDfsIterable { public: - NodeDfsIterable(TNode n); - - // Modifying the traversal order - // Modify this iterable to be in post-order (default) - NodeDfsIterable& inPostorder(); - // Modify this iterable to be in pre-order - NodeDfsIterable& inPreorder(); - - // Skip a node (and its descendants) if true. - NodeDfsIterable& skipIf(std::function skipCondition); + /** + * Creates a new node wrapper that can be used to iterate over the children + * of a node in pre-/post-order. + * + * @param n The node the iterate + * @param order The order in which the children are visited. + * @param skipIf Function that determines whether a given node and its + * descendants should be skipped or not. + */ + NodeDfsIterable( + TNode n, + VisitOrder order = VisitOrder::POSTORDER, + std::function skipIf = [](TNode) { return false; }); // Move/copy construction and assignment. Destructor. NodeDfsIterable(NodeDfsIterable&&) = default; @@ -130,7 +138,7 @@ class NodeDfsIterable private: TNode d_node; - bool d_postorder; + VisitOrder d_order; std::function d_skipIf; }; diff --git a/test/unit/expr/node_traversal_black.h b/test/unit/expr/node_traversal_black.h index b751a0999..7e08f209d 100644 --- a/test/unit/expr/node_traversal_black.h +++ b/test/unit/expr/node_traversal_black.h @@ -58,7 +58,7 @@ class NodePostorderTraversalBlack : public CxxTest::TestSuite Node eb = d_nodeManager->mkConst(false); Node cnd = d_nodeManager->mkNode(XOR, tb, eb); - auto traversal = NodeDfsIterable(cnd).inPostorder(); + auto traversal = NodeDfsIterable(cnd, VisitOrder::POSTORDER); NodeDfsIterator i = traversal.begin(); NodeDfsIterator end = traversal.end(); TS_ASSERT_EQUALS(*i, tb); @@ -79,7 +79,7 @@ class NodePostorderTraversalBlack : public CxxTest::TestSuite Node eb = d_nodeManager->mkConst(false); Node cnd = d_nodeManager->mkNode(XOR, tb, eb); - auto traversal = NodeDfsIterable(cnd).inPostorder(); + auto traversal = NodeDfsIterable(cnd, VisitOrder::POSTORDER); NodeDfsIterator i = traversal.begin(); NodeDfsIterator end = traversal.end(); TS_ASSERT_EQUALS(*(i++), tb); @@ -108,7 +108,7 @@ class NodePostorderTraversalBlack : public CxxTest::TestSuite Node cnd = d_nodeManager->mkNode(XOR, tb, eb); size_t count = 0; - for (auto i : NodeDfsIterable(cnd).inPostorder()) + for (auto i : NodeDfsIterable(cnd, VisitOrder::POSTORDER)) { ++count; } @@ -122,7 +122,7 @@ class NodePostorderTraversalBlack : public CxxTest::TestSuite Node cnd = d_nodeManager->mkNode(XOR, tb, eb); size_t count = 0; - for (auto i : NodeDfsIterable(cnd).inPostorder()) + for (auto i : NodeDfsIterable(cnd, VisitOrder::POSTORDER)) { if (i.isConst()) { @@ -139,7 +139,7 @@ class NodePostorderTraversalBlack : public CxxTest::TestSuite Node cnd = d_nodeManager->mkNode(XOR, tb, eb); Node top = d_nodeManager->mkNode(XOR, cnd, cnd); - auto traversal = NodeDfsIterable(top).inPostorder(); + auto traversal = NodeDfsIterable(top, VisitOrder::POSTORDER); size_t count = std::count_if(traversal.begin(), traversal.end(), @@ -155,7 +155,7 @@ class NodePostorderTraversalBlack : public CxxTest::TestSuite Node top = d_nodeManager->mkNode(XOR, cnd, cnd); std::vector expected = {tb, eb, cnd, top}; - auto traversal = NodeDfsIterable(top).inPostorder(); + auto traversal = NodeDfsIterable(top, VisitOrder::POSTORDER); std::vector actual; std::copy(traversal.begin(), traversal.end(), std::back_inserter(actual)); @@ -170,8 +170,8 @@ class NodePostorderTraversalBlack : public CxxTest::TestSuite Node top = d_nodeManager->mkNode(XOR, cnd, cnd); std::vector expected = {top}; - auto traversal = NodeDfsIterable(top).inPostorder().skipIf( - [&cnd](TNode n) { return n == cnd; }); + auto traversal = NodeDfsIterable( + top, VisitOrder::POSTORDER, [&cnd](TNode n) { return n == cnd; }); std::vector actual; std::copy(traversal.begin(), traversal.end(), std::back_inserter(actual)); @@ -204,7 +204,7 @@ class NodePreorderTraversalBlack : public CxxTest::TestSuite Node eb = d_nodeManager->mkConst(false); Node cnd = d_nodeManager->mkNode(XOR, tb, eb); - auto traversal = NodeDfsIterable(cnd).inPreorder(); + auto traversal = NodeDfsIterable(cnd, VisitOrder::PREORDER); NodeDfsIterator i = traversal.begin(); NodeDfsIterator end = traversal.end(); TS_ASSERT_EQUALS(*i, cnd); @@ -225,7 +225,7 @@ class NodePreorderTraversalBlack : public CxxTest::TestSuite Node eb = d_nodeManager->mkConst(false); Node cnd = d_nodeManager->mkNode(XOR, tb, eb); - auto traversal = NodeDfsIterable(cnd).inPreorder(); + auto traversal = NodeDfsIterable(cnd, VisitOrder::PREORDER); NodeDfsIterator i = traversal.begin(); NodeDfsIterator end = traversal.end(); TS_ASSERT_EQUALS(*(i++), cnd); @@ -241,7 +241,7 @@ class NodePreorderTraversalBlack : public CxxTest::TestSuite Node cnd = d_nodeManager->mkNode(XOR, tb, eb); size_t count = 0; - for (auto i : NodeDfsIterable(cnd).inPreorder()) + for (auto i : NodeDfsIterable(cnd, VisitOrder::PREORDER)) { ++count; } @@ -255,7 +255,7 @@ class NodePreorderTraversalBlack : public CxxTest::TestSuite Node cnd = d_nodeManager->mkNode(XOR, tb, eb); size_t count = 0; - for (auto i : NodeDfsIterable(cnd).inPreorder()) + for (auto i : NodeDfsIterable(cnd, VisitOrder::PREORDER)) { if (i.isConst()) { @@ -272,7 +272,7 @@ class NodePreorderTraversalBlack : public CxxTest::TestSuite Node cnd = d_nodeManager->mkNode(XOR, tb, eb); Node top = d_nodeManager->mkNode(XOR, cnd, cnd); - auto traversal = NodeDfsIterable(top).inPreorder(); + auto traversal = NodeDfsIterable(top, VisitOrder::PREORDER); size_t count = std::count_if(traversal.begin(), traversal.end(), @@ -288,7 +288,7 @@ class NodePreorderTraversalBlack : public CxxTest::TestSuite Node top = d_nodeManager->mkNode(XOR, cnd, cnd); std::vector expected = {top, cnd, tb, eb}; - auto traversal = NodeDfsIterable(top).inPreorder(); + auto traversal = NodeDfsIterable(top, VisitOrder::PREORDER); std::vector actual; std::copy(traversal.begin(), traversal.end(), std::back_inserter(actual)); @@ -303,8 +303,8 @@ class NodePreorderTraversalBlack : public CxxTest::TestSuite Node top = d_nodeManager->mkNode(XOR, cnd, cnd); std::vector expected = {top, cnd, eb}; - auto traversal = NodeDfsIterable(top).inPreorder().skipIf( - [&tb](TNode n) { return n == tb; }); + auto traversal = NodeDfsIterable( + top, VisitOrder::PREORDER, [&tb](TNode n) { return n == tb; }); std::vector actual; std::copy(traversal.begin(), traversal.end(), std::back_inserter(actual)); -- 2.30.2