]>
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) |
51b1e171 | 11 | #define SHOWN (LAST_EPOCH_FLAG << 2) |
8906300f | 12 | |
a6f68d47 LT |
13 | static const char rev_list_usage[] = |
14 | "usage: git-rev-list [OPTION] commit-id <commit-id>\n" | |
15 | " --max-count=nr\n" | |
16 | " --max-age=epoch\n" | |
17 | " --min-age=epoch\n" | |
9d97aa64 | 18 | " --header\n" |
a3437b8c JS |
19 | " --pretty\n" |
20 | " --merge-order [ --show-breaks ]"; | |
a6f68d47 | 21 | |
8b3a1e05 | 22 | static int bisect_list = 0; |
3c90f03d | 23 | static int tag_objects = 0; |
9de48752 LT |
24 | static int tree_objects = 0; |
25 | static int blob_objects = 0; | |
81f2bb1f LT |
26 | static int verbose_header = 0; |
27 | static int show_parents = 0; | |
81f2bb1f LT |
28 | static int hdr_termination = 0; |
29 | static const char *prefix = ""; | |
30 | static unsigned long max_age = -1; | |
31 | static unsigned long min_age = -1; | |
32 | static int max_count = -1; | |
000182ea | 33 | static enum cmit_fmt commit_format = CMIT_FMT_RAW; |
a3437b8c JS |
34 | static int merge_order = 0; |
35 | static int show_breaks = 0; | |
5e749e25 | 36 | static int stop_traversal = 0; |
81f2bb1f LT |
37 | |
38 | static void show_commit(struct commit *commit) | |
39 | { | |
51b1e171 | 40 | commit->object.flags |= SHOWN; |
a3437b8c JS |
41 | if (show_breaks) { |
42 | prefix = "| "; | |
43 | if (commit->object.flags & DISCONTINUITY) { | |
44 | prefix = "^ "; | |
45 | } else if (commit->object.flags & BOUNDARY) { | |
46 | prefix = "= "; | |
47 | } | |
48 | } | |
81f2bb1f LT |
49 | printf("%s%s", prefix, sha1_to_hex(commit->object.sha1)); |
50 | if (show_parents) { | |
51 | struct commit_list *parents = commit->parents; | |
52 | while (parents) { | |
53 | printf(" %s", sha1_to_hex(parents->item->object.sha1)); | |
54 | parents = parents->next; | |
55 | } | |
56 | } | |
57 | putchar('\n'); | |
58 | if (verbose_header) { | |
000182ea LT |
59 | static char pretty_header[16384]; |
60 | pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header)); | |
61 | printf("%s%c", pretty_header, hdr_termination); | |
a3437b8c JS |
62 | } |
63 | } | |
64 | ||
65 | static int filter_commit(struct commit * commit) | |
66 | { | |
5e749e25 JS |
67 | if (merge_order && stop_traversal && commit->object.flags & BOUNDARY) |
68 | return STOP; | |
51b1e171 | 69 | if (commit->object.flags & (UNINTERESTING|SHOWN)) |
a3437b8c JS |
70 | return CONTINUE; |
71 | if (min_age != -1 && (commit->date > min_age)) | |
72 | return CONTINUE; | |
5e749e25 JS |
73 | if (max_age != -1 && (commit->date < max_age)) { |
74 | if (!merge_order) | |
75 | return STOP; | |
76 | else { | |
77 | stop_traversal = 1; | |
78 | return CONTINUE; | |
79 | } | |
80 | } | |
a3437b8c JS |
81 | if (max_count != -1 && !max_count--) |
82 | return STOP; | |
a3437b8c JS |
83 | return DO; |
84 | } | |
85 | ||
86 | static int process_commit(struct commit * commit) | |
87 | { | |
88 | int action=filter_commit(commit); | |
89 | ||
90 | if (action == STOP) { | |
91 | return STOP; | |
92 | } | |
93 | ||
94 | if (action == CONTINUE) { | |
95 | return CONTINUE; | |
81f2bb1f | 96 | } |
a3437b8c JS |
97 | |
98 | show_commit(commit); | |
99 | ||
100 | return CONTINUE; | |
81f2bb1f LT |
101 | } |
102 | ||
9ce43d1c | 103 | static struct object_list **add_object(struct object *obj, struct object_list **p, const char *name) |
9de48752 LT |
104 | { |
105 | struct object_list *entry = xmalloc(sizeof(*entry)); | |
106 | entry->item = obj; | |
36f8d174 | 107 | entry->next = *p; |
9ce43d1c | 108 | entry->name = name; |
9de48752 LT |
109 | *p = entry; |
110 | return &entry->next; | |
111 | } | |
112 | ||
9ce43d1c | 113 | static struct object_list **process_blob(struct blob *blob, struct object_list **p, const char *name) |
9de48752 LT |
114 | { |
115 | struct object *obj = &blob->object; | |
116 | ||
117 | if (!blob_objects) | |
118 | return p; | |
119 | if (obj->flags & (UNINTERESTING | SEEN)) | |
120 | return p; | |
121 | obj->flags |= SEEN; | |
9ce43d1c | 122 | return add_object(obj, p, name); |
9de48752 LT |
123 | } |
124 | ||
9ce43d1c | 125 | static struct object_list **process_tree(struct tree *tree, struct object_list **p, const char *name) |
9de48752 LT |
126 | { |
127 | struct object *obj = &tree->object; | |
128 | struct tree_entry_list *entry; | |
129 | ||
130 | if (!tree_objects) | |
131 | return p; | |
132 | if (obj->flags & (UNINTERESTING | SEEN)) | |
133 | return p; | |
134 | if (parse_tree(tree) < 0) | |
135 | die("bad tree object %s", sha1_to_hex(obj->sha1)); | |
136 | obj->flags |= SEEN; | |
9ce43d1c | 137 | p = add_object(obj, p, name); |
9de48752 LT |
138 | for (entry = tree->entries ; entry ; entry = entry->next) { |
139 | if (entry->directory) | |
9ce43d1c | 140 | p = process_tree(entry->item.tree, p, entry->name); |
9de48752 | 141 | else |
9ce43d1c | 142 | p = process_blob(entry->item.blob, p, entry->name); |
9de48752 LT |
143 | } |
144 | return p; | |
145 | } | |
146 | ||
36f8d174 LT |
147 | static struct object_list *pending_objects = NULL; |
148 | ||
81f2bb1f LT |
149 | static void show_commit_list(struct commit_list *list) |
150 | { | |
36f8d174 | 151 | struct object_list *objects = NULL, **p = &objects, *pending; |
81f2bb1f LT |
152 | while (list) { |
153 | struct commit *commit = pop_most_recent_commit(&list, SEEN); | |
154 | ||
9ce43d1c | 155 | p = process_tree(commit->tree, p, ""); |
a3437b8c | 156 | if (process_commit(commit) == STOP) |
81f2bb1f | 157 | break; |
81f2bb1f | 158 | } |
36f8d174 LT |
159 | for (pending = pending_objects; pending; pending = pending->next) { |
160 | struct object *obj = pending->item; | |
161 | const char *name = pending->name; | |
162 | if (obj->flags & (UNINTERESTING | SEEN)) | |
163 | continue; | |
164 | if (obj->type == tag_type) { | |
165 | obj->flags |= SEEN; | |
166 | p = add_object(obj, p, name); | |
167 | continue; | |
168 | } | |
169 | if (obj->type == tree_type) { | |
170 | p = process_tree((struct tree *)obj, p, name); | |
171 | continue; | |
172 | } | |
173 | if (obj->type == blob_type) { | |
174 | p = process_blob((struct blob *)obj, p, name); | |
175 | continue; | |
176 | } | |
177 | die("unknown pending object %s (%s)", sha1_to_hex(obj->sha1), name); | |
178 | } | |
9de48752 | 179 | while (objects) { |
9ce43d1c | 180 | printf("%s %s\n", sha1_to_hex(objects->item->sha1), objects->name); |
9de48752 LT |
181 | objects = objects->next; |
182 | } | |
183 | } | |
184 | ||
185 | static void mark_blob_uninteresting(struct blob *blob) | |
186 | { | |
187 | if (!blob_objects) | |
188 | return; | |
189 | if (blob->object.flags & UNINTERESTING) | |
190 | return; | |
191 | blob->object.flags |= UNINTERESTING; | |
192 | } | |
193 | ||
194 | static void mark_tree_uninteresting(struct tree *tree) | |
195 | { | |
196 | struct object *obj = &tree->object; | |
197 | struct tree_entry_list *entry; | |
198 | ||
199 | if (!tree_objects) | |
200 | return; | |
201 | if (obj->flags & UNINTERESTING) | |
202 | return; | |
203 | obj->flags |= UNINTERESTING; | |
204 | if (parse_tree(tree) < 0) | |
205 | die("bad tree %s", sha1_to_hex(obj->sha1)); | |
206 | entry = tree->entries; | |
207 | while (entry) { | |
208 | if (entry->directory) | |
209 | mark_tree_uninteresting(entry->item.tree); | |
210 | else | |
211 | mark_blob_uninteresting(entry->item.blob); | |
212 | entry = entry->next; | |
213 | } | |
81f2bb1f LT |
214 | } |
215 | ||
8906300f LT |
216 | static void mark_parents_uninteresting(struct commit *commit) |
217 | { | |
218 | struct commit_list *parents = commit->parents; | |
219 | ||
9de48752 LT |
220 | if (tree_objects) |
221 | mark_tree_uninteresting(commit->tree); | |
8906300f LT |
222 | while (parents) { |
223 | struct commit *commit = parents->item; | |
224 | commit->object.flags |= UNINTERESTING; | |
225 | parents = parents->next; | |
226 | } | |
227 | } | |
228 | ||
229 | static int everybody_uninteresting(struct commit_list *list) | |
230 | { | |
231 | while (list) { | |
232 | struct commit *commit = list->item; | |
233 | list = list->next; | |
234 | if (commit->object.flags & UNINTERESTING) | |
235 | continue; | |
236 | return 0; | |
237 | } | |
238 | return 1; | |
239 | } | |
240 | ||
8b3a1e05 LT |
241 | /* |
242 | * This is a truly stupid algorithm, but it's only | |
243 | * used for bisection, and we just don't care enough. | |
244 | * | |
245 | * We care just barely enough to avoid recursing for | |
246 | * non-merge entries. | |
247 | */ | |
248 | static int count_distance(struct commit_list *entry) | |
249 | { | |
250 | int nr = 0; | |
251 | ||
252 | while (entry) { | |
253 | struct commit *commit = entry->item; | |
254 | struct commit_list *p; | |
255 | ||
256 | if (commit->object.flags & (UNINTERESTING | COUNTED)) | |
257 | break; | |
258 | nr++; | |
259 | commit->object.flags |= COUNTED; | |
260 | p = commit->parents; | |
261 | entry = p; | |
262 | if (p) { | |
263 | p = p->next; | |
264 | while (p) { | |
265 | nr += count_distance(p); | |
266 | p = p->next; | |
267 | } | |
268 | } | |
269 | } | |
270 | return nr; | |
271 | } | |
272 | ||
3d958064 | 273 | static void clear_distance(struct commit_list *list) |
8b3a1e05 LT |
274 | { |
275 | while (list) { | |
276 | struct commit *commit = list->item; | |
277 | commit->object.flags &= ~COUNTED; | |
278 | list = list->next; | |
279 | } | |
280 | } | |
281 | ||
282 | static struct commit_list *find_bisection(struct commit_list *list) | |
283 | { | |
284 | int nr, closest; | |
285 | struct commit_list *p, *best; | |
286 | ||
287 | nr = 0; | |
288 | p = list; | |
289 | while (p) { | |
290 | nr++; | |
291 | p = p->next; | |
292 | } | |
293 | closest = 0; | |
294 | best = list; | |
295 | ||
296 | p = list; | |
297 | while (p) { | |
298 | int distance = count_distance(p); | |
299 | clear_distance(list); | |
300 | if (nr - distance < distance) | |
301 | distance = nr - distance; | |
302 | if (distance > closest) { | |
303 | best = p; | |
304 | closest = distance; | |
305 | } | |
306 | p = p->next; | |
307 | } | |
308 | if (best) | |
309 | best->next = NULL; | |
310 | return best; | |
311 | } | |
312 | ||
6da4016a | 313 | static struct commit_list *limit_list(struct commit_list *list) |
3b42a63c LT |
314 | { |
315 | struct commit_list *newlist = NULL; | |
316 | struct commit_list **p = &newlist; | |
36f8d174 | 317 | while (list) { |
3b42a63c LT |
318 | struct commit *commit = pop_most_recent_commit(&list, SEEN); |
319 | struct object *obj = &commit->object; | |
320 | ||
337cb3fb | 321 | if (obj->flags & UNINTERESTING) { |
3b42a63c LT |
322 | mark_parents_uninteresting(commit); |
323 | if (everybody_uninteresting(list)) | |
324 | break; | |
325 | continue; | |
326 | } | |
327 | p = &commit_list_insert(commit, p)->next; | |
36f8d174 | 328 | } |
8b3a1e05 LT |
329 | if (bisect_list) |
330 | newlist = find_bisection(newlist); | |
3b42a63c LT |
331 | return newlist; |
332 | } | |
333 | ||
36f8d174 LT |
334 | static void add_pending_object(struct object *obj, const char *name) |
335 | { | |
336 | add_object(obj, &pending_objects, name); | |
337 | } | |
338 | ||
3c90f03d LT |
339 | static struct commit *get_commit_reference(const char *name, unsigned int flags) |
340 | { | |
341 | unsigned char sha1[20]; | |
36f8d174 | 342 | struct object *object; |
3c90f03d LT |
343 | |
344 | if (get_sha1(name, sha1)) | |
345 | usage(rev_list_usage); | |
36f8d174 LT |
346 | object = parse_object(sha1); |
347 | if (!object) | |
348 | die("bad object %s", name); | |
349 | ||
350 | /* | |
351 | * Tag object? Look what it points to.. | |
352 | */ | |
353 | if (object->type == tag_type) { | |
354 | struct tag *tag = (struct tag *) object; | |
355 | object->flags |= flags; | |
356 | if (tag_objects && !(object->flags & UNINTERESTING)) | |
357 | add_pending_object(object, tag->tag); | |
358 | object = tag->tagged; | |
359 | } | |
360 | ||
361 | /* | |
362 | * Commit object? Just return it, we'll do all the complex | |
363 | * reachability crud. | |
364 | */ | |
365 | if (object->type == commit_type) { | |
366 | struct commit *commit = (struct commit *)object; | |
367 | object->flags |= flags; | |
368 | if (parse_commit(commit) < 0) | |
369 | die("unable to parse commit %s", name); | |
370 | return commit; | |
371 | } | |
372 | ||
373 | /* | |
374 | * Tree object? Either mark it uniniteresting, or add it | |
375 | * to the list of objects to look at later.. | |
376 | */ | |
377 | if (object->type == tree_type) { | |
378 | struct tree *tree = (struct tree *)object; | |
379 | if (!tree_objects) | |
960bba0d | 380 | return NULL; |
36f8d174 LT |
381 | if (flags & UNINTERESTING) { |
382 | mark_tree_uninteresting(tree); | |
383 | return NULL; | |
384 | } | |
385 | add_pending_object(object, ""); | |
386 | return NULL; | |
387 | } | |
388 | ||
389 | /* | |
390 | * Blob object? You know the drill by now.. | |
391 | */ | |
392 | if (object->type == blob_type) { | |
393 | struct blob *blob = (struct blob *)object; | |
394 | if (!blob_objects) | |
960bba0d | 395 | return NULL; |
36f8d174 LT |
396 | if (flags & UNINTERESTING) { |
397 | mark_blob_uninteresting(blob); | |
398 | return NULL; | |
399 | } | |
400 | add_pending_object(object, ""); | |
401 | return NULL; | |
402 | } | |
403 | die("%s is unknown object", name); | |
3c90f03d LT |
404 | } |
405 | ||
64745109 LT |
406 | int main(int argc, char **argv) |
407 | { | |
64745109 | 408 | struct commit_list *list = NULL; |
337cb3fb | 409 | int i, limited = 0; |
64745109 | 410 | |
fcfda02b | 411 | for (i = 1 ; i < argc; i++) { |
337cb3fb | 412 | int flags; |
fcfda02b | 413 | char *arg = argv[i]; |
337cb3fb | 414 | struct commit *commit; |
fcfda02b KS |
415 | |
416 | if (!strncmp(arg, "--max-count=", 12)) { | |
417 | max_count = atoi(arg + 12); | |
a6f68d47 LT |
418 | continue; |
419 | } | |
420 | if (!strncmp(arg, "--max-age=", 10)) { | |
fcfda02b | 421 | max_age = atoi(arg + 10); |
a6f68d47 LT |
422 | continue; |
423 | } | |
424 | if (!strncmp(arg, "--min-age=", 10)) { | |
fcfda02b | 425 | min_age = atoi(arg + 10); |
a6f68d47 | 426 | continue; |
fcfda02b | 427 | } |
a6f68d47 LT |
428 | if (!strcmp(arg, "--header")) { |
429 | verbose_header = 1; | |
430 | continue; | |
431 | } | |
000182ea LT |
432 | if (!strncmp(arg, "--pretty", 8)) { |
433 | commit_format = get_commit_format(arg+8); | |
9d97aa64 | 434 | verbose_header = 1; |
9d97aa64 LT |
435 | hdr_termination = '\n'; |
436 | prefix = "commit "; | |
437 | continue; | |
438 | } | |
97658004 LT |
439 | if (!strcmp(arg, "--parents")) { |
440 | show_parents = 1; | |
441 | continue; | |
442 | } | |
8b3a1e05 LT |
443 | if (!strcmp(arg, "--bisect")) { |
444 | bisect_list = 1; | |
445 | continue; | |
446 | } | |
9de48752 | 447 | if (!strcmp(arg, "--objects")) { |
3c90f03d | 448 | tag_objects = 1; |
9de48752 LT |
449 | tree_objects = 1; |
450 | blob_objects = 1; | |
451 | continue; | |
452 | } | |
a3437b8c JS |
453 | if (!strncmp(arg, "--merge-order", 13)) { |
454 | merge_order = 1; | |
455 | continue; | |
456 | } | |
457 | if (!strncmp(arg, "--show-breaks", 13)) { | |
458 | show_breaks = 1; | |
459 | continue; | |
460 | } | |
a6f68d47 | 461 | |
337cb3fb LT |
462 | flags = 0; |
463 | if (*arg == '^') { | |
464 | flags = UNINTERESTING; | |
465 | arg++; | |
466 | limited = 1; | |
467 | } | |
3c90f03d | 468 | if (show_breaks && !merge_order) |
a6f68d47 | 469 | usage(rev_list_usage); |
3c90f03d LT |
470 | commit = get_commit_reference(arg, flags); |
471 | if (!commit) | |
472 | continue; | |
337cb3fb | 473 | commit_list_insert(commit, &list); |
fcfda02b KS |
474 | } |
475 | ||
a3437b8c | 476 | if (!merge_order) { |
17ebe977 | 477 | if (limited) |
a3437b8c JS |
478 | list = limit_list(list); |
479 | show_commit_list(list); | |
a3437b8c | 480 | } else { |
a3437b8c JS |
481 | if (sort_list_in_merge_order(list, &process_commit)) { |
482 | die("merge order sort failed\n"); | |
483 | } | |
a3437b8c | 484 | } |
8906300f | 485 | |
64745109 LT |
486 | return 0; |
487 | } |