[GH-ISSUE #5931] [Bug] trace_call_path retains quadratic traversal state #3606

New issue

Closed

opened 2026-10-31 00:42:19 +00:00 by bsakaguchi · 1 comment

bsakaguchi commented

2026-10-31 00:42:19 +00:00

Owner

Originally created by @dakjdakd on GitHub (Oct 21, 2026).
Original GitHub issue: https://github.com/morluto/rea/issues/5931

Summary

trace_call_path retains a complete path array for every discovered address during breadth-first traversal. On a long linear graph, the retained traversal state grows quadratically even though the final result needs only the selected path and the discovered relationships.

Background

The operation explores provider-reported caller/callee relationships, deduplicates addresses, preserves breadth-first ordering, and optionally stops when it reaches a goal. The current state map stores both each node's depth and a copied path from the start node to that node.

Problem

Every newly discovered node copies its parent's path and appends one address. A traversal of n nodes therefore retains roughly 1 + 2 + ... + n path entries. Long or dense analyses spend most of their memory on duplicate prefixes, and the retained state can exceed the process heap even when the graph and final response are otherwise manageable.

Expected behavior

Traversal should retain only the information needed to reproduce the selected BFS path: each node's depth and its parent address. The path should be reconstructed once a goal is reached. No-goal traversal must keep its existing complete coverage and output ordering, while goal traversal must preserve the same shortest path semantics.

Scope

This issue concerns internal traversal-state representation. It does not add an arbitrary graph cap, change provider calls, alter cancellation behavior, or change the serialized result contract.

Originally created by @dakjdakd on GitHub (Oct 21, 2026). Original GitHub issue: https://github.com/morluto/rea/issues/5931 ## Summary `trace_call_path` retains a complete path array for every discovered address during breadth-first traversal. On a long linear graph, the retained traversal state grows quadratically even though the final result needs only the selected path and the discovered relationships. ## Background The operation explores provider-reported caller/callee relationships, deduplicates addresses, preserves breadth-first ordering, and optionally stops when it reaches a goal. The current state map stores both each node's depth and a copied path from the start node to that node. ## Problem Every newly discovered node copies its parent's path and appends one address. A traversal of `n` nodes therefore retains roughly `1 + 2 + ... + n` path entries. Long or dense analyses spend most of their memory on duplicate prefixes, and the retained state can exceed the process heap even when the graph and final response are otherwise manageable. ## Expected behavior Traversal should retain only the information needed to reproduce the selected BFS path: each node's depth and its parent address. The path should be reconstructed once a goal is reached. No-goal traversal must keep its existing complete coverage and output ordering, while goal traversal must preserve the same shortest path semantics. ## Scope This issue concerns internal traversal-state representation. It does not add an arbitrary graph cap, change provider calls, alter cancellation behavior, or change the serialized result contract.

bsakaguchi closed this issue

2026-10-31 00:42:19 +00:00

bsakaguchi commented

2026-10-31 00:42:20 +00:00

Author

Owner

@dakjdakd commented on GitHub (Oct 21, 2026):

The focused implementation is ready on dakjdakd/rea:fix/trace-call-path-memory at commit 66a755dce4. The corresponding draft PR body is prepared and will be submitted as soon as pull-request creation is available for this account.

@dakjdakd commented on GitHub (Oct 21, 2026): The focused implementation is ready on dakjdakd/rea:fix/trace-call-path-memory at commit 66a755dce45dc24228c3703a4935ff76220eedd5. The corresponding draft PR body is prepared and will be submitted as soon as pull-request creation is available for this account.

bsakaguchi referenced this issue

2026-10-31 01:09:55 +00:00

[PR #3606] [MERGED] fix(contracts): reject NUL bytes in keyed archive and extraction paths #5851

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

morluto/rea#3606

No description provided.

Rows
Columns