commit 807c60e9b0d21645de0e196aaf07eb447a1c7487
from: Stefan Sperling <stsp@stsp.name>
via: Thomas Adam <thomas@xteddy.org>
date: Sat Mar 30 17:21:23 2024 UTC

make 'got rebase' find a merge base with topological sorting if needed

Fixes a problematic case of spurious conflicts encountered by
naddy@ on landry's firefox package git repository.

The current implementation of toposort is expensive, so this might
make rebase appear to run slowly on large repositories. However,
this is better than letting users deal with spurious conflicts.

ok op@

commit - e6fdf1dda4bb09f48bc1344b207aebb193636a7f
commit + 807c60e9b0d21645de0e196aaf07eb447a1c7487
blob - dcc18548536ddae27b9d4ec7e2783af9a8735119
blob + af1a4ad687b6df528594ca423dfba16083a969f0
--- cvg/cvg.c
+++ cvg/cvg.c
@@ -2064,7 +2064,7 @@ check_linear_ancestry(struct got_object_id *commit_id,
 	struct got_object_id *yca_id;
 
 	err = got_commit_graph_find_youngest_common_ancestor(&yca_id,
-	    commit_id, base_commit_id, 1, repo, check_cancelled, NULL);
+	    commit_id, base_commit_id, 1, 0, repo, check_cancelled, NULL);
 	if (err)
 		return err;
 
blob - 8eb1de9d033a4fbe3d7bc8adff0491af9182f4f1
blob + 744c27831da9fae5b3fc6abdfcc2c92d92dfbfc1
--- got/got.c
+++ got/got.c
@@ -2890,7 +2890,7 @@ check_linear_ancestry(struct got_object_id *commit_id,
 	struct got_object_id *yca_id;
 
 	err = got_commit_graph_find_youngest_common_ancestor(&yca_id,
-	    commit_id, base_commit_id, 1, repo, check_cancelled, NULL);
+	    commit_id, base_commit_id, 1, 0, repo, check_cancelled, NULL);
 	if (err)
 		return err;
 
@@ -11019,7 +11019,7 @@ print_backup_ref(const char *branch_name, const char *
 		goto done;
 
 	err = got_commit_graph_find_youngest_common_ancestor(&yca_id,
-	    old_commit_id, new_commit_id, 1, repo, check_cancelled, NULL);
+	    old_commit_id, new_commit_id, 1, 0, repo, check_cancelled, NULL);
 	if (err)
 		goto done;
 
@@ -11249,6 +11249,63 @@ abort_progress(void *arg, unsigned char status, const 
 }
 
 static const struct got_error *
+find_merge_commit_yca(struct got_object_id **new_yca_id,
+    struct got_object_id *branch_head_commit_id,
+    struct got_object_id *yca_id,
+    struct got_object_id *base_commit_id,
+    struct got_repository *repo)
+{
+	const struct got_error *err = NULL;
+	struct got_commit_graph *graph = NULL;
+	struct got_commit_object *commit = NULL;
+
+	*new_yca_id = NULL;
+
+	err = got_commit_graph_open(&graph, "/", 1);
+	if (err)
+		return err;
+
+	err = got_commit_graph_iter_start(graph, base_commit_id,
+	    repo, check_cancelled, NULL);
+	if (err)
+		goto done;
+
+	for (;;) {
+		struct got_object_id id;
+
+		err = got_commit_graph_iter_next(&id, graph, repo,
+		    check_cancelled, NULL);
+		if (err) {
+			if (err->code == GOT_ERR_ITER_COMPLETED)
+				err = NULL;
+			break;
+		}
+
+		err = got_object_open_as_commit(&commit, repo, &id);
+		if (err)
+			break;
+
+		if (got_object_commit_get_nparents(commit) > 1) {
+			/* Search for a better YCA using toposort. */
+			err = got_commit_graph_find_youngest_common_ancestor(
+			    new_yca_id, base_commit_id, branch_head_commit_id,
+			    0, 1, repo, check_cancelled, NULL);
+			break;
+		}
+
+		if (got_object_id_cmp(&id, yca_id) == 0)
+			break;
+		got_object_commit_close(commit);
+		commit = NULL;
+	}
+done:
+	got_commit_graph_close(graph);
+	if (commit)
+		got_object_commit_close(commit);
+	return err;
+}
+
+static const struct got_error *
 cmd_rebase(int argc, char *argv[])
 {
 	const struct got_error *error = NULL;
@@ -11499,8 +11556,8 @@ cmd_rebase(int argc, char *argv[])
 		}
 
 		error = got_commit_graph_find_youngest_common_ancestor(&yca_id,
-		    base_commit_id, branch_head_commit_id, 1, repo,
-		    check_cancelled, NULL);
+		    base_commit_id, branch_head_commit_id, 1, 0,
+		    repo, check_cancelled, NULL);
 		if (error) {
 			if (error->code == GOT_ERR_ANCESTRY) {
 				error = got_error_msg(GOT_ERR_ANCESTRY,
@@ -11508,6 +11565,24 @@ cmd_rebase(int argc, char *argv[])
 				    "ancestry with work tree's branch");
 			}
 			goto done;
+		}
+
+		/*
+		 * If a merge commit appears between the new base branch tip
+		 * and a YCA found via first-parent traversal then we might
+		 * find a better YCA using topologically sorted commits.
+		 */
+		if (got_object_id_cmp(base_commit_id, yca_id) != 0) {
+			struct got_object_id *better_yca_id;
+			error = find_merge_commit_yca(&better_yca_id,
+			    branch_head_commit_id, yca_id,
+			    base_commit_id, repo);
+			if (error)
+				goto done;
+			if (better_yca_id) {
+				free(yca_id);
+				yca_id = better_yca_id;
+			}
 		}
 
 		if (got_object_id_cmp(base_commit_id, yca_id) == 0) {
@@ -13509,7 +13584,7 @@ cmd_merge(int argc, char *argv[])
 	}
 
 	error = got_commit_graph_find_youngest_common_ancestor(&yca_id,
-	    wt_branch_tip, branch_tip, 0, repo,
+	    wt_branch_tip, branch_tip, 0, 0, repo,
 	    check_cancelled, NULL);
 	if (error && error->code != GOT_ERR_ANCESTRY)
 		goto done;
blob - 35d7c7072f5ce67648f7f2c4a878396746ad3e45
blob + a425d8d817ab860cb50f4d849945ba8fe207c0fd
--- include/got_commit_graph.h
+++ include/got_commit_graph.h
@@ -34,4 +34,4 @@ const struct got_error *got_commit_graph_intersect(str
 /* Find the youngest common ancestor of two commits. */
 const struct got_error *got_commit_graph_find_youngest_common_ancestor(
     struct got_object_id **, struct got_object_id *, struct got_object_id *,
-    int, struct got_repository *, got_cancel_cb, void *);
+    int, int, struct got_repository *, got_cancel_cb, void *);
blob - a0fc7d3f98de504f08c2cba03e15a2d6c8115c7c
blob + 4e7352b4283256df4cc76652d06010a30cb4d263
--- lib/commit_graph.c
+++ lib/commit_graph.c
@@ -701,12 +701,14 @@ find_yca_add_id(struct got_object_id **yca_id, struct 
  * common ancestors.
  *
  * If first_parent_traversal is nonzero, only linear history is considered.
+ * If toposort is set then sort commits in topological order before
+ * traversing them.
  */
 const struct got_error *
 got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
     struct got_object_id *commit_id, struct got_object_id *commit_id2,
-    int first_parent_traversal,
-    struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
+    int first_parent_traversal, int toposort, struct got_repository *repo,
+    got_cancel_cb cancel_cb, void *cancel_arg)
 {
 	const struct got_error *err = NULL;
 	struct got_commit_graph *graph = NULL, *graph2 = NULL;
@@ -727,16 +729,28 @@ got_commit_graph_find_youngest_common_ancestor(struct 
 	if (err)
 		goto done;
 
-	err = got_commit_graph_iter_start(graph, commit_id, repo,
-	    cancel_cb, cancel_arg);
-	if (err)
-		goto done;
+	if (toposort) {
+		err = got_commit_graph_toposort(graph, commit_id, repo,
+		    cancel_cb, cancel_arg);
+		if (err)
+			goto done;
 
-	err = got_commit_graph_iter_start(graph2, commit_id2, repo,
-	    cancel_cb, cancel_arg);
-	if (err)
-		goto done;
+		err = got_commit_graph_toposort(graph2, commit_id2, repo,
+		    cancel_cb, cancel_arg);
+		if (err)
+			goto done;
+	} else {
+		err = got_commit_graph_iter_start(graph, commit_id, repo,
+		    cancel_cb, cancel_arg);
+		if (err)
+			goto done;
 
+		err = got_commit_graph_iter_start(graph2, commit_id2, repo,
+		    cancel_cb, cancel_arg);
+		if (err)
+			goto done;
+	}
+
 	for (;;) {
 		if (cancel_cb) {
 			err = (*cancel_cb)(cancel_arg);
blob - ef2cbf72a659a6264cdd3058b1b25fd66b9ac26c
blob + 4a74280afdd447d96b205542e1fd78551d115479
--- lib/send.c
+++ lib/send.c
@@ -222,7 +222,7 @@ check_common_ancestry(const char *refname, struct got_
 		    "bad object type on server for %s", refname);
 
 	err = got_commit_graph_find_youngest_common_ancestor(&yca_id,
-	    my_id, their_id, 0, repo, cancel_cb, cancel_arg);
+	    my_id, their_id, 0, 0, repo, cancel_cb, cancel_arg);
 	if (err)
 		return err;
 	if (yca_id == NULL)
blob - 46f11f7c161db17549ba3c6ba4055ffcc81b97ce
blob + 0239e75d3e0b84aa67d95700219ecda8782265ef
--- regress/cmdline/rebase.sh
+++ regress/cmdline/rebase.sh
@@ -2236,8 +2236,7 @@ test_rebase_merged_history_traversal() {
 	local commit1=`git_show_branch_head $testroot/repo master`
 
 	(cd $testroot/wt && got branch newbranch2) >/dev/null
-	(cd $testroot/wt && got rebase newbranch1) > $testroot/stdout \
-		2> $testroot/stderr
+	(cd $testroot/wt && got rebase newbranch1) > $testroot/stdout
 
 	echo "Forwarding refs/heads/newbranch1 to commit $commit1" > \
 		$testroot/stdout.expected
@@ -2245,8 +2244,9 @@ test_rebase_merged_history_traversal() {
 		>> $testroot/stdout.expected
 
 	if ! cmp -s $testroot/stdout.expected $testroot/stdout; then
-		#diff -u $testroot/stdout.expected $testroot/stdout
-		ret="xfail ($(head -n1 $testroot/stdout))"
+		diff -u $testroot/stdout.expected $testroot/stdout
+		test_done "$testroot" "1"
+		return 1
 	fi
 
 	test_done "$testroot" "$ret"