Add type annotations to sortedcontainers

[althonos]

trafficstars

Hi @grantjenks,

this PR adds type annotations to the sortedcontainers package. They should be consistent with their list, set and dict annotations from the typeshed annotations. All collections are invariant generics.

Here are the current quirks:

• __new__ annotations are not supported, so mypy does not understand that creating a SortedList with a key argument returns a SortedKeyList instance (this is a mypy bug, see python/mypy#3307)
• ~~SortedItemsView raises an error because of supposedly incompatible base classes (this is a mypy bug, see python/mypy#5973)~~ this has been fixed in mypy
• Until typing exposes Protocols, it is not really possible to set the return type of key functions. This means that the acceptable type for a key is Callable[[T], Any]. In particular, this also means that bisect_key_left and bisect_key_right accept Any. The other way around would be to make SortedList a generic over both T and K where K is the key type, but that would possibly be a hindrance to end users.
• SortedKeyList.__contains__(value) should accept anything (as any Sequence), but since the value is passed to self._key, the value should be of type T for the code never to fail. The choices are: either only accept T, typecheck the value in the code, or return False on any TypeError raised by the key. None of them are really satisfactory IMO.
• SortedDict.setdefault has the same signature than dict.setdefault from the standard library, although in theory the signature should have an overload if not default is given.

[althonos]

Well, I'm not a typing master myself, but basically, you'll need a typechecker set-up, for instance mypy or pyre (I tested with both of these).

Then you can run the typechecker first of all on the codebase itself (e.g. mypy -p sortedcontainers), and it should not raise any error (except the ones listed above that are to be fixed by the mypy team).

AFAIK, there's no way to test the typing is good (that's like testing a program is without bugs), but maybe you could try to have test cases with erroneous typing to see it is detected (such as appending an int to a SortedList[str]) although I'm not sure how to do it.

[althonos]

@bryanforbes: thanks for your review ! I'll add the required changes soon.

[bryanforbes]

Thanks for doing this, @althonos. You beat me to it :).

[althonos]

@bryanforbes : thanks for reviewing my code ! I let so much slip through it's mostly thanks to you this PR became high-standard enough :wink:

[bryanforbes]

@grantjenks This is ready to merge

[bryanforbes]

Great questions, @grantjenks, and I didn't find them as challenges. Hopefully my answers were helpful and not condescending.

[grantjenks]

I looked around a bit and searched typing.py but could not find the typing hints for OrderedDict and the like. Are there pyi files for the built-in types? How do I compare what’s here with the standard library?

[althonos]

@grantjenks: they can be found in the python/typeshed repository: for instance, dict annotations can be found here, and OrderedDict annotations here

[oremanj]

Any updates on this? I'm using sortedcontainers in a typed project and it would be great to have the type hints available.

[grantjenks]

I'm making progress on reviewing the changes but it's a large addition and a new kind of feature for me.

[viveshok]

thanks to everyone involved with this work (starting with sortedcontainers itself), very appreciated

[pisiiki]

I would love to see this merged too. Great work.

[grantjenks]

I apologize for the delay. I have recently learned more about mypy and type annotations. I may be able to get something rolled out by the end of the month. Until then, I'm open to the type annotations being added to typeshed: https://github.com/python/typeshed

[grantjenks]

Sorry for the great delay in this pull request. I'm keeping it in my Inbox now and looking for time to review the changes and merge.

[nathanielobrown]

Just tried using this and got the following error:

In [1]: from sortedcontainers import SortedList                                                        

In [2]: s: SortedList[int] = SortedList()                                                              
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-7fb24f1c5eef> in <module>
----> 1 s: SortedList[int] = SortedList()

TypeError: 'ABCMeta' object is not subscriptable

Installed with pip install git+git://github.com/althonos/python-sortedcontainers.git@master.

Am I doing something wrong or is this an issue?

[althonos]

@nathanielobrown : kinda expected, since we are only adding stub files, and not changing anything in the code, including the ABCMeta inheritance.

It probably works with

s: "SortedList[int]" = SortedList() 

[althonos]

Added suggestions from @SimonBin , and rebased against latest master. Sorry for the delay.

[samestep]

Any update on this? Is review by @grantjenks the bottleneck, or is there still work left to be done which an external contributor could help with?

[grantjenks]

I think I’m the blocker. Still haven’t had time to learn enough about type annotations. Using them in other projects has had mixed results.

Two open questions for me:

1. I’d like to cythonize sorted containers. Is Cython able to understand pyi files? What’s the integration story there?
2. With generics like “list[int]” that are available in more recent versions, can those be used here too? Or is it subject to the same compatibility issues Python typically has?

[samestep]

I don't know the answer to 1, but for 2, anecdotally: in PyTorch we're still using the old List[int] style because we need to support Python 3.6.

[antonagestam]

@grantjenks Perhaps mypyc could be a plausible alternative? https://github.com/mypyc/mypyc

Also: take your time. Open source burnout is real, and it's your free time.

[samestep]

Also: take your time. Open source burnout is real, and it's your free time.

Ditto on this; please don't take my earlier comments as a demand, just curious about the state of things

[althonos]

Please don't feel any pressure from my side, I know reviewing large PRs takes time and dedication. Now trying to answer the questions:

I’d like to cythonize sorted containers. Is Cython able to understand pyi files? What’s the integration story there?

Basically your .pyi files are going to be independent from your Cython sources, and Cython cannot generate them (yet?). So you need to maintain the signatures yourself. However the .pyi are often more accurate: you can't really describe an Optional[int] directly in the Cython signatures, it's either int or object. I have a Cython project with type stubs here: althonos/pyrodigal.

With generics like “list[int]” that are available in more recent versions, can those be used here too? Or is it subject to the same compatibility issues Python typically has?

Indeed as @samestep mentioned, for Python 3.6 compatibility you should still use List[int], though it's reaching end-of-life in six months. But nothing stops you from keeping the code compatible with Python 3.6 but making the stubs Python 3.7+ I think.

[samestep]

But nothing stops you from keeping the code compatible with Python 3.6 but making the stubs Python 3.7+ I think.

@althonos I don't believe this is true; quoting PEP 484:

Annotations must be valid expressions that evaluate without raising exceptions at the time the function is defined (but see below for forward references).

As another example, if I remember correctly, typing something as SortedList[str] from this library raises a runtime error while just SortedList is fine (as is 'SortedList[str]' I believe, although I don't know think that works with mypy). So if you want to support Python 3.6, I don't believe the new list[int] syntax can be used.

(I'm not at my computer right now, but once I am, I'll double-check this and edit my comment accordingly.)

[althonos]

@samestep : You have activated my trap card! To your PEP 484 I raise you PEP 585!

Joke aside, from Python 3.9 onward, x: SortedList[str] = SortedList() totally works in the Python code because SortedList inherits from MutableSequence, which is now a typing variant, so the metaclass allows indexing at the type level. In previous versions, it's not the case (because the metaclass is still type).

To fix that in the Python code of sortedcontainers consumer there are two choices: either put quotes everywhere (works with Python 3.6+), use the future for PEP 563: from __future__ import annotations to disable evaluation of annotations.

From the perspective of mypy, whatever the version, everything works.

EDIT:

Oh and about the section you quote, it's only relevant for the annotations within Python sources. That PEP explicitly states the following afterwards:

Stub files are files containing type hints that are only for use by the type checker, not at runtime.

So the version of your stub only matters for version of mypy that gets invoked on the stubs.

[samestep]

Oh and about the section you quote, it's only relevant for the annotations within Python sources. That PEP explicitly states the following afterwards:

Stub files are files containing type hints that are only for use by the type checker, not at runtime.

So the version of your stub only matters for version of mypy that gets invoked on the stubs.

Ah, you are correct; I was very confused when reading the first part of your comment because I tried this in Python 3.6 just now and it didn't work:

>>> l: list[int] = [1, 2, 3]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'type' object is not subscriptable
>>> from __future__ import annotations
  File "<stdin>", line 1
SyntaxError: future feature annotations is not defined

But I had forgotten that this PR only adds the type annotations in .pyi files, so from what you've said, it sounds like it should work fine with Python 3.6 even if those stubs use post-3.6 typing features?

[dpinol]

Hi, any chance to advance on this?

[grantjenks]

Sorry, no. It still hasn't made it to the top of my list. If those interested want to publish a sortedcontainers-types package with the pyi files, then I'm okay with that.

[ml31415]

Guys, this PR is soon reaching its fifth birthday ... that should have been enough time for a review. Just get it merged!

[grantjenks]

@ml31415 Sorry, no. It still hasn't made it to the top of my list. If those interested want to publish a sortedcontainers-types package with the pyi files, then I'm okay with that.