System and method for validating hierarchically-organized messages

• US 20050044093A1
• Filed: 08/18/2003
• Published: 02/24/2005
• Est. Priority Date: 08/18/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Janakiraman, Mathrubootham, Patch, Raymond Robert
• Granted Patent: US 7,464,331 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 medium encoded with computer-executable instructions to perform a method of validating a message comprising:

encountering a first element of the message;

consulting a first validation table to identify a first delegate that corresponds to said first element;

applying said first delegate to said first element;

encountering a second element that is a root of a subtree of said first element; and

applying a second delegate to said second element in accordance with said first validation table.

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

prior to consulting said first validation table, determining that a second validation table contains no delegate that corresponds to said first element.

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

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

applying said third delegate to said first element.

4. The computer-readable medium of claim 1, wherein said first validation table includes, for each element listed in said first validation table, a flag indicating whether subtrees of a given element are to be traversed, and wherein the method further comprises:

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

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

selecting, according to a criterion, said first validation table from among a plurality of validation tables, the selected validation table being the table that is consulted to identify delegates to be applied.

6. The computer-readable medium of claim 1, wherein said first delegate makes at least one decision based on an element that is nether said first element nor a subtree of said first element.

7. The computer-readable medium of claim 1, wherein the message comprises extensible Markup Language (XML) content.

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

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

determining whether the message is valid based on application of delegates to the message in accordance with one or more validation tables including said first validation table.

10. A method of validating of a message comprising:

creating one or more validation delegates, each validation delegate being adapted to validate a particular type of element of the message;

creating a first validation table that specifies at least one of the validation delegates for each type of element of the message; and

applying a validation engine to the message, wherein the validation engine, for each element of the message, consults said first validation table to identify a validation delegate to be applied to the element, and applies the identified validation delegate to the element.

11. The method of claim 10, further comprising:

creating a second validation table that specifies a validation delegate for each type of element of the message,

wherein the validation engine consults the second validation table and, if there is an entry for a given type of element, applies the validation delegate specified by the second validation table, and otherwise applies the validation delegate specified by the first validation table.

12. The method of claim 10, wherein the first validation table specifies first and second validation delegates for each type of element of the message, and wherein the validation engine applies the first validation delegate to the element when the element is encountered, and applies 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 applied.

13. The method of claim 10, wherein the message comprises extensible Markup Language (XML) content.

14. The method of claim 10, wherein said message is organized in the form of a tree, each element of the message corresponding to a node in the tree.

15. The method of claim 10, wherein said first validation table specifies, for each type of element in the message, a flag indicating whether the validation delegates for subtrees of said type of element are to be applied to said subtrees.

16. The method of claim 10, wherein each of said validation delegates comprises interpretable code.

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

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

a plurality of element names, each element name identifying a portion of a message; and

for each element name, a corresponding name of a first delegate, each first delegate comprising code that validates the element of the message that corresponds to the element name.

19. The computer-readable medium of claim 18, wherein the data structure further comprises:

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.

20. The computer-readable medium of claim 18, wherein the data structure further comprises:

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.

21. A system for validating a message organized in the form of a tree, the system comprising:

a first validation table indicating a plurality of delegates, each delegate corresponding to a name of an element in the tree;

a validation engine that traverses the tree and, for each element encountered in the traversal of the tree, consults the first validation table to identify one of the plurality of delegates that is to be applied to the encountered element, and that applies the identified delegate by invoking the delegate.

22. The system of claim 21, further comprising:

a second validation table indicating a plurality of delegates, each delegate corresponding to a name of an element in the tree;

wherein the validation engine, for each element encountered in the traversal of the tree, consults the second validation table to determine whether there is an entry for the encountered element, the validation engine using the entry for the encountered element in the second validation table if there is such an entry, the validation engine consulting the first validation table if the second validation table contains no entry corresponding to the encountered element.

23. The system of claim 21, 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.

24. The system of claim 21, wherein the message comprises extensible Markup Language (XML) content.

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