diffmerge.cc #1

/*
 * Copyright 1995, 2007 Perforce Software.  All rights reserved.
 *
 * This file is part of Perforce - the FAST SCM System.
 */

/*
 * diffmerge.cc - 3 way file merge
 *
 * Classes defined:
 *
 *	DiffMerge - control block for merging
 *
 * Public methods:
 *
 *	DiffMerge::DiffMerge() - Merge 3 files to produce integrated result
 *	DiffMerge::~DiffMerge() - dispose of DiffMerge and its contents
 *	DiffMerge::Read() - produce next part of integrated result
 *
 * Internal classes:
 *
 *	DiffFfile - line oriented ReadFile
 *	DiffDFile - a diff stream
 *
 * Private methods:
 *
 *	DiffDFile::DiffDFile() - start a diff(1) between the base and one leg
 *
 * History:
 *	2-18-97 (seiwald) - translated to C++.
 */

# define NEED_TYPES
# define NEED_FILE

# include <stdhdrs.h>

# include <error.h>
# include <debug.h>
# include <strbuf.h>
# include <filesys.h>

# include <readfile.h>

# include <diff.h>
# include <diffsp.h>
# include <diffan.h>
# include <diffmerge.h>

# define DEBUG_MERGE ( p4debug.GetLevel( DT_DIFF ) >= 3 )

/*
 * selbitTab - how to output each leg given the next pair of diffs
 *
 * DiffLeg represents the leg we're looking to output, and DiffDiffs
 * is how DiffDiff() said the next pair of diffs merged. 
 */

enum DiffLeg { DL_BASE, DL_LEG1, DL_LEG2, DL_LAST } ;

const int selbitTab[ DL_LAST ][ DD_LAST ] = {

/* BASE	at */ 	/* EOF */	0,		
		/* LEG1	*/	SEL_BASE|SEL_LEG2,	// base == leg2
		/* LEG2	*/	SEL_BASE|SEL_LEG1,	// base == leg1
		/* BOTH	*/	SEL_BASE,	
		/* CONF	*/	SEL_BASE|SEL_CONF,	
		/* ALL */	SEL_ALL,

/* LEG1	at */ 	/* EOF */	0,		
		/* LEG1	*/	SEL_LEG1|SEL_RSLT,
		/* LEG2	*/	0,			
		/* BOTH	*/	SEL_LEG1|SEL_LEG2|SEL_RSLT, // leg1 == leg2
		/* CONF	*/	SEL_LEG1|SEL_RSLT|SEL_CONF, // leg1 != leg2
		/* ALL */	0,

/* LEG2 at */ 	/* EOF */	0,
		/* LEG1	*/	0,
		/* LEG2	*/	SEL_LEG2|SEL_RSLT,
		/* BOTH	*/	0,			// == leg1
		/* CONF	*/	SEL_LEG2|SEL_RSLT|SEL_CONF, // leg1 != leg2
		/* ALL */	0,

};

/* 
 * MergeState - state for Read()'s state machine
 */

enum MergeState {
	MS_DIFFDIFF,	/* do diff diff */
	MS_BASE,	/* dumping the original */
	MS_LEG1,	/* dumping leg1 */
	MS_LEG2,	/* dumping leg2 */
	MS_DONE		/* return 0 */
} ;

/*
 * DiffDFile::DiffDFile() - popen(3) a diff(1) between the base and one leg
 */

inline LineNo dmin( LineNo a, LineNo b )  { return a < b ? a : b; }

/*
 * DiffFfile - line oriented ReadFile
 */

class DiffFfile : public Sequence { 

    public:
			DiffFfile( 
			    FileSys *file,
			    const DiffFlags &flags,
			    LineType lt,
			    Error *e ) 
			    : Sequence( file, flags, e )
			{ 
			    lineType = lt;
			    end = 0;
			}

    	LineLen  	MaxLineLength() const;

	LineType	lineType;

	/* Track our progress for output */

	LineNo		start;	/* first line to output */
	LineNo		end;	/* last line, and sync point */

} ;

/*
 * DiffDFile - a diff stream
 */

class DiffDFile : public DiffAnalyze {

    public:
			DiffDFile( DiffFfile *base, DiffFfile *leg )
			: DiffAnalyze( base, leg ) 
			{ 
				this->base = base;
				this->leg = leg;
				s = *GetSnake(); 
			}

	LineNo		StartLeg() { return s.y - leg->end; }
	LineNo		StartBase() { return s.x - base->end; }
	LineNo		EndLeg() { return s.v - leg->end; }
	LineNo		EndBase() { return s.u - base->end; }

	// alias the above for the leg1 leg2 snake ONLY

	LineNo		StartL1() { return StartBase(); }
	LineNo		StartL2() { return StartLeg(); }
	LineNo		EndL1() { return EndBase(); }
	LineNo		EndL2() { return EndLeg(); }

	void		AdvanceAndSync();

    public:

	Snake		s;		/* snake of differences */

    private:

	DiffFfile	*base;	/* for StartBase()/EndBase() */
	DiffFfile	*leg;	/* for StartLeg()/EndLeg() */

} ;

void
DiffDFile::AdvanceAndSync()
{
	// Advance

	while( s.next && ( EndLeg() <= 0 || EndBase() <= 0 ) ) 
	    s = *s.next;

	// Sync up to starting point

	LineNo adj = dmin( StartLeg(), StartBase() );
	if( adj < 0 ) { s.y += -adj; s.x += -adj; }
}

void
SnakeDump( const char *t, Snake *s )
{
	p4debug.printf( "snake %s\n", t );

	while( s )
	{
	    p4debug.printf("s %x %d %d %d %d\n", s, s->x, s->u, s->y, s->v );
	    s = s->next;
	}
}

/*
 * DiffMerge::DiffMerge() - Merge 3 files to produce integrated result
 */

DiffMerge::DiffMerge( 
	FileSys *base,
	FileSys *leg1,
	FileSys *leg2,
	const DiffFlags &flags,
	LineType lineType,
	Error *e )
{
	readFile = 0;
	emptyFile = 0;
	bf = lf1 = lf2 = 0;
	df1 = df2 = df3 = 0;
	
	switch( flags.grid )
	{
	case DiffFlags::Optimal:
	    gridType = GRT_OPTIMAL;
	    break;
	case DiffFlags::Guarded:
	    gridType = GRT_GUARDED;
	    break;
	case DiffFlags::TwoWay:
	    gridType = GRT_TWOWAY;
	    emptyFile = FileSys::Create( FST_EMPTY );
	    break;
	}

	state = MS_DIFFDIFF;

	if( DEBUG_MERGE )
	    p4debug.printf( "merging %s x %s x %s\n", base->Name(),
	        leg1->Name(), leg2->Name() );

	/*
	**  Open the three input files.
	*/

	bf = new DiffFfile( emptyFile ? emptyFile : base, flags, lineType, e );
	lf1 = new DiffFfile( leg1, flags, lineType, e );
	lf2 = new DiffFfile( leg2, flags, lineType, e );

	if( e->Test() )
	    return;

	/*
	**  Fork off the two diffs, between the base and l1, and between
	**  base and l2.  Prime the diff file structures by reading the
	**  first two diffs.
	*/

	df1 = new DiffDFile( bf, lf1 );
	df2 = new DiffDFile( bf, lf2 );
	df3 = new DiffDFile( lf1, lf2 );

	if( DEBUG_MERGE )
	{
	    SnakeDump( "df1", &df1->s );
	    SnakeDump( "df2", &df2->s );
	    SnakeDump( "df3", &df3->s );
	}
}

/*
 * DiffMerge::~DiffMerge() - dispose of DiffMerge and its contents
 */

DiffMerge::~DiffMerge()
{
	delete bf;
	delete lf1;
	delete lf2;

	delete df1;
	delete df2;
	delete df3;

	delete emptyFile;
}

/*
 * DiffMerge::Read() - produce next part of integrated result
 */

int
DiffMerge::Read( char *buf, int len, int *outlen )
{
	for(;;)
	{
	    /*
	     * If readFile is set, we're still returning output from
	     * one of the file legs.  Keep doing so until the user's
	     * buffer is satisfied, or we've output this chunk.
	     */

	    if( readFile )
	    {
		*outlen = readFile->CopyLines( 
		    readFile->start, 
		    readFile->end,
		    buf, len, 
		    readFile->lineType );

		if( !*outlen )
		    readFile = 0;

		return selbits;
	    }

	    switch( state )
	    {
	    case MS_DIFFDIFF:	

		/* do diff diff */

		if( ( diffDiff = DiffDiff() ) == DD_EOF )
		{
		    state = MS_DONE;
		    break;
		}

	        if( diffDiff != DD_ALL)
		{
		    *outlen = 0;
		    state = MS_BASE;
		    return SEL_ALL;
		}

	    case MS_BASE:		/* dumping the original */

		if( selbits = selbitTab[ DL_BASE ][ diffDiff ] )
		{
		    readFile = bf;
		    readFile->SeekLine( bf->start );
		    state = MS_LEG1;
		    break;
		}

	    case MS_LEG1:		/* dumping leg1 */

		if( selbits = selbitTab[ DL_LEG1 ][ diffDiff ] )
		{
		    readFile = lf1;
		    readFile->SeekLine( lf1->start );
		    state = MS_LEG2;
		    break;
		}

	    case MS_LEG2:		/* dumping leg2 */

		if( selbits = selbitTab[ DL_LEG2 ][ diffDiff ] )
		{
		    readFile = lf2;
		    readFile->SeekLine( lf2->start );
		}

		state = MS_DIFFDIFF;
		break;

	    case MS_DONE:		/* return 0 */

		*outlen = 0;
		return 0;
	    }
	}
}

/*
 * DiffMerge::BitNames() - turn out mnemonic(?) names for the flags
 */

const char *
DiffMerge::BitNames( int bits )
{
	switch( bits )
	{
	case SEL_ALL:			return "ALL";
	case SEL_BASE:			return "BASE";
	case SEL_BASE|SEL_CONF:		return "BASE CONFLICT";
	case SEL_BASE|SEL_LEG1:		return "BASE L1";
	case SEL_BASE|SEL_LEG2:		return "BASE L2";
	case SEL_LEG1|SEL_RSLT|SEL_CONF:return "L1 CONFLICT";
	case SEL_LEG2|SEL_RSLT|SEL_CONF:return "L2 CONFLICT";
	case SEL_LEG1|SEL_RSLT:		return "L1";
	case SEL_LEG2|SEL_RSLT:		return "L2";
	case SEL_LEG1|SEL_LEG2|SEL_RSLT:return "L1 L2";
	default:			return "?";
	}
}

/*
 * DiffMerge::MaxLineLength() - find the maximum length of a line in any file
 */

LineLen 
DiffMerge::MaxLineLength() const
{
	LineLen l, m = bf->MaxLineLength();

	if( ( l = lf1->MaxLineLength() ) > m ) m = l;
	if( ( l = lf2->MaxLineLength() ) > m ) m = l;

	return m;
}

/*
 * DiffFfile::MaxLineLength() - find the maximum length of a line
 */

LineLen 
DiffFfile::MaxLineLength() const
{
	LineLen m = 0;

	for( LineNo l = 0; l < Lines(); l++ )
	    if( m < Length( l ) )
		 m = Length( l );

	return  m;
}

enum Mode {
	ALL, ALL1, ALL2, 
	BOTH, BOTHX, 
	BOTHX1, BOTHX2, CONF,
	DEL1, DEL2,
	DELB, DELB1, DELB2,
	EDIT1, EDIT2,
	EDITC1, EDITC2,
	INSX1, INSX2,
	INSY1, INSY2,
	INS12, INSX12, INSY12,
	INS1, INS2, 
	INSC1, INSC2, 
	INSC3, INSC4,
	INSC5, INSC6,
	INSC7, INSC8,
	NONE
} ;

const char *ModeNames[] = {
	"ALL", "ALL1", "ALL2", 
	"BOTH", "BOTHX", 
	"BOTHX1", "BOTHX2", "CONF",
	"DEL1", "DEL2", 
	"DELB", "DELB1", "DELB2", 
	"EDIT1", "EDIT2",
	"EDITC1", "EDITC2",
	"INSX1", "INSX2",
	"INSY1", "INSY2",
	"INS12", "INSX12", "INSY12",
	"INS1", "INS2", 
	"INSC1", "INSC2", 
	"INSC3", "INSC4",
	"INSC5", "INSC6",
	"INSC7", "INSC8",
	"NONE"
} ;

struct DiffGrid {

	Mode		mode;
	DiffDiffs	diffs;

} ;

const DiffGrid twoWayGrid[2][2][2][2][2][2] = {

//    ---- BASE/LEG1         ---- BASE/LEG2         ---- LEG1/LEG2
//    ||                     ||                     ||
//    __   __   __      __   __   _X      __   __   X_      __   __   XX  
//    __   _X   __      __   _X   _X      __   _X   X_      __   _X   XX  
//    __   X_   __      __   X_   _X      __   X_   X_      __   X_   XX  
//    __   XX   __      __   XX   _X      __   XX   X_      __   XX   XX  

      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,

//    _X   __   __      _X   __   _X      _X   __   X_      _X   __   XX  
//    _X   _X   __      _X   _X   _X      _X   _X   X_      _X   _X   XX  
//    _X   X_   __      _X   X_   _X      _X   X_   X_      _X   X_   XX  
//    _X   XX   __      _X   XX   _X      _X   XX   X_      _X   XX   XX  

      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,

//    X_   __   __      X_   __   _X      X_   __   X_      X_   __   XX  
//    X_   _X   __      X_   _X   _X      X_   _X   X_      X_   _X   XX  
//    X_   X_   __      X_   X_   _X      X_   X_   X_      X_   X_   XX  
//    X_   XX   __      X_   XX   _X      X_   XX   X_      X_   XX   XX  

      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,

//    XX   __   __      XX   __   _X      XX   __   X_      XX   __   XX  
//    XX   _X   __      XX   _X   _X      XX   _X   X_      XX   _X   XX  
//    XX   X_   __      XX   X_   _X      XX   X_   X_      XX   X_   XX  
//    XX   XX   __      XX   XX   _X      XX   XX   X_      XX   XX   XX  

      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     CONF,DD_CONF,     BOTH,DD_BOTH
} ;

const DiffGrid optimalGrid[2][2][2][2][2][2] = {

//    ---- BASE/LEG1         ---- BASE/LEG2         ---- LEG1/LEG2
//    ||                     ||                     ||
//    __   __   __      __   __   _X      __   __   X_      __   __   XX  
//    __   _X   __      __   _X   _X      __   _X   X_      __   _X   XX  
//    __   X_   __      __   X_   _X      __   X_   X_      __   X_   XX  
//    __   XX   __      __   XX   _X      __   XX   X_      __   XX   XX  

      CONF,DD_CONF,     INSX1,DD_LEG1,    INSX2,DD_LEG2,    BOTHX,DD_BOTH,
      CONF,DD_CONF,     INSC6,DD_CONF,    INSX2,DD_LEG2,    BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     DELB,DD_BOTH,     DELB,DD_BOTH,
      EDITC1,DD_CONF,   EDIT1,DD_LEG1,    EDIT1,DD_LEG1,    ALL2,DD_ALL,

//    _X   __   __      _X   __   _X      _X   __   X_      _X   __   XX  
//    _X   _X   __      _X   _X   _X      _X   _X   X_      _X   _X   XX  
//    _X   X_   __      _X   X_   _X      _X   X_   X_      _X   X_   XX  
//    _X   XX   __      _X   XX   _X      _X   XX   X_      _X   XX   XX  

      CONF,DD_CONF,     INSX1,DD_LEG1,    INSC5,DD_CONF,    BOTH,DD_BOTH,
      INS12,DD_CONF,    INSX12,DD_CONF,   INSY12,DD_CONF,   BOTH,DD_BOTH,
      CONF,DD_CONF,     CONF,DD_CONF,     INSC3,DD_CONF,    INSC3,DD_CONF,
      INSX1,DD_LEG1,    INSX1,DD_LEG1,    INSC1,DD_CONF,    ALL2,DD_ALL,

//    X_   __   __      X_   __   _X      X_   __   X_      X_   __   XX  
//    X_   _X   __      X_   _X   _X      X_   _X   X_      X_   _X   XX  
//    X_   X_   __      X_   X_   _X      X_   X_   X_      X_   X_   XX  
//    X_   XX   __      X_   XX   _X      X_   XX   X_      X_   XX   XX  

      CONF,DD_CONF,     DELB,DD_BOTH,     CONF,DD_CONF,     DELB,DD_BOTH,
      CONF,DD_CONF,     INSC4,DD_CONF,    CONF,DD_CONF,     INSC4,DD_CONF,
      DELB,DD_BOTH,     DELB,DD_BOTH,     DELB,DD_BOTH,     DELB,DD_BOTH,
      DEL1,DD_LEG1,     DEL1,DD_LEG1,     INSC8,DD_CONF,    ALL2,DD_ALL,

//    XX   __   __      XX   __   _X      XX   __   X_      XX   __   XX  
//    XX   _X   __      XX   _X   _X      XX   _X   X_      XX   _X   XX  
//    XX   X_   __      XX   X_   _X      XX   X_   X_      XX   X_   XX  
//    XX   XX   __      XX   XX   _X      XX   XX   X_      XX   XX   XX  

      EDITC2,DD_CONF,   EDIT2,DD_LEG2,    EDIT2,DD_LEG2,    ALL1,DD_ALL,
      INSX2,DD_LEG2,    INSC2,DD_CONF,    INSX2,DD_LEG2,    ALL1,DD_ALL,
      DEL2,DD_LEG2,     INSC7,DD_CONF,    DEL2,DD_LEG2,     ALL1,DD_ALL,
      ALL,DD_ALL,       ALL,DD_ALL,       ALL,DD_ALL,       ALL,DD_ALL
} ;

const DiffGrid conservativeGrid[2][2][2][2][2][2] = {

//    ---- BASE/LEG1         ---- BASE/LEG2         ---- LEG1/LEG2
//    ||                     ||                     ||
//    __   __   __      __   __   _X      __   __   X_      __   __   XX  
//    __   _X   __      __   _X   _X      __   _X   X_      __   _X   XX  
//    __   X_   __      __   X_   _X      __   X_   X_      __   X_   XX  
//    __   XX   __      __   XX   _X      __   XX   X_      __   XX   XX  

      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     BOTHX,DD_CONF,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     BOTH,DD_CONF,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,

//    _X   __   __      _X   __   _X      _X   __   X_      _X   __   XX  
//    _X   _X   __      _X   _X   _X      _X   _X   X_      _X   _X   XX  
//    _X   X_   __      _X   X_   _X      _X   X_   X_      _X   X_   XX  
//    _X   XX   __      _X   XX   _X      _X   XX   X_      _X   XX   XX  

      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     BOTH,DD_CONF,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     BOTH,DD_CONF,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     BOTHX1,DD_CONF,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,

//    X_   __   __      X_   __   _X      X_   __   X_      X_   __   XX  
//    X_   _X   __      X_   _X   _X      X_   _X   X_      X_   _X   XX  
//    X_   X_   __      X_   X_   _X      X_   X_   X_      X_   X_   XX  
//    X_   XX   __      X_   XX   _X      X_   XX   X_      X_   XX   XX  

      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     BOTHX2,DD_CONF,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,

//    XX   __   __      XX   __   _X      XX   __   X_      XX   __   XX  
//    XX   _X   __      XX   _X   _X      XX   _X   X_      XX   _X   XX  
//    XX   X_   __      XX   X_   _X      XX   X_   X_      XX   X_   XX  
//    XX   XX   __      XX   XX   _X      XX   XX   X_      XX   XX   XX  

      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,
      NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL,     NONE, DD_ALL
} ;

DiffDiffs
DiffMerge::DiffDiff()
{
	/* All legs completely output? */

	if( bf->end == bf->Lines() &&
	    lf1->end == lf1->Lines() &&
	    lf2->end == lf2->Lines() )
		return( DD_EOF );

	/* Advance to next snake, if past old one. */

	df1->AdvanceAndSync();
	df2->AdvanceAndSync();
	df3->AdvanceAndSync();

	LineNo lb = 0, l1 = 0, l2 = 0;

	DiffGrid d;
	d.mode = NONE;

	// '-dg' (guarded) flag informs merge to use the conservative grid,
	// if no mode is returned then fallback to the optimal grid.

	// '-dt' (twoway) flag informs merge to use the twoway grid,

	if( gridType == GRT_TWOWAY ) d = twoWayGrid
		[ df1->StartLeg() == 0 ][ df1->StartBase() == 0 ]
		[ df2->StartLeg() == 0 ][ df2->StartBase() == 0 ]
		[ df3->StartL1() == 0 ][ df3->StartL2() == 0 ];

	if( gridType == GRT_GUARDED ) d = conservativeGrid
		[ df1->StartLeg() == 0 ][ df1->StartBase() == 0 ]
		[ df2->StartLeg() == 0 ][ df2->StartBase() == 0 ]
		[ df3->StartL1() == 0 ][ df3->StartL2() == 0 ];
	
	if( d.mode == NONE ) d = optimalGrid
		[ df1->StartLeg() == 0 ][ df1->StartBase() == 0 ]
		[ df2->StartLeg() == 0 ][ df2->StartBase() == 0 ]
		[ df3->StartL1() == 0 ][ df3->StartL2() == 0 ];

	Mode initialMode = d.mode;

	// Pre-process rules,  typically the outer snake information
	// contradicts the inner snake, its not perfect, but we use
	// the length of the snake to determine the best outcome.

	// Advance files

	switch( d.mode )
	{
	case INSC1:
	    if( df3->EndL1() > df2->EndBase() )   // trust outer - insert L2
	    { d.mode = INSY2; d.diffs = DD_LEG2; break; }

	    d.mode = INS1; d.diffs = DD_LEG1;     // trust inner - insert L1
	    break;

	case INSC2:
	    if( df3->EndL2() > df1->EndBase() )   // trust outer - insert L2
	    { d.mode = INSY1; d.diffs = DD_LEG1; break; }

	    d.mode = INS2; d.diffs = DD_LEG2;     // trust inner = insert L1
	    break;

	case INSC3:
	    if( df3->EndL1() >= df1->EndLeg() )   // trust outer - delete base
	    { d.mode = DELB1; d.diffs = DD_BOTH; break; }

	    d.mode = INS1; d.diffs = DD_LEG1;     // trust inner - insert L1
	    break;

	case INSC4:
	    if( df3->EndL2() >= df2->EndLeg() )   // trust outer - delete base
	    { d.mode = DELB2; d.diffs = DD_BOTH; break; }

	    d.mode = INS2; d.diffs = DD_LEG2;     // trust inner - insert L2
	    break;

	case INSC5:
	    if( df3->EndL1() >= df1->EndLeg() )   // trust outer - delete base
	    { d.mode = DELB1; d.diffs = DD_BOTH; break; }

	    if( df3->EndL1() >= df1->EndBase() )  // trust outer - insert L2
	    { d.mode = INSX2; d.diffs = DD_LEG2; break; }

	    d.mode = INS1; d.diffs = DD_LEG1;     // trust inner - insert L1
	    break;

	case INSC6:
	    if( df3->EndL2() >= df2->EndLeg() )   // trust outer - delete base
	    { d.mode = DELB2; d.diffs = DD_BOTH; break; }

	    if( df3->EndL2() >= df2->EndBase() )  // trust outer - insert L1
	    { d.mode = INSX1; d.diffs = DD_LEG1; break; }

	    d.mode = INS2; d.diffs = DD_LEG2;     // trust inner - insert L2
	    break;

	case INSC7:
	   if( df1->EndBase() > df2->StartBase() ||   // overlap in delete
	       df2->EndBase() == df2->StartBase() )   // eof detection
	   { d.mode = DEL2; d.diffs = DD_LEG2; }
	   break;

	case INSC8:
	   if( df2->EndBase() > df1->StartBase() ||   // overlap in delete
	       df1->EndBase() == df1->StartBase() )   // eof detection
	   { d.mode = DEL1; d.diffs = DD_LEG1; }
	   break;

	case INSX12:
	    if( df3->StartL1() < df1->StartLeg() &&
	        df3->EndL1() >= df1->StartLeg() &&
	        df3->EndL2() >= df2->StartLeg() ) // trust outer - insert L1
	    { d.mode = INSY1; d.diffs = DD_LEG1; }
	    break;

	case INSY12:
	    if( df3->StartL2() < df2->StartLeg() &&
	        df3->EndL2() >= df2->StartLeg() &&
	        df3->EndL1() >= df1->StartLeg() ) // trust outer - insert L2
	    { d.mode = INSY2; d.diffs = DD_LEG2; }
	    break;
	}

	switch( d.mode )
	{
	case ALL1:
	    lb = l1 = l2 = dmin( df1->EndBase(), df3->EndL1() );
	    break;

	case ALL2:
	    lb = l1 = l2 = dmin( df2->EndBase(), df3->EndL2() );
	    break;

	case ALL:
	    lb = l1 = l2 = dmin( df1->EndBase(), df2->EndBase() );
	    break;

	case BOTH:
	    lb = dmin( df1->StartBase(), df2->StartBase() );
	    l1 = dmin( df1->StartLeg(), df3->EndL1() );
	    l2 = dmin( df2->StartLeg(), df3->EndL2() );
	    l1 = l2 = dmin( l1, l2 );
	    break;

	case BOTHX:
	    lb = dmin( df1->StartBase(), df2->StartBase() );
	    l1 = dmin( df1->StartLeg(), df3->EndL1() );
	    l2 = dmin( df2->StartLeg(), df3->EndL2() );
	    l1 = l2 = dmin( l1, l2 );
	    lb = dmin( lb, l1 );
	    d.mode = BOTH;
	    break;

	case BOTHX1:
	    l1 = l2 = dmin( df1->StartLeg(), df3->EndL1() );
	    d.mode = BOTH;
	    break;

	case BOTHX2:
	    l1 = l2 = dmin( df2->StartLeg(), df3->EndL2() );
	    d.mode = BOTH;
	    break;

	case DELB:
	    lb = dmin( df1->StartBase(), df2->StartBase() );
	    break;

	case DELB1:
	    lb = df1->EndBase();
	    break;

	case DELB2:
	    lb = df2->EndBase();
	    break;

	case DEL1:
	    lb = l2 = dmin( df1->StartBase(), df2->EndBase() );
	    break;

	case DEL2:
	    lb = l1 = dmin( df2->StartBase(), df1->EndBase() );
	    break;

	case EDIT1:
	case EDITC1:
	    l1 = dmin( df1->StartLeg(), df3->StartL1() );
	    lb = l2 = dmin( df1->StartBase(), df2->EndBase() );
	    break;

	case EDIT2:
	case EDITC2:
	    l2 = dmin( df2->StartLeg(), df3->StartL2() );
	    lb = l1 = dmin( df1->EndBase(), df2->StartBase() );
	    break;

	case INSX1:
	    l1 = dmin( df1->StartLeg(), df3->StartL1() );
	    break;

	case INSX2:
	    l2 = dmin( df2->StartLeg(), df3->StartL2() );
	    break;

	case INSY1:
	    l1 = df3->StartL1();
	    break;

	case INSY2:
	    l2 = df3->StartL2();
	    break;

	case INS1:
	    l1 = df1->StartLeg();
	    break;

	case INS2:
	    l2 = df2->StartLeg();
	    break;

	case INSX12:
	    l1 = dmin( df1->StartLeg(), df3->StartL1() );
	    l2 = df2->StartLeg();
	    break;

	case INSY12:
	    l1 = df1->StartLeg();
	    l2 = dmin( df2->StartLeg(), df3->StartL2() );
	    break;

	case CONF:
	    lb = dmin( df1->StartBase(), df2->StartBase() );
	    // fall through

	case INS12:
	    l1 = dmin( df1->StartLeg(), df3->StartL1() );
	    l2 = dmin( df2->StartLeg(), df3->StartL2() );
	    break;
	}

	if( DEBUG_MERGE )
	{
	    p4debug.printf("\nMMMM df1(%d,%d)B(%d,%d)L df2(%d,%d)B(%d,%d)L ",
	        df1->StartBase(),df1->EndBase(),df1->StartLeg(),df1->EndLeg(),
	        df2->StartBase(),df2->EndBase(),df2->StartLeg(),df2->EndLeg());

	    p4debug.printf("df3(%d,%d)L1(%d,%d)L2 [%c%c %c%c %c%c]\n",
	        df3->StartL1(),df3->EndL1(),df3->StartL2(),df3->EndL2(),
	        df1->StartLeg() == 0 ? 'X' : '_', 
	        df1->StartBase() == 0 ? 'X' : '_',
	        df2->StartLeg() == 0 ? 'X' : '_',
	        df2->StartBase() == 0 ? 'X' : '_',
	        df3->StartL1() == 0 ? 'X' : '_', 
	        df3->StartL2() == 0 ? 'X' : '_');

	    p4debug.printf("MMMM %s%s%s advancing %+d,%+d,%+d\n", 
	        ModeNames[ initialMode ], 
	        d.mode != initialMode ? " -> " : "",
	        d.mode != initialMode ? ModeNames[ d.mode ] : "",
	        lb, l1, l2 );
	}

	/* Set output range (start/end).  End is new sync point. */

	bf->start = bf->end;
	lf1->start = lf1->end;
	lf2->start = lf2->end;

	bf->end += lb;
	lf1->end += l1;
	lf2->end += l2;

	/* If an action may be downgraded from a conflict (currently only
	 * EDITC1 and EDITC2 fit that category), make sure they actually get
	 * through the processing or downgrade it now.
	 *
	 * 2007.2  Added BOTH (guarded mode)
	 */

	if( bf->end == bf->Lines() &&
	    lf1->end == lf1->Lines() &&
	    lf2->end == lf2->Lines() )
	{
	    if( d.mode == EDITC1 ) d.diffs = DD_LEG1; 
	    if( d.mode == EDITC2 ) d.diffs = DD_LEG2; 
	    if( d.mode == BOTH ) d.diffs = DD_BOTH; 
	}

	/* Handle Conflicts (post processing) 
	 * 
	 * Sometimes it is necessary to extend the conflict area to produce
	 * the best conflict.  Advance all snakes to the conflict end region 
	 * and see what happens next.  Depending  on the result,  we may grow 
	 * the conflict several times before returning.
	 *
	 * 2007.2 added the guarded flag (-dg) which uses the conservative 
	 * grid to change the action of "BOTH" processing.  Note that during
	 * conflict extension only (-dg) processed files will see "BOTH" as
	 * the conflict mode.
	 */

	DiffGrid n;
	int extendConflict = 0;

	while( d.diffs == DD_CONF && ( bf->end != bf->Lines() || 
	                               lf1->end != lf1->Lines() || 
	                               lf2->end != lf2->Lines() ) )
	{
	    LineNo ab = 0, a1 = 0, a2 = 0;

	    // Conflict caused by inserting on L1 and L2 can never extend
	    // the base.

	    int noBaseAdvance = ( d.mode == INS12 
	                       || d.mode == INSX12 
	                       || d.mode == INSY12 );

	    df1->AdvanceAndSync();
	    df2->AdvanceAndSync();
	    df3->AdvanceAndSync();

	    n = optimalGrid
	        [ df1->StartLeg() == 0 ][ df1->StartBase() == 0 ]
		[ df2->StartLeg() == 0 ][ df2->StartBase() == 0 ]
		[ gridType == GRT_GUARDED && df3->StartL1() == 0 
	                                  && df3->StartL2() == 0 ]
		[ gridType == GRT_GUARDED && df3->StartL1() == 0 
	                                  && df3->StartL2() == 0 ];
	
	    switch( n.mode )
	    {
	    case INSX1: 
	        if( d.mode == INSC7 && extendConflict < 2 )
	        { d.diffs = DD_LEG2; break; }
	    case INS1:
	        a1 = df1->StartLeg();
	        break;
	    case INSX2: 
	        if( d.mode == INSC8 && extendConflict < 2 )
	        { d.diffs = DD_LEG1; break; }
	    case INS2:
	        a2 = df2->StartLeg();
	        break;
	    case DEL1:
	        ab = a2 = dmin( df1->StartBase(), df2->EndBase() );
	        break;
	    case DEL2: 
	        ab = a1 = dmin( df2->StartBase(), df1->EndBase() );
	        break;
	    case DELB:
	        // Prior to adding EDITC1 and EDITC2,  DELB would not 
	        // extend the conflict area, lets keep it that way.
	        // Added INSC7 and INSC8 for 2010.2.
	        if( d.mode != EDITC1 && d.mode != EDITC2 && 
	            d.mode != INSC7  && d.mode != INSC8 )
	            break;
	    case INSC3:
	    case INSC4:
	    case CONF:
	        ab = dmin( df1->StartBase(), df2->StartBase() );
	    case INS12:
	        if( d.mode == BOTH )
	        { 
	            a1 = df1->StartLeg(); 
	            a2 = df2->StartLeg(); 
	            break;
	        }

	        if( !noBaseAdvance )
	        {
	            a1 = dmin( df1->StartLeg(), df3->StartL1() );
	            a2 = dmin( df2->StartLeg(), df3->StartL2() );
	            break;
	        }

	        // INS12,INSX12,INSY12 (conflict) made a bad decision and 
	        // went with an outer snake,  since we are still in the 
	        // inner snake/ make up for that now by advancing to 
	        // inner startlegs.

	        if( df1->StartLeg() > df3->EndL1() &&
	            df2->StartLeg() > df3->EndL2() )
	        { 
	            a1 = df1->StartLeg(); 
	            a2 = df2->StartLeg(); 
	        }
	        break;
	    case EDITC1:
	        if( gridType == GRT_GUARDED ) 
	        {
	            a1 = dmin( df1->StartLeg(), df3->StartL1() );
	            ab = a2 = dmin( df1->StartBase(), df2->EndBase() );
	        }
	        break;
	    case EDITC2:
	        if( gridType == GRT_GUARDED )
	        {
	            a2 = dmin( df2->StartLeg(), df3->StartL2() );
	            ab = a1 = dmin( df1->EndBase(), df2->StartBase() );
	        }
	        break;
	    case BOTH:
	        a1 = dmin( df1->StartLeg(), df3->EndL1() );
	        a2 = dmin( df2->StartLeg(), df3->EndL2() );
	        break;

	    default:
	        break;
	    }

	    // if EDITC (conflict)  doesn't advance in the deleted leg
	    // then this isn't a conflict (fall back to edit).  
	    // if BOTH (conflict)  doesn't advance then fall back to both.

	    if( !extendConflict )
	    {
	        switch( d.mode )
	        {
	        case EDITC1:  if( !ab && !a2) d.diffs = DD_LEG1;
	                      break;
	        case EDITC2:  if( !ab && !a1) d.diffs = DD_LEG2;
	                      break;
	        case BOTH:    if( !ab && !a1 && !a2 ) d.diffs = DD_BOTH;
	                      break;
	        }
	    }

	    // INS12 (conflict) cannot advance base - bail
	    
	    if( noBaseAdvance && ab ) 
	        break;

	    // No conflict extension  - bail

	    if( !ab && !a1 && !a2 )
	        break;

	    // No longer a conflict - bail

	    if( d.diffs != DD_CONF )
	        break;

	    if( DEBUG_MERGE )
	        p4debug.printf("MMMM %s/%s adjustment %+d,%+d,%+d\n",
	            ModeNames[ d.mode ], ModeNames[ n.mode ], ab, a1, a2 );

	    bf->end += ab;
	    lf1->end += a1;
	    lf2->end += a2;

	    extendConflict++;
	}

	return d.diffs;
}