[ty] Fall back to ambiguous for large control flow graphs#23399
Merged
charliermarsh merged 4 commits intomainfrom Feb 19, 2026
Merged
[ty] Fall back to ambiguous for large control flow graphs#23399charliermarsh merged 4 commits intomainfrom
charliermarsh merged 4 commits intomainfrom
Conversation
Typing conformance resultsNo changes detected ✅ |
|
Memory usage reportMemory usage unchanged ✅ |
charliermarsh
requested review from
AlexWaygood,
carljm,
dcreager,
ibraheemdev and
sharkdp
as code owners
|
| Lint rule | Added | Removed | Changed |
|---|---|---|---|
invalid-await |
40 | 0 | 0 |
invalid-argument-type |
0 | 1 | 0 |
invalid-return-type |
1 | 0 | 0 |
| Total | 41 | 1 | 0 |
sharkdp
approved these changes
Feb 19, 2026
Comment on lines
+594
to
+596
| if self.interiors.len() >= MAX_INTERIOR_NODES { | ||
| return AMBIGUOUS; | ||
| } |
Contributor
There was a problem hiding this comment.
Why are these placed before, and not after the cache lookup?
Comment on lines
319
to
320
| /// (e.g., a 5000-line while loop with hundreds of if-branches). This is sound: we lose | ||
| /// precision about what's definitely reachable/unreachable but never report incorrect results. |
Contributor
There was a problem hiding this comment.
Well, that depends on how we interpret "incorrect results". Losing precision in the reachability and narrowing constraint BDD can lead to all sorts of incorrect results, both false positives and false negatives. I would probably write something like
Suggested change
| /// (e.g., a 5000-line while loop with hundreds of if-branches). This is sound: we lose | |
| /// precision about what's definitely reachable/unreachable but never report incorrect results. | |
| /// (e.g., a 5000-line while loop with hundreds of if-branches). This can lead to less precise | |
| /// reachability analysis and type narrowing. |
| /// operations return `AMBIGUOUS` to prevent exponential blowup on pathological inputs | ||
| /// (e.g., a 5000-line while loop with hundreds of if-branches). This is sound: we lose | ||
| /// precision about what's definitely reachable/unreachable but never report incorrect results. | ||
| const MAX_INTERIOR_NODES: usize = 512 * 1024; |
Contributor
There was a problem hiding this comment.
I have no feeling for the magnitude of this number. I understand that it solves the Tauon problem, but I don't know how many other real world projects this might affect. Can we maybe push a test branch where we panic! if we exceed the threshold and see how many ecosystem projects fail (if any)?
Ideally, I think we would calibrate that number by e.g. decreasing the threshold until we hit panics, and then make it 10x or 100x larger to be "far away enough" from affecting any real projects (apart from Tauon, I guess).
I also tried to generate a test case for this feature, but my first attempt resulted in a relatively large input (which gives me some confidence that this threshold is high enough). I should probably add loops, because they seem to make the problem much worse.
Member
Author
There was a problem hiding this comment.
So it looks like 64 * 1024 leads to a panic in setuptools, but 128 * 1024 has no panic. I'll stick with 512 * 1024 for now as a reasonable increase atop that, though obviously somewhat arbitrary...
charliermarsh
force-pushed
the
charlie/ambiguous
branch
from
108580a to
f7729e1
Compare
Member
Author
My understanding is that it increased the number of nodes by about 50% (i.e., we were already creating around 2M nodes), though I don't fully understand why the runtime exploded at that threshold. |
knutwannheden
pushed a commit
to openrewrite/ruff
that referenced
this pull request
Feb 20, 2026
…23399) ## Summary This [giant loop](https://github.com/Taiko2k/Tauon/blob/08bfd249f404817e58078a2cbce7a69d3f949f0c/src/tauon/t_modules/t_main.py#L44882-L49772) is causing us to create (per Claude) over 3 million nodes in the TDD graph. We now cap the analysis, which causes us to fall back to "ambiguous" -- so we can still detect most diagnostics, but lose some capabilities. Closes astral-sh/ty#2846.
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
4 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
This giant loop is causing us to create (per Claude) over 3 million nodes in the TDD graph. We now cap the analysis, which causes us to fall back to "ambiguous" -- so we can still detect most diagnostics, but lose some capabilities.
Closes astral-sh/ty#2846.