[PATCH 7/8] tag: use commit_contains

[Jeff King <peff@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