[24/27] bisect: Stop bisection when we are confident about bad commit

Commit Message

Jan Kara Nov. 18, 2021, 4:49 p.m. UTC

When we found a commit that has high enough probability of being bad,
stop bisection and report it.

Signed-off-by: Jan Kara <[e-mail]>
---
 bisect.c | 18 +++++++++++++++---
 1 file changed, 15 insertions(+), 3 deletions(-)

Patch

diff --git a/bisect.c b/bisect.c
index 12b027b86e75..7da74778d780 100644
--- a/bisect.c
+++ b/bisect.c
@@ -624,7 +624,7 @@  static int sw_rev_bmp_cmp(const void *data, const struct hashmap_entry *ap,
  * Compute for each commit a probability it is the bad one given tests
  * performed so far.
  */
-static void compute_commit_weights(struct commit_list *list)
+static struct commit_list *compute_commit_weights(struct commit_list *list)
 {
 	struct commit_list *p;
 	struct hashmap reach_map;
@@ -714,9 +714,14 @@  static void compute_commit_weights(struct commit_list *list)
 		found_entry = hashmap_get_entry(&reach_map, &entry, entry, NULL);
 		pweight->node_weight =
 			found_entry->cluster_p_bad / found_entry->count;
+		/* Found node we are confident enough is bad? */
+		if (pweight->node_weight >= result_confidence)
+			break;
 	}
 
 	hashmap_clear_and_free(&reach_map, struct sw_rev_bmp_hash_entry, entry);
+
+	return p;
 }
 
 void find_bisection(struct commit_list **commit_list, int *reaches,
@@ -758,14 +763,21 @@  void find_bisection(struct commit_list **commit_list, int *reaches,
 	if (result_confidence)
 		compute_tested_descendants(list);
 	list = reverse_list(list);
-	if (result_confidence)
-		compute_commit_weights(list);
+	if (result_confidence) {
+		best = compute_commit_weights(list);
+		/* Found commit we are confident is bad? Stop bisection... */
+		if (best) {
+			oidcpy(current_bad_oid, &best->item->object.oid);
+			goto found_best;
+		}
+	}
 	show_list("bisection 2 sorted", 0, nr, list);
 
 	/* Do the real work of finding bisection commit. */
 	best = do_find_bisection(list, nr, bisect_flags);
 	if (best) {
 		if (!(bisect_flags & FIND_BISECTION_ALL)) {
+found_best:
 			list->item = best->item;
 			free_commit_list(list->next);
 			best = list;