Avoid stack overflows in resolver error reporting#19684
Closed
charliermarsh wants to merge 8 commits into
Closed
Conversation
Member
Author
|
I'm going to look at avoiding recursion altogether too. |
adb03ae to
46bb603
Compare
charliermarsh
added a commit
that referenced
this pull request
Jun 7, 2026
## Summary Prior to this change, resolving an unsatisfiable dependency graph with many candidate versions could overflow the process stack while constructing, reducing, formatting, or dropping the resolver error. This PR is an alternative to #19684. That PR retains the recursive derivation-tree algorithms and uses `stacker::maybe_grow` before recursive descent, while making ownership-sensitive destruction and selected traversals iterative. This PR instead removes recursion from every derivation-tree path: transformations and reductions use explicit post-order work stacks. (The tradeoff is a larger implementation with more explicit traversal state, but we avoid the `stacker` dependency, which also doesn't seem to work on all of our supported platforms.) Closes #19672.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Prior to this change, resolving an unsatisfiable dependency graph with many candidate versions could overflow the process stack while constructing and displaying the resolver error.
This PR makes derivation-tree error handling stack-safe by growing the stack during recursive transformations, hint generation, debugging, and report formatting. Tree traversal and destruction use iterative implementations where possible (avoiding another overflow when large intermediate trees are inspected or dropped).
Since PubGrub's recursive reporting entry point is private, we mirror its reporter for now while preserving its output and shared-node references.
Closes #19672.