diff options
author | Jean-Jacques Lafay <jeanjacques.lafay@gmail.com> | 2014-04-24 14:24:39 +0200 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2014-04-25 09:35:20 -0700 |
commit | cbc60b67201e083a4970c8731c5382a575357e36 (patch) | |
tree | 3272cd96773c56c647a03c3bf0f46f784eda4a32 /builtin | |
parent | 779792a5f24bb4e8049c4f88ad752e70d4a8a080 (diff) | |
download | git-cbc60b67201e083a4970c8731c5382a575357e36.tar.gz git-cbc60b67201e083a4970c8731c5382a575357e36.tar.xz |
git tag --contains: avoid stack overflow
In large repos, the recursion implementation of contains(commit,
commit_list) may result in a stack overflow. Replace the recursion with
a loop to fix it.
This problem is more apparent on Windows than on Linux, where the stack
is more limited by default.
See also this thread on the msysGit list:
https://groups.google.com/d/topic/msysgit/FqT6boJrb2g/discussion
[jes: re-written to imitate the original recursion more closely]
Thomas Braun pointed out several documentation shortcomings.
Tests are run only if ulimit -s is available. This means they cannot
be run on Windows.
Signed-off-by: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Tested-by: Stepan Kasal <kasal@ucw.cz>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'builtin')
-rw-r--r-- | builtin/tag.c | 90 |
1 files changed, 75 insertions, 15 deletions
diff --git a/builtin/tag.c b/builtin/tag.c index 6c7c6bde9..f3440023a 100644 --- a/builtin/tag.c +++ b/builtin/tag.c @@ -80,11 +80,19 @@ static int in_commit_list(const struct commit_list *want, struct commit *c) return 0; } -static int contains_recurse(struct commit *candidate, +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) { - struct commit_list *p; - /* was it previously marked as containing a want commit? */ if (candidate->object.flags & TMP_MARK) return 1; @@ -92,26 +100,78 @@ static int contains_recurse(struct commit *candidate, if (candidate->object.flags & UNINTERESTING) return 0; /* or are we it? */ - if (in_commit_list(want, candidate)) + if (in_commit_list(want, candidate)) { + candidate->object.flags |= TMP_MARK; return 1; + } if (parse_commit(candidate) < 0) return 0; - /* Otherwise recurse and mark ourselves for future traversals. */ - for (p = candidate->parents; p; p = p->next) { - if (contains_recurse(p->item, want)) { - candidate->object.flags |= TMP_MARK; - return 1; - } - } - candidate->object.flags |= UNINTERESTING; - return 0; + return -1; } -static int contains(struct commit *candidate, const struct commit_list *want) +/* + * 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) { - return contains_recurse(candidate, 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) |