Fossil SCM

Demonstrate the concept of a generic DiffBuilder object.

drh 2021-08-29 22:55 diff-color-enhancements
Commit 6e8d87b398f52d7c3bfc5e165f5e0b01316aec358d77488b21dbe45c00acda6f
Parent e696aa705c00a87…
2 files changed +233 -7 +7 -3
~ src/diff.c ~ src/diffcmd.c
M src/diff.c
+233 -7
--- src/diff.c
+++ src/diff.c
@@ -44,10 +44,11 @@
4444
 #define DIFF_NOTTOOBIG (((u64)0x08)<<32) /* Only display if not too big */
4545
 #define DIFF_STRIP_EOLCR (((u64)0x10)<<32) /* Strip trailing CR */
4646
 #define DIFF_SLOW_SBS (((u64)0x20)<<32) /* Better but slower side-by-side */
4747
 #define DIFF_WEBPAGE (((u64)0x40)<<32) /* Complete webpage */
4848
 #define DIFF_BROWSER (((u64)0x80)<<32) /* The --browser option */
49
+#define DIFF_DEBUG1 (((u64)0x100000)<<32) /* Debugging diff output */
4950
5051
 /*
5152
 ** These error messages are shared in multiple locations. They are defined
5253
 ** here for consistency.
5354
 */
@@ -279,13 +280,13 @@
279280
 /*
280281
 ** Return true if the regular expression *pRe matches any of the
281282
 ** N dlines
282283
 */
283284
 static int re_dline_match(
284
- ReCompiled *pRe, /* The regular expression to be matched */
285
- DLine *aDLine, /* First of N DLines to compare against */
286
- int N /* Number of DLines to check */
285
+ ReCompiled *pRe, /* The regular expression to be matched */
286
+ const DLine *aDLine, /* First of N DLines to compare against */
287
+ int N /* Number of DLines to check */
287288
 ){
288289
 while( N-- ){
289290
 if( re_match(pRe, (const unsigned char *)aDLine->z, LENGTH(aDLine)) ){
290291
 return 1;
291292
 }
@@ -1034,11 +1035,11 @@
10341035
 ** (1) Remove leading and trailing whitespace.
10351036
 ** (2) Truncate both strings to at most 250 characters
10361037
 ** (3) Find the length of the longest common subsequence
10371038
 ** (4) Longer common subsequences yield lower scores.
10381039
 */
1039
-static int match_dline(DLine *pA, DLine *pB){
1040
+static int match_dline(const DLine *pA, const DLine *pB){
10401041
 const char *zA; /* Left string */
10411042
 const char *zB; /* right string */
10421043
 int nA; /* Bytes in zA[] */
10431044
 int nB; /* Bytes in zB[] */
10441045
 int avg; /* Average length of A and B */
@@ -1113,13 +1114,13 @@
11131114
 ** each other. Insertion and deletion costs are 50. Match costs
11141115
 ** are between 0 and 100 where 0 is a perfect match 100 is a complete
11151116
 ** mismatch.
11161117
 */
11171118
 static unsigned char *sbsAlignment(
1118
- DLine *aLeft, int nLeft, /* Text on the left */
1119
- DLine *aRight, int nRight, /* Text on the right */
1120
- u64 diffFlags /* Flags passed into the original diff */
1119
+ const DLine *aLeft, int nLeft, /* Text on the left */
1120
+ const DLine *aRight, int nRight, /* Text on the right */
1121
+ u64 diffFlags /* Flags passed into the original diff */
11211122
 ){
11221123
 int i, j, k; /* Loop counters */
11231124
 int *a; /* One row of the Wagner matrix */
11241125
 int *pToFree; /* Space that needs to be freed */
11251126
 unsigned char *aM; /* Wagner result matrix */
@@ -1233,19 +1234,21 @@
12331234
 /* Return the result */
12341235
 fossil_free(pToFree);
12351236
 return aM;
12361237
 }
12371238
1239
+#if 0 /* not used */
12381240
 /*
12391241
 ** R[] is an array of six integer, two COPY/DELETE/INSERT triples for a
12401242
 ** pair of adjacent differences. Return true if the gap between these
12411243
 ** two differences is so small that they should be rendered as a single
12421244
 ** edit.
12431245
 */
12441246
 static int smallGap(int *R){
12451247
 return R[3]<=2 || R[3]<=(R[1]+R[2]+R[4]+R[5])/8;
12461248
 }
1249
+#endif
12471250
12481251
 /*
12491252
 ** Given a diff context in which the aEdit[] array has been filled
12501253
 ** in, compute a side-by-side diff into pOut.
12511254
 */
@@ -1395,19 +1398,21 @@
13951398
 for(i=0; i<nr; i++){
13961399
 unsigned char *alignment;
13971400
 ma = R[r+i*3+1]; /* Lines on left but not on right */
13981401
 mb = R[r+i*3+2]; /* Lines on right but not on left */
13991402
1403
+#if 0 /* not used */
14001404
 /* If the gap between the current diff and then next diff within the
14011405
 ** same block is not too great, then render them as if they are a
14021406
 ** single diff. */
14031407
 while( i<nr-1 && smallGap(&R[r+i*3]) ){
14041408
 i++;
14051409
 m = R[r+i*3];
14061410
 ma += R[r+i*3+1] + m;
14071411
 mb += R[r+i*3+2] + m;
14081412
 }
1413
+#endif
14091414
14101415
 alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
14111416
 for(j=0; ma+mb>0; j++){
14121417
 if( alignment[j]==1 ){
14131418
 /* Delete one line from the left */
@@ -1505,10 +1510,227 @@
15051510
 blob_reset(s.apCols[i]);
15061511
 }
15071512
 blob_append(pOut, "</tr></table>\n", -1);
15081513
 }
15091514
 }
1515
+
1516
+/*
1517
+** This is an abstract superclass for an object that accepts difference
1518
+** lines and formats them for display. Subclasses of this object format
1519
+** the diff output in different ways.
1520
+*/
1521
+typedef struct DiffBuilder DiffBuilder;
1522
+struct DiffBuilder {
1523
+ void (*xSkip)(DiffBuilder*, unsigned int);
1524
+ void (*xCommon)(DiffBuilder*,const DLine*);
1525
+ void (*xInsert)(DiffBuilder*,const DLine*);
1526
+ void (*xDelete)(DiffBuilder*,const DLine*);
1527
+ void (*xEdit)(DiffBuilder*,const DLine*,const DLine*);
1528
+ void (*xEnd)(DiffBuilder*);
1529
+ unsigned int lnLeft; /* Lines seen on the left (delete) side */
1530
+ unsigned int lnRight; /* Lines seen on the right (insert) side */
1531
+ Blob *pOut; /* Output blob */
1532
+ /* Subclass add additional fields */
1533
+};
1534
+
1535
+/************************* DiffBuilderDebug ********************************/
1536
+static void dfdebugSkip(DiffBuilder *p, unsigned int n){
1537
+ fossil_print("SKIP %d (%d..%d left and %d..%d right)\n",
1538
+ n, p->lnLeft+1, p->lnLeft+n, p->lnRight+1, p->lnRight+n);
1539
+ p->lnLeft += n;
1540
+ p->lnRight += n;
1541
+}
1542
+static void dfdebugCommon(DiffBuilder *p, const DLine *pLine){
1543
+ p->lnLeft++;
1544
+ p->lnRight++;
1545
+ fossil_print("COMMON %8u %8u %.*s\n",
1546
+ p->lnLeft, p->lnRight, (int)pLine->n, pLine->z);
1547
+}
1548
+static void dfdebugInsert(DiffBuilder *p, const DLine *pLine){
1549
+ p->lnRight++;
1550
+ fossil_print("RIGHT %8d %.*s\n",
1551
+ p->lnRight, (int)pLine->n, pLine->z);
1552
+}
1553
+static void dfdebugDelete(DiffBuilder *p, const DLine *pLine){
1554
+ p->lnLeft++;
1555
+ fossil_print("LEFT %8u %.*s\n",
1556
+ p->lnLeft, (int)pLine->n, pLine->z);
1557
+}
1558
+static void dfdebugEdit(DiffBuilder *p, const DLine *pX, const DLine *pY){
1559
+ p->lnLeft++;
1560
+ p->lnRight++;
1561
+ fossil_print("EDIT %8u %.*s\n %8u %.*s\n",
1562
+ p->lnLeft, (int)pX->n, pX->z, p->lnRight, (int)pY->n, pY->z);
1563
+}
1564
+static void dfdebugEnd(DiffBuilder *p){
1565
+ fossil_print("END with %u lines left and %u lines right\n",
1566
+ p->lnLeft, p->lnRight);
1567
+ fossil_free(p);
1568
+}
1569
+static DiffBuilder *dfdebugNew(void){
1570
+ DiffBuilder *p = fossil_malloc(sizeof(*p));
1571
+ p->xSkip = dfdebugSkip;
1572
+ p->xCommon = dfdebugCommon;
1573
+ p->xInsert = dfdebugInsert;
1574
+ p->xDelete = dfdebugDelete;
1575
+ p->xEdit = dfdebugEdit;
1576
+ p->xEnd = dfdebugEnd;
1577
+ p->lnLeft = p->lnRight = 0;
1578
+ return p;
1579
+}
1580
+/****************************************************************************/
1581
+
1582
+/*
1583
+** Format a diff using a DiffBuilder object
1584
+*/
1585
+static void formatDiff(
1586
+ DContext *p, /* The computed diff */
1587
+ ReCompiled *pRe, /* Only show changes that match this regex */
1588
+ u64 diffFlags, /* Flags controlling the diff */
1589
+ DiffBuilder *pBuilder /* The formatter object */
1590
+){
1591
+ const DLine *A; /* Left side of the diff */
1592
+ const DLine *B; /* Right side of the diff */
1593
+ unsigned int a = 0; /* Index of next line in A[] */
1594
+ unsigned int b = 0; /* Index of next line in B[] */
1595
+ const int *R; /* Array of COPY/DELETE/INSERT triples */
1596
+ unsigned int r; /* Index into R[] */
1597
+ unsigned int nr; /* Number of COPY/DELETE/INSERT triples to process */
1598
+ unsigned int mxr; /* Maximum value for r */
1599
+ unsigned int na, nb; /* Number of lines shown from A and B */
1600
+ unsigned int i, j; /* Loop counters */
1601
+ unsigned int m, ma, mb;/* Number of lines to output */
1602
+ unsigned int skip; /* Number of lines to skip */
1603
+ unsigned int nContext; /* Lines of context above and below each change */
1604
+
1605
+ nContext = diff_context_lines(diffFlags);
1606
+ A = p->aFrom;
1607
+ B = p->aTo;
1608
+ R = p->aEdit;
1609
+ mxr = p->nEdit;
1610
+ while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }
1611
+
1612
+ for(r=0; r<mxr; r += 3*nr){
1613
+ /* Figure out how many triples to show in a single block */
1614
+ for(nr=1; R[r+nr*3]>0 && R[r+nr*3]<nContext*2; nr++){}
1615
+
1616
+ /* If there is a regex, skip this block (generate no diff output)
1617
+ ** if the regex matches or does not match both insert and delete.
1618
+ ** Only display the block if one side matches but the other side does
1619
+ ** not.
1620
+ */
1621
+ if( pRe ){
1622
+ int hideBlock = 1;
1623
+ int xa = a, xb = b;
1624
+ for(i=0; hideBlock && i<nr; i++){
1625
+ int c1, c2;
1626
+ xa += R[r+i*3];
1627
+ xb += R[r+i*3];
1628
+ c1 = re_dline_match(pRe, &A[xa], R[r+i*3+1]);
1629
+ c2 = re_dline_match(pRe, &B[xb], R[r+i*3+2]);
1630
+ hideBlock = c1==c2;
1631
+ xa += R[r+i*3+1];
1632
+ xb += R[r+i*3+2];
1633
+ }
1634
+ if( hideBlock ){
1635
+ a = xa;
1636
+ b = xb;
1637
+ continue;
1638
+ }
1639
+ }
1640
+
1641
+ /* For the current block comprising nr triples, figure out
1642
+ ** how many lines of A and B are to be displayed
1643
+ */
1644
+ if( R[r]>nContext ){
1645
+ na = nb = nContext;
1646
+ skip = R[r] - nContext;
1647
+ }else{
1648
+ na = nb = R[r];
1649
+ skip = 0;
1650
+ }
1651
+ for(i=0; i<nr; i++){
1652
+ na += R[r+i*3+1];
1653
+ nb += R[r+i*3+2];
1654
+ }
1655
+ if( R[r+nr*3]>nContext ){
1656
+ na += nContext;
1657
+ nb += nContext;
1658
+ }else{
1659
+ na += R[r+nr*3];
1660
+ nb += R[r+nr*3];
1661
+ }
1662
+ for(i=1; i<nr; i++){
1663
+ na += R[r+i*3];
1664
+ nb += R[r+i*3];
1665
+ }
1666
+
1667
+ if( skip>0 ){
1668
+ pBuilder->xSkip(pBuilder, skip);
1669
+ }
1670
+
1671
+ /* Show the initial common area */
1672
+ a += skip;
1673
+ b += skip;
1674
+ m = R[r] - skip;
1675
+ for(j=0; j<m; j++){
1676
+ pBuilder->xCommon(pBuilder, &A[a+j]);
1677
+ }
1678
+ a += m;
1679
+ b += m;
1680
+
1681
+ /* Show the differences */
1682
+ for(i=0; i<nr; i++){
1683
+ unsigned char *alignment;
1684
+ ma = R[r+i*3+1]; /* Lines on left but not on right */
1685
+ mb = R[r+i*3+2]; /* Lines on right but not on left */
1686
+
1687
+ alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1688
+ for(j=0; ma+mb>0; j++){
1689
+ if( alignment[j]==1 ){
1690
+ /* Delete one line from the left */
1691
+ pBuilder->xDelete(pBuilder, &A[a]);
1692
+ ma--;
1693
+ a++;
1694
+ }else if( alignment[j]==2 ){
1695
+ /* Insert one line on the right */
1696
+ pBuilder->xInsert(pBuilder, &B[b]);
1697
+ assert( mb>0 );
1698
+ mb--;
1699
+ b++;
1700
+ }else{
1701
+ /* The left line is changed into the right line */
1702
+ pBuilder->xEdit(pBuilder, &A[a], &B[b]);
1703
+ assert( ma>0 && mb>0 );
1704
+ ma--;
1705
+ mb--;
1706
+ a++;
1707
+ b++;
1708
+ }
1709
+ }
1710
+ fossil_free(alignment);
1711
+ if( i<nr-1 ){
1712
+ m = R[r+i*3+3];
1713
+ for(j=0; j<m; j++){
1714
+ pBuilder->xCommon(pBuilder, &A[a+j]);
1715
+ }
1716
+ b += m;
1717
+ a += m;
1718
+ }
1719
+ }
1720
+
1721
+ /* Show the final common area */
1722
+ assert( nr==i );
1723
+ m = R[r+nr*3];
1724
+ if( m>nContext ) m = nContext;
1725
+ for(j=0; j<m; j++){
1726
+ pBuilder->xCommon(pBuilder, &A[a+j]);
1727
+ }
1728
+ }
1729
+ pBuilder->xEnd(pBuilder);
1730
+}
1731
+
15101732
15111733
 /*
15121734
 ** Compute the optimal longest common subsequence (LCS) using an
15131735
 ** exhaustive search. This version of the LCS is only used for
15141736
 ** shorter input strings since runtime is O(N*N) where N is the
@@ -2041,10 +2263,13 @@
20412263
 g.diffCnt[0]++;
20422264
 blob_appendf(pOut, "%10d %10d", nIns, nDel);
20432265
 }
20442266
 }else if( diffFlags & DIFF_SIDEBYSIDE ){
20452267
 sbsDiff(&c, pOut, pRe, diffFlags);
2268
+ }else if( diffFlags & DIFF_DEBUG1 ){
2269
+ DiffBuilder *pBuilder = dfdebugNew();
2270
+ formatDiff(&c, pRe, diffFlags, pBuilder);
20462271
 }else{
20472272
 contextDiff(&c, pOut, pRe, diffFlags);
20482273
 }
20492274
 fossil_free(c.aFrom);
20502275
 fossil_free(c.aTo);
@@ -2176,10 +2401,11 @@
21762401
 if( zRe ){
21772402
 const char *zErr = re_compile(&pRe, zRe, 0);
21782403
 if( zErr ) fossil_fatal("regex error: %s", zErr);
21792404
 }
21802405
 diffFlag = diff_options();
2406
+ if( find_option("debug",0,0)!=0 ) diffFlag |= DIFF_DEBUG1;
21812407
 verify_all_options();
21822408
 if( g.argc!=4 ) usage("FILE1 FILE2");
21832409
 blob_zero(&out);
21842410
 diff_begin(diffFlag);
21852411
 diff_print_filenames(g.argv[2], g.argv[3], diffFlag, &out);
21862412
--- src/diff.c
+++ src/diff.c
@@ -44,10 +44,11 @@
44 #define DIFF_NOTTOOBIG (((u64)0x08)<<32) /* Only display if not too big */
45 #define DIFF_STRIP_EOLCR (((u64)0x10)<<32) /* Strip trailing CR */
46 #define DIFF_SLOW_SBS (((u64)0x20)<<32) /* Better but slower side-by-side */
47 #define DIFF_WEBPAGE (((u64)0x40)<<32) /* Complete webpage */
48 #define DIFF_BROWSER (((u64)0x80)<<32) /* The --browser option */
 
49
50 /*
51 ** These error messages are shared in multiple locations. They are defined
52 ** here for consistency.
53 */
@@ -279,13 +280,13 @@
279 /*
280 ** Return true if the regular expression *pRe matches any of the
281 ** N dlines
282 */
283 static int re_dline_match(
284 ReCompiled *pRe, /* The regular expression to be matched */
285 DLine *aDLine, /* First of N DLines to compare against */
286 int N /* Number of DLines to check */
287 ){
288 while( N-- ){
289 if( re_match(pRe, (const unsigned char *)aDLine->z, LENGTH(aDLine)) ){
290 return 1;
291 }
@@ -1034,11 +1035,11 @@
1034 ** (1) Remove leading and trailing whitespace.
1035 ** (2) Truncate both strings to at most 250 characters
1036 ** (3) Find the length of the longest common subsequence
1037 ** (4) Longer common subsequences yield lower scores.
1038 */
1039 static int match_dline(DLine *pA, DLine *pB){
1040 const char *zA; /* Left string */
1041 const char *zB; /* right string */
1042 int nA; /* Bytes in zA[] */
1043 int nB; /* Bytes in zB[] */
1044 int avg; /* Average length of A and B */
@@ -1113,13 +1114,13 @@
1113 ** each other. Insertion and deletion costs are 50. Match costs
1114 ** are between 0 and 100 where 0 is a perfect match 100 is a complete
1115 ** mismatch.
1116 */
1117 static unsigned char *sbsAlignment(
1118 DLine *aLeft, int nLeft, /* Text on the left */
1119 DLine *aRight, int nRight, /* Text on the right */
1120 u64 diffFlags /* Flags passed into the original diff */
1121 ){
1122 int i, j, k; /* Loop counters */
1123 int *a; /* One row of the Wagner matrix */
1124 int *pToFree; /* Space that needs to be freed */
1125 unsigned char *aM; /* Wagner result matrix */
@@ -1233,19 +1234,21 @@
1233 /* Return the result */
1234 fossil_free(pToFree);
1235 return aM;
1236 }
1237
 
1238 /*
1239 ** R[] is an array of six integer, two COPY/DELETE/INSERT triples for a
1240 ** pair of adjacent differences. Return true if the gap between these
1241 ** two differences is so small that they should be rendered as a single
1242 ** edit.
1243 */
1244 static int smallGap(int *R){
1245 return R[3]<=2 || R[3]<=(R[1]+R[2]+R[4]+R[5])/8;
1246 }
 
1247
1248 /*
1249 ** Given a diff context in which the aEdit[] array has been filled
1250 ** in, compute a side-by-side diff into pOut.
1251 */
@@ -1395,19 +1398,21 @@
1395 for(i=0; i<nr; i++){
1396 unsigned char *alignment;
1397 ma = R[r+i*3+1]; /* Lines on left but not on right */
1398 mb = R[r+i*3+2]; /* Lines on right but not on left */
1399
 
1400 /* If the gap between the current diff and then next diff within the
1401 ** same block is not too great, then render them as if they are a
1402 ** single diff. */
1403 while( i<nr-1 && smallGap(&R[r+i*3]) ){
1404 i++;
1405 m = R[r+i*3];
1406 ma += R[r+i*3+1] + m;
1407 mb += R[r+i*3+2] + m;
1408 }
 
1409
1410 alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1411 for(j=0; ma+mb>0; j++){
1412 if( alignment[j]==1 ){
1413 /* Delete one line from the left */
@@ -1505,10 +1510,227 @@
1505 blob_reset(s.apCols[i]);
1506 }
1507 blob_append(pOut, "</tr></table>\n", -1);
1508 }
1509 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1510
1511 /*
1512 ** Compute the optimal longest common subsequence (LCS) using an
1513 ** exhaustive search. This version of the LCS is only used for
1514 ** shorter input strings since runtime is O(N*N) where N is the
@@ -2041,10 +2263,13 @@
2041 g.diffCnt[0]++;
2042 blob_appendf(pOut, "%10d %10d", nIns, nDel);
2043 }
2044 }else if( diffFlags & DIFF_SIDEBYSIDE ){
2045 sbsDiff(&c, pOut, pRe, diffFlags);
 
 
 
2046 }else{
2047 contextDiff(&c, pOut, pRe, diffFlags);
2048 }
2049 fossil_free(c.aFrom);
2050 fossil_free(c.aTo);
@@ -2176,10 +2401,11 @@
2176 if( zRe ){
2177 const char *zErr = re_compile(&pRe, zRe, 0);
2178 if( zErr ) fossil_fatal("regex error: %s", zErr);
2179 }
2180 diffFlag = diff_options();
 
2181 verify_all_options();
2182 if( g.argc!=4 ) usage("FILE1 FILE2");
2183 blob_zero(&out);
2184 diff_begin(diffFlag);
2185 diff_print_filenames(g.argv[2], g.argv[3], diffFlag, &out);
2186
--- src/diff.c
+++ src/diff.c
@@ -44,10 +44,11 @@
44 #define DIFF_NOTTOOBIG (((u64)0x08)<<32) /* Only display if not too big */
45 #define DIFF_STRIP_EOLCR (((u64)0x10)<<32) /* Strip trailing CR */
46 #define DIFF_SLOW_SBS (((u64)0x20)<<32) /* Better but slower side-by-side */
47 #define DIFF_WEBPAGE (((u64)0x40)<<32) /* Complete webpage */
48 #define DIFF_BROWSER (((u64)0x80)<<32) /* The --browser option */
49 #define DIFF_DEBUG1 (((u64)0x100000)<<32) /* Debugging diff output */
50
51 /*
52 ** These error messages are shared in multiple locations. They are defined
53 ** here for consistency.
54 */
@@ -279,13 +280,13 @@
280 /*
281 ** Return true if the regular expression *pRe matches any of the
282 ** N dlines
283 */
284 static int re_dline_match(
285 ReCompiled *pRe, /* The regular expression to be matched */
286 const DLine *aDLine, /* First of N DLines to compare against */
287 int N /* Number of DLines to check */
288 ){
289 while( N-- ){
290 if( re_match(pRe, (const unsigned char *)aDLine->z, LENGTH(aDLine)) ){
291 return 1;
292 }
@@ -1034,11 +1035,11 @@
1035 ** (1) Remove leading and trailing whitespace.
1036 ** (2) Truncate both strings to at most 250 characters
1037 ** (3) Find the length of the longest common subsequence
1038 ** (4) Longer common subsequences yield lower scores.
1039 */
1040 static int match_dline(const DLine *pA, const DLine *pB){
1041 const char *zA; /* Left string */
1042 const char *zB; /* right string */
1043 int nA; /* Bytes in zA[] */
1044 int nB; /* Bytes in zB[] */
1045 int avg; /* Average length of A and B */
@@ -1113,13 +1114,13 @@
1114 ** each other. Insertion and deletion costs are 50. Match costs
1115 ** are between 0 and 100 where 0 is a perfect match 100 is a complete
1116 ** mismatch.
1117 */
1118 static unsigned char *sbsAlignment(
1119 const DLine *aLeft, int nLeft, /* Text on the left */
1120 const DLine *aRight, int nRight, /* Text on the right */
1121 u64 diffFlags /* Flags passed into the original diff */
1122 ){
1123 int i, j, k; /* Loop counters */
1124 int *a; /* One row of the Wagner matrix */
1125 int *pToFree; /* Space that needs to be freed */
1126 unsigned char *aM; /* Wagner result matrix */
@@ -1233,19 +1234,21 @@
1234 /* Return the result */
1235 fossil_free(pToFree);
1236 return aM;
1237 }
1238
1239 #if 0 /* not used */
1240 /*
1241 ** R[] is an array of six integer, two COPY/DELETE/INSERT triples for a
1242 ** pair of adjacent differences. Return true if the gap between these
1243 ** two differences is so small that they should be rendered as a single
1244 ** edit.
1245 */
1246 static int smallGap(int *R){
1247 return R[3]<=2 || R[3]<=(R[1]+R[2]+R[4]+R[5])/8;
1248 }
1249 #endif
1250
1251 /*
1252 ** Given a diff context in which the aEdit[] array has been filled
1253 ** in, compute a side-by-side diff into pOut.
1254 */
@@ -1395,19 +1398,21 @@
1398 for(i=0; i<nr; i++){
1399 unsigned char *alignment;
1400 ma = R[r+i*3+1]; /* Lines on left but not on right */
1401 mb = R[r+i*3+2]; /* Lines on right but not on left */
1402
1403 #if 0 /* not used */
1404 /* If the gap between the current diff and then next diff within the
1405 ** same block is not too great, then render them as if they are a
1406 ** single diff. */
1407 while( i<nr-1 && smallGap(&R[r+i*3]) ){
1408 i++;
1409 m = R[r+i*3];
1410 ma += R[r+i*3+1] + m;
1411 mb += R[r+i*3+2] + m;
1412 }
1413 #endif
1414
1415 alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1416 for(j=0; ma+mb>0; j++){
1417 if( alignment[j]==1 ){
1418 /* Delete one line from the left */
@@ -1505,10 +1510,227 @@
1510 blob_reset(s.apCols[i]);
1511 }
1512 blob_append(pOut, "</tr></table>\n", -1);
1513 }
1514 }
1515
1516 /*
1517 ** This is an abstract superclass for an object that accepts difference
1518 ** lines and formats them for display. Subclasses of this object format
1519 ** the diff output in different ways.
1520 */
1521 typedef struct DiffBuilder DiffBuilder;
1522 struct DiffBuilder {
1523 void (*xSkip)(DiffBuilder*, unsigned int);
1524 void (*xCommon)(DiffBuilder*,const DLine*);
1525 void (*xInsert)(DiffBuilder*,const DLine*);
1526 void (*xDelete)(DiffBuilder*,const DLine*);
1527 void (*xEdit)(DiffBuilder*,const DLine*,const DLine*);
1528 void (*xEnd)(DiffBuilder*);
1529 unsigned int lnLeft; /* Lines seen on the left (delete) side */
1530 unsigned int lnRight; /* Lines seen on the right (insert) side */
1531 Blob *pOut; /* Output blob */
1532 /* Subclass add additional fields */
1533 };
1534
1535 /************************* DiffBuilderDebug ********************************/
1536 static void dfdebugSkip(DiffBuilder *p, unsigned int n){
1537 fossil_print("SKIP %d (%d..%d left and %d..%d right)\n",
1538 n, p->lnLeft+1, p->lnLeft+n, p->lnRight+1, p->lnRight+n);
1539 p->lnLeft += n;
1540 p->lnRight += n;
1541 }
1542 static void dfdebugCommon(DiffBuilder *p, const DLine *pLine){
1543 p->lnLeft++;
1544 p->lnRight++;
1545 fossil_print("COMMON %8u %8u %.*s\n",
1546 p->lnLeft, p->lnRight, (int)pLine->n, pLine->z);
1547 }
1548 static void dfdebugInsert(DiffBuilder *p, const DLine *pLine){
1549 p->lnRight++;
1550 fossil_print("RIGHT %8d %.*s\n",
1551 p->lnRight, (int)pLine->n, pLine->z);
1552 }
1553 static void dfdebugDelete(DiffBuilder *p, const DLine *pLine){
1554 p->lnLeft++;
1555 fossil_print("LEFT %8u %.*s\n",
1556 p->lnLeft, (int)pLine->n, pLine->z);
1557 }
1558 static void dfdebugEdit(DiffBuilder *p, const DLine *pX, const DLine *pY){
1559 p->lnLeft++;
1560 p->lnRight++;
1561 fossil_print("EDIT %8u %.*s\n %8u %.*s\n",
1562 p->lnLeft, (int)pX->n, pX->z, p->lnRight, (int)pY->n, pY->z);
1563 }
1564 static void dfdebugEnd(DiffBuilder *p){
1565 fossil_print("END with %u lines left and %u lines right\n",
1566 p->lnLeft, p->lnRight);
1567 fossil_free(p);
1568 }
1569 static DiffBuilder *dfdebugNew(void){
1570 DiffBuilder *p = fossil_malloc(sizeof(*p));
1571 p->xSkip = dfdebugSkip;
1572 p->xCommon = dfdebugCommon;
1573 p->xInsert = dfdebugInsert;
1574 p->xDelete = dfdebugDelete;
1575 p->xEdit = dfdebugEdit;
1576 p->xEnd = dfdebugEnd;
1577 p->lnLeft = p->lnRight = 0;
1578 return p;
1579 }
1580 /****************************************************************************/
1581
1582 /*
1583 ** Format a diff using a DiffBuilder object
1584 */
1585 static void formatDiff(
1586 DContext *p, /* The computed diff */
1587 ReCompiled *pRe, /* Only show changes that match this regex */
1588 u64 diffFlags, /* Flags controlling the diff */
1589 DiffBuilder *pBuilder /* The formatter object */
1590 ){
1591 const DLine *A; /* Left side of the diff */
1592 const DLine *B; /* Right side of the diff */
1593 unsigned int a = 0; /* Index of next line in A[] */
1594 unsigned int b = 0; /* Index of next line in B[] */
1595 const int *R; /* Array of COPY/DELETE/INSERT triples */
1596 unsigned int r; /* Index into R[] */
1597 unsigned int nr; /* Number of COPY/DELETE/INSERT triples to process */
1598 unsigned int mxr; /* Maximum value for r */
1599 unsigned int na, nb; /* Number of lines shown from A and B */
1600 unsigned int i, j; /* Loop counters */
1601 unsigned int m, ma, mb;/* Number of lines to output */
1602 unsigned int skip; /* Number of lines to skip */
1603 unsigned int nContext; /* Lines of context above and below each change */
1604
1605 nContext = diff_context_lines(diffFlags);
1606 A = p->aFrom;
1607 B = p->aTo;
1608 R = p->aEdit;
1609 mxr = p->nEdit;
1610 while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }
1611
1612 for(r=0; r<mxr; r += 3*nr){
1613 /* Figure out how many triples to show in a single block */
1614 for(nr=1; R[r+nr*3]>0 && R[r+nr*3]<nContext*2; nr++){}
1615
1616 /* If there is a regex, skip this block (generate no diff output)
1617 ** if the regex matches or does not match both insert and delete.
1618 ** Only display the block if one side matches but the other side does
1619 ** not.
1620 */
1621 if( pRe ){
1622 int hideBlock = 1;
1623 int xa = a, xb = b;
1624 for(i=0; hideBlock && i<nr; i++){
1625 int c1, c2;
1626 xa += R[r+i*3];
1627 xb += R[r+i*3];
1628 c1 = re_dline_match(pRe, &A[xa], R[r+i*3+1]);
1629 c2 = re_dline_match(pRe, &B[xb], R[r+i*3+2]);
1630 hideBlock = c1==c2;
1631 xa += R[r+i*3+1];
1632 xb += R[r+i*3+2];
1633 }
1634 if( hideBlock ){
1635 a = xa;
1636 b = xb;
1637 continue;
1638 }
1639 }
1640
1641 /* For the current block comprising nr triples, figure out
1642 ** how many lines of A and B are to be displayed
1643 */
1644 if( R[r]>nContext ){
1645 na = nb = nContext;
1646 skip = R[r] - nContext;
1647 }else{
1648 na = nb = R[r];
1649 skip = 0;
1650 }
1651 for(i=0; i<nr; i++){
1652 na += R[r+i*3+1];
1653 nb += R[r+i*3+2];
1654 }
1655 if( R[r+nr*3]>nContext ){
1656 na += nContext;
1657 nb += nContext;
1658 }else{
1659 na += R[r+nr*3];
1660 nb += R[r+nr*3];
1661 }
1662 for(i=1; i<nr; i++){
1663 na += R[r+i*3];
1664 nb += R[r+i*3];
1665 }
1666
1667 if( skip>0 ){
1668 pBuilder->xSkip(pBuilder, skip);
1669 }
1670
1671 /* Show the initial common area */
1672 a += skip;
1673 b += skip;
1674 m = R[r] - skip;
1675 for(j=0; j<m; j++){
1676 pBuilder->xCommon(pBuilder, &A[a+j]);
1677 }
1678 a += m;
1679 b += m;
1680
1681 /* Show the differences */
1682 for(i=0; i<nr; i++){
1683 unsigned char *alignment;
1684 ma = R[r+i*3+1]; /* Lines on left but not on right */
1685 mb = R[r+i*3+2]; /* Lines on right but not on left */
1686
1687 alignment = sbsAlignment(&A[a], ma, &B[b], mb, diffFlags);
1688 for(j=0; ma+mb>0; j++){
1689 if( alignment[j]==1 ){
1690 /* Delete one line from the left */
1691 pBuilder->xDelete(pBuilder, &A[a]);
1692 ma--;
1693 a++;
1694 }else if( alignment[j]==2 ){
1695 /* Insert one line on the right */
1696 pBuilder->xInsert(pBuilder, &B[b]);
1697 assert( mb>0 );
1698 mb--;
1699 b++;
1700 }else{
1701 /* The left line is changed into the right line */
1702 pBuilder->xEdit(pBuilder, &A[a], &B[b]);
1703 assert( ma>0 && mb>0 );
1704 ma--;
1705 mb--;
1706 a++;
1707 b++;
1708 }
1709 }
1710 fossil_free(alignment);
1711 if( i<nr-1 ){
1712 m = R[r+i*3+3];
1713 for(j=0; j<m; j++){
1714 pBuilder->xCommon(pBuilder, &A[a+j]);
1715 }
1716 b += m;
1717 a += m;
1718 }
1719 }
1720
1721 /* Show the final common area */
1722 assert( nr==i );
1723 m = R[r+nr*3];
1724 if( m>nContext ) m = nContext;
1725 for(j=0; j<m; j++){
1726 pBuilder->xCommon(pBuilder, &A[a+j]);
1727 }
1728 }
1729 pBuilder->xEnd(pBuilder);
1730 }
1731
1732
1733 /*
1734 ** Compute the optimal longest common subsequence (LCS) using an
1735 ** exhaustive search. This version of the LCS is only used for
1736 ** shorter input strings since runtime is O(N*N) where N is the
@@ -2041,10 +2263,13 @@
2263 g.diffCnt[0]++;
2264 blob_appendf(pOut, "%10d %10d", nIns, nDel);
2265 }
2266 }else if( diffFlags & DIFF_SIDEBYSIDE ){
2267 sbsDiff(&c, pOut, pRe, diffFlags);
2268 }else if( diffFlags & DIFF_DEBUG1 ){
2269 DiffBuilder *pBuilder = dfdebugNew();
2270 formatDiff(&c, pRe, diffFlags, pBuilder);
2271 }else{
2272 contextDiff(&c, pOut, pRe, diffFlags);
2273 }
2274 fossil_free(c.aFrom);
2275 fossil_free(c.aTo);
@@ -2176,10 +2401,11 @@
2401 if( zRe ){
2402 const char *zErr = re_compile(&pRe, zRe, 0);
2403 if( zErr ) fossil_fatal("regex error: %s", zErr);
2404 }
2405 diffFlag = diff_options();
2406 if( find_option("debug",0,0)!=0 ) diffFlag |= DIFF_DEBUG1;
2407 verify_all_options();
2408 if( g.argc!=4 ) usage("FILE1 FILE2");
2409 blob_zero(&out);
2410 diff_begin(diffFlag);
2411 diff_print_filenames(g.argv[2], g.argv[3], diffFlag, &out);
2412
M src/diffcmd.c
+7 -3
--- src/diffcmd.c
+++ src/diffcmd.c
@@ -128,14 +128,18 @@
128128
 }
129129
130130
 /*
131131
 ** Print the +++/--- filename lines for a diff operation.
132132
 */
133
-void diff_print_filenames(const char *zLeft, const char *zRight,
134
- u64 diffFlags, Blob *diffBlob){
133
+void diff_print_filenames(
134
+ const char *zLeft,
135
+ const char *zRight,
136
+ u64 diffFlags,
137
+ Blob *diffBlob
138
+){
135139
 char *z = 0;
136
- if( diffFlags & DIFF_BRIEF ){
140
+ if( diffFlags & (DIFF_BRIEF|DIFF_DEBUG1) ){
137141
 /* no-op */
138142
 }else if( diffFlags & DIFF_WEBPAGE ){
139143
 if( fossil_strcmp(zLeft,zRight)==0 ){
140144
 z = mprintf("<h1>%h</h1>\n", zLeft);
141145
 }else{
142146
--- src/diffcmd.c
+++ src/diffcmd.c
@@ -128,14 +128,18 @@
128 }
129
130 /*
131 ** Print the +++/--- filename lines for a diff operation.
132 */
133 void diff_print_filenames(const char *zLeft, const char *zRight,
134 u64 diffFlags, Blob *diffBlob){
 
 
 
 
135 char *z = 0;
136 if( diffFlags & DIFF_BRIEF ){
137 /* no-op */
138 }else if( diffFlags & DIFF_WEBPAGE ){
139 if( fossil_strcmp(zLeft,zRight)==0 ){
140 z = mprintf("<h1>%h</h1>\n", zLeft);
141 }else{
142
--- src/diffcmd.c
+++ src/diffcmd.c
@@ -128,14 +128,18 @@
128 }
129
130 /*
131 ** Print the +++/--- filename lines for a diff operation.
132 */
133 void diff_print_filenames(
134 const char *zLeft,
135 const char *zRight,
136 u64 diffFlags,
137 Blob *diffBlob
138 ){
139 char *z = 0;
140 if( diffFlags & (DIFF_BRIEF|DIFF_DEBUG1) ){
141 /* no-op */
142 }else if( diffFlags & DIFF_WEBPAGE ){
143 if( fossil_strcmp(zLeft,zRight)==0 ){
144 z = mprintf("<h1>%h</h1>\n", zLeft);
145 }else{
146

Keyboard Shortcuts

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