Merge branch 'en/merge-ort-recursive'
[git] / bisect.c
1 #include "cache.h"
2 #include "config.h"
3 #include "commit.h"
4 #include "diff.h"
5 #include "revision.h"
6 #include "refs.h"
7 #include "list-objects.h"
8 #include "quote.h"
9 #include "sha1-lookup.h"
10 #include "run-command.h"
11 #include "log-tree.h"
12 #include "bisect.h"
13 #include "oid-array.h"
14 #include "strvec.h"
15 #include "commit-slab.h"
16 #include "commit-reach.h"
17 #include "object-store.h"
18 #include "dir.h"
19
20 static struct oid_array good_revs;
21 static struct oid_array skipped_revs;
22
23 static struct object_id *current_bad_oid;
24
25 static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
26 static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
27
28 static const char *term_bad;
29 static const char *term_good;
30
31 /* Remember to update object flag allocation in object.h */
32 #define COUNTED         (1u<<16)
33
34 /*
35  * This is a truly stupid algorithm, but it's only
36  * used for bisection, and we just don't care enough.
37  *
38  * We care just barely enough to avoid recursing for
39  * non-merge entries.
40  */
41 static int count_distance(struct commit_list *entry)
42 {
43         int nr = 0;
44
45         while (entry) {
46                 struct commit *commit = entry->item;
47                 struct commit_list *p;
48
49                 if (commit->object.flags & (UNINTERESTING | COUNTED))
50                         break;
51                 if (!(commit->object.flags & TREESAME))
52                         nr++;
53                 commit->object.flags |= COUNTED;
54                 p = commit->parents;
55                 entry = p;
56                 if (p) {
57                         p = p->next;
58                         while (p) {
59                                 nr += count_distance(p);
60                                 p = p->next;
61                         }
62                 }
63         }
64
65         return nr;
66 }
67
68 static void clear_distance(struct commit_list *list)
69 {
70         while (list) {
71                 struct commit *commit = list->item;
72                 commit->object.flags &= ~COUNTED;
73                 list = list->next;
74         }
75 }
76
77 define_commit_slab(commit_weight, int *);
78 static struct commit_weight commit_weight;
79
80 #define DEBUG_BISECT 0
81
82 static inline int weight(struct commit_list *elem)
83 {
84         return **commit_weight_at(&commit_weight, elem->item);
85 }
86
87 static inline void weight_set(struct commit_list *elem, int weight)
88 {
89         **commit_weight_at(&commit_weight, elem->item) = weight;
90 }
91
92 static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)
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                         count++;
100                 if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)
101                         break;
102         }
103         return count;
104 }
105
106 static inline int approx_halfway(struct commit_list *p, int nr)
107 {
108         int diff;
109
110         /*
111          * Don't short-cut something we are not going to return!
112          */
113         if (p->item->object.flags & TREESAME)
114                 return 0;
115         if (DEBUG_BISECT)
116                 return 0;
117         /*
118          * For small number of commits 2 and 3 are halfway of 5, and
119          * 3 is halfway of 6 but 2 and 4 are not.
120          */
121         diff = 2 * weight(p) - nr;
122         switch (diff) {
123         case -1: case 0: case 1:
124                 return 1;
125         default:
126                 /*
127                  * For large number of commits we are not so strict, it's
128                  * good enough if it's within ~0.1% of the halfway point,
129                  * e.g. 5000 is exactly halfway of 10000, but we consider
130                  * the values [4996, 5004] as halfway as well.
131                  */
132                 if (abs(diff) < nr / 1024)
133                         return 1;
134                 return 0;
135         }
136 }
137
138 static void show_list(const char *debug, int counted, int nr,
139                       struct commit_list *list)
140 {
141         struct commit_list *p;
142
143         if (!DEBUG_BISECT)
144                 return;
145
146         fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
147
148         for (p = list; p; p = p->next) {
149                 struct commit_list *pp;
150                 struct commit *commit = p->item;
151                 unsigned commit_flags = commit->object.flags;
152                 enum object_type type;
153                 unsigned long size;
154                 char *buf = read_object_file(&commit->object.oid, &type,
155                                              &size);
156                 const char *subject_start;
157                 int subject_len;
158
159                 fprintf(stderr, "%c%c%c ",
160                         (commit_flags & TREESAME) ? ' ' : 'T',
161                         (commit_flags & UNINTERESTING) ? 'U' : ' ',
162                         (commit_flags & COUNTED) ? 'C' : ' ');
163                 if (*commit_weight_at(&commit_weight, p->item))
164                         fprintf(stderr, "%3d", weight(p));
165                 else
166                         fprintf(stderr, "---");
167                 fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
168                 for (pp = commit->parents; pp; pp = pp->next)
169                         fprintf(stderr, " %.*s", 8,
170                                 oid_to_hex(&pp->item->object.oid));
171
172                 subject_len = find_commit_subject(buf, &subject_start);
173                 if (subject_len)
174                         fprintf(stderr, " %.*s", subject_len, subject_start);
175                 fprintf(stderr, "\n");
176         }
177 }
178
179 static struct commit_list *best_bisection(struct commit_list *list, int nr)
180 {
181         struct commit_list *p, *best;
182         int best_distance = -1;
183
184         best = list;
185         for (p = list; p; p = p->next) {
186                 int distance;
187                 unsigned commit_flags = p->item->object.flags;
188
189                 if (commit_flags & TREESAME)
190                         continue;
191                 distance = weight(p);
192                 if (nr - distance < distance)
193                         distance = nr - distance;
194                 if (distance > best_distance) {
195                         best = p;
196                         best_distance = distance;
197                 }
198         }
199
200         return best;
201 }
202
203 struct commit_dist {
204         struct commit *commit;
205         int distance;
206 };
207
208 static int compare_commit_dist(const void *a_, const void *b_)
209 {
210         struct commit_dist *a, *b;
211
212         a = (struct commit_dist *)a_;
213         b = (struct commit_dist *)b_;
214         if (a->distance != b->distance)
215                 return b->distance - a->distance; /* desc sort */
216         return oidcmp(&a->commit->object.oid, &b->commit->object.oid);
217 }
218
219 static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
220 {
221         struct commit_list *p;
222         struct commit_dist *array = xcalloc(nr, sizeof(*array));
223         struct strbuf buf = STRBUF_INIT;
224         int cnt, i;
225
226         for (p = list, cnt = 0; p; p = p->next) {
227                 int distance;
228                 unsigned commit_flags = p->item->object.flags;
229
230                 if (commit_flags & TREESAME)
231                         continue;
232                 distance = weight(p);
233                 if (nr - distance < distance)
234                         distance = nr - distance;
235                 array[cnt].commit = p->item;
236                 array[cnt].distance = distance;
237                 cnt++;
238         }
239         QSORT(array, cnt, compare_commit_dist);
240         for (p = list, i = 0; i < cnt; i++) {
241                 struct object *obj = &(array[i].commit->object);
242
243                 strbuf_reset(&buf);
244                 strbuf_addf(&buf, "dist=%d", array[i].distance);
245                 add_name_decoration(DECORATION_NONE, buf.buf, obj);
246
247                 p->item = array[i].commit;
248                 if (i < cnt - 1)
249                         p = p->next;
250         }
251         if (p) {
252                 free_commit_list(p->next);
253                 p->next = NULL;
254         }
255         strbuf_release(&buf);
256         free(array);
257         return list;
258 }
259
260 /*
261  * zero or positive weight is the number of interesting commits it can
262  * reach, including itself.  Especially, weight = 0 means it does not
263  * reach any tree-changing commits (e.g. just above uninteresting one
264  * but traversal is with pathspec).
265  *
266  * weight = -1 means it has one parent and its distance is yet to
267  * be computed.
268  *
269  * weight = -2 means it has more than one parent and its distance is
270  * unknown.  After running count_distance() first, they will get zero
271  * or positive distance.
272  */
273 static struct commit_list *do_find_bisection(struct commit_list *list,
274                                              int nr, int *weights,
275                                              unsigned bisect_flags)
276 {
277         int n, counted;
278         struct commit_list *p;
279
280         counted = 0;
281
282         for (n = 0, p = list; p; p = p->next) {
283                 struct commit *commit = p->item;
284                 unsigned commit_flags = commit->object.flags;
285
286                 *commit_weight_at(&commit_weight, p->item) = &weights[n++];
287                 switch (count_interesting_parents(commit, bisect_flags)) {
288                 case 0:
289                         if (!(commit_flags & TREESAME)) {
290                                 weight_set(p, 1);
291                                 counted++;
292                                 show_list("bisection 2 count one",
293                                           counted, nr, list);
294                         }
295                         /*
296                          * otherwise, it is known not to reach any
297                          * tree-changing commit and gets weight 0.
298                          */
299                         break;
300                 case 1:
301                         weight_set(p, -1);
302                         break;
303                 default:
304                         weight_set(p, -2);
305                         break;
306                 }
307         }
308
309         show_list("bisection 2 initialize", counted, nr, list);
310
311         /*
312          * If you have only one parent in the resulting set
313          * then you can reach one commit more than that parent
314          * can reach.  So we do not have to run the expensive
315          * count_distance() for single strand of pearls.
316          *
317          * However, if you have more than one parents, you cannot
318          * just add their distance and one for yourself, since
319          * they usually reach the same ancestor and you would
320          * end up counting them twice that way.
321          *
322          * So we will first count distance of merges the usual
323          * way, and then fill the blanks using cheaper algorithm.
324          */
325         for (p = list; p; p = p->next) {
326                 if (p->item->object.flags & UNINTERESTING)
327                         continue;
328                 if (weight(p) != -2)
329                         continue;
330                 if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)
331                         BUG("shouldn't be calling count-distance in fp mode");
332                 weight_set(p, count_distance(p));
333                 clear_distance(list);
334
335                 /* Does it happen to be at half-way? */
336                 if (!(bisect_flags & FIND_BISECTION_ALL) &&
337                       approx_halfway(p, nr))
338                         return p;
339                 counted++;
340         }
341
342         show_list("bisection 2 count_distance", counted, nr, list);
343
344         while (counted < nr) {
345                 for (p = list; p; p = p->next) {
346                         struct commit_list *q;
347                         unsigned commit_flags = p->item->object.flags;
348
349                         if (0 <= weight(p))
350                                 continue;
351
352                         for (q = p->item->parents;
353                              q;
354                              q = bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY ? NULL : q->next) {
355                                 if (q->item->object.flags & UNINTERESTING)
356                                         continue;
357                                 if (0 <= weight(q))
358                                         break;
359                         }
360                         if (!q)
361                                 continue;
362
363                         /*
364                          * weight for p is unknown but q is known.
365                          * add one for p itself if p is to be counted,
366                          * otherwise inherit it from q directly.
367                          */
368                         if (!(commit_flags & TREESAME)) {
369                                 weight_set(p, weight(q)+1);
370                                 counted++;
371                                 show_list("bisection 2 count one",
372                                           counted, nr, list);
373                         }
374                         else
375                                 weight_set(p, weight(q));
376
377                         /* Does it happen to be at half-way? */
378                         if (!(bisect_flags & FIND_BISECTION_ALL) &&
379                               approx_halfway(p, nr))
380                                 return p;
381                 }
382         }
383
384         show_list("bisection 2 counted all", counted, nr, list);
385
386         if (!(bisect_flags & FIND_BISECTION_ALL))
387                 return best_bisection(list, nr);
388         else
389                 return best_bisection_sorted(list, nr);
390 }
391
392 void find_bisection(struct commit_list **commit_list, int *reaches,
393                     int *all, unsigned bisect_flags)
394 {
395         int nr, on_list;
396         struct commit_list *list, *p, *best, *next, *last;
397         int *weights;
398
399         show_list("bisection 2 entry", 0, 0, *commit_list);
400         init_commit_weight(&commit_weight);
401
402         /*
403          * Count the number of total and tree-changing items on the
404          * list, while reversing the list.
405          */
406         for (nr = on_list = 0, last = NULL, p = *commit_list;
407              p;
408              p = next) {
409                 unsigned commit_flags = p->item->object.flags;
410
411                 next = p->next;
412                 if (commit_flags & UNINTERESTING) {
413                         free(p);
414                         continue;
415                 }
416                 p->next = last;
417                 last = p;
418                 if (!(commit_flags & TREESAME))
419                         nr++;
420                 on_list++;
421         }
422         list = last;
423         show_list("bisection 2 sorted", 0, nr, list);
424
425         *all = nr;
426         weights = xcalloc(on_list, sizeof(*weights));
427
428         /* Do the real work of finding bisection commit. */
429         best = do_find_bisection(list, nr, weights, bisect_flags);
430         if (best) {
431                 if (!(bisect_flags & FIND_BISECTION_ALL)) {
432                         list->item = best->item;
433                         free_commit_list(list->next);
434                         best = list;
435                         best->next = NULL;
436                 }
437                 *reaches = weight(best);
438         }
439         free(weights);
440         *commit_list = best;
441         clear_commit_weight(&commit_weight);
442 }
443
444 static int register_ref(const char *refname, const struct object_id *oid,
445                         int flags, void *cb_data)
446 {
447         struct strbuf good_prefix = STRBUF_INIT;
448         strbuf_addstr(&good_prefix, term_good);
449         strbuf_addstr(&good_prefix, "-");
450
451         if (!strcmp(refname, term_bad)) {
452                 current_bad_oid = xmalloc(sizeof(*current_bad_oid));
453                 oidcpy(current_bad_oid, oid);
454         } else if (starts_with(refname, good_prefix.buf)) {
455                 oid_array_append(&good_revs, oid);
456         } else if (starts_with(refname, "skip-")) {
457                 oid_array_append(&skipped_revs, oid);
458         }
459
460         strbuf_release(&good_prefix);
461
462         return 0;
463 }
464
465 static int read_bisect_refs(void)
466 {
467         return for_each_ref_in("refs/bisect/", register_ref, NULL);
468 }
469
470 static GIT_PATH_FUNC(git_path_bisect_names, "BISECT_NAMES")
471 static GIT_PATH_FUNC(git_path_bisect_expected_rev, "BISECT_EXPECTED_REV")
472 static GIT_PATH_FUNC(git_path_bisect_ancestors_ok, "BISECT_ANCESTORS_OK")
473 static GIT_PATH_FUNC(git_path_bisect_run, "BISECT_RUN")
474 static GIT_PATH_FUNC(git_path_bisect_start, "BISECT_START")
475 static GIT_PATH_FUNC(git_path_bisect_log, "BISECT_LOG")
476 static GIT_PATH_FUNC(git_path_bisect_terms, "BISECT_TERMS")
477 static GIT_PATH_FUNC(git_path_bisect_first_parent, "BISECT_FIRST_PARENT")
478 static GIT_PATH_FUNC(git_path_head_name, "head-name")
479
480 static void read_bisect_paths(struct strvec *array)
481 {
482         struct strbuf str = STRBUF_INIT;
483         const char *filename = git_path_bisect_names();
484         FILE *fp = xfopen(filename, "r");
485
486         while (strbuf_getline_lf(&str, fp) != EOF) {
487                 strbuf_trim(&str);
488                 if (sq_dequote_to_strvec(str.buf, array))
489                         die(_("Badly quoted content in file '%s': %s"),
490                             filename, str.buf);
491         }
492
493         strbuf_release(&str);
494         fclose(fp);
495 }
496
497 static char *join_oid_array_hex(struct oid_array *array, char delim)
498 {
499         struct strbuf joined_hexs = STRBUF_INIT;
500         int i;
501
502         for (i = 0; i < array->nr; i++) {
503                 strbuf_addstr(&joined_hexs, oid_to_hex(array->oid + i));
504                 if (i + 1 < array->nr)
505                         strbuf_addch(&joined_hexs, delim);
506         }
507
508         return strbuf_detach(&joined_hexs, NULL);
509 }
510
511 /*
512  * In this function, passing a not NULL skipped_first is very special.
513  * It means that we want to know if the first commit in the list is
514  * skipped because we will want to test a commit away from it if it is
515  * indeed skipped.
516  * So if the first commit is skipped, we cannot take the shortcut to
517  * just "return list" when we find the first non skipped commit, we
518  * have to return a fully filtered list.
519  *
520  * We use (*skipped_first == -1) to mean "it has been found that the
521  * first commit is not skipped". In this case *skipped_first is set back
522  * to 0 just before the function returns.
523  */
524 struct commit_list *filter_skipped(struct commit_list *list,
525                                    struct commit_list **tried,
526                                    int show_all,
527                                    int *count,
528                                    int *skipped_first)
529 {
530         struct commit_list *filtered = NULL, **f = &filtered;
531
532         *tried = NULL;
533
534         if (skipped_first)
535                 *skipped_first = 0;
536         if (count)
537                 *count = 0;
538
539         if (!skipped_revs.nr)
540                 return list;
541
542         while (list) {
543                 struct commit_list *next = list->next;
544                 list->next = NULL;
545                 if (0 <= oid_array_lookup(&skipped_revs, &list->item->object.oid)) {
546                         if (skipped_first && !*skipped_first)
547                                 *skipped_first = 1;
548                         /* Move current to tried list */
549                         *tried = list;
550                         tried = &list->next;
551                 } else {
552                         if (!show_all) {
553                                 if (!skipped_first || !*skipped_first)
554                                         return list;
555                         } else if (skipped_first && !*skipped_first) {
556                                 /* This means we know it's not skipped */
557                                 *skipped_first = -1;
558                         }
559                         /* Move current to filtered list */
560                         *f = list;
561                         f = &list->next;
562                         if (count)
563                                 (*count)++;
564                 }
565                 list = next;
566         }
567
568         if (skipped_first && *skipped_first == -1)
569                 *skipped_first = 0;
570
571         return filtered;
572 }
573
574 #define PRN_MODULO 32768
575
576 /*
577  * This is a pseudo random number generator based on "man 3 rand".
578  * It is not used properly because the seed is the argument and it
579  * is increased by one between each call, but that should not matter
580  * for this application.
581  */
582 static unsigned get_prn(unsigned count)
583 {
584         count = count * 1103515245 + 12345;
585         return (count/65536) % PRN_MODULO;
586 }
587
588 /*
589  * Custom integer square root from
590  * https://en.wikipedia.org/wiki/Integer_square_root
591  */
592 static int sqrti(int val)
593 {
594         float d, x = val;
595
596         if (!val)
597                 return 0;
598
599         do {
600                 float y = (x + (float)val / x) / 2;
601                 d = (y > x) ? y - x : x - y;
602                 x = y;
603         } while (d >= 0.5);
604
605         return (int)x;
606 }
607
608 static struct commit_list *skip_away(struct commit_list *list, int count)
609 {
610         struct commit_list *cur, *previous;
611         int prn, index, i;
612
613         prn = get_prn(count);
614         index = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO);
615
616         cur = list;
617         previous = NULL;
618
619         for (i = 0; cur; cur = cur->next, i++) {
620                 if (i == index) {
621                         if (!oideq(&cur->item->object.oid, current_bad_oid))
622                                 return cur;
623                         if (previous)
624                                 return previous;
625                         return list;
626                 }
627                 previous = cur;
628         }
629
630         return list;
631 }
632
633 static struct commit_list *managed_skipped(struct commit_list *list,
634                                            struct commit_list **tried)
635 {
636         int count, skipped_first;
637
638         *tried = NULL;
639
640         if (!skipped_revs.nr)
641                 return list;
642
643         list = filter_skipped(list, tried, 0, &count, &skipped_first);
644
645         if (!skipped_first)
646                 return list;
647
648         return skip_away(list, count);
649 }
650
651 static void bisect_rev_setup(struct repository *r, struct rev_info *revs,
652                              const char *prefix,
653                              const char *bad_format, const char *good_format,
654                              int read_paths)
655 {
656         struct strvec rev_argv = STRVEC_INIT;
657         int i;
658
659         repo_init_revisions(r, revs, prefix);
660         revs->abbrev = 0;
661         revs->commit_format = CMIT_FMT_UNSPECIFIED;
662
663         /* rev_argv.argv[0] will be ignored by setup_revisions */
664         strvec_push(&rev_argv, "bisect_rev_setup");
665         strvec_pushf(&rev_argv, bad_format, oid_to_hex(current_bad_oid));
666         for (i = 0; i < good_revs.nr; i++)
667                 strvec_pushf(&rev_argv, good_format,
668                              oid_to_hex(good_revs.oid + i));
669         strvec_push(&rev_argv, "--");
670         if (read_paths)
671                 read_bisect_paths(&rev_argv);
672
673         setup_revisions(rev_argv.nr, rev_argv.v, revs, NULL);
674         /* XXX leak rev_argv, as "revs" may still be pointing to it */
675 }
676
677 static void bisect_common(struct rev_info *revs)
678 {
679         if (prepare_revision_walk(revs))
680                 die("revision walk setup failed");
681         if (revs->tree_objects)
682                 mark_edges_uninteresting(revs, NULL, 0);
683 }
684
685 static enum bisect_error error_if_skipped_commits(struct commit_list *tried,
686                                     const struct object_id *bad)
687 {
688         if (!tried)
689                 return BISECT_OK;
690
691         printf("There are only 'skip'ped commits left to test.\n"
692                "The first %s commit could be any of:\n", term_bad);
693
694         for ( ; tried; tried = tried->next)
695                 printf("%s\n", oid_to_hex(&tried->item->object.oid));
696
697         if (bad)
698                 printf("%s\n", oid_to_hex(bad));
699         printf(_("We cannot bisect more!\n"));
700
701         return BISECT_ONLY_SKIPPED_LEFT;
702 }
703
704 static int is_expected_rev(const struct object_id *oid)
705 {
706         const char *filename = git_path_bisect_expected_rev();
707         struct stat st;
708         struct strbuf str = STRBUF_INIT;
709         FILE *fp;
710         int res = 0;
711
712         if (stat(filename, &st) || !S_ISREG(st.st_mode))
713                 return 0;
714
715         fp = fopen_or_warn(filename, "r");
716         if (!fp)
717                 return 0;
718
719         if (strbuf_getline_lf(&str, fp) != EOF)
720                 res = !strcmp(str.buf, oid_to_hex(oid));
721
722         strbuf_release(&str);
723         fclose(fp);
724
725         return res;
726 }
727
728 static enum bisect_error bisect_checkout(const struct object_id *bisect_rev, int no_checkout)
729 {
730         char bisect_rev_hex[GIT_MAX_HEXSZ + 1];
731         enum bisect_error res = BISECT_OK;
732
733         oid_to_hex_r(bisect_rev_hex, bisect_rev);
734         update_ref(NULL, "BISECT_EXPECTED_REV", bisect_rev, NULL, 0, UPDATE_REFS_DIE_ON_ERR);
735
736         argv_checkout[2] = bisect_rev_hex;
737         if (no_checkout) {
738                 update_ref(NULL, "BISECT_HEAD", bisect_rev, NULL, 0,
739                            UPDATE_REFS_DIE_ON_ERR);
740         } else {
741                 res = run_command_v_opt(argv_checkout, RUN_GIT_CMD);
742                 if (res)
743                         /*
744                          * Errors in `run_command()` itself, signaled by res < 0,
745                          * and errors in the child process, signaled by res > 0
746                          * can both be treated as regular BISECT_FAILURE (-1).
747                          */
748                         return -abs(res);
749         }
750
751         argv_show_branch[1] = bisect_rev_hex;
752         res = run_command_v_opt(argv_show_branch, RUN_GIT_CMD);
753         /*
754          * Errors in `run_command()` itself, signaled by res < 0,
755          * and errors in the child process, signaled by res > 0
756          * can both be treated as regular BISECT_FAILURE (-1).
757          */
758         return -abs(res);
759 }
760
761 static struct commit *get_commit_reference(struct repository *r,
762                                            const struct object_id *oid)
763 {
764         struct commit *c = lookup_commit_reference(r, oid);
765         if (!c)
766                 die(_("Not a valid commit name %s"), oid_to_hex(oid));
767         return c;
768 }
769
770 static struct commit **get_bad_and_good_commits(struct repository *r,
771                                                 int *rev_nr)
772 {
773         struct commit **rev;
774         int i, n = 0;
775
776         ALLOC_ARRAY(rev, 1 + good_revs.nr);
777         rev[n++] = get_commit_reference(r, current_bad_oid);
778         for (i = 0; i < good_revs.nr; i++)
779                 rev[n++] = get_commit_reference(r, good_revs.oid + i);
780         *rev_nr = n;
781
782         return rev;
783 }
784
785 static enum bisect_error handle_bad_merge_base(void)
786 {
787         if (is_expected_rev(current_bad_oid)) {
788                 char *bad_hex = oid_to_hex(current_bad_oid);
789                 char *good_hex = join_oid_array_hex(&good_revs, ' ');
790                 if (!strcmp(term_bad, "bad") && !strcmp(term_good, "good")) {
791                         fprintf(stderr, _("The merge base %s is bad.\n"
792                                 "This means the bug has been fixed "
793                                 "between %s and [%s].\n"),
794                                 bad_hex, bad_hex, good_hex);
795                 } else if (!strcmp(term_bad, "new") && !strcmp(term_good, "old")) {
796                         fprintf(stderr, _("The merge base %s is new.\n"
797                                 "The property has changed "
798                                 "between %s and [%s].\n"),
799                                 bad_hex, bad_hex, good_hex);
800                 } else {
801                         fprintf(stderr, _("The merge base %s is %s.\n"
802                                 "This means the first '%s' commit is "
803                                 "between %s and [%s].\n"),
804                                 bad_hex, term_bad, term_good, bad_hex, good_hex);
805                 }
806                 return BISECT_MERGE_BASE_CHECK;
807         }
808
809         fprintf(stderr, _("Some %s revs are not ancestors of the %s rev.\n"
810                 "git bisect cannot work properly in this case.\n"
811                 "Maybe you mistook %s and %s revs?\n"),
812                 term_good, term_bad, term_good, term_bad);
813         return BISECT_FAILED;
814 }
815
816 static void handle_skipped_merge_base(const struct object_id *mb)
817 {
818         char *mb_hex = oid_to_hex(mb);
819         char *bad_hex = oid_to_hex(current_bad_oid);
820         char *good_hex = join_oid_array_hex(&good_revs, ' ');
821
822         warning(_("the merge base between %s and [%s] "
823                 "must be skipped.\n"
824                 "So we cannot be sure the first %s commit is "
825                 "between %s and %s.\n"
826                 "We continue anyway."),
827                 bad_hex, good_hex, term_bad, mb_hex, bad_hex);
828         free(good_hex);
829 }
830
831 /*
832  * "check_merge_bases" checks that merge bases are not "bad" (or "new").
833  *
834  * - If one is "bad" (or "new"), it means the user assumed something wrong
835  * and we must return error with a non 0 error code.
836  * - If one is "good" (or "old"), that's good, we have nothing to do.
837  * - If one is "skipped", we can't know but we should warn.
838  * - If we don't know, we should check it out and ask the user to test.
839  * - If a merge base must be tested, on success return
840  * BISECT_INTERNAL_SUCCESS_MERGE_BASE (-11) a special condition
841  * for early success, this will be converted back to 0 in
842  * check_good_are_ancestors_of_bad().
843  */
844 static enum bisect_error check_merge_bases(int rev_nr, struct commit **rev, int no_checkout)
845 {
846         enum bisect_error res = BISECT_OK;
847         struct commit_list *result;
848
849         result = get_merge_bases_many(rev[0], rev_nr - 1, rev + 1);
850
851         for (; result; result = result->next) {
852                 const struct object_id *mb = &result->item->object.oid;
853                 if (oideq(mb, current_bad_oid)) {
854                         res = handle_bad_merge_base();
855                         break;
856                 } else if (0 <= oid_array_lookup(&good_revs, mb)) {
857                         continue;
858                 } else if (0 <= oid_array_lookup(&skipped_revs, mb)) {
859                         handle_skipped_merge_base(mb);
860                 } else {
861                         printf(_("Bisecting: a merge base must be tested\n"));
862                         res = bisect_checkout(mb, no_checkout);
863                         if (!res)
864                                 /* indicate early success */
865                                 res = BISECT_INTERNAL_SUCCESS_MERGE_BASE;
866                         break;
867                 }
868         }
869
870         free_commit_list(result);
871         return res;
872 }
873
874 static int check_ancestors(struct repository *r, int rev_nr,
875                            struct commit **rev, const char *prefix)
876 {
877         struct rev_info revs;
878         int res;
879
880         bisect_rev_setup(r, &revs, prefix, "^%s", "%s", 0);
881
882         bisect_common(&revs);
883         res = (revs.commits != NULL);
884
885         /* Clean up objects used, as they will be reused. */
886         clear_commit_marks_many(rev_nr, rev, ALL_REV_FLAGS);
887
888         return res;
889 }
890
891 /*
892  * "check_good_are_ancestors_of_bad" checks that all "good" revs are
893  * ancestor of the "bad" rev.
894  *
895  * If that's not the case, we need to check the merge bases.
896  * If a merge base must be tested by the user, its source code will be
897  * checked out to be tested by the user and we will return.
898  */
899
900 static enum bisect_error check_good_are_ancestors_of_bad(struct repository *r,
901                                             const char *prefix,
902                                             int no_checkout)
903 {
904         char *filename;
905         struct stat st;
906         int fd, rev_nr;
907         enum bisect_error res = BISECT_OK;
908         struct commit **rev;
909
910         if (!current_bad_oid)
911                 return error(_("a %s revision is needed"), term_bad);
912
913         filename = git_pathdup("BISECT_ANCESTORS_OK");
914
915         /* Check if file BISECT_ANCESTORS_OK exists. */
916         if (!stat(filename, &st) && S_ISREG(st.st_mode))
917                 goto done;
918
919         /* Bisecting with no good rev is ok. */
920         if (!good_revs.nr)
921                 goto done;
922
923         /* Check if all good revs are ancestor of the bad rev. */
924
925         rev = get_bad_and_good_commits(r, &rev_nr);
926         if (check_ancestors(r, rev_nr, rev, prefix))
927                 res = check_merge_bases(rev_nr, rev, no_checkout);
928         free(rev);
929
930         if (!res) {
931                 /* Create file BISECT_ANCESTORS_OK. */
932                 fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
933                 if (fd < 0)
934                         /*
935                          * BISECT_ANCESTORS_OK file is not absolutely necessary,
936                          * the bisection process will continue at the next
937                          * bisection step.
938                          * So, just signal with a warning that something
939                          * might be wrong.
940                          */
941                         warning_errno(_("could not create file '%s'"),
942                                 filename);
943                 else
944                         close(fd);
945         }
946  done:
947         free(filename);
948         return res;
949 }
950
951 /*
952  * This does "git diff-tree --pretty COMMIT" without one fork+exec.
953  */
954 static void show_diff_tree(struct repository *r,
955                            const char *prefix,
956                            struct commit *commit)
957 {
958         const char *argv[] = {
959                 "diff-tree", "--pretty", "--stat", "--summary", "--cc", NULL
960         };
961         struct rev_info opt;
962
963         git_config(git_diff_ui_config, NULL);
964         repo_init_revisions(r, &opt, prefix);
965
966         setup_revisions(ARRAY_SIZE(argv) - 1, argv, &opt, NULL);
967         log_tree_commit(&opt, commit);
968 }
969
970 /*
971  * The terms used for this bisect session are stored in BISECT_TERMS.
972  * We read them and store them to adapt the messages accordingly.
973  * Default is bad/good.
974  */
975 void read_bisect_terms(const char **read_bad, const char **read_good)
976 {
977         struct strbuf str = STRBUF_INIT;
978         const char *filename = git_path_bisect_terms();
979         FILE *fp = fopen(filename, "r");
980
981         if (!fp) {
982                 if (errno == ENOENT) {
983                         *read_bad = "bad";
984                         *read_good = "good";
985                         return;
986                 } else {
987                         die_errno(_("could not read file '%s'"), filename);
988                 }
989         } else {
990                 strbuf_getline_lf(&str, fp);
991                 *read_bad = strbuf_detach(&str, NULL);
992                 strbuf_getline_lf(&str, fp);
993                 *read_good = strbuf_detach(&str, NULL);
994         }
995         strbuf_release(&str);
996         fclose(fp);
997 }
998
999 /*
1000  * We use the convention that return BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND (-10) means
1001  * the bisection process finished successfully.
1002  * In this case the calling function or command should not turn a
1003  * BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND return code into an error or a non zero exit code.
1004  *
1005  * Checking BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND
1006  * in bisect_helper::bisect_next() and only transforming it to 0 at
1007  * the end of bisect_helper::cmd_bisect__helper() helps bypassing
1008  * all the code related to finding a commit to test.
1009  */
1010 enum bisect_error bisect_next_all(struct repository *r, const char *prefix)
1011 {
1012         struct rev_info revs;
1013         struct commit_list *tried;
1014         int reaches = 0, all = 0, nr, steps;
1015         enum bisect_error res = BISECT_OK;
1016         struct object_id *bisect_rev;
1017         char *steps_msg;
1018         /*
1019          * If no_checkout is non-zero, the bisection process does not
1020          * checkout the trial commit but instead simply updates BISECT_HEAD.
1021          */
1022         int no_checkout = ref_exists("BISECT_HEAD");
1023         unsigned bisect_flags = 0;
1024
1025         read_bisect_terms(&term_bad, &term_good);
1026         if (read_bisect_refs())
1027                 die(_("reading bisect refs failed"));
1028
1029         if (file_exists(git_path_bisect_first_parent()))
1030                 bisect_flags |= FIND_BISECTION_FIRST_PARENT_ONLY;
1031
1032         if (skipped_revs.nr)
1033                 bisect_flags |= FIND_BISECTION_ALL;
1034
1035         res = check_good_are_ancestors_of_bad(r, prefix, no_checkout);
1036         if (res)
1037                 return res;
1038
1039         bisect_rev_setup(r, &revs, prefix, "%s", "^%s", 1);
1040
1041         revs.first_parent_only = !!(bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY);
1042         revs.limited = 1;
1043
1044         bisect_common(&revs);
1045
1046         find_bisection(&revs.commits, &reaches, &all, bisect_flags);
1047         revs.commits = managed_skipped(revs.commits, &tried);
1048
1049         if (!revs.commits) {
1050                 /*
1051                  * We should return error here only if the "bad"
1052                  * commit is also a "skip" commit.
1053                  */
1054                 res = error_if_skipped_commits(tried, NULL);
1055                 if (res < 0)
1056                         return res;
1057                 printf(_("%s was both %s and %s\n"),
1058                        oid_to_hex(current_bad_oid),
1059                        term_good,
1060                        term_bad);
1061
1062                 return BISECT_FAILED;
1063         }
1064
1065         if (!all) {
1066                 fprintf(stderr, _("No testable commit found.\n"
1067                         "Maybe you started with bad path parameters?\n"));
1068
1069                 return BISECT_NO_TESTABLE_COMMIT;
1070         }
1071
1072         bisect_rev = &revs.commits->item->object.oid;
1073
1074         if (oideq(bisect_rev, current_bad_oid)) {
1075                 res = error_if_skipped_commits(tried, current_bad_oid);
1076                 if (res)
1077                         return res;
1078                 printf("%s is the first %s commit\n", oid_to_hex(bisect_rev),
1079                         term_bad);
1080
1081                 show_diff_tree(r, prefix, revs.commits->item);
1082                 /*
1083                  * This means the bisection process succeeded.
1084                  * Using BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND (-10)
1085                  * so that the call chain can simply check
1086                  * for negative return values for early returns up
1087                  * until the cmd_bisect__helper() caller.
1088                  */
1089                 return BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND;
1090         }
1091
1092         nr = all - reaches - 1;
1093         steps = estimate_bisect_steps(all);
1094
1095         steps_msg = xstrfmt(Q_("(roughly %d step)", "(roughly %d steps)",
1096                   steps), steps);
1097         /*
1098          * TRANSLATORS: the last %s will be replaced with "(roughly %d
1099          * steps)" translation.
1100          */
1101         printf(Q_("Bisecting: %d revision left to test after this %s\n",
1102                   "Bisecting: %d revisions left to test after this %s\n",
1103                   nr), nr, steps_msg);
1104         free(steps_msg);
1105         /* Clean up objects used, as they will be reused. */
1106         repo_clear_commit_marks(r, ALL_REV_FLAGS);
1107
1108         return bisect_checkout(bisect_rev, no_checkout);
1109 }
1110
1111 static inline int log2i(int n)
1112 {
1113         int log2 = 0;
1114
1115         for (; n > 1; n >>= 1)
1116                 log2++;
1117
1118         return log2;
1119 }
1120
1121 static inline int exp2i(int n)
1122 {
1123         return 1 << n;
1124 }
1125
1126 /*
1127  * Estimate the number of bisect steps left (after the current step)
1128  *
1129  * For any x between 0 included and 2^n excluded, the probability for
1130  * n - 1 steps left looks like:
1131  *
1132  * P(2^n + x) == (2^n - x) / (2^n + x)
1133  *
1134  * and P(2^n + x) < 0.5 means 2^n < 3x
1135  */
1136 int estimate_bisect_steps(int all)
1137 {
1138         int n, x, e;
1139
1140         if (all < 3)
1141                 return 0;
1142
1143         n = log2i(all);
1144         e = exp2i(n);
1145         x = all - e;
1146
1147         return (e < 3 * x) ? n : n - 1;
1148 }
1149
1150 static int mark_for_removal(const char *refname, const struct object_id *oid,
1151                             int flag, void *cb_data)
1152 {
1153         struct string_list *refs = cb_data;
1154         char *ref = xstrfmt("refs/bisect%s", refname);
1155         string_list_append(refs, ref);
1156         return 0;
1157 }
1158
1159 int bisect_clean_state(void)
1160 {
1161         int result = 0;
1162
1163         /* There may be some refs packed during bisection */
1164         struct string_list refs_for_removal = STRING_LIST_INIT_NODUP;
1165         for_each_ref_in("refs/bisect", mark_for_removal, (void *) &refs_for_removal);
1166         string_list_append(&refs_for_removal, xstrdup("BISECT_HEAD"));
1167         result = delete_refs("bisect: remove", &refs_for_removal, REF_NO_DEREF);
1168         refs_for_removal.strdup_strings = 1;
1169         string_list_clear(&refs_for_removal, 0);
1170         unlink_or_warn(git_path_bisect_expected_rev());
1171         unlink_or_warn(git_path_bisect_ancestors_ok());
1172         unlink_or_warn(git_path_bisect_log());
1173         unlink_or_warn(git_path_bisect_names());
1174         unlink_or_warn(git_path_bisect_run());
1175         unlink_or_warn(git_path_bisect_terms());
1176         unlink_or_warn(git_path_bisect_first_parent());
1177         /* Cleanup head-name if it got left by an old version of git-bisect */
1178         unlink_or_warn(git_path_head_name());
1179         /*
1180          * Cleanup BISECT_START last to support the --no-checkout option
1181          * introduced in the commit 4796e823a.
1182          */
1183         unlink_or_warn(git_path_bisect_start());
1184
1185         return result;
1186 }