Semantic diff and automerge

Patent metadata

Field	Value
Publication number	US-10949612-B2
Application number	US-201615376085-A
Country	US
Kind code	B2
Filing date	Dec 12, 2016
Priority date	Mar 30, 2012
Publication date	Mar 16, 2021
Grant date	Mar 16, 2021

Abstract

Resolving conflicting changes to structured data files. A method includes for a structured data file which has both a generic structure and dialects built on top of the generic structure, for which conflicting changes have been made, and where an original version of the structured data, a first version of the structured data and a second version of the structured data exist, determining a dialect of the structured data. The method further includes, based on the determined dialect performing at least one of merge or diff operations on the original version of the structured data, the first version of the structured data and the second version of the structured data.

First claim

What is claimed is:

1. In a computing environment, a method of resolving conflicting changes to structured data files, the method comprising:
for a structured data file which has both a generic structure and dialects built on top of the generic structure, for which conflicting changes have been made, and where an original version of the structured data, a first version of the structured data and a second version of the structured data exist:
determining a dialect that is used for the structured data, the determined dialect imposing semantic rules for determining differences in the structured data; and
based on the determined dialect,
performing a two-way diff comprising:
determining a set of differences, diff1, between the original version of the structured data and the first version of the structured data,
determining a second set of differences, diff2, between the original version of the structured data and the second version of the structured data, and

performing a three-way diff comprising:
traversing diff1 to:
determine changes in diff1 which do not conflict with changes in diff2, and
determine changes in diff1 which do conflict with changes in diff2, and

traversing diff2 to:
determine changes in diff2 which do not conflict with changes in diff1, and
determine changes in diff2 which do conflict with changes in diff1; and

performing a merge by:
applying to the original version of the structured data non-conflicting changes in the differences between the original version and the first version and differences between the original version and the second version; and
resolving conflicts between the differences between the original version and the first version and differences between the original version and the second version.

2. The method of claim 1 further comprising:
identifying a rule file associated with the determined dialect;
using the rule file, identifying different subsets of one or more of the three versions of the structured data file and at least one of different merge or diff rules associated with the different subsets of one or more of the three versions of the structured data file; and
applying the different rules to the different subsets of one or more of the three versions of the structured data file.

3. The method of claim 2 , wherein using the rule file identifying different subsets of one or more of the three versions of the structured data file and at least one of different merge or diff rules associated with the different subsets of one or more of the three versions of the structured data the file, comprises following an Xpath expression.

4. The method of claim 2 , wherein the rule file comprises a rule specifying that a merge is not resolved for a particular subset of one or more of the three versions of the structured data file.

5. The method of claim 2 , wherein the rule file comprises a rule specifying that order matters for at least one of merge or diff operations for a particular subset of one or more of the three versions of the structured data file.

6. The method of claim 2 , wherein the rule file comprises a rule specifying that order does not matter for at least one of merge or diff operations for a particular subset of one or more of the three versions of the structured data file.

7. The method of claim 2 , wherein the rule file comprises a rule specifying that differences in specific identified attributes do not matter for at least one of merge or diff operations for a particular subset of one or more of the three versions of the structured data file.

8. The method of claim 2 , wherein the rule file comprises a rule specifying a subset of one or more of the three versions of the structured data file as requiring uniqueness such that two or more modified data items with the same unique identifier are in conflict.

9. The method of claim 8 , further comprising resolving the conflict by creating one or more new unique identifiers.

10. The method of claim 2 , wherein the rule file comprises a rule specifying that a particular portion of one or more of the three versions of the structured data file should not be semantically merged.

11. The method of claim 1 wherein determining a dialect comprises examining a description document.

12. The method of claim 1 wherein determining a dialect comprises examining the structured text data file.

13. The method of claim 1 further comprising automatically generating rules for at least one of semantic merge or diff operations based on previously existing semantic format descriptions for structured data.

14. The method of claim 1 , wherein the dialect specifies a related set of structured textual data to be operated on.

15. The method of claim 1 , further comprising merging the different versions while preserving human context recognizability.

16. The method of claim 15 wherein merging the different versions while preserving human context recognizability comprises preserving whitespace structure across the file.

17. The method of claim 15 wherein merging the different versions while preserving human context recognizability comprises preserving comment adjacency.

18. One or more computer readable storage devices comprising computer executable instructions that when executed by one or more processors cause one or more processors to perform the following:
for a structured data file which has both a generic structure and dialects built on top of the generic structure, for which conflicting changes have been made, and where an original version of the structured data, a first version of the structured data and a second version of the structured data exist, determining a dialect of the structured data, the determined dialect imposing semantic rules for determining differences in the structured data; and
based on the determined dialect,
performing a two-way diff comprising:
determining a set of differences, diff1, between the original version of the structured data and the first version of the structured data,
determining a second set of differences, diff2, between the original version of the structured data and the second version of the structured data, and

performing a three-way diff comprising:
traversing diff1 to:
determine changes in diff1 which do not conflict with changes in diff2, and
determine changes in diff1 which do conflict with changes in diff2, and

traversing diff2 to:
determine changes in diff2 which do not conflict with changes in diff1, and
determine changes in diff2 which do conflict with changes in diff1; and

performing a merge by:
applying to the original version of the structured data non-conflicting changes in the differences between the original version and the first version and differences between the original version and the second version and
resolving conflicts between the differences between the original version and the first version and differences between the original version and the second version.

19. In a computing environment, a system for resolving conflicting changes to structured data files, the system comprising:
one or more computer processors; and
computer readable memory having stored therein computer executable instructions which, when executed on the one or more processors, configures the system to instantiate:
a file repository configured to store a latest version of a structured text data file and to check the latest version of the structured text data file out to users, wherein the latest version of the structured text data file is an authoritative version of the struc

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Kilian David Charles
• Millott Louisa Rose
• Jones Gareth Alun
• Bragdon Andrew Craig
• Xiao Yu
• Abraham Arun Mathew
• Blasko Kevin J
• Lovett Christopher
• Groves Mark

Classifications

• G06F40/197 Primary

  Version control (for software G06F8/71) · CPC title

• G06F16/1767

  Concurrency control, e.g. optimistic or pessimistic approaches · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F40/205

  Parsing · CPC title

• G06F40/143

  Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD] · CPC title