US 10,558,737 B2Granted

Generating a semantic diff

AssigneeGitHub, Inc.

InventorsRob Rix, Rick Winfrey, Joshua Evan Vera, Timothy Evan Clem

Life of this patent

Estimating the term…

Loading patent…

Abstract

Generation of a semantic diff is described. A machine according to some example embodiments generates first and second parse trees by parsing the first and second documents using a grammar of a coding language common to both documents. The machine classifies subtrees within these parse trees and determines that a first subtree from the first document shares a classification with a second subtree from the second document. Based on their sharing of the classification, the machine selects these two subtrees for comparison to each other and also chooses a comparison procedure based on the shared classification. The machine then executes the selected comparison procedure with the selected two subtrees as input and generates a differential subtree that indicates one or more differences between the two subtrees. The machine may also generate a differential tree that indicates differences between the entireties of the first and second documents.

Claims25

Dependent claims

A method comprising:

accessing, by one or more processors, a first text document and a second text document both written in a coding language that is common to both;
determining the coding language is one of a plurality of programming languages, wherein each of the plurality of programming languages uniquely corresponds to at least one of a language specific specification or a language specific or grammar stored in a storage device that is accessible by the one or more processors;
accessing the at least one of the specification or the grammar corresponding to the determined coding language, by the one or more processors;
based on the accessed at least one of the specification or the grammar:
generating, by the one or more processors, a first parse tree and a second parse tree by parsing the accessed first text document and the second text document, respectively, based on a grammar of the coding language common to the first text document and the second text document, the first parse tree including a first plurality of subtrees, the second parse tree including a second plurality of subtrees;
and
determining, by the one or more processors, that a first subtree in the first plurality of subtrees shares a classification with a second subtree in the second plurality of subtrees by classifying the first subtree and the second subtree based on a set of classifications that includes the shared classification;
selecting, by the one or more processors, the first subtree and the second subtree for comparison to each other based on the determining that the first subtree shares the classification with the second subtree;
mapping each one of the set of classifications to one of a plurality of available comparison procedures that is applicable to the corresponding classification;
selecting, by the one or more processors, a comparison procedure from the plurality of available comparison procedures applicable to the first subtree and the second subtree based on the classification shared by the first subtree and the second subtree;
and
generating, by the one or more processors, a differential subtree by performing the selected comparison procedure on the first subtree and the second subtree, the generated differential subtree indicating a textual difference between the first subtree and the second subtree.

9 more elements

A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are executable by one or more processors of a machine, cause the machine to perform operations comprising:

accessing a first text document and a second text document both written in a coding language that is common to both;
determining the coding language is one of a plurality of programming languages, wherein each of the plurality of coding languages uniquely corresponds to at least one of a language specific specification or a language specific grammar stored in a storage device that is accessible by the one or more processors;
accessing the at least one of the specification or the grammar corresponding to the determined coding language, by the one or more processors;
based on the accessed at least one of the specification or the grammar:
generating a first parse tree and a second parse tree by parsing the accessed first text document and the second text document, respectively, based on a grammar of the coding language common to the first text document and the second text document, the first parse tree including a first plurality of subtrees, the second parse tree including a second plurality of subtrees;
and
determining that a first subtree in the first plurality of subtrees shares a classification with a second subtree in the second plurality of subtrees by classifying the first subtree and the second subtree based on a set of classifications that includes the shared classification;
selecting the first subtree and the second subtree for comparison to each other based on the determining that the first subtree shares the classification with the second subtree;
mapping each one of the set of classification to one of a plurality of available comparison procedures that is applicable to the corresponding classification;
selecting a comparison procedure from the plurality of available comparison procedures applicable to the first subtree and the second subtree based on the classification shared by the first subtree and the second subtree;
and
generating a differential subtree by performing the selected comparison procedure on the first subtree and the second subtree, the generated differential subtree indicating a textual difference between the first subtree and the second subtree.

9 more elements

A system comprising:

one or more processors;
and
a memory storing instructions that, when executed by at least one processor among the one or more processors, cause the system to perform operations comprising:
accessing a first text document and a second text document both written in a coding language that is common to both;
determining the coding language is one of a plurality of programming languages, wherein each of the plurality of programming languages uniquely corresponds to at least one of a language specific specification or a language specific grammar stored in a storage device that is accessible by the one or more processors;
accessing the at least one of the specification or the grammar corresponding to the determined coding language, by the one or more processors;
based on the accessed at least one of the specification or the grammar:
generating a first parse tree and a second parse tree by parsing the accessed first text document and the second text document, respectively, the first parse tree including a first plurality of subtrees, the second parse tree including a second plurality of subtrees;
and
determining that a first subtree in the first plurality of subtrees shares a classification with a second subtree in the second plurality of subtrees by classifying the first subtree and the second subtree based on a set of classifications that includes the shared classification;
selecting the first subtree and the second subtree for comparison to each other based on the determining that the first subtree shares the classification with the second subtree;
mapping each one of the set of classifications to one of a plurality of available comparison procedures that is applicable to the corresponding classification;
selecting a comparison procedure from the plurality of available comparison procedures applicable to the first subtree and the second subtree based on the classification shared by the first subtree and the second subtree;
and
generating a differential subtree by performing the selected comparison procedure on the first subtree and the second subtree, the generated differential subtree indicating a textual difference between the first subtree and the second subtree.

12 more elements

Dependencies are inferred from the claim text.