Long if-elif chain causes Ty to take 9+ minutes on 61 lines of code

[Nikratio]

Summary

The following file is unfeasible to check with Ty 0.0.80 (I aborted after 9+ minutes). With Ty 0.0.17, it still finished sub-second.

I assume there is something pathologic about this code, and I wouldn't necessarily expect Ty to typecheck it more quickly, but I would much rather have it skip the file with a warning (or abort with an error) than hanging.

The reproducer code does not do anything useful, but the pattern (and problem) was discovered in a production codebase. I think it is triggered by migration code of the form:

try:
    from new_location.colors import *
except ImportError:
    class Color(enum.Enum):
        ...  # identical fallback definition

Reproducer

import enum
import random


class _ColorA(enum.Enum):
    RED = 1
    ORANGE = 2
    YELLOW = 3
    GREEN = 4
    BLUE = 5
    INDIGO = 6
    VIOLET = 7
    BLACK = 8
    WHITE = 9
    GRAY = 10


class _ColorB(enum.Enum):
    RED = 1
    ORANGE = 2
    YELLOW = 3
    GREEN = 4
    BLUE = 5
    INDIGO = 6
    VIOLET = 7
    BLACK = 8
    WHITE = 9
    GRAY = 10


Color = _ColorA if random.random() < 0.5 else _ColorB


def describe(item):
    if isinstance(item, str):
        return item

    if item == Color.RED:
        name = "red"
    elif item == Color.ORANGE:
        name = "orange"
    elif item == Color.YELLOW:
        name = "yellow"
    elif item == Color.GREEN:
        name = "green"
    elif item == Color.BLUE:
        name = "blue"
    elif item == Color.INDIGO:
        name = "indigo"
    elif item == Color.VIOLET:
        name = "violet"
    elif item == Color.BLACK:
        name = "black"
    elif item == Color.WHITE:
        name = "white"
    elif item == Color.GRAY:
        name = "gray"
    else:
        raise ValueError(item)

    return name

Scaling

Changing the number of elif branches in the code, I found:

branches	check time
6	0.19 s
7	1.12 s
8	9.25 s
9	86.5 s
10	> 300 s

Workarounds

Each of the following changesbrings check time back below a second:

• Delete the isinstance(item, str) guard and its return
• Replace the union with a single class (Color = _ColorA)
• Replace the elif chain with a dict lookup (name = names[item])

Version

I've checked it with:

 uvx ty -V
ty 0.0.80

> time uvx ty check reproducer.py 
Checking --------- 0/1 files^C
________________________________________________________
Executed in    6.53 secs    fish           external
   usr time    6.25 secs    0.00 millis    6.25 secs
   sys time    0.27 secs    1.53 millis    0.27 secs

With an older version, it's much faster:

> ty --version
ty 0.0.17

> ty check reproducer.py
All checks passed!

________________________________________________________
Executed in   31.25 millis    fish           external
   usr time   21.37 millis    0.17 millis   21.20 millis
   sys time   14.08 millis    1.03 millis   13.06 millis

[sharkdp]

Thank you for reporting this.

After the isinstance check, the type of item is Unknown & ~str. Then, since Color is a union of _ColorA and _ColorB, we infer an exponentially growing union of types for item in narrowing:

  (Unknown & ~str & ~Literal[_ColorA.RED])
| (Unknown & ~str & ~Literal[_ColorB.RED])

  (Unknown & ~str & ~Literal[_ColorA.RED] & ~Literal[_ColorA.ORANGE])
| (Unknown & ~str & ~Literal[_ColorA.RED] & ~Literal[_ColorB.ORANGE])
| (Unknown & ~str & ~Literal[_ColorB.RED] & ~Literal[_ColorA.ORANGE])
| (Unknown & ~str & ~Literal[_ColorB.RED] & ~Literal[_ColorB.ORANGE])

[sharkdp]

Not sure if that's helpful, since it's quite old, but it bisects to astral-sh/ruff#25788 (Improve equality-based narrowing for ==, !=, and match)