Fossil SCM

fossil-scm / src / graph.c
Source Blame History 1084 lines
14c19fb… drh 1 /*
c19f34c… drh 2 ** Copyright (c) 2010 D. Richard Hipp
14c19fb… drh 3 **
14c19fb… drh 4 ** This program is free software; you can redistribute it and/or
c06edd2… drh 5 ** modify it under the terms of the Simplified BSD License (also
c06edd2… drh 6 ** known as the "2-Clause License" or "FreeBSD License".)
c06edd2… drh 7
14c19fb… drh 8 ** This program is distributed in the hope that it will be useful,
c06edd2… drh 9 ** but without any warranty; without even the implied warranty of
c06edd2… drh 10 ** merchantability or fitness for a particular purpose.
14c19fb… drh 11 **
14c19fb… drh 12 ** Author contact information:
14c19fb… drh 13 ** [email protected]
14c19fb… drh 14 ** http://www.hwaci.com/drh/
14c19fb… drh 15 **
14c19fb… drh 16 *******************************************************************************
14c19fb… drh 17 **
14c19fb… drh 18 ** This file contains code to compute a revision history graph.
14c19fb… drh 19 */
14c19fb… drh 20 #include "config.h"
14c19fb… drh 21 #include "graph.h"
14c19fb… drh 22 #include <assert.h>
14c19fb… drh 23
d14590d… drh 24 /* Notes:
d14590d… drh 25 **
d14590d… drh 26 ** The graph is laid out in 1 or more "rails". A "rail" is a vertical
d14590d… drh 27 ** band in the graph in which one can place nodes or arrows connecting
d14590d… drh 28 ** nodes. There can be between 1 and GR_MAX_RAIL rails. If the graph
40320f6… drh 29 ** is too complex to be displayed in GR_MAX_RAIL rails, it is omitted.
d14590d… drh 30 **
d14590d… drh 31 ** A "riser" is the thick line that comes out of the top of a node and
d14590d… drh 32 ** goes up to the next node on the branch, or to the top of the screen.
d14590d… drh 33 ** A "descender" is a thick line that comes out of the bottom of a node
d14590d… drh 34 ** and proceeds down to the bottom of the page.
d14590d… drh 35 **
40320f6… drh 36 ** A "merge riser" is a thin line going up out of a node to indicate a
40320f6… drh 37 ** merge or cherrypick. (Cherrypicks are drawn with thin dashed lines.
40320f6… drh 38 ** Merges are drawn with thin solid lines.) A "merge riser" might go
40320f6… drh 39 ** stright up out of the top of a leaf node, but for non-leaves, they
40320f6… drh 40 ** go horizontally to their assigned rail first, then up.
40320f6… drh 41 **
d14590d… drh 42 ** Invoke graph_init() to create a new GraphContext object. Then
d14590d… drh 43 ** call graph_add_row() to add nodes, one by one, to the graph.
d14590d… drh 44 ** Nodes must be added in display order, from top to bottom.
d14590d… drh 45 ** Then invoke graph_render() to run the layout algorithm. The
40320f6… drh 46 ** layout algorithm computes which rail each nodes sit on, and
d14590d… drh 47 ** the rails used for merge arrows.
d14590d… drh 48 */
d14590d… drh 49
14c19fb… drh 50 #if INTERFACE
14c19fb… drh 51
ab71d95… drh 52 /*
ab71d95… drh 53 ** The type of integer identifiers for rows of the graph.
ab71d95… drh 54 **
ab71d95… drh 55 ** For a normal /timeline graph, the identifiers are never that big
d83638e… danield 56 ** an ordinary 32-bit int will work fine. But for the /finfo page,
ab71d95… drh 57 ** the identifier is a combination of the BLOB.RID and the FILENAME.FNID
ab71d95… drh 58 ** values, and so it can become quite large for repos that have both many
ab71d95… drh 59 ** check-ins and many files. For this reason, we make the identifier
ab71d95… drh 60 ** a 64-bit integer, to dramatically reduce the risk of an overflow.
ab71d95… drh 61 */
ab71d95… drh 62 typedef sqlite3_int64 GraphRowId;
ab71d95… drh 63
a8c6f3a… drh 64 #define GR_MAX_RAIL 64 /* Max number of "rails" to display */
14c19fb… drh 65
14c19fb… drh 66 /* The graph appears vertically beside a timeline. Each row in the
e685fc0… drh 67 ** timeline corresponds to a row in the graph. GraphRow.idx is 0 for
e685fc0… drh 68 ** the top-most row and increases moving down. Hence (in the absence of
e685fc0… drh 69 ** time skew) parents have a larger index than their children.
694e11a… drh 70 **
694e11a… drh 71 ** The nParent field is -1 for entires that do not participate in the graph
694e11a… drh 72 ** but which are included just so that we can capture their background color.
14c19fb… drh 73 */
14c19fb… drh 74 struct GraphRow {
ab71d95… drh 75 GraphRowId rid; /* The rid for the check-in */
d14590d… drh 76 i8 nParent; /* Number of parents. */
55ab522… drh 77 i8 nCherrypick; /* Subset of aParent that are cherrypicks */
55ab522… drh 78 i8 nNonCherrypick; /* Number of non-cherrypick parents */
1eb9f5a… drh 79 u8 nMergeChild; /* Number of merge children */
ab71d95… drh 80 GraphRowId *aParent; /* Array of parents. 0 element is primary .*/
14c19fb… drh 81 char *zBranch; /* Branch name */
96722b6… drh 82 char *zBgClr; /* Background Color */
323299c… drh 83 char zUuid[HNAME_MAX+1]; /* Check-in for file ID */
14c19fb… drh 84
14c19fb… drh 85 GraphRow *pNext; /* Next row down in the list of all rows */
14c19fb… drh 86 GraphRow *pPrev; /* Previous row */
080ab8c… jan.nijtmans 87
d14590d… drh 88 int idx; /* Row index. Top row is smallest. */
c9d3900… danield 89 int idxTop; /* Direct descendant highest up on the graph */
98870a8… drh 90 GraphRow *pChild; /* Child immediately above this node */
0551ff8… drh 91 u8 isDup; /* True if this is duplicate of a prior entry */
d7a0240… drh 92 u8 isLeaf; /* True if this is a leaf node */
1e70f82… drh 93 u8 isStepParent; /* pChild is actually a step-child. The thick
1e70f82… drh 94 ** arrow up to the child is dashed, not solid */
8b3e3e0… drh 95 u8 hasNormalOutMerge; /* Is parent of at laest 1 non-cherrypick merge */
d7a0240… drh 96 u8 timeWarp; /* Child is earlier in time */
94979bc… drh 97 u8 bDescender; /* True if riser from bottom of graph to here. */
e008e05… drh 98 u8 selfUp; /* Space above this node but belonging */
94979bc… drh 99 i8 iRail; /* Which rail this check-in appears on. 0-based.*/
ca869aa… drh 100 i8 mergeOut; /* Merge out to this rail. -1 if no merge-out */
a6934b4… drh 101 u8 mergeIn[GR_MAX_RAIL]; /* Merge in from non-zero rails */
94979bc… drh 102 int aiRiser[GR_MAX_RAIL]; /* Risers from this node to a higher row. */
4614dad… drh 103 int mergeUpto; /* Draw the mergeOut rail up to this level */
30aec47… drh 104 int cherrypickUpto; /* Continue the mergeOut rail up to here */
8d4ee62… drh 105 u64 mergeDown; /* Draw merge lines up from bottom of graph */
55ab522… drh 106 u64 cherrypickDown; /* Draw cherrypick lines up from bottom */
8d4ee62… drh 107 u64 railInUse; /* Mask of occupied rails at this row */
14c19fb… drh 108 };
14c19fb… drh 109
14c19fb… drh 110 /* Context while building a graph
14c19fb… drh 111 */
14c19fb… drh 112 struct GraphContext {
98870a8… drh 113 int nErr; /* Number of errors encountered */
98870a8… drh 114 int mxRail; /* Number of rails required to render the graph */
01d8bf9… drh 115 GraphRow *pFirst; /* First row in the list. Top row of graph. */
01d8bf9… drh 116 GraphRow *pLast; /* Last row in the list. Bottom row of graph. */
98870a8… drh 117 int nBranch; /* Number of distinct branches */
98870a8… drh 118 char **azBranch; /* Names of the branches */
7c2577b… drh 119 int nRow; /* Number of rows */
7c2577b… drh 120 int nHash; /* Number of slots in apHash[] */
1e70f82… drh 121 u8 hasOffsetMergeRiser; /* Merge arrow from leaf goes up on a different
1e70f82… drh 122 ** rail that the node */
a8c6f3a… drh 123 u8 bOverfull; /* Unable to allocate sufficient rails */
d1d7fce… drh 124 u64 mergeRail; /* Rails used for merge lines */
98870a8… drh 125 GraphRow **apHash; /* Hash table of GraphRow objects. Key: rid */
202d3ea… drh 126 u8 aiRailMap[GR_MAX_RAIL+1]; /* Mapping of rails to actually columns */
14c19fb… drh 127 };
14c19fb… drh 128
14c19fb… drh 129 #endif
8d4ee62… drh 130
8d4ee62… drh 131 /* The N-th bit */
8d4ee62… drh 132 #define BIT(N) (((u64)1)<<(N))
d14590d… drh 133
d14590d… drh 134 /*
d1d7fce… drh 135 ** Number of rows before and after a node with a riser or descender
d14590d… drh 136 ** that goes off-screen before we can reuse that rail.
d14590d… drh 137 */
d14590d… drh 138 #define RISER_MARGIN 4
d14590d… drh 139
14c19fb… drh 140
14c19fb… drh 141 /*
14c19fb… drh 142 ** Malloc for zeroed space. Panic if unable to provide the
14c19fb… drh 143 ** requested space.
14c19fb… drh 144 */
14c19fb… drh 145 void *safeMalloc(int nByte){
8f41b2f… drh 146 void *p = fossil_malloc(nByte);
14c19fb… drh 147 memset(p, 0, nByte);
14c19fb… drh 148 return p;
14c19fb… drh 149 }
14c19fb… drh 150
14c19fb… drh 151 /*
14c19fb… drh 152 ** Create and initialize a GraphContext
14c19fb… drh 153 */
14c19fb… drh 154 GraphContext *graph_init(void){
14c19fb… drh 155 return (GraphContext*)safeMalloc( sizeof(GraphContext) );
14c19fb… drh 156 }
14c19fb… drh 157
14c19fb… drh 158 /*
cbafc70… drh 159 ** Clear all content from a graph
14c19fb… drh 160 */
cbafc70… drh 161 static void graph_clear(GraphContext *p){
14c19fb… drh 162 int i;
14c19fb… drh 163 GraphRow *pRow;
14c19fb… drh 164 while( p->pFirst ){
14c19fb… drh 165 pRow = p->pFirst;
14c19fb… drh 166 p->pFirst = pRow->pNext;
14c19fb… drh 167 free(pRow);
14c19fb… drh 168 }
14c19fb… drh 169 for(i=0; i<p->nBranch; i++) free(p->azBranch[i]);
14c19fb… drh 170 free(p->azBranch);
7c2577b… drh 171 free(p->apHash);
cbafc70… drh 172 memset(p, 0, sizeof(*p));
cbafc70… drh 173 p->nErr = 1;
cbafc70… drh 174 }
cbafc70… drh 175
cbafc70… drh 176 /*
cbafc70… drh 177 ** Destroy a GraphContext;
cbafc70… drh 178 */
cbafc70… drh 179 void graph_free(GraphContext *p){
cbafc70… drh 180 graph_clear(p);
14c19fb… drh 181 free(p);
7c2577b… drh 182 }
7c2577b… drh 183
7c2577b… drh 184 /*
98870a8… drh 185 ** Insert a row into the hash table. pRow->rid is the key. Keys must
98870a8… drh 186 ** be unique. If there is already another row with the same rid,
98870a8… drh 187 ** overwrite the prior entry if and only if the overwrite flag is set.
7c2577b… drh 188 */
0551ff8… drh 189 static void hashInsert(GraphContext *p, GraphRow *pRow, int overwrite){
7c2577b… drh 190 int h;
7c2577b… drh 191 h = pRow->rid % p->nHash;
7c2577b… drh 192 while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
7c2577b… drh 193 h++;
7c2577b… drh 194 if( h>=p->nHash ) h = 0;
7c2577b… drh 195 }
0551ff8… drh 196 if( p->apHash[h]==0 || overwrite ){
0551ff8… drh 197 p->apHash[h] = pRow;
0551ff8… drh 198 }
7c2577b… drh 199 }
7c2577b… drh 200
7c2577b… drh 201 /*
7c2577b… drh 202 ** Look up the row with rid.
7c2577b… drh 203 */
ab71d95… drh 204 static GraphRow *hashFind(GraphContext *p, GraphRowId rid){
7c2577b… drh 205 int h = rid % p->nHash;
7c2577b… drh 206 while( p->apHash[h] && p->apHash[h]->rid!=rid ){
7c2577b… drh 207 h++;
7c2577b… drh 208 if( h>=p->nHash ) h = 0;
7c2577b… drh 209 }
7c2577b… drh 210 return p->apHash[h];
14c19fb… drh 211 }
14c19fb… drh 212
14c19fb… drh 213 /*
14c19fb… drh 214 ** Return the canonical pointer for a given branch name.
14c19fb… drh 215 ** Multiple calls to this routine with equivalent strings
14c19fb… drh 216 ** will return the same pointer.
96722b6… drh 217 **
98870a8… drh 218 ** The returned value is a pointer to a (readonly) string that
080ab8c… jan.nijtmans 219 ** has the useful property that strings can be checked for
98870a8… drh 220 ** equality by comparing pointers.
98870a8… drh 221 **
96722b6… drh 222 ** Note: also used for background color names.
14c19fb… drh 223 */
14c19fb… drh 224 static char *persistBranchName(GraphContext *p, const char *zBranch){
14c19fb… drh 225 int i;
14c19fb… drh 226 for(i=0; i<p->nBranch; i++){
31c52c7… drh 227 if( fossil_strcmp(zBranch, p->azBranch[i])==0 ) return p->azBranch[i];
14c19fb… drh 228 }
14c19fb… drh 229 p->nBranch++;
8f41b2f… drh 230 p->azBranch = fossil_realloc(p->azBranch, sizeof(char*)*p->nBranch);
4c3e172… danield 231 p->azBranch[p->nBranch-1] = fossil_strdup(zBranch);
14c19fb… drh 232 return p->azBranch[p->nBranch-1];
14c19fb… drh 233 }
14c19fb… drh 234
14c19fb… drh 235 /*
98870a8… drh 236 ** Add a new row to the graph context. Rows are added from top to bottom.
14c19fb… drh 237 */
7c2577b… drh 238 int graph_add_row(
14c19fb… drh 239 GraphContext *p, /* The context to which the row is added */
ab71d95… drh 240 GraphRowId rid, /* RID for the check-in */
14c19fb… drh 241 int nParent, /* Number of parents */
55ab522… drh 242 int nCherrypick, /* How many of aParent[] are actually cherrypicks */
ab71d95… drh 243 GraphRowId *aParent, /* Array of parents */
96722b6… drh 244 const char *zBranch, /* Branch for this check-in */
d7a0240… drh 245 const char *zBgClr, /* Background color. NULL or "" for white. */
fd9b7bd… drh 246 const char *zUuid, /* hash name of the object being graphed */
d7a0240… drh 247 int isLeaf /* True if this row is a leaf */
14c19fb… drh 248 ){
14c19fb… drh 249 GraphRow *pRow;
5ee80c5… drh 250 int nByte;
ba34443… drh 251 static int nRow = 0;
14c19fb… drh 252
7c2577b… drh 253 if( p->nErr ) return 0;
5ee80c5… drh 254 nByte = sizeof(GraphRow);
694e11a… drh 255 if( nParent>0 ) nByte += sizeof(pRow->aParent[0])*nParent;
5ee80c5… drh 256 pRow = (GraphRow*)safeMalloc( nByte );
ab71d95… drh 257 pRow->aParent = nParent>0 ? (GraphRowId*)&pRow[1] : 0;
14c19fb… drh 258 pRow->rid = rid;
55ab522… drh 259 if( nCherrypick>=nParent ){
55ab522… drh 260 nCherrypick = nParent-1; /* Safety. Should never happen. */
55ab522… drh 261 }
14c19fb… drh 262 pRow->nParent = nParent;
55ab522… drh 263 pRow->nCherrypick = nCherrypick;
55ab522… drh 264 pRow->nNonCherrypick = nParent - nCherrypick;
14c19fb… drh 265 pRow->zBranch = persistBranchName(p, zBranch);
5bff5e5… drh 266 if( zUuid==0 ) zUuid = "";
5bff5e5… drh 267 sqlite3_snprintf(sizeof(pRow->zUuid), pRow->zUuid, "%s", zUuid);
d7a0240… drh 268 pRow->isLeaf = isLeaf;
d7a0240… drh 269 memset(pRow->aiRiser, -1, sizeof(pRow->aiRiser));
c06e296… drh 270 if( zBgClr==0 ) zBgClr = "";
96722b6… drh 271 pRow->zBgClr = persistBranchName(p, zBgClr);
694e11a… drh 272 if( nParent>0 ) memcpy(pRow->aParent, aParent, sizeof(aParent[0])*nParent);
14c19fb… drh 273 if( p->pFirst==0 ){
14c19fb… drh 274 p->pFirst = pRow;
14c19fb… drh 275 }else{
14c19fb… drh 276 p->pLast->pNext = pRow;
14c19fb… drh 277 }
14c19fb… drh 278 p->pLast = pRow;
7c2577b… drh 279 p->nRow++;
ba34443… drh 280 pRow->idx = pRow->idxTop = ++nRow;
7c2577b… drh 281 return pRow->idx;
14c19fb… drh 282 }
14c19fb… drh 283
14c19fb… drh 284 /*
14c19fb… drh 285 ** Return the index of a rail currently not in use for any row between
080ab8c… jan.nijtmans 286 ** top and bottom, inclusive.
14c19fb… drh 287 */
16e703b… drh 288 static int findFreeRail(
16e703b… drh 289 GraphContext *p, /* The graph context */
16e703b… drh 290 int top, int btm, /* Span of rows for which the rail is needed */
d1d7fce… drh 291 int iNearto, /* Find rail nearest to this rail */
d1d7fce… drh 292 int bMergeRail /* This rail will be used for a merge line */
16e703b… drh 293 ){
14c19fb… drh 294 GraphRow *pRow;
14c19fb… drh 295 int i;
16e703b… drh 296 int iBest = 0;
16e703b… drh 297 int iBestDist = 9999;
f734110… drh 298 u64 inUseMask = 0;
14c19fb… drh 299 for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
14c19fb… drh 300 while( pRow && pRow->idx<=btm ){
14c19fb… drh 301 inUseMask |= pRow->railInUse;
14c19fb… drh 302 pRow = pRow->pNext;
14c19fb… drh 303 }
d1d7fce… drh 304
d1d7fce… drh 305 /* First look for a match that honors bMergeRail */
d1d7fce… drh 306 for(i=0; i<=p->mxRail; i++){
d1d7fce… drh 307 u64 m = BIT(i);
d1d7fce… drh 308 int dist;
d1d7fce… drh 309 if( inUseMask & m ) continue;
d1d7fce… drh 310 if( (bMergeRail!=0) != ((p->mergeRail & m)!=0) ) continue;
d1d7fce… drh 311 if( iNearto<=0 ){
d1d7fce… drh 312 iBest = i;
d1d7fce… drh 313 iBestDist = 1;
d1d7fce… drh 314 break;
d1d7fce… drh 315 }
d1d7fce… drh 316 dist = i - iNearto;
d1d7fce… drh 317 if( dist<0 ) dist = -dist;
d1d7fce… drh 318 if( dist<iBestDist ){
d1d7fce… drh 319 iBestDist = dist;
d1d7fce… drh 320 iBest = i;
d1d7fce… drh 321 }
d1d7fce… drh 322 }
275da70… danield 323
d1d7fce… drh 324 /* If no match, consider all possible rails */
d1d7fce… drh 325 if( iBestDist>1000 ){
d1d7fce… drh 326 for(i=0; i<=p->mxRail+1; i++){
16e703b… drh 327 int dist;
d1d7fce… drh 328 if( inUseMask & BIT(i) ) continue;
0551ff8… drh 329 if( iNearto<=0 ){
5399c5d… drh 330 iBest = i;
d1d7fce… drh 331 iBestDist = 1;
5399c5d… drh 332 break;
0551ff8… drh 333 }
16e703b… drh 334 dist = i - iNearto;
16e703b… drh 335 if( dist<0 ) dist = -dist;
16e703b… drh 336 if( dist<iBestDist ){
16e703b… drh 337 iBestDist = dist;
16e703b… drh 338 iBest = i;
16e703b… drh 339 }
16e703b… drh 340 }
16e703b… drh 341 }
a8c6f3a… drh 342 if( iBestDist>1000 ){
a8c6f3a… drh 343 p->bOverfull = 1;
a8c6f3a… drh 344 iBest = GR_MAX_RAIL;
a8c6f3a… drh 345 }
a8c6f3a… drh 346 if( iBest>GR_MAX_RAIL ){
a8c6f3a… drh 347 p->bOverfull = 1;
a8c6f3a… drh 348 iBest = GR_MAX_RAIL;
a8c6f3a… drh 349 }
d7a0240… drh 350 if( iBest>p->mxRail ) p->mxRail = iBest;
d1d7fce… drh 351 if( bMergeRail ) p->mergeRail |= BIT(iBest);
16e703b… drh 352 return iBest;
16e703b… drh 353 }
16e703b… drh 354
16e703b… drh 355 /*
98870a8… drh 356 ** Assign all children of node pBottom to the same rail as pBottom.
98870a8… drh 357 */
d14590d… drh 358 static void assignChildrenToRail(GraphRow *pBottom, u32 tmFlags){
98870a8… drh 359 int iRail = pBottom->iRail;
98870a8… drh 360 GraphRow *pCurrent;
98870a8… drh 361 GraphRow *pPrior;
8d4ee62… drh 362 u64 mask = ((u64)1)<<iRail;
98870a8… drh 363
98870a8… drh 364 pBottom->railInUse |= mask;
98870a8… drh 365 pPrior = pBottom;
98870a8… drh 366 for(pCurrent=pBottom->pChild; pCurrent; pCurrent=pCurrent->pChild){
98870a8… drh 367 assert( pPrior->idx > pCurrent->idx );
98870a8… drh 368 assert( pCurrent->iRail<0 );
5399c5d… drh 369 if( pPrior->timeWarp ) break;
98870a8… drh 370 pCurrent->iRail = iRail;
98870a8… drh 371 pCurrent->railInUse |= mask;
94979bc… drh 372 pPrior->aiRiser[iRail] = pCurrent->idx;
7503f98… drh 373 while( pPrior->idx > pCurrent->idx ){
98870a8… drh 374 pPrior->railInUse |= mask;
98870a8… drh 375 pPrior = pPrior->pPrev;
98870a8… drh 376 assert( pPrior!=0 );
98870a8… drh 377 }
ea61f4a… drh 378 }
d14590d… drh 379 /* Mask of additional rows for the riser to infinity */
d14590d… drh 380 if( !pPrior->isLeaf && (tmFlags & TIMELINE_DISJOINT)==0 ){
d14590d… drh 381 int n = RISER_MARGIN;
d14590d… drh 382 GraphRow *p;
e008e05… drh 383 pPrior->selfUp = 0;
d14590d… drh 384 for(p=pPrior; p && (n--)>0; p=p->pPrev){
e008e05… drh 385 pPrior->selfUp++;
d14590d… drh 386 p->railInUse |= mask;
d14590d… drh 387 }
d14590d… drh 388 }
e008e05… drh 389 }
e008e05… drh 390
a3bfe42… drh 391
a3bfe42… drh 392 /*
a3bfe42… drh 393 ** Check to see if rail iRail is clear from pBottom up to and including
a3bfe42… drh 394 ** pTop.
a3bfe42… drh 395 */
a3bfe42… drh 396 static int railIsClear(GraphRow *pBottom, int iTop, int iRail){
a3bfe42… drh 397 u64 m = BIT(iRail);
a3bfe42… drh 398 while( pBottom && pBottom->idx>=iTop ){
a3bfe42… drh 399 if( pBottom->railInUse & m ) return 0;
a3bfe42… drh 400 pBottom = pBottom->pPrev;
a3bfe42… drh 401 }
a3bfe42… drh 402 return 1;
a3bfe42… drh 403 }
a3bfe42… drh 404
313cd3c… drh 405 /*
313cd3c… drh 406 ** Create a merge-arrow riser going from pParent up to pChild.
313cd3c… drh 407 */
313cd3c… drh 408 static void createMergeRiser(
313cd3c… drh 409 GraphContext *p,
a3bfe42… drh 410 GraphRow *pParent, /* Lower node from which the merge line begins */
a3bfe42… drh 411 GraphRow *pChild, /* Upper node at which the merge line ends */
a3bfe42… drh 412 int isCherrypick /* True for a cherry-pick merge */
313cd3c… drh 413 ){
313cd3c… drh 414 int u;
8d4ee62… drh 415 u64 mask;
313cd3c… drh 416 GraphRow *pLoop;
313cd3c… drh 417
313cd3c… drh 418 if( pParent->mergeOut<0 ){
313cd3c… drh 419 u = pParent->aiRiser[pParent->iRail];
6b56d89… drh 420 if( u<0 && railIsClear(pParent->pPrev, pChild->idx, pParent->iRail) ){
a3bfe42… drh 421 /* pParent is a leaf and the merge-line can be drawn straight up.*/
a3bfe42… drh 422 pParent->mergeOut = pParent->iRail;
a3bfe42… drh 423 mask = BIT(pParent->iRail);
a3bfe42… drh 424 for(pLoop=pChild->pNext; pLoop && pLoop->rid!=pParent->rid;
a3bfe42… drh 425 pLoop=pLoop->pNext){
a3bfe42… drh 426 pLoop->railInUse |= mask;
a3bfe42… drh 427 }
a3bfe42… drh 428 }else if( u>0 && u<pChild->idx ){
313cd3c… drh 429 /* The thick arrow up to the next primary child of pDesc goes
313cd3c… drh 430 ** further up than the thin merge arrow riser, so draw them both
313cd3c… drh 431 ** on the same rail. */
e008e05… drh 432 pParent->mergeOut = pParent->iRail;
e008e05… drh 433 }else if( pParent->idx - pChild->idx < pParent->selfUp ){
d14590d… drh 434 pParent->mergeOut = pParent->iRail;
d14590d… drh 435 }else{
313cd3c… drh 436 /* The thin merge arrow riser is taller than the thick primary
313cd3c… drh 437 ** child riser, so use separate rails. */
313cd3c… drh 438 int iTarget = pParent->iRail;
1e70f82… drh 439 if( u<0 ) p->hasOffsetMergeRiser = 1;
d1d7fce… drh 440 pParent->mergeOut = findFreeRail(p, pChild->idx, pParent->idx-1,
d1d7fce… drh 441 iTarget, 1);
ca869aa… drh 442 mask = BIT(pParent->mergeOut);
313cd3c… drh 443 for(pLoop=pChild->pNext; pLoop && pLoop->rid!=pParent->rid;
313cd3c… drh 444 pLoop=pLoop->pNext){
313cd3c… drh 445 pLoop->railInUse |= mask;
313cd3c… drh 446 }
8b3e3e0… drh 447 }
8b3e3e0… drh 448 }
30aec47… drh 449 if( isCherrypick ){
30aec47… drh 450 if( pParent->cherrypickUpto==0 || pParent->cherrypickUpto > pChild->idx ){
30aec47… drh 451 pParent->cherrypickUpto = pChild->idx;
30aec47… drh 452 }
30aec47… drh 453 }else{
8b3e3e0… drh 454 pParent->hasNormalOutMerge = 1;
30aec47… drh 455 if( pParent->mergeUpto==0 || pParent->mergeUpto > pChild->idx ){
30aec47… drh 456 pParent->mergeUpto = pChild->idx;
30aec47… drh 457 }
55ab522… drh 458 }
55ab522… drh 459 pChild->mergeIn[pParent->mergeOut] = isCherrypick ? 2 : 1;
cbc84ad… drh 460 }
cbc84ad… drh 461
cbc84ad… drh 462 /*
cbc84ad… drh 463 ** Compute the maximum rail number.
cbc84ad… drh 464 */
cbc84ad… drh 465 static void find_max_rail(GraphContext *p){
cbc84ad… drh 466 GraphRow *pRow;
cbc84ad… drh 467 p->mxRail = 0;
cbc84ad… drh 468 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
cbc84ad… drh 469 if( pRow->iRail>p->mxRail ) p->mxRail = pRow->iRail;
ca869aa… drh 470 if( pRow->mergeOut>p->mxRail ) p->mxRail = pRow->mergeOut;
55ab522… drh 471 while( p->mxRail<GR_MAX_RAIL
55ab522… drh 472 && (pRow->mergeDown|pRow->cherrypickDown)>(BIT(p->mxRail+1)-1)
55ab522… drh 473 ){
cbc84ad… drh 474 p->mxRail++;
cbc84ad… drh 475 }
cbc84ad… drh 476 }
98870a8… drh 477 }
98870a8… drh 478
da4a3b4… drh 479 /*
d14590d… drh 480 ** Draw a riser from pRow upward to indicate that it is going
d14590d… drh 481 ** to a node that is off the graph to the top.
da4a3b4… drh 482 */
da4a3b4… drh 483 static void riser_to_top(GraphRow *pRow){
da4a3b4… drh 484 u64 mask = BIT(pRow->iRail);
d14590d… drh 485 int n = RISER_MARGIN;
da4a3b4… drh 486 pRow->aiRiser[pRow->iRail] = 0;
d14590d… drh 487 while( pRow && (n--)>0 ){
da4a3b4… drh 488 pRow->railInUse |= mask;
da4a3b4… drh 489 pRow = pRow->pPrev;
da4a3b4… drh 490 }
da4a3b4… drh 491 }
98870a8… drh 492
98870a8… drh 493 /*
14c19fb… drh 494 ** Compute the complete graph
9ed1343… drh 495 **
9ed1343… drh 496 ** When primary or merge parents are off-screen, normally a line is drawn
9ed1343… drh 497 ** from the node down to the bottom of the graph. This line is called a
9ed1343… drh 498 ** "descender". But if the omitDescenders flag is true, then lines down
9ed1343… drh 499 ** to the bottom of the screen are omitted.
fff033f… drh 500 **
fff033f… drh 501 ** The tmFlags parameter is zero or more of the TIMELINE_* constants.
fff033f… drh 502 ** Only the following are honored:
fff033f… drh 503 **
fff033f… drh 504 ** TIMELINE_DISJOINT: Omit descenders
fff033f… drh 505 ** TIMELINE_FILLGAPS: Use step-children
d14590d… drh 506 ** TIMELINE_XMERGE: Omit off-graph merge lines
14c19fb… drh 507 */
e89ea2c… drh 508 void graph_finish(
e89ea2c… drh 509 GraphContext *p, /* The graph to be laid out */
e89ea2c… drh 510 Matcher *pLeftBranch, /* Compares true for left-most branch */
e89ea2c… drh 511 u32 tmFlags /* TIMELINE flags */
e89ea2c… drh 512 ){
98870a8… drh 513 GraphRow *pRow, *pDesc, *pDup, *pLoop, *pParent;
95d6ddc… drh 514 int i, j;
8d4ee62… drh 515 u64 mask;
cbc84ad… drh 516 int hasDup = 0; /* True if one or more isDup entries */
96722b6… drh 517 const char *zTrunk;
ca0d66b… danield 518 const char *zMainBranch;
d19df61… drh 519 u8 *aMap; /* Copy of p->aiRailMap */
fff033f… drh 520 int omitDescenders = (tmFlags & TIMELINE_DISJOINT)!=0;
628fc32… drh 521 int nTimewarp = 0;
4fc08f9… drh 522 int riserMargin = (tmFlags & TIMELINE_DISJOINT) ? 0 : RISER_MARGIN;
9ed1343… drh 523
9ed1343… drh 524 /* If mergeRiserFrom[X]==Y that means rail X holds a merge riser
9ed1343… drh 525 ** coming up from the bottom of the graph from off-screen check-in Y
9ed1343… drh 526 ** where Y is the RID. There is no riser on rail X if mergeRiserFrom[X]==0.
9ed1343… drh 527 */
ab71d95… drh 528 GraphRowId mergeRiserFrom[GR_MAX_RAIL];
14c19fb… drh 529
14c19fb… drh 530 if( p==0 || p->pFirst==0 || p->nErr ) return;
cae94fe… drh 531 p->nErr = 1; /* Assume an error until proven otherwise */
14c19fb… drh 532
14c19fb… drh 533 /* Initialize all rows */
7c2577b… drh 534 p->nHash = p->nRow*2 + 1;
7c2577b… drh 535 p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
14c19fb… drh 536 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
14c19fb… drh 537 if( pRow->pNext ) pRow->pNext->pPrev = pRow;
14c19fb… drh 538 pRow->iRail = -1;
14c19fb… drh 539 pRow->mergeOut = -1;
0551ff8… drh 540 if( (pDup = hashFind(p, pRow->rid))!=0 ){
0551ff8… drh 541 hasDup = 1;
0551ff8… drh 542 pDup->isDup = 1;
0551ff8… drh 543 }
0551ff8… drh 544 hashInsert(p, pRow, 1);
14c19fb… drh 545 }
14c19fb… drh 546 p->mxRail = -1;
9ed1343… drh 547 memset(mergeRiserFrom, 0, sizeof(mergeRiserFrom));
94979bc… drh 548
94979bc… drh 549 /* Purge merge-parents that are out-of-graph if descenders are not
94979bc… drh 550 ** drawn.
94979bc… drh 551 **
94979bc… drh 552 ** Each node has one primary parent and zero or more "merge" parents.
c49030f… drh 553 ** A merge parent is a prior check-in from which changes were merged into
94979bc… drh 554 ** the current check-in. If a merge parent is not in the visible section
94979bc… drh 555 ** of this graph, then no arrows will be drawn for it, so remove it from
94979bc… drh 556 ** the aParent[] array.
94979bc… drh 557 */
d14590d… drh 558 if( (tmFlags & (TIMELINE_DISJOINT|TIMELINE_XMERGE))!=0 ){
94979bc… drh 559 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
94979bc… drh 560 for(i=1; i<pRow->nParent; i++){
1eb9f5a… drh 561 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
1eb9f5a… drh 562 if( pParent==0 ){
275da70… danield 563 memmove(pRow->aParent+i, pRow->aParent+i+1,
55ab522… drh 564 sizeof(pRow->aParent[0])*(pRow->nParent-i-1));
55ab522… drh 565 pRow->nParent--;
55ab522… drh 566 if( i<pRow->nNonCherrypick ){
55ab522… drh 567 pRow->nNonCherrypick--;
55ab522… drh 568 }else{
55ab522… drh 569 pRow->nCherrypick--;
55ab522… drh 570 }
94979bc… drh 571 i--;
94979bc… drh 572 }
1eb9f5a… drh 573 }
1eb9f5a… drh 574 }
1eb9f5a… drh 575 }
275da70… danield 576
1eb9f5a… drh 577 /* Put the deepest (earliest) merge parent first in the list.
1eb9f5a… drh 578 ** An off-screen merge parent is considered deepest.
1eb9f5a… drh 579 */
1eb9f5a… drh 580 for(pRow=p->pFirst; pRow; pRow=pRow->pNext ){
1eb9f5a… drh 581 if( pRow->nParent<=1 ) continue;
1eb9f5a… drh 582 for(i=1; i<pRow->nParent; i++){
1eb9f5a… drh 583 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
1eb9f5a… drh 584 if( pParent ) pParent->nMergeChild++;
1eb9f5a… drh 585 }
1eb9f5a… drh 586 if( pRow->nCherrypick>1 ){
1eb9f5a… drh 587 int iBest = -1;
1eb9f5a… drh 588 int iDeepest = -1;
1eb9f5a… drh 589 for(i=pRow->nNonCherrypick; i<pRow->nParent; i++){
1eb9f5a… drh 590 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
1eb9f5a… drh 591 if( pParent==0 ){
1eb9f5a… drh 592 iBest = i;
1eb9f5a… drh 593 break;
1eb9f5a… drh 594 }
1eb9f5a… drh 595 if( pParent->idx>iDeepest ){
1eb9f5a… drh 596 iDeepest = pParent->idx;
1eb9f5a… drh 597 iBest = i;
1eb9f5a… drh 598 }
1eb9f5a… drh 599 }
1eb9f5a… drh 600 i = pRow->nNonCherrypick;
1eb9f5a… drh 601 if( iBest>i ){
ab71d95… drh 602 GraphRowId x = pRow->aParent[i];
1eb9f5a… drh 603 pRow->aParent[i] = pRow->aParent[iBest];
1eb9f5a… drh 604 pRow->aParent[iBest] = x;
1eb9f5a… drh 605 }
1eb9f5a… drh 606 }
1eb9f5a… drh 607 if( pRow->nNonCherrypick>2 ){
1eb9f5a… drh 608 int iBest = -1;
1eb9f5a… drh 609 int iDeepest = -1;
1eb9f5a… drh 610 for(i=1; i<pRow->nNonCherrypick; i++){
1eb9f5a… drh 611 GraphRow *pParent = hashFind(p, pRow->aParent[i]);
1eb9f5a… drh 612 if( pParent==0 ){
1eb9f5a… drh 613 iBest = i;
1eb9f5a… drh 614 break;
1eb9f5a… drh 615 }
1eb9f5a… drh 616 if( pParent->idx>iDeepest ){
1eb9f5a… drh 617 iDeepest = pParent->idx;
1eb9f5a… drh 618 iBest = i;
1eb9f5a… drh 619 }
1eb9f5a… drh 620 }
1eb9f5a… drh 621 if( iBest>1 ){
ab71d95… drh 622 GraphRowId x = pRow->aParent[1];
1eb9f5a… drh 623 pRow->aParent[1] = pRow->aParent[iBest];
1eb9f5a… drh 624 pRow->aParent[iBest] = x;
65aa10f… drh 625 }
65aa10f… drh 626 }
65aa10f… drh 627 }
65aa10f… drh 628
65aa10f… drh 629 /* If the primary parent is in a different branch, but there are
65aa10f… drh 630 ** other parents in the same branch, reorder the parents to make
65aa10f… drh 631 ** the parent from the same branch the primary parent.
65aa10f… drh 632 */
65aa10f… drh 633 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
65aa10f… drh 634 if( pRow->isDup ) continue;
55ab522… drh 635 if( pRow->nNonCherrypick<2 ) continue; /* Not a fork */
65aa10f… drh 636 pParent = hashFind(p, pRow->aParent[0]);
65aa10f… drh 637 if( pParent==0 ) continue; /* Parent off-screen */
65aa10f… drh 638 if( pParent->zBranch==pRow->zBranch ) continue; /* Same branch */
55ab522… drh 639 for(i=1; i<pRow->nNonCherrypick; i++){
65aa10f… drh 640 pParent = hashFind(p, pRow->aParent[i]);
03250bc… drh 641 if( pParent && pParent->zBranch==pRow->zBranch ){
ab71d95… drh 642 GraphRowId t = pRow->aParent[0];
65aa10f… drh 643 pRow->aParent[0] = pRow->aParent[i];
65aa10f… drh 644 pRow->aParent[i] = t;
65aa10f… drh 645 break;
080ab8c… jan.nijtmans 646 }
080ab8c… jan.nijtmans 647 }
080ab8c… jan.nijtmans 648 }
080ab8c… jan.nijtmans 649
e685fc0… drh 650
080ab8c… jan.nijtmans 651 /* Find the pChild pointer for each node.
98870a8… drh 652 **
cf17857… drh 653 ** The pChild points to the node directly above on the same rail.
98870a8… drh 654 ** The pChild must be in the same branch. Leaf nodes have a NULL
98870a8… drh 655 ** pChild.
98870a8… drh 656 **
98870a8… drh 657 ** In the case of a fork, choose the pChild that results in the
98870a8… drh 658 ** longest rail.
98870a8… drh 659 */
98870a8… drh 660 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
98870a8… drh 661 if( pRow->isDup ) continue;
694e11a… drh 662 if( pRow->nParent<=0 ) continue; /* Root node */
98870a8… drh 663 pParent = hashFind(p, pRow->aParent[0]);
79b81a3… drh 664 if( pParent==0 ) continue; /* Parent off-screen */
79b81a3… drh 665 if( pParent->zBranch!=pRow->zBranch ) continue; /* Different branch */
d7a0240… drh 666 if( pParent->idx <= pRow->idx ){
d14590d… drh 667 pParent->timeWarp = 1;
628fc32… drh 668 nTimewarp++;
7193681… drh 669 }else if( pRow->idxTop < pParent->idxTop ){
98870a8… drh 670 pParent->pChild = pRow;
7193681… drh 671 pParent->idxTop = pRow->idxTop;
98870a8… drh 672 }
98870a8… drh 673 }
98870a8… drh 674
fff033f… drh 675 if( tmFlags & TIMELINE_FILLGAPS ){
90cb547… drh 676 /* If a node has no pChild in the graph
90cb547… drh 677 ** and there is a node higher up in the graph
7193681… drh 678 ** that is in the same branch and has no in-graph parent, then
7193681… drh 679 ** make the lower node a step-child of the upper node. This will
d14590d… drh 680 ** be represented on the graph by a thick dotted line without an arrowhead.
fff033f… drh 681 */
fff033f… drh 682 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
fff033f… drh 683 if( pRow->pChild ) continue;
90cb547… drh 684 if( pRow->isLeaf ) continue;
fff033f… drh 685 for(pLoop=pRow->pPrev; pLoop; pLoop=pLoop->pPrev){
fff033f… drh 686 if( pLoop->nParent>0
fff033f… drh 687 && pLoop->zBranch==pRow->zBranch
fff033f… drh 688 && hashFind(p,pLoop->aParent[0])==0
fff033f… drh 689 ){
fff033f… drh 690 pRow->pChild = pLoop;
fff033f… drh 691 pRow->isStepParent = 1;
fff033f… drh 692 pLoop->aParent[0] = pRow->rid;
fff033f… drh 693 break;
fff033f… drh 694 }
fff033f… drh 695 }
fff033f… drh 696 }
fff033f… drh 697 }
fff033f… drh 698
d14590d… drh 699 /* Set the idxTop values for all entries. The idxTop value is the
d14590d… drh 700 ** "idx" value for the top entry in its stack of children.
d14590d… drh 701 */
d14590d… drh 702 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
d14590d… drh 703 GraphRow *pChild = pRow->pChild;
d14590d… drh 704 if( pChild && pRow->idxTop>pChild->idxTop ){
d14590d… drh 705 pRow->idxTop = pChild->idxTop;
d14590d… drh 706 }
d14590d… drh 707 }
d14590d… drh 708
14c19fb… drh 709 /* Identify rows where the primary parent is off screen. Assign
d14590d… drh 710 ** each to a rail and draw descenders downward.
98870a8… drh 711 **
3a6dd83… drh 712 ** Strive to put the main branch (usually "trunk") on far left.
98870a8… drh 713 */
ca0d66b… danield 714 zMainBranch = db_main_branch();
3a6dd83… drh 715 zTrunk = persistBranchName(p, zMainBranch);
98870a8… drh 716 for(i=0; i<2; i++){
98870a8… drh 717 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
d14590d… drh 718 if( i==0 && pRow->zBranch!=zTrunk ) continue;
d14590d… drh 719 if( pRow->iRail>=0 ) continue;
64aa186… drh 720 if( pRow->isDup ) continue;
694e11a… drh 721 if( pRow->nParent<0 ) continue;
98870a8… drh 722 if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){
d1d7fce… drh 723 pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx+riserMargin,0,0);
a8c6f3a… drh 724 /* if( p->mxRail>=GR_MAX_RAIL ) return; */
8d4ee62… drh 725 mask = BIT(pRow->iRail);
4614dad… drh 726 if( !omitDescenders ){
d14590d… drh 727 int n = RISER_MARGIN;
98870a8… drh 728 pRow->bDescender = pRow->nParent>0;
d14590d… drh 729 for(pLoop=pRow; pLoop && (n--)>0; pLoop=pLoop->pNext){
98870a8… drh 730 pLoop->railInUse |= mask;
98870a8… drh 731 }
98870a8… drh 732 }
d14590d… drh 733 assignChildrenToRail(pRow, tmFlags);
14c19fb… drh 734 }
14c19fb… drh 735 }
14c19fb… drh 736 }
14c19fb… drh 737
14c19fb… drh 738 /* Assign rails to all rows that are still unassigned.
16e703b… drh 739 */
16e703b… drh 740 for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
ab71d95… drh 741 GraphRowId parentRid;
98870a8… drh 742
98870a8… drh 743 if( pRow->iRail>=0 ){
d7a0240… drh 744 if( pRow->pChild==0 && !pRow->timeWarp ){
8ce629f… jan.nijtmans 745 if( !omitDescenders && count_nonbranch_children(pRow->rid)!=0 ){
da4a3b4… drh 746 riser_to_top(pRow);
d7a0240… drh 747 }
d7a0240… drh 748 }
98870a8… drh 749 continue;
98870a8… drh 750 }
694e11a… drh 751 if( pRow->isDup || pRow->nParent<0 ){
cbc84ad… drh 752 continue;
0551ff8… drh 753 }else{
0551ff8… drh 754 assert( pRow->nParent>0 );
0551ff8… drh 755 parentRid = pRow->aParent[0];
98870a8… drh 756 pParent = hashFind(p, parentRid);
98870a8… drh 757 if( pParent==0 ){
0551ff8… drh 758 pRow->iRail = ++p->mxRail;
a8c6f3a… drh 759 if( p->mxRail>=GR_MAX_RAIL ){
a8c6f3a… drh 760 pRow->iRail = p->mxRail = GR_MAX_RAIL;
a8c6f3a… drh 761 p->bOverfull = 1;
a8c6f3a… drh 762 }
8d4ee62… drh 763 pRow->railInUse = BIT(pRow->iRail);
0551ff8… drh 764 continue;
0551ff8… drh 765 }
79b81a3… drh 766 if( pParent->idx>pRow->idx ){
79b81a3… drh 767 /* Common case: Child occurs after parent and is above the
79b81a3… drh 768 ** parent in the timeline */
d14590d… drh 769 pRow->iRail = findFreeRail(p, pRow->idxTop, pParent->idx,
d1d7fce… drh 770 pParent->iRail, 0);
a8c6f3a… drh 771 /* if( p->mxRail>=GR_MAX_RAIL ) return; */
79b81a3… drh 772 pParent->aiRiser[pRow->iRail] = pRow->idx;
79b81a3… drh 773 }else{
79b81a3… drh 774 /* Timewarp case: Child occurs earlier in time than parent and
79b81a3… drh 775 ** appears below the parent in the timeline. */
79b81a3… drh 776 int iDownRail = ++p->mxRail;
9b9d52b… drh 777 if( iDownRail<1 ) iDownRail = ++p->mxRail;
a8c6f3a… drh 778 if( p->mxRail>GR_MAX_RAIL ){
a8c6f3a… drh 779 iDownRail = p->mxRail = GR_MAX_RAIL;
a8c6f3a… drh 780 p->bOverfull = 1;
a8c6f3a… drh 781 }
79b81a3… drh 782 pRow->iRail = ++p->mxRail;
a8c6f3a… drh 783 if( p->mxRail>=GR_MAX_RAIL ){
a8c6f3a… drh 784 pRow->iRail = p->mxRail = GR_MAX_RAIL;
a8c6f3a… drh 785 p->bOverfull = 1;
a8c6f3a… drh 786 }
8d4ee62… drh 787 pRow->railInUse = BIT(pRow->iRail);
79b81a3… drh 788 pParent->aiRiser[iDownRail] = pRow->idx;
8d4ee62… drh 789 mask = BIT(iDownRail);
79b81a3… drh 790 for(pLoop=p->pFirst; pLoop; pLoop=pLoop->pNext){
79b81a3… drh 791 pLoop->railInUse |= mask;
79b81a3… drh 792 }
79b81a3… drh 793 }
ea61f4a… drh 794 }
8d4ee62… drh 795 mask = BIT(pRow->iRail);
ea61f4a… drh 796 pRow->railInUse |= mask;
f734110… drh 797 if( pRow->pChild ){
d14590d… drh 798 assignChildrenToRail(pRow, tmFlags);
8ce629f… jan.nijtmans 799 }else if( !omitDescenders && count_nonbranch_children(pRow->rid)!=0 ){
e806671… drh 800 if( !pRow->timeWarp ) riser_to_top(pRow);
98870a8… drh 801 }
98870a8… drh 802 if( pParent ){
5399c5d… drh 803 if( pParent->idx>pRow->idx ){
5399c5d… drh 804 /* Common case: Parent is below current row in the graph */
5399c5d… drh 805 for(pLoop=pParent->pPrev; pLoop && pLoop!=pRow; pLoop=pLoop->pPrev){
5399c5d… drh 806 pLoop->railInUse |= mask;
5399c5d… drh 807 }
5399c5d… drh 808 }else{
5399c5d… drh 809 /* Timewarp case: Parent is above current row in the graph */
5399c5d… drh 810 for(pLoop=pParent->pNext; pLoop && pLoop!=pRow; pLoop=pLoop->pNext){
5399c5d… drh 811 pLoop->railInUse |= mask;
5399c5d… drh 812 }
98870a8… drh 813 }
98870a8… drh 814 }
14c19fb… drh 815 }
14c19fb… drh 816
14c19fb… drh 817 /*
14c19fb… drh 818 ** Insert merge rails and merge arrows
14c19fb… drh 819 */
14c19fb… drh 820 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
1eb9f5a… drh 821 int iReuseIdx = -1;
1eb9f5a… drh 822 int iReuseRail = -1;
1eb9f5a… drh 823 int isCherrypick = 0;
32c9c47… drh 824 for(i=1; i<pRow->nParent; i++){
ab71d95… drh 825 GraphRowId parentRid = pRow->aParent[i];
1eb9f5a… drh 826 if( i==pRow->nNonCherrypick ){
7688673… drh 827 /* Because full merges are laid out before cherrypicks,
d1d7fce… drh 828 ** it is ok to use a full-merge raiser for a cherrypick.
7688673… drh 829 ** See the graph on check-in 8ac66ef33b464d28 for example
7688673… drh 830 ** iReuseIdx = -1;
7688673… drh 831 ** iReuseRail = -1; */
1eb9f5a… drh 832 isCherrypick = 1;
1eb9f5a… drh 833 }
32c9c47… drh 834 pDesc = hashFind(p, parentRid);
e685fc0… drh 835 if( pDesc==0 ){
0cb6e03… ashepilko 836 int iMrail = -1;
1eb9f5a… drh 837 /* Merge from a node that is off-screen */
1eb9f5a… drh 838 if( iReuseIdx>=p->nRow+1 ){
1eb9f5a… drh 839 continue; /* Suppress multiple off-screen merges */
1eb9f5a… drh 840 }
95d6ddc… drh 841 for(j=0; j<GR_MAX_RAIL; j++){
9ed1343… drh 842 if( mergeRiserFrom[j]==parentRid ){
95d6ddc… drh 843 iMrail = j;
95d6ddc… drh 844 break;
95d6ddc… drh 845 }
95d6ddc… drh 846 }
95d6ddc… drh 847 if( iMrail==-1 ){
d1d7fce… drh 848 iMrail = findFreeRail(p, pRow->idx, p->pLast->idx, 0, 1);
a8c6f3a… drh 849 /*if( p->mxRail>=GR_MAX_RAIL ) return;*/
9ed1343… drh 850 mergeRiserFrom[iMrail] = parentRid;
95d6ddc… drh 851 }
1eb9f5a… drh 852 iReuseIdx = p->nRow+1;
1eb9f5a… drh 853 iReuseRail = iMrail;
8d4ee62… drh 854 mask = BIT(iMrail);
55ab522… drh 855 if( i>=pRow->nNonCherrypick ){
55ab522… drh 856 pRow->mergeIn[iMrail] = 2;
55ab522… drh 857 pRow->cherrypickDown |= mask;
55ab522… drh 858 }else{
55ab522… drh 859 pRow->mergeIn[iMrail] = 1;
55ab522… drh 860 pRow->mergeDown |= mask;
55ab522… drh 861 }
e685fc0… drh 862 for(pLoop=pRow->pNext; pLoop; pLoop=pLoop->pNext){
32c9c47… drh 863 pLoop->railInUse |= mask;
32c9c47… drh 864 }
e685fc0… drh 865 }else{
1eb9f5a… drh 866 /* The merge parent node does exist on this graph */
1eb9f5a… drh 867 if( iReuseIdx>pDesc->idx
1eb9f5a… drh 868 && pDesc->nMergeChild==1
1eb9f5a… drh 869 ){
1eb9f5a… drh 870 /* Reuse an existing merge riser */
1eb9f5a… drh 871 pDesc->mergeOut = iReuseRail;
1eb9f5a… drh 872 if( isCherrypick ){
1eb9f5a… drh 873 pDesc->cherrypickUpto = pDesc->idx;
1eb9f5a… drh 874 }else{
1eb9f5a… drh 875 pDesc->hasNormalOutMerge = 1;
1eb9f5a… drh 876 pDesc->mergeUpto = pDesc->idx;
1eb9f5a… drh 877 }
1eb9f5a… drh 878 }else{
1eb9f5a… drh 879 /* Create a new merge for an on-screen node */
1eb9f5a… drh 880 createMergeRiser(p, pDesc, pRow, isCherrypick);
a8c6f3a… drh 881 /* if( p->mxRail>=GR_MAX_RAIL ) return; */
7688673… drh 882 if( iReuseIdx<0
7688673… drh 883 && pDesc->nMergeChild==1
7688673… drh 884 && (pDesc->iRail!=pDesc->mergeOut || pDesc->isLeaf)
7688673… drh 885 ){
1eb9f5a… drh 886 iReuseIdx = pDesc->idx;
1eb9f5a… drh 887 iReuseRail = pDesc->mergeOut;
1eb9f5a… drh 888 }
1eb9f5a… drh 889 }
32c9c47… drh 890 }
0551ff8… drh 891 }
0551ff8… drh 892 }
0551ff8… drh 893
0551ff8… drh 894 /*
080ab8c… jan.nijtmans 895 ** Insert merge rails from primaries to duplicates.
0551ff8… drh 896 */
a8c6f3a… drh 897 if( hasDup && p->mxRail<GR_MAX_RAIL ){
cbc84ad… drh 898 int dupRail;
64aa186… drh 899 int mxRail;
cbc84ad… drh 900 find_max_rail(p);
64aa186… drh 901 mxRail = p->mxRail;
64aa186… drh 902 dupRail = mxRail+1;
a8c6f3a… drh 903 /* if( p->mxRail>=GR_MAX_RAIL ) return; */
0551ff8… drh 904 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
0551ff8… drh 905 if( !pRow->isDup ) continue;
cbc84ad… drh 906 pRow->iRail = dupRail;
0551ff8… drh 907 pDesc = hashFind(p, pRow->rid);
0551ff8… drh 908 assert( pDesc!=0 && pDesc!=pRow );
55ab522… drh 909 createMergeRiser(p, pDesc, pRow, 0);
ca869aa… drh 910 if( pDesc->mergeOut>mxRail ) mxRail = pDesc->mergeOut;
64aa186… drh 911 }
64aa186… drh 912 if( dupRail<=mxRail ){
64aa186… drh 913 dupRail = mxRail+1;
64aa186… drh 914 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
64aa186… drh 915 if( pRow->isDup ) pRow->iRail = dupRail;
64aa186… drh 916 }
313cd3c… drh 917 }
a8c6f3a… drh 918 /* if( mxRail>=GR_MAX_RAIL ) return; */
7c2577b… drh 919 }
7c2577b… drh 920
7c2577b… drh 921 /*
7c2577b… drh 922 ** Find the maximum rail number.
7c2577b… drh 923 */
cbc84ad… drh 924 find_max_rail(p);
51510bf… drh 925
1e70f82… drh 926 /* If a leaf node has a merge riser going up on a different rail,
1e70f82… drh 927 ** try to move the rail of the node (and its ancestors) to be underneath
1e70f82… drh 928 ** the merge riser. This is an optimization that improves the
1e70f82… drh 929 ** appearance of graph but is not strictly necessary.
1e70f82… drh 930 */
1e70f82… drh 931 if( nTimewarp==0 && p->hasOffsetMergeRiser ){
1e70f82… drh 932 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
1e70f82… drh 933 GraphRow *pBottom; /* Bottom row of a branch */
1e70f82… drh 934 GraphRow *pRoot; /* Node off of which the branch diverges */
1e70f82… drh 935 int iFrom; /* Proposed to move from this rail */
1e70f82… drh 936 int iTo; /* Move the branch to this rail */
1e70f82… drh 937
1e70f82… drh 938 iFrom = pRow->iRail;
1e70f82… drh 939 if( pRow->aiRiser[iFrom]>=0 ) continue; /* Not a leaf */
1e70f82… drh 940 if( pRow->mergeOut<0 ) continue; /* No merge riser */
1e70f82… drh 941 if( pRow->mergeOut==iFrom ) continue; /* Riser already aligned */
1e70f82… drh 942 iTo = pRow->mergeOut;
1e70f82… drh 943
1e70f82… drh 944 /* Find the bottom (oldest) node in the branch */
1e70f82… drh 945 pBottom = 0;
1e70f82… drh 946 for(pLoop=pRow; pLoop; pLoop=pLoop->pNext){
1e70f82… drh 947 if( pLoop->idxTop==pRow->idx ) pBottom = pLoop;
1e70f82… drh 948 }
1e70f82… drh 949 if( pBottom==0 ) continue; /* Not possible */
1e70f82… drh 950
1e70f82… drh 951 /* Verify that the rail we want to shift into is clear */
1e70f82… drh 952 pLoop = pBottom;
1e70f82… drh 953 if( pLoop->pNext ) pLoop = pLoop->pNext;
1e70f82… drh 954 if( !railIsClear(pLoop, pRow->idx+1, iTo) ){
1e70f82… drh 955 /* Other nodes or risers are already using the space that
1e70f82… drh 956 ** we propose to move the pRow branch into. */
1e70f82… drh 957 continue;
1e70f82… drh 958 }
1e70f82… drh 959
1e70f82… drh 960 /* Find the "root" of the branch. The root is a different branch
1e70f82… drh 961 ** from which the pRow branch emerges. There might not be a root
1e70f82… drh 962 ** if the pRow branch started off the bottom of the screen.
1e70f82… drh 963 */
1e70f82… drh 964 for(pRoot=pBottom->pNext; pRoot; pRoot=pRoot->pNext){
33fe72c… drh 965 if( pRoot->aiRiser[iFrom]==pBottom->idx ) break;
1e70f82… drh 966 }
1e70f82… drh 967 if( pRoot && pRoot->iRail==iTo ){
1e70f82… drh 968 /* The parent branch from which this branch emerges is on the
1e70f82… drh 969 ** same rail as pRow. Do not shift as that would stack a child
1e70f82… drh 970 ** branch directly above its parent. */
1e70f82… drh 971 continue;
1e70f82… drh 972 }
1e70f82… drh 973
1e70f82… drh 974 /* All clear. Make the translation
275da70… danield 975 */
1e70f82… drh 976 for(pLoop=pRow; pLoop && pLoop->idx<=pBottom->idx; pLoop=pLoop->pNext){
1e70f82… drh 977 if( pLoop->iRail==iFrom ){
1e70f82… drh 978 pLoop->iRail = iTo;
1e70f82… drh 979 pLoop->aiRiser[iTo] = pLoop->aiRiser[iFrom];
1e70f82… drh 980 pLoop->aiRiser[iFrom] = -1;
1e70f82… drh 981 }
1e70f82… drh 982 }
1e70f82… drh 983 if( pRoot ){
1e70f82… drh 984 pRoot->aiRiser[iTo] = pRoot->aiRiser[iFrom];
1e70f82… drh 985 pRoot->aiRiser[iFrom] = -1;
1e70f82… drh 986 }
1e70f82… drh 987 }
1e70f82… drh 988 }
1e70f82… drh 989
d1d7fce… drh 990 /*
d1d7fce… drh 991 ** Compute the rail mapping that tries to put the branch named
e89ea2c… drh 992 ** pLeftBranch at the left margin. Other branches that merge
e89ea2c… drh 993 ** with pLeftBranch are to the right with merge rails in between.
d1d7fce… drh 994 **
d1d7fce… drh 995 ** aMap[X]=Y means that the X-th rail is drawn as the Y-th rail.
ebbfe7d… drh 996 **
ebbfe7d… drh 997 ** Do not move rails around if there are timewarps, because that can
ebbfe7d… drh 998 ** seriously mess up the display of timewarps. Timewarps should be
ebbfe7d… drh 999 ** rare so this should not be a serious limitation to the algorithm.
d1d7fce… drh 1000 */
d1d7fce… drh 1001 aMap = p->aiRailMap;
ebbfe7d… drh 1002 for(i=0; i<=p->mxRail; i++) aMap[i] = i; /* Set up a default mapping */
d1d7fce… drh 1003 if( nTimewarp==0 ){
055cef4… drh 1004 int kk;
ebbfe7d… drh 1005 /* Priority bits:
ebbfe7d… drh 1006 **
ebbfe7d… drh 1007 ** 0x04 The preferred branch
ebbfe7d… drh 1008 **
b71363e… drh 1009 ** 0x02 A merge rail - a rail that contains merge lines into
b71363e… drh 1010 ** the preferred branch. Only applies if a preferred branch
b71363e… drh 1011 ** is defined. This improves the display of r=BRANCH
b71363e… drh 1012 ** options to /timeline.
ebbfe7d… drh 1013 **
ebbfe7d… drh 1014 ** 0x01 A rail that merges with the preferred branch
ebbfe7d… drh 1015 */
055cef4… drh 1016 u16 aPriority[GR_MAX_RAIL];
055cef4… drh 1017 int mxMatch = 0;
055cef4… drh 1018 memset(aPriority, 0, (p->mxRail+1)*sizeof(aPriority[0]));
e89ea2c… drh 1019 if( pLeftBranch ){
d1d7fce… drh 1020 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
055cef4… drh 1021 int iMatch = match_text(pLeftBranch, pRow->zBranch);
055cef4… drh 1022 if( iMatch>0 ){
055cef4… drh 1023 if( iMatch>10 ) iMatch = 10;
055cef4… drh 1024 aPriority[pRow->iRail] |= 1<<(iMatch+1);
055cef4… drh 1025 if( mxMatch<iMatch ) mxMatch = iMatch;
d1d7fce… drh 1026 for(i=0; i<=p->mxRail; i++){
d1d7fce… drh 1027 if( pRow->mergeIn[i] ) aPriority[i] |= 1;
d1d7fce… drh 1028 }
d1d7fce… drh 1029 if( pRow->mergeOut>=0 ) aPriority[pRow->mergeOut] |= 1;
d1d7fce… drh 1030 }
d1d7fce… drh 1031 }
b71363e… drh 1032 for(i=0; i<=p->mxRail; i++){
b71363e… drh 1033 if( p->mergeRail & BIT(i) ){
b71363e… drh 1034 aPriority[i] |= 2;
b71363e… drh 1035 }
b71363e… drh 1036 }
d1d7fce… drh 1037 }else{
d1d7fce… drh 1038 j = 1;
d1d7fce… drh 1039 aPriority[0] = 4;
055cef4… drh 1040 mxMatch = 1;
d1d7fce… drh 1041 for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
d1d7fce… drh 1042 if( pRow->iRail==0 ){
d1d7fce… drh 1043 for(i=0; i<=p->mxRail; i++){
d1d7fce… drh 1044 if( pRow->mergeIn[i] ) aPriority[i] |= 1;
d1d7fce… drh 1045 }
d1d7fce… drh 1046 if( pRow->mergeOut>=0 ) aPriority[pRow->mergeOut] |= 1;
d1d7fce… drh 1047 }
d1d7fce… drh 1048 }
d1d7fce… drh 1049 }
d1d7fce… drh 1050
d1d7fce… drh 1051 #if 0
d1d7fce… drh 1052 fprintf(stderr,"mergeRail: 0x%llx\n", p->mergeRail);
d1d7fce… drh 1053 fprintf(stderr,"Priority:");
055cef4… drh 1054 for(i=0; i<=p->mxRail; i++){
055cef4… drh 1055 fprintf(stderr," %x.%x",
055cef4… drh 1056 aPriority[i]/4, aPriority[i]&3);
055cef4… drh 1057 }
d1d7fce… drh 1058 fprintf(stderr,"\n");
d1d7fce… drh 1059 #endif
d1d7fce… drh 1060
ebbfe7d… drh 1061 j = 0;
055cef4… drh 1062 for(kk=4; kk<=1<<(mxMatch+1); kk*=2){
055cef4… drh 1063 for(i=0; i<=p->mxRail; i++){
055cef4… drh 1064 if( aPriority[i]>=kk && aPriority[i]<kk*2 ){
055cef4… drh 1065 aMap[i] = j++;
055cef4… drh 1066 }
055cef4… drh 1067 }
d1d7fce… drh 1068 }
d1d7fce… drh 1069 for(i=p->mxRail; i>=0; i--){
d1d7fce… drh 1070 if( aPriority[i]==3 ) aMap[i] = j++;
d1d7fce… drh 1071 }
d1d7fce… drh 1072 for(i=0; i<=p->mxRail; i++){
d1d7fce… drh 1073 if( aPriority[i]==1 || aPriority[i]==2 ) aMap[i] = j++;
d1d7fce… drh 1074 }
d1d7fce… drh 1075 for(i=0; i<=p->mxRail; i++){
d1d7fce… drh 1076 if( aPriority[i]==0 ) aMap[i] = j++;
d1d7fce… drh 1077 }
d19df61… drh 1078 cgi_printf("<!-- aiRailMap =");
d19df61… drh 1079 for(i=0; i<=p->mxRail; i++) cgi_printf(" %d", aMap[i]);
d19df61… drh 1080 cgi_printf(" -->\n");
51510bf… drh 1081 }
51510bf… drh 1082
cae94fe… drh 1083 p->nErr = 0;
14c19fb… drh 1084 }

Keyboard Shortcuts

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