#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 approx_halfway(struct commit_list *p, int nr)
{
int diff;
/*
* Don't short-cut something we are not going to return!
*/
if (p->item->object.flags & TREESAME)
return 0;
if (DEBUG_BISECT)
return 0;
/*
* For small number of commits 2 and 3 are halfway of 5, and
* 3 is halfway of 6 but 2 and 4 are not.
*/
diff = 2 * weight(p) - nr;
switch (diff) {
case -1: case 0: case 1:
return 1;
default:
/*
* For large number of commits we are not so strict, it's
* good enough if it's within ~0.1% of the halfway point,
* e.g. 5000 is exactly halfway of 10000, but we consider
* the values [4996, 5004] as halfway as well.
*/
if (abs(diff) < nr / 1024)
return 1;
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,
|