[PATCH] branch: let --delete-merged find squash merged branches

[PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren via GitGitGadget]

From: Harald Nordgren <haraldnordgren@gmail.com>

Branches merged on GitHub with "Squash and merge" or "Rebase and
merge" are never deleted by "git branch --delete-merged". The upstream
holds a rewritten copy of their work, so their tips are not reachable
from it and they look unmerged forever.

Treat such a branch as merged when some upstream commit since the fork
point contains all of its changes, so that merging the branch into
that commit would change nothing. Name that commit in the output so
the user can see where the work went:

    Deleted branch topic (was 1a2b3c4, landed as 9f8e7d6).

The first upstream commit that contains the changes is used, so the
branch is deleted even if upstream later reverted or reworked them.
Nothing is lost, since that commit keeps them in the upstream history.
A branch whose changes only partly landed is kept.

Signed-off-by: Harald Nordgren <haraldnordgren@gmail.com>
---
    branch: let --delete-merged find squash merged branches
    
    Branches merged on GitHub with "Squash and merge" or "Rebase and merge"
    are never deleted by git branch --delete-merged, because their tips are
    not reachable from the upstream. This treats such a branch as merged
    when some upstream commit contains all of its changes, and names that
    commit in the output:
    
    Deleted branch topic (was 1a2b3c4, landed as 9f8e7d6).
    
    
    After the release of 2.56, I saw people liking the --delete-merged
    feature, but asking for this. A lot of people, me included prefer
    squash-merge and it currently doesn't work with --delete-merged.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2425%2FHaraldNordgren%2Fbranch-delete-squashed-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2425/HaraldNordgren/branch-delete-squashed-v1
Pull-Request: https://github.com/git/git/pull/2425

 Documentation/git-branch.adoc |  15 +--
 builtin/branch.c              | 183 ++++++++++++++++++++++++++++++++--
 t/t3200-branch.sh             |  74 ++++++++++++++
 3 files changed, 259 insertions(+), 13 deletions(-)

diff --git a/Documentation/git-branch.adoc b/Documentation/git-branch.adoc
index bfdf459329..0427324de1 100644
--- a/Documentation/git-branch.adoc
+++ b/Documentation/git-branch.adoc
@@ -204,12 +204,15 @@ This option is only applicable in non-verbose mode.
 
 `--delete-merged <pattern>`::
 	Delete local branches whose configured upstream matches
-	_<pattern>_, but only when their tip is reachable from that
-	upstream. In other words, the work on the branch has already
-	landed on the upstream it tracks, so the local copy is no longer
-	needed. _<pattern>_ may name a ref, a remote (using the branch its
-	`HEAD` points at), or a shell-style glob. The option can be
-	repeated to widen the upstream match.
+	_<pattern>_, but only when their work has already landed on that
+	upstream, so the local copy is no longer needed. This is the case
+	when their tip is reachable from the upstream, or when some
+	upstream commit contains all of their changes, as happens after
+	a squash or rebase merge, even if those changes were later
+	reverted. The message for such a branch names the first upstream
+	commit that contains its changes. _<pattern>_ may name a ref, a
+	remote (using the branch its `HEAD` points at), or a shell-style
+	glob. The option can be repeated to widen the upstream match.
 	Optional _<branch-pattern>_ arguments limit which local branches
 	are considered, e.g. `git branch --delete-merged 'origin/*'
 	'topic-*'`.
diff --git a/builtin/branch.c b/builtin/branch.c
index a613148fc7..982a8abe24 100644
--- a/builtin/branch.c
+++ b/builtin/branch.c
@@ -29,6 +29,13 @@
 #include "help.h"
 #include "advice.h"
 #include "commit-reach.h"
+#include "diff.h"
+#include "diffcore.h"
+#include "hex.h"
+#include "merge-ll.h"
+#include "revision.h"
+#include "tree-walk.h"
+#include "xdiff-interface.h"
 
 static const char * const builtin_branch_usage[] = {
 	N_("git branch [<options>] [-r | -a] [--merged] [--no-merged] [(--forked <branch>)...]"),
@@ -236,7 +243,7 @@ static void delete_branch_config(const char *branchname)
 }
 
 static int delete_branches(int argc, const char **argv, int kinds,
-			   unsigned int flags)
+			   unsigned int flags, struct strmap *landed_commits)
 {
 	struct commit *head_rev = NULL;
 	struct object_id oid;
@@ -334,6 +341,8 @@ static int delete_branches(int argc, const char **argv, int kinds,
 		}
 
 		if (!(ref_flags & (REF_ISSYMREF|REF_ISBROKEN)) &&
+		    !(landed_commits &&
+		      strmap_contains(landed_commits, bname.buf)) &&
 		    check_branch_commit(bname.buf, name, &oid, head_rev, kinds,
 					flags)) {
 			if (!(flags & DELETE_BRANCH_SKIP_UNMERGED))
@@ -357,15 +366,33 @@ static int delete_branches(int argc, const char **argv, int kinds,
 	for_each_string_list_item(item, &refs_to_delete) {
 		char *describe_ref = item->util;
 		char *name = item->string;
+		struct commit *landed = landed_commits ?
+			strmap_get(landed_commits, name + branch_name_pos) : NULL;
+		const char *landed_abbrev = landed ?
+			repo_find_unique_abbrev(the_repository,
+						&landed->object.oid,
+						DEFAULT_ABBREV) : NULL;
+
 		if (flags & DELETE_BRANCH_DRY_RUN) {
-			if (!(flags & DELETE_BRANCH_QUIET))
+			if (flags & DELETE_BRANCH_QUIET)
+				;
+			else if (landed)
+				printf(_("Would delete branch %s (was %s, landed as %s).\n"),
+				       name + branch_name_pos, describe_ref,
+				       landed_abbrev);
+			else
 				printf(remote_branch
 					? _("Would delete remote-tracking branch %s (was %s).\n")
 					: _("Would delete branch %s (was %s).\n"),
 					name + branch_name_pos, describe_ref);
 		} else if (!refs_ref_exists(get_main_ref_store(the_repository), name)) {
 			char *refname = name + branch_name_pos;
-			if (!(flags & DELETE_BRANCH_QUIET))
+			if (flags & DELETE_BRANCH_QUIET)
+				;
+			else if (landed)
+				printf(_("Deleted branch %s (was %s, landed as %s).\n"),
+				       refname, describe_ref, landed_abbrev);
+			else
 				printf(remote_branch
 					? _("Deleted remote-tracking branch %s (was %s).\n")
 					: _("Deleted branch %s (was %s).\n"),
@@ -824,6 +851,134 @@ static int branch_pushes_to_upstream(struct branch *branch,
 	return ret;
 }
 
+struct branch_change {
+	char *path;
+	struct object_id base_oid, branch_oid;
+	unsigned short branch_mode;
+};
+
+static void collect_branch_changes(struct commit *base, struct commit *rev,
+				   struct branch_change **changes,
+				   size_t *nr, size_t *alloc)
+{
+	struct diff_options opt;
+
+	repo_diff_setup(the_repository, &opt);
+	opt.flags.recursive = 1;
+	opt.output_format = DIFF_FORMAT_NO_OUTPUT;
+	diff_setup_done(&opt);
+	diff_tree_oid(get_commit_tree_oid(base), get_commit_tree_oid(rev),
+		      "", &opt);
+	for (int i = 0; i < diff_queued_diff.nr; i++) {
+		struct diff_filepair *p = diff_queued_diff.queue[i];
+		struct branch_change *change;
+
+		ALLOC_GROW(*changes, *nr + 1, *alloc);
+		change = &(*changes)[(*nr)++];
+		change->path = xstrdup(p->two->path);
+		oidcpy(&change->base_oid, DIFF_FILE_VALID(p->one) ?
+		       &p->one->oid : null_oid(the_hash_algo));
+		oidcpy(&change->branch_oid, DIFF_FILE_VALID(p->two) ?
+		       &p->two->oid : null_oid(the_hash_algo));
+		change->branch_mode = p->two->mode;
+	}
+	diff_flush(&opt);
+}
+
+static int merge_keeps_upstream(const struct branch_change *change,
+				const struct object_id *upstream_oid)
+{
+	mmfile_t base, upstream, branch;
+	mmbuffer_t result = { 0 };
+	int ret;
+
+	read_mmblob(&base, the_repository->objects, &change->base_oid);
+	read_mmblob(&upstream, the_repository->objects, upstream_oid);
+	read_mmblob(&branch, the_repository->objects, &change->branch_oid);
+	ret = ll_merge(&result, change->path, &base, "base",
+		       &upstream, "upstream", &branch, "branch",
+		       the_repository->index, NULL) == LL_MERGE_OK &&
+	      result.size == upstream.size &&
+	      !memcmp(result.ptr, upstream.ptr, upstream.size);
+
+	free(base.ptr);
+	free(upstream.ptr);
+	free(branch.ptr);
+	free(result.ptr);
+	return ret;
+}
+
+static int change_landed(const struct branch_change *change,
+			 struct commit *commit)
+{
+	struct object_id oid;
+	unsigned short mode;
+
+	if (get_tree_entry(the_repository, get_commit_tree_oid(commit),
+			   change->path, &oid, &mode))
+		return is_null_oid(&change->branch_oid);
+	if (oideq(&oid, &change->branch_oid))
+		return mode == change->branch_mode;
+	if (is_null_oid(&change->base_oid) ||
+	    is_null_oid(&change->branch_oid) ||
+	    oideq(&oid, &change->base_oid) ||
+	    mode != change->branch_mode || !S_ISREG(mode))
+		return 0;
+	return merge_keeps_upstream(change, &oid);
+}
+
+static struct commit *find_landed_commit(struct commit *rev,
+					 struct commit *upstream)
+{
+	struct commit_list *merge_bases = NULL;
+	struct branch_change *changes = NULL;
+	size_t changes_nr = 0, changes_alloc = 0;
+	struct commit *commit, *landed = NULL;
+	struct strvec args = STRVEC_INIT;
+	struct rev_info revs;
+
+	if (repo_get_merge_bases(the_repository, upstream, rev,
+				 &merge_bases) < 0)
+		exit(128);
+	if (!merge_bases)
+		return NULL;
+	collect_branch_changes(merge_bases->item, rev, &changes,
+			       &changes_nr, &changes_alloc);
+	commit_list_free(merge_bases);
+	if (!changes_nr)
+		return NULL;
+
+	strvec_pushl(&args, "rev-list", "--reverse",
+		     oid_to_hex(&upstream->object.oid), NULL);
+	strvec_pushf(&args, "^%s", oid_to_hex(&rev->object.oid));
+	strvec_push(&args, "--");
+	for (size_t i = 0; i < changes_nr; i++)
+		strvec_pushf(&args, ":(literal)%s", changes[i].path);
+
+	repo_init_revisions(the_repository, &revs, NULL);
+	setup_revisions_from_strvec(&args, &revs, NULL);
+	if (prepare_revision_walk(&revs))
+		die(_("revision walk setup failed"));
+	while (!landed && (commit = get_revision(&revs))) {
+		size_t i;
+
+		for (i = 0; i < changes_nr; i++)
+			if (!change_landed(&changes[i], commit))
+				break;
+		if (i == changes_nr)
+			landed = commit;
+	}
+	release_revisions(&revs);
+	clear_commit_marks(upstream, ALL_REV_FLAGS);
+	clear_commit_marks(rev, ALL_REV_FLAGS);
+	strvec_clear(&args);
+
+	for (size_t i = 0; i < changes_nr; i++)
+		free(changes[i].path);
+	free(changes);
+	return landed;
+}
+
 static int delete_merged_branches(const struct strvec *upstreams,
 				 const char **argv, unsigned int flags)
 {
@@ -832,6 +987,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
 	struct ref_array candidates = { 0 };
 	struct strset deletable_branch_names = STRSET_INIT;
 	struct strset protected_branch_names = STRSET_INIT;
+	struct strmap landed_commits = STRMAP_INIT;
 	struct strvec branches_to_delete = STRVEC_INIT;
 	struct strbuf key = STRBUF_INIT;
 	struct hashmap_iter iter;
@@ -852,6 +1008,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
 		const char *branch_name;
 		struct branch *branch;
 		const char *upstream_refname;
+		struct commit *landed = NULL;
 		int opt_out;
 
 		if (!skip_prefix(branch_refname, "refs/heads/", &branch_name))
@@ -867,8 +1024,17 @@ static int delete_merged_branches(const struct strvec *upstreams,
 			continue;
 		if (check_branch_commit(branch_name, branch_name,
 					&candidates.items[i]->objectname, NULL,
-					FILTER_REFS_BRANCHES, DELETE_BRANCH_SKIP_UNMERGED))
-			continue;
+					FILTER_REFS_BRANCHES,
+					DELETE_BRANCH_SKIP_UNMERGED)) {
+			struct commit *rev = lookup_commit_reference(
+				the_repository, &candidates.items[i]->objectname);
+			struct commit *upstream = lookup_commit_reference_by_name(
+				upstream_refname);
+
+			if (!rev || !upstream ||
+			    !(landed = find_landed_commit(rev, upstream)))
+				continue;
+		}
 
 		strbuf_reset(&key);
 		strbuf_addf(&key, "branch.%s.deletemerged", branch_name);
@@ -882,6 +1048,8 @@ static int delete_merged_branches(const struct strvec *upstreams,
 		}
 
 		strset_add(&deletable_branch_names, branch_name);
+		if (landed)
+			strmap_put(&landed_commits, branch_name, landed);
 	}
 
 	protect_stacked_branch_bases(refs, &deletable_branch_names,
@@ -895,7 +1063,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
 				      FILTER_REFS_BRANCHES,
 				      DELETE_BRANCH_SKIP_UNMERGED |
 				      DELETE_BRANCH_NO_HEAD_FALLBACK |
-				      flags);
+				      flags, &landed_commits);
 
 	if (!ret && !(flags & DELETE_BRANCH_DRY_RUN))
 		clear_deleted_upstreams(&protected_branch_names,
@@ -903,6 +1071,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
 
 	strbuf_release(&key);
 	strvec_clear(&branches_to_delete);
+	strmap_clear(&landed_commits, 0);
 	strset_clear(&protected_branch_names);
 	strset_clear(&deletable_branch_names);
 	ref_array_clear(&candidates);
@@ -1135,7 +1304,7 @@ int cmd_branch(int argc,
 			die(_("branch name required"));
 		ret = delete_branches(argc, argv, filter.kind,
 				      (delete > 1 ? DELETE_BRANCH_FORCE : 0) |
-				      (quiet ? DELETE_BRANCH_QUIET : 0));
+				      (quiet ? DELETE_BRANCH_QUIET : 0), NULL);
 		goto out;
 	} else if (delete_merged.nr) {
 		ret = delete_merged_branches(&delete_merged, argv,
diff --git a/t/t3200-branch.sh b/t/t3200-branch.sh
index cdb6c6a634..3b05718bab 100755
--- a/t/t3200-branch.sh
+++ b/t/t3200-branch.sh
@@ -1979,6 +1979,80 @@ test_expect_success '--delete-merged deletes only selected merged branches' '
 	)
 '
 
+push_topic () {
+	branch=$1 &&
+	shift &&
+	(
+		cd repo &&
+		git checkout -b "$branch" --track origin/next &&
+		for commit in "$@"
+		do
+			test_commit "$commit" || return 1
+		done &&
+		git push origin "$branch" &&
+		git checkout --detach
+	)
+}
+
+squash_merge_upstream () {
+	(
+		cd upstream &&
+		git checkout next &&
+		git merge --squash "$1" &&
+		git commit -m "Squash merge of $1" &&
+		git checkout main
+	)
+}
+
+test_expect_success '--delete-merged deletes a squash merged branch' '
+	setup_repo_for_delete_merged &&
+	push_topic squashed squashed-one squashed-two &&
+	push_topic partial partial-landed partial-pending &&
+	squash_merge_upstream partial~1 &&
+	squash_merge_upstream squashed &&
+	squash=$(git -C upstream rev-parse --short next) &&
+	(
+		cd repo &&
+		git fetch origin &&
+		sha=$(git rev-parse --short squashed) &&
+
+		git branch --delete-merged origin/next >actual 2>&1 &&
+		echo "Deleted branch squashed (was $sha, landed as $squash)." >expect &&
+		test_cmp expect actual &&
+
+		check_branches <<-\EOF
+		main
+		partial
+		EOF
+	)
+'
+
+test_expect_success '--delete-merged deletes a squash merged branch that was reverted' '
+	setup_repo_for_delete_merged &&
+	push_topic reverted reverted-work &&
+	squash_merge_upstream reverted &&
+	squash=$(git -C upstream rev-parse --short next) &&
+	(
+		cd upstream &&
+		git checkout next &&
+		git revert --no-edit HEAD &&
+		git checkout main
+	) &&
+	(
+		cd repo &&
+		git fetch origin &&
+		sha=$(git rev-parse --short reverted) &&
+
+		git branch --delete-merged origin/next >actual 2>&1 &&
+		echo "Deleted branch reverted (was $sha, landed as $squash)." >expect &&
+		test_cmp expect actual &&
+
+		check_branches <<-\EOF
+		main
+		EOF
+	)
+'
+
 test_expect_success '--delete-merged keeps main despite a different default push remote' '
 	setup_repo_for_delete_merged &&
 	create_merged_branch on-next &&

base-commit: a018953688f1b10bddf91bff8747068f5f4746a4
-- 
gitgitgadget

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Kristoffer Haugsbakk]

On Tue, Sep 29, 2026, at 09:30, Harald Nordgren via GitGitGadget wrote:
> From: Harald Nordgren <haraldnordgren@gmail.com>
>
> Branches merged on GitHub with "Squash and merge" or "Rebase and
> merge" are never deleted by "git branch --delete-merged". The upstream
> holds a rewritten copy of their work, so their tips are not reachable
> from it and they look unmerged forever.

An example closer to git(1)’s home:

    git merge --squash
    git commit

>[snip]

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren]

On Tue, Sep 29, 2026 at 9:47 AM Kristoffer Haugsbakk
<kristofferhaugsbakk@fastmail.com> wrote:
>
> On Tue, Sep 29, 2026, at 09:30, Harald Nordgren via GitGitGadget wrote:
> > From: Harald Nordgren <haraldnordgren@gmail.com>
> >
> > Branches merged on GitHub with "Squash and merge" or "Rebase and
> > merge" are never deleted by "git branch --delete-merged". The upstream
> > holds a rewritten copy of their work, so their tips are not reachable
> > from it and they look unmerged forever.
>
> An example closer to git(1)’s home:
>
>     git merge --squash
>     git commit

True. But likely it opens up the question of _why_ would anyone on
upstream be doing such destructive actions? Well, then the answer is
of course that millions of users (including) me do that via GitHub all
the time.

Maybe I should include both examples in my text.


Harald

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Kristoffer Haugsbakk]

On Tue, Sep 29, 2026, at 09:52, Harald Nordgren wrote:
> On Tue, Sep 29, 2026 at 9:47 AM Kristoffer Haugsbakk
> <kristofferhaugsbakk@fastmail.com> wrote:
>>
>> On Tue, Sep 29, 2026, at 09:30, Harald Nordgren via GitGitGadget wrote:
>> > From: Harald Nordgren <haraldnordgren@gmail.com>
>> >
>> > Branches merged on GitHub with "Squash and merge" or "Rebase and
>> > merge" are never deleted by "git branch --delete-merged". The upstream
>> > holds a rewritten copy of their work, so their tips are not reachable
>> > from it and they look unmerged forever.
>>
>> An example closer to git(1)’s home:
>>
>>     git merge --squash
>>     git commit
>
> True. But likely it opens up the question of _why_ would anyone on
> upstream be doing such destructive actions? Well, then the answer is
> of course that millions of users (including) me do that via GitHub all
> the time.
>
> Maybe I should include both examples in my text.

My *guess* is that `git merge --squash` inspired the forge squashes.
But the forges popularized it.

The apparent `git merge --squash` approach of using `git log` for
concatenating the commit messages isn’t that nice in my opinion. So I
wonder how much it is used.

Re: [PATCH] branch: let --delete-merged find squash merged branches

[D. Ben Knoble]

On Tue, Sep 29, 2026 at 4:17 AM Kristoffer Haugsbakk
<kristofferhaugsbakk@fastmail.com> wrote:
>
> On Tue, Sep 29, 2026, at 09:52, Harald Nordgren wrote:
> > On Tue, Sep 29, 2026 at 9:47 AM Kristoffer Haugsbakk
> > <kristofferhaugsbakk@fastmail.com> wrote:
> >>
> >> On Tue, Sep 29, 2026, at 09:30, Harald Nordgren via GitGitGadget wrote:
> >> > From: Harald Nordgren <haraldnordgren@gmail.com>
> >> >
> >> > Branches merged on GitHub with "Squash and merge" or "Rebase and
> >> > merge" are never deleted by "git branch --delete-merged". The upstream
> >> > holds a rewritten copy of their work, so their tips are not reachable
> >> > from it and they look unmerged forever.
> >>
> >> An example closer to git(1)’s home:
> >>
> >>     git merge --squash
> >>     git commit
> >
> > True. But likely it opens up the question of _why_ would anyone on
> > upstream be doing such destructive actions? Well, then the answer is
> > of course that millions of users (including) me do that via GitHub all
> > the time.
> >
> > Maybe I should include both examples in my text.
>
> My *guess* is that `git merge --squash` inspired the forge squashes.
> But the forges popularized it.
>
> The apparent `git merge --squash` approach of using `git log` for
> concatenating the commit messages isn’t that nice in my opinion. So I
> wonder how much it is used.

The same behavior is present in GitHub's default squash merge message,
and almost no one I work with bothers to edit it.

It's really sad to lose the opportunity to have good commit messages
when using squash-and-merge on a forge---not because we *cannot*, but
because the defaults do not *encourage* it (and we all know how
defaults affect user behavior!).

Anyway, see https://benknoble.github.io/blog/2024/08/02/github-squash/
for a distillation of my thoughts from working around folks that
squash carelessly.

So, anecdotally: it is used widely due to defaults. Blech.

-- 
D. Ben Knoble

Re: [PATCH] branch: let --delete-merged find squash merged branches

[D. Ben Knoble]

Without looking too much further…

On Tue, Sep 29, 2026 at 3:33 AM Harald Nordgren via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Harald Nordgren <haraldnordgren@gmail.com>
>
> Branches merged on GitHub with "Squash and merge" or "Rebase and
> merge" are never deleted by "git branch --delete-merged". The upstream
> holds a rewritten copy of their work, so their tips are not reachable
> from it and they look unmerged forever.
>
> Treat such a branch as merged when some upstream commit since the fork
> point contains all of its changes, so that merging the branch into
> that commit would change nothing. Name that commit in the output so
> the user can see where the work went:
>
>     Deleted branch topic (was 1a2b3c4, landed as 9f8e7d6).
>
> The first upstream commit that contains the changes is used, so the
> branch is deleted even if upstream later reverted or reworked them.
> Nothing is lost, since that commit keeps them in the upstream history.
> A branch whose changes only partly landed is kept.
>
> Signed-off-by: Harald Nordgren <haraldnordgren@gmail.com>

…in the rebase case, I would expect something like git-log's
--cherry-mark option (or really the algorithm behind it, git-cherry,
and git-range-diff) to be useful for identifying rebased branches. But
of course even rebase-merged branches can end up with minor
differences (say, a commit was made upstream before that branch was
rebased with an identical change; no conflict occurs, but the new
commit differs from the old by not having that change).

In the squash case, I suppose the best we can do is check that all our
changes were applied at some point between the merge-base and the tip.
There probably won't be any tree-same commits, though maybe a
(premature?) optimization can return early if the trees match exactly.

It looked like you don't distinguish the 2 cases in the code, and I
think that's reasonable: we wouldn't know a priori whether to check
for a rebased series or a squashed commit, so we'd have to run both
checks, and the latter presumably subsumes the former.

Anyway, I can see how this would all be fairly expensive---on one repo
I work in, git-range-diff can be somewhat slow depending on how many
commits are in the range, I think. I don't know if it's worth trying
to state that for folks, though? If we ever make improvements to
performance, we'd have to remember to remove the "this may be slow"
text.

> After the release of 2.56, I saw people liking the --delete-merged
>    feature, but asking for this. A lot of people, me included prefer
>    squash-merge and it currently doesn't work with --delete-merged.

Btw, I wonder if you can share where you saw this? 2.56 was released
so recently I'm (pleasantly) surprised there's already feedback on
this!

-- 
D. Ben Knoble

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Kristoffer Haugsbakk]

On Tue, Sep 29, 2026, at 13:18, D. Ben Knoble wrote:
> On Tue, Sep 29, 2026 at 4:17 AM Kristoffer Haugsbakk
> <kristofferhaugsbakk@fastmail.com> wrote:
>>
>> On Tue, Sep 29, 2026, at 09:52, Harald Nordgren wrote:
>> > [snip]
>> >
>> > Maybe I should include both examples in my text.
>>
>> My *guess* is that `git merge --squash` inspired the forge squashes.
>> But the forges popularized it.
>>
>> The apparent `git merge --squash` approach of using `git log` for
>> concatenating the commit messages isn’t that nice in my opinion. So I
>> wonder how much it is used.
>
> The same behavior is present in GitHub's default squash merge message,
> and almost no one I work with bothers to edit it.

The asterisk bullet points on GitHub are better than `git merge
--squash`:

    Squashed commit of the following:

    [just `git log` of the commits in the range]

> It's really sad to lose the opportunity to have good commit messages
> when using squash-and-merge on a forge---not because we *cannot*, but
> because the defaults do not *encourage* it (and we all know how
> defaults affect user behavior!).

In my opinion squash merges cannot be implemented in a good way, in a
way that leads to good commits. Fundamentally not. It’s the button to
both squash “oops” and the incremental, valuable commits, resulting in a
blob where even a manually written commit message cannot document all
the changes properly. And the reasons why are laid out in your article,
I think...

>
> Anyway, see https://benknoble.github.io/blog/2024/08/02/github-squash/
> for a distillation of my thoughts from working around folks that
> squash carelessly.
>
> So, anecdotally: it is used widely due to defaults. Blech.

Which is excellent. Thanks for writing it.

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren]

> > After the release of 2.56, I saw people liking the --delete-merged
> >    feature, but asking for this. A lot of people, me included prefer
> >    squash-merge and it currently doesn't work with --delete-merged.
>
> Btw, I wonder if you can share where you saw this? 2.56 was released
> so recently I'm (pleasantly) surprised there's already feedback on
> this!

Reddit thread: https://www.reddit.com/r/git/comments/1wsnrl9/comment/pcncf5t

There was only one person asking to clean up squashed branches. But I
also started thinking about it the other day, when 2.56 drew closer,
and I realized that friends that work in companies using squash merge
won't get any benefit from this.

Blog posts that is drawing attention to this new feature (not
necessary feedbacking on it):

- https://github.blog/open-source/git/highlights-from-git-2-56/
- https://about.gitlab.com/blog/whats-new-in-git-2-56-0/
- https://9to5linux.com/git-2-56-adds-new-options-for-cleaning-up-branches-and-resolving-conflicts
- https://linuxiac.com/git-2-56-released-with-safer-conflict-resolution-and-performance-gains/

Btw, I love squash merge!


Harald

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren]

> Anyway, I can see how this would all be fairly expensive---on one repo
> I work in, git-range-diff can be somewhat slow depending on how many
> commits are in the range, I think. I don't know if it's worth trying
> to state that for folks, though? If we ever make improvements to
> performance, we'd have to remember to remove the "this may be slow"
> text.

It was much slower in my first iterations, so running this on my local
Git repo now does not feel painfully slow. Although slower than
without this feature.

We might hide it behind a feature flag?


Harald

Re: [PATCH] branch: let --delete-merged find squash merged branches

[D. Ben Knoble]

On Tue, Sep 29, 2026 at 9:53 AM Harald Nordgren
<haraldnordgren@gmail.com> wrote:
>
> > Anyway, I can see how this would all be fairly expensive---on one repo
> > I work in, git-range-diff can be somewhat slow depending on how many
> > commits are in the range, I think. I don't know if it's worth trying
> > to state that for folks, though? If we ever make improvements to
> > performance, we'd have to remember to remove the "this may be slow"
> > text.
>
> It was much slower in my first iterations, so running this on my local
> Git repo now does not feel painfully slow. Although slower than
> without this feature.
>
> We might hide it behind a feature flag?

I could imagine wanting a CSV-style value for the option, like
"--delete-merged=squashed,rebased" vs. "--delete-merged=merged"
(current default), or something. But I'd have to think about whether
I'm suggesting that only to work around performance or to also support
actual use cases. Mostly I think people just want to go "gah, delete
merged branches" and not think about it further… hm.

-- 
D. Ben Knoble

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren]

> > We might hide it behind a feature flag?
>
> I could imagine wanting a CSV-style value for the option, like
> "--delete-merged=squashed,rebased" vs. "--delete-merged=merged"
> (current default), or something. But I'd have to think about whether
> I'm suggesting that only to work around performance or to also support
> actual use cases. Mostly I think people just want to go "gah, delete
> merged branches" and not think about it further… hm.

For me, the only reason to hide this would be for performance.

Yes, I think most people (me included) would rather have the simplest
possible command. I'd rather not have to specify the pattern so that
these are to the same:

    git branch --delete-merged
    git branch --delete-merged '*/*'


Harald

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Phillip Wood]

On 29/09/2026 12:26, D. Ben Knoble wrote:
> On Tue, Sep 29, 2026 at 3:33 AM Harald Nordgren via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
> 
> …in the rebase case, I would expect something like git-log's
> --cherry-mark option (or really the algorithm behind it, git-cherry,
> and git-range-diff) 

That's what I was expecting as well. It would be worth carefully 
studying the implementation of git-cherry. "git cherry A...B" 
precalculates the patch-ids from the side of the merge base that has the 
fewest commits and then walks the other side to compare them. While it 
is walking the other side I think it also looks at which paths were 
changed to avoid calculating the patch-id for commits that cannot match. 
It also batches fetches the blobs it needs in partial clones.

As far as I can see the implementation here makes a separate upstream 
revision walk for each branch, and recalculates the upstream diffs each 
time which seems less efficient than it could be.
> to be useful for identifying rebased branches. But
> of course even rebase-merged branches can end up with minor
> differences (say, a commit was made upstream before that branch was
> rebased with an identical change; no conflict occurs, but the new
> commit differs from the old by not having that change).

Yes if a branch has been rebased before it is merged it may be altered 
such that we cannot detect it.
> In the squash case, I suppose the best we can do is check that all our
> changes were applied at some point between the merge-base and the tip.
> There probably won't be any tree-same commits, though maybe a
> (premature?) optimization can return early if the trees match exactly.

If we have

(topic)  D - C - B - A
                       \
  (main)    M - Q - P - O -
             \          /
               - - S - -

where M is a squashed merge of topic I think we have

     M^2^{tree} == topic^{tree}
     Merge-base(M^1, M^2) == Merge-base(topic, topic@{upstream})
     $(git rev-list --count --right-only M^1...M^2) == 1

If you know your repository only has squash merges that were not rebased 
it would be a lot more efficient to just look at the trees and 
merge-bases, especially in a blobless clone. Having an option to turn 
off the patch-id based detection would probably be useful in that case.

I think detecting branches that have been squashed and/or rebased is a 
useful improvement, but it needs careful implementation to be efficient 
enough that it is practical in large repositories and I'm unlikely to 
have time to closely review it.

Thanks

Phillip

> It looked like you don't distinguish the 2 cases in the code, and I
> think that's reasonable: we wouldn't know a priori whether to check
> for a rebased series or a squashed commit, so we'd have to run both
> checks, and the latter presumably subsumes the former.
> 
> Anyway, I can see how this would all be fairly expensive---on one repo
> I work in, git-range-diff can be somewhat slow depending on how many
> commits are in the range, I think. I don't know if it's worth trying
> to state that for folks, though? If we ever make improvements to
> performance, we'd have to remember to remove the "this may be slow"
> text.
> 
>> After the release of 2.56, I saw people liking the --delete-merged
>>     feature, but asking for this. A lot of people, me included prefer
>>     squash-merge and it currently doesn't work with --delete-merged.
> 
> Btw, I wonder if you can share where you saw this? 2.56 was released
> so recently I'm (pleasantly) surprised there's already feedback on
> this!
> 

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren]

> As far as I can see the implementation here makes a separate upstream
> revision walk for each branch, and recalculates the upstream diffs each
> time which seems less efficient than it could be.

Yes, that can be improved!

> > In the squash case, I suppose the best we can do is check that all our
> > changes were applied at some point between the merge-base and the tip.
> > There probably won't be any tree-same commits, though maybe a
> > (premature?) optimization can return early if the trees match exactly.
...
> If you know your repository only has squash merges that were not rebased
> it would be a lot more efficient to just look at the trees and
> merge-bases, especially in a blobless clone. Having an option to turn
> off the patch-id based detection would probably be useful in that case.

Maybe yes, but for users I imagine they want the interface to be as
simple as possible.

I'm iterating on the code on my side (sharing logic between branches,
etc) and it became fast on my local Git repo. If there are no
performance concerns then would we still want the option to turn it
off?


Harald

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Phillip Wood]

Hi Harald

On 04/10/2026 23:28, Harald Nordgren wrote:
> ...
>> If you know your repository only has squash merges that were not rebased
>> it would be a lot more efficient to just look at the trees and
>> merge-bases, especially in a blobless clone. Having an option to turn
>> off the patch-id based detection would probably be useful in that case.
> 
> Maybe yes, but for users I imagine they want the interface to be as
> simple as possible.

Agreed, they also don't want to wait to find squashed merges they know 
they do not have.

> I'm iterating on the code on my side (sharing logic between branches,
> etc) and it became fast on my local Git repo. If there are no
> performance concerns then would we still want the option to turn it
> off?

Even an efficient implementation is going to be a lot slower when it is 
trying to find branches that have been squashed, so I think we probably 
do want a way to turn it off. That's especially true in partial clones 
where we'll have to download a bunch of blobs to do the squash 
detection. So long as it isn't diabolically slow enabling it by default 
is probably fine.

Thanks

Phillip

Re: [PATCH] branch: let --delete-merged find squash merged branches

[D. Ben Knoble]

On Sun, Oct 4, 2026 at 5:54 AM Phillip Wood <phillip.wood123@gmail.com> wrote:
>
> On 29/09/2026 12:26, D. Ben Knoble wrote:
> > On Tue, Sep 29, 2026 at 3:33 AM Harald Nordgren via GitGitGadget
> > <gitgitgadget@gmail.com> wrote:
> >
> > …in the rebase case, I would expect something like git-log's
> > --cherry-mark option (or really the algorithm behind it, git-cherry,
> > and git-range-diff)
>
> That's what I was expecting as well. It would be worth carefully
> studying the implementation of git-cherry. "git cherry A...B"
> precalculates the patch-ids from the side of the merge base that has the
> fewest commits and then walks the other side to compare them. While it
> is walking the other side I think it also looks at which paths were
> changed to avoid calculating the patch-id for commits that cannot match.
> It also batches fetches the blobs it needs in partial clones.
>
> As far as I can see the implementation here makes a separate upstream
> revision walk for each branch, and recalculates the upstream diffs each
> time which seems less efficient than it could be.

Thanks for spelling that out!

> > to be useful for identifying rebased branches. But
> > of course even rebase-merged branches can end up with minor
> > differences (say, a commit was made upstream before that branch was
> > rebased with an identical change; no conflict occurs, but the new
> > commit differs from the old by not having that change).
>
> Yes if a branch has been rebased before it is merged it may be altered
> such that we cannot detect it.

Yep. I'm not sure what Harald (or we) would want to do here.
git-range-diff has trouble detecting these scenarios today, so maybe
matching that and later finding a way to improve is ok.

> > In the squash case, I suppose the best we can do is check that all our
> > changes were applied at some point between the merge-base and the tip.
> > There probably won't be any tree-same commits, though maybe a
> > (premature?) optimization can return early if the trees match exactly.
>
> If we have
>
> (topic)  D - C - B - A
>                        \
>   (main)    M - Q - P - O -
>              \          /
>                - - S - -
>
> where M is a squashed merge of topic I think we have
>
>      M^2^{tree} == topic^{tree}
>      Merge-base(M^1, M^2) == Merge-base(topic, topic@{upstream})
>      $(git rev-list --count --right-only M^1...M^2) == 1

Perhaps we are thinking of 2 different things? In practice when I see
a merge created using GitHub's squash and merge option (and, I think,
also when using `merge --squash`), there is no second parent. You
could instead just get

    (main) S - Q - P - O

where S is A+B+C+D applied to Q (i.e., closer to a cherry-pick with
--no-commit).

And we know that S is not necessarily tree-same to topic's D, so…?

-- 
D. Ben Knoble

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren]

> Even an efficient implementation is going to be a lot slower when it is
> trying to find branches that have been squashed, so I think we probably
> do want a way to turn it off. That's especially true in partial clones
> where we'll have to download a bunch of blobs to do the squash
> detection. So long as it isn't diabolically slow enabling it by default
> is probably fine.

A bit slower (depends on how much!) could be worth it for improved
usability. This is not a command that users will run multiple times a
day.

I would hope we could have it on by default and add a flag to turn it
off instead.

For partial or shallow clones, we should probably warn the user that
detection won't be able to search the full history, and offer them to
unshallow, etc. It's very reasonable that some parts are turned off,
when the user doesn't want to hold the complete repo.



Harald

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Kristoffer Haugsbakk]

On Thu, Oct 8, 2026, at 20:42, Harald Nordgren wrote:
>> Even an efficient implementation is going to be a lot slower when it is
>> trying to find branches that have been squashed, so I think we probably
>> do want a way to turn it off. That's especially true in partial clones
>> where we'll have to download a bunch of blobs to do the squash
>> detection. So long as it isn't diabolically slow enabling it by default
>> is probably fine.
>
> A bit slower (depends on how much!) could be worth it for improved
> usability. This is not a command that users will run multiple times a
> day.

I would really like a solid delete operation that I can run, say,
overnight. I have better hygiene practices today but I didn’t back then,
so things have piled up.

One big cleanup is worth a nightly run. So I don’t care about how slow
it is.

>[snip]

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren]

On Fri, Oct 9, 2026 at 10:16 AM Kristoffer Haugsbakk
<kristofferhaugsbakk@fastmail.com> wrote:
>
> On Thu, Oct 8, 2026, at 20:42, Harald Nordgren wrote:
> >> Even an efficient implementation is going to be a lot slower when it is
> >> trying to find branches that have been squashed, so I think we probably
> >> do want a way to turn it off. That's especially true in partial clones
> >> where we'll have to download a bunch of blobs to do the squash
> >> detection. So long as it isn't diabolically slow enabling it by default
> >> is probably fine.
> >
> > A bit slower (depends on how much!) could be worth it for improved
> > usability. This is not a command that users will run multiple times a
> > day.
>
> I would really like a solid delete operation that I can run, say,
> overnight. I have better hygiene practices today but I didn’t back then,
> so things have piled up.
>
> One big cleanup is worth a nightly run. So I don’t care about how slow
> it is.

I would love to have a `full-clean` command that bundles
`deleted-merged` and all `prune` commands, and uses sensible defaults
for each one. (I have a hard time believing that it would need to run
overnight anyway).

I have known people who just delete the whole repo on any signs of
trouble. People out there are so scared of Git, so let's give them
sensible defaults to work with.


Harald

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren]

Interesting to note is that merged branches inside our repo change
when Junio signs off on them. So without this functionality they are
not cleaned either.


Harald

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Phillip Wood]

Hi Ben

On 08/10/2026 18:51, D. Ben Knoble wrote:
> On Sun, Oct 4, 2026 at 5:54 AM Phillip Wood <phillip.wood123@gmail.com> wrote:
>>
>> If we have
>>
>> (topic)  D - C - B - A
>>                         \
>>    (main)    M - Q - P - O -
>>               \          /
>>                 - - S - -
>>
>> where M is a squashed merge of topic I think we have
>>
>>       M^2^{tree} == topic^{tree}
>>       Merge-base(M^1, M^2) == Merge-base(topic, topic@{upstream})
>>       $(git rev-list --count --right-only M^1...M^2) == 1
> 
> Perhaps we are thinking of 2 different things? In practice when I see
> a merge created using GitHub's squash and merge option (and, I think,
> also when using `merge --squash`), there is no second parent. You
> could instead just get
> 
>      (main) S - Q - P - O
> 
> where S is A+B+C+D applied to Q (i.e., closer to a cherry-pick with
> --no-commit).

Oh, you're right, I'd misremembered how "merge --squash" worked.

> And we know that S is not necessarily tree-same to topic's D, so…?

I agree we need to use patch ids rather than trees in that case.

Thanks

Phillip

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Phillip Wood]

Hi Harald

On 08/10/2026 19:42, Harald Nordgren wrote:
>> Even an efficient implementation is going to be a lot slower when it is
>> trying to find branches that have been squashed, so I think we probably
>> do want a way to turn it off. That's especially true in partial clones
>> where we'll have to download a bunch of blobs to do the squash
>> detection. So long as it isn't diabolically slow enabling it by default
>> is probably fine.
> 
> A bit slower (depends on how much!) could be worth it for improved
> usability. This is not a command that users will run multiple times a
> day.
> 
> I would hope we could have it on by default and add a flag to turn it
> off instead.

That's my hope too

> For partial or shallow clones, we should probably warn the user that
> detection won't be able to search the full history, and offer them to
> unshallow, etc. It's very reasonable that some parts are turned off,
> when the user doesn't want to hold the complete repo.
I've not really though much about shallow clones, but for partial clones 
I think it is perfectly reasonable to go and fetch the blobs we need to 
calculate the patch ids and warn in the documentation that it can be slow.

Thanks

Phillip

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Phillip Wood]

Hi Harald

On 09/10/2026 12:18, Harald Nordgren wrote:
> Interesting to note is that merged branches inside our repo change
> when Junio signs off on them. So without this functionality they are
> not cleaned either.
That's true for a patched based workflow like the one on this list 
whether or not the maintainer signs off the commits. It is slightly 
different from the squash merge case because you need to look for the 
individual commits upstream, rather than the combined changes from the 
branch.

Thanks

Phillip

Re: [PATCH] branch: let --delete-merged find squash merged branches

[Harald Nordgren]

> I've not really though much about shallow clones, but for partial clones
> I think it is perfectly reasonable to go and fetch the blobs we need to
> calculate the patch ids and warn in the documentation that it can be slow.

Would you say the blobless case should be handled now, or can be left
as a follow-up topic?


Harald

[PATCH v2 0/2] branch: let --delete-merged find squash merged branches

[Harald Nordgren via GitGitGadget]

Branches merged on GitHub with "Squash and merge" or "Rebase and merge" are
never deleted by git branch --delete-merged, because their tips are not
reachable from the upstream. This treats such a branch as merged when some
upstream commit contains all of its changes, and names that commit in the
output:

Deleted branch topic (was 1a2b3c4, landed as 9f8e7d6).


Changes in v2:

 * Diff each upstream commit once and share the result between all branches,
   faster than v1.
 * Fix a branch merged with a merge commit being reported as "landed as" the
   merge when another branch was searched first, and add a test for it. Show
   the topic commit itself in "landed as" for work that arrived through a
   merge.
 * Use git merge --squash as the example in the commit message and mention
   GitHub's squash and rebase buttons.
 * Add --no-squashed to skip the squash search.

Harald Nordgren (2):
  branch: let --delete-merged find squash merged branches
  branch: add --no-squashed to skip the squash search

 Documentation/git-branch.adoc |  23 ++-
 builtin/branch.c              | 342 ++++++++++++++++++++++++++++++++--
 t/t3200-branch.sh             | 170 +++++++++++++++++
 3 files changed, 509 insertions(+), 26 deletions(-)


base-commit: 6de20f6092dcf9bdb1c8efe03db4b70c82b423dd
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2425%2FHaraldNordgren%2Fbranch-delete-squashed-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2425/HaraldNordgren/branch-delete-squashed-v2
Pull-Request: https://github.com/git/git/pull/2425

Range-diff vs v1:

 1:  c9ab56d8b2 ! 1:  94a6d23f8b branch: let --delete-merged find squash merged branches
     @@ Metadata
       ## Commit message ##
          branch: let --delete-merged find squash merged branches
      
     -    Branches merged on GitHub with "Squash and merge" or "Rebase and
     -    merge" are never deleted by "git branch --delete-merged". The upstream
     -    holds a rewritten copy of their work, so their tips are not reachable
     -    from it and they look unmerged forever.
     +    A branch that upstream integrated with
     +
     +        git merge --squash topic
     +        git commit
     +
     +    is never deleted by "git branch --delete-merged". The same goes for a
     +    branch that was rebased or cherry-picked onto upstream. The upstream
     +    holds a rewritten copy of its work, so its tip is not reachable from
     +    it and it looks unmerged forever.
     +
     +    This happens all the time on hosting services. The "Squash and merge"
     +    and "Rebase and merge" buttons on GitHub land pull requests this way,
     +    so contributors to such projects collect local branches that
     +    "--delete-merged" never cleans up.
      
          Treat such a branch as merged when some upstream commit since the fork
          point contains all of its changes, so that merging the branch into
     @@ builtin/branch.c
       #include "help.h"
       #include "advice.h"
       #include "commit-reach.h"
     ++#include "commit-slab.h"
      +#include "diff.h"
      +#include "diffcore.h"
      +#include "hex.h"
     @@ builtin/branch.c: static int branch_pushes_to_upstream(struct branch *branch,
       	return ret;
       }
       
     ++enum change_state {
     ++	CHANGE_MISSING,
     ++	CHANGE_LANDED,
     ++	CHANGE_NEEDS_MERGE,
     ++};
     ++
      +struct branch_change {
      +	char *path;
     -+	struct object_id base_oid, branch_oid;
     ++	struct object_id base_oid, branch_oid, upstream_oid;
      +	unsigned short branch_mode;
     ++	enum change_state state;
     ++};
     ++
     ++struct landing_search {
     ++	const char *branch_name;
     ++	struct commit *rev;
     ++	struct commit *upstream;
     ++	struct branch_change *changes;
     ++	size_t changes_nr, changes_alloc;
      +};
      +
     -+static void collect_branch_changes(struct commit *base, struct commit *rev,
     -+				   struct branch_change **changes,
     -+				   size_t *nr, size_t *alloc)
     ++define_commit_slab(changed_paths, struct string_list *);
     ++
     ++static void collect_branch_changes(struct landing_search *search,
     ++				   struct commit *base)
      +{
      +	struct diff_options opt;
      +
     @@ builtin/branch.c: static int branch_pushes_to_upstream(struct branch *branch,
      +	opt.flags.recursive = 1;
      +	opt.output_format = DIFF_FORMAT_NO_OUTPUT;
      +	diff_setup_done(&opt);
     -+	diff_tree_oid(get_commit_tree_oid(base), get_commit_tree_oid(rev),
     -+		      "", &opt);
     ++	diff_tree_oid(get_commit_tree_oid(base),
     ++		      get_commit_tree_oid(search->rev), "", &opt);
      +	for (int i = 0; i < diff_queued_diff.nr; i++) {
      +		struct diff_filepair *p = diff_queued_diff.queue[i];
      +		struct branch_change *change;
      +
     -+		ALLOC_GROW(*changes, *nr + 1, *alloc);
     -+		change = &(*changes)[(*nr)++];
     ++		ALLOC_GROW(search->changes, search->changes_nr + 1,
     ++			   search->changes_alloc);
     ++		change = &search->changes[search->changes_nr++];
      +		change->path = xstrdup(p->two->path);
      +		oidcpy(&change->base_oid, DIFF_FILE_VALID(p->one) ?
      +		       &p->one->oid : null_oid(the_hash_algo));
     @@ builtin/branch.c: static int branch_pushes_to_upstream(struct branch *branch,
      +	diff_flush(&opt);
      +}
      +
     -+static int merge_keeps_upstream(const struct branch_change *change,
     -+				const struct object_id *upstream_oid)
     ++static int merge_keeps_upstream(const struct branch_change *change)
      +{
      +	mmfile_t base, upstream, branch;
      +	mmbuffer_t result = { 0 };
      +	int ret;
      +
      +	read_mmblob(&base, the_repository->objects, &change->base_oid);
     -+	read_mmblob(&upstream, the_repository->objects, upstream_oid);
     ++	read_mmblob(&upstream, the_repository->objects, &change->upstream_oid);
      +	read_mmblob(&branch, the_repository->objects, &change->branch_oid);
      +	ret = ll_merge(&result, change->path, &base, "base",
      +		       &upstream, "upstream", &branch, "branch",
     @@ builtin/branch.c: static int branch_pushes_to_upstream(struct branch *branch,
      +	return ret;
      +}
      +
     -+static int change_landed(const struct branch_change *change,
     -+			 struct commit *commit)
     ++static enum change_state change_state_at(struct branch_change *change,
     ++					 struct commit *commit)
      +{
     -+	struct object_id oid;
      +	unsigned short mode;
      +
      +	if (get_tree_entry(the_repository, get_commit_tree_oid(commit),
     -+			   change->path, &oid, &mode))
     -+		return is_null_oid(&change->branch_oid);
     -+	if (oideq(&oid, &change->branch_oid))
     -+		return mode == change->branch_mode;
     ++			   change->path, &change->upstream_oid, &mode))
     ++		return is_null_oid(&change->branch_oid) ?
     ++			CHANGE_LANDED : CHANGE_MISSING;
     ++	if (oideq(&change->upstream_oid, &change->branch_oid))
     ++		return mode == change->branch_mode ?
     ++			CHANGE_LANDED : CHANGE_MISSING;
      +	if (is_null_oid(&change->base_oid) ||
      +	    is_null_oid(&change->branch_oid) ||
     -+	    oideq(&oid, &change->base_oid) ||
     ++	    oideq(&change->upstream_oid, &change->base_oid) ||
      +	    mode != change->branch_mode || !S_ISREG(mode))
     -+		return 0;
     -+	return merge_keeps_upstream(change, &oid);
     ++		return CHANGE_MISSING;
     ++	return CHANGE_NEEDS_MERGE;
      +}
      +
     -+static struct commit *find_landed_commit(struct commit *rev,
     -+					 struct commit *upstream)
     ++static int changes_landed(struct landing_search *search,
     ++			  struct commit *commit)
     ++{
     ++	for (size_t i = 0; i < search->changes_nr; i++) {
     ++		struct branch_change *change = &search->changes[i];
     ++
     ++		change->state = change_state_at(change, commit);
     ++		if (change->state == CHANGE_MISSING)
     ++			return 0;
     ++	}
     ++	for (size_t i = 0; i < search->changes_nr; i++) {
     ++		struct branch_change *change = &search->changes[i];
     ++
     ++		if (change->state == CHANGE_NEEDS_MERGE &&
     ++		    !merge_keeps_upstream(change))
     ++			return 0;
     ++	}
     ++	return 1;
     ++}
     ++
     ++static struct string_list *changed_paths_of(struct changed_paths *cache,
     ++					    struct diff_options *opt,
     ++					    struct commit *commit)
     ++{
     ++	struct string_list **paths = changed_paths_at(cache, commit);
     ++	struct commit *parent;
     ++
     ++	if (*paths)
     ++		return *paths;
     ++
     ++	CALLOC_ARRAY(*paths, 1);
     ++	string_list_init_dup(*paths);
     ++	parent = commit->parents ? commit->parents->item : NULL;
     ++	if (parent && repo_parse_commit(the_repository, parent))
     ++		die(_("could not parse commit %s"),
     ++		    oid_to_hex(&parent->object.oid));
     ++	diff_tree_oid(parent ? get_commit_tree_oid(parent) : NULL,
     ++		      get_commit_tree_oid(commit), "", opt);
     ++	for (int i = 0; i < diff_queued_diff.nr; i++) {
     ++		struct diff_filepair *p = diff_queued_diff.queue[i];
     ++
     ++		string_list_append(*paths, p->two->path);
     ++	}
     ++	diff_flush(opt);
     ++	string_list_sort(*paths);
     ++	return *paths;
     ++}
     ++
     ++static void free_changed_paths(struct string_list **paths)
     ++{
     ++	if (!*paths)
     ++		return;
     ++	string_list_clear(*paths, 0);
     ++	free(*paths);
     ++}
     ++
     ++static int touches_changes(struct string_list *paths,
     ++			   const struct landing_search *search)
     ++{
     ++	for (size_t i = 0; i < search->changes_nr; i++)
     ++		if (string_list_has_string(paths, search->changes[i].path))
     ++			return 1;
     ++	return 0;
     ++}
     ++
     ++static struct commit *find_landed_commit(struct landing_search *search,
     ++					 struct changed_paths *cache,
     ++					 struct diff_options *opt)
      +{
     -+	struct commit_list *merge_bases = NULL;
     -+	struct branch_change *changes = NULL;
     -+	size_t changes_nr = 0, changes_alloc = 0;
      +	struct commit *commit, *landed = NULL;
      +	struct strvec args = STRVEC_INIT;
      +	struct rev_info revs;
      +
     -+	if (repo_get_merge_bases(the_repository, upstream, rev,
     -+				 &merge_bases) < 0)
     -+		exit(128);
     -+	if (!merge_bases)
     -+		return NULL;
     -+	collect_branch_changes(merge_bases->item, rev, &changes,
     -+			       &changes_nr, &changes_alloc);
     -+	commit_list_free(merge_bases);
     -+	if (!changes_nr)
     -+		return NULL;
     -+
      +	strvec_pushl(&args, "rev-list", "--reverse",
     -+		     oid_to_hex(&upstream->object.oid), NULL);
     -+	strvec_pushf(&args, "^%s", oid_to_hex(&rev->object.oid));
     -+	strvec_push(&args, "--");
     -+	for (size_t i = 0; i < changes_nr; i++)
     -+		strvec_pushf(&args, ":(literal)%s", changes[i].path);
     ++		     oid_to_hex(&search->upstream->object.oid), NULL);
     ++	strvec_pushf(&args, "^%s", oid_to_hex(&search->rev->object.oid));
      +
      +	repo_init_revisions(the_repository, &revs, NULL);
      +	setup_revisions_from_strvec(&args, &revs, NULL);
      +	if (prepare_revision_walk(&revs))
      +		die(_("revision walk setup failed"));
     -+	while (!landed && (commit = get_revision(&revs))) {
     -+		size_t i;
     -+
     -+		for (i = 0; i < changes_nr; i++)
     -+			if (!change_landed(&changes[i], commit))
     -+				break;
     -+		if (i == changes_nr)
     ++	while (!landed && (commit = get_revision(&revs)))
     ++		if (touches_changes(changed_paths_of(cache, opt, commit),
     ++				    search) &&
     ++		    changes_landed(search, commit))
      +			landed = commit;
     -+	}
      +	release_revisions(&revs);
     -+	clear_commit_marks(upstream, ALL_REV_FLAGS);
     -+	clear_commit_marks(rev, ALL_REV_FLAGS);
     ++	clear_commit_marks(search->upstream, ALL_REV_FLAGS);
     ++	clear_commit_marks(search->rev, ALL_REV_FLAGS);
      +	strvec_clear(&args);
     -+
     -+	for (size_t i = 0; i < changes_nr; i++)
     -+		free(changes[i].path);
     -+	free(changes);
      +	return landed;
      +}
     ++
     ++static void find_landed_commits(struct landing_search *searches,
     ++				size_t searches_nr,
     ++				struct strmap *landed_commits)
     ++{
     ++	struct changed_paths cache;
     ++	struct diff_options opt;
     ++
     ++	for (size_t i = 0; i < searches_nr; i++) {
     ++		struct landing_search *search = &searches[i];
     ++		struct commit_list *merge_bases = NULL;
     ++
     ++		if (repo_get_merge_bases(the_repository, search->upstream,
     ++					 search->rev, &merge_bases) < 0)
     ++			exit(128);
     ++		if (merge_bases)
     ++			collect_branch_changes(search, merge_bases->item);
     ++		commit_list_free(merge_bases);
     ++	}
     ++
     ++	repo_diff_setup(the_repository, &opt);
     ++	opt.flags.recursive = 1;
     ++	opt.output_format = DIFF_FORMAT_NO_OUTPUT;
     ++	opt.no_free = 1;
     ++	diff_setup_done(&opt);
     ++	init_changed_paths(&cache);
     ++
     ++	for (size_t i = 0; i < searches_nr; i++) {
     ++		struct commit *landed;
     ++
     ++		if (!searches[i].changes_nr)
     ++			continue;
     ++		landed = find_landed_commit(&searches[i], &cache, &opt);
     ++		if (landed)
     ++			strmap_put(landed_commits, searches[i].branch_name,
     ++				   landed);
     ++	}
     ++
     ++	deep_clear_changed_paths(&cache, free_changed_paths);
     ++	opt.no_free = 0;
     ++	diff_free(&opt);
     ++}
     ++
     ++static int branch_opted_out(struct strbuf *key, const char *branch_name,
     ++			    unsigned int flags)
     ++{
     ++	int opt_out;
     ++
     ++	strbuf_reset(key);
     ++	strbuf_addf(key, "branch.%s.deletemerged", branch_name);
     ++	if (repo_config_get_bool(the_repository, key->buf, &opt_out) ||
     ++	    opt_out)
     ++		return 0;
     ++	if (!(flags & DELETE_BRANCH_QUIET))
     ++		fprintf(stderr,
     ++			_("Skipping '%s' (branch.%s.deleteMerged is false)\n"),
     ++			branch_name, branch_name);
     ++	return 1;
     ++}
      +
       static int delete_merged_branches(const struct strvec *upstreams,
       				 const char **argv, unsigned int flags)
     @@ builtin/branch.c: static int delete_merged_branches(const struct strvec *upstrea
       	struct strset deletable_branch_names = STRSET_INIT;
       	struct strset protected_branch_names = STRSET_INIT;
      +	struct strmap landed_commits = STRMAP_INIT;
     ++	struct landing_search *searches = NULL;
     ++	size_t searches_nr = 0, searches_alloc = 0;
       	struct strvec branches_to_delete = STRVEC_INIT;
       	struct strbuf key = STRBUF_INIT;
       	struct hashmap_iter iter;
     @@ builtin/branch.c: static int delete_merged_branches(const struct strvec *upstrea
       		const char *branch_name;
       		struct branch *branch;
       		const char *upstream_refname;
     -+		struct commit *landed = NULL;
     - 		int opt_out;
     +-		int opt_out;
       
       		if (!skip_prefix(branch_refname, "refs/heads/", &branch_name))
     + 			BUG("filter returned non-branch ref '%s'", branch_refname);
      @@ builtin/branch.c: static int delete_merged_branches(const struct strvec *upstreams,
       			continue;
       		if (check_branch_commit(branch_name, branch_name,
       					&candidates.items[i]->objectname, NULL,
      -					FILTER_REFS_BRANCHES, DELETE_BRANCH_SKIP_UNMERGED))
      -			continue;
     +-
     +-		strbuf_reset(&key);
     +-		strbuf_addf(&key, "branch.%s.deletemerged", branch_name);
     +-		if (!repo_config_get_bool(the_repository, key.buf, &opt_out) &&
     +-		    !opt_out) {
     +-			if (!(flags & DELETE_BRANCH_QUIET))
     +-				fprintf(stderr,
     +-					_("Skipping '%s' (branch.%s.deleteMerged is false)\n"),
     +-					branch_name, branch_name);
      +					FILTER_REFS_BRANCHES,
      +					DELETE_BRANCH_SKIP_UNMERGED)) {
      +			struct commit *rev = lookup_commit_reference(
     @@ builtin/branch.c: static int delete_merged_branches(const struct strvec *upstrea
      +			struct commit *upstream = lookup_commit_reference_by_name(
      +				upstream_refname);
      +
     -+			if (!rev || !upstream ||
     -+			    !(landed = find_landed_commit(rev, upstream)))
     ++			if (!rev || !upstream)
      +				continue;
     -+		}
     - 
     - 		strbuf_reset(&key);
     - 		strbuf_addf(&key, "branch.%s.deletemerged", branch_name);
     -@@ builtin/branch.c: static int delete_merged_branches(const struct strvec *upstreams,
     ++			ALLOC_GROW(searches, searches_nr + 1, searches_alloc);
     ++			searches[searches_nr++] = (struct landing_search) {
     ++				.branch_name = branch_name,
     ++				.rev = rev,
     ++				.upstream = upstream,
     ++			};
     + 			continue;
       		}
       
     - 		strset_add(&deletable_branch_names, branch_name);
     -+		if (landed)
     -+			strmap_put(&landed_commits, branch_name, landed);
     +-		strset_add(&deletable_branch_names, branch_name);
     ++		if (!branch_opted_out(&key, branch_name, flags))
     ++			strset_add(&deletable_branch_names, branch_name);
     ++	}
     ++
     ++	find_landed_commits(searches, searches_nr, &landed_commits);
     ++	for (size_t i = 0; i < searches_nr; i++) {
     ++		const char *branch_name = searches[i].branch_name;
     ++
     ++		if (strmap_contains(&landed_commits, branch_name) &&
     ++		    !branch_opted_out(&key, branch_name, flags))
     ++			strset_add(&deletable_branch_names, branch_name);
       	}
       
       	protect_stacked_branch_bases(refs, &deletable_branch_names,
     @@ builtin/branch.c: static int delete_merged_branches(const struct strvec *upstrea
       
       	strbuf_release(&key);
       	strvec_clear(&branches_to_delete);
     ++	for (size_t i = 0; i < searches_nr; i++) {
     ++		for (size_t j = 0; j < searches[i].changes_nr; j++)
     ++			free(searches[i].changes[j].path);
     ++		free(searches[i].changes);
     ++	}
     ++	free(searches);
      +	strmap_clear(&landed_commits, 0);
       	strset_clear(&protected_branch_names);
       	strset_clear(&deletable_branch_names);
     @@ t/t3200-branch.sh: test_expect_success '--delete-merged deletes only selected me
      +test_expect_success '--delete-merged deletes a squash merged branch' '
      +	setup_repo_for_delete_merged &&
      +	push_topic squashed squashed-one squashed-two &&
     -+	push_topic partial partial-landed partial-pending &&
     ++	push_topic partial lands-upstream stays-local &&
      +	squash_merge_upstream partial~1 &&
      +	squash_merge_upstream squashed &&
      +	squash=$(git -C upstream rev-parse --short next) &&
     @@ t/t3200-branch.sh: test_expect_success '--delete-merged deletes only selected me
      +		EOF
      +	)
      +'
     ++
     ++test_expect_success '--delete-merged deletes a squash merged branch after upstream changed the same file' '
     ++	(
     ++		cd upstream &&
     ++		git checkout next &&
     ++		test_write_lines 1 2 3 4 5 6 7 8 9 10 >shared &&
     ++		git add shared &&
     ++		git commit -m "add shared" &&
     ++		git checkout main
     ++	) &&
     ++	setup_repo_for_delete_merged &&
     ++	(
     ++		cd repo &&
     ++		git checkout -b edits-shared --track origin/next &&
     ++		test_write_lines 1 two 3 4 5 6 7 8 9 10 >shared &&
     ++		git commit -a -m "edit line 2" &&
     ++		git push origin edits-shared &&
     ++		git checkout --detach
     ++	) &&
     ++	(
     ++		cd upstream &&
     ++		git checkout next &&
     ++		test_write_lines 1 2 3 4 five 6 7 8 9 10 >shared &&
     ++		git commit -a -m "edit line 5" &&
     ++		git checkout main
     ++	) &&
     ++	squash_merge_upstream edits-shared &&
     ++	squash=$(git -C upstream rev-parse --short next) &&
     ++	(
     ++		cd repo &&
     ++		git fetch origin &&
     ++		sha=$(git rev-parse --short edits-shared) &&
     ++
     ++		git branch --delete-merged origin/next >actual 2>&1 &&
     ++		echo "Deleted branch edits-shared (was $sha, landed as $squash)." >expect &&
     ++		test_cmp expect actual &&
     ++
     ++		check_branches <<-\EOF
     ++		main
     ++		EOF
     ++	)
     ++'
     ++
     ++test_expect_success '--delete-merged reports a merge plainly next to an unmerged branch' '
     ++	setup_repo_for_delete_merged &&
     ++	push_topic a-unmerged unmerged-work &&
     ++	push_topic b-merged merged-work &&
     ++	(
     ++		cd upstream &&
     ++		git checkout next &&
     ++		test_commit upstream-work &&
     ++		git merge --no-ff b-merged &&
     ++		git checkout main
     ++	) &&
     ++	(
     ++		cd repo &&
     ++		git fetch origin &&
     ++		sha=$(git rev-parse --short b-merged) &&
     ++
     ++		git branch --delete-merged origin/next >actual 2>&1 &&
     ++		echo "Deleted branch b-merged (was $sha)." >expect &&
     ++		test_cmp expect actual &&
     ++
     ++		check_branches <<-\EOF
     ++		a-unmerged
     ++		main
     ++		EOF
     ++	)
     ++'
      +
       test_expect_success '--delete-merged keeps main despite a different default push remote' '
       	setup_repo_for_delete_merged &&
 -:  ---------- > 2:  ec88bde252 branch: add --no-squashed to skip the squash search

-- 
gitgitgadget

[PATCH v2 1/2] branch: let --delete-merged find squash merged branches

[Harald Nordgren via GitGitGadget]

From: Harald Nordgren <haraldnordgren@gmail.com>

A branch that upstream integrated with

    git merge --squash topic
    git commit

is never deleted by "git branch --delete-merged". The same goes for a
branch that was rebased or cherry-picked onto upstream. The upstream
holds a rewritten copy of its work, so its tip is not reachable from
it and it looks unmerged forever.

This happens all the time on hosting services. The "Squash and merge"
and "Rebase and merge" buttons on GitHub land pull requests this way,
so contributors to such projects collect local branches that
"--delete-merged" never cleans up.

Treat such a branch as merged when some upstream commit since the fork
point contains all of its changes, so that merging the branch into
that commit would change nothing. Name that commit in the output so
the user can see where the work went:

    Deleted branch topic (was 1a2b3c4, landed as 9f8e7d6).

The first upstream commit that contains the changes is used, so the
branch is deleted even if upstream later reverted or reworked them.
Nothing is lost, since that commit keeps them in the upstream history.
A branch whose changes only partly landed is kept.

Signed-off-by: Harald Nordgren <haraldnordgren@gmail.com>
---
 Documentation/git-branch.adoc |  15 +-
 builtin/branch.c              | 332 ++++++++++++++++++++++++++++++++--
 t/t3200-branch.sh             | 143 +++++++++++++++
 3 files changed, 466 insertions(+), 24 deletions(-)

diff --git a/Documentation/git-branch.adoc b/Documentation/git-branch.adoc
index bfdf459329..0427324de1 100644
--- a/Documentation/git-branch.adoc
+++ b/Documentation/git-branch.adoc
@@ -204,12 +204,15 @@ This option is only applicable in non-verbose mode.
 
 `--delete-merged <pattern>`::
 	Delete local branches whose configured upstream matches
-	_<pattern>_, but only when their tip is reachable from that
-	upstream. In other words, the work on the branch has already
-	landed on the upstream it tracks, so the local copy is no longer
-	needed. _<pattern>_ may name a ref, a remote (using the branch its
-	`HEAD` points at), or a shell-style glob. The option can be
-	repeated to widen the upstream match.
+	_<pattern>_, but only when their work has already landed on that
+	upstream, so the local copy is no longer needed. This is the case
+	when their tip is reachable from the upstream, or when some
+	upstream commit contains all of their changes, as happens after
+	a squash or rebase merge, even if those changes were later
+	reverted. The message for such a branch names the first upstream
+	commit that contains its changes. _<pattern>_ may name a ref, a
+	remote (using the branch its `HEAD` points at), or a shell-style
+	glob. The option can be repeated to widen the upstream match.
 	Optional _<branch-pattern>_ arguments limit which local branches
 	are considered, e.g. `git branch --delete-merged 'origin/*'
 	'topic-*'`.
diff --git a/builtin/branch.c b/builtin/branch.c
index a613148fc7..513c39763b 100644
--- a/builtin/branch.c
+++ b/builtin/branch.c
@@ -29,6 +29,14 @@
 #include "help.h"
 #include "advice.h"
 #include "commit-reach.h"
+#include "commit-slab.h"
+#include "diff.h"
+#include "diffcore.h"
+#include "hex.h"
+#include "merge-ll.h"
+#include "revision.h"
+#include "tree-walk.h"
+#include "xdiff-interface.h"
 
 static const char * const builtin_branch_usage[] = {
 	N_("git branch [<options>] [-r | -a] [--merged] [--no-merged] [(--forked <branch>)...]"),
@@ -236,7 +244,7 @@ static void delete_branch_config(const char *branchname)
 }
 
 static int delete_branches(int argc, const char **argv, int kinds,
-			   unsigned int flags)
+			   unsigned int flags, struct strmap *landed_commits)
 {
 	struct commit *head_rev = NULL;
 	struct object_id oid;
@@ -334,6 +342,8 @@ static int delete_branches(int argc, const char **argv, int kinds,
 		}
 
 		if (!(ref_flags & (REF_ISSYMREF|REF_ISBROKEN)) &&
+		    !(landed_commits &&
+		      strmap_contains(landed_commits, bname.buf)) &&
 		    check_branch_commit(bname.buf, name, &oid, head_rev, kinds,
 					flags)) {
 			if (!(flags & DELETE_BRANCH_SKIP_UNMERGED))
@@ -357,15 +367,33 @@ static int delete_branches(int argc, const char **argv, int kinds,
 	for_each_string_list_item(item, &refs_to_delete) {
 		char *describe_ref = item->util;
 		char *name = item->string;
+		struct commit *landed = landed_commits ?
+			strmap_get(landed_commits, name + branch_name_pos) : NULL;
+		const char *landed_abbrev = landed ?
+			repo_find_unique_abbrev(the_repository,
+						&landed->object.oid,
+						DEFAULT_ABBREV) : NULL;
+
 		if (flags & DELETE_BRANCH_DRY_RUN) {
-			if (!(flags & DELETE_BRANCH_QUIET))
+			if (flags & DELETE_BRANCH_QUIET)
+				;
+			else if (landed)
+				printf(_("Would delete branch %s (was %s, landed as %s).\n"),
+				       name + branch_name_pos, describe_ref,
+				       landed_abbrev);
+			else
 				printf(remote_branch
 					? _("Would delete remote-tracking branch %s (was %s).\n")
 					: _("Would delete branch %s (was %s).\n"),
 					name + branch_name_pos, describe_ref);
 		} else if (!refs_ref_exists(get_main_ref_store(the_repository), name)) {
 			char *refname = name + branch_name_pos;
-			if (!(flags & DELETE_BRANCH_QUIET))
+			if (flags & DELETE_BRANCH_QUIET)
+				;
+			else if (landed)
+				printf(_("Deleted branch %s (was %s, landed as %s).\n"),
+				       refname, describe_ref, landed_abbrev);
+			else
 				printf(remote_branch
 					? _("Deleted remote-tracking branch %s (was %s).\n")
 					: _("Deleted branch %s (was %s).\n"),
@@ -824,6 +852,251 @@ static int branch_pushes_to_upstream(struct branch *branch,
 	return ret;
 }
 
+enum change_state {
+	CHANGE_MISSING,
+	CHANGE_LANDED,
+	CHANGE_NEEDS_MERGE,
+};
+
+struct branch_change {
+	char *path;
+	struct object_id base_oid, branch_oid, upstream_oid;
+	unsigned short branch_mode;
+	enum change_state state;
+};
+
+struct landing_search {
+	const char *branch_name;
+	struct commit *rev;
+	struct commit *upstream;
+	struct branch_change *changes;
+	size_t changes_nr, changes_alloc;
+};
+
+define_commit_slab(changed_paths, struct string_list *);
+
+static void collect_branch_changes(struct landing_search *search,
+				   struct commit *base)
+{
+	struct diff_options opt;
+
+	repo_diff_setup(the_repository, &opt);
+	opt.flags.recursive = 1;
+	opt.output_format = DIFF_FORMAT_NO_OUTPUT;
+	diff_setup_done(&opt);
+	diff_tree_oid(get_commit_tree_oid(base),
+		      get_commit_tree_oid(search->rev), "", &opt);
+	for (int i = 0; i < diff_queued_diff.nr; i++) {
+		struct diff_filepair *p = diff_queued_diff.queue[i];
+		struct branch_change *change;
+
+		ALLOC_GROW(search->changes, search->changes_nr + 1,
+			   search->changes_alloc);
+		change = &search->changes[search->changes_nr++];
+		change->path = xstrdup(p->two->path);
+		oidcpy(&change->base_oid, DIFF_FILE_VALID(p->one) ?
+		       &p->one->oid : null_oid(the_hash_algo));
+		oidcpy(&change->branch_oid, DIFF_FILE_VALID(p->two) ?
+		       &p->two->oid : null_oid(the_hash_algo));
+		change->branch_mode = p->two->mode;
+	}
+	diff_flush(&opt);
+}
+
+static int merge_keeps_upstream(const struct branch_change *change)
+{
+	mmfile_t base, upstream, branch;
+	mmbuffer_t result = { 0 };
+	int ret;
+
+	read_mmblob(&base, the_repository->objects, &change->base_oid);
+	read_mmblob(&upstream, the_repository->objects, &change->upstream_oid);
+	read_mmblob(&branch, the_repository->objects, &change->branch_oid);
+	ret = ll_merge(&result, change->path, &base, "base",
+		       &upstream, "upstream", &branch, "branch",
+		       the_repository->index, NULL) == LL_MERGE_OK &&
+	      result.size == upstream.size &&
+	      !memcmp(result.ptr, upstream.ptr, upstream.size);
+
+	free(base.ptr);
+	free(upstream.ptr);
+	free(branch.ptr);
+	free(result.ptr);
+	return ret;
+}
+
+static enum change_state change_state_at(struct branch_change *change,
+					 struct commit *commit)
+{
+	unsigned short mode;
+
+	if (get_tree_entry(the_repository, get_commit_tree_oid(commit),
+			   change->path, &change->upstream_oid, &mode))
+		return is_null_oid(&change->branch_oid) ?
+			CHANGE_LANDED : CHANGE_MISSING;
+	if (oideq(&change->upstream_oid, &change->branch_oid))
+		return mode == change->branch_mode ?
+			CHANGE_LANDED : CHANGE_MISSING;
+	if (is_null_oid(&change->base_oid) ||
+	    is_null_oid(&change->branch_oid) ||
+	    oideq(&change->upstream_oid, &change->base_oid) ||
+	    mode != change->branch_mode || !S_ISREG(mode))
+		return CHANGE_MISSING;
+	return CHANGE_NEEDS_MERGE;
+}
+
+static int changes_landed(struct landing_search *search,
+			  struct commit *commit)
+{
+	for (size_t i = 0; i < search->changes_nr; i++) {
+		struct branch_change *change = &search->changes[i];
+
+		change->state = change_state_at(change, commit);
+		if (change->state == CHANGE_MISSING)
+			return 0;
+	}
+	for (size_t i = 0; i < search->changes_nr; i++) {
+		struct branch_change *change = &search->changes[i];
+
+		if (change->state == CHANGE_NEEDS_MERGE &&
+		    !merge_keeps_upstream(change))
+			return 0;
+	}
+	return 1;
+}
+
+static struct string_list *changed_paths_of(struct changed_paths *cache,
+					    struct diff_options *opt,
+					    struct commit *commit)
+{
+	struct string_list **paths = changed_paths_at(cache, commit);
+	struct commit *parent;
+
+	if (*paths)
+		return *paths;
+
+	CALLOC_ARRAY(*paths, 1);
+	string_list_init_dup(*paths);
+	parent = commit->parents ? commit->parents->item : NULL;
+	if (parent && repo_parse_commit(the_repository, parent))
+		die(_("could not parse commit %s"),
+		    oid_to_hex(&parent->object.oid));
+	diff_tree_oid(parent ? get_commit_tree_oid(parent) : NULL,
+		      get_commit_tree_oid(commit), "", opt);
+	for (int i = 0; i < diff_queued_diff.nr; i++) {
+		struct diff_filepair *p = diff_queued_diff.queue[i];
+
+		string_list_append(*paths, p->two->path);
+	}
+	diff_flush(opt);
+	string_list_sort(*paths);
+	return *paths;
+}
+
+static void free_changed_paths(struct string_list **paths)
+{
+	if (!*paths)
+		return;
+	string_list_clear(*paths, 0);
+	free(*paths);
+}
+
+static int touches_changes(struct string_list *paths,
+			   const struct landing_search *search)
+{
+	for (size_t i = 0; i < search->changes_nr; i++)
+		if (string_list_has_string(paths, search->changes[i].path))
+			return 1;
+	return 0;
+}
+
+static struct commit *find_landed_commit(struct landing_search *search,
+					 struct changed_paths *cache,
+					 struct diff_options *opt)
+{
+	struct commit *commit, *landed = NULL;
+	struct strvec args = STRVEC_INIT;
+	struct rev_info revs;
+
+	strvec_pushl(&args, "rev-list", "--reverse",
+		     oid_to_hex(&search->upstream->object.oid), NULL);
+	strvec_pushf(&args, "^%s", oid_to_hex(&search->rev->object.oid));
+
+	repo_init_revisions(the_repository, &revs, NULL);
+	setup_revisions_from_strvec(&args, &revs, NULL);
+	if (prepare_revision_walk(&revs))
+		die(_("revision walk setup failed"));
+	while (!landed && (commit = get_revision(&revs)))
+		if (touches_changes(changed_paths_of(cache, opt, commit),
+				    search) &&
+		    changes_landed(search, commit))
+			landed = commit;
+	release_revisions(&revs);
+	clear_commit_marks(search->upstream, ALL_REV_FLAGS);
+	clear_commit_marks(search->rev, ALL_REV_FLAGS);
+	strvec_clear(&args);
+	return landed;
+}
+
+static void find_landed_commits(struct landing_search *searches,
+				size_t searches_nr,
+				struct strmap *landed_commits)
+{
+	struct changed_paths cache;
+	struct diff_options opt;
+
+	for (size_t i = 0; i < searches_nr; i++) {
+		struct landing_search *search = &searches[i];
+		struct commit_list *merge_bases = NULL;
+
+		if (repo_get_merge_bases(the_repository, search->upstream,
+					 search->rev, &merge_bases) < 0)
+			exit(128);
+		if (merge_bases)
+			collect_branch_changes(search, merge_bases->item);
+		commit_list_free(merge_bases);
+	}
+
+	repo_diff_setup(the_repository, &opt);
+	opt.flags.recursive = 1;
+	opt.output_format = DIFF_FORMAT_NO_OUTPUT;
+	opt.no_free = 1;
+	diff_setup_done(&opt);
+	init_changed_paths(&cache);
+
+	for (size_t i = 0; i < searches_nr; i++) {
+		struct commit *landed;
+
+		if (!searches[i].changes_nr)
+			continue;
+		landed = find_landed_commit(&searches[i], &cache, &opt);
+		if (landed)
+			strmap_put(landed_commits, searches[i].branch_name,
+				   landed);
+	}
+
+	deep_clear_changed_paths(&cache, free_changed_paths);
+	opt.no_free = 0;
+	diff_free(&opt);
+}
+
+static int branch_opted_out(struct strbuf *key, const char *branch_name,
+			    unsigned int flags)
+{
+	int opt_out;
+
+	strbuf_reset(key);
+	strbuf_addf(key, "branch.%s.deletemerged", branch_name);
+	if (repo_config_get_bool(the_repository, key->buf, &opt_out) ||
+	    opt_out)
+		return 0;
+	if (!(flags & DELETE_BRANCH_QUIET))
+		fprintf(stderr,
+			_("Skipping '%s' (branch.%s.deleteMerged is false)\n"),
+			branch_name, branch_name);
+	return 1;
+}
+
 static int delete_merged_branches(const struct strvec *upstreams,
 				 const char **argv, unsigned int flags)
 {
@@ -832,6 +1105,9 @@ static int delete_merged_branches(const struct strvec *upstreams,
 	struct ref_array candidates = { 0 };
 	struct strset deletable_branch_names = STRSET_INIT;
 	struct strset protected_branch_names = STRSET_INIT;
+	struct strmap landed_commits = STRMAP_INIT;
+	struct landing_search *searches = NULL;
+	size_t searches_nr = 0, searches_alloc = 0;
 	struct strvec branches_to_delete = STRVEC_INIT;
 	struct strbuf key = STRBUF_INIT;
 	struct hashmap_iter iter;
@@ -852,7 +1128,6 @@ static int delete_merged_branches(const struct strvec *upstreams,
 		const char *branch_name;
 		struct branch *branch;
 		const char *upstream_refname;
-		int opt_out;
 
 		if (!skip_prefix(branch_refname, "refs/heads/", &branch_name))
 			BUG("filter returned non-branch ref '%s'", branch_refname);
@@ -867,21 +1142,35 @@ static int delete_merged_branches(const struct strvec *upstreams,
 			continue;
 		if (check_branch_commit(branch_name, branch_name,
 					&candidates.items[i]->objectname, NULL,
-					FILTER_REFS_BRANCHES, DELETE_BRANCH_SKIP_UNMERGED))
-			continue;
-
-		strbuf_reset(&key);
-		strbuf_addf(&key, "branch.%s.deletemerged", branch_name);
-		if (!repo_config_get_bool(the_repository, key.buf, &opt_out) &&
-		    !opt_out) {
-			if (!(flags & DELETE_BRANCH_QUIET))
-				fprintf(stderr,
-					_("Skipping '%s' (branch.%s.deleteMerged is false)\n"),
-					branch_name, branch_name);
+					FILTER_REFS_BRANCHES,
+					DELETE_BRANCH_SKIP_UNMERGED)) {
+			struct commit *rev = lookup_commit_reference(
+				the_repository, &candidates.items[i]->objectname);
+			struct commit *upstream = lookup_commit_reference_by_name(
+				upstream_refname);
+
+			if (!rev || !upstream)
+				continue;
+			ALLOC_GROW(searches, searches_nr + 1, searches_alloc);
+			searches[searches_nr++] = (struct landing_search) {
+				.branch_name = branch_name,
+				.rev = rev,
+				.upstream = upstream,
+			};
 			continue;
 		}
 
-		strset_add(&deletable_branch_names, branch_name);
+		if (!branch_opted_out(&key, branch_name, flags))
+			strset_add(&deletable_branch_names, branch_name);
+	}
+
+	find_landed_commits(searches, searches_nr, &landed_commits);
+	for (size_t i = 0; i < searches_nr; i++) {
+		const char *branch_name = searches[i].branch_name;
+
+		if (strmap_contains(&landed_commits, branch_name) &&
+		    !branch_opted_out(&key, branch_name, flags))
+			strset_add(&deletable_branch_names, branch_name);
 	}
 
 	protect_stacked_branch_bases(refs, &deletable_branch_names,
@@ -895,7 +1184,7 @@ static int delete_merged_branches(const struct strvec *upstreams,
 				      FILTER_REFS_BRANCHES,
 				      DELETE_BRANCH_SKIP_UNMERGED |
 				      DELETE_BRANCH_NO_HEAD_FALLBACK |
-				      flags);
+				      flags, &landed_commits);
 
 	if (!ret && !(flags & DELETE_BRANCH_DRY_RUN))
 		clear_deleted_upstreams(&protected_branch_names,
@@ -903,6 +1192,13 @@ static int delete_merged_branches(const struct strvec *upstreams,
 
 	strbuf_release(&key);
 	strvec_clear(&branches_to_delete);
+	for (size_t i = 0; i < searches_nr; i++) {
+		for (size_t j = 0; j < searches[i].changes_nr; j++)
+			free(searches[i].changes[j].path);
+		free(searches[i].changes);
+	}
+	free(searches);
+	strmap_clear(&landed_commits, 0);
 	strset_clear(&protected_branch_names);
 	strset_clear(&deletable_branch_names);
 	ref_array_clear(&candidates);
@@ -1135,7 +1431,7 @@ int cmd_branch(int argc,
 			die(_("branch name required"));
 		ret = delete_branches(argc, argv, filter.kind,
 				      (delete > 1 ? DELETE_BRANCH_FORCE : 0) |
-				      (quiet ? DELETE_BRANCH_QUIET : 0));
+				      (quiet ? DELETE_BRANCH_QUIET : 0), NULL);
 		goto out;
 	} else if (delete_merged.nr) {
 		ret = delete_merged_branches(&delete_merged, argv,
diff --git a/t/t3200-branch.sh b/t/t3200-branch.sh
index cdb6c6a634..adf1bc2233 100755
--- a/t/t3200-branch.sh
+++ b/t/t3200-branch.sh
@@ -1979,6 +1979,149 @@ test_expect_success '--delete-merged deletes only selected merged branches' '
 	)
 '
 
+push_topic () {
+	branch=$1 &&
+	shift &&
+	(
+		cd repo &&
+		git checkout -b "$branch" --track origin/next &&
+		for commit in "$@"
+		do
+			test_commit "$commit" || return 1
+		done &&
+		git push origin "$branch" &&
+		git checkout --detach
+	)
+}
+
+squash_merge_upstream () {
+	(
+		cd upstream &&
+		git checkout next &&
+		git merge --squash "$1" &&
+		git commit -m "Squash merge of $1" &&
+		git checkout main
+	)
+}
+
+test_expect_success '--delete-merged deletes a squash merged branch' '
+	setup_repo_for_delete_merged &&
+	push_topic squashed squashed-one squashed-two &&
+	push_topic partial lands-upstream stays-local &&
+	squash_merge_upstream partial~1 &&
+	squash_merge_upstream squashed &&
+	squash=$(git -C upstream rev-parse --short next) &&
+	(
+		cd repo &&
+		git fetch origin &&
+		sha=$(git rev-parse --short squashed) &&
+
+		git branch --delete-merged origin/next >actual 2>&1 &&
+		echo "Deleted branch squashed (was $sha, landed as $squash)." >expect &&
+		test_cmp expect actual &&
+
+		check_branches <<-\EOF
+		main
+		partial
+		EOF
+	)
+'
+
+test_expect_success '--delete-merged deletes a squash merged branch that was reverted' '
+	setup_repo_for_delete_merged &&
+	push_topic reverted reverted-work &&
+	squash_merge_upstream reverted &&
+	squash=$(git -C upstream rev-parse --short next) &&
+	(
+		cd upstream &&
+		git checkout next &&
+		git revert --no-edit HEAD &&
+		git checkout main
+	) &&
+	(
+		cd repo &&
+		git fetch origin &&
+		sha=$(git rev-parse --short reverted) &&
+
+		git branch --delete-merged origin/next >actual 2>&1 &&
+		echo "Deleted branch reverted (was $sha, landed as $squash)." >expect &&
+		test_cmp expect actual &&
+
+		check_branches <<-\EOF
+		main
+		EOF
+	)
+'
+
+test_expect_success '--delete-merged deletes a squash merged branch after upstream changed the same file' '
+	(
+		cd upstream &&
+		git checkout next &&
+		test_write_lines 1 2 3 4 5 6 7 8 9 10 >shared &&
+		git add shared &&
+		git commit -m "add shared" &&
+		git checkout main
+	) &&
+	setup_repo_for_delete_merged &&
+	(
+		cd repo &&
+		git checkout -b edits-shared --track origin/next &&
+		test_write_lines 1 two 3 4 5 6 7 8 9 10 >shared &&
+		git commit -a -m "edit line 2" &&
+		git push origin edits-shared &&
+		git checkout --detach
+	) &&
+	(
+		cd upstream &&
+		git checkout next &&
+		test_write_lines 1 2 3 4 five 6 7 8 9 10 >shared &&
+		git commit -a -m "edit line 5" &&
+		git checkout main
+	) &&
+	squash_merge_upstream edits-shared &&
+	squash=$(git -C upstream rev-parse --short next) &&
+	(
+		cd repo &&
+		git fetch origin &&
+		sha=$(git rev-parse --short edits-shared) &&
+
+		git branch --delete-merged origin/next >actual 2>&1 &&
+		echo "Deleted branch edits-shared (was $sha, landed as $squash)." >expect &&
+		test_cmp expect actual &&
+
+		check_branches <<-\EOF
+		main
+		EOF
+	)
+'
+
+test_expect_success '--delete-merged reports a merge plainly next to an unmerged branch' '
+	setup_repo_for_delete_merged &&
+	push_topic a-unmerged unmerged-work &&
+	push_topic b-merged merged-work &&
+	(
+		cd upstream &&
+		git checkout next &&
+		test_commit upstream-work &&
+		git merge --no-ff b-merged &&
+		git checkout main
+	) &&
+	(
+		cd repo &&
+		git fetch origin &&
+		sha=$(git rev-parse --short b-merged) &&
+
+		git branch --delete-merged origin/next >actual 2>&1 &&
+		echo "Deleted branch b-merged (was $sha)." >expect &&
+		test_cmp expect actual &&
+
+		check_branches <<-\EOF
+		a-unmerged
+		main
+		EOF
+	)
+'
+
 test_expect_success '--delete-merged keeps main despite a different default push remote' '
 	setup_repo_for_delete_merged &&
 	create_merged_branch on-next &&
-- 
gitgitgadget

[PATCH v2 2/2] branch: add --no-squashed to skip the squash search

[Harald Nordgren via GitGitGadget]

From: Harald Nordgren <haraldnordgren@gmail.com>

Finding branches that were squash or rebase merged makes "git branch
--delete-merged" slower, and in a partial clone it may have to
download blobs. Users who do not need it have no way to skip that
search.

Add --no-squashed, which only deletes branches whose tip is reachable
from their upstream.

Signed-off-by: Harald Nordgren <haraldnordgren@gmail.com>
---
 Documentation/git-branch.adoc |  8 +++++++-
 builtin/branch.c              | 12 ++++++++++--
 t/t3200-branch.sh             | 27 +++++++++++++++++++++++++++
 3 files changed, 44 insertions(+), 3 deletions(-)

diff --git a/Documentation/git-branch.adoc b/Documentation/git-branch.adoc
index 0427324de1..90960384c4 100644
--- a/Documentation/git-branch.adoc
+++ b/Documentation/git-branch.adoc
@@ -25,7 +25,7 @@ git branch (-m|-M) [<old-branch>] <new-branch>
 git branch (-c|-C) [<old-branch>] <new-branch>
 git branch (-d|-D) [-r] <branch-name>...
 git branch --edit-description [<branch-name>]
-git branch [--dry-run] (--delete-merged <pattern>)... [<branch-pattern>...]
+git branch [--dry-run] [--no-squashed] (--delete-merged <pattern>)... [<branch-pattern>...]
 
 DESCRIPTION
 -----------
@@ -244,6 +244,12 @@ remove it anyway.
 	sanity-checking a wide pattern like `'origin/*'` before
 	committing to the deletion.
 
+`--no-squashed`::
+	With `--delete-merged`, only delete branches whose tip is
+	reachable from their upstream. This skips the search for
+	branches that were squash or rebase merged, which takes longer
+	and may have to download blobs in a partial clone.
+
 `-v`::
 `-vv`::
 `--verbose`::
diff --git a/builtin/branch.c b/builtin/branch.c
index 513c39763b..96f10a7546 100644
--- a/builtin/branch.c
+++ b/builtin/branch.c
@@ -209,6 +209,7 @@ enum delete_branch_flags {
 	DELETE_BRANCH_SKIP_UNMERGED = (1 << 2),
 	DELETE_BRANCH_NO_HEAD_FALLBACK = (1 << 3),
 	DELETE_BRANCH_DRY_RUN = (1 << 4),
+	DELETE_BRANCH_NO_SQUASHED = (1 << 5),
 };
 
 static int check_branch_commit(const char *branchname, const char *refname,
@@ -1149,7 +1150,8 @@ static int delete_merged_branches(const struct strvec *upstreams,
 			struct commit *upstream = lookup_commit_reference_by_name(
 				upstream_refname);
 
-			if (!rev || !upstream)
+			if ((flags & DELETE_BRANCH_NO_SQUASHED) ||
+			    !rev || !upstream)
 				continue;
 			ALLOC_GROW(searches, searches_nr + 1, searches_alloc);
 			searches[searches_nr++] = (struct landing_search) {
@@ -1272,6 +1274,7 @@ int cmd_branch(int argc,
 	    unset_upstream = 0, show_current = 0, edit_description = 0;
 	struct strvec delete_merged = STRVEC_INIT;
 	int dry_run = 0;
+	int no_squashed = 0;
 	const char *new_upstream = NULL;
 	int noncreate_actions = 0;
 	/* possible options */
@@ -1330,6 +1333,8 @@ int cmd_branch(int argc,
 			PARSE_OPT_NONEG, parse_opt_strvec),
 		OPT_BOOL(0, "dry-run", &dry_run,
 			N_("with --delete-merged, only print which branches would be deleted")),
+		OPT_BOOL(0, "no-squashed", &no_squashed,
+			N_("with --delete-merged, skip the search for squash merged branches")),
 		OPT__FORCE(&force, N_("force creation, move/rename, deletion"), PARSE_OPT_NOCOMPLETE),
 		OPT_MERGED(&filter, N_("print only branches that are merged")),
 		OPT_NO_MERGED(&filter, N_("print only branches that are not merged")),
@@ -1394,6 +1399,8 @@ int cmd_branch(int argc,
 
 	if (dry_run && !delete_merged.nr)
 		die(_("--dry-run requires --delete-merged"));
+	if (no_squashed && !delete_merged.nr)
+		die(_("--no-squashed requires --delete-merged"));
 
 	if (recurse_submodules_explicit) {
 		if (!submodule_propagate_branches)
@@ -1436,7 +1443,8 @@ int cmd_branch(int argc,
 	} else if (delete_merged.nr) {
 		ret = delete_merged_branches(&delete_merged, argv,
 					     (quiet ? DELETE_BRANCH_QUIET : 0) |
-					     (dry_run ? DELETE_BRANCH_DRY_RUN : 0));
+					     (dry_run ? DELETE_BRANCH_DRY_RUN : 0) |
+					     (no_squashed ? DELETE_BRANCH_NO_SQUASHED : 0));
 		goto out;
 	} else if (show_current) {
 		print_current_branch_name();
diff --git a/t/t3200-branch.sh b/t/t3200-branch.sh
index adf1bc2233..70a38663f1 100755
--- a/t/t3200-branch.sh
+++ b/t/t3200-branch.sh
@@ -2095,6 +2095,28 @@ test_expect_success '--delete-merged deletes a squash merged branch after upstre
 	)
 '
 
+test_expect_success '--delete-merged --no-squashed deletes only reachable branches' '
+	setup_repo_for_delete_merged &&
+	create_merged_branch merged &&
+	push_topic squash-merged squash-merged-work &&
+	squash_merge_upstream squash-merged &&
+	(
+		cd repo &&
+		git fetch origin &&
+		sha=$(git rev-parse --short merged) &&
+
+		git branch --delete-merged origin/next --no-squashed \
+			>actual 2>&1 &&
+		echo "Deleted branch merged (was $sha)." >expect &&
+		test_cmp expect actual &&
+
+		check_branches <<-\EOF
+		main
+		squash-merged
+		EOF
+	)
+'
+
 test_expect_success '--delete-merged reports a merge plainly next to an unmerged branch' '
 	setup_repo_for_delete_merged &&
 	push_topic a-unmerged unmerged-work &&
@@ -2316,6 +2338,11 @@ test_expect_success "branch -d still deletes a deleteMerged=false branch" '
 	)
 '
 
+test_expect_success '--no-squashed without --delete-merged is rejected' '
+	test_must_fail git -C forked branch --no-squashed 2>err &&
+	test_grep "requires --delete-merged" err
+'
+
 test_expect_success '--dry-run without --delete-merged is rejected' '
 	test_must_fail git -C forked branch --dry-run 2>err &&
 	test_grep "requires --delete-merged" err
-- 
gitgitgadget