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

Support recursive types #731

Open
o11c opened this Issue Jul 30, 2015 · 31 comments

Comments

Projects
None yet
@o11c
Contributor

o11c commented Jul 30, 2015

The following in particular would be useful:

Callback = Callable[[str], 'Callback']
Foo = Union[str, List['Foo']]
@JukkaL

This comment has been minimized.

Collaborator

JukkaL commented Aug 4, 2015

If (or when) mypy will have structural subtyping, recursive types would also be useful there.

@JukkaL JukkaL added the postponed label Oct 13, 2015

@JukkaL

This comment has been minimized.

Collaborator

JukkaL commented Oct 13, 2015

My current plan is to postpone recursive types until simple structural subtyping is in and reconsider them later. After thinking about them more they are going to increase complexity a lot of I haven't seen much evidence for them being needed that often.

@oconnor663

This comment has been minimized.

oconnor663 commented Oct 16, 2015

If I'm understanding this issue right, I'm running into it for classes that want a fluent interface. So for example, if I want callers to do something like this:

myfoo.add(bar).add(baz).finish()

Then the definition of the Foo class and the add method need to look something like this:

class Foo:
    def add(self, x) -> Foo:  # Python chokes on this line!
        # do stuff
        return self

Another place where Python commonly does return self is in the __enter__ method for context managers. Is mypy able to typecheck those right now?

@kirbyfan64

This comment has been minimized.

Contributor

kirbyfan64 commented Oct 16, 2015

@oconnor663 Try:

class Foo:
    def add(self, x) -> 'Foo':
        # do stuff
        return self
@oconnor663

This comment has been minimized.

oconnor663 commented Oct 16, 2015

Ah, thank you.

@oconnor663

This comment has been minimized.

oconnor663 commented Oct 16, 2015

@kirbyfan64, do you know if there are standard functions anywhere that understand this convention? Like, if I wanted to introspect a couple functions and compare the types of their arguments, should I handle the Foo == "Foo" case explicitly? That seems doable, but a string-aware version of say isinstance seems harder.

@kirbyfan64

This comment has been minimized.

Contributor

kirbyfan64 commented Oct 16, 2015

@oconnor663 I don't think there's anything like that. If you're introspecting the functions via a decorator, you could try accessing the caller's globals and locals.

@gvanrossum

This comment has been minimized.

Member

gvanrossum commented Oct 16, 2015

You're aware of typing.get_type_hints(obj)right? It is similar to obj.annotations` but expands forward references.
https://docs.python.org/3/library/typing.html?highlight=typing#typing.get_type_hints

There used to be an instance() implementation in typing.py but Mark Shannon
made me take it out. It's being deleted in this rev:
python/typing@ac7494f

On Fri, Oct 16, 2015 at 9:37 AM, Ryan Gonzalez notifications@github.com
wrote:

@oconnor663 https://github.com/oconnor663 I don't think there's
anything like that. If you're introspecting the functions via a decorator,
you could try accessing the caller's globals and locals.


Reply to this email directly or view it on GitHub
#731 (comment).

--Guido van Rossum (python.org/~guido)

@oconnor663

This comment has been minimized.

oconnor663 commented Oct 16, 2015

@gvanrossum that's exactly what I was looking for, thanks. Sorry for the n00b questions today, but awesome that all this is supported.

@JukkaL

This comment has been minimized.

Collaborator

JukkaL commented Oct 17, 2015

Mypy should detect missing string literal escapes (see #948).

@dmoisset

This comment has been minimized.

Contributor

dmoisset commented Aug 18, 2016

Going back to the original point on the issue, I found a case in the stdlib where this would be needed; the type for isinstance() is currently:

def isinstance(o: object, t: Union[type, Tuple[type, ...]]) -> bool: ...

but it should actually be:

ClassInfo = Union[type, Tuple['ClassInfo', ...]]
def isinstance(o: object, t: ClassInfo) -> bool: ...

Because according to https://docs.python.org/3/library/functions.html#isinstance the tuples can be nested. I found an actual example of this while typechecking django.http.response.HttpResponse.content

@gvanrossum gvanrossum added this to the Future milestone Aug 18, 2016

cortesi added a commit to cortesi/mitmproxy that referenced this issue Mar 20, 2017

Make tnetstrings pass mypy
Mypy doesn't support recursive types yet, so we can't properly express
TSerializable nested structures. For now, we just disable type checking in the
appropriate locations.

python/mypy#731
@srittau

This comment has been minimized.

Contributor

srittau commented Mar 29, 2017

I have come across this while trying to define a generic JSON type:

JSON = Union[Dict[str, "JSON"], List["JSON"], str, int, float, bool, None]

So consider this a +1 for supporting this use case.

@gvanrossum gvanrossum removed this from the Future milestone Mar 29, 2017

@graingert

This comment has been minimized.

Contributor

graingert commented Jul 24, 2017

@srittau JSON needs to be Any because it is recursive and you can give json.loads a custom JSONEncoder class:

_PlainJSON = Union[Dict[str, "_PlainJSON"], List["_PlainJSON"], str, int, float, bool, None]
_T = TypeVar('_T')
JSON = Union[_PlainJSON, _T, Dict[str, "JSON"], List["JSON"]]
def loads(data: str, cls: Type[JSONEncoder[_T]]) -> JSON: ...

of course recursive types and Type[JSONEncoder[_T]] types arn't supported.

@DustinWehr

This comment has been minimized.

DustinWehr commented Jan 18, 2018

The following pattern seems to be good enough for my purposes. The boilerplate is tolerable for me.

class BTree(NamedTuple):
    val: int
    left_ : Any
    right_ : Any

    # typed constructor
    @staticmethod
    def c(val: int, left: Optional['BTree'] = None, right: Optional['BTree'] = None) -> 'BTree':
        return BTree(val, left, right)

    # typed accessors
    @property
    def left(self) -> Optional['BTree']:
        return cast(Optional[BTree], self.left_)
    @property
    def right(self) -> Optional['BTree']:
        return cast(Optional[BTree], self.right_)

atree = BTree.c(1, BTree.c(2, BTree.c(3), BTree.c(4)), BTree.c(5))
atree2 = BTree.c(1, BTree.c(2, BTree.c(3), BTree.c(4)), BTree.c(5))
assert atree == atree2
assert isinstance(atree,BTree) and isinstance(atree.left,BTree) and isinstance(atree.left.left,BTree)
@DustinWehr

This comment has been minimized.

DustinWehr commented Feb 14, 2018

Latest version of pattern. We use this example at Legalese for interacting with SMT solvers (the SMTLIB language).

I found that I ended up forgetting to use the typed .c static method instead of the untyped constructor in the BTree example above. This version addresses that. It's only very minor deficits are:

  1. Boilerplate (which I don't care about if the datatype is significant enough for us to care about the difference between an immutable recursive datatype and Tuple[Any,...])
  2. The constructor SMTExprNonatom and the type SMTExprNonatom_ do not share the same name. But this is only aesthetic; You won't use one when you mean the other, since with this naming convention, SMTExprNonatom will come up first in autocomplete, and only SMTExprNonatom_ can be used in a type position.
# Immutable recursive datatypes pattern
SMTAtom = Union[str, int, float, bool]
SMTExpr = Union['SMTExprNonatom_',SMTAtom]
class SMTExprNonatom_(NamedTuple):  
    symb: str
    args_: Tuple[Any,...] # see `args` below
    @staticmethod  # typed constructor, which we alias to `SMTExprNonatom` after the class def
    def c(symb:str, args:Iterable[SMTExpr]) -> 'SMTExprNonatom_': return SMTExprNonatom_(symb, tuple(args))
    @property # typed accessor
    def args(self) -> Tuple[SMTExpr]: return cast(Tuple[SMTExpr], self.args_)
SMTExprNonatom = SMTExprNonatom_.c
SMTCommand = NewType('SMTCommand', SMTExprNonatom_)

@JukkaL JukkaL changed the title from Support recursive types. to Support recursive types May 17, 2018

@JukkaL

This comment has been minimized.

Collaborator

JukkaL commented May 17, 2018

Updating to normal priority since this comes up frequently and the implementation got easier with some recent changes.

@DustinWehr

This comment has been minimized.

DustinWehr commented May 18, 2018

@JukkaL, anything I could do to help?

@JukkaL

This comment has been minimized.

Collaborator

JukkaL commented May 18, 2018

@DustinWehr We are not ready to start implementing this yet -- it's still a pretty complex feature, and we have other high-priority work scheduled for the near future. Finding additional real-world use cases where recursive types could be used would be helpful, though. JSON is the canonical use case, but beyond that we don't have many examples.

@Daenyth

This comment has been minimized.

Daenyth commented May 19, 2018

An example would be describing a typed AST, as those are usually recursive

@LiraNuna

This comment has been minimized.

LiraNuna commented May 19, 2018

We use a library called asynq and it has a recursive type for futures.

@DustinWehr

This comment has been minimized.

DustinWehr commented May 19, 2018

@DustinWehr

This comment has been minimized.

DustinWehr commented May 25, 2018

@JukkaL in case you are skeptical that people (besides the teams speaking up in this thread) are using python for typical FP use cases, a couple serious example projects of that type are:
http://microsoft.github.io/ivy/language.html
https://en.wikipedia.org/wiki/SageMath

@ilevkivskyi

This comment has been minimized.

Collaborator

ilevkivskyi commented Jun 11, 2018

Just a dump of a recent discussion with @JukkaL:

  • We will use µ-type representation of recursive types, i.e. TypeAlias node + TypeAliasInstance type.
  • We can support generic recursive aliases like A = Tuple[T, A[T]], and then A[int].
  • µ-type approach solves the serialization problem, i.e. the same cross_ref dance can be repeated only for TypeAlias vs TypeAliasInstance as for TypeInfo vs Instance.
  • Subtyping, meets, joins, etc. will be calculated essentially as for protocols with a single covariant member. We will have separate assumption stacks at the top of corresponding functions (to not mix with protocols).
  • Calling s = expand_once(s), t = expand_once(t) at the top of type-expecting functions will save many isinstance() checks for branches for different type kinds.
  • However, mypy has a lot of ad-hoc subtyping checks that needs to be updated in addition, we could use either an lgtm query or a simple mypy visitor to find all relevant isinstance() calls.
  • Refactoring that will introduce TypeAlias symbol node (for unrelated benefits) is underway, PR will be up shortly.
  • Realistic time for implementation is 2-3 weeks.
  • Potential target schedule (taking into account other tasks and priorities) is January-February 2019.
@deeplook

This comment has been minimized.

deeplook commented Sep 14, 2018

Just stumbled over this from the JSON example perspective... Is there any timeline/roadmap for recursive types already?

@graingert

This comment has been minimized.

Contributor

graingert commented Sep 14, 2018

Potential target schedule (taking into account other tasks and priorities) is January-February 2019.

@euresti

This comment has been minimized.

Contributor

euresti commented Sep 14, 2018

We have a workaround in our codebase:

JSON_PRIMITIVE = Union[None, bool, str, int, float]
if TYPE_CHECKING:
    # To avoid hitting an Any in mypy because of the recursive type we add a
    # couple of layers of non-recursive types.
    JSON_BASE = Union[  # type: ignore # Recursive type
        JSON_PRIMITIVE, Dict[str, "JSON_BASE"], List["JSON_BASE"]
    ]
    JSON2 = Union[  # type: ignore # Recursive type
        JSON_PRIMITIVE, Dict[str, JSON_BASE], List[JSON_BASE]
    ]
    JSON1 = Union[  # type: ignore # Recursive type
        JSON_PRIMITIVE, Dict[str, JSON2], List[JSON2]
    ]
    JSON = Union[  # type: ignore # Recursive type
        JSON_PRIMITIVE, Dict[str, JSON1], List[JSON1]
    ]
else:
   JSON = Union[JSON_PRIMITIVE, Dict[str, "JSON"], List["JSON"]]

This gives us a couple of layers of Dict and Lists before we get to Any. However we've learned that using JSON is exceedingly painful because of that Union You have to either isinstance very heavily or cast to get around issues. Dict[str, Any] is sadly the name of the game most of the time.

@Daenyth

This comment has been minimized.

Daenyth commented Sep 14, 2018

I ended up going with this in a previous project - you can construct a json parser given a typing.NamedTuple class that matches the json structure

https://gist.github.com/Daenyth/37d615e502114009d6a33652a814a7c8

@azag0

This comment has been minimized.

azag0 commented Sep 23, 2018

Speaking of workarounds for JSON, here is a pretty solid workaround using protocols. @ilevkivskyi, @JukkaL, do you see any potential gotchas beyond mimicking the required behavior of list and dict (which could be improved by including more functions)? Also, I'm not sure about performance.

from typing import Any, Dict, Union, Sequence, overload
from typing_extensions import Protocol


class _JSONArray(Protocol):
    def __getitem__(self, idx: int) -> 'JSONLike': ...
    # hack to enforce an actual list
    def sort(self) -> None: ...


class _JSONDict(Protocol):
    def __getitem__(self, key: str) -> 'JSONLike': ...
    # hack to enforce an actual dict
    @staticmethod
    @overload
    def fromkeys(seq: Sequence[Any]) -> Dict[Any, Any]: ...
    @staticmethod
    @overload
    def fromkeys(seq: Sequence[Any], value: Any) -> Dict[Any, Any]: ...


JSONLike = Union[str, int, float, bool, None, _JSONArray, _JSONDict]


obj: JSONLike = {"1": 1}  # ok
obj2: JSONLike = {1: 1}  # fail
obj3: JSONLike = [1, 2, {3: [5, 6]}]  # fail
obj4: JSONLike = {"s": [None]}  # ok
obj5: JSONLike = [[b'a']]  # fail
@azag0

This comment has been minimized.

azag0 commented Sep 23, 2018

Hm, ok, the limitation of this approach obviously being that it's "one-directional", one would still have to cast JSONArray/Dict to List/Dict when getting out of JSON.

@kojiromike

This comment has been minimized.

kojiromike commented Sep 30, 2018

@DustinWehr ...Finding additional real-world use cases where recursive types could be used would be helpful, though. JSON is the canonical use case, but beyond that we don't have many examples.

@JukkaL I suppose it's a pretty similar problem to that of JSON, but I've been trying to add type hints to apache/avro. Without recursive types I can't express the shape of avro schema completely.

Here is the work in progress. Variance is hard and mypy has found a lot of problems, so I expect to be working on this for a while.

@pstch

This comment has been minimized.

pstch commented Nov 13, 2018

About real-world use cases where recursive types could be useful, they are useful when writing programs that deal with explicitly recursive data structures (not just JSON), which encompasses a large class of programs. Such programs may be written and properly specified without recursive data types, but they can be needed to provide a complete type specification of some implementations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment