git

1
#define USE_THE_REPOSITORY_VARIABLE
2

3
#include "git-compat-util.h"
4
#include "config.h"
5
#include "commit.h"
6
#include "diff.h"
7
#include "environment.h"
8
#include "gettext.h"
9
#include "hex.h"
10
#include "revision.h"
11
#include "refs.h"
12
#include "list-objects.h"
13
#include "quote.h"
14
#include "run-command.h"
15
#include "log-tree.h"
16
#include "bisect.h"
17
#include "oid-array.h"
18
#include "strvec.h"
19
#include "commit-slab.h"
20
#include "commit-reach.h"
21
#include "object-name.h"
22
#include "object-store-ll.h"
23
#include "path.h"
24
#include "dir.h"
25

26
static struct oid_array good_revs;
27
static struct oid_array skipped_revs;
28

29
static struct object_id *current_bad_oid;
30

31
static const char *term_bad;
32
static const char *term_good;
33

34
/* Remember to update object flag allocation in object.h */
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
 */
44
static 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

71
static 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_commit_slab(commit_weight, int *);
81
static struct commit_weight commit_weight;
82

83
#define DEBUG_BISECT 0
84

85
static inline int weight(struct commit_list *elem)
86
{
87
	return **commit_weight_at(&commit_weight, elem->item);
88
}
89

90
static inline void weight_set(struct commit_list *elem, int weight)
91
{
92
	**commit_weight_at(&commit_weight, elem->item) = weight;
93
}
94

95
static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)
96
{
97
	struct commit_list *p;
98
	int count;
99

100
	for (count = 0, p = commit->parents; p; p = p->next) {
101
		if (!(p->item->object.flags & UNINTERESTING))
102
			count++;
103
		if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)
104
			break;
105
	}
106
	return count;
107
}
108

109
static inline int approx_halfway(struct commit_list *p, int nr)
110
{
111
	int diff;
112

113
	/*
114
	 * Don't short-cut something we are not going to return!
115
	 */
116
	if (p->item->object.flags & TREESAME)
117
		return 0;
118
	if (DEBUG_BISECT)
119
		return 0;
120
	/*
121
	 * For small number of commits 2 and 3 are halfway of 5, and
122
	 * 3 is halfway of 6 but 2 and 4 are not.
123
	 */
124
	diff = 2 * weight(p) - nr;
125
	switch (diff) {
126
	case -1: case 0: case 1:
127
		return 1;
128
	default:
129
		/*
130
		 * For large number of commits we are not so strict, it's
131
		 * good enough if it's within ~0.1% of the halfway point,
132
		 * e.g. 5000 is exactly halfway of 10000, but we consider
133
		 * the values [4996, 5004] as halfway as well.
134
		 */
135
		if (abs(diff) < nr / 1024)
136
			return 1;
137
		return 0;
138
	}
139
}
140

141
static void show_list(const char *debug, int counted, int nr,
142
		      struct commit_list *list)
143
{
144
	struct commit_list *p;
145

146
	if (!DEBUG_BISECT)
147
		return;
148

149
	fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
150

151
	for (p = list; p; p = p->next) {
152
		struct commit_list *pp;
153
		struct commit *commit = p->item;
154
		unsigned commit_flags = commit->object.flags;
155
		enum object_type type;
156
		unsigned long size;
157
		char *buf = repo_read_object_file(the_repository,
158
						  &commit->object.oid, &type,
159
						  &size);
160
		const char *subject_start;
161
		int subject_len;
162

163
		if (!buf)
164
			die(_("unable to read %s"), oid_to_hex(&commit->object.oid));
165

166
		fprintf(stderr, "%c%c%c ",
167
			(commit_flags & TREESAME) ? ' ' : 'T',
168
			(commit_flags & UNINTERESTING) ? 'U' : ' ',
169
			(commit_flags & COUNTED) ? 'C' : ' ');
170
		if (*commit_weight_at(&commit_weight, p->item))
171
			fprintf(stderr, "%3d", weight(p));
172
		else
173
			fprintf(stderr, "---");
174
		fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
175
		for (pp = commit->parents; pp; pp = pp->next)
176
			fprintf(stderr, " %.*s", 8,
177
				oid_to_hex(&pp->item->object.oid));
178

179
		subject_len = find_commit_subject(buf, &subject_start);
180
		if (subject_len)
181
			fprintf(stderr, " %.*s", subject_len, subject_start);
182
		fprintf(stderr, "\n");
183
	}
184
}
185

186
static struct commit_list *best_bisection(struct commit_list *list, int nr)
187
{
188
	struct commit_list *p, *best;
189
	int best_distance = -1;
190

191
	best = list;
192
	for (p = list; p; p = p->next) {
193
		int distance;
194
		unsigned commit_flags = p->item->object.flags;
195

196
		if (commit_flags & TREESAME)
197
			continue;
198
		distance = weight(p);
199
		if (nr - distance < distance)
200
			distance = nr - distance;
201
		if (distance > best_distance) {
202
			best = p;
203
			best_distance = distance;
204
		}
205
	}
206

207
	return best;
208
}
209

210
struct commit_dist {
211
	struct commit *commit;
212
	int distance;
213
};
214

215
static int compare_commit_dist(const void *a_, const void *b_)
216
{
217
	struct commit_dist *a, *b;
218

219
	a = (struct commit_dist *)a_;
220
	b = (struct commit_dist *)b_;
221
	if (a->distance != b->distance)
222
		return b->distance - a->distance; /* desc sort */
223
	return oidcmp(&a->commit->object.oid, &b->commit->object.oid);
224
}
225

226
static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
227
{
228
	struct commit_list *p;
229
	struct commit_dist *array = xcalloc(nr, sizeof(*array));
230
	struct strbuf buf = STRBUF_INIT;
231
	int cnt, i;
232

233
	for (p = list, cnt = 0; p; p = p->next) {
234
		int distance;
235
		unsigned commit_flags = p->item->object.flags;
236

237
		if (commit_flags & TREESAME)
238
			continue;
239
		distance = weight(p);
240
		if (nr - distance < distance)
241
			distance = nr - distance;
242
		array[cnt].commit = p->item;
243
		array[cnt].distance = distance;
244
		cnt++;
245
	}
246
	QSORT(array, cnt, compare_commit_dist);
247
	for (p = list, i = 0; i < cnt; i++) {
248
		struct object *obj = &(array[i].commit->object);
249

250
		strbuf_reset(&buf);
251
		strbuf_addf(&buf, "dist=%d", array[i].distance);
252
		add_name_decoration(DECORATION_NONE, buf.buf, obj);
253

254
		p->item = array[i].commit;
255
		if (i < cnt - 1)
256
			p = p->next;
257
	}
258
	if (p) {
259
		free_commit_list(p->next);
260
		p->next = NULL;
261
	}
262
	strbuf_release(&buf);
263
	free(array);
264
	return list;
265
}
266

267
/*
268
 * zero or positive weight is the number of interesting commits it can
269
 * reach, including itself.  Especially, weight = 0 means it does not
270
 * reach any tree-changing commits (e.g. just above uninteresting one
271
 * but traversal is with pathspec).
272
 *
273
 * weight = -1 means it has one parent and its distance is yet to
274
 * be computed.
275
 *
276
 * weight = -2 means it has more than one parent and its distance is
277
 * unknown.  After running count_distance() first, they will get zero
278
 * or positive distance.
279
 */
280
static struct commit_list *do_find_bisection(struct commit_list *list,
281
					     int nr, int *weights,
282
					     unsigned bisect_flags)
283
{
284
	int n, counted;
285
	struct commit_list *p;
286

287
	counted = 0;
288

289
	for (n = 0, p = list; p; p = p->next) {
290
		struct commit *commit = p->item;
291
		unsigned commit_flags = commit->object.flags;
292

293
		*commit_weight_at(&commit_weight, p->item) = &weights[n++];
294
		switch (count_interesting_parents(commit, bisect_flags)) {
295
		case 0:
296
			if (!(commit_flags & TREESAME)) {
297
				weight_set(p, 1);
298
				counted++;
299
				show_list("bisection 2 count one",
300
					  counted, nr, list);
301
			}
302
			/*
303
			 * otherwise, it is known not to reach any
304
			 * tree-changing commit and gets weight 0.
305
			 */
306
			break;
307
		case 1:
308
			weight_set(p, -1);
309
			break;
310
		default:
311
			weight_set(p, -2);
312
			break;
313
		}
314
	}
315

316
	show_list("bisection 2 initialize", counted, nr, list);
317

318
	/*
319
	 * If you have only one parent in the resulting set
320
	 * then you can reach one commit more than that parent
321
	 * can reach.  So we do not have to run the expensive
322
	 * count_distance() for single strand of pearls.
323
	 *
324
	 * However, if you have more than one parents, you cannot
325
	 * just add their distance and one for yourself, since
326
	 * they usually reach the same ancestor and you would
327
	 * end up counting them twice that way.
328
	 *
329
	 * So we will first count distance of merges the usual
330
	 * way, and then fill the blanks using cheaper algorithm.
331
	 */
332
	for (p = list; p; p = p->next) {
333
		if (p->item->object.flags & UNINTERESTING)
334
			continue;
335
		if (weight(p) != -2)
336
			continue;
337
		if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)
338
			BUG("shouldn't be calling count-distance in fp mode");
339
		weight_set(p, count_distance(p));
340
		clear_distance(list);
341

342
		/* Does it happen to be at half-way? */
343
		if (!(bisect_flags & FIND_BISECTION_ALL) &&
344
		      approx_halfway(p, nr))
345
			return p;
346
		counted++;
347
	}
348

349
	show_list("bisection 2 count_distance", counted, nr, list);
350

351
	while (counted < nr) {
352
		for (p = list; p; p = p->next) {
353
			struct commit_list *q;
354
			unsigned commit_flags = p->item->object.flags;
355

356
			if (0 <= weight(p))
357
				continue;
358

359
			for (q = p->item->parents;
360
			     q;
361
			     q = bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY ? NULL : q->next) {
362
				if (q->item->object.flags & UNINTERESTING)
363
					continue;
364
				if (0 <= weight(q))
365
					break;
366
			}
367
			if (!q)
368
				continue;
369

370
			/*
371
			 * weight for p is unknown but q is known.
372
			 * add one for p itself if p is to be counted,
373
			 * otherwise inherit it from q directly.
374
			 */
375
			if (!(commit_flags & TREESAME)) {
376
				weight_set(p, weight(q)+1);
377
				counted++;
378
				show_list("bisection 2 count one",
379
					  counted, nr, list);
380
			}
381
			else
382
				weight_set(p, weight(q));
383

384
			/* Does it happen to be at half-way? */
385
			if (!(bisect_flags & FIND_BISECTION_ALL) &&
386
			      approx_halfway(p, nr))
387
				return p;
388
		}
389
	}
390

391
	show_list("bisection 2 counted all", counted, nr, list);
392

393
	if (!(bisect_flags & FIND_BISECTION_ALL))
394
		return best_bisection(list, nr);
395
	else
396
		return best_bisection_sorted(list, nr);
397
}
398

399
void find_bisection(struct commit_list **commit_list, int *reaches,
400
		    int *all, unsigned bisect_flags)
401
{
402
	int nr, on_list;
403
	struct commit_list *list, *p, *best, *next, *last;
404
	int *weights;
405

406
	show_list("bisection 2 entry", 0, 0, *commit_list);
407
	init_commit_weight(&commit_weight);
408

409
	/*
410
	 * Count the number of total and tree-changing items on the
411
	 * list, while reversing the list.
412
	 */
413
	for (nr = on_list = 0, last = NULL, p = *commit_list;
414
	     p;
415
	     p = next) {
416
		unsigned commit_flags = p->item->object.flags;
417

418
		next = p->next;
419
		if (commit_flags & UNINTERESTING) {
420
			free(p);
421
			continue;
422
		}
423
		p->next = last;
424
		last = p;
425
		if (!(commit_flags & TREESAME))
426
			nr++;
427
		on_list++;
428
	}
429
	list = last;
430
	show_list("bisection 2 sorted", 0, nr, list);
431

432
	*all = nr;
433
	CALLOC_ARRAY(weights, on_list);
434

435
	/* Do the real work of finding bisection commit. */
436
	best = do_find_bisection(list, nr, weights, bisect_flags);
437
	if (best) {
438
		if (!(bisect_flags & FIND_BISECTION_ALL)) {
439
			list->item = best->item;
440
			free_commit_list(list->next);
441
			best = list;
442
			best->next = NULL;
443
		}
444
		*reaches = weight(best);
445
	}
446
	free(weights);
447
	*commit_list = best;
448
	clear_commit_weight(&commit_weight);
449
}
450

451
static int register_ref(const char *refname, const char *referent UNUSED, const struct object_id *oid,
452
			int flags UNUSED, void *cb_data UNUSED)
453
{
454
	struct strbuf good_prefix = STRBUF_INIT;
455
	strbuf_addstr(&good_prefix, term_good);
456
	strbuf_addstr(&good_prefix, "-");
457

458
	if (!strcmp(refname, term_bad)) {
459
		current_bad_oid = xmalloc(sizeof(*current_bad_oid));
460
		oidcpy(current_bad_oid, oid);
461
	} else if (starts_with(refname, good_prefix.buf)) {
462
		oid_array_append(&good_revs, oid);
463
	} else if (starts_with(refname, "skip-")) {
464
		oid_array_append(&skipped_revs, oid);
465
	}
466

467
	strbuf_release(&good_prefix);
468

469
	return 0;
470
}
471

472
static int read_bisect_refs(void)
473
{
474
	return refs_for_each_ref_in(get_main_ref_store(the_repository),
475
				    "refs/bisect/", register_ref, NULL);
476
}
477

478
static GIT_PATH_FUNC(git_path_bisect_names, "BISECT_NAMES")
479
static GIT_PATH_FUNC(git_path_bisect_ancestors_ok, "BISECT_ANCESTORS_OK")
480
static GIT_PATH_FUNC(git_path_bisect_run, "BISECT_RUN")
481
static GIT_PATH_FUNC(git_path_bisect_start, "BISECT_START")
482
static GIT_PATH_FUNC(git_path_bisect_log, "BISECT_LOG")
483
static GIT_PATH_FUNC(git_path_bisect_terms, "BISECT_TERMS")
484
static GIT_PATH_FUNC(git_path_bisect_first_parent, "BISECT_FIRST_PARENT")
485

486
static void read_bisect_paths(struct strvec *array)
487
{
488
	struct strbuf str = STRBUF_INIT;
489
	const char *filename = git_path_bisect_names();
490
	FILE *fp = xfopen(filename, "r");
491

492
	while (strbuf_getline_lf(&str, fp) != EOF) {
493
		strbuf_trim(&str);
494
		if (sq_dequote_to_strvec(str.buf, array))
495
			die(_("Badly quoted content in file '%s': %s"),
496
			    filename, str.buf);
497
	}
498

499
	strbuf_release(&str);
500
	fclose(fp);
501
}
502

503
static char *join_oid_array_hex(struct oid_array *array, char delim)
504
{
505
	struct strbuf joined_hexs = STRBUF_INIT;
506
	int i;
507

508
	for (i = 0; i < array->nr; i++) {
509
		strbuf_addstr(&joined_hexs, oid_to_hex(array->oid + i));
510
		if (i + 1 < array->nr)
511
			strbuf_addch(&joined_hexs, delim);
512
	}
513

514
	return strbuf_detach(&joined_hexs, NULL);
515
}
516

517
/*
518
 * In this function, passing a not NULL skipped_first is very special.
519
 * It means that we want to know if the first commit in the list is
520
 * skipped because we will want to test a commit away from it if it is
521
 * indeed skipped.
522
 * So if the first commit is skipped, we cannot take the shortcut to
523
 * just "return list" when we find the first non skipped commit, we
524
 * have to return a fully filtered list.
525
 *
526
 * We use (*skipped_first == -1) to mean "it has been found that the
527
 * first commit is not skipped". In this case *skipped_first is set back
528
 * to 0 just before the function returns.
529
 */
530
struct commit_list *filter_skipped(struct commit_list *list,
531
				   struct commit_list **tried,
532
				   int show_all,
533
				   int *count,
534
				   int *skipped_first)
535
{
536
	struct commit_list *filtered = NULL, **f = &filtered;
537

538
	*tried = NULL;
539

540
	if (skipped_first)
541
		*skipped_first = 0;
542
	if (count)
543
		*count = 0;
544

545
	if (!skipped_revs.nr)
546
		return list;
547

548
	while (list) {
549
		struct commit_list *next = list->next;
550
		list->next = NULL;
551
		if (0 <= oid_array_lookup(&skipped_revs, &list->item->object.oid)) {
552
			if (skipped_first && !*skipped_first)
553
				*skipped_first = 1;
554
			/* Move current to tried list */
555
			*tried = list;
556
			tried = &list->next;
557
		} else {
558
			if (!show_all) {
559
				if (!skipped_first || !*skipped_first)
560
					return list;
561
			} else if (skipped_first && !*skipped_first) {
562
				/* This means we know it's not skipped */
563
				*skipped_first = -1;
564
			}
565
			/* Move current to filtered list */
566
			*f = list;
567
			f = &list->next;
568
			if (count)
569
				(*count)++;
570
		}
571
		list = next;
572
	}
573

574
	if (skipped_first && *skipped_first == -1)
575
		*skipped_first = 0;
576

577
	return filtered;
578
}
579

580
#define PRN_MODULO 32768
581

582
/*
583
 * This is a pseudo random number generator based on "man 3 rand".
584
 * It is not used properly because the seed is the argument and it
585
 * is increased by one between each call, but that should not matter
586
 * for this application.
587
 */
588
static unsigned get_prn(unsigned count)
589
{
590
	count = count * 1103515245 + 12345;
591
	return (count/65536) % PRN_MODULO;
592
}
593

594
/*
595
 * Custom integer square root from
596
 * https://en.wikipedia.org/wiki/Integer_square_root
597
 */
598
static int sqrti(int val)
599
{
600
	float d, x = val;
601

602
	if (!val)
603
		return 0;
604

605
	do {
606
		float y = (x + (float)val / x) / 2;
607
		d = (y > x) ? y - x : x - y;
608
		x = y;
609
	} while (d >= 0.5);
610

611
	return (int)x;
612
}
613

614
static struct commit_list *skip_away(struct commit_list *list, int count)
615
{
616
	struct commit_list *cur, *previous;
617
	int prn, index, i;
618

619
	prn = get_prn(count);
620
	index = (count * prn / PRN_MODULO) * sqrti(prn) / sqrti(PRN_MODULO);
621

622
	cur = list;
623
	previous = NULL;
624

625
	for (i = 0; cur; cur = cur->next, i++) {
626
		if (i == index) {
627
			if (!oideq(&cur->item->object.oid, current_bad_oid))
628
				return cur;
629
			if (previous)
630
				return previous;
631
			return list;
632
		}
633
		previous = cur;
634
	}
635

636
	return list;
637
}
638

639
static struct commit_list *managed_skipped(struct commit_list *list,
640
					   struct commit_list **tried)
641
{
642
	int count, skipped_first;
643

644
	*tried = NULL;
645

646
	if (!skipped_revs.nr)
647
		return list;
648

649
	list = filter_skipped(list, tried, 0, &count, &skipped_first);
650

651
	if (!skipped_first)
652
		return list;
653

654
	return skip_away(list, count);
655
}
656

657
static void bisect_rev_setup(struct repository *r, struct rev_info *revs,
658
			     struct strvec *rev_argv,
659
			     const char *prefix,
660
			     const char *bad_format, const char *good_format,
661
			     int read_paths)
662
{
663
	struct setup_revision_opt opt = {
664
		.free_removed_argv_elements = 1,
665
	};
666
	int i;
667

668
	repo_init_revisions(r, revs, prefix);
669
	revs->abbrev = 0;
670
	revs->commit_format = CMIT_FMT_UNSPECIFIED;
671

672
	/* rev_argv.argv[0] will be ignored by setup_revisions */
673
	strvec_push(rev_argv, "bisect_rev_setup");
674
	strvec_pushf(rev_argv, bad_format, oid_to_hex(current_bad_oid));
675
	for (i = 0; i < good_revs.nr; i++)
676
		strvec_pushf(rev_argv, good_format,
677
			     oid_to_hex(good_revs.oid + i));
678
	strvec_push(rev_argv, "--");
679
	if (read_paths)
680
		read_bisect_paths(rev_argv);
681

682
	setup_revisions(rev_argv->nr, rev_argv->v, revs, &opt);
683
}
684

685
static void bisect_common(struct rev_info *revs)
686
{
687
	if (prepare_revision_walk(revs))
688
		die("revision walk setup failed");
689
	if (revs->tree_objects)
690
		mark_edges_uninteresting(revs, NULL, 0);
691
}
692

693
static enum bisect_error error_if_skipped_commits(struct commit_list *tried,
694
				    const struct object_id *bad)
695
{
696
	if (!tried)
697
		return BISECT_OK;
698

699
	printf("There are only 'skip'ped commits left to test.\n"
700
	       "The first %s commit could be any of:\n", term_bad);
701

702
	for ( ; tried; tried = tried->next)
703
		printf("%s\n", oid_to_hex(&tried->item->object.oid));
704

705
	if (bad)
706
		printf("%s\n", oid_to_hex(bad));
707
	printf(_("We cannot bisect more!\n"));
708

709
	return BISECT_ONLY_SKIPPED_LEFT;
710
}
711

712
static int is_expected_rev(const struct object_id *oid)
713
{
714
	struct object_id expected_oid;
715
	if (refs_read_ref(get_main_ref_store(the_repository), "BISECT_EXPECTED_REV", &expected_oid))
716
		return 0;
717
	return oideq(oid, &expected_oid);
718
}
719

720
enum bisect_error bisect_checkout(const struct object_id *bisect_rev,
721
				  int no_checkout)
722
{
723
	struct commit *commit;
724
	struct pretty_print_context pp = {0};
725
	struct strbuf commit_msg = STRBUF_INIT;
726

727
	refs_update_ref(get_main_ref_store(the_repository), NULL,
728
			"BISECT_EXPECTED_REV", bisect_rev, NULL, 0,
729
			UPDATE_REFS_DIE_ON_ERR);
730

731
	if (no_checkout) {
732
		refs_update_ref(get_main_ref_store(the_repository), NULL,
733
				"BISECT_HEAD", bisect_rev, NULL, 0,
734
				UPDATE_REFS_DIE_ON_ERR);
735
	} else {
736
		struct child_process cmd = CHILD_PROCESS_INIT;
737

738
		cmd.git_cmd = 1;
739
		strvec_pushl(&cmd.args, "checkout", "-q",
740
			     oid_to_hex(bisect_rev), "--", NULL);
741
		if (run_command(&cmd))
742
			/*
743
			 * Errors in `run_command()` itself, signaled by res < 0,
744
			 * and errors in the child process, signaled by res > 0
745
			 * can both be treated as regular BISECT_FAILED (-1).
746
			 */
747
			return BISECT_FAILED;
748
	}
749

750
	commit = lookup_commit_reference(the_repository, bisect_rev);
751
	repo_format_commit_message(the_repository, commit, "[%H] %s%n",
752
				   &commit_msg, &pp);
753
	fputs(commit_msg.buf, stdout);
754
	strbuf_release(&commit_msg);
755

756
	return BISECT_OK;
757
}
758

759
static struct commit *get_commit_reference(struct repository *r,
760
					   const struct object_id *oid)
761
{
762
	struct commit *c = lookup_commit_reference(r, oid);
763
	if (!c)
764
		die(_("Not a valid commit name %s"), oid_to_hex(oid));
765
	return c;
766
}
767

768
static struct commit **get_bad_and_good_commits(struct repository *r,
769
						int *rev_nr)
770
{
771
	struct commit **rev;
772
	int i, n = 0;
773

774
	ALLOC_ARRAY(rev, 1 + good_revs.nr);
775
	rev[n++] = get_commit_reference(r, current_bad_oid);
776
	for (i = 0; i < good_revs.nr; i++)
777
		rev[n++] = get_commit_reference(r, good_revs.oid + i);
778
	*rev_nr = n;
779

780
	return rev;
781
}
782

783
static enum bisect_error handle_bad_merge_base(void)
784
{
785
	if (is_expected_rev(current_bad_oid)) {
786
		char *bad_hex = oid_to_hex(current_bad_oid);
787
		char *good_hex = join_oid_array_hex(&good_revs, ' ');
788
		if (!strcmp(term_bad, "bad") && !strcmp(term_good, "good")) {
789
			fprintf(stderr, _("The merge base %s is bad.\n"
790
				"This means the bug has been fixed "
791
				"between %s and [%s].\n"),
792
				bad_hex, bad_hex, good_hex);
793
		} else if (!strcmp(term_bad, "new") && !strcmp(term_good, "old")) {
794
			fprintf(stderr, _("The merge base %s is new.\n"
795
				"The property has changed "
796
				"between %s and [%s].\n"),
797
				bad_hex, bad_hex, good_hex);
798
		} else {
799
			fprintf(stderr, _("The merge base %s is %s.\n"
800
				"This means the first '%s' commit is "
801
				"between %s and [%s].\n"),
802
				bad_hex, term_bad, term_good, bad_hex, good_hex);
803
		}
804
		return BISECT_MERGE_BASE_CHECK;
805
	}
806

807
	fprintf(stderr, _("Some %s revs are not ancestors of the %s rev.\n"
808
		"git bisect cannot work properly in this case.\n"
809
		"Maybe you mistook %s and %s revs?\n"),
810
		term_good, term_bad, term_good, term_bad);
811
	return BISECT_FAILED;
812
}
813

814
static void handle_skipped_merge_base(const struct object_id *mb)
815
{
816
	char *mb_hex = oid_to_hex(mb);
817
	char *bad_hex = oid_to_hex(current_bad_oid);
818
	char *good_hex = join_oid_array_hex(&good_revs, ' ');
819

820
	warning(_("the merge base between %s and [%s] "
821
		"must be skipped.\n"
822
		"So we cannot be sure the first %s commit is "
823
		"between %s and %s.\n"
824
		"We continue anyway."),
825
		bad_hex, good_hex, term_bad, mb_hex, bad_hex);
826
	free(good_hex);
827
}
828

829
/*
830
 * "check_merge_bases" checks that merge bases are not "bad" (or "new").
831
 *
832
 * - If one is "bad" (or "new"), it means the user assumed something wrong
833
 * and we must return error with a non 0 error code.
834
 * - If one is "good" (or "old"), that's good, we have nothing to do.
835
 * - If one is "skipped", we can't know but we should warn.
836
 * - If we don't know, we should check it out and ask the user to test.
837
 * - If a merge base must be tested, on success return
838
 * BISECT_INTERNAL_SUCCESS_MERGE_BASE (-11) a special condition
839
 * for early success, this will be converted back to 0 in
840
 * check_good_are_ancestors_of_bad().
841
 */
842
static enum bisect_error check_merge_bases(int rev_nr, struct commit **rev, int no_checkout)
843
{
844
	enum bisect_error res = BISECT_OK;
845
	struct commit_list *result = NULL;
846

847
	if (repo_get_merge_bases_many(the_repository, rev[0], rev_nr - 1,
848
				      rev + 1, &result) < 0)
849
		exit(128);
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 strvec rev_argv = STRVEC_INIT;
878
	struct rev_info revs;
879
	int res;
880

881
	bisect_rev_setup(r, &revs, &rev_argv, prefix, "^%s", "%s", 0);
882

883
	bisect_common(&revs);
884
	res = (revs.commits != NULL);
885

886
	/* Clean up objects used, as they will be reused. */
887
	clear_commit_marks_many(rev_nr, rev, ALL_REV_FLAGS);
888

889
	release_revisions(&revs);
890
	strvec_clear(&rev_argv);
891
	return res;
892
}
893

894
/*
895
 * "check_good_are_ancestors_of_bad" checks that all "good" revs are
896
 * ancestor of the "bad" rev.
897
 *
898
 * If that's not the case, we need to check the merge bases.
899
 * If a merge base must be tested by the user, its source code will be
900
 * checked out to be tested by the user and we will return.
901
 */
902

903
static enum bisect_error check_good_are_ancestors_of_bad(struct repository *r,
904
					    const char *prefix,
905
					    int no_checkout)
906
{
907
	char *filename;
908
	struct stat st;
909
	int fd, rev_nr;
910
	enum bisect_error res = BISECT_OK;
911
	struct commit **rev;
912

913
	if (!current_bad_oid)
914
		return error(_("a %s revision is needed"), term_bad);
915

916
	filename = git_pathdup("BISECT_ANCESTORS_OK");
917

918
	/* Check if file BISECT_ANCESTORS_OK exists. */
919
	if (!stat(filename, &st) && S_ISREG(st.st_mode))
920
		goto done;
921

922
	/* Bisecting with no good rev is ok. */
923
	if (!good_revs.nr)
924
		goto done;
925

926
	/* Check if all good revs are ancestor of the bad rev. */
927

928
	rev = get_bad_and_good_commits(r, &rev_nr);
929
	if (check_ancestors(r, rev_nr, rev, prefix))
930
		res = check_merge_bases(rev_nr, rev, no_checkout);
931
	free(rev);
932

933
	if (!res) {
934
		/* Create file BISECT_ANCESTORS_OK. */
935
		fd = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0600);
936
		if (fd < 0)
937
			/*
938
			 * BISECT_ANCESTORS_OK file is not absolutely necessary,
939
			 * the bisection process will continue at the next
940
			 * bisection step.
941
			 * So, just signal with a warning that something
942
			 * might be wrong.
943
			 */
944
			warning_errno(_("could not create file '%s'"),
945
				filename);
946
		else
947
			close(fd);
948
	}
949
 done:
950
	free(filename);
951
	return res;
952
}
953

954
/*
955
 * Display a commit summary to the user.
956
 */
957
static void show_commit(struct commit *commit)
958
{
959
	struct child_process show = CHILD_PROCESS_INIT;
960

961
	/*
962
	 * Call git show with --no-pager, as it would otherwise
963
	 * paginate the "git show" output only, not the output
964
	 * from bisect_next_all(); this can be fixed by moving
965
	 * it into a --format parameter, but that would override
966
	 * the user's default options for "git show", which we
967
	 * are trying to honour.
968
	 */
969
	strvec_pushl(&show.args,
970
		     "--no-pager",
971
		     "show",
972
		     "--stat",
973
		     "--summary",
974
		     "--no-abbrev-commit",
975
		     "--diff-merges=first-parent",
976
		     oid_to_hex(&commit->object.oid), NULL);
977
	show.git_cmd = 1;
978
	if (run_command(&show))
979
		die(_("unable to start 'show' for object '%s'"),
980
		    oid_to_hex(&commit->object.oid));
981
}
982

983
/*
984
 * The terms used for this bisect session are stored in BISECT_TERMS.
985
 * We read them and store them to adapt the messages accordingly.
986
 * Default is bad/good.
987
 */
988
void read_bisect_terms(const char **read_bad, const char **read_good)
989
{
990
	struct strbuf str = STRBUF_INIT;
991
	const char *filename = git_path_bisect_terms();
992
	FILE *fp = fopen(filename, "r");
993

994
	if (!fp) {
995
		if (errno == ENOENT) {
996
			*read_bad = "bad";
997
			*read_good = "good";
998
			return;
999
		} else {
1000
			die_errno(_("could not read file '%s'"), filename);
1001
		}
1002
	} else {
1003
		strbuf_getline_lf(&str, fp);
1004
		*read_bad = strbuf_detach(&str, NULL);
1005
		strbuf_getline_lf(&str, fp);
1006
		*read_good = strbuf_detach(&str, NULL);
1007
	}
1008
	strbuf_release(&str);
1009
	fclose(fp);
1010
}
1011

1012
/*
1013
 * We use the convention that return BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND (-10) means
1014
 * the bisection process finished successfully.
1015
 * In this case the calling function or command should not turn a
1016
 * BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND return code into an error or a non zero exit code.
1017
 *
1018
 * Checking BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND
1019
 * in bisect_helper::bisect_next() and only transforming it to 0 at
1020
 * the end of bisect_helper::cmd_bisect__helper() helps bypassing
1021
 * all the code related to finding a commit to test.
1022
 */
1023
enum bisect_error bisect_next_all(struct repository *r, const char *prefix)
1024
{
1025
	struct strvec rev_argv = STRVEC_INIT;
1026
	struct rev_info revs = REV_INFO_INIT;
1027
	struct commit_list *tried;
1028
	int reaches = 0, all = 0, nr, steps;
1029
	enum bisect_error res = BISECT_OK;
1030
	struct object_id *bisect_rev;
1031
	char *steps_msg;
1032
	/*
1033
	 * If no_checkout is non-zero, the bisection process does not
1034
	 * checkout the trial commit but instead simply updates BISECT_HEAD.
1035
	 */
1036
	int no_checkout = refs_ref_exists(get_main_ref_store(the_repository),
1037
					  "BISECT_HEAD");
1038
	unsigned bisect_flags = 0;
1039

1040
	read_bisect_terms(&term_bad, &term_good);
1041
	if (read_bisect_refs())
1042
		die(_("reading bisect refs failed"));
1043

1044
	if (file_exists(git_path_bisect_first_parent()))
1045
		bisect_flags |= FIND_BISECTION_FIRST_PARENT_ONLY;
1046

1047
	if (skipped_revs.nr)
1048
		bisect_flags |= FIND_BISECTION_ALL;
1049

1050
	res = check_good_are_ancestors_of_bad(r, prefix, no_checkout);
1051
	if (res)
1052
		goto cleanup;
1053

1054
	bisect_rev_setup(r, &revs, &rev_argv, prefix, "%s", "^%s", 1);
1055

1056
	revs.first_parent_only = !!(bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY);
1057
	revs.limited = 1;
1058

1059
	bisect_common(&revs);
1060

1061
	find_bisection(&revs.commits, &reaches, &all, bisect_flags);
1062
	revs.commits = managed_skipped(revs.commits, &tried);
1063

1064
	if (!revs.commits) {
1065
		/*
1066
		 * We should return error here only if the "bad"
1067
		 * commit is also a "skip" commit.
1068
		 */
1069
		res = error_if_skipped_commits(tried, NULL);
1070
		if (res < 0)
1071
			goto cleanup;
1072
		printf(_("%s was both %s and %s\n"),
1073
		       oid_to_hex(current_bad_oid),
1074
		       term_good,
1075
		       term_bad);
1076

1077
		res = BISECT_FAILED;
1078
		goto cleanup;
1079
	}
1080

1081
	if (!all) {
1082
		fprintf(stderr, _("No testable commit found.\n"
1083
			"Maybe you started with bad path arguments?\n"));
1084

1085
		res = BISECT_NO_TESTABLE_COMMIT;
1086
		goto cleanup;
1087
	}
1088

1089
	bisect_rev = &revs.commits->item->object.oid;
1090

1091
	if (oideq(bisect_rev, current_bad_oid)) {
1092
		res = error_if_skipped_commits(tried, current_bad_oid);
1093
		if (res)
1094
			return res;
1095
		printf("%s is the first %s commit\n", oid_to_hex(bisect_rev),
1096
			term_bad);
1097

1098
		show_commit(revs.commits->item);
1099
		/*
1100
		 * This means the bisection process succeeded.
1101
		 * Using BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND (-10)
1102
		 * so that the call chain can simply check
1103
		 * for negative return values for early returns up
1104
		 * until the cmd_bisect__helper() caller.
1105
		 */
1106
		res = BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND;
1107
		goto cleanup;
1108
	}
1109

1110
	nr = all - reaches - 1;
1111
	steps = estimate_bisect_steps(all);
1112

1113
	steps_msg = xstrfmt(Q_("(roughly %d step)", "(roughly %d steps)",
1114
		  steps), steps);
1115
	/*
1116
	 * TRANSLATORS: the last %s will be replaced with "(roughly %d
1117
	 * steps)" translation.
1118
	 */
1119
	printf(Q_("Bisecting: %d revision left to test after this %s\n",
1120
		  "Bisecting: %d revisions left to test after this %s\n",
1121
		  nr), nr, steps_msg);
1122
	free(steps_msg);
1123
	/* Clean up objects used, as they will be reused. */
1124
	repo_clear_commit_marks(r, ALL_REV_FLAGS);
1125

1126
	res = bisect_checkout(bisect_rev, no_checkout);
1127
cleanup:
1128
	release_revisions(&revs);
1129
	strvec_clear(&rev_argv);
1130
	return res;
1131
}
1132

1133
static inline int log2i(int n)
1134
{
1135
	int log2 = 0;
1136

1137
	for (; n > 1; n >>= 1)
1138
		log2++;
1139

1140
	return log2;
1141
}
1142

1143
static inline int exp2i(int n)
1144
{
1145
	return 1 << n;
1146
}
1147

1148
/*
1149
 * Estimate the number of bisect steps left (after the current step)
1150
 *
1151
 * For any x between 0 included and 2^n excluded, the probability for
1152
 * n - 1 steps left looks like:
1153
 *
1154
 * P(2^n + x) == (2^n - x) / (2^n + x)
1155
 *
1156
 * and P(2^n + x) < 0.5 means 2^n < 3x
1157
 */
1158
int estimate_bisect_steps(int all)
1159
{
1160
	int n, x, e;
1161

1162
	if (all < 3)
1163
		return 0;
1164

1165
	n = log2i(all);
1166
	e = exp2i(n);
1167
	x = all - e;
1168

1169
	return (e < 3 * x) ? n : n - 1;
1170
}
1171

1172
static int mark_for_removal(const char *refname,
1173
			    const char *referent UNUSED,
1174
			    const struct object_id *oid UNUSED,
1175
			    int flag UNUSED, void *cb_data)
1176
{
1177
	struct string_list *refs = cb_data;
1178
	char *ref = xstrfmt("refs/bisect%s", refname);
1179
	string_list_append(refs, ref);
1180
	return 0;
1181
}
1182

1183
int bisect_clean_state(void)
1184
{
1185
	int result = 0;
1186

1187
	/* There may be some refs packed during bisection */
1188
	struct string_list refs_for_removal = STRING_LIST_INIT_NODUP;
1189
	refs_for_each_ref_in(get_main_ref_store(the_repository),
1190
			     "refs/bisect", mark_for_removal,
1191
			     (void *) &refs_for_removal);
1192
	string_list_append(&refs_for_removal, xstrdup("BISECT_HEAD"));
1193
	string_list_append(&refs_for_removal, xstrdup("BISECT_EXPECTED_REV"));
1194
	result = refs_delete_refs(get_main_ref_store(the_repository),
1195
				  "bisect: remove", &refs_for_removal,
1196
				  REF_NO_DEREF);
1197
	refs_for_removal.strdup_strings = 1;
1198
	string_list_clear(&refs_for_removal, 0);
1199
	unlink_or_warn(git_path_bisect_ancestors_ok());
1200
	unlink_or_warn(git_path_bisect_log());
1201
	unlink_or_warn(git_path_bisect_names());
1202
	unlink_or_warn(git_path_bisect_run());
1203
	unlink_or_warn(git_path_bisect_terms());
1204
	unlink_or_warn(git_path_bisect_first_parent());
1205
	/*
1206
	 * Cleanup BISECT_START last to support the --no-checkout option
1207
	 * introduced in the commit 4796e823a.
1208
	 */
1209
	unlink_or_warn(git_path_bisect_start());
1210

1211
	return result;
1212
}
1213