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

[RFC/PATCH 8/9] ref-filter: add '--contains' option

From
Karthik Nayak <karthik.188@gmail.com>
Date
Jun 6, 2015, 20:04 UTC
Message-ID
<1433621052-5588-8-git-send-email-karthik.188@gmail.com>
In-Reply-To
<1433621052-5588-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, 115 insertions(+), 2 deletions(-)
diff --git a/ref-filter.c b/ref-filter.c
index 2be9df2..6c5f5c2 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 stack {
+	int nr, alloc;
+	struct stack_entry {
+		struct commit *commit;
+		struct commit_list *parents;
+	} *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_stack(struct commit *candidate, struct stack *stack)
+{
+	ALLOC_GROW(stack->stack, stack->nr + 1, stack->alloc);
+	stack->stack[stack->nr].commit = candidate;
+	stack->stack[stack->nr++].parents = candidate->parents;
+}
+
+static enum contains_result contains_tag_algo(struct commit *candidate,
+		const struct commit_list *want)
+{
+	struct stack stack = { 0, 0, NULL };
+	int result = contains_test(candidate, want);
+
+	if (result != CONTAINS_UNKNOWN)
+		return result;
+
+	push_to_stack(candidate, &stack);
+	while (stack.nr) {
+		struct stack_entry *entry = &stack.stack[stack.nr - 1];
+		struct commit *commit = entry->commit;
+		struct commit_list *parents = entry->parents;
+
+		if (!parents) {
+			commit->object.flags |= UNINTERESTING;
+			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;
+			stack.nr--;
+			break;
+		case CONTAINS_NO:
+			entry->parents = parents->next;
+			break;
+		case CONTAINS_UNKNOWN:
+			push_to_stack(parents->item, &stack);
+			break;
+		}
+	}
+	free(stack.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);
+}
 /*
  * Given a refname, return 1 if the refname matches with one of the patterns
  * while the pattern is a pathname like 'refs/tags' or 'refs/heads/master'
@@ -902,10 +1009,13 @@ 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(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 622b942..c71704e 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -41,6 +41,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,
@@ -48,6 +49,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.2
Previous: Karthik NayakNext: Karthik Nayak
Message 31 of 37 in “add options to ref-filter”
  1. 0/9 add options to ref-filterKarthik Nayak, Jun 6, 2015
  2. 1/9 tag: libify parse_opt_points_at()Karthik Nayak, Jun 6, 2015
  3. 2/9 ref-filter: implement '--points-at' optionKarthik Nayak, Jun 6, 2015
  4. Matthieu MoyJun 8, 2015
  5. Karthik NayakJun 8, 2015
  6. Matthieu MoyJun 8, 2015
  7. Karthik NayakJun 8, 2015
  8. 3/9 for-each-ref: add '--points-at' optionKarthik Nayak, Jun 6, 2015
  9. Matthieu MoyJun 8, 2015
  10. Karthik NayakJun 8, 2015
  11. Junio C HamanoJun 8, 2015
  12. Karthik NayakJun 9, 2015
  13. Junio C HamanoJun 9, 2015
  14. Karthik NayakJun 10, 2015
  15. Matthieu MoyJun 10, 2015
  16. Karthik NayakJun 10, 2015
  17. 4/9 parse-options: add parse_opt_merge_filter()Karthik Nayak, Jun 6, 2015
  18. Matthieu MoyJun 8, 2015
  19. Karthik NayakJun 8, 2015
  20. Junio C HamanoJun 8, 2015
  21. Karthik NayakJun 9, 2015
  22. 5/9 ref-filter: implement '--merged' and '--no-merged' optionsKarthik Nayak, Jun 6, 2015
  23. Matthieu MoyJun 8, 2015
  24. Karthik NayakJun 8, 2015
  25. 6/9 for-each-ref: add '--merged' and '--no-merged' optionsKarthik Nayak, Jun 6, 2015
  26. Matthieu MoyJun 8, 2015
  27. Karthik NayakJun 8, 2015
  28. 7/9 parse-options.h: add macros for '--contains' optionKarthik Nayak, Jun 6, 2015
  29. Junio C HamanoJun 8, 2015
  30. Karthik NayakJun 9, 2015
  31. 8/9 ref-filter: add '--contains' optionKarthik Nayak, Jun 6, 2015
  32. 9/9 for-each-ref: add '--contains' optionKarthik Nayak, Jun 6, 2015
  33. Junio C HamanoJun 8, 2015
  34. Karthik NayakJun 9, 2015
  35. Christian CouderJun 7, 2015
  36. Karthik NayakJun 8, 2015
  37. Junio C HamanoJun 8, 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.