C3-Линеаризация (Method Resolution Order - MRO)

Алгоритм, используемый преимущественно для получения устойчивой линеаризации иерархии множественного наследования в объектно-ориентированном программировании.

Данная линеаризация используется для определения порядка, в котором должны наследоваться методы.

Линеаризация

Линеаризация класса C - список родительских классов класса C, включая сам класс C. Порядок начинается с самого ближайшего родительского класса.

В случае классического наследования C --> C1 --> C2 линеаризация класса C будет иметь вид [C, C1, C2].

Стоит отметить что не все классы допускают линеаризацию.

Пример ситуации где не возможна линеаризация

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

  class C(A,B): fail

Представление иерархии, примера выше, в виде графа

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

L[A] = [A, X, Y, O]

L[B] = [B, Y, X, O]

L[C] = [A, B, X, Y, O] - не монотонна!

Монотонность

MRO монотонно когда следующее заявление является истинным (true):

Если C1 предшествует C2 в линеаризации C, тогда C1 предшествует C2 в линеаризации любого производного класса от класса C.

Получение монотонной линеаризации

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

• C1 C2 ... CN - список классов [C1, C2, ..., CN]
• head = C1 - head первый элемент списка
• tail = C2 ... CN - tail остальная часть списка
• C + (C1 C2 ... CN) = C C1 C2 ... CN - сумма списков [C] + [C1, C2, ..., CN]

Линеаризация класса C определяется как сумма C плюс объединение merge линеаризаций родительских классов и списка родительских классов:

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

К примеру, если C это класс object, у которого нет родительских классов, то линеаризация тривиальна:

L[object] = object

Однако, обычно необходимо вычислить объединение merge в соответствии со следующим правилом:

Берем первый элемент head из первого списка, т.е. L[B1][0]; если head не входит в tail любого другого списка, то добавляем head в линеаризацию C и удаляем его из списков в merge, иначе берем head из следующего списка и проходим те же шаги что были описаны ранее. И так повторяем до тех пор пока не удалим все классы из merge или если не возможно будет удалить head значит в этом случае не возможно построить линеаризацию.

В случае одного родительского класса (классическое наследование) merge для получения линеаризации выглядит просто:

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

Однако в случае множественного наследования merge будет немного сложней. Для того что бы лучше понять его, рассмотрим несколько примеров:

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

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 и C:

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

Теперь мы можем рассчитать линеаризацию для A:

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

Монотонность для C и B сохранилась

                 L[C] - монотонна
               _ ___ _
              | |   | |
   L[A] = A B C D E F O
            |___|_|___|
                 L[B] - монотонна

Ссылки

• Python Documentation
• Habrahabr (Python)