Fossil

**
** This file contains code used to trace paths of through the
** directed acyclic graph (DAG) of check-ins.
*/
#include "config.h"
#include "path.h"
#include <assert.h>
#include <math.h>

#if INTERFACE
/* Nodes for the paths through the DAG.
*/
struct PathNode {
  int rid;                 /* ID for this node */
  u8 fromIsParent;         /* True if pFrom is the parent of rid */
  u8 isPrim;               /* True if primary side of common ancestor */
  u8 isHidden;             /* Abbreviate output in "fossil bisect ls" */

  char *zBranch;           /* Branch name for this node.  Might be NULL */
  double mtime;            /* Date/time of this check-in */
  PathNode *pFrom;         /* Node we came from */
  union {
    double rCost;          /* Cost of getting to this node from pStart */
    PathNode *pTo;         /* Next on path from beginning to end */
  } u;
  PathNode *pAll;          /* List of all nodes */
};
#endif

/*
** Local variables for this module
*/
static struct {
  PQueue pending;       /* Nodes pending review for inclusion in the graph */
  PathNode *pAll;       /* All nodes */

  int nStep;            /* Number of steps from first to last */
  int nNotHidden;       /* Number of steps not counting hidden nodes */
  int brCost;           /* Extra cost for moving to a different branch */
  int revCost;          /* Extra cost for changing directions */
  PathNode *pStart;     /* Earliest node */
  PathNode *pEnd;       /* Most recent */
} path;

/*
** Return the first (last) element of the computed path.
*/

/*
** Return the number of non-hidden steps in the computed path.
*/
int path_length_not_hidden(void){ return path.nNotHidden; }

/*
** Create a new node and insert it into the path.pending queue.
*/
static PathNode *path_new_node(int rid, PathNode *pFrom, int isParent){
  PathNode *p;

  p = fossil_malloc( sizeof(*p) );
  memset(p, 0, sizeof(*p));
  p->pAll = path.pAll;
  path.pAll = p;
  p->rid = rid;
  p->fromIsParent = isParent;
  p->pFrom = pFrom;
  p->u.rCost = pFrom ? pFrom->u.rCost : 0.0;
  if( path.brCost ){
    p->zBranch = branch_of_rid(rid);
    p->mtime = mtime_of_rid(rid, 0.0);
    if( pFrom ){
      p->u.rCost +=  fabs(pFrom->mtime - p->mtime);
      if( fossil_strcmp(p->zBranch, pFrom->zBranch)!=0 ){
        p->u.rCost += path.brCost;
      }
    }
  }else{
    /* When brCost==0, we try to minimize the number of nodes
    ** along the path.  The cost is just the number of nodes back
    ** to the start.  We do not need to know the branch name nor
    ** the mtime */
    p->u.rCost += 1.0;
  }
  pqueuex_insert_ptr(&path.pending, (void*)p, p->u.rCost);

  return p;
}

/*
** Reset memory used by the shortest path algorithm.
*/
void path_reset(void){
  PathNode *p;
  while( path.pAll ){
    p = path.pAll;
    path.pAll = p->pAll;
    fossil_free(p->zBranch);
    fossil_free(p);
  }
  pqueuex_clear(&path.pending);
  memset(&path, 0, sizeof(path));
}

/*
** Construct the path from path.pStart to path.pEnd in the u.pTo fields.
*/
static void path_reverse_path(void){

  int iTo,            /* Path ends here */
  int directOnly,     /* No merge links if true */
  int oneWayOnly,     /* Parent->child only if true */
  Bag *pHidden,       /* Hidden nodes */
  int branchCost      /* Add extra codes to changing branches */
){
  Stmt s;
  Bag seen;
  PathNode *p;


  path_reset();
  path.brCost = branchCost;
  path.pStart = path_new_node(iFrom, 0, 0);
  if( iTo==iFrom ){
    path.pEnd = path.pStart;
    return path.pStart;

  }else{
    db_prepare(&s,
        "SELECT cid, 1 FROM plink WHERE pid=:pid "
        "UNION ALL "
        "SELECT pid, 0 FROM plink WHERE cid=:pid"
    );
  }


  bag_init(&seen);


  while( (p = pqueuex_extract_ptr(&path.pending))!=0 ){
















    if( p->rid==iTo ){
      db_finalize(&s);
      path.pEnd = p;
      path_reverse_path();
      for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
        if( !p->isHidden ) path.nNotHidden++;
      }
      return path.pStart;
    }
    if( bag_find(&seen, p->rid) ) continue;
    bag_insert(&seen, p->rid);
    db_bind_int(&s, ":pid", p->rid);
    while( db_step(&s)==SQLITE_ROW ){
      int cid = db_column_int(&s, 0);
      int isParent = db_column_int(&s, 1);
      PathNode *pNew;
      if( bag_find(&seen, cid) ) continue;
      pNew = path_new_node(cid, p, isParent);
      if( pHidden && bag_find(pHidden,cid) ) pNew->isHidden = 1;
    }
    db_reset(&s);


  }
  db_finalize(&s);
  path_reset();
  return 0;
}

/*

/*
** Find the closest common ancestor of two nodes.  "Closest" means the
** fewest number of arcs.
*/
int path_common_ancestor(int iMe, int iYou){
  Stmt s;
  PathNode *pThis;
  PathNode *p;
  Bag me, you;

  if( iMe==iYou ) return iMe;
  if( iMe==0 || iYou==0 ) return 0;
  path_reset();
  path.pStart = path_new_node(iMe, 0, 0);
  path.pStart->isPrim = 1;
  path.pEnd = path_new_node(iYou, 0, 0);
  db_prepare(&s, "SELECT pid FROM plink WHERE cid=:cid");
  bag_init(&me);
  bag_insert(&me, iMe);
  bag_init(&you);
  bag_insert(&you, iYou);



  while( (pThis = pqueuex_extract_ptr(&path.pending))!=0 ){
    db_bind_int(&s, ":cid", pThis->rid);
    while( db_step(&s)==SQLITE_ROW ){
      int pid = db_column_int(&s, 0);
      if( bag_find(pThis->isPrim ? &you : &me, pid) ){
        /* pid is the common ancestor */
        PathNode *pNext;
        for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
        assert( p!=0 );
        pNext = p;
        while( pNext ){
          pNext = p->pFrom;
          p->pFrom = pThis;
          pThis = p;
          p = pNext;
        }
        if( pThis==path.pStart ) path.pStart = path.pEnd;
        path.pEnd = pThis;
        path_reverse_path();
        db_finalize(&s);
        return pid;
      }else if( bag_find(pThis->isPrim ? &me : &you, pid) ){
        /* pid is just an alternative path to a node we've already visited */
        continue;
      }
      p = path_new_node(pid, pThis, 0);
      p->isPrim = pThis->isPrim;
      bag_insert(pThis->isPrim ? &me : &you, pid);
    }
    db_reset(&s);


  }
  db_finalize(&s);
  path_reset();
  return 0;
}

/*