From 6683463ed6b2da9eed309c305806f9393d1ae728 Mon Sep 17 00:00:00 2001
From: Linus Torvalds <torvalds@ppc970.osdl.org>
Date: Sun, 17 Apr 2005 12:18:17 -0700
Subject: [PATCH] Do a very simple "merge-base" that finds the most recent
 common parent of two commits.

The question of "best" commit can probably be tweaked almost arbitrarily.
In particular, trying to take things like how big the tree differences
are into account migt be a good idea. This one is just very simple.
---
 Makefile     |  5 ++++-
 merge-base.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 61 insertions(+), 1 deletion(-)
 create mode 100644 merge-base.c

diff --git a/Makefile b/Makefile
index 92de1cb7..871c0bb0 100644
--- a/Makefile
+++ b/Makefile
@@ -14,7 +14,7 @@ CC=gcc
 
 PROG=   update-cache show-diff init-db write-tree read-tree commit-tree \
 	cat-file fsck-cache checkout-cache diff-tree rev-tree show-files \
-	check-files ls-tree
+	check-files ls-tree merge-base
 
 all: $(PROG)
 
@@ -64,6 +64,9 @@ check-files: check-files.o read-cache.o
 ls-tree: ls-tree.o read-cache.o
 	$(CC) $(CFLAGS) -o ls-tree ls-tree.o read-cache.o $(LIBS)
 
+merge-base: merge-base.o read-cache.o
+	$(CC) $(CFLAGS) -o merge-base merge-base.o read-cache.o $(LIBS)
+
 read-cache.o: cache.h
 show-diff.o: cache.h
 
diff --git a/merge-base.c b/merge-base.c
new file mode 100644
index 00000000..36ac4200
--- /dev/null
+++ b/merge-base.c
@@ -0,0 +1,57 @@
+#include "cache.h"
+#include "revision.h"
+
+/*
+ * This is stupid. We could have much better heurstics, I bet.
+ */
+static int better(struct revision *new, struct revision *old)
+{
+	return new->date > old->date;
+}
+
+static struct revision *common_parent(struct revision *rev1, struct revision *rev2)
+{
+	int i;
+	struct revision *best = NULL;
+
+	mark_reachable(rev1, 1);
+	mark_reachable(rev2, 2);
+	for (i = 0; i < nr_revs ;i++) {
+		struct revision *rev = revs[i];
+		if ((rev->flags & 3) != 3)
+			continue;
+		if (!best) {
+			best = rev;
+			continue;
+		}
+		if (better(rev, best))
+			best = rev;
+	}
+	return best;
+}
+
+int main(int argc, char **argv)
+{
+	unsigned char rev1[20], rev2[20];
+	struct revision *common;
+
+	if (argc != 3 || get_sha1_hex(argv[1], rev1) || get_sha1_hex(argv[2], rev2))
+		usage("merge-base <commit1> <commit2>");
+
+	/*
+	 * We will eventually want to include a revision cache file
+	 * that "rev-tree.c" has generated, since this is going to
+	 * otherwise be quite expensive for big trees..
+	 *
+	 * That's some time off, though, and in the meantime we know
+	 * that we have a solution to the eventual expense.
+	 */
+	parse_commit(rev1);
+	parse_commit(rev2);
+
+	common = common_parent(lookup_rev(rev1), lookup_rev(rev2));
+	if (!common)
+		die("no common parent found");
+	printf("%s\n", sha1_to_hex(common->sha1));
+	return 0;
+}
-- 
2.11.0