https://github.com/rust-lang/rust is not bisectable

https://github.com/rust-lang/rust is not bisectable

[Askar Safin]

Hi. It seems that either "git bisect" has a bug, either repo at
https://github.com/rust-lang/rust is broken.

(Keep in mind that Rust project has somehow custom git setup:
https://doc.rust-lang.org/nightly/clippy/development/infrastructure/sync.html#patching-git-subtree-to-work-with-big-repos
)

So, here are steps to reproduce. I use fresh debian sid with git 2.39.0.

root@f6ca188fd101:/# git clone https://github.com/rust-lang/rust
Cloning into 'rust'...
remote: Enumerating objects: 2107155, done.
remote: Counting objects: 100% (145/145), done.
remote: Compressing objects: 100% (79/79), done.
remote: Total 2107155 (delta 73), reused 102 (delta 64), pack-reused 2107010
Receiving objects: 100% (2107155/2107155), 1009.95 MiB | 2.74 MiB/s, done.
Resolving deltas: 100% (1647434/1647434), done.
Updating files: 100% (38754/38754), done.
root@f6ca188fd101:/# cd rust

Now let's notice that commit 7175c499ecc32cb3ff713be0bbac9fd12990a34e
has word "bootstrap" in file "compiler/rustc_target/src/abi/mod.rs",
but commit 49c2279ef658d8732597c4da93897d84838f3df5 (master as of
2022-12-17) - does not.

Also, let's notice that 7175c499ecc32cb3ff713be0bbac9fd12990a34e is an
ancestor of 49c2279ef658d8732597c4da93897d84838f3df5. (Everywhere I
say that X is an ancestor of Y, I mean that X can be found in "git log
Y", in other words "git log Y | grep -q '^commit X' " returns true.)

Now let's find the first commit, which doesn't contain "bootstrap" in
that file in this interval. Let's do it using "git bisect".

root@f6ca188fd101:/rust# git bisect start
status: waiting for both good and bad commits
root@f6ca188fd101:/rust# git bisect good
7175c499ecc32cb3ff713be0bbac9fd12990a34e
status: waiting for bad commit, 1 good commit known
root@f6ca188fd101:/rust# git bisect bad 49c2279ef658d8732597c4da93897d84838f3df5
Bisecting: 23901 revisions left to test after this (roughly 15 steps)
[26562973b3482a635416b2b663a13016d4d90e20] Auto merge of #13653 -
VannTen:fix/doc-typo-vim-lsp, r=Veykril

Okay, so "git bisect" gave us commit
26562973b3482a635416b2b663a13016d4d90e20. And here I see a bug:
7175c499ecc32cb3ff713be0bbac9fd12990a34e is NOT ancestor of
26562973b3482a635416b2b663a13016d4d90e20! But I think "git bisect"
should give us some commit between "good" and "bad", so presumably
"good" should be an ancestor of the commit returned by "git bisect".

-- 
Askar Safin

Re: https://github.com/rust-lang/rust is not bisectable

[Andreas Schwab]

On Dez 17 2022, Askar Safin wrote:

> Okay, so "git bisect" gave us commit
> 26562973b3482a635416b2b663a13016d4d90e20. And here I see a bug:
> 7175c499ecc32cb3ff713be0bbac9fd12990a34e is NOT ancestor of
> 26562973b3482a635416b2b663a13016d4d90e20!

26562973b3482a635416b2b663a13016d4d90e20 is an ancestor of the bad
commit, and not an ancestor of the good commit, thus it is a candidate
for introducing the bad condition.  In a non-linear history, there can
be multiple good commits that are not directly related, each one cutting
out branches from the history.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: https://github.com/rust-lang/rust is not bisectable

[Askar Safin]

At some point that "bootstrap" word appeared, then at some point it
disappeared again. I'm trying to find a point where it has
disappeared. Consider this script:

==begin
#!/bin/bash

set -e
set -x

git bisect reset
git bisect start
git bisect good 7175c499ecc32cb3ff713be0bbac9fd12990a34e
git bisect bad 49c2279ef658d8732597c4da93897d84838f3df5

while :; do
  if grep -q bootstrap compiler/rustc_target/src/abi/mod.rs; then
    git bisect good
  else
    git bisect bad
  fi
  sleep 1
done
==end

Here is the output: https://paste.debian.net/1264444/ . As you can
see, we always choose "else git bisect bad". And we reach... initial
commit!

Well, technically speaking, this is correct: initial commit is
actually the first commit, where word "bootstrap" is not present in
compiler/rustc_target/src/abi/mod.rs . But this is not what I want! I
want to find commit, which is the first one, which doesn't have
"bootstrap" in compiler/rustc_target/src/abi/mod.rs, AND which is
descendant of good commit ( 7175c499ecc32cb3ff713be0bbac9fd12990a34e
).

Also, after failing with "git bisect", I did MANUAL BISECT!!!!!! I did
this: I run command "gitk --ancestry-path $GOOD..$BAD". Then I clicked
to some commit located nearly in the middle of history, then I copied
its ID. Then I switched to this commit and checked whether it is good.
Then I again run command "gitk --ancestry-path $GOOD..$BAD", this time
with a smaller interval. I did this several times and eventually I was
able to find the faulty commit! (Well, the result was not good enough:
this manual bisecting gave me some merge commit, so I still don't see
the actual commit. But it is still better than "git bisect": "git
bisect" simply gave me the initial commit.)

So, as you can see, manual bisecting (somewhat) works and "git bisect"
doesn't. This means that something is wrong with "git bisect". (Maybe
there is a way to make "git bisect" behave similar to that "gitk"
experiment above?)

Let me say this in other words: I want git-bisect to mark all commits,
which are not descendants of good, as good. (Here I assume bad is
descendant of good.)

-- 
Askar Safin

Re: https://github.com/rust-lang/rust is not bisectable

[Andreas Schwab]

On Dez 18 2022, Askar Safin wrote:

> At some point that "bootstrap" word appeared, then at some point it
> disappeared again.

If you have more that one distinct range where the bad condition exists
then bisection will not work correctly.  Bisection assumes that there is
only one commit in the search space that introduces the bad condition.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: https://github.com/rust-lang/rust is not bisectable

[SZEDER Gábor]

On Sun, Dec 18, 2022 at 06:15:44AM +0300, Askar Safin wrote:
> At some point that "bootstrap" word appeared, then at some point it
> disappeared again. I'm trying to find a point where it has
> disappeared. Consider this script:
> 
> ==begin
> #!/bin/bash
> 
> set -e
> set -x
> 
> git bisect reset
> git bisect start
> git bisect good 7175c499ecc32cb3ff713be0bbac9fd12990a34e
> git bisect bad 49c2279ef658d8732597c4da93897d84838f3df5
> 
> while :; do
>   if grep -q bootstrap compiler/rustc_target/src/abi/mod.rs; then
>     git bisect good
>   else
>     git bisect bad
>   fi
>   sleep 1
> done
> ==end
> 
> Here is the output: https://paste.debian.net/1264444/ . As you can
> see, we always choose "else git bisect bad". And we reach... initial
> commit!

Yeah, but as you can see from all those

  grep: compiler/rustc_target/src/abi/mod.rs: No such file or directory

error messages, it didn't choose bad because "bootstrap" was not
present in the file in question, but because the file in question was
not present in the examined revision in the first place!  You must
take this into consideration when deciding whether a revision is good
or bad.

> Well, technically speaking, this is correct: initial commit is
> actually the first commit, where word "bootstrap" is not present in
> compiler/rustc_target/src/abi/mod.rs . But this is not what I want! I
> want to find commit, which is the first one, which doesn't have
> "bootstrap" in compiler/rustc_target/src/abi/mod.rs, AND which is
> descendant of good commit ( 7175c499ecc32cb3ff713be0bbac9fd12990a34e
> ).

No, you want to find the first commit which does contain a file 
compiler/rustc_target/src/abi/mod.rs, and where that file doesn't
contain "bootstrap".

  $ git bisect start 49c2279ef658d8732597c4da93897d84838f3df5 7175c499ecc32cb3ff713be0bbac9fd12990a34e
  Bisecting: 23901 revisions left to test after this (roughly 15 steps)
  [26562973b3482a635416b2b663a13016d4d90e20] Auto merge of #13653 - VannTen:fix/doc-typo-vim-lsp, r=Veykril
  $ cat run.sh
  #!/bin/sh
  
  file="compiler/rustc_target/src/abi/mod.rs"
  if test ! -f "$file"
  then
  	echo "  !!!  missing $file"
  elif grep -q bootstrap "$file"
  then
  	echo "  +++  found bootstrap in $file"
  else
  	echo "  ---  no bootstrap in $file"
  	false
  fi
  $ git bisect run ./run.sh
  running './run.sh'
    !!!  missing compiler/rustc_target/src/abi/mod.rs
  Bisecting: 11961 revisions left to test after this (roughly 14 steps)
  [7a8636c843bd24038fe1d1f69b4a8e4b0ea55d4e] Auto merge of #100982 - fee1-dead-contrib:const-impl-requires-const-trait, r=oli-obk
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 5974 revisions left to test after this (roughly 13 steps)
  [335e7d3e33300942ce99e7010a31ad4c1086a36a] Rollup merge of #98745 - thomcc:build-dir-arg, r=jyn514
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 2980 revisions left to test after this (roughly 12 steps)
  [512a328e2fb32bddd206461770a2c058368519cc] Auto merge of #95309 - lcnr:dropck-cleanup, r=nikomatsakis
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 1485 revisions left to test after this (roughly 11 steps)
  [143eaa8d441641251ab41ed73deaba0d8d0cf4a5] Auto merge of #93970 - cjgillot:novis, r=petrochenkov
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 748 revisions left to test after this (roughly 10 steps)
  [198a1548ea4c25e3756d70bb2cafed6bb1860d6a] Rollup merge of #95369 - jyn514:test-rustdoc, r=Mark-Simulacrum
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 374 revisions left to test after this (roughly 9 steps)
  [3c2f864ffbf0e3d01f3f684acbd0ee602619bf19] session: opt for enabling directionality markers
  running './run.sh'
    +++  found bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 186 revisions left to test after this (roughly 8 steps)
  [7b285d09e9e4ccf8273cc03dba28e8a428e6084e] Rollup merge of #95791 - oconnor663:doc_comment, r=thomcc
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 93 revisions left to test after this (roughly 7 steps)
  [201cf3dba302cec9b62e9b988858dcad47a88a4f] Auto merge of #95723 - SparrowLii:const_goto, r=fee1-dead
  running './run.sh'
    +++  found bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 47 revisions left to test after this (roughly 6 steps)
  [2e4964ed3d6a4de97b863777f97c7790808afce3] Rollup merge of #95714 - KSBilodeau:master, r=Dylan-DPC
  running './run.sh'
    +++  found bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 23 revisions left to test after this (roughly 5 steps)
  [ed6c958ee4bf081deec951996ace9c508360c1d9] Auto merge of #95760 - Dylan-DPC:rollup-uskzggh, r=Dylan-DPC
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 12 revisions left to test after this (roughly 4 steps)
  [870ab12ea7976ad3c56eac6f0559b122e0f055c5] Rollup merge of #95752 - compiler-errors:issue-82866, r=Dylan-DPC
  running './run.sh'
    +++  found bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 6 revisions left to test after this (roughly 3 steps)
  [73dc13058d37ebcfcdde46e7f63c4c69bd26685d] remove ~const Drop from rustdoc test
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 2 revisions left to test after this (roughly 2 steps)
  [b744bb67fdfd3e34404cc9df1d87acdfdb4a0cb4] rustc_trait_selection changes
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 0 revisions left to test after this (roughly 1 step)
  [181d28bb6110dc974879db20d433f21aa142db3a] trivial cfg(bootstrap) changes
  running './run.sh'
    ---  no bootstrap in compiler/rustc_target/src/abi/mod.rs
  Bisecting: 0 revisions left to test after this (roughly 0 steps)
  [e96538aeeb2a71e672e1d1a40dcaf0ad34a826b5] bump stage0 to the latest beta
  running './run.sh'
    +++  found bootstrap in compiler/rustc_target/src/abi/mod.rs
  181d28bb6110dc974879db20d433f21aa142db3a is the first bad commit
  commit 181d28bb6110dc974879db20d433f21aa142db3a
  Author: Pietro Albini <pietro@pietroalbini.org>
  Date:   Tue Apr 5 22:42:23 2022 +0200
  
      trivial cfg(bootstrap) changes
  
  [ ... diffstat ... ]
  bisect found first bad commit

Re: https://github.com/rust-lang/rust is not bisectable

[Askar Safin]

SZEDER Gábor, yes, in this particular case this helps. Thank you! (But
I still wonder how to tell git-bisect to ignore commits, which are not
descendants of good commit.)

-- 
Askar Safin

Re: https://github.com/rust-lang/rust is not bisectable

[Andreas Schwab]

If you are only interested in the linear part of the history you can use
--first-parent.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: https://github.com/rust-lang/rust is not bisectable

[SZEDER Gábor]

On Sun, Dec 18, 2022 at 01:03:54PM +0300, Askar Safin wrote:
> SZEDER Gábor, yes, in this particular case this helps.

Not just in this particular case, but this solves a general issue of
bisecting non-linear histories that is the file/testcase/whatever of
interest is not present in all candidate revisions in the range '^good
bad'.

> (But
> I still wonder how to tell git-bisect to ignore commits, which are not
> descendants of good commit.)

In general you do not want to tell that to bisect, because any one of
them could have introduced the change you are looking for.  Consider
the following piece of history, where commits 'm<N>' are on the master
branch, 'b<N>' are on a different branch, and the commit marked with C
made a buggy change, and commits marked with G and B are the ones you
marked as good and bad you started the bisection.

            (G)            (M)  (B)
  m1---m2---m3---m4---m5---m6---m7
        \                 /
         b1---b2---b3---b4
                   (C)

If bisect were to ignore commits "which are not descendants of good
commit", then it wouldn't look at any of the 'b<N>' commits made on
the side branch.  It would only look at commits m{3,4,5,6,7}, and thus
report m6 as the first bad commit, which is clearly not the case.

RE: https://github.com/rust-lang/rust is not bisectable

[rsbecker]

On December 18, 2022 5:53 AM, SZEDER Gábor wrote:
>On Sun, Dec 18, 2022 at 01:03:54PM +0300, Askar Safin wrote:
>> SZEDER Gábor, yes, in this particular case this helps.
>
>Not just in this particular case, but this solves a general issue of bisecting non-
>linear histories that is the file/testcase/whatever of interest is not present in all
>candidate revisions in the range '^good bad'.
>
>> (But
>> I still wonder how to tell git-bisect to ignore commits, which are not
>> descendants of good commit.)
>
>In general you do not want to tell that to bisect, because any one of them could
>have introduced the change you are looking for.  Consider the following piece of
>history, where commits 'm<N>' are on the master branch, 'b<N>' are on a
>different branch, and the commit marked with C made a buggy change, and
>commits marked with G and B are the ones you marked as good and bad you
>started the bisection.
>
>            (G)            (M)  (B)
>  m1---m2---m3---m4---m5---m6---m7
>        \                 /
>         b1---b2---b3---b4
>                   (C)
>
>If bisect were to ignore commits "which are not descendants of good commit",
>then it wouldn't look at any of the 'b<N>' commits made on the side branch.  It
>would only look at commits m{3,4,5,6,7}, and thus report m6 as the first bad
>commit, which is clearly not the case.

Could you not use bisect skip to ignore the commits that cannot be tested?