Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Do not draw risers and descenders all the way to the top and bottom of the graph if that is not necessary. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | graph-improvements |
Files: | files | file ages | folders |
SHA3-256: |
9978f8120d422d0a7e4d6b7a24af271d |
User & Date: | drh 2019-05-16 19:00:45.793 |
Context
2019-05-16
| ||
21:42 | Improvements to rail selection in the graph layout. ... (check-in: aa43709a user: drh tags: graph-improvements) | |
19:00 | Do not draw risers and descenders all the way to the top and bottom of the graph if that is not necessary. ... (check-in: 9978f812 user: drh tags: graph-improvements) | |
16:19 | Attempts at improving timeline graphs to be more intuitive and informational. For this check-in, add the TIMELINE_XMERGE property to disable merge lines to non-graph nodes. Then disable TIMELINE_DISJOINT for branch graphs. ... (check-in: f6d74f16 user: drh tags: graph-improvements) | |
Changes
Changes to src/graph.c.
︙ | ︙ | |||
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | ******************************************************************************* ** ** This file contains code to compute a revision history graph. */ #include "config.h" #include "graph.h" #include <assert.h> #if INTERFACE #define GR_MAX_RAIL 40 /* Max number of "rails" to display */ /* The graph appears vertically beside a timeline. Each row in the ** timeline corresponds to a row in the graph. GraphRow.idx is 0 for ** the top-most row and increases moving down. Hence (in the absence of ** time skew) parents have a larger index than their children. ** ** The nParent field is -1 for entires that do not participate in the graph ** but which are included just so that we can capture their background color. */ struct GraphRow { int rid; /* The rid for the check-in */ | > > > > > > > > > > > > > > > > > > > > | | < | 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | ******************************************************************************* ** ** This file contains code to compute a revision history graph. */ #include "config.h" #include "graph.h" #include <assert.h> /* Notes: ** ** The graph is laid out in 1 or more "rails". A "rail" is a vertical ** band in the graph in which one can place nodes or arrows connecting ** nodes. There can be between 1 and GR_MAX_RAIL rails. If the graph ** is to complex to be displayed in GR_MAX_RAIL rails, it is omitted. ** ** A "riser" is the thick line that comes out of the top of a node and ** goes up to the next node on the branch, or to the top of the screen. ** A "descender" is a thick line that comes out of the bottom of a node ** and proceeds down to the bottom of the page. ** ** Invoke graph_init() to create a new GraphContext object. Then ** call graph_add_row() to add nodes, one by one, to the graph. ** Nodes must be added in display order, from top to bottom. ** Then invoke graph_render() to run the layout algorithm. The ** layout algorithm computes which rails all of the nodes sit on, and ** the rails used for merge arrows. */ #if INTERFACE #define GR_MAX_RAIL 40 /* Max number of "rails" to display */ /* The graph appears vertically beside a timeline. Each row in the ** timeline corresponds to a row in the graph. GraphRow.idx is 0 for ** the top-most row and increases moving down. Hence (in the absence of ** time skew) parents have a larger index than their children. ** ** The nParent field is -1 for entires that do not participate in the graph ** but which are included just so that we can capture their background color. */ struct GraphRow { int rid; /* The rid for the check-in */ i8 nParent; /* Number of parents. */ i8 nCherrypick; /* Subset of aParent that are cherrypicks */ i8 nNonCherrypick; /* Number of non-cherrypick parents */ int *aParent; /* Array of parents. 0 element is primary .*/ char *zBranch; /* Branch name */ char *zBgClr; /* Background Color */ char zUuid[HNAME_MAX+1]; /* Check-in for file ID */ GraphRow *pNext; /* Next row down in the list of all rows */ GraphRow *pPrev; /* Previous row */ int idx; /* Row index. Top row is smallest. */ int idxTop; /* Direct descendent highest up on the graph */ GraphRow *pChild; /* Child immediately above this node */ u8 isDup; /* True if this is duplicate of a prior entry */ u8 isLeaf; /* True if this is a leaf node */ u8 isStepParent; /* pChild is actually a step-child */ u8 hasNormalOutMerge; /* Is parent of at laest 1 non-cherrypick merge */ u8 timeWarp; /* Child is earlier in time */ u8 bDescender; /* True if riser from bottom of graph to here. */ i8 iRail; /* Which rail this check-in appears on. 0-based.*/ i8 mergeOut; /* Merge out to this rail. -1 if no merge-out */ u8 mergeIn[GR_MAX_RAIL]; /* Merge in from non-zero rails */ int aiRiser[GR_MAX_RAIL]; /* Risers from this node to a higher row. */ int mergeUpto; /* Draw the mergeOut rail up to this level */ int cherrypickUpto; /* Continue the mergeOut rail up to here */ u64 mergeDown; /* Draw merge lines up from bottom of graph */ u64 cherrypickDown; /* Draw cherrypick lines up from bottom */ u64 railInUse; /* Mask of occupied rails at this row */ }; /* Context while building a graph */ struct GraphContext { int nErr; /* Number of errors encountered */ |
︙ | ︙ | |||
81 82 83 84 85 86 87 88 89 90 91 92 93 94 | GraphRow **apHash; /* Hash table of GraphRow objects. Key: rid */ }; #endif /* The N-th bit */ #define BIT(N) (((u64)1)<<(N)) /* ** Malloc for zeroed space. Panic if unable to provide the ** requested space. */ void *safeMalloc(int nByte){ void *p = fossil_malloc(nByte); | > > > > > > > | 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | GraphRow **apHash; /* Hash table of GraphRow objects. Key: rid */ }; #endif /* The N-th bit */ #define BIT(N) (((u64)1)<<(N)) /* ** Number of rows before and answer a node with a riser or descender ** that goes off-screen before we can reuse that rail. */ #define RISER_MARGIN 4 /* ** Malloc for zeroed space. Panic if unable to provide the ** requested space. */ void *safeMalloc(int nByte){ void *p = fossil_malloc(nByte); |
︙ | ︙ | |||
244 245 246 247 248 249 250 | int iBestDist = 9999; u64 inUseMask = 0; for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){} while( pRow && pRow->idx<=btm ){ inUseMask |= pRow->railInUse; pRow = pRow->pNext; } | | | 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 | int iBestDist = 9999; u64 inUseMask = 0; for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){} while( pRow && pRow->idx<=btm ){ inUseMask |= pRow->railInUse; pRow = pRow->pNext; } for(i=0; i<GR_MAX_RAIL; i++){ if( (inUseMask & BIT(i))==0 ){ int dist; if( iNearto<=0 ){ return i; } dist = i - iNearto; if( dist<0 ) dist = -dist; |
︙ | ︙ | |||
266 267 268 269 270 271 272 | if( iBest>p->mxRail ) p->mxRail = iBest; return iBest; } /* ** Assign all children of node pBottom to the same rail as pBottom. */ | | > > > > > > > > | | > | | 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 | if( iBest>p->mxRail ) p->mxRail = iBest; return iBest; } /* ** Assign all children of node pBottom to the same rail as pBottom. */ static void assignChildrenToRail(GraphRow *pBottom, u32 tmFlags){ int iRail = pBottom->iRail; GraphRow *pCurrent; GraphRow *pPrior; u64 mask = ((u64)1)<<iRail; pBottom->railInUse |= mask; pPrior = pBottom; for(pCurrent=pBottom->pChild; pCurrent; pCurrent=pCurrent->pChild){ assert( pPrior->idx > pCurrent->idx ); assert( pCurrent->iRail<0 ); pCurrent->iRail = iRail; pCurrent->railInUse |= mask; pPrior->aiRiser[iRail] = pCurrent->idx; while( pPrior->idx > pCurrent->idx ){ pPrior->railInUse |= mask; pPrior = pPrior->pPrev; assert( pPrior!=0 ); } } /* Mask of additional rows for the riser to infinity */ if( !pPrior->isLeaf && (tmFlags & TIMELINE_DISJOINT)==0 ){ int n = RISER_MARGIN; GraphRow *p; for(p=pPrior; p && (n--)>0; p=p->pPrev){ p->railInUse |= mask; } } } /* ** Create a merge-arrow riser going from pParent up to pChild. */ static void createMergeRiser( GraphContext *p, GraphRow *pParent, GraphRow *pChild, int isCherrypick ){ int u; u64 mask; GraphRow *pLoop; if( pParent->mergeOut<0 ){ u = pParent->aiRiser[pParent->iRail]; if( u>0 && u<pChild->idx ){ /* The thick arrow up to the next primary child of pDesc goes ** further up than the thin merge arrow riser, so draw them both ** on the same rail. */ pParent->mergeOut = pParent->iRail; }else{ /* The thin merge arrow riser is taller than the thick primary ** child riser, so use separate rails. */ int iTarget = pParent->iRail; int iBtm = pParent->idx - (u==0 ? RISER_MARGIN : 1); pParent->mergeOut = findFreeRail(p, pChild->idx, iBtm, iTarget); mask = BIT(pParent->mergeOut); for(pLoop=pChild->pNext; pLoop && pLoop->rid!=pParent->rid; pLoop=pLoop->pNext){ pLoop->railInUse |= mask; } } } |
︙ | ︙ | |||
351 352 353 354 355 356 357 | ){ p->mxRail++; } } } /* | | > > | | 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 | ){ p->mxRail++; } } } /* ** Draw a riser from pRow upward to indicate that it is going ** to a node that is off the graph to the top. */ static void riser_to_top(GraphRow *pRow){ u64 mask = BIT(pRow->iRail); int n = RISER_MARGIN; pRow->aiRiser[pRow->iRail] = 0; while( pRow && (n--)>0 ){ pRow->railInUse |= mask; pRow = pRow->pPrev; } } /* |
︙ | ︙ | |||
486 487 488 489 490 491 492 | if( pRow->idxTop < pParent->idxTop ){ pParent->pChild = pRow; pParent->idxTop = pRow->idxTop; } } if( tmFlags & TIMELINE_FILLGAPS ){ | | | | > | < | < < < > | | | 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 | if( pRow->idxTop < pParent->idxTop ){ pParent->pChild = pRow; pParent->idxTop = pRow->idxTop; } } if( tmFlags & TIMELINE_FILLGAPS ){ /* If a node has no pChild but there is a node higher up in the graph ** that is in the same branch and that other node has no parent in ** the graph, the lower node a step-child of the upper node. This will ** be represented on the graph by a thick dotted line without an arrowhead. */ for(pRow=p->pFirst; pRow; pRow=pRow->pNext){ if( pRow->pChild ) continue; for(pLoop=pRow->pPrev; pLoop; pLoop=pLoop->pPrev){ if( pLoop->nParent>0 && pLoop->zBranch==pRow->zBranch && hashFind(p,pLoop->aParent[0])==0 ){ pRow->pChild = pLoop; pRow->idxTop = pLoop->idxTop; pRow->isStepParent = 1; pLoop->aParent[0] = pRow->rid; break; } } } } /* Identify rows where the primary parent is off screen. Assign ** each to a rail and draw descenders downward. ** ** Strive to put the "trunk" branch on far left. */ zTrunk = persistBranchName(p, "trunk"); for(i=0; i<2; i++){ for(pRow=p->pLast; pRow; pRow=pRow->pPrev){ if( pRow->isDup ) continue; if( pRow->nParent<0 ) continue; if( i==0 ){ if( pRow->zBranch!=zTrunk ) continue; }else { if( pRow->iRail>=0 ) continue; } if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){ pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx+RISER_MARGIN, 0); if( p->mxRail>=GR_MAX_RAIL ) return; mask = BIT(pRow->iRail); if( !omitDescenders ){ int n = RISER_MARGIN; pRow->bDescender = pRow->nParent>0; for(pLoop=pRow; pLoop && (n--)>0; pLoop=pLoop->pNext){ pLoop->railInUse |= mask; } } assignChildrenToRail(pRow, tmFlags); } } } /* Assign rails to all rows that are still unassigned. */ for(pRow=p->pLast; pRow; pRow=pRow->pPrev){ |
︙ | ︙ | |||
590 591 592 593 594 595 596 | pLoop->railInUse |= mask; } } } mask = BIT(pRow->iRail); pRow->railInUse |= mask; if( pRow->pChild ){ | | | 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 | pLoop->railInUse |= mask; } } } mask = BIT(pRow->iRail); pRow->railInUse |= mask; if( pRow->pChild ){ assignChildrenToRail(pRow, tmFlags); }else if( !omitDescenders && count_nonbranch_children(pRow->rid)!=0 ){ if( !pRow->timeWarp ) riser_to_top(pRow); } if( pParent ){ for(pLoop=pParent->pPrev; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){ pLoop->railInUse |= mask; } |
︙ | ︙ |
Changes to src/graph.js.
︙ | ︙ | |||
195 196 197 198 199 200 201 | var y0 = from.y + node.h/2; var y1 = Math.ceil(to.y + node.h + arw.h/2); drawLine(line,color,x,y0,null,y1); x = to.x + (node.w-arw.w)/2; var n = drawBox(arw.cls,null,x,y); if(color) n.style.borderBottomColor = color; } | | | 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 | var y0 = from.y + node.h/2; var y1 = Math.ceil(to.y + node.h + arw.h/2); drawLine(line,color,x,y0,null,y1); x = to.x + (node.w-arw.w)/2; var n = drawBox(arw.cls,null,x,y); if(color) n.style.borderBottomColor = color; } function drawDotted(from,to,color){ var x = to.x + (node.w-line.w)/2; var y0 = from.y + node.h/2; var y1 = Math.ceil(to.y + node.h); drawLine(dotLine,color,x,y0,null,y1); } /* Draw thin horizontal or vertical lines representing merges */ function drawMergeLine(x0,y0,x1,y1){ |
︙ | ︙ | |||
241 242 243 244 245 246 247 | var e = document.getElementById("mc"+p.id); if(e) e.style.backgroundColor = p.bg; e = document.getElementById("md"+p.id); if(e) e.style.backgroundColor = p.bg; } if( p.r<0 ) return; if( p.u>0 ) drawUpArrow(p,tx.rowinfo[p.u-tx.iTopRow],p.fg); | | > > > > > > > | > > | > > > > > > > | 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 | var e = document.getElementById("mc"+p.id); if(e) e.style.backgroundColor = p.bg; e = document.getElementById("md"+p.id); if(e) e.style.backgroundColor = p.bg; } if( p.r<0 ) return; if( p.u>0 ) drawUpArrow(p,tx.rowinfo[p.u-tx.iTopRow],p.fg); if( p.sb>0 ) drawDotted(p,tx.rowinfo[p.sb-tx.iTopRow],null); var cls = node.cls; if( p.hasOwnProperty('mi') && p.mi.length ) cls += " merge"; if( p.f&1 ) cls += " leaf"; var n = drawBox(cls,p.bg,p.x,p.y); n.id = "tln"+p.id; n.onclick = clickOnNode; n.style.zIndex = 10; if( !tx.omitDescenders ){ if( p.u==0 ){ if( p.hasOwnProperty('mo') && p.r==p.mo ){ var top = tx.rowinfo[p.mu-tx.iTopRow] drawUpArrow(p,{x: p.x, y: top.y-node.h}, p.fg); }else if( p.y>100 ){ drawUpArrow(p,{x: p.x, y: p.y-50}, p.fg); }else{ drawUpArrow(p,{x: p.x, y: 0},p.fg); } } if( p.hasOwnProperty('d') ){ if( p.y + 150 >= btm ){ drawUpArrow({x: p.x, y: btm - node.h/2},p,p.fg); }else{ drawUpArrow({x: p.x, y: p.y+50},p,p.fg); drawDotted({x: p.x, y: p.y+63},{x: p.x, y: p.y+50-node.h/2},null); } } } if( p.hasOwnProperty('mo') ){ var x0 = p.x + node.w/2; var x1 = p.mo*railPitch + node.w/2; var u = tx.rowinfo[p.mu-tx.iTopRow]; var y1 = miLineY(u); if( p.u<0 || p.mo!=p.r ){ |
︙ | ︙ |