[RFC/PATCH 5/9] ref-filter: implement '--merged' and '--no-merged' options

[Karthik Nayak <karthik.188@gmail.com>]

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 will be listed. 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 | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 ref-filter.h |  8 ++++++++
 2 files changed, 68 insertions(+), 1 deletion(-)

diff --git a/ref-filter.c b/ref-filter.c
index 456b0fa..2be9df2 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;
 
@@ -888,6 +889,7 @@ int ref_filter_handler(const char *refname, const struct object_id *oid, int fla
 	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);
@@ -900,12 +902,19 @@ int ref_filter_handler(const char *refname, const struct object_id *oid, int fla
 	if (!match_points_at(&filter->points_at, oid->hash, refname))
 		return 0;
 
+	if(filter->merge_commit) {
+		commit = lookup_commit_reference_gently(sha1, 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;
@@ -931,6 +940,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. The refs are provided and iterated
  * over using the for_each_ref_fn(). The refs are stored into and filtered
@@ -938,7 +991,13 @@ void ref_array_clear(struct ref_array *array)
  */
 int filter_refs(int (for_each_ref_fn)(each_ref_fn, void *), struct ref_filter_cbdata *data)
 {
-	return for_each_ref_fn(ref_filter_handler, data);
+	int ret;
+
+	ret = for_each_ref_fn(ref_filter_handler, data);
+	if (data->filter.merge_commit)
+		do_merge_filter(data);
+
+	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 a8980e7..622b942 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -28,6 +28,7 @@ struct ref_array_item {
 	unsigned char objectname[20];
 	int flag;
 	char *symref;
+	struct commit *commit;
 	struct atom_value *value;
 	char refname[FLEX_ARRAY];
 };
@@ -40,6 +41,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.2