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

Patent metadata

Field	Value
Publication number	US-9489367-B2
Application number	US-201313909655-A
Country	US
Kind code	B2
Filing date	Jun 4, 2013
Priority date	Feb 27, 2013
Publication date	Nov 8, 2016
Grant date	Nov 8, 2016

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.

First claim

What is claimed is:

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

Assignees

• Google Inc

Inventors

• Danziger Joshua Ari
• Karve Amod
• Kahlon Yossi
• Simon Benjamin Wolfe
• Lloyd Zachary Erik

Classifications

• G06Q10/101 Primary

  Collaborative creation, e.g. joint development of products or services · CPC title

• G06F40/18 Primary

  of spreadsheets (form-filling G06F40/174) · CPC title

• G06F17/246 Primary

  Physics · mapped topic