[PATCH v4 0/6] log: speed up --follow following renames for non-linear history

[Miklos Vajna <vmiklos@collabora.com>]

Hi Patrick,

Thanks for the reviews of v3. Changes in v4:

- The -m --follow fix is now a separate patch (3/6), so the simplify
  patch (4/6) no longer changes behavior. The two bugs you pointed out
  in the old commit message have one cause: the followed path is not
  restored between the parents of a merge. So 3/6 fixes both. The
  commit message of 4/6 now says upfront that 304812ed33 (log: improve
  --follow following renames for non-linear history, 2026-06-22) caused
  a performance regression.

- Fixed the brace style nit in the simplify patch.

- Patch 6/6 fixes the case you found, where the speedup lost history:
  one side of the merge renamed the path, and the other side, whose
  version the merge dropped, edited the old name. It uses your test.
  I kept it separate from the speedup patch, which is complicated
  enough already. With the extra check, the linux.git case still takes
  about 37s.

- I also noticed that the simplify patch lost history with
  --diff-merges=first-parent, which diffs merges only against their
  first parent, but still walks all parents. Fixed that and added a
  test for it to 1/6.

Thanks,

Miklos

Miklos Vajna (6):
  t4219: test more --follow cases across merges
  log: extract showing the remerge/combined diff of a merge commit
  log: fix -m --follow losing the history of later parents
  log: simplify --follow following renames for non-linear history
  log: speed up --follow following renames for non-linear history
  log: fix --follow following an edit on a side the merge did not take

 log-tree.c                  | 265 +++++++++++++++++++++++++++++-------
 t/t4219-log-follow-merge.sh | 171 +++++++++++++++++++++++
 2 files changed, 388 insertions(+), 48 deletions(-)

Interdiff against v3:
diff --git a/log-tree.c b/log-tree.c
index d5ce58d91d..c2c3473f25 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -1111,15 +1111,20 @@ static void set_pathspec_to_single_path(struct pathspec *ps, const char *path)
 		       PATHSPEC_LITERAL_PATH, "", paths);
 }
 
-static int commit_has_path(struct rev_info *opt, struct commit *c,
-			   const char *path)
+static int tree_has_path(struct rev_info *opt, struct object_id *tree,
+			 const char *path)
 {
 	struct object_id oid;
 	unsigned short mode;
 
+	return !get_tree_entry(opt->diffopt.repo, tree, path, &oid, &mode);
+}
+
+static int commit_has_path(struct rev_info *opt, struct commit *c,
+			   const char *path)
+{
 	parse_commit_or_die(c);
-	return !get_tree_entry(opt->diffopt.repo, get_commit_tree_oid(c), path,
-			       &oid, &mode);
+	return tree_has_path(opt, get_commit_tree_oid(c), path);
 }
 
 static void remember_follow_pathspec(struct rev_info *opt,
@@ -1169,26 +1174,97 @@ void release_follow_pathspec_slab(struct rev_info *opt)
 	FREE_AND_NULL(opt->follow_pathspec_slab);
 }
 
+/*
+ * Did 'parent' change a file since 'base' that the merge (with tree 'oid') no
+ * longer has? Only such a file can be the source of a rename on the other side
+ * of the merge that still needs to be followed in 'parent'.
+ */
+static int follow_parent_changed_dropped_file(struct rev_info *opt,
+					      struct commit *base,
+					      struct commit *parent,
+					      struct object_id *oid)
+{
+	struct diff_options diff_opts;
+	int i, ret = 0;
+
+	repo_diff_setup(opt->diffopt.repo, &diff_opts);
+	diff_opts.flags.recursive = 1;
+	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
+	diff_setup_done(&diff_opts);
+	diff_tree_oid(get_commit_tree_oid(base), get_commit_tree_oid(parent),
+		      "", &diff_opts);
+	for (i = 0; i < diff_queued_diff.nr && !ret; i++) {
+		struct diff_filepair *p = diff_queued_diff.queue[i];
+
+		ret = DIFF_FILE_VALID(p->two) &&
+		      !tree_has_path(opt, oid, p->two->path);
+	}
+	diff_queue_clear(&diff_queued_diff);
+	diff_free(&diff_opts);
+	return ret;
+}
+
+/*
+ * Is 'path' in the merge (with tree 'oid') renamed from a file of 'parent'?
+ * Only look at the files that the merge deleted, not at all files of 'parent'
+ * like --follow does.
+ */
+static int follow_has_rename_source(struct rev_info *opt,
+				    struct commit *parent,
+				    struct object_id *oid, const char *path)
+{
+	struct diff_options diff_opts;
+	int i, ret = 0;
+
+	repo_diff_setup(opt->diffopt.repo, &diff_opts);
+	diff_opts.flags.recursive = 1;
+	diff_opts.detect_rename = DIFF_DETECT_RENAME;
+	diff_opts.rename_score = opt->diffopt.rename_score;
+	diff_opts.single_follow = path;
+	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
+	diff_setup_done(&diff_opts);
+	diff_tree_oid(get_commit_tree_oid(parent), oid, "", &diff_opts);
+	diffcore_std(&diff_opts);
+	for (i = 0; i < diff_queued_diff.nr && !ret; i++) {
+		struct diff_filepair *p = diff_queued_diff.queue[i];
+
+		ret = p->status == DIFF_STATUS_RENAMED &&
+		      !strcmp(p->two->path, path);
+	}
+	diff_queue_clear(&diff_queued_diff);
+	diff_free(&diff_opts);
+	return ret;
+}
+
 /*
  * When the path in a merge is the same as in 'same', does the path still need
  * renames to be followed in 'parent'? Only if the merge has the path, 'parent'
- * doesn't have it, but its fork point with 'same' had it, e.g. 'parent'
- * renamed the path.
+ * doesn't have it, and either:
+ *
+ * - its fork point with 'same' had it, e.g. 'parent' renamed the path, or
+ * - 'same' renamed the path from a file that 'parent' changed.
  */
 static int follow_needs_renames(struct rev_info *opt, struct commit *parent,
-				struct commit *same, const char *path)
+				struct commit *same, struct object_id *oid,
+				const char *path)
 {
 	struct commit_list *bases = NULL, *base;
-	int ret = 0;
+	int ret = 0, changed_dropped = 0;
 
 	if (commit_has_path(opt, parent, path) ||
 	    !commit_has_path(opt, same, path))
 		return 0;
 	if (repo_get_merge_bases(opt->diffopt.repo, parent, same, &bases) < 0)
 		exit(128);
-	for (base = bases; base && !ret; base = base->next)
+	for (base = bases; base && !ret; base = base->next) {
 		ret = commit_has_path(opt, base->item, path);
+		if (!ret && !changed_dropped)
+			changed_dropped = follow_parent_changed_dropped_file(
+				opt, base->item, parent, oid);
+	}
 	commit_list_free(bases);
+	if (!ret && changed_dropped)
+		ret = follow_has_rename_source(opt, parent, oid, path);
 	return ret;
 }
 
@@ -1295,8 +1371,9 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log
 			changed = diff_queued_diff.nr;
 			diff_queue_clear(&diff_queued_diff);
 			opt->diffopt.found_follow = 0;
-		} else
+		} else {
 			log_tree_diff_flush(opt);
+		}
 
 		showed_log |= !opt->loginfo;
 
@@ -1312,7 +1389,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log
 			     parents = parents->next) {
 				if (parents->item != parent &&
 				    follow_needs_renames(opt, parents->item,
-							 parent, path))
+							 parent, oid, path))
 					tail = &commit_list_insert(parents->item,
 								   tail)->next;
 				else
@@ -1340,8 +1417,15 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log
 			opt->diffopt.flags.follow_renames = 1;
 			parents = all_parents;
 		}
-		if (!parents || opt->first_parent_merges)
+		if (!parents)
 			break;
+		if (opt->first_parent_merges && !follow_only) {
+			if (!path || opt->first_parent_only)
+				break;
+			/* Only find the path to follow in the other parents */
+			follow_only = 1;
+			opt->diffopt.flags.follow_renames = 0;
+		}
 		if (path)
 			set_pathspec_to_single_path(&opt->diffopt.pathspec,
 						    path);
diff --git a/t/t4219-log-follow-merge.sh b/t/t4219-log-follow-merge.sh
index c8474ed151..a85fb78ca2 100755
--- a/t/t4219-log-follow-merge.sh
+++ b/t/t4219-log-follow-merge.sh
@@ -254,4 +254,47 @@ test_expect_success '--follow follows a rename on the side the merge did not tak
 	test_cmp expect actual
 '
 
+test_expect_success '--follow with --diff-merges=first-parent follows all parents' '
+	git -C keep log --follow --diff-merges=first-parent --no-patch \
+		--pretty=tformat:%s F >actual &&
+	cat >expect <<-\EOF &&
+	B2: update G
+	B1: rename F to G
+	A1: update F in place
+	O: add F
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'setup merge keeping the renamed path, other side edited the old one' '
+	git init keep-renamed &&
+	printf "line 1\nline 2\nline 3\nline 4\nline 5\n" >keep-renamed/F &&
+	git -C keep-renamed add F &&
+	test_tick &&
+	git -C keep-renamed commit -m "O: add F" &&
+	git -C keep-renamed branch B &&
+	git -C keep-renamed mv F G &&
+	test_tick &&
+	git -C keep-renamed commit -m "A1: rename F to G on master" &&
+
+	git -C keep-renamed checkout B &&
+	printf "line 1\nline 2\nline 3\nline 4 T\nline 5\n" >keep-renamed/F &&
+	test_tick &&
+	git -C keep-renamed commit -am "B2: update F on B" &&
+
+	git -C keep-renamed checkout master &&
+	test_tick &&
+	git -C keep-renamed merge -s ours -m "M: merge B, keep G, drop F" B
+'
+
+test_expect_success '--follow follows an edit on the side the merge did not take' '
+	git -C keep-renamed log --follow --pretty=tformat:%s G >actual &&
+	cat >expect <<-\EOF &&
+	B2: update F on B
+	A1: rename F to G on master
+	O: add F
+	EOF
+	test_cmp expect actual
+'
+
 test_done
-- 
2.56.0