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 }