Fossil SCM

Improvements to the new path_shortest() implementation, include many enhancements to debugging and analysis capabilities.

drh 2025-03-08 21:36 min-from-to
Commit 923dca30146d8636a77775c7e6223abde71c1a0b32ec7b1b724478a5d0600cb3
Parent 14372167c9c3405…
1 file changed +52 -21
~ src/path.c
M src/path.c
+52 -21
--- src/path.c
+++ src/path.c
@@ -52,10 +52,11 @@
5252
 int brCost; /* Extra cost for moving to a different branch */
5353
 int revCost; /* Extra cost for changing directions */
5454
 PathNode *pStart; /* Earliest node */
5555
 PathNode *pEnd; /* Most recent */
5656
 } path;
57
+static int path_debug = 0; /* Flag to enable debugging */
5758
5859
 /*
5960
 ** Return the first (last) element of the computed path.
6061
 */
6162
 PathNode *path_first(void){ return path.pStart; }
@@ -68,10 +69,38 @@
6869
6970
 /*
7071
 ** Return the number of non-hidden steps in the computed path.
7172
 */
7273
 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
+}
73102
74103
 /*
75104
 ** Create a new node and insert it into the path.pending queue.
76105
 */
77106
 static PathNode *path_new_node(int rid, PathNode *pFrom, int isParent){
@@ -99,10 +128,13 @@
99128
 ** along the path. The cost is just the number of nodes back
100129
 ** to the start. We do not need to know the branch name nor
101130
 ** the mtime */
102131
 p->u.rCost += 1.0;
103132
 }
133
+ if( path_debug ){
134
+ fossil_print("PUSH %-50s cost = %g\n", path_rid_desc(p->rid), p->u.rCost);
135
+ }
104136
 pqueuex_insert_ptr(&path.pending, (void*)p, p->u.rCost);
105137
 return p;
106138
 }
107139
108140
 /*
@@ -174,21 +206,24 @@
174206
 );
175207
 }else if( directOnly ){
176208
 db_prepare(&s,
177209
 "SELECT cid, 1 FROM plink WHERE pid=:pid AND isprim "
178210
 "UNION ALL "
179
- "SELECT pid, 0 FROM plink WHERE cid=:pid AND isprim"
211
+ "SELECT pid, 0 FROM plink WHERE :back AND cid=:pid AND isprim"
180212
 );
181213
 }else{
182214
 db_prepare(&s,
183215
 "SELECT cid, 1 FROM plink WHERE pid=:pid "
184216
 "UNION ALL "
185
- "SELECT pid, 0 FROM plink WHERE cid=:pid"
217
+ "SELECT pid, 0 FROM plink WHERE :back AND cid=:pid"
186218
 );
187219
 }
188220
 bag_init(&seen);
189221
 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
+ }
190225
 if( p->rid==iTo ){
191226
 db_finalize(&s);
192227
 path.pEnd = p;
193228
 path_reverse_path();
194229
 for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
@@ -197,10 +232,11 @@
197232
 return path.pStart;
198233
 }
199234
 if( bag_find(&seen, p->rid) ) continue;
200235
 bag_insert(&seen, p->rid);
201236
 db_bind_int(&s, ":pid", p->rid);
237
+ if( !oneWayOnly ) db_bind_int(&s, ":back", !p->fromIsParent);
202238
 while( db_step(&s)==SQLITE_ROW ){
203239
 int cid = db_column_int(&s, 0);
204240
 int isParent = db_column_int(&s, 1);
205241
 PathNode *pNew;
206242
 if( bag_find(&seen, cid) ) continue;
@@ -281,14 +317,19 @@
281317
 }
282318
283319
 /*
284320
 ** COMMAND: test-shortest-path
285321
 **
286
-** Usage: %fossil test-shortest-path ?--no-merge? VERSION1 VERSION2
322
+** Usage: %fossil test-shortest-path [OPTIONS] VERSION1 VERSION2
323
+**
324
+** Report the shortest path between two check-ins. Options:
287325
 **
288
-** Report the shortest path between two check-ins. If the --no-merge flag
289
-** is used, follow only direct parent-child paths and omit merge links.
326
+** --branch-cost N Additional cost N for changing branches
327
+** --debug Show debugging output
328
+** --one-way One-way forwards in time, parent->child only
329
+** --no-merge Follow only direct parent-child paths and omit
330
+** merge links.
290331
 */
291332
 void shortest_path_test_cmd(void){
292333
 int iFrom;
293334
 int iTo;
294335
 PathNode *p;
@@ -299,33 +340,23 @@
299340
300341
 db_find_and_open_repository(0,0);
301342
 directOnly = find_option("no-merge",0,0)!=0;
302343
 oneWay = find_option("one-way",0,0)!=0;
303344
 zBrCost = find_option("branch-cost",0,1);
345
+ if( find_option("debug",0,0)!=0 ) path_debug = 1;
304346
 if( g.argc!=4 ) usage("VERSION1 VERSION2");
305347
 iFrom = name_to_rid(g.argv[2]);
306348
 iTo = name_to_rid(g.argv[3]);
307
- p = path_shortest(iFrom, iTo, directOnly, oneWay, 0, atoi(zBrCost));
349
+ p = path_shortest(iFrom, iTo, directOnly, oneWay, 0,
350
+ zBrCost ? atoi(zBrCost) : 0);
308351
 if( p==0 ){
309352
 fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]);
310353
 }
311354
 for(n=1, p=path.pStart; p; p=p->u.pTo, n++){
312
- char *z;
313
- z = db_text(0,
314
- "SELECT substr(uuid,1,12) || ' ' || datetime(mtime)"
315
- " FROM blob, event"
316
- " WHERE blob.rid=%d AND event.objid=%d AND event.type='ci'",
317
- p->rid, p->rid);
318
- fossil_print("%4d: %5d %s", n, p->rid, z);
319
- fossil_free(z);
320
- if( p->u.pTo ){
321
- fossil_print(" is a %s of\n",
322
- p->u.pTo->fromIsParent ? "parent" : "child");
323
- }else{
324
- fossil_print("\n");
325
- }
326
- }
355
+ fossil_print("%4d: %s\n", n, path_rid_desc(p->rid));
356
+ }
357
+ path_debug = 0;
327358
 }
328359
329360
 /*
330361
 ** Find the closest common ancestor of two nodes. "Closest" means the
331362
 ** fewest number of arcs.
332363
--- src/path.c
+++ src/path.c
@@ -52,10 +52,11 @@
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
58 /*
59 ** Return the first (last) element of the computed path.
60 */
61 PathNode *path_first(void){ return path.pStart; }
@@ -68,10 +69,38 @@
68
69 /*
70 ** Return the number of non-hidden steps in the computed path.
71 */
72 int path_length_not_hidden(void){ return path.nNotHidden; }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
73
74 /*
75 ** Create a new node and insert it into the path.pending queue.
76 */
77 static PathNode *path_new_node(int rid, PathNode *pFrom, int isParent){
@@ -99,10 +128,13 @@
99 ** along the path. The cost is just the number of nodes back
100 ** to the start. We do not need to know the branch name nor
101 ** the mtime */
102 p->u.rCost += 1.0;
103 }
 
 
 
104 pqueuex_insert_ptr(&path.pending, (void*)p, p->u.rCost);
105 return p;
106 }
107
108 /*
@@ -174,21 +206,24 @@
174 );
175 }else if( directOnly ){
176 db_prepare(&s,
177 "SELECT cid, 1 FROM plink WHERE pid=:pid AND isprim "
178 "UNION ALL "
179 "SELECT pid, 0 FROM plink WHERE cid=:pid AND isprim"
180 );
181 }else{
182 db_prepare(&s,
183 "SELECT cid, 1 FROM plink WHERE pid=:pid "
184 "UNION ALL "
185 "SELECT pid, 0 FROM plink WHERE cid=:pid"
186 );
187 }
188 bag_init(&seen);
189 while( (p = pqueuex_extract_ptr(&path.pending))!=0 ){
 
 
 
190 if( p->rid==iTo ){
191 db_finalize(&s);
192 path.pEnd = p;
193 path_reverse_path();
194 for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
@@ -197,10 +232,11 @@
197 return path.pStart;
198 }
199 if( bag_find(&seen, p->rid) ) continue;
200 bag_insert(&seen, p->rid);
201 db_bind_int(&s, ":pid", p->rid);
 
202 while( db_step(&s)==SQLITE_ROW ){
203 int cid = db_column_int(&s, 0);
204 int isParent = db_column_int(&s, 1);
205 PathNode *pNew;
206 if( bag_find(&seen, cid) ) continue;
@@ -281,14 +317,19 @@
281 }
282
283 /*
284 ** COMMAND: test-shortest-path
285 **
286 ** Usage: %fossil test-shortest-path ?--no-merge? VERSION1 VERSION2
 
 
287 **
288 ** Report the shortest path between two check-ins. If the --no-merge flag
289 ** is used, follow only direct parent-child paths and omit merge links.
 
 
 
290 */
291 void shortest_path_test_cmd(void){
292 int iFrom;
293 int iTo;
294 PathNode *p;
@@ -299,33 +340,23 @@
299
300 db_find_and_open_repository(0,0);
301 directOnly = find_option("no-merge",0,0)!=0;
302 oneWay = find_option("one-way",0,0)!=0;
303 zBrCost = find_option("branch-cost",0,1);
 
304 if( g.argc!=4 ) usage("VERSION1 VERSION2");
305 iFrom = name_to_rid(g.argv[2]);
306 iTo = name_to_rid(g.argv[3]);
307 p = path_shortest(iFrom, iTo, directOnly, oneWay, 0, atoi(zBrCost));
 
308 if( p==0 ){
309 fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]);
310 }
311 for(n=1, p=path.pStart; p; p=p->u.pTo, n++){
312 char *z;
313 z = db_text(0,
314 "SELECT substr(uuid,1,12) || ' ' || datetime(mtime)"
315 " FROM blob, event"
316 " WHERE blob.rid=%d AND event.objid=%d AND event.type='ci'",
317 p->rid, p->rid);
318 fossil_print("%4d: %5d %s", n, p->rid, z);
319 fossil_free(z);
320 if( p->u.pTo ){
321 fossil_print(" is a %s of\n",
322 p->u.pTo->fromIsParent ? "parent" : "child");
323 }else{
324 fossil_print("\n");
325 }
326 }
327 }
328
329 /*
330 ** Find the closest common ancestor of two nodes. "Closest" means the
331 ** fewest number of arcs.
332
--- src/path.c
+++ src/path.c
@@ -52,10 +52,11 @@
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; }
@@ -68,10 +69,38 @@
69
70 /*
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){
@@ -99,10 +128,13 @@
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 /*
@@ -174,21 +206,24 @@
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 ){
@@ -197,10 +232,11 @@
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;
@@ -281,14 +317,19 @@
317 }
318
319 /*
320 ** COMMAND: test-shortest-path
321 **
322 ** Usage: %fossil test-shortest-path [OPTIONS] VERSION1 VERSION2
323 **
324 ** Report the shortest path between two check-ins. Options:
325 **
326 ** --branch-cost N Additional cost N for changing branches
327 ** --debug Show debugging output
328 ** --one-way One-way forwards in time, parent->child only
329 ** --no-merge Follow only direct parent-child paths and omit
330 ** merge links.
331 */
332 void shortest_path_test_cmd(void){
333 int iFrom;
334 int iTo;
335 PathNode *p;
@@ -299,33 +340,23 @@
340
341 db_find_and_open_repository(0,0);
342 directOnly = find_option("no-merge",0,0)!=0;
343 oneWay = find_option("one-way",0,0)!=0;
344 zBrCost = find_option("branch-cost",0,1);
345 if( find_option("debug",0,0)!=0 ) path_debug = 1;
346 if( g.argc!=4 ) usage("VERSION1 VERSION2");
347 iFrom = name_to_rid(g.argv[2]);
348 iTo = name_to_rid(g.argv[3]);
349 p = path_shortest(iFrom, iTo, directOnly, oneWay, 0,
350 zBrCost ? atoi(zBrCost) : 0);
351 if( p==0 ){
352 fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]);
353 }
354 for(n=1, p=path.pStart; p; p=p->u.pTo, n++){
355 fossil_print("%4d: %s\n", n, path_rid_desc(p->rid));
356 }
357 path_debug = 0;
 
 
 
 
 
 
 
 
 
 
 
 
358 }
359
360 /*
361 ** Find the closest common ancestor of two nodes. "Closest" means the
362 ** fewest number of arcs.
363

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button