git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 12/27] bisect: Accept and store confidence with each decision

From
JKJan Kara <jack@suse.cz>
Date
Nov 18, 2021, 16:49 UTC
Message-ID
<20211118164940.8818-13-jack@suse.cz>
In-Reply-To
<20211118164940.8818-1-jack@suse.cz>

With each decision whether a commit is good or bad, accept an optional confidence argument and store it in bisect log and special file with probabilities a test is recording a 'bad' result. We will later use these probabilities to alter decisions about the next bisection point.

Signed-off-by: Jan Kara <jack@suse.cz>
---
 bisect.c                 |  51 ++++++++++++++++
 builtin/bisect--helper.c | 129 ++++++++++++++++++++++++++++++++-------
 fixedpoint.h             |  29 +++++++++
 3 files changed, 186 insertions(+), 23 deletions(-)
 create mode 100644 fixedpoint.h
diff --git a/bisect.c b/bisect.c
index ab264b8ca879..0773a872c82b 100644
--- a/bisect.c
+++ b/bisect.c
@@ -16,8 +16,10 @@
 #include "commit-reach.h"
 #include "object-store.h"
 #include "dir.h"
+#include "fixedpoint.h"
 
 static struct oid_array good_revs;
+static struct oid_array ptest_revs;
 static struct oid_array skipped_revs;
 
 static struct object_id *current_bad_oid;
@@ -444,12 +446,17 @@ static int register_ref(const char *refname, const struct object_id *oid,
 			int flags, void *cb_data)
 {
 	struct strbuf good_prefix = STRBUF_INIT;
+	struct strbuf ptest_prefix = STRBUF_INIT;
+
 	strbuf_addstr(&good_prefix, term_good);
 	strbuf_addstr(&good_prefix, "-");
+	strbuf_addstr(&ptest_prefix, "ptest-");
 
 	if (!strcmp(refname, term_bad)) {
 		current_bad_oid = xmalloc(sizeof(*current_bad_oid));
 		oidcpy(current_bad_oid, oid);
+	} else if (starts_with(refname, ptest_prefix.buf)) {
+		oid_array_append(&ptest_revs, oid);
 	} else if (starts_with(refname, good_prefix.buf)) {
 		oid_array_append(&good_revs, oid);
 	} else if (starts_with(refname, "skip-")) {
@@ -474,8 +481,46 @@ static GIT_PATH_FUNC(git_path_bisect_start, "BISECT_START")
 static GIT_PATH_FUNC(git_path_bisect_log, "BISECT_LOG")
 static GIT_PATH_FUNC(git_path_bisect_terms, "BISECT_TERMS")
 static GIT_PATH_FUNC(git_path_bisect_first_parent, "BISECT_FIRST_PARENT")
+static GIT_PATH_FUNC(git_path_bisect_confidences, "BISECT_CONFIDENCES")
 static GIT_PATH_FUNC(git_path_head_name, "head-name")
 
+static void read_bisect_confidences(void)
+{
+	struct strbuf str = STRBUF_INIT;
+	const char *filename = git_path_bisect_confidences();
+	FILE *fp = fopen(filename, "r");
+
+	/* Just a regular bisection? */
+	if (!fp)
+		return;
+
+	while (strbuf_getline_lf(&str, fp) != EOF) {
+		fpnum_t prob;
+		char *spc;
+		char state;
+		struct object_id oid;
+
+		strbuf_trim(&str);
+		spc = strchr(str.buf, ' ');
+		if (!spc)
+			die(_("Badly formatted content in file '%s': %s"),
+			    filename, str.buf);
+		*spc = 0;
+		if (sscanf(spc + 1, "%c %" FPNUM_FMT, &state, &prob) != 2)
+			die(_("Cannot parse confidence in file '%s': %s"),
+			    filename, spc+1);
+		if (state != 'g' && state != 'b')
+			die(_("Unknown test state in file '%s': '%c'"),
+			    filename, state);
+		if (get_oid(str.buf, &oid))
+			die(_("Cannot get oid of rev '%s' from file '%s'"),
+			    str.buf, filename);
+		/* We'll use parsed data later */
+	}
+	strbuf_release(&str);
+	fclose(fp);
+}
+
 static void read_bisect_paths(struct strvec *array)
 {
 	struct strbuf str = STRBUF_INIT;
@@ -661,6 +706,10 @@ static void bisect_rev_setup(struct repository *r, struct rev_info *revs,
 
 	/* rev_argv.argv[0] will be ignored by setup_revisions */
 	strvec_push(&rev_argv, "bisect_rev_setup");
+	/*
+	 * We use only revision certainly known to be good or bad for limiting
+	 * a search.
+	 */
 	strvec_pushf(&rev_argv, bad_format, oid_to_hex(current_bad_oid));
 	for (i = 0; i < good_revs.nr; i++)
 		strvec_pushf(&rev_argv, good_format,
@@ -1023,6 +1072,7 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix)
 	read_bisect_terms(&term_bad, &term_good);
 	if (read_bisect_refs())
 		die(_("reading bisect refs failed"));
+	read_bisect_confidences();
 
 	if (file_exists(git_path_bisect_first_parent()))
 		bisect_flags |= FIND_BISECTION_FIRST_PARENT_ONLY;
@@ -1172,6 +1222,7 @@ int bisect_clean_state(void)
 	unlink_or_warn(git_path_bisect_run());
 	unlink_or_warn(git_path_bisect_terms());
 	unlink_or_warn(git_path_bisect_first_parent());
+	unlink_or_warn(git_path_bisect_confidences());
 	/* Cleanup head-name if it got left by an old version of git-bisect */
 	unlink_or_warn(git_path_head_name());
 	/*
diff --git a/builtin/bisect--helper.c b/builtin/bisect--helper.c
index 28a2e6a5750b..f88feb8da949 100644
--- a/builtin/bisect--helper.c
+++ b/builtin/bisect--helper.c
@@ -9,6 +9,7 @@
 #include "prompt.h"
 #include "quote.h"
 #include "revision.h"
+#include "fixedpoint.h"
 
 static GIT_PATH_FUNC(git_path_bisect_terms, "BISECT_TERMS")
 static GIT_PATH_FUNC(git_path_bisect_expected_rev, "BISECT_EXPECTED_REV")
@@ -19,6 +20,7 @@ static GIT_PATH_FUNC(git_path_head_name, "head-name")
 static GIT_PATH_FUNC(git_path_bisect_names, "BISECT_NAMES")
 static GIT_PATH_FUNC(git_path_bisect_first_parent, "BISECT_FIRST_PARENT")
 static GIT_PATH_FUNC(git_path_bisect_run, "BISECT_RUN")
+static GIT_PATH_FUNC(git_path_bisect_confidences, "BISECT_CONFIDENCES")
 
 static const char * const git_bisect_helper_usage[] = {
 	N_("git bisect--helper --bisect-reset [<commit>]"),
@@ -26,8 +28,8 @@ static const char * const git_bisect_helper_usage[] = {
 	N_("git bisect--helper --bisect-start [--term-{new,bad}=<term> --term-{old,good}=<term>]"
 					    " [--no-checkout] [--first-parent] [<bad> [<good>...]] [--] [<paths>...]"),
 	N_("git bisect--helper --bisect-next"),
-	N_("git bisect--helper --bisect-state (bad|new) [<rev>]"),
-	N_("git bisect--helper --bisect-state (good|old) [<rev>...]"),
+	N_("git bisect--helper --bisect-state (bad|new) [--confidence <conf>] [<rev>]"),
+	N_("git bisect--helper --bisect-state (good|old) [--confidence <conf>] [<rev>...]"),
 	N_("git bisect--helper --bisect-replay <filename>"),
 	N_("git bisect--helper --bisect-skip [(<rev>|<range>)...]"),
 	N_("git bisect--helper --bisect-visualize"),
@@ -254,18 +256,24 @@ static void log_commit(FILE *fp, char *fmt, const char *state,
 	free(label);
 }
 
-static int bisect_write(const char *state, const char *rev,
+static int bisect_write(const char *state, const char *rev, fpnum_t confidence,
 			const struct bisect_terms *terms, int nolog)
 {
+	const char *logstate = state;
 	struct strbuf tag = STRBUF_INIT;
 	struct object_id oid;
 	struct commit *commit;
 	FILE *fp = NULL;
 	int res = 0;
 
+	/* Uncertain result? */
+	if (one_of(state, terms->term_bad, terms->term_good, NULL) &&
+	    confidence != FP_ONE)
+		state = "ptest";
+
 	if (!strcmp(state, terms->term_bad)) {
 		strbuf_addf(&tag, "refs/bisect/%s", state);
-	} else if (one_of(state, terms->term_good, "skip", NULL)) {
+	} else if (one_of(state, terms->term_good, "skip", "ptest", NULL)) {
 		strbuf_addf(&tag, "refs/bisect/%s-%s", state, rev);
 	} else {
 		res = error(_("Bad bisect_write argument: %s"), state);
@@ -283,6 +291,24 @@ static int bisect_write(const char *state, const char *rev,
 		goto finish;
 	}
 
+	/* Store confidence if it is non-trivial */
+	if (!strcmp(state, "ptest")) {
+		char cstate;
+
+		fp = fopen(git_path_bisect_confidences(), "a");
+		if (!fp) {
+			res = error_errno(_("couldn't open the file '%s'"),
+				git_path_bisect_confidences());
+			goto finish;
+		}
+		if (!strcmp(logstate, terms->term_bad))
+			cstate = 'b';
+		else
+			cstate = 'g';
+		fprintf(fp, "%s %c %" FPNUM_FMT "\n", rev, cstate, confidence);
+		fclose(fp);
+	}
+
 	fp = fopen(git_path_bisect_log(), "a");
 	if (!fp) {
 		res = error_errno(_("couldn't open the file '%s'"), git_path_bisect_log());
@@ -290,10 +316,16 @@ static int bisect_write(const char *state, const char *rev,
 	}
 
 	commit = lookup_commit_reference(the_repository, &oid);
-	log_commit(fp, "%s", state, commit);
+	log_commit(fp, "%s", logstate, commit);
 
-	if (!nolog)
-		fprintf(fp, "git bisect %s %s\n", state, rev);
+	if (!nolog) {
+		if (!strcmp(state, "ptest")) {
+			fprintf(fp, "git bisect %s --confidence %lf %s\n",
+				logstate, fp_to_double(confidence), rev);
+		} else {
+			fprintf(fp, "git bisect %s %s\n", logstate, rev);
+		}
+	}
 
 finish:
 	if (fp)
@@ -612,6 +644,16 @@ static enum bisect_error bisect_auto_next(struct bisect_terms *terms, const char
 	return bisect_next(terms, prefix);
 }
 
+static int parse_confidence(const char *str, fpnum_t *confidence)
+{
+	double confd;
+
+	if (sscanf(str, "%lf", &confd) != 1 || confd < 0 || confd > 1)
+		return error(_("invalid confidence '%s'"), str);
+	*confidence = double_to_fp(confd);
+	return 0;
+}
+
 static enum bisect_error bisect_start(struct bisect_terms *terms, const char **argv, int argc)
 {
 	int no_checkout = 0;
@@ -784,8 +826,8 @@ static enum bisect_error bisect_start(struct bisect_terms *terms, const char **a
 	write_file(git_path_bisect_names(), "%s\n", bisect_names.buf);
 
 	for (i = 0; i < states.nr; i++)
-		if (bisect_write(states.items[i].string,
-				 revs.items[i].string, terms, 1)) {
+		if (bisect_write(states.items[i].string, revs.items[i].string,
+		    FP_ONE, terms, 1)) {
 			res = BISECT_FAILED;
 			goto finish;
 		}
@@ -854,6 +896,7 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a
 	struct object_id oid, expected;
 	struct strbuf buf = STRBUF_INIT;
 	struct oid_array revs = OID_ARRAY_INIT;
+	fpnum_t confidence = FP_ONE;
 
 	if (!argc)
 		return error(_("Please call `--bisect-state` with at least one argument"));
@@ -868,6 +911,15 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a
 
 	argv++;
 	argc--;
+
+	if (argc > 0 && !strcmp(argv[0], "--confidence")) {
+		if (argc < 2)
+			return error(_("missing confidence argument"));
+		if (parse_confidence(argv[1], &confidence))
+			return -1;
+		argv += 2;
+		argc -= 2;
+	}
 	if (argc > 1 && !strcmp(state, terms->term_bad))
 		return error(_("'git bisect %s' can take only one argument."), terms->term_bad);
 
@@ -912,7 +964,8 @@ static enum bisect_error bisect_state(struct bisect_terms *terms, const char **a
 	strbuf_release(&buf);
 
 	for (i = 0; i < revs.nr; i++) {
-		if (bisect_write(state, oid_to_hex(&revs.oid[i]), terms, 0)) {
+		if (bisect_write(state, oid_to_hex(&revs.oid[i]), confidence,
+				 terms, 0)) {
 			oid_array_clear(&revs);
 			return BISECT_FAILED;
 		}
@@ -946,39 +999,69 @@ static enum bisect_error bisect_log(void)
 
 static int process_replay_line(struct bisect_terms *terms, struct strbuf *line)
 {
-	const char *p = line->buf + strspn(line->buf, " \t");
-	char *word_end, *rev;
+	char *p = line->buf + strspn(line->buf, " \t");
+	char *word_end, *cmd;
 
-	if ((!skip_prefix(p, "git bisect", &p) &&
-	!skip_prefix(p, "git-bisect", &p)) || !isspace(*p))
+	if ((!skip_prefix(p, "git bisect", (const char **)&p) &&
+	!skip_prefix(p, "git-bisect", (const char **)&p)) || !isspace(*p))
 		return 0;
 	p += strspn(p, " \t");
 
+	cmd = p;
 	word_end = (char *)p + strcspn(p, " \t");
-	rev = word_end + strspn(word_end, " \t");
+	p = word_end + strspn(word_end, " \t");
 	*word_end = '\0'; /* NUL-terminate the word */
 
 	get_terms(terms);
-	if (check_and_set_terms(terms, p))
+	if (check_and_set_terms(terms, cmd))
 		return -1;
 
-	if (!strcmp(p, "start")) {
+	if (!strcmp(cmd, "start")) {
 		struct strvec argv = STRVEC_INIT;
 		int res;
-		sq_dequote_to_strvec(rev, &argv);
+		sq_dequote_to_strvec(p, &argv);
 		res = bisect_start(terms, argv.v, argv.nr);
 		strvec_clear(&argv);
 		return res;
 	}
 
-	if (one_of(p, terms->term_good,
-	   terms->term_bad, "skip", NULL))
-		return bisect_write(p, rev, terms, 0);
+	if (one_of(cmd, terms->term_good,
+	   terms->term_bad, "skip", NULL)) {
+		fpnum_t confidence = FP_ONE;
+		char *arg;
+
+		arg = p;
+		word_end = (char *)p + strcspn(p, " \t");
+		p = word_end + strspn(word_end, " \t");
+		*word_end = '\0';
+		if (!strcmp(arg, "--confidence")) {
+			if (!strcmp(cmd, "skip")) {
+				error(_("skipping does not take confidence"));
+				return -1;
+			}
+			if (!*p) {
+				error(_("missing bisect confidence argument"));
+				return -1;
+			}
+			arg = p;
+			word_end = (char *)p + strcspn(p, " \t");
+			p = word_end + strspn(word_end, " \t");
+			*word_end = '\0';
+			if (parse_confidence(arg, &confidence))
+				return -1;
+			arg = p;
+		}
+		if (!*arg) {
+			error(_("missing bisect revision"));
+			return -1;
+		}
+		return bisect_write(cmd, arg, confidence, terms, 0);
+	}
 
-	if (!strcmp(p, "terms")) {
+	if (!strcmp(cmd, "terms")) {
 		struct strvec argv = STRVEC_INIT;
 		int res;
-		sq_dequote_to_strvec(rev, &argv);
+		sq_dequote_to_strvec(p, &argv);
 		res = bisect_terms(terms, argv.nr == 1 ? argv.v[0] : NULL);
 		strvec_clear(&argv);
 		return res;
diff --git a/fixedpoint.h b/fixedpoint.h
new file mode 100644
index 000000000000..addef223be2b
--- /dev/null
+++ b/fixedpoint.h
@@ -0,0 +1,29 @@
+#ifndef FIXEDPOINT_H
+#define FIXEDPOINT_H
+
+#include <inttypes.h>
+
+#define FIXEDPOINT_SHIFT 32
+
+typedef uint64_t fpnum_t;
+
+#define FPNUM_FMT PRIu64
+
+static inline const fpnum_t frac_to_fp(unsigned int n, unsigned int d)
+{
+	return (((fpnum_t)n) << FIXEDPOINT_SHIFT) / d;
+}
+
+static inline const fpnum_t double_to_fp(double n)
+{
+	return (n * (1ULL << FIXEDPOINT_SHIFT));
+}
+
+static inline const double fp_to_double(fpnum_t n)
+{
+	return ((double)n) / (1ULL << FIXEDPOINT_SHIFT);
+}
+
+#define FP_ONE frac_to_fp(1, 1)
+
+#endif

-- 
2.26.2
Previous: Jan KaraNext: Jan Kara
Message 32 of 43 in “Stochastic bisection support”
  1. Jan KaraNov 18, 2021
  2. 04/27 bisect: Fixup bisect-porcelain/32Jan Kara, Nov 18, 2021
  3. 02/27 bisect: Fixup bisect-porcelain/17Jan Kara, Nov 18, 2021
  4. Taylor BlauNov 18, 2021
  5. Jan KaraNov 22, 2021
  6. 03/27 bisect: Fixup test bisect-porcelain/20Jan Kara, Nov 18, 2021
  7. Chris TorekNov 18, 2021
  8. Taylor BlauNov 18, 2021
  9. Jan KaraNov 22, 2021
  10. 01/27 bisect: Fixup test rev-list-bisect/02Jan Kara, Nov 18, 2021
  11. Chris TorekNov 18, 2021
  12. Johannes SchindelinNov 19, 2021
  13. Jan KaraNov 22, 2021
  14. 10/27 bisect: Fixup bisect-porcelain/58Jan Kara, Nov 18, 2021
  15. 08/27 bisect: Fixup bisect-porcelain/50Jan Kara, Nov 18, 2021
  16. 05/27 bisect: Fixup bisect-porcelain/34Jan Kara, Nov 18, 2021
  17. 09/27 bisect: Fixup bisect-porcelain/54Jan Kara, Nov 18, 2021
  18. 06/27 bisect: Fixup bisect-porcelain/40Jan Kara, Nov 18, 2021
  19. 15/27 bisect: Rename clear_distance() to clear_counted_flag()Jan Kara, Nov 18, 2021
  20. 20/27 bisect: Compute probability a particular commit is badJan Kara, Nov 18, 2021
  21. 23/27 bisect: Find bisection point for stochastic weightsJan Kara, Nov 18, 2021
  22. 11/27 bisect: Fix bisection debuggingJan Kara, Nov 18, 2021
  23. 13/27 bisect: Allow specifying desired result confidenceJan Kara, Nov 18, 2021
  24. 22/27 bisect: Move count_distance()Jan Kara, Nov 18, 2021
  25. 19/27 bisect: Compute reachability of tested revsJan Kara, Nov 18, 2021
  26. 07/27 bisect: Remove duplicated bisect-porcelain/48Jan Kara, Nov 18, 2021
  27. 16/27 bisect: Separate commit list reversalJan Kara, Nov 18, 2021
  28. 14/27 bisect: Use void * for commit_weightJan Kara, Nov 18, 2021
  29. 17/27 bisect: Allow more complex commit weightsJan Kara, Nov 18, 2021
  30. 18/27 bisect: Terminate early if there are no eligible commitsJan Kara, Nov 18, 2021
  31. 21/27 bisect: Reorganize commit weight computationJan Kara, Nov 18, 2021
  32. 12/27 bisect: Accept and store confidence with each decisionJan Kara, Nov 18, 2021
  33. 24/27 bisect: Stop bisection when we are confident about bad commitJan Kara, Nov 18, 2021
  34. 26/27 bisect: Debug stochastic bisectionJan Kara, Nov 18, 2021
  35. 25/27 bisect: Report commit with the highest probabilityJan Kara, Nov 18, 2021
  36. 27/27 bisect: Allow bisection debugging of approx_halfway()Jan Kara, Nov 18, 2021
  37. Taylor BlauNov 18, 2021
  38. Jan KaraNov 22, 2021
  39. Johannes SchindelinNov 19, 2021
  40. Chris TorekNov 20, 2021
  41. Jan KaraNov 22, 2021
  42. Christian CouderNov 22, 2021
  43. Jan KaraNov 22, 2021

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.