Fossil SCM

Code and comment cleanup. Fixes to the new formatDiff() routine related to block alignment.

drh 2021-08-30 12:00 diff-color-enhancements
Commit 16a2364f3670205bc4fd8611d15727becaecf725370a902a61f3e6c97d83af44
Parent 5e70c3ff96d97d3…
1 file changed +45 -52
~ src/diff.c
M src/diff.c
+45 -52
--- src/diff.c
+++ src/diff.c
@@ -1103,22 +1103,17 @@
11031103
 ** 1. Delete the next line of pLeft.
11041104
 ** 2. Insert the next line of pRight.
11051105
 ** 3. The next line of pLeft changes into the next line of pRight.
11061106
 ** 4. Delete one line from pLeft and add one line to pRight.
11071107
 **
1108
-** Values larger than three indicate better matches.
1109
-**
1110
-** The length of the returned array will be just large enough to cause
1111
-** all elements of pLeft and pRight to be consumed.
1112
-**
11131108
 ** Algorithm: Wagner's minimum edit-distance algorithm, modified by
11141109
 ** adding a cost to each match based on how well the two rows match
11151110
 ** each other. Insertion and deletion costs are 50. Match costs
11161111
 ** are between 0 and 100 where 0 is a perfect match 100 is a complete
11171112
 ** mismatch.
11181113
 */
1119
-static unsigned char *sbsAlignment(
1114
+static unsigned char *diffBlockAlignment(
11201115
 const DLine *aLeft, int nLeft, /* Text on the left */
11211116
 const DLine *aRight, int nRight, /* Text on the right */
11221117
 u64 diffFlags /* Flags passed into the original diff */
11231118
 ){
11241119
 int i, j, k; /* Loop counters */
@@ -1128,24 +1123,26 @@
11281123
 int nMatch, iMatch; /* Number of matching lines and match score */
11291124
 int mnLen; /* MIN(nLeft, nRight) */
11301125
 int mxLen; /* MAX(nLeft, nRight) */
11311126
 int aBuf[100]; /* Stack space for a[] if nRight not to big */
11321127
1133
- aM = fossil_malloc( (nLeft+1)*(nRight+1) );
11341128
 if( nLeft==0 ){
1129
+ aM = fossil_malloc( nLeft + nRight + 2 );
11351130
 memset(aM, 2, nRight);
11361131
 return aM;
11371132
 }
11381133
 if( nRight==0 ){
1134
+ aM = fossil_malloc( nLeft + nRight + 2 );
11391135
 memset(aM, 1, nLeft);
11401136
 return aM;
11411137
 }
11421138
11431139
 /* This algorithm is O(N**2). So if N is too big, bail out with a
11441140
 ** simple (but stupid and ugly) result that doesn't take too long. */
11451141
 mnLen = nLeft<nRight ? nLeft : nRight;
11461142
 if( nLeft*nRight>100000 && (diffFlags & DIFF_SLOW_SBS)==0 ){
1143
+ aM = fossil_malloc( nLeft + nRight + 2 );
11471144
 memset(aM, 4, mnLen);
11481145
 if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
11491146
 if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
11501147
 return aM;
11511148
 }
@@ -1154,10 +1151,12 @@
11541151
 pToFree = 0;
11551152
 a = aBuf;
11561153
 }else{
11571154
 a = pToFree = fossil_malloc( sizeof(a[0])*(nRight+1) );
11581155
 }
1156
+ aM = fossil_malloc( (nLeft+1)*(nRight+1) );
1157
+
11591158
11601159
 /* Compute the best alignment */
11611160
 for(i=0; i<=nRight; i++){
11621161
 aM[i] = 2;
11631162
 a[i] = i*50;
@@ -1235,22 +1234,10 @@
12351234
 /* Return the result */
12361235
 fossil_free(pToFree);
12371236
 return aM;
12381237
 }
12391238
1240
-#if 0 /* not used */
1241
-/*
1242
-** R[] is an array of six integer, two COPY/DELETE/INSERT triples for a
1243
-** pair of adjacent differences. Return true if the gap between these
1244
-** two differences is so small that they should be rendered as a single
1245
-** edit.
1246
-*/
1247
-static int smallGap(int *R){
1248
- return R[3]<=2 || R[3]<=(R[1]+R[2]+R[4]+R[5])/8;
1249
-}
1250
-#endif
1251
-
12521239
 /*
12531240
 ** Given a diff context in which the aEdit[] array has been filled
12541241
 ** in, compute a side-by-side diff into pOut.
12551242
 */
12561243
 static void sbsDiff(
@@ -1399,23 +1386,11 @@
13991386
 for(i=0; i<nr; i++){
14001387
 unsigned char *alignment;
14011388
 ma = R[r+i*3+1]; /* Lines on left but not on right */
14021389
 mb = R[r+i*3+2]; /* Lines on right but not on left */
14031390
1404
-#if 0 /* not used */
1405
- /* If the gap between the current diff and then next diff within the
1406
- ** same block is not too great, then render them as if they are a
1407
- ** single diff. */
1408
- while( i<nr-1 && smallGap(&R[r+i*3]) ){
1409
- i++;
1410
- m = R[r+i*3];
1411
- ma += R[r+i*3+1] + m;
1412
- mb += R[r+i*3+2] + m;
1413
- }
1414
-#endif
1415
-
1416
- alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1391
+ alignment = diffBlockAlignment(&A[a], ma, &B[b], mb, diffFlags);
14171392
 for(j=0; ma+mb>0; j++){
14181393
 if( alignment[j]==1 ){
14191394
 /* Delete one line from the left */
14201395
 sbsWriteLineno(&s, a, SBS_LNA);
14211396
 s.a[0].iStart = 0;
@@ -1684,31 +1659,49 @@
16841659
 for(i=0; i<nr; i++){
16851660
 unsigned char *alignment;
16861661
 ma = R[r+i*3+1]; /* Lines on left but not on right */
16871662
 mb = R[r+i*3+2]; /* Lines on right but not on left */
16881663
1689
- alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1664
+ alignment = diffBlockAlignment(&A[a], ma, &B[b], mb, diffFlags);
16901665
 for(j=0; ma+mb>0; j++){
1691
- if( alignment[j]==1 ){
1692
- /* Delete one line from the left */
1693
- pBuilder->xDelete(pBuilder, &A[a]);
1694
- ma--;
1695
- a++;
1696
- }else if( alignment[j]==2 ){
1697
- /* Insert one line on the right */
1698
- pBuilder->xInsert(pBuilder, &B[b]);
1699
- assert( mb>0 );
1700
- mb--;
1701
- b++;
1702
- }else{
1703
- /* The left line is changed into the right line */
1704
- pBuilder->xEdit(pBuilder, &A[a], &B[b]);
1705
- assert( ma>0 && mb>0 );
1706
- ma--;
1707
- mb--;
1708
- a++;
1709
- b++;
1666
+ switch( alignment[j] ){
1667
+ case 1: {
1668
+ /* Delete one line from the left */
1669
+ pBuilder->xDelete(pBuilder, &A[a]);
1670
+ ma--;
1671
+ a++;
1672
+ break;
1673
+ }
1674
+ case 2: {
1675
+ /* Insert one line on the right */
1676
+ pBuilder->xInsert(pBuilder, &B[b]);
1677
+ assert( mb>0 );
1678
+ mb--;
1679
+ b++;
1680
+ break;
1681
+ }
1682
+ case 3: {
1683
+ /* The left line is changed into the right line */
1684
+ pBuilder->xEdit(pBuilder, &A[a], &B[b]);
1685
+ assert( ma>0 && mb>0 );
1686
+ ma--;
1687
+ mb--;
1688
+ a++;
1689
+ b++;
1690
+ break;
1691
+ }
1692
+ case 4: {
1693
+ /* Delete from left then separately insert on the right */
1694
+ pBuilder->xDelete(pBuilder, &A[a]);
1695
+ ma--;
1696
+ a++;
1697
+ pBuilder->xInsert(pBuilder, &B[b]);
1698
+ assert( mb>0 );
1699
+ mb--;
1700
+ b++;
1701
+ break;
1702
+ }
17101703
 }
17111704
 }
17121705
 fossil_free(alignment);
17131706
 if( i<nr-1 ){
17141707
 m = R[r+i*3+3];
17151708
--- src/diff.c
+++ src/diff.c
@@ -1103,22 +1103,17 @@
1103 ** 1. Delete the next line of pLeft.
1104 ** 2. Insert the next line of pRight.
1105 ** 3. The next line of pLeft changes into the next line of pRight.
1106 ** 4. Delete one line from pLeft and add one line to pRight.
1107 **
1108 ** Values larger than three indicate better matches.
1109 **
1110 ** The length of the returned array will be just large enough to cause
1111 ** all elements of pLeft and pRight to be consumed.
1112 **
1113 ** Algorithm: Wagner's minimum edit-distance algorithm, modified by
1114 ** adding a cost to each match based on how well the two rows match
1115 ** each other. Insertion and deletion costs are 50. Match costs
1116 ** are between 0 and 100 where 0 is a perfect match 100 is a complete
1117 ** mismatch.
1118 */
1119 static unsigned char *sbsAlignment(
1120 const DLine *aLeft, int nLeft, /* Text on the left */
1121 const DLine *aRight, int nRight, /* Text on the right */
1122 u64 diffFlags /* Flags passed into the original diff */
1123 ){
1124 int i, j, k; /* Loop counters */
@@ -1128,24 +1123,26 @@
1128 int nMatch, iMatch; /* Number of matching lines and match score */
1129 int mnLen; /* MIN(nLeft, nRight) */
1130 int mxLen; /* MAX(nLeft, nRight) */
1131 int aBuf[100]; /* Stack space for a[] if nRight not to big */
1132
1133 aM = fossil_malloc( (nLeft+1)*(nRight+1) );
1134 if( nLeft==0 ){
 
1135 memset(aM, 2, nRight);
1136 return aM;
1137 }
1138 if( nRight==0 ){
 
1139 memset(aM, 1, nLeft);
1140 return aM;
1141 }
1142
1143 /* This algorithm is O(N**2). So if N is too big, bail out with a
1144 ** simple (but stupid and ugly) result that doesn't take too long. */
1145 mnLen = nLeft<nRight ? nLeft : nRight;
1146 if( nLeft*nRight>100000 && (diffFlags & DIFF_SLOW_SBS)==0 ){
 
1147 memset(aM, 4, mnLen);
1148 if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
1149 if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
1150 return aM;
1151 }
@@ -1154,10 +1151,12 @@
1154 pToFree = 0;
1155 a = aBuf;
1156 }else{
1157 a = pToFree = fossil_malloc( sizeof(a[0])*(nRight+1) );
1158 }
 
 
1159
1160 /* Compute the best alignment */
1161 for(i=0; i<=nRight; i++){
1162 aM[i] = 2;
1163 a[i] = i*50;
@@ -1235,22 +1234,10 @@
1235 /* Return the result */
1236 fossil_free(pToFree);
1237 return aM;
1238 }
1239
1240 #if 0 /* not used */
1241 /*
1242 ** R[] is an array of six integer, two COPY/DELETE/INSERT triples for a
1243 ** pair of adjacent differences. Return true if the gap between these
1244 ** two differences is so small that they should be rendered as a single
1245 ** edit.
1246 */
1247 static int smallGap(int *R){
1248 return R[3]<=2 || R[3]<=(R[1]+R[2]+R[4]+R[5])/8;
1249 }
1250 #endif
1251
1252 /*
1253 ** Given a diff context in which the aEdit[] array has been filled
1254 ** in, compute a side-by-side diff into pOut.
1255 */
1256 static void sbsDiff(
@@ -1399,23 +1386,11 @@
1399 for(i=0; i<nr; i++){
1400 unsigned char *alignment;
1401 ma = R[r+i*3+1]; /* Lines on left but not on right */
1402 mb = R[r+i*3+2]; /* Lines on right but not on left */
1403
1404 #if 0 /* not used */
1405 /* If the gap between the current diff and then next diff within the
1406 ** same block is not too great, then render them as if they are a
1407 ** single diff. */
1408 while( i<nr-1 && smallGap(&R[r+i*3]) ){
1409 i++;
1410 m = R[r+i*3];
1411 ma += R[r+i*3+1] + m;
1412 mb += R[r+i*3+2] + m;
1413 }
1414 #endif
1415
1416 alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1417 for(j=0; ma+mb>0; j++){
1418 if( alignment[j]==1 ){
1419 /* Delete one line from the left */
1420 sbsWriteLineno(&s, a, SBS_LNA);
1421 s.a[0].iStart = 0;
@@ -1684,31 +1659,49 @@
1684 for(i=0; i<nr; i++){
1685 unsigned char *alignment;
1686 ma = R[r+i*3+1]; /* Lines on left but not on right */
1687 mb = R[r+i*3+2]; /* Lines on right but not on left */
1688
1689 alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1690 for(j=0; ma+mb>0; j++){
1691 if( alignment[j]==1 ){
1692 /* Delete one line from the left */
1693 pBuilder->xDelete(pBuilder, &A[a]);
1694 ma--;
1695 a++;
1696 }else if( alignment[j]==2 ){
1697 /* Insert one line on the right */
1698 pBuilder->xInsert(pBuilder, &B[b]);
1699 assert( mb>0 );
1700 mb--;
1701 b++;
1702 }else{
1703 /* The left line is changed into the right line */
1704 pBuilder->xEdit(pBuilder, &A[a], &B[b]);
1705 assert( ma>0 && mb>0 );
1706 ma--;
1707 mb--;
1708 a++;
1709 b++;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1710 }
1711 }
1712 fossil_free(alignment);
1713 if( i<nr-1 ){
1714 m = R[r+i*3+3];
1715
--- src/diff.c
+++ src/diff.c
@@ -1103,22 +1103,17 @@
1103 ** 1. Delete the next line of pLeft.
1104 ** 2. Insert the next line of pRight.
1105 ** 3. The next line of pLeft changes into the next line of pRight.
1106 ** 4. Delete one line from pLeft and add one line to pRight.
1107 **
 
 
 
 
 
1108 ** Algorithm: Wagner's minimum edit-distance algorithm, modified by
1109 ** adding a cost to each match based on how well the two rows match
1110 ** each other. Insertion and deletion costs are 50. Match costs
1111 ** are between 0 and 100 where 0 is a perfect match 100 is a complete
1112 ** mismatch.
1113 */
1114 static unsigned char *diffBlockAlignment(
1115 const DLine *aLeft, int nLeft, /* Text on the left */
1116 const DLine *aRight, int nRight, /* Text on the right */
1117 u64 diffFlags /* Flags passed into the original diff */
1118 ){
1119 int i, j, k; /* Loop counters */
@@ -1128,24 +1123,26 @@
1123 int nMatch, iMatch; /* Number of matching lines and match score */
1124 int mnLen; /* MIN(nLeft, nRight) */
1125 int mxLen; /* MAX(nLeft, nRight) */
1126 int aBuf[100]; /* Stack space for a[] if nRight not to big */
1127
 
1128 if( nLeft==0 ){
1129 aM = fossil_malloc( nLeft + nRight + 2 );
1130 memset(aM, 2, nRight);
1131 return aM;
1132 }
1133 if( nRight==0 ){
1134 aM = fossil_malloc( nLeft + nRight + 2 );
1135 memset(aM, 1, nLeft);
1136 return aM;
1137 }
1138
1139 /* This algorithm is O(N**2). So if N is too big, bail out with a
1140 ** simple (but stupid and ugly) result that doesn't take too long. */
1141 mnLen = nLeft<nRight ? nLeft : nRight;
1142 if( nLeft*nRight>100000 && (diffFlags & DIFF_SLOW_SBS)==0 ){
1143 aM = fossil_malloc( nLeft + nRight + 2 );
1144 memset(aM, 4, mnLen);
1145 if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
1146 if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
1147 return aM;
1148 }
@@ -1154,10 +1151,12 @@
1151 pToFree = 0;
1152 a = aBuf;
1153 }else{
1154 a = pToFree = fossil_malloc( sizeof(a[0])*(nRight+1) );
1155 }
1156 aM = fossil_malloc( (nLeft+1)*(nRight+1) );
1157
1158
1159 /* Compute the best alignment */
1160 for(i=0; i<=nRight; i++){
1161 aM[i] = 2;
1162 a[i] = i*50;
@@ -1235,22 +1234,10 @@
1234 /* Return the result */
1235 fossil_free(pToFree);
1236 return aM;
1237 }
1238
 
 
 
 
 
 
 
 
 
 
 
 
1239 /*
1240 ** Given a diff context in which the aEdit[] array has been filled
1241 ** in, compute a side-by-side diff into pOut.
1242 */
1243 static void sbsDiff(
@@ -1399,23 +1386,11 @@
1386 for(i=0; i<nr; i++){
1387 unsigned char *alignment;
1388 ma = R[r+i*3+1]; /* Lines on left but not on right */
1389 mb = R[r+i*3+2]; /* Lines on right but not on left */
1390
1391 alignment = diffBlockAlignment(&A[a], ma, &B[b], mb, diffFlags);
 
 
 
 
 
 
 
 
 
 
 
 
1392 for(j=0; ma+mb>0; j++){
1393 if( alignment[j]==1 ){
1394 /* Delete one line from the left */
1395 sbsWriteLineno(&s, a, SBS_LNA);
1396 s.a[0].iStart = 0;
@@ -1684,31 +1659,49 @@
1659 for(i=0; i<nr; i++){
1660 unsigned char *alignment;
1661 ma = R[r+i*3+1]; /* Lines on left but not on right */
1662 mb = R[r+i*3+2]; /* Lines on right but not on left */
1663
1664 alignment = diffBlockAlignment(&A[a], ma, &B[b], mb, diffFlags);
1665 for(j=0; ma+mb>0; j++){
1666 switch( alignment[j] ){
1667 case 1: {
1668 /* Delete one line from the left */
1669 pBuilder->xDelete(pBuilder, &A[a]);
1670 ma--;
1671 a++;
1672 break;
1673 }
1674 case 2: {
1675 /* Insert one line on the right */
1676 pBuilder->xInsert(pBuilder, &B[b]);
1677 assert( mb>0 );
1678 mb--;
1679 b++;
1680 break;
1681 }
1682 case 3: {
1683 /* The left line is changed into the right line */
1684 pBuilder->xEdit(pBuilder, &A[a], &B[b]);
1685 assert( ma>0 && mb>0 );
1686 ma--;
1687 mb--;
1688 a++;
1689 b++;
1690 break;
1691 }
1692 case 4: {
1693 /* Delete from left then separately insert on the right */
1694 pBuilder->xDelete(pBuilder, &A[a]);
1695 ma--;
1696 a++;
1697 pBuilder->xInsert(pBuilder, &B[b]);
1698 assert( mb>0 );
1699 mb--;
1700 b++;
1701 break;
1702 }
1703 }
1704 }
1705 fossil_free(alignment);
1706 if( i<nr-1 ){
1707 m = R[r+i*3+3];
1708

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button