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