Systems and methods for mutations and operational transforms in a collaborative spreadsheet environment

• US 9,489,367 B2
• Filed: 06/04/2013
• Issued: 11/08/2016
• Est. Priority Date: 02/27/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Danziger, Joshua Ari, Karve, Amod, Kahlon, Yossi, Simon, Benjamin Wolfe, Lloyd, Zachary Erik
• Primary Examiner(s): Mills, Frank D
• Application Number:
  US13/909,655
• Publication Number:
  US 20150199327A1
• Time in Patent Office: 1,253 Days
• Field of Search: 707/202, 715/220
• US Class Current: 1/1
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services

Abstract

Mutations representing spreadsheet edit operations are received at a server from client computers of collaborators and also at a collaborator'"'"'s client computer from other collaborators and the server. Different mutations may conflict, i.e., provide contradictory instructions on how a spreadsheet is to be edited. Techniques for representing sort operations, cut-and-paste operations, and operations to change cell properties as mutations, and operational transform techniques that can be used to resolve conflicts between such mutations, are disclosed herein. Further disclosed herein are techniques for identifying and processing computationally intensive types of mutations in a calculation thread which operates asynchronously with respect to a UI thread at a collaborator'"'"'s client computer. The processing may include performing an operational transform on results of the calculation thread based on results obtained in the UI thread.

Claims

1. A method for updating a spreadsheet based on user inputs, the method comprising:

receiving a first mutation of a first priority from a source location specifying a function to be applied to data of the spreadsheet, the first mutation comprising (1) a selection of one or more cells at the source location and (2) a mapping from the source location to a destination location;

receiving a second mutation of a second priority from a portion of the source location specifying a data edit mutation to be applied to the spreadsheet, wherein the second mutation is received after the selection of the one or more cells at the source location and before the mapping from the source location to the destination location is received;

determining, by a processor, that the second priority is greater than the first priority;

in response to determining that the second priority is greater than the first priority;

applying the second mutation to the spreadsheet;

performing an operational transform on the selection of the one or more cells of the first mutation based on the second mutation to generate a modified first mutation; and

pasting the modified first mutation to the spreadsheet.

2. The method of claim 1, wherein:

the first mutation corresponds to a cut operation and a paste operation,

the cut operation corresponds to the selection of one or more cells at the source location and the paste operation corresponds to the mapping from the source location to the destination location, and

after the cut operation is received, populating a mutation data structure comprising (1) a value of each cell in the selection of one more cells and (2) the mapping from the source location to the destination location for each cell in the selection of one or more cells.

3. The method of claim 2, wherein applying the modified first mutation to the spreadsheet further comprises:

setting values of destination cells of the spreadsheet in the paste operation,

clearing values of source cells of the spreadsheet in the cut operation, and

updating one or more formulas in the spreadsheet that reference source cell locations in the spreadsheet, upon receiving the data edit mutation between the cut operation and the paste operation.

4. The method of claim 3, wherein updating one or more formulas in the spreadsheet that reference source cell locations in the spreadsheet comprises:

identifying a formula associated with a cell of the spreadsheet,

receiving the data edit mutation between the cut operation and the paste operation, and

updating the formula only if it is determined that the formula references only cells that are included within the source cell locations in the spreadsheet.

5. The method of claim 2, wherein the second mutation corresponds to a command to delete a row within a region of source cells of the cut operation in the spreadsheet, and in response to receiving the second mutation, performing the operational transform comprises omitting contents of the deleted row from the mutation data structure after the cut operation at the source cells before pasting the selection of one or more source cells in a region of destination cells of the paste operation in the spreadsheet.

6. The method of claim 2, wherein the second mutation corresponds to a command to insert a row within a region of destination cells of the paste operation in the spreadsheet, and in response to receiving the second mutation, performing the operational transform comprises preserving a location and content of the inserted row during the paste operation.

7. The method of claim 1, wherein:

the first mutation corresponds to a column sort operation,

the first mutation comprises the mapping from the source location to the destination location for each cell in the selection of one or more cells, and

the first mutation further comprises at least one value of cell data stored in each cell in the selection of one or more cells.

8. The method of claim 7, wherein the first mutation originates at a first client computer and the second mutation originates at a second client computer, and wherein the first mutation and the second mutation are received at a server.

9. The method of claim 8, wherein:

the second client computer is located remotely to the first client computer, and

in response to receiving the data edit mutation, the first client computer performs the operational transform of the first mutation.

10. The method of claim 9, wherein the first client computer performs the operational transform of the first mutation, by reading from a mutation data structure comprising (1) a value of each cell in the selection of one more cells and (2) the mapping from the source location to the destination location for each cell in the selection of one or more source cells without reading from or writing to a chunk of the spreadsheet including a source location of the selection of one or more cells.

11. The method of claim 1, wherein the first priority is determined based on a first type of the first mutation and the second priority is based on a second type of the second mutation.

12. A computing system configured to update a spreadsheet based on user inputs, the computing system comprising:

a network interface configured to;

receive a first mutation of a first priority from a source location specifying a function to be applied to data of the spreadsheet, the first mutation comprising (1) a selection of one or more cells at the source location and (2) a mapping from the source location to a destination location; and

receive a second mutation of a second priority from a portion of the source location specifying a data edit mutation to be applied to the spreadsheet, wherein the second priority is higher than the first priority, and the second mutation is received after the selection of the one or more cells at the source location and before the mapping from the source location to the destination location is received;

a processor configured to;

determine that the second priority is greater than the first priority;

in response to determining that the second priority is greater than the first priority;

apply the second mutation to the spreadsheet;

perform an operational transform on the selection of the one or more cells of the first mutation based on the second mutation to generate a modified first mutation; and

paste the modified first mutation to the spreadsheet.

13. The computing system of claim 12, wherein:

the first mutation corresponds to a cut operation and a paste operation, wherein the cut operation corresponds to the selection of one or more cells at the source location and the paste operation corresponds to the mapping from the source location to the destination location, and

after the cut operation is received, populating a mutation data structure comprising (1) a value of each cell in the selection of one more cells and (2) the mapping from the source location to the destination location for each cell in the selection of one or more cells.

14. The computing system of claim 13, wherein the processor is further configured to apply the modified first mutation to the spreadsheet by:

setting values of destination cells of the spreadsheet in the paste operation,

clearing values of source cells of the spreadsheet in the cut operation, and

updating one or more formulas in the spreadsheet that reference source cell locations in the spreadsheet, upon receiving the data edit mutation between the cut operation and the paste operation.

15. The computing system of claim 14, wherein the processor is further configured to update one or more formulas in the spreadsheet that reference source cell locations in the spreadsheet by:

identifying a formula associated with a cell of the spreadsheet,

receiving the data edit mutation between the cut operation and the paste operation, and

updating the formula only if it is determined that the formula references only cells that are included within the source cell locations in the spreadsheet.

16. The computing system of claim 13, wherein the second mutation corresponds to a command to delete a row within a region of source cells of the cut operation in the spreadsheet, and in response to receiving the second mutation, performing the operational transform comprises omitting contents of the deleted row from the mutation data structure after the cut operation at the source cells before pasting the selection of one or more source cells in a region of destination cells of the paste operation in the spreadsheet.

17. The computing system of claim 13, wherein the second mutation corresponds to a command to insert a row within a region of destination cells of the paste operation in the spreadsheet, and in response to receiving the second mutation performing the operational transform comprises preserving a location and content of the inserted row during the paste operation.

18. The computing system of claim 12, wherein:

the first mutation corresponds to a column sort operation,

the first mutation comprises the mapping from the source location to the destination location for each cell in the selection of one or more cells, and

the first mutation further comprises at least one value of cell data stored in each cell in the selection of one or more cells.

19. The computing system of claim 18, wherein the first mutation originates at a first client computer and the second mutation originates at a second client computer, and wherein the first mutation and the second mutation are received at a server.

20. The computing system of claim 18, wherein:

the second client computer is located remotely to the first client computer, and

in response to receiving the data edit mutation, the first client computer is configured to perform the operational transform of the first mutation.

21. The computing system of claim 20, wherein the first client computer is configured to perform the operational transform of the first mutation, by reading from a mutation data structure comprising (1) a value of each cell in the selection of one more cells and (2) the mapping from the source location to the destination location for each cell in the selection of one or more cells without reading from or writing to a chunk of the spreadsheet including a source location of the selection of one or more cells.

22. The computing system of claim 12, wherein the first priority is determined based on a first type of the first mutation and the second priority is based on a second type of the second mutation.