Add stubs for sortedcontainers

[jakob-keller]

Hello!

I am interested in adding stubs for sortedcontainers to typeshed. The maintainer, @grantjenks, supports this initiative.

Are there any concerns? Otherwise I would start drafting a PR.

[AlexWaygood]

Sounds like a great idea to me! sortedcontainers has been around for a while and has a good reputation as a high-quality library. PR welcome!

There's some instructions in CONTRIBUTING.md for adding new stubs, but let us know if anything's unclear :)

[DMRobertson]

Note that there is a PR to sortedcontainers with stubs: https://github.com/grantjenks/python-sortedcontainers/pull/107

We use these in Synapse and not had any problems with them. I did have to update the stubs to be compatible with a typeshed change though: matrix-org/synapse@e1993b4 (#12650)

[jakob-keller]

Note that there is a PR to sortedcontainers with stubs: grantjenks/python-sortedcontainers#107

Thanks for the heads up! I believe, I am already half-way through preparing a fresh stub package for typeshed, which is what the maintainer seams to prefer at this point. My focus lies on applying current typeshed best practices as much as possible. In my eyes, the existing PR looks a bit dated in that respect: use of Optional instead of | None, no use of Self...

This is somewhat new territory for me, so I fully expect a few rounds of reviews and changes, but I will cross-check with the existing PR to make sure I incorporate any lessons learned in my work before I push.

I am looking forward to getting any feedback once this is out.

[jakob-keller]

sortedcontainers.SortedSet.__init__() conditionally adds certain methods to instances. I am struggling to find proper type hints for that pattern.

I see several options to address this:

1. Omit these conditional methods, since they are not part of the 'core' class. This would satisfy the typeshed test suite. However, users would likely see false positive errors when using these methods.

2. Include these conditional methods, since their signature is known and they might be available for a given instance. The downside is potential for false negatives, i.e. users not been warned about using methods that are not actually available at runtime.

3. Finding creative ways to type both variants. What I came up with: start with 1. and add an additional _SortedKeySet stub that inherits from SortedSet and includes conditional methods. SortedSet.new() would be overloaded in a way to return the stub-only _SortedKeySet if conditional methods will be available at runtime. Downside is that the stubs would deviate substantially from the implementation, even adding an additional stub-only class.

4. Refactor sortedcontainers to resolve the conditional methods. This would be out-of-scope for me.

Could someone offer me guidance, please?

[AlexWaygood]

@jakob-keller, there's no ideal solution here, but the following hack works reasonably well, I think:

from collections.abc import Callable
from typing import overload

class SortedSet:
    @overload
    def __new__(cls, key: None = ...) -> SortedSet: ...
    @overload
    def __new__(cls, key: Callable[[], int]) -> _SortedSetWithExtraMethods: ...

class _SortedSetWithExtraMethods(SortedSet):
    def extra_method(self) -> None: ...

reveal_type(SortedSet())  # Revealed type is "SortedSet"
reveal_type(SortedSet(key=lambda: 5))  # Revealed type is "_SortedSetWithExtraMethods"

https://mypy-play.net/?mypy=latest&python=3.10&gist=0d151897cc1862ff8671a1acbfb2cbbc

The downside is we have to make up this fictional subclass _SortedSetWithExtraMethods. But I think it's the best we can do.

(I've no idea whether the types here are correct; I've only skimmed the source code in the last 5 minutes. This is just a proof of concept to give you some ideas :)

[jakob-keller]

@jakob-keller, there's no ideal solution here, but the following hack works reasonably well, I think:

from typing import Callable, overload

class SortedSet:
    @overload
    def __new__(cls, key: None = ...) -> SortedSet: ...
    @overload
    def __new__(cls, key: Callable[[], int]) -> _SortedSetWithExtraMethods: ...

class _SortedSetWithExtraMethods(SortedSet):
    def extra_method(self) -> None: ...

reveal_type(SortedSet())  # Revealed type is "SortedSet"
reveal_type(SortedSet(key=lambda: 5))  # Revealed type is "_SortedSetWithExtraMethods"

https://mypy-play.net/?mypy=latest&python=3.10&gist=0d151897cc1862ff8671a1acbfb2cbbc

The downside is we have to make up this fictional subclass _SortedSetWithExtraMethods. But I think it's the best we can do.

(I've no idea whether the types here are correct; I've only skimmed the source code in the last 5 minutes. This is just a proof of concept to give you some ideas :)

Perfect, that's what I had in mind as option 3. Just wasn't sure if that level of 'creativity' was permitted here :-D

[jakob-keller]

Alright, I finally got around to finishing a draft PR #8731.

From my point of view, there are a few peculiar details in the way sortedcontainers is implemented that does not quite lend itself to type hints. I tried to deal with it as best as I could.

Can't wait for your feedback!

[jakob-keller]

Sorry, I was unable to complete a PR since I migrated away from sortedcontainers in the meantime.

[vipierozan99]

Sorry, I was unable to complete a PR since I migrated away from sortedcontainers in the meantime.

What did you migrate to?

[jakob-keller]

Sorry, I was unable to complete a PR since I migrated away from sortedcontainers in the meantime.

What did you migrate to?

Basically, my use cases are now covered by a combination of regular lists and bisect.insort(), which supports the key argument since Python 3.10.

[Jeremiah-England]

For googlers, here is now a sortedcontainers-stubs package on PyPI: https://github.com/h4l/sortedcontainers-stubs