RFC patchshow-branch: use commit-slab for flag storage

Replace direct accesses to commit->object.flags with the commit-slab mechanism. Introduce `get_commit_flags()` and `set_commit_flags()` to retrieve and update flags, respectively, and include `revision.h` so that the canonical UNINTERESTING definition is used.

Signed-off-by: Meet Soni <meetsoni3017@gmail.com>
---
I'm not entirely sure what the TODO comment meant by storing a pointer to
the "ref name" directly, so I've assumed that the intent was to store
flags (of type int) directly in the commit-slab instead of commit->object.

I've tested these changes using:
 - test suite -- they passed.
 - github ci result -- https://github.com/inosmeet/git/actions/runs/13355488433

The review from Junio that led to this TODO comment [1]:

Ultimately, I'm interested in implementing this change and would appreciate some guidance. Specifically, does this mean I should define the commit-slab using a struct containing both an int and a size, instead of just an int?

[1]: https://lore.kernel.org/git/xmqq36yud9bp.fsf@gitster-ct.c.googlers.com/

 builtin/show-branch.c | 59 +++++++++++++++++++++++++------------------
 1 file changed, 34 insertions(+), 25 deletions(-)

Meet Soni <meetsoni3017@gmail.com> writes:

Ohhhh. I thought people somehow have "refactored" the commit traversal code here to share more with the machinery used by the "log" family of commands, but the change in this patch being contained within the single "show-branch" file indicates that it is not the case, which is good ;-)

And the MAX_REVS limitation has been with us from the very beginning of the "show-branch" command. Lifting it is very good ;-) ;-).

It has been forever since I looked at the code around here the last time, but I suspect that it meant the final mapping the code makes at the output phase from the bit position in the flags bits to which reference the bit (i.e. "I am reachable from that ref") could be omitted if we make the slab entry a set of (interned) refnames.

But I think using a slab whose element is still a bag of bits that is wider than object.flags word is is the most straight-forward way to lift MAX_REVS limitation. If we can leave everything else unchanged, that would be great.

New tests that traverse from more than historical MAX_REVS would be the most interesting.

It is not exactly surprising if the existing tests do not exercise such a case (even though it probably should have been checking that the command refused to accept more than MAX_REVS refs to prevent it from producing garbage results).

If there were such a test to illustrate what happens when too many refs are given, we can demonstrate how the behaviour changes, for the better, with this change ;-)

However ...

... it does not make much sense to use the slab mechanism if we are still limited to bitsizeof(type(flags)). If your "int" is 32 bit, and the command line fed 100 revs, we'd want a flags parameter that can house at least 100 bits passed into the "set" function, and yields the result that can hold at least 100 bits from the "get" function. I'd expect that the interface would be more like

    static int get_commit_flags(struct commit *commit, unsigned flags[]);
    static int set_commit_flags(struct commit *commit, unsigned flags[]);

with a file-scope static variable signaling how many bits we are dealing with (allowing these functions to infer how many words flags[] array has), and the return values from these helpers to indicate success (with 0) and failure (with a negative value). On a 32-bit platform, you'd need at least 4 words in flags[] array to deal with 100 revs. On a 64-bit box, 2 words would be sufficient.

I would imagine that we would need two more helpers

    static int set_flag_bit(unsigned flags[], unsigned n);
    static int get_flag_bit(unsigned flags[], unsigned n);

to query the n-th bit in a set of bits stored in flags[] array.

Thanks.

On Tue, Feb 18, 2025 at 10:40:21AM -0800, Junio C Hamano wrote:

Yeah. I did not see the word "stride" anywhere in your email, so I wanted to provide a further hint: the commit-slab "_with_stride()" variant is meant to handle this kind of arbitrary-sized data. This was part of the original commit-slab implementation in a84b794ad0 (commit-slab: introduce a macro to define a slab for new type, 2013-04-13), but AFAIK we've never actually used it in practice. See that commit for some examples.

-Peff

Jeff King <peff@peff.net> writes:

Wow, after reading the log message of that commit, I realize that we already were considering that one-bit-per-ref needs dynamic scaling and folks must have been thinking hard about it (I do not think the author of the commit alone thought it---it must have been a group effort on the list, which the log message merely explains the motivation behind the design).

Thanks for a pointer ;-)

On Fri, Feb 21, 2025 at 09:15:07AM -0800, Junio C Hamano wrote:

Definitely one of the use cases we discussed early on was using it in paint_down_to_common(). This series:

  https://lore.kernel.org/git/20140625233429.GA20457@sigill.intra.peff.net/

built a fast --contains traversal using the slab stride. I think I stalled because I hadn't convinced myself fully that it covered all cases. You left some very thoughtful comments, but I guess I just never got back around to it.

We ended up taking the early parts (like converting quadratic list access to a prio_queue) as a separate series. I don't know how valuable the rest of it is; there has been a lot of work since then in this area by Stolee, et al. So it's unclear how much it would help now.

But the "bitset" API from:

  https://lore.kernel.org/git/20140625234000.GD23146@sigill.intra.peff.net/

would probably be useful if somebody is trying to help show-branch. It gives you the arbitrary-sized thing you'd store in the slab.

-Peff

On Wed Feb 19, 2025 at 12:10 AM IST, Junio C Hamano wrote:

Agreed. Looking at the code, there seems to be two prequisites for removing MAX_REVS limitation:

- Removing dependency on MAX_REVS for allocating arrays (ref_names,
  revs, etc.)
  (can convert these to heap allocation)

- Removing dependency on MAX_REVS for storing flags (which can be
  achieved by using the slab mechanism and using some kind of bitset
  API or we can use 'bitmap' from ewok.h)

Thanks.