Fossil SCM

Additional alignment debugging information output for "fossil diff --debug".

drh 2022-01-23 11:29 diff-improvement

Commit 9aaefcfd0a8746b63bad3b832ff70b396130c4b705fb2c093d3315e88146b09b

Parent c311efef078c873…

1 file changed +21 -1

M src/diff.c

+21 -1

		--- src/diff.c
		+++ src/diff.c
		@@ -1822,11 +1822,11 @@
1822	1822	int limit = minInt(nA-i, nB-j);
1823	1823	for(k=best; k<=limit && zA[k+i]==zB[k+j]; k++){}
1824	1824	if( k>best ) best = k;
1825	1825	}
1826	1826	}
1827		- score = (best>=avg) ? 0 : (avg - best)*100/avg;
	1827	+ score = 5 + ((best>=avg) ? 0 : (avg - best)*95/avg);
1828	1828
1829	1829	#if 0
1830	1830	fprintf(stderr, "A: [%.s]\nB: [%.s]\nbest=%d avg=%d score=%d\n",
1831	1831	nA, zA+1, nB, zB+1, best, avg, score);
1832	1832	#endif
		@@ -1937,10 +1937,18 @@
1937	1937	diffDLineXfer(dc.aTo, aRight, nRight);
1938	1938	longestCommonSequence(&dc,0,nLeft,0,nRight,&iSX,&iEX,&iSY,&iEY);
1939	1939	fossil_free(dc.aFrom);
1940	1940	nLCS = iEX - iSX;
1941	1941	if( nLCS<5 ) return 0; /* No good LCS was found */
	1942	+
	1943	+ if( pCfg->diffFlags & DIFF_DEBUG ){
	1944	+ fossil_print(" LCS size=%d\n"
	1945	+ " [%.*s]\n"
	1946	+ " [%.*s]\n",
	1947	+ nLCS, aLeft[iSX].n, aLeft[iSX].z,
	1948	+ aLeft[iEX-1].n, aLeft[iEX-1].z);
	1949	+ }
1942	1950
1943	1951	a1 = diffBlockAlignment(aLeft,iSX,aRight,iSY,pCfg,&n1);
1944	1952	a2 = diffBlockAlignment(aLeft+iEX, nLeft-iEX,
1945	1953	aRight+iEY, nRight-iEY,
1946	1954	pCfg, &n2);
		@@ -1987,10 +1995,16 @@
1987	1995	aBig = aRight;
1988	1996	nBig = nRight;
1989	1997	}
1990	1998	iDivBig = nBig/2;
1991	1999	iDivSmall = nSmall/2;
	2000	+
	2001	+ if( pCfg->diffFlags & DIFF_DEBUG ){
	2002	+ fossil_print(" Divide at [%.*s]\n",
	2003	+ aBig[iDivBig].n, aBig[iDivBig].z);
	2004	+ }
	2005	+
1992	2006	bestScore = 10000;
1993	2007	for(i=0; i<nSmall; i++){
1994	2008	score = match_dline(aBig+iDivBig, aSmall+i) + abs(i-nSmall/2)*2;
1995	2009	if( score<bestScore ){
1996	2010	bestScore = score;
		@@ -2070,10 +2084,16 @@
2070	2084	aM = fossil_malloc( nLeft + 2 );
2071	2085	memset(aM, 1, nLeft);
2072	2086	*pNResult = nLeft;
2073	2087	return aM;
2074	2088	}
	2089	+
	2090	+ if( pCfg->diffFlags & DIFF_DEBUG ){
	2091	+ fossil_print("BlockAlignment:\n [%.s] + %d\n [%.s] + %d\n",
	2092	+ aLeft[0].n, aLeft[0].z, nLeft,
	2093	+ aRight[0].n, aRight[0].z, nRight);
	2094	+ }
2075	2095
2076	2096	/* For large alignments, try to use alternative algorithms that are
2077	2097	** faster than the O(N*N) Wagner edit distance.
2078	2098	*/
2079	2099	if( nLeft*nRight>DIFF_ALIGN_MX && (pCfg->diffFlags & DIFF_SLOW_SBS)==0 ){
2080	2100

	--- src/diff.c
	+++ src/diff.c
	@@ -1822,11 +1822,11 @@
1822	int limit = minInt(nA-i, nB-j);
1823	for(k=best; k<=limit && zA[k+i]==zB[k+j]; k++){}
1824	if( k>best ) best = k;
1825	}
1826	}
1827	score = (best>=avg) ? 0 : (avg - best)*100/avg;
1828
1829	#if 0
1830	fprintf(stderr, "A: [%.s]\nB: [%.s]\nbest=%d avg=%d score=%d\n",
1831	nA, zA+1, nB, zB+1, best, avg, score);
1832	#endif
	@@ -1937,10 +1937,18 @@
1937	diffDLineXfer(dc.aTo, aRight, nRight);
1938	longestCommonSequence(&dc,0,nLeft,0,nRight,&iSX,&iEX,&iSY,&iEY);
1939	fossil_free(dc.aFrom);
1940	nLCS = iEX - iSX;
1941	if( nLCS<5 ) return 0; /* No good LCS was found */








1942
1943	a1 = diffBlockAlignment(aLeft,iSX,aRight,iSY,pCfg,&n1);
1944	a2 = diffBlockAlignment(aLeft+iEX, nLeft-iEX,
1945	aRight+iEY, nRight-iEY,
1946	pCfg, &n2);
	@@ -1987,10 +1995,16 @@
1987	aBig = aRight;
1988	nBig = nRight;
1989	}
1990	iDivBig = nBig/2;
1991	iDivSmall = nSmall/2;






1992	bestScore = 10000;
1993	for(i=0; i<nSmall; i++){
1994	score = match_dline(aBig+iDivBig, aSmall+i) + abs(i-nSmall/2)*2;
1995	if( score<bestScore ){
1996	bestScore = score;
	@@ -2070,10 +2084,16 @@
2070	aM = fossil_malloc( nLeft + 2 );
2071	memset(aM, 1, nLeft);
2072	*pNResult = nLeft;
2073	return aM;
2074	}






2075
2076	/* For large alignments, try to use alternative algorithms that are
2077	** faster than the O(N*N) Wagner edit distance.
2078	*/
2079	if( nLeft*nRight>DIFF_ALIGN_MX && (pCfg->diffFlags & DIFF_SLOW_SBS)==0 ){
2080

	--- src/diff.c
	+++ src/diff.c
	@@ -1822,11 +1822,11 @@
1822	int limit = minInt(nA-i, nB-j);
1823	for(k=best; k<=limit && zA[k+i]==zB[k+j]; k++){}
1824	if( k>best ) best = k;
1825	}
1826	}
1827	score = 5 + ((best>=avg) ? 0 : (avg - best)*95/avg);
1828
1829	#if 0
1830	fprintf(stderr, "A: [%.s]\nB: [%.s]\nbest=%d avg=%d score=%d\n",
1831	nA, zA+1, nB, zB+1, best, avg, score);
1832	#endif
	@@ -1937,10 +1937,18 @@
1937	diffDLineXfer(dc.aTo, aRight, nRight);
1938	longestCommonSequence(&dc,0,nLeft,0,nRight,&iSX,&iEX,&iSY,&iEY);
1939	fossil_free(dc.aFrom);
1940	nLCS = iEX - iSX;
1941	if( nLCS<5 ) return 0; /* No good LCS was found */
1942
1943	if( pCfg->diffFlags & DIFF_DEBUG ){
1944	fossil_print(" LCS size=%d\n"
1945	" [%.*s]\n"
1946	" [%.*s]\n",
1947	nLCS, aLeft[iSX].n, aLeft[iSX].z,
1948	aLeft[iEX-1].n, aLeft[iEX-1].z);
1949	}
1950
1951	a1 = diffBlockAlignment(aLeft,iSX,aRight,iSY,pCfg,&n1);
1952	a2 = diffBlockAlignment(aLeft+iEX, nLeft-iEX,
1953	aRight+iEY, nRight-iEY,
1954	pCfg, &n2);
	@@ -1987,10 +1995,16 @@
1995	aBig = aRight;
1996	nBig = nRight;
1997	}
1998	iDivBig = nBig/2;
1999	iDivSmall = nSmall/2;
2000
2001	if( pCfg->diffFlags & DIFF_DEBUG ){
2002	fossil_print(" Divide at [%.*s]\n",
2003	aBig[iDivBig].n, aBig[iDivBig].z);
2004	}
2005
2006	bestScore = 10000;
2007	for(i=0; i<nSmall; i++){
2008	score = match_dline(aBig+iDivBig, aSmall+i) + abs(i-nSmall/2)*2;
2009	if( score<bestScore ){
2010	bestScore = score;
	@@ -2070,10 +2084,16 @@
2084	aM = fossil_malloc( nLeft + 2 );
2085	memset(aM, 1, nLeft);
2086	*pNResult = nLeft;
2087	return aM;
2088	}
2089
2090	if( pCfg->diffFlags & DIFF_DEBUG ){
2091	fossil_print("BlockAlignment:\n [%.s] + %d\n [%.s] + %d\n",
2092	aLeft[0].n, aLeft[0].z, nLeft,
2093	aRight[0].n, aRight[0].z, nRight);
2094	}
2095
2096	/* For large alignments, try to use alternative algorithms that are
2097	** faster than the O(N*N) Wagner edit distance.
2098	*/
2099	if( nLeft*nRight>DIFF_ALIGN_MX && (pCfg->diffFlags & DIFF_SLOW_SBS)==0 ){
2100

Fossil SCM

Keyboard Shortcuts