Fossil SCM

Merge the diff enhancements from the diff-experimental branch into trunk.

drh 2012-02-06 15:21 trunk merge
Commit bba7aea8ca8ddc57dcc11d4a5b5ffa41ff3ba193
Parent 98cf5c33bc1529e…
2 files changed +282 -44 +1 -1
~ src/diff.c ~ src/style.c
M src/diff.c
+282 -44
--- src/diff.c
+++ src/diff.c
@@ -355,19 +355,21 @@
355355
 typedef struct SbsLine SbsLine;
356356
 struct SbsLine {
357357
 char *zLine; /* The output line under construction */
358358
 int n; /* Index of next unused slot in the zLine[] */
359359
 int width; /* Maximum width of a column in the output */
360
- unsigned char escHtml; /* True to escape html characters */
360
+ unsigned char escHtml; /* True to escape html characters */
361
+ int iStart; /* Write zStart prior to character iStart */
362
+ const char *zStart; /* A <span> tag */
363
+ int iEnd; /* Write </span> prior to character iEnd */
361364
 };
362365
363366
 /*
364367
 ** Flags for sbsWriteText()
365368
 */
366
-#define SBS_NEWLINE 0x0001 /* End with \n\000 */
367
-#define SBS_PAD 0x0002 /* Pad output to width spaces */
368
-#define SBS_ENDSPAN 0x0004 /* Write a </span> after text */
369
+#define SBS_NEWLINE 0x0001 /* End with \n\000 */
370
+#define SBS_PAD 0x0002 /* Pad output to width spaces */
369371
370372
 /*
371373
 ** Write up to width characters of pLine into z[]. Translate tabs into
372374
 ** spaces. Add a newline if SBS_NEWLINE is set. Translate HTML characters
373375
 ** if SBS_HTML is set. Pad the rendering out width bytes if SBS_PAD is set.
@@ -380,10 +382,20 @@
380382
 const char *zIn = pLine->z;
381383
 char *z = &p->zLine[p->n];
382384
 int w = p->width;
383385
 for(i=j=k=0; k<w && i<n; i++, k++){
384386
 char c = zIn[i];
387
+ if( p->escHtml ){
388
+ if( i==p->iStart ){
389
+ int x = strlen(p->zStart);
390
+ memcpy(z+j, p->zStart, x);
391
+ j += x;
392
+ }else if( i==p->iEnd ){
393
+ memcpy(z+j, "</span>", 7);
394
+ j += 7;
395
+ }
396
+ }
385397
 if( c=='\t' ){
386398
 z[j++] = ' ';
387399
 while( (k&7)!=7 && k<w ){ z[j++] = ' '; k++; }
388400
 }else if( c=='\r' || c=='\f' ){
389401
 z[j++] = ' ';
@@ -398,11 +410,11 @@
398410
 j += 4;
399411
 }else{
400412
 z[j++] = c;
401413
 }
402414
 }
403
- if( (flags & SBS_ENDSPAN) && p->escHtml ){
415
+ if( p->escHtml && i<=p->iEnd ){
404416
 memcpy(&z[j], "</span>", 7);
405417
 j += 7;
406418
 }
407419
 if( (flags & SBS_PAD)!=0 ){
408420
 while( k<w ){ k++; z[j++] = ' '; }
@@ -444,10 +456,226 @@
444456
 p->n += 6;
445457
 sbsWriteHtml(p, "</span>");
446458
 p->zLine[p->n++] = ' ';
447459
 }
448460
461
+/*
462
+** Write out lines that have been edited. Adjust the highlight to cover
463
+** only those parts of the line that actually changed.
464
+*/
465
+static void sbsWriteLineChange(
466
+ SbsLine *p, /* The SBS output line */
467
+ DLine *pLeft, /* Left line of the change */
468
+ int lnLeft, /* Line number for the left line */
469
+ DLine *pRight, /* Right line of the change */
470
+ int lnRight /* Line number of the right line */
471
+){
472
+ int nLeft; /* Length of left line in bytes */
473
+ int nRight; /* Length of right line in bytes */
474
+ int nPrefix; /* Length of common prefix */
475
+ int nSuffix; /* Length of common suffix */
476
+ int width; /* Total column width */
477
+ const char *zLeft; /* Text of the left line */
478
+ const char *zRight; /* Text of the right line */
479
+
480
+ nLeft = pLeft->h & LENGTH_MASK;
481
+ zLeft = pLeft->z;
482
+ nRight = pRight->h & LENGTH_MASK;
483
+ zRight = pRight->z;
484
+
485
+ nPrefix = 0;
486
+ while( nPrefix<nLeft && nPrefix<nRight && zLeft[nPrefix]==zRight[nPrefix] ){
487
+ nPrefix++;
488
+ }
489
+ nSuffix = 0;
490
+ if( nPrefix<nLeft && nPrefix<nRight ){
491
+ while( nSuffix<nLeft && nSuffix<nRight
492
+ && zLeft[nLeft-nSuffix-1]==zRight[nRight-nSuffix-1] ){
493
+ nSuffix++;
494
+ }
495
+ if( nSuffix==nLeft || nSuffix==nRight ) nPrefix = 0;
496
+ }
497
+ if( nPrefix+nSuffix > nLeft ) nSuffix = nLeft - nPrefix;
498
+ if( nPrefix+nSuffix > nRight ) nSuffix = nRight - nPrefix;
499
+ if( nPrefix+nSuffix==nLeft ){
500
+ /* Text inserted on the right */
501
+ sbsWriteLineno(p, lnLeft);
502
+ p->iStart = p->iEnd = -1;
503
+ sbsWriteText(p, pLeft, SBS_PAD);
504
+ sbsWrite(p, " | ", 3);
505
+ sbsWriteLineno(p, lnRight);
506
+ p->iStart = nPrefix;
507
+ p->iEnd = nRight - nSuffix;
508
+ p->zStart = "<span class=\"diffadd\">";
509
+ sbsWriteText(p, pRight, SBS_NEWLINE);
510
+ }else if( nPrefix+nSuffix==nRight ){
511
+ /* Text deleted from the left */
512
+ sbsWriteLineno(p, lnLeft);
513
+ p->iStart = nPrefix;
514
+ p->iEnd = nLeft - nSuffix;
515
+ p->zStart = "<span class=\"diffrm\">";
516
+ sbsWriteText(p, pLeft, SBS_PAD);
517
+ sbsWrite(p, " | ", 3);
518
+ sbsWriteLineno(p, lnRight);
519
+ p->iStart = p->iEnd = -1;
520
+ sbsWriteText(p, pRight, SBS_NEWLINE);
521
+ }else{
522
+ /* Text modified between left and right */
523
+ sbsWriteLineno(p, lnLeft);
524
+ p->iStart = nPrefix;
525
+ p->iEnd = nLeft - nSuffix;
526
+ p->zStart = "<span class=\"diffchng\">";
527
+ sbsWriteText(p, pLeft, SBS_PAD);
528
+ sbsWrite(p, " | ", 3);
529
+ sbsWriteLineno(p, lnRight);
530
+ p->iEnd = nRight - nSuffix;
531
+ sbsWriteText(p, pRight, SBS_NEWLINE);
532
+ }
533
+}
534
+
535
+/*
536
+** Return the number between 0 and 100 that is smaller the closer pA and
537
+** pB match. Return 0 for a perfect match. Return 100 if pA and pB are
538
+** completely different.
539
+*/
540
+static int match_dline(DLine *pA, DLine *pB){
541
+ const char *zA;
542
+ const char *zB;
543
+ int nA;
544
+ int nB;
545
+ int minDist;
546
+ int i;
547
+ int nMatch;
548
+ int score;
549
+
550
+ zA = pA->z;
551
+ zB = pB->z;
552
+ nA = pA->h & LENGTH_MASK;
553
+ nB = pB->h & LENGTH_MASK;
554
+ while( nA>0 && fossil_isspace(zA[0]) ){ nA--; zA++; }
555
+ while( nA>0 && fossil_isspace(zA[nA-1]) ){ nA--; }
556
+ while( nB>0 && fossil_isspace(zB[0]) ){ nB--; zB++; }
557
+ while( nB>0 && fossil_isspace(zB[nB-1]) ){ nB--; }
558
+ minDist = nA;
559
+ if( minDist>nB ) minDist = nB;
560
+ if( minDist==0 ){
561
+ score = 100;
562
+ }else{
563
+ for(i=0; i<nA && i<nB && zA[i]==zB[i]; i++){}
564
+ nMatch = i;
565
+ for(i=1; i<=nA && i<=nB && zA[nA-i]==zB[nB-i]; i++){}
566
+ nMatch += i-1;
567
+ score = (nMatch >= minDist) ? 0 : ((minDist - nMatch)*100)/minDist;
568
+ }
569
+ return score;
570
+}
571
+
572
+/*
573
+** There is a change block in which nLeft lines of text on the left are
574
+** converted into nRight lines of text on the right. This routine computes
575
+** how the lines on the left line up with the lines on the right.
576
+**
577
+** The return value is a buffer of unsigned characters, obtained from
578
+** fossil_malloc(). (The caller needs to free the return value using
579
+** fossil_free().) Entries in the returned array have values as follows:
580
+**
581
+** 1. Delete the next line of pLeft.
582
+** 2. The next line of pLeft changes into the next line of pRight.
583
+** 3. Insert the next line of pRight.
584
+**
585
+** The length of the returned array will be just large enough to cause
586
+** all elements of pLeft and pRight to be consumed.
587
+**
588
+** Algorithm: Wagner's minimum edit-distance algorithm, modified by
589
+** adding a cost to each match based on how well the two rows match
590
+** each other. Insertion and deletion costs are 50. Match costs
591
+** are between 0 and 100 where 0 is a perfect match 100 is a complete
592
+** mismatch.
593
+*/
594
+static unsigned char *sbsAlignment(
595
+ DLine *aLeft, int nLeft, /* Text on the left */
596
+ DLine *aRight, int nRight /* Text on the right */
597
+){
598
+ int i, j, k; /* Loop counters */
599
+ int *a; /* One row of the Wagner matrix */
600
+ int *pToFree; /* Space that needs to be freed */
601
+ unsigned char *aM; /* Wagner result matrix */
602
+ int aBuf[100]; /* Stack space for a[] if nRight not to big */
603
+
604
+ aM = fossil_malloc( (nLeft+1)*(nRight+1) );
605
+ if( nLeft==0 ){
606
+ memset(aM, 3, nRight);
607
+ return aM;
608
+ }
609
+ if( nRight==0 ){
610
+ memset(aM, 1, nLeft);
611
+ return aM;
612
+ }
613
+ if( nRight < (sizeof(aBuf)/sizeof(aBuf[0]))-1 ){
614
+ pToFree = 0;
615
+ a = aBuf;
616
+ }else{
617
+ a = pToFree = fossil_malloc( sizeof(a[0])*(nRight+1) );
618
+ }
619
+
620
+ /* Compute the best alignment */
621
+ for(i=0; i<=nRight; i++){
622
+ aM[i] = 3;
623
+ a[i] = i*50;
624
+ }
625
+ aM[0] = 0;
626
+ for(j=1; j<=nLeft; j++){
627
+ int p = a[0];
628
+ a[0] = p+50;
629
+ aM[j*(nRight+1)] = 1;
630
+ for(i=1; i<=nRight; i++){
631
+ int m = a[i-1]+50;
632
+ int d = 3;
633
+ if( m>a[i]+50 ){
634
+ m = a[i]+50;
635
+ d = 1;
636
+ }
637
+ if( m>p ){
638
+ int score = match_dline(&aLeft[j-1], &aRight[i-1]);
639
+ if( (score<66 || (i<j+1 && i>j-1)) && m>p+score ){
640
+ m = p+score;
641
+ d = 2;
642
+ }
643
+ }
644
+ p = a[i];
645
+ a[i] = m;
646
+ aM[j*(nRight+1)+i] = d;
647
+ }
648
+ }
649
+
650
+ /* Compute the lowest-cost path back through the matrix */
651
+ i = nRight;
652
+ j = nLeft;
653
+ k = (nRight+1)*(nLeft+1)-1;
654
+ while( i+j>0 ){
655
+ unsigned char c = aM[k--];
656
+ if( c==2 ){
657
+ assert( i>0 && j>0 );
658
+ i--;
659
+ j--;
660
+ }else if( c==3 ){
661
+ assert( i>0 );
662
+ i--;
663
+ }else{
664
+ assert( j>0 );
665
+ j--;
666
+ }
667
+ aM[k] = aM[j*(nRight+1)+i];
668
+ }
669
+ k++;
670
+ i = (nRight+1)*(nLeft+1) - k;
671
+ memmove(aM, &aM[k], i);
672
+
673
+ /* Return the result */
674
+ fossil_free(pToFree);
675
+ return aM;
676
+}
449677
450678
 /*
451679
 ** Given a diff context in which the aEdit[] array has been filled
452680
 ** in, compute a side-by-side diff into pOut.
453681
 */
@@ -474,10 +702,12 @@
474702
475703
 s.zLine = fossil_malloc( 10*width + 100 );
476704
 if( s.zLine==0 ) return;
477705
 s.width = width;
478706
 s.escHtml = escHtml;
707
+ s.iStart = -1;
708
+ s.iEnd = -1;
479709
 A = p->aFrom;
480710
 B = p->aTo;
481711
 R = p->aEdit;
482712
 mxr = p->nEdit;
483713
 while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }
@@ -527,10 +757,11 @@
527757
 b += skip;
528758
 m = R[r] - skip;
529759
 for(j=0; j<m; j++){
530760
 s.n = 0;
531761
 sbsWriteLineno(&s, a+j);
762
+ s.iStart = s.iEnd = -1;
532763
 sbsWriteText(&s, &A[a+j], SBS_PAD);
533764
 sbsWrite(&s, " ", 3);
534765
 sbsWriteLineno(&s, b+j);
535766
 sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
536767
 blob_append(pOut, s.zLine, s.n);
@@ -538,52 +769,58 @@
538769
 a += m;
539770
 b += m;
540771
541772
 /* Show the differences */
542773
 for(i=0; i<nr; i++){
543
- ma = R[r+i*3+1];
544
- mb = R[r+i*3+2];
545
- m = ma<mb ? ma : mb;
546
- for(j=0; j<m; j++){
547
- s.n = 0;
548
- sbsWriteLineno(&s, a+j);
549
- sbsWriteHtml(&s, "<span class=\"diffchng\">");
550
- sbsWriteText(&s, &A[a+j], SBS_PAD | SBS_ENDSPAN);
551
- sbsWrite(&s, " | ", 3);
552
- sbsWriteLineno(&s, b+j);
553
- sbsWriteHtml(&s, "<span class=\"diffchng\">");
554
- sbsWriteText(&s, &B[b+j], SBS_NEWLINE | SBS_ENDSPAN);
555
- blob_append(pOut, s.zLine, s.n);
556
- }
557
- a += m;
558
- b += m;
559
- ma -= m;
560
- mb -= m;
561
- for(j=0; j<ma; j++){
562
- s.n = 0;
563
- sbsWriteLineno(&s, a+j);
564
- sbsWriteHtml(&s, "<span class=\"diffrm\">");
565
- sbsWriteText(&s, &A[a+j], SBS_PAD | SBS_ENDSPAN);
566
- sbsWrite(&s, " <\n", 3);
567
- blob_append(pOut, s.zLine, s.n);
568
- }
569
- a += ma;
570
- for(j=0; j<mb; j++){
571
- s.n = 0;
572
- sbsWriteSpace(&s, width + 7);
573
- sbsWrite(&s, " > ", 3);
574
- sbsWriteLineno(&s, b+j);
575
- sbsWriteHtml(&s, "<span class=\"diffadd\">");
576
- sbsWriteText(&s, &B[b+j], SBS_NEWLINE | SBS_ENDSPAN);
577
- blob_append(pOut, s.zLine, s.n);
578
- }
579
- b += mb;
774
+ unsigned char *alignment;
775
+ ma = R[r+i*3+1]; /* Lines on left but not on right */
776
+ mb = R[r+i*3+2]; /* Lines on right but not on left */
777
+ alignment = sbsAlignment(&A[a], ma, &B[b], mb);
778
+ for(j=0; ma+mb>0; j++){
779
+ if( alignment[j]==1 ){
780
+ s.n = 0;
781
+ sbsWriteLineno(&s, a);
782
+ s.iStart = 0;
783
+ s.zStart = "<span class=\"diffrm\">";
784
+ s.iEnd = s.width;
785
+ sbsWriteText(&s, &A[a], SBS_PAD);
786
+ sbsWrite(&s, " <\n", 3);
787
+ blob_append(pOut, s.zLine, s.n);
788
+ assert( ma>0 );
789
+ ma--;
790
+ a++;
791
+ }else if( alignment[j]==2 ){
792
+ s.n = 0;
793
+ sbsWriteLineChange(&s, &A[a], a, &B[b], b);
794
+ blob_append(pOut, s.zLine, s.n);
795
+ assert( ma>0 && mb>0 );
796
+ ma--;
797
+ mb--;
798
+ a++;
799
+ b++;
800
+ }else{
801
+ s.n = 0;
802
+ sbsWriteSpace(&s, width + 7);
803
+ sbsWrite(&s, " > ", 3);
804
+ sbsWriteLineno(&s, b);
805
+ s.iStart = 0;
806
+ s.zStart = "<span class=\"diffadd\">";
807
+ s.iEnd = s.width;
808
+ sbsWriteText(&s, &B[b], SBS_NEWLINE);
809
+ blob_append(pOut, s.zLine, s.n);
810
+ assert( mb>0 );
811
+ mb--;
812
+ b++;
813
+ }
814
+ }
815
+ fossil_free(alignment);
580816
 if( i<nr-1 ){
581817
 m = R[r+i*3+3];
582818
 for(j=0; j<m; j++){
583819
 s.n = 0;
584820
 sbsWriteLineno(&s, a+j);
821
+ s.iStart = s.iEnd = -1;
585822
 sbsWriteText(&s, &A[a+j], SBS_PAD);
586823
 sbsWrite(&s, " ", 3);
587824
 sbsWriteLineno(&s, b+j);
588825
 sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
589826
 blob_append(pOut, s.zLine, s.n);
@@ -598,10 +835,11 @@
598835
 m = R[r+nr*3];
599836
 if( m>nContext ) m = nContext;
600837
 for(j=0; j<m; j++){
601838
 s.n = 0;
602839
 sbsWriteLineno(&s, a+j);
840
+ s.iStart = s.iEnd = -1;
603841
 sbsWriteText(&s, &A[a+j], SBS_PAD);
604842
 sbsWrite(&s, " ", 3);
605843
 sbsWriteLineno(&s, b+j);
606844
 sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
607845
 blob_append(pOut, s.zLine, s.n);
@@ -943,11 +1181,11 @@
9431181
 p->aEdit[r+3]++;
9441182
 cpy--;
9451183
 }
9461184
9471185
 /* Shift insertions toward the end of the file */
948
- while( p->aEdit[r+3]>0 && del==0 && ins>0 ){
1186
+ while( r+3<p->nEdit && p->aEdit[r+3]>0 && del==0 && ins>0 ){
9491187
 DLine *pTop = &p->aTo[lnTo]; /* First line inserted */
9501188
 DLine *pBtm = &p->aTo[lnTo+ins]; /* First line past end of insert */
9511189
 if( same_dline(pTop, pBtm)==0 ) break;
9521190
 if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop+1)+LENGTH(pBtm) ) break;
9531191
 lnFrom++;
@@ -969,11 +1207,11 @@
9691207
 p->aEdit[r+3]++;
9701208
 cpy--;
9711209
 }
9721210
9731211
 /* Shift deletions toward the end of the file */
974
- while( p->aEdit[r+3]>0 && del>0 && ins==0 ){
1212
+ while( r+3<p->nEdit && p->aEdit[r+3]>0 && del>0 && ins==0 ){
9751213
 DLine *pTop = &p->aFrom[lnFrom]; /* First line deleted */
9761214
 DLine *pBtm = &p->aFrom[lnFrom+del]; /* First line past end of delete */
9771215
 if( same_dline(pTop, pBtm)==0 ) break;
9781216
 if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop)+LENGTH(pBtm) ) break;
9791217
 lnFrom++;
9801218
--- src/diff.c
+++ src/diff.c
@@ -355,19 +355,21 @@
355 typedef struct SbsLine SbsLine;
356 struct SbsLine {
357 char *zLine; /* The output line under construction */
358 int n; /* Index of next unused slot in the zLine[] */
359 int width; /* Maximum width of a column in the output */
360 unsigned char escHtml; /* True to escape html characters */
 
 
 
361 };
362
363 /*
364 ** Flags for sbsWriteText()
365 */
366 #define SBS_NEWLINE 0x0001 /* End with \n\000 */
367 #define SBS_PAD 0x0002 /* Pad output to width spaces */
368 #define SBS_ENDSPAN 0x0004 /* Write a </span> after text */
369
370 /*
371 ** Write up to width characters of pLine into z[]. Translate tabs into
372 ** spaces. Add a newline if SBS_NEWLINE is set. Translate HTML characters
373 ** if SBS_HTML is set. Pad the rendering out width bytes if SBS_PAD is set.
@@ -380,10 +382,20 @@
380 const char *zIn = pLine->z;
381 char *z = &p->zLine[p->n];
382 int w = p->width;
383 for(i=j=k=0; k<w && i<n; i++, k++){
384 char c = zIn[i];
 
 
 
 
 
 
 
 
 
 
385 if( c=='\t' ){
386 z[j++] = ' ';
387 while( (k&7)!=7 && k<w ){ z[j++] = ' '; k++; }
388 }else if( c=='\r' || c=='\f' ){
389 z[j++] = ' ';
@@ -398,11 +410,11 @@
398 j += 4;
399 }else{
400 z[j++] = c;
401 }
402 }
403 if( (flags & SBS_ENDSPAN) && p->escHtml ){
404 memcpy(&z[j], "</span>", 7);
405 j += 7;
406 }
407 if( (flags & SBS_PAD)!=0 ){
408 while( k<w ){ k++; z[j++] = ' '; }
@@ -444,10 +456,226 @@
444 p->n += 6;
445 sbsWriteHtml(p, "</span>");
446 p->zLine[p->n++] = ' ';
447 }
448
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
449
450 /*
451 ** Given a diff context in which the aEdit[] array has been filled
452 ** in, compute a side-by-side diff into pOut.
453 */
@@ -474,10 +702,12 @@
474
475 s.zLine = fossil_malloc( 10*width + 100 );
476 if( s.zLine==0 ) return;
477 s.width = width;
478 s.escHtml = escHtml;
 
 
479 A = p->aFrom;
480 B = p->aTo;
481 R = p->aEdit;
482 mxr = p->nEdit;
483 while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }
@@ -527,10 +757,11 @@
527 b += skip;
528 m = R[r] - skip;
529 for(j=0; j<m; j++){
530 s.n = 0;
531 sbsWriteLineno(&s, a+j);
 
532 sbsWriteText(&s, &A[a+j], SBS_PAD);
533 sbsWrite(&s, " ", 3);
534 sbsWriteLineno(&s, b+j);
535 sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
536 blob_append(pOut, s.zLine, s.n);
@@ -538,52 +769,58 @@
538 a += m;
539 b += m;
540
541 /* Show the differences */
542 for(i=0; i<nr; i++){
543 ma = R[r+i*3+1];
544 mb = R[r+i*3+2];
545 m = ma<mb ? ma : mb;
546 for(j=0; j<m; j++){
547 s.n = 0;
548 sbsWriteLineno(&s, a+j);
549 sbsWriteHtml(&s, "<span class=\"diffchng\">");
550 sbsWriteText(&s, &A[a+j], SBS_PAD | SBS_ENDSPAN);
551 sbsWrite(&s, " | ", 3);
552 sbsWriteLineno(&s, b+j);
553 sbsWriteHtml(&s, "<span class=\"diffchng\">");
554 sbsWriteText(&s, &B[b+j], SBS_NEWLINE | SBS_ENDSPAN);
555 blob_append(pOut, s.zLine, s.n);
556 }
557 a += m;
558 b += m;
559 ma -= m;
560 mb -= m;
561 for(j=0; j<ma; j++){
562 s.n = 0;
563 sbsWriteLineno(&s, a+j);
564 sbsWriteHtml(&s, "<span class=\"diffrm\">");
565 sbsWriteText(&s, &A[a+j], SBS_PAD | SBS_ENDSPAN);
566 sbsWrite(&s, " <\n", 3);
567 blob_append(pOut, s.zLine, s.n);
568 }
569 a += ma;
570 for(j=0; j<mb; j++){
571 s.n = 0;
572 sbsWriteSpace(&s, width + 7);
573 sbsWrite(&s, " > ", 3);
574 sbsWriteLineno(&s, b+j);
575 sbsWriteHtml(&s, "<span class=\"diffadd\">");
576 sbsWriteText(&s, &B[b+j], SBS_NEWLINE | SBS_ENDSPAN);
577 blob_append(pOut, s.zLine, s.n);
578 }
579 b += mb;
 
 
 
 
 
580 if( i<nr-1 ){
581 m = R[r+i*3+3];
582 for(j=0; j<m; j++){
583 s.n = 0;
584 sbsWriteLineno(&s, a+j);
 
585 sbsWriteText(&s, &A[a+j], SBS_PAD);
586 sbsWrite(&s, " ", 3);
587 sbsWriteLineno(&s, b+j);
588 sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
589 blob_append(pOut, s.zLine, s.n);
@@ -598,10 +835,11 @@
598 m = R[r+nr*3];
599 if( m>nContext ) m = nContext;
600 for(j=0; j<m; j++){
601 s.n = 0;
602 sbsWriteLineno(&s, a+j);
 
603 sbsWriteText(&s, &A[a+j], SBS_PAD);
604 sbsWrite(&s, " ", 3);
605 sbsWriteLineno(&s, b+j);
606 sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
607 blob_append(pOut, s.zLine, s.n);
@@ -943,11 +1181,11 @@
943 p->aEdit[r+3]++;
944 cpy--;
945 }
946
947 /* Shift insertions toward the end of the file */
948 while( p->aEdit[r+3]>0 && del==0 && ins>0 ){
949 DLine *pTop = &p->aTo[lnTo]; /* First line inserted */
950 DLine *pBtm = &p->aTo[lnTo+ins]; /* First line past end of insert */
951 if( same_dline(pTop, pBtm)==0 ) break;
952 if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop+1)+LENGTH(pBtm) ) break;
953 lnFrom++;
@@ -969,11 +1207,11 @@
969 p->aEdit[r+3]++;
970 cpy--;
971 }
972
973 /* Shift deletions toward the end of the file */
974 while( p->aEdit[r+3]>0 && del>0 && ins==0 ){
975 DLine *pTop = &p->aFrom[lnFrom]; /* First line deleted */
976 DLine *pBtm = &p->aFrom[lnFrom+del]; /* First line past end of delete */
977 if( same_dline(pTop, pBtm)==0 ) break;
978 if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop)+LENGTH(pBtm) ) break;
979 lnFrom++;
980
--- src/diff.c
+++ src/diff.c
@@ -355,19 +355,21 @@
355 typedef struct SbsLine SbsLine;
356 struct SbsLine {
357 char *zLine; /* The output line under construction */
358 int n; /* Index of next unused slot in the zLine[] */
359 int width; /* Maximum width of a column in the output */
360 unsigned char escHtml; /* True to escape html characters */
361 int iStart; /* Write zStart prior to character iStart */
362 const char *zStart; /* A <span> tag */
363 int iEnd; /* Write </span> prior to character iEnd */
364 };
365
366 /*
367 ** Flags for sbsWriteText()
368 */
369 #define SBS_NEWLINE 0x0001 /* End with \n\000 */
370 #define SBS_PAD 0x0002 /* Pad output to width spaces */
 
371
372 /*
373 ** Write up to width characters of pLine into z[]. Translate tabs into
374 ** spaces. Add a newline if SBS_NEWLINE is set. Translate HTML characters
375 ** if SBS_HTML is set. Pad the rendering out width bytes if SBS_PAD is set.
@@ -380,10 +382,20 @@
382 const char *zIn = pLine->z;
383 char *z = &p->zLine[p->n];
384 int w = p->width;
385 for(i=j=k=0; k<w && i<n; i++, k++){
386 char c = zIn[i];
387 if( p->escHtml ){
388 if( i==p->iStart ){
389 int x = strlen(p->zStart);
390 memcpy(z+j, p->zStart, x);
391 j += x;
392 }else if( i==p->iEnd ){
393 memcpy(z+j, "</span>", 7);
394 j += 7;
395 }
396 }
397 if( c=='\t' ){
398 z[j++] = ' ';
399 while( (k&7)!=7 && k<w ){ z[j++] = ' '; k++; }
400 }else if( c=='\r' || c=='\f' ){
401 z[j++] = ' ';
@@ -398,11 +410,11 @@
410 j += 4;
411 }else{
412 z[j++] = c;
413 }
414 }
415 if( p->escHtml && i<=p->iEnd ){
416 memcpy(&z[j], "</span>", 7);
417 j += 7;
418 }
419 if( (flags & SBS_PAD)!=0 ){
420 while( k<w ){ k++; z[j++] = ' '; }
@@ -444,10 +456,226 @@
456 p->n += 6;
457 sbsWriteHtml(p, "</span>");
458 p->zLine[p->n++] = ' ';
459 }
460
461 /*
462 ** Write out lines that have been edited. Adjust the highlight to cover
463 ** only those parts of the line that actually changed.
464 */
465 static void sbsWriteLineChange(
466 SbsLine *p, /* The SBS output line */
467 DLine *pLeft, /* Left line of the change */
468 int lnLeft, /* Line number for the left line */
469 DLine *pRight, /* Right line of the change */
470 int lnRight /* Line number of the right line */
471 ){
472 int nLeft; /* Length of left line in bytes */
473 int nRight; /* Length of right line in bytes */
474 int nPrefix; /* Length of common prefix */
475 int nSuffix; /* Length of common suffix */
476 int width; /* Total column width */
477 const char *zLeft; /* Text of the left line */
478 const char *zRight; /* Text of the right line */
479
480 nLeft = pLeft->h & LENGTH_MASK;
481 zLeft = pLeft->z;
482 nRight = pRight->h & LENGTH_MASK;
483 zRight = pRight->z;
484
485 nPrefix = 0;
486 while( nPrefix<nLeft && nPrefix<nRight && zLeft[nPrefix]==zRight[nPrefix] ){
487 nPrefix++;
488 }
489 nSuffix = 0;
490 if( nPrefix<nLeft && nPrefix<nRight ){
491 while( nSuffix<nLeft && nSuffix<nRight
492 && zLeft[nLeft-nSuffix-1]==zRight[nRight-nSuffix-1] ){
493 nSuffix++;
494 }
495 if( nSuffix==nLeft || nSuffix==nRight ) nPrefix = 0;
496 }
497 if( nPrefix+nSuffix > nLeft ) nSuffix = nLeft - nPrefix;
498 if( nPrefix+nSuffix > nRight ) nSuffix = nRight - nPrefix;
499 if( nPrefix+nSuffix==nLeft ){
500 /* Text inserted on the right */
501 sbsWriteLineno(p, lnLeft);
502 p->iStart = p->iEnd = -1;
503 sbsWriteText(p, pLeft, SBS_PAD);
504 sbsWrite(p, " | ", 3);
505 sbsWriteLineno(p, lnRight);
506 p->iStart = nPrefix;
507 p->iEnd = nRight - nSuffix;
508 p->zStart = "<span class=\"diffadd\">";
509 sbsWriteText(p, pRight, SBS_NEWLINE);
510 }else if( nPrefix+nSuffix==nRight ){
511 /* Text deleted from the left */
512 sbsWriteLineno(p, lnLeft);
513 p->iStart = nPrefix;
514 p->iEnd = nLeft - nSuffix;
515 p->zStart = "<span class=\"diffrm\">";
516 sbsWriteText(p, pLeft, SBS_PAD);
517 sbsWrite(p, " | ", 3);
518 sbsWriteLineno(p, lnRight);
519 p->iStart = p->iEnd = -1;
520 sbsWriteText(p, pRight, SBS_NEWLINE);
521 }else{
522 /* Text modified between left and right */
523 sbsWriteLineno(p, lnLeft);
524 p->iStart = nPrefix;
525 p->iEnd = nLeft - nSuffix;
526 p->zStart = "<span class=\"diffchng\">";
527 sbsWriteText(p, pLeft, SBS_PAD);
528 sbsWrite(p, " | ", 3);
529 sbsWriteLineno(p, lnRight);
530 p->iEnd = nRight - nSuffix;
531 sbsWriteText(p, pRight, SBS_NEWLINE);
532 }
533 }
534
535 /*
536 ** Return the number between 0 and 100 that is smaller the closer pA and
537 ** pB match. Return 0 for a perfect match. Return 100 if pA and pB are
538 ** completely different.
539 */
540 static int match_dline(DLine *pA, DLine *pB){
541 const char *zA;
542 const char *zB;
543 int nA;
544 int nB;
545 int minDist;
546 int i;
547 int nMatch;
548 int score;
549
550 zA = pA->z;
551 zB = pB->z;
552 nA = pA->h & LENGTH_MASK;
553 nB = pB->h & LENGTH_MASK;
554 while( nA>0 && fossil_isspace(zA[0]) ){ nA--; zA++; }
555 while( nA>0 && fossil_isspace(zA[nA-1]) ){ nA--; }
556 while( nB>0 && fossil_isspace(zB[0]) ){ nB--; zB++; }
557 while( nB>0 && fossil_isspace(zB[nB-1]) ){ nB--; }
558 minDist = nA;
559 if( minDist>nB ) minDist = nB;
560 if( minDist==0 ){
561 score = 100;
562 }else{
563 for(i=0; i<nA && i<nB && zA[i]==zB[i]; i++){}
564 nMatch = i;
565 for(i=1; i<=nA && i<=nB && zA[nA-i]==zB[nB-i]; i++){}
566 nMatch += i-1;
567 score = (nMatch >= minDist) ? 0 : ((minDist - nMatch)*100)/minDist;
568 }
569 return score;
570 }
571
572 /*
573 ** There is a change block in which nLeft lines of text on the left are
574 ** converted into nRight lines of text on the right. This routine computes
575 ** how the lines on the left line up with the lines on the right.
576 **
577 ** The return value is a buffer of unsigned characters, obtained from
578 ** fossil_malloc(). (The caller needs to free the return value using
579 ** fossil_free().) Entries in the returned array have values as follows:
580 **
581 ** 1. Delete the next line of pLeft.
582 ** 2. The next line of pLeft changes into the next line of pRight.
583 ** 3. Insert the next line of pRight.
584 **
585 ** The length of the returned array will be just large enough to cause
586 ** all elements of pLeft and pRight to be consumed.
587 **
588 ** Algorithm: Wagner's minimum edit-distance algorithm, modified by
589 ** adding a cost to each match based on how well the two rows match
590 ** each other. Insertion and deletion costs are 50. Match costs
591 ** are between 0 and 100 where 0 is a perfect match 100 is a complete
592 ** mismatch.
593 */
594 static unsigned char *sbsAlignment(
595 DLine *aLeft, int nLeft, /* Text on the left */
596 DLine *aRight, int nRight /* Text on the right */
597 ){
598 int i, j, k; /* Loop counters */
599 int *a; /* One row of the Wagner matrix */
600 int *pToFree; /* Space that needs to be freed */
601 unsigned char *aM; /* Wagner result matrix */
602 int aBuf[100]; /* Stack space for a[] if nRight not to big */
603
604 aM = fossil_malloc( (nLeft+1)*(nRight+1) );
605 if( nLeft==0 ){
606 memset(aM, 3, nRight);
607 return aM;
608 }
609 if( nRight==0 ){
610 memset(aM, 1, nLeft);
611 return aM;
612 }
613 if( nRight < (sizeof(aBuf)/sizeof(aBuf[0]))-1 ){
614 pToFree = 0;
615 a = aBuf;
616 }else{
617 a = pToFree = fossil_malloc( sizeof(a[0])*(nRight+1) );
618 }
619
620 /* Compute the best alignment */
621 for(i=0; i<=nRight; i++){
622 aM[i] = 3;
623 a[i] = i*50;
624 }
625 aM[0] = 0;
626 for(j=1; j<=nLeft; j++){
627 int p = a[0];
628 a[0] = p+50;
629 aM[j*(nRight+1)] = 1;
630 for(i=1; i<=nRight; i++){
631 int m = a[i-1]+50;
632 int d = 3;
633 if( m>a[i]+50 ){
634 m = a[i]+50;
635 d = 1;
636 }
637 if( m>p ){
638 int score = match_dline(&aLeft[j-1], &aRight[i-1]);
639 if( (score<66 || (i<j+1 && i>j-1)) && m>p+score ){
640 m = p+score;
641 d = 2;
642 }
643 }
644 p = a[i];
645 a[i] = m;
646 aM[j*(nRight+1)+i] = d;
647 }
648 }
649
650 /* Compute the lowest-cost path back through the matrix */
651 i = nRight;
652 j = nLeft;
653 k = (nRight+1)*(nLeft+1)-1;
654 while( i+j>0 ){
655 unsigned char c = aM[k--];
656 if( c==2 ){
657 assert( i>0 && j>0 );
658 i--;
659 j--;
660 }else if( c==3 ){
661 assert( i>0 );
662 i--;
663 }else{
664 assert( j>0 );
665 j--;
666 }
667 aM[k] = aM[j*(nRight+1)+i];
668 }
669 k++;
670 i = (nRight+1)*(nLeft+1) - k;
671 memmove(aM, &aM[k], i);
672
673 /* Return the result */
674 fossil_free(pToFree);
675 return aM;
676 }
677
678 /*
679 ** Given a diff context in which the aEdit[] array has been filled
680 ** in, compute a side-by-side diff into pOut.
681 */
@@ -474,10 +702,12 @@
702
703 s.zLine = fossil_malloc( 10*width + 100 );
704 if( s.zLine==0 ) return;
705 s.width = width;
706 s.escHtml = escHtml;
707 s.iStart = -1;
708 s.iEnd = -1;
709 A = p->aFrom;
710 B = p->aTo;
711 R = p->aEdit;
712 mxr = p->nEdit;
713 while( mxr>2 && R[mxr-1]==0 && R[mxr-2]==0 ){ mxr -= 3; }
@@ -527,10 +757,11 @@
757 b += skip;
758 m = R[r] - skip;
759 for(j=0; j<m; j++){
760 s.n = 0;
761 sbsWriteLineno(&s, a+j);
762 s.iStart = s.iEnd = -1;
763 sbsWriteText(&s, &A[a+j], SBS_PAD);
764 sbsWrite(&s, " ", 3);
765 sbsWriteLineno(&s, b+j);
766 sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
767 blob_append(pOut, s.zLine, s.n);
@@ -538,52 +769,58 @@
769 a += m;
770 b += m;
771
772 /* Show the differences */
773 for(i=0; i<nr; i++){
774 unsigned char *alignment;
775 ma = R[r+i*3+1]; /* Lines on left but not on right */
776 mb = R[r+i*3+2]; /* Lines on right but not on left */
777 alignment = sbsAlignment(&A[a], ma, &B[b], mb);
778 for(j=0; ma+mb>0; j++){
779 if( alignment[j]==1 ){
780 s.n = 0;
781 sbsWriteLineno(&s, a);
782 s.iStart = 0;
783 s.zStart = "<span class=\"diffrm\">";
784 s.iEnd = s.width;
785 sbsWriteText(&s, &A[a], SBS_PAD);
786 sbsWrite(&s, " <\n", 3);
787 blob_append(pOut, s.zLine, s.n);
788 assert( ma>0 );
789 ma--;
790 a++;
791 }else if( alignment[j]==2 ){
792 s.n = 0;
793 sbsWriteLineChange(&s, &A[a], a, &B[b], b);
794 blob_append(pOut, s.zLine, s.n);
795 assert( ma>0 && mb>0 );
796 ma--;
797 mb--;
798 a++;
799 b++;
800 }else{
801 s.n = 0;
802 sbsWriteSpace(&s, width + 7);
803 sbsWrite(&s, " > ", 3);
804 sbsWriteLineno(&s, b);
805 s.iStart = 0;
806 s.zStart = "<span class=\"diffadd\">";
807 s.iEnd = s.width;
808 sbsWriteText(&s, &B[b], SBS_NEWLINE);
809 blob_append(pOut, s.zLine, s.n);
810 assert( mb>0 );
811 mb--;
812 b++;
813 }
814 }
815 fossil_free(alignment);
816 if( i<nr-1 ){
817 m = R[r+i*3+3];
818 for(j=0; j<m; j++){
819 s.n = 0;
820 sbsWriteLineno(&s, a+j);
821 s.iStart = s.iEnd = -1;
822 sbsWriteText(&s, &A[a+j], SBS_PAD);
823 sbsWrite(&s, " ", 3);
824 sbsWriteLineno(&s, b+j);
825 sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
826 blob_append(pOut, s.zLine, s.n);
@@ -598,10 +835,11 @@
835 m = R[r+nr*3];
836 if( m>nContext ) m = nContext;
837 for(j=0; j<m; j++){
838 s.n = 0;
839 sbsWriteLineno(&s, a+j);
840 s.iStart = s.iEnd = -1;
841 sbsWriteText(&s, &A[a+j], SBS_PAD);
842 sbsWrite(&s, " ", 3);
843 sbsWriteLineno(&s, b+j);
844 sbsWriteText(&s, &B[b+j], SBS_NEWLINE);
845 blob_append(pOut, s.zLine, s.n);
@@ -943,11 +1181,11 @@
1181 p->aEdit[r+3]++;
1182 cpy--;
1183 }
1184
1185 /* Shift insertions toward the end of the file */
1186 while( r+3<p->nEdit && p->aEdit[r+3]>0 && del==0 && ins>0 ){
1187 DLine *pTop = &p->aTo[lnTo]; /* First line inserted */
1188 DLine *pBtm = &p->aTo[lnTo+ins]; /* First line past end of insert */
1189 if( same_dline(pTop, pBtm)==0 ) break;
1190 if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop+1)+LENGTH(pBtm) ) break;
1191 lnFrom++;
@@ -969,11 +1207,11 @@
1207 p->aEdit[r+3]++;
1208 cpy--;
1209 }
1210
1211 /* Shift deletions toward the end of the file */
1212 while( r+3<p->nEdit && p->aEdit[r+3]>0 && del>0 && ins==0 ){
1213 DLine *pTop = &p->aFrom[lnFrom]; /* First line deleted */
1214 DLine *pBtm = &p->aFrom[lnFrom+del]; /* First line past end of delete */
1215 if( same_dline(pTop, pBtm)==0 ) break;
1216 if( LENGTH(pTop)+LENGTH(pBtm-1)<=LENGTH(pTop)+LENGTH(pBtm) ) break;
1217 lnFrom++;
1218
M src/style.c
+1 -1
--- src/style.c
+++ src/style.c
@@ -764,11 +764,11 @@
764764
 @ font-family: monospace;
765765
 @ white-space: pre;
766766
 },
767767
 { "span.diffchng",
768768
 "changes in a diff",
769
- @ background-color: #ffffc8;
769
+ @ background-color: #e0e0ff;
770770
 },
771771
 { "span.diffadd",
772772
 "added code in a diff",
773773
 @ background-color: #e0ffe0;
774774
 },
775775
--- src/style.c
+++ src/style.c
@@ -764,11 +764,11 @@
764 @ font-family: monospace;
765 @ white-space: pre;
766 },
767 { "span.diffchng",
768 "changes in a diff",
769 @ background-color: #ffffc8;
770 },
771 { "span.diffadd",
772 "added code in a diff",
773 @ background-color: #e0ffe0;
774 },
775
--- src/style.c
+++ src/style.c
@@ -764,11 +764,11 @@
764 @ font-family: monospace;
765 @ white-space: pre;
766 },
767 { "span.diffchng",
768 "changes in a diff",
769 @ background-color: #e0e0ff;
770 },
771 { "span.diffadd",
772 "added code in a diff",
773 @ background-color: #e0ffe0;
774 },
775

Keyboard Shortcuts

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