Getting first tag per branch for a commit

Getting first tag per branch for a commit

[Orgad Shaneh]

Hi,

git describe --tags <commit> gives me the first tag that includes this commit.

git tag --contains <commit> shows all the tags that contain the commit.

git branch -a --contains <commit> shows the branches that include this commit.

What I'd like to have is a way to tell the first tag per branch (or
per merge) that the commit appeared on.

I'll use an example from the Git repository. Let's pick commit
32b8c581ec which was first introduced in v2.9.3.

git describe --tags will only show v2.9.3

git tag --contains shows the following list:
v2.10.0
v2.10.0-rc0
v2.10.0-rc1
v2.10.0-rc2
v2.10.1
v2.10.2
v2.10.3
v2.11.0
v2.11.0-rc0
v2.11.0-rc1
v2.11.0-rc2
v2.11.0-rc3
v2.11.1
v2.11.2
v2.12.0
v2.12.0-rc0
v2.12.0-rc1
v2.12.0-rc2
v2.12.1
v2.12.2
v2.12.3
v2.13.0
v2.13.0-rc0
v2.13.0-rc1
v2.13.0-rc2
v2.13.1
v2.13.2
v2.9.3
v2.9.4

What really interests me as a user is the "first in the series" tag
for each version. What I'd expect is:
v2.10.0-rc0
v2.9.3

and I can conclude that if it appeared in 2.9.3 then 2.9.4 also has
it, and if it's in 2.10.0-rc0 then all the following versions (2.10.x
and up) include it.

I think that this can be done by filtering out tags that are connected
to already listed tags by first-parent link.

Is there a way to achieve this kind of "simplified contained in" list?

Related: https://bugs.chromium.org/p/gerrit/issues/detail?id=4331

- Orgad

Re: Getting first tag per branch for a commit

[Junio C Hamano]

Orgad Shaneh <orgads@gmail.com> writes:

> What I'd like to have is a way to tell the first tag per branch (or
> per merge) that the commit appeared on.

> I think that this can be done by filtering out tags that are connected
> to already listed tags by first-parent link.

Yes.  When one tag can be reached by another tag, then the former is
definitely an earlier tag than the latter.

A trivial way to compute it would require O(n^2) invocations of "git
merge-base --is-ancestor".  Alternatively, I think you can perhaps
use "git merge-base --independent".

Having said that, one thing to keep in mind is that a single "first
tag" may not exist at all.

Consider this topology:

          o---X-------.                topic
         /     \       \
 ---o---o---o-------o---N---S---o---   maint
     \           \   \           \
      o---o---o---M---o---o---T---o--- master

where a topic branch was forked from the maintenance track, which is
periodically merged to the master branch.  That topic branch has the
commit of interest, X, which first gets merged to the master branch
at merge M, which eventually gets tagged as T (i.e. a new feature
release).  But (wall-clock-wise) after merge M is made and the
change is tested in the context of the master branch, but before the
release T happens, the topic may be merged down to the maintenance
track at merge N.  Then eventually the tip of the maintenance track
is tagged as S (i.e. a maintenance release).

Topologically, T and S cannot be compared and they both contain X,
so the question "what is the first tag on 'master' that has commit
X?" does not have a single unique answer.  Both S and T are eligible.

You could define various heuristics to tiebreak among these tags.
You may be tempted to compare timestamps of S and T.  If they were
equal, then you might want to compare timestamps of M and N.

But you'd need to accept that fundamentally there may not be a
single "first tag".

Re: Getting first tag per branch for a commit

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Orgad Shaneh <orgads@gmail.com> writes:
>
>> What I'd like to have is a way to tell the first tag per branch (or
>> per merge) that the commit appeared on.
>
>> I think that this can be done by filtering out tags that are connected
>> to already listed tags by first-parent link.
>
> Yes.  When one tag can be reached by another tag, then the former is
> definitely an earlier tag than the latter.
>
> A trivial way to compute it would require O(n^2) invocations of "git
> merge-base --is-ancestor".  Alternatively, I think you can perhaps
> use "git merge-base --independent".

Ah, forget the latter.  "independent" is about solving the opposite
use case--it is to cull the ones that can be reached by other tips.

Re: Getting first tag per branch for a commit

[Orgad Shaneh]

On Mon, Jun 26, 2017 at 12:54 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Orgad Shaneh <orgads@gmail.com> writes:
>
>> What I'd like to have is a way to tell the first tag per branch (or
>> per merge) that the commit appeared on.
>
>> I think that this can be done by filtering out tags that are connected
>> to already listed tags by first-parent link.
>
> Yes.  When one tag can be reached by another tag, then the former is
> definitely an earlier tag than the latter.
>
> A trivial way to compute it would require O(n^2) invocations of "git
> merge-base --is-ancestor".  Alternatively, I think you can perhaps
> use "git merge-base --independent".

I think this feature needs to be implemented in Git (by a flag to git describe).
O(n^2) is way too much when you have 20,000 tags.

Unfortunately, I don't feel qualified for implementing it myself. Does anyone
else volunteer? :)

> Having said that, one thing to keep in mind is that a single "first
> tag" may not exist at all.
>
> Consider this topology:
>
>           o---X-------.                topic
>          /     \       \
>  ---o---o---o-------o---N---S---o---   maint
>      \           \   \           \
>       o---o---o---M---o---o---T---o--- master
>
> where a topic branch was forked from the maintenance track, which is
> periodically merged to the master branch.  That topic branch has the
> commit of interest, X, which first gets merged to the master branch
> at merge M, which eventually gets tagged as T (i.e. a new feature
> release).  But (wall-clock-wise) after merge M is made and the
> change is tested in the context of the master branch, but before the
> release T happens, the topic may be merged down to the maintenance
> track at merge N.  Then eventually the tip of the maintenance track
> is tagged as S (i.e. a maintenance release).
>
> Topologically, T and S cannot be compared and they both contain X,
> so the question "what is the first tag on 'master' that has commit
> X?" does not have a single unique answer.  Both S and T are eligible.
>
> You could define various heuristics to tiebreak among these tags.
> You may be tempted to compare timestamps of S and T.  If they were
> equal, then you might want to compare timestamps of M and N.
>
> But you'd need to accept that fundamentally there may not be a
> single "first tag".

I accept that. Anyway, this looks to me like a corner case, and I don't mind
having several tags from the same branch for this case.

- Orgad