]>
Commit | Line | Data |
---|---|---|
f76412ed JH |
1 | #include <stdlib.h> |
2 | #include "cache.h" | |
3 | #include "commit.h" | |
4 | #include "refs.h" | |
5 | ||
6 | static const char show_branch_usage[] = | |
1f8af483 | 7 | "git-show-branch [--all] [--heads] [--tags] [--more=count | --list | --independent | --merge-base ] [<refs>...]"; |
f76412ed JH |
8 | |
9 | #define UNINTERESTING 01 | |
10 | ||
11 | #define REV_SHIFT 2 | |
12 | #define MAX_REVS 29 /* should not exceed bits_per_int - REV_SHIFT */ | |
13 | ||
14 | static struct commit *interesting(struct commit_list *list) | |
15 | { | |
16 | while (list) { | |
17 | struct commit *commit = list->item; | |
18 | list = list->next; | |
19 | if (commit->object.flags & UNINTERESTING) | |
20 | continue; | |
21 | return commit; | |
22 | } | |
23 | return NULL; | |
24 | } | |
25 | ||
26 | static struct commit *pop_one_commit(struct commit_list **list_p) | |
27 | { | |
28 | struct commit *commit; | |
29 | struct commit_list *list; | |
30 | list = *list_p; | |
31 | commit = list->item; | |
32 | *list_p = list->next; | |
33 | free(list); | |
34 | return commit; | |
35 | } | |
36 | ||
37 | struct commit_name { | |
8e5dd22b JH |
38 | const char *head_name; /* which head's ancestor? */ |
39 | int generation; /* how many parents away from head_name */ | |
f76412ed JH |
40 | }; |
41 | ||
8e5dd22b | 42 | /* Name the commit as nth generation ancestor of head_name; |
f76412ed JH |
43 | * we count only the first-parent relationship for naming purposes. |
44 | */ | |
8e5dd22b | 45 | static void name_commit(struct commit *commit, const char *head_name, int nth) |
f76412ed JH |
46 | { |
47 | struct commit_name *name; | |
48 | if (!commit->object.util) | |
49 | commit->object.util = xmalloc(sizeof(struct commit_name)); | |
50 | name = commit->object.util; | |
8e5dd22b | 51 | name->head_name = head_name; |
f76412ed JH |
52 | name->generation = nth; |
53 | } | |
54 | ||
55 | /* Parent is the first parent of the commit. We may name it | |
8e5dd22b | 56 | * as (n+1)th generation ancestor of the same head_name as |
f76412ed JH |
57 | * commit is nth generation ancestore of, if that generation |
58 | * number is better than the name it already has. | |
59 | */ | |
60 | static void name_parent(struct commit *commit, struct commit *parent) | |
61 | { | |
62 | struct commit_name *commit_name = commit->object.util; | |
63 | struct commit_name *parent_name = parent->object.util; | |
64 | if (!commit_name) | |
65 | return; | |
66 | if (!parent_name || | |
67 | commit_name->generation + 1 < parent_name->generation) | |
8e5dd22b | 68 | name_commit(parent, commit_name->head_name, |
f76412ed JH |
69 | commit_name->generation + 1); |
70 | } | |
71 | ||
8e5dd22b JH |
72 | static int name_first_parent_chain(struct commit *c) |
73 | { | |
74 | int i = 0; | |
75 | while (c) { | |
76 | struct commit *p; | |
77 | if (!c->object.util) | |
78 | break; | |
79 | if (!c->parents) | |
80 | break; | |
81 | p = c->parents->item; | |
82 | if (!p->object.util) { | |
83 | name_parent(c, p); | |
84 | i++; | |
85 | } | |
86 | c = p; | |
87 | } | |
88 | return i; | |
89 | } | |
90 | ||
91 | static void name_commits(struct commit_list *list, | |
92 | struct commit **rev, | |
93 | char **ref_name, | |
94 | int num_rev) | |
95 | { | |
96 | struct commit_list *cl; | |
97 | struct commit *c; | |
98 | int i; | |
99 | ||
100 | /* First give names to the given heads */ | |
101 | for (cl = list; cl; cl = cl->next) { | |
102 | c = cl->item; | |
103 | if (c->object.util) | |
104 | continue; | |
105 | for (i = 0; i < num_rev; i++) { | |
106 | if (rev[i] == c) { | |
107 | name_commit(c, ref_name[i], 0); | |
108 | break; | |
109 | } | |
110 | } | |
111 | } | |
112 | ||
113 | /* Then commits on the first parent ancestry chain */ | |
114 | do { | |
115 | i = 0; | |
116 | for (cl = list; cl; cl = cl->next) { | |
117 | i += name_first_parent_chain(cl->item); | |
118 | } | |
119 | } while (i); | |
120 | ||
121 | /* Finally, any unnamed commits */ | |
122 | do { | |
123 | i = 0; | |
124 | for (cl = list; cl; cl = cl->next) { | |
125 | struct commit_list *parents; | |
126 | struct commit_name *n; | |
127 | int nth; | |
128 | c = cl->item; | |
129 | if (!c->object.util) | |
130 | continue; | |
131 | n = c->object.util; | |
132 | parents = c->parents; | |
133 | nth = 0; | |
134 | while (parents) { | |
135 | struct commit *p = parents->item; | |
136 | char newname[1000]; | |
137 | parents = parents->next; | |
138 | nth++; | |
139 | if (p->object.util) | |
140 | continue; | |
fbaf834d JH |
141 | switch (n->generation) { |
142 | case 0: | |
143 | sprintf(newname, "%s^%d", | |
144 | n->head_name, nth); | |
145 | break; | |
146 | case 1: | |
147 | sprintf(newname, "%s^^%d", | |
148 | n->head_name, nth); | |
149 | break; | |
150 | default: | |
151 | sprintf(newname, "%s~%d^%d", | |
152 | n->head_name, n->generation, | |
153 | nth); | |
154 | } | |
8e5dd22b JH |
155 | name_commit(p, strdup(newname), 0); |
156 | i++; | |
157 | name_first_parent_chain(p); | |
158 | } | |
159 | } | |
160 | } while (i); | |
161 | } | |
162 | ||
f76412ed JH |
163 | static int mark_seen(struct commit *commit, struct commit_list **seen_p) |
164 | { | |
165 | if (!commit->object.flags) { | |
166 | insert_by_date(commit, seen_p); | |
167 | return 1; | |
168 | } | |
169 | return 0; | |
170 | } | |
171 | ||
172 | static void join_revs(struct commit_list **list_p, | |
173 | struct commit_list **seen_p, | |
174 | int num_rev, int extra) | |
175 | { | |
176 | int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1); | |
177 | int all_revs = all_mask & ~((1u << REV_SHIFT) - 1); | |
178 | ||
179 | while (*list_p) { | |
180 | struct commit_list *parents; | |
181 | struct commit *commit = pop_one_commit(list_p); | |
182 | int flags = commit->object.flags & all_mask; | |
f76412ed JH |
183 | int still_interesting = !!interesting(*list_p); |
184 | ||
185 | if (!still_interesting && extra < 0) | |
186 | break; | |
187 | ||
188 | mark_seen(commit, seen_p); | |
189 | if ((flags & all_revs) == all_revs) | |
190 | flags |= UNINTERESTING; | |
191 | parents = commit->parents; | |
192 | ||
193 | while (parents) { | |
194 | struct commit *p = parents->item; | |
195 | int this_flag = p->object.flags; | |
196 | parents = parents->next; | |
f76412ed JH |
197 | if ((this_flag & flags) == flags) |
198 | continue; | |
199 | parse_commit(p); | |
200 | if (mark_seen(p, seen_p) && !still_interesting) | |
201 | extra--; | |
202 | p->object.flags |= flags; | |
203 | insert_by_date(p, list_p); | |
204 | } | |
205 | } | |
206 | } | |
207 | ||
8e5dd22b | 208 | static void show_one_commit(struct commit *commit) |
f76412ed JH |
209 | { |
210 | char pretty[128], *cp; | |
211 | struct commit_name *name = commit->object.util; | |
0a2ba738 JH |
212 | if (commit->object.parsed) |
213 | pretty_print_commit(CMIT_FMT_ONELINE, commit->buffer, ~0, | |
214 | pretty, sizeof(pretty)); | |
215 | else | |
216 | strcpy(pretty, "(unavailable)"); | |
f76412ed JH |
217 | if (!strncmp(pretty, "[PATCH] ", 8)) |
218 | cp = pretty + 8; | |
219 | else | |
220 | cp = pretty; | |
8e5dd22b JH |
221 | if (name && name->head_name) { |
222 | printf("[%s", name->head_name); | |
f76412ed JH |
223 | if (name->generation) |
224 | printf("~%d", name->generation); | |
225 | printf("] "); | |
226 | } | |
227 | puts(cp); | |
228 | } | |
229 | ||
230 | static char *ref_name[MAX_REVS + 1]; | |
231 | static int ref_name_cnt; | |
232 | ||
628894b2 JH |
233 | static int compare_ref_name(const void *a_, const void *b_) |
234 | { | |
235 | const char * const*a = a_, * const*b = b_; | |
236 | return strcmp(*a, *b); | |
237 | } | |
238 | ||
239 | static void sort_ref_range(int bottom, int top) | |
240 | { | |
241 | qsort(ref_name + bottom, top - bottom, sizeof(ref_name[0]), | |
242 | compare_ref_name); | |
243 | } | |
244 | ||
f76412ed JH |
245 | static int append_ref(const char *refname, const unsigned char *sha1) |
246 | { | |
247 | struct commit *commit = lookup_commit_reference_gently(sha1, 1); | |
248 | if (!commit) | |
249 | return 0; | |
250 | if (MAX_REVS < ref_name_cnt) { | |
251 | fprintf(stderr, "warning: ignoring %s; " | |
252 | "cannot handle more than %d refs", | |
253 | refname, MAX_REVS); | |
254 | return 0; | |
255 | } | |
256 | ref_name[ref_name_cnt++] = strdup(refname); | |
257 | ref_name[ref_name_cnt] = NULL; | |
258 | return 0; | |
259 | } | |
260 | ||
261 | static int append_head_ref(const char *refname, const unsigned char *sha1) | |
262 | { | |
263 | if (strncmp(refname, "refs/heads/", 11)) | |
264 | return 0; | |
628894b2 | 265 | return append_ref(refname + 11, sha1); |
f76412ed JH |
266 | } |
267 | ||
268 | static int append_tag_ref(const char *refname, const unsigned char *sha1) | |
269 | { | |
270 | if (strncmp(refname, "refs/tags/", 10)) | |
271 | return 0; | |
272 | return append_ref(refname + 5, sha1); | |
273 | } | |
274 | ||
275 | static void snarf_refs(int head, int tag) | |
276 | { | |
628894b2 JH |
277 | if (head) { |
278 | int orig_cnt = ref_name_cnt; | |
f76412ed | 279 | for_each_ref(append_head_ref); |
628894b2 JH |
280 | sort_ref_range(orig_cnt, ref_name_cnt); |
281 | } | |
282 | if (tag) { | |
283 | int orig_cnt = ref_name_cnt; | |
f76412ed | 284 | for_each_ref(append_tag_ref); |
628894b2 JH |
285 | sort_ref_range(orig_cnt, ref_name_cnt); |
286 | } | |
f76412ed JH |
287 | } |
288 | ||
289 | static int rev_is_head(char *head_path, int headlen, | |
290 | char *name, | |
291 | unsigned char *head_sha1, unsigned char *sha1) | |
292 | { | |
293 | int namelen; | |
294 | if ((!head_path[0]) || memcmp(head_sha1, sha1, 20)) | |
295 | return 0; | |
296 | namelen = strlen(name); | |
297 | if ((headlen < namelen) || | |
298 | memcmp(head_path + headlen - namelen, name, namelen)) | |
299 | return 0; | |
300 | if (headlen == namelen || | |
301 | head_path[headlen - namelen - 1] == '/') | |
302 | return 1; | |
303 | return 0; | |
304 | } | |
305 | ||
306 | static int show_merge_base(struct commit_list *seen, int num_rev) | |
307 | { | |
308 | int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1); | |
309 | int all_revs = all_mask & ~((1u << REV_SHIFT) - 1); | |
2f0f8b71 | 310 | int exit_status = 1; |
f76412ed JH |
311 | |
312 | while (seen) { | |
313 | struct commit *commit = pop_one_commit(&seen); | |
314 | int flags = commit->object.flags & all_mask; | |
315 | if (!(flags & UNINTERESTING) && | |
316 | ((flags & all_revs) == all_revs)) { | |
317 | puts(sha1_to_hex(commit->object.sha1)); | |
2f0f8b71 JH |
318 | exit_status = 0; |
319 | commit->object.flags |= UNINTERESTING; | |
f76412ed JH |
320 | } |
321 | } | |
2f0f8b71 | 322 | return exit_status; |
f76412ed JH |
323 | } |
324 | ||
1f8af483 JH |
325 | static int show_independent(struct commit **rev, |
326 | int num_rev, | |
327 | char **ref_name, | |
328 | unsigned int *rev_mask) | |
329 | { | |
330 | int i; | |
331 | ||
332 | for (i = 0; i < num_rev; i++) { | |
333 | struct commit *commit = rev[i]; | |
334 | unsigned int flag = rev_mask[i]; | |
335 | ||
336 | if (commit->object.flags == flag) | |
337 | puts(sha1_to_hex(commit->object.sha1)); | |
338 | commit->object.flags |= UNINTERESTING; | |
339 | } | |
340 | return 0; | |
341 | } | |
342 | ||
f76412ed JH |
343 | int main(int ac, char **av) |
344 | { | |
345 | struct commit *rev[MAX_REVS], *commit; | |
346 | struct commit_list *list = NULL, *seen = NULL; | |
1f8af483 | 347 | unsigned int rev_mask[MAX_REVS]; |
f76412ed JH |
348 | int num_rev, i, extra = 0; |
349 | int all_heads = 0, all_tags = 0; | |
8e5dd22b | 350 | int all_mask, all_revs, shown_merge_point; |
f76412ed JH |
351 | char head_path[128]; |
352 | int head_path_len; | |
353 | unsigned char head_sha1[20]; | |
354 | int merge_base = 0; | |
1f8af483 | 355 | int independent = 0; |
f5e375c9 | 356 | char **label; |
f76412ed | 357 | |
076b2324 JH |
358 | setup_git_directory(); |
359 | ||
f76412ed JH |
360 | while (1 < ac && av[1][0] == '-') { |
361 | char *arg = av[1]; | |
362 | if (!strcmp(arg, "--all")) | |
363 | all_heads = all_tags = 1; | |
364 | else if (!strcmp(arg, "--heads")) | |
365 | all_heads = 1; | |
366 | else if (!strcmp(arg, "--tags")) | |
367 | all_tags = 1; | |
368 | else if (!strcmp(arg, "--more")) | |
369 | extra = 1; | |
1f8af483 JH |
370 | else if (!strcmp(arg, "--list")) |
371 | extra = -1; | |
372 | else if (!strncmp(arg, "--more=", 7)) | |
f76412ed | 373 | extra = atoi(arg + 7); |
f76412ed JH |
374 | else if (!strcmp(arg, "--merge-base")) |
375 | merge_base = 1; | |
1f8af483 JH |
376 | else if (!strcmp(arg, "--independent")) |
377 | independent = 1; | |
f76412ed JH |
378 | else |
379 | usage(show_branch_usage); | |
380 | ac--; av++; | |
381 | } | |
382 | ac--; av++; | |
383 | ||
1f8af483 JH |
384 | /* Only one of these is allowed */ |
385 | if (1 < independent + merge_base + (extra != 0)) | |
386 | usage(show_branch_usage); | |
387 | ||
f76412ed JH |
388 | if (all_heads + all_tags) |
389 | snarf_refs(all_heads, all_tags); | |
390 | ||
391 | while (0 < ac) { | |
392 | unsigned char revkey[20]; | |
393 | if (get_sha1(*av, revkey)) | |
394 | die("bad sha1 reference %s", *av); | |
395 | append_ref(*av, revkey); | |
396 | ac--; av++; | |
397 | } | |
398 | ||
399 | /* If still no revs, then add heads */ | |
400 | if (!ref_name_cnt) | |
401 | snarf_refs(1, 0); | |
402 | ||
403 | for (num_rev = 0; ref_name[num_rev]; num_rev++) { | |
404 | unsigned char revkey[20]; | |
1f8af483 | 405 | unsigned int flag = 1u << (num_rev + REV_SHIFT); |
f76412ed JH |
406 | |
407 | if (MAX_REVS <= num_rev) | |
408 | die("cannot handle more than %d revs.", MAX_REVS); | |
409 | if (get_sha1(ref_name[num_rev], revkey)) | |
410 | usage(show_branch_usage); | |
411 | commit = lookup_commit_reference(revkey); | |
412 | if (!commit) | |
413 | die("cannot find commit %s (%s)", | |
414 | ref_name[num_rev], revkey); | |
415 | parse_commit(commit); | |
f76412ed JH |
416 | mark_seen(commit, &seen); |
417 | ||
418 | /* rev#0 uses bit REV_SHIFT, rev#1 uses bit REV_SHIFT+1, | |
419 | * and so on. REV_SHIFT bits from bit 0 are used for | |
420 | * internal bookkeeping. | |
421 | */ | |
1f8af483 JH |
422 | commit->object.flags |= flag; |
423 | if (commit->object.flags == flag) | |
424 | insert_by_date(commit, &list); | |
f76412ed JH |
425 | rev[num_rev] = commit; |
426 | } | |
1f8af483 JH |
427 | for (i = 0; i < num_rev; i++) |
428 | rev_mask[i] = rev[i]->object.flags; | |
429 | ||
430 | if (0 <= extra) | |
431 | join_revs(&list, &seen, num_rev, extra); | |
f76412ed JH |
432 | |
433 | head_path_len = readlink(".git/HEAD", head_path, sizeof(head_path)-1); | |
434 | if ((head_path_len < 0) || get_sha1("HEAD", head_sha1)) | |
435 | head_path[0] = 0; | |
436 | else | |
437 | head_path[head_path_len] = 0; | |
438 | ||
439 | if (merge_base) | |
440 | return show_merge_base(seen, num_rev); | |
441 | ||
1f8af483 JH |
442 | if (independent) |
443 | return show_independent(rev, num_rev, ref_name, rev_mask); | |
444 | ||
445 | /* Show list; --more=-1 means list-only */ | |
c9d023b2 | 446 | if (1 < num_rev || extra < 0) { |
f76412ed JH |
447 | for (i = 0; i < num_rev; i++) { |
448 | int j; | |
449 | int is_head = rev_is_head(head_path, | |
450 | head_path_len, | |
451 | ref_name[i], | |
452 | head_sha1, | |
453 | rev[i]->object.sha1); | |
1f8af483 JH |
454 | if (extra < 0) |
455 | printf("%c [%s] ", | |
456 | is_head ? '*' : ' ', ref_name[i]); | |
457 | else { | |
458 | for (j = 0; j < i; j++) | |
459 | putchar(' '); | |
460 | printf("%c [%s] ", | |
461 | is_head ? '*' : '!', ref_name[i]); | |
462 | } | |
8e5dd22b | 463 | show_one_commit(rev[i]); |
f76412ed | 464 | } |
1f8af483 JH |
465 | if (0 <= extra) { |
466 | for (i = 0; i < num_rev; i++) | |
467 | putchar('-'); | |
468 | putchar('\n'); | |
469 | } | |
f5e375c9 | 470 | } |
1f8af483 JH |
471 | if (extra < 0) |
472 | exit(0); | |
f5e375c9 | 473 | |
8e5dd22b JH |
474 | /* Sort topologically */ |
475 | sort_in_topological_order(&seen); | |
476 | ||
477 | /* Give names to commits */ | |
478 | name_commits(seen, rev, ref_name, num_rev); | |
479 | ||
480 | all_mask = ((1u << (REV_SHIFT + num_rev)) - 1); | |
481 | all_revs = all_mask & ~((1u << REV_SHIFT) - 1); | |
482 | shown_merge_point = 0; | |
483 | ||
f76412ed JH |
484 | while (seen) { |
485 | struct commit *commit = pop_one_commit(&seen); | |
486 | int this_flag = commit->object.flags; | |
8e5dd22b | 487 | int is_merge_point = (this_flag & all_revs) == all_revs; |
f5e375c9 JH |
488 | static char *obvious[] = { "" }; |
489 | ||
8e5dd22b JH |
490 | if (is_merge_point) |
491 | shown_merge_point = 1; | |
492 | ||
f5e375c9 JH |
493 | if (1 < num_rev) { |
494 | for (i = 0; i < num_rev; i++) | |
495 | putchar((this_flag & (1u << (i + REV_SHIFT))) | |
496 | ? '+' : ' '); | |
497 | putchar(' '); | |
498 | } | |
8e5dd22b | 499 | show_one_commit(commit); |
f5e375c9 JH |
500 | if (num_rev == 1) |
501 | label = obvious; | |
8e5dd22b JH |
502 | if (shown_merge_point && is_merge_point) |
503 | if (--extra < 0) | |
504 | break; | |
f76412ed JH |
505 | } |
506 | return 0; | |
507 | } |