Andrew's git / gitweb.git / rev-list.c
?
rev-list.con commit [PATCH] Prevent git-rev-list without --merge-order producing duplicates in output (51b1e17)
   1#include "cache.h"
   2#include "commit.h"
   3#include "epoch.h"
   4
   5#define SEEN            (1u << 0)
   6#define INTERESTING     (1u << 1)
   7#define COUNTED         (1u << 2)
   8#define SHOWN           (LAST_EPOCH_FLAG << 2)
   9
  10static const char rev_list_usage[] =
  11        "usage: git-rev-list [OPTION] commit-id <commit-id>\n"
  12                      "  --max-count=nr\n"
  13                      "  --max-age=epoch\n"
  14                      "  --min-age=epoch\n"
  15                      "  --header\n"
  16                      "  --pretty\n"
  17                      "  --merge-order [ --show-breaks ]";
  18
  19static int bisect_list = 0;
  20static int verbose_header = 0;
  21static int show_parents = 0;
  22static int hdr_termination = 0;
  23static const char *prefix = "";
  24static unsigned long max_age = -1;
  25static unsigned long min_age = -1;
  26static int max_count = -1;
  27static enum cmit_fmt commit_format = CMIT_FMT_RAW;
  28static int merge_order = 0;
  29static int show_breaks = 0;
  30
  31static void show_commit(struct commit *commit)
  32{
  33        commit->object.flags |= SHOWN;
  34        if (show_breaks) {
  35                prefix = "| ";
  36                if (commit->object.flags & DISCONTINUITY) {
  37                        prefix = "^ ";     
  38                } else if (commit->object.flags & BOUNDARY) {
  39                        prefix = "= ";
  40                } 
  41        }                       
  42        printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
  43        if (show_parents) {
  44                struct commit_list *parents = commit->parents;
  45                while (parents) {
  46                        printf(" %s", sha1_to_hex(parents->item->object.sha1));
  47                        parents = parents->next;
  48                }
  49        }
  50        putchar('\n');
  51        if (verbose_header) {
  52                static char pretty_header[16384];
  53                pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header));
  54                printf("%s%c", pretty_header, hdr_termination);
  55        }       
  56}
  57
  58static int filter_commit(struct commit * commit)
  59{
  60        if (commit->object.flags & (UNINTERESTING|SHOWN))
  61                return CONTINUE;
  62        if (min_age != -1 && (commit->date > min_age))
  63                return CONTINUE;
  64        if (max_age != -1 && (commit->date < max_age))
  65                return STOP;
  66        if (max_count != -1 && !max_count--)
  67                return STOP;
  68        return DO;
  69}
  70
  71static int process_commit(struct commit * commit)
  72{
  73        int action=filter_commit(commit);
  74
  75        if (action == STOP) {
  76                return STOP;
  77        }
  78
  79        if (action == CONTINUE) {
  80                return CONTINUE;
  81        }
  82
  83        show_commit(commit);
  84
  85        return CONTINUE;
  86}
  87
  88static void show_commit_list(struct commit_list *list)
  89{
  90        while (list) {
  91                struct commit *commit = pop_most_recent_commit(&list, SEEN);
  92
  93                if (process_commit(commit) == STOP)
  94                        break;
  95        }
  96}
  97
  98static void mark_parents_uninteresting(struct commit *commit)
  99{
 100        struct commit_list *parents = commit->parents;
 101
 102        while (parents) {
 103                struct commit *commit = parents->item;
 104                commit->object.flags |= UNINTERESTING;
 105                parents = parents->next;
 106        }
 107}
 108
 109static int everybody_uninteresting(struct commit_list *list)
 110{
 111        while (list) {
 112                struct commit *commit = list->item;
 113                list = list->next;
 114                if (commit->object.flags & UNINTERESTING)
 115                        continue;
 116                return 0;
 117        }
 118        return 1;
 119}
 120
 121/*
 122 * This is a truly stupid algorithm, but it's only
 123 * used for bisection, and we just don't care enough.
 124 *
 125 * We care just barely enough to avoid recursing for
 126 * non-merge entries.
 127 */
 128static int count_distance(struct commit_list *entry)
 129{
 130        int nr = 0;
 131
 132        while (entry) {
 133                struct commit *commit = entry->item;
 134                struct commit_list *p;
 135
 136                if (commit->object.flags & (UNINTERESTING | COUNTED))
 137                        break;
 138                nr++;
 139                commit->object.flags |= COUNTED;
 140                p = commit->parents;
 141                entry = p;
 142                if (p) {
 143                        p = p->next;
 144                        while (p) {
 145                                nr += count_distance(p);
 146                                p = p->next;
 147                        }
 148                }
 149        }
 150        return nr;
 151}
 152
 153static void clear_distance(struct commit_list *list)
 154{
 155        while (list) {
 156                struct commit *commit = list->item;
 157                commit->object.flags &= ~COUNTED;
 158                list = list->next;
 159        }
 160}
 161
 162static struct commit_list *find_bisection(struct commit_list *list)
 163{
 164        int nr, closest;
 165        struct commit_list *p, *best;
 166
 167        nr = 0;
 168        p = list;
 169        while (p) {
 170                nr++;
 171                p = p->next;
 172        }
 173        closest = 0;
 174        best = list;
 175
 176        p = list;
 177        while (p) {
 178                int distance = count_distance(p);
 179                clear_distance(list);
 180                if (nr - distance < distance)
 181                        distance = nr - distance;
 182                if (distance > closest) {
 183                        best = p;
 184                        closest = distance;
 185                }
 186                p = p->next;
 187        }
 188        if (best)
 189                best->next = NULL;
 190        return best;
 191}
 192
 193struct commit_list *limit_list(struct commit_list *list)
 194{
 195        struct commit_list *newlist = NULL;
 196        struct commit_list **p = &newlist;
 197        do {
 198                struct commit *commit = pop_most_recent_commit(&list, SEEN);
 199                struct object *obj = &commit->object;
 200
 201                if (obj->flags & UNINTERESTING) {
 202                        mark_parents_uninteresting(commit);
 203                        if (everybody_uninteresting(list))
 204                                break;
 205                        continue;
 206                }
 207                p = &commit_list_insert(commit, p)->next;
 208        } while (list);
 209        if (bisect_list)
 210                newlist = find_bisection(newlist);
 211        return newlist;
 212}
 213
 214static enum cmit_fmt get_commit_format(const char *arg)
 215{
 216        if (!*arg)
 217                return CMIT_FMT_DEFAULT;
 218        if (!strcmp(arg, "=raw"))
 219                return CMIT_FMT_RAW;
 220        if (!strcmp(arg, "=medium"))
 221                return CMIT_FMT_MEDIUM;
 222        if (!strcmp(arg, "=short"))
 223                return CMIT_FMT_SHORT;
 224        usage(rev_list_usage);  
 225}                       
 226
 227
 228int main(int argc, char **argv)
 229{
 230        struct commit_list *list = NULL;
 231        int i, limited = 0;
 232
 233        for (i = 1 ; i < argc; i++) {
 234                int flags;
 235                char *arg = argv[i];
 236                unsigned char sha1[20];
 237                struct commit *commit;
 238
 239                if (!strncmp(arg, "--max-count=", 12)) {
 240                        max_count = atoi(arg + 12);
 241                        continue;
 242                }
 243                if (!strncmp(arg, "--max-age=", 10)) {
 244                        max_age = atoi(arg + 10);
 245                        continue;
 246                }
 247                if (!strncmp(arg, "--min-age=", 10)) {
 248                        min_age = atoi(arg + 10);
 249                        continue;
 250                }
 251                if (!strcmp(arg, "--header")) {
 252                        verbose_header = 1;
 253                        continue;
 254                }
 255                if (!strncmp(arg, "--pretty", 8)) {
 256                        commit_format = get_commit_format(arg+8);
 257                        verbose_header = 1;
 258                        hdr_termination = '\n';
 259                        prefix = "commit ";
 260                        continue;
 261                }
 262                if (!strcmp(arg, "--parents")) {
 263                        show_parents = 1;
 264                        continue;
 265                }
 266                if (!strcmp(arg, "--bisect")) {
 267                        bisect_list = 1;
 268                        continue;
 269                }
 270                if (!strncmp(arg, "--merge-order", 13)) {
 271                        merge_order = 1;
 272                        continue;
 273                }
 274                if (!strncmp(arg, "--show-breaks", 13)) {
 275                        show_breaks = 1;
 276                        continue;
 277                }
 278
 279                flags = 0;
 280                if (*arg == '^') {
 281                        flags = UNINTERESTING;
 282                        arg++;
 283                        limited = 1;
 284                }
 285                if (get_sha1(arg, sha1) || (show_breaks && !merge_order))
 286                        usage(rev_list_usage);
 287                commit = lookup_commit_reference(sha1);
 288                if (!commit || parse_commit(commit) < 0)
 289                        die("bad commit object %s", arg);
 290                commit->object.flags |= flags;
 291                commit_list_insert(commit, &list);
 292        }
 293
 294        if (!list)
 295                usage(rev_list_usage);
 296
 297        if (!merge_order) {             
 298                if (limited)
 299                        list = limit_list(list);
 300                show_commit_list(list);
 301        } else {
 302                if (sort_list_in_merge_order(list, &process_commit)) {
 303                          die("merge order sort failed\n");
 304                }
 305        }
 306
 307        return 0;
 308}