commit e12cc036c3e7a71d71bb6a83a9a97bd53f5ba497
from: Stefan Sperling <stsp@stsp.name>
date: Wed Mar 27 10:49:13 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 - 83e5e9a11730a93d948aabbafdb2592713eb6f28
commit + e12cc036c3e7a71d71bb6a83a9a97bd53f5ba497
blob - 88729baf00e38ec442bf51dbd5f42196934e953a
blob + 93b12cd6d160b9b15d26706c00de377d49219f15
--- cvg/cvg.c
+++ cvg/cvg.c
@@ -2066,7 +2066,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 - 74e2fb65d552093211aa85ccb3eaaa5d77f81f6f
blob + 3ccb50b750cbf5628d56d7f361fdd88e54426fd6
--- got/got.c
+++ got/got.c
@@ -2891,7 +2891,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;
 
@@ -11020,7 +11020,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;
 
@@ -11250,6 +11250,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;
@@ -11500,8 +11557,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,
@@ -11509,6 +11566,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) {
@@ -13510,7 +13585,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 - 976b20aab20831ca6c66bb5793542bf438ec1688
blob + 3748c660e7ad27e0b645825b852620a1a041ed71
--- lib/commit_graph.c
+++ lib/commit_graph.c
@@ -702,12 +702,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;
@@ -728,16 +730,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 - 681905dc26b73d6a41382533ca6a87a306c8a240
blob + b6be87a769c4d7440f941e66aabb66e589e19a77
--- lib/send.c
+++ lib/send.c
@@ -226,7 +226,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"