git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / Atom feed
From: Jeff King <peff@peff.net>
To: Arnaud Morin <arnaud.morin@gmail.com>
Cc: git@vger.kernel.org, Kevin Willford <kewillf@microsoft.com>
Subject: Re: rev-list with multiple commits sharing same patch-id
Date: Tue, 12 Jan 2021 09:17:37 -0500
Message-ID: <X/2vgbnxWSmst5yB@coredump.intra.peff.net> (raw)
In-Reply-To: <20210109162440.GM31701@sync>

On Sat, Jan 09, 2021 at 04:24:40PM +0000, Arnaud Morin wrote:

> After digging a little bit, the thing is that this commit is having the
> following patch-id:
> $ git show dbf86d8aafc897a25a3093139b4237a62395041e | git patch-id
> 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e
> 
> Which is also already existing in an other commit:
> $ for c in $(git rev-list HEAD) ; do git show $c |git patch-id |grep 20f4ace68e80a751b07d78a27c94e83d6c5314bc; done
> 20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e
> 20f4ace68e80a751b07d78a27c94e83d6c5314bc 8969d3fa9159730fd3b23199873bfb26e3d20027

A slight nit first. Those two commits have the same patch-id, but in
your graph they are on the same branch ("master", not "B"):

> The commits in B are cherry-picked from master.
> Here is the graph:
> $ git log --graph --oneline --all
> * ae2e3c4 (origin/B, B) remove line2 and add line4 (bis)
> * a7a0339 remove line4
> * caa4aad restore line2
> * d7dc596 remove line2 add line4
> * 44bcfd4 add line3
> * e372641 b
> | * dbf86d8 (HEAD -> master, origin/master) remove line2 and add line4 (bis)
> | * 4017282 remove line4
> | * 0f2a449 restore line2
> | * 8969d3f remove line2 add line4
> | * e73b420 add line3
> | * fe5a75a b
> |/  
> * 6192505 a
> * b4089e1 init

And --cherry-pick is only looking for matches between the two sides of
the symmetric difference.

However, I think that patch-id does exist on the other side (it appears
again twice in fact, which is not surprising):

  $ git rev-list --all | git diff-tree --stdin -p | git patch-id | grep 20f4ace68e80
  20f4ace68e80a751b07d78a27c94e83d6c5314bc ae2e3c4754f53440cc4612d35f80d795a695c862
  20f4ace68e80a751b07d78a27c94e83d6c5314bc dbf86d8aafc897a25a3093139b4237a62395041e
  20f4ace68e80a751b07d78a27c94e83d6c5314bc d7dc596fcc34662cba35363febc846bfcab1e4be
  20f4ace68e80a751b07d78a27c94e83d6c5314bc 8969d3fa9159730fd3b23199873bfb26e3d20027

So the entries should be suppressed from both sides.

It looks like this was broken in v2.10.0, via dfb7a1b4d0 (patch-ids:
stop using a hand-rolled hashmap implementation, 2016-07-29).

I think the issue is that it is allowing duplicate entries in the
hashmap. The algorithm is something like:

  - iterate over left-hand commits, inserting patch-id for each into
    hashmap

  - iterate over right-hand commits, seeing if any are present in
    hashmap. If so, we exclude the commit _and_ mark the patch-id as
    "seen"

  - iterate again over left-hand commits, omitting any whose patch-ids
    are marked as "seen"

So if two commits on the left-hand side have the same patch-id, if we
insert two entries into the hashmap, then only one of them is going to
get its "seen" flag marked in the middle step.

-Peff

  parent reply	other threads:[~2021-01-12 14:20 UTC|newest]

Thread overview: 15+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-01-09 16:24 Arnaud Morin
2021-01-11  7:59 ` Arnaud Morin
2021-01-11  9:54 ` Christian Couder
2021-01-11 18:25   ` Arnaud Morin
2021-01-12 14:17 ` Jeff King [this message]
2021-01-12 15:11   ` Jeff King
2021-01-12 15:34     ` Arnaud Morin
2021-01-12 15:52       ` [PATCH] patch-ids: handle duplicate hashmap entries Jeff King
2021-01-12 16:24         ` Arnaud Morin
2021-01-12 19:13         ` Junio C Hamano
2021-01-13  9:24           ` Arnaud Morin
2021-01-13 12:59             ` Jeff King
2021-01-13 20:21               ` Junio C Hamano
2021-01-13 20:33                 ` Jeff King
2021-01-13 19:28             ` Junio C Hamano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=X/2vgbnxWSmst5yB@coredump.intra.peff.net \
    --to=peff@peff.net \
    --cc=arnaud.morin@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=kewillf@microsoft.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

git@vger.kernel.org list mirror (unofficial, one of many)

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V1 git git/ https://public-inbox.org/git \
		git@vger.kernel.org
	public-inbox-index git

Example config snippet for mirrors.
Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.io/gmane.comp.version-control.git
 note: .onion URLs require Tor: https://www.torproject.org/

code repositories for the project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

AGPL code for this site: git clone https://public-inbox.org/public-inbox.git