1 /*
2 ** Copyright (c) 2011 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 manage the "leaf" table of the
19 ** repository.
20 **
21 ** The LEAF table contains the rids for all leaves in the check-in DAG.
22 ** A leaf is a check-in that has no children in the same branch.
23 */
24 #include "config.h"
25 #include "leaf.h"
26 #include <assert.h>
27
28
29 /*
30 ** Return true if the check-in with RID=rid is a leaf.
31 **
32 ** A leaf has no children in the same branch.
33 */
is_a_leaf(int rid)34 int is_a_leaf(int rid){
35 int rc;
36 static const char zSql[] =
37 @ SELECT 1 FROM plink
38 @ WHERE pid=%d
39 @ AND coalesce((SELECT value FROM tagxref
40 @ WHERE tagid=%d AND rid=plink.pid), 'trunk')
41 @ =coalesce((SELECT value FROM tagxref
42 @ WHERE tagid=%d AND rid=plink.cid), 'trunk')
43 ;
44 rc = db_int(0, zSql /*works-like:"%d,%d,%d"*/,
45 rid, TAG_BRANCH, TAG_BRANCH);
46 return rc==0;
47 }
48
49 /*
50 ** Count the number of primary non-branch children for the given check-in.
51 **
52 ** A primary child is one where the parent is the primary parent, not
53 ** a merge parent. A "leaf" is a node that has zero children of any
54 ** kind. This routine counts only primary children.
55 **
56 ** A non-branch child is one which is on the same branch as the parent.
57 */
count_nonbranch_children(int pid)58 int count_nonbranch_children(int pid){
59 int nNonBranch = 0;
60 static Stmt q;
61 static const char zSql[] =
62 @ SELECT count(*) FROM plink
63 @ WHERE pid=:pid AND isprim
64 @ AND coalesce((SELECT value FROM tagxref
65 @ WHERE tagid=%d AND rid=plink.pid), 'trunk')
66 @ =coalesce((SELECT value FROM tagxref
67 @ WHERE tagid=%d AND rid=plink.cid), 'trunk')
68 ;
69 db_static_prepare(&q, zSql /*works-like: "%d,%d"*/, TAG_BRANCH, TAG_BRANCH);
70 db_bind_int(&q, ":pid", pid);
71 if( db_step(&q)==SQLITE_ROW ){
72 nNonBranch = db_column_int(&q, 0);
73 }
74 db_reset(&q);
75 return nNonBranch;
76 }
77
78
79 /*
80 ** Recompute the entire LEAF table.
81 **
82 ** This can be expensive (5 seconds or so) for a really large repository.
83 ** So it is only done for things like a rebuild.
84 */
leaf_rebuild(void)85 void leaf_rebuild(void){
86 db_multi_exec(
87 "DELETE FROM leaf;"
88 "INSERT OR IGNORE INTO leaf"
89 " SELECT cid FROM plink"
90 " EXCEPT"
91 " SELECT pid FROM plink"
92 " WHERE coalesce((SELECT value FROM tagxref"
93 " WHERE tagid=%d AND rid=plink.pid),'trunk')"
94 " == coalesce((SELECT value FROM tagxref"
95 " WHERE tagid=%d AND rid=plink.cid),'trunk')",
96 TAG_BRANCH, TAG_BRANCH
97 );
98 }
99
100 /*
101 ** A bag of check-ins whose leaf status needs to be checked.
102 */
103 static Bag needToCheck;
104
105 /*
106 ** Check to see if check-in "rid" is a leaf and either add it to the LEAF
107 ** table if it is, or remove it if it is not.
108 */
leaf_check(int rid)109 void leaf_check(int rid){
110 static Stmt checkIfLeaf;
111 static Stmt addLeaf;
112 static Stmt removeLeaf;
113 int rc;
114
115 db_static_prepare(&checkIfLeaf,
116 "SELECT 1 FROM plink"
117 " WHERE pid=:rid"
118 " AND coalesce((SELECT value FROM tagxref"
119 " WHERE tagid=%d AND rid=:rid),'trunk')"
120 " == coalesce((SELECT value FROM tagxref"
121 " WHERE tagid=%d AND rid=plink.cid),'trunk');",
122 TAG_BRANCH, TAG_BRANCH
123 );
124 db_bind_int(&checkIfLeaf, ":rid", rid);
125 rc = db_step(&checkIfLeaf);
126 db_reset(&checkIfLeaf);
127 if( rc==SQLITE_ROW ){
128 db_static_prepare(&removeLeaf, "DELETE FROM leaf WHERE rid=:rid");
129 db_bind_int(&removeLeaf, ":rid", rid);
130 db_step(&removeLeaf);
131 db_reset(&removeLeaf);
132 }else{
133 db_static_prepare(&addLeaf, "INSERT OR IGNORE INTO leaf VALUES(:rid)");
134 db_bind_int(&addLeaf, ":rid", rid);
135 db_step(&addLeaf);
136 db_reset(&addLeaf);
137 }
138 }
139
140 /*
141 ** Return an SQL expression (stored in memory obtained from fossil_malloc())
142 ** that is true if the SQL variable named "zVar" contains the rid with
143 ** a CLOSED tag. In other words, return true if the leaf is closed.
144 **
145 ** The result can be prefaced with a NOT operator to get all leaves that
146 ** are open.
147 */
leaf_is_closed_sql(const char * zVar)148 char *leaf_is_closed_sql(const char *zVar){
149 return mprintf(
150 "EXISTS(SELECT 1 FROM tagxref AS tx"
151 " WHERE tx.rid=%s"
152 " AND tx.tagid=%d"
153 " AND tx.tagtype>0)",
154 zVar, TAG_CLOSED
155 );
156 }
157
158 /*
159 ** Returns true if vid refers to a closed leaf, else false. vid is
160 ** assumed to refer to a manifest, but this function does not verify
161 ** that.
162 */
leaf_is_closed(int vid)163 int leaf_is_closed(int vid){
164 return db_exists("SELECT 1 FROM tagxref"
165 " WHERE tagid=%d AND rid=%d AND tagtype>0",
166 TAG_CLOSED, vid);
167 }
168
169 /*
170 ** Schedule a leaf check for "rid" and its parents.
171 */
leaf_eventually_check(int rid)172 void leaf_eventually_check(int rid){
173 static Stmt parentsOf;
174
175 db_static_prepare(&parentsOf,
176 "SELECT pid FROM plink WHERE cid=:rid AND pid>0"
177 );
178 db_bind_int(&parentsOf, ":rid", rid);
179 bag_insert(&needToCheck, rid);
180 while( db_step(&parentsOf)==SQLITE_ROW ){
181 bag_insert(&needToCheck, db_column_int(&parentsOf, 0));
182 }
183 db_reset(&parentsOf);
184 }
185
186 /*
187 ** Do all pending leaf checks.
188 */
leaf_do_pending_checks(void)189 void leaf_do_pending_checks(void){
190 int rid;
191 for(rid=bag_first(&needToCheck); rid; rid=bag_next(&needToCheck,rid)){
192 leaf_check(rid);
193 }
194 bag_clear(&needToCheck);
195 }
196
197 /*
198 ** If check-in rid is an open-leaf and there exists another
199 ** open leaf on the same branch, then return 1.
200 **
201 ** If check-in rid is not an open leaf, or if it is the only open leaf
202 ** on its branch, then return 0.
203 */
leaf_ambiguity(int rid)204 int leaf_ambiguity(int rid){
205 int rc; /* Result */
206 char zVal[30];
207 if( !is_a_leaf(rid) ) return 0;
208 sqlite3_snprintf(sizeof(zVal), zVal, "%d", rid);
209 rc = db_exists(
210 "SELECT 1 FROM leaf"
211 " WHERE NOT %z"
212 " AND rid<>%d"
213 " AND (SELECT value FROM tagxref WHERE tagid=%d AND rid=leaf.rid)="
214 " (SELECT value FROM tagxref WHERE tagid=%d AND rid=%d)"
215 " AND NOT %z",
216 leaf_is_closed_sql(zVal), rid, TAG_BRANCH, TAG_BRANCH, rid,
217 leaf_is_closed_sql("leaf.rid"));
218 return rc;
219 }
220
221 /*
222 ** If check-in rid is an open-leaf and there exists another open leaf
223 ** on the same branch, then print a detailed warning showing all open
224 ** leaves on that branch.
225 */
leaf_ambiguity_warning(int rid,int currentCkout)226 int leaf_ambiguity_warning(int rid, int currentCkout){
227 char *zBr;
228 Stmt q;
229 int n = 0;
230 Blob msg;
231 if( leaf_ambiguity(rid)==0 ) return 0;
232 zBr = db_text(0, "SELECT value FROM tagxref WHERE tagid=%d AND rid=%d",
233 TAG_BRANCH, rid);
234 if( zBr==0 ) zBr = fossil_strdup("trunk");
235 blob_init(&msg, 0, 0);
236 blob_appendf(&msg, "WARNING: multiple open leaf check-ins on %s:", zBr);
237 db_prepare(&q,
238 "SELECT"
239 " (SELECT uuid FROM blob WHERE rid=leaf.rid),"
240 " (SELECT datetime(mtime,toLocal()) FROM event WHERE objid=leaf.rid),"
241 " leaf.rid"
242 " FROM leaf"
243 " WHERE (SELECT value FROM tagxref WHERE tagid=%d AND rid=leaf.rid)=%Q"
244 " AND NOT %z"
245 " ORDER BY 2 DESC",
246 TAG_BRANCH, zBr, leaf_is_closed_sql("leaf.rid")
247 );
248 while( db_step(&q)==SQLITE_ROW ){
249 blob_appendf(&msg, "\n (%d) %s [%S]%s",
250 ++n, db_column_text(&q,1), db_column_text(&q,0),
251 db_column_int(&q,2)==currentCkout ? " (current)" : "");
252 }
253 db_finalize(&q);
254 fossil_warning("%s",blob_str(&msg));
255 blob_reset(&msg);
256 return 1;
257 }
258
259 /*
260 ** COMMAND: test-leaf-ambiguity
261 **
262 ** Usage: %fossil NAME ...
263 **
264 ** Resolve each name on the command line and call leaf_ambiguity_warning()
265 ** for each resulting RID.
266 */
leaf_ambiguity_warning_test(void)267 void leaf_ambiguity_warning_test(void){
268 int i;
269 int rid;
270 int rc;
271 db_find_and_open_repository(0,0);
272 verify_all_options();
273 for(i=2; i<g.argc; i++){
274 char *zUuid;
275 rid = name_to_typed_rid(g.argv[i], "ci");
276 zUuid = db_text(0, "SELECT uuid FROM blob WHERE rid=%d", rid);
277 fossil_print("%s (rid=%d) %S ", g.argv[i], rid, zUuid ? zUuid : "(none)");
278 fossil_free(zUuid);
279 rc = leaf_ambiguity_warning(rid, rid);
280 if( rc==0 ) fossil_print(" ok\n");
281 }
282 }
283