Use C3 MRO algorithm

[gvanrossum]

BPO	618704
Nosy	@gvanrossum

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/gvanrossum'
closed_at = <Date 2002-11-14.19:50:56.000>
created_at = <Date 2002-10-04.19:11:26.000>
labels = ['interpreter-core']
title = 'Use C3 MRO algorithm'
updated_at = <Date 2002-11-14.19:50:56.000>
user = 'https://github.com/gvanrossum'

bugs.python.org fields:

activity = <Date 2002-11-14.19:50:56.000>
actor = 'gvanrossum'
assignee = 'gvanrossum'
closed = True
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2002-10-04.19:11:26.000>
creator = 'gvanrossum'
dependencies = []
files = []
hgrepos = []
issue_num = 618704
keywords = []
message_count = 2.0
messages = ['12604', '12605']
nosy_count = 1.0
nosy_names = ['gvanrossum']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue618704'
versions = ['Python 2.3']

[gvanrossum]

In

http://mail.python.org/pipermail/python-dev/2002-October/029035.html

and following messages, Samuele Pedroni argues that the
current MRO algorithm has some unexpected properties,
and that the "naive" algorithm described in the docs
(keep the last occurrence in a depth-first search) is
not monotonic. The current algorithm is monotonic. A
better algorithm, named C3, is described in this paper:

http://www.webcom.com/haahr/dylan/linearization-oopsla96.html

I believe that the current algorithm is the same as
L*[LOOPS] mentioned in this paper (though I have no
proof). The paper argues convincingly that C3 is better
than L*[LOOPS], so I propose to use C3 starting in
Python 2.3.

This can cause backwards compatibilities in certain
cases, but the new algorithm matches intuition better
than the current algorithm. (The naive algorithm from
the docs is unacceptable due to its non-monotonicity.)

[gvanrossum]

Logged In: YES
user_id=6380

Fixed; I checked in the code from patch 619475.