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