Fossil SCM

fossil-scm / src / path.c
Source Blame History 737 lines
e5121b4… drh 1 /*
c19f34c… drh 2 ** Copyright (c) 2011 D. Richard Hipp
e5121b4… drh 3 **
e5121b4… drh 4 ** This program is free software; you can redistribute it and/or
e5121b4… drh 5 ** modify it under the terms of the Simplified BSD License (also
e5121b4… drh 6 ** known as the "2-Clause License" or "FreeBSD License".)
e5121b4… drh 7
e5121b4… drh 8 ** This program is distributed in the hope that it will be useful,
e5121b4… drh 9 ** but without any warranty; without even the implied warranty of
e5121b4… drh 10 ** merchantability or fitness for a particular purpose.
e5121b4… drh 11 **
e5121b4… drh 12 ** Author contact information:
e5121b4… drh 13 ** [email protected]
e5121b4… drh 14 **
e5121b4… drh 15 *******************************************************************************
e5121b4… drh 16 **
e5121b4… drh 17 ** This file contains code used to trace paths of through the
6ec2c2e… mistachkin 18 ** directed acyclic graph (DAG) of check-ins.
e5121b4… drh 19 */
e5121b4… drh 20 #include "config.h"
e5121b4… drh 21 #include "path.h"
e5121b4… drh 22 #include <assert.h>
4e23c2a… drh 23 #include <math.h>
e5121b4… drh 24
e5121b4… drh 25 #if INTERFACE
e5121b4… drh 26 /* Nodes for the paths through the DAG.
e5121b4… drh 27 */
e5121b4… drh 28 struct PathNode {
e5121b4… drh 29 int rid; /* ID for this node */
e5121b4… drh 30 u8 fromIsParent; /* True if pFrom is the parent of rid */
e5121b4… drh 31 u8 isPrim; /* True if primary side of common ancestor */
eec1114… drh 32 u8 isHidden; /* Abbreviate output in "fossil bisect ls" */
4e23c2a… drh 33 char *zBranch; /* Branch name for this node. Might be NULL */
4e23c2a… drh 34 double mtime; /* Date/time of this check-in */
e5121b4… drh 35 PathNode *pFrom; /* Node we came from */
e5121b4… drh 36 union {
4e23c2a… drh 37 double rCost; /* Cost of getting to this node from pStart */
e5121b4… drh 38 PathNode *pTo; /* Next on path from beginning to end */
e5121b4… drh 39 } u;
4e23c2a… drh 40 PathNode *pAll; /* List of all nodes */
e5121b4… drh 41 };
e5121b4… drh 42 #endif
e5121b4… drh 43
e5121b4… drh 44 /*
e5121b4… drh 45 ** Local variables for this module
e5121b4… drh 46 */
e5121b4… drh 47 static struct {
4e23c2a… drh 48 PQueue pending; /* Nodes pending review for inclusion in the graph */
e5121b4… drh 49 PathNode *pAll; /* All nodes */
e5121b4… drh 50 int nStep; /* Number of steps from first to last */
9e7262b… drh 51 int nNotHidden; /* Number of steps not counting hidden nodes */
4e23c2a… drh 52 int brCost; /* Extra cost for moving to a different branch */
4e23c2a… drh 53 int revCost; /* Extra cost for changing directions */
e5121b4… drh 54 PathNode *pStart; /* Earliest node */
e5121b4… drh 55 PathNode *pEnd; /* Most recent */
e5121b4… drh 56 } path;
4e23c2a… drh 57 static int path_debug = 0; /* Flag to enable debugging */
e5121b4… drh 58
e5121b4… drh 59 /*
e5121b4… drh 60 ** Return the first (last) element of the computed path.
e5121b4… drh 61 */
e5121b4… drh 62 PathNode *path_first(void){ return path.pStart; }
e5121b4… drh 63 PathNode *path_last(void){ return path.pEnd; }
e5121b4… drh 64
e5121b4… drh 65 /*
e5121b4… drh 66 ** Return the number of steps in the computed path.
e5121b4… drh 67 */
e5121b4… drh 68 int path_length(void){ return path.nStep; }
e5121b4… drh 69
e5121b4… drh 70 /*
9e7262b… drh 71 ** Return the number of non-hidden steps in the computed path.
9e7262b… drh 72 */
9e7262b… drh 73 int path_length_not_hidden(void){ return path.nNotHidden; }
9e7262b… drh 74
9e7262b… drh 75 /*
4e23c2a… drh 76 ** Used for debugging only.
4e23c2a… drh 77 **
4e23c2a… drh 78 ** Given a RID, return the ISO date/time string and branch for the
4e23c2a… drh 79 ** corresponding check-in. Memory is held locally and is overwritten
4e23c2a… drh 80 ** with each call.
4e23c2a… drh 81 */
4e23c2a… drh 82 char *path_rid_desc(int rid){
4e23c2a… drh 83 static Stmt q;
4e23c2a… drh 84 static char *zDesc = 0;
4e23c2a… drh 85 db_static_prepare(&q,
4e23c2a… drh 86 "SELECT concat(strftime('%%Y%%m%%d%%H%%M',event.mtime),'/',value)"
4e23c2a… drh 87 " FROM event, tagxref"
4e23c2a… drh 88 " WHERE event.objid=:rid"
4e23c2a… drh 89 " AND tagxref.rid=:rid"
4e23c2a… drh 90 " AND tagxref.tagid=%d"
4e23c2a… drh 91 " AND tagxref.tagtype>0",
4e23c2a… drh 92 TAG_BRANCH
4e23c2a… drh 93 );
4e23c2a… drh 94 fossil_free(zDesc);
4e23c2a… drh 95 db_bind_int(&q, ":rid", rid);
4e23c2a… drh 96 if( db_step(&q)==SQLITE_ROW ){
4e23c2a… drh 97 zDesc = fossil_strdup(db_column_text(&q,0));
4e23c2a… drh 98 }
4e23c2a… drh 99 db_reset(&q);
4e23c2a… drh 100 return zDesc ? zDesc : "???";
4e23c2a… drh 101 }
4e23c2a… drh 102
4e23c2a… drh 103 /*
4e23c2a… drh 104 ** Create a new node and insert it into the path.pending queue.
e5121b4… drh 105 */
e5121b4… drh 106 static PathNode *path_new_node(int rid, PathNode *pFrom, int isParent){
e5121b4… drh 107 PathNode *p;
e5121b4… drh 108
e5121b4… drh 109 p = fossil_malloc( sizeof(*p) );
e5121b4… drh 110 memset(p, 0, sizeof(*p));
4e23c2a… drh 111 p->pAll = path.pAll;
4e23c2a… drh 112 path.pAll = p;
e5121b4… drh 113 p->rid = rid;
e5121b4… drh 114 p->fromIsParent = isParent;
e5121b4… drh 115 p->pFrom = pFrom;
4e23c2a… drh 116 p->u.rCost = pFrom ? pFrom->u.rCost : 0.0;
4e23c2a… drh 117 if( path.brCost ){
4e23c2a… drh 118 p->zBranch = branch_of_rid(rid);
4e23c2a… drh 119 p->mtime = mtime_of_rid(rid, 0.0);
4e23c2a… drh 120 if( pFrom ){
4e23c2a… drh 121 p->u.rCost += fabs(pFrom->mtime - p->mtime);
4e23c2a… drh 122 if( fossil_strcmp(p->zBranch, pFrom->zBranch)!=0 ){
4e23c2a… drh 123 p->u.rCost += path.brCost;
4e23c2a… drh 124 }
4e23c2a… drh 125 }
4e23c2a… drh 126 }else{
4e23c2a… drh 127 /* When brCost==0, we try to minimize the number of nodes
4e23c2a… drh 128 ** along the path. The cost is just the number of nodes back
4e23c2a… drh 129 ** to the start. We do not need to know the branch name nor
4e23c2a… drh 130 ** the mtime */
4e23c2a… drh 131 p->u.rCost += 1.0;
4e23c2a… drh 132 }
4e23c2a… drh 133 if( path_debug ){
4e23c2a… drh 134 fossil_print("PUSH %-50s cost = %g\n", path_rid_desc(p->rid), p->u.rCost);
4e23c2a… drh 135 }
4e23c2a… drh 136 pqueuex_insert_ptr(&path.pending, (void*)p, p->u.rCost);
e5121b4… drh 137 return p;
e5121b4… drh 138 }
e5121b4… drh 139
e5121b4… drh 140 /*
e5121b4… drh 141 ** Reset memory used by the shortest path algorithm.
e5121b4… drh 142 */
e5121b4… drh 143 void path_reset(void){
e5121b4… drh 144 PathNode *p;
e5121b4… drh 145 while( path.pAll ){
e5121b4… drh 146 p = path.pAll;
e5121b4… drh 147 path.pAll = p->pAll;
4e23c2a… drh 148 fossil_free(p->zBranch);
e5121b4… drh 149 fossil_free(p);
e5121b4… drh 150 }
4e23c2a… drh 151 pqueuex_clear(&path.pending);
336e135… drh 152 memset(&path, 0, sizeof(path));
e5121b4… drh 153 }
e5121b4… drh 154
e5121b4… drh 155 /*
e5121b4… drh 156 ** Construct the path from path.pStart to path.pEnd in the u.pTo fields.
e5121b4… drh 157 */
6306914… drh 158 static void path_reverse_path(void){
e5121b4… drh 159 PathNode *p;
6306914… drh 160 assert( path.pEnd!=0 );
e5121b4… drh 161 for(p=path.pEnd; p && p->pFrom; p = p->pFrom){
e5121b4… drh 162 p->pFrom->u.pTo = p;
e5121b4… drh 163 }
e5121b4… drh 164 path.pEnd->u.pTo = 0;
e5121b4… drh 165 assert( p==path.pStart );
e5121b4… drh 166 }
e5121b4… drh 167
e5121b4… drh 168 /*
e5121b4… drh 169 ** Compute the shortest path from iFrom to iTo
e5121b4… drh 170 **
e5121b4… drh 171 ** If directOnly is true, then use only the "primary" links from parent to
e5121b4… drh 172 ** child. In other words, ignore merges.
e5121b4… drh 173 **
20d02ab… jan.nijtmans 174 ** Return a pointer to the beginning of the path (the iFrom node).
e5121b4… drh 175 ** Elements of the path can be traversed by following the PathNode.u.pTo
e5121b4… drh 176 ** pointer chain.
e5121b4… drh 177 **
e5121b4… drh 178 ** Return NULL if no path is found.
e5121b4… drh 179 */
0b93b0f… drh 180 PathNode *path_shortest(
0b93b0f… drh 181 int iFrom, /* Path starts here */
0b93b0f… drh 182 int iTo, /* Path ends here */
0b93b0f… drh 183 int directOnly, /* No merge links if true */
9e7262b… drh 184 int oneWayOnly, /* Parent->child only if true */
4e23c2a… drh 185 Bag *pHidden, /* Hidden nodes */
4e23c2a… drh 186 int branchCost /* Add extra cost to changing branches */
0b93b0f… drh 187 ){
66951fa… drh 188 Stmt s;
4e23c2a… drh 189 Bag seen;
66951fa… drh 190 PathNode *p;
66951fa… drh 191
66951fa… drh 192 path_reset();
4e23c2a… drh 193 path.brCost = branchCost;
66951fa… drh 194 path.pStart = path_new_node(iFrom, 0, 0);
66951fa… drh 195 if( iTo==iFrom ){
66951fa… drh 196 path.pEnd = path.pStart;
da9aa4a… drh 197 path.pEnd->u.pTo = 0;
0b93b0f… drh 198 return path.pStart;
0b93b0f… drh 199 }
f035988… drh 200 if( oneWayOnly && directOnly ){
20d02ab… jan.nijtmans 201 db_prepare(&s,
f035988… drh 202 "SELECT cid, 1 FROM plink WHERE pid=:pid AND isprim"
f035988… drh 203 );
f035988… drh 204 }else if( oneWayOnly ){
20d02ab… jan.nijtmans 205 db_prepare(&s,
0b93b0f… drh 206 "SELECT cid, 1 FROM plink WHERE pid=:pid "
0b93b0f… drh 207 );
0b93b0f… drh 208 }else if( directOnly ){
20d02ab… jan.nijtmans 209 db_prepare(&s,
20d02ab… jan.nijtmans 210 "SELECT cid, 1 FROM plink WHERE pid=:pid AND isprim "
20d02ab… jan.nijtmans 211 "UNION ALL "
4e23c2a… drh 212 "SELECT pid, 0 FROM plink WHERE :back AND cid=:pid AND isprim"
20d02ab… jan.nijtmans 213 );
20d02ab… jan.nijtmans 214 }else{
20d02ab… jan.nijtmans 215 db_prepare(&s,
20d02ab… jan.nijtmans 216 "SELECT cid, 1 FROM plink WHERE pid=:pid "
20d02ab… jan.nijtmans 217 "UNION ALL "
4e23c2a… drh 218 "SELECT pid, 0 FROM plink WHERE :back AND cid=:pid"
20d02ab… jan.nijtmans 219 );
20d02ab… jan.nijtmans 220 }
4e23c2a… drh 221 bag_init(&seen);
4e23c2a… drh 222 while( (p = pqueuex_extract_ptr(&path.pending))!=0 ){
4e23c2a… drh 223 if( path_debug ){
4e23c2a… drh 224 printf("PULL %s %g\n", path_rid_desc(p->rid), p->u.rCost);
4e23c2a… drh 225 }
4e23c2a… drh 226 if( p->rid==iTo ){
4e23c2a… drh 227 db_finalize(&s);
4e23c2a… drh 228 path.pEnd = p;
4e23c2a… drh 229 path_reverse_path();
4e23c2a… drh 230 for(p=path.pStart->u.pTo; p; p=p->u.pTo ){
4e23c2a… drh 231 if( !p->isHidden ) path.nNotHidden++;
4e23c2a… drh 232 }
4e23c2a… drh 233 return path.pStart;
4e23c2a… drh 234 }
4e23c2a… drh 235 if( bag_find(&seen, p->rid) ) continue;
4e23c2a… drh 236 bag_insert(&seen, p->rid);
4e23c2a… drh 237 db_bind_int(&s, ":pid", p->rid);
4e23c2a… drh 238 if( !oneWayOnly ) db_bind_int(&s, ":back", !p->fromIsParent);
4e23c2a… drh 239 while( db_step(&s)==SQLITE_ROW ){
4e23c2a… drh 240 int cid = db_column_int(&s, 0);
4e23c2a… drh 241 int isParent = db_column_int(&s, 1);
4e23c2a… drh 242 PathNode *pNew;
4e23c2a… drh 243 if( bag_find(&seen, cid) ) continue;
4e23c2a… drh 244 pNew = path_new_node(cid, p, isParent);
4e23c2a… drh 245 if( pHidden && bag_find(pHidden,cid) ) pNew->isHidden = 1;
4e23c2a… drh 246 }
4e23c2a… drh 247 db_reset(&s);
e5121b4… drh 248 }
e5121b4… drh 249 db_finalize(&s);
e5121b4… drh 250 path_reset();
e5121b4… drh 251 return 0;
e5121b4… drh 252 }
e5121b4… drh 253
e5121b4… drh 254 /*
e5121b4… drh 255 ** Find the mid-point of the path. If the path contains fewer than
e5121b4… drh 256 ** 2 steps, return 0.
e5121b4… drh 257 */
e5121b4… drh 258 PathNode *path_midpoint(void){
e5121b4… drh 259 PathNode *p;
e5121b4… drh 260 int i;
9e7262b… drh 261 if( path.nNotHidden<2 ) return 0;
9e7262b… drh 262 for(p=path.pEnd, i=0; p && (p->isHidden || i<path.nNotHidden/2); p=p->pFrom){
9e7262b… drh 263 if( !p->isHidden ) i++;
9e7262b… drh 264 }
9e7262b… drh 265 return p;
42f61b6… drh 266 }
42f61b6… drh 267
42f61b6… drh 268 /*
42f61b6… drh 269 ** Find the next most recent node on a path.
42f61b6… drh 270 */
42f61b6… drh 271 PathNode *path_next(void){
42f61b6… drh 272 PathNode *p;
42f61b6… drh 273 p = path.pStart;
42f61b6… drh 274 if( p ) p = p->u.pTo;
42f61b6… drh 275 return p;
42f61b6… drh 276 }
42f61b6… drh 277
42f61b6… drh 278 /*
4e23c2a… drh 279 ** Return the branch for a path node.
4e23c2a… drh 280 **
4e23c2a… drh 281 ** Storage space is managed by the path subsystem. The returned value
4e23c2a… drh 282 ** is valid until the path is reset.
4e23c2a… drh 283 */
4e23c2a… drh 284 const char *path_branch(PathNode *p){
4e23c2a… drh 285 if( p==0 ) return 0;
4e23c2a… drh 286 if( p->zBranch==0 ) p->zBranch = branch_of_rid(p->rid);
4e23c2a… drh 287 return p->zBranch;
4e23c2a… drh 288 }
4e23c2a… drh 289
4e23c2a… drh 290 /*
b45dd1c… drh 291 ** Return an estimate of the number of comparisons remaining in order
b45dd1c… drh 292 ** to bisect path. This is based on the log2() of path.nStep.
b45dd1c… drh 293 */
b45dd1c… drh 294 int path_search_depth(void){
b45dd1c… drh 295 int i, j;
9e7262b… drh 296 for(i=0, j=1; j<path.nNotHidden; i++, j+=j){}
b45dd1c… drh 297 return i;
95cc4b9… drh 298 }
95cc4b9… drh 299
95cc4b9… drh 300 /*
95cc4b9… drh 301 ** Compute the shortest path between two check-ins and then transfer
95cc4b9… drh 302 ** that path into the "ancestor" table. This is a utility used by
95cc4b9… drh 303 ** both /annotate and /finfo. See also: compute_direct_ancestors().
95cc4b9… drh 304 */
95cc4b9… drh 305 void path_shortest_stored_in_ancestor_table(
95cc4b9… drh 306 int origid, /* RID for check-in at start of the path */
95cc4b9… drh 307 int cid /* RID for check-in at the end of the path */
95cc4b9… drh 308 ){
95cc4b9… drh 309 PathNode *pPath;
95cc4b9… drh 310 int gen = 0;
5eba557… drh 311 Stmt ins;
4e23c2a… drh 312 pPath = path_shortest(cid, origid, 1, 0, 0, 0);
95cc4b9… drh 313 db_multi_exec(
95cc4b9… drh 314 "CREATE TEMP TABLE IF NOT EXISTS ancestor("
95cc4b9… drh 315 " rid INT UNIQUE,"
95cc4b9… drh 316 " generation INTEGER PRIMARY KEY"
95cc4b9… drh 317 ");"
95cc4b9… drh 318 "DELETE FROM ancestor;"
95cc4b9… drh 319 );
5eba557… drh 320 db_prepare(&ins, "INSERT INTO ancestor(rid, generation) VALUES(:rid,:gen)");
95cc4b9… drh 321 while( pPath ){
5eba557… drh 322 db_bind_int(&ins, ":rid", pPath->rid);
5eba557… drh 323 db_bind_int(&ins, ":gen", ++gen);
5eba557… drh 324 db_step(&ins);
5eba557… drh 325 db_reset(&ins);
95cc4b9… drh 326 pPath = pPath->u.pTo;
95cc4b9… drh 327 }
5eba557… drh 328 db_finalize(&ins);
95cc4b9… drh 329 path_reset();
26eef7f… rberteig 330 }
26eef7f… rberteig 331
26eef7f… rberteig 332 /*
26eef7f… rberteig 333 ** COMMAND: test-shortest-path
26eef7f… rberteig 334 **
4e23c2a… drh 335 ** Usage: %fossil test-shortest-path [OPTIONS] VERSION1 VERSION2
4e23c2a… drh 336 **
4e23c2a… drh 337 ** Report the shortest path between two check-ins. Options:
e5121b4… drh 338 **
4e23c2a… drh 339 ** --branch-cost N Additional cost N for changing branches
4e23c2a… drh 340 ** --debug Show debugging output
4e23c2a… drh 341 ** --one-way One-way forwards in time, parent->child only
4e23c2a… drh 342 ** --no-merge Follow only direct parent-child paths and omit
4e23c2a… drh 343 ** merge links.
e5121b4… drh 344 */
e5121b4… drh 345 void shortest_path_test_cmd(void){
e5121b4… drh 346 int iFrom;
e5121b4… drh 347 int iTo;
e5121b4… drh 348 PathNode *p;
e5121b4… drh 349 int n;
e5121b4… drh 350 int directOnly;
0b93b0f… drh 351 int oneWay;
4e23c2a… drh 352 const char *zBrCost;
e5121b4… drh 353
e5121b4… drh 354 db_find_and_open_repository(0,0);
e5121b4… drh 355 directOnly = find_option("no-merge",0,0)!=0;
0b93b0f… drh 356 oneWay = find_option("one-way",0,0)!=0;
4e23c2a… drh 357 zBrCost = find_option("branch-cost",0,1);
4e23c2a… drh 358 if( find_option("debug",0,0)!=0 ) path_debug = 1;
e5121b4… drh 359 if( g.argc!=4 ) usage("VERSION1 VERSION2");
e5121b4… drh 360 iFrom = name_to_rid(g.argv[2]);
e5121b4… drh 361 iTo = name_to_rid(g.argv[3]);
4e23c2a… drh 362 p = path_shortest(iFrom, iTo, directOnly, oneWay, 0,
4e23c2a… drh 363 zBrCost ? atoi(zBrCost) : 0);
e5121b4… drh 364 if( p==0 ){
e5121b4… drh 365 fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]);
e5121b4… drh 366 }
e5121b4… drh 367 for(n=1, p=path.pStart; p; p=p->u.pTo, n++){
4e23c2a… drh 368 fossil_print("%4d: %s\n", n, path_rid_desc(p->rid));
4e23c2a… drh 369 }
4e23c2a… drh 370 path_debug = 0;
e5121b4… drh 371 }
e5121b4… drh 372
e5121b4… drh 373 /*
e5121b4… drh 374 ** Find the closest common ancestor of two nodes. "Closest" means the
e5121b4… drh 375 ** fewest number of arcs.
e5121b4… drh 376 */
e5121b4… drh 377 int path_common_ancestor(int iMe, int iYou){
e5121b4… drh 378 Stmt s;
4e23c2a… drh 379 PathNode *pThis;
e5121b4… drh 380 PathNode *p;
e5121b4… drh 381 Bag me, you;
e5121b4… drh 382
e5121b4… drh 383 if( iMe==iYou ) return iMe;
e5121b4… drh 384 if( iMe==0 || iYou==0 ) return 0;
e5121b4… drh 385 path_reset();
e5121b4… drh 386 path.pStart = path_new_node(iMe, 0, 0);
e5121b4… drh 387 path.pStart->isPrim = 1;
e5121b4… drh 388 path.pEnd = path_new_node(iYou, 0, 0);
e5121b4… drh 389 db_prepare(&s, "SELECT pid FROM plink WHERE cid=:cid");
e5121b4… drh 390 bag_init(&me);
e5121b4… drh 391 bag_insert(&me, iMe);
e5121b4… drh 392 bag_init(&you);
e5121b4… drh 393 bag_insert(&you, iYou);
4e23c2a… drh 394 while( (pThis = pqueuex_extract_ptr(&path.pending))!=0 ){
4e23c2a… drh 395 db_bind_int(&s, ":cid", pThis->rid);
4e23c2a… drh 396 while( db_step(&s)==SQLITE_ROW ){
4e23c2a… drh 397 int pid = db_column_int(&s, 0);
4e23c2a… drh 398 if( bag_find(pThis->isPrim ? &you : &me, pid) ){
4e23c2a… drh 399 /* pid is the common ancestor */
4e23c2a… drh 400 PathNode *pNext;
4e23c2a… drh 401 for(p=path.pAll; p && p->rid!=pid; p=p->pAll){}
4e23c2a… drh 402 assert( p!=0 );
4e23c2a… drh 403 pNext = p;
4e23c2a… drh 404 while( pNext ){
4e23c2a… drh 405 pNext = p->pFrom;
4e23c2a… drh 406 p->pFrom = pThis;
4e23c2a… drh 407 pThis = p;
4e23c2a… drh 408 p = pNext;
4e23c2a… drh 409 }
4e23c2a… drh 410 if( pThis==path.pStart ) path.pStart = path.pEnd;
4e23c2a… drh 411 path.pEnd = pThis;
4e23c2a… drh 412 path_reverse_path();
4e23c2a… drh 413 db_finalize(&s);
4e23c2a… drh 414 return pid;
4e23c2a… drh 415 }else if( bag_find(pThis->isPrim ? &me : &you, pid) ){
4e23c2a… drh 416 /* pid is just an alternative path to a node we've already visited */
4e23c2a… drh 417 continue;
4e23c2a… drh 418 }
4e23c2a… drh 419 p = path_new_node(pid, pThis, 0);
4e23c2a… drh 420 p->isPrim = pThis->isPrim;
4e23c2a… drh 421 bag_insert(pThis->isPrim ? &me : &you, pid);
4e23c2a… drh 422 }
4e23c2a… drh 423 db_reset(&s);
e5121b4… drh 424 }
e5121b4… drh 425 db_finalize(&s);
e5121b4… drh 426 path_reset();
e5121b4… drh 427 return 0;
e5121b4… drh 428 }
e5121b4… drh 429
e5121b4… drh 430 /*
26eef7f… rberteig 431 ** COMMAND: test-ancestor-path
e5121b4… drh 432 **
e5121b4… drh 433 ** Usage: %fossil test-ancestor-path VERSION1 VERSION2
e5121b4… drh 434 **
e5121b4… drh 435 ** Report the path from VERSION1 to VERSION2 through their most recent
e5121b4… drh 436 ** common ancestor.
e5121b4… drh 437 */
e5121b4… drh 438 void ancestor_path_test_cmd(void){
e5121b4… drh 439 int iFrom;
e5121b4… drh 440 int iTo;
e5121b4… drh 441 int iPivot;
e5121b4… drh 442 PathNode *p;
e5121b4… drh 443 int n;
e5121b4… drh 444
e5121b4… drh 445 db_find_and_open_repository(0,0);
e5121b4… drh 446 if( g.argc!=4 ) usage("VERSION1 VERSION2");
e5121b4… drh 447 iFrom = name_to_rid(g.argv[2]);
e5121b4… drh 448 iTo = name_to_rid(g.argv[3]);
e5121b4… drh 449 iPivot = path_common_ancestor(iFrom, iTo);
e5121b4… drh 450 for(n=1, p=path.pStart; p; p=p->u.pTo, n++){
e5121b4… drh 451 char *z;
e5121b4… drh 452 z = db_text(0,
e5121b4… drh 453 "SELECT substr(uuid,1,12) || ' ' || datetime(mtime)"
e5121b4… drh 454 " FROM blob, event"
e5121b4… drh 455 " WHERE blob.rid=%d AND event.objid=%d AND event.type='ci'",
e5121b4… drh 456 p->rid, p->rid);
21acce3… drh 457 fossil_print("%4d: %5d %s", n, p->rid, z);
e5121b4… drh 458 fossil_free(z);
d8ec765… drh 459 if( p->rid==iFrom ) fossil_print(" VERSION1");
d8ec765… drh 460 if( p->rid==iTo ) fossil_print(" VERSION2");
d8ec765… drh 461 if( p->rid==iPivot ) fossil_print(" PIVOT");
d8ec765… drh 462 fossil_print("\n");
e5121b4… drh 463 }
e5121b4… drh 464 }
e5121b4… drh 465
e5121b4… drh 466
e5121b4… drh 467 /*
e5121b4… drh 468 ** A record of a file rename operation.
e5121b4… drh 469 */
e5121b4… drh 470 typedef struct NameChange NameChange;
e5121b4… drh 471 struct NameChange {
e5121b4… drh 472 int origName; /* Original name of file */
e5121b4… drh 473 int curName; /* Current name of the file */
e5121b4… drh 474 int newName; /* Name of file in next version */
e5121b4… drh 475 NameChange *pNext; /* List of all name changes */
e5121b4… drh 476 };
e5121b4… drh 477
e5121b4… drh 478 /*
c49030f… drh 479 ** Compute all file name changes that occur going from check-in iFrom
c49030f… drh 480 ** to check-in iTo.
e5121b4… drh 481 **
e5121b4… drh 482 ** The number of name changes is written into *pnChng. For each name
20d02ab… jan.nijtmans 483 ** change, two integers are allocated for *piChng. The first is the
21acce3… drh 484 ** filename.fnid for the original name as seen in check-in iFrom and
21acce3… drh 485 ** the second is for new name as it is used in check-in iTo.
21acce3… drh 486 **
e5121b4… drh 487 ** Space to hold *piChng is obtained from fossil_malloc() and should
e5121b4… drh 488 ** be released by the caller.
e5121b4… drh 489 **
21acce3… drh 490 ** This routine really has nothing to do with path. It is located
e5121b4… drh 491 ** in this path.c module in order to leverage some of the path
e5121b4… drh 492 ** infrastructure.
e5121b4… drh 493 */
e5121b4… drh 494 void find_filename_changes(
21acce3… drh 495 int iFrom, /* Ancestor check-in */
21acce3… drh 496 int iTo, /* Recent check-in */
b92e460… wyoung 497 int revOK, /* OK to move backwards (child->parent) if true */
21acce3… drh 498 int *pnChng, /* Number of name changes along the path */
21acce3… drh 499 int **aiChng, /* Name changes */
21acce3… drh 500 const char *zDebug /* Generate trace output if no NULL */
e5121b4… drh 501 ){
21acce3… drh 502 PathNode *p; /* For looping over path from iFrom to iTo */
e5121b4… drh 503 NameChange *pAll = 0; /* List of all name changes seen so far */
e5121b4… drh 504 NameChange *pChng; /* For looping through the name change list */
e5121b4… drh 505 int nChng = 0; /* Number of files whose names have changed */
e5121b4… drh 506 int *aChng; /* Two integers per name change */
e5121b4… drh 507 int i; /* Loop counter */
e5121b4… drh 508 Stmt q1; /* Query of name changes */
e5121b4… drh 509
e5121b4… drh 510 *pnChng = 0;
e5121b4… drh 511 *aiChng = 0;
25b2a80… stephan 512 if(0==iFrom){
25b2a80… stephan 513 fossil_fatal("Invalid 'from' RID: 0");
25b2a80… stephan 514 }else if(0==iTo){
25b2a80… stephan 515 fossil_fatal("Invalid 'to' RID: 0");
25b2a80… stephan 516 }
66951fa… drh 517 if( iFrom==iTo ) return;
e5121b4… drh 518 path_reset();
4e23c2a… drh 519 p = path_shortest(iFrom, iTo, 1, revOK==0, 0, 0);
e5121b4… drh 520 if( p==0 ) return;
e5121b4… drh 521 path_reverse_path();
e5121b4… drh 522 db_prepare(&q1,
0b93b0f… drh 523 "SELECT pfnid, fnid FROM mlink"
0b93b0f… drh 524 " WHERE mid=:mid AND (pfnid>0 OR fid==0)"
0b93b0f… drh 525 " ORDER BY pfnid"
e5121b4… drh 526 );
e5121b4… drh 527 for(p=path.pStart; p; p=p->u.pTo){
e5121b4… drh 528 int fnid, pfnid;
e5121b4… drh 529 if( !p->fromIsParent && (p->u.pTo==0 || p->u.pTo->fromIsParent) ){
e5121b4… drh 530 /* Skip nodes where the parent is not on the path */
e5121b4… drh 531 continue;
e5121b4… drh 532 }
e5121b4… drh 533 db_bind_int(&q1, ":mid", p->rid);
40086b7… drh 534 if( zDebug ){
40086b7… drh 535 fossil_print("%s check-in %.16z %z rid %d\n",
40086b7… drh 536 zDebug,
40086b7… drh 537 db_text(0, "SELECT uuid FROM blob WHERE rid=%d", p->rid),
40086b7… drh 538 db_text(0, "SELECT date(mtime) FROM event WHERE objid=%d", p->rid),
40086b7… drh 539 p->rid
40086b7… drh 540 );
40086b7… drh 541 }
e5121b4… drh 542 while( db_step(&q1)==SQLITE_ROW ){
0b93b0f… drh 543 fnid = db_column_int(&q1, 1);
0b93b0f… drh 544 pfnid = db_column_int(&q1, 0);
0b93b0f… drh 545 if( pfnid==0 ){
0b93b0f… drh 546 pfnid = fnid;
0b93b0f… drh 547 fnid = 0;
0b93b0f… drh 548 }
0b93b0f… drh 549 if( !p->fromIsParent ){
0b93b0f… drh 550 int t = fnid;
0b93b0f… drh 551 fnid = pfnid;
0b93b0f… drh 552 pfnid = t;
21acce3… drh 553 }
21acce3… drh 554 if( zDebug ){
40086b7… drh 555 fossil_print("%s %d[%z] -> %d[%z]\n",
40086b7… drh 556 zDebug,
21acce3… drh 557 pfnid,
21acce3… drh 558 db_text(0, "SELECT name FROM filename WHERE fnid=%d", pfnid),
21acce3… drh 559 fnid,
21acce3… drh 560 db_text(0, "SELECT name FROM filename WHERE fnid=%d", fnid));
e5121b4… drh 561 }
e5121b4… drh 562 for(pChng=pAll; pChng; pChng=pChng->pNext){
e5121b4… drh 563 if( pChng->curName==pfnid ){
e5121b4… drh 564 pChng->newName = fnid;
e5121b4… drh 565 break;
e5121b4… drh 566 }
e5121b4… drh 567 }
0b93b0f… drh 568 if( pChng==0 && fnid>0 ){
e5121b4… drh 569 pChng = fossil_malloc( sizeof(*pChng) );
e5121b4… drh 570 pChng->pNext = pAll;
e5121b4… drh 571 pAll = pChng;
e5121b4… drh 572 pChng->origName = pfnid;
e5121b4… drh 573 pChng->curName = pfnid;
e5121b4… drh 574 pChng->newName = fnid;
e5121b4… drh 575 nChng++;
e5121b4… drh 576 }
e5121b4… drh 577 }
0b93b0f… drh 578 for(pChng=pAll; pChng; pChng=pChng->pNext){
0b93b0f… drh 579 pChng->curName = pChng->newName;
0b93b0f… drh 580 }
e5121b4… drh 581 db_reset(&q1);
e5121b4… drh 582 }
e5121b4… drh 583 db_finalize(&q1);
e5121b4… drh 584 if( nChng ){
e5121b4… drh 585 aChng = *aiChng = fossil_malloc( nChng*2*sizeof(int) );
0b93b0f… drh 586 for(pChng=pAll, i=0; pChng; pChng=pChng->pNext){
0b93b0f… drh 587 if( pChng->newName==0 ) continue;
0b93b0f… drh 588 if( pChng->origName==0 ) continue;
e5121b4… drh 589 aChng[i] = pChng->origName;
e5121b4… drh 590 aChng[i+1] = pChng->newName;
21acce3… drh 591 if( zDebug ){
21acce3… drh 592 fossil_print("%s summary %d[%z] -> %d[%z]\n",
21acce3… drh 593 zDebug,
21acce3… drh 594 aChng[i],
21acce3… drh 595 db_text(0, "SELECT name FROM filename WHERE fnid=%d", aChng[i]),
21acce3… drh 596 aChng[i+1],
21acce3… drh 597 db_text(0, "SELECT name FROM filename WHERE fnid=%d", aChng[i+1]));
21acce3… drh 598 }
0b93b0f… drh 599 i += 2;
e5121b4… drh 600 }
0b93b0f… drh 601 *pnChng = i/2;
e5121b4… drh 602 while( pAll ){
e5121b4… drh 603 pChng = pAll;
e5121b4… drh 604 pAll = pAll->pNext;
e5121b4… drh 605 fossil_free(pChng);
e5121b4… drh 606 }
e5121b4… drh 607 }
337617b… drh 608 path_reset();
e5121b4… drh 609 }
e5121b4… drh 610
e5121b4… drh 611 /*
e5121b4… drh 612 ** COMMAND: test-name-changes
e5121b4… drh 613 **
0b93b0f… drh 614 ** Usage: %fossil test-name-changes [--debug] VERSION1 VERSION2
e5121b4… drh 615 **
e5121b4… drh 616 ** Show all filename changes that occur going from VERSION1 to VERSION2
e5121b4… drh 617 */
e5121b4… drh 618 void test_name_change(void){
e5121b4… drh 619 int iFrom;
e5121b4… drh 620 int iTo;
e5121b4… drh 621 int *aChng;
e5121b4… drh 622 int nChng;
e5121b4… drh 623 int i;
0b93b0f… drh 624 const char *zDebug = 0;
b92e460… wyoung 625 int revOK = 0;
e5121b4… drh 626
e5121b4… drh 627 db_find_and_open_repository(0,0);
0b93b0f… drh 628 zDebug = find_option("debug",0,0)!=0 ? "debug" : 0;
b92e460… wyoung 629 revOK = find_option("bidirectional",0,0)!=0;
21acce3… drh 630 if( g.argc<4 ) usage("VERSION1 VERSION2");
21acce3… drh 631 while( g.argc>=4 ){
21acce3… drh 632 iFrom = name_to_rid(g.argv[2]);
21acce3… drh 633 iTo = name_to_rid(g.argv[3]);
b92e460… wyoung 634 find_filename_changes(iFrom, iTo, revOK, &nChng, &aChng, zDebug);
21acce3… drh 635 fossil_print("------ Changes for (%d) %s -> (%d) %s\n",
21acce3… drh 636 iFrom, g.argv[2], iTo, g.argv[3]);
21acce3… drh 637 for(i=0; i<nChng; i++){
21acce3… drh 638 char *zFrom, *zTo;
21acce3… drh 639
21acce3… drh 640 zFrom = db_text(0, "SELECT name FROM filename WHERE fnid=%d", aChng[i*2]);
21acce3… drh 641 zTo = db_text(0, "SELECT name FROM filename WHERE fnid=%d", aChng[i*2+1]);
21acce3… drh 642 fossil_print("[%s] -> [%s]\n", zFrom, zTo);
21acce3… drh 643 fossil_free(zFrom);
21acce3… drh 644 fossil_free(zTo);
21acce3… drh 645 }
21acce3… drh 646 fossil_free(aChng);
21acce3… drh 647 g.argv += 2;
21acce3… drh 648 g.argc -= 2;
21acce3… drh 649 }
09f82ac… drh 650 }
09f82ac… drh 651
09f82ac… drh 652 /* Query to extract all rename operations */
20d02ab… jan.nijtmans 653 static const char zRenameQuery[] =
b6aa2a2… drh 654 @ CREATE TEMP TABLE renames AS
98fe1d8… drh 655 @ SELECT
b6aa2a2… drh 656 @ datetime(event.mtime) AS date,
98fe1d8… drh 657 @ F.name AS old_name,
98fe1d8… drh 658 @ T.name AS new_name,
b6aa2a2… drh 659 @ blob.uuid AS checkin
98fe1d8… drh 660 @ FROM mlink, filename F, filename T, event, blob
98fe1d8… drh 661 @ WHERE coalesce(mlink.pfnid,0)!=0 AND mlink.pfnid!=mlink.fnid
98fe1d8… drh 662 @ AND F.fnid=mlink.pfnid
98fe1d8… drh 663 @ AND T.fnid=mlink.fnid
98fe1d8… drh 664 @ AND event.objid=mlink.mid
98fe1d8… drh 665 @ AND event.type='ci'
b6aa2a2… drh 666 @ AND blob.rid=mlink.mid;
98fe1d8… drh 667 ;
98fe1d8… drh 668
98fe1d8… drh 669 /* Query to extract distinct rename operations */
98fe1d8… drh 670 static const char zDistinctRenameQuery[] =
b6aa2a2… drh 671 @ CREATE TEMP TABLE renames AS
09f82ac… drh 672 @ SELECT
b6aa2a2… drh 673 @ min(datetime(event.mtime)) AS date,
09f82ac… drh 674 @ F.name AS old_name,
09f82ac… drh 675 @ T.name AS new_name,
b6aa2a2… drh 676 @ blob.uuid AS checkin
09f82ac… drh 677 @ FROM mlink, filename F, filename T, event, blob
09f82ac… drh 678 @ WHERE coalesce(mlink.pfnid,0)!=0 AND mlink.pfnid!=mlink.fnid
09f82ac… drh 679 @ AND F.fnid=mlink.pfnid
09f82ac… drh 680 @ AND T.fnid=mlink.fnid
09f82ac… drh 681 @ AND event.objid=mlink.mid
09f82ac… drh 682 @ AND event.type='ci'
09f82ac… drh 683 @ AND blob.rid=mlink.mid
b6aa2a2… drh 684 @ GROUP BY 2, 3;
09f82ac… drh 685 ;
20d02ab… jan.nijtmans 686
09f82ac… drh 687 /*
09f82ac… drh 688 ** WEBPAGE: test-rename-list
09f82ac… drh 689 **
09f82ac… drh 690 ** Print a list of all file rename operations throughout history.
2f78b2c… danield 691 ** This page is intended for testing purposes only and may change
09f82ac… drh 692 ** or be discontinued without notice.
09f82ac… drh 693 */
09f82ac… drh 694 void test_rename_list_page(void){
09f82ac… drh 695 Stmt q;
b6aa2a2… drh 696 int nRename;
b6aa2a2… drh 697 int nCheckin;
09f82ac… drh 698
09f82ac… drh 699 login_check_credentials();
653dd40… drh 700 if( !g.perm.Read ){ login_needed(g.anon.Read); return; }
112c713… drh 701 style_set_current_feature("test");
98fe1d8… drh 702 if( P("all")!=0 ){
c0ed950… drh 703 style_header("List Of All Filename Changes");
b6aa2a2… drh 704 db_multi_exec("%s", zRenameQuery/*safe-for-%s*/);
98fe1d8… drh 705 style_submenu_element("Distinct", "%R/test-rename-list");
98fe1d8… drh 706 }else{
c0ed950… drh 707 style_header("List Of Distinct Filename Changes");
b6aa2a2… drh 708 db_multi_exec("%s", zDistinctRenameQuery/*safe-for-%s*/);
98fe1d8… drh 709 style_submenu_element("All", "%R/test-rename-list?all");
98fe1d8… drh 710 }
b6aa2a2… drh 711 nRename = db_int(0, "SELECT count(*) FROM renames;");
b6aa2a2… drh 712 nCheckin = db_int(0, "SELECT count(DISTINCT checkin) FROM renames;");
b6aa2a2… drh 713 db_prepare(&q, "SELECT date, old_name, new_name, checkin FROM renames"
b6aa2a2… drh 714 " ORDER BY date DESC, old_name ASC");
c027368… drh 715 @ <h1>%d(nRename) filename changes in %d(nCheckin) check-ins</h1>
80ec9d5… drh 716 @ <table class='sortable' data-column-types='tttt' data-init-sort='1'\
80ec9d5… drh 717 @ border="1" cellpadding="2" cellspacing="0">
80ec9d5… drh 718 @ <thead><tr><th>Date &amp; Time</th>
09f82ac… drh 719 @ <th>Old Name</th>
09f82ac… drh 720 @ <th>New Name</th>
80ec9d5… drh 721 @ <th>Check-in</th></tr></thead><tbody>
09f82ac… drh 722 while( db_step(&q)==SQLITE_ROW ){
09f82ac… drh 723 const char *zDate = db_column_text(&q, 0);
09f82ac… drh 724 const char *zOld = db_column_text(&q, 1);
09f82ac… drh 725 const char *zNew = db_column_text(&q, 2);
09f82ac… drh 726 const char *zUuid = db_column_text(&q, 3);
09f82ac… drh 727 @ <tr>
09f82ac… drh 728 @ <td>%z(href("%R/timeline?c=%t",zDate))%s(zDate)</a></td>
09f82ac… drh 729 @ <td>%z(href("%R/finfo?name=%t",zOld))%h(zOld)</a></td>
09f82ac… drh 730 @ <td>%z(href("%R/finfo?name=%t",zNew))%h(zNew)</a></td>
1fee037… drh 731 @ <td>%z(href("%R/info/%!S",zUuid))%S(zUuid)</a></td></tr>
09f82ac… drh 732 }
80ec9d5… drh 733 @ </tbody></table>
09f82ac… drh 734 db_finalize(&q);
80ec9d5… drh 735 style_table_sorter();
112c713… drh 736 style_finish_page();
e5121b4… drh 737 }

Keyboard Shortcuts

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