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