Realtime synchronized document editing by multiple users

• US 8,656,290 B1
• Filed: 04/28/2009
• Issued: 02/18/2014
• Est. Priority Date: 01/08/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Greenspan, David, Iba, Aaron, Zamfirescu-Pereira, John Dalbert
• Primary Examiner(s): Bashore, William
• Assistant Examiner(s): Nabi, Reza
• Application Number:
  US12/431,627
• Time in Patent Office: 1,757 Days
• Field of Search: 715/753
• US Class Current: 715/753
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/197 Version control for software G06F8/71

Abstract

Collaborative editing of electronic documents in realtime is provided. A host serves a client code over a network to a plurality of clients that each employ a browser to run the client code. The client code revises the text document locally in response to user input, frequently sends those edits to the host, receives updates from the other clients via the host, and revises the local text document accordingly. Each client, in some embodiments, stores three variables, one for edits not yet reported to the host, one for edits reported by not yet acknowledged, and one for the text document as modified by the acknowledged edits. Updates from the other clients are applied to the three variables according to certain rules. A composition of the three variables yields a version of the text document. The host keeps records of which edits were introduced by which client.

Claims

1. A server system comprising:

at least one processor;

memory; and

one or more programs, wherein the one or more programs are stored in the memory and

configured to be executed by the one or more processors, the one or more programs including

instructions for;

storing a document as an ordered set of revision records, wherein the document is accessible to a plurality of client computer systems including a first client and a second client;

receiving, from the first client, a representation of a first changeset specifying one or more changes relative to a first version of the document;

receiving, from the second client, a representation of a second changeset specifying one or more changes relative to the first version of the document;

identifying a respective revision record for the document, wherein the respective revision record corresponds to one or more changes that were made to the document prior to receiving the representation of the first changeset and the representation of the second changeset;

generating a translated changeset;

based on a merge of the first changeset and the second changeset, and one or more revision records including the respective revision record;

adding a new revision record that includes the translated changeset to an end of the ordered set of revision records;

transmitting a first representation of the translated changeset to the first client; and

transmitting a second representation of the translated changeset to the second client, wherein each of the first changeset and the second changeset further comprises;

a first length of a version of the document before a change is applied;

a second length of a next version of the document subsequent to the change; and

an array indicating which characters from the version of the document are retained, the characters represented by indices in the version of the document, and which characters are being added to the next version of the document.

2. The system of claim 1, wherein a plurality of the revision records

for the ˜

document each include a respective revision number.

3. The system of claim 1, wherein a plurality of the revision records for the document each include a respective changeset that specifies at least one addition or deletion of a character from a prior version of the document.

4. The system of claim 1, further comprising after receiving the representation of the first changeset, sending an acknowledgement to the first client indicating that the first changeset has been received.

5. The system of claim 1, wherein the first representation of the translated changeset comprises a first follows changeset computed from the first changeset and the second changeset.

6. A method comprising:

at a server system having one or more processors and memory storing one or more programs that when executed by the one or more processors cause the server system to perform the method, the method comprising;

storing a document as an ordered set of revision records, wherein the document is accessible to a plurality of client computer systems including a first client and a second client;

receiving, from the first client, a representation of a first changeset specifying one or more changes relative to a first version of the document;

receiving, from the second client, a representation of a second changeset specifying one or more changes relative to the first version of the document;

identifying a respective revision record for the document, wherein the respective revision record corresponds to one or more changes that were made to the document prior to receiving the representation of the first changeset and the representation of the second changeset;

generating a translated changeset;

based on the a merge of first changeset and the second changeset, and one or more revision records including the respective revision record;

adding a new revision record that includes the translated changeset to an end of the ordered set of revision records;

transmitting a first representation of the translated changeset to the first client; and

transmitting a second representation of the translated changeset to the second client, wherein each of the first changeset and the second changeset further comprises;

a first length of a version of the document before a change is applied;

a second length of a next version of the document subsequent to the change; and

an array indicating which characters from the version of the document are retained, the characters represented by indices in the version of the document, and which characters are being added to the next version of the document.

7. The method of claim 6 wherein the translated changeset specifies changes relative to a current version of the document stored at the server prior to receiving the representation of the first changeset from the first client.

8. The method of claim 6 further comprising, after receiving the representation of the first changeset, sending an acknowledgement to the first client indicating that the first changeset has been received.

9. The method of claim 6, wherein:

the second client stores a second version of the document different from the first version

of the document; and

the translated changeset specifies one or more changes relative to the second version of the document and enables the second client to update the second version of the document at the second client in accordance with changes made by the first client to the first version of the document.

10. The method of claim 6, wherein:

the respective revision record includes a changeset that updates the first version of the document to a second version of the document;

the second version of the document was a current version of the document prior to receiving the representation of the first changeset; and

the translated changeset updates the second version of the document to a current version of the document that incorporates the changes from the first client.

11. The method of claim 6, wherein:

the respective revision record includes a changeset that updates the first version of the document to a second version of the document;

a third version of the document was a current version of the document prior to receiving the representation of the first changeset;

the one or more revision records include a plurality of revision records that update the first version of the document to the third version of the document; and

the translated changeset updates the third version of the document to a current version of the document that incorporates the changes from the first client and changes included in the plurality of revision records.

12. The method of claim 6, wherein:

the respective revision record includes a respective changeset that updates the first version of the document to a second version of the document; and

the respective changeset specifies one or more changes that have been synchronized with the second client and have not been synchronized with the first client.

13. The method of claim 12, further comprising:

generating a second translated changeset based on the first changeset and the respective

changeset, wherein the second translated changeset updates a current version of the document at the first client that incorporates the first changeset to a current version of the document at the server system that incorporates the respective changeset and the translated changeset; and

transmitting a representation of the second translated changeset the second client.

14. The method of claim 6, wherein the first changeset includes a revision number corresponding to the first version.

15. The method of claim 6, wherein:

the first changeset includes a unique identifier for the first client; and

the method further comprises determining a revision number for the first version based on the unique identifier for the first client.

16. The method of claim 6, wherein the respective revision record includes a changeset and an authorship.

17. The method of claim 6, wherein the first representation of the translated changeset comprises a first follows changeset computed from the first changeset and the second changeset.

18. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a computer system with one or more processors, cause the computer system to:

store a document as an ordered set of revision records, wherein the document is accessible to a plurality of client computer systems including a first client and a second client;

receive, from the first client, a representation of a first changeset specifying one or more changes relative to a first version of the document;

receive, from the second client, a representation of a second changeset specifying one or more changes relative to the first version of the document;

identify a respective revision record for the document, wherein the respective revision record corresponds to one or more changes that were made to the document prior to receiving the representation of the first changeset and the representation of the second changeset;

generate a translated changeset;

based on a merge of the first changeset and the second changeset, and one or more revision records including the respective revision record;

add a new revision record that includes the translated changeset to an end of the ordered set of revision records;

transmit a first representation of the translated changeset to the first client; and

transmit a second representation of the translated changeset to the second client,

wherein each of the first changeset and the second changeset further comprises;

a first length of a version of the document before a change is applied;

a second length of a next version of the document subsequent to the change; and

an array indicating which characters from the version of the document are retained, the characters represented by indices in the version of the document, and which characters are being added to the next version of the document.

19. The non-transitory computer readable storage medium of claim 18, wherein the first representation of the translated changeset comprises a first follows changeset computed from the first changeset and the second changeset.