Re: [PATCH] Bisect: fix calculation of the number of suspicious revisions

From

Junio C Hamano <junkio@cox.net>

Date

Mar 22, 2007, 01:19 UTC

Message-ID

<7vlkhqxefy.fsf@assigned-by-dhcp.cox.net>

In-Reply-To

<Pine.LNX.4.64.0703211521290.6730@woody.linux-foundation.org>

Linus Torvalds <torvalds@linux-foundation.org> writes:

> (In fact, I would also suggest we drop or try to fix BISECT_NAMES support, 
> while at it - it never really worked, and iirc it was partly exactly 
> *because* of the end-condition not being handled right).

I am not opposed to dropping bisect-names.

---

run_one () {
	bisect=$($cmd --bisect $bad --not $good)
	ifgood=$(git-rev-list $bad --not $good $bisect | wc -l)
	ifbad=$(git-rev-list $bisect --not $good | wc -l)
	echo "bad $bad"
	echo "good $good"
	echo "ifgood $ifgood"
	echo "ifbad $ifbad"
	echo

	if test "$bisect" = "$bad"
	then
		false
	else
		case "$flip" in
		good)
			good="$good $bisect"
			flip=bad
			;;
		bad)
			bad="$bisect"
			flip=good
			;;
		esac
		true
	fi
}

while run_one
do
	:
done
-- >8 -- end of test script -- >8 --

 builtin-rev-list.c |  169 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 167 insertions(+), 2 deletions(-)

diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index c2db5a5..c43d88d 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -203,6 +203,167 @@ static struct commit_list *find_bisection(struct commit_list *list)
 	return best;
 }
 
+static inline int commit_interesting(struct commit_list *elem)
+{
+	unsigned flags = elem->item->object.flags;
+	if (flags & UNINTERESTING)
+		return 0;
+	return (!revs.prune_fn || (flags & TREECHANGE));
+}
+
+static inline int weight(struct commit_list *elem)
+{
+	return *((int*)(elem->item->util));
+}
+
+static inline void weight_set(struct commit_list *elem, int weight)
+{
+	*((int*)(elem->item->util)) = weight;
+}
+
+static int count_interesting_parents(struct commit_list *elem)
+{
+	int cnt = 0;
+	if (!elem->item->parents)
+		return cnt;
+	for (elem = elem->item->parents; elem; elem = elem->next) {
+		if (commit_interesting(elem))
+			cnt++;
+	}
+	return cnt;
+}
+
+static struct commit_list *find_bisection_2(struct commit_list *list)
+{
+	int n, nr, last_counted, counted, distance;
+	struct commit_list *p, *best;
+	int *weights;
+
+	for (nr = 0, p = list; p; p = p->next) {
+		if (commit_interesting(p))
+			nr++;
+	}
+	weights = xcalloc(nr, sizeof(int*));
+	counted = 0;
+
+	for (n = 0, p = list; p; p = p->next) {
+		if (!commit_interesting(p))
+			continue;
+		if (commit_interesting(p)) {
+			/*
+			 * positive weight is the number of interesting
+			 * commits it can reach, including itself.
+			 * weight = 0 means it has one parent and
+			 * its distance is unknown.
+			 * weight < 0 means it has more than one
+			 * parent and its distance is unknown.
+			 */
+			p->item->util = &weights[n++];
+			switch (count_interesting_parents(p)) {
+			case 0:
+				weight_set(p, 1);
+				counted++;
+				break;
+			case 1:
+				weight_set(p, 0);
+				break;
+			default:
+				weight_set(p, -1);
+				break;
+			}
+		}
+	}
+
+	/*
+	 * If you have only one parent in the resulting set
+	 * then you can reach one commit more than that parent
+	 * can reach.  So we do not have to run the expensive
+	 * count_distance() for single strand of pearls.
+	 *
+	 * However, if you have more than one parents, you cannot
+	 * just add their distance and one for yourself, since
+	 * they usually reach the same ancestor and you would
+	 * end up counting them twice that way.
+	 *
+	 * So we will first count distance of merges the usual
+	 * way, and then fill the blanks using cheaper algorithm.
+	 */
+	for (p = list; p; p = p->next) {
+		if (!commit_interesting(p))
+			continue;
+		n = weight(p);
+		if (0 <= n)
+			continue;
+		distance = count_distance(p);
+		clear_distance(p);
+		weight_set(p, distance);
+		distance = weight(p) * 2;
+		if (nr == distance || (nr+1) == distance) {
+			p->next = NULL;
+			free(weights);
+			return p;
+		}
+		counted++;
+	}
+
+	while (counted < nr) {
+		do {
+			last_counted = counted;
+			for (p = list; p; p = p->next) {
+				struct commit_list *q;
+
+				if (!commit_interesting(p) || 0 < weight(p))
+					continue;
+				if (weight(p) < 0)
+					die("OOPS");
+				for (q = p->item->parents;
+				     q;
+				     q = q->next)
+					if (commit_interesting(q) &&
+					    0 < weight(q))
+						break;
+				if (!q)
+					continue;
+				weight_set(p, weight(q)+1);
+				counted++;
+
+				/*
+				 * Do we happen to have found one that
+				 * has the desired half-weight?
+				 */
+				distance = weight(p) * 2;
+				if (nr == distance || (nr+1) == distance) {
+					p->next = NULL;
+					free(weights);
+					return p;
+				}
+			}
+		} while (counted != last_counted);
+
+	}
+
+	/* Then find the best one */
+	counted = 0;
+	best = list;
+	for (p = list; p; p = p->next) {
+		if (!commit_interesting(p))
+			continue;
+		distance = weight(p);
+		if (nr - distance < distance)
+			distance = nr - distance;
+		if (distance > counted) {
+			best = p;
+			counted = distance;
+		}
+	}
+	if (best) {
+		best->next = NULL;
+	}
+	free(weights);
+	return best;
+}
+
+
 static void read_revisions_from_stdin(struct rev_info *revs)
 {
 	char line[1000];
@@ -285,8 +446,12 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (revs.tree_objects)
 		mark_edges_uninteresting(revs.commits, &revs, show_edge);
 
-	if (bisect_list)
-		revs.commits = find_bisection(revs.commits);
+	if (bisect_list) {
+		if (!revs.prune_fn)
+			revs.commits = find_bisection_2(revs.commits);
+		else
+			revs.commits = find_bisection(revs.commits);
+	}
 
 	traverse_commit_list(&revs, show_commit, show_object);