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

[PATCH v4 10/19] ref-filter: implement '--contains' option

From
Karthik Nayak <karthik.188@gmail.com>
Date
Jun 21, 2015, 20:48 UTC
Message-ID
<1434919705-4884-10-git-send-email-karthik.188@gmail.com>
In-Reply-To
<1434919705-4884-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>
---
 ref-filter.c | 114 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 ref-filter.h |   3 ++
 2 files changed, 116 insertions(+), 1 deletion(-)
diff --git a/ref-filter.c b/ref-filter.c
index d62fa63..06f598b 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"
@@ -908,10 +1016,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 7241a1d..3c59431 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.439.gfea0c2a.dirty
Previous: Karthik NayakNext: Karthik Nayak
Message 33 of 37 in “add options to for-each-ref”
  1. 00/11 add options to for-each-refKarthik Nayak, Jun 21, 2015
  2. 01/19 t6301: for-each-ref tests for ref-filter APIsKarthik Nayak, Jun 21, 2015
  3. 02/19 tag: libify parse_opt_points_at()Karthik Nayak, Jun 21, 2015
  4. 03/19 ref-filter: implement '--points-at' optionKarthik Nayak, Jun 21, 2015
  5. Eric SunshineJun 22, 2015
  6. Karthik NayakJun 23, 2015
  7. 04/19 for-each-ref: add '--points-at' optionKarthik Nayak, Jun 21, 2015
  8. Junio C HamanoJun 22, 2015
  9. Karthik NayakJun 22, 2015
  10. Matthieu MoyJun 22, 2015
  11. Junio C HamanoJun 22, 2015
  12. Karthik NayakJun 22, 2015
  13. Junio C HamanoJun 22, 2015
  14. Eric SunshineJun 22, 2015
  15. Karthik NayakJun 23, 2015
  16. 05/19 ref-filter: add parse_opt_merge_filter()Karthik Nayak, Jun 21, 2015
  17. Junio C HamanoJun 22, 2015
  18. Matthieu MoyJun 22, 2015
  19. Junio C HamanoJun 22, 2015
  20. Karthik NayakJun 22, 2015
  21. 06/19 ref-filter: implement '--merged' and '--no-merged' optionsKarthik Nayak, Jun 21, 2015
  22. Junio C HamanoJun 22, 2015
  23. Karthik NayakJun 22, 2015
  24. 07/19 for-each-ref: add '--merged' and '--no-merged' optionsKarthik Nayak, Jun 21, 2015
  25. Eric SunshineJun 22, 2015
  26. Karthik NayakJun 23, 2015
  27. 08/19 parse-option: rename parse_opt_with_commit()Karthik Nayak, Jun 21, 2015
  28. Junio C HamanoJun 22, 2015
  29. Karthik NayakJun 22, 2015
  30. Junio C HamanoJun 22, 2015
  31. Karthik NayakJun 22, 2015
  32. 09/19 parse-options.h: add macros for '--contains' optionKarthik Nayak, Jun 21, 2015
  33. 10/19 ref-filter: implement '--contains' optionKarthik Nayak, Jun 21, 2015
  34. 11/19 for-each-ref: add '--contains' optionKarthik Nayak, Jun 21, 2015
  35. Karthik NayakJun 21, 2015
  36. Junio C HamanoJun 22, 2015
  37. Karthik NayakJun 22, 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.