XSLT/XPATH Focus Inference For Optimized XSLT Implementation

Abstract

Techniques are provided for performing focus inference when compiling an Extensible Markup Language Transforms (XSLT) stylesheet into a compiled XSLT processor. In XPath/XSLT, expression evaluation occurs with respect to the dynamic context. In XPath, the part of the dynamic context, related to the context node-set, is called the “focus” of the expression. Conceptually, the focus would need to be systematically computed and propagated along the recursive execution of XSLT templates. This is costly. Focus inference enables the more efficient execution of XSLT programs since the inferred focus information can be used directly by a code generator in an XSLT compilation architecture.

What is claimed: 
     
         1 . A method for performing inference flags when compiling an Extensible Markup Language Transforms (XSLT) stylesheet into a compiled XSLT processor, comprising:
 generating an Abstract Syntax Tree (AST) from the XSLT stylesheet;   annotating nodes in the AST that are associated with variables and parameters with a first set of inference flags, each inference flag of the first set of inference flags comprising a context position flag and a context size flag;   building a reverse call graph for at least one template associated with the XSLT stylesheet; and   propagating a second set of inference flags through the reverse call graph.   
     
     
         2 . The method of  claim 1 , wherein each inference flag of the first set of inference flags comprises a context item flag. 
     
     
         3 . The method of  claim 1 , wherein each inference flag of the second set of inference flags comprises a context position flag, a context size flag, and a context item flag. 
     
     
         4 . The method of  claim 1 , wherein building the reverse call graph comprises adding edges to a node that represents two or more of the at least one template. 
     
     
         5 . The method of  claim 1 , wherein annotating nodes and building a reverse call graph comprise annotating each node and building each corresponding portion of the reverse call graph in-sequence. 
     
     
         6 . The method of  claim 1 , wherein annotating nodes comprises determining for each node which of the inference flags of the first set of inference flags are required for propagating the second set of inference flags through the reverse call graph and annotating each node with the required inference flags. 
     
     
         7 . The method of  claim 6 , wherein a bottom-up analysis is used to determine for each node which of the inference flags of the first set of inference flags are required for propagating the second set of inference flags through the reverse call graph. 
     
     
         8 . The method of  claim 1  further comprising using the context position flags and the context size flags directly in a code generator of an XSLT compiler. 
     
     
         9 . A system for performing inference flags 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 system to:
 generate an Abstract Syntax Tree (AST) from the XSLT stylesheet; 
 annotate nodes in the AST that are associated with variables and parameters with a first set of inference flags, each inference flag of the first set of inference flags comprising a context position flag and a context size flag; 
 build a reverse call graph for at least one template associated with the XSLT stylesheet; and 
 propagate a second set of inference flags through the reverse call graph. 
   
     
     
         10 . The system of  claim 9 , wherein each inference flag of the first set of inference flags comprises a context item flag. 
     
     
         11 . The system of  claim 9 , wherein each inference flag of the second set of inference flags comprises a context position flag, a context size flag, and a context item flag. 
     
     
         12 . The system of  claim 9 , wherein to build a reverse call graph comprises adding edges to a node that represents two or more of the at least one template. 
     
     
         13 . The system of  claim 9 , wherein to annotate nodes and to build a reverse call graph comprise annotating each node and building each corresponding portion of the reverse call graph in-sequence. 
     
     
         14 . The system of  claim 9 , wherein to annotate nodes comprises using a bottom-up analysis to determine for each node which of the inference flags of the first set of inference flags are required to propagate the second set of inference flags through the reverse call graph and annotating each node with the required inference flags. 
     
     
         15 . The system of  claim 9  further comprising instructions that upon execution cause the processor to use the context position flags and the context size flags directly in one or more of a code generator of an XSLT compiler. 
     
     
         16 . A computer readable storage medium bearing instructions for performing inference flags when compiling an Extensible Markup Language Transforms (XSLT) stylesheet into a compiled XSLT processor, the instructions comprising:
 instructions for generating an Abstract Syntax Tree (AST) from the XSLT stylesheet;   instructions for annotating nodes in the AST that are associated with variables and parameters with a first set of inference flags, each inference flag of the first set of inference flags comprising a context position flag and a context size flag;   instructions for building a reverse call graph for at least one template associated with the XSLT stylesheet; and   instructions for propagating a second set of inference flags through the reverse call graph.   
     
     
         17 . The computer readable storage medium of  claim 16 , wherein each inference flag of the first set of inference flags comprises a context item flag and wherein each inference flag of the second set of inference flags comprises a context position flag, a context size flag, and a context item flag. 
     
     
         18 . The computer readable storage medium of  claim 16 , wherein the instructions for building a reverse call graph comprise instructions for adding edges to a node that represents two or more of the least one template. 
     
     
         19 . The computer readable storage medium of  claim 16 , wherein the instructions for annotating nodes and the instructions for building a reverse call graph comprise instructions for annotating each node and building each corresponding portion of the reverse call graph in-sequence. 
     
     
         20 . The computer readable storage medium of  claim 16 , wherein the instructions for annotating nodes comprise instructions for using a bottom-up analysis to determine for each node which of the inference flags of the first set of inference flags are required for propagating the second set of inference flags through the reverse call graph and for annotating each node with the required inference flags.