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

Примечание

Это исторический документ, представленный в качестве приложения к официальной документации. Порядок разрешения методов, обсуждаемый здесь, был введен в Python 2.3, но он по-прежнему используется в более поздних версиях - включая Python 3.

По Michele Simionato.

Аннотация:

Этот документ предназначен для программистов на Python, которые хотят понять порядок разрешения метода C3, используемый в Python 2.3. Хотя он и не предназначен для новичков, он вполне обучаем и содержит множество отработанных примеров. Я не знаю других общедоступных документов с аналогичным объемом, поэтому он должен быть полезен.

Отказ от ответственности:

Я передаю этот документ в дар Python Software Foundation под лицензией Python 2.3. Как обычно в таких случаях, я предупреждаю читателя, что то, что написано ниже, должно быть правильным, но я не даю никаких гарантий. Используйте это на свой страх и риск!

Благодарности:

Все люди из списка рассылки Python, которые прислали мне свою поддержку. Полу Фоули, который указал на различные неточности и заставил меня добавить часть о локальном упорядочивании старшинства. Дэвиду Гуджеру за помощь с форматированием в reStructuredText. Дэвиду Мерцу за помощь в редактировании. Наконец, Гвидо ван Россум, который с энтузиазмом добавил этот документ на официальную домашнюю страницу Python 2.3..

Начало

Felix qui potuit rerum cognoscere causas – Virgilius

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

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

Не бойся!

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

Позвольте мне начать с некоторых основных определений.

1. При наличии класса C в сложной иерархии множественного наследования нетривиальной задачей является определение порядка переопределения методов, то есть определение порядка предков C.

2. Список предков класса C, включая сам класс, упорядоченный от ближайшего предка к самому дальнему, называется списком старшинства класса или линеаризацией C.

3. Порядок разрешения методов (Method Resolution Order, MRO) - это набор правил, которые строят линеаризацию. В литературе по Python идиома «MRO of 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 не вызывает исключения, но выбирает 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.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:

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!

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

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

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

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

#<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>

Вот и все, друзья,

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

Ресурсы

[1]

Поток на python-dev, начатый Самуэле Педрони: https://mail.python.org/pipermail/python-dev/2002-October/029035.html

[2]

Статья Монотонная линеаризация суперкласса для Dylan: https://doi.org/10.1145/236337.236343

[3]

Эссе Гвидо ван Россума, Объединение типов и классов в Python 2.2: https://web.archive.org/web/20140210194412/http://www.python.org/download/releases/2.2.2/descrintro