[PEAK] naming.lookup() vs config.lookupComponent()

[Doug Quale]

"Phillip J. Eby" <pje at telecommunity.com> writes:

> I think that probably the best thing to do would be to simply make
> parent iteration fail after a predetermined "recursion limit", since
> it's likely that component trees of depth 100 or greater (e.g. an
> infinite parent loop) are some kind of error, anyway.  This would be
> faster and less resource intensive to check than trying to track
> whether a particular component has already been seen in the iteration
> process.

That would work.  I know of 3 different techniques used to detect
circularities, each with different design tradeoffs:

1. iteration/recursion limit
   (linear time, constant space) Simple and easy to understand but
   limits depth.  Used by Unix to detect circular symlinks.

2. keep full history
   (linear time, linear space) Unattractive unless the history is
   needed for some other reason because of the large space cost.

3. 2-pointer tortoise and hare algorithm
   (linear time, constant space) Fairly simple.  Constant space cost
   is a big attraction, and time penalty is not too severe.

If you haven't seen the tortoise and hare algorithm, it's an idea that
is well known in the Lisp world where circular lists are fairly
common.  The key idea is that you can detect circular structures
without keeping an entire path history -- all you need is one extra
pointer.  It uses a slow pointer and a fast pointer.  At each step,
the slow pointer advances one and the fast pointer advances two.  If
the structure is circular the fast and slow pointers will eventually
meet.

I think in this case it would look something like (untested):

def iterParents(component):

    """Iterate over all parents of 'component'"""

    # Use tortoise and hare algorithm to detect circular parent hierarchies.
    slow = fast = component

    while slow is not None:

        yield slow

        slow = getParentComponent(slow)

        fast = getParentComponent(getParentComponent(fast))
        if fast is not None and slow == fast:
            raise exception.CyclicComponentTree('circular component parent hierarchy')