XSLT/XPATH focus inference for optimized XSLT implementation

1. A method for performing focus inference when compiling an Extensible Markup Language Transforms (XSLT) stylesheet into a compiled XSLT processor, comprising:

generating an Abstract Syntax Tree (AST) from said XSLT stylesheet;

annotating nodes in said AST that are associated with variables and parameters with focus inference flags, said annotating comprising for each of said nodes determining which of a plurality of focus inference flags that define a focus is required to be maintained;

building a reverse call graph for a template associated with the XSLT stylesheet;

propagating any focus inference flags from a callee template to a caller template;

propagating any focus inference flags through the reverse call graph; and

using the focus defined by the focus inference flags directly in one or more of a code generator in an XSLT compilation architecture, an interpreter, and/or a JITer,

wherein said focus inference flags comprise a “current” focus inference flag, a “position” focus inference flag, and a “last” focus inference flag.

2. The method of claim 1 , wherein said reverse call graph represents a can-be-called by relation for an xsl:call-template in an xsl-template at a top level case.

3. The method of claim 1 , wherein said reverse call graph represents a can-be-called by relation for an xsl:apply-imports case.

4. The method of claim 1 , wherein said propagating any focus inference flags through the reverse call graph is conducted by a fixed-point algorithm on a control-flow graph.

5. The method of claim 1 , wherein said propagating any focus inference flags through the reverse call graph is conducted by a non-iterative depth first traversal of the reverse call graph.

6. The method of claim 1 , further comprising determining one or more parts of a focus that are required for an XPath expression at execution time.

7. A system for performing focus inference when compiling an Extensible Markup Language Transforms (XSLT) stylesheet into a compiled XSLT processor, comprising:

a processor coupled to a memory, the memory having stored thereon instructions that when executed by the processor cause the processor to:

generate an Abstract Syntax Tree (AST) from said XSLT stylesheet;

annotate nodes in said AST that are associated with variables and parameters with focus inference flags, said annotating comprising for each of said nodes determining which of a plurality of focus inference flags that define a focus is required to be maintained;

build a reverse call graph for a template associated with the XSLT stylesheet;

propagate any focus inference flags from a callee template to a caller template;

propagate any focus inference flags through the reverse call graph; and use the focus defined by the focus inference flags directly in one or more of a code generator in an XSLT compilation architecture, an interpreter, and/or a JITer,

wherein said focus inference flags comprise a “current” focus inference flag, a “position” focus inference flag, and a “last” focus inference flag.

8. The system of claim 7 , wherein said reverse call graph represents a can-be-called by relation for an xsl:call-template in an xsl-template at a top level case.

9. The system of claim 7 , wherein said reverse call graph represents a can-be-called by relation for an xsl:apply-imports case.

10. The system of claim 7 , wherein propagating any focus inference flags through the reverse call graph further comprises using a fixed-point algorithm on a control-flow graph.

11. The system of claim 7 , wherein propagating any focus inference flags through the reverse call graph further comprises using a fixed-point algorithm on a data-flow graph.

12. The system of claim 7 , wherein propagating any focus inference flags through the reverse call graph further comprises conducting a non-iterative depth first traversal of the reverse call graph.

13. A computer readable storage medium bearing instructions for performing focus inference when compiling an Extensible Markup Language Transforms (XSLT) stylesheet into a compiled XSLT processor, said instructions comprising:

instructions for generating an Abstract Syntax Tree (AST) from said XSLT stylesheet;

instructions for annotating nodes in said AST that are associated with variables and parameters with focus inference flags, said annotating comprising for each of said nodes determining which of a plurality of focus inference flags that define a focus is required to be maintained;

instructions for building a reverse call graph for a template associated with the XSLT stylesheet;

instructions for propagating any focus inference flags from a callee template to a caller template;

instructions for propagating any focus inference flags through the reverse call graph; and

instructions for using the focus defined by the focus inference flags directly in one or more of a code generator in an XSLT compilation architecture, an interpreter, and/or a JITer,

wherein said focus inference flags comprise a “current” focus inference flag, a “position” focus inference flag, and a “last” focus inference flag.

14. The computer readable storage medium of claim 13 , wherein said reverse call graph represents a can-be-called by relation for an xsl:call-template in an xsl-template at a top level case.

15. The computer readable storage medium of claim 13 , wherein said reverse call graph represents a can-be-called by relation for xsl:apply-imports case.

16. The computer readable storage medium of claim 13 , wherein said instructions for propagating any focus inference flags through the reverse call graph use a fixed-point algorithm on a control flow graph or a data-flow graph.

17. The computer readable storage medium of claim 13 , wherein said instructions for propagating any focus inference flags through the reverse call graph use a non-iterative depth first traversal of the reverse call graph.