Overview
| SHA1 Hash: | e45d478f0c37add20a1dad418706b42745b1911e |
|---|---|
| Date: | 2009-03-20 01:23:53 |
| User: | drh |
| Comment: | Improve merge conflict markings. |
| Timelines: | ancestors | descendants | both | trunk |
| Other Links: | files | ZIP archive | manifest |
Tags And Properties
- branch=trunk inherited from [a28c83647d]
- sym-trunk inherited from [a28c83647d]
Changes
[hide diffs]Modified src/merge3.c from [e01dd37d11] to [b978e84c95].
@@ -24,18 +24,26 @@
** This module implements a 3-way merge
*/
#include "config.h"
#include "merge3.h"
-#if 0
+#if 1
#define DEBUG(X) X
+#define ISDEBUG 1
#else
#define DEBUG(X)
+#define ISDEBUG 0
#endif
/*
-** Opcodes
+** Opcodes.
+**
+** Values are important here. The text_diff() function returns an array
+** of triples of integers where within each triple, the 0 element is
+** the number of lines to copy, the 1 element is the number of lines to
+** delete and the 2 element is the number of lines to insert. The CPY,
+** DEL, and INS opcodes must correspond to these indices.
*/
#define CPY 0
#define DEL 1
#define INS 2
#define END 3
@@ -56,10 +64,13 @@
for(i=0; z1[i]!='\n' && z1[i]==z2[i]; i++){}
return z2[i]=='\n' || (z2[i]=='\r' && z2[i+1]=='\n')
|| (z1[i]=='\r' && z2[i]=='\n' && z1[i+1]=='\n');
}
+/* The minimum of two integers */
+#define min(A,B) (A<B?A:B)
+
/*
** Do a three-way merge. Initialize pOut to contain the result.
**
** The merge is an edit against pV2. Both pV1 and pV2 have a
** common origin at pPivot. Apply the changes of pPivot ==> pV1
@@ -69,33 +80,41 @@
** -1 is returned and pOut is unmodified. If there are merge
** conflicts, the merge proceeds as best as it can and the number
** of conflicts is returns
*/
int blob_merge(Blob *pPivot, Blob *pV1, Blob *pV2, Blob *pOut){
- int *aC1; /* Changes from pPivot to pV1 */
- int *aC2; /* Changes from pPivot to pV2 */
- int i1, i2;
- int op1, op2;
- int limit1, limit2;
- int inConflict = 0;
- int nConflict = 0;
- static const char zBegin[] = ">>>>>>>> BEGIN MERGE CONFLICT <<<<<<<<\n";
- static const char zEnd[] = ">>>>>>>>> END MERGE CONFLICT <<<<<<<<<\n";
+ int *aC1; /* Changes from pPivot to pV1 */
+ int *aC2; /* Changes from pPivot to pV2 */
+ int i1, i2; /* Index into aC1[] and aC2[] */
+ int op1, op2; /* Opcode for aC1[] and aC2[] */
+ int n1, n2; /* Counts for op1 and op2 */
+ int mn; /* Minimum count of op1 and op2 */
+ int limit1, limit2; /* Sizes of aC1[] and aC2[] */
+ int nConflict = 0; /* Number of merge conflicts seen so far */
+ static const char zBegin[] = ">>>>>>> BEGIN MERGE CONFLICT\n";
+ static const char zMid[] = "============================\n";
+ static const char zEnd[] = "<<<<<<< END MERGE CONFLICT\n";
+
+#if ISDEBUG
+ static const char *zOp[] = { "CPY", "DEL", "INS", "END", "UNK" };
+#endif
+ /* Compute the edits that occur from pPivot => pV1 and pPivot => pV2 */
aC1 = text_diff(pPivot, pV1, 0, 0);
aC2 = text_diff(pPivot, pV2, 0, 0);
-
if( aC2==0 || aC2==0 ){
free(aC1);
free(aC2);
return -1;
}
- blob_zero(pOut);
- blob_rewind(pV1);
+
+ blob_zero(pOut); /* Merge results stored in pOut */
+ blob_rewind(pV1); /* Rewind inputs: Needed to reconstruct output */
blob_rewind(pV2);
blob_rewind(pPivot);
+ /* Determine the length of the aC1[] and aC2[] change vectors */
for(i1=0; aC1[i1] || aC1[i1+1] || aC1[i1+2]; i1+=3){}
limit1 = i1;
for(i2=0; aC2[i2] || aC2[i2+1] || aC2[i2+2]; i2+=3){}
limit2 = i2;
@@ -107,100 +126,136 @@
printf("c2: %4d %4d %4d\n", aC2[i2], aC2[i2+1], aC2[i2+2]);
}
)
op1 = op2 = UNK;
- i1 = i2 = 0;
- while( i1<limit1 && aC1[i1]==0 ){ i1++; }
- while( i2<limit2 && aC2[i2]==0 ){ i2++; }
-
+ i1 = i2 = -1;
+ n1 = n2 = 0;
while(1){
if( op1==UNK ){
- if( i1>=limit1 ){
- op1 = END;
- DEBUG( printf("get op1=END\n"); )
+ if( n1 ){
+ op1 = i1 % 3;
}else{
- op1 = i1 % 3;
- aC1[i1]--;
- DEBUG( printf("get op1=%d from %d (%d->%d)\n",
- op1,i1,aC1[i1]+1,aC1[i1]); )
+ i1++;
while( i1<limit1 && aC1[i1]==0 ){ i1++; }
+ if( i1>=limit1 ){
+ op1 = END;
+ }else{
+ op1 = i1 % 3;
+ n1 = aC1[i1];
+ }
}
}
if( op2==UNK ){
- if( i2>=limit2 ){
- op2 = END;
- DEBUG( printf("get op2=END\n"); )
+ if( n2 ){
+ op2 = i2 % 3;
}else{
- op2 = i2 % 3;
- aC2[i2]--;
- DEBUG( printf("get op2=%d from %d (%d->%d)\n",
- op2,i2,aC2[i2]+1,aC2[i2]); )
+ i2++;
while( i2<limit2 && aC2[i2]==0 ){ i2++; }
+ if( i2>=limit2 ){
+ op2 = END;
+ }else{
+ op2 = i2 % 3;
+ n2 = aC2[i2];
+ }
}
}
- DEBUG( printf("op1=%d op2=%d\n", op1, op2); )
+ DEBUG( printf("op1=%s(%d) op2=%s(%d)\n", zOp[op1], n1, zOp[op2], n2); )
if( op1==END ){
if( op2==INS ){
- blob_copy_lines(pOut, pV2, 1);
- op2 = UNK;
- }else{
- break;
+ DEBUG( printf("INSERT %d FROM 2\n", n2); )
+ blob_copy_lines(pOut, pV2, n2);
}
+ break;
}else if( op2==END ){
if( op1==INS ){
- blob_copy_lines(pOut, pV1, 1);
- op1 = UNK;
- }else{
- break;
+ DEBUG( printf("INSERT %d FROM 1\n", n1); )
+ blob_copy_lines(pOut, pV1, n1);
}
- }else if( op1==INS && op2==INS ){
- if( !inConflict && sameLine(pV1, pV2) ){
- blob_copy_lines(pOut, pV2, 1);
- blob_copy_lines(0, pV1, 0);
- op1 = UNK;
- op2 = UNK;
- }else{
- if( !inConflict ){
- inConflict = 1;
- nConflict++;
- blob_appendf(pOut, zBegin);
- }
- blob_copy_lines(pOut, pV1, 1);
- op1 = UNK;
- }
- }else if( op1==INS ){
- blob_copy_lines(pOut, pV1, 1);
- op1 = UNK;
- }else if( op2==INS ){
+ break;
+ }else if( op1==CPY && op2==CPY ){
+ mn = min(n1,n2);
+ DEBUG( printf("COPY %d\n", mn); )
+ blob_copy_lines(pOut, pPivot, mn);
+ blob_copy_lines(0, pV1, mn);
+ blob_copy_lines(0, pV2, mn);
+ n1 -= mn;
+ n2 -= mn;
+ op1 = op2 = UNK;
+ }else if( op1==DEL && op2==DEL ){
+ mn = min(n1,n2);
+ DEBUG( printf("SKIP %d both\n", mn); )
+ blob_copy_lines(0, pPivot, mn);
+ n1 -= mn;
+ n2 -= mn;
+ op1 = op2 = UNK;
+ }else if( op1==INS && op2==INS && sameLine(pV1, pV2) ){
+ DEBUG( printf("DUPLICATE INSERT\n"); )
blob_copy_lines(pOut, pV2, 1);
+ blob_copy_lines(0, pV1, 1);
+ n1--;
+ n2--;
+ op1 = op2 = UNK;
+ }else if( op1==CPY && op2==DEL ){
+ mn = min(n1,n2);
+ DEBUG( printf("SKIP %d two\n", mn); )
+ blob_copy_lines(0, pPivot, mn);
+ blob_copy_lines(0, pV1, mn);
+ n1 -= mn;
+ n2 -= mn;
+ op1 = op2 = UNK;
+ }else if( op2==CPY && op1==DEL ){
+ mn = min(n1,n2);
+ DEBUG( printf("SKIP %d one\n", mn); )
+ blob_copy_lines(0, pPivot, mn);
+ blob_copy_lines(0, pV2, mn);
+ n2 -= mn;
+ n1 -= mn;
+ op1 = op2 = UNK;
+ }else if( op1==CPY && op2==INS ){
+ DEBUG( printf("INSERT %d two\n", n2); )
+ blob_copy_lines(pOut, pV2, n2);
+ n2 = 0;
op2 = UNK;
+ }else if( op2==CPY && op1==INS ){
+ DEBUG( printf("INSERT %d one\n", n1); )
+ blob_copy_lines(pOut, pV1, n1);
+ n1 = 0;
+ op1 = UNK;
}else{
- if( inConflict ){
- inConflict = 0;
- blob_appendf(pOut, zEnd);
- }
- if( op1==DEL || op2==DEL ){
- blob_copy_lines(0, pPivot, 1);
- if( op2==CPY ){
- blob_copy_lines(0, pV2, 1);
+ int toSkip = 0;
+ nConflict++;
+ DEBUG( printf("CONFLICT\n"); )
+ blob_appendf(pOut, zBegin);
+ if( op1==DEL ){
+ toSkip = n1;
+ i1++;
+ if( aC1[i1] ){
+ blob_copy_lines(pOut, pV1, aC1[i1]);
}
- if( op1==CPY ){
- blob_copy_lines(0, pV1, 1);
+ }else{
+ blob_copy_lines(pOut, pV1, n1);
+ }
+ n1 = 0;
+ op1 = UNK;
+ blob_appendf(pOut, zMid);
+ if( op2==DEL ){
+ blob_copy_lines(0, pPivot, n2);
+ i2++;
+ if( aC2[i2] ){
+ blob_copy_lines(pOut, pV2, aC2[i2]);
}
}else{
- assert( op1==CPY && op2==CPY );
- blob_copy_lines(pOut, pPivot, 1);
- blob_copy_lines(0, pV1, 1);
- blob_copy_lines(0, pV2, 1);
+ blob_copy_lines(pOut, pV2, n2);
+ }
+ if( toSkip ){
+ blob_copy_lines(0, pPivot, toSkip);
}
- op1 = UNK;
+ n2 = 0;
op2 = UNK;
- }
- }
- if( inConflict ){
- blob_appendf(pOut, zEnd);
+ blob_appendf(pOut, zEnd);
+ }
}
free(aC1);
free(aC2);
return nConflict;