Title: Innocuous parent class changes multiple inheritance MRO
Type: behavior Stage: resolved
Components: Interpreter Core Versions: Python 3.8
Status: closed Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: cykerway, mark.dickinson, steven.daprano
Priority: normal Keywords:

Created on 2019-12-28 02:21 by cykerway, last changed 2020-01-21 17:18 by corona10. This issue is now closed.

File name Uploaded Description Edit cykerway, 2019-12-28 02:21 MRO test file.
Messages (8)
msg358921 - (view) Author: Cyker Way (cykerway) * Date: 2019-12-28 02:21
With an inheritance graph like this:

        A       C
        B       D      (X)      A

Adding or removing class X in E's parents will change the order of A and C in E's MRO: EBDAC vs EBDCXA.

I couldn't imagine what would be the "perfect" MRO. However, given X is completely independent from A and C, this behavior looks strange and problematic.
msg358926 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2019-12-28 02:56
Have you read the description of how the MRO is calculated? It's a standard algorithm. So long as the result matches the C3 linearisation algorithm, then it's not a bug.

I've gone back to Python 2.4 and tested the MRO. With and without class X, the MRO is:

    E B D C X A object
    E B D A C object

so the result seems to be consistent back to 2.4 if not older. So it's not a change in behaviour in 3.8. It also matches the result of my own implementation of the C3 algorithm that I wrote some time ago to check my understanding of it.

So it looks to me that this is the correct behaviour, going back to 2.3, so I'm closing it as "Not a bug". If you disagree, and can find a bug in Python's C3 linearisation algorithm, please feel free to reopen. If you disagree with the choice of the C3 algorithm, and want to suggest some other algorithm, you'll need to write a PEP setting forth the pros and cons of both, explaining why the alternative is better than the status quo.
msg358929 - (view) Author: Cyker Way (cykerway) * Date: 2019-12-28 05:53
Thanks for reply. It's not about the Python's implementation of C3 but C3 itself being used as the MRO algorithm in Python. It bites when you remove an independent interface from your class definition and its method calls become something else.

I think I can propose an easy fix to C3. I would just call it C3.9 if it's going to be merged in Python 3.9. The difference between C3.9 and C3 is: During a merge, put the list of the parents in front of the linearizations of the parents, namely:

Instead of: L[C(B1 ... BN)] = C + merge(L[B1], ..., L[BN], B1 ... BN)

We do: L[C(B1 ... BN)] = C + merge(B1 ... BN, L[B1], ... , L[BN])

This preserves the guarantees of C3 (for example, local precedence ordering, monotonicity), plus another property: When you remove a leaf node in the dependency graph, the MRO of other nodes remain the same. Practically, this means when a developer removes an independent interface from his class, he knows the MRO of the remaining classes keep the same. Here the independent interface can even have its own class hierarchy, and the proof goes by removing each leaf one by one in its hierarchy.

For example, using the same

EB + [DA A DC A]
EBD + [A A C A]
EBDA + [C]

EBD + [XA A C X A]
EBDX + [A A C A]

You can see EBDAC is a sub-sequence of EBDXAC.

The proof is intuitive. I can give a sketch here. Assume without loss of generality, class E extends A, B, C, D, and we add a new base class X between B and C, now we have:

(f1) E + [ABXCD L(A) L(B) X L(C) L(D)]

Compare this with:

(f0) E + [ABCD L(A) L(B) L(C) L(D)]

We can carry all the computation in f1 just as in f0 until X becomes the head of the first list item:

(f1') E... + [XCD ... X ... ]

(f0') E... + [CD ... ... ]

At this time we know we can extract X in (f1') because X is in any tail. After we extract X, (f1') becomes (f0') and we can carry all the operations just as in (f0'). So the result of (f1) is merely an added X and all other elements keep the same order. Intuitively, the performance of C3.9 should be almost the same as C3. The only drawback I can think of is existing code may have a different MRO, but that happened when Python adopted C3.

Not sure if this is worth a PEP. If anyone is interested feel free to leave a message.
msg358930 - (view) Author: Cyker Way (cykerway) * Date: 2019-12-28 05:57
a typo: this time we know we can extract X in (f1') because X is NOT in any tail...

Missed the "NOT" in the previous text.
msg358931 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2019-12-28 06:46
Whether this proposed change is worth a PEP is a value judgement, but 
whether it will need a PEP is, I think, a fact. It is a backwards 
incompatible change (it will change the inheritance order of classes) 
potentially breaking people's code. Its not a small change, so it will 
(almost certainly) need a PEP.

The C3 linearisation algoritm has been published in the academic 
literature, where it has been peer-reviewed. It has been in use in 
languages such as Dylan, Python and Perl 6 for at least 16 years. Your 
variant is experimental and untested (unless you can point to languages 
already using it). It won't be easy to convince the core devs to change 
algorithms unless you can point to an actual problem with the status quo 
more serious than "it surprises me".

I don't think the bug tracker is the right place to debate your variant: 
probably not enough eyes on it, and I'm certainly not qualified to pick 
out problems with your design or judge if it is better. If you want to 
take this further, I suggest you try the Python-Ideas or Python-Dev 
mailing lists:

* Python-Ideas is high-volume and plagued by bike-shedding, but is the 
official first step for proposing major changes to the language.

* Python-Dev is lower volume and more likely to catch the eye of senior 
core developers, but they may tell you to take it to Python-Ideas first 
(but not always).

If you don't like mailing lists, you could try Discuss:

Whichever forum you pick, be prepared for serious push-back. The onus 
will be on you to prove that the status quo is not good and your 
alternative solves some real problems. You might want to read these 

I'm telling you this not to discourage you from taking it further, but 
so that you understand that if you want this change you have to be 
prepared to work for it.

Good luck!
msg358938 - (view) Author: Cyker Way (cykerway) * Date: 2019-12-28 10:31
Thank you for the links. I doubt this c3 variant could break EPG consistency making it c2. May run some tests later and move on to discussion board. Guess I'm done here.
msg358939 - (view) Author: Cyker Way (cykerway) * Date: 2019-12-28 10:50
Ahhh, 1 second, I haven't really quit from this. I could open another thread but it's highly related to this one.

I just came up with something that looks like a bug not a feature in the original c3.

    #!/usr/bin/env python3

    #        A       C
    #        B       D      X      A
    #                E      F
    #                G

    class A(object): pass
    class B(A): pass
    class C(object): pass
    class D(C): pass
    class X(object): pass
    class E(B, D, A): pass
    class F(B, D, X, A): pass
    class G(E, F): pass

The script fails. It cannot find GEFBDCXA, which looks valid?

You can close again if you feel this isn't a bug. I'm gone for a while.
msg358986 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-12-29 11:49
> You can close again if you feel this isn't a bug.

Yep, it's still not a bug. As Steven said, Python is correctly (modulo undiscovered bugs) implementing the C3 algorithm, and the C3 algorithm does indeed fail in this case.
Date User Action Args
2020-01-21 17:18:47corona10setpull_requests: - pull_request17493
2020-01-21 17:16:12corona10setpull_requests: + pull_request17493
2019-12-29 11:49:32mark.dickinsonsetstatus: open -> closed

messages: + msg358986
nosy: + mark.dickinson
2019-12-28 10:50:04cykerwaysetstatus: closed -> open
resolution: not a bug ->
messages: + msg358939
2019-12-28 10:31:44cykerwaysetmessages: + msg358938
2019-12-28 06:46:49steven.dapranosetmessages: + msg358931
2019-12-28 05:57:23cykerwaysetmessages: + msg358930
2019-12-28 05:53:09cykerwaysetmessages: + msg358929
2019-12-28 02:56:05steven.dapranosetstatus: open -> closed

nosy: + steven.daprano
messages: + msg358926

resolution: not a bug
stage: resolved
2019-12-28 02:21:57cykerwaycreate