[v2,2/2] ref-filter: allow merged and no-merged filters

Commit Message

Aaron Lipman Sept. 11, 2020, 6:57 p.m. UTC

Enable ref-filter to process multiple merged and no-merged filters, and
extend functionality to git branch, git tag and git for-each-ref. This
provides an easy way to check for branches that are "graduation
candidates:"

$ git branch --merged next --no-merged master

To accomplish this, store the merged and no-merged filters in two
commit_list structs (reachable_from and unreachable_from) rather than
using a single commit struct (merge_commit).

If passed more than one merged (or more than one no-merged) filter, refs
must be reachable from any one of the merged commits, and reachable from
none of the no-merged commits.

Signed-off-by: Aaron Lipman <[e-mail]>
---
 Documentation/git-branch.txt       |  6 +--
 Documentation/git-for-each-ref.txt |  6 +--
 Documentation/git-tag.txt          |  4 +-
 builtin/branch.c                   |  4 +-
 builtin/tag.c                      |  6 +--
 ref-filter.c                       | 71 ++++++++++++++++--------------
 ref-filter.h                       |  9 +---
 t/t3200-branch.sh                  |  4 +-
 t/t3201-branch-contains.sh         | 27 ++++++++++++
 t/t6302-for-each-ref-filter.sh     |  4 +-
 t/t7004-tag.sh                     |  2 +-
 11 files changed, 83 insertions(+), 60 deletions(-)

Comments

Junio C Hamano Sept. 11, 2020, 9:47 p.m. UTC | #1

Aaron Lipman <[e-mail]> writes:

> If passed more than one merged (or more than one no-merged) filter, refs
> must be reachable from any one of the merged commits, and reachable from
> none of the no-merged commits.

This mirrors how the "contains" behaves, which is good.

>  Documentation/git-branch.txt       |  6 +--
>  Documentation/git-for-each-ref.txt |  6 +--
>  Documentation/git-tag.txt          |  4 +-

It is a bit sad that this only removes from documentation without
adding (the removal is because merged and no-merged are no longer
mutually exclusive).  There should be a new description on how it
behaves when both of them are given---the combination were impossible
so it was sufficient to say "they are incompatible", but now the user
needs to know how they interact with each other.

Perhaps --contains side can already be combined so they have
description we can borrow here?  I didn't look too carefully.

> diff --git a/ref-filter.c b/ref-filter.c
> index 110bcd741a..c04dca47d1 100644
> --- a/ref-filter.c
> +++ b/ref-filter.c
> @@ -2231,11 +2231,17 @@ void ref_array_clear(struct ref_array *array)
>  	}
>  }
>  
> -static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata)
> +static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata, int reachable)
>  {
> +	struct commit_list *check_reachable_list = reachable ?
> +		ref_cbdata->filter->reachable_from :
> +		ref_cbdata->filter->unreachable_from;
> +
> +	if (!check_reachable_list)
> +		return;
> +

We do not allow decl-after-statement.

>  	struct rev_info revs;
>  	int i, old_nr;
> -	struct ref_filter *filter = ref_cbdata->filter;
>  	struct ref_array *array = ref_cbdata->array;
>  	struct commit **to_clear = xcalloc(sizeof(struct commit *), array->nr);
>  
> @@ -2247,12 +2253,15 @@ static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata)
>  		to_clear[i] = item->commit;
>  	}
>  
> -	filter->merge_commit->object.flags |= UNINTERESTING;
> -	add_pending_object(&revs, &filter->merge_commit->object, "");
> +	for (struct commit_list *rl = check_reachable_list; rl; rl = rl->next) {
> +		struct commit *merge_commit = rl->item;
> +		merge_commit->object.flags |= UNINTERESTING;
> +		add_pending_object(&revs, &merge_commit->object, "");
> -	revs.limited = 1;
> -	if (prepare_revision_walk(&revs))
> -		die(_("revision walk setup failed"));
> +		revs.limited = 1;
> +		if (prepare_revision_walk(&revs))
> +			die(_("revision walk setup failed"));
> +	}

This looks wrong.  I would have expected, instead of placing the
single object to the pending queue, the loop places all the filter
objects in a queue, and then makes a limited revision walk just
once.  In general, each time after the code makes a call to
prepare_revision_walk() to perform a revision walk, before doing so
again, the object flags used for the walking must be cleared.  You
can tell that the original code structure follows the pattern.
Calling it inside a loop breaks the pattern a big time.

In any case, we mark the named commits as UNINTERESTING and walk
from them and the tips of (surviving) refs to see which refs are
reachable from _any_ of the named commits.  The original code is a
degenerated case of having only one named commit.

The idea of the original is when checking for "--merged", any ref
whose tip is reachable from the named commit is merged and should be
shown.  That extends naturally to multiple commits given to
"--merged"; any ref whose tip is reachable from one of the named
commits is selected.

For "--no-merged", any ref whose tip is reachable from the named
commit is merged and should be excluded.  That also extends to
multiple commits.  Any ref whose tip is reachable from one of the
"--no-merged" commit is rejected.

> @@ -2263,14 +2272,19 @@ static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata)
>  
>  		int is_merged = !!(commit->object.flags & UNINTERESTING);
>  
> -		if (is_merged == (filter->merge == REF_FILTER_MERGED_INCLUDE))
> +		if (is_merged == reachable)
>  			array->items[array->nr++] = array->items[i];
>  		else
>  			free_array_item(item);

So, in the original code, if the tip of the ref is reachable from
the given commit (i.e. painted UNINTERESTING), we keep it in the
array when looking for "--merged".  That corresponds to the case 
where reachable is true.  Similarly for the --no-merged case.

So the overall logic seems sound.  It's just the callsite of
prepare_revision_walk() which does the actual painting of the graph
looks wrong.

> @@ -2541,31 +2555,22 @@ int parse_opt_merge_filter(const struct option *opt, const char *arg, int unset)
>  {
>  	struct ref_filter *rf = opt->value;
>  	struct object_id oid;
> -	int no_merged = starts_with(opt->long_name, "no");
>  
>  	BUG_ON_OPT_NEG(unset);
>  
> -	if (rf->merge) {
> -		if (no_merged) {
> -			return error(_("option `%s' is incompatible with --merged"),
> -				     opt->long_name);
> -		} else {
> -			return error(_("option `%s' is incompatible with --no-merged"),
> -				     opt->long_name);
> -		}
> -	}
> -
> -	rf->merge = no_merged
> -		? REF_FILTER_MERGED_OMIT
> -		: REF_FILTER_MERGED_INCLUDE;
> -
>  	if (get_oid(arg, &oid))
>  		die(_("malformed object name %s"), arg);
>  
> -	rf->merge_commit = lookup_commit_reference_gently(the_repository,
> -							  &oid, 0);
> -	if (!rf->merge_commit)
> +	struct commit *merge_commit = lookup_commit_reference_gently(the_repository,
> +								     &oid, 0);

decl-after-statement here, too.

> +	if (!merge_commit)
>  		return error(_("option `%s' must point to a commit"), opt->long_name);
>  
> +	if (starts_with(opt->long_name, "no"))
> +		commit_list_insert(merge_commit, &rf->unreachable_from);
> +	else
> +		commit_list_insert(merge_commit, &rf->reachable_from);
> +
>  	return 0;
>  }

Thanks.

Patch

diff --git a/Documentation/git-branch.txt b/Documentation/git-branch.txt
index 03c0824d52..8f0dbcd0ac 100644
--- a/Documentation/git-branch.txt
+++ b/Documentation/git-branch.txt
@@ -252,13 +252,11 @@  start-point is either a local or remote-tracking branch.
 
 --merged [<commit>]::
 	Only list branches whose tips are reachable from the
-	specified commit (HEAD if not specified). Implies `--list`,
-	incompatible with `--no-merged`.
+	specified commit (HEAD if not specified). Implies `--list`.
 
 --no-merged [<commit>]::
 	Only list branches whose tips are not reachable from the
-	specified commit (HEAD if not specified). Implies `--list`,
-	incompatible with `--merged`.
+	specified commit (HEAD if not specified). Implies `--list`.
 
 <branchname>::
 	The name of the branch to create or delete.
diff --git a/Documentation/git-for-each-ref.txt b/Documentation/git-for-each-ref.txt
index 616ce46087..f8322a7be2 100644
--- a/Documentation/git-for-each-ref.txt
+++ b/Documentation/git-for-each-ref.txt
@@ -76,13 +76,11 @@  OPTIONS
 
 --merged[=<object>]::
 	Only list refs whose tips are reachable from the
-	specified commit (HEAD if not specified),
-	incompatible with `--no-merged`.
+	specified commit (HEAD if not specified).
 
 --no-merged[=<object>]::
 	Only list refs whose tips are not reachable from the
-	specified commit (HEAD if not specified),
-	incompatible with `--merged`.
+	specified commit (HEAD if not specified).
 
 --contains[=<object>]::
 	Only list refs which contain the specified commit (HEAD if not
diff --git a/Documentation/git-tag.txt b/Documentation/git-tag.txt
index f6d9791780..786d4dfd6f 100644
--- a/Documentation/git-tag.txt
+++ b/Documentation/git-tag.txt
@@ -149,11 +149,11 @@  This option is only applicable when listing tags without annotation lines.
 
 --merged [<commit>]::
 	Only list tags whose commits are reachable from the specified
-	commit (`HEAD` if not specified), incompatible with `--no-merged`.
+	commit (`HEAD` if not specified).
 
 --no-merged [<commit>]::
 	Only list tags whose commits are not reachable from the specified
-	commit (`HEAD` if not specified), incompatible with `--merged`.
+	commit (`HEAD` if not specified).
 
 --points-at <object>::
 	Only list tags of the given object (HEAD if not
diff --git a/builtin/branch.c b/builtin/branch.c
index e82301fb1b..4bdb700dd5 100644
--- a/builtin/branch.c
+++ b/builtin/branch.c
@@ -688,8 +688,8 @@  int cmd_branch(int argc, const char **argv, const char *prefix)
 	    !show_current && !unset_upstream && argc == 0)
 		list = 1;
 
-	if (filter.with_commit || filter.merge != REF_FILTER_MERGED_NONE || filter.points_at.nr ||
-	    filter.no_commit)
+	if (filter.with_commit || filter.no_commit ||
+	    filter.reachable_from || filter.unreachable_from || filter.points_at.nr)
 		list = 1;
 
 	if (!!delete + !!rename + !!copy + !!new_upstream + !!show_current +
diff --git a/builtin/tag.c b/builtin/tag.c
index 5cbd80dc3e..b1a0398c85 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -457,8 +457,8 @@  int cmd_tag(int argc, const char **argv, const char *prefix)
 		if (argc == 0)
 			cmdmode = 'l';
 		else if (filter.with_commit || filter.no_commit ||
-			 filter.points_at.nr || filter.merge_commit ||
-			 filter.lines != -1)
+			 filter.reachable_from || filter.unreachable_from ||
+			 filter.points_at.nr || filter.lines != -1)
 			cmdmode = 'l';
 	}
 
@@ -509,7 +509,7 @@  int cmd_tag(int argc, const char **argv, const char *prefix)
 		die(_("--no-contains option is only allowed in list mode"));
 	if (filter.points_at.nr)
 		die(_("--points-at option is only allowed in list mode"));
-	if (filter.merge_commit)
+	if (filter.reachable_from || filter.unreachable_from)
 		die(_("--merged and --no-merged options are only allowed in list mode"));
 	if (cmdmode == 'd')
 		return for_each_tag_name(argv, delete_tag, NULL);
diff --git a/ref-filter.c b/ref-filter.c
index 110bcd741a..c04dca47d1 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -2167,9 +2167,9 @@  static int ref_filter_handler(const char *refname, const struct object_id *oid,
 	 * obtain the commit using the 'oid' available and discard all
 	 * non-commits early. The actual filtering is done later.
 	 */
-	if (filter->merge_commit || filter->with_commit || filter->no_commit || filter->verbose) {
-		commit = lookup_commit_reference_gently(the_repository, oid,
-							1);
+	if (filter->reachable_from || filter->unreachable_from ||
+	    filter->with_commit || filter->no_commit || filter->verbose) {
+		commit = lookup_commit_reference_gently(the_repository, oid, 1);
 		if (!commit)
 			return 0;
 		/* We perform the filtering for the '--contains' option... */
@@ -2231,11 +2231,17 @@  void ref_array_clear(struct ref_array *array)
 	}
 }
 
-static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata)
+static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata, int reachable)
 {
+	struct commit_list *check_reachable_list = reachable ?
+		ref_cbdata->filter->reachable_from :
+		ref_cbdata->filter->unreachable_from;
+
+	if (!check_reachable_list)
+		return;
+
 	struct rev_info revs;
 	int i, old_nr;
-	struct ref_filter *filter = ref_cbdata->filter;
 	struct ref_array *array = ref_cbdata->array;
 	struct commit **to_clear = xcalloc(sizeof(struct commit *), array->nr);
 
@@ -2247,12 +2253,15 @@  static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata)
 		to_clear[i] = item->commit;
 	}
 
-	filter->merge_commit->object.flags |= UNINTERESTING;
-	add_pending_object(&revs, &filter->merge_commit->object, "");
+	for (struct commit_list *rl = check_reachable_list; rl; rl = rl->next) {
+		struct commit *merge_commit = rl->item;
+		merge_commit->object.flags |= UNINTERESTING;
+		add_pending_object(&revs, &merge_commit->object, "");
 
-	revs.limited = 1;
-	if (prepare_revision_walk(&revs))
-		die(_("revision walk setup failed"));
+		revs.limited = 1;
+		if (prepare_revision_walk(&revs))
+			die(_("revision walk setup failed"));
+	}
 
 	old_nr = array->nr;
 	array->nr = 0;
@@ -2263,14 +2272,19 @@  static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata)
 
 		int is_merged = !!(commit->object.flags & UNINTERESTING);
 
-		if (is_merged == (filter->merge == REF_FILTER_MERGED_INCLUDE))
+		if (is_merged == reachable)
 			array->items[array->nr++] = array->items[i];
 		else
 			free_array_item(item);
-	}
+  }
 
 	clear_commit_marks_many(old_nr, to_clear, ALL_REV_FLAGS);
-	clear_commit_marks(filter->merge_commit, ALL_REV_FLAGS);
+
+	while (check_reachable_list) {
+		struct commit *merge_commit = pop_commit(&check_reachable_list);
+		clear_commit_marks(merge_commit, ALL_REV_FLAGS);
+	}
+
 	free(to_clear);
 }
 
@@ -2322,8 +2336,8 @@  int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int
 	clear_contains_cache(&ref_cbdata.no_contains_cache);
 
 	/*  Filters that need revision walking */
-	if (filter->merge_commit)
-		do_merge_filter(&ref_cbdata);
+	do_merge_filter(&ref_cbdata, 1);
+	do_merge_filter(&ref_cbdata, 0);
 
 	return ret;
 }
@@ -2541,31 +2555,22 @@  int parse_opt_merge_filter(const struct option *opt, const char *arg, int unset)
 {
 	struct ref_filter *rf = opt->value;
 	struct object_id oid;
-	int no_merged = starts_with(opt->long_name, "no");
 
 	BUG_ON_OPT_NEG(unset);
 
-	if (rf->merge) {
-		if (no_merged) {
-			return error(_("option `%s' is incompatible with --merged"),
-				     opt->long_name);
-		} else {
-			return error(_("option `%s' is incompatible with --no-merged"),
-				     opt->long_name);
-		}
-	}
-
-	rf->merge = no_merged
-		? REF_FILTER_MERGED_OMIT
-		: REF_FILTER_MERGED_INCLUDE;
-
 	if (get_oid(arg, &oid))
 		die(_("malformed object name %s"), arg);
 
-	rf->merge_commit = lookup_commit_reference_gently(the_repository,
-							  &oid, 0);
-	if (!rf->merge_commit)
+	struct commit *merge_commit = lookup_commit_reference_gently(the_repository,
+								     &oid, 0);
+
+	if (!merge_commit)
 		return error(_("option `%s' must point to a commit"), opt->long_name);
 
+	if (starts_with(opt->long_name, "no"))
+		commit_list_insert(merge_commit, &rf->unreachable_from);
+	else
+		commit_list_insert(merge_commit, &rf->reachable_from);
+
 	return 0;
 }
diff --git a/ref-filter.h b/ref-filter.h
index 8ecc33cdfa..feaef4a8fd 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -54,13 +54,8 @@  struct ref_filter {
 	struct oid_array points_at;
 	struct commit_list *with_commit;
 	struct commit_list *no_commit;
-
-	enum {
-		REF_FILTER_MERGED_NONE = 0,
-		REF_FILTER_MERGED_INCLUDE,
-		REF_FILTER_MERGED_OMIT
-	} merge;
-	struct commit *merge_commit;
+	struct commit_list *reachable_from;
+	struct commit_list *unreachable_from;
 
 	unsigned int with_commit_tag_algo : 1,
 		match_as_path : 1,
diff --git a/t/t3200-branch.sh b/t/t3200-branch.sh
index 028c88d1b2..be8f61b751 100755
--- a/t/t3200-branch.sh
+++ b/t/t3200-branch.sh
@@ -1299,8 +1299,8 @@  test_expect_success '--merged catches invalid object names' '
 	test_must_fail git branch --merged 0000000000000000000000000000000000000000
 '
 
-test_expect_success '--merged is incompatible with --no-merged' '
-	test_must_fail git branch --merged HEAD --no-merged HEAD
+test_expect_success '--merged is compatible with --no-merged' '
+	git branch --merged master --no-merged master
 '
 
 test_expect_success '--list during rebase' '
diff --git a/t/t3201-branch-contains.sh b/t/t3201-branch-contains.sh
index cd205b5560..d1ec594f6a 100755
--- a/t/t3201-branch-contains.sh
+++ b/t/t3201-branch-contains.sh
@@ -226,6 +226,16 @@  test_expect_success 'multiple branch --contains' '
 	test_cmp expect actual
 '
 
+test_expect_success 'multiple branch --merged' '
+	git branch --merged next --merged master >actual &&
+	cat >expect <<-\EOF &&
+	  feature_a
+	  master
+	* next
+	EOF
+	test_cmp expect actual
+'
+
 test_expect_success 'multiple branch --no-contains' '
 	git branch --no-contains feature_a --no-contains feature_b >actual &&
 	cat >expect <<-\EOF &&
@@ -234,6 +244,14 @@  test_expect_success 'multiple branch --no-contains' '
 	test_cmp expect actual
 '
 
+test_expect_success 'multiple branch --no-merged' '
+	git branch --no-merged next --no-merged master >actual &&
+	cat >expect <<-\EOF &&
+	  feature_b
+	EOF
+	test_cmp expect actual
+'
+
 test_expect_success 'branch --contains combined with --no-contains' '
 	git checkout master &&
 	git merge feature_a &&
@@ -247,4 +265,13 @@  test_expect_success 'branch --contains combined with --no-contains' '
 	test_cmp expect actual
 '
 
+test_expect_success 'branch --merged combined with --no-merged' '
+	git branch --merged next --no-merged master >actual &&
+	cat >expect <<-\EOF &&
+	  feature_b
+	* next
+	EOF
+	test_cmp expect actual
+'
+
 test_done
diff --git a/t/t6302-for-each-ref-filter.sh b/t/t6302-for-each-ref-filter.sh
index 35408d53fd..781e470aea 100755
--- a/t/t6302-for-each-ref-filter.sh
+++ b/t/t6302-for-each-ref-filter.sh
@@ -437,8 +437,8 @@  test_expect_success 'check %(if:notequals=<string>)' '
 	test_cmp expect actual
 '
 
-test_expect_success '--merged is incompatible with --no-merged' '
-	test_must_fail git for-each-ref --merged HEAD --no-merged HEAD
+test_expect_success '--merged is compatible with --no-merged' '
+	git for-each-ref --merged HEAD --no-merged HEAD
 '
 
 test_expect_success 'validate worktree atom' '
diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index 74b637deb2..7d544eceda 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -2016,7 +2016,7 @@  test_expect_success '--merged can be used in non-list mode' '
 '
 
 test_expect_success '--merged is incompatible with --no-merged' '
-	test_must_fail git tag --merged HEAD --no-merged HEAD
+	git tag --merged HEAD --no-merged HEAD
 '
 
 test_expect_success '--merged shows merged tags' '