System and method for validating hierarchically-organized messages

• US 7,464,331 B2
• Filed: 08/18/2003
• Issued: 12/09/2008
• Est. Priority Date: 08/18/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Janakiraman, Mathrubootham, Patch, Raymond Robert
• Primary Examiner(s): Vaughn; Gregory J.
• Application Number:
  US10/643,031
• Publication Number:
  US 20050044093A1
• Time in Patent Office: 1,940 Days
• Field of Search: 715/500, 715/509, 715/513, 715/514, 715/526, 715/200, 715/217, 715/234, 715/237, 715/273
• US Class Current: 715/237
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/226 Validation

Abstract

A mechanism for validating a message, such as an XML message or other hierarchically-organized content. A validation engine walks through the tree represented by the message preferably in depth-first traversal order. Upon encountering each node in the tree, the validation engine consults a validation table to identify a delegate that is to be invoked. The validation engine then invokes the delegate identified for that node, and calls itself recursively on the subtrees of the current node. After the subtrees have been processed, the validation engine again consults the validation table to identify a post-handler for the current node, and then invokes the post-handler. An entry in the validation table may be flagged as “exclusive” to prevent traversal of subtrees of the node corresponding to that entry. Additionally, there may be both global and local validation tables, where the global table is used when a node has no entry in the local table.

Claims

1. A computer-readable storage medium encoded with computer-executable instructions to perform a method of validating text content structured into a plurality of elements comprised of markup and the content, which is delimited by the mark, the method comprising:

encountering as part of a depth-first traversal order for encountering the plurality of elements, a first element of the plurality of elements;

consulting one or more validation tables to identify, from among a plurality of validation delegates, a first delegate that corresponds to said first element, the one or more validation tables not being schema that describe valid syntax or structure of said text content, the one or more validation tables including a local validation table and a global validation table, the one or more validation tables including for each element listed in said one or more validation tables, a flag indicating whether subtrees of a given element are to be traversed;

determining that the flag corresponding to said first element indicates that subtrees of said first element are to be traversed;

executing said first delegate with the content of the first element to determine whether the content in the first element is valid;

encountering as part of the depth-first traversal order for encountering the plurality of elements, a second element that is a root of a subtree of said first element;

consulting the one or more validation tables to identify, from among the plurality of validation delegates, a second delegate; and

executing said second delegate with the content of the second element to determine whether the content in the second element is valid,

wherein at least one of said first delegate or said second delegate determines whether the content of the element to which it is applied is valid based on at least one non-syntactic condition of the corresponding content.

2. The computer-readable storage medium of claim 1, further comprising:

prior to consulting said one or more validation tables, determining that at least one of the one or more validation tables contains no delegate that corresponds to said first element.

3. The computer-readable storage medium of claim 1, wherein said act of executing said first delegate is performed prior to said act of encountering said second element, and wherein the method further comprises:

subsequent to executing said second delegate, consulting said first validation table to identify a third delegate that corresponds to said first element; and

executing said third delegate with the content of said first element.

4. The computer-readable storage medium of claim 1, wherein a validation engine is used for validating the text content, the method further comprising:

specifying a third delegate as an exclusive delegate whereby the exclusive delegate has exclusive control over validating a specific node and subtrees of the specific node and wherein the validation engine is inhibited from traversing the node and the subtrees of the specific node.

5. The computer-readable storage medium of claim 1, wherein the local table is consulted prior to consulting the global table.

6. The computer-readable storage medium of claim 1, wherein said method further comprises:

determining that the flag corresponding to said second element indicates that subtrees of said second element are not to be traversed; and

applying said second delegate to said second element without traversing subtrees of said second element.

7. The computer-readable storage medium of claim 1, wherein said first delegate and said second delegate each comprise interpretable code.

8. The computer-readable storage medium of claim 1, wherein the method further comprises:

determining whether the text content is valid based on execution of delegates with the text content in accordance with said one or more validation tables.

9. A method of validating text content structured into a plurality of elements comprised of markup and the content, which is delimited by the markup, comprising:

creating one or more validation delegates, each validation delegate being adapted to determine whether a particular type of element of the text is valid, the one or more validation delegates including an exclusive delegate having exclusive control over validating a specific node and subtrees of the specific node;

creating a local validation table that specifies validation delegates specific to a particular class of text; and

applying a validation engine to the text, wherein the validation engine, for each of the elements, consults said local validation table to identify, from among the validation delegates specified by the table, a validation delegate to be executed with the element, and executes the identified validation delegate with the content of the element,

wherein at least one of the validation delegates determines whether the content of the element with which it is executed is valid based on at least one non-syntactic condition of the content of the element.

10. The method of claim 9, further comprising:

creating a global validation table that specifies validation delegates that apply to a broad category of text classes, wherein the validation engine consults the local validation table and, if there is an entry for a given type of element, executes the validation delegate specified by the local validation table, and otherwise executes the validation delegate specified by the global validation table.

11. The method of claim 9, wherein the local validation table specifies first and second validation delegates for each type of element of the text content, and wherein the validation engine executes the first validation delegate to the element when the element is encountered, and executes the second validation delegate to the element after the first validation delegate, and the validation delegates applicable to any subtrees of the element, have been executed.

12. The method of claim 9, wherein said text content is organized in the form of a tree, each element of the text content corresponding to a node in the tree.

13. The method of claim 9, wherein said local validation table specifies, for each type of element in the text content, a flag indicating whether the validation delegates for subtrees of said type of element are to be applied to said subtrees.

14. The method of claim 9, wherein each of said validation delegates comprises interpretable code.

15. The method of claim 9, wherein at least one of the validation delegates comprises a null delegate.

16. A computer-readable storage medium having stored thereon a data structure comprising:

a plurality of element names, each element name identifying an element within text content that is structured into a plurality of elements comprised of markup and the content, which is delimited by the markup; and

for each element name, a corresponding name of a first delegate, each first delegate comprising code that determines whether the element that corresponds to the element name is valid, wherein the first delegate determines whether the element that it is called upon to validate is valid based on at least one non-syntactic condition of the content that corresponds to that element;

for each element name, a corresponding name of a second delegate, each second delegate comprising code that executes after the first delegate corresponding to the element name, and any delegates corresponding to a subtree of the element that corresponds to the element name, have been run; and

for each element name, a flag indicating whether the first delegate corresponding to the element name is to be applied exclusively to the element corresponding to the element name and to any subtree thereof.

17. A system for validating text content that comprises a plurality of elements that comprise markup and content, the text content being organized in the form of a tree, the system comprising:

a computer-readable storage medium containing a first validation table indicating a plurality of delegates, each delegate corresponding to a name of an element in the tree, wherein at least one of the plurality of delegates is an exclusive delegate having exclusive control over validating a specific node and subtrees of the specific node; and

the computer-readable storage medium further containing a validation engine configured to traverse the tree and, for each element encountered in the traversal of the tree, consult the first validation table to identify one of the plurality of delegates that is to be executed with the encountered element, and to execute the identified delegate by invoking the delegate,

wherein at least one of the plurality of delegates determines whether the element with which it is executed is valid based on at least one non-syntactic condition.

18. The system of claim 17, further comprising:

a second validation table contained in the computer-readable storage medium, the second validation table indicating a plurality of delegates, each delegate corresponding to a name of an element in the tree,

wherein the validation engine is further configured to, for each element encountered in the traversal of the tree, consult the second validation table to determine whether there is an entry for the encountered element, use the entry if the entry is present, and consult the first validation table if the second validation table contains no entry corresponding to the encountered element.

19. The system of claim 17, wherein the first validation table identifies a post-handling delegate for at least some of the elements in the tree, the post-handling delegate being invoked after the delegate for the element, and the delegates for the element'"'"'s subtrees, have been invoked.

20. The system of claim 17, wherein the first validation table indicates, for a first one of the encountered elements, that the delegate identified by the first validation table for said first one of the encountered elements is to be applied to a subtree rooted at said first one of the encountered elements, and wherein the validation delegate identified for said first one of the elements by said first validation table is given exclusive control over said first one of the elements and any subtree of said first one of the elements.

21. The system of claim 17, wherein each of the delegates comprises interpretable code.

22. A computer readable storage medium storing a validation engine that performs a process, the process performed by the validation engine comprising:

traversing a structured document to visit elements of the structured document, the elements comprising markup and content that is delimited by the markup, where the markup conforms to a markup language, and where the elements are of various element types; and

checking the types of the respective elements when the validation engine visits the elements for validation and using the types to determine which executable validation delegates to execute to validate the contents of the respective elements, where the determining is performed according to mapping information that maps the executable validation delegates to corresponding element types, and where the mapping information can be modified to cause the same validation engine, without modification, to modify which executable validation delegates the validation engine selects for which corresponding element types, the determining further comprising examination of the condition of a flag contained in the mapping information for indicating whether the subtrees of a given element are to be traversed.

23. A computer readable storage medium storing a validation engine according to claim 22, wherein the executable validation delegates validate that the content satisfies non-syntactic conditions.

24. A computer readable storage medium storing a validation engine according to claim 22, wherein the traversing is recursive and the content of at least one element is determined to be valid or not based on a delegate selected for the at least one element and based on another delegate selected for an element in a sub-tree of the at least one element.