Consider (one day) adding an inheritance order class precedence mechanism
Sometimes I get MRO failures when defining classes. For example, if R < E, C B < S, E S < C Z < B, R Then Z cannot be instantiated because C precedes E in B and E precedes C in R. The problem is that when the inheritance graph was topologically-sorted in B, the order was S, C, E. It could just as easily have been S, E, C. So, one solution is to add C explicitly to B's base class list, but this is annoying because B might not care about C (it's an implementation detail of S). It also means that if the hierarchy changes, a lot of these added extra base classes need to be fixed. I propose adding a magic member to classes: __precedes__ that is a list of classes. So, the fix for the above problem would be to define E as follows: class E: from whatever import C __precedes__ = [C] Then, when topologically-sorting (so-called linearizing) the ancestor classes, Python can try to ensure that E precedes C when defining B. Best, Neil
On Wed, Nov 15, 2017 at 11:49 PM, Neil Girdhar <mistersheik@gmail.com> wrote:
So it sounds like you are talking about the way that the siblings in the inheritance tree (the bases of each class) get "flattened" into the mro in a depth-first manner, and the relative order of siblings is not preserved. What would you think about not topologically sorting the inheritance tree as such, but sorting a graph that has additional edges according to the base lists of each class involved? In this case those edges would be E->C, S->E, B->R. Is this what your talking about, or do I misinterpret the problem? -- Koos -- + Koos Zevenhoven + http://twitter.com/k7hoven +
On Wednesday, November 15, 2017 at 5:32:00 PM UTC-5, Koos Zevenhoven wrote:
It is preserved, but there are insufficient constraints, which causes problems with future class definitions.
That's already part of the topological sorting algorithm. You have to do that. I'm suggesting additional constraints.
On Thu, Nov 16, 2017 at 5:28 AM, Neil Girdhar <mistersheik@gmail.com> wrote:
I'm talking about the initial graph to be sorted. Not some intermediate graph that may be used for describing steps in an algorithm. Anyway, the contraint given by the edge E->C is not yet part of the algorithm, because if it was already there, you wouldn't need "__precedes__" to add that edge. But another thing that affects this is whether we consider multiple occurrences of a class in the inheritance tree as the same node in the inheritance graph or not. If yes, then the inheritance tree and the inheritance graph are two different things. ––Koos -- + Koos Zevenhoven + http://twitter.com/k7hoven +
On Wed, Nov 15, 2017 at 01:49:03PM -0800, Neil Girdhar wrote:
These are not equivalent: B < S, E B < E, S so your comment that it could "just have easily" been S, E, C is not generally true. Calling C.method(self) E.method(self) in that order is not, in general, the same as calling them in the opposite order.
As the author of E, why would I do that? I don't even know that B exists, and even if I did know about B, by adding __precedes__ I risk breaking classes X, Y and Z which expect C to precede E.
Then, when topologically-sorting (so-called linearizing) the ancestor classes, Python can try to ensure that E precedes C when defining B.
How? You're glossing over the most important detail: *how* should Python produce a consistant, monotonic, bug-free linearization of the superclasses given an arbitrary number of (possibly conflicting) __precedes__ constraints? If __precedes__ is a hard constraint, then you have to deal with inconsistent constraints *as well as* inconsistent inheritence orders. If __precedes__ is just a suggestion, rather than a hard constraint, then you have to deal with the cases where the actual MRO ignores the suggestion, leading to contradiction between what the source says and what the code actually does. In either case, we know have an even more complicated set of inheritence rules, with even more things that can go wrong. Getting the MRO for multiple inheritence right is hard enough already. Python's current MRO algorithm is the third, the first two were broken: http://python-history.blogspot.com.au/2010/06/method-resolution-order.html https://www.python.org/download/releases/2.3/mro/ Letting people mess with the MRO will surely lead to subtle and hard to diagnose bugs. The harsh truth is that sometimes you just do not have a consistent MRO for a certain set of superclasses. Python refuses to let you use such an inconsistent MRO, not because it is trying to be annoying, but because such inconsistent MROs are broken. If you know of an alternative MRO that gives correct results for the class hierarchy you give above, please share. -- Steve
Steven D'Aprano wrote:
Not in general, but in many cases they will be, e.g. if E and S have no method names in common. I think the OP is implying that his case is one of those. Maybe what's really wanted is a way to say "B inherits from S and E, but it doesn't care what order they go in". Then the MRO generating algorithm could in principle swap them if it would result in a consistent MRO. Or maybe the MRO generator could decide for itself if the order of two base classes can be swapped by inspecting their attributes to see if any of them clash? -- Greg
Ethan Furman wrote:
If they don't have any clashing attributes, why does order matter?
It doesn't -- that's the point. Currently it's assumed that the order base classes appear in a class statement is the order that they must appear in the MRO. But that's not always true. I'm suggesting that the MRO algorithm should not assume that and should make its own assessment of the required ordering. -- Greg
It doesn't -- that's the point. Currently it's assumed that the order base classes appear in a class statement is the order that they must appear in the MRO. It’s not assumed — it’s how order is specified by the coder... But that's not always true. Isn’t it true by definition? I'm suggesting that the MRO algorithm should not assume that and should make its own assessment of the required ordering. Isn’t that impossible? It could determine that order doesn’t matter (no name clashes), but when that’s the case, there’s nothing to do. What am I missing? -CHB -- Greg _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
On Thu, Nov 16, 2017 at 07:10:15PM +1300, Greg Ewing wrote:
Explicit is better than implicit :-) If Neil meant his suggestion to only apply in the case where S and E have no methods in common, he should have said so. Given the possibility of __getattr__ or more exotic things like metaclass trickery, we might not even be able to tell what methods are possible. We'd need either some philosophy like "if you use this feature, you're responsible for ensuring it works" (an excellent way to guarantee hard-to-diagnose bugs in people's code *wink* ) or a more complex set of requirements: - none of the classes involved have a non-standard metaclass; - none of them override __getattribute__ or __getattr__ - none of them have any methods in common then, and only then, can Python attempt to reorder the MRO to suit. Did I miss any necessary conditions? But that seems like its adding a lot of complexity for little benefit. Its not even clear whether this is practical -- why would the author of class E specify __precedes__ to suit a class that they don't even know exists? What if two classes both want E to specify the order in opposite directions? If I am the author of both E and B, then why don't I just reorder E's superclasses directly, instead of using __precedes__? There's a lot of benefit to having a relatively simple, understandable algorithm for determining the MRO, as opposed to some sort of adaptive rule that will try to reorder classes according to potentially clashing constraints. If that means that some classes cannot go together in multiple inheritence because their MRO would be inconsistent, I think that's a price worth paying for not having to debug inheritence bugs caused by weirdly reordered MROs. -- Steve
On 17 November 2017 at 15:52, Steven D'Aprano <steve@pearwood.info> wrote:
I'll note that an interesting side effect of https://www.python.org/dev/peps/pep-0560/#mro-entries will be to allow folks to write: class MyCustomMRO: def __init__(self, *bases): self._resolved_bases = my_mro_resolver(bases) def __mro_entries(self, orig_bases): if len(orig_bases) > 1 or orig_bases[0] is not self: raise TypeError("CustomMRO instance must be sole base class") return self._resolved_bases class Z(MyCustomMRO(B, R)): ... The custom MRO algorithm may then allow for use case specific hints to handle situations that the default C3 resolver will reject as inconsistent or ambiguous. (I'll also note that such a custom resolver would be able to manufacture and inject synthetic metaclasses if that's what someone decided they really wanted to do, by also synthesising a custom base class to stick at the head of the list of bases). Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Fri, Nov 17, 2017 at 10:14 AM, Nick Coghlan <ncoghlan@gmail.com> wrote:
I can imagine someone wanting that, but it still doesn't allow customizing the *whole* MRO, AFAICT. Regarding the inheritance trees of B and R that is. Or at least trying to somehow achieve that without introducing a metaclass would probably become a terrible hack (if not just impossible). ––Koos -- + Koos Zevenhoven + http://twitter.com/k7hoven +
On 18 November 2017 at 09:03, Neil Girdhar <mistersheik@gmail.com> wrote:
Unfortunately, as Koos noted, it doesn't actually work as simply as I presented it: even if you spell out a full MRO in the most-derived class, the C3 resolution algorithm will complain that it's inconsistent with the order in one of the two conflicting base classes. So to truly get a custom method resolution order, you're likely going to end up needing a custom metaclass involved. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 19 November 2017 at 06:56, Neil Girdhar <mistersheik@gmail.com> wrote:
I don't actually know what C3 allows in principle, I only know that CPython's resolver still complains in practice: >>> class C: pass ... >>> class S(C): pass ... >>> class E: pass ... >>> class B(S, E): pass ... >>> class R(E, C): pass ... >>> class Z(B, S, R, E, C): pass ... Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: Cannot create a consistent method resolution order (MRO) for bases C, E I think the problem is that the resolver isn't looking at the declared bases of "B", and "R", it's looking at their full MRO: >>> B.__mro__ (<class '__main__.B'>, <class '__main__.S'>, <class '__main__.C'>, <class '__main__.E'>, <class 'object'>) >>> R.__mro__ (<class '__main__.R'>, <class '__main__.E'>, <class '__main__.C'>, <class 'object'>) Changing the heuristics used to generate B's MRO such that "C" and "E" appeared in the opposite order wouldn't really help, since that would just flip the problematic case to be the "R(C, E)" declaration. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 21 November 2017 at 11:09, Neil Girdhar <mistersheik@gmail.com> wrote:
Right, but once you do that, then the existing resolver is already able to handle things: >>> class C: pass ... >>> class S(C): pass ... >>> class E: pass ... >>> class B(S, E, C): pass ... >>> class R(E, C): pass ... >>> class Z(B, R): pass ... >>> If you wanted to pick up cases where two classes generate inconsistent MROs that will prevent mutual subclasses (like "class B(S, E)" vs "class R(E, C)"), that feels like a job for a type checker, since it isn't obvious whether it's the definition of B or the definition of R that should be changed to reorder their MRO. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 21 November 2017 at 12:34, Nick Coghlan <ncoghlan@gmail.com> wrote:
I do wonder if we might be able to make the error message here less cryptic by mentioning which *listed* base classes brought in the conflicting MRO entries. Consider the current: >>> class Z(B, R): pass ... Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: Cannot create a consistent method resolution order (MRO) for bases C, E vs something like: TypeError: Cannot create a consistent method resolution order (MRO) for bases C, E (inherited through B, R) (Note: I haven't actually checked how practical it would be to implement something like that) Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Mon, Nov 20, 2017 at 9:41 PM Nick Coghlan <ncoghlan@gmail.com> wrote:
I totally agree. I actually proposed this on ideas a few months ago and then wrote something here: https://github.com/NeilGirdhar/inheritance_graph If you have any suggestions or improvements, please feel free to improve the code. Best, Neil
On Mon, Nov 20, 2017 at 9:34 PM Nick Coghlan <ncoghlan@gmail.com> wrote:
Sure, but like I mentioned, that's really ugly because B doesn't care about C and shouldn't have to mention it as a base class. This solution can quickly spiral out of control so that changes in the inheritance graph require you to hunt down extraneous base classes.
yes, exactly.
I don't know what the "type checker" means here. I figured that the easiest user specification would be precedence relationships between classes that could be applied (in the way I described). And I figured that that could be processed for given classes when their MRO is generated. The proposal of having a custom MRO generator would also be able to solve this problem.
On Thu, Nov 16, 2017 at 1:11 AM Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
Interesting idea, but unfortunately, reordering base classes doesn't solve all of the problems that a precedence specification does. For example, the original example was: R < E, C B < S, E S < C Z < B, R If we make it slightly more complicated: class Y: pass class X(Y): pass class E(X): pass class C: pass class R(E, C): pass class S(C, Y): pass class B(S, E): pass class Z(B, R): pass Then, S and E can't be swapped.
In general, I think that this would be a cool project, but is much hard than the user declaring a consistent order.
On Wed, Nov 15, 2017 at 11:49 PM, Neil Girdhar <mistersheik@gmail.com> wrote:
So it sounds like you are talking about the way that the siblings in the inheritance tree (the bases of each class) get "flattened" into the mro in a depth-first manner, and the relative order of siblings is not preserved. What would you think about not topologically sorting the inheritance tree as such, but sorting a graph that has additional edges according to the base lists of each class involved? In this case those edges would be E->C, S->E, B->R. Is this what your talking about, or do I misinterpret the problem? -- Koos -- + Koos Zevenhoven + http://twitter.com/k7hoven +
On Wednesday, November 15, 2017 at 5:32:00 PM UTC-5, Koos Zevenhoven wrote:
It is preserved, but there are insufficient constraints, which causes problems with future class definitions.
That's already part of the topological sorting algorithm. You have to do that. I'm suggesting additional constraints.
On Thu, Nov 16, 2017 at 5:28 AM, Neil Girdhar <mistersheik@gmail.com> wrote:
I'm talking about the initial graph to be sorted. Not some intermediate graph that may be used for describing steps in an algorithm. Anyway, the contraint given by the edge E->C is not yet part of the algorithm, because if it was already there, you wouldn't need "__precedes__" to add that edge. But another thing that affects this is whether we consider multiple occurrences of a class in the inheritance tree as the same node in the inheritance graph or not. If yes, then the inheritance tree and the inheritance graph are two different things. ––Koos -- + Koos Zevenhoven + http://twitter.com/k7hoven +
On Wed, Nov 15, 2017 at 01:49:03PM -0800, Neil Girdhar wrote:
These are not equivalent: B < S, E B < E, S so your comment that it could "just have easily" been S, E, C is not generally true. Calling C.method(self) E.method(self) in that order is not, in general, the same as calling them in the opposite order.
As the author of E, why would I do that? I don't even know that B exists, and even if I did know about B, by adding __precedes__ I risk breaking classes X, Y and Z which expect C to precede E.
Then, when topologically-sorting (so-called linearizing) the ancestor classes, Python can try to ensure that E precedes C when defining B.
How? You're glossing over the most important detail: *how* should Python produce a consistant, monotonic, bug-free linearization of the superclasses given an arbitrary number of (possibly conflicting) __precedes__ constraints? If __precedes__ is a hard constraint, then you have to deal with inconsistent constraints *as well as* inconsistent inheritence orders. If __precedes__ is just a suggestion, rather than a hard constraint, then you have to deal with the cases where the actual MRO ignores the suggestion, leading to contradiction between what the source says and what the code actually does. In either case, we know have an even more complicated set of inheritence rules, with even more things that can go wrong. Getting the MRO for multiple inheritence right is hard enough already. Python's current MRO algorithm is the third, the first two were broken: http://python-history.blogspot.com.au/2010/06/method-resolution-order.html https://www.python.org/download/releases/2.3/mro/ Letting people mess with the MRO will surely lead to subtle and hard to diagnose bugs. The harsh truth is that sometimes you just do not have a consistent MRO for a certain set of superclasses. Python refuses to let you use such an inconsistent MRO, not because it is trying to be annoying, but because such inconsistent MROs are broken. If you know of an alternative MRO that gives correct results for the class hierarchy you give above, please share. -- Steve
Steven D'Aprano wrote:
Not in general, but in many cases they will be, e.g. if E and S have no method names in common. I think the OP is implying that his case is one of those. Maybe what's really wanted is a way to say "B inherits from S and E, but it doesn't care what order they go in". Then the MRO generating algorithm could in principle swap them if it would result in a consistent MRO. Or maybe the MRO generator could decide for itself if the order of two base classes can be swapped by inspecting their attributes to see if any of them clash? -- Greg
Ethan Furman wrote:
If they don't have any clashing attributes, why does order matter?
It doesn't -- that's the point. Currently it's assumed that the order base classes appear in a class statement is the order that they must appear in the MRO. But that's not always true. I'm suggesting that the MRO algorithm should not assume that and should make its own assessment of the required ordering. -- Greg
It doesn't -- that's the point. Currently it's assumed that the order base classes appear in a class statement is the order that they must appear in the MRO. It’s not assumed — it’s how order is specified by the coder... But that's not always true. Isn’t it true by definition? I'm suggesting that the MRO algorithm should not assume that and should make its own assessment of the required ordering. Isn’t that impossible? It could determine that order doesn’t matter (no name clashes), but when that’s the case, there’s nothing to do. What am I missing? -CHB -- Greg _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
On Thu, Nov 16, 2017 at 07:10:15PM +1300, Greg Ewing wrote:
Explicit is better than implicit :-) If Neil meant his suggestion to only apply in the case where S and E have no methods in common, he should have said so. Given the possibility of __getattr__ or more exotic things like metaclass trickery, we might not even be able to tell what methods are possible. We'd need either some philosophy like "if you use this feature, you're responsible for ensuring it works" (an excellent way to guarantee hard-to-diagnose bugs in people's code *wink* ) or a more complex set of requirements: - none of the classes involved have a non-standard metaclass; - none of them override __getattribute__ or __getattr__ - none of them have any methods in common then, and only then, can Python attempt to reorder the MRO to suit. Did I miss any necessary conditions? But that seems like its adding a lot of complexity for little benefit. Its not even clear whether this is practical -- why would the author of class E specify __precedes__ to suit a class that they don't even know exists? What if two classes both want E to specify the order in opposite directions? If I am the author of both E and B, then why don't I just reorder E's superclasses directly, instead of using __precedes__? There's a lot of benefit to having a relatively simple, understandable algorithm for determining the MRO, as opposed to some sort of adaptive rule that will try to reorder classes according to potentially clashing constraints. If that means that some classes cannot go together in multiple inheritence because their MRO would be inconsistent, I think that's a price worth paying for not having to debug inheritence bugs caused by weirdly reordered MROs. -- Steve
On 17 November 2017 at 15:52, Steven D'Aprano <steve@pearwood.info> wrote:
I'll note that an interesting side effect of https://www.python.org/dev/peps/pep-0560/#mro-entries will be to allow folks to write: class MyCustomMRO: def __init__(self, *bases): self._resolved_bases = my_mro_resolver(bases) def __mro_entries(self, orig_bases): if len(orig_bases) > 1 or orig_bases[0] is not self: raise TypeError("CustomMRO instance must be sole base class") return self._resolved_bases class Z(MyCustomMRO(B, R)): ... The custom MRO algorithm may then allow for use case specific hints to handle situations that the default C3 resolver will reject as inconsistent or ambiguous. (I'll also note that such a custom resolver would be able to manufacture and inject synthetic metaclasses if that's what someone decided they really wanted to do, by also synthesising a custom base class to stick at the head of the list of bases). Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Fri, Nov 17, 2017 at 10:14 AM, Nick Coghlan <ncoghlan@gmail.com> wrote:
I can imagine someone wanting that, but it still doesn't allow customizing the *whole* MRO, AFAICT. Regarding the inheritance trees of B and R that is. Or at least trying to somehow achieve that without introducing a metaclass would probably become a terrible hack (if not just impossible). ––Koos -- + Koos Zevenhoven + http://twitter.com/k7hoven +
On 18 November 2017 at 09:03, Neil Girdhar <mistersheik@gmail.com> wrote:
Unfortunately, as Koos noted, it doesn't actually work as simply as I presented it: even if you spell out a full MRO in the most-derived class, the C3 resolution algorithm will complain that it's inconsistent with the order in one of the two conflicting base classes. So to truly get a custom method resolution order, you're likely going to end up needing a custom metaclass involved. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 19 November 2017 at 06:56, Neil Girdhar <mistersheik@gmail.com> wrote:
I don't actually know what C3 allows in principle, I only know that CPython's resolver still complains in practice: >>> class C: pass ... >>> class S(C): pass ... >>> class E: pass ... >>> class B(S, E): pass ... >>> class R(E, C): pass ... >>> class Z(B, S, R, E, C): pass ... Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: Cannot create a consistent method resolution order (MRO) for bases C, E I think the problem is that the resolver isn't looking at the declared bases of "B", and "R", it's looking at their full MRO: >>> B.__mro__ (<class '__main__.B'>, <class '__main__.S'>, <class '__main__.C'>, <class '__main__.E'>, <class 'object'>) >>> R.__mro__ (<class '__main__.R'>, <class '__main__.E'>, <class '__main__.C'>, <class 'object'>) Changing the heuristics used to generate B's MRO such that "C" and "E" appeared in the opposite order wouldn't really help, since that would just flip the problematic case to be the "R(C, E)" declaration. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 21 November 2017 at 11:09, Neil Girdhar <mistersheik@gmail.com> wrote:
Right, but once you do that, then the existing resolver is already able to handle things: >>> class C: pass ... >>> class S(C): pass ... >>> class E: pass ... >>> class B(S, E, C): pass ... >>> class R(E, C): pass ... >>> class Z(B, R): pass ... >>> If you wanted to pick up cases where two classes generate inconsistent MROs that will prevent mutual subclasses (like "class B(S, E)" vs "class R(E, C)"), that feels like a job for a type checker, since it isn't obvious whether it's the definition of B or the definition of R that should be changed to reorder their MRO. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 21 November 2017 at 12:34, Nick Coghlan <ncoghlan@gmail.com> wrote:
I do wonder if we might be able to make the error message here less cryptic by mentioning which *listed* base classes brought in the conflicting MRO entries. Consider the current: >>> class Z(B, R): pass ... Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: Cannot create a consistent method resolution order (MRO) for bases C, E vs something like: TypeError: Cannot create a consistent method resolution order (MRO) for bases C, E (inherited through B, R) (Note: I haven't actually checked how practical it would be to implement something like that) Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Mon, Nov 20, 2017 at 9:41 PM Nick Coghlan <ncoghlan@gmail.com> wrote:
I totally agree. I actually proposed this on ideas a few months ago and then wrote something here: https://github.com/NeilGirdhar/inheritance_graph If you have any suggestions or improvements, please feel free to improve the code. Best, Neil
On Mon, Nov 20, 2017 at 9:34 PM Nick Coghlan <ncoghlan@gmail.com> wrote:
Sure, but like I mentioned, that's really ugly because B doesn't care about C and shouldn't have to mention it as a base class. This solution can quickly spiral out of control so that changes in the inheritance graph require you to hunt down extraneous base classes.
yes, exactly.
I don't know what the "type checker" means here. I figured that the easiest user specification would be precedence relationships between classes that could be applied (in the way I described). And I figured that that could be processed for given classes when their MRO is generated. The proposal of having a custom MRO generator would also be able to solve this problem.
On Thu, Nov 16, 2017 at 1:11 AM Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
Interesting idea, but unfortunately, reordering base classes doesn't solve all of the problems that a precedence specification does. For example, the original example was: R < E, C B < S, E S < C Z < B, R If we make it slightly more complicated: class Y: pass class X(Y): pass class E(X): pass class C: pass class R(E, C): pass class S(C, Y): pass class B(S, E): pass class Z(B, R): pass Then, S and E can't be swapped.
In general, I think that this would be a cool project, but is much hard than the user declaring a consistent order.
participants (7)
-
Chris Barker - NOAA Federal -
Ethan Furman -
Greg Ewing -
Koos Zevenhoven -
Neil Girdhar -
Nick Coghlan -
Steven D'Aprano