git-rev-list: "--bisect" flag

Ok, I just added a feature to "git-rev-list" that I hereby nominate to be the coolest feature ever, namely the "--bisect" flag, which basically tries to split the list of revisions in two, and prints out just the "most middle" commit.

The idea is that you want to do binary-search for a bug, but since the git history isn't a nice linear thing, you don't know where the hell the mid-point is between two commits, and even if you _do_ know where it is, it gets even more complicated when you have 3 points (on different branches) that are known good, and one point that is known bad.

Now, assuming you have three known-good points, and one known bad point, the way to get all commits in between is

	git-rev-list bad ^good1 ^good2 ^good3

and with the new flag you can now trivially get an estimate for what the mid-point is in this list. So you just do

	git-rev-list --bisect bad ^good1 ^good2 ^good3

and you now have the point to test. If testing shows that mid-way-point was bad, you just continue with that as a "new bad":

	git-rev-list --bisect new-bad ^good1 ^good2 ^good3

but if it shows that that point was still good, you instead just add it to the list of uninteresting commits, and do

	git-rev-list --bisect bad ^good1 ^good2 ^good3 ^new-good

instead. Every iteration you basically cut down the number of commits by half - you're bisecting the set, and binary-searching for the first bad commit.

Note that git also makes resetting to the test-point be really trivial: you just do

	git-read-tree -m -u <prev-point> <test-point>

where "prev-point" was your previous state (ie usually "HEAD" the first time, but the previous test-point otherwise), and "test-point" is the new point you want to test.

I haven't scripted this, but it should basically be pretty easy to add a couple of simple scripts to make it very easy to do the binary search be totally automated, assuming just a simple "mark test as failed/good" interface. Even without the scripting, it shouldn't be that hard to do entirely by hand.

The idea being that if you notice that something doesn't work (usually in HEAD), but you know it used to work in the previous release, you just start the whole thing going with

	# set up initial state
	cat .git/HEAD > .git/BAD
	cat .git/HEAD > .git/CURRENT
	echo "^v2.6.12" > .git/GOOD

and then you just do something like:

	# iterate
	git-rev-list --bisect BAD $(cat .git/BAD) > .git/HALFWAY
	if [ ! -s .git/HALFWAY ]; then
		echo FOUND IT:
		cat .git/CURRENT
		exit 1
	fi
	git-read-tree -m -u CURRENT HALFWAY
	cat .git/HALFWAY > .git/CURRENT

	make ..

	# if good
	echo '^'$(cat .git/CURENT) >> .git/GOOD
	.. iterate ..

	# if bad
	cat .git/CURRENT > .git/BAD
	.. iterate ..

until it says "FOUND IT".

(The above is untested, but the --bisect behaviour itself I tested, and it seems to do the right thing).

NOTE! I'm not convinced I actually find a particularly good place to split at, but I think my stupid "halfway point" decision is good enough in practice. So it might not really be a real binary search, but I think it comes pretty close to it unless you have some really odd cases.

			Linus