git bisect for reachable commits only

git bisect for reachable commits only

[Oleg Taranenko]

Hi all,


I just found an interesting post how git bisect can trouble humans.
Full story is here
https://groups.google.com/forum/#!topic/git-users/v3__t42qbKE


My suggestion to fix it (ditto)


What I suggest change logic of bisecting to something like


      git config bisect.reachable true


This behaviour will reduce bisecting only to reachable commits between
bad/good points and will never goes away.

Maybe if commit will be found at merge commit git bisect can suggest
open another round trip to looking into not reachable way, but anyway
it should be explicit confirmed by user.


BTW, if bad commit is merge point with more than 2 parents, how git
bisect will find "first wrong commit" at the current state?


Thanks for the attention,


Oleg

Re: git bisect for reachable commits only

[Junio C Hamano]

Oleg Taranenko <olegtaranenko@gmail.com> writes:

> What I suggest change logic of bisecting to something like
>
>       git config bisect.reachable true

Such a configuration should not be needed.

When a history with this shape is given to "git bisect":

    ----o---o---X---Y---B
         \     /
          o---G

and you gave G as good, and B as bad, it is a BUG that needs to be
fixed if bisect strayed outside G, X, Y and B.  Setting your new
configuration to false would mean "please run a buggy version of
bisect", which does not make much sense, I would think.

Re: git bisect for reachable commits only

[Oleg Taranenko]

Hi Junio,

Thanks for reply.
Let consider two pretty similar use cases.

************ SCENARIO 1 ************

mkdir bisect
cd bisect/
git init
git touch coffee
git commit -am "create coffee"
git branch develop
echo sugar >> coffee
git commit -am "add sugar" # we are still in master branch
git checkout develop       # get back to coffe without sugar
git touch tee              # cooking tee in develop branch
git commit -am "tee"
git merge master           #
cat coffee                 # after merge coffe has sugar
ex +g/sugar/d -cwq coffee  # introducing 'bug' by removing sugar from coffee
git commit -am "merged/amended" --amend       # the history is amended
echo "sugar" >> tee
git commit -am "sugar for tee"              # just advance for measure

# -------------- We are getting following state ------------------
git status                 # develop branch
git log --full-history --graph --pretty=oneline
* 83e9577b4a5d553fdc16806fdea9757229ea9222 sugar for tee
*   23a4aa69a9d5c03aa145844005555b7ee00c4d63 merged/amended
|\
| * 4c1caf7cb2417181c035a953afdf2389dd130aef add sugar
* | c080fb4df39d721e2f2e0fdd91fe16d8bdd77515 tee
|/
* 3c3043b7d0a0d260c78db55b565f26e430aa5c80 create coffee

cat coffee # nothing                        # discovering coffee has no sugar
git checkout 4c1c                           # but we remember it should to have
cat coffee                                  # ..."sugar"

git bisect start
git bisect good
git bisect bad develop   # 23a4
cat coffee               # nothing
git bisect bad           # c080
cat coffee               # nothing
git bisect bad           #
c080fb4df39d721e2f2e0fdd91fe16d8bdd77515 is the first bad commit
commit c080fb4df39d721e2f2e0fdd91fe16d8bdd77515
Author: Oleg Taranenko <olegtaranenko@gmail.com>
Date:   Fri Jul 29 09:08:47 2016 +0200

    tee

:000000 100644 0000000000000000000000000000000000000000
e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 A tee



We are getting first bad commit c080, but git bisect fails.
We remember is was introduced in the 23a4 commit via wrong merge and
history amending.


************ SCENARIO 2 ************
cd ..
mkdir bisect2
cd bisect2
git init
git touch coffee
git commit -am "create coffee"
echo sugar >> coffee
# we are still in master branch
git commit -am "add sugar"
git branch develop
echo milk >> coffee
git commit -am "add milk to coffee"

# get back to coffe without sugar
git checkout  develop
ex "+g/sugar/d" -cwq coffee
echo milk >> coffee
git commit -am "coffee: replace sugar with milk"
# cooking tee in develop branch
git touch tee
git commit -am "tee"
git checkout master
git merge develop


#Here we are getting real conflict
cat coffee
#<<<<<<< HEAD
#sugar
#=======
#>>>>>>> develop
#milk

#resolving
git checkout develop --theirs -- coffee
cat coffee             # milk
git commit -am "conflict resolved"
echo "sugar" >> tee
git commit -am "sugar for tee"              # just advance for measure


 ---------- State -----------------
git log --full-history --graph --pretty=oneline
* b88a3cb3df58fc018d635d559d212707e953f84d sugar for tee
*   138824139c0237fe05419d4f40a693e4c19405a3 conflict resolved
|\
| * e1ddbfe05d632d6f12dd7ff9d9b61475c2cde867 tee
| * ddfb5188c98b8fc803a036ac4eee0610e2bba53f coffee: replace sugar with milk
* | 0e1c55363e5b2fb04a6072fa470f90770b3eee22 add milk to coffee
|/
* 465d0c68c597f1534c3c1e19ed9a086c5da190ae add sugar
* 24b73ce9085a6d411c06c08cca0536dc8f2239c7 create coffee


cat coffee      # only milk, no sugar... bug
git checkout 792d
cat coffee                 # OK, milk & sugar
git bisect start
git bisect good
git bisect bad master      # e1dd
cat coffee                 # milk only
git bisect bad             # ddfb
cat coffee                 # milk only
git bisect bad             # first bad commit !!

It happens, git really found that somebody (me) was replaced sugar
with milk, because ancestor of both branches already has sugar, and
commit ddfb
explicit removes it.

As we can see, both strategies can coexisting, and now I ever can't
state for sure, which one is more intuitive correct.

I think if repo has relative straight history, more productive to use
bisect with auto search in un-reachable commits.
For messy repositories (especially, with lots of aliens code) more
safe to use --reachable bisecting strategy.

Then, I suggest as well additional to defaulting via 'git config
bisect.reachable true/false' use per bisect session switch

    git bisect start --[un-]reachable-commits # which will override
default setting


Thanks you for reading to this point,

Oleg

On Fri, Jul 29, 2016 at 8:03 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Oleg Taranenko <olegtaranenko@gmail.com> writes:
>
>> What I suggest change logic of bisecting to something like
>>
>>       git config bisect.reachable true
>
> Such a configuration should not be needed.
>
> When a history with this shape is given to "git bisect":
>
>     ----o---o---X---Y---B
>          \     /
>           o---G
>
> and you gave G as good, and B as bad, it is a BUG that needs to be
> fixed if bisect strayed outside G, X, Y and B.  Setting your new
> configuration to false would mean "please run a buggy version of
> bisect", which does not make much sense, I would think.
>
>
>
>
>

Re: git bisect for reachable commits only

[Jakub Narębski]

W dniu 31.07.2016 o 02:06, Oleg Taranenko pisze:

> Then, I suggest as well additional to defaulting via 'git config
> bisect.reachable true/false' use per bisect session switch
> 
>     git bisect start --[un-]reachable-commits # which will override
> default setting

Isn't `--reachable-commits` the same as existing `--ancestry-path`
option to `git log` and friends (I wonder if passing log options to
bisect, that is: `git bisect --ancestry-path ...` would work)?

-- 
Jakub Narębski

Re: git bisect for reachable commits only

[Junio C Hamano]

Jakub Narębski <jnareb@gmail.com> writes:

> Isn't `--reachable-commits` the same as existing `--ancestry-path`
> option to `git log` and friends (I wonder if passing log options to
> bisect, that is: `git bisect --ancestry-path ...` would work)?

Yes, I somehow missed it, but you are absolutely correct to point
out that what is being requested is --ancestry-path.

My gut feeling is that by default the command should be taught to
follow the ancestry path, but I say this with reservation, as I am
not sure offhand what it means to traverse along the ancestry path
when there are multiple good commits.

Thanks.

Re: git bisect for reachable commits only

[Oleg Taranenko]

Guys,

further investigation shows, git bisect is broken from its core... really.
Let consider 3rd a bit more complicated scenario

#cd ..
#rm -rf bisect3
mkdir bisect3
cd bisect3
git init
git touch coffee
git commit -am "create coffee"
git branch tee
echo sugar >> coffee
git commit -am "add sugar"  # we are still in master branch
echo "milk" >> coffee
git commit -am "milk for coffee"
ex +g/sugar/d -cwq coffee  # introducing 'bug'
git commit -am "somehow remove sugar"
echo "mixing..." >> coffee
git commit -am "coffee mixing"

git checkout tee            # get back to coffee without sugar
git touch tee
git commit -am "tee"

git branch cocktail
echo "sugar" >> tee
git commit -am "sugar for tee"
echo "milk" >> tee
git commit -am "milk for tee"
echo "mixing..." >> tee
git commit -am "tee mixing"

git checkout cocktail
git touch cocktail
git commit -am "prepare cocktail"
echo orange >>cocktail
git commit -am "add orange juice"
echo rum >>cocktail
git commit -am "add rum"
echo mixing >> cocktail
git commit -am "cocktail mixing"
cat cocktail  #orange, rum, mixing
git merge tee
git merge master

git touch serve
git commit -am "serving..."

git log --full-history --graph --pretty=oneline

* 059adf903a2cbc06fe05dda4c916e2c586907f23 serving...
*   efc89d5253d3126defc7362c25ef069ae9b43fc7 Merge branch 'master' into cocktail
|\
| * dd41e230a3cac5d51a1e994747ff470e2af03cae coffee mixing
| * c2a44672f1197f34e04cd0fd66434a2b286b574e somehow remove sugar
| * f50352cfb6bc4a237b73c95ed7ebca074603ae11 milk for coffee
| * 79b253b316cdc3668697afe473610e35b453ab2f add sugar
* |   2d626eb5cfaa40a4503be58a5ed27f1ececa6d02 Merge branch 'tee' into cocktail
|\ \
| * | 7aba690c6c6f73f1906871c9dbf9737ec11a152b tee mixing
| * | eca611a93697359ec7a52f4a045461180bc365c3 milk for tee
| * | 7d6844724d0e81751ec1a67c1ffdf0d0fb932350 sugar for tee
* | | 6754e816922989d5870ec3452437bbbe6aca4d0f cocktail mixing
* | | 5cbbf0f0882c497590838b163210db3a393b647e add rum
* | | b46d7d8a361daae382fbef7acabda5416d23da46 add orange juice
* | | e571fdd09582e40fc54ffc5a4f112eac2b9f2c8e prepare cocktail
|/ /
* | 041a5a53704bccc60c489f8c9a4742bad79d5a95 tee
|/
* a52a4fa6770d000a9f4e9e297739a6dc88c0cc50 create coffee

As you can see, no tricks with amended history, but...

git bisect start HEAD 79b2
Bisecting: 8 revisions left to test after this (roughly 3 steps)
[6754e816922989d5870ec3452437bbbe6aca4d0f] cocktail mixing
cat coffee
git bisect bad
Bisecting: 2 revisions left to test after this (roughly 1 step)
[e571fdd09582e40fc54ffc5a4f112eac2b9f2c8e] prepare cocktail
git bisect bad
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[041a5a53704bccc60c489f8c9a4742bad79d5a95] tee
git bisect bad
041a5a53704bccc60c489f8c9a4742bad79d5a95 is the first bad commit
commit 041a5a53704bccc60c489f8c9a4742bad79d5a95
Author: Oleg Taranenko <olegtaranenko@gmail.com>
Date:   Mon Aug 1 10:53:52 2016 +0200

    tee

:000000 100644 0000000000000000000000000000000000000000
e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 A tee

git bisect ever not looked into the path where good commit is
declared. Instead it found somehow most common ancestor from whole
tree (a52a create coffee),  assume it is GOOD commit (why !?) and
check only ^1 (not ^2) parent commit for testing as a potential bug
commit.
No wonder now, I got a disaster result, looking in my heavy enterprise
repository.

Can somebody take care of this issue?

Thanks, Oleg

On Sun, Jul 31, 2016 at 2:06 AM, Oleg Taranenko <olegtaranenko@gmail.com> wrote:
> Hi Junio,
>
> Thanks for reply.
> Let consider two pretty similar use cases.
>
> ************ SCENARIO 1 ************
>
> mkdir bisect
> cd bisect/
> git init
> git touch coffee
> git commit -am "create coffee"
> git branch develop
> echo sugar >> coffee
> git commit -am "add sugar" # we are still in master branch
> git checkout develop       # get back to coffe without sugar
> git touch tee              # cooking tee in develop branch
> git commit -am "tee"
> git merge master           #
> cat coffee                 # after merge coffe has sugar
> ex +g/sugar/d -cwq coffee  # introducing 'bug' by removing sugar from coffee
> git commit -am "merged/amended" --amend       # the history is amended
> echo "sugar" >> tee
> git commit -am "sugar for tee"              # just advance for measure
>
> # -------------- We are getting following state ------------------
> git status                 # develop branch
> git log --full-history --graph --pretty=oneline
> * 83e9577b4a5d553fdc16806fdea9757229ea9222 sugar for tee
> *   23a4aa69a9d5c03aa145844005555b7ee00c4d63 merged/amended
> |\
> | * 4c1caf7cb2417181c035a953afdf2389dd130aef add sugar
> * | c080fb4df39d721e2f2e0fdd91fe16d8bdd77515 tee
> |/
> * 3c3043b7d0a0d260c78db55b565f26e430aa5c80 create coffee
>
> cat coffee # nothing                        # discovering coffee has no sugar
> git checkout 4c1c                           # but we remember it should to have
> cat coffee                                  # ..."sugar"
>
> git bisect start
> git bisect good
> git bisect bad develop   # 23a4
> cat coffee               # nothing
> git bisect bad           # c080
> cat coffee               # nothing
> git bisect bad           #
> c080fb4df39d721e2f2e0fdd91fe16d8bdd77515 is the first bad commit
> commit c080fb4df39d721e2f2e0fdd91fe16d8bdd77515
> Author: Oleg Taranenko <olegtaranenko@gmail.com>
> Date:   Fri Jul 29 09:08:47 2016 +0200
>
>     tee
>
> :000000 100644 0000000000000000000000000000000000000000
> e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 A tee
>
>
>
> We are getting first bad commit c080, but git bisect fails.
> We remember is was introduced in the 23a4 commit via wrong merge and
> history amending.
>
>
> ************ SCENARIO 2 ************
> cd ..
> mkdir bisect2
> cd bisect2
> git init
> git touch coffee
> git commit -am "create coffee"
> echo sugar >> coffee
> # we are still in master branch
> git commit -am "add sugar"
> git branch develop
> echo milk >> coffee
> git commit -am "add milk to coffee"
>
> # get back to coffe without sugar
> git checkout  develop
> ex "+g/sugar/d" -cwq coffee
> echo milk >> coffee
> git commit -am "coffee: replace sugar with milk"
> # cooking tee in develop branch
> git touch tee
> git commit -am "tee"
> git checkout master
> git merge develop
>
>
> #Here we are getting real conflict
> cat coffee
> #<<<<<<< HEAD
> #sugar
> #=======
> #>>>>>>> develop
> #milk
>
> #resolving
> git checkout develop --theirs -- coffee
> cat coffee             # milk
> git commit -am "conflict resolved"
> echo "sugar" >> tee
> git commit -am "sugar for tee"              # just advance for measure
>
>
>  ---------- State -----------------
> git log --full-history --graph --pretty=oneline
> * b88a3cb3df58fc018d635d559d212707e953f84d sugar for tee
> *   138824139c0237fe05419d4f40a693e4c19405a3 conflict resolved
> |\
> | * e1ddbfe05d632d6f12dd7ff9d9b61475c2cde867 tee
> | * ddfb5188c98b8fc803a036ac4eee0610e2bba53f coffee: replace sugar with milk
> * | 0e1c55363e5b2fb04a6072fa470f90770b3eee22 add milk to coffee
> |/
> * 465d0c68c597f1534c3c1e19ed9a086c5da190ae add sugar
> * 24b73ce9085a6d411c06c08cca0536dc8f2239c7 create coffee
>
>
> cat coffee      # only milk, no sugar... bug
> git checkout 792d
> cat coffee                 # OK, milk & sugar
> git bisect start
> git bisect good
> git bisect bad master      # e1dd
> cat coffee                 # milk only
> git bisect bad             # ddfb
> cat coffee                 # milk only
> git bisect bad             # first bad commit !!
>
> It happens, git really found that somebody (me) was replaced sugar
> with milk, because ancestor of both branches already has sugar, and
> commit ddfb
> explicit removes it.
>
> As we can see, both strategies can coexisting, and now I ever can't
> state for sure, which one is more intuitive correct.
>
> I think if repo has relative straight history, more productive to use
> bisect with auto search in un-reachable commits.
> For messy repositories (especially, with lots of aliens code) more
> safe to use --reachable bisecting strategy.
>
> Then, I suggest as well additional to defaulting via 'git config
> bisect.reachable true/false' use per bisect session switch
>
>     git bisect start --[un-]reachable-commits # which will override
> default setting
>
>
> Thanks you for reading to this point,
>
> Oleg
>
> On Fri, Jul 29, 2016 at 8:03 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Oleg Taranenko <olegtaranenko@gmail.com> writes:
>>
>>> What I suggest change logic of bisecting to something like
>>>
>>>       git config bisect.reachable true
>>
>> Such a configuration should not be needed.
>>
>> When a history with this shape is given to "git bisect":
>>
>>     ----o---o---X---Y---B
>>          \     /
>>           o---G
>>
>> and you gave G as good, and B as bad, it is a BUG that needs to be
>> fixed if bisect strayed outside G, X, Y and B.  Setting your new
>> configuration to false would mean "please run a buggy version of
>> bisect", which does not make much sense, I would think.
>>
>>
>>
>>
>>

Re: git bisect for reachable commits only

[Christian Couder]

On Mon, Aug 1, 2016 at 12:02 PM, Oleg Taranenko <olegtaranenko@gmail.com> wrote:
> Guys,
>
> further investigation shows, git bisect is broken from its core... really.
> Let consider 3rd a bit more complicated scenario
>
> #cd ..
> #rm -rf bisect3
> mkdir bisect3
> cd bisect3
> git init
> git touch coffee

git touch is not a git command

> git commit -am "create coffee"

you need to "git add coffee" first otherwise it doesn't work

> git branch tee
> echo sugar >> coffee
> git commit -am "add sugar"  # we are still in master branch
> echo "milk" >> coffee
> git commit -am "milk for coffee"
> ex +g/sugar/d -cwq coffee  # introducing 'bug'
> git commit -am "somehow remove sugar"
> echo "mixing..." >> coffee
> git commit -am "coffee mixing"
>
> git checkout tee            # get back to coffee without sugar
> git touch tee

git touch is not a git command
it might be an alias you have that does `touch "$@" && git add "$@"`

> git commit -am "tee"
>
> git branch cocktail
> echo "sugar" >> tee
> git commit -am "sugar for tee"
> echo "milk" >> tee
> git commit -am "milk for tee"
> echo "mixing..." >> tee
> git commit -am "tee mixing"
>
> git checkout cocktail
> git touch cocktail
> git commit -am "prepare cocktail"
> echo orange >>cocktail
> git commit -am "add orange juice"
> echo rum >>cocktail
> git commit -am "add rum"
> echo mixing >> cocktail
> git commit -am "cocktail mixing"
> cat cocktail  #orange, rum, mixing
> git merge tee
> git merge master
>
> git touch serve
> git commit -am "serving..."
>
> git log --full-history --graph --pretty=oneline
>
> * 059adf903a2cbc06fe05dda4c916e2c586907f23 serving...
> *   efc89d5253d3126defc7362c25ef069ae9b43fc7 Merge branch 'master' into cocktail
> |\
> | * dd41e230a3cac5d51a1e994747ff470e2af03cae coffee mixing
> | * c2a44672f1197f34e04cd0fd66434a2b286b574e somehow remove sugar
> | * f50352cfb6bc4a237b73c95ed7ebca074603ae11 milk for coffee
> | * 79b253b316cdc3668697afe473610e35b453ab2f add sugar
> * |   2d626eb5cfaa40a4503be58a5ed27f1ececa6d02 Merge branch 'tee' into cocktail
> |\ \
> | * | 7aba690c6c6f73f1906871c9dbf9737ec11a152b tee mixing
> | * | eca611a93697359ec7a52f4a045461180bc365c3 milk for tee
> | * | 7d6844724d0e81751ec1a67c1ffdf0d0fb932350 sugar for tee
> * | | 6754e816922989d5870ec3452437bbbe6aca4d0f cocktail mixing
> * | | 5cbbf0f0882c497590838b163210db3a393b647e add rum
> * | | b46d7d8a361daae382fbef7acabda5416d23da46 add orange juice
> * | | e571fdd09582e40fc54ffc5a4f112eac2b9f2c8e prepare cocktail
> |/ /
> * | 041a5a53704bccc60c489f8c9a4742bad79d5a95 tee
> |/
> * a52a4fa6770d000a9f4e9e297739a6dc88c0cc50 create coffee
>
> As you can see, no tricks with amended history, but...
>
> git bisect start HEAD 79b2
> Bisecting: 8 revisions left to test after this (roughly 3 steps)
> [6754e816922989d5870ec3452437bbbe6aca4d0f] cocktail mixing
> cat coffee
> git bisect bad

Why is it bad?
Is it because there is no sugar?
In this case you are searching for a commit that removed sugar.

> Bisecting: 2 revisions left to test after this (roughly 1 step)
> [e571fdd09582e40fc54ffc5a4f112eac2b9f2c8e] prepare cocktail
> git bisect bad
> Bisecting: 0 revisions left to test after this (roughly 0 steps)
> [041a5a53704bccc60c489f8c9a4742bad79d5a95] tee
> git bisect bad
> 041a5a53704bccc60c489f8c9a4742bad79d5a95 is the first bad commit
> commit 041a5a53704bccc60c489f8c9a4742bad79d5a95
> Author: Oleg Taranenko <olegtaranenko@gmail.com>
> Date:   Mon Aug 1 10:53:52 2016 +0200
>
>     tee
>
> :000000 100644 0000000000000000000000000000000000000000
> e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 A tee
>
> git bisect ever not looked into the path where good commit is
> declared. Instead it found somehow most common ancestor from whole
> tree (a52a create coffee),  assume it is GOOD commit (why !?)

Yes, and the reason is that all the ancestors of a good commit are
considered good.
That's because git bisect supposes that there is only one transition
from good to bad.
Otherwise we would need a more complex algorithm to find all the
transitions from good to bad, and that is not generally needed.

> and
> check only ^1 (not ^2) parent commit for testing as a potential bug
> commit.
> No wonder now, I got a disaster result, looking in my heavy enterprise
> repository.
>
> Can somebody take care of this issue?

I haven't looked at your previous issue much, sorry I have been busy these days.

Re: git bisect for reachable commits only

[Junio C Hamano]

Christian Couder <christian.couder@gmail.com> writes:

> Yes, and the reason is that all the ancestors of a good commit are
> considered good.
> That's because git bisect supposes that there is only one transition
> from good to bad.
> Otherwise we would need a more complex algorithm to find all the
> transitions from good to bad, and that is not generally needed.

It may be debatable if that is generally needed or not, but by
definition "bisect" is about having a history that has a SINGLE
point that changes from good to bad (or old to new, or "have sugar"
to "no sugar"), and that single-ness is what allows us to BIsect the
graph.  So even if it may be a good thing to have to be able to find
multiple transitions, that is outside the scope of how the current
"git bisect" was designed to be used.

> I haven't looked at your previous issue much, sorry I have been busy these days.

I think the "previous issue" was that we can ask the user to ask to
check one of 'x' or 'y' when given Good and Bad points in a graph like
this:

        x---y---y---o---B
         \         / 
          x---G---o

while a more natural expectation by a user would be that we only
need to check one of these two 'o'.

Thinking about it again, I actually think it makes sense to ask the
user to check 'y'; there is no good reason to believe that 'y' can
never have introduced the badness we are hunting for, and limiting
the search to --ancestry-path (which is to ask only for 'o') would
stop at the merge 'o' if one of the 'y' were bad, which would
prevents us from knowing the exact breakage.

There however is no excuse if we asked to check 'x', though.  They
are ancestors of a Good commit, and "git bisect" should be able to
assume they are Good.

Re: git bisect for reachable commits only

[Christian Couder]

On Mon, Aug 1, 2016 at 9:51 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Christian Couder <christian.couder@gmail.com> writes:
>
>> Yes, and the reason is that all the ancestors of a good commit are
>> considered good.
>> That's because git bisect supposes that there is only one transition
>> from good to bad.
>> Otherwise we would need a more complex algorithm to find all the
>> transitions from good to bad, and that is not generally needed.
>
> It may be debatable if that is generally needed or not, but by
> definition "bisect" is about having a history that has a SINGLE
> point that changes from good to bad (or old to new, or "have sugar"
> to "no sugar"), and that single-ness is what allows us to BIsect the
> graph.  So even if it may be a good thing to have to be able to find
> multiple transitions, that is outside the scope of how the current
> "git bisect" was designed to be used.

Yeah, this is a better version of what I wanted to say.

>> I haven't looked at your previous issue much, sorry I have been busy these days.
>
> I think the "previous issue" was that we can ask the user to ask to
> check one of 'x' or 'y' when given Good and Bad points in a graph like
> this:
>
>         x---y---y---o---B
>          \         /
>           x---G---o
>
> while a more natural expectation by a user would be that we only
> need to check one of these two 'o'.

Yeah, I reproduced the steps described in the Google Groups discussion:

https://groups.google.com/forum/#!topic/git-users/v3__t42qbKE

and I think that is indeed the "previous issue".

> Thinking about it again, I actually think it makes sense to ask the
> user to check 'y'; there is no good reason to believe that 'y' can
> never have introduced the badness we are hunting for, and limiting
> the search to --ancestry-path (which is to ask only for 'o') would
> stop at the merge 'o' if one of the 'y' were bad, which would
> prevents us from knowing the exact breakage.

I agree.

> There however is no excuse if we asked to check 'x', though.  They
> are ancestors of a Good commit, and "git bisect" should be able to
> assume they are Good.

I think it does. When I reproduced the steps in the "previous issue",
it did assume they are good.

Re: git bisect for reachable commits only

[Junio C Hamano]

Christian Couder <christian.couder@gmail.com> writes:

>> I think the "previous issue" was that we can ask the user to ask to
>> check one of 'x' or 'y' when given Good and Bad points in a graph like
>> this:
>>
>>         x---y---y---o---B
>>          \         /
>>           x---G---o
>>
>> while a more natural expectation by a user would be that we only
>> need to check one of these two 'o'.
>
> Yeah, I reproduced the steps described in the Google Groups discussion:
>
> https://groups.google.com/forum/#!topic/git-users/v3__t42qbKE
>
> and I think that is indeed the "previous issue".
>
>> Thinking about it again, I actually think it makes sense to ask the
>> user to check 'y'; there is no good reason to believe that 'y' can
>> never have introduced the badness we are hunting for, and limiting
>> the search to --ancestry-path (which is to ask only for 'o') would
>> stop at the merge 'o' if one of the 'y' were bad, which would
>> prevents us from knowing the exact breakage.
>
> I agree.

Having agreed on that, there are cases where you do want to stop at
the merge 'o' on the upper history, when lower-history leading to B
is the mainline and you are interested in finding the merge with
which side branch introduced a breakage, and not particularly
interested in finding the exact commit on the side branch.  Upon
finding the merge 'o' that is the parent of 'B' is bad, you find out
the owner of the side branch merged there who wrote the two 'y's,
and have him work on figuring out where in his branch he broke it.

For that, the --ancestry-path is a wrong way to traverse; what we
want in that context is the --first-parent traversal.

>> There however is no excuse if we asked to check 'x', though.  They
>> are ancestors of a Good commit, and "git bisect" should be able to
>> assume they are Good.
>
> I think it does. When I reproduced the steps in the "previous issue",
> it did assume they are good.

I actually had an impression that the original report claimed that
the user was asked to check immediate parent of G, and that would be
a bug.

Re: git bisect for reachable commits only

[Oleg Taranenko]

Guys,

thanks for discussion, I will try to reply in bulk here.
First, assuming the common ancestor is GOOD based on the fact that
some descendant given as GOOD is pretty bad idea.
It may be, but may not be. In the git-flow like workflows new features
(aka branches) are created from trunk (master/develop/...)
sporadically,
but later they will mutual merging. I would say more probably they
have not common base, then have.

Second, I don't ask "create a new algorithm to find all transition
from good/old to bad/new", not nesessary. If programmer feels
something
suspicious, he/she can create another bisect session with narrowed commit range.

Third, testing of any specific commit can be very expensive operation.
In my case - shutdown servers/refresh dbs/clean/rebuild in
eclipse/running servers/dropping browser cache/running app in
browser/going through some pages/view UI.
Some of steps of course are automated, but some not. Anyway I spend
5-10 min for every iteration. So knowing what commit is bad or good is
very valuable, then I'm very interested to hunt the bug-introduced
commit with minimal count of testing.

Scenario 4 (I will keep my previous mail numbering for possible later reference)
                 z1----z2---z3
                /     /      \
    G----x1----x2----/---x3---x4--B
          \         /   /
           y1--y2--y3--y4

This is the happy straight case with closed DAG (hehe, git for
scientists) between given G good and B bad commits.
Ideal bisect will check first the shortest way between G & B:
x1/x2/x3/x4. Let name first-bug commit we are really hunting H and
current first-bug candidate as h.
If h == x1 or x2 -> stop, found
If h == x3, bisect will try to test y2/y3/y4 path only
If h == x4, bisect will select shortest path z1/z2 (keeping in mind,
that x2 is already tested and is good)
  If h == z1 - found
  if h == z2 - looking in path y1/y2/y3

Scenario 5.
              v1-------v2
             /          \
        w1--/---w2-------w3---------w4--w5
       /   /   /                         \
      /   /   /            z1----z2---z3  \
     /   /   /            /     /      \   \
    C3--C2--C1--G--x1----x2----/---x3---x4--x5--x6--B
                    \         /   /
                     y1--y2--y3--y4

Unhappy case, we have side branches which may introduce bug behaviour,
we need to look it through to figure out why it was done, what problem
was solved for that and so on.
Let looking in shortest path x1-x6. If h == x1..x4 - happy use case of
scenario 4. If discover that h == x5, we are forgetting about z/y
paths, but first we looking for nearest common commit (C1). As far as
we agree that currently is not clear when the new feature was
introduced we need to explicit check commit C1 whether it contains a
feature we are hunting bug up.
if C1 is good then pretty possible bad transition was happend in w2-w5
commits. Else (C1 is bad) assume that there is no transition from good
to bad, then assume H == x5 (stop)
if C1 is good and h == w4/w5 => stop,
  else if h == w3, new roundtrip, forgetting about w1 commit(not
interesting), testing C2, if bad - stop H == w3, if good, v1/v2
commits are to test.
  else if h == w2, forgetting C2 testing, just testing C3. If bad,
stop, H == w3, if good, w1 to test.

Using this approach we can safe working with ever octopus merging
(personally I'm not using, but why not)


Scenario 6.
                    z1---z2---z3
                   /    /       \
    C1--G--x1----x2----/------x3 |
     \      \         /         \|
      \      y1--y2--y3--y4--y5--y6--B
       \              \         /|
        \              w1--w2-w3 |
         \                      /
          v1------------------v2

Important note. Before start every side circuit based on common
ancestor user should be explicitly warned, that this is not just
ordinal intermediate bisect commit testing, but possible new round
trips with new commit/steps counts
For example, if current shortest path is x1-x6, bisect should say
about only 6 commits (3 after bisect), not calculating commits in
other paths.
Reaching node decision, bisect will stay and prompt for testing new
common ancestor with clear instructions what happens, if it will be
good or bad, (new unchecked commits and new left bisect steps, in case
good and stop or switch to other path in case of octopus).

I have another request to get git bisect more user-friendly, regarding
rolling back last step or steps, if accidentally 'git bisect bad' or
'good' was wrong entered, but I think it worth for another thread.


Cheers, Oleg

Re: git bisect for reachable commits only

[Stefan Beller]

On Tue, Aug 2, 2016 at 3:15 AM, Oleg Taranenko <olegtaranenko@gmail.com> wrote:
> Guys,
>
> thanks for discussion, I will try to reply in bulk here.
> First, assuming the common ancestor is GOOD based on the fact that
> some descendant given as GOOD is pretty bad idea.
> It may be, but may not be. In the git-flow like workflows new features
> (aka branches) are created from trunk (master/develop/...)
> sporadically,
> but later they will mutual merging. I would say more probably they
> have not common base, then have.

git bisect has the underlying assumption that the BUG is not there initially
and introduced by one specific commit, and continues to be there until B.
With this assumption you can do a binary search, which allows searching
in O(log n), which is optimal for the number of iterations needed.

>
> Second, I don't ask "create a new algorithm to find all transition
> from good/old to bad/new", not nesessary. If programmer feels
> something
> suspicious, he/she can create another bisect session with narrowed commit range.
>
> Third, testing of any specific commit can be very expensive operation.
> In my case - shutdown servers/refresh dbs/clean/rebuild in
> eclipse/running servers/dropping browser cache/running app in
> browser/going through some pages/view UI.
> Some of steps of course are automated, but some not. Anyway I spend
> 5-10 min for every iteration. So knowing what commit is bad or good is
> very valuable, then I'm very interested to hunt the bug-introduced
> commit with minimal count of testing.


As you point out each iteration is a burden to the user, so they should be
kept to a minimum.

>
> Scenario 4 (I will keep my previous mail numbering for possible later reference)
>                  z1----z2---z3
>                 /     /      \
>     G----x1----x2----/---x3---x4--B
>           \         /   /
>            y1--y2--y3--y4
>
> This is the happy straight case with closed DAG (hehe, git for
> scientists) between given G good and B bad commits.
> Ideal bisect will check first the shortest way between G & B:
> x1/x2/x3/x4. Let name first-bug commit we are really hunting H and
> current first-bug candidate as h.
> If h == x1 or x2 -> stop, found
> If h == x3, bisect will try to test y2/y3/y4 path only
> If h == x4, bisect will select shortest path z1/z2 (keeping in mind,
> that x2 is already tested and is good)
>   If h == z1 - found
>   if h == z2 - looking in path y1/y2/y3

* git is agnostic of the workflow, i.e. it doesn't know the notion of
topic branches or such.
* What is the worst case in you strategy?
  (h=y4 means 7 tests by the user IIUC)

Given the assumptions as laid out above such that we are able to
do a binary search, the ideal candidate for scenario 4 is
y4 or z3 as these split the set of commits to be investigated into
2 equally sized sets of ancestors and non-ancestors.

When a specific workflow is given, it may make sense to weight
commits differently. Also some people asked for a strategy that only
checks merge commits first, as there are far fewer merge commits and
these generally are used for introducing a new feature or refactoring.

Re: git bisect for reachable commits only

[Junio C Hamano]

Oleg Taranenko <olegtaranenko@gmail.com> writes:

> First, assuming the common ancestor is GOOD based on the fact that
> some descendant given as GOOD is pretty bad idea.

What you claim is fundamentally incompatible with the way "bisect"
works as a O(log(n)) operation.  It is likely that your definition
of Good for the purpose of your bug-hunting needs to be rethought if
you want to take advantage of "bisect".

> I have another request to get git bisect more user-friendly, regarding
> rolling back last step or steps, if accidentally 'git bisect bad' or
> 'good' was wrong entered, but I think it worth for another thread.

Are you aware that you can check $GIT_DIR/BISECT_LOG and replay it
to recreate any previous state of the bisection?  That would
probably help.

Re: git bisect for reachable commits only

[Oleg Taranenko]

On Tue, Aug 2, 2016 at 11:00 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Oleg Taranenko <olegtaranenko@gmail.com> writes:
>
>> First, assuming the common ancestor is GOOD based on the fact that
>> some descendant given as GOOD is pretty bad idea.
>
> What you claim is fundamentally incompatible with the way "bisect"
> works as a O(log(n)) operation.  It is likely that your definition
> of Good for the purpose of your bug-hunting needs to be rethought if
> you want to take advantage of "bisect".

Without context it sounds a bit silly, agree. Context was, maybe not
explicit stated, based on previous discussion:

If we looking in direct path G..B, of course bisect should show its
power O(log(n));
BUT, assuming that any predecessor (G~1/G~2...)...is good if this
commit G~n has direct path to B,  but not via G, (as git does now) is
wrong.
This is my concern. Ever G~1 may have not feature we are looking for,
then we must treated it as BAD in current git bisect session. To be
sure we require additional evidence and just opening a new bisect
roundrips in case G~n is GOOD.
If G~n confirmed as BAD, we need to stop looking in this path (no need
to find transition BAG -> BAD) and switch to another possible common
ancestor (or next octopus parent)
In merge-based development (opposite to rebased one) this can happen very easy


>> I have another request to get git bisect more user-friendly, regarding
>> rolling back last step or steps, if accidentally 'git bisect bad' or
>> 'good' was wrong entered, but I think it worth for another thread.
>
> Are you aware that you can check $GIT_DIR/BISECT_LOG and replay it
> to recreate any previous state of the bisection?  That would
> probably help.

git bisect log / replay is not convenient. First we need to find place
where to keep log file (not forget its name), then edit it. If I'm not
sure how many steps I did a mistake the troubles doubles,
What are obstacles to implement git bisect back ?
or git bisect back --steps=2
I don't think it will be significant change in code.

It would be a great help especially if hunting in multiply logically
loose-coupled repos. Say searching bug in application, possible caused
elusive changes on several dependent libraries.