Fossil SCM
Add the (unsupported) test-shortest-path command for finding the shortest path between two checkins in the DAG.
Commit
c49ee72b09f0b565b2147656b1b988b5840669cf
Parent
7ec43ccb7a1f348…
1 file changed
+64
-10
+64
-10
| --- src/bisect.c | ||
| +++ src/bisect.c | ||
| @@ -23,12 +23,16 @@ | ||
| 23 | 23 | /* Nodes for the shortest path algorithm. |
| 24 | 24 | */ |
| 25 | 25 | typedef struct BisectNode BisectNode; |
| 26 | 26 | struct BisectNode { |
| 27 | 27 | int rid; /* ID for this node */ |
| 28 | + int fromIsParent; /* True if pFrom is the parent of rid */ | |
| 28 | 29 | BisectNode *pFrom; /* Node we came from */ |
| 29 | - BisectNode *pPeer; /* List of nodes of the same generation */ | |
| 30 | + union { | |
| 31 | + BisectNode *pPeer; /* List of nodes of the same generation */ | |
| 32 | + BisectNode *pTo; /* Next on path from beginning to end */ | |
| 33 | + } u; | |
| 30 | 34 | BisectNode *pAll; /* List of all nodes */ |
| 31 | 35 | }; |
| 32 | 36 | |
| 33 | 37 | /* |
| 34 | 38 | ** Local variables for this module |
| @@ -38,23 +42,25 @@ | ||
| 38 | 42 | BisectNode *pAll; /* All nodes */ |
| 39 | 43 | Bag seen; /* Nodes seen before */ |
| 40 | 44 | int bad; /* The bad version */ |
| 41 | 45 | int good; /* The good version */ |
| 42 | 46 | int nStep; /* Number of steps from good to bad */ |
| 47 | + BisectNode *pStart; /* Earliest node (bad) */ | |
| 43 | 48 | BisectNode *pEnd; /* Most recent (good) */ |
| 44 | 49 | } bisect; |
| 45 | 50 | |
| 46 | 51 | /* |
| 47 | 52 | ** Create a new node |
| 48 | 53 | */ |
| 49 | -static BisectNode *bisect_new_node(int rid, BisectNode *pFrom){ | |
| 54 | +static BisectNode *bisect_new_node(int rid, BisectNode *pFrom, int isParent){ | |
| 50 | 55 | BisectNode *p; |
| 51 | 56 | |
| 52 | 57 | p = fossil_malloc( sizeof(*p) ); |
| 53 | 58 | p->rid = rid; |
| 59 | + p->fromIsParent = isParent; | |
| 54 | 60 | p->pFrom = pFrom; |
| 55 | - p->pPeer = bisect.pCurrent; | |
| 61 | + p->u.pPeer = bisect.pCurrent; | |
| 56 | 62 | bisect.pCurrent = p; |
| 57 | 63 | p->pAll = bisect.pAll; |
| 58 | 64 | bisect.pAll = p; |
| 59 | 65 | bisect.pEnd = p; |
| 60 | 66 | bag_insert(&bisect.seen, rid); |
| @@ -81,41 +87,89 @@ | ||
| 81 | 87 | /* |
| 82 | 88 | ** Compute the shortest path from iFrom to iTo |
| 83 | 89 | */ |
| 84 | 90 | static BisectNode *bisect_shortest_path(int iFrom, int iTo){ |
| 85 | 91 | Stmt s; |
| 86 | - BisectNode *pStart; | |
| 87 | 92 | BisectNode *pPrev; |
| 88 | 93 | BisectNode *p; |
| 89 | 94 | |
| 90 | 95 | bisect_reset(); |
| 91 | - pStart = bisect_new_node(iFrom, 0); | |
| 92 | - if( iTo==iFrom ) return pStart; | |
| 93 | - db_prepare(&s, "SELECT cid FROM plink WHERE pid=:pid " | |
| 94 | - "UNION ALL SELECT pid FROM plink WHERE cid=:pid"); | |
| 96 | + bisect.pStart = bisect_new_node(iFrom, 0, 0); | |
| 97 | + if( iTo==iFrom ) return bisect.pStart; | |
| 98 | + db_prepare(&s, "SELECT cid, 1 FROM plink WHERE pid=:pid " | |
| 99 | + "UNION ALL SELECT pid, 0 FROM plink WHERE cid=:pid"); | |
| 95 | 100 | while( bisect.pCurrent ){ |
| 96 | 101 | bisect.nStep++; |
| 97 | 102 | pPrev = bisect.pCurrent; |
| 98 | 103 | bisect.pCurrent = 0; |
| 99 | 104 | while( pPrev ){ |
| 100 | 105 | db_bind_int(&s, ":pid", pPrev->rid); |
| 101 | 106 | while( db_step(&s)==SQLITE_ROW ){ |
| 102 | 107 | int cid = db_column_int(&s, 0); |
| 108 | + int isParent = db_column_int(&s, 1); | |
| 103 | 109 | if( bag_find(&bisect.seen, cid) ) continue; |
| 104 | - p = bisect_new_node(cid, pPrev); | |
| 110 | + p = bisect_new_node(cid, pPrev, isParent); | |
| 105 | 111 | if( cid==iTo ){ |
| 106 | 112 | db_finalize(&s); |
| 107 | 113 | return p; |
| 108 | 114 | } |
| 109 | 115 | } |
| 110 | 116 | db_reset(&s); |
| 111 | - pPrev = pPrev->pPeer; | |
| 117 | + pPrev = pPrev->u.pPeer; | |
| 112 | 118 | } |
| 113 | 119 | } |
| 114 | 120 | bisect_reset(); |
| 115 | 121 | return 0; |
| 116 | 122 | } |
| 123 | + | |
| 124 | +/* | |
| 125 | +** Construct the path from bisect.pStart to bisect.pEnd in the u.pTo fields. | |
| 126 | +*/ | |
| 127 | +static void bisect_reverse_path(void){ | |
| 128 | + BisectNode *p; | |
| 129 | + for(p=bisect.pEnd; p && p->pFrom; p = p->pFrom){ | |
| 130 | + p->pFrom->u.pTo = p; | |
| 131 | + } | |
| 132 | + bisect.pEnd->u.pTo = 0; | |
| 133 | + assert( p==bisect.pStart ); | |
| 134 | +} | |
| 135 | + | |
| 136 | +/* | |
| 137 | +** COMMAND: test-shortest-path VERSION1 VERSION2 | |
| 138 | +** | |
| 139 | +** Report the shortest path between two checkins. | |
| 140 | +*/ | |
| 141 | +void shortest_path_test_cmd(void){ | |
| 142 | + int iFrom; | |
| 143 | + int iTo; | |
| 144 | + BisectNode *p; | |
| 145 | + int n; | |
| 146 | + db_find_and_open_repository(0,0); | |
| 147 | + if( g.argc!=4 ) usage("VERSION1 VERSION2"); | |
| 148 | + iFrom = name_to_rid(g.argv[2]); | |
| 149 | + iTo = name_to_rid(g.argv[3]); | |
| 150 | + p = bisect_shortest_path(iFrom, iTo); | |
| 151 | + if( p==0 ){ | |
| 152 | + fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]); | |
| 153 | + } | |
| 154 | + bisect_reverse_path(); | |
| 155 | + for(n=1, p=bisect.pStart; p; p=p->u.pTo, n++){ | |
| 156 | + char *z; | |
| 157 | + z = db_text(0, | |
| 158 | + "SELECT substr(uuid,1,12) || ' ' || datetime(mtime)" | |
| 159 | + " FROM blob, event" | |
| 160 | + " WHERE blob.rid=%d AND event.objid=%d AND event.type='ci'", | |
| 161 | + p->rid, p->rid); | |
| 162 | + printf("%4d: %s", n, z); | |
| 163 | + fossil_free(z); | |
| 164 | + if( p->u.pTo ){ | |
| 165 | + printf(" is a %s of\n", p->u.pTo->fromIsParent ? "parent" : "child"); | |
| 166 | + }else{ | |
| 167 | + printf("\n"); | |
| 168 | + } | |
| 169 | + } | |
| 170 | +} | |
| 117 | 171 | |
| 118 | 172 | /* |
| 119 | 173 | ** Find the shortest path between bad and good. |
| 120 | 174 | */ |
| 121 | 175 | static BisectNode *bisect_path(void){ |
| 122 | 176 |
| --- src/bisect.c | |
| +++ src/bisect.c | |
| @@ -23,12 +23,16 @@ | |
| 23 | /* Nodes for the shortest path algorithm. |
| 24 | */ |
| 25 | typedef struct BisectNode BisectNode; |
| 26 | struct BisectNode { |
| 27 | int rid; /* ID for this node */ |
| 28 | BisectNode *pFrom; /* Node we came from */ |
| 29 | BisectNode *pPeer; /* List of nodes of the same generation */ |
| 30 | BisectNode *pAll; /* List of all nodes */ |
| 31 | }; |
| 32 | |
| 33 | /* |
| 34 | ** Local variables for this module |
| @@ -38,23 +42,25 @@ | |
| 38 | BisectNode *pAll; /* All nodes */ |
| 39 | Bag seen; /* Nodes seen before */ |
| 40 | int bad; /* The bad version */ |
| 41 | int good; /* The good version */ |
| 42 | int nStep; /* Number of steps from good to bad */ |
| 43 | BisectNode *pEnd; /* Most recent (good) */ |
| 44 | } bisect; |
| 45 | |
| 46 | /* |
| 47 | ** Create a new node |
| 48 | */ |
| 49 | static BisectNode *bisect_new_node(int rid, BisectNode *pFrom){ |
| 50 | BisectNode *p; |
| 51 | |
| 52 | p = fossil_malloc( sizeof(*p) ); |
| 53 | p->rid = rid; |
| 54 | p->pFrom = pFrom; |
| 55 | p->pPeer = bisect.pCurrent; |
| 56 | bisect.pCurrent = p; |
| 57 | p->pAll = bisect.pAll; |
| 58 | bisect.pAll = p; |
| 59 | bisect.pEnd = p; |
| 60 | bag_insert(&bisect.seen, rid); |
| @@ -81,41 +87,89 @@ | |
| 81 | /* |
| 82 | ** Compute the shortest path from iFrom to iTo |
| 83 | */ |
| 84 | static BisectNode *bisect_shortest_path(int iFrom, int iTo){ |
| 85 | Stmt s; |
| 86 | BisectNode *pStart; |
| 87 | BisectNode *pPrev; |
| 88 | BisectNode *p; |
| 89 | |
| 90 | bisect_reset(); |
| 91 | pStart = bisect_new_node(iFrom, 0); |
| 92 | if( iTo==iFrom ) return pStart; |
| 93 | db_prepare(&s, "SELECT cid FROM plink WHERE pid=:pid " |
| 94 | "UNION ALL SELECT pid FROM plink WHERE cid=:pid"); |
| 95 | while( bisect.pCurrent ){ |
| 96 | bisect.nStep++; |
| 97 | pPrev = bisect.pCurrent; |
| 98 | bisect.pCurrent = 0; |
| 99 | while( pPrev ){ |
| 100 | db_bind_int(&s, ":pid", pPrev->rid); |
| 101 | while( db_step(&s)==SQLITE_ROW ){ |
| 102 | int cid = db_column_int(&s, 0); |
| 103 | if( bag_find(&bisect.seen, cid) ) continue; |
| 104 | p = bisect_new_node(cid, pPrev); |
| 105 | if( cid==iTo ){ |
| 106 | db_finalize(&s); |
| 107 | return p; |
| 108 | } |
| 109 | } |
| 110 | db_reset(&s); |
| 111 | pPrev = pPrev->pPeer; |
| 112 | } |
| 113 | } |
| 114 | bisect_reset(); |
| 115 | return 0; |
| 116 | } |
| 117 | |
| 118 | /* |
| 119 | ** Find the shortest path between bad and good. |
| 120 | */ |
| 121 | static BisectNode *bisect_path(void){ |
| 122 |
| --- src/bisect.c | |
| +++ src/bisect.c | |
| @@ -23,12 +23,16 @@ | |
| 23 | /* Nodes for the shortest path algorithm. |
| 24 | */ |
| 25 | typedef struct BisectNode BisectNode; |
| 26 | struct BisectNode { |
| 27 | int rid; /* ID for this node */ |
| 28 | int fromIsParent; /* True if pFrom is the parent of rid */ |
| 29 | BisectNode *pFrom; /* Node we came from */ |
| 30 | union { |
| 31 | BisectNode *pPeer; /* List of nodes of the same generation */ |
| 32 | BisectNode *pTo; /* Next on path from beginning to end */ |
| 33 | } u; |
| 34 | BisectNode *pAll; /* List of all nodes */ |
| 35 | }; |
| 36 | |
| 37 | /* |
| 38 | ** Local variables for this module |
| @@ -38,23 +42,25 @@ | |
| 42 | BisectNode *pAll; /* All nodes */ |
| 43 | Bag seen; /* Nodes seen before */ |
| 44 | int bad; /* The bad version */ |
| 45 | int good; /* The good version */ |
| 46 | int nStep; /* Number of steps from good to bad */ |
| 47 | BisectNode *pStart; /* Earliest node (bad) */ |
| 48 | BisectNode *pEnd; /* Most recent (good) */ |
| 49 | } bisect; |
| 50 | |
| 51 | /* |
| 52 | ** Create a new node |
| 53 | */ |
| 54 | static BisectNode *bisect_new_node(int rid, BisectNode *pFrom, int isParent){ |
| 55 | BisectNode *p; |
| 56 | |
| 57 | p = fossil_malloc( sizeof(*p) ); |
| 58 | p->rid = rid; |
| 59 | p->fromIsParent = isParent; |
| 60 | p->pFrom = pFrom; |
| 61 | p->u.pPeer = bisect.pCurrent; |
| 62 | bisect.pCurrent = p; |
| 63 | p->pAll = bisect.pAll; |
| 64 | bisect.pAll = p; |
| 65 | bisect.pEnd = p; |
| 66 | bag_insert(&bisect.seen, rid); |
| @@ -81,41 +87,89 @@ | |
| 87 | /* |
| 88 | ** Compute the shortest path from iFrom to iTo |
| 89 | */ |
| 90 | static BisectNode *bisect_shortest_path(int iFrom, int iTo){ |
| 91 | Stmt s; |
| 92 | BisectNode *pPrev; |
| 93 | BisectNode *p; |
| 94 | |
| 95 | bisect_reset(); |
| 96 | bisect.pStart = bisect_new_node(iFrom, 0, 0); |
| 97 | if( iTo==iFrom ) return bisect.pStart; |
| 98 | db_prepare(&s, "SELECT cid, 1 FROM plink WHERE pid=:pid " |
| 99 | "UNION ALL SELECT pid, 0 FROM plink WHERE cid=:pid"); |
| 100 | while( bisect.pCurrent ){ |
| 101 | bisect.nStep++; |
| 102 | pPrev = bisect.pCurrent; |
| 103 | bisect.pCurrent = 0; |
| 104 | while( pPrev ){ |
| 105 | db_bind_int(&s, ":pid", pPrev->rid); |
| 106 | while( db_step(&s)==SQLITE_ROW ){ |
| 107 | int cid = db_column_int(&s, 0); |
| 108 | int isParent = db_column_int(&s, 1); |
| 109 | if( bag_find(&bisect.seen, cid) ) continue; |
| 110 | p = bisect_new_node(cid, pPrev, isParent); |
| 111 | if( cid==iTo ){ |
| 112 | db_finalize(&s); |
| 113 | return p; |
| 114 | } |
| 115 | } |
| 116 | db_reset(&s); |
| 117 | pPrev = pPrev->u.pPeer; |
| 118 | } |
| 119 | } |
| 120 | bisect_reset(); |
| 121 | return 0; |
| 122 | } |
| 123 | |
| 124 | /* |
| 125 | ** Construct the path from bisect.pStart to bisect.pEnd in the u.pTo fields. |
| 126 | */ |
| 127 | static void bisect_reverse_path(void){ |
| 128 | BisectNode *p; |
| 129 | for(p=bisect.pEnd; p && p->pFrom; p = p->pFrom){ |
| 130 | p->pFrom->u.pTo = p; |
| 131 | } |
| 132 | bisect.pEnd->u.pTo = 0; |
| 133 | assert( p==bisect.pStart ); |
| 134 | } |
| 135 | |
| 136 | /* |
| 137 | ** COMMAND: test-shortest-path VERSION1 VERSION2 |
| 138 | ** |
| 139 | ** Report the shortest path between two checkins. |
| 140 | */ |
| 141 | void shortest_path_test_cmd(void){ |
| 142 | int iFrom; |
| 143 | int iTo; |
| 144 | BisectNode *p; |
| 145 | int n; |
| 146 | db_find_and_open_repository(0,0); |
| 147 | if( g.argc!=4 ) usage("VERSION1 VERSION2"); |
| 148 | iFrom = name_to_rid(g.argv[2]); |
| 149 | iTo = name_to_rid(g.argv[3]); |
| 150 | p = bisect_shortest_path(iFrom, iTo); |
| 151 | if( p==0 ){ |
| 152 | fossil_fatal("no path from %s to %s", g.argv[1], g.argv[2]); |
| 153 | } |
| 154 | bisect_reverse_path(); |
| 155 | for(n=1, p=bisect.pStart; p; p=p->u.pTo, n++){ |
| 156 | char *z; |
| 157 | z = db_text(0, |
| 158 | "SELECT substr(uuid,1,12) || ' ' || datetime(mtime)" |
| 159 | " FROM blob, event" |
| 160 | " WHERE blob.rid=%d AND event.objid=%d AND event.type='ci'", |
| 161 | p->rid, p->rid); |
| 162 | printf("%4d: %s", n, z); |
| 163 | fossil_free(z); |
| 164 | if( p->u.pTo ){ |
| 165 | printf(" is a %s of\n", p->u.pTo->fromIsParent ? "parent" : "child"); |
| 166 | }else{ |
| 167 | printf("\n"); |
| 168 | } |
| 169 | } |
| 170 | } |
| 171 | |
| 172 | /* |
| 173 | ** Find the shortest path between bad and good. |
| 174 | */ |
| 175 | static BisectNode *bisect_path(void){ |
| 176 |