Branch data Line data Source code
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 : 0 : static int sameLines(const char *pV1, const char *pV2, int N){
74 : : int i;
75 : : char c;
76 : :
77 [ # # ]: 0 : if( N==0 ) return 1;
78 [ # # ]: 0 : for(i=0; (c=pV1[i])==pV2[i]; i++){
79 [ # # # # ]: 0 : if( c=='\n' || c==0 ){
80 : 0 : N--;
81 [ # # # # ]: 0 : if( N==0 || c==0 ) return 1;
82 : 0 : }
83 : 0 : }
84 : 0 : return 0;
85 : 0 : }
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 : 0 : 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 [ # # ]: 0 : if( aC1[0]!=aC2[0] ) return 0;
101 [ # # ]: 0 : if( aC1[1]!=aC2[1] ) return 0;
102 [ # # ]: 0 : if( aC1[2]!=aC2[2] ) return 0;
103 [ # # ]: 0 : if( sameLines(pV1, pV2, aC1[2]) ) return 1;
104 : 0 : return 0;
105 : 0 : }
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 : 472 : buf_copy_lines(xstring *to, const char *from, int N)
117 : : {
118 : 472 : int cnt = 0;
119 : : int i;
120 : :
121 [ + + ]: 472 : if (N == 0)
122 : 49 : return (0);
123 : 423 : i = 0;
124 [ + + ]: 2825 : while (from[i] != 0) {
125 [ + + ]: 2721 : if (from[i] == '\n') {
126 : 358 : cnt++;
127 [ + + ]: 358 : if (cnt == N) {
128 : 319 : i++;
129 : 319 : break;
130 : : }
131 : 39 : }
132 : 2402 : i++;
133 : : }
134 [ + + ]: 423 : if (to)
135 : 177 : fwrite(from, i, 1, to->fp);
136 : 423 : return (i);
137 : 472 : }
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 : 64 : 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 : 64 : 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 : 64 : aC1 = text_diff(pPivot, pV1);
170 : 64 : aC2 = text_diff(pPivot, pV2);
171 [ + - - + ]: 64 : if( aC1==0 || aC2==0 ){
172 : 0 : free(aC1);
173 : 0 : free(aC2);
174 : 0 : return -1;
175 : : }
176 : :
177 : : /* Determine the length of the aC1[] and aC2[] change vectors */
178 [ + + + + : 143 : for(i1=0; aC1[i1] || aC1[i1+1] || aC1[i1+2]; i1+=3){}
+ + ]
179 : 64 : limit1 = i1;
180 [ + + + + : 133 : for(i2=0; aC2[i2] || aC2[i2+1] || aC2[i2+2]; i2+=3){}
+ + ]
181 : 64 : 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 : 64 : i1 = i2 = 0;
189 [ + + + + ]: 205 : while( i1<limit1 && i2<limit2 ){
190 : :
191 [ + + + + ]: 141 : if( aC1[i1]>0 && aC2[i2]>0 ){
192 : : /* Output text that is unchanged in both V1 and V2 */
193 [ + + ]: 77 : nCpy = min(aC1[i1], aC2[i2]);
194 : 77 : pPivot += buf_copy_lines(pOut, pPivot, nCpy);
195 : 77 : pV1 += buf_copy_lines(NULL, pV1, nCpy);
196 : 77 : pV2 += buf_copy_lines(NULL, pV2, nCpy);
197 : 77 : aC1[i1] -= nCpy;
198 : 77 : aC2[i2] -= nCpy;
199 : 77 : }else
200 [ + - + + : 64 : 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 : 10 : nDel = aC2[i2+1];
203 : 10 : nIns = aC2[i2+2];
204 : 10 : pPivot += buf_copy_lines(NULL, pPivot, nDel);
205 : 10 : pV1 += buf_copy_lines(NULL, pV1, nDel);
206 : 10 : pV2 += buf_copy_lines(pOut, pV2, nIns);
207 : 10 : aC1[i1] -= nDel;
208 : 10 : i2 += 3;
209 : 10 : }else
210 [ + - + - : 54 : 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 : 54 : nDel = aC1[i1+1];
213 : 54 : nIns = aC1[i1+2];
214 : 54 : pPivot += buf_copy_lines(NULL, pPivot, nDel);
215 : 54 : pV2 += buf_copy_lines(NULL, pV2, nDel);
216 : 54 : pV1 += buf_copy_lines(pOut, pV1, nIns);
217 : 54 : aC2[i2] -= nDel;
218 : 54 : i1 += 3;
219 : 54 : }else
220 [ # # ]: 0 : if( sameEdit(&aC1[i1], &aC2[i2], pV1, pV2) ){
221 : : /* Output edits that are identical in both V1 and V2. */
222 : 0 : nDel = aC1[i1+1];
223 : 0 : nIns = aC1[i1+2];
224 : 0 : pPivot += buf_copy_lines(NULL, pPivot, nDel);
225 : 0 : pV1 += buf_copy_lines(pOut, pV1, nIns);
226 : 0 : pV2 += buf_copy_lines(NULL, pV2, nIns);
227 : 0 : i1 += 3;
228 : 0 : i2 += 3;
229 : 0 : }else
230 : : {
231 : 0 : return (-1);
232 : : }
233 : :
234 : : /* If we are finished with an edit triple, advance to the next
235 : : ** triple.
236 : : */
237 [ + + + + : 141 : if( i1<limit1 && aC1[i1]==0 && aC1[i1+1]==0 && aC1[i1+2]==0 ) i1+=3;
+ + + + ]
238 [ + + + + : 141 : 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 [ + + - + ]: 64 : if( i1<limit1 && aC1[i1+2]>0 ){
246 : 10 : buf_copy_lines(pOut, pV1, aC1[i1+2]);
247 [ + + + - ]: 64 : }else if( i2<limit2 && aC2[i2+2]>0 ){
248 : 39 : buf_copy_lines(pOut, pV2, aC2[i2+2]);
249 : 39 : }
250 : :
251 : 64 : free(aC1);
252 : 64 : free(aC2);
253 : 64 : return 0;
254 : 64 : }
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 : 64 : 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 : 64 : rc = buf_merge(pPivot, pV1, pV2, pOut);
282 : 64 : return rc;
283 : : }
|
