Fossil

    compile-commands=0 =>
      "Check for compile_commands.json support."
}

# Update the minimum required SQLite version number here, and also
# in src/main.c near the sqlite3_libversion_number() call.  Take care
# that both places agree!
define MINIMUM_SQLITE_VERSION "3.46.0"
define MINIMUM_SQLITE_VERSION "3.49.0"

# This is useful for people wanting Fossil to use an external SQLite library
# to compare the one they have against the minimum required
if {[opt-bool print-minimum-sqlite-version]} {
  puts [get-define MINIMUM_SQLITE_VERSION]
  exit 0
}

** Find the shortest path between bad and good.
*/
void bisect_path(void){
  PathNode *p;
  bisect.bad = db_lget_int("bisect-bad", 0);
  bisect.good = db_lget_int("bisect-good", 0);
  if( bisect.good>0 && bisect.bad==0 ){
    path_shortest(bisect.good, bisect.good, 0, 0, 0);
    path_shortest(bisect.good, bisect.good, 0, 0, 0, 0);
  }else if( bisect.bad>0 && bisect.good==0 ){
    path_shortest(bisect.bad, bisect.bad, 0, 0, 0);
    path_shortest(bisect.bad, bisect.bad, 0, 0, 0, 0);
  }else if( bisect.bad==0 && bisect.good==0 ){
    fossil_fatal("neither \"good\" nor \"bad\" versions have been identified");
  }else{
    Bag skip;
    int bDirect = bisect_option("direct-only");
    char *zLog = db_lget("bisect-log","");
    Blob log, id;
    bag_init(&skip);
    blob_init(&log, zLog, -1);
    while( blob_token(&log, &id) ){
      if( blob_str(&id)[0]=='s' ){
        bag_insert(&skip, atoi(blob_str(&id)+1));
      }
    }
    blob_reset(&log);
    p = path_shortest(bisect.good, bisect.bad, bDirect, 0, &skip);
    p = path_shortest(bisect.good, bisect.bad, bDirect, 0, &skip, 0);
    bag_clear(&skip);
    if( p==0 ){
      char *zBad = db_text(0,"SELECT uuid FROM blob WHERE rid=%d",bisect.bad);
      char *zGood = db_text(0,"SELECT uuid FROM blob WHERE rid=%d",bisect.good);
      fossil_fatal("no path from good ([%S]) to bad ([%S]) or back",
                   zGood, zBad);
    }

    }
  }
  if( iCurrent>0 ){
    bisect_log_append(&ins, ++cnt, "CURRENT", iCurrent);
  }
  if( bDetail && lastGood>0 && lastBad>0 ){
    PathNode *p;
    p = path_shortest(lastGood, lastBad, bisect_option("direct-only"),0, 0);
    p = path_shortest(lastGood, lastBad, bisect_option("direct-only"),0, 0, 0);
    while( p ){
      bisect_log_append(&ins, ++cnt, 0, p->rid);
      p = p->u.pTo;
    }
    path_reset();
  }
  db_exec_sql(blob_sql_text(&ins));

      "    WHERE tagxref.rid=leaves.rid "
      "      AND tagxref.tagid=%d"
      "      AND tagxref.tagtype>0)",
      TAG_CLOSED
    );
  }
}

/*
** If RID refers to a check-in, return the mtime of that check-in - the
** julian day number of when the check-in occurred.
*/
double mtime_of_rid(int rid, double mtime){
  static Stmt q;
  db_static_prepare(&q,"SELECT mtime FROM event WHERE objid=:rid");
  db_bind_int(&q, ":rid", rid);
  if( db_step(&q)==SQLITE_ROW ){
    mtime = db_column_double(&q,0);
  }
  db_reset(&q);
  return mtime;
}



/*
** Load the record ID rid and up to |N|-1 closest ancestors into
** the "ok" table.  If N is zero, no limit.  If ridBackTo is not zero
** then stop the search upon reaching the ancestor with rid==ridBackTo.
*/
void compute_ancestors(int rid, int N, int directOnly, int ridBackTo){

    **    (1)  Primary parents
    **    (2)  Merge parents
    **    (3)  Cherrypick merge parents.
    **    (4)  All ancestores of 1 and 2 but not of 3.
    */
    double rLimitMtime = 0.0;
    if( ridBackTo ){
      rLimitMtime = db_double(0.0,
      rLimitMtime = mtime_of_rid(ridBackTo, 0.0);
         "SELECT mtime FROM event WHERE objid=%d",
         ridBackTo);
    }
    db_multi_exec(
      "WITH RECURSIVE\n"
      "  parent(pid,cid,isCP) AS (\n"
      "    SELECT plink.pid, plink.cid, 0 AS xisCP FROM plink\n"
      "    UNION ALL\n"
      "    SELECT parentid, childid, 1 FROM cherrypick WHERE NOT isExclude\n"

  fossil_printf_selfcheck();
  fossil_limit_memory(1);

  /* When updating the minimum SQLite version, change the number here,
  ** and also MINIMUM_SQLITE_VERSION value set in ../auto.def.  Take
  ** care that both places agree! */
  if( sqlite3_libversion_number()<3046000
   || strncmp(sqlite3_sourceid(),"2024-08-16",10)<0
  if( sqlite3_libversion_number()<3049000
   || strncmp(sqlite3_sourceid(),"2025-02-06",10)<0
  ){
    fossil_panic("Unsuitable SQLite version %s, must be at least 3.43.0",
    fossil_panic("Unsuitable SQLite version %s, must be at least 3.49.0",
                 sqlite3_libversion());
  }

  sqlite3_config(SQLITE_CONFIG_MULTITHREAD);
  sqlite3_config(SQLITE_CONFIG_LOG, fossil_sqlite_log, 0);
  memset(&g, 0, sizeof(g));
  g.now = time(0);

** Return 0 if there are no matches.
**
** This is a tricky query to do efficiently.
** If the tag is very common (ex: "trunk") then
** we want to use the query identified below as Q1 - which searches
** the most recent EVENT table entries for the most recent with the tag.
** But if the tag is relatively scarce (anything other than "trunk", basically)
** then we want to do the indexed search show below as Q2.
** then we want to do the indexed search shown below as Q2.
*/
static int most_recent_event_with_tag(const char *zTag, const char *zType){
  return db_int(0,
    "SELECT objid FROM ("
      /* Q1:  Begin by looking for the tag in the 30 most recent events */
      "SELECT objid"
       " FROM (SELECT * FROM event ORDER BY mtime DESC LIMIT 30) AS ex"

**
** 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 {
    PathNode *pPeer;       /* List of nodes of the same generation */
    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 */
  PathNode *pAll;          /* List of all nodes */
};
#endif

/*
** Local variables for this module
*/
static struct {
  PathNode *pCurrent;   /* Current generation of nodes */
  PQueue pending;       /* Nodes pending review for inclusion in the graph */
  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 */
  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;
static int path_debug = 0;  /* Flag to enable debugging */

/*
** Return the first (last) element of the computed path.
*/
PathNode *path_first(void){ return path.pStart; }
PathNode *path_last(void){ return path.pEnd; }

/*
** Return the number of steps in the computed path.
*/
int path_length(void){ return path.nStep; }

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

/*
** Used for debugging only.
**
** Given a RID, return the ISO date/time string and branch for the
** corresponding check-in.  Memory is held locally and is overwritten
** with each call.
*/
char *path_rid_desc(int rid){
  static Stmt q;
  static char *zDesc = 0;
  db_static_prepare(&q, 
    "SELECT concat(strftime('%%Y%%m%%d%%H%%M',event.mtime),'/',value)"
    "  FROM event, tagxref"
    " WHERE event.objid=:rid"
    "   AND tagxref.rid=:rid"
    "   AND tagxref.tagid=%d"
    "   AND tagxref.tagtype>0",
    TAG_BRANCH
  );
  fossil_free(zDesc);
  db_bind_int(&q, ":rid", rid);
  if( db_step(&q)==SQLITE_ROW ){
    zDesc = fossil_strdup(db_column_text(&q,0));
  }
  db_reset(&q);
  return zDesc ? zDesc : "???";
}

/*
** Create a new node
** 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.pPeer = path.pCurrent;
  path.pCurrent = p;
  p->pAll = path.pAll;
  path.pAll = p;
  bag_insert(&path.seen, rid);
  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;
  }
  if( path_debug ){
    fossil_print("PUSH %-50s cost = %g\n", path_rid_desc(p->rid), p->u.rCost);
  }
  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);
  }
  bag_clear(&path.seen);
  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){

** 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 */
  Bag *pHidden,       /* Hidden nodes */
  int branchCost      /* Add extra cost to changing branches */
){
  Stmt s;
  PathNode *pPrev;
  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;
  }
  if( oneWayOnly && directOnly ){
    db_prepare(&s,
        "SELECT cid, 1 FROM plink WHERE pid=:pid AND isprim"
    );
  }else if( oneWayOnly ){
    db_prepare(&s,
        "SELECT cid, 1 FROM plink WHERE pid=:pid "
    );
  }else if( directOnly ){
    db_prepare(&s,
        "SELECT cid, 1 FROM plink WHERE pid=:pid AND isprim "
        "UNION ALL "
        "SELECT pid, 0 FROM plink WHERE cid=:pid AND isprim"
        "SELECT pid, 0 FROM plink WHERE :back AND cid=:pid AND isprim"
    );
  }else{
    db_prepare(&s,
        "SELECT cid, 1 FROM plink WHERE pid=:pid "
        "UNION ALL "
        "SELECT pid, 0 FROM plink WHERE cid=:pid"
        "SELECT pid, 0 FROM plink WHERE :back AND cid=:pid"
    );
  }
  while( path.pCurrent ){
    path.nStep++;
    pPrev = path.pCurrent;
  bag_init(&seen);
  while( (p = pqueuex_extract_ptr(&path.pending))!=0 ){
    if( path_debug ){
    path.pCurrent = 0;
    while( pPrev ){
      db_bind_int(&s, ":pid", pPrev->rid);
      printf("PULL %s %g\n", path_rid_desc(p->rid), p->u.rCost);
      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;
        if( cid==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;
        }
      }
      db_reset(&s);
    }
    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);
    if( !oneWayOnly ) db_bind_int(&s, ":back", !p->fromIsParent);
    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);
      pPrev = pPrev->u.pPeer;
    }
  }
  db_finalize(&s);
  path_reset();
  return 0;
}

/*

*/
PathNode *path_next(void){
  PathNode *p;
  p = path.pStart;
  if( p ) p = p->u.pTo;
  return p;
}

/*
** Return the branch for a path node.
**
** Storage space is managed by the path subsystem.  The returned value
** is valid until the path is reset.
*/
const char *path_branch(PathNode *p){
  if( p==0 ) return 0;
  if( p->zBranch==0 ) p->zBranch = branch_of_rid(p->rid);
  return p->zBranch;
}

/*
** Return an estimate of the number of comparisons remaining in order
** to bisect path.  This is based on the log2() of path.nStep.
*/
int path_search_depth(void){
  int i, j;

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

  db_finalize(&ins);
  path_reset();
}

/*
** COMMAND: test-shortest-path
**
** Usage: %fossil test-shortest-path ?--no-merge? VERSION1 VERSION2
** Usage: %fossil test-shortest-path [OPTIONS] VERSION1 VERSION2
**
** Report the shortest path between two check-ins.  If the --no-merge flag
** is used, follow only direct parent-child paths and omit merge links.
** Report the shortest path between two check-ins.  Options:
**
**    --branch-cost N    Additional cost N for changing branches
**    --debug            Show debugging output
**    --one-way          One-way forwards in time, parent->child only
**    --no-merge         Follow only direct parent-child paths and omit
**                       merge links.
*/
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( find_option("debug",0,0)!=0 ) path_debug = 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);
  p = path_shortest(iFrom, iTo, directOnly, oneWay, 0,
                    zBrCost ? atoi(zBrCost) : 0);
  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)"
      "  FROM blob, event"
      " WHERE blob.rid=%d AND event.objid=%d AND event.type='ci'",
      p->rid, p->rid);
    fossil_print("%4d: %5d %s", n, p->rid, z);
    fossil_free(z);
    if( p->u.pTo ){
      fossil_print(" is a %s of\n",
                   p->u.pTo->fromIsParent ? "parent" : "child");
    }else{
      fossil_print("\n");
    }
    fossil_print("%4d: %s\n", n, path_rid_desc(p->rid));
  }
  }
  path_debug = 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 *pPrev;
  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( path.pCurrent ){
    pPrev = path.pCurrent;
    path.pCurrent = 0;
    while( pPrev ){
      db_bind_int(&s, ":cid", pPrev->rid);
      while( db_step(&s)==SQLITE_ROW ){
        int pid = db_column_int(&s, 0);
        if( bag_find(pPrev->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 = pPrev;
            pPrev = p;
            p = pNext;
          }
          if( pPrev==path.pStart ) path.pStart = path.pEnd;
          path.pEnd = pPrev;
          path_reverse_path();
          db_finalize(&s);
          return pid;
        }else if( bag_find(&path.seen, pid) ){
          /* pid is just an alternative path on one of the legs */
          continue;
        }
        p = path_new_node(pid, pPrev, 0);
        p->isPrim = pPrev->isPrim;
        bag_insert(pPrev->isPrim ? &me : &you, pid);
      }
      db_reset(&s);
  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);
      pPrev = pPrev->u.pPeer;
    }
  }
  db_finalize(&s);
  path_reset();
  return 0;
}

/*

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

**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*******************************************************************************
**
** This file contains code used to implement a priority queue.
** A priority queue is a list of items order by a floating point
** value.  We can insert integers with each integer tied to its
** value then extract the integer with the smallest value.
** value.  Each value can be associated with either a pointer or
** an integer.  Items are inserted into the queue in an arbitrary
** order, but are returned in order of the floating point value.
**
** The way this queue is used, we never expect it to contain more
** than 2 or 3 elements, so a simple array is sufficient as the
** implementation.  This could give worst case O(N) insert times,
** but because of the nature of the problem we expect O(1) performance.
** This implementation uses a heap of QueueElement objects.  The
** root of the heap is PQueue.a[0].  Each node a[x] has two daughter
** nodes a[x*2+1] and a[x*2+2].  The mother node of a[y] is a[(y-1)/2]
** (assuming integer division rounded down).  The following is always true:
**
**    The value of any node is less than or equal two the values
**    of both daughter nodes.  (The Heap Property).
**
** A consequence of the heap property is that a[0] always contains
** the node with the smallest value.
**
** Compatibility note:  Some versions of OpenSSL export a symbols
** like "pqueue_insert".  This is, technically, a bug in OpenSSL.
** We work around it here by using "pqueuex_" instead of "pqueue_".
*/
#include "config.h"
#include "pqueue.h"
#include <assert.h>


#if INTERFACE
/*
** An integer can appear in the bag at most once.
** Integers must be positive.
*/
struct PQueue {
  int cnt;   /* Number of entries in the queue */
  int sz;    /* Number of slots in a[] */
  struct QueueElement {
    union {
    int id;          /* ID of the element */
      int id;          /* ID of the element */
      void *p;         /* Pointer to an object */
    } u;
    double value;    /* Value of element.  Kept in ascending order */
  } *a;
};
#endif

/*
** Initialize a PQueue structure

/*
** Change the size of the queue so that it contains N slots
*/
static void pqueuex_resize(PQueue *p, int N){
  p->a = fossil_realloc(p->a, sizeof(p->a[0])*N);
  p->sz = N;
}

/*
** Allocate a new queue entry and return a pointer to it.
*/
static struct QueueElement *pqueuex_new_entry(PQueue *p){
  if( p->cnt+1>p->sz ){
    pqueuex_resize(p, p->cnt+7);
  }
  return &p->a[p->cnt++];
}

/*
** Element p->a[p->cnt-1] has just been inserted.  Shift entries
** around so as to preserve the heap property.
*/
static void pqueuex_rebalance(PQueue *p){
  int i, j;
  struct QueueElement *a = p->a;
  i = p->cnt-1;
  while( (j = (i-1)/2)>=0 && a[j].value>a[i].value ){
    struct QueueElement t = a[j];
    a[j] = a[i];
    a[i] = t;
    i = j;
  }
}

/*
** Insert element e into the queue.
*/
void pqueuex_insert(PQueue *p, int e, double v){
  struct QueueElement *pE = pqueuex_new_entry(p);
  pE->value = v;
  pE->u.id = e;
  pqueuex_rebalance(p);
}
void pqueuex_insert_ptr(PQueue *p, void *pPtr, double v){
  struct QueueElement *pE = pqueuex_new_entry(p);
  pE->value = v;
  pE->u.p = pPtr;
  pqueuex_rebalance(p);
}

/*
** Remove and discard p->a[0] element from the queue.  Rearrange
** nodes to preserve the heap property.
*/
static void pqueuex_pop(PQueue *p){
  int i, j;
  struct QueueElement *a = p->a;
  struct QueueElement tmp;
  i = 0;
  if( p->cnt+1>p->sz ){
    pqueuex_resize(p, p->cnt+5);
  a[0] = a[p->cnt-1];
  p->cnt--;
  }
  for(i=0; i<p->cnt; i++){
    if( p->a[i].value>v ){
  while( (j = i*2+1)<p->cnt ){
    if( j+1<p->cnt && a[j].value > a[j+1].value ) j++;
    if( a[i].value < a[j].value ) break;
      for(j=p->cnt; j>i; j--){
        p->a[j] = p->a[j-1];
      }
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
    i = j;
  }
      break;
    }
  }
  p->a[i].id = e;
  p->a[i].value = v;
  p->cnt++;
}

/*
** Extract the first element from the queue (the element with
** the smallest value) and return its ID.  Return 0 if the queue
** is empty.
*/
int pqueuex_extract(PQueue *p){
  int e, i;
  int e;
  if( p->cnt==0 ){
    return 0;
  }
  e = p->a[0].id;
  for(i=0; i<p->cnt-1; i++){
    p->a[i] = p->a[i+1];
  }
  p->cnt--;
  return e;
  e = p->a[0].u.id;
  pqueuex_pop(p);
  return e;
}
void *pqueuex_extract_ptr(PQueue *p){
  void *pPtr;
  if( p->cnt==0 ){
    return 0;
  }
  pPtr = p->a[0].u.p;
  pqueuex_pop(p);
  return pPtr;
}

/*
** Print the entire heap associated with the test-pqueue command.
*/
static void pqueuex_test_print(PQueue *p){
  int j;
  for(j=0; j<p->cnt; j++){
    fossil_print("(%d) %g/%s ",j,p->a[j].value,p->a[j].u.p);
  }
  fossil_print("\n");
}

/*
** COMMAND: test-pqueue
**
** This command is used for testing the PQueue object.  There are one
** or more arguments, each of the form:
**
**     (1)    NUMBER/TEXT
**     (2)    ^
**     (3)    -v
**
** Form (1) arguments add an entry to the queue with value NUMBER and
** content TEXT.  Form (2) pops off the queue entry with the smallest
** value.  Form (3) (the -v option) causes the heap to be displayed after
** each subsequent operation.
*/
void pqueuex_test_cmd(void){
  int i;
  PQueue x;
  const char *zId;
  int bDebug = 0;

  pqueuex_init(&x);
  for(i=2; i<g.argc; i++){
    const char *zArg = g.argv[i];
    if( strcmp(zArg,"-v")==0 ){
      bDebug = 1;
    }else if( strcmp(zArg, "^")==0 ){
      zId = pqueuex_extract_ptr(&x);
      if( zId==0 ){
        fossil_print("%2d: POP     NULL\n", i);
      }else{
        fossil_print("%2d: POP     \"%s\"\n", i, zId);
      }
      if( bDebug) pqueuex_test_print(&x);
    }else{
      double r = atof(zArg);
      zId = strchr(zArg,'/');
      if( zId==0 ) zId = zArg;
      if( zId[0]=='/' ) zId++;
      pqueuex_insert_ptr(&x, (void*)zId, r);
      fossil_print("%2d: INSERT  \"%s\"\n", i, zId);
      if( bDebug) pqueuex_test_print(&x);
    }
  }
  while( (zId = pqueuex_extract_ptr(&x))!=0 ){
    fossil_print("... POP     \"%s\"\n", zId);
    if( bDebug) pqueuex_test_print(&x);
  }
  pqueuex_clear(&x);
}

    if( mtime>0.0 ){
      if( pzDisplay ) *pzDisplay = fossil_strdup(zDate);
      return mtime;
    }
  }
  rid = symbolic_name_to_rid(z, "*");
  if( rid ){
    mtime = db_double(0.0, "SELECT mtime FROM event WHERE objid=%d", rid);
    mtime = mtime_of_rid(rid, 0.0);
  }else{
    mtime = db_double(-1.0,
        "SELECT max(event.mtime) FROM event, tag, tagxref"
        " WHERE tag.tagname GLOB 'event-%q*'"
        "   AND tagxref.tagid=tag.tagid AND tagxref.tagtype"
        "   AND event.objid=tagxref.rid",
        z

        "    FROM dx, plink"
        "   WHERE plink.pid=dx.id"
        "     AND plink.mtime<=(SELECT max(event.mtime) FROM tagxref, event"
                               " WHERE tagxref.tagid=%d AND tagxref.tagtype>0"
                               " AND event.objid=tagxref.rid)"
        "   ORDER BY plink.mtime)"
        "SELECT id FROM dx, tagxref"
        " WHERE tagid=%d AND tagtype>0 AND rid=id LIMIT 1",
        " WHERE tagid=%d AND tagtype>0 AND rid=id"
        " ORDER BY dx.mtime LIMIT 1",
        iFrom, iFrom, tagId, tagId
      );
    }else{
      db_prepare(&q,
        "WITH RECURSIVE dx(id,mtime) AS ("
        "  SELECT %d, event.mtime FROM event WHERE objid=%d"
        "  UNION"

        "    FROM dx, plink, event"
        "   WHERE plink.cid=dx.id AND event.objid=plink.pid"
        "     AND event.mtime>=(SELECT min(event.mtime) FROM tagxref, event"
                               " WHERE tagxref.tagid=%d AND tagxref.tagtype>0"
                               " AND event.objid=tagxref.rid)"
        "   ORDER BY event.mtime DESC)"
        "SELECT id FROM dx, tagxref"
        " WHERE tagid=%d AND tagtype>0 AND rid=id LIMIT 1",
        " WHERE tagid=%d AND tagtype>0 AND rid=id"
        " ORDER BY dx.mtime DESC LIMIT 1",
        iFrom, iFrom, tagId, tagId
      );
    }else{
      db_prepare(&q,
        "WITH RECURSIVE dx(id,mtime) AS ("
        "  SELECT %d, event.mtime FROM event WHERE objid=%d"
        "  UNION"

**                       d2=CKIN2        ... Use CKIN2 if CHECKIN is not found
**                       ft=DESCENDANT   ... going forward to DESCENDANT
**    dp=CHECKIN      Same as 'd=CHECKIN&p=CHECKIN'
**    dp2=CKIN2       Same as 'd2=CKIN2&p2=CKIN2'
**    df=CHECKIN      Same as 'd=CHECKIN&n1=all&nd'.  Mnemonic: "Derived From"
**    bt=CHECKIN      "Back To".  Show ancenstors going back to CHECKIN
**                       p=CX       ... from CX back to time of CHECKIN
**                       from=CX    ... shortest path from CX back to CHECKIN
**                       from=CX    ... path from CX back to CHECKIN
**    ft=CHECKIN      "Forward To":  Show decendents forward to CHECKIN
**                       d=CX       ... from CX up to the time of CHECKIN
**                       from=CX    ... shortest path from CX up to CHECKIN
**                       from=CX    ... path from CX up to CHECKIN
**    t=TAG           Show only check-ins with the given TAG
**    r=TAG           Same as 't=TAG&rel'.  Mnemonic: "Related"
**    tl=TAGLIST      Same as 't=TAGLIST&ms=brlist'.  Mnemonic: "Tag List"
**    rl=TAGLIST      Same as 'r=TAGLIST&ms=brlist'.  Mnemonic: "Related List"
**    ml=TAGLIST      Same as 'tl=TAGLIST&mionly'.  Mnemonic: "Merge-in List"
**    sl=TAGLIST      "Sort List". Draw TAGLIST branches ordered left to right.
**    rel             Show related check-ins as well as those matching t=TAG

**    ncp             Omit cherrypick merges
**    nd              Do not highlight the focus check-in
**    nsm             Omit the submenu
**    nc              Omit all graph colors other than highlights
**    v               Show details of files changed
**    vfx             Show complete text of forum messages
**    f=CHECKIN       Family (immediate parents and children) of CHECKIN
**    from=CHECKIN    Path through common ancestor from...
**                       to=CHECKIN      ... to this
**                       to2=CHECKIN     ... backup name if to= doesn't resolve
**                       shortest        ... show only the shortest path
**                       rel             ... also show related checkins
**                       bt=PRIOR        ... path from CHECKIN back to PRIOR
**                       ft=LATER        ... path from CHECKIN forward to LATER
**    me=CHECKIN      Most direct path from...
**                       you=CHECKIN     ... to this
**                       rel             ... also show related checkins
**    from=CHECKIN    Path through common ancestor from CHECKIN...
**                       to=CHECKIN   ... to this
**                       to2=CHECKIN  ... backup name if to= doesn't resolve
**                       shortest     ... pick path with least number of nodes
**                       rel          ... also show related checkins
**                       min          ... hide long sequences along same branch
**                       bt=PRIOR     ... path from CHECKIN back to PRIOR
**                       ft=LATER     ... path from CHECKIN forward to LATER
**    me=CHECKIN      Most direct path from CHECKIN...
**                       you=CHECKIN  ... to this
**                       rel          ... also show related checkins
**    uf=FILE_HASH    Show only check-ins that contain the given file version
**                    All qualifying check-ins are shown unless there is
**                    also an n= or n1= query parameter.
**    chng=GLOBLIST   Show only check-ins that involve changes to a file whose
**                    name matches one of the comma-separate GLOBLIST
**    brbg            Background color determined by branch name
**    ubg             Background color determined by user

  int tmFlags = 0;                   /* Timeline flags */
  const char *zThisTag = 0;          /* Suppress links to this tag */
  const char *zThisUser = 0;         /* Suppress links to this user */
  HQuery url;                        /* URL for various branch links */
  int from_rid = name_to_typed_rid(P("from"),"ci"); /* from= for paths */
  const char *zTo2 = 0;
  int to_rid = name_choice("to","to2",&zTo2);    /* to= for path timelines */
  int noMerge = P("shortest")==0;           /* Follow merge links if shorter */
  int bShort = P("shortest")!=0;                 /* shortest possible path */
  int me_rid = name_to_typed_rid(P("me"),"ci");  /* me= for common ancestory */
  int you_rid = name_to_typed_rid(P("you"),"ci");/* you= for common ancst */
  int pd_rid;
  const char *zDPName;                /* Value of p=, d=, or dp= params */
  double rBefore, rAfter, rCirca;     /* Boundary times */
  const char *z;
  char *zOlderButton = 0;             /* URL for Older button at the bottom */
  char *zOlderButtonLabel = 0;        /* Label for the Older Button */
  char *zNewerButton = 0;             /* URL for Newer button at the top */
  char *zNewerButtonLabel = 0;        /* Label for the Newer button */
  int selectedRid = 0;                /* Show a highlight on this RID */
  int secondaryRid = 0;               /* Show secondary highlight */
  int disableY = 0;                   /* Disable type selector on submenu */
  int advancedMenu = 0;               /* Use the advanced menu design */
  char *zPlural;                      /* Ending for plural forms */
  int showCherrypicks = 1;            /* True to show cherrypick merges */
  int haveParameterN;                 /* True if n= query parameter present */
  int from_to_mode = 0;               /* 0: from,to. 1: from,ft 2: from,bt */
  int showSql = PB("showsql");        /* True to show the SQL */
  Blob allSql;                        /* Copy of all SQL text */
  int bMin = P("min")!=0;             /* True if "min" query parameter used */

  login_check_credentials();
  url_initialize(&url, "timeline");
  cgi_query_parameters_to_url(&url);
  blob_init(&allSql, 0, 0);

  /* The "mionly" query parameter is like "rel", but shows merge-ins only */

    PathNode *p = 0;
    const char *zFrom = 0;
    const char *zTo = 0;
    Blob ins;
    int nNodeOnPath = 0;
    int commonAncs = 0;    /* Common ancestors of me_rid and you_rid. */
    int earlierRid = 0, laterRid = 0;
    int cost = bShort ? 0 : 1;
    int nSkip = 0;

    if( from_rid && to_rid ){
      if( from_to_mode==0 ){
        p = path_shortest(from_rid, to_rid, noMerge, 0, 0);
        p = path_shortest(from_rid, to_rid, 0, 0, 0, cost);
      }else if( from_to_mode==1 ){
        p = path_shortest(from_rid, to_rid, 0, 1, 0);
        p = path_shortest(from_rid, to_rid, 0, 1, 0, cost);
        earlierRid = commonAncs = from_rid;
        laterRid = to_rid;
      }else{
        p = path_shortest(to_rid, from_rid, 0, 1, 0);
        p = path_shortest(to_rid, from_rid, 0, 1, 0, cost);
        earlierRid = commonAncs = to_rid;
        laterRid = from_rid;
      }
      zFrom = P("from");
      zTo = zTo2 ? zTo2 : P("to");
    }else{
      commonAncs = path_common_ancestor(me_rid, you_rid);

    db_multi_exec(
      "CREATE TEMP TABLE IF NOT EXISTS pathnode(x INTEGER PRIMARY KEY);"
    );
    if( p ){
      int cnt = 4;
      blob_init(&ins, 0, 0);
      blob_append_sql(&ins, "INSERT INTO pathnode(x) VALUES(%d)", p->rid);
      if( p->u.pTo==0 ) bMin = 0;
      for(p=p->u.pTo; p; p=p->u.pTo){
        if( bMin
      p = p->u.pTo;
      while( p ){
        if( cnt==8 ){
         && p->u.pTo!=0
         && fossil_strcmp(path_branch(p->pFrom),path_branch(p))==0
         && fossil_strcmp(path_branch(p),path_branch(p->u.pTo))==0
        ){
          nSkip++;
        }else if( cnt==8 ){
          blob_append_sql(&ins, ",\n  (%d)", p->rid);
          cnt = 0;
        }else{
          cnt++;
          blob_append_sql(&ins, ",(%d)", p->rid);
        }
        p = p->u.pTo;
      }
    }
    path_reset();
    db_multi_exec("%s", blob_str(&ins)/*safe-for-%s*/);
    blob_reset(&ins);
    if( related ){
      db_multi_exec(

    db_multi_exec("%s", blob_sql_text(&sql));
    if( advancedMenu ){
      style_submenu_checkbox("v", "Files", (zType[0]!='a' && zType[0]!='c'),0);
    }
    nNodeOnPath = db_int(0, "SELECT count(*) FROM temp.pathnode");
    if( nNodeOnPath==1 && from_to_mode>0 ){
      blob_appendf(&desc,"Check-in ");
    }else if( from_to_mode>0 ){
      blob_appendf(&desc, "%d check-ins on the shorted path from ",nNodeOnPath);
    }else if( bMin ){
      blob_appendf(&desc, "%d of %d check-ins along the path from ",
                   nNodeOnPath, nNodeOnPath+nSkip);
    }else{
      blob_appendf(&desc, "%d check-ins going from ", nNodeOnPath);
    }
    if( from_rid==selectedRid ){
      blob_appendf(&desc, "<span class='timelineSelected'>");
    }
    blob_appendf(&desc, "%z%h</a>", href("%R/info/%h", zFrom), zFrom);

    if( zCiName==0 ) zCiName = zUuid;
    blob_append_sql(&sql, " AND event.objid IN ok");
    nd = 0;
    if( d_rid ){
      double rStopTime = 9e99;
      zFwdTo = P("ft");
      if( zFwdTo ){
        double rStartDate = db_double(0.0,
        double rStartDate = mtime_of_rid(d_rid, 0.0);
           "SELECT mtime FROM event WHERE objid=%d", d_rid);
        ridFwdTo = first_checkin_with_tag_after_date(zFwdTo, rStartDate);
        if( ridFwdTo==0 ){
          ridFwdTo = name_to_typed_rid(zBackTo,"ci");
        }
        if( ridFwdTo ){
          if( !haveParameterN ) nEntry = 0;
          rStopTime = db_double(9e99,
          rStopTime = mtime_of_rid(ridFwdTo, 9e99);
            "SELECT mtime FROM event WHERE objid=%d", ridFwdTo);
        }
      }
      if( rStopTime<9e99 ){
        rStopTime += 5.8e-6;  /* Round up by 1/2 second */
      }
      db_multi_exec(
        "WITH RECURSIVE dx(rid,mtime) AS (\n"

      }
      if( useDividers && !selectedRid ) selectedRid = d_rid;
      db_multi_exec("DELETE FROM ok");
    }
    if( p_rid ){
      zBackTo = P("bt");
      if( zBackTo ){
        double rDateLimit = db_double(0.0,
        double rDateLimit = mtime_of_rid(p_rid, 0.0);
           "SELECT mtime FROM event WHERE objid=%d", p_rid);
        ridBackTo = last_checkin_with_tag_before_date(zBackTo, rDateLimit);
        if( ridBackTo==0 ){
          ridBackTo = name_to_typed_rid(zBackTo,"ci");
        }
        if( ridBackTo && !haveParameterN ) nEntry = 0;
      }
      compute_ancestors(p_rid, nEntry==0 ? 0 : nEntry+1, 0, ridBackTo);