X-Git-Url: https://git.verplant.org/?a=blobdiff_plain;f=rev-list.c;h=16920ef69e844697628ca3775403f86cc1c13945;hb=180926636e47ecfe28d03cec493af75899994f0f;hp=b526ad4e0d773066ee9cfa6c233b802ced468d2d;hpb=17ebe977d72290dcdc848b78ae2e65b59d4e1b4c;p=git.git

diff --git a/rev-list.c b/rev-list.c
index b526ad4e..16920ef6 100644
--- a/rev-list.c
+++ b/rev-list.c
@@ -4,6 +4,8 @@
 
 #define SEEN		(1u << 0)
 #define INTERESTING	(1u << 1)
+#define COUNTED		(1u << 2)
+#define SHOWN		(LAST_EPOCH_FLAG << 2)
 
 static const char rev_list_usage[] =
 	"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
@@ -14,6 +16,7 @@ static const char rev_list_usage[] =
 		      "  --pretty\n"
 		      "  --merge-order [ --show-breaks ]";
 
+static int bisect_list = 0;
 static int verbose_header = 0;
 static int show_parents = 0;
 static int hdr_termination = 0;
@@ -24,9 +27,11 @@ static int max_count = -1;
 static enum cmit_fmt commit_format = CMIT_FMT_RAW;
 static int merge_order = 0;
 static int show_breaks = 0;
+static int stop_traversal = 0;
 
 static void show_commit(struct commit *commit)
 {
+	commit->object.flags |= SHOWN;
 	if (show_breaks) {
 		prefix = "| ";
 		if (commit->object.flags & DISCONTINUITY) {
@@ -53,15 +58,22 @@ static void show_commit(struct commit *commit)
 
 static int filter_commit(struct commit * commit)
 {
-	if (commit->object.flags & UNINTERESTING)
+	if (merge_order && stop_traversal && commit->object.flags & BOUNDARY)
+		return STOP;
+	if (commit->object.flags & (UNINTERESTING|SHOWN))
 		return CONTINUE;
 	if (min_age != -1 && (commit->date > min_age))
 		return CONTINUE;
-	if (max_age != -1 && (commit->date < max_age))
-		return STOP;
+	if (max_age != -1 && (commit->date < max_age)) {
+		if (!merge_order)
+			return STOP;
+		else {
+			stop_traversal = 1;
+			return CONTINUE;
+		}
+	}
 	if (max_count != -1 && !max_count--)
 		return STOP;
-
 	return DO;
 }
 
@@ -115,6 +127,78 @@ static int everybody_uninteresting(struct commit_list *list)
 	return 1;
 }
 
+/*
+ * This is a truly stupid algorithm, but it's only
+ * used for bisection, and we just don't care enough.
+ *
+ * We care just barely enough to avoid recursing for
+ * non-merge entries.
+ */
+static int count_distance(struct commit_list *entry)
+{
+	int nr = 0;
+
+	while (entry) {
+		struct commit *commit = entry->item;
+		struct commit_list *p;
+
+		if (commit->object.flags & (UNINTERESTING | COUNTED))
+			break;
+		nr++;
+		commit->object.flags |= COUNTED;
+		p = commit->parents;
+		entry = p;
+		if (p) {
+			p = p->next;
+			while (p) {
+				nr += count_distance(p);
+				p = p->next;
+			}
+		}
+	}
+	return nr;
+}
+
+static void clear_distance(struct commit_list *list)
+{
+	while (list) {
+		struct commit *commit = list->item;
+		commit->object.flags &= ~COUNTED;
+		list = list->next;
+	}
+}
+
+static struct commit_list *find_bisection(struct commit_list *list)
+{
+	int nr, closest;
+	struct commit_list *p, *best;
+
+	nr = 0;
+	p = list;
+	while (p) {
+		nr++;
+		p = p->next;
+	}
+	closest = 0;
+	best = list;
+
+	p = list;
+	while (p) {
+		int distance = count_distance(p);
+		clear_distance(list);
+		if (nr - distance < distance)
+			distance = nr - distance;
+		if (distance > closest) {
+			best = p;
+			closest = distance;
+		}
+		p = p->next;
+	}
+	if (best)
+		best->next = NULL;
+	return best;
+}
+
 struct commit_list *limit_list(struct commit_list *list)
 {
 	struct commit_list *newlist = NULL;
@@ -131,6 +215,8 @@ struct commit_list *limit_list(struct commit_list *list)
 		}
 		p = &commit_list_insert(commit, p)->next;
 	} while (list);
+	if (bisect_list)
+		newlist = find_bisection(newlist);
 	return newlist;
 }
 
@@ -186,6 +272,10 @@ int main(int argc, char **argv)
 			show_parents = 1;
 			continue;
 		}
+		if (!strcmp(arg, "--bisect")) {
+			bisect_list = 1;
+			continue;
+		}
 		if (!strncmp(arg, "--merge-order", 13)) {
 		        merge_order = 1;
 			continue;