Subject: Re: [PATCH v2 12/13] name-rev: eliminate recursion in name_rev()

From: SZEDER Gábor <[email-masked]>
Date: Mon, 9 Dec 2019 13:22:46 +0100

On Wed, Nov 27, 2019 at 09:57:51AM -0800, Jonathan Tan wrote:
> > Note that this slightly changes the order of lines in the output of
> > 'git name-rev --all', usually swapping two lines every 35 lines in
> > git.git or every 150 lines in linux.git.  This shouldn't matter in
> > practice, because the output has always been unordered anyway.
> 
> I didn't verify that the changing of order is fine, but other than that,
> this patch looks great.

FWIW, the sorted output is the same (well, it would clearly be a bug
if it wasn't):

  $ .../v2.24.0/bin/git name-rev --all |sort >orig.sorted
  $ git name-rev --all |sort >new.sorted
  $ diff -u orig.sorted new.sorted 
  $ echo $?
  0

I still don't understand where that slight change in the order of
lines comes from, though I didn't really tried to understand it, to be
honest...

> > This patch is best viewed with '--ignore-all-space'.
> 
> Thanks for the tip! I ended up unindenting the loop to see the changes
> better, but I should have done this instead.

At one point I was considering an additional noop preparatory commit
that would have added one more indentation level to name_rev()'s for
loop.  That patch would have an empty diff with '--ignore-all-spaces',
of course, and the diff of the patch eliminating the recursion would
look sensible by default.
Would that have been worth it?  Dunno.

> > -static void name_rev(struct commit *commit,
> > +static void name_rev(struct commit *start_commit,
> >  		const char *tip_name, timestamp_t taggerdate,
> >  		int from_tag)
> 
> There are many changes from tip_name to name->tip_name in this function
> that mean that tip_name is no longer used within this function. Should
> this cleanup have been done in one of the earlier patches?

I've added a new patch to do that.

> Apart from that, overall, this patch looks like a straightforward good
> change. When we have a parent, instead of immediately calling name_rev()
> recursively, we first add it to an array, and then (in reverse order)
> add it to a priority queue which is actually used as a LIFO stack.

Yeah, 'commit->parents' is a single linked list, so we can't iterate
over it backwards, hence that interim array.