@@ -38,11 +38,12 @@
#define min(A,B) (A<B?A:B)
/*
** Compare N lines of text from pV1 and pV2. If the lines
-** are the same, return true. Return false if they are different.
+** are the same, return true. Return false if one or more of the N
+** lines are different.
**
-** The cursor on both pV1 and pV2 is unchanged.
+** The cursors on both pV1 and pV2 is unchanged by this comparison.
*/
static int sameLines(Blob *pV1, Blob *pV2, int N){
char *z1, *z2;
int i;
@@ -59,13 +60,20 @@
return 0;
}
/*
-** Look at the next edit triple in both aC1 and aC2. If they describe
-** an identical edit, then return 1. If the edits are different,
-** return 0.
+** Look at the next edit triple in both aC1 and aC2. (An "edit triple" is
+** three integers describing the number of copies, deletes, and inserts in
+** moving from the original to the edited copy of the file.) If the three
+** integers of the edit triples describe an identical edit, then return 1.
+** If the edits are different, return 0.
*/
-static int sameEdit(int *aC1, int *aC2, Blob *pV1, Blob *pV2){
+static int sameEdit(
+ int *aC1, /* Array of edit integers for file 1 */
+ int *aC2, /* Array of edit integers for file 2 */
+ Blob *pV1, /* Text of file 1 */
+ Blob *pV2 /* Text of file 2 */
+){
if( aC1[0]!=aC2[0] ) return 0;
if( aC1[1]!=aC2[1] ) return 0;
if( aC1[2]!=aC2[2] ) return 0;
if( sameLines(pV1, pV2, aC1[2]) ) return 1;
@@ -79,9 +87,9 @@
** (0) The number of lines to copy
** (1) The number of lines to delete
** (2) The number of liens to insert
**
-** Suppose we want to advance over sz lines of the pivot. This routine
+** Suppose we want to advance over sz lines of the originl file. This routine
** returns true if that advance would land us on a copy operation. It
** returns false if the advance would end on a delete.
*/
static int ends_at_CPY(int *aC, int sz){
@@ -99,8 +107,13 @@
** pSrc contains an edited file where aC[] describes the edit. Part of
** pSrc has already been output. This routine outputs additional lines
** of pSrc - lines that correspond to the next sz lines of the original
** unedited file.
+**
+** Note that sz counts the number of lines of text in the original file.
+** But text is output from the edited file. So the number of lines transfer
+** to pOut might be different from sz. Fewer lines appear in pOut if there
+** are deletes. More lines appear if there are inserts.
**
** The aC[] array is updated and the new index into aC[] is returned.
*/
static int output_one_side(
@@ -149,12 +162,19 @@
static const char zBegin[] = ">>>>>>> BEGIN MERGE CONFLICT\n";
static const char zMid[] = "============================\n";
static const char zEnd[] = "<<<<<<< END MERGE CONFLICT\n";
- /* Compute the edits that occur from pPivot => pV1 and pPivot => pV2 */
+ /* Compute the edits that occur from pPivot => pV1 (into aC1)
+ ** and pPivot => pV2 (into aC2). Each of the aC1 and aC2 arrays is
+ ** an array of integer triples. Within each triple, the first integer
+ ** is the number of lines of text to copy directly from the pivot,
+ ** the second integer is the number of lines of text to omit from the
+ ** pivot, and the third integer is the number of lines of text that are
+ ** inserted. The edit array ends with a triple of 0,0,0.
+ */
aC1 = text_diff(pPivot, pV1, 0, 0);
aC2 = text_diff(pPivot, pV2, 0, 0);
- if( aC2==0 || aC2==0 ){
+ if( aC1==0 || aC2==0 ){
free(aC1);
free(aC2);
return -1;
}
@@ -178,15 +198,21 @@
printf("c2: %4d %4d %4d\n", aC2[i2], aC2[i2+1], aC2[i2+2]);
}
)
+ /* Loop over the two edit vectors and use them to compute merged text
+ ** which is written into pOut. i1 and i2 are multiples of 3 which are
+ ** indices into aC1[] and aC2[] to the edit triple currently being
+ ** processed
+ */
i1 = i2 = 0;
while( i1<limit1 && i2<limit2 ){
DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
if( aC1[i1]>0 && aC2[i2]>0 ){
+ /* Output text that is unchanged in both V1 and V2 */
nCpy = min(aC1[i1], aC2[i2]);
DEBUG( printf("COPY %d\n", nCpy); )
blob_copy_lines(pOut, pPivot, nCpy);
blob_copy_lines(0, pV1, nCpy);
@@ -194,8 +220,9 @@
aC1[i1] -= nCpy;
aC2[i2] -= nCpy;
}else
if( aC1[i1] >= aC2[i2+1] && aC1[i1]>0 && aC2[i2+1]+aC2[i2+2]>0 ){
+ /* Output edits to V2 that occurs within unchanged regions of V1 */
nDel = aC2[i2+1];
nIns = aC2[i2+2];
DEBUG( printf("EDIT -%d+%d left\n", nDel, nIns); )
blob_copy_lines(0, pPivot, nDel);
@@ -204,8 +231,9 @@
aC1[i1] -= nDel;
i2 += 3;
}else
if( aC2[i2] >= aC1[i1+1] && aC2[i2]>0 && aC1[i1+1]+aC1[i1+2]>0 ){
+ /* Output edits to V1 that occur within unchanged regions of V2 */
nDel = aC1[i1+1];
nIns = aC1[i1+2];
DEBUG( printf("EDIT -%d+%d right\n", nDel, nIns); )
blob_copy_lines(0, pPivot, nDel);
@@ -214,8 +242,9 @@
aC2[i2] -= nDel;
i1 += 3;
}else
if( sameEdit(&aC1[i1], &aC2[i2], pV1, pV2) ){
+ /* Output edits that are identical in both V1 and V2. */
assert( aC1[i1]==0 );
nDel = aC1[i1+1];
nIns = aC1[i1+2];
DEBUG( printf("EDIT -%d+%d both\n", nDel, nIns); )
@@ -225,8 +254,12 @@
i1 += 3;
i2 += 3;
}else
{
+ /* We have found a region where different edits to V1 and V2 overlap.
+ ** This is a merge conflict. Find the size of the conflict, then
+ ** output both possible edits separate by distinctive marks.
+ */
int sz = 1; /* Size of the conflict in lines */
nConflict++;
while( !ends_at_CPY(&aC1[i1], sz) || !ends_at_CPY(&aC2[i2], sz) ){
sz++;
@@ -238,11 +271,20 @@
i2 = output_one_side(pOut, pV2, aC2, i2, sz);
blob_appendf(pOut, zEnd);
blob_copy_lines(0, pPivot, sz);
}
+
+ /* If we are finished with an edit triple, advance to the next
+ ** triple.
+ */
if( i1<limit1 && aC1[i1]==0 && aC1[i1+1]==0 && aC1[i1+2]==0 ) i1+=3;
if( i2<limit2 && aC2[i2]==0 && aC2[i2+1]==0 && aC2[i2+2]==0 ) i2+=3;
}
+
+ /* When one of the two edit vectors reaches its end, there might still
+ ** be an insert in the other edit vector. Output this remaining
+ ** insert.
+ */
DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
if( i1<limit1 && aC1[i1+2]>0 ){