Fossil

Check-in [ab71d95a]
Login

Check-in [ab71d95a]

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: ab71d95a9f3263699fc4e64e2f8a6ea9dfa6afffbec8e611d21bff6e77bfadc0
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
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/finfo.c.

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;
    int 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_int(&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 ? 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);







|





|










|
|
|







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
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=%d(frid>0 ? 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=%d(aParent[0])
        for(ii=1; ii<nParent; ii++){
          @ %d(aParent[ii])
        }
      }
      zAncLink = href("%R/finfo?name=%T&from=%!S&debug=1",zFName,zCkin);
      @ %z(zAncLink)[ancestry]</a>
    }
    tag_private_status(frid);
    /* End timelineDetail */







|



|

|







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
57
58
59
60
61
62
63
64
65
66
67
68
69
** 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 */
  u8 nMergeChild;             /* Number of merge children */
  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 */








>
>
>
>
>
>
>
>
>
>
>
>











|




|







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
181
182
183
184
185
186
187
188
    p->apHash[h] = pRow;
  }
}

/*
** Look up the row with rid.
*/
static GraphRow *hashFind(GraphContext *p, int 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];
}







|







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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
}

/*
** 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 */
  int rid,             /* RID for the check-in */
  int nParent,         /* Number of parents */
  int nCherrypick,     /* How many of aParent[] are actually cherrypicks */
  int *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 ? (int*)&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;







|


|













|







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
445
446
447
448
449
450
451
452
  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.
  */
  int 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 );







|







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
519
520
521
522
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
        if( pParent->idx>iDeepest ){
          iDeepest = pParent->idx;
          iBest = i;
        }
      }
      i = pRow->nNonCherrypick;
      if( iBest>i ){
        int 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 ){
        int 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 ){
        int t = pRow->aParent[0];
        pRow->aParent[0] = pRow->aParent[i];
        pRow->aParent[i] = t;
        break;
      }
    }
  }








|



















|



















|







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
657
658
659
660
661
662
663
664
      }
    }
  }

  /* Assign rails to all rows that are still unassigned.
  */
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
    int parentRid;

    if( pRow->iRail>=0 ){
      if( pRow->pChild==0 && !pRow->timeWarp ){
        if( !omitDescenders && count_nonbranch_children(pRow->rid)!=0 ){
          riser_to_top(pRow);
        }
      }







|







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
731
732
733
734
735
736
737
738
  ** 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++){
      int 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;







|







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
489
490
491
492
493
494
495
496
          zBgClr = hash_color(zBr);
        }
      }
    }
    if( zType[0]=='c' && pGraph ){
      int nParent = 0;
      int nCherrypick = 0;
      int 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);







|







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);