Порядок разрешения методов в Python 2.3

Начало

Felix qui potuit rerum cognoscere causas — Вергилий

Всё началось с сообщения Samuele Pedroni в списке рассылки разработчиков Python [1]. В своём сообщении Samuele показал, что порядок разрешения методов в Python 2.2 не является монотонным, и предложил заменить его порядком разрешения методов C3. Guido согласился с его доводами, поэтому в Python 2.3 теперь используется C3. Сам метод C3 не имеет отношения к Python: его придумали разработчики Dylan, а описан он в статье, предназначенной для программистов на Lisp [2]. В этой статье (надеюсь, доступно) обсуждается алгоритм C3 для питонистов, желающих понять причины изменений.

Прежде всего отмечу, что всё, о чём я собираюсь рассказать, относится только к классам нового стиля, появившимся в Python 2.2: классы старого стиля сохраняют прежний порядок разрешения методов — сначала в глубину, затем слева направо. Таким образом, старый код с классами старого стиля не будет нарушен; и даже если в принципе код с классами нового стиля в Python 2.2 мог бы быть нарушен, на практике случаи, когда порядок разрешения C3 отличается от порядка разрешения методов в Python 2.2, настолько редки, что реальных проблем с кодом не ожидается. Итак:

Не пугайтесь!

Кроме того, если вы не используете множественное наследование в значительной степени и у вас нет нетривиальных иерархий, вам не нужно понимать алгоритм C3, и вы можете спокойно пропустить эту статью. С другой стороны, если вы действительно хотите знать, как работает множественное наследование, эта статья для вас. Хорошая новость в том, что всё не так сложно, как может показаться.

Начну с нескольких основных определений.

1. Для класса C в сложной иерархии множественного наследования определить порядок переопределения методов, то есть порядок предков C, — нетривиальная задача.
2. Список предков класса C, включающий сам класс и упорядоченный от ближайшего предка к самому дальнему, называется списком приоритетов класса или линеаризацией C.
3. Порядок разрешения методов (MRO) — это набор правил, по которым строится линеаризация. В литературе по Python выражение «MRO класса C» также используется как синоним линеаризации класса C.
4. Например, в случае иерархии с одиночным наследованием, если C является подклассом C1, а C1 — подклассом C2, то линеаризация C — это просто список [C, C1, C2]. Однако в иерархиях с множественным наследованием построить линеаризацию сложнее, поскольку труднее обеспечить соблюдение локального порядка приоритета и монотонности.
5. Локальный порядок приоритета я рассмотрю позже, а определение монотонности приведу сейчас. MRO является монотонным, если выполняется следующее условие: если C1 предшествует C2 в линеаризации C, то C1 предшествует C2 в линеаризации любого подкласса C. В противном случае безобидная операция создания нового класса могла бы изменить порядок разрешения методов и потенциально привести к очень тонким ошибкам. Примеры таких ситуаций будут приведены далее.
6. Не для всех классов можно построить линеаризацию. В сложных иерархиях бывают случаи, когда невозможно создать класс, линеаризация которого удовлетворяла бы всем желаемым свойствам.

Вот пример такой ситуации. Рассмотрим иерархию

>>> O = object
>>> class X(O): pass
>>> class Y(O): pass
>>> class A(X,Y): pass
>>> class B(Y,X): pass

которую можно представить следующим графом наследования. Здесь O обозначает класс object, с которого начинается любая иерархия классов нового стиля:

 -----------
|           |
|    O      |
|  /   \    |
 - X    Y  /
   |  / | /
   | /  |/
   A    B
   \   /
     ?

В этом случае невозможно создать новый класс C на основе A и B, поскольку X предшествует Y в A, а Y предшествует X в B, поэтому порядок разрешения методов в C был бы неоднозначным.

В такой ситуации Python 2.3 вызывает исключение (TypeError: конфликт MRO между базовыми классами Y и X), не позволяя неопытному программисту создавать неоднозначные иерархии. Python 2.2, напротив, исключение не вызывает, а выбирает порядок ad hoc (в данном случае CABXYO).

Порядок разрешения методов C3

Введу несколько простых обозначений, которые пригодятся в дальнейшем. Буду использовать сокращённую запись:

C1 C2 ... CN

для обозначения списка классов [C1, C2, … , CN].

Голова списка — его первый элемент:

head = C1

а хвост — оставшаяся часть списка:

tail = C2 ... CN.

Также буду использовать обозначение:

C + (C1 C2 ... CN) = C C1 C2 ... CN

для обозначения суммы списков [C] + [C1, C2, … ,CN].

Теперь я могу объяснить, как работает MRO в Python 2.3.

Рассмотрим класс C в иерархии с множественным наследованием, где C наследуется от базовых классов B1, B2, … , BN. Нужно вычислить линеаризацию L[C] класса C. Правило таково:

линеаризация C — это сумма C и слияния линеаризаций родительских классов со списком этих родительских классов.

В символьной записи:

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

В частности, если C — класс object, у которого нет родителей, его линеаризация тривиальна:

L[object] = object.

Однако в общем случае слияние нужно вычислять по следующему правилу:

возьмите голову первого списка, то есть L[B1][0]; если этой головы нет в хвосте ни одного из остальных списков, добавьте её в линеаризацию C и удалите её из списков, участвующих в слиянии. В противном случае рассмотрите голову следующего списка и возьмите её, если она подходит. Затем повторяйте эту операцию, пока не будут удалены все классы или пока не окажется, что подходящих голов нет. В последнем случае построить слияние невозможно, и Python 2.3 откажется создавать класс C и вызовет исключение.

Это правило гарантирует, что операция слияния сохраняет порядок, если его можно сохранить. С другой стороны, если порядок сохранить невозможно (как в приведённом выше примере серьёзного конфликта порядка), вычислить слияние не удастся.

Если у C только один родительский класс (одиночное наследование), вычислить слияние несложно; в этом случае:

L[C(B)] = C + merge(L[B],B) = C + L[B]

Однако при множественном наследовании всё сложнее, и я не думаю, что вы поймёте это правило без пары примеров ;-)

Примеры

Первый пример. Рассмотрим следующую иерархию:

>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(D,E): pass
>>> class A(B,C): pass

В этом случае граф наследования можно изобразить так:

                          6
                         ---
Level 3                 | O |                  (more general)
                      /  ---  \
                     /    |    \                      |
                    /     |     \                     |
                   /      |      \                    |
                  ---    ---    ---                   |
Level 2        3 | D | 4| E |  | F | 5                |
                  ---    ---    ---                   |
                   \  \ _ /       |                   |
                    \    / \ _    |                   |
                     \  /      \  |                   |
                      ---      ---                    |
Level 1            1 | B |    | C | 2                 |
                      ---      ---                    |
                        \      /                      |
                         \    /                      \ /
                           ---
Level 0                 0 | A |                (more specialized)
                           ---

Линеаризации O, D, E и F тривиальны:

L[O] = O
L[D] = D O
L[E] = E O
L[F] = F O

Линеаризацию B можно вычислить следующим образом:

L[B] = B + merge(DO, EO, DE)

Видим, что D — подходящая голова, поэтому берём её, и остаётся вычислить merge(O,EO,E). Теперь O не является подходящей головой, поскольку находится в хвосте последовательности EO. В этом случае правило предписывает перейти к следующей последовательности. Затем видим, что E — подходящая голова; берём её, и остаётся вычислить merge(O,O), что даёт O. Следовательно:

L[B] =  B D E O

Применив ту же процедуру, получим:

L[C] = C + merge(DO,FO,DF)
     = C + D + merge(O,FO,F)
     = C + D + F + merge(O,O)
     = C D F O

Теперь можно вычислить:

L[A] = A + merge(BDEO,CDFO,BC)
     = A + B + merge(DEO,CDFO,C)
     = A + B + C + merge(DEO,DFO)
     = A + B + C + D + merge(EO,FO)
     = A + B + C + D + E + merge(O,FO)
     = A + B + C + D + E + F + merge(O,O)
     = A B C D E F O

В этом примере линеаризация довольно удачно упорядочена в соответствии с уровнем наследования: более низкие уровни (то есть более специализированные классы) имеют более высокий приоритет (см. граф наследования). Однако так бывает не всегда.

Предлагаю читателю в качестве упражнения вычислить линеаризацию для моего второго примера:

>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(E,D): pass
>>> class A(B,C): pass

Единственное отличие от предыдущего примера — замена B(D,E) –> B(E,D); однако даже такое небольшое изменение полностью меняет порядок в иерархии:

                           6
                          ---
Level 3                  | O |
                       /  ---  \
                      /    |    \
                     /     |     \
                    /      |      \
                  ---     ---    ---
Level 2        2 | E | 4 | D |  | F | 5
                  ---     ---    ---
                   \      / \     /
                    \    /   \   /
                     \  /     \ /
                      ---     ---
Level 1            1 | B |   | C | 3
                      ---     ---
                       \       /
                        \     /
                          ---
Level 0                0 | A |
                          ---

Обратите внимание, что класс E, находящийся на втором уровне иерархии, предшествует классу C, находящемуся на первом уровне, то есть E более специализирован, чем C, хотя и расположен на более высоком уровне.

Ленивый программист может получить MRO напрямую из Python 2.2, поскольку в данном случае он совпадает с линеаризацией Python 2.3. Достаточно вызвать метод mro() класса A:

>>> A.mro()
[<class 'A'>, <class 'B'>, <class 'E'>,
<class 'C'>, <class 'D'>, <class 'F'>,
<class 'object'>]

Наконец, рассмотрим пример из первого раздела, в котором возникал серьёзный конфликт порядка. В этом случае легко вычислить линеаризации O, X, Y, A и B:

L[O] = 0
L[X] = X O
L[Y] = Y O
L[A] = A X Y O
L[B] = B Y X O

Однако вычислить линеаризацию класса C, наследующего от A и B, невозможно:

L[C] = C + merge(AXYO, BYXO, AB)
     = C + A + merge(XYO, BYXO, B)
     = C + A + B + merge(XYO, YXO)

На этом этапе мы не можем объединить списки XYO и YXO, поскольку X находится в хвосте YXO, а Y — в хвосте XYO: значит, подходящих голов нет, и алгоритм C3 останавливается. Python 2.3 вызывает ошибку и отказывается создавать класс C.

Некорректные порядки разрешения методов

MRO является некорректным, если нарушает такие фундаментальные свойства, как локальный порядок приоритета и монотонность. В этом разделе я покажу, что некорректны и MRO классов старого стиля, и MRO классов нового стиля в Python 2.2.

Начать проще с локального порядка приоритета. Рассмотрим следующий пример:

>>> F=type('Food',(),{'remember2buy':'spam'})
>>> E=type('Eggs',(F,),{'remember2buy':'eggs'})
>>> G=type('GoodFood',(F,E),{}) # under Python 2.3 this is an error!

с такой диаграммой наследования:

             O
             |
(buy spam)   F
             | \
             | E   (buy eggs)
             | /
             G

      (buy eggs or spam ?)

Мы видим, что класс G наследуется от F и E, причём F стоит перед E. Поэтому мы ожидали бы, что атрибут G.remember2buy будет унаследован от F.remember2buy, а не от E.remember2buy. Тем не менее Python 2.2 выдаёт:

>>> G.remember2buy
'eggs'

Это нарушает локальный порядок приоритета, поскольку порядок в списке локальных приоритетов, то есть в списке родительских классов G, не сохраняется в линеаризации G в Python 2.2:

L[G,P22]= G E F object   # F *follows* E

Можно возразить, что причина, по которой F следует за E в линеаризации Python 2.2, заключается в том, что F менее специализирован, чем E, поскольку F является суперклассом E. Тем не менее нарушение локального порядка приоритета весьма неинтуитивно и чревато ошибками. Особенно важно, что в классах старого стиля поведение другое:

>>> class F: remember2buy='spam'
>>> class E(F): remember2buy='eggs'
>>> class G(F,E): pass
>>> G.remember2buy
'spam'

В этом случае MRO равен GFEF, и локальный порядок приоритета сохраняется.

Как правило, следует избегать иерархий, подобных предыдущей, поскольку неясно, должен ли F переопределять E или наоборот. Python 2.3 устраняет неоднозначность, вызывая исключение при создании класса G и тем самым не позволяя программисту создавать неоднозначные иерархии. Это происходит потому, что алгоритм C3 не может вычислить слияние:

merge(FO,EFO,FE)

поскольку F находится в хвосте EFO, а E — в хвосте FE.

Правильное решение — создать однозначную иерархию, то есть наследовать G от E и F (сначала от более специализированного класса), а не от F и E. В этом случае MRO равен GEF, и никаких сомнений не возникает.

           O
           |
           F (spam)
         / |
(eggs)   E |
         \ |
           G
             (eggs, no doubt)

Python 2.3 заставляет программиста создавать хорошие иерархии (или, по крайней мере, менее подверженные ошибкам).

К слову, отмечу, что алгоритм Python 2.3 достаточно умен, чтобы распознавать очевидные ошибки, например повторение классов в списке родительских классов:

>>> class A(object): pass
>>> class C(A,A): pass # error
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: duplicate base class A

В такой ситуации Python 2.2 (как для классов старого стиля, так и для классов нового стиля) не вызвал бы исключения.

Наконец, хочу отметить два вывода, которые мы сделали из этого примера:

1. несмотря на название, MRO определяет порядок разрешения атрибутов, а не только методов;
2. основная еда питонистов — спам! (но вы и так это знали ;-)

Обсудив локальный порядок приоритета, перейдём к монотонности. Я хочу показать, что MRO как классов старого стиля, так и классов нового стиля в Python 2.2 не является монотонным.

Доказать немонотонность MRO классов старого стиля довольно просто — достаточно взглянуть на ромбовидную диаграмму:

   C
  / \
 /   \
A     B
 \   /
  \ /
   D

Несогласованность легко заметить:

L[B,P21] = B C        # B precedes C : B's methods win
L[D,P21] = D A C B C  # B follows C  : C's methods win!

С другой стороны, с MRO в Python 2.2 и 2.3 проблем нет: оба дают:

L[D] = D A B C

В своём эссе [3] Guido отмечает, что на практике MRO классов старого стиля не так уж плох, поскольку ромбовидных иерархий для таких классов обычно можно избегать. Но все классы нового стиля наследуются от object, поэтому ромбовидных иерархий избежать нельзя, а несогласованности возникают в каждом графе множественного наследования.

MRO в Python 2.2 затрудняет, но не исключает нарушение монотонности. Следующий пример, первоначально предложенный Samuele Pedroni, показывает, что MRO в Python 2.2 немонотонен:

>>> class A(object): pass
>>> class B(object): pass
>>> class C(object): pass
>>> class D(object): pass
>>> class E(object): pass
>>> class K1(A,B,C): pass
>>> class K2(D,B,E): pass
>>> class K3(D,A):   pass
>>> class Z(K1,K2,K3): pass

Вот линеаризации согласно MRO C3 (читатель должен проверить эти линеаризации в качестве упражнения и нарисовать диаграмму наследования ;-)

L[A] = A O
L[B] = B O
L[C] = C O
L[D] = D O
L[E] = E O
L[K1]= K1 A B C O
L[K2]= K2 D B E O
L[K3]= K3 D A O
L[Z] = Z K1 K2 K3 D A B C E O

Python 2.2 выдаёт точно такие же линеаризации для A, B, C, D, E, K1, K2 и K3, но другую линеаризацию для Z:

L[Z,P22] = Z K1 K3 A K2 D B C E O

Очевидно, что эта линеаризация неверна, поскольку A стоит перед D, тогда как в линеаризации K3 A стоит после D. Иными словами, в K3 методы, унаследованные от D, переопределяют методы, унаследованные от A, но в Z, который по-прежнему является подклассом K3, методы, унаследованные от A, переопределяют методы, унаследованные от D! Это нарушает монотонность. Кроме того, линеаризация Z в Python 2.2 также не согласуется с локальным порядком приоритета: локальный список приоритетов класса Z равен [K1, K2, K3] (K2 предшествует K3), тогда как в линеаризации Z K2 следует за K3. Эти проблемы объясняют, почему правило версии 2.2 было отвергнуто в пользу правила C3.

Конец

Этот раздел предназначен для нетерпеливых читателей, которые пропустили все предыдущие разделы и сразу перешли к концу. Он также для ленивых программистов, которые не захотели напрягать мозги. Наконец, он для программистов с некоторой долей самоуверенности, иначе они не стали бы читать статью о порядке разрешения методов C3 в иерархиях множественного наследования ;-) Все три достоинства вместе (а не по отдельности) заслуживают награды: это короткий скрипт для Python 2.2, который позволяет вычислить MRO версии 2.3, не напрягая мозги. Просто измените последнюю строку, чтобы поэкспериментировать с различными примерами, рассмотренными в этой статье:

#<mro.py>

"""C3 algorithm by Samuele Pedroni (with readability enhanced by me)."""

class __metaclass__(type):
    "All classes are metamagically modified to be nicely printed"
    __repr__ = lambda cls: cls.__name__

class ex_2:
    "Serious order disagreement" #From Guido
    class O: pass
    class X(O): pass
    class Y(O): pass
    class A(X,Y): pass
    class B(Y,X): pass
    try:
        class Z(A,B): pass #creates Z(A,B) in Python 2.2
    except TypeError:
        pass # Z(A,B) cannot be created in Python 2.3

class ex_5:
    "My first example"
    class O: pass
    class F(O): pass
    class E(O): pass
    class D(O): pass
    class C(D,F): pass
    class B(D,E): pass
    class A(B,C): pass

class ex_6:
    "My second example"
    class O: pass
    class F(O): pass
    class E(O): pass
    class D(O): pass
    class C(D,F): pass
    class B(E,D): pass
    class A(B,C): pass

class ex_9:
    "Difference between Python 2.2 MRO and C3" #From Samuele
    class O: pass
    class A(O): pass
    class B(O): pass
    class C(O): pass
    class D(O): pass
    class E(O): pass
    class K1(A,B,C): pass
    class K2(D,B,E): pass
    class K3(D,A): pass
    class Z(K1,K2,K3): pass

def merge(seqs):
    print '\n\nCPL[%s]=%s' % (seqs[0][0],seqs),
    res = []; i=0
    while 1:
      nonemptyseqs=[seq for seq in seqs if seq]
      if not nonemptyseqs: return res
      i+=1; print '\n',i,'round: candidates...',
      for seq in nonemptyseqs: # find merge candidates among seq heads
          cand = seq[0]; print ' ',cand,
          nothead=[s for s in nonemptyseqs if cand in s[1:]]
          if nothead: cand=None #reject candidate
          else: break
      if not cand: raise "Inconsistent hierarchy"
      res.append(cand)
      for seq in nonemptyseqs: # remove cand
          if seq[0] == cand: del seq[0]

def mro(C):
    "Compute the class precedence list (mro) according to C3"
    return merge([[C]]+map(mro,C.__bases__)+[list(C.__bases__)])

def print_mro(C):
    print '\nMRO[%s]=%s' % (C,mro(C))
    print '\nP22 MRO[%s]=%s' % (C,C.mro())

print_mro(ex_9.Z)

#</mro.py>

На этом всё, друзья!

Наслаждайтесь!

Материалы