/* 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" */
  u8 nDelay;               /* Delay this many steps before walking */
  char *zBranch;           /* Branch name for this node.  Might be NULL */
  PathNode *pFrom;         /* Node we came from */
  union {
    PathNode *pPeer;       /* List of nodes of the same generation */
    PathNode *pTo;         /* Next on path from beginning to end */
  } u;
  PathNode *pAll;        /* List of all nodes */
};
#endif

/*
** Local variables for this module
*/
static struct {
  PathNode *pCurrent;   /* Current generation of nodes */
  PathNode *pAll;       /* All nodes */
  Bag seen;             /* Nodes seen before */
  int nStep;            /* Number of steps from first to last */
  int nNotHidden;       /* Number of steps not counting hidden nodes */
  u8 brCost;            /* Extra cost for moving to a different branch */
  PathNode *pStart;     /* Earliest node */
  PathNode *pEnd;       /* Most recent */
} path;

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

  PathNode *p;

  p = fossil_malloc( sizeof(*p) );
  memset(p, 0, sizeof(*p));
  p->rid = rid;
  p->fromIsParent = isParent;
  p->pFrom = pFrom;
  if( path.brCost ){
    p->zBranch = branch_of_rid(rid);
    if( pFrom && fossil_strcmp(p->zBranch, pFrom->zBranch)!=0 ){
      p->nDelay = path.brCost;
    }
  }
  p->u.pPeer = path.pCurrent;
  path.pCurrent = p;
  p->pAll = path.pAll;
  path.pAll = p;
  bag_insert(&path.seen, rid);
  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);
  }
  bag_clear(&path.seen);
  memset(&path, 0, sizeof(path));
}

/*

** Return NULL if no path is found.
*/
PathNode *path_shortest(
  int iFrom,          /* Path starts here */
  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;
  PathNode *pPrev;
  PathNode *p;
  int nPriorPeer = 1;

  path_reset();
  path.brCost = branchCost;
  path.pStart = path_new_node(iFrom, 0, 0);
  if( iTo==iFrom ){
    path.pEnd = path.pStart;
    return path.pStart;
  }
  if( oneWayOnly && directOnly ){
    db_prepare(&s,

    db_prepare(&s,
        "SELECT cid, 1 FROM plink WHERE pid=:pid "
        "UNION ALL "
        "SELECT pid, 0 FROM plink WHERE cid=:pid"
    );
  }
  while( path.pCurrent ){
    if( nPriorPeer ) path.nStep++;
    nPriorPeer = 0;
    pPrev = path.pCurrent;
    path.pCurrent = 0;
    while( pPrev ){
      if( pPrev->nDelay>0 && (nPriorPeer>0 || pPrev->u.pPeer!=0) ){
        PathNode *pThis = pPrev;
        pPrev = pThis->u.pPeer;
        pThis->u.pPeer = path.pCurrent;
        path.pCurrent = pThis;
        pThis->nDelay--;
        continue;
      }
      nPriorPeer++;
      db_bind_int(&s, ":pid", pPrev->rid);
      while( db_step(&s)==SQLITE_ROW ){
        int cid = db_column_int(&s, 0);
        int isParent = db_column_int(&s, 1);
        if( bag_find(&path.seen, cid) ) continue;
        p = path_new_node(cid, pPrev, isParent);
        if( pHidden && bag_find(pHidden,cid) ) p->isHidden = 1;

void path_shortest_stored_in_ancestor_table(
  int origid,     /* RID for check-in at start of the path */
  int cid         /* RID for check-in at the end of the path */
){
  PathNode *pPath;
  int gen = 0;
  Stmt ins;
  pPath = path_shortest(cid, origid, 1, 0, 0, 0);
  db_multi_exec(
    "CREATE TEMP TABLE IF NOT EXISTS ancestor("
    "  rid INT UNIQUE,"
    "  generation INTEGER PRIMARY KEY"
    ");"
    "DELETE FROM ancestor;"
  );

void shortest_path_test_cmd(void){
  int iFrom;
  int iTo;
  PathNode *p;
  int n;
  int directOnly;
  int oneWay;
  const char *zBrCost;

  db_find_and_open_repository(0,0);
  directOnly = find_option("no-merge",0,0)!=0;
  oneWay = find_option("one-way",0,0)!=0;
  zBrCost = find_option("branch-cost",0,1);
  if( g.argc!=4 ) usage("VERSION1 VERSION2");
  iFrom = name_to_rid(g.argv[2]);
  iTo = name_to_rid(g.argv[3]);
  p = path_shortest(iFrom, iTo, directOnly, oneWay, 0, atoi(zBrCost));
  if( p==0 ){
    fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]);
  }
  for(n=1, p=path.pStart; p; p=p->u.pTo, n++){
    char *z;
    z = db_text(0,
      "SELECT substr(uuid,1,12) || ' ' || datetime(mtime)"

  if(0==iFrom){
    fossil_fatal("Invalid 'from' RID: 0");
  }else if(0==iTo){
    fossil_fatal("Invalid 'to' RID: 0");
  }
  if( iFrom==iTo ) return;
  path_reset();
  p = path_shortest(iFrom, iTo, 1, revOK==0, 0, 0);
  if( p==0 ) return;
  path_reverse_path();
  db_prepare(&q1,
     "SELECT pfnid, fnid FROM mlink"
     " WHERE mid=:mid AND (pfnid>0 OR fid==0)"
     " ORDER BY pfnid"
  );