Порядок разрешения методов в 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

Можно утверждать, что 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] Гвидо отмечает, что 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>

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

всего хорошего!

Материалы