8000 Make joins symmetric and transitive? · Issue #3257 · python/mypy · GitHub
[go: up one dir, main page]
Skip to content

Make joins symmetric and transitive? #3257

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.

Sign up for GitHub

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

Jump to bottom
Closed
JukkaL opened this issue Apr 26, 2017 · 4 comments
Closed

Make joins symmetric and transitive? #3257

JukkaL opened this issue Apr 26, 2017 · 4 comments
Labels
needs discussion topic-protocols

Comments

@JukkaL
Copy link
Collaborator
JukkaL commented Apr 26, 2017

Joins don't have lattice properties with multiple inheritance. Here is an example of where things currently aren't right because joins aren't symmetric:

class A: pass
class B: pass

class C(A, B): pass
class D(B, A): pass

a = [C(), D()]  # List[A]
b = [D(), C()]  # List[B]

Similar examples can we found for transitivity, I believe -- changing the order of things in a list causes a different type to be inferred, which is at least somewhat bad, as it makes mypy feel unpredictable in some cases.

One option would be to only follow the first/leftmost base class in case of multiple inheritance, so the both results would be List[object]. We can tweak the example to work it consistently while producing useful types:

class A: pass
class B: pass

class C(A, B): pass
class D(A, B): pass

a = [C(), D()]  # would be List[A]
b = [D(), C()]  # would be List[A]

Though theoretically better, it has some issues:

  • This might be confusing for users as well. However, at least we could document the behavior pretty easily and it would be predictable.
  • We'd likely need to update typeshed to have base classes in a suitable order.
  • Existing code may require additional type annotations. It's unclear what the impact would be.

Alternatively, we could just not care about lattice properties. I think that joins only affect inferred types and they won't cause a runtime safety issue since we check types after inference. However, we should review all uses of joins in the implementation and try to understand what the implications would be.

Another fix would be to generate more union types from joins, but that would likely have a bigger effect. Now that union types aren't as buggy as they used to be, this might be at least worth some experimentation.

This issue also affects protocols (#3132), and there the situation is much more complicated.
@ilevkivskyi
Copy link
Member

Just an idea concerning unions and multiple inheritance. If I have two nominal types, then there are three options:

  • The two MROs are non-overlapping, then the join is object.
  • We find a class X that appears in both MROs, and it appears before any other class that also appear in both MROs - in this case X is the join.
  • We find some entangled MRO situation, like on the silly drawing below. 
    A - A1 - A2 - C - D - A5 - A6 - E - A8 - ...
               \ /              |           \
               / \              |            object
             /     \             \          /
  B - B1 - D - B3 - C - B5 - B6 - E - B8 -

What I propose for the last case is to return Union[C, D] as join(A, B). This is less restrictive than following the left-most class, while it is symmetric. Unfortunately, it looks like it is still not associative, for example the triple B3, B, A looks dangerous to me.

@ilevkivskyi ilevkivskyi mentioned this issue May 3, 2017
Open
@pkch
Copy link
Contributor
pkch commented May 3, 2017

Perhaps we could store the join as a Union until the last moment, and convert it to the common ancestor just before doing something that the user will see?

So for example, in @ilevkivskyi case, the join of B3, B, A is just a triple (B3, B, A) (basically a Union[B3, B, A] that only survives internally). Symmetry and associativity is preserved of course. But when doing any operations that will be visible to the user, this tuple is replaced by the nearest common ancestor in the inheritance hierarchy of all the items in the tuple, so E in this case.

@ilevkivskyi
Copy link
Member

Perhaps we could store the join as a Union until the last moment, and convert it to the common ancestor just before doing something that the user will see?

This idea was discussed in #3132 but it looks like this could get complicated pretty quickly.

@ilevkivskyi ilevkivskyi mentioned this issue Aug 15, 2017
Closed
@ilevkivskyi ilevkivskyi mentioned this issue Dec 15, 2017
Open
@ilevkivskyi ilevkivskyi mentioned this issue Jun 11, 2019
Closed
@JukkaL
Copy link
Collaborator Author
JukkaL commented Jan 29, 2020

Closing this since nobody has come up with a feasible semantics, and the current behavior seems to be quite acceptable in practice.

@JukkaL JukkaL closed this as completed Jan 29, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
needs discussion topic-protocols
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@JukkaL @pkch @ilevkivskyi
0