Порядок разрешения методов 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, который хочет понять причины изменения.

Прежде всего, позвольте мне отметить, что сказанное мной относится только к классам нового стиля, введённым в 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 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) является плохим, когда он нарушает такие фундаментальные свойства, как локальный порядок приоритета и монотонность. В этом разделе я покажу, что порядок разрешения методов как для классических, так и для новых стилей классов в 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.rembermer2buy, а не от 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. стандартным продуктом для Python-разработчиков является спам! (но вы это уже знали ;-)

После обсуждения проблемы локального порядка приоритета, позвольте мне теперь рассмотреть вопрос монотонности. Моя цель — показать, что ни 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! Это нарушение монотонности. Более того, линейная структура Python 2.2 для Z также не соответствует локальному порядку приоритета, поскольку локальный список приоритетов класса 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>

Вот и всё,

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

Ресурсы