diff options
author | Andres Noetzli <andres.noetzli@gmail.com> | 2020-06-05 05:03:16 -0700 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-06-05 07:03:16 -0500 |
commit | 8b5ffcd602730db5bba135b557f60ca181b8af1f (patch) | |
tree | 42cff7e487b37cf596bf70d0611af424d754fd6d /src | |
parent | 4593ac048f355856232482bdc4964ce90d64169b (diff) |
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
Diffstat (limited to 'src')
-rw-r--r-- | src/expr/node_traversal.cpp | 43 | ||||
-rw-r--r-- | src/expr/node_traversal.h | 50 |
2 files changed, 42 insertions, 51 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<bool(TNode)> 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<bool(TNode)> skipCondition) +NodeDfsIterable::NodeDfsIterable(TNode n, + VisitOrder order, + std::function<bool(TNode)> 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<bool(TNode)> skipIf); + NodeDfsIterator(TNode n, VisitOrder order, std::function<bool(TNode)> 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<TNode, bool, TNodeHashFunction> 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<bool(TNode)> 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<bool(TNode)> 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<bool(TNode)> 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<bool(TNode)> d_skipIf; }; |