From: Jeff King <peff@peff.net>
To: git@vger.kernel.org
Subject: [PATCH 7/8] tag: use commit_contains
Date: Wed, 25 Jun 2014 19:49:21 -0400 [thread overview]
Message-ID: <20140625234921.GG23146@sigill.intra.peff.net> (raw)
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
next prev parent reply other threads:[~2014-06-25 23:49 UTC|newest]
Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-06-25 23:34 [PATCH 0/8] use merge-base for tag --contains Jeff King
2014-06-25 23:35 ` [PATCH 1/8] tag: allow --sort with -n Jeff King
2014-06-25 23:35 ` [PATCH 2/8] tag: factor out decision to stream tags Jeff King
2014-06-25 23:39 ` [PATCH 3/8] paint_down_to_common: use prio_queue Jeff King
2014-07-01 16:23 ` Junio C Hamano
2014-07-01 17:10 ` Jeff King
2014-06-25 23:40 ` [PATCH 4/8] add functions for memory-efficient bitmaps Jeff King
2014-06-26 3:15 ` Torsten Bögershausen
2014-06-26 15:51 ` Jeff King
2014-06-29 7:41 ` Eric Sunshine
2014-06-30 17:07 ` Jeff King
2014-07-01 16:57 ` Junio C Hamano
2014-07-01 17:18 ` Jeff King
2014-06-25 23:42 ` [PATCH 5/8] string-list: add pos to iterator callback Jeff King
2014-07-01 17:45 ` Junio C Hamano
2014-07-01 19:00 ` Jeff King
2014-06-25 23:47 ` [PATCH 6/8] commit: provide a fast multi-tip contains function Jeff King
2014-06-26 18:55 ` Junio C Hamano
2014-06-26 19:19 ` Junio C Hamano
2014-06-26 19:26 ` Junio C Hamano
2014-07-01 18:16 ` Junio C Hamano
2014-07-01 19:14 ` Junio C Hamano
2014-06-25 23:49 ` Jeff King [this message]
2014-06-25 23:53 ` [PATCH 8/8] perf: add tests for tag --contains Jeff King
2014-06-26 0:01 ` Jeff King
2014-06-26 0:04 ` Jeff King
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20140625234921.GG23146@sigill.intra.peff.net \
--to=peff@peff.net \
--cc=git@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).