Preview traversal using Python generators with a mechanism to ignore subtrees

As indicated by the audio diode, yours is iterator.throw(IgnoreSubtree)

returning the iterator

next value (will mask the complex exception handling for a moment), so it consumes 2

what you expect to see added to out

on the next loop iteration in test_ignore_subtree

.

You also asked about why he throws himself StopIteration

; sequence Exception

called / caught:

• iterator.throw(IgnoreSubtree)
  
  throws IgnoreSubtree
  
  that falls into the inner looppreorder_traversal
  
  
• which IgnoreSubtree
  
  goes to the inner iterator withiterator.throw(e)
  
  
• IgnoreSubtree
  
  gets into except IgnoreSubtree:
  
  and return
  
  called; however iterator.throw(e)
  
  wants to get the next value from this inner iterator that only has return
  
  ed, so it is promoted StopIteration
  
  .
• before the original is returned iterator.throw(IgnoreSubtree)
  
  , it goes through the outer loop again in preorder_traversal
  
  because it wants to return the next value from iterator
  
  .

Hope this helps!

Update

Here is the implementation of this basic circuit that I would use, as well as the nosetest passing:

from nose.tools import eq_

def preorder_traversal(obj, ignore_only_descendents_of=None, ignore_subtrees=None):
    if ignore_subtrees and obj in ignore_subtrees:
        return

    yield obj

    if ignore_only_descendents_of and obj in ignore_only_descendents_of:
        return

    if isinstance(obj, dict):
        for k, v in iter(sorted(obj.iteritems())):
            iterator = preorder_traversal(v, ignore_only_descendents_of, ignore_subtrees)
            for o in iterator:
                yield o


def test_ignore_subtree():
    obj = {'a': {'c': 3}, 'b': 2, 'd': {'e': {'f': 4}}, 'g': 5, 'h': 6}
    ignore_only_descendents_of = [{'e': {'f': 4}}]
    ignore_subtrees = [{'c': 3}, 5]

    iterator = preorder_traversal(obj, ignore_only_descendents_of, ignore_subtrees)
    out = []

    for o in iterator:
        out.append(o)

    expected = [obj, 2, {'e': {'f': 4}}, 6]
    eq_(expected, out)

      

        
        
        
      

    

Notes:

• your example allows you to exclude descendants {'c':3}
  
  including {'c':3}
  
  ; I found this a bit confusing, as I expect you would normally want to exclude an entire subtree including its root, so I changed preorder_traversal
  
  to exclude two optional lists of things each time.
• moving the subtrees to jump into the iterator itself seems cleaner; you can avoid using it Exception
  
  for flow control altogether.
• a more complex example demonstrating two types of subtree exceptions.

Implementing clipping a subtree throw

excluding from an iterator results in messy, error-prone code, both in the generator and in the function that consumes it. Looking at some of the answers, it makes me think that the filter callback is a sane approach.

This would be a generalization of Ryan's answer :

def preorder_traversal(obj, bailout_fn=None):
    yield obj
    if bailout_fn and bailout_fn(obj):
        return

    if isinstance(obj, dict):
        for k, v in obj.iteritems():
            for o in preorder_traversal(v, bailout_fn):
                yield o

      

        
        
        
      

    

And here are some nasal tests that demonstrate how they are used:

def test_ignore_subtree():
    obj = {'a': {'c': 3}, 'b': 2}
    eq_([obj, {'c': 3}, 3, 2], list(preorder_traversal(obj)))

    iterator = preorder_traversal(obj, lambda o: o == {'c': 3})
    out = list(iterator)
    eq_([obj, {'c': 3}, 2], out)


def test_ignore_subtree2():
    obj = {'a': {'c': 3, 'd': 4}, 'b': 2}
    eq_([obj, {'c': 3, 'd': 4}, 3, 4, 2],
            list(preorder_traversal(obj)))

    iterator = preorder_traversal(obj, lambda o: o == {'c': 3, 'd': 4})
    out = list(iterator)

    eq_([obj, {'c': 3, 'd': 4}, 2], out)

      

        
        
        
      

    

I have never posted a second answer before, but I think it is appropriate in this case. The first section of this answer discusses a way to clean up the generator interface. The second section discusses when it is most appropriate to use this fix and when it is more appropriate to replace it with throw

a different construct.

Cleaning up the interface

There are two key issues with the generator. None of them have anything to do with correctness - it behaves as expected. They are related to the interface. So fix the interface issues with the wrapper function.

The first problem is that it throw

returns the severity that the current test removes. So write a wrapper that returns a nonessential value when called IgnoreSubtree

. And the second problem is that when thrown IgnoreSubtree

, sometimes it completely exhausts the iterator. So write a wrapper that catches StopIteration

and handles it gracefully. It does the following:

def ptv_wrapper(obj):
    pt = preorder_traversal(obj)
    while True:
        try:
            o = pt.next()
            while True:
                try:
                    yield o
                except IgnoreSubtree as e:
                    yield
                    o = pt.throw(e)
                else:
                    break

        except StopIteration:
            return

      

        
        
        
      

    

Your above code will work as is if you use the above as a wrapper around preorder_traversal

.

When to use throw

; When to use callbacks When to usesend

The question of whether to use throw

in this case is difficult. As danvk pointed out , this exception-based method uses some rather complex (and exotic) methods, and the extra complexity may not be worth it. Also, there is something a little fishy about using control flow exceptions. Generators already do this internally (using StopIteration

), so there must be some kind of excuse, but it's worth considering that this is an excuse.

The first question is whether it uses throw

or reduces the complexity of the existing code. If your use case does not require a tight coupling between generator and consumer, you are probably better off using callbacks. (And if your code is tightly coupled, but not necessary, you should refactor!) However, in some cases, a hard linking is unavoidable. In these cases, using throw

(or send

- see below) probably doesn't increase the complexity and can reduce it. Indeed, if you use callbacks in a situation where those callbacks depend on a lot of external state to do what they need to do, then you are probably writing code with tight coupling and low coupling - the worst of both worlds! Using throw

orsend

, you make sure that the generator and the state that controls it are close to each other; the connection will be high, but there will be cohesion that will likely lead to less complex code.

The second question is whether to use throw

or send

. The second option should be considered here because it is another way for the consumer to signal the generator that something is up. You can think of send

as LBYL to throw

EAFP . This helps provide some intuition about when to use one or the other. It depends on how often you often pass signals between the generator and the consumer. EAFP code that rarely throws exceptions will usually be faster than the corresponding LBYL code. But EAFP code, which often throws exceptions, will be much slower than the corresponding LBYL code. This helps explain why Python iterators are used StopIterator

instead of tests: in the vast majority of casesStopIterator

will only be thrown out once! Thus, the cost of that catch and toss becomes a fixed overhead that is quickly overwhelmed by other performance bottlenecks.

This means that if the use is IgnoreSubtree

infrequent (more like using Python StopIterator

), then you can probably use throw

. Otherwise, consider using send

.