Optimized Transpilation

Patent metadata

Field	Value
Publication number	US-2021096832-A1
Application number	US-201916589998-A
Country	US
Kind code	A1
Filing date	Oct 1, 2019
Priority date	Oct 1, 2019
Publication date	Apr 1, 2021
Grant date	—

Abstract

System and methods are described to parse input source code and generate a tree representing the input source code, optimize the tree by determining reusable sub-trees of the tree and replacing the reusable sub-trees with variables, and transpile the optimized tree to generate output source code.

First claim

1 . An apparatus, comprising:
a processing device; and a memory device coupled to the processing device, the memory device having instructions stored thereon that, in response to execution by the processing device, cause the processing device to: parse input source code and generate a tree representing the input source code; optimize the tree by recursively traverse the tree starting with a root node of the tree as a current node; if the current node represents a reusable sub-tree already encountered during traversal, replace the current node with a first leaf node assigned to a variable; and
if the current node does not represent a reusable sub-tree already encountered during traversal, and the current node has already been encountered during traversal, assign a new variable, replace the current node with a second leaf node referencing the new variable, and replace a previous instance of the current node with a third leaf node referencing the new variable; and
transpile the optimized tree to generate output source code.

2 . The apparatus of claim 1 , wherein the tree is an abstract syntax tree.

3 . The apparatus of claim 1 , wherein the input source code is in a formula language.

4 . The apparatus of claim 1 , wherein the output source code in JavaScript.

5 . (canceled)

6 . The apparatus of claim 1 , wherein instructions to optimize the tree comprise instructions that, in response to execution by the processing device, cause the processing device to:
if the current node does not represent a reusable sub-tree already encountered during traversal, and the current node has already been encountered during traversal, store the new variable in a set of replaced sub-trees.

7 . The apparatus of claim 1 , wherein instructions to optimize the tree comprise instructions that, in response to execution by the processing device, cause the processing device to:
if the current node does not represent a reusable sub-tree already encountered during traversal, and the current node has not already been encountered during traversal, add the current node to a set of nodes already encountered during traversal.

8 . The apparatus of claim 1 , wherein instructions to transpile the optimized tree to generate output source code comprise instructions that, in response to execution by the processing device, cause the processing device to:
sort replaced sub-trees by level of the tree; and transpile, in sorted order, each replaced sub-tree, and append generated source code for each replaced sub-tree as an assignment statement to a variable assigned to each replaced sub-tree.

9 . The apparatus of claim 8 , comprising instructions that, in response to execution by the processing device, cause the processing device to:
sort the replaced sub-trees by level of the tree from deepest level of the tree to top-most level of the tree.

10 . A computer-implemented method comprising:
parsing input source code and generating a tree representing the input source code; optimizing the tree by recursively traversing the tree starting with a root node of the tree as a current node, if the current node represents a reusable sub-tree already encountered during traversal, replacing the current node with a first leaf node assigned to a variable, and if the current node does not represent a reusable sub-tree already encountered during traversal, and the current node has already been encountered during traversal, assigning a new variable, replacing the current node with a second leaf node referencing the new variable, and replacing a previous instance of the current node with a third leaf node referencing the new variable; and transpiling the optimized tree to generate output source code.

11 . The computer-implemented method of claim 10 , wherein the tree is an abstract syntax tree.

12 . The computer-implemented method of claim 10 , wherein the input source code is in a formula language.

13 . The computer-implemented method of claim 10 , wherein the output source code in JavaScript.

14 . (canceled)

15 . The computer-implemented method of claim 10 , wherein optimizing the tree comprises:
if the current node does not represent a reusable sub-tree already encountered during traversal, and the current node has already been encountered during traversal, storing the new variable in a set of replaced sub-trees.

16 . The computer-implemented method of claim 10 , wherein optimizing the tree comprises:
if the current node does not represent a reusable sub-tree already encountered during traversal, and the current node has not already been encountered during traversal, adding the current node to a set of nodes already encountered during traversal.

17 . The computer-implemented method of claim 10 , wherein transpiling the optimized tree to generate output source code comprises:
sorting replaced sub-trees by level of the tree; and transpiling, in sorted order, each replaced sub-tree, and appending generated source code for each replaced sub-tree as an assignment statement to a variable assigned to each replaced sub-tree.

18 . The computer-implemented method of claim 17 , comprising sorting the replaced sub-trees by level of the tree from deepest level of the tree to top-most level of the tree.

19 . A tangible, non-transitory computer-readable storage medium having instructions encoded thereon which, when executed by a processing device, cause the processing device to:
parse input source code and generating a tree representing the input source code;
optimize the tree by recursively traverse the tree starting with a root node of the tree as a current node;
if the current node represents a reusable sub-tree already encountered during traversal, replace the current node with a first leaf node assigned to a variable; and
if the current node does not represent a reusable sub-tree already encountered during traversal, and the current node has already been encountered during traversal, assign a new variable, replace the current node with a second leaf node referencing the new variable, and replace a previous instance of the current node with a third leaf node referencing the new variable; and

transpile the optimized tree to generate output source code.

20 . (canceled)

21 . The tangible, non-transitory computer-readable storage medium of claim 19 , wherein instructions stored thereon to optimize the tree comprise instructions that, in response to execution by the processing device, cause the processing device to:
if the current node does not represent a reusable sub-tree already encountered during traversal, and the current node has already been encountered during traversal, store the new variable in a set of replaced sub-trees.

22 . The tangible, non-transitory computer-readable storage medium of claim 19 , wherein instructions stored thereon to optimize the tree comprise instructions that, in response to execution by the processing device, cause the processing device to:
if the current node does not represent a reusable sub-tree already encountered during traversal, and the current node has not already been encountered during traversal, add the current node to a set of nodes already encountered during traversal.

23 . The tangible, non-transitory computer-readable storage medium of claim 19 , wherein instructions stored thereon to transpile the optimized tree to generate output source code comprise instructions that, in response to execution by the processing d

Assignees

• Salesforce Com Inc

Inventors

• Rich Alexander
• Kathiara Jinai

Classifications

• G06F8/51

  Source to source · CPC title

• G06F8/427 Primary

  Parsing · CPC title

• G06F7/24

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title

• G06F40/211 Primary

  Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars · CPC title

• G06F40/154

  Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets · CPC title