'tag -l' and 'branch -l' have two different ways of finding out if a certain ref contains a commit. Implement both these methods in ref-filter and give the caller of ref-filter API the option to pick which implementation to be used. 'branch -l' uses 'is_descendant_of()' from commit.c which is left as the default implementation to be used. 'tag -l' uses a more specific algorithm since ffc4b80. This implementation is used whenever the 'with_commit_tag_algo' bit is set in 'struct ref_filter'. Mentored-by: Christian Couder <christian.couder@xxxxxxxxx> Mentored-by: Matthieu Moy <matthieu.moy@xxxxxxxxxxxxxxx> Signed-off-by: Karthik Nayak <karthik.188@xxxxxxxxx> --- ref-filter.c | 114 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- ref-filter.h | 3 ++ 2 files changed, 115 insertions(+), 2 deletions(-) diff --git a/ref-filter.c b/ref-filter.c index 2be9df2..6c5f5c2 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -818,6 +818,113 @@ static void get_ref_atom_value(struct ref_array_item *ref, int atom, struct atom *v = &ref->value[atom]; } +enum contains_result { + CONTAINS_UNKNOWN = -1, + CONTAINS_NO = 0, + CONTAINS_YES = 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 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; +} + +/* + * 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; +} + +static void push_to_stack(struct commit *candidate, struct stack *stack) +{ + ALLOC_GROW(stack->stack, stack->nr + 1, stack->alloc); + stack->stack[stack->nr].commit = candidate; + stack->stack[stack->nr++].parents = candidate->parents; +} + +static enum contains_result contains_tag_algo(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 int commit_contains(struct ref_filter *filter, struct commit *commit) +{ + if (filter->with_commit_tag_algo) + return contains_tag_algo(commit, filter->with_commit); + return is_descendant_of(commit, filter->with_commit); +} /* * Given a refname, return 1 if the refname matches with one of the patterns * while the pattern is a pathname like 'refs/tags' or 'refs/heads/master' @@ -902,10 +1009,13 @@ int ref_filter_handler(const char *refname, const struct object_id *oid, int fla if (!match_points_at(&filter->points_at, oid->hash, refname)) return 0; - if(filter->merge_commit) { - commit = lookup_commit_reference_gently(sha1, 1); + if(filter->merge_commit || filter->with_commit) { + commit = lookup_commit_reference_gently(oid->hash, 1); if (!commit) return 0; + if(filter->with_commit && + !commit_contains(filter, commit)) + return 0; } /* diff --git a/ref-filter.h b/ref-filter.h index 622b942..c71704e 100644 --- a/ref-filter.h +++ b/ref-filter.h @@ -41,6 +41,7 @@ struct ref_array { struct ref_filter { const char **name_patterns; struct sha1_array points_at; + struct commit_list *with_commit; enum { REF_FILTER_MERGED_NONE = 0, @@ -48,6 +49,8 @@ struct ref_filter { REF_FILTER_MERGED_OMIT } merge; struct commit *merge_commit; + + unsigned int with_commit_tag_algo: 1; }; struct ref_filter_cbdata { -- 2.4.2 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html