speedup typechecking of nested if expressions #12700
Conversation
This comment has been minimized.
This comment has been minimized.
mypy/checkexpr.py
Outdated
| @@ -3910,6 +3916,15 @@ def visit_conditional_expr(self, e: ConditionalExpr, allow_none_return: bool = F | |||
| if_type = self.analyze_cond_branch(if_map, e.if_expr, context=else_type, | |||
| allow_none_return=allow_none_return) | |||
|
|
|||
| elif if_type == ctx or (if_lit is not None and (if_lit == ctx or if_lit == ctx_lit)): | |||
There was a problem hiding this comment.
if_type == ctx seems clearly fine, but I'm not sure I 100% understand the second half of the check.
I agree that join will turn literals back into fallbacks, but it's not obvious to me that the only effect of using the fallback type as context would be to turn a returned literal type into its fallback.
I'm also worried / optimistic that a change along the lines of #12395 might breaking assumptions here / make this change unnecessary
There was a problem hiding this comment.
Honestly, I don't quite understand why this second call to analyze_cond_branch is here at all... It can't think of a case where it is relevant to us the type of the result of the if branch to infer the type of the result of the else branch. But then again I don't fully understand the semantics of the "type context"...
From what I understand though, it seems silly to pass a literal type as type context to analyze_cond_branch and it would probably make more sense to always pass the fallback type instead, which would simplify things back to a simple if_type == ctx (after generalizing if_type and ctx to their respective fallback types if either is a literal).
Maybe someone with a deeper understanding of this logic can chime in? @JukkaL maybe ?
There was a problem hiding this comment.
Updated with a new approach that feels more theoretically sound and more robust to any change similar to #12395
This comment has been minimized.
This comment has been minimized.
huguesb
force-pushed
the
pr-fix-slow-nested-if-literal
branch
from
84d38f5
to
1f0741b
Compare
This comment has been minimized.
This comment has been minimized.
Deeply nested if/else expressions have a worst-case exponential behavior. This will for instance manifest when returning literal values which cause repeated analysis of conditional branches with subtly different type context for each literal. This can be optimized by observing that a simple literal context will yield the same analysis as its fallback type, and likewise, two literals of the same fallback type will yield the same analysis. In those case we can avoid the repeated analysis and prevent the worst-case exponential behavior. Fixes python#9591
huguesb
force-pushed
the
pr-fix-slow-nested-if-literal
branch
from
1f0741b
to
2c0209e
Compare
|
According to mypy_primer, this change has no effect on the checked open source code. 🤖🎉 |
Deeply nested if/else expressions have a worst-case exponential behavior. This will for instance manifest when returning literal values which cause repeated analysis of conditional branches with subtly different type context for each literal. This can be optimized by observing that a simple literal context will yield the same analysis as its fallback type, and likewise, two literals of the same fallback type will yield the same analysis. In those case we can avoid the repeated analysis and prevent the worst-case exponential behavior. Fixes #9591
Deeply nested if/else expressions have a worst-case exponential behavior.
This will for instance manifest when returning literal values which cause
repeated analysis of conditional branches with subtly different type context
for each literal.
This can be optimized by observing that a simple literal context will yield
the same analysis as its fallback type, and likewise, two literals of the
same fallback type will yield the same analysis. In those case we can avoid
the repeated analysis and prevent the worst-case exponential behavior.
Fixes #9591