From mboxrd@z Thu Jan 1 00:00:00 1970 From: Karthik Nayak Subject: [PATCH v6 10/11] ref-filter: implement '--contains' option Date: Thu, 25 Jun 2015 14:27:12 +0530 Message-ID: <1435222633-32007-10-git-send-email-karthik.188@gmail.com> References: <1435222633-32007-1-git-send-email-karthik.188@gmail.com> Cc: christian.couder@gmail.com, Matthieu.Moy@grenoble-inp.fr, gitster@pobox.com, Karthik Nayak To: git@vger.kernel.org X-From: git-owner@vger.kernel.org Thu Jun 25 10:58:12 2015 Return-path: Envelope-to: gcvg-git-2@plane.gmane.org Received: from vger.kernel.org ([209.132.180.67]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Z82z4-0000qv-8i for gcvg-git-2@plane.gmane.org; Thu, 25 Jun 2015 10:58:10 +0200 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752227AbbFYI6F (ORCPT ); Thu, 25 Jun 2015 04:58:05 -0400 Received: from mail-pd0-f182.google.com ([209.85.192.182]:36746 "EHLO mail-pd0-f182.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752168AbbFYI6A (ORCPT ); Thu, 25 Jun 2015 04:58:00 -0400 Received: by pdcu2 with SMTP id u2so49326681pdc.3 for ; Thu, 25 Jun 2015 01:58:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=JkPALbPpzNk4cBguttQ2sgibsy2FInk3nAFOqRgx0z8=; b=zUS9HoocKVTU3ogj36LAT3D/cBMfbbyMq6VMJ1REmp/qyxldXCRPlcwLMlKZAuo/l3 uCokS+lxwzoy5MbymCZUw7zAd8zdcks2F7TtnQLn9Sq1Op8FpBoU1oQvinABqanfYC5B W8XhgemAnao8dcCH0U1aghYqPDbGKJVf+ONR4kk4zhbtp9lCCDvw9nDt1tKB14AjPaG3 eWxoJ1vSQh2C0wYgMTdhsg7LEZdviKE9CA69nA84kMkljup/Y53GRXUi+qDZl1sEMtjz 7iTRtW6AY1rAK4CAydbb9+z9G5dUAl6QXsRegJIdY5aKHqNUiaYulH2JYQMyhRrQb+xw izPw== X-Received: by 10.70.48.229 with SMTP id p5mr16392867pdn.78.1435222680565; Thu, 25 Jun 2015 01:58:00 -0700 (PDT) Received: from ashley.localdomain ([106.51.130.23]) by mx.google.com with ESMTPSA id wa4sm29391000pab.17.2015.06.25.01.57.57 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Thu, 25 Jun 2015 01:57:59 -0700 (PDT) X-Mailer: git-send-email 2.4.4 In-Reply-To: <1435222633-32007-1-git-send-email-karthik.188@gmail.com> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Archived-At: '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 Mentored-by: Matthieu Moy Signed-off-by: Karthik Nayak --- ref-filter.c | 114 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- ref-filter.h | 3 ++ 2 files changed, 116 insertions(+), 1 deletion(-) diff --git a/ref-filter.c b/ref-filter.c index 2f20cb3..f793386 100644 --- a/ref-filter.c +++ b/ref-filter.c @@ -818,6 +818,114 @@ 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 contains_stack { + int nr, alloc; + struct contains_stack_entry { + struct commit *commit; + struct commit_list *parents; + } *contains_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_contains_stack(struct commit *candidate, struct contains_stack *contains_stack) +{ + ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc); + contains_stack->contains_stack[contains_stack->nr].commit = candidate; + contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents; +} + +static enum contains_result contains_tag_algo(struct commit *candidate, + const struct commit_list *want) +{ + struct contains_stack contains_stack = { 0, 0, NULL }; + int result = contains_test(candidate, want); + + if (result != CONTAINS_UNKNOWN) + return result; + + push_to_contains_stack(candidate, &contains_stack); + while (contains_stack.nr) { + struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1]; + struct commit *commit = entry->commit; + struct commit_list *parents = entry->parents; + + if (!parents) { + commit->object.flags |= UNINTERESTING; + contains_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; + contains_stack.nr--; + break; + case CONTAINS_NO: + entry->parents = parents->next; + break; + case CONTAINS_UNKNOWN: + push_to_contains_stack(parents->item, &contains_stack); + break; + } + } + free(contains_stack.contains_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); +} + /* * Return 1 if the refname matches one of the patterns, otherwise 0. * A pattern can be path prefix (e.g. a refname "refs/heads/master" @@ -908,10 +1016,14 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid, * obtain the commit using the 'oid' available and discard all * non-commits early. The actual filtering is done later. */ - if (filter->merge_commit) { + if (filter->merge_commit || filter->with_commit) { commit = lookup_commit_reference_gently(oid->hash, 1); if (!commit) return 0; + /* We perform the filtering for the '--contains' option */ + if (filter->with_commit && + !commit_contains(filter, commit)) + return 0; } /* diff --git a/ref-filter.h b/ref-filter.h index 7241a1d..3c59431 100644 --- a/ref-filter.h +++ b/ref-filter.h @@ -44,6 +44,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, @@ -51,6 +52,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.4