6 #include "list-objects.h"
8 #include "sha1-lookup.h"
9 #include "run-command.h"
13 unsigned char (*sha1
)[20];
18 static struct sha1_array skipped_revs
;
20 static const char **rev_argv
;
21 static int rev_argv_nr
;
22 static int rev_argv_alloc
;
24 static const unsigned char *current_bad_sha1
;
26 static const char *argv_diff_tree
[] = {"diff-tree", "--pretty", NULL
, NULL
};
27 static const char *argv_checkout
[] = {"checkout", "-q", NULL
, "--", NULL
};
28 static const char *argv_show_branch
[] = {"show-branch", NULL
, NULL
};
30 /* bits #0-15 in revision.h */
32 #define COUNTED (1u<<16)
35 * This is a truly stupid algorithm, but it's only
36 * used for bisection, and we just don't care enough.
38 * We care just barely enough to avoid recursing for
41 static int count_distance(struct commit_list
*entry
)
46 struct commit
*commit
= entry
->item
;
47 struct commit_list
*p
;
49 if (commit
->object
.flags
& (UNINTERESTING
| COUNTED
))
51 if (!(commit
->object
.flags
& TREESAME
))
53 commit
->object
.flags
|= COUNTED
;
59 nr
+= count_distance(p
);
68 static void clear_distance(struct commit_list
*list
)
71 struct commit
*commit
= list
->item
;
72 commit
->object
.flags
&= ~COUNTED
;
77 #define DEBUG_BISECT 0
79 static inline int weight(struct commit_list
*elem
)
81 return *((int*)(elem
->item
->util
));
84 static inline void weight_set(struct commit_list
*elem
, int weight
)
86 *((int*)(elem
->item
->util
)) = weight
;
89 static int count_interesting_parents(struct commit
*commit
)
91 struct commit_list
*p
;
94 for (count
= 0, p
= commit
->parents
; p
; p
= p
->next
) {
95 if (p
->item
->object
.flags
& UNINTERESTING
)
102 static inline int halfway(struct commit_list
*p
, int nr
)
105 * Don't short-cut something we are not going to return!
107 if (p
->item
->object
.flags
& TREESAME
)
112 * 2 and 3 are halfway of 5.
113 * 3 is halfway of 6 but 2 and 4 are not.
115 switch (2 * weight(p
) - nr
) {
116 case -1: case 0: case 1:
124 #define show_list(a,b,c,d) do { ; } while (0)
126 static void show_list(const char *debug
, int counted
, int nr
,
127 struct commit_list
*list
)
129 struct commit_list
*p
;
131 fprintf(stderr
, "%s (%d/%d)\n", debug
, counted
, nr
);
133 for (p
= list
; p
; p
= p
->next
) {
134 struct commit_list
*pp
;
135 struct commit
*commit
= p
->item
;
136 unsigned flags
= commit
->object
.flags
;
137 enum object_type type
;
139 char *buf
= read_sha1_file(commit
->object
.sha1
, &type
, &size
);
142 fprintf(stderr
, "%c%c%c ",
143 (flags
& TREESAME
) ? ' ' : 'T',
144 (flags
& UNINTERESTING
) ? 'U' : ' ',
145 (flags
& COUNTED
) ? 'C' : ' ');
147 fprintf(stderr
, "%3d", weight(p
));
149 fprintf(stderr
, "---");
150 fprintf(stderr
, " %.*s", 8, sha1_to_hex(commit
->object
.sha1
));
151 for (pp
= commit
->parents
; pp
; pp
= pp
->next
)
152 fprintf(stderr
, " %.*s", 8,
153 sha1_to_hex(pp
->item
->object
.sha1
));
155 sp
= strstr(buf
, "\n\n");
158 for (ep
= sp
; *ep
&& *ep
!= '\n'; ep
++)
160 fprintf(stderr
, " %.*s", (int)(ep
- sp
), sp
);
162 fprintf(stderr
, "\n");
165 #endif /* DEBUG_BISECT */
167 static struct commit_list
*best_bisection(struct commit_list
*list
, int nr
)
169 struct commit_list
*p
, *best
;
170 int best_distance
= -1;
173 for (p
= list
; p
; p
= p
->next
) {
175 unsigned flags
= p
->item
->object
.flags
;
177 if (flags
& TREESAME
)
179 distance
= weight(p
);
180 if (nr
- distance
< distance
)
181 distance
= nr
- distance
;
182 if (distance
> best_distance
) {
184 best_distance
= distance
;
192 struct commit
*commit
;
196 static int compare_commit_dist(const void *a_
, const void *b_
)
198 struct commit_dist
*a
, *b
;
200 a
= (struct commit_dist
*)a_
;
201 b
= (struct commit_dist
*)b_
;
202 if (a
->distance
!= b
->distance
)
203 return b
->distance
- a
->distance
; /* desc sort */
204 return hashcmp(a
->commit
->object
.sha1
, b
->commit
->object
.sha1
);
207 static struct commit_list
*best_bisection_sorted(struct commit_list
*list
, int nr
)
209 struct commit_list
*p
;
210 struct commit_dist
*array
= xcalloc(nr
, sizeof(*array
));
213 for (p
= list
, cnt
= 0; p
; p
= p
->next
) {
215 unsigned flags
= p
->item
->object
.flags
;
217 if (flags
& TREESAME
)
219 distance
= weight(p
);
220 if (nr
- distance
< distance
)
221 distance
= nr
- distance
;
222 array
[cnt
].commit
= p
->item
;
223 array
[cnt
].distance
= distance
;
226 qsort(array
, cnt
, sizeof(*array
), compare_commit_dist
);
227 for (p
= list
, i
= 0; i
< cnt
; i
++) {
228 struct name_decoration
*r
= xmalloc(sizeof(*r
) + 100);
229 struct object
*obj
= &(array
[i
].commit
->object
);
231 sprintf(r
->name
, "dist=%d", array
[i
].distance
);
232 r
->next
= add_decoration(&name_decoration
, obj
, r
);
233 p
->item
= array
[i
].commit
;
243 * zero or positive weight is the number of interesting commits it can
244 * reach, including itself. Especially, weight = 0 means it does not
245 * reach any tree-changing commits (e.g. just above uninteresting one
246 * but traversal is with pathspec).
248 * weight = -1 means it has one parent and its distance is yet to
251 * weight = -2 means it has more than one parent and its distance is
252 * unknown. After running count_distance() first, they will get zero
253 * or positive distance.
255 static struct commit_list
*do_find_bisection(struct commit_list
*list
,
256 int nr
, int *weights
,
260 struct commit_list
*p
;
264 for (n
= 0, p
= list
; p
; p
= p
->next
) {
265 struct commit
*commit
= p
->item
;
266 unsigned flags
= commit
->object
.flags
;
268 p
->item
->util
= &weights
[n
++];
269 switch (count_interesting_parents(commit
)) {
271 if (!(flags
& TREESAME
)) {
274 show_list("bisection 2 count one",
278 * otherwise, it is known not to reach any
279 * tree-changing commit and gets weight 0.
291 show_list("bisection 2 initialize", counted
, nr
, list
);
294 * If you have only one parent in the resulting set
295 * then you can reach one commit more than that parent
296 * can reach. So we do not have to run the expensive
297 * count_distance() for single strand of pearls.
299 * However, if you have more than one parents, you cannot
300 * just add their distance and one for yourself, since
301 * they usually reach the same ancestor and you would
302 * end up counting them twice that way.
304 * So we will first count distance of merges the usual
305 * way, and then fill the blanks using cheaper algorithm.
307 for (p
= list
; p
; p
= p
->next
) {
308 if (p
->item
->object
.flags
& UNINTERESTING
)
312 weight_set(p
, count_distance(p
));
313 clear_distance(list
);
315 /* Does it happen to be at exactly half-way? */
316 if (!find_all
&& halfway(p
, nr
))
321 show_list("bisection 2 count_distance", counted
, nr
, list
);
323 while (counted
< nr
) {
324 for (p
= list
; p
; p
= p
->next
) {
325 struct commit_list
*q
;
326 unsigned flags
= p
->item
->object
.flags
;
330 for (q
= p
->item
->parents
; q
; q
= q
->next
) {
331 if (q
->item
->object
.flags
& UNINTERESTING
)
340 * weight for p is unknown but q is known.
341 * add one for p itself if p is to be counted,
342 * otherwise inherit it from q directly.
344 if (!(flags
& TREESAME
)) {
345 weight_set(p
, weight(q
)+1);
347 show_list("bisection 2 count one",
351 weight_set(p
, weight(q
));
353 /* Does it happen to be at exactly half-way? */
354 if (!find_all
&& halfway(p
, nr
))
359 show_list("bisection 2 counted all", counted
, nr
, list
);
362 return best_bisection(list
, nr
);
364 return best_bisection_sorted(list
, nr
);
367 struct commit_list
*find_bisection(struct commit_list
*list
,
368 int *reaches
, int *all
,
372 struct commit_list
*p
, *best
, *next
, *last
;
375 show_list("bisection 2 entry", 0, 0, list
);
378 * Count the number of total and tree-changing items on the
379 * list, while reversing the list.
381 for (nr
= on_list
= 0, last
= NULL
, p
= list
;
384 unsigned flags
= p
->item
->object
.flags
;
387 if (flags
& UNINTERESTING
)
391 if (!(flags
& TREESAME
))
396 show_list("bisection 2 sorted", 0, nr
, list
);
399 weights
= xcalloc(on_list
, sizeof(*weights
));
401 /* Do the real work of finding bisection commit. */
402 best
= do_find_bisection(list
, nr
, weights
, find_all
);
406 *reaches
= weight(best
);
412 static int register_ref(const char *refname
, const unsigned char *sha1
,
413 int flags
, void *cb_data
)
415 if (!strcmp(refname
, "bad")) {
416 ALLOC_GROW(rev_argv
, rev_argv_nr
+ 1, rev_argv_alloc
);
417 current_bad_sha1
= sha1
;
418 rev_argv
[rev_argv_nr
++] = xstrdup(sha1_to_hex(sha1
));
419 } else if (!prefixcmp(refname
, "good-")) {
420 const char *hex
= sha1_to_hex(sha1
);
421 char *good
= xmalloc(strlen(hex
) + 2);
423 memcpy(good
+ 1, hex
, strlen(hex
) + 1);
424 ALLOC_GROW(rev_argv
, rev_argv_nr
+ 1, rev_argv_alloc
);
425 rev_argv
[rev_argv_nr
++] = good
;
426 } else if (!prefixcmp(refname
, "skip-")) {
427 ALLOC_GROW(skipped_revs
.sha1
, skipped_revs
.sha1_nr
+ 1,
428 skipped_revs
.sha1_alloc
);
429 hashcpy(skipped_revs
.sha1
[skipped_revs
.sha1_nr
++], sha1
);
435 static int read_bisect_refs(void)
437 return for_each_ref_in("refs/bisect/", register_ref
, NULL
);
440 void read_bisect_paths(void)
442 struct strbuf str
= STRBUF_INIT
;
443 const char *filename
= git_path("BISECT_NAMES");
444 FILE *fp
= fopen(filename
, "r");
447 die("Could not open file '%s': %s", filename
, strerror(errno
));
449 while (strbuf_getline(&str
, fp
, '\n') != EOF
) {
454 quoted
= strbuf_detach(&str
, NULL
);
455 res
= sq_dequote_to_argv(quoted
, &rev_argv
,
456 &rev_argv_nr
, &rev_argv_alloc
);
458 die("Badly quoted content in file '%s': %s",
462 strbuf_release(&str
);
466 static int skipcmp(const void *a
, const void *b
)
468 return hashcmp(a
, b
);
471 static void prepare_skipped(void)
473 qsort(skipped_revs
.sha1
, skipped_revs
.sha1_nr
,
474 sizeof(*skipped_revs
.sha1
), skipcmp
);
477 static const unsigned char *skipped_sha1_access(size_t index
, void *table
)
479 unsigned char (*skipped
)[20] = table
;
480 return skipped
[index
];
483 static int lookup_skipped(unsigned char *sha1
)
485 return sha1_pos(sha1
, skipped_revs
.sha1
, skipped_revs
.sha1_nr
,
486 skipped_sha1_access
);
489 struct commit_list
*filter_skipped(struct commit_list
*list
,
490 struct commit_list
**tried
,
493 struct commit_list
*filtered
= NULL
, **f
= &filtered
;
497 if (!skipped_revs
.sha1_nr
)
503 struct commit_list
*next
= list
->next
;
505 if (0 <= lookup_skipped(list
->item
->object
.sha1
)) {
506 /* Move current to tried list */
512 /* Move current to filtered list */
522 static void bisect_rev_setup(struct rev_info
*revs
, const char *prefix
)
524 init_revisions(revs
, prefix
);
526 revs
->commit_format
= CMIT_FMT_UNSPECIFIED
;
528 /* argv[0] will be ignored by setup_revisions */
529 ALLOC_GROW(rev_argv
, rev_argv_nr
+ 1, rev_argv_alloc
);
530 rev_argv
[rev_argv_nr
++] = xstrdup("bisect_rev_setup");
532 if (read_bisect_refs())
533 die("reading bisect refs failed");
535 ALLOC_GROW(rev_argv
, rev_argv_nr
+ 1, rev_argv_alloc
);
536 rev_argv
[rev_argv_nr
++] = xstrdup("--");
540 ALLOC_GROW(rev_argv
, rev_argv_nr
+ 1, rev_argv_alloc
);
541 rev_argv
[rev_argv_nr
++] = NULL
;
543 setup_revisions(rev_argv_nr
, rev_argv
, revs
, NULL
);
548 static void bisect_common(struct rev_info
*revs
, const char *prefix
,
549 int *reaches
, int *all
)
551 bisect_rev_setup(revs
, prefix
);
553 if (prepare_revision_walk(revs
))
554 die("revision walk setup failed");
555 if (revs
->tree_objects
)
556 mark_edges_uninteresting(revs
->commits
, revs
, NULL
);
558 revs
->commits
= find_bisection(revs
->commits
, reaches
, all
,
559 !!skipped_revs
.sha1_nr
);
562 static void exit_if_skipped_commits(struct commit_list
*tried
,
563 const unsigned char *bad
)
568 printf("There are only 'skip'ped commits left to test.\n"
569 "The first bad commit could be any of:\n");
570 print_commit_list(tried
, "%s\n", "%s\n");
572 printf("%s\n", sha1_to_hex(bad
));
573 printf("We cannot bisect more!\n");
577 static void mark_expected_rev(char *bisect_rev_hex
)
579 int len
= strlen(bisect_rev_hex
);
580 const char *filename
= git_path("BISECT_EXPECTED_REV");
581 int fd
= open(filename
, O_CREAT
| O_TRUNC
| O_WRONLY
, 0600);
584 die("could not create file '%s': %s",
585 filename
, strerror(errno
));
587 bisect_rev_hex
[len
] = '\n';
588 write_or_die(fd
, bisect_rev_hex
, len
+ 1);
589 bisect_rev_hex
[len
] = '\0';
592 die("closing file %s: %s", filename
, strerror(errno
));
595 static int bisect_checkout(char *bisect_rev_hex
)
599 mark_expected_rev(bisect_rev_hex
);
601 argv_checkout
[2] = bisect_rev_hex
;
602 res
= run_command_v_opt(argv_checkout
, RUN_GIT_CMD
);
606 argv_show_branch
[1] = bisect_rev_hex
;
607 return run_command_v_opt(argv_show_branch
, RUN_GIT_CMD
);
611 * We use the convention that exiting with an exit code 10 means that
612 * the bisection process finished successfully.
613 * In this case the calling shell script should exit 0.
615 int bisect_next_exit(const char *prefix
)
617 struct rev_info revs
;
618 struct commit_list
*tried
;
619 int reaches
= 0, all
= 0, nr
;
620 const unsigned char *bisect_rev
;
621 char bisect_rev_hex
[41];
623 bisect_common(&revs
, prefix
, &reaches
, &all
);
625 revs
.commits
= filter_skipped(revs
.commits
, &tried
, 0);
629 * We should exit here only if the "bad"
630 * commit is also a "skip" commit.
632 exit_if_skipped_commits(tried
, NULL
);
634 printf("%s was both good and bad\n",
635 sha1_to_hex(current_bad_sha1
));
639 bisect_rev
= revs
.commits
->item
->object
.sha1
;
640 memcpy(bisect_rev_hex
, sha1_to_hex(bisect_rev
), 41);
642 if (!hashcmp(bisect_rev
, current_bad_sha1
)) {
643 exit_if_skipped_commits(tried
, current_bad_sha1
);
644 printf("%s is first bad commit\n", bisect_rev_hex
);
645 argv_diff_tree
[2] = bisect_rev_hex
;
646 run_command_v_opt(argv_diff_tree
, RUN_GIT_CMD
);
647 /* This means the bisection process succeeded. */
651 nr
= all
- reaches
- 1;
652 printf("Bisecting: %d revisions left to test after this "
653 "(roughly %d steps)\n", nr
, estimate_bisect_steps(all
));
655 return bisect_checkout(bisect_rev_hex
);