Create iterators for `exprt` and associated utility functions

[jasigal]

@jasigal commented on Thu Jul 20 2017

Currently there is no good, unified way to do the following:

• Determine is any subexpression satisfies a predicate
• Find a subexpression that satisfies a predicate
• Count the number of subexpressions that satisfy a predicate
• Traverse an expression to create a new data structure
• Feed all subexpressions into a function one at a time

By adding iterators to exprts, we can use them to do all of the above more simply (as opposed to doing a stack based traversal by hand each time) and additionally make use of the <algorithm> standard library. Some functions may need to be back-ported from C++17/20.

The changes for exprt can be had in its class definition, and functions using these iterators specific to exprts can be put in util/expr.cpp.

---

@peterschrammel commented on Thu Jul 20 2017

@jasigal, move this issue to diffblue/cbmc please

[tautschnig]

I agree that these are repeated problems and I'm looking forward to seeing the solution :-)

[LAJW]

I'm on it.

So the first iterator would be exprt::depth_iteratort obtainable by calling exprt::depth_begin() and exprt::depth_end().

The reason for naming it depth_* instead of classic begin/end() would be to avoid confusing behaviour when calling:

for (const auto& child_expr : parent_expr)

Where parent_expr is some form of an array and the expected behaviour would be to do flat traversal.

STL algorithms would still be usable, just the specific iteration choice would be made explicit. For example:

std::for_each(
    expr.breadth_begin(),
    expr.breadth_end(),
    [](const exprt&) {
    // Do stuff
});

[LAJW]

Here's the PR implementing those iterators: #1165
Test-gen submodule update: https://github.com/diffblue/test-gen/pull/870

[TGWDB]

Closing as this is a feature request that is partially addressed and otherwise very old.