Support recursive types

[o11c]

The following in particular would be useful:

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

[JukkaL]

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

[JukkaL]

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]

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?

[refi64]

@oconnor663 Try:

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

[oconnor663]

Ah, thank you.

[oconnor663]

@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.

[refi64]

@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]

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: https://github.com/ambv/typehinting/commit/ac7494fa900f76c7b3342bb6e0389e1543de0071

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 https://github.com/JukkaL/mypy/issues/731#issuecomment-148763562.

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

[oconnor663]

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

[JukkaL]

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

[dmoisset]

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

[srittau]

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.

[graingert]

@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]

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]

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]

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

[DustinWehr]

@JukkaL, anything I could do to help?

[JukkaL]

@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]

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

[LiraNuna]

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

[DustinWehr]

Any real-world use case for typical strongly-typed FP languages would be a real-world use case, since you can do algebraic datatypes with recursive types, NamedTuple, and Union.

On Sat, May 19, 2018 at 11:30 AM, Liran Nuna notifications@github.com wrote:

We use a library called asynq https://github.com/quora/asynq/tree/master/asynq and it has a recursive type for futures.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/python/mypy/issues/731#issuecomment-390423917, or mute the thread https://github.com/notifications/unsubscribe-auth/ABjF7mfPjT4NNau4NpAEmY_6F86tCc_gks5t0GTJgaJpZM4FizHE .

[DustinWehr]

@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]

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]

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

[graingert]

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

[euresti]

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]

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

[jhrmnn]

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

[jhrmnn]

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]

@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]

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.

[harrislapiroff]

Another real world use case. I'm writing a function for a CMS which builds a page tree from a value like this:

[
    (
        Page(title='Page 1'),
        [
            (Page(title='Page 2'), ...),
            (Page(title='Page 2'), ...),
        ]
    ),
]

where ... are nested iterables of the same structure, representing the child pages. The type would be something like

PageTree = Iterable[Tuple[Page, 'PageTree']]

[SKHecht]

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

I'm not sure if there is any update on the timeline for this, but if it won't be soon, would it be possible to add a config option to suppress the 'Recursive types not fully supported yet, nested types replaced with "Any"' error message?

I'm okay with my project having Anys for now, and it'd be nice to be able to write the recursive types now and not need to go back and replace them once recursive types are implemented.

[ilevkivskyi]

I'm not sure if there is any update on the timeline for this

I think we are still on time (most likely late February).

[tedkornish]

Is there a place to watch or contribute to progress on this?

[graingert]

@tedkornish https://github.com/python/mypy/issues/6204 and any other commits into newsemnal

[graingert]

@tedkornish https://github.com/python/mypy/commits/master/mypy/newsemanal

[graingert]

@JukkaL it looks like newsemnal landed, did it include support for recursive types?

[JukkaL]

It looks like we'll need to wait a bit more until we add recursive type support. I can't give a new estimate yet.

[sanderr]

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.

A work-around proposal that does not require casting to List/Dict:

from typing import Optional, Union, Iterable, Mapping, List, Dict

Primitive = Union[str, int, bool]
JsonType = Optional[Union[Primitive, "JsonList", "JsonDict"]]

class JsonList(list):
    """
        List type containing MyType elements.
    """
    def __init__(self, iterable: Iterable[JsonType]) -> None:
        super().__init__(iterable)

class JsonDict(dict):
    """
        Dict type with str keys and JsonType values.
    """
    def __init__(self, mapping: Optional[Mapping[str, JsonType]] = None, **kwargs: JsonType) -> None:
        if mapping is None:
            super().__init__(**kwargs)
        else:
            super().__init__(mapping, **kwargs)

lst: JsonList = JsonList([
    1,
    JsonList([
        2,
        JsonList([
            3,
            JsonList([
                4,
                JsonList([
                    5,
                    JsonDict(
                        recursion=True
                    ),
                    True,
                    None
                ])
            ])
        ])
    ])
])
dct: Dict[str, JsonType] = JsonDict(
    name="myName",
    lst=lst,
    integer=12,
    none=None
)

dct_lst: JsonType = dct.get("lst")
dct_integer: JsonType = dct["integer"]
generic_list: List[JsonType] = lst
lst_item: JsonType = lst[0]
generic_list_item: JsonType = generic_list[0]

Of course, the Primitive type should be expanded to include all desired primitives.

[catb0t]

@sanderr your code is very useful, i've modified it into a strict version that doesn't use Any and passes the strictest configuration https://gist.github.com/catb0t/bd82f7815b7e95b5dd3c3ad294f3cbbf

[sanderr]

@catb0t I opted for the generic list and dict types over List[JsonType] and Dict[str, JsonType] because one of my vim plugins complained: no-member: Instance of 'JsonDict' has no 'get' member and similar. I assumed this complaint came from mypy, but it appears to be something else, so it seems like your modification is indeed better. Two observations:

• if you inherit from the specific list and dict types as you do, I believe it is not even necessary to override __init__.
• if you do decide to override __init__, be aware that I wrote above more as a proof of concept than as a stable drop-in replacement for list and dict types. I believe the dict constructor in particular is a bit more complex than what I wrote, so it might be worth looking into that. For example, the code snippet below shows a valid construction of a dict, that isn't typed correctly by my implementation:

  dict([("key", "value"), ("other_key", "other_value")])
  JsonDict([("key", "value"), ("other_key", "other_value")])

[mitar]

@ilevkivskyi Does this also work now with the new analyzer?

[JelleZijlstra]

Not yet, @ilevkivskyi is actually currently working on adding support for recursive types. He will know the exact schedule better but it looks like mypy will support recursive types in the fairly near future.

[ir4y]

Are there any updates @ilevkivskyi ? Is there any help needed?

[ilevkivskyi]

@ir4y There are only sad updates: I am no longer working on this, and likely will not work on this in foreseeable future. You can try pushing it yourself, but it is not an easy task, and I can't guide you, sorry (others may still have time for this).

[ir4y]

@ilevkivskyi

it is not an easy task

Sure it is. Otherwise, it will be already done.

I will try to add support for recursive types.

I can't guide you

It is sad.

Could you at least provide some details that may be helpful? What is a good start point for this task? Do you have any WIP pull-request? What common issues I'll face?

[anentropic]

There are a couple of other type-checkers for Python out there...

Facebook released pyre-check. I don't know if it supports recursive types because I get cryptic parse errors when trying to run it on my project.

Google's pytype seems to handle recursive types ok, I can run it on my project with the # type: ignore comments removed from the recursive types and it's all fine. Less anecdotally, I think one of the devs commented here that it is supported: https://lobste.rs/s/0uv5hy/how_quickly_find_type_issues_your_python#c_df7acb

...maybe something can be learned from the pytype codebase to bring this feature into mypy?

[ir4y]

@anentropic There is also pyrigth by Microsoft.

[JukkaL]

Here's a very short summary of recursive types could be implemented (on top of the foundation that @ilevkivskyi has already implemented).

A simple self-recursive type would use TypeAlias that has a TypeAliasType that contains the recursive reference. TypeAliasType instances can be expanded an arbitrary number of times (the expansion for recursive types is infinite, so we'd only expand as much as is needed). The tricky bit is that type operations such as subtype checks would need to limit recursion when there are type alias types, similar to how we deal with recursive protocols right now. (see _assuming etc. in TypeState and how it's used).

When I have more time I can write a more detailed description and/or provide links to external resources.

To start with, I'd recommend trying to support some basic operations for a simple recursive type such as X = Union[int, List['X'].

We can disable support for recursive types initially while the implementation is incomplete, and provide a command-line option to enable them. This way the feature can be implemented incrementally, and PRs can be merged to master even if things are not quite ready. Even if whoever starts to work on this can't finish the implementation, somebody else can later continue the work, without impacting mypy users.