Make eval/FullBinaryNode tree traversal iterative (stack-safe for deep trees)

[evaleev]

Squash the code-recursive tree traversals in the eval layer so evaluation of a deep tree (a long contraction chain, or a nested Sum) is bounded by the heap rather than the C++ call stack. Previously such a tree overflowed the stack at depth ~thousands -- in the evaluate() walk, and (before evaluation even ran) in FullBinaryNode's copy/transform/destroy.

binary_node: deep_copy, transform_node, and the destructor iterative

FullBinaryNode owns its children by unique_ptr, so the implicit destructor recursed to the tree's depth; deep_copy() and the free function transform_node() likewise recursed.

• ~FullBinaryNode() dismantles the subtree via a work list, detaching each node's children before it is destroyed, so every node destruction is O(1).
• deep_copy() and transform_node() do an iterative post-order build with an explicit frame stack (std::deque, so a top-frame reference survives push_back). transform_node applies its data map post-order; as a pure map its order is immaterial, and its only callers (typed binarize<T> and the TA to_ta_node helper) are order-insensitive.

The tree fold (fold_left_to_node / the range-accumulate ctor) and the tree visitors (detail::visit, parent-pointer based) were already iterative. size(), operator==, and digraph/tikz remain recursive but are not on the build/eval/destroy path.

eval: the core evaluate() traversal iterative

The core evaluate(node, le, cache) -- the only overload with unbounded recursion (the layout/multi-root overloads just wrap or loop over it) -- now walks with an explicit std::deque work stack. The per-node cache key is EvalExpr's stored O(1) hash, so nothing in the walk recurses.

Behavior is preserved:

• Checked cache wrapper: a hit returns the phase-applied cached pointer; a miss on a mapped node schedules a store once computed (a store_after flag replaces the recursive evaluate<..., Unchecked> re-entry).
• Custom-evaluator interception is consulted when a frame is first visited, and a non-null result short-circuits the subtree (children never pushed) -- the subtree pruning custom evaluators rely on is unchanged.
• leaf / Adjoint / Sum / Product dispatch, the shaped-product hook, de-nesting, canonicalization-phase multiplication, and every trace log site carry over unchanged.

Tests

• [FullBinaryNode][stack-safety]: build, copy, transform_node, and destroy a depth-200000 tree (all O(N)); pre-refactor this overflowed the stack.
• [eval_tapp][custom-evaluator]: pins the interception contract on the plain (non-batched) path -- a non-null custom result short-circuits the subtree (leaves never evaluated), a null result declines to the standard scheme.

[Copilot]

Pull request overview

This PR refactors evaluation-tree traversal and FullBinaryNode subtree operations to be iterative, making deep-tree evaluation/copy/transform/destruction stack-safe (bounded by heap rather than C++ call stack). This targets previously observed stack overflows on trees with depth in the thousands+ during evaluation and node lifecycle operations.

Changes:

• Reworked eval::evaluate(node, le, cache) to use an explicit frame stack (std::deque) instead of recursion, preserving cache behavior and custom-evaluator interception semantics.
• Made FullBinaryNode deep copy, transform_node, and destruction iterative to avoid recursive depth during copy/transform/destroy.
• Added unit tests to cover deep-tree stack-safety and to pin the custom-evaluator short-circuit contract on the non-batched evaluation path.

Reviewed changes

Copilot reviewed 4 out of 4 changed files in this pull request and generated 1 comment.

File	Description
tests/unit/test_eval_tapp.cpp	Adds a unit test ensuring custom-evaluator interception is consulted pre-scheme and can short-circuit subtree evaluation.
tests/unit/test_binary_node.cpp	Adds a deep-tree (depth 200k) stack-safety regression test for copy/transform/destruction.
SeQuant/core/eval/eval.hpp	Refactors the core evaluate() traversal to be iterative via an explicit stack of frames.
SeQuant/core/binary_node.hpp	Implements iterative deep_copy, transform_node, and a non-recursive subtree destructor for FullBinaryNode.

---

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

[evaleev]

This store-then-return-phase pattern is a faithful copy of the pre-existing recursive code on master, not a change introduced by this PR. Master's Checked wrapper does the same in its cache.exists(node) branch:

auto ptr = cache.store(
    node, mult_by_phase(evaluate<..., Unchecked>(node, le, cache)));
return mult_by_phase(ptr);

finish_phase_b mirrors that exactly (store apply_phase(...), return apply_phase(ptr)), and the already-cached cache.access branch applies the phase once in both master and this PR. This PR is a mechanical recursion->iteration refactor that preserves evaluation semantics; the real-tree [dryrun-eval] results are unchanged. The "aliasing" comment concerns the operand (child) buffers on the binary-eval path (a child with canon_phase()!=1 keeps its pre-phase buffer in the cache, so it cannot be consumed by move) -- a separate node from the one being stored here. If there is a latent double-phase concern it is pre-existing on master and out of scope for a stack-safety refactor; happy to file it separately.

[evaleev]

Followed up with a full trace of the cache/phase semantics -- the double application is intentional and correct, not a latent bug (superseding my "happy to file separately" note above):

• apply_phase always fresh-allocates (res->mult_by_phase(phase) constructs a new eval_result; never mutates in place), so the two calls make two distinct buffers -- the cached buffer is never re-mutated.
• cache.store(key, ptr) returns the same buffer it was handed (entry::store then entry::access -> same data_p), so the return does re-apply phase: cache holds phase*rb, caller gets phase*(phase*rb).
• canon_phase is a strict involution: std::int8_t set only to +/-1. So phase^2 == 1, and the store path returns rb unchanged while the cache retains the occurrence-independent phase*rb.
• Both roles are load-bearing for CSE: the cache is keyed canonically, so occurrences differing only by sign share one entry. The store-side apply_phase normalizes the value into the canonical (pre-phase) buffer phase*rb -- exactly the "cache holds pre-phase data" invariant used by the aliasing checks. The return-side apply_phase de-normalizes back to this occurrence's value rb; a later hit for a different occurrence applies its own node phase at the Enter path. Dropping either call corrupts signs (store-side -> caches an occurrence-specific signed buffer that poisons other occurrences; return-side -> hands the storing occurrence the wrong-sign canonical buffer).
• Reachable (interior contraction nodes can carry canon_phase == -1 and are exactly the cached/repeated ones) but correct -- which is why master produces correct antisymmetric CCSD/CCSDT energies. Behavior is byte-equivalent to master; this PR only translated the recursive mult_by_phase wrapper into finish_phase_b. No change needed.

[Krzmbrzl]

Did you also find a case where you run into stack overflows due to very deep trees? Did you also run into #418? with these expressions?

[evaleev]

Did you also find a case where you run into stack overflows due to very deep trees? Did you also run into #418? with these expressions?

yes, even conventional high-order CC (before @ABesharat's changes) could not be handled as a single tree, due to running out of stack space.

[Krzmbrzl]

Alright but from skimming through the changes #418 is unaffected by the changes here, right?

[evaleev]

It should fix #418 . One of the tests checks an expression w/ 200000 terms