Repository navigation
[ty] Avoid recursion when projecting narrowing constraints - #26276
Merged
Merged
Conversation
charliermarsh
added
the
bug
Typing conformance resultsNo changes detected ✅Current numbersThe percentage of diagnostics emitted that were expected errors held steady at 94.37%. The percentage of expected errors that received a diagnostic held steady at 89.00%. The number of fully passing files held steady at 94/134. |
Memory usage reportSummary
Significant changesClick to expand detailed breakdownprefect
trio
sphinx
flake8
|
|
charliermarsh
marked this pull request as ready for review
June 23, 2026 17:47
charliermarsh
force-pushed
the
charlie/unroll-narrowing-projection
branch
2 times, most recently
from
June 23, 2026 19:27
ca37784 to
21446d8
Compare
Member
|
Same here. I don’t think I’m the right reviewer for this |
Member
Author
|
Why? This is mechanically unrolling the recursive loop. There isn’t really any specific logic here? |
carljm
approved these changes
Jun 23, 2026
carljm
left a comment
carljm
left a comment
Contributor
There was a problem hiding this comment.
This looks good. Thank you! A regression test that would actually stack overflow on main would be a nice addition.
charliermarsh
force-pushed
the
charlie/unroll-narrowing-projection
branch
from
June 23, 2026 23:19
76c8a95 to
0f94c6a
Compare
charliermarsh
enabled auto-merge (squash)
June 23, 2026 23:23
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
3 participants
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
NarrowingProjector::projectrecursively walks the input narrowing decision diagram before producing the projected graph for one place. Deep constraint chains can therefore exhaust the native stack even when the projected graph is shallow.This replaces the recursive traversal with an explicit post-order worklist. A small inline action buffer avoids a heap allocation for common shallow projections. The actions preserve the existing visitation order and semantics: uncertain branches are projected before resolving non-terminal calls, ordinary predicates project all three branches before computing their narrowing constraints, and completed nodes continue to use the same cache.
The full ty semantic suite and workspace Clippy pass.