[RFC PATCH 1/1] worktree list: add --merged and --no-merged

[Jasper Mayone <me@jaspermayone.com>]

Users who keep one worktree per topic have no direct way to find the
worktrees whose work has already landed. "git branch --merged" lists
the branches, but the user then has to match each branch to a
worktree by hand, and a detached worktree has no branch to match.
"git branch --delete-merged" skips any branch that is checked out in
a worktree, so these are exactly the branches it leaves behind.

Teach "git worktree list" the same --merged and --no-merged filters
that "git branch", "git tag" and "git for-each-ref" have, applied to
the HEAD of each worktree. The options are parsed by the same
OPT_MERGED and OPT_NO_MERGED helpers, so the default (the HEAD of the
current worktree), the error messages and the rules for combining
them are the same: a worktree is shown when its HEAD is reachable
from at least one of the --merged commits and from none of the
--no-merged commits.

A bare worktree, a worktree on an unborn branch, and a worktree whose
HEAD cannot be read have no HEAD commit, so the filters leave them
out. Both output formats are kept, so the result can be used directly
with "--porcelain -z":

    git worktree list --porcelain -z --merged origin/main

Nothing is removed. Removing the worktrees stays a separate step with
"git worktree remove", which already refuses a dirty or locked
worktree.

Signed-off-by: Jasper Mayone <me@jaspermayone.com>
---
 Documentation/git-worktree.adoc |  24 +++++-
 builtin/worktree.c              |  80 +++++++++++++++++++-
 t/t2402-worktree-list.sh        | 125 ++++++++++++++++++++++++++++++++
 3 files changed, 226 insertions(+), 3 deletions(-)

diff --git a/Documentation/git-worktree.adoc b/Documentation/git-worktree.adoc
index e6e77252ab..817766b07c 100644
--- a/Documentation/git-worktree.adoc
+++ b/Documentation/git-worktree.adoc
@@ -11,7 +11,7 @@ SYNOPSIS
 [synopsis]
 git worktree add [-f] [--detach] [--checkout] [--lock [--reason <string>]]
 		 [--orphan] [(-b | -B) <new-branch>] <path> [<commit-ish>]
-git worktree list [-v | --porcelain [-z]]
+git worktree list [-v | --porcelain [-z]] [--merged [<commit>]] [--no-merged [<commit>]]
 git worktree lock [--reason <string>] <worktree>
 git worktree move <worktree> <new-path>
 git worktree prune [-n] [-v] [--expire <expire>]
@@ -114,6 +114,11 @@ whether the worktree is bare, the revision currently checked out, the
 branch currently checked out (or "detached HEAD" if none), "locked" if
 the worktree is locked, "prunable" if the worktree can be pruned by the
 `prune` command.
++
+With `--merged` or `--no-merged`, only the worktrees whose `HEAD` is
+(or is not) reachable from the given commit are listed. This finds the
+worktrees whose work has landed, for example to remove them with
+`git worktree remove`.
 
 `lock`::
 
@@ -268,6 +273,23 @@ mismatch, even if the links are correct.
 	to parse the output when a worktree path contains a newline
 	character.
 
+`--merged [<commit>]`::
+	With `list`, only list worktrees whose `HEAD` is reachable from
+	_<commit>_. _<commit>_ defaults to the `HEAD` of the current
+	worktree.
+
+`--no-merged [<commit>]`::
+	With `list`, only list worktrees whose `HEAD` is not reachable
+	from _<commit>_. _<commit>_ defaults to the `HEAD` of the current
+	worktree.
++
+When `--merged` and `--no-merged` are combined or repeated, only
+worktrees whose `HEAD` is reachable from at least one of the
+`--merged` commits and from none of the `--no-merged` commits are
+listed. With either option, a bare worktree, a worktree on an unborn
+branch, and a worktree whose `HEAD` cannot be read are not listed,
+because they have no `HEAD` commit.
+
 `-q`::
 `--quiet`::
 	With `add`, suppress feedback messages.
diff --git a/builtin/worktree.c b/builtin/worktree.c
index 77ecd0f71f..5db9efb435 100644
--- a/builtin/worktree.c
+++ b/builtin/worktree.c
@@ -5,6 +5,7 @@
 #include "abspath.h"
 #include "advice.h"
 #include "checkout.h"
+#include "commit-reach.h"
 #include "config.h"
 #include "copy.h"
 #include "dir.h"
@@ -18,8 +19,10 @@
 #include "strvec.h"
 #include "branch.h"
 #include "read-cache-ll.h"
+#include "ref-filter.h"
 #include "refs.h"
 #include "remote.h"
+#include "revision.h"
 #include "run-command.h"
 #include "hook.h"
 #include "sigchain.h"
@@ -33,7 +36,7 @@
 	   "                 [--orphan] [(-b | -B) <new-branch>] <path> [<commit-ish>]")
 
 #define BUILTIN_WORKTREE_LIST_USAGE \
-	N_("git worktree list [-v | --porcelain [-z]]")
+	N_("git worktree list [-v | --porcelain [-z]] [--merged [<commit>]] [--no-merged [<commit>]]")
 #define BUILTIN_WORKTREE_LOCK_USAGE \
 	N_("git worktree lock [--reason <string>] <worktree>")
 #define BUILTIN_WORKTREE_MOVE_USAGE \
@@ -1125,11 +1128,78 @@ static void pathsort(struct worktree **wt)
 	QSORT(wt, n, pathcmp);
 }
 
+/*
+ * Set result[i] when tips[i] is reachable from one of the commits in
+ * "bases".
+ */
+static void mark_reachable(struct repository *repo,
+			   struct commit **tips, size_t nr,
+			   struct commit_list *bases, int *result)
+{
+	tips_reachable_from_bases(repo, bases, tips, nr, UNINTERESTING);
+	for (size_t i = 0; i < nr; i++)
+		result[i] = !!(tips[i]->object.flags & UNINTERESTING);
+	clear_commit_marks_many(nr, tips, ALL_REV_FLAGS);
+	for (; bases; bases = bases->next)
+		clear_commit_marks(bases->item, ALL_REV_FLAGS);
+}
+
+/*
+ * Keep only the worktrees whose HEAD is reachable from one of the
+ * "--merged" commits and from none of the "--no-merged" commits, like
+ * the ref filters of "git branch". A bare or unborn worktree has no
+ * HEAD commit, and neither has a broken one, so these are dropped.
+ */
+static void filter_merged(struct repository *repo, struct worktree **wt,
+			  struct ref_filter *filter)
+{
+	struct commit **tips = NULL;
+	int *merged, *unmerged;
+	size_t nr = 0, alloc = 0, kept = 0;
+
+	for (size_t i = 0; wt[i]; i++) {
+		struct commit *commit = NULL;
+
+		if (!wt[i]->is_bare && !is_null_oid(&wt[i]->head_oid))
+			commit = lookup_commit_reference_gently(repo,
+								&wt[i]->head_oid, 1);
+		if (!commit) {
+			free_worktree(wt[i]);
+			continue;
+		}
+		ALLOC_GROW(tips, nr + 1, alloc);
+		tips[nr] = commit;
+		wt[nr++] = wt[i];
+	}
+	wt[nr] = NULL;
+
+	CALLOC_ARRAY(merged, nr);
+	CALLOC_ARRAY(unmerged, nr);
+	if (filter->reachable_from)
+		mark_reachable(repo, tips, nr, filter->reachable_from, merged);
+	if (filter->unreachable_from)
+		mark_reachable(repo, tips, nr, filter->unreachable_from,
+			       unmerged);
+
+	for (size_t i = 0; i < nr; i++) {
+		if ((!filter->reachable_from || merged[i]) && !unmerged[i])
+			wt[kept++] = wt[i];
+		else
+			free_worktree(wt[i]);
+	}
+	wt[kept] = NULL;
+
+	free(tips);
+	free(merged);
+	free(unmerged);
+}
+
 static int list(int ac, const char **av, const char *prefix,
-		struct repository *repo UNUSED)
+		struct repository *repo)
 {
 	int porcelain = 0;
 	int line_terminator = '\n';
+	struct ref_filter filter = REF_FILTER_INIT;
 
 	struct option options[] = {
 		OPT_BOOL(0, "porcelain", &porcelain, N_("machine-readable output")),
@@ -1138,6 +1208,8 @@ static int list(int ac, const char **av, const char *prefix,
 				N_("add 'prunable' annotation to missing worktrees older than <time>")),
 		OPT_SET_INT('z', NULL, &line_terminator,
 			    N_("terminate records with a NUL character"), '\0'),
+		OPT_MERGED(&filter, N_("show only worktrees whose HEAD is merged")),
+		OPT_NO_MERGED(&filter, N_("show only worktrees whose HEAD is not merged")),
 		OPT_END()
 	};
 
@@ -1157,6 +1229,9 @@ static int list(int ac, const char **av, const char *prefix,
 		/* sort worktrees by path but keep main worktree at top */
 		pathsort(worktrees + 1);
 
+		if (filter.reachable_from || filter.unreachable_from)
+			filter_merged(repo, worktrees, &filter);
+
 		if (!porcelain)
 			measure_widths(worktrees, &abbrev,
 				       &display, &path_maxwidth);
@@ -1174,6 +1249,7 @@ static int list(int ac, const char **av, const char *prefix,
 		free(display);
 		free_worktrees(worktrees);
 	}
+	ref_filter_clear(&filter);
 	return 0;
 }
 
diff --git a/t/t2402-worktree-list.sh b/t/t2402-worktree-list.sh
index eeaf800d74..0e0e3d7f06 100755
--- a/t/t2402-worktree-list.sh
+++ b/t/t2402-worktree-list.sh
@@ -318,4 +318,129 @@ test_expect_success 'worktree path when called in .git directory' '
 	test_cmp list1 list2
 '
 
+test_expect_success 'setup for "list --merged"' '
+	git init merged &&
+	(
+		cd merged &&
+		test_commit base &&
+		git branch landed &&
+		git branch pending &&
+		git worktree add ../wt-landed landed &&
+		git worktree add ../wt-pending pending &&
+		git worktree add --detach ../wt-detached main &&
+		git -C ../wt-landed commit --allow-empty -m landed &&
+		git -C ../wt-pending commit --allow-empty -m pending &&
+		git merge --ff-only landed
+	)
+'
+
+list_paths () {
+	git -C merged worktree list --porcelain "$@" >out &&
+	sed -n "s/^worktree //p" out >actual
+}
+
+test_expect_success '"list --merged" shows only merged worktrees' '
+	list_paths --merged main &&
+	cat >expect <<-EOF &&
+	$(pwd)/merged
+	$(pwd)/wt-detached
+	$(pwd)/wt-landed
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_success '"list --merged" defaults to the current worktree HEAD' '
+	git -C wt-pending worktree list --porcelain --merged >out &&
+	sed -n "s/^worktree //p" out >actual &&
+	cat >expect <<-EOF &&
+	$(pwd)/wt-detached
+	$(pwd)/wt-pending
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_success '"list --no-merged" shows only unmerged worktrees' '
+	list_paths --no-merged main &&
+	echo "$(pwd)/wt-pending" >expect &&
+	test_cmp expect actual
+'
+
+test_expect_success '"list --merged" with several commits' '
+	list_paths --merged main --merged pending --no-merged base &&
+	cat >expect <<-EOF &&
+	$(pwd)/merged
+	$(pwd)/wt-landed
+	$(pwd)/wt-pending
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_success '"list --merged" keeps the normal output format' '
+	git -C merged worktree list --merged main >out &&
+	sed "s/  */ /g" <out >actual &&
+	cat >expect <<-EOF &&
+	$(pwd)/merged $(git -C merged rev-parse --short main) [main]
+	$(pwd)/wt-detached $(git -C merged rev-parse --short base) (detached HEAD)
+	$(pwd)/wt-landed $(git -C merged rev-parse --short landed) [landed]
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_success '"list --merged" rejects a bad commit' '
+	test_must_fail git -C merged worktree list --merged no-such-ref 2>err &&
+	test_grep "malformed object name" err &&
+	test_must_fail git -C merged worktree list --merged "main^{tree}" 2>err &&
+	test_grep "must point to a commit" err
+'
+
+test_expect_success '"list --merged" can list nothing' '
+	git -C merged worktree list --merged base --no-merged base >actual &&
+	test_must_be_empty actual
+'
+
+test_expect_success '"list --merged" works with -z' '
+	git -C merged worktree list --porcelain -z --no-merged main >out &&
+	tr "\0" "\n" <out >actual &&
+	cat >expect <<-EOF &&
+	worktree $(pwd)/wt-pending
+	HEAD $(git -C merged rev-parse pending)
+	branch refs/heads/pending
+
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_success '"list --merged" works with -v' '
+	test_when_finished "git -C merged worktree unlock wt-landed" &&
+	git -C merged worktree lock --reason "keep it" wt-landed &&
+	git -C merged worktree list -v --merged main >out &&
+	test_grep "^	locked: keep it" out
+'
+
+test_expect_success '"list --[no-]merged" omits unborn and broken worktrees' '
+	test_when_finished "rm -rf wt-unborn wt-broken && git -C merged worktree prune" &&
+	git -C merged worktree add --orphan -b unborn ../wt-unborn &&
+	git -C merged worktree add --detach ../wt-broken main &&
+	echo "$ZERO_OID" >merged/.git/worktrees/wt-broken/HEAD &&
+	git -C merged worktree list --porcelain >out &&
+	test_grep "^worktree $(pwd)/wt-unborn" out &&
+	test_grep "^worktree $(pwd)/wt-broken" out &&
+	git -C merged worktree list --porcelain --merged main >out &&
+	test_grep ! "wt-unborn" out &&
+	test_grep ! "wt-broken" out &&
+	git -C merged worktree list --porcelain --no-merged main >out &&
+	test_grep ! "wt-unborn" out &&
+	test_grep ! "wt-broken" out
+'
+
+test_expect_success '"list --merged" omits a bare main worktree' '
+	test_when_finished "rm -rf bare-merged there" &&
+	git clone --bare merged bare-merged &&
+	git -C bare-merged worktree add --detach ../there main &&
+	git -C bare-merged worktree list --porcelain --merged main >out &&
+	sed -n "s/^worktree //p" out >actual &&
+	git -C there rev-parse --show-toplevel >expect &&
+	test_cmp expect actual
+'
+
 test_done
-- 
2.56.0