PugXML - A Small, Pugnacious XML Parser

• Download source files - 29 Kb
• Download demo project - 43 Kb
• Download manual (.chm format) - 256 Kb

Introduction

Presented is a small, fast, non-validating DOM XML parser, contained in a single header, having no dependencies other than the standard C libraries, and <iostream> (KERNEL32.DLL with WIN32). This XML parser segments a given string in situ (like strtok), performing scanning/tokenization, and parsing in a single pass. Preliminary analysis shows a best-case of 22 X86 CPU clock cycles average per input byte, and a worst-case of 108 CPU cycles, for an executable built using VC7 with the /Og /Ob2 /Oi /Ot /Oy compiler optimization flags. This may be further improved by modifying the parser to discard comments, processing instruction (PI), DOCTYPE, and CDATA sections, as well as using faster memory management routines, (notice how the Microsoft malloc, realloc and free implementations seem to be rather slow).

Why Write Another XML Parser?

Of the many XML parsers available, most present significant concerns, such as complexity, size, portability, etc. It is no small task to correctly implement XML-reading capabilities in a C or C++ application. Of the C, C++ and COM implementations one must gain familiarity with, and work with a large set of functions, structures, and/or classes. In addition, the basic function of many of these implementations is opaque, or obscured by a hairy call graph, so implementation-specific modification or optimization is not realistically possible.

As the use of XML gains ground in diverse industries, year after year, one finds people doing all kinds of bizarre things with XML that were perhaps never intended by the original working group (see for example: HumanML, XML markup for human emotions, etc.; and SuperX++, an XML-based programming language). The bottom line is that these diverse needs are not best met by one 'universal' XML parsing solution, but occasionally the requirements may indicate a customized approach.

The implementation presented here served as a study model for an XML-parsing algorithm that was later rewritten in assembly, for an embedded implementation. The intention here was to develop a lightweight, fully transparent XML parser, from which the essential process of parsing XML markup could be examined, and then pared down as needed. The source code and description may be used for didactic purposes, as a drop-in solution for light-weight DOM-style XML parsing in your own application, or may be used as a model or starting point for developing your own custom parser.

Approach

The PugXML parser performs string scanning, tokenization, parsing, and construction of the document tree structure in a single pass. A common approach in designing a parser would be to scan and tokenize the string in an initial pass, build the parse tree structure in the next pass, then validate in additional passes. While this approach has many advantages in terms of simplicity of implementation, error detection/tolerance/recovery, etc., it can easily result in a larger, slower, more opaque implementation, as the construction and maintenance of a token table requires additional memory and instruction steps. Eliminating the use of the tokenization pass, while significantly smaller, and faster, results in code that can be difficult to follow, as some goto statements are needed.

In our approach we avoid traversing the tree as it is being built, in order to improve performance, although this has certain drawbacks. The XML format is cleverly designed with redundancy and error-correction features. In developing a single-pass XML parser we rely heavily on these in order to minimize look-ahead and look-back scanning of the input string. A brief examination of the nature of XML markup will permit us to address this approach in further detail. The structure of an XML document is that of a tree, where each tree node or branch may have certain associated data. In our implementation, each branch may be one of the following standalone or hierarchical types:

Standalone Types

1.)  <!ATTLIST ...>
2.)  <!ELEMENT ...>
3.)  <!ENTITY ...>
4.)  <!NOTATION ...>
5.)  <?name ... ?>
6.)  <name ... />
7.)  <!--text-->
8.)  <![CDATA[text]]>
9.)  <![INCLUDE[text]]>
10.) text	

Hierarchical

11.)  <!DOCTYPE [...]>
12.) <name ...>...</name>

Representation

All branches, and their attributes are represented using the structures:

• XMLATTR is a name=value attribute structure. The *_insitu (in situ) flags keep track of whether the string is a segment of the original parse string (this helps with garbage collection).
• XMLENTITY specifies the kind of branch, as in the above discussion of "standalone" and "hierarchical" types.
• XMLBRANCH is a the branch itself, which may have zero or more attributes (pointers to XMLATTR structures), zero or more children (pointers to XMLBRANCH structures), an element name, data, and a classification. The *_space scalars keep track of how much pointer space is available in the array.

During the parsing process we maintain a cursor to our current branch (like a stack). Upon hitting a standalone region, we just append a new branch as a child of the cursor branch. Upon hitting an hierarchical region, we append a new branch as a child of the cursor branch, then set our cursor to this new branch (like a stack push). On leaving a hierarchical region (e.g. '</name>'), we set our cursor to its parent (like a stack pop). To save time, and avoid traversing the tree as we build it (such as verifying that we are popping the right branch), we ignore the end-tag name (e.g. '</name>'), and just step to the parent of the current branch. This should be OK if the document is well-formed, but may cause problems otherwise (for example, parsing HTML). Using this approach, the following malformed structure:

<example>
	<foo>Oops!</bar>
	<bar>Ouch!</foo>
	<strange>Huh?</>
	<goo><gaa></goo></gaa>
</example>

would parse as:

<example>
        <foo>Oops!</foo>
        <bar>Ouch!</bar>
        <strange>Huh?</strange>
        <goo><gaa /></goo>
</example>

This seems a half-way usable interpretation, however parsers checking for well-formedness would choke on it. Because this is not compliant behavior, the PugXML parser, and parsers taking a similar approach would be indicated for situations requiring the parsing of machine-generated, well-formed fully-compliant XML documents, and not human-generated documents. See W3C Compliance below.

The Inner Loop

In developing the PugXML parser, the intention was to try to condense everything into a single function with a single loop, removing all non-essential operations (within a reasonable margin). The PugXML parser inner loop may be understood most easily using the finite state machine (FSM) formalism, as depicted in the simplified diagram below. The parser functions as a giant while() loop on the condition that a string zero-terminator is not hit. Within this loop a number of states are possible. Depending upon the current state:

• A new node is appended to the current node's list of children and the cursor is moved to this position (::GraftBranch()).
• A new attribute is appended to the current node's list of attributes (::AddAttribute()).
• The starting position of a string segment is stored in the current context (e.g. a node or attribute), then the end position is located and zero-terminated.
• The cursor is moved to the current node's parent (pCursor = pCursor->parent).
• Any time we hit a sequence we don't like, we continue, in which case we obliviously gobble up the string until we enter another valid segment. Note: if the document is very badly formed, we may end up rejecting the entire input.

Each vertex in the diagram below represents a character, or set of characters we expect to encounter (see the inline static BOOL Is*(TCHAR c) member functions of the CPugXmlParser class). Edges between vertices represent control flow as each successive character, or classified segment of characters is matched. The stippled arrows signify that you can get to the indicated vertex from just about anywhere.

String Segmentation Process

Below is a graphical depiction and narration of the incremental string segmentation process for a sample XML string, with reference to the above diagram. Each numbered rectangle represents the state of the input string as the parsing proceeds.

For the following string:

<example version="1.0">Text</example>

segmentation would proceed:

such that, at:

1. A '<', then a symbol char is hit (see ::IsSymbol()) so we are now in the '<#' state. A new node is grafted onto the tree (pCursor= ::GraftBranch()). The position is stored in the LPTSTR XMLBRANCH::name member.
2. Whitespace is hit, so the parser is now in the '<#_' state. The character at this offset is set to null. We expect to hit an attribute, but we could just as well hit a '/' or a '>'.
3. A symbol char is hit so we assume an attribute ('<#_#') state. An attribute is appended to the XMLATTR** XMLBRANCH::attribute member. The string position is stored in the attribute char* XMLATTR::name member.
4. We scan ahead for a '=', ' ', '/', or '>'. Finding an '=', we expect attribute data to follow.
5. Finding a '"', we remember this quote character, then store the next character position in the LPTSTR XMLATTR::value member of the current attribute.
6. We now scan ahead until we hit the terminating '"', then mark it as null.
7. We have hit a '>', and there is following non-whitespace data so we graft a new node onto the tree (pCursor= ::GraftBranch()), store the following position in the LPTSTR XMLBRANCH::data member, then restore the cursor to the current node's parent (pCursor = pCursor->parent).
8. We now search ahead for a '<', then mark it as null, terminating the PCDATA segment. Finding a following '/', we are in a '</' state, so we step to the current node's parent (pCursor = pCursor->parent).

resulting in the document tree:

Usage

First and foremost, because the generated document tree structure is directly indexed to the input string, you must ensure that the input string will exist for as long as you wish to traverse the tree. In addition, the string is altered by the parsing process (it is zero-terminated for every element name, attribute name, PCDATA section, etc.), so you cannot expect to use it for anything after the parsing pass is completed. If you want to alter any string segment (e.g. element name, attribute value, etc.) the wrapper class, CPugXmlBranch , will allocate memory for that segment if the resulting string will not fit in the existing space. This can result in greater memory use.

Following is a listing for a minimal application using the GnatXMLParser. Note: See the demo project for more extensive examples.

#include <iostream>
#include "pugxml.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	if(argc < 2) return 0; //Expect a filename argument.
	CPugXmlParser* pXml = new CPugXmlParser(); //Construct.
	pXml->ParseFile(argv[1]); //Parse the file.
	cout << pXml->GetRoot() << endl; //Output the resulting tree.
	delete pXml; //Destruct.
	return 0;
}

Classes (Note: See also 'pugxml.h' or the provided manual)

The PugXML parser uses only a limited set of classes, the methods of which are all implemented inline in order to shoehorn everything into a single header. The classes you need mainly be concerned with are CPugXmlParser, which provides an interface to the underlying parser function (static LPTSTR CPugXmlParser::Parse()), and CPugXmlBranch, which provides a lightweight interface to the generated document tree. If you would like to minimize code size, cut & paste the inline functions to a new .cpp file, and remove the inline declarations. If you would like to use the basic parsing facility in a C project, dispense with the classes, and copy the static member functions of CPugXmlParser, the defines, enums, structures, and the global functions, NewAttribute(), NewBranch(), GraftBranch(), AddAttribute(), and FreeTree() to your C implementation file. The entire implementation uses only the following externs, so it should be relatively easy to port:

• malloc, memset, realloc, free, memcpy.
• strlen, isalnum, strncpy (or their wide equivalents via <wtypes.h> and <tchar.h>).
• strtol, strtod, strtok, strcpy (ditto, for CPugXmlBranch).
• CreateFile, ReadFile, CloseHandle, ZeroMemory (for CPugXmlParser::ReadFileData(), could as easily be fopen, fread, fclose).
• ostream (for CPugXmlBranch::Serialize() - wanton profligacy: who needs streams, when you have handles!).

BOOL IsDTD()<br>
							BOOL IsDTD_ATTLIST()<br>
							BOOL IsDTD_ELEMENT()<br>
							BOOL IsDTD_ENTITY()<br>
							BOOL IsDTD_NOTATION()

Performance

Note: For all performance tests, the parser was configured with following flags set: (PARSE_PI|PARSE_DOCTYPE|PARSE_COMMENTS|PARSE_CDATA|PARSE_DTD).

Operating Efficiency

The CCPUTicker class by J.M. McGuiness and P.J. Naughter was used to measure the elapsed count of non-exclusive Pentium clock cycles for the static Parse inner loop. This value was divided by the count input bytes. In this summary test, a set of seven well-formed XML documents were parsed, representing a random mix of sizes, features and complexity. Following is a table of these measurements, and two plots, Input Bytes/Elapsed CPU Cycles (c_n-c₀), and Input Bytes/Elapsed Milliseconds (t_n-t₀).

Note: See Test Platform below for the test platform specs.

An identical test performed using the MSXML 4.0, and .NET parsers showed a 4.5X increase in elapsed milliseconds.

Memory Overhead

In an additional test, the parser's memory overhead was measured as a function of input bytes, and peak memory usage. This gains cogency in the context of the input data markup-to-data ratio. In the table below, 'Saturated' markup refers to markup that has a high markup-to-data ratio, e.g.:

<a><b><c><d><e/></d></c></a></a>

<a b="b" c="c" d="d" e="e">f</a>

'Sparse' markup refers to the opposite, e.g.:

<aaaaaaaaaaaaaaaaaaaaaaaaaaaaa/>

<a>bbbbbbbbbbbbbbbbbbbbbbbbb</a>

and, 'Mixed' markup would be somewhere in between.

As you can see, 'Saturated' markup has the highest memory overhead (understandably, since the parser must allocate many more XMLBRANCH or XMLATTR structures). Although it is not implemented in PugXML, it should be possible to take a random sampling of the input string by counting the markup character to data character ratio, and thereby estimate both memory overhead, and knowing the input string length, peak memory usage. This might prove useful for embedded implementations where one would desire to know a priori whether the potential document tree could fit into memory.

An identical test performed using the MSXML 4.0, and .NET parsers showed a memory overhead of approximately 3.5X that of the PugXML parser.

Interpretation

OK, so the PugXML parser is comparatively fast, and doesn't use absurd amounts of memory, but what does this really mean? By analogy, if you took your average gas guzzling SUV (MSXML 4.0), and stripped everything off the chassis, except for one seat, the steering wheel, and the engine, you could probably get the thing going really fast. The question you have to ask yourself is: would you drive your children to school in such a vehicle? You bet! (Note: For some serious performance in a fully-validating XML parser, take a look at RXP).

Test Platform

OS Name Microsoft Windows 2000
Version 5.0.2195 Service Pack 3, RC 3.136 Build 2195
Processor x86 Family 5 Model 9 Stepping 1 AuthenticAMD ~451 Mhz
Total Physical Memory 261,680 KB
Total Virtual Memory 1,024,820 KB

W3C Compliance

PugXML was designed to perform robust parsing of potentially malformed XML markup, and as such is non-compliant. Using a fully W3C-compliant parser adhering to the strictures of well-formedness, validity, DTDs, XSDs, etc., one often hits a document that simply cannot be parsed with significant manual editing. PugXML never rejects a document. PugXML will parse a wide variety of malformed fragments, and attempt to generate a well-formed document tree. Using the W3C Conformance Test Suite 20020606, PugXML will parse all well-formed (valid) stand-alone documents correctly (without entity expansion). Of the invalid tests, PugXML will, in 99% of the cases yield a well-formed document tree from which one can actually extract some data. Despite not being fully W3C compliant, PugXML could easily be used as a starting point to build a fully compliant parser (although it would be sure to bite you if you tried).

Known Problems

• Entities: Although the DOCTYPE section and subsidiary DTD entities may be parsed using this parser, entities declared therein are not expanded in the document. In addition, build-in entities (e.g. '
') are not expanded however they are retained in whatever name, data or value section, so it would not be difficult to apply them after the document tree is constructed. Alternatively, you could first parse the DTD section, build an entity table, expand instances of the entities in the input string, then parse the input string as normally.
• Character Encodings: Although the parser can be compiled and will run correctly with UNICODE or _MBCS defined, it does not understand character encoding as specified in the XML PI section. If you are attempting to parse a non-standard codepage, the parser may fail, or corrupt the data. Currently the parser will work correctly for UTF-8 (65001), and various flavors of Latin and Western European ISO/ASCII with _MBCS defined, and for UNICODE (1200) with UNICODE defined (but not both in the same build). If your requirements include the need to parse ad-hoc data that may use one or more different codepages, you might consider using another parser.
• Recursion: Some functions such as the traversal helpers, and the static stream output function, CPugXmlBranch::Serialize, are implemented using recursion. In some cases, particularly if you are traversing a very deep tree, and depending on your compiler, you may encounter a stack overflow. It would be relatively easy to make safer non-recursive implementations (see the ::FreeTree function for an example of non-recursive traversal).
• XML Namespaces: The parser does not tokenize '<ns:tag...' or '<... ns:attribute...'. If namespace prefixes are present they will be left as is, as part of the object name, e.g. 'ns:tag' or 'ns:attribute'.

Errata

Since the initial performance measurements, there have been some minor changes made to the static CPugXmlParser::Parse(), NewBranch() and GraftBranch() functions (verification of memory allocation, and the string normalization option). Until new tests can be performed it is hard to say whether or how these changes may impact the overall performance.

History

• 01/15/2003: Bug Fix: A memory exception at CPugXmlParser::~CPugXmlParser(), or CPugXmlParser::Clear(), when parser option PARSE_DTD_ONLY is not set. Note: The source download, but not the demo project, has been updated with this fix.
• 01/10/2003: Initial Release.