From mboxrd@z Thu Jan 1 00:00:00 1970 From: Karthik Nayak Subject: [PATCH v7 10/11] ref-filter: implement '--contains' option Date: Thu, 2 Jul 2015 20:51:09 +0530 Message-ID: <1435850470-5175-10-git-send-email-karthik.188@gmail.com> References: <1435850470-5175-1-git-send-email-karthik.188@gmail.com> Cc: christian.couder@gmail.com, Matthieu.Moy@grenoble-inp.fr, Karthik Nayak To: git@vger.kernel.org X-From: git-owner@vger.kernel.org Thu Jul 02 17:22:34 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 1ZAgJs-0000Y7-BE for gcvg-git-2@plane.gmane.org; Thu, 02 Jul 2015 17:22:32 +0200 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753464AbbGBPW0 (ORCPT ); Thu, 2 Jul 2015 11:22:26 -0400 Received: from mail-pa0-f50.google.com ([209.85.220.50]:35557 "EHLO mail-pa0-f50.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753266AbbGBPWN (ORCPT ); Thu, 2 Jul 2015 11:22:13 -0400 Received: by pactm7 with SMTP id tm7so42020860pac.2 for ; Thu, 02 Jul 2015 08:22:13 -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=mE9J7ZpKdFpkdtQy+nCw1zlPytQx0EhdUu+VPO5zCdM=; b=q/UFF3aQHeT8H26Uq5n+5r8muROJ2K4GI0ZkGsfRkSnxQX9JjUrXDcP6Kz5sNTfjUk UEB+De3yykSfMtW5btZX08F6vAxlrhGlyPKLKfNP61jxN6IRuYxJId6EiNaV0ZFst6QA ZJ1zWVCDAW4OpHFkZbwBBKnWCN2dOFvl+5wbsa8sMaZMEoCsjy2POihiXAd23sh859Ec kSKMHIZGXRHVoI3snWK92TsVeOyz0b1mr7QJBmycZuSIVJ3uDs0YdJ/zeKaXAOimD681 YQIvLLDni8km7fu/2pimvVOKy7uTzJeu0OkqjgUb2AQq/vejnMzjUYQj3V4Ui/sRSF+2 YC3w== X-Received: by 10.66.119.239 with SMTP id kx15mr68315914pab.156.1435850533378; Thu, 02 Jul 2015 08:22:13 -0700 (PDT) Received: from ashley.localdomain ([106.51.130.23]) by mx.google.com with ESMTPSA id fu2sm635208pdb.32.2015.07.02.08.22.10 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Thu, 02 Jul 2015 08:22:12 -0700 (PDT) X-Mailer: git-send-email 2.4.4 In-Reply-To: <1435850470-5175-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 2bf8bf5..33e3ac0 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" @@ -921,10 +1029,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..0bfe05a 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