Qiskit / qiskit / 31708153674

88%

main: 88%

Build Type

push

github

Committed by web-flow

Commit Message

Reimplement SymbolExpr::eval to be iterative (backport #16756) (#16758)

* Reimplement SymbolExpr::eval to be iterative (#16756)

* Reimplement SymbolExpr::eval to be iterative

The previous implementation of the eval method for the SymbolExpr struct
was implemented recursively. While a recursive implementation of
expression tree traversal is very natural and a consise to write this
can lead to stack growth for large expression tree. This can lead to a
stack overflow if the expression tree being traversed is sufficiently
large. To avoid this issue this commit reimplements the eval method's
tree traversal to be iterative. The core of the algorithm does an
in-order tree traversal using a while loop. There is no functional
difference in how the tree is evaluated but it avoids the stack growth
issues with the recursive implementation.

One caveat for this implementation is as eval is often used internally
for methods on the SymbolExpr struct. For example, the SymbolExpr::eq()
method's implementation internally calls eval. So this iterative
implementation has to be done very carefully to avoid introducing
recursion accidently. During development an earlier attempt relied on
SymbolExpr::eq() which caused a similar recursion issue that could lead
to a stack overflow (much more easily actually because it would nest more
deeply).

This also adds two rust tests to the symbol_expr module. These are
largely dupliclative with existing tests in the python test suite,
but they were specific edge cases I needed to debug and doing it via
rust tests was simpler. I opted to leave them in as they basically add
no overhead to the test suite and they proved useful for the development
of this PR. But the bulk of the coverage still occurs via the python
test suite and these tests weren't intended to change that.

Fixes #16676

* Use approx equality for test to account for miri fp precision

* Delete test case with fp comparison

We don't need the rust test doing the floating... (continued)

Coverage Stats

110 of 133 new or added lines in 1 file covered. (82.71%)

30 existing lines in 4 files now uncovered.

113049 of 128862 relevant lines covered (87.73%)

996593.88 hits per line