Home
About Perforce
Contact
Site Map
RSSThe DiffMerge Source Code
Read this page along with Code in Motion, a chapter from the book, Beautiful Code, (O'Reilly, 2007).
1: /*
2: * Copyright 1995, 2007 Perforce Software. All rights reserved.
3: *
4: * This file is part of Perforce - the FAST SCM System.
5: */
6:
7: /*
8: * diffmerge.cc - 3 way file merge
9: *
10: * Classes defined:
11: *
12: * DiffMerge - control block for merging
13: *
14: * Public methods:
15: *
16: * DiffMerge::DiffMerge() - Merge 3 files to produce integrated result
17: * DiffMerge::~DiffMerge() - dispose of DiffMerge and its contents
18: * DiffMerge::Read() - produce next part of integrated result
19: *
20: * Internal classes:
21: *
22: * DiffFfile - line oriented ReadFile
23: * DiffDFile - a diff stream
24: *
25: * Private methods:
26: *
27: * DiffDFile::DiffDFile() - start a diff(1) between the base and one leg
28: *
29: * History:
30: * 2-18-97 (seiwald) - translated to C++.
31: */
32:
33: # define NEED_TYPES
34: # define NEED_FILE
35:
36: # include <stdhdrs.h>
37:
38: # include <error.h>
39: # include <debug.h>
40: # include <strbuf.h>
41: # include <filesys.h>
42:
43: # include <readfile.h>
44:
45: # include <diff.h>
46: # include <diffsp.h>
47: # include <diffan.h>
48: # include <diffmerge.h>
49:
50: # define DEBUG_MERGE ( p4debug.GetLevel( DT_DIFF ) >= 3 )
51:
52: /*
53: * selbitTab - how to output each leg given the next pair of diffs
54: *
55: * DiffLeg represents the leg we're looking to output, and DiffDiffs
56: * is how DiffDiff() said the next pair of diffs merged.
57: */
58:
59: enum DiffLeg { DL_BASE, DL_LEG1, DL_LEG2, DL_LAST } ;
60:
61: const int selbitTab[ DL_LAST ][ DD_LAST ] = {
62:
63: /* BASE at */ /* EOF */ 0,
64: /* LEG1 */ SEL_BASE|SEL_LEG2, // base == leg2
65: /* LEG2 */ SEL_BASE|SEL_LEG1, // base == leg1
66: /* BOTH */ SEL_BASE,
67: /* CONF */ SEL_BASE|SEL_CONF,
68: /* ALL */ SEL_ALL,
69:
70: /* LEG1 at */ /* EOF */ 0,
71: /* LEG1 */ SEL_LEG1|SEL_RSLT,
72: /* LEG2 */ 0,
73: /* BOTH */ SEL_LEG1|SEL_LEG2|SEL_RSLT, // leg1 == leg2
74: /* CONF */ SEL_LEG1|SEL_RSLT|SEL_CONF, // leg1 != leg2
75: /* ALL */ 0,
76:
77: /* LEG2 at */ /* EOF */ 0,
78: /* LEG1 */ 0,
79: /* LEG2 */ SEL_LEG2|SEL_RSLT,
80: /* BOTH */ 0, // == leg1
81: /* CONF */ SEL_LEG2|SEL_RSLT|SEL_CONF, // leg1 != leg2
82: /* ALL */ 0,
83:
84: };
85:
86: /*
87: * MergeState - state for Read()'s state machine
88: */
89:
90: enum MergeState {
91: MS_DIFFDIFF, /* do diff diff */
92: MS_BASE, /* dumping the original */
93: MS_LEG1, /* dumping leg1 */
94: MS_LEG2, /* dumping leg2 */
95: MS_DONE /* return 0 */
96: } ;
97:
98: /*
99: * DiffDFile::DiffDFile() - popen(3) a diff(1) between the base and one leg
100: */
101:
102: inline int dmin( int a, int b ) { return a < b ? a : b; }
103:
104: /*
105: * DiffFfile - line oriented ReadFile
106: */
107:
108: class DiffFfile : public Sequence {
109:
110: public:
111: DiffFfile(
112: FileSys *file,
113: const DiffFlags &flags,
114: LineType lt,
115: Error *e )
116: : Sequence( file, flags, e )
117: {
118: lineType = lt;
119: end = 0;
120: }
121:
122: size_t MaxLineLength() const;
123:
124: LineType lineType;
125:
126: /* Track our progress for output */
127:
128: int start; /* first line to output */
129: int end; /* last line, and sync point */
130:
131: } ;
132:
133: /*
134: * DiffDFile - a diff stream
135: */
136:
137: class DiffDFile : public DiffAnalyze {
138:
139: public:
140: DiffDFile( DiffFfile *base, DiffFfile *leg )
141: : DiffAnalyze( base, leg )
142: {
143: this->base = base;
144: this->leg = leg;
145: s = *GetSnake();
146: }
147:
148: int StartLeg() { return s.y - leg->end; }
149: int StartBase() { return s.x - base->end; }
150: int EndLeg() { return s.v - leg->end; }
151: int EndBase() { return s.u - base->end; }
152:
153: // alias the above for the leg1 leg2 snake ONLY
154:
155: int StartL1() { return StartBase(); }
156: int StartL2() { return StartLeg(); }
157: int EndL1() { return EndBase(); }
158: int EndL2() { return EndLeg(); }
159:
160: void AdvanceAndSync();
161:
162: public:
163:
164: Snake s; /* snake of differences */
165:
166: private:
167:
168: DiffFfile *base; /* for StartBase()/EndBase() */
169: DiffFfile *leg; /* for StartLeg()/EndLeg() */
170:
171: } ;
172:
173: void
174: DiffDFile::AdvanceAndSync()
175: {
176: // Advance
177:
178: while( s.next && ( EndLeg() <= 0 || EndBase() <= 0 ) )
179: s = *s.next;
180:
181: // Sync up to starting point
182:
183: int adj = dmin( StartLeg(), StartBase() );
184: if( adj < 0 ) { s.y += -adj; s.x += -adj; }
185: }
186:
187: void
188: SnakeDump( const char *t, Snake *s )
189: {
190: printf( "snake %s\n", t );
191:
192: while( s )
193: {
194: printf("s %x %d %d %d %d\n", s, s->x, s->u, s->y, s->v );
195: s = s->next;
196: }
197: }
198:
199: /*
200: * DiffMerge::DiffMerge() - Merge 3 files to produce integrated result
201: */
202:
203: DiffMerge::DiffMerge(
204: FileSys *base,
205: FileSys *leg1,
206: FileSys *leg2,
207: const DiffFlags &flags,
208: LineType lineType,
209: Error *e )
210: {
211: readFile = 0;
212: bf = lf1 = lf2 = 0;
213: df1 = df2 = df3 = 0;
214:
215: state = MS_DIFFDIFF;
216:
217: if( DEBUG_MERGE )
218: printf( "merging %s x %s x %s\n", base->Name(),
219: leg1->Name(), leg2->Name() );
220:
221: /*
222: ** Open the three input files.
223: */
224:
225: bf = new DiffFfile( base, flags, lineType, e );
226: lf1 = new DiffFfile( leg1, flags, lineType, e );
227: lf2 = new DiffFfile( leg2, flags, lineType, e );
228:
229: if( e->Test() )
230: return;
231:
232: /*
233: ** Fork off the two diffs, between the base and l1, and between
234: ** base and l2. Prime the diff file structures by reading the
235: ** first two diffs.
236: */
237:
238: df1 = new DiffDFile( bf, lf1 );
239: df2 = new DiffDFile( bf, lf2 );
240: df3 = new DiffDFile( lf1, lf2 );
241:
242: if( DEBUG_MERGE )
243: {
244: SnakeDump( "df1", &df1->s );
245: SnakeDump( "df2", &df2->s );
246: SnakeDump( "df3", &df3->s );
247: }
248: }
249:
250: /*
251: * DiffMerge::~DiffMerge() - dispose of DiffMerge and its contents
252: */
253:
254: DiffMerge::~DiffMerge()
255: {
256: delete bf;
257: delete lf1;
258: delete lf2;
259:
260: delete df1;
261: delete df2;
262: delete df3;
263: }
264:
265: /*
266: * DiffMerge::Read() - produce next part of integrated result
267: */
268:
269: int
270: DiffMerge::Read( char *buf, int len, int *outlen )
271: {
272: for(;;)
273: {
274: /*
275: * If readFile is set, we're still returning output from
276: * one of the file legs. Keep doing so until the user's
277: * buffer is satisfied, or we've output this chunk.
278: */
279:
280: if( readFile )
281: {
282: *outlen = readFile->CopyLines(
283: readFile->start,
284: readFile->end,
285: buf, len,
286: readFile->lineType );
287:
288: if( !*outlen )
289: readFile = 0;
290:
291: return selbits;
292: }
293:
294: switch( state )
295: {
296: case MS_DIFFDIFF:
297:
298: /* do diff diff */
299:
300: if( ( diffDiff = DiffDiff() ) == DD_EOF )
301: {
302: state = MS_DONE;
303: break;
304: }
305:
306: if( diffDiff != DD_ALL)
307: {
308: *outlen = 0;
309: state = MS_BASE;
310: return SEL_ALL;
311: }
312:
313: case MS_BASE: /* dumping the original */
314:
315: if( selbits = selbitTab[ DL_BASE ][ diffDiff ] )
316: {
317: readFile = bf;
318: readFile->SeekLine( bf->start );
319: state = MS_LEG1;
320: break;
321: }
322:
323: case MS_LEG1: /* dumping leg1 */
324:
325: if( selbits = selbitTab[ DL_LEG1 ][ diffDiff ] )
326: {
327: readFile = lf1;
328: readFile->SeekLine( lf1->start );
329: state = MS_LEG2;
330: break;
331: }
332:
333: case MS_LEG2: /* dumping leg2 */
334:
335: if( selbits = selbitTab[ DL_LEG2 ][ diffDiff ] )
336: {
337: readFile = lf2;
338: readFile->SeekLine( lf2->start );
339: }
340:
341: state = MS_DIFFDIFF;
342: break;
343:
344: case MS_DONE: /* return 0 */
345:
346: *outlen = 0;
347: return 0;
348: }
349: }
350: }
351:
352: /*
353: * DiffMerge::BitNames() - turn out mnemonic(?) names for the flags
354: */
355:
356: const char *
357: DiffMerge::BitNames( int bits )
358: {
359: switch( bits )
360: {
361: case SEL_ALL: return "ALL";
362: case SEL_BASE: return "BASE";
363: case SEL_BASE|SEL_CONF: return "BASE CONFLICT";
364: case SEL_BASE|SEL_LEG1: return "BASE L1";
365: case SEL_BASE|SEL_LEG2: return "BASE L2";
366: case SEL_LEG1|SEL_RSLT|SEL_CONF:return "L1 CONFLICT";
367: case SEL_LEG2|SEL_RSLT|SEL_CONF:return "L2 CONFLICT";
368: case SEL_LEG1|SEL_RSLT: return "L1";
369: case SEL_LEG2|SEL_RSLT: return "L2";
370: case SEL_LEG1|SEL_LEG2|SEL_RSLT:return "L1 L2";
371: default: return "?";
372: }
373: }
374:
375: /*
376: * DiffMerge::MaxLineLength() - find the maximum length of a line in any file
377: */
378:
379: size_t DiffMerge::MaxLineLength() const
380: {
381: size_t l, m = bf->MaxLineLength();
382:
383: if( ( l = lf1->MaxLineLength() ) > m ) m = l;
384: if( ( l = lf2->MaxLineLength() ) > m ) m = l;
385:
386: return m;
387: }
388:
389: /*
390: * DiffFfile::MaxLineLength() - find the maximum length of a line
391: */
392:
393: size_t
394: DiffFfile::MaxLineLength() const
395: {
396: size_t m = 0;
397:
398: for( int l = 0; l < Lines(); l++ )
399: if( m < Length( l ) )
400: m = Length( l );
401:
402: return m;
403: }
404:
405: enum Mode {
406: ALL, ALL1, ALL2,
407: BOTH, BOTHX, CONF,
408: DEL1, DEL2,
409: DELB, DELB1, DELB2,
410: EDIT1, EDIT2,
411: EDITC1, EDITC2,
412: INSX1, INSX2,
413: INSY1, INSY2,
414: INS12, INSX12, INSY12,
415: INS1, INS2,
416: INSC1, INSC2,
417: INSC3, INSC4,
418: INSC5, INSC6
419: } ;
420:
421: const char *ModeNames[] = {
422: "ALL", "ALL1", "ALL2",
423: "BOTH", "BOTHX", "CONF",
424: "DEL1", "DEL2",
425: "DELB", "DELB1", "DELB2",
426: "EDIT1", "EDIT2",
427: "EDITC1", "EDITC2",
428: "INSX1", "INSX2",
429: "INSY1", "INSY2",
430: "INS12", "INSX12", "INSY12",
431: "INS1", "INS2",
432: "INSC1", "INSC2",
433: "INSC3", "INSC4",
434: "INSC5", "INSC6"
435: } ;
436:
437: const struct DiffGrid {
438:
439: Mode mode;
440: DiffDiffs diffs;
441:
442: } diffGrid[2][2][2][2][2][2] = {
443:
444: // ---- BASE/LEG1 ---- BASE/LEG2 ---- LEG1/LEG2
445: // || || ||
446: // __ __ __ __ __ _X __ __ X_ __ __ XX
447: // __ _X __ __ _X _X __ _X X_ __ _X XX
448: // __ X_ __ __ X_ _X __ X_ X_ __ X_ XX
449: // __ XX __ __ XX _X __ XX X_ __ XX XX
450:
451: CONF,DD_CONF, INSX1,DD_LEG1, INSX2,DD_LEG2, BOTHX,DD_BOTH,
452: CONF,DD_CONF, INSC6,DD_CONF, INSX2,DD_LEG2, BOTH,DD_BOTH,
453: CONF,DD_CONF, CONF,DD_CONF, DELB,DD_BOTH, DELB,DD_BOTH,
454: EDITC1,DD_CONF, EDIT1,DD_LEG1, EDIT1,DD_LEG1, ALL2,DD_ALL,
455:
456: // _X __ __ _X __ _X _X __ X_ _X __ XX
457: // _X _X __ _X _X _X _X _X X_ _X _X XX
458: // _X X_ __ _X X_ _X _X X_ X_ _X X_ XX
459: // _X XX __ _X XX _X _X XX X_ _X XX XX
460:
461: CONF,DD_CONF, INSX1,DD_LEG1, INSC5,DD_CONF, BOTH,DD_BOTH,
462: INS12,DD_CONF, INSX12,DD_CONF, INSY12,DD_CONF, BOTH,DD_BOTH,
463: CONF,DD_CONF, CONF,DD_CONF, INSC3,DD_CONF, INSC3,DD_CONF,
464: INSX1,DD_LEG1, INSX1,DD_LEG1, INSC1,DD_CONF, ALL2,DD_ALL,
465:
466: // X_ __ __ X_ __ _X X_ __ X_ X_ __ XX
467: // X_ _X __ X_ _X _X X_ _X X_ X_ _X XX
468: // X_ X_ __ X_ X_ _X X_ X_ X_ X_ X_ XX
469: // X_ XX __ X_ XX _X X_ XX X_ X_ XX XX
470:
471: CONF,DD_CONF, DELB,DD_BOTH, CONF,DD_CONF, DELB,DD_BOTH,
472: CONF,DD_CONF, INSC4,DD_CONF, CONF,DD_CONF, INSC4,DD_CONF,
473: DELB,DD_BOTH, DELB,DD_BOTH, DELB,DD_BOTH, DELB,DD_BOTH,
474: DEL1,DD_LEG1, DEL1,DD_LEG1, DEL1,DD_LEG1, ALL2,DD_ALL,
475:
476: // XX __ __ XX __ _X XX __ X_ XX __ XX
477: // XX _X __ XX _X _X XX _X X_ XX _X XX
478: // XX X_ __ XX X_ _X XX X_ X_ XX X_ XX
479: // XX XX __ XX XX _X XX XX X_ XX XX XX
480:
481: EDITC2,DD_CONF, EDIT2,DD_LEG2, EDIT2,DD_LEG2, ALL1,DD_ALL,
482: INSX2,DD_LEG2, INSC2,DD_CONF, INSX2,DD_LEG2, ALL1,DD_ALL,
483: DEL2,DD_LEG2, DEL2,DD_LEG2, DEL2,DD_LEG2, ALL1,DD_ALL,
484: ALL,DD_ALL, ALL,DD_ALL, ALL,DD_ALL, ALL,DD_ALL
485: } ;
486:
487: DiffDiffs
488: DiffMerge::DiffDiff()
489: {
490: /* All legs completely output? */
491:
492: if( bf->end == bf->Lines() &&
493: lf1->end == lf1->Lines() &&
494: lf2->end == lf2->Lines() )
495: return( DD_EOF );
496:
497: /* Advance to next snake, if past old one. */
498:
499: df1->AdvanceAndSync();
500: df2->AdvanceAndSync();
501: df3->AdvanceAndSync();
502:
503: int lb = 0, l1 = 0, l2 = 0;
504:
505: DiffGrid d = diffGrid
506: [ df1->StartLeg() == 0 ][ df1->StartBase() == 0 ]
507: [ df2->StartLeg() == 0 ][ df2->StartBase() == 0 ]
508: [ df3->StartL1() == 0 ][ df3->StartL2() == 0 ];
509:
510: Mode initialMode = d.mode;
511:
512: // Pre-process rules, typically the outer snake information
513: // contradicts the inner snake, its not perfect, but we use
514: // the length of the snake to determine the best outcome.
515:
516: switch( d.mode )
517: {
518: case INSC1:
519: if( df3->EndL1() > df2->EndBase() ) // trust outer - insert L2
520: { d.mode = INSY2; d.diffs = DD_LEG2; break; }
521:
522: d.mode = INS1; d.diffs = DD_LEG1; // trust inner - insert L1
523: break;
524:
525: case INSC2:
526: if( df3->EndL2() > df1->EndBase() ) // trust outer - insert L2
527: { d.mode = INSY1; d.diffs = DD_LEG1; break; }
528:
529: d.mode = INS2; d.diffs = DD_LEG2; // trust inner = insert L1
530: break;
531:
532: case INSC3:
533: if( df3->EndL1() >= df1->EndLeg() ) // trust outer - delete base
534: { d.mode = DELB1; d.diffs = DD_BOTH; break; }
535:
536: d.mode = INS1; d.diffs = DD_LEG1; // trust inner - insert L1
537: break;
538:
539: case INSC4:
540: if( df3->EndL2() >= df2->EndLeg() ) // trust outer - delete base
541: { d.mode = DELB2; d.diffs = DD_BOTH; break; }
542:
543: d.mode = INS2; d.diffs = DD_LEG2; // trust inner - insert L2
544: break;
545:
546: case INSC5:
547: if( df3->EndL1() >= df1->EndLeg() ) // trust outer - delete base
548: { d.mode = DELB1; d.diffs = DD_BOTH; break; }
549:
550: if( df3->EndL1() >= df1->EndBase() ) // trust outer - insert L2
551: { d.mode = INSX2; d.diffs = DD_LEG2; break; }
552:
553: d.mode = INS1; d.diffs = DD_LEG1; // trust inner - insert L1
554: break;
555:
556: case INSC6:
557: if( df3->EndL2() >= df2->EndLeg() ) // trust outer - delete base
558: { d.mode = DELB2; d.diffs = DD_BOTH; break; }
559:
560: if( df3->EndL2() >= df2->EndBase() ) // trust outer - insert L1
561: { d.mode = INSX1; d.diffs = DD_LEG1; break; }
562:
563: d.mode = INS2; d.diffs = DD_LEG2; // trust inner - insert L2
564: break;
565:
566: case INSX12:
567: if( df3->StartL1() < df1->StartLeg() &&
568: df3->EndL1() >= df1->StartLeg() &&
569: df3->EndL2() >= df2->StartLeg() ) // trust outer - insert L1
570: { d.mode = INSY1; d.diffs = DD_LEG1; }
571: break;
572:
573: case INSY12:
574: if( df3->StartL2() < df2->StartLeg() &&
575: df3->EndL2() >= df2->StartLeg() &&
576: df3->EndL1() >= df1->StartLeg() ) // trust outer - insert L2
577: { d.mode = INSY2; d.diffs = DD_LEG2; }
578: break;
579: }
580:
581: // Advance files
582:
583: switch( d.mode )
584: {
585: case ALL1:
586: lb = l1 = l2 = dmin( df1->EndBase(), df3->EndL1() );
587: break;
588:
589: case ALL2:
590: lb = l1 = l2 = dmin( df2->EndBase(), df3->EndL2() );
591: break;
592:
593: case ALL:
594: lb = l1 = l2 = dmin( df1->EndBase(), df2->EndBase() );
595: break;
596:
597: case BOTH:
598: lb = dmin( df1->StartBase(), df2->StartBase() );
599: l1 = dmin( df1->StartLeg(), df3->EndL1() );
600: l2 = dmin( df2->StartLeg(), df3->EndL2() );
601: l1 = l2 = dmin( l1, l2 );
602: break;
603:
604: case BOTHX:
605: lb = dmin( df1->StartBase(), df2->StartBase() );
606: l1 = dmin( df1->StartLeg(), df3->EndL1() );
607: l2 = dmin( df2->StartLeg(), df3->EndL2() );
608: l1 = l2 = dmin( l1, l2 );
609: lb = dmin( lb, l1 );
610: break;
611:
612: case DELB:
613: lb = dmin( df1->StartBase(), df2->StartBase() );
614: break;
615:
616: case DELB1:
617: lb = df1->EndBase();
618: break;
619:
620: case DELB2:
621: lb = df2->EndBase();
622: break;
623:
624: case DEL1:
625: lb = l2 = dmin( df1->StartBase(), df2->EndBase() );
626: break;
627:
628: case DEL2:
629: lb = l1 = dmin( df2->StartBase(), df1->EndBase() );
630: break;
631:
632: case EDIT1:
633: case EDITC1:
634: l1 = dmin( df1->StartLeg(), df3->StartL1() );
635: lb = l2 = dmin( df1->StartBase(), df2->EndBase() );
636: break;
637:
638: case EDIT2:
639: case EDITC2:
640: l2 = dmin( df2->StartLeg(), df3->StartL2() );
641: lb = l1 = dmin( df1->EndBase(), df2->StartBase() );
642: break;
643:
644: case INSX1:
645: l1 = dmin( df1->StartLeg(), df3->StartL1() );
646: break;
647:
648: case INSX2:
649: l2 = dmin( df2->StartLeg(), df3->StartL2() );
650: break;
651:
652: case INSY1:
653: l1 = df3->StartL1();
654: break;
655:
656: case INSY2:
657: l2 = df3->StartL2();
658: break;
659:
660: case INS1:
661: l1 = df1->StartLeg();
662: break;
663:
664: case INS2:
665: l2 = df2->StartLeg();
666: break;
667:
668: case INSX12:
669: l1 = dmin( df1->StartLeg(), df3->StartL1() );
670: l2 = df2->StartLeg();
671: break;
672:
673: case INSY12:
674: l1 = df1->StartLeg();
675: l2 = dmin( df2->StartLeg(), df3->StartL2() );
676: break;
677:
678: case CONF:
679: lb = dmin( df1->StartBase(), df2->StartBase() );
680: // fall through
681:
682: case INS12:
683: l1 = dmin( df1->StartLeg(), df3->StartL1() );
684: l2 = dmin( df2->StartLeg(), df3->StartL2() );
685: break;
686: }
687:
688: if( DEBUG_MERGE )
689: {
690: printf("\nMMMM %d+%d (%d-%d,%d-%d) %d+%d (%d-%d,%d-%d) ",
691: lf1->end, bf->end, df1->s.y, df1->s.v, df1->s.x, df1->s.u,
692: lf2->end, bf->end, df2->s.y, df2->s.v, df2->s.x, df2->s.u);
693:
694: printf("%d+%d (%d-%d,%d-%d) [%c%c %c%c %c%c]\n",
695: lf1->end, lf2->end, df3->s.x, df3->s.u, df3->s.y, df3->s.v,
696: df1->StartLeg() == 0 ? 'X' : '_',
697: df1->StartBase() == 0 ? 'X' : '_',
698: df2->StartLeg() == 0 ? 'X' : '_',
699: df2->StartBase() == 0 ? 'X' : '_',
700: df3->StartL1() == 0 ? 'X' : '_',
701: df3->StartL2() == 0 ? 'X' : '_');
702:
703: printf("MMMM %s%s%s advancing %+d,%+d,%+d\n",
704: ModeNames[ initialMode ],
705: d.mode != initialMode ? " -> " : "",
706: d.mode != initialMode ? ModeNames[ d.mode ] : "",
707: lb, l1, l2 );
708: }
709:
710: /* Set output range (start/end). End is new sync point. */
711:
712: bf->start = bf->end;
713: lf1->start = lf1->end;
714: lf2->start = lf2->end;
715:
716: bf->end += lb;
717: lf1->end += l1;
718: lf2->end += l2;
719:
720: /* If an action may be downgraded from a conflict (currently only
721: * EDITC1 and EDITC2 fit that category), make sure they actually get
722: * through the processing or downgrade it now.
723: */
724:
725: if( bf->end == bf->Lines() &&
726: lf1->end == lf1->Lines() &&
727: lf2->end == lf2->Lines() )
728: {
729: if( d.mode == EDITC1 ) d.diffs = DD_LEG1;
730: if( d.mode == EDITC2 ) d.diffs = DD_LEG2;
731: }
732:
733: /* Handle Conflicts (post processing)
734: *
735: * Sometimes it is necessary to extend the conflict area to produce
736: * the best conflict. Advance all snakes to the conflict end region
737: * and see what happens next. Depending on the result, we may grow
738: * the conflict several times before returning.
739: */
740:
741: DiffGrid n;
742: int extendConflict = 0;
743:
744: while( d.diffs == DD_CONF && ( bf->end != bf->Lines() ||
745: lf1->end != lf1->Lines() ||
746: lf2->end != lf2->Lines() ) )
747: {
748: int ab = 0, a1 = 0, a2 = 0;
749:
750: // Conflict caused by inserting on L1 and L2 can never extend
751: // the base.
752:
753: int noBaseAdvance = ( d.mode == INS12
754: || d.mode == INSX12
755: || d.mode == INSY12 );
756:
757: df1->AdvanceAndSync();
758: df2->AdvanceAndSync();
759: df3->AdvanceAndSync();
760:
761: n = diffGrid
762: [ df1->StartLeg() == 0 ][ df1->StartBase() == 0 ]
763: [ df2->StartLeg() == 0 ][ df2->StartBase() == 0 ]
764: [ 0 ][ 0 ];
765:
766: switch( n.mode )
767: {
768: case INSX1: case INS1:
769: a1 = df1->StartLeg();
770: break;
771: case INSX2: case INS2:
772: a2 = df2->StartLeg();
773: break;
774: case DEL1:
775: ab = a2 = dmin( df1->StartBase(), df2->EndBase() );
776: break;
777: case DEL2:
778: ab = a1 = dmin( df2->StartBase(), df1->EndBase() );
779: break;
780: case DELB:
781: // Prior to adding EDITC1 and EDITC2, DELB would not
782: // extend the conflict area, lets keep it that way.
783: if( d.mode != EDITC1 && d.mode != EDITC2 )
784: break;
785: case CONF:
786: ab = dmin( df1->StartBase(), df2->StartBase() );
787: case INS12:
788: if( !noBaseAdvance )
789: {
790: a1 = dmin( df1->StartLeg(), df3->StartL1() );
791: a2 = dmin( df2->StartLeg(), df3->StartL2() );
792: break;
793: }
794:
795: // INS12,INSX12,INSY12 (conflict) made a bad decision and
796: // went with an outer snake, since we are still in the
797: // inner snake/ make up for that now by advancing to
798: // inner startlegs.
799:
800: if( df1->StartLeg() > df3->EndL1() &&
801: df2->StartLeg() > df3->EndL2() )
802: {
803: a1 = df1->StartLeg();
804: a2 = df2->StartLeg();
805: }
806: break;
807:
808: default:
809: break;
810: }
811:
812: // if EDITC (conflict) doesn't advance in the deleted leg
813: // then this isn't a conflict (fall back to edit).
814:
815: if( !extendConflict && d.mode == EDITC1 && !ab && !a2 )
816: d.diffs = DD_LEG1;
817:
818: if( !extendConflict && d.mode == EDITC2 && !ab && !a1 )
819: d.diffs = DD_LEG2;
820:
821: // INS12 (conflict) cannot advance base - bail
822:
823: if( noBaseAdvance && ab )
824: break;
825:
826: // No conflict extension - bail
827:
828: if( !ab && !a1 && !a2 )
829: break;
830:
831: // No longer a conflict - bail
832:
833: if( d.diffs != DD_CONF )
834: break;
835:
836: if( DEBUG_MERGE )
837: printf("MMMM %s/%s adjustment %+d,%+d,%+d\n",
838: ModeNames[ d.mode ], ModeNames[ n.mode ], ab, a1, a2 );
839:
840: bf->end += ab;
841: lf1->end += a1;
842: lf2->end += a2;
843:
844: extendConflict++;
845: }
846:
847: return d.diffs;
848: }
Privacy Policy