bisect: use a bottom-up traversal to find relevant weights

The idea is to reverse the DAG and perform a traversal
starting on all sources of the reversed DAG.

We walk from the bottom commits, incrementing the weight while
walking on a part of the graph that is single strand of pearls,
or doing the "count the reachable ones the hard way" using
compute_weight() when we hit a merge commit.

A traversal ends when the computed weight is falling or halfway.
This way, commits with too high weight to be relevant are never
visited (and their weights are never computed).

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

1 files changed, 150 insertions, 76 deletions

diff --git a/bisect.c b/bisect.c
index c6bad437eb..9487ba9198 100644
--- a/bisect.c
+++ b/bisect.c
@@ -30,6 +30,9 @@ static unsigned marker;
 struct node_data {
 	int weight;
 	unsigned marked;
+	unsigned parents;
+	unsigned visited : 1;
+	struct commit_list *children;
 };
 
 #define DEBUG_BISECT 0
@@ -110,16 +113,6 @@ static int count_interesting_parents(struct commit *commit)
 	return count;
 }
 
-static inline int halfway(struct commit *commit)
-{
-	/*
-	 * Don't short-cut something we are not going to return!
-	 */
-	if (commit->object.flags & TREESAME)
-		return 0;
-	return !distance_direction(commit);
-}
-
 #if !DEBUG_BISECT
 #define show_list(a,b,c) do { ; } while (0)
 #else
@@ -340,90 +333,168 @@ static void compute_all_weights(struct commit_list *list,
 	show_list("bisection 2 counted all", counted, list);
 }
 
-/* At the moment this is basically the same as compute_all_weights()
- * but with a halfway shortcut */
-static void compute_relevant_weights(struct commit_list *list,
-				     struct node_data *weights)
+static struct commit_list *build_reversed_dag(struct commit_list *list,
+					      struct node_data *nodes)
 {
-	int n, counted;
+	struct commit_list *sources = NULL;
 	struct commit_list *p;
-
-	counted = 0;
-
-	for (n = 0, p = list; p; p = p->next) {
+	int n = 0;
+	for (p = list; p; p = p->next)
+		p->item->util = &nodes[n++];
+	for (p = list; p; p = p->next) {
+		struct commit_list *parent;
 		struct commit *commit = p->item;
-		unsigned flags = commit->object.flags;
-
-		commit->util = &weights[n++];
-		switch (count_interesting_parents(commit)) {
-		case 0:
-			if (!(flags & TREESAME)) {
-				node_data(commit)->weight = 1;
-				counted++;
-				show_list("bisection 2 count one",
-					  counted, list);
+		for (parent = commit->parents; parent; parent = parent->next) {
+			if (!(parent->item->object.flags & UNINTERESTING)) {
+				struct commit_list **next = &node_data(parent->item)->children;
+				commit_list_insert(commit, next);
+				node_data(commit)->parents++;
 			}
-			break;
-		case 1:
-			node_data(commit)->weight = -1;
-			break;
-		default:
-			node_data(commit)->weight = -2;
-			break;
 		}
 	}
 
-	show_list("bisection 2 initialize", counted, list);
-
+	/* find all sources */
 	for (p = list; p; p = p->next) {
-		if (!(p->item->object.flags & UNINTERESTING)
-		 && (node_data(p->item)->weight == -2)) {
-			compute_weight(p->item);
+		if (node_data(p->item)->parents == 0)
+			commit_list_insert(p->item, &sources);
+	}
 
-			/* Does it happen to be at exactly half-way? */
-			if (halfway(p->item))
-				return;
-			counted++;
+	return sources;
+}
+
+static inline void commit_list_insert_unique(struct commit *item,
+				      struct commit_list **list)
+{
+	if (!*list || item < (*list)->item) /* empty list or item will be first */
+		commit_list_insert(item, list);
+	else if (item != (*list)->item) { /* item will not be first or not inserted */
+		struct commit_list *p = *list;
+		for (; p->next && p->next->item < item; p = p->next);
+		if (!p->next || item != p->next->item) /* not already inserted */
+			commit_list_insert(item, &p->next);
+	}
+}
+
+/* do a traversal on the reversed DAG (starting from commits in queue),
+ * but stop at merge commits */
+static void traversal_up_to_merges(struct commit_list *queue,
+				   struct commit_list **merges)
+{
+	assert(queue);
+	while (queue) {
+		struct commit *top = queue->item;
+		struct commit_list *p;
+
+		pop_commit(&queue);
+
+		if (distance_direction(top) > 0) {
+			node_data(top)->visited = 1;
+
+			/* queue children */
+			for (p = node_data(top)->children; p; p = p->next) {
+				if (node_data(p->item)->parents > 1) /* child is a merge */
+					commit_list_insert_unique(p->item, merges);
+				else {
+					node_data(p->item)->weight = node_data(top)->weight;
+					if (!(p->item->object.flags & TREESAME))
+						node_data(p->item)->weight++;
+					commit_list_insert(p->item, &queue);
+				}
+			}
 		}
 	}
+}
 
-	show_list("bisection 2 compute_weight", counted, list);
+static inline int all_parents_are_visited(struct commit *merge)
+{
+	struct commit_list *p;
+	for (p = merge->parents; p; p = p->next) {
+		if (p->item->util && !node_data(p->item)->visited)
+			return 0;
+	}
+	return 1;
+}
 
-	while (counted < total) {
-		for (p = list; p; p = p->next) {
-			struct commit_list *q;
-			unsigned flags = p->item->object.flags;
+static struct commit *extract_merge_to_queue(struct commit_list **merges)
+{
+	assert(merges);
 
-			if (0 <= node_data(p->item)->weight)
-				continue;
-			for (q = p->item->parents; q; q = q->next) {
-				if (q->item->object.flags & UNINTERESTING)
-					continue;
-				if (0 <= node_data(q->item)->weight)
-					break;
-			}
-			if (!q)
-				continue;
+	struct commit_list *p, *q;
+	struct commit *found;
 
-			/*
-			 * weight for p is unknown but q is known.
-			 * add one for p itself if p is to be counted,
-			 * otherwise inherit it from q directly.
-			 */
-			node_data(p->item)->weight = node_data(q->item)->weight;
-			if (!(flags & TREESAME)) {
-				node_data(p->item)->weight++;
-				counted++;
-				show_list("bisection 2 count one",
-					  counted, list);
-			}
+	/* find a merge that is ready, i.e. all parents have been computed */
+	for (q = NULL, p = *merges; p && !all_parents_are_visited(p->item);
+	     q = p, p = p->next);
+	if (!p)
+		return NULL;
 
-			/* Does it happen to be at exactly half-way? */
-			if (halfway(p->item))
-				return;
+	/* remove that commit from the list and return it */
+	if (q) {
+		assert(q->next == p);
+		q->next = p->next;
+	} else /* found first element of list */
+		*merges = p->next;
+	found = p->item;
+	free(p);
+
+	return found;
+}
+
+static inline int find_new_queue_from_merges(struct commit_list **queue,
+				      struct commit_list **merges)
+{
+	if (*merges) {
+		struct commit *merge = extract_merge_to_queue(merges);
+		*queue = NULL;
+		if (merge) {
+			commit_list_insert(merge, queue);
+			return 1;
 		}
 	}
-	show_list("bisection 2 counted all", counted, list);
+	return 0;
+}
+
+static inline void compute_merge_weights(struct commit_list *merges)
+{
+	struct commit_list *p;
+	for (p = merges; p; p = p->next)
+		compute_weight(p->item);
+}
+
+static void bottom_up_traversal(struct commit_list *queue)
+{
+	struct commit_list *merges = NULL;
+	traversal_up_to_merges(queue, &merges);
+	while (find_new_queue_from_merges(&queue, &merges)) {
+		compute_merge_weights(queue);
+		traversal_up_to_merges(queue, &merges);
+	}
+
+	/* cleanup */
+	free_commit_list(merges);
+}
+
+/* The idea is to reverse the DAG and perform a modified breadth-first search
+ * on it, starting on all sources of the reversed DAG.
+ * Before each visit of a commit, its weight is induced.
+ * This only works for non-merge commits, so the traversal stops prematurely on
+ * merge commits (that are collected in a list).
+ * Merge commits from that collection are considered for further visits
+ * as soon as all parents have been visited.
+ * Their weights are computed using compute_weight().
+ * Each traversal ends when the computed weight is falling or halfway.
+ */
+static void compute_relevant_weights(struct commit_list *list,
+				     struct node_data *weights)
+{
+	struct commit_list *p;
+	struct commit_list *sources = build_reversed_dag(list, weights);
+
+	for (p = sources; p; p = p->next)
+		node_data(p->item)->weight = 1;
+	bottom_up_traversal(sources);
+
+	show_list("bisection 3 result", total, list);
 }
 
 struct commit_list *find_bisection(struct commit_list *list,
@@ -470,8 +541,11 @@ struct commit_list *find_bisection(struct commit_list *list,
 		compute_all_weights(list, weights);
 		best = best_bisection_sorted(list);
 	} else {
+		int i;
 		compute_relevant_weights(list, weights);
 		best = best_bisection(list);
+		for (i = 0; i < on_list; i++) /* cleanup */
+			free_commit_list(weights[i].children);
 	}
 	assert(best);
 	*reaches = node_data(best->item)->weight;