'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.cou...@gmail.com>
Mentored-by: Matthieu Moy <matthieu....@grenoble-inp.fr>
Signed-off-by: Karthik Nayak <karthik....@gmail.com>
---
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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
