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

[Jan Kara <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