#include "cache.h"
#include "config.h"
#include "commit.h"
#include "diff.h"
#include "revision.h"
#include "refs.h"
#include "list-objects.h"
#include "quote.h"
#include "sha1-lookup.h"
#include "run-command.h"
#include "log-tree.h"
#include "bisect.h"
#include "oid-array.h"
#include "strvec.h"
#include "commit-slab.h"
#include "commit-reach.h"
#include "object-store.h"
#include "dir.h"
static struct oid_array good_revs;
static struct oid_array skipped_revs;
static struct object_id *current_bad_oid;
static const char *argv_checkout[] = {"checkout", "-q", NULL, "--", NULL};
static const char *argv_show_branch[] = {"show-branch", NULL, NULL};
static const char *term_bad;
static const char *term_good;
/* Remember to update object flag allocation in object.h */
#define COUNTED (1u<<16)
/*
* This is a truly stupid algorithm, but it's only
* used for bisection, and we just don't care enough.
*
* We care just barely enough to avoid recursing for
* non-merge entries.
*/
static int count_distance(struct commit_list *entry)
{
int nr = 0;
while (entry) {
struct commit *commit = entry->item;
struct commit_list *p;
if (commit->object.flags & (UNINTERESTING | COUNTED))
break;
if (!(commit->object.flags & TREESAME))
nr++;
commit->object.flags |= COUNTED;
p = commit->parents;
entry = p;
if (p) {
p = p->next;
while (p) {
nr += count_distance(p);
p = p->next;
}
}
}
return nr;
}
static void clear_distance(struct commit_list *list)
{
while (list) {
struct commit *commit = list->item;
commit->object.flags &= ~COUNTED;
list = list->next;
}
}
define_commit_slab(commit_weight, int *);
static struct commit_weight commit_weight;
#define DEBUG_BISECT 0
static inline int weight(struct commit_list *elem)
{
return **commit_weight_at(&commit_weight, elem->item);
}
static inline void weight_set(struct commit_list *elem, int weight)
{
**commit_weight_at(&commit_weight, elem->item) = weight;
}
static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)
{
struct commit_list *p;
int count;
for (count = 0, p = commit->parents; p; p = p->next) {
if (!(p->item->object.flags & UNINTERESTING))
count++;
if (bisect_flags & FIND_BISECTION_FIRST_PARENT_ONLY)
break;
}
return count;
}
static inline int halfway(struct commit_list *p, int nr)
{
/*
* Don't short-cut something we are not going to return!
*/
if (p->item->object.flags & TREESAME)
return 0;
if (DEBUG_BISECT)
return 0;
/*
* 2 and 3 are halfway of 5.
* 3 is halfway of 6 but 2 and 4 are not.
*/
switch (2 * weight(p) - nr) {
case -1: case 0: case 1:
return 1;
default:
return 0;
}
}
static void show_list(const char *debug, int counted, int nr,
struct commit_list *list)
{
struct commit_list *p;
if (!DEBUG_BISECT)
return;
fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
for (p = list; p; p = p->next) {
struct commit_list *pp;
struct commit *commit = p->item;
unsigned commit_flags = commit->object.flags;
enum object_type type;
unsigned long size;
char *buf = read_object_file(&commit->object.oid, &type,
&size);
const char *subject_start;
int subject_len;
fprintf(stderr, "%c%c%c ",
(commit_flags & TREESAME) ? ' ' : 'T',
(commit_flags & UNINTERESTING) ? 'U' : ' ',
(commit_flags & COUNTED) ? 'C' : ' ');
if (*commit_weight_at(&commit_weight, p->item))
fprintf(stderr, "%3d", weight(p));
else
fprintf(stderr, "---");
fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
for (pp = commit->parents; pp; pp = pp->next)
fprintf(stderr, " %.*s", 8,
|