Fossil SCM

Add the "min" query parameter to /timeline. Other minor bug fixes found while working on the new feature. The priority queue implementation was rewritten. Minimum SQLite increased to 3.49.0.

drh 2025-03-09 19:28 trunk merge

Commit 4e23c2a91af07aa24097c1d0c49bd2ef0ddabb3bd03694b4fd90ce0784caa5cf

Parent f01d60fd175fbf3…

8 files changed +1 -1 +4 -4 +18 -3 +3 -3 +1 -1 +157 -97 +147 -27 +40 -31

~ auto.def ~ src/bisect.c ~ src/descendants.c ~ src/main.c ~ src/name.c ~ src/path.c ~ src/pqueue.c ~ src/timeline.c

M auto.def

+1 -1

		--- auto.def
		+++ auto.def
		@@ -36,11 +36,11 @@
36	36	}
37	37
38	38	# Update the minimum required SQLite version number here, and also
39	39	# in src/main.c near the sqlite3_libversion_number() call. Take care
40	40	# that both places agree!
41		-define MINIMUM_SQLITE_VERSION "3.46.0"
	41	+define MINIMUM_SQLITE_VERSION "3.49.0"
42	42
43	43	# This is useful for people wanting Fossil to use an external SQLite library
44	44	# to compare the one they have against the minimum required
45	45	if {[opt-bool print-minimum-sqlite-version]} {
46	46	puts [get-define MINIMUM_SQLITE_VERSION]
47	47

	--- auto.def
	+++ auto.def
	@@ -36,11 +36,11 @@
36	}
37
38	# Update the minimum required SQLite version number here, and also
39	# in src/main.c near the sqlite3_libversion_number() call. Take care
40	# that both places agree!
41	define MINIMUM_SQLITE_VERSION "3.46.0"
42
43	# This is useful for people wanting Fossil to use an external SQLite library
44	# to compare the one they have against the minimum required
45	if {[opt-bool print-minimum-sqlite-version]} {
46	puts [get-define MINIMUM_SQLITE_VERSION]
47

	--- auto.def
	+++ auto.def
	@@ -36,11 +36,11 @@
36	}
37
38	# Update the minimum required SQLite version number here, and also
39	# in src/main.c near the sqlite3_libversion_number() call. Take care
40	# that both places agree!
41	define MINIMUM_SQLITE_VERSION "3.49.0"
42
43	# This is useful for people wanting Fossil to use an external SQLite library
44	# to compare the one they have against the minimum required
45	if {[opt-bool print-minimum-sqlite-version]} {
46	puts [get-define MINIMUM_SQLITE_VERSION]
47

M src/bisect.c

+4 -4

		--- src/bisect.c
		+++ src/bisect.c
		@@ -37,13 +37,13 @@
37	37	void bisect_path(void){
38	38	PathNode *p;
39	39	bisect.bad = db_lget_int("bisect-bad", 0);
40	40	bisect.good = db_lget_int("bisect-good", 0);
41	41	if( bisect.good>0 && bisect.bad==0 ){
42		- path_shortest(bisect.good, bisect.good, 0, 0, 0);
	42	+ path_shortest(bisect.good, bisect.good, 0, 0, 0, 0);
43	43	}else if( bisect.bad>0 && bisect.good==0 ){
44		- path_shortest(bisect.bad, bisect.bad, 0, 0, 0);
	44	+ path_shortest(bisect.bad, bisect.bad, 0, 0, 0, 0);
45	45	}else if( bisect.bad==0 && bisect.good==0 ){
46	46	fossil_fatal("neither \"good\" nor \"bad\" versions have been identified");
47	47	}else{
48	48	Bag skip;
49	49	int bDirect = bisect_option("direct-only");
		@@ -55,11 +55,11 @@
55	55	if( blob_str(&id)[0]=='s' ){
56	56	bag_insert(&skip, atoi(blob_str(&id)+1));
57	57	}
58	58	}
59	59	blob_reset(&log);
60		- p = path_shortest(bisect.good, bisect.bad, bDirect, 0, &skip);
	60	+ p = path_shortest(bisect.good, bisect.bad, bDirect, 0, &skip, 0);
61	61	bag_clear(&skip);
62	62	if( p==0 ){
63	63	char *zBad = db_text(0,"SELECT uuid FROM blob WHERE rid=%d",bisect.bad);
64	64	char *zGood = db_text(0,"SELECT uuid FROM blob WHERE rid=%d",bisect.good);
65	65	fossil_fatal("no path from good ([%S]) to bad ([%S]) or back",
		@@ -292,11 +292,11 @@
292	292	if( iCurrent>0 ){
293	293	bisect_log_append(&ins, ++cnt, "CURRENT", iCurrent);
294	294	}
295	295	if( bDetail && lastGood>0 && lastBad>0 ){
296	296	PathNode *p;
297		- p = path_shortest(lastGood, lastBad, bisect_option("direct-only"),0, 0);
	297	+ p = path_shortest(lastGood, lastBad, bisect_option("direct-only"),0, 0, 0);
298	298	while( p ){
299	299	bisect_log_append(&ins, ++cnt, 0, p->rid);
300	300	p = p->u.pTo;
301	301	}
302	302	path_reset();
303	303

	--- src/bisect.c
	+++ src/bisect.c
	@@ -37,13 +37,13 @@
37	void bisect_path(void){
38	PathNode *p;
39	bisect.bad = db_lget_int("bisect-bad", 0);
40	bisect.good = db_lget_int("bisect-good", 0);
41	if( bisect.good>0 && bisect.bad==0 ){
42	path_shortest(bisect.good, bisect.good, 0, 0, 0);
43	}else if( bisect.bad>0 && bisect.good==0 ){
44	path_shortest(bisect.bad, bisect.bad, 0, 0, 0);
45	}else if( bisect.bad==0 && bisect.good==0 ){
46	fossil_fatal("neither \"good\" nor \"bad\" versions have been identified");
47	}else{
48	Bag skip;
49	int bDirect = bisect_option("direct-only");
	@@ -55,11 +55,11 @@
55	if( blob_str(&id)[0]=='s' ){
56	bag_insert(&skip, atoi(blob_str(&id)+1));
57	}
58	}
59	blob_reset(&log);
60	p = path_shortest(bisect.good, bisect.bad, bDirect, 0, &skip);
61	bag_clear(&skip);
62	if( p==0 ){
63	char *zBad = db_text(0,"SELECT uuid FROM blob WHERE rid=%d",bisect.bad);
64	char *zGood = db_text(0,"SELECT uuid FROM blob WHERE rid=%d",bisect.good);
65	fossil_fatal("no path from good ([%S]) to bad ([%S]) or back",
	@@ -292,11 +292,11 @@
292	if( iCurrent>0 ){
293	bisect_log_append(&ins, ++cnt, "CURRENT", iCurrent);
294	}
295	if( bDetail && lastGood>0 && lastBad>0 ){
296	PathNode *p;
297	p = path_shortest(lastGood, lastBad, bisect_option("direct-only"),0, 0);
298	while( p ){
299	bisect_log_append(&ins, ++cnt, 0, p->rid);
300	p = p->u.pTo;
301	}
302	path_reset();
303

	--- src/bisect.c
	+++ src/bisect.c
	@@ -37,13 +37,13 @@
37	void bisect_path(void){
38	PathNode *p;
39	bisect.bad = db_lget_int("bisect-bad", 0);
40	bisect.good = db_lget_int("bisect-good", 0);
41	if( bisect.good>0 && bisect.bad==0 ){
42	path_shortest(bisect.good, bisect.good, 0, 0, 0, 0);
43	}else if( bisect.bad>0 && bisect.good==0 ){
44	path_shortest(bisect.bad, bisect.bad, 0, 0, 0, 0);
45	}else if( bisect.bad==0 && bisect.good==0 ){
46	fossil_fatal("neither \"good\" nor \"bad\" versions have been identified");
47	}else{
48	Bag skip;
49	int bDirect = bisect_option("direct-only");
	@@ -55,11 +55,11 @@
55	if( blob_str(&id)[0]=='s' ){
56	bag_insert(&skip, atoi(blob_str(&id)+1));
57	}
58	}
59	blob_reset(&log);
60	p = path_shortest(bisect.good, bisect.bad, bDirect, 0, &skip, 0);
61	bag_clear(&skip);
62	if( p==0 ){
63	char *zBad = db_text(0,"SELECT uuid FROM blob WHERE rid=%d",bisect.bad);
64	char *zGood = db_text(0,"SELECT uuid FROM blob WHERE rid=%d",bisect.good);
65	fossil_fatal("no path from good ([%S]) to bad ([%S]) or back",
	@@ -292,11 +292,11 @@
292	if( iCurrent>0 ){
293	bisect_log_append(&ins, ++cnt, "CURRENT", iCurrent);
294	}
295	if( bDetail && lastGood>0 && lastBad>0 ){
296	PathNode *p;
297	p = path_shortest(lastGood, lastBad, bisect_option("direct-only"),0, 0, 0);
298	while( p ){
299	bisect_log_append(&ins, ++cnt, 0, p->rid);
300	p = p->u.pTo;
301	}
302	path_reset();
303

M src/descendants.c

+18 -3

		--- src/descendants.c
		+++ src/descendants.c
		@@ -156,10 +156,27 @@
156	156	" AND tagxref.tagtype>0)",
157	157	TAG_CLOSED
158	158	);
159	159	}
160	160	}
	161	+
	162	+/*
	163	+** If RID refers to a check-in, return the mtime of that check-in - the
	164	+** julian day number of when the check-in occurred.
	165	+*/
	166	+double mtime_of_rid(int rid, double mtime){
	167	+ static Stmt q;
	168	+ db_static_prepare(&q,"SELECT mtime FROM event WHERE objid=:rid");
	169	+ db_bind_int(&q, ":rid", rid);
	170	+ if( db_step(&q)==SQLITE_ROW ){
	171	+ mtime = db_column_double(&q,0);
	172	+ }
	173	+ db_reset(&q);
	174	+ return mtime;
	175	+}
	176	+
	177	+
161	178
162	179	/*
163	180	** Load the record ID rid and up to \|N\|-1 closest ancestors into
164	181	** the "ok" table. If N is zero, no limit. If ridBackTo is not zero
165	182	** then stop the search upon reaching the ancestor with rid==ridBackTo.
		@@ -197,13 +214,11 @@
197	214	** (3) Cherrypick merge parents.
198	215	** (4) All ancestores of 1 and 2 but not of 3.
199	216	*/
200	217	double rLimitMtime = 0.0;
201	218	if( ridBackTo ){
202		- rLimitMtime = db_double(0.0,
203		- "SELECT mtime FROM event WHERE objid=%d",
204		- ridBackTo);
	219	+ rLimitMtime = mtime_of_rid(ridBackTo, 0.0);
205	220	}
206	221	db_multi_exec(
207	222	"WITH RECURSIVE\n"
208	223	" parent(pid,cid,isCP) AS (\n"
209	224	" SELECT plink.pid, plink.cid, 0 AS xisCP FROM plink\n"
210	225

	--- src/descendants.c
	+++ src/descendants.c
	@@ -156,10 +156,27 @@
156	" AND tagxref.tagtype>0)",
157	TAG_CLOSED
158	);
159	}
160	}

















161
162	/*
163	** Load the record ID rid and up to \|N\|-1 closest ancestors into
164	** the "ok" table. If N is zero, no limit. If ridBackTo is not zero
165	** then stop the search upon reaching the ancestor with rid==ridBackTo.
	@@ -197,13 +214,11 @@
197	** (3) Cherrypick merge parents.
198	** (4) All ancestores of 1 and 2 but not of 3.
199	*/
200	double rLimitMtime = 0.0;
201	if( ridBackTo ){
202	rLimitMtime = db_double(0.0,
203	"SELECT mtime FROM event WHERE objid=%d",
204	ridBackTo);
205	}
206	db_multi_exec(
207	"WITH RECURSIVE\n"
208	" parent(pid,cid,isCP) AS (\n"
209	" SELECT plink.pid, plink.cid, 0 AS xisCP FROM plink\n"
210

	--- src/descendants.c
	+++ src/descendants.c
	@@ -156,10 +156,27 @@
156	" AND tagxref.tagtype>0)",
157	TAG_CLOSED
158	);
159	}
160	}
161
162	/*
163	** If RID refers to a check-in, return the mtime of that check-in - the
164	** julian day number of when the check-in occurred.
165	*/
166	double mtime_of_rid(int rid, double mtime){
167	static Stmt q;
168	db_static_prepare(&q,"SELECT mtime FROM event WHERE objid=:rid");
169	db_bind_int(&q, ":rid", rid);
170	if( db_step(&q)==SQLITE_ROW ){
171	mtime = db_column_double(&q,0);
172	}
173	db_reset(&q);
174	return mtime;
175	}
176
177
178
179	/*
180	** Load the record ID rid and up to \|N\|-1 closest ancestors into
181	** the "ok" table. If N is zero, no limit. If ridBackTo is not zero
182	** then stop the search upon reaching the ancestor with rid==ridBackTo.
	@@ -197,13 +214,11 @@
214	** (3) Cherrypick merge parents.
215	** (4) All ancestores of 1 and 2 but not of 3.
216	*/
217	double rLimitMtime = 0.0;
218	if( ridBackTo ){
219	rLimitMtime = mtime_of_rid(ridBackTo, 0.0);


220	}
221	db_multi_exec(
222	"WITH RECURSIVE\n"
223	" parent(pid,cid,isCP) AS (\n"
224	" SELECT plink.pid, plink.cid, 0 AS xisCP FROM plink\n"
225

M src/main.c

+3 -3

		--- src/main.c
		+++ src/main.c
		@@ -726,14 +726,14 @@
726	726	fossil_limit_memory(1);
727	727
728	728	/* When updating the minimum SQLite version, change the number here,
729	729	** and also MINIMUM_SQLITE_VERSION value set in ../auto.def. Take
730	730	** care that both places agree! */
731		- if( sqlite3_libversion_number()<3046000
732		- \|\| strncmp(sqlite3_sourceid(),"2024-08-16",10)<0
	731	+ if( sqlite3_libversion_number()<3049000
	732	+ \|\| strncmp(sqlite3_sourceid(),"2025-02-06",10)<0
733	733	){
734		- fossil_panic("Unsuitable SQLite version %s, must be at least 3.43.0",
	734	+ fossil_panic("Unsuitable SQLite version %s, must be at least 3.49.0",
735	735	sqlite3_libversion());
736	736	}
737	737
738	738	sqlite3_config(SQLITE_CONFIG_MULTITHREAD);
739	739	sqlite3_config(SQLITE_CONFIG_LOG, fossil_sqlite_log, 0);
740	740

	--- src/main.c
	+++ src/main.c
	@@ -726,14 +726,14 @@
726	fossil_limit_memory(1);
727
728	/* When updating the minimum SQLite version, change the number here,
729	** and also MINIMUM_SQLITE_VERSION value set in ../auto.def. Take
730	** care that both places agree! */
731	if( sqlite3_libversion_number()<3046000
732	\|\| strncmp(sqlite3_sourceid(),"2024-08-16",10)<0
733	){
734	fossil_panic("Unsuitable SQLite version %s, must be at least 3.43.0",
735	sqlite3_libversion());
736	}
737
738	sqlite3_config(SQLITE_CONFIG_MULTITHREAD);
739	sqlite3_config(SQLITE_CONFIG_LOG, fossil_sqlite_log, 0);
740

	--- src/main.c
	+++ src/main.c
	@@ -726,14 +726,14 @@
726	fossil_limit_memory(1);
727
728	/* When updating the minimum SQLite version, change the number here,
729	** and also MINIMUM_SQLITE_VERSION value set in ../auto.def. Take
730	** care that both places agree! */
731	if( sqlite3_libversion_number()<3049000
732	\|\| strncmp(sqlite3_sourceid(),"2025-02-06",10)<0
733	){
734	fossil_panic("Unsuitable SQLite version %s, must be at least 3.49.0",
735	sqlite3_libversion());
736	}
737
738	sqlite3_config(SQLITE_CONFIG_MULTITHREAD);
739	sqlite3_config(SQLITE_CONFIG_LOG, fossil_sqlite_log, 0);
740

M src/name.c

+1 -1

		--- src/name.c
		+++ src/name.c
		@@ -231,11 +231,11 @@
231	231	** This is a tricky query to do efficiently.
232	232	** If the tag is very common (ex: "trunk") then
233	233	** we want to use the query identified below as Q1 - which searches
234	234	** the most recent EVENT table entries for the most recent with the tag.
235	235	** But if the tag is relatively scarce (anything other than "trunk", basically)
236		-** then we want to do the indexed search show below as Q2.
	236	+** then we want to do the indexed search shown below as Q2.
237	237	*/
238	238	static int most_recent_event_with_tag(const char zTag, const char zType){
239	239	return db_int(0,
240	240	"SELECT objid FROM ("
241	241	/* Q1: Begin by looking for the tag in the 30 most recent events */
242	242

	--- src/name.c
	+++ src/name.c
	@@ -231,11 +231,11 @@
231	** This is a tricky query to do efficiently.
232	** If the tag is very common (ex: "trunk") then
233	** we want to use the query identified below as Q1 - which searches
234	** the most recent EVENT table entries for the most recent with the tag.
235	** But if the tag is relatively scarce (anything other than "trunk", basically)
236	** then we want to do the indexed search show below as Q2.
237	*/
238	static int most_recent_event_with_tag(const char zTag, const char zType){
239	return db_int(0,
240	"SELECT objid FROM ("
241	/* Q1: Begin by looking for the tag in the 30 most recent events */
242

	--- src/name.c
	+++ src/name.c
	@@ -231,11 +231,11 @@
231	** This is a tricky query to do efficiently.
232	** If the tag is very common (ex: "trunk") then
233	** we want to use the query identified below as Q1 - which searches
234	** the most recent EVENT table entries for the most recent with the tag.
235	** But if the tag is relatively scarce (anything other than "trunk", basically)
236	** then we want to do the indexed search shown below as Q2.
237	*/
238	static int most_recent_event_with_tag(const char zTag, const char zType){
239	return db_int(0,
240	"SELECT objid FROM ("
241	/* Q1: Begin by looking for the tag in the 30 most recent events */
242

M src/path.c

+157 -97

		--- src/path.c
		+++ src/path.c
		@@ -18,40 +18,45 @@
18	18	** directed acyclic graph (DAG) of check-ins.
19	19	*/
20	20	#include "config.h"
21	21	#include "path.h"
22	22	#include <assert.h>
	23	+#include <math.h>
23	24
24	25	#if INTERFACE
25	26	/* Nodes for the paths through the DAG.
26	27	*/
27	28	struct PathNode {
28	29	int rid; /* ID for this node */
29	30	u8 fromIsParent; /* True if pFrom is the parent of rid */
30	31	u8 isPrim; /* True if primary side of common ancestor */
31	32	u8 isHidden; /* Abbreviate output in "fossil bisect ls" */
	33	+ char zBranch; / Branch name for this node. Might be NULL */
	34	+ double mtime; /* Date/time of this check-in */
32	35	PathNode pFrom; / Node we came from */
33	36	union {
34		- PathNode pPeer; / List of nodes of the same generation */
	37	+ double rCost; /* Cost of getting to this node from pStart */
35	38	PathNode pTo; / Next on path from beginning to end */
36	39	} u;
37		- PathNode pAll; / List of all nodes */
	40	+ PathNode pAll; / List of all nodes */
38	41	};
39	42	#endif
40	43
41	44	/*
42	45	** Local variables for this module
43	46	*/
44	47	static struct {
45		- PathNode pCurrent; / Current generation of nodes */
	48	+ PQueue pending; /* Nodes pending review for inclusion in the graph */
46	49	PathNode pAll; / All nodes */
47		- Bag seen; /* Nodes seen before */
48	50	int nStep; /* Number of steps from first to last */
49	51	int nNotHidden; /* Number of steps not counting hidden nodes */
	52	+ int brCost; /* Extra cost for moving to a different branch */
	53	+ int revCost; /* Extra cost for changing directions */
50	54	PathNode pStart; / Earliest node */
51	55	PathNode pEnd; / Most recent */
52	56	} path;
	57	+static int path_debug = 0; /* Flag to enable debugging */
53	58
54	59	/*
55	60	** Return the first (last) element of the computed path.
56	61	*/
57	62	PathNode *path_first(void){ return path.pStart; }
		@@ -66,25 +71,71 @@
66	71	** Return the number of non-hidden steps in the computed path.
67	72	*/
68	73	int path_length_not_hidden(void){ return path.nNotHidden; }
69	74
70	75	/*
71		-** Create a new node
	76	+** Used for debugging only.
	77	+**
	78	+** Given a RID, return the ISO date/time string and branch for the
	79	+** corresponding check-in. Memory is held locally and is overwritten
	80	+** with each call.
	81	+*/
	82	+char *path_rid_desc(int rid){
	83	+ static Stmt q;
	84	+ static char *zDesc = 0;
	85	+ db_static_prepare(&q,
	86	+ "SELECT concat(strftime('%%Y%%m%%d%%H%%M',event.mtime),'/',value)"
	87	+ " FROM event, tagxref"
	88	+ " WHERE event.objid=:rid"
	89	+ " AND tagxref.rid=:rid"
	90	+ " AND tagxref.tagid=%d"
	91	+ " AND tagxref.tagtype>0",
	92	+ TAG_BRANCH
	93	+ );
	94	+ fossil_free(zDesc);
	95	+ db_bind_int(&q, ":rid", rid);
	96	+ if( db_step(&q)==SQLITE_ROW ){
	97	+ zDesc = fossil_strdup(db_column_text(&q,0));
	98	+ }
	99	+ db_reset(&q);
	100	+ return zDesc ? zDesc : "???";
	101	+}
	102	+
	103	+/*
	104	+** Create a new node and insert it into the path.pending queue.
72	105	*/
73	106	static PathNode path_new_node(int rid, PathNode pFrom, int isParent){
74	107	PathNode *p;
75	108
76	109	p = fossil_malloc( sizeof(*p) );
77	110	memset(p, 0, sizeof(*p));
	111	+ p->pAll = path.pAll;
	112	+ path.pAll = p;
78	113	p->rid = rid;
79	114	p->fromIsParent = isParent;
80	115	p->pFrom = pFrom;
81		- p->u.pPeer = path.pCurrent;
82		- path.pCurrent = p;
83		- p->pAll = path.pAll;
84		- path.pAll = p;
85		- bag_insert(&path.seen, rid);
	116	+ p->u.rCost = pFrom ? pFrom->u.rCost : 0.0;
	117	+ if( path.brCost ){
	118	+ p->zBranch = branch_of_rid(rid);
	119	+ p->mtime = mtime_of_rid(rid, 0.0);
	120	+ if( pFrom ){
	121	+ p->u.rCost += fabs(pFrom->mtime - p->mtime);
	122	+ if( fossil_strcmp(p->zBranch, pFrom->zBranch)!=0 ){
	123	+ p->u.rCost += path.brCost;
	124	+ }
	125	+ }
	126	+ }else{
	127	+ /* When brCost==0, we try to minimize the number of nodes
	128	+ ** along the path. The cost is just the number of nodes back
	129	+ ** to the start. We do not need to know the branch name nor
	130	+ ** the mtime */
	131	+ p->u.rCost += 1.0;
	132	+ }
	133	+ if( path_debug ){
	134	+ fossil_print("PUSH %-50s cost = %g\n", path_rid_desc(p->rid), p->u.rCost);
	135	+ }
	136	+ pqueuex_insert_ptr(&path.pending, (void*)p, p->u.rCost);
86	137	return p;
87	138	}
88	139
89	140	/*
90	141	** Reset memory used by the shortest path algorithm.
		@@ -92,13 +143,14 @@
92	143	void path_reset(void){
93	144	PathNode *p;
94	145	while( path.pAll ){
95	146	p = path.pAll;
96	147	path.pAll = p->pAll;
	148	+ fossil_free(p->zBranch);
97	149	fossil_free(p);
98	150	}
99		- bag_clear(&path.seen);
	151	+ pqueuex_clear(&path.pending);
100	152	memset(&path, 0, sizeof(path));
101	153	}
102	154
103	155	/*
104	156	** Construct the path from path.pStart to path.pEnd in the u.pTo fields.
		@@ -128,17 +180,19 @@
128	180	PathNode *path_shortest(
129	181	int iFrom, /* Path starts here */
130	182	int iTo, /* Path ends here */
131	183	int directOnly, /* No merge links if true */
132	184	int oneWayOnly, /* Parent->child only if true */
133		- Bag pHidden / Hidden nodes */
	185	+ Bag pHidden, / Hidden nodes */
	186	+ int branchCost /* Add extra cost to changing branches */
134	187	){
135	188	Stmt s;
136		- PathNode *pPrev;
	189	+ Bag seen;
137	190	PathNode *p;
138	191
139	192	path_reset();
	193	+ path.brCost = branchCost;
140	194	path.pStart = path_new_node(iFrom, 0, 0);
141	195	if( iTo==iFrom ){
142	196	path.pEnd = path.pStart;
143	197	return path.pStart;
144	198	}
		@@ -152,44 +206,46 @@
152	206	);
153	207	}else if( directOnly ){
154	208	db_prepare(&s,
155	209	"SELECT cid, 1 FROM plink WHERE pid=:pid AND isprim "
156	210	"UNION ALL "
157		- "SELECT pid, 0 FROM plink WHERE cid=:pid AND isprim"
	211	+ "SELECT pid, 0 FROM plink WHERE :back AND cid=:pid AND isprim"
158	212	);
159	213	}else{
160	214	db_prepare(&s,
161	215	"SELECT cid, 1 FROM plink WHERE pid=:pid "
162	216	"UNION ALL "
163		- "SELECT pid, 0 FROM plink WHERE cid=:pid"
	217	+ "SELECT pid, 0 FROM plink WHERE :back AND cid=:pid"
164	218	);
165	219	}
166		- while( path.pCurrent ){
167		- path.nStep++;
168		- pPrev = path.pCurrent;
169		- path.pCurrent = 0;
170		- while( pPrev ){
171		- db_bind_int(&s, ":pid", pPrev->rid);
172		- while( db_step(&s)==SQLITE_ROW ){
173		- int cid = db_column_int(&s, 0);
174		- int isParent = db_column_int(&s, 1);
175		- if( bag_find(&path.seen, cid) ) continue;
176		- p = path_new_node(cid, pPrev, isParent);
177		- if( pHidden && bag_find(pHidden,cid) ) p->isHidden = 1;
178		- if( cid==iTo ){
179		- db_finalize(&s);
180		- path.pEnd = p;
181		- path_reverse_path();
182		- for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
183		- if( !p->isHidden ) path.nNotHidden++;
184		- }
185		- return path.pStart;
186		- }
187		- }
188		- db_reset(&s);
189		- pPrev = pPrev->u.pPeer;
190		- }
	220	+ bag_init(&seen);
	221	+ while( (p = pqueuex_extract_ptr(&path.pending))!=0 ){
	222	+ if( path_debug ){
	223	+ printf("PULL %s %g\n", path_rid_desc(p->rid), p->u.rCost);
	224	+ }
	225	+ if( p->rid==iTo ){
	226	+ db_finalize(&s);
	227	+ path.pEnd = p;
	228	+ path_reverse_path();
	229	+ for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
	230	+ if( !p->isHidden ) path.nNotHidden++;
	231	+ }
	232	+ return path.pStart;
	233	+ }
	234	+ if( bag_find(&seen, p->rid) ) continue;
	235	+ bag_insert(&seen, p->rid);
	236	+ db_bind_int(&s, ":pid", p->rid);
	237	+ if( !oneWayOnly ) db_bind_int(&s, ":back", !p->fromIsParent);
	238	+ while( db_step(&s)==SQLITE_ROW ){
	239	+ int cid = db_column_int(&s, 0);
	240	+ int isParent = db_column_int(&s, 1);
	241	+ PathNode *pNew;
	242	+ if( bag_find(&seen, cid) ) continue;
	243	+ pNew = path_new_node(cid, p, isParent);
	244	+ if( pHidden && bag_find(pHidden,cid) ) pNew->isHidden = 1;
	245	+ }
	246	+ db_reset(&s);
191	247	}
192	248	db_finalize(&s);
193	249	path_reset();
194	250	return 0;
195	251	}
		@@ -215,10 +271,22 @@
215	271	PathNode *p;
216	272	p = path.pStart;
217	273	if( p ) p = p->u.pTo;
218	274	return p;
219	275	}
	276	+
	277	+/*
	278	+** Return the branch for a path node.
	279	+**
	280	+** Storage space is managed by the path subsystem. The returned value
	281	+** is valid until the path is reset.
	282	+*/
	283	+const char path_branch(PathNode p){
	284	+ if( p==0 ) return 0;
	285	+ if( p->zBranch==0 ) p->zBranch = branch_of_rid(p->rid);
	286	+ return p->zBranch;
	287	+}
220	288
221	289	/*
222	290	** Return an estimate of the number of comparisons remaining in order
223	291	** to bisect path. This is based on the log2() of path.nStep.
224	292	*/
		@@ -238,11 +306,11 @@
238	306	int cid /* RID for check-in at the end of the path */
239	307	){
240	308	PathNode *pPath;
241	309	int gen = 0;
242	310	Stmt ins;
243		- pPath = path_shortest(cid, origid, 1, 0, 0);
	311	+ pPath = path_shortest(cid, origid, 1, 0, 0, 0);
244	312	db_multi_exec(
245	313	"CREATE TEMP TABLE IF NOT EXISTS ancestor("
246	314	" rid INT UNIQUE,"
247	315	" generation INTEGER PRIMARY KEY"
248	316	");"
		@@ -261,58 +329,55 @@
261	329	}
262	330
263	331	/*
264	332	** COMMAND: test-shortest-path
265	333	**
266		-** Usage: %fossil test-shortest-path ?--no-merge? VERSION1 VERSION2
	334	+** Usage: %fossil test-shortest-path [OPTIONS] VERSION1 VERSION2
	335	+**
	336	+** Report the shortest path between two check-ins. Options:
267	337	**
268		-** Report the shortest path between two check-ins. If the --no-merge flag
269		-** is used, follow only direct parent-child paths and omit merge links.
	338	+** --branch-cost N Additional cost N for changing branches
	339	+** --debug Show debugging output
	340	+** --one-way One-way forwards in time, parent->child only
	341	+** --no-merge Follow only direct parent-child paths and omit
	342	+** merge links.
270	343	*/
271	344	void shortest_path_test_cmd(void){
272	345	int iFrom;
273	346	int iTo;
274	347	PathNode *p;
275	348	int n;
276	349	int directOnly;
277	350	int oneWay;
	351	+ const char *zBrCost;
278	352
279	353	db_find_and_open_repository(0,0);
280	354	directOnly = find_option("no-merge",0,0)!=0;
281	355	oneWay = find_option("one-way",0,0)!=0;
	356	+ zBrCost = find_option("branch-cost",0,1);
	357	+ if( find_option("debug",0,0)!=0 ) path_debug = 1;
282	358	if( g.argc!=4 ) usage("VERSION1 VERSION2");
283	359	iFrom = name_to_rid(g.argv[2]);
284	360	iTo = name_to_rid(g.argv[3]);
285		- p = path_shortest(iFrom, iTo, directOnly, oneWay, 0);
	361	+ p = path_shortest(iFrom, iTo, directOnly, oneWay, 0,
	362	+ zBrCost ? atoi(zBrCost) : 0);
286	363	if( p==0 ){
287	364	fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]);
288	365	}
289	366	for(n=1, p=path.pStart; p; p=p->u.pTo, n++){
290		- char *z;
291		- z = db_text(0,
292		- "SELECT substr(uuid,1,12) \|\| ' ' \|\| datetime(mtime)"
293		- " FROM blob, event"
294		- " WHERE blob.rid=%d AND event.objid=%d AND event.type='ci'",
295		- p->rid, p->rid);
296		- fossil_print("%4d: %5d %s", n, p->rid, z);
297		- fossil_free(z);
298		- if( p->u.pTo ){
299		- fossil_print(" is a %s of\n",
300		- p->u.pTo->fromIsParent ? "parent" : "child");
301		- }else{
302		- fossil_print("\n");
303		- }
304		- }
	367	+ fossil_print("%4d: %s\n", n, path_rid_desc(p->rid));
	368	+ }
	369	+ path_debug = 0;
305	370	}
306	371
307	372	/*
308	373	** Find the closest common ancestor of two nodes. "Closest" means the
309	374	** fewest number of arcs.
310	375	*/
311	376	int path_common_ancestor(int iMe, int iYou){
312	377	Stmt s;
313		- PathNode *pPrev;
	378	+ PathNode *pThis;
314	379	PathNode *p;
315	380	Bag me, you;
316	381
317	382	if( iMe==iYou ) return iMe;
318	383	if( iMe==0 \|\| iYou==0 ) return 0;
		@@ -323,45 +388,40 @@
323	388	db_prepare(&s, "SELECT pid FROM plink WHERE cid=:cid");
324	389	bag_init(&me);
325	390	bag_insert(&me, iMe);
326	391	bag_init(&you);
327	392	bag_insert(&you, iYou);
328		- while( path.pCurrent ){
329		- pPrev = path.pCurrent;
330		- path.pCurrent = 0;
331		- while( pPrev ){
332		- db_bind_int(&s, ":cid", pPrev->rid);
333		- while( db_step(&s)==SQLITE_ROW ){
334		- int pid = db_column_int(&s, 0);
335		- if( bag_find(pPrev->isPrim ? &you : &me, pid) ){
336		- /* pid is the common ancestor */
337		- PathNode *pNext;
338		- for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
339		- assert( p!=0 );
340		- pNext = p;
341		- while( pNext ){
342		- pNext = p->pFrom;
343		- p->pFrom = pPrev;
344		- pPrev = p;
345		- p = pNext;
346		- }
347		- if( pPrev==path.pStart ) path.pStart = path.pEnd;
348		- path.pEnd = pPrev;
349		- path_reverse_path();
350		- db_finalize(&s);
351		- return pid;
352		- }else if( bag_find(&path.seen, pid) ){
353		- /* pid is just an alternative path on one of the legs */
354		- continue;
355		- }
356		- p = path_new_node(pid, pPrev, 0);
357		- p->isPrim = pPrev->isPrim;
358		- bag_insert(pPrev->isPrim ? &me : &you, pid);
359		- }
360		- db_reset(&s);
361		- pPrev = pPrev->u.pPeer;
362		- }
	393	+ while( (pThis = pqueuex_extract_ptr(&path.pending))!=0 ){
	394	+ db_bind_int(&s, ":cid", pThis->rid);
	395	+ while( db_step(&s)==SQLITE_ROW ){
	396	+ int pid = db_column_int(&s, 0);
	397	+ if( bag_find(pThis->isPrim ? &you : &me, pid) ){
	398	+ /* pid is the common ancestor */
	399	+ PathNode *pNext;
	400	+ for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
	401	+ assert( p!=0 );
	402	+ pNext = p;
	403	+ while( pNext ){
	404	+ pNext = p->pFrom;
	405	+ p->pFrom = pThis;
	406	+ pThis = p;
	407	+ p = pNext;
	408	+ }
	409	+ if( pThis==path.pStart ) path.pStart = path.pEnd;
	410	+ path.pEnd = pThis;
	411	+ path_reverse_path();
	412	+ db_finalize(&s);
	413	+ return pid;
	414	+ }else if( bag_find(pThis->isPrim ? &me : &you, pid) ){
	415	+ /* pid is just an alternative path to a node we've already visited */
	416	+ continue;
	417	+ }
	418	+ p = path_new_node(pid, pThis, 0);
	419	+ p->isPrim = pThis->isPrim;
	420	+ bag_insert(pThis->isPrim ? &me : &you, pid);
	421	+ }
	422	+ db_reset(&s);
363	423	}
364	424	db_finalize(&s);
365	425	path_reset();
366	426	return 0;
367	427	}
		@@ -453,11 +513,11 @@
453	513	}else if(0==iTo){
454	514	fossil_fatal("Invalid 'to' RID: 0");
455	515	}
456	516	if( iFrom==iTo ) return;
457	517	path_reset();
458		- p = path_shortest(iFrom, iTo, 1, revOK==0, 0);
	518	+ p = path_shortest(iFrom, iTo, 1, revOK==0, 0, 0);
459	519	if( p==0 ) return;
460	520	path_reverse_path();
461	521	db_prepare(&q1,
462	522	"SELECT pfnid, fnid FROM mlink"
463	523	" WHERE mid=:mid AND (pfnid>0 OR fid==0)"
464	524

	--- src/path.c
	+++ src/path.c
	@@ -18,40 +18,45 @@
18	** directed acyclic graph (DAG) of check-ins.
19	*/
20	#include "config.h"
21	#include "path.h"
22	#include <assert.h>

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


32	PathNode pFrom; / Node we came from */
33	union {
34	PathNode pPeer; / List of nodes of the same generation */
35	PathNode pTo; / Next on path from beginning to end */
36	} u;
37	PathNode pAll; / List of all nodes */
38	};
39	#endif
40
41	/*
42	** Local variables for this module
43	*/
44	static struct {
45	PathNode pCurrent; / Current generation of nodes */
46	PathNode pAll; / All nodes */
47	Bag seen; /* Nodes seen before */
48	int nStep; /* Number of steps from first to last */
49	int nNotHidden; /* Number of steps not counting hidden nodes */


50	PathNode pStart; / Earliest node */
51	PathNode pEnd; / Most recent */
52	} path;

53
54	/*
55	** Return the first (last) element of the computed path.
56	*/
57	PathNode *path_first(void){ return path.pStart; }
	@@ -66,25 +71,71 @@
66	** Return the number of non-hidden steps in the computed path.
67	*/
68	int path_length_not_hidden(void){ return path.nNotHidden; }
69
70	/*
71	** Create a new node




























72	*/
73	static PathNode path_new_node(int rid, PathNode pFrom, int isParent){
74	PathNode *p;
75
76	p = fossil_malloc( sizeof(*p) );
77	memset(p, 0, sizeof(*p));


78	p->rid = rid;
79	p->fromIsParent = isParent;
80	p->pFrom = pFrom;
81	p->u.pPeer = path.pCurrent;
82	path.pCurrent = p;
83	p->pAll = path.pAll;
84	path.pAll = p;
85	bag_insert(&path.seen, rid);
















86	return p;
87	}
88
89	/*
90	** Reset memory used by the shortest path algorithm.
	@@ -92,13 +143,14 @@
92	void path_reset(void){
93	PathNode *p;
94	while( path.pAll ){
95	p = path.pAll;
96	path.pAll = p->pAll;

97	fossil_free(p);
98	}
99	bag_clear(&path.seen);
100	memset(&path, 0, sizeof(path));
101	}
102
103	/*
104	** Construct the path from path.pStart to path.pEnd in the u.pTo fields.
	@@ -128,17 +180,19 @@
128	PathNode *path_shortest(
129	int iFrom, /* Path starts here */
130	int iTo, /* Path ends here */
131	int directOnly, /* No merge links if true */
132	int oneWayOnly, /* Parent->child only if true */
133	Bag pHidden / Hidden nodes */

134	){
135	Stmt s;
136	PathNode *pPrev;
137	PathNode *p;
138
139	path_reset();

140	path.pStart = path_new_node(iFrom, 0, 0);
141	if( iTo==iFrom ){
142	path.pEnd = path.pStart;
143	return path.pStart;
144	}
	@@ -152,44 +206,46 @@
152	);
153	}else if( directOnly ){
154	db_prepare(&s,
155	"SELECT cid, 1 FROM plink WHERE pid=:pid AND isprim "
156	"UNION ALL "
157	"SELECT pid, 0 FROM plink WHERE cid=:pid AND isprim"
158	);
159	}else{
160	db_prepare(&s,
161	"SELECT cid, 1 FROM plink WHERE pid=:pid "
162	"UNION ALL "
163	"SELECT pid, 0 FROM plink WHERE cid=:pid"
164	);
165	}
166	while( path.pCurrent ){
167	path.nStep++;
168	pPrev = path.pCurrent;
169	path.pCurrent = 0;
170	while( pPrev ){
171	db_bind_int(&s, ":pid", pPrev->rid);
172	while( db_step(&s)==SQLITE_ROW ){
173	int cid = db_column_int(&s, 0);
174	int isParent = db_column_int(&s, 1);
175	if( bag_find(&path.seen, cid) ) continue;
176	p = path_new_node(cid, pPrev, isParent);
177	if( pHidden && bag_find(pHidden,cid) ) p->isHidden = 1;
178	if( cid==iTo ){
179	db_finalize(&s);
180	path.pEnd = p;
181	path_reverse_path();
182	for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
183	if( !p->isHidden ) path.nNotHidden++;
184	}
185	return path.pStart;
186	}
187	}
188	db_reset(&s);
189	pPrev = pPrev->u.pPeer;
190	}


191	}
192	db_finalize(&s);
193	path_reset();
194	return 0;
195	}
	@@ -215,10 +271,22 @@
215	PathNode *p;
216	p = path.pStart;
217	if( p ) p = p->u.pTo;
218	return p;
219	}












220
221	/*
222	** Return an estimate of the number of comparisons remaining in order
223	** to bisect path. This is based on the log2() of path.nStep.
224	*/
	@@ -238,11 +306,11 @@
238	int cid /* RID for check-in at the end of the path */
239	){
240	PathNode *pPath;
241	int gen = 0;
242	Stmt ins;
243	pPath = path_shortest(cid, origid, 1, 0, 0);
244	db_multi_exec(
245	"CREATE TEMP TABLE IF NOT EXISTS ancestor("
246	" rid INT UNIQUE,"
247	" generation INTEGER PRIMARY KEY"
248	");"
	@@ -261,58 +329,55 @@
261	}
262
263	/*
264	** COMMAND: test-shortest-path
265	**
266	** Usage: %fossil test-shortest-path ?--no-merge? VERSION1 VERSION2


267	**
268	** Report the shortest path between two check-ins. If the --no-merge flag
269	** is used, follow only direct parent-child paths and omit merge links.



270	*/
271	void shortest_path_test_cmd(void){
272	int iFrom;
273	int iTo;
274	PathNode *p;
275	int n;
276	int directOnly;
277	int oneWay;

278
279	db_find_and_open_repository(0,0);
280	directOnly = find_option("no-merge",0,0)!=0;
281	oneWay = find_option("one-way",0,0)!=0;


282	if( g.argc!=4 ) usage("VERSION1 VERSION2");
283	iFrom = name_to_rid(g.argv[2]);
284	iTo = name_to_rid(g.argv[3]);
285	p = path_shortest(iFrom, iTo, directOnly, oneWay, 0);

286	if( p==0 ){
287	fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]);
288	}
289	for(n=1, p=path.pStart; p; p=p->u.pTo, n++){
290	char *z;
291	z = db_text(0,
292	"SELECT substr(uuid,1,12) \|\| ' ' \|\| datetime(mtime)"
293	" FROM blob, event"
294	" WHERE blob.rid=%d AND event.objid=%d AND event.type='ci'",
295	p->rid, p->rid);
296	fossil_print("%4d: %5d %s", n, p->rid, z);
297	fossil_free(z);
298	if( p->u.pTo ){
299	fossil_print(" is a %s of\n",
300	p->u.pTo->fromIsParent ? "parent" : "child");
301	}else{
302	fossil_print("\n");
303	}
304	}
305	}
306
307	/*
308	** Find the closest common ancestor of two nodes. "Closest" means the
309	** fewest number of arcs.
310	*/
311	int path_common_ancestor(int iMe, int iYou){
312	Stmt s;
313	PathNode *pPrev;
314	PathNode *p;
315	Bag me, you;
316
317	if( iMe==iYou ) return iMe;
318	if( iMe==0 \|\| iYou==0 ) return 0;
	@@ -323,45 +388,40 @@
323	db_prepare(&s, "SELECT pid FROM plink WHERE cid=:cid");
324	bag_init(&me);
325	bag_insert(&me, iMe);
326	bag_init(&you);
327	bag_insert(&you, iYou);
328	while( path.pCurrent ){
329	pPrev = path.pCurrent;
330	path.pCurrent = 0;
331	while( pPrev ){
332	db_bind_int(&s, ":cid", pPrev->rid);
333	while( db_step(&s)==SQLITE_ROW ){
334	int pid = db_column_int(&s, 0);
335	if( bag_find(pPrev->isPrim ? &you : &me, pid) ){
336	/* pid is the common ancestor */
337	PathNode *pNext;
338	for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
339	assert( p!=0 );
340	pNext = p;
341	while( pNext ){
342	pNext = p->pFrom;
343	p->pFrom = pPrev;
344	pPrev = p;
345	p = pNext;
346	}
347	if( pPrev==path.pStart ) path.pStart = path.pEnd;
348	path.pEnd = pPrev;
349	path_reverse_path();
350	db_finalize(&s);
351	return pid;
352	}else if( bag_find(&path.seen, pid) ){
353	/* pid is just an alternative path on one of the legs */
354	continue;
355	}
356	p = path_new_node(pid, pPrev, 0);
357	p->isPrim = pPrev->isPrim;
358	bag_insert(pPrev->isPrim ? &me : &you, pid);
359	}
360	db_reset(&s);
361	pPrev = pPrev->u.pPeer;
362	}
363	}
364	db_finalize(&s);
365	path_reset();
366	return 0;
367	}
	@@ -453,11 +513,11 @@
453	}else if(0==iTo){
454	fossil_fatal("Invalid 'to' RID: 0");
455	}
456	if( iFrom==iTo ) return;
457	path_reset();
458	p = path_shortest(iFrom, iTo, 1, revOK==0, 0);
459	if( p==0 ) return;
460	path_reverse_path();
461	db_prepare(&q1,
462	"SELECT pfnid, fnid FROM mlink"
463	" WHERE mid=:mid AND (pfnid>0 OR fid==0)"
464

	--- src/path.c
	+++ src/path.c
	@@ -18,40 +18,45 @@
18	** directed acyclic graph (DAG) of check-ins.
19	*/
20	#include "config.h"
21	#include "path.h"
22	#include <assert.h>
23	#include <math.h>
24
25	#if INTERFACE
26	/* Nodes for the paths through the DAG.
27	*/
28	struct PathNode {
29	int rid; /* ID for this node */
30	u8 fromIsParent; /* True if pFrom is the parent of rid */
31	u8 isPrim; /* True if primary side of common ancestor */
32	u8 isHidden; /* Abbreviate output in "fossil bisect ls" */
33	char zBranch; / Branch name for this node. Might be NULL */
34	double mtime; /* Date/time of this check-in */
35	PathNode pFrom; / Node we came from */
36	union {
37	double rCost; /* Cost of getting to this node from pStart */
38	PathNode pTo; / Next on path from beginning to end */
39	} u;
40	PathNode pAll; / List of all nodes */
41	};
42	#endif
43
44	/*
45	** Local variables for this module
46	*/
47	static struct {
48	PQueue pending; /* Nodes pending review for inclusion in the graph */
49	PathNode pAll; / All nodes */

50	int nStep; /* Number of steps from first to last */
51	int nNotHidden; /* Number of steps not counting hidden nodes */
52	int brCost; /* Extra cost for moving to a different branch */
53	int revCost; /* Extra cost for changing directions */
54	PathNode pStart; / Earliest node */
55	PathNode pEnd; / Most recent */
56	} path;
57	static int path_debug = 0; /* Flag to enable debugging */
58
59	/*
60	** Return the first (last) element of the computed path.
61	*/
62	PathNode *path_first(void){ return path.pStart; }
	@@ -66,25 +71,71 @@
71	** Return the number of non-hidden steps in the computed path.
72	*/
73	int path_length_not_hidden(void){ return path.nNotHidden; }
74
75	/*
76	** Used for debugging only.
77	**
78	** Given a RID, return the ISO date/time string and branch for the
79	** corresponding check-in. Memory is held locally and is overwritten
80	** with each call.
81	*/
82	char *path_rid_desc(int rid){
83	static Stmt q;
84	static char *zDesc = 0;
85	db_static_prepare(&q,
86	"SELECT concat(strftime('%%Y%%m%%d%%H%%M',event.mtime),'/',value)"
87	" FROM event, tagxref"
88	" WHERE event.objid=:rid"
89	" AND tagxref.rid=:rid"
90	" AND tagxref.tagid=%d"
91	" AND tagxref.tagtype>0",
92	TAG_BRANCH
93	);
94	fossil_free(zDesc);
95	db_bind_int(&q, ":rid", rid);
96	if( db_step(&q)==SQLITE_ROW ){
97	zDesc = fossil_strdup(db_column_text(&q,0));
98	}
99	db_reset(&q);
100	return zDesc ? zDesc : "???";
101	}
102
103	/*
104	** Create a new node and insert it into the path.pending queue.
105	*/
106	static PathNode path_new_node(int rid, PathNode pFrom, int isParent){
107	PathNode *p;
108
109	p = fossil_malloc( sizeof(*p) );
110	memset(p, 0, sizeof(*p));
111	p->pAll = path.pAll;
112	path.pAll = p;
113	p->rid = rid;
114	p->fromIsParent = isParent;
115	p->pFrom = pFrom;
116	p->u.rCost = pFrom ? pFrom->u.rCost : 0.0;
117	if( path.brCost ){
118	p->zBranch = branch_of_rid(rid);
119	p->mtime = mtime_of_rid(rid, 0.0);
120	if( pFrom ){
121	p->u.rCost += fabs(pFrom->mtime - p->mtime);
122	if( fossil_strcmp(p->zBranch, pFrom->zBranch)!=0 ){
123	p->u.rCost += path.brCost;
124	}
125	}
126	}else{
127	/* When brCost==0, we try to minimize the number of nodes
128	** along the path. The cost is just the number of nodes back
129	** to the start. We do not need to know the branch name nor
130	** the mtime */
131	p->u.rCost += 1.0;
132	}
133	if( path_debug ){
134	fossil_print("PUSH %-50s cost = %g\n", path_rid_desc(p->rid), p->u.rCost);
135	}
136	pqueuex_insert_ptr(&path.pending, (void*)p, p->u.rCost);
137	return p;
138	}
139
140	/*
141	** Reset memory used by the shortest path algorithm.
	@@ -92,13 +143,14 @@
143	void path_reset(void){
144	PathNode *p;
145	while( path.pAll ){
146	p = path.pAll;
147	path.pAll = p->pAll;
148	fossil_free(p->zBranch);
149	fossil_free(p);
150	}
151	pqueuex_clear(&path.pending);
152	memset(&path, 0, sizeof(path));
153	}
154
155	/*
156	** Construct the path from path.pStart to path.pEnd in the u.pTo fields.
	@@ -128,17 +180,19 @@
180	PathNode *path_shortest(
181	int iFrom, /* Path starts here */
182	int iTo, /* Path ends here */
183	int directOnly, /* No merge links if true */
184	int oneWayOnly, /* Parent->child only if true */
185	Bag pHidden, / Hidden nodes */
186	int branchCost /* Add extra cost to changing branches */
187	){
188	Stmt s;
189	Bag seen;
190	PathNode *p;
191
192	path_reset();
193	path.brCost = branchCost;
194	path.pStart = path_new_node(iFrom, 0, 0);
195	if( iTo==iFrom ){
196	path.pEnd = path.pStart;
197	return path.pStart;
198	}
	@@ -152,44 +206,46 @@
206	);
207	}else if( directOnly ){
208	db_prepare(&s,
209	"SELECT cid, 1 FROM plink WHERE pid=:pid AND isprim "
210	"UNION ALL "
211	"SELECT pid, 0 FROM plink WHERE :back AND cid=:pid AND isprim"
212	);
213	}else{
214	db_prepare(&s,
215	"SELECT cid, 1 FROM plink WHERE pid=:pid "
216	"UNION ALL "
217	"SELECT pid, 0 FROM plink WHERE :back AND cid=:pid"
218	);
219	}
220	bag_init(&seen);
221	while( (p = pqueuex_extract_ptr(&path.pending))!=0 ){
222	if( path_debug ){
223	printf("PULL %s %g\n", path_rid_desc(p->rid), p->u.rCost);
224	}
225	if( p->rid==iTo ){
226	db_finalize(&s);
227	path.pEnd = p;
228	path_reverse_path();
229	for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
230	if( !p->isHidden ) path.nNotHidden++;
231	}
232	return path.pStart;
233	}
234	if( bag_find(&seen, p->rid) ) continue;
235	bag_insert(&seen, p->rid);
236	db_bind_int(&s, ":pid", p->rid);
237	if( !oneWayOnly ) db_bind_int(&s, ":back", !p->fromIsParent);
238	while( db_step(&s)==SQLITE_ROW ){
239	int cid = db_column_int(&s, 0);
240	int isParent = db_column_int(&s, 1);
241	PathNode *pNew;
242	if( bag_find(&seen, cid) ) continue;
243	pNew = path_new_node(cid, p, isParent);
244	if( pHidden && bag_find(pHidden,cid) ) pNew->isHidden = 1;
245	}
246	db_reset(&s);
247	}
248	db_finalize(&s);
249	path_reset();
250	return 0;
251	}
	@@ -215,10 +271,22 @@
271	PathNode *p;
272	p = path.pStart;
273	if( p ) p = p->u.pTo;
274	return p;
275	}
276
277	/*
278	** Return the branch for a path node.
279	**
280	** Storage space is managed by the path subsystem. The returned value
281	** is valid until the path is reset.
282	*/
283	const char path_branch(PathNode p){
284	if( p==0 ) return 0;
285	if( p->zBranch==0 ) p->zBranch = branch_of_rid(p->rid);
286	return p->zBranch;
287	}
288
289	/*
290	** Return an estimate of the number of comparisons remaining in order
291	** to bisect path. This is based on the log2() of path.nStep.
292	*/
	@@ -238,11 +306,11 @@
306	int cid /* RID for check-in at the end of the path */
307	){
308	PathNode *pPath;
309	int gen = 0;
310	Stmt ins;
311	pPath = path_shortest(cid, origid, 1, 0, 0, 0);
312	db_multi_exec(
313	"CREATE TEMP TABLE IF NOT EXISTS ancestor("
314	" rid INT UNIQUE,"
315	" generation INTEGER PRIMARY KEY"
316	");"
	@@ -261,58 +329,55 @@
329	}
330
331	/*
332	** COMMAND: test-shortest-path
333	**
334	** Usage: %fossil test-shortest-path [OPTIONS] VERSION1 VERSION2
335	**
336	** Report the shortest path between two check-ins. Options:
337	**
338	** --branch-cost N Additional cost N for changing branches
339	** --debug Show debugging output
340	** --one-way One-way forwards in time, parent->child only
341	** --no-merge Follow only direct parent-child paths and omit
342	** merge links.
343	*/
344	void shortest_path_test_cmd(void){
345	int iFrom;
346	int iTo;
347	PathNode *p;
348	int n;
349	int directOnly;
350	int oneWay;
351	const char *zBrCost;
352
353	db_find_and_open_repository(0,0);
354	directOnly = find_option("no-merge",0,0)!=0;
355	oneWay = find_option("one-way",0,0)!=0;
356	zBrCost = find_option("branch-cost",0,1);
357	if( find_option("debug",0,0)!=0 ) path_debug = 1;
358	if( g.argc!=4 ) usage("VERSION1 VERSION2");
359	iFrom = name_to_rid(g.argv[2]);
360	iTo = name_to_rid(g.argv[3]);
361	p = path_shortest(iFrom, iTo, directOnly, oneWay, 0,
362	zBrCost ? atoi(zBrCost) : 0);
363	if( p==0 ){
364	fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]);
365	}
366	for(n=1, p=path.pStart; p; p=p->u.pTo, n++){
367	fossil_print("%4d: %s\n", n, path_rid_desc(p->rid));
368	}
369	path_debug = 0;












370	}
371
372	/*
373	** Find the closest common ancestor of two nodes. "Closest" means the
374	** fewest number of arcs.
375	*/
376	int path_common_ancestor(int iMe, int iYou){
377	Stmt s;
378	PathNode *pThis;
379	PathNode *p;
380	Bag me, you;
381
382	if( iMe==iYou ) return iMe;
383	if( iMe==0 \|\| iYou==0 ) return 0;
	@@ -323,45 +388,40 @@
388	db_prepare(&s, "SELECT pid FROM plink WHERE cid=:cid");
389	bag_init(&me);
390	bag_insert(&me, iMe);
391	bag_init(&you);
392	bag_insert(&you, iYou);
393	while( (pThis = pqueuex_extract_ptr(&path.pending))!=0 ){
394	db_bind_int(&s, ":cid", pThis->rid);
395	while( db_step(&s)==SQLITE_ROW ){
396	int pid = db_column_int(&s, 0);
397	if( bag_find(pThis->isPrim ? &you : &me, pid) ){
398	/* pid is the common ancestor */
399	PathNode *pNext;
400	for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
401	assert( p!=0 );
402	pNext = p;
403	while( pNext ){
404	pNext = p->pFrom;
405	p->pFrom = pThis;
406	pThis = p;
407	p = pNext;
408	}
409	if( pThis==path.pStart ) path.pStart = path.pEnd;
410	path.pEnd = pThis;
411	path_reverse_path();
412	db_finalize(&s);
413	return pid;
414	}else if( bag_find(pThis->isPrim ? &me : &you, pid) ){
415	/* pid is just an alternative path to a node we've already visited */
416	continue;
417	}
418	p = path_new_node(pid, pThis, 0);
419	p->isPrim = pThis->isPrim;
420	bag_insert(pThis->isPrim ? &me : &you, pid);
421	}
422	db_reset(&s);





423	}
424	db_finalize(&s);
425	path_reset();
426	return 0;
427	}
	@@ -453,11 +513,11 @@
513	}else if(0==iTo){
514	fossil_fatal("Invalid 'to' RID: 0");
515	}
516	if( iFrom==iTo ) return;
517	path_reset();
518	p = path_shortest(iFrom, iTo, 1, revOK==0, 0, 0);
519	if( p==0 ) return;
520	path_reverse_path();
521	db_prepare(&q1,
522	"SELECT pfnid, fnid FROM mlink"
523	" WHERE mid=:mid AND (pfnid>0 OR fid==0)"
524

M src/pqueue.c

+147 -27

		--- src/pqueue.c
		+++ src/pqueue.c
		@@ -15,17 +15,24 @@
15	15	**
16	16	*******************************************************************************
17	17	**
18	18	** This file contains code used to implement a priority queue.
19	19	** A priority queue is a list of items order by a floating point
20		-** value. We can insert integers with each integer tied to its
21		-** value then extract the integer with the smallest value.
	20	+** value. Each value can be associated with either a pointer or
	21	+** an integer. Items are inserted into the queue in an arbitrary
	22	+** order, but are returned in order of the floating point value.
	23	+**
	24	+** This implementation uses a heap of QueueElement objects. The
	25	+** root of the heap is PQueue.a[0]. Each node a[x] has two daughter
	26	+** nodes a[x2+1] and a[x2+2]. The mother node of a[y] is a[(y-1)/2]
	27	+** (assuming integer division rounded down). The following is always true:
	28	+**
	29	+** The value of any node is less than or equal two the values
	30	+** of both daughter nodes. (The Heap Property).
22	31	**
23		-** The way this queue is used, we never expect it to contain more
24		-** than 2 or 3 elements, so a simple array is sufficient as the
25		-** implementation. This could give worst case O(N) insert times,
26		-** but because of the nature of the problem we expect O(1) performance.
	32	+** A consequence of the heap property is that a[0] always contains
	33	+** the node with the smallest value.
27	34	**
28	35	** Compatibility note: Some versions of OpenSSL export a symbols
29	36	** like "pqueue_insert". This is, technically, a bug in OpenSSL.
30	37	** We work around it here by using "pqueuex_" instead of "pqueue_".
31	38	*/
		@@ -41,11 +48,14 @@
41	48	*/
42	49	struct PQueue {
43	50	int cnt; /* Number of entries in the queue */
44	51	int sz; /* Number of slots in a[] */
45	52	struct QueueElement {
46		- int id; /* ID of the element */
	53	+ union {
	54	+ int id; /* ID of the element */
	55	+ void p; / Pointer to an object */
	56	+ } u;
47	57	double value; /* Value of element. Kept in ascending order */
48	58	} *a;
49	59	};
50	60	#endif
51	61
		@@ -69,44 +79,154 @@
69	79	*/
70	80	static void pqueuex_resize(PQueue *p, int N){
71	81	p->a = fossil_realloc(p->a, sizeof(p->a[0])*N);
72	82	p->sz = N;
73	83	}
	84	+
	85	+/*
	86	+** Allocate a new queue entry and return a pointer to it.
	87	+*/
	88	+static struct QueueElement pqueuex_new_entry(PQueue p){
	89	+ if( p->cnt+1>p->sz ){
	90	+ pqueuex_resize(p, p->cnt+7);
	91	+ }
	92	+ return &p->a[p->cnt++];
	93	+}
	94	+
	95	+/*
	96	+** Element p->a[p->cnt-1] has just been inserted. Shift entries
	97	+** around so as to preserve the heap property.
	98	+*/
	99	+static void pqueuex_rebalance(PQueue *p){
	100	+ int i, j;
	101	+ struct QueueElement *a = p->a;
	102	+ i = p->cnt-1;
	103	+ while( (j = (i-1)/2)>=0 && a[j].value>a[i].value ){
	104	+ struct QueueElement t = a[j];
	105	+ a[j] = a[i];
	106	+ a[i] = t;
	107	+ i = j;
	108	+ }
	109	+}
74	110
75	111	/*
76	112	** Insert element e into the queue.
77	113	*/
78	114	void pqueuex_insert(PQueue *p, int e, double v){
	115	+ struct QueueElement *pE = pqueuex_new_entry(p);
	116	+ pE->value = v;
	117	+ pE->u.id = e;
	118	+ pqueuex_rebalance(p);
	119	+}
	120	+void pqueuex_insert_ptr(PQueue p, void pPtr, double v){
	121	+ struct QueueElement *pE = pqueuex_new_entry(p);
	122	+ pE->value = v;
	123	+ pE->u.p = pPtr;
	124	+ pqueuex_rebalance(p);
	125	+}
	126	+
	127	+/*
	128	+** Remove and discard p->a[0] element from the queue. Rearrange
	129	+** nodes to preserve the heap property.
	130	+*/
	131	+static void pqueuex_pop(PQueue *p){
79	132	int i, j;
80		- if( p->cnt+1>p->sz ){
81		- pqueuex_resize(p, p->cnt+5);
82		- }
83		- for(i=0; i<p->cnt; i++){
84		- if( p->a[i].value>v ){
85		- for(j=p->cnt; j>i; j--){
86		- p->a[j] = p->a[j-1];
87		- }
88		- break;
89		- }
90		- }
91		- p->a[i].id = e;
92		- p->a[i].value = v;
93		- p->cnt++;
	133	+ struct QueueElement *a = p->a;
	134	+ struct QueueElement tmp;
	135	+ i = 0;
	136	+ a[0] = a[p->cnt-1];
	137	+ p->cnt--;
	138	+ while( (j = i*2+1)<p->cnt ){
	139	+ if( j+1<p->cnt && a[j].value > a[j+1].value ) j++;
	140	+ if( a[i].value < a[j].value ) break;
	141	+ tmp = a[i];
	142	+ a[i] = a[j];
	143	+ a[j] = tmp;
	144	+ i = j;
	145	+ }
94	146	}
95	147
96	148	/*
97	149	** Extract the first element from the queue (the element with
98	150	** the smallest value) and return its ID. Return 0 if the queue
99	151	** is empty.
100	152	*/
101	153	int pqueuex_extract(PQueue *p){
102		- int e, i;
	154	+ int e;
	155	+ if( p->cnt==0 ){
	156	+ return 0;
	157	+ }
	158	+ e = p->a[0].u.id;
	159	+ pqueuex_pop(p);
	160	+ return e;
	161	+}
	162	+void pqueuex_extract_ptr(PQueue p){
	163	+ void *pPtr;
103	164	if( p->cnt==0 ){
104	165	return 0;
105	166	}
106		- e = p->a[0].id;
107		- for(i=0; i<p->cnt-1; i++){
108		- p->a[i] = p->a[i+1];
	167	+ pPtr = p->a[0].u.p;
	168	+ pqueuex_pop(p);
	169	+ return pPtr;
	170	+}
	171	+
	172	+/*
	173	+** Print the entire heap associated with the test-pqueue command.
	174	+*/
	175	+static void pqueuex_test_print(PQueue *p){
	176	+ int j;
	177	+ for(j=0; j<p->cnt; j++){
	178	+ fossil_print("(%d) %g/%s ",j,p->a[j].value,p->a[j].u.p);
	179	+ }
	180	+ fossil_print("\n");
	181	+}
	182	+
	183	+/*
	184	+** COMMAND: test-pqueue
	185	+**
	186	+** This command is used for testing the PQueue object. There are one
	187	+** or more arguments, each of the form:
	188	+**
	189	+** (1) NUMBER/TEXT
	190	+** (2) ^
	191	+** (3) -v
	192	+**
	193	+** Form (1) arguments add an entry to the queue with value NUMBER and
	194	+** content TEXT. Form (2) pops off the queue entry with the smallest
	195	+** value. Form (3) (the -v option) causes the heap to be displayed after
	196	+** each subsequent operation.
	197	+*/
	198	+void pqueuex_test_cmd(void){
	199	+ int i;
	200	+ PQueue x;
	201	+ const char *zId;
	202	+ int bDebug = 0;
	203	+
	204	+ pqueuex_init(&x);
	205	+ for(i=2; i<g.argc; i++){
	206	+ const char *zArg = g.argv[i];
	207	+ if( strcmp(zArg,"-v")==0 ){
	208	+ bDebug = 1;
	209	+ }else if( strcmp(zArg, "^")==0 ){
	210	+ zId = pqueuex_extract_ptr(&x);
	211	+ if( zId==0 ){
	212	+ fossil_print("%2d: POP NULL\n", i);
	213	+ }else{
	214	+ fossil_print("%2d: POP \"%s\"\n", i, zId);
	215	+ }
	216	+ if( bDebug) pqueuex_test_print(&x);
	217	+ }else{
	218	+ double r = atof(zArg);
	219	+ zId = strchr(zArg,'/');
	220	+ if( zId==0 ) zId = zArg;
	221	+ if( zId[0]=='/' ) zId++;
	222	+ pqueuex_insert_ptr(&x, (void*)zId, r);
	223	+ fossil_print("%2d: INSERT \"%s\"\n", i, zId);
	224	+ if( bDebug) pqueuex_test_print(&x);
	225	+ }
	226	+ }
	227	+ while( (zId = pqueuex_extract_ptr(&x))!=0 ){
	228	+ fossil_print("... POP \"%s\"\n", zId);
	229	+ if( bDebug) pqueuex_test_print(&x);
109	230	}
110		- p->cnt--;
111		- return e;
	231	+ pqueuex_clear(&x);
112	232	}
113	233

	--- src/pqueue.c
	+++ src/pqueue.c
	@@ -15,17 +15,24 @@
15	**
16	*******************************************************************************
17	**
18	** This file contains code used to implement a priority queue.
19	** A priority queue is a list of items order by a floating point
20	** value. We can insert integers with each integer tied to its
21	** value then extract the integer with the smallest value.









22	**
23	** The way this queue is used, we never expect it to contain more
24	** than 2 or 3 elements, so a simple array is sufficient as the
25	** implementation. This could give worst case O(N) insert times,
26	** but because of the nature of the problem we expect O(1) performance.
27	**
28	** Compatibility note: Some versions of OpenSSL export a symbols
29	** like "pqueue_insert". This is, technically, a bug in OpenSSL.
30	** We work around it here by using "pqueuex_" instead of "pqueue_".
31	*/
	@@ -41,11 +48,14 @@
41	*/
42	struct PQueue {
43	int cnt; /* Number of entries in the queue */
44	int sz; /* Number of slots in a[] */
45	struct QueueElement {
46	int id; /* ID of the element */



47	double value; /* Value of element. Kept in ascending order */
48	} *a;
49	};
50	#endif
51
	@@ -69,44 +79,154 @@
69	*/
70	static void pqueuex_resize(PQueue *p, int N){
71	p->a = fossil_realloc(p->a, sizeof(p->a[0])*N);
72	p->sz = N;
73	}


























74
75	/*
76	** Insert element e into the queue.
77	*/
78	void pqueuex_insert(PQueue *p, int e, double v){

















79	int i, j;
80	if( p->cnt+1>p->sz ){
81	pqueuex_resize(p, p->cnt+5);
82	}
83	for(i=0; i<p->cnt; i++){
84	if( p->a[i].value>v ){
85	for(j=p->cnt; j>i; j--){
86	p->a[j] = p->a[j-1];
87	}
88	break;
89	}
90	}
91	p->a[i].id = e;
92	p->a[i].value = v;
93	p->cnt++;
94	}
95
96	/*
97	** Extract the first element from the queue (the element with
98	** the smallest value) and return its ID. Return 0 if the queue
99	** is empty.
100	*/
101	int pqueuex_extract(PQueue *p){
102	int e, i;









103	if( p->cnt==0 ){
104	return 0;
105	}
106	e = p->a[0].id;
107	for(i=0; i<p->cnt-1; i++){
108	p->a[i] = p->a[i+1];




























































109	}
110	p->cnt--;
111	return e;
112	}
113

	--- src/pqueue.c
	+++ src/pqueue.c
	@@ -15,17 +15,24 @@
15	**
16	*******************************************************************************
17	**
18	** This file contains code used to implement a priority queue.
19	** A priority queue is a list of items order by a floating point
20	** value. Each value can be associated with either a pointer or
21	** an integer. Items are inserted into the queue in an arbitrary
22	** order, but are returned in order of the floating point value.
23	**
24	** This implementation uses a heap of QueueElement objects. The
25	** root of the heap is PQueue.a[0]. Each node a[x] has two daughter
26	** nodes a[x2+1] and a[x2+2]. The mother node of a[y] is a[(y-1)/2]
27	** (assuming integer division rounded down). The following is always true:
28	**
29	** The value of any node is less than or equal two the values
30	** of both daughter nodes. (The Heap Property).
31	**
32	** A consequence of the heap property is that a[0] always contains
33	** the node with the smallest value.


34	**
35	** Compatibility note: Some versions of OpenSSL export a symbols
36	** like "pqueue_insert". This is, technically, a bug in OpenSSL.
37	** We work around it here by using "pqueuex_" instead of "pqueue_".
38	*/
	@@ -41,11 +48,14 @@
48	*/
49	struct PQueue {
50	int cnt; /* Number of entries in the queue */
51	int sz; /* Number of slots in a[] */
52	struct QueueElement {
53	union {
54	int id; /* ID of the element */
55	void p; / Pointer to an object */
56	} u;
57	double value; /* Value of element. Kept in ascending order */
58	} *a;
59	};
60	#endif
61
	@@ -69,44 +79,154 @@
79	*/
80	static void pqueuex_resize(PQueue *p, int N){
81	p->a = fossil_realloc(p->a, sizeof(p->a[0])*N);
82	p->sz = N;
83	}
84
85	/*
86	** Allocate a new queue entry and return a pointer to it.
87	*/
88	static struct QueueElement pqueuex_new_entry(PQueue p){
89	if( p->cnt+1>p->sz ){
90	pqueuex_resize(p, p->cnt+7);
91	}
92	return &p->a[p->cnt++];
93	}
94
95	/*
96	** Element p->a[p->cnt-1] has just been inserted. Shift entries
97	** around so as to preserve the heap property.
98	*/
99	static void pqueuex_rebalance(PQueue *p){
100	int i, j;
101	struct QueueElement *a = p->a;
102	i = p->cnt-1;
103	while( (j = (i-1)/2)>=0 && a[j].value>a[i].value ){
104	struct QueueElement t = a[j];
105	a[j] = a[i];
106	a[i] = t;
107	i = j;
108	}
109	}
110
111	/*
112	** Insert element e into the queue.
113	*/
114	void pqueuex_insert(PQueue *p, int e, double v){
115	struct QueueElement *pE = pqueuex_new_entry(p);
116	pE->value = v;
117	pE->u.id = e;
118	pqueuex_rebalance(p);
119	}
120	void pqueuex_insert_ptr(PQueue p, void pPtr, double v){
121	struct QueueElement *pE = pqueuex_new_entry(p);
122	pE->value = v;
123	pE->u.p = pPtr;
124	pqueuex_rebalance(p);
125	}
126
127	/*
128	** Remove and discard p->a[0] element from the queue. Rearrange
129	** nodes to preserve the heap property.
130	*/
131	static void pqueuex_pop(PQueue *p){
132	int i, j;
133	struct QueueElement *a = p->a;
134	struct QueueElement tmp;
135	i = 0;
136	a[0] = a[p->cnt-1];
137	p->cnt--;
138	while( (j = i*2+1)<p->cnt ){
139	if( j+1<p->cnt && a[j].value > a[j+1].value ) j++;
140	if( a[i].value < a[j].value ) break;
141	tmp = a[i];
142	a[i] = a[j];
143	a[j] = tmp;
144	i = j;
145	}

146	}
147
148	/*
149	** Extract the first element from the queue (the element with
150	** the smallest value) and return its ID. Return 0 if the queue
151	** is empty.
152	*/
153	int pqueuex_extract(PQueue *p){
154	int e;
155	if( p->cnt==0 ){
156	return 0;
157	}
158	e = p->a[0].u.id;
159	pqueuex_pop(p);
160	return e;
161	}
162	void pqueuex_extract_ptr(PQueue p){
163	void *pPtr;
164	if( p->cnt==0 ){
165	return 0;
166	}
167	pPtr = p->a[0].u.p;
168	pqueuex_pop(p);
169	return pPtr;
170	}
171
172	/*
173	** Print the entire heap associated with the test-pqueue command.
174	*/
175	static void pqueuex_test_print(PQueue *p){
176	int j;
177	for(j=0; j<p->cnt; j++){
178	fossil_print("(%d) %g/%s ",j,p->a[j].value,p->a[j].u.p);
179	}
180	fossil_print("\n");
181	}
182
183	/*
184	** COMMAND: test-pqueue
185	**
186	** This command is used for testing the PQueue object. There are one
187	** or more arguments, each of the form:
188	**
189	** (1) NUMBER/TEXT
190	** (2) ^
191	** (3) -v
192	**
193	** Form (1) arguments add an entry to the queue with value NUMBER and
194	** content TEXT. Form (2) pops off the queue entry with the smallest
195	** value. Form (3) (the -v option) causes the heap to be displayed after
196	** each subsequent operation.
197	*/
198	void pqueuex_test_cmd(void){
199	int i;
200	PQueue x;
201	const char *zId;
202	int bDebug = 0;
203
204	pqueuex_init(&x);
205	for(i=2; i<g.argc; i++){
206	const char *zArg = g.argv[i];
207	if( strcmp(zArg,"-v")==0 ){
208	bDebug = 1;
209	}else if( strcmp(zArg, "^")==0 ){
210	zId = pqueuex_extract_ptr(&x);
211	if( zId==0 ){
212	fossil_print("%2d: POP NULL\n", i);
213	}else{
214	fossil_print("%2d: POP \"%s\"\n", i, zId);
215	}
216	if( bDebug) pqueuex_test_print(&x);
217	}else{
218	double r = atof(zArg);
219	zId = strchr(zArg,'/');
220	if( zId==0 ) zId = zArg;
221	if( zId[0]=='/' ) zId++;
222	pqueuex_insert_ptr(&x, (void*)zId, r);
223	fossil_print("%2d: INSERT \"%s\"\n", i, zId);
224	if( bDebug) pqueuex_test_print(&x);
225	}
226	}
227	while( (zId = pqueuex_extract_ptr(&x))!=0 ){
228	fossil_print("... POP \"%s\"\n", zId);
229	if( bDebug) pqueuex_test_print(&x);
230	}
231	pqueuex_clear(&x);

232	}
233

M src/timeline.c

+40 -31

		--- src/timeline.c
		+++ src/timeline.c
		@@ -1113,11 +1113,11 @@
1113	1113	return mtime;
1114	1114	}
1115	1115	}
1116	1116	rid = symbolic_name_to_rid(z, "*");
1117	1117	if( rid ){
1118		- mtime = db_double(0.0, "SELECT mtime FROM event WHERE objid=%d", rid);
	1118	+ mtime = mtime_of_rid(rid, 0.0);
1119	1119	}else{
1120	1120	mtime = db_double(-1.0,
1121	1121	"SELECT max(event.mtime) FROM event, tag, tagxref"
1122	1122	" WHERE tag.tagname GLOB 'event-%q*'"
1123	1123	" AND tagxref.tagid=tag.tagid AND tagxref.tagtype"
		@@ -1408,11 +1408,12 @@
1408	1408	" AND plink.mtime<=(SELECT max(event.mtime) FROM tagxref, event"
1409	1409	" WHERE tagxref.tagid=%d AND tagxref.tagtype>0"
1410	1410	" AND event.objid=tagxref.rid)"
1411	1411	" ORDER BY plink.mtime)"
1412	1412	"SELECT id FROM dx, tagxref"
1413		- " WHERE tagid=%d AND tagtype>0 AND rid=id LIMIT 1",
	1413	+ " WHERE tagid=%d AND tagtype>0 AND rid=id"
	1414	+ " ORDER BY dx.mtime LIMIT 1",
1414	1415	iFrom, iFrom, tagId, tagId
1415	1416	);
1416	1417	}else{
1417	1418	db_prepare(&q,
1418	1419	"WITH RECURSIVE dx(id,mtime) AS ("
		@@ -1439,11 +1440,12 @@
1439	1440	" AND event.mtime>=(SELECT min(event.mtime) FROM tagxref, event"
1440	1441	" WHERE tagxref.tagid=%d AND tagxref.tagtype>0"
1441	1442	" AND event.objid=tagxref.rid)"
1442	1443	" ORDER BY event.mtime DESC)"
1443	1444	"SELECT id FROM dx, tagxref"
1444		- " WHERE tagid=%d AND tagtype>0 AND rid=id LIMIT 1",
	1445	+ " WHERE tagid=%d AND tagtype>0 AND rid=id"
	1446	+ " ORDER BY dx.mtime DESC LIMIT 1",
1445	1447	iFrom, iFrom, tagId, tagId
1446	1448	);
1447	1449	}else{
1448	1450	db_prepare(&q,
1449	1451	"WITH RECURSIVE dx(id,mtime) AS ("
		@@ -1572,14 +1574,14 @@
1572	1574	** dp=CHECKIN Same as 'd=CHECKIN&p=CHECKIN'
1573	1575	** dp2=CKIN2 Same as 'd2=CKIN2&p2=CKIN2'
1574	1576	** df=CHECKIN Same as 'd=CHECKIN&n1=all&nd'. Mnemonic: "Derived From"
1575	1577	** bt=CHECKIN "Back To". Show ancenstors going back to CHECKIN
1576	1578	** p=CX ... from CX back to time of CHECKIN
1577		-** from=CX ... shortest path from CX back to CHECKIN
	1579	+** from=CX ... path from CX back to CHECKIN
1578	1580	** ft=CHECKIN "Forward To": Show decendents forward to CHECKIN
1579	1581	** d=CX ... from CX up to the time of CHECKIN
1580		-** from=CX ... shortest path from CX up to CHECKIN
	1582	+** from=CX ... path from CX up to CHECKIN
1581	1583	** t=TAG Show only check-ins with the given TAG
1582	1584	** r=TAG Same as 't=TAG&rel'. Mnemonic: "Related"
1583	1585	** tl=TAGLIST Same as 't=TAGLIST&ms=brlist'. Mnemonic: "Tag List"
1584	1586	** rl=TAGLIST Same as 'r=TAGLIST&ms=brlist'. Mnemonic: "Related List"
1585	1587	** ml=TAGLIST Same as 'tl=TAGLIST&mionly'. Mnemonic: "Merge-in List"
		@@ -1600,20 +1602,21 @@
1600	1602	** nsm Omit the submenu
1601	1603	** nc Omit all graph colors other than highlights
1602	1604	** v Show details of files changed
1603	1605	** vfx Show complete text of forum messages
1604	1606	** f=CHECKIN Family (immediate parents and children) of CHECKIN
1605		-** from=CHECKIN Path through common ancestor from...
1606		-** to=CHECKIN ... to this
1607		-** to2=CHECKIN ... backup name if to= doesn't resolve
1608		-** shortest ... show only the shortest path
1609		-** rel ... also show related checkins
1610		-** bt=PRIOR ... path from CHECKIN back to PRIOR
1611		-** ft=LATER ... path from CHECKIN forward to LATER
1612		-** me=CHECKIN Most direct path from...
1613		-** you=CHECKIN ... to this
1614		-** rel ... also show related checkins
	1607	+** from=CHECKIN Path through common ancestor from CHECKIN...
	1608	+** to=CHECKIN ... to this
	1609	+** to2=CHECKIN ... backup name if to= doesn't resolve
	1610	+** shortest ... pick path with least number of nodes
	1611	+** rel ... also show related checkins
	1612	+** min ... hide long sequences along same branch
	1613	+** bt=PRIOR ... path from CHECKIN back to PRIOR
	1614	+** ft=LATER ... path from CHECKIN forward to LATER
	1615	+** me=CHECKIN Most direct path from CHECKIN...
	1616	+** you=CHECKIN ... to this
	1617	+** rel ... also show related checkins
1615	1618	** uf=FILE_HASH Show only check-ins that contain the given file version
1616	1619	** All qualifying check-ins are shown unless there is
1617	1620	** also an n= or n1= query parameter.
1618	1621	** chng=GLOBLIST Show only check-ins that involve changes to a file whose
1619	1622	** name matches one of the comma-separate GLOBLIST
		@@ -1696,11 +1699,11 @@
1696	1699	const char zThisUser = 0; / Suppress links to this user */
1697	1700	HQuery url; /* URL for various branch links */
1698	1701	int from_rid = name_to_typed_rid(P("from"),"ci"); /* from= for paths */
1699	1702	const char *zTo2 = 0;
1700	1703	int to_rid = name_choice("to","to2",&zTo2); /* to= for path timelines */
1701		- int noMerge = P("shortest")==0; /* Follow merge links if shorter */
	1704	+ int bShort = P("shortest")!=0; /* shortest possible path */
1702	1705	int me_rid = name_to_typed_rid(P("me"),"ci"); /* me= for common ancestory */
1703	1706	int you_rid = name_to_typed_rid(P("you"),"ci");/* you= for common ancst */
1704	1707	int pd_rid;
1705	1708	const char zDPName; / Value of p=, d=, or dp= params */
1706	1709	double rBefore, rAfter, rCirca; /* Boundary times */
		@@ -1717,10 +1720,11 @@
1717	1720	int showCherrypicks = 1; /* True to show cherrypick merges */
1718	1721	int haveParameterN; /* True if n= query parameter present */
1719	1722	int from_to_mode = 0; /* 0: from,to. 1: from,ft 2: from,bt */
1720	1723	int showSql = PB("showsql"); /* True to show the SQL */
1721	1724	Blob allSql; /* Copy of all SQL text */
	1725	+ int bMin = P("min")!=0; /* True if "min" query parameter used */
1722	1726
1723	1727	login_check_credentials();
1724	1728	url_initialize(&url, "timeline");
1725	1729	cgi_query_parameters_to_url(&url);
1726	1730	blob_init(&allSql, 0, 0);
		@@ -2072,20 +2076,22 @@
2072	2076	const char *zTo = 0;
2073	2077	Blob ins;
2074	2078	int nNodeOnPath = 0;
2075	2079	int commonAncs = 0; /* Common ancestors of me_rid and you_rid. */
2076	2080	int earlierRid = 0, laterRid = 0;
	2081	+ int cost = bShort ? 0 : 1;
	2082	+ int nSkip = 0;
2077	2083
2078	2084	if( from_rid && to_rid ){
2079	2085	if( from_to_mode==0 ){
2080		- p = path_shortest(from_rid, to_rid, noMerge, 0, 0);
	2086	+ p = path_shortest(from_rid, to_rid, 0, 0, 0, cost);
2081	2087	}else if( from_to_mode==1 ){
2082		- p = path_shortest(from_rid, to_rid, 0, 1, 0);
	2088	+ p = path_shortest(from_rid, to_rid, 0, 1, 0, cost);
2083	2089	earlierRid = commonAncs = from_rid;
2084	2090	laterRid = to_rid;
2085	2091	}else{
2086		- p = path_shortest(to_rid, from_rid, 0, 1, 0);
	2092	+ p = path_shortest(to_rid, from_rid, 0, 1, 0, cost);
2087	2093	earlierRid = commonAncs = to_rid;
2088	2094	laterRid = from_rid;
2089	2095	}
2090	2096	zFrom = P("from");
2091	2097	zTo = zTo2 ? zTo2 : P("to");
		@@ -2112,20 +2118,25 @@
2112	2118	);
2113	2119	if( p ){
2114	2120	int cnt = 4;
2115	2121	blob_init(&ins, 0, 0);
2116	2122	blob_append_sql(&ins, "INSERT INTO pathnode(x) VALUES(%d)", p->rid);
2117		- p = p->u.pTo;
2118		- while( p ){
2119		- if( cnt==8 ){
	2123	+ if( p->u.pTo==0 ) bMin = 0;
	2124	+ for(p=p->u.pTo; p; p=p->u.pTo){
	2125	+ if( bMin
	2126	+ && p->u.pTo!=0
	2127	+ && fossil_strcmp(path_branch(p->pFrom),path_branch(p))==0
	2128	+ && fossil_strcmp(path_branch(p),path_branch(p->u.pTo))==0
	2129	+ ){
	2130	+ nSkip++;
	2131	+ }else if( cnt==8 ){
2120	2132	blob_append_sql(&ins, ",\n (%d)", p->rid);
2121	2133	cnt = 0;
2122	2134	}else{
2123	2135	cnt++;
2124	2136	blob_append_sql(&ins, ",(%d)", p->rid);
2125	2137	}
2126		- p = p->u.pTo;
2127	2138	}
2128	2139	}
2129	2140	path_reset();
2130	2141	db_multi_exec("%s", blob_str(&ins)/safe-for-%s/);
2131	2142	blob_reset(&ins);
		@@ -2185,12 +2196,13 @@
2185	2196	style_submenu_checkbox("v", "Files", (zType[0]!='a' && zType[0]!='c'),0);
2186	2197	}
2187	2198	nNodeOnPath = db_int(0, "SELECT count(*) FROM temp.pathnode");
2188	2199	if( nNodeOnPath==1 && from_to_mode>0 ){
2189	2200	blob_appendf(&desc,"Check-in ");
2190		- }else if( from_to_mode>0 ){
2191		- blob_appendf(&desc, "%d check-ins on the shorted path from ",nNodeOnPath);
	2201	+ }else if( bMin ){
	2202	+ blob_appendf(&desc, "%d of %d check-ins along the path from ",
	2203	+ nNodeOnPath, nNodeOnPath+nSkip);
2192	2204	}else{
2193	2205	blob_appendf(&desc, "%d check-ins going from ", nNodeOnPath);
2194	2206	}
2195	2207	if( from_rid==selectedRid ){
2196	2208	blob_appendf(&desc, "<span class='timelineSelected'>");
		@@ -2242,20 +2254,18 @@
2242	2254	nd = 0;
2243	2255	if( d_rid ){
2244	2256	double rStopTime = 9e99;
2245	2257	zFwdTo = P("ft");
2246	2258	if( zFwdTo ){
2247		- double rStartDate = db_double(0.0,
2248		- "SELECT mtime FROM event WHERE objid=%d", d_rid);
	2259	+ double rStartDate = mtime_of_rid(d_rid, 0.0);
2249	2260	ridFwdTo = first_checkin_with_tag_after_date(zFwdTo, rStartDate);
2250	2261	if( ridFwdTo==0 ){
2251	2262	ridFwdTo = name_to_typed_rid(zBackTo,"ci");
2252	2263	}
2253	2264	if( ridFwdTo ){
2254	2265	if( !haveParameterN ) nEntry = 0;
2255		- rStopTime = db_double(9e99,
2256		- "SELECT mtime FROM event WHERE objid=%d", ridFwdTo);
	2266	+ rStopTime = mtime_of_rid(ridFwdTo, 9e99);
2257	2267	}
2258	2268	}
2259	2269	if( rStopTime<9e99 ){
2260	2270	rStopTime += 5.8e-6; /* Round up by 1/2 second */
2261	2271	}
		@@ -2280,12 +2290,11 @@
2280	2290	db_multi_exec("DELETE FROM ok");
2281	2291	}
2282	2292	if( p_rid ){
2283	2293	zBackTo = P("bt");
2284	2294	if( zBackTo ){
2285		- double rDateLimit = db_double(0.0,
2286		- "SELECT mtime FROM event WHERE objid=%d", p_rid);
	2295	+ double rDateLimit = mtime_of_rid(p_rid, 0.0);
2287	2296	ridBackTo = last_checkin_with_tag_before_date(zBackTo, rDateLimit);
2288	2297	if( ridBackTo==0 ){
2289	2298	ridBackTo = name_to_typed_rid(zBackTo,"ci");
2290	2299	}
2291	2300	if( ridBackTo && !haveParameterN ) nEntry = 0;
2292	2301

	--- src/timeline.c
	+++ src/timeline.c
	@@ -1113,11 +1113,11 @@
1113	return mtime;
1114	}
1115	}
1116	rid = symbolic_name_to_rid(z, "*");
1117	if( rid ){
1118	mtime = db_double(0.0, "SELECT mtime FROM event WHERE objid=%d", rid);
1119	}else{
1120	mtime = db_double(-1.0,
1121	"SELECT max(event.mtime) FROM event, tag, tagxref"
1122	" WHERE tag.tagname GLOB 'event-%q*'"
1123	" AND tagxref.tagid=tag.tagid AND tagxref.tagtype"
	@@ -1408,11 +1408,12 @@
1408	" AND plink.mtime<=(SELECT max(event.mtime) FROM tagxref, event"
1409	" WHERE tagxref.tagid=%d AND tagxref.tagtype>0"
1410	" AND event.objid=tagxref.rid)"
1411	" ORDER BY plink.mtime)"
1412	"SELECT id FROM dx, tagxref"
1413	" WHERE tagid=%d AND tagtype>0 AND rid=id LIMIT 1",

1414	iFrom, iFrom, tagId, tagId
1415	);
1416	}else{
1417	db_prepare(&q,
1418	"WITH RECURSIVE dx(id,mtime) AS ("
	@@ -1439,11 +1440,12 @@
1439	" AND event.mtime>=(SELECT min(event.mtime) FROM tagxref, event"
1440	" WHERE tagxref.tagid=%d AND tagxref.tagtype>0"
1441	" AND event.objid=tagxref.rid)"
1442	" ORDER BY event.mtime DESC)"
1443	"SELECT id FROM dx, tagxref"
1444	" WHERE tagid=%d AND tagtype>0 AND rid=id LIMIT 1",

1445	iFrom, iFrom, tagId, tagId
1446	);
1447	}else{
1448	db_prepare(&q,
1449	"WITH RECURSIVE dx(id,mtime) AS ("
	@@ -1572,14 +1574,14 @@
1572	** dp=CHECKIN Same as 'd=CHECKIN&p=CHECKIN'
1573	** dp2=CKIN2 Same as 'd2=CKIN2&p2=CKIN2'
1574	** df=CHECKIN Same as 'd=CHECKIN&n1=all&nd'. Mnemonic: "Derived From"
1575	** bt=CHECKIN "Back To". Show ancenstors going back to CHECKIN
1576	** p=CX ... from CX back to time of CHECKIN
1577	** from=CX ... shortest path from CX back to CHECKIN
1578	** ft=CHECKIN "Forward To": Show decendents forward to CHECKIN
1579	** d=CX ... from CX up to the time of CHECKIN
1580	** from=CX ... shortest path from CX up to CHECKIN
1581	** t=TAG Show only check-ins with the given TAG
1582	** r=TAG Same as 't=TAG&rel'. Mnemonic: "Related"
1583	** tl=TAGLIST Same as 't=TAGLIST&ms=brlist'. Mnemonic: "Tag List"
1584	** rl=TAGLIST Same as 'r=TAGLIST&ms=brlist'. Mnemonic: "Related List"
1585	** ml=TAGLIST Same as 'tl=TAGLIST&mionly'. Mnemonic: "Merge-in List"
	@@ -1600,20 +1602,21 @@
1600	** nsm Omit the submenu
1601	** nc Omit all graph colors other than highlights
1602	** v Show details of files changed
1603	** vfx Show complete text of forum messages
1604	** f=CHECKIN Family (immediate parents and children) of CHECKIN
1605	** from=CHECKIN Path through common ancestor from...
1606	** to=CHECKIN ... to this
1607	** to2=CHECKIN ... backup name if to= doesn't resolve
1608	** shortest ... show only the shortest path
1609	** rel ... also show related checkins
1610	** bt=PRIOR ... path from CHECKIN back to PRIOR
1611	** ft=LATER ... path from CHECKIN forward to LATER
1612	** me=CHECKIN Most direct path from...
1613	** you=CHECKIN ... to this
1614	** rel ... also show related checkins

1615	** uf=FILE_HASH Show only check-ins that contain the given file version
1616	** All qualifying check-ins are shown unless there is
1617	** also an n= or n1= query parameter.
1618	** chng=GLOBLIST Show only check-ins that involve changes to a file whose
1619	** name matches one of the comma-separate GLOBLIST
	@@ -1696,11 +1699,11 @@
1696	const char zThisUser = 0; / Suppress links to this user */
1697	HQuery url; /* URL for various branch links */
1698	int from_rid = name_to_typed_rid(P("from"),"ci"); /* from= for paths */
1699	const char *zTo2 = 0;
1700	int to_rid = name_choice("to","to2",&zTo2); /* to= for path timelines */
1701	int noMerge = P("shortest")==0; /* Follow merge links if shorter */
1702	int me_rid = name_to_typed_rid(P("me"),"ci"); /* me= for common ancestory */
1703	int you_rid = name_to_typed_rid(P("you"),"ci");/* you= for common ancst */
1704	int pd_rid;
1705	const char zDPName; / Value of p=, d=, or dp= params */
1706	double rBefore, rAfter, rCirca; /* Boundary times */
	@@ -1717,10 +1720,11 @@
1717	int showCherrypicks = 1; /* True to show cherrypick merges */
1718	int haveParameterN; /* True if n= query parameter present */
1719	int from_to_mode = 0; /* 0: from,to. 1: from,ft 2: from,bt */
1720	int showSql = PB("showsql"); /* True to show the SQL */
1721	Blob allSql; /* Copy of all SQL text */

1722
1723	login_check_credentials();
1724	url_initialize(&url, "timeline");
1725	cgi_query_parameters_to_url(&url);
1726	blob_init(&allSql, 0, 0);
	@@ -2072,20 +2076,22 @@
2072	const char *zTo = 0;
2073	Blob ins;
2074	int nNodeOnPath = 0;
2075	int commonAncs = 0; /* Common ancestors of me_rid and you_rid. */
2076	int earlierRid = 0, laterRid = 0;


2077
2078	if( from_rid && to_rid ){
2079	if( from_to_mode==0 ){
2080	p = path_shortest(from_rid, to_rid, noMerge, 0, 0);
2081	}else if( from_to_mode==1 ){
2082	p = path_shortest(from_rid, to_rid, 0, 1, 0);
2083	earlierRid = commonAncs = from_rid;
2084	laterRid = to_rid;
2085	}else{
2086	p = path_shortest(to_rid, from_rid, 0, 1, 0);
2087	earlierRid = commonAncs = to_rid;
2088	laterRid = from_rid;
2089	}
2090	zFrom = P("from");
2091	zTo = zTo2 ? zTo2 : P("to");
	@@ -2112,20 +2118,25 @@
2112	);
2113	if( p ){
2114	int cnt = 4;
2115	blob_init(&ins, 0, 0);
2116	blob_append_sql(&ins, "INSERT INTO pathnode(x) VALUES(%d)", p->rid);
2117	p = p->u.pTo;
2118	while( p ){
2119	if( cnt==8 ){






2120	blob_append_sql(&ins, ",\n (%d)", p->rid);
2121	cnt = 0;
2122	}else{
2123	cnt++;
2124	blob_append_sql(&ins, ",(%d)", p->rid);
2125	}
2126	p = p->u.pTo;
2127	}
2128	}
2129	path_reset();
2130	db_multi_exec("%s", blob_str(&ins)/safe-for-%s/);
2131	blob_reset(&ins);
	@@ -2185,12 +2196,13 @@
2185	style_submenu_checkbox("v", "Files", (zType[0]!='a' && zType[0]!='c'),0);
2186	}
2187	nNodeOnPath = db_int(0, "SELECT count(*) FROM temp.pathnode");
2188	if( nNodeOnPath==1 && from_to_mode>0 ){
2189	blob_appendf(&desc,"Check-in ");
2190	}else if( from_to_mode>0 ){
2191	blob_appendf(&desc, "%d check-ins on the shorted path from ",nNodeOnPath);

2192	}else{
2193	blob_appendf(&desc, "%d check-ins going from ", nNodeOnPath);
2194	}
2195	if( from_rid==selectedRid ){
2196	blob_appendf(&desc, "<span class='timelineSelected'>");
	@@ -2242,20 +2254,18 @@
2242	nd = 0;
2243	if( d_rid ){
2244	double rStopTime = 9e99;
2245	zFwdTo = P("ft");
2246	if( zFwdTo ){
2247	double rStartDate = db_double(0.0,
2248	"SELECT mtime FROM event WHERE objid=%d", d_rid);
2249	ridFwdTo = first_checkin_with_tag_after_date(zFwdTo, rStartDate);
2250	if( ridFwdTo==0 ){
2251	ridFwdTo = name_to_typed_rid(zBackTo,"ci");
2252	}
2253	if( ridFwdTo ){
2254	if( !haveParameterN ) nEntry = 0;
2255	rStopTime = db_double(9e99,
2256	"SELECT mtime FROM event WHERE objid=%d", ridFwdTo);
2257	}
2258	}
2259	if( rStopTime<9e99 ){
2260	rStopTime += 5.8e-6; /* Round up by 1/2 second */
2261	}
	@@ -2280,12 +2290,11 @@
2280	db_multi_exec("DELETE FROM ok");
2281	}
2282	if( p_rid ){
2283	zBackTo = P("bt");
2284	if( zBackTo ){
2285	double rDateLimit = db_double(0.0,
2286	"SELECT mtime FROM event WHERE objid=%d", p_rid);
2287	ridBackTo = last_checkin_with_tag_before_date(zBackTo, rDateLimit);
2288	if( ridBackTo==0 ){
2289	ridBackTo = name_to_typed_rid(zBackTo,"ci");
2290	}
2291	if( ridBackTo && !haveParameterN ) nEntry = 0;
2292

	--- src/timeline.c
	+++ src/timeline.c
	@@ -1113,11 +1113,11 @@
1113	return mtime;
1114	}
1115	}
1116	rid = symbolic_name_to_rid(z, "*");
1117	if( rid ){
1118	mtime = mtime_of_rid(rid, 0.0);
1119	}else{
1120	mtime = db_double(-1.0,
1121	"SELECT max(event.mtime) FROM event, tag, tagxref"
1122	" WHERE tag.tagname GLOB 'event-%q*'"
1123	" AND tagxref.tagid=tag.tagid AND tagxref.tagtype"
	@@ -1408,11 +1408,12 @@
1408	" AND plink.mtime<=(SELECT max(event.mtime) FROM tagxref, event"
1409	" WHERE tagxref.tagid=%d AND tagxref.tagtype>0"
1410	" AND event.objid=tagxref.rid)"
1411	" ORDER BY plink.mtime)"
1412	"SELECT id FROM dx, tagxref"
1413	" WHERE tagid=%d AND tagtype>0 AND rid=id"
1414	" ORDER BY dx.mtime LIMIT 1",
1415	iFrom, iFrom, tagId, tagId
1416	);
1417	}else{
1418	db_prepare(&q,
1419	"WITH RECURSIVE dx(id,mtime) AS ("
	@@ -1439,11 +1440,12 @@
1440	" AND event.mtime>=(SELECT min(event.mtime) FROM tagxref, event"
1441	" WHERE tagxref.tagid=%d AND tagxref.tagtype>0"
1442	" AND event.objid=tagxref.rid)"
1443	" ORDER BY event.mtime DESC)"
1444	"SELECT id FROM dx, tagxref"
1445	" WHERE tagid=%d AND tagtype>0 AND rid=id"
1446	" ORDER BY dx.mtime DESC LIMIT 1",
1447	iFrom, iFrom, tagId, tagId
1448	);
1449	}else{
1450	db_prepare(&q,
1451	"WITH RECURSIVE dx(id,mtime) AS ("
	@@ -1572,14 +1574,14 @@
1574	** dp=CHECKIN Same as 'd=CHECKIN&p=CHECKIN'
1575	** dp2=CKIN2 Same as 'd2=CKIN2&p2=CKIN2'
1576	** df=CHECKIN Same as 'd=CHECKIN&n1=all&nd'. Mnemonic: "Derived From"
1577	** bt=CHECKIN "Back To". Show ancenstors going back to CHECKIN
1578	** p=CX ... from CX back to time of CHECKIN
1579	** from=CX ... path from CX back to CHECKIN
1580	** ft=CHECKIN "Forward To": Show decendents forward to CHECKIN
1581	** d=CX ... from CX up to the time of CHECKIN
1582	** from=CX ... path from CX up to CHECKIN
1583	** t=TAG Show only check-ins with the given TAG
1584	** r=TAG Same as 't=TAG&rel'. Mnemonic: "Related"
1585	** tl=TAGLIST Same as 't=TAGLIST&ms=brlist'. Mnemonic: "Tag List"
1586	** rl=TAGLIST Same as 'r=TAGLIST&ms=brlist'. Mnemonic: "Related List"
1587	** ml=TAGLIST Same as 'tl=TAGLIST&mionly'. Mnemonic: "Merge-in List"
	@@ -1600,20 +1602,21 @@
1602	** nsm Omit the submenu
1603	** nc Omit all graph colors other than highlights
1604	** v Show details of files changed
1605	** vfx Show complete text of forum messages
1606	** f=CHECKIN Family (immediate parents and children) of CHECKIN
1607	** from=CHECKIN Path through common ancestor from CHECKIN...
1608	** to=CHECKIN ... to this
1609	** to2=CHECKIN ... backup name if to= doesn't resolve
1610	** shortest ... pick path with least number of nodes
1611	** rel ... also show related checkins
1612	** min ... hide long sequences along same branch
1613	** bt=PRIOR ... path from CHECKIN back to PRIOR
1614	** ft=LATER ... path from CHECKIN forward to LATER
1615	** me=CHECKIN Most direct path from CHECKIN...
1616	** you=CHECKIN ... to this
1617	** rel ... also show related checkins
1618	** uf=FILE_HASH Show only check-ins that contain the given file version
1619	** All qualifying check-ins are shown unless there is
1620	** also an n= or n1= query parameter.
1621	** chng=GLOBLIST Show only check-ins that involve changes to a file whose
1622	** name matches one of the comma-separate GLOBLIST
	@@ -1696,11 +1699,11 @@
1699	const char zThisUser = 0; / Suppress links to this user */
1700	HQuery url; /* URL for various branch links */
1701	int from_rid = name_to_typed_rid(P("from"),"ci"); /* from= for paths */
1702	const char *zTo2 = 0;
1703	int to_rid = name_choice("to","to2",&zTo2); /* to= for path timelines */
1704	int bShort = P("shortest")!=0; /* shortest possible path */
1705	int me_rid = name_to_typed_rid(P("me"),"ci"); /* me= for common ancestory */
1706	int you_rid = name_to_typed_rid(P("you"),"ci");/* you= for common ancst */
1707	int pd_rid;
1708	const char zDPName; / Value of p=, d=, or dp= params */
1709	double rBefore, rAfter, rCirca; /* Boundary times */
	@@ -1717,10 +1720,11 @@
1720	int showCherrypicks = 1; /* True to show cherrypick merges */
1721	int haveParameterN; /* True if n= query parameter present */
1722	int from_to_mode = 0; /* 0: from,to. 1: from,ft 2: from,bt */
1723	int showSql = PB("showsql"); /* True to show the SQL */
1724	Blob allSql; /* Copy of all SQL text */
1725	int bMin = P("min")!=0; /* True if "min" query parameter used */
1726
1727	login_check_credentials();
1728	url_initialize(&url, "timeline");
1729	cgi_query_parameters_to_url(&url);
1730	blob_init(&allSql, 0, 0);
	@@ -2072,20 +2076,22 @@
2076	const char *zTo = 0;
2077	Blob ins;
2078	int nNodeOnPath = 0;
2079	int commonAncs = 0; /* Common ancestors of me_rid and you_rid. */
2080	int earlierRid = 0, laterRid = 0;
2081	int cost = bShort ? 0 : 1;
2082	int nSkip = 0;
2083
2084	if( from_rid && to_rid ){
2085	if( from_to_mode==0 ){
2086	p = path_shortest(from_rid, to_rid, 0, 0, 0, cost);
2087	}else if( from_to_mode==1 ){
2088	p = path_shortest(from_rid, to_rid, 0, 1, 0, cost);
2089	earlierRid = commonAncs = from_rid;
2090	laterRid = to_rid;
2091	}else{
2092	p = path_shortest(to_rid, from_rid, 0, 1, 0, cost);
2093	earlierRid = commonAncs = to_rid;
2094	laterRid = from_rid;
2095	}
2096	zFrom = P("from");
2097	zTo = zTo2 ? zTo2 : P("to");
	@@ -2112,20 +2118,25 @@
2118	);
2119	if( p ){
2120	int cnt = 4;
2121	blob_init(&ins, 0, 0);
2122	blob_append_sql(&ins, "INSERT INTO pathnode(x) VALUES(%d)", p->rid);
2123	if( p->u.pTo==0 ) bMin = 0;
2124	for(p=p->u.pTo; p; p=p->u.pTo){
2125	if( bMin
2126	&& p->u.pTo!=0
2127	&& fossil_strcmp(path_branch(p->pFrom),path_branch(p))==0
2128	&& fossil_strcmp(path_branch(p),path_branch(p->u.pTo))==0
2129	){
2130	nSkip++;
2131	}else if( cnt==8 ){
2132	blob_append_sql(&ins, ",\n (%d)", p->rid);
2133	cnt = 0;
2134	}else{
2135	cnt++;
2136	blob_append_sql(&ins, ",(%d)", p->rid);
2137	}

2138	}
2139	}
2140	path_reset();
2141	db_multi_exec("%s", blob_str(&ins)/safe-for-%s/);
2142	blob_reset(&ins);
	@@ -2185,12 +2196,13 @@
2196	style_submenu_checkbox("v", "Files", (zType[0]!='a' && zType[0]!='c'),0);
2197	}
2198	nNodeOnPath = db_int(0, "SELECT count(*) FROM temp.pathnode");
2199	if( nNodeOnPath==1 && from_to_mode>0 ){
2200	blob_appendf(&desc,"Check-in ");
2201	}else if( bMin ){
2202	blob_appendf(&desc, "%d of %d check-ins along the path from ",
2203	nNodeOnPath, nNodeOnPath+nSkip);
2204	}else{
2205	blob_appendf(&desc, "%d check-ins going from ", nNodeOnPath);
2206	}
2207	if( from_rid==selectedRid ){
2208	blob_appendf(&desc, "<span class='timelineSelected'>");
	@@ -2242,20 +2254,18 @@
2254	nd = 0;
2255	if( d_rid ){
2256	double rStopTime = 9e99;
2257	zFwdTo = P("ft");
2258	if( zFwdTo ){
2259	double rStartDate = mtime_of_rid(d_rid, 0.0);

2260	ridFwdTo = first_checkin_with_tag_after_date(zFwdTo, rStartDate);
2261	if( ridFwdTo==0 ){
2262	ridFwdTo = name_to_typed_rid(zBackTo,"ci");
2263	}
2264	if( ridFwdTo ){
2265	if( !haveParameterN ) nEntry = 0;
2266	rStopTime = mtime_of_rid(ridFwdTo, 9e99);

2267	}
2268	}
2269	if( rStopTime<9e99 ){
2270	rStopTime += 5.8e-6; /* Round up by 1/2 second */
2271	}
	@@ -2280,12 +2290,11 @@
2290	db_multi_exec("DELETE FROM ok");
2291	}
2292	if( p_rid ){
2293	zBackTo = P("bt");
2294	if( zBackTo ){
2295	double rDateLimit = mtime_of_rid(p_rid, 0.0);

2296	ridBackTo = last_checkin_with_tag_before_date(zBackTo, rDateLimit);
2297	if( ridBackTo==0 ){
2298	ridBackTo = name_to_typed_rid(zBackTo,"ci");
2299	}
2300	if( ridBackTo && !haveParameterN ) nEntry = 0;
2301

Fossil SCM

Keyboard Shortcuts