Incremental computing of changes to computer user interfaces

• US 8,627,199 B1
• Filed: 03/01/2011
• Issued: 01/07/2014
• Est. Priority Date: 01/29/2010
• Status: Active Grant

• Current Assignee: Asana
• Original Assignee: Asana
• Inventors: Moskovitz, Dustin, Rosenstein, Justin, Handley, Malcolm
• Primary Examiner(s): Hutton, Jr., Doug
• Assistant Examiner(s): Smith, Tionna
• Application Number:
  US13/038,356
• Time in Patent Office: 1,043 Days
• Field of Search: 715/234
• US Class Current: 715/234
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: G06F 9/45529 Embedded in an application, e.g. JavaScript in a Web browser

Abstract

A method is provided to update information in a computer system comprising providing a reactive value hierarchy structure in a non-transitory computer readable storage device; in response to a change in a reactive value corresponding to a node in the hierarchy, marking nodes within the hierarchy that share as dirty a path with a node corresponding to a changed reactive value; traversing down through the hierarchy to a level where a reactive value is located that is either dirty or clean; if the reactive value is dirty, traversing back up to a dependent node in the hierarchy and compute a new reactive value and repeating the traversing down step; if the reactive value is clean, traversing back up to a dependent node and repeating the traversing down step; and producing at least one side-effect in the computer system in response to a compute of a new reactive value.

Claims

1. A method comprising:

configuring a processor to execute a function first time;

in the course of execution of the function, producing a reactive value hierarchy structure in a non-transitory computer readable storage device that includes a plurality of respective nodes that correspond to respective reactive values used in the first execution of the function and that indicates relationships among nodes that correspond to relationships among corresponding reactive values during the first execution of the function;

wherein respective nodes in the hierarchy act as dependent nodes to other nodes lower in the hierarchy that act as inputs nodes to the respective nodes;

wherein the respective nodes act as input nodes to the other nodes higher in the hierarchy that act as dependent nodes to the respective nodes; and

wherein respective nodes are associated with respective ordered sets of one or more input nodes ordered according to order of use of their corresponding reactive values during the first execution of the function;

identifying one or more changed reactive values associated with one or more nodes;

traversing upward within the hierarchy starting from the nodes identified as having changed reactive values to identify multiple nodes within the hierarchy that are possibly dirty due to the one or more identified reactive value changes;

associating dirty state and dirty count information in the storage device with the multiple nodes identified as possibly dirty;

configuring the processor to execute the function a second time using the changed reactive values;

wherein configuring the processor to execute the function a second time includes;

configuring the processor to recursively run a process to ensure current reactive values for the nodes within the hierarchy;

wherein the process includes;

monitoring dirty state information and dirty count information associated with a given node;

while the dirty state information associated with the given node indicates not dirty and the dirty count information of the given node indicates that the given node is possibly dirty, requesting the process in order one at a time on successive ordered input nodes to the given node;

when the dirty state information associated with the given node is dirty, computing a current reactive value for the given node and decrementing the dirty count information of direct dependent nodes of the of the given node and if the computed current reactive value for the given node is changed then marking as dirty, dirty state information associated with direct dependent nodes of the given node; and

when the dirty state information associated with the given node indicates not dirty and the dirty count information indicates that the given node is not dirty, returning a current reactive value of the given node to a dependent node that requested performing the process on the given node.

2. The method of claim 1,

wherein computing a current reactive value includes requesting the process on each input node to the given node.

3. The method of claim 1 further including:

decrementing the dirty count information of the given node upon occurrence of computing the current reactive value.

4. The method of claim 1 further including:

returning the computed current reactive value of the given node to the dependent node that requested performing of the process on the given node.

5. The method of claim 1 further including:

marking as not dirty, dirty state information associated with the given node upon occurrence of computing the current reactive value.

6. The method of claim 1 further including:

marking as not dirty, dirty state information associated with the given node upon occurrence of computing the current reactive value;

wherein returning the current reactive value of the given node to a dependent node that requested performing the process on the given node involves returning the computed current reactive value.

7. The method of claim 1,

wherein dirty information state of an associated node is indicative of whether a reactive value of that associated node changed due to the received reactive value change.

8. The method of claim 1,

wherein dirty count information of an associated node is indicative of number of nodes that are direct inputs to that associated node have reactive values that possibly changed due to the received reactive value change.

9. A method comprising:

configuring a processor to execute a function first time;

in the course of execution of the function, producing a reactive value hierarchy structure in a non-transitory computer readable storage device that includes a plurality of respective nodes that correspond to respective reactive values used in the first execution of the function and that indicates relationships among nodes that correspond to relationships among corresponding reactive values during the first execution of the function;

wherein respective nodes in the hierarchy act as dependent nodes to other nodes lower in the hierarchy that act as inputs nodes to the respective nodes;

wherein the respective nodes act as input nodes to the other nodes higher in the hierarchy that act as dependent nodes to the respective nodes; and

wherein respective nodes are associated with respective ordered sets of one or more input nodes ordered according to order of use of their corresponding reactive values during the first execution of the function;

in response to a change in a reactive value corresponding to a node in the hierarchy, marking nodes within the hierarchy that share a path with a node corresponding to a changed reactive value with indicia to indicate that they are possibly dirty;

configuring the processor to execute the function a second time;

in the course of executing the function the second time, configuring the processor to perform a recursive process that includes;

traversing down through one or more levels of the hierarchy following a path indicated by the marking that includes a possibly dirty node from the lowest order input node not yet traversed at successive levels of the hierarchy to a level where the reactive value has changed;

determining whether the changed reactive value indicates that the reactive value of the dependent node at a next level above in the hierarchy that was most recently traversed down from is dirty or clean;

if the reactive value of the dependent node at a next level above in the hierarchy that was most recently traversed down from is determined to be dirty then computing a new reactive value for that node;

if the reactive value of the dependent node at a next level above in the hierarchy that was most recently traversed down from is determined to be clean then traversing back up to a dependent node at a next level above in the hierarchy that was most recently traversed down from and repeating the traversing down step;

determining whether the computed new reactive value results in one or more reactive values in the hierarchy being obsolete; and

removing from one or more nodes in the hierarchy a marking that indicates a shared path with a possibly dirty node that is obsolete.

10. The method of claim 9,

wherein the step of executing the function the second time includes performing the recursive process for multiple different paths indicated by the marking as including a possibly dirty node.

11. The method of claim 9,

wherein the step of executing the function the second time includes performing the recursive process for each of multiple different paths indicated by the marking as including a possibly dirty node;

and

wherein the step of removing from one or more nodes in the hierarchy a marking that indicates a shared path with a possibly dirty node avoids performing the recursive process for the path that had been indicated by the removed marking.

12. The method of claim 9,

wherein determining whether the computed new reactive value results in one or more reactive values in the hierarchy being obsolete involves determining whether the function branched to an execution path the second time that is different from an execution path that the function branched to the first time.

13. An article of manufacture that includes a non-transitory computer readable storage device encode with program code to cause a processor to perform a process comprising:

configuring a processor to execute a function first time;

in the course of execution of the function, producing a reactive value hierarchy structure in a non-transitory computer readable storage device that includes a plurality of respective nodes that correspond to respective reactive values used in the first execution of the function and that indicates relationships among nodes that correspond to relationships among corresponding reactive values during the first execution of the function;

wherein respective nodes in the hierarchy act as dependent nodes to other nodes lower in the hierarchy that act as inputs nodes to the respective nodes;

wherein the respective nodes act as input nodes to the other nodes higher in the hierarchy that act as dependent nodes to the respective nodes; and

wherein respective nodes are associated with respective ordered sets of one or more input nodes ordered according to order of use of their corresponding reactive values during the first execution of the function;

identifying one or more changed reactive values associated with one or more nodes;

traversing upward within the hierarchy starting from the nodes identified as having changed reactive values to identify multiple nodes within the hierarchy that are possibly dirty due to the one or more identified reactive value changes;

associating dirty state and dirty count information in the storage device with the multiple nodes identified as possibly dirty;

configuring the processor to execute the function a second time using the changed reactive values;

wherein configuring the processor to execute the function a second time includes;

configuring the processor to recursively run a process to ensure current reactive values for the nodes within the hierarchy;

wherein the process includes;

monitoring dirty state information and dirty count information associated with a given node;

while the dirty state information associated with the given node indicates not dirty and the dirty count information of the given node indicates that the given node is possibly dirty, requesting the process in order one at a time on successive ordered input nodes to the given node;

when the dirty state information associated with the given node is dirty, computing a current reactive value for the given node and decrementing the dirty count information of direct dependent nodes of the of the given node and if the computed current reactive value for the given node is changed then marking as dirty, dirty state information associated with direct dependent nodes of the given node; and

when the dirty state information associated with the given node indicates not dirty and the dirty count information indicates that the given node is not dirty, returning a current reactive value of the given node to a dependent node that requested performing the process on the given node.

14. A system that includes a processor and a computer readable storage device and a communication bus connecting the processor and the device, wherein the computer readable storage device is encoded with program code to cause the processor to perform a process comprising:

configuring a processor to execute a function first time;

in the course of execution of the function, producing a reactive value hierarchy structure in a non-transitory computer readable storage device that includes a plurality of respective nodes that correspond to respective reactive values used in the first execution of the function and that indicates relationships among nodes that correspond to relationships among corresponding reactive values during the first execution of the function;

wherein respective nodes in the hierarchy act as dependent nodes to other nodes lower in the hierarchy that act as inputs nodes to the respective nodes;

wherein the respective nodes act as input nodes to the other nodes higher in the hierarchy that act as dependent nodes to the respective nodes; and

wherein respective nodes are associated with respective ordered sets of one or more input nodes ordered according to order of use of their corresponding reactive values during the first execution of the function;

identifying one or more changed reactive values associated with one or more nodes;

traversing upward within the hierarchy starting from the nodes identified as having changed reactive values to identify multiple nodes within the hierarchy that are possibly dirty due to the one or more identified reactive value changes;

associating dirty state and dirty count information in the storage device with the multiple nodes identified as possibly dirty;

configuring the processor to execute the function a second time using the changed reactive values;

wherein configuring the processor to execute the function a second time includes;

configuring the processor to recursively run a process to ensure current reactive values for the nodes within the hierarchy;

wherein the process includes;

monitoring dirty state information and dirty count information associated with a given node;

while the dirty state information associated with the given node indicates not dirty and the dirty count information of the given node indicates that the given node is possibly dirty, requesting the process in order one at a time on successive ordered input nodes to the given node;

when the dirty state information associated with the given node is dirty, computing a current reactive value for the given node and decrementing the dirty count information of direct dependent nodes of the of the given node and if the computed current reactive value for the given node is changed then marking as dirty, dirty state information associated with direct dependent nodes of the given node; and

when the dirty state information associated with the given node indicates not dirty and the dirty count information indicates that the given node is not dirty, returning a current reactive value of the given node to a dependent node that requested performing the process on the given node.

15. An article of manufacture that includes a non-transitory computer readable storage device encode with program code to cause a processor to perform a process comprising:

configuring a processor to execute a function first time;

in the course of execution of the function, producing a reactive value hierarchy structure in a non-transitory computer readable storage device that includes a plurality of respective nodes that correspond to respective reactive values used in the first execution of the function and that indicates relationships among nodes that correspond to relationships among corresponding reactive values during the first execution of the function;

wherein respective nodes in the hierarchy act as dependent nodes to other nodes lower in the hierarchy that act as inputs nodes to the respective nodes;

wherein the respective nodes act as input nodes to the other nodes higher in the hierarchy that act as dependent nodes to the respective nodes; and

wherein respective nodes are associated with respective ordered sets of one or more input nodes ordered according to order of use of their corresponding reactive values during the first execution of the function;

in response to a change in a reactive value corresponding to a node in the hierarchy, marking nodes within the hierarchy that share a path with a node corresponding to a changed reactive value with indicia to indicate that that they are possibly dirty;

configuring the processor to execute the function a second time;

in the course of executing the function the second time, configuring the processor to perform a recursive process that includes;

traversing down through one or more levels of the hierarchy following a path indicated by the marking that includes a possibly dirty node from the lowest order input node not yet traversed at successive levels of the hierarchy to a level where the reactive value has changed;

determining whether the changed reactive value indicates that the reactive value of the dependent node at a next level above in the hierarchy that was most recently traversed down from is dirty or clean;

if the reactive value of the dependent node at a next level above in the hierarchy that was most recently traversed down from is determined to be dirty then computing a new reactive value for that node;

if the reactive value of the dependent node at a next level above in the hierarchy that was most recently traversed down from is determined to be clean then traversing back up to a dependent node at a next level above in the hierarchy that was most recently traversed down from and repeating the traversing down step;

determining whether the computed new reactive value results in one or more reactive values in the hierarchy being obsolete; and

removing from one or more nodes in the hierarchy a marking that indicates a shared path with a possibly dirty node that is obsolete.

16. A system that includes a processor and a computer readable storage device and a communication bus connecting the processor and the device, wherein the computer readable storage device is encoded with program code to cause the processor to perform a process comprising:

configuring a processor to execute a function first time;

in the course of execution of the function, producing a reactive value hierarchy structure in a non-transitory computer readable storage device that includes a plurality of respective nodes that correspond to respective reactive values used in the first execution of the function and that indicates relationships among nodes that correspond to relationships among corresponding reactive values during the first execution of the function;

wherein respective nodes in the hierarchy act as dependent nodes to other nodes lower in the hierarchy that act as inputs nodes to the respective nodes;

wherein the respective nodes act as input nodes to the other nodes higher in the hierarchy that act as dependent nodes to the respective nodes; and

wherein respective nodes are associated with respective ordered sets of one or more input nodes ordered according to order of use of their corresponding reactive values during the first execution of the function;

in response to a change in a reactive value corresponding to a node in the hierarchy, marking nodes within the hierarchy that share a path with a node corresponding to a changed reactive value with indicia to indicate that they are possibly dirty;

configuring the processor to execute the function a second time;

in the course of executing the function the second time, configuring the processor to perform a recursive process that includes;

traversing down through one or more levels of the hierarchy following a path indicated by the marking that includes a possibly dirty node from the lowest order input node not yet traversed at successive levels of the hierarchy to a level where the reactive value has changed;

determining whether the changed reactive value indicates that the reactive value of the dependent node at a next level above in the hierarchy that was most recently traversed down from is dirty or clean;

if the reactive value of the dependent node at a next level above in the hierarchy that was most recently traversed down from is determined to be dirty then computing a new reactive value for that node;

if the reactive value of the dependent node at a next level above in the hierarchy that was most recently traversed down from is determined to be clean then traversing back up to a dependent node at a next level above in the hierarchy that was most recently traversed down from and repeating the traversing down step;

determining whether the computed new reactive value results in one or more reactive values in the hierarchy being obsolete; and

removing from one or more nodes in the hierarchy a marking that indicates a shared path with a possibly dirty node that is obsolete.