Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add mypy type hints? #68

Open
Daenyth opened this issue May 5, 2017 · 18 comments
Open

Add mypy type hints? #68

Daenyth opened this issue May 5, 2017 · 18 comments

Comments

@Daenyth
Copy link

Daenyth commented May 5, 2017

This would help people who'd like to use sortedcontainers in a project with mypy type checking.

https://github.com/python/mypy/wiki/Creating-Stubs-For-Python-Modules

@grantjenks
Copy link
Owner

I am open to it. Pull request welcome.

@Daenyth
Copy link
Author

Daenyth commented May 5, 2017

Fair enough. If I can get some time to devote to it I'll see what I can do.

@solomon-b
Copy link

If this is still desired, I would like to take this issue on.

@solomon-b
Copy link

I wrote a stubfile for SortedList and SortedListWithKeys. I've never written a type hints for someone else's project so I'm hoping to get some feedback before I continue with the remaining classes.

https://github.com/ssbothwell/sorted_containers/blob/master/sortedcontainers/sortedlist.pyi

Thanks!

@Daenyth
Copy link
Author

Daenyth commented Oct 5, 2017

Off the bat I think it's probably wrong to use the Orderable type that you've made there. As far as I know, it works for any type defining inequality protocols.

The class should probably extend Generic[_A] where _A = TypeVar('_A'). Unfortunately as far as I'm aware there's no way to restrict it to be orderable types, but the alternative is to say Iterable[Any] and throw out element safety.

@solomon-b
Copy link

Thanks for the feedback. The Orderable type alias seemed questionable to me but I went with it as an initial draft.

I'm assuming that in this type of situation the type hints are meant mainly for IDE support rather then static analysis. Given that, maybe Iterable[Any] is not a big problem. I could also alias Iterable[Any] to Orderable as a hint for developers that the method is actually taking an orderable object while still not breaking static analysis.

What do you think?

@solomon-b
Copy link

solomon-b commented Oct 5, 2017

PEP484 has a solution using a Type Variable with an upper bound. Any type replacing the type variable must implement the __lt__ method.

This ensures only types with inequality are passed but not that they all can be compared to each other. It sounds like this is the best solution we are going to get for the time being. I updated my stub file to include this.

On another note, mypy throws some "incompatible with supertype" errors for methods in SortedListWithKey that overload those in SortedList. An example is key() which returns None in SortedList and returns the key function in SortedListWithKey. I think this is violating the covariance rule for return types.

I also get an error about MutableSequence (which SortedList inherits from) not being defined. Do I need to import the base class into the stubfile?

@grantjenks
Copy link
Owner

Sorry for the silence on this issue. I don't remember getting email updates.

I've been working on V2 which will adopt Python 3 semantics for some APIs while still being backwards-compatible with Python 2. I'm afraid I've changed some of the parameter names which will require updating in your pyi file.

I'm also not sure how to test your pyi file.

@bryanforbes
Copy link

If you're still open to this, I can work up a PR

@grantjenks
Copy link
Owner

I'm open to it.

Still prefer pyi over source changes. And I'm not sure how to test it.

It'll be a learning experience for me.

@Daenyth
Copy link
Author

Daenyth commented Sep 14, 2018

I'm not actively doing python at the moment but do feel free to ping me with any questions, I'd be happy to help you work through any issues you come across.

@Madoshakalaka
Copy link

@grantjenks Oh, I just saw this thread after I submitted #136 . What do you think of the pull request?

@nacitar
Copy link

nacitar commented Aug 22, 2021

I'd just like to express my interest in this feature. Has there been any more progress with the pull request?

@grantjenks
Copy link
Owner

I think the realistic timeline for me understanding type hints and merging these is still months away. Given that it's already been years, I'd suggest contributing them to the typeshed at https://github.com/python/typeshed/blob/master/CONTRIBUTING.md Is there anyone willing to pursue maintaining type hints there?

@grantjenks grantjenks changed the title Add mypy type stubs? Add mypy type hints? Aug 20, 2022
@grantjenks grantjenks removed the V3 label Aug 20, 2022
@SimpleArt
Copy link

SimpleArt commented Mar 11, 2023

Worth noting that the main problem with adding type hints to this is the dynamic structure of all the key= cases, which seems to have been the main cause for others to fail to add type hints which behave correctly.

The biggest problem here is the complicated methods involved in SortedSet.__init__, where different methods are added depending on the type.

It probably is possible to hack together some sort of solution together, but this is really not ideal. Doing so makes it harder for those using type hints to figure out what the expected type is trying to say, which arguably defeats much of the purpose.

Likewise, the use of __new__ to instantiate different classes is going to cause confusion with x: SortedKeyList = SortedList(...).

There are ways to redesign this package in such a way that adding type hints is more sensible.

  • Make SortedKeySet to alleviate the problems with SortedSet.
  • Use separate constructor functions entirely, such as sorted_list(iterable, key).

For the second point, the idea is that one would add the following:

# If key is None, which it is by default, then return a SortedList.
@overload
def sorted_list(
    iterable: Optional[Iterable[T]] = ..., key: None = ...
) -> SortedList[T]: ...

# Otherwise key should be a function accepting values and returning keys.
# If provided, the iterable should match the necessary values.
# This case returns a sorted key list with the appropriate key and value types.
@overload
def sorted_list(
    iterable: Optional[Iterable[VT]] = ..., key: Callable[[VT], KT]
) -> SortedKeyList[KT, VT]: ...

# The type hints above would be added to typeshed,
# while the below implementation would be added here.
def sorted_list(iterable=None, key=None):
    if key is None:
        return SortedList(iterable)
    else:
        return SortedKeyList(iterable, key)

These constructor functions can be added without removing the current approach with __init__ and __new__, which could become deprecated and slowly removed or simply fail to support accurate typing in some cases if users choose to use the old constructors instead of the new ones.

@Jeremiah-England
Copy link

For those looking for something to use today, see these: https://github.com/h4l/sortedcontainers-stubs

They work very well for me!

@jgarvin
Copy link

jgarvin commented Sep 11, 2024

I ended up writing my own SortedSet and in the process came up with a workaround for the key type. The idea is to keep the type of the key function out of the sorted set type itself (so you have SortedSet[T], not SortedSet[T, KeyType] and assert in the default key function that the type is actually Comparable. This has the downside that if you use the constructor that doesn't take a key function and it's not comparable you don't find out until runtime the first time you add an element to the container, but the other aspects of type safety are preserved (you can only put T and take T out of the container). It would be possible to do better with overloads but there is a mypy bug python/mypy#17614.

from typing import Protocol, Self, runtime_checkable, Generic, Callable

@runtime_checkable
class Comparable(Protocol):
    def __lt__(self, other: Self) -> bool: ...
    def __eq__(self, other: Any) -> bool: ...

T = TypeVar('T') # notice there is no Comparable bound!

class SortedSet(Generic[T]):
    def __init__(self, elements: Iterable[T] = [], key: Callable[[T], Comparable] | None = None) -> None:
        self.data: list[T] = []
        self._key: Callable[[T], Comparable]
        if key is None:
            def check_comparable(x: T) -> Comparable:
                assert isinstance(x, Comparable)
                return x
            self._key = check_comparable
        else:
            self._key = key
        self.update(elements)

@vtgn
Copy link

vtgn commented Nov 24, 2024

Hi!

What's new?! Still no typing from 2017?!... :/

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

10 participants