threads / discuss / 46256

Getting first tag per branch for a commit

Subject: Getting first tag per branch for a commit

## tl;dr

4 messages between Jun 25, 2017 and Jun 26, 2017.

replies: 3people: 2as markdown or json

Orgad Shaneh· Jun 25, 2017, 14:06 UTC · lore

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

Junio C Hamano· Jun 25, 2017, 21:54 UTC · re: Orgad Shaneh · lore

Re: Getting first tag per branch for a commit

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".

Junio C Hamano· Jun 25, 2017, 22:22 UTC · re: Junio C Hamano · lore

Re: Getting first tag per branch for a commit

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

Show 14 quoted lines

> 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.

Orgad Shaneh· Jun 26, 2017, 09:37 UTC · re: Junio C Hamano · lore

Re: Getting first tag per branch for a commit

On Mon, Jun 26, 2017 at 12:54 AM, Junio C Hamano <gitster@pobox.com> wrote:

Show 14 quoted lines

> 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? :)

Show 31 quoted lines

> 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