Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | For the graph drawing routines, make the graph row identifier a 64-bit integer type to avoid the possibility of integer overflow in /finfo where the row ids are a composite of the blob.rid and filename.fnid and hence might become large for repositories with many files and many check-ins. |
---|---|
Downloads: | Tarball | ZIP archive | SQL archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA3-256: |
ab71d95a9f3263699fc4e64e2f8a6ea9 |
User & Date: | drh 2020-10-20 00:20:35 |
Context
2020-10-20
| ||
10:08 | Small tweaks to the CAP Theorem doc ... (check-in: 67a4c1d3 user: wyoung tags: trunk) | |
00:20 | For the graph drawing routines, make the graph row identifier a 64-bit integer type to avoid the possibility of integer overflow in /finfo where the row ids are a composite of the blob.rid and filename.fnid and hence might become large for repositories with many files and many check-ins. ... (check-in: ab71d95a user: drh tags: trunk) | |
2020-10-19
| ||
20:52 | Update the built-in SQLite to fix a bug introduced by the previous update. ... (check-in: 0fac549b user: drh tags: trunk) | |
Changes
Changes to src/finfo.c.
︙ | ︙ | |||
576 577 578 579 580 581 582 | int pfnid = db_column_int(&q, 11); int szFile = db_column_int(&q, 12); int fnid = db_column_int(&q, 13); const char *zFName = db_column_text(&q,14); int gidx; char zTime[10]; int nParent = 0; | | | | | | | 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 | int pfnid = db_column_int(&q, 11); int szFile = db_column_int(&q, 12); int fnid = db_column_int(&q, 13); const char *zFName = db_column_text(&q,14); int gidx; char zTime[10]; int nParent = 0; GraphRowId aParent[GR_MAX_RAIL]; db_bind_int(&qparent, ":fid", frid); db_bind_int(&qparent, ":mid", fmid); db_bind_int(&qparent, ":fnid", fnid); while( db_step(&qparent)==SQLITE_ROW && nParent<count(aParent) ){ aParent[nParent] = db_column_int64(&qparent, 0); nParent++; } db_reset(&qparent); if( zBr==0 ) zBr = "trunk"; if( uBg ){ zBgClr = hash_color(zUser); }else if( brBg || zBgClr==0 || zBgClr[0]==0 ){ zBgClr = strcmp(zBr,"trunk")==0 ? "" : hash_color(zBr); } gidx = graph_add_row(pGraph, frid>0 ? (GraphRowId)frid*(mxfnid+1)+fnid : fpid+1000000000, nParent, 0, aParent, zBr, zBgClr, zUuid, 0); if( strncmp(zDate, zPrevDate, 10) ){ sqlite3_snprintf(sizeof(zPrevDate), zPrevDate, "%.10s", zDate); @ <tr><td> @ <div class="divider timelineDate">%s(zPrevDate)</div> @ </td><td></td><td></td></tr> } memcpy(zTime, &zDate[11], 5); |
︙ | ︙ | |||
717 718 719 720 721 722 723 | } @ </span></span> } if( fDebug & FINFO_DEBUG_MLINK ){ int ii; char *zAncLink; @ <br />fid=%d(frid) \ | | | | | 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 | } @ </span></span> } if( fDebug & FINFO_DEBUG_MLINK ){ int ii; char *zAncLink; @ <br />fid=%d(frid) \ @ graph-id=%lld(frid>0?(GraphRowId)frid*(mxfnid+1)+fnid:fpid+1000000000) \ @ pid=%d(fpid) mid=%d(fmid) fnid=%d(fnid) \ @ pfnid=%d(pfnid) mxfnid=%d(mxfnid) if( nParent>0 ){ @ parents=%lld(aParent[0]) for(ii=1; ii<nParent; ii++){ @ %lld(aParent[ii]) } } zAncLink = href("%R/finfo?name=%T&from=%!S&debug=1",zFName,zCkin); @ %z(zAncLink)[ancestry]</a> } tag_private_status(frid); /* End timelineDetail */ |
︙ | ︙ |
Changes to src/graph.c.
︙ | ︙ | |||
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | ** 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 { | > > > > > > > > > > > > | | | 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 | ** 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 /* ** The type of integer identifiers for rows of the graph. ** ** For a normal /timeline graph, the identifiers are never that big ** an an ordinary 32-bit int will work fine. But for the /finfo page, ** the identifier is a combination of the BLOB.RID and the FILENAME.FNID ** values, and so it can become quite large for repos that have both many ** check-ins and many files. For this reason, we make the identifier ** a 64-bit integer, to dramatically reduce the risk of an overflow. */ typedef sqlite3_int64 GraphRowId; #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 { GraphRowId 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 */ u8 nMergeChild; /* Number of merge children */ GraphRowId *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 */ |
︙ | ︙ | |||
174 175 176 177 178 179 180 | p->apHash[h] = pRow; } } /* ** Look up the row with rid. */ | | | 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 | p->apHash[h] = pRow; } } /* ** Look up the row with rid. */ static GraphRow *hashFind(GraphContext *p, GraphRowId rid){ int h = rid % p->nHash; while( p->apHash[h] && p->apHash[h]->rid!=rid ){ h++; if( h>=p->nHash ) h = 0; } return p->apHash[h]; } |
︙ | ︙ | |||
210 211 212 213 214 215 216 | } /* ** Add a new row to the graph context. Rows are added from top to bottom. */ int graph_add_row( GraphContext *p, /* The context to which the row is added */ | | | | | 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 | } /* ** Add a new row to the graph context. Rows are added from top to bottom. */ int graph_add_row( GraphContext *p, /* The context to which the row is added */ GraphRowId rid, /* RID for the check-in */ int nParent, /* Number of parents */ int nCherrypick, /* How many of aParent[] are actually cherrypicks */ GraphRowId *aParent, /* Array of parents */ const char *zBranch, /* Branch for this check-in */ const char *zBgClr, /* Background color. NULL or "" for white. */ const char *zUuid, /* hash name of the object being graphed */ int isLeaf /* True if this row is a leaf */ ){ GraphRow *pRow; int nByte; static int nRow = 0; if( p->nErr ) return 0; nByte = sizeof(GraphRow); if( nParent>0 ) nByte += sizeof(pRow->aParent[0])*nParent; pRow = (GraphRow*)safeMalloc( nByte ); pRow->aParent = nParent>0 ? (GraphRowId*)&pRow[1] : 0; pRow->rid = rid; if( nCherrypick>=nParent ){ nCherrypick = nParent-1; /* Safety. Should never happen. */ } pRow->nParent = nParent; pRow->nCherrypick = nCherrypick; pRow->nNonCherrypick = nParent - nCherrypick; |
︙ | ︙ | |||
438 439 440 441 442 443 444 | int nTimewarp = 0; int riserMargin = (tmFlags & TIMELINE_DISJOINT) ? 0 : RISER_MARGIN; /* If mergeRiserFrom[X]==Y that means rail X holds a merge riser ** coming up from the bottom of the graph from off-screen check-in Y ** where Y is the RID. There is no riser on rail X if mergeRiserFrom[X]==0. */ | | | 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 | int nTimewarp = 0; int riserMargin = (tmFlags & TIMELINE_DISJOINT) ? 0 : RISER_MARGIN; /* If mergeRiserFrom[X]==Y that means rail X holds a merge riser ** coming up from the bottom of the graph from off-screen check-in Y ** where Y is the RID. There is no riser on rail X if mergeRiserFrom[X]==0. */ GraphRowId mergeRiserFrom[GR_MAX_RAIL]; if( p==0 || p->pFirst==0 || p->nErr ) return; p->nErr = 1; /* Assume an error until proven otherwise */ /* Initialize all rows */ p->nHash = p->nRow*2 + 1; p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash ); |
︙ | ︙ | |||
512 513 514 515 516 517 518 | if( pParent->idx>iDeepest ){ iDeepest = pParent->idx; iBest = i; } } i = pRow->nNonCherrypick; if( iBest>i ){ | | | | | 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 | if( pParent->idx>iDeepest ){ iDeepest = pParent->idx; iBest = i; } } i = pRow->nNonCherrypick; if( iBest>i ){ GraphRowId x = pRow->aParent[i]; pRow->aParent[i] = pRow->aParent[iBest]; pRow->aParent[iBest] = x; } } if( pRow->nNonCherrypick>2 ){ int iBest = -1; int iDeepest = -1; for(i=1; i<pRow->nNonCherrypick; i++){ GraphRow *pParent = hashFind(p, pRow->aParent[i]); if( pParent==0 ){ iBest = i; break; } if( pParent->idx>iDeepest ){ iDeepest = pParent->idx; iBest = i; } } if( iBest>1 ){ GraphRowId x = pRow->aParent[1]; pRow->aParent[1] = pRow->aParent[iBest]; pRow->aParent[iBest] = x; } } } /* If the primary parent is in a different branch, but there are ** other parents in the same branch, reorder the parents to make ** the parent from the same branch the primary parent. */ for(pRow=p->pFirst; pRow; pRow=pRow->pNext){ if( pRow->isDup ) continue; if( pRow->nNonCherrypick<2 ) continue; /* Not a fork */ pParent = hashFind(p, pRow->aParent[0]); if( pParent==0 ) continue; /* Parent off-screen */ if( pParent->zBranch==pRow->zBranch ) continue; /* Same branch */ for(i=1; i<pRow->nNonCherrypick; i++){ pParent = hashFind(p, pRow->aParent[i]); if( pParent && pParent->zBranch==pRow->zBranch ){ GraphRowId t = pRow->aParent[0]; pRow->aParent[0] = pRow->aParent[i]; pRow->aParent[i] = t; break; } } } |
︙ | ︙ | |||
650 651 652 653 654 655 656 | } } } /* Assign rails to all rows that are still unassigned. */ for(pRow=p->pLast; pRow; pRow=pRow->pPrev){ | | | 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 | } } } /* Assign rails to all rows that are still unassigned. */ for(pRow=p->pLast; pRow; pRow=pRow->pPrev){ GraphRowId parentRid; if( pRow->iRail>=0 ){ if( pRow->pChild==0 && !pRow->timeWarp ){ if( !omitDescenders && count_nonbranch_children(pRow->rid)!=0 ){ riser_to_top(pRow); } } |
︙ | ︙ | |||
724 725 726 727 728 729 730 | ** Insert merge rails and merge arrows */ for(pRow=p->pFirst; pRow; pRow=pRow->pNext){ int iReuseIdx = -1; int iReuseRail = -1; int isCherrypick = 0; for(i=1; i<pRow->nParent; i++){ | | | 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 | ** Insert merge rails and merge arrows */ for(pRow=p->pFirst; pRow; pRow=pRow->pNext){ int iReuseIdx = -1; int iReuseRail = -1; int isCherrypick = 0; for(i=1; i<pRow->nParent; i++){ GraphRowId parentRid = pRow->aParent[i]; if( i==pRow->nNonCherrypick ){ /* Because full merges are laid out before cherrypicks, ** it is ok to use a full-merge raise for a cherrypick. ** See the graph on check-in 8ac66ef33b464d28 for example ** iReuseIdx = -1; ** iReuseRail = -1; */ isCherrypick = 1; |
︙ | ︙ |
Changes to src/timeline.c.
︙ | ︙ | |||
482 483 484 485 486 487 488 | zBgClr = hash_color(zBr); } } } if( zType[0]=='c' && pGraph ){ int nParent = 0; int nCherrypick = 0; | | | 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 | zBgClr = hash_color(zBr); } } } if( zType[0]=='c' && pGraph ){ int nParent = 0; int nCherrypick = 0; GraphRowId aParent[GR_MAX_RAIL]; static Stmt qparent; db_static_prepare(&qparent, "SELECT pid FROM plink" " WHERE cid=:rid AND pid NOT IN phantom" " ORDER BY isprim DESC /*sort*/" ); db_bind_int(&qparent, ":rid", rid); |
︙ | ︙ |