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

[PATCH 7/8] tag: use commit_contains

From
Jeff King <peff@peff.net>
Date
Jun 25, 2014, 23:49 UTC
Message-ID
<20140625234921.GG23146@sigill.intra.peff.net>
In-Reply-To
<20140625233429.GA20457@sigill.intra.peff.net>

The newly added commit_contains function should do a better job than our custom depth-first traversal. It should be the same speed when going close to the roots, but much faster when all tags are close to the searched-for commit (this usually isn't the case, but could be if you limit the tags with a pattern).

It also cleans up some of the more egregious pitfalls of the original implementation, including an abuse of the UNINTERESTING and TMP_MARK flags, an utterly confusing calling convention (it silently caches the bits between calls, with no checks that our "with_commit" was the same for each call), and a failure to clean up after itself (tainting any further traversals).

Signed-off-by: Jeff King <peff@peff.net>
---
The code to use the new contains function ends up disappointingly longer
than I would have hoped, but it has to massage our string_list of tag
names into a list of commits, and then massage the output back into a
filtered string list. It's not too bad, though. And as I mentioned, I
hope to eventually factor this out to share with for-each-ref and
branch.
 builtin/tag.c | 161 +++++++++++++++++-----------------------------------------
 1 file changed, 48 insertions(+), 113 deletions(-)
diff --git a/builtin/tag.c b/builtin/tag.c
index 3ef2fab..f17192c 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -72,108 +72,6 @@ static const unsigned char *match_points_at(const char *refname,
 	return NULL;
 }
 
-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;
-}
-
-enum contains_result {
-	CONTAINS_UNKNOWN = -1,
-	CONTAINS_NO = 0,
-	CONTAINS_YES = 1,
-};
-
-/*
- * 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;
-}
-
-/*
- * 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 void push_to_stack(struct commit *candidate, struct stack *stack)
-{
-	int index = stack->nr++;
-	ALLOC_GROW(stack->stack, stack->nr, stack->alloc);
-	stack->stack[index].commit = candidate;
-	stack->stack[index].parents = candidate->parents;
-}
-
-static enum contains_result contains(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 void show_tag_lines(const unsigned char *sha1, int lines)
 {
 	int i;
@@ -227,7 +125,7 @@ static void print_tag(const char *refname, const unsigned char *sha1,
 
 static int filter_can_stream(struct tag_filter *filter)
 {
-	return !filter->sort;
+	return !filter->sort && !filter->with_commit;
 }
 
 static int show_reference(const char *refname, const unsigned char *sha1,
@@ -236,16 +134,6 @@ static int show_reference(const char *refname, const unsigned char *sha1,
 	struct tag_filter *filter = cb_data;
 
 	if (match_pattern(filter->patterns, refname)) {
-		if (filter->with_commit) {
-			struct commit *commit;
-
-			commit = lookup_commit_reference_gently(sha1, 1);
-			if (!commit)
-				return 0;
-			if (!contains(commit, filter->with_commit))
-				return 0;
-		}
-
 		if (points_at.nr && !match_points_at(refname, sha1))
 			return 0;
 
@@ -258,6 +146,46 @@ static int show_reference(const char *refname, const unsigned char *sha1,
 	return 0;
 }
 
+static int util_is_not_null(struct string_list_item *it, int pos, void *data)
+{
+	return !!it->util;
+}
+
+static int matches_contains(struct string_list_item *it, int pos, void *data)
+{
+	unsigned char *contains = data;
+	return contains[pos];
+}
+
+static void limit_by_contains(struct string_list *tags, struct commit_list *with)
+{
+	struct commit_list *tag_commits = NULL, **tail = &tag_commits;
+	unsigned char *result;
+	int i;
+
+	for (i = 0; i < tags->nr; i++) {
+		struct string_list_item *it = &tags->items[i];
+		struct commit *c = lookup_commit_reference_gently(it->util, 1);
+		if (c)
+			tail = commit_list_append(c, tail);
+		else {
+			free(it->util);
+			it->util = NULL;
+		}
+	}
+	filter_string_list(tags, 0, util_is_not_null, NULL);
+
+	if (!tags->nr)
+		return;
+
+	result = xmalloc(tags->nr);
+	commit_contains(with, tag_commits, NULL, result);
+	filter_string_list(tags, 1, matches_contains, result);
+
+	free(result);
+	free_commit_list(tag_commits);
+}
+
 static int sort_by_version(const void *a_, const void *b_)
 {
 	const struct string_list_item *a = a_;
@@ -278,9 +206,16 @@ static int list_tags(const char **patterns, int lines,
 	filter.tags.strdup_strings = 1;
 
 	for_each_tag_ref(show_reference, (void *) &filter);
+	if (with_commit)
+		limit_by_contains(&filter.tags, with_commit);
 	if ((sort & SORT_MASK) == VERCMP_SORT)
 		qsort(filter.tags.items, filter.tags.nr,
 		      sizeof(struct string_list_item), sort_by_version);
+	if (sort) {
+		if ((sort & SORT_MASK) == VERCMP_SORT)
+			qsort(filter.tags.items, filter.tags.nr,
+			      sizeof(struct string_list_item), sort_by_version);
+	}
 	if (!filter_can_stream(&filter)) {
 		int i;
 		if (sort & REVERSE_SORT)

-- 
2.0.0.566.gfe3e6b2
Previous: Junio C HamanoNext: Jeff King
Message 23 of 26 in “use merge-base for tag --contains”
  1. 0/8 use merge-base for tag --containsJeff King, Jun 25, 2014
  2. 1/8 tag: allow --sort with -nJeff King, Jun 25, 2014
  3. 2/8 tag: factor out decision to stream tagsJeff King, Jun 25, 2014
  4. 3/8 paint_down_to_common: use prio_queueJeff King, Jun 25, 2014
  5. Junio C HamanoJul 1, 2014
  6. Jeff KingJul 1, 2014
  7. 4/8 add functions for memory-efficient bitmapsJeff King, Jun 25, 2014
  8. Torsten BögershausenJun 26, 2014
  9. Jeff KingJun 26, 2014
  10. Eric SunshineJun 29, 2014
  11. Jeff KingJun 30, 2014
  12. Junio C HamanoJul 1, 2014
  13. Jeff KingJul 1, 2014
  14. 5/8 string-list: add pos to iterator callbackJeff King, Jun 25, 2014
  15. Junio C HamanoJul 1, 2014
  16. Jeff KingJul 1, 2014
  17. 6/8 commit: provide a fast multi-tip contains functionJeff King, Jun 25, 2014
  18. Junio C HamanoJun 26, 2014
  19. Junio C HamanoJun 26, 2014
  20. Junio C HamanoJun 26, 2014
  21. Junio C HamanoJul 1, 2014
  22. Junio C HamanoJul 1, 2014
  23. 7/8 tag: use commit_containsJeff King, Jun 25, 2014
  24. 8/8 perf: add tests for tag --containsJeff King, Jun 25, 2014
  25. Jeff KingJun 26, 2014
  26. Jeff KingJun 26, 2014

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.