6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** Copyright (c) 2007 D. Richard Hipp 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** This program is free software; you can redistribute it and/or 6458f020fc 2008-05-14 drh: ** modify it under the terms of the GNU General Public 6458f020fc 2008-05-14 drh: ** License version 2 as published by the Free Software Foundation. 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** This program is distributed in the hope that it will be useful, 6458f020fc 2008-05-14 drh: ** but WITHOUT ANY WARRANTY; without even the implied warranty of 6458f020fc 2008-05-14 drh: ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 6458f020fc 2008-05-14 drh: ** General Public License for more details. 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** You should have received a copy of the GNU General Public 6458f020fc 2008-05-14 drh: ** License along with this library; if not, write to the 6458f020fc 2008-05-14 drh: ** Free Software Foundation, Inc., 59 Temple Place - Suite 330, 6458f020fc 2008-05-14 drh: ** Boston, MA 02111-1307, USA. 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** Author contact information: 6458f020fc 2008-05-14 drh: ** drh@hwaci.com 6458f020fc 2008-05-14 drh: ** http://www.hwaci.com/drh/ 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ******************************************************************************* 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** This file contains code used to find decendants of a version 6458f020fc 2008-05-14 drh: ** or leaves of a version tree. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: #include "config.h" 6458f020fc 2008-05-14 drh: #include "descendants.h" 6458f020fc 2008-05-14 drh: #include <assert.h> 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** Create a temporary table named "leaves" if it does not 6458f020fc 2008-05-14 drh: ** already exist. Load this table with the RID of all b6e22e62cf 2009-01-20 drh: ** check-ins that are leaves which are decended from b6e22e62cf 2009-01-20 drh: ** check-in iBase. b6e22e62cf 2009-01-20 drh: ** b6e22e62cf 2009-01-20 drh: ** A "leaf" is a check-in that has no children. For the purpose b6e22e62cf 2009-01-20 drh: ** of finding leaves, children marked with the "newbranch" tag are b6e22e62cf 2009-01-20 drh: ** not counted as children. For example: b6e22e62cf 2009-01-20 drh: ** b6e22e62cf 2009-01-20 drh: ** b6e22e62cf 2009-01-20 drh: ** A -> B -> C -> D b6e22e62cf 2009-01-20 drh: ** `-> E b6e22e62cf 2009-01-20 drh: ** b6e22e62cf 2009-01-20 drh: ** D and E are clearly leaves since they have no children. If b6e22e62cf 2009-01-20 drh: ** D has the "newbranch" tag, then C is also a leaf since its only b6e22e62cf 2009-01-20 drh: ** child is marked as a newbranch. b6e22e62cf 2009-01-20 drh: ** b6e22e62cf 2009-01-20 drh: ** The closeMode flag determines behavior associated with the "closed" b6e22e62cf 2009-01-20 drh: ** tag: b6e22e62cf 2009-01-20 drh: ** b6e22e62cf 2009-01-20 drh: ** closeMode==0 Show all leaves regardless of the "closed" tag. b6e22e62cf 2009-01-20 drh: ** b6e22e62cf 2009-01-20 drh: ** closeMode==1 Show only leaves without the "closed" tag. b6e22e62cf 2009-01-20 drh: ** b6e22e62cf 2009-01-20 drh: ** closeMode==2 Show only leaves with the "closed" tag. b6e22e62cf 2009-01-20 drh: ** b6e22e62cf 2009-01-20 drh: ** The default behavior is to ignore closed leaves (closeMode==0). To b6e22e62cf 2009-01-20 drh: ** Show all leaves, use closeMode==1. To show only closed leaves, use b6e22e62cf 2009-01-20 drh: ** closeMode==2. 6458f020fc 2008-05-14 drh: */ b6e22e62cf 2009-01-20 drh: void compute_leaves(int iBase, int closeMode){ 6458f020fc 2008-05-14 drh: Bag seen; /* Descendants seen */ 6458f020fc 2008-05-14 drh: Bag pending; /* Unpropagated descendants */ b6e22e62cf 2009-01-20 drh: Stmt q; /* Query to find children of a check-in */ b6e22e62cf 2009-01-20 drh: Stmt isBr; /* Query to check to see if a check-in starts a new branch */ b6e22e62cf 2009-01-20 drh: Stmt ins; /* INSERT statement for a new record */ 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: db_multi_exec( 6458f020fc 2008-05-14 drh: "CREATE TEMP TABLE IF NOT EXISTS leaves(" 6458f020fc 2008-05-14 drh: " rid INTEGER PRIMARY KEY" 6458f020fc 2008-05-14 drh: ");" 6458f020fc 2008-05-14 drh: "DELETE FROM leaves;" 6458f020fc 2008-05-14 drh: ); 6458f020fc 2008-05-14 drh: bag_init(&seen); 6458f020fc 2008-05-14 drh: bag_init(&pending); b6e22e62cf 2009-01-20 drh: if( iBase<=0 ){ b6e22e62cf 2009-01-20 drh: iBase = db_int(0, "SELECT objid FROM event WHERE type='ci'" b6e22e62cf 2009-01-20 drh: " ORDER BY mtime LIMIT 1"); b6e22e62cf 2009-01-20 drh: } 6458f020fc 2008-05-14 drh: bag_insert(&pending, iBase); b6e22e62cf 2009-01-20 drh: db_prepare(&q, "SELECT cid FROM plink WHERE pid=:rid"); b6e22e62cf 2009-01-20 drh: db_prepare(&isBr, b6e22e62cf 2009-01-20 drh: "SELECT 1 FROM tagxref WHERE rid=:rid AND tagid=%d AND tagtype=1", b6e22e62cf 2009-01-20 drh: TAG_NEWBRANCH b6e22e62cf 2009-01-20 drh: ); b6e22e62cf 2009-01-20 drh: db_prepare(&ins, "INSERT OR IGNORE INTO leaves VALUES(:rid)"); 6458f020fc 2008-05-14 drh: while( bag_count(&pending) ){ 6458f020fc 2008-05-14 drh: int rid = bag_first(&pending); 6458f020fc 2008-05-14 drh: int cnt = 0; 6458f020fc 2008-05-14 drh: bag_remove(&pending, rid); b6e22e62cf 2009-01-20 drh: db_bind_int(&q, ":rid", rid); 6458f020fc 2008-05-14 drh: while( db_step(&q)==SQLITE_ROW ){ 6458f020fc 2008-05-14 drh: int cid = db_column_int(&q, 0); 6458f020fc 2008-05-14 drh: if( bag_insert(&seen, cid) ){ 6458f020fc 2008-05-14 drh: bag_insert(&pending, cid); 6458f020fc 2008-05-14 drh: } b6e22e62cf 2009-01-20 drh: db_bind_int(&isBr, ":rid", cid); b6e22e62cf 2009-01-20 drh: if( db_step(&isBr)==SQLITE_DONE ){ b6e22e62cf 2009-01-20 drh: cnt++; b6e22e62cf 2009-01-20 drh: } b6e22e62cf 2009-01-20 drh: db_reset(&isBr); 6458f020fc 2008-05-14 drh: } b6e22e62cf 2009-01-20 drh: db_reset(&q); 6458f020fc 2008-05-14 drh: if( cnt==0 ){ b6e22e62cf 2009-01-20 drh: db_bind_int(&ins, ":rid", rid); b6e22e62cf 2009-01-20 drh: db_step(&ins); b6e22e62cf 2009-01-20 drh: db_reset(&ins); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: } b6e22e62cf 2009-01-20 drh: db_finalize(&ins); b6e22e62cf 2009-01-20 drh: db_finalize(&isBr); b6e22e62cf 2009-01-20 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: bag_clear(&pending); 6458f020fc 2008-05-14 drh: bag_clear(&seen); b6e22e62cf 2009-01-20 drh: if( closeMode==1 ){ b6e22e62cf 2009-01-20 drh: db_multi_exec( b6e22e62cf 2009-01-20 drh: "DELETE FROM leaves WHERE rid IN" b6e22e62cf 2009-01-20 drh: " (SELECT leaves.rid FROM leaves, tagxref" b6e22e62cf 2009-01-20 drh: " WHERE tagxref.rid=leaves.rid " b6e22e62cf 2009-01-20 drh: " AND tagxref.tagid=%d" b6e22e62cf 2009-01-20 drh: " AND tagxref.tagtype>0)", b6e22e62cf 2009-01-20 drh: TAG_CLOSED b6e22e62cf 2009-01-20 drh: ); b6e22e62cf 2009-01-20 drh: }else if( closeMode==2 ){ b6e22e62cf 2009-01-20 drh: db_multi_exec( b6e22e62cf 2009-01-20 drh: "DELETE FROM leaves WHERE rid NOT IN" b6e22e62cf 2009-01-20 drh: " (SELECT leaves.rid FROM leaves, tagxref" b6e22e62cf 2009-01-20 drh: " WHERE tagxref.rid=leaves.rid " b6e22e62cf 2009-01-20 drh: " AND tagxref.tagid=%d" b6e22e62cf 2009-01-20 drh: " AND tagxref.tagtype>0)", b6e22e62cf 2009-01-20 drh: TAG_CLOSED b6e22e62cf 2009-01-20 drh: ); b6e22e62cf 2009-01-20 drh: } 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** Load the record ID rid and up to N-1 closest ancestors into 6458f020fc 2008-05-14 drh: ** the "ok" table. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void compute_ancestors(int rid, int N){ 6458f020fc 2008-05-14 drh: Bag seen; 6458f020fc 2008-05-14 drh: PQueue queue; 6458f020fc 2008-05-14 drh: bag_init(&seen); 6458f020fc 2008-05-14 drh: pqueue_init(&queue); 6458f020fc 2008-05-14 drh: bag_insert(&seen, rid); 6458f020fc 2008-05-14 drh: pqueue_insert(&queue, rid, 0.0); 6458f020fc 2008-05-14 drh: while( (N--)>0 && (rid = pqueue_extract(&queue))!=0 ){ 6458f020fc 2008-05-14 drh: Stmt q; 6458f020fc 2008-05-14 drh: db_multi_exec("INSERT OR IGNORE INTO ok VALUES(%d)", rid); 6458f020fc 2008-05-14 drh: db_prepare(&q, 6458f020fc 2008-05-14 drh: "SELECT a.pid, b.mtime FROM plink a LEFT JOIN plink b ON b.cid=a.pid" 6458f020fc 2008-05-14 drh: " WHERE a.cid=%d", rid 6458f020fc 2008-05-14 drh: ); 6458f020fc 2008-05-14 drh: while( db_step(&q)==SQLITE_ROW ){ 6458f020fc 2008-05-14 drh: int pid = db_column_int(&q, 0); 6458f020fc 2008-05-14 drh: double mtime = db_column_double(&q, 1); 6458f020fc 2008-05-14 drh: if( bag_insert(&seen, pid) ){ 6458f020fc 2008-05-14 drh: pqueue_insert(&queue, pid, -mtime); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: bag_clear(&seen); 6458f020fc 2008-05-14 drh: pqueue_clear(&queue); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** Load the record ID rid and up to N-1 closest descendants into 6458f020fc 2008-05-14 drh: ** the "ok" table. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void compute_descendants(int rid, int N){ 6458f020fc 2008-05-14 drh: Bag seen; 6458f020fc 2008-05-14 drh: PQueue queue; 6458f020fc 2008-05-14 drh: bag_init(&seen); 6458f020fc 2008-05-14 drh: pqueue_init(&queue); 6458f020fc 2008-05-14 drh: bag_insert(&seen, rid); 6458f020fc 2008-05-14 drh: pqueue_insert(&queue, rid, 0.0); 6458f020fc 2008-05-14 drh: while( (N--)>0 && (rid = pqueue_extract(&queue))!=0 ){ 6458f020fc 2008-05-14 drh: Stmt q; 6458f020fc 2008-05-14 drh: db_multi_exec("INSERT OR IGNORE INTO ok VALUES(%d)", rid); 6458f020fc 2008-05-14 drh: db_prepare(&q,"SELECT cid, mtime FROM plink WHERE pid=%d", rid); 6458f020fc 2008-05-14 drh: while( db_step(&q)==SQLITE_ROW ){ 6458f020fc 2008-05-14 drh: int pid = db_column_int(&q, 0); 6458f020fc 2008-05-14 drh: double mtime = db_column_double(&q, 1); 6458f020fc 2008-05-14 drh: if( bag_insert(&seen, pid) ){ 6458f020fc 2008-05-14 drh: pqueue_insert(&queue, pid, mtime); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: bag_clear(&seen); 6458f020fc 2008-05-14 drh: pqueue_clear(&queue); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** COMMAND: descendants 6458f020fc 2008-05-14 drh: ** e8c4f69c50 2008-10-24 drh: ** Usage: %fossil descendants ?BASELINE-ID? 6458f020fc 2008-05-14 drh: ** e8c4f69c50 2008-10-24 drh: ** Find all leaf descendants of the baseline specified or if the argument e8c4f69c50 2008-10-24 drh: ** is omitted, of the baseline currently checked out. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void descendants_cmd(void){ 6458f020fc 2008-05-14 drh: Stmt q; 6458f020fc 2008-05-14 drh: int base; 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: db_must_be_within_tree(); 6458f020fc 2008-05-14 drh: if( g.argc==2 ){ 6458f020fc 2008-05-14 drh: base = db_lget_int("checkout", 0); 6458f020fc 2008-05-14 drh: }else{ 6458f020fc 2008-05-14 drh: base = name_to_rid(g.argv[2]); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: if( base==0 ) return; b6e22e62cf 2009-01-20 drh: compute_leaves(base, 0); 6458f020fc 2008-05-14 drh: db_prepare(&q, 6458f020fc 2008-05-14 drh: "%s" 6458f020fc 2008-05-14 drh: " AND event.objid IN (SELECT rid FROM leaves)" 6458f020fc 2008-05-14 drh: " ORDER BY event.mtime DESC", 6458f020fc 2008-05-14 drh: timeline_query_for_tty() 6458f020fc 2008-05-14 drh: ); 6458f020fc 2008-05-14 drh: print_timeline(&q, 20); 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** COMMAND: leaves 6458f020fc 2008-05-14 drh: ** b6e22e62cf 2009-01-20 drh: ** Usage: %fossil leaves ?--all? ?--closed? 6458f020fc 2008-05-14 drh: ** b6e22e62cf 2009-01-20 drh: ** Find leaves of all branches. By default show only open leaves. b6e22e62cf 2009-01-20 drh: ** The --all flag causes all leaves (closed and open) to be shown. b6e22e62cf 2009-01-20 drh: ** The --closed flag shows only closed leaves. 6458f020fc 2008-05-14 drh: */ b6e22e62cf 2009-01-20 drh: void leaves_cmd(void){ 6458f020fc 2008-05-14 drh: Stmt q; b6e22e62cf 2009-01-20 drh: int showAll = find_option("all", 0, 0)!=0; b6e22e62cf 2009-01-20 drh: int showClosed = find_option("closed", 0, 0)!=0; 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: db_must_be_within_tree(); b6e22e62cf 2009-01-20 drh: compute_leaves(0, showAll ? 0 : showClosed ? 2 : 1); 6458f020fc 2008-05-14 drh: db_prepare(&q, 6458f020fc 2008-05-14 drh: "%s" b6e22e62cf 2009-01-20 drh: " AND blob.rid IN leaves" 6458f020fc 2008-05-14 drh: " ORDER BY event.mtime DESC", 6458f020fc 2008-05-14 drh: timeline_query_for_tty() 6458f020fc 2008-05-14 drh: ); 6458f020fc 2008-05-14 drh: print_timeline(&q, 2000); 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** WEBPAGE: leaves 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** Find leaves of all branches. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void leaves_page(void){ 6458f020fc 2008-05-14 drh: Stmt q; b6e22e62cf 2009-01-20 drh: int showAll = P("all")!=0; b6e22e62cf 2009-01-20 drh: int showClosed = P("closed")!=0; 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: login_check_credentials(); 6458f020fc 2008-05-14 drh: if( !g.okRead ){ login_needed(); return; } 6458f020fc 2008-05-14 drh: b6e22e62cf 2009-01-20 drh: if( !showAll ){ b6e22e62cf 2009-01-20 drh: style_submenu_element("All", "All", "leaves?all"); b6e22e62cf 2009-01-20 drh: } b6e22e62cf 2009-01-20 drh: if( !showClosed ){ b6e22e62cf 2009-01-20 drh: style_submenu_element("Closed", "Closed", "leaves?closed"); b6e22e62cf 2009-01-20 drh: } b6e22e62cf 2009-01-20 drh: if( showClosed || showAll ){ b6e22e62cf 2009-01-20 drh: style_submenu_element("Open", "Open", "leaves"); b6e22e62cf 2009-01-20 drh: } 6458f020fc 2008-05-14 drh: style_header("Leaves"); 6458f020fc 2008-05-14 drh: login_anonymous_available(); b6e22e62cf 2009-01-20 drh: compute_leaves(0, showAll ? 0 : showClosed ? 2 : 1); b7f32a71ab 2009-01-20 drh: @ <table width="33%%" align="right" border="1"> b7f32a71ab 2009-01-20 drh: @ <tr><td> b7f32a71ab 2009-01-20 drh: @ <b>Nomenclature:</b> b7f32a71ab 2009-01-20 drh: @ <ol> b7f32a71ab 2009-01-20 drh: @ <li> A <b>leaf</b> is a check-in with no descendants.</li> b7f32a71ab 2009-01-20 drh: @ <li> An <b>open leaf</b> is a leaf that does not have a "closed" tag b7f32a71ab 2009-01-20 drh: @ and is thus assumed to still be in use.</li> b7f32a71ab 2009-01-20 drh: @ <li> A <b>closed leaf</b> has a "closed" tag and is thus assumed to b7f32a71ab 2009-01-20 drh: @ be historical and no longer in active use.</li> b7f32a71ab 2009-01-20 drh: @ </ol> b7f32a71ab 2009-01-20 drh: @ </td></tr></table> b6e22e62cf 2009-01-20 drh: if( showAll ){ b6e22e62cf 2009-01-20 drh: @ <h1>All leaves, both open and closed</h1> b6e22e62cf 2009-01-20 drh: }else if( showClosed ){ b6e22e62cf 2009-01-20 drh: @ <h1>Closed leaves only</h1> b6e22e62cf 2009-01-20 drh: }else{ b6e22e62cf 2009-01-20 drh: @ <h1>All open leaves</h1> b6e22e62cf 2009-01-20 drh: } 6458f020fc 2008-05-14 drh: db_prepare(&q, 6458f020fc 2008-05-14 drh: "%s" b6e22e62cf 2009-01-20 drh: " AND blob.rid IN leaves" 6458f020fc 2008-05-14 drh: " ORDER BY event.mtime DESC", 6458f020fc 2008-05-14 drh: timeline_query_for_www() 6458f020fc 2008-05-14 drh: ); 580d6ad8c7 2009-01-21 drh: www_print_timeline(&q, 0, 0); 6458f020fc 2008-05-14 drh: db_finalize(&q); b7f32a71ab 2009-01-20 drh: @ <br clear="both"> 6458f020fc 2008-05-14 drh: @ <script> 6458f020fc 2008-05-14 drh: @ function xin(id){ 6458f020fc 2008-05-14 drh: @ } 6458f020fc 2008-05-14 drh: @ function xout(id){ 6458f020fc 2008-05-14 drh: @ } 6458f020fc 2008-05-14 drh: @ </script> 6458f020fc 2008-05-14 drh: style_footer(); 6458f020fc 2008-05-14 drh: }
File Annotation