Fossil SCM

Experimental and undocument --yy option to the various diff operations does a slow O(N*N) algorithm which can sometimes compute a better side-by-side diff. But it can also take a lot longer and so is not recommended unless really needed.

drh 2017-06-11 16:25 trunk

Commit 1b3fa2610a494166b7ab61c6fd6bfab8b1752be47c1faf1866613f4a8a55c849

Parent e0757d270c3c10d…

1 file changed +8 -3

~ src/diff.c

M src/diff.c

+8 -3

		--- src/diff.c
		+++ src/diff.c
		@@ -40,10 +40,11 @@
40	40	#define DIFF_NOOPT (((u64)0x01)<<32) /* Suppress optimizations (debug) */
41	41	#define DIFF_INVERT (((u64)0x02)<<32) /* Invert the diff (debug) */
42	42	#define DIFF_CONTEXT_EX (((u64)0x04)<<32) /* Use context even if zero */
43	43	#define DIFF_NOTTOOBIG (((u64)0x08)<<32) /* Only display if not too big */
44	44	#define DIFF_STRIP_EOLCR (((u64)0x10)<<32) /* Strip trailing CR */
	45	+#define DIFF_SLOW_SBS (((u64)0x20)<<32) /* Better, but slower side-by-side */
45	46
46	47	/*
47	48	** These error messages are shared in multiple locations. They are defined
48	49	** here for consistency.
49	50	*/
		@@ -1037,11 +1038,12 @@
1037	1038	** are between 0 and 100 where 0 is a perfect match 100 is a complete
1038	1039	** mismatch.
1039	1040	*/
1040	1041	static unsigned char *sbsAlignment(
1041	1042	DLine aLeft, int nLeft, / Text on the left */
1042		- DLine aRight, int nRight / Text on the right */
	1043	+ DLine aRight, int nRight, / Text on the right */
	1044	+ u64 diffFlags /* Flags passed into the original diff */
1043	1045	){
1044	1046	int i, j, k; /* Loop counters */
1045	1047	int a; / One row of the Wagner matrix */
1046	1048	int pToFree; / Space that needs to be freed */
1047	1049	unsigned char aM; / Wagner result matrix */
		@@ -1061,11 +1063,11 @@
1061	1063	}
1062	1064
1063	1065	/* This algorithm is O(N**2). So if N is too big, bail out with a
1064	1066	** simple (but stupid and ugly) result that doesn't take too long. */
1065	1067	mnLen = nLeft<nRight ? nLeft : nRight;
1066		- if( nLeft*nRight>100000 ){
	1068	+ if( nLeft*nRight>100000 && (diffFlags & DIFF_SLOW_SBS)==0 ){
1067	1069	memset(aM, 4, mnLen);
1068	1070	if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
1069	1071	if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
1070	1072	return aM;
1071	1073	}
		@@ -1325,11 +1327,11 @@
1325	1327	m = R[r+i*3];
1326	1328	ma += R[r+i*3+1] + m;
1327	1329	mb += R[r+i*3+2] + m;
1328	1330	}
1329	1331
1330		- alignment = sbsAlignment(&A[a], ma, &B[b], mb);
	1332	+ alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1331	1333	for(j=0; ma+mb>0; j++){
1332	1334	if( alignment[j]==1 ){
1333	1335	/* Delete one line from the left */
1334	1336	sbsWriteLineno(&s, a, SBS_LNA);
1335	1337	s.iStart = 0;
		@@ -1967,10 +1969,13 @@
1967	1969	}
1968	1970	if( find_option("strip-trailing-cr",0,0)!=0 ){
1969	1971	diffFlags \|= DIFF_STRIP_EOLCR;
1970	1972	}
1971	1973	if( find_option("side-by-side","y",0)!=0 ) diffFlags \|= DIFF_SIDEBYSIDE;
	1974	+ if( find_option("yy",0,0)!=0 ){
	1975	+ diffFlags \|= DIFF_SIDEBYSIDE \| DIFF_SLOW_SBS;
	1976	+ }
1972	1977	if( find_option("unified",0,0)!=0 ) diffFlags &= ~DIFF_SIDEBYSIDE;
1973	1978	if( (z = find_option("context","c",1))!=0 && (f = atoi(z))>=0 ){
1974	1979	if( f > DIFF_CONTEXT_MASK ) f = DIFF_CONTEXT_MASK;
1975	1980	diffFlags \|= f + DIFF_CONTEXT_EX;
1976	1981	}
1977	1982

	--- src/diff.c
	+++ src/diff.c
	@@ -40,10 +40,11 @@
40	#define DIFF_NOOPT (((u64)0x01)<<32) /* Suppress optimizations (debug) */
41	#define DIFF_INVERT (((u64)0x02)<<32) /* Invert the diff (debug) */
42	#define DIFF_CONTEXT_EX (((u64)0x04)<<32) /* Use context even if zero */
43	#define DIFF_NOTTOOBIG (((u64)0x08)<<32) /* Only display if not too big */
44	#define DIFF_STRIP_EOLCR (((u64)0x10)<<32) /* Strip trailing CR */

45
46	/*
47	** These error messages are shared in multiple locations. They are defined
48	** here for consistency.
49	*/
	@@ -1037,11 +1038,12 @@
1037	** are between 0 and 100 where 0 is a perfect match 100 is a complete
1038	** mismatch.
1039	*/
1040	static unsigned char *sbsAlignment(
1041	DLine aLeft, int nLeft, / Text on the left */
1042	DLine aRight, int nRight / Text on the right */

1043	){
1044	int i, j, k; /* Loop counters */
1045	int a; / One row of the Wagner matrix */
1046	int pToFree; / Space that needs to be freed */
1047	unsigned char aM; / Wagner result matrix */
	@@ -1061,11 +1063,11 @@
1061	}
1062
1063	/* This algorithm is O(N**2). So if N is too big, bail out with a
1064	** simple (but stupid and ugly) result that doesn't take too long. */
1065	mnLen = nLeft<nRight ? nLeft : nRight;
1066	if( nLeft*nRight>100000 ){
1067	memset(aM, 4, mnLen);
1068	if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
1069	if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
1070	return aM;
1071	}
	@@ -1325,11 +1327,11 @@
1325	m = R[r+i*3];
1326	ma += R[r+i*3+1] + m;
1327	mb += R[r+i*3+2] + m;
1328	}
1329
1330	alignment = sbsAlignment(&A[a], ma, &B[b], mb);
1331	for(j=0; ma+mb>0; j++){
1332	if( alignment[j]==1 ){
1333	/* Delete one line from the left */
1334	sbsWriteLineno(&s, a, SBS_LNA);
1335	s.iStart = 0;
	@@ -1967,10 +1969,13 @@
1967	}
1968	if( find_option("strip-trailing-cr",0,0)!=0 ){
1969	diffFlags \|= DIFF_STRIP_EOLCR;
1970	}
1971	if( find_option("side-by-side","y",0)!=0 ) diffFlags \|= DIFF_SIDEBYSIDE;



1972	if( find_option("unified",0,0)!=0 ) diffFlags &= ~DIFF_SIDEBYSIDE;
1973	if( (z = find_option("context","c",1))!=0 && (f = atoi(z))>=0 ){
1974	if( f > DIFF_CONTEXT_MASK ) f = DIFF_CONTEXT_MASK;
1975	diffFlags \|= f + DIFF_CONTEXT_EX;
1976	}
1977

	--- src/diff.c
	+++ src/diff.c
	@@ -40,10 +40,11 @@
40	#define DIFF_NOOPT (((u64)0x01)<<32) /* Suppress optimizations (debug) */
41	#define DIFF_INVERT (((u64)0x02)<<32) /* Invert the diff (debug) */
42	#define DIFF_CONTEXT_EX (((u64)0x04)<<32) /* Use context even if zero */
43	#define DIFF_NOTTOOBIG (((u64)0x08)<<32) /* Only display if not too big */
44	#define DIFF_STRIP_EOLCR (((u64)0x10)<<32) /* Strip trailing CR */
45	#define DIFF_SLOW_SBS (((u64)0x20)<<32) /* Better, but slower side-by-side */
46
47	/*
48	** These error messages are shared in multiple locations. They are defined
49	** here for consistency.
50	*/
	@@ -1037,11 +1038,12 @@
1038	** are between 0 and 100 where 0 is a perfect match 100 is a complete
1039	** mismatch.
1040	*/
1041	static unsigned char *sbsAlignment(
1042	DLine aLeft, int nLeft, / Text on the left */
1043	DLine aRight, int nRight, / Text on the right */
1044	u64 diffFlags /* Flags passed into the original diff */
1045	){
1046	int i, j, k; /* Loop counters */
1047	int a; / One row of the Wagner matrix */
1048	int pToFree; / Space that needs to be freed */
1049	unsigned char aM; / Wagner result matrix */
	@@ -1061,11 +1063,11 @@
1063	}
1064
1065	/* This algorithm is O(N**2). So if N is too big, bail out with a
1066	** simple (but stupid and ugly) result that doesn't take too long. */
1067	mnLen = nLeft<nRight ? nLeft : nRight;
1068	if( nLeft*nRight>100000 && (diffFlags & DIFF_SLOW_SBS)==0 ){
1069	memset(aM, 4, mnLen);
1070	if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
1071	if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
1072	return aM;
1073	}
	@@ -1325,11 +1327,11 @@
1327	m = R[r+i*3];
1328	ma += R[r+i*3+1] + m;
1329	mb += R[r+i*3+2] + m;
1330	}
1331
1332	alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1333	for(j=0; ma+mb>0; j++){
1334	if( alignment[j]==1 ){
1335	/* Delete one line from the left */
1336	sbsWriteLineno(&s, a, SBS_LNA);
1337	s.iStart = 0;
	@@ -1967,10 +1969,13 @@
1969	}
1970	if( find_option("strip-trailing-cr",0,0)!=0 ){
1971	diffFlags \|= DIFF_STRIP_EOLCR;
1972	}
1973	if( find_option("side-by-side","y",0)!=0 ) diffFlags \|= DIFF_SIDEBYSIDE;
1974	if( find_option("yy",0,0)!=0 ){
1975	diffFlags \|= DIFF_SIDEBYSIDE \| DIFF_SLOW_SBS;
1976	}
1977	if( find_option("unified",0,0)!=0 ) diffFlags &= ~DIFF_SIDEBYSIDE;
1978	if( (z = find_option("context","c",1))!=0 && (f = atoi(z))>=0 ){
1979	if( f > DIFF_CONTEXT_MASK ) f = DIFF_CONTEXT_MASK;
1980	diffFlags \|= f + DIFF_CONTEXT_EX;
1981	}
1982

Fossil SCM

Keyboard Shortcuts