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

Начало

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

Всё началось с сообщения Самуэле Педрони в списке рассылки разработчиков Python [1]. В своём сообщении Самуэле показал, что порядок разрешения методов в Python 2.2 не является монотонным, и предложил заменить его порядком разрешения методов C3. Гвидо согласился с его доводами, поэтому в 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: в A класс X предшествует Y, а в B класс Y предшествует X, поэтому порядок разрешения методов в C был бы неоднозначным.

В такой ситуации Python 2.3 вызывает исключение (TypeError: MRO conflict among bases Y, X), не позволяя неопытному программисту создавать неоднозначные иерархии. Python 2.2 исключение не вызывает, а выбирает произвольный порядок (в данном случае 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

Можно возразить, что в линеаризации Python 2.2 F следует за E, поскольку 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 классов старого стиля, ни 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], что на практике MRO старого стиля не так уж плох, поскольку для классов старого стиля обычно можно избегать ромбовидных иерархий. Но все классы нового стиля наследуются от object, поэтому ромбовидных иерархий не избежать, а противоречия возникают в каждом графе множественного наследования.

MRO Python 2.2 затрудняет нарушение монотонности, но не исключает его. Следующий пример, первоначально предложенный Самуэле Педрони, показывает, что 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>

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

приятного чтения!

Материалы