SHA1 Hash:	3e89b0c52648512790ae4c02101e2a25c520a502
Date:	2009-03-22 12:25:59
User:	drh
Comment:	Fix a bug in error recovery logic in the 3-way merge. Added new comments to the 3-way merge code to hopefully make it easier to understand.
Timelines:	ancestors | descendants | both | trunk
Other Links:	files | ZIP archive | manifest

• branch=trunk inherited from [a28c83647d]
• sym-trunk inherited from [a28c83647d]

Modified src/merge3.c from [137ba3bf55] to [61efa8a333].

@@ -37,13 +37,14 @@
 /* The minimum of two integers */
 #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;
 
@@ -58,15 +59,22 @@
   }
   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;
   return 0;
@@ -78,11 +86,11 @@
 **
 **   (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){
   while( sz>0 && (aC[0]>0 || aC[1]>0 || aC[2]>0) ){
@@ -98,10 +106,15 @@
 /*
 ** 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(
   Blob *pOut,     /* Write to this blob */
@@ -148,14 +161,21 @@
   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";
 
-  /* 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;
   }
 
@@ -177,26 +197,33 @@
     for(i2=0; i2<limit2; i2+=3){
      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);
       blob_copy_lines(0, pV2, nCpy);
       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);
       blob_copy_lines(0, pV1, nDel);
@@ -203,10 +230,11 @@
       blob_copy_lines(pOut, pV2, nIns);
       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);
       blob_copy_lines(0, pV2, nDel);
@@ -213,10 +241,11 @@
       blob_copy_lines(pOut, pV1, nIns);
       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); )
       blob_copy_lines(0, pPivot, nDel);
@@ -224,10 +253,14 @@
       blob_copy_lines(0, pV2, nIns);
       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++;
       }
@@ -237,13 +270,22 @@
       blob_appendf(pOut, zMid);
       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 ){
     DEBUG( printf("INSERT +%d left\n", aC1[i1+2]); )