git-rev-list --bisect: optimization

[thirdparty/git.git] / builtin-rev-list.c

diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 723e4d419c64d3782b3612a1d1a7975e1f006146..b395ffeb03340af98f7f2c6447c850f7529d1cfb 100644 (file)
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -207,6 +207,160 @@ 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 *reaches, int *all)
+{
+       int n, nr, counted, distance;
+       struct commit_list *p, *best;
+       int *weights;
+
+       for (nr = 0, p = list; p; p = p->next) {
+               if (commit_interesting(p))
+                       nr++;
+       }
+       *all = 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);
+
+               /* Does it happen to be at exactly half-way? */
+               distance *= 2;
+               if (nr == distance || (nr+1) == distance) {
+                       p->next = NULL;
+                       *reaches = weight(p);
+                       free(weights);
+                       return p;
+               }
+               counted++;
+       }
+
+       while (counted < nr) {
+               for (p = list; p; p = p->next) {
+                       struct commit_list *q;
+
+                       if (!commit_interesting(p) || 0 < weight(p))
+                               continue;
+                       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++;
+
+                       /* Does it happen to be at exactly half-way? */
+                       distance = weight(p) * 2;
+                       if (nr == distance || (nr+1) == distance) {
+                               p->next = NULL;
+                               *reaches = weight(p);
+                               free(weights);
+                               return p;
+                       }
+               }
+       }
+
+       /* 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;
+                       *reaches = weight(p);
+               }
+       }
+       if (best)
+               best->next = NULL;
+       free(weights);
+       return best;
+}
+
 static void read_revisions_from_stdin(struct rev_info *revs)
 {
        char line[1000];
@@ -298,8 +452,12 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
        if (bisect_list) {
                int reaches = reaches, all = all;
 
-               revs.commits = find_bisection(revs.commits,
-                                             &reaches, &all);
+               if (!revs.prune_fn)
+                       revs.commits = find_bisection_2(revs.commits,
+                                                       &reaches, &all);
+               else
+                       revs.commits = find_bisection(revs.commits,
+                                                     &reaches, &all);
                if (bisect_show_vars) {
                        int cnt;
                        if (!revs.commits)