Fossil SCM

Change back to using minimum edit distance for computing similarity of lines for alignment in side-by-side diff change blocks.

drh 2012-02-07 00:01 trunk
Commit 51bda5e44149e711f38f8f0d3e96fca3d64c6652
Parent a928c89cb187c3f…
1 file changed +52 -15
~ src/diff.c
M src/diff.c
+52 -15
--- src/diff.c
+++ src/diff.c
@@ -536,40 +536,77 @@
536536
 ** Return the number between 0 and 100 that is smaller the closer pA and
537537
 ** pB match. Return 0 for a perfect match. Return 100 if pA and pB are
538538
 ** completely different.
539539
 */
540540
 static int match_dline(DLine *pA, DLine *pB){
541
+ int *pToFree;
542
+ int *a;
541543
 const char *zA;
542544
 const char *zB;
543545
 int nA;
544546
 int nB;
545
- int minDist;
546
- int i;
547
- int nMatch;
548
- int score;
547
+ int avg;
548
+ int i, j, dist, score;
549
+ int aStatic[200];
549550
550551
 zA = pA->z;
551552
 zB = pB->z;
552553
 nA = pA->h & LENGTH_MASK;
553554
 nB = pB->h & LENGTH_MASK;
554555
 while( nA>0 && fossil_isspace(zA[0]) ){ nA--; zA++; }
555556
 while( nA>0 && fossil_isspace(zA[nA-1]) ){ nA--; }
556557
 while( nB>0 && fossil_isspace(zB[0]) ){ nB--; zB++; }
557558
 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
- }
559
+ avg = (nA+nB)/2;
560
+ if( avg==0 ) return 100;
561
+ dist = 0;
562
+
563
+ /* Remove any common prefix and suffix */
564
+ while( nA && nB && zA[0]==zB[0] ){
565
+ nA--;
566
+ nB--;
567
+ zA++;
568
+ zB++;
569
+ dist++;
570
+ }
571
+ while( nA && nB && zA[nA-1]==zB[nB-1] ){
572
+ nA--;
573
+ nB--;
574
+ dist++;
575
+ }
576
+
577
+ if( nA>0 && nB>0 ){
578
+ /* Allocate space of the dynamic programming array */
579
+ if( nB<sizeof(aStatic)/sizeof(aStatic[0]) ){
580
+ pToFree = 0;
581
+ a = aStatic;
582
+ }else{
583
+ pToFree = a = fossil_malloc( (nB+1)*sizeof(a[0]) );
584
+ }
585
+
586
+ /* Compute the length of the best sequence of matching characters */
587
+ for(i=0; i<=nB; i++) a[i] = 0;
588
+ for(j=0; j<nA; j++){
589
+ int p = 0;
590
+ for(i=0; i<nB; i++){
591
+ int m = a[i];
592
+ if( m<a[i+1] ) m = a[i+1];
593
+ if( m<p+1 && zA[j]==zB[i] ) m = p+1;
594
+ p = a[i+1];
595
+ a[i+1] = m;
596
+ }
597
+ }
598
+ dist += a[nB];
599
+ fossil_free(pToFree);
600
+ }
601
+ score = dist>avg ? 0 : (avg - dist)*100/avg;
602
+
603
+ /* Return the result */
569604
 return score;
570605
 }
606
+
607
+
571608
572609
 /*
573610
 ** There is a change block in which nLeft lines of text on the left are
574611
 ** converted into nRight lines of text on the right. This routine computes
575612
 ** how the lines on the left line up with the lines on the right.
576613
--- src/diff.c
+++ src/diff.c
@@ -536,40 +536,77 @@
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
--- src/diff.c
+++ src/diff.c
@@ -536,40 +536,77 @@
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 int *pToFree;
542 int *a;
543 const char *zA;
544 const char *zB;
545 int nA;
546 int nB;
547 int avg;
548 int i, j, dist, score;
549 int aStatic[200];
 
550
551 zA = pA->z;
552 zB = pB->z;
553 nA = pA->h & LENGTH_MASK;
554 nB = pB->h & LENGTH_MASK;
555 while( nA>0 && fossil_isspace(zA[0]) ){ nA--; zA++; }
556 while( nA>0 && fossil_isspace(zA[nA-1]) ){ nA--; }
557 while( nB>0 && fossil_isspace(zB[0]) ){ nB--; zB++; }
558 while( nB>0 && fossil_isspace(zB[nB-1]) ){ nB--; }
559 avg = (nA+nB)/2;
560 if( avg==0 ) return 100;
561 dist = 0;
562
563 /* Remove any common prefix and suffix */
564 while( nA && nB && zA[0]==zB[0] ){
565 nA--;
566 nB--;
567 zA++;
568 zB++;
569 dist++;
570 }
571 while( nA && nB && zA[nA-1]==zB[nB-1] ){
572 nA--;
573 nB--;
574 dist++;
575 }
576
577 if( nA>0 && nB>0 ){
578 /* Allocate space of the dynamic programming array */
579 if( nB<sizeof(aStatic)/sizeof(aStatic[0]) ){
580 pToFree = 0;
581 a = aStatic;
582 }else{
583 pToFree = a = fossil_malloc( (nB+1)*sizeof(a[0]) );
584 }
585
586 /* Compute the length of the best sequence of matching characters */
587 for(i=0; i<=nB; i++) a[i] = 0;
588 for(j=0; j<nA; j++){
589 int p = 0;
590 for(i=0; i<nB; i++){
591 int m = a[i];
592 if( m<a[i+1] ) m = a[i+1];
593 if( m<p+1 && zA[j]==zB[i] ) m = p+1;
594 p = a[i+1];
595 a[i+1] = m;
596 }
597 }
598 dist += a[nB];
599 fossil_free(pToFree);
600 }
601 score = dist>avg ? 0 : (avg - dist)*100/avg;
602
603 /* Return the result */
604 return score;
605 }
606
607
608
609 /*
610 ** There is a change block in which nLeft lines of text on the left are
611 ** converted into nRight lines of text on the right. This routine computes
612 ** how the lines on the left line up with the lines on the right.
613

Keyboard Shortcuts

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