merge3.c
1 /*- 2 * Copyright (c) 2014 Baptiste Daroussin <bapt@FreeBSD.org> 3 * All rights reserved. 4 *~ 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer 10 * in this position and unchanged. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 *~ 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 /* 28 * This code has been extracted from the fossil scm code 29 * and modified 30 */ 31 32 /* 33 ** Copyright (c) 2007 D. Richard Hipp 34 ** 35 ** This program is free software; you can redistribute it and/or 36 ** modify it under the terms of the Simplified BSD License (also 37 ** known as the "2-Clause License" or "FreeBSD License".) 38 39 ** This program is distributed in the hope that it will be useful, 40 ** but without any warranty; without even the implied warranty of 41 ** merchantability or fitness for a particular purpose. 42 ** 43 ** Author contact information: 44 ** drh@hwaci.com 45 ** http://www.hwaci.com/drh/ 46 ** 47 ******************************************************************************* 48 ** 49 ** This module implements a 3-way merge 50 */ 51 52 #include <sys/types.h> 53 #include <xstring.h> 54 55 #include <string.h> 56 #include <stdlib.h> 57 #include <stdio.h> 58 59 #include "private/utils.h" 60 61 /* The minimum of two integers */ 62 #ifndef min 63 # define min(A,B) (A<B?A:B) 64 #endif 65 66 /* 67 ** Compare N lines of text from pV1 and pV2. If the lines 68 ** are the same, return true. Return false if one or more of the N 69 ** lines are different. 70 ** 71 ** The cursors on both pV1 and pV2 is unchanged by this comparison. 72 */ 73 static int sameLines(const char *pV1, const char *pV2, int N){ 74 int i; 75 char c; 76 77 if( N==0 ) return 1; 78 for(i=0; (c=pV1[i])==pV2[i]; i++){ 79 if( c=='\n' || c==0 ){ 80 N--; 81 if( N==0 || c==0 ) return 1; 82 } 83 } 84 return 0; 85 } 86 87 /* 88 ** Look at the next edit triple in both aC1 and aC2. (An "edit triple" is 89 ** three integers describing the number of copies, deletes, and inserts in 90 ** moving from the original to the edited copy of the file.) If the three 91 ** integers of the edit triples describe an identical edit, then return 1. 92 ** If the edits are different, return 0. 93 */ 94 static int sameEdit( 95 int *aC1, /* Array of edit integers for file 1 */ 96 int *aC2, /* Array of edit integers for file 2 */ 97 const char *pV1, /* Text of file 1 */ 98 const char *pV2 /* Text of file 2 */ 99 ){ 100 if( aC1[0]!=aC2[0] ) return 0; 101 if( aC1[1]!=aC2[1] ) return 0; 102 if( aC1[2]!=aC2[2] ) return 0; 103 if( sameLines(pV1, pV2, aC1[2]) ) return 1; 104 return 0; 105 } 106 107 /* 108 ** Copy N lines of text from from into to. 109 ** The return value is the number of characters copied, normally including 110 ** the \n and should be used to advance the 'from' pointer. 111 ** 112 ** If to==NULL then this routine simply counts characters for N lines. 113 */ 114 115 static int 116 buf_copy_lines(xstring *to, const char *from, int N) 117 { 118 int cnt = 0; 119 int i; 120 121 if (N == 0) 122 return (0); 123 i = 0; 124 while (from[i] != 0) { 125 if (from[i] == '\n') { 126 cnt++; 127 if (cnt == N) { 128 i++; 129 break; 130 } 131 } 132 i++; 133 } 134 if (to) 135 fwrite(from, i, 1, to->fp); 136 return (i); 137 } 138 139 /* 140 ** Do a three-way merge. Initialize pOut to contain the result. 141 ** 142 ** The merge is an edit against pV2. Both pV1 and pV2 have a 143 ** common origin at pPivot. Apply the changes of pPivot ==> pV1 144 ** to pV2. 145 ** 146 ** The return is 0 upon complete success. If any input file is binary, 147 ** -1 is returned and pOut is unmodified. If there are merge 148 ** conflicts, the merge proceeds as best as it can and the number 149 ** of conflicts is returns 150 */ 151 static int 152 buf_merge(char *pPivot, char *pV1, char *pV2, xstring *pOut){ 153 int *aC1; /* Changes from pPivot to pV1 */ 154 int *aC2; /* Changes from pPivot to pV2 */ 155 int i1, i2; /* Index into aC1[] and aC2[] */ 156 int nCpy, nDel, nIns; /* Number of lines to copy, delete, or insert */ 157 int limit1, limit2; /* Sizes of aC1[] and aC2[] */ 158 159 xstring_reset(pOut); /* Merge results stored in pOut */ 160 161 /* Compute the edits that occur from pPivot => pV1 (into aC1) 162 ** and pPivot => pV2 (into aC2). Each of the aC1 and aC2 arrays is 163 ** an array of integer triples. Within each triple, the first integer 164 ** is the number of lines of text to copy directly from the pivot, 165 ** the second integer is the number of lines of text to omit from the 166 ** pivot, and the third integer is the number of lines of text that are 167 ** inserted. The edit array ends with a triple of 0,0,0. 168 */ 169 aC1 = text_diff(pPivot, pV1); 170 aC2 = text_diff(pPivot, pV2); 171 if( aC1==0 || aC2==0 ){ 172 free(aC1); 173 free(aC2); 174 return -1; 175 } 176 177 /* Determine the length of the aC1[] and aC2[] change vectors */ 178 for(i1=0; aC1[i1] || aC1[i1+1] || aC1[i1+2]; i1+=3){} 179 limit1 = i1; 180 for(i2=0; aC2[i2] || aC2[i2+1] || aC2[i2+2]; i2+=3){} 181 limit2 = i2; 182 183 /* Loop over the two edit vectors and use them to compute merged text 184 ** which is written into pOut. i1 and i2 are multiples of 3 which are 185 ** indices into aC1[] and aC2[] to the edit triple currently being 186 ** processed 187 */ 188 i1 = i2 = 0; 189 while( i1<limit1 && i2<limit2 ){ 190 191 if( aC1[i1]>0 && aC2[i2]>0 ){ 192 /* Output text that is unchanged in both V1 and V2 */ 193 nCpy = min(aC1[i1], aC2[i2]); 194 pPivot += buf_copy_lines(pOut, pPivot, nCpy); 195 pV1 += buf_copy_lines(NULL, pV1, nCpy); 196 pV2 += buf_copy_lines(NULL, pV2, nCpy); 197 aC1[i1] -= nCpy; 198 aC2[i2] -= nCpy; 199 }else 200 if( aC1[i1] >= aC2[i2+1] && aC1[i1]>0 && aC2[i2+1]+aC2[i2+2]>0 ){ 201 /* Output edits to V2 that occurs within unchanged regions of V1 */ 202 nDel = aC2[i2+1]; 203 nIns = aC2[i2+2]; 204 pPivot += buf_copy_lines(NULL, pPivot, nDel); 205 pV1 += buf_copy_lines(NULL, pV1, nDel); 206 pV2 += buf_copy_lines(pOut, pV2, nIns); 207 aC1[i1] -= nDel; 208 i2 += 3; 209 }else 210 if( aC2[i2] >= aC1[i1+1] && aC2[i2]>0 && aC1[i1+1]+aC1[i1+2]>0 ){ 211 /* Output edits to V1 that occur within unchanged regions of V2 */ 212 nDel = aC1[i1+1]; 213 nIns = aC1[i1+2]; 214 pPivot += buf_copy_lines(NULL, pPivot, nDel); 215 pV2 += buf_copy_lines(NULL, pV2, nDel); 216 pV1 += buf_copy_lines(pOut, pV1, nIns); 217 aC2[i2] -= nDel; 218 i1 += 3; 219 }else 220 if( sameEdit(&aC1[i1], &aC2[i2], pV1, pV2) ){ 221 /* Output edits that are identical in both V1 and V2. */ 222 nDel = aC1[i1+1]; 223 nIns = aC1[i1+2]; 224 pPivot += buf_copy_lines(NULL, pPivot, nDel); 225 pV1 += buf_copy_lines(pOut, pV1, nIns); 226 pV2 += buf_copy_lines(NULL, pV2, nIns); 227 i1 += 3; 228 i2 += 3; 229 }else 230 { 231 return (-1); 232 } 233 234 /* If we are finished with an edit triple, advance to the next 235 ** triple. 236 */ 237 if( i1<limit1 && aC1[i1]==0 && aC1[i1+1]==0 && aC1[i1+2]==0 ) i1+=3; 238 if( i2<limit2 && aC2[i2]==0 && aC2[i2+1]==0 && aC2[i2+2]==0 ) i2+=3; 239 } 240 241 /* When one of the two edit vectors reaches its end, there might still 242 ** be an insert in the other edit vector. Output this remaining 243 ** insert. 244 */ 245 if( i1<limit1 && aC1[i1+2]>0 ){ 246 buf_copy_lines(pOut, pV1, aC1[i1+2]); 247 }else if( i2<limit2 && aC2[i2+2]>0 ){ 248 buf_copy_lines(pOut, pV2, aC2[i2+2]); 249 } 250 251 free(aC1); 252 free(aC2); 253 return 0; 254 } 255 256 /* 257 ** This routine is a wrapper around blob_merge() with the following 258 ** enhancements: 259 ** 260 ** (1) If the merge-command is defined, then use the external merging 261 ** program specified instead of the built-in blob-merge to do the 262 ** merging. Panic if the external merger fails. 263 ** ** Not currently implemented ** 264 ** 265 ** (2) If gmerge-command is defined and there are merge conflicts in 266 ** blob_merge() then invoke the external graphical merger to resolve 267 ** the conflicts. 268 ** 269 ** (3) If a merge conflict occurs and gmerge-command is not defined, 270 ** then write the pivot, original, and merge-in files to the 271 ** filesystem. 272 */ 273 int merge_3way( 274 char *pPivot, /* Common ancestor (older) */ 275 char *pV1, /* Name of file for version merging into (mine) */ 276 char *pV2, /* Version merging from (yours) */ 277 xstring *pOut /* Output written here */ 278 ){ 279 int rc; /* Return code of subroutines and this routine */ 280 281 rc = buf_merge(pPivot, pV1, pV2, pOut); 282 return rc; 283 }