[BUG?] 'git describe seen'?

[BUG?] 'git describe seen'?

[Junio C Hamano]

This does not seem a new problem at all, as v2.10.0 thru more recent
versions of "git describe" seem to give me the same answer.

Anyway, I am seeing a curious symptom.

$ git rev-list --count v2.31.0..seen
716
$ git rev-list --count v2.31.1..seen
687

The above means that 'seen' is closer to v2.31.1 than v2.31.0; there
are fewer commits that are not in v2.31.1 that are in 'seen', than
commits that are not in v2.31.0 that are in 'seen'.  

That is naturally expected.

$ git rev-list --count v2.31.0..v2.31.1
29

And that difference of 29 matches the difference, which is 716 - 687.

But here is what is puzzling.

$ git describe seen
v2.31.0-716-g7b65b53281

$ git rev-list --first-parent master..seen |
  while read v
  do
	d=$(git describe $v)
	echo $v $d
	case "$d" in v2.31.1-*) break ;; esac
  done
7b65b53281ae06ee25dd47dead4062125eb54427 v2.31.0-716-g7b65b53281
eec14f0fec886c909a29d63a94537df5a62be618 v2.31.0-714-geec14f0fec
...
103835562c64abef2319995716230f92092f87af v2.31.0-569-g103835562c
d4324831d9152b16e091646e22a6e03423a59c93 v2.31.1-516-gd4324831d9

Is there something tricky about the topic merged at 10383556 (Merge
branch 'jh/rfc-builtin-fsmonitor' into seen, 2021-04-17) to confuse
the counting done in "git describe"?

$ git log --first-parent --oneline master..103835562^2
14d50074ff t7527: test status with untracked-cache and fsmonitor--daemon
07dbff70ce p7519: add fsmonitor--daemon
436807f77a t7527: create test for fsmonitor--daemon
c826602412 fsmonitor: force update index when fsmonitor token advances
aaaf17ce60 fsmonitor--daemon: use a cookie file to sync with file system
71a0e07d79 fsmonitor--daemon:: introduce client delay for testing
9aedb0f1ea fsmonitor--daemon: periodically truncate list of modified files
d4ae16b416 fsmonitor--daemon: implement handle_client callback
94f826fd48 fsmonitor-fs-listen-macos: implement FSEvent listener on MacOS
25663103ea fsmonitor-fs-listen-macos: add macos header files for FSEvent
e504205db7 fsmonitor-fs-listen-win32: implement FSMonitor backend on Windows
5e207d2af6 fsmonitor--daemon: create token-based changed path cache
42f493472f fsmonitor--daemon: define token-ids
082b8085d3 fsmonitor--daemon: add pathname classification
d4f4c59e56 fsmonitor--daemon: implement daemon command options
aec39650b5 fsmonitor-fs-listen-macos: stub in backend for MacOS
100cb9e8ad fsmonitor-fs-listen-win32: stub in backend for Windows
404d7dbdb6 fsmonitor--daemon: implement client command options
1f2d717bd6 fsmonitor--daemon: add a built-in fsmonitor daemon
4b10913cfe fsmonitor: introduce `core.useBuiltinFSMonitor` to call the daemon via IPC
867611645c config: FSMonitor is repository-specific
6e74370ce4 fsmonitor-ipc: create client routines for git-fsmonitor--daemon
ff338b5790 Merge branch 'jh/simple-ipc' into jh/rfc-builtin-fsmonitor

Re: [BUG?] 'git describe seen'?

[SZEDER Gábor]

On Sat, Apr 17, 2021 at 04:45:59PM -0700, Junio C Hamano wrote:
> This does not seem a new problem at all, as v2.10.0 thru more recent
> versions of "git describe" seem to give me the same answer.
> 
> Anyway, I am seeing a curious symptom.
> 
> $ git rev-list --count v2.31.0..seen
> 716
> $ git rev-list --count v2.31.1..seen
> 687
> 
> The above means that 'seen' is closer to v2.31.1 than v2.31.0; there
> are fewer commits that are not in v2.31.1 that are in 'seen', than
> commits that are not in v2.31.0 that are in 'seen'.  
> 
> That is naturally expected.
> 
> $ git rev-list --count v2.31.0..v2.31.1
> 29
> 
> And that difference of 29 matches the difference, which is 716 - 687.
> 
> But here is what is puzzling.
> 
> $ git describe seen
> v2.31.0-716-g7b65b53281
> 
> $ git rev-list --first-parent master..seen |
>   while read v
>   do
> 	d=$(git describe $v)
> 	echo $v $d
> 	case "$d" in v2.31.1-*) break ;; esac
>   done
> 7b65b53281ae06ee25dd47dead4062125eb54427 v2.31.0-716-g7b65b53281
> eec14f0fec886c909a29d63a94537df5a62be618 v2.31.0-714-geec14f0fec
> ...
> 103835562c64abef2319995716230f92092f87af v2.31.0-569-g103835562c
> d4324831d9152b16e091646e22a6e03423a59c93 v2.31.1-516-gd4324831d9
> 
> Is there something tricky about the topic merged at 10383556 (Merge
> branch 'jh/rfc-builtin-fsmonitor' into seen, 2021-04-17) to confuse
> the counting done in "git describe"?

Subsequent merges with identical timestamps can easily confuse 'git
describe', I wonder whether this is another symptom of the issue
reported at:

  https://public-inbox.org/git/20191008123156.GG11529@szeder.dev/

Re: [BUG?] 'git describe seen'?

[SZEDER Gábor]

On Sun, Apr 18, 2021 at 10:21:04AM +0200, SZEDER Gábor wrote:
> On Sat, Apr 17, 2021 at 04:45:59PM -0700, Junio C Hamano wrote:
> > This does not seem a new problem at all, as v2.10.0 thru more recent
> > versions of "git describe" seem to give me the same answer.
> > 
> > Anyway, I am seeing a curious symptom.
> > 
> > $ git rev-list --count v2.31.0..seen
> > 716
> > $ git rev-list --count v2.31.1..seen
> > 687
> > 
> > The above means that 'seen' is closer to v2.31.1 than v2.31.0; there
> > are fewer commits that are not in v2.31.1 that are in 'seen', than
> > commits that are not in v2.31.0 that are in 'seen'.  
> > 
> > That is naturally expected.
> > 
> > $ git rev-list --count v2.31.0..v2.31.1
> > 29
> > 
> > And that difference of 29 matches the difference, which is 716 - 687.
> > 
> > But here is what is puzzling.
> > 
> > $ git describe seen
> > v2.31.0-716-g7b65b53281
> > 
> > $ git rev-list --first-parent master..seen |
> >   while read v
> >   do
> > 	d=$(git describe $v)
> > 	echo $v $d
> > 	case "$d" in v2.31.1-*) break ;; esac
> >   done
> > 7b65b53281ae06ee25dd47dead4062125eb54427 v2.31.0-716-g7b65b53281
> > eec14f0fec886c909a29d63a94537df5a62be618 v2.31.0-714-geec14f0fec
> > ...
> > 103835562c64abef2319995716230f92092f87af v2.31.0-569-g103835562c
> > d4324831d9152b16e091646e22a6e03423a59c93 v2.31.1-516-gd4324831d9
> > 
> > Is there something tricky about the topic merged at 10383556 (Merge
> > branch 'jh/rfc-builtin-fsmonitor' into seen, 2021-04-17) to confuse
> > the counting done in "git describe"?
> 
> Subsequent merges with identical timestamps can easily confuse 'git
> describe', I wonder whether this is another symptom of the issue
> reported at:
> 
>   https://public-inbox.org/git/20191008123156.GG11529@szeder.dev/

That is not the only issue playing a role here, though.

'git describe --debug ...' shows a handful of candidate tags sorted
(primarily) by their depth counted from the to-be-described commit:

  $ git describe --debug origin/seen
  describe origin/seen
  No exact match on refs or tags, searching to describe
   annotated        716 v2.31.0
   annotated        708 v2.31.1
   annotated        733 v2.31.0-rc2
   annotated        755 v2.31.0-rc1
   annotated        818 v2.31.0-rc0
   annotated        895 v2.30.2
   annotated        897 v2.29.3
   annotated        899 v2.28.1
   annotated        901 v2.27.1
   annotated        903 v2.26.3
  traversed 3768 commits
  more than 10 tags found; listed 10 most recent
  gave up search at 42ce4c7930ff494136256554cbed730857084c70
  v2.31.0-716-g7b65b53281

Notice two issues with this output:

  - v2.31.0's depth is ok, but v2.31.1's is wrong:

      $ git rev-list --count v2.31.0..origin/seen
      716
      $ git rev-list --count v2.31.1..origin/seen
      687

  - The order of v2.31.0 and v2.31.1 is clearly wrong.

    I think this is because of the following code snippet from
    builtin/describe.c:describe_commit():

        QSORT(all_matches, match_cnt, compare_pt);

        if (gave_up_on) {
                commit_list_insert_by_date(gave_up_on, &list);
                seen_commits--;
        }
        seen_commits += finish_depth_computation(&list, &all_matches[0]);
        free_commit_list(list);

    I.e. we sort based on depth before calling
    finish_depth_computation(), which doesn't look right...  Looking
    at the depths before sorting shows that v2.31.1's depth is the
    same (708), but v2.31.0's depth is only 696 instead of 716.  Now,
    while this explains why those two tags are listed in the wrong
    order, it is still troubling that v2.31.0's depth is lower that
    v2.31.1's.

    Switching the order of finish_depth_computation() and QSORT() does
    fix thier order based on their depth, but, alas, those depths are
    still wrong:

      $ ./bin-wrappers/git describe --debug origin/seen
      describe origin/seen
      No exact match on refs or tags, searching to describe
       annotated        696 v2.31.0
       annotated        729 v2.31.1
       annotated        733 v2.31.0-rc2
       annotated        755 v2.31.0-rc1
       annotated        818 v2.31.0-rc0
       annotated        895 v2.30.2
       annotated        897 v2.29.3
       annotated        899 v2.28.1
       annotated        901 v2.27.1
       annotated        903 v2.26.3
      traversed 3768 commits
      more than 10 tags found; listed 10 most recent
      gave up search at 42ce4c7930ff494136256554cbed730857084c70
      v2.31.0-696-g7b65b53281

    However, switching the order of finish_depth_computation() and
    QSORT() might be wrong in itself: finish_depth_computation() was
    introduced in 1b600e659a (Compute accurate distances in
    git-describe before output., 2007-01-27), which states [1] the
    following in its commit message:

      We can easily reduce the total number of commits that need to be
      walked at the end by stopping as soon as all of the commits in the
      commit queue are flagged as being merged into the already selected
      best possible tag.

    But which candidate is that "best possible tag"?  The one whose
    depth is the lowest, so we do have to sort before calling
    finish_depth_computation() (or, strictly speaking, we don't have
    to sort, we only have to find the candidate with the lowest
    depth).

At this point I call it quits, because I don't think we can't talk
about accurate depth at all without first fixing the issue I linked in
my previous message.


[1] 1b600e659a also states the following:

      This means we can simply finish
      counting out the revisions still in our commit queue to present
      the accurate distance at the end.  The number of commits remaining
      in the commit queue is probably less than the number of commits
      already traversed, so finishing out the count is not likely to take
      very long. 

   Looking at the 'seen_commits' variable shows that in this
   particular case we traverse 905 commits before calling
   finish_depth_computation(), which then traverses an additional
   3768 - 905 = 2863 commits, i.e. the assumption in 1b600e659a might
   not hold.

Re: [BUG?] 'git describe seen'?

[René Scharfe]

Am 18.04.21 um 01:45 schrieb Junio C Hamano:
> This does not seem a new problem at all, as v2.10.0 thru more recent
> versions of "git describe" seem to give me the same answer.
>
> Anyway, I am seeing a curious symptom.
>
> $ git rev-list --count v2.31.0..seen
> 716
> $ git rev-list --count v2.31.1..seen
> 687
>
> The above means that 'seen' is closer to v2.31.1 than v2.31.0; there
> are fewer commits that are not in v2.31.1 that are in 'seen', than
> commits that are not in v2.31.0 that are in 'seen'.
>
> That is naturally expected.
>
> $ git rev-list --count v2.31.0..v2.31.1
> 29
>
> And that difference of 29 matches the difference, which is 716 - 687.
>
> But here is what is puzzling.
>
> $ git describe seen
> v2.31.0-716-g7b65b53281
>
> $ git rev-list --first-parent master..seen |
>   while read v
>   do
> 	d=$(git describe $v)
> 	echo $v $d
> 	case "$d" in v2.31.1-*) break ;; esac
>   done
> 7b65b53281ae06ee25dd47dead4062125eb54427 v2.31.0-716-g7b65b53281
> eec14f0fec886c909a29d63a94537df5a62be618 v2.31.0-714-geec14f0fec
> ...
> 103835562c64abef2319995716230f92092f87af v2.31.0-569-g103835562c
> d4324831d9152b16e091646e22a6e03423a59c93 v2.31.1-516-gd4324831d9
>
> Is there something tricky about the topic merged at 10383556 (Merge
> branch 'jh/rfc-builtin-fsmonitor' into seen, 2021-04-17) to confuse
> the counting done in "git describe"?

You get the expected result if you only allow one or two candidates, but
adding more of them changes that somehow.  The patch below shows the
values used for sorting the candidates; the numbers in the existing
debug output are a bit confusing because they show the finished depth
for the first entry and the raw ones for the rest:

   $ git describe --debug 103835562c --candidates=2
   describe 103835562c
   No exact match on refs or tags, searching to describe
         472        1 v2.31.1
         481        2 v2.31.0
    annotated        582 v2.31.1
    annotated        481 v2.31.0
   traversed 3621 commits
   more than 2 tags found; listed 2 most recent
   gave up search at 13d7ab6b5d7929825b626f050b62a11241ea4945
   v2.31.1-582-g103835562c

   $ git describe --debug 103835562c --candidates=3
   describe 103835562c
   No exact match on refs or tags, searching to describe
         496        2 v2.31.0
         499        1 v2.31.1
         524        3 v2.31.0-rc2
    annotated        569 v2.31.0
    annotated        499 v2.31.1
    annotated        524 v2.31.0-rc2
   traversed 3621 commits
   more than 3 tags found; listed 3 most recent
   gave up search at f01623b2c9d14207e497b21ebc6b3ec4afaf4b46
   v2.31.0-569-g103835562c

Why do the depths change if we add another candidate?  I guess that's
because this loop can increase the depth of each candidate for
unflagged commits:

                for (cur_match = 0; cur_match < match_cnt; cur_match++) {
                        struct possible_tag *t = &all_matches[cur_match];
                        if (!(c->object.flags & t->flag_within))
                                t->depth++;
                }

Adding v2.31.0-rc2 increases the depth of v2.31.0 from 481 by 15 to 496
and of v2.31.1 from 472 by 27 to 499.  We can print the IDs of those
unflagged objects like this:

                for (cur_match = 0; cur_match < match_cnt; cur_match++) {
                        struct possible_tag *t = &all_matches[cur_match];
                        if (!(c->object.flags & t->flag_within)) {
                                t->depth++;
				if (match_cnt == 3)
					fprintf(stderr, "%s %s\n",
						oid_to_hex(&c->object.oid),
						t->name->path);
			}
                }

We can then get the commits that increase the depth of v2.31.0, but not
of v2.31.1, when we add the third candidate, v2.31.0-rc2, using
something like this:

   $ awk '$2 == "v2.31.0" {print $1}' err |
     grep -v -f <(awk '$2 == "v2.31.1" {print $1}' err) |
     git show --oneline --no-patch --stdin

   68b5c3aa48 Makefile: update 'make fuzz-all' docs to reflect modern clang
   241b5d3ebe fix xcalloc() argument order
   93c3d297b5 git mv foo FOO ; git mv foo bar gave an assert

And vice versa, the fifteen commits that increase the depth of v2.31.1,
but not of v2.31.0:

   834845142d l10n: de.po: Update German translation for Git v2.31.0
   408985d301 l10n: pt_PT: add Portuguese translations part 1
   1369935987 l10n: vi.po(5104t): for git v2.31.0 l10n round 2
   b0adcc311b l10n: es: 2.31.0 round 2
   c21ad4d941 l10n: Add translation team info
   8c4abfb8be l10n: start Indonesian translation
   8278f87022 l10n: zh_TW.po: v2.31.0 round 2 (15 untranslated)
   2f176de687 l10n: bg.po: Updated Bulgarian translation (5104t)
   1ecef023a9 Merge branch 'fr_next' of github.com:jnavila/git
   5b888ad949 Merge branch 'master' of github.com:nafmo/git-l10n-sv
   068cb92300 l10n: fr: v2.31 rnd 2
   f6a7e896b8 l10n: tr: v2.31.0-rc1
   929dc48e96 l10n: sv.po: Update Swedish translation (5104t0f0u)
   9b7e82b940 l10n: git.pot: v2.31.0 round 2 (9 new, 8 removed)
   4dd8469336 Merge branch 'master' of github.com:git/git

That matches the observation above that the depth of v2.31.1 was
increased by twelve more than the depth of v2.31.0.

And at that point I'm lost because I have no idea why adding
v2.31.0-rc2 should increase the depth of v2.31.0 and v2.31.1
differently.

René


diff --git a/builtin/describe.c b/builtin/describe.c
index 40482d8e9f..24d7a8a9cb 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -432,6 +432,14 @@ static void describe_commit(struct object_id *oid, struct strbuf *dst)

 	QSORT(all_matches, match_cnt, compare_pt);

+	if (debug) {
+		for (cur_match = 0; cur_match < match_cnt; cur_match++) {
+			struct possible_tag *t = &all_matches[cur_match];
+			fprintf(stderr, " %8d %8d %s\n",
+				t->depth, t->found_order, t->name->path);
+		}
+	}
+
 	if (gave_up_on) {
 		commit_list_insert_by_date(gave_up_on, &list);
 		seen_commits--;

Re: [BUG?] 'git describe seen'?

[Bagas Sanjaya]

On 18/04/21 17.26, René Scharfe wrote:
> And vice versa, the fifteen commits that increase the depth of v2.31.1,
> but not of v2.31.0:
> 
>     834845142d l10n: de.po: Update German translation for Git v2.31.0
>     408985d301 l10n: pt_PT: add Portuguese translations part 1
>     1369935987 l10n: vi.po(5104t): for git v2.31.0 l10n round 2
>     b0adcc311b l10n: es: 2.31.0 round 2
>     c21ad4d941 l10n: Add translation team info
>     8c4abfb8be l10n: start Indonesian translation
>     8278f87022 l10n: zh_TW.po: v2.31.0 round 2 (15 untranslated)
>     2f176de687 l10n: bg.po: Updated Bulgarian translation (5104t)
>     1ecef023a9 Merge branch 'fr_next' of github.com:jnavila/git
>     5b888ad949 Merge branch 'master' of github.com:nafmo/git-l10n-sv
>     068cb92300 l10n: fr: v2.31 rnd 2
>     f6a7e896b8 l10n: tr: v2.31.0-rc1
>     929dc48e96 l10n: sv.po: Update Swedish translation (5104t0f0u)
>     9b7e82b940 l10n: git.pot: v2.31.0 round 2 (9 new, 8 removed)
>     4dd8469336 Merge branch 'master' of github.com:git/git
> 
> That matches the observation above that the depth of v2.31.1 was
> increased by twelve more than the depth of v2.31.0.

Did you mean fifteen commits between v2.31.1 and v2.31.0? If so it's
illogical, because these commits (from git-po workflow) were merged
on rc1-rc2 of v2.31.

-- 
An old man doll... just what I always wanted! - Clara