[PATCH 02/16] bisect: add test for the bisect algorithm

git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed

From: Stephan Beyer <s-beyer@gmx.net>
To: git@vger.kernel.org
Cc: Stephan Beyer <s-beyer@gmx.net>,
	Christian Couder <chriscool@tuxfamily.org>
Subject: [PATCH 02/16] bisect: add test for the bisect algorithm
Date: Fri, 26 Feb 2016 03:04:28 +0100	[thread overview]
Message-ID: <1456452282-10325-3-git-send-email-s-beyer@gmx.net> (raw)
In-Reply-To: <1456452282-10325-1-git-send-email-s-beyer@gmx.net>

Signed-off-by: Stephan Beyer <s-beyer@gmx.net>
---

To be honest: the test could be better, it could be more "targeted",
i.e. the example commit history could be smaller and just consider
all the cases and corner cases and whatever.
However, I made it first to understand the algorithm and verify the
description of it in the documentation. Then I was too lazy to
improve it. I am sorry that this is no better advertising text. ;)

Moreover, the test does not test one important thing that is
always cared about in the bisect code: TREESAME commits.
Perhaps I got the concept wrong. I tried to obtain TREESAME commits
using 'git commit --allow-empty -m "same tree"'. However, those
commits were never considered being TREESAME. So I gave up (I did
not care much.)
Anyone has an idea how to obtain them?
Or is this a bug that should be fixed?

(Also UNINTERESTING commits are never found by the DEBUG_BISECT
output, but I think this is because they are just filtered out.)

 t/t8010-bisect-algorithm.sh | 162 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 162 insertions(+)
 create mode 100755 t/t8010-bisect-algorithm.sh

diff --git a/t/t8010-bisect-algorithm.sh b/t/t8010-bisect-algorithm.sh
new file mode 100755
index 0000000..bda59da
--- /dev/null
+++ b/t/t8010-bisect-algorithm.sh
@@ -0,0 +1,162 @@
+#!/bin/sh
+#
+# Copyright (c) 2016 Stephan Beyer
+#
+test_description='Tests git bisect algorithm'
+
+exec </dev/null
+
+. ./test-lib.sh
+
+test_expect_success 'set up a history for the test' '
+	test_commit A1 A 1 &&
+	test_commit A2 A 2 &&
+	test_commit A3 A 3 &&
+	test_commit A4 A 4 &&
+	test_commit A5 A 5 &&
+	test_commit A6 A 6 &&
+	git checkout -b b A5 &&
+	test_commit B1 B 1 &&
+	git checkout master &&
+	test_commit A7 A 7 &&
+	git checkout b &&
+	test_commit B2 B 2 &&
+	git checkout master &&
+	test_commit A8 A 8 &&
+	test_merge Bmerge b &&
+	git checkout b &&
+	test_commit B3 B 3 &&
+	git checkout -b c A7 &&
+	test_commit C1 C 1 &&
+	git checkout -b d A3 &&
+	test_commit D1 D 1 &&
+	git checkout c &&
+	test_commit C2 C 2 &&
+	git checkout d &&
+	test_commit D2 D 2 &&
+	git checkout c &&
+	test_commit C3 C 3 &&
+	git checkout master &&
+	git merge -m BCDmerge b c d &&
+	git tag BCDmerge &&
+	test_commit A9 A 9 &&
+	git checkout d &&
+	test_commit D3 &&
+	git checkout master
+'
+
+test_expect_success 'bisect algorithm works in linear history with an odd number of commits' '
+	git bisect start A7 &&
+	git bisect next &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse A3)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse A4)"
+'
+
+test_expect_success 'bisect algorithm works in linear history with an even number of commits' '
+	git bisect reset &&
+	git bisect start A8 &&
+	git bisect next &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse A4)"
+'
+
+test_expect_success 'bisect algorithm works with a merge' '
+	git bisect reset &&
+	git bisect start Bmerge &&
+	git bisect next &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse A5)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse A8)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse B2)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse B1)"
+'
+
+#                   | w  min | w  min | w  min | w  min |
+# B---.    BCDmerge | 18  0  | 9    0 | 5    0 | 3    0 |
+# |\ \ \            |        |        |        |        |
+# | | | *  D2       | 5   5  | 2    2 | 2    2*| good   |
+# | | | *  D1       | 4   4  | 1    1 | 1    1 | good   |
+# | | * |  C3       | 10  8  | 1    1 | 1    1 | 1    1*|
+# | | * |  C2       | 9   9 *| good   | good   | good   |
+# | | * |  C1       | 8   8  | good   | good   | good   |
+# | * | |  B3       | 8   8  | 3    3 | 1    1 | 1    1*|
+# * | | |  Bmerge   | 11  7  | 4    4*| good   | good   |
+# |\ \ \ \          |        |        |        |        |
+# | |/ / /          |        |        |        |        |
+# | * | |  B2       | 7   7  | 2    2 | good   | good   |
+# | * | |  B1       | 6   6  | 1    1 | good   | good   |
+# * | | |  A8       | 8   8  | 1    1 | good   | good   |
+# | |/ /            |        |        |        |        |
+# |/| |             |        |        |        |        |
+# * | |   A7        | 7   7  | good   | good   | good   |
+# * | |   A6        | 6   6  | good   | good   | good   |
+# |/ /              |        |        |        |        |
+# * |     A5        | 5   5  | good   | good   | good   |
+# * |     A4        | 4   4  | good   | good   | good   |
+# |/                |        |        |        |        |
+# *       A3        | 3   3  | good   | good   | good   |
+# *       A2        | 2   2  | good   | good   | good   |
+# *       A1        | 1   1  | good   | good   | good   |
+
+test_expect_success 'bisect algorithm works with octopus merge' '
+	git bisect reset &&
+	git bisect start BCDmerge &&
+	git bisect next &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse C2)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse Bmerge)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse D2)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse B3)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse C3)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse C3)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse B3)" &&
+	git bisect good > output &&
+	grep "$(git rev-parse BCDmerge) is the first bad commit" output
+'
+
+# G 5a6bcdf        D3       | w  min | w  min |
+# | B 02f2eed      A9       | 14  0  | 7   0  |
+# | *---. 6174c5c  BCDmerge | 13  1  | 6   1  |
+# | |\ \ \                  |        |        |
+# | |_|_|/                  |        |        |
+# |/| | |                   |        |        |
+# G | | | a6d6dab  D2       | good   | good   |
+# * | | | 86414e4  D1       | good   | good   |
+# | | | * c672402  C3       | 7   7 *| good   |
+# | | | * 0555272  C2       | 6   6  | good   |
+# | | | * 28c2b2a  C1       | 5   5  | good   |
+# | | * | 4b5a7d9  B3       | 5   5  | 3   3 *|
+# | * | | a419ab7  Bmerge   | 8   6  | 4   3 *|
+# | |\ \ \                  |        |        |
+# | | |/ /                  |        |        |
+# | | * | 4fa1e39  B2       | 4   4  | 2   2  |
+# | | * | 92a014d  B1       | 3   3  | 1   1  |
+# | * | | 79158c7  A8       | 5   5  | 1   1  |
+# | | |/                    |        |        |
+# | |/|                     |        |        |
+# | * | 237eb73    A7       | 4   4  | good   |
+# | * | 3b2f811    A6       | 3   3  | good   |
+# | |/                      |        |        |
+# | * 0f2b6d2      A5       | 2   2  | good   |
+# | * 1fcdaf0      A4       | 1   1  | good   |
+# |/                        |        |        |
+# * 096648b        A3       | good   | good   |
+# * 1cf01b8        A2       | good   | good   |
+# * 6623165        A1       | good   | good   |
+
+test_expect_success 'bisect algorithm works with good commit on unrelated branch' '
+	git bisect reset &&
+	git bisect start A9 D3 &&
+	test "$(git rev-parse HEAD)" = "$(git merge-base A9 D3)" &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse D2)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse C3)" &&
+	git bisect good &&
+	test "$(git rev-parse HEAD)" = "$(git rev-parse B3)" \
+	  -o "$(git rev-parse HEAD)" = "$(git rev-parse Bmerge)"
+'
+
+test_done
-- 
2.7.1.354.gd492730.dirty

next prev parent reply	other threads:[~2016-02-26  2:06 UTC|newest]

Thread overview: 34+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-02-26  2:04 [PATCH 00/16] git bisect improvements Stephan Beyer
2016-02-26  2:04 ` [PATCH 01/16] bisect: write about `bisect next` in documentation Stephan Beyer
2016-02-26  8:02   ` Jacob Keller
2016-02-26 18:47   ` Junio C Hamano
2016-02-27 13:45     ` Stephan Beyer
2016-02-27 18:03       ` Junio C Hamano
2016-02-27 19:38         ` Stephan Beyer
2016-02-28 18:28           ` Junio C Hamano
2016-02-26  2:04 ` Stephan Beyer [this message]
2016-02-26  6:53   ` [PATCH 02/16] bisect: add test for the bisect algorithm Christian Couder
2016-02-26 21:38     ` Stephan Beyer
2016-02-27 11:40       ` Christian Couder
2016-02-27 12:42         ` Matthieu Moy
2016-02-26  2:04 ` [PATCH 03/16] bisect: make bisect compile if DEBUG_BISECT is set Stephan Beyer
2016-02-26  2:04 ` [PATCH 04/16] bisect: make algorithm behavior independent of DEBUG_BISECT Stephan Beyer
2016-02-26  2:04 ` [PATCH 05/16] bisect: get rid of recursion in count_distance() Stephan Beyer
2016-02-26  2:04 ` [PATCH 06/16] bisect: use struct node_data array instead of int array Stephan Beyer
2016-02-26  2:04 ` [PATCH 07/16] bisect: replace clear_distance() by unique markers Stephan Beyer
2016-02-26  2:04 ` [PATCH 08/16] bisect: use commit instead of commit list as arguments when appropriate Stephan Beyer
2016-02-26  3:10   ` Junio C Hamano
2016-02-26  2:04 ` [PATCH 09/16] bisect: extract get_distance() function from code duplication Stephan Beyer
2016-02-26  2:04 ` [PATCH 10/16] bisect: introduce distance_direction() Stephan Beyer
2016-02-26  2:04 ` [PATCH 11/16] bisect: make total number of commits global Stephan Beyer
2016-02-26  2:04 ` [PATCH 12/16] bisect: rename count_distance() to compute_weight() Stephan Beyer
2016-02-26  2:04 ` [PATCH 13/16] bisect: prepare for different algorithms based on find_all Stephan Beyer
2016-02-26  2:04 ` [PATCH 14/16] bisect: use a modified breadth-first search to find relevant weights Stephan Beyer
2016-02-26  3:09   ` Junio C Hamano
2016-02-26 20:55     ` Stephan Beyer
2016-02-26  2:04 ` [PATCH 15/16] bisect: compute best bisection in compute_relevant_weights() Stephan Beyer
2016-02-26  2:04 ` [PATCH 16/16] bisect: get back halfway shortcut Stephan Beyer
2016-03-20 18:50 ` [PATCH 00/16] git bisect improvements Pranit Bauva
2016-03-21 22:22   ` Stephan Beyer
2016-03-22  7:35     ` Christian Couder
2016-03-22 11:35     ` Pranit Bauva

find likely ancestor, descendant, or conflicting patches for this message:
( dfblob:bda59da )
 OR (
bs:"[PATCH 02/16] bisect: add test for the bisect algorithm" )
	(help)

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=1456452282-10325-3-git-send-email-s-beyer@gmx.net \
    --to=s-beyer@gmx.net \
    --cc=chriscool@tuxfamily.org \
    --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).