Artifact Content
Not logged in

Artifact 6cb824a041723f2bf8e82765386ed5974e335c92:


     1  /*
     2  ** Copyright (c) 2007 D. Richard Hipp
     3  **
     4  ** This program is free software; you can redistribute it and/or
     5  ** modify it under the terms of the Simplified BSD License (also
     6  ** known as the "2-Clause License" or "FreeBSD License".)
     7  
     8  ** This program is distributed in the hope that it will be useful,
     9  ** but without any warranty; without even the implied warranty of
    10  ** merchantability or fitness for a particular purpose.
    11  **
    12  ** Author contact information:
    13  **   drh@hwaci.com
    14  **   http://www.hwaci.com/drh/
    15  **
    16  *******************************************************************************
    17  **
    18  ** This file contains code used to find descendants of a version
    19  ** or leaves of a version tree.
    20  */
    21  #include "config.h"
    22  #include "descendants.h"
    23  #include <assert.h>
    24  
    25  
    26  /*
    27  ** Create a temporary table named "leaves" if it does not
    28  ** already exist.  Load this table with the RID of all
    29  ** check-ins that are leaves which are descended from
    30  ** check-in iBase.
    31  **
    32  ** A "leaf" is a check-in that has no children in the same branch.
    33  ** There is a separate permanent table LEAF that contains all leaves
    34  ** in the tree.  This routine is used to compute a subset of that
    35  ** table consisting of leaves that are descended from a single check-in.
    36  **
    37  ** The closeMode flag determines behavior associated with the "closed"
    38  ** tag:
    39  **
    40  **    closeMode==0       Show all leaves regardless of the "closed" tag.
    41  **
    42  **    closeMode==1       Show only leaves without the "closed" tag.
    43  **
    44  **    closeMode==2       Show only leaves with the "closed" tag.
    45  **
    46  ** The default behavior is to ignore closed leaves (closeMode==0).  To
    47  ** Show all leaves, use closeMode==1.  To show only closed leaves, use
    48  ** closeMode==2.
    49  */
    50  void compute_leaves(int iBase, int closeMode){
    51  
    52    /* Create the LEAVES table if it does not already exist.  Make sure
    53    ** it is empty.
    54    */
    55    db_multi_exec(
    56      "CREATE TEMP TABLE IF NOT EXISTS leaves("
    57      "  rid INTEGER PRIMARY KEY"
    58      ");"
    59      "DELETE FROM leaves;"
    60    );
    61  
    62    if( iBase>0 ){
    63      Bag seen;     /* Descendants seen */
    64      Bag pending;  /* Unpropagated descendants */
    65      Stmt q1;      /* Query to find children of a check-in */
    66      Stmt isBr;    /* Query to check to see if a check-in starts a new branch */
    67      Stmt ins;     /* INSERT statement for a new record */
    68  
    69      /* Initialize the bags. */
    70      bag_init(&seen);
    71      bag_init(&pending);
    72      bag_insert(&pending, iBase);
    73  
    74      /* This query returns all non-branch-merge children of check-in :rid.
    75      **
    76      ** If a child is a merge of a fork within the same branch, it is
    77      ** returned.  Only merge children in different branches are excluded.
    78      */
    79      db_prepare(&q1,
    80        "SELECT cid FROM plink"
    81        " WHERE pid=:rid"
    82        "   AND (isprim"
    83        "        OR coalesce((SELECT value FROM tagxref"
    84                          "   WHERE tagid=%d AND rid=plink.pid), 'trunk')"
    85                   "=coalesce((SELECT value FROM tagxref"
    86                          "   WHERE tagid=%d AND rid=plink.cid), 'trunk'))",
    87        TAG_BRANCH, TAG_BRANCH
    88      );
    89  
    90      /* This query returns a single row if check-in :rid is the first
    91      ** check-in of a new branch.
    92      */
    93      db_prepare(&isBr,
    94         "SELECT 1 FROM tagxref"
    95         " WHERE rid=:rid AND tagid=%d AND tagtype=2"
    96         "   AND srcid>0",
    97         TAG_BRANCH
    98      );
    99  
   100      /* This statement inserts check-in :rid into the LEAVES table.
   101      */
   102      db_prepare(&ins, "INSERT OR IGNORE INTO leaves VALUES(:rid)");
   103  
   104      while( bag_count(&pending) ){
   105        int rid = bag_first(&pending);
   106        int cnt = 0;
   107        bag_remove(&pending, rid);
   108        db_bind_int(&q1, ":rid", rid);
   109        while( db_step(&q1)==SQLITE_ROW ){
   110          int cid = db_column_int(&q1, 0);
   111          if( bag_insert(&seen, cid) ){
   112            bag_insert(&pending, cid);
   113          }
   114          db_bind_int(&isBr, ":rid", cid);
   115          if( db_step(&isBr)==SQLITE_DONE ){
   116            cnt++;
   117          }
   118          db_reset(&isBr);
   119        }
   120        db_reset(&q1);
   121        if( cnt==0 && !is_a_leaf(rid) ){
   122          cnt++;
   123        }
   124        if( cnt==0 ){
   125          db_bind_int(&ins, ":rid", rid);
   126          db_step(&ins);
   127          db_reset(&ins);
   128        }
   129      }
   130      db_finalize(&ins);
   131      db_finalize(&isBr);
   132      db_finalize(&q1);
   133      bag_clear(&pending);
   134      bag_clear(&seen);
   135    }else{
   136      db_multi_exec(
   137        "INSERT INTO leaves"
   138        "  SELECT leaf.rid FROM leaf"
   139      );
   140    }
   141    if( closeMode==1 ){
   142      db_multi_exec(
   143        "DELETE FROM leaves WHERE rid IN"
   144        "  (SELECT leaves.rid FROM leaves, tagxref"
   145        "    WHERE tagxref.rid=leaves.rid "
   146        "      AND tagxref.tagid=%d"
   147        "      AND tagxref.tagtype>0)",
   148        TAG_CLOSED
   149      );
   150    }else if( closeMode==2 ){
   151      db_multi_exec(
   152        "DELETE FROM leaves WHERE rid NOT IN"
   153        "  (SELECT leaves.rid FROM leaves, tagxref"
   154        "    WHERE tagxref.rid=leaves.rid "
   155        "      AND tagxref.tagid=%d"
   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.
   165  */
   166  void compute_ancestors(int rid, int N, int directOnly){
   167    db_multi_exec(
   168      "WITH RECURSIVE "
   169      "  ancestor(rid, mtime) AS ("
   170      "    SELECT %d, mtime FROM event WHERE objid=%d "
   171      "    UNION "
   172      "    SELECT plink.pid, event.mtime"
   173      "      FROM ancestor, plink, event"
   174      "     WHERE plink.cid=ancestor.rid"
   175      "       AND event.objid=plink.pid %s"
   176      "     ORDER BY mtime DESC LIMIT %d"
   177      "  )"
   178      "INSERT INTO ok"
   179      "  SELECT rid FROM ancestor;",
   180      rid, rid, directOnly ? "AND plink.isPrim" : "", N
   181    );
   182  }
   183  
   184  /*
   185  ** Compute all direct ancestors (merge ancestors do not count)
   186  ** for the check-in rid and put them in a table named "ancestor".
   187  ** Label each generation with consecutive integers going backwards
   188  ** in time such that rid has the smallest generation number and the oldest
   189  ** direct ancestor as the largest generation number.
   190  */
   191  void compute_direct_ancestors(int rid){
   192    db_multi_exec(
   193      "CREATE TEMP TABLE IF NOT EXISTS ancestor(rid INTEGER UNIQUE NOT NULL,"
   194                                              " generation INTEGER PRIMARY KEY);"
   195      "DELETE FROM ancestor;"
196 "WITH RECURSIVE g(x,i) AS (" 197 " VALUES(%d,1)" 198 " UNION ALL" 199 " SELECT plink.pid, g.i+1 FROM plink, g" 200 " WHERE plink.cid=g.x AND plink.isprim)" 201 "INSERT INTO ancestor(rid,generation) SELECT x,i FROM g;",
202 rid 203 ); 204 } 205 206 /* 207 ** Compute the "mtime" of the file given whose blob.rid is "fid" that 208 ** is part of check-in "vid". The mtime will be the mtime on vid or 209 ** some ancestor of vid where fid first appears. 210 */ 211 int mtime_of_manifest_file( 212 int vid, /* The check-in that contains fid */ 213 int fid, /* The id of the file whose check-in time is sought */ 214 i64 *pMTime /* Write result here */ 215 ){ 216 static int prevVid = -1; 217 static Stmt q; 218 219 if( prevVid!=vid ){ 220 prevVid = vid; 221 db_multi_exec("DROP TABLE IF EXISTS temp.ok;" 222 "CREATE TEMP TABLE ok(x INTEGER PRIMARY KEY);"); 223 compute_ancestors(vid, 100000000, 1); 224 } 225 db_static_prepare(&q, 226 "SELECT (max(event.mtime)-2440587.5)*86400 FROM mlink, event" 227 " WHERE mlink.mid=event.objid" 228 " AND +mlink.mid IN ok" 229 " AND mlink.fid=:fid"); 230 db_bind_int(&q, ":fid", fid); 231 if( db_step(&q)!=SQLITE_ROW ){ 232 db_reset(&q); 233 return 1; 234 } 235 *pMTime = db_column_int64(&q, 0); 236 db_reset(&q); 237 return 0; 238 } 239 240 /* 241 ** Load the record ID rid and up to N-1 closest descendants into 242 ** the "ok" table. 243 */ 244 void compute_descendants(int rid, int N){ 245 db_multi_exec( 246 "WITH RECURSIVE" 247 " dx(rid,mtime) AS (" 248 " SELECT %d, 0" 249 " UNION" 250 " SELECT plink.cid, plink.mtime FROM dx, plink" 251 " WHERE plink.pid=dx.rid" 252 " ORDER BY 2" 253 " )" 254 "INSERT OR IGNORE INTO ok SELECT rid FROM dx LIMIT %d", 255 rid, N 256 ); 257 } 258 259 /* 260 ** COMMAND: descendants* 261 ** 262 ** Usage: %fossil descendants ?CHECKIN? ?OPTIONS? 263 ** 264 ** Find all leaf descendants of the check-in specified or if the argument 265 ** is omitted, of the check-in currently checked out. 266 ** 267 ** Options: 268 ** -R|--repository FILE Extract info from repository FILE 269 ** -W|--width <num> Width of lines (default is to auto-detect). 270 ** Must be >20 or 0 (= no limit, resulting in a 271 ** single line per entry). 272 ** 273 ** See also: finfo, info, leaves 274 */ 275 void descendants_cmd(void){ 276 Stmt q; 277 int base, width; 278 const char *zWidth; 279 280 db_find_and_open_repository(0,0); 281 zWidth = find_option("width","W",1); 282 if( zWidth ){ 283 width = atoi(zWidth); 284 if( (width!=0) && (width<=20) ){ 285 fossil_fatal("-W|--width value must be >20 or 0"); 286 } 287 }else{ 288 width = -1; 289 } 290 291 /* We should be done with options.. */ 292 verify_all_options(); 293 294 if( g.argc==2 ){ 295 base = db_lget_int("checkout", 0); 296 }else{ 297 base = name_to_typed_rid(g.argv[2], "ci"); 298 } 299 if( base==0 ) return; 300 compute_leaves(base, 0); 301 db_prepare(&q, 302 "%s" 303 " AND event.objid IN (SELECT rid FROM leaves)" 304 " ORDER BY event.mtime DESC", 305 timeline_query_for_tty() 306 ); 307 print_timeline(&q, 0, width, 0); 308 db_finalize(&q); 309 } 310 311 /* 312 ** COMMAND: leaves* 313 ** 314 ** Usage: %fossil leaves ?OPTIONS? 315 ** 316 ** Find leaves of all branches. By default show only open leaves. 317 ** The -a|--all flag causes all leaves (closed and open) to be shown. 318 ** The -c|--closed flag shows only closed leaves. 319 ** 320 ** The --recompute flag causes the content of the "leaf" table in the 321 ** repository database to be recomputed. 322 ** 323 ** Options: 324 ** -a|--all show ALL leaves 325 ** --bybranch order output by branch name 326 ** -c|--closed show only closed leaves 327 ** -m|--multiple show only cases with multiple leaves on a single branch 328 ** --recompute recompute the "leaf" table in the repository DB 329 ** -W|--width <num> Width of lines (default is to auto-detect). Must be 330 ** >39 or 0 (= no limit, resulting in a single line per 331 ** entry). 332 ** 333 ** See also: descendants, finfo, info, branch 334 */ 335 void leaves_cmd(void){ 336 Stmt q; 337 Blob sql; 338 int showAll = find_option("all", "a", 0)!=0; 339 int showClosed = find_option("closed", "c", 0)!=0; 340 int recomputeFlag = find_option("recompute",0,0)!=0; 341 int byBranch = find_option("bybranch",0,0)!=0; 342 int multipleFlag = find_option("multiple","m",0)!=0; 343 const char *zWidth = find_option("width","W",1); 344 char *zLastBr = 0; 345 int n, width; 346 char zLineNo[10]; 347 348 if( multipleFlag ) byBranch = 1; 349 if( zWidth ){ 350 width = atoi(zWidth); 351 if( (width!=0) && (width<=39) ){ 352 fossil_fatal("-W|--width value must be >39 or 0"); 353 } 354 }else{ 355 width = -1; 356 } 357 db_find_and_open_repository(0,0); 358 359 /* We should be done with options.. */ 360 verify_all_options(); 361 362 if( recomputeFlag ) leaf_rebuild(); 363 blob_zero(&sql); 364 blob_append(&sql, timeline_query_for_tty(), -1); 365 if( !multipleFlag ){ 366 /* The usual case - show all leaves */ 367 blob_append_sql(&sql, " AND blob.rid IN leaf"); 368 }else{ 369 /* Show only leaves where two are more occur in the same branch */ 370 db_multi_exec( 371 "CREATE TEMP TABLE openLeaf(rid INTEGER PRIMARY KEY);" 372 "INSERT INTO openLeaf(rid)" 373 " SELECT rid FROM leaf" 374 " WHERE NOT EXISTS(" 375 " SELECT 1 FROM tagxref" 376 " WHERE tagid=%d AND tagtype>0 AND rid=leaf.rid);", 377 TAG_CLOSED 378 ); 379 db_multi_exec( 380 "CREATE TEMP TABLE ambiguousBranch(brname TEXT);" 381 "INSERT INTO ambiguousBranch(brname)" 382 " SELECT (SELECT value FROM tagxref WHERE tagid=%d AND rid=openLeaf.rid)" 383 " FROM openLeaf" 384 " GROUP BY 1 HAVING count(*)>1;", 385 TAG_BRANCH 386 ); 387 db_multi_exec( 388 "CREATE TEMP TABLE ambiguousLeaf(rid INTEGER PRIMARY KEY);\n" 389 "INSERT INTO ambiguousLeaf(rid)\n" 390 " SELECT rid FROM openLeaf\n" 391 " WHERE (SELECT value FROM tagxref WHERE tagid=%d AND rid=openLeaf.rid)" 392 " IN (SELECT brname FROM ambiguousBranch);", 393 TAG_BRANCH 394 ); 395 blob_append_sql(&sql, " AND blob.rid IN ambiguousLeaf"); 396 } 397 if( showClosed ){ 398 blob_append_sql(&sql," AND %z", leaf_is_closed_sql("blob.rid")); 399 }else if( !showAll ){ 400 blob_append_sql(&sql," AND NOT %z", leaf_is_closed_sql("blob.rid")); 401 } 402 if( byBranch ){ 403 db_prepare(&q, "%s ORDER BY nullif(branch,'trunk') COLLATE nocase," 404 " event.mtime DESC", 405 blob_sql_text(&sql)); 406 }else{ 407 db_prepare(&q, "%s ORDER BY event.mtime DESC", blob_sql_text(&sql)); 408 } 409 blob_reset(&sql); 410 n = 0; 411 while( db_step(&q)==SQLITE_ROW ){ 412 const char *zId = db_column_text(&q, 1); 413 const char *zDate = db_column_text(&q, 2); 414 const char *zCom = db_column_text(&q, 3); 415 const char *zBr = db_column_text(&q, 7); 416 char *z; 417 418 if( byBranch && fossil_strcmp(zBr, zLastBr)!=0 ){ 419 fossil_print("*** %s ***\n", zBr); 420 fossil_free(zLastBr); 421 zLastBr = fossil_strdup(zBr); 422 if( multipleFlag ) n = 0; 423 } 424 n++; 425 sqlite3_snprintf(sizeof(zLineNo), zLineNo, "(%d)", n); 426 fossil_print("%6s ", zLineNo); 427 z = mprintf("%s [%S] %s", zDate, zId, zCom); 428 comment_print(z, zCom, 7, width, g.comFmtFlags); 429 fossil_free(z); 430 } 431 fossil_free(zLastBr); 432 db_finalize(&q); 433 } 434 435 /* 436 ** WEBPAGE: leaves 437 ** 438 ** Show leaf check-ins in a timeline. By default only open leaves 439 ** are listed. 440 ** 441 ** A "leaf" is a check-in with no children in the same branch. A 442 ** "closed leaf" is a leaf that has a "closed" tag. An "open leaf" 443 ** is a leaf without a "closed" tag. 444 ** 445 ** Query parameters: 446 ** 447 ** all Show all leaves 448 ** closed Show only closed leaves 449 */ 450 void leaves_page(void){ 451 Blob sql; 452 Stmt q; 453 int showAll = P("all")!=0; 454 int showClosed = P("closed")!=0; 455 456 login_check_credentials(); 457 if( !g.perm.Read ){ login_needed(g.anon.Read); return; } 458 459 if( !showAll ){ 460 style_submenu_element("All", "All", "leaves?all"); 461 } 462 if( !showClosed ){ 463 style_submenu_element("Closed", "Closed", "leaves?closed"); 464 } 465 if( showClosed || showAll ){ 466 style_submenu_element("Open", "Open", "leaves"); 467 } 468 style_header("Leaves"); 469 login_anonymous_available(); 470 #if 0 471 style_sidebox_begin("Nomenclature:", "33%"); 472 @ <ol> 473 @ <li> A <div class="sideboxDescribed">leaf</div> 474 @ is a check-in with no descendants in the same branch.</li> 475 @ <li> An <div class="sideboxDescribed">open leaf</div> 476 @ is a leaf that does not have a "closed" tag 477 @ and is thus assumed to still be in use.</li> 478 @ <li> A <div class="sideboxDescribed">closed leaf</div> 479 @ has a "closed" tag and is thus assumed to 480 @ be historical and no longer in active use.</li> 481 @ </ol> 482 style_sidebox_end(); 483 #endif 484 485 if( showAll ){ 486 @ <h1>All leaves, both open and closed:</h1> 487 }else if( showClosed ){ 488 @ <h1>Closed leaves:</h1> 489 }else{ 490 @ <h1>Open leaves:</h1> 491 } 492 blob_zero(&sql); 493 blob_append(&sql, timeline_query_for_www(), -1); 494 blob_append_sql(&sql, " AND blob.rid IN leaf"); 495 if( showClosed ){ 496 blob_append_sql(&sql," AND %z", leaf_is_closed_sql("blob.rid")); 497 }else if( !showAll ){ 498 blob_append_sql(&sql," AND NOT %z", leaf_is_closed_sql("blob.rid")); 499 } 500 db_prepare(&q, "%s ORDER BY event.mtime DESC", blob_sql_text(&sql)); 501 blob_reset(&sql); 502 www_print_timeline(&q, TIMELINE_LEAFONLY, 0, 0, 0, 0); 503 db_finalize(&q); 504 @ <br /> 505 style_footer(); 506 } 507 508 #if INTERFACE 509 /* Flag parameters to compute_uses_file() */ 510 #define USESFILE_DELETE 0x01 /* Include the check-ins where file deleted */ 511 512 #endif 513 514 515 /* 516 ** Add to table zTab the record ID (rid) of every check-in that contains 517 ** the file fid. 518 */ 519 void compute_uses_file(const char *zTab, int fid, int usesFlags){ 520 Bag seen; 521 Bag pending; 522 Stmt ins; 523 Stmt q; 524 int rid; 525 526 bag_init(&seen); 527 bag_init(&pending); 528 db_prepare(&ins, "INSERT OR IGNORE INTO \"%w\" VALUES(:rid)", zTab); 529 db_prepare(&q, "SELECT mid FROM mlink WHERE fid=%d", fid); 530 while( db_step(&q)==SQLITE_ROW ){ 531 int mid = db_column_int(&q, 0); 532 bag_insert(&pending, mid); 533 bag_insert(&seen, mid); 534 db_bind_int(&ins, ":rid", mid); 535 db_step(&ins); 536 db_reset(&ins); 537 } 538 db_finalize(&q); 539 540 db_prepare(&q, "SELECT mid FROM mlink WHERE pid=%d", fid); 541 while( db_step(&q)==SQLITE_ROW ){ 542 int mid = db_column_int(&q, 0); 543 bag_insert(&seen, mid); 544 if( usesFlags & USESFILE_DELETE ){ 545 db_bind_int(&ins, ":rid", mid); 546 db_step(&ins); 547 db_reset(&ins); 548 } 549 } 550 db_finalize(&q); 551 db_prepare(&q, "SELECT cid FROM plink WHERE pid=:rid AND isprim"); 552 553 while( (rid = bag_first(&pending))!=0 ){ 554 bag_remove(&pending, rid); 555 db_bind_int(&q, ":rid", rid); 556 while( db_step(&q)==SQLITE_ROW ){ 557 int mid = db_column_int(&q, 0); 558 if( bag_find(&seen, mid) ) continue; 559 bag_insert(&seen, mid); 560 bag_insert(&pending, mid); 561 db_bind_int(&ins, ":rid", mid); 562 db_step(&ins); 563 db_reset(&ins); 564 } 565 db_reset(&q); 566 } 567 db_finalize(&q); 568 db_finalize(&ins); 569 bag_clear(&seen); 570 bag_clear(&pending); 571 }