System and method for an improved type inference

• US 20060242115A1
• Filed: 04/25/2005
• Published: 10/26/2006
• Est. Priority Date: 04/25/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cseri, Istvan, Rys, Michael, Seeliger, Oliver N., Kukol, Peter, Baras, Adrian S.
• Granted Patent: US 7,426,503 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 8/437 Type checking

Abstract

An improved type inference may be calculated for a path expression that may be classified into a series of input expressions followed by steps. For each such series, the inference may be calculated based on input including a type for the input expression, an axis for the step, and a node test for the step. The cardinality of the input expression type is preserved for the calculation of the step type. Also, a set of one or more matching node types may be identified within the type repository. These matching node types are node types within the axis of the step that match the node test of the step. These matching node types are identified without calculating the full content type implied by the axis. Avoiding the calculation of the full content type of the axis may reduce the processing time required to perform the inference.

Claims

1. A method for calculating an inferred type of a step in a path expression having an input expression followed by the step, the input expression having an associated input expression type with an associated input expression type cardinality, the step having an axis and a node test, the method comprising:

preserving the input expression type cardinality for calculating the inferred type of the step; and

calculating the inferred type of the step in accordance with the preserved input expression type cardinality, the axis, and the node test.

2. The method of claim 1, comprising calculating the inferred type of the step in accordance with the preserved input expression type cardinality, the axis, and the node test which is a node kind test.

3. The method of claim 1, comprising calculating the inferred type of the step in accordance with the preserved input expression type cardinality, the axis, and the node test which is a name test.

4. The method of claim 1, wherein calculating the inferred type of the step in accordance with the preserved input expression type cardinality, the axis, and the node test comprises:

identifying a set of at least one matching node type within a type repository that matches both the axis and the node test for the step without calculating a full content type implied by the axis;

retrieving a type of each identified matching node from the type repository; and

calculating the inferred type of the step in accordance with the preserved input expression type cardinality and the type of each identified matching node.

5. The method of claim 1, wherein calculating the inferred type of the step comprises:

identifying a symbol in element content corresponding to the input expression;

determining that the symbol is an element;

determining whether the axis is a child axis;

if not, then returning an empty set;

if so, then determining whether the symbol matches the node test;

if not, then returning an empty set;

if so, then calculating the inferred type of the step in accordance with the symbol.

6. The method of claim 1, wherein calculating the inferred type of the step comprises:

identifying a symbol in element content corresponding to the input expression;

determining that the symbol is an attribute;

determining whether the axis is an attribute axis;

if not, then returning an empty set;

if so, then determining whether the symbol matches the node test;

if not, then returning an empty set;

if so, then calculating the inferred type of the step in accordance with the symbol.

7. A computer readable medium having computer executable instructions for performing the steps recited in claim 1.

8. A method for calculating an inferred type of a step in a path expression having an input expression followed by a step, the input expression having an associated input expression type with an associated input expression type cardinality, the step having an axis and a node test, the method comprising:

identifying a set of at least one matching node type within a type repository that matches both the axis and the node test for the step without calculating a full content type implied by the axis; and

retrieving a type of each identified matching node from the type repository.

9. The method of claim 8, comprising identifying a set of at least one matching node type within a type repository that matches both the axis and the node test which is a node kind test.

10. The method of claim 8, comprising identifying a set of at least one matching node type within a type repository that matches both the axis and the node test which is a name test.

11. The method of claim 8, further comprising:

preserving the input expression type cardinality for calculating the inferred type of the step; and

calculating the inferred type of the step in accordance with the preserved input expression type cardinality and the type of each identified matching node.

12. The method of claim 11, wherein calculating the inferred type of the step comprises:

identifying a symbol in element content corresponding to the input expression;

determining that the symbol is an element;

determining whether the axis is a child axis;

if not, then returning an empty set;

if so, then determining whether the symbol matches the node test;

if not, then returning an empty set;

if so, then calculating the inferred type of the step in accordance with the symbol.

13. The method of claim 11, wherein calculating the inferred type of the step comprises:

identifying a symbol in element content corresponding to the input expression;

determining that the symbol is an attribute;

determining whether the axis is an attribute axis;

if not, then returning an empty set;

if so, then determining whether the symbol matches the node test;

if not, then returning an empty set;

if so, then calculating the inferred type of the step in accordance with the symbol.

14. A computer readable medium having computer executable instructions for performing the steps recited in claim 8.

15. A system for calculating an inferred type of a step in a path expression having an input expression followed by a step, the input expression having an associated input expression type with an associated input expression type cardinality, the step having an axis and a node test, the system comprising:

a processor operative to execute computer executable instructions; and

memory having stored therein computer executable instructions for performing the following stages;

preserving the input expression type cardinality for calculating the inferred type of the step; and

calculating the inferred type of the step in accordance with the preserved input expression type cardinality, the axis, and the node test.

16. The system of claim 15, wherein the node test is a node kind test.

17. The system of claim 15, wherein the node test is a name test.

18. The system of claim 15, further comprising a type repository into which type information corresponding to a schema is loaded.

19. The system of claim 15, wherein the type repository is a symbol table.

20. The system of claim 15, further comprising an annotated abstract syntax tree in which the inferred type of the step annotates a corresponding step node.