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