From: Junio C Hamano <gitster@pobox.com>
Date: Fri, 2 Nov 2018 02:04:55 +0000 (+0900)
Subject: Merge branch 'pk/rebase-in-c-4-opts'
X-Git-Tag: v2.20.0-rc0~91
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/0293121717ba66f089a38ce4d4d895db0f946e49?ds=inline;hp=--cc

Merge branch 'pk/rebase-in-c-4-opts'

Rewrite "git rebase" in C.

* pk/rebase-in-c-4-opts:
builtin rebase: support --root
builtin rebase: add support for custom merge strategies
builtin rebase: support `fork-point` option
merge-base --fork-point: extract libified function
builtin rebase: support --rebase-merges[=[no-]rebase-cousins]
builtin rebase: support `--allow-empty-message` option
builtin rebase: support `--exec`
builtin rebase: support `--autostash` option
builtin rebase: support `-C` and `--whitespace=<type>`
builtin rebase: support `--gpg-sign` option
builtin rebase: support `--autosquash`
builtin rebase: support `keep-empty` option
builtin rebase: support `ignore-date` option
builtin rebase: support `ignore-whitespace` option
builtin rebase: support --committer-date-is-author-date
builtin rebase: support --rerere-autoupdate
builtin rebase: support --signoff
builtin rebase: allow selecting the rebase "backend"
---

0293121717ba66f089a38ce4d4d895db0f946e49
diff --cc commit.c
index dc8a39d52a,a3fc77a4eb..d566d7e45c
--- a/commit.c
+++ b/commit.c
@@@ -17,6 -17,7 +17,8 @@@
  #include "sha1-lookup.h"
  #include "wt-status.h"
  #include "advice.h"
+ #include "refs.h"
++#include "commit-reach.h"
  
  static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
  
@@@ -843,6 -844,444 +845,86 @@@ void sort_in_topological_order(struct c
  		clear_author_date_slab(&author_date);
  }
  
 -/* merge-base stuff */
 -
 -/* Remember to update object flag allocation in object.h */
 -#define PARENT1		(1u<<16)
 -#define PARENT2		(1u<<17)
 -#define STALE		(1u<<18)
 -#define RESULT		(1u<<19)
 -
 -static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
 -
 -static int queue_has_nonstale(struct prio_queue *queue)
 -{
 -	int i;
 -	for (i = 0; i < queue->nr; i++) {
 -		struct commit *commit = queue->array[i].data;
 -		if (!(commit->object.flags & STALE))
 -			return 1;
 -	}
 -	return 0;
 -}
 -
 -/* all input commits in one and twos[] must have been parsed! */
 -static struct commit_list *paint_down_to_common(struct commit *one, int n,
 -						struct commit **twos,
 -						int min_generation)
 -{
 -	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 -	struct commit_list *result = NULL;
 -	int i;
 -	uint32_t last_gen = GENERATION_NUMBER_INFINITY;
 -
 -	one->object.flags |= PARENT1;
 -	if (!n) {
 -		commit_list_append(one, &result);
 -		return result;
 -	}
 -	prio_queue_put(&queue, one);
 -
 -	for (i = 0; i < n; i++) {
 -		twos[i]->object.flags |= PARENT2;
 -		prio_queue_put(&queue, twos[i]);
 -	}
 -
 -	while (queue_has_nonstale(&queue)) {
 -		struct commit *commit = prio_queue_get(&queue);
 -		struct commit_list *parents;
 -		int flags;
 -
 -		if (commit->generation > last_gen)
 -			BUG("bad generation skip %8x > %8x at %s",
 -			    commit->generation, last_gen,
 -			    oid_to_hex(&commit->object.oid));
 -		last_gen = commit->generation;
 -
 -		if (commit->generation < min_generation)
 -			break;
 -
 -		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
 -		if (flags == (PARENT1 | PARENT2)) {
 -			if (!(commit->object.flags & RESULT)) {
 -				commit->object.flags |= RESULT;
 -				commit_list_insert_by_date(commit, &result);
 -			}
 -			/* Mark parents of a found merge stale */
 -			flags |= STALE;
 -		}
 -		parents = commit->parents;
 -		while (parents) {
 -			struct commit *p = parents->item;
 -			parents = parents->next;
 -			if ((p->object.flags & flags) == flags)
 -				continue;
 -			if (parse_commit(p))
 -				return NULL;
 -			p->object.flags |= flags;
 -			prio_queue_put(&queue, p);
 -		}
 -	}
 -
 -	clear_prio_queue(&queue);
 -	return result;
 -}
 -
 -static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
 -{
 -	struct commit_list *list = NULL;
 -	struct commit_list *result = NULL;
 -	int i;
 -
 -	for (i = 0; i < n; i++) {
 -		if (one == twos[i])
 -			/*
 -			 * We do not mark this even with RESULT so we do not
 -			 * have to clean it up.
 -			 */
 -			return commit_list_insert(one, &result);
 -	}
 -
 -	if (parse_commit(one))
 -		return NULL;
 -	for (i = 0; i < n; i++) {
 -		if (parse_commit(twos[i]))
 -			return NULL;
 -	}
 -
 -	list = paint_down_to_common(one, n, twos, 0);
 -
 -	while (list) {
 -		struct commit *commit = pop_commit(&list);
 -		if (!(commit->object.flags & STALE))
 -			commit_list_insert_by_date(commit, &result);
 -	}
 -	return result;
 -}
 -
+ struct rev_collect {
+ 	struct commit **commit;
+ 	int nr;
+ 	int alloc;
+ 	unsigned int initial : 1;
+ };
+ 
+ static void add_one_commit(struct object_id *oid, struct rev_collect *revs)
+ {
+ 	struct commit *commit;
+ 
+ 	if (is_null_oid(oid))
+ 		return;
+ 
+ 	commit = lookup_commit(the_repository, oid);
+ 	if (!commit ||
+ 	    (commit->object.flags & TMP_MARK) ||
+ 	    parse_commit(commit))
+ 		return;
+ 
+ 	ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
+ 	revs->commit[revs->nr++] = commit;
+ 	commit->object.flags |= TMP_MARK;
+ }
+ 
+ static int collect_one_reflog_ent(struct object_id *ooid, struct object_id *noid,
+ 				  const char *ident, timestamp_t timestamp,
+ 				  int tz, const char *message, void *cbdata)
+ {
+ 	struct rev_collect *revs = cbdata;
+ 
+ 	if (revs->initial) {
+ 		revs->initial = 0;
+ 		add_one_commit(ooid, revs);
+ 	}
+ 	add_one_commit(noid, revs);
+ 	return 0;
+ }
+ 
+ struct commit *get_fork_point(const char *refname, struct commit *commit)
+ {
+ 	struct object_id oid;
+ 	struct rev_collect revs;
+ 	struct commit_list *bases;
+ 	int i;
+ 	struct commit *ret = NULL;
+ 
+ 	memset(&revs, 0, sizeof(revs));
+ 	revs.initial = 1;
+ 	for_each_reflog_ent(refname, collect_one_reflog_ent, &revs);
+ 
+ 	if (!revs.nr && !get_oid(refname, &oid))
+ 		add_one_commit(&oid, &revs);
+ 
+ 	for (i = 0; i < revs.nr; i++)
+ 		revs.commit[i]->object.flags &= ~TMP_MARK;
+ 
+ 	bases = get_merge_bases_many(commit, revs.nr, revs.commit);
+ 
+ 	/*
+ 	 * There should be one and only one merge base, when we found
+ 	 * a common ancestor among reflog entries.
+ 	 */
+ 	if (!bases || bases->next)
+ 		goto cleanup_return;
+ 
+ 	/* And the found one must be one of the reflog entries */
+ 	for (i = 0; i < revs.nr; i++)
+ 		if (&bases->item->object == &revs.commit[i]->object)
+ 			break; /* found */
+ 	if (revs.nr <= i)
+ 		goto cleanup_return;
+ 
+ 	ret = bases->item;
+ 
+ cleanup_return:
+ 	free_commit_list(bases);
+ 	return ret;
+ }
+ 
 -struct commit_list *get_octopus_merge_bases(struct commit_list *in)
 -{
 -	struct commit_list *i, *j, *k, *ret = NULL;
 -
 -	if (!in)
 -		return ret;
 -
 -	commit_list_insert(in->item, &ret);
 -
 -	for (i = in->next; i; i = i->next) {
 -		struct commit_list *new_commits = NULL, *end = NULL;
 -
 -		for (j = ret; j; j = j->next) {
 -			struct commit_list *bases;
 -			bases = get_merge_bases(i->item, j->item);
 -			if (!new_commits)
 -				new_commits = bases;
 -			else
 -				end->next = bases;
 -			for (k = bases; k; k = k->next)
 -				end = k;
 -		}
 -		ret = new_commits;
 -	}
 -	return ret;
 -}
 -
 -static int remove_redundant(struct commit **array, int cnt)
 -{
 -	/*
 -	 * Some commit in the array may be an ancestor of
 -	 * another commit.  Move such commit to the end of
 -	 * the array, and return the number of commits that
 -	 * are independent from each other.
 -	 */
 -	struct commit **work;
 -	unsigned char *redundant;
 -	int *filled_index;
 -	int i, j, filled;
 -
 -	work = xcalloc(cnt, sizeof(*work));
 -	redundant = xcalloc(cnt, 1);
 -	ALLOC_ARRAY(filled_index, cnt - 1);
 -
 -	for (i = 0; i < cnt; i++)
 -		parse_commit(array[i]);
 -	for (i = 0; i < cnt; i++) {
 -		struct commit_list *common;
 -		uint32_t min_generation = array[i]->generation;
 -
 -		if (redundant[i])
 -			continue;
 -		for (j = filled = 0; j < cnt; j++) {
 -			if (i == j || redundant[j])
 -				continue;
 -			filled_index[filled] = j;
 -			work[filled++] = array[j];
 -
 -			if (array[j]->generation < min_generation)
 -				min_generation = array[j]->generation;
 -		}
 -		common = paint_down_to_common(array[i], filled, work,
 -					      min_generation);
 -		if (array[i]->object.flags & PARENT2)
 -			redundant[i] = 1;
 -		for (j = 0; j < filled; j++)
 -			if (work[j]->object.flags & PARENT1)
 -				redundant[filled_index[j]] = 1;
 -		clear_commit_marks(array[i], all_flags);
 -		clear_commit_marks_many(filled, work, all_flags);
 -		free_commit_list(common);
 -	}
 -
 -	/* Now collect the result */
 -	COPY_ARRAY(work, array, cnt);
 -	for (i = filled = 0; i < cnt; i++)
 -		if (!redundant[i])
 -			array[filled++] = work[i];
 -	for (j = filled, i = 0; i < cnt; i++)
 -		if (redundant[i])
 -			array[j++] = work[i];
 -	free(work);
 -	free(redundant);
 -	free(filled_index);
 -	return filled;
 -}
 -
 -static struct commit_list *get_merge_bases_many_0(struct commit *one,
 -						  int n,
 -						  struct commit **twos,
 -						  int cleanup)
 -{
 -	struct commit_list *list;
 -	struct commit **rslt;
 -	struct commit_list *result;
 -	int cnt, i;
 -
 -	result = merge_bases_many(one, n, twos);
 -	for (i = 0; i < n; i++) {
 -		if (one == twos[i])
 -			return result;
 -	}
 -	if (!result || !result->next) {
 -		if (cleanup) {
 -			clear_commit_marks(one, all_flags);
 -			clear_commit_marks_many(n, twos, all_flags);
 -		}
 -		return result;
 -	}
 -
 -	/* There are more than one */
 -	cnt = commit_list_count(result);
 -	rslt = xcalloc(cnt, sizeof(*rslt));
 -	for (list = result, i = 0; list; list = list->next)
 -		rslt[i++] = list->item;
 -	free_commit_list(result);
 -
 -	clear_commit_marks(one, all_flags);
 -	clear_commit_marks_many(n, twos, all_flags);
 -
 -	cnt = remove_redundant(rslt, cnt);
 -	result = NULL;
 -	for (i = 0; i < cnt; i++)
 -		commit_list_insert_by_date(rslt[i], &result);
 -	free(rslt);
 -	return result;
 -}
 -
 -struct commit_list *get_merge_bases_many(struct commit *one,
 -					 int n,
 -					 struct commit **twos)
 -{
 -	return get_merge_bases_many_0(one, n, twos, 1);
 -}
 -
 -struct commit_list *get_merge_bases_many_dirty(struct commit *one,
 -					       int n,
 -					       struct commit **twos)
 -{
 -	return get_merge_bases_many_0(one, n, twos, 0);
 -}
 -
 -struct commit_list *get_merge_bases(struct commit *one, struct commit *two)
 -{
 -	return get_merge_bases_many_0(one, 1, &two, 1);
 -}
 -
 -/*
 - * Is "commit" a descendant of one of the elements on the "with_commit" list?
 - */
 -int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
 -{
 -	if (!with_commit)
 -		return 1;
 -	while (with_commit) {
 -		struct commit *other;
 -
 -		other = with_commit->item;
 -		with_commit = with_commit->next;
 -		if (in_merge_bases(other, commit))
 -			return 1;
 -	}
 -	return 0;
 -}
 -
 -/*
 - * Is "commit" an ancestor of one of the "references"?
 - */
 -int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference)
 -{
 -	struct commit_list *bases;
 -	int ret = 0, i;
 -	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
 -
 -	if (parse_commit(commit))
 -		return ret;
 -	for (i = 0; i < nr_reference; i++) {
 -		if (parse_commit(reference[i]))
 -			return ret;
 -		if (reference[i]->generation < min_generation)
 -			min_generation = reference[i]->generation;
 -	}
 -
 -	if (commit->generation > min_generation)
 -		return ret;
 -
 -	bases = paint_down_to_common(commit, nr_reference, reference, commit->generation);
 -	if (commit->object.flags & PARENT2)
 -		ret = 1;
 -	clear_commit_marks(commit, all_flags);
 -	clear_commit_marks_many(nr_reference, reference, all_flags);
 -	free_commit_list(bases);
 -	return ret;
 -}
 -
 -/*
 - * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
 - */
 -int in_merge_bases(struct commit *commit, struct commit *reference)
 -{
 -	return in_merge_bases_many(commit, 1, &reference);
 -}
 -
 -struct commit_list *reduce_heads(struct commit_list *heads)
 -{
 -	struct commit_list *p;
 -	struct commit_list *result = NULL, **tail = &result;
 -	struct commit **array;
 -	int num_head, i;
 -
 -	if (!heads)
 -		return NULL;
 -
 -	/* Uniquify */
 -	for (p = heads; p; p = p->next)
 -		p->item->object.flags &= ~STALE;
 -	for (p = heads, num_head = 0; p; p = p->next) {
 -		if (p->item->object.flags & STALE)
 -			continue;
 -		p->item->object.flags |= STALE;
 -		num_head++;
 -	}
 -	array = xcalloc(num_head, sizeof(*array));
 -	for (p = heads, i = 0; p; p = p->next) {
 -		if (p->item->object.flags & STALE) {
 -			array[i++] = p->item;
 -			p->item->object.flags &= ~STALE;
 -		}
 -	}
 -	num_head = remove_redundant(array, num_head);
 -	for (i = 0; i < num_head; i++)
 -		tail = &commit_list_insert(array[i], tail)->next;
 -	free(array);
 -	return result;
 -}
 -
 -void reduce_heads_replace(struct commit_list **heads)
 -{
 -	struct commit_list *result = reduce_heads(*heads);
 -	free_commit_list(*heads);
 -	*heads = result;
 -}
 -
  static const char gpg_sig_header[] = "gpgsig";
  static const int gpg_sig_header_len = sizeof(gpg_sig_header) - 1;
  
diff --cc commit.h
index 1d260d62f5,b34240017f..6c4428c593
--- a/commit.h
+++ b/commit.h
@@@ -202,9 -202,17 +202,11 @@@ typedef int (*each_commit_graft_fn)(con
  
  struct commit_graft *read_graft_line(struct strbuf *line);
  int register_commit_graft(struct repository *r, struct commit_graft *, int);
 +void prepare_commit_graft(struct repository *r);
  struct commit_graft *lookup_commit_graft(struct repository *r, const struct object_id *oid);
  
 -extern struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2);
 -extern struct commit_list *get_merge_bases_many(struct commit *one, int n, struct commit **twos);
 -extern struct commit_list *get_octopus_merge_bases(struct commit_list *in);
 -
 -/* To be used only when object flags after this call no longer matter */
 -extern struct commit_list *get_merge_bases_many_dirty(struct commit *one, int n, struct commit **twos);
 -
+ struct commit *get_fork_point(const char *refname, struct commit *commit);
+ 
  /* largest positive number a signed 32-bit integer can contain */
  #define INFINITE_DEPTH 0x7fffffff