Fossil

** The aC[] array is updated and the new index into aC[] is returned.
*/
static int output_one_side(
  Blob *pOut,     /* Write to this blob */
  Blob *pSrc,     /* The edited file that is to be copied to pOut */
  int *aC,        /* Array of integer triples describing the edit */
  int i,          /* Index in aC[] of current location in pSrc */
  int sz,         /* Number of lines in unedited source to output */
  int *pLn        /* Line number counter */
){
  while( sz>0 ){
    if( aC[i]==0 && aC[i+1]==0 && aC[i+2]==0 ) break;
    if( aC[i]>=sz ){
      blob_copy_lines(pOut, pSrc, sz);  *pLn += sz;
      aC[i] -= sz;
      break;
    }
    blob_copy_lines(pOut, pSrc, aC[i]);      *pLn += aC[i];
    blob_copy_lines(pOut, pSrc, aC[i+2]);    *pLn += aC[i+2];
    sz -= aC[i] + aC[i+1];
    i += 3;
  }
  return i;
}

/*
** Text of boundary markers for merge conflicts.
*/
static const char *const mergeMarker[] = {
 /*123456789 123456789 123456789 123456789 123456789 123456789 123456789*/
  "<<<<<<< BEGIN MERGE CONFLICT: local copy shown first <<<<<<<<<<<<",
  "||||||| COMMON ANCESTOR content follows |||||||||||||||||||||||||",
  "======= MERGED IN content follows ===============================",
  ">>>>>>> END MERGE CONFLICT >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"
};

/*
** Return true if the input blob contains any CR/LF pairs on the first
** ten lines. This should be enough to detect files that use mainly CR/LF
** line endings without causing a performance impact for LF only files.
*/

void ensure_line_end(Blob *pBlob, int useCrLf){
  if( pBlob->nUsed<=0 ) return;
  if( pBlob->aData[pBlob->nUsed-1]!='\n' ){
    if( useCrLf ) blob_append_char(pBlob, '\r');
    blob_append_char(pBlob, '\n');
  }
}

/*
** Write out one of the four merge-marks.
*/
void append_merge_mark(Blob *pOut, int iMark, int ln, int useCrLf){
  ensure_line_end(pOut, useCrLf);
  blob_append(pOut, mergeMarker[iMark], -1);
  if( ln>0 ) blob_appendf(pOut, " (line %d)", ln);
  ensure_line_end(pOut, useCrLf);
}

/*
** 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
** to pV2.

  int *aC1;              /* Changes from pPivot to pV1 */
  int *aC2;              /* Changes from pPivot to pV2 */
  int i1, i2;            /* Index into aC1[] and aC2[] */
  int nCpy, nDel, nIns;  /* Number of lines to copy, delete, or insert */
  int limit1, limit2;    /* Sizes of aC1[] and aC2[] */
  int nConflict = 0;     /* Number of merge conflicts seen so far */
  int useCrLf = 0;
  int ln1, ln2, lnPivot; /* Line numbers for all files */
  DiffConfig DCfg;

  blob_zero(pOut);         /* Merge results stored in pOut */
  
  /* If both pV1 and pV2 start with a UTF-8 byte-order-mark (BOM),
  ** keep it in the output. This should be secure enough not to cause
  ** unintended changes to the merged file and consistent with what

  /* 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;
  ln1 = ln2 = lnPivot = 1;
  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); lnPivot += nCpy;
      blob_copy_lines(0, pV1, nCpy);       ln1 += nCpy;
      blob_copy_lines(0, pV2, nCpy);       ln2 += 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);    lnPivot += nDel;
      blob_copy_lines(0, pV1, nDel);       ln1 += nDel;
      blob_copy_lines(pOut, pV2, nIns);    ln2 += 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);    lnPivot += nDel;
      blob_copy_lines(0, pV2, nDel);       ln2 += nDel;
      blob_copy_lines(pOut, pV1, nIns);    ln1 += 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);    lnPivot += nDel;
      blob_copy_lines(pOut, pV1, nIns);    ln1 += nIns;
      blob_copy_lines(0, pV2, nIns);       ln2 += 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 separated 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++;
      }
      DEBUG( printf("CONFLICT %d\n", sz); )


      append_merge_mark(pOut, 0, ln1, useCrLf);
      i1 = output_one_side(pOut, pV1, aC1, i1, sz, &ln1);


      append_merge_mark(pOut, 1, lnPivot, useCrLf);
      blob_copy_lines(pOut, pPivot, sz);   lnPivot += sz;


      append_merge_mark(pOut, 2, ln2, useCrLf);
      i2 = output_one_side(pOut, pV2, aC2, i2, sz, &ln2);


      append_merge_mark(pOut, 3, -1, useCrLf);
   }

    /* 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;

  int n = blob_size(p) - len + 1;
  assert( len==(int)strlen(mergeMarker[1]) );
  assert( len==(int)strlen(mergeMarker[2]) );
  assert( len==(int)strlen(mergeMarker[3]) );
  assert( count(mergeMarker)==4 );
  for(i=0; i<n; ){
    for(j=0; j<4; j++){
      if( (memcmp(&z[i], mergeMarker[j], len)==0) ){
        return 1;
      }
    }
    while( i<n && z[i]!='\n' ){ i++; }
    while( i<n && (z[i]=='\n' || z[i]=='\r') ){ i++; }
  }
  return 0;
}