bisect: remove too much function nesting
[git/git.git] / bisect.c
CommitLineData
a2ad79ce
CC
1#include "cache.h"
2#include "commit.h"
3#include "diff.h"
4#include "revision.h"
1bf072e3
CC
5#include "refs.h"
6#include "list-objects.h"
3b437b0d 7#include "quote.h"
4eb5b646 8#include "sha1-lookup.h"
ef24c7ca 9#include "run-command.h"
a2ad79ce
CC
10#include "bisect.h"
11
6212b1aa
CC
12struct sha1_array {
13 unsigned char (*sha1)[20];
14 int sha1_nr;
15 int sha1_alloc;
16};
17
fad2d31d 18static struct sha1_array good_revs;
6212b1aa 19static struct sha1_array skipped_revs;
1bf072e3 20
ef24c7ca
CC
21static const unsigned char *current_bad_sha1;
22
1c953a1f
CC
23struct argv_array {
24 const char **argv;
25 int argv_nr;
26 int argv_alloc;
27};
28
ef24c7ca
CC
29static const char *argv_diff_tree[] = {"diff-tree", "--pretty", NULL, NULL};
30static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
31static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
32
a2ad79ce
CC
33/* bits #0-15 in revision.h */
34
35#define COUNTED (1u<<16)
36
37/*
38 * This is a truly stupid algorithm, but it's only
39 * used for bisection, and we just don't care enough.
40 *
41 * We care just barely enough to avoid recursing for
42 * non-merge entries.
43 */
44static int count_distance(struct commit_list *entry)
45{
46 int nr = 0;
47
48 while (entry) {
49 struct commit *commit = entry->item;
50 struct commit_list *p;
51
52 if (commit->object.flags & (UNINTERESTING | COUNTED))
53 break;
54 if (!(commit->object.flags & TREESAME))
55 nr++;
56 commit->object.flags |= COUNTED;
57 p = commit->parents;
58 entry = p;
59 if (p) {
60 p = p->next;
61 while (p) {
62 nr += count_distance(p);
63 p = p->next;
64 }
65 }
66 }
67
68 return nr;
69}
70
71static void clear_distance(struct commit_list *list)
72{
73 while (list) {
74 struct commit *commit = list->item;
75 commit->object.flags &= ~COUNTED;
76 list = list->next;
77 }
78}
79
80#define DEBUG_BISECT 0
81
82static inline int weight(struct commit_list *elem)
83{
84 return *((int*)(elem->item->util));
85}
86
87static inline void weight_set(struct commit_list *elem, int weight)
88{
89 *((int*)(elem->item->util)) = weight;
90}
91
92static int count_interesting_parents(struct commit *commit)
93{
94 struct commit_list *p;
95 int count;
96
97 for (count = 0, p = commit->parents; p; p = p->next) {
98 if (p->item->object.flags & UNINTERESTING)
99 continue;
100 count++;
101 }
102 return count;
103}
104
105static inline int halfway(struct commit_list *p, int nr)
106{
107 /*
108 * Don't short-cut something we are not going to return!
109 */
110 if (p->item->object.flags & TREESAME)
111 return 0;
112 if (DEBUG_BISECT)
113 return 0;
114 /*
115 * 2 and 3 are halfway of 5.
116 * 3 is halfway of 6 but 2 and 4 are not.
117 */
118 switch (2 * weight(p) - nr) {
119 case -1: case 0: case 1:
120 return 1;
121 default:
122 return 0;
123 }
124}
125
126#if !DEBUG_BISECT
127#define show_list(a,b,c,d) do { ; } while (0)
128#else
129static void show_list(const char *debug, int counted, int nr,
130 struct commit_list *list)
131{
132 struct commit_list *p;
133
134 fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
135
136 for (p = list; p; p = p->next) {
137 struct commit_list *pp;
138 struct commit *commit = p->item;
139 unsigned flags = commit->object.flags;
140 enum object_type type;
141 unsigned long size;
142 char *buf = read_sha1_file(commit->object.sha1, &type, &size);
143 char *ep, *sp;
144
145 fprintf(stderr, "%c%c%c ",
146 (flags & TREESAME) ? ' ' : 'T',
147 (flags & UNINTERESTING) ? 'U' : ' ',
148 (flags & COUNTED) ? 'C' : ' ');
149 if (commit->util)
150 fprintf(stderr, "%3d", weight(p));
151 else
152 fprintf(stderr, "---");
153 fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
154 for (pp = commit->parents; pp; pp = pp->next)
155 fprintf(stderr, " %.*s", 8,
156 sha1_to_hex(pp->item->object.sha1));
157
158 sp = strstr(buf, "\n\n");
159 if (sp) {
160 sp += 2;
161 for (ep = sp; *ep && *ep != '\n'; ep++)
162 ;
163 fprintf(stderr, " %.*s", (int)(ep - sp), sp);
164 }
165 fprintf(stderr, "\n");
166 }
167}
168#endif /* DEBUG_BISECT */
169
170static struct commit_list *best_bisection(struct commit_list *list, int nr)
171{
172 struct commit_list *p, *best;
173 int best_distance = -1;
174
175 best = list;
176 for (p = list; p; p = p->next) {
177 int distance;
178 unsigned flags = p->item->object.flags;
179
180 if (flags & TREESAME)
181 continue;
182 distance = weight(p);
183 if (nr - distance < distance)
184 distance = nr - distance;
185 if (distance > best_distance) {
186 best = p;
187 best_distance = distance;
188 }
189 }
190
191 return best;
192}
193
194struct commit_dist {
195 struct commit *commit;
196 int distance;
197};
198
199static int compare_commit_dist(const void *a_, const void *b_)
200{
201 struct commit_dist *a, *b;
202
203 a = (struct commit_dist *)a_;
204 b = (struct commit_dist *)b_;
205 if (a->distance != b->distance)
206 return b->distance - a->distance; /* desc sort */
207 return hashcmp(a->commit->object.sha1, b->commit->object.sha1);
208}
209
210static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
211{
212 struct commit_list *p;
213 struct commit_dist *array = xcalloc(nr, sizeof(*array));
214 int cnt, i;
215
216 for (p = list, cnt = 0; p; p = p->next) {
217 int distance;
218 unsigned flags = p->item->object.flags;
219
220 if (flags & TREESAME)
221 continue;
222 distance = weight(p);
223 if (nr - distance < distance)
224 distance = nr - distance;
225 array[cnt].commit = p->item;
226 array[cnt].distance = distance;
227 cnt++;
228 }
229 qsort(array, cnt, sizeof(*array), compare_commit_dist);
230 for (p = list, i = 0; i < cnt; i++) {
231 struct name_decoration *r = xmalloc(sizeof(*r) + 100);
232 struct object *obj = &(array[i].commit->object);
233
234 sprintf(r->name, "dist=%d", array[i].distance);
235 r->next = add_decoration(&name_decoration, obj, r);
236 p->item = array[i].commit;
237 p = p->next;
238 }
239 if (p)
240 p->next = NULL;
241 free(array);
242 return list;
243}
244
245/*
246 * zero or positive weight is the number of interesting commits it can
247 * reach, including itself. Especially, weight = 0 means it does not
248 * reach any tree-changing commits (e.g. just above uninteresting one
249 * but traversal is with pathspec).
250 *
251 * weight = -1 means it has one parent and its distance is yet to
252 * be computed.
253 *
254 * weight = -2 means it has more than one parent and its distance is
255 * unknown. After running count_distance() first, they will get zero
256 * or positive distance.
257 */
258static struct commit_list *do_find_bisection(struct commit_list *list,
259 int nr, int *weights,
260 int find_all)
261{
262 int n, counted;
263 struct commit_list *p;
264
265 counted = 0;
266
267 for (n = 0, p = list; p; p = p->next) {
268 struct commit *commit = p->item;
269 unsigned flags = commit->object.flags;
270
271 p->item->util = &weights[n++];
272 switch (count_interesting_parents(commit)) {
273 case 0:
274 if (!(flags & TREESAME)) {
275 weight_set(p, 1);
276 counted++;
277 show_list("bisection 2 count one",
278 counted, nr, list);
279 }
280 /*
281 * otherwise, it is known not to reach any
282 * tree-changing commit and gets weight 0.
283 */
284 break;
285 case 1:
286 weight_set(p, -1);
287 break;
288 default:
289 weight_set(p, -2);
290 break;
291 }
292 }
293
294 show_list("bisection 2 initialize", counted, nr, list);
295
296 /*
297 * If you have only one parent in the resulting set
298 * then you can reach one commit more than that parent
299 * can reach. So we do not have to run the expensive
300 * count_distance() for single strand of pearls.
301 *
302 * However, if you have more than one parents, you cannot
303 * just add their distance and one for yourself, since
304 * they usually reach the same ancestor and you would
305 * end up counting them twice that way.
306 *
307 * So we will first count distance of merges the usual
308 * way, and then fill the blanks using cheaper algorithm.
309 */
310 for (p = list; p; p = p->next) {
311 if (p->item->object.flags & UNINTERESTING)
312 continue;
313 if (weight(p) != -2)
314 continue;
315 weight_set(p, count_distance(p));
316 clear_distance(list);
317
318 /* Does it happen to be at exactly half-way? */
319 if (!find_all && halfway(p, nr))
320 return p;
321 counted++;
322 }
323
324 show_list("bisection 2 count_distance", counted, nr, list);
325
326 while (counted < nr) {
327 for (p = list; p; p = p->next) {
328 struct commit_list *q;
329 unsigned flags = p->item->object.flags;
330
331 if (0 <= weight(p))
332 continue;
333 for (q = p->item->parents; q; q = q->next) {
334 if (q->item->object.flags & UNINTERESTING)
335 continue;
336 if (0 <= weight(q))
337 break;
338 }
339 if (!q)
340 continue;
341
342 /*
343 * weight for p is unknown but q is known.
344 * add one for p itself if p is to be counted,
345 * otherwise inherit it from q directly.
346 */
347 if (!(flags & TREESAME)) {
348 weight_set(p, weight(q)+1);
349 counted++;
350 show_list("bisection 2 count one",
351 counted, nr, list);
352 }
353 else
354 weight_set(p, weight(q));
355
356 /* Does it happen to be at exactly half-way? */
357 if (!find_all && halfway(p, nr))
358 return p;
359 }
360 }
361
362 show_list("bisection 2 counted all", counted, nr, list);
363
364 if (!find_all)
365 return best_bisection(list, nr);
366 else
367 return best_bisection_sorted(list, nr);
368}
369
370struct commit_list *find_bisection(struct commit_list *list,
371 int *reaches, int *all,
372 int find_all)
373{
374 int nr, on_list;
375 struct commit_list *p, *best, *next, *last;
376 int *weights;
377
378 show_list("bisection 2 entry", 0, 0, list);
379
380 /*
381 * Count the number of total and tree-changing items on the
382 * list, while reversing the list.
383 */
384 for (nr = on_list = 0, last = NULL, p = list;
385 p;
386 p = next) {
387 unsigned flags = p->item->object.flags;
388
389 next = p->next;
390 if (flags & UNINTERESTING)
391 continue;
392 p->next = last;
393 last = p;
394 if (!(flags & TREESAME))
395 nr++;
396 on_list++;
397 }
398 list = last;
399 show_list("bisection 2 sorted", 0, nr, list);
400
401 *all = nr;
402 weights = xcalloc(on_list, sizeof(*weights));
403
404 /* Do the real work of finding bisection commit. */
405 best = do_find_bisection(list, nr, weights, find_all);
406 if (best) {
407 if (!find_all)
408 best->next = NULL;
409 *reaches = weight(best);
410 }
411 free(weights);
412 return best;
413}
414
1c953a1f 415static void argv_array_push(struct argv_array *array, const char *string)
3755ccdb 416{
1c953a1f
CC
417 ALLOC_GROW(array->argv, array->argv_nr + 1, array->argv_alloc);
418 array->argv[array->argv_nr++] = string;
419}
3755ccdb 420
1c953a1f
CC
421static void argv_array_push_sha1(struct argv_array *array,
422 const unsigned char *sha1,
423 const char *format)
424{
425 struct strbuf buf = STRBUF_INIT;
3755ccdb 426 strbuf_addf(&buf, format, sha1_to_hex(sha1));
1c953a1f 427 argv_array_push(array, strbuf_detach(&buf, NULL));
3755ccdb
CC
428}
429
fad2d31d
CC
430static void sha1_array_push(struct sha1_array *array,
431 const unsigned char *sha1)
432{
433 ALLOC_GROW(array->sha1, array->sha1_nr + 1, array->sha1_alloc);
434 hashcpy(array->sha1[array->sha1_nr++], sha1);
435}
436
1bf072e3
CC
437static int register_ref(const char *refname, const unsigned char *sha1,
438 int flags, void *cb_data)
439{
440 if (!strcmp(refname, "bad")) {
ef24c7ca 441 current_bad_sha1 = sha1;
1bf072e3 442 } else if (!prefixcmp(refname, "good-")) {
fad2d31d 443 sha1_array_push(&good_revs, sha1);
1bf072e3 444 } else if (!prefixcmp(refname, "skip-")) {
fad2d31d 445 sha1_array_push(&skipped_revs, sha1);
1bf072e3
CC
446 }
447
448 return 0;
449}
450
451static int read_bisect_refs(void)
452{
453 return for_each_ref_in("refs/bisect/", register_ref, NULL);
454}
455
1c953a1f 456void read_bisect_paths(struct argv_array *array)
3b437b0d
CC
457{
458 struct strbuf str = STRBUF_INIT;
459 const char *filename = git_path("BISECT_NAMES");
460 FILE *fp = fopen(filename, "r");
461
462 if (!fp)
463 die("Could not open file '%s': %s", filename, strerror(errno));
464
465 while (strbuf_getline(&str, fp, '\n') != EOF) {
466 char *quoted;
467 int res;
468
469 strbuf_trim(&str);
470 quoted = strbuf_detach(&str, NULL);
1c953a1f
CC
471 res = sq_dequote_to_argv(quoted, &array->argv,
472 &array->argv_nr, &array->argv_alloc);
3b437b0d
CC
473 if (res)
474 die("Badly quoted content in file '%s': %s",
475 filename, quoted);
476 }
477
478 strbuf_release(&str);
479 fclose(fp);
480}
481
95188648
CC
482static int skipcmp(const void *a, const void *b)
483{
484 return hashcmp(a, b);
485}
486
487static void prepare_skipped(void)
488{
6212b1aa
CC
489 qsort(skipped_revs.sha1, skipped_revs.sha1_nr,
490 sizeof(*skipped_revs.sha1), skipcmp);
95188648
CC
491}
492
4eb5b646
CC
493static const unsigned char *skipped_sha1_access(size_t index, void *table)
494{
495 unsigned char (*skipped)[20] = table;
496 return skipped[index];
497}
498
95188648
CC
499static int lookup_skipped(unsigned char *sha1)
500{
6212b1aa 501 return sha1_pos(sha1, skipped_revs.sha1, skipped_revs.sha1_nr,
4eb5b646 502 skipped_sha1_access);
95188648
CC
503}
504
505struct commit_list *filter_skipped(struct commit_list *list,
506 struct commit_list **tried,
507 int show_all)
508{
509 struct commit_list *filtered = NULL, **f = &filtered;
510
511 *tried = NULL;
512
6212b1aa 513 if (!skipped_revs.sha1_nr)
95188648
CC
514 return list;
515
516 prepare_skipped();
517
518 while (list) {
519 struct commit_list *next = list->next;
520 list->next = NULL;
521 if (0 <= lookup_skipped(list->item->object.sha1)) {
522 /* Move current to tried list */
523 *tried = list;
524 tried = &list->next;
525 } else {
526 if (!show_all)
527 return list;
528 /* Move current to filtered list */
529 *f = list;
530 f = &list->next;
531 }
532 list = next;
533 }
534
535 return filtered;
536}
1bf072e3 537
3b437b0d 538static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
1bf072e3 539{
2b020695 540 struct argv_array rev_argv = { NULL, 0, 0 };
fad2d31d
CC
541 int i;
542
3b437b0d
CC
543 init_revisions(revs, prefix);
544 revs->abbrev = 0;
545 revs->commit_format = CMIT_FMT_UNSPECIFIED;
1bf072e3 546
1c953a1f
CC
547 /* rev_argv.argv[0] will be ignored by setup_revisions */
548 argv_array_push(&rev_argv, xstrdup("bisect_rev_setup"));
549 argv_array_push_sha1(&rev_argv, current_bad_sha1, "%s");
fad2d31d 550 for (i = 0; i < good_revs.sha1_nr; i++)
1c953a1f
CC
551 argv_array_push_sha1(&rev_argv, good_revs.sha1[i], "^%s");
552 argv_array_push(&rev_argv, xstrdup("--"));
553 read_bisect_paths(&rev_argv);
554 argv_array_push(&rev_argv, NULL);
3b437b0d 555
1c953a1f 556 setup_revisions(rev_argv.argv_nr, rev_argv.argv, revs, NULL);
3b437b0d
CC
557 revs->limited = 1;
558}
559
2b020695 560static void bisect_common(struct rev_info *revs, int *reaches, int *all)
2ace9727 561{
2ace9727
CC
562 if (prepare_revision_walk(revs))
563 die("revision walk setup failed");
564 if (revs->tree_objects)
565 mark_edges_uninteresting(revs->commits, revs, NULL);
566
567 revs->commits = find_bisection(revs->commits, reaches, all,
6212b1aa 568 !!skipped_revs.sha1_nr);
2ace9727
CC
569}
570
ef24c7ca
CC
571static void exit_if_skipped_commits(struct commit_list *tried,
572 const unsigned char *bad)
573{
574 if (!tried)
575 return;
576
577 printf("There are only 'skip'ped commits left to test.\n"
578 "The first bad commit could be any of:\n");
579 print_commit_list(tried, "%s\n", "%s\n");
580 if (bad)
581 printf("%s\n", sha1_to_hex(bad));
582 printf("We cannot bisect more!\n");
583 exit(2);
584}
585
586static void mark_expected_rev(char *bisect_rev_hex)
587{
588 int len = strlen(bisect_rev_hex);
589 const char *filename = git_path("BISECT_EXPECTED_REV");
590 int fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
591
592 if (fd < 0)
593 die("could not create file '%s': %s",
594 filename, strerror(errno));
595
596 bisect_rev_hex[len] = '\n';
597 write_or_die(fd, bisect_rev_hex, len + 1);
598 bisect_rev_hex[len] = '\0';
599
600 if (close(fd) < 0)
601 die("closing file %s: %s", filename, strerror(errno));
602}
603
604static int bisect_checkout(char *bisect_rev_hex)
605{
606 int res;
607
608 mark_expected_rev(bisect_rev_hex);
609
610 argv_checkout[2] = bisect_rev_hex;
611 res = run_command_v_opt(argv_checkout, RUN_GIT_CMD);
612 if (res)
613 exit(res);
614
615 argv_show_branch[1] = bisect_rev_hex;
616 return run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
617}
618
619/*
620 * We use the convention that exiting with an exit code 10 means that
621 * the bisection process finished successfully.
622 * In this case the calling shell script should exit 0.
623 */
624int bisect_next_exit(const char *prefix)
625{
626 struct rev_info revs;
627 struct commit_list *tried;
628 int reaches = 0, all = 0, nr;
629 const unsigned char *bisect_rev;
630 char bisect_rev_hex[41];
631
2b020695
CC
632 if (read_bisect_refs())
633 die("reading bisect refs failed");
634
635 bisect_rev_setup(&revs, prefix);
636
637 bisect_common(&revs, &reaches, &all);
ef24c7ca
CC
638
639 revs.commits = filter_skipped(revs.commits, &tried, 0);
640
641 if (!revs.commits) {
642 /*
643 * We should exit here only if the "bad"
644 * commit is also a "skip" commit.
645 */
646 exit_if_skipped_commits(tried, NULL);
647
648 printf("%s was both good and bad\n",
649 sha1_to_hex(current_bad_sha1));
650 exit(1);
651 }
652
653 bisect_rev = revs.commits->item->object.sha1;
654 memcpy(bisect_rev_hex, sha1_to_hex(bisect_rev), 41);
655
656 if (!hashcmp(bisect_rev, current_bad_sha1)) {
657 exit_if_skipped_commits(tried, current_bad_sha1);
658 printf("%s is first bad commit\n", bisect_rev_hex);
659 argv_diff_tree[2] = bisect_rev_hex;
660 run_command_v_opt(argv_diff_tree, RUN_GIT_CMD);
661 /* This means the bisection process succeeded. */
662 exit(10);
663 }
664
665 nr = all - reaches - 1;
666 printf("Bisecting: %d revisions left to test after this "
667 "(roughly %d steps)\n", nr, estimate_bisect_steps(all));
668
669 return bisect_checkout(bisect_rev_hex);
670}
671