git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Karthik Nayak <karthik.188@gmail.com>
Date
Jul 7, 2015, 16:06 UTC
Message-ID
<1436285177-12279-10-git-send-email-karthik.188@gmail.com>
In-Reply-To
<1436285177-12279-1-git-send-email-karthik.188@gmail.com>

'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>
---
 builtin/tag.c |   5 +++
 ref-filter.c  | 114 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 ref-filter.h  |   3 ++
 3 files changed, 121 insertions(+), 1 deletion(-)
diff --git a/builtin/tag.c b/builtin/tag.c
index 767162e..071d001 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -86,6 +86,11 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
 	return 0;
 }
 
+/*
+ * The entire code segment for supporting the --contains option has been
+ * copied over to ref-filter.{c,h}. This will be deleted evetually when
+ * we port tag.c to use ref-filter APIs.
+ */
 enum contains_result {
 	CONTAINS_UNKNOWN = -1,
 	CONTAINS_NO = 0,
diff --git a/ref-filter.c b/ref-filter.c
index 148b7cd..dd0709d 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -818,6 +818,114 @@ 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"
@@ -922,10 +1030,14 @@ 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) {
+	if (filter->merge_commit || filter->with_commit) {
 		commit = lookup_commit_reference_gently(oid->hash, 1);
 		if (!commit)
 			return 0;
+		/* We perform the filtering for the '--contains' option */
+		if (filter->with_commit &&
+		    !commit_contains(filter, commit))
+			return 0;
 	}
 
 	/*
diff --git a/ref-filter.h b/ref-filter.h
index f115174..6bf27d8 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.5
Previous: Karthik NayakNext: Karthik Nayak
Message 11 of 18 in “add options to for-each-ref”
  1. 00/11 add options to for-each-refKarthik Nayak, Jul 7, 2015
  2. 01/11 t6302: for-each-ref tests for ref-filter APIsKarthik Nayak, Jul 7, 2015
  3. 02/11 tag: libify parse_opt_points_at()Karthik Nayak, Jul 7, 2015
  4. 03/11 ref-filter: implement '--points-at' optionKarthik Nayak, Jul 7, 2015
  5. 04/11 for-each-ref: add '--points-at' optionKarthik Nayak, Jul 7, 2015
  6. 05/11 ref-filter: add parse_opt_merge_filter()Karthik Nayak, Jul 7, 2015
  7. 06/11 ref-filter: implement '--merged' and '--no-merged' optionsKarthik Nayak, Jul 7, 2015
  8. 07/11 for-each-ref: add '--merged' and '--no-merged' optionsKarthik Nayak, Jul 7, 2015
  9. 08/11 parse-option: rename parse_opt_with_commit()Karthik Nayak, Jul 7, 2015
  10. 09/11 parse-options.h: add macros for '--contains' optionKarthik Nayak, Jul 7, 2015
  11. 10/11 ref-filter: implement '--contains' optionKarthik Nayak, Jul 7, 2015
  12. 11/11 for-each-ref: add '--contains' optionKarthik Nayak, Jul 7, 2015
  13. Torsten BögershausenJul 8, 2015
  14. Matthieu MoyJul 8, 2015
  15. Karthik NayakJul 8, 2015
  16. Matthieu MoyJul 8, 2015
  17. Karthik NayakJul 9, 2015
  18. 01/11 t6302: for-each-ref tests for ref-filter APIsKarthik Nayak, Jul 9, 2015

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.