Commit Diff


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"