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

[PATCH/RFC 2/5] replay: short-circuit merge replay when parent and base trees are unchanged

From
Johannes Schindelin via GitGitGadget <gitgitgadget@gmail.com>
Date
May 6, 2026, 22:43 UTC
Message-ID
<2f3d696104f7f634e2ca3bb51d57d5c57ffb0bbd.1778107405.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.2106.git.1778107405.gitgitgadget@gmail.com>
From: Johannes Schindelin <johannes.schindelin@gmx.de>

For the common `git history reword` case the rewrite changes only commit messages, so every commit on the line being replayed has the same tree as before. When such a rewrite reaches a 2-parent merge whose rewritten parents AND merge bases all carry the same trees as the originals, the inner auto-merge of the rewritten parents (N) is tree-equal to the inner auto-merge of the original parents (R), and the outer 3-way merge with R as the merge base, the original merge tree as side 1 and N as side 2 yields the original tree as result.

Detect this in `pick_merge_commit()` before doing any merge work and write the new merge commit directly with the original tree and the rewritten parents. This saves two recursive merges and one non-recursive merge per merge commit on the rewrite path, which dominates the cost of `git history reword` across histories with many merges.

The merge-base trees must be checked too, in order. Tree-same parents over a tree-different base could still produce a different auto-merge (a conflict region that did not exist before, or vice versa), and the original resolution would be inappropriate to apply.

To avoid recomputing the merge bases when the fast path does not apply, both pairs are computed up front and the slow path that follows reuses them.

Assisted-by: Claude Opus 4.7
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 replay.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 58 insertions(+), 9 deletions(-)
diff --git a/replay.c b/replay.c
index 3dbce095f9..5dfdef1447 100644
--- a/replay.c
+++ b/replay.c
@@ -396,6 +396,64 @@ static struct commit *pick_merge_commit(struct repository *repo,
 	replayed_par1 = mapped_commit(replayed_commits, parent1, parent1);
 	replayed_par2 = mapped_commit(replayed_commits, parent2, parent2);
 
+	/*
+	 * Compute both pairs of merge bases up front. The fast path below
+	 * needs them for the tree-equality check, and the slow path that
+	 * follows reuses them to avoid recomputing.
+	 */
+	if (repo_get_merge_bases(repo, parent1, parent2, &parent_bases) < 0 ||
+	    repo_get_merge_bases(repo, replayed_par1, replayed_par2,
+				 &replayed_bases) < 0) {
+		result->clean = -1;
+		goto out;
+	}
+
+	/*
+	 * Fast path: when both rewritten parents carry the same trees as
+	 * the originals AND every merge base does too (in order), the
+	 * auto-merges R and N would be tree-equal (their inputs match
+	 * content-wise), so the outer 3-way merge trivially yields the
+	 * original merge's tree. Skip the inner merges and write the new
+	 * merge commit directly.
+	 *
+	 * This is the common case for `git history reword`, which only
+	 * changes commit messages and so leaves every tree on the line
+	 * being replayed unchanged. The merge-base trees must be checked
+	 * too: tree-same parents over a tree-different base could still
+	 * produce a different auto-merge (a conflict region that did not
+	 * exist before, or vice versa), and the original resolution would
+	 * be inappropriate.
+	 */
+	if (oideq(&repo_get_commit_tree(repo, parent1)->object.oid,
+		  &repo_get_commit_tree(repo, replayed_par1)->object.oid) &&
+	    oideq(&repo_get_commit_tree(repo, parent2)->object.oid,
+		  &repo_get_commit_tree(repo, replayed_par2)->object.oid)) {
+		struct commit_list *bo, *bn;
+		int bases_match = 1;
+
+		for (bo = parent_bases, bn = replayed_bases;
+		     bo && bn;
+		     bo = bo->next, bn = bn->next) {
+			if (!oideq(&repo_get_commit_tree(repo, bo->item)->object.oid,
+				   &repo_get_commit_tree(repo, bn->item)->object.oid)) {
+				bases_match = 0;
+				break;
+			}
+		}
+		if (bo || bn)
+			bases_match = 0;
+
+		if (bases_match) {
+			pickme_tree = repo_get_commit_tree(repo, pickme);
+			parents = NULL;
+			commit_list_insert(replayed_par2, &parents);
+			commit_list_insert(replayed_par1, &parents);
+			picked = create_commit(repo, pickme_tree, pickme,
+					       parents, REPLAY_MODE_PICK);
+			goto out;
+		}
+	}
+
 	/*
 	 * R: auto-remerge of the original parents.
 	 *
@@ -408,10 +466,6 @@ static struct commit *pick_merge_commit(struct repository *repo,
 	remerge_opt.show_rename_progress = 0;
 	remerge_opt.branch1 = "ours";
 	remerge_opt.branch2 = "theirs";
-	if (repo_get_merge_bases(repo, parent1, parent2, &parent_bases) < 0) {
-		result->clean = -1;
-		goto out;
-	}
 	merge_incore_recursive(&remerge_opt, parent_bases,
 			       parent1, parent2, &remerge_res);
 	parent_bases = NULL; /* consumed by merge_incore_recursive */
@@ -425,11 +479,6 @@ static struct commit *pick_merge_commit(struct repository *repo,
 	new_merge_opt.show_rename_progress = 0;
 	new_merge_opt.branch1 = "ours";
 	new_merge_opt.branch2 = "theirs";
-	if (repo_get_merge_bases(repo, replayed_par1, replayed_par2,
-				 &replayed_bases) < 0) {
-		result->clean = -1;
-		goto out;
-	}
 	merge_incore_recursive(&new_merge_opt, replayed_bases,
 			       replayed_par1, replayed_par2, &new_merge_res);
 	replayed_bases = NULL; /* consumed by merge_incore_recursive */
-- 
gitgitgadget
Previous: Philippe BlainNext: Johannes Schindelin via GitGitGadget
Message 10 of 19 in “replay: support replaying 2-parent merges”
  1. 0/5 replay: support replaying 2-parent mergesJohannes Schindelin via GitGitGadget, May 6, 2026
  2. 1/5 replay: support replaying 2-parent mergesJohannes Schindelin via GitGitGadget, May 6, 2026
  3. Phillip WoodMay 8, 2026
  4. Phillip WoodMay 8, 2026
  5. Johannes SchindelinMay 17, 2026
  6. Johannes SchindelinMay 17, 2026
  7. Kristoffer HaugsbakkMay 26, 2026
  8. Philippe BlainNov 5, 2026
  9. Philippe BlainNov 13, 2026
  10. 2/5 replay: short-circuit merge replay when parent and base trees are unchangedJohannes Schindelin via GitGitGadget, May 6, 2026
  11. 3/5 history.adoc: describe merge-replay support and its limitsJohannes Schindelin via GitGitGadget, May 6, 2026
  12. 5/5 t3454: cover merge-replay scenarios with the historian helperJohannes Schindelin via GitGitGadget, May 6, 2026
  13. 4/5 test-tool: add a "historian" subcommand for building merge fixturesJohannes Schindelin via GitGitGadget, May 6, 2026
  14. Toon ClaesMay 12, 2026
  15. Johannes SchindelinMay 17, 2026
  16. D. Ben KnobleMay 7, 2026
  17. Johannes SchindelinMay 7, 2026
  18. Ben KnobleMay 7, 2026
  19. Johannes SchindelinMay 17, 2026

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.