Index: src/diff.c
==================================================================
--- src/diff.c
+++ src/diff.c
@@ -355,19 +355,21 @@
typedef struct SbsLine SbsLine;
struct SbsLine {
char *zLine; /* The output line under construction */
int n; /* Index of next unused slot in the zLine[] */
int width; /* Maximum width of a column in the output */
- unsigned char escHtml; /* True to escape html characters */
+ unsigned char escHtml; /* True to escape html characters */
+ int iStart; /* Write zStart prior to character iStart */
+ const char *zStart; /* A <span> tag */
+ int iEnd; /* Write </span> prior to character iEnd */
};
/*
** Flags for sbsWriteText()
*/
-#define SBS_NEWLINE 0x0001 /* End with \n\000 */
-#define SBS_PAD 0x0002 /* Pad output to width spaces */
-#define SBS_ENDSPAN 0x0004 /* Write a </span> after text */
+#define SBS_NEWLINE 0x0001 /* End with \n\000 */
+#define SBS_PAD 0x0002 /* Pad output to width spaces */
/*
** Write up to width characters of pLine into z[]. Translate tabs into
** spaces. Add a newline if SBS_NEWLINE is set. Translate HTML characters
** if SBS_HTML is set. Pad the rendering out width bytes if SBS_PAD is set.
@@ -380,10 +382,20 @@
const char *zIn = pLine->z;
char *z = &p->zLine[p->n];
int w = p->width;
for(i=j=k=0; k<w && i<n; i++, k++){
char c = zIn[i];
+ if( p->escHtml ){
+ if( i==p->iStart ){
+ int x = strlen(p->zStart);
+ memcpy(z+j, p->zStart, x);
+ j += x;
+ }else if( i==p->iEnd ){
+ memcpy(z+j, "</span>", 7);
+ j += 7;
+ }
+ }
if( c=='\t' ){
z[j++] = ' ';
while( (k&7)!=7 && k<w ){ z[j++] = ' '; k++; }
}else if( c=='\r' || c=='\f' ){
z[j++] = ' ';
@@ -398,11 +410,11 @@
j += 4;
}else{
z[j++] = c;
}
}
- if( (flags & SBS_ENDSPAN) && p->escHtml ){
+ if( p->escHtml && i<=p->iEnd ){
memcpy(&z[j], "</span>", 7);
j += 7;
}
if( (flags & SBS_PAD)!=0 ){
while( k<w ){ k++; z[j++] = ' '; }
@@ -444,10 +456,226 @@
p->n += 6;
sbsWriteHtml(p, "</span>");
p->zLine[p->n++] = ' ';
}
+/*
+** Write out lines that have been edited. Adjust the highlight to cover
+** only those parts of the line that actually changed.
+*/
+static void sbsWriteLineChange(
+ SbsLine *p, /* The SBS output line */
+ DLine *pLeft, /* Left line of the change */
+ int lnLeft, /* Line number for the left line */
+ DLine *pRight, /* Right line of the change */
+ int lnRight /* Line number of the right line */
+){
+ int nLeft; /* Length of left line in bytes */
+ int nRight; /* Length of right line in bytes */
+ int nPrefix; /* Length of common prefix */
+ int nSuffix; /* Length of common suffix */
+ int width; /* Total column width */
+ const char *zLeft; /* Text of the left line */
+ const char *zRight; /* Text of the right line */
+
+ nLeft = pLeft->h & LENGTH_MASK;
+ zLeft = pLeft->z;
+ nRight = pRight->h & LENGTH_MASK;
+ zRight = pRight->z;
+
+ nPrefix = 0;
+ while( nPrefix<nLeft && nPrefix<nRight && zLeft[nPrefix]==zRight[nPrefix] ){
+ nPrefix++;
+ }
+ nSuffix = 0;
+ if( nPrefix<nLeft && nPrefix<nRight ){
+ while( nSuffix<nLeft && nSuffix<nRight
+ && zLeft[nLeft-nSuffix-1]==zRight[nRight-nSuffix-1] ){
+ nSuffix++;
+ }
+ if( nSuffix==nLeft || nSuffix==nRight ) nPrefix = 0;
+ }
+ if( nPrefix+nSuffix > nLeft ) nSuffix = nLeft - nPrefix;
+ if( nPrefix+nSuffix > nRight ) nSuffix = nRight - nPrefix;
+ if( nPrefix+nSuffix==nLeft ){
+ /* Text inserted on the right */
+ sbsWriteLineno(p, lnLeft);
+ p->iStart = p->iEnd = -1;
+ sbsWriteText(p, pLeft, SBS_PAD);
+ sbsWrite(p, " | ", 3);
+ sbsWriteLineno(p, lnRight);
+ p->iStart = nPrefix;
+ p->iEnd = nRight - nSuffix;
+ p->zStart = "<span class=\"diffadd\">";
+ sbsWriteText(p, pRight, SBS_NEWLINE);
+ }else if( nPrefix+nSuffix==nRight ){
+ /* Text deleted from the left */
+ sbsWriteLineno(p, lnLeft);
+ p->iStart = nPrefix;
+ p->iEnd = nLeft - nSuffix;
+ p->zStart = "<span class=\"diffrm\">";
+ sbsWriteText(p, pLeft, SBS_PAD);
+ sbsWrite(p, " | ", 3);
+ sbsWriteLineno(p, lnRight);
+ p->iStart = p->iEnd = -1;
+ sbsWriteText(p, pRight, SBS_NEWLINE);
+ }else{
+ /* Text modified between left and right */
+ sbsWriteLineno(p, lnLeft);
+ p->iStart = nPrefix;
+ p->iEnd = nLeft - nSuffix;
+ p->zStart = "<span class=\"diffchng\">";
+ sbsWriteText(p, pLeft, SBS_PAD);
+ sbsWrite(p, " | ", 3);
+ sbsWriteLineno(p, lnRight);
+ p->iEnd = nRight - nSuffix;
+ sbsWriteText(p, pRight, SBS_NEWLINE);
+ }
+}
+
+/*
+** Return the number between 0 and 100 that is smaller the closer pA and
+** pB match. Return 0 for a perfect match. Return 100 if pA and pB are
+** completely different.
+*/
+static int match_dline(DLine *pA, DLine *pB){
+ const char *zA;
+ const char *zB;
+ int nA;
+ int nB;
+ int minDist;
+ int i;
+ int nMatch;
+ int score;
+
+ zA = pA->z;
+ zB = pB->z;
+ nA = pA->h & LENGTH_MASK;
+ nB = pB->h & LENGTH_MASK;
+ while( nA>0 && fossil_isspace(zA[0]) ){ nA--; zA++; }
+ while( nA>0 && fossil_isspace(zA[nA-1]) ){ nA--; }
+ while( nB>0 && fossil_isspace(zB[0]) ){ nB--; zB++; }
+ while( nB>0 && fossil_isspace(zB[nB-1]) ){ nB--; }
+ minDist = nA;
+ if( minDist>nB ) minDist = nB;
+ if( minDist==0 ){
+ score = 100;
+ }else{
+ for(i=0; i<nA && i<nB && zA[i]==zB[i]; i++){}
+ nMatch = i;
+ for(i=1; i<=nA && i<=nB && zA[nA-i]==zB[nB-i]; i++){}
+ nMatch += i-1;
+ score = (nMatch >= minDist) ? 0 : ((minDist - nMatch)*100)/minDist;
+ }
+ return score;
+}
+
+/*
+** There is a change block in which nLeft lines of text on the left are
+** converted into nRight lines of text on the right. This routine computes
+** how the lines on the left line up with the lines on the right.
+**
+** The return value is a buffer of unsigned characters, obtained from
+** fossil_malloc(). (The caller needs to free the return value using
+** fossil_free().) Entries in the returned array have values as follows:
+**
+** 1. Delete the next line of pLeft.
+** 2. The next line of pLeft changes into the next line of pRight.
+** 3. Insert the next line of pRight.
+**
+** The length of the returned array will be just large enough to cause
+** all elements of pLeft and pRight to be consumed.
+**
+** Algorithm: Wagner's minimum edit-distance algorithm, modified by
+** adding a cost to each match based on how well the two rows match
+** each other. Insertion and deletion costs are 50. Match costs
+** are between 0 and 100 where 0 is a perfect match 100 is a complete
+** mismatch.
+*/
+static unsigned char *sbsAlignment(
+ DLine *aLeft, int nLeft, /* Text on the left */
+ DLine *aRight, int nRight /* Text on the right */
+){
+ int i, j, k; /* Loop counters */
+ int *a; /* One row of the Wagner matrix */
+ int *pToFree; /* Space that needs to be freed */
+ unsigned char *aM; /* Wagner result matrix */
+ int aBuf[100]; /* Stack space for a[] if nRight not to big */
+
+ aM = fossil_malloc( (nLeft+1)*(nRight+1) );
+ if( nLeft==0 ){
+ memset(aM, 3, nRight);
+ return aM;
+ }
+ if( nRight==0 ){
+ memset(aM, 1, nLeft);
+ return aM;
+ }
+ if( nRight < (sizeof(aBuf)/sizeof(aBuf[0]))-1 ){
+ pToFree = 0;
+ a = aBuf;
+ }else{
+ a = pToFree = fossil_malloc( sizeof(a[0])*(nRight+1) );
+ }
+
+ /* Compute the best alignment */
+ for(i=0; i<=nRight; i++){
+ aM[i] = 3;
+ a[i] = i*50;
+ }
+ aM[0] = 0;
+ for(j=1; j<=nLeft; j++){
+ int p = a[0];
+ a[0] = p+50;
+ aM[j*(nRight+1)] = 1;
+ for(i=1; i<=nRight; i++){
+ int m = a[i-1]+50;
+ int d = 3;
+ if( m>a[i]+50 ){
+ m = a[i]+50;
+ d = 1;
+ }
+ if( m>p ){
+ int score = match_dline(&aLeft[j-1], &aRight[i-1]);
+ if( (score<66 || (i<j+1 && i>j-1)) && m>p+score ){
+ m = p+score;
+ d = 2;
+ }
+ }
+ p = a[i];
+ a[i] = m;
+ aM[j*(nRight+1)+i] = d;
+ }
+ }
+
+ /* Compute the lowest-cost path back through the matrix */
+ i = nRight;
+ j = nLeft;
+ k = (nRight+1)*(nLeft+1)-1;
+ while( i+j>0 ){
+ unsigned char c = aM[k--];
+ if( c==2 ){
+ assert( i>0 && j>0 );
+ i--;
+ j--;
+ }else if( c==3 ){
+ assert( i>0 );
+ i--;
+ }else{
+ assert( j>0 );
+ j--;
+ }
+ aM[k] = aM[j*(nRight+1)+i];
+ }
+ k++;
+ i = (nRight+1)*(nLeft+1) - k;
+ memmove(aM, &aM[k], i);
+
+ /* Return the result */
+ fossil_free(pToFree);
+ return aM;
+}
/*
** Given a diff context in which the aEdit[] array has been filled
** in, compute a side-by-side diff into pOut.
*/
@@ -474,10 +702,12 @@
s.zLine = fossil_malloc( 10*width + 100 );
if( s.zLine==0 ) return;
s.width = width;
s.escHtml = escHtml;
+ s.iStart = -1;
+ s.iEnd = -1;
A = p->aFrom;
B = p->aTo;
R = p->aEdit;
mxr = p->nEdit;
while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }
@@ -527,10 +757,11 @@
b += skip;
m = R[r] - skip;
for(j=0; j<m; j++){
s.n = 0;
sbsWriteLineno(&s, a+j);
+ s.iStart = s.iEnd = -1;
sbsWriteText(&s, &A[a+j], SBS_PAD);
sbsWrite(&s, " ", 3);
sbsWriteLineno(&s, b+j);
sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
blob_append(pOut, s.zLine, s.n);
@@ -538,52 +769,58 @@
a += m;
b += m;
/* Show the differences */
for(i=0; i<nr; i++){
- ma = R[r+i*3+1];
- mb = R[r+i*3+2];
- m = ma<mb ? ma : mb;
- for(j=0; j<m; j++){
- s.n = 0;
- sbsWriteLineno(&s, a+j);
- sbsWriteHtml(&s, "<span class=\"diffchng\">");
- sbsWriteText(&s, &A[a+j], SBS_PAD | SBS_ENDSPAN);
- sbsWrite(&s, " | ", 3);
- sbsWriteLineno(&s, b+j);
- sbsWriteHtml(&s, "<span class=\"diffchng\">");
- sbsWriteText(&s, &B[b+j], SBS_NEWLINE | SBS_ENDSPAN);
- blob_append(pOut, s.zLine, s.n);
- }
- a += m;
- b += m;
- ma -= m;
- mb -= m;
- for(j=0; j<ma; j++){
- s.n = 0;
- sbsWriteLineno(&s, a+j);
- sbsWriteHtml(&s, "<span class=\"diffrm\">");
- sbsWriteText(&s, &A[a+j], SBS_PAD | SBS_ENDSPAN);
- sbsWrite(&s, " <\n", 3);
- blob_append(pOut, s.zLine, s.n);
+ unsigned char *alignment;
+ ma = R[r+i*3+1]; /* Lines on left but not on right */
+ mb = R[r+i*3+2]; /* Lines on right but not on left */
+ alignment = sbsAlignment(&A[a], ma, &B[b], mb);
+ for(j=0; ma+mb>0; j++){
+ if( alignment[j]==1 ){
+ s.n = 0;
+ sbsWriteLineno(&s, a);
+ s.iStart = 0;
+ s.zStart = "<span class=\"diffrm\">";
+ s.iEnd = s.width;
+ sbsWriteText(&s, &A[a], SBS_PAD);
+ sbsWrite(&s, " <\n", 3);
+ blob_append(pOut, s.zLine, s.n);
+ assert( ma>0 );
+ ma--;
+ a++;
+ }else if( alignment[j]==2 ){
+ s.n = 0;
+ sbsWriteLineChange(&s, &A[a], a, &B[b], b);
+ blob_append(pOut, s.zLine, s.n);
+ assert( ma>0 && mb>0 );
+ ma--;
+ mb--;
+ a++;
+ b++;
+ }else{
+ s.n = 0;
+ sbsWriteSpace(&s, width + 7);
+ sbsWrite(&s, " > ", 3);
+ sbsWriteLineno(&s, b);
+ s.iStart = 0;
+ s.zStart = "<span class=\"diffadd\">";
+ s.iEnd = s.width;
+ sbsWriteText(&s, &B[b], SBS_NEWLINE);
+ blob_append(pOut, s.zLine, s.n);
+ assert( mb>0 );
+ mb--;
+ b++;
+ }
}
- a += ma;
- for(j=0; j<mb; j++){
- s.n = 0;
- sbsWriteSpace(&s, width + 7);
- sbsWrite(&s, " > ", 3);
- sbsWriteLineno(&s, b+j);
- sbsWriteHtml(&s, "<span class=\"diffadd\">");
- sbsWriteText(&s, &B[b+j], SBS_NEWLINE | SBS_ENDSPAN);
- blob_append(pOut, s.zLine, s.n);
- }
- b += mb;
+ fossil_free(alignment);
if( i<nr-1 ){
m = R[r+i*3+3];
for(j=0; j<m; j++){
s.n = 0;
sbsWriteLineno(&s, a+j);
+ s.iStart = s.iEnd = -1;
sbsWriteText(&s, &A[a+j], SBS_PAD);
sbsWrite(&s, " ", 3);
sbsWriteLineno(&s, b+j);
sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
blob_append(pOut, s.zLine, s.n);
@@ -598,10 +835,11 @@
m = R[r+nr*3];
if( m>nContext ) m = nContext;
for(j=0; j<m; j++){
s.n = 0;
sbsWriteLineno(&s, a+j);
+ s.iStart = s.iEnd = -1;
sbsWriteText(&s, &A[a+j], SBS_PAD);
sbsWrite(&s, " ", 3);
sbsWriteLineno(&s, b+j);
sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
blob_append(pOut, s.zLine, s.n);
@@ -943,11 +1181,11 @@
p->aEdit[r+3]++;
cpy--;
}
/* Shift insertions toward the end of the file */
- while( p->aEdit[r+3]>0 && del==0 && ins>0 ){
+ while( r+3<p->nEdit && p->aEdit[r+3]>0 && del==0 && ins>0 ){
DLine *pTop = &p->aTo[lnTo]; /* First line inserted */
DLine *pBtm = &p->aTo[lnTo+ins]; /* First line past end of insert */
if( same_dline(pTop, pBtm)==0 ) break;
if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop+1)+LENGTH(pBtm) ) break;
lnFrom++;
@@ -969,11 +1207,11 @@
p->aEdit[r+3]++;
cpy--;
}
/* Shift deletions toward the end of the file */
- while( p->aEdit[r+3]>0 && del>0 && ins==0 ){
+ while( r+3<p->nEdit && p->aEdit[r+3]>0 && del>0 && ins==0 ){
DLine *pTop = &p->aFrom[lnFrom]; /* First line deleted */
DLine *pBtm = &p->aFrom[lnFrom+del]; /* First line past end of delete */
if( same_dline(pTop, pBtm)==0 ) break;
if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop)+LENGTH(pBtm) ) break;
lnFrom++;
Index: src/style.c
==================================================================
--- src/style.c
+++ src/style.c
@@ -764,11 +764,11 @@
@ font-family: monospace;
@ white-space: pre;
},
{ "span.diffchng",
"changes in a diff",
- @ background-color: #ffffc8;
+ @ background-color: #e0e0ff;
},
{ "span.diffadd",
"added code in a diff",
@ background-color: #e0ffe0;
},