From: "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: Junio C Hamano <gitster@pobox.com>,
Derrick Stolee <dstolee@microsoft.com>
Subject: [PATCH 03/16] commit-reach: move commit_contains from ref-filter
Date: Mon, 25 Jun 2018 14:01:28 -0400 [thread overview]
Message-ID: <b9687d2b21c4560178a509572770e3a058582a8b.1531746010.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.10.git.gitgitgadget@gmail.com>
From: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
commit-reach.c | 120 ++++++++++++++++++++++++++++++++++++++++
commit-reach.h | 18 +++++-
fast-import.c | 1 +
ref-filter.c | 147 +++----------------------------------------------
4 files changed, 146 insertions(+), 140 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index a6bc4781a..9e56f90ea 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -1,5 +1,6 @@
#include "cache.h"
#include "commit.h"
+#include "commit-graph.h"
#include "decorate.h"
#include "prio-queue.h"
#include "tree.h"
@@ -411,3 +412,122 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
unmark_and_free(used, TMP_MARK);
return found;
}
+
+/*
+ * 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 (!oidcmp(&want->item->object.oid, &c->object.oid))
+ return 1;
+ return 0;
+}
+
+/*
+ * Test whether the candidate 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,
+ struct contains_cache *cache,
+ uint32_t cutoff)
+{
+ enum contains_result *cached = contains_cache_at(cache, candidate);
+
+ /* If we already have the answer cached, return that. */
+ if (*cached)
+ return *cached;
+
+ /* or are we it? */
+ if (in_commit_list(want, candidate)) {
+ *cached = CONTAINS_YES;
+ return CONTAINS_YES;
+ }
+
+ /* Otherwise, we don't know; prepare to recurse */
+ parse_commit_or_die(candidate);
+
+ if (candidate->generation < cutoff)
+ return CONTAINS_NO;
+
+ return CONTAINS_UNKNOWN;
+}
+
+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_cache *cache)
+{
+ struct contains_stack contains_stack = { 0, 0, NULL };
+ enum contains_result result;
+ uint32_t cutoff = GENERATION_NUMBER_INFINITY;
+ const struct commit_list *p;
+
+ for (p = want; p; p = p->next) {
+ struct commit *c = p->item;
+ load_commit_graph_info(the_repository, c);
+ if (c->generation < cutoff)
+ cutoff = c->generation;
+ }
+
+ result = contains_test(candidate, want, cache, cutoff);
+ 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) {
+ *contains_cache_at(cache, commit) = CONTAINS_NO;
+ contains_stack.nr--;
+ }
+ /*
+ * If we just popped the stack, parents->item has been marked,
+ * therefore contains_test will return a meaningful yes/no.
+ */
+ else switch (contains_test(parents->item, want, cache, cutoff)) {
+ case CONTAINS_YES:
+ *contains_cache_at(cache, commit) = CONTAINS_YES;
+ 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, cache, cutoff);
+}
+
+int commit_contains(struct ref_filter *filter, struct commit *commit,
+ struct commit_list *list, struct contains_cache *cache)
+{
+ if (filter->with_commit_tag_algo)
+ return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
+ return is_descendant_of(commit, list);
+}
diff --git a/commit-reach.h b/commit-reach.h
index 35ec9f0dd..925cb05d7 100644
--- a/commit-reach.h
+++ b/commit-reach.h
@@ -2,6 +2,8 @@
#define __COMMIT_REACH_H__
#include "commit.h"
+#include "commit-slab.h"
+#include "ref-filter.h"
struct commit_list *get_merge_bases_many(struct commit *one,
int n,
@@ -19,7 +21,6 @@ int is_descendant_of(struct commit *commit, struct commit_list *with_commit);
int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference);
int in_merge_bases(struct commit *commit, struct commit *reference);
-
/*
* Takes a list of commits and returns a new list where those
* have been removed that can be reached from other commits in
@@ -40,4 +41,19 @@ void reduce_heads_replace(struct commit_list **heads);
int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
+/*
+ * Unknown has to be "0" here, because that's the default value for
+ * contains_cache slab entries that have not yet been assigned.
+ */
+enum contains_result {
+ CONTAINS_UNKNOWN = 0,
+ CONTAINS_NO,
+ CONTAINS_YES
+};
+
+define_commit_slab(contains_cache, enum contains_result);
+
+int commit_contains(struct ref_filter *filter, struct commit *commit,
+ struct commit_list *list, struct contains_cache *cache);
+
#endif
diff --git a/fast-import.c b/fast-import.c
index 3ea578102..4a93df383 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -171,6 +171,7 @@ Format of STDIN stream:
#include "packfile.h"
#include "object-store.h"
#include "mem-pool.h"
+#include "commit-reach.h"
#define PACK_ID_BITS 16
#define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
diff --git a/ref-filter.c b/ref-filter.c
index 9b2da8839..35b2d25ce 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -18,7 +18,7 @@
#include "trailer.h"
#include "wt-status.h"
#include "commit-slab.h"
-#include "commit-graph.h"
+#include "commit-reach.h"
static struct ref_msg {
const char *gone;
@@ -1623,144 +1623,6 @@ static int get_ref_atom_value(struct ref_array_item *ref, int atom,
return 0;
}
-/*
- * Unknown has to be "0" here, because that's the default value for
- * contains_cache slab entries that have not yet been assigned.
- */
-enum contains_result {
- CONTAINS_UNKNOWN = 0,
- CONTAINS_NO,
- CONTAINS_YES
-};
-
-define_commit_slab(contains_cache, enum contains_result);
-
-struct ref_filter_cbdata {
- struct ref_array *array;
- struct ref_filter *filter;
- struct contains_cache contains_cache;
- struct contains_cache no_contains_cache;
-};
-
-/*
- * 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 (!oidcmp(&want->item->object.oid, &c->object.oid))
- return 1;
- return 0;
-}
-
-/*
- * Test whether the candidate 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,
- struct contains_cache *cache,
- uint32_t cutoff)
-{
- enum contains_result *cached = contains_cache_at(cache, candidate);
-
- /* If we already have the answer cached, return that. */
- if (*cached)
- return *cached;
-
- /* or are we it? */
- if (in_commit_list(want, candidate)) {
- *cached = CONTAINS_YES;
- return CONTAINS_YES;
- }
-
- /* Otherwise, we don't know; prepare to recurse */
- parse_commit_or_die(candidate);
-
- if (candidate->generation < cutoff)
- return CONTAINS_NO;
-
- return CONTAINS_UNKNOWN;
-}
-
-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_cache *cache)
-{
- struct contains_stack contains_stack = { 0, 0, NULL };
- enum contains_result result;
- uint32_t cutoff = GENERATION_NUMBER_INFINITY;
- const struct commit_list *p;
-
- for (p = want; p; p = p->next) {
- struct commit *c = p->item;
- load_commit_graph_info(the_repository, c);
- if (c->generation < cutoff)
- cutoff = c->generation;
- }
-
- result = contains_test(candidate, want, cache, cutoff);
- 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) {
- *contains_cache_at(cache, commit) = CONTAINS_NO;
- contains_stack.nr--;
- }
- /*
- * If we just popped the stack, parents->item has been marked,
- * therefore contains_test will return a meaningful yes/no.
- */
- else switch (contains_test(parents->item, want, cache, cutoff)) {
- case CONTAINS_YES:
- *contains_cache_at(cache, commit) = CONTAINS_YES;
- 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, cache, cutoff);
-}
-
-static int commit_contains(struct ref_filter *filter, struct commit *commit,
- struct commit_list *list, struct contains_cache *cache)
-{
- if (filter->with_commit_tag_algo)
- return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
- return is_descendant_of(commit, list);
-}
-
/*
* Return 1 if the refname matches one of the patterns, otherwise 0.
* A pattern can be a literal prefix (e.g. a refname "refs/heads/master"
@@ -1987,6 +1849,13 @@ static int filter_ref_kind(struct ref_filter *filter, const char *refname)
return ref_kind_from_refname(refname);
}
+struct ref_filter_cbdata {
+ struct ref_array *array;
+ struct ref_filter *filter;
+ struct contains_cache contains_cache;
+ struct contains_cache no_contains_cache;
+};
+
/*
* A call-back given to for_each_ref(). Filter refs and keep them for
* later object processing.
--
gitgitgadget
next prev parent reply other threads:[~2018-07-16 13:00 UTC|newest]
Thread overview: 118+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-07-16 13:00 [PATCH 00/16] Consolidate reachability logic Derrick Stolee via GitGitGadget
2018-06-19 20:25 ` [PATCH 04/16] upload-pack: make reachable() more generic Derrick Stolee via GitGitGadget
2018-06-19 20:35 ` [PATCH 05/16] upload-pack: refactor ok_to_give_up() Derrick Stolee via GitGitGadget
2018-06-25 17:16 ` [PATCH 01/16] commit-reach: move walk methods from commit.c Derrick Stolee via GitGitGadget
2018-07-16 18:57 ` Stefan Beller
2018-07-16 21:31 ` Jonathan Tan
2018-06-25 17:35 ` [PATCH 02/16] commit-reach: move ref_newer from remote.c Derrick Stolee via GitGitGadget
2018-07-16 19:10 ` Stefan Beller
2018-06-25 18:01 ` Derrick Stolee via GitGitGadget [this message]
2018-07-16 19:14 ` [PATCH 03/16] commit-reach: move commit_contains from ref-filter Stefan Beller
2018-06-28 12:31 ` [PATCH 15/16] commit-reach: make can_all_from_reach... linear Derrick Stolee via GitGitGadget
2018-07-16 22:37 ` Stefan Beller
2018-07-17 1:16 ` Jonathan Tan
2018-10-01 19:16 ` René Scharfe
2018-10-01 19:26 ` Derrick Stolee
2018-10-01 20:37 ` René Scharfe
2018-10-04 22:59 ` René Scharfe
2018-10-05 12:15 ` Derrick Stolee
2018-10-05 16:51 ` Jeff King
2018-10-05 18:48 ` René Scharfe
2018-10-05 19:08 ` Jeff King
2018-10-05 19:36 ` René Scharfe
2018-10-05 19:42 ` Jeff King
2018-10-14 14:29 ` René Scharfe
2018-10-15 15:31 ` Derrick Stolee
2018-10-15 16:26 ` René Scharfe
2018-10-16 23:09 ` Junio C Hamano
2018-10-17 8:33 ` Jeff King
2020-11-18 2:16 ` Jonathan Nieder
2020-11-18 6:54 ` Jeff King
2020-11-18 17:47 ` René Scharfe
2018-10-05 19:12 ` Ævar Arnfjörð Bjarmason
2018-10-05 19:28 ` Jeff King
2018-10-05 19:42 ` Ævar Arnfjörð Bjarmason
2018-10-05 19:44 ` Jeff King
2018-07-12 20:47 ` [PATCH 06/16] upload-pack: generalize commit date cutoff Derrick Stolee via GitGitGadget
2018-07-16 19:38 ` Stefan Beller
2018-07-18 16:04 ` Derrick Stolee
2018-07-12 20:52 ` [PATCH 07/16] commit-reach: move can_all_from_reach_with_flags Derrick Stolee via GitGitGadget
2018-07-16 22:37 ` Jonathan Tan
2018-07-13 14:06 ` [PATCH 08/16] test-reach: create new test tool for ref_newer Derrick Stolee via GitGitGadget
2018-07-16 23:00 ` Jonathan Tan
2018-07-18 16:14 ` Derrick Stolee
2018-07-13 14:28 ` [PATCH 09/16] test-reach: test in_merge_bases Derrick Stolee via GitGitGadget
2018-07-13 14:38 ` [PATCH 10/16] test-reach: test is_descendant_of Derrick Stolee via GitGitGadget
2018-07-13 14:51 ` [PATCH 11/16] test-reach: test get_merge_bases_many Derrick Stolee via GitGitGadget
2018-07-16 21:24 ` Stefan Beller
2018-07-16 23:08 ` Jonathan Tan
2018-07-13 16:51 ` [PATCH 12/16] test-reach: test reduce_heads Derrick Stolee via GitGitGadget
2018-07-16 21:30 ` Stefan Beller
2018-07-16 21:59 ` Eric Sunshine
2018-07-13 17:22 ` [PATCH 13/16] test-reach: test can_all_from_reach_with_flags Derrick Stolee via GitGitGadget
2018-07-16 21:54 ` Stefan Beller
2018-07-18 16:54 ` Derrick Stolee
2018-07-17 0:10 ` Jonathan Tan
2018-07-13 18:37 ` [PATCH 14/16] commit-reach: replace ref_newer logic Derrick Stolee via GitGitGadget
2018-07-16 22:16 ` Stefan Beller
2018-07-13 19:25 ` [PATCH 16/16] commit-reach: use can_all_from_reach Derrick Stolee via GitGitGadget
2018-07-16 22:47 ` Stefan Beller
2018-07-16 13:54 ` [PATCH 00/16] Consolidate reachability logic Ramsay Jones
2018-07-16 16:18 ` Jeff King
2018-07-16 18:40 ` Eric Sunshine
2018-07-16 18:56 ` Jeff King
2018-07-16 18:59 ` Eric Sunshine
2018-07-18 12:32 ` Johannes Schindelin
2018-07-18 12:23 ` Johannes Schindelin
2018-07-18 19:21 ` Jeff King
2018-07-19 16:34 ` Johannes Schindelin
2018-07-16 17:26 ` Stefan Beller
2018-07-16 18:44 ` Eric Sunshine
2018-07-16 18:47 ` Derrick Stolee
2018-07-18 12:28 ` Johannes Schindelin
2018-07-18 15:01 ` Duy Nguyen
2018-07-18 17:01 ` Junio C Hamano
2018-07-18 17:11 ` Derrick Stolee
2018-07-19 16:37 ` Johannes Schindelin
2018-07-19 16:32 ` Johannes Schindelin
2018-07-20 16:33 ` [PATCH v2 00/18] " Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 01/18] commit-reach: move walk methods from commit.c Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 02/18] commit.h: remove method declarations Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 03/18] commit-reach: move ref_newer from remote.c Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 04/18] commit-reach: move commit_contains from ref-filter Derrick Stolee
2018-08-28 21:24 ` Jonathan Nieder
2018-08-28 21:33 ` Derrick Stolee
2018-08-28 21:36 ` [PATCH] commit-reach: correct accidental #include of C file Jonathan Nieder
2018-08-28 21:39 ` Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 05/18] upload-pack: make reachable() more generic Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 06/18] upload-pack: refactor ok_to_give_up() Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 07/18] upload-pack: generalize commit date cutoff Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 08/18] commit-reach: move can_all_from_reach_with_flags Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 09/18] test-reach: create new test tool for ref_newer Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 10/18] test-reach: test in_merge_bases Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 11/18] test-reach: test is_descendant_of Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 12/18] test-reach: test get_merge_bases_many Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 13/18] test-reach: test reduce_heads Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 14/18] test-reach: test can_all_from_reach_with_flags Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 15/18] test-reach: test commit_contains Derrick Stolee
2018-07-23 20:35 ` Jonathan Tan
2018-07-25 18:08 ` Junio C Hamano
2018-07-25 18:30 ` Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 16/18] commit-reach: replace ref_newer logic Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 17/18] commit-reach: make can_all_from_reach... linear Derrick Stolee
2018-07-23 20:41 ` Jonathan Tan
2018-08-01 20:41 ` Derrick Stolee
2018-09-12 4:14 ` Jeff King
2018-09-12 4:29 ` Jeff King
2018-09-12 13:08 ` Derrick Stolee
2018-07-20 16:33 ` [PATCH v2 18/18] commit-reach: use can_all_from_reach Derrick Stolee
2018-07-20 17:10 ` [PATCH v2 00/18] Consolidate reachability logic Stefan Beller
2018-07-20 17:15 ` Derrick Stolee
2018-07-20 22:16 ` Stefan Beller
2018-08-01 20:33 ` Derrick Stolee
2018-07-20 17:18 ` Derrick Stolee
2018-07-20 18:09 ` Eric Sunshine
2018-07-20 19:14 ` Derrick Stolee
2018-07-20 17:41 ` Duy Nguyen
2018-07-20 19:09 ` Derrick Stolee
2018-07-20 22:45 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=b9687d2b21c4560178a509572770e3a058582a8b.1531746010.git.gitgitgadget@gmail.com \
--to=gitgitgadget@gmail.com \
--cc=dstolee@microsoft.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).