[PATCH] Pull refs by HTTP

diff --git a/rev-list.c b/rev-list.c
index c27b138f3a16fbe689376959ffd62e898b4d8756..16920ef69e844697628ca3775403f86cc1c13945 100644 (file)
--- 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;
@@ -214,17 +304,13 @@ int main(int argc, char **argv)
                usage(rev_list_usage);
 
        if (!merge_order) {             
-       
-               if (limited) 
+               if (limited)
                        list = limit_list(list);
                show_commit_list(list);
-                       
        } else {
-               
                if (sort_list_in_merge_order(list, &process_commit)) {
                          die("merge order sort failed\n");
                }
-                                       
        }
 
        return 0;