[Zope-dev] New-style ExtensionClasses (Zope 2.8) -- MRO issue

[Jim Fulton]

I've been working on a "new-style" ExtensionClass (nsEC) project to
reimplement ExtensionClass as a new-style meta class.  This will allow
ExtensionClasses (i.e. most Zope 2 classes) to be able to use features
of new-style Python classes, including:

- New protocols,

- Descriptors,

- Garbage Collection,

   ...

I think I've got this largely working, but have encountered a
significant issue that I'd like some input on.

New-style classes and classic classes use different algorithms for
looking up inherited attributes (e.g. methods).  Classic classes use a
left-to-right depth-first algorithm.  Python 2.3 uses a "C3
Method-Resolution Order" algorithm.  I won't try to explain how this
algorithm works. If you are curious, see:

   http://www.python.org/2.3/mro.html

This new algorithm has a couple of noteworthy properties:

- It yields different lookup results than the left-to-right
   depth-first algorithm used for classic classes.

- It is sometimes impossible to compute a "method resolution order"
   for a given class and base classes.

     >>> class A(object):
     ...     pass

     >>> class B(A):
     ...     pass

     >>> class C(A, B):
     ...     pass

     Traceback (most recent call last):
       File "<stdin>", line 1, in ?
     TypeError: Cannot create a consistent method resolution
     order (MRO) for bases B, A

The original ExtensionClass used the left-to-right depth-first
algorithm used for classic classes.  Currently, nsEC inherits the new
method lookup algorithm from type (the standard Python 2.3 metaclass
used for new-style classes).  This has run into significant
difficulties with the Zope 2 classes, which have a highly complex
inheritence graph.

An initial analysis showed that for more than half of the classes in
Zope 2, it was impossible to compute a method-resolution order using
the new algorithm.  After about a day of analysis (and development of
a tool to aid in the analysis) I've been able to adjust the Zope
classes so that they will work with the new algorithm.

I also analyzed the CMF head.  To use the new algorithm with the CMF,
it was necessary to make some changes to the CMF and to Zope.  In one
case, it was necessary to copy some methods around.

An interesting result of the analysis is that it identified several
methods that were being inherited incorrectly.  The new inheritence
algorithm yeilded better results for these cases, once the classes
were modified enough to use the algorithm at all.

It is very likely that, if we use the new algorithm for nsEC, many
products will not work anymore (meaning with Zope 2.8).  Modifying the
products to work will probably be a non-trivial undertaking.

We have three alternatives:

1. Use the old method-lookup algorithm for nsEC.

    Pro: backward compatible

    Con: may produce odd results if a new-style class with a complex
         arrangement of base classes is mixed with an ExtensionClass.

2. Use the new-style method-lookup algithm

    Pro: Most consistent with new-style classes.

    Cons: Likely that many products will be broken and require change
          to work with nsEC/Zope 2.8.

          Analysis of the changes needed to fix method-resolution-order
          problems is extremely complex.

3. Use a hybrid schema.  I'll call this the "encapsulated base"
    scheme.

    Consider:

      >>> class C(X, Y, Z):
      ...    def foo(self): ...
      ...    ...

    When we look up an attribute, we do the following:

    - Look in C's dictionary first. All three algorithms agree on
      this. :)

    - Look up the attribute in X.  We don't care how we het the
      attribute from X. If X is a new-style-class, we use the new
      algithm. If X is a classic class, we use left-to-right
      depth-first. If X is an nsEC, use the "encapsulated base"
      algithm.

      If we don't find the attribute in X, look in Y and then in Z,
      using the same approach.

      This algithm will produce backward compatible results, providing
      the equivalent of left-to-right depth-first for nsECs and classic
      classes.

      (Note for the more advanced reader:
       we'll actually do something less abstract.  We'll use a simple
       algorthm to merge the __mro__ of the base classes, computing an
       __mro__ for classes classes using the left-to-right depth-first
       algorithm. We'll basically lay the mros end-to-end left-to-right
       and remove repeats, keeping the first occurence of each class.)

    I find this approach appealing for reasons of encapsulation.  When
    reasoning about C, I can reason from known behavior of X, Y, and Z,
    without considering their respective inherietnce hierarchies, which
    I consider to be an implementation detail.

    Pros: backward compatible

          Less likely than option 1 to produce odd results if a
          new-style class with a complex arrangement of base classes is
          mixed with an ExtensionClass.

    Con: may produce odd results if a new-style class with a complex
         arrangement of base classes is mixed with an ExtensionClass.


Thoughts?

I am worried enough about breaking products that I'm inclined to go
with option 3.

Does anybody think we ought to use the new algorithm (option 2)?

Jim

-- 
Jim Fulton           mailto:jim at zope.com       Python Powered!
CTO                  (540) 361-1714            http://www.python.org
Zope Corporation     http://www.zope.com       http://www.zope.org