1 /*
2 ** Copyright (c) 2010 D. Richard Hipp
3 **
4 ** This program is free software; you can redistribute it and/or
5 ** modify it under the terms of the Simplified BSD License (also
6 ** known as the "2-Clause License" or "FreeBSD License".)
7
8 ** This program is distributed in the hope that it will be useful,
9 ** but without any warranty; without even the implied warranty of
10 ** merchantability or fitness for a particular purpose.
11 **
12 ** Author contact information:
13 ** drh@hwaci.com
14 ** http://www.hwaci.com/drh/
15 **
16 *******************************************************************************
17 **
18 ** This file contains code to compute a revision history graph.
19 */
20 #include "config.h"
21 #include "graph.h"
22 #include <assert.h>
23
24 /* Notes:
25 **
26 ** The graph is laid out in 1 or more "rails". A "rail" is a vertical
27 ** band in the graph in which one can place nodes or arrows connecting
28 ** nodes. There can be between 1 and GR_MAX_RAIL rails. If the graph
29 ** is to complex to be displayed in GR_MAX_RAIL rails, it is omitted.
30 **
31 ** A "riser" is the thick line that comes out of the top of a node and
32 ** goes up to the next node on the branch, or to the top of the screen.
33 ** A "descender" is a thick line that comes out of the bottom of a node
34 ** and proceeds down to the bottom of the page.
35 **
36 ** Invoke graph_init() to create a new GraphContext object. Then
37 ** call graph_add_row() to add nodes, one by one, to the graph.
38 ** Nodes must be added in display order, from top to bottom.
39 ** Then invoke graph_render() to run the layout algorithm. The
40 ** layout algorithm computes which rails all of the nodes sit on, and
41 ** the rails used for merge arrows.
42 */
43
44 #if INTERFACE
45
46 /*
47 ** The type of integer identifiers for rows of the graph.
48 **
49 ** For a normal /timeline graph, the identifiers are never that big
50 ** an an ordinary 32-bit int will work fine. But for the /finfo page,
51 ** the identifier is a combination of the BLOB.RID and the FILENAME.FNID
52 ** values, and so it can become quite large for repos that have both many
53 ** check-ins and many files. For this reason, we make the identifier
54 ** a 64-bit integer, to dramatically reduce the risk of an overflow.
55 */
56 typedef sqlite3_int64 GraphRowId;
57
58 #define GR_MAX_RAIL 40 /* Max number of "rails" to display */
59
60 /* The graph appears vertically beside a timeline. Each row in the
61 ** timeline corresponds to a row in the graph. GraphRow.idx is 0 for
62 ** the top-most row and increases moving down. Hence (in the absence of
63 ** time skew) parents have a larger index than their children.
64 **
65 ** The nParent field is -1 for entires that do not participate in the graph
66 ** but which are included just so that we can capture their background color.
67 */
68 struct GraphRow {
69 GraphRowId rid; /* The rid for the check-in */
70 i8 nParent; /* Number of parents. */
71 i8 nCherrypick; /* Subset of aParent that are cherrypicks */
72 i8 nNonCherrypick; /* Number of non-cherrypick parents */
73 u8 nMergeChild; /* Number of merge children */
74 GraphRowId *aParent; /* Array of parents. 0 element is primary .*/
75 char *zBranch; /* Branch name */
76 char *zBgClr; /* Background Color */
77 char zUuid[HNAME_MAX+1]; /* Check-in for file ID */
78
79 GraphRow *pNext; /* Next row down in the list of all rows */
80 GraphRow *pPrev; /* Previous row */
81
82 int idx; /* Row index. Top row is smallest. */
83 int idxTop; /* Direct descendent highest up on the graph */
84 GraphRow *pChild; /* Child immediately above this node */
85 u8 isDup; /* True if this is duplicate of a prior entry */
86 u8 isLeaf; /* True if this is a leaf node */
87 u8 isStepParent; /* pChild is actually a step-child */
88 u8 hasNormalOutMerge; /* Is parent of at laest 1 non-cherrypick merge */
89 u8 timeWarp; /* Child is earlier in time */
90 u8 bDescender; /* True if riser from bottom of graph to here. */
91 u8 selfUp; /* Space above this node but belonging */
92 i8 iRail; /* Which rail this check-in appears on. 0-based.*/
93 i8 mergeOut; /* Merge out to this rail. -1 if no merge-out */
94 u8 mergeIn[GR_MAX_RAIL]; /* Merge in from non-zero rails */
95 int aiRiser[GR_MAX_RAIL]; /* Risers from this node to a higher row. */
96 int mergeUpto; /* Draw the mergeOut rail up to this level */
97 int cherrypickUpto; /* Continue the mergeOut rail up to here */
98 u64 mergeDown; /* Draw merge lines up from bottom of graph */
99 u64 cherrypickDown; /* Draw cherrypick lines up from bottom */
100 u64 railInUse; /* Mask of occupied rails at this row */
101 };
102
103 /* Context while building a graph
104 */
105 struct GraphContext {
106 int nErr; /* Number of errors encountered */
107 int mxRail; /* Number of rails required to render the graph */
108 GraphRow *pFirst; /* First row in the list. Top row of graph. */
109 GraphRow *pLast; /* Last row in the list. Bottom row of graph. */
110 int nBranch; /* Number of distinct branches */
111 char **azBranch; /* Names of the branches */
112 int nRow; /* Number of rows */
113 int nHash; /* Number of slots in apHash[] */
114 GraphRow **apHash; /* Hash table of GraphRow objects. Key: rid */
115 u8 aiRailMap[GR_MAX_RAIL]; /* Mapping of rails to actually columns */
116 };
117
118 #endif
119
120 /* The N-th bit */
121 #define BIT(N) (((u64)1)<<(N))
122
123 /*
124 ** Number of rows before and answer a node with a riser or descender
125 ** that goes off-screen before we can reuse that rail.
126 */
127 #define RISER_MARGIN 4
128
129
130 /*
131 ** Malloc for zeroed space. Panic if unable to provide the
132 ** requested space.
133 */
safeMalloc(int nByte)134 void *safeMalloc(int nByte){
135 void *p = fossil_malloc(nByte);
136 memset(p, 0, nByte);
137 return p;
138 }
139
140 /*
141 ** Create and initialize a GraphContext
142 */
graph_init(void)143 GraphContext *graph_init(void){
144 return (GraphContext*)safeMalloc( sizeof(GraphContext) );
145 }
146
147 /*
148 ** Clear all content from a graph
149 */
graph_clear(GraphContext * p)150 static void graph_clear(GraphContext *p){
151 int i;
152 GraphRow *pRow;
153 while( p->pFirst ){
154 pRow = p->pFirst;
155 p->pFirst = pRow->pNext;
156 free(pRow);
157 }
158 for(i=0; i<p->nBranch; i++) free(p->azBranch[i]);
159 free(p->azBranch);
160 free(p->apHash);
161 memset(p, 0, sizeof(*p));
162 p->nErr = 1;
163 }
164
165 /*
166 ** Destroy a GraphContext;
167 */
graph_free(GraphContext * p)168 void graph_free(GraphContext *p){
169 graph_clear(p);
170 free(p);
171 }
172
173 /*
174 ** Insert a row into the hash table. pRow->rid is the key. Keys must
175 ** be unique. If there is already another row with the same rid,
176 ** overwrite the prior entry if and only if the overwrite flag is set.
177 */
hashInsert(GraphContext * p,GraphRow * pRow,int overwrite)178 static void hashInsert(GraphContext *p, GraphRow *pRow, int overwrite){
179 int h;
180 h = pRow->rid % p->nHash;
181 while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
182 h++;
183 if( h>=p->nHash ) h = 0;
184 }
185 if( p->apHash[h]==0 || overwrite ){
186 p->apHash[h] = pRow;
187 }
188 }
189
190 /*
191 ** Look up the row with rid.
192 */
hashFind(GraphContext * p,GraphRowId rid)193 static GraphRow *hashFind(GraphContext *p, GraphRowId rid){
194 int h = rid % p->nHash;
195 while( p->apHash[h] && p->apHash[h]->rid!=rid ){
196 h++;
197 if( h>=p->nHash ) h = 0;
198 }
199 return p->apHash[h];
200 }
201
202 /*
203 ** Return the canonical pointer for a given branch name.
204 ** Multiple calls to this routine with equivalent strings
205 ** will return the same pointer.
206 **
207 ** The returned value is a pointer to a (readonly) string that
208 ** has the useful property that strings can be checked for
209 ** equality by comparing pointers.
210 **
211 ** Note: also used for background color names.
212 */
persistBranchName(GraphContext * p,const char * zBranch)213 static char *persistBranchName(GraphContext *p, const char *zBranch){
214 int i;
215 for(i=0; i<p->nBranch; i++){
216 if( fossil_strcmp(zBranch, p->azBranch[i])==0 ) return p->azBranch[i];
217 }
218 p->nBranch++;
219 p->azBranch = fossil_realloc(p->azBranch, sizeof(char*)*p->nBranch);
220 p->azBranch[p->nBranch-1] = mprintf("%s", zBranch);
221 return p->azBranch[p->nBranch-1];
222 }
223
224 /*
225 ** Add a new row to the graph context. Rows are added from top to bottom.
226 */
graph_add_row(GraphContext * p,GraphRowId rid,int nParent,int nCherrypick,GraphRowId * aParent,const char * zBranch,const char * zBgClr,const char * zUuid,int isLeaf)227 int graph_add_row(
228 GraphContext *p, /* The context to which the row is added */
229 GraphRowId rid, /* RID for the check-in */
230 int nParent, /* Number of parents */
231 int nCherrypick, /* How many of aParent[] are actually cherrypicks */
232 GraphRowId *aParent, /* Array of parents */
233 const char *zBranch, /* Branch for this check-in */
234 const char *zBgClr, /* Background color. NULL or "" for white. */
235 const char *zUuid, /* hash name of the object being graphed */
236 int isLeaf /* True if this row is a leaf */
237 ){
238 GraphRow *pRow;
239 int nByte;
240 static int nRow = 0;
241
242 if( p->nErr ) return 0;
243 nByte = sizeof(GraphRow);
244 if( nParent>0 ) nByte += sizeof(pRow->aParent[0])*nParent;
245 pRow = (GraphRow*)safeMalloc( nByte );
246 pRow->aParent = nParent>0 ? (GraphRowId*)&pRow[1] : 0;
247 pRow->rid = rid;
248 if( nCherrypick>=nParent ){
249 nCherrypick = nParent-1; /* Safety. Should never happen. */
250 }
251 pRow->nParent = nParent;
252 pRow->nCherrypick = nCherrypick;
253 pRow->nNonCherrypick = nParent - nCherrypick;
254 pRow->zBranch = persistBranchName(p, zBranch);
255 if( zUuid==0 ) zUuid = "";
256 sqlite3_snprintf(sizeof(pRow->zUuid), pRow->zUuid, "%s", zUuid);
257 pRow->isLeaf = isLeaf;
258 memset(pRow->aiRiser, -1, sizeof(pRow->aiRiser));
259 if( zBgClr==0 ) zBgClr = "";
260 pRow->zBgClr = persistBranchName(p, zBgClr);
261 if( nParent>0 ) memcpy(pRow->aParent, aParent, sizeof(aParent[0])*nParent);
262 if( p->pFirst==0 ){
263 p->pFirst = pRow;
264 }else{
265 p->pLast->pNext = pRow;
266 }
267 p->pLast = pRow;
268 p->nRow++;
269 pRow->idx = pRow->idxTop = ++nRow;
270 return pRow->idx;
271 }
272
273 /*
274 ** Return the index of a rail currently not in use for any row between
275 ** top and bottom, inclusive.
276 */
findFreeRail(GraphContext * p,int top,int btm,int iNearto)277 static int findFreeRail(
278 GraphContext *p, /* The graph context */
279 int top, int btm, /* Span of rows for which the rail is needed */
280 int iNearto /* Find rail nearest to this rail */
281 ){
282 GraphRow *pRow;
283 int i;
284 int iBest = 0;
285 int iBestDist = 9999;
286 u64 inUseMask = 0;
287 for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
288 while( pRow && pRow->idx<=btm ){
289 inUseMask |= pRow->railInUse;
290 pRow = pRow->pNext;
291 }
292 for(i=0; i<GR_MAX_RAIL; i++){
293 if( (inUseMask & BIT(i))==0 ){
294 int dist;
295 if( iNearto<=0 ){
296 iBest = i;
297 break;
298 }
299 dist = i - iNearto;
300 if( dist<0 ) dist = -dist;
301 if( dist<iBestDist ){
302 iBestDist = dist;
303 iBest = i;
304 }
305 }
306 }
307 if( iBestDist>1000 ) p->nErr++;
308 if( iBest>p->mxRail ) p->mxRail = iBest;
309 return iBest;
310 }
311
312 /*
313 ** Assign all children of node pBottom to the same rail as pBottom.
314 */
assignChildrenToRail(GraphRow * pBottom,u32 tmFlags)315 static void assignChildrenToRail(GraphRow *pBottom, u32 tmFlags){
316 int iRail = pBottom->iRail;
317 GraphRow *pCurrent;
318 GraphRow *pPrior;
319 u64 mask = ((u64)1)<<iRail;
320
321 pBottom->railInUse |= mask;
322 pPrior = pBottom;
323 for(pCurrent=pBottom->pChild; pCurrent; pCurrent=pCurrent->pChild){
324 assert( pPrior->idx > pCurrent->idx );
325 assert( pCurrent->iRail<0 );
326 if( pPrior->timeWarp ) break;
327 pCurrent->iRail = iRail;
328 pCurrent->railInUse |= mask;
329 pPrior->aiRiser[iRail] = pCurrent->idx;
330 while( pPrior->idx > pCurrent->idx ){
331 pPrior->railInUse |= mask;
332 pPrior = pPrior->pPrev;
333 assert( pPrior!=0 );
334 }
335 }
336 /* Mask of additional rows for the riser to infinity */
337 if( !pPrior->isLeaf && (tmFlags & TIMELINE_DISJOINT)==0 ){
338 int n = RISER_MARGIN;
339 GraphRow *p;
340 pPrior->selfUp = 0;
341 for(p=pPrior; p && (n--)>0; p=p->pPrev){
342 pPrior->selfUp++;
343 p->railInUse |= mask;
344 }
345 }
346 }
347
348 /*
349 ** Create a merge-arrow riser going from pParent up to pChild.
350 */
createMergeRiser(GraphContext * p,GraphRow * pParent,GraphRow * pChild,int isCherrypick)351 static void createMergeRiser(
352 GraphContext *p,
353 GraphRow *pParent,
354 GraphRow *pChild,
355 int isCherrypick
356 ){
357 int u;
358 u64 mask;
359 GraphRow *pLoop;
360
361 if( pParent->mergeOut<0 ){
362 u = pParent->aiRiser[pParent->iRail];
363 if( u>0 && u<pChild->idx ){
364 /* The thick arrow up to the next primary child of pDesc goes
365 ** further up than the thin merge arrow riser, so draw them both
366 ** on the same rail. */
367 pParent->mergeOut = pParent->iRail;
368 }else if( pParent->idx - pChild->idx < pParent->selfUp ){
369 pParent->mergeOut = pParent->iRail;
370 }else{
371 /* The thin merge arrow riser is taller than the thick primary
372 ** child riser, so use separate rails. */
373 int iTarget = pParent->iRail;
374 pParent->mergeOut = findFreeRail(p, pChild->idx, pParent->idx-1, iTarget);
375 mask = BIT(pParent->mergeOut);
376 for(pLoop=pChild->pNext; pLoop && pLoop->rid!=pParent->rid;
377 pLoop=pLoop->pNext){
378 pLoop->railInUse |= mask;
379 }
380 }
381 }
382 if( isCherrypick ){
383 if( pParent->cherrypickUpto==0 || pParent->cherrypickUpto > pChild->idx ){
384 pParent->cherrypickUpto = pChild->idx;
385 }
386 }else{
387 pParent->hasNormalOutMerge = 1;
388 if( pParent->mergeUpto==0 || pParent->mergeUpto > pChild->idx ){
389 pParent->mergeUpto = pChild->idx;
390 }
391 }
392 pChild->mergeIn[pParent->mergeOut] = isCherrypick ? 2 : 1;
393 }
394
395 /*
396 ** Compute the maximum rail number.
397 */
find_max_rail(GraphContext * p)398 static void find_max_rail(GraphContext *p){
399 GraphRow *pRow;
400 p->mxRail = 0;
401 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
402 if( pRow->iRail>p->mxRail ) p->mxRail = pRow->iRail;
403 if( pRow->mergeOut>p->mxRail ) p->mxRail = pRow->mergeOut;
404 while( p->mxRail<GR_MAX_RAIL
405 && (pRow->mergeDown|pRow->cherrypickDown)>(BIT(p->mxRail+1)-1)
406 ){
407 p->mxRail++;
408 }
409 }
410 }
411
412 /*
413 ** Draw a riser from pRow upward to indicate that it is going
414 ** to a node that is off the graph to the top.
415 */
riser_to_top(GraphRow * pRow)416 static void riser_to_top(GraphRow *pRow){
417 u64 mask = BIT(pRow->iRail);
418 int n = RISER_MARGIN;
419 pRow->aiRiser[pRow->iRail] = 0;
420 while( pRow && (n--)>0 ){
421 pRow->railInUse |= mask;
422 pRow = pRow->pPrev;
423 }
424 }
425
426
427 /*
428 ** Compute the complete graph
429 **
430 ** When primary or merge parents are off-screen, normally a line is drawn
431 ** from the node down to the bottom of the graph. This line is called a
432 ** "descender". But if the omitDescenders flag is true, then lines down
433 ** to the bottom of the screen are omitted.
434 **
435 ** The tmFlags parameter is zero or more of the TIMELINE_* constants.
436 ** Only the following are honored:
437 **
438 ** TIMELINE_DISJOINT: Omit descenders
439 ** TIMELINE_FILLGAPS: Use step-children
440 ** TIMELINE_XMERGE: Omit off-graph merge lines
441 */
graph_finish(GraphContext * p,const char * zLeftBranch,u32 tmFlags)442 void graph_finish(GraphContext *p, const char *zLeftBranch, u32 tmFlags){
443 GraphRow *pRow, *pDesc, *pDup, *pLoop, *pParent;
444 int i, j;
445 u64 mask;
446 int hasDup = 0; /* True if one or more isDup entries */
447 const char *zTrunk;
448 u8 *aMap; /* Copy of p->aiRailMap */
449 int omitDescenders = (tmFlags & TIMELINE_DISJOINT)!=0;
450 int nTimewarp = 0;
451 int riserMargin = (tmFlags & TIMELINE_DISJOINT) ? 0 : RISER_MARGIN;
452
453 /* If mergeRiserFrom[X]==Y that means rail X holds a merge riser
454 ** coming up from the bottom of the graph from off-screen check-in Y
455 ** where Y is the RID. There is no riser on rail X if mergeRiserFrom[X]==0.
456 */
457 GraphRowId mergeRiserFrom[GR_MAX_RAIL];
458
459 if( p==0 || p->pFirst==0 || p->nErr ) return;
460 p->nErr = 1; /* Assume an error until proven otherwise */
461
462 /* Initialize all rows */
463 p->nHash = p->nRow*2 + 1;
464 p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
465 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
466 if( pRow->pNext ) pRow->pNext->pPrev = pRow;
467 pRow->iRail = -1;
468 pRow->mergeOut = -1;
469 if( (pDup = hashFind(p, pRow->rid))!=0 ){
470 hasDup = 1;
471 pDup->isDup = 1;
472 }
473 hashInsert(p, pRow, 1);
474 }
475 p->mxRail = -1;
476 memset(mergeRiserFrom, 0, sizeof(mergeRiserFrom));
477
478 /* Purge merge-parents that are out-of-graph if descenders are not
479 ** drawn.
480 **
481 ** Each node has one primary parent and zero or more "merge" parents.
482 ** A merge parent is a prior check-in from which changes were merged into
483 ** the current check-in. If a merge parent is not in the visible section
484 ** of this graph, then no arrows will be drawn for it, so remove it from
485 ** the aParent[] array.
486 */
487 if( (tmFlags & (TIMELINE_DISJOINT|TIMELINE_XMERGE))!=0 ){
488 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
489 for(i=1; i<pRow->nParent; i++){
490 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
491 if( pParent==0 ){
492 memmove(pRow->aParent+i, pRow->aParent+i+1,
493 sizeof(pRow->aParent[0])*(pRow->nParent-i-1));
494 pRow->nParent--;
495 if( i<pRow->nNonCherrypick ){
496 pRow->nNonCherrypick--;
497 }else{
498 pRow->nCherrypick--;
499 }
500 i--;
501 }
502 }
503 }
504 }
505
506 /* Put the deepest (earliest) merge parent first in the list.
507 ** An off-screen merge parent is considered deepest.
508 */
509 for(pRow=p->pFirst; pRow; pRow=pRow->pNext ){
510 if( pRow->nParent<=1 ) continue;
511 for(i=1; i<pRow->nParent; i++){
512 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
513 if( pParent ) pParent->nMergeChild++;
514 }
515 if( pRow->nCherrypick>1 ){
516 int iBest = -1;
517 int iDeepest = -1;
518 for(i=pRow->nNonCherrypick; i<pRow->nParent; i++){
519 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
520 if( pParent==0 ){
521 iBest = i;
522 break;
523 }
524 if( pParent->idx>iDeepest ){
525 iDeepest = pParent->idx;
526 iBest = i;
527 }
528 }
529 i = pRow->nNonCherrypick;
530 if( iBest>i ){
531 GraphRowId x = pRow->aParent[i];
532 pRow->aParent[i] = pRow->aParent[iBest];
533 pRow->aParent[iBest] = x;
534 }
535 }
536 if( pRow->nNonCherrypick>2 ){
537 int iBest = -1;
538 int iDeepest = -1;
539 for(i=1; i<pRow->nNonCherrypick; i++){
540 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
541 if( pParent==0 ){
542 iBest = i;
543 break;
544 }
545 if( pParent->idx>iDeepest ){
546 iDeepest = pParent->idx;
547 iBest = i;
548 }
549 }
550 if( iBest>1 ){
551 GraphRowId x = pRow->aParent[1];
552 pRow->aParent[1] = pRow->aParent[iBest];
553 pRow->aParent[iBest] = x;
554 }
555 }
556 }
557
558 /* If the primary parent is in a different branch, but there are
559 ** other parents in the same branch, reorder the parents to make
560 ** the parent from the same branch the primary parent.
561 */
562 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
563 if( pRow->isDup ) continue;
564 if( pRow->nNonCherrypick<2 ) continue; /* Not a fork */
565 pParent = hashFind(p, pRow->aParent[0]);
566 if( pParent==0 ) continue; /* Parent off-screen */
567 if( pParent->zBranch==pRow->zBranch ) continue; /* Same branch */
568 for(i=1; i<pRow->nNonCherrypick; i++){
569 pParent = hashFind(p, pRow->aParent[i]);
570 if( pParent && pParent->zBranch==pRow->zBranch ){
571 GraphRowId t = pRow->aParent[0];
572 pRow->aParent[0] = pRow->aParent[i];
573 pRow->aParent[i] = t;
574 break;
575 }
576 }
577 }
578
579
580 /* Find the pChild pointer for each node.
581 **
582 ** The pChild points to the node directly above on the same rail.
583 ** The pChild must be in the same branch. Leaf nodes have a NULL
584 ** pChild.
585 **
586 ** In the case of a fork, choose the pChild that results in the
587 ** longest rail.
588 */
589 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
590 if( pRow->isDup ) continue;
591 if( pRow->nParent<=0 ) continue; /* Root node */
592 pParent = hashFind(p, pRow->aParent[0]);
593 if( pParent==0 ) continue; /* Parent off-screen */
594 if( pParent->zBranch!=pRow->zBranch ) continue; /* Different branch */
595 if( pParent->idx <= pRow->idx ){
596 pParent->timeWarp = 1;
597 nTimewarp++;
598 }else if( pRow->idxTop < pParent->idxTop ){
599 pParent->pChild = pRow;
600 pParent->idxTop = pRow->idxTop;
601 }
602 }
603
604 if( tmFlags & TIMELINE_FILLGAPS ){
605 /* If a node has no pChild in the graph
606 ** and there is a node higher up in the graph
607 ** that is in the same branch and has no in-graph parent, then
608 ** make the lower node a step-child of the upper node. This will
609 ** be represented on the graph by a thick dotted line without an arrowhead.
610 */
611 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
612 if( pRow->pChild ) continue;
613 if( pRow->isLeaf ) continue;
614 for(pLoop=pRow->pPrev; pLoop; pLoop=pLoop->pPrev){
615 if( pLoop->nParent>0
616 && pLoop->zBranch==pRow->zBranch
617 && hashFind(p,pLoop->aParent[0])==0
618 ){
619 pRow->pChild = pLoop;
620 pRow->isStepParent = 1;
621 pLoop->aParent[0] = pRow->rid;
622 break;
623 }
624 }
625 }
626 }
627
628 /* Set the idxTop values for all entries. The idxTop value is the
629 ** "idx" value for the top entry in its stack of children.
630 */
631 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
632 GraphRow *pChild = pRow->pChild;
633 if( pChild && pRow->idxTop>pChild->idxTop ){
634 pRow->idxTop = pChild->idxTop;
635 }
636 }
637
638 /* Identify rows where the primary parent is off screen. Assign
639 ** each to a rail and draw descenders downward.
640 **
641 ** Strive to put the "trunk" branch on far left.
642 */
643 zTrunk = persistBranchName(p, "trunk");
644 for(i=0; i<2; i++){
645 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
646 if( i==0 && pRow->zBranch!=zTrunk ) continue;
647 if( pRow->iRail>=0 ) continue;
648 if( pRow->isDup ) continue;
649 if( pRow->nParent<0 ) continue;
650 if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){
651 pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx+riserMargin, 0);
652 if( p->mxRail>=GR_MAX_RAIL ) return;
653 mask = BIT(pRow->iRail);
654 if( !omitDescenders ){
655 int n = RISER_MARGIN;
656 pRow->bDescender = pRow->nParent>0;
657 for(pLoop=pRow; pLoop && (n--)>0; pLoop=pLoop->pNext){
658 pLoop->railInUse |= mask;
659 }
660 }
661 assignChildrenToRail(pRow, tmFlags);
662 }
663 }
664 }
665
666 /* Assign rails to all rows that are still unassigned.
667 */
668 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
669 GraphRowId parentRid;
670
671 if( pRow->iRail>=0 ){
672 if( pRow->pChild==0 && !pRow->timeWarp ){
673 if( !omitDescenders && count_nonbranch_children(pRow->rid)!=0 ){
674 riser_to_top(pRow);
675 }
676 }
677 continue;
678 }
679 if( pRow->isDup || pRow->nParent<0 ){
680 continue;
681 }else{
682 assert( pRow->nParent>0 );
683 parentRid = pRow->aParent[0];
684 pParent = hashFind(p, parentRid);
685 if( pParent==0 ){
686 pRow->iRail = ++p->mxRail;
687 if( p->mxRail>=GR_MAX_RAIL ) return;
688 pRow->railInUse = BIT(pRow->iRail);
689 continue;
690 }
691 if( pParent->idx>pRow->idx ){
692 /* Common case: Child occurs after parent and is above the
693 ** parent in the timeline */
694 pRow->iRail = findFreeRail(p, pRow->idxTop, pParent->idx,
695 pParent->iRail);
696 if( p->mxRail>=GR_MAX_RAIL ) return;
697 pParent->aiRiser[pRow->iRail] = pRow->idx;
698 }else{
699 /* Timewarp case: Child occurs earlier in time than parent and
700 ** appears below the parent in the timeline. */
701 int iDownRail = ++p->mxRail;
702 if( iDownRail<1 ) iDownRail = ++p->mxRail;
703 pRow->iRail = ++p->mxRail;
704 if( p->mxRail>=GR_MAX_RAIL ) return;
705 pRow->railInUse = BIT(pRow->iRail);
706 pParent->aiRiser[iDownRail] = pRow->idx;
707 mask = BIT(iDownRail);
708 for(pLoop=p->pFirst; pLoop; pLoop=pLoop->pNext){
709 pLoop->railInUse |= mask;
710 }
711 }
712 }
713 mask = BIT(pRow->iRail);
714 pRow->railInUse |= mask;
715 if( pRow->pChild ){
716 assignChildrenToRail(pRow, tmFlags);
717 }else if( !omitDescenders && count_nonbranch_children(pRow->rid)!=0 ){
718 if( !pRow->timeWarp ) riser_to_top(pRow);
719 }
720 if( pParent ){
721 if( pParent->idx>pRow->idx ){
722 /* Common case: Parent is below current row in the graph */
723 for(pLoop=pParent->pPrev; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){
724 pLoop->railInUse |= mask;
725 }
726 }else{
727 /* Timewarp case: Parent is above current row in the graph */
728 for(pLoop=pParent->pNext; pLoop && pLoop!=pRow; pLoop=pLoop->pNext){
729 pLoop->railInUse |= mask;
730 }
731 }
732 }
733 }
734
735 /*
736 ** Insert merge rails and merge arrows
737 */
738 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
739 int iReuseIdx = -1;
740 int iReuseRail = -1;
741 int isCherrypick = 0;
742 for(i=1; i<pRow->nParent; i++){
743 GraphRowId parentRid = pRow->aParent[i];
744 if( i==pRow->nNonCherrypick ){
745 /* Because full merges are laid out before cherrypicks,
746 ** it is ok to use a full-merge raise for a cherrypick.
747 ** See the graph on check-in 8ac66ef33b464d28 for example
748 ** iReuseIdx = -1;
749 ** iReuseRail = -1; */
750 isCherrypick = 1;
751 }
752 pDesc = hashFind(p, parentRid);
753 if( pDesc==0 ){
754 int iMrail = -1;
755 /* Merge from a node that is off-screen */
756 if( iReuseIdx>=p->nRow+1 ){
757 continue; /* Suppress multiple off-screen merges */
758 }
759 for(j=0; j<GR_MAX_RAIL; j++){
760 if( mergeRiserFrom[j]==parentRid ){
761 iMrail = j;
762 break;
763 }
764 }
765 if( iMrail==-1 ){
766 iMrail = findFreeRail(p, pRow->idx, p->pLast->idx, 0);
767 if( p->mxRail>=GR_MAX_RAIL ) return;
768 mergeRiserFrom[iMrail] = parentRid;
769 }
770 iReuseIdx = p->nRow+1;
771 iReuseRail = iMrail;
772 mask = BIT(iMrail);
773 if( i>=pRow->nNonCherrypick ){
774 pRow->mergeIn[iMrail] = 2;
775 pRow->cherrypickDown |= mask;
776 }else{
777 pRow->mergeIn[iMrail] = 1;
778 pRow->mergeDown |= mask;
779 }
780 for(pLoop=pRow->pNext; pLoop; pLoop=pLoop->pNext){
781 pLoop->railInUse |= mask;
782 }
783 }else{
784 /* The merge parent node does exist on this graph */
785 if( iReuseIdx>pDesc->idx
786 && pDesc->nMergeChild==1
787 ){
788 /* Reuse an existing merge riser */
789 pDesc->mergeOut = iReuseRail;
790 if( isCherrypick ){
791 pDesc->cherrypickUpto = pDesc->idx;
792 }else{
793 pDesc->hasNormalOutMerge = 1;
794 pDesc->mergeUpto = pDesc->idx;
795 }
796 }else{
797 /* Create a new merge for an on-screen node */
798 createMergeRiser(p, pDesc, pRow, isCherrypick);
799 if( p->mxRail>=GR_MAX_RAIL ) return;
800 if( iReuseIdx<0
801 && pDesc->nMergeChild==1
802 && (pDesc->iRail!=pDesc->mergeOut || pDesc->isLeaf)
803 ){
804 iReuseIdx = pDesc->idx;
805 iReuseRail = pDesc->mergeOut;
806 }
807 }
808 }
809 }
810 }
811
812 /*
813 ** Insert merge rails from primaries to duplicates.
814 */
815 if( hasDup ){
816 int dupRail;
817 int mxRail;
818 find_max_rail(p);
819 mxRail = p->mxRail;
820 dupRail = mxRail+1;
821 if( p->mxRail>=GR_MAX_RAIL ) return;
822 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
823 if( !pRow->isDup ) continue;
824 pRow->iRail = dupRail;
825 pDesc = hashFind(p, pRow->rid);
826 assert( pDesc!=0 && pDesc!=pRow );
827 createMergeRiser(p, pDesc, pRow, 0);
828 if( pDesc->mergeOut>mxRail ) mxRail = pDesc->mergeOut;
829 }
830 if( dupRail<=mxRail ){
831 dupRail = mxRail+1;
832 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
833 if( pRow->isDup ) pRow->iRail = dupRail;
834 }
835 }
836 if( mxRail>=GR_MAX_RAIL ) return;
837 }
838
839 /*
840 ** Find the maximum rail number.
841 */
842 find_max_rail(p);
843
844 /*
845 ** Compute the rail mapping.
846 */
847 aMap = p->aiRailMap;
848 for(i=0; i<=p->mxRail; i++) aMap[i] = i;
849 if( zLeftBranch && nTimewarp==0 ){
850 char *zLeft = persistBranchName(p, zLeftBranch);
851 j = 0;
852 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
853 if( pRow->zBranch==zLeft && aMap[pRow->iRail]>=j ){
854 for(i=0; i<=p->mxRail; i++){
855 if( aMap[i]>=j && aMap[i]<=pRow->iRail ) aMap[i]++;
856 }
857 aMap[pRow->iRail] = j++;
858 }
859 }
860 cgi_printf("<!-- aiRailMap =");
861 for(i=0; i<=p->mxRail; i++) cgi_printf(" %d", aMap[i]);
862 cgi_printf(" -->\n");
863 }
864
865 p->nErr = 0;
866 }
867