Fossil

/*
** Typedef for a 64-bit integer
*/
typedef sqlite3_int64 i64;
typedef sqlite3_uint64 u64;

/*
** 8-bit types
*/
typedef unsigned char u8;
typedef signed char i8;

/* In the timeline, check-in messages are truncated at the first space
** that is more than MX_CKIN_MSG from the beginning, or at the first
** paragraph break that is more than MN_CKIN_MSG from the beginning.
*/
#define MN_CKIN_MSG   100
#define MX_CKIN_MSG   300

/* 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.
*/
struct GraphRow {
  int rid;                    /* The rid for the check-in */
  i8 nParent;                 /* Number of parents */
  int aParent[GR_MAX_PARENT]; /* Array of parents.  0 element is primary .*/
  char *zBranch;              /* Branch name */
  char *zBgClr;               /* Background Color */

  GraphRow *pNext;            /* Next row down in the list of all rows */
  GraphRow *pPrev;            /* Previous row */
  
  int idx;                    /* Row index.  First is 1.  0 used for "none" */
  int idxTop;                 /* Direct descendent highest up on the graph */
  GraphRow *pChild;           /* Child immediately above this node */
  u8 isDup;                   /* True if this is duplicate of a prior entry */
  u8 bDescender;              /* True if riser from bottom of graph to here. */
  i8 iRail;                   /* Which rail this check-in appears on. 0-based.*/
  i8 mergeOut;                /* Merge out to this rail */
  int aiRiser[GR_MAX_RAIL];   /* Risers from this node to a higher row. */

  u32 mergeIn;                /* Merge in from other rails */

  int mergeUpto;              /* Draw the merge rail up to this level */
  u32 mergeDown;              /* Draw merge lines up from bottom of graph */

  u32 railInUse;              /* Mask of occupied rails at this row */
};

/* Context while building a graph
*/
struct GraphContext {
  int nErr;                  /* Number of errors encountered */
  int mxRail;                /* Number of rails required to render the graph */

  pBottom->railInUse |= mask;
  pPrior = pBottom;
  for(pCurrent=pBottom->pChild; pCurrent; pCurrent=pCurrent->pChild){
    assert( pPrior->idx > pCurrent->idx );
    assert( pCurrent->iRail<0 );
    pCurrent->iRail = iRail;
    pCurrent->railInUse |= mask;
    pPrior->aiRiser[iRail] = pCurrent->idx;
    while( pPrior->idx > pCurrent->idx ){
      pPrior->railInUse |= mask;
      pPrior = pPrior->pPrev;
      assert( pPrior!=0 );
    }
  }
}

    if( (pDup = hashFind(p, pRow->rid))!=0 ){
      hasDup = 1;
      pDup->isDup = 1;
    }
    hashInsert(p, pRow, 1);
  }
  p->mxRail = -1;

  /* Purge merge-parents that are out-of-graph if descenders are not
  ** drawn.
  **
  ** Each node has one primary parent and zero or more "merge" parents.
  ** A merge parent is a prior checkin from which changes were merged into
  ** the current check-in.  If a merge parent is not in the visible section
  ** of this graph, then no arrows will be drawn for it, so remove it from
  ** the aParent[] array.
  */
  if( omitDescenders ){
    for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
      for(i=1; i<pRow->nParent; i++){
        if( hashFind(p, pRow->aParent[i])==0 ){
          pRow->aParent[i] = pRow->aParent[--pRow->nParent];
          i--;
        }
      }
    }
  }


  /* Find the pChild pointer for each node. 
  **
  ** The pChild points to the node directly above on the same rail.
  ** The pChild must be in the same branch.  Leaf nodes have a NULL
  ** pChild.
  **

      if( pParent==0 ){
        /* Time skew */
        pRow->iRail = ++p->mxRail;
        pRow->railInUse = 1<<pRow->iRail;
        continue;
      }
      pRow->iRail = findFreeRail(p, 0, pParent->idx, inUse, pParent->iRail);
      pParent->aiRiser[pRow->iRail] = pRow->idx;
    }
    mask = 1<<pRow->iRail;
    pRow->railInUse |= mask;
    if( pRow->pChild==0 ){
      inUse &= ~mask;
    }else{
      inUse |= mask;

void timeline_output_graph_javascript(GraphContext *pGraph){
  if( pGraph && pGraph->nErr==0 ){
    GraphRow *pRow;
    int i;
    char cSep;
    @ <script  type="text/JavaScript">
    @ /* <![CDATA[ */

    /* the rowinfo[] array contains all the information needed to generate
    ** the graph.  Each entry contains information for a single row:
    **
    **   id:  The id of the <div> element for the row. This is an integer.
    **        to get an actual id, prepend "m" to the integer.  The top node
    **        is 1 and numbers increase moving down the timeline.
    **   bg:  The background color for this row
    **    r:  The "rail" that the node for this row sits on.  The left-most
    **        rail is 0 and the number increases to the right.
    **    d:  True if there is a "descender" - an arrow coming from the bottom
    **        of the page straight up to this node.
    **   mo:  "merge-out".  If non-negative, this is a rail number on which
    **        a merge arrow travels upward.  The merge arrow is drawn upwards
    **        to the row identified by mu:.  This value is negative then
    **        node has no merge children and no merge-out line is drawn.
    **   mu:  The id of the row which is the top of the merge-out arrow.
    **   md:  A bitmask of rails on which merge-arrow descenders should be
    **        drawn from this row to the bottom of the page.  The least
    **        significant bit (1) corresponds to rail 0.  The 2-bit corresponds
    **        to rail 1.  And so forth.  This value is 0 if there are no
    **        merge-arrow descenders.
    **    u:  Draw a think child-line out of the top of this node and up to
    **        the node with an id equal to this value.  0 if there is no
    **        thick-line riser.
    **   au:  An array of integers that define thick-line risers for branches.
    **        The integers are in pairs.  For each pair, the first integer is
    **        is the rail on which the riser should run and the second integer
    **        is the id of the node upto which the riser should run.
    **   mi:  "merge-in".  An array of integer rail numbers from which
    **        merge arrows should be drawn into this node.
    */
    cgi_printf("var rowinfo = [\n");
    for(pRow=pGraph->pFirst; pRow; pRow=pRow->pNext){
      cgi_printf("{id:%d,bg:\"%s\",r:%d,d:%d,mo:%d,mu:%d,md:%u,u:%d,au:",
        pRow->idx,
        pRow->zBgClr,
        pRow->iRail,
        pRow->bDescender,
        pRow->mergeOut,
        pRow->mergeUpto,
        pRow->mergeDown,
        pRow->aiRiser[pRow->iRail]
      );
      cSep = '[';
      for(i=0; i<GR_MAX_RAIL; i++){
        if( i==pRow->iRail ) continue;
        if( pRow->aiRiser[i]>0 ){
          cgi_printf("%c%d,%d", cSep, i, pRow->aiRiser[i]);
          cSep = ',';
        }
      }
      if( cSep=='[' ) cgi_printf("[");
      cgi_printf("],mi:");
      cSep = '[';
      for(i=0; i<GR_MAX_RAIL; i++){

    @ }
    @ function renderGraph(){
    @   var canvasDiv = document.getElementById("canvas");
    @   while( canvasDiv.hasChildNodes() ){
    @     canvasDiv.removeChild(canvasDiv.firstChild);
    @   }
    @   var canvasY = absoluteY("timelineTable");
    @   var left = absoluteX("m"+rowinfo[0].id) - absoluteX("canvas") + 15;
    @   var width = nrail*20;
    @   for(var i in rowinfo){
    @     rowinfo[i].y = absoluteY("m"+rowinfo[i].id) + 10 - canvasY;
    @     rowinfo[i].x = left + rowinfo[i].r*20;
    @   }
    @   var btm = absoluteY("grbtm") + 10 - canvasY;
    @   if( btm<32768 ){
    @     canvasDiv.innerHTML = '<canvas id="timeline-canvas" '+
    @        'style="position:absolute;left:'+(left-5)+'px;"' +
    @        ' width="'+width+'" height="'+btm+'"><'+'/canvas>';

    @       context.fillRect(x0-left+5,y0,x1-x0+1,y1-y0+1);
    @     };
    @   }
    @   for(var i in rowinfo){
    @     drawNode(rowinfo[i], left, btm);
    @   }
    @ }
    @ var lastId = "m"+rowinfo[rowinfo.length-1].id;
    @ var lastY = 0;
    @ function checkHeight(){
    @   var h = absoluteY(lastId);
    @   if( h!=lastY ){
    @     renderGraph();
    @     lastY = h;
    @   }

<title>Graph Test One</title>

This page contains examples a list of URLs of timelines with
interesting graphs.  Click on all URLs, one by one, to verify 
the correct operation of the graph drawing logic.

  *  [/timeline?n=20&y=ci&b=2010-11-08]
  *  [/timeline?n=40&y=ci&b=2010-11-08]
  *  [/timeline?n=1000&y=ci&b=2010-11-08]
  *  [/timeline?f=3ea66260b5555d2e]
  *  [/timeline?r=experimental]
  *  [/timeline?r=experimental&n=1000]
  *  [/timeline?r=creole]
  *  [/timeline?t=creole]
  *  [/timeline?t=release]
  *  [/timeline?r=release]
  *  [/finfo?name=Makefile]
  *  [/timeline?a=1970-01-01]