Fossil SCM

Refactor the 3-way-merge logic to make it easier to extend and enhance.

drh 2024-11-28 15:07 trunk
Commit c4df699fd11fc32ed728933407aa1f2393e604076ce6131c4ec35cc791394d3a
Parent 5233364196e06d8…
1 file changed +285 -136
~ src/merge3.c
M src/merge3.c
+285 -136
--- src/merge3.c
+++ src/merge3.c
@@ -98,46 +98,10 @@
9898
 aC += 3;
9999
 }
100100
 return 1;
101101
 }
102102
103
-/*
104
-** pSrc contains an edited file where aC[] describes the edit. Part of
105
-** pSrc has already been output. This routine outputs additional lines
106
-** of pSrc - lines that correspond to the next sz lines of the original
107
-** unedited file.
108
-**
109
-** Note that sz counts the number of lines of text in the original file.
110
-** But text is output from the edited file. So the number of lines transfer
111
-** to pOut might be different from sz. Fewer lines appear in pOut if there
112
-** are deletes. More lines appear if there are inserts.
113
-**
114
-** The aC[] array is updated and the new index into aC[] is returned.
115
-*/
116
-static int output_one_side(
117
- Blob *pOut, /* Write to this blob */
118
- Blob *pSrc, /* The edited file that is to be copied to pOut */
119
- int *aC, /* Array of integer triples describing the edit */
120
- int i, /* Index in aC[] of current location in pSrc */
121
- int sz, /* Number of lines in unedited source to output */
122
- int *pLn /* Line number counter */
123
-){
124
- while( sz>0 ){
125
- if( aC[i]==0 && aC[i+1]==0 && aC[i+2]==0 ) break;
126
- if( aC[i]>=sz ){
127
- blob_copy_lines(pOut, pSrc, sz); *pLn += sz;
128
- aC[i] -= sz;
129
- break;
130
- }
131
- blob_copy_lines(pOut, pSrc, aC[i]); *pLn += aC[i];
132
- blob_copy_lines(pOut, pSrc, aC[i+2]); *pLn += aC[i+2];
133
- sz -= aC[i] + aC[i+1];
134
- i += 3;
135
- }
136
- return i;
137
-}
138
-
139103
 /*
140104
 ** Text of boundary markers for merge conflicts.
141105
 */
142106
 static const char *const mergeMarker[] = {
143107
 /*123456789 123456789 123456789 123456789 123456789 123456789 123456789*/
@@ -186,10 +150,228 @@
186150
 ensure_line_end(pOut, useCrLf);
187151
 blob_append(pOut, mergeMarker[iMark], -1);
188152
 if( ln>0 ) blob_appendf(pOut, " (line %d)", ln);
189153
 ensure_line_end(pOut, useCrLf);
190154
 }
155
+
156
+/*
157
+** This is an abstract class for constructing a merge.
158
+** Subclasses of this object format the merge output in different ways.
159
+**
160
+** To subclass, create an instance of the MergeBuilder object and fill
161
+** in appropriate method implementations.
162
+*/
163
+typedef struct MergeBuilder MergeBuilder;
164
+struct MergeBuilder {
165
+ void (*xStart)(MergeBuilder*);
166
+ void (*xSame)(MergeBuilder*, unsigned int);
167
+ void (*xChngV1)(MergeBuilder*, unsigned int, unsigned int);
168
+ void (*xChngV2)(MergeBuilder*, unsigned int, unsigned int);
169
+ void (*xChngBoth)(MergeBuilder*, unsigned int, unsigned int);
170
+ void (*xConflict)(MergeBuilder*, unsigned int, unsigned int, unsigned int);
171
+ void (*xEnd)(MergeBuilder*);
172
+ void (*xDestroy)(MergeBuilder*);
173
+ const char *zPivot; /* Label or name for the pivot */
174
+ const char *zV1; /* Label or name for the V1 file */
175
+ const char *zV2; /* Label or name for the V2 file */
176
+ const char *zOut; /* Label or name for the output */
177
+ Blob *pPivot; /* The common ancestor */
178
+ Blob *pV1; /* First variant */
179
+ Blob *pV2; /* Second variant */
180
+ Blob *pOut; /* Write merge results here */
181
+ int useCrLf; /* Use CRLF line endings */
182
+ unsigned int lnPivot; /* Lines read from pivot */
183
+ unsigned int lnV1; /* Lines read from v1 */
184
+ unsigned int lnV2; /* Lines read from v2 */
185
+ unsigned int lnOut; /* Lines written to out */
186
+ unsigned int nConflict; /* Number of conflicts seen */
187
+};
188
+
189
+
190
+/************************* Generic MergeBuilder ******************************/
191
+/* These are generic methods for MergeBuilder. They just output debugging
192
+** information. But some of them are useful as base methods for other useful
193
+** implementations of MergeBuilder.
194
+*/
195
+
196
+/* xStart() and xEnd() are called to generate header and fotter information
197
+** in the output. This is a no-op in the generic implementation.
198
+*/
199
+static void dbgStartEnd(MergeBuilder *p){ (void)p; }
200
+
201
+/* The next N lines of PIVOT are unchanged in both V1 and V2
202
+*/
203
+static void dbgSame(MergeBuilder *p, unsigned int N){
204
+ blob_appendf(p->pOut, "COPY %u lines (%u..%u) FROM BASELINE\n",
205
+ N, p->lnPivot, p->lnPivot+N-1);
206
+ p->lnPivot += N;
207
+ p->lnV1 += N;
208
+ p->lnV2 += N;
209
+}
210
+
211
+/* The next nPivot lines of the PIVOT are changed into nV1 lines by V1
212
+*/
213
+static void dbgChngV1(MergeBuilder *p, unsigned int nPivot, unsigned int nV1){
214
+ blob_appendf(p->pOut, "COPY %u lines (%u..%u) FROM V1\n",
215
+ nV1, p->lnV1, p->lnV1+nV1-1);
216
+ p->lnPivot += nPivot;
217
+ p->lnV2 += nPivot;
218
+ p->lnV1 += nV1;
219
+}
220
+
221
+/* The next nPivot lines of the PIVOT are changed into nV2 lines by V2
222
+*/
223
+static void dbgChngV2(MergeBuilder *p, unsigned int nPivot, unsigned int nV2){
224
+ blob_appendf(p->pOut, "COPY %u lines (%u..%u) FROM V2\n",
225
+ nV2, p->lnV2, p->lnV2+nV2-1);
226
+ p->lnPivot += nPivot;
227
+ p->lnV1 += nPivot;
228
+ p->lnV2 += nV2;
229
+}
230
+
231
+/* The next nPivot lines of the PIVOT are changed into nV lines from V1 and
232
+** V2, which should be the same. In other words, the same change is found
233
+** in both V1 and V2.
234
+*/
235
+static void dbgChngBoth(MergeBuilder *p, unsigned int nPivot, unsigned int nV){
236
+ blob_appendf(p->pOut, "COPY %u lines (%u..%u) FROM V1\n",
237
+ nV, p->lnV1, p->lnV1+nV-1);
238
+ p->lnPivot += nPivot;
239
+ p->lnV1 += nV;
240
+ p->lnV2 += nV;
241
+}
242
+
243
+/* V1 and V2 have different and overlapping changes. The next nPivot lines
244
+** of the PIVOT are converted into nV1 lines of V1 and nV2 lines of V2.
245
+*/
246
+static void dbgConflict(
247
+ MergeBuilder *p,
248
+ unsigned int nPivot,
249
+ unsigned int nV1,
250
+ unsigned int nV2
251
+){
252
+ blob_appendf(p->pOut,
253
+ "CONFLICT BASELINE(%u..%u) versus V1(%u..%u) versus V2(%u..%u)\n",
254
+ p->lnPivot, p->lnPivot+nPivot-1,
255
+ p->lnV1, p->lnPivot+nV1-1,
256
+ p->lnV2, p->lnPivot+nV2-1);
257
+ p->lnV1 += nV1;
258
+ p->lnPivot += nPivot;
259
+ p->lnV2 += nV2;
260
+}
261
+
262
+/* Generic destructor for the MergeBuilder object
263
+*/
264
+static void dbgDestroy(MergeBuilder *p){
265
+ memset(p, 0, sizeof(*p));
266
+}
267
+
268
+/* Generic initializer for a MergeBuilder object
269
+*/
270
+static void mergebuilder_init(MergeBuilder *p){
271
+ memset(p, 0, sizeof(*p));
272
+ p->xStart = dbgStartEnd;
273
+ p->xSame = dbgSame;
274
+ p->xChngV1 = dbgChngV1;
275
+ p->xChngV2 = dbgChngV2;
276
+ p->xChngBoth = dbgChngBoth;
277
+ p->xConflict = dbgConflict;
278
+ p->xEnd = dbgStartEnd;
279
+ p->xDestroy = dbgDestroy;
280
+}
281
+
282
+
283
+/************************* MergeBuilderText **********************************/
284
+/* This version of MergeBuilder actually performs a merge on file and puts
285
+** the result in pOut
286
+*/
287
+static void txtStart(MergeBuilder *p){
288
+ /* If both pV1 and pV2 start with a UTF-8 byte-order-mark (BOM),
289
+ ** keep it in the output. This should be secure enough not to cause
290
+ ** unintended changes to the merged file and consistent with what
291
+ ** users are using in their source files.
292
+ */
293
+ if( starts_with_utf8_bom(p->pV1, 0) && starts_with_utf8_bom(p->pV2, 0) ){
294
+ blob_append(p->pOut, (char*)get_utf8_bom(0), -1);
295
+ }
296
+ if( contains_crlf(p->pV1) && contains_crlf(p->pV2) ){
297
+ p->useCrLf = 1;
298
+ }
299
+}
300
+static void txtSame(MergeBuilder *p, unsigned int N){
301
+ blob_copy_lines(p->pOut, p->pPivot, N); p->lnPivot += N;
302
+ blob_copy_lines(0, p->pV1, N); p->lnV1 += N;
303
+ blob_copy_lines(0, p->pV2, N); p->lnV2 += N;
304
+}
305
+static void txtChngV1(MergeBuilder *p, unsigned int nPivot, unsigned int nV1){
306
+ blob_copy_lines(0, p->pPivot, nPivot); p->lnPivot += nPivot;
307
+ blob_copy_lines(0, p->pV2, nPivot); p->lnV2 += nPivot;
308
+ blob_copy_lines(p->pOut, p->pV1, nV1); p->lnV1 += nV1;
309
+}
310
+static void txtChngV2(MergeBuilder *p, unsigned int nPivot, unsigned int nV2){
311
+ blob_copy_lines(0, p->pPivot, nPivot); p->lnPivot += nPivot;
312
+ blob_copy_lines(0, p->pV1, nPivot); p->lnV1 += nPivot;
313
+ blob_copy_lines(p->pOut, p->pV2, nV2); p->lnV2 += nV2;
314
+}
315
+static void txtChngBoth(MergeBuilder *p, unsigned int nPivot, unsigned int nV){
316
+ blob_copy_lines(0, p->pPivot, nPivot); p->lnPivot += nPivot;
317
+ blob_copy_lines(0, p->pV1, nPivot); p->lnV1 += nV;
318
+ blob_copy_lines(p->pOut, p->pV2, nV); p->lnV2 += nV;
319
+}
320
+static void txtConflict(
321
+ MergeBuilder *p,
322
+ unsigned int nPivot,
323
+ unsigned int nV1,
324
+ unsigned int nV2
325
+){
326
+ append_merge_mark(p->pOut, 0, p->lnV1, p->useCrLf);
327
+ blob_copy_lines(p->pOut, p->pV1, nV1); p->lnV1 += nV1;
328
+
329
+ append_merge_mark(p->pOut, 1, p->lnPivot, p->useCrLf);
330
+ blob_copy_lines(p->pOut, p->pPivot, nPivot); p->lnPivot += nPivot;
331
+
332
+ append_merge_mark(p->pOut, 2, p->lnV2, p->useCrLf);
333
+ blob_copy_lines(p->pOut, p->pV2, nV2); p->lnV2 += nV2;
334
+
335
+ append_merge_mark(p->pOut, 3, -1, p->useCrLf);
336
+}
337
+static void mergebuilder_init_text(MergeBuilder *p){
338
+ mergebuilder_init(p);
339
+ p->xStart = txtStart;
340
+ p->xSame = txtSame;
341
+ p->xChngV1 = txtChngV1;
342
+ p->xChngV2 = txtChngV2;
343
+ p->xChngBoth = txtChngBoth;
344
+ p->xConflict = txtConflict;
345
+}
346
+/*****************************************************************************/
347
+
348
+/*
349
+** aC[] is an "edit triple" for changes from A to B. Advance through
350
+** this triple to determine the number of lines to bypass on B in order
351
+** to match an advance of sz lines on A.
352
+*/
353
+static int skip_conflict(
354
+ int *aC, /* Array of integer triples describing the edit */
355
+ int i, /* Index in aC[] of current location */
356
+ int sz, /* Lines of A that have been skipped */
357
+ unsigned int *pLn /* OUT: Lines of B to skip to keep aligment with A */
358
+){
359
+ *pLn = 0;
360
+ while( sz>0 ){
361
+ if( aC[i]==0 && aC[i+1]==0 && aC[i+2]==0 ) break;
362
+ if( aC[i]>=sz ){
363
+ aC[i] -= sz;
364
+ break;
365
+ }
366
+ *pLn += aC[i];
367
+ *pLn += aC[i+2];
368
+ sz -= aC[i] + aC[i+1];
369
+ i += 3;
370
+ }
371
+ return i;
372
+}
191373
192374
 /*
193375
 ** Do a three-way merge. Initialize pOut to contain the result.
194376
 **
195377
 ** The merge is an edit against pV2. Both pV1 and pV2 have a
@@ -199,156 +381,104 @@
199381
 ** The return is 0 upon complete success. If any input file is binary,
200382
 ** -1 is returned and pOut is unmodified. If there are merge
201383
 ** conflicts, the merge proceeds as best as it can and the number
202384
 ** of conflicts is returns
203385
 */
204
-static int blob_merge(Blob *pPivot, Blob *pV1, Blob *pV2, Blob *pOut){
386
+static int blob_merge(MergeBuilder *p){
205387
 int *aC1; /* Changes from pPivot to pV1 */
206388
 int *aC2; /* Changes from pPivot to pV2 */
207389
 int i1, i2; /* Index into aC1[] and aC2[] */
208390
 int nCpy, nDel, nIns; /* Number of lines to copy, delete, or insert */
209391
 int limit1, limit2; /* Sizes of aC1[] and aC2[] */
210392
 int nConflict = 0; /* Number of merge conflicts seen so far */
211
- int useCrLf = 0;
212
- int ln1, ln2, lnPivot; /* Line numbers for all files */
213393
 DiffConfig DCfg;
214394
215
- blob_zero(pOut); /* Merge results stored in pOut */
216
-
217
- /* If both pV1 and pV2 start with a UTF-8 byte-order-mark (BOM),
218
- ** keep it in the output. This should be secure enough not to cause
219
- ** unintended changes to the merged file and consistent with what
220
- ** users are using in their source files.
221
- */
222
- if( starts_with_utf8_bom(pV1, 0) && starts_with_utf8_bom(pV2, 0) ){
223
- blob_append(pOut, (char*)get_utf8_bom(0), -1);
224
- }
225
-
226
- /* Check once to see if both pV1 and pV2 contains CR/LF endings.
227
- ** If true, CR/LF pair will be used later to append the
228
- ** boundary markers for merge conflicts.
229
- */
230
- if( contains_crlf(pV1) && contains_crlf(pV2) ){
231
- useCrLf = 1;
232
- }
233
-
234395
 /* Compute the edits that occur from pPivot => pV1 (into aC1)
235396
 ** and pPivot => pV2 (into aC2). Each of the aC1 and aC2 arrays is
236397
 ** an array of integer triples. Within each triple, the first integer
237398
 ** is the number of lines of text to copy directly from the pivot,
238399
 ** the second integer is the number of lines of text to omit from the
239400
 ** pivot, and the third integer is the number of lines of text that are
240401
 ** inserted. The edit array ends with a triple of 0,0,0.
241402
 */
242403
 diff_config_init(&DCfg, 0);
243
- aC1 = text_diff(pPivot, pV1, 0, &DCfg);
244
- aC2 = text_diff(pPivot, pV2, 0, &DCfg);
404
+ aC1 = text_diff(p->pPivot, p->pV1, 0, &DCfg);
405
+ aC2 = text_diff(p->pPivot, p->pV2, 0, &DCfg);
245406
 if( aC1==0 || aC2==0 ){
246407
 free(aC1);
247408
 free(aC2);
248409
 return -1;
249410
 }
250411
251
- blob_rewind(pV1); /* Rewind inputs: Needed to reconstruct output */
252
- blob_rewind(pV2);
253
- blob_rewind(pPivot);
412
+ blob_rewind(p->pV1); /* Rewind inputs: Needed to reconstruct output */
413
+ blob_rewind(p->pV2);
414
+ blob_rewind(p->pPivot);
254415
255416
 /* Determine the length of the aC1[] and aC2[] change vectors */
256417
 for(i1=0; aC1[i1] || aC1[i1+1] || aC1[i1+2]; i1+=3){}
257418
 limit1 = i1;
258419
 for(i2=0; aC2[i2] || aC2[i2+1] || aC2[i2+2]; i2+=3){}
259420
 limit2 = i2;
260421
261
- DEBUG(
262
- for(i1=0; i1<limit1; i1+=3){
263
- printf("c1: %4d %4d %4d\n", aC1[i1], aC1[i1+1], aC1[i1+2]);
264
- }
265
- for(i2=0; i2<limit2; i2+=3){
266
- printf("c2: %4d %4d %4d\n", aC2[i2], aC2[i2+1], aC2[i2+2]);
267
- }
268
- )
422
+ /* Output header text and do any other required initialization */
423
+ p->xStart(p);
269424
270425
 /* Loop over the two edit vectors and use them to compute merged text
271426
 ** which is written into pOut. i1 and i2 are multiples of 3 which are
272427
 ** indices into aC1[] and aC2[] to the edit triple currently being
273428
 ** processed
274429
 */
275430
 i1 = i2 = 0;
276
- ln1 = ln2 = lnPivot = 1;
277431
 while( i1<limit1 && i2<limit2 ){
278
- DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
279
- i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
280
- i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
281
-
282432
 if( aC1[i1]>0 && aC2[i2]>0 ){
283433
 /* Output text that is unchanged in both V1 and V2 */
284434
 nCpy = min(aC1[i1], aC2[i2]);
285
- DEBUG( printf("COPY %d\n", nCpy); )
286
- blob_copy_lines(pOut, pPivot, nCpy); lnPivot += nCpy;
287
- blob_copy_lines(0, pV1, nCpy); ln1 += nCpy;
288
- blob_copy_lines(0, pV2, nCpy); ln2 += nCpy;
435
+ p->xSame(p, nCpy);
289436
 aC1[i1] -= nCpy;
290437
 aC2[i2] -= nCpy;
291438
 }else
292439
 if( aC1[i1] >= aC2[i2+1] && aC1[i1]>0 && aC2[i2+1]+aC2[i2+2]>0 ){
293440
 /* Output edits to V2 that occurs within unchanged regions of V1 */
294441
 nDel = aC2[i2+1];
295442
 nIns = aC2[i2+2];
296
- DEBUG( printf("EDIT -%d+%d left\n", nDel, nIns); )
297
- blob_copy_lines(0, pPivot, nDel); lnPivot += nDel;
298
- blob_copy_lines(0, pV1, nDel); ln1 += nDel;
299
- blob_copy_lines(pOut, pV2, nIns); ln2 += nIns;
443
+ p->xChngV2(p, nDel, nIns);
300444
 aC1[i1] -= nDel;
301445
 i2 += 3;
302446
 }else
303447
 if( aC2[i2] >= aC1[i1+1] && aC2[i2]>0 && aC1[i1+1]+aC1[i1+2]>0 ){
304448
 /* Output edits to V1 that occur within unchanged regions of V2 */
305449
 nDel = aC1[i1+1];
306450
 nIns = aC1[i1+2];
307
- DEBUG( printf("EDIT -%d+%d right\n", nDel, nIns); )
308
- blob_copy_lines(0, pPivot, nDel); lnPivot += nDel;
309
- blob_copy_lines(0, pV2, nDel); ln2 += nDel;
310
- blob_copy_lines(pOut, pV1, nIns); ln1 += nIns;
451
+ p->xChngV2(p, nDel, nIns);
311452
 aC2[i2] -= nDel;
312453
 i1 += 3;
313454
 }else
314
- if( sameEdit(&aC1[i1], &aC2[i2], pV1, pV2) ){
455
+ if( sameEdit(&aC1[i1], &aC2[i2], p->pV1, p->pV2) ){
315456
 /* Output edits that are identical in both V1 and V2. */
316457
 assert( aC1[i1]==0 );
317458
 nDel = aC1[i1+1];
318459
 nIns = aC1[i1+2];
319
- DEBUG( printf("EDIT -%d+%d both\n", nDel, nIns); )
320
- blob_copy_lines(0, pPivot, nDel); lnPivot += nDel;
321
- blob_copy_lines(pOut, pV1, nIns); ln1 += nIns;
322
- blob_copy_lines(0, pV2, nIns); ln2 += nIns;
460
+ p->xChngBoth(p, nDel, nIns);
323461
 i1 += 3;
324462
 i2 += 3;
325463
 }else
326464
 {
327465
 /* We have found a region where different edits to V1 and V2 overlap.
328466
 ** This is a merge conflict. Find the size of the conflict, then
329467
 ** output both possible edits separated by distinctive marks.
330468
 */
331
- int sz = 1; /* Size of the conflict in lines */
469
+ unsigned int sz = 1; /* Size of the conflict in lines */
470
+ unsigned int nV1, nV2;
332471
 nConflict++;
333472
 while( !ends_at_CPY(&aC1[i1], sz) || !ends_at_CPY(&aC2[i2], sz) ){
334473
 sz++;
335474
 }
336
- DEBUG( printf("CONFLICT %d\n", sz); )
337
-
338
- append_merge_mark(pOut, 0, ln1, useCrLf);
339
- i1 = output_one_side(pOut, pV1, aC1, i1, sz, &ln1);
340
-
341
- append_merge_mark(pOut, 1, lnPivot, useCrLf);
342
- blob_copy_lines(pOut, pPivot, sz); lnPivot += sz;
343
-
344
- append_merge_mark(pOut, 2, ln2, useCrLf);
345
- i2 = output_one_side(pOut, pV2, aC2, i2, sz, &ln2);
346
-
347
- append_merge_mark(pOut, 3, -1, useCrLf);
348
- }
349
-
475
+ i1 = skip_conflict(aC1, i1, sz, &nV1);
476
+ i2 = skip_conflict(aC2, i2, sz, &nV2);
477
+ p->xConflict(p, sz, nV1, nV2);
478
+ }
479
+
350480
 /* If we are finished with an edit triple, advance to the next
351481
 ** triple.
352482
 */
353483
 if( i1<limit1 && aC1[i1]==0 && aC1[i1+1]==0 && aC1[i1+2]==0 ) i1+=3;
354484
 if( i2<limit2 && aC2[i2]==0 && aC2[i2+1]==0 && aC2[i2+2]==0 ) i2+=3;
@@ -356,20 +486,18 @@
356486
357487
 /* When one of the two edit vectors reaches its end, there might still
358488
 ** be an insert in the other edit vector. Output this remaining
359489
 ** insert.
360490
 */
361
- DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
362
- i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
363
- i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
364491
 if( i1<limit1 && aC1[i1+2]>0 ){
365
- DEBUG( printf("INSERT +%d left\n", aC1[i1+2]); )
366
- blob_copy_lines(pOut, pV1, aC1[i1+2]);
492
+ p->xChngV1(p, 0, aC1[i1+2]);
367493
 }else if( i2<limit2 && aC2[i2+2]>0 ){
368
- DEBUG( printf("INSERT +%d right\n", aC2[i2+2]); )
369
- blob_copy_lines(pOut, pV2, aC2[i2+2]);
494
+ p->xChngV1(p, 0, aC2[i2+2]);
370495
 }
496
+
497
+ /* Output footer text */
498
+ p->xEnd(p);
371499
372500
 free(aC1);
373501
 free(aC2);
374502
 return nConflict;
375503
 }
@@ -412,14 +540,15 @@
412540
 }
413541
414542
 /*
415543
 ** COMMAND: 3-way-merge*
416544
 **
417
-** Usage: %fossil 3-way-merge BASELINE V1 V2 MERGED
545
+** Usage: %fossil 3-way-merge BASELINE V1 V2 [MERGED]
418546
 **
419547
 ** Inputs are files BASELINE, V1, and V2. The file MERGED is generated
420
-** as output.
548
+** as output. If no MERGED file is specified, output is sent to
549
+** stdout.
421550
 **
422551
 ** BASELINE is a common ancestor of two files V1 and V2 that have diverging
423552
 ** edits. The generated output file MERGED is the combination of all
424553
 ** changes in both V1 and V2.
425554
 **
@@ -436,37 +565,50 @@
436565
 ** cp Xup.c Xbase.c
437566
 ** # Verify that everything still works
438567
 ** fossil commit
439568
 **
440569
 */
441
-void delta_3waymerge_cmd(void){
442
- Blob pivot, v1, v2, merged;
570
+void merge_3way_cmd(void){
571
+ MergeBuilder s;
443572
 int nConflict;
573
+ Blob pivot, v1, v2, out;
574
+
575
+ mergebuilder_init_text(&s);
576
+ if( find_option("debug", 0, 0) ){
577
+ mergebuilder_init(&s);
578
+ }
579
+ blob_zero(&pivot); s.pPivot = &pivot;
580
+ blob_zero(&v1); s.pV1 = &v1;
581
+ blob_zero(&v2); s.pV2 = &v2;
582
+ blob_zero(&out); s.pOut = &out;
444583
445584
 /* We should be done with options.. */
446585
 verify_all_options();
447586
448
- if( g.argc!=6 ){
449
- usage("PIVOT V1 V2 MERGED");
587
+ if( g.argc!=6 && g.argc!=5 ){
588
+ usage("[OPTIONS] PIVOT V1 V2 [MERGED]");
450589
 }
451
- if( blob_read_from_file(&pivot, g.argv[2], ExtFILE)<0 ){
590
+ if( blob_read_from_file(s.pPivot, g.argv[2], ExtFILE)<0 ){
452591
 fossil_fatal("cannot read %s", g.argv[2]);
453592
 }
454
- if( blob_read_from_file(&v1, g.argv[3], ExtFILE)<0 ){
593
+ if( blob_read_from_file(s.pV1, g.argv[3], ExtFILE)<0 ){
455594
 fossil_fatal("cannot read %s", g.argv[3]);
456595
 }
457
- if( blob_read_from_file(&v2, g.argv[4], ExtFILE)<0 ){
596
+ if( blob_read_from_file(s.pV2, g.argv[4], ExtFILE)<0 ){
458597
 fossil_fatal("cannot read %s", g.argv[4]);
459598
 }
460
- nConflict = blob_merge(&pivot, &v1, &v2, &merged);
461
- if( blob_write_to_file(&merged, g.argv[5])<(int)blob_size(&merged) ){
462
- fossil_fatal("cannot write %s", g.argv[4]);
599
+ nConflict = blob_merge(&s);
600
+ if( g.argc==6 ){
601
+ blob_write_to_file(s.pOut, g.argv[5]);
602
+ }else{
603
+ blob_write_to_file(s.pOut, "-");
463604
 }
605
+ s.xDestroy(&s);
464606
 blob_reset(&pivot);
465607
 blob_reset(&v1);
466608
 blob_reset(&v2);
467
- blob_reset(&merged);
609
+ blob_reset(&out);
468610
 if( nConflict>0 ) fossil_warning("WARNING: %d merge conflicts", nConflict);
469611
 }
470612
471613
 /*
472614
 ** aSubst is an array of string pairs. The first element of each pair is
@@ -539,30 +681,37 @@
539681
 const char *zV1, /* Name of file for version merging into (mine) */
540682
 Blob *pV2, /* Version merging from (yours) */
541683
 Blob *pOut, /* Output written here */
542684
 unsigned mergeFlags /* Flags that control operation */
543685
 ){
544
- Blob v1; /* Content of zV1 */
545
- int rc; /* Return code of subroutines and this routine */
686
+ Blob v1; /* Content of zV1 */
687
+ int rc; /* Return code of subroutines and this routine */
546688
 const char *zGMerge; /* Name of the gmerge command */
689
+ MergeBuilder s; /* The merge state */
547690
548
- blob_read_from_file(&v1, zV1, ExtFILE);
549
- rc = blob_merge(pPivot, &v1, pV2, pOut);
691
+ mergebuilder_init_text(&s);
692
+ s.pPivot = pPivot;
693
+ s.pV1 = &v1;
694
+ s.pV2 = pV2;
695
+ blob_zero(pOut);
696
+ s.pOut = pOut;
697
+ blob_read_from_file(s.pV1, zV1, ExtFILE);
698
+ rc = blob_merge(&s);
550699
 zGMerge = rc<=0 ? 0 : db_get("gmerge-command", 0);
551700
 if( (mergeFlags & MERGE_DRYRUN)==0
552701
 && ((zGMerge!=0 && zGMerge[0]!=0)
553702
 || (rc!=0 && (mergeFlags & MERGE_KEEP_FILES)!=0)) ){
554703
 char *zPivot; /* Name of the pivot file */
555704
 char *zOrig; /* Name of the original content file */
556705
 char *zOther; /* Name of the merge file */
557706
558707
 zPivot = file_newname(zV1, "baseline", 1);
559
- blob_write_to_file(pPivot, zPivot);
708
+ blob_write_to_file(s.pPivot, zPivot);
560709
 zOrig = file_newname(zV1, "original", 1);
561
- blob_write_to_file(&v1, zOrig);
710
+ blob_write_to_file(s.pV1, zOrig);
562711
 zOther = file_newname(zV1, "merge", 1);
563
- blob_write_to_file(pV2, zOther);
712
+ blob_write_to_file(s.pV2, zOther);
564713
 if( rc>0 ){
565714
 if( zGMerge && zGMerge[0] ){
566715
 char *zOut; /* Temporary output file */
567716
 char *zCmd; /* Command to invoke */
568717
 const char *azSubst[8]; /* Strings to be substituted */
@@ -589,8 +738,8 @@
589738
 }
590739
 fossil_free(zPivot);
591740
 fossil_free(zOrig);
592741
 fossil_free(zOther);
593742
 }
594
- blob_reset(&v1);
743
+ s.xDestroy(&s);
595744
 return rc;
596745
 }
597746
--- src/merge3.c
+++ src/merge3.c
@@ -98,46 +98,10 @@
98 aC += 3;
99 }
100 return 1;
101 }
102
103 /*
104 ** pSrc contains an edited file where aC[] describes the edit. Part of
105 ** pSrc has already been output. This routine outputs additional lines
106 ** of pSrc - lines that correspond to the next sz lines of the original
107 ** unedited file.
108 **
109 ** Note that sz counts the number of lines of text in the original file.
110 ** But text is output from the edited file. So the number of lines transfer
111 ** to pOut might be different from sz. Fewer lines appear in pOut if there
112 ** are deletes. More lines appear if there are inserts.
113 **
114 ** The aC[] array is updated and the new index into aC[] is returned.
115 */
116 static int output_one_side(
117 Blob *pOut, /* Write to this blob */
118 Blob *pSrc, /* The edited file that is to be copied to pOut */
119 int *aC, /* Array of integer triples describing the edit */
120 int i, /* Index in aC[] of current location in pSrc */
121 int sz, /* Number of lines in unedited source to output */
122 int *pLn /* Line number counter */
123 ){
124 while( sz>0 ){
125 if( aC[i]==0 && aC[i+1]==0 && aC[i+2]==0 ) break;
126 if( aC[i]>=sz ){
127 blob_copy_lines(pOut, pSrc, sz); *pLn += sz;
128 aC[i] -= sz;
129 break;
130 }
131 blob_copy_lines(pOut, pSrc, aC[i]); *pLn += aC[i];
132 blob_copy_lines(pOut, pSrc, aC[i+2]); *pLn += aC[i+2];
133 sz -= aC[i] + aC[i+1];
134 i += 3;
135 }
136 return i;
137 }
138
139 /*
140 ** Text of boundary markers for merge conflicts.
141 */
142 static const char *const mergeMarker[] = {
143 /*123456789 123456789 123456789 123456789 123456789 123456789 123456789*/
@@ -186,10 +150,228 @@
186 ensure_line_end(pOut, useCrLf);
187 blob_append(pOut, mergeMarker[iMark], -1);
188 if( ln>0 ) blob_appendf(pOut, " (line %d)", ln);
189 ensure_line_end(pOut, useCrLf);
190 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
191
192 /*
193 ** Do a three-way merge. Initialize pOut to contain the result.
194 **
195 ** The merge is an edit against pV2. Both pV1 and pV2 have a
@@ -199,156 +381,104 @@
199 ** The return is 0 upon complete success. If any input file is binary,
200 ** -1 is returned and pOut is unmodified. If there are merge
201 ** conflicts, the merge proceeds as best as it can and the number
202 ** of conflicts is returns
203 */
204 static int blob_merge(Blob *pPivot, Blob *pV1, Blob *pV2, Blob *pOut){
205 int *aC1; /* Changes from pPivot to pV1 */
206 int *aC2; /* Changes from pPivot to pV2 */
207 int i1, i2; /* Index into aC1[] and aC2[] */
208 int nCpy, nDel, nIns; /* Number of lines to copy, delete, or insert */
209 int limit1, limit2; /* Sizes of aC1[] and aC2[] */
210 int nConflict = 0; /* Number of merge conflicts seen so far */
211 int useCrLf = 0;
212 int ln1, ln2, lnPivot; /* Line numbers for all files */
213 DiffConfig DCfg;
214
215 blob_zero(pOut); /* Merge results stored in pOut */
216
217 /* If both pV1 and pV2 start with a UTF-8 byte-order-mark (BOM),
218 ** keep it in the output. This should be secure enough not to cause
219 ** unintended changes to the merged file and consistent with what
220 ** users are using in their source files.
221 */
222 if( starts_with_utf8_bom(pV1, 0) && starts_with_utf8_bom(pV2, 0) ){
223 blob_append(pOut, (char*)get_utf8_bom(0), -1);
224 }
225
226 /* Check once to see if both pV1 and pV2 contains CR/LF endings.
227 ** If true, CR/LF pair will be used later to append the
228 ** boundary markers for merge conflicts.
229 */
230 if( contains_crlf(pV1) && contains_crlf(pV2) ){
231 useCrLf = 1;
232 }
233
234 /* Compute the edits that occur from pPivot => pV1 (into aC1)
235 ** and pPivot => pV2 (into aC2). Each of the aC1 and aC2 arrays is
236 ** an array of integer triples. Within each triple, the first integer
237 ** is the number of lines of text to copy directly from the pivot,
238 ** the second integer is the number of lines of text to omit from the
239 ** pivot, and the third integer is the number of lines of text that are
240 ** inserted. The edit array ends with a triple of 0,0,0.
241 */
242 diff_config_init(&DCfg, 0);
243 aC1 = text_diff(pPivot, pV1, 0, &DCfg);
244 aC2 = text_diff(pPivot, pV2, 0, &DCfg);
245 if( aC1==0 || aC2==0 ){
246 free(aC1);
247 free(aC2);
248 return -1;
249 }
250
251 blob_rewind(pV1); /* Rewind inputs: Needed to reconstruct output */
252 blob_rewind(pV2);
253 blob_rewind(pPivot);
254
255 /* Determine the length of the aC1[] and aC2[] change vectors */
256 for(i1=0; aC1[i1] || aC1[i1+1] || aC1[i1+2]; i1+=3){}
257 limit1 = i1;
258 for(i2=0; aC2[i2] || aC2[i2+1] || aC2[i2+2]; i2+=3){}
259 limit2 = i2;
260
261 DEBUG(
262 for(i1=0; i1<limit1; i1+=3){
263 printf("c1: %4d %4d %4d\n", aC1[i1], aC1[i1+1], aC1[i1+2]);
264 }
265 for(i2=0; i2<limit2; i2+=3){
266 printf("c2: %4d %4d %4d\n", aC2[i2], aC2[i2+1], aC2[i2+2]);
267 }
268 )
269
270 /* Loop over the two edit vectors and use them to compute merged text
271 ** which is written into pOut. i1 and i2 are multiples of 3 which are
272 ** indices into aC1[] and aC2[] to the edit triple currently being
273 ** processed
274 */
275 i1 = i2 = 0;
276 ln1 = ln2 = lnPivot = 1;
277 while( i1<limit1 && i2<limit2 ){
278 DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
279 i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
280 i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
281
282 if( aC1[i1]>0 && aC2[i2]>0 ){
283 /* Output text that is unchanged in both V1 and V2 */
284 nCpy = min(aC1[i1], aC2[i2]);
285 DEBUG( printf("COPY %d\n", nCpy); )
286 blob_copy_lines(pOut, pPivot, nCpy); lnPivot += nCpy;
287 blob_copy_lines(0, pV1, nCpy); ln1 += nCpy;
288 blob_copy_lines(0, pV2, nCpy); ln2 += nCpy;
289 aC1[i1] -= nCpy;
290 aC2[i2] -= nCpy;
291 }else
292 if( aC1[i1] >= aC2[i2+1] && aC1[i1]>0 && aC2[i2+1]+aC2[i2+2]>0 ){
293 /* Output edits to V2 that occurs within unchanged regions of V1 */
294 nDel = aC2[i2+1];
295 nIns = aC2[i2+2];
296 DEBUG( printf("EDIT -%d+%d left\n", nDel, nIns); )
297 blob_copy_lines(0, pPivot, nDel); lnPivot += nDel;
298 blob_copy_lines(0, pV1, nDel); ln1 += nDel;
299 blob_copy_lines(pOut, pV2, nIns); ln2 += nIns;
300 aC1[i1] -= nDel;
301 i2 += 3;
302 }else
303 if( aC2[i2] >= aC1[i1+1] && aC2[i2]>0 && aC1[i1+1]+aC1[i1+2]>0 ){
304 /* Output edits to V1 that occur within unchanged regions of V2 */
305 nDel = aC1[i1+1];
306 nIns = aC1[i1+2];
307 DEBUG( printf("EDIT -%d+%d right\n", nDel, nIns); )
308 blob_copy_lines(0, pPivot, nDel); lnPivot += nDel;
309 blob_copy_lines(0, pV2, nDel); ln2 += nDel;
310 blob_copy_lines(pOut, pV1, nIns); ln1 += nIns;
311 aC2[i2] -= nDel;
312 i1 += 3;
313 }else
314 if( sameEdit(&aC1[i1], &aC2[i2], pV1, pV2) ){
315 /* Output edits that are identical in both V1 and V2. */
316 assert( aC1[i1]==0 );
317 nDel = aC1[i1+1];
318 nIns = aC1[i1+2];
319 DEBUG( printf("EDIT -%d+%d both\n", nDel, nIns); )
320 blob_copy_lines(0, pPivot, nDel); lnPivot += nDel;
321 blob_copy_lines(pOut, pV1, nIns); ln1 += nIns;
322 blob_copy_lines(0, pV2, nIns); ln2 += nIns;
323 i1 += 3;
324 i2 += 3;
325 }else
326 {
327 /* We have found a region where different edits to V1 and V2 overlap.
328 ** This is a merge conflict. Find the size of the conflict, then
329 ** output both possible edits separated by distinctive marks.
330 */
331 int sz = 1; /* Size of the conflict in lines */
 
332 nConflict++;
333 while( !ends_at_CPY(&aC1[i1], sz) || !ends_at_CPY(&aC2[i2], sz) ){
334 sz++;
335 }
336 DEBUG( printf("CONFLICT %d\n", sz); )
337
338 append_merge_mark(pOut, 0, ln1, useCrLf);
339 i1 = output_one_side(pOut, pV1, aC1, i1, sz, &ln1);
340
341 append_merge_mark(pOut, 1, lnPivot, useCrLf);
342 blob_copy_lines(pOut, pPivot, sz); lnPivot += sz;
343
344 append_merge_mark(pOut, 2, ln2, useCrLf);
345 i2 = output_one_side(pOut, pV2, aC2, i2, sz, &ln2);
346
347 append_merge_mark(pOut, 3, -1, useCrLf);
348 }
349
350 /* If we are finished with an edit triple, advance to the next
351 ** triple.
352 */
353 if( i1<limit1 && aC1[i1]==0 && aC1[i1+1]==0 && aC1[i1+2]==0 ) i1+=3;
354 if( i2<limit2 && aC2[i2]==0 && aC2[i2+1]==0 && aC2[i2+2]==0 ) i2+=3;
@@ -356,20 +486,18 @@
356
357 /* When one of the two edit vectors reaches its end, there might still
358 ** be an insert in the other edit vector. Output this remaining
359 ** insert.
360 */
361 DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
362 i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
363 i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
364 if( i1<limit1 && aC1[i1+2]>0 ){
365 DEBUG( printf("INSERT +%d left\n", aC1[i1+2]); )
366 blob_copy_lines(pOut, pV1, aC1[i1+2]);
367 }else if( i2<limit2 && aC2[i2+2]>0 ){
368 DEBUG( printf("INSERT +%d right\n", aC2[i2+2]); )
369 blob_copy_lines(pOut, pV2, aC2[i2+2]);
370 }
 
 
 
371
372 free(aC1);
373 free(aC2);
374 return nConflict;
375 }
@@ -412,14 +540,15 @@
412 }
413
414 /*
415 ** COMMAND: 3-way-merge*
416 **
417 ** Usage: %fossil 3-way-merge BASELINE V1 V2 MERGED
418 **
419 ** Inputs are files BASELINE, V1, and V2. The file MERGED is generated
420 ** as output.
 
421 **
422 ** BASELINE is a common ancestor of two files V1 and V2 that have diverging
423 ** edits. The generated output file MERGED is the combination of all
424 ** changes in both V1 and V2.
425 **
@@ -436,37 +565,50 @@
436 ** cp Xup.c Xbase.c
437 ** # Verify that everything still works
438 ** fossil commit
439 **
440 */
441 void delta_3waymerge_cmd(void){
442 Blob pivot, v1, v2, merged;
443 int nConflict;
 
 
 
 
 
 
 
 
 
 
444
445 /* We should be done with options.. */
446 verify_all_options();
447
448 if( g.argc!=6 ){
449 usage("PIVOT V1 V2 MERGED");
450 }
451 if( blob_read_from_file(&pivot, g.argv[2], ExtFILE)<0 ){
452 fossil_fatal("cannot read %s", g.argv[2]);
453 }
454 if( blob_read_from_file(&v1, g.argv[3], ExtFILE)<0 ){
455 fossil_fatal("cannot read %s", g.argv[3]);
456 }
457 if( blob_read_from_file(&v2, g.argv[4], ExtFILE)<0 ){
458 fossil_fatal("cannot read %s", g.argv[4]);
459 }
460 nConflict = blob_merge(&pivot, &v1, &v2, &merged);
461 if( blob_write_to_file(&merged, g.argv[5])<(int)blob_size(&merged) ){
462 fossil_fatal("cannot write %s", g.argv[4]);
 
 
463 }
 
464 blob_reset(&pivot);
465 blob_reset(&v1);
466 blob_reset(&v2);
467 blob_reset(&merged);
468 if( nConflict>0 ) fossil_warning("WARNING: %d merge conflicts", nConflict);
469 }
470
471 /*
472 ** aSubst is an array of string pairs. The first element of each pair is
@@ -539,30 +681,37 @@
539 const char *zV1, /* Name of file for version merging into (mine) */
540 Blob *pV2, /* Version merging from (yours) */
541 Blob *pOut, /* Output written here */
542 unsigned mergeFlags /* Flags that control operation */
543 ){
544 Blob v1; /* Content of zV1 */
545 int rc; /* Return code of subroutines and this routine */
546 const char *zGMerge; /* Name of the gmerge command */
 
547
548 blob_read_from_file(&v1, zV1, ExtFILE);
549 rc = blob_merge(pPivot, &v1, pV2, pOut);
 
 
 
 
 
 
550 zGMerge = rc<=0 ? 0 : db_get("gmerge-command", 0);
551 if( (mergeFlags & MERGE_DRYRUN)==0
552 && ((zGMerge!=0 && zGMerge[0]!=0)
553 || (rc!=0 && (mergeFlags & MERGE_KEEP_FILES)!=0)) ){
554 char *zPivot; /* Name of the pivot file */
555 char *zOrig; /* Name of the original content file */
556 char *zOther; /* Name of the merge file */
557
558 zPivot = file_newname(zV1, "baseline", 1);
559 blob_write_to_file(pPivot, zPivot);
560 zOrig = file_newname(zV1, "original", 1);
561 blob_write_to_file(&v1, zOrig);
562 zOther = file_newname(zV1, "merge", 1);
563 blob_write_to_file(pV2, zOther);
564 if( rc>0 ){
565 if( zGMerge && zGMerge[0] ){
566 char *zOut; /* Temporary output file */
567 char *zCmd; /* Command to invoke */
568 const char *azSubst[8]; /* Strings to be substituted */
@@ -589,8 +738,8 @@
589 }
590 fossil_free(zPivot);
591 fossil_free(zOrig);
592 fossil_free(zOther);
593 }
594 blob_reset(&v1);
595 return rc;
596 }
597
--- src/merge3.c
+++ src/merge3.c
@@ -98,46 +98,10 @@
98 aC += 3;
99 }
100 return 1;
101 }
102
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
103 /*
104 ** Text of boundary markers for merge conflicts.
105 */
106 static const char *const mergeMarker[] = {
107 /*123456789 123456789 123456789 123456789 123456789 123456789 123456789*/
@@ -186,10 +150,228 @@
150 ensure_line_end(pOut, useCrLf);
151 blob_append(pOut, mergeMarker[iMark], -1);
152 if( ln>0 ) blob_appendf(pOut, " (line %d)", ln);
153 ensure_line_end(pOut, useCrLf);
154 }
155
156 /*
157 ** This is an abstract class for constructing a merge.
158 ** Subclasses of this object format the merge output in different ways.
159 **
160 ** To subclass, create an instance of the MergeBuilder object and fill
161 ** in appropriate method implementations.
162 */
163 typedef struct MergeBuilder MergeBuilder;
164 struct MergeBuilder {
165 void (*xStart)(MergeBuilder*);
166 void (*xSame)(MergeBuilder*, unsigned int);
167 void (*xChngV1)(MergeBuilder*, unsigned int, unsigned int);
168 void (*xChngV2)(MergeBuilder*, unsigned int, unsigned int);
169 void (*xChngBoth)(MergeBuilder*, unsigned int, unsigned int);
170 void (*xConflict)(MergeBuilder*, unsigned int, unsigned int, unsigned int);
171 void (*xEnd)(MergeBuilder*);
172 void (*xDestroy)(MergeBuilder*);
173 const char *zPivot; /* Label or name for the pivot */
174 const char *zV1; /* Label or name for the V1 file */
175 const char *zV2; /* Label or name for the V2 file */
176 const char *zOut; /* Label or name for the output */
177 Blob *pPivot; /* The common ancestor */
178 Blob *pV1; /* First variant */
179 Blob *pV2; /* Second variant */
180 Blob *pOut; /* Write merge results here */
181 int useCrLf; /* Use CRLF line endings */
182 unsigned int lnPivot; /* Lines read from pivot */
183 unsigned int lnV1; /* Lines read from v1 */
184 unsigned int lnV2; /* Lines read from v2 */
185 unsigned int lnOut; /* Lines written to out */
186 unsigned int nConflict; /* Number of conflicts seen */
187 };
188
189
190 /************************* Generic MergeBuilder ******************************/
191 /* These are generic methods for MergeBuilder. They just output debugging
192 ** information. But some of them are useful as base methods for other useful
193 ** implementations of MergeBuilder.
194 */
195
196 /* xStart() and xEnd() are called to generate header and fotter information
197 ** in the output. This is a no-op in the generic implementation.
198 */
199 static void dbgStartEnd(MergeBuilder *p){ (void)p; }
200
201 /* The next N lines of PIVOT are unchanged in both V1 and V2
202 */
203 static void dbgSame(MergeBuilder *p, unsigned int N){
204 blob_appendf(p->pOut, "COPY %u lines (%u..%u) FROM BASELINE\n",
205 N, p->lnPivot, p->lnPivot+N-1);
206 p->lnPivot += N;
207 p->lnV1 += N;
208 p->lnV2 += N;
209 }
210
211 /* The next nPivot lines of the PIVOT are changed into nV1 lines by V1
212 */
213 static void dbgChngV1(MergeBuilder *p, unsigned int nPivot, unsigned int nV1){
214 blob_appendf(p->pOut, "COPY %u lines (%u..%u) FROM V1\n",
215 nV1, p->lnV1, p->lnV1+nV1-1);
216 p->lnPivot += nPivot;
217 p->lnV2 += nPivot;
218 p->lnV1 += nV1;
219 }
220
221 /* The next nPivot lines of the PIVOT are changed into nV2 lines by V2
222 */
223 static void dbgChngV2(MergeBuilder *p, unsigned int nPivot, unsigned int nV2){
224 blob_appendf(p->pOut, "COPY %u lines (%u..%u) FROM V2\n",
225 nV2, p->lnV2, p->lnV2+nV2-1);
226 p->lnPivot += nPivot;
227 p->lnV1 += nPivot;
228 p->lnV2 += nV2;
229 }
230
231 /* The next nPivot lines of the PIVOT are changed into nV lines from V1 and
232 ** V2, which should be the same. In other words, the same change is found
233 ** in both V1 and V2.
234 */
235 static void dbgChngBoth(MergeBuilder *p, unsigned int nPivot, unsigned int nV){
236 blob_appendf(p->pOut, "COPY %u lines (%u..%u) FROM V1\n",
237 nV, p->lnV1, p->lnV1+nV-1);
238 p->lnPivot += nPivot;
239 p->lnV1 += nV;
240 p->lnV2 += nV;
241 }
242
243 /* V1 and V2 have different and overlapping changes. The next nPivot lines
244 ** of the PIVOT are converted into nV1 lines of V1 and nV2 lines of V2.
245 */
246 static void dbgConflict(
247 MergeBuilder *p,
248 unsigned int nPivot,
249 unsigned int nV1,
250 unsigned int nV2
251 ){
252 blob_appendf(p->pOut,
253 "CONFLICT BASELINE(%u..%u) versus V1(%u..%u) versus V2(%u..%u)\n",
254 p->lnPivot, p->lnPivot+nPivot-1,
255 p->lnV1, p->lnPivot+nV1-1,
256 p->lnV2, p->lnPivot+nV2-1);
257 p->lnV1 += nV1;
258 p->lnPivot += nPivot;
259 p->lnV2 += nV2;
260 }
261
262 /* Generic destructor for the MergeBuilder object
263 */
264 static void dbgDestroy(MergeBuilder *p){
265 memset(p, 0, sizeof(*p));
266 }
267
268 /* Generic initializer for a MergeBuilder object
269 */
270 static void mergebuilder_init(MergeBuilder *p){
271 memset(p, 0, sizeof(*p));
272 p->xStart = dbgStartEnd;
273 p->xSame = dbgSame;
274 p->xChngV1 = dbgChngV1;
275 p->xChngV2 = dbgChngV2;
276 p->xChngBoth = dbgChngBoth;
277 p->xConflict = dbgConflict;
278 p->xEnd = dbgStartEnd;
279 p->xDestroy = dbgDestroy;
280 }
281
282
283 /************************* MergeBuilderText **********************************/
284 /* This version of MergeBuilder actually performs a merge on file and puts
285 ** the result in pOut
286 */
287 static void txtStart(MergeBuilder *p){
288 /* If both pV1 and pV2 start with a UTF-8 byte-order-mark (BOM),
289 ** keep it in the output. This should be secure enough not to cause
290 ** unintended changes to the merged file and consistent with what
291 ** users are using in their source files.
292 */
293 if( starts_with_utf8_bom(p->pV1, 0) && starts_with_utf8_bom(p->pV2, 0) ){
294 blob_append(p->pOut, (char*)get_utf8_bom(0), -1);
295 }
296 if( contains_crlf(p->pV1) && contains_crlf(p->pV2) ){
297 p->useCrLf = 1;
298 }
299 }
300 static void txtSame(MergeBuilder *p, unsigned int N){
301 blob_copy_lines(p->pOut, p->pPivot, N); p->lnPivot += N;
302 blob_copy_lines(0, p->pV1, N); p->lnV1 += N;
303 blob_copy_lines(0, p->pV2, N); p->lnV2 += N;
304 }
305 static void txtChngV1(MergeBuilder *p, unsigned int nPivot, unsigned int nV1){
306 blob_copy_lines(0, p->pPivot, nPivot); p->lnPivot += nPivot;
307 blob_copy_lines(0, p->pV2, nPivot); p->lnV2 += nPivot;
308 blob_copy_lines(p->pOut, p->pV1, nV1); p->lnV1 += nV1;
309 }
310 static void txtChngV2(MergeBuilder *p, unsigned int nPivot, unsigned int nV2){
311 blob_copy_lines(0, p->pPivot, nPivot); p->lnPivot += nPivot;
312 blob_copy_lines(0, p->pV1, nPivot); p->lnV1 += nPivot;
313 blob_copy_lines(p->pOut, p->pV2, nV2); p->lnV2 += nV2;
314 }
315 static void txtChngBoth(MergeBuilder *p, unsigned int nPivot, unsigned int nV){
316 blob_copy_lines(0, p->pPivot, nPivot); p->lnPivot += nPivot;
317 blob_copy_lines(0, p->pV1, nPivot); p->lnV1 += nV;
318 blob_copy_lines(p->pOut, p->pV2, nV); p->lnV2 += nV;
319 }
320 static void txtConflict(
321 MergeBuilder *p,
322 unsigned int nPivot,
323 unsigned int nV1,
324 unsigned int nV2
325 ){
326 append_merge_mark(p->pOut, 0, p->lnV1, p->useCrLf);
327 blob_copy_lines(p->pOut, p->pV1, nV1); p->lnV1 += nV1;
328
329 append_merge_mark(p->pOut, 1, p->lnPivot, p->useCrLf);
330 blob_copy_lines(p->pOut, p->pPivot, nPivot); p->lnPivot += nPivot;
331
332 append_merge_mark(p->pOut, 2, p->lnV2, p->useCrLf);
333 blob_copy_lines(p->pOut, p->pV2, nV2); p->lnV2 += nV2;
334
335 append_merge_mark(p->pOut, 3, -1, p->useCrLf);
336 }
337 static void mergebuilder_init_text(MergeBuilder *p){
338 mergebuilder_init(p);
339 p->xStart = txtStart;
340 p->xSame = txtSame;
341 p->xChngV1 = txtChngV1;
342 p->xChngV2 = txtChngV2;
343 p->xChngBoth = txtChngBoth;
344 p->xConflict = txtConflict;
345 }
346 /*****************************************************************************/
347
348 /*
349 ** aC[] is an "edit triple" for changes from A to B. Advance through
350 ** this triple to determine the number of lines to bypass on B in order
351 ** to match an advance of sz lines on A.
352 */
353 static int skip_conflict(
354 int *aC, /* Array of integer triples describing the edit */
355 int i, /* Index in aC[] of current location */
356 int sz, /* Lines of A that have been skipped */
357 unsigned int *pLn /* OUT: Lines of B to skip to keep aligment with A */
358 ){
359 *pLn = 0;
360 while( sz>0 ){
361 if( aC[i]==0 && aC[i+1]==0 && aC[i+2]==0 ) break;
362 if( aC[i]>=sz ){
363 aC[i] -= sz;
364 break;
365 }
366 *pLn += aC[i];
367 *pLn += aC[i+2];
368 sz -= aC[i] + aC[i+1];
369 i += 3;
370 }
371 return i;
372 }
373
374 /*
375 ** Do a three-way merge. Initialize pOut to contain the result.
376 **
377 ** The merge is an edit against pV2. Both pV1 and pV2 have a
@@ -199,156 +381,104 @@
381 ** The return is 0 upon complete success. If any input file is binary,
382 ** -1 is returned and pOut is unmodified. If there are merge
383 ** conflicts, the merge proceeds as best as it can and the number
384 ** of conflicts is returns
385 */
386 static int blob_merge(MergeBuilder *p){
387 int *aC1; /* Changes from pPivot to pV1 */
388 int *aC2; /* Changes from pPivot to pV2 */
389 int i1, i2; /* Index into aC1[] and aC2[] */
390 int nCpy, nDel, nIns; /* Number of lines to copy, delete, or insert */
391 int limit1, limit2; /* Sizes of aC1[] and aC2[] */
392 int nConflict = 0; /* Number of merge conflicts seen so far */
 
 
393 DiffConfig DCfg;
394
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
395 /* Compute the edits that occur from pPivot => pV1 (into aC1)
396 ** and pPivot => pV2 (into aC2). Each of the aC1 and aC2 arrays is
397 ** an array of integer triples. Within each triple, the first integer
398 ** is the number of lines of text to copy directly from the pivot,
399 ** the second integer is the number of lines of text to omit from the
400 ** pivot, and the third integer is the number of lines of text that are
401 ** inserted. The edit array ends with a triple of 0,0,0.
402 */
403 diff_config_init(&DCfg, 0);
404 aC1 = text_diff(p->pPivot, p->pV1, 0, &DCfg);
405 aC2 = text_diff(p->pPivot, p->pV2, 0, &DCfg);
406 if( aC1==0 || aC2==0 ){
407 free(aC1);
408 free(aC2);
409 return -1;
410 }
411
412 blob_rewind(p->pV1); /* Rewind inputs: Needed to reconstruct output */
413 blob_rewind(p->pV2);
414 blob_rewind(p->pPivot);
415
416 /* Determine the length of the aC1[] and aC2[] change vectors */
417 for(i1=0; aC1[i1] || aC1[i1+1] || aC1[i1+2]; i1+=3){}
418 limit1 = i1;
419 for(i2=0; aC2[i2] || aC2[i2+1] || aC2[i2+2]; i2+=3){}
420 limit2 = i2;
421
422 /* Output header text and do any other required initialization */
423 p->xStart(p);
 
 
 
 
 
 
424
425 /* Loop over the two edit vectors and use them to compute merged text
426 ** which is written into pOut. i1 and i2 are multiples of 3 which are
427 ** indices into aC1[] and aC2[] to the edit triple currently being
428 ** processed
429 */
430 i1 = i2 = 0;
 
431 while( i1<limit1 && i2<limit2 ){
 
 
 
 
432 if( aC1[i1]>0 && aC2[i2]>0 ){
433 /* Output text that is unchanged in both V1 and V2 */
434 nCpy = min(aC1[i1], aC2[i2]);
435 p->xSame(p, nCpy);
 
 
 
436 aC1[i1] -= nCpy;
437 aC2[i2] -= nCpy;
438 }else
439 if( aC1[i1] >= aC2[i2+1] && aC1[i1]>0 && aC2[i2+1]+aC2[i2+2]>0 ){
440 /* Output edits to V2 that occurs within unchanged regions of V1 */
441 nDel = aC2[i2+1];
442 nIns = aC2[i2+2];
443 p->xChngV2(p, nDel, nIns);
 
 
 
444 aC1[i1] -= nDel;
445 i2 += 3;
446 }else
447 if( aC2[i2] >= aC1[i1+1] && aC2[i2]>0 && aC1[i1+1]+aC1[i1+2]>0 ){
448 /* Output edits to V1 that occur within unchanged regions of V2 */
449 nDel = aC1[i1+1];
450 nIns = aC1[i1+2];
451 p->xChngV2(p, nDel, nIns);
 
 
 
452 aC2[i2] -= nDel;
453 i1 += 3;
454 }else
455 if( sameEdit(&aC1[i1], &aC2[i2], p->pV1, p->pV2) ){
456 /* Output edits that are identical in both V1 and V2. */
457 assert( aC1[i1]==0 );
458 nDel = aC1[i1+1];
459 nIns = aC1[i1+2];
460 p->xChngBoth(p, nDel, nIns);
 
 
 
461 i1 += 3;
462 i2 += 3;
463 }else
464 {
465 /* We have found a region where different edits to V1 and V2 overlap.
466 ** This is a merge conflict. Find the size of the conflict, then
467 ** output both possible edits separated by distinctive marks.
468 */
469 unsigned int sz = 1; /* Size of the conflict in lines */
470 unsigned int nV1, nV2;
471 nConflict++;
472 while( !ends_at_CPY(&aC1[i1], sz) || !ends_at_CPY(&aC2[i2], sz) ){
473 sz++;
474 }
475 i1 = skip_conflict(aC1, i1, sz, &nV1);
476 i2 = skip_conflict(aC2, i2, sz, &nV2);
477 p->xConflict(p, sz, nV1, nV2);
478 }
479
 
 
 
 
 
 
 
 
 
480 /* If we are finished with an edit triple, advance to the next
481 ** triple.
482 */
483 if( i1<limit1 && aC1[i1]==0 && aC1[i1+1]==0 && aC1[i1+2]==0 ) i1+=3;
484 if( i2<limit2 && aC2[i2]==0 && aC2[i2+1]==0 && aC2[i2+2]==0 ) i2+=3;
@@ -356,20 +486,18 @@
486
487 /* When one of the two edit vectors reaches its end, there might still
488 ** be an insert in the other edit vector. Output this remaining
489 ** insert.
490 */
 
 
 
491 if( i1<limit1 && aC1[i1+2]>0 ){
492 p->xChngV1(p, 0, aC1[i1+2]);
 
493 }else if( i2<limit2 && aC2[i2+2]>0 ){
494 p->xChngV1(p, 0, aC2[i2+2]);
 
495 }
496
497 /* Output footer text */
498 p->xEnd(p);
499
500 free(aC1);
501 free(aC2);
502 return nConflict;
503 }
@@ -412,14 +540,15 @@
540 }
541
542 /*
543 ** COMMAND: 3-way-merge*
544 **
545 ** Usage: %fossil 3-way-merge BASELINE V1 V2 [MERGED]
546 **
547 ** Inputs are files BASELINE, V1, and V2. The file MERGED is generated
548 ** as output. If no MERGED file is specified, output is sent to
549 ** stdout.
550 **
551 ** BASELINE is a common ancestor of two files V1 and V2 that have diverging
552 ** edits. The generated output file MERGED is the combination of all
553 ** changes in both V1 and V2.
554 **
@@ -436,37 +565,50 @@
565 ** cp Xup.c Xbase.c
566 ** # Verify that everything still works
567 ** fossil commit
568 **
569 */
570 void merge_3way_cmd(void){
571 MergeBuilder s;
572 int nConflict;
573 Blob pivot, v1, v2, out;
574
575 mergebuilder_init_text(&s);
576 if( find_option("debug", 0, 0) ){
577 mergebuilder_init(&s);
578 }
579 blob_zero(&pivot); s.pPivot = &pivot;
580 blob_zero(&v1); s.pV1 = &v1;
581 blob_zero(&v2); s.pV2 = &v2;
582 blob_zero(&out); s.pOut = &out;
583
584 /* We should be done with options.. */
585 verify_all_options();
586
587 if( g.argc!=6 && g.argc!=5 ){
588 usage("[OPTIONS] PIVOT V1 V2 [MERGED]");
589 }
590 if( blob_read_from_file(s.pPivot, g.argv[2], ExtFILE)<0 ){
591 fossil_fatal("cannot read %s", g.argv[2]);
592 }
593 if( blob_read_from_file(s.pV1, g.argv[3], ExtFILE)<0 ){
594 fossil_fatal("cannot read %s", g.argv[3]);
595 }
596 if( blob_read_from_file(s.pV2, g.argv[4], ExtFILE)<0 ){
597 fossil_fatal("cannot read %s", g.argv[4]);
598 }
599 nConflict = blob_merge(&s);
600 if( g.argc==6 ){
601 blob_write_to_file(s.pOut, g.argv[5]);
602 }else{
603 blob_write_to_file(s.pOut, "-");
604 }
605 s.xDestroy(&s);
606 blob_reset(&pivot);
607 blob_reset(&v1);
608 blob_reset(&v2);
609 blob_reset(&out);
610 if( nConflict>0 ) fossil_warning("WARNING: %d merge conflicts", nConflict);
611 }
612
613 /*
614 ** aSubst is an array of string pairs. The first element of each pair is
@@ -539,30 +681,37 @@
681 const char *zV1, /* Name of file for version merging into (mine) */
682 Blob *pV2, /* Version merging from (yours) */
683 Blob *pOut, /* Output written here */
684 unsigned mergeFlags /* Flags that control operation */
685 ){
686 Blob v1; /* Content of zV1 */
687 int rc; /* Return code of subroutines and this routine */
688 const char *zGMerge; /* Name of the gmerge command */
689 MergeBuilder s; /* The merge state */
690
691 mergebuilder_init_text(&s);
692 s.pPivot = pPivot;
693 s.pV1 = &v1;
694 s.pV2 = pV2;
695 blob_zero(pOut);
696 s.pOut = pOut;
697 blob_read_from_file(s.pV1, zV1, ExtFILE);
698 rc = blob_merge(&s);
699 zGMerge = rc<=0 ? 0 : db_get("gmerge-command", 0);
700 if( (mergeFlags & MERGE_DRYRUN)==0
701 && ((zGMerge!=0 && zGMerge[0]!=0)
702 || (rc!=0 && (mergeFlags & MERGE_KEEP_FILES)!=0)) ){
703 char *zPivot; /* Name of the pivot file */
704 char *zOrig; /* Name of the original content file */
705 char *zOther; /* Name of the merge file */
706
707 zPivot = file_newname(zV1, "baseline", 1);
708 blob_write_to_file(s.pPivot, zPivot);
709 zOrig = file_newname(zV1, "original", 1);
710 blob_write_to_file(s.pV1, zOrig);
711 zOther = file_newname(zV1, "merge", 1);
712 blob_write_to_file(s.pV2, zOther);
713 if( rc>0 ){
714 if( zGMerge && zGMerge[0] ){
715 char *zOut; /* Temporary output file */
716 char *zCmd; /* Command to invoke */
717 const char *azSubst[8]; /* Strings to be substituted */
@@ -589,8 +738,8 @@
738 }
739 fossil_free(zPivot);
740 fossil_free(zOrig);
741 fossil_free(zOther);
742 }
743 s.xDestroy(&s);
744 return rc;
745 }
746

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button