MERGING VERSIONS OF DOCUMENTS USING MULTIPLE MASTERS

• US 20090313331A1
• Filed: 06/13/2008
• Published: 12/17/2009
• Est. Priority Date: 06/13/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Clarke, Simon P., Baer, Peter P., Rasmussen, David John
• Granted Patent: US 7,899,883 B2
• Time in Patent Office: Days
• US Class Current: 709/205
• CPC Class Codes: G06F 40/197 Version control for software G06F8/71

Abstract

Tools and techniques are described for merging versions of documents using multiple masters. These tools may provide methods that include syncing a first peer system with at least a second peer system, with the first and second peer systems receiving respective instances of a document for collaborative editing. The first and second peer systems may maintain respective version histories associated with the document, with these version histories capturing and storing revisions occurring locally at the first and second peer systems. The first and second peer systems may exchange version histories, and merge these version histories.

Claims

1. At least one computer-readable storage medium having computer-executable instructions stored thereon which, when executed by a computer, cause the computer to perform a method comprising:

receiving a representation of at least one revision to a document that is provided to a plurality of peer systems for collaborative editing;

storing a first version history of the document that captures at least the revision locally at a first one of the peer systems;

syncing the first one of the peer systems with at least a second one of the peer systems;

sending the first version history of the document to the second peer system;

receiving a second version history of the document from the second peer system, wherein the second version history stores at least one revision occurring locally at the second peer system; and

merging at least the first and second version histories.

2. The storage medium of claim 1, wherein the first version history includes representations of a plurality of versions of the document stored locally on the first peer system, wherein one of the versions include a representation of the revision, further comprising instructions for associating respective unique identifiers with the versions.

3. The storage medium of claim 2, wherein the instructions for merging the first and second version histories include instructions for combining the first and second version histories of the document into a combined version history graph, wherein the combined version history graph includes at least a plurality of states that correspond to versions of the document.

4. The storage medium of claim 3, wherein the combined version history graph includes at least one representation of a user revision to the document that transitions the document from a first one of the states to a second one of the states in response to the user revision.

5. The storage medium of claim 3, wherein the combined version history graph includes at least one representation of a system-created revision to the document that transitions the document from a first one of the states to a second one of the states in connection with merging the first and second version histories.

6. The storage medium of claim 3, wherein the combined version history graph includes at least one representation of a user revision to the document that transitions the document from a first one of the states to a second one of the states in response to the user revision.

7. The storage medium of claim 3, wherein at least one of the states is created in response to a user revision of the document.

8. The storage medium of claim 3, wherein at least one of the states is created by one of the peer systems in response to merging the first and the second version histories.

9. The storage medium of claim 1, wherein the instructions for merging at least the first and second version histories include instructions for inferring a plurality of delta operations from the combined version history graph, and for expressing the delta operations as a list.

10. The storage medium of claim 1, wherein the combined version history graph is implemented as a directed acyclic graph, and wherein the instructions for merging at least the first and second version histories include instructions for reducing the combined version history graph to a tree representation.

11. At least one computer-readable storage medium having computer-executable instructions stored thereon which, when executed by a computer, cause the computer to perform a method comprising:

syncing a first peer system with at least a second peer system, wherein the first and second peer systems are for receiving respective instances of a document for collaborative editing, and are for maintaining respective first and second version histories associated with the document, wherein the first and second version histories are for capturing and storing revisions occurring locally at the first and second peer systems;

exchanging the first and second version histories between the first and second peer systems; and

merging at least the first and second version histories.

12. The storage medium of claim 11, further comprising instructions for combining graph representations of the first and second version histories into a combined version history graph.

13. The storage medium of claim 12, further comprising instructions for reducing the combined version history graph into a tree representation.

14. The storage medium of claim 13, wherein the tree representation includes at least one leaf node, and wherein the instructions for reducing the combined version history graph into a tree representation include instructions for determining whether the leaf node represents a state that is calculated by the first peer system or the second peer system in connection with a merge operation.

15. The storage medium of claim 13, wherein the tree representation includes at least one leaf node, and further comprising instructions for removing the leaf node in response to determining that it represents a state that is calculated by the first peer system or the second peer system in connection with a merge operation.

16. The storage medium of claim 13, wherein the tree representation includes at least one node, and further comprising instructions for determining whether the node is associated with at least two immediate parents in the tree representation.

17. The storage medium of claim 16, further comprising instructions for removing all but one of the immediate parents of the node.

18. The storage medium of claim 11, further comprising instructions for creating a merged state in response to merging at least the first and second version histories, and further comprising instructions for assigning a unique identifier to the merged state, wherein the unique identifier is identical across the first and second peer systems.

19. A system comprising:

a first peer system including at least one processor and at least one computer-readable storage medium having computer-executable instructions stored thereon which, when executed by the first peer system, cause the first peer system to provide a first instance of a multi-master merge service that performs a method comprising;

receiving at least one document that is provided to a plurality of peer systems, including at least the first peer system, for collaborative editing;

receiving at least a first revision to the document;

storing at least the first revision in a first version history locally at the first peer system;

a second peer system including at least one processor and at least one computer-readable storage medium having computer-executable instructions stored thereon which, when executed by the second peer system, cause the second peer system to provide a second instance of a multi-master merge service that performs a method comprising;

receiving at least the document as provided to the peer systems, including at least the second peer system;

receiving at least a second revision to the document;

storing at least the second revision in a second version history locally at the second peer system;

syncing the second peer system with the first peer system;

sending the second version history to the first peer system;

receiving the first version history from the first peer system; and

merging the first and second version histories.

20. The system of claim 19, wherein the first and second peer systems include respective local storage elements, wherein the local storage elements contain version history information that include representations of the revisions as respectively stored on the first and second peer systems.