Index: auto.def ================================================================== --- auto.def +++ auto.def @@ -36,11 +36,11 @@ } # 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] Index: src/bisect.c ================================================================== --- src/bisect.c +++ src/bisect.c @@ -37,13 +37,13 @@ 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"); @@ -55,11 +55,11 @@ 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", @@ -292,11 +292,11 @@ 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(); Index: src/descendants.c ================================================================== --- src/descendants.c +++ src/descendants.c @@ -156,10 +156,27 @@ " 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. @@ -197,13 +214,11 @@ ** (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, - "SELECT mtime FROM event WHERE objid=%d", - ridBackTo); + rLimitMtime = mtime_of_rid(ridBackTo, 0.0); } db_multi_exec( "WITH RECURSIVE\n" " parent(pid,cid,isCP) AS (\n" " SELECT plink.pid, plink.cid, 0 AS xisCP FROM plink\n" Index: src/main.c ================================================================== --- src/main.c +++ src/main.c @@ -726,14 +726,14 @@ 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); Index: src/name.c ================================================================== --- src/name.c +++ src/name.c @@ -231,11 +231,11 @@ ** 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 */ Index: src/path.c ================================================================== --- src/path.c +++ src/path.c @@ -18,40 +18,45 @@ ** directed acyclic graph (DAG) of check-ins. */ #include "config.h" #include "path.h" #include +#include #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; } @@ -66,25 +71,71 @@ ** Return the number of non-hidden steps in the computed path. */ int path_length_not_hidden(void){ return path.nNotHidden; } /* -** Create a new node +** 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 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. @@ -92,13 +143,14 @@ 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. @@ -128,17 +180,19 @@ 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; } @@ -152,44 +206,46 @@ ); }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; - path.pCurrent = 0; - while( pPrev ){ - 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; - 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); - pPrev = pPrev->u.pPeer; - } + bag_init(&seen); + while( (p = pqueuex_extract_ptr(&path.pending))!=0 ){ + if( path_debug ){ + printf("PULL %s %g\n", path_rid_desc(p->rid), p->u.rCost); + } + 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); } db_finalize(&s); path_reset(); return 0; } @@ -215,10 +271,22 @@ 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. */ @@ -238,11 +306,11 @@ 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" ");" @@ -261,58 +329,55 @@ } /* ** 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. Options: ** -** 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. +** --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; @@ -323,45 +388,40 @@ 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); - pPrev = pPrev->u.pPeer; - } + 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; } @@ -453,11 +513,11 @@ }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)" Index: src/pqueue.c ================================================================== --- src/pqueue.c +++ src/pqueue.c @@ -15,17 +15,24 @@ ** ******************************************************************************* ** ** 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. +** +** 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). ** -** 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. +** 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_". */ @@ -41,11 +48,14 @@ */ struct PQueue { int cnt; /* Number of entries in the queue */ int sz; /* Number of slots in a[] */ struct QueueElement { - int id; /* ID of the element */ + union { + int id; /* ID of the element */ + void *p; /* Pointer to an object */ + } u; double value; /* Value of element. Kept in ascending order */ } *a; }; #endif @@ -69,44 +79,154 @@ */ 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; - if( p->cnt+1>p->sz ){ - pqueuex_resize(p, p->cnt+5); - } - for(i=0; icnt; i++){ - if( p->a[i].value>v ){ - for(j=p->cnt; j>i; j--){ - p->a[j] = p->a[j-1]; - } - break; - } - } - p->a[i].id = e; - p->a[i].value = v; - p->cnt++; + struct QueueElement *a = p->a; + struct QueueElement tmp; + i = 0; + a[0] = a[p->cnt-1]; + p->cnt--; + while( (j = i*2+1)cnt ){ + if( j+1cnt && a[j].value > a[j+1].value ) j++; + if( a[i].value < a[j].value ) break; + tmp = a[i]; + a[i] = a[j]; + a[j] = tmp; + i = j; + } } /* ** 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].u.id; + pqueuex_pop(p); + return e; +} +void *pqueuex_extract_ptr(PQueue *p){ + void *pPtr; if( p->cnt==0 ){ return 0; } - e = p->a[0].id; - for(i=0; icnt-1; i++){ - p->a[i] = p->a[i+1]; + 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; jcnt; 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; icnt--; - return e; + pqueuex_clear(&x); } Index: src/timeline.c ================================================================== --- src/timeline.c +++ src/timeline.c @@ -1113,11 +1113,11 @@ 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" @@ -1408,11 +1408,12 @@ " 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 (" @@ -1439,11 +1440,12 @@ " 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 (" @@ -1572,14 +1574,14 @@ ** 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" @@ -1600,20 +1602,21 @@ ** 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 @@ -1696,11 +1699,11 @@ 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 */ @@ -1717,10 +1720,11 @@ 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); @@ -2072,20 +2076,22 @@ 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"); @@ -2112,20 +2118,25 @@ ); if( p ){ int cnt = 4; blob_init(&ins, 0, 0); blob_append_sql(&ins, "INSERT INTO pathnode(x) VALUES(%d)", p->rid); - p = p->u.pTo; - while( p ){ - if( cnt==8 ){ + if( p->u.pTo==0 ) bMin = 0; + for(p=p->u.pTo; p; p=p->u.pTo){ + if( bMin + && 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); @@ -2185,12 +2196,13 @@ 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, ""); @@ -2242,20 +2254,18 @@ nd = 0; if( d_rid ){ double rStopTime = 9e99; zFwdTo = P("ft"); if( zFwdTo ){ - double rStartDate = db_double(0.0, - "SELECT mtime FROM event WHERE objid=%d", d_rid); + double rStartDate = mtime_of_rid(d_rid, 0.0); 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, - "SELECT mtime FROM event WHERE objid=%d", ridFwdTo); + rStopTime = mtime_of_rid(ridFwdTo, 9e99); } } if( rStopTime<9e99 ){ rStopTime += 5.8e-6; /* Round up by 1/2 second */ } @@ -2280,12 +2290,11 @@ db_multi_exec("DELETE FROM ok"); } if( p_rid ){ zBackTo = P("bt"); if( zBackTo ){ - double rDateLimit = db_double(0.0, - "SELECT mtime FROM event WHERE objid=%d", p_rid); + double rDateLimit = mtime_of_rid(p_rid, 0.0); ridBackTo = last_checkin_with_tag_before_date(zBackTo, rDateLimit); if( ridBackTo==0 ){ ridBackTo = name_to_typed_rid(zBackTo,"ci"); } if( ridBackTo && !haveParameterN ) nEntry = 0;