Re: [PATCH] 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.
>
> Signed-off-by: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>

> ---
> builtin/tag.c  | 83 
> ++++++++++++++++++++++++++++++++++++++++------------------
> t/t7004-tag.sh | 21 +++++++++++++++
> 2 files changed, 78 insertions(+), 26 deletions(-)
>
> diff --git a/builtin/tag.c b/builtin/tag.c
> index 9c3e067..4be67dd 100644
> --- a/builtin/tag.c
> +++ b/builtin/tag.c
> @@ -73,40 +73,71 @@ static int in_commit_list(const struct commit_list 
> *want, struct commit *c)
>  return 0;
> }
>
> -static int contains_recurse(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;
> - /* 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))
> - return 1;
> +struct commit_list_list {
> + struct commit *item;
> + struct commit_list *next_item;
> + struct commit_list_list *next;
> +};
>
> - if (parse_commit(candidate) < 0)
> - return 0;
> +static void mark_path(struct commit_list_list *path, int status)
> +{
> + struct commit_list_list *temp;
> + while (path) {
> + path->item->object.flags |= status;
> + temp = path;
> + path = temp->next;
> + free(temp);
> + }
> +}
>
> - /* 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;
> +static int contains(struct commit *candidate,
> +     const struct commit_list *want)
> +{
> + /* previously implemented with a recursion, but could stack overflow 
> in large repos */
> + struct commit_list_list *p, *tmp;
> + p = xmalloc(sizeof(struct commit_list_list));
> + p->item = candidate;
> + p->next_item = NULL;
> + p->next = NULL;
> +
> + while (p) {
> + candidate = p->item;
> +
> + /* is it ok : */
> + /* was it previously marked as containing a want commit? */
> + /* or are we it? */
> + if (candidate->object.flags & TMP_MARK || in_commit_list(want, 
> candidate)) {
> + mark_path(p, TMP_MARK);
>  return 1;
>  }
> + /* is it not ok : */
> + /* was it previously marked as not possibly containing a want 
> commit? */
> + /* do we have parents? */
> + if (candidate->object.flags & UNINTERESTING || 
> parse_commit(candidate) < 0 || !candidate->parents) {
> + candidate->object.flags |= UNINTERESTING;
> + /* then backtrack, marking as UNINTERESTING along the way */
> + while (p && !p->next_item) {
> + p->item->object.flags |= UNINTERESTING;
> + tmp = p;
> + p = tmp->next;
> + free(tmp);
> + }
> + if (p) {
> + p->item = p->next_item->item;
> + p->next_item = p->next_item->next;
> + }
> + } else {
> + /* let's check the parents */
> + tmp = xmalloc(sizeof(struct commit_list_list));
> + tmp->item = candidate->parents->item;
> + tmp->next_item = candidate->parents->next;
> + tmp->next = p;
> + p = tmp;
> + }
>  }
> - candidate->object.flags |= UNINTERESTING;
>  return 0;
> }
>
> -static int contains(struct commit *candidate, const struct 
> commit_list *want)
> -{
> - return contains_recurse(candidate, want);
> -}
> -
> static void show_tag_lines(const unsigned char *sha1, int lines)
> {
>  int i;
> diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
> index 5189446..196ac54 100755
> --- a/t/t7004-tag.sh
> +++ b/t/t7004-tag.sh
> @@ -1365,4 +1365,25 @@ test_expect_success 'multiple --points-at are 
> OR-ed together' '
>  test_cmp expect actual
> '
>
> +# what about a deep repo ?
> +
> +>expect
> +test_expect_success '--contains works in a deep repo' '
> + i=1
> + while test $i -lt 40000
> + do
> + echo "commit refs/heads/master
> +committer A U Thor <author@example.com> $((1000000000 + $i * 100)) 
> +0200
> +data <<EOF
> +commit #$i
> +EOF"
> + test $i == 1 && echo "from refs/heads/master^0"
> + i=$(($i + 1))
> + done | git fast-import
> + git checkout master
> + git tag far-far-away HEAD^
> + git tag --contains HEAD >actual &&
> + test_cmp expect actual
> +'
> +
> test_done
> -- 
> 1.8.0.msysgit.0.1.geed93bd.dirty
>
> --