git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 2/2] Introduce reduce_heads()

From
Junio C Hamano <gitster@pobox.com>
Date
Jun 21, 2008, 09:45 UTC
Message-ID
<7vfxr7azos.fsf@gitster.siamese.dyndns.org>
In-Reply-To
<1214007784-4801-1-git-send-email-vmiklos@frugalware.org>

The new function reduce_heads() is given a list of commits, and removes ones that can be reached from other commits in the list. It is useful for reducing the commits randomly thrown at the git-merge command and remove redundant commits that the user shouldn't have given to it.

The implementation uses the get_merge_bases_many() introduced in the previous commit. If the merge base between one commit taken from the list and the remaining commits is the commit itself, that means the commit is reachable from some of the other commits.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 * The important part of this patch is the addition to commit.c to show
   how I would write your filter_independent().  The new command is not
   essential, but is included as a demonstration.
 Makefile               |    1 +
 builtin-reduce-heads.c |   44 ++++++++++++++++++++++++++++++++++++++++++++
 builtin.h              |    1 +
 commit.c               |   45 +++++++++++++++++++++++++++++++++++++++++++++
 commit.h               |    2 ++
 git.c                  |    1 +
 6 files changed, 94 insertions(+), 0 deletions(-)
 create mode 100644 builtin-reduce-heads.c
diff --git a/Makefile b/Makefile
index b003e3e..d660756 100644
--- a/Makefile
+++ b/Makefile
@@ -522,6 +522,7 @@ BUILTIN_OBJS += builtin-pack-refs.o
 BUILTIN_OBJS += builtin-prune-packed.o
 BUILTIN_OBJS += builtin-prune.o
 BUILTIN_OBJS += builtin-push.o
+BUILTIN_OBJS += builtin-reduce-heads.o
 BUILTIN_OBJS += builtin-read-tree.o
 BUILTIN_OBJS += builtin-reflog.o
 BUILTIN_OBJS += builtin-remote.o
diff --git a/builtin-reduce-heads.c b/builtin-reduce-heads.c
new file mode 100644
index 0000000..ff6178d
--- /dev/null
+++ b/builtin-reduce-heads.c
@@ -0,0 +1,44 @@
+#include "cache.h"
+#include "commit.h"
+#include "strbuf.h"
+
+static void show_commit_list(struct commit_list *list)
+{
+	while (list) {
+		struct strbuf it;
+		struct commit *commit = list->item;
+
+		list = list->next;
+		strbuf_init(&it, 128);
+		parse_commit(commit);
+		pretty_print_commit(CMIT_FMT_ONELINE, commit, &it,
+				    0, NULL, NULL, 0, 0);
+		puts(it.buf);
+		strbuf_release(&it);
+	}
+}
+
+int cmd_reduce_heads(int ac, const char **av, const char *prefix)
+{
+	struct commit_list *list = NULL, **tail = &list;
+	int i;
+
+	for (i = 1; i < ac; i++) {
+		struct commit *commit;
+		unsigned char sha1[20];
+
+		if (get_sha1(av[i], sha1))
+			die("'%s' is not a valid ref.", av[i]);
+		commit = lookup_commit_reference(sha1);
+		if (!commit)
+			die("cannot find commit %s", av[i]);
+		tail = &commit_list_insert(commit, tail)->next;
+	}
+
+	show_commit_list(list);
+	putchar('\n');
+
+	list = reduce_heads(list);
+	show_commit_list(list);
+	return 0;
+}
diff --git a/builtin.h b/builtin.h
index b460b2d..b6fb163 100644
--- a/builtin.h
+++ b/builtin.h
@@ -72,6 +72,7 @@ extern int cmd_read_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_reflog(int argc, const char **argv, const char *prefix);
 extern int cmd_remote(int argc, const char **argv, const char *prefix);
 extern int cmd_config(int argc, const char **argv, const char *prefix);
+extern int cmd_reduce_heads(int argc, const char **argv, const char *prefix);
 extern int cmd_rerere(int argc, const char **argv, const char *prefix);
 extern int cmd_reset(int argc, const char **argv, const char *prefix);
 extern int cmd_rev_list(int argc, const char **argv, const char *prefix);
diff --git a/commit.c b/commit.c
index 4ee234d..0fc4acb 100644
--- a/commit.c
+++ b/commit.c
@@ -690,3 +690,48 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)
 	free_commit_list(bases);
 	return ret;
 }
+
+struct commit_list *reduce_heads(struct commit_list *heads)
+{
+	struct commit_list *p;
+	struct commit_list *result = NULL, **tail = &result;
+	struct commit **other;
+	size_t num_head, num_other;
+
+	if (!heads)
+		return NULL;
+
+	/* Avoid unnecessary reallocations */
+	for (p = heads, num_head = 0; p; p = p->next)
+		num_head++;
+	other = xcalloc(sizeof(*other), num_head);
+
+	/* For each commit, see if it can be reached by others */
+	for (p = heads; p; p = p->next) {
+		struct commit_list *q, *base;
+
+		num_other = 0;
+		for (q = heads; q; q = q->next) {
+			if (p == q)
+				continue;
+			other[num_other++] = q->item;
+		}
+		if (num_other) {
+			base = get_merge_bases_many(p->item, num_other, other, 1);
+		} else
+			base = NULL;
+		/*
+		 * If p->item does not have anything common with other
+		 * commits, there won't be any merge base.  If it is
+		 * reachable from some of the others, p->item will be
+		 * the merge base.  If its history is connected with
+		 * others, but p->item is not reachable by others, we
+		 * will get something other than p->item back.
+		 */
+		if (!base || (base->item != p->item))
+			tail = &(commit_list_insert(p->item, tail)->next);
+		free_commit_list(base);
+	}
+	free(other);
+	return result;
+}
diff --git a/commit.h b/commit.h
index 2d94d41..ec95102 100644
--- a/commit.h
+++ b/commit.h
@@ -138,4 +138,6 @@ static inline int single_parent(struct commit *commit)
 	return commit->parents && !commit->parents->next;
 }
 
+struct commit_list *reduce_heads(struct commit_list *heads);
+
 #endif /* COMMIT_H */
diff --git a/git.c b/git.c
index 59f0fcc..23b690d 100644
--- a/git.c
+++ b/git.c
@@ -338,6 +338,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "prune-packed", cmd_prune_packed, RUN_SETUP },
 		{ "push", cmd_push, RUN_SETUP },
 		{ "read-tree", cmd_read_tree, RUN_SETUP },
+		{ "reduce-heads", cmd_reduce_heads, RUN_SETUP },
 		{ "reflog", cmd_reflog, RUN_SETUP },
 		{ "remote", cmd_remote, RUN_SETUP },
 		{ "repo-config", cmd_config },

-- 
1.5.6.6.gd3e97
Previous: Junio C HamanoNext: Junio C Hamano
Message 21 of 23 in “Build in merge”
  1. 00/11 Build in mergeMiklos Vajna, Jun 19, 2008
  2. 01/11 Move split_cmdline() to alias.cMiklos Vajna, Jun 19, 2008
  3. 02/11 Move commit_list_count() to commit.cMiklos Vajna, Jun 19, 2008
  4. 03/11 Move parse-options's skip_prefix() to git-compat-util.hMiklos Vajna, Jun 19, 2008
  5. 04/11 Add new test to ensure git-merge handles pull.twohead and pull.octopusMiklos Vajna, Jun 19, 2008
  6. 05/11 parseopt: add a new PARSE_OPT_ARGV0_IS_AN_OPTION optionMiklos Vajna, Jun 19, 2008
  7. 06/11 Move read_cache_unmerged() to read-cache.cMiklos Vajna, Jun 19, 2008
  8. 07/11 git-fmt-merge-msg: make it usable from other builtinsMiklos Vajna, Jun 19, 2008
  9. 08/11 Introduce get_octopus_merge_bases() in commit.cMiklos Vajna, Jun 19, 2008
  10. 09/11 Introduce filter_independent() in commit.cMiklos Vajna, Jun 19, 2008
  11. 10/11 Build in mergeMiklos Vajna, Jun 19, 2008
  12. 11/11 Add new test to ensure git-merge handles more than 25 refs.Miklos Vajna, Jun 19, 2008
  13. Junio C HamanoJun 20, 2008
  14. Johannes SchindelinJun 20, 2008
  15. Miklos VajnaJun 20, 2008
  16. Johannes SchindelinJun 20, 2008
  17. Miklos VajnaJun 20, 2008
  18. Introduce filter_independent() in commit.cMiklos Vajna, Jun 21, 2008
  19. Junio C HamanoJun 21, 2008
  20. 1/2 Introduce get_merge_bases_many()Junio C Hamano, Jun 21, 2008
  21. 2/2 Introduce reduce_heads()Junio C Hamano, Jun 21, 2008
  22. Junio C HamanoJun 20, 2008
  23. Miklos VajnaJun 21, 2008

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.