From: Scott Schmit <i.grok@comcast.net>
To: git@vger.kernel.org
Subject: Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect
Date: Fri, 20 Mar 2015 09:02:35 -0400 [thread overview]
Message-ID: <20150320130235.GA18772@odin.ulthar.us> (raw)
In-Reply-To: <xmqqbnjsrcyz.fsf@gitster.dls.corp.google.com>
[-- Attachment #1: Type: text/plain, Size: 2726 bytes --]
On Mon, Mar 16, 2015 at 11:53:08AM -0700, Junio C Hamano wrote:
> Because the history is not linear in Git, bisection works by
> shrinking a subgraph of the history DAG that contains "yet to be
> tested, suspected to have introduced a badness" commits. The
> subgraph is defined as anything reachable from _the_ "bad" commit
> (initially, the one you give to the command when you start) that are
> not reachable from any of the "good" commits.
>
> Suppose you started from this graph. Time flows left to right as
> usual.
>
> ---0---2---4---6---8---9
> \ /
> 1---3---5---7
>
> Then mark the initial good and bad commits as G and B.
>
> ---G---2---4---6---8---B
> \ /
> 1---3---5---7
>
> And imagine that you are asked to check 4, which turns out to be
> good. We do not _move_ G to 4; we mark 4 as good, while keeping
> 0 also as good.
>
> ---G---2---G---6---8---B
> \ /
> 1---3---5---7
>
> And if you are next asked to check 5, and mark it as good, the graph
> will become like this:
>
> ---G---2---G---6---8---B
> \ /
> 1---3---G---7
>
> Of course, at this point, the subgraph of suspects are 6, 7, 8 and
> 9, and the subgraph no longer is affected by the fact that 0 is
> good. But it is crucial to keep 0 marked as good in the step before
> this one, before you tested 5, as that is what allows us not having
> to test any ancestors of 0 at all.
>
> Now, one may wonder why we need multiple "good" commits but we do
> not need multiple "bad" commits. This comes from the nature of
> "bisection", which is a tool to find a _single_ breakage [*1*], and
> a fundamental assumption is that a breakage does not fix itself.
>
> Hence, if you have a history that looks like this:
>
>
> G...1---2---3---4---6---8---B
> \
> 5---7---B
>
> it follows that 4 must also be "bad". It used to be good long time
> ago somewhere before 1, and somewhere along way on the history,
> there was a single breakage event that we are hunting for. That
> single event cannot be 5, 6, 7 or 8 because breakage at say 5 would
> not explain why the tip of the upper branch is broken---its breakage
> has no way to propagate there. The breakage must have happened at 4
> or before that commit.
But what if 7 & 8 are the same patch, cherry-picked? Or nearly the same
patch, but with some conflict resolution?
Couldn't that lead to the case that 4, 5, and 6 are good, while 7 & 8
are bad? Or does that violate the "single breakage" rule in a way that
might be too subtle for some users?
--
Scott Schmit
[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 3891 bytes --]
next prev parent reply other threads:[~2015-03-20 13:02 UTC|newest]
Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-03-03 14:19 [BUG] Segfault with rev-list --bisect Troy Moure
2015-03-04 5:33 ` Jeff King
2015-03-04 23:44 ` Junio C Hamano
2015-03-05 2:15 ` Troy Moure
2015-03-07 21:31 ` [PATCH] rev-list: refuse --first-parent combined with --bisect Kevin Daudt
2015-03-07 23:13 ` Kevin Daudt
2015-03-08 8:00 ` Junio C Hamano
2015-03-08 14:18 ` [PATCH v2] " Kevin Daudt
2015-03-08 15:02 ` [PATCH v3] " Kevin Daudt
2015-03-08 15:03 ` Kevin Daudt
2015-03-08 21:58 ` Eric Sunshine
2015-03-09 11:57 ` Kevin Daudt
2015-03-09 20:56 ` [PATCH v4] " Kevin Daudt
2015-03-10 22:09 ` Junio C Hamano
2015-03-10 22:55 ` Kevin Daudt
2015-03-10 23:12 ` Junio C Hamano
2015-03-11 18:45 ` Kevin Daudt
2015-03-11 20:13 ` Junio C Hamano
2015-03-16 16:33 ` Kevin Daudt
2015-03-16 18:53 ` Junio C Hamano
2015-03-16 20:25 ` Philip Oakley
2015-03-16 21:05 ` Junio C Hamano
2015-03-17 16:09 ` Christian Couder
2015-03-17 18:33 ` Junio C Hamano
2015-03-17 19:49 ` Christian Couder
2015-03-17 20:46 ` Junio C Hamano
2015-03-18 10:36 ` Christian Couder
2015-03-19 23:51 ` Philip Oakley
2015-03-20 13:02 ` Scott Schmit [this message]
2015-03-19 22:14 ` [PATCH v5] " Kevin Daudt
2015-03-19 22:43 ` Junio C Hamano
2015-03-21 22:01 ` Kevin Daudt
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
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20150320130235.GA18772@odin.ulthar.us \
--to=i.grok@comcast.net \
--cc=git@vger.kernel.org \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).