DAZipper.cpp #1

#include "DAZipper.h"

#include <clientapi.h>
#include "DAFile.h"
#include "DAInteg.h"
#include "DALine.h"
#include "DARev.h"
#include "DATooth.h"

struct DAFileStack
{
	DAFile* file;
	DAFileStack* next;
};

DAZipper::DAZipper( DAFile* f, int r )
: file( f ), rev( r )
{
	copy = 0x0;
	sources = 0x0;

	left = new DATooth( 0x0 );
	right = new DATooth( 0x0 );

	DARev* drev = file->getRev( rev );
	if ( !drev ) return;

	bool fileFound;
	DAFileStack* newFile;

	DAInteg* integ = 0x0;
	for ( int i = 0 ; i < drev->integCount() ; i++ )
	{
		integ = drev->getInteg( i );

		if ( !integ->getFile() ) continue;

		if (	integ->getHow() == DAInteg::Branch ||
				integ->getHow() == DAInteg::Copy		)
		{
			copy = integ;
			continue;
		}

		fileFound = false;
		for ( DAFileStack* s = sources ; s ; s = s->next )
		{
			if ( s->file == integ->getFile() )
				fileFound = true;
		}
		if ( fileFound )
			continue;

		newFile = new DAFileStack;
		newFile->file = integ->getFile();
		newFile->next = sources;
		sources = newFile;
	}
}

DAZipper::~DAZipper(void)
{
	DAFileStack* s;
	while ( sources )
	{
		s = sources;
		sources = s->next;
		delete s;
	}

	while ( left->nextTooth() != left )
	{
		delete left->nextTooth();
	}
	delete left;
	while ( right->nextTooth() != right )
	{
		delete right->nextTooth();
	}
	delete right;
}

void DAZipper::Zip()
{
	// Copies are easy.  Handle those first.
	if ( copy ) ZipCopy();

	// Now build the actual "zipper" halves.
	for ( DAFileStack* s = sources ; s ; s = s->next )
	{
		buildLeftZipper( s->file );
	}
	if ( left->nextTooth() != left )
		buildRightZipper();

	// Try context matching.
	matchByContext();

	// Cut out any remaining teeth that can't possibly match anything.
	eliminateUniques();

	// Try order matching.
	matchByDistance();

	// Eliminate anything that's left.
	eliminateAll();
}

void DAZipper::ZipCopy()
{
	if ( !copy->getFile() ) return;

	// A "copy" record implies that this revision is
	// a perfect copy of the from revision, with maybe
	// the occasional ktext anomaly.  As such, we ought
	// to be able to match lines in the source and target
	// to each other one-for-one.
	DALine* src = copy->getFile()->zeroLine()->nextAsOf( copy->getERev() );
	DALine* tgt = file->zeroLine()->nextAsOf( rev );

	while ( src->text() && tgt->text() )
	{
		if (	!tgt->zipped() && 
				tgt->lowerRev() == rev &&
				src->text() == tgt->text()	)
		{
			tgt->setAncestor( src );
		}

		src = src->nextAsOf( copy->getERev() );
		tgt = tgt->nextAsOf( rev );
	}
}

void DAZipper::buildLeftZipper( DAFile* source )
{
	bool isRelevant;
	DAInteg* integ;
	int srev, erev;
	DARev* drev = file->getRev( rev );

	for ( DALine* line = source->zeroLine()->nextLine() ; 
			line->text() ; 
			line = line->nextLine() )
	{
		if ( line->getTooth() ) continue;

		isRelevant = false;
		for ( int i = 0 ; i < drev->integCount() ; i++ )
		{
			integ = drev->getInteg( i );

			if (	integ->getHow() == DAInteg::Branch ||
					integ->getHow() == DAInteg::Copy   ||
					integ->getHow() == DAInteg::Ignore	) continue;

			srev = integ->getSRev();
			erev = integ->getERev();
			if ( integ->getHow() == DAInteg::Add )
				srev = 1;

			if ( srev <= line->lowerRev() &&  //line added at or after srev
				 erev >= line->lowerRev() &&  //line added at or before erev
				 erev <= line->upperRev() )   //line not removed before erev
			{
				isRelevant = true;
				break;
			}
		}

		if ( isRelevant )
		{
			left->prependTooth( new DATooth( line ) );
		}
	}
}

void DAZipper::buildRightZipper()
{
	for ( DALine* line = file->zeroLine()->nextLine() ;
			line->text() ;
			line = line->nextLine() )
	{
		if ( line->lowerRev() != rev ) continue;
		if ( line->zipped() ) continue;

		right->prependTooth( new DATooth( line ) );
	}
}


void DAZipper::eliminateAll()
{
	while ( left->nextTooth()->getLine() )
	{
		delete left->nextTooth();
	}
	while ( right->nextTooth()->getLine() )
	{
		right->nextTooth()->getLine()->setAncestor
			( right->nextTooth()->getLine() );
		delete right->nextTooth();
	}
}

void DAZipper::eliminateUniques()
{
	DATooth *s, *t;
	DATooth* unique = 0x0;
	bool hasMatch;
	for ( s = left->nextTooth() ; s->getLine() ; s = s->nextTooth() )
	{
		delete unique;
		unique = 0x0;

		hasMatch = false;
		for ( t = right->nextTooth() ; t->getLine() ; t = t->nextTooth() )
		{
			if ( s->getLine()->text() == t->getLine()->text() )
			{
				hasMatch = true;
				break;
			}
		}

		if ( !hasMatch ) unique = s;
	}
	delete unique;
	unique = 0x0;

	for ( s = right->nextTooth() ; s->getLine() ; s = s->nextTooth() )
	{
		delete unique;
		unique = 0x0;

		hasMatch = false;
		for ( t = left->nextTooth() ; t->getLine() ; t = t->nextTooth() )
		{
			if ( s->getLine()->text() == t->getLine()->text() )
			{
				hasMatch = true;
				break;
			}
		}

		if ( !hasMatch ) unique = s;
	}

	delete unique;
}

void DAZipper::matchByContext()
{
	DATooth* t = right->nextTooth();
	DALine* ancLine;
	DATooth* ancTooth;

	while ( t->getLine() )
	{
		ancLine = 0x0;
		ancTooth = 0x0;
		if ( ( (ancLine = t->getLine()->prevAsOf( rev )->ancestor()) &&
			   (ancTooth = ancLine->nextToothed()->getTooth()) &&
			   ancTooth->getLine()->text() == t->getLine()->text() ) ||
		     ( (ancLine = t->getLine()->nextAsOf( rev )->ancestor()) &&
			   (ancTooth = ancLine->prevToothed()->getTooth()) &&
			   ancTooth->getLine()->text() == t->getLine()->text() ) ) 
		{
			t->getLine()->setAncestor( ancTooth->getLine() );
			delete t;
			delete ancTooth;
			ancTooth = 0x0;
			t = right;
		}
		t = t->nextTooth();	 
	}
}

void DAZipper::matchByDistance()
{
	DATooth* l = left->nextTooth();
	DATooth* r = right->nextTooth();
	DATooth *lc, *rc;
	DATooth *lm, *rm;
	while ( l->getLine() && r->getLine() )
	{
		lc = r;
		rc = l;
		lm = rm = 0x0;
		while ( lc->getLine() || rc->getLine() )
		{
			if ( lc->getLine() )
			{
				if ( lc->getLine()->text() == l->getLine()->text() )
					break;
				else
					lc = lc->nextTooth();
			}
			if ( rc->getLine() )
			{
				if ( rc->getLine()->text() == r->getLine()->text() )
					break;
				else
					rc = rc->nextTooth();
			}
		}
		if ( lc->getLine() &&  l->getLine()->text() == lc->getLine()->text() )
		{
			lm = l;
			rm = lc;
		}
		if ( rc->getLine() && rc->getLine()->text() ==  r->getLine()->text() )
		{
			lm = rc;
			rm = r;
		}

		if ( lm && rm )
		{
			l = lm->nextTooth();
			r = rm->nextTooth();
			rm->getLine()->setAncestor( lm->getLine() );
			delete lm;
			delete rm;
		}
		else
		{
			l = l->nextTooth();
			r = r->nextTooth();
		}
	}
}