10 #include "list-objects.h"
13 /* bits #0-15 in revision.h */
15 #define COUNTED (1u<<16)
17 static const char rev_list_usage
[] =
18 "git-rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
31 " formatting output:\n"
33 " --objects | --objects-edge\n"
35 " --header | --pretty\n"
36 " --abbrev=nr | --no-abbrev\n"
44 static struct rev_info revs
;
46 static int bisect_list
;
47 static int show_timestamp
;
48 static int hdr_termination
;
49 static const char *header_prefix
;
51 static void show_commit(struct commit
*commit
)
54 printf("%lu ", commit
->date
);
56 fputs(header_prefix
, stdout
);
57 if (commit
->object
.flags
& BOUNDARY
)
59 else if (revs
.left_right
) {
60 if (commit
->object
.flags
& SYMMETRIC_LEFT
)
65 if (revs
.abbrev_commit
&& revs
.abbrev
)
66 fputs(find_unique_abbrev(commit
->object
.sha1
, revs
.abbrev
),
69 fputs(sha1_to_hex(commit
->object
.sha1
), stdout
);
71 struct commit_list
*parents
= commit
->parents
;
73 printf(" %s", sha1_to_hex(parents
->item
->object
.sha1
));
74 parents
= parents
->next
;
77 if (revs
.commit_format
== CMIT_FMT_ONELINE
)
82 if (revs
.verbose_header
) {
85 pretty_print_commit(revs
.commit_format
, commit
,
86 &buf
, revs
.abbrev
, NULL
, NULL
, revs
.date_mode
);
87 printf("%s%c", buf
.buf
, hdr_termination
);
90 maybe_flush_or_die(stdout
, "stdout");
91 if (commit
->parents
) {
92 free_commit_list(commit
->parents
);
93 commit
->parents
= NULL
;
96 commit
->buffer
= NULL
;
99 static void show_object(struct object_array_entry
*p
)
101 /* An object with name "foo\n0000000..." can be used to
102 * confuse downstream git-pack-objects very badly.
104 const char *ep
= strchr(p
->name
, '\n');
106 if (p
->item
->type
== OBJ_BLOB
&& !has_sha1_file(p
->item
->sha1
))
107 die("missing blob object '%s'", sha1_to_hex(p
->item
->sha1
));
110 printf("%s %.*s\n", sha1_to_hex(p
->item
->sha1
),
111 (int) (ep
- p
->name
),
115 printf("%s %s\n", sha1_to_hex(p
->item
->sha1
), p
->name
);
118 static void show_edge(struct commit
*commit
)
120 printf("-%s\n", sha1_to_hex(commit
->object
.sha1
));
124 * This is a truly stupid algorithm, but it's only
125 * used for bisection, and we just don't care enough.
127 * We care just barely enough to avoid recursing for
130 static int count_distance(struct commit_list
*entry
)
135 struct commit
*commit
= entry
->item
;
136 struct commit_list
*p
;
138 if (commit
->object
.flags
& (UNINTERESTING
| COUNTED
))
140 if (!revs
.prune_fn
|| (commit
->object
.flags
& TREECHANGE
))
142 commit
->object
.flags
|= COUNTED
;
148 nr
+= count_distance(p
);
157 static void clear_distance(struct commit_list
*list
)
160 struct commit
*commit
= list
->item
;
161 commit
->object
.flags
&= ~COUNTED
;
166 #define DEBUG_BISECT 0
168 static inline int weight(struct commit_list
*elem
)
170 return *((int*)(elem
->item
->util
));
173 static inline void weight_set(struct commit_list
*elem
, int weight
)
175 *((int*)(elem
->item
->util
)) = weight
;
178 static int count_interesting_parents(struct commit
*commit
)
180 struct commit_list
*p
;
183 for (count
= 0, p
= commit
->parents
; p
; p
= p
->next
) {
184 if (p
->item
->object
.flags
& UNINTERESTING
)
191 static inline int halfway(struct commit_list
*p
, int distance
, int nr
)
194 * Don't short-cut something we are not going to return!
196 if (revs
.prune_fn
&& !(p
->item
->object
.flags
& TREECHANGE
))
201 * 2 and 3 are halfway of 5.
202 * 3 is halfway of 6 but 2 and 4 are not.
205 switch (distance
- nr
) {
206 case -1: case 0: case 1:
214 #define show_list(a,b,c,d) do { ; } while (0)
216 static void show_list(const char *debug
, int counted
, int nr
,
217 struct commit_list
*list
)
219 struct commit_list
*p
;
221 fprintf(stderr
, "%s (%d/%d)\n", debug
, counted
, nr
);
223 for (p
= list
; p
; p
= p
->next
) {
224 struct commit_list
*pp
;
225 struct commit
*commit
= p
->item
;
226 unsigned flags
= commit
->object
.flags
;
227 enum object_type type
;
229 char *buf
= read_sha1_file(commit
->object
.sha1
, &type
, &size
);
232 fprintf(stderr
, "%c%c%c ",
233 (flags
& TREECHANGE
) ? 'T' : ' ',
234 (flags
& UNINTERESTING
) ? 'U' : ' ',
235 (flags
& COUNTED
) ? 'C' : ' ');
237 fprintf(stderr
, "%3d", weight(p
));
239 fprintf(stderr
, "---");
240 fprintf(stderr
, " %.*s", 8, sha1_to_hex(commit
->object
.sha1
));
241 for (pp
= commit
->parents
; pp
; pp
= pp
->next
)
242 fprintf(stderr
, " %.*s", 8,
243 sha1_to_hex(pp
->item
->object
.sha1
));
245 sp
= strstr(buf
, "\n\n");
248 for (ep
= sp
; *ep
&& *ep
!= '\n'; ep
++)
250 fprintf(stderr
, " %.*s", (int)(ep
- sp
), sp
);
252 fprintf(stderr
, "\n");
255 #endif /* DEBUG_BISECT */
258 * zero or positive weight is the number of interesting commits it can
259 * reach, including itself. Especially, weight = 0 means it does not
260 * reach any tree-changing commits (e.g. just above uninteresting one
261 * but traversal is with pathspec).
263 * weight = -1 means it has one parent and its distance is yet to
266 * weight = -2 means it has more than one parent and its distance is
267 * unknown. After running count_distance() first, they will get zero
268 * or positive distance.
271 static struct commit_list
*find_bisection(struct commit_list
*list
,
272 int *reaches
, int *all
)
274 int n
, nr
, on_list
, counted
, distance
;
275 struct commit_list
*p
, *best
, *next
, *last
;
278 show_list("bisection 2 entry", 0, 0, list
);
281 * Count the number of total and tree-changing items on the
282 * list, while reversing the list.
284 for (nr
= on_list
= 0, last
= NULL
, p
= list
;
287 unsigned flags
= p
->item
->object
.flags
;
290 if (flags
& UNINTERESTING
)
294 if (!revs
.prune_fn
|| (flags
& TREECHANGE
))
299 show_list("bisection 2 sorted", 0, nr
, list
);
302 weights
= xcalloc(on_list
, sizeof(*weights
));
305 for (n
= 0, p
= list
; p
; p
= p
->next
) {
306 struct commit
*commit
= p
->item
;
307 unsigned flags
= commit
->object
.flags
;
309 p
->item
->util
= &weights
[n
++];
310 switch (count_interesting_parents(commit
)) {
312 if (!revs
.prune_fn
|| (flags
& TREECHANGE
)) {
315 show_list("bisection 2 count one",
319 * otherwise, it is known not to reach any
320 * tree-changing commit and gets weight 0.
332 show_list("bisection 2 initialize", counted
, nr
, list
);
335 * If you have only one parent in the resulting set
336 * then you can reach one commit more than that parent
337 * can reach. So we do not have to run the expensive
338 * count_distance() for single strand of pearls.
340 * However, if you have more than one parents, you cannot
341 * just add their distance and one for yourself, since
342 * they usually reach the same ancestor and you would
343 * end up counting them twice that way.
345 * So we will first count distance of merges the usual
346 * way, and then fill the blanks using cheaper algorithm.
348 for (p
= list
; p
; p
= p
->next
) {
349 if (p
->item
->object
.flags
& UNINTERESTING
)
354 distance
= count_distance(p
);
355 clear_distance(list
);
356 weight_set(p
, distance
);
358 /* Does it happen to be at exactly half-way? */
359 if (halfway(p
, distance
, nr
)) {
368 show_list("bisection 2 count_distance", counted
, nr
, list
);
370 while (counted
< nr
) {
371 for (p
= list
; p
; p
= p
->next
) {
372 struct commit_list
*q
;
373 unsigned flags
= p
->item
->object
.flags
;
377 for (q
= p
->item
->parents
; q
; q
= q
->next
) {
378 if (q
->item
->object
.flags
& UNINTERESTING
)
387 * weight for p is unknown but q is known.
388 * add one for p itself if p is to be counted,
389 * otherwise inherit it from q directly.
391 if (!revs
.prune_fn
|| (flags
& TREECHANGE
)) {
392 weight_set(p
, weight(q
)+1);
394 show_list("bisection 2 count one",
398 weight_set(p
, weight(q
));
400 /* Does it happen to be at exactly half-way? */
401 distance
= weight(p
);
402 if (halfway(p
, distance
, nr
)) {
411 show_list("bisection 2 counted all", counted
, nr
, list
);
413 /* Then find the best one */
416 for (p
= list
; p
; p
= p
->next
) {
417 unsigned flags
= p
->item
->object
.flags
;
419 if (revs
.prune_fn
&& !(flags
& TREECHANGE
))
421 distance
= weight(p
);
422 if (nr
- distance
< distance
)
423 distance
= nr
- distance
;
424 if (distance
> counted
) {
427 *reaches
= weight(p
);
436 static void read_revisions_from_stdin(struct rev_info
*revs
)
440 while (fgets(line
, sizeof(line
), stdin
) != NULL
) {
441 int len
= strlen(line
);
442 if (line
[len
- 1] == '\n')
447 die("options not supported in --stdin mode");
448 if (handle_revision_arg(line
, revs
, 0, 1))
449 die("bad revision '%s'", line
);
453 int cmd_rev_list(int argc
, const char **argv
, const char *prefix
)
455 struct commit_list
*list
;
457 int read_from_stdin
= 0;
458 int bisect_show_vars
= 0;
460 git_config(git_default_config
);
461 init_revisions(&revs
, prefix
);
463 revs
.commit_format
= CMIT_FMT_UNSPECIFIED
;
464 argc
= setup_revisions(argc
, argv
, &revs
, NULL
);
466 for (i
= 1 ; i
< argc
; i
++) {
467 const char *arg
= argv
[i
];
469 if (!strcmp(arg
, "--header")) {
470 revs
.verbose_header
= 1;
473 if (!strcmp(arg
, "--timestamp")) {
477 if (!strcmp(arg
, "--bisect")) {
481 if (!strcmp(arg
, "--bisect-vars")) {
483 bisect_show_vars
= 1;
486 if (!strcmp(arg
, "--stdin")) {
487 if (read_from_stdin
++)
488 die("--stdin given twice?");
489 read_revisions_from_stdin(&revs
);
492 usage(rev_list_usage
);
495 if (revs
.commit_format
!= CMIT_FMT_UNSPECIFIED
) {
496 /* The command line has a --pretty */
497 hdr_termination
= '\n';
498 if (revs
.commit_format
== CMIT_FMT_ONELINE
)
501 header_prefix
= "commit ";
503 else if (revs
.verbose_header
)
504 /* Only --header was specified */
505 revs
.commit_format
= CMIT_FMT_RAW
;
510 (!(revs
.tag_objects
||revs
.tree_objects
||revs
.blob_objects
) &&
511 !revs
.pending
.nr
)) ||
513 usage(rev_list_usage
);
515 save_commit_buffer
= revs
.verbose_header
|| revs
.grep_filter
;
516 track_object_refs
= 0;
520 prepare_revision_walk(&revs
);
521 if (revs
.tree_objects
)
522 mark_edges_uninteresting(revs
.commits
, &revs
, show_edge
);
525 int reaches
= reaches
, all
= all
;
527 revs
.commits
= find_bisection(revs
.commits
, &reaches
, &all
);
528 if (bisect_show_vars
) {
533 * revs.commits can reach "reaches" commits among
534 * "all" commits. If it is good, then there are
535 * (all-reaches) commits left to be bisected.
536 * On the other hand, if it is bad, then the set
537 * to bisect is "reaches".
538 * A bisect set of size N has (N-1) commits further
539 * to test, as we already know one bad one.
544 printf("bisect_rev=%s\n"
549 sha1_to_hex(revs
.commits
->item
->object
.sha1
),
558 traverse_commit_list(&revs
, show_commit
, show_object
);