March 10, 2009

Enhancing the standard NSXMLParser class

Cocoa offers a "complete" XML parser with the NSXML family of classes. This tree-based parser is fairly sophisticated but it is not included in Cocoa-Touch. In the spirit of small and simple, iPhone developers have the NSXMLParser class to use. This is an event-driven parser, which calls methods on a delegate to handle "events" as it parses through the XML. The basic operation of the NSXMLParser class will not be covered here. This is well documented in the Apple Programming Guide "Introduction to Event-Driven XML Programming Guide for Cocoa". What I would like to introduce is an enhancement to this parser. For very simple XML parsing purposes, NSXMLParser is probably adequate, but it is not going to handle all your XML parsing needs. The biggest problem with this type of streaming parser is that you lose the structure of your data; your call-backs do not provide any context or hierarchy. Thus your parser:didStartElement and parser:foundCharacters methods tend to be very messy with lots of if/else if statements, and you have to keep track of your own context via instance variables.

A better way: a Tree

One solution is to use the parser to build a tree first, then your application can access the tree afterwards. Even the above referenced document alludes to this solution. Below is such a solution, an implementation of the XMLTreeParser and XMLTreeNode classes. The tree that is built uses nodes of type XMLTreeNode. The node is defined this way:
@interface XMLTreeNode : NSObject {
   XMLTreeNode* parent;
   NSString* name;                  // element name
   NSMutableDictionary* attributes;
   NSMutableString* text;           // from foundCharacters()
   NSMutableDictionary* children;   // key is child's element name, value is NSMutableArray of tree nodes
} 
Most of these properties are obvious. The text property is a concatenation of all the free-floating text that were inside an element. For example, the text "Hello World" would be stored in the text property:
<elementName>Hello World</elementName>
The choice of using a dictionary for the children property might be a curious one. The key of the dictionary is an NSString, which is the element name. The value of the dictionary is an NSArray of XMLTreeNode objects. To illustrate, here is some sample XML:
<stuff>
<item attr="value1"/>
<item attr="value2"/>
<note>TEXT</note>
</stuff>
Parsing this would create a root node with one child whose name is "stuff". The "stuff" node has two entries in its children dictionary: one entry for "item" and one for "note". The value for these entries is an NSArray of XMLTreeNode objects. The "item" array will have two nodes, and the "note" array will have only one. The use of a dictionary allows us to quickly search for children, as we'll see later. The downside of this is that the order of the "item" and "note" child nodes for "stuff" will not be retained. This is a side-effect of dictionaries not preserving the order. However, proper XML should not care about the order of the elements, only that the hierarchy is correct. I should note that the order of children of the same element is preserved. For example, when you query the tree, you have no idea if the "item" children will come before the "next" child or not. What you do know, though, is that you will get the item with "value1" before the item with "value2". This is important for the indexing scheme described below.

Building the tree

To create a parser, simply instantiate the XMLTreeParser class:
XMLTreeParser* parser = [[XMLTreeParser alloc] init];
This is a very simple implementation, so as it currently stands, an instance can only parse one XML input. There is no way to reuse a parser instance to parse some other XML. But that would be an easy exercise for the reader to address. Now to start parsing, call the parse method and provide the XML data:
XMLTreeNode* root = [parser parse:xmlData];
Again, this simple implementation only handles XML passed directly to it, not indirectly through a filename. When this returns, your XML has been completely parsed. The beautiful part is you don't have to write all those event handlers. What you get back is the root node of the tree. This node does not have any useful data other than its children. This return will be nil if there is any problem parsing the supplied XML.

Querying the tree

Now you could traverse through the tree manually looking for things. A good demonstration of how to do this is in the XMLTreeNode method "description". This method will recreate the XML from the tree; unparse it, if you will. It will dump out the element name and any attributes. Then it will iterate over all the children and recursively call description on all of them. Please take a look at the implementation of -(NSString*) description in the XMLTreeNode class to see this. For simpler queries, the XMLTreeNode class offers methods to find child nodes. These are the find* methods.

Do you know where your children are?

The most basic find method is findChildren. This simply returns an array of children that match the given element name. Referring back to the simple XML above, the statements below will pull out a list of XMLTreeNodes for the "item" elements:
NSArray* stuffs = [root findChildren:@"stuff"];
XMLTreeNode* stuff = [stuffs objectAtIndex:0];
NSArray* items = [stuff findChildren:@"item"];
OK, this is great, but a little cumbersome. If you know that there is only one "stuff" element, it's a shame you have to get back an array of them. So there is the findChild method, which returns a single XMLTreeNode object:
XMLTreeNode stuff = [root findChild:@"stuff"];
What if there are more than one "stuff" elements? This version of findChild: always takes the first element in the array. If you want a different element, you must use findChild:at:
XMLTreeNode* item2 = [stuff findChild:@"item" at:1];
This will return the second "item" node.

Getting deeper

Pretty cool, but this is still a little cumbersome. What if you have XML with elements 10 layers deep? That means at least 10 separate calls to findChild:. The findChild: method supports paths. Here is an example to get the first "item" node in one call:
XMLTreeNode* item1 = [root findChild:@"stuff/item"];
This basically combines two searches into 1. Now, for your 10-deep XML, you could use something like this:
XMLTreeNode* deep = [root findChild:@"stuff/items/item/something/lists/list/test"];
That's 7 searches in 1.

Pinpoint accuracy

Note that for every step through the path in the above example, if there are more than one element with the same name, this will traverse the first one. If you want a different element besides the first one, then you would have to fall back on the single-step findChild:at: method. Or, you can specify an index:
// I want the 3rd doodad in the 4th thingamajig of the 2nd whatchacallit
XMLTreeNode* doodad3 = [root findChild:@"whatchacallit[1]/thingamajig[3]/doodad[2]"];
Remember that these indeces are 0-based, so they are one less than what you'd expect. Now you can dig around in your XML to your heart's content. Be aware that if the query fails anywhere along the path, it will return nil. So if you get nil back from a find method, you can assume that it didn't find what you were looking for.

Optmization

If you find yourself traversing over the same ground over and over, you can move your starting point. There is no need to always start at the root node. Each node has these find methods, so you can get a new starting point and search from there:
XMLTreeNode* searchRoot = [root findChild:@"stuff/same/old/path"];
XMLTreeNode* newThing = [searchRoot findChild:@"cool/new/thing"];
Think of this as changing your current directory so you don't always have to type in the full path.

Room for improvement

That's it for now. This simple implementation could have a lot more features added. For instance, you could pluck out attributes from a path like this:
NSString* value = [root findChildAttr:@"stuff/item[1].value"];
This would get the attribute "value" from the second "item" element under "stuff". But what it does now is all that was required for my current project. Other enhancements could follow as the needs arise.

Download

You can access the source code to XMLTreeParser and XMLTreeNode here.

17 comments:

  1. Thanks for sharing! I've been trying to write a generic unknown xml parser but as you said, I kept getting lost with all the case statements in the didEndElement delegate method.

    Using a tree approach gives me half the solution I need. My goal is to display my xml in an UITableView. The UITableView must build itself based on the xml (sections, section titles, cell.textlabels...). How would you suggest using XMLTreeNode to create: An initial array (*tablexml), where if I [tablexml count] it will return the number of sections, where each "section" is its own NSMutableArray, and each "item" is a NSDictionary. If I've made myself clear, I hope to have one array holding sections, and the sections array holding dictionaries, where each dictionary is an item in the section.

    Thanks in advance for any help, I hope I'm just missing something simple. Again, thank you for posting your experience with NSXML parser and helping others find a useful solution to parsing larger XML files!

    Example XML file for building a UITableView:
    http://dl.dropbox.com/u/5367983/XMLExample.txt

    ReplyDelete
  2. I think this is pretty straightforward. You can get an array of all the child nodes of with something like this:

    XMLTreeNode* table_data = [root findChild:@"table_data"];

    NSArray* sections = [table_data findChildren:@"section"];

    ReplyDelete
  3. Thanks for sharing! I used your XMLTreeParser. It is easy to use and it works great. I add a short example application, showing how to parse a Web Service using XMLTreeParser (http://mentormate.com/blog/iphone-application-development-xml-parser-parsing-libraries/).

    ReplyDelete
  4. I have a question about your XMLTreeParser class if you have a second - I'm trying to use it in a project that parses some fairly large XML files, and the parser seems to be allocating memory somewhere that never gets freed.

    If I simplify my parse module down to just this:

    NSData *xmlData = [[NSData alloc] initWithContentsOfFile:xmlFile];

    XMLTreeParser *parser = [[XMLTreeParser alloc] init];
    XMLTreeNode *root = [parser parse:xmlData];
    [parser release];
    [xmlData release];

    and I run with instruments in this simplified form, I can see about 250k (roughly the size of my xml file) getting allocated each time I call this, but it never gets freed up. Any ideas?

    I noticed in your code there is one place where you alloc a NSMutableDictionary and you have a comment that says "// this will retain twice, so release one of the reference counts" and then you release it. This seems odd to me (why does it retain twice??), and I'm wondering if maybe there is someplace else where this is happening too.

    Aside from that, your class is great - saved me a lot of work dealing with Apple's wacky event-driven parser. But the memory problem is a show-stopper for me, because I need call this repeatedly, and I run out of memory after awhile.

    Thanks for any help you can give me.

    ReplyDelete
  5. I believe I found and fixed some memory leaks in the XMLTreeParser class not long ago. I will check tonight and update the code.

    ReplyDelete
  6. There was a memory leak (one missing release), and I have uploaded a newer version of the XML Tree parser. Unfortunately, the Google Group I had this code hosted on has been down for several days, so I posted the new code on the Osmorphis web site: http://sites.google.com/site/osmorphis/xmltree.zip?attredirects=0&d=1

    To answer your question about the comment of "will retain twice": The alloc/init combo will retain the object once, then the assignment to the property will retain it again, because the property was created with the "retain" attribute. I could have simply assigned to the ivar instead of the property, but I don't know which is better. Property usage is still something I'm trying to get comfortable with.

    ReplyDelete
  7. Awesome - I'll try the new version. Thanks again for a great and useful "no frills" parser.

    ReplyDelete
  8. Hmm. This code appears to not maintain the order of elements and that will break things for people. Why not put the elements in an array and have a node at each array position?

    While XML does not guarantee that element order is maintained, there is so much code out there that assumes it is that anything that doesn't will cause failures.

    ReplyDelete
  9. Maintaining order was not a requirement when I designed this, nor do I see it as an important feature. If you need guaranteed element order, this is not the package for you.

    ReplyDelete
  10. I have to say i have just implemented your code and wow it saved me hours of work, keep up the good work

    ReplyDelete
  11. Just a quick question..
    Can this be used to write back to the XML? Can you give some ideas in that direction?

    Thanks in advance!

    ReplyDelete
  12. Nope, this is for reading XML only. It's hard for me to even think why you would want to write XML on iOS. There are several other ways to persist hierarchical data that does not involve XML. JSON, plists, etc.

    ReplyDelete
  13. I want to use your XMLTreeParser code in our commercial project. It seems from the discussion on this page that the code is meant to be used freely, but the source code files says it is "Copyright 2009 Osmorphis. All rights reserved." This means I legally cant use it. Have you considered putting it under MIT or similar license instead?

    ReplyDelete
  14. You can use the code freely.

    ReplyDelete
  15. Thanks! The code works perfectly!

    ReplyDelete
  16. Thanks for taking time to post this. Even though it has been posted some time ago. It is still very useful for me. Nice share..

    ReplyDelete
  17. thanks for posting this code works perfectly

    ReplyDelete