Fossil SCM

More compact representation of a left/right rewrite on side-by-side diffs.

drh 2012-12-15 01:17 UTC trunk
Commit 233c4975a82cf895c49794deedbd989256c87fc7
Parent 52db049b8922fae…
1 file changed +42 -12
~ src/diff.c
M src/diff.c
+42 -12
--- src/diff.c
+++ src/diff.c
@@ -1043,13 +1043,14 @@
10431043
 **
10441044
 ** The return value is a buffer of unsigned characters, obtained from
10451045
 ** fossil_malloc(). (The caller needs to free the return value using
10461046
 ** fossil_free().) Entries in the returned array have values as follows:
10471047
 **
1048
-** 1. Delete the next line of pLeft.
1049
-** 2. Insert the next line of pRight.
1050
-** 3... The next line of pLeft changes into the next line of pRight.
1048
+** 1. Delete the next line of pLeft.
1049
+** 2. Insert the next line of pRight.
1050
+** 3. The next line of pLeft changes into the next line of pRight.
1051
+** 4. Delete one line from pLeft and add one line to pRight.
10511052
 **
10521053
 ** Values larger than three indicate better matches.
10531054
 **
10541055
 ** The length of the returned array will be just large enough to cause
10551056
 ** all elements of pLeft and pRight to be consumed.
@@ -1068,10 +1069,11 @@
10681069
 int *a; /* One row of the Wagner matrix */
10691070
 int *pToFree; /* Space that needs to be freed */
10701071
 unsigned char *aM; /* Wagner result matrix */
10711072
 int nMatch, iMatch; /* Number of matching lines and match score */
10721073
 int mnLen; /* MIN(nLeft, nRight) */
1074
+ int mxLen; /* MAX(nLeft, nRight) */
10731075
 int aBuf[100]; /* Stack space for a[] if nRight not to big */
10741076
10751077
 aM = fossil_malloc( (nLeft+1)*(nRight+1) );
10761078
 if( nLeft==0 ){
10771079
 memset(aM, 2, nRight);
@@ -1082,13 +1084,15 @@
10821084
 return aM;
10831085
 }
10841086
10851087
 /* This algorithm is O(N**2). So if N is too big, bail out with a
10861088
 ** simple (but stupid and ugly) result that doesn't take too long. */
1089
+ mnLen = nLeft<nRight ? nLeft : nRight;
10871090
 if( nLeft*nRight>100000 ){
1088
- memset(aM, 2, nRight);
1089
- memset(aM+nRight, 1, nLeft);
1091
+ memset(aM, 4, mnLen);
1092
+ if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
1093
+ if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
10901094
 return aM;
10911095
 }
10921096
10931097
 if( nRight < (sizeof(aBuf)/sizeof(aBuf[0]))-1 ){
10941098
 pToFree = 0;
@@ -1131,24 +1135,26 @@
11311135
 i = nRight;
11321136
 j = nLeft;
11331137
 k = (nRight+1)*(nLeft+1)-1;
11341138
 nMatch = iMatch = 0;
11351139
 while( i+j>0 ){
1136
- unsigned char c = aM[k--];
1140
+ unsigned char c = aM[k];
11371141
 if( c>=3 ){
11381142
 assert( i>0 && j>0 );
11391143
 i--;
11401144
 j--;
11411145
 nMatch++;
11421146
 iMatch += (c>>2);
1147
+ aM[k] = 3;
11431148
 }else if( c==2 ){
11441149
 assert( i>0 );
11451150
 i--;
11461151
 }else{
11471152
 assert( j>0 );
11481153
 j--;
11491154
 }
1155
+ k--;
11501156
 aM[k] = aM[j*(nRight+1)+i];
11511157
 }
11521158
 k++;
11531159
 i = (nRight+1)*(nLeft+1) - k;
11541160
 memmove(aM, &aM[k], i);
@@ -1161,14 +1167,15 @@
11611167
 ** by all of the left side deleted.
11621168
 **
11631169
 ** The coefficients for conditions (1) and (2) above are determined by
11641170
 ** experimentation.
11651171
 */
1166
- mnLen = nLeft>nRight ? nLeft : nRight;
1167
- if( i*4>mnLen*5 && (nMatch==0 || iMatch/nMatch>15) ){
1168
- memset(aM, 2, nRight);
1169
- memset(aM+nRight, 1, nLeft);
1172
+ mxLen = nLeft>nRight ? nLeft : nRight;
1173
+ if( i*4>mxLen*5 && (nMatch==0 || iMatch/nMatch>15) ){
1174
+ memset(aM, 4, mnLen);
1175
+ if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
1176
+ if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
11701177
 }
11711178
11721179
 /* Return the result */
11731180
 fossil_free(pToFree);
11741181
 return aM;
@@ -1302,10 +1309,11 @@
13021309
 }
13031310
13041311
 alignment = sbsAlignment(&A[a], ma, &B[b], mb);
13051312
 for(j=0; ma+mb>0; j++){
13061313
 if( alignment[j]==1 ){
1314
+ /* Delete one line from the left */
13071315
 s.n = 0;
13081316
 sbsWriteLineno(&s, a);
13091317
 s.iStart = 0;
13101318
 s.zStart = "<span class=\"diffrm\">";
13111319
 s.iEnd = s.width;
@@ -1317,20 +1325,22 @@
13171325
 }
13181326
 blob_append(pOut, s.zLine, s.n);
13191327
 assert( ma>0 );
13201328
 ma--;
13211329
 a++;
1322
- }else if( alignment[j]>=3 ){
1330
+ }else if( alignment[j]==3 ){
1331
+ /* The left line is changed into the right line */
13231332
 s.n = 0;
13241333
 sbsWriteLineChange(&s, &A[a], a, &B[b], b);
13251334
 blob_append(pOut, s.zLine, s.n);
13261335
 assert( ma>0 && mb>0 );
13271336
 ma--;
13281337
 mb--;
13291338
 a++;
13301339
 b++;
1331
- }else{
1340
+ }else if( alignment[j]==2 ){
1341
+ /* Insert one line on the right */
13321342
 s.n = 0;
13331343
 sbsWriteSpace(&s, width + 7);
13341344
 if( escHtml ){
13351345
 sbsWrite(&s, " &gt; ", 6);
13361346
 }else{
@@ -1343,11 +1353,31 @@
13431353
 sbsWriteText(&s, &B[b], SBS_NEWLINE);
13441354
 blob_append(pOut, s.zLine, s.n);
13451355
 assert( mb>0 );
13461356
 mb--;
13471357
 b++;
1358
+ }else{
1359
+ /* Delete from the left and insert on the right */
1360
+ s.n = 0;
1361
+ sbsWriteLineno(&s, a);
1362
+ s.iStart = 0;
1363
+ s.zStart = "<span class=\"diffrm\">";
1364
+ s.iEnd = s.width;
1365
+ sbsWriteText(&s, &A[a], SBS_PAD);
1366
+ sbsWrite(&s, " | ", 3);
1367
+ sbsWriteLineno(&s, b);
1368
+ s.iStart = 0;
1369
+ s.zStart = "<span class=\"diffadd\">";
1370
+ s.iEnd = s.width;
1371
+ sbsWriteText(&s, &B[b], SBS_NEWLINE);
1372
+ blob_append(pOut, s.zLine, s.n);
1373
+ ma--;
1374
+ mb--;
1375
+ a++;
1376
+ b++;
13481377
 }
1378
+
13491379
 }
13501380
 fossil_free(alignment);
13511381
 if( i<nr-1 ){
13521382
 m = R[r+i*3+3];
13531383
 for(j=0; j<m; j++){
13541384
--- src/diff.c
+++ src/diff.c
@@ -1043,13 +1043,14 @@
1043 **
1044 ** The return value is a buffer of unsigned characters, obtained from
1045 ** fossil_malloc(). (The caller needs to free the return value using
1046 ** fossil_free().) Entries in the returned array have values as follows:
1047 **
1048 ** 1. Delete the next line of pLeft.
1049 ** 2. Insert the next line of pRight.
1050 ** 3... The next line of pLeft changes into the next line of pRight.
 
1051 **
1052 ** Values larger than three indicate better matches.
1053 **
1054 ** The length of the returned array will be just large enough to cause
1055 ** all elements of pLeft and pRight to be consumed.
@@ -1068,10 +1069,11 @@
1068 int *a; /* One row of the Wagner matrix */
1069 int *pToFree; /* Space that needs to be freed */
1070 unsigned char *aM; /* Wagner result matrix */
1071 int nMatch, iMatch; /* Number of matching lines and match score */
1072 int mnLen; /* MIN(nLeft, nRight) */
 
1073 int aBuf[100]; /* Stack space for a[] if nRight not to big */
1074
1075 aM = fossil_malloc( (nLeft+1)*(nRight+1) );
1076 if( nLeft==0 ){
1077 memset(aM, 2, nRight);
@@ -1082,13 +1084,15 @@
1082 return aM;
1083 }
1084
1085 /* This algorithm is O(N**2). So if N is too big, bail out with a
1086 ** simple (but stupid and ugly) result that doesn't take too long. */
 
1087 if( nLeft*nRight>100000 ){
1088 memset(aM, 2, nRight);
1089 memset(aM+nRight, 1, nLeft);
 
1090 return aM;
1091 }
1092
1093 if( nRight < (sizeof(aBuf)/sizeof(aBuf[0]))-1 ){
1094 pToFree = 0;
@@ -1131,24 +1135,26 @@
1131 i = nRight;
1132 j = nLeft;
1133 k = (nRight+1)*(nLeft+1)-1;
1134 nMatch = iMatch = 0;
1135 while( i+j>0 ){
1136 unsigned char c = aM[k--];
1137 if( c>=3 ){
1138 assert( i>0 && j>0 );
1139 i--;
1140 j--;
1141 nMatch++;
1142 iMatch += (c>>2);
 
1143 }else if( c==2 ){
1144 assert( i>0 );
1145 i--;
1146 }else{
1147 assert( j>0 );
1148 j--;
1149 }
 
1150 aM[k] = aM[j*(nRight+1)+i];
1151 }
1152 k++;
1153 i = (nRight+1)*(nLeft+1) - k;
1154 memmove(aM, &aM[k], i);
@@ -1161,14 +1167,15 @@
1161 ** by all of the left side deleted.
1162 **
1163 ** The coefficients for conditions (1) and (2) above are determined by
1164 ** experimentation.
1165 */
1166 mnLen = nLeft>nRight ? nLeft : nRight;
1167 if( i*4>mnLen*5 && (nMatch==0 || iMatch/nMatch>15) ){
1168 memset(aM, 2, nRight);
1169 memset(aM+nRight, 1, nLeft);
 
1170 }
1171
1172 /* Return the result */
1173 fossil_free(pToFree);
1174 return aM;
@@ -1302,10 +1309,11 @@
1302 }
1303
1304 alignment = sbsAlignment(&A[a], ma, &B[b], mb);
1305 for(j=0; ma+mb>0; j++){
1306 if( alignment[j]==1 ){
 
1307 s.n = 0;
1308 sbsWriteLineno(&s, a);
1309 s.iStart = 0;
1310 s.zStart = "<span class=\"diffrm\">";
1311 s.iEnd = s.width;
@@ -1317,20 +1325,22 @@
1317 }
1318 blob_append(pOut, s.zLine, s.n);
1319 assert( ma>0 );
1320 ma--;
1321 a++;
1322 }else if( alignment[j]>=3 ){
 
1323 s.n = 0;
1324 sbsWriteLineChange(&s, &A[a], a, &B[b], b);
1325 blob_append(pOut, s.zLine, s.n);
1326 assert( ma>0 && mb>0 );
1327 ma--;
1328 mb--;
1329 a++;
1330 b++;
1331 }else{
 
1332 s.n = 0;
1333 sbsWriteSpace(&s, width + 7);
1334 if( escHtml ){
1335 sbsWrite(&s, " &gt; ", 6);
1336 }else{
@@ -1343,11 +1353,31 @@
1343 sbsWriteText(&s, &B[b], SBS_NEWLINE);
1344 blob_append(pOut, s.zLine, s.n);
1345 assert( mb>0 );
1346 mb--;
1347 b++;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1348 }
 
1349 }
1350 fossil_free(alignment);
1351 if( i<nr-1 ){
1352 m = R[r+i*3+3];
1353 for(j=0; j<m; j++){
1354
--- src/diff.c
+++ src/diff.c
@@ -1043,13 +1043,14 @@
1043 **
1044 ** The return value is a buffer of unsigned characters, obtained from
1045 ** fossil_malloc(). (The caller needs to free the return value using
1046 ** fossil_free().) Entries in the returned array have values as follows:
1047 **
1048 ** 1. Delete the next line of pLeft.
1049 ** 2. Insert the next line of pRight.
1050 ** 3. The next line of pLeft changes into the next line of pRight.
1051 ** 4. Delete one line from pLeft and add one line to pRight.
1052 **
1053 ** Values larger than three indicate better matches.
1054 **
1055 ** The length of the returned array will be just large enough to cause
1056 ** all elements of pLeft and pRight to be consumed.
@@ -1068,10 +1069,11 @@
1069 int *a; /* One row of the Wagner matrix */
1070 int *pToFree; /* Space that needs to be freed */
1071 unsigned char *aM; /* Wagner result matrix */
1072 int nMatch, iMatch; /* Number of matching lines and match score */
1073 int mnLen; /* MIN(nLeft, nRight) */
1074 int mxLen; /* MAX(nLeft, nRight) */
1075 int aBuf[100]; /* Stack space for a[] if nRight not to big */
1076
1077 aM = fossil_malloc( (nLeft+1)*(nRight+1) );
1078 if( nLeft==0 ){
1079 memset(aM, 2, nRight);
@@ -1082,13 +1084,15 @@
1084 return aM;
1085 }
1086
1087 /* This algorithm is O(N**2). So if N is too big, bail out with a
1088 ** simple (but stupid and ugly) result that doesn't take too long. */
1089 mnLen = nLeft<nRight ? nLeft : nRight;
1090 if( nLeft*nRight>100000 ){
1091 memset(aM, 4, mnLen);
1092 if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
1093 if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
1094 return aM;
1095 }
1096
1097 if( nRight < (sizeof(aBuf)/sizeof(aBuf[0]))-1 ){
1098 pToFree = 0;
@@ -1131,24 +1135,26 @@
1135 i = nRight;
1136 j = nLeft;
1137 k = (nRight+1)*(nLeft+1)-1;
1138 nMatch = iMatch = 0;
1139 while( i+j>0 ){
1140 unsigned char c = aM[k];
1141 if( c>=3 ){
1142 assert( i>0 && j>0 );
1143 i--;
1144 j--;
1145 nMatch++;
1146 iMatch += (c>>2);
1147 aM[k] = 3;
1148 }else if( c==2 ){
1149 assert( i>0 );
1150 i--;
1151 }else{
1152 assert( j>0 );
1153 j--;
1154 }
1155 k--;
1156 aM[k] = aM[j*(nRight+1)+i];
1157 }
1158 k++;
1159 i = (nRight+1)*(nLeft+1) - k;
1160 memmove(aM, &aM[k], i);
@@ -1161,14 +1167,15 @@
1167 ** by all of the left side deleted.
1168 **
1169 ** The coefficients for conditions (1) and (2) above are determined by
1170 ** experimentation.
1171 */
1172 mxLen = nLeft>nRight ? nLeft : nRight;
1173 if( i*4>mxLen*5 && (nMatch==0 || iMatch/nMatch>15) ){
1174 memset(aM, 4, mnLen);
1175 if( nLeft>mnLen ) memset(aM+mnLen, 1, nLeft-mnLen);
1176 if( nRight>mnLen ) memset(aM+mnLen, 2, nRight-mnLen);
1177 }
1178
1179 /* Return the result */
1180 fossil_free(pToFree);
1181 return aM;
@@ -1302,10 +1309,11 @@
1309 }
1310
1311 alignment = sbsAlignment(&A[a], ma, &B[b], mb);
1312 for(j=0; ma+mb>0; j++){
1313 if( alignment[j]==1 ){
1314 /* Delete one line from the left */
1315 s.n = 0;
1316 sbsWriteLineno(&s, a);
1317 s.iStart = 0;
1318 s.zStart = "<span class=\"diffrm\">";
1319 s.iEnd = s.width;
@@ -1317,20 +1325,22 @@
1325 }
1326 blob_append(pOut, s.zLine, s.n);
1327 assert( ma>0 );
1328 ma--;
1329 a++;
1330 }else if( alignment[j]==3 ){
1331 /* The left line is changed into the right line */
1332 s.n = 0;
1333 sbsWriteLineChange(&s, &A[a], a, &B[b], b);
1334 blob_append(pOut, s.zLine, s.n);
1335 assert( ma>0 && mb>0 );
1336 ma--;
1337 mb--;
1338 a++;
1339 b++;
1340 }else if( alignment[j]==2 ){
1341 /* Insert one line on the right */
1342 s.n = 0;
1343 sbsWriteSpace(&s, width + 7);
1344 if( escHtml ){
1345 sbsWrite(&s, " &gt; ", 6);
1346 }else{
@@ -1343,11 +1353,31 @@
1353 sbsWriteText(&s, &B[b], SBS_NEWLINE);
1354 blob_append(pOut, s.zLine, s.n);
1355 assert( mb>0 );
1356 mb--;
1357 b++;
1358 }else{
1359 /* Delete from the left and insert on the right */
1360 s.n = 0;
1361 sbsWriteLineno(&s, a);
1362 s.iStart = 0;
1363 s.zStart = "<span class=\"diffrm\">";
1364 s.iEnd = s.width;
1365 sbsWriteText(&s, &A[a], SBS_PAD);
1366 sbsWrite(&s, " | ", 3);
1367 sbsWriteLineno(&s, b);
1368 s.iStart = 0;
1369 s.zStart = "<span class=\"diffadd\">";
1370 s.iEnd = s.width;
1371 sbsWriteText(&s, &B[b], SBS_NEWLINE);
1372 blob_append(pOut, s.zLine, s.n);
1373 ma--;
1374 mb--;
1375 a++;
1376 b++;
1377 }
1378
1379 }
1380 fossil_free(alignment);
1381 if( i<nr-1 ){
1382 m = R[r+i*3+3];
1383 for(j=0; j<m; j++){
1384

Keyboard Shortcuts

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