There are several commit walks in the codebase. Group them together into
a new commit-reach.c file and corresponding header. After we group these
walks into one place, we can reduce duplicate logic by calling
equivalent methods.
The method declarations in commit.h are not touched by this commit and
will be moved in a following commit. Many consumers need to point to
commit-reach.h and that would bloat this commit.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
LIB_OBJS += combine-diff.o
LIB_OBJS += commit.o
LIB_OBJS += commit-graph.o
+LIB_OBJS += commit-reach.o
LIB_OBJS += compat/obstack.o
LIB_OBJS += compat/terminal.o
LIB_OBJS += config.o
--- /dev/null
+#include "cache.h"
+#include "prio-queue.h"
+#include "commit.h"
+#include "commit-reach.h"
+
+/* 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 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;
+}
--- /dev/null
+#ifndef __COMMIT_REACH_H__
+#define __COMMIT_REACH_H__
+
+struct commit;
+struct commit_list;
+
+struct commit_list *get_merge_bases_many(struct commit *one,
+ int n,
+ struct commit **twos);
+struct commit_list *get_merge_bases_many_dirty(struct commit *one,
+ int n,
+ struct commit **twos);
+struct commit_list *get_merge_bases(struct commit *one, struct commit *two);
+struct commit_list *get_octopus_merge_bases(struct commit_list *in);
+
+/* To be used only when object flags after this call no longer matter */
+struct commit_list *get_merge_bases_many_dirty(struct commit *one, int n, struct commit **twos);
+
+int is_descendant_of(struct commit *commit, struct commit_list *with_commit);
+int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference);
+int in_merge_bases(struct commit *commit, struct commit *reference);
+
+
+/*
+ * Takes a list of commits and returns a new list where those
+ * have been removed that can be reached from other commits in
+ * the list. It is useful for, e.g., reducing the commits
+ * randomly thrown at the git-merge command and removing
+ * redundant commits that the user shouldn't have given to it.
+ *
+ * This function destroys the STALE bit of the commit objects'
+ * flags.
+ */
+struct commit_list *reduce_heads(struct commit_list *heads);
+
+/*
+ * Like `reduce_heads()`, except it replaces the list. Use this
+ * instead of `foo = reduce_heads(foo);` to avoid memory leaks.
+ */
+void reduce_heads_replace(struct commit_list **heads);
+
+#endif
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 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;
* bisect.c: 16
* bundle.c: 16
* http-push.c: 16-----19
- * commit.c: 16-----19
+ * commit-reach.c: 16-----19
* sha1-name.c: 20
* list-objects-filter.c: 21
* builtin/fsck.c: 0--3