Of the numerous features recently added to Python, generators truly stand out. Fredrik Lundh, a Python insider well known for wry commentary, put it best: Comparing generators to other recent changes in Python, he said, "Generators [open] a new universe; the rest is more like moving the furniture around." In this tip, I show you how generators can be used to make XML DOM processing with Python even smoother.

Note: In his excellent series on generators in the IBM developerWorks Linux zone (see Resources), David Mertz discusses the basics of generators and some neat applications. If you are not familiar with generators, I recommend that you review at least his first article on the topic. You will need Python 2.2 to use generators.

Smart and fast iterators

Node iterators are a very common design pattern in XML, and are a fixture of DOM. A node iterator visits every node in an XML document in turn, following the standard document order. Node iterators are notorious for being slow and fiddly, but generators in Python offer a wonderfully concise and efficient implementation of node iterators. See Listing 1.

                
		
#Required in Python 2.2, and must be the first import
from __future__ import generators
from xml.dom import Node

def doc_order_iter(node):
    """
    Iterates over each node in document order,
    returning each in turn
    """
    #Document order returns the current node,
    #then each of its children in turn
    yield node
    for child in node.childNodes:
        #Create a generator for each child,
        #Over which to iterate
        for cn in doc_order_iter(child):
            yield cn
    return

#Parse a document then print the Python representation
#of each node object in document order

DOC = """\
<memo xmlns='http://spam.com'>
<date form="iso-8601">2002-08-14</date>
This is just to <strong>say</strong>:
I ate the eggs you left in the fridge
And were probably saving for breakfast.
Do you know?  They were <emph>quite</emph> rotten.
</memo>
"""

from xml.dom import minidom
doc = minidom.parseString(DOC)
for node in doc_order_iter(doc):
    print node

Traversing trees is one of the classic use-cases for generators (such a traversal is the main example in the official specification for Python generators). This means that XML's natural tree structure is very well suited to generator idioms. You can copy the doc_order_iter function to your code and use it any time you need to iterate over a document's nodes (a fairly common requirement in XML processing). The function starts by yielding the given node right away. Remember that this suspends its operation and returns control to the caller. The next time it is called, it initiates a loop over its children. The function recursively sets up a generator for each of its child nodes. This has the effect of traversing down the tree such that each node is visited first, and then each of its children, from left to right. The return at the end signals the complete termination of the generator's operation. The output is shown in Listing 2:

                
	
$ python nodeiter1.py
<xml.dom.minidom.Document instance at 0x8267a1c>
<DOM Element: memo at 136739676>
<DOM Text node "
">
<DOM Element: date at 136742132>
<DOM Text node "2002-08-14">
<DOM Text node "
">
<DOM Text node "This is ju...">
<DOM Element: strong at 136744780>
<DOM Text node "say">
<DOM Text node ":">
<DOM Text node "
">
<DOM Text node "I ate the ...">
<DOM Text node "
">
<DOM Text node "And were p...">
<DOM Text node "
">
<DOM Text node "Do you kno...">
<DOM Element: emph at 136748228>
<DOM Text node "quite">
<DOM Text node " rotten.">
<DOM Text node "
">

Back to top

How about attributes?

doc_order_iter does not iterate over attribute nodes because they are not considered children of their parent nodes in the DOM. It's not likely that you'll need to do a full iteration that includes attributes, but as an illustration, Listing 3 is a function that does so.

                

from xml.dom import Node

def full_doc_order_iter(node):
    """
    Returns each node in document order,
    including attributes, which are visited
    immediately after their element
    """
    yield node
    if node.nodeType == Node.ELEMENT_NODE:
        #Attributes are stored in a dictionary and
        #have no set order.  The values() call
        #gets a list of actual attribute node objects
        #from the dictionary
        for attr in node.attributes.values():
            yield attr
    for child in node.childNodes:
        for cn in full_doc_order_iter(child):
            yield cn
    return

After the given node is yielded, if it is an element node, its attributes are yielded as well (in arbitrary order).

Warning: This function is written as if attribute nodes have no children (and therefore there is no need to spawn a new generator for each attribute node). In the DOM proper, attributes can have one or more children, which must be text nodes. This is something of an oddity and annoyance in the DOM, and in practice, most people treat attributes atomically, even in DOM processing.

Being selective

The iterators presented so far return all the nodes in the document, without discrimination. But sometimes you want to be more selective. You can easily modify these generators to apply a criteria against each node in order to decide whether to return it. Listing 4 shows a function, doc_order_iter_filter, which is a general framework for iterating over all nodes in a document (not including attribute nodes) and returning only those that pass a filter function given to the generator.

                

def doc_order_iter_filter(node, filter_func):
    if filter_func(node):
        yield node
    for child in node.childNodes:
        for cn in doc_order_iter_filter(child, filter_func):
            yield cn
    return

This time a filter function is passed in. This function takes a node object and returns 0 or 1. You can make this function as simple or complex as you please in its selection of nodes. Before yielding the given node, it is checked against the filter function. This check is applied again for each of the values returned from the recursive generators that are spawned.

As an example, Listing 5 uses this framework to generate only the elements in the document.

                

def get_elements(node):
    elem_filter = lambda n: n.nodeType == Node.ELEMENT_NODE
    return doc_order_iter_filter(node, elem_filter)

The filter setup does a simple check of the node type. Then a generator is created and returned, prepped to iterate over all nodes with the given filter applied. It is important to remember that the last line is not an ordinary function call. It creates a generator -- a function in suspended animation, in a way, and the calling code can then treat this return result as an iterator. This iterator, in turn, returns a new, yielded value each time it is called until the generator hits the return statement. This means that the order of control is not typical of procedural languages: In effect, the doc_order_iter_filter generator outlives the function (get_elements) from which it is invoked.

Back to top

Summary

Generators are a true boon to XML processing in Python. I have found myself using them so frequently in XML processing that it's hard for me to imagine how I did without them before. Use generators when you have to perform some operation repeatedly over all or selected nodes in the document. It does not have to be in document order. You can arrange the flow of control however you need to yield the results you require.

Resources

• Read David Mertz's excellent series on Python generators in the Linux zone: "Iterators and simple generators" (developerWorks, September 2001), "Generator-based state machines" (developerWorks, July 2002), and "Implementing 'weightless threads' with Python generators" (developerWorks, June 2002).
  
  
• If you are really serious about understanding generators quickly and deeply, you might want to visit the source: PEP 255 (the formal specification for generators). The main example in this document is tree traversal.
  
  
• Find more XML resources on the developerWorks XML zone. For a complete list of XML tips to date, check out the tips summary page.
  
  
• IBM trial software: Build your next development project with trial software available for download directly from developerWorks.
  
  
• Find out how you can become an IBM Certified Developer in XML and related technologies.
  
  
• Want us to send you useful XML tips like this every week? Sign up for the developerWorks XML Tips newsletter.
  
  

About the author

Uche Ogbuji is a consultant and co-founder of Fourthought Inc., a software vendor and consultancy specializing in XML solutions for enterprise knowledge management. Fourthought develops 4Suite, an open source platform for XML, RDF, and knowledge-management applications. Mr. Ogbuji is a Computer Engineer and writer born in Nigeria, living and working in Boulder, Colorado, USA. You can contact him at uche@ogbuji.net.

Rate this article

Comments

Back to top

Table of contents

• Smart and fast iterators
• How about attributes?
• Summary
• Resources
• About the author
• Comments