git/bisect.c

#define USE_THE_REPOSITORY_VARIABLE

#include "git-compat-util.h"
#include "config.h"
#include "commit.h"
#include "diff.h"
#include "environment.h"
#include "gettext.h"
#include "hex.h"
#include "revision.h"
#include "refs.h"
#include "list-objects.h"
#include "quote.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-name.h"
#include "object-store-ll.h"
#include "path.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 *term_bad;
static const char *term_good;

/* Remember to update object flag allocation in object.h */
#define COUNTED …

/*
 * 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)
{ … }

static void clear_distance(struct commit_list *list)
{ … }

define_commit_slab(commit_weight, int *);
static struct commit_weight commit_weight;

#define DEBUG_BISECT …

static inline int weight(struct commit_list *elem)
{ … }

static inline void weight_set(struct commit_list *elem, int weight)
{ … }

static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)
{ … }

static inline int approx_halfway(struct commit_list *p, int nr)
{ … }

static void show_list(const char *debug, int counted, int nr,
		      struct commit_list *list)
{ … }

static struct commit_list *best_bisection(struct commit_list *list, int nr)
{ … }

struct commit_dist { … };

static int compare_commit_dist(const void *a_, const void *b_)
{ … }

static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
{ … }

/*
 * zero or positive weight is the number of interesting commits it can
 * reach, including itself.  Especially, weight = 0 means it does not
 * reach any tree-changing commits (e.g. just above uninteresting one
 * but traversal is with pathspec).
 *
 * weight = -1 means it has one parent and its distance is yet to
 * be computed.
 *
 * weight = -2 means it has more than one parent and its distance is
 * unknown.  After running count_distance() first, they will get zero
 * or positive distance.
 */
static struct commit_list *do_find_bisection(struct commit_list *list,
					     int nr, int *weights,
					     unsigned bisect_flags)
{ … }

void find_bisection(struct commit_list **commit_list, int *reaches,
		    int *all, unsigned bisect_flags)
{ … }

static int register_ref(const char *refname, const char *referent UNUSED, const struct object_id *oid,
			int flags UNUSED, void *cb_data UNUSED)
{ … }

static int read_bisect_refs(void)
{ … }

static GIT_PATH_FUNC(git_path_bisect_names, "BISECT_NAMES")
static GIT_PATH_FUNC(git_path_bisect_ancestors_ok, "BISECT_ANCESTORS_OK")
static GIT_PATH_FUNC(git_path_bisect_run, "BISECT_RUN")
static GIT_PATH_FUNC(git_path_bisect_start, "BISECT_START")
static GIT_PATH_FUNC(git_path_bisect_log, "BISECT_LOG")
static GIT_PATH_FUNC(git_path_bisect_terms, "BISECT_TERMS")
static GIT_PATH_FUNC(git_path_bisect_first_parent, "BISECT_FIRST_PARENT")

static void read_bisect_paths(struct strvec *array)
{ … }

static char *join_oid_array_hex(struct oid_array *array, char delim)
{ … }

/*
 * In this function, passing a not NULL skipped_first is very special.
 * It means that we want to know if the first commit in the list is
 * skipped because we will want to test a commit away from it if it is
 * indeed skipped.
 * So if the first commit is skipped, we cannot take the shortcut to
 * just "return list" when we find the first non skipped commit, we
 * have to return a fully filtered list.
 *
 * We use (*skipped_first == -1) to mean "it has been found that the
 * first commit is not skipped". In this case *skipped_first is set back
 * to 0 just before the function returns.
 */
struct commit_list *filter_skipped(struct commit_list *list,
				   struct commit_list **tried,
				   int show_all,
				   int *count,
				   int *skipped_first)
{ … }

#define PRN_MODULO …

/*
 * This is a pseudo random number generator based on "man 3 rand".
 * It is not used properly because the seed is the argument and it
 * is increased by one between each call, but that should not matter
 * for this application.
 */
static unsigned get_prn(unsigned count)
{ … }

/*
 * Custom integer square root from
 * https://en.wikipedia.org/wiki/Integer_square_root
 */
static int sqrti(int val)
{ … }

static struct commit_list *skip_away(struct commit_list *list, int count)
{ … }

static struct commit_list *managed_skipped(struct commit_list *list,
					   struct commit_list **tried)
{ … }

static void bisect_rev_setup(struct repository *r, struct rev_info *revs,
			     struct strvec *rev_argv,
			     const char *prefix,
			     const char *bad_format, const char *good_format,
			     int read_paths)
{ … }

static void bisect_common(struct rev_info *revs)
{ … }

static enum bisect_error error_if_skipped_commits(struct commit_list *tried,
				    const struct object_id *bad)
{ … }

static int is_expected_rev(const struct object_id *oid)
{ … }

enum bisect_error bisect_checkout(const struct object_id *bisect_rev,
				  int no_checkout)
{ … }

static struct commit *get_commit_reference(struct repository *r,
					   const struct object_id *oid)
{ … }

static struct commit **get_bad_and_good_commits(struct repository *r,
						int *rev_nr)
{ … }

static enum bisect_error handle_bad_merge_base(void)
{ … }

static void handle_skipped_merge_base(const struct object_id *mb)
{ … }

/*
 * "check_merge_bases" checks that merge bases are not "bad" (or "new").
 *
 * - If one is "bad" (or "new"), it means the user assumed something wrong
 * and we must return error with a non 0 error code.
 * - If one is "good" (or "old"), that's good, we have nothing to do.
 * - If one is "skipped", we can't know but we should warn.
 * - If we don't know, we should check it out and ask the user to test.
 * - If a merge base must be tested, on success return
 * BISECT_INTERNAL_SUCCESS_MERGE_BASE (-11) a special condition
 * for early success, this will be converted back to 0 in
 * check_good_are_ancestors_of_bad().
 */
static enum bisect_error check_merge_bases(int rev_nr, struct commit **rev, int no_checkout)
{ … }

static int check_ancestors(struct repository *r, int rev_nr,
			   struct commit **rev, const char *prefix)
{ … }

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

static enum bisect_error check_good_are_ancestors_of_bad(struct repository *r,
					    const char *prefix,
					    int no_checkout)
{ … }

/*
 * Display a commit summary to the user.
 */
static void show_commit(struct commit *commit)
{ … }

/*
 * The terms used for this bisect session are stored in BISECT_TERMS.
 * We read them and store them to adapt the messages accordingly.
 * Default is bad/good.
 */
void read_bisect_terms(const char **read_bad, const char **read_good)
{ … }

/*
 * We use the convention that return BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND (-10) means
 * the bisection process finished successfully.
 * In this case the calling function or command should not turn a
 * BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND return code into an error or a non zero exit code.
 *
 * Checking BISECT_INTERNAL_SUCCESS_1ST_BAD_FOUND
 * in bisect_helper::bisect_next() and only transforming it to 0 at
 * the end of bisect_helper::cmd_bisect__helper() helps bypassing
 * all the code related to finding a commit to test.
 */
enum bisect_error bisect_next_all(struct repository *r, const char *prefix)
{ … }

static inline int exp2i(int n)
{ … }

/*
 * Estimate the number of bisect steps left (after the current step)
 *
 * For any x between 0 included and 2^n excluded, the probability for
 * n - 1 steps left looks like:
 *
 * P(2^n + x) == (2^n - x) / (2^n + x)
 *
 * and P(2^n + x) < 0.5 means 2^n < 3x
 */
int estimate_bisect_steps(int all)
{ … }

static int mark_for_removal(const char *refname,
			    const char *referent UNUSED,
			    const struct object_id *oid UNUSED,
			    int flag UNUSED, void *cb_data)
{ … }

int bisect_clean_state(void)
{ … }