show-branch uses commit->object.flags to store per-branch reachability bits, one bit per branch starting at REV_SHIFT. The flags word has only a fixed number of available bits, limiting the number of branches that can be shown simultaneously.
Convert the per-branch bits to a dedicated commit-slab using uint64_t as the element type, initialized with a stride via init_commit_rev_flags_with_stride(). Keep the UNINTERESTING bit in object.flags where it belongs, as it is used for revision walking and does not need to be in the per-branch slab. With UNINTERESTING removed from the slab, REV_SHIFT becomes 0 and all 64 bits of uint64_t are available for branch tracking.
Add helper functions get_rev_flags_ptr(), peek_rev_flags_ptr(), has_any_rev_flags(), or_rev_flag_bit(), test_rev_flag_bit(), has_all_rev_flags(), has_only_rev_flag_bit(), and has_subset_rev_flags() to encapsulate per-bit slab access cleanly. Use has_only_rev_flag_bit() in show_independent() to preserve the original semantics: a commit is independent only if reachable from exactly one tip. Use has_subset_rev_flags() in join_revs() to skip parents whose flags already include all of the current commit's flags, avoiding redundant propagation and queue thrashing in dense histories.
Fix join_revs() to correctly propagate UNINTERESTING to parents using a local commit_is_merge_base variable, without smudging the commit itself, matching the original behavior.
Remove the hardcoded MAX_REVS limit entirely by dynamically growing the ref_name[] array with ALLOC_GROW, and allocating rev[] and reflog_msg[] dynamically after all refs are collected. Compute flags_stride at runtime as (ref_name_cnt + 63) / 64 so the slab supports an arbitrary number of branches.
Remove the hardcoded branch limit from documentation since there is no longer a fixed maximum. Add tests to verify show-branch works correctly with more than 27 branches. Include revision.h for the shared UNINTERESTING definition.
Signed-off-by: Gatla Vishweshwar Reddy <gatlavishweshwarreddy26@gmail.com>
---
I took time to read through the code carefully before sending this.
Show changes to 3 files +179 −91
Documentation/git-show-branch.adoc, builtin/show-branch.c, t/t3202-show-branch.sh
diff --git a/Documentation/git-show-branch.adoc b/Documentation/git-show-branch.adoc
index 7e86d54a24..3df107b7f4 100644
--- a/Documentation/git-show-branch.adoc
+++ b/Documentation/git-show-branch.adoc
@@ -22,8 +22,6 @@ Shows the commit ancestry graph starting from the commits named
with <rev>s or <glob>s (or all refs under refs/heads
and/or refs/tags) semi-visually.
-It cannot show more than 26 branches and commits at a time.
-
It uses `showbranch.default` multi-valued configuration items if
no <rev> or <glob> is given on the command line.
diff --git a/builtin/show-branch.c b/builtin/show-branch.c
index f02831b085..47c3819c07 100644
--- a/builtin/show-branch.c
+++ b/builtin/show-branch.c
@@ -9,6 +9,7 @@
#include "hex.h"
#include "pretty.h"
#include "refs.h"
+#include "revision.h"
#include "color.h"
#include "strvec.h"
#include "object-name.h"
@@ -35,15 +36,11 @@ static enum git_colorbool showbranch_use_color = GIT_COLOR_UNKNOWN;
static struct strvec default_args = STRVEC_INIT;
/*
- * TODO: convert this use of commit->object.flags to commit-slab
- * instead to store a pointer to ref name directly. Then use the same
- * UNINTERESTING definition from revision.h here.
+ * TODO: store a pointer to ref name directly in the commit-slab
+ * instead, and use the UNINTERESTING definition from revision.h
+ * here once that is done.
*/
-#define UNINTERESTING 01
-
-#define REV_SHIFT 2
-#define MAX_REVS (FLAG_BITS - REV_SHIFT) /* should not exceed bits_per_int - REV_SHIFT */
-
+#define REV_SHIFT 0
#define DEFAULT_REFLOG 4
static const char *get_color_code(int idx)
@@ -79,11 +76,87 @@ struct commit_name {
define_commit_slab(commit_name_slab, struct commit_name *);
static struct commit_name_slab name_slab;
+define_commit_slab(commit_rev_flags, uint64_t);
+static struct commit_rev_flags rev_flags_slab;
+static int flags_stride; /* number of uint64_t words per commit */
+
static struct commit_name *commit_to_name(struct commit *commit)
{
return *commit_name_slab_at(&name_slab, commit);
}
+static uint64_t *get_rev_flags_ptr(struct commit *commit)
+{
+ return commit_rev_flags_at(&rev_flags_slab, commit);
+}
+
+static uint64_t *peek_rev_flags_ptr(struct commit *commit)
+{
+ return commit_rev_flags_peek(&rev_flags_slab, commit);
+}
+
+static int has_any_rev_flags(struct commit *commit)
+{
+ uint64_t *f = peek_rev_flags_ptr(commit);
+ int i;
+ if (!f)
+ return 0;
+ for (i = 0; i < flags_stride; i++)
+ if (f[i])
+ return 1;
+ return 0;
+}
+
+static void or_rev_flag_bit(struct commit *commit, int branch)
+{
+ get_rev_flags_ptr(commit)[branch / 64] |= UINT64_C(1) << (branch % 64);
+}
+
+static int test_rev_flag_bit(struct commit *commit, int branch)
+{
+ uint64_t *f = peek_rev_flags_ptr(commit);
+ return f && !!(f[branch / 64] & (UINT64_C(1) << (branch % 64)));
+}
+
+static int has_all_rev_flags(struct commit *commit, int num_rev)
+{
+ int i;
+ for (i = 0; i < num_rev; i++)
+ if (!test_rev_flag_bit(commit, i))
+ return 0;
+ return 1;
+}
+
+static int has_only_rev_flag_bit(struct commit *commit, int branch)
+{
+ uint64_t *f = peek_rev_flags_ptr(commit);
+ int i;
+ if (!f)
+ return 0;
+ for (i = 0; i < flags_stride; i++) {
+ uint64_t expected = (i == branch / 64)
+ ? (UINT64_C(1) << (branch % 64))
+ : 0;
+ if (f[i] != expected)
+ return 0;
+ }
+ return 1;
+}
+
+static int has_subset_rev_flags(struct commit *src, struct commit *dst)
+{
+ uint64_t *s = peek_rev_flags_ptr(src);
+ uint64_t *d = peek_rev_flags_ptr(dst);
+ int i;
+ if (!s)
+ return 1; /* src has no flags, trivially a subset */
+ if (!d)
+ return 0; /* dst has no flags but src has some */
+ for (i = 0; i < flags_stride; i++)
+ if (s[i] & ~d[i])
+ return 0;
+ return 1;
+}
/* Name the commit as nth generation ancestor of head_name;
* we count only the first-parent relationship for naming purposes.
@@ -215,7 +288,7 @@ static void name_commits(struct commit_list *list,
static int mark_seen(struct commit *commit, struct commit_list **seen_p)
{
- if (!commit->object.flags) {
+ if (!has_any_rev_flags(commit)) {
commit_list_insert(commit, seen_p);
return 1;
}
@@ -226,39 +299,41 @@ static void join_revs(struct prio_queue *queue,
struct commit_list **seen_p,
int num_rev, int extra)
{
- int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
- int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
-
while (queue->nr) {
struct commit_list *parents;
int still_interesting = !!interesting(queue);
struct commit *commit = prio_queue_peek(queue);
bool get_pending = true;
- int flags = commit->object.flags & all_mask;
if (!still_interesting && extra <= 0)
break;
mark_seen(commit, seen_p);
- if ((flags & all_revs) == all_revs)
- flags |= UNINTERESTING;
- parents = commit->parents;
-
- while (parents) {
- struct commit *p = parents->item;
- int this_flag = p->object.flags;
- parents = parents->next;
- if ((this_flag & flags) == flags)
- continue;
- repo_parse_commit(the_repository, p);
- if (mark_seen(p, seen_p) && !still_interesting)
- extra--;
- p->object.flags |= flags;
- if (get_pending)
- prio_queue_replace(queue, p);
- else
- prio_queue_put(queue, p);
- get_pending = false;
+ {
+ int commit_is_merge_base = has_all_rev_flags(commit, num_rev);
+ parents = commit->parents;
+
+ while (parents) {
+ struct commit *p = parents->item;
+ int _b;
+ parents = parents->next;
+ if (has_subset_rev_flags(commit, p) &&
+ (!commit_is_merge_base || (p->object.flags & UNINTERESTING)))
+ continue;
+ repo_parse_commit(the_repository, p);
+ if (mark_seen(p, seen_p) && !still_interesting)
+ extra--;
+ for (_b = 0; _b < num_rev; _b++)
+ if (test_rev_flag_bit(commit, _b))
+ or_rev_flag_bit(p, _b);
+ if (commit_is_merge_base)
+ p->object.flags |= UNINTERESTING;
+ if (get_pending)
+ prio_queue_replace(queue, p);
+ else
+ prio_queue_put(queue, p);
+ get_pending = false;
+ }
}
if (get_pending)
prio_queue_get(queue);
@@ -278,7 +353,7 @@ static void join_revs(struct prio_queue *queue,
struct commit *c = s->item;
struct commit_list *parents;
- if (((c->object.flags & all_revs) != all_revs) &&
+ if (!has_all_rev_flags(c, num_rev) &&
!(c->object.flags & UNINTERESTING))
continue;
@@ -335,8 +410,9 @@ static void show_one_commit(struct commit *commit, int no_name)
strbuf_release(&pretty);
}
-static char *ref_name[MAX_REVS + 1];
+static char **ref_name;
static int ref_name_cnt;
+static int ref_name_alloc;
static const char *find_digit_prefix(const char *s, int *v)
{
@@ -409,12 +485,7 @@ static int append_ref(const char *refname, const struct object_id *oid,
if (!strcmp(refname, ref_name[i]))
return 0;
}
- if (MAX_REVS <= ref_name_cnt) {
- warning(Q_("ignoring %s; cannot handle more than %d ref",
- "ignoring %s; cannot handle more than %d refs",
- MAX_REVS), refname, MAX_REVS);
- return 0;
- }
+ ALLOC_GROW(ref_name, ref_name_cnt + 2, ref_name_alloc);
ref_name[ref_name_cnt++] = xstrdup(refname);
ref_name[ref_name_cnt] = NULL;
return 0;
@@ -511,15 +582,12 @@ static int rev_is_head(const char *head, const char *name)
static int show_merge_base(const struct commit_list *seen, int num_rev)
{
- int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
- int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
int exit_status = 1;
for (const struct commit_list *s = seen; s; s = s->next) {
struct commit *commit = s->item;
- int flags = commit->object.flags & all_mask;
- if (!(flags & UNINTERESTING) &&
- ((flags & all_revs) == all_revs)) {
+ if (!(commit->object.flags & UNINTERESTING) &&
+ has_all_rev_flags(commit, num_rev)) {
puts(oid_to_hex(&commit->object.oid));
exit_status = 0;
commit->object.flags |= UNINTERESTING;
@@ -528,17 +596,13 @@ static int show_merge_base(const struct commit_list *seen, int num_rev)
return exit_status;
}
-static int show_independent(struct commit **rev,
- int num_rev,
- unsigned int *rev_mask)
+static int show_independent(struct commit **rev, int num_rev)
{
int i;
for (i = 0; i < num_rev; i++) {
struct commit *commit = rev[i];
- unsigned int flag = rev_mask[i];
-
- if (commit->object.flags == flag)
+ if (has_only_rev_flag_bit(commit, i))
puts(oid_to_hex(&commit->object.oid));
commit->object.flags |= UNINTERESTING;
}
@@ -560,8 +624,7 @@ static void append_one_rev(const char *av)
match_ref_slash = count_slashes(av);
refs_for_each_ref(get_main_ref_store(the_repository),
append_matching_ref, NULL);
- if (saved_matches == ref_name_cnt &&
- ref_name_cnt < MAX_REVS)
+ if (saved_matches == ref_name_cnt)
error(_("no matching refs with %s"), av);
sort_ref_range(saved_matches, ref_name_cnt);
return;
@@ -603,13 +666,12 @@ static int omit_in_dense(struct commit *commit, struct commit **rev, int n)
* Otherwise, if it is a merge that is reachable from only one
* tip, it is not that interesting.
*/
- int i, flag, count;
+ int i, count;
for (i = 0; i < n; i++)
if (rev[i] == commit)
return 0;
- flag = commit->object.flags;
for (i = count = 0; i < n; i++) {
- if (flag & (1u << (i + REV_SHIFT)))
+ if (test_rev_flag_bit(commit, i))
count++;
}
if (count == 1)
@@ -644,14 +706,12 @@ int cmd_show_branch(int ac,
const char *prefix,
struct repository *repo UNUSED)
{
- struct commit *rev[MAX_REVS], *commit;
- char *reflog_msg[MAX_REVS] = {0};
+ struct commit **rev = NULL, *commit;
+ char **reflog_msg = NULL;
struct commit_list *seen = NULL;
struct prio_queue queue = { compare_commits_by_commit_date };
- unsigned int rev_mask[MAX_REVS];
int num_rev, i, extra = 0;
int all_heads = 0, all_remotes = 0;
- int all_mask, all_revs;
enum rev_sort_order sort_order = REV_SORT_IN_GRAPH_ORDER;
char *head;
struct object_id head_oid;
@@ -713,8 +773,6 @@ int cmd_show_branch(int ac,
const char **args_copy = NULL;
int ret;
- init_commit_name_slab(&name_slab);
-
repo_config(the_repository, git_show_branch_config, NULL);
/* If nothing is specified, try the default first */
@@ -728,6 +786,8 @@ int cmd_show_branch(int ac,
show_branch_usage, PARSE_OPT_STOP_AT_NON_OPTION);
if (all_heads)
all_remotes = 1;
+ if (reflog)
+ CALLOC_ARRAY(reflog_msg, reflog + 1);
if (extra || reflog) {
/* "listing" mode is incompatible with
@@ -754,7 +814,6 @@ int cmd_show_branch(int ac,
/* If nothing is specified, show all branches by default */
if (ac <= topics && all_heads + all_remotes == 0)
all_heads = 1;
-
if (reflog) {
struct object_id oid;
char *ref;
@@ -777,11 +836,6 @@ int cmd_show_branch(int ac,
}
if (ac != 1)
die(_("--reflog option needs one branch name"));
-
- if (MAX_REVS < reflog)
- die(Q_("only %d entry can be shown at one time.",
- "only %d entries can be shown at one time.",
- MAX_REVS), MAX_REVS);
if (!repo_dwim_ref(the_repository, *av, strlen(*av), &oid,
&ref, 0))
die(_("no such ref %s"), *av);
@@ -868,14 +922,18 @@ int cmd_show_branch(int ac,
goto out;
}
+ flags_stride = (ref_name_cnt + 63) / 64;
+ if (!flags_stride)
+ flags_stride = 1;
+ init_commit_rev_flags_with_stride(&rev_flags_slab, flags_stride);
+ CALLOC_ARRAY(rev, ref_name_cnt);
+ if (!reflog_msg)
+ CALLOC_ARRAY(reflog_msg, ref_name_cnt);
+
for (num_rev = 0; ref_name[num_rev]; num_rev++) {
struct object_id revkey;
- unsigned int flag = 1u << (num_rev + REV_SHIFT);
+ int first_seen;
- if (MAX_REVS <= num_rev)
- die(Q_("cannot handle more than %d rev.",
- "cannot handle more than %d revs.",
- MAX_REVS), MAX_REVS);
if (repo_get_oid(the_repository, ref_name[num_rev], &revkey))
die(_("'%s' is not a valid ref."), ref_name[num_rev]);
commit = lookup_commit_reference(the_repository, &revkey);
@@ -885,17 +943,15 @@ int cmd_show_branch(int ac,
repo_parse_commit(the_repository, commit);
mark_seen(commit, &seen);
- /* rev#0 uses bit REV_SHIFT, rev#1 uses bit REV_SHIFT+1,
- * and so on. REV_SHIFT bits from bit 0 are used for
- * internal bookkeeping.
+ /* rev#0 uses bit 0, rev#1 uses bit 1,
+ * and so on. All bits are available for branch tracking.
*/
- commit->object.flags |= flag;
- if (commit->object.flags == flag)
+ first_seen = !has_any_rev_flags(commit);
+ or_rev_flag_bit(commit, num_rev);
+ if (first_seen)
prio_queue_put(&queue, commit);
rev[num_rev] = commit;
}
- for (i = 0; i < num_rev; i++)
- rev_mask[i] = rev[i]->object.flags;
if (0 <= extra)
join_revs(&queue, &seen, num_rev, extra);
@@ -908,7 +964,7 @@ int cmd_show_branch(int ac,
}
if (independent) {
- ret = show_independent(rev, num_rev, rev_mask);
+ ret = show_independent(rev, num_rev);
goto out;
}
@@ -958,13 +1014,9 @@ int cmd_show_branch(int ac,
if (!sha1_name && !no_name)
name_commits(seen, rev, ref_name, num_rev);
- all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
- all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
-
for (struct commit_list *l = seen; l; l = l->next) {
struct commit *commit = l->item;
- int this_flag = commit->object.flags;
- int is_merge_point = ((this_flag & all_revs) == all_revs);
+ int is_merge_point = has_all_rev_flags(commit, num_rev);
shown_merge_point |= is_merge_point;
@@ -973,14 +1025,14 @@ int cmd_show_branch(int ac,
commit->parents->next);
if (topics &&
!is_merge_point &&
- (this_flag & (1u << REV_SHIFT)))
+ test_rev_flag_bit(commit, 0))
continue;
if (!sparse && is_merge &&
omit_in_dense(commit, rev, num_rev))
continue;
for (i = 0; i < num_rev; i++) {
int mark;
- if (!(this_flag & (1u << (i + REV_SHIFT))))
+ if (!test_rev_flag_bit(commit, i))
mark = ' ';
else if (is_merge)
mark = '-';
@@ -1006,10 +1058,16 @@ int cmd_show_branch(int ac,
ret = 0;
out:
- for (size_t i = 0; i < ARRAY_SIZE(reflog_msg); i++)
+ for (i = 0; i < ref_name_cnt; i++)
free(reflog_msg[i]);
+ free(reflog_msg);
+ free(rev);
+ for (i = 0; i < ref_name_cnt; i++)
+ free(ref_name[i]);
+ free(ref_name);
commit_list_free(seen);
clear_prio_queue(&queue);
+ clear_commit_rev_flags(&rev_flags_slab);
free(args_copy);
free(head);
return ret;
diff --git a/t/t3202-show-branch.sh b/t/t3202-show-branch.sh
index a1139f79e2..d04f642998 100755
--- a/t/t3202-show-branch.sh
+++ b/t/t3202-show-branch.sh
@@ -283,4 +283,36 @@ test_expect_success '--reflog handles missing reflog' '
test_must_be_empty actual
'
+test_expect_success 'show-branch with 30 branches succeeds' '
+ git checkout initial &&
+ for i in $(test_seq 11 30)
+ do
+ git checkout -b branch$i initial &&
+ test_commit --no-tag branch$i || return 1
+ done &&
+ git show-branch $(git for-each-ref \
+ --sort=version:refname \
+ --format="%(refname:strip=2)" \
+ "refs/heads/branch*") >actual &&
+ test_line_count -ge 30 actual
+'
+
+test_expect_success 'show-branch --independent with 30 branches' '
+ git show-branch --independent $(git for-each-ref \
+ --sort=version:refname \
+ --format="%(refname:strip=2)" \
+ "refs/heads/branch*") >actual &&
+ test_line_count -ge 30 actual
+'
+
+test_expect_success 'show-branch --merge-base with 30 branches' '
+ git rev-parse initial >expect &&
+ git show-branch --merge-base $(git for-each-ref \
+ --sort=version:refname \
+ --format="%(refname:strip=2)" \
+ "refs/heads/branch*") >actual &&
+ test_cmp expect actual
+'
+
+
test_done