Skip to content

[red-knot] avoid divergent iteration due to unbounded union growth #17465

@carljm

Description

@carljm

In this code sample (provided by @skshetry in #17457 (comment)), we enter divergent fixpoint iteration and end up panicking with "too many iterations":

class Klass:
    def __init__(self) -> None:
        self.attr = 1

    def copy(self, other: "Klass"):
        self.attr = other.attr or self.attr

The issue is that we infer a type of Unknown & ~AlwaysFalsy, which we then union with itself on each subsequent iteration, but we fail to simplify this union, so it just grows on each iteration.

There should be multiple parts to the fix here. One is that we should be able to simplify (Unknown & ~AlwaysFalsy) | (Unknown & ~AlwaysFalsy) to just Unknown & ~AlwaysFalsy.

The other is that we should have a reliable backstop, since our union and intersection simplification will never be perfect. If any union or intersection grows over a certain size limit, we need to just best-effort reduce it to the nearest enclosing "join" type, or just object.

Metadata

Metadata

Assignees

Labels

tyMulti-file analysis & type inference

Type

No type

Projects

No projects

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions