Web-based incremental computing

• US 8,572,477 B1
• Filed: 01/31/2011
• Issued: 10/29/2013
• Est. Priority Date: 01/29/2010
• Status: Active Grant

• Current Assignee: Asana
• Original Assignee: Asana
• Inventors: Moskovitz, Dustin, Rosenstein, Justin
• Primary Examiner(s): Patel, Manglesh M
• Application Number:
  US13/017,730
• Time in Patent Office: 1,002 Days
• Field of Search: 715/200, 715/234
• US Class Current: 715/234
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation

Abstract

A method and a system implementing web-based incremental computing. A webpage updates when a data value relevant to displayed information is altered and updates only those affected elements. A watch system monitors relevant data values and in conjunction with a dependency tree, may execute functions to alter only altered elements of a webpage. A framework to automatically track data dependencies and propagate data changes is disclosed.

Claims

1. A method to update a document object model (DOM) stored in a computer readable storage device, wherein producing the DOM includes running a function that includes multiple expressions on a computer system in response to a set of input values, the method comprising:

producing a dependency graph structure in a computer readable storage device that includes nodes that correspond to reactive values produced in the course of evaluation of the expressions within the function in response to the set of input values and that includes a node that corresponds to a contained in relationship between a reactive value and a corresponding element of the DOM in response to evaluation of one or more expressions within the function in response to the set of input values indicating inclusion of such node having the contained in relationship and that includes paths among the nodes that represent dependency relationships among the reactive values, wherein respective paths include a root node and include respective input nodes that are associated with respective input values and include respective nodes, disposed between the root node and respective input nodes, that are associated in the storage device with at least one of expressions within the function used to produce respective reactive values that correspond to those respective nodes or to the contained in relationship;

detecting a change of at least one input value from the set of input values;

in response to the detected change of the at least one input value, selecting in ascending order of node depth within the dependency graph structure, a respective node from among the root node and respective nodes on respective paths that have a respective input node associated with a respective changed input value; and

re-running on a computer system a respective expression, that is associated with the respective selected node, using the changed input value to determine a respective changed reactive value;

in response to the re-running the respective expression associated with the respective selected node, prior to re-running an expression associated with a respective next selected node in the ascending order of node depth, changing the dependency graph structure to represent any changes to one or more dependency relationships among reactive values produced as a result of the respective re-running;

continuing the acts of re-running and changing in the ascending order of node depth within the changed dependency graph structure; and

in the course of the acts of re-running, in response to the dependency graph structure including a node that corresponds to a contained in relationship between a changed reactive value and a corresponding element of the DOM, propagating the changed reactive value to that corresponding element of the DOM.

2. The method of claim 1,

wherein changing the dependency graph structure to represent any changes to one or more dependency relationships among reactive values produced as a result of the respective re-running includes:

adding a node to the dependency graph structure.

3. The method of claim 1,

wherein changing the dependency graph structure to represent any changes to one or more dependency relationships among reactive values produced as a result of the respective re-running includes:

deleting a node from the dependency graph structure.

4. The method of claim 1,

wherein changing the dependency graph structure to represent any changes to one or more dependency relationships among reactive values produced as a result of the respective re-running includes:

adding a node to the dependency graph structure; and

deleting a node from the dependency graph structure.

5. The method of claim 1,

wherein respective nodes of dependency graph structure are associated in the storage device with respective reactive values produced using respective expressions associated with the nodes.

6. The method of claim 5 further including:

wherein the act of re-running the respective expression associated with the respective selected node, prior to re-running an expression associated with a respective next selected node in the ascending order of node depth, further includes changing the dependency graph structure to,

associate the respective changed reactive value in the storage device with the respective selected node.

7. The method of claim 1,

wherein continuing the acts of re-running and changing in the ascending order of node depth within the changed dependency graph structure includes terminating the acts of re-running and changing in response to a changed dependency graph structure in which no path that includes a node that is associated with a changed input value includes a node that corresponds to a reactive value that has respective contained-in relationship with another reactive value that corresponds to another respective node of the dependency graph structure.

8. The method of claim 1,

wherein respective nodes of dependency graph structure are associated in the storage device with respective reactive values produced using respective expressions associated with the nodes;

and further including;

associating respective watch programs with the root node and with respective nodes that correspond to respective reactive values that have respective contained-in relationships with other reactive values that correspond to other respective nodes of the dependency graph structure;

using a watch program associated with a node to run an expression associated with the node to determine whether a reactive value associated with the node has changed.

9. The method of claim 1 further including:

associating respective watch programs with the root node and with respective nodes that correspond to respective reactive values that have respective contained-in relationships with other reactive values that correspond to other respective nodes of the dependency graph structure;

wherein re-running on a computer system a respective expression, that is associated with the respective selected node, involves using a respective watch process associated with the respective selected node to run the respective expression using the changed input value, to determine a respective changed reactive value.

10. The method of claim 1 further including:

associating respective watch programs with the root node and with respective nodes that correspond to respective reactive values that have respective contained-in relationships with other reactive values that correspond to other respective nodes of the dependency graph structure; and

wherein re-running on a computer system a respective expression, that is associated with the respective selected node, involves using a respective watch process associated with the respective selected node to run the respective expression using the changed input value, to determine a respective changed reactive value; and

wherein the act of re-running the respective expression associated with the respective selected node, prior to re-running an expression associated with a respective next selected node in the ascending order of node depth, further includes changing the dependency graph structure to,

remove an association in the storage device between the changed dependency graph structure and a respective watch program that has become obsolete.

11. The method of claim 1 further including:

associating respective watch programs with the root node and with respective nodes that correspond to respective reactive values that have respective contained-in relationships with other reactive values that correspond to other respective nodes of the dependency graph structure; and

wherein re-running on a computer system a respective expression, that is associated with the respective selected node, involves using a respective watch process associated with the respective selected node to run the respective expression using the changed input value, to determine a respective changed reactive value; and

wherein the act of re-running the respective expression associated with the respective selected node, prior to re-running an expression associated with a respective next selected node in the ascending order of node depth, further includes changing the dependency graph structure to,

add an association in the storage device between a respective watch program and a respective node of the changed dependency graph structure that corresponds to a reactive value that has a contained-in relationship with another reactive value that corresponds to another node of the graph.

12. The method of claim 1,

wherein detecting a change of at least one input value includes capturing user input.

13. The method of claim 1,

wherein detecting a change of at least one input value includes receiving notification of a changed database value.

14. An article of manufacture that includes a computer readable storage device that stores computer readable code to configure a computer to implement a method to update a document object model (DOM) stored in a computer readable storage device, wherein producing the DOM includes running a function that includes multiple expressions on a computer system in response to a set of input values, the method comprising:

producing a dependency graph structure in a computer readable storage device that includes nodes that correspond to reactive values produced in the course of evaluation of the expressions within the function in response to the set of input values and that includes a node that corresponds to a contained in relationship between a reactive value and a corresponding element of the DOM in response to evaluation of one or more expressions within the function in response to the set of input values indicating inclusion of such node having the contained in relationship and that includes paths among the nodes that represent dependency relationships among the reactive values, wherein respective paths include a root node and include respective input nodes that are associated with respective input values and include respective nodes, disposed between the root node and respective input nodes, that are associated in the storage device with at least one of expressions within the function used to produce respective reactive values that correspond to those respective nodes or to the contained in relationship;

detecting a change of at least one input value from the set of input values;

in response to the detected change of the at least one input value, selecting in ascending order of node depth within the dependency graph structure, a respective node from among the root node and respective nodes on respective paths that have a respective input node associated with a respective changed input value; and

re-running on a computer system a respective expression, that is associated with the respective selected node, using the changed input value to determine a respective changed reactive value;

in response to the re-running the respective expression associated with the respective selected node, prior to re-running an expression associated with a respective next selected node in the ascending order of node depth, changing the dependency graph structure to represent any changes to one or more dependency relationships among reactive values produced as a result of the respective re-running;

continuing the acts of re-running and changing in the ascending order of node depth within the changed dependency graph structure; and

in the course of the acts of re-running, in response to the dependency graph structure including a node that corresponds to a contained in relationship between a changed reactive value and a corresponding element of the DOM, propagating the changed reactive value to that corresponding element of the DOM.

15. The article of claim 14,

wherein changing the dependency graph structure to represent any changes to one or more dependency relationships among reactive values produced as a result of the respective re-running includes:

adding a node to the dependency graph structure.

16. The article of claim 14,

wherein changing the dependency graph structure to represent any changes to one or more dependency relationships among reactive values produced as a result of the respective re-running includes:

deleting a node from the dependency graph structure.

17. The article of claim 14,

wherein changing the dependency graph structure to represent any changes to one or more dependency relationships among reactive values produced as a result of the respective re-running includes:

adding a node to the dependency graph structure; and

deleting a node from the dependency graph structure.

18. The article of claim 14,

wherein continuing the acts of re-running and changing in the ascending order of node depth within the changed dependency graph structure includes terminating the acts of re-running and changing in response to a changed dependency graph structure in which no path that includes a node that is associated with a changed input value includes a node that corresponds to a reactive value that has respective contained-in relationship with another reactive value that corresponds to another respective node of the dependency graph structure.

19. The article of claim 14,

wherein respective nodes of dependency graph structure are associated in the storage device with respective reactive values produced using respective expressions associated with the nodes;

and further including;

associating respective watch programs with the root node and with respective that correspond to respective reactive values that have respective contained-in relationships with other reactive values that correspond to other respective nodes of the dependency graph structure;

using a watch program associated with a node to run an expression associated with the node to determine whether a reactive value associated with the node has changed.

20. The article of claim 14, the method further including:

associating respective watch programs with the root node and with respective nodes that correspond to respective reactive values that have respective contained-in relationships with other reactive values that correspond to other respective nodes of the dependency graph structure; and

wherein re-running on a computer system a respective expression, that is associated with the respective selected node, involves using a respective watch process associated with the respective selected node to run the respective expression using the changed input value, to determine a respective changed reactive value.

21. A system comprising:

at least one processor;

non-transitory machine readable storage device; and

a communication bus coupling the processor and the storage device;

wherein the storage device stores computer readable code to configure the at least one processor to implement a method to update a document object model (DOM) stored in a computer readable storage device, wherein producing the DOM includes running a function that includes multiple expressions on the at least one processor in response to a set of input values, the method comprising;

producing a dependency graph structure in a computer readable storage device that includes nodes that correspond to reactive values produced in the course of evaluation of the expressions within the function in response to the set of input values and that includes a node that corresponds to a contained in relationship between a reactive value and a corresponding element of the DOM in response to evaluation of one or more expressions within the function in response to the set of input values indicating inclusion of such node having the contained in relationship and that includes paths among the nodes that represent dependency relationships among the reactive values, wherein respective paths include a root node and include respective input nodes that are associated with respective input values and include respective nodes, disposed between the root node and respective input nodes, that are associated in the storage device with at least one of expressions within the function used to produce respective reactive values that correspond to those respective nodes or to the contained in relationship;

detecting a change of at least one input value from the set of input values;

in response to the detected change of the at least one input value, selecting in ascending order of node depth within the dependency graph structure, a respective node from among the root node and respective nodes on respective paths that have a respective input node associated with a respective changed input value; and

re-running on a computer system a respective expression, that is associated with the respective selected node, using the changed input value to determine a respective changed reactive value;

in response to the re-running the respective expression associated with the respective selected node, prior to re-running an expression associated with a respective next selected node in the ascending order of node depth, changing the dependency graph structure to represent any changes to one or more dependency relationships among reactive values produced as a result of the respective re-running;

continuing the acts of re-running and changing in the ascending order of node depth within the changed dependency graph structure; and

in the course of the acts of re-running, in response to the dependency graph structure including a node that corresponds to a contained in relationship between a changed reactive value and a corresponding element of the DOM, propagating the changed reactive value to that corresponding element of the DOM.