Fix lifetime and copy issues with NodeDfsIterable (#4569)
authorAndres Noetzli <andres.noetzli@gmail.com>
Fri, 5 Jun 2020 12:03:16 +0000 (05:03 -0700)
committerGitHub <noreply@github.com>
Fri, 5 Jun 2020 12:03:16 +0000 (07:03 -0500)
commit8b5ffcd602730db5bba135b557f60ca181b8af1f
tree42cff7e487b37cf596bf70d0611af424d754fd6d
parent4593ac048f355856232482bdc4964ce90d64169b
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
src/expr/node_traversal.h
test/unit/expr/node_traversal_black.h