[PATCH] add *--no-merges* flag to suppress display of merge commits
[git] / rev-list.c
1 #include "cache.h"
2 #include "tag.h"
3 #include "commit.h"
4 #include "tree.h"
5 #include "blob.h"
6 #include "epoch.h"
7
8 #define SEEN            (1u << 0)
9 #define INTERESTING     (1u << 1)
10 #define COUNTED         (1u << 2)
11 #define SHOWN           (1u << 3)
12
13 static const char rev_list_usage[] =
14         "git-rev-list [OPTION] commit-id <commit-id>\n"
15                       "  --max-count=nr\n"
16                       "  --max-age=epoch\n"
17                       "  --min-age=epoch\n"
18                       "  --parents\n"
19                       "  --bisect\n"
20                       "  --objects\n"
21                       "  --unpacked\n"
22                       "  --header\n"
23                       "  --pretty\n"
24                       "  --no-merges\n"
25                       "  --merge-order [ --show-breaks ]\n"
26                       "  --topo-order";
27
28 static int unpacked = 0;
29 static int bisect_list = 0;
30 static int tag_objects = 0;
31 static int tree_objects = 0;
32 static int blob_objects = 0;
33 static int verbose_header = 0;
34 static int show_parents = 0;
35 static int hdr_termination = 0;
36 static const char *prefix = "";
37 static unsigned long max_age = -1;
38 static unsigned long min_age = -1;
39 static int max_count = -1;
40 static enum cmit_fmt commit_format = CMIT_FMT_RAW;
41 static int merge_order = 0;
42 static int show_breaks = 0;
43 static int stop_traversal = 0;
44 static int topo_order = 0;
45 static int no_merges = 0;
46
47 static void show_commit(struct commit *commit)
48 {
49         commit->object.flags |= SHOWN;
50         if (show_breaks) {
51                 prefix = "| ";
52                 if (commit->object.flags & DISCONTINUITY) {
53                         prefix = "^ ";     
54                 } else if (commit->object.flags & BOUNDARY) {
55                         prefix = "= ";
56                 } 
57         }                       
58         printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
59         if (show_parents) {
60                 struct commit_list *parents = commit->parents;
61                 while (parents) {
62                         printf(" %s", sha1_to_hex(parents->item->object.sha1));
63                         parents = parents->next;
64                 }
65         }
66         putchar('\n');
67         if (verbose_header) {
68                 static char pretty_header[16384];
69                 pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header));
70                 printf("%s%c", pretty_header, hdr_termination);
71         }
72         fflush(stdout);
73 }
74
75 static int filter_commit(struct commit * commit)
76 {
77         if (stop_traversal && (commit->object.flags & BOUNDARY))
78                 return STOP;
79         if (commit->object.flags & (UNINTERESTING|SHOWN))
80                 return CONTINUE;
81         if (min_age != -1 && (commit->date > min_age))
82                 return CONTINUE;
83         if (max_age != -1 && (commit->date < max_age)) {
84                 stop_traversal=1;
85                 return merge_order?CONTINUE:STOP;
86         }
87         if (max_count != -1 && !max_count--)
88                 return STOP;
89         if (no_merges && (commit->parents && commit->parents->next))
90                 return CONTINUE;
91         return DO;
92 }
93
94 static int process_commit(struct commit * commit)
95 {
96         int action=filter_commit(commit);
97
98         if (action == STOP) {
99                 return STOP;
100         }
101
102         if (action == CONTINUE) {
103                 return CONTINUE;
104         }
105
106         show_commit(commit);
107
108         return CONTINUE;
109 }
110
111 static struct object_list **add_object(struct object *obj, struct object_list **p, const char *name)
112 {
113         struct object_list *entry = xmalloc(sizeof(*entry));
114         entry->item = obj;
115         entry->next = *p;
116         entry->name = name;
117         *p = entry;
118         return &entry->next;
119 }
120
121 static struct object_list **process_blob(struct blob *blob, struct object_list **p, const char *name)
122 {
123         struct object *obj = &blob->object;
124
125         if (!blob_objects)
126                 return p;
127         if (obj->flags & (UNINTERESTING | SEEN))
128                 return p;
129         obj->flags |= SEEN;
130         return add_object(obj, p, name);
131 }
132
133 static struct object_list **process_tree(struct tree *tree, struct object_list **p, const char *name)
134 {
135         struct object *obj = &tree->object;
136         struct tree_entry_list *entry;
137
138         if (!tree_objects)
139                 return p;
140         if (obj->flags & (UNINTERESTING | SEEN))
141                 return p;
142         if (parse_tree(tree) < 0)
143                 die("bad tree object %s", sha1_to_hex(obj->sha1));
144         obj->flags |= SEEN;
145         p = add_object(obj, p, name);
146         for (entry = tree->entries ; entry ; entry = entry->next) {
147                 if (entry->directory)
148                         p = process_tree(entry->item.tree, p, entry->name);
149                 else
150                         p = process_blob(entry->item.blob, p, entry->name);
151         }
152         return p;
153 }
154
155 static struct object_list *pending_objects = NULL;
156
157 static void show_commit_list(struct commit_list *list)
158 {
159         struct object_list *objects = NULL, **p = &objects, *pending;
160         while (list) {
161                 struct commit *commit = pop_most_recent_commit(&list, SEEN);
162
163                 p = process_tree(commit->tree, p, "");
164                 if (process_commit(commit) == STOP)
165                         break;
166         }
167         for (pending = pending_objects; pending; pending = pending->next) {
168                 struct object *obj = pending->item;
169                 const char *name = pending->name;
170                 if (obj->flags & (UNINTERESTING | SEEN))
171                         continue;
172                 if (obj->type == tag_type) {
173                         obj->flags |= SEEN;
174                         p = add_object(obj, p, name);
175                         continue;
176                 }
177                 if (obj->type == tree_type) {
178                         p = process_tree((struct tree *)obj, p, name);
179                         continue;
180                 }
181                 if (obj->type == blob_type) {
182                         p = process_blob((struct blob *)obj, p, name);
183                         continue;
184                 }
185                 die("unknown pending object %s (%s)", sha1_to_hex(obj->sha1), name);
186         }
187         while (objects) {
188                 printf("%s %s\n", sha1_to_hex(objects->item->sha1), objects->name);
189                 objects = objects->next;
190         }
191 }
192
193 static void mark_blob_uninteresting(struct blob *blob)
194 {
195         if (!blob_objects)
196                 return;
197         if (blob->object.flags & UNINTERESTING)
198                 return;
199         blob->object.flags |= UNINTERESTING;
200 }
201
202 static void mark_tree_uninteresting(struct tree *tree)
203 {
204         struct object *obj = &tree->object;
205         struct tree_entry_list *entry;
206
207         if (!tree_objects)
208                 return;
209         if (obj->flags & UNINTERESTING)
210                 return;
211         obj->flags |= UNINTERESTING;
212         if (!has_sha1_file(obj->sha1))
213                 return;
214         if (parse_tree(tree) < 0)
215                 die("bad tree %s", sha1_to_hex(obj->sha1));
216         entry = tree->entries;
217         while (entry) {
218                 if (entry->directory)
219                         mark_tree_uninteresting(entry->item.tree);
220                 else
221                         mark_blob_uninteresting(entry->item.blob);
222                 entry = entry->next;
223         }
224 }
225
226 static void mark_parents_uninteresting(struct commit *commit)
227 {
228         struct commit_list *parents = commit->parents;
229
230         if (tree_objects)
231                 mark_tree_uninteresting(commit->tree);
232         while (parents) {
233                 struct commit *commit = parents->item;
234                 commit->object.flags |= UNINTERESTING;
235
236                 /*
237                  * Normally we haven't parsed the parent
238                  * yet, so we won't have a parent of a parent
239                  * here. However, it may turn out that we've
240                  * reached this commit some other way (where it
241                  * wasn't uninteresting), in which case we need
242                  * to mark its parents recursively too..
243                  */
244                 if (commit->parents)
245                         mark_parents_uninteresting(commit);
246
247                 /*
248                  * A missing commit is ok iff its parent is marked 
249                  * uninteresting.
250                  *
251                  * We just mark such a thing parsed, so that when
252                  * it is popped next time around, we won't be trying
253                  * to parse it and get an error.
254                  */
255                 if (!has_sha1_file(commit->object.sha1))
256                         commit->object.parsed = 1;
257                 parents = parents->next;
258         }
259 }
260
261 static int everybody_uninteresting(struct commit_list *orig)
262 {
263         struct commit_list *list = orig;
264         while (list) {
265                 struct commit *commit = list->item;
266                 list = list->next;
267                 if (commit->object.flags & UNINTERESTING)
268                         continue;
269                 return 0;
270         }
271
272         /*
273          * Ok, go back and mark all the edge trees uninteresting,
274          * since otherwise we can have situations where a parent
275          * that was marked uninteresting (and we never even had
276          * to look at) had lots of objects that we don't want to
277          * include.
278          *
279          * NOTE! This still doesn't mean that the object list is
280          * "correct", since we may end up listing objects that
281          * even older commits (that we don't list) do actually
282          * reference, but it gets us to a minimal list (or very
283          * close) in practice.
284          */
285         if (!tree_objects)
286                 return 1;
287
288         while (orig) {
289                 struct commit *commit = orig->item;
290                 if (!parse_commit(commit) && commit->tree)
291                         mark_tree_uninteresting(commit->tree);
292                 orig = orig->next;
293         }
294         return 1;
295 }
296
297 /*
298  * This is a truly stupid algorithm, but it's only
299  * used for bisection, and we just don't care enough.
300  *
301  * We care just barely enough to avoid recursing for
302  * non-merge entries.
303  */
304 static int count_distance(struct commit_list *entry)
305 {
306         int nr = 0;
307
308         while (entry) {
309                 struct commit *commit = entry->item;
310                 struct commit_list *p;
311
312                 if (commit->object.flags & (UNINTERESTING | COUNTED))
313                         break;
314                 nr++;
315                 commit->object.flags |= COUNTED;
316                 p = commit->parents;
317                 entry = p;
318                 if (p) {
319                         p = p->next;
320                         while (p) {
321                                 nr += count_distance(p);
322                                 p = p->next;
323                         }
324                 }
325         }
326         return nr;
327 }
328
329 static void clear_distance(struct commit_list *list)
330 {
331         while (list) {
332                 struct commit *commit = list->item;
333                 commit->object.flags &= ~COUNTED;
334                 list = list->next;
335         }
336 }
337
338 static struct commit_list *find_bisection(struct commit_list *list)
339 {
340         int nr, closest;
341         struct commit_list *p, *best;
342
343         nr = 0;
344         p = list;
345         while (p) {
346                 nr++;
347                 p = p->next;
348         }
349         closest = 0;
350         best = list;
351
352         p = list;
353         while (p) {
354                 int distance = count_distance(p);
355                 clear_distance(list);
356                 if (nr - distance < distance)
357                         distance = nr - distance;
358                 if (distance > closest) {
359                         best = p;
360                         closest = distance;
361                 }
362                 p = p->next;
363         }
364         if (best)
365                 best->next = NULL;
366         return best;
367 }
368
369 static struct commit_list *limit_list(struct commit_list *list)
370 {
371         struct commit_list *newlist = NULL;
372         struct commit_list **p = &newlist;
373         while (list) {
374                 struct commit *commit = pop_most_recent_commit(&list, SEEN);
375                 struct object *obj = &commit->object;
376
377                 if (unpacked && has_sha1_pack(obj->sha1))
378                         obj->flags |= UNINTERESTING;
379                 if (obj->flags & UNINTERESTING) {
380                         mark_parents_uninteresting(commit);
381                         if (everybody_uninteresting(list))
382                                 break;
383                         continue;
384                 }
385                 p = &commit_list_insert(commit, p)->next;
386         }
387         if (bisect_list)
388                 newlist = find_bisection(newlist);
389         return newlist;
390 }
391
392 static void add_pending_object(struct object *obj, const char *name)
393 {
394         add_object(obj, &pending_objects, name);
395 }
396
397 static struct commit *get_commit_reference(const char *name, unsigned int flags)
398 {
399         unsigned char sha1[20];
400         struct object *object;
401
402         if (get_sha1(name, sha1))
403                 usage(rev_list_usage);
404         object = parse_object(sha1);
405         if (!object)
406                 die("bad object %s", name);
407
408         /*
409          * Tag object? Look what it points to..
410          */
411         while (object->type == tag_type) {
412                 struct tag *tag = (struct tag *) object;
413                 object->flags |= flags;
414                 if (tag_objects && !(object->flags & UNINTERESTING))
415                         add_pending_object(object, tag->tag);
416                 object = parse_object(tag->tagged->sha1);
417         }
418
419         /*
420          * Commit object? Just return it, we'll do all the complex
421          * reachability crud.
422          */
423         if (object->type == commit_type) {
424                 struct commit *commit = (struct commit *)object;
425                 object->flags |= flags;
426                 if (parse_commit(commit) < 0)
427                         die("unable to parse commit %s", name);
428                 if (flags & UNINTERESTING)
429                         mark_parents_uninteresting(commit);
430                 return commit;
431         }
432
433         /*
434          * Tree object? Either mark it uniniteresting, or add it
435          * to the list of objects to look at later..
436          */
437         if (object->type == tree_type) {
438                 struct tree *tree = (struct tree *)object;
439                 if (!tree_objects)
440                         return NULL;
441                 if (flags & UNINTERESTING) {
442                         mark_tree_uninteresting(tree);
443                         return NULL;
444                 }
445                 add_pending_object(object, "");
446                 return NULL;
447         }
448
449         /*
450          * Blob object? You know the drill by now..
451          */
452         if (object->type == blob_type) {
453                 struct blob *blob = (struct blob *)object;
454                 if (!blob_objects)
455                         return NULL;
456                 if (flags & UNINTERESTING) {
457                         mark_blob_uninteresting(blob);
458                         return NULL;
459                 }
460                 add_pending_object(object, "");
461                 return NULL;
462         }
463         die("%s is unknown object", name);
464 }
465
466 static void handle_one_commit(struct commit *com, struct commit_list **lst)
467 {
468         if (!com || com->object.flags & SEEN)
469                 return;
470         com->object.flags |= SEEN;
471         commit_list_insert(com, lst);
472 }
473
474
475 int main(int argc, char **argv)
476 {
477         struct commit_list *list = NULL;
478         int i, limited = 0;
479
480         for (i = 1 ; i < argc; i++) {
481                 int flags;
482                 char *arg = argv[i];
483                 char *dotdot;
484                 struct commit *commit;
485
486                 if (!strncmp(arg, "--max-count=", 12)) {
487                         max_count = atoi(arg + 12);
488                         continue;
489                 }
490                 if (!strncmp(arg, "--max-age=", 10)) {
491                         max_age = atoi(arg + 10);
492                         continue;
493                 }
494                 if (!strncmp(arg, "--min-age=", 10)) {
495                         min_age = atoi(arg + 10);
496                         continue;
497                 }
498                 if (!strcmp(arg, "--header")) {
499                         verbose_header = 1;
500                         continue;
501                 }
502                 if (!strncmp(arg, "--pretty", 8)) {
503                         commit_format = get_commit_format(arg+8);
504                         verbose_header = 1;
505                         hdr_termination = '\n';
506                         prefix = "commit ";
507                         continue;
508                 }
509                 if (!strncmp(arg, "--no-merges", 11)) {
510                         no_merges = 1;
511                         continue;
512                 }
513                 if (!strcmp(arg, "--parents")) {
514                         show_parents = 1;
515                         continue;
516                 }
517                 if (!strcmp(arg, "--bisect")) {
518                         bisect_list = 1;
519                         continue;
520                 }
521                 if (!strcmp(arg, "--objects")) {
522                         tag_objects = 1;
523                         tree_objects = 1;
524                         blob_objects = 1;
525                         continue;
526                 }
527                 if (!strcmp(arg, "--unpacked")) {
528                         unpacked = 1;
529                         limited = 1;
530                         continue;
531                 }
532                 if (!strcmp(arg, "--merge-order")) {
533                         merge_order = 1;
534                         continue;
535                 }
536                 if (!strcmp(arg, "--show-breaks")) {
537                         show_breaks = 1;
538                         continue;
539                 }
540                 if (!strcmp(arg, "--topo-order")) {
541                         topo_order = 1;
542                         limited = 1;
543                         continue;
544                 }
545
546                 if (show_breaks && !merge_order)
547                         usage(rev_list_usage);
548
549                 flags = 0;
550                 dotdot = strstr(arg, "..");
551                 if (dotdot) {
552                         char *next = dotdot + 2;
553                         struct commit *exclude = NULL;
554                         struct commit *include = NULL;
555                         *dotdot = 0;
556                         exclude = get_commit_reference(arg, UNINTERESTING);
557                         include = get_commit_reference(next, 0);
558                         if (exclude && include) {
559                                 limited = 1;
560                                 handle_one_commit(exclude, &list);
561                                 handle_one_commit(include, &list);
562                                 continue;
563                         }
564                         *next = '.';
565                 }
566                 if (*arg == '^') {
567                         flags = UNINTERESTING;
568                         arg++;
569                         limited = 1;
570                 }
571                 commit = get_commit_reference(arg, flags);
572                 handle_one_commit(commit, &list);
573         }
574
575         if (!merge_order) {             
576                 sort_by_date(&list);
577                 if (limited)
578                         list = limit_list(list);
579                 if (topo_order)
580                         sort_in_topological_order(&list);
581                 show_commit_list(list);
582         } else {
583 #ifndef NO_OPENSSL
584                 if (sort_list_in_merge_order(list, &process_commit)) {
585                         die("merge order sort failed\n");
586                 }
587 #else
588                 die("merge order sort unsupported, OpenSSL not linked");
589 #endif
590         }
591
592         return 0;
593 }