[PATCH v2 00/11] add options to for-each-ref

[PATCH v2 00/11] add options to for-each-ref

[karthik nayak]

This is continuation of the patch series 'Create ref-filter from for-each-ref'
found at : http://article.gmane.org/gmane.comp.version-control.git/271563

The previous version of this series can be found at :
http://www.mail-archive.com/git%40vger.kernel.org/msg70929.html

Changes made:
* Added tests
* Added comments to filter_refs()
* Small structural changes
* Various coding style fixes

Thanks to Junio C Hamano, Matthieu Moy, and Christian Couder for all
the suggestions.

-- 
Regards,
Karthik Nayak

[PATCH v2 01/11] t6301: for-each-ref tests for ref-filter APIs

[Karthik Nayak]

Add tests for for-each-ref which utilizes the ref-filter APIs.

Based-on-patch-by: Jeff King <peff@peff.net>
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 t/t6301-for-each-ref-filter.sh | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)
 create mode 100644 t/t6301-for-each-ref-filter.sh

diff --git a/t/t6301-for-each-ref-filter.sh b/t/t6301-for-each-ref-filter.sh
new file mode 100644
index 0000000..5bd49b3
--- /dev/null
+++ b/t/t6301-for-each-ref-filter.sh
@@ -0,0 +1,35 @@
+#!/bin/sh
+
+test_description='test for-each-refs usage of ref-filter APIs'
+
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/lib-gpg.sh
+
+test_expect_success 'setup some history and refs' '
+	test_commit one &&
+	test_commit two &&
+	test_commit three &&
+	git checkout -b side &&
+	test_commit four &&
+	git checkout master &&
+	git update-ref refs/odd/spot master
+'
+test_expect_success 'filtering by leading name' '
+	cat >expect <<-\EOF &&
+	refs/heads/master
+	refs/heads/side
+	EOF
+	git for-each-ref --format="%(refname)" refs/heads >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'filtering with fnmatch' '
+	cat >expect <<-\EOF &&
+	refs/tags/three
+	refs/tags/two
+	EOF
+	git for-each-ref --format="%(refname)" refs/tags/t* >actual &&
+	test_cmp expect actual
+'
+
+test_done
-- 
2.4.3.435.g2403634.dirty

[PATCH v2 02/11] tag: libify parse_opt_points_at()

[Karthik Nayak]

Rename 'parse_opt_points_at()' to 'parse_opt_object_name()' and
move it from 'tag.c' to 'parse-options'. This now acts as a common
parse_opt function which accepts an objectname and stores it into
a sha1_array.

Based-on-patch-by: Jeff King <peff@peff.net>
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 builtin/tag.c      | 21 ++-------------------
 parse-options-cb.c | 17 +++++++++++++++++
 parse-options.h    |  1 +
 3 files changed, 20 insertions(+), 19 deletions(-)

diff --git a/builtin/tag.c b/builtin/tag.c
index 5f6cdc5..e36c43e 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -546,23 +546,6 @@ static int strbuf_check_tag_ref(struct strbuf *sb, const char *name)
 	return check_refname_format(sb->buf, 0);
 }
 
-static int parse_opt_points_at(const struct option *opt __attribute__((unused)),
-			const char *arg, int unset)
-{
-	unsigned char sha1[20];
-
-	if (unset) {
-		sha1_array_clear(&points_at);
-		return 0;
-	}
-	if (!arg)
-		return error(_("switch 'points-at' requires an object"));
-	if (get_sha1(arg, sha1))
-		return error(_("malformed object name '%s'"), arg);
-	sha1_array_append(&points_at, sha1);
-	return 0;
-}
-
 static int parse_opt_sort(const struct option *opt, const char *arg, int unset)
 {
 	int *sort = opt->value;
@@ -625,8 +608,8 @@ int cmd_tag(int argc, const char **argv, const char *prefix)
 			parse_opt_with_commit, (intptr_t)"HEAD",
 		},
 		{
-			OPTION_CALLBACK, 0, "points-at", NULL, N_("object"),
-			N_("print only tags of the object"), 0, parse_opt_points_at
+			OPTION_CALLBACK, 0, "points-at", &points_at, N_("object"),
+			N_("print only tags of the object"), 0, parse_opt_object_name
 		},
 		OPT_END()
 	};
diff --git a/parse-options-cb.c b/parse-options-cb.c
index be8c413..de75411 100644
--- a/parse-options-cb.c
+++ b/parse-options-cb.c
@@ -4,6 +4,7 @@
 #include "commit.h"
 #include "color.h"
 #include "string-list.h"
+#include "sha1-array.h"
 
 /*----- some often used options -----*/
 
@@ -92,6 +93,22 @@ int parse_opt_with_commit(const struct option *opt, const char *arg, int unset)
 	return 0;
 }
 
+int parse_opt_object_name(const struct option *opt, const char *arg, int unset)
+{
+	unsigned char sha1[20];
+
+	if (unset) {
+		sha1_array_clear(opt->value);
+		return 0;
+	}
+	if (!arg)
+		return -1;
+	if (get_sha1(arg, sha1))
+		return error(_("malformed object name '%s'"), arg);
+	sha1_array_append(opt->value, sha1);
+	return 0;
+}
+
 int parse_opt_tertiary(const struct option *opt, const char *arg, int unset)
 {
 	int *target = opt->value;
diff --git a/parse-options.h b/parse-options.h
index c71e9da..36c71fe 100644
--- a/parse-options.h
+++ b/parse-options.h
@@ -220,6 +220,7 @@ extern int parse_opt_approxidate_cb(const struct option *, const char *, int);
 extern int parse_opt_expiry_date_cb(const struct option *, const char *, int);
 extern int parse_opt_color_flag_cb(const struct option *, const char *, int);
 extern int parse_opt_verbosity_cb(const struct option *, const char *, int);
+extern int parse_opt_object_name(const struct option *, const char *, int);
 extern int parse_opt_with_commit(const struct option *, const char *, int);
 extern int parse_opt_tertiary(const struct option *, const char *, int);
 extern int parse_opt_string_list(const struct option *, const char *, int);
-- 
2.4.3.435.g2403634.dirty

[PATCH v2 03/11] ref-filter: implement '--points-at' option

[Karthik Nayak]

In 'tag -l' we have '--points-at' option which lets users
list only tags which point to a particular commit. Implement
this option in 'ref-filter.{c,h}' so that other commands can
benefit from this.

This is duplicated from tag.c, we will eventually remove that
when we port tag.c to use ref-filter APIs.

Based-on-patch-by: Jeff King <peff@peff.net>
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 builtin/tag.c |  4 ++++
 ref-filter.c  | 26 ++++++++++++++++++++++++++
 ref-filter.h  |  1 +
 3 files changed, 31 insertions(+)

diff --git a/builtin/tag.c b/builtin/tag.c
index e36c43e..280981f 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -56,6 +56,10 @@ static int match_pattern(const char **patterns, const char *ref)
 	return 0;
 }
 
+/*
+ * This is currently duplicated in ref-filter.c, and will eventually be
+ * removed as we port tag.c to use the ref-filter APIs.
+ */
 static const unsigned char *match_points_at(const char *refname,
 					    const unsigned char *sha1)
 {
diff --git a/ref-filter.c b/ref-filter.c
index 43502a4..591e281 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -842,6 +842,29 @@ static int match_name_as_path(const char **pattern, const char *refname)
 	return 0;
 }
 
+/*
+ * Given a ref (sha1, refname) see if it points to a one of the sha1s
+ * in a sha1_array.
+ */
+static int match_points_at(struct sha1_array *points_at, const unsigned char *sha1,
+			   const char *refname)
+{
+	struct object *obj;
+
+	if (!points_at || !points_at->nr)
+		return 1;
+
+	if (sha1_array_lookup(points_at, sha1) >= 0)
+		return 1;
+
+	obj = parse_object_or_die(sha1, refname);
+	if (obj->type == OBJ_TAG &&
+	    sha1_array_lookup(points_at, ((struct tag *)obj)->tagged->sha1) >= 0)
+		return 1;
+
+	return 0;
+}
+
 /* Allocate space for a new ref_array_item and copy the objectname and flag to it */
 static struct ref_array_item *new_ref_array_item(const char *refname,
 						 const unsigned char *objectname,
@@ -875,6 +898,9 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,
 	if (*filter->name_patterns && !match_name_as_path(filter->name_patterns, refname))
 		return 0;
 
+	if (!match_points_at(&filter->points_at, oid->hash, refname))
+		return 0;
+
 	/*
 	 * We do not open the object yet; sort may only need refname
 	 * to do its job and the resulting list may yet to be pruned
diff --git a/ref-filter.h b/ref-filter.h
index 6997984..c2856b8 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -42,6 +42,7 @@ struct ref_array {
 
 struct ref_filter {
 	const char **name_patterns;
+	struct sha1_array points_at;
 };
 
 struct ref_filter_cbdata {
-- 
2.4.3.435.g2403634.dirty

[PATCH v2 04/11] for-each-ref: add '--points-at' option

[Karthik Nayak]

Add the '--points-at' option provided by 'ref-filter'. The
option lets the user to pick only refs which point to a particular
commit.

Add documentation and tests for the same.

Based-on-patch-by: Jeff King <peff@peff.net>
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 Documentation/git-for-each-ref.txt |  3 +++
 builtin/for-each-ref.c             |  9 +++++++--
 t/t6301-for-each-ref-filter.sh     | 10 ++++++++++
 3 files changed, 20 insertions(+), 2 deletions(-)

diff --git a/Documentation/git-for-each-ref.txt b/Documentation/git-for-each-ref.txt
index 7f8d9a5..0524ac4 100644
--- a/Documentation/git-for-each-ref.txt
+++ b/Documentation/git-for-each-ref.txt
@@ -10,6 +10,7 @@ SYNOPSIS
 [verse]
 'git for-each-ref' [--count=<count>] [--shell|--perl|--python|--tcl]
 		   [(--sort=<key>)...] [--format=<format>] [<pattern>...]
+		   [--points-at <object>]
 
 DESCRIPTION
 -----------
@@ -62,6 +63,8 @@ OPTIONS
 	the specified host language.  This is meant to produce
 	a scriptlet that can directly be `eval`ed.
 
+--points-at <object>::
+	Only list refs of the given object.
 
 FIELD NAMES
 -----------
diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
index 7919206..2dee149 100644
--- a/builtin/for-each-ref.c
+++ b/builtin/for-each-ref.c
@@ -7,6 +7,7 @@
 
 static char const * const for_each_ref_usage[] = {
 	N_("git for-each-ref [<options>] [<pattern>]"),
+	N_("git for-each-ref [--points-at <object>]"),
 	NULL
 };
 
@@ -34,9 +35,15 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 		OPT_STRING(  0 , "format", &format, N_("format"), N_("format to use for the output")),
 		OPT_CALLBACK(0 , "sort", sorting_tail, N_("key"),
 			    N_("field name to sort on"), &parse_opt_ref_sorting),
+		OPT_CALLBACK(0, "points-at", &filter.points_at,
+			     N_("object"), N_("print only refs of the object"),
+			     parse_opt_object_name),
 		OPT_END(),
 	};
 
+	memset(&array, 0, sizeof(array));
+	memset(&filter, 0, sizeof(filter));
+
 	parse_options(argc, argv, prefix, opts, for_each_ref_usage, 0);
 	if (maxcount < 0) {
 		error("invalid --count argument: `%d'", maxcount);
@@ -55,8 +62,6 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 	/* for warn_ambiguous_refs */
 	git_config(git_default_config, NULL);
 
-	memset(&array, 0, sizeof(array));
-	memset(&filter, 0, sizeof(filter));
 	filter.name_patterns = argv;
 	filter_refs(&array, &filter, FILTER_REFS_ALL | FILTER_REFS_INCLUDE_BROKEN);
 	ref_array_sort(sorting, &array);
diff --git a/t/t6301-for-each-ref-filter.sh b/t/t6301-for-each-ref-filter.sh
index 5bd49b3..3a1c3f6 100644
--- a/t/t6301-for-each-ref-filter.sh
+++ b/t/t6301-for-each-ref-filter.sh
@@ -32,4 +32,14 @@ test_expect_success 'filtering with fnmatch' '
 	test_cmp expect actual
 '
 
+test_expect_success 'filtering with --points-at' '
+	cat >expect <<-\EOF &&
+	refs/heads/master
+	refs/odd/spot
+	refs/tags/three
+	EOF
+	git for-each-ref --format="%(refname)" --points-at=master >actual &&
+	test_cmp expect actual
+'
+
 test_done
-- 
2.4.3.435.g2403634.dirty

[PATCH v2 05/11] ref-filter: add parse_opt_merge_filter()

[Karthik Nayak]

Add 'parse_opt_merge_filter()' to parse '--merged' and '--no-merged'
options and write MACROS for the same.

This is copied from 'builtin/branch.c' which will eventually be removed
when we port 'branch.c' to use ref-filter APIs.

Based-on-patch-by: Jeff King <peff@peff.net>
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 builtin/branch.c |  4 ++++
 ref-filter.c     | 21 +++++++++++++++++++++
 ref-filter.h     | 14 ++++++++++++++
 3 files changed, 39 insertions(+)

diff --git a/builtin/branch.c b/builtin/branch.c
index b42e5b6..ddd90e6 100644
--- a/builtin/branch.c
+++ b/builtin/branch.c
@@ -745,6 +745,10 @@ static void rename_branch(const char *oldname, const char *newname, int force)
 	strbuf_release(&newsection);
 }
 
+/*
+ * This function is duplicated in ref-filter. It will eventually be removed
+ * when we port branch.c to use ref-filter APIs.
+ */
 static int opt_parse_merge_filter(const struct option *opt, const char *arg, int unset)
 {
 	merge_filter = ((opt->long_name[0] == 'n')
diff --git a/ref-filter.c b/ref-filter.c
index 591e281..6502179 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -1125,3 +1125,24 @@ int parse_opt_ref_sorting(const struct option *opt, const char *arg, int unset)
 	s->atom = parse_ref_filter_atom(arg, arg+len);
 	return 0;
 }
+
+int parse_opt_merge_filter(const struct option *opt, const char *arg, int unset)
+{
+	struct ref_filter *rf = opt->value;
+	unsigned char sha1[20];
+
+	rf->merge = starts_with(opt->long_name, "no")
+		? REF_FILTER_MERGED_OMIT
+		: REF_FILTER_MERGED_INCLUDE;
+
+	if (!arg)
+		arg = "HEAD";
+	if (get_sha1(arg, sha1))
+		die(_("malformed object name %s"), arg);
+
+	rf->merge_commit = lookup_commit_reference_gently(sha1, 0);
+	if (!rf->merge_commit)
+		return opterror(opt, "must point to a commit", 0);
+
+	return 0;
+}
diff --git a/ref-filter.h b/ref-filter.h
index c2856b8..799e118 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -50,6 +50,18 @@ struct ref_filter_cbdata {
 	struct ref_filter *filter;
 };
 
+/*  Macros for checking --merged and --no-merged options */
+#define OPT_NO_MERGED(filter, h) \
+	{ OPTION_CALLBACK, 0, "no-merged", (filter), N_("commit"), (h), \
+	  PARSE_OPT_LASTARG_DEFAULT | PARSE_OPT_NONEG, \
+	  parse_opt_merge_filter, (intptr_t) "HEAD" \
+	}
+#define OPT_MERGED(filter, h) \
+	{ OPTION_CALLBACK, 0, "merged", (filter), N_("commit"), (h), \
+	  PARSE_OPT_LASTARG_DEFAULT | PARSE_OPT_NONEG, \
+	  parse_opt_merge_filter, (intptr_t) "HEAD" \
+	}
+
 /*
  * API for filtering a set of refs. Based on the type of refs the user
  * has requested, we iterate through those refs and apply filters
@@ -71,5 +83,7 @@ void show_ref_array_item(struct ref_array_item *info, const char *format, int qu
 int parse_opt_ref_sorting(const struct option *opt, const char *arg, int unset);
 /*  Default sort option based on refname */
 struct ref_sorting *ref_default_sorting(void);
+/*  Function to parse --merged and --no-merged options */
+int parse_opt_merge_filter(const struct option *opt, const char *arg, int unset);
 
 #endif /*  REF_FILTER_H  */
-- 
2.4.3.435.g2403634.dirty

Re: [PATCH v2 05/11] ref-filter: add parse_opt_merge_filter()

[Christian Couder]

On Sat, Jun 13, 2015 at 10:18 PM, Karthik Nayak <karthik.188@gmail.com> wrote:
>
> diff --git a/ref-filter.h b/ref-filter.h
> index c2856b8..799e118 100644
> --- a/ref-filter.h
> +++ b/ref-filter.h
> @@ -50,6 +50,18 @@ struct ref_filter_cbdata {
>         struct ref_filter *filter;
>  };
>
> +/*  Macros for checking --merged and --no-merged options */
> +#define OPT_NO_MERGED(filter, h) \
> +       { OPTION_CALLBACK, 0, "no-merged", (filter), N_("commit"), (h), \
> +         PARSE_OPT_LASTARG_DEFAULT | PARSE_OPT_NONEG, \
> +         parse_opt_merge_filter, (intptr_t) "HEAD" \
> +       }
> +#define OPT_MERGED(filter, h) \
> +       { OPTION_CALLBACK, 0, "merged", (filter), N_("commit"), (h), \
> +         PARSE_OPT_LASTARG_DEFAULT | PARSE_OPT_NONEG, \
> +         parse_opt_merge_filter, (intptr_t) "HEAD" \
> +       }

Could you reduce the redundancy in these 2 macros?

Re: [PATCH v2 05/11] ref-filter: add parse_opt_merge_filter()

[karthik nayak]

On Sun, Jun 14, 2015 at 11:19 AM, Christian Couder
<christian.couder@gmail.com> wrote:
> On Sat, Jun 13, 2015 at 10:18 PM, Karthik Nayak <karthik.188@gmail.com> wrote:
>>
>> diff --git a/ref-filter.h b/ref-filter.h
>> index c2856b8..799e118 100644
>> --- a/ref-filter.h
>> +++ b/ref-filter.h
>> @@ -50,6 +50,18 @@ struct ref_filter_cbdata {
>>         struct ref_filter *filter;
>>  };
>>
>> +/*  Macros for checking --merged and --no-merged options */
>> +#define OPT_NO_MERGED(filter, h) \
>> +       { OPTION_CALLBACK, 0, "no-merged", (filter), N_("commit"), (h), \
>> +         PARSE_OPT_LASTARG_DEFAULT | PARSE_OPT_NONEG, \
>> +         parse_opt_merge_filter, (intptr_t) "HEAD" \
>> +       }
>> +#define OPT_MERGED(filter, h) \
>> +       { OPTION_CALLBACK, 0, "merged", (filter), N_("commit"), (h), \
>> +         PARSE_OPT_LASTARG_DEFAULT | PARSE_OPT_NONEG, \
>> +         parse_opt_merge_filter, (intptr_t) "HEAD" \
>> +       }
>
> Could you reduce the redundancy in these 2 macros?

Yes, will do!

-- 
Regards,
Karthik Nayak

[PATCH v2 06/11] ref-filter: implement '--merged' and '--no-merged' options

[Karthik Nayak]

In 'branch -l' we have '--merged' option which only lists refs (branches)
merged into the named commit and '--no-merged' option which only lists
refs (branches) not merged into the named commit. Implement these two
options in ref-filter.{c,h} so that other commands can benefit from this.

Based-on-patch-by: Jeff King <peff@peff.net>
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 ref-filter.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 ref-filter.h |  8 +++++++
 2 files changed, 72 insertions(+), 4 deletions(-)

diff --git a/ref-filter.c b/ref-filter.c
index 6502179..06328eb 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -9,6 +9,7 @@
 #include "tag.h"
 #include "quote.h"
 #include "ref-filter.h"
+#include "revision.h"
 
 typedef enum { FIELD_STR, FIELD_ULONG, FIELD_TIME } cmp_type;
 
@@ -889,6 +890,7 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,
 	struct ref_filter_cbdata *ref_cbdata = cb_data;
 	struct ref_filter *filter = ref_cbdata->filter;
 	struct ref_array_item *ref;
+	struct commit *commit = NULL;
 
 	if (flag & REF_BAD_NAME) {
 		  warning("ignoring ref with broken name %s", refname);
@@ -901,12 +903,19 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,
 	if (!match_points_at(&filter->points_at, oid->hash, refname))
 		return 0;
 
+	if (filter->merge_commit) {
+		commit = lookup_commit_reference_gently(oid->hash, 1);
+		if (!commit)
+			return 0;
+	}
+
 	/*
 	 * We do not open the object yet; sort may only need refname
 	 * to do its job and the resulting list may yet to be pruned
 	 * by maxcount logic.
 	 */
 	ref = new_ref_array_item(refname, oid->hash, flag);
+	ref->commit = commit;
 
 	REALLOC_ARRAY(ref_cbdata->array->items, ref_cbdata->array->nr + 1);
 	ref_cbdata->array->items[ref_cbdata->array->nr++] = ref;
@@ -932,6 +941,50 @@ void ref_array_clear(struct ref_array *array)
 	array->nr = array->alloc = 0;
 }
 
+static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata)
+{
+	struct rev_info revs;
+	int i, old_nr;
+	struct ref_filter *filter = ref_cbdata->filter;
+	struct ref_array *array = ref_cbdata->array;
+	struct commit_list *p, *to_clear = NULL;
+
+	init_revisions(&revs, NULL);
+
+	for (i = 0; i < array->nr; i++) {
+		struct ref_array_item *item = array->items[i];
+		add_pending_object(&revs, &item->commit->object, item->refname);
+		commit_list_insert(item->commit, &to_clear);
+	}
+
+	filter->merge_commit->object.flags |= UNINTERESTING;
+	add_pending_object(&revs, &filter->merge_commit->object, "");
+
+	revs.limited = 1;
+	if (prepare_revision_walk(&revs))
+		die(_("revision walk setup failed"));
+
+	old_nr = array->nr;
+	array->nr = 0;
+
+	for (i = 0; i < old_nr; i++) {
+		struct ref_array_item *item = array->items[i];
+		struct commit *commit = item->commit;
+
+		int is_merged = !!(commit->object.flags & UNINTERESTING);
+
+		if (is_merged == (filter->merge == REF_FILTER_MERGED_INCLUDE))
+			array->items[array->nr++] = array->items[i];
+		else
+			free_array_item(item);
+	}
+
+	for (p = to_clear; p; p = p->next)
+		clear_commit_marks(p->item, ALL_REV_FLAGS);
+	clear_commit_marks(filter->merge_commit, ALL_REV_FLAGS);
+	free_commit_list(to_clear);
+}
+
 /*
  * API for filtering a set of refs. Based on the type of refs the user
  * has requested, we iterate through those refs and apply filters
@@ -941,17 +994,24 @@ void ref_array_clear(struct ref_array *array)
 int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int type)
 {
 	struct ref_filter_cbdata ref_cbdata;
+	int ret = 0;
 
 	ref_cbdata.array = array;
 	ref_cbdata.filter = filter;
 
+	/*  Simple per-ref filtering */
 	if (type & (FILTER_REFS_ALL | FILTER_REFS_INCLUDE_BROKEN))
-		return for_each_rawref(ref_filter_handler, &ref_cbdata);
+		ret = for_each_rawref(ref_filter_handler, &ref_cbdata);
 	else if (type & FILTER_REFS_ALL)
-		return for_each_ref(ref_filter_handler, &ref_cbdata);
-	else
+		ret = for_each_ref(ref_filter_handler, &ref_cbdata);
+	else if (type)
 		die("filter_refs: invalid type");
-	return 0;
+
+	/*  Filters that need revision walking */
+	if (filter->merge_commit)
+		do_merge_filter(&ref_cbdata);
+
+	return ret;
 }
 
 static int cmp_ref_sorting(struct ref_sorting *s, struct ref_array_item *a, struct ref_array_item *b)
diff --git a/ref-filter.h b/ref-filter.h
index 799e118..39d66b0 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -31,6 +31,7 @@ struct ref_array_item {
 	unsigned char objectname[20];
 	int flag;
 	const char *symref;
+	struct commit *commit;
 	struct atom_value *value;
 	char refname[FLEX_ARRAY];
 };
@@ -43,6 +44,13 @@ struct ref_array {
 struct ref_filter {
 	const char **name_patterns;
 	struct sha1_array points_at;
+
+	enum {
+		REF_FILTER_MERGED_NONE = 0,
+		REF_FILTER_MERGED_INCLUDE,
+		REF_FILTER_MERGED_OMIT
+	} merge;
+	struct commit *merge_commit;
 };
 
 struct ref_filter_cbdata {
-- 
2.4.3.435.g2403634.dirty

[PATCH v2 07/11] for-each-ref: add '--merged' and '--no-merged' options

[Karthik Nayak]

Add the '--merged' and '--no-merged' options provided by 'ref-filter'.
The '--merged' option lets the user to only list refs merged into the
named commit. The '--no-merged' option lets the user to only list refs
not merged into the named commit.

Add documentation and tests for the same.

Based-on-patch-by: Jeff King <peff@peff.net>
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 Documentation/git-for-each-ref.txt | 10 +++++++++-
 builtin/for-each-ref.c             |  3 +++
 t/t6301-for-each-ref-filter.sh     | 21 +++++++++++++++++++++
 3 files changed, 33 insertions(+), 1 deletion(-)

diff --git a/Documentation/git-for-each-ref.txt b/Documentation/git-for-each-ref.txt
index 0524ac4..d61a756 100644
--- a/Documentation/git-for-each-ref.txt
+++ b/Documentation/git-for-each-ref.txt
@@ -10,7 +10,7 @@ SYNOPSIS
 [verse]
 'git for-each-ref' [--count=<count>] [--shell|--perl|--python|--tcl]
 		   [(--sort=<key>)...] [--format=<format>] [<pattern>...]
-		   [--points-at <object>]
+		   [--points-at <object>] [(--merged | --no-merged) <object>]
 
 DESCRIPTION
 -----------
@@ -66,6 +66,14 @@ OPTIONS
 --points-at <object>::
 	Only list refs of the given object.
 
+--merged [<commit>]::
+	Only list refs whose tips are reachable from the
+	specified commit (HEAD if not specified).
+
+--no-merged [<commit>]::
+	Only list refs whose tips are not reachable from the
+	specified commit (HEAD if not specified).
+
 FIELD NAMES
 -----------
 
diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
index 2dee149..00913f4 100644
--- a/builtin/for-each-ref.c
+++ b/builtin/for-each-ref.c
@@ -8,6 +8,7 @@
 static char const * const for_each_ref_usage[] = {
 	N_("git for-each-ref [<options>] [<pattern>]"),
 	N_("git for-each-ref [--points-at <object>]"),
+	N_("git for-each-ref [(--merged | --no-merged) <object>]"),
 	NULL
 };
 
@@ -38,6 +39,8 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 		OPT_CALLBACK(0, "points-at", &filter.points_at,
 			     N_("object"), N_("print only refs of the object"),
 			     parse_opt_object_name),
+		OPT_MERGED(&filter, N_("print only refs that are merged")),
+		OPT_NO_MERGED(&filter, N_("print only refs that are not merged")),
 		OPT_END(),
 	};
 
diff --git a/t/t6301-for-each-ref-filter.sh b/t/t6301-for-each-ref-filter.sh
index 3a1c3f6..3ed97bd 100644
--- a/t/t6301-for-each-ref-filter.sh
+++ b/t/t6301-for-each-ref-filter.sh
@@ -42,4 +42,25 @@ test_expect_success 'filtering with --points-at' '
 	test_cmp expect actual
 '
 
+test_expect_success 'filtering with --merged' '
+	cat >expect <<-\EOF &&
+	refs/heads/master
+	refs/odd/spot
+	refs/tags/one
+	refs/tags/three
+	refs/tags/two
+	EOF
+	git for-each-ref --format="%(refname)" --merged=master >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'filtering with --no-merged' '
+	cat >expect <<-\EOF &&
+	refs/heads/side
+	refs/tags/four
+	EOF
+	git for-each-ref --format="%(refname)" --no-merged=master >actual &&
+	test_cmp expect actual
+'
+
 test_done
-- 
2.4.3.435.g2403634.dirty

[PATCH v2 08/11] parse-option: rename parse_opt_with_commit()

[Karthik Nayak]

Rename parse_opt_with_commit() to parse_opt_commit_object_name()
to show that it can be used to obtain a list of commits and is
not constricted to usage of '--contains' option.

Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 builtin/branch.c   | 4 ++--
 builtin/tag.c      | 4 ++--
 parse-options-cb.c | 2 +-
 parse-options.h    | 2 +-
 4 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/builtin/branch.c b/builtin/branch.c
index ddd90e6..ddd728e 100644
--- a/builtin/branch.c
+++ b/builtin/branch.c
@@ -828,13 +828,13 @@ int cmd_branch(int argc, const char **argv, const char *prefix)
 			OPTION_CALLBACK, 0, "contains", &with_commit, N_("commit"),
 			N_("print only branches that contain the commit"),
 			PARSE_OPT_LASTARG_DEFAULT,
-			parse_opt_with_commit, (intptr_t)"HEAD",
+			parse_opt_commit_object_name, (intptr_t)"HEAD",
 		},
 		{
 			OPTION_CALLBACK, 0, "with", &with_commit, N_("commit"),
 			N_("print only branches that contain the commit"),
 			PARSE_OPT_HIDDEN | PARSE_OPT_LASTARG_DEFAULT,
-			parse_opt_with_commit, (intptr_t) "HEAD",
+			parse_opt_commit_object_name, (intptr_t) "HEAD",
 		},
 		OPT__ABBREV(&abbrev),
 
diff --git a/builtin/tag.c b/builtin/tag.c
index 280981f..2d6610a 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -603,13 +603,13 @@ int cmd_tag(int argc, const char **argv, const char *prefix)
 			OPTION_CALLBACK, 0, "contains", &with_commit, N_("commit"),
 			N_("print only tags that contain the commit"),
 			PARSE_OPT_LASTARG_DEFAULT,
-			parse_opt_with_commit, (intptr_t)"HEAD",
+			parse_opt_commit_object_name, (intptr_t)"HEAD",
 		},
 		{
 			OPTION_CALLBACK, 0, "with", &with_commit, N_("commit"),
 			N_("print only tags that contain the commit"),
 			PARSE_OPT_HIDDEN | PARSE_OPT_LASTARG_DEFAULT,
-			parse_opt_with_commit, (intptr_t)"HEAD",
+			parse_opt_commit_object_name, (intptr_t)"HEAD",
 		},
 		{
 			OPTION_CALLBACK, 0, "points-at", &points_at, N_("object"),
diff --git a/parse-options-cb.c b/parse-options-cb.c
index de75411..8bec5e4 100644
--- a/parse-options-cb.c
+++ b/parse-options-cb.c
@@ -77,7 +77,7 @@ int parse_opt_verbosity_cb(const struct option *opt, const char *arg,
 	return 0;
 }
 
-int parse_opt_with_commit(const struct option *opt, const char *arg, int unset)
+int parse_opt_commit_object_name(const struct option *opt, const char *arg, int unset)
 {
 	unsigned char sha1[20];
 	struct commit *commit;
diff --git a/parse-options.h b/parse-options.h
index 36c71fe..8542d9c 100644
--- a/parse-options.h
+++ b/parse-options.h
@@ -221,7 +221,7 @@ extern int parse_opt_expiry_date_cb(const struct option *, const char *, int);
 extern int parse_opt_color_flag_cb(const struct option *, const char *, int);
 extern int parse_opt_verbosity_cb(const struct option *, const char *, int);
 extern int parse_opt_object_name(const struct option *, const char *, int);
-extern int parse_opt_with_commit(const struct option *, const char *, int);
+extern int parse_opt_commit_object_name(const struct option *, const char *, int);
 extern int parse_opt_tertiary(const struct option *, const char *, int);
 extern int parse_opt_string_list(const struct option *, const char *, int);
 extern int parse_opt_noop_cb(const struct option *, const char *, int);
-- 
2.4.3.435.g2403634.dirty

[PATCH v2 09/11] parse-options.h: add macros for '--contains' option

[Karthik Nayak]

Add a macro for using the '--contains' option in parse-options.h
also include an optional '--with' option macro which performs the
same action as '--contains'.

Make tag.c use this new macro

Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 builtin/tag.c   | 14 ++------------
 parse-options.h |  7 +++++++
 2 files changed, 9 insertions(+), 12 deletions(-)

diff --git a/builtin/tag.c b/builtin/tag.c
index 2d6610a..767162e 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -595,23 +595,13 @@ int cmd_tag(int argc, const char **argv, const char *prefix)
 
 		OPT_GROUP(N_("Tag listing options")),
 		OPT_COLUMN(0, "column", &colopts, N_("show tag list in columns")),
+		OPT_CONTAINS(&with_commit, N_("print only tags that contain the commit")),
+		OPT_WITH(&with_commit, N_("print only tags that contain the commit")),
 		{
 			OPTION_CALLBACK, 0, "sort", &tag_sort, N_("type"), N_("sort tags"),
 			PARSE_OPT_NONEG, parse_opt_sort
 		},
 		{
-			OPTION_CALLBACK, 0, "contains", &with_commit, N_("commit"),
-			N_("print only tags that contain the commit"),
-			PARSE_OPT_LASTARG_DEFAULT,
-			parse_opt_commit_object_name, (intptr_t)"HEAD",
-		},
-		{
-			OPTION_CALLBACK, 0, "with", &with_commit, N_("commit"),
-			N_("print only tags that contain the commit"),
-			PARSE_OPT_HIDDEN | PARSE_OPT_LASTARG_DEFAULT,
-			parse_opt_commit_object_name, (intptr_t)"HEAD",
-		},
-		{
 			OPTION_CALLBACK, 0, "points-at", &points_at, N_("object"),
 			N_("print only tags of the object"), 0, parse_opt_object_name
 		},
diff --git a/parse-options.h b/parse-options.h
index 8542d9c..d76e907 100644
--- a/parse-options.h
+++ b/parse-options.h
@@ -243,5 +243,12 @@ extern int parse_opt_noop_cb(const struct option *, const char *, int);
 	OPT_COLOR_FLAG(0, "color", (var), (h))
 #define OPT_COLUMN(s, l, v, h) \
 	{ OPTION_CALLBACK, (s), (l), (v), N_("style"), (h), PARSE_OPT_OPTARG, parseopt_column_callback }
+#define _OPT_CONTAINS_OR_WITH(name, variable, help) \
+	{ OPTION_CALLBACK, 0, name, (variable), N_("commit"), (help), \
+	  PARSE_OPT_LASTARG_DEFAULT, \
+	  parse_opt_commit_object_name, (intptr_t) "HEAD" \
+	}
+#define OPT_CONTAINS(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h)
+#define OPT_WITH(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h)
 
 #endif
-- 
2.4.3.435.g2403634.dirty

Re: [PATCH v2 09/11] parse-options.h: add macros for '--contains' option

[Christian Couder]

On Sat, Jun 13, 2015 at 10:18 PM, Karthik Nayak <karthik.188@gmail.com> wrote:
> Add a macro for using the '--contains' option in parse-options.h
> also include an optional '--with' option macro which performs the
> same action as '--contains'.
>
> Make tag.c use this new macro
>
> Mentored-by: Christian Couder <christian.couder@gmail.com>
> Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
> Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
> ---
>  builtin/tag.c   | 14 ++------------
>  parse-options.h |  7 +++++++
>  2 files changed, 9 insertions(+), 12 deletions(-)
>
> diff --git a/builtin/tag.c b/builtin/tag.c
> index 2d6610a..767162e 100644
> --- a/builtin/tag.c
> +++ b/builtin/tag.c
> @@ -595,23 +595,13 @@ int cmd_tag(int argc, const char **argv, const char *prefix)
>
>                 OPT_GROUP(N_("Tag listing options")),
>                 OPT_COLUMN(0, "column", &colopts, N_("show tag list in columns")),
> +               OPT_CONTAINS(&with_commit, N_("print only tags that contain the commit")),
> +               OPT_WITH(&with_commit, N_("print only tags that contain the commit")),
>                 {
>                         OPTION_CALLBACK, 0, "sort", &tag_sort, N_("type"), N_("sort tags"),
>                         PARSE_OPT_NONEG, parse_opt_sort
>                 },
>                 {
> -                       OPTION_CALLBACK, 0, "contains", &with_commit, N_("commit"),
> -                       N_("print only tags that contain the commit"),
> -                       PARSE_OPT_LASTARG_DEFAULT,
> -                       parse_opt_commit_object_name, (intptr_t)"HEAD",
> -               },
> -               {
> -                       OPTION_CALLBACK, 0, "with", &with_commit, N_("commit"),
> -                       N_("print only tags that contain the commit"),
> -                       PARSE_OPT_HIDDEN | PARSE_OPT_LASTARG_DEFAULT,

The PARSE_OPT_HIDDEN flag is removed below. This means that "--with"
will appear in the "git tag -h" output, which means that "--with"
should appear in the documentation...
The commit message may also want to tell that with is not hidden any more.

> -                       parse_opt_commit_object_name, (intptr_t)"HEAD",
> -               },
> -               {
>                         OPTION_CALLBACK, 0, "points-at", &points_at, N_("object"),
>                         N_("print only tags of the object"), 0, parse_opt_object_name
>                 },
> diff --git a/parse-options.h b/parse-options.h
> index 8542d9c..d76e907 100644
> --- a/parse-options.h
> +++ b/parse-options.h
> @@ -243,5 +243,12 @@ extern int parse_opt_noop_cb(const struct option *, const char *, int);
>         OPT_COLOR_FLAG(0, "color", (var), (h))
>  #define OPT_COLUMN(s, l, v, h) \
>         { OPTION_CALLBACK, (s), (l), (v), N_("style"), (h), PARSE_OPT_OPTARG, parseopt_column_callback }
> +#define _OPT_CONTAINS_OR_WITH(name, variable, help) \
> +       { OPTION_CALLBACK, 0, name, (variable), N_("commit"), (help), \
> +         PARSE_OPT_LASTARG_DEFAULT, \
> +         parse_opt_commit_object_name, (intptr_t) "HEAD" \
> +       }
> +#define OPT_CONTAINS(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h)
> +#define OPT_WITH(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h)

Shouldn't it be "with" instead of "contains"?

Re: [PATCH v2 09/11] parse-options.h: add macros for '--contains' option

[karthik nayak]

On Sun, Jun 14, 2015 at 11:43 AM, Christian Couder
<christian.couder@gmail.com> wrote:
> On Sat, Jun 13, 2015 at 10:18 PM, Karthik Nayak <karthik.188@gmail.com> wrote:
>> Add a macro for using the '--contains' option in parse-options.h
>> also include an optional '--with' option macro which performs the
>> same action as '--contains'.
>>
>> Make tag.c use this new macro
>>
>> Mentored-by: Christian Couder <christian.couder@gmail.com>
>> Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
>> Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
>> ---
>>  builtin/tag.c   | 14 ++------------
>>  parse-options.h |  7 +++++++
>>  2 files changed, 9 insertions(+), 12 deletions(-)
>>
>> diff --git a/builtin/tag.c b/builtin/tag.c
>> index 2d6610a..767162e 100644
>> --- a/builtin/tag.c
>> +++ b/builtin/tag.c
>> @@ -595,23 +595,13 @@ int cmd_tag(int argc, const char **argv, const char *prefix)
>>
>>                 OPT_GROUP(N_("Tag listing options")),
>>                 OPT_COLUMN(0, "column", &colopts, N_("show tag list in columns")),
>> +               OPT_CONTAINS(&with_commit, N_("print only tags that contain the commit")),
>> +               OPT_WITH(&with_commit, N_("print only tags that contain the commit")),
>>                 {
>>                         OPTION_CALLBACK, 0, "sort", &tag_sort, N_("type"), N_("sort tags"),
>>                         PARSE_OPT_NONEG, parse_opt_sort
>>                 },
>>                 {
>> -                       OPTION_CALLBACK, 0, "contains", &with_commit, N_("commit"),
>> -                       N_("print only tags that contain the commit"),
>> -                       PARSE_OPT_LASTARG_DEFAULT,
>> -                       parse_opt_commit_object_name, (intptr_t)"HEAD",
>> -               },
>> -               {
>> -                       OPTION_CALLBACK, 0, "with", &with_commit, N_("commit"),
>> -                       N_("print only tags that contain the commit"),
>> -                       PARSE_OPT_HIDDEN | PARSE_OPT_LASTARG_DEFAULT,
>
> The PARSE_OPT_HIDDEN flag is removed below. This means that "--with"
> will appear in the "git tag -h" output, which means that "--with"
> should appear in the documentation...
> The commit message may also want to tell that with is not hidden any more.
>

Yes! I will add that.

>> -                       parse_opt_commit_object_name, (intptr_t)"HEAD",
>> -               },
>> -               {
>>                         OPTION_CALLBACK, 0, "points-at", &points_at, N_("object"),
>>                         N_("print only tags of the object"), 0, parse_opt_object_name
>>                 },
>> diff --git a/parse-options.h b/parse-options.h
>> index 8542d9c..d76e907 100644
>> --- a/parse-options.h
>> +++ b/parse-options.h
>> @@ -243,5 +243,12 @@ extern int parse_opt_noop_cb(const struct option *, const char *, int);
>>         OPT_COLOR_FLAG(0, "color", (var), (h))
>>  #define OPT_COLUMN(s, l, v, h) \
>>         { OPTION_CALLBACK, (s), (l), (v), N_("style"), (h), PARSE_OPT_OPTARG, parseopt_column_callback }
>> +#define _OPT_CONTAINS_OR_WITH(name, variable, help) \
>> +       { OPTION_CALLBACK, 0, name, (variable), N_("commit"), (help), \
>> +         PARSE_OPT_LASTARG_DEFAULT, \
>> +         parse_opt_commit_object_name, (intptr_t) "HEAD" \
>> +       }
>> +#define OPT_CONTAINS(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h)
>> +#define OPT_WITH(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h)
>
> Shouldn't it be "with" instead of "contains"?

Actually it wouldn't matter, but since I've removed the PARSE_OPT_HIDDEN flag
it would show 'contains' twice. Will change it to 'with'.

Thanks for the review.

-- 
Regards,
Karthik Nayak

Re: [PATCH v2 09/11] parse-options.h: add macros for '--contains' option

[Junio C Hamano]

Christian Couder <christian.couder@gmail.com> writes:

> The PARSE_OPT_HIDDEN flag is removed below. This means that "--with"
> will appear in the "git tag -h" output, which means that "--with"
> should appear in the documentation...
> The commit message may also want to tell that with is not hidden any more.

Or why is it a good idea to stop hiding.

I would prefer to keep it hidden to avoid "what's the difference
between the two" confusion.

Re: [PATCH v2 09/11] parse-options.h: add macros for '--contains' option

[karthik nayak]

On Tue, Jun 16, 2015 at 12:57 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Christian Couder <christian.couder@gmail.com> writes:
>
>> The PARSE_OPT_HIDDEN flag is removed below. This means that "--with"
>> will appear in the "git tag -h" output, which means that "--with"
>> should appear in the documentation...
>> The commit message may also want to tell that with is not hidden any more.
>
> Or why is it a good idea to stop hiding.
>
> I would prefer to keep it hidden to avoid "what's the difference
> between the two" confusion.

Ok than, will do that.

-- 
Regards,
Karthik Nayak

[PATCH v2 10/11] ref-filter: implement '--contains' option

[Karthik Nayak]

'tag -l' and 'branch -l' have two different ways of finding
out if a certain ref contains a commit. Implement both these
methods in ref-filter and give the caller of ref-filter API
the option to pick which implementation to be used.

'branch -l' uses 'is_descendant_of()' from commit.c which is
left as the default implementation to be used.

'tag -l' uses a more specific algorithm since ffc4b80. This
implementation is used whenever the 'with_commit_tag_algo' bit
is set in 'struct ref_filter'.

Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 ref-filter.c | 112 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 ref-filter.h |   3 ++
 2 files changed, 114 insertions(+), 1 deletion(-)

diff --git a/ref-filter.c b/ref-filter.c
index 06328eb..40eb90e 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -818,6 +818,113 @@ static void get_ref_atom_value(struct ref_array_item *ref, int atom, struct atom
 	*v = &ref->value[atom];
 }
 
+enum contains_result {
+	CONTAINS_UNKNOWN = -1,
+	CONTAINS_NO = 0,
+	CONTAINS_YES = 1
+};
+
+/*
+ * Mimicking the real stack, this stack lives on the heap, avoiding stack
+ * overflows.
+ *
+ * At each recursion step, the stack items points to the commits whose
+ * ancestors are to be inspected.
+ */
+struct contains_stack {
+	int nr, alloc;
+	struct contains_stack_entry {
+		struct commit *commit;
+		struct commit_list *parents;
+	} *contains_stack;
+};
+
+static int in_commit_list(const struct commit_list *want, struct commit *c)
+{
+	for (; want; want = want->next)
+		if (!hashcmp(want->item->object.sha1, c->object.sha1))
+			return 1;
+	return 0;
+}
+
+/*
+ * Test whether the candidate or one of its parents is contained in the list.
+ * Do not recurse to find out, though, but return -1 if inconclusive.
+ */
+static enum contains_result contains_test(struct commit *candidate,
+			    const struct commit_list *want)
+{
+	/* was it previously marked as containing a want commit? */
+	if (candidate->object.flags & TMP_MARK)
+		return 1;
+	/* or marked as not possibly containing a want commit? */
+	if (candidate->object.flags & UNINTERESTING)
+		return 0;
+	/* or are we it? */
+	if (in_commit_list(want, candidate)) {
+		candidate->object.flags |= TMP_MARK;
+		return 1;
+	}
+
+	if (parse_commit(candidate) < 0)
+		return 0;
+
+	return -1;
+}
+
+static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)
+{
+	ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);
+	contains_stack->contains_stack[contains_stack->nr].commit = candidate;
+	contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
+}
+
+static enum contains_result contains_tag_algo(struct commit *candidate,
+		const struct commit_list *want)
+{
+	struct contains_stack contains_stack = { 0, 0, NULL };
+	int result = contains_test(candidate, want);
+
+	if (result != CONTAINS_UNKNOWN)
+		return result;
+
+	push_to_contains_stack(candidate, &contains_stack);
+	while (contains_stack.nr) {
+		struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
+		struct commit *commit = entry->commit;
+		struct commit_list *parents = entry->parents;
+
+		if (!parents) {
+			commit->object.flags |= UNINTERESTING;
+			contains_stack.nr--;
+		}
+		/*
+		 * If we just popped the stack, parents->item has been marked,
+		 * therefore contains_test will return a meaningful 0 or 1.
+		 */
+		else switch (contains_test(parents->item, want)) {
+		case CONTAINS_YES:
+			commit->object.flags |= TMP_MARK;
+			contains_stack.nr--;
+			break;
+		case CONTAINS_NO:
+			entry->parents = parents->next;
+			break;
+		case CONTAINS_UNKNOWN:
+			push_to_contains_stack(parents->item, &contains_stack);
+			break;
+		}
+	}
+	free(contains_stack.contains_stack);
+	return contains_test(candidate, want);
+}
+
+static int commit_contains(struct ref_filter *filter, struct commit *commit)
+{
+	if (filter->with_commit_tag_algo)
+		return contains_tag_algo(commit, filter->with_commit);
+	return is_descendant_of(commit, filter->with_commit);
+}
 /*
  * Return 1 if the refname matches one of the patterns, otherwise 0.
  * A pattern can be path prefix (e.g. a refname "refs/heads/master"
@@ -903,10 +1010,13 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,
 	if (!match_points_at(&filter->points_at, oid->hash, refname))
 		return 0;
 
-	if (filter->merge_commit) {
+	if (filter->merge_commit || filter->with_commit) {
 		commit = lookup_commit_reference_gently(oid->hash, 1);
 		if (!commit)
 			return 0;
+		if (filter->with_commit &&
+		    !commit_contains(filter, commit))
+			return 0;
 	}
 
 	/*
diff --git a/ref-filter.h b/ref-filter.h
index 39d66b0..e614713 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -44,6 +44,7 @@ struct ref_array {
 struct ref_filter {
 	const char **name_patterns;
 	struct sha1_array points_at;
+	struct commit_list *with_commit;
 
 	enum {
 		REF_FILTER_MERGED_NONE = 0,
@@ -51,6 +52,8 @@ struct ref_filter {
 		REF_FILTER_MERGED_OMIT
 	} merge;
 	struct commit *merge_commit;
+
+	unsigned int with_commit_tag_algo: 1;
 };
 
 struct ref_filter_cbdata {
-- 
2.4.3.435.g2403634.dirty

[PATCH v2 11/11] for-each-ref: add '--contains' option

[Karthik Nayak]

Add the '--contains' option provided by 'ref-filter'. The '--contains'
option lists only refs which are contain the mentioned commit (HEAD if
no commit is explicitly given).

Add documentation and tests for the same.

Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
---
 Documentation/git-for-each-ref.txt |  5 +++++
 builtin/for-each-ref.c             |  2 ++
 t/t6301-for-each-ref-filter.sh     | 13 +++++++++++++
 3 files changed, 20 insertions(+)

diff --git a/Documentation/git-for-each-ref.txt b/Documentation/git-for-each-ref.txt
index d61a756..7a949f3 100644
--- a/Documentation/git-for-each-ref.txt
+++ b/Documentation/git-for-each-ref.txt
@@ -11,6 +11,7 @@ SYNOPSIS
 'git for-each-ref' [--count=<count>] [--shell|--perl|--python|--tcl]
 		   [(--sort=<key>)...] [--format=<format>] [<pattern>...]
 		   [--points-at <object>] [(--merged | --no-merged) <object>]
+		   [--contains <object>]
 
 DESCRIPTION
 -----------
@@ -74,6 +75,10 @@ OPTIONS
 	Only list refs whose tips are not reachable from the
 	specified commit (HEAD if not specified).
 
+--contains [<commit>]::
+	Only list tags which contain the specified commit (HEAD if not
+	specified).
+
 FIELD NAMES
 -----------
 
diff --git a/builtin/for-each-ref.c b/builtin/for-each-ref.c
index 00913f4..8ccbb1c 100644
--- a/builtin/for-each-ref.c
+++ b/builtin/for-each-ref.c
@@ -9,6 +9,7 @@ static char const * const for_each_ref_usage[] = {
 	N_("git for-each-ref [<options>] [<pattern>]"),
 	N_("git for-each-ref [--points-at <object>]"),
 	N_("git for-each-ref [(--merged | --no-merged) <object>]"),
+	N_("git for-each-ref [--contains <object>]"),
 	NULL
 };
 
@@ -41,6 +42,7 @@ int cmd_for_each_ref(int argc, const char **argv, const char *prefix)
 			     parse_opt_object_name),
 		OPT_MERGED(&filter, N_("print only refs that are merged")),
 		OPT_NO_MERGED(&filter, N_("print only refs that are not merged")),
+		OPT_CONTAINS(&filter.with_commit, N_("print only refs which contain the commit")),
 		OPT_END(),
 	};
 
diff --git a/t/t6301-for-each-ref-filter.sh b/t/t6301-for-each-ref-filter.sh
index 3ed97bd..17cf7b0 100644
--- a/t/t6301-for-each-ref-filter.sh
+++ b/t/t6301-for-each-ref-filter.sh
@@ -63,4 +63,17 @@ test_expect_success 'filtering with --no-merged' '
 	test_cmp expect actual
 '
 
+test_expect_success 'filtering with --contains' '
+	cat >expect <<-\EOF &&
+	refs/heads/master
+	refs/heads/side
+	refs/odd/spot
+	refs/tags/four
+	refs/tags/three
+	refs/tags/two
+	EOF
+	git for-each-ref --format="%(refname)" --contains=two >actual &&
+	test_cmp expect actual
+'
+
 test_done
-- 
2.4.3.435.g2403634.dirty

Re: [PATCH v2 01/11] t6301: for-each-ref tests for ref-filter APIs

[Matthieu Moy]

Karthik Nayak <karthik.188@gmail.com> writes:

> +test_expect_success 'setup some history and refs' '
> +	test_commit one &&
> +	test_commit two &&
> +	test_commit three &&
> +	git checkout -b side &&
> +	test_commit four &&
> +	git checkout master &&
> +	git update-ref refs/odd/spot master

I think you want more corner-cases here. For example,
refs/headsfoo/master should not match refs/heads, and it's easy to write
an incorrect implementation for this => test.

> +'
> +test_expect_success 'filtering by leading name' '

Blank line between tests please.

> +	cat >expect <<-\EOF &&
> +	refs/heads/master
> +	refs/heads/side
> +	EOF
> +	git for-each-ref --format="%(refname)" refs/heads >actual &&
> +	test_cmp expect actual
> +'

Isn't this test redundant with the content of t6300-for-each-ref.sh?

At this point, you've done only internal refactoring, so you shouldn't
need new tests (except to fix coverage holes in existing tests).

I guess you're adding this to build more tests on top, but the commit
message should clarify this.

-- 
Matthieu Moy
http://www-verimag.imag.fr/~moy/

Re: [PATCH v2 01/11] t6301: for-each-ref tests for ref-filter APIs

[karthik nayak]

On Sun, Jun 14, 2015 at 1:42 PM, Matthieu Moy
<Matthieu.Moy@grenoble-inp.fr> wrote:
> Karthik Nayak <karthik.188@gmail.com> writes:
>
>> +test_expect_success 'setup some history and refs' '
>> +     test_commit one &&
>> +     test_commit two &&
>> +     test_commit three &&
>> +     git checkout -b side &&
>> +     test_commit four &&
>> +     git checkout master &&
>> +     git update-ref refs/odd/spot master
>
> I think you want more corner-cases here. For example,
> refs/headsfoo/master should not match refs/heads, and it's easy to write
> an incorrect implementation for this => test.

Like you mentioned below, currently it's redundant with t6300 and its
purpose is to add tests for new functionality we provide to for-each-ref
via ref-filter. This is done in the next few patches in this series.

>
>> +'
>> +test_expect_success 'filtering by leading name' '
>
> Blank line between tests please.

Noted. Thanks.

>
>> +     cat >expect <<-\EOF &&
>> +     refs/heads/master
>> +     refs/heads/side
>> +     EOF
>> +     git for-each-ref --format="%(refname)" refs/heads >actual &&
>> +     test_cmp expect actual
>> +'
>
> Isn't this test redundant with the content of t6300-for-each-ref.sh?
>
> At this point, you've done only internal refactoring, so you shouldn't
> need new tests (except to fix coverage holes in existing tests).
>
> I guess you're adding this to build more tests on top, but the commit
> message should clarify this.
>

I'll add a note to the commit message about how this test file is so
that we can integrate
more tests in the future for functionality given to for-each-ref via
ref-filter APIs.

-- 
Regards,
Karthik Nayak