This invention relates to methods and apparatus for parsing Extensible Markup Language (XML) data streams.
Extensible Markup Language (XML) is a meta-markup language that provides a format for describing structured data. XML is similar to HTML in that it is a tag-based language. By virtue of its tag-based nature, XML defines a strict tree structure or hierarchy. XML is a derivative of Standard Generalized Markup Language (SGML) that provides a uniform method for describing and exchanging structured data in an open, text-based format. XML utilizes the concepts of elements and namespaces. Compared to HTML, which is a display-oriented markup language, XML is a general-purpose language used to represent structured data without including information that describes how to format the data for display.
XML xe2x80x9celementsxe2x80x9d are structural constructs that consist of a start tag, an end or close tag, and the information or content that is contained between the tags. A xe2x80x9cstart tagxe2x80x9d is formatted as xe2x80x9c less than tagname greater than xe2x80x9d and an xe2x80x9cend tagxe2x80x9d is formatted as xe2x80x9c less than /tagname greater than xe2x80x9d. In an XML document, start and end tags can be nested within other start and end tags. All elements that occur within a particular element must have their start and end tags occur before the end tag of that particular element. This defines a strict tree-like structure. Each element forms a node in this tree, and potentially has xe2x80x9cchildxe2x80x9d or xe2x80x9cbranchxe2x80x9d nodes. The child nodes represent any XML elements that occur between the start and end tags of the xe2x80x9cparentxe2x80x9d node. XML accommodates an infinite number of database schemas. Within each schema, a xe2x80x9cdictionaryxe2x80x9d of element names is defined. The dictionary of element names defined by a schema is referred to as a xe2x80x9cnamespace.xe2x80x9d Within an XML document, element names are qualified by namespace identifiers. When qualified by a namespace identifer, a tag name appears in the form xe2x80x9c[namespace]:[tagname]xe2x80x9d. This model enables the same element name to appear in multiple schemas, or namespaces, and for instances of these duplicate element names to appear in the same XML document without colliding.
Start tags can declare an arbitrary number of xe2x80x9cattributesxe2x80x9d which declare xe2x80x9cproperty valuesxe2x80x9d associated with the element being declared. Attributes are declared within the start tag using the form xe2x80x9c less than [tagname] [attributel],[attribute2] . . . ,[attributeN] greater than xe2x80x9d, where an attribute through attributeN are declarations of an arbitrary number of tag attributes. Each attribute declaration is of the form xe2x80x9c[attributeName]=[attributeValue]xe2x80x9d where each attribute is identified by a unique name followed by an xe2x80x9c=xe2x80x9d character, followed by the value of the attribute.
Within an XML document, namespace declarations occur as attributes of start tags. Namespace declarations are of the form xe2x80x9cxmlns:[prefix]=[uri]xe2x80x9d. A namespace declaration indicates that the XML document contains element names that are defined within a specified namespace or schema. Prefix is an arbitrary designation that will be used later in the XML document as an indication that an element name is a member of the namespace declared by uri. The prefix is valid only within the context of the specific XML document. xe2x80x9cUrixe2x80x9d or universal resource indicator is either a path to a document describing a specific namespace or schema or a globally unique identifier of a specific namespace or schema. Uri is valid across all XML documents. Namespace declarations are xe2x80x9cinheritedxe2x80x9d, which means that a namespace declaration applies to the element in which it was declared as well as to all elements contained within that element.
Namespace inheritance within an XML document allows non-qualified names to use xe2x80x9cdefaultxe2x80x9d namespaces. Default namespaces are explicitly declared as attributes of start tags. Default namespace declarations are of the form xe2x80x9cxmlns=[uri]xe2x80x9d. Note that the declaration of a default namespace is equivalent to the declaration of a non-default namespace but the prefix is omitted A namespace specification within an XML document is said to have a xe2x80x9cscopexe2x80x9d which includes all child nodes beneath the namespace specification.
One exemplary usage of XML is the exchange of data between different entities, such as client and server computers, in the form of requests and responses. A client might generate a request for information or a request for a certain server action, and a server might generate a response to the client that contains the information or confirms whether the certain action has been performed. The contents of these requests and responses are xe2x80x9cXML documentsxe2x80x9d, which are sequences of characters that comply with the specification of XML. Part of the document exchange process between clients and servers involves parsing the XML documents when they are received. In many cases, it is convenient to represent these XML documents in memory as a hierarchical tree structure. Once the hierarchical tree structure is built, the actual parsing process can begin. Consider the following exemplary XML code:
This code includes three XML namespace declarations that are each designated with xe2x80x9cxmlnsxe2x80x9d. The declarations include a prefix, e.g. xe2x80x9cpersonxe2x80x9d, xe2x80x9cdsigxe2x80x9d, and xe2x80x9ctransxe2x80x9d respectively, and the expanded namespace to which each prefix refers, e.g. www.schemas.org/people, dsig.org, and www.schemas.org/transactions respectively. This code tells any reader that if an element name begins with xe2x80x9cdsig:xe2x80x9d its meaning is defined by whoever owns the www.dsig.org namespace. Similarly, elements beginning with the xe2x80x9cperson:xe2x80x9d prefix have meanings defined by the www.schemas.org/people namespace and elements beginning with the xe2x80x9ctransxe2x80x9d prefix have meanings defined by the www.schemas.org/transactions namespace. It is important to note that another XML document that incorporated elements from any of the namespaces included in this sample might declare prefixes that are different from those used in this example. As noted earlier, prefixes are arbitrarily defined by the document author and have meaning only within the context of the specific element of the specific document in which they are declared.
Namespaces ensure that element names do not conflict, and clarify who defined which term. They do not give instructions on how to process the elements. Readers still need to know what the elements mean and decide how to process them. Namespaces simply keep the names straight.
FIG. 1 shows how the structure of the above code can be represented in a hierarchical tree structure. In FIG. 1, all of the elements or nodes are set out in an exemplary tree that represents the XML document. Such a structure is typically constructed in memory, with each node containing all data necessary for the start and end tags of that node.
It has been typical in the past to build the entire tree structure, such as the one shown in FIG. 1, before parsing the XML document. For large XML documents, this can consume a great deal of memory and processor time. Thus, it would be desirable to avoid this process if at all possible.
XML parsers are used to various applications to process XML documents. Parsers must know what particular elements mean and how to process them. Tags from multiple namespaces can be mixed, which is essential with data coming from multiple sources across the Web. With namespaces, both elements could exist in the same XML-based document instance but could refer back to two different schemas, uniquely qualifying their semantics. Parsers typically take the form of a code library that can be used by developers in conjunction with higher level languages such as C++ or Java. Using functions provided by such a code library, developers can access the structure of an XML document, enumerate its elements and their attributes, and manipulate the information that is contained within the document""s prolog. A simple example would be an XML parser utility that checks for xe2x80x9cwell-formedxe2x80x9d or xe2x80x9cvalidxe2x80x9d documents, and serves as the equivalent of an syntax checker.
XML parsers typically read XML files or data streams and construct a hierarchically structured tree, such as the one appearing in FIG. 1, as a data structure in memory. The XML parser then typically hands off this data structure data to viewers and other applications for processing. So, in the example XML code discussed above, a parser would first build the entire tree structure that is shown in FIG. 1 prior to interpreting the contents of the document. Only after the entire tree structure was built in memory would the parser begin to interpret the document.
One problem that is associated with XML parsers such as this is that they have to build an entire hierarchically structured tree in memory before interpreting the contents of the document. This approach is not efficient because of the demands it places on the memory that is required to store the tree structure and the speed with which information can be conveyed to a client. For example, this type of approach is not efficient for an application that is doing work in connection with a large quantity of XML data that might be streaming in at a relatively slow speed. Consider, for example, that a client asks a server for a list of all messages of a certain type that are in a certain folder. The entire message list is going to be returned by the server as one large data stream. If the client has to wait for the entire message list to be returned from the server, then the client cannot begin to display any portion of the list until all of the data has been received. Furthermore, this process requires the parser to make at least two passes over the data; the first pass to build the tree structure, and the second pass to traverse the nodes of the tree to interpret the contents of the document. This approach requires a large memory overhead (for storing the XML data and building the hierarchical tree structure) which, in turn, impacts the speed with which responses can be used by client applications.
This invention arose out of concerns associated with providing improved XML parsers and methods of parsing XML data streams that reduce memory overhead and increase the speed with which XML data can be provided and used by a client
Various features of the invention provide methods and systems for parsing an XML data stream that do not require that an entire hierarchical tree structure be built and stored in memory in conjunction with parsing activities.
Various parsing support structures are defined that enable the inventive parsing activities. An element stack is defined and used as a way to organize parsing activities and maintain a definable place within the structure of an XML data stream as it is received. During parsing activities the element stack grows and shrinks in connection with how deep into an XML data stream the parser goes.
A namespace hierarchy is defined as the XML data stream is received. In one described embodiment, the namespace hierarchy is a collection of namespace objects that each represent a namespace specification that is encountered in the XML data stream. Each object includes a namespace specification and, in the case of non-default namespace, a namespace prefix. Within the hierarchy, namespace objects refer to their parent. The namespace hierarchy is used for mapping a particular encountered namespace specification into a unique value that represents both the namespace specification and an element tag in which the namespace occurs.
A dictionary collection is defined and includes one or more dictionaries. Each dictionary is specifically associated with a namespace specification that is encountered in the XML data stream. The dictionaries contain one or more entries for one or more tag names, and a globally unique token that is associated with each tag name. The token is returned and placed on the element stack, along with another special value that enables the proper state to be maintained during processing of the XML data stream.
When an XML element is encountered, the element stack is used to organize parsing activities as the parser makes its way through the XML data stream. During parsing activities, various notifications are generated by the parser and sent to the client or application when various events occur. Exemplary notifications include, without limitation, those that are sent when: a new tag is encountered, the children of a tag are entered, data is encountered within a tag, and a close tag is encountered. These notifications can be used to organize parsing activities. For example, when notification is received that a new tag has been encountered, the element can be pushed onto the element stack. Similarly, when notification is received that a close tag has been encountered, the top frame can be removed from the element stack.