Fossil

  db_finalize(&q);
  if( pGraph ){
    graph_finish(pGraph, 0);
    if( pGraph->nErr ){
      graph_free(pGraph);
      pGraph = 0;
    }else{
      int w = (pGraph->mxRail+1)*pGraph->iRailPitch + 10;
      @ <tr><td></td><td>
      @ <div id="grbtm" style="width:%d(w)px;"></div>
      @     </td><td></td></tr>
    }
  }
  @ </table>
  timeline_output_graph_javascript(pGraph, 0, 1);
  style_footer();
}

*/
#include "config.h"
#include "graph.h"
#include <assert.h>

#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.
*/
struct GraphRow {

  u8 timeWarp;                /* Child is earlier in time */
  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.  -1 if no merge-out */
  u8 mergeIn[GR_MAX_RAIL];    /* Merge in from non-zero rails */
  int aiRiser[GR_MAX_RAIL];   /* Risers from this node to a higher row. */
  int mergeUpto;              /* Draw the mergeOut rail up to this level */
  u64 mergeDown;              /* Draw merge lines up from bottom of graph */

  u64 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 */
  int iRailPitch;            /* Pixels between rail centers */
  GraphRow *pFirst;          /* First row in the list */
  GraphRow *pLast;           /* Last row in the list */
  int nBranch;               /* Number of distinct branches */
  char **azBranch;           /* Names of the branches */
  int nRow;                  /* Number of rows */
  int nHash;                 /* Number of slots in apHash[] */
  GraphRow **apHash;         /* Hash table of GraphRow objects.  Key: rid */
};

#endif

/* The N-th bit */
#define BIT(N)  (((u64)1)<<(N))

/*
** Malloc for zeroed space.  Panic if unable to provide the
** requested space.
*/
void *safeMalloc(int nByte){
  void *p = fossil_malloc(nByte);
  memset(p, 0, nByte);

/*
** Return the index of a rail currently not in use for any row between
** top and bottom, inclusive.  
*/
static int findFreeRail(
  GraphContext *p,         /* The graph context */
  int top, int btm,        /* Span of rows for which the rail is needed */
  u64 inUseMask,           /* Mask or rails already in use */
  int iNearto              /* Find rail nearest to this rail */
){
  GraphRow *pRow;
  int i;
  int iBest = 0;
  int iBestDist = 9999;
  for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
  while( pRow && pRow->idx<=btm ){
    inUseMask |= pRow->railInUse;
    pRow = pRow->pNext;
  }
  for(i=0; i<32; i++){
    if( (inUseMask & BIT(i))==0 ){
      int dist;
      if( iNearto<=0 ){
        return i;
      }
      dist = i - iNearto;
      if( dist<0 ) dist = -dist;
      if( dist<iBestDist ){

/*
** Assign all children of node pBottom to the same rail as pBottom.
*/
static void assignChildrenToRail(GraphRow *pBottom){
  int iRail = pBottom->iRail;
  GraphRow *pCurrent;
  GraphRow *pPrior;
  u64 mask = ((u64)1)<<iRail;

  pBottom->iRail = iRail;
  pBottom->railInUse |= mask;
  pPrior = pBottom;
  for(pCurrent=pBottom->pChild; pCurrent; pCurrent=pCurrent->pChild){
    assert( pPrior->idx > pCurrent->idx );
    assert( pCurrent->iRail<0 );

*/
static void createMergeRiser(
  GraphContext *p,
  GraphRow *pParent,
  GraphRow *pChild
){
  int u;
  u64 mask;
  GraphRow *pLoop;

  if( pParent->mergeOut<0 ){
    u = pParent->aiRiser[pParent->iRail];
    if( u>=0 && u<pChild->idx ){
      /* The thick arrow up to the next primary child of pDesc goes
      ** further up than the thin merge arrow riser, so draw them both
      ** on the same rail. */
      pParent->mergeOut = pParent->iRail*4;
      if( pParent->iRail<pChild->iRail ) pParent->mergeOut += 2;
      pParent->mergeUpto = pChild->idx;
    }else{
      /* The thin merge arrow riser is taller than the thick primary
      ** child riser, so use separate rails. */
      int iTarget = pParent->iRail;
      pParent->mergeOut = findFreeRail(p, pChild->idx, pParent->idx-1,
                                       0, iTarget)*4 + 1;
      pParent->mergeUpto = pChild->idx;
      mask = BIT(pParent->mergeOut/4);
      for(pLoop=pChild->pNext; pLoop && pLoop->rid!=pParent->rid;
           pLoop=pLoop->pNext){
        pLoop->railInUse |= mask;
      }
    }
  }
  pChild->mergeIn[pParent->mergeOut/4] = (pParent->mergeOut&3)+1;
}

/*
** Compute the maximum rail number.
*/
static void find_max_rail(GraphContext *p){
  GraphRow *pRow;
  p->mxRail = 0;
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->iRail>p->mxRail ) p->mxRail = pRow->iRail;
    if( pRow->mergeOut/4>p->mxRail ) p->mxRail = pRow->mergeOut/4;
    while( p->mxRail<GR_MAX_RAIL && pRow->mergeDown>(BIT(p->mxRail+1)-1) ){
      p->mxRail++;
    }
  }
}


/*
** Compute the complete graph
*/
void graph_finish(GraphContext *p, int omitDescenders){
  GraphRow *pRow, *pDesc, *pDup, *pLoop, *pParent;
  int i;
  u64 mask;
  u64 inUse;
  int hasDup = 0;      /* True if one or more isDup entries */
  const char *zTrunk;

  if( p==0 || p->pFirst==0 || p->nErr ) return;
  p->nErr = 1;   /* Assume an error until proven otherwise */

  /* Initialize all rows */

      if( pRow->nParent==0 || hashFind(p,pRow->aParent[0])==0 ){
        if( omitDescenders ){
          pRow->iRail = findFreeRail(p, pRow->idxTop, pRow->idx, 0, 0);
        }else{
          pRow->iRail = ++p->mxRail;
        }
        if( p->mxRail>=GR_MAX_RAIL ) return;
        mask = BIT(pRow->iRail);
        if( !omitDescenders ){
          pRow->bDescender = pRow->nParent>0;
          for(pLoop=pRow; pLoop; pLoop=pLoop->pNext){
            pLoop->railInUse |= mask;
          }
        }
        assignChildrenToRail(pRow);
      }
    }
  }

  /* Assign rails to all rows that are still unassigned.
  */
  inUse = BIT(p->mxRail+1) - 1;
  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 ){
          inUse &= ~BIT(pRow->iRail);
        }else{
          pRow->aiRiser[pRow->iRail] = 0;
          mask = BIT(pRow->iRail);
          for(pLoop=pRow; pLoop; pLoop=pLoop->pPrev){
            pLoop->railInUse |= mask;
          }
        }
      }
      continue;
    }
    if( pRow->isDup ){
      continue;
    }else{
      assert( pRow->nParent>0 );
      parentRid = pRow->aParent[0];
      pParent = hashFind(p, parentRid);
      if( pParent==0 ){
        pRow->iRail = ++p->mxRail;
        if( p->mxRail>=GR_MAX_RAIL ) return;
        pRow->railInUse = BIT(pRow->iRail);
        continue;
      }
      if( pParent->idx>pRow->idx ){
        /* Common case:  Child occurs after parent and is above the
        ** parent in the timeline */
        pRow->iRail = findFreeRail(p, 0, pParent->idx, inUse, pParent->iRail);
        if( p->mxRail>=GR_MAX_RAIL ) return;
        pParent->aiRiser[pRow->iRail] = pRow->idx;
      }else{
        /* Timewarp case:  Child occurs earlier in time than parent and
        ** appears below the parent in the timeline. */
        int iDownRail = ++p->mxRail;
        if( iDownRail<1 ) iDownRail = ++p->mxRail;
        pRow->iRail = ++p->mxRail;
        if( p->mxRail>=GR_MAX_RAIL ) return;
        pRow->railInUse = BIT(pRow->iRail);
        pParent->aiRiser[iDownRail] = pRow->idx;
        mask = BIT(iDownRail);
        inUse |= mask;
        for(pLoop=p->pFirst; pLoop; pLoop=pLoop->pNext){
          pLoop->railInUse |= mask;
        }
      }
    }
    mask = BIT(pRow->iRail);
    pRow->railInUse |= mask;
    if( pRow->pChild==0 ){
      inUse &= ~mask;
    }else{
      inUse |= mask;
      assignChildrenToRail(pRow);
    }

    for(i=1; i<pRow->nParent; i++){
      int parentRid = pRow->aParent[i];
      pDesc = hashFind(p, parentRid);
      if( pDesc==0 ){
        /* Merge from a node that is off-screen */
        int iMrail = findFreeRail(p, pRow->idx, p->nRow, 0, 0);
        if( p->mxRail>=GR_MAX_RAIL ) return;
        mask = BIT(iMrail);
        pRow->mergeIn[iMrail] = 2;
        pRow->mergeDown |= mask;
        for(pLoop=pRow->pNext; pLoop; pLoop=pLoop->pNext){
          pLoop->railInUse |= mask;
        }
      }else{
        /* Merge from an on-screen node */

    if( mxRail>=GR_MAX_RAIL ) return;
  }

  /*
  ** Find the maximum rail number.
  */
  find_max_rail(p);
  p->iRailPitch = 18 - (p->mxRail/3);
  if( p->iRailPitch<12 ) p->iRailPitch = 12;
  p->nErr = 0;
}

      graph_free(pGraph);
      pGraph = 0;
    }else{
      int w;
      /* style is not moved to css, because this is
      ** a technical div for the timeline graph
      */


      w = (pGraph->mxRail+1)*pGraph->iRailPitch + 10;
      @ <tr><td></td><td>
      @ <div id="grbtm" style="width:%d(w)px;"></div>
      @ </td><td></td></tr>
    }
  }
  @ </table>
  if( fchngQueryInit ) db_finalize(&fchngQuery);