Fossil SCM

Graph improvement: When there are multiple inbound merge arrows, try to combine as many as possible into a single riser.

drh 2020-06-08 17:10 trunk
Commit 1eb9f5a81a9af81172a33601cdc6912e866a863a57445403e1a89007dbef5157
Parent 3ab64c5a4d3deb7…
3 files changed +89 -4 +15 -2 +1 -1
~ src/graph.c ~ src/graph.js ~ src/timeline.c
M src/graph.c
+89 -4
--- src/graph.c
+++ src/graph.c
@@ -56,10 +56,11 @@
5656
 struct GraphRow {
5757
 int rid; /* The rid for the check-in */
5858
 i8 nParent; /* Number of parents. */
5959
 i8 nCherrypick; /* Subset of aParent that are cherrypicks */
6060
 i8 nNonCherrypick; /* Number of non-cherrypick parents */
61
+ u8 nMergeChild; /* Number of merge children */
6162
 int *aParent; /* Array of parents. 0 element is primary .*/
6263
 char *zBranch; /* Branch name */
6364
 char *zBgClr; /* Background Color */
6465
 char zUuid[HNAME_MAX+1]; /* Check-in for file ID */
6566
@@ -472,11 +473,12 @@
472473
 ** the aParent[] array.
473474
 */
474475
 if( (tmFlags & (TIMELINE_DISJOINT|TIMELINE_XMERGE))!=0 ){
475476
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
476477
 for(i=1; i<pRow->nParent; i++){
477
- if( hashFind(p, pRow->aParent[i])==0 ){
478
+ GraphRow *pParent = hashFind(p, pRow->aParent[i]);
479
+ if( pParent==0 ){
478480
 memmove(pRow->aParent+i, pRow->aParent+i+1,
479481
 sizeof(pRow->aParent[0])*(pRow->nParent-i-1));
480482
 pRow->nParent--;
481483
 if( i<pRow->nNonCherrypick ){
482484
 pRow->nNonCherrypick--;
@@ -486,10 +488,62 @@
486488
 i--;
487489
 }
488490
 }
489491
 }
490492
 }
493
+
494
+ /* Put the deepest (earliest) merge parent first in the list.
495
+ ** An off-screen merge parent is considered deepest.
496
+ */
497
+ for(pRow=p->pFirst; pRow; pRow=pRow->pNext ){
498
+ if( pRow->nParent<=1 ) continue;
499
+ for(i=1; i<pRow->nParent; i++){
500
+ GraphRow *pParent = hashFind(p, pRow->aParent[i]);
501
+ if( pParent ) pParent->nMergeChild++;
502
+ }
503
+ if( pRow->nCherrypick>1 ){
504
+ int iBest = -1;
505
+ int iDeepest = -1;
506
+ for(i=pRow->nNonCherrypick; i<pRow->nParent; i++){
507
+ GraphRow *pParent = hashFind(p, pRow->aParent[i]);
508
+ if( pParent==0 ){
509
+ iBest = i;
510
+ break;
511
+ }
512
+ if( pParent->idx>iDeepest ){
513
+ iDeepest = pParent->idx;
514
+ iBest = i;
515
+ }
516
+ }
517
+ i = pRow->nNonCherrypick;
518
+ if( iBest>i ){
519
+ int x = pRow->aParent[i];
520
+ pRow->aParent[i] = pRow->aParent[iBest];
521
+ pRow->aParent[iBest] = x;
522
+ }
523
+ }
524
+ if( pRow->nNonCherrypick>2 ){
525
+ int iBest = -1;
526
+ int iDeepest = -1;
527
+ for(i=1; i<pRow->nNonCherrypick; i++){
528
+ GraphRow *pParent = hashFind(p, pRow->aParent[i]);
529
+ if( pParent==0 ){
530
+ iBest = i;
531
+ break;
532
+ }
533
+ if( pParent->idx>iDeepest ){
534
+ iDeepest = pParent->idx;
535
+ iBest = i;
536
+ }
537
+ }
538
+ if( iBest>1 ){
539
+ int x = pRow->aParent[1];
540
+ pRow->aParent[1] = pRow->aParent[iBest];
541
+ pRow->aParent[iBest] = x;
542
+ }
543
+ }
544
+ }
491545
492546
 /* If the primary parent is in a different branch, but there are
493547
 ** other parents in the same branch, reorder the parents to make
494548
 ** the parent from the same branch the primary parent.
495549
 */
@@ -668,15 +722,26 @@
668722
669723
 /*
670724
 ** Insert merge rails and merge arrows
671725
 */
672726
 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
727
+ int iReuseIdx = -1;
728
+ int iReuseRail = -1;
729
+ int isCherrypick = 0;
673730
 for(i=1; i<pRow->nParent; i++){
674731
 int parentRid = pRow->aParent[i];
732
+ if( i==pRow->nNonCherrypick ){
733
+ iReuseIdx = -1;
734
+ iReuseRail = -1;
735
+ isCherrypick = 1;
736
+ }
675737
 pDesc = hashFind(p, parentRid);
676738
 if( pDesc==0 ){
677739
 /* Merge from a node that is off-screen */
740
+ if( iReuseIdx>=p->nRow+1 ){
741
+ continue; /* Suppress multiple off-screen merges */
742
+ }
678743
 int iMrail = -1;
679744
 for(j=0; j<GR_MAX_RAIL; j++){
680745
 if( mergeRiserFrom[j]==parentRid ){
681746
 iMrail = j;
682747
 break;
@@ -685,10 +750,12 @@
685750
 if( iMrail==-1 ){
686751
 iMrail = findFreeRail(p, pRow->idx, p->pLast->idx, 0);
687752
 if( p->mxRail>=GR_MAX_RAIL ) return;
688753
 mergeRiserFrom[iMrail] = parentRid;
689754
 }
755
+ iReuseIdx = p->nRow+1;
756
+ iReuseRail = iMrail;
690757
 mask = BIT(iMrail);
691758
 if( i>=pRow->nNonCherrypick ){
692759
 pRow->mergeIn[iMrail] = 2;
693760
 pRow->cherrypickDown |= mask;
694761
 }else{
@@ -697,13 +764,31 @@
697764
 }
698765
 for(pLoop=pRow->pNext; pLoop; pLoop=pLoop->pNext){
699766
 pLoop->railInUse |= mask;
700767
 }
701768
 }else{
702
- /* Merge from an on-screen node */
703
- createMergeRiser(p, pDesc, pRow, i>=pRow->nNonCherrypick);
704
- if( p->mxRail>=GR_MAX_RAIL ) return;
769
+ /* The merge parent node does exist on this graph */
770
+ if( iReuseIdx>pDesc->idx
771
+ && pDesc->nMergeChild==1
772
+ ){
773
+ /* Reuse an existing merge riser */
774
+ pDesc->mergeOut = iReuseRail;
775
+ if( isCherrypick ){
776
+ pDesc->cherrypickUpto = pDesc->idx;
777
+ }else{
778
+ pDesc->hasNormalOutMerge = 1;
779
+ pDesc->mergeUpto = pDesc->idx;
780
+ }
781
+ }else{
782
+ /* Create a new merge for an on-screen node */
783
+ createMergeRiser(p, pDesc, pRow, isCherrypick);
784
+ if( p->mxRail>=GR_MAX_RAIL ) return;
785
+ if( iReuseIdx<0 && pDesc->nMergeChild==1 ){
786
+ iReuseIdx = pDesc->idx;
787
+ iReuseRail = pDesc->mergeOut;
788
+ }
789
+ }
705790
 }
706791
 }
707792
 }
708793
709794
 /*
710795
--- src/graph.c
+++ src/graph.c
@@ -56,10 +56,11 @@
56 struct GraphRow {
57 int rid; /* The rid for the check-in */
58 i8 nParent; /* Number of parents. */
59 i8 nCherrypick; /* Subset of aParent that are cherrypicks */
60 i8 nNonCherrypick; /* Number of non-cherrypick parents */
 
61 int *aParent; /* Array of parents. 0 element is primary .*/
62 char *zBranch; /* Branch name */
63 char *zBgClr; /* Background Color */
64 char zUuid[HNAME_MAX+1]; /* Check-in for file ID */
65
@@ -472,11 +473,12 @@
472 ** the aParent[] array.
473 */
474 if( (tmFlags & (TIMELINE_DISJOINT|TIMELINE_XMERGE))!=0 ){
475 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
476 for(i=1; i<pRow->nParent; i++){
477 if( hashFind(p, pRow->aParent[i])==0 ){
 
478 memmove(pRow->aParent+i, pRow->aParent+i+1,
479 sizeof(pRow->aParent[0])*(pRow->nParent-i-1));
480 pRow->nParent--;
481 if( i<pRow->nNonCherrypick ){
482 pRow->nNonCherrypick--;
@@ -486,10 +488,62 @@
486 i--;
487 }
488 }
489 }
490 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
491
492 /* If the primary parent is in a different branch, but there are
493 ** other parents in the same branch, reorder the parents to make
494 ** the parent from the same branch the primary parent.
495 */
@@ -668,15 +722,26 @@
668
669 /*
670 ** Insert merge rails and merge arrows
671 */
672 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
 
 
 
673 for(i=1; i<pRow->nParent; i++){
674 int parentRid = pRow->aParent[i];
 
 
 
 
 
675 pDesc = hashFind(p, parentRid);
676 if( pDesc==0 ){
677 /* Merge from a node that is off-screen */
 
 
 
678 int iMrail = -1;
679 for(j=0; j<GR_MAX_RAIL; j++){
680 if( mergeRiserFrom[j]==parentRid ){
681 iMrail = j;
682 break;
@@ -685,10 +750,12 @@
685 if( iMrail==-1 ){
686 iMrail = findFreeRail(p, pRow->idx, p->pLast->idx, 0);
687 if( p->mxRail>=GR_MAX_RAIL ) return;
688 mergeRiserFrom[iMrail] = parentRid;
689 }
 
 
690 mask = BIT(iMrail);
691 if( i>=pRow->nNonCherrypick ){
692 pRow->mergeIn[iMrail] = 2;
693 pRow->cherrypickDown |= mask;
694 }else{
@@ -697,13 +764,31 @@
697 }
698 for(pLoop=pRow->pNext; pLoop; pLoop=pLoop->pNext){
699 pLoop->railInUse |= mask;
700 }
701 }else{
702 /* Merge from an on-screen node */
703 createMergeRiser(p, pDesc, pRow, i>=pRow->nNonCherrypick);
704 if( p->mxRail>=GR_MAX_RAIL ) return;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
705 }
706 }
707 }
708
709 /*
710
--- src/graph.c
+++ src/graph.c
@@ -56,10 +56,11 @@
56 struct GraphRow {
57 int rid; /* The rid for the check-in */
58 i8 nParent; /* Number of parents. */
59 i8 nCherrypick; /* Subset of aParent that are cherrypicks */
60 i8 nNonCherrypick; /* Number of non-cherrypick parents */
61 u8 nMergeChild; /* Number of merge children */
62 int *aParent; /* Array of parents. 0 element is primary .*/
63 char *zBranch; /* Branch name */
64 char *zBgClr; /* Background Color */
65 char zUuid[HNAME_MAX+1]; /* Check-in for file ID */
66
@@ -472,11 +473,12 @@
473 ** the aParent[] array.
474 */
475 if( (tmFlags & (TIMELINE_DISJOINT|TIMELINE_XMERGE))!=0 ){
476 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
477 for(i=1; i<pRow->nParent; i++){
478 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
479 if( pParent==0 ){
480 memmove(pRow->aParent+i, pRow->aParent+i+1,
481 sizeof(pRow->aParent[0])*(pRow->nParent-i-1));
482 pRow->nParent--;
483 if( i<pRow->nNonCherrypick ){
484 pRow->nNonCherrypick--;
@@ -486,10 +488,62 @@
488 i--;
489 }
490 }
491 }
492 }
493
494 /* Put the deepest (earliest) merge parent first in the list.
495 ** An off-screen merge parent is considered deepest.
496 */
497 for(pRow=p->pFirst; pRow; pRow=pRow->pNext ){
498 if( pRow->nParent<=1 ) continue;
499 for(i=1; i<pRow->nParent; i++){
500 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
501 if( pParent ) pParent->nMergeChild++;
502 }
503 if( pRow->nCherrypick>1 ){
504 int iBest = -1;
505 int iDeepest = -1;
506 for(i=pRow->nNonCherrypick; i<pRow->nParent; i++){
507 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
508 if( pParent==0 ){
509 iBest = i;
510 break;
511 }
512 if( pParent->idx>iDeepest ){
513 iDeepest = pParent->idx;
514 iBest = i;
515 }
516 }
517 i = pRow->nNonCherrypick;
518 if( iBest>i ){
519 int x = pRow->aParent[i];
520 pRow->aParent[i] = pRow->aParent[iBest];
521 pRow->aParent[iBest] = x;
522 }
523 }
524 if( pRow->nNonCherrypick>2 ){
525 int iBest = -1;
526 int iDeepest = -1;
527 for(i=1; i<pRow->nNonCherrypick; i++){
528 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
529 if( pParent==0 ){
530 iBest = i;
531 break;
532 }
533 if( pParent->idx>iDeepest ){
534 iDeepest = pParent->idx;
535 iBest = i;
536 }
537 }
538 if( iBest>1 ){
539 int x = pRow->aParent[1];
540 pRow->aParent[1] = pRow->aParent[iBest];
541 pRow->aParent[iBest] = x;
542 }
543 }
544 }
545
546 /* If the primary parent is in a different branch, but there are
547 ** other parents in the same branch, reorder the parents to make
548 ** the parent from the same branch the primary parent.
549 */
@@ -668,15 +722,26 @@
722
723 /*
724 ** Insert merge rails and merge arrows
725 */
726 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
727 int iReuseIdx = -1;
728 int iReuseRail = -1;
729 int isCherrypick = 0;
730 for(i=1; i<pRow->nParent; i++){
731 int parentRid = pRow->aParent[i];
732 if( i==pRow->nNonCherrypick ){
733 iReuseIdx = -1;
734 iReuseRail = -1;
735 isCherrypick = 1;
736 }
737 pDesc = hashFind(p, parentRid);
738 if( pDesc==0 ){
739 /* Merge from a node that is off-screen */
740 if( iReuseIdx>=p->nRow+1 ){
741 continue; /* Suppress multiple off-screen merges */
742 }
743 int iMrail = -1;
744 for(j=0; j<GR_MAX_RAIL; j++){
745 if( mergeRiserFrom[j]==parentRid ){
746 iMrail = j;
747 break;
@@ -685,10 +750,12 @@
750 if( iMrail==-1 ){
751 iMrail = findFreeRail(p, pRow->idx, p->pLast->idx, 0);
752 if( p->mxRail>=GR_MAX_RAIL ) return;
753 mergeRiserFrom[iMrail] = parentRid;
754 }
755 iReuseIdx = p->nRow+1;
756 iReuseRail = iMrail;
757 mask = BIT(iMrail);
758 if( i>=pRow->nNonCherrypick ){
759 pRow->mergeIn[iMrail] = 2;
760 pRow->cherrypickDown |= mask;
761 }else{
@@ -697,13 +764,31 @@
764 }
765 for(pLoop=pRow->pNext; pLoop; pLoop=pLoop->pNext){
766 pLoop->railInUse |= mask;
767 }
768 }else{
769 /* The merge parent node does exist on this graph */
770 if( iReuseIdx>pDesc->idx
771 && pDesc->nMergeChild==1
772 ){
773 /* Reuse an existing merge riser */
774 pDesc->mergeOut = iReuseRail;
775 if( isCherrypick ){
776 pDesc->cherrypickUpto = pDesc->idx;
777 }else{
778 pDesc->hasNormalOutMerge = 1;
779 pDesc->mergeUpto = pDesc->idx;
780 }
781 }else{
782 /* Create a new merge for an on-screen node */
783 createMergeRiser(p, pDesc, pRow, isCherrypick);
784 if( p->mxRail>=GR_MAX_RAIL ) return;
785 if( iReuseIdx<0 && pDesc->nMergeChild==1 ){
786 iReuseIdx = pDesc->idx;
787 iReuseRail = pDesc->mergeOut;
788 }
789 }
790 }
791 }
792 }
793
794 /*
795
M src/graph.js
+15 -2
--- src/graph.js
+++ src/graph.js
@@ -431,18 +431,31 @@
431431
 }else{
432432
 mergeLines[p.mo] = -mLine.w/2;
433433
 }
434434
 x1 += mergeLines[p.mo]
435435
 var y0 = p.y+2;
436
+ var isCP = p.hasOwnProperty('cu');
436437
 if( p.mu==p.id ){
437
- drawCherrypickLine(x0,y0,x1+(x0<x1 ? mLine.w : 0),null);
438
+ /* Merge out error to an existing riser from below */
439
+ var dx = x1<x0 ? mArrow.w : -mArrow.w;
440
+ if( isCP ){
441
+ drawCherrypickLine(x0,y0,x1+dx,null);
442
+ cls = "arrow cherrypick " + (x1<x0 ? "l" : "r");
443
+ }else{
444
+ drawMergeLine(x0,y0,x1+dx,null);
445
+ cls = "arrow merge " + (x1<x0 ? "l" : "r");
446
+ }
447
+ if( p.mu==p.cu ){
448
+ dx = x1<x0 ? mLine.w : -(mArrow.w + mLine.w/2);
449
+ drawBox(cls,null,x1+dx,y0+(mLine.w-mArrow.h)/2);
450
+ }
438451
 y1 = y0;
439452
 }else{
440453
 drawMergeLine(x0,y0,x1+(x0<x1 ? mLine.w : 0),null);
441454
 drawMergeLine(x1,y0+mLine.w,null,y1);
442455
 }
443
- if( p.hasOwnProperty('cu') ){
456
+ if( isCP ){
444457
 var u2 = tx.rowinfo[p.cu-tx.iTopRow];
445458
 var y2 = miLineY(u2);
446459
 drawCherrypickLine(x1,y1,null,y2);
447460
 }
448461
 }else if( mergeOffset ){
449462
--- src/graph.js
+++ src/graph.js
@@ -431,18 +431,31 @@
431 }else{
432 mergeLines[p.mo] = -mLine.w/2;
433 }
434 x1 += mergeLines[p.mo]
435 var y0 = p.y+2;
 
436 if( p.mu==p.id ){
437 drawCherrypickLine(x0,y0,x1+(x0<x1 ? mLine.w : 0),null);
 
 
 
 
 
 
 
 
 
 
 
 
438 y1 = y0;
439 }else{
440 drawMergeLine(x0,y0,x1+(x0<x1 ? mLine.w : 0),null);
441 drawMergeLine(x1,y0+mLine.w,null,y1);
442 }
443 if( p.hasOwnProperty('cu') ){
444 var u2 = tx.rowinfo[p.cu-tx.iTopRow];
445 var y2 = miLineY(u2);
446 drawCherrypickLine(x1,y1,null,y2);
447 }
448 }else if( mergeOffset ){
449
--- src/graph.js
+++ src/graph.js
@@ -431,18 +431,31 @@
431 }else{
432 mergeLines[p.mo] = -mLine.w/2;
433 }
434 x1 += mergeLines[p.mo]
435 var y0 = p.y+2;
436 var isCP = p.hasOwnProperty('cu');
437 if( p.mu==p.id ){
438 /* Merge out error to an existing riser from below */
439 var dx = x1<x0 ? mArrow.w : -mArrow.w;
440 if( isCP ){
441 drawCherrypickLine(x0,y0,x1+dx,null);
442 cls = "arrow cherrypick " + (x1<x0 ? "l" : "r");
443 }else{
444 drawMergeLine(x0,y0,x1+dx,null);
445 cls = "arrow merge " + (x1<x0 ? "l" : "r");
446 }
447 if( p.mu==p.cu ){
448 dx = x1<x0 ? mLine.w : -(mArrow.w + mLine.w/2);
449 drawBox(cls,null,x1+dx,y0+(mLine.w-mArrow.h)/2);
450 }
451 y1 = y0;
452 }else{
453 drawMergeLine(x0,y0,x1+(x0<x1 ? mLine.w : 0),null);
454 drawMergeLine(x1,y0+mLine.w,null,y1);
455 }
456 if( isCP ){
457 var u2 = tx.rowinfo[p.cu-tx.iTopRow];
458 var y2 = miLineY(u2);
459 drawCherrypickLine(x1,y1,null,y2);
460 }
461 }else if( mergeOffset ){
462
M src/timeline.c
+1 -1
--- src/timeline.c
+++ src/timeline.c
@@ -999,11 +999,11 @@
999999
 }
10001000
 if( pRow->mergeOut>=0 ){
10011001
 cgi_printf("\"mo\":%d,", aiMap[pRow->mergeOut]);
10021002
 if( pRow->mergeUpto==0 ) pRow->mergeUpto = pRow->idx;
10031003
 cgi_printf("\"mu\":%d,", pRow->mergeUpto);
1004
- if( pRow->cherrypickUpto>0 && pRow->cherrypickUpto<pRow->mergeUpto ){
1004
+ if( pRow->cherrypickUpto>0 && pRow->cherrypickUpto<=pRow->mergeUpto ){
10051005
 cgi_printf("\"cu\":%d,", pRow->cherrypickUpto);
10061006
 }
10071007
 }
10081008
 if( pRow->isStepParent ){
10091009
 cgi_printf("\"sb\":%d,", pRow->aiRiser[pRow->iRail]);
10101010
--- src/timeline.c
+++ src/timeline.c
@@ -999,11 +999,11 @@
999 }
1000 if( pRow->mergeOut>=0 ){
1001 cgi_printf("\"mo\":%d,", aiMap[pRow->mergeOut]);
1002 if( pRow->mergeUpto==0 ) pRow->mergeUpto = pRow->idx;
1003 cgi_printf("\"mu\":%d,", pRow->mergeUpto);
1004 if( pRow->cherrypickUpto>0 && pRow->cherrypickUpto<pRow->mergeUpto ){
1005 cgi_printf("\"cu\":%d,", pRow->cherrypickUpto);
1006 }
1007 }
1008 if( pRow->isStepParent ){
1009 cgi_printf("\"sb\":%d,", pRow->aiRiser[pRow->iRail]);
1010
--- src/timeline.c
+++ src/timeline.c
@@ -999,11 +999,11 @@
999 }
1000 if( pRow->mergeOut>=0 ){
1001 cgi_printf("\"mo\":%d,", aiMap[pRow->mergeOut]);
1002 if( pRow->mergeUpto==0 ) pRow->mergeUpto = pRow->idx;
1003 cgi_printf("\"mu\":%d,", pRow->mergeUpto);
1004 if( pRow->cherrypickUpto>0 && pRow->cherrypickUpto<=pRow->mergeUpto ){
1005 cgi_printf("\"cu\":%d,", pRow->cherrypickUpto);
1006 }
1007 }
1008 if( pRow->isStepParent ){
1009 cgi_printf("\"sb\":%d,", pRow->aiRiser[pRow->iRail]);
1010

Keyboard Shortcuts

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